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

[Daniel Burrows]

On Tue, Mar 03, 2009 at 11:49:14PM -0800, Daniel Burrows <dburrows at debian.org> was heard to say:
> I haven't put my finger on exactly what was going on, but
> safe-upgrade is heavily based on user constraints, and I'm guessing
> there was some pathological interaction that was causing it to never
> pick the one dependency that would have made it obvious that all those
> packages had to be held back.

  The answer, now that I've got some sleep, is obvious.  I put in that
rule to avoid a situation where the user had rejected one decision that
was on most of the chains of reasoning (esp. the "better"-looking ones).
Since most decisions in a normal resolver run aren't rejected, and
hence most dependencies don't impinge on a user constraint, this had the
effect of forcing the resolver to honor the handful of rejections the
user had put in place prior to doing anything else.

  Fast-forward to now...it turns out that safe-upgrade rejects all but
one version of every package in the archive.  So the assumptions are
reversed: most dependencies *do* impinge on a user constraint.  This
leads to a sort of "priority inversion" in the resolver, where the one
dependency that would sort anything out can't be looked at until all
the other dependencies *that the search would ever look at* have been
examined...even though most of those branches of the search, or in this
case all of them, end up being dead-ends (they go into the deferred
queue and are never heard from again).

  Daniel