Merge branch 'solver3' into 'main'

solver3: Verbose error messages and some bugfixes

See merge request apt-team/apt!457

30 files changed, 654 insertions, 113 deletions

diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc
index c1a1098b5..9f27951e8 100644
--- a/apt-pkg/solver3.cc
+++ b/apt-pkg/solver3.cc
@@ -35,6 +35,7 @@
 #include <cassert>
 #include <chrono>
 #include <ctime>
+#include <iomanip>
 #include <sstream>
 
 // FIXME: Helpers stolen from DepCache, please give them back.
@@ -231,16 +232,31 @@ bool APT::Solver::Work::operator<(APT::Solver::Work const &b) const
    return false;
 }
 
-std::string APT::Solver::Clause::toString(pkgCache &cache) const
+std::string APT::Solver::Clause::toString(pkgCache &cache, bool pretty) const
 {
    std::string out;
-   if (auto Pkg = reason.Pkg(cache); not Pkg.end())
-      out.append(Pkg.FullName());
-   if (auto Ver = reason.Ver(cache); not Ver.end())
-      out.append(Ver.ParentPkg().FullName()).append("=").append(Ver.VerStr());
-   out.append(" -> ");
-   for (auto var : solutions)
-      out.append(" | ").append(var.toString(cache));
+   out.append(reason.toString(cache));
+   if (dep && pretty)
+   {
+      out.append(" ").append(pkgCache::DepIterator(cache, dep).DepType()).append(" ");
+      for (auto dep = pkgCache::DepIterator(cache, this->dep); not dep.end(); ++dep)
+      {
+	 out.append(dep.TargetPkg().FullName(true));
+	 if (dep.TargetVer())
+	    out.append(" (").append(dep.CompType()).append(" ").append(dep.TargetVer()).append(")");
+	 if (!(dep->CompareOp & pkgCache::Dep::Or))
+	    break;
+	 out.append(" | ");
+      }
+   }
+   else if (group == Group::SelectVersion && negative)
+      out.append(" conflicts with other versions of itself");
+   else
+   {
+      out.append(" -> ");
+      for (auto var : solutions)
+	 out.append(" | ").append(var.toString(cache));
+   }
    return out;
 }
 
@@ -262,8 +278,12 @@ inline APT::Solver::Var APT::Solver::bestReason(APT::Solver::Clause const *claus
       return Var{};
    if (clause->reason == var)
       for (auto choice : clause->solutions)
-	 if ((*this)[choice].decision != Decision::NONE)
+      {
+	 if (clause->negative && (*this)[choice].decision == Decision::MUST)
+	    return choice;
+	 if (not clause->negative && (*this)[choice].decision == Decision::MUSTNOT)
 	    return choice;
+      }
    return clause->reason;
 }
 
@@ -288,6 +308,167 @@ std::string APT::Solver::WhyStr(Var reason) const
    return outstr;
 }
 
+std::string APT::Solver::LongWhyStr(Var var, bool decision, const Clause *rclause, std::string prefix, std::unordered_set<Var> &seen) const
+{
+   std::ostringstream out;
+
+   // Helper function to nicely print more details than just "install/do not install", such as "removal", "upgrade", "downgrade", "install"
+   auto printSelection = [this](Var var, bool decision)
+   {
+      std::string s;
+      if (auto pkg = var.Pkg(cache); not decision && pkg && pkg->CurrentVer)
+	 strprintf(s, "%s is selected for removal", var.toString(cache).c_str());
+      else if (auto ver = var.Ver(cache); decision && ver && ver.ParentPkg().CurrentVer() && ver.ParentPkg().CurrentVer() != ver)
+      {
+	 if (cache.VS->CmpVersion(ver.ParentPkg().CurrentVer().VerStr(), ver.VerStr()) < 0)
+	    strprintf(s, "%s is selected as an upgrade", var.toString(cache).c_str());
+	 else
+	    strprintf(s, "%s is selected as a downgrade", var.toString(cache).c_str());
+      }
+      else if (not decision)
+	 strprintf(s, "%s is not selected for install", var.toString(cache).c_str());
+      else
+	 strprintf(s, "%s is selected for install", var.toString(cache).c_str());
+      return s;
+   };
+
+   // Helper: Recurse into all of the children of the clause and print the decision for them.
+   auto recurseChildren = [&](const Clause *clause, Var skip = Var())
+   {
+      if (clause->solutions.empty())
+	 out << prefix << "[no choices]\n";
+      for (auto choice : clause->solutions)
+      {
+	 if (choice == skip)
+	    continue;
+
+	 if ((*this)[choice].decision == Decision::NONE)
+	    out << prefix << "- " << choice.toString(cache) << " is undecided\n";
+	 else
+	    out << prefix << "- " << LongWhyStr(choice, (*this)[choice].decision == Decision::MUST, (*this)[choice].reason, prefix + "  ", seen).substr(prefix.size() + 2);
+      }
+   };
+
+   // Version selection clauses like pkg=ver -> pkg or pkg -> pkg=ver are irrelevant for the user, skip them
+   if (decision && rclause && rclause->group == Group::SelectVersion)
+   {
+      var = rclause->reason;
+      rclause = (*this)[var].reason;
+   }
+
+   // No reason given, probably a user request or manually installed or essential or whatnot.
+   if (not rclause)
+   {
+      out << prefix << printSelection(var, decision) << "\n";
+      return out.str();
+   }
+
+   // We could be called with a decision we tried to make but failed due to a conflict;
+   // this checks if it is the real decision.
+   if ((*this)[var].decision != Decision::NONE && decision == ((*this)[var].decision == Decision::MUST) && (*this)[var].reason == rclause)
+   {
+      // If we have seen the real decision before; we dont't need to print it again.
+      if (seen.find(var) != seen.end())
+      {
+	 out << prefix << printSelection(var, decision) << " as above\n";
+	 return out.str();
+      }
+      seen.insert(var);
+   }
+
+   // A package was decided "not install" due to a positive clause, so the clause is unsat.
+   if (not decision && rclause && not rclause->negative)
+   {
+      out << prefix << rclause->toString(cache, true) << "\n";
+      out << prefix << "but none of the choices are installable:\n";
+      recurseChildren(rclause);
+      return out.str();
+   }
+
+   // Build the strongest path from a root to our decision leaf
+   std::vector<Var> path;
+   for (auto reason = bestReason(rclause, var); not reason.empty(); reason = bestReason((*this)[reason].reason, reason))
+      path.push_back(reason);
+
+   // Render the strong reasoning path
+   out << prefix << printSelection(var, decision) << " because:\n";
+   auto w = std::to_string(path.size() + 1).size();
+   size_t i = 1;
+   for (auto it = path.rbegin(); it != path.rend(); ++it, ++i)
+   {
+      auto const &state = (*this)[*it];
+      // Don't print version selection clauses
+      if (state.reason && state.reason->group == Group::SelectVersion)
+      {
+	 --i;
+	 continue;
+      }
+      if (seen.find(*it) != seen.end())
+      {
+	 if ((it + 1) == path.rend() || seen.find(*(it + 1)) == seen.end())
+	 {
+	    out << prefix << (i == 1 ? "" : "1-") << i << ". " << printSelection(*it, state.decision == Decision::MUST) << " as above\n";
+	 }
+	 continue;
+      }
+      seen.insert(*it);
+      if (state.reason)
+      {
+	 out << prefix << std::setw(w) << i << ". " << state.reason->toString(cache, true) << "\n";
+	 if (state.reason->solutions.size() > 1)
+	    out << prefix << std::setw(w) << " " << "  [selected " << it->toString(cache) << " for " << (state.decision == Decision::MUST ? "install" : "remove") << "]\n";
+      }
+      else
+	 out << prefix << std::setw(w) << i << ". " << printSelection(*it, state.decision == Decision::MUST) << "\n";
+   }
+
+   // Print the leaf. We can't have the leaf in the path because we might be called for an attempted decision
+   // that conflicts with the actual assignment (to simplify: we marked X for not install, then we process Y depends X
+   // and try to mark X and reach the conflict, we are called with "X" and the "Y depends X" clause).
+   out << prefix << std::setw(w) << i << ". " << rclause->toString(cache, true) << "\n";
+   if (rclause->solutions.size() > 1)
+      out << prefix << std::setw(w) << " " << "  " << "[selected " << bestReason(rclause, var).toString(cache) << "]\n";
+
+   bool firstContext = true;
+   // Show alternative paths not taken. Consider you have Y depends X|Z; and you mark X
+   // for it; we show above Y -> X as the path, but here we go show why Z was not considered in "Y depends X|Z".
+   for (auto it = path.rbegin(); it != path.rend(); ++it)
+   {
+      auto const &state = (*this)[*it];
+      if (not state.reason) // If we have no reason, we don't have alternatives
+	 continue;
+      if (state.reason->solutions.size() <= 1) // Nothing to print if we no alternatives
+	 continue;
+      if (state.reason->negative) // We only actually need one conflicting choice, ignore others
+	 continue;
+
+      if (firstContext)
+      {
+	 out << prefix << "For context, additional choices that could not be installed:" << "\n";
+      }
+
+      firstContext = false;
+      out << prefix << "* In " << state.reason->toString(cache, true) << ":\n";
+      prefix += "  ";
+      recurseChildren(state.reason, *it);
+      prefix.resize(prefix.size() - 2);
+   }
+   if (rclause->solutions.size() > 1 && not rclause->negative)
+   {
+      if (firstContext)
+      {
+	 out << prefix << "For context, additional choices that could not be installed:" << "\n";
+      }
+      firstContext = false;
+      out << prefix << "* In " << rclause->toString(cache, true) << ":\n";
+      prefix += "  ";
+      recurseChildren(rclause, var);
+      prefix.resize(prefix.size() - 2);
+   }
+
+   return out.str();
+}
+
 // This is essentially asking whether any other binary in the source package has a higher candidate
 // version. This pretends that each package is installed at the same source version as the package
 // under consideration.
@@ -360,7 +541,14 @@ bool APT::Solver::Enqueue(Var var, bool decision, const Clause *reason)
    if (state.decision != Decision::NONE)
    {
       if (state.decision != decisionCast)
-	 return _error->Error("Conflict: %s -> %s%s but %s", WhyStr(bestReason(reason, var)).c_str(), decision ? "" : "not ", var.toString(cache).c_str(), WhyStr(var).c_str());
+      {
+	 std::ostringstream err;
+	 err << "Unable to satisfy dependencies. Reached two conflicting decisions:" << "\n";
+	 std::unordered_set<Var> seen;
+	 err << "1. " << LongWhyStr(var, state.decision == Decision::MUST, state.reason, "   ", seen).substr(3) << "\n";
+	 err << "2. " << LongWhyStr(var, decision, reason, "   ", seen).substr(3);
+	 return _error->Error("%s", err.str().c_str());
+      }
       return true;
    }
 
@@ -444,13 +632,14 @@ bool APT::Solver::Propagate()
    return true;
 }
 
-void APT::Solver::RegisterClause(Clause &&clause)
+const APT::Solver::Clause *APT::Solver::RegisterClause(Clause &&clause)
 {
    auto &clauses = (*this)[clause.reason].clauses;
    clauses.push_back(std::make_unique<Clause>(std::move(clause)));
    auto const &inserted = clauses.back();
    for (auto var : inserted->solutions)
       (*this)[var].rclauses.push_back(inserted.get());
+   return inserted.get();
 }
 
 void APT::Solver::Discover(Var var)
@@ -757,7 +946,7 @@ bool APT::Solver::AddWork(Work &&w)
 	 if (not Enqueue(var, false, w.clause))
 	    return false;
    }
-   else if (not w.clause->solutions.empty())
+   else
    {
       if (unlikely(debug >= 3 && w.clause->optional))
 	 std::cerr << "Enqueuing Recommends " << w.clause->toString(cache) << std::endl;
@@ -769,10 +958,6 @@ bool APT::Solver::AddWork(Work &&w)
       work.push_back(std::move(w));
       std::push_heap(work.begin(), work.end());
    }
-   else if (not w.clause->optional && w.clause->dep)
-      return _error->Error("Unsatisfiable dependency group %s -> %s", w.clause->reason.toString(cache).c_str(), pkgCache::DepIterator(cache, w.clause->dep).TargetPkg().FullName().c_str());
-   else if (not w.clause->optional)
-      return _error->Error("Unsatisfiable dependency group %s", w.clause->reason.toString(cache).c_str());
    return true;
 }
 
@@ -816,8 +1001,6 @@ bool APT::Solver::Solve()
       if (unlikely(debug >= 1))
 	 std::cerr << item.toString(cache) << std::endl;
 
-      assert(item.clause->solutions.size() > 1 || item.clause->optional);
-
       bool foundSolution = false;
       for (auto &sol : item.clause->solutions)
       {
@@ -841,15 +1024,13 @@ bool APT::Solver::Solve()
       }
       if (not foundSolution && not item.clause->optional)
       {
-	 std::ostringstream dep;
-	 assert(item.clause->solutions.size() > 0);
-	 for (auto &sol : item.clause->solutions)
-	    dep << (dep.tellp() == 0 ? "" : " | ") << sol.toString(cache);
-	 _error->Error("Unsatisfiable dependency: %s -> %s", WhyStr(item.clause->reason).c_str(), dep.str().c_str());
-	 for (auto &sol : item.clause->solutions)
-	    if ((*this)[sol].decision == Decision::MUSTNOT)
-	       _error->Error("Not considered: %s: %s", sol.toString(cache).c_str(),
-			     WhyStr(sol).c_str());
+	 std::ostringstream err;
+
+	 err << "Unable to satisfy dependencies. Reached two conflicting decisions:" << "\n";
+	 std::unordered_set<Var> seen;
+	 err << "1. " << LongWhyStr(item.clause->reason, true, (*this)[item.clause->reason].reason, "   ", seen).substr(3) << "\n";
+	 err << "2. " << LongWhyStr(item.clause->reason, false, item.clause, "   ", seen).substr(3);
+	 _error->Error("%s", err.str().c_str());
 	 if (not Pop())
 	    return false;
       }
@@ -931,8 +1112,8 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache)
 	 {
 	    Clause w{Var(), Group, isOptional};
 	    w.solutions.push_back(Var(P));
-	    RegisterClause(std::move(w));
-	    if (not AddWork(Work{rootState->clauses.back().get(), depth()}))
+	    auto insertedW = RegisterClause(std::move(w));
+	    if (not AddWork(Work{insertedW, depth()}))
 	       return false;
 
 	    // Given A->A2|A1, B->B1|B2; Bn->An, if we select `not A1`, we
@@ -944,8 +1125,8 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache)
 	    for (auto V = P.VersionList(); not V.end(); ++V)
 	       shortcircuit.solutions.push_back(Var(V));
 	    std::stable_sort(shortcircuit.solutions.begin(), shortcircuit.solutions.end(), CompareProviders3{cache, policy, P, *this});
-	    RegisterClause(std::move(shortcircuit));
-	    if (not AddWork(Work{rootState->clauses.back().get(), depth()}))
+	    auto insertedShort = RegisterClause(std::move(shortcircuit));
+	    if (not AddWork(Work{insertedShort, depth()}))
 	       return false;
 
 	    // Discovery here is needed so the shortcircuit clause can actually become unit.
@@ -963,8 +1144,8 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache)
 	 std::stable_sort(w.solutions.begin(), w.solutions.end(), CompareProviders3{cache, policy, P, *this});
 	 if (unlikely(debug >= 1))
 	    std::cerr << "Install essential package " << P << std::endl;
-	 RegisterClause(std::move(w));
-	 if (not AddWork(Work{rootState->clauses.back().get(), depth()}))
+	 auto inserted = RegisterClause(std::move(w));
+	 if (not AddWork(Work{inserted, depth()}))
 	    return false;
       }
    }
diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h
index 0ad0800ba..9d4a195ec 100644
--- a/apt-pkg/solver3.h
+++ b/apt-pkg/solver3.h
@@ -84,6 +84,7 @@ class Solver
    struct Clause;
    struct Work;
    struct Solved;
+   friend struct std::hash<APT::Solver::Var>;
 
    // \brief Groups of works, these are ordered.
    //
@@ -246,7 +247,7 @@ class Solver
    // utilizing the discoverQ above.
    void Discover(Var var);
    // \brief Link a clause into the watchers
-   void RegisterClause(Clause &&clause);
+   const Clause *RegisterClause(Clause &&clause);
    // \brief Enqueue dependencies shared by all versions of the package.
    void RegisterCommonDependencies(pkgCache::PkgIterator Pkg);
 
@@ -290,6 +291,19 @@ class Solver
 
    // Print dependency chain
    std::string WhyStr(Var reason) const;
+
+   /**
+    * \brief Print a long reason string
+    *
+    * Print a reason as to why `rclause` implies `decision` for the variable `var`.
+    *
+    * \param var The variable to print the reason for
+    * \param decision The assumed decision to print the reason for (may be different from actual decision if rclause is specified)
+    * \param rclause The clause that caused this variable to be marked (or would be marked)
+    * \param prefix A prefix, for indentation purposes, as this is recursive
+    * \param seen A set of seen objects such that the output does not repeat itself (not for safety, it is acyclic)
+    */
+   std::string LongWhyStr(Var var, bool decision, const Clause *rclause, std::string prefix, std::unordered_set<Var> &seen) const;
 };
 
 }; // namespace APT
@@ -304,48 +318,44 @@ class Solver
  */
 struct APT::Solver::Var
 {
-   uint32_t IsVersion : 1;
-   uint32_t MapPtr : 31;
+   uint32_t value;
+
+   explicit constexpr Var(uint32_t value = 0) : value{value} {}
+   explicit Var(pkgCache::PkgIterator const &Pkg) : value(uint32_t(Pkg.MapPointer()) << 1) {}
+   explicit Var(pkgCache::VerIterator const &Ver) : value(uint32_t(Ver.MapPointer()) << 1 | 1) {}
 
-   Var() : IsVersion(0), MapPtr(0) {}
-   explicit Var(pkgCache::PkgIterator const &Pkg) : IsVersion(0), MapPtr(Pkg.MapPointer()) {}
-   explicit Var(pkgCache::VerIterator const &Ver) : IsVersion(1), MapPtr(Ver.MapPointer()) {}
+   inline constexpr bool isVersion() const { return value & 1; }
+   inline constexpr uint32_t mapPtr() const { return value >> 1; }
 
    // \brief Return the package, if any, otherwise 0.
    map_pointer<pkgCache::Package> Pkg() const
    {
-      return IsVersion ? 0 : map_pointer<pkgCache::Package>{(uint32_t)MapPtr};
+      return isVersion() ? 0 : map_pointer<pkgCache::Package>{mapPtr()};
    }
    // \brief Return the version, if any, otherwise 0.
    map_pointer<pkgCache::Version> Ver() const
    {
-      return IsVersion ? map_pointer<pkgCache::Version>{(uint32_t)MapPtr} : 0;
+      return isVersion() ? map_pointer<pkgCache::Version>{mapPtr()} : 0;
    }
    // \brief Return the package iterator if storing a package, or an empty one
    pkgCache::PkgIterator Pkg(pkgCache &cache) const
    {
-      return IsVersion ? pkgCache::PkgIterator() : pkgCache::PkgIterator(cache, cache.PkgP + Pkg());
+      return isVersion() ? pkgCache::PkgIterator() : pkgCache::PkgIterator(cache, cache.PkgP + Pkg());
    }
    // \brief Return the version iterator if storing a package, or an empty end.
    pkgCache::VerIterator Ver(pkgCache &cache) const
    {
-      return IsVersion ? pkgCache::VerIterator(cache, cache.VerP + Ver()) : pkgCache::VerIterator();
+      return isVersion() ? pkgCache::VerIterator(cache, cache.VerP + Ver()) : pkgCache::VerIterator();
    }
    // \brief Return a package, cast from version if needed
    pkgCache::PkgIterator CastPkg(pkgCache &cache) const
    {
-      assert(MapPtr != 0);
-      return IsVersion ? Ver(cache).ParentPkg() : Pkg(cache);
+      return isVersion() ? Ver(cache).ParentPkg() : Pkg(cache);
    }
    // \brief Check if there is no reason.
-   bool empty() const
-   {
-      return IsVersion == 0 && MapPtr == 0;
-   }
-   bool operator==(Var const other) const
-   {
-      return IsVersion == other.IsVersion && MapPtr == other.MapPtr;
-   }
+   constexpr bool empty() const { return value == 0; }
+   constexpr bool operator!=(Var const other) const { return value != other.value; }
+   constexpr bool operator==(Var const other) const { return value == other.value; }
 
    std::string toString(pkgCache &cache) const
    {
@@ -381,7 +391,7 @@ struct APT::Solver::Clause
 
    inline Clause(Var reason, Group group, bool optional = false, bool negative = false) : reason(reason), group(group), optional(optional), negative(negative) {}
 
-   std::string toString(pkgCache &cache) const;
+   std::string toString(pkgCache &cache, bool pretty = false) const;
 };
 
 /**
@@ -498,3 +508,11 @@ inline const APT::Solver::State &APT::Solver::operator[](Var r) const
 {
    return const_cast<Solver &>(*this)[r];
 }
+
+// Custom specialization of std::hash can be injected in namespace std.
+template <>
+struct std::hash<APT::Solver::Var>
+{
+   std::hash<decltype(APT::Solver::Var::value)> hash_value;
+   std::size_t operator()(const APT::Solver::Var &v) const noexcept { return hash_value(v.value); }
+};
diff --git a/test/integration/test-apt-get-build-dep-barbarian b/test/integration/test-apt-get-build-dep-barbarian
index 48873c59b..8763e8fc7 100755
--- a/test/integration/test-apt-get-build-dep-barbarian
+++ b/test/integration/test-apt-get-build-dep-barbarian
@@ -83,7 +83,16 @@ testsuccessequal "$(installsfoosamey 'amd64' 'i386')" apt build-dep cool-foo -s
 testsuccessequal "$(installsfoosamey 'i386' 'i386')" apt build-dep bad-amd64-foo -s -a i386
 testsuccessequal "$(installsfoosamey 'amd64' 'i386')" apt build-dep bad-armel-foo -s -a i386
 testsuccessequal "$(installsfoosamey 'i386' 'i386')" apt build-dep bad-amd64-armel-foo -s -a i386
-testfailuremsg 'E: Conflict: builddeps:bad-amd64-i386-foo:i386=1 -> builddeps:bad-amd64-i386-foo:i386 -> not foo:amd64=1 -> not builddeps:bad-amd64-i386-foo:i386 but builddeps:bad-amd64-i386-foo:i386=1 -> builddeps:bad-amd64-i386-foo:i386'  apt build-dep bad-amd64-i386-foo -s -a i386 --solver 3.0
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. builddeps:bad-amd64-i386-foo:i386=1 is selected for install
+   2. builddeps:bad-amd64-i386-foo:i386 Depends foo:i386
+      but none of the choices are installable:
+      - foo:amd64=1 is not selected for install because:
+        1. builddeps:bad-amd64-i386-foo:i386=1 is selected for install
+        2. builddeps:bad-amd64-i386-foo:i386 Conflicts foo:amd64
+      - foo:i386=1 is not selected for install because:
+        1. builddeps:bad-amd64-i386-foo:i386=1 is selected for install as above
+        2. builddeps:bad-amd64-i386-foo:i386 Conflicts foo:i386'  apt build-dep bad-amd64-i386-foo -s -a i386 --solver 3.0
 testfailureequal 'Reading package lists...
 Reading package lists...
 Building dependency tree...
@@ -96,7 +105,16 @@ The following information may help to resolve the situation:
 The following packages have unmet dependencies:
  builddeps:bad-amd64-i386-foo:i386 : Depends: foo:i386
 E: Unable to correct problems, you have held broken packages.' apt build-dep bad-amd64-i386-foo -s -a i386 --solver internal
-testfailuremsg 'E: Conflict: builddeps:bad-amd64-i386-armel-foo:i386=1 -> builddeps:bad-amd64-i386-armel-foo:i386 -> not foo:amd64=1 -> not builddeps:bad-amd64-i386-armel-foo:i386 but builddeps:bad-amd64-i386-armel-foo:i386=1 -> builddeps:bad-amd64-i386-armel-foo:i386' apt build-dep bad-amd64-i386-armel-foo -s -a i386 --solver 3.0
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. builddeps:bad-amd64-i386-armel-foo:i386=1 is selected for install
+   2. builddeps:bad-amd64-i386-armel-foo:i386 Depends foo:i386
+      but none of the choices are installable:
+      - foo:amd64=1 is not selected for install because:
+        1. builddeps:bad-amd64-i386-armel-foo:i386=1 is selected for install
+        2. builddeps:bad-amd64-i386-armel-foo:i386 Conflicts foo:amd64
+      - foo:i386=1 is not selected for install because:
+        1. builddeps:bad-amd64-i386-armel-foo:i386=1 is selected for install as above
+        2. builddeps:bad-amd64-i386-armel-foo:i386 Conflicts foo:i386' apt build-dep bad-amd64-i386-armel-foo -s -a i386 --solver 3.0
 testfailureequal 'Reading package lists...
 Reading package lists...
 Building dependency tree...
@@ -115,7 +133,19 @@ testsuccessequal "$(installsfoosamey 'i386' 'armel')" apt build-dep bad-amd64-fo
 testsuccessequal "$(installsfoosamey 'amd64' 'armel')" apt build-dep bad-armel-foo -s -a armel
 testsuccessequal "$(installsfoosamey 'i386' 'armel')" apt build-dep bad-amd64-armel-foo -s -a armel
 testsuccessequal "$(installsfoosamey 'armel' 'armel')" apt build-dep bad-amd64-i386-foo -s -a armel
-FAILUREMSG="E: Conflict: builddeps:bad-amd64-i386-armel-foo:armel=1 -> builddeps:bad-amd64-i386-armel-foo:armel -> not foo:amd64=1 -> not builddeps:bad-amd64-i386-armel-foo:armel but builddeps:bad-amd64-i386-armel-foo:armel=1 -> builddeps:bad-amd64-i386-armel-foo:armel"
+FAILUREMSG="E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. builddeps:bad-amd64-i386-armel-foo:armel=1 is selected for install
+   2. builddeps:bad-amd64-i386-armel-foo:armel Depends foo:armel
+      but none of the choices are installable:
+      - foo:amd64=1 is not selected for install because:
+        1. builddeps:bad-amd64-i386-armel-foo:armel=1 is selected for install
+        2. builddeps:bad-amd64-i386-armel-foo:armel Conflicts foo:amd64
+      - foo:i386=1 is not selected for install because:
+        1. builddeps:bad-amd64-i386-armel-foo:armel=1 is selected for install as above
+        2. builddeps:bad-amd64-i386-armel-foo:armel Conflicts foo:i386
+      - foo:armel=1 is not selected for install because:
+        1. builddeps:bad-amd64-i386-armel-foo:armel=1 is selected for install as above
+        2. builddeps:bad-amd64-i386-armel-foo:armel Conflicts foo:armel"
 FAILURE='Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have
diff --git a/test/integration/test-apt-get-build-dep-file b/test/integration/test-apt-get-build-dep-file
index 8147bb0a3..fd48aef47 100755
--- a/test/integration/test-apt-get-build-dep-file
+++ b/test/integration/test-apt-get-build-dep-file
@@ -160,7 +160,11 @@ cd ../..
 
 testfailureequal 'E: Must specify at least one package to check builddeps for' aptget build-dep
 testfailuremsg 'W: No architecture information available for armel. See apt.conf(5) APT::Architectures for setup
-E: Unsatisfiable dependency group builddeps:./foo-1.0:armel -> debhelper:armel' aptget build-dep --simulate ./foo-1.0 -a armel --solver 3.0
+E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. builddeps:./foo-1.0:armel=1 is selected for install
+   2. builddeps:./foo-1.0:armel Depends debhelper:armel (>= 7)
+      but none of the choices are installable:
+      [no choices]' aptget build-dep --simulate ./foo-1.0 -a armel --solver 3.0
 testfailureequal "Note, using directory './foo-1.0' to get the build dependencies
 Reading package lists...
 Building dependency tree...
diff --git a/test/integration/test-apt-get-install-deb b/test/integration/test-apt-get-install-deb
index 1540db272..07de975c4 100755
--- a/test/integration/test-apt-get-install-deb
+++ b/test/integration/test-apt-get-install-deb
@@ -32,7 +32,11 @@ done
 
 buildsimplenativepackage 'foo' 'i386,amd64' '1.0'
 
-testfailuremsg "E: Conflict: foo:amd64=1.0 -> foo:amd64 but foo:i386=1.0 -> not foo:amd64" aptget install ./incoming/foo_1.0_i386.deb ./incoming/foo_1.0_amd64.deb -s --solver 3.0
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. foo:amd64 is not selected for install because:
+      1. foo:i386=1.0 is selected for install
+      2. foo:amd64 Conflicts foo:i386
+   2. foo:amd64=1.0 is selected for install" aptget install ./incoming/foo_1.0_i386.deb ./incoming/foo_1.0_amd64.deb -s --solver 3.0
 testfailureequal "Reading package lists...
 Building dependency tree...
 Note, selecting 'foo:i386' instead of './incoming/foo_1.0_i386.deb'
@@ -177,7 +181,11 @@ echo 'Package: /pkg-/
 Pin: release a=experimental
 Pin-Priority: 501' > rootdir/etc/apt/preferences.d/pinit
 
-testfailuremsg 'E: Unsatisfiable dependency group pkg-last-line-parse:amd64 -> pkg-as-it-should-be:amd64' aptget install -q=0 ./incoming/pkg-last-line-parse_0_all.deb --solver 3.0
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. pkg-last-line-parse:amd64=0 is selected for install
+   2. pkg-last-line-parse:amd64 PreDepends pkg-as-it-should-be
+      but none of the choices are installable:
+      [no choices]' aptget install -q=0 ./incoming/pkg-last-line-parse_0_all.deb --solver 3.0
 testfailuremsg 'E: Unable to correct problems, you have held broken packages.' aptget install -q=0 ./incoming/pkg-last-line-parse_0_all.deb --solver internal
 testsuccess aptget install ./incoming/pkg-as-it-should-be_0_all.deb
 testsuccess aptget install ./incoming/pkg-last-line-parse_0_all.deb
diff --git a/test/integration/test-apt-get-satisfy b/test/integration/test-apt-get-satisfy
index 02a444dff..8e5e06843 100755
--- a/test/integration/test-apt-get-satisfy
+++ b/test/integration/test-apt-get-satisfy
@@ -80,7 +80,11 @@ testrun 'External' 'Reading package lists...
 Building dependency tree...
 Execute external solver...' --solver apt
 
-testfailuremsg "E: Unsatisfiable dependency group satisfy:command-line:i386 -> depends:i386" aptget satisfy --simulate "depends (>= 2)" "Conflicts: conflicts:i386 (>= 1) [i386], conflicts:amd64 (>= 1) [amd64]" --solver 3.0
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. satisfy:command-line:i386=1 is selected for install
+   2. satisfy:command-line:i386 Depends depends (>= 2)
+      but none of the choices are installable:
+      [no choices]" aptget satisfy --simulate "depends (>= 2)" "Conflicts: conflicts:i386 (>= 1) [i386], conflicts:amd64 (>= 1) [amd64]" --solver 3.0
 
 testfailureequal "Reading package lists...
 Building dependency tree...
diff --git a/test/integration/test-apt-get-source-only b/test/integration/test-apt-get-source-only
index 882f82b33..e5d246f6e 100755
--- a/test/integration/test-apt-get-source-only
+++ b/test/integration/test-apt-get-source-only
@@ -40,7 +40,11 @@ The following information may help to resolve the situation:
 
 The following packages have unmet dependencies:
  builddeps:foo : Depends: foo-bd but it is not installable
-E: Unsatisfiable dependency group builddeps:foo:amd64 -> foo-bd:amd64"
+E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. builddeps:foo:amd64=1 is selected for install
+   2. builddeps:foo:amd64 Depends foo-bd
+      but none of the choices are installable:
+      [no choices]"
 
 BUILDDEPNOTFOO="Reading package lists...
 Building dependency tree...
@@ -52,7 +56,11 @@ The following information may help to resolve the situation:
 
 The following packages have unmet dependencies:
  builddeps:not-foo : Depends: not-foo-bd but it is not installable
-E: Unsatisfiable dependency group builddeps:not-foo:amd64 -> not-foo-bd:amd64"
+E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. builddeps:not-foo:amd64=1 is selected for install
+   2. builddeps:not-foo:amd64 Depends not-foo-bd
+      but none of the choices are installable:
+      [no choices]"
 else
 BUILDDEPFOO="Reading package lists...
 Building dependency tree...
diff --git a/test/integration/test-apt-install-file-reltag b/test/integration/test-apt-install-file-reltag
index 0637c5472..053c785fd 100755
--- a/test/integration/test-apt-install-file-reltag
+++ b/test/integration/test-apt-install-file-reltag
@@ -31,7 +31,7 @@ buildsimplenativepackage 'foobar2' 'all' '1' 'unstable' 'Depends: foo (= 5), baz
 
 testunsat() {
     testfailure "$@"
-    testsuccess grep -E "^E: (Unable to correct problems,|Conflict:)" "${TMPWORKINGDIRECTORY}/rootdir/tmp/testfailure.output"
+    testsuccess grep -E "^E: (Unable to correct problems,|Unable to satisfy dependencies. Reached two conflicting decisions)" "${TMPWORKINGDIRECTORY}/rootdir/tmp/testfailure.output"
 }
 
 ln -s "$(readlink -f ./incoming/foobar2_1_all.deb)" foobar.deb
diff --git a/test/integration/test-apt-never-markauto-sections b/test/integration/test-apt-never-markauto-sections
index 95ba47553..bf08507d0 100755
--- a/test/integration/test-apt-never-markauto-sections
+++ b/test/integration/test-apt-never-markauto-sections
@@ -49,7 +49,18 @@ Remv foreignpkg:i386 [1]
 Remv nosection [1]
 Remv texteditor [1]' aptget autoremove mydesktop -s
 
-testfailuremsg 'E: Conflict: not texteditor:amd64 -> not bad-texteditor:amd64 but mydesktop:amd64 -> mydesktop-core:amd64 -> bad-texteditor:amd64' aptget autoremove texteditor -s --solver 3.0 #-o Debug::pkgDepCache::AutoInstall=1 -o Debug::pkgProblemResolver=1 -o Debug::pkgDepCache::Marker=1
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. bad-texteditor:amd64 is selected for install because:
+      1. mydesktop:amd64 is selected for install
+      2. mydesktop:amd64 Depends mydesktop-core
+      3. mydesktop-core:amd64 Depends bad-texteditor | texteditor
+         [selected mydesktop-core:amd64]
+      For context, additional choices that could not be installed:
+      * In mydesktop-core:amd64 Depends bad-texteditor | texteditor:
+        - texteditor:amd64 is selected for removal
+   2. bad-texteditor:amd64 Depends texteditor
+      but none of the choices are installable:
+      - texteditor:amd64 is selected for removal' aptget autoremove texteditor -s --solver 3.0 #-o Debug::pkgDepCache::AutoInstall=1 -o Debug::pkgProblemResolver=1 -o Debug::pkgDepCache::Marker=1
 testsuccessequal 'Reading package lists...
 Building dependency tree...
 Reading state information...
diff --git a/test/integration/test-bug-598669-install-postfix-gets-exim-heavy b/test/integration/test-bug-598669-install-postfix-gets-exim-heavy
index 6c9fb60c0..98479b5fd 100755
--- a/test/integration/test-bug-598669-install-postfix-gets-exim-heavy
+++ b/test/integration/test-bug-598669-install-postfix-gets-exim-heavy
@@ -1,4 +1,4 @@
-#!/bin/sh
+t-bug-598669-install-postfix-gets-exim-heavy!/bin/sh
 set -e
 
 TESTDIR="$(readlink -f "$(dirname "$0")")"
@@ -7,7 +7,13 @@ setupenvironment
 configarchitecture "i386"
 setupaptarchive
 
-testfailuremsg "E: Conflict: exim4-daemon-light:i386 -> not postfix:i386=2.7.1-1 but postfix:i386=2.7.1-1" aptget install postfix --solver 3.0
+# FIXME: Should this say selected postifx?
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. postfix:i386=2.7.1-1 is selected for install
+   2. postfix:i386=2.7.1-1 is not selected for install because:
+      1. exim4-daemon-light:i386 is selected for install
+      2. exim4-daemon-light:i386 Conflicts mail-transport-agent
+         [selected exim4-daemon-light:i386]" aptget install postfix --solver 3.0
 allowremovemanual
 testfailureequal "Reading package lists...
 Building dependency tree...
diff --git a/test/integration/test-bug-601961-install-info b/test/integration/test-bug-601961-install-info
index 6d68372b5..be55e76a7 100755
--- a/test/integration/test-bug-601961-install-info
+++ b/test/integration/test-bug-601961-install-info
@@ -60,4 +60,8 @@ The following information may help to resolve the situation:
 
 The following packages have unmet dependencies:
  findutils : Depends: essentialpkg but it is not going to be installed
-E: Conflict: findutils:i386 -> essentialpkg:i386 but not essentialpkg:i386' aptget remove essentialpkg --trivial-only --solver 3.0
+E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. essentialpkg:i386 is selected for removal
+   2. essentialpkg:i386 is selected for install because:
+      1. findutils:i386 is selected for install
+      2. findutils:i386 Depends essentialpkg' aptget remove essentialpkg --trivial-only --solver 3.0
diff --git a/test/integration/test-bug-612557-garbage-upgrade b/test/integration/test-bug-612557-garbage-upgrade
index 4ef241cad..a001c4385 100755
--- a/test/integration/test-bug-612557-garbage-upgrade
+++ b/test/integration/test-bug-612557-garbage-upgrade
@@ -18,7 +18,14 @@ testsuccess aptmark markauto python-uno openoffice.org-common
 testmarkedauto python-uno openoffice.org-common
 
 # The 3.0 solver does not remove openoffice.org-emailmerge because it is manually installed.
-testfailuremsg "E: Conflict: openoffice.org-emailmerge:i386 -> openoffice.org-common:i386 -> openoffice.org-common:i386=1:3.2.1-11+squeeze2 but python-uno:i386=1:3.3.0-2 -> libreoffice-common:i386 -> not openoffice.org-common:i386=1:3.2.1-11+squeeze2" aptget --trivial-only install python-uno --solver 3.0
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. openoffice.org-common:i386=1:3.2.1-11+squeeze2 is not selected for install because:
+      1. python-uno:i386=1:3.3.0-2 is selected as an upgrade
+      2. python-uno:i386=1:3.3.0-2 Depends libreoffice-common
+      3. libreoffice-common:i386 Conflicts openoffice.org-common
+   2. openoffice.org-common:i386 is selected for install because:
+      1. openoffice.org-emailmerge:i386 is selected for install
+      2. openoffice.org-emailmerge:i386 PreDepends openoffice.org-common" aptget --trivial-only install python-uno --solver 3.0
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Reading state information...
diff --git a/test/integration/test-bug-618848-always-respect-user-requests b/test/integration/test-bug-618848-always-respect-user-requests
index d59491af6..b1cccef9d 100755
--- a/test/integration/test-bug-618848-always-respect-user-requests
+++ b/test/integration/test-bug-618848-always-respect-user-requests
@@ -14,7 +14,11 @@ insertpackage 'unstable' 'exim4-daemon-heavy' 'all' '1.0' 'Depends: libdb4.8'
 setupaptarchive
 
 # This does not work in 3.0 solver: We do not remove manually installed packages.
-testfailuremsg "E: Conflict: not libdb4.8:i386 -> not exim4-daemon-light:i386 but exim4-daemon-light:i386" aptget remove libdb4.8 --solver 3.0 -s
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. exim4-daemon-light:i386 is selected for install
+   2. exim4-daemon-light:i386 Depends libdb4.8
+      but none of the choices are installable:
+      - libdb4.8:i386 is selected for removal" aptget remove libdb4.8 --solver 3.0 -s
 allowremovemanual
 testsuccessequal "Reading package lists...
 Building dependency tree...
diff --git a/test/integration/test-bug-632221-cross-dependency-satisfaction b/test/integration/test-bug-632221-cross-dependency-satisfaction
index d101bd1fa..6e39b384c 100755
--- a/test/integration/test-bug-632221-cross-dependency-satisfaction
+++ b/test/integration/test-bug-632221-cross-dependency-satisfaction
@@ -35,7 +35,11 @@ insertsource 'unstable' 'source-specific-armel' 'armel' '1' 'Build-Depends: spec
 
 setupaptarchive
 
-testfailuremsg "E: Unsatisfiable dependency group builddeps:forbidden-no:armel -> amdboot:any:any" aptget build-dep forbidden-no -s -a armel --solver 3.0
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. builddeps:forbidden-no:armel=1 is selected for install
+   2. builddeps:forbidden-no:armel Depends amdboot:any
+      but none of the choices are installable:
+      [no choices]" aptget build-dep forbidden-no -s -a armel --solver 3.0
 testfailureequal 'Reading package lists...
 Reading package lists...
 Building dependency tree...
@@ -49,7 +53,11 @@ The following packages have unmet dependencies:
  builddeps:forbidden-no:armel : Depends: amdboot:any but it is not installable
 E: Unable to correct problems, you have held broken packages.' aptget build-dep forbidden-no -s -a armel --solver internal
 
-testfailuremsg "E: Unsatisfiable dependency group builddeps:forbidden-same:armel -> libc6:any:any" aptget build-dep forbidden-same -s -a armel --solver 3.0
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. builddeps:forbidden-same:armel=1 is selected for install
+   2. builddeps:forbidden-same:armel Depends libc6:any
+      but none of the choices are installable:
+      [no choices]" aptget build-dep forbidden-same -s -a armel --solver 3.0
 testfailureequal 'Reading package lists...
 Reading package lists...
 Building dependency tree...
@@ -63,7 +71,11 @@ The following packages have unmet dependencies:
  builddeps:forbidden-same:armel : Depends: libc6:any but it is not installable
 E: Unable to correct problems, you have held broken packages.' aptget build-dep forbidden-same -s -a armel --solver internal
 
-testfailuremsg 'E: Unsatisfiable dependency group builddeps:forbidden-foreign:armel -> doxygen:any:any' aptget build-dep forbidden-foreign -s -a armel --solver 3.0
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. builddeps:forbidden-foreign:armel=1 is selected for install
+   2. builddeps:forbidden-foreign:armel Depends doxygen:any
+      but none of the choices are installable:
+      [no choices]' aptget build-dep forbidden-foreign -s -a armel --solver 3.0
 testfailureequal 'Reading package lists...
 Reading package lists...
 Building dependency tree...
diff --git a/test/integration/test-bug-675449-essential-are-protected b/test/integration/test-bug-675449-essential-are-protected
index 36e7b645e..c8e832d72 100755
--- a/test/integration/test-bug-675449-essential-are-protected
+++ b/test/integration/test-bug-675449-essential-are-protected
@@ -114,7 +114,7 @@ The following packages have unmet dependencies:
  foo : Depends: libfoo but it is not going to be installed
 E: Error, pkgProblemResolver::Resolve generated breaks, this may be caused by held packages.' aptget purge libfoo -s --solver internal
 
-testequal 'Reading package lists...
+testfailureequal 'Reading package lists...
 Building dependency tree...
 Solving dependencies...
 Some packages could not be installed. This may mean that you have
@@ -125,4 +125,8 @@ The following information may help to resolve the situation:
 
 The following packages have unmet dependencies:
  foo : Depends: libfoo but it is not going to be installed
-E: Conflict: foo:amd64 -> libfoo:amd64 but not libfoo:amd64' aptget purge libfoo -s --solver 3.0
+E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. libfoo:amd64 is selected for removal
+   2. libfoo:amd64 is selected for install because:
+      1. foo:amd64 is selected for install
+      2. foo:amd64 Depends libfoo' aptget purge libfoo -s --solver 3.0
diff --git a/test/integration/test-bug-683786-build-dep-on-virtual-packages b/test/integration/test-bug-683786-build-dep-on-virtual-packages
index 75f0a9626..a682a2f1a 100755
--- a/test/integration/test-bug-683786-build-dep-on-virtual-packages
+++ b/test/integration/test-bug-683786-build-dep-on-virtual-packages
@@ -41,7 +41,11 @@ The following NEW packages will be installed:
 Inst po-debconf (1 unstable [all])
 Conf po-debconf (1 unstable [all])' aptget build-dep dash -s
 
-testfailuremsg 'E: Unsatisfiable dependency group builddeps:dash:armel -> po-debconf:armel' aptget build-dep -aarmel dash -s --solver 3.0
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. builddeps:dash:armel=1 is selected for install
+   2. builddeps:dash:armel Depends po-debconf:armel
+      but none of the choices are installable:
+      [no choices]' aptget build-dep -aarmel dash -s --solver 3.0
 testfailureequal 'Reading package lists...
 Reading package lists...
 Building dependency tree...
@@ -55,7 +59,11 @@ The following packages have unmet dependencies:
  builddeps:dash:armel : Depends: po-debconf:armel but it is not installable
 E: Unable to correct problems, you have held broken packages.' aptget build-dep -aarmel dash -s --solver internal
 
-testfailuremsg 'E: Unsatisfiable dependency group builddeps:diffutils:armel -> texi2html:armel' aptget build-dep -aarmel diffutils -s --solver 3.0
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. builddeps:diffutils:armel=1 is selected for install
+   2. builddeps:diffutils:armel Depends texi2html:armel
+      but none of the choices are installable:
+      [no choices]' aptget build-dep -aarmel diffutils -s --solver 3.0
 testfailureequal 'Reading package lists...
 Reading package lists...
 Building dependency tree...
@@ -78,7 +86,11 @@ The following NEW packages will be installed:
 Inst libselinux1-dev (1 unstable [amd64])
 Conf libselinux1-dev (1 unstable [amd64])" aptget build-dep sed -s
 
-testfailuremsg 'E: Unsatisfiable dependency group builddeps:sed:armel -> libselinux-dev:armel' aptget build-dep -aarmel sed -s --solver 3.0
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. builddeps:sed:armel=1 is selected for install
+   2. builddeps:sed:armel Depends libselinux-dev:armel
+      but none of the choices are installable:
+      [no choices]' aptget build-dep -aarmel sed -s --solver 3.0
 testfailureequal 'Reading package lists...
 Reading package lists...
 Building dependency tree...
diff --git a/test/integration/test-bug-723586-any-stripped-in-single-arch b/test/integration/test-bug-723586-any-stripped-in-single-arch
index 17c3839d1..672413125 100755
--- a/test/integration/test-bug-723586-any-stripped-in-single-arch
+++ b/test/integration/test-bug-723586-any-stripped-in-single-arch
@@ -41,7 +41,11 @@ The following information may help to resolve the situation:
 
 The following packages have unmet dependencies:
  python-mips : Depends: python3:mips but it is not installable
-E: Unsatisfiable dependency group python-mips:amd64 -> python3:mips:any'
+E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. python-mips:amd64=3 is selected for install
+   2. python-mips:amd64 Depends python3:mips
+      but none of the choices are installable:
+      [no choices]'
 else
 FAILLOG='Reading package lists...
 Building dependency tree...
diff --git a/test/integration/test-bug-735967-lib32-to-i386-unavailable b/test/integration/test-bug-735967-lib32-to-i386-unavailable
index 2eedf22ab..83992e386 100755
--- a/test/integration/test-bug-735967-lib32-to-i386-unavailable
+++ b/test/integration/test-bug-735967-lib32-to-i386-unavailable
@@ -50,7 +50,13 @@ Remv lib32nss-mdns [0.9-1]
 Inst libnss-mdns [0.9-1] (0.10-6 unstable [amd64])
 Conf libnss-mdns (0.10-6 unstable [amd64])' aptget dist-upgrade -s --solver internal
 
-testfailuremsg 'E: Unsatisfiable dependency group libfoo:amd64 -> libfoo-bin:amd64' aptget install foo -s --solver 3.0
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. libfoo:amd64 is selected for install because:
+      1. foo:amd64=1 is selected for install
+      2. foo:amd64 Depends libfoo
+   2. libfoo:amd64 Depends libfoo-bin
+      but none of the choices are installable:
+      [no choices]' aptget install foo -s --solver 3.0
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have
diff --git a/test/integration/test-bug-745046-candidate-propagation-fails b/test/integration/test-bug-745046-candidate-propagation-fails
index a8ee50124..8475a4ea1 100755
--- a/test/integration/test-bug-745046-candidate-propagation-fails
+++ b/test/integration/test-bug-745046-candidate-propagation-fails
@@ -39,7 +39,11 @@ The following information may help to resolve the situation:
 
 The following packages have unmet dependencies:
  gedit : Depends: common (>= 2) but it is not installable
-E: Unsatisfiable dependency group gedit:amd64=2 -> common:amd64" aptget install gedit/experimental -sq=0 --solver 3.0
+E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. gedit:amd64=2 is selected as an upgrade
+   2. gedit:amd64=2 Depends common (>= 2)
+      but none of the choices are installable:
+      [no choices]" aptget install gedit/experimental -sq=0 --solver 3.0
 
 insertinstalledpackage 'common' 'amd64' '2'
 
diff --git a/test/integration/test-bug-961266-hold-means-hold b/test/integration/test-bug-961266-hold-means-hold
index 8c18cd757..c97aa0839 100755
--- a/test/integration/test-bug-961266-hold-means-hold
+++ b/test/integration/test-bug-961266-hold-means-hold
@@ -89,7 +89,16 @@ The following information may help to resolve the situation:
 
 The following packages have unmet dependencies:
  git-ng : Depends: git (> 1:2.26.2)
-E: Conflict: git:amd64=1:2.25.1-1 -> not git:amd64=1:2.26.2-1 -> not git-ng:amd64 but git-ng:amd64=1:2.26.2-1 -> git-ng:amd64' apt install git-ng -s --solver 3.0
+E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. git-ng:amd64=1:2.26.2-1 is selected for install
+   2. git-ng:amd64 Depends git (> 1:2.26.2)
+      but none of the choices are installable:
+      - git:amd64=1:2.26.2-1 is not selected for install because:
+        1. git:amd64=1:2.25.1-1 is selected for install
+        2. git:amd64=1:2.25.1-1 conflicts with other versions of itself
+      - git:i386=1:2.26.2-1 is not selected for install because:
+        1. git:amd64=1:2.25.1-1 is selected for install as above
+        2. git:amd64 Conflicts git:i386' apt install git-ng -s --solver 3.0
 
 
 msgmsg 'Now mix it up by' 'holding git-cvs'
@@ -126,7 +135,20 @@ The following information may help to resolve the situation:
 
 The following packages have unmet dependencies:
  git-ng : Depends: git (> 1:2.26.2)
-E: Conflict: git-cvs:amd64=1:2.25.1-1 -> git:amd64=1:2.25.1-1 -> not git:amd64=1:2.26.2-1 but git-ng:amd64=1:2.26.2-1 -> git-ng:amd64 -> git:amd64=1:2.26.2-1' apt install git-ng -s --solver 3.0
+E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. git:amd64=1:2.26.2-1 is selected as an upgrade because:
+      1. git-ng:amd64=1:2.26.2-1 is selected for install
+      2. git-ng:amd64 Depends git (> 1:2.26.2)
+         [selected git-ng:amd64]
+      For context, additional choices that could not be installed:
+      * In git-ng:amd64 Depends git (> 1:2.26.2):
+        - git:i386=1:2.26.2-1 is not selected for install because:
+          1. git:amd64 is selected for install
+          2. git:amd64 Conflicts git:i386
+   2. git:amd64=1:2.26.2-1 is not selected for install because:
+      1. git-cvs:amd64=1:2.25.1-1 is selected for install
+      2. git-cvs:amd64=1:2.25.1-1 Depends git (< 1:2.25.1-.)
+      3. git:amd64=1:2.25.1-1 conflicts with other versions of itself' apt install git-ng -s --solver 3.0
 
 
 msgmsg 'Now mix it up by' 'holding both'
@@ -162,4 +184,13 @@ The following information may help to resolve the situation:
 
 The following packages have unmet dependencies:
  git-ng : Depends: git (> 1:2.26.2)
-E: Conflict: git:amd64=1:2.25.1-1 -> not git:amd64=1:2.26.2-1 -> not git-ng:amd64 but git-ng:amd64=1:2.26.2-1 -> git-ng:amd64' apt install git-ng -s --solver 3.0
+E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. git-ng:amd64=1:2.26.2-1 is selected for install
+   2. git-ng:amd64 Depends git (> 1:2.26.2)
+      but none of the choices are installable:
+      - git:amd64=1:2.26.2-1 is not selected for install because:
+        1. git:amd64=1:2.25.1-1 is selected for install
+        2. git:amd64=1:2.25.1-1 conflicts with other versions of itself
+      - git:i386=1:2.26.2-1 is not selected for install because:
+        1. git:amd64=1:2.25.1-1 is selected for install as above
+        2. git:amd64 Conflicts git:i386' apt install git-ng -s --solver 3.0
diff --git a/test/integration/test-explore-or-groups-in-markinstall b/test/integration/test-explore-or-groups-in-markinstall
index 4c67296d7..60de59193 100755
--- a/test/integration/test-explore-or-groups-in-markinstall
+++ b/test/integration/test-explore-or-groups-in-markinstall
@@ -161,7 +161,13 @@ testfailureequal "$BADSOLVETEXT3
 The following packages have unmet dependencies:
  bad-upgrade-level1 : Depends: bad-upgrade-level0 (>= 2) but 1 is to be installed
                       Depends: unneeded2 but it is not going to be installed
-E: Unsatisfiable dependency group bad-upgrade-level0:amd64=2 -> unknown:amd64" apt install bad-upgrade-level1 -s --solver 3.0
+E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. bad-upgrade-level0:amd64=2 is selected as an upgrade because:
+      1. bad-upgrade-level1:amd64=2 is selected as an upgrade
+      2. bad-upgrade-level1:amd64=2 Depends bad-upgrade-level0 (>= 2)
+   2. bad-upgrade-level0:amd64=2 Depends unknown
+      but none of the choices are installable:
+      [no choices]" apt install bad-upgrade-level1 -s --solver 3.0
 testfailureequal "$BADSOLVETEXT
 The following packages have unmet dependencies:
  bad-conflict-level0 : Conflicts: bad-conflict-level2 but 1 is to be installed
@@ -171,7 +177,15 @@ testfailureequal "$BADSOLVETEXT3
 The following packages have unmet dependencies:
  bad-conflict-level2 : Depends: bad-conflict-level1 but it is not going to be installed
                        Depends: unneeded2 but it is not going to be installed
-E: Conflict: bad-conflict-level2:amd64=1 -> not bad-conflict-level0:amd64 -> not bad-conflict-level1:amd64 but bad-conflict-level2:amd64=1 -> bad-conflict-level2:amd64 -> bad-conflict-level1:amd64" apt install bad-conflict-level2 -s --solver 3.0
+E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. bad-conflict-level1:amd64 is selected for install because:
+      1. bad-conflict-level2:amd64=1 is selected for install
+      2. bad-conflict-level2:amd64 Depends bad-conflict-level1
+   2. bad-conflict-level1:amd64 Depends bad-conflict-level0
+      but none of the choices are installable:
+      - bad-conflict-level0:amd64 is not selected for install because:
+        1. bad-conflict-level2:amd64=1 is selected for install as above
+        2. bad-conflict-level0:amd64 Conflicts bad-conflict-level2" apt install bad-conflict-level2 -s --solver 3.0
 
 if $TEST_WITH_APTITUDE; then
 	testsuccesstailequal 6 'The following packages have been kept back:
diff --git a/test/integration/test-handling-broken-orgroups b/test/integration/test-handling-broken-orgroups
index f9c436f81..5c882b516 100755
--- a/test/integration/test-handling-broken-orgroups
+++ b/test/integration/test-handling-broken-orgroups
@@ -47,7 +47,11 @@ Inst coolstuff2 (1.0-1 unstable [all])
 Conf stuff (1.0-1 unstable [all])
 Conf coolstuff2 (1.0-1 unstable [all])' aptget install coolstuff2 -s
 
-testfailuremsg 'E: Unsatisfiable dependency group coolstuff-broken:i386 -> cool2:i386' aptget install coolstuff-broken --solver 3.0 -s
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. coolstuff-broken:i386=1.0-1 is selected for install
+   2. coolstuff-broken:i386 Depends cool2 | stuff2
+      but none of the choices are installable:
+      [no choices]' aptget install coolstuff-broken --solver 3.0 -s
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have
@@ -95,7 +99,11 @@ Inst coolstuff-provided (1.0-1 unstable [all])
 Conf extrastuff (1.0-1 unstable [all])
 Conf coolstuff-provided (1.0-1 unstable [all])' aptget install coolstuff-provided -s
 
-testfailuremsg 'E: Conflict: coolstuff-provided-broken:i386=1.0-1 -> coolstuff-provided-broken:i386 -> extrastuff:i386=1.0-1 but not extrastuff:i386=1.0-1' aptget install coolstuff-provided-broken --solver 3.0 -s
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. extrastuff:i386=1.0-1 is not selected for install
+   2. extrastuff:i386=1.0-1 is selected for install because:
+      1. coolstuff-provided-broken:i386=1.0-1 is selected for install
+      2. coolstuff-provided-broken:i386 Depends cool2 | stuff-abi-2' aptget install coolstuff-provided-broken --solver 3.0 -s
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have
diff --git a/test/integration/test-ignore-provides-if-versioned-breaks b/test/integration/test-ignore-provides-if-versioned-breaks
index 27197e1e6..87e609bef 100755
--- a/test/integration/test-ignore-provides-if-versioned-breaks
+++ b/test/integration/test-ignore-provides-if-versioned-breaks
@@ -32,7 +32,12 @@ insertpackage 'unstable' 'foo-same-breaker-none' 'i386' '1.0' 'Breaks: foo-same'
 
 
 setupaptarchive
-testfailuremsg 'E: Conflict: foo-provider:i386=1.0 -> not foo-breaker-none:i386 but foo-breaker-none:i386=1.0 -> foo-breaker-none:i386' aptget install foo-provider foo-breaker-none -s --solver 3.0
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. foo-breaker-none:i386=1.0 is selected for install
+   2. foo-breaker-none:i386 is not selected for install because:
+      1. foo-provider:i386=1.0 is selected for install
+      2. foo-breaker-none:i386 Breaks foo
+         [selected foo-provider:i386=1.0]' aptget install foo-provider foo-breaker-none -s --solver 3.0
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have
@@ -71,7 +76,12 @@ Conf foo (4.0 unstable [i386])
 Conf foo-breaker-3 (1.0 unstable [i386])
 Conf foo-provider (1.0 unstable [i386])' aptget install foo-provider foo-breaker-3 -s
 
-testfailuremsg 'E: Conflict: foo-foreign-breaker-none:i386=1.0 -> foo-foreign-breaker-none:i386 -> not foo-foreign-provider:i386=1.0 but foo-foreign-provider:i386=1.0' aptget install foo-foreign-provider foo-foreign-breaker-none -s --solver 3.0
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. foo-foreign-provider:i386=1.0 is selected for install
+   2. foo-foreign-provider:i386=1.0 is not selected for install because:
+      1. foo-foreign-breaker-none:i386=1.0 is selected for install
+      2. foo-foreign-breaker-none:i386 Breaks foo-foreign
+         [selected foo-foreign-breaker-none:i386]' aptget install foo-foreign-provider foo-foreign-breaker-none -s --solver 3.0
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have
@@ -110,7 +120,12 @@ Conf foo-foreign:amd64 (4.0 unstable [amd64])
 Conf foo-foreign-breaker-3 (1.0 unstable [i386])
 Conf foo-foreign-provider (1.0 unstable [i386])' aptget install foo-foreign-provider foo-foreign-breaker-3 -s
 
-testfailuremsg 'E: Conflict: foo-same-provider:i386=1.0 -> not foo-same-breaker-none:i386 but foo-same-breaker-none:i386=1.0 -> foo-same-breaker-none:i386' aptget install foo-same-provider foo-same-breaker-none -s --solver 3.0
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. foo-same-breaker-none:i386=1.0 is selected for install
+   2. foo-same-breaker-none:i386 is not selected for install because:
+      1. foo-same-provider:i386=1.0 is selected for install
+      2. foo-same-breaker-none:i386 Breaks foo-same
+         [selected foo-same-provider:i386=1.0]' aptget install foo-same-provider foo-same-breaker-none -s --solver 3.0
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have
diff --git a/test/integration/test-ignore-provides-if-versioned-conflicts b/test/integration/test-ignore-provides-if-versioned-conflicts
index caff5e3b0..cdf69656e 100755
--- a/test/integration/test-ignore-provides-if-versioned-conflicts
+++ b/test/integration/test-ignore-provides-if-versioned-conflicts
@@ -33,7 +33,12 @@ insertpackage 'unstable' 'foo-same-breaker-none' 'i386' '1.0' 'Conflicts: foo-sa
 
 setupaptarchive
 
-testfailuremsg 'E: Conflict: foo-provider:i386=1.0 -> not foo-breaker-none:i386 but foo-breaker-none:i386=1.0 -> foo-breaker-none:i386' aptget install foo-provider foo-breaker-none -s --solver 3.0
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. foo-breaker-none:i386=1.0 is selected for install
+   2. foo-breaker-none:i386 is not selected for install because:
+      1. foo-provider:i386=1.0 is selected for install
+      2. foo-breaker-none:i386 Conflicts foo
+         [selected foo-provider:i386=1.0]' aptget install foo-provider foo-breaker-none -s --solver 3.0
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have
@@ -72,7 +77,12 @@ Conf foo (4.0 unstable [i386])
 Conf foo-breaker-3 (1.0 unstable [i386])
 Conf foo-provider (1.0 unstable [i386])' aptget install foo-provider foo-breaker-3 -s
 
-testfailuremsg 'E: Conflict: foo-foreign-breaker-none:i386=1.0 -> foo-foreign-breaker-none:i386 -> not foo-foreign-provider:i386=1.0 but foo-foreign-provider:i386=1.0' aptget install foo-foreign-provider foo-foreign-breaker-none -s --solver 3.0
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. foo-foreign-provider:i386=1.0 is selected for install
+   2. foo-foreign-provider:i386=1.0 is not selected for install because:
+      1. foo-foreign-breaker-none:i386=1.0 is selected for install
+      2. foo-foreign-breaker-none:i386 Conflicts foo-foreign
+         [selected foo-foreign-breaker-none:i386]' aptget install foo-foreign-provider foo-foreign-breaker-none -s --solver 3.0
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have
@@ -111,7 +121,12 @@ Conf foo-foreign:amd64 (4.0 unstable [amd64])
 Conf foo-foreign-breaker-3 (1.0 unstable [i386])
 Conf foo-foreign-provider (1.0 unstable [i386])' aptget install foo-foreign-provider foo-foreign-breaker-3 -s
 
-testfailuremsg 'E: Conflict: foo-same-provider:i386=1.0 -> not foo-same-breaker-none:i386 but foo-same-breaker-none:i386=1.0 -> foo-same-breaker-none:i386' aptget install foo-same-provider foo-same-breaker-none -s --solver 3.0
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. foo-same-breaker-none:i386=1.0 is selected for install
+   2. foo-same-breaker-none:i386 is not selected for install because:
+      1. foo-same-provider:i386=1.0 is selected for install
+      2. foo-same-breaker-none:i386 Conflicts foo-same
+         [selected foo-same-provider:i386=1.0]' aptget install foo-same-provider foo-same-breaker-none -s --solver 3.0
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have
diff --git a/test/integration/test-multiarch-allowed b/test/integration/test-multiarch-allowed
index 9d8920e0f..ca13cc50d 100755
--- a/test/integration/test-multiarch-allowed
+++ b/test/integration/test-multiarch-allowed
@@ -64,18 +64,36 @@ Inst needsfoo:i386 (1 unstable [i386])
 Conf foo:i386 (1 unstable [i386])
 Conf needsfoo:i386 (1 unstable [i386])' aptget install needsfoo:i386 -s
 # FIXME: same problem, but two different unmet dependency messages depending on install order
-testfailuremsg "E: Conflict: foo:amd64=1 -> not foo:i386 -> not needsfoo:i386 but needsfoo:i386=1 -> needsfoo:i386" aptget install needsfoo:i386 foo:amd64 -s --solver 3.0
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. needsfoo:i386=1 is selected for install
+   2. needsfoo:i386 Depends foo:i386
+      but none of the choices are installable:
+      - foo:i386 is not selected for install because:
+        1. foo:amd64=1 is selected for install
+        2. foo:i386 Conflicts foo" aptget install needsfoo:i386 foo:amd64 -s --solver 3.0
 testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  foo : Conflicts: foo:i386 but 1 is to be installed
  foo:i386 : Conflicts: foo but 1 is to be installed
 E: Unable to correct problems, you have held broken packages." aptget install needsfoo:i386 foo:amd64 -s --solver internal
-testfailuremsg "E: Conflict: foo:amd64=1 -> not foo:i386 -> not needsfoo:i386 but needsfoo:i386=1 -> needsfoo:i386" aptget install foo:amd64 needsfoo:i386 -s --solver 3.0
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. needsfoo:i386=1 is selected for install
+   2. needsfoo:i386 Depends foo:i386
+      but none of the choices are installable:
+      - foo:i386 is not selected for install because:
+        1. foo:amd64=1 is selected for install
+        2. foo:i386 Conflicts foo" aptget install foo:amd64 needsfoo:i386 -s --solver 3.0
 testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  needsfoo:i386 : Depends: foo:i386 but it is not installable
 E: Unable to correct problems, you have held broken packages." aptget install foo:amd64 needsfoo:i386 -s --solver internal
-testfailuremsg "E: Conflict: foo:i386=1 -> not foo:amd64 -> not needsfoo:amd64 but needsfoo:amd64=1 -> needsfoo:amd64" aptget install needsfoo foo:i386 -s --solver 3.0
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. needsfoo:amd64=1 is selected for install
+   2. needsfoo:amd64 Depends foo
+      but none of the choices are installable:
+      - foo:amd64 is not selected for install because:
+        1. foo:i386=1 is selected for install
+        2. foo:amd64 Conflicts foo:i386" aptget install needsfoo foo:i386 -s --solver 3.0
 testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  foo : Conflicts: foo:i386 but 1 is to be installed
@@ -135,11 +153,19 @@ if [ "$APT_SOLVER" = "3.0" ]; then
 NEEDSFOO2NATIVE="$BADPREFIX
 The following packages have unmet dependencies:
  needsfoover2 : Depends: foo:any (>= 2)
-E: Unsatisfiable dependency group needsfoover2:amd64 -> foo:any:any"
+E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. needsfoover2:amd64=1 is selected for install
+   2. needsfoover2:amd64 Depends foo:any (>= 2)
+      but none of the choices are installable:
+      [no choices]"
 NEEDSFOO2FOREIGN="$BADPREFIX
 The following packages have unmet dependencies:
  needsfoover2:i386 : Depends: foo:any (>= 2)
-E: Unsatisfiable dependency group needsfoover2:i386 -> foo:any:any"
+E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. needsfoover2:i386=1 is selected for install
+   2. needsfoover2:i386 Depends foo:any (>= 2)
+      but none of the choices are installable:
+      [no choices]"
 else
 NEEDSFOO2NATIVE="$BADPREFIX
 The following packages have unmet dependencies:
@@ -156,9 +182,31 @@ testfailureequal "$NEEDSFOO2FOREIGN" aptget install needsfoover2:i386 foo:i386 -
 testfailureequal "$NEEDSFOO2NATIVE" aptget install needsfoover2 foo:i386 -s
 
 solveableinsinglearch2() {
-	testfailuremsg 'E: Conflict: hatesfoo:amd64=1 -> hatesfoo:amd64 -> not foo:amd64=1 but foo:amd64=1' aptget install foo hatesfoo -s --solver 3.0
-	testfailuremsg 'E: Conflict: hatesfooany:amd64=1 -> hatesfooany:amd64 -> not foo:amd64=1 but foo:amd64=1' aptget install foo hatesfooany -s --solver 3.0
-	testfailuremsg 'E: Conflict: hatesfoonative:amd64=1 -> hatesfoonative:amd64 -> not foo:amd64=1 but foo:amd64=1' aptget install foo hatesfoonative -s --solver 3.0
+	testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. foo:amd64=1 is selected for install
+   2. foo:amd64=1 is not selected for install because:
+      1. hatesfoo:amd64=1 is selected for install
+      2. hatesfoo:amd64 Conflicts foo' aptget install foo hatesfoo -s --solver 3.0
+
+	if [ "$(getarchitectures)" = "amd64 " ]; then
+		testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. foo:amd64=1 is selected for install
+   2. foo:amd64=1 is not selected for install because:
+      1. hatesfooany:amd64=1 is selected for install
+      2. hatesfooany:amd64 Conflicts foo:any' aptget install foo hatesfooany -s --solver 3.0
+	else
+		testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. foo:amd64=1 is selected for install
+   2. foo:amd64=1 is not selected for install because:
+      1. hatesfooany:amd64=1 is selected for install
+      2. hatesfooany:amd64 Conflicts foo:any
+         [selected hatesfooany:amd64]' aptget install foo hatesfooany -s --solver 3.0
+	fi
+	testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. foo:amd64=1 is selected for install
+   2. foo:amd64=1 is not selected for install because:
+      1. hatesfoonative:amd64=1 is selected for install
+      2. hatesfoonative:amd64 Conflicts foo:amd64' aptget install foo hatesfoonative -s --solver 3.0
 	testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  hatesfoo : Conflicts: foo but 1 is to be installed
@@ -171,12 +219,21 @@ The following packages have unmet dependencies:
 E: Unable to correct problems, you have held broken packages." aptget install foo hatesfoonative -s --solver internal
 }
 solveableinsinglearch2
-testfailuremsg "E: Conflict: hatesfoo:amd64=1 -> hatesfoo:amd64 -> not foo:i386=1 but foo:i386=1" aptget install foo:i386 hatesfoo -s --solver 3.0
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. foo:i386=1 is selected for install
+   2. foo:i386=1 is not selected for install because:
+      1. hatesfoo:amd64=1 is selected for install
+      2. hatesfoo:amd64 Conflicts foo:i386" aptget install foo:i386 hatesfoo -s --solver 3.0
 testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  hatesfoo : Conflicts: foo:i386 but 1 is to be installed
 E: Unable to correct problems, you have held broken packages." aptget install foo:i386 hatesfoo -s --solver internal
-testfailuremsg "E: Conflict: hatesfooany:amd64=1 -> hatesfooany:amd64 -> not foo:i386=1 but foo:i386=1" aptget install foo:i386 hatesfooany -s --solver 3.0
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. foo:i386=1 is selected for install
+   2. foo:i386=1 is not selected for install because:
+      1. hatesfooany:amd64=1 is selected for install
+      2. hatesfooany:amd64 Conflicts foo:any
+         [selected hatesfooany:amd64]" aptget install foo:i386 hatesfooany -s --solver 3.0
 testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  hatesfooany : Conflicts: foo:any
@@ -191,7 +248,11 @@ Inst hatesfoonative (1 unstable [amd64])
 Conf foo:i386 (1 unstable [i386])
 Conf hatesfoonative (1 unstable [amd64])' aptget install foo:i386 hatesfoonative -s
 
-testfailuremsg "E: Unsatisfiable dependency group needscoolfoo:i386 -> coolfoo:i386" aptget install needscoolfoo:i386 -s --solver 3.0
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. needscoolfoo:i386=1 is selected for install
+   2. needscoolfoo:i386 Depends coolfoo:i386
+      but none of the choices are installable:
+      [no choices]" aptget install needscoolfoo:i386 -s --solver 3.0
 testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  needscoolfoo:i386 : Depends: coolfoo:i386 but it is not installable
@@ -264,12 +325,20 @@ Inst needscoolfoover1 (1 unstable [amd64])
 Conf coolfoo (1 unstable [amd64])
 Conf coolfoover (1 unstable [amd64])
 Conf needscoolfoover1 (1 unstable [amd64])' aptget install needscoolfoover1 -s
-	testfailuremsg "E: Unsatisfiable dependency group needscoolfoover2:amd64 -> coolfoo:any:any" aptget install needscoolfoover2 -s --solver 3.0
+	testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. needscoolfoover2:amd64=1 is selected for install
+   2. needscoolfoover2:amd64 Depends coolfoo:any (>= 2)
+      but none of the choices are installable:
+      [no choices]" aptget install needscoolfoover2 -s --solver 3.0
 	testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  needscoolfoover2 : Depends: coolfoo:any (>= 2)
 E: Unable to correct problems, you have held broken packages." aptget install needscoolfoover2 -s --solver internal
-	testfailuremsg "E: Unsatisfiable dependency group needscoolfoover3:amd64 -> coolfoo:any:any" aptget install needscoolfoover3 -s --solver 3.0
+	testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. needscoolfoover3:amd64=1 is selected for install
+   2. needscoolfoover3:amd64 Depends coolfoo:any (>= 2)
+      but none of the choices are installable:
+      [no choices]" aptget install needscoolfoover3 -s --solver 3.0
 	testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  needscoolfoover3 : Depends: coolfoo:any (>= 2)
diff --git a/test/integration/test-multiarch-foreign b/test/integration/test-multiarch-foreign
index 5a7b1a3b7..a04b854a5 100755
--- a/test/integration/test-multiarch-foreign
+++ b/test/integration/test-multiarch-foreign
@@ -179,14 +179,23 @@ distribution that some required packages have not yet been created
 or been moved out of Incoming.
 The following information may help to resolve the situation:
 '
-	testfailuremsg "E: Conflict: ${1%:*}:$4=1.0 -> not hates-foo:amd64 but hates-foo:amd64=1.0 -> hates-foo:amd64"  aptget install $1 hates-foo -s --solver 3.0
+	testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. hates-foo:amd64=1.0 is selected for install
+   2. hates-foo:amd64 is not selected for install because:
+      1. ${1%:*}:$4=1.0 is selected for install
+      2. hates-foo:amd64 Conflicts foo
+         [selected ${1%:*}:$4=1.0]"  aptget install $1 hates-foo -s --solver 3.0
 	testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  hates-foo : Conflicts: foo
              Conflicts: foo:i386
              Conflicts: foo:armel
 E: Unable to correct problems, you have held broken packages." aptget install $1 hates-foo -s --solver internal
-	testfailuremsg "E: Conflict: $2:amd64=1.0 -> $2:amd64 -> not foo:$4=1.0 but foo:$4=1.0" aptget install $1 $2 -s --solver 3.0
+	testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. foo:$4=1.0 is selected for install
+   2. foo:$4=1.0 is not selected for install because:
+      1. $2:amd64=1.0 is selected for install
+      2. $2:amd64 Conflicts foo:$4" aptget install $1 $2 -s --solver 3.0
 	testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  $2 : Conflicts: foo:$4
diff --git a/test/integration/test-prefer-higher-priority-providers b/test/integration/test-prefer-higher-priority-providers
index e16e98e23..87954c5d4 100755
--- a/test/integration/test-prefer-higher-priority-providers
+++ b/test/integration/test-prefer-higher-priority-providers
@@ -91,7 +91,16 @@ Inst awesome (1 unstable [all])
 Conf baz (1 unstable [all])
 Conf awesome (1 unstable [all])" aptget install awesome foo- bar- -s
 
-testfailuremsg "E: Conflict: awesome:$native=1 -> awesome:$native -> baz:$native=1 -> baz:$native but not baz:$native" aptget install awesome foo- bar- baz- -s --solver 3.0
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. baz:$native is not selected for install
+   2. baz:$native=1 is selected for install because:
+      1. awesome:$native=1 is selected for install
+      2. awesome:$native Depends stuff
+         [selected awesome:$native]
+      For context, additional choices that could not be installed:
+      * In awesome:$native Depends stuff:
+        - foo:$native=1 is not selected for install
+        - bar:$native=1 is not selected for install" aptget install awesome foo- bar- baz- -s --solver 3.0
 testfailureequal "Reading package lists...
 Building dependency tree...
 Package 'foo' is not installed, so not removed
diff --git a/test/integration/test-release-candidate-switching b/test/integration/test-release-candidate-switching
index db7e29495..be5b3f997 100755
--- a/test/integration/test-release-candidate-switching
+++ b/test/integration/test-release-candidate-switching
@@ -449,7 +449,11 @@ The following information may help to resolve the situation:
 The following packages have unmet dependencies:
  uninstallablepkg : Depends: libmtp8 (>= 10:0.20.1) but it is not going to be installed
                     Depends: amarok-utils (= 2.3.2-2+exp) but it is not going to be installed
-E: Unsatisfiable dependency group uninstallablepkg:i386 -> libmtp8:i386" aptget install uninstallablepkg/experimental --trivial-only -V --solver 3.0
+E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. amarok-utils:i386=2.3.2-2+exp is not selected for install
+   2. amarok-utils:i386=2.3.2-2+exp is selected for install because:
+      1. uninstallablepkg:i386=1.0 is selected for install
+      2. uninstallablepkg:i386 Depends amarok-utils (= 2.3.2-2+exp)" aptget install uninstallablepkg/experimental --trivial-only -V --solver 3.0
 
 insertinstalledpackage 'libmtp8' 'i386'  '1'
 insertinstalledpackage 'amarok' 'i386' '3' 'Depends: amarok-common (= 3), libmtp8 (>= 1)'
diff --git a/test/integration/test-solver3-alternatives b/test/integration/test-solver3-alternatives
new file mode 100755
index 000000000..8a3645f82
--- /dev/null
+++ b/test/integration/test-solver3-alternatives
@@ -0,0 +1,32 @@
+#!/bin/sh
+set -e
+
+TESTDIR="$(readlink -f "$(dirname "$0")")"
+. "$TESTDIR/framework"
+setupenvironment
+configarchitecture 'amd64'
+
+insertpackage 'unstable' 'unsat' 'all' '3' 'Depends: a | b'
+insertpackage 'unstable' 'a' 'all' '3' 'Depends: aa|ab'
+insertpackage 'unstable' 'b' 'all' '3' 'Depends: ba|bb'
+insertpackage 'unstable' 'aa' 'all' '3' 'Depends: aax'
+insertpackage 'unstable' 'ab' 'all' '3' 'Depends: abx'
+insertpackage 'unstable' 'ba' 'all' '3' 'Depends: bay'
+insertpackage 'unstable' 'bb' 'all' '3' 'Depends: bby'
+setupaptarchive
+
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. bb:amd64 is selected for install because:
+      1. unsat:amd64=3 is selected for install
+      2. unsat:amd64 Depends a | b
+         [selected b:amd64 for install]
+      3. b:amd64 Depends ba | bb
+         [selected b:amd64]
+      For context, additional choices that could not be installed:
+      * In unsat:amd64 Depends a | b:
+        - a:amd64 is not selected for install
+      * In b:amd64 Depends ba | bb:
+        - ba:amd64 is not selected for install
+   2. bb:amd64 Depends bby
+      but none of the choices are installable:
+      [no choices]" apt install unsat --solver 3.0
diff --git a/test/integration/test-specific-architecture-dependencies b/test/integration/test-specific-architecture-dependencies
index be8ea4245..b9ce155de 100755
--- a/test/integration/test-specific-architecture-dependencies
+++ b/test/integration/test-specific-architecture-dependencies
@@ -194,7 +194,11 @@ The following NEW packages will be installed:
 Inst foo-depender (1 unstable [amd64])
 Conf foo-depender (1 unstable [amd64])' aptget install foo-depender -s
 
-testfailuremsg 'E: Unsatisfiable dependency group foo-depender:i386 -> foo:i386' aptget install foo-depender:i386 -s --solver 3.0
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. foo-depender:i386=1 is selected for install
+   2. foo-depender:i386 Depends foo:i386
+      but none of the choices are installable:
+      [no choices]' aptget install foo-depender:i386 -s --solver 3.0
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have
@@ -313,7 +317,11 @@ Remv libold [1]
 Inst breaker-x64 (1 unstable [amd64])
 Conf breaker-x64 (1 unstable [amd64])' aptget install breaker-x64:amd64 -s
 
-testfailuremsg 'E: Unsatisfiable dependency group depender-x32:amd64 -> libc6:i386:any' aptget install depender-x32 -s --solver 3.0
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. depender-x32:amd64=1 is selected for install
+   2. depender-x32:amd64 Depends libc6:i386
+      but none of the choices are installable:
+      [no choices]' aptget install depender-x32 -s --solver 3.0
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have