Менеджер пакетов для SB-дистрибутива

[Devoter]

Создавая эту тему, я бы не хотел увидеть здесь бессмысленных рассуждений по поводу смысла создания еще одного менеджера или того больше - дистрибутива. Так что желающим поговорить об этом ждут другие разделы форума.
Хотелось бы спросить следующее: имеется некоторое древо пакетов (думаю, всем это ясно), а также - конфигурационные файлы (по типу тех же ebuild'ов в gentoo), + база данных, со списком все установленных пакетов (загрузку из репозиториев, распаковку, конфигурирование пока обсуждать не будем). И есть конкретный пакет, который пользователь хочет установить.
Вопрос в том: как определнить все зависимости (ближайшие зависимости известны) для данного пакета, чтобы установить их.
Например:
pack1 - ближайшие зависимости - pack1.1, pack1.2
pack1.1 - ближайшие зависимости pack1.1.1, pack 1.1.2
pack 1.2 - ближайшие зависимости pack1.2.1, pack 1.1.2

нужно установить пакет pack1.
предполагаю такой алгоритм работы:
1. Чтение ближайших зависимостей и поиск их в БД установленных пакетов
2. Если не все зависимости установлены то
2.1. Переход к первой зависимости, а далее - к П.1.
2.2. Переход к П.2.
3. Установка пакета.

То есть, мой алгоритм работает через рекурсию.
Мне бы хотелось узнать другие способы, чтоб так сильно не грузить память.
Заранее благодарен.

[NickLion]

ИМХО, критичнее не память (она все-равно неплохо будет жраться), а скорость разрешения зависимостей. Можно рассмотреть множество пакетов и их зависимостей как ориентированный граф. Т.о. разрешение зависимостей - распространение от данной вершины-пакета по всем ребрам-зависимостям в вершины, которые помечены как неустановленные. А само распространение реализуем рекурсией - поиск в глубину либо очередью - поиск в ширину. Заранее подумайте о циклических зависимостях. А еще есть пакеты несовместимые друг с другом.

[NickLion]

Тут подумал, в общем случае зависимости могут быть посложнее. Например - пакет А зависит от Б или В. Соответственно, если мы, к примеру, убираем по каким-то несовместимостям пакет Б, то надо будет поставить для пакета А пакет В. А еще заранее введите поняти установленного и установленного по зависимостям пакета. Тогда висячие установленные по зависимостям пакеты можно будет убирать. Сделать автоматическую сборку мусора

[Portnov]

В общих чертах - рекурсия с мемоизацией. Т.е. вероятно будет частой такая схема (A -> B означает что A зависит от B):

A -> B; A -> C; B -> D; C -> D;

(часто такое называют "ромбовидной зависимостью"). Так вот, когда мы в первый раз доходим (скажем, по цепочке A -> B -> D) до выяснения зависимостей пакета D, их надо запомнить, чтобы не вычислять их заново, когда придём в ту же точку по цепочке A -> C -> D или ещё какой.

[Devoter]

Ну это ежу понятно

[nesk]

А почему бы не посмотреть, как это уже реализовано?
Как говориться: хочешь научиться программировать - сделай дизассемблер возьми исходники, посмотри как это делают другие.

[NickLion]

А почему бы не посмотреть, как это уже реализовано?
Как говориться: хочешь научиться программировать - сделай дизассемблер возьми исходники, посмотри как это делают другие.

Совет хороший, но есть один минус - часто за оптимизациями не всегда можно увидеть основной алгоритм. Поэтому, имхо, лучше сначала все же самому реализовать, потыкаться носом во все подводные камни, понять что собственно надо, а затем смотреть как это сделано у других.

[Devoter]

Пытался как-то разобраться в исходниках portage - честно говоря, ничего хорошего из этого не вышло, возможно потому что тогда был слабо знаком с этой кухней.
А вот насчет замены рекурсивного метода на очередь подумаю.
Возможно, такой подход не самый красивый, но должен меньше ресурсов требовать.
Да и мысли кое какие уже имеются.
Кстати, о конфликтах. Если взять в расчет тот факт, что менеджер пишется для SB-дистрибутива, то можно и предположить, что конфликтующие пакеты можно просто-напросто устанавливать в разные директории (если требуется использование именно обоих пакетов).
Пока проект на стадии составления и проработки алгоритма, так что принимаются все возможные советы.

[Devoter]

Вообще, если кто-то хочет принять участие в обсуждении проекта - открыл сегодня сайт на эту тему - retech.ucoz.org. Заходите.
P.S.: Товарищи-модераторы, это - не реклама, а просто предложение по обсуждению.

[watashiwa_daredeska]

Вообще говоря, это задача о топологической сортировке. По этим ключевым словам можно найти кучу описаний и реализаций.

На правах оффтопика. Задача о простом удовлетворении зависимостей -- не самая сложная и интересная в деле управления пакетами.

В общих чертах - рекурсия с мемоизацией.

На императивных языках эту задачу обычно решают очередью и set'ом.

[svary]

Вообще говоря, это задача о топологической сортировке.

Мне кажется (насколько я помню теорию графов), что это задача об обходе графа. Не обязательно дерева и даже не обязательно - связного.
Вот здесь можно посмотреть :
Обходы графа в глубину и в ширину.
Еще на эту тему книжка хорошая есть :
Теория графов. Алгоритмический подход

[Devoter]

Мысли уже кое-какие сложились (они изложены на сайте проекта), а за ссылки - спасибо, обязательно прочту.

[watashiwa_daredeska]

Мне кажется (насколько я помню теорию графов), что это задача об обходе графа.

Это не обход графа, а именно топологическая сортировка.

Не обязательно дерева

Граф зависимостей, в идеале, бесконтурный ориентированный. Бывают, конечно, аномалии, когда A->B, B->A и в бинарных дистрибутивах по правилам работы с пакетами такие аномалии разрешимы -- надо просто ставить оба пакета. Правда, опять же в бинарных дистрибутивах, есть зависимости разных типов. Если в этом аномальном контуре A predepends B и B predepends A, то такой контур неразрешим, и даже если только одна из этих двух зависимостей predepends -- тоже.

не обязательно - связного.

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

[Devoter]

Учту ваши предложения обязательно.

[Devoter]

С алгоритмом установки пакетов и поиска зависимостей успокоился - сделал.
Теперь думаю над тем, как бы корректно удалять пакеты.
И вот еще попутный вопрос:
Далеко не во всех пакетах предусмотрена команда make uninstall. Вот и вопрос: как организовать корректное удаление пакетов, без использования этой самой команды? Возможно, есть утилита-фильтр позволяющая проследить копирование или перемещение файлов из заданной директории и ее поддиректорий, и куда. Чтобы эти данные где-то сохранить.

[watashiwa_daredeska]

думаю над тем, как бы корректно удалять пакеты.

Вот тут и начинается основное веселье в МП :) Размер веселья зависит от смысла, вкладываемого в слово "корректно".

как организовать корректное удаление пакетов, без использования этой самой команды?

checkinstall. make [un]install не подходят по любому, даже если они есть.

[Devoter]

Я тут погуглил и пришел к выводу, что необходимо сперва устанавливать пакет в мнимый корень, только тогда, там уже сохранять пути, а потом копировать в нормальную директорию. Только вопрос в том: как заставить make install игнорировать параметр --prefix=/usr (к примеру) и заставлять ее копировать файлы в другую папку.

[Devoter]

Нашел решение в Gentoo'шном скрипте emake.
Вроде бы скрипт короткий, я его даже немного подрезал, дабы убрать лишние переменные, но все равно не могу понять: как он работает.
Догадки имеются, но хотелось бы детального объяснения.
Насколько я понял: он каждый файл, который передается в install через make подправляет и вместо префикса вставляет адрес указанной директории.

Код: Выделить всё

#!/bin/bash
( for arg in ${MAKE:-make} "$@"; do
    [[ ${arg} == *" "* ]] \
        && printf "'%s' " "${arg}" \
        || printf "%s " "${arg}"
done
printf "\n"
) >&2

exec ${MAKE:-make} "$@"