[Aptitude-devel] Design notes on producing better (or at least more predictable) resolver results.

[Daniel Burrows]

On Sun, Feb 15, 2009 at 08:26:57PM -0800, Daniel Burrows <dburrows at debian.org> was heard to say:
  [quoting a lot of myself for full context]
>       We would accomplish this using some sort of "link" that means
>       "whenever you create a search node containing this version, also
>       create a search node that adds this other version (if it's
>       legal)".  So, we would add links from the removal version of
>       "Old" to every version of "New" that fully replaces "Old"; if the
>       resolver had a search node S that installed "SomethingElse" and
>       it was planning to fix its conflict by removing "Old", it would
>       generate the following successors:
> 
>           (a) S + "remove Old"
>           (b) S + "remove Old" + "install New"
> 
>       The difference is that the current resolver will only produce (a)
>       because it has no reason to try installing New.
 [snip]
>       As a side effect, this could interact badly with some other
>       assumptions the resolver makes: normally it can save time by
>       throwing out a search node if a solution that was previously
>       produced is a strict subset of that node.  A perfect example of
>       this is (a) and (b) above: (a) is a subset of (b), so if (a) was
>       a solution, the user would never see (b).  On the other hand, if
>       this ever happens, then (a) ended up at a lower tier than (b);
>       since the whole point of this is to allow (b) to appear if it's
>       a lower tier than (a), maybe that's OK.

  Of course, there's a very simple solution to this problem, and I
don't know why I didn't see it before.  It's the same problem we have
with unresolved soft dependencies: we need to remember *in the
solution* that we have made a *positive* decision not to replace the
package that's being replaced.  That way, the full solution that just
removes "Old" is not a subset of the solution that installs "New" also,
because the second solution doesn't contain the note that the
replacement wasn't carried out.  In fact, solutions that replace "Old"
with "New" might end up being subsets of solutions the don't, but that
install "New" later on via another route.

  That wraps the whole thing up neatly.  The only remaining question I
have is, should this be an intrinsic property of versions (represented
in the universe by stepping over dep lists and querying for full
replacements), or should it be passed in the way scores and initial
installations are?
  My first thought was that it would be passed in like a score, but I'm
starting to think that it's more of an intrinsic property along the
lines of a soft dependency.  Which reminds me, I really should write
that intermediate caching layer for the universe sometime... (calculating
dependency solution lists and so on can be expensive; it would be nice
to compute them less often)

  Daniel