[Caml-list] External dependency solvers for opam

[Caml-list] External dependency solvers for opam

[Roberto Di Cosmo]

Dear all,
     the short story is that we need help in packaging for Mac OSX and Windows
some specialised solvers that can be used with opam, and are already packaged
for Debian: aspcud, mccs and packup, with aspcud being the highest priority.

The Debian packages, built by Ralf Treinen, are a good entry point for any
volunteer, as they contain the pointer to the upstream source, list the
C/C++ libraries and other dependencies involved, and contain useful patches
not yet integrated upstream; even if you do not have a Debian (or Ubuntu)
machine at hand, most of the information is available here

   aspcud : http://packages.debian.org/wheezy/aspcud
   mccs   : http://packages.debian.org/wheezy/mccs
   packup : http://packages.debian.org/wheezy/packup

If you are willing to help with this work, please post a comment under the
corresponding issues opened on github, and say to what part of the effort
you whish to contribute, so we can have some basic coordination among
the volunteers.

   aspcud : https://github.com/ocaml/opam/issues/1074
   mccs   : https://github.com/ocaml/opam/issues/1075
   packup : https://github.com/ocaml/opam/issues/1076

Now, here comes the long story, that might be of interest for you even if
you are just a regular user of opam.

As you might know, the opam package manager incorporates state-of-the-art
technology that has been developed for managing packages in GNU/Linux
distributions in the Mancoosi project (www.mancoosi.org), and uses the
libcudf and dose libraries from it.

A key point of the approach which we set forth in Mancoosi (for the interested
reader, see [1,2] below), is that a modern package manager should clearly
separate a platform specific front-end from a platform independent back-end in
charge of solving dependencies in order to perform upgrades or downgrades
according to the user's preferences. 

Using the CUDF format as a pivot, we can share the effort of developing
efficient solvers among multiple package managers, and can even use different
solvers in the same package manager if the default one hits its limits (which
*can* happen, as dependency solving is an NP-complete problem). This is actually
possible today in Debian: you can call apt-get with the option --solver SOLVER
where SOLVER can be aspcud, mccs or packup.

User preferences are an important, and often overlooked concept: when you 
request the installation of a package, there might be many ways of satisfying
it, and a user should be able to state, for example, whether he is a "trendy"
person that prefers to see all other packages upgraded to the latest possible
version at the same time, or on the contrary, a "paranoid" person that wants
to change them as little as possible.

This is why all CUDF compliant solvers allow to specify user preferences by
combining lexicographically keyworks like "new", "changed", "removed", "notuptodate";
for example, a trendy person will use as preference

   -removed,-notuptodate,-new

meaning "please minimise the number of removed packages, and then the number
of packages that are not at their latest version, and finally the number of
package that were not already present"

While a paranoid person would use

   -removed, -changed

meaning "please minimise the number of removed packages, and then the number of
packages that are modified (installed/removed/upgraded/downgraded)".

Actually, the criteria supported by the CUDF solvers evolved over time, and 
aspcud supports nowadays a more sophisticated preference language
(see http://www.mancoosi.org/misc-2012/criteria/), but all of "new",
"changed", "removed" and "notuptodate" can be encoded in the latest version,
and aspcud as packaged for Debian accepts them right away.

The good news is that opam has built-in support to use aspcud as an external
CUDF-compliant solver too: if aspcud is installed on your machine, then
dependency solving will be delegated to aspcud, and the default preferences are
set to -removed,-notuptodate,-new.

You can change these preferences if needed by just setting the OPAMCRITERIA
environment variable, and you can ask opam not to use the external solver
with the option --no-aspcud (that should really be --no-external-solver).

Now that the opam users are hitting the limits of the internal solver embedded
in opam, it is important to have CUDF compliant solvers available on all platforms:
aspcud is a priority because it can be used by opam right away (no need to change
even a single line of code), but packup and mccs are important too, as with little
changes in the opam code one will be able to choose which solver to use.

So, to sum up:

 - if you are running Debian (or a Debian-based distribution, like Ubuntu), lucky you,
   just apt-get install aspcud and you are all set; you can even play with OPAMCRITERIA
   to adjust the solutions to your needs, and you can use --no-aspcud if you want to
   see the difference with the internal solver

 - if you are on another platform, stay tuned for when packages for aspcud/packup/mccs
   will be available on your platform

--
Roberto

[1] A modular package manager architecture, http://dx.doi.org/10.1016/j.infsof.2012.09.002
    also freely available from http://www.dicosmo.org/Articles/2013-AbateDiCosmoTreinenZacchiroli-Ist.pdf

[2] Dependency solving: A separate concern in component evolution management, http://dx.doi.org/10.1016/j.jss.2012.02.018 
    also freely available from http://www.dicosmo.org/Articles/2012-AbateDiCosmoTreinenZacchiroli-Jss.pdf