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-multiarch-foreign | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'test/integration/test-multiarch-foreign') diff --git a/test/integration/test-multiarch-foreign b/test/integration/test-multiarch-foreign index 228fa8895..b356c64c7 100755 --- a/test/integration/test-multiarch-foreign +++ b/test/integration/test-multiarch-foreign @@ -179,7 +179,7 @@ distribution that some required packages have not yet been created or been moved out of Incoming. The following information may help to resolve the situation: ' - testfailuremsg "E: Conflict: -> ${1%:*}:$4=1.0 but hates-foo:amd64=1.0 -> not ${1%:*}:$4=1.0" aptget install $1 hates-foo -s --solver 3.0 + testfailuremsg "E: Conflict: hates-foo:amd64=1.0 -> not ${1%:*}:$4=1.0 but ${1%:*}:$4=1.0" aptget install $1 hates-foo -s --solver 3.0 testfailureequal "$BADPREFIX The following packages have unmet dependencies: hates-foo : Conflicts: foo -- cgit v1.2.3-70-g09d2