ALT Linux Team development discussions
 help / color / mirror / Atom feed
From: Alexey Tourbin <at@altlinux.ru>
To: ALT Devel discussion list <devel@lists.altlinux.org>
Subject: Re: [devel] оптимизация сборочных зависимостей
Date: Thu, 31 Aug 2006 00:29:06 +0400
Message-ID: <20060830202906.GF11420@localhost.localdomain> (raw)
In-Reply-To: <20060830161050.GA31919@basalt.office.altlinux.org>

[-- Attachment #1: Type: text/plain, Size: 3248 bytes --]

On Wed, Aug 30, 2006 at 08:10:50PM +0400, Dmitry V. Levin wrote:
> > (Алгоритм оптимизации BuildRequires обсуждался вчера в частной
> > переписке.  Правда, спросонья я потерял к нему интерес.  Если это
> > интересно кому-то ещё, тогда можно перенести обсуждение сюда.)
> 
> Думаю, что лучше перенести сюда - вдруг среди нас есть специалист/практик
> по теории графов?

Вот примитивный алгоритм, который однако же работает некорректно,
поскольку полностью исключает из списка циклы.

Дан список пакетов P.  Составим два отношения req<name,dep> и
prov<name,dep> (которые соответствуют rpm -q --requires и
rpm -q --provides).  Соединим req и prov по полю dep и сделаем
проекцию на prov<name>.  Получим список пакетов, которые
требуются какими-либо пакетами из исходного списка P.
Следовательно, эти пакеты можно удалить.

Пример.  Дано: glibc-core, sh.
req:
	sh	libc.so.6
	...
prov:
	glibc-core	libc.so.6
	...
Соединение:
	sh -> libc.so.6 -> glibc-core
Проекция:
	glibc-core

Следовательно, казалось бы, пакет glibc-core можно удалить.
Но это работает корректно не во всех случаях.

(Далее я поясняю на примерах, когда и почему это не работает.)

1) Рассмотрим пакет perl-base.  Одной из его особенностей является то,
что он почему то требует сам себя -- Requires: perl-base.  Получается
соединение perl-base -> perl-base -> perl-base и пакет совершенно
автоматически удаляется из списка.

Вот сам скрипт, с которым можно поиграться.

$ cat ./optimize_package_list
#!/bin/sh -ef
. tmpdir.sh
cd $TMPDIR
rpm -q --qf '[%{REQUIRENAME}\t%{NAME}\n]' -- "$@" >qR
rpm -q --qf '[%{PROVIDENAME}\t%{NAME}\n]' -- "$@" >qP
awk '{print$2,$1}' qR |sort -u -k2,2 -k1,1 -o qR
awk '{print$2,$1}' qP |sort -u -k2,2 -k1,1 -o qP
#head -v qR qP
join -j 2 -o 2.1 qR qP |sort -u >extrareq
awk '{print$1}' qR |sort -u >req
#head -v req extrareq
comm -23 req extrareq |xargs -r echo
$ ./optimize_package_list perl-base
$

(tmpdir.sh есть в пакете qa-robot)

2) Далее, рассмотрим пакеты perl-DateTime и perl-DateTime-TimeZone.
Эти пакеты зависят друг от друга, получается следующее соединение:

perl-DateTime -> perl(DateTime/TimeZone.pm) -> perl-DateTime-TimeZone
perl-DateTime-TimeZone -> perl(DateTime.pm) -> perl-DateTime

Опять получается, что все требуемые зависимости опять же предоставляются
самими этими пакетами, поэтому уже сразу два пакет, которые образуют
цикл, совершенно автоматически исключаются из списка.

$ ./optimize_package_list perl-DateTime perl-DateTime-TimeZone
$

Ясно, что 1) является частным случаем 2).  Это можно представить себе
как простую и сложную рекурсию.  При простой рекурсии фунция f вызывает
сама себя.  При сложной рекурсии функция f1 вызывает f2, которая в свою
очередь опять вызывает f1.

3) A requires B, B requires C, ..., X requires Y, Y requires A.

Короче, должно быть уже ясно, что при наличии циклических зависимостей
удаляется *весь цикл*, т.е. вследствие некорректной оптимизации теряется
потенциально много пакетов.

Далее, я знаю, как обнаруживать циклы.  Нужно сделать соединение ещё раз
само на себя и проверить, не совпадают ли начальный и конечный элементы.
Не понтяно правда, что потом делать с обнаруженными таким образом циклами.

[-- Attachment #2: Type: application/pgp-signature, Size: 189 bytes --]

  parent reply	other threads:[~2006-08-30 20:29 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
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 [this message]
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=20060830202906.GF11420@localhost.localdomain \
    --to=at@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