Re: RFC: The Future of Solving Dependency Problems in APT (SAT, CUDF)
Ho, ho, ho all :)
On Wed, Dec 22, 2010 at 18:32, Julian Andres Klode <jak@debian.org> wrote:
> as discussed on IRC; the time is ready for APT to gain some more
> advanced facilities in the area of solving dependency problems.
(as said on IRC, i am a bit low on time, but some comments anyway)
> 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.
Passing a depCache into an abstract resolver seems a bit strange as
it is the key part of the internal APT resolver including a lot of stuff which
will properly not be used by another resolver (okay, aptitude, but picosat?),
e.g. State of dependencies, autoremove flags and so on.
What we want is exporting only the pkgCache to the resolver to save them
from the hassle of parsing the Packages files on their own. Resolvers who
can handle a pkgCache will be happy, others need an intermediate level to
reformat it to some other format (e.g. {C,D}UDF).
(thinking of pkgCache as a really big {Package,Version}Set)
Further more, i would like to have a Hold(VersionSet) to tell the resolver
e.g. about dpkg holds and maybe even a Keep(PackageSet) to tell the
resolver to never remove this set of packages (but upgrade is fine) which
could be handy for essentials and co.
In return i would expect a set of versions of packages to install and to
remove.
Solver::Rules is a mystery for me. Most complains about the resolver in
APT evolve from the fact that it doesn't switch candidate versions if it
has to (the popular car v2 with wheels v3 and v2 example comes to mind).
How to transport the meaning of candidate after all?
For me, candidate is an (important) implementation detail of the APT resolver.
Another resolver should be able to choose freely if he wants to put on wheel
v3 or v2 and therefore doesn't need a concept of candidate version.
I would say that every version i tell the solver about should be a candidate
for him to choose from -- why should i tell him about versions i don't want
in the first place after all? So in the end pkgCache is maybe the wrong
choice and we should give the solver a (big) VersionSet as problem space.
The problem with these multiple candidates would be that while an experimental
package can be a candidate, if at all possible stable should be preferred
which leads us to think about how we exposure pkgPolicy to the resolver world.
Wasn't in an old thread yet-another-description language mentioned for
exactly this task?
> 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.
I would divide Solvers into Internal (i can pass pkgCache/VersionSet directly
into it) and External (i need to reformat pkgCache/VersionSet) and subclass
it for {D,C}UDF and maybe other formats of other resolvers.
After all, how a solver solves isn't really interesting for the implementation
of an interface to it - and hard to define or in what category belongs
APT/aptitude?
Beside that a CUDFSolver could be a SATSolver internally (noone forbids
writing a picosat solver based on cudf data)…
> The second attachment, sat-solver.cc, is a proof of concept stand-alone
> SAT solver on APT, utilizing the SAT solver 'picosat' for the actual
> solving process. The version of 'picosat' in Debian is built without
> trace support, if you link the program against a version with trace
> support, it can tell which dependencies could not be satisfied (but it
> requires a bit more memory then, mostly for storing which clause belongs
> to which dependency).
If i see it correctly your proof of concept doesn't use the depCache -
beside for the sake of simulating more what APT does - so that would
be a proof by experiment for my theory above. :)
Integrating the proof into apt-get directly should be relatively simple but i
would like to see the abstraction to be in first so that APT doesn't need to
be linked against picosat (and all the others which will come maybe).
Some sort of plugin system maybe…
The version system (and a bit of other stuff) in APT has some sort of
built-in plugin system, if we could make that more dynamic…
(yes, i am dreaming a bit now)
> 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.
You forgot in your implementation that Debian has a lot of implicit
dependencies (or conflicts if you like) as it doesn't allow two different
version of the same package to be installed (minor, but to consider)
and i think there were other obstacles mentioned in the older threads
which make it helpful at least to use a debian specific format if possible,
but i am not sure and again i can't find it right now.
> 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). I would also like to create the CudfSolver, but I'd need a
> solver to test with. If anyone knows such solvers, please write.
Regarding picosat, feel free to go on, i am interested to see what will
happen and it could "simplify" abstraction if we have two solvers to
"hide" under a common interface instead of just the APT beast as we
have only one try to get it right before the front-ends will (ab)use it…
On the other hand, i would like to claim CUDF for me as i am currently
in the process of setting up a stay at "mancoosi headquarter" around
April to work on teaching APT how to read/write CUDF and doing
something meaningful in between. :)
After all an interesting year 2011 is upcoming, but until then:
Merry package management days… -uh, i mean Christmas :)
David
Reply to: