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

[Daniel Burrows]

On Sat, Feb 14, 2009 at 08:35:54AM -0800, Daniel Burrows <dburrows at debian.org> was heard to say:
>   But in fact, I have trouble thinking of any situation where it is
> reasonable to prefer removals to installs, and I can't think of *any*
> situation where it is *un*reasonable to prefer installs to removals
> (even if it's not what the user wants, at least it doesn't make them go
> "WTF!?!").  And I've finally thought of a clean, simple, easy mechanism
> that will provide the desired predictability, while also allowing some
> elegant optimizations that should defuse the worries I had about the
> performance impacts of going down this road.  I'm still not sure whether
> the semantics are right, which is part of why I'm writing this list.

  So, I have come across one case where this is wrong.  Fully replacing
a package under Policy 7.6.2 should be considered a "safe" operation,
and it's tricky to get right under this proposed design.

  Say we have two packages, "Old" and "New", and "New" replaces "Old".
Consider the following cases:

  (1) Both "Old" and "New" are installed.  In this case, we can simply
      say that removing "Old" is still considered to be on the "safe"
      tier.  (if New is removed, the search node will be promoted to
      the "removal" tier)

  (2) Only "New" is installed.  In this case nothing needs to be done:
      removing "New" and installing "Old" *should* be pushed to a later
      search tier, IMO.

  (3) Neither package is installed.  In this case, again, nothing is
      to be done: we only care about the replacement if Old is
      installed by a search node, and once it is, every successor of
      that node must include it by the monotonicity rule.

  (4) Only "Old" is installed.  In this case we need to ensure that it's
      possible to remove Old and install New without incurring a tier
      promotion.

      One solution would be to "demote" the tier of "remove Old", but
      *only* in search nodes that also contain New (and don't yet
      remove "Old").  That would be safe and easy, but it doesn't solve
      the problem.  Suppose we have a package "SomethingElse" that
      conflicts with "Old", but not "New".  In this case, we might want
      to know that installing "New" instead of "Old" will fix the
      problem safely -- but removing "Old" will hurl us into the
      removal tier, so we won't be able to even realize that "New" can
      be installed.

      The only way I can think of to solve this seems like a little
      bit of a hack, but it should work and if it's the best option,
      it might be worth it.  Basically, the idea is to somehow force
      the resolver to output the solution that also contains "New"
      *as soon as* it removes "Old", and in particular before the
      intermediate solutions are sorted by tier.  This would solve the
      problem, because that temporarily "bad" solution would never be
      seen; or rather, it would be seen, but so would the "good"
      solution containing "New".

      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.

      The big thing that worries me about this hack is that it causes
      the resolver to "spontaneously" install packages without any
      need, something it doesn't do right now: at the moment, every
      package install can be traced to a dependency.  OTOH, if the
      install produces a usable solution, then arguably it *was*
      needed; it was used to "fix" the conflict in a safe way.

      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.

  Daniel