solver3: Use a propagation queue

Instead of directly propagating in a recursive fashion,
queue propagations in a queue and work on them in a loop
per the miniSAT paper.

We call Propagate() only at the end of the FromDepCache()
function and then in the Solve loop. Delaying the initial
propagation means that we get a stronger reasoning:

Assume you have x->a->b->c, y->c and you install x,y:
- Previously we traversed: x, y, x->a, a->b, b->c, (y->c)
- but now we traverse:     x, y, x->a, y->c, a->b, (b->c)
Notably c now has the implication y->c instead of x->a->b->c.

Inside the solver we need to call Propagate in a loop:
Propagating facts can fail and we then backtrack. If backtracking
is succesful, we have gained a new fact to propagate.

12 files changed, 21 insertions, 33 deletions

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