Merge branch 'solver3' into 'main'

solver3: Refactorings

See merge request apt-team/apt!542

37 files changed, 925 insertions, 852 deletions

diff --git a/apt-pkg/contrib/macros.h b/apt-pkg/contrib/macros.h
index 08e7aeb72..1a76ef60a 100644
--- a/apt-pkg/contrib/macros.h
+++ b/apt-pkg/contrib/macros.h
@@ -33,6 +33,14 @@
 	#define likely(x)	(x)
 	#define unlikely(x)	(x)
 #endif
+
+// Asserts that the result of expr is true
+#define must_succeed(expr) ({                                                                                   \
+   auto result = (expr);                                                                                        \
+   if (unlikely(not result))                                                                                    \
+      fprintf(stderr, "%s:%d: %s: Assertion `%s` failed.\n", __FILE__, __LINE__, __FUNCTION__, #expr), abort(); \
+   result;                                                                                                      \
+})
 #endif
 
 #if APT_GCC_VERSION >= 0x0300
diff --git a/apt-pkg/edsp.cc b/apt-pkg/edsp.cc
index 6c9c3f3ee..2d7fdcc3c 100644
--- a/apt-pkg/edsp.cc
+++ b/apt-pkg/edsp.cc
@@ -796,7 +796,7 @@ bool EDSP::ResolveExternal(const char* const solver, pkgDepCache &Cache,
 			 unsigned int const flags, OpProgress *Progress) {
    if (strstr(solver, "3.") == solver)
    {
-      APT::Solver s(Cache.GetCache(), Cache.GetPolicy(), (EDSP::Request::Flags) flags);
+      APT::Solver::DependencySolver s(Cache.GetCache(), Cache.GetPolicy(), (EDSP::Request::Flags)flags);
       FileFd output;
       bool res = true;
       if (Progress != NULL)
diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc
index 4d7e0ff0b..096cbb521 100644
--- a/apt-pkg/solver3.cc
+++ b/apt-pkg/solver3.cc
@@ -38,188 +38,28 @@
 #include <iomanip>
 #include <sstream>
 
-// FIXME: Helpers stolen from DepCache, please give them back.
-struct APT::Solver::CompareProviders3 /*{{{*/
-{
-   pkgCache &Cache;
-   pkgDepCache::Policy &Policy;
-   pkgCache::PkgIterator const Pkg;
-   APT::Solver &Solver;
-
-   pkgCache::VerIterator bestVersion(pkgCache::PkgIterator pkg)
-   {
-      pkgCache::VerIterator res = pkg.VersionList();
-      for (auto v = res; not v.end(); ++v)
-	 res = std::max(res, v, *this);
-      return res;
-   }
-   bool operator()(Var a, Var b)
-   {
-      pkgCache::VerIterator va = a.Ver(Cache);
-      pkgCache::VerIterator vb = b.Ver(Cache);
-      if (auto pa = a.Pkg(Cache))
-	 va = bestVersion(pa);
-      if (auto pb = b.Pkg(Cache))
-	 vb = bestVersion(pb);
-
-      assert(not va.end() && not vb.end());
-      return (*this)(va, vb);
-   }
-   bool operator()(pkgCache::VerIterator const &AV, pkgCache::VerIterator const &BV)
-   {
-      assert(not AV.end() && not BV.end());
-      pkgCache::PkgIterator const A = AV.ParentPkg();
-      pkgCache::PkgIterator const B = BV.ParentPkg();
-      // Compare versions for the same package. FIXME: Move this to the real implementation
-      if (A == B)
-      {
-	 if (AV == BV)
-	    return false;
-
-	 // Candidate wins in upgrade scenario
-	 if (Solver.IsUpgrade)
-	 {
-	    auto Cand = Solver.GetCandidateVer(A);
-	    if (AV == Cand || BV == Cand)
-	       return (AV == Cand);
-	 }
-
-	 // Installed version wins otherwise
-	 if (A.CurrentVer() == AV || B.CurrentVer() == BV)
-	    return (A.CurrentVer() == AV);
-
-	 // Rest is ordered list, first by priority
-	 if (auto pinA = Solver.GetPriority(AV), pinB = Solver.GetPriority(BV); pinA != pinB)
-	    return pinA > pinB;
-
-	 // Then by version
-	 return _system->VS->CmpVersion(AV.VerStr(), BV.VerStr()) > 0;
-      }
-      // Try obsolete choices only after exhausting non-obsolete choices such that we install
-      // packages replacing them and don't keep back upgrades depending on the replacement to
-      // keep the obsolete package installed.
-      if (Solver.IsUpgrade)
-	 if (auto obsoleteA = Solver.Obsolete(A), obsoleteB = Solver.Obsolete(B); obsoleteA != obsoleteB)
-	    return obsoleteB;
-      // Prefer MA:same packages if other architectures for it are installed
-      if ((AV->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same ||
-	  (BV->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same)
-      {
-	 bool instA = false;
-	 if ((AV->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same)
-	 {
-	    pkgCache::GrpIterator Grp = A.Group();
-	    for (pkgCache::PkgIterator P = Grp.PackageList(); P.end() == false; P = Grp.NextPkg(P))
-	       if (P->CurrentVer != 0)
-	       {
-		  instA = true;
-		  break;
-	       }
-	 }
-	 bool instB = false;
-	 if ((BV->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same)
-	 {
-	    pkgCache::GrpIterator Grp = B.Group();
-	    for (pkgCache::PkgIterator P = Grp.PackageList(); P.end() == false; P = Grp.NextPkg(P))
-	    {
-	       if (P->CurrentVer != 0)
-	       {
-		  instB = true;
-		  break;
-	       }
-	    }
-	 }
-	 if (instA != instB)
-	    return instA;
-      }
-      if ((A->CurrentVer == 0 || B->CurrentVer == 0) && A->CurrentVer != B->CurrentVer)
-	 return A->CurrentVer != 0;
-      // Prefer packages in the same group as the target; e.g. foo:i386, foo:amd64
-      if (A->Group != B->Group && not Pkg.end())
-      {
-	 if (A->Group == Pkg->Group && B->Group != Pkg->Group)
-	    return true;
-	 else if (B->Group == Pkg->Group && A->Group != Pkg->Group)
-	    return false;
-      }
-      // we like essentials
-      if ((A->Flags & pkgCache::Flag::Essential) != (B->Flags & pkgCache::Flag::Essential))
-      {
-	 if ((A->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
-	    return true;
-	 else if ((B->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
-	    return false;
-      }
-      if ((A->Flags & pkgCache::Flag::Important) != (B->Flags & pkgCache::Flag::Important))
-      {
-	 if ((A->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important)
-	    return true;
-	 else if ((B->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important)
-	    return false;
-      }
-      // prefer native architecture
-      if (strcmp(A.Arch(), B.Arch()) != 0)
-      {
-	 if (strcmp(A.Arch(), A.Cache()->NativeArch()) == 0)
-	    return true;
-	 else if (strcmp(B.Arch(), B.Cache()->NativeArch()) == 0)
-	    return false;
-	 std::vector<std::string> archs = APT::Configuration::getArchitectures();
-	 for (std::vector<std::string>::const_iterator a = archs.begin(); a != archs.end(); ++a)
-	    if (*a == A.Arch())
-	       return true;
-	    else if (*a == B.Arch())
-	       return false;
-      }
-      // higher priority seems like a good idea
-      if (AV->Priority != BV->Priority)
-	 return AV->Priority < BV->Priority;
-      if (auto NameCmp = strcmp(A.Name(), B.Name()))
-	 return NameCmp < 0;
-      // unable to decide…
-      return A->ID > B->ID;
-   }
-};
-
-/** \brief Returns \b true for packages matching a regular
- *  expression in APT::NeverAutoRemove.
- */
-class DefaultRootSetFunc2 : public pkgDepCache::DefaultRootSetFunc
+namespace APT::Solver
 {
-   std::unique_ptr<APT::CacheFilter::Matcher> Kernels;
-
-   public:
-   DefaultRootSetFunc2(pkgCache *cache) : Kernels(APT::KernelAutoRemoveHelper::GetProtectedKernelsFilter(cache)) {};
-   ~DefaultRootSetFunc2() override = default;
 
-   bool InRootSet(const pkgCache::PkgIterator &pkg) override { return pkg.end() == false && ((*Kernels)(pkg) || DefaultRootSetFunc::InRootSet(pkg)); };
-}; // FIXME: DEDUP with pkgDepCache.
-/*}}}*/
-
-APT::Solver::Solver(pkgCache &cache, pkgDepCache::Policy &policy, EDSP::Request::Flags requestFlags)
+Solver::Solver(pkgCache &cache)
     : cache(cache),
-      policy(policy),
       rootState(new State),
       pkgStates(cache),
-      verStates(cache),
-      pkgObsolete(cache),
-      priorities(cache),
-      candidates(cache),
-      requestFlags(requestFlags)
+      verStates(cache)
 {
    // Ensure trivially
    static_assert(std::is_trivially_destructible_v<Work>);
-   static_assert(std::is_trivially_destructible_v<Solved>);
-   static_assert(sizeof(APT::Solver::Var) == sizeof(map_pointer<pkgCache::Package>));
-   static_assert(sizeof(APT::Solver::Var) == sizeof(map_pointer<pkgCache::Version>));
+   static_assert(std::is_trivially_destructible_v<Trail>);
+   static_assert(sizeof(Var) == sizeof(map_pointer<pkgCache::Package>));
+   static_assert(sizeof(Var) == sizeof(map_pointer<pkgCache::Version>));
    // Root state is "true".
-   rootState->decision = Decision::MUST;
+   rootState->assignment = LiftedBool::True;
 }
 
-APT::Solver::~Solver() = default;
+Solver::~Solver() = default;
 
 // This function determines if a work item is less important than another.
-bool APT::Solver::Work::operator<(APT::Solver::Work const &b) const
+bool Solver::Work::operator<(Solver::Work const &b) const
 {
    if ((not clause->optional && size < 2) != (not b.clause->optional && b.size < 2))
       return not b.clause->optional && b.size < 2;
@@ -280,40 +120,45 @@ std::string APT::Solver::Clause::toString(pkgCache &cache, bool pretty, bool sho
    return out;
 }
 
-std::string APT::Solver::Work::toString(pkgCache &cache) const
+std::string Solver::Work::toString(pkgCache &cache) const
 {
    std::ostringstream out;
    if (erased)
       out << "Erased ";
    if (clause->optional)
       out << "Optional ";
-   out << "Item (" << ssize_t(size <= clause->solutions.size() ? size : -1) << "@" << depth << ") ";
+   out << "Item (" << ssize_t(size <= clause->solutions.size() ? size : -1) << "@" << level << ") ";
    out << clause->toString(cache);
    return out.str();
 }
 
-inline APT::Solver::Var APT::Solver::bestReason(APT::Solver::Clause const *clause, APT::Solver::Var var) const
+inline Var Solver::bestReason(Clause const *clause, Var var) const
 {
    if (not clause)
       return Var{};
    if (clause->reason == var)
       for (auto choice : clause->solutions)
       {
-	 if (clause->negative && (*this)[choice].decision == Decision::MUST)
+	 if (clause->negative && value(choice) == LiftedBool::True)
 	    return choice;
-	 if (not clause->negative && (*this)[choice].decision == Decision::MUSTNOT)
+	 if (not clause->negative && value(choice) == LiftedBool::False)
 	    return choice;
       }
    return clause->reason;
 }
 
+inline LiftedBool Solver::value(Lit lit) const
+{
+   return lit.sign() ? ~(*this)[lit.var()].assignment : (*this)[lit.var()].assignment;
+}
+
 // Prints an implication graph part of the form A -> B -> C, possibly with "not"
-std::string APT::Solver::WhyStr(Var reason) const
+std::string Solver::WhyStr(Var reason) const
 {
    std::vector<std::string> out;
    while (not reason.empty())
    {
-      if ((*this)[reason].decision == Decision::MUSTNOT)
+      if (value(reason) == LiftedBool::False)
 	 out.push_back(std::string("not ") + reason.toString(cache));
       else
 	 out.push_back(reason.toString(cache));
@@ -328,31 +173,31 @@ 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::string Solver::LongWhyStr(Var var, bool assignment, 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)
+   auto printSelection = [this](Var var, bool assignment)
    {
       std::string s;
-      if (auto pkg = var.Pkg(cache); not decision && pkg && pkg->CurrentVer)
+      if (auto pkg = var.Pkg(cache); not assignment && 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)
+      else if (auto ver = var.Ver(cache); assignment && 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)
+      else if (not assignment)
 	 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.
+   // Helper: Recurse into all of the children of the clause and print the assignment for them.
    auto recurseChildren = [&](const Clause *clause, Var skip = Var())
    {
       if (clause->solutions.empty())
@@ -362,16 +207,16 @@ std::string APT::Solver::LongWhyStr(Var var, bool decision, const Clause *rclaus
 	 if (choice == skip)
 	    continue;
 
-	 if ((*this)[choice].decision == Decision::NONE)
+	 if (value(choice) == LiftedBool::Undefined)
 	    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);
+	    out << prefix << "- " << LongWhyStr(choice, value(choice) == LiftedBool::True, (*this)[choice].reason, prefix + "  ", seen).substr(prefix.size() + 2);
       }
    };
 
    // Inverse version selection clauses that select the package if the version is selected,
    // such as pkg=ver -> pkg, are irrelevant for the user, skip them
-   if (var.Pkg() && decision && rclause && rclause->group == Group::SelectVersion)
+   if (var.Pkg() && assignment && rclause && rclause->group == Group::SelectVersion)
    {
       var = rclause->reason;
       rclause = (*this)[var].reason;
@@ -380,25 +225,25 @@ std::string APT::Solver::LongWhyStr(Var var, bool decision, const Clause *rclaus
    // No reason given, probably a user request or manually installed or essential or whatnot.
    if (not rclause)
    {
-      out << prefix << printSelection(var, decision) << "\n";
+      out << prefix << printSelection(var, assignment) << "\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)
+   // We could be called with a assignment we tried to make but failed due to a conflict;
+   // this checks if it is the real assignment.
+   if (value(var) != LiftedBool::Undefined && assignment == (value(var) == LiftedBool::True) && (*this)[var].reason == rclause)
    {
-      // If we have seen the real decision before; we dont't need to print it again.
+      // If we have seen the real assignment before; we dont't need to print it again.
       if (seen.find(var) != seen.end())
       {
-	 out << prefix << printSelection(var, decision) << " as above\n";
+	 out << prefix << printSelection(var, assignment) << " 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)
+   if (not assignment && rclause && not rclause->negative)
    {
       out << prefix << rclause->toString(cache, true) << "\n";
       out << prefix << "but none of the choices are installable:\n";
@@ -406,13 +251,13 @@ std::string APT::Solver::LongWhyStr(Var var, bool decision, const Clause *rclaus
       return out.str();
    }
 
-   // Build the strongest path from a root to our decision leaf
+   // Build the strongest path from a root to our assignment 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";
+   out << prefix << printSelection(var, assignment) << " 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)
@@ -428,7 +273,7 @@ std::string APT::Solver::LongWhyStr(Var var, bool decision, const Clause *rclaus
       {
 	 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";
+	    out << prefix << (i == 1 ? "" : "1-") << i << ". " << printSelection(*it, state.assignment == LiftedBool::True) << " as above\n";
 	 }
 	 continue;
       }
@@ -437,13 +282,13 @@ std::string APT::Solver::LongWhyStr(Var var, bool decision, const Clause *rclaus
       {
 	 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";
+	    out << prefix << std::setw(w) << " " << "  [selected " << it->toString(cache) << " for " << (state.assignment == LiftedBool::True ? "install" : "remove") << "]\n";
       }
       else
-	 out << prefix << std::setw(w) << i << ". " << printSelection(*it, state.decision == Decision::MUST) << "\n";
+	 out << prefix << std::setw(w) << i << ". " << printSelection(*it, state.assignment == LiftedBool::True) << "\n";
    }
 
-   // Print the leaf. We can't have the leaf in the path because we might be called for an attempted decision
+   // Print the leaf. We can't have the leaf in the path because we might be called for an attempted assignment
    // 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";
@@ -490,122 +335,58 @@ std::string APT::Solver::LongWhyStr(Var var, bool decision, const Clause *rclaus
    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.
-bool APT::Solver::ObsoletedByNewerSourceVersion(pkgCache::VerIterator cand) const
+bool Solver::Assume(Lit lit, const Clause *reason)
 {
-   const auto pkg = cand.ParentPkg();
-   const int candPriority = GetPriority(cand);
-
-   for (auto ver = cand.Cache()->FindGrp(cand.SourcePkgName()).VersionsInSource(); not ver.end(); ver = ver.NextInSource())
-   {
-      // We are only interested in other packages in the same source package; built for the same architecture.
-      if (ver->ParentPkg == cand->ParentPkg || ver.ParentPkg()->Arch != cand.ParentPkg()->Arch ||
-	    (ver->MultiArch & pkgCache::Version::All) != (cand->MultiArch & pkgCache::Version::All) ||
-	     cache.VS->CmpVersion(ver.SourceVerStr(), cand.SourceVerStr()) <= 0)
-	 continue;
-
-      // We also take equal priority here, given that we have a higher version
-      const int priority = GetPriority(ver);
-      if (priority == 0 || priority < candPriority)
-	 continue;
-
-      pkgObsolete[pkg] = 2;
-      if (debug >= 3)
-	 std::cerr << "Obsolete: " << cand.ParentPkg().FullName() << "=" << cand.VerStr() << " due to " << ver.ParentPkg().FullName() << "=" << ver.VerStr() << "\n";
-      return true;
-   }
-
-   return false;
+   trailLim.push_back(trail.size());
+   return Enqueue(lit, std::move(reason));
 }
 
-bool APT::Solver::Obsolete(pkgCache::PkgIterator pkg, bool AllowManual) const
+bool Solver::Enqueue(Lit lit, const Clause *reason)
 {
-   if ((*this)[pkg].flags.manual && not AllowManual)
-      return false;
-   if (pkgObsolete[pkg] != 0)
-      return pkgObsolete[pkg] == 2;
+   assert(not lit.empty());
 
-   auto ver = GetCandidateVer(pkg);
+   auto &state = (*this)[lit.var()];
+   auto assignment = lit.sign() ? LiftedBool::False : LiftedBool::True;
 
-   if (ver.end() && not StrictPinning)
-      ver = pkg.VersionList();
-   if (ver.end())
+   if (state.assignment != LiftedBool::Undefined)
    {
-      if (debug >= 3)
-	 std::cerr << "Obsolete: " << pkg.FullName() << " - not installable\n";
-      pkgObsolete[pkg] = 2;
-      return true;
-   }
-
-   if (ObsoletedByNewerSourceVersion(ver))
-      return true;
-
-   // Any version downloadable is good enough for us tbh
-   for (auto ver = pkg.VersionList(); not ver.end(); ++ver)
-   {
-      if (ver.Downloadable())
-      {
-	 pkgObsolete[pkg] = 1;
-	 return false;
-      }
-   }
-
-   if (debug >= 3)
-      std::cerr << "Obsolete: " << ver.ParentPkg().FullName() << "=" << ver.VerStr() << " - not installable\n";
-   pkgObsolete[pkg] = 2;
-   return true;
-}
-bool APT::Solver::Assume(Var var, bool decision, const Clause *reason)
-{
-   choices.push_back(solved.size());
-   return Enqueue(var, decision, std::move(reason));
-}
-
-bool APT::Solver::Enqueue(Var var, bool decision, const Clause *reason)
-{
-   auto &state = (*this)[var];
-   auto decisionCast = decision ? Decision::MUST : Decision::MUSTNOT;
-
-   if (state.decision != Decision::NONE)
-   {
-      if (state.decision != decisionCast)
+      if (state.assignment != assignment)
       {
 	 std::ostringstream err;
-	 err << "Unable to satisfy dependencies. Reached two conflicting decisions:" << "\n";
+	 err << "Unable to satisfy dependencies. Reached two conflicting assignments:" << "\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);
+	 err << "1. " << LongWhyStr(lit.var(), state.assignment == LiftedBool::True, state.reason, "   ", seen).substr(3) << "\n";
+	 err << "2. " << LongWhyStr(lit.var(), not lit.sign(), reason, "   ", seen).substr(3);
 	 return _error->Error("%s", err.str().c_str());
       }
       return true;
    }
 
-   state.decision = decisionCast;
-   state.depth = depth();
+   state.assignment = assignment;
+   state.level = decisionLevel();
    state.reason = reason;
 
+   // FIXME: Adjust call to bestReason to use lit
    if (unlikely(debug >= 1))
-      std::cerr << "[" << depth() << "] " << (decision ? "Install" : "Reject") << ":" << var.toString(cache) << " (" << WhyStr(bestReason(reason, var)) << ")\n";
+      std::cerr << "[" << decisionLevel() << "] " << (lit.sign() ? "Reject" : "Install") << ":" << lit.var().toString(cache) << " (" << WhyStr(bestReason(reason, lit.var())) << ")\n";
 
-   solved.push_back(Solved{var, std::nullopt});
-   propQ.push(var);
+   trail.push_back(Trail{lit.var(), std::nullopt});
+   propQ.push(lit.var());
 
    return true;
 }
 
-bool APT::Solver::Propagate()
+bool Solver::Propagate()
 {
    while (!propQ.empty())
    {
       Var var = propQ.front();
       propQ.pop();
-      if ((*this)[var].decision == Decision::MUST)
+      if (value(var) == LiftedBool::True)
       {
 	 Discover(var);
 	 for (auto &clause : (*this)[var].clauses)
-	    if (not AddWork(Work{clause.get(), depth()}))
+	    if (not AddWork(Work{clause.get(), decisionLevel()}))
 	       return false;
 	 for (auto rclause : (*this)[var].rclauses)
 	 {
@@ -613,37 +394,37 @@ bool APT::Solver::Propagate()
 	       continue;
 	    if (unlikely(debug >= 3))
 	       std::cerr << "Propagate " << var.toString(cache) << " to NOT " << rclause->reason.toString(cache) << " for dep " << const_cast<Clause *>(rclause)->toString(cache) << std::endl;
-	    if (not Enqueue(rclause->reason, false, rclause))
+	    if (not Enqueue(~rclause->reason, rclause))
 	       return false;
 	 }
       }
-      else if ((*this)[var].decision == Decision::MUSTNOT)
+      else if (value(var) == LiftedBool::False)
       {
 	 for (auto rclause : (*this)[var].rclauses)
 	 {
 	    if (rclause->negative || rclause->reason.empty())
 	       continue;
-	    if ((*this)[rclause->reason].decision == Decision::MUSTNOT)
+	    if (value(rclause->reason) == LiftedBool::False)
 	       continue;
 
 	    auto count = std::count_if(rclause->solutions.begin(), rclause->solutions.end(), [this](auto var)
-				       { return (*this)[var].decision != Decision::MUSTNOT; });
+				       { return value(var) != LiftedBool::False; });
 
-	    if (count == 1 && (*this)[rclause->reason].decision == Decision::MUST)
+	    if (count == 1 && value(rclause->reason) == LiftedBool::True)
 	    {
 	       if (unlikely(debug >= 3))
 		  std::cerr << "Propagate NOT " << var.toString(cache) << " to unit clause " << rclause->toString(cache);
 	       if (rclause->optional)
 	       {
 		  // Enqueue duplicated item, this will ensure we see it at the correct time
-		  if (not AddWork(Work{rclause, depth()}))
+		  if (not AddWork(Work{rclause, decisionLevel()}))
 		     return false;
 	       }
 	       else
 	       {
 		  // Find the variable that must be chosen and enqueue it as a fact
 		  for (auto sol : rclause->solutions)
-		     if ((*this)[sol].decision == Decision::NONE && not Enqueue(sol, true, rclause))
+		     if (value(sol) == LiftedBool::Undefined && not Enqueue(sol, rclause))
 			return false;
 	       }
 	       continue;
@@ -654,7 +435,7 @@ bool APT::Solver::Propagate()
 	    if (unlikely(debug >= 3))
 	       std::cerr << "Propagate NOT " << var.toString(cache) << " to " << rclause->reason.toString(cache) << " for dep " << const_cast<Clause *>(rclause)->toString(cache) << std::endl;
 
-	    if (not Enqueue(rclause->reason, false, rclause)) // Last version invalidated
+	    if (not Enqueue(~rclause->reason, rclause)) // Last version invalidated
 	       return false;
 	 }
       }
@@ -662,6 +443,348 @@ bool APT::Solver::Propagate()
    return true;
 }
 
+void Solver::UndoOne()
+{
+   auto trailItem = trail.back();
+
+   if (unlikely(debug >= 4))
+      std::cerr << "Undoing a single assignment\n";
+
+   if (not trailItem.assigned.empty())
+   {
+      if (unlikely(debug >= 4))
+	 std::cerr << "Unassign " << trailItem.assigned.toString(cache) << "\n";
+      auto &state = (*this)[trailItem.assigned];
+      state.assignment = LiftedBool::Undefined;
+      state.reason = nullptr;
+      state.reasonStr = nullptr;
+      state.level = 0;
+   }
+
+   if (auto work = trailItem.work)
+   {
+      if (unlikely(debug >= 4))
+	 std::cerr << "Adding work item " << work->toString(cache) << std::endl;
+
+      must_succeed(AddWork(std::move(*work)));
+   }
+
+   trail.pop_back();
+
+   // FIXME: Add the undo handling here once we have watchers.
+}
+
+bool Solver::Pop()
+{
+   if (decisionLevel() == 0)
+      return false;
+
+   time_t now = time(nullptr);
+   if (startTime == 0)
+      startTime = now;
+   if (now - startTime >= Timeout)
+      return _error->Error("Solver timed out.");
+
+   if (unlikely(debug >= 2))
+      for (std::string msg; _error->PopMessage(msg);)
+	 std::cerr << "Branch failed: " << msg << std::endl;
+
+   _error->Discard();
+
+   // Assume() actually failed to enqueue anything, abort here
+   if (trailLim.back() == trail.size())
+   {
+      trailLim.pop_back();
+      return true;
+   }
+
+   assert(trailLim.back() < trail.size());
+   int itemsToUndo = trail.size() - trailLim.back();
+   auto choice = trail[trailLim.back()].assigned;
+
+   for (; itemsToUndo; --itemsToUndo)
+      UndoOne();
+
+   // We need to remove any work that is at a higher level.
+   // FIXME: We should just mark the entries as erased and only do a compaction
+   //        of the heap once we have a lot of erased entries in it.
+   trailLim.pop_back();
+   work.erase(std::remove_if(work.begin(), work.end(), [this](Work &w) -> bool
+			     { return w.level > decisionLevel() || w.erased; }),
+	      work.end());
+   std::make_heap(work.begin(), work.end());
+
+   if (unlikely(debug >= 2))
+      std::cerr << "Backtracking to choice " << choice.toString(cache) << "\n";
+
+   // FIXME: There should be a reason!
+   if (not choice.empty() && not Enqueue(~choice, {}))
+      return false;
+
+   (*this)[choice].reasonStr = "backtracked";
+
+   if (unlikely(debug >= 2))
+      std::cerr << "Backtracked to choice " << choice.toString(cache) << "\n";
+
+   return true;
+}
+
+bool Solver::AddWork(Work &&w)
+{
+   if (w.clause->negative)
+   {
+      for (auto var : w.clause->solutions)
+	 if (not Enqueue(~var, w.clause))
+	    return false;
+   }
+   else
+   {
+      if (unlikely(debug >= 3 && w.clause->optional))
+	 std::cerr << "Enqueuing Recommends " << w.clause->toString(cache) << std::endl;
+      if (w.clause->solutions.size() == 1 && not w.clause->optional)
+	 return Enqueue(w.clause->solutions[0], w.clause);
+
+      w.size = std::count_if(w.clause->solutions.begin(), w.clause->solutions.end(), [this](auto V)
+			     { return value(V) != LiftedBool::False; });
+      work.push_back(std::move(w));
+      std::push_heap(work.begin(), work.end());
+   }
+   return true;
+}
+
+bool Solver::Solve()
+{
+   _error->PushToStack();
+   DEFER([&]()
+	 { _error->MergeWithStack(); });
+   startTime = time(nullptr);
+   while (true)
+   {
+      while (_error->PendingError() || not Propagate())
+      {
+	 if (not Pop())
+	    return false;
+      }
+
+      if (work.empty())
+	 break;
+
+      auto item = work.front();
+      std::pop_heap(work.begin(), work.end());
+      work.pop_back();
+      // This item has been replaced with a new one. Remove it.
+      if (item.erased)
+	 continue;
+
+      if (std::any_of(item.clause->solutions.begin(), item.clause->solutions.end(), [this](auto ver)
+		      { return value(ver) == LiftedBool::True; }))
+      {
+	 if (unlikely(debug >= 2))
+	    std::cerr << "ELIDED " << item.toString(cache) << std::endl;
+      }
+      else if (auto candidate = std::find_if(item.clause->solutions.begin(), item.clause->solutions.end(), [this](auto ver)
+					     { return value(ver) == LiftedBool::Undefined; });
+	       candidate != item.clause->solutions.end())
+      {
+	 if (unlikely(debug >= 3))
+	    std::cerr << item.toString(cache) << "\n"
+		      << "(try it: " << candidate->toString(cache) << ")\n";
+	 must_succeed(Assume(*candidate, item.clause));
+      }
+      else if (item.clause->optional)
+      {
+	 if (unlikely(debug >= 1))
+	    std::cerr << item.toString(cache) << "\n";
+      }
+      else
+      {
+	 if (unlikely(debug >= 1))
+	    std::cerr << item.toString(cache) << "\n";
+	 // Enqueue produces the right error message for us here, given that reason has been assigned true already...
+	 assert(value(item.clause->reason) == LiftedBool::True);
+	 must_succeed(not Enqueue(~item.clause->reason, item.clause));
+	 assert(value(item.clause->reason) == LiftedBool::True);
+      }
+      // Must push to trail after any Assume() above.
+      trail.push_back(Trail{Var(), item});
+   }
+
+   return true;
+}
+
+// --------------------------------------------------------------------------------------------------------------------
+// -------------------------------------------- Dependency solver -----------------------------------------------------
+// --------------------------------------------------------------------------------------------------------------------
+// FIXME: Helpers stolen from DepCache, please give them back.
+struct CompareProviders3 /*{{{*/
+{
+   pkgCache &Cache;
+   pkgDepCache::Policy &Policy;
+   pkgCache::PkgIterator const Pkg;
+   APT::Solver::DependencySolver &Solver;
+
+   pkgCache::VerIterator bestVersion(pkgCache::PkgIterator pkg)
+   {
+      pkgCache::VerIterator res = pkg.VersionList();
+      for (auto v = res; not v.end(); ++v)
+	 res = std::max(res, v, *this);
+      return res;
+   }
+   bool operator()(Var a, Var b)
+   {
+      pkgCache::VerIterator va = a.Ver(Cache);
+      pkgCache::VerIterator vb = b.Ver(Cache);
+      if (auto pa = a.Pkg(Cache))
+	 va = bestVersion(pa);
+      if (auto pb = b.Pkg(Cache))
+	 vb = bestVersion(pb);
+
+      assert(not va.end() && not vb.end());
+      return (*this)(va, vb);
+   }
+   bool operator()(pkgCache::VerIterator const &AV, pkgCache::VerIterator const &BV)
+   {
+      assert(not AV.end() && not BV.end());
+      pkgCache::PkgIterator const A = AV.ParentPkg();
+      pkgCache::PkgIterator const B = BV.ParentPkg();
+      // Compare versions for the same package. FIXME: Move this to the real implementation
+      if (A == B)
+      {
+	 if (AV == BV)
+	    return false;
+
+	 // Candidate wins in upgrade scenario
+	 if (Solver.IsUpgrade)
+	 {
+	    auto Cand = Solver.GetCandidateVer(A);
+	    if (AV == Cand || BV == Cand)
+	       return (AV == Cand);
+	 }
+
+	 // Installed version wins otherwise
+	 if (A.CurrentVer() == AV || B.CurrentVer() == BV)
+	    return (A.CurrentVer() == AV);
+
+	 // Rest is ordered list, first by priority
+	 if (auto pinA = Solver.GetPriority(AV), pinB = Solver.GetPriority(BV); pinA != pinB)
+	    return pinA > pinB;
+
+	 // Then by version
+	 return _system->VS->CmpVersion(AV.VerStr(), BV.VerStr()) > 0;
+      }
+      // Try obsolete choices only after exhausting non-obsolete choices such that we install
+      // packages replacing them and don't keep back upgrades depending on the replacement to
+      // keep the obsolete package installed.
+      if (Solver.IsUpgrade)
+	 if (auto obsoleteA = Solver.Obsolete(A), obsoleteB = Solver.Obsolete(B); obsoleteA != obsoleteB)
+	    return obsoleteB;
+      // Prefer MA:same packages if other architectures for it are installed
+      if ((AV->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same ||
+	  (BV->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same)
+      {
+	 bool instA = false;
+	 if ((AV->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same)
+	 {
+	    pkgCache::GrpIterator Grp = A.Group();
+	    for (pkgCache::PkgIterator P = Grp.PackageList(); P.end() == false; P = Grp.NextPkg(P))
+	       if (P->CurrentVer != 0)
+	       {
+		  instA = true;
+		  break;
+	       }
+	 }
+	 bool instB = false;
+	 if ((BV->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same)
+	 {
+	    pkgCache::GrpIterator Grp = B.Group();
+	    for (pkgCache::PkgIterator P = Grp.PackageList(); P.end() == false; P = Grp.NextPkg(P))
+	    {
+	       if (P->CurrentVer != 0)
+	       {
+		  instB = true;
+		  break;
+	       }
+	    }
+	 }
+	 if (instA != instB)
+	    return instA;
+      }
+      if ((A->CurrentVer == 0 || B->CurrentVer == 0) && A->CurrentVer != B->CurrentVer)
+	 return A->CurrentVer != 0;
+      // Prefer packages in the same group as the target; e.g. foo:i386, foo:amd64
+      if (A->Group != B->Group && not Pkg.end())
+      {
+	 if (A->Group == Pkg->Group && B->Group != Pkg->Group)
+	    return true;
+	 else if (B->Group == Pkg->Group && A->Group != Pkg->Group)
+	    return false;
+      }
+      // we like essentials
+      if ((A->Flags & pkgCache::Flag::Essential) != (B->Flags & pkgCache::Flag::Essential))
+      {
+	 if ((A->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
+	    return true;
+	 else if ((B->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
+	    return false;
+      }
+      if ((A->Flags & pkgCache::Flag::Important) != (B->Flags & pkgCache::Flag::Important))
+      {
+	 if ((A->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important)
+	    return true;
+	 else if ((B->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important)
+	    return false;
+      }
+      // prefer native architecture
+      if (strcmp(A.Arch(), B.Arch()) != 0)
+      {
+	 if (strcmp(A.Arch(), A.Cache()->NativeArch()) == 0)
+	    return true;
+	 else if (strcmp(B.Arch(), B.Cache()->NativeArch()) == 0)
+	    return false;
+	 std::vector<std::string> archs = APT::Configuration::getArchitectures();
+	 for (std::vector<std::string>::const_iterator a = archs.begin(); a != archs.end(); ++a)
+	    if (*a == A.Arch())
+	       return true;
+	    else if (*a == B.Arch())
+	       return false;
+      }
+      // higher priority seems like a good idea
+      if (AV->Priority != BV->Priority)
+	 return AV->Priority < BV->Priority;
+      if (auto NameCmp = strcmp(A.Name(), B.Name()))
+	 return NameCmp < 0;
+      // unable to decide…
+      return A->ID > B->ID;
+   }
+};
+
+/** \brief Returns \b true for packages matching a regular
+ *  expression in APT::NeverAutoRemove.
+ */
+class DefaultRootSetFunc2 : public pkgDepCache::DefaultRootSetFunc
+{
+   std::unique_ptr<APT::CacheFilter::Matcher> Kernels;
+
+   public:
+   DefaultRootSetFunc2(pkgCache *cache) : Kernels(APT::KernelAutoRemoveHelper::GetProtectedKernelsFilter(cache)) {};
+   ~DefaultRootSetFunc2() override = default;
+
+   bool InRootSet(const pkgCache::PkgIterator &pkg) override { return pkg.end() == false && ((*Kernels)(pkg) || DefaultRootSetFunc::InRootSet(pkg)); };
+}; // FIXME: DEDUP with pkgDepCache.
+/*}}}*/
+
+DependencySolver::DependencySolver(pkgCache &cache, pkgDepCache::Policy &policy, EDSP::Request::Flags requestFlags)
+    : Solver(cache),
+      policy(policy),
+      requestFlags(requestFlags),
+      pkgObsolete(cache),
+      priorities(cache),
+      candidates(cache)
+{
+}
+
+DependencySolver::~DependencySolver() = default;
+
 static bool SameOrGroup(pkgCache::DepIterator a, pkgCache::DepIterator b)
 {
    while (1)
@@ -679,7 +802,7 @@ static bool SameOrGroup(pkgCache::DepIterator a, pkgCache::DepIterator b)
    return not(a->CompareOp & pkgCache::Dep::Or) && not(b->CompareOp & pkgCache::Dep::Or);
 }
 
-const APT::Solver::Clause *APT::Solver::RegisterClause(Clause &&clause)
+const Clause *DependencySolver::RegisterClause(Clause &&clause)
 {
    auto &clauses = (*this)[clause.reason].clauses;
    pkgCache::DepIterator dep(cache, clause.dep);
@@ -703,17 +826,15 @@ const APT::Solver::Clause *APT::Solver::RegisterClause(Clause &&clause)
 	     earlierDep.TargetPkg() != dep.TargetPkg())
 	    continue;
 	 if (std::none_of(earlierClause->solutions.begin(), earlierClause->solutions.end(), [&clause](auto earlierSol)
-			  { return std::find(clause.solutions.begin(),
-					     clause.solutions.end(),
-					     earlierSol) != clause.solutions.end(); }))
+			  { return std::ranges::contains(clause.solutions,
+							 earlierSol); }))
 	    continue;
 
 	 if (earlierClause->optional == clause.optional)
 	 {
 	    std::erase_if(earlierClause->solutions, [&clause, this](auto earlierSol)
-			  { return std::find(clause.solutions.begin(),
-					     clause.solutions.end(),
-					     earlierSol) == clause.solutions.end(); });
+			  { return not std::ranges::contains(clause.solutions,
+							     earlierSol); });
 
 	    earlierClause->merged.push_front(clause);
 	    merged = true;
@@ -722,9 +843,8 @@ const APT::Solver::Clause *APT::Solver::RegisterClause(Clause &&clause)
 	 {
 	    // If say a Depends has fewer solution than a Recommends, remove the Recommend's extranous ones.
 	    std::erase_if(clause.solutions, [&earlierClause, this](auto sol)
-			  { return std::find(earlierClause->solutions.begin(),
-					     earlierClause->solutions.end(),
-					     sol) == earlierClause->solutions.end(); });
+			  { return not std::ranges::contains(earlierClause->solutions,
+							     sol); });
 
 	    // Remove recursion here, such that we display correctly (if we ever display anywhere...)
 	    auto earlierClauseCopy = *earlierClause;
@@ -744,7 +864,74 @@ const APT::Solver::Clause *APT::Solver::RegisterClause(Clause &&clause)
    return inserted.get();
 }
 
-void APT::Solver::Discover(Var var)
+// 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.
+bool DependencySolver::ObsoletedByNewerSourceVersion(pkgCache::VerIterator cand) const
+{
+   const auto pkg = cand.ParentPkg();
+   const int candPriority = GetPriority(cand);
+
+   for (auto ver = cand.Cache()->FindGrp(cand.SourcePkgName()).VersionsInSource(); not ver.end(); ver = ver.NextInSource())
+   {
+      // We are only interested in other packages in the same source package; built for the same architecture.
+      if (ver->ParentPkg == cand->ParentPkg || ver.ParentPkg()->Arch != cand.ParentPkg()->Arch ||
+	  (ver->MultiArch & pkgCache::Version::All) != (cand->MultiArch & pkgCache::Version::All) ||
+	  cache.VS->CmpVersion(ver.SourceVerStr(), cand.SourceVerStr()) <= 0)
+	 continue;
+
+      // We also take equal priority here, given that we have a higher version
+      const int priority = GetPriority(ver);
+      if (priority == 0 || priority < candPriority)
+	 continue;
+
+      pkgObsolete[pkg] = 2;
+      if (debug >= 3)
+	 std::cerr << "Obsolete: " << cand.ParentPkg().FullName() << "=" << cand.VerStr() << " due to " << ver.ParentPkg().FullName() << "=" << ver.VerStr() << "\n";
+      return true;
+   }
+
+   return false;
+}
+
+bool DependencySolver::Obsolete(pkgCache::PkgIterator pkg, bool AllowManual) const
+{
+   if ((*this)[pkg].flags.manual && not AllowManual)
+      return false;
+   if (pkgObsolete[pkg] != 0)
+      return pkgObsolete[pkg] == 2;
+
+   auto ver = GetCandidateVer(pkg);
+
+   if (ver.end() && not StrictPinning)
+      ver = pkg.VersionList();
+   if (ver.end())
+   {
+      if (debug >= 3)
+	 std::cerr << "Obsolete: " << pkg.FullName() << " - not installable\n";
+      pkgObsolete[pkg] = 2;
+      return true;
+   }
+
+   if (ObsoletedByNewerSourceVersion(ver))
+      return true;
+
+   // Any version downloadable is good enough for us tbh
+   for (auto ver = pkg.VersionList(); not ver.end(); ++ver)
+   {
+      if (ver.Downloadable())
+      {
+	 pkgObsolete[pkg] = 1;
+	 return false;
+      }
+   }
+
+   if (debug >= 3)
+      std::cerr << "Obsolete: " << ver.ParentPkg().FullName() << "=" << ver.VerStr() << " - not installable\n";
+   pkgObsolete[pkg] = 2;
+   return true;
+}
+void DependencySolver::Discover(Var var)
 {
    assert(discoverQ.empty());
    discoverQ.push(var);
@@ -811,15 +998,15 @@ void APT::Solver::Discover(Var var)
 	 }
       }
 
-      // Recursively discover everything else that is not already FALSE by fact (MUSTNOT at depth 0)
+      // Recursively discover everything else that is not already FALSE by fact (False at level 0)
       for (auto const &clause : state.clauses)
 	 for (auto const &var : clause->solutions)
-	    if ((*this)[var].decision != Decision::MUSTNOT || (*this)[var].depth > 0)
+	    if (value(var) != LiftedBool::False || (*this)[var].level > 0)
 	       discoverQ.push(var);
    }
 }
 
-void APT::Solver::RegisterCommonDependencies(pkgCache::PkgIterator Pkg)
+void DependencySolver::RegisterCommonDependencies(pkgCache::PkgIterator Pkg)
 {
    for (auto dep = Pkg.VersionList().DependsList(); not dep.end();)
    {
@@ -846,7 +1033,7 @@ void APT::Solver::RegisterCommonDependencies(pkgCache::PkgIterator Pkg)
    }
 }
 
-APT::Solver::Clause APT::Solver::TranslateOrGroup(pkgCache::DepIterator start, pkgCache::DepIterator end, Var reason)
+Clause DependencySolver::TranslateOrGroup(pkgCache::DepIterator start, pkgCache::DepIterator end, Var reason)
 {
    // Non-important dependencies can only be installed if they are currently satisfied, see the check further
    // below once we have calculated all possible solutions.
@@ -984,204 +1171,8 @@ APT::Solver::Clause APT::Solver::TranslateOrGroup(pkgCache::DepIterator start, p
    return clause;
 }
 
-void APT::Solver::Push(Var var, Work work)
-{
-   if (unlikely(debug >= 2))
-      std::cerr << "Trying choice for " << work.toString(cache) << std::endl;
-
-   choices.push_back(solved.size());
-   solved.push_back(Solved{var, std::move(work)});
-}
-
-void APT::Solver::UndoOne()
-{
-   auto solvedItem = solved.back();
-
-   if (unlikely(debug >= 4))
-      std::cerr << "Undoing a single decision\n";
-
-   if (not solvedItem.assigned.empty())
-   {
-      if (unlikely(debug >= 4))
-	 std::cerr << "Unassign " << solvedItem.assigned.toString(cache) << "\n";
-      auto &state = (*this)[solvedItem.assigned];
-      state.decision = Decision::NONE;
-      state.reason = nullptr;
-      state.reasonStr = nullptr;
-      state.depth = 0;
-   }
-
-   if (auto work = solvedItem.work)
-   {
-      if (unlikely(debug >= 4))
-	 std::cerr << "Adding work item " << work->toString(cache) << std::endl;
-
-      if (not AddWork(std::move(*work)))
-	 abort();
-   }
-
-   solved.pop_back();
-
-   // FIXME: Add the undo handling here once we have watchers.
-}
-
-bool APT::Solver::Pop()
-{
-   if (depth() == 0)
-      return false;
-
-   time_t now = time(nullptr);
-   if (startTime == 0)
-      startTime = now;
-   if (now - startTime >= Timeout)
-      return _error->Error("Solver timed out.");
-
-   if (unlikely(debug >= 2))
-      for (std::string msg; _error->PopMessage(msg);)
-	 std::cerr << "Branch failed: " << msg << std::endl;
-
-   _error->Discard();
-
-   // Assume() actually failed to enqueue anything, abort here
-   if (choices.back() == solved.size())
-   {
-      choices.pop_back();
-      return true;
-   }
-
-   assert(choices.back() < solved.size());
-   int itemsToUndo = solved.size() - choices.back();
-   auto choice = solved[choices.back()].assigned;
-
-   for (; itemsToUndo; --itemsToUndo)
-      UndoOne();
-
-   // We need to remove any work that is at a higher depth.
-   // FIXME: We should just mark the entries as erased and only do a compaction
-   //        of the heap once we have a lot of erased entries in it.
-   choices.pop_back();
-   work.erase(std::remove_if(work.begin(), work.end(), [this](Work &w) -> bool
-			     { return w.depth > depth() || w.erased; }),
-	      work.end());
-   std::make_heap(work.begin(), work.end());
-
-   if (unlikely(debug >= 2))
-      std::cerr << "Backtracking to choice " << choice.toString(cache) << "\n";
-
-   // FIXME: There should be a reason!
-   if (not choice.empty() && not Enqueue(choice, false, {}))
-      return false;
-
-   (*this)[choice].reasonStr = "backtracked";
-
-   if (unlikely(debug >= 2))
-      std::cerr << "Backtracked to choice " << choice.toString(cache) << "\n";
-
-   return true;
-}
-
-bool APT::Solver::AddWork(Work &&w)
-{
-   if (w.clause->negative)
-   {
-      for (auto var : w.clause->solutions)
-	 if (not Enqueue(var, false, w.clause))
-	    return false;
-   }
-   else
-   {
-      if (unlikely(debug >= 3 && w.clause->optional))
-	 std::cerr << "Enqueuing Recommends " << w.clause->toString(cache) << std::endl;
-      if (w.clause->solutions.size() == 1 && not w.clause->optional)
-	 return Enqueue(w.clause->solutions[0], true, w.clause);
-
-      w.size = std::count_if(w.clause->solutions.begin(), w.clause->solutions.end(), [this](auto V)
-			     { return (*this)[V].decision != Decision::MUSTNOT; });
-      work.push_back(std::move(w));
-      std::push_heap(work.begin(), work.end());
-   }
-   return true;
-}
-
-bool APT::Solver::Solve()
-{
-   _error->PushToStack();
-   DEFER([&]() { _error->MergeWithStack(); });
-   startTime = time(nullptr);
-   while (true)
-   {
-      while (not Propagate())
-      {
-	 if (not Pop())
-	    return false;
-      }
-
-      if (work.empty())
-	 break;
-
-      // *NOW* we can pop the item.
-      std::pop_heap(work.begin(), work.end());
-
-      // This item has been replaced with a new one. Remove it.
-      if (work.back().erased)
-      {
-	 work.pop_back();
-	 continue;
-      }
-      auto item = std::move(work.back());
-      work.pop_back();
-      solved.push_back(Solved{Var(), item});
-
-      if (std::any_of(item.clause->solutions.begin(), item.clause->solutions.end(), [this](auto ver)
-		      { return (*this)[ver].decision == Decision::MUST; }))
-      {
-	 if (unlikely(debug >= 2))
-	    std::cerr << "ELIDED " << item.toString(cache) << std::endl;
-	 continue;
-      }
-
-      if (unlikely(debug >= 1))
-	 std::cerr << item.toString(cache) << std::endl;
-
-      bool foundSolution = false;
-      for (auto &sol : item.clause->solutions)
-      {
-	 if ((*this)[sol].decision == Decision::MUSTNOT)
-	 {
-	    if (unlikely(debug >= 3))
-	       std::cerr << "(existing conflict: " << sol.toString(cache) << ")\n";
-	    continue;
-	 }
-	 if (item.size > 1 || item.clause->optional)
-	 {
-	    Push(sol, item);
-	 }
-	 if (unlikely(debug >= 3))
-	    std::cerr << "(try it: " << sol.toString(cache) << ")\n";
-	 if (not Enqueue(sol, true, item.clause) && not Pop())
-	    return false;
-	 foundSolution = true;
-	 break;
-      }
-      if (not foundSolution && not item.clause->optional)
-      {
-	 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;
-      }
-   }
-
-   return true;
-}
-
 // \brief Apply the selections from the dep cache to the solver
-bool APT::Solver::FromDepCache(pkgDepCache &depcache)
+bool DependencySolver::FromDepCache(pkgDepCache &depcache)
 {
    DefaultRootSetFunc2 rootSet(&cache);
    std::vector<Var> manualPackages;
@@ -1195,7 +1186,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache)
 	 bool isPhasing = IsUpgrade && depcache.PhasingApplied(P) && not isForced;
 	 for (auto V = P.VersionList(); not V.end(); ++V)
 	    if (P.CurrentVer() != V && (depcache.GetCandidateVersion(P) != V || isPhasing))
-	       if (not Enqueue(Var(V), false, {}))
+	       if (not Enqueue(~Var(V), {}))
 		  return false;
       }
    }
@@ -1215,7 +1206,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache)
       {
 	 if (unlikely(debug >= 1))
 	    std::cerr << "Hold " << P.FullName() << "\n";
-	 if (P->CurrentVer ? not Enqueue(Var(P.CurrentVer()), true) : not Enqueue(Var(P), false))
+	 if (P->CurrentVer ? not Enqueue(Var(P.CurrentVer())) : not Enqueue(~Var(P)))
 	    return false;
       }
       else if (state.Delete()						  // Normal delete request.
@@ -1225,7 +1216,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache)
       {
 	 if (unlikely(debug >= 1))
 	    std::cerr << "Delete " << P.FullName() << "\n";
-	 if (not Enqueue(Var(P), false))
+	 if (not Enqueue(~Var(P)))
 	    return false;
       }
       else if (state.Install() || (state.Keep() && P->CurrentVer))
@@ -1251,7 +1242,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache)
 	 if (not isOptional)
 	 {
 	    // Pre-empt the non-optional requests, as we don't want to queue them, we can just "unit propagate" here.
-	    if (depcache[P].Keep() ? not Enqueue(Var(P), true) : not Enqueue(Var(depcache.GetCandidateVersion(P)), true))
+	    if (depcache[P].Keep() ? not Enqueue(Var(P)) : not Enqueue(Var(depcache.GetCandidateVersion(P))))
 	       return false;
 	 }
 	 else
@@ -1259,7 +1250,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache)
 	    Clause w{Var(), Group, isOptional};
 	    w.solutions.push_back(Var(P));
 	    auto insertedW = RegisterClause(std::move(w));
-	    if (insertedW && not AddWork(Work{insertedW, depth()}))
+	    if (insertedW && not AddWork(Work{insertedW, decisionLevel()}))
 	       return false;
 
 	    if (not isAuto)
@@ -1275,7 +1266,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache)
 	       shortcircuit.solutions.push_back(Var(V));
 	    std::stable_sort(shortcircuit.solutions.begin(), shortcircuit.solutions.end(), CompareProviders3{cache, policy, P, *this});
 	    auto insertedShort = RegisterClause(std::move(shortcircuit));
-	    if (insertedShort && not AddWork(Work{insertedShort, depth()}))
+	    if (insertedShort && not AddWork(Work{insertedShort, decisionLevel()}))
 	       return false;
 
 	    // Discovery here is needed so the shortcircuit clause can actually become unit.
@@ -1294,7 +1285,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache)
 	 if (unlikely(debug >= 1))
 	    std::cerr << "Install essential package " << P << std::endl;
 	 auto inserted = RegisterClause(std::move(w));
-	 if (inserted && not AddWork(Work{inserted, depth()}))
+	 if (inserted && not AddWork(Work{inserted, decisionLevel()}))
 	    return false;
       }
    }
@@ -1305,15 +1296,14 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache)
    std::stable_sort(manualPackages.begin(), manualPackages.end(), CompareProviders3{cache, policy, {}, *this});
    for (auto assumption : manualPackages)
    {
-      if (not Assume(assumption, true, {}) || not Propagate())
-	 if (not Pop())
-	    abort();
+      if (not Assume(assumption, {}) || not Propagate())
+	 must_succeed(Pop());
    }
 
    return true;
 }
 
-bool APT::Solver::ToDepCache(pkgDepCache &depcache) const
+bool DependencySolver::ToDepCache(pkgDepCache &depcache) const
 {
    FastContiguousCacheMap<pkgCache::Package, bool> movedManual(cache);
    pkgDepCache::ActionGroup group(depcache);
@@ -1321,11 +1311,11 @@ bool APT::Solver::ToDepCache(pkgDepCache &depcache) const
    {
       depcache[P].Marked = 0;
       depcache[P].Garbage = 0;
-      if ((*this)[P].decision == Decision::MUST)
+      if (value(Var(P)) == LiftedBool::True)
       {
 	 pkgCache::VerIterator cand;
 	 for (auto V = P.VersionList(); cand.end() && not V.end(); V++)
-	    if ((*this)[V].decision == Decision::MUST)
+	    if (value(Var(V)) == LiftedBool::True)
 	       cand = V;
 
 	 auto reasonClause = (*this)[cand].reason;
@@ -1379,9 +1369,9 @@ bool APT::Solver::ToDepCache(pkgDepCache &depcache) const
 }
 
 // Command-line
-std::string APT::Solver::InternalCliWhy(pkgDepCache &cache, pkgCache::PkgIterator pkg, bool decision)
+std::string DependencySolver::InternalCliWhy(pkgDepCache &cache, pkgCache::PkgIterator pkg, bool assignment)
 {
-   APT::Solver solver(cache.GetCache(), cache.GetPolicy(), EDSP::Request::Flags(0));
+   DependencySolver solver(cache.GetCache(), cache.GetPolicy(), EDSP::Request::Flags(0));
    // In case nothing has a positive dependency on pkg it may not actually be discovered in a `why-not`
    // scenario, so make sure we discover it explicitly.
    solver.Discover(Var(pkg));
@@ -1389,11 +1379,12 @@ std::string APT::Solver::InternalCliWhy(pkgDepCache &cache, pkgCache::PkgIterato
       return "";
    std::unordered_set<Var> seen;
    std::string buf;
-   if (solver[Var(pkg)].decision == Decision::NONE)
+   if (solver[Var(pkg)].assignment == LiftedBool::Undefined)
       return strprintf(buf, "%s is undecided\n", pkg.FullName().c_str()), buf;
-   if (decision && solver[Var(pkg)].decision != Decision::MUST)
+   if (assignment && solver[Var(pkg)].assignment != LiftedBool::True)
       return strprintf(buf, "%s is not actually marked for install\n", pkg.FullName().c_str()), buf;
-   if (not decision && solver[Var(pkg)].decision == Decision::MUST)
+   if (not assignment && solver[Var(pkg)].assignment == LiftedBool::True)
       return strprintf(buf, "%s is actually marked for install\n", pkg.FullName().c_str()), buf;
-   return solver.LongWhyStr(Var(pkg), decision, solver[Var(pkg)].reason, "", seen);
+   return solver.LongWhyStr(Var(pkg), assignment, solver[Var(pkg)].reason, "", seen);
 }
+} // namespace APT::Solver
diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h
index 45b55d962..4a2b4ac8d 100644
--- a/apt-pkg/solver3.h
+++ b/apt-pkg/solver3.h
@@ -22,7 +22,7 @@
 
 template <typename T> struct always_false : std::false_type {};
 
-namespace APT
+namespace APT::Solver
 {
 
 /**
@@ -59,6 +59,10 @@ class ContiguousCacheMap
    V &operator[](const K *key) { return data_[key->ID]; }
    const V &operator[](const K *key) const { return data_[key->ID]; }
    ~ContiguousCacheMap() { delete[] data_; }
+
+   // Delete copy constructors for memory safety (rule of 3)
+   ContiguousCacheMap(const ContiguousCacheMap &) = delete;
+   ContiguousCacheMap &operator=(const ContiguousCacheMap &) = delete;
 };
 
 /**
@@ -67,6 +71,203 @@ class ContiguousCacheMap
 template <typename K, typename V>
 using FastContiguousCacheMap = ContiguousCacheMap<K, V, true>;
 
+struct Lit;
+
+// \brief Groups of works, these are ordered.
+//
+// Later items will be skipped if they are optional, or we will when backtracking,
+// try a different choice for them.
+enum class Group : uint8_t
+{
+   HoldOrDelete,
+
+   // Satisfying dependencies on entirely new packages first is a good idea because
+   // it may contain replacement packages like libfoo1t64 whereas we later will see
+   // Depends: libfoo1 where libfoo1t64 Provides libfoo1 and we'd have to choose.
+   SatisfyNew,
+   Satisfy,
+   // On a similar note as for SatisfyNew, if the dependency contains obsolete packages
+   // try it last.
+   SatisfyObsolete,
+
+   // Select a version of a package chosen for install.
+   SelectVersion,
+
+   // My intuition tells me that we should try to schedule upgrades first, then
+   // any non-obsolete installed packages, and only finally obsolete ones, such
+   // that newer packages guide resolution of dependencies for older ones, they
+   // may have more stringent dependencies, like a (>> 2) whereas an obsolete
+   // package may have a (>> 1), for example.
+   UpgradeManual,
+   InstallManual,
+   ObsoleteManual,
+
+   // Automatically installed packages must come last in the group, this allows
+   // us to see if they were installed as a dependency of a manually installed package,
+   // allowing a simple implementation of an autoremoval code.
+   UpgradeAuto,
+   KeepAuto,
+   ObsoleteAuto,
+
+   // Satisfy optional dependencies that were previously satisfied but won't otherwise be installed
+   SatisfySuggests,
+};
+
+// \brief This essentially describes the install state in RFC2119 terms.
+enum class LiftedBool : uint8_t
+{
+   // \brief We have not made a choice about the package yet
+   Undefined,
+   // \brief We need to install this package
+   True,
+   // \brief We cannot install this package (need conflicts with it)
+   False,
+};
+
+/**
+ * \brief Tagged union holding either a package, version, or nothing; representing the reason for installing something.
+ *
+ * We want to keep track of the reason why things are being installed such that
+ * we can have sensible debugging abilities; and we want to generically refer to
+ * both packages and versions as variables, hence this class was added.
+ *
+ */
+struct Var
+{
+   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) {}
+
+   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>{mapPtr()};
+   }
+   // \brief Return the version, if any, otherwise 0.
+   map_pointer<pkgCache::Version> Ver() const
+   {
+      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());
+   }
+   // \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();
+   }
+   // \brief Return a package, cast from version if needed
+   pkgCache::PkgIterator CastPkg(pkgCache &cache) const
+   {
+      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 noexcept { return value != other.value; }
+   constexpr bool operator==(Var const other) const noexcept { return value == other.value; }
+
+   /// \brief Negate
+   constexpr Lit operator~() const;
+
+   std::string toString(pkgCache &cache) const
+   {
+      if (auto P = Pkg(cache); not P.end())
+	 return P.FullName();
+      if (auto V = Ver(cache); not V.end())
+	 return V.ParentPkg().FullName() + "=" + V.VerStr();
+      return "(root)";
+   }
+};
+
+/**
+ * \brief A literal is a variable with a sign.
+ *
+ * A literal 'A' means 'install A' whereas a literal '-A' means 'do not install A'.
+ */
+struct Lit
+{
+   private:
+   friend struct std::hash<Lit>;
+   // Private constructor from a number, to be used with operator~
+   explicit constexpr Lit(int32_t value) : value{value} {}
+   int32_t value;
+
+   public:
+   // SAFETY: value must be 31 bit, one bit is needed for the sign.
+   constexpr Lit(Var var) : value{static_cast<int32_t>(var.value)} {}
+
+   // Accessors
+   constexpr Var var() const { return Var(std::abs(value)); }
+   constexpr bool sign() const { return value < 0; }
+   constexpr Lit operator~() const { return Lit(-value); }
+
+   // Properties
+   constexpr bool empty() const { return value == 0; }
+   constexpr bool operator!=(Lit const other) const noexcept { return value != other.value; }
+   constexpr bool operator==(Lit const other) const noexcept { return value == other.value; }
+
+   std::string toString(pkgCache &cache) const { return (sign() ? "not " : "") + var().toString(cache); }
+};
+
+/**
+ * \brief A single clause
+ *
+ * A clause is a normalized, expanded dependency, translated into an implication
+ * in terms of Var objects, that is, `reason -> solutions[0] | ... | solutions[n]`
+ */
+struct Clause
+{
+   // \brief Underyling dependency
+   pkgCache::Dependency *dep = nullptr;
+   // \brief Var for the work
+   Var reason;
+   // \brief The group we are in
+   Group group;
+   // \brief Possible solutions to this task, ordered in order of preference.
+   std::vector<Var> solutions{};
+   // \brief An optional clause does not need to be satisfied
+   bool optional;
+
+   // \brief A negative clause negates the solutions, that is X->A|B you get X->!(A|B), aka X->!A&!B
+   bool negative;
+
+   // \brief An optional clause may be eager
+   bool eager;
+
+   // Clauses merged with this clause
+   std::forward_list<Clause> merged;
+
+   inline Clause(Var reason, Group group, bool optional = false, bool negative = false) : reason(reason), group(group), optional(optional), negative(negative), eager(not optional) {}
+
+   std::string toString(pkgCache &cache, bool pretty = false, bool showMerged = true) const;
+};
+
+constexpr Lit Solver::Var::operator~() const
+{
+   return ~Lit(*this);
+}
+
+inline LiftedBool operator~(LiftedBool value)
+{
+   switch (value)
+   {
+   case LiftedBool::Undefined:
+      return LiftedBool::Undefined;
+   case LiftedBool::True:
+      return LiftedBool::False;
+   case LiftedBool::False:
+      return LiftedBool::True;
+   }
+   abort();
+}
+
 /*
  * \brief APT 3.0 solver
  *
@@ -79,71 +280,24 @@ using FastContiguousCacheMap = ContiguousCacheMap<K, V, true>;
  */
 class Solver
 {
-   enum class Decision : uint16_t;
-   enum class Hint : uint16_t;
-   struct Var;
-   struct CompareProviders3;
+   protected:
    struct State;
-   struct Clause;
    struct Work;
-   struct Solved;
-   friend struct std::hash<APT::Solver::Var>;
+   struct Trail;
 
-   // \brief Groups of works, these are ordered.
-   //
-   // Later items will be skipped if they are optional, or we will when backtracking,
-   // try a different choice for them.
-   enum class Group : uint8_t
-   {
-      HoldOrDelete,
-
-      // Satisfying dependencies on entirely new packages first is a good idea because
-      // it may contain replacement packages like libfoo1t64 whereas we later will see
-      // Depends: libfoo1 where libfoo1t64 Provides libfoo1 and we'd have to choose.
-      SatisfyNew,
-      Satisfy,
-      // On a similar note as for SatisfyNew, if the dependency contains obsolete packages
-      // try it last.
-      SatisfyObsolete,
-
-      // Select a version of a package chosen for install.
-      SelectVersion,
-
-      // My intuition tells me that we should try to schedule upgrades first, then
-      // any non-obsolete installed packages, and only finally obsolete ones, such
-      // that newer packages guide resolution of dependencies for older ones, they
-      // may have more stringent dependencies, like a (>> 2) whereas an obsolete
-      // package may have a (>> 1), for example.
-      UpgradeManual,
-      InstallManual,
-      ObsoleteManual,
-
-      // Automatically installed packages must come last in the group, this allows
-      // us to see if they were installed as a dependency of a manually installed package,
-      // allowing a simple implementation of an autoremoval code.
-      UpgradeAuto,
-      KeepAuto,
-      ObsoleteAuto,
-
-      // Satisfy optional dependencies that were previously satisfied but won't otherwise be installed
-      SatisfySuggests,
-   };
-
-   // \brief Type to record depth at. This may very well be a 16-bit
-   // unsigned integer, then change Solver::State::Decision to be a
+   // \brief Type to record decision level at. This may very well be a 16-bit
+   // unsigned integer, then change Solver::State::LiftedBool to be a
    // uint16_t class enum as well to get a more compact space.
-   using depth_type = unsigned int;
+   using level_type = unsigned int;
 
    // Documentation
    template <typename T>
    using heap = std::vector<T>;
 
-   static_assert(sizeof(depth_type) >= sizeof(map_id_t));
+   static_assert(sizeof(level_type) >= sizeof(map_id_t));
 
    // Cache is needed to construct Iterators from Version objects we see
    pkgCache &cache;
-   // Policy is needed for determining candidate version.
-   pkgDepCache::Policy &policy;
    // Root state
    std::unique_ptr<State> rootState;
    // States for packages
@@ -174,304 +328,211 @@ class Solver
    inline State &operator[](Var r);
    inline const State &operator[](Var r) const;
 
-   mutable FastContiguousCacheMap<pkgCache::Package, char> pkgObsolete;
-   // \brief Check if package is obsolete.
-   // \param AllowManual controls whether manual packages can be obsolete
-   bool Obsolete(pkgCache::PkgIterator pkg, bool AllowManual=false) const;
-   bool ObsoletedByNewerSourceVersion(pkgCache::VerIterator cand) const;
-
-   mutable FastContiguousCacheMap<pkgCache::Version, short> priorities;
-   short GetPriority(pkgCache::VerIterator ver) const
-   {
-      if (priorities[ver] == 0)
-	 priorities[ver] = policy.GetPriority(ver);
-      return priorities[ver];
-   }
-
-   mutable ContiguousCacheMap<pkgCache::Package, pkgCache::VerIterator> candidates;
-   pkgCache::VerIterator GetCandidateVer(pkgCache::PkgIterator pkg) const
-   {
-      if (candidates[pkg].end())
-	 candidates[pkg] = policy.GetCandidateVer(pkg);
-      return candidates[pkg];
-   }
-
    // \brief Heap of the remaining work.
    //
-   // We are using an std::vector with std::make_heap(), std::push_heap(),
-   // and std::pop_heap() rather than a priority_queue because we need to
-   // be able to iterate over the queued work and see if a choice would
-   // invalidate any work.
+   // In contrast to MiniSAT which picks undecided literals and decides them,
+   // we keep track of unsolved active clauses in a priority queue. This allows
+   // us to for example, solve Depends before Recommends (see Group).
    heap<Work> work;
 
-   // \brief Backlog of solved work.
-   //
-   // Solved work may become invalidated when backtracking, so store it
-   // here to revisit it later. This is similar to what MiniSAT calls the
-   // trail; one distinction is that we have both literals and our work
-   // queue to be concerned about
-   std::vector<Solved> solved;
+   /// \brief Trail of assignments done, and clauses solved.
+   ///
+   /// Record past assignments and solved clauses such that we can revert them when
+   /// backtracking.
+   std::vector<Trail> trail;
+
+   /// \brief Separator indices for different decision levels in trail
+   std::vector<level_type> trailLim{};
 
    // \brief Propagation queue
    std::queue<Var> propQ;
-   // \brief Discover variables
-   std::queue<Var> discoverQ;
-
-   // \brief Current decision level.
-   //
-   // This is an index into the solved vector.
-   std::vector<depth_type> choices{};
 
    // \brief The time we called Solve()
    time_t startTime{};
 
-   EDSP::Request::Flags requestFlags;
    /// Various configuration options
    std::string version{_config->Find("APT::Solver", "3.0")};
    // \brief Debug level
    int debug{_config->FindI("Debug::APT::Solver")};
-   // \brief If set, we try to keep automatically installed packages installed.
-   bool KeepAuto{version == "3.0" || not _config->FindB("APT::Get::AutomaticRemove")};
-   // \brief Determines if we are in upgrade mode.
-   bool IsUpgrade{_config->FindB("APT::Solver::Upgrade", requestFlags &EDSP::Request::UPGRADE_ALL)};
-   // \brief If set, removals are allowed.
-   bool AllowRemove{_config->FindB("APT::Solver::Remove", not(requestFlags & EDSP::Request::FORBID_REMOVE))};
-   // \brief If set, removal of manual packages is allowed.
-   bool AllowRemoveManual{AllowRemove && _config->FindB("APT::Solver::RemoveManual", true)};
-   // \brief If set, installs are allowed.
-   bool AllowInstall{_config->FindB("APT::Solver::Install", not(requestFlags & EDSP::Request::FORBID_NEW_INSTALL))};
-   // \brief If set, we use strict pinning.
-   bool StrictPinning{_config->FindB("APT::Solver::Strict-Pinning", true)};
-   // \brief If set, we install missing recommends and pick new best packages.
-   bool FixPolicyBroken{_config->FindB("APT::Get::Fix-Policy-Broken")};
-   // \brief If set, we use strict pinning.
-   bool DeferVersionSelection{_config->FindB("APT::Solver::Defer-Version-Selection", true)};
    // \brief If set, we use strict pinning.
    int Timeout{_config->FindI("APT::Solver::Timeout", 10)};
 
-   // \brief Keep recommends installed
-   bool KeepRecommends{_config->FindB("APT::AutoRemove::RecommendsImportant", true)};
-   // \brief Keep suggests installed
-   bool KeepSuggests{_config->FindB("APT::AutoRemove::SuggestsImportant", true)};
-
    // \brief Discover a variable, translating the underlying dependencies to the SAT presentation
    //
    // This does a breadth-first search of the entire dependency tree of var,
    // utilizing the discoverQ above.
-   void Discover(Var var);
-   // \brief Link a clause into the watchers
-   const Clause *RegisterClause(Clause &&clause);
-   // \brief Enqueue dependencies shared by all versions of the package.
-   void RegisterCommonDependencies(pkgCache::PkgIterator Pkg);
-
-   // \brief Translate an or group into a clause object
-   [[nodiscard]] Clause TranslateOrGroup(pkgCache::DepIterator start, pkgCache::DepIterator end, Var reason);
+   virtual void Discover(Var var) = 0;
    // \brief Propagate all pending propagations
    [[nodiscard]] bool Propagate();
 
-   // \brief Return the current depth (choices.size() with casting)
-   depth_type depth()
+   // \brief Return the current level (.size() with casting)
+   level_type decisionLevel()
    {
-      return static_cast<depth_type>(choices.size());
+      return static_cast<level_type>(trailLim.size());
    }
    inline Var bestReason(Clause const *clause, Var var) const;
+   inline LiftedBool value(Lit lit) const;
 
    public:
-   // \brief Create a new decision level.
-   void Push(Var var, Work work);
    // \brief Revert to the previous decision level.
    [[nodiscard]] bool Pop();
-   // \brief Undo a single assignment / solved work item
+   // \brief Undo a single assignment / trail work item
    void UndoOne();
    // \brief Add work to our work queue.
    [[nodiscard]] bool AddWork(Work &&work);
 
    // \brief Basic solver initializer. This cannot fail.
-   Solver(pkgCache &Cache, pkgDepCache::Policy &Policy, EDSP::Request::Flags requestFlags);
-   ~Solver();
-
-   // Assume that the variable is decided as specified.
-   [[nodiscard]] bool Assume(Var var, bool decision, const Clause *reason = nullptr);
-   // Enqueue a decision fact
-   [[nodiscard]] bool Enqueue(Var var, bool decision, const Clause *reason = nullptr);
+   Solver(pkgCache &Cache);
+   virtual ~Solver();
 
-   // \brief Apply the selections from the dep cache to the solver
-   [[nodiscard]] bool FromDepCache(pkgDepCache &depcache);
-   // \brief Apply the solver result to the depCache
-   [[nodiscard]] bool ToDepCache(pkgDepCache &depcache) const;
+   // Assume a literal
+   [[nodiscard]] bool Assume(Lit lit, const Clause *reason = nullptr);
+   // Enqueue a fact
+   [[nodiscard]] bool Enqueue(Lit lit, const Clause *reason = nullptr);
 
    // \brief Solve the dependencies
    [[nodiscard]] bool Solve();
 
    // Print dependency chain
-   std::string WhyStr(Var reason) const;
+   virtual 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`.
+    * Print a reason as to why `rclause` implies `assignment` 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 assignment The assumed assignment to print the reason for (may be different from actual assignment 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;
-
-   // \brief Temporary internal API with external linkage for the `apt why` and `apt why-not` commands.
-   APT_PUBLIC static std::string InternalCliWhy(pkgDepCache &depcache, pkgCache::PkgIterator Pkg, bool decision);
+   virtual std::string LongWhyStr(Var var, bool assignment, const Clause *rclause, std::string prefix, std::unordered_set<Var> &seen) const;
 };
 
-}; // namespace APT
-
-/**
- * \brief Tagged union holding either a package, version, or nothing; representing the reason for installing something.
+/*
+ * \brief APT 3.0 solver
  *
- * We want to keep track of the reason why things are being installed such that
- * we can have sensible debugging abilities; and we want to generically refer to
- * both packages and versions as variables, hence this class was added.
+ * This is a simple solver focused on understandability and sensible results, it
+ * will not generally find all solutions to the problem but will try to find the best
+ * ones.
  *
+ * It is a brute force solver with heuristics, conflicts learning, and 2**32 levels
+ * of backtracking.
  */
-struct APT::Solver::Var
+class DependencySolver : public Solver
 {
-   uint32_t value;
+   friend class CompareProviders3;
 
-   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) {}
+   // Policy is needed for determining candidate version.
+   pkgDepCache::Policy &policy;
+   // Request flags determine the behavior of the options below, make sure it comes first.
+   EDSP::Request::Flags requestFlags;
 
-   inline constexpr bool isVersion() const { return value & 1; }
-   inline constexpr uint32_t mapPtr() const { return value >> 1; }
+   // Configuration options for the dependency solver
+   bool KeepAuto{version == "3.0" || not _config->FindB("APT::Get::AutomaticRemove")};
+   bool IsUpgrade{_config->FindB("APT::Solver::Upgrade", requestFlags &EDSP::Request::UPGRADE_ALL)};
+   bool AllowRemove{_config->FindB("APT::Solver::Remove", not(requestFlags & EDSP::Request::FORBID_REMOVE))};
+   bool AllowRemoveManual{AllowRemove && _config->FindB("APT::Solver::RemoveManual", true)};
+   bool AllowInstall{_config->FindB("APT::Solver::Install", not(requestFlags & EDSP::Request::FORBID_NEW_INSTALL))};
+   bool StrictPinning{_config->FindB("APT::Solver::Strict-Pinning", true)};
+   bool FixPolicyBroken{_config->FindB("APT::Get::Fix-Policy-Broken")};
+   bool DeferVersionSelection{_config->FindB("APT::Solver::Defer-Version-Selection", true)};
+   bool KeepRecommends{_config->FindB("APT::AutoRemove::RecommendsImportant", true)};
+   bool KeepSuggests{_config->FindB("APT::AutoRemove::SuggestsImportant", true)};
 
-   // \brief Return the package, if any, otherwise 0.
-   map_pointer<pkgCache::Package> Pkg() const
-   {
-      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>{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());
-   }
-   // \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();
-   }
-   // \brief Return a package, cast from version if needed
-   pkgCache::PkgIterator CastPkg(pkgCache &cache) const
+   // Helper functions for detecting obsolete packages
+   mutable FastContiguousCacheMap<pkgCache::Package, char> pkgObsolete;
+   bool Obsolete(pkgCache::PkgIterator pkg, bool AllowManual = false) const;
+   bool ObsoletedByNewerSourceVersion(pkgCache::VerIterator cand) const;
+
+   // GetPriority() with caching
+   mutable FastContiguousCacheMap<pkgCache::Version, short> priorities;
+   short GetPriority(pkgCache::VerIterator ver) const
    {
-      return isVersion() ? Ver(cache).ParentPkg() : Pkg(cache);
+      if (priorities[ver] == 0)
+	 priorities[ver] = policy.GetPriority(ver);
+      return priorities[ver];
    }
-   // \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 operator==(Var const other) const { return value == other.value; }
 
-   std::string toString(pkgCache &cache) const
+   // GetCandidateVer() with caching
+   mutable ContiguousCacheMap<pkgCache::Package, pkgCache::VerIterator> candidates;
+   pkgCache::VerIterator GetCandidateVer(pkgCache::PkgIterator pkg) const
    {
-      if (auto P = Pkg(cache); not P.end())
-	 return P.FullName();
-      if (auto V = Ver(cache); not V.end())
-	 return V.ParentPkg().FullName() + "=" + V.VerStr();
-      return "(root)";
+      if (candidates[pkg].end())
+	 candidates[pkg] = policy.GetCandidateVer(pkg);
+      return candidates[pkg];
    }
-};
-
-/**
- * \brief A single clause
- *
- * A clause is a normalized, expanded dependency, translated into an implication
- * in terms of Var objects, that is, `reason -> solutions[0] | ... | solutions[n]`
- */
-struct APT::Solver::Clause
-{
-   // \brief Underyling dependency
-   pkgCache::Dependency *dep = nullptr;
-   // \brief Var for the work
-   Var reason;
-   // \brief The group we are in
-   Group group;
-   // \brief Possible solutions to this task, ordered in order of preference.
-   std::vector<Var> solutions{};
-   // \brief An optional clause does not need to be satisfied
-   bool optional;
 
-   // \brief A negative clause negates the solutions, that is X->A|B you get X->!(A|B), aka X->!A&!B
-   bool negative;
-
-   // \brief An optional clause may be eager
-   bool eager;
+   // \brief Discover variables
+   std::queue<Var> discoverQ;
+   /// \brief Discover the dependencies of the variable
+   void Discover(Var var) override;
+   /// \brief Link a clause into the watchers
+   const Clause *RegisterClause(Clause &&clause);
+   /// \brief Enqueue dependencies shared by all versions of the package.
+   void RegisterCommonDependencies(pkgCache::PkgIterator Pkg);
 
-   // Clauses merged with this clause
-   std::forward_list<Clause> merged;
+   /// \brief Translate an or group into a clause object
+   [[nodiscard]] Clause TranslateOrGroup(pkgCache::DepIterator start, pkgCache::DepIterator end, Var reason);
 
-   inline Clause(Var reason, Group group, bool optional = false, bool negative = false) : reason(reason), group(group), optional(optional), negative(negative), eager(not optional) {}
+   public:
+   // \brief Basic solver initializer. This cannot fail.
+   DependencySolver(pkgCache &Cache, pkgDepCache::Policy &Policy, EDSP::Request::Flags requestFlags);
+   ~DependencySolver() override;
 
-   std::string toString(pkgCache &cache, bool pretty = false, bool showMerged = true) const;
+   /// \brief Apply the selections from the dep cache to the solver
+   [[nodiscard]] bool FromDepCache(pkgDepCache &depcache);
+   /// \brief Apply the solver result to the depCache
+   [[nodiscard]] bool ToDepCache(pkgDepCache &depcache) const;
+   /// \brief Temporary internal API with external linkage for the `apt why` and `apt why-not` commands.
+   APT_PUBLIC static std::string InternalCliWhy(pkgDepCache &depcache, pkgCache::PkgIterator Pkg, bool assignment);
 };
-
+}; // namespace APT::Solver
 /**
  * \brief A single work item
  *
  * A work item is a positive dependency that still needs to be resolved. Work
- * is ordered, by depth, length of solutions, and optionality.
+ * is ordered, by level, length of solutions, and optionality.
  *
  * The work can always be recalculated from the state by iterating over dependencies
  * of all packages in there, finding solutions to them, and then adding all dependencies
  * not yet resolved to the work queue.
  */
-struct APT::Solver::Work
+struct APT::Solver::Solver::Work
 {
    const Clause *clause;
 
-   // \brief The depth at which the item has been added
-   depth_type depth;
+   // \brief The level at which the item has been added
+   level_type level;
 
-   // Number of valid choices
+   /// Number of valid choices at insertion time
    size_t size{0};
 
    // \brief This item should be removed from the queue.
    bool erased{false};
 
-   bool operator<(APT::Solver::Work const &b) const;
+   bool operator<(APT::Solver::Solver::Work const &b) const;
    std::string toString(pkgCache &cache) const;
-   inline Work(const Clause *clause, depth_type depth) : clause(clause), depth(depth) {}
-};
-
-// \brief This essentially describes the install state in RFC2119 terms.
-enum class APT::Solver::Decision : uint16_t
-{
-   // \brief We have not made a choice about the package yet
-   NONE,
-   // \brief We need to install this package
-   MUST,
-   // \brief We cannot install this package (need conflicts with it)
-   MUSTNOT,
+   inline Work(const Clause *clause, level_type level) : clause(clause), level(level) {}
 };
 
 /**
  * \brief The solver state
  *
- * For each version, the solver records a decision at a certain level. It
+ * For each version, the solver records a assignment at a certain level. It
  * maintains an array mapping from version ID to state.
  */
-struct APT::Solver::State
+struct APT::Solver::Solver::State
 {
-   // \brief The reason for causing this state (invalid for NONE).
+   // \brief The reason for causing this state (invalid for Undefined).
    //
    // Rejects may have been caused by a later state. Consider we select
-   // between x1 and x2 in depth = N. If we now find dependencies of x1
+   // between x1 and x2 in level = N. If we now find dependencies of x1
    // leading to a conflict with a package in K < N, we will record all
-   // of them as REJECT in depth = K.
+   // of them as REJECT in level = K.
    //
-   // You can follow the reason chain upwards as long as the depth
+   // You can follow the reason chain upwards as long as the level
    // doesn't increase to unwind.
    //
    // Vars < 0 are package ID, reasons > 0 are version IDs.
@@ -479,11 +540,10 @@ struct APT::Solver::State
 
    const char *reasonStr{};
 
-   // \brief The depth at which the decision has been taken
-   depth_type depth{0};
+   // \brief The level at which the value has been assigned
+   level_type level{0};
 
-   // \brief This essentially describes the install state in RFC2119 terms.
-   Decision decision{Decision::NONE};
+   LiftedBool assignment{LiftedBool::Undefined};
 
    // \brief Flags.
    struct
@@ -501,20 +561,26 @@ struct APT::Solver::State
 };
 
 /**
- * \brief A solved item.
+ * \brief A trail item.
  *
- * Here we keep track of solved clauses and variable assignments such that we can easily undo
- * them.
+ * In MiniSAT, a trail item is an assigned literal. However, we store an assigned variable instead,
+ * since the assignment is still recorded when we need to access the trail; there does not appear
+ * to be a substantial value in recording the sign here; but it produces a risk for a disagreement
+ * between the actual state and the sign recorded in the trail.
+ *
+ * In addition to MiniSAT's trail, we also need to keep a trail of solved Work items; that is
+ * clauses that were being solved, as when undoing the trail, we need to mark those clauses
+ * active again by putting them back on the work heap.
  */
-struct APT::Solver::Solved
+struct APT::Solver::Solver::Trail
 {
-   // \brief A variable that has been assigned. We store this as a reason (FIXME: Rename Var to Var)
+   /// \brief A variable that got assigned True or False. May be reset to Undefined on backtracking.
    Var assigned;
-   // \brief A work item that has been solved. This needs to be put back on the queue.
+   /// \brief A work item (a clause) that was solved. Needs to be put back on the work heap on backtracking.
    std::optional<Work> work;
 };
 
-inline APT::Solver::State &APT::Solver::operator[](Var r)
+inline APT::Solver::Solver::State &APT::Solver::Solver::operator[](APT::Solver::Var r)
 {
    if (auto P = r.Pkg())
       return (*this)[cache.PkgP + P];
@@ -523,7 +589,7 @@ inline APT::Solver::State &APT::Solver::operator[](Var r)
    return *rootState.get();
 }
 
-inline const APT::Solver::State &APT::Solver::operator[](Var r) const
+inline const APT::Solver::Solver::State &APT::Solver::Solver::operator[](APT::Solver::Var r) const
 {
    return const_cast<Solver &>(*this)[r];
 }
@@ -535,3 +601,11 @@ 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); }
 };
+
+// Custom specialization of std::hash can be injected in namespace std.
+template <>
+struct std::hash<APT::Solver::Lit>
+{
+   std::hash<decltype(APT::Solver::Lit::value)> hash_value;
+   std::size_t operator()(const APT::Solver::Lit &v) const noexcept { return hash_value(v.value); }
+};
diff --git a/cmdline/apt.cc b/cmdline/apt.cc
index 9acde0b32..4a0708db8 100644
--- a/cmdline/apt.cc
+++ b/cmdline/apt.cc
@@ -66,7 +66,7 @@ static bool DoWhy(CommandLine &CmdL) /*{{{*/
    if (unlikely(not CacheFile.BuildDepCache()))
       return false;
    for (auto pkg : pkgset)
-      std::cout << APT::Solver::InternalCliWhy(CacheFile, pkg, decision) << std::flush;
+      std::cout << APT::Solver::DependencySolver::InternalCliWhy(CacheFile, pkg, decision) << std::flush;
    return not _error->PendingError();
 }
 static std::vector<aptDispatchWithHelp> GetCommands()			/*{{{*/
diff --git a/debian/libapt-pkg7.0.symbols b/debian/libapt-pkg7.0.symbols
index cb857b159..d29826e5a 100644
--- a/debian/libapt-pkg7.0.symbols
+++ b/debian/libapt-pkg7.0.symbols
@@ -1320,7 +1320,7 @@ libapt-pkg.so.7.0 libapt-pkg7.0 #MINVER#
  (arch=ppc64el|c++)"GlobalError::InsertErrno(GlobalError::MsgType, char const*, char const*, char*&, int, unsigned long&)@APTPKG_7.0" 0.8.11.4
  (arch=armel armhf|c++)"RFC1123StrToTime(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&, long long&)@APTPKG_7.0" 1.9.0
  (arch=armel armhf|c++)"TimeRFC1123[abi:cxx11](long long, bool)@APTPKG_7.0" 2.7.14
- (c++)"APT::Solver::InternalCliWhy[abi:cxx11](pkgDepCache&, pkgCache::PkgIterator, bool)@APTPKG_7.0" 3.1.0~
+ (c++)"APT::Solver::Solver::InternalCliWhy[abi:cxx11](pkgDepCache&, pkgCache::PkgIterator, bool)@APTPKG_7.0" 3.1.0~
 # Optional C++ standard library symbols
 # These are inlined libstdc++ symbols and not supposed to be part of our ABI
 # but we cannot stop stuff from linking against it, sigh.
diff --git a/test/integration/test-apt-get-build-dep-barbarian b/test/integration/test-apt-get-build-dep-barbarian
index 8763e8fc7..e30390331 100755
--- a/test/integration/test-apt-get-build-dep-barbarian
+++ b/test/integration/test-apt-get-build-dep-barbarian
@@ -83,7 +83,7 @@ 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: Unable to satisfy dependencies. Reached two conflicting decisions:
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting assignments:
    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:
@@ -105,7 +105,7 @@ 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: Unable to satisfy dependencies. Reached two conflicting decisions:
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting assignments:
    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:
@@ -133,7 +133,7 @@ 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: Unable to satisfy dependencies. Reached two conflicting decisions:
+FAILUREMSG="E: Unable to satisfy dependencies. Reached two conflicting assignments:
    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:
diff --git a/test/integration/test-apt-get-build-dep-file b/test/integration/test-apt-get-build-dep-file
index fd48aef47..71da4d1dd 100755
--- a/test/integration/test-apt-get-build-dep-file
+++ b/test/integration/test-apt-get-build-dep-file
@@ -160,7 +160,7 @@ 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: Unable to satisfy dependencies. Reached two conflicting decisions:
+E: Unable to satisfy dependencies. Reached two conflicting assignments:
    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:
diff --git a/test/integration/test-apt-get-install-deb b/test/integration/test-apt-get-install-deb
index 07de975c4..cb423cd59 100755
--- a/test/integration/test-apt-get-install-deb
+++ b/test/integration/test-apt-get-install-deb
@@ -32,7 +32,7 @@ done
 
 buildsimplenativepackage 'foo' 'i386,amd64' '1.0'
 
-testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting assignments:
    1. foo:amd64 is not selected for install because:
       1. foo:i386=1.0 is selected for install
       2. foo:amd64 Conflicts foo:i386
@@ -181,7 +181,7 @@ echo 'Package: /pkg-/
 Pin: release a=experimental
 Pin-Priority: 501' > rootdir/etc/apt/preferences.d/pinit
 
-testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting assignments:
    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:
diff --git a/test/integration/test-apt-get-satisfy b/test/integration/test-apt-get-satisfy
index 8d57a98a8..3d215ff86 100755
--- a/test/integration/test-apt-get-satisfy
+++ b/test/integration/test-apt-get-satisfy
@@ -80,7 +80,7 @@ testrun 'External' 'Reading package lists...
 Building dependency tree...
 Execute external solver...' --solver apt
 
-testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting assignments:
    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:
diff --git a/test/integration/test-apt-get-source-only b/test/integration/test-apt-get-source-only
index 91a157b47..052aac9b6 100755
--- a/test/integration/test-apt-get-source-only
+++ b/test/integration/test-apt-get-source-only
@@ -40,7 +40,7 @@ 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: Unable to satisfy dependencies. Reached two conflicting decisions:
+E: Unable to satisfy dependencies. Reached two conflicting assignments:
    1. builddeps:foo:amd64=1 is selected for install
    2. builddeps:foo:amd64 Depends foo-bd
       but none of the choices are installable:
@@ -56,7 +56,7 @@ 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: Unable to satisfy dependencies. Reached two conflicting decisions:
+E: Unable to satisfy dependencies. Reached two conflicting assignments:
    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:
diff --git a/test/integration/test-apt-install-file-reltag b/test/integration/test-apt-install-file-reltag
index 053c785fd..1b113b82f 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,|Unable to satisfy dependencies. Reached two conflicting decisions)" "${TMPWORKINGDIRECTORY}/rootdir/tmp/testfailure.output"
+    testsuccess grep -E "^E: (Unable to correct problems,|Unable to satisfy dependencies. Reached two conflicting assignments)" "${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 14ce3ae5a..ea80f8b70 100755
--- a/test/integration/test-apt-never-markauto-sections
+++ b/test/integration/test-apt-never-markauto-sections
@@ -49,7 +49,7 @@ Remv foreignpkg:i386 [1]
 Remv nosection [1]
 Remv texteditor [1]' aptget autoremove mydesktop -s
 
-testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting assignments:
    1. bad-texteditor:amd64 is selected for install because:
       1. mydesktop:amd64 is selected for install
       2. mydesktop:amd64 Depends mydesktop-core
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 a87481302..b4ad0f447 100755
--- a/test/integration/test-bug-598669-install-postfix-gets-exim-heavy
+++ b/test/integration/test-bug-598669-install-postfix-gets-exim-heavy
@@ -8,7 +8,7 @@ configarchitecture "i386"
 setupaptarchive
 
 # FIXME: Should this say selected postifx?
-testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting assignments:
    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
diff --git a/test/integration/test-bug-601961-install-info b/test/integration/test-bug-601961-install-info
index be55e76a7..712a9ba14 100755
--- a/test/integration/test-bug-601961-install-info
+++ b/test/integration/test-bug-601961-install-info
@@ -60,7 +60,7 @@ 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: Unable to satisfy dependencies. Reached two conflicting decisions:
+E: Unable to satisfy dependencies. Reached two conflicting assignments:
    1. essentialpkg:i386 is selected for removal
    2. essentialpkg:i386 is selected for install because:
       1. findutils:i386 is selected for install
diff --git a/test/integration/test-bug-612557-garbage-upgrade b/test/integration/test-bug-612557-garbage-upgrade
index ced55a5bf..9bc83cce4 100755
--- a/test/integration/test-bug-612557-garbage-upgrade
+++ b/test/integration/test-bug-612557-garbage-upgrade
@@ -18,7 +18,7 @@ testsuccess aptmark markauto python-uno openoffice.org-common
 testmarkedauto python-uno openoffice.org-common
 
 # The 3.0 solver does not remove openoffice.org-emailmerge because it is manually installed.
-testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting assignments:
    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
diff --git a/test/integration/test-bug-618848-always-respect-user-requests b/test/integration/test-bug-618848-always-respect-user-requests
index 6dd77af58..d59e458ce 100755
--- a/test/integration/test-bug-618848-always-respect-user-requests
+++ b/test/integration/test-bug-618848-always-respect-user-requests
@@ -14,7 +14,7 @@ insertpackage 'unstable' 'exim4-daemon-heavy' 'all' '1.0' 'Depends: libdb4.8'
 setupaptarchive
 
 # This does not work in 3.0 solver: We do not remove manually installed packages.
-testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting assignments:
    1. exim4-daemon-light:i386 is selected for install
    2. exim4-daemon-light:i386 Depends libdb4.8
       but none of the choices are installable:
diff --git a/test/integration/test-bug-632221-cross-dependency-satisfaction b/test/integration/test-bug-632221-cross-dependency-satisfaction
index 6e39b384c..903133cc7 100755
--- a/test/integration/test-bug-632221-cross-dependency-satisfaction
+++ b/test/integration/test-bug-632221-cross-dependency-satisfaction
@@ -35,7 +35,7 @@ insertsource 'unstable' 'source-specific-armel' 'armel' '1' 'Build-Depends: spec
 
 setupaptarchive
 
-testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting assignments:
    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:
@@ -53,7 +53,7 @@ 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: Unable to satisfy dependencies. Reached two conflicting decisions:
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting assignments:
    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:
@@ -71,7 +71,7 @@ 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: Unable to satisfy dependencies. Reached two conflicting decisions:
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting assignments:
    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:
diff --git a/test/integration/test-bug-675449-essential-are-protected b/test/integration/test-bug-675449-essential-are-protected
index c8e832d72..d7e284ece 100755
--- a/test/integration/test-bug-675449-essential-are-protected
+++ b/test/integration/test-bug-675449-essential-are-protected
@@ -125,7 +125,7 @@ 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: Unable to satisfy dependencies. Reached two conflicting decisions:
+E: Unable to satisfy dependencies. Reached two conflicting assignments:
    1. libfoo:amd64 is selected for removal
    2. libfoo:amd64 is selected for install because:
       1. foo:amd64 is selected for install
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 a682a2f1a..42d4162aa 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,7 @@ 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: Unable to satisfy dependencies. Reached two conflicting decisions:
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting assignments:
    1. builddeps:dash:armel=1 is selected for install
    2. builddeps:dash:armel Depends po-debconf:armel
       but none of the choices are installable:
@@ -59,7 +59,7 @@ 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: Unable to satisfy dependencies. Reached two conflicting decisions:
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting assignments:
    1. builddeps:diffutils:armel=1 is selected for install
    2. builddeps:diffutils:armel Depends texi2html:armel
       but none of the choices are installable:
@@ -86,7 +86,7 @@ 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: Unable to satisfy dependencies. Reached two conflicting decisions:
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting assignments:
    1. builddeps:sed:armel=1 is selected for install
    2. builddeps:sed:armel Depends libselinux-dev:armel
       but none of the choices are installable:
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 191d75647..20116a653 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,7 @@ 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: Unable to satisfy dependencies. Reached two conflicting decisions:
+E: Unable to satisfy dependencies. Reached two conflicting assignments:
    1. python-mips:amd64=3 is selected for install
    2. python-mips:amd64 Depends python3:mips
       but none of the choices are installable:
diff --git a/test/integration/test-bug-735967-lib32-to-i386-unavailable b/test/integration/test-bug-735967-lib32-to-i386-unavailable
index 83992e386..bd3172d68 100755
--- a/test/integration/test-bug-735967-lib32-to-i386-unavailable
+++ b/test/integration/test-bug-735967-lib32-to-i386-unavailable
@@ -50,7 +50,7 @@ Remv lib32nss-mdns [0.9-1]
 Inst libnss-mdns [0.9-1] (0.10-6 unstable [amd64])
 Conf libnss-mdns (0.10-6 unstable [amd64])' aptget dist-upgrade -s --solver internal
 
-testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting assignments:
    1. libfoo:amd64 is selected for install because:
       1. foo:amd64=1 is selected for install
       2. foo:amd64 Depends libfoo
diff --git a/test/integration/test-bug-745046-candidate-propagation-fails b/test/integration/test-bug-745046-candidate-propagation-fails
index f4fc15e0e..3c02f55a6 100755
--- a/test/integration/test-bug-745046-candidate-propagation-fails
+++ b/test/integration/test-bug-745046-candidate-propagation-fails
@@ -40,7 +40,7 @@ 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: Unable to satisfy dependencies. Reached two conflicting decisions:
+E: Unable to satisfy dependencies. Reached two conflicting assignments:
    1. gedit:amd64=2 is selected as an upgrade
    2. gedit:amd64=2 Depends common (>= 2)
       but none of the choices are installable:
diff --git a/test/integration/test-bug-961266-hold-means-hold b/test/integration/test-bug-961266-hold-means-hold
index 08c74e052..e95bb6ed6 100755
--- a/test/integration/test-bug-961266-hold-means-hold
+++ b/test/integration/test-bug-961266-hold-means-hold
@@ -89,7 +89,7 @@ The following information may help to resolve the situation:
 
 The following packages have unmet dependencies:
  git-ng : Depends: git (> 1:2.26.2)
-E: Unable to satisfy dependencies. Reached two conflicting decisions:
+E: Unable to satisfy dependencies. Reached two conflicting assignments:
    1. git-ng:amd64=1:2.26.2-1 is selected for install
    2. git-ng:amd64 Depends git (> 1:2.26.2) and Depends git (< 1:2.26.2-.)
       but none of the choices are installable:
@@ -135,7 +135,7 @@ The following information may help to resolve the situation:
 
 The following packages have unmet dependencies:
  git-ng : Depends: git (> 1:2.26.2)
-E: Unable to satisfy dependencies. Reached two conflicting decisions:
+E: Unable to satisfy dependencies. Reached two conflicting assignments:
    1. git-ng:amd64=1:2.26.2-1 is selected for install
    2. git-ng:amd64 Depends git (> 1:2.26.2) and Depends git (< 1:2.26.2-.)
       but none of the choices are installable:
@@ -181,7 +181,7 @@ The following information may help to resolve the situation:
 
 The following packages have unmet dependencies:
  git-ng : Depends: git (> 1:2.26.2)
-E: Unable to satisfy dependencies. Reached two conflicting decisions:
+E: Unable to satisfy dependencies. Reached two conflicting assignments:
    1. git-ng:amd64=1:2.26.2-1 is selected for install
    2. git-ng:amd64 Depends git (> 1:2.26.2) and Depends git (< 1:2.26.2-.)
       but none of the choices are installable:
diff --git a/test/integration/test-explore-or-groups-in-markinstall b/test/integration/test-explore-or-groups-in-markinstall
index 77f769e77..1b5cc2823 100755
--- a/test/integration/test-explore-or-groups-in-markinstall
+++ b/test/integration/test-explore-or-groups-in-markinstall
@@ -161,7 +161,7 @@ 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: Unable to satisfy dependencies. Reached two conflicting decisions:
+E: Unable to satisfy dependencies. Reached two conflicting assignments:
    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)
@@ -177,7 +177,7 @@ 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: Unable to satisfy dependencies. Reached two conflicting decisions:
+E: Unable to satisfy dependencies. Reached two conflicting assignments:
    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
diff --git a/test/integration/test-handling-broken-orgroups b/test/integration/test-handling-broken-orgroups
index 5c882b516..184c84377 100755
--- a/test/integration/test-handling-broken-orgroups
+++ b/test/integration/test-handling-broken-orgroups
@@ -47,7 +47,7 @@ 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: Unable to satisfy dependencies. Reached two conflicting decisions:
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting assignments:
    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:
@@ -99,7 +99,7 @@ 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: Unable to satisfy dependencies. Reached two conflicting decisions:
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting assignments:
    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
diff --git a/test/integration/test-ignore-provides-if-versioned-breaks b/test/integration/test-ignore-provides-if-versioned-breaks
index 87e609bef..a7a7d88ed 100755
--- a/test/integration/test-ignore-provides-if-versioned-breaks
+++ b/test/integration/test-ignore-provides-if-versioned-breaks
@@ -32,7 +32,7 @@ insertpackage 'unstable' 'foo-same-breaker-none' 'i386' '1.0' 'Breaks: foo-same'
 
 
 setupaptarchive
-testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting assignments:
    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
@@ -76,7 +76,7 @@ Conf foo (4.0 unstable [i386])
 Conf foo-breaker-3 (1.0 unstable [i386])
 Conf foo-provider (1.0 unstable [i386])' aptget install foo-provider foo-breaker-3 -s
 
-testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting assignments:
    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
@@ -120,7 +120,7 @@ Conf foo-foreign:amd64 (4.0 unstable [amd64])
 Conf foo-foreign-breaker-3 (1.0 unstable [i386])
 Conf foo-foreign-provider (1.0 unstable [i386])' aptget install foo-foreign-provider foo-foreign-breaker-3 -s
 
-testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting assignments:
    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
diff --git a/test/integration/test-ignore-provides-if-versioned-conflicts b/test/integration/test-ignore-provides-if-versioned-conflicts
index cdf69656e..517436d57 100755
--- a/test/integration/test-ignore-provides-if-versioned-conflicts
+++ b/test/integration/test-ignore-provides-if-versioned-conflicts
@@ -33,7 +33,7 @@ insertpackage 'unstable' 'foo-same-breaker-none' 'i386' '1.0' 'Conflicts: foo-sa
 
 setupaptarchive
 
-testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting assignments:
    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
@@ -77,7 +77,7 @@ Conf foo (4.0 unstable [i386])
 Conf foo-breaker-3 (1.0 unstable [i386])
 Conf foo-provider (1.0 unstable [i386])' aptget install foo-provider foo-breaker-3 -s
 
-testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting assignments:
    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
@@ -121,7 +121,7 @@ Conf foo-foreign:amd64 (4.0 unstable [amd64])
 Conf foo-foreign-breaker-3 (1.0 unstable [i386])
 Conf foo-foreign-provider (1.0 unstable [i386])' aptget install foo-foreign-provider foo-foreign-breaker-3 -s
 
-testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting assignments:
    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
diff --git a/test/integration/test-multiarch-allowed b/test/integration/test-multiarch-allowed
index 8c244ed57..c40de6cc8 100755
--- a/test/integration/test-multiarch-allowed
+++ b/test/integration/test-multiarch-allowed
@@ -64,7 +64,7 @@ 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: Unable to satisfy dependencies. Reached two conflicting decisions:
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting assignments:
    1. needsfoo:i386=1 is selected for install
    2. needsfoo:i386 Depends foo:i386
       but none of the choices are installable:
@@ -76,7 +76,7 @@ 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: Unable to satisfy dependencies. Reached two conflicting decisions:
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting assignments:
    1. needsfoo:i386=1 is selected for install
    2. needsfoo:i386 Depends foo:i386
       but none of the choices are installable:
@@ -87,7 +87,7 @@ 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: Unable to satisfy dependencies. Reached two conflicting decisions:
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting assignments:
    1. needsfoo:amd64=1 is selected for install
    2. needsfoo:amd64 Depends foo
       but none of the choices are installable:
@@ -153,7 +153,7 @@ if [ "$APT_SOLVER" != "internal" ]; then
 NEEDSFOO2NATIVE="$BADPREFIX
 The following packages have unmet dependencies:
  needsfoover2 : Depends: foo:any (>= 2)
-E: Unable to satisfy dependencies. Reached two conflicting decisions:
+E: Unable to satisfy dependencies. Reached two conflicting assignments:
    1. needsfoover2:amd64=1 is selected for install
    2. needsfoover2:amd64 Depends foo:any (>= 2)
       but none of the choices are installable:
@@ -161,7 +161,7 @@ E: Unable to satisfy dependencies. Reached two conflicting decisions:
 NEEDSFOO2FOREIGN="$BADPREFIX
 The following packages have unmet dependencies:
  needsfoover2:i386 : Depends: foo:any (>= 2)
-E: Unable to satisfy dependencies. Reached two conflicting decisions:
+E: Unable to satisfy dependencies. Reached two conflicting assignments:
    1. needsfoover2:i386=1 is selected for install
    2. needsfoover2:i386 Depends foo:any (>= 2)
       but none of the choices are installable:
@@ -182,27 +182,27 @@ testfailureequal "$NEEDSFOO2FOREIGN" aptget install needsfoover2:i386 foo:i386 -
 testfailureequal "$NEEDSFOO2NATIVE" aptget install needsfoover2 foo:i386 -s
 
 solveableinsinglearch2() {
-	testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+	testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting assignments:
    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:
+		testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting assignments:
    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:
+		testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting assignments:
    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:
+	testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting assignments:
    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
@@ -219,7 +219,7 @@ 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: Unable to satisfy dependencies. Reached two conflicting decisions:
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting assignments:
    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
@@ -228,7 +228,7 @@ 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: Unable to satisfy dependencies. Reached two conflicting decisions:
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting assignments:
    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
@@ -248,7 +248,7 @@ Inst hatesfoonative (1 unstable [amd64])
 Conf foo:i386 (1 unstable [i386])
 Conf hatesfoonative (1 unstable [amd64])' aptget install foo:i386 hatesfoonative -s
 
-testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting assignments:
    1. needscoolfoo:i386=1 is selected for install
    2. needscoolfoo:i386 Depends coolfoo:i386
       but none of the choices are installable:
@@ -325,7 +325,7 @@ 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: Unable to satisfy dependencies. Reached two conflicting decisions:
+	testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting assignments:
    1. needscoolfoover2:amd64=1 is selected for install
    2. needscoolfoover2:amd64 Depends coolfoo:any (>= 2)
       but none of the choices are installable:
@@ -334,7 +334,7 @@ Conf needscoolfoover1 (1 unstable [amd64])' aptget install needscoolfoover1 -s
 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: Unable to satisfy dependencies. Reached two conflicting decisions:
+	testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting assignments:
    1. needscoolfoover3:amd64=1 is selected for install
    2. needscoolfoover3:amd64 Depends coolfoo:any (>= 2)
       but none of the choices are installable:
diff --git a/test/integration/test-multiarch-foreign b/test/integration/test-multiarch-foreign
index a04b854a5..e71c1ae5a 100755
--- a/test/integration/test-multiarch-foreign
+++ b/test/integration/test-multiarch-foreign
@@ -179,7 +179,7 @@ distribution that some required packages have not yet been created
 or been moved out of Incoming.
 The following information may help to resolve the situation:
 '
-	testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+	testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting assignments:
    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
@@ -191,7 +191,7 @@ The following packages have unmet dependencies:
              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: Unable to satisfy dependencies. Reached two conflicting decisions:
+	testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting assignments:
    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
diff --git a/test/integration/test-prefer-higher-priority-providers b/test/integration/test-prefer-higher-priority-providers
index 87954c5d4..07a0033b1 100755
--- a/test/integration/test-prefer-higher-priority-providers
+++ b/test/integration/test-prefer-higher-priority-providers
@@ -91,7 +91,7 @@ Inst awesome (1 unstable [all])
 Conf baz (1 unstable [all])
 Conf awesome (1 unstable [all])" aptget install awesome foo- bar- -s
 
-testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting assignments:
    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
diff --git a/test/integration/test-release-candidate-switching b/test/integration/test-release-candidate-switching
index 18396252f..16eb4f1ec 100755
--- a/test/integration/test-release-candidate-switching
+++ b/test/integration/test-release-candidate-switching
@@ -448,7 +448,7 @@ 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: Unable to satisfy dependencies. Reached two conflicting decisions:
+E: Unable to satisfy dependencies. Reached two conflicting assignments:
    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
diff --git a/test/integration/test-solver3-alternatives b/test/integration/test-solver3-alternatives
index 8a3645f82..45b4395cd 100755
--- a/test/integration/test-solver3-alternatives
+++ b/test/integration/test-solver3-alternatives
@@ -15,7 +15,7 @@ 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:
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting assignments:
    1. bb:amd64 is selected for install because:
       1. unsat:amd64=3 is selected for install
       2. unsat:amd64 Depends a | b
diff --git a/test/integration/test-solver3-evaluation b/test/integration/test-solver3-evaluation
index f5a10f5fa..06edb4962 100755
--- a/test/integration/test-solver3-evaluation
+++ b/test/integration/test-solver3-evaluation
@@ -142,7 +142,7 @@ The following packages have unmet dependencies:
  a : Depends: c but it is not going to be installed
 E: Unable to correct problems, you have held broken packages.
 E: The following information from --solver 3.0 may provide additional context:
-   Unable to satisfy dependencies. Reached two conflicting decisions:
+   Unable to satisfy dependencies. Reached two conflicting assignments:
    1. a:amd64=3 is selected for install
    2. a:amd64 Depends c
       but none of the choices are installable:
@@ -176,7 +176,7 @@ Package: apt
 Title: Failure: The 3.0 solver did not find a result
 SourcePackage: apt
 ErrorMessage:
- Unable to satisfy dependencies. Reached two conflicting decisions:
+ Unable to satisfy dependencies. Reached two conflicting assignments:
  1. a:amd64=3 is selected for install
  .
  2. a:amd64 Depends c
diff --git a/test/integration/test-solver3-show-version-selection b/test/integration/test-solver3-show-version-selection
index 0de6600af..e0453feed 100755
--- a/test/integration/test-solver3-show-version-selection
+++ b/test/integration/test-solver3-show-version-selection
@@ -14,7 +14,7 @@ insertpackage 'installed,unstable' 'libgcc-s1' 'amd64' '14.2.0-18' 'Multi-Arch:
 
 setupaptarchive
 
-testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting assignments:
    1. libc6:s390x is selected for install because:
       1. sbuild-build-depends-main-dummy:s390x=0.invalid.0 is selected for install
       2. sbuild-build-depends-main-dummy:s390x Depends libgstreamer1.0-dev:s390x
@@ -26,7 +26,7 @@ testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decis
         2. libgcc-s1:amd64 is available in version 14.2.0-18
         3. libgcc-s1:s390x Breaks libgcc-s1 (!= 14.2.0-17)" apt install sbuild-build-depends-main-dummy --solver 3.0 libgcc-s1 -s
 
-testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting assignments:
    1. libc6:s390x is selected for install because:
       1. sbuild-build-depends-main-dummy:s390x=0.invalid.0 is selected for install
       2. sbuild-build-depends-main-dummy:s390x Depends libgstreamer1.0-dev:s390x
diff --git a/test/integration/test-specific-architecture-dependencies b/test/integration/test-specific-architecture-dependencies
index b9ce155de..3ffa3669c 100755
--- a/test/integration/test-specific-architecture-dependencies
+++ b/test/integration/test-specific-architecture-dependencies
@@ -194,7 +194,7 @@ 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: Unable to satisfy dependencies. Reached two conflicting decisions:
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting assignments:
    1. foo-depender:i386=1 is selected for install
    2. foo-depender:i386 Depends foo:i386
       but none of the choices are installable:
@@ -317,7 +317,7 @@ Remv libold [1]
 Inst breaker-x64 (1 unstable [amd64])
 Conf breaker-x64 (1 unstable [amd64])' aptget install breaker-x64:amd64 -s
 
-testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting assignments:
    1. depender-x32:amd64=1 is selected for install
    2. depender-x32:amd64 Depends libc6:i386
       but none of the choices are installable:
diff --git a/test/integration/test-ubuntu-bug-2111792-intersecting-dependencies b/test/integration/test-ubuntu-bug-2111792-intersecting-dependencies
index 4d32c0130..7e770a30d 100755
--- a/test/integration/test-ubuntu-bug-2111792-intersecting-dependencies
+++ b/test/integration/test-ubuntu-bug-2111792-intersecting-dependencies
@@ -96,7 +96,7 @@ The following information may help to resolve the situation:
 
 The following packages have unmet dependencies:
  git-ng : Depends: git (> 1:2.26.2)
-E: Unable to satisfy dependencies. Reached two conflicting decisions:
+E: Unable to satisfy dependencies. Reached two conflicting assignments:
    1. git-ng:amd64=1:2.26.2-1 is selected for install
    2. git-ng:amd64 Depends git (> 1:2.26.2) and Depends git (< 1:2.26.2-.)
       but none of the choices are installable:
@@ -129,7 +129,7 @@ The following information may help to resolve the situation:
 
 The following packages have unmet dependencies:
  git-ng : Depends: git (> 1:2.26.2)
-E: Unable to satisfy dependencies. Reached two conflicting decisions:
+E: Unable to satisfy dependencies. Reached two conflicting assignments:
    1. git-ng:amd64=1:2.26.2-1 is selected for install
    2. git-ng:amd64 Depends git (> 1:2.26.2) and Depends git (< 1:2.26.2-.)
       but none of the choices are installable:
@@ -163,7 +163,7 @@ The following information may help to resolve the situation:
 
 The following packages have unmet dependencies:
  git-ng : Depends: git (> 1:2.26.2)
-E: Unable to satisfy dependencies. Reached two conflicting decisions:
+E: Unable to satisfy dependencies. Reached two conflicting assignments:
    1. git-ng:amd64=1:2.26.2-1 is selected for install
    2. git-ng:amd64 Depends git (> 1:2.26.2) and Depends git (< 1:2.26.2-.)
       but none of the choices are installable: