From 59b8099d79b5e103585b66279f191f4cb421a770 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Mon, 22 Dec 2025 22:12:33 +0100 Subject: 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 --- apt-pkg/edsp.cc | 2 +- apt-pkg/solver3.cc | 64 +++++---- apt-pkg/solver3.h | 414 ++++++++++++++++++++++++++--------------------------- 3 files changed, 239 insertions(+), 241 deletions(-) (limited to 'apt-pkg') 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 #include +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); static_assert(std::is_trivially_destructible_v); - static_assert(sizeof(APT::Solver::Var) == sizeof(map_pointer)); - static_assert(sizeof(APT::Solver::Var) == sizeof(map_pointer)); + static_assert(sizeof(Var) == sizeof(map_pointer)); + static_assert(sizeof(Var) == sizeof(map_pointer)); // 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 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 &seen) const +std::string Solver::LongWhyStr(Var var, bool decision, const Clause *rclause, std::string prefix, std::unordered_set &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 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 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 struct always_false : std::false_type {}; -namespace APT +namespace APT::Solver { /** @@ -67,6 +67,203 @@ class ContiguousCacheMap template using FastContiguousCacheMap = ContiguousCacheMap; +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 Pkg() const + { + return isVersion() ? 0 : map_pointer{mapPtr()}; + } + // \brief Return the version, if any, otherwise 0. + map_pointer Ver() const + { + return isVersion() ? map_pointer{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; + // 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(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 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 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; */ 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; - friend struct std::hash; - - // \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 @@ -325,131 +474,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 Pkg() const - { - return isVersion() ? 0 : map_pointer{mapPtr()}; - } - // \brief Return the version, if any, otherwise 0. - map_pointer Ver() const - { - return isVersion() ? map_pointer{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; - // 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(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 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 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 * @@ -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; }; -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(*this)[r]; } @@ -582,22 +595,3 @@ struct std::hash std::hash 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(); -} -- cgit v1.2.3-70-g09d2