dist-upgrade: Revert phased updates using keeps only

In the bug, mutter was kept back due to phasing and the new gnome-shell
depended on that, and was therefore kept back as well, however,
gnome-shell-common was not broken, and apt decided to continue upgrading
it by removing gnome-shell and the ubuntu desktop meta packages.

This is potentially a regression of LP#1990586 where we added keep
back calls to the start of the dist-upgrade to ensure that we do not
mark stuff for upgrade in the first place that depends on phasing
updates, however it was generally allowed by the resolver to also
do those removals.

To fix this, we need to resolve the update normally and then use
ResolveByKeepInternal to keep back any changes broken by held back
packages.

However, doing so breaks test-bug-591882-conkeror because ResolveByKeep
keeps back packages for broken Recommends as well, which is not
something we generally want to do in a dist-upgrade after we already
decided to upgrade it.

To circumvent that issue, extend the pkgProblemResolver to allow
a package to be policy broken, and mark all packages that already
were already going to be policy broken to be allowed to be that,
such that we don't try to undo their installs.

LP: #2025462

3 files changed, 32 insertions, 10 deletions

diff --git a/apt-pkg/algorithms.cc b/apt-pkg/algorithms.cc
index 272917b08..3d4096a94 100644
--- a/apt-pkg/algorithms.cc
+++ b/apt-pkg/algorithms.cc
@@ -1234,7 +1234,8 @@ bool pkgProblemResolver::InstOrNewPolicyBroken(pkgCache::PkgIterator I)
    }
 
    // a newly broken policy (recommends/suggests) is a problem
-   if (Cache[I].NowPolicyBroken() == false &&
+   if ((Flags[I->ID] & BrokenPolicyAllowed) == 0 &&
+       Cache[I].NowPolicyBroken() == false &&
        Cache[I].InstPolicyBroken() == true)
    {
       if (Debug == true)
diff --git a/apt-pkg/algorithms.h b/apt-pkg/algorithms.h
index 12a77d4b8..f06a38c1b 100644
--- a/apt-pkg/algorithms.h
+++ b/apt-pkg/algorithms.h
@@ -102,10 +102,16 @@ class APT_PUBLIC pkgProblemResolver						/*{{{*/
    typedef pkgCache::PrvIterator PrvIterator;
    typedef pkgCache::Version Version;
    typedef pkgCache::Package Package;
-   
-   enum Flags {Protected = (1 << 0), PreInstalled = (1 << 1),
-               Upgradable = (1 << 2), ReInstateTried = (1 << 3),
-               ToRemove = (1 << 4)};
+
+   enum Flags
+   {
+      Protected = (1 << 0),
+      PreInstalled = (1 << 1),
+      Upgradable = (1 << 2),
+      ReInstateTried = (1 << 3),
+      ToRemove = (1 << 4),
+      BrokenPolicyAllowed = (1 << 5)
+   };
    int *Scores;
    unsigned char *Flags;
    bool Debug;
@@ -129,7 +135,10 @@ class APT_PUBLIC pkgProblemResolver						/*{{{*/
    
    inline void Protect(pkgCache::PkgIterator Pkg) {Flags[Pkg->ID] |= Protected; Cache.MarkProtected(Pkg);};
    inline void Remove(pkgCache::PkgIterator Pkg) {Flags[Pkg->ID] |= ToRemove;};
-   inline void Clear(pkgCache::PkgIterator Pkg) {Flags[Pkg->ID] &= ~(Protected | ToRemove);};
+   inline void Clear(pkgCache::PkgIterator Pkg) { Flags[Pkg->ID] &= ~(Protected | ToRemove | BrokenPolicyAllowed); };
+#ifdef APT_COMPILING_APT
+   inline void AllowBrokenPolicy(pkgCache::PkgIterator Pkg) { Flags[Pkg->ID] |= BrokenPolicyAllowed; };
+#endif
 
    // Try to intelligently resolve problems by installing and removing packages
    bool Resolve(bool BrokenFix = false, OpProgress * const Progress = NULL);
diff --git a/apt-pkg/upgrade.cc b/apt-pkg/upgrade.cc
index e3e98e5c6..3e1bb292b 100644
--- a/apt-pkg/upgrade.cc
+++ b/apt-pkg/upgrade.cc
@@ -134,8 +134,6 @@ static bool pkgDistUpgrade(pkgDepCache &Cache, OpProgress * const Progress)
 
    pkgDepCache::ActionGroup group(Cache);
 
-   PhasedUpgrader().HoldBackIgnoredPhasedUpdates(Cache, nullptr);
-
    /* Upgrade all installed packages first without autoinst to help the resolver
       in versioned or-groups to upgrade the old solver instead of installing
       a new one (if the old solver is not the first one [anymore]) */
@@ -216,9 +214,23 @@ static bool pkgDistUpgrade(pkgDepCache &Cache, OpProgress * const Progress)
       }
    }
 
-   PhasedUpgrader().HoldBackIgnoredPhasedUpdates(Cache, &Fix);
+   bool success = Fix.ResolveInternal(false);
+   if (success)
+   {
+      // Revert phased updates using keeps. An issue with ResolveByKeep is
+      // that it also keeps back packages due to (new) broken Recommends,
+      // even if Upgrade already decided this is fine, so we will mark all
+      // packages that dist-upgrade decided may have a broken policy as allowed
+      // to do so such that we do not keep them back again.
+      pkgProblemResolver FixPhasing(&Cache);
+
+      for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
+	 if (Cache[I].InstPolicyBroken())
+	    FixPhasing.AllowBrokenPolicy(I);
+      PhasedUpgrader().HoldBackIgnoredPhasedUpdates(Cache, &FixPhasing);
+      success = FixPhasing.ResolveByKeepInternal();
+   }
 
-   bool const success = Fix.ResolveInternal(false);
    if (Progress != NULL)
       Progress->Done();
    return success;