[devel] apt virtual packages

[devel] apt virtual packages

[Alexey Tourbin]

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

Я собрал себе хешером в ~tmp/build libdb4.4 из git репозитария.
При этом я надеюсь, что пакеты в ~tmp/build будут перекрывать пакеты от
сизифа.  От сизифа я скачал только свежие хеши.

Теперь при попытке установки в ~tmp/build libdb4-devel туда ставится
libdb4.3-devel.

$ hsh-install ~tmp/build libdb4-devel
Preparing packages for installation...
libdb4.3-4.3.29-alt3
libdb4.3-devel-4.3.29-alt3
$

Аналогичная история с gcc.  Я склонировал и собрал с помощью gear
gcc4.1.  Теперь при попытке установки в сборочницу пакета gcc-c++
(зависимость из BuildRequires) apt хочет туда поставить gcc3.4-c++:

$ hsh-install ~tmp/build gcc-c++
install: cannot stat `/raid/ALT/Sisyphus/i586/RPMS.classic/cpp3.4-3.4.5-alt6.i586.rpm': No such file or directory
install: cannot stat `/raid/ALT/Sisyphus/i586/RPMS.classic/gcc3.4-3.4.5-alt6.i586.rpm': No such file or directory
install: cannot stat `/raid/ALT/Sisyphus/i586/RPMS.classic/libstdc++3.4-3.4.5-alt6.i586.rpm': No such file or directory
install: cannot stat `/raid/ALT/Sisyphus/i586/RPMS.classic/libstdc++3.4-devel-3.4.5-alt6.i586.rpm': No such file or directory
install: cannot stat `/raid/ALT/Sisyphus/i586/RPMS.classic/gcc3.4-c++-3.4.5-alt6.i586.rpm': No such file or directory
hsh-install: failed to copy files.
$

Кажется, когда apt видит, что для виртуального пакета имются два пакета
с одинаковым названием (но разных сборок), он попросту пытается ставить
что-то ещё.

Как бы апту мозги вправить, чтобы он ставил прежде всего именно то, что
у меня лежит в сборочнице?  Можно конечно в багзиллу написать или самому
в апте ковыряться, но может быть уже кто-то знает?

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

Re: [devel] apt virtual packages

[Dmitry V. Levin]

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

On Tue, Oct 10, 2006 at 02:32:36AM +0400, Alexey Tourbin wrote:
> Кажется, когда apt видит, что для виртуального пакета имются два пакета
> с одинаковым названием (но разных сборок), он попросту пытается ставить
> что-то ещё.

Кажется, что apt не сортирует виртуальные пакеты.

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

Можно запинать (повысить приоритет) сборочнице, но это workaround.

> Можно конечно в багзиллу написать или самому
> в апте ковыряться, но может быть уже кто-то знает?

Я буду признателен тому, кто решит эту задачу (т.е. зафиксит apt).


-- 
ldv

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

Re: [devel] apt virtual packages

[Alexey Tourbin]

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

On Tue, Oct 10, 2006 at 02:41:52AM +0400, Dmitry V. Levin wrote:
> > Можно конечно в багзиллу написать или самому
> > в апте ковыряться, но может быть уже кто-то знает?
> 
> Я буду признателен тому, кто решит эту задачу (т.е. зафиксит apt).

Я вроде бы зафиксил, хотя меня гложут сомнения.

--- apt-get.cc-	2006-10-10 03:04:25 +0400
+++ apt-get.cc	2006-10-10 04:30:30 +0400
@@ -1275,14 +1275,18 @@ bool TryToInstall(pkgCache::PkgIterator 
 	    continue;
 	 }
 	 // Is the provides pointing to the candidate version?
-	 if (PrvPkgCandVer == Prv.OwnerVer())
+	 bool good = false;
+	 for (; PrvPkgCandVer.end() == false; ++PrvPkgCandVer)
 	 {
-	    // Yes, it is. This is a good solution.
-	    GoodSolutions.push_back(PrvPkg);
-	    if (instVirtual)
-		break;
-	    continue;
+	    if (PrvPkgCandVer == Prv.OwnerVer())
+	    {
+	       // Yes, it is. This is a good solution.
+	       good = true;
+	       GoodSolutions.push_back(PrvPkg);
+	    }
 	 }
+	 if (good && instVirtual)
+	    break;
       }
       vector<string> GoodSolutionNames;
       unsigned int GoodSolutionsInstalled = 0, GoodSolutionInstallNumber = 0;
End of patch

Вот полностью релевантный кусок кода (исправленный).

  1270           pkgCache::VerIterator PrvPkgCandVer =
  1271                                   Cache[PrvPkg].CandidateVerIter(Cache);
  1272           if (PrvPkgCandVer.end() == true)
  1273           {
  1274              // Packages without a candidate version are not good solutions.
  1275              continue;
  1276           }
  1277           // Is the provides pointing to the candidate version?
  1278           bool good = false;
  1279           for (; PrvPkgCandVer.end() == false; ++PrvPkgCandVer)
  1280           {
  1281              if (PrvPkgCandVer == Prv.OwnerVer())
  1282              {
  1283                 // Yes, it is. This is a good solution.
  1284                 good = true;
  1285                 GoodSolutions.push_back(PrvPkg);
  1286              }
  1287           }
  1288           if (good && instVirtual)
  1289              break;
  1290        }

Здесь PrvPkg -- это реальный пакет, который провайдит виртуальную
зависимость.  Мы проверяем, есть ли у реального пакета "версия".
(Что такое "версия"?  Я плохо понимаю внутренние структуры апта, поэтому
и гложут сомнения.)  Если реальный пакет без версии, тогда он не тянет
на установку через виртуальную зависимость.  Далее, в оригинальном коде
проверяется нечто странное, что я не могу до конца сформулировать.

	if (PrvPkgCandVer == Prv.OwnerVer())

Смысле в том, что версия PrvPkgCandVer, найденная через reverse lookup,
должна совпадать с непосредственной версией Prv.OwnerVer().  Тогда пакет
-- хороший кандидат.  Но PrvPkgCandVer -- это итератор.  Кстати, кажется
Prv.OwnerVer это тоже итератор.  Если в репозитарии оказывается два
пакета с одинаковым именем и версией, то совпадение сразу же не
гарантируется.  Один из этих итераторов нужно "прокрутить" и проверять
условие в цикле, что я и делаю.

Скажите, кто-нибудь понимает внутренние структуры апта?  Муть какая-то.
Где об этом можно что-нибудь прочитать?

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

Re: [devel] apt virtual packages

[Dmitry V. Levin]

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

On Tue, Oct 10, 2006 at 04:40:28AM +0400, Alexey Tourbin wrote:
> On Tue, Oct 10, 2006 at 02:41:52AM +0400, Dmitry V. Levin wrote:
> > > Можно конечно в багзиллу написать или самому
> > > в апте ковыряться, но может быть уже кто-то знает?
> > 
> > Я буду признателен тому, кто решит эту задачу (т.е. зафиксит apt).
> 
> Я вроде бы зафиксил, хотя меня гложут сомнения.
[...]
> Смысле в том, что версия PrvPkgCandVer, найденная через reverse lookup,
> должна совпадать с непосредственной версией Prv.OwnerVer().  Тогда пакет
> -- хороший кандидат.  Но PrvPkgCandVer -- это итератор.  Кстати, кажется
> Prv.OwnerVer это тоже итератор.  Если в репозитарии оказывается два
> пакета с одинаковым именем и версией, то совпадение сразу же не
> гарантируется.  Один из этих итераторов нужно "прокрутить" и проверять
> условие в цикле, что я и делаю.

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

> Скажите, кто-нибудь понимает внутренние структуры апта?

Хм.

> Муть какая-то.
> Где об этом можно что-нибудь прочитать?

Боюсь что RTFS.


-- 
ldv

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

Re: [devel] apt virtual packages

[Alexey Tourbin]

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

On Tue, Oct 10, 2006 at 07:39:03PM +0400, Dmitry V. Levin wrote:
> On Tue, Oct 10, 2006 at 04:40:28AM +0400, Alexey Tourbin wrote:
> > On Tue, Oct 10, 2006 at 02:41:52AM +0400, Dmitry V. Levin wrote:
> > > > Можно конечно в багзиллу написать или самому
> > > > в апте ковыряться, но может быть уже кто-то знает?
> > > 
> > > Я буду признателен тому, кто решит эту задачу (т.е. зафиксит apt).
> > 
> > Я вроде бы зафиксил, хотя меня гложут сомнения.
> [...]
> > Смысле в том, что версия PrvPkgCandVer, найденная через reverse lookup,
> > должна совпадать с непосредственной версией Prv.OwnerVer().  Тогда пакет
> > -- хороший кандидат.  Но PrvPkgCandVer -- это итератор.  Кстати, кажется
> > Prv.OwnerVer это тоже итератор.  Если в репозитарии оказывается два
> > пакета с одинаковым именем и версией, то совпадение сразу же не
> > гарантируется.  Один из этих итераторов нужно "прокрутить" и проверять
> > условие в цикле, что я и делаю.
> 
> Видимо, ты прав.  Надо бы, конечно, проверить экспериментально, но код
> говорит в твою пользу.

Я проверил экспериментально.  Я в общем-то начал с "printf debugging"
(правда, в Си+плюс это правильнее называть "cerr debugging") на двух
песочницах, в одной из которым лежит самосборный libdb4.4-devel, а в
другой нет.  Соответственно стало ясно, что отсев происходит именно в
этом месте.

Теперь, этот патч сделан относительно rpm -bp, он конфликтует с ещё
одним патчем alt-TryToInstall.patch.  Как его правильно приложить я не
знаю, поэтому публиковать свой /packages/apt не буду.  Хотелось думать,
что с git'ом такие проблемы уйдут, но они не уходят.

Типа
PATH=$PWD:$PATH ~tmp/build1/aptbox/apt-get --dry-run install gcc-c++
PATH=$PWD:$PATH ~tmp/build2/aptbox/apt-get --dry-run install gcc-c++

То есть я подошел к этому как естествоиспытатель.  Как ещё такие вещи
отлаживать я просто ума не приложу.

> > Скажите, кто-нибудь понимает внутренние структуры апта?
> Хм.

Я их лишь отчасти, очень приблизительно, понял, когда просматривал
исходники перловых привязок к libapt-pkg.

Одна из проблем в том что они self-referring (цикличны/рекурисивны) и их
в перле нельзя стандартными средствами по-нормальному сдампить (в
читаемом виде), чтобы посмотреть что же там на самом деле есть.

> > Муть какая-то.
> > Где об этом можно что-нибудь прочитать?
> Боюсь что RTFS.

Си+плюс не способствует пониманию исходников.  Ну что такое у итератора
перегрузка оператора "=="?  Головная боль.  Тем более что ctags тоже
что-то не очень мне помог.

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

Re: [devel] apt virtual packages

[Dmitry V. Levin]

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

On Tue, Oct 10, 2006 at 07:52:51PM +0400, Alexey Tourbin wrote:
> On Tue, Oct 10, 2006 at 07:39:03PM +0400, Dmitry V. Levin wrote:
> > On Tue, Oct 10, 2006 at 04:40:28AM +0400, Alexey Tourbin wrote:
> > > On Tue, Oct 10, 2006 at 02:41:52AM +0400, Dmitry V. Levin wrote:
> > > > > Можно конечно в багзиллу написать или самому
> > > > > в апте ковыряться, но может быть уже кто-то знает?
> > > > 
> > > > Я буду признателен тому, кто решит эту задачу (т.е. зафиксит apt).
> > > 
> > > Я вроде бы зафиксил, хотя меня гложут сомнения.
[...]
> Я проверил экспериментально.  Я в общем-то начал с "printf debugging"
> (правда, в Си+плюс это правильнее называть "cerr debugging") на двух
> песочницах, в одной из которым лежит самосборный libdb4.4-devel, а в
> другой нет.  Соответственно стало ясно, что отсев происходит именно в
> этом месте.

Ну вот, значит одной непреодолимой проблемой, от которой так страдал
cray@ и ещё несколько человек, теперь стало меньше.

> Теперь, этот патч сделан относительно rpm -bp, он конфликтует с ещё
> одним патчем alt-TryToInstall.patch.  Как его правильно приложить я не
> знаю, поэтому публиковать свой /packages/apt не буду.  Хотелось думать,
> что с git'ом такие проблемы уйдут, но они не уходят.

Такие проблемы уйдут только если высокие патчащие стороны договорятся
использовать один и тот же стиль работы.  Если одни держат патчи отдельно
(как в прежние времена), а другие - приложенными, то будут возникать
коллизии.


-- 
ldv

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

Re: [devel] apt virtual packages

[Alexey Tourbin]

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

On Wed, Oct 11, 2006 at 02:11:27AM +0400, Dmitry V. Levin wrote:
> > Я проверил экспериментально.  Я в общем-то начал с "printf debugging"
> > (правда, в Си+плюс это правильнее называть "cerr debugging") на двух
> > песочницах, в одной из которым лежит самосборный libdb4.4-devel, а в
> > другой нет.  Соответственно стало ясно, что отсев происходит именно в
> > этом месте.
> 
> Ну вот, значит одной непреодолимой проблемой, от которой так страдал
> cray@ и ещё несколько человек, теперь стало меньше.

А cray@ разве страдал именно от этой проблемы?  Помнится у него какая-то
бодяга с python-dev была, но это вроде бы не совсем то.

> > Теперь, этот патч сделан относительно rpm -bp, он конфликтует с ещё
> > одним патчем alt-TryToInstall.patch.  Как его правильно приложить я не
> > знаю, поэтому публиковать свой /packages/apt не буду.  Хотелось думать,
> > что с git'ом такие проблемы уйдут, но они не уходят.
> 
> Такие проблемы уйдут только если высокие патчащие стороны договорятся
> использовать один и тот же стиль работы.  Если одни держат патчи отдельно
> (как в прежние времена), а другие - приложенными, то будут возникать
> коллизии.

Коллизии и так возникают -- патч на патче сидит и патчем погоняет.
Человеку удобнее работать с git как с полноценным архиватором истории и т.п.
Хранить в git'е птачи -- это полумера, большинство достоинств git
в таком случае использовать нельзя.  Нужна осмысленная гранулярная
история изменений, а в прежние времена тарболл это всегда был черный
ящик, внутренности которого лишь слегка проглядывали за счет патчей.

У git'а конечно есть свои ограничения, он направлен на rapid разработку
и частые слияния, а какие тут частые слияния, если кругом одни крокодилы
плавают.

Это я к чему.  apt походу никому не нужен, кроме нас и "того мужика".
Причем у нас apt -- системообразующая вещь, а тому мужику не ясно какой
от него интерес.  Вон на apt-rpm.org написано: fix building with older
compilers (eg gcc-2.96).  По-моему это глупость какая-то.  Нужно
ориентироваться на стандарт языка, а не на допотопный компилятор.
Тем боле что компилятор с тех пор подправили.  Впрочем, Си+плюс и сам
по себе не вызывает у меня энтузиазма.  Ссылка в тему: C++ Grammar
http://www.nobugs.org/developer/parsingcpp/mikedimmick.txt
Про разбор Си+плюс целые PhD диссертации пишут, обычный yacc его не
берет.  Нафик такое счастье не нужно.

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

Re: [devel] apt virtual packages

[Serge Pavlovsky]

В Срд, 11/10/2006 в 04:16 +0400, Alexey Tourbin пишет:
> Ссылка в тему: C++ Grammar
> http://www.nobugs.org/developer/parsingcpp/mikedimmick.txt
> Про разбор Си+плюс целые PhD диссертации пишут, обычный yacc его не
> берет.

а еще говорят, что все проблемы в своей грамматике с++ унаследовал от с.
и в gcc и в g++ парсер щас самодельный

Re: [devel] apt virtual packages

[Dmitry V. Levin]

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

On Wed, Oct 11, 2006 at 04:16:36AM +0400, Alexey Tourbin wrote:
> On Wed, Oct 11, 2006 at 02:11:27AM +0400, Dmitry V. Levin wrote:
> > > Я проверил экспериментально.  Я в общем-то начал с "printf debugging"
> > > (правда, в Си+плюс это правильнее называть "cerr debugging") на двух
> > > песочницах, в одной из которым лежит самосборный libdb4.4-devel, а в
> > > другой нет.  Соответственно стало ясно, что отсев происходит именно в
> > > этом месте.
> > 
> > Ну вот, значит одной непреодолимой проблемой, от которой так страдал
> > cray@ и ещё несколько человек, теперь стало меньше.
> 
> А cray@ разве страдал именно от этой проблемы?  Помнится у него какая-то
> бодяга с python-dev была, но это вроде бы не совсем то.

У него была проблема с очень похожими симптомами, и она, к сожалению,
твоим исправлением не решена.

Как воспроизвести:
1. Взять пакет python-2.4.4-alt2.src.rpm из Сизифа, увеличить релиз и
собрать получившийся python-2.4.4-alt2.1.src.rpm
2. Взять пакет python-module-tpg-3.1.0-alt1.src.rpm из Сизифа и
попробовать собрать (--with-stuff по умолчанию).
Этот python-module-tpg не соберётся с такой диагностикой:

Reading Package Lists...
Building Dependency Tree...
Selected version 2.4.4-alt2 for python-devel
Selected version 0.29-alt3 for rpm-build-python
rpm-build-python is already the newest version.
Some packages could not be installed. This may mean that you have
requested an impossible situation or if you are using the unstable
distribution that some required packages have not yet been created
or been moved out of Incoming.
The following information may help to resolve the situation:

The following packages have unmet dependencies:
  python-dev: Depends: python-base (= 2.4.4-alt2) but 2.4.4-alt2.1 is to be installed
E: Broken packages
install: failed to calculate package file list.
install: Failed to generate package file list.

Причём:
$ rpmquery -pR python-module-tpg-3.1.0-alt1.src.rpm |grep -v ^rpmlib
python-devel = 2.4
rpm-build-python >= 0.8
$ workdir/aptbox/apt-get -y --print-uris install python-devel 2>&1 |grep ^Selecting
Selecting python-dev for 'python-devel'
$ workdir/aptbox/apt-get -y --print-uris install python-devel=2.4
Reading Package Lists...
Building Dependency Tree...
Selected version 2.4.4-alt2 for python-devel
Some packages could not be installed. This may mean that you have
requested an impossible situation or if you are using the unstable
distribution that some required packages have not yet been created
or been moved out of Incoming.

Since you only requested a single operation it is extremely likely that
the package is simply not installable and a bug report against
that package should be filed.
The following information may help to resolve the situation:

The following packages have unmet dependencies:
  python-dev: Depends: python-base (= 2.4.4-alt2) but 2.4.4-alt2.1 is to be installed
E: Broken packages


-- 
ldv

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

Re: [devel] apt virtual packages

[Alexey Tourbin]

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

On Fri, Dec 08, 2006 at 01:52:33AM +0300, Dmitry V. Levin wrote:
> On Wed, Oct 11, 2006 at 04:16:36AM +0400, Alexey Tourbin wrote:
> > On Wed, Oct 11, 2006 at 02:11:27AM +0400, Dmitry V. Levin wrote:
> > > > Я проверил экспериментально.  Я в общем-то начал с "printf debugging"
> > > > (правда, в Си+плюс это правильнее называть "cerr debugging") на двух
> > > > песочницах, в одной из которым лежит самосборный libdb4.4-devel, а в
> > > > другой нет.  Соответственно стало ясно, что отсев происходит именно в
> > > > этом месте.
> > > 
> > > Ну вот, значит одной непреодолимой проблемой, от которой так страдал
> > > cray@ и ещё несколько человек, теперь стало меньше.
> > 
> > А cray@ разве страдал именно от этой проблемы?  Помнится у него какая-то
> > бодяга с python-dev была, но это вроде бы не совсем то.
> 
> У него была проблема с очень похожими симптомами, и она, к сожалению,
> твоим исправлением не решена.
> 
> Как воспроизвести:
> 1. Взять пакет python-2.4.4-alt2.src.rpm из Сизифа, увеличить релиз и
> собрать получившийся python-2.4.4-alt2.1.src.rpm

Питон для сборки требует xorg-x11-devel xorg-x11-mesaGL!
Когда я его соберу...

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

Re: [devel] apt virtual packages

[Dmitry V. Levin]

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

On Sat, Dec 09, 2006 at 12:27:18AM +0300, Alexey Tourbin wrote:
> On Fri, Dec 08, 2006 at 01:52:33AM +0300, Dmitry V. Levin wrote:
> > On Wed, Oct 11, 2006 at 04:16:36AM +0400, Alexey Tourbin wrote:
> > > On Wed, Oct 11, 2006 at 02:11:27AM +0400, Dmitry V. Levin wrote:
> > > > > Я проверил экспериментально.  Я в общем-то начал с "printf debugging"
> > > > > (правда, в Си+плюс это правильнее называть "cerr debugging") на двух
> > > > > песочницах, в одной из которым лежит самосборный libdb4.4-devel, а в
> > > > > другой нет.  Соответственно стало ясно, что отсев происходит именно в
> > > > > этом месте.
> > > > 
> > > > Ну вот, значит одной непреодолимой проблемой, от которой так страдал
> > > > cray@ и ещё несколько человек, теперь стало меньше.
> > > 
> > > А cray@ разве страдал именно от этой проблемы?  Помнится у него какая-то
> > > бодяга с python-dev была, но это вроде бы не совсем то.
> > 
> > У него была проблема с очень похожими симптомами, и она, к сожалению,
> > твоим исправлением не решена.
> > 
> > Как воспроизвести:
> > 1. Взять пакет python-2.4.4-alt2.src.rpm из Сизифа, увеличить релиз и
> > собрать получившийся python-2.4.4-alt2.1.src.rpm
> 
> Питон для сборки требует xorg-x11-devel xorg-x11-mesaGL!

Я не в курсе зачем это ему понадобилось.

> Когда я его соберу...

Можно собрать удалённо.


-- 
ldv

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

Re: [devel] apt virtual packages

[Alexey Tourbin]

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

On Sat, Dec 09, 2006 at 12:43:48AM +0300, Dmitry V. Levin wrote:
> > Когда я его соберу...
> Можно собрать удалённо.

Удаленно отжаливать неудобно.  У меня теперь безлимитный интернет,
но, кажется, мне забыли переключить скорость 64Kbit/sec -> 128...

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

Re: [devel] apt virtual packages

[Dmitry V. Levin]

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

On Sat, Dec 09, 2006 at 12:27:18AM +0300, Alexey Tourbin wrote:
> On Fri, Dec 08, 2006 at 01:52:33AM +0300, Dmitry V. Levin wrote:
> > On Wed, Oct 11, 2006 at 04:16:36AM +0400, Alexey Tourbin wrote:
> > > On Wed, Oct 11, 2006 at 02:11:27AM +0400, Dmitry V. Levin wrote:
> > > > > Я проверил экспериментально.  Я в общем-то начал с "printf debugging"
> > > > > (правда, в Си+плюс это правильнее называть "cerr debugging") на двух
> > > > > песочницах, в одной из которым лежит самосборный libdb4.4-devel, а в
> > > > > другой нет.  Соответственно стало ясно, что отсев происходит именно в
> > > > > этом месте.
> > > > 
> > > > Ну вот, значит одной непреодолимой проблемой, от которой так страдал
> > > > cray@ и ещё несколько человек, теперь стало меньше.
> > > 
> > > А cray@ разве страдал именно от этой проблемы?  Помнится у него какая-то
> > > бодяга с python-dev была, но это вроде бы не совсем то.
> > 
> > У него была проблема с очень похожими симптомами, и она, к сожалению,
> > твоим исправлением не решена.
> > 
> > Как воспроизвести:
> > 1. Взять пакет python-2.4.4-alt2.src.rpm из Сизифа, увеличить релиз и
> > собрать получившийся python-2.4.4-alt2.1.src.rpm
> 
> Питон для сборки требует xorg-x11-devel xorg-x11-mesaGL!

Запустил buildreq, получил:
# Automatically added by buildreq on Sat Dec 09 2006
BuildRequires: bzlib-devel gcc-c++ libdb4-devel libgdbm-devel libncurses-devel libreadline-devel libssl-devel tk-devel zlib-devel


-- 
ldv

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

Re: [devel] apt virtual packages

[Dmitry V. Levin]

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

On Sat, Dec 09, 2006 at 01:01:08AM +0300, Dmitry V. Levin wrote:
> On Sat, Dec 09, 2006 at 12:27:18AM +0300, Alexey Tourbin wrote:
> > On Fri, Dec 08, 2006 at 01:52:33AM +0300, Dmitry V. Levin wrote:
> > > On Wed, Oct 11, 2006 at 04:16:36AM +0400, Alexey Tourbin wrote:
> > > > On Wed, Oct 11, 2006 at 02:11:27AM +0400, Dmitry V. Levin wrote:
> > > > > > Я проверил экспериментально.  Я в общем-то начал с "printf debugging"
> > > > > > (правда, в Си+плюс это правильнее называть "cerr debugging") на двух
> > > > > > песочницах, в одной из которым лежит самосборный libdb4.4-devel, а в
> > > > > > другой нет.  Соответственно стало ясно, что отсев происходит именно в
> > > > > > этом месте.
> > > > > 
> > > > > Ну вот, значит одной непреодолимой проблемой, от которой так страдал
> > > > > cray@ и ещё несколько человек, теперь стало меньше.
> > > > 
> > > > А cray@ разве страдал именно от этой проблемы?  Помнится у него какая-то
> > > > бодяга с python-dev была, но это вроде бы не совсем то.
> > > 
> > > У него была проблема с очень похожими симптомами, и она, к сожалению,
> > > твоим исправлением не решена.
> > > 
> > > Как воспроизвести:
> > > 1. Взять пакет python-2.4.4-alt2.src.rpm из Сизифа, увеличить релиз и
> > > собрать получившийся python-2.4.4-alt2.1.src.rpm
> > 
> > Питон для сборки требует xorg-x11-devel xorg-x11-mesaGL!
> 
> Запустил buildreq, получил:
> # Automatically added by buildreq on Sat Dec 09 2006
> BuildRequires: bzlib-devel gcc-c++ libdb4-devel libgdbm-devel libncurses-devel libreadline-devel libssl-devel tk-devel zlib-devel

Запустил buildreq -bi, получил:
# Automatically added by buildreq on Sat Dec 09 2006 (-bi)
BuildRequires: bzlib-devel emacs-common gcc-c++ libdb4-devel libgdbm-devel libncurses-devel libreadline-devel libssl-devel tk-devel zlib-devel


-- 
ldv

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

Re: [devel] apt virtual packages

[Alexey Tourbin]

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

On Fri, Dec 08, 2006 at 01:52:33AM +0300, Dmitry V. Levin wrote:
> On Wed, Oct 11, 2006 at 04:16:36AM +0400, Alexey Tourbin wrote:
> > On Wed, Oct 11, 2006 at 02:11:27AM +0400, Dmitry V. Levin wrote:
> > > > Я проверил экспериментально.  Я в общем-то начал с "printf debugging"
> > > > (правда, в Си+плюс это правильнее называть "cerr debugging") на двух
> > > > песочницах, в одной из которым лежит самосборный libdb4.4-devel, а в
> > > > другой нет.  Соответственно стало ясно, что отсев происходит именно в
> > > > этом месте.
> > > 
> > > Ну вот, значит одной непреодолимой проблемой, от которой так страдал
> > > cray@ и ещё несколько человек, теперь стало меньше.
> > 
> > А cray@ разве страдал именно от этой проблемы?  Помнится у него какая-то
> > бодяга с python-dev была, но это вроде бы не совсем то.
> 
> У него была проблема с очень похожими симптомами, и она, к сожалению,
> твоим исправлением не решена.
> 
> Как воспроизвести:
> 1. Взять пакет python-2.4.4-alt2.src.rpm из Сизифа, увеличить релиз и
> собрать получившийся python-2.4.4-alt2.1.src.rpm
> 2. Взять пакет python-module-tpg-3.1.0-alt1.src.rpm из Сизифа и
> попробовать собрать (--with-stuff по умолчанию).
> Этот python-module-tpg не соберётся с такой диагностикой:

Существует в природе какой-нибудь rpm header editor?
Мне нужно кое-что в python-module-tpg-3.1.0-alt1.src.rpm поправить,
так сказать, inplace.

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

Re: [devel] apt virtual packages

[Alexey Tourbin]

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

On Fri, Dec 08, 2006 at 01:52:33AM +0300, Dmitry V. Levin wrote:
> У него была проблема с очень похожими симптомами, и она, к сожалению,
> твоим исправлением не решена.

Это совсем другая проблема.

> Как воспроизвести:
> 1. Взять пакет python-2.4.4-alt2.src.rpm из Сизифа, увеличить релиз и
> собрать получившийся python-2.4.4-alt2.1.src.rpm
> 2. Взять пакет python-module-tpg-3.1.0-alt1.src.rpm из Сизифа и
> попробовать собрать (--with-stuff по умолчанию).
> Этот python-module-tpg не соберётся с такой диагностикой:
> 
> Reading Package Lists...
> Building Dependency Tree...
> Selected version 2.4.4-alt2 for python-devel
> Selected version 0.29-alt3 for rpm-build-python
> rpm-build-python is already the newest version.
> Some packages could not be installed. This may mean that you have
> requested an impossible situation or if you are using the unstable
> distribution that some required packages have not yet been created
> or been moved out of Incoming.
> The following information may help to resolve the situation:
> 
> The following packages have unmet dependencies:
>   python-dev: Depends: python-base (= 2.4.4-alt2) but 2.4.4-alt2.1 is to be installed
> E: Broken packages
> install: failed to calculate package file list.
> install: Failed to generate package file list.
> 
> Причём:
> $ rpmquery -pR python-module-tpg-3.1.0-alt1.src.rpm |grep -v ^rpmlib
> python-devel = 2.4
> rpm-build-python >= 0.8
> $ workdir/aptbox/apt-get -y --print-uris install python-devel 2>&1 |grep ^Selecting
> Selecting python-dev for 'python-devel'
> $ workdir/aptbox/apt-get -y --print-uris install python-devel=2.4
> Reading Package Lists...
> Building Dependency Tree...
> Selected version 2.4.4-alt2 for python-devel
> Some packages could not be installed. This may mean that you have
> requested an impossible situation or if you are using the unstable
> distribution that some required packages have not yet been created
> or been moved out of Incoming.
> 
> Since you only requested a single operation it is extremely likely that
> the package is simply not installable and a bug report against
> that package should be filed.
> The following information may help to resolve the situation:
> 
> The following packages have unmet dependencies:
>   python-dev: Depends: python-base (= 2.4.4-alt2) but 2.4.4-alt2.1 is to be installed
> E: Broken packages

Суть проблемы в том, что когда просят установить виртуальный пакет с
версией, apt берет первый попавшийся реальный пакет, который дает этот
виртуальный пакет с этой версией.

apt-get.cc:
  2102           if (VerTag != 0)
  2103              // CNC:2003-11-05
  2104              if (TryToChangeVer(Pkg,Cache,VerOp,VerTag,VerIsRel) == false)
  2105                 return false;
  2106           if (TryToInstall(Pkg,Cache,Fix,Remove,BrokenFix,ExpectedInst) == false)
  2107              return false;

Проблема в процедуре TryToChangeVer.  Эта процедура пытается подыскать
реальный пакет (в данном случае для python-devel=2.4) и выбирает первое
что только можно выбрать.

--- apt-get.cc- 2006-12-14 23:36:02 +0000
+++ apt-get.cc  2006-12-14 23:38:04 +0000
@@ -1537,6 +1537,8 @@ bool TryToChangeVer(pkgCache::PkgIterato
                                 pkgVersionMatch::Version),VerOp);

    pkgCache::VerIterator Ver = Match.Find(Pkg);
+   for (pkgCache::VerIterator i = Ver; i.end() == false; i++)
+      fprintf(stderr, "Seen pkg %s ver %s\n", Pkg.Name(), i.VerStr());

    if (Ver.end() == true)
    {

$ PATH=$PWD:$PATH ~tmp/build/aptbox/apt-get --dry-run install python-devel=2.4
Reading Package Lists... Done                                                              
Building Dependency Tree... Done
Seen pkg python-devel ver 2.4.4-alt2
^^^
Selected version 2.4.4-alt2 for python-devel
Some packages could not be installed. This may mean that you have
requested an impossible situation or if you are using the unstable
distribution that some required packages have not yet been created
or been moved out of Incoming.

Since you only requested a single operation it is extremely likely that
the package is simply not installable and a bug report against
that package should be filed.
The following information may help to resolve the situation:

The following packages have unmet dependencies:
  python-dev: Depends: python-base (= 2.4.4-alt2) but 2.4.4-alt2.1 is to be installed
E: Broken packages
$

Т.е. 2.4.4-alt2.1 в этом месте не видно вообще.
Соответственно, дальше, вероятно, стоит ковырять pkgVersionMatch::Find.

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

Re: [devel] apt virtual packages

[Alexey Tourbin]

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

On Fri, Dec 15, 2006 at 02:40:38AM +0300, Alexey Tourbin wrote:
> Суть проблемы в том, что когда просят установить виртуальный пакет с
> версией, apt берет первый попавшийся реальный пакет, который дает этот
> виртуальный пакет с этой версией.
> 
> apt-get.cc:
>   2102           if (VerTag != 0)
>   2103              // CNC:2003-11-05
>   2104              if (TryToChangeVer(Pkg,Cache,VerOp,VerTag,VerIsRel) == false)
>   2105                 return false;
>   2106           if (TryToInstall(Pkg,Cache,Fix,Remove,BrokenFix,ExpectedInst) == false)
>   2107              return false;
> 
> Проблема в процедуре TryToChangeVer.  Эта процедура пытается подыскать
> реальный пакет (в данном случае для python-devel=2.4) и выбирает первое
> что только можно выбрать.

Если просто тупо отрубить TryToInstall, то всё начинает работать.

--- apt-get.cc- 2006-12-14 23:36:02 +0000
+++ apt-get.cc  2006-12-14 23:44:10 +0000
@@ -2099,10 +2101,10 @@ bool DoInstall(CommandLine &CmdL)
       }
       else
       {
-        if (VerTag != 0)
-           // CNC:2003-11-05
-           if (TryToChangeVer(Pkg,Cache,VerOp,VerTag,VerIsRel) == false)
-              return false;
+//      if (VerTag != 0)
+//         // CNC:2003-11-05
+//         if (TryToChangeVer(Pkg,Cache,VerOp,VerTag,VerIsRel) == false)
+//            return false;
         if (TryToInstall(Pkg,Cache,Fix,Remove,BrokenFix,ExpectedInst) == false)
            return false;
       }

> --- apt-get.cc- 2006-12-14 23:36:02 +0000
> +++ apt-get.cc  2006-12-14 23:38:04 +0000
> @@ -1537,6 +1537,8 @@ bool TryToChangeVer(pkgCache::PkgIterato
>                                  pkgVersionMatch::Version),VerOp);
> 
>     pkgCache::VerIterator Ver = Match.Find(Pkg);
> +   for (pkgCache::VerIterator i = Ver; i.end() == false; i++)
> +      fprintf(stderr, "Seen pkg %s ver %s\n", Pkg.Name(), i.VerStr());
> 
>     if (Ver.end() == true)
>     {

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

Re: [devel] apt virtual packages

[Alexey Tourbin]

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

On Fri, Dec 15, 2006 at 02:46:42AM +0300, Alexey Tourbin wrote:
> On Fri, Dec 15, 2006 at 02:40:38AM +0300, Alexey Tourbin wrote:
> > Суть проблемы в том, что когда просят установить виртуальный пакет с
> > версией, apt берет первый попавшийся реальный пакет, который дает этот
> > виртуальный пакет с этой версией.
> > 
> > apt-get.cc:
> >   2102           if (VerTag != 0)
> >   2103              // CNC:2003-11-05
> >   2104              if (TryToChangeVer(Pkg,Cache,VerOp,VerTag,VerIsRel) == false)
> >   2105                 return false;
> >   2106           if (TryToInstall(Pkg,Cache,Fix,Remove,BrokenFix,ExpectedInst) == false)
> >   2107              return false;
> > 
> > Проблема в процедуре TryToChangeVer.  Эта процедура пытается подыскать
> > реальный пакет (в данном случае для python-devel=2.4) и выбирает первое
> > что только можно выбрать.
> 
> Если просто тупо отрубить TryToInstall, то всё начинает работать.

С другой стороны, начинает работать install python-devel=3.0.

> --- apt-get.cc- 2006-12-14 23:36:02 +0000
> +++ apt-get.cc  2006-12-14 23:44:10 +0000
> @@ -2099,10 +2101,10 @@ bool DoInstall(CommandLine &CmdL)
>        }
>        else
>        {
> -        if (VerTag != 0)
> -           // CNC:2003-11-05
> -           if (TryToChangeVer(Pkg,Cache,VerOp,VerTag,VerIsRel) == false)
> -              return false;
> +//      if (VerTag != 0)
> +//         // CNC:2003-11-05
> +//         if (TryToChangeVer(Pkg,Cache,VerOp,VerTag,VerIsRel) == false)
> +//            return false;
>          if (TryToInstall(Pkg,Cache,Fix,Remove,BrokenFix,ExpectedInst) == false)
>             return false;
>        }

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

Re: [devel] apt virtual packages

[Alexey Tourbin]

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

On Fri, Dec 15, 2006 at 02:40:38AM +0300, Alexey Tourbin wrote:
> Т.е. 2.4.4-alt2.1 в этом месте не видно вообще.
> Соответственно, дальше, вероятно, стоит ковырять pkgVersionMatch::Find.

Вот фикс, с которым будет выбираться не первая попавшаяся, а последняя
попавшаяся версия.  install python-devel=2.4 теперь работает (в том
смысле, что установить можно только 2.4.4-alt2.1).

--- apt-pkg/versionmatch.cc-	2006-12-15 01:11:52 +0000
+++ apt-pkg/versionmatch.cc	2006-12-15 01:15:17 +0000
@@ -205,10 +205,10 @@ pkgCache::VerIterator pkgVersionMatch::F
          if (VerPrefixMatch || (HasRelease && strchr(PrvVerStr, '-') == NULL))
          {
             if (MatchVer(PrvVerStr,VerStr,VerPrefixMatch) == true)
-               return Prv.OwnerVer();
+               Ver = Prv.OwnerVer();
          } else {
             if (VS->CheckDep(PrvVerStr,VerOp,VerStr.c_str()) == true)
-               return Prv.OwnerVer();
+               Ver = Prv.OwnerVer();
          }
       }
    }

Впрочем install python-base=2.4.4-alt2 python-devel=2.4
не работает ни так ни сяк.

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

Re: [devel] apt virtual packages

[Michael Shigorin]

On Fri, Dec 15, 2006 at 04:25:03AM +0300, Alexey Tourbin wrote:
> Впрочем install python-base=2.4.4-alt2 python-devel=2.4
> не работает ни так ни сяк.

Разве там синтаксис указания версии не %name#%version
(python-base#2.4.4-alt2)?

-- 
 ---- WBR, Michael Shigorin <mike@altlinux.ru>
  ------ Linux.Kiev http://www.linux.kiev.ua/

Re: [devel] apt virtual packages

[Alexey Tourbin]

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

On Fri, Dec 15, 2006 at 03:49:22PM +0200, Michael Shigorin wrote:
> On Fri, Dec 15, 2006 at 04:25:03AM +0300, Alexey Tourbin wrote:
> > Впрочем install python-base=2.4.4-alt2 python-devel=2.4
> > не работает ни так ни сяк.
> 
> Разве там синтаксис указания версии не %name#%version
> (python-base#2.4.4-alt2)?

Как же ты думаешь хешер работает когда там указаны зависимости
что-то >= что-то?  Он их так в командную строку и пихает.

$ hsh --initroot ~tmp/build
...
$ hsh-install ~tmp/build 'perl-devel>5'
Preparing packages for installation...
perl-devel-5.8.8-alt5
$

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

Re: [devel] apt virtual packages

[Dmitry V. Levin]

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

On Fri, Dec 15, 2006 at 04:25:03AM +0300, Alexey Tourbin wrote:
> On Fri, Dec 15, 2006 at 02:40:38AM +0300, Alexey Tourbin wrote:
> > Т.е. 2.4.4-alt2.1 в этом месте не видно вообще.
> > Соответственно, дальше, вероятно, стоит ковырять pkgVersionMatch::Find.
> 
> Вот фикс, с которым будет выбираться не первая попавшаяся, а последняя
> попавшаяся версия.

Я правильно помню что они отсортированы и потому последняя попавшаяся
будет наибольшей?

> install python-devel=2.4 теперь работает (в том
> смысле, что установить можно только 2.4.4-alt2.1).
> 
> --- apt-pkg/versionmatch.cc-	2006-12-15 01:11:52 +0000
> +++ apt-pkg/versionmatch.cc	2006-12-15 01:15:17 +0000
> @@ -205,10 +205,10 @@ pkgCache::VerIterator pkgVersionMatch::F
>           if (VerPrefixMatch || (HasRelease && strchr(PrvVerStr, '-') == NULL))
>           {
>              if (MatchVer(PrvVerStr,VerStr,VerPrefixMatch) == true)
> -               return Prv.OwnerVer();
> +               Ver = Prv.OwnerVer();
>           } else {
>              if (VS->CheckDep(PrvVerStr,VerOp,VerStr.c_str()) == true)
> -               return Prv.OwnerVer();
> +               Ver = Prv.OwnerVer();
>           }
>        }
>     }
> 
> Впрочем install python-base=2.4.4-alt2 python-devel=2.4
> не работает ни так ни сяк.

Т.е. ни до патча ни после патча?
Интересно, сломает этот патч что-нибудь или нет?


-- 
ldv

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

Re: [devel] apt virtual packages

[Alexey Tourbin]

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

On Sat, Dec 16, 2006 at 01:27:48AM +0300, Dmitry V. Levin wrote:
> On Fri, Dec 15, 2006 at 04:25:03AM +0300, Alexey Tourbin wrote:
> > On Fri, Dec 15, 2006 at 02:40:38AM +0300, Alexey Tourbin wrote:
> > > Т.е. 2.4.4-alt2.1 в этом месте не видно вообще.
> > > Соответственно, дальше, вероятно, стоит ковырять pkgVersionMatch::Find.
> > 
> > Вот фикс, с которым будет выбираться не первая попавшаяся, а последняя
> > попавшаяся версия.
> 
> Я правильно помню что они отсортированы и потому последняя попавшаяся
> будет наибольшей?

Нет, я в этом не уверен.

> > install python-devel=2.4 теперь работает (в том
> > смысле, что установить можно только 2.4.4-alt2.1).
> > 
> > --- apt-pkg/versionmatch.cc-	2006-12-15 01:11:52 +0000
> > +++ apt-pkg/versionmatch.cc	2006-12-15 01:15:17 +0000
> > @@ -205,10 +205,10 @@ pkgCache::VerIterator pkgVersionMatch::F
> >           if (VerPrefixMatch || (HasRelease && strchr(PrvVerStr, '-') == NULL))
> >           {
> >              if (MatchVer(PrvVerStr,VerStr,VerPrefixMatch) == true)
> > -               return Prv.OwnerVer();
> > +               Ver = Prv.OwnerVer();
> >           } else {
> >              if (VS->CheckDep(PrvVerStr,VerOp,VerStr.c_str()) == true)
> > -               return Prv.OwnerVer();
> > +               Ver = Prv.OwnerVer();
> >           }
> >        }
> >     }
> > 
> > Впрочем install python-base=2.4.4-alt2 python-devel=2.4
> > не работает ни так ни сяк.
> 
> Т.е. ни до патча ни после патча?

Ни до ни после.
Потому что апт что делает.  Он ставит каждый пакет по очереди.

До и после патча два варианта.  Объясняю коротко, я уже вчера этой
лихорадкой переболел, сами там разбирайтесь.

1) Ставим python-base=2.4.4-alt2,
Пробуем ставить python-devel=2.4-alt2.1 => ОТСТОЙ

ИЛИ

2) Ставим python-base=2.4.4-alt2,
Ставим python-devel=2.4-alt2,
по зависимостям вытягивается python-strict=2.4-alt2.1 => ОТСТОЙ

В общем апт не должен ставить пакеты подряд.  А для каждого пакета
подряд он должен выделять подмножество пакетов удовлетворяющих условию.
А на втором проходе из этих подмножеств выделять одно непротиворечивое
множество которое подлежит установке.

> Интересно, сломает этот патч что-нибудь или нет?

Не сломает.  Он только влияет на виртуальные пакеты с версией.  А на
пакеты без версии типа autoconf	опять будет по алфавиту, а может
pkgVersionMatch::Find в этом случае вообще не включается.

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

Re: [devel] apt virtual packages

[Alexey I. Froloff]

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

* Alexey Tourbin <at@> [061216 01:48]:
> В общем апт не должен ставить пакеты подряд.  А для каждого пакета
> подряд он должен выделять подмножество пакетов удовлетворяющих условию.
> А на втором проходе из этих подмножеств выделять одно непротиворечивое
> множество которое подлежит установке.

http://people.debian.org/~dburrows/model.pdf

Правда я этот резольвер оторвал, потому как глючный дюже...

-- 
Regards,
Sir Raorn.

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

Re: [devel] apt virtual packages

[Alexey Tourbin]

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

On Sat, Dec 16, 2006 at 03:03:05PM +0300, Alexey I. Froloff wrote:
> * Alexey Tourbin <at@> [061216 01:48]:
> > В общем апт не должен ставить пакеты подряд.  А для каждого пакета
> > подряд он должен выделять подмножество пакетов удовлетворяющих условию.
> > А на втором проходе из этих подмножеств выделять одно непротиворечивое
> > множество которое подлежит установке.
> 
> http://people.debian.org/~dburrows/model.pdf
> Правда я этот резольвер оторвал, потому как глючный дюже...

Спасибо!  Я как раз думал, что это математическая задача.  То есть нужно
предложить конечный набор (последовательность) правил, как минимум для
install, а лучше ещё и для dist-upgrade, и желательно без весов.  То
есть чисто на теории множеств + исчислении предикатов, без чисел.   Я
пока не понимаю, можно ли эту "последовательность" будет развернуть в
конечный автомат, тогда ляпота.

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

С виртуальными пакетами и их версиями слишком много тонкостей.  Но любой
виртуальный пакет можно моделировать как дизъюнкцию реальных пакетов,
т.е. virtual := real1 | real2 | ...

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

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

Re: [devel] apt virtual packages

[Dmitry V. Levin]

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

On Sat, Dec 16, 2006 at 11:19:25PM +0300, Alexey Tourbin wrote:
> On Sat, Dec 16, 2006 at 03:03:05PM +0300, Alexey I. Froloff wrote:
> > * Alexey Tourbin <at@> [061216 01:48]:
> > > В общем апт не должен ставить пакеты подряд.  А для каждого пакета
> > > подряд он должен выделять подмножество пакетов удовлетворяющих условию.
> > > А на втором проходе из этих подмножеств выделять одно непротиворечивое
> > > множество которое подлежит установке.
> > 
> > http://people.debian.org/~dburrows/model.pdf
> > Правда я этот резольвер оторвал, потому как глючный дюже...
> 
> Спасибо!  Я как раз думал, что это математическая задача.  То есть нужно
> предложить конечный набор (последовательность) правил, как минимум для
> install, а лучше ещё и для dist-upgrade, и желательно без весов.  То
> есть чисто на теории множеств + исчислении предикатов, без чисел.

Я не верю что это можно сделать в общем случае, поскольку иногда решений
более одного.


-- 
ldv

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

Re: [devel] apt virtual packages

[Alexey Tourbin]

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

On Sun, Dec 17, 2006 at 12:02:22AM +0300, Dmitry V. Levin wrote:
> On Sat, Dec 16, 2006 at 11:19:25PM +0300, Alexey Tourbin wrote:
> > On Sat, Dec 16, 2006 at 03:03:05PM +0300, Alexey I. Froloff wrote:
> > > * Alexey Tourbin <at@> [061216 01:48]:
> > > > В общем апт не должен ставить пакеты подряд.  А для каждого пакета
> > > > подряд он должен выделять подмножество пакетов удовлетворяющих условию.
> > > > А на втором проходе из этих подмножеств выделять одно непротиворечивое
> > > > множество которое подлежит установке.
> > > 
> > > http://people.debian.org/~dburrows/model.pdf
> > > Правда я этот резольвер оторвал, потому как глючный дюже...
> > 
> > Спасибо!  Я как раз думал, что это математическая задача.  То есть нужно
> > предложить конечный набор (последовательность) правил, как минимум для
> > install, а лучше ещё и для dist-upgrade, и желательно без весов.  То
> > есть чисто на теории множеств + исчислении предикатов, без чисел.
> 
> Я не верю что это можно сделать в общем случае, поскольку иногда решений
> более одного.

В одном частном случае, когда решений больше одного, это называется
shift/reduce conflict.  Автоматы обходятся без чисел (без весов), это
фундаментальное.

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

Re: [devel] apt virtual packages

[Dmitry V. Levin]

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

On Sun, Dec 17, 2006 at 12:08:24AM +0300, Alexey Tourbin wrote:
> On Sun, Dec 17, 2006 at 12:02:22AM +0300, Dmitry V. Levin wrote:
> > On Sat, Dec 16, 2006 at 11:19:25PM +0300, Alexey Tourbin wrote:
> > > On Sat, Dec 16, 2006 at 03:03:05PM +0300, Alexey I. Froloff wrote:
> > > > * Alexey Tourbin <at@> [061216 01:48]:
> > > > > В общем апт не должен ставить пакеты подряд.  А для каждого пакета
> > > > > подряд он должен выделять подмножество пакетов удовлетворяющих условию.
> > > > > А на втором проходе из этих подмножеств выделять одно непротиворечивое
> > > > > множество которое подлежит установке.
> > > > 
> > > > http://people.debian.org/~dburrows/model.pdf
> > > > Правда я этот резольвер оторвал, потому как глючный дюже...
> > > 
> > > Спасибо!  Я как раз думал, что это математическая задача.  То есть нужно
> > > предложить конечный набор (последовательность) правил, как минимум для
> > > install, а лучше ещё и для dist-upgrade, и желательно без весов.  То
> > > есть чисто на теории множеств + исчислении предикатов, без чисел.
> > 
> > Я не верю что это можно сделать в общем случае, поскольку иногда решений
> > более одного.
> 
> В одном частном случае, когда решений больше одного, это называется
> shift/reduce conflict.  Автоматы обходятся без чисел (без весов), это
> фундаментальное.

Для автоматов пишут правила.


-- 
ldv

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

Re: [devel] apt virtual packages

[Alexey Tourbin]

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

On Sun, Dec 17, 2006 at 12:26:49AM +0300, Dmitry V. Levin wrote:
> > > Я не верю что это можно сделать в общем случае, поскольку иногда решений
> > > более одного.
> > 
> > В одном частном случае, когда решений больше одного, это называется
> > shift/reduce conflict.  Автоматы обходятся без чисел (без весов), это
> > фундаментальное.
> 
> Для автоматов пишут правила.

Можно одно конвертировать в другое.  То есть если веса по сути задают
convex hull тогда может быть их можно конвертировать в конечную
последовательность состояний.  Я же говорю, выбор в дискретном
автомате можно задать без весов (т.е. без бесконечного множества чисел).
В общем тут есть тонкости с точки зрения decidability и computability.

Мне надо ещё подумать.  Я это не изучил и не обдумал ещё как следует.
У меня пока только обрывки познания теплятся в пьяной голове.

Считай что я гоню.

> -- 
> ldv

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

Re: [devel] apt virtual packages

[Alexey Tourbin]

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

On Sat, Dec 16, 2006 at 01:27:48AM +0300, Dmitry V. Levin wrote:
> On Fri, Dec 15, 2006 at 04:25:03AM +0300, Alexey Tourbin wrote:
> > On Fri, Dec 15, 2006 at 02:40:38AM +0300, Alexey Tourbin wrote:
> > > Т.е. 2.4.4-alt2.1 в этом месте не видно вообще.
> > > Соответственно, дальше, вероятно, стоит ковырять pkgVersionMatch::Find.
> > 
> > Вот фикс, с которым будет выбираться не первая попавшаяся, а последняя
> > попавшаяся версия.
> 
> Я правильно помню что они отсортированы и потому последняя попавшаяся
> будет наибольшей?

Теперь я почти уверен, что они отсротированы, поэтому последняя
попавшаяся будет наибольшей.

$ perl -MAptPkg::Cache -le '$c=AptPkg::Cache->new;while(($k,$v)=each%$c){@v=@{$v->VersionList};if(@v>1){@v=map$$_{VerStr},@v;print"$k\t@v"}}' |
	awk '$2!=$3'
syslogd 1.4.1-alt26 1.4.1-alt25              
python-modules  2.4.4-alt2.1 2.4.4-alt2
vim-common      4:7.0.178-alt1 4:7.0.162-alt1 4:7.0.146-alt1 4:7.0.122-alt1
python-tools-modulator  2.4.4-alt2.1 2.4.4-alt2
libaprutil      1:0.9.13-alt1 1:0.9.12-alt1
...
$

Они должны быть отсортированы при создании pkgcache.bin.
Предположительно здесь:

$ grep qsort apt-pkg/orderlist.cc
   qsort(List,End - List,sizeof(*List),&OrderCompareB);   
   qsort(List,End - List,sizeof(*List),&OrderCompareA);
$

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

Re: [devel] apt virtual packages

[Alexey Tourbin]

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

On Sun, Dec 17, 2006 at 12:58:56PM +0300, Alexey Tourbin wrote:
> Теперь я почти уверен, что они отсротированы, поэтому последняя
> попавшаяся будет наибольшей.
> 
> $ perl -MAptPkg::Cache -le '$c=AptPkg::Cache->new;while(($k,$v)=each%$c){@v=@{$v->VersionList};if(@v>1){@v=map$$_{VerStr},@v;print"$k\t@v"}}' |
> 	awk '$2!=$3'
> syslogd 1.4.1-alt26 1.4.1-alt25              
> python-modules  2.4.4-alt2.1 2.4.4-alt2
> vim-common      4:7.0.178-alt1 4:7.0.162-alt1 4:7.0.146-alt1 4:7.0.122-alt1
> python-tools-modulator  2.4.4-alt2.1 2.4.4-alt2
> libaprutil      1:0.9.13-alt1 1:0.9.12-alt1
> ...
> $

Что-то не сходится.  Из этого получается что последняя попавшаяся будет
наименьшей.  Надо ещё подумать.

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

Re: [devel] apt virtual packages

[Alexey Tourbin]

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

On Sun, Dec 17, 2006 at 01:02:23PM +0300, Alexey Tourbin wrote:
> On Sun, Dec 17, 2006 at 12:58:56PM +0300, Alexey Tourbin wrote:
> > Теперь я почти уверен, что они отсротированы, поэтому последняя
> > попавшаяся будет наибольшей.
> > 
> > $ perl -MAptPkg::Cache -le '$c=AptPkg::Cache->new;while(($k,$v)=each%$c){@v=@{$v->VersionList};if(@v>1){@v=map$$_{VerStr},@v;print"$k\t@v"}}' |
> > 	awk '$2!=$3'
> > syslogd 1.4.1-alt26 1.4.1-alt25              
> > python-modules  2.4.4-alt2.1 2.4.4-alt2
> > vim-common      4:7.0.178-alt1 4:7.0.162-alt1 4:7.0.146-alt1 4:7.0.122-alt1
> > python-tools-modulator  2.4.4-alt2.1 2.4.4-alt2
> > libaprutil      1:0.9.13-alt1 1:0.9.12-alt1
> > ...
> > $
> 
> Что-то не сходится.  Из этого получается что последняя попавшаяся будет
> наименьшей.  Надо ещё подумать.

Всё правильно, сортировка по возрастанию версии касается ProvidesList.

$ perl -MAptPkg::Cache -le '$c=AptPkg::Cache->new;@v=map$$_{OwnerVer}{VerStr},@{$$c{"python-devel"}{ProvidesList}};print"@v"'
2.3.5-alt1 2.4.4-alt2 2.4.4-alt2.1
$

В общем нутром чую, что Pkg.ProvidesList() т.е. список --whatprovides
отсортирован по версиям реальных пакетов, которые предоставляют
виртуальную зависимость.

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

[devel] [PATCH] apt virtual packages

[Alexey Tourbin]

[-- Attachment #1.1: Type: text/plain, Size: 1350 bytes --]

On Fri, Dec 15, 2006 at 04:25:03AM +0300, Alexey Tourbin wrote:
> On Fri, Dec 15, 2006 at 02:40:38AM +0300, Alexey Tourbin wrote:
> > Т.е. 2.4.4-alt2.1 в этом месте не видно вообще.
> > Соответственно, дальше, вероятно, стоит ковырять pkgVersionMatch::Find.
> 
> Вот фикс, с которым будет выбираться не первая попавшаяся, а последняя
> попавшаяся версия.  install python-devel=2.4 теперь работает (в том
> смысле, что установить можно только 2.4.4-alt2.1).
> 
> --- apt-pkg/versionmatch.cc-	2006-12-15 01:11:52 +0000
> +++ apt-pkg/versionmatch.cc	2006-12-15 01:15:17 +0000
> @@ -205,10 +205,10 @@ pkgCache::VerIterator pkgVersionMatch::F
>           if (VerPrefixMatch || (HasRelease && strchr(PrvVerStr, '-') == NULL))
>           {
>              if (MatchVer(PrvVerStr,VerStr,VerPrefixMatch) == true)
> -               return Prv.OwnerVer();
> +               Ver = Prv.OwnerVer();
>           } else {
>              if (VS->CheckDep(PrvVerStr,VerOp,VerStr.c_str()) == true)
> -               return Prv.OwnerVer();
> +               Ver = Prv.OwnerVer();
>           }
>        }
>     }
> 
> Впрочем install python-base=2.4.4-alt2 python-devel=2.4
> не работает ни так ни сяк.

Этот патч был неправильным, потому что версии в ProvidesList на самом
деле не отсортированы.  Вот правильный вариант патча (прицеплен).

[-- Attachment #1.2: versionmatch.patch --]
[-- Type: text/plain, Size: 3061 bytes --]

--- apt-0.5.15lorg2/apt-pkg/versionmatch.h-	2006-06-17 22:00:13 +0400
+++ apt-0.5.15lorg2/apt-pkg/versionmatch.h	2006-12-17 15:49:08 +0300
@@ -36,6 +36,7 @@
 #endif
 
 #include <string>
+#include <list>
 #include <apt-pkg/pkgcache.h>
 
 using std::string;
@@ -70,6 +71,7 @@
 			       
    // CNC:2003-11-05
    pkgVersionMatch(string Data,MatchType Type,int Op=pkgCache::Dep::Equals);
+   std::list<pkgCache::VerIterator> FindAll(pkgCache::PkgIterator Pkg);
 };
 
 #endif
--- apt-0.5.15lorg2/apt-pkg/versionmatch.cc-	2006-12-15 04:11:52 +0300
+++ apt-0.5.15lorg2/apt-pkg/versionmatch.cc	2006-12-17 16:38:44 +0300
@@ -164,11 +164,17 @@
 // VersionMatch::Find - Locate the best match for the select type	/*{{{*/
 // ---------------------------------------------------------------------
 /* */
-pkgCache::VerIterator pkgVersionMatch::Find(pkgCache::PkgIterator Pkg)
+static inline bool
+vercmpOrder(const pkgCache::VerIterator &a, const pkgCache::VerIterator &b)
+{
+   return a.CompareVer(b) < 0;
+}
+std::list<pkgCache::VerIterator> pkgVersionMatch::FindAll(pkgCache::PkgIterator Pkg)
 {
    // CNC:2003-11-05
    pkgVersioningSystem *VS = Pkg.Cache()->VS;
    pkgCache::VerIterator Ver = Pkg.VersionList();
+   std::list<pkgCache::VerIterator> found;
 
    for (; Ver.end() == false; Ver++)
    {
@@ -178,10 +184,10 @@
          if (VerPrefixMatch)
 	 {
 	    if (MatchVer(Ver.VerStr(),VerStr,VerPrefixMatch) == true)
-	       return Ver;
+	       found.push_back(Ver);
 	 } else {
 	    if (VS->CheckDep(Ver.VerStr(),VerOp,VerStr.c_str()) == true)
-	       return Ver;
+	       found.push_back(Ver);
 	 }
 
 	 continue;
@@ -189,8 +195,11 @@
       
       for (pkgCache::VerFileIterator VF = Ver.FileList(); VF.end() == false; VF++)
 	 if (FileMatch(VF.File()) == true)
-	    return Ver;
+	    found.push_back(Ver);
    }
+
+   if (found.size() > 0)
+      goto done;
       
    // CNC:2003-11-11 - Virtual package handling.
    if (Type == Version)
@@ -205,15 +214,32 @@
          if (VerPrefixMatch || (HasRelease && strchr(PrvVerStr, '-') == NULL))
          {
             if (MatchVer(PrvVerStr,VerStr,VerPrefixMatch) == true)
-               return Prv.OwnerVer();
+               found.push_back(Prv.OwnerVer());
          } else {
             if (VS->CheckDep(PrvVerStr,VerOp,VerStr.c_str()) == true)
-               return Prv.OwnerVer();
+               found.push_back(Prv.OwnerVer());
          }
       }
    }
 
-   // This will be Ended by now.
+done:
+   // best versions go first
+   found.sort(vercmpOrder);
+   found.unique();
+   found.reverse();
+   return found;
+}
+
+pkgCache::VerIterator pkgVersionMatch::Find(pkgCache::PkgIterator Pkg)
+{
+   std::list<pkgCache::VerIterator> found = FindAll(Pkg);
+   if (found.size() > 0)
+      return found.front();
+
+   // return "empty" iterator at its end
+   pkgCache::VerIterator Ver = Pkg.VersionList();
+   while (Ver.end() == false)
+      Ver++;
    return Ver;
 }
 									/*}}}*/

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

[devel] gendiff

[Alexey Tourbin]

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

On Sun, Dec 17, 2006 at 04:43:40PM +0300, Alexey Tourbin wrote:
> --- apt-0.5.15lorg2/apt-pkg/versionmatch.h-	2006-06-17 22:00:13 +0400
> +++ apt-0.5.15lorg2/apt-pkg/versionmatch.h	2006-12-17 15:49:08 +0300
> @@ -36,6 +36,7 @@
>  #endif
>  
>  #include <string>
> +#include <list>
>  #include <apt-pkg/pkgcache.h>
>  
>  using std::string;
> @@ -70,6 +71,7 @@
>  			       
>     // CNC:2003-11-05
>     pkgVersionMatch(string Data,MatchType Type,int Op=pkgCache::Dep::Equals);
> +   std::list<pkgCache::VerIterator> FindAll(pkgCache::PkgIterator Pkg);
>  };

Надо бы в gendiff запихать опцию diff -p.

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

Re: [devel] apt virtual packages

[Alexey I. Froloff]

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

* Dmitry V. Levin <ldv@> [061217 00:13]:
> > > http://people.debian.org/~dburrows/model.pdf
> > > Правда я этот резольвер оторвал, потому как глючный дюже...
> Я не верю что это можно сделать в общем случае, поскольку иногда решений
> более одного.
Да.  И aptitude предлагает все эти решения пользователю.  Только
у меня этот резольвер вываливался на ассертах :-(

-- 
Regards,
Sir Raorn.

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

Re: [devel] apt virtual packages

[Alexey Tourbin]

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

On Sun, Dec 17, 2006 at 04:51:50PM +0300, Alexey I. Froloff wrote:
> * Dmitry V. Levin <ldv@> [061217 00:13]:
> > > > http://people.debian.org/~dburrows/model.pdf
> > > > Правда я этот резольвер оторвал, потому как глючный дюже...
> > Я не верю что это можно сделать в общем случае, поскольку иногда решений
> > более одного.
> Да.  И aptitude предлагает все эти решения пользователю.  Только
> у меня этот резольвер вываливался на ассертах :-(

Он там доказывает что в его модели проблема поиска оптимального решения
NP-complete (это очень плохо по сложности).  Доказывает по аналогии с
CNF-SAT, а как это доказывается для CNF-SAT я не знаю, поэтому ничего
не понял.  В общем на будущее надо скачивать книжку Papadimitriou
Computational Complexity, может у кого-нибудь уже есть?

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

Re: [devel] [PATCH] apt virtual packages

[Alexey Tourbin]

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

On Sun, Dec 17, 2006 at 04:43:40PM +0300, Alexey Tourbin wrote:
> +static inline bool
> +vercmpOrder(const pkgCache::VerIterator &a, const pkgCache::VerIterator &b)
> +{
> +   return a.CompareVer(b) < 0;
> +}

Кстати вот тут должно быть "<" или "<="?
Что-то у Страуса примера на сортировку с предикатом порядка нету.

> +done:
> +   // best versions go first
> +   found.sort(vercmpOrder);
> +   found.unique();
> +   found.reverse();
> +   return found;
> +}

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

Re: [devel] [PATCH] apt virtual packages

[Alexey Tourbin]

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

On Sun, Dec 17, 2006 at 05:14:14PM +0300, Alexey Tourbin wrote:
> On Sun, Dec 17, 2006 at 04:43:40PM +0300, Alexey Tourbin wrote:
> > +static inline bool
> > +vercmpOrder(const pkgCache::VerIterator &a, const pkgCache::VerIterator &b)
> > +{
> > +   return a.CompareVer(b) < 0;
> > +}
> 
> Кстати вот тут должно быть "<" или "<="?
> Что-то у Страуса примера на сортировку с предикатом порядка нету.

Ага, тут похоже должно быть "<=".  Дело в том, что всего одной операции
"<=" достаточно, чтобы логически вывести все остальные операции сравнения.

(==)(a,b) := (a<=b)&&(b<=a)
(>=)(a,b) := !(b<=a)
(!=)(a,b) := !(a==b)
(<)(a,b)  := (a<=b)&&(a!=b)
(>)(a,b)  := (a>=b)&&(a!=b)

А в случае с одной только операцией "<" такой ляпоты не получается,
потому что не удается логически вывести равенство.

А может я чего-то не понимаю?  Кто точно знает?

> > +done:
> > +   // best versions go first
> > +   found.sort(vercmpOrder);
> > +   found.unique();
> > +   found.reverse();
> > +   return found;
> > +}

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

Re: [devel] [PATCH] apt virtual packages

[Alexey Tourbin]

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

On Sun, Dec 17, 2006 at 07:09:33PM +0300, Alexey Tourbin wrote:
> On Sun, Dec 17, 2006 at 05:14:14PM +0300, Alexey Tourbin wrote:
> > On Sun, Dec 17, 2006 at 04:43:40PM +0300, Alexey Tourbin wrote:
> > > +static inline bool
> > > +vercmpOrder(const pkgCache::VerIterator &a, const pkgCache::VerIterator &b)
> > > +{
> > > +   return a.CompareVer(b) < 0;
> > > +}
> > 
> > Кстати вот тут должно быть "<" или "<="?
> > Что-то у Страуса примера на сортировку с предикатом порядка нету.
> 
> Ага, тут похоже должно быть "<=".  Дело в том, что всего одной операции
> "<=" достаточно, чтобы логически вывести все остальные операции сравнения.
> 
> (==)(a,b) := (a<=b)&&(b<=a)
> (>=)(a,b) := !(b<=a)

Тут у меня логическая ошибка, кажется должно быть

  (>=)(a,b) := !(b<=a)||(b==a)

Но не суть.  Суть в том что нестрогий порядок позволяет доопределить
равенство, а строгий не позволяет.

> (!=)(a,b) := !(a==b)
> (<)(a,b)  := (a<=b)&&(a!=b)
> (>)(a,b)  := (a>=b)&&(a!=b)

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

Re: [devel] [PATCH] apt virtual packages

[Alexey Tourbin]

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

On Sun, Dec 17, 2006 at 07:09:33PM +0300, Alexey Tourbin wrote:
> Ага, тут похоже должно быть "<=".  Дело в том, что всего одной операции
> "<=" достаточно, чтобы логически вывести все остальные операции сравнения.
> 
> (==)(a,b) := (a<=b)&&(b<=a)
> (>=)(a,b) := !(b<=a)
> (!=)(a,b) := !(a==b)
> (<)(a,b)  := (a<=b)&&(a!=b)
> (>)(a,b)  := (a>=b)&&(a!=b)
> 
> А в случае с одной только операцией "<" такой ляпоты не получается,
> потому что не удается логически вывести равенство.

Кажется я гоню, причем от безграмотности а не от большого ума.  Если
есть отношение "<", то равенство можно доопределить через отрицание:

(a==b) := !((a<b)||(b<a))

Проверка
(1==1) == !((1<1)||(1<1)) == !(FALSE||FALSE) = !FALSE = TRUE
(1==2) == !((1<2)||(2<1)) == !(TRUE||FALSE) = !TRUE = FALSE

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

[devel] Papadimitriou

[Alexey Tourbin]

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

On Sun, Dec 17, 2006 at 05:12:47PM +0300, Alexey Tourbin wrote:
> не понял.  В общем на будущее надо скачивать книжку Papadimitriou
> Computational Complexity, может у кого-нибудь уже есть?

Скачалось.  Кому надо стучитсь за что купил за то продам.

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

[devel] std::sort

[Alex V. Myltsev]

On Sun, 17 Dec 2006 19:41:28 +0300
Alexey Tourbin wrote:
> Кажется я гоню, причем от безграмотности а не от большого ума.  Если
> есть отношение "<", то равенство можно доопределить через отрицание:
> (a==b) := !((a<b)||(b<a))
Да, специально для этого есть требование в STL:
The ordering relation on RandomAccessIterator's value type [must be]
a strict weak ordering.

Вообще, полезное чтение http://www.sgi.com/tech/stl/sort.html --
например, там ясно написано, что предикат -- это по смыслу operator<.

Re: [devel] [PATCH] apt virtual packages

[Dmitry V. Levin]

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

On Sun, Dec 17, 2006 at 05:14:14PM +0300, Alexey Tourbin wrote:
> On Sun, Dec 17, 2006 at 04:43:40PM +0300, Alexey Tourbin wrote:
> > +static inline bool
> > +vercmpOrder(const pkgCache::VerIterator &a, const pkgCache::VerIterator &b)
> > +{
> > +   return a.CompareVer(b) < 0;
> > +}
> 
> Кстати вот тут должно быть "<" или "<="?

Для std:: должно быть less.


-- 
ldv

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

Re: [devel] apt virtual packages

[Alex V. Myltsev]

On Sun, 17 Dec 2006 17:12:47 +0300
Alexey Tourbin wrote:
> Он там доказывает что в его модели проблема поиска оптимального
> решения NP-complete (это очень плохо по сложности).
Это в худшем случае очень плохо по сложности, а на практике может
отлично работать. Про это там дальше хорошо написано, см. раздел 
"Don't panic".

> Доказывает по
> аналогии с CNF-SAT, а как это доказывается для CNF-SAT я не знаю,
> поэтому ничего не понял.
1) Обычно NP-полноту задачи выполнимости КНФ доказывают, строя сведение
к ней для любой задачи из NP. Рассказать в общих чертах или offtopic?
2) Доказательство там не "по аналогии" с ВЫП, а сведением ВЫП к задаче
существования корректной установки. Знать доказательство NP-полноты ВЫП
здесь не нужно, достаточно помнить факт.

Re: [devel] [PATCH] apt virtual packages

[Hihin Ruslan]

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

Здравствуйте Alexey Tourbin
  В сообщении от Sunday 17 December 2006 19:15 Alexey Tourbin 
написал(a):
 > On Sun, Dec 17, 2006 at 07:09:33PM +0300, Alexey Tourbin wrote:
 > > On Sun, Dec 17, 2006 at 05:14:14PM +0300, Alexey Tourbin wrote:
 > > > On Sun, Dec 17, 2006 at 04:43:40PM +0300, Alexey Tourbin wrote:
 > > > > +static inline bool
 > > > >
 > > > > +vercmpOrder(const pkgCache::VerIterator &a, const
 > > > > pkgCache::VerIterator &b)
 > > > >
 > > > > +{
 > > > >
 > > > > +   return a.CompareVer(b) < 0;
 > > > >
 > > > > +}
 > > >
 > > > Кстати вот тут должно быть "<" или "<="?
 > > >
 > > > Что-то у Страуса примера на сортировку с предикатом порядка
 > > > нету.
 > >
 > > Ага, тут похоже должно быть "<=".  Дело в том, что всего одной
 > > операции
 > >
 > > "<=" достаточно, чтобы логически вывести все остальные операции
 > > сравнения.
 > >
 > >
 > >
 > > (==)(a,b) := (a<=b)&&(b<=a)
 > >
 > > (>=)(a,b) := !(b<=a)
Это явно неправильно
 (>=)(a,b) := !(b<a)
>
 > Тут у меня логическая ошибка, кажется должно быть
 >
 >
 >
 >   (>=)(a,b) := !(b<=a)||(b==a)
 >
 > Но не суть.  Суть в том что нестрогий порядок позволяет доопределить
 >
 > равенство, а строгий не позволяет.

Что-то я не очень пойму к чему это всё , но 
!(>=)(a,b) := (<)(a,b) :=  (a<b)
и обратно
!(>)(a,b) := (<=)(a,b) :=  (a<=b)
(>)(a,b) := !(  (<)(a,b)||(==)(a,b) )  = !(a<=b) 
т.е. строгий и нестрогий порядок - суть просто обратные действия 
(отношения).
 
 > > (!=)(a,b) := !(a==b)
 > >
 > > (<)(a,b)  := (a<=b)&&(a!=b)
 > >
 > > (>)(a,b)  := (a>=b)&&(a!=b)

-- 
С уважением Xихин Руслан

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

Re: [devel] std::sort

[Alexey Tourbin]

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

On Sun, Dec 17, 2006 at 07:49:29PM +0300, Alex V. Myltsev wrote:
> On Sun, 17 Dec 2006 19:41:28 +0300
> Alexey Tourbin wrote:
> > Кажется я гоню, причем от безграмотности а не от большого ума.  Если
> > есть отношение "<", то равенство можно доопределить через отрицание:
> > (a==b) := !((a<b)||(b<a))
> Да, специально для этого есть требование в STL:
> The ordering relation on RandomAccessIterator's value type [must be]
> a strict weak ordering.

Спасибо.  Что такое "strict weak ordering" по-русски?  Антирефлексивное
неполное отношение порядка?  То есть некоторые элементы несравнимы и
неравны, а те которые сравнимы обязательно неравны.  Не посоветуйте
книжечки какой-нибудь для просветления мозгов?  Я две книжки про это
дело время от времени в туалете читаю -- Новиков "Дискретная математика
для программистов" и Адельсон-Вельский--Кузнецов "Дискретная математика
для инженера".  Что-то полного просветления пока не наступило.

> Вообще, полезное чтение http://www.sgi.com/tech/stl/sort.html --
> например, там ясно написано, что предикат -- это по смыслу operator<.

Да я Страуса листал а у него книжка толстая и наполовину бестолковая.

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

Re: [devel] [PATCH] apt virtual packages

[Alexey Tourbin]

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

On Sun, Dec 17, 2006 at 08:05:06PM +0300, Hihin Ruslan wrote:
>  > > (>=)(a,b) := !(b<=a)
> Это явно неправильно
>  (>=)(a,b) := !(b<a)

Да.  Но операция "<" ещё не определена.  Суть в том чтобы
последовательно определять операции через предыдующие введенные
операции.  Я уже исправился.

В остальном вы, наверное, правы.

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

Re: [devel] apt virtual packages

[Alexey Tourbin]

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

On Sun, Dec 17, 2006 at 07:58:08PM +0300, Alex V. Myltsev wrote:
> On Sun, 17 Dec 2006 17:12:47 +0300
> Alexey Tourbin wrote:
> > Он там доказывает что в его модели проблема поиска оптимального
> > решения NP-complete (это очень плохо по сложности).
> Это в худшем случае очень плохо по сложности, а на практике может
> отлично работать. Про это там дальше хорошо написано, см. раздел 
> "Don't panic".
> 
> > Доказывает по
> > аналогии с CNF-SAT, а как это доказывается для CNF-SAT я не знаю,
> > поэтому ничего не понял.
> 1) Обычно NP-полноту задачи выполнимости КНФ доказывают, строя сведение
> к ней для любой задачи из NP. Рассказать в общих чертах или offtopic?

Не оффтопик, но погодите.  Что такое КНФ я знаю хорошо, а что такое NP
я знаю хуже.  Нужно мне ещё самообразоваться.  Но сегодня выходной а
скоро будет новый год, борода из ваты, пьянь такая, и дел из-за синей
горы подвалило в общем ой.

Просто сейчас надо апт зафиксить чтобы он во всех типичных случаях всё
ставил как надо.  Кроме меня желающих нет я так понимаю.  Полиномиальная
трудность булевых функций это хорошо но пожалуй уже на следующий год.

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

Re: [devel] [JT] std::sort

[Alex V. Myltsev]

On Sun, 17 Dec 2006 20:15:15 +0300
Alexey Tourbin wrote:
> Что такое "strict weak ordering" по-русски?
Не знаю.
> Антирефлексивное неполное отношение порядка? То есть некоторые
> элементы несравнимы и неравны, а те которые сравнимы обязательно
> неравны.
Этого мало. Это у вас вроде строгий частичный порядок получается, но он
допускает такую ситуацию: a<b<c<e, a<d<e, пары (b,d) и (c,d) несравнимы.
То есть несравнимость может быть нетранзитивной, а это плохо: например,
подают нам на вход последовательность {a,c,d,b,e}; она неупорядочена, а
сравнением соседних элементов мы этого обнаружить не можем. И
сортировка вся идёт лесом.

А требуемый strict weak ordering -- это почти полный порядок, но только
каждый элемент может быть в нескольких экземплярах. "Нестрогий полный
порядок", что ли :).

> Да я Страуса листал а у него книжка толстая и наполовину бестолковая.
Google лучше.

Re: [devel] [JT] apt virtual packages

[Alex V. Myltsev]

On Sun, 17 Dec 2006 20:45:11 +0300
Alexey Tourbin wrote:
> Просто сейчас надо апт зафиксить чтобы он во всех типичных случаях всё
> ставил как надо.
> Полиномиальная трудность булевых функций это хорошо но пожалуй уже на
> следующий год.
Вооот. Из чего следует вывод: P там или NP, но задачу решать надо, а всё
это доказательство в model.pdf было только для наукообразности.

Re: [devel] [JT] std::sort

[Alexey Tourbin]

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

On Sun, Dec 17, 2006 at 08:54:19PM +0300, Alex V. Myltsev wrote:
> On Sun, 17 Dec 2006 20:15:15 +0300
> Alexey Tourbin wrote:
> > Что такое "strict weak ordering" по-русски?
> Не знаю.
> > Антирефлексивное неполное отношение порядка? То есть некоторые
> > элементы несравнимы и неравны, а те которые сравнимы обязательно
> > неравны.
> Этого мало. Это у вас вроде строгий частичный порядок получается, но он

Да.  Тогда что означает "weak"?

> допускает такую ситуацию: a<b<c<e, a<d<e, пары (b,d) и (c,d) несравнимы.
> То есть несравнимость может быть нетранзитивной, а это плохо: например,
> подают нам на вход последовательность {a,c,d,b,e}; она неупорядочена, а
> сравнением соседних элементов мы этого обнаружить не можем. И
> сортировка вся идёт лесом.
> 
> А требуемый strict weak ordering -- это почти полный порядок, но только
> каждый элемент может быть в нескольких экземплярах. "Нестрогий полный
> порядок", что ли :).

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

Re: [devel] [JT] apt virtual packages

[Alexey Tourbin]

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

On Sun, Dec 17, 2006 at 08:57:08PM +0300, Alex V. Myltsev wrote:
> On Sun, 17 Dec 2006 20:45:11 +0300
> Alexey Tourbin wrote:
> > Просто сейчас надо апт зафиксить чтобы он во всех типичных случаях всё
> > ставил как надо.
> > Полиномиальная трудность булевых функций это хорошо но пожалуй уже на
> > следующий год.
> Вооот. Из чего следует вывод: P там или NP, но задачу решать надо, а всё
> это доказательство в model.pdf было только для наукообразности.

Нет.  Это вовсе не из наукообразности в смысле чистоплюйства.
Предел практической вычислимости подступает к горлу довольно быстро.
Вот один дебилушка который реализовал продвинутый dependency solver пишет:

  One of the known issues in I've been trying to address in Smart for
  a while is the freezing effect that happens when a very complex
  upgrading situation (such as a full distribution upgrade) results in
  a combinatory explosion due to the number of choices to be
  analysed. Unfortunately, I never had time to really put in practice a
  reasonable solution for the problem. At this point, the beauty of
  open source software starts to shine.                                                                                                     
                                                                                                                                            
  A few weeks ago, Eran Tromer got close to the project and started
  researching and discussing about the issue. Not only that, but he
  produced actual patches that change the algorithm to prune the search
  space and find resonable solutions in acceptable timings. These
  patches were applied into the development version, and included in
  release 0.50rc1.                                                       
                                                                                                                                            
  The preliminary results are quite impressive. David Farning has
  tested Smart 0.50rc1 with Fedora in several situations, and reported:     
                                                                                                                                            
  fc4->fc5, fc4->fc6, fc4->devel, fc5->fc6, all calculate updates and
  upgrades in a few minutes on a vm with 512M, using standard repos +
  Freshrpms and Dries. Much quicker than with 0.42.                                                                                         

http://blog.labix.org

Несклько минут уходит на то, чтобы вычислить dist-upgrade на две тысячи
пакетов.  При том что никаких сложных переименований там на самом деле
нет, просто резольвер перебирает все-все-все возможные варианты.  А до
этого полчаса наверное обновление считал, и это преподносится как
большой успех!

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

Re: [devel] [JT] std::sort

[Hihin Ruslan]

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

Здравствуйте Alex V. Myltsev
  В сообщении от Sunday 17 December 2006 20:54 Alex V. Myltsev 
написал(a):

 > Этого мало. Это у вас вроде строгий частичный порядок получается, но
 > он
 >
 > допускает такую ситуацию: a<b<c<e, a<d<e, пары (b,d) и (c,d)
 > несравнимы.
  > То есть несравнимость может быть нетранзитивной, а это плохо:
 > например,
 >
 > подают нам на вход последовательность {a,c,d,b,e}; она
 > неупорядочена, а
  > сравнением соседних элементов мы этого обнаружить не можем. И
  > сортировка вся идёт лесом.
Как это не парадоксально,  но если читать что несравнимость - это один 
из видов равенства, то можно упорядочить в - вашем примере 
{a,b,c,d,e} или {a,(b,,d),e} - где (c,d,e) - любая перестановка из c,d,e
 Интереснее вариант  a<b<c<e, b<d<e, пары (a,d), (c,d) несравнимы
Имеем {a,b,(c,d),e}, т.е. значение (сортировочной меры) несравнимого 
элемента должно быть равно максимальному из несравнимых с ней 
элементов.
  Если-бы упорядочивали по убыванию, а не по возрастанию, то тогда-бы 
был минимальный элемент.
 В любом случае первый этап такой сортировки - каждому элементу 
присвоить сортировочную меру (вес), а потом сортировать уже элементы по 
этой сортировочной мере.

Т.е. имеем соизмеримые элементы - с ними всё ясно - всегда можно 
проиндексировать их, и несравнимые - для них вначале (до присвоения 
реального веса) можно считать, что их вес очень большой и равен 
условному максимуму. Но как только находится максимальный вес 
несравнимого элемента, присваивается этот вес.

В нашем примере имеем первоначальные веса :
Исходя из b<d<e:
b=1
d=2
e=3

Исходя из a<b<c :
a=1
b=2
c=3

Т.к. у b входит в оба "графа", то имеем откорректированные веса первой 
ветки:
b=2; d=3; e=4;

Т.к. все ветки дерева пройдены и все элементы пройдены - имеем :
a=1 b=2 c=3 d=3 e=3
 
В общем имеем ситуацию сортировки элементов графа 


 > А требуемый strict weak ordering -- это почти полный порядок, но
 > только
 > каждый элемент может быть в нескольких экземплярах. "Нестрогий
 > полный
 > порядок", что ли :).
Это тоже алгоритм, но приводит к дублированию элементов.

 >
 > > Да я Страуса листал а у него книжка толстая и наполовину
 > > бестолковая.
 >
 > Google лучше.
 Может  я мои мысли помогут :)
 
-- 
С уважением Xихин Руслан

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

Re: [devel] [JT] std::sort

[Hihin Ruslan]

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

Здравствуйте Hihin Ruslan
  В сообщении от Sunday 17 December 2006 22:42 Hihin Ruslan написал(a):

 >
 > Т.к. все ветки дерева пройдены и все элементы пройдены - имеем :
 >
 > a=1 b=2 c=3 d=3 e=3
 a=1 b=2 c=3 d=3 e=4
:)
-- 
С уважением Xихин Руслан

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

Re: [devel] [JT] std::sort

[Alex V. Myltsev]

On Sun, 17 Dec 2006 22:42:52 +0300 Hihin Ruslan wrote:
>  > подают нам на вход последовательность {a,c,d,b,e}; она
>  > неупорядочена, а
>  > сравнением соседних элементов мы этого обнаружить не можем. И
>  > сортировка вся идёт лесом.
> Как это не парадоксально,  но если читать что несравнимость - это
> один из видов равенства, то можно упорядочить в - вашем примере 
Конечно, можно. Это же частичный порядок, никто не мешает его
доопределить %-).
> В общем имеем ситуацию сортировки элементов графа 
Угу. И что-то подсказывает мне, что это дольше, чем сортировка
множества с полным порядком, которая чаще всего нужна на практике.
Поэтому и появилось в STL упомянутое требование. (А те, кому
действительно нужно сортировать графы, могут написать собственный
sort.)

(Мне кажется, продолжать тему в этом направлении можно только в
smoke-room.)

Re: [devel] [JT] std::sort

[Hihin Ruslan]

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

Здравствуйте Hihin Ruslan
  В сообщении от Sunday 17 December 2006 23:01 Hihin Ruslan написал(a):
 > Здравствуйте Hihin Ruslan
 >
 >   В сообщении от Sunday 17 December 2006 22:42 Hihin Ruslan 
написал(a):
 >  > Т.к. все ветки дерева пройдены и все элементы пройдены - имеем :
 >  >
 >  >
 >  >
 >  > a=1 b=2 c=3 d=3 e=3
 >
 >  a=1 b=2 c=3 d=3 e=4
 >
 > :)
Имеем 
a<b<c<e, b<d<e, пары (a,d), (c,d) несравнимы
Считаем, что при сравнении (a и d) и (с и d) они равны. 
Первоначальный массив :
{d,e,b,a,c}

т.к.
d<e; e>b
{d,b,e,a,c}

т.к.
e>a
{d,b,a,e,c}

т.к.
e<c
{d,b,a,c,e}

{b,d,a,c,e}
т.к. d=a не переставляем
{b,d,a,c,e}
Приплыли :)

Переставим "равные" - несравнимые элементы a и d
{b,a,d,c,e}
{a,b,d,c,e} - нормально :)

Наверное несравнимые элементы при сортировке всё-же лучше всегда 
переставлять, что-бы не было тупиков типа {b,a,d,c,e}
-- 
С уважением Xихин Руслан

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

Re: [devel] [JT] std::sort

[Hihin Ruslan]

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

Здравствуйте Alex V. Myltsev
  В сообщении от Sunday 17 December 2006 23:18 Alex V. Myltsev 
написал(a):
 > On Sun, 17 Dec 2006 22:42:52 +0300 Hihin Ruslan wrote:
 > >  > подают нам на вход последовательность {a,c,d,b,e}; она
 > >  > неупорядочена, а   сравнением соседних элементов мы этого
 > >  > обнаружить не можем. И  сортировка вся идёт лесом.
  > > Как это не парадоксально,  но если читать что несравнимость - это
  > > один из видов равенства, то можно упорядочить в - вашем примере
  > Конечно, можно. Это же частичный порядок, никто не мешает его
  > доопределить %-).
 >
 > > В общем имеем ситуацию сортировки элементов графа
  > Угу. И что-то подсказывает мне, что это дольше, чем сортировка
  > множества с полным порядком
 Упрощённо имеем :
Множество пакетов A(a1),B(a2),C(a3)...N(an), 
A1(b1),B1(b2),...N1(bn), ......Z1(z1),Z2(z2),...ZN(zn), 
где a...z - характеристика ветки, 
     1..n -  вес пакета в ветке
     A...ZN - имя пакета:
Имеются следующие отношения между пакетами 
Наследования A<B, если характеристика ветки у них совпадает и вес пакета 
в ветке у пакета A < веса пакета в ветке у пакета B 
A=B - пакеты не соизмеримы (характеристика веток не совпадает).

Каждый пакет A несёт в себе информацию о пакетах от которых он зависит, 
т.е. если пакет A имеет характеристику веток A(a4,b3,...zn), то он 
несёт в себе перечень пакетов (имена B,C...N) с характеристиками веток 
a3,b2,..z(n-1)

Имеем неупорядоченное множество пакетов {A,....Z}
Выбираем первый пакет (A) и определяем пакты - родители пакета A,
пусть это будут RA1, RA2 .. RAN, пере-упорядочиваем множество :
{RA1, RA2.. RAN, A,..... Z}, теперь выбираем элемент множества RA1 и 
ставим перед ним всех его родителей и т.д. в результате вытягиваем всех 
предков пакета A. Аналогично разбираемся с пакетами B и т.д. Если 
оказывается, что пакет F, имеет родителем уже рассмотренный пакет. 
например RB3, то он ставится после пакета RB3, а все родители пакета F 
находящиеся пока справа от него, перемещаются налево от него и по ним 
тоже происходит сортировка, после чего сортировка возвращается к 
элементу, следовавшему за F (пусть будет E).
   
  > , которая чаще всего нужна на практике.
 Правильнее сказать - её алгоритм проще, а вот насчёт того, что 
сортировка графов дольше - это неверно, наоборот сортировка множества 
дольше, т.к. в нём не учитывается, что в самих пакетах уже есть 
информация о пакетах - родителях и приходится путём перебора 
их "отсеивать".
  > Поэтому и появилось в STL упомянутое требование. (А те, кому
  > действительно нужно сортировать графы, могут написать собственный
  > sort.)
Вообще-то есть tsort, правда я не разбирался как он работает, но в RPM 
он есть, во всяком случае в исходниках RPM лежит программка rpmsort 
(опять-же подробно не смотрел её код). Насколько я знаю алгоритм 
сортировки графов подробно рассмотрен в одном из томов Кнут (в юности 
читал, но сам том с сортировкой у меня не сохранился).

http://homepages.compuserve.de/chasluebeck/lipsky2.htm
http://algolist.manual.ru/sort/

 > (Мне кажется, продолжать тему в этом направлении можно только в
 > smoke-room.)
Ну извините, я заканчиваю на этом :)

-- 
С уважением Xихин Руслан

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

Re: [devel] [PATCH] apt virtual packages

[Led]

В сообщении от 17 декабря 2006 18:09 Alexey Tourbin написал(a):
> On Sun, Dec 17, 2006 at 05:14:14PM +0300, Alexey Tourbin wrote:
> > On Sun, Dec 17, 2006 at 04:43:40PM +0300, Alexey Tourbin wrote:
> > > +static inline bool
> > > +vercmpOrder(const pkgCache::VerIterator &a, const
> > > pkgCache::VerIterator &b) +{
> > > +   return a.CompareVer(b) < 0;
> > > +}
> >
> > Кстати вот тут должно быть "<" или "<="?
> > Что-то у Страуса примера на сортировку с предикатом порядка нету.
>
> Ага, тут похоже должно быть "<=".  Дело в том, что всего одной операции
> "<=" достаточно, чтобы логически вывести все остальные операции сравнения.
>
> (==)(a,b) := (a<=b)&&(b<=a)
> (>=)(a,b) := !(b<=a)
> (!=)(a,b) := !(a==b)
> (<)(a,b)  := (a<=b)&&(a!=b)
> (>)(a,b)  := (a>=b)&&(a!=b)
>
> А в случае с одной только операцией "<" такой ляпоты не получается,
> потому что не удается логически вывести равенство.

(==)(a,b) := !(a<b)&&!(b<a)

?

-- 
Led.

Re: [devel] [PATCH] apt virtual packages

[Alexey Tourbin]

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

On Mon, Dec 18, 2006 at 12:39:28PM +0200, Led wrote:
> > А в случае с одной только операцией "<" такой ляпоты не получается,
> > потому что не удается логически вывести равенство.
> 
> (==)(a,b) := !(a<b)&&!(b<a)
> 
> ?

Да.  Я уже исправился и предложил вариант
(a==b) := !((a<b)||(b<a))

который по закону Де Моргана или как его там эквиваленен вашему.

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

Re: [devel] [PATCH] apt virtual packages

[Alexey Tourbin]

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

On Sun, Dec 17, 2006 at 04:43:40PM +0300, Alexey Tourbin wrote:
> Этот патч был неправильным, потому что версии в ProvidesList на самом
> деле не отсортированы.  Вот правильный вариант патча (прицеплен).

В принципе этот патч почти хороший.  То есть его можно брать в очередную
сборку.

Есть другая идея.  В TryToChangeVer можно теперь вызывать не Find(),
который вернет наилучшую версию, а новый FindAll(), и применять к нему
технику &(Fix.ScoreSort).

Ну в общем это техника не совсем родная для апта, она содержится
в apt-0.5.15cnc6-alt-virtual-scores.patch.  Что-то я уже не понимаю что
у апта родное а что кто-то из нас добавил года три назад.

В общем смысл в чем.  Сейчас как происходит: когда просим ставить пакет
без версии, тогда вызывается Fix.ScoreSort.  А когда просим ставить
пакет с версией, тогда уже никакого ScoreSort нет.  Простейший вариант --
при попытке ставить виртуальный или реальный пакет с версией ставить
всегда реальный пакет с наибольшей реальной версией, удовлетворяющей
зависимость по требуемой версиеи.  Это то что сделано в [PATCH].  Второй
вариант -- ввести ScoreSort в TryToChangeVer.

В общем-то по идее НЕ надо делать различия между виртуальными и
реальными пакетам.  Одна и та же зависимость может разрешаться в N
реальных пактов и M виртуальных пакетов.  Тогда что делать?

Я тут думал о теории графов но на самом деле графа-то как такового нет.
Если нельзя однозначно сконструировать матрицу инциденций тогда это уже
не граф.

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