Разрешение зависимостей в пакетном менеджере
Раз уж я тут пишу понемногу свой крутой пакетный манагёр, расскажу о пакетных менеджерах немного.
Пакетный менеджер — штука сложная. Потому что, хотя задача у него, в общем-то, одна — менеджировать пакеты — сюда включается и установка, и удаление, и обновление, и, вообще, много всякого. Но а так как пока сам не напишешь, ПМ не поймёшь, здесь расскажу об установке пакетов и зависимостей с кодом.
Ещё немного предисловий, о зависимостях. Это ключевая фича ПМ: вы-то прогу скопировать/разархировать и сами можете, вот только если программа зависит от другой, а та — от двух других, и т. д., вам это надоест. Людям надоело. Создали пакетные менеджеры. Теперь программы пакуются в пакеты — а рядом со скомпилированными бинарниками лежит ещё кусок информации: имя пакета, версии, зависимости, авторы, изменения и много-много всяких других полей. При установке данные считываются и далее уже делается, что сказано. Зависимости ли ставятся, ещё ли что-нибудь.
А затем пакетов становится много, появляются репозитории полноценные, ну и так далее.
Итак, давайте сделаем программу для установки пакетов. Ну, почти. Именно полезной нагрузки как таковой не будет, будем использовать такую структуру информации о пакете (назовём это манифестом пакета):
{ "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
-
3
0 комментариев
Рекомендуемые комментарии
Нет комментариев для отображения