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.)

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