My Opinions

The not so easy path to installing a new package

A couple of days ago, I wanted to visualize the space occupied by the files on my hard disk, that has grown too much lately, and for this I was ready to give a try to a tool named Baobab, that looked appealing. Being a Debian guy, I am used to finding a package with the same name... so I looked for it

$apt-cache search baobab
baobab - graphical tool to analyse disk usage
gnome-utils - GNOME desktop utilities

Cool, the package is there, let's get it!

A first try using Apt

As I am a command-line addict, here is what I tried:

$apt-get -s install baobab

Reading package lists... Done 
Building dependency tree
Reading state information... Done
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:
  gnome-settings-daemon: Breaks: gnome-screensaver (< 2.28.0) but 2.26.1-1 is to be installed
E: Broken packages

Well, this is not really helpful, as I do not have the slightest idea, looking at the error message, of what can be going wrong.

A second try using Aptitude

So I decided to use another package manager, aptitude, to see whether I would be more lucky:

$aptitude -s install baobab
Reading package lists... Done
Building dependency tree
Reading state information... Done
Reading extended state information
Initializing package states... Done
Reading task descriptions... Done
The following packages are BROKEN:
  gnome-utils
The following NEW packages will be installed:
  baobab
0 packages upgraded, 1 newly installed, 0 to remove and 2258 not upgraded.
Need to get 107kB of archives. After unpacking 446kB will be used.
The following packages have unmet dependencies:
  gnome-utils: Conflicts: baobab but 2.4.2-1.1+b1 is to be installed.
The following actions will resolve these dependencies:

Remove the following packages:
gnome
gnome-desktop-environment
libgdict-1.0-6

Install the following packages:
libgnome-desktop-2 [2.22.3-2 (stable)]

Downgrade the following packages:
gnome-utils [2.26.0-1 (now) -> 2.14.0.dfsg-5 (oldstable)]

Score is -142

Accept this solution? [Y/n/q/?]

Hey, that seems better: aptitude seems to have found a way to get baobab on my machine! Looking at the messages, though, I am a bit concerned at first: aptitude wants to remove gnome and gnome-desktop-environment, which I would like not to loose, but a quick inspection of the metadata for these two packages tells me that they are just meta packages, created to bring in all the functionality of Gnome:

Package: gnome
Priority: optional
Section: gnome
Installed-Size: 56
Maintainer: Debian GNOME Maintainers <pkg-gnome-maintainers@lists.alioth.debian.org>
Architecture: i386
Source: meta-gnome2
Version: 1:2.28+7
Depends: gnome-desktop-environment (= 1:2.28+7), gdm-themes | gdm3, gnome-themes-extras,
               gnome-games (>= 1:2.28), libpam-gnome-keyring (>= 2.28), gstreamer0.10-plugins-ugly (>= 0.10.12),
               gstreamer0.10-ffmpeg (>= 0.10.9), rhythmbox-plugins (>= 0.12.5) | banshee (>= 1.5),
               rhythmbox-plugin-cdrecorder (>= 0.12.5) | banshee (>= 1.5), synaptic (>= 0.62),
               system-config-printer (>= 1.0.0), totem-mozilla, epiphany-extensions, gedit-plugins,
               evolution-plugins (>= 2.28), evolution-exchange (>= 2.28) | evolution-mapi (>= 0.28),
               evolution-webcal (>= 2.28), software-center, gnome-codec-install, transmission-gtk,
               arj, avahi-daemon, tomboy (>= 1.0) | gnote
Recommends: gnome-games-extra-data (>= 2.28), network-manager-gnome (>= 0.7), gnome-office (= 1:2.28+7),
               update-notifier, remmina, hal-cups-utils, gthumb, liferea | evolution-rss | blam, menu-xdg,
               gdebi, mozilla-plugin-gnash
Suggests: gnome-dbg, openoffice.org-gnome, openoffice.org-evolution
Conflicts: gnome-cups-manager
Filename: pool/main/m/meta-gnome2/gnome_2.28+7_i386.deb
Size: 17416
MD5sum: f69994ad9e30f054ad6ae37d88079dad
SHA1: 0d40a7532761ce696157cc6956fd03318b6ad2c9
SHA256: bd7a947dfa79deb751d635b73cf5feaeebbf2ca074af5f8d50a1747cd60dacab
Description: The GNOME Desktop Environment, with extra components
 This is the GNOME Desktop environment, an intuitive and attractive
 desktop, with extra components.
 .
 This package depends on the standard distribution of the GNOME desktop
 environment, plus a complete range of plugins and other applications
 integrating with GNOME and Debian, providing the best possible
 environment to date.
Tag: interface::x11, role::metapackage, special::meta, suite::gnome, uitoolkit::gtk, use::gameplaying
Task: gnome-desktop

It seems that removing these meta-packages will not lead to any loss of real functionality, so I decide to go ahead, and let aptitude do its magic:

Accept this solution? [Y/n/q/?] Y
The following packages will be DOWNGRADED:
  gnome-utils
The following NEW packages will be installed:
  baobab libgnome-desktop-2{a}
The following packages will be REMOVED:
  abiword{u} abiword-common{u} abiword-help{u} abiword-plugin-goffice{u} abiword-plugin-grammar{u}
  abiword-plugin-mathview{u} arj{u} at-spi{u} bluez-gnome{u} brasero-common{u} cheese{u} clive{u} clive-utils{u}
  dasher{u} dasher-data{u} dmz-cursor-theme{u} ekiga{u} empathy{u} eog{u} epiphany-extensions-more{u} espeak{u}
  espeak-data{u} evolution-exchange{u} fast-user-switch-applet{u} file-roller{u} gcalctool{u}
  gconf-defaults-service{u} gconf-editor{u} gdm{u} gdm-themes{u} gedit{u} gedit-common{u} gedit-plugins{u}
  ggzcore-bin{u} gnome{a} gnome-accessibility{u} gnome-accessibility-themes{u} gnome-app-install{u}
  gnome-backgrounds{u} gnome-cards-data{u} gnome-core{u} gnome-desktop-environment{a} gnome-games{u}
  gnome-games-data{u} gnome-games-extra-data{u} gnome-mag{u} gnome-nettool{u} gnome-office{u} gnome-orca{u}
  gnome-power-manager{u} gnome-screensaver{u} gnome-system-tools{u} gnome-themes{u} gnome-themes-extras{u}
  gnome-themes-more{u} gnome-vfs-obexftp{u} gnome-volume-manager{u} gnuchess{u} gnuchess-book{u} gnumeric{u}
  gnumeric-common{u} gok{u} gstreamer0.10-nice{u} gstreamer0.10-tools{u} gtk2-engines{u} gtk2-engines-pixbuf{u}
  gtk2-engines-smooth{u} gucharmap{u} gvfs-bin{u} hamster-applet{u} latex-xft-fonts{u} libaiksaurus-1.2-0c2a{u}
  libaiksaurus-1.2-data{u} libaiksaurusgtk-1.2-0c2a{u} libalut0{u} libart2.0-cil{u} libatspi1.0-0{u} libavahi-ui0{u}
  libberkeleydb-perl{u} libbrasero-media0{u} libcolorblind0{u} libconfig-tiny-perl{u} libcrypt-passwdmd5-perl{u}
  libcrypt-twofish-perl{u} libcryptui0{u} libdmx1{u} libempathy-common{u} libempathy-gtk-common{u}
  libempathy-gtk19{u} libempathy23{u} libespeak1{u} libexpect-perl{u} libgail-gnome-module{u} libgconf2.0-cil{u}
  libgdict-1.0-6{a} libgdl-1-0{u} libgdl-1-common{u} libgdome2-0{u} libgdome2-cpp-smart0c2a{u}
  libgetopt-argvfile-perl{u} libggz2{u} libggzcore9{u} libggzmod4{u} libglade2.0-cil{u} libgmime-2.0-2a{u}
  libgmime2.2a-cil{u} libgnome-mag2{u} libgnome-speech7{u} libgnome-vfs2.0-cil{u} libgnome2.24-cil{u}
  libgnomepanel2.24-cil{u} libgoffice-0-8{u} libgoffice-0-8-common{u} libgpod-common{u} libgpod4{u}
  libgstfarsight0.10-0{u} libgtk-vnc-1.0-0{u} libgtk2.0-cil{u} libgtkhtml2-0{u} libgtkmathview0c2a{u}
  libgtksourceview2.0-0{u} libgtksourceview2.0-common{u} libhtml-strip-perl{u} libio-stty-perl{u} liblink-grammar4{u}
  libloudmouth1-0{u} libmissioncontrol-client0{u} libmissioncontrol-server1{u} libmono-addins-gui0.2-cil{u}
  libmono-addins0.2-cil{u} libmono-cairo2.0-cil{u} libndesk-dbus-glib1.0-cil{u} libndesk-dbus1.0-cil{u} libnice0{u}
  libopal3.6.1{u} libots0{u} libpt2.6.1{u} libpt2.6.1-plugins-alsa{u} libpt2.6.1-plugins-v4l2{u} libsgutils1{u}
  libtelepathy-farsight0{u} libtelepathy-glib0{u} libtelepathy2{u} libuniversal-require-perl{u} libwww-curl-perl{u}
  libxml-rss-libxml-perl{u} link-grammar-dictionaries-en{u} mousetweaks{u} perl-tk{u} planner{u} python-4suite-doc{u}
  python-4suite-xml{u} python-brlapi{u} python-eggtrayicon{u} python-gdl{u} python-gksu2{u} python-gnome2-extras{u}
  python-gtkhtml2{u} python-gtkmozembed{u} python-gtksourceview2{u} python-pyatspi{u} python-sexy{u} python-vte{u}
  rhythmbox{u} rss-glx{u} seahorse{u} seahorse-plugins{u} serpentine{u} sg3-utils{u} sound-juicer{u} swfdec-gnome{u}
  telepathy-gabble{u} telepathy-mission-control{u} telepathy-salut{u} tomboy{u} totem{u} transmission-common{u}
  transmission-gtk{u} vinagre{u} vino{u}
0 packages upgraded, 2 newly installed, 1 downgraded, 180 to remove and 2125 not upgraded.
Need to get 2442kB of archives. After unpacking 536MB will be freed.
Do you want to continue? [Y/n/?]

Excuse me? 180 to remove? This is not what I was promised!

As you can imagine, faced with such a situation, any reasonable person will abort the operation, and start some more serious investigation to find out what is going on.

Analysis of the causes of a potential disaster

Had I accepted the solution proposed by aptitude, I would have completely lost all the gnome environment functionality: I think we all agree this should be considered as a 'real 'disaster'', so it is important to understand where it comes from.

There are sereveral fundamental issues.

Quality of the upgrade paths proposed by the package managers

Since the old days of the EDOS Project, we know that even the apparently simple problem of knowing whether a single package is installable from scratch is NP-Complete.

To make things worse, when an installation request is satisfiable, there might be exponentially many different ways to satisfy it: just think of what happens if you have many independent packages available, any solution might decide to include or exclude each of these packages, which leads to a huge solution space.

This means that either we are allowed to explain to the tools what kind of solution we want, or the tool needs to incorporate some default strategy to choose a solution for us.

No package manager I am aware of allows the user to easily specify a general criterion to pick a solution suited for her needs. They all incorporate some kind of default strategy to choose a solution for us, and this might lead to very surprising results: there is a survey of package mangers performed a few years ago which is quite informative, and scary, I would say. You will see in that survey that a lot of choices are made for you by the package managers: apt-get and aptitude, for example, try their best to bring in the latest version of every package they encounter while looking locally for a solution, and this might lead to huge upgrades even when you try to install an apparently minor software component.

Even more unfortunately, apparently package manager developers have all in mind use cases different from mine: I did not find a single package manager that implements a strategy thac could be resumed as hey, I am giving a presentation in a couple of hours: I need to install this little new nifty program, but please find a way to leave alone all the rest of my machine, I do not want any surprise now.

So the lesson learned here is that the task of a modern package manager is really complex: apart from all the usual package management tasks, it is supposed to find a solution for an NP-complete problem, and possibly one that is optimal with respect to a sensible optimization criterion. As we have seen in the example above, apt is not able to find a solution for one particular problem that admits a solution (so its solver is incomplete), while aptitude offers a solution which is not acceptable.

In the Mancoosi project, we believe that the only sensible way to cope with this complex issues is to apply the old separation of concerns recipe:

1. Decouple the solver from the package manager. A package manager should not implement a new, specialised solving algorithm: getting right a complete algorithm for NP-complete problems is not easy, while there is a full research community sharing knowledge in this area, and developing state-of-the art solvers: as the old adage goes, good programmers write good code; great programmers steal great code. In Mancoosi, we have proposed CUDF as a common format to represent upgrade problems, that can be used as an interface between package managers and external solvers. If you are a package manager developer or maintainer, please consider using CUDF as an interface to external solvers, and get in touch with us.
2. Make the optimization criterion explicit, and user configurable. When dealing with a complex optimization problem, one cannot assume to always know better than the user what the user wants: in the above case, removing 180 packages to install a single new component is not acceptable for many of us, and we should be allowed to say this explicitly. In the Mancoosi project, we are working on MooML, a generic, flexible language able to capture most optimization functions, and yet reasonably close to what modern solvers are able to handle.
3. Listen to the users. We should make easy for users to tell us when and why they are unhappy with the solutions found (or missed) by current package managers, and we should collect that information in a systematic way, to be able to analyse it and build on it. In Mancoosi we have setup an infrastructure to do so for the Caixa Magica, Mandriva and Debian distribution. If you are a user of any of these distributions, please consider submitting your reports using the tools and approaches described in the links above. For example, the traces of the two aborted installation detailed in this post are stored online here and herein the Mancoosi DUDF repository for Debian. If you are a distribution editor, please consider setting up a similar infrastructure, and get in touch with us.
4. Foster collaboration with researchers. Building on (or stealing) existing state-of-the-art solvers might seem a good-enough strategy, but it is too short sighted. The best people to improve and adapt existing solvers to the kind of problems we face when installing packages are the smart research guys that wrote the solvers, and we need to bring them in! In Mancoosi, we are running an International Solver Competition where we offer problems collected from the users of various GNU/Linux distribution, and we challenge them to find optimal solutions according to different optimization criteria. If you are a researcher working on optimization and problem solving, please consider participating in the Mancoosi International Solver Competition .

Currently, we have played with a couple of predefined optimization criteria : the paranoid one, that basically says "install that package, but leave the rest alone"; and the "trendy" one, that basically says "go ahead, bring in all the cool newest stuff you find, as far as you do not bring in too many packages that I did not have yet, unless to satisfy the Recommends dependencies".

Using one of the state of the art solver with the paranoid citerion on the CUDF document produced on my machine from the above example leads to finding this solution:

Remove: gnome-utils gnome-desktop-environment gnome
Install: baobab=2.4.2-1.1+b1

And I also know that this solution is the best I can get: the solver used is complete for the paranoid optimization function!

If you are curious to know, this solution has been found in less than 3 minutes, using a highly non-optimised pipeline built with the different Mancoosi components developed to enable the solver competition (our goal was not to write yet another package manager), but the actual time spent by the solver on this particular instance is less than 20 seconds (the rest is due to the inefficient structure of the pipeline).

And yes, it might be the case that in the near future you will get from us a polished version of this pipeline as an emergency tool to help you find your way out when you are caught in one of the many pitfalls of the current package manager.

Autoremove is subject to serious pitfalls in the presence of 'meta' packages.

Looking better into the reasons why aptitude wants to destroy my gnome desktop, and leave me with an old fashioned command-line interface, one can find a bad consequence of an apparently good idea: autoremove.

The autoremove feature has been introduced a while ago to help users get rid of packages that are not needed any more: the idea is that when the package manager removes a package that is on the machine because it was requested by the user, it will also remove all of its dependencies which are no longer needed for any other package requested by the user; such packages are also called orphans, and the autoremove feature has be considered so helpful that it is now the default behavior in recent versions of aptitude.

Unfortunately, there are cases when autoremove is not such a good idea: to understand the problem, let's summarize what autoremove does (please forgive the necessary approximation), considering again our example above.

1. At some point in time, the user (me), asks to install the gnome package. As we have seen above, this is a meta-package intended to bring into my machine all the components of the Gnome desktop, sparing me the tedious work of digging out the 100+ packages that compose it.
2. Aptitude (and now apt-get too) mark Gnome as a package that has been explicitly requested from the user, and all the other components of Gnome are marked as 'automatic' dependencies (i.e. packages not explicitly requested by the user, but installed to satisfy a user request)
3. When I request the installation of baobab, the solver in aptitude sees that the installed version of gnome-utils is in conflict with baobab, so decides to downgrade it, but doing so breaks libgdict-1.0.6, which leads to the removal of gnome-desktop-environment and gnome (so far, so good)
4. Applying the autoremove policy, when removing the gnome package, that I had explicitly requested, aptitude decides to get rid of all the orphans of gnome, which are the 100+ packages composing the gnome desktop!

It is clear that autoremove interacts badly with meta-packages: metapackages are just a convenient way to bring in a collection of related packages, and a user will be quite confortable to live with a broken metapackage if this is necessary to accommodate versions of some components which are not aligned with that particular metapackage.

Orphaning all dependencies of a metapackage, and removing all of them, as soon as one of the hundreds of these dependencies is broken, is not reasonable: it leads to surprising behaviour!

The user should be at least asked whether they want to perform autoremove or not, like what apt-get does. In the current situation, I did not find a way to tell aptitude on the command line not to apply the autoremove policy.

We did not need to do anything in the first place, and the system should have told me!

Digging into this issue a bit more deeper, I found out that I did not need to install the baobab package at all! Sometimes ago the baobab functionality has been merged into the gnome-utils package, and it was just enough to launch the program:

$which baobab
/usr/bin/baobab
$dpkg -S /usr/bin/baobab
gnome-utils: /usr/bin/baobab

Could the system have told me in the first place? The answer is yes: just look at the meta-information available to the package manager.

$apt-cache show gnome-utils
Package: gnome-utils
Status: install ok installed
Priority: optional
Section: gnome
Installed-Size: 20700
Maintainer: Debian GNOME Maintainers <pkg-gnome-maintainers@lists.alioth.debian.org>
Architecture: i386
Version: 2.26.0-1
Replaces: baobab, gdict, gnome-admin (<= 1.0.3-2), gnome-panel (<< 2.9), gnome-panel-data (<< 2.9)
Provides: dict-client, gdict
Depends: e2fslibs (>= 1.37), libart-2.0-2 (>= 2.3.18), libatk1.0-0 (>= 1.20.0), libbonobo2-0 (>= 2.15.0),
               libbonoboui2-0 (>= 2.15.1), libc6 (>= 2.3.6-6~), libcairo2 (>= 1.2.4), libdbus-1-3 (>= 1.0.2),
               libfontconfig1 (>= 2.4.0), libfreetype6 (>= 2.2.1), libgconf2-4 (>= 2.23.2),
               libgdict-1.0-6 (>= 2.23.90), libglade2-0 (>= 1:2.6.1), libglib2.0-0 (>= 2.18.0), libgnome-desktop-2-11,
               libgnome2-0 (>= 2.17.3), libgnomecanvas2-0 (>= 2.11.1), libgnomeui-0 (>= 2.22.0),
               libgnomevfs2-0 (>= 1:2.17.90), libgtk2.0-0 (>= 2.14.0), libgtop2-7 (>= 2.23.2), libhal1 (>= 0.5.8.1),
               libice6 (>= 1:1.0.0), liborbit2 (>= 1:2.14.10), libpanel-applet2-0 (>= 2.19.3), libpango1.0-0 (>= 1.14.0),
               libpopt0 (>= 1.14), libsm6, libstartup-notification0 (>= 0.10), libx11-6, libxext6, libxml2 (>= 2.6.27),
               zlib1g (>= 1:1.1.4), gconf2 (>= 2.10.1-2)
Recommends: gksu
Suggests: yelp, gcalctool
Conflicts: baobab, gdict, gfloppy, gnome-panel (<< 2.10), gnome-panel-data (<< 2.10)
Description: GNOME desktop utilities
 This package contains the following utilities for the GNOME desktop:
 .
  - baobab, a disk usage analyser
  - gfloppy, a tool for formatting floppy disks
  - gnome-dictionary, a program which can look up the definition of words
    over the internet (including a panel applet to do the same)
  - gnome-search-tool, with which one can find files by name or content
  - gnome-system-log, a log viewing application
  - gnome-screenshot, a tool to take desktop screenshots and save them into
    a file
Homepage: http://live.gnome.org/GnomeUtils

Do you see the Replaces: and Conflicts: lines? The package gnome-utils both replaces and conflicts with the old package baobab, which is a telltale sign of the fact that it supercedes it. According to Debian Policy, one might also expect a Provides: baobab in the metadata, but it is understandable that old package names be dropped over time to avoid polluting the package namespace.

A nice package manager should have said

$nice-package-manager install baobab
The baobab package exists in the oldstable baseline, but is superceded by
the more recent gnome-utils (2.26.0-1), which is already installed on your system.
The package gnome-utils might already contain all the functionality of package baobab.
Do you really want to install the package baobab and uninstall/downgrade gnome-utils? [y/N]

And this would have allowed me to spend an afternoon doing something else :-)

Conclusions

As we have seen, managing a set of installed packages on a GNU/Linux machine is not an easy task, either from the complexity point of view (the problem is NP-Complete), or the usability point of view (autoremove is nice sometimes, and sometimes not). Mancoosi is helping along with some fundamental issues, like the development of efficient algorithms, flexible user optimization criteria and distribution-independent formats for exchanging and representing upgrade problems, as well as by collecting real user experience records.

But much more is left to be done to take into account the evolution of packages over time: the case of the baobab package shown here has been an interesting running example to see how wrong things can go when the complexity of all the issues related to computational complexity, optimization, distribution policy and usability is intermixed.

Disclaimer for casual readers

Please notice that the baobab case chosen here is just an example: the goal was to show a real example where many complex intertwined issues come to light, and where the user is led astray by the current tools. Of course, one could say that I should not keep oldstable among the sources for apt-get or aptitude; or that I should have tried to type baobab in the command line before installing the package; others could even come up with much more debatable suggestions like "use distribution XXX instead of Debian", or "RPM would not have this issue". Any comment along these lines would be completely out of scope.

Also notice that I used apt-get and aptitude, but very similar issues come up with many other package managers, so this post should not be construed as a negative criticism of these tools (that I use daily): our goal in Mancoosi is to help all package managers improve, to help users have a better experience with Free Software

It would also be highly inappropriate to use material herein to pretend that Free Software is less usable than proprietary software: configuration and upgrade maintenance are very difficult problems that exist pretty much in the proprietary world too, even if they are hidden behind nice GUI interfaces; in the Free Software world, we are making this open, and leading the way by experimenting new ideas that the industries from the proprietary world follow closely.