[devel] оптимизация сборочных зависимостей

[Alexey Tourbin]

On Thu, Aug 31, 2006 at 01:17:07AM +0400, Dmitry V. Levin wrote:
> On Thu, Aug 31, 2006 at 12:57:49AM +0400, Damir Shayhutdinov wrote:
> > > Далее, я знаю, как обнаруживать циклы.  Нужно сделать соединение ещё раз
> > > само на себя и проверить, не совпадают ли начальный и конечный элементы.
> > > Не понтяно правда, что потом делать с обнаруженными таким образом циклами.
> > Заменять на любой пакет из цикла - то есть, как говорил Сергей,
> > схлопывать циклы в одну вершину.
> 
> На любой пакет из цикла нельзя по двум причинам:
> 1. некоторые вершины есть виртуальные пакеты, их оставлять нехорошо;

Это решается соединением requires на provides.

Здесь есть более тонкая проблема, о которой написал vsu.  Если нечто
предоставляется двумя разными пакетами из списка, тогда теряется
уверенность, что можно сразу два эти пакета выкинуть.  Ибо впоследствии
в сборочном чруте может оказаться только один из них.

Правда, я пока не успел столкнуться с этой проблемой.  Её можно решить
грубо, учитывая каждый provides только один раз, то есть типа вот так:

--- /usr/bin/packagereq-	2006-09-05 07:11:28 +0000
+++ /usr/bin/packagereq	2006-09-05 14:07:27 +0000
@@ -154,7 +154,7 @@ sort -k1,1 -k2,2 -u -o "$WORKDIR"/Rn "$W
 # make list of provides
 cat "$WORKDIR"/n |
 	xargs -r rpmquery --qf '[%{PROVIDENAME}\t%{NAME}\n]' -- >"$WORKDIR"/Pn
-sort -k1,1 -k2,2 -u -o "$WORKDIR"/Pn "$WORKDIR"/Pn
+sort -k1,1 -u -o "$WORKDIR"/Pn "$WORKDIR"/Pn
 # make list of package pairs where first depends on second
 join -j 1 -o '1.2 2.2' "$WORKDIR"/Rn "$WORKDIR"/Pn |
 	sort -u >"$WORKDIR"/nn

(Но можно и не решать.:)

> 2. некоторые вершины могут принадлежать нескольким цепочкам, таким
> вершинам следует отдавать приоритет.

А вот с этой проблемой я уже столкнулся, причем дважды в одном пакете.
Проблема состоит в том, что из-за произвольного (относительно предметной
области) разрыва циклов в tsort список пакетов получается неоптимальным
(т.е. в результате в нём присутствуют лишние элементы).

Это пакет perl-XML-Feed.

packagereq: building requires list: tsort: -: input contains a loop:
tsort: perl-XML-SAX
tsort: perl-XML-LibXML
tsort: -: input contains a loop:
tsort: perl-HTML-Parser
tsort: perl-libwww
tsort: -: input contains a loop:
tsort: perl-DateTime-TimeZone
tsort: perl-DateTime

Вот список nn:

bzip2 bzlib
bzip2 glibc-core
bzlib glibc-core
coreutils glibc-core
coreutils sh
findutils glibc-core
findutils sh
glibc-core setup
glibc-gconv-modules glibc-core
glibc-locales glibc-core
glibc-locales sh
glibc-nss glibc-core
libbeecrypt glibc-core
libdb4.4 glibc-core
libelf glibc-core
libexpat glibc-core
libexpat sh
libpopt glibc-core
librpm bzlib
librpm glibc-core
librpm libbeecrypt
librpm libdb4.4
librpm libelf
librpm libpopt
librpm zlib
librpmbuild glibc-core
librpmbuild librpm
libxml2 glibc-core
libxml2 zlib
make glibc-core
make sh
perl-Compress-Zlib glibc-core
perl-Compress-Zlib perl-base
perl-Compress-Zlib zlib
perl-DateTime glibc-core
perl-DateTime perl-DateTime-Locale
perl-DateTime perl-DateTime-TimeZone
perl-DateTime perl-Params-Validate
perl-DateTime perl-base
perl-DateTime-Format-Mail perl-DateTime
perl-DateTime-Format-Mail perl-Params-Validate
perl-DateTime-Format-W3CDTF perl-DateTime
perl-DateTime-Locale perl-Params-Validate
perl-DateTime-Locale perl-base
perl-DateTime-TimeZone perl-DateTime
perl-DateTime-TimeZone perl-Params-Validate
perl-DateTime-TimeZone perl-base
perl-Encode glibc-core
perl-Encode perl-base
perl-ExtUtils-AutoInstall perl-base
perl-ExtUtils-AutoInstall perl-devel
perl-Feed-Find perl-Class-ErrorHandler
perl-Feed-Find perl-HTML-Parser
perl-Feed-Find perl-URI
perl-Feed-Find perl-base
perl-Feed-Find perl-libwww
perl-HTML-Parser glibc-core
perl-HTML-Parser perl-HTML-Tagset
perl-HTML-Parser perl-URI
perl-HTML-Parser perl-base
perl-HTML-Parser perl-libwww
perl-Module-Install perl-YAML
perl-Module-Install perl-base
perl-Module-Install perl-devel
perl-Params-Validate glibc-core
perl-Params-Validate perl-base
perl-URI perl-base
perl-URI-Fetch perl-Class-ErrorHandler
perl-URI-Fetch perl-URI
perl-URI-Fetch perl-base
perl-URI-Fetch perl-libwww
perl-XML-Atom perl-Class-Data-Inheritable
perl-XML-Atom perl-DateTime
perl-XML-Atom perl-Encode
perl-XML-Atom perl-HTML-Parser
perl-XML-Atom perl-XML-LibXML
perl-XML-Atom perl-base
perl-XML-Atom perl-libwww
perl-XML-LibXML glibc-core
perl-XML-LibXML libxml2
perl-XML-LibXML perl-XML-SAX
perl-XML-LibXML perl-base
perl-XML-Parser glibc-core
perl-XML-Parser libexpat
perl-XML-Parser perl-URI
perl-XML-Parser perl-base
perl-XML-Parser perl-libwww
perl-XML-RSS perl-XML-Parser
perl-XML-SAX perl-XML-LibXML
perl-XML-SAX perl-base
perl-YAML perl-base
perl-YAML perl-devel
perl-base glibc-core
perl-base perl-base
perl-devel glibc-core
perl-devel perl-base
perl-libwww perl-Compress-Zlib
perl-libwww perl-HTML-Parser
perl-libwww perl-URI
perl-libwww perl-base
rpm coreutils
rpm glibc-core
rpm libpopt
rpm librpm
rpm librpmbuild
rpm sh
rpm-build bzip2
rpm-build coreutils
rpm-build findutils
rpm-build glibc-core
rpm-build libpopt
rpm-build librpm
rpm-build librpmbuild
rpm-build make
rpm-build perl-base
rpm-build rpm
rpm-build sed
rpm-build sh
rpm-build tar
sed glibc-core
sed sh
sh glibc-core
tar glibc-core
tar sh
zlib glibc-core

Вывод tsort такой:

glibc-gconv-modules
glibc-locales
glibc-nss
perl-DateTime-Format-Mail
perl-DateTime-Format-W3CDTF
perl-ExtUtils-AutoInstall
perl-Feed-Find
perl-Module-Install
perl-URI-Fetch
perl-XML-Atom
perl-XML-RSS
rpm-build
perl-YAML
perl-Class-ErrorHandler
perl-Encode
perl-Class-Data-Inheritable
perl-XML-Parser
tar
sed
rpm
make
findutils
bzip2
perl-devel
libexpat
librpmbuild
coreutils
librpm
sh
libpopt
libelf
libdb4.4
libbeecrypt
bzlib
perl-XML-SAX
perl-XML-LibXML
libxml2
perl-HTML-Parser
perl-libwww
perl-HTML-Tagset
perl-URI
perl-Compress-Zlib
zlib
perl-DateTime-TimeZone
perl-DateTime
perl-DateTime-Locale
perl-Params-Validate
perl-base
glibc-core
setup

Список после оптимизации такой:

perl-DateTime-Format-Mail perl-DateTime-Format-W3CDTF perl-DateTime-TimeZone perl-ExtUtils-AutoInstall perl-Feed-Find perl-Module-Install perl-URI-Fetch perl-XML-Atom perl-XML-RSS perl-XML-SAX

Здесь два раза повторяется похожая ситуация:

1) Пакеты perl-DateTime-Format-Mail и perl-DateTime-Format-W3CDTF
требуют пакет perl-DateTime, а perl-DateTime и perl-DateTime-TimeZone
образуют цикл.  Из-за того, что perl-DateTime-TimeZone оказался выше по
списку, чем perl-DateTime, не происходит вычеркивание цикла целиком:
пакет perl-DateTime-TimeZone остается в списке.

То есть могло бы получиться, что perl-DateTime-Format-Mail вычеркнул
perl-DateTime, а perl-DateTime вычеркнул perl-DateTime-TimeZone, и тогда
цикл вычеркивается полностью.  Но этого не получилось.

2) perl-XML-Atom требует perl-XML-LibXML, а perl-XML-LibXML и
perl-XML-SAX образуют цикл.  Цикл опять не вычеркнут полностью -- в
списке остался perl-XML-SAX -- потому что perl-XML-SAX оказался выше по
списку, чем perl-XML-LibXML.

Теперь можно подумать, каким образом сформулировать требование к tsort
в части более "топологичного" разрыва циклов.
----------- следующая часть -----------
Было удалено вложение не в текстовом формате...
Имя     : =?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/20060905/1024299d/attachment-0001.bin>