On year ago, we (the mancoosi team) published a comparison study regarding the state of the art of dependency solving in debian. As few noticed, the data presented had few glitches that I promised to fix. So we’ve repeated our tests using exactly the same data we used one year ago, but now using the latest available versions of all package managers as available in debian unstable.

During the last year, three out of four solver that we evaluated release a major upgrade so I expected many improvements in performances and accuracy.

• apt-get 0.8.10 -> 0.9.7
• aptitude 0.6.3 -> 0.6.7
• smart 1.3-1 -> 1.4
• cupt 1.5.14.1 -> 2.5.6

Mpm, our test-bench for new technologies, changed quite a bit under the wood as a consequence of the evolution of apt-cudf and the recent work done in apt-get to integrate external cudf dependency solvers.

Overall the results of our study are not changed. All solvers but mpm, that is based on aspcud, are not scalable as the number of packages (and alternatives) grows. It seems that Smart is the solver that does not give up, incurring in a timeout (fixed at 60 seconds) most of the time. Aptitude is the solver that tried to give you a solution, doesn’t matter what and as result providing solutions that do not satisfy the user request for one reason or the other. Apt-get does surprisingly well, but it gives up pretty often showing the incomplete nature of it’s internal solver. Cupt sometimes timeout, sometimes gives up, but when it is able to provide an answer it is usually optimal and it is very fast … Mpm consistently finds an optimal solution, but sometimes it takes really a long time to do it. Since mpm is written in python and not optimized for speed this is not a big problem for us. The technology used by mpm is now integrated in apt-get and I hope this will alleviate this problem.

All the details of our study can be found one the Mancoosi Website as usual with a lot of details. For example here you can find the results when mixing four major releases : sarge-etch-lenny-squeeze.

Comments are more then welcome.

apt-get and aptitide were two missing competitors of the misc competition. However it is important and interesting how these two tools compete against other solvers submitted to MISC. In this post I want to present two simple tools to convert cudf documents to something that apt-get based tools can handle. Cudf and debian share many characteristics but also have important semantic differences. One important difference is about installing multiple versions of the same package. Since this is allowed in cudf, but not in debian, we can use apt-get and aptitude only to solver cudf problems that respect this constraint, ruling out, for example, all cudfs from the rpm world. Another difference to take care is about the request semantic. In cudf, request can contain version constraints. For example, one can ask to upgrade the package wheel to a version greater then 2. Since it is not possible to translate directly this request in cudf we are forced to add a dummy package encoding the disjunction of all packages that respect this constraint. This problem does not arise with remove request as the refer always to the currently installed package.

Apt-get needs two files : The Packages file that contains the list of all packages known to the meta-installer and the status file that contains the list of packages that must result currently installed. To generate these files I wrote a small utility using the dose3 framework imaginatively called cudftodeb . This tool gets a cudf and produces three files : Packages, status and Request with the Request file containing the list of files to install or remove in a syntax compatible with apt-get .

In other to run apt-get/aptitude with these files, you would need a simple bash script. You can find details here for apt-get and here for aptitude. Most important option is the -s used to simulate an installation.

With the -v option of apt-get we can generate a parsable solution. This output is the piped through an other tool called aptgetsolutions in order to produce a cudf solution closing the circle.

For example, this is the trace produced by aptitude when trying to solve the legacy.cudf problem :

Reading package lists...
Building dependency tree...
Reading extended state information...
Initializing package states...
Reading task descriptions...
The following NEW packages will be installed:
  bicycle dummy_wheel electric-engine{b} glass{a} window{a}
The following packages will be upgraded:
  door wheel
2 packages upgraded, 5 newly installed, 0 to remove and 1 not upgraded.
Need to get 0B of archives. After unpacking 0B will be used.
The following packages have unmet dependencies:
  gasoline-engine: Conflicts: engine which is a virtual package.
  electric-engine: Conflicts: engine which is a virtual package.
The following actions will resolve these dependencies:

     Remove the following packages:
1)     gasoline-engine

The following NEW packages will be installed:
  bicycle dummy_wheel electric-engine glass{a} window{a}
The following packages will be REMOVED:
  gasoline-engine{a}
The following packages will be upgraded:
  door wheel
2 packages upgraded, 5 newly installed, 1 to remove and 0 not upgraded.
Need to get 0B of archives. After unpacking 0B will be used.
WARNING: untrusted versions of the following packages will be installed!

Untrusted packages could compromise your system's security.
You should only proceed with the installation if you are certain that
this is what you want to do.

  wheel bicycle dummy_wheel door glass electric-engine window

*** WARNING ***   Ignoring these trust violations because
                  aptitude::CmdLine::Ignore-Trust-Violations is 'true'!
Remv gasoline-engine [1] [car ]
Inst bicycle (7 localhost) [car ]
Inst glass (2 localhost) [car ]
Inst window (3 localhost) [car ]
Inst door [1] (2 localhost) [car ]
Inst wheel [2] (3 localhost) [car ]
Inst dummy_wheel (1 localhost) [car ]
Inst electric-engine (1 localhost)
Conf bicycle (7 localhost)
Conf glass (2 localhost)
Conf window (3 localhost)
Conf door (2 localhost)
Conf wheel (3 localhost)
Conf dummy_wheel (1 localhost)
Conf electric-engine (1 localhost)

Not the package dummy_wheel used to encode the upgrade request of wheel>>2. This dummy package encodes the request as a dependency :

Package: dummy_wheel
Version: 1
Architecture: i386
Depends: wheel (= 3)
Filename: /var/fakedummy_wheel1

One last remark about apt-get. I just run on this bug today using an old version of apt-get that is shipped with lenny. For our experiments we are using only the latest version of apt-get in debian testing.

In the same spirit of this blog post http://chistera.yi.org/~adeodato/blog/106_fakeapt.html , this is a simple bash function to simulate an aptitude run on a given status and packages list. We assume yes for all question so to make aptitude not interactive and we assume the flag -f in order to alway try to fix broken universe before trying to satisfy the request.

fakeaptitude() {
    aptitude -s \
        -o APT::Get::List-Cleanup="false" \
        -o Dir::Cache=$aptroot \
        -o Dir::State=$aptroot \
        -o Dir::State::status=$aptroot/status \
        -o Dir::Etc::SourceList=$aptroot/sources.list \
        -o APT::Architecture=amd64 \
        -o Aptitude::CmdLine::Fix-Broken="true" \
        -o Aptitude::CmdLine::Assume-Yes="true" \
        $@
}

initapt() {
  list=$1
  mkdir -p $aptroot/{archives,lists}/partial
  cp status.$list $aptroot/status
  if [ ! -f $list.packages.gz ]; then
    gzip $list.packages
  fi
  cp $list.packages.gz $aptroot/lists/Packages.gz
cat<<EOF > $aptroot/sources.list
deb file:$aptroot/lists/ ./
EOF
fakeaptitude update
}