On Thu, Dec 23, 2010 at 01:47:59PM +0100, David Kalnischkies wrote:
> 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.
If I read you correctly, this is indeed one of the reasons from which
APT incompleteness (i.e. the inability to find a solution to a
dependency problem where one does exist). I concur that it should not be
promoted from an APT's solver implementation detail to a part of the
problem description. Doing so will seriously undermine the room of
improvement to dependency solving capabilities that an external solver
could contribute.
> 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?
Yes, but it ain't easy to find the good balance in designing such a
language. That is why for our competition we have decided, for the
moment, to have different tracks where solvers have optimized different
strategies.
The challenge ahead of us for an external solver is deciding which, of
current APT behavior, is part of the problem description
(i.e. constraint that cannot be violated) and which are not. Those who
are not can then be expressed as optimization criteria that external
solver will be required to address.
For instance, the one about experimental will most likely become a hard
constraint, while other aspects (e.g. installation of Recommends) can
become soft constraints that the solvers will have to optimize.
> 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)…
As a matter of fact, we already have solvers CUDF solvers based on a
wide range of techniques, including: SAT, MaxSAT, PBO (Pseudo Boolean
Optimization), ASP (Answer Set Programming), and
zecret-proprietary-stuff. The results we have up to know show that no
one-size-does-fit-all solution is better than the others in all the
scenarios we have tested so far. While on one hand this might be seen as
depressing, on the other hand it is a motivation for not committing to
any specific technique, even if only in the name.
> 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.
There are a couple of glitches in getting the conversion right. One is
the one you mention about implicit conflicts (which should be made
explicit, as dependency problems coming from other distros---most
notably those RPM-based---do not have them). Another one is the
disambiguation of package names which appear both as virtual and as
non-virtual packages, as the policy requires to treat them differently
when it comes to versioned dependencies.
Cheers.
PS I'm subscribed to deity@lists.d.o, feel free to drop an explicit Cc
to me when following up
--
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