Merge branch 'solver3' into 'main'

solver3: Unit propagation queues

See merge request apt-team/apt!440

15 files changed, 74 insertions, 36 deletions

diff --git a/test/integration/solver3.broken b/test/integration/solver3.broken
index dd06ed0eb..2212c34ae 100644
--- a/test/integration/solver3.broken
+++ b/test/integration/solver3.broken
@@ -6,12 +6,10 @@ test-apt-install-file-reltag
 test-apt-install-order-matters-a-bit
 test-apt-move-and-forget-manual-sections
 test-apt-patterns
-test-apt-source-and-build-dep
 test-bug-470115-new-and-tighten-recommends
 test-bug-602412-dequote-redirect
 test-bug-611729-mark-as-manual
 test-bug-675449-essential-are-protected
-test-bug-709560-set-candidate-release
 test-bug-745046-candidate-propagation-fails
 test-bug-753297-upgradable
 test-bug-767891-force-essential-important
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-bug-735967-lib32-to-i386-unavailable b/test/integration/test-bug-735967-lib32-to-i386-unavailable
index cc925d161..a44e58570 100755
--- a/test/integration/test-bug-735967-lib32-to-i386-unavailable
+++ b/test/integration/test-bug-735967-lib32-to-i386-unavailable
@@ -35,6 +35,12 @@ testsuccess aptget update
 testsuccessequal 'Reading package lists...
 Building dependency tree...
 Calculating upgrade...
+The following packages have been kept back:
+  lib32nss-mdns libnss-mdns
+0 upgraded, 0 newly installed, 0 to remove and 2 not upgraded.' aptget dist-upgrade -s --solver 3.0
+testsuccessequal 'Reading package lists...
+Building dependency tree...
+Calculating upgrade...
 The following packages will be REMOVED:
   lib32nss-mdns
 The following packages will be upgraded:
@@ -42,7 +48,7 @@ The following packages will be upgraded:
 1 upgraded, 0 newly installed, 1 to remove and 0 not upgraded.
 Remv lib32nss-mdns [0.9-1]
 Inst libnss-mdns [0.9-1] (0.10-6 unstable [amd64])
-Conf libnss-mdns (0.10-6 unstable [amd64])' aptget dist-upgrade -s
+Conf libnss-mdns (0.10-6 unstable [amd64])' aptget dist-upgrade -s --solver internal
 
 testfailuremsg 'E: Unsatisfiable dependency group libfoo:amd64=1 -> libfoo-bin:amd64' aptget install foo -s --solver 3.0
 testfailureequal 'Reading package lists...
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
diff --git a/test/integration/test-solver-recommends-depends b/test/integration/test-solver-recommends-depends
new file mode 100755
index 000000000..90c5050a7
--- /dev/null
+++ b/test/integration/test-solver-recommends-depends
@@ -0,0 +1,46 @@
+#!/bin/sh
+set -e
+
+TESTDIR="$(readlink -f "$(dirname "$0")")"
+. "$TESTDIR/framework"
+setupenvironment
+allowremovemanual
+configarchitecture 'amd64'
+
+insertpackage 'unstable' 'a' 'all' '2'
+insertpackage 'unstable' 'b' 'all' '2'
+insertpackage 'unstable' 'x' 'all' '3' 'Depends: xx
+Recommends: b'
+insertpackage 'unstable' 'xx' 'all' '3' 'Depends: a | b
+Recommends: b'
+
+setupaptarchive
+
+msgmsg "Test that the Recommends does not influence the Depends"
+testsuccessequal "The following additional packages will be installed:
+  a b
+The following NEW packages will be installed:
+  a b xx
+0 upgraded, 3 newly installed, 0 to remove and 0 not upgraded.
+Inst a (2 unstable [all])
+Inst b (2 unstable [all])
+Inst xx (3 unstable [all])
+Conf a (2 unstable [all])
+Conf b (2 unstable [all])
+Conf xx (3 unstable [all])" apt install -s xx -qq
+
+
+msgmsg "Test that the Recommends in x does not influence the Depends in xx (one level lower)"
+testsuccessequal "The following additional packages will be installed:
+  a b xx
+The following NEW packages will be installed:
+  a b x xx
+0 upgraded, 4 newly installed, 0 to remove and 0 not upgraded.
+Inst a (2 unstable [all])
+Inst b (2 unstable [all])
+Inst xx (3 unstable [all])
+Inst x (3 unstable [all])
+Conf a (2 unstable [all])
+Conf b (2 unstable [all])
+Conf xx (3 unstable [all])
+Conf x (3 unstable [all])" apt install -s x -qq