From: Sergey Vlasov <vsu@altlinux.ru> To: ALT Devel discussion list <devel@lists.altlinux.org> Subject: Re: [devel] оптимизация сборочных зависимостей Date: Thu, 31 Aug 2006 00:12:07 +0400 Message-ID: <20060830201207.GE10840@procyon.home> (raw) In-Reply-To: <20060830164352.GA32596@basalt.office.altlinux.org> [-- Attachment #1: Type: text/plain, Size: 2941 bytes --] 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.) Далее, имея граф зависимостей между пакетами, необходимо каким-то образом определить минимальный набор вершин, пути, исходящие из которых, покрывают все вершины графа. При отсутствии циклов эта задача решается очень просто - достаточно найти вершины, в которые не входит ни одно ребро (пакеты, которые не зависят от других пакетов). Если же в графе есть циклы, каждый цикл нужно схлопнуть в одну вершину, затем, когда в графе не останется циклов, определить нужный набор вершин; если в этот набор попали вершины, полученные из циклов, для них можно выбрать любой пакет, входивший в цикл. [-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]
next prev parent reply other threads:[~2006-08-30 20:12 UTC|newest] Thread overview: 72+ messages / expand[flat|nested] mbox.gz Atom feed top 2006-08-30 14:58 [devel] libpixman Alexey Tourbin 2006-08-30 15:01 ` Dmitry V. Levin 2006-08-30 15:10 ` Alexey Tourbin 2006-08-30 15:20 ` Valery V. Inozemtsev 2006-08-30 15:29 ` Dmitry V. Levin 2006-08-30 15:36 ` Valery V. Inozemtsev 2006-08-30 15:41 ` Dmitry V. Levin 2006-08-30 16:00 ` Alexey Tourbin 2006-08-30 16:10 ` [devel] оптимизация сборочных зависимостей Dmitry V. Levin 2006-08-30 16:28 ` Alexey Tourbin 2006-08-30 16:43 ` Dmitry V. Levin 2006-08-30 18:30 ` Alexey Tourbin 2006-08-30 20:12 ` Sergey Vlasov [this message] 2006-08-30 21:01 ` Alexey Tourbin 2006-08-30 22:48 ` Alexey Tourbin 2006-08-30 23:19 ` Alexey Tourbin 2006-08-31 0:17 ` Денис Смирнов 2006-08-31 4:05 ` Alexey Tourbin 2006-09-05 13:10 ` [devel] оптимизация сборочных зависимостей (buildreq) Ildar Mulyukov 2006-09-05 13:48 ` Alexey Tourbin 2006-09-05 14:57 ` Ildar Mulyukov 2006-09-05 18:15 ` Michael Shigorin 2006-09-05 19:08 ` Alexey Tourbin 2006-09-05 19:15 ` Michael Shigorin 2006-09-06 4:06 ` Ildar Mulyukov 2006-08-30 23:45 ` [devel] оптимизация сборочных зависимостей Dmitry V. Levin 2006-08-31 0:27 ` Alexey Tourbin 2006-08-31 0:59 ` Alexey Tourbin 2006-09-02 16:34 ` Michael Shigorin 2006-09-03 2:12 ` Alexey Tourbin 2006-08-30 19:07 ` Alexey Tourbin 2006-08-30 20:29 ` Alexey Tourbin 2006-08-30 20:57 ` Damir Shayhutdinov 2006-08-30 21:17 ` Dmitry V. Levin 2006-08-31 12:29 ` Sergey Vlasov 2006-09-05 14:28 ` Alexey Tourbin 2006-09-03 4:36 ` Alexey Tourbin 2006-09-03 6:34 ` Alexey Tourbin 2006-09-03 6:52 ` Alexey Tourbin 2006-09-03 6:56 ` Alexey Tourbin 2006-09-03 13:38 ` [devel] readlink Dmitry V. Levin 2006-09-04 7:30 ` Alexey Tourbin 2006-09-03 17:08 ` [devel] оптимизация сборочных зависимостей Michael Shigorin 2006-09-03 17:39 ` Damir Shayhutdinov 2006-09-04 7:26 ` Alexey Tourbin 2006-09-04 11:30 ` Денис Смирнов 2006-09-04 9:42 ` [devel] xargs usage (Was: Re: оптимизация сборочных зависимостей) Andrei Bulava 2006-09-04 9:50 ` Alexey Tourbin 2006-09-03 10:57 ` [devel] оптимизация сборочных зависимостей Alexey Tourbin 2006-09-03 17:07 ` Michael Shigorin 2006-09-04 11:14 ` [devel] esound (was: Re: оптимизация сборочных зависимостей ) Igor Zubkov 2006-09-02 16:24 ` [devel] buildreq2 (was: libpixman) Michael Shigorin 2006-09-03 1:29 ` Alexey Tourbin 2006-09-03 17:11 ` Michael Shigorin 2006-09-03 2:00 ` [devel] buildreq FRs Alexey Tourbin 2006-09-03 17:16 ` Michael Shigorin 2006-08-30 19:28 ` [devel] libpixman Kirill Maslinsky 2006-08-30 19:38 ` Andrey Rahmatullin 2006-08-30 19:52 ` Alexey Tourbin 2006-08-30 20:20 ` Sergey Vlasov 2006-08-30 20:31 ` Alexey Tourbin 2006-08-31 20:06 ` [devel] buildreq ignore.d/fonts-cache Alexey Tourbin 2006-09-02 16:42 ` Michael Shigorin 2006-09-02 17:17 ` Dmitry V. Levin 2006-08-31 5:36 ` [devel] libpixman Andrey Rahmatullin 2006-08-31 6:11 ` Alexey I. Froloff 2006-09-02 16:40 ` Michael Shigorin 2006-08-30 19:57 ` [devel] buildreq при каждой сборке? Kirill Maslinsky 2006-08-30 19:39 ` [devel] libpixman Alexey Tourbin 2006-08-30 19:45 ` Konstantin A. Lepikhov 2006-08-30 19:53 ` Alexey Tourbin 2006-08-30 20:19 ` Kirill Maslinsky
Reply instructions: You may reply publicly to this message via plain-text email using any one of the following methods: * Save the following mbox file, import it into your mail client, and reply-to-all from there: mbox Avoid top-posting and favor interleaved quoting: https://en.wikipedia.org/wiki/Posting_style#Interleaved_style * Reply using the --to, --cc, and --in-reply-to switches of git-send-email(1): git send-email \ --in-reply-to=20060830201207.GE10840@procyon.home \ --to=vsu@altlinux.ru \ --cc=devel@lists.altlinux.org \ /path/to/YOUR_REPLY https://kernel.org/pub/software/scm/git/docs/git-send-email.html * If your mail client supports setting the In-Reply-To header via mailto: links, try the mailto: link
ALT Linux Team development discussions This inbox may be cloned and mirrored by anyone: git clone --mirror http://lore.altlinux.org/devel/0 devel/git/0.git # If you have public-inbox 1.1+ installed, you may # initialize and index your mirror using the following commands: public-inbox-init -V2 devel devel/ http://lore.altlinux.org/devel \ devel@altlinux.org devel@altlinux.ru devel@lists.altlinux.org devel@lists.altlinux.ru devel@linux.iplabs.ru mandrake-russian@linuxteam.iplabs.ru sisyphus@linuxteam.iplabs.ru public-inbox-index devel Example config snippet for mirrors. Newsgroup available over NNTP: nntp://lore.altlinux.org/org.altlinux.lists.devel AGPL code for this site: git clone https://public-inbox.org/public-inbox.git