solver3: Refactor to use a namespace

This removes the need for the forward references, thus fixing part
of the libc++ issues pointed out in [merge-511].

[merge-511] https://salsa.debian.org/apt-team/apt/-/merge_requests/511/diffs

5 files changed, 241 insertions, 243 deletions

diff --git a/apt-pkg/edsp.cc b/apt-pkg/edsp.cc
index 6c9c3f3ee..a2f2e0c00 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::Solver 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 6f84a11a8..50bef7b9f 100644
--- a/apt-pkg/solver3.cc
+++ b/apt-pkg/solver3.cc
@@ -38,13 +38,16 @@
 #include <iomanip>
 #include <sstream>
 
+namespace APT::Solver
+{
+
 // FIXME: Helpers stolen from DepCache, please give them back.
-struct APT::Solver::CompareProviders3 /*{{{*/
+struct Solver::CompareProviders3 /*{{{*/
 {
    pkgCache &Cache;
    pkgDepCache::Policy &Policy;
    pkgCache::PkgIterator const Pkg;
-   APT::Solver &Solver;
+   APT::Solver::Solver &Solver;
 
    pkgCache::VerIterator bestVersion(pkgCache::PkgIterator pkg)
    {
@@ -196,7 +199,7 @@ class DefaultRootSetFunc2 : public pkgDepCache::DefaultRootSetFunc
 }; // FIXME: DEDUP with pkgDepCache.
 /*}}}*/
 
-APT::Solver::Solver(pkgCache &cache, pkgDepCache::Policy &policy, EDSP::Request::Flags requestFlags)
+Solver::Solver(pkgCache &cache, pkgDepCache::Policy &policy, EDSP::Request::Flags requestFlags)
     : cache(cache),
       policy(policy),
       rootState(new State),
@@ -210,16 +213,16 @@ APT::Solver::Solver(pkgCache &cache, pkgDepCache::Policy &policy, EDSP::Request:
    // Ensure trivially
    static_assert(std::is_trivially_destructible_v<Work>);
    static_assert(std::is_trivially_destructible_v<Trail>);
-   static_assert(sizeof(APT::Solver::Var) == sizeof(map_pointer<pkgCache::Package>));
-   static_assert(sizeof(APT::Solver::Var) == sizeof(map_pointer<pkgCache::Version>));
+   static_assert(sizeof(Var) == sizeof(map_pointer<pkgCache::Package>));
+   static_assert(sizeof(Var) == sizeof(map_pointer<pkgCache::Version>));
    // Root state is "true".
    rootState->decision = 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,7 +283,7 @@ 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)
@@ -292,7 +295,7 @@ std::string APT::Solver::Work::toString(pkgCache &cache) const
    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{};
@@ -307,13 +310,13 @@ inline APT::Solver::Var APT::Solver::bestReason(APT::Solver::Clause const *claus
    return clause->reason;
 }
 
-inline APT::Solver::LiftedBool APT::Solver::value(Lit lit) const
+inline LiftedBool Solver::value(Lit lit) const
 {
    return lit.sign() ? ~(*this)[lit.var()].decision : (*this)[lit.var()].decision;
 }
 
 // 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())
@@ -333,7 +336,7 @@ 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 decision, const Clause *rclause, std::string prefix, std::unordered_set<Var> &seen) const
 {
    std::ostringstream out;
 
@@ -498,7 +501,7 @@ std::string APT::Solver::LongWhyStr(Var var, bool decision, const Clause *rclaus
 // 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::ObsoletedByNewerSourceVersion(pkgCache::VerIterator cand) const
 {
    const auto pkg = cand.ParentPkg();
    const int candPriority = GetPriority(cand);
@@ -525,7 +528,7 @@ bool APT::Solver::ObsoletedByNewerSourceVersion(pkgCache::VerIterator cand) cons
    return false;
 }
 
-bool APT::Solver::Obsolete(pkgCache::PkgIterator pkg, bool AllowManual) const
+bool Solver::Obsolete(pkgCache::PkgIterator pkg, bool AllowManual) const
 {
    if ((*this)[pkg].flags.manual && not AllowManual)
       return false;
@@ -562,13 +565,13 @@ bool APT::Solver::Obsolete(pkgCache::PkgIterator pkg, bool AllowManual) const
    pkgObsolete[pkg] = 2;
    return true;
 }
-bool APT::Solver::Assume(Lit lit, const Clause *reason)
+bool Solver::Assume(Lit lit, const Clause *reason)
 {
    trailLim.push_back(trail.size());
    return Enqueue(lit, std::move(reason));
 }
 
-bool APT::Solver::Enqueue(Lit lit, const Clause *reason)
+bool Solver::Enqueue(Lit lit, const Clause *reason)
 {
    auto &state = (*this)[lit.var()];
    auto decisionCast = lit.sign() ? LiftedBool::False : LiftedBool::True;
@@ -601,7 +604,7 @@ bool APT::Solver::Enqueue(Lit lit, const Clause *reason)
    return true;
 }
 
-bool APT::Solver::Propagate()
+bool Solver::Propagate()
 {
    while (!propQ.empty())
    {
@@ -685,7 +688,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 *Solver::RegisterClause(Clause &&clause)
 {
    auto &clauses = (*this)[clause.reason].clauses;
    pkgCache::DepIterator dep(cache, clause.dep);
@@ -750,7 +753,7 @@ const APT::Solver::Clause *APT::Solver::RegisterClause(Clause &&clause)
    return inserted.get();
 }
 
-void APT::Solver::Discover(Var var)
+void Solver::Discover(Var var)
 {
    assert(discoverQ.empty());
    discoverQ.push(var);
@@ -825,7 +828,7 @@ void APT::Solver::Discover(Var var)
    }
 }
 
-void APT::Solver::RegisterCommonDependencies(pkgCache::PkgIterator Pkg)
+void Solver::RegisterCommonDependencies(pkgCache::PkgIterator Pkg)
 {
    for (auto dep = Pkg.VersionList().DependsList(); not dep.end();)
    {
@@ -852,7 +855,7 @@ void APT::Solver::RegisterCommonDependencies(pkgCache::PkgIterator Pkg)
    }
 }
 
-APT::Solver::Clause APT::Solver::TranslateOrGroup(pkgCache::DepIterator start, pkgCache::DepIterator end, Var reason)
+Clause Solver::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.
@@ -990,7 +993,7 @@ APT::Solver::Clause APT::Solver::TranslateOrGroup(pkgCache::DepIterator start, p
    return clause;
 }
 
-void APT::Solver::Push(Var var, Work work)
+void Solver::Push(Var var, Work work)
 {
    if (unlikely(debug >= 2))
       std::cerr << "Trying choice for " << work.toString(cache) << std::endl;
@@ -999,7 +1002,7 @@ void APT::Solver::Push(Var var, Work work)
    trail.push_back(Trail{var, std::move(work)});
 }
 
-void APT::Solver::UndoOne()
+void Solver::UndoOne()
 {
    auto trailItem = trail.back();
 
@@ -1031,7 +1034,7 @@ void APT::Solver::UndoOne()
    // FIXME: Add the undo handling here once we have watchers.
 }
 
-bool APT::Solver::Pop()
+bool Solver::Pop()
 {
    if (decisionLevel() == 0)
       return false;
@@ -1086,7 +1089,7 @@ bool APT::Solver::Pop()
    return true;
 }
 
-bool APT::Solver::AddWork(Work &&w)
+bool Solver::AddWork(Work &&w)
 {
    if (w.clause->negative)
    {
@@ -1109,7 +1112,7 @@ bool APT::Solver::AddWork(Work &&w)
    return true;
 }
 
-bool APT::Solver::Solve()
+bool Solver::Solve()
 {
    _error->PushToStack();
    DEFER([&]() { _error->MergeWithStack(); });
@@ -1187,7 +1190,7 @@ bool APT::Solver::Solve()
 }
 
 // \brief Apply the selections from the dep cache to the solver
-bool APT::Solver::FromDepCache(pkgDepCache &depcache)
+bool Solver::FromDepCache(pkgDepCache &depcache)
 {
    DefaultRootSetFunc2 rootSet(&cache);
    std::vector<Var> manualPackages;
@@ -1319,7 +1322,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache)
    return true;
 }
 
-bool APT::Solver::ToDepCache(pkgDepCache &depcache) const
+bool Solver::ToDepCache(pkgDepCache &depcache) const
 {
    FastContiguousCacheMap<pkgCache::Package, bool> movedManual(cache);
    pkgDepCache::ActionGroup group(depcache);
@@ -1385,9 +1388,9 @@ bool APT::Solver::ToDepCache(pkgDepCache &depcache) const
 }
 
 // Command-line
-std::string APT::Solver::InternalCliWhy(pkgDepCache &cache, pkgCache::PkgIterator pkg, bool decision)
+std::string Solver::InternalCliWhy(pkgDepCache &cache, pkgCache::PkgIterator pkg, bool decision)
 {
-   APT::Solver solver(cache.GetCache(), cache.GetPolicy(), EDSP::Request::Flags(0));
+   Solver 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));
@@ -1403,3 +1406,4 @@ std::string APT::Solver::InternalCliWhy(pkgDepCache &cache, pkgCache::PkgIterato
       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);
 }
+} // namespace APT::Solver
diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h
index eff2c50d6..1d591686b 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
 {
 
 /**
@@ -67,6 +67,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 { return value != other.value; }
+   constexpr bool operator==(Var const other) const { 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 { return value != other.value; }
+   constexpr bool operator==(Lit const other) const { 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 decision)
+{
+   switch (decision)
+   {
+   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,59 +276,11 @@ using FastContiguousCacheMap = ContiguousCacheMap<K, V, true>;
  */
 class Solver
 {
-   public:
-   enum class LiftedBool : uint8_t;
-   struct Var;
-   struct Lit;
-
    private:
    struct CompareProviders3;
    struct State;
-   struct Clause;
    struct Work;
    struct Trail;
-   friend struct std::hash<APT::Solver::Var>;
-   friend struct std::hash<APT::Solver::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 Type to record depth at. This may very well be a 16-bit
    // unsigned integer, then change Solver::State::LiftedBool to be a
@@ -326,131 +475,6 @@ class Solver
 }; // 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; and we want to generically refer to
- * both packages and versions as variables, hence this class was added.
- *
- */
-struct APT::Solver::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 { return value != other.value; }
-   constexpr bool operator==(Var const other) const { 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 APT::Solver::Lit
-{
-   private:
-   friend struct std::hash<APT::Solver::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(APT::Solver::Var var) : value{static_cast<int32_t>(var.value)} {}
-
-   // Accessors
-   constexpr APT::Solver::Var var() const { return APT::Solver::Var(std::abs(value)); }
-   constexpr bool sign() const { return value < 0; }
-   constexpr APT::Solver::Lit operator~() const { return Lit(-value); }
-
-   // Properties
-   constexpr bool empty() const { return value == 0; }
-   constexpr bool operator!=(Lit const other) const { return value != other.value; }
-   constexpr bool operator==(Lit const other) const { 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 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;
-
-   // 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;
-};
-
-/**
  * \brief A single work item
  *
  * A work item is a positive dependency that still needs to be resolved. Work
@@ -460,7 +484,7 @@ struct APT::Solver::Clause
  * 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;
 
@@ -473,29 +497,18 @@ struct APT::Solver::Work
    // \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::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 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.
  */
-struct APT::Solver::State
+struct APT::Solver::Solver::State
 {
    // \brief The reason for causing this state (invalid for Undefined).
    //
@@ -545,7 +558,7 @@ struct APT::Solver::State
  * 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::Trail
+struct APT::Solver::Solver::Trail
 {
    /// \brief A variable that got assigned True or False. May be reset to Undefined on backtracking.
    Var assigned;
@@ -553,7 +566,7 @@ struct APT::Solver::Trail
    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];
@@ -562,7 +575,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];
 }
@@ -582,22 +595,3 @@ 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); }
 };
-
-constexpr APT::Solver::Lit APT::Solver::Var::operator~() const
-{
-   return ~Lit(*this);
-}
-
-inline APT::Solver::LiftedBool operator~(APT::Solver::LiftedBool decision)
-{
-   switch (decision)
-   {
-   case APT::Solver::LiftedBool::Undefined:
-      return APT::Solver::LiftedBool::Undefined;
-   case APT::Solver::LiftedBool::True:
-      return APT::Solver::LiftedBool::False;
-   case APT::Solver::LiftedBool::False:
-      return APT::Solver::LiftedBool::True;
-   }
-   abort();
-}
diff --git a/cmdline/apt.cc b/cmdline/apt.cc
index 9acde0b32..39ec68e71 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::Solver::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.