From 222271ee0d44c8e7bc00935fbbc2615529a4cdfc Mon Sep 17 00:00:00 2001
From: Julian Andres Klode <julian.klode@canonical.com>
Date: Mon, 10 Feb 2025 17:17:35 +0100
Subject: 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).
---
 apt-pkg/solver3.cc | 79 ++++++++++++++++++++++++++++++++----------------------
 1 file changed, 47 insertions(+), 32 deletions(-)

(limited to 'apt-pkg/solver3.cc')

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);
    }
 }
 
-- 
cgit v1.2.3-70-g09d2