solver3: Only enqueue shared dependencies at the package level

Dependencies shared by all versions are enqueued at the package
level, so avoid enqueuing duplicates at the version level. This
presumably has no meaningful impact on performance, potentially
a negative performance impact on some workloads as we now need
to find the duplicates again; it can become useful when there
is a lot of backtracking.

More importantly though this improves error messages, because
now we can say that "all versions of foo depend on X", rather
than saying "foo=1 depends on X" and you are left wondering
why we did not select "foo=2".

In this commit though, improved error messages are not implemented,
they depend on redesigning the reason tracking to use clauses.

Also the rationale tracking includes a lot more dependencies of
the form "pkg:arch=version -> pkg:arch" which are annoying. Improved
error messages should fold them into one node.

22 files changed, 74 insertions, 65 deletions

diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc
index 945d912db..f2e4360ff 100644
--- a/apt-pkg/solver3.cc
+++ b/apt-pkg/solver3.cc
@@ -454,6 +454,10 @@ void APT::Solver::Discover(Var var)
       var = discoverQ.front();
       discoverQ.pop();
 
+      // Package needs to be discovered before the version to be able to dedup shared dependencies
+      if (auto Ver = var.Ver(cache); not Ver.end() && not(*this)[Ver.ParentPkg()].flags.discovered)
+	 var = Var(Ver.ParentPkg());
+
       auto &state = (*this)[var];
 
       if (state.flags.discovered)
@@ -495,6 +499,12 @@ void APT::Solver::Discover(Var var)
 	    pkgCache::DepIterator end;
 	    dep.GlobOr(start, end); // advances dep
 
+	    // This dependency is shared across all versions, skip it.
+	    if (auto &pkgClauses = (*this)[Ver.ParentPkg()].clauses;
+		std::any_of(pkgClauses.begin(), pkgClauses.end(), [start](auto &c)
+			    { return c->dep && c->dep->DependencyData == start->DependencyData; }))
+	       continue;
+
 	    auto clause = TranslateOrGroup(start, end, Var(Ver));
 
 	    RegisterClause(std::move(clause));
diff --git a/test/integration/test-apt-get-build-dep-barbarian b/test/integration/test-apt-get-build-dep-barbarian
index e070e96ca..48873c59b 100755
--- a/test/integration/test-apt-get-build-dep-barbarian
+++ b/test/integration/test-apt-get-build-dep-barbarian
@@ -83,7 +83,7 @@ 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 -> not foo:amd64=1 -> not builddeps:bad-amd64-i386-foo:i386=1 but builddeps:bad-amd64-i386-foo:i386=1'  apt build-dep bad-amd64-i386-foo -s -a i386 --solver 3.0
+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
 testfailureequal 'Reading package lists...
 Reading package lists...
 Building dependency tree...
@@ -96,7 +96,7 @@ 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 -> not foo:amd64=1 -> not builddeps:bad-amd64-i386-armel-foo:i386=1 but builddeps:bad-amd64-i386-armel-foo:i386=1' apt build-dep bad-amd64-i386-armel-foo -s -a i386 --solver 3.0
+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
 testfailureequal 'Reading package lists...
 Reading package lists...
 Building dependency tree...
@@ -115,7 +115,7 @@ 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 -> not foo:amd64=1 -> not builddeps:bad-amd64-i386-armel-foo:armel=1 but builddeps:bad-amd64-i386-armel-foo:armel=1"
+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"
 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 bd30cfcfd..8147bb0a3 100755
--- a/test/integration/test-apt-get-build-dep-file
+++ b/test/integration/test-apt-get-build-dep-file
@@ -160,7 +160,7 @@ 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=1 -> debhelper:armel' aptget build-dep --simulate ./foo-1.0 -a armel --solver 3.0
+E: Unsatisfiable dependency group builddeps:./foo-1.0:armel -> debhelper:armel' 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 5599586fd..1540db272 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: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
+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
 testfailureequal "Reading package lists...
 Building dependency tree...
 Note, selecting 'foo:i386' instead of './incoming/foo_1.0_i386.deb'
@@ -177,7 +177,7 @@ 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=0 -> pkg-as-it-should-be:amd64' aptget install -q=0 ./incoming/pkg-last-line-parse_0_all.deb --solver 3.0
+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 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 fc7e8050e..02a444dff 100755
--- a/test/integration/test-apt-get-satisfy
+++ b/test/integration/test-apt-get-satisfy
@@ -80,7 +80,7 @@ testrun 'External' 'Reading package lists...
 Building dependency tree...
 Execute external solver...' --solver apt
 
-testfailuremsg "E: Unsatisfiable dependency group satisfy:command-line:i386=1 -> depends:i386" aptget satisfy --simulate "depends (>= 2)" "Conflicts: conflicts:i386 (>= 1) [i386], conflicts:amd64 (>= 1) [amd64]" --solver 3.0
+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
 
 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 b974146ff..882f82b33 100755
--- a/test/integration/test-apt-get-source-only
+++ b/test/integration/test-apt-get-source-only
@@ -40,7 +40,7 @@ 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=1 -> foo-bd:amd64"
+E: Unsatisfiable dependency group builddeps:foo:amd64 -> foo-bd:amd64"
 
 BUILDDEPNOTFOO="Reading package lists...
 Building dependency tree...
@@ -52,7 +52,7 @@ 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=1 -> not-foo-bd:amd64"
+E: Unsatisfiable dependency group builddeps:not-foo:amd64 -> not-foo-bd:amd64"
 else
 BUILDDEPFOO="Reading package lists...
 Building dependency tree...
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 6b5e31eea..8abc7c854 100755
--- a/test/integration/test-bug-549968-install-depends-of-not-installed
+++ b/test/integration/test-bug-549968-install-depends-of-not-installed
@@ -37,7 +37,6 @@ Solving dependencies...Install coolstuff:i386 ()
 Delete extracoolstuff:i386
 [0] Reject:extracoolstuff:i386 ()
 [0] Install:coolstuff:i386 (coolstuff:i386=1.0)
-Optional Item (0@0) coolstuff:i386=1.0 ->  | extracoolstuff:i386
 Optional Item (0@0) coolstuff:i386 ->  | extracoolstuff:i386
 
 Recommended packages:
diff --git a/test/integration/test-bug-604222-new-and-autoremove b/test/integration/test-bug-604222-new-and-autoremove
index 8f464ae15..70dc4cac3 100755
--- a/test/integration/test-bug-604222-new-and-autoremove
+++ b/test/integration/test-bug-604222-new-and-autoremove
@@ -96,15 +96,15 @@ rm -f rootdir/var/lib/dpkg/status rootdir/var/lib/apt/extended_states
 if [ "$APT_SOLVER" = "3.0" ]; then
 CONFLICTING='Reading package lists...
 Building dependency tree...
-Solving dependencies...MANUAL dummy-archive:i386
+Solving dependencies...Install dummy-archive:i386 ()
 [0] Install:dummy-archive:i386=0.invalid.0 ()
 [0] Install:dummy-archive:i386 (dummy-archive:i386=0.invalid.0)
-[0] Install:libavcodec52:i386 (dummy-archive:i386=0.invalid.0)
-[0] Install:libavcodec52:i386=4:0.5.2-6 (dummy-archive:i386=0.invalid.0 -> libavcodec52:i386)
-[0] Reject:libvtk5-dev:i386=5.4.2-8 (dummy-archive:i386=0.invalid.0 -> libavcodec52:i386)
-[0] Reject:libvtk5-dev:i386 (dummy-archive:i386=0.invalid.0 -> libavcodec52:i386 -> not libvtk5-dev:i386=5.4.2-8)
-[0] Install:libopenal-dev:i386 (dummy-archive:i386=0.invalid.0)
-[0] Install:libopenal-dev:i386=1:1.12.854-2 (dummy-archive:i386=0.invalid.0 -> libopenal-dev:i386)
+[0] Install:libavcodec52:i386 (dummy-archive:i386=0.invalid.0 -> dummy-archive:i386)
+[0] Install:libavcodec52:i386=4:0.5.2-6 (dummy-archive:i386=0.invalid.0 -> dummy-archive:i386 -> libavcodec52:i386)
+[0] Reject:libvtk5-dev:i386=5.4.2-8 (dummy-archive:i386=0.invalid.0 -> dummy-archive:i386 -> libavcodec52:i386)
+[0] Reject:libvtk5-dev:i386 (dummy-archive:i386=0.invalid.0 -> dummy-archive:i386 -> libavcodec52:i386 -> not libvtk5-dev:i386=5.4.2-8)
+[0] Install:libopenal-dev:i386 (dummy-archive:i386=0.invalid.0 -> dummy-archive:i386)
+[0] Install:libopenal-dev:i386=1:1.12.854-2 (dummy-archive:i386=0.invalid.0 -> dummy-archive:i386 -> libopenal-dev:i386)
 
 The following additional packages will be installed:
   libavcodec52 libopenal-dev
diff --git a/test/integration/test-bug-632221-cross-dependency-satisfaction b/test/integration/test-bug-632221-cross-dependency-satisfaction
index 90cb8684f..d101bd1fa 100755
--- a/test/integration/test-bug-632221-cross-dependency-satisfaction
+++ b/test/integration/test-bug-632221-cross-dependency-satisfaction
@@ -35,7 +35,7 @@ insertsource 'unstable' 'source-specific-armel' 'armel' '1' 'Build-Depends: spec
 
 setupaptarchive
 
-testfailuremsg "E: Unsatisfiable dependency group builddeps:forbidden-no:armel=1 -> amdboot:any:any" aptget build-dep forbidden-no -s -a armel --solver 3.0
+testfailuremsg "E: Unsatisfiable dependency group builddeps:forbidden-no:armel -> amdboot:any:any" aptget build-dep forbidden-no -s -a armel --solver 3.0
 testfailureequal 'Reading package lists...
 Reading package lists...
 Building dependency tree...
@@ -49,7 +49,7 @@ 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=1 -> libc6:any:any" aptget build-dep forbidden-same -s -a armel --solver 3.0
+testfailuremsg "E: Unsatisfiable dependency group builddeps:forbidden-same:armel -> libc6:any:any" aptget build-dep forbidden-same -s -a armel --solver 3.0
 testfailureequal 'Reading package lists...
 Reading package lists...
 Building dependency tree...
@@ -63,7 +63,7 @@ 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=1 -> doxygen:any:any' aptget build-dep forbidden-foreign -s -a armel --solver 3.0
+testfailuremsg 'E: Unsatisfiable dependency group builddeps:forbidden-foreign:armel -> doxygen:any:any' 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-683786-build-dep-on-virtual-packages b/test/integration/test-bug-683786-build-dep-on-virtual-packages
index 45e40e20e..75f0a9626 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,7 @@ 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=1 -> po-debconf:armel' aptget build-dep -aarmel dash -s --solver 3.0
+testfailuremsg 'E: Unsatisfiable dependency group builddeps:dash:armel -> po-debconf:armel' aptget build-dep -aarmel dash -s --solver 3.0
 testfailureequal 'Reading package lists...
 Reading package lists...
 Building dependency tree...
@@ -55,7 +55,7 @@ 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=1 -> texi2html:armel' aptget build-dep -aarmel diffutils -s --solver 3.0
+testfailuremsg 'E: Unsatisfiable dependency group builddeps:diffutils:armel -> texi2html:armel' aptget build-dep -aarmel diffutils -s --solver 3.0
 testfailureequal 'Reading package lists...
 Reading package lists...
 Building dependency tree...
@@ -78,7 +78,7 @@ 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=1 -> libselinux-dev:armel' aptget build-dep -aarmel sed -s --solver 3.0
+testfailuremsg 'E: Unsatisfiable dependency group builddeps:sed:armel -> libselinux-dev:armel' 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 441bc29c2..17c3839d1 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,7 @@ 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=3 -> python3:mips:any'
+E: Unsatisfiable dependency group python-mips:amd64 -> python3:mips:any'
 else
 FAILLOG='Reading package lists...
 Building dependency tree...
diff --git a/test/integration/test-bug-960705-propagate-protected-to-satisfied-depends b/test/integration/test-bug-960705-propagate-protected-to-satisfied-depends
index 2f82e9df0..492958cb3 100755
--- a/test/integration/test-bug-960705-propagate-protected-to-satisfied-depends
+++ b/test/integration/test-bug-960705-propagate-protected-to-satisfied-depends
@@ -23,16 +23,16 @@ Building dependency tree...
 Solving dependencies...Install foobar:amd64 ()
 [0] Install:foobar:amd64=1 ()
 [0] Install:foobar:amd64 (foobar:amd64=1)
-[0] Install:requires-foo:amd64 (foobar:amd64=1)
-[0] Install:requires-foo:amd64=1 (foobar:amd64=1 -> requires-foo:amd64)
-[0] Install:foo:amd64 (foobar:amd64=1 -> requires-foo:amd64)
-[0] Install:foo:amd64=1 (foobar:amd64=1 -> requires-foo:amd64 -> foo:amd64)
-[0] Install:foo-depends:amd64 (foobar:amd64=1 -> requires-foo:amd64 -> foo:amd64)
-[0] Reject:conflicts-foo:amd64 (foobar:amd64=1 -> requires-foo:amd64 -> foo:amd64 -> foo:amd64=1)
-[0] Reject:conflicts-foo:amd64=1 (foobar:amd64=1 -> requires-foo:amd64 -> foo:amd64 -> foo:amd64=1)
-[0] Install:foo-depends:amd64=1 (foobar:amd64=1 -> requires-foo:amd64 -> foo:amd64 -> foo-depends:amd64)
-[0] Install:fine-foo:amd64 (foobar:amd64=1)
-[0] Install:fine-foo:amd64=1 (foobar:amd64=1 -> fine-foo:amd64)
+[0] Install:requires-foo:amd64 (foobar:amd64=1 -> foobar:amd64)
+[0] Install:requires-foo:amd64=1 (foobar:amd64=1 -> foobar:amd64 -> requires-foo:amd64)
+[0] Install:foo:amd64 (foobar:amd64=1 -> foobar:amd64 -> requires-foo:amd64)
+[0] Install:foo:amd64=1 (foobar:amd64=1 -> foobar:amd64 -> requires-foo:amd64 -> foo:amd64)
+[0] Install:foo-depends:amd64 (foobar:amd64=1 -> foobar:amd64 -> requires-foo:amd64 -> foo:amd64)
+[0] Reject:conflicts-foo:amd64 (foobar:amd64=1 -> foobar:amd64 -> requires-foo:amd64 -> foo:amd64 -> foo:amd64=1)
+[0] Install:foo-depends:amd64=1 (foobar:amd64=1 -> foobar:amd64 -> requires-foo:amd64 -> foo:amd64 -> foo-depends:amd64)
+[0] Install:fine-foo:amd64 (foobar:amd64=1 -> foobar:amd64)
+[0] Reject:conflicts-foo:amd64=1 (foobar:amd64=1 -> foobar:amd64 -> requires-foo:amd64 -> foo:amd64 -> foo:amd64=1 -> not conflicts-foo:amd64)
+[0] Install:fine-foo:amd64=1 (foobar:amd64=1 -> foobar:amd64 -> fine-foo:amd64)
 
 The following additional packages will be installed:
   fine-foo foo foo-depends requires-foo
diff --git a/test/integration/test-bug-961266-hold-means-hold b/test/integration/test-bug-961266-hold-means-hold
index b33a5aca7..8c18cd757 100755
--- a/test/integration/test-bug-961266-hold-means-hold
+++ b/test/integration/test-bug-961266-hold-means-hold
@@ -89,7 +89,7 @@ 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=1:2.26.2-1 but git-ng:amd64=1:2.26.2-1' apt install git-ng -s --solver 3.0
+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
 
 
 msgmsg 'Now mix it up by' 'holding git-cvs'
@@ -126,7 +126,7 @@ 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:amd64=1:2.26.2-1' apt install git-ng -s --solver 3.0
+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
 
 
 msgmsg 'Now mix it up by' 'holding both'
@@ -162,4 +162,4 @@ 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=1:2.26.2-1 but git-ng:amd64=1:2.26.2-1' apt install git-ng -s --solver 3.0
+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
diff --git a/test/integration/test-explore-or-groups-in-markinstall b/test/integration/test-explore-or-groups-in-markinstall
index 00e99875a..4c67296d7 100755
--- a/test/integration/test-explore-or-groups-in-markinstall
+++ b/test/integration/test-explore-or-groups-in-markinstall
@@ -171,7 +171,7 @@ 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 -> bad-conflict-level1:amd64 -> bad-conflict-level0:amd64 but bad-conflict-level2:amd64=1 -> not bad-conflict-level0:amd64" apt install bad-conflict-level2 -s --solver 3.0
+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
 
 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 50b158752..f9c436f81 100755
--- a/test/integration/test-handling-broken-orgroups
+++ b/test/integration/test-handling-broken-orgroups
@@ -47,7 +47,7 @@ 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=1.0-1 -> cool2:i386' aptget install coolstuff-broken --solver 3.0 -s
+testfailuremsg 'E: Unsatisfiable dependency group coolstuff-broken:i386 -> cool2:i386' 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 +95,7 @@ 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 -> extrastuff:i386=1.0-1 but not extrastuff:i386=1.0-1' aptget install coolstuff-provided-broken --solver 3.0 -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
 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 0263e8567..27197e1e6 100755
--- a/test/integration/test-ignore-provides-if-versioned-breaks
+++ b/test/integration/test-ignore-provides-if-versioned-breaks
@@ -32,7 +32,7 @@ insertpackage 'unstable' 'foo-same-breaker-none' 'i386' '1.0' 'Breaks: foo-same'
 
 
 setupaptarchive
-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
+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
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have
@@ -71,7 +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-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
+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
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have
@@ -110,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-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
+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
 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 7f0c357fa..caff5e3b0 100755
--- a/test/integration/test-ignore-provides-if-versioned-conflicts
+++ b/test/integration/test-ignore-provides-if-versioned-conflicts
@@ -33,7 +33,7 @@ insertpackage 'unstable' 'foo-same-breaker-none' 'i386' '1.0' 'Conflicts: foo-sa
 
 setupaptarchive
 
-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
+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
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have
@@ -72,7 +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-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
+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
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have
@@ -111,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-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
+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
 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 0e3903f1b..9d8920e0f 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 -> foo:i386 but foo:amd64=1 -> not foo:i386" aptget install needsfoo:i386 foo:amd64 -s --solver 3.0
+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
 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 -> foo:i386 but foo:amd64=1 -> not foo:i386" aptget install foo:amd64 needsfoo:i386 -s --solver 3.0
+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
 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 -> foo:amd64 but foo:i386=1 -> not foo:amd64" aptget install needsfoo foo:i386 -s --solver 3.0
+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
 testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  foo : Conflicts: foo:i386 but 1 is to be installed
@@ -135,11 +135,11 @@ 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=1 -> foo:any:any"
+E: Unsatisfiable dependency group needsfoover2:amd64 -> foo:any:any"
 NEEDSFOO2FOREIGN="$BADPREFIX
 The following packages have unmet dependencies:
  needsfoover2:i386 : Depends: foo:any (>= 2)
-E: Unsatisfiable dependency group needsfoover2:i386=1 -> foo:any:any"
+E: Unsatisfiable dependency group needsfoover2:i386 -> foo:any:any"
 else
 NEEDSFOO2NATIVE="$BADPREFIX
 The following packages have unmet dependencies:
@@ -156,9 +156,9 @@ testfailureequal "$NEEDSFOO2FOREIGN" aptget install needsfoover2:i386 foo:i386 -
 testfailureequal "$NEEDSFOO2NATIVE" aptget install needsfoover2 foo:i386 -s
 
 solveableinsinglearch2() {
-	testfailuremsg 'E: Conflict: hatesfoo:amd64=1 -> not foo:amd64=1 but foo:amd64=1' aptget install foo hatesfoo -s --solver 3.0
-	testfailuremsg 'E: Conflict: hatesfooany:amd64=1 -> not foo:amd64=1 but foo:amd64=1' aptget install foo hatesfooany -s --solver 3.0
-	testfailuremsg 'E: Conflict: hatesfoonative:amd64=1 -> not foo:amd64=1 but foo:amd64=1' aptget install foo hatesfoonative -s --solver 3.0
+	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
 	testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  hatesfoo : Conflicts: foo but 1 is to be installed
@@ -171,12 +171,12 @@ 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 -> not foo:i386=1 but foo:i386=1" aptget install foo:i386 hatesfoo -s --solver 3.0
+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
 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 -> not foo:i386=1 but foo:i386=1" aptget install foo:i386 hatesfooany -s --solver 3.0
+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
 testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  hatesfooany : Conflicts: foo:any
@@ -191,7 +191,7 @@ 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=1 -> coolfoo:i386" aptget install needscoolfoo:i386 -s --solver 3.0
+testfailuremsg "E: Unsatisfiable dependency group needscoolfoo:i386 -> coolfoo:i386" 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 +264,12 @@ 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=1 -> coolfoo:any:any" aptget install needscoolfoover2 -s --solver 3.0
+	testfailuremsg "E: Unsatisfiable dependency group needscoolfoover2:amd64 -> coolfoo:any:any" 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=1 -> coolfoo:any:any" aptget install needscoolfoover3 -s --solver 3.0
+	testfailuremsg "E: Unsatisfiable dependency group needscoolfoover3:amd64 -> coolfoo:any:any" 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 b356c64c7..5a7b1a3b7 100755
--- a/test/integration/test-multiarch-foreign
+++ b/test/integration/test-multiarch-foreign
@@ -179,14 +179,14 @@ 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: hates-foo:amd64=1.0 -> not ${1%:*}:$4=1.0 but ${1%:*}:$4=1.0"  aptget install $1 hates-foo -s --solver 3.0
+	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
 	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 -> not foo:$4=1.0 but foo:$4=1.0" aptget install $1 $2 -s --solver 3.0
+	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
 	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 76a03b3fb..e16e98e23 100755
--- a/test/integration/test-prefer-higher-priority-providers
+++ b/test/integration/test-prefer-higher-priority-providers
@@ -91,7 +91,7 @@ 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 -> baz:$native=1 -> baz:$native but not baz:$native" aptget install awesome foo- bar- baz- -s --solver 3.0
+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
 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 dfd59584f..db7e29495 100755
--- a/test/integration/test-release-candidate-switching
+++ b/test/integration/test-release-candidate-switching
@@ -449,7 +449,7 @@ 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=1.0 -> libmtp8:i386" aptget install uninstallablepkg/experimental --trivial-only -V --solver 3.0
+E: Unsatisfiable dependency group uninstallablepkg:i386 -> libmtp8:i386" 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-specific-architecture-dependencies b/test/integration/test-specific-architecture-dependencies
index ca39f18d8..be8ea4245 100755
--- a/test/integration/test-specific-architecture-dependencies
+++ b/test/integration/test-specific-architecture-dependencies
@@ -194,7 +194,7 @@ 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=1 -> foo:i386' aptget install foo-depender:i386 -s --solver 3.0
+testfailuremsg 'E: Unsatisfiable dependency group foo-depender:i386 -> foo:i386' 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 +313,7 @@ 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=1 -> libc6:i386:any' aptget install depender-x32 -s --solver 3.0
+testfailuremsg 'E: Unsatisfiable dependency group depender-x32:amd64 -> libc6:i386:any' 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