Reexplore providers of marked packages if some didn't satisfy before

The autoremove algorithm would mark a package previously after exploring
it once, but it could have been that it ignored some providers due to
them not satisfying the (versioned) dependency. A later dependency which
they might satisfy would encounter the package as already marked and
hence doesn't explore the providers anymore leaving us with internal
errors (as in the contrived new testcase).

This is resolved by introducing a new flag denoting if we explored every
provider already and only skip exploring if that is true, which sounds
bad but is really not such a common occurrence that it seems noticeable
in practice. It also helps us marking virtual packages as explored now
which would previously be tried each time they are encountered mostly
hiding this problem for the (far more common) fully virtual package.

4 files changed, 117 insertions, 81 deletions

diff --git a/apt-pkg/depcache.cc b/apt-pkg/depcache.cc
index 398216f82..13beeb713 100644
--- a/apt-pkg/depcache.cc
+++ b/apt-pkg/depcache.cc
@@ -121,6 +121,7 @@ pkgDepCache::ActionGroup::~ActionGroup()
 struct pkgDepCache::Private
 {
    std::unique_ptr<InRootSetFunc> inRootSetFunc;
+   std::vector<bool> fullyExplored;
 };
 pkgDepCache::pkgDepCache(pkgCache *const pCache, Policy *const Plcy) : group_level(0), Cache(pCache), PkgState(0), DepState(0),
 								       iUsrSize(0), iDownloadSize(0), iInstCount(0), iDelCount(0), iKeepCount(0),
@@ -2234,6 +2235,7 @@ bool pkgDepCache::MarkRequired(InRootSetFunc &userFunc)
       PkgState[i].Marked  = false;
       PkgState[i].Garbage = false;
    }
+   d->fullyExplored = std::vector<bool>(PackagesCount, false);
    if (debug_autoremove)
       for(PkgIterator p = PkgBegin(); !p.end(); ++p)
 	 if(PkgState[p->ID].Flags & Flag::Auto)
@@ -2272,7 +2274,7 @@ bool pkgDepCache::MarkRequired(InRootSetFunc &userFunc)
 	 MarkPackage(P, P.CurrentVer(),
 	       follow_recommends, follow_suggests, reason);
    }
-
+   d->fullyExplored.clear();
    return true;
 }
 									/*}}}*/
@@ -2283,28 +2285,33 @@ void pkgDepCache::MarkPackage(const pkgCache::PkgIterator &Pkg,
 			      bool const &follow_suggests,
 			      const char *reason)
 {
-   {
-      pkgDepCache::StateCache &state = PkgState[Pkg->ID];
-      // if we are marked already we are done
-      if(state.Marked || unlikely(Ver.end()))
-	 return;
-      state.Marked=true;
-   }
+   if (Ver.end() || (d->fullyExplored[Pkg->ID] && PkgState[Pkg->ID].Marked))
+      return;
 
    if (IsPkgInBoringState(Pkg, PkgState))
+   {
+      d->fullyExplored[Pkg->ID] = true;
       return;
+   }
 
+   PkgState[Pkg->ID].Marked = true;
    bool const debug_autoremove = _config->FindB("Debug::pkgAutoRemove", false);
    if(debug_autoremove)
       std::clog << "Marking: " << Pkg.FullName() << " " << Ver.VerStr()
 		<< " (" << reason << ")" << std::endl;
 
    std::unique_ptr<APT::CacheFilter::Matcher> IsAVersionedKernelPackage, IsProtectedKernelPackage;
-
-   for (auto D = Ver.DependsList(); D.end() == false; ++D)
+   auto const sort_by_source_version = [](pkgCache::VerIterator const &A, pkgCache::VerIterator const &B) {
+      auto const verret = A.Cache()->VS->CmpVersion(A.SourceVerStr(), B.SourceVerStr());
+      if (verret != 0)
+	 return verret > 0;
+      return A->ID < B->ID;
+   };
+
+   for (auto D = Ver.DependsList(); not D.end(); ++D)
    {
       auto const T = D.TargetPkg();
-      if (PkgState[T->ID].Marked)
+      if (T.end() || d->fullyExplored[T->ID])
 	 continue;
 
       if (D->Type != Dep::Depends &&
@@ -2313,91 +2320,88 @@ void pkgDepCache::MarkPackage(const pkgCache::PkgIterator &Pkg,
 	    (follow_suggests == false || D->Type != Dep::Suggests))
 	 continue;
 
-      // handle the virtual part first
+      bool unsatisfied_choice = false;
       std::unordered_map<std::string, APT::VersionVector> providers_by_source;
-      for(auto Prv = T.ProvidesList(); Prv.end() == false; ++Prv)
+      // collect real part
+      if (not IsPkgInBoringState(T, PkgState))
       {
-	 auto PP = Prv.OwnerPkg();
+	 auto const TV = (PkgState[T->ID].Install()) ? PkgState[T->ID].InstVerIter(*this) : T.CurrentVer();
+	 if (likely(not TV.end()))
+	 {
+	    if (not D.IsSatisfied(TV))
+	       unsatisfied_choice = true;
+	    else
+	       providers_by_source[TV.SourcePkgName()].push_back(TV);
+	 }
+      }
+      if (providers_by_source.empty() && not unsatisfied_choice)
+	 PkgState[T->ID].Marked = true;
+      // collect virtual part
+      for (auto Prv = T.ProvidesList(); not Prv.end(); ++Prv)
+      {
+	 auto const PP = Prv.OwnerPkg();
 	 if (IsPkgInBoringState(PP, PkgState))
 	    continue;
 
 	 // we want to ignore provides from uninteresting versions
 	 auto const PV = (PkgState[PP->ID].Install()) ?
 	    PkgState[PP->ID].InstVerIter(*this) : PP.CurrentVer();
-	 if (unlikely(PV.end()) || PV != Prv.OwnerVer() || D.IsSatisfied(Prv) == false)
+	 if (unlikely(PV.end()) || PV != Prv.OwnerVer())
 	    continue;
 
-	 providers_by_source[PV.SourcePkgName()].push_back(PV);
+	 if (not D.IsSatisfied(Prv))
+	    unsatisfied_choice = true;
+	 else
+	    providers_by_source[PV.SourcePkgName()].push_back(PV);
       }
-      if (providers_by_source.empty() == false)
+      // only latest binary package of a source package is marked instead of all
+      for (auto &providers : providers_by_source)
       {
-	 // sort providers by source version so that only the latest versioned
-	 // binary package of a source package is marked instead of all
-	 auto const sort_by_version = [](pkgCache::VerIterator const &A, pkgCache::VerIterator const &B) {
-	    auto const verret = A.Cache()->VS->CmpVersion(A.SourceVerStr(), B.SourceVerStr());
-	    if (verret != 0)
-	       return verret > 0;
-	    return A->ID < B->ID;
-	 };
-	 for (auto &providers : providers_by_source)
-	 {
-	    std::sort(providers.second.begin(), providers.second.end(), sort_by_version);
-	    auto const highestSrcVer = (*providers.second.begin()).SourceVerStr();
-	    auto notThisVer = std::find_if_not(providers.second.begin(), providers.second.end(), [&](auto const &V) { return strcmp(highestSrcVer, V.SourceVerStr()) == 0; });
-	    if (notThisVer != providers.second.end())
-	       providers.second.erase(notThisVer, providers.second.end());
-	    // if the provider is a versioned kernel package mark them only for protected kernels
-	    if (providers.second.size() == 1)
-	       continue;
-	    if (not IsAVersionedKernelPackage)
-	       IsAVersionedKernelPackage = [&]() -> std::unique_ptr<APT::CacheFilter::Matcher> {
-		  auto const patterns = _config->FindVector("APT::VersionedKernelPackages");
-		  if (patterns.empty())
-		     return std::make_unique<APT::CacheFilter::FalseMatcher>();
-		  std::ostringstream regex;
-		  regex << '^';
-		  std::copy(patterns.begin(), patterns.end() - 1, std::ostream_iterator<std::string>(regex, "-.*$|^"));
-		  regex << patterns.back() << "-.*$";
-		  return std::make_unique<APT::CacheFilter::PackageNameMatchesRegEx>(regex.str());
-	       }();
-	    if (not std::all_of(providers.second.begin(), providers.second.end(), [&](auto const &Prv) { return (*IsAVersionedKernelPackage)(Prv.ParentPkg()); }))
-	       continue;
-	    // … if there is at least one for protected kernels installed
-	    if (not IsProtectedKernelPackage)
-	       IsProtectedKernelPackage = APT::KernelAutoRemoveHelper::GetProtectedKernelsFilter(Cache);
-	    if (not std::any_of(providers.second.begin(), providers.second.end(), [&](auto const &Prv) { return (*IsProtectedKernelPackage)(Prv.ParentPkg()); }))
-	       continue;
-	    providers.second.erase(std::remove_if(providers.second.begin(), providers.second.end(),
+	 std::sort(providers.second.begin(), providers.second.end(), sort_by_source_version);
+	 auto const highestSrcVer = (*providers.second.begin()).SourceVerStr();
+	 auto notThisVer = std::find_if_not(providers.second.begin(), providers.second.end(), [&](auto const &V) { return strcmp(highestSrcVer, V.SourceVerStr()) == 0; });
+	 if (notThisVer != providers.second.end())
+	    providers.second.erase(notThisVer, providers.second.end());
+	 // if the provider is a versioned kernel package mark them only for protected kernels
+	 if (providers.second.size() == 1)
+	    continue;
+	 if (not IsAVersionedKernelPackage)
+	    IsAVersionedKernelPackage = [&]() -> std::unique_ptr<APT::CacheFilter::Matcher> {
+	       auto const patterns = _config->FindVector("APT::VersionedKernelPackages");
+	       if (patterns.empty())
+		  return std::make_unique<APT::CacheFilter::FalseMatcher>();
+	       std::ostringstream regex;
+	       regex << '^';
+	       std::copy(patterns.begin(), patterns.end() - 1, std::ostream_iterator<std::string>(regex, "-.*$|^"));
+	       regex << patterns.back() << "-.*$";
+	       return std::make_unique<APT::CacheFilter::PackageNameMatchesRegEx>(regex.str());
+	    }();
+	 if (not std::all_of(providers.second.begin(), providers.second.end(), [&](auto const &Prv) { return (*IsAVersionedKernelPackage)(Prv.ParentPkg()); }))
+	    continue;
+	 // … if there is at least one for protected kernels installed
+	 if (not IsProtectedKernelPackage)
+	    IsProtectedKernelPackage = APT::KernelAutoRemoveHelper::GetProtectedKernelsFilter(Cache);
+	 if (not std::any_of(providers.second.begin(), providers.second.end(), [&](auto const &Prv) { return (*IsProtectedKernelPackage)(Prv.ParentPkg()); }))
+	    continue;
+	 providers.second.erase(std::remove_if(providers.second.begin(), providers.second.end(),
 					       [&](auto const &Prv) { return not((*IsProtectedKernelPackage)(Prv.ParentPkg())); }),
 				providers.second.end());
-	 }
+      }
 
-	 for (auto const &providers : providers_by_source)
+      if (not unsatisfied_choice)
+	 d->fullyExplored[T->ID] = true;
+      for (auto const &providers : providers_by_source)
+      {
+	 for (auto const &PV : providers.second)
 	 {
-	    for (auto const &PV : providers.second)
-	    {
-	       auto const PP = PV.ParentPkg();
-	       if (debug_autoremove)
-		  std::clog << "Following dep: " << APT::PrettyDep(this, D)
-			    << ", provided by " << PP.FullName() << " " << PV.VerStr()
-			    << " (" << providers_by_source.size() << "/" << providers.second.size() << ")\n";
-	       MarkPackage(PP, PV, follow_recommends, follow_suggests, "Provider");
-	    }
+	    auto const PP = PV.ParentPkg();
+	    if (debug_autoremove)
+	       std::clog << "Following dep: " << APT::PrettyDep(this, D)
+			 << ", provided by " << PP.FullName() << " " << PV.VerStr()
+			 << " (" << providers_by_source.size() << "/" << providers.second.size() << ")\n";
+	    MarkPackage(PP, PV, follow_recommends, follow_suggests, "Dependency");
 	 }
       }
-
-      // now deal with the real part of the package
-      if (IsPkgInBoringState(T, PkgState))
-	 continue;
-
-      auto const TV = (PkgState[T->ID].Install()) ?
-	 PkgState[T->ID].InstVerIter(*this) : T.CurrentVer();
-      if (unlikely(TV.end()) || D.IsSatisfied(TV) == false)
-	 continue;
-
-      if (debug_autoremove)
-	 std::clog << "Following dep: " << APT::PrettyDep(this, D) << std::endl;
-      MarkPackage(T, TV, follow_recommends, follow_suggests, "Dependency");
    }
 }
 									/*}}}*/
diff --git a/test/integration/test-apt-get-autoremove-real-virtual-provider b/test/integration/test-apt-get-autoremove-real-virtual-provider
new file mode 100755
index 000000000..4940ab5ff
--- /dev/null
+++ b/test/integration/test-apt-get-autoremove-real-virtual-provider
@@ -0,0 +1,32 @@
+#!/bin/sh
+set -e
+
+TESTDIR="$(readlink -f "$(dirname "$0")")"
+. "$TESTDIR/framework"
+setupenvironment
+configarchitecture 'amd64'
+
+insertinstalledpackage 'needs' 'all' '1'
+insertinstalledpackage 'needs-provider1' 'all' '1' 'Provides: needs (= 1)'
+insertinstalledpackage 'needs-provider2' 'all' '1' 'Provides: needs (= 2)'
+insertinstalledpackage 'needs-provider3' 'all' '1' 'Provides: needs (= 3)'
+insertinstalledpackage 'needs-provider4' 'all' '1' 'Provides: needs (= 4)'
+
+insertinstalledpackage 'foo' 'all' '1' 'Depends: needs (= 1), needs (= 2), needs (= 3)'
+
+testsuccess aptmark auto 'needs*'
+testsuccessequal 'needs
+needs-provider1
+needs-provider2
+needs-provider3
+needs-provider4' aptmark showauto
+
+testsuccess aptget check -s
+
+testsuccessequal 'Reading package lists...
+Building dependency tree...
+Reading state information...
+The following packages will be REMOVED:
+  needs-provider4
+0 upgraded, 0 newly installed, 1 to remove and 0 not upgraded.
+Remv needs-provider4 [1]' aptget autoremove -s
diff --git a/test/integration/test-bug-618848-always-respect-user-requests b/test/integration/test-bug-618848-always-respect-user-requests
index 1e144f1ee..225db299c 100755
--- a/test/integration/test-bug-618848-always-respect-user-requests
+++ b/test/integration/test-bug-618848-always-respect-user-requests
@@ -17,7 +17,7 @@ testsuccessequal "Reading package lists...
 Building dependency tree...
   MarkDelete libdb4.8:i386 < 1.0 @ii pmK > FU=1
   MarkDelete exim4-daemon-light:i386 < 1.0 @ii mK Ib > FU=0
-    MarkInstall exim4-daemon-heavy:i386 < none -> 1.0 @un uN Ib > FU=0
+    MarkInstall exim4-daemon-heavy:i386 < none -> 1.0 @un umN Ib > FU=0
       exim4-daemon-heavy:i386 Depends on libdb4.8:i386 < 1.0 @ii pmR > can't be satisfied! (dep)
   MarkDelete exim4:i386 < 1.0 @ii mK Ib > FU=0
 The following packages will be REMOVED:
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 ad1501b66..54781a6cc 100755
--- a/test/integration/test-bug-960705-propagate-protected-to-satisfied-conflict
+++ b/test/integration/test-bug-960705-propagate-protected-to-satisfied-conflict
@@ -26,13 +26,13 @@ Investigating (0) init:amd64 < 1 @ii mK Ib >
 Broken init:amd64 PreDepends on systemd-sysv:amd64 < 1 @ii pmR >
   Considering systemd-sysv:amd64 0 as a solution to init:amd64 5100
   Added systemd-sysv:amd64 to the remove list
-Broken init:amd64 PreDepends on sysvinit-core:amd64 < none @un pH >
+Broken init:amd64 PreDepends on sysvinit-core:amd64 < none @un pmH >
   Considering sysvinit-core:amd64 0 as a solution to init:amd64 5100
   Ignore MarkKeep of systemd-sysv:amd64 < 1 @ii pmR > as its mode (Delete) is protected
 Investigating (1) init:amd64 < 1 @ii mK Ib >
 Broken init:amd64 PreDepends on systemd-sysv:amd64 < 1 @ii pmR >
   Considering systemd-sysv:amd64 5100 as a solution to init:amd64 5100
-Broken init:amd64 PreDepends on sysvinit-core:amd64 < none @un pH >
+Broken init:amd64 PreDepends on sysvinit-core:amd64 < none @un pmH >
   Considering sysvinit-core:amd64 0 as a solution to init:amd64 5100
   Or group remove for init:amd64
   MarkDelete init:amd64 < 1 @ii mK Ib > FU=0