Propagate protected to already satisfied dependencies

The previous commit deals with negative, now we add the positive side of
things as well which makes this a recursive endevour. As we can push the
protected flag forward only if a single solution for a dependency exists
it is easy for trees to not get it, so if resolving becomes difficult it
won't help at all.

3 files changed, 89 insertions, 46 deletions

diff --git a/apt-pkg/depcache.cc b/apt-pkg/depcache.cc
index a36b1865e..842630ec6 100644
--- a/apt-pkg/depcache.cc
+++ b/apt-pkg/depcache.cc
@@ -1074,6 +1074,9 @@ struct CompareProviders							/*{{{*/
 bool pkgDepCache::MarkInstall_StateChange(pkgCache::PkgIterator const &Pkg, bool AutoInst, bool FromUser) /*{{{*/
 {
    auto &P = (*this)[Pkg];
+   if (P.Protect() && P.InstallVer == P.CandidateVer)
+      return true;
+
    P.iFlags &= ~pkgDepCache::AutoKept;
 
    /* Target the candidate version and remove the autoflag. We reset the
@@ -1141,7 +1144,7 @@ static bool MarkInstall_CollectDependencies(pkgDepCache const &Cache, pkgCache::
 	 if ((Cache[Dep] & pkgDepCache::DepInstall) == pkgDepCache::DepInstall)
 	    foundSolution = true;
       }
-      if (foundSolution && (not propagateProctected || not Start.IsNegative()))
+      if (foundSolution && not propagateProctected)
 	 continue;
 
       /* Check if this dep should be consider for install.
@@ -1290,9 +1293,26 @@ static bool MarkInstall_InstallDependencies(pkgDepCache &Cache, bool const Debug
       auto const Copy = Dep;
       pkgCache::DepIterator Start, End;
       Dep.GlobOr(Start, End);
-      if (std::any_of(Start, Dep, IsSatisfiedByInstalled))
+      bool foundSolution = std::any_of(Start, Dep, IsSatisfiedByInstalled);
+      if (foundSolution && not propagateProctected)
 	 continue;
       bool const IsCriticalDep = Start.IsCritical();
+      if (foundSolution)
+      {
+	 // try propagating protected to this satisfied dependency
+	 if (not IsCriticalDep)
+	    continue;
+	 auto const possibleSolutions = getAllPossibleSolutions(Cache, Start, End, APT::CacheSetHelper::CANDANDINST, false);
+	 if (possibleSolutions.size() != 1)
+	    continue;
+	 auto const InstPkg = possibleSolutions.begin().ParentPkg();
+	 if (Cache[InstPkg].Protect())
+	    continue;
+	 Cache.MarkProtected(InstPkg);
+	 if (not Cache.MarkInstall(InstPkg, true, Depth + 1, false, ForceImportantDeps))
+	    failedToInstallSomething = true;
+	 continue;
+      }
 
       /* Check if any ImportantDep() (but not Critical) were added
        * since we installed the package.  Also check for deps that
@@ -1345,35 +1365,16 @@ static bool MarkInstall_InstallDependencies(pkgDepCache &Cache, bool const Debug
 	 }
       }
 
-      pkgCacheFile CacheFile{&Cache};
-      APT::PackageVector toUpgrade, toNewInstall;
-      do
-      {
-	 if ((Cache[Start] & pkgDepCache::DepCVer) != pkgDepCache::DepCVer)
-	    continue;
-
-	 APT::VersionVector verlist = APT::VersionVector::FromDependency(CacheFile, Start, APT::CacheSetHelper::CANDIDATE);
-	 std::sort(verlist.begin(), verlist.end(), CompareProviders{Cache, Start});
-	 for (auto const &Ver : verlist)
-	 {
-	    auto P = Ver.ParentPkg();
-	    if (P->CurrentVer != 0)
-	       toUpgrade.emplace_back(std::move(P));
-	    else
-	       toNewInstall.emplace_back(std::move(P));
-	 }
-      } while (Start++ != End);
-
-      std::move(toNewInstall.begin(), toNewInstall.end(), std::back_inserter(toUpgrade));
-      bool foundSolution = false;
-      for (auto const &InstPkg : toUpgrade)
+      auto const possibleSolutions = getAllPossibleSolutions(Cache, Start, End, APT::CacheSetHelper::CANDIDATE, true);
+      for (auto const &InstVer : possibleSolutions)
       {
+	 auto const InstPkg = InstVer.ParentPkg();
 	 if (Cache[InstPkg].CandidateVer == nullptr || Cache[InstPkg].CandidateVer == InstPkg.CurrentVer())
 	    continue;
 	 if (DebugAutoInstall)
 	    std::clog << OutputInDepth(Depth) << "Installing " << InstPkg.FullName()
 		      << " as " << End.DepType() << " of " << Pkg.FullName() << '\n';
-	 if (propagateProctected && IsCriticalDep && toUpgrade.size() == 1)
+	 if (propagateProctected && IsCriticalDep && possibleSolutions.size() == 1)
 	 {
 	    if (not Cache.MarkInstall(InstPkg, false, Depth + 1, false, ForceImportantDeps))
 	       continue;
@@ -1415,15 +1416,17 @@ bool pkgDepCache::MarkInstall(PkgIterator const &Pkg, bool AutoInst,
    if (P.CandidateVer == 0)
       return false;
 
-   /* Check that it is not already marked for install and that it can be 
-      installed */
-   if ((not P.InstPolicyBroken() && not P.InstBroken()) &&
-       (P.Mode == ModeInstall ||
-	P.CandidateVer == (Version *)Pkg.CurrentVer()))
+   // Check that it is not already marked for install and that it can be installed
+   if (not P.Protect() && not P.InstPolicyBroken() && not P.InstBroken())
    {
-      if (P.CandidateVer == (Version *)Pkg.CurrentVer() && P.InstallVer == 0)
-	 return MarkKeep(Pkg, false, FromUser, Depth + 1);
-      return true;
+      if (P.CandidateVer == Pkg.CurrentVer())
+      {
+	 if (P.InstallVer == 0)
+	    return MarkKeep(Pkg, false, FromUser, Depth + 1);
+	 return true;
+      }
+      else if (P.Mode == ModeInstall)
+	 return true;
    }
 
    // check if we are allowed to install the package
diff --git a/test/integration/test-bug-604222-new-and-autoremove b/test/integration/test-bug-604222-new-and-autoremove
index 6009ca0d2..aaeac09a8 100755
--- a/test/integration/test-bug-604222-new-and-autoremove
+++ b/test/integration/test-bug-604222-new-and-autoremove
@@ -59,12 +59,10 @@ The following package was automatically installed and is no longer required:
   libvtk5.4
 Use '$AUTOREMOVE' to remove it.
 The following additional packages will be installed:
-  libavcodec52 libopenal-dev libvtk5.4
+  libavcodec52 libopenal-dev
 The following NEW packages will be installed:
   dummy-archive libavcodec52 libopenal-dev
-The following packages will be upgraded:
-  libvtk5.4
-1 upgraded, 3 newly installed, 0 to remove and 0 not upgraded.
+0 upgraded, 3 newly installed, 0 to remove and 1 not upgraded.
 After this operation, 129 kB of additional disk space will be used.
 E: Trivial Only specified but this is not a trivial operation." aptget install dummy-archive --trivial-only
 testequal "Reading package lists...
@@ -73,12 +71,10 @@ Reading state information...
 1 package was automatically installed and is no longer required.
 Use '$AUTOREMOVE' to remove it.
 The following additional packages will be installed:
-  libavcodec52 libopenal-dev libvtk5.4
+  libavcodec52 libopenal-dev
 The following NEW packages will be installed:
   dummy-archive libavcodec52 libopenal-dev
-The following packages will be upgraded:
-  libvtk5.4
-1 upgraded, 3 newly installed, 0 to remove and 0 not upgraded.
+0 upgraded, 3 newly installed, 0 to remove and 1 not upgraded.
 After this operation, 129 kB of additional disk space will be used.
 E: Trivial Only specified but this is not a trivial operation." aptget install dummy-archive --trivial-only -o APT::Get::HideAutoRemove=small
 
@@ -88,12 +84,11 @@ rm -f rootdir/var/lib/apt/extended_states
 CONFLICTING='Reading package lists...
 Building dependency tree...
   MarkInstall dummy-archive:i386 < none -> 0.invalid.0 @un puN Ib > FU=1
-    MarkInstall libvtk5-dev:i386 < none -> 5.4.2-8 @un uN Ib > FU=0
-      MarkInstall libvtk5.4:i386 < none -> 5.4.2-8 @un uN > FU=0
-  MarkKeep libvtk5-dev:i386 < none -> 5.4.2-8 @un uN > FU=0
-  MarkKeep libvtk5-dev:i386 < none -> 5.4.2-8 @un uN > FU=0
+    MarkInstall libavcodec52:i386 < none -> 4:0.5.2-6 @un puN > FU=0
+    MarkInstall libopenal-dev:i386 < none -> 1:1.12.854-2 @un puN > FU=0
+  Ignore MarkGarbage of libopenal-dev:i386 < none -> 1:1.12.854-2 @un puN > as its mode (Install) is protected
   Ignore MarkGarbage of libavcodec52:i386 < none -> 4:0.5.2-6 @un puN > as its mode (Install) is protected
-  MarkDelete libvtk5.4:i386 < none -> 5.4.2-8 @un ugN > FU=0
+  Ignore MarkGarbage of libopenal-dev:i386 < none -> 1:1.12.854-2 @un puN > as its mode (Install) is protected
   Ignore MarkGarbage of libavcodec52:i386 < none -> 4:0.5.2-6 @un puN > as its mode (Install) is protected
 The following additional packages will be installed:
   libavcodec52 libopenal-dev
diff --git a/test/integration/test-bug-960705-propagate-protected-to-satisfied-depends b/test/integration/test-bug-960705-propagate-protected-to-satisfied-depends
new file mode 100755
index 000000000..ca6bf8d7c
--- /dev/null
+++ b/test/integration/test-bug-960705-propagate-protected-to-satisfied-depends
@@ -0,0 +1,45 @@
+#!/bin/sh
+set -e
+
+TESTDIR="$(readlink -f "$(dirname "$0")")"
+. "$TESTDIR/framework"
+setupenvironment
+configarchitecture 'amd64'
+
+# without requires-foo it is sadly not as clear cut what should happen
+insertpackage 'unstable' 'foobar' 'all' '1' 'Depends: foo | bar, requires-foo, conflicts-foo | fine-foo'
+insertpackage 'unstable' 'foo' 'all' '1' 'Depends: foo-depends'
+insertpackage 'unstable' 'foo-depends' 'all' '1'
+insertpackage 'unstable' 'bar' 'all' '1'
+insertpackage 'unstable' 'requires-foo' 'all' '1' 'Depends: foo'
+insertpackage 'unstable' 'conflicts-foo' 'all' '1' 'Conflicts: foo'
+insertpackage 'unstable' 'fine-foo' 'all' '1'
+
+
+setupaptarchive
+
+testsuccessequal "Reading package lists...
+Building dependency tree...
+  Installing foo:amd64 as Depends of foobar:amd64
+    Installing foo-depends:amd64 as Depends of foo:amd64
+  Installing requires-foo:amd64 as Depends of foobar:amd64
+  Installing conflicts-foo:amd64 as Depends of foobar:amd64
+  Installing fine-foo:amd64 as Depends of foobar:amd64
+Starting pkgProblemResolver with broken count: 0
+Starting 2 pkgProblemResolver with broken count: 0
+Done
+The following additional packages will be installed:
+  fine-foo foo foo-depends requires-foo
+The following NEW packages will be installed:
+  fine-foo foo foo-depends foobar requires-foo
+0 upgraded, 5 newly installed, 0 to remove and 0 not upgraded.
+Inst fine-foo (1 unstable [all])
+Inst foo-depends (1 unstable [all])
+Inst foo (1 unstable [all])
+Inst requires-foo (1 unstable [all])
+Inst foobar (1 unstable [all])
+Conf fine-foo (1 unstable [all])
+Conf foo-depends (1 unstable [all])
+Conf foo (1 unstable [all])
+Conf requires-foo (1 unstable [all])
+Conf foobar (1 unstable [all])" apt install foobar -so Debug::pkgProblemResolver=1 -o Debug::pkgDepCache::AutoInstall=1