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

[Alexey Tourbin]

On Thu, Aug 31, 2006 at 12:12:07AM +0400, Sergey Vlasov wrote:
> > >    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) - зависимости
> между пакетами.

Этот список deps -- кандидат на топологическую сортировку -- tsort(1).
Правда, tsort не умеет *молча* разрывать циклы.  Но этой особенностью
tsort в общем-то можно пренебречь.

Я вчера много думал, как всё это можно сделать, а сегодня спросонья, как
уже писал, потерял интерес... :)

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

rpm -q --whatprovides $dep |sort -u |wc -w

> Далее, имея граф зависимостей между пакетами, необходимо каким-то
> образом определить минимальный набор вершин, пути, исходящие из
> которых, покрывают все вершины графа.  При отсутствии циклов эта
> задача решается очень просто - достаточно найти вершины, в которые не
> входит ни одно ребро (пакеты, которые не зависят от других пакетов).
> Если же в графе есть циклы, каждый цикл нужно схлопнуть в одну
> вершину, затем, когда в графе не останется циклов, определить нужный
> набор вершин; если в этот набор попали вершины, полученные из циклов,
> для них можно выбрать любой пакет, входивший в цикл.

Топологическая сортировка, кажется, решает эту проблему.
Пусть есть список пакетов, отсортированный топологически: пакеты в
начале списка требуют пакеты, которые находятся ближе к концу списка.

Тогда можно применить что-то вроде решета Эратосфена, которое
используется для просева простых чисел.  Берем элемент списка и
вычеркиваем все *последующие* элементы, которые к нему сводятся.
Но не просто вычеркиваем, а как бы зануляем, чтобы уже вычеркнутые
элементы сохранились для последующих вычеркиваний.  Тогда на выходе
должен остаться список пакетов, которые не сводятся друг ко другу.
----------- следующая часть -----------
Было удалено вложение не в текстовом формате...
Имя     : =?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/9230736d/attachment-0001.bin>