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-get-install-deb | 2 +- test/integration/test-apt-never-markauto-sections | 2 +- .../test-bug-549968-install-depends-of-not-installed | 2 +- .../test-bug-598669-install-postfix-gets-exim-heavy | 2 +- test/integration/test-bug-601961-install-info | 2 +- test/integration/test-bug-612557-garbage-upgrade | 2 +- .../integration/test-bug-618848-always-respect-user-requests | 2 +- test/integration/test-dpkg-i-apt-install-fix-broken | 8 ++++---- test/integration/test-ignore-provides-if-versioned-breaks | 12 +++--------- test/integration/test-ignore-provides-if-versioned-conflicts | 12 +++--------- test/integration/test-multiarch-allowed | 6 +++--- test/integration/test-multiarch-foreign | 2 +- 12 files changed, 21 insertions(+), 33 deletions(-) (limited to 'test') diff --git a/test/integration/test-apt-get-install-deb b/test/integration/test-apt-get-install-deb index 6cbd25c9f..5599586fd 100755 --- a/test/integration/test-apt-get-install-deb +++ b/test/integration/test-apt-get-install-deb @@ -32,7 +32,7 @@ done buildsimplenativepackage 'foo' 'i386,amd64' '1.0' -testfailuremsg "E: Conflict: -> foo:amd64=1.0 but foo:i386=1.0 -> not foo:amd64=1.0" aptget install ./incoming/foo_1.0_i386.deb ./incoming/foo_1.0_amd64.deb -s --solver 3.0 +testfailuremsg "E: Conflict: foo:i386=1.0 -> not foo:amd64=1.0 but foo:amd64=1.0" aptget install ./incoming/foo_1.0_i386.deb ./incoming/foo_1.0_amd64.deb -s --solver 3.0 testfailureequal "Reading package lists... Building dependency tree... Note, selecting 'foo:i386' instead of './incoming/foo_1.0_i386.deb' 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... 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 76219290a..33cbd6ee4 100755 --- a/test/integration/test-bug-549968-install-depends-of-not-installed +++ b/test/integration/test-bug-549968-install-depends-of-not-installed @@ -34,9 +34,9 @@ Building dependency tree... Package 'extracoolstuff' is not installed, so not removed Solving dependencies...Install coolstuff:i386 () [0] Install:coolstuff:i386=1.0 () -[0] Install:coolstuff:i386 (coolstuff:i386=1.0) 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=1.0 diff --git a/test/integration/test-bug-598669-install-postfix-gets-exim-heavy b/test/integration/test-bug-598669-install-postfix-gets-exim-heavy index e27ddb2db..d721bdaa8 100755 --- a/test/integration/test-bug-598669-install-postfix-gets-exim-heavy +++ b/test/integration/test-bug-598669-install-postfix-gets-exim-heavy @@ -7,7 +7,7 @@ setupenvironment configarchitecture "i386" setupaptarchive -testfailuremsg "E: Conflict: -> postfix:i386=2.7.1-1 but exim4-daemon-light:i386 -> exim4-daemon-light:i386=4.72-1 -> not postfix:i386=2.7.1-1" aptget install postfix --solver 3.0 +testfailuremsg "E: Conflict: exim4-daemon-light:i386 -> exim4-daemon-light:i386=4.72-1 -> not postfix:i386=2.7.1-1 but postfix:i386=2.7.1-1" aptget install postfix --solver 3.0 allowremovemanual testfailureequal "Reading package lists... Building dependency tree... diff --git a/test/integration/test-bug-601961-install-info b/test/integration/test-bug-601961-install-info index 94a5ad2cf..809ebf3c3 100755 --- a/test/integration/test-bug-601961-install-info +++ b/test/integration/test-bug-601961-install-info @@ -60,4 +60,4 @@ The following information may help to resolve the situation: The following packages have unmet dependencies: findutils : Depends: essentialpkg but it is not going to be installed -E: Conflict: -> findutils:i386 but not essentialpkg:i386 -> not essentialpkg:i386=4.13a.dfsg.1-6 -> not findutils:i386=4.4.2-1+b1 -> not findutils:i386' aptget remove essentialpkg --trivial-only --solver 3.0 +E: Conflict: findutils:i386 -> essentialpkg:i386=4.13a.dfsg.1-6 but not essentialpkg:i386 -> not essentialpkg:i386=4.13a.dfsg.1-6' aptget remove essentialpkg --trivial-only --solver 3.0 diff --git a/test/integration/test-bug-612557-garbage-upgrade b/test/integration/test-bug-612557-garbage-upgrade index 2a4c952ee..f695b499e 100755 --- a/test/integration/test-bug-612557-garbage-upgrade +++ b/test/integration/test-bug-612557-garbage-upgrade @@ -18,7 +18,7 @@ testsuccess aptmark markauto python-uno openoffice.org-common testmarkedauto python-uno openoffice.org-common # The 3.0 solver does not remove openoffice.org-emailmerge because it is manually installed. -testfailuremsg "E: Conflict: -> openoffice.org-emailmerge:i386 but python-uno:i386=1:3.3.0-2 -> libreoffice-common:i386=1:3.3.0-2 -> not openoffice.org-common:i386=1:3.2.1-11+squeeze2 -> not openoffice.org-emailmerge:i386=1:3.2.1-11+squeeze2 -> not openoffice.org-emailmerge:i386" aptget --trivial-only install python-uno --solver 3.0 +testfailuremsg "E: Conflict: python-uno:i386=1:3.3.0-2 -> libreoffice-common:i386=1:3.3.0-2 -> not openoffice.org-common:i386=1:3.2.1-11+squeeze2 but openoffice.org-emailmerge:i386 -> openoffice.org-common:i386=1:3.2.1-11+squeeze2" aptget --trivial-only install python-uno --solver 3.0 testfailureequal 'Reading package lists... Building dependency tree... Reading state information... diff --git a/test/integration/test-bug-618848-always-respect-user-requests b/test/integration/test-bug-618848-always-respect-user-requests index 8b7b17b77..90965eb22 100755 --- a/test/integration/test-bug-618848-always-respect-user-requests +++ b/test/integration/test-bug-618848-always-respect-user-requests @@ -14,7 +14,7 @@ insertpackage 'unstable' 'exim4-daemon-heavy' 'all' '1.0' 'Depends: libdb4.8' setupaptarchive # This does not work in 3.0 solver: We do not remove manually installed packages. -testfailuremsg "E: Conflict: not libdb4.8:i386 -> not libdb4.8:i386=1.0 -> not exim4-daemon-light:i386=1.0 -> not exim4:i386=1.0 but exim4:i386 -> exim4:i386=1.0" aptget remove libdb4.8 --solver 3.0 -s +testfailuremsg "E: Conflict: exim4-daemon-light:i386 -> libdb4.8:i386=1.0 but not libdb4.8:i386 -> not libdb4.8:i386=1.0" aptget remove libdb4.8 --solver 3.0 -s allowremovemanual testsuccessequal "Reading package lists... Building dependency tree... diff --git a/test/integration/test-dpkg-i-apt-install-fix-broken b/test/integration/test-dpkg-i-apt-install-fix-broken index 21d8e298e..252933184 100755 --- a/test/integration/test-dpkg-i-apt-install-fix-broken +++ b/test/integration/test-dpkg-i-apt-install-fix-broken @@ -17,15 +17,15 @@ Building dependency tree... Correcting dependencies...Install autopkgtest-satdep:amd64 () [0] Install:autopkgtest-satdep:amd64 () [0] Install:autopkgtest-satdep:amd64=1 (autopkgtest-satdep:amd64) -[0] Install:debhelper:amd64=1 (autopkgtest-satdep:amd64 -> autopkgtest-satdep:amd64=1) -[0] Install:debhelper:amd64 (autopkgtest-satdep:amd64 -> autopkgtest-satdep:amd64=1 -> debhelper:amd64=1) +[0] Install:debhelper:amd64=1 (autopkgtest-satdep:amd64) +[0] Install:debhelper:amd64 (autopkgtest-satdep:amd64 -> debhelper:amd64=1) Done Solving dependencies...Install debhelper:amd64 (M) Install autopkgtest-satdep:amd64 () [0] Install:autopkgtest-satdep:amd64 () [0] Install:autopkgtest-satdep:amd64=1 (autopkgtest-satdep:amd64) -[0] Install:debhelper:amd64=1 (autopkgtest-satdep:amd64 -> autopkgtest-satdep:amd64=1) -[0] Install:debhelper:amd64 (autopkgtest-satdep:amd64 -> autopkgtest-satdep:amd64=1 -> debhelper:amd64=1) +[0] Install:debhelper:amd64=1 (autopkgtest-satdep:amd64) +[0] Install:debhelper:amd64 (autopkgtest-satdep:amd64 -> debhelper:amd64=1) The following additional packages will be installed: debhelper diff --git a/test/integration/test-ignore-provides-if-versioned-breaks b/test/integration/test-ignore-provides-if-versioned-breaks index 7947d6d01..0263e8567 100755 --- a/test/integration/test-ignore-provides-if-versioned-breaks +++ b/test/integration/test-ignore-provides-if-versioned-breaks @@ -32,10 +32,7 @@ insertpackage 'unstable' 'foo-same-breaker-none' 'i386' '1.0' 'Breaks: foo-same' setupaptarchive -testfailuremsg 'E: Conflict: foo:i386 but no versions are installable -E: Uninstallable version: foo-breaker-none:i386=1.0 -> not foo:i386=4.0 -E: Uninstallable version: foo-breaker-none:i386=1.0 -> not foo:i386=2.0 -E: Uninstallable version: foo-breaker-none:i386=1.0 -> not foo:i386=2.0' aptget install foo-provider foo-breaker-none -s --solver 3.0 +testfailuremsg 'E: Conflict: foo-breaker-none:i386=1.0 -> not foo-provider:i386=1.0 but foo-provider:i386=1.0' aptget install foo-provider foo-breaker-none -s --solver 3.0 testfailureequal 'Reading package lists... Building dependency tree... Some packages could not be installed. This may mean that you have @@ -74,10 +71,7 @@ Conf foo (4.0 unstable [i386]) Conf foo-breaker-3 (1.0 unstable [i386]) Conf foo-provider (1.0 unstable [i386])' aptget install foo-provider foo-breaker-3 -s -testfailuremsg 'E: Conflict: foo-foreign:amd64 but no versions are installable -E: Uninstallable version: foo-foreign-breaker-none:i386=1.0 -> not foo-foreign:amd64=4.0 -E: Uninstallable version: foo-foreign-breaker-none:i386=1.0 -> not foo-foreign:amd64=2.0 -E: Uninstallable version: foo-foreign-breaker-none:i386=1.0 -> not foo-foreign:amd64=4.0' aptget install foo-foreign-provider foo-foreign-breaker-none -s --solver 3.0 +testfailuremsg 'E: Conflict: foo-foreign-breaker-none:i386=1.0 -> not foo-foreign-provider:i386=1.0 but foo-foreign-provider:i386=1.0' aptget install foo-foreign-provider foo-foreign-breaker-none -s --solver 3.0 testfailureequal 'Reading package lists... Building dependency tree... Some packages could not be installed. This may mean that you have @@ -116,7 +110,7 @@ Conf foo-foreign:amd64 (4.0 unstable [amd64]) Conf foo-foreign-breaker-3 (1.0 unstable [i386]) Conf foo-foreign-provider (1.0 unstable [i386])' aptget install foo-foreign-provider foo-foreign-breaker-3 -s -testfailuremsg 'E: Conflict: -> foo-same:i386 but foo-same-breaker-none:i386=1.0 -> not foo-same:i386=2.0 -> not foo-same:i386' aptget install foo-same-provider foo-same-breaker-none -s --solver 3.0 +testfailuremsg 'E: Conflict: foo-same-breaker-none:i386=1.0 -> not foo-same-provider:i386=1.0 but foo-same-provider:i386=1.0' aptget install foo-same-provider foo-same-breaker-none -s --solver 3.0 testfailureequal 'Reading package lists... Building dependency tree... Some packages could not be installed. This may mean that you have diff --git a/test/integration/test-ignore-provides-if-versioned-conflicts b/test/integration/test-ignore-provides-if-versioned-conflicts index dd24263d1..7f0c357fa 100755 --- a/test/integration/test-ignore-provides-if-versioned-conflicts +++ b/test/integration/test-ignore-provides-if-versioned-conflicts @@ -33,10 +33,7 @@ insertpackage 'unstable' 'foo-same-breaker-none' 'i386' '1.0' 'Conflicts: foo-sa setupaptarchive -testfailuremsg 'E: Conflict: foo:i386 but no versions are installable -E: Uninstallable version: foo-breaker-none:i386=1.0 -> not foo:i386=4.0 -E: Uninstallable version: foo-breaker-none:i386=1.0 -> not foo:i386=2.0 -E: Uninstallable version: foo-breaker-none:i386=1.0 -> not foo:i386=2.0' aptget install foo-provider foo-breaker-none -s --solver 3.0 +testfailuremsg 'E: Conflict: foo-breaker-none:i386=1.0 -> not foo-provider:i386=1.0 but foo-provider:i386=1.0' aptget install foo-provider foo-breaker-none -s --solver 3.0 testfailureequal 'Reading package lists... Building dependency tree... Some packages could not be installed. This may mean that you have @@ -75,10 +72,7 @@ Conf foo (4.0 unstable [i386]) Conf foo-breaker-3 (1.0 unstable [i386]) Conf foo-provider (1.0 unstable [i386])' aptget install foo-provider foo-breaker-3 -s -testfailuremsg 'E: Conflict: foo-foreign:amd64 but no versions are installable -E: Uninstallable version: foo-foreign-breaker-none:i386=1.0 -> not foo-foreign:amd64=4.0 -E: Uninstallable version: foo-foreign-breaker-none:i386=1.0 -> not foo-foreign:amd64=2.0 -E: Uninstallable version: foo-foreign-breaker-none:i386=1.0 -> not foo-foreign:amd64=4.0' aptget install foo-foreign-provider foo-foreign-breaker-none -s --solver 3.0 +testfailuremsg 'E: Conflict: foo-foreign-breaker-none:i386=1.0 -> not foo-foreign-provider:i386=1.0 but foo-foreign-provider:i386=1.0' aptget install foo-foreign-provider foo-foreign-breaker-none -s --solver 3.0 testfailureequal 'Reading package lists... Building dependency tree... Some packages could not be installed. This may mean that you have @@ -117,7 +111,7 @@ Conf foo-foreign:amd64 (4.0 unstable [amd64]) Conf foo-foreign-breaker-3 (1.0 unstable [i386]) Conf foo-foreign-provider (1.0 unstable [i386])' aptget install foo-foreign-provider foo-foreign-breaker-3 -s -testfailuremsg 'E: Conflict: -> foo-same:i386 but foo-same-breaker-none:i386=1.0 -> not foo-same:i386=2.0 -> not foo-same:i386' aptget install foo-same-provider foo-same-breaker-none -s --solver 3.0 +testfailuremsg 'E: Conflict: foo-same-breaker-none:i386=1.0 -> not foo-same-provider:i386=1.0 but foo-same-provider:i386=1.0' aptget install foo-same-provider foo-same-breaker-none -s --solver 3.0 testfailureequal 'Reading package lists... Building dependency tree... Some packages could not be installed. This may mean that you have diff --git a/test/integration/test-multiarch-allowed b/test/integration/test-multiarch-allowed index 298867c5f..4b795bd5e 100755 --- a/test/integration/test-multiarch-allowed +++ b/test/integration/test-multiarch-allowed @@ -64,18 +64,18 @@ Inst needsfoo:i386 (1 unstable [i386]) Conf foo:i386 (1 unstable [i386]) Conf needsfoo:i386 (1 unstable [i386])' aptget install needsfoo:i386 -s # FIXME: same problem, but two different unmet dependency messages depending on install order -testfailuremsg "E: Conflict: -> needsfoo:i386=1 but foo:amd64=1 -> not foo:i386=1 -> not needsfoo:i386=1" aptget install needsfoo:i386 foo:amd64 -s --solver 3.0 +testfailuremsg "E: Conflict: needsfoo:i386=1 -> foo:i386=1 but foo:amd64=1 -> not foo:i386=1" aptget install needsfoo:i386 foo:amd64 -s --solver 3.0 testfailureequal "$BADPREFIX The following packages have unmet dependencies: foo : Conflicts: foo:i386 but 1 is to be installed foo:i386 : Conflicts: foo but 1 is to be installed E: Unable to correct problems, you have held broken packages." aptget install needsfoo:i386 foo:amd64 -s --solver internal -testfailuremsg "E: Conflict: -> needsfoo:i386=1 but foo:amd64=1 -> not foo:i386=1 -> not needsfoo:i386=1" aptget install foo:amd64 needsfoo:i386 -s --solver 3.0 +testfailuremsg "E: Conflict: needsfoo:i386=1 -> foo:i386=1 but foo:amd64=1 -> not foo:i386=1" aptget install foo:amd64 needsfoo:i386 -s --solver 3.0 testfailureequal "$BADPREFIX The following packages have unmet dependencies: needsfoo:i386 : Depends: foo:i386 but it is not installable E: Unable to correct problems, you have held broken packages." aptget install foo:amd64 needsfoo:i386 -s --solver internal -testfailuremsg "E: Conflict: -> needsfoo:amd64=1 but foo:i386=1 -> not foo:amd64=1 -> not needsfoo:amd64=1" aptget install needsfoo foo:i386 -s --solver 3.0 +testfailuremsg "E: Conflict: needsfoo:amd64=1 -> foo:amd64=1 but foo:i386=1 -> not foo:amd64=1" aptget install needsfoo foo:i386 -s --solver 3.0 testfailureequal "$BADPREFIX The following packages have unmet dependencies: foo : Conflicts: foo:i386 but 1 is to be installed 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