On Wed, Aug 30, 2006 at 08:10:50PM +0400, Dmitry V. Levin wrote:
> > (Алгоритм оптимизации BuildRequires обсуждался вчера в частной
> > переписке.  Правда, спросонья я потерял к нему интерес.  Если это
> > интересно кому-то ещё, тогда можно перенести обсуждение сюда.)
> 
> Думаю, что лучше перенести сюда - вдруг среди нас есть специалист/практик
> по теории графов?

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

Дан список пакетов P.  Составим два отношения req<name,dep> и
prov<name,dep> (которые соответствуют rpm -q --requires и
rpm -q --provides).  Соединим req и prov по полю dep и сделаем
проекцию на prov<name>.  Получим список пакетов, которые
требуются какими-либо пакетами из исходного списка P.
Следовательно, эти пакеты можно удалить.

Пример.  Дано: glibc-core, sh.
req:
	sh	libc.so.6
	...
prov:
	glibc-core	libc.so.6
	...
Соединение:
	sh -> libc.so.6 -> glibc-core
Проекция:
	glibc-core

Следовательно, казалось бы, пакет glibc-core можно удалить.
Но это работает корректно не во всех случаях.

(Далее я поясняю на примерах, когда и почему это не работает.)

1) Рассмотрим пакет perl-base.  Одной из его особенностей является то,
что он почему то требует сам себя -- Requires: perl-base.  Получается
соединение perl-base -> perl-base -> perl-base и пакет совершенно
автоматически удаляется из списка.

Вот сам скрипт, с которым можно поиграться.

$ cat ./optimize_package_list
#!/bin/sh -ef
. tmpdir.sh
cd $TMPDIR
rpm -q --qf '[%{REQUIRENAME}\t%{NAME}\n]' -- "$@" >qR
rpm -q --qf '[%{PROVIDENAME}\t%{NAME}\n]' -- "$@" >qP
awk '{print$2,$1}' qR |sort -u -k2,2 -k1,1 -o qR
awk '{print$2,$1}' qP |sort -u -k2,2 -k1,1 -o qP
#head -v qR qP
join -j 2 -o 2.1 qR qP |sort -u >extrareq
awk '{print$1}' qR |sort -u >req
#head -v req extrareq
comm -23 req extrareq |xargs -r echo
$ ./optimize_package_list perl-base
$

(tmpdir.sh есть в пакете qa-robot)

2) Далее, рассмотрим пакеты perl-DateTime и perl-DateTime-TimeZone.
Эти пакеты зависят друг от друга, получается следующее соединение:

perl-DateTime -> perl(DateTime/TimeZone.pm) -> perl-DateTime-TimeZone
perl-DateTime-TimeZone -> perl(DateTime.pm) -> perl-DateTime

Опять получается, что все требуемые зависимости опять же предоставляются
самими этими пакетами, поэтому уже сразу два пакет, которые образуют
цикл, совершенно автоматически исключаются из списка.

$ ./optimize_package_list perl-DateTime perl-DateTime-TimeZone
$

Ясно, что 1) является частным случаем 2).  Это можно представить себе
как простую и сложную рекурсию.  При простой рекурсии фунция f вызывает
сама себя.  При сложной рекурсии функция f1 вызывает f2, которая в свою
очередь опять вызывает f1.

3) A requires B, B requires C, ..., X requires Y, Y requires A.

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

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