User preferences for dependency solvers: a short survey, and new features added in the latest aspcud solver

A key component of a modular package manager architecture is a solver able to handle dependency problems efficiently, and compute a solution which is aligned with the user preferences. Aspcud is one of the most successful such solvers, and its new release 1.9 version brings some new features to the limelight. Let's take some time to sum up the essential concepts today.

Specifying user Preferences for Dependency Solvers

According to the approach described in the article A modular package manager architecture (also available from here), which was one of the outcomes of the efforts of our team in the Mancoosi research project, a modern package manager should adopt a modular architecture, relying on external dependency solvers for package managers, that communicate with the package manager front-end via the CUDF format.

Nowadays, several CUDF-compatible solvers are available, developed by a variety of research teams during the MISC competitions run yearly from 2010 to 2012: aspcud, Mccs, Packup and P2Cudf.

All these solvers are able to read CUDF documents, and accept a user preference parameter that allows to specify the criteria that the solver should optimize when looking for a solution. These user preferences are the main subject of this post.

What are user preferences for installations, and why are them important?

When you request the installation of some packages, say p1...pn, a package manager has a lot to do: it needs to look at all the packages already installed on your machine, find all packages available from the repositories, consider your request, and then come up with a set of actions to be performed to satisfy it.

Unfortunately, there are a lot of assumptions hidden in your mind when you tell the package manager that you want p1...pn installed: should it choose the latest version of the p1...pn? That seems a sensible thing to do, but sometimes installing a recent version of a package p may lead to downgrading or removing another package q, which is something you might not want. What should the package manager do in this case? Remove q to get the lates p, or keep q and get the most recent p that is compatible with it? Well, the answer is: it depends!!! It depends on what you really want, and different users may have different points of view.

User preferences, supported by CUDF-compatible solvers, are the means you can use to make the assumptions in your mind explicit and known to the solver, so that the actions performed on your machine correspond to your personalised needs.

How do I specify my preferences?

Preferences are expressed using a simple language built by prefixing a little set of combinators with the - (minus, for minimisation) or + (plus, for maximisation) operators.

The simplest combinators, introduced in the MISC 2010 competition, are the following ones:

  • new : the number of new packages
  • changed : the number of packages modified
  • removed : the number of packages removed
  • notuptodate : the number of packages that are not at their latest version

For example, the preference -removed tells the solver that among all possible ways of satisfying your request, it should choose one that minimises the number of packages removed.

These combinators can be combined in a comma separated sequence, that is treated in lexicographic order.

For example, the preference -removed,-notuptodate,-changed tells the solver that after ensuring that removals are minimised, it should look for a solution that minimises also the number of packages wich are not at their latest version, and then reduce the changes to a minimum.

If you are a very conservative user, you might prefer to use -removed,-changed instead

Yes, there are different versions of the user preference language

The preferences language described in the previous section, which corresponds to the one used in the 2010 competition, should be supported by all external solvers, but if you happen to use as external solver one of the entrants of the 2012 competition, like recent versions of aspcud, then you have access to a more sophisticated set of preferences, described in the 2012 MISC competition rules. In this setting, you can create preference combinators by applying a predefined set of operators to package selectors.

Package selectors

Package selectors allows to identify a set of packages, and since 2012 one could use the following:

  • solution is the set of packages that are in the solution found by the solver
  • changed is the set of packages that have been either newly installed or removed (this includes upgrades and downgrades, that can be seen as a removal followed by an installation)
  • new is the set of packages that are present in the solution, and for which no package of the same name was initially installed.
  • removed is the set of packages that were initially installed, and for which no package of the same name is present in the solution.
  • up is the set of upgraded packages.
  • down is the set of downgraded packages.

Operators

Operators allow to compute an integer value from a set of packages, and since 2012 one could use the following:

  • count(X) is the number of packages in X.
  • sum(X,f) is the sum over all packages in the set X of the value of their integer field f.
  • notuptodate(X) is the number of packages in X that are not in the latest known version.
  • unsat_recommends(X) counts the number of disjunctions in Recommends-fields of packages in X that are not satisfied in the solution.
  • aligned(X,g1,g2) is technically equal to #{ (x.g1,x.g2) | x ∈ X } - #{ x.g1 | x ∈ X }. In other words, one groups the packages in X according to their values at the properties g1 and g2 and count the number of groups, yielding a value v1. Then we do the same when grouping only by the property g1, yielding a value v2. The value returned is v1-v2, which is useful, for example, to spot binary packages built from different versions of the same source package.

An example, please!!!

For example, you could use -count(removed),-count(down),-sum(solution,installedsize),-notuptodate(solution),-count(changed) to instruct a solver to minimise removals, then downgrades, then the installed size, then the number of packages not at their latest version, and finally the number of packages changed on the systems.

News in aspcud 1.9.x

The aspcud solver supports this extended language starting from its version 1.8.0, but starting from version 1.9.x, it adds support for three extra selectors, that are particularly useful to preform local upgrades. Here they are:

  • installrequest is the set of packages in the solution that satisfy the requirements mentioned in the install: part of a CUDF request
  • upgraderequest is the set of packages in the solution that satisfy the requirements mentioned in the upgrade: part of a CUDF request
  • request is the union of the above two

Using this extended set of package selector, it is now finally possible to specify user preferences that describe optimisations to be applied only to the packages explicitly mentioned in the request. For example, -notuptodate(request),-count(changed) would find a solution that tries to bring all packages mentioned in the request to their latest version, while leaving all the rest as untouched as possible.

And if we have added to each package a priority value, we could also play with preferences like +sum(upgraderequest,priority),-count(changed) to get the packages mentioned in the upgrade request to the version with the highest possible priority, while leaving all the rest as untouched as possible.

How to get aspcud 1.9.x

Just go to the aspcud release page, or the aspcud svn repository, and enjoy!!!

And of course, special thanks to Roland Kaminski for having released aspcud 1.9.x with the new suggested selectors, and various improvements that make it easier to port across a wide set of platforms.