From 3523efb15d48ce3c6f9212f50dfc892497ba9dcb Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Sat, 2 Nov 2024 13:55:39 +0100 Subject: solver3: Use a propagation queue Instead of directly propagating in a recursive fashion, queue propagations in a queue and work on them in a loop per the miniSAT paper. We call Propagate() only at the end of the FromDepCache() function and then in the Solve loop. Delaying the initial propagation means that we get a stronger reasoning: Assume you have x->a->b->c, y->c and you install x,y: - Previously we traversed: x, y, x->a, a->b, b->c, (y->c) - but now we traverse: x, y, x->a, y->c, a->b, (b->c) Notably c now has the implication y->c instead of x->a->b->c. Inside the solver we need to call Propagate in a loop: Propagating facts can fail and we then backtrack. If backtracking is succesful, we have gained a new fact to propagate. --- test/integration/test-apt-never-markauto-sections | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'test/integration/test-apt-never-markauto-sections') diff --git a/test/integration/test-apt-never-markauto-sections b/test/integration/test-apt-never-markauto-sections index 85412b17b..33b790871 100755 --- a/test/integration/test-apt-never-markauto-sections +++ b/test/integration/test-apt-never-markauto-sections @@ -49,7 +49,7 @@ Remv foreignpkg:i386 [1] Remv nosection [1] Remv texteditor [1]' aptget autoremove mydesktop -s -testfailuremsg 'E: Conflict: not texteditor:amd64 -> not texteditor:amd64=1 -> not bad-texteditor:amd64=1 -> not mydesktop-core:amd64=1 but mydesktop:amd64 -> mydesktop:amd64=1 -> mydesktop-core:amd64=1' aptget autoremove texteditor -s --solver 3.0 #-o Debug::pkgDepCache::AutoInstall=1 -o Debug::pkgProblemResolver=1 -o Debug::pkgDepCache::Marker=1 +testfailuremsg 'E: Conflict: not texteditor:amd64 -> not texteditor:amd64=1 -> not mydesktop-core:amd64=1 but mydesktop:amd64 -> mydesktop-core:amd64=1' aptget autoremove texteditor -s --solver 3.0 #-o Debug::pkgDepCache::AutoInstall=1 -o Debug::pkgProblemResolver=1 -o Debug::pkgDepCache::Marker=1 testsuccessequal 'Reading package lists... Building dependency tree... Reading state information... -- cgit v1.2.3-70-g09d2