Раз уж я тут пишу понемногу свой крутой пакетный манагёр, расскажу о пакетных менеджерах немного.

Пакетный менеджер — штука сложная. Потому что, хотя задача у него, в общем-то, одна — менеджировать пакеты — сюда включается и установка, и удаление, и обновление, и, вообще, много всякого. Но а так как пока сам не напишешь, ПМ не поймёшь, здесь расскажу об установке пакетов и зависимостей с кодом.

Ещё немного предисловий, о зависимостях. Это ключевая фича ПМ: вы-то прогу скопировать/разархировать и сами можете, вот только если программа зависит от другой, а та — от двух других, и т. д., вам это надоест. Людям надоело. Создали пакетные менеджеры. Теперь программы пакуются в пакеты — а рядом со скомпилированными бинарниками лежит ещё кусок информации: имя пакета, версии, зависимости, авторы, изменения и много-много всяких других полей. При установке данные считываются и далее уже делается, что сказано. Зависимости ли ставятся, ещё ли что-нибудь.

А затем пакетов становится много, появляются репозитории полноценные, ну и так далее.

Итак, давайте сделаем программу для установки пакетов. Ну, почти. Именно полезной нагрузки как таковой не будет, будем использовать такую структуру информации о пакете (назовём это манифестом пакета):

{ "name": "имя пакета", "files":  [ { "url": "http://example.com/bin-1", "path": "/usr/bin/program1" }  , { "url": "http://example.com/library-1.so", "path": "/usr/lib/library1.so" }  ]}

Пока без зависимостей, всё просто.

Вот такой код получим:

def install(name):  # получаем манифест пакета с данным именем  manifest = getManifest(name)   # проходимся по файлам...  for file in manifest["files"]:    # ...скачиваем и ставим их в нужные места    download(url=file["url"], path=file["path"])

Ничего примечательного, на самом деле. Получаем манифест, скачиваем файлы и пишем "тадаам".

Давайте сделаем вот такие манифесты:

{ "name": "pkg1"  # имя пакета, "deps":  # зависимости  [ { "name": "pkg1-1" }  , { "name": "pkg1-2" }  ], "files": [ { "url": "http://example.com/pkg1/file", "path": "/opt/pkg1/file" } ]} { "name": "pkg1-1", "deps": [ { "name": "pkg1-1-1" } ], "files":  [ { "url": "http://example.com/pkg1-1/file1", "path": "/opt/pkg1-1/file1" }  , { "url": "http://example.com/pkg1-1/file2", "path": "/opt/pkg1-1/file2" }  ]} { "name": "pkg1-1-1", "deps": [], "files": [ { "url": "http://example.com/pkg1-1-1/file", "path": "/opt/pkg1-1-1/file" } ] { "name": "pkg1-2", "deps": [], "files":  [ { "url": "http://example.com/pkg1-2/file1", "path": "/opt/pkg1-2/file1" }  , { "url": "http://example.com/pkg1-2/file2", "path": "/opt/pkg1-2/file2" }  ]}

У нас есть 4 пакета: pkg1, pkg1-1, pkg1-1-1, pkg1-2. Вот граф зависимостей:

Очевидно, что просто так теперь тут в рандомном порядке пакеты поставить нельзя. Так как при установке пакета, например, pkg1-1, он совершенно справедливо считает, что его зависимость, pkg1-1-1, уже установлена.

То есть, по-хорошему, нам надо сначала брать пакеты без неразрешённых зависимостей, и подниматься вверх. Однако, есть идея покруче.

Я сейчас наваяю рекурсивную функцию resolveDeps, которая будет, как ни странно, разрешать зависимости:

def resolveDeps(name):  result = []  # результатирующая последовательность установки пакетов  manifest = getManifest(name)  for dep in manifest["deps"]:    # В Python справедливен код типа `[1, 2, 3] + [4, 5, 6] == [1, 2, 3, 4, 5, 6]`, т.е. склеиваение списков.    result = resolveDeps(dep["name"]) + result  return result

Если мы дадим ей манифесты, она выдаст вот такой список: ["pkg1-1-1", "pkg1-1", "pkg1-2", "pkg1"] — от менее сложного к более сложному. То, что нужно. Затем мы ставим просто их:

for pkg in resolveDeps("pkg1"):  install(pkg)

Давайте улучшим алгоритм. Сделаем проверку на установленность: нам ведь не надо повторно скачивать файлы, которые уже есть.

def resolveDeps(name):  result = []  # Проверяем, установлен ли пакет  if not isInstalled(name):    manifest = getManifest(name)    for dep in manifest["deps"]:      result = resolveDeps(dep["name"]) + result  return result

Если у нас уже поставлен pkg1-1, то получим всего лишь ["pkg1-2", "pkg1"]. Круто!

Возьмём другой граф:

Как видно, от pkg1-1-1 зависят сразу 2 пакета: pkg1-1 и pkg1-2. Проблема в том, что на выходе у нас будет ["pkg1-1-1", "pkg1-1-1", "pkg1-1", "pkg1-2", "pkg1"] — ни разу не то, что мы хотели. Давайте это исправим:

def resolveDeps(name, resolved=None):  resolved = resolved or []  # список уже разрешённых пакетов  if name in resolved:    # Пакет уже был разрешён, ничего больше не требуется    return resolved  if not isInstalled(name):    manifest = getManifest(name)    for dep in manifest["deps"]:      resolveDeps(dep["name"], resolved)  # Теперь список один на всю рекурсию    resolved.append(name)  # Без рекурсии сюда попасть можно, если пакет не имеет неустановленных зависимостей  return resolved

Теперь выхлоп у нас ["pkg1-1-1", "pkg1-1", "pkg1-2", "pkg1"] — как и предписывали.

А вот вам ещё граф:

Какая тут засада? А у нас дерево циркулярное — не руки циркуляркой отрезает, а в бесконечную рекурсию вводит. Вот как можно этого избежать:

def resolveDeps(name, resolved=None, unresolved=None):  resolved = resolved or []  unresolved = unresolved or []  # список ещё не разрешённых пакетов  if name in unresolved:    # Мы попали сюда через рекурсию. Когда-то пакет уже был добавлен в список unresolved,    # после чего функция ушла в рекурсивное разрешение зависимостей этого пакета.    # Какой-то из зависимостей в итоге опять имеет данный пакет как зависимость.    # Это ошибка, такого быть не должно, паникуем.    raise ValueError("circular dependencies detected")  if name in resolved:    # Пакет уже был разрешён, ничего больше не требуется    return resolved  unresolved.append(name)  if not isInstalled(name):    manifest = getManifest(name)    for dep in manifest["deps"]:      resolveDeps(dep["name"], resolved, unresolved)  # даём unresolved    resolved.append(name)  # Не забываем убирать из списка  del unresolved[unresoved.index(name)]  return resolved

Теперь у нас в данном графе будет сгенерировано исключение, а потому рекурсии бесконечной не произойдёт.

Итак, у нас есть простая функция, которая составляет список пакетов для последовательной установки без ломаний. Это уже круто, но время шло, и появилось такое явление как версии. Впрочем, об этом поговорим в другой раз. Там есть свои заморочки, с которыми нужно разобраться.

Вот похожая статья, но на английском. Рекомендую ознакомиться.

Лицензия: CreativeCommons Attribution-NonCommercial 4.0 International License