[Aptitude-devel] external solver support?

Fri Sep 19 15:01:28 UTC 2008

On Fri, Sep 19, 2008 at 07:19:15AM -0700, Daniel Burrows wrote:
> > [1] we have found even simple examples in which all solvers we have in
> >     Debian fail to find a solution where on exists and can be easily
> >     found by any SAT solvers
>   Really?  The only cases I'm aware of that occur in the wild are things
> like the bug that was recently reported against apt, which involve a full
> system upgrade with lots of complicated dependencies.

Yup, but I wasn't the guy doing the tests and I don't know if the reason
you mention or not. I'll look for the actual examples and forward them.

> > That's not a big deal, and that's why I would like to have the ability
> > to invoke _external_ solvers which can be written in whatever language.
> > If people like to write them in OCaml they can do it, if the algorithm
> > works nothing inhibit to then implement it in whatever other languages.
> > Again I've a political point here: if the people working on algorithms
> > like to program in OCaml I don't want to stop them, I would like to be
> > able to tell them something like: «go implement this binary API, then we
> > can try your solver with aptitude».
> 
>   Mhm.  I don't see a problem with enabling this, but someone should
> rewrite the solver in C++ if you want it included in apt (at least,
> that's my opinion).  This isn't so much a technical objection (although

Yes, OK, no problem. These, and related concerns, are typical project
management / software engineering problem, we will think about them once
we have something working :)

> > The only additional layer I want to add to apt/aptitude is a clear
> > interface between the package manager and the solver, possibly the
> > *same* interface for the two. How do you consider this? Would it be an
> > excessive cost according to your point of view? (OK, it is hard to tell
> > without having yet the interface, but if yours is a "no-way" it would be
> > pointless to start thinking about one :-))
> 
>   I don't see a problem with having this sort of an interface present.
> I just want to make sure you're aware of the problems before you run up
> against them. :-)

ACK.

> > Then, we would like to move to user-specified optimization criteria. The
> > idea is to find a small language (like APT pinning, but with a clear
> > formalization, and with access to package properties) the user can write
> > down in a configuration file and optimize wrt that. Algorithmically, at
> > this point you will be leaving plain SAT solving and enter the harder
> > area of multi-criteria optimization ...
> 
>   But dependency resolution is *inherently* about multi-criteria
> optimization.  Throwing a SAT solver at the problem, if they aren't
> rigged for this sort of thing (and I don't know if they are as I haven't
> used them myself) is probably not going to produce terribly good results.

Not really. It is true that plain SAT solving is quite pointless for
dependency resolution *on a user machine* (you have no guarantee of the
minimality of the found solution, but we really don't want to install
half of the archive of extra packages when the user request was just one
package).

But it is not necessarily pointless for other needs of dependency
resolutions. A good, and used, example of that is the EDOS tools we are
using within Debian QA. They use SAT solving to discover that it is
possible, in some way, to install a given package, so this package is
worth to be shipped in the Debian archive. If there is no way whatever
to install a given package, it is probably not worth to distribute it at
all.

So, some instances of dependency resolution problems can properly be
addressed also by plain SAT solving, but I understand your point of
view: on the package manager side you always have something to optimize,
at least minimality of what you add to the system. The game starts to be
interesting adding more criteria of course ... (e.g., the policies
implemented in the SMART package manager).

> > "plugin system" is quite a mouthful :), my goal would be the ability in
> > apt/aptitude to invoke an *external process* as a solver. The
> > requirement of the process to be external is on one hand to leverage
> > implementation of solvers in whatever language, on the other to enable
> > shipping solvers in Debian packages other than apt/aptitude.
> 
>   You can probably base it on the protocol used to communicate with
> download helpers.

OK, even though that protocols are plain text, right? Or there are some
cases in which binary data are passed directly to apt?
... well, never mind, I'll need to have a look at that code anyhow.

> > Well, at least initially I think the whole state should be passed to the
> > solver. I've a rough idea that sending that all in a binary format would
> > be something like 400Kb, it shouldn't be that slow through a pipe (but
> > more benchmarks are needed of course).
> 
>   Hm, I suppose.  The binary format is going to be harder to debug, but
> I guess it should be pretty stable.

ACK.

> > If possible, I would prefer to work on a simplified model. Ideally, the
> > interface should not be apt-specific.
> 
>   Have I pointed you at my little write-up of aptitude's model yet?
>     http://people.debian.org/~dburrows/model.pdf
>   Nothing very exciting, but it might give you some ideas.

Nope, I wasn't aware of it, I'll have a look. In exchange, I have to
point you to the EDOS dependency model:
http://www.lsv.ens-cachan.fr/Publis/PAPERS/PDF/edos-ase06.pdf . At first
sight of your work, this EDOS paper makes not attempt to discuss
algorithms (for example the optimizations implemented by
edos-{deb,rpm}check are not discussed}, but it does illustrate the
dependency model we have used thus far.

Cheers.

-- 
Stefano Zacchiroli -*- PhD in Computer Science \ PostDoc @ Univ. Paris 7
zack@{upsilon.cc,pps.jussieu.fr,debian.org} -<>- http://upsilon.cc/zack/
I'm still an SGML person,this newfangled /\ All one has to do is hit the
XML stuff is so ... simplistic  -- Manoj \/ right keys at the right time
-------------- next part --------------
A non-text attachment was scrubbed...
Name: not available
Type: application/pgp-signature
Size: 189 bytes
Desc: Digital signature
Url : http://lists.alioth.debian.org/pipermail/aptitude-devel/attachments/20080919/c6eaf625/attachment.pgp 