Re: [ANNOUNCE] GSoC project: Improving kconfig using a SAT solver

[James Bottomley <James.Bottomley@HansenPartnership.com>]

On Mon, 2010-05-17 at 16:21 +0200, Vegard Nossum wrote:
> On 17 May 2010 15:21, James Bottomley
> <James.Bottomley@hansenpartnership.com> wrote:
> >> > I assume you got inspired by the libzypp use of a SAT solver
> >> > for package dependencies?  One problem that is visible there
> >> > is that it can be hard to display conflicts in a nice and understandable
> >> > way to the user, especially if there are lots of dependencies.
> >> >
> >> > It might be worth planning in some time to solve that nicely.
> >>
> >> Thanks! I didn't actually get inspired by libzypp -- but somebody else
> >> mentioned it too, so I guess I should take a look!
> >>
> >> You bring up a valid point, and I admittedly haven't given it VERY
> >> much thought yet, but I think that conflicts could be displayed in the
> >> following way: If an instance is unsolvable, then it means that all
> >> possible valuations/assignments make at least one clause (disjunction)
> >> false. Each clause is usually generated by exactly one dependency
> >> specification (the "depends on" directive), so we could print these
> >> dependencies to the screen as suggestions for how to resolve the
> >> conflict.
> >
> > Actually, the problem is a bit different from the zypper one: Since each
> > package supplies its own dependencies and obsoletes, it is possible to
> > get an unsolvable installation problem.  What zypper tries to do in
> > these situations is recommend possible courses of action (like remove
> > these five packages from your current system, or downgrade this one
> > etc.).  For the Kconfig system, an unsolvable configuration is actually
> > a bug in the Kconfig files.  You can proceed on the premise that it's a
> > single symbol that has the wrong depends or selects and isolate it from
> > there.  Done right, the Kconfig SAT solver shouldn't detect this problem
> > only when a triggering configuration is input, but all the time, so it
> > becomes impossible to introduce buggy Kconfig directives into the kernel
> > tree.
> 
> Even if the problem is different from zypper's, it is also here
> possible to get an unsatisfiable instance. You are right that, yes,
> the kconfig files on their own should always be satisfiable. But
> that's before the user has made any choices at all. An example of an
> unsatisfiable instance would be one where the user demands that 1.
> some USB driver is enabled, while 2. USB support in general is
> disabled.

Actually, these are two separate problems.  The first is basic
consistency within the Kconfig subsytstem (something that select
currently damages for us).  The second is what to present to the user,
which is where the inception of the select problem came from.  A user
doesn't really want to know that USB device X depends on usb storage,
SCSI and a raft of other things ... they just want it to configure a
kernel that supports their device.  In particular, we don't want to
present every possible option to users and then try to work out a
solution, we really need guided configuration (which, in some measure,
is what we have today: if you don't select general USB, you won't see
any USB drivers.  Or more importantly, if you select an Adaptec SCSI
card, we just enable whichever transport library it needs).

> But yes, once the basic infrastructure is in place, checking the
> consistency of the kconfig files alone (not taking user's config into
> account) should be trivial.

Right, this will solve our current kernel developer issue ... I'm
betting the guiding users one will be slightly harder.

James