Перейти к содержимому






Фотография
* * * * * 2 голосов

Разрешение зависимостей в пакетном менеджере

Написано Fingercomp , в Пакетные менеджеры, Tutorials 22 Октябрь 2016 · 982 просмотров

programming algorithms package dependency resolve
Разрешение зависимостей в пакетном менеджере

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

 

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

 

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

 

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

 

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

{ "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
Изображение



  • Totoro, Sharplook, Kartze и еще 1 это нравится




Обратные ссылки на эту запись [ URL обратной ссылки ]

Обратных ссылок на эту запись нет

1 посетителей

0 пользователей, 1 гостей, 0 анонимных

Лицензия

Новые комментарии