Greetings!

Дано: имеется список пакетов, полученный packagereq, БЕЗ учета текущей
оптимизации.  Список пакетов вычисляется на основе вывода strace и
получается очень большим.  Некоторая часть этого списка не содержит
полезной информации.  Задача: оптимизировать список пакетов.

Анализ текущего алгоритма оптимизации: если в списке есть пакеты с
названиями %name и %name-foo, то пакет %name удаляется из списка.
Если в списке есть пакеты с названиями lib%name и %name, то пакет
lib%name удаляется из списка.  Удаляются также все пакеты из списка
essential.

Недостатки текущего алгоритма: алгоритм не учитывает зависимости между
пакетами.  В результате 1) список пакетов остается перегруженным; 2)
алгоритм делает ошибки, если структура зависимостей не соответствует
описанным допущениям.

Примеры, которые демонстрируют недостатоки алгоритма:

$ packagereq -o /dev/stdout -- sh -c 'cat `rpm -ql perl-DBD-mysql libMySQL` &>/dev/null ||:'
packagereq: building requires list: libMySQL perl-DBD-mysql
libMySQL perl-DBD-mysql
$

Сейчас в сизифе есть два пакета с libmysqlclient.so.  perl-DBD-mysql
собран с одной из этих библиотек.  Впоследствии он может быть пересобран
с другой.  Зависимость в третьем пакете на libMySQL не нужна.

$ packagereq -o /dev/stdout -- sh -c 'cat `rpm -ql libpcre-devel libpcre` &>/dev/null ||:'
packagereq: building requires list: libpcre-devel libpcre-devel
$

Пакеты libpcre-devel и libpcre, увы, между собой не связаны.

Пример с пакетам ruby, который приводит к тому, что в минимальной
сборочной среде ruby отсутствует, я уже приводил.


Определения.

Прямая зависимость между пакетами: пакет A напрямую зависит от пакета B,
если на уровне RPM существует зависимость следующего типа:

%package -n A
Requires: B

Пример прямой зависимости:
$ rpm -q --requires libpcre-devel | grep pcre
libpcre3 = 4.4-alt1
$

Пакет pcre-devel напрямую зависит от libpcre3.


Прямая зависимость через виртуальный пакет: пакет A зависит от пакета B
через виртуальный пакет, если на уровне RPM существует зависимость
следующего типа:

%package -n A
Requires: package_B

%package -n B
Provides: package_B

Пример зависимости через виртуальный пакет:

$ rpm -q --requires perl-DBD-mysql | grep mysqlclient
libmysqlclient.so.12
$ rpm -q --whatprovides libmysqlclient.so.12
libMySQL-4.0.15-alt2
$

Пакет perl-DBD-mysql зависит от пакета libMySQL через виртуальный пакет
libmysqlclient.so.12.


Косвенная зависимость: любые зависимости с более сложной структурой не
рассматриваются.


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


Преимущества алгоритма: алгоритм лишен недостатков текущего алгоритма.

Недостаток алгоритма: результат зависит от порядка пакетов в списке.
Пример:

BuildRequires: XFree86-libs XFree86-devel XFree86-devel-static
		^-------------'     ^----------------'
Пакеты XFree86-libs и XFree86-devel будут по очереди удалены.

BuildRequires: XFree86-devel XFree86-devel-static XFree86-libs
			`----------------------------^
		^---------------------'
Первым будет удален пакет XFree86-devel; информация о том, что он
непосредственно зависит от XFree86-libs, будет потеряна.

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

Недостаток алгоритма: алгоритм не работает с виртуальными пакетами
(которые packagereq подставляет в соответствии с правилами
/etc/buildreqs/packages/substitute.d).  Обсуждение на канале привело
меня к мысли, что семантика виртуальных пакетов, которые предоставляются
несколькими другими пакетами, определена недостаточно хорошо.  Нужно
сформулировать правила использования виртуальных пакетов.

Прототип реализации прилагается.
Примеры работы прототипа:

$ perl rpm.pl libMySQL perl-DBD-mysql
        perl-DBD-mysql requires libMySQL through libmysqlclient.so.12
                libMySQL optimized out
perl-DBD-mysql

$ perl rpm.pl libpcre3 libpcre libpcre-devel
        libpcre-devel requires libpcre3
                libpcre3 optimized out
libpcre libpcre-devel

$ perl rpm.pl XFree86-libs XFree86-devel XFree86-devel-static
        XFree86-devel requires XFree86-libs through libX11.so.6
                XFree86-libs optimized out
        XFree86-devel-static requires XFree86-devel
                XFree86-devel optimized out
XFree86-devel-static