solver3: Defer version selection where possible

If a dependency can be satisfied by all versions of a package,
add the package to the clause instead of the version object.

This works only if there are no providers for the package: Providers
are quite hard to enumerate over and make sure that all versions of
a package satisfy the provider dependency.

Implement arbitrary selection between packages and versions for
the CompareProviders class: We pick the best version for each package
and then pit them against each other.

9 files changed, 37 insertions, 31 deletions

diff --git a/test/integration/test-apt-never-markauto-sections b/test/integration/test-apt-never-markauto-sections
index 33b790871..e60a6e648 100755
--- a/test/integration/test-apt-never-markauto-sections
+++ b/test/integration/test-apt-never-markauto-sections
@@ -49,7 +49,7 @@ Remv foreignpkg:i386 [1]
 Remv nosection [1]
 Remv texteditor [1]' aptget autoremove mydesktop -s
 
-testfailuremsg 'E: Conflict: not texteditor:amd64 -> not texteditor:amd64=1 -> not mydesktop-core:amd64=1 but mydesktop:amd64 -> mydesktop-core:amd64=1' aptget autoremove texteditor -s --solver 3.0 #-o Debug::pkgDepCache::AutoInstall=1 -o Debug::pkgProblemResolver=1 -o Debug::pkgDepCache::Marker=1
+testfailuremsg 'E: Conflict: not texteditor:amd64 -> not texteditor:amd64=1 -> not mydesktop-core:amd64=1 but mydesktop:amd64 -> mydesktop-core:amd64 -> mydesktop-core:amd64=1' aptget autoremove texteditor -s --solver 3.0 #-o Debug::pkgDepCache::AutoInstall=1 -o Debug::pkgProblemResolver=1 -o Debug::pkgDepCache::Marker=1
 testsuccessequal 'Reading package lists...
 Building dependency tree...
 Reading state information...
diff --git a/test/integration/test-bug-549968-install-depends-of-not-installed b/test/integration/test-bug-549968-install-depends-of-not-installed
index ec730c7b2..7c4e76fd9 100755
--- a/test/integration/test-bug-549968-install-depends-of-not-installed
+++ b/test/integration/test-bug-549968-install-depends-of-not-installed
@@ -38,8 +38,8 @@ Delete extracoolstuff:i386
 [0] Reject:extracoolstuff:i386 ()
 [0] Install:coolstuff:i386 (coolstuff:i386=1.0)
 [0] Reject:extracoolstuff:i386=1.0 (not extracoolstuff:i386)
-Optional Item (0@0) coolstuff:i386 ->  | extracoolstuff:i386=1.0
-Optional Item (0@0) coolstuff:i386=1.0 ->  | extracoolstuff:i386=1.0
+Optional Item (0@0) coolstuff:i386=1.0 ->  | extracoolstuff:i386
+Optional Item (0@0) coolstuff:i386 ->  | extracoolstuff:i386
 
 Recommended packages:
   extracoolstuff
diff --git a/test/integration/test-bug-601961-install-info b/test/integration/test-bug-601961-install-info
index 809ebf3c3..6d68372b5 100755
--- a/test/integration/test-bug-601961-install-info
+++ b/test/integration/test-bug-601961-install-info
@@ -60,4 +60,4 @@ The following information may help to resolve the situation:
 
 The following packages have unmet dependencies:
  findutils : Depends: essentialpkg but it is not going to be installed
-E: Conflict: findutils:i386 -> essentialpkg:i386=4.13a.dfsg.1-6 but not essentialpkg:i386 -> not essentialpkg:i386=4.13a.dfsg.1-6' aptget remove essentialpkg --trivial-only --solver 3.0
+E: Conflict: findutils:i386 -> essentialpkg:i386 but not essentialpkg:i386' aptget remove essentialpkg --trivial-only --solver 3.0
diff --git a/test/integration/test-bug-604222-new-and-autoremove b/test/integration/test-bug-604222-new-and-autoremove
index 1090e8b93..1bd7c5101 100755
--- a/test/integration/test-bug-604222-new-and-autoremove
+++ b/test/integration/test-bug-604222-new-and-autoremove
@@ -99,13 +99,13 @@ Building dependency tree...
 Solving dependencies...MANUAL 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=4:0.5.2-6 (dummy-archive:i386=0.invalid.0)
-[0] Install:libavcodec52:i386 (dummy-archive:i386=0.invalid.0 -> libavcodec52:i386=4:0.5.2-6)
-[0] Reject:libvtk5-dev:i386=5.4.2-8 (dummy-archive:i386=0.invalid.0 -> libavcodec52:i386=4:0.5.2-6)
-[0] Reject:libvtk5-dev:i386 (dummy-archive:i386=0.invalid.0 -> libavcodec52:i386=4:0.5.2-6 -> not libvtk5-dev:i386=5.4.2-8)
-Item (1@0) dummy-archive:i386=0.invalid.0 ->  | libvtk5-dev:i386=5.4.2-8 | libopenal-dev:i386=1:1.12.854-2
-[0] Install:libopenal-dev:i386=1:1.12.854-2 (dummy-archive:i386=0.invalid.0)
-[0] Install:libopenal-dev:i386 (dummy-archive:i386=0.invalid.0 -> libopenal-dev:i386=1:1.12.854-2)
+[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)
+Item (1@0) dummy-archive:i386=0.invalid.0 ->  | libvtk5-dev:i386 | libopenal-dev:i386
+[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)
 
 The following additional packages will be installed:
   libavcodec52 libopenal-dev
diff --git a/test/integration/test-bug-612557-garbage-upgrade b/test/integration/test-bug-612557-garbage-upgrade
index f695b499e..4ef241cad 100755
--- a/test/integration/test-bug-612557-garbage-upgrade
+++ b/test/integration/test-bug-612557-garbage-upgrade
@@ -18,7 +18,7 @@ testsuccess aptmark markauto python-uno openoffice.org-common
 testmarkedauto python-uno openoffice.org-common
 
 # The 3.0 solver does not remove openoffice.org-emailmerge because it is manually installed.
-testfailuremsg "E: Conflict: python-uno:i386=1:3.3.0-2 -> libreoffice-common:i386=1:3.3.0-2 -> not openoffice.org-common:i386=1:3.2.1-11+squeeze2 but openoffice.org-emailmerge:i386 -> openoffice.org-common:i386=1:3.2.1-11+squeeze2" aptget --trivial-only install python-uno --solver 3.0
+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
 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 90965eb22..8ba750b44 100755
--- a/test/integration/test-bug-618848-always-respect-user-requests
+++ b/test/integration/test-bug-618848-always-respect-user-requests
@@ -14,7 +14,7 @@ insertpackage 'unstable' 'exim4-daemon-heavy' 'all' '1.0' 'Depends: libdb4.8'
 setupaptarchive
 
 # This does not work in 3.0 solver: We do not remove manually installed packages.
-testfailuremsg "E: Conflict: exim4-daemon-light:i386 -> libdb4.8:i386=1.0 but not libdb4.8:i386 -> not libdb4.8:i386=1.0" aptget remove libdb4.8 --solver 3.0 -s
+testfailuremsg "E: Conflict: exim4-daemon-light:i386 -> libdb4.8:i386 but not libdb4.8:i386" aptget remove libdb4.8 --solver 3.0 -s
 allowremovemanual
 testsuccessequal "Reading package lists...
 Building dependency tree...
diff --git a/test/integration/test-bug-735967-lib32-to-i386-unavailable b/test/integration/test-bug-735967-lib32-to-i386-unavailable
index a44e58570..2eedf22ab 100755
--- a/test/integration/test-bug-735967-lib32-to-i386-unavailable
+++ b/test/integration/test-bug-735967-lib32-to-i386-unavailable
@@ -50,7 +50,7 @@ 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=1 -> libfoo-bin:amd64' aptget install foo -s --solver 3.0
+testfailuremsg 'E: Unsatisfiable dependency group libfoo:amd64 -> libfoo-bin:amd64' 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-960705-propagate-protected-to-satisfied-depends b/test/integration/test-bug-960705-propagate-protected-to-satisfied-depends
index e5a12986d..a203fe06e 100755
--- a/test/integration/test-bug-960705-propagate-protected-to-satisfied-depends
+++ b/test/integration/test-bug-960705-propagate-protected-to-satisfied-depends
@@ -23,20 +23,20 @@ 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=1 (foobar:amd64=1)
-[0] Install:requires-foo:amd64 (foobar:amd64=1 -> requires-foo:amd64=1)
-[0] Install:foo:amd64=1 (foobar:amd64=1 -> requires-foo:amd64=1)
-[0] Install:foo:amd64 (foobar:amd64=1 -> requires-foo:amd64=1 -> foo:amd64=1)
-[0] Install:foo-depends:amd64=1 (foobar:amd64=1 -> requires-foo:amd64=1 -> foo:amd64=1)
-[0] Install:foo-depends:amd64 (foobar:amd64=1 -> requires-foo:amd64=1 -> foo:amd64=1 -> foo-depends:amd64=1)
-Item (2@0) foobar:amd64=1 ->  | conflicts-foo:amd64=1 | fine-foo:amd64=1
-[1] Install:conflicts-foo:amd64=1 (foobar:amd64=1)
-[1] Install:conflicts-foo:amd64 (foobar:amd64=1 -> conflicts-foo:amd64=1)
-[0] Reject:conflicts-foo:amd64=1 ()
-[0] Reject:conflicts-foo:amd64 (not conflicts-foo:amd64=1)
-Item (1@0) foobar:amd64=1 ->  | conflicts-foo:amd64=1 | fine-foo:amd64=1
-[0] Install:fine-foo:amd64=1 (foobar:amd64=1)
-[0] Install:fine-foo:amd64 (foobar:amd64=1 -> fine-foo: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] Install:foo-depends:amd64=1 (foobar:amd64=1 -> requires-foo:amd64 -> foo:amd64 -> foo-depends:amd64)
+Item (2@0) foobar:amd64=1 ->  | conflicts-foo:amd64 | fine-foo:amd64
+[1] Install:conflicts-foo:amd64 (foobar:amd64=1)
+[1] Install:conflicts-foo:amd64=1 (foobar:amd64=1 -> conflicts-foo:amd64)
+[0] Reject:conflicts-foo:amd64 ()
+[0] Reject:conflicts-foo:amd64=1 (not conflicts-foo:amd64)
+Item (1@0) foobar:amd64=1 ->  | conflicts-foo:amd64 | fine-foo:amd64
+[0] Install:fine-foo:amd64 (foobar:amd64=1)
+[0] Install:fine-foo:amd64=1 (foobar:amd64=1 -> fine-foo:amd64)
 
 The following additional packages will be installed:
   fine-foo foo foo-depends requires-foo
diff --git a/test/integration/test-multiarch-allowed b/test/integration/test-multiarch-allowed
index 4b795bd5e..9fc49275a 100755
--- a/test/integration/test-multiarch-allowed
+++ b/test/integration/test-multiarch-allowed
@@ -64,18 +64,24 @@ 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=1 but foo:amd64=1 -> not foo:i386=1" aptget install needsfoo:i386 foo:amd64 -s --solver 3.0
+testfailuremsg "E: Conflict: needsfoo:i386=1 -> foo:i386 but no versions are installable
+E: Uninstallable version: foo:amd64=1 -> not foo:i386=1
+E: Uninstallable version: foo:amd64=1 -> not foo:i386=1" aptget install needsfoo:i386 foo:amd64 -s --solver 3.0
 testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  foo : Conflicts: foo:i386 but 1 is to be installed
  foo:i386 : Conflicts: foo but 1 is to be installed
 E: Unable to correct problems, you have held broken packages." aptget install needsfoo:i386 foo:amd64 -s --solver internal
-testfailuremsg "E: Conflict: needsfoo:i386=1 -> foo:i386=1 but foo:amd64=1 -> not foo:i386=1" aptget install foo:amd64 needsfoo:i386 -s --solver 3.0
+testfailuremsg "E: Conflict: needsfoo:i386=1 -> foo:i386 but no versions are installable
+E: Uninstallable version: foo:amd64=1 -> not foo:i386=1
+E: Uninstallable version: foo:amd64=1 -> not foo:i386=1" aptget install foo:amd64 needsfoo:i386 -s --solver 3.0
 testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  needsfoo:i386 : Depends: foo:i386 but it is not installable
 E: Unable to correct problems, you have held broken packages." aptget install foo:amd64 needsfoo:i386 -s --solver internal
-testfailuremsg "E: Conflict: needsfoo:amd64=1 -> foo:amd64=1 but foo:i386=1 -> not foo:amd64=1" aptget install needsfoo foo:i386 -s --solver 3.0
+testfailuremsg "E: Conflict: needsfoo:amd64=1 -> foo:amd64 but no versions are installable
+E: Uninstallable version: foo:i386=1 -> not foo:amd64=1
+E: Uninstallable version: foo:i386=1 -> not foo:amd64=1" aptget install needsfoo foo:i386 -s --solver 3.0
 testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  foo : Conflicts: foo:i386 but 1 is to be installed