Merge branch 'solver3' into 'main'

solver3: Verbose error messages and some bugfixes

See merge request apt-team/apt!457

28 files changed, 401 insertions, 59 deletions

diff --git a/test/integration/test-apt-get-build-dep-barbarian b/test/integration/test-apt-get-build-dep-barbarian
index 48873c59b..8763e8fc7 100755
--- a/test/integration/test-apt-get-build-dep-barbarian
+++ b/test/integration/test-apt-get-build-dep-barbarian
@@ -83,7 +83,16 @@ testsuccessequal "$(installsfoosamey 'amd64' 'i386')" apt build-dep cool-foo -s
 testsuccessequal "$(installsfoosamey 'i386' 'i386')" apt build-dep bad-amd64-foo -s -a i386
 testsuccessequal "$(installsfoosamey 'amd64' 'i386')" apt build-dep bad-armel-foo -s -a i386
 testsuccessequal "$(installsfoosamey 'i386' 'i386')" apt build-dep bad-amd64-armel-foo -s -a i386
-testfailuremsg 'E: Conflict: builddeps:bad-amd64-i386-foo:i386=1 -> builddeps:bad-amd64-i386-foo:i386 -> not foo:amd64=1 -> not builddeps:bad-amd64-i386-foo:i386 but builddeps:bad-amd64-i386-foo:i386=1 -> builddeps:bad-amd64-i386-foo:i386'  apt build-dep bad-amd64-i386-foo -s -a i386 --solver 3.0
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. builddeps:bad-amd64-i386-foo:i386=1 is selected for install
+   2. builddeps:bad-amd64-i386-foo:i386 Depends foo:i386
+      but none of the choices are installable:
+      - foo:amd64=1 is not selected for install because:
+        1. builddeps:bad-amd64-i386-foo:i386=1 is selected for install
+        2. builddeps:bad-amd64-i386-foo:i386 Conflicts foo:amd64
+      - foo:i386=1 is not selected for install because:
+        1. builddeps:bad-amd64-i386-foo:i386=1 is selected for install as above
+        2. builddeps:bad-amd64-i386-foo:i386 Conflicts foo:i386'  apt build-dep bad-amd64-i386-foo -s -a i386 --solver 3.0
 testfailureequal 'Reading package lists...
 Reading package lists...
 Building dependency tree...
@@ -96,7 +105,16 @@ The following information may help to resolve the situation:
 The following packages have unmet dependencies:
  builddeps:bad-amd64-i386-foo:i386 : Depends: foo:i386
 E: Unable to correct problems, you have held broken packages.' apt build-dep bad-amd64-i386-foo -s -a i386 --solver internal
-testfailuremsg 'E: Conflict: builddeps:bad-amd64-i386-armel-foo:i386=1 -> builddeps:bad-amd64-i386-armel-foo:i386 -> not foo:amd64=1 -> not builddeps:bad-amd64-i386-armel-foo:i386 but builddeps:bad-amd64-i386-armel-foo:i386=1 -> builddeps:bad-amd64-i386-armel-foo:i386' apt build-dep bad-amd64-i386-armel-foo -s -a i386 --solver 3.0
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. builddeps:bad-amd64-i386-armel-foo:i386=1 is selected for install
+   2. builddeps:bad-amd64-i386-armel-foo:i386 Depends foo:i386
+      but none of the choices are installable:
+      - foo:amd64=1 is not selected for install because:
+        1. builddeps:bad-amd64-i386-armel-foo:i386=1 is selected for install
+        2. builddeps:bad-amd64-i386-armel-foo:i386 Conflicts foo:amd64
+      - foo:i386=1 is not selected for install because:
+        1. builddeps:bad-amd64-i386-armel-foo:i386=1 is selected for install as above
+        2. builddeps:bad-amd64-i386-armel-foo:i386 Conflicts foo:i386' apt build-dep bad-amd64-i386-armel-foo -s -a i386 --solver 3.0
 testfailureequal 'Reading package lists...
 Reading package lists...
 Building dependency tree...
@@ -115,7 +133,19 @@ testsuccessequal "$(installsfoosamey 'i386' 'armel')" apt build-dep bad-amd64-fo
 testsuccessequal "$(installsfoosamey 'amd64' 'armel')" apt build-dep bad-armel-foo -s -a armel
 testsuccessequal "$(installsfoosamey 'i386' 'armel')" apt build-dep bad-amd64-armel-foo -s -a armel
 testsuccessequal "$(installsfoosamey 'armel' 'armel')" apt build-dep bad-amd64-i386-foo -s -a armel
-FAILUREMSG="E: Conflict: builddeps:bad-amd64-i386-armel-foo:armel=1 -> builddeps:bad-amd64-i386-armel-foo:armel -> not foo:amd64=1 -> not builddeps:bad-amd64-i386-armel-foo:armel but builddeps:bad-amd64-i386-armel-foo:armel=1 -> builddeps:bad-amd64-i386-armel-foo:armel"
+FAILUREMSG="E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. builddeps:bad-amd64-i386-armel-foo:armel=1 is selected for install
+   2. builddeps:bad-amd64-i386-armel-foo:armel Depends foo:armel
+      but none of the choices are installable:
+      - foo:amd64=1 is not selected for install because:
+        1. builddeps:bad-amd64-i386-armel-foo:armel=1 is selected for install
+        2. builddeps:bad-amd64-i386-armel-foo:armel Conflicts foo:amd64
+      - foo:i386=1 is not selected for install because:
+        1. builddeps:bad-amd64-i386-armel-foo:armel=1 is selected for install as above
+        2. builddeps:bad-amd64-i386-armel-foo:armel Conflicts foo:i386
+      - foo:armel=1 is not selected for install because:
+        1. builddeps:bad-amd64-i386-armel-foo:armel=1 is selected for install as above
+        2. builddeps:bad-amd64-i386-armel-foo:armel Conflicts foo:armel"
 FAILURE='Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have
diff --git a/test/integration/test-apt-get-build-dep-file b/test/integration/test-apt-get-build-dep-file
index 8147bb0a3..fd48aef47 100755
--- a/test/integration/test-apt-get-build-dep-file
+++ b/test/integration/test-apt-get-build-dep-file
@@ -160,7 +160,11 @@ cd ../..
 
 testfailureequal 'E: Must specify at least one package to check builddeps for' aptget build-dep
 testfailuremsg 'W: No architecture information available for armel. See apt.conf(5) APT::Architectures for setup
-E: Unsatisfiable dependency group builddeps:./foo-1.0:armel -> debhelper:armel' aptget build-dep --simulate ./foo-1.0 -a armel --solver 3.0
+E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. builddeps:./foo-1.0:armel=1 is selected for install
+   2. builddeps:./foo-1.0:armel Depends debhelper:armel (>= 7)
+      but none of the choices are installable:
+      [no choices]' aptget build-dep --simulate ./foo-1.0 -a armel --solver 3.0
 testfailureequal "Note, using directory './foo-1.0' to get the build dependencies
 Reading package lists...
 Building dependency tree...
diff --git a/test/integration/test-apt-get-install-deb b/test/integration/test-apt-get-install-deb
index 1540db272..07de975c4 100755
--- a/test/integration/test-apt-get-install-deb
+++ b/test/integration/test-apt-get-install-deb
@@ -32,7 +32,11 @@ done
 
 buildsimplenativepackage 'foo' 'i386,amd64' '1.0'
 
-testfailuremsg "E: Conflict: foo:amd64=1.0 -> foo:amd64 but foo:i386=1.0 -> not foo:amd64" aptget install ./incoming/foo_1.0_i386.deb ./incoming/foo_1.0_amd64.deb -s --solver 3.0
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. foo:amd64 is not selected for install because:
+      1. foo:i386=1.0 is selected for install
+      2. foo:amd64 Conflicts foo:i386
+   2. foo:amd64=1.0 is selected for install" 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'
@@ -177,7 +181,11 @@ echo 'Package: /pkg-/
 Pin: release a=experimental
 Pin-Priority: 501' > rootdir/etc/apt/preferences.d/pinit
 
-testfailuremsg 'E: Unsatisfiable dependency group pkg-last-line-parse:amd64 -> pkg-as-it-should-be:amd64' aptget install -q=0 ./incoming/pkg-last-line-parse_0_all.deb --solver 3.0
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. pkg-last-line-parse:amd64=0 is selected for install
+   2. pkg-last-line-parse:amd64 PreDepends pkg-as-it-should-be
+      but none of the choices are installable:
+      [no choices]' aptget install -q=0 ./incoming/pkg-last-line-parse_0_all.deb --solver 3.0
 testfailuremsg 'E: Unable to correct problems, you have held broken packages.' aptget install -q=0 ./incoming/pkg-last-line-parse_0_all.deb --solver internal
 testsuccess aptget install ./incoming/pkg-as-it-should-be_0_all.deb
 testsuccess aptget install ./incoming/pkg-last-line-parse_0_all.deb
diff --git a/test/integration/test-apt-get-satisfy b/test/integration/test-apt-get-satisfy
index 02a444dff..8e5e06843 100755
--- a/test/integration/test-apt-get-satisfy
+++ b/test/integration/test-apt-get-satisfy
@@ -80,7 +80,11 @@ testrun 'External' 'Reading package lists...
 Building dependency tree...
 Execute external solver...' --solver apt
 
-testfailuremsg "E: Unsatisfiable dependency group satisfy:command-line:i386 -> depends:i386" aptget satisfy --simulate "depends (>= 2)" "Conflicts: conflicts:i386 (>= 1) [i386], conflicts:amd64 (>= 1) [amd64]" --solver 3.0
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. satisfy:command-line:i386=1 is selected for install
+   2. satisfy:command-line:i386 Depends depends (>= 2)
+      but none of the choices are installable:
+      [no choices]" aptget satisfy --simulate "depends (>= 2)" "Conflicts: conflicts:i386 (>= 1) [i386], conflicts:amd64 (>= 1) [amd64]" --solver 3.0
 
 testfailureequal "Reading package lists...
 Building dependency tree...
diff --git a/test/integration/test-apt-get-source-only b/test/integration/test-apt-get-source-only
index 882f82b33..e5d246f6e 100755
--- a/test/integration/test-apt-get-source-only
+++ b/test/integration/test-apt-get-source-only
@@ -40,7 +40,11 @@ The following information may help to resolve the situation:
 
 The following packages have unmet dependencies:
  builddeps:foo : Depends: foo-bd but it is not installable
-E: Unsatisfiable dependency group builddeps:foo:amd64 -> foo-bd:amd64"
+E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. builddeps:foo:amd64=1 is selected for install
+   2. builddeps:foo:amd64 Depends foo-bd
+      but none of the choices are installable:
+      [no choices]"
 
 BUILDDEPNOTFOO="Reading package lists...
 Building dependency tree...
@@ -52,7 +56,11 @@ The following information may help to resolve the situation:
 
 The following packages have unmet dependencies:
  builddeps:not-foo : Depends: not-foo-bd but it is not installable
-E: Unsatisfiable dependency group builddeps:not-foo:amd64 -> not-foo-bd:amd64"
+E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. builddeps:not-foo:amd64=1 is selected for install
+   2. builddeps:not-foo:amd64 Depends not-foo-bd
+      but none of the choices are installable:
+      [no choices]"
 else
 BUILDDEPFOO="Reading package lists...
 Building dependency tree...
diff --git a/test/integration/test-apt-install-file-reltag b/test/integration/test-apt-install-file-reltag
index 0637c5472..053c785fd 100755
--- a/test/integration/test-apt-install-file-reltag
+++ b/test/integration/test-apt-install-file-reltag
@@ -31,7 +31,7 @@ buildsimplenativepackage 'foobar2' 'all' '1' 'unstable' 'Depends: foo (= 5), baz
 
 testunsat() {
     testfailure "$@"
-    testsuccess grep -E "^E: (Unable to correct problems,|Conflict:)" "${TMPWORKINGDIRECTORY}/rootdir/tmp/testfailure.output"
+    testsuccess grep -E "^E: (Unable to correct problems,|Unable to satisfy dependencies. Reached two conflicting decisions)" "${TMPWORKINGDIRECTORY}/rootdir/tmp/testfailure.output"
 }
 
 ln -s "$(readlink -f ./incoming/foobar2_1_all.deb)" foobar.deb
diff --git a/test/integration/test-apt-never-markauto-sections b/test/integration/test-apt-never-markauto-sections
index 95ba47553..bf08507d0 100755
--- a/test/integration/test-apt-never-markauto-sections
+++ b/test/integration/test-apt-never-markauto-sections
@@ -49,7 +49,18 @@ Remv foreignpkg:i386 [1]
 Remv nosection [1]
 Remv texteditor [1]' aptget autoremove mydesktop -s
 
-testfailuremsg 'E: Conflict: not texteditor:amd64 -> not bad-texteditor:amd64 but mydesktop:amd64 -> mydesktop-core:amd64 -> bad-texteditor:amd64' aptget autoremove texteditor -s --solver 3.0 #-o Debug::pkgDepCache::AutoInstall=1 -o Debug::pkgProblemResolver=1 -o Debug::pkgDepCache::Marker=1
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. bad-texteditor:amd64 is selected for install because:
+      1. mydesktop:amd64 is selected for install
+      2. mydesktop:amd64 Depends mydesktop-core
+      3. mydesktop-core:amd64 Depends bad-texteditor | texteditor
+         [selected mydesktop-core:amd64]
+      For context, additional choices that could not be installed:
+      * In mydesktop-core:amd64 Depends bad-texteditor | texteditor:
+        - texteditor:amd64 is selected for removal
+   2. bad-texteditor:amd64 Depends texteditor
+      but none of the choices are installable:
+      - texteditor:amd64 is selected for removal' 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-598669-install-postfix-gets-exim-heavy b/test/integration/test-bug-598669-install-postfix-gets-exim-heavy
index 6c9fb60c0..98479b5fd 100755
--- a/test/integration/test-bug-598669-install-postfix-gets-exim-heavy
+++ b/test/integration/test-bug-598669-install-postfix-gets-exim-heavy
@@ -1,4 +1,4 @@
-#!/bin/sh
+t-bug-598669-install-postfix-gets-exim-heavy!/bin/sh
 set -e
 
 TESTDIR="$(readlink -f "$(dirname "$0")")"
@@ -7,7 +7,13 @@ setupenvironment
 configarchitecture "i386"
 setupaptarchive
 
-testfailuremsg "E: Conflict: exim4-daemon-light:i386 -> not postfix:i386=2.7.1-1 but postfix:i386=2.7.1-1" aptget install postfix --solver 3.0
+# FIXME: Should this say selected postifx?
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. postfix:i386=2.7.1-1 is selected for install
+   2. postfix:i386=2.7.1-1 is not selected for install because:
+      1. exim4-daemon-light:i386 is selected for install
+      2. exim4-daemon-light:i386 Conflicts mail-transport-agent
+         [selected exim4-daemon-light:i386]" 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 6d68372b5..be55e76a7 100755
--- a/test/integration/test-bug-601961-install-info
+++ b/test/integration/test-bug-601961-install-info
@@ -60,4 +60,8 @@ 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 -> essentialpkg:i386 but not essentialpkg:i386' aptget remove essentialpkg --trivial-only --solver 3.0
+E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. essentialpkg:i386 is selected for removal
+   2. essentialpkg:i386 is selected for install because:
+      1. findutils:i386 is selected for install
+      2. findutils:i386 Depends essentialpkg' 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 4ef241cad..a001c4385 100755
--- a/test/integration/test-bug-612557-garbage-upgrade
+++ b/test/integration/test-bug-612557-garbage-upgrade
@@ -18,7 +18,14 @@ 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 -> openoffice.org-common:i386 -> openoffice.org-common:i386=1:3.2.1-11+squeeze2 but python-uno:i386=1:3.3.0-2 -> libreoffice-common:i386 -> not openoffice.org-common:i386=1:3.2.1-11+squeeze2" aptget --trivial-only install python-uno --solver 3.0
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. openoffice.org-common:i386=1:3.2.1-11+squeeze2 is not selected for install because:
+      1. python-uno:i386=1:3.3.0-2 is selected as an upgrade
+      2. python-uno:i386=1:3.3.0-2 Depends libreoffice-common
+      3. libreoffice-common:i386 Conflicts openoffice.org-common
+   2. openoffice.org-common:i386 is selected for install because:
+      1. openoffice.org-emailmerge:i386 is selected for install
+      2. openoffice.org-emailmerge:i386 PreDepends openoffice.org-common" 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 d59491af6..b1cccef9d 100755
--- a/test/integration/test-bug-618848-always-respect-user-requests
+++ b/test/integration/test-bug-618848-always-respect-user-requests
@@ -14,7 +14,11 @@ 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 exim4-daemon-light:i386 but exim4-daemon-light:i386" aptget remove libdb4.8 --solver 3.0 -s
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. exim4-daemon-light:i386 is selected for install
+   2. exim4-daemon-light:i386 Depends libdb4.8
+      but none of the choices are installable:
+      - libdb4.8:i386 is selected for removal" aptget remove libdb4.8 --solver 3.0 -s
 allowremovemanual
 testsuccessequal "Reading package lists...
 Building dependency tree...
diff --git a/test/integration/test-bug-632221-cross-dependency-satisfaction b/test/integration/test-bug-632221-cross-dependency-satisfaction
index d101bd1fa..6e39b384c 100755
--- a/test/integration/test-bug-632221-cross-dependency-satisfaction
+++ b/test/integration/test-bug-632221-cross-dependency-satisfaction
@@ -35,7 +35,11 @@ insertsource 'unstable' 'source-specific-armel' 'armel' '1' 'Build-Depends: spec
 
 setupaptarchive
 
-testfailuremsg "E: Unsatisfiable dependency group builddeps:forbidden-no:armel -> amdboot:any:any" aptget build-dep forbidden-no -s -a armel --solver 3.0
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. builddeps:forbidden-no:armel=1 is selected for install
+   2. builddeps:forbidden-no:armel Depends amdboot:any
+      but none of the choices are installable:
+      [no choices]" aptget build-dep forbidden-no -s -a armel --solver 3.0
 testfailureequal 'Reading package lists...
 Reading package lists...
 Building dependency tree...
@@ -49,7 +53,11 @@ The following packages have unmet dependencies:
  builddeps:forbidden-no:armel : Depends: amdboot:any but it is not installable
 E: Unable to correct problems, you have held broken packages.' aptget build-dep forbidden-no -s -a armel --solver internal
 
-testfailuremsg "E: Unsatisfiable dependency group builddeps:forbidden-same:armel -> libc6:any:any" aptget build-dep forbidden-same -s -a armel --solver 3.0
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. builddeps:forbidden-same:armel=1 is selected for install
+   2. builddeps:forbidden-same:armel Depends libc6:any
+      but none of the choices are installable:
+      [no choices]" aptget build-dep forbidden-same -s -a armel --solver 3.0
 testfailureequal 'Reading package lists...
 Reading package lists...
 Building dependency tree...
@@ -63,7 +71,11 @@ The following packages have unmet dependencies:
  builddeps:forbidden-same:armel : Depends: libc6:any but it is not installable
 E: Unable to correct problems, you have held broken packages.' aptget build-dep forbidden-same -s -a armel --solver internal
 
-testfailuremsg 'E: Unsatisfiable dependency group builddeps:forbidden-foreign:armel -> doxygen:any:any' aptget build-dep forbidden-foreign -s -a armel --solver 3.0
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. builddeps:forbidden-foreign:armel=1 is selected for install
+   2. builddeps:forbidden-foreign:armel Depends doxygen:any
+      but none of the choices are installable:
+      [no choices]' aptget build-dep forbidden-foreign -s -a armel --solver 3.0
 testfailureequal 'Reading package lists...
 Reading package lists...
 Building dependency tree...
diff --git a/test/integration/test-bug-675449-essential-are-protected b/test/integration/test-bug-675449-essential-are-protected
index 36e7b645e..c8e832d72 100755
--- a/test/integration/test-bug-675449-essential-are-protected
+++ b/test/integration/test-bug-675449-essential-are-protected
@@ -114,7 +114,7 @@ The following packages have unmet dependencies:
  foo : Depends: libfoo but it is not going to be installed
 E: Error, pkgProblemResolver::Resolve generated breaks, this may be caused by held packages.' aptget purge libfoo -s --solver internal
 
-testequal 'Reading package lists...
+testfailureequal 'Reading package lists...
 Building dependency tree...
 Solving dependencies...
 Some packages could not be installed. This may mean that you have
@@ -125,4 +125,8 @@ The following information may help to resolve the situation:
 
 The following packages have unmet dependencies:
  foo : Depends: libfoo but it is not going to be installed
-E: Conflict: foo:amd64 -> libfoo:amd64 but not libfoo:amd64' aptget purge libfoo -s --solver 3.0
+E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. libfoo:amd64 is selected for removal
+   2. libfoo:amd64 is selected for install because:
+      1. foo:amd64 is selected for install
+      2. foo:amd64 Depends libfoo' aptget purge libfoo -s --solver 3.0
diff --git a/test/integration/test-bug-683786-build-dep-on-virtual-packages b/test/integration/test-bug-683786-build-dep-on-virtual-packages
index 75f0a9626..a682a2f1a 100755
--- a/test/integration/test-bug-683786-build-dep-on-virtual-packages
+++ b/test/integration/test-bug-683786-build-dep-on-virtual-packages
@@ -41,7 +41,11 @@ The following NEW packages will be installed:
 Inst po-debconf (1 unstable [all])
 Conf po-debconf (1 unstable [all])' aptget build-dep dash -s
 
-testfailuremsg 'E: Unsatisfiable dependency group builddeps:dash:armel -> po-debconf:armel' aptget build-dep -aarmel dash -s --solver 3.0
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. builddeps:dash:armel=1 is selected for install
+   2. builddeps:dash:armel Depends po-debconf:armel
+      but none of the choices are installable:
+      [no choices]' aptget build-dep -aarmel dash -s --solver 3.0
 testfailureequal 'Reading package lists...
 Reading package lists...
 Building dependency tree...
@@ -55,7 +59,11 @@ The following packages have unmet dependencies:
  builddeps:dash:armel : Depends: po-debconf:armel but it is not installable
 E: Unable to correct problems, you have held broken packages.' aptget build-dep -aarmel dash -s --solver internal
 
-testfailuremsg 'E: Unsatisfiable dependency group builddeps:diffutils:armel -> texi2html:armel' aptget build-dep -aarmel diffutils -s --solver 3.0
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. builddeps:diffutils:armel=1 is selected for install
+   2. builddeps:diffutils:armel Depends texi2html:armel
+      but none of the choices are installable:
+      [no choices]' aptget build-dep -aarmel diffutils -s --solver 3.0
 testfailureequal 'Reading package lists...
 Reading package lists...
 Building dependency tree...
@@ -78,7 +86,11 @@ The following NEW packages will be installed:
 Inst libselinux1-dev (1 unstable [amd64])
 Conf libselinux1-dev (1 unstable [amd64])" aptget build-dep sed -s
 
-testfailuremsg 'E: Unsatisfiable dependency group builddeps:sed:armel -> libselinux-dev:armel' aptget build-dep -aarmel sed -s --solver 3.0
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. builddeps:sed:armel=1 is selected for install
+   2. builddeps:sed:armel Depends libselinux-dev:armel
+      but none of the choices are installable:
+      [no choices]' aptget build-dep -aarmel sed -s --solver 3.0
 testfailureequal 'Reading package lists...
 Reading package lists...
 Building dependency tree...
diff --git a/test/integration/test-bug-723586-any-stripped-in-single-arch b/test/integration/test-bug-723586-any-stripped-in-single-arch
index 17c3839d1..672413125 100755
--- a/test/integration/test-bug-723586-any-stripped-in-single-arch
+++ b/test/integration/test-bug-723586-any-stripped-in-single-arch
@@ -41,7 +41,11 @@ The following information may help to resolve the situation:
 
 The following packages have unmet dependencies:
  python-mips : Depends: python3:mips but it is not installable
-E: Unsatisfiable dependency group python-mips:amd64 -> python3:mips:any'
+E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. python-mips:amd64=3 is selected for install
+   2. python-mips:amd64 Depends python3:mips
+      but none of the choices are installable:
+      [no choices]'
 else
 FAILLOG='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 2eedf22ab..83992e386 100755
--- a/test/integration/test-bug-735967-lib32-to-i386-unavailable
+++ b/test/integration/test-bug-735967-lib32-to-i386-unavailable
@@ -50,7 +50,13 @@ 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 --solver internal
 
-testfailuremsg 'E: Unsatisfiable dependency group libfoo:amd64 -> libfoo-bin:amd64' aptget install foo -s --solver 3.0
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. libfoo:amd64 is selected for install because:
+      1. foo:amd64=1 is selected for install
+      2. foo:amd64 Depends libfoo
+   2. libfoo:amd64 Depends libfoo-bin
+      but none of the choices are installable:
+      [no choices]' aptget install foo -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-bug-745046-candidate-propagation-fails b/test/integration/test-bug-745046-candidate-propagation-fails
index a8ee50124..8475a4ea1 100755
--- a/test/integration/test-bug-745046-candidate-propagation-fails
+++ b/test/integration/test-bug-745046-candidate-propagation-fails
@@ -39,7 +39,11 @@ The following information may help to resolve the situation:
 
 The following packages have unmet dependencies:
  gedit : Depends: common (>= 2) but it is not installable
-E: Unsatisfiable dependency group gedit:amd64=2 -> common:amd64" aptget install gedit/experimental -sq=0 --solver 3.0
+E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. gedit:amd64=2 is selected as an upgrade
+   2. gedit:amd64=2 Depends common (>= 2)
+      but none of the choices are installable:
+      [no choices]" aptget install gedit/experimental -sq=0 --solver 3.0
 
 insertinstalledpackage 'common' 'amd64' '2'
 
diff --git a/test/integration/test-bug-961266-hold-means-hold b/test/integration/test-bug-961266-hold-means-hold
index 8c18cd757..c97aa0839 100755
--- a/test/integration/test-bug-961266-hold-means-hold
+++ b/test/integration/test-bug-961266-hold-means-hold
@@ -89,7 +89,16 @@ The following information may help to resolve the situation:
 
 The following packages have unmet dependencies:
  git-ng : Depends: git (> 1:2.26.2)
-E: Conflict: git:amd64=1:2.25.1-1 -> not git:amd64=1:2.26.2-1 -> not git-ng:amd64 but git-ng:amd64=1:2.26.2-1 -> git-ng:amd64' apt install git-ng -s --solver 3.0
+E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. git-ng:amd64=1:2.26.2-1 is selected for install
+   2. git-ng:amd64 Depends git (> 1:2.26.2)
+      but none of the choices are installable:
+      - git:amd64=1:2.26.2-1 is not selected for install because:
+        1. git:amd64=1:2.25.1-1 is selected for install
+        2. git:amd64=1:2.25.1-1 conflicts with other versions of itself
+      - git:i386=1:2.26.2-1 is not selected for install because:
+        1. git:amd64=1:2.25.1-1 is selected for install as above
+        2. git:amd64 Conflicts git:i386' apt install git-ng -s --solver 3.0
 
 
 msgmsg 'Now mix it up by' 'holding git-cvs'
@@ -126,7 +135,20 @@ The following information may help to resolve the situation:
 
 The following packages have unmet dependencies:
  git-ng : Depends: git (> 1:2.26.2)
-E: Conflict: git-cvs:amd64=1:2.25.1-1 -> git:amd64=1:2.25.1-1 -> not git:amd64=1:2.26.2-1 but git-ng:amd64=1:2.26.2-1 -> git-ng:amd64 -> git:amd64=1:2.26.2-1' apt install git-ng -s --solver 3.0
+E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. git:amd64=1:2.26.2-1 is selected as an upgrade because:
+      1. git-ng:amd64=1:2.26.2-1 is selected for install
+      2. git-ng:amd64 Depends git (> 1:2.26.2)
+         [selected git-ng:amd64]
+      For context, additional choices that could not be installed:
+      * In git-ng:amd64 Depends git (> 1:2.26.2):
+        - git:i386=1:2.26.2-1 is not selected for install because:
+          1. git:amd64 is selected for install
+          2. git:amd64 Conflicts git:i386
+   2. git:amd64=1:2.26.2-1 is not selected for install because:
+      1. git-cvs:amd64=1:2.25.1-1 is selected for install
+      2. git-cvs:amd64=1:2.25.1-1 Depends git (< 1:2.25.1-.)
+      3. git:amd64=1:2.25.1-1 conflicts with other versions of itself' apt install git-ng -s --solver 3.0
 
 
 msgmsg 'Now mix it up by' 'holding both'
@@ -162,4 +184,13 @@ The following information may help to resolve the situation:
 
 The following packages have unmet dependencies:
  git-ng : Depends: git (> 1:2.26.2)
-E: Conflict: git:amd64=1:2.25.1-1 -> not git:amd64=1:2.26.2-1 -> not git-ng:amd64 but git-ng:amd64=1:2.26.2-1 -> git-ng:amd64' apt install git-ng -s --solver 3.0
+E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. git-ng:amd64=1:2.26.2-1 is selected for install
+   2. git-ng:amd64 Depends git (> 1:2.26.2)
+      but none of the choices are installable:
+      - git:amd64=1:2.26.2-1 is not selected for install because:
+        1. git:amd64=1:2.25.1-1 is selected for install
+        2. git:amd64=1:2.25.1-1 conflicts with other versions of itself
+      - git:i386=1:2.26.2-1 is not selected for install because:
+        1. git:amd64=1:2.25.1-1 is selected for install as above
+        2. git:amd64 Conflicts git:i386' apt install git-ng -s --solver 3.0
diff --git a/test/integration/test-explore-or-groups-in-markinstall b/test/integration/test-explore-or-groups-in-markinstall
index 4c67296d7..60de59193 100755
--- a/test/integration/test-explore-or-groups-in-markinstall
+++ b/test/integration/test-explore-or-groups-in-markinstall
@@ -161,7 +161,13 @@ testfailureequal "$BADSOLVETEXT3
 The following packages have unmet dependencies:
  bad-upgrade-level1 : Depends: bad-upgrade-level0 (>= 2) but 1 is to be installed
                       Depends: unneeded2 but it is not going to be installed
-E: Unsatisfiable dependency group bad-upgrade-level0:amd64=2 -> unknown:amd64" apt install bad-upgrade-level1 -s --solver 3.0
+E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. bad-upgrade-level0:amd64=2 is selected as an upgrade because:
+      1. bad-upgrade-level1:amd64=2 is selected as an upgrade
+      2. bad-upgrade-level1:amd64=2 Depends bad-upgrade-level0 (>= 2)
+   2. bad-upgrade-level0:amd64=2 Depends unknown
+      but none of the choices are installable:
+      [no choices]" apt install bad-upgrade-level1 -s --solver 3.0
 testfailureequal "$BADSOLVETEXT
 The following packages have unmet dependencies:
  bad-conflict-level0 : Conflicts: bad-conflict-level2 but 1 is to be installed
@@ -171,7 +177,15 @@ testfailureequal "$BADSOLVETEXT3
 The following packages have unmet dependencies:
  bad-conflict-level2 : Depends: bad-conflict-level1 but it is not going to be installed
                        Depends: unneeded2 but it is not going to be installed
-E: Conflict: bad-conflict-level2:amd64=1 -> not bad-conflict-level0:amd64 -> not bad-conflict-level1:amd64 but bad-conflict-level2:amd64=1 -> bad-conflict-level2:amd64 -> bad-conflict-level1:amd64" apt install bad-conflict-level2 -s --solver 3.0
+E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. bad-conflict-level1:amd64 is selected for install because:
+      1. bad-conflict-level2:amd64=1 is selected for install
+      2. bad-conflict-level2:amd64 Depends bad-conflict-level1
+   2. bad-conflict-level1:amd64 Depends bad-conflict-level0
+      but none of the choices are installable:
+      - bad-conflict-level0:amd64 is not selected for install because:
+        1. bad-conflict-level2:amd64=1 is selected for install as above
+        2. bad-conflict-level0:amd64 Conflicts bad-conflict-level2" apt install bad-conflict-level2 -s --solver 3.0
 
 if $TEST_WITH_APTITUDE; then
 	testsuccesstailequal 6 'The following packages have been kept back:
diff --git a/test/integration/test-handling-broken-orgroups b/test/integration/test-handling-broken-orgroups
index f9c436f81..5c882b516 100755
--- a/test/integration/test-handling-broken-orgroups
+++ b/test/integration/test-handling-broken-orgroups
@@ -47,7 +47,11 @@ Inst coolstuff2 (1.0-1 unstable [all])
 Conf stuff (1.0-1 unstable [all])
 Conf coolstuff2 (1.0-1 unstable [all])' aptget install coolstuff2 -s
 
-testfailuremsg 'E: Unsatisfiable dependency group coolstuff-broken:i386 -> cool2:i386' aptget install coolstuff-broken --solver 3.0 -s
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. coolstuff-broken:i386=1.0-1 is selected for install
+   2. coolstuff-broken:i386 Depends cool2 | stuff2
+      but none of the choices are installable:
+      [no choices]' aptget install coolstuff-broken --solver 3.0 -s
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have
@@ -95,7 +99,11 @@ Inst coolstuff-provided (1.0-1 unstable [all])
 Conf extrastuff (1.0-1 unstable [all])
 Conf coolstuff-provided (1.0-1 unstable [all])' aptget install coolstuff-provided -s
 
-testfailuremsg 'E: Conflict: coolstuff-provided-broken:i386=1.0-1 -> coolstuff-provided-broken:i386 -> extrastuff:i386=1.0-1 but not extrastuff:i386=1.0-1' aptget install coolstuff-provided-broken --solver 3.0 -s
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. extrastuff:i386=1.0-1 is not selected for install
+   2. extrastuff:i386=1.0-1 is selected for install because:
+      1. coolstuff-provided-broken:i386=1.0-1 is selected for install
+      2. coolstuff-provided-broken:i386 Depends cool2 | stuff-abi-2' aptget install coolstuff-provided-broken --solver 3.0 -s
 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-breaks b/test/integration/test-ignore-provides-if-versioned-breaks
index 27197e1e6..87e609bef 100755
--- a/test/integration/test-ignore-provides-if-versioned-breaks
+++ b/test/integration/test-ignore-provides-if-versioned-breaks
@@ -32,7 +32,12 @@ insertpackage 'unstable' 'foo-same-breaker-none' 'i386' '1.0' 'Breaks: foo-same'
 
 
 setupaptarchive
-testfailuremsg 'E: Conflict: foo-provider:i386=1.0 -> not foo-breaker-none:i386 but foo-breaker-none:i386=1.0 -> foo-breaker-none:i386' aptget install foo-provider foo-breaker-none -s --solver 3.0
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. foo-breaker-none:i386=1.0 is selected for install
+   2. foo-breaker-none:i386 is not selected for install because:
+      1. foo-provider:i386=1.0 is selected for install
+      2. foo-breaker-none:i386 Breaks foo
+         [selected 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
@@ -71,7 +76,12 @@ 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-breaker-none:i386=1.0 -> foo-foreign-breaker-none:i386 -> 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
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. foo-foreign-provider:i386=1.0 is selected for install
+   2. foo-foreign-provider:i386=1.0 is not selected for install because:
+      1. foo-foreign-breaker-none:i386=1.0 is selected for install
+      2. foo-foreign-breaker-none:i386 Breaks foo-foreign
+         [selected foo-foreign-breaker-none:i386]' 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
@@ -110,7 +120,12 @@ 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-provider:i386=1.0 -> not foo-same-breaker-none:i386 but foo-same-breaker-none:i386=1.0 -> foo-same-breaker-none:i386' aptget install foo-same-provider foo-same-breaker-none -s --solver 3.0
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. foo-same-breaker-none:i386=1.0 is selected for install
+   2. foo-same-breaker-none:i386 is not selected for install because:
+      1. foo-same-provider:i386=1.0 is selected for install
+      2. foo-same-breaker-none:i386 Breaks foo-same
+         [selected 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 caff5e3b0..cdf69656e 100755
--- a/test/integration/test-ignore-provides-if-versioned-conflicts
+++ b/test/integration/test-ignore-provides-if-versioned-conflicts
@@ -33,7 +33,12 @@ insertpackage 'unstable' 'foo-same-breaker-none' 'i386' '1.0' 'Conflicts: foo-sa
 
 setupaptarchive
 
-testfailuremsg 'E: Conflict: foo-provider:i386=1.0 -> not foo-breaker-none:i386 but foo-breaker-none:i386=1.0 -> foo-breaker-none:i386' aptget install foo-provider foo-breaker-none -s --solver 3.0
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. foo-breaker-none:i386=1.0 is selected for install
+   2. foo-breaker-none:i386 is not selected for install because:
+      1. foo-provider:i386=1.0 is selected for install
+      2. foo-breaker-none:i386 Conflicts foo
+         [selected 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
@@ -72,7 +77,12 @@ 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-breaker-none:i386=1.0 -> foo-foreign-breaker-none:i386 -> 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
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. foo-foreign-provider:i386=1.0 is selected for install
+   2. foo-foreign-provider:i386=1.0 is not selected for install because:
+      1. foo-foreign-breaker-none:i386=1.0 is selected for install
+      2. foo-foreign-breaker-none:i386 Conflicts foo-foreign
+         [selected foo-foreign-breaker-none:i386]' 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
@@ -111,7 +121,12 @@ 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-provider:i386=1.0 -> not foo-same-breaker-none:i386 but foo-same-breaker-none:i386=1.0 -> foo-same-breaker-none:i386' aptget install foo-same-provider foo-same-breaker-none -s --solver 3.0
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. foo-same-breaker-none:i386=1.0 is selected for install
+   2. foo-same-breaker-none:i386 is not selected for install because:
+      1. foo-same-provider:i386=1.0 is selected for install
+      2. foo-same-breaker-none:i386 Conflicts foo-same
+         [selected 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 9d8920e0f..ca13cc50d 100755
--- a/test/integration/test-multiarch-allowed
+++ b/test/integration/test-multiarch-allowed
@@ -64,18 +64,36 @@ 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: foo:amd64=1 -> not foo:i386 -> not needsfoo:i386 but needsfoo:i386=1 -> needsfoo:i386" aptget install needsfoo:i386 foo:amd64 -s --solver 3.0
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. needsfoo:i386=1 is selected for install
+   2. needsfoo:i386 Depends foo:i386
+      but none of the choices are installable:
+      - foo:i386 is not selected for install because:
+        1. foo:amd64=1 is selected for install
+        2. foo:i386 Conflicts foo" 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: foo:amd64=1 -> not foo:i386 -> not needsfoo:i386 but needsfoo:i386=1 -> needsfoo:i386" aptget install foo:amd64 needsfoo:i386 -s --solver 3.0
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. needsfoo:i386=1 is selected for install
+   2. needsfoo:i386 Depends foo:i386
+      but none of the choices are installable:
+      - foo:i386 is not selected for install because:
+        1. foo:amd64=1 is selected for install
+        2. foo:i386 Conflicts foo" 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: foo:i386=1 -> not foo:amd64 -> not needsfoo:amd64 but needsfoo:amd64=1 -> needsfoo:amd64" aptget install needsfoo foo:i386 -s --solver 3.0
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. needsfoo:amd64=1 is selected for install
+   2. needsfoo:amd64 Depends foo
+      but none of the choices are installable:
+      - foo:amd64 is not selected for install because:
+        1. foo:i386=1 is selected for install
+        2. foo:amd64 Conflicts foo:i386" 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
@@ -135,11 +153,19 @@ if [ "$APT_SOLVER" = "3.0" ]; then
 NEEDSFOO2NATIVE="$BADPREFIX
 The following packages have unmet dependencies:
  needsfoover2 : Depends: foo:any (>= 2)
-E: Unsatisfiable dependency group needsfoover2:amd64 -> foo:any:any"
+E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. needsfoover2:amd64=1 is selected for install
+   2. needsfoover2:amd64 Depends foo:any (>= 2)
+      but none of the choices are installable:
+      [no choices]"
 NEEDSFOO2FOREIGN="$BADPREFIX
 The following packages have unmet dependencies:
  needsfoover2:i386 : Depends: foo:any (>= 2)
-E: Unsatisfiable dependency group needsfoover2:i386 -> foo:any:any"
+E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. needsfoover2:i386=1 is selected for install
+   2. needsfoover2:i386 Depends foo:any (>= 2)
+      but none of the choices are installable:
+      [no choices]"
 else
 NEEDSFOO2NATIVE="$BADPREFIX
 The following packages have unmet dependencies:
@@ -156,9 +182,31 @@ testfailureequal "$NEEDSFOO2FOREIGN" aptget install needsfoover2:i386 foo:i386 -
 testfailureequal "$NEEDSFOO2NATIVE" aptget install needsfoover2 foo:i386 -s
 
 solveableinsinglearch2() {
-	testfailuremsg 'E: Conflict: hatesfoo:amd64=1 -> hatesfoo:amd64 -> not foo:amd64=1 but foo:amd64=1' aptget install foo hatesfoo -s --solver 3.0
-	testfailuremsg 'E: Conflict: hatesfooany:amd64=1 -> hatesfooany:amd64 -> not foo:amd64=1 but foo:amd64=1' aptget install foo hatesfooany -s --solver 3.0
-	testfailuremsg 'E: Conflict: hatesfoonative:amd64=1 -> hatesfoonative:amd64 -> not foo:amd64=1 but foo:amd64=1' aptget install foo hatesfoonative -s --solver 3.0
+	testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. foo:amd64=1 is selected for install
+   2. foo:amd64=1 is not selected for install because:
+      1. hatesfoo:amd64=1 is selected for install
+      2. hatesfoo:amd64 Conflicts foo' aptget install foo hatesfoo -s --solver 3.0
+
+	if [ "$(getarchitectures)" = "amd64 " ]; then
+		testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. foo:amd64=1 is selected for install
+   2. foo:amd64=1 is not selected for install because:
+      1. hatesfooany:amd64=1 is selected for install
+      2. hatesfooany:amd64 Conflicts foo:any' aptget install foo hatesfooany -s --solver 3.0
+	else
+		testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. foo:amd64=1 is selected for install
+   2. foo:amd64=1 is not selected for install because:
+      1. hatesfooany:amd64=1 is selected for install
+      2. hatesfooany:amd64 Conflicts foo:any
+         [selected hatesfooany:amd64]' aptget install foo hatesfooany -s --solver 3.0
+	fi
+	testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. foo:amd64=1 is selected for install
+   2. foo:amd64=1 is not selected for install because:
+      1. hatesfoonative:amd64=1 is selected for install
+      2. hatesfoonative:amd64 Conflicts foo:amd64' aptget install foo hatesfoonative -s --solver 3.0
 	testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  hatesfoo : Conflicts: foo but 1 is to be installed
@@ -171,12 +219,21 @@ The following packages have unmet dependencies:
 E: Unable to correct problems, you have held broken packages." aptget install foo hatesfoonative -s --solver internal
 }
 solveableinsinglearch2
-testfailuremsg "E: Conflict: hatesfoo:amd64=1 -> hatesfoo:amd64 -> not foo:i386=1 but foo:i386=1" aptget install foo:i386 hatesfoo -s --solver 3.0
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. foo:i386=1 is selected for install
+   2. foo:i386=1 is not selected for install because:
+      1. hatesfoo:amd64=1 is selected for install
+      2. hatesfoo:amd64 Conflicts foo:i386" aptget install foo:i386 hatesfoo -s --solver 3.0
 testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  hatesfoo : Conflicts: foo:i386 but 1 is to be installed
 E: Unable to correct problems, you have held broken packages." aptget install foo:i386 hatesfoo -s --solver internal
-testfailuremsg "E: Conflict: hatesfooany:amd64=1 -> hatesfooany:amd64 -> not foo:i386=1 but foo:i386=1" aptget install foo:i386 hatesfooany -s --solver 3.0
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. foo:i386=1 is selected for install
+   2. foo:i386=1 is not selected for install because:
+      1. hatesfooany:amd64=1 is selected for install
+      2. hatesfooany:amd64 Conflicts foo:any
+         [selected hatesfooany:amd64]" aptget install foo:i386 hatesfooany -s --solver 3.0
 testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  hatesfooany : Conflicts: foo:any
@@ -191,7 +248,11 @@ Inst hatesfoonative (1 unstable [amd64])
 Conf foo:i386 (1 unstable [i386])
 Conf hatesfoonative (1 unstable [amd64])' aptget install foo:i386 hatesfoonative -s
 
-testfailuremsg "E: Unsatisfiable dependency group needscoolfoo:i386 -> coolfoo:i386" aptget install needscoolfoo:i386 -s --solver 3.0
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. needscoolfoo:i386=1 is selected for install
+   2. needscoolfoo:i386 Depends coolfoo:i386
+      but none of the choices are installable:
+      [no choices]" aptget install needscoolfoo:i386 -s --solver 3.0
 testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  needscoolfoo:i386 : Depends: coolfoo:i386 but it is not installable
@@ -264,12 +325,20 @@ Inst needscoolfoover1 (1 unstable [amd64])
 Conf coolfoo (1 unstable [amd64])
 Conf coolfoover (1 unstable [amd64])
 Conf needscoolfoover1 (1 unstable [amd64])' aptget install needscoolfoover1 -s
-	testfailuremsg "E: Unsatisfiable dependency group needscoolfoover2:amd64 -> coolfoo:any:any" aptget install needscoolfoover2 -s --solver 3.0
+	testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. needscoolfoover2:amd64=1 is selected for install
+   2. needscoolfoover2:amd64 Depends coolfoo:any (>= 2)
+      but none of the choices are installable:
+      [no choices]" aptget install needscoolfoover2 -s --solver 3.0
 	testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  needscoolfoover2 : Depends: coolfoo:any (>= 2)
 E: Unable to correct problems, you have held broken packages." aptget install needscoolfoover2 -s --solver internal
-	testfailuremsg "E: Unsatisfiable dependency group needscoolfoover3:amd64 -> coolfoo:any:any" aptget install needscoolfoover3 -s --solver 3.0
+	testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. needscoolfoover3:amd64=1 is selected for install
+   2. needscoolfoover3:amd64 Depends coolfoo:any (>= 2)
+      but none of the choices are installable:
+      [no choices]" aptget install needscoolfoover3 -s --solver 3.0
 	testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  needscoolfoover3 : Depends: coolfoo:any (>= 2)
diff --git a/test/integration/test-multiarch-foreign b/test/integration/test-multiarch-foreign
index 5a7b1a3b7..a04b854a5 100755
--- a/test/integration/test-multiarch-foreign
+++ b/test/integration/test-multiarch-foreign
@@ -179,14 +179,23 @@ 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 -> not hates-foo:amd64 but hates-foo:amd64=1.0 -> hates-foo:amd64"  aptget install $1 hates-foo -s --solver 3.0
+	testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. hates-foo:amd64=1.0 is selected for install
+   2. hates-foo:amd64 is not selected for install because:
+      1. ${1%:*}:$4=1.0 is selected for install
+      2. hates-foo:amd64 Conflicts foo
+         [selected ${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
              Conflicts: foo:i386
              Conflicts: foo:armel
 E: Unable to correct problems, you have held broken packages." aptget install $1 hates-foo -s --solver internal
-	testfailuremsg "E: Conflict: $2:amd64=1.0 -> $2:amd64 -> not foo:$4=1.0 but foo:$4=1.0" aptget install $1 $2 -s --solver 3.0
+	testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. foo:$4=1.0 is selected for install
+   2. foo:$4=1.0 is not selected for install because:
+      1. $2:amd64=1.0 is selected for install
+      2. $2:amd64 Conflicts foo:$4" aptget install $1 $2 -s --solver 3.0
 	testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  $2 : Conflicts: foo:$4
diff --git a/test/integration/test-prefer-higher-priority-providers b/test/integration/test-prefer-higher-priority-providers
index e16e98e23..87954c5d4 100755
--- a/test/integration/test-prefer-higher-priority-providers
+++ b/test/integration/test-prefer-higher-priority-providers
@@ -91,7 +91,16 @@ Inst awesome (1 unstable [all])
 Conf baz (1 unstable [all])
 Conf awesome (1 unstable [all])" aptget install awesome foo- bar- -s
 
-testfailuremsg "E: Conflict: awesome:$native=1 -> awesome:$native -> baz:$native=1 -> baz:$native but not baz:$native" aptget install awesome foo- bar- baz- -s --solver 3.0
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. baz:$native is not selected for install
+   2. baz:$native=1 is selected for install because:
+      1. awesome:$native=1 is selected for install
+      2. awesome:$native Depends stuff
+         [selected awesome:$native]
+      For context, additional choices that could not be installed:
+      * In awesome:$native Depends stuff:
+        - foo:$native=1 is not selected for install
+        - bar:$native=1 is not selected for install" aptget install awesome foo- bar- baz- -s --solver 3.0
 testfailureequal "Reading package lists...
 Building dependency tree...
 Package 'foo' is not installed, so not removed
diff --git a/test/integration/test-release-candidate-switching b/test/integration/test-release-candidate-switching
index db7e29495..be5b3f997 100755
--- a/test/integration/test-release-candidate-switching
+++ b/test/integration/test-release-candidate-switching
@@ -449,7 +449,11 @@ The following information may help to resolve the situation:
 The following packages have unmet dependencies:
  uninstallablepkg : Depends: libmtp8 (>= 10:0.20.1) but it is not going to be installed
                     Depends: amarok-utils (= 2.3.2-2+exp) but it is not going to be installed
-E: Unsatisfiable dependency group uninstallablepkg:i386 -> libmtp8:i386" aptget install uninstallablepkg/experimental --trivial-only -V --solver 3.0
+E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. amarok-utils:i386=2.3.2-2+exp is not selected for install
+   2. amarok-utils:i386=2.3.2-2+exp is selected for install because:
+      1. uninstallablepkg:i386=1.0 is selected for install
+      2. uninstallablepkg:i386 Depends amarok-utils (= 2.3.2-2+exp)" aptget install uninstallablepkg/experimental --trivial-only -V --solver 3.0
 
 insertinstalledpackage 'libmtp8' 'i386'  '1'
 insertinstalledpackage 'amarok' 'i386' '3' 'Depends: amarok-common (= 3), libmtp8 (>= 1)'
diff --git a/test/integration/test-solver3-alternatives b/test/integration/test-solver3-alternatives
new file mode 100755
index 000000000..8a3645f82
--- /dev/null
+++ b/test/integration/test-solver3-alternatives
@@ -0,0 +1,32 @@
+#!/bin/sh
+set -e
+
+TESTDIR="$(readlink -f "$(dirname "$0")")"
+. "$TESTDIR/framework"
+setupenvironment
+configarchitecture 'amd64'
+
+insertpackage 'unstable' 'unsat' 'all' '3' 'Depends: a | b'
+insertpackage 'unstable' 'a' 'all' '3' 'Depends: aa|ab'
+insertpackage 'unstable' 'b' 'all' '3' 'Depends: ba|bb'
+insertpackage 'unstable' 'aa' 'all' '3' 'Depends: aax'
+insertpackage 'unstable' 'ab' 'all' '3' 'Depends: abx'
+insertpackage 'unstable' 'ba' 'all' '3' 'Depends: bay'
+insertpackage 'unstable' 'bb' 'all' '3' 'Depends: bby'
+setupaptarchive
+
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. bb:amd64 is selected for install because:
+      1. unsat:amd64=3 is selected for install
+      2. unsat:amd64 Depends a | b
+         [selected b:amd64 for install]
+      3. b:amd64 Depends ba | bb
+         [selected b:amd64]
+      For context, additional choices that could not be installed:
+      * In unsat:amd64 Depends a | b:
+        - a:amd64 is not selected for install
+      * In b:amd64 Depends ba | bb:
+        - ba:amd64 is not selected for install
+   2. bb:amd64 Depends bby
+      but none of the choices are installable:
+      [no choices]" apt install unsat --solver 3.0
diff --git a/test/integration/test-specific-architecture-dependencies b/test/integration/test-specific-architecture-dependencies
index be8ea4245..b9ce155de 100755
--- a/test/integration/test-specific-architecture-dependencies
+++ b/test/integration/test-specific-architecture-dependencies
@@ -194,7 +194,11 @@ The following NEW packages will be installed:
 Inst foo-depender (1 unstable [amd64])
 Conf foo-depender (1 unstable [amd64])' aptget install foo-depender -s
 
-testfailuremsg 'E: Unsatisfiable dependency group foo-depender:i386 -> foo:i386' aptget install foo-depender:i386 -s --solver 3.0
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. foo-depender:i386=1 is selected for install
+   2. foo-depender:i386 Depends foo:i386
+      but none of the choices are installable:
+      [no choices]' aptget install foo-depender:i386 -s --solver 3.0
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have
@@ -313,7 +317,11 @@ Remv libold [1]
 Inst breaker-x64 (1 unstable [amd64])
 Conf breaker-x64 (1 unstable [amd64])' aptget install breaker-x64:amd64 -s
 
-testfailuremsg 'E: Unsatisfiable dependency group depender-x32:amd64 -> libc6:i386:any' aptget install depender-x32 -s --solver 3.0
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. depender-x32:amd64=1 is selected for install
+   2. depender-x32:amd64 Depends libc6:i386
+      but none of the choices are installable:
+      [no choices]' aptget install depender-x32 -s --solver 3.0
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have