Merge branch 'solver3' into 'main'

solver3: Unit propagation queues

See merge request apt-team/apt!440

17 files changed, 146 insertions, 93 deletions

diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc
index da80222e8..6f445328c 100644
--- a/apt-pkg/solver3.cc
+++ b/apt-pkg/solver3.cc
@@ -187,8 +187,13 @@ bool APT::Solver::Work::operator<(APT::Solver::Work const &b) const
       return not b.optional && b.size < 2;
    if (group != b.group)
       return group > b.group;
-   if (optional && b.optional && reason.empty() != b.reason.empty())
-      return reason.empty();
+   if (optional && b.optional)
+   {
+      if ((size < 2) != (b.size < 2))
+	 return b.size < 2;
+      if (reason.empty() != b.reason.empty())
+	 return reason.empty();
+   }
    // An optional item is less important than a required one.
    if (optional != b.optional)
       return optional;
@@ -337,60 +342,25 @@ bool APT::Solver::Enqueue(Var var, bool decision, Var reason)
       std::cerr << "[" << depth() << "] " << (decision ? "Install" : "Reject") << ":" << var.toString(cache) << " (" << WhyStr(state.reason) << ")\n";
 
    solved.push_back(Solved{var, std::nullopt});
+   propQ.push(var);
 
    if (not decision)
-   {
-      if (not PropagateReject(var))
-	 return false;
       needsRescore = true;
-   }
-   else
-   {
-      if (not PropagateInstall(var))
-	 return false;
-   }
+
    return true;
 }
 
-bool APT::Solver::Install(pkgCache::PkgIterator Pkg, Var reason, Group group)
+bool APT::Solver::Propagate()
 {
-   if ((*this)[Pkg].decision == Decision::MUST)
-      return true;
-
-   // Note decision
-   if (not Enqueue(Var(Pkg), true, reason))
-      return false;
-
-   bool anyInstallable = false;
-   // Insert the work item.
-   Work workItem{Var(Pkg), depth(), group};
-   for (auto ver = Pkg.VersionList(); not ver.end(); ver++)
-   {
-      workItem.solutions.push_back(ver);
-      if ((*this)[ver].decision != Decision::MUSTNOT)
-	 anyInstallable = true;
-   }
-
-   if (not anyInstallable)
+   while (!propQ.empty())
    {
-      _error->Error("Conflict: %s -> %s but no versions are installable",
-		    WhyStr(reason).c_str(), Pkg.FullName().c_str());
-      for (auto ver = Pkg.VersionList(); not ver.end(); ver++)
-	 _error->Error("Uninstallable version: %s", WhyStr(Var(ver)).c_str());
-      return false;
+      Var var = propQ.front();
+      propQ.pop();
+      if ((*this)[var].decision == Decision::MUST && not PropagateInstall(var))
+	 return false;
+      else if ((*this)[var].decision == Decision::MUSTNOT && not PropagateReject(var))
+	 return false;
    }
-
-   std::stable_sort(workItem.solutions.begin(), workItem.solutions.end(), CompareProviders3{cache, policy, Pkg, *this});
-   assert(workItem.solutions.size() > 0);
-
-   if (workItem.solutions.size() > 1 || workItem.optional)
-      AddWork(std::move(workItem));
-   else if (not Enqueue(Var(pkgCache::VerIterator(cache, workItem.solutions[0])), true, workItem.reason))
-      return false;
-
-   if (not EnqueueCommonDependencies(Pkg))
-      return false;
-
    return true;
 }
 
@@ -398,6 +368,40 @@ bool APT::Solver::PropagateInstall(Var var)
 {
    if (auto Pkg = var.Pkg(cache); not Pkg.end())
    {
+      bool anyInstallable = false;
+      bool anyMust = false;
+      // Insert the work item.
+      Work workItem{Var(Pkg), depth(), Group::SelectVersion};
+      for (auto ver = Pkg.VersionList(); not ver.end(); ver++)
+      {
+	 workItem.solutions.push_back(ver);
+	 if ((*this)[ver].decision != Decision::MUSTNOT)
+	    anyInstallable = true;
+	 if ((*this)[ver].decision == Decision::MUST)
+	    anyMust = true;
+      }
+
+      if (not anyInstallable)
+      {
+	 _error->Error("Conflict: %s -> %s but no versions are installable",
+		       WhyStr((*this)[Pkg].reason).c_str(), Pkg.FullName().c_str());
+	 for (auto ver = Pkg.VersionList(); not ver.end(); ver++)
+	    _error->Error("Uninstallable version: %s", WhyStr(Var(ver)).c_str());
+	 return false;
+      }
+
+      std::stable_sort(workItem.solutions.begin(), workItem.solutions.end(), CompareProviders3{cache, policy, Pkg, *this});
+      assert(workItem.solutions.size() > 0);
+
+      if (workItem.solutions.size() > 1 || workItem.optional)
+	 AddWork(std::move(workItem));
+      else if (not Enqueue(Var(pkgCache::VerIterator(cache, workItem.solutions[0])), true, workItem.reason))
+	 return false;
+
+      // FIXME: We skip enqueuing duplicate common dependencies if we already selected a version, but
+      // we should not have common dependencies duplicated in the version objects anyway.
+      if (not anyMust && not EnqueueCommonDependencies(Pkg))
+	 return false;
    }
    else if (auto Ver = var.Ver(cache); not Ver.end())
    {
@@ -598,8 +602,6 @@ bool APT::Solver::EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepItera
 	 return true;
       }
    }
-   else if (workItem.optional && start.ParentPkg()->CurrentVer == 0)
-      workItem.group = Group::NewUnsatRecommends;
 
    if (not workItem.solutions.empty())
    {
@@ -827,8 +829,17 @@ void APT::Solver::RescoreWorkIfNeeded()
 
 bool APT::Solver::Solve()
 {
-   while (not work.empty())
+   while (true)
    {
+      while (not Propagate())
+      {
+	 if (not Pop())
+	    return false;
+      }
+
+      if (work.empty())
+	 break;
+
       // Rescore the work if we need to
       RescoreWorkIfNeeded();
       // *NOW* we can pop the item.
@@ -894,7 +905,7 @@ bool APT::Solver::Solve()
 	 }
 	 if (unlikely(debug >= 3))
 	    std::cerr << "(try it: " << ver.ParentPkg().FullName() << "=" << ver.VerStr() << ")\n";
-	 if (not Enqueue(Var(pkgCache::VerIterator(cache, ver)), true, item.reason) && not Pop())
+	 if (not Enqueue(Var(ver), true, item.reason) && not Pop())
 	    return false;
 	 foundSolution = true;
 	 break;
@@ -984,7 +995,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache)
 	 if (not isOptional)
 	 {
 	    // Pre-empt the non-optional requests, as we don't want to queue them, we can just "unit propagate" here.
-	    if (depcache[P].Keep() ? not Install(P, {}, Group) : not Enqueue(Var(depcache.GetCandidateVersion(P)), true, {}))
+	    if (depcache[P].Keep() ? not Enqueue(Var(P), true, {}) : not Enqueue(Var(depcache.GetCandidateVersion(P)), true, {}))
 	       return false;
 	 }
 	 else
@@ -998,7 +1009,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache)
       }
    }
 
-   return true;
+   return Propagate();
 }
 
 bool APT::Solver::ToDepCache(pkgDepCache &depcache)
diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h
index a643d5d07..4f6f83d15 100644
--- a/apt-pkg/solver3.h
+++ b/apt-pkg/solver3.h
@@ -46,7 +46,6 @@ class Solver
    enum class Group : uint8_t
    {
       HoldOrDelete,
-      NewUnsatRecommends,
 
       // Satisfying dependencies on entirely new packages first is a good idea because
       // it may contain replacement packages like libfoo1t64 whereas we later will see
@@ -57,6 +56,9 @@ class Solver
       // try it last.
       SatisfyObsolete,
 
+      // Select a version of a package chosen for install.
+      SelectVersion,
+
       // My intuition tells me that we should try to schedule upgrades first, then
       // any non-obsolete installed packages, and only finally obsolete ones, such
       // that newer packages guide resolution of dependencies for older ones, they
@@ -130,6 +132,9 @@ class Solver
    // queue to be concerned about
    std::vector<Solved> solved{};
 
+   // \brief Propagation queue
+   std::queue<Var> propQ;
+
    // \brief Current decision level.
    //
    // This is an index into the solved vector.
@@ -153,6 +158,8 @@ class Solver
    bool RejectReverseDependencies(pkgCache::VerIterator Ver);
    // \brief Enqueue a single or group
    bool EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepIterator end, Var reason);
+   // \brief Propagate all pending propagations
+   bool Propagate();
    // \brief Propagate a "true" value of a variable
    bool PropagateInstall(Var var);
    // \brief Propagate a rejection of a variable
@@ -184,9 +191,6 @@ class Solver
    // Enqueue a decision fact
    bool Enqueue(Var var, bool decision, Var reason);
 
-   // \brief Mark the package for install. This is annoying as it incurs a decision
-   bool Install(pkgCache::PkgIterator Pkg, Var reason, Group group);
-
    // \brief Apply the selections from the dep cache to the solver
    bool FromDepCache(pkgDepCache &depcache);
    // \brief Apply the solver result to the depCache
diff --git a/test/integration/solver3.broken b/test/integration/solver3.broken
index dd06ed0eb..2212c34ae 100644
--- a/test/integration/solver3.broken
+++ b/test/integration/solver3.broken
@@ -6,12 +6,10 @@ test-apt-install-file-reltag
 test-apt-install-order-matters-a-bit
 test-apt-move-and-forget-manual-sections
 test-apt-patterns
-test-apt-source-and-build-dep
 test-bug-470115-new-and-tighten-recommends
 test-bug-602412-dequote-redirect
 test-bug-611729-mark-as-manual
 test-bug-675449-essential-are-protected
-test-bug-709560-set-candidate-release
 test-bug-745046-candidate-propagation-fails
 test-bug-753297-upgradable
 test-bug-767891-force-essential-important
diff --git a/test/integration/test-apt-get-install-deb b/test/integration/test-apt-get-install-deb
index 6cbd25c9f..5599586fd 100755
--- a/test/integration/test-apt-get-install-deb
+++ b/test/integration/test-apt-get-install-deb
@@ -32,7 +32,7 @@ done
 
 buildsimplenativepackage 'foo' 'i386,amd64' '1.0'
 
-testfailuremsg "E: Conflict:  -> foo:amd64=1.0 but foo:i386=1.0 -> not foo:amd64=1.0" aptget install ./incoming/foo_1.0_i386.deb ./incoming/foo_1.0_amd64.deb -s --solver 3.0
+testfailuremsg "E: Conflict: foo:i386=1.0 -> not foo:amd64=1.0 but foo:amd64=1.0" aptget install ./incoming/foo_1.0_i386.deb ./incoming/foo_1.0_amd64.deb -s --solver 3.0
 testfailureequal "Reading package lists...
 Building dependency tree...
 Note, selecting 'foo:i386' instead of './incoming/foo_1.0_i386.deb'
diff --git a/test/integration/test-apt-never-markauto-sections b/test/integration/test-apt-never-markauto-sections
index 85412b17b..33b790871 100755
--- a/test/integration/test-apt-never-markauto-sections
+++ b/test/integration/test-apt-never-markauto-sections
@@ -49,7 +49,7 @@ Remv foreignpkg:i386 [1]
 Remv nosection [1]
 Remv texteditor [1]' aptget autoremove mydesktop -s
 
-testfailuremsg 'E: Conflict: not texteditor:amd64 -> not texteditor:amd64=1 -> not bad-texteditor:amd64=1 -> not mydesktop-core:amd64=1 but mydesktop:amd64 -> mydesktop:amd64=1 -> mydesktop-core:amd64=1' aptget autoremove texteditor -s --solver 3.0 #-o Debug::pkgDepCache::AutoInstall=1 -o Debug::pkgProblemResolver=1 -o Debug::pkgDepCache::Marker=1
+testfailuremsg 'E: Conflict: not texteditor:amd64 -> not texteditor:amd64=1 -> not mydesktop-core:amd64=1 but mydesktop:amd64 -> mydesktop-core:amd64=1' aptget autoremove texteditor -s --solver 3.0 #-o Debug::pkgDepCache::AutoInstall=1 -o Debug::pkgProblemResolver=1 -o Debug::pkgDepCache::Marker=1
 testsuccessequal 'Reading package lists...
 Building dependency tree...
 Reading state information...
diff --git a/test/integration/test-bug-549968-install-depends-of-not-installed b/test/integration/test-bug-549968-install-depends-of-not-installed
index 76219290a..33cbd6ee4 100755
--- a/test/integration/test-bug-549968-install-depends-of-not-installed
+++ b/test/integration/test-bug-549968-install-depends-of-not-installed
@@ -34,9 +34,9 @@ Building dependency tree...
 Package 'extracoolstuff' is not installed, so not removed
 Solving dependencies...Install coolstuff:i386 ()
 [0] Install:coolstuff:i386=1.0 ()
-[0] Install:coolstuff:i386 (coolstuff:i386=1.0)
 Delete extracoolstuff:i386
 [0] Reject:extracoolstuff:i386 ()
+[0] Install:coolstuff:i386 (coolstuff:i386=1.0)
 [0] Reject:extracoolstuff:i386=1.0 (not extracoolstuff:i386)
 Optional Item (0@0) coolstuff:i386=1.0 ->  | extracoolstuff:i386=1.0
 
diff --git a/test/integration/test-bug-598669-install-postfix-gets-exim-heavy b/test/integration/test-bug-598669-install-postfix-gets-exim-heavy
index e27ddb2db..d721bdaa8 100755
--- a/test/integration/test-bug-598669-install-postfix-gets-exim-heavy
+++ b/test/integration/test-bug-598669-install-postfix-gets-exim-heavy
@@ -7,7 +7,7 @@ setupenvironment
 configarchitecture "i386"
 setupaptarchive
 
-testfailuremsg "E: Conflict:  -> postfix:i386=2.7.1-1 but exim4-daemon-light:i386 -> exim4-daemon-light:i386=4.72-1 -> not postfix:i386=2.7.1-1" aptget install postfix --solver 3.0
+testfailuremsg "E: Conflict: exim4-daemon-light:i386 -> exim4-daemon-light:i386=4.72-1 -> not postfix:i386=2.7.1-1 but postfix:i386=2.7.1-1" aptget install postfix --solver 3.0
 allowremovemanual
 testfailureequal "Reading package lists...
 Building dependency tree...
diff --git a/test/integration/test-bug-601961-install-info b/test/integration/test-bug-601961-install-info
index 94a5ad2cf..809ebf3c3 100755
--- a/test/integration/test-bug-601961-install-info
+++ b/test/integration/test-bug-601961-install-info
@@ -60,4 +60,4 @@ The following information may help to resolve the situation:
 
 The following packages have unmet dependencies:
  findutils : Depends: essentialpkg but it is not going to be installed
-E: Conflict:  -> findutils:i386 but not essentialpkg:i386 -> not essentialpkg:i386=4.13a.dfsg.1-6 -> not findutils:i386=4.4.2-1+b1 -> not findutils:i386' aptget remove essentialpkg --trivial-only --solver 3.0
+E: Conflict: findutils:i386 -> essentialpkg:i386=4.13a.dfsg.1-6 but not essentialpkg:i386 -> not essentialpkg:i386=4.13a.dfsg.1-6' aptget remove essentialpkg --trivial-only --solver 3.0
diff --git a/test/integration/test-bug-612557-garbage-upgrade b/test/integration/test-bug-612557-garbage-upgrade
index 2a4c952ee..f695b499e 100755
--- a/test/integration/test-bug-612557-garbage-upgrade
+++ b/test/integration/test-bug-612557-garbage-upgrade
@@ -18,7 +18,7 @@ testsuccess aptmark markauto python-uno openoffice.org-common
 testmarkedauto python-uno openoffice.org-common
 
 # The 3.0 solver does not remove openoffice.org-emailmerge because it is manually installed.
-testfailuremsg "E: Conflict:  -> openoffice.org-emailmerge:i386 but python-uno:i386=1:3.3.0-2 -> libreoffice-common:i386=1:3.3.0-2 -> not openoffice.org-common:i386=1:3.2.1-11+squeeze2 -> not openoffice.org-emailmerge:i386=1:3.2.1-11+squeeze2 -> not openoffice.org-emailmerge:i386" aptget --trivial-only install python-uno --solver 3.0
+testfailuremsg "E: Conflict: python-uno:i386=1:3.3.0-2 -> libreoffice-common:i386=1:3.3.0-2 -> not openoffice.org-common:i386=1:3.2.1-11+squeeze2 but openoffice.org-emailmerge:i386 -> openoffice.org-common:i386=1:3.2.1-11+squeeze2" aptget --trivial-only install python-uno --solver 3.0
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Reading state information...
diff --git a/test/integration/test-bug-618848-always-respect-user-requests b/test/integration/test-bug-618848-always-respect-user-requests
index 8b7b17b77..90965eb22 100755
--- a/test/integration/test-bug-618848-always-respect-user-requests
+++ b/test/integration/test-bug-618848-always-respect-user-requests
@@ -14,7 +14,7 @@ insertpackage 'unstable' 'exim4-daemon-heavy' 'all' '1.0' 'Depends: libdb4.8'
 setupaptarchive
 
 # This does not work in 3.0 solver: We do not remove manually installed packages.
-testfailuremsg "E: Conflict: not libdb4.8:i386 -> not libdb4.8:i386=1.0 -> not exim4-daemon-light:i386=1.0 -> not exim4:i386=1.0 but exim4:i386 -> exim4:i386=1.0" aptget remove libdb4.8 --solver 3.0 -s
+testfailuremsg "E: Conflict: exim4-daemon-light:i386 -> libdb4.8:i386=1.0 but not libdb4.8:i386 -> not libdb4.8:i386=1.0" aptget remove libdb4.8 --solver 3.0 -s
 allowremovemanual
 testsuccessequal "Reading package lists...
 Building dependency tree...
diff --git a/test/integration/test-bug-735967-lib32-to-i386-unavailable b/test/integration/test-bug-735967-lib32-to-i386-unavailable
index cc925d161..a44e58570 100755
--- a/test/integration/test-bug-735967-lib32-to-i386-unavailable
+++ b/test/integration/test-bug-735967-lib32-to-i386-unavailable
@@ -35,6 +35,12 @@ testsuccess aptget update
 testsuccessequal 'Reading package lists...
 Building dependency tree...
 Calculating upgrade...
+The following packages have been kept back:
+  lib32nss-mdns libnss-mdns
+0 upgraded, 0 newly installed, 0 to remove and 2 not upgraded.' aptget dist-upgrade -s --solver 3.0
+testsuccessequal 'Reading package lists...
+Building dependency tree...
+Calculating upgrade...
 The following packages will be REMOVED:
   lib32nss-mdns
 The following packages will be upgraded:
@@ -42,7 +48,7 @@ The following packages will be upgraded:
 1 upgraded, 0 newly installed, 1 to remove and 0 not upgraded.
 Remv lib32nss-mdns [0.9-1]
 Inst libnss-mdns [0.9-1] (0.10-6 unstable [amd64])
-Conf libnss-mdns (0.10-6 unstable [amd64])' aptget dist-upgrade -s
+Conf libnss-mdns (0.10-6 unstable [amd64])' aptget dist-upgrade -s --solver internal
 
 testfailuremsg 'E: Unsatisfiable dependency group libfoo:amd64=1 -> libfoo-bin:amd64' aptget install foo -s --solver 3.0
 testfailureequal 'Reading package lists...
diff --git a/test/integration/test-dpkg-i-apt-install-fix-broken b/test/integration/test-dpkg-i-apt-install-fix-broken
index 21d8e298e..252933184 100755
--- a/test/integration/test-dpkg-i-apt-install-fix-broken
+++ b/test/integration/test-dpkg-i-apt-install-fix-broken
@@ -17,15 +17,15 @@ Building dependency tree...
 Correcting dependencies...Install autopkgtest-satdep:amd64 ()
 [0] Install:autopkgtest-satdep:amd64 ()
 [0] Install:autopkgtest-satdep:amd64=1 (autopkgtest-satdep:amd64)
-[0] Install:debhelper:amd64=1 (autopkgtest-satdep:amd64 -> autopkgtest-satdep:amd64=1)
-[0] Install:debhelper:amd64 (autopkgtest-satdep:amd64 -> autopkgtest-satdep:amd64=1 -> debhelper:amd64=1)
+[0] Install:debhelper:amd64=1 (autopkgtest-satdep:amd64)
+[0] Install:debhelper:amd64 (autopkgtest-satdep:amd64 -> debhelper:amd64=1)
  Done
 Solving dependencies...Install debhelper:amd64 (M)
 Install autopkgtest-satdep:amd64 ()
 [0] Install:autopkgtest-satdep:amd64 ()
 [0] Install:autopkgtest-satdep:amd64=1 (autopkgtest-satdep:amd64)
-[0] Install:debhelper:amd64=1 (autopkgtest-satdep:amd64 -> autopkgtest-satdep:amd64=1)
-[0] Install:debhelper:amd64 (autopkgtest-satdep:amd64 -> autopkgtest-satdep:amd64=1 -> debhelper:amd64=1)
+[0] Install:debhelper:amd64=1 (autopkgtest-satdep:amd64)
+[0] Install:debhelper:amd64 (autopkgtest-satdep:amd64 -> debhelper:amd64=1)
 
 The following additional packages will be installed:
   debhelper
diff --git a/test/integration/test-ignore-provides-if-versioned-breaks b/test/integration/test-ignore-provides-if-versioned-breaks
index 7947d6d01..0263e8567 100755
--- a/test/integration/test-ignore-provides-if-versioned-breaks
+++ b/test/integration/test-ignore-provides-if-versioned-breaks
@@ -32,10 +32,7 @@ insertpackage 'unstable' 'foo-same-breaker-none' 'i386' '1.0' 'Breaks: foo-same'
 
 
 setupaptarchive
-testfailuremsg 'E: Conflict: foo:i386 but no versions are installable
-E: Uninstallable version: foo-breaker-none:i386=1.0 -> not foo:i386=4.0
-E: Uninstallable version: foo-breaker-none:i386=1.0 -> not foo:i386=2.0
-E: Uninstallable version: foo-breaker-none:i386=1.0 -> not foo:i386=2.0' aptget install foo-provider foo-breaker-none -s --solver 3.0
+testfailuremsg 'E: Conflict: foo-breaker-none:i386=1.0 -> not foo-provider:i386=1.0 but foo-provider:i386=1.0' aptget install foo-provider foo-breaker-none -s --solver 3.0
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have
@@ -74,10 +71,7 @@ Conf foo (4.0 unstable [i386])
 Conf foo-breaker-3 (1.0 unstable [i386])
 Conf foo-provider (1.0 unstable [i386])' aptget install foo-provider foo-breaker-3 -s
 
-testfailuremsg 'E: Conflict: foo-foreign:amd64 but no versions are installable
-E: Uninstallable version: foo-foreign-breaker-none:i386=1.0 -> not foo-foreign:amd64=4.0
-E: Uninstallable version: foo-foreign-breaker-none:i386=1.0 -> not foo-foreign:amd64=2.0
-E: Uninstallable version: foo-foreign-breaker-none:i386=1.0 -> not foo-foreign:amd64=4.0' aptget install foo-foreign-provider foo-foreign-breaker-none -s --solver 3.0
+testfailuremsg 'E: Conflict: foo-foreign-breaker-none:i386=1.0 -> not foo-foreign-provider:i386=1.0 but foo-foreign-provider:i386=1.0' aptget install foo-foreign-provider foo-foreign-breaker-none -s --solver 3.0
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have
@@ -116,7 +110,7 @@ Conf foo-foreign:amd64 (4.0 unstable [amd64])
 Conf foo-foreign-breaker-3 (1.0 unstable [i386])
 Conf foo-foreign-provider (1.0 unstable [i386])' aptget install foo-foreign-provider foo-foreign-breaker-3 -s
 
-testfailuremsg 'E: Conflict:  -> foo-same:i386 but foo-same-breaker-none:i386=1.0 -> not foo-same:i386=2.0 -> not foo-same:i386' aptget install foo-same-provider foo-same-breaker-none -s --solver 3.0
+testfailuremsg 'E: Conflict: foo-same-breaker-none:i386=1.0 -> not foo-same-provider:i386=1.0 but foo-same-provider:i386=1.0' aptget install foo-same-provider foo-same-breaker-none -s --solver 3.0
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have
diff --git a/test/integration/test-ignore-provides-if-versioned-conflicts b/test/integration/test-ignore-provides-if-versioned-conflicts
index dd24263d1..7f0c357fa 100755
--- a/test/integration/test-ignore-provides-if-versioned-conflicts
+++ b/test/integration/test-ignore-provides-if-versioned-conflicts
@@ -33,10 +33,7 @@ insertpackage 'unstable' 'foo-same-breaker-none' 'i386' '1.0' 'Conflicts: foo-sa
 
 setupaptarchive
 
-testfailuremsg 'E: Conflict: foo:i386 but no versions are installable
-E: Uninstallable version: foo-breaker-none:i386=1.0 -> not foo:i386=4.0
-E: Uninstallable version: foo-breaker-none:i386=1.0 -> not foo:i386=2.0
-E: Uninstallable version: foo-breaker-none:i386=1.0 -> not foo:i386=2.0' aptget install foo-provider foo-breaker-none -s --solver 3.0
+testfailuremsg 'E: Conflict: foo-breaker-none:i386=1.0 -> not foo-provider:i386=1.0 but foo-provider:i386=1.0' aptget install foo-provider foo-breaker-none -s --solver 3.0
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have
@@ -75,10 +72,7 @@ Conf foo (4.0 unstable [i386])
 Conf foo-breaker-3 (1.0 unstable [i386])
 Conf foo-provider (1.0 unstable [i386])' aptget install foo-provider foo-breaker-3 -s
 
-testfailuremsg 'E: Conflict: foo-foreign:amd64 but no versions are installable
-E: Uninstallable version: foo-foreign-breaker-none:i386=1.0 -> not foo-foreign:amd64=4.0
-E: Uninstallable version: foo-foreign-breaker-none:i386=1.0 -> not foo-foreign:amd64=2.0
-E: Uninstallable version: foo-foreign-breaker-none:i386=1.0 -> not foo-foreign:amd64=4.0' aptget install foo-foreign-provider foo-foreign-breaker-none -s --solver 3.0
+testfailuremsg 'E: Conflict: foo-foreign-breaker-none:i386=1.0 -> not foo-foreign-provider:i386=1.0 but foo-foreign-provider:i386=1.0' aptget install foo-foreign-provider foo-foreign-breaker-none -s --solver 3.0
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have
@@ -117,7 +111,7 @@ Conf foo-foreign:amd64 (4.0 unstable [amd64])
 Conf foo-foreign-breaker-3 (1.0 unstable [i386])
 Conf foo-foreign-provider (1.0 unstable [i386])' aptget install foo-foreign-provider foo-foreign-breaker-3 -s
 
-testfailuremsg 'E: Conflict:  -> foo-same:i386 but foo-same-breaker-none:i386=1.0 -> not foo-same:i386=2.0 -> not foo-same:i386' aptget install foo-same-provider foo-same-breaker-none -s --solver 3.0
+testfailuremsg 'E: Conflict: foo-same-breaker-none:i386=1.0 -> not foo-same-provider:i386=1.0 but foo-same-provider:i386=1.0' aptget install foo-same-provider foo-same-breaker-none -s --solver 3.0
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have
diff --git a/test/integration/test-multiarch-allowed b/test/integration/test-multiarch-allowed
index 298867c5f..4b795bd5e 100755
--- a/test/integration/test-multiarch-allowed
+++ b/test/integration/test-multiarch-allowed
@@ -64,18 +64,18 @@ Inst needsfoo:i386 (1 unstable [i386])
 Conf foo:i386 (1 unstable [i386])
 Conf needsfoo:i386 (1 unstable [i386])' aptget install needsfoo:i386 -s
 # FIXME: same problem, but two different unmet dependency messages depending on install order
-testfailuremsg "E: Conflict:  -> needsfoo:i386=1 but foo:amd64=1 -> not foo:i386=1 -> not needsfoo:i386=1" aptget install needsfoo:i386 foo:amd64 -s --solver 3.0
+testfailuremsg "E: Conflict: needsfoo:i386=1 -> foo:i386=1 but foo:amd64=1 -> not foo:i386=1" aptget install needsfoo:i386 foo:amd64 -s --solver 3.0
 testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  foo : Conflicts: foo:i386 but 1 is to be installed
  foo:i386 : Conflicts: foo but 1 is to be installed
 E: Unable to correct problems, you have held broken packages." aptget install needsfoo:i386 foo:amd64 -s --solver internal
-testfailuremsg "E: Conflict:  -> needsfoo:i386=1 but foo:amd64=1 -> not foo:i386=1 -> not needsfoo:i386=1" aptget install foo:amd64 needsfoo:i386 -s --solver 3.0
+testfailuremsg "E: Conflict: needsfoo:i386=1 -> foo:i386=1 but foo:amd64=1 -> not foo:i386=1" aptget install foo:amd64 needsfoo:i386 -s --solver 3.0
 testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  needsfoo:i386 : Depends: foo:i386 but it is not installable
 E: Unable to correct problems, you have held broken packages." aptget install foo:amd64 needsfoo:i386 -s --solver internal
-testfailuremsg "E: Conflict:  -> needsfoo:amd64=1 but foo:i386=1 -> not foo:amd64=1 -> not needsfoo:amd64=1" aptget install needsfoo foo:i386 -s --solver 3.0
+testfailuremsg "E: Conflict: needsfoo:amd64=1 -> foo:amd64=1 but foo:i386=1 -> not foo:amd64=1" aptget install needsfoo foo:i386 -s --solver 3.0
 testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  foo : Conflicts: foo:i386 but 1 is to be installed
diff --git a/test/integration/test-multiarch-foreign b/test/integration/test-multiarch-foreign
index 228fa8895..b356c64c7 100755
--- a/test/integration/test-multiarch-foreign
+++ b/test/integration/test-multiarch-foreign
@@ -179,7 +179,7 @@ distribution that some required packages have not yet been created
 or been moved out of Incoming.
 The following information may help to resolve the situation:
 '
-	testfailuremsg "E: Conflict:  -> ${1%:*}:$4=1.0 but hates-foo:amd64=1.0 -> not ${1%:*}:$4=1.0"  aptget install $1 hates-foo -s --solver 3.0
+	testfailuremsg "E: Conflict: hates-foo:amd64=1.0 -> not ${1%:*}:$4=1.0 but ${1%:*}:$4=1.0"  aptget install $1 hates-foo -s --solver 3.0
 	testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  hates-foo : Conflicts: foo
diff --git a/test/integration/test-solver-recommends-depends b/test/integration/test-solver-recommends-depends
new file mode 100755
index 000000000..90c5050a7
--- /dev/null
+++ b/test/integration/test-solver-recommends-depends
@@ -0,0 +1,46 @@
+#!/bin/sh
+set -e
+
+TESTDIR="$(readlink -f "$(dirname "$0")")"
+. "$TESTDIR/framework"
+setupenvironment
+allowremovemanual
+configarchitecture 'amd64'
+
+insertpackage 'unstable' 'a' 'all' '2'
+insertpackage 'unstable' 'b' 'all' '2'
+insertpackage 'unstable' 'x' 'all' '3' 'Depends: xx
+Recommends: b'
+insertpackage 'unstable' 'xx' 'all' '3' 'Depends: a | b
+Recommends: b'
+
+setupaptarchive
+
+msgmsg "Test that the Recommends does not influence the Depends"
+testsuccessequal "The following additional packages will be installed:
+  a b
+The following NEW packages will be installed:
+  a b xx
+0 upgraded, 3 newly installed, 0 to remove and 0 not upgraded.
+Inst a (2 unstable [all])
+Inst b (2 unstable [all])
+Inst xx (3 unstable [all])
+Conf a (2 unstable [all])
+Conf b (2 unstable [all])
+Conf xx (3 unstable [all])" apt install -s xx -qq
+
+
+msgmsg "Test that the Recommends in x does not influence the Depends in xx (one level lower)"
+testsuccessequal "The following additional packages will be installed:
+  a b xx
+The following NEW packages will be installed:
+  a b x xx
+0 upgraded, 4 newly installed, 0 to remove and 0 not upgraded.
+Inst a (2 unstable [all])
+Inst b (2 unstable [all])
+Inst xx (3 unstable [all])
+Inst x (3 unstable [all])
+Conf a (2 unstable [all])
+Conf b (2 unstable [all])
+Conf xx (3 unstable [all])
+Conf x (3 unstable [all])" apt install -s x -qq