[Aptitude-devel] 0.5.2 nearly done, almost certainly.

[Daniel Burrows]

On Sun, Apr 19, 2009 at 09:21:34PM -0700, Daniel Burrows <dburrows at debian.org> was heard to say:
>   Disabling reinstatement is a brutal fix that will have unpleasant
> side-effects.  I might look into whether there's a better option, but I
> don't have many ideas.  The one thing I've thought of is to check
> whether each reinstated package conflicts or is conflicted by any
> installed package (a fairly quick test).  Doing this will solve some
> instances of the problem, but I'm not convinced that it solves all of
> them.  For instance: what if the package that can't be reinstated is a
> dependency of *another* package that was reinstated?  Is there any way
> to avoid full dependency resolution if that happens?

  I think I know the solution.  But first we have to ask, what's the
goal?  I think the goal is to reinstate dependencies whenever possible,
but without sending the program to an inconsistent state.  sweep()
should never break dependencies.  However, most of the time packages
can be reinstated without harm -- this behavior has been in there for
years without causing trouble.  So it's excessive to simply remove this
capability because it occasionally breaks when combined with the
dependency solver.  Better to fix sweep() to never break dependencies.

  To achieve that, packages should be reinstated unless one of these
conditions holds:

  (1) they conflict with an installed package
  (2) they are reinstated only due to packages which conflict with an
      installed package
  (3) they depend on a package that was not reinstated because it
      conflicts with an installed package

  So, here's the plan, in pseudocode:

def sweep_with_dependency_rollback():
    let reinstated = {}, reinstated_bad = {}

    for each package P:
        if P needs to be removed:
            remove P
        elif P needs to be reinstated:
            if P does not conflict with an installed package:
                insert P into reinstated
            else:
                insert P into reinstated_bad

    # Throw out packages that have a forward dependency on something
    # with a conflict.
    for each package P in reinstated_bad:
        for each package P' that transitively depends on P such that
            P' and all intervening packages are in reinstated:
            remove P' and the other packages along the path to P
                   from reinstated

    # Throw out packages from the reinstated set that are "orphaned".
    let reinstated_orphans = {}
    for each package P in reinstated:
        if P is in reinstated_orphans:
           continue

        if there is no manually installed package P' that transitively
           depends on P such that all the intervening packages are in
           reinstated:
           insert P into reinstated_orphans

    for each package P in (reinstated - reinstated_orphans):
        reinstate P


  The real implementation will look somewhat different (it'll be more
efficient and have a bunch of recursive routines for the complicated
conditions I wrote out), but will do more or less the same thing.

  Daniel