From 222271ee0d44c8e7bc00935fbbc2615529a4cdfc Mon Sep 17 00:00:00 2001 From: Julian Andres Klode 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.h | 5 +++++ 1 file changed, 5 insertions(+) (limited to 'apt-pkg/solver3.h') 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 propQ; + // \brief Discover variables + std::queue 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); -- cgit v1.2.3-70-g09d2