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). --- test/integration/test-bug-549968-install-depends-of-not-installed | 1 - 1 file changed, 1 deletion(-) (limited to 'test') diff --git a/test/integration/test-bug-549968-install-depends-of-not-installed b/test/integration/test-bug-549968-install-depends-of-not-installed index 7c4e76fd9..6b5e31eea 100755 --- a/test/integration/test-bug-549968-install-depends-of-not-installed +++ b/test/integration/test-bug-549968-install-depends-of-not-installed @@ -37,7 +37,6 @@ Solving dependencies...Install coolstuff:i386 () Delete extracoolstuff:i386 [0] Reject:extracoolstuff:i386 () [0] Install:coolstuff:i386 (coolstuff:i386=1.0) -[0] Reject:extracoolstuff:i386=1.0 (not extracoolstuff:i386) Optional Item (0@0) coolstuff:i386=1.0 -> | extracoolstuff:i386 Optional Item (0@0) coolstuff:i386 -> | extracoolstuff:i386 -- cgit v1.2.3-70-g09d2