Delay removals due to Conflicts until Depends are resolved

Marking a package for removal is fine if we know that we have to remove
that package, but if we are in an alternative branch we might not go
this route in the end and hence have a package pointlessly marked for
removal which isn't questioned later on.

We check if we are allowed to remove that package to avoid working on
the positive dependencies if not, but we mark them for removal only
after all the other dependencies are successfully resolved.

In an ideal world we would let the problemResolver do its job on them,
but the resolver might decide against doing the removal exploring
another option like the next alternative, which might be a good idea,
but is not the behaviour we had before, so that is the best we can do
for now without changing the resolver drastically.

4 files changed, 176 insertions, 80 deletions

diff --git a/apt-pkg/depcache.cc b/apt-pkg/depcache.cc
index 2eac1ba41..7a068da1b 100644
--- a/apt-pkg/depcache.cc
+++ b/apt-pkg/depcache.cc
@@ -839,13 +839,73 @@ void pkgDepCache::Update(PkgIterator const &Pkg)
 	 Update(P.ParentPkg().RevDependsList());
 }
 									/*}}}*/
+// DepCache::IsModeChangeOk - check if it is ok to change the mode	/*{{{*/
+// ---------------------------------------------------------------------
+/* this is used by all Mark methods on the very first line to check sanity
+   and prevents mode changes for packages on hold for example.
+   If you want to check Mode specific stuff you can use the virtual public
+   Is<Mode>Ok methods instead */
+static char const* PrintMode(char const mode)
+{
+	 switch (mode)
+	 {
+	 case pkgDepCache::ModeInstall: return "Install";
+	 case pkgDepCache::ModeKeep: return "Keep";
+	 case pkgDepCache::ModeDelete: return "Delete";
+	 case pkgDepCache::ModeGarbage: return "Garbage";
+	 default: return "UNKNOWN";
+	 }
+}
+static bool IsModeChangeOk(pkgDepCache &Cache, pkgDepCache::ModeList const mode, pkgCache::PkgIterator const &Pkg,
+			   unsigned long const Depth, bool const FromUser, bool const DebugMarker)
+{
+   // we are not trying to hard…
+   if (unlikely(Depth > 100))
+      return false;
+
+   // general sanity
+   if (unlikely(Pkg.end() == true || Pkg->VersionList == 0))
+      return false;
+
+   // the user is always right
+   if (FromUser == true)
+      return true;
+
+   auto &P = Cache[Pkg];
+   // not changing the mode is obviously also fine as we might want to call
+   // e.g. MarkInstall multiple times with different arguments for the same package
+   if (P.Mode == mode)
+      return true;
+
+   // if previous state was set by user only user can reset it
+   if ((P.iFlags & pkgDepCache::Protected) == pkgDepCache::Protected)
+   {
+      if (unlikely(DebugMarker == true))
+	 std::clog << OutputInDepth(Depth) << "Ignore Mark" << PrintMode(mode)
+		   << " of " << APT::PrettyPkg(&Cache, Pkg) << " as its mode (" << PrintMode(P.Mode)
+		   << ") is protected" << std::endl;
+      return false;
+   }
+   // enforce dpkg holds
+   else if (mode != pkgDepCache::ModeKeep && Pkg->SelectedState == pkgCache::State::Hold &&
+	    _config->FindB("APT::Ignore-Hold",false) == false)
+   {
+      if (unlikely(DebugMarker == true))
+	 std::clog << OutputInDepth(Depth) << "Hold prevents Mark" << PrintMode(mode)
+		   << " of " << APT::PrettyPkg(&Cache, Pkg) << std::endl;
+      return false;
+   }
+
+   return true;
+}
+									/*}}}*/
 // DepCache::MarkKeep - Put the package in the keep state		/*{{{*/
 // ---------------------------------------------------------------------
 /* */
 bool pkgDepCache::MarkKeep(PkgIterator const &Pkg, bool Soft, bool FromUser,
                            unsigned long Depth)
 {
-   if (IsModeChangeOk(ModeKeep, Pkg, Depth, FromUser) == false)
+   if (not IsModeChangeOk(*this, ModeKeep, Pkg, Depth, FromUser, DebugMarker))
       return false;
 
    /* Reject an attempt to keep a non-source broken installed package, those
@@ -905,7 +965,7 @@ bool pkgDepCache::MarkKeep(PkgIterator const &Pkg, bool Soft, bool FromUser,
 bool pkgDepCache::MarkDelete(PkgIterator const &Pkg, bool rPurge,
                              unsigned long Depth, bool FromUser)
 {
-   if (IsModeChangeOk(ModeDelete, Pkg, Depth, FromUser) == false)
+   if (not IsModeChangeOk(*this, ModeDelete, Pkg, Depth, FromUser, DebugMarker))
       return false;
 
    StateCache &P = PkgState[Pkg->ID];
@@ -1004,66 +1064,6 @@ bool pkgDepCache::IsDeleteOkProtectInstallRequests(PkgIterator const &Pkg,
    return true;
 }
 									/*}}}*/
-// DepCache::IsModeChangeOk - check if it is ok to change the mode	/*{{{*/
-// ---------------------------------------------------------------------
-/* this is used by all Mark methods on the very first line to check sanity
-   and prevents mode changes for packages on hold for example.
-   If you want to check Mode specific stuff you can use the virtual public
-   Is<Mode>Ok methods instead */
-static char const* PrintMode(char const mode)
-{
-	 switch (mode)
-	 {
-	 case pkgDepCache::ModeInstall: return "Install";
-	 case pkgDepCache::ModeKeep: return "Keep";
-	 case pkgDepCache::ModeDelete: return "Delete";
-	 case pkgDepCache::ModeGarbage: return "Garbage";
-	 default: return "UNKNOWN";
-	 }
-}
-bool pkgDepCache::IsModeChangeOk(ModeList const mode, PkgIterator const &Pkg,
-				 unsigned long const Depth, bool const FromUser)
-{
-   // we are not trying to hard…
-   if (unlikely(Depth > 100))
-      return false;
-
-   // general sanity
-   if (unlikely(Pkg.end() == true || Pkg->VersionList == 0))
-      return false;
-
-   // the user is always right
-   if (FromUser == true)
-      return true;
-
-   StateCache &P = PkgState[Pkg->ID];
-   // not changing the mode is obviously also fine as we might want to call
-   // e.g. MarkInstall multiple times with different arguments for the same package
-   if (P.Mode == mode)
-      return true;
-
-   // if previous state was set by user only user can reset it
-   if ((P.iFlags & Protected) == Protected)
-   {
-      if (unlikely(DebugMarker == true))
-	 std::clog << OutputInDepth(Depth) << "Ignore Mark" << PrintMode(mode)
-		   << " of " << APT::PrettyPkg(this, Pkg) << " as its mode (" << PrintMode(P.Mode)
-		   << ") is protected" << std::endl;
-      return false;
-   }
-   // enforce dpkg holds
-   else if (mode != ModeKeep && Pkg->SelectedState == pkgCache::State::Hold &&
-	    _config->FindB("APT::Ignore-Hold",false) == false)
-   {
-      if (unlikely(DebugMarker == true))
-	 std::clog << OutputInDepth(Depth) << "Hold prevents Mark" << PrintMode(mode)
-		   << " of " << APT::PrettyPkg(this, Pkg) << std::endl;
-      return false;
-   }
-
-   return true;
-}
-									/*}}}*/
 struct CompareProviders							/*{{{*/
 {
    pkgDepCache const &Cache;
@@ -1285,25 +1285,35 @@ static APT::VersionVector getAllPossibleSolutions(pkgDepCache &Cache, pkgCache::
    return toUpgrade;
 }
 									/*}}}*/
-static bool MarkInstall_MarkDeleteForNotUpgradeable(pkgDepCache &Cache, bool const DebugAutoInstall, pkgCache::VerIterator const &PV, unsigned long const Depth, pkgCache::PkgIterator const &Pkg, bool const propagateProctected)/*{{{*/
+static bool MarkInstall_MarkDeleteForNotUpgradeable(pkgDepCache &Cache, bool const DebugAutoInstall, pkgCache::VerIterator const &PV, unsigned long const Depth, pkgCache::PkgIterator const &Pkg, bool const propagateProctected, APT::PackageVector &delayedRemove)/*{{{*/
 {
    auto &State = Cache[Pkg];
-   if (not State.Delete())
+   if (not propagateProctected)
    {
+      if (State.Delete())
+	 return true;
       if(DebugAutoInstall)
-	 std::clog << OutputInDepth(Depth) << " Removing: " << Pkg.Name() << " as upgrade is not an option for " << PV.ParentPkg().FullName() << " (" << PV.VerStr() << ")\n";
-      if (not Cache.MarkDelete(Pkg, false, Depth + 1, false))
+	 std::clog << OutputInDepth(Depth) << " Delayed Removing: " << Pkg.FullName() << " as upgrade is not an option for " << PV.ParentPkg().FullName() << " (" << PV.VerStr() << ")\n";
+      if (not IsModeChangeOk(Cache, pkgDepCache::ModeDelete, Pkg, Depth, false, DebugAutoInstall) ||
+	  not Cache.IsDeleteOk(Pkg, false, Depth, false))
 	 return false;
+      delayedRemove.push_back(Pkg);
+      return true;
    }
-   if (propagateProctected)
+
+   if (not State.Delete())
    {
-      MarkInstall_DiscardCandidate(Cache, Pkg);
-      Cache.MarkProtected(Pkg);
+      if(DebugAutoInstall)
+	 std::clog << OutputInDepth(Depth) << " Removing: " << Pkg.FullName() << " as upgrade is not an option for " << PV.ParentPkg().FullName() << " (" << PV.VerStr() << ")\n";
+      if (not Cache.MarkDelete(Pkg, false, Depth + 1, false))
+	 return false;
    }
+   MarkInstall_DiscardCandidate(Cache, Pkg);
+   Cache.MarkProtected(Pkg);
    return true;
 }
 									/*}}}*/
-static bool MarkInstall_RemoveConflictsIfNotUpgradeable(pkgDepCache &Cache, bool const DebugAutoInstall, pkgCache::VerIterator const &PV, unsigned long Depth, std::vector<pkgCache::DepIterator> &toRemove, APT::PackageVector &toUpgrade, bool const propagateProctected, bool const FromUser) /*{{{*/
+static bool MarkInstall_RemoveConflictsIfNotUpgradeable(pkgDepCache &Cache, bool const DebugAutoInstall, pkgCache::VerIterator const &PV, unsigned long Depth, std::vector<pkgCache::DepIterator> &toRemove, APT::PackageVector &toUpgrade, APT::PackageVector &delayedRemove, bool const propagateProctected, bool const FromUser) /*{{{*/
 {
    /* Negative dependencies have no or-group
       If the candidate is effected try to keep current and discard candidate
@@ -1335,7 +1345,7 @@ static bool MarkInstall_RemoveConflictsIfNotUpgradeable(pkgDepCache &Cache, bool
 	    else
 	       badCandidate.push_back(Pkg);
 	 }
-	 else if (not MarkInstall_MarkDeleteForNotUpgradeable(Cache, DebugAutoInstall, PV, Depth, Pkg, propagateProctected))
+	 else if (not MarkInstall_MarkDeleteForNotUpgradeable(Cache, DebugAutoInstall, PV, Depth, Pkg, propagateProctected, delayedRemove))
 	 {
 	    failedToRemoveSomething = true;
 	    if (not propagateProctected && not FromUser)
@@ -1351,7 +1361,9 @@ static bool MarkInstall_RemoveConflictsIfNotUpgradeable(pkgDepCache &Cache, bool
 	 if (State.CandidateVer != Ver && State.CandidateVer != nullptr &&
 	     std::find(badCandidate.cbegin(), badCandidate.cend(), Pkg) == badCandidate.end())
 	    toUpgrade.push_back(Pkg);
-	 else if (not MarkInstall_MarkDeleteForNotUpgradeable(Cache, DebugAutoInstall, PV, Depth, Pkg, propagateProctected))
+	 else if (State.CandidateVer == Pkg.CurrentVer())
+	    ; // already done in the first loop above
+	 else if (not MarkInstall_MarkDeleteForNotUpgradeable(Cache, DebugAutoInstall, PV, Depth, Pkg, propagateProctected, delayedRemove))
 	 {
 	    failedToRemoveSomething = true;
 	    if (not propagateProctected && not FromUser)
@@ -1509,7 +1521,7 @@ bool pkgDepCache::MarkInstall(PkgIterator const &Pkg, bool AutoInst,
 			      unsigned long Depth, bool FromUser,
 			      bool ForceImportantDeps)
 {
-   if (IsModeChangeOk(ModeInstall, Pkg, Depth, FromUser) == false)
+   if (not IsModeChangeOk(*this, ModeInstall, Pkg, Depth, FromUser, DebugMarker))
       return false;
 
    StateCache &P = PkgState[Pkg->ID];
@@ -1544,7 +1556,7 @@ bool pkgDepCache::MarkInstall(PkgIterator const &Pkg, bool AutoInst,
    bool hasFailed = false;
 
    std::vector<pkgCache::DepIterator> toInstall, toRemove;
-   APT::PackageVector toUpgrade;
+   APT::PackageVector toUpgrade, delayedRemove;
    if (AutoSolve)
    {
       VerIterator const PV = P.CandidateVerIter(*this);
@@ -1553,7 +1565,7 @@ bool pkgDepCache::MarkInstall(PkgIterator const &Pkg, bool AutoInst,
       if (not MarkInstall_CollectDependencies(*this, PV, toInstall, toRemove))
 	 return false;
 
-      if (not MarkInstall_RemoveConflictsIfNotUpgradeable(*this, DebugAutoInstall, PV, Depth, toRemove, toUpgrade, P.Protect(), FromUser))
+      if (not MarkInstall_RemoveConflictsIfNotUpgradeable(*this, DebugAutoInstall, PV, Depth, toRemove, toUpgrade, delayedRemove, P.Protect(), FromUser))
       {
 	 if (failEarly)
 	    return false;
@@ -1627,6 +1639,19 @@ bool pkgDepCache::MarkInstall(PkgIterator const &Pkg, bool AutoInst,
       hasFailed = true;
    }
 
+   for (auto const &R : delayedRemove)
+   {
+      if (not MarkDelete(R, false, Depth, false))
+      {
+	 if (failEarly)
+	 {
+	    MarkInstall_DiscardInstall(Pkg);
+	    return false;
+	 }
+	 hasFailed = true;
+      }
+   }
+
    if (MoveAutoBitToDependencies)
    {
       if (DebugAutoInstall)
@@ -2182,7 +2207,7 @@ bool pkgDepCache::MarkRequired(InRootSetFunc &userFunc)
 	 reason = "Required";
       else if (userFunc.InRootSet(P))
 	 reason = "Blacklisted [APT::NeverAutoRemove]";
-      else if (IsModeChangeOk(ModeGarbage, P, 0, false) == false)
+      else if (not IsModeChangeOk(*this, ModeGarbage, P, 0, false, DebugMarker))
 	 reason = "Hold";
       else
 	 continue;
diff --git a/apt-pkg/depcache.h b/apt-pkg/depcache.h
index d9bb69a18..78f88ba2f 100644
--- a/apt-pkg/depcache.h
+++ b/apt-pkg/depcache.h
@@ -518,9 +518,6 @@ class APT_PUBLIC pkgDepCache : protected pkgCache::Namespace
    private:
    void * const d;
 
-   APT_HIDDEN bool IsModeChangeOk(ModeList const mode, PkgIterator const &Pkg,
-			unsigned long const Depth, bool const FromUser);
-
    APT_HIDDEN bool MarkInstall_StateChange(PkgIterator const &Pkg, bool AutoInst, bool FromUser);
    APT_HIDDEN bool MarkInstall_DiscardInstall(PkgIterator const &Pkg);
 
diff --git a/test/integration/test-bug-960705-propagate-protected-to-satisfied-conflict b/test/integration/test-bug-960705-propagate-protected-to-satisfied-conflict
index e793193c3..ad1501b66 100755
--- a/test/integration/test-bug-960705-propagate-protected-to-satisfied-conflict
+++ b/test/integration/test-bug-960705-propagate-protected-to-satisfied-conflict
@@ -17,7 +17,7 @@ setupaptarchive
 
 testsuccessequal "Reading package lists...
 Building dependency tree...
-   Removing: systemd-sysv as upgrade is not an option for runit-init:amd64 (1)
+   Removing: systemd-sysv:amd64 as upgrade is not an option for runit-init:amd64 (1)
     MarkDelete systemd-sysv:amd64 < 1 @ii mK > FU=0
   MarkInstall runit-init:amd64 < none -> 1 @un puN > FU=1
 Starting pkgProblemResolver with broken count: 1
diff --git a/test/integration/test-resolver-delays-remove-decisions b/test/integration/test-resolver-delays-remove-decisions
new file mode 100755
index 000000000..3321ed3a7
--- /dev/null
+++ b/test/integration/test-resolver-delays-remove-decisions
@@ -0,0 +1,74 @@
+#!/bin/sh
+set -e
+
+TESTDIR="$(readlink -f "$(dirname "$0")")"
+. "$TESTDIR/framework"
+setupenvironment
+configarchitecture 'amd64' 'i386'
+
+insertinstalledpackage 'stuff' 'all' '1'
+
+insertpackage 'unstable' 'foobar' 'all' '1' 'Depends: foo | bar'
+insertpackage 'unstable' 'foo' 'all' '1' 'Conflicts: stuff
+Depends: foo-dep'
+insertpackage 'unstable' 'foo-dep' 'all' '1' 'Depends: uninstallable'
+
+insertpackage 'unstable' 'bar' 'all' '1'
+
+setupaptarchive
+
+# We are needlessly removing "stuff" if we don't delay its marking here
+# as we do not question the remove later on
+testsuccessequal "Reading package lists...
+Building dependency tree...
+  MarkInstall foobar:amd64 < none -> 1 @un puN Ib > FU=1
+  Installing foo:amd64 as Depends of foobar:amd64
+     Delayed Removing: stuff:amd64 as upgrade is not an option for foo:amd64 (1)
+    MarkInstall foo:amd64 < none -> 1 @un uN Ib > FU=0
+    Installing foo-dep:amd64 as Depends of foo:amd64
+      foo-dep:amd64 Depends on uninstallable:amd64 < none @un H > can't be satisfied!
+      foo:amd64 Depends on foo-dep:amd64 < none @un H > can't be satisfied! (dep)
+  Installing bar:amd64 as Depends of foobar:amd64
+    MarkInstall bar:amd64 < none -> 1 @un uN > FU=0
+Starting pkgProblemResolver with broken count: 0
+Starting 2 pkgProblemResolver with broken count: 0
+Done
+The following additional packages will be installed:
+  bar
+The following NEW packages will be installed:
+  bar foobar
+0 upgraded, 2 newly installed, 0 to remove and 0 not upgraded.
+Inst bar (1 unstable [all])
+Inst foobar (1 unstable [all])
+Conf bar (1 unstable [all])
+Conf foobar (1 unstable [all])" apt install foobar -s -o Debug::pkgProblemResolver=1 -o Debug::pkgDepCache::Marker=1 -o Debug::pkgDepCache::AutoInstall=1
+
+insertinstalledpackage 'uninstallable' 'all' '1'
+
+testsuccessequal "Reading package lists...
+Building dependency tree...
+  MarkInstall foobar:amd64 < none -> 1 @un puN Ib > FU=1
+  Installing foo:amd64 as Depends of foobar:amd64
+     Delayed Removing: stuff:amd64 as upgrade is not an option for foo:amd64 (1)
+    MarkInstall foo:amd64 < none -> 1 @un uN Ib > FU=0
+    Installing foo-dep:amd64 as Depends of foo:amd64
+      MarkInstall foo-dep:amd64 < none -> 1 @un uN > FU=0
+    MarkDelete stuff:amd64 < 1 @ii mK > FU=0
+Starting pkgProblemResolver with broken count: 0
+Starting 2 pkgProblemResolver with broken count: 0
+Done
+The following additional packages will be installed:
+  foo foo-dep
+The following packages will be REMOVED:
+  stuff
+The following NEW packages will be installed:
+  foo foo-dep foobar
+  MarkDelete stuff:amd64 < 1 @ii K > FU=1
+0 upgraded, 3 newly installed, 1 to remove and 0 not upgraded.
+Remv stuff [1]
+Inst foo-dep (1 unstable [all])
+Inst foo (1 unstable [all])
+Inst foobar (1 unstable [all])
+Conf foo-dep (1 unstable [all])
+Conf foo (1 unstable [all])
+Conf foobar (1 unstable [all])" apt install foobar -s -o Debug::pkgProblemResolver=1 -o Debug::pkgDepCache::Marker=1 -o Debug::pkgDepCache::AutoInstall=1