[Aptitude-devel] Design notes on producing better (or at least more predictable) resolver results.
dburrows at debian.org
Mon Feb 16 04:26:57 UTC 2009
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
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
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.
More information about the Aptitude-devel