On Wed, Dec 22, 2010 at 06:32:20PM +0100, Julian Andres Klode wrote:
> as discussed on IRC; the time is ready for APT to gain some more
> advanced facilities in the area of solving dependency problems.
I surely concur :)
> The first file that I attach is solver.h. This outlines my proposal for
> a new solver API. It contains the interface of an abstract base class
> APT::Solver that provides an interface for solving changes, inspired by
> discussions with some members of the community.
I leave the comments on this API to the tech APT people.
However, to my recalling, there was an unsolved problem in dealing with
an external solver, namely how to discriminate between packages coming
from APT repositories and identically-looking packages which have been
possibly locally rebuilt by the user. Does your API rely on hashing of
some set of package field to generate package identifiers as the current
APT?
I believe this problem deserves a cleaner solution, but the only
solutions I can imagine require support at the dpkg level as well.
> It shall be the base for two new classes: SatSolver and CudfSolver. The
> first class implements a solver based on the boolean satisfiability
> problem, the second one an interface to an external solver with data
> exchange happening via the CUDF format[1]. We'd also be willing to merge
> aptitude's solver into this new infrastructure if useful.
<snip>
> I also have a proof of concept CUDF writer written in Python, but
> decided that we do not really need it now (it only writes the universe
> to stdout, no request). And yes, pure CUDF, no Debian-specific version
> thereof.
I'm glad to hear this. Is the code in APT2? I'd appreciate pointers to
it to have a look. Also, I've noticed a backlog on IRC (sorry, too late
to reply to it) about some very interesting performances of your writer;
care to report them here?
> If there are no objections, I will create a new branch, and implement
> a SatSolver using picosat therein (as that's fairly easy and produces
> good results).
Here, are you referring to an APT branch or ...?
> I would also like to create the CudfSolver, but I'd need a solver to
> test with. If anyone knows such solvers, please write.
In the Mancoosi project we do have quite some of them, coming from the
MISC 2010 competition http://www.mancoosi.org/misc-2010/ . In general,
we have two variants of each participant solver, one implementing a
"trendy" optimization strategy (try to upgrade as much packages as
possible), and another one implementing a "paranoid" strategy (try to
satisfy user request, but by changing as little packages as
possible). Mind you though, as the participants were free to use the
language they want, there's quite some Java around which is not exactly
"fast" in CUDF parsing.
I'm adding to Cc: Pietro Abate, a co-worker of mine in the Mancoosi
project. He has been one of the main organizers of the MISC competition
and he has collected the code of all participant solvers. Unfortunately
there is at least one case in which we cannot re-distribute the code of
a participating solver (it was licensed to us only for the purposes of
the competition), but all other solvers are free software. Pietro can
give you the actual code and/or point you to where the solvers are
available for download.
( Pietro: for reference the initial mail of this thread is at
http://lists.debian.org/deity/2010/12/msg00053.html )
Cheers.
--
Stefano Zacchiroli -o- PhD in Computer Science \ PostDoc @ Univ. Paris 7
zack@{upsilon.cc,pps.jussieu.fr,debian.org} -<>- http://upsilon.cc/zack/
Quando anche i santi ti voltano le spalle, | . |. I've fans everywhere
ti resta John Fante -- V. Capossela .......| ..: |.......... -- C. Adams
Attachment:
signature.asc
Description: Digital signature