Как менеджеры пакетов (aptitude, yum, portage) строят свои деревья зависимостей?
-
10-07-2019 - |
Вопрос
Я понимаю основные концепции, но используются ли какие-либо специальные алгоритмы или, может быть, какие-то блоги, статьи или даже книги по этой теме для тех, кто строит свою собственную систему?Кажется, существует очень мало информации о фактическом внедрении такой системы.
Решение
Само дерево зависимостей несложно загрузить: все, что вам нужно, — это некоторое сопоставление ключей (например, имен) с объектами.
Вы не указали язык, поэтому я выбрал Python.Ожидаемый ввод — это файл строк в форме «[имя]:[зависимости, разделенные пробелами]».
def load_depends(file):
depends = {}
for line in file:
line = line.strip()
if not line or line.startswith("#"): # allow blanks and comments
continue
name, _, deps = line.partition(":")
deps = deps.strip()
assert deps, "invalid input" # most basic input error-checking
depends[name] = set(deps.split())
return depends
В этом коде предполагается, что любой элемент, не указанный в списке, не имеет никаких зависимостей, и при желании вы можете перемещаться по дереву и добавлять пустые записи.По крайней мере, вам следует проверить наличие рекурсивных зависимостей.
Пример:
>>> input = """\
... a: b c
... b: c
... c: d
... e: a
... """.split("\n")
>>> from pprint import pprint
>>> pprint(load_depends(input))
{'a': set(['b', 'c']),
'b': set(['c']),
'c': set(['d']),
'e': set(['a'])}
[Примечание:Я использую ярлык, поскольку на самом деле мне нужен не файл строк, а итерация строк (которой соответствует файл), поэтому я передаю список строк в функцию.]
Вы можете создавать всевозможные функции поверх этой базовой структуры и инкапсулировать ее и эти концепции (например, «зависит», «рекомендует», «предлагает», даже «конфликты» или «заменяет» и т. д.) в различные объекты, специфичные для вашей системы.
Другие советы
Многие другие концепции также включают в себя деревья зависимостей, такие как разрешение MIB SNMP, компиляция исходного кода C/C++.Так что вы можете ссылаться на любые другие материалы, в которых говорится об этом :)