solver3: Discover recursive dependencies

When we have discovered all clauses for a version, discover
each possible solution for the clauses. This means that when
Discover(foo) is called _anything_ that could lead to foo becoming
uninstallable is translated; so we can extend this next by keeping
a list of reverse dependencies for each package and rejecting
those.

We limit the discovery to those variables that we did not already
enqueue as a negative fact at the root level, as those can never
become true.

We are utilizing a queue here which is not the most performant
solution possible, but where it excels is in producing usable
stack traces when debugging. Traversing the entire dependency
tree using recursion can easily produce thousand levels of
recursion.

The queue means that we discover packages in a breadth-first
manner compatible with the order in which we propagate dependencies,
which is helpful for consistency.

The queue did not appear as a bottleneck in benchmarking. If it did,
we could switch to a grow-only ring buffer (std::queue's underlying
deque also shrinks automatically which is suboptimal).

2 files changed, 52 insertions, 32 deletions

diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc
index ed781df13..b4a69d844 100644
--- a/apt-pkg/solver3.cc
+++ b/apt-pkg/solver3.cc
@@ -396,51 +396,66 @@ void APT::Solver::RegisterClause(Clause &&clause)
 
 void APT::Solver::Discover(Var var)
 {
-   auto &state = (*this)[var];
-
-   if (state.flags.discovered)
-      return;
-
-   state.flags.discovered = true;
+   assert(discoverQ.empty());
+   discoverQ.push(var);
 
-   if (auto Pkg = var.Pkg(cache); not Pkg.end())
+   while (not discoverQ.empty())
    {
-      Clause clause{Var(Pkg), Group::SelectVersion};
-      for (auto ver = Pkg.VersionList(); not ver.end(); ver++)
-	 clause.solutions.push_back(Var(ver));
+      var = discoverQ.front();
+      discoverQ.pop();
 
-      std::stable_sort(clause.solutions.begin(), clause.solutions.end(), CompareProviders3{cache, policy, Pkg, *this});
-      RegisterClause(std::move(clause));
+      auto &state = (*this)[var];
 
-      RegisterCommonDependencies(Pkg);
-   }
-   else if (auto Ver = var.Ver(cache); not Ver.end())
-   {
-      Clause clause{Var(Ver), Group::SelectVersion};
-      clause.solutions = {Var(Ver.ParentPkg())};
-      RegisterClause(std::move(clause));
+      if (state.flags.discovered)
+	 continue;
+
+      state.flags.discovered = true;
 
-      for (auto OV = Ver.ParentPkg().VersionList(); not OV.end(); ++OV)
+      if (auto Pkg = var.Pkg(cache); not Pkg.end())
       {
-	 if (OV == Ver)
-	    continue;
+	 Clause clause{Var(Pkg), Group::SelectVersion};
+	 for (auto ver = Pkg.VersionList(); not ver.end(); ver++)
+	    clause.solutions.push_back(Var(ver));
 
-	 Clause clause{Var(Ver), Group::SelectVersion, false, true /* negative */};
-	 clause.solutions = {Var(OV)};
+	 std::stable_sort(clause.solutions.begin(), clause.solutions.end(), CompareProviders3{cache, policy, Pkg, *this});
 	 RegisterClause(std::move(clause));
-      }
 
-      for (auto dep = Ver.DependsList(); not dep.end();)
+	 RegisterCommonDependencies(Pkg);
+      }
+      else if (auto Ver = var.Ver(cache); not Ver.end())
       {
-	 // Compute a single dependency element (glob or)
-	 pkgCache::DepIterator start;
-	 pkgCache::DepIterator end;
-	 dep.GlobOr(start, end); // advances dep
+	 Clause clause{Var(Ver), Group::SelectVersion};
+	 clause.solutions = {Var(Ver.ParentPkg())};
+	 RegisterClause(std::move(clause));
 
-	 auto clause = TranslateOrGroup(start, end, Var(Ver));
+	 for (auto OV = Ver.ParentPkg().VersionList(); not OV.end(); ++OV)
+	 {
+	    if (OV == Ver)
+	       continue;
 
-	 RegisterClause(std::move(clause));
+	    Clause clause{Var(Ver), Group::SelectVersion, false, true /* negative */};
+	    clause.solutions = {Var(OV)};
+	    RegisterClause(std::move(clause));
+	 }
+
+	 for (auto dep = Ver.DependsList(); not dep.end();)
+	 {
+	    // Compute a single dependency element (glob or)
+	    pkgCache::DepIterator start;
+	    pkgCache::DepIterator end;
+	    dep.GlobOr(start, end); // advances dep
+
+	    auto clause = TranslateOrGroup(start, end, Var(Ver));
+
+	    RegisterClause(std::move(clause));
+	 }
       }
+
+      // Recursively discover everything else that is not already FALSE by fact (MUSTNOT at depth 0)
+      for (auto const &clause : state.clauses)
+	 for (auto const &var : clause->solutions)
+	    if ((*this)[var].decision != Decision::MUSTNOT || (*this)[var].depth > 0)
+	       discoverQ.push(var);
    }
 }
 
diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h
index e43e1065c..34da03ea0 100644
--- a/apt-pkg/solver3.h
+++ b/apt-pkg/solver3.h
@@ -205,6 +205,8 @@ class Solver
 
    // \brief Propagation queue
    std::queue<Var> propQ;
+   // \brief Discover variables
+   std::queue<Var> discoverQ;
 
    // \brief Current decision level.
    //
@@ -232,6 +234,9 @@ class Solver
    bool DeferVersionSelection{_config->FindB("APT::Solver::Defer-Version-Selection", true)};
 
    // \brief Discover a variable, translating the underlying dependencies to the SAT presentation
+   //
+   // This does a breadth-first search of the entire dependency tree of var,
+   // utilizing the discoverQ above.
    void Discover(Var var);
    // \brief Link a clause into the watchers
    void RegisterClause(Clause &&clause);