[devel] оптимизация сборочных зависимостей
Alexey Tourbin
=?iso-8859-1?q?at_=CE=C1_altlinux=2Eru?=
Чт Авг 31 00:29:06 MSD 2006
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.
Короче, должно быть уже ясно, что при наличии циклических зависимостей
удаляется *весь цикл*, т.е. вследствие некорректной оптимизации теряется
потенциально много пакетов.
Далее, я знаю, как обнаруживать циклы. Нужно сделать соединение ещё раз
само на себя и проверить, не совпадают ли начальный и конечный элементы.
Не понтяно правда, что потом делать с обнаруженными таким образом циклами.
----------- следующая часть -----------
Было удалено вложение не в текстовом формате...
Имя : =?iso-8859-1?q?=CF=D4=D3=D5=D4=D3=D4=D7=D5=C5=D4?=
Тип : application/pgp-signature
Размер : 189 байтов
Описание: =?iso-8859-1?q?=CF=D4=D3=D5=D4=D3=D4=D7=D5=C5=D4?=
Url : <http://lists.altlinux.org/pipermail/devel/attachments/20060831/224fe398/attachment-0001.bin>
Подробная информация о списке рассылки Devel