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

[Sergey Vlasov]

On Wed, Aug 30, 2006 at 08:43:52PM +0400, Dmitry V. Levin wrote:
> On Wed, Aug 30, 2006 at 08:28:49PM +0400, Alexey Tourbin wrote:
> > On Wed, Aug 30, 2006 at 08:10:50PM +0400, Dmitry V. Levin wrote:
> > > > (Алгоритм оптимизации BuildRequires обсуждался вчера в частной
> > > > переписке.  Правда, спросонья я потерял к нему интерес.  Если это
> > > > интересно кому-то ещё, тогда можно перенести обсуждение сюда.)
> > > 
> > > Думаю, что лучше перенести сюда - вдруг среди нас есть специалист/практик
> > > по теории графов?
> > 
> > Тогда повторю вопрос.
> > 
> >    145  "$PACKAGEOF" -f "$WORKDIR/files" >"$WORKDIR/packages"
> >    146  sort -u -o "$WORKDIR/packages" "$WORKDIR/packages"
> 
> packages - это список имён пакетов, которые использовались для сборки
> посредством files.
> 
> >    148  cat "$WORKDIR/packages" |
> >    149          xargs -r rpmquery --qf '[%{REQUIRENAME}\n]' -- |  
> >    150          sort -u >"$WORKDIR/reqs"
> 
> reqs - это все requires пакетов packages.

Вот здесь вместо этого можно построить список пар вида
"PackageName RequireName".

> >    152  cat "$WORKDIR/packages" |
> >    153          xargs -r rpmquery --qf '[%{PROVIDENAME}\t%{NAME}\n]' -- |
> >    154          sort -k2,2 -k1,1 -u >"$WORKDIR/provs"
> 
> provs - это всё provides пакетов packages в виде пар
> "ProvideName PackageName".

Далее join по reqs.RequireName == provs.ProvideName даст список пар
"PackageName -> RequiredPackageName" (назовём его deps) - зависимости
между пакетами.

(На самом деле это тоже не совсем правильно - возможна ситуация, когда
один и тот же виртуальный пакет провайдится несколькими пакетами,
попавшими в список используемых; в этом случае наличие в BuildRequires
пакетов, требующих такую зависимость, не гарантирует установки всех
нужных пакетов.  Чтобы не получить в таком случае неверный результат,
список provs надо предварительно почистить - все ProvideName,
встречающиеся более одного раза, нужно удалить.  Хотя и это не
поможет, если аналогичные provides есть ещё в пакетах, не попавших в
список packages; более того, такие пакеты могут существовать в
репозитории, но не быть установлены в системе, где выполняется
buildreq...  Получается, что наиболее правильный способ - использовать
список provs от всего репозитория, а не только от packages.)

Далее, имея граф зависимостей между пакетами, необходимо каким-то
образом определить минимальный набор вершин, пути, исходящие из
которых, покрывают все вершины графа.  При отсутствии циклов эта
задача решается очень просто - достаточно найти вершины, в которые не
входит ни одно ребро (пакеты, которые не зависят от других пакетов).
Если же в графе есть циклы, каждый цикл нужно схлопнуть в одну
вершину, затем, когда в графе не останется циклов, определить нужный
набор вершин; если в этот набор попали вершины, полученные из циклов,
для них можно выбрать любой пакет, входивший в цикл.
----------- следующая часть -----------
Было удалено вложение не в текстовом формате...
Имя     : =?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/f300f411/attachment-0001.bin>