Package: apt
Version: 0.9.7.7
Severity: serious
Hi,
there is a problem in apt's score computation (algorithms.cc,
MakeScores()) w.r.t. to the negative scores for "optional" and "extra"
packages. Adding abs(negative score) to some package may give in
incorrect boost to that package.
Setting severity to serious as this should be fixed (and this seems possible
in a rather non-intrusive way) for wheezy, so that the fix will be
available for the wheezy->jessie upgrades in the future.
Note that I rebuilt (and slightly patched (to output non-boring packages
with score 0)) apt/sid for squeeze to have the "new" apt perform the
distupgrade from squeeze to wheezy - to see whether this works better
than squeeze's old apt - and to find problems still existing.
I consider any "kept back" during a distupgrade from any valid subset of
squeeze packages to wheezy as a "problem". Or an attempt to remove the
package to be tested if that still exists and is installable in wheezy.
I have a local piuparts instance running for this setup, so I could
easily check the effect of a fix on a large portion of the archive by
testing it on squeeze->wheezy upgrades.
One of the first problems I noticed was apt preferring to keep back
libhangul-dev instead of kicking out libhangul0, libhangul0-data and
installing libhangul1, libhangul-data.
Setup is a minimal squeeze system with no recommends and libhangul-dev
installed, there 'apt-get dist-upgrade' to wheezy is being run.
>From the attached log:
2 liblzma2 [ amd64 ] < 5.0.0-2 > ( libs )
1 uuid-runtime [ amd64 ] < none -> 2.20.1-5.3 > ( libs )
1 libldap-2.4-2 [ amd64 ] < none -> 2.4.31-1 > ( libs )
1 bsdmainutils [ amd64 ] < none -> 9.0.3 > ( utils )
1 psmisc [ amd64 ] < none -> 22.19-1+deb7u1 > ( admin )
1 apt-utils [ amd64 ] < none -> 0.9.7.7 > ( admin )
1 awk [ amd64 ] < none > ( none )
* 1 libhangul0-data [ amd64 ] < 0.0.11-2 > ( libs )
1 libgpm2 [ amd64 ] < none -> 1.20.4-6 > ( libs )
1 libpng12-0 [ amd64 ] < none -> 1.2.49-1 > ( libs )
1 bash-completion [ amd64 ] < none -> 1:2.0-1 > ( shells )
1 libdb4.8 [ amd64 ] < 4.8.30-2 > ( libs )
1 gnupg-curl [ amd64 ] < none -> 1.4.12-7 > ( utils )
* 0 libhangul-data [ amd64 ] < none -> 0.1.0-2 > ( libs )
0 gcc-4.4-base [ amd64 ] < 4.4.5-8 -> 4.4.7-2 > ( libs )
0 libsemanage-common [ amd64 ] < none -> 2.1.6-6 > ( libs )
* 0 libhangul-dev [ amd64 ] < 0.0.11-2 -> 0.1.0-2 > ( libdevel )
0 libustr-1.0-1 [ amd64 ] < none -> 1.0.4-3 > ( libs )
* 0 libhangul1 [ amd64 ] < none -> 0.1.0-2 > ( libs )
* -1 libhangul0 [ amd64 ] < 0.0.11-2 > ( libs )
Starting 2
Investigating (0) libhangul-data [ amd64 ] < none -> 0.1.0-2 > ( libs )
Broken libhangul-data:amd64 Conflicts on libhangul0-data [ amd64 ] < 0.0.11-2 > ( libs )
Considering libhangul0-data:amd64 1 as a solution to libhangul-data:amd64 0
Holding Back libhangul-data:amd64 rather than change libhangul0-data:amd64
Investigating (0) libhangul1 [ amd64 ] < none -> 0.1.0-2 > ( libs )
Broken libhangul1:amd64 Depends on libhangul-data [ amd64 ] < none -> 0.1.0-2 > ( libs ) (>= 0.1.0-2)
Considering libhangul-data:amd64 0 as a solution to libhangul1:amd64 0
Holding Back libhangul1:amd64 rather than change libhangul-data:amd64
Investigating (1) libhangul-dev [ amd64 ] < 0.0.11-2 -> 0.1.0-2 > ( libdevel )
Broken libhangul-dev:amd64 Depends on libhangul1 [ amd64 ] < none -> 0.1.0-2 > ( libs ) (= 0.1.0-2)
Considering libhangul1:amd64 0 as a solution to libhangul-dev:amd64 0
Holding Back libhangul-dev:amd64 rather than change libhangul1:amd64
Try to Re-Instate (2) libhangul-dev:amd64
Done
The following NEW packages will be installed:
gcc-4.7-base libdb5.1 liblzma5 libmount1 libpam-modules-bin
libsemanage-common libsemanage1 libtinfo5 libustr-1.0-1 multiarch-support
The following packages have been kept back:
libhangul-dev
The following packages will be upgraded:
The dependency chains are:
squeeze: libhangul-dev -> libhangul0 -> libhangul0-data
wheezy: libhangul-dev -> libhangul1 -> libhangul-data
Let me try to compute the scores manually after reading algorithms.cc
MakeScores():
First round (initialization):
libhangul-dev => 0
-1 optional
1 installed and not obsolete
libhangul0 => -1
-1 optional
0 installed but obsolete
libhangul0-data => 0
-1 optional
0 installed but obsolete
1 rdepends (libhangul0)
libhangul1 => 0
-1 optional
0 not installed
1 rdepends (libhangul-dev)
libhangul-data => 0
-1 optional
0 not installed
1 rdepends (libhangul1)
Second round (one level propagation):
libhangul-dev => 0
0 round 1
0 no rdepends
libhangul0 => -1
-1 round 1
0 no rdepends
libhangul0-data => 1
0 round 1
1 libhangul0: abs(-1)
libhangul1 => 0
0 round 1
0 libhangul-dev
libhangul-data => 0
0 round 1
0 libhangul1
Oops, now libhangul0-data (1) is more valuable than libhangul-data (0)
The flaw is here:
Scores[I->ID] += abs(OldScores[D.ParentPkg()->ID]);
as "optional" leaf packages will have a score of -1 - and even worse,
"extra" leaf packages will have a score of -2. Running abs() on this
gives a boost to the wrong packages.
Suggestions for alternative propagation functions:
// current and wrong
Score += abs(RDepScore)
// ignore negatives, they already contributed
// PrioDepends/PrioRecommends to our score
Score += max(0, RDepScore)
// ignore negatives, but give another point for the rdep
Score += max(1, RDepScore)
// give a point for all rdeps, not only the low scoring ones
Score += 1 + max(0, RDepScore)
maybe replace 1 with PrioDepends/PrioRecommends as fitting
Another possibility would be to add 3 to all scores to move them out of
the negative area. (That would also distinguish scores initilized to 0
(i.e. boring packages) and scored that added up to 0 (i.e. interesting
packages) because that can no longer happen).
As I said above, I'd like to test your preferred choice :-)
Andreas
PS: The next interesting point to analyze are the problems with the
libjpeg-dev transition (a virtual package that moved from libjpeg62-dev
to libjpeg8-dev) that is currently solved miserably by apt/squeeze -
usually preferring to keep libjpeg62-dev/squeeze instead of installing
libjpeg8-dev/wheezy. So far I only have 12000 of of 28000 packages
tested and the libjpeg-dev dependencies seem to come later ... and that
problem could be related to the current one.
Attachment:
hangul.log.gz
Description: GNU Zip compressed data