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.

1 files changed, 82 insertions, 78 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");
    }
 }
 									/*}}}*/