Initial implementation of the 3.0 solver

This is a simple backtracking brute-force solver with heurisitcs,
this initial version has the following known gaps:

- Errors are not kept from branches, the error reporting after
  backtracking isn't particularly useful.
- We cannot show automatically removed packages
- We cannot replace packages with others
- We do not have conflict-driven clause learning yet

Untested:

- Multi-arch

This solver is fundamentally different in key aspects:

- It solves smaller dependency groups before larger ones, leading
  us to avoid installing A in A|B if B is installed more often and
  more consistently.

- It only keeps the automatic packages reachable via the strongest
  path. Currently it only implements autoremoval, but not display
  of autoremoval as we simply enqueue all automatically installed
  packages at the end when not doing automatic removal.

  This will need some translation where we Solve() first, and then
  Solve() again with the automatically installed packages added such
  that we can mark them as Garbage for display purposes.

- It does not remove manually installed packages.

Hook the solver in via the EDSP framework, this allows us to achieve
easy initial integration without lots of issues.

A lot of this work was planned and executed in my free time and then
some leaked into work time I suppose.

Implementation notes:

- Restore the full backlog of items

  The annoying thing is that we record only when an item was enqueued
  and not the level at which it was installed, so when going back a
  decision level we might have to reinstall packages that were queued
  at an earlier decision level because they were only installed at a
  later decision level.

- When picking one version, reject the others

- Propagate conflicts up to reverse dependencies

  This will recursively mark every reverse dependency that can
  no longer be satisfied as MUSTNOT.

  Also make sure to recursively call Reject(Ver) from Reject(Pkg)
  to make sure we trigger the Rejections there.

  This means we now end up having Recursion in the algorithm. An
  alternative approach would be to push *reject* items to the heap
  and then do them, but this is not entirely straight forward and
  it may simply not be necessary.

-  Sort upgrades before other optional installs containing subsets

  If I want to upgrade a package A, I schedule A3|A2|A1; if another
  thing depends specifically on A1; we'd not be installed. Hence we
  need to sort upgrades first.

  This only is needed for optional packages; manual packages will
  figure this out naturally.

- Rescoring is lazily implemented. Instead of calling make_heap()
  after rescoring items, we just mark the items as dirty and reinsert
  them. We also only rescore from the main solve loop, Reject() marks
  the heap as needing a rescore due to a Conflict (as some versions will
  no longer be installable), and RescoreWorkIfNeeded() then will do the
  rescoring.

- Recursive unit propagation: Install() and Reject() recursively call
  each other to promote decisions across single-version dependencies
  (or across not-anymore satisfiable reverse-depends).

- Make Reason constructors explicit, this enhances readability

  This makes calls like the one in here be

    Reject(object, Reason(otherObject))

  Ensuring that it's clear that the 2nd argument is a reason at the
  caller side.

- Split Decision into Decision and Hint vs. first draft

  When branching/deciding, we do not want to override SHOULD and MAY.
  We do not actually use them yet, and we do actually clean them when
  backtracking, but let's at least keep the data structure correct.

  Convert the enum to a 16-bit integer so we can still fit in the same
  space as before.

4 files changed, 1264 insertions, 0 deletions

diff --git a/apt-pkg/edsp.cc b/apt-pkg/edsp.cc
index a02e400c2..589400870 100644
--- a/apt-pkg/edsp.cc
+++ b/apt-pkg/edsp.cc
@@ -19,6 +19,7 @@
 #include <apt-pkg/pkgsystem.h>
 #include <apt-pkg/prettyprinters.h>
 #include <apt-pkg/progress.h>
+#include <apt-pkg/solver3.h>
 #include <apt-pkg/string_view.h>
 #include <apt-pkg/strutl.h>
 #include <apt-pkg/tagfile.h>
@@ -765,6 +766,18 @@ static bool CreateDumpFile(char const * const id, char const * const type, FileF
 // EDSP::ResolveExternal - resolve problems by asking external for help	{{{*/
 bool EDSP::ResolveExternal(const char* const solver, pkgDepCache &Cache,
 			 unsigned int const flags, OpProgress *Progress) {
+   if (strcmp(solver, "3.0") == 0)
+   {
+      APT::Solver s(Cache.GetCache(), Cache.GetPolicy());
+      FileFd output;
+      if (not s.FromDepCache(Cache))
+	 return false;
+      if (not s.Solve())
+	 return false;
+      if (not s.ToDepCache(Cache))
+	 return false;
+      return true;
+   }
 	if (strcmp(solver, "internal") == 0)
 	{
 		FileFd output;
diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc
new file mode 100644
index 000000000..d43bd5b33
--- /dev/null
+++ b/apt-pkg/solver3.cc
@@ -0,0 +1,960 @@
+/*
+ * solver3.cc - The APT 3.0 solver
+ *
+ * Copyright (c) 2023 Julian Andres Klode
+ * Copyright (c) 2023 Canonical Ltd
+ *
+ * SPDX-License-Identifier: GPL-2.0+
+ */
+
+#define APT_COMPILING_APT
+
+#include <config.h>
+
+#include <apt-pkg/algorithms.h>
+#include <apt-pkg/aptconfiguration.h>
+#include <apt-pkg/cachefilter.h>
+#include <apt-pkg/cacheset.h>
+#include <apt-pkg/error.h>
+#include <apt-pkg/macros.h>
+#include <apt-pkg/pkgsystem.h>
+#include <apt-pkg/solver3.h>
+#include <apt-pkg/version.h>
+
+#include <algorithm>
+#include <cassert>
+#include <sstream>
+
+// FIXME: Helpers stolen from DepCache, please give them back.
+struct CompareProviders3 /*{{{*/
+{
+   pkgCache &Cache;
+   pkgDepCache::Policy &Policy;
+   pkgCache::PkgIterator const Pkg;
+   bool upgrade{_config->FindB("APT::Solver::Upgrade", false)};
+
+   bool operator()(pkgCache::Version *AV, pkgCache::Version *BV)
+   {
+      return (*this)(pkgCache::VerIterator(Cache, AV), pkgCache::VerIterator(Cache, BV));
+   }
+   bool operator()(pkgCache::VerIterator const &AV, pkgCache::VerIterator const &BV)
+   {
+      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;
+	 if (not upgrade && A->CurrentVer != 0 && A.CurrentVer() == AV)
+	    return true;
+	 if (Policy.GetPriority(AV) < Policy.GetPriority(BV))
+	    return false;
+
+	 return _system->VS->CmpVersion(AV.VerStr(), BV.VerStr()) > 0;
+      }
+      // 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)
+      {
+	 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)){};
+   virtual ~DefaultRootSetFunc2(){};
+
+   bool InRootSet(const pkgCache::PkgIterator &pkg) APT_OVERRIDE { return pkg.end() == false && ((*Kernels)(pkg) || DefaultRootSetFunc::InRootSet(pkg)); };
+}; // FIXME: DEDUP with pkgDepCache.
+/*}}}*/
+
+APT::Solver::Solver(pkgCache &cache, pkgDepCache::Policy &policy)
+    : cache(cache),
+      policy(policy),
+      pkgStates{cache.Head().PackageCount},
+      verStates{cache.Head().VersionCount}
+{
+   static_assert(sizeof(APT::Solver::State<pkgCache::PkgIterator>) == 3 * sizeof(int));
+   static_assert(sizeof(APT::Solver::State<pkgCache::VerIterator>) == 3 * sizeof(int));
+   static_assert(sizeof(APT::Solver::Reason) == sizeof(map_pointer<pkgCache::Package>));
+   static_assert(sizeof(APT::Solver::Reason) == sizeof(map_pointer<pkgCache::Version>));
+}
+
+// This function determines if a work item is less important than another.
+bool APT::Solver::Work::operator<(APT::Solver::Work const &b) const
+{
+   if (optional && b.optional && reason.empty() && b.reason.empty() && upgrade != b.upgrade)
+   {
+      // Assuming we have libfoo-dev=5.1 Depends libfoo5.1-dev upgrade to libfoo-dev=5.3 Depends libfoo5.3-dev,
+      // We schedule libfoo-dev=5.3|libfoo-dev=5.1, libfoo5.1-dev. The latter would be resolved first, resulting
+      // in libfoo-dev being kept back.
+      //
+      // However, if we schedule not libfoo5.1-dev but bar Recommends libfoo5.1-dev, we should not be breaking that
+      // Recommends, hence we need to ensure that if we order an upgrade before an optional package that this optional
+      // package was a top level package, i.e. b.reason is empty (or our reason in the reverse case).
+      //
+      // So if we are the upgrade, and b also Depends on one of our versions, we need to satisfy b after we
+      // have scheduled the upgrade.
+      if (upgrade)
+	 return std::any_of(b.solutions.begin(), b.solutions.end(), [this](auto bsol) -> bool
+			    { return std::find(solutions.begin(), solutions.end(), bsol) != solutions.end(); });
+      else
+	 return std::any_of(solutions.begin(), solutions.end(), [b](auto sol) -> bool
+			    { return std::find(b.solutions.begin(), b.solutions.end(), sol) != b.solutions.end(); });
+   }
+   // An optional item is less important than a required one.
+   if (optional != b.optional)
+      return optional;
+   // More solutions to explore are more expensive.
+   if (size != b.size)
+      return size > b.size;
+   // We enqueue common dependencies at the package level to avoid choosing versions, so let's solve package items first,
+   // this improves the implication graph as it now tells you that common dependencies were installed by the package.
+   if (reason.Pkg() != b.reason.Pkg())
+      return reason.Pkg() == 0;
+
+   return false;
+}
+
+void APT::Solver::Work::Dump(pkgCache &cache)
+{
+   if (dirty)
+      std::cerr << "Dirty ";
+   if (optional)
+      std::cerr << "Optional ";
+   std::cerr << "Item (" << size << "@" << depth << (upgrade ? "u" : "") << ") ";
+   if (auto Pkg = reason.Pkg(); Pkg != 0)
+      std::cerr << pkgCache::PkgIterator(cache, cache.PkgP + Pkg).FullName();
+   if (auto Ver = reason.Ver(); Ver != 0)
+      std::cerr << pkgCache::VerIterator(cache, cache.VerP + Ver).ParentPkg().FullName() << "=" << pkgCache::VerIterator(cache, cache.VerP + Ver).VerStr();
+   std::cerr << " -> ";
+   for (auto sol : solutions)
+   {
+      auto Ver = pkgCache::VerIterator(cache, sol);
+      std::cerr << " | " << Ver.ParentPkg().FullName() << "=" << Ver.VerStr();
+   }
+}
+
+// Prints an implication graph part of the form A -> B -> C, possibly with "not"
+std::string APT::Solver::WhyStr(Reason reason)
+{
+   std::vector<std::string> out;
+
+   while (not reason.empty())
+   {
+      if (auto Pkg = pkgCache::PkgIterator(cache, cache.PkgP + reason.Pkg()); not Pkg.end())
+      {
+	 if ((*this)[Pkg].decision == Decision::MUSTNOT)
+	    out.push_back(std::string("not ") + Pkg.FullName());
+	 else
+	    out.push_back(Pkg.FullName());
+	 reason = (*this)[Pkg].reason;
+      }
+      if (auto Ver = pkgCache::VerIterator(cache, cache.VerP + reason.Ver()); not Ver.end())
+      {
+	 if ((*this)[Ver].decision == Decision::MUSTNOT)
+	    out.push_back(std::string("not ") + Ver.ParentPkg().FullName() + "=" + Ver.VerStr());
+	 else
+	    out.push_back(Ver.ParentPkg().FullName() + "=" + Ver.VerStr());
+	 reason = (*this)[Ver].reason;
+      }
+   }
+
+   std::string outstr;
+   for (auto I = out.rbegin(); I != out.rend(); ++I)
+   {
+      outstr += (outstr.size() == 0 ? "" : " -> ") + *I;
+   }
+   return outstr;
+}
+
+bool APT::Solver::Install(pkgCache::PkgIterator Pkg, Reason reason)
+{
+   if ((*this)[Pkg].decision == Decision::MUST)
+      return true;
+
+   // Check conflicting selections
+   if ((*this)[Pkg].decision == Decision::MUSTNOT)
+      return _error->Error("Conflict: %s -> %s but %s", WhyStr(reason).c_str(), Pkg.FullName().c_str(), WhyStr(Reason(Pkg)).c_str());
+
+   bool anyInstallable = false;
+   for (auto ver = Pkg.VersionList(); not ver.end(); ver++)
+      if ((*this)[ver].decision != Decision::MUSTNOT)
+	 anyInstallable = true;
+
+   if (not anyInstallable)
+   {
+      _error->Error("Conflict: %s -> %s but no versions are installable",
+		    WhyStr(reason).c_str(), Pkg.FullName().c_str());
+      for (auto ver = Pkg.VersionList(); not ver.end(); ver++)
+	 _error->Error("Uninstallable version: %s", WhyStr(Reason(ver)).c_str());
+      return false;
+   }
+
+   // Note decision
+   if (unlikely(debug >= 1))
+      std::cerr << "[" << depth() << "] Install:" << Pkg.FullName() << " (" << WhyStr(reason) << ")\n";
+   (*this)[Pkg] = {reason, depth(), Decision::MUST,};
+
+   // Insert the work item.
+   Work workItem{Reason(Pkg), depth()};
+   for (auto ver = Pkg.VersionList(); not ver.end(); ver++)
+      if (IsAllowedVersion(ver))
+	 workItem.solutions.push_back(ver);
+   std::sort(workItem.solutions.begin(), workItem.solutions.end(), CompareProviders3{cache, policy, Pkg});
+   assert(workItem.solutions.size() > 0);
+
+   if (workItem.solutions.size() > 1 || workItem.optional)
+      AddWork(std::move(workItem));
+   else if (not Install(pkgCache::VerIterator(cache, workItem.solutions[0]), workItem.reason))
+      return false;
+
+   if (not EnqueueCommonDependencies(Pkg))
+      return false;
+
+   return true;
+}
+
+bool APT::Solver::Install(pkgCache::VerIterator Ver, Reason reason)
+{
+   if ((*this)[Ver].decision == Decision::MUST)
+      return true;
+
+   if (unlikely(debug >= 1))
+      assert(IsAllowedVersion(Ver));
+
+   // Check conflicting selections
+   if ((*this)[Ver].decision == Decision::MUSTNOT)
+      return _error->Error("Conflict: %s -> %s but %s",
+			   WhyStr(reason).c_str(),
+			   (Ver.ParentPkg().FullName() + "=" + Ver.VerStr()).c_str(),
+			   WhyStr(Reason(Ver)).c_str());
+   if ((*this)[Ver.ParentPkg()].decision == Decision::MUSTNOT)
+      return _error->Error("Conflict: %s -> %s but %s",
+			   WhyStr(reason).c_str(),
+			   (Ver.ParentPkg().FullName() + "=" + Ver.VerStr()).c_str(),
+			   WhyStr(Reason(Ver.ParentPkg())).c_str());
+   for (auto otherVer = Ver.ParentPkg().VersionList(); not otherVer.end(); otherVer++)
+      if (otherVer->ID != Ver->ID && (*this)[otherVer].decision == Decision::MUST)
+	 return _error->Error("Conflict: %s -> %s but %s",
+			      WhyStr(reason).c_str(),
+			      (Ver.ParentPkg().FullName() + "=" + Ver.VerStr()).c_str(),
+			      WhyStr(Reason(otherVer)).c_str());
+
+   // Note decision
+   if (unlikely(debug >= 1))
+      std::cerr << "[" << depth() << "] Install:" << Ver.ParentPkg().FullName() << "=" << Ver.VerStr() << " (" << WhyStr(reason) << ")\n";
+   (*this)[Ver] = {reason, depth(), Decision::MUST,};
+   if ((*this)[Ver.ParentPkg()].decision != Decision::MUST)
+      (*this)[Ver.ParentPkg()] = {Reason(Ver), depth(), Decision::MUST,};
+
+   for (auto OV = Ver.ParentPkg().VersionList(); not OV.end(); ++OV)
+   {
+      if (OV != Ver && not Reject(OV, Reason(Ver)))
+	 return false;
+   }
+
+   for (auto dep = Ver.DependsList(); not dep.end();)
+   {
+      // Compute a single dependency element (glob or)
+      pkgCache::DepIterator start;
+      pkgCache::DepIterator end;
+      dep.GlobOr(start, end); // advances dep
+
+      if (not policy.IsImportantDep(start))
+	 continue;
+      if (not EnqueueOrGroup(start, end, Reason(Ver)))
+	 return false;
+   }
+
+   return true;
+}
+
+bool APT::Solver::Reject(pkgCache::PkgIterator Pkg, Reason reason)
+{
+   if ((*this)[Pkg].decision == Decision::MUSTNOT)
+      return true;
+
+   // Check conflicting selections
+   for (auto ver = Pkg.VersionList(); not ver.end(); ver++)
+      if ((*this)[ver].decision == Decision::MUST)
+	 return _error->Error("Conflict: %s -> not %s but %s", WhyStr(reason).c_str(), Pkg.FullName().c_str(), WhyStr(Reason(ver)).c_str());
+   if ((*this)[Pkg].decision == Decision::MUST)
+      return _error->Error("Conflict: %s -> not %s but %s", WhyStr(reason).c_str(), Pkg.FullName().c_str(), WhyStr(Reason(Pkg)).c_str());
+
+   // Reject the package and its versions.
+   if (unlikely(debug >= 1))
+      std::cerr << "[" << depth() << "] Reject:" << Pkg.FullName() << " (" << WhyStr(reason) << ")\n";
+   (*this)[Pkg] = {reason, depth(), Decision::MUSTNOT,};
+   for (auto ver = Pkg.VersionList(); not ver.end(); ver++)
+      if (not Reject(ver, Reason(Pkg)))
+	 return false;
+
+   needsRescore = true;
+
+   return true;
+}
+
+// \brief Do not install this version
+bool APT::Solver::Reject(pkgCache::VerIterator Ver, Reason reason)
+{
+   if ((*this)[Ver].decision == Decision::MUSTNOT)
+      return true;
+
+   // Check conflicting choices.
+   if ((*this)[Ver].decision == Decision::MUST)
+      return _error->Error("Conflict: %s -> not %s but %s",
+			   WhyStr(reason).c_str(),
+			   (Ver.ParentPkg().FullName() + "=" + Ver.VerStr()).c_str(),
+			   WhyStr(Reason(Ver)).c_str());
+
+   // Mark the package as rejected and propagate up as needed.
+   if (unlikely(debug >= 1))
+      std::cerr << "[" << depth() << "] Reject:" << Ver.ParentPkg().FullName() << "=" << Ver.VerStr() << " (" << WhyStr(reason) << ")\n";
+   (*this)[Ver] = {reason, depth(), Decision::MUSTNOT,};
+   if (auto pkg = Ver.ParentPkg(); (*this)[pkg].decision != Decision::MUSTNOT)
+   {
+      bool anyInstallable = false;
+      for (auto otherVer = pkg.VersionList(); not otherVer.end(); otherVer++)
+	 if (otherVer->ID != Ver->ID && (*this)[otherVer].decision != Decision::MUSTNOT)
+	    anyInstallable = true;
+
+      if (anyInstallable)
+	 ;
+      else if ((*this)[pkg].decision == Decision::MUST) // Must install, but none available
+      {
+	 _error->Error("Conflict: %s but no versions are installable",
+		       WhyStr(Reason(pkg)).c_str());
+	 for (auto otherVer = pkg.VersionList(); not otherVer.end(); otherVer++)
+	    if ((*this)[otherVer].decision == Decision::MUSTNOT)
+	       _error->Error("Uninstallable version: %s", WhyStr(Reason(otherVer)).c_str());
+	 return _error->Error("Uninstallable version: %s -> not %s",
+			      WhyStr(reason).c_str(),
+			      (Ver.ParentPkg().FullName() + "=" + Ver.VerStr()).c_str());
+      }
+      else if ((*this)[Ver.ParentPkg()].decision != Decision::MUSTNOT) // Last installable invalidated
+	 (*this)[Ver.ParentPkg()] = {Reason(Ver), depth(), Decision::MUSTNOT};
+   }
+
+   if (not RejectReverseDependencies(Ver))
+      return false;
+
+   needsRescore = true;
+
+   return true;
+}
+
+bool APT::Solver::EnqueueCommonDependencies(pkgCache::PkgIterator Pkg)
+{
+   if (not _config->FindB("APT::Solver::Enqueue-Common-Dependencies", true))
+      return false;
+   for (auto dep = Pkg.VersionList().DependsList(); not dep.end();)
+   {
+      pkgCache::DepIterator start;
+      pkgCache::DepIterator end;
+      dep.GlobOr(start, end); // advances dep
+
+      bool allHaveDep = true;
+      for (auto ver = Pkg.VersionList()++; not ver.end(); ver++)
+      {
+	 bool haveDep = false;
+	 for (auto otherDep = ver.DependsList(); not haveDep && not otherDep.end(); otherDep++)
+	    haveDep = otherDep->DependencyData == start->DependencyData;
+	 if (!haveDep)
+	    allHaveDep = haveDep;
+      }
+      if (not allHaveDep)
+	 continue;
+      if (not policy.IsImportantDep(start))
+	 continue;
+      if (not EnqueueOrGroup(start, end, Reason(Pkg)))
+	 return false;
+   }
+
+   return true;
+}
+
+bool APT::Solver::EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepIterator end, Reason reason)
+{
+   auto TgtPkg = start.TargetPkg();
+   auto Ver = start.ParentVer();
+   auto fixPolicy = _config->FindB("APT::Get::Fix-Policy-Broken");
+
+   if (unlikely(debug >= 3))
+      std::cerr << "Found dependency critical " << Ver.ParentPkg().FullName() << "=" << Ver.VerStr() << " -> " << start.TargetPkg().FullName() << "\n";
+
+   Work workItem{reason, depth(), not start.IsCritical() /* optional */};
+
+   do
+   {
+      auto begin = workItem.solutions.size();
+      auto all = start.AllTargets();
+
+      for (auto tgt = all; *tgt; ++tgt)
+      {
+	 pkgCache::VerIterator tgti(cache, *tgt);
+
+	 if (start.IsNegative())
+	 {
+	    if (unlikely(debug >= 3))
+	       std::cerr << "Reject: " << Ver.ParentPkg().FullName() << "=" << Ver.VerStr() << " -> " << tgti.ParentPkg().FullName() << "=" << tgti.VerStr() << "\n";
+	    // FIXME: We should be collecting these and marking the heap only once.
+	    if (not Reject(pkgCache::VerIterator(cache, *tgt), Reason(Ver)))
+	       return false;
+	 }
+	 else
+	 {
+	    if (unlikely(debug >= 3))
+	       std::cerr << "Adding work to  item " << Ver.ParentPkg().FullName() << "=" << Ver.VerStr() << " -> " << tgti.ParentPkg().FullName() << "=" << tgti.VerStr() << "\n";
+	    if (IsAllowedVersion(*tgt))
+	       workItem.solutions.push_back(*tgt);
+	 }
+      }
+      delete[] all;
+
+      // If we are fixing the policy, we need to sort each alternative in an or group separately
+      // FIXME: This is not really true, though, we should fix the CompareProviders to ignore the
+      // installed state
+      if (fixPolicy)
+	 std::sort(workItem.solutions.begin() + begin, workItem.solutions.end(), CompareProviders3{cache, policy, TgtPkg});
+
+      if (start == end)
+	 break;
+      ++start;
+   } while (1);
+
+   if (not fixPolicy)
+      std::sort(workItem.solutions.begin(), workItem.solutions.end(), CompareProviders3{cache, policy, TgtPkg});
+
+   // Figure out if the reason is installed
+   bool reasonInstalled = false;
+   if (auto p = workItem.reason.Pkg())
+      reasonInstalled = pkgCache::PkgIterator(cache, cache.PkgP + p)->CurrentVer != 0;
+   else if (auto v = workItem.reason.Ver())
+      reasonInstalled = pkgCache::VerIterator(cache, cache.VerP + v).ParentPkg()->CurrentVer != 0;
+
+   // Try to perserve satisfied Recommends. FIXME: We should check if the Recommends was there in the installed version?
+   if (workItem.optional && reasonInstalled && not fixPolicy &&
+       not std::any_of(workItem.solutions.begin(), workItem.solutions.end(), [this](auto ver)
+		       { return pkgCache::VerIterator(cache, ver).ParentPkg()->CurrentVer != 0; }))
+   {
+      if (unlikely(debug >= 3))
+      {
+	 std::cerr << "Ignoring currently unsatisfied Recommends ";
+	 workItem.Dump(cache);
+	 std::cerr << "\n";
+      }
+      return true;
+   }
+   if (not workItem.solutions.empty())
+   {
+      // std::sort(workItem.solutions.begin(), workItem.solutions.end(), CompareProviders3{cache, TgtPkg});
+      if (unlikely(debug >= 3 && workItem.optional))
+      {
+	 std::cerr << "Enqueuing currently satisfied Recommends ";
+	 workItem.Dump(cache);
+	 std::cerr << "\n";
+      }
+      if (workItem.optional || workItem.solutions.size() > 1)
+	 AddWork(std::move(workItem));
+      else if (not Install(pkgCache::VerIterator(cache, workItem.solutions[0]), reason))
+	 return false;
+   }
+   else if (start.IsCritical() && not start.IsNegative())
+   {
+      return _error->Error("Unsatisfiable dependency group %s=%s -> %s", Ver.ParentPkg().FullName().c_str(), Ver.VerStr(), TgtPkg.FullName().c_str());
+   }
+   return true;
+}
+
+// \brief Find the or group containing the given dependency.
+static void FindOrGroup(pkgCache::DepIterator const &D, pkgCache::DepIterator &start, pkgCache::DepIterator &end)
+{
+   for (auto dep = D.ParentVer().DependsList(); not dep.end();)
+   {
+      dep.GlobOr(start, end); // advances dep
+
+      for (auto member = start;;)
+      {
+	 if (member == D)
+	    return;
+	 if (member == end)
+	    break;
+	 member++;
+      }
+   }
+
+   _error->Fatal("Found a dependency that does not exist in its parent version");
+   abort();
+}
+
+// This is the opposite of EnqueueOrDependencies, it rejects the reverse dependencies of the
+// given version iterator.
+bool APT::Solver::RejectReverseDependencies(pkgCache::VerIterator Ver)
+{
+   // This checks whether an or group is still satisfiable.
+   auto stillPossible = [this](pkgCache::DepIterator start, pkgCache::DepIterator end)
+   {
+      while (1)
+      {
+	 std::unique_ptr<pkgCache::Version *[]> Ts{start.AllTargets()};
+	 for (size_t i = 0; Ts[i] != nullptr; ++i)
+	    if ((*this)[Ts[i]].decision != Decision::MUSTNOT)
+	       return true;
+
+	 if (start == end)
+	    return false;
+
+	 start++;
+      }
+   };
+
+   for (auto RD = Ver.ParentPkg().RevDependsList(); not RD.end(); ++RD)
+   {
+      auto RDV = RD.ParentVer();
+      if (RD.IsNegative() || not RD.IsCritical() || not RD.IsSatisfied(Ver))
+	 continue;
+
+      if ((*this)[RDV].decision == Decision::MUSTNOT)
+	 continue;
+
+      pkgCache::DepIterator start;
+      pkgCache::DepIterator end;
+      FindOrGroup(RD, start, end);
+
+      if (stillPossible(start, end))
+	 continue;
+
+      if (unlikely(debug >= 3))
+	 std::cerr << "Propagate NOT " << Ver.ParentPkg().FullName() << "=" << Ver.VerStr() << " to " << RDV.ParentPkg().FullName() << "=" << RDV.VerStr() << " for dependency group starting with" << start.TargetPkg().FullName() << std::endl;
+
+      if (not Reject(RDV, Reason(Ver)))
+	 return false;
+   }
+   return true;
+}
+
+bool APT::Solver::IsAllowedVersion(pkgCache::Version *V)
+{
+   pkgCache::VerIterator ver(cache, V);
+   if (not StrictPinning || ver.ParentPkg().CurrentVer() == ver || policy.GetCandidateVer(ver.ParentPkg()) == ver)
+      return true;
+
+   if (unlikely(debug >= 3))
+      std::cerr << "Ignoring: " << ver.ParentPkg().FullName() << "=" << ver.VerStr() << "(neither candidate nor installed)\n";
+   return false;
+}
+
+void APT::Solver::Push(Work work)
+{
+   if (unlikely(debug >= 2))
+   {
+      std::cerr << "Trying choice for ";
+      work.Dump(cache);
+      std::cerr << "\n";
+   }
+   choices.push_back(std::move(work));
+   // Pop() will call MergeWithStack() when reverting to level 0, or RevertToStack after dumping to the debug log.
+   _error->PushToStack();
+}
+
+bool APT::Solver::Pop()
+{
+   auto depth = APT::Solver::depth();
+   if (depth == 0)
+      return false;
+
+   if (unlikely(debug >= 2))
+      for (std::string msg; _error->PopMessage(msg);)
+	 std::cerr << "Branch failed: " << msg << std::endl;
+
+   _error->RevertToStack();
+
+   depth--;
+
+   // Clean up the higher level states.
+   // FIXME: Do not override the hints here.
+   for (auto &state : pkgStates)
+      if (state.depth > depth)
+	 state = {};
+   for (auto &state : verStates)
+      if (state.depth > depth)
+	 state = {};
+
+   // This destroys the invariants that `work` must be a heap. But this is ok:
+   // we are restoring the invariant below, because rejecting a package always
+   // calls std::make_heap.
+   work.erase(std::remove_if(work.begin(), work.end(), [depth](Work &w) -> bool
+			     { return w.depth > depth || w.dirty; }),
+	      work.end());
+   std::make_heap(work.begin(), work.end());
+
+   // Go over the solved items, see if any of them need to be moved back or deleted.
+   solved.erase(std::remove_if(solved.begin(), solved.end(), [this, depth](Work &w) -> bool
+			       {
+				 if (w.depth > depth) // Deeper decision level is no longer valid.
+				    return true;
+				 // This item is still solved, keep it on the solved list.
+				 if (not std::any_of(w.solutions.begin(), w.solutions.end(), [this](auto ver)
+						     { return (*this)[ver].decision == Decision::MUST; }))
+				    return false;
+				 // We are not longer solved, move it back to work.
+				 AddWork(std::move(w));
+				 return true; }),
+		solved.end());
+
+   Work w = std::move(choices.back());
+   choices.pop_back();
+   if (unlikely(debug >= 2))
+   {
+      std::cerr << "Backtracking to choice ";
+      w.Dump(cache);
+      std::cerr << "\n";
+   }
+   if (unlikely(debug >= 4))
+   {
+      std::cerr << "choices: ";
+      for (auto &i : choices)
+      {
+	 std::cerr << pkgCache::VerIterator(cache, i.choice).ParentPkg().FullName(true) << "=" << pkgCache::VerIterator(cache, i.choice).VerStr();
+      }
+      std::cerr << std::endl;
+   }
+
+   assert(w.choice != nullptr);
+   // FIXME: There should be a reason!
+   if (not Reject(pkgCache::VerIterator(cache, w.choice), {}))
+      return false;
+
+   w.choice = nullptr;
+   AddWork(std::move(w));
+   return true;
+}
+
+void APT::Solver::AddWork(Work &&w)
+{
+   w.size = std::count_if(w.solutions.begin(), w.solutions.end(), [this](auto V)
+			  { return (*this)[V].decision != Decision::MUSTNOT; });
+   work.push_back(std::move(w));
+   std::push_heap(work.begin(), work.end());
+}
+
+void APT::Solver::RescoreWorkIfNeeded()
+{
+   if (not needsRescore)
+      return;
+
+   needsRescore = false;
+   std::vector<Work> resized;
+   for (auto &w : work)
+   {
+      if (w.dirty)
+	 continue;
+      size_t newSize = std::count_if(w.solutions.begin(), w.solutions.end(), [this](auto V)
+				     { return (*this)[V].decision != Decision::MUSTNOT; });
+
+      // Notably we only insert the work into the queue if it got smaller. Work that got larger
+      // we just move around when we get to it too early in Solve(). This reduces memory usage
+      // at the expense of counting each item we see in Solve().
+      if (newSize < w.size)
+      {
+	 Work newWork(w);
+	 newWork.size = newSize;
+	 resized.push_back(std::move(newWork));
+	 w.dirty = true;
+      }
+   }
+   if (unlikely(debug >= 2))
+      std::cerr << "Rescored: " << resized.size() << "items\n";
+   for (auto &w : resized)
+   {
+      work.push_back(std::move(w));
+      std::push_heap(work.begin(), work.end());
+   }
+}
+
+bool APT::Solver::Solve()
+{
+   while (not work.empty())
+   {
+      // Rescore the work if we need to
+      RescoreWorkIfNeeded();
+      // *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().dirty)
+      {
+	 work.pop_back();
+	 continue;
+      }
+
+      // If our size increased, queue again.
+      size_t newSize = std::count_if(work.back().solutions.begin(), work.back().solutions.end(), [this](auto V)
+				     { return (*this)[V].decision != Decision::MUSTNOT; });
+
+      if (newSize > work.back().size)
+      {
+	 work.back().size = newSize;
+	 std::push_heap(work.begin(), work.end());
+	 continue;
+      }
+      assert(newSize == work.back().size);
+
+      auto item = std::move(work.back());
+      work.pop_back();
+      solved.push_back(item);
+
+      if (std::any_of(item.solutions.begin(), item.solutions.end(), [this](auto ver)
+		      { return (*this)[ver].decision == Decision::MUST; }))
+      {
+	 if (unlikely(debug >= 2))
+	 {
+	    std::cerr << "ELIDED ";
+	    item.Dump(cache);
+	    std::cerr << "\n";
+	 }
+	 continue;
+      }
+
+      if (unlikely(debug >= 1))
+      {
+	 item.Dump(cache);
+	 std::cerr << "\n";
+      }
+
+      assert(item.solutions.size() > 1 || item.optional);
+
+      bool foundSolution = false;
+      for (auto &sol : item.solutions)
+      {
+	 pkgCache::VerIterator ver(cache, sol);
+	 if ((*this)[ver].decision == Decision::MUSTNOT)
+	 {
+	    if (unlikely(debug >= 3))
+	       std::cerr << "(existing conflict: " << ver.ParentPkg().FullName() << "=" << ver.VerStr() << ")\n";
+	    continue;
+	 }
+	 if (item.size > 1 || item.optional)
+	 {
+	    item.choice = ver;
+	    Push(item);
+	 }
+	 if (unlikely(debug >= 3))
+	    std::cerr << "(try it: " << ver.ParentPkg().FullName() << "=" << ver.VerStr() << ")\n";
+	 if (not Install(pkgCache::VerIterator(cache, ver), item.reason) && not Pop())
+	    return false;
+	 foundSolution = true;
+	 break;
+      }
+      if (not foundSolution && not item.optional)
+      {
+	 std::ostringstream dep;
+	 assert(item.solutions.size() > 0);
+	 for (auto &sol : item.solutions)
+	    dep << (dep.tellp() == 0 ? "" : " | ") << pkgCache::VerIterator(cache, sol).ParentPkg().FullName() << "=" << pkgCache::VerIterator(cache, sol).VerStr();
+	 _error->Error("Unsatisfiable dependency: %s -> %s", WhyStr(item.reason).c_str(), dep.str().c_str());
+	 for (auto &sol : item.solutions)
+	    if ((*this)[sol].decision == Decision::MUSTNOT)
+	       _error->Error("Not considered: %s=%s: %s", pkgCache::VerIterator(cache, sol).ParentPkg().FullName().c_str(),
+			     pkgCache::VerIterator(cache, sol).VerStr(),
+			     WhyStr(Reason(pkgCache::VerIterator(cache, sol))).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 KeepAuto = not _config->FindB("APT::Get::AutomaticRemove");
+   bool AllowRemove = _config->FindB("APT::Solver::Remove", true);
+   bool AllowInstall = _config->FindB("APT::Solver::Install", true);
+   DefaultRootSetFunc2 rootSet(&cache);
+
+   for (auto P = cache.PkgBegin(); not P.end(); P++)
+   {
+      if (P->VersionList == nullptr)
+	 continue;
+
+      auto state = depcache[P];
+      auto maybeInstall = state.Install() || (state.Keep() && P->CurrentVer);
+      auto reject = state.Delete() || (depcache[P].Keep() && not P->CurrentVer && depcache[P].Protect());
+      if (P->SelectedState == pkgCache::State::Hold && not state.Protect())
+      {
+	 if (unlikely(debug >= 1))
+	    std::cerr << "Hold " << P.FullName() << "\n";
+	 if (P->CurrentVer ? not Install(P.CurrentVer(), {}) : not Reject(P, {}))
+	    return false;
+      }
+      else if (reject)
+      {
+	 if (unlikely(debug >= 1))
+	    std::cerr << "Delete " << P.FullName() << "\n";
+	 if (!Reject(P, {}))
+	    return false;
+      }
+      else if (maybeInstall && P->Flags & (pkgCache::Flag::Essential | pkgCache::Flag::Important))
+      {
+	 if (unlikely(debug >= 1))
+	    std::cerr << "ESSENTIAL " << P.FullName() << "\n";
+	 if (depcache[P].Keep() ? not Install(P, {}) : not Install(depcache.GetCandidateVersion(P), {}))
+	    return false;
+      }
+      else if (maybeInstall && not(depcache[P].Flags & pkgCache::Flag::Auto))
+      {
+	 if (unlikely(debug >= 1))
+	    std::cerr << "MANUAL " << P.FullName() << "\n";
+	 if (depcache[P].Keep() ? not Install(P, {}) : not Install(depcache.GetCandidateVersion(P), {}))
+	    return false;
+      }
+      else if (maybeInstall && (KeepAuto || rootSet.InRootSet(P)) && (depcache[P].Flags & pkgCache::Flag::Auto))
+      {
+	 auto Upgrade = depcache.GetCandidateVersion(P) != P.CurrentVer();
+	 if (unlikely(debug >= 1))
+	    std::cerr << "AUTOMATIC " << P.FullName() << (Upgrade ? " - upgrade" : "") << "\n";
+
+	 if (not AllowRemove)
+	 {
+	    if (depcache[P].Keep() ? not Install(P, {}) : not Install(depcache.GetCandidateVersion(P), {}))
+	       return false;
+	 }
+	 else
+	 {
+	    Work w{Reason(), depth(), true, Upgrade};
+	    for (auto V = P.VersionList(); not V.end(); ++V)
+	       if (IsAllowedVersion(V))
+		  w.solutions.push_back(V);
+	    std::sort(w.solutions.begin(), w.solutions.end(), CompareProviders3{cache, policy, P});
+	    AddWork(std::move(w));
+	 }
+      }
+      else if (P->CurrentVer == 0 && not AllowInstall)
+      {
+	 if (unlikely(debug >= 1))
+	    std::cerr << "NOT ALLOWING INSTALL OF " << P.FullName() << "\n";
+	 if (not Reject(P, {}))
+	    return false;
+      }
+   }
+
+   return true;
+}
+
+bool APT::Solver::ToDepCache(pkgDepCache &depcache)
+{
+   pkgDepCache::ActionGroup group(depcache);
+   for (auto P = cache.PkgBegin(); not P.end(); P++)
+   {
+      if ((*this)[P].decision == Decision::MUST)
+      {
+	 for (auto V = P.VersionList(); not V.end(); V++)
+	 {
+	    if ((*this)[V].decision == Decision::MUST)
+	    {
+	       depcache.SetCandidateVersion(V);
+	       break;
+	    }
+	 }
+	 auto reason = (*this)[depcache.GetCandidateVersion(P)].reason;
+	 if (auto RP = reason.Pkg(); RP == P.MapPointer())
+	    reason = (*this)[P].reason;
+
+	 depcache.MarkInstall(P, false, 0, reason.empty());
+	 if (not P->CurrentVer)
+	    depcache.MarkAuto(P, not reason.empty());
+	 depcache[P].Marked = 1;
+	 depcache[P].Garbage = 0;
+      }
+      else if (P->CurrentVer)
+      {
+	 depcache.MarkDelete(P, false, 0, (*this)[P].reason.empty());
+	 depcache[P].Marked = 0;
+	 depcache[P].Garbage = 1;
+      }
+   }
+   return true;
+}
diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h
new file mode 100644
index 000000000..cf2fb2ecc
--- /dev/null
+++ b/apt-pkg/solver3.h
@@ -0,0 +1,286 @@
+/*
+ * solver3.h - The APT 3.0 solver
+ *
+ * Copyright (c) 2023 Julian Andres Klode
+ * Copyright (c) 2023 Canonical Ltd
+ *
+ * SPDX-License-Identifier: GPL-2.0+
+ */
+
+#include <vector>
+
+#include <apt-pkg/configuration.h>
+#include <apt-pkg/depcache.h>
+#include <apt-pkg/pkgcache.h>
+#include <apt-pkg/policy.h>
+
+namespace APT
+{
+
+/*
+ * \brief APT 3.0 solver
+ *
+ * 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.
+ */
+class Solver
+{
+   enum class Decision : uint16_t;
+   enum class Hint : uint16_t;
+   struct Reason;
+   template <typename T>
+   struct State;
+   struct Work;
+
+   // \brief Type to record depth at. This may very well be a 16-bit
+   // unsigned integer, then change Solver::State::Decision to be a
+   // uint16_t class enum as well to get a more compact space.
+   using depth_type = unsigned int;
+
+   // Documentation
+   template <typename T>
+   using heap = std::vector<T>;
+
+   static_assert(sizeof(depth_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;
+   // States for packages
+   std::vector<State<pkgCache::Package>> pkgStates{};
+   // States for versions
+   std::vector<State<pkgCache::Version>> verStates{};
+
+   // \brief Helper function for safe access to package state.
+   inline State<pkgCache::Package> &operator[](pkgCache::Package *P)
+   {
+      return pkgStates[P->ID];
+   }
+
+   // \brief Helper function for safe access to version state.
+   inline State<pkgCache::Version> &operator[](pkgCache::Version *V)
+   {
+      return verStates[V->ID];
+   }
+
+   // \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.
+   heap<Work> work{};
+   // \brief Whether RescoreWork() actually needs to rescore the work.
+   bool needsRescore{false};
+
+   // \brief Current decision level.
+   //
+   // Each time a decision needs to be made we can push the item under
+   // consideration to our backlog of choices made and then later we can
+   // restore it easily.
+   std::vector<Work> choices{};
+   // \brief Backlog of solved work.
+   //
+   // Solved work may become invalidated when backtracking, so store it
+   // here to revisit it later.
+   std::vector<Work> solved{};
+
+   /// Various configuration options
+   // \brief Debug level
+   int debug{_config->FindI("Debug::APT::Solver")};
+   // \brief If set, we try to keep automatically installed packages installed.
+   bool KeepAuto{not _config->FindB("APT::Get::AutomaticRemove")};
+   // \brief If set, removals are allowed.
+   bool AllowRemove{_config->FindB("APT::Solver::Remove", true)};
+   // \brief If set, installs are allowed.
+   bool AllowInstall{_config->FindB("APT::Solver::Install", true)};
+   // \brief If set, we use strict pinning.
+   bool StrictPinning{_config->FindB("APT::Solver::Strict-Pinning", true)};
+
+   // \brief Enqueue dependencies shared by all versions of the package.
+   bool EnqueueCommonDependencies(pkgCache::PkgIterator Pkg);
+   // \brief Reject reverse dependencies. Must call std::make_heap() after.
+   bool RejectReverseDependencies(pkgCache::VerIterator Ver);
+   // \brief Enqueue a single or group
+   bool EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepIterator end, Reason reason);
+   // \brief Check if a version is allowed by policy.
+   bool IsAllowedVersion(pkgCache::Version *V);
+
+   // \brief Return the current depth (choices.size() with casting)
+   depth_type depth()
+   {
+      return static_cast<depth_type>(choices.size());
+   }
+
+   public:
+   // \brief Create a new decision level.
+   bool Pop();
+   // \brief Revert to the previous decision level.
+   void Push(Work work);
+   // \brief Add work to our work queue.
+   void AddWork(Work &&work);
+   // \brief Rescore the work after a reject or a pop
+   void RescoreWorkIfNeeded();
+
+   // \brief Basic solver initializer. This cannot fail.
+   Solver(pkgCache &Cache, pkgDepCache::Policy &Policy);
+
+   // \brief Mark the package for install. This is annoying as it incurs a decision
+   bool Install(pkgCache::PkgIterator Pkg, Reason reason);
+   // \brief Install a version.
+   bool Install(pkgCache::VerIterator Ver, Reason reason);
+   // \brief Do not install this package
+   bool Reject(pkgCache::PkgIterator Pkg, Reason reason);
+   // \brief Do not install this version.
+   bool Reject(pkgCache::VerIterator Ver, Reason reason);
+
+   // \brief Apply the selections from the dep cache to the solver
+   bool FromDepCache(pkgDepCache &depcache);
+   // \brief Apply the solver result to the depCache
+   bool ToDepCache(pkgDepCache &depcache);
+
+   // \brief Solve the dependencies
+   bool Solve();
+
+   // Print dependency chain
+   std::string WhyStr(Reason reason);
+};
+
+}; // namespace APT
+
+/**
+ * \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.
+ *
+ * If the reason is empty, this means the package is automatically installed.
+ */
+struct APT::Solver::Reason
+{
+   uint32_t IsVersion : 1;
+   uint32_t MapPtr : 31;
+
+   Reason() : IsVersion(0), MapPtr(0) {}
+   explicit Reason(pkgCache::PkgIterator const &Pkg) : IsVersion(0), MapPtr(Pkg.MapPointer()) {}
+   explicit Reason(pkgCache::VerIterator const &Ver) : IsVersion(1), MapPtr(Ver.MapPointer()) {}
+
+   // \brief Return the package, if any, otherwise 0.
+   map_pointer<pkgCache::Package> Pkg() const
+   {
+      return IsVersion ? 0 : map_pointer<pkgCache::Package>{(uint32_t)MapPtr};
+   }
+   // \brief Return the version, if any, otherwise 0.
+   map_pointer<pkgCache::Version> Ver() const
+   {
+      return IsVersion ? map_pointer<pkgCache::Version>{(uint32_t)MapPtr} : 0;
+   }
+   // \brief Check if there is no reason.
+   bool empty() const
+   {
+      return IsVersion == 0 && MapPtr == 0;
+   }
+};
+
+/**
+ * \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.
+ *
+ * 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
+{
+   // \brief Reason for the work
+   Reason reason;
+   // \brief The depth at which the item has been added
+   depth_type depth;
+
+   // \brief Possible solutions to this task, ordered in order of preference.
+   std::vector<pkgCache::Version *> solutions{};
+
+   // This is a union because we only need to store the choice we made when adding
+   // to the choice vector, and we don't need the size of valid choices in there.
+   union
+   {
+      // The choice we took
+      pkgCache::Version *choice;
+      // Number of valid choices
+      size_t size;
+   };
+
+   // \brief Whether this is an optional work item, they will be processed last
+   bool optional;
+   // \brief Whether this is an ugprade
+   bool upgrade;
+   // \brief This item should be removed from the queue.
+   bool dirty;
+
+   bool operator<(APT::Solver::Work const &b) const;
+   // \brief Dump the work item to std::cerr
+   void Dump(pkgCache &cache);
+
+   inline Work(Reason reason, depth_type depth, bool optional = false, bool upgrade = false) : reason(reason), depth(depth), size(0), optional(optional), upgrade(upgrade), dirty(false) {}
+};
+
+// \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,
+};
+
+// \brief Hints for the solver about the item.
+enum class APT::Solver::Hint : uint16_t
+{
+   // \brief We have not made a choice about the package yet
+   NONE,
+   // \brief This package was listed as a Recommends of a must package,
+   SHOULD,
+   // \brief This package was listed as a Suggests of a must-not package
+   MAY,
+};
+
+/**
+ * \brief The solver state
+ *
+ * For each version, the solver records a decision at a certain level. It
+ * maintains an array mapping from version ID to state.
+ */
+template <typename T>
+struct APT::Solver::State
+{
+   // \brief The reason for causing this state (invalid for NONE).
+   //
+   // 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
+   // leading to a conflict with a package in K < N, we will record all
+   // of them as REJECT in depth = K.
+   //
+   // You can follow the reason chain upwards as long as the depth
+   // doesn't increase to unwind.
+   //
+   // Reasons < 0 are package ID, reasons > 0 are version IDs.
+   Reason reason{};
+
+   // \brief The depth at which the decision has been taken
+   depth_type depth{0};
+
+   // \brief This essentially describes the install state in RFC2119 terms.
+   Decision decision{Decision::NONE};
+
+   // \brief Any hint.
+   Hint hint{Hint::NONE};
+};
diff --git a/apt-pkg/upgrade.cc b/apt-pkg/upgrade.cc
index fad47838c..ac0b71cdf 100644
--- a/apt-pkg/upgrade.cc
+++ b/apt-pkg/upgrade.cc
@@ -312,6 +312,11 @@ bool pkgMinimizeUpgrade(pkgDepCache &Cache)
 // APT::Upgrade::Upgrade - Upgrade using a specific strategy		/*{{{*/
 bool APT::Upgrade::Upgrade(pkgDepCache &Cache, int mode, OpProgress * const Progress)
 {
+   _config->Set("APT::Solver::Upgrade", "true");
+   if (mode & FORBID_REMOVE_PACKAGES)
+      _config->Set("APT::Solver::Remove", "false");
+   if (mode & FORBID_INSTALL_NEW_PACKAGES)
+      _config->Set("APT::Solver::Install", "false");
    if (mode == ALLOW_EVERYTHING)
       return pkgDistUpgrade(Cache, Progress);
    else if ((mode & ~FORBID_REMOVE_PACKAGES) == 0)