From 56c14eab8f399497295bb74d551dc49a4a763486 Mon Sep 17 00:00:00 2001
From: Julian Andres Klode <julian.klode@canonical.com>
Date: Wed, 19 Feb 2025 12:30:51 +0100
Subject: solver3: Simplify Var pointer tagging

Use an integer and tag the lowest bit manually. This makes it
much easier to next convert this into a literal.

Add some constexpr and remove an unnecessary assertion on
CastPkg().
---
 apt-pkg/solver3.h | 31 ++++++++++++++++---------------
 1 file changed, 16 insertions(+), 15 deletions(-)

(limited to 'apt-pkg/solver3.h')

diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h
index 0ad0800ba..e9f1ced7b 100644
--- a/apt-pkg/solver3.h
+++ b/apt-pkg/solver3.h
@@ -304,47 +304,48 @@ class Solver
  */
 struct APT::Solver::Var
 {
-   uint32_t IsVersion : 1;
-   uint32_t MapPtr : 31;
+   uint32_t value;
 
-   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()) {}
+   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) {}
+
+   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
+   constexpr bool empty() const
    {
-      return IsVersion == 0 && MapPtr == 0;
+      return value == 0;
    }
-   bool operator==(Var const other) const
+   constexpr bool operator==(Var const other) const
    {
-      return IsVersion == other.IsVersion && MapPtr == other.MapPtr;
+      return value == other.value;
    }
 
    std::string toString(pkgCache &cache) const
-- 
cgit v1.2.3-70-g09d2


From 7194a6b39c2aa6f1006630975a1bf4ffc3c9daf2 Mon Sep 17 00:00:00 2001
From: Julian Andres Klode <julian.klode@canonical.com>
Date: Thu, 20 Feb 2025 12:21:42 +0100
Subject: solver3: refactor: Return inserted Clause in AddWork()

This avoids relying on the inserted clause being at the back
of the clauses vector.
---
 apt-pkg/solver3.cc | 15 ++++++++-------
 apt-pkg/solver3.h  |  2 +-
 2 files changed, 9 insertions(+), 8 deletions(-)

(limited to 'apt-pkg/solver3.h')

diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc
index c1a1098b5..5469a1881 100644
--- a/apt-pkg/solver3.cc
+++ b/apt-pkg/solver3.cc
@@ -444,13 +444,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)
@@ -931,8 +932,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 +945,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 +964,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 e9f1ced7b..6e45d5f45 100644
--- a/apt-pkg/solver3.h
+++ b/apt-pkg/solver3.h
@@ -246,7 +246,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);
 
-- 
cgit v1.2.3-70-g09d2


From 7d5fe59c19edf06cbee3e0b34d71032322907ae6 Mon Sep 17 00:00:00 2001
From: Julian Andres Klode <julian.klode@canonical.com>
Date: Tue, 4 Mar 2025 22:23:47 +0100
Subject: solver3: cleanup operators for Var

Particularly, use single line and implement operator!=
---
 apt-pkg/solver3.h | 11 +++--------
 1 file changed, 3 insertions(+), 8 deletions(-)

(limited to 'apt-pkg/solver3.h')

diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h
index 6e45d5f45..73ed26030 100644
--- a/apt-pkg/solver3.h
+++ b/apt-pkg/solver3.h
@@ -339,14 +339,9 @@ struct APT::Solver::Var
       return isVersion() ? Ver(cache).ParentPkg() : Pkg(cache);
    }
    // \brief Check if there is no reason.
-   constexpr bool empty() const
-   {
-      return value == 0;
-   }
-   constexpr bool operator==(Var const other) const
-   {
-      return value == other.value;
-   }
+   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
    {
-- 
cgit v1.2.3-70-g09d2


From 142d6499b51451d57fc050c71ffcfb8338e02b7e Mon Sep 17 00:00:00 2001
From: Julian Andres Klode <julian.klode@canonical.com>
Date: Thu, 6 Mar 2025 20:07:00 +0100
Subject: solver3: Support pretty printing clauses

This will print the underlying dependency which is nicer to
read.
---
 apt-pkg/solver3.cc | 21 ++++++++++++++++-----
 apt-pkg/solver3.h  |  2 +-
 2 files changed, 17 insertions(+), 6 deletions(-)

(limited to 'apt-pkg/solver3.h')

diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc
index 5469a1881..d9ed1a7bb 100644
--- a/apt-pkg/solver3.cc
+++ b/apt-pkg/solver3.cc
@@ -231,13 +231,24 @@ 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(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(" | ");
+      }
+      return out;
+   }
    out.append(" -> ");
    for (auto var : solutions)
       out.append(" | ").append(var.toString(cache));
diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h
index 73ed26030..519f48b13 100644
--- a/apt-pkg/solver3.h
+++ b/apt-pkg/solver3.h
@@ -377,7 +377,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;
 };
 
 /**
-- 
cgit v1.2.3-70-g09d2


From 3967b75ae4a10d0d79560dfecb8eb210aad4f4f2 Mon Sep 17 00:00:00 2001
From: Julian Andres Klode <julian.klode@canonical.com>
Date: Thu, 6 Mar 2025 20:07:30 +0100
Subject: solver3: Verbose error messages

Introduce a new function, LongWhyStr() that returns a longer
reason for why something is being installed (or not).

This does the same path walk as the other function does, but
it renders the clauses at each level, and one per line, so
the whole output is a lot more informative.

It is a separate function to keep the existing debug messages
use the simple single line implication graph

We remove the other special case in AddWork() for empty solutions
to mke use of the general case in Solve() instead, and then adapt
the case in Solve() to the same case as in Enqueue(). This also
happens to fix the bug that when we encountered an empty clause
we just printed the clause had no solution, but not how we got
to install the package with the clause.

Adapt the test suite for the changes which is an annoying amount
of paperwork.
---
 apt-pkg/solver3.cc                                 | 207 ++++++++++++++++++---
 apt-pkg/solver3.h                                  |  22 +++
 test/integration/test-apt-get-build-dep-barbarian  |  36 +++-
 test/integration/test-apt-get-build-dep-file       |   6 +-
 test/integration/test-apt-get-install-deb          |  12 +-
 test/integration/test-apt-get-satisfy              |   6 +-
 test/integration/test-apt-get-source-only          |  12 +-
 test/integration/test-apt-install-file-reltag      |   2 +-
 test/integration/test-apt-never-markauto-sections  |  13 +-
 ...test-bug-598669-install-postfix-gets-exim-heavy |  10 +-
 test/integration/test-bug-601961-install-info      |   6 +-
 test/integration/test-bug-612557-garbage-upgrade   |   9 +-
 .../test-bug-618848-always-respect-user-requests   |   6 +-
 .../test-bug-632221-cross-dependency-satisfaction  |  18 +-
 .../test-bug-675449-essential-are-protected        |   8 +-
 .../test-bug-683786-build-dep-on-virtual-packages  |  18 +-
 .../test-bug-723586-any-stripped-in-single-arch    |   6 +-
 .../test-bug-735967-lib32-to-i386-unavailable      |   8 +-
 .../test-bug-745046-candidate-propagation-fails    |   6 +-
 test/integration/test-bug-961266-hold-means-hold   |  37 +++-
 .../test-explore-or-groups-in-markinstall          |  18 +-
 test/integration/test-handling-broken-orgroups     |  12 +-
 .../test-ignore-provides-if-versioned-breaks       |  21 ++-
 .../test-ignore-provides-if-versioned-conflicts    |  21 ++-
 test/integration/test-multiarch-allowed            |  95 ++++++++--
 test/integration/test-multiarch-foreign            |  13 +-
 .../test-prefer-higher-priority-providers          |  11 +-
 test/integration/test-release-candidate-switching  |   6 +-
 test/integration/test-solver3-alternatives         |  32 ++++
 .../test-specific-architecture-dependencies        |  12 +-
 30 files changed, 609 insertions(+), 80 deletions(-)
 create mode 100755 test/integration/test-solver3-alternatives

(limited to 'apt-pkg/solver3.h')

diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc
index 3511132dd..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.
@@ -247,11 +248,15 @@ std::string APT::Solver::Clause::toString(pkgCache &cache, bool pretty) const
 	    break;
 	 out.append(" | ");
       }
-      return out;
    }
-   out.append(" -> ");
-   for (auto var : solutions)
-      out.append(" | ").append(var.toString(cache));
+   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;
 }
 
@@ -303,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.
@@ -375,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;
    }
 
@@ -773,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;
@@ -785,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;
 }
 
@@ -832,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)
       {
@@ -857,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;
       }
diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h
index 519f48b13..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.
    //
@@ -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
@@ -494,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
-- 
cgit v1.2.3-70-g09d2