From 6ae4194b68f04b7724e5f9d3bd19c0b52990ae4f Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Sun, 21 Dec 2025 21:37:11 +0100 Subject: solver3: Introduce a Lit type to hold literals --- apt-pkg/solver3.h | 48 ++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 48 insertions(+) diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h index 45b55d962..97a833b5c 100644 --- a/apt-pkg/solver3.h +++ b/apt-pkg/solver3.h @@ -82,12 +82,14 @@ class Solver enum class Decision : uint16_t; enum class Hint : uint16_t; struct Var; + struct Lit; struct CompareProviders3; struct State; struct Clause; struct Work; struct Solved; friend struct std::hash; + friend struct std::hash; // \brief Groups of works, these are ordered. // @@ -374,6 +376,9 @@ struct APT::Solver::Var 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()) @@ -384,6 +389,36 @@ struct APT::Solver::Var } }; +/** + * \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 * @@ -535,3 +570,16 @@ struct std::hash std::hash hash_value; std::size_t operator()(const APT::Solver::Var &v) const noexcept { return hash_value(v.value); } }; + +// Custom specialization of std::hash can be injected in namespace std. +template <> +struct std::hash +{ + 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); +} -- cgit v1.2.3-70-g09d2 From 1700acb919ce9c495db4dce4003f73751cc9c1f2 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Sun, 21 Dec 2025 21:44:46 +0100 Subject: solver3: Refactor Assume(), Enqueue() from Var to Lit This simplifies the code _slightly_ --- apt-pkg/solver3.cc | 45 +++++++++++++++++++++++---------------------- apt-pkg/solver3.h | 6 +++--- 2 files changed, 26 insertions(+), 25 deletions(-) diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index 4d7e0ff0b..1b3852520 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -557,16 +557,16 @@ bool APT::Solver::Obsolete(pkgCache::PkgIterator pkg, bool AllowManual) const pkgObsolete[pkg] = 2; return true; } -bool APT::Solver::Assume(Var var, bool decision, const Clause *reason) +bool APT::Solver::Assume(Lit lit, const Clause *reason) { choices.push_back(solved.size()); - return Enqueue(var, decision, std::move(reason)); + return Enqueue(lit, std::move(reason)); } -bool APT::Solver::Enqueue(Var var, bool decision, const Clause *reason) +bool APT::Solver::Enqueue(Lit lit, const Clause *reason) { - auto &state = (*this)[var]; - auto decisionCast = decision ? Decision::MUST : Decision::MUSTNOT; + auto &state = (*this)[lit.var()]; + auto decisionCast = lit.sign() ? Decision::MUSTNOT : Decision::MUST; if (state.decision != Decision::NONE) { @@ -575,8 +575,8 @@ bool APT::Solver::Enqueue(Var var, bool decision, const Clause *reason) std::ostringstream err; err << "Unable to satisfy dependencies. Reached two conflicting decisions:" << "\n"; std::unordered_set seen; - err << "1. " << LongWhyStr(var, state.decision == Decision::MUST, state.reason, " ", seen).substr(3) << "\n"; - err << "2. " << LongWhyStr(var, decision, reason, " ", seen).substr(3); + err << "1. " << LongWhyStr(lit.var(), state.decision == Decision::MUST, state.reason, " ", seen).substr(3) << "\n"; + err << "2. " << LongWhyStr(lit.var(), not lit.sign(), reason, " ", seen).substr(3); return _error->Error("%s", err.str().c_str()); } return true; @@ -586,11 +586,12 @@ bool APT::Solver::Enqueue(Var var, bool decision, const Clause *reason) state.depth = depth(); state.reason = reason; + // FIXME: Adjust call to bestReason to use lit if (unlikely(debug >= 1)) - std::cerr << "[" << depth() << "] " << (decision ? "Install" : "Reject") << ":" << var.toString(cache) << " (" << WhyStr(bestReason(reason, var)) << ")\n"; + std::cerr << "[" << depth() << "] " << (lit.sign() ? "Reject" : "Install") << ":" << lit.var().toString(cache) << " (" << WhyStr(bestReason(reason, lit.var())) << ")\n"; - solved.push_back(Solved{var, std::nullopt}); - propQ.push(var); + solved.push_back(Solved{lit.var(), std::nullopt}); + propQ.push(lit.var()); return true; } @@ -613,7 +614,7 @@ bool APT::Solver::Propagate() continue; if (unlikely(debug >= 3)) std::cerr << "Propagate " << var.toString(cache) << " to NOT " << rclause->reason.toString(cache) << " for dep " << const_cast(rclause)->toString(cache) << std::endl; - if (not Enqueue(rclause->reason, false, rclause)) + if (not Enqueue(~rclause->reason, rclause)) return false; } } @@ -643,7 +644,7 @@ bool APT::Solver::Propagate() { // Find the variable that must be chosen and enqueue it as a fact for (auto sol : rclause->solutions) - if ((*this)[sol].decision == Decision::NONE && not Enqueue(sol, true, rclause)) + if ((*this)[sol].decision == Decision::NONE && not Enqueue(sol, rclause)) return false; } continue; @@ -654,7 +655,7 @@ bool APT::Solver::Propagate() if (unlikely(debug >= 3)) std::cerr << "Propagate NOT " << var.toString(cache) << " to " << rclause->reason.toString(cache) << " for dep " << const_cast(rclause)->toString(cache) << std::endl; - if (not Enqueue(rclause->reason, false, rclause)) // Last version invalidated + if (not Enqueue(~rclause->reason, rclause)) // Last version invalidated return false; } } @@ -1069,7 +1070,7 @@ bool APT::Solver::Pop() std::cerr << "Backtracking to choice " << choice.toString(cache) << "\n"; // FIXME: There should be a reason! - if (not choice.empty() && not Enqueue(choice, false, {})) + if (not choice.empty() && not Enqueue(~choice, {})) return false; (*this)[choice].reasonStr = "backtracked"; @@ -1085,7 +1086,7 @@ bool APT::Solver::AddWork(Work &&w) if (w.clause->negative) { for (auto var : w.clause->solutions) - if (not Enqueue(var, false, w.clause)) + if (not Enqueue(~var, w.clause)) return false; } else @@ -1093,7 +1094,7 @@ bool APT::Solver::AddWork(Work &&w) if (unlikely(debug >= 3 && w.clause->optional)) std::cerr << "Enqueuing Recommends " << w.clause->toString(cache) << std::endl; if (w.clause->solutions.size() == 1 && not w.clause->optional) - return Enqueue(w.clause->solutions[0], true, w.clause); + return Enqueue(w.clause->solutions[0], w.clause); w.size = std::count_if(w.clause->solutions.begin(), w.clause->solutions.end(), [this](auto V) { return (*this)[V].decision != Decision::MUSTNOT; }); @@ -1158,7 +1159,7 @@ bool APT::Solver::Solve() } if (unlikely(debug >= 3)) std::cerr << "(try it: " << sol.toString(cache) << ")\n"; - if (not Enqueue(sol, true, item.clause) && not Pop()) + if (not Enqueue(sol, item.clause) && not Pop()) return false; foundSolution = true; break; @@ -1195,7 +1196,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache) bool isPhasing = IsUpgrade && depcache.PhasingApplied(P) && not isForced; for (auto V = P.VersionList(); not V.end(); ++V) if (P.CurrentVer() != V && (depcache.GetCandidateVersion(P) != V || isPhasing)) - if (not Enqueue(Var(V), false, {})) + if (not Enqueue(~Var(V), {})) return false; } } @@ -1215,7 +1216,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache) { if (unlikely(debug >= 1)) std::cerr << "Hold " << P.FullName() << "\n"; - if (P->CurrentVer ? not Enqueue(Var(P.CurrentVer()), true) : not Enqueue(Var(P), false)) + if (P->CurrentVer ? not Enqueue(Var(P.CurrentVer())) : not Enqueue(~Var(P))) return false; } else if (state.Delete() // Normal delete request. @@ -1225,7 +1226,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache) { if (unlikely(debug >= 1)) std::cerr << "Delete " << P.FullName() << "\n"; - if (not Enqueue(Var(P), false)) + if (not Enqueue(~Var(P))) return false; } else if (state.Install() || (state.Keep() && P->CurrentVer)) @@ -1251,7 +1252,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache) if (not isOptional) { // Pre-empt the non-optional requests, as we don't want to queue them, we can just "unit propagate" here. - if (depcache[P].Keep() ? not Enqueue(Var(P), true) : not Enqueue(Var(depcache.GetCandidateVersion(P)), true)) + if (depcache[P].Keep() ? not Enqueue(Var(P)) : not Enqueue(Var(depcache.GetCandidateVersion(P)))) return false; } else @@ -1305,7 +1306,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache) std::stable_sort(manualPackages.begin(), manualPackages.end(), CompareProviders3{cache, policy, {}, *this}); for (auto assumption : manualPackages) { - if (not Assume(assumption, true, {}) || not Propagate()) + if (not Assume(assumption, {}) || not Propagate()) if (not Pop()) abort(); } diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h index 97a833b5c..8310bb1c5 100644 --- a/apt-pkg/solver3.h +++ b/apt-pkg/solver3.h @@ -292,10 +292,10 @@ class Solver Solver(pkgCache &Cache, pkgDepCache::Policy &Policy, EDSP::Request::Flags requestFlags); ~Solver(); - // Assume that the variable is decided as specified. - [[nodiscard]] bool Assume(Var var, bool decision, const Clause *reason = nullptr); + // Assume a literal + [[nodiscard]] bool Assume(Lit lit, const Clause *reason = nullptr); // Enqueue a decision fact - [[nodiscard]] bool Enqueue(Var var, bool decision, const Clause *reason = nullptr); + [[nodiscard]] bool Enqueue(Lit lit, const Clause *reason = nullptr); // \brief Apply the selections from the dep cache to the solver [[nodiscard]] bool FromDepCache(pkgDepCache &depcache); -- cgit v1.2.3-70-g09d2 From 982b94ba9d7615d2b5a6420411c3d41356fdf19a Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Sun, 21 Dec 2025 22:56:13 +0100 Subject: solver3: Implement value(Lit) and use it --- apt-pkg/solver3.cc | 41 +++++++++++++++++++++++------------------ apt-pkg/solver3.h | 19 ++++++++++++++++++- 2 files changed, 41 insertions(+), 19 deletions(-) diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index 1b3852520..0779d2c7d 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -299,21 +299,26 @@ inline APT::Solver::Var APT::Solver::bestReason(APT::Solver::Clause const *claus if (clause->reason == var) for (auto choice : clause->solutions) { - if (clause->negative && (*this)[choice].decision == Decision::MUST) + if (clause->negative && value(choice) == Decision::MUST) return choice; - if (not clause->negative && (*this)[choice].decision == Decision::MUSTNOT) + if (not clause->negative && value(choice) == Decision::MUSTNOT) return choice; } return clause->reason; } +inline APT::Solver::Decision APT::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::vector out; while (not reason.empty()) { - if ((*this)[reason].decision == Decision::MUSTNOT) + if (value(reason) == Decision::MUSTNOT) out.push_back(std::string("not ") + reason.toString(cache)); else out.push_back(reason.toString(cache)); @@ -362,10 +367,10 @@ std::string APT::Solver::LongWhyStr(Var var, bool decision, const Clause *rclaus if (choice == skip) continue; - if ((*this)[choice].decision == Decision::NONE) + if (value(choice) == Decision::NONE) out << prefix << "- " << choice.toString(cache) << " is undecided\n"; else - out << prefix << "- " << LongWhyStr(choice, (*this)[choice].decision == Decision::MUST, (*this)[choice].reason, prefix + " ", seen).substr(prefix.size() + 2); + out << prefix << "- " << LongWhyStr(choice, value(choice) == Decision::MUST, (*this)[choice].reason, prefix + " ", seen).substr(prefix.size() + 2); } }; @@ -386,7 +391,7 @@ std::string APT::Solver::LongWhyStr(Var var, bool decision, const Clause *rclaus // We could be called with a decision we tried to make but failed due to a conflict; // this checks if it is the real decision. - if ((*this)[var].decision != Decision::NONE && decision == ((*this)[var].decision == Decision::MUST) && (*this)[var].reason == rclause) + if (value(var) != Decision::NONE && decision == (value(var) == Decision::MUST) && (*this)[var].reason == rclause) { // If we have seen the real decision before; we dont't need to print it again. if (seen.find(var) != seen.end()) @@ -602,7 +607,7 @@ bool APT::Solver::Propagate() { Var var = propQ.front(); propQ.pop(); - if ((*this)[var].decision == Decision::MUST) + if (value(var) == Decision::MUST) { Discover(var); for (auto &clause : (*this)[var].clauses) @@ -618,19 +623,19 @@ bool APT::Solver::Propagate() return false; } } - else if ((*this)[var].decision == Decision::MUSTNOT) + else if (value(var) == Decision::MUSTNOT) { for (auto rclause : (*this)[var].rclauses) { if (rclause->negative || rclause->reason.empty()) continue; - if ((*this)[rclause->reason].decision == Decision::MUSTNOT) + if (value(rclause->reason) == Decision::MUSTNOT) continue; auto count = std::count_if(rclause->solutions.begin(), rclause->solutions.end(), [this](auto var) - { return (*this)[var].decision != Decision::MUSTNOT; }); + { return value(var) != Decision::MUSTNOT; }); - if (count == 1 && (*this)[rclause->reason].decision == Decision::MUST) + if (count == 1 && value(rclause->reason) == Decision::MUST) { if (unlikely(debug >= 3)) std::cerr << "Propagate NOT " << var.toString(cache) << " to unit clause " << rclause->toString(cache); @@ -644,7 +649,7 @@ bool APT::Solver::Propagate() { // Find the variable that must be chosen and enqueue it as a fact for (auto sol : rclause->solutions) - if ((*this)[sol].decision == Decision::NONE && not Enqueue(sol, rclause)) + if (value(sol) == Decision::NONE && not Enqueue(sol, rclause)) return false; } continue; @@ -815,7 +820,7 @@ void APT::Solver::Discover(Var var) // Recursively discover everything else that is not already FALSE by fact (MUSTNOT at depth 0) for (auto const &clause : state.clauses) for (auto const &var : clause->solutions) - if ((*this)[var].decision != Decision::MUSTNOT || (*this)[var].depth > 0) + if (value(var) != Decision::MUSTNOT || (*this)[var].depth > 0) discoverQ.push(var); } } @@ -1097,7 +1102,7 @@ bool APT::Solver::AddWork(Work &&w) return Enqueue(w.clause->solutions[0], w.clause); w.size = std::count_if(w.clause->solutions.begin(), w.clause->solutions.end(), [this](auto V) - { return (*this)[V].decision != Decision::MUSTNOT; }); + { return value(V) != Decision::MUSTNOT; }); work.push_back(std::move(w)); std::push_heap(work.begin(), work.end()); } @@ -1134,7 +1139,7 @@ bool APT::Solver::Solve() solved.push_back(Solved{Var(), item}); if (std::any_of(item.clause->solutions.begin(), item.clause->solutions.end(), [this](auto ver) - { return (*this)[ver].decision == Decision::MUST; })) + { return value(ver) == Decision::MUST; })) { if (unlikely(debug >= 2)) std::cerr << "ELIDED " << item.toString(cache) << std::endl; @@ -1147,7 +1152,7 @@ bool APT::Solver::Solve() bool foundSolution = false; for (auto &sol : item.clause->solutions) { - if ((*this)[sol].decision == Decision::MUSTNOT) + if (value(sol) == Decision::MUSTNOT) { if (unlikely(debug >= 3)) std::cerr << "(existing conflict: " << sol.toString(cache) << ")\n"; @@ -1322,11 +1327,11 @@ bool APT::Solver::ToDepCache(pkgDepCache &depcache) const { depcache[P].Marked = 0; depcache[P].Garbage = 0; - if ((*this)[P].decision == Decision::MUST) + if (value(Var(P)) == Decision::MUST) { pkgCache::VerIterator cand; for (auto V = P.VersionList(); cand.end() && not V.end(); V++) - if ((*this)[V].decision == Decision::MUST) + if (value(Var(V)) == Decision::MUST) cand = V; auto reasonClause = (*this)[cand].reason; diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h index 8310bb1c5..235717d86 100644 --- a/apt-pkg/solver3.h +++ b/apt-pkg/solver3.h @@ -79,10 +79,12 @@ using FastContiguousCacheMap = ContiguousCacheMap; */ class Solver { + public: enum class Decision : uint16_t; - enum class Hint : uint16_t; struct Var; struct Lit; + + private: struct CompareProviders3; struct State; struct Clause; @@ -277,6 +279,7 @@ class Solver return static_cast(choices.size()); } inline Var bestReason(Clause const *clause, Var var) const; + inline Decision value(Lit lit) const; public: // \brief Create a new decision level. @@ -583,3 +586,17 @@ constexpr APT::Solver::Lit APT::Solver::Var::operator~() const { return ~Lit(*this); } + +inline APT::Solver::Decision operator~(APT::Solver::Decision decision) +{ + switch (decision) + { + case APT::Solver::Decision::NONE: + return APT::Solver::Decision::NONE; + case APT::Solver::Decision::MUST: + return APT::Solver::Decision::MUSTNOT; + case APT::Solver::Decision::MUSTNOT: + return APT::Solver::Decision::MUST; + } + abort(); +} -- cgit v1.2.3-70-g09d2 From e456e83b4a3986b672dbe98ed9b508606f2eb867 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Sun, 21 Dec 2025 23:16:30 +0100 Subject: solver3: Rename Decision to LiftedBool MUST becomes True, MUSTNOT becomes False, and NONE becomes Undefined. --- apt-pkg/solver3.cc | 62 +++++++++++++++++++++++++++--------------------------- apt-pkg/solver3.h | 32 ++++++++++++++-------------- 2 files changed, 47 insertions(+), 47 deletions(-) diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index 0779d2c7d..afed249e5 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -213,7 +213,7 @@ APT::Solver::Solver(pkgCache &cache, pkgDepCache::Policy &policy, EDSP::Request: static_assert(sizeof(APT::Solver::Var) == sizeof(map_pointer)); static_assert(sizeof(APT::Solver::Var) == sizeof(map_pointer)); // Root state is "true". - rootState->decision = Decision::MUST; + rootState->decision = LiftedBool::True; } APT::Solver::~Solver() = default; @@ -299,15 +299,15 @@ inline APT::Solver::Var APT::Solver::bestReason(APT::Solver::Clause const *claus if (clause->reason == var) for (auto choice : clause->solutions) { - if (clause->negative && value(choice) == Decision::MUST) + if (clause->negative && value(choice) == LiftedBool::True) return choice; - if (not clause->negative && value(choice) == Decision::MUSTNOT) + if (not clause->negative && value(choice) == LiftedBool::False) return choice; } return clause->reason; } -inline APT::Solver::Decision APT::Solver::value(Lit lit) const +inline APT::Solver::LiftedBool APT::Solver::value(Lit lit) const { return lit.sign() ? ~(*this)[lit.var()].decision : (*this)[lit.var()].decision; } @@ -318,7 +318,7 @@ std::string APT::Solver::WhyStr(Var reason) const std::vector out; while (not reason.empty()) { - if (value(reason) == Decision::MUSTNOT) + if (value(reason) == LiftedBool::False) out.push_back(std::string("not ") + reason.toString(cache)); else out.push_back(reason.toString(cache)); @@ -367,10 +367,10 @@ std::string APT::Solver::LongWhyStr(Var var, bool decision, const Clause *rclaus if (choice == skip) continue; - if (value(choice) == Decision::NONE) + if (value(choice) == LiftedBool::Undefined) out << prefix << "- " << choice.toString(cache) << " is undecided\n"; else - out << prefix << "- " << LongWhyStr(choice, value(choice) == Decision::MUST, (*this)[choice].reason, prefix + " ", seen).substr(prefix.size() + 2); + out << prefix << "- " << LongWhyStr(choice, value(choice) == LiftedBool::True, (*this)[choice].reason, prefix + " ", seen).substr(prefix.size() + 2); } }; @@ -391,7 +391,7 @@ std::string APT::Solver::LongWhyStr(Var var, bool decision, const Clause *rclaus // We could be called with a decision we tried to make but failed due to a conflict; // this checks if it is the real decision. - if (value(var) != Decision::NONE && decision == (value(var) == Decision::MUST) && (*this)[var].reason == rclause) + if (value(var) != LiftedBool::Undefined && decision == (value(var) == LiftedBool::True) && (*this)[var].reason == rclause) { // If we have seen the real decision before; we dont't need to print it again. if (seen.find(var) != seen.end()) @@ -433,7 +433,7 @@ std::string APT::Solver::LongWhyStr(Var var, bool decision, const Clause *rclaus { if ((it + 1) == path.rend() || seen.find(*(it + 1)) == seen.end()) { - out << prefix << (i == 1 ? "" : "1-") << i << ". " << printSelection(*it, state.decision == Decision::MUST) << " as above\n"; + out << prefix << (i == 1 ? "" : "1-") << i << ". " << printSelection(*it, state.decision == LiftedBool::True) << " as above\n"; } continue; } @@ -442,10 +442,10 @@ std::string APT::Solver::LongWhyStr(Var var, bool decision, const Clause *rclaus { out << prefix << std::setw(w) << i << ". " << state.reason->toString(cache, true) << "\n"; if (state.reason->solutions.size() > 1) - out << prefix << std::setw(w) << " " << " [selected " << it->toString(cache) << " for " << (state.decision == Decision::MUST ? "install" : "remove") << "]\n"; + out << prefix << std::setw(w) << " " << " [selected " << it->toString(cache) << " for " << (state.decision == LiftedBool::True ? "install" : "remove") << "]\n"; } else - out << prefix << std::setw(w) << i << ". " << printSelection(*it, state.decision == Decision::MUST) << "\n"; + out << prefix << std::setw(w) << i << ". " << printSelection(*it, state.decision == LiftedBool::True) << "\n"; } // Print the leaf. We can't have the leaf in the path because we might be called for an attempted decision @@ -571,16 +571,16 @@ bool APT::Solver::Assume(Lit lit, const Clause *reason) bool APT::Solver::Enqueue(Lit lit, const Clause *reason) { auto &state = (*this)[lit.var()]; - auto decisionCast = lit.sign() ? Decision::MUSTNOT : Decision::MUST; + auto decisionCast = lit.sign() ? LiftedBool::False : LiftedBool::True; - if (state.decision != Decision::NONE) + if (state.decision != LiftedBool::Undefined) { if (state.decision != decisionCast) { std::ostringstream err; err << "Unable to satisfy dependencies. Reached two conflicting decisions:" << "\n"; std::unordered_set seen; - err << "1. " << LongWhyStr(lit.var(), state.decision == Decision::MUST, state.reason, " ", seen).substr(3) << "\n"; + err << "1. " << LongWhyStr(lit.var(), state.decision == LiftedBool::True, state.reason, " ", seen).substr(3) << "\n"; err << "2. " << LongWhyStr(lit.var(), not lit.sign(), reason, " ", seen).substr(3); return _error->Error("%s", err.str().c_str()); } @@ -607,7 +607,7 @@ bool APT::Solver::Propagate() { Var var = propQ.front(); propQ.pop(); - if (value(var) == Decision::MUST) + if (value(var) == LiftedBool::True) { Discover(var); for (auto &clause : (*this)[var].clauses) @@ -623,19 +623,19 @@ bool APT::Solver::Propagate() return false; } } - else if (value(var) == Decision::MUSTNOT) + else if (value(var) == LiftedBool::False) { for (auto rclause : (*this)[var].rclauses) { if (rclause->negative || rclause->reason.empty()) continue; - if (value(rclause->reason) == Decision::MUSTNOT) + if (value(rclause->reason) == LiftedBool::False) continue; auto count = std::count_if(rclause->solutions.begin(), rclause->solutions.end(), [this](auto var) - { return value(var) != Decision::MUSTNOT; }); + { return value(var) != LiftedBool::False; }); - if (count == 1 && value(rclause->reason) == Decision::MUST) + if (count == 1 && value(rclause->reason) == LiftedBool::True) { if (unlikely(debug >= 3)) std::cerr << "Propagate NOT " << var.toString(cache) << " to unit clause " << rclause->toString(cache); @@ -649,7 +649,7 @@ bool APT::Solver::Propagate() { // Find the variable that must be chosen and enqueue it as a fact for (auto sol : rclause->solutions) - if (value(sol) == Decision::NONE && not Enqueue(sol, rclause)) + if (value(sol) == LiftedBool::Undefined && not Enqueue(sol, rclause)) return false; } continue; @@ -817,10 +817,10 @@ void APT::Solver::Discover(Var var) } } - // Recursively discover everything else that is not already FALSE by fact (MUSTNOT at depth 0) + // Recursively discover everything else that is not already FALSE by fact (False at depth 0) for (auto const &clause : state.clauses) for (auto const &var : clause->solutions) - if (value(var) != Decision::MUSTNOT || (*this)[var].depth > 0) + if (value(var) != LiftedBool::False || (*this)[var].depth > 0) discoverQ.push(var); } } @@ -1011,7 +1011,7 @@ void APT::Solver::UndoOne() if (unlikely(debug >= 4)) std::cerr << "Unassign " << solvedItem.assigned.toString(cache) << "\n"; auto &state = (*this)[solvedItem.assigned]; - state.decision = Decision::NONE; + state.decision = LiftedBool::Undefined; state.reason = nullptr; state.reasonStr = nullptr; state.depth = 0; @@ -1102,7 +1102,7 @@ bool APT::Solver::AddWork(Work &&w) return Enqueue(w.clause->solutions[0], w.clause); w.size = std::count_if(w.clause->solutions.begin(), w.clause->solutions.end(), [this](auto V) - { return value(V) != Decision::MUSTNOT; }); + { return value(V) != LiftedBool::False; }); work.push_back(std::move(w)); std::push_heap(work.begin(), work.end()); } @@ -1139,7 +1139,7 @@ bool APT::Solver::Solve() solved.push_back(Solved{Var(), item}); if (std::any_of(item.clause->solutions.begin(), item.clause->solutions.end(), [this](auto ver) - { return value(ver) == Decision::MUST; })) + { return value(ver) == LiftedBool::True; })) { if (unlikely(debug >= 2)) std::cerr << "ELIDED " << item.toString(cache) << std::endl; @@ -1152,7 +1152,7 @@ bool APT::Solver::Solve() bool foundSolution = false; for (auto &sol : item.clause->solutions) { - if (value(sol) == Decision::MUSTNOT) + if (value(sol) == LiftedBool::False) { if (unlikely(debug >= 3)) std::cerr << "(existing conflict: " << sol.toString(cache) << ")\n"; @@ -1327,11 +1327,11 @@ bool APT::Solver::ToDepCache(pkgDepCache &depcache) const { depcache[P].Marked = 0; depcache[P].Garbage = 0; - if (value(Var(P)) == Decision::MUST) + if (value(Var(P)) == LiftedBool::True) { pkgCache::VerIterator cand; for (auto V = P.VersionList(); cand.end() && not V.end(); V++) - if (value(Var(V)) == Decision::MUST) + if (value(Var(V)) == LiftedBool::True) cand = V; auto reasonClause = (*this)[cand].reason; @@ -1395,11 +1395,11 @@ std::string APT::Solver::InternalCliWhy(pkgDepCache &cache, pkgCache::PkgIterato return ""; std::unordered_set seen; std::string buf; - if (solver[Var(pkg)].decision == Decision::NONE) + if (solver[Var(pkg)].decision == LiftedBool::Undefined) return strprintf(buf, "%s is undecided\n", pkg.FullName().c_str()), buf; - if (decision && solver[Var(pkg)].decision != Decision::MUST) + if (decision && solver[Var(pkg)].decision != LiftedBool::True) return strprintf(buf, "%s is not actually marked for install\n", pkg.FullName().c_str()), buf; - if (not decision && solver[Var(pkg)].decision == Decision::MUST) + if (not decision && solver[Var(pkg)].decision == LiftedBool::True) return strprintf(buf, "%s is actually marked for install\n", pkg.FullName().c_str()), buf; return solver.LongWhyStr(Var(pkg), decision, solver[Var(pkg)].reason, "", seen); } diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h index 235717d86..c4b87e9fe 100644 --- a/apt-pkg/solver3.h +++ b/apt-pkg/solver3.h @@ -80,7 +80,7 @@ using FastContiguousCacheMap = ContiguousCacheMap; class Solver { public: - enum class Decision : uint16_t; + enum class LiftedBool : uint8_t; struct Var; struct Lit; @@ -134,7 +134,7 @@ class Solver }; // \brief Type to record depth at. This may very well be a 16-bit - // unsigned integer, then change Solver::State::Decision to be a + // unsigned integer, then change Solver::State::LiftedBool to be a // uint16_t class enum as well to get a more compact space. using depth_type = unsigned int; @@ -279,7 +279,7 @@ class Solver return static_cast(choices.size()); } inline Var bestReason(Clause const *clause, Var var) const; - inline Decision value(Lit lit) const; + inline LiftedBool value(Lit lit) const; public: // \brief Create a new decision level. @@ -484,14 +484,14 @@ struct APT::Solver::Work }; // \brief This essentially describes the install state in RFC2119 terms. -enum class APT::Solver::Decision : uint16_t +enum class APT::Solver::LiftedBool : uint8_t { // \brief We have not made a choice about the package yet - NONE, + Undefined, // \brief We need to install this package - MUST, + True, // \brief We cannot install this package (need conflicts with it) - MUSTNOT, + False, }; /** @@ -502,7 +502,7 @@ enum class APT::Solver::Decision : uint16_t */ struct APT::Solver::State { - // \brief The reason for causing this state (invalid for NONE). + // \brief The reason for causing this state (invalid for Undefined). // // Rejects may have been caused by a later state. Consider we select // between x1 and x2 in depth = N. If we now find dependencies of x1 @@ -521,7 +521,7 @@ struct APT::Solver::State depth_type depth{0}; // \brief This essentially describes the install state in RFC2119 terms. - Decision decision{Decision::NONE}; + LiftedBool decision{LiftedBool::Undefined}; // \brief Flags. struct @@ -587,16 +587,16 @@ constexpr APT::Solver::Lit APT::Solver::Var::operator~() const return ~Lit(*this); } -inline APT::Solver::Decision operator~(APT::Solver::Decision decision) +inline APT::Solver::LiftedBool operator~(APT::Solver::LiftedBool decision) { switch (decision) { - case APT::Solver::Decision::NONE: - return APT::Solver::Decision::NONE; - case APT::Solver::Decision::MUST: - return APT::Solver::Decision::MUSTNOT; - case APT::Solver::Decision::MUSTNOT: - return APT::Solver::Decision::MUST; + 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 From 93675680fca31004d5ea9e011d025c0ff189fc81 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Mon, 22 Dec 2025 18:14:38 +0100 Subject: solver3: Rename key concepts to MiniSAT names This should make it easier for people with MiniSAT knowledge to onboard themselves to the solver. --- apt-pkg/solver3.cc | 54 +++++++++++++++++++++++++-------------------------- apt-pkg/solver3.h | 57 +++++++++++++++++++++++++++--------------------------- 2 files changed, 56 insertions(+), 55 deletions(-) diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index afed249e5..6f84a11a8 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -209,7 +209,7 @@ 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(std::is_trivially_destructible_v); static_assert(sizeof(APT::Solver::Var) == sizeof(map_pointer)); static_assert(sizeof(APT::Solver::Var) == sizeof(map_pointer)); // Root state is "true". @@ -564,7 +564,7 @@ bool APT::Solver::Obsolete(pkgCache::PkgIterator pkg, bool AllowManual) const } bool APT::Solver::Assume(Lit lit, const Clause *reason) { - choices.push_back(solved.size()); + trailLim.push_back(trail.size()); return Enqueue(lit, std::move(reason)); } @@ -588,14 +588,14 @@ bool APT::Solver::Enqueue(Lit lit, const Clause *reason) } state.decision = decisionCast; - state.depth = depth(); + state.depth = decisionLevel(); state.reason = reason; // FIXME: Adjust call to bestReason to use lit if (unlikely(debug >= 1)) - std::cerr << "[" << depth() << "] " << (lit.sign() ? "Reject" : "Install") << ":" << lit.var().toString(cache) << " (" << WhyStr(bestReason(reason, lit.var())) << ")\n"; + std::cerr << "[" << decisionLevel() << "] " << (lit.sign() ? "Reject" : "Install") << ":" << lit.var().toString(cache) << " (" << WhyStr(bestReason(reason, lit.var())) << ")\n"; - solved.push_back(Solved{lit.var(), std::nullopt}); + trail.push_back(Trail{lit.var(), std::nullopt}); propQ.push(lit.var()); return true; @@ -611,7 +611,7 @@ bool APT::Solver::Propagate() { Discover(var); for (auto &clause : (*this)[var].clauses) - if (not AddWork(Work{clause.get(), depth()})) + if (not AddWork(Work{clause.get(), decisionLevel()})) return false; for (auto rclause : (*this)[var].rclauses) { @@ -642,7 +642,7 @@ bool APT::Solver::Propagate() if (rclause->optional) { // Enqueue duplicated item, this will ensure we see it at the correct time - if (not AddWork(Work{rclause, depth()})) + if (not AddWork(Work{rclause, decisionLevel()})) return false; } else @@ -995,29 +995,29 @@ void APT::Solver::Push(Var var, Work work) if (unlikely(debug >= 2)) std::cerr << "Trying choice for " << work.toString(cache) << std::endl; - choices.push_back(solved.size()); - solved.push_back(Solved{var, std::move(work)}); + trailLim.push_back(trail.size()); + trail.push_back(Trail{var, std::move(work)}); } void APT::Solver::UndoOne() { - auto solvedItem = solved.back(); + auto trailItem = trail.back(); if (unlikely(debug >= 4)) std::cerr << "Undoing a single decision\n"; - if (not solvedItem.assigned.empty()) + if (not trailItem.assigned.empty()) { if (unlikely(debug >= 4)) - std::cerr << "Unassign " << solvedItem.assigned.toString(cache) << "\n"; - auto &state = (*this)[solvedItem.assigned]; + std::cerr << "Unassign " << trailItem.assigned.toString(cache) << "\n"; + auto &state = (*this)[trailItem.assigned]; state.decision = LiftedBool::Undefined; state.reason = nullptr; state.reasonStr = nullptr; state.depth = 0; } - if (auto work = solvedItem.work) + if (auto work = trailItem.work) { if (unlikely(debug >= 4)) std::cerr << "Adding work item " << work->toString(cache) << std::endl; @@ -1026,14 +1026,14 @@ void APT::Solver::UndoOne() abort(); } - solved.pop_back(); + trail.pop_back(); // FIXME: Add the undo handling here once we have watchers. } bool APT::Solver::Pop() { - if (depth() == 0) + if (decisionLevel() == 0) return false; time_t now = time(nullptr); @@ -1049,15 +1049,15 @@ bool APT::Solver::Pop() _error->Discard(); // Assume() actually failed to enqueue anything, abort here - if (choices.back() == solved.size()) + if (trailLim.back() == trail.size()) { - choices.pop_back(); + trailLim.pop_back(); return true; } - assert(choices.back() < solved.size()); - int itemsToUndo = solved.size() - choices.back(); - auto choice = solved[choices.back()].assigned; + assert(trailLim.back() < trail.size()); + int itemsToUndo = trail.size() - trailLim.back(); + auto choice = trail[trailLim.back()].assigned; for (; itemsToUndo; --itemsToUndo) UndoOne(); @@ -1065,9 +1065,9 @@ bool APT::Solver::Pop() // We need to remove any work that is at a higher depth. // FIXME: We should just mark the entries as erased and only do a compaction // of the heap once we have a lot of erased entries in it. - choices.pop_back(); + trailLim.pop_back(); work.erase(std::remove_if(work.begin(), work.end(), [this](Work &w) -> bool - { return w.depth > depth() || w.erased; }), + { return w.depth > decisionLevel() || w.erased; }), work.end()); std::make_heap(work.begin(), work.end()); @@ -1136,7 +1136,7 @@ bool APT::Solver::Solve() } auto item = std::move(work.back()); work.pop_back(); - solved.push_back(Solved{Var(), item}); + trail.push_back(Trail{Var(), item}); if (std::any_of(item.clause->solutions.begin(), item.clause->solutions.end(), [this](auto ver) { return value(ver) == LiftedBool::True; })) @@ -1265,7 +1265,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache) Clause w{Var(), Group, isOptional}; w.solutions.push_back(Var(P)); auto insertedW = RegisterClause(std::move(w)); - if (insertedW && not AddWork(Work{insertedW, depth()})) + if (insertedW && not AddWork(Work{insertedW, decisionLevel()})) return false; if (not isAuto) @@ -1281,7 +1281,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache) shortcircuit.solutions.push_back(Var(V)); std::stable_sort(shortcircuit.solutions.begin(), shortcircuit.solutions.end(), CompareProviders3{cache, policy, P, *this}); auto insertedShort = RegisterClause(std::move(shortcircuit)); - if (insertedShort && not AddWork(Work{insertedShort, depth()})) + if (insertedShort && not AddWork(Work{insertedShort, decisionLevel()})) return false; // Discovery here is needed so the shortcircuit clause can actually become unit. @@ -1300,7 +1300,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache) if (unlikely(debug >= 1)) std::cerr << "Install essential package " << P << std::endl; auto inserted = RegisterClause(std::move(w)); - if (inserted && not AddWork(Work{inserted, depth()})) + if (inserted && not AddWork(Work{inserted, decisionLevel()})) return false; } } diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h index c4b87e9fe..eff2c50d6 100644 --- a/apt-pkg/solver3.h +++ b/apt-pkg/solver3.h @@ -89,7 +89,7 @@ class Solver struct State; struct Clause; struct Work; - struct Solved; + struct Trail; friend struct std::hash; friend struct std::hash; @@ -202,30 +202,25 @@ class Solver // \brief Heap of the remaining work. // - // We are using an std::vector with std::make_heap(), std::push_heap(), - // and std::pop_heap() rather than a priority_queue because we need to - // be able to iterate over the queued work and see if a choice would - // invalidate any work. + // In contrast to MiniSAT which picks undecided literals and decides them, + // we keep track of unsolved active clauses in a priority queue. This allows + // us to for example, solve Depends before Recommends (see Group). heap work; - // \brief Backlog of solved work. - // - // Solved work may become invalidated when backtracking, so store it - // here to revisit it later. This is similar to what MiniSAT calls the - // trail; one distinction is that we have both literals and our work - // queue to be concerned about - std::vector solved; + /// \brief Trail of assignments done, and clauses solved. + /// + /// Record past assignments and solved clauses such that we can revert them when + /// backtracking. + std::vector trail; + + /// \brief Separator indices for different decision levels in trail + std::vector trailLim{}; // \brief Propagation queue std::queue propQ; // \brief Discover variables std::queue discoverQ; - // \brief Current decision level. - // - // This is an index into the solved vector. - std::vector choices{}; - // \brief The time we called Solve() time_t startTime{}; @@ -273,10 +268,10 @@ class Solver // \brief Propagate all pending propagations [[nodiscard]] bool Propagate(); - // \brief Return the current depth (choices.size() with casting) - depth_type depth() + // \brief Return the current depth (.size() with casting) + depth_type decisionLevel() { - return static_cast(choices.size()); + return static_cast(trailLim.size()); } inline Var bestReason(Clause const *clause, Var var) const; inline LiftedBool value(Lit lit) const; @@ -286,7 +281,7 @@ class Solver void Push(Var var, Work work); // \brief Revert to the previous decision level. [[nodiscard]] bool Pop(); - // \brief Undo a single assignment / solved work item + // \brief Undo a single assignment / trail work item void UndoOne(); // \brief Add work to our work queue. [[nodiscard]] bool AddWork(Work &&work); @@ -472,7 +467,7 @@ struct APT::Solver::Work // \brief The depth at which the item has been added depth_type depth; - // Number of valid choices + /// Number of valid choices at insertion time size_t size{0}; // \brief This item should be removed from the queue. @@ -539,16 +534,22 @@ struct APT::Solver::State }; /** - * \brief A solved item. + * \brief A trail item. + * + * In MiniSAT, a trail item is an assigned literal. However, we store an assigned variable instead, + * since the assignment is still recorded when we need to access the trail; there does not appear + * to be a substantial value in recording the sign here; but it produces a risk for a disagreement + * between the actual state and the sign recorded in the trail. * - * Here we keep track of solved clauses and variable assignments such that we can easily undo - * them. + * In addition to MiniSAT's trail, we also need to keep a trail of solved Work items; that is + * clauses that were being solved, as when undoing the trail, we need to mark those clauses + * active again by putting them back on the work heap. */ -struct APT::Solver::Solved +struct APT::Solver::Trail { - // \brief A variable that has been assigned. We store this as a reason (FIXME: Rename Var to Var) + /// \brief A variable that got assigned True or False. May be reset to Undefined on backtracking. Var assigned; - // \brief A work item that has been solved. This needs to be put back on the queue. + /// \brief A work item (a clause) that was solved. Needs to be put back on the work heap on backtracking. std::optional work; }; -- cgit v1.2.3-70-g09d2 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 +++++++++++++++++++++---------------------- cmdline/apt.cc | 2 +- debian/libapt-pkg7.0.symbols | 2 +- 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 #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(); -} 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 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, std::allocator > 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. -- cgit v1.2.3-70-g09d2 From e92750f895af0e957d297c17149878235467cca1 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Mon, 22 Dec 2025 22:33:12 +0100 Subject: solver3: Extract DependencySolver Extract almost all dependency logic into a subclass --- apt-pkg/edsp.cc | 2 +- apt-pkg/solver3.cc | 48 +++++++++++------ apt-pkg/solver3.h | 154 +++++++++++++++++++++++++++++------------------------ cmdline/apt.cc | 2 +- 4 files changed, 117 insertions(+), 89 deletions(-) diff --git a/apt-pkg/edsp.cc b/apt-pkg/edsp.cc index a2f2e0c00..2d7fdcc3c 100644 --- a/apt-pkg/edsp.cc +++ b/apt-pkg/edsp.cc @@ -796,7 +796,7 @@ bool EDSP::ResolveExternal(const char* const solver, pkgDepCache &Cache, unsigned int const flags, OpProgress *Progress) { if (strstr(solver, "3.") == solver) { - APT::Solver::Solver s(Cache.GetCache(), Cache.GetPolicy(), (EDSP::Request::Flags)flags); + APT::Solver::DependencySolver s(Cache.GetCache(), Cache.GetPolicy(), (EDSP::Request::Flags)flags); FileFd output; bool res = true; if (Progress != NULL) diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index 50bef7b9f..ec33cc1f6 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -47,7 +47,7 @@ struct Solver::CompareProviders3 /*{{{*/ pkgCache &Cache; pkgDepCache::Policy &Policy; pkgCache::PkgIterator const Pkg; - APT::Solver::Solver &Solver; + APT::Solver::DependencySolver &Solver; pkgCache::VerIterator bestVersion(pkgCache::PkgIterator pkg) { @@ -199,16 +199,30 @@ class DefaultRootSetFunc2 : public pkgDepCache::DefaultRootSetFunc }; // FIXME: DEDUP with pkgDepCache. /*}}}*/ -Solver::Solver(pkgCache &cache, pkgDepCache::Policy &policy, EDSP::Request::Flags requestFlags) +Solver::Solver(pkgCache &cache) : cache(cache), - policy(policy), rootState(new State), pkgStates(cache), - verStates(cache), + verStates(cache) +{ + // Ensure trivially + static_assert(std::is_trivially_destructible_v); + static_assert(std::is_trivially_destructible_v); + static_assert(sizeof(Var) == sizeof(map_pointer)); + static_assert(sizeof(Var) == sizeof(map_pointer)); + // Root state is "true". + rootState->decision = LiftedBool::True; +} + +Solver::~Solver() = default; + +DependencySolver::DependencySolver(pkgCache &cache, pkgDepCache::Policy &policy, EDSP::Request::Flags requestFlags) + : Solver(cache), + policy(policy), + requestFlags(requestFlags), pkgObsolete(cache), priorities(cache), - candidates(cache), - requestFlags(requestFlags) + candidates(cache) { // Ensure trivially static_assert(std::is_trivially_destructible_v); @@ -219,7 +233,7 @@ Solver::Solver(pkgCache &cache, pkgDepCache::Policy &policy, EDSP::Request::Flag rootState->decision = LiftedBool::True; } -Solver::~Solver() = default; +DependencySolver::~DependencySolver() = default; // This function determines if a work item is less important than another. bool Solver::Work::operator<(Solver::Work const &b) const @@ -501,7 +515,7 @@ std::string Solver::LongWhyStr(Var var, bool decision, const Clause *rclause, st // 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 Solver::ObsoletedByNewerSourceVersion(pkgCache::VerIterator cand) const +bool DependencySolver::ObsoletedByNewerSourceVersion(pkgCache::VerIterator cand) const { const auto pkg = cand.ParentPkg(); const int candPriority = GetPriority(cand); @@ -528,7 +542,7 @@ bool Solver::ObsoletedByNewerSourceVersion(pkgCache::VerIterator cand) const return false; } -bool Solver::Obsolete(pkgCache::PkgIterator pkg, bool AllowManual) const +bool DependencySolver::Obsolete(pkgCache::PkgIterator pkg, bool AllowManual) const { if ((*this)[pkg].flags.manual && not AllowManual) return false; @@ -688,7 +702,7 @@ static bool SameOrGroup(pkgCache::DepIterator a, pkgCache::DepIterator b) return not(a->CompareOp & pkgCache::Dep::Or) && not(b->CompareOp & pkgCache::Dep::Or); } -const Clause *Solver::RegisterClause(Clause &&clause) +const Clause *DependencySolver::RegisterClause(Clause &&clause) { auto &clauses = (*this)[clause.reason].clauses; pkgCache::DepIterator dep(cache, clause.dep); @@ -753,7 +767,7 @@ const Clause *Solver::RegisterClause(Clause &&clause) return inserted.get(); } -void Solver::Discover(Var var) +void DependencySolver::Discover(Var var) { assert(discoverQ.empty()); discoverQ.push(var); @@ -828,7 +842,7 @@ void Solver::Discover(Var var) } } -void Solver::RegisterCommonDependencies(pkgCache::PkgIterator Pkg) +void DependencySolver::RegisterCommonDependencies(pkgCache::PkgIterator Pkg) { for (auto dep = Pkg.VersionList().DependsList(); not dep.end();) { @@ -855,7 +869,7 @@ void Solver::RegisterCommonDependencies(pkgCache::PkgIterator Pkg) } } -Clause Solver::TranslateOrGroup(pkgCache::DepIterator start, pkgCache::DepIterator end, Var reason) +Clause DependencySolver::TranslateOrGroup(pkgCache::DepIterator start, pkgCache::DepIterator end, Var reason) { // Non-important dependencies can only be installed if they are currently satisfied, see the check further // below once we have calculated all possible solutions. @@ -1190,7 +1204,7 @@ bool Solver::Solve() } // \brief Apply the selections from the dep cache to the solver -bool Solver::FromDepCache(pkgDepCache &depcache) +bool DependencySolver::FromDepCache(pkgDepCache &depcache) { DefaultRootSetFunc2 rootSet(&cache); std::vector manualPackages; @@ -1322,7 +1336,7 @@ bool Solver::FromDepCache(pkgDepCache &depcache) return true; } -bool Solver::ToDepCache(pkgDepCache &depcache) const +bool DependencySolver::ToDepCache(pkgDepCache &depcache) const { FastContiguousCacheMap movedManual(cache); pkgDepCache::ActionGroup group(depcache); @@ -1388,9 +1402,9 @@ bool Solver::ToDepCache(pkgDepCache &depcache) const } // Command-line -std::string Solver::InternalCliWhy(pkgDepCache &cache, pkgCache::PkgIterator pkg, bool decision) +std::string DependencySolver::InternalCliWhy(pkgDepCache &cache, pkgCache::PkgIterator pkg, bool decision) { - Solver solver(cache.GetCache(), cache.GetPolicy(), EDSP::Request::Flags(0)); + DependencySolver solver(cache.GetCache(), cache.GetPolicy(), EDSP::Request::Flags(0)); // In case nothing has a positive dependency on pkg it may not actually be discovered in a `why-not` // scenario, so make sure we discover it explicitly. solver.Discover(Var(pkg)); diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h index 1d591686b..9faa97079 100644 --- a/apt-pkg/solver3.h +++ b/apt-pkg/solver3.h @@ -276,7 +276,7 @@ inline LiftedBool operator~(LiftedBool decision) */ class Solver { - private: + protected: struct CompareProviders3; struct State; struct Work; @@ -295,8 +295,6 @@ class Solver // Cache is needed to construct Iterators from Version objects we see pkgCache &cache; - // Policy is needed for determining candidate version. - pkgDepCache::Policy &policy; // Root state std::unique_ptr rootState; // States for packages @@ -327,28 +325,6 @@ class Solver inline State &operator[](Var r); inline const State &operator[](Var r) const; - mutable FastContiguousCacheMap pkgObsolete; - // \brief Check if package is obsolete. - // \param AllowManual controls whether manual packages can be obsolete - bool Obsolete(pkgCache::PkgIterator pkg, bool AllowManual=false) const; - bool ObsoletedByNewerSourceVersion(pkgCache::VerIterator cand) const; - - mutable FastContiguousCacheMap priorities; - short GetPriority(pkgCache::VerIterator ver) const - { - if (priorities[ver] == 0) - priorities[ver] = policy.GetPriority(ver); - return priorities[ver]; - } - - mutable ContiguousCacheMap candidates; - pkgCache::VerIterator GetCandidateVer(pkgCache::PkgIterator pkg) const - { - if (candidates[pkg].end()) - candidates[pkg] = policy.GetCandidateVer(pkg); - return candidates[pkg]; - } - // \brief Heap of the remaining work. // // In contrast to MiniSAT which picks undecided literals and decides them, @@ -367,53 +343,22 @@ class Solver // \brief Propagation queue std::queue propQ; - // \brief Discover variables - std::queue discoverQ; // \brief The time we called Solve() time_t startTime{}; - EDSP::Request::Flags requestFlags; /// Various configuration options std::string version{_config->Find("APT::Solver", "3.0")}; // \brief Debug level int debug{_config->FindI("Debug::APT::Solver")}; - // \brief If set, we try to keep automatically installed packages installed. - bool KeepAuto{version == "3.0" || not _config->FindB("APT::Get::AutomaticRemove")}; - // \brief Determines if we are in upgrade mode. - bool IsUpgrade{_config->FindB("APT::Solver::Upgrade", requestFlags &EDSP::Request::UPGRADE_ALL)}; - // \brief If set, removals are allowed. - bool AllowRemove{_config->FindB("APT::Solver::Remove", not(requestFlags & EDSP::Request::FORBID_REMOVE))}; - // \brief If set, removal of manual packages is allowed. - bool AllowRemoveManual{AllowRemove && _config->FindB("APT::Solver::RemoveManual", true)}; - // \brief If set, installs are allowed. - bool AllowInstall{_config->FindB("APT::Solver::Install", not(requestFlags & EDSP::Request::FORBID_NEW_INSTALL))}; - // \brief If set, we use strict pinning. - bool StrictPinning{_config->FindB("APT::Solver::Strict-Pinning", true)}; - // \brief If set, we install missing recommends and pick new best packages. - bool FixPolicyBroken{_config->FindB("APT::Get::Fix-Policy-Broken")}; - // \brief If set, we use strict pinning. - bool DeferVersionSelection{_config->FindB("APT::Solver::Defer-Version-Selection", true)}; // \brief If set, we use strict pinning. int Timeout{_config->FindI("APT::Solver::Timeout", 10)}; - // \brief Keep recommends installed - bool KeepRecommends{_config->FindB("APT::AutoRemove::RecommendsImportant", true)}; - // \brief Keep suggests installed - bool KeepSuggests{_config->FindB("APT::AutoRemove::SuggestsImportant", true)}; - // \brief Discover a variable, translating the underlying dependencies to the SAT presentation // // This does a breadth-first search of the entire dependency tree of var, // utilizing the discoverQ above. - void Discover(Var var); - // \brief Link a clause into the watchers - const Clause *RegisterClause(Clause &&clause); - // \brief Enqueue dependencies shared by all versions of the package. - void RegisterCommonDependencies(pkgCache::PkgIterator Pkg); - - // \brief Translate an or group into a clause object - [[nodiscard]] Clause TranslateOrGroup(pkgCache::DepIterator start, pkgCache::DepIterator end, Var reason); + virtual void Discover(Var var) = 0; // \brief Propagate all pending propagations [[nodiscard]] bool Propagate(); @@ -436,24 +381,19 @@ class Solver [[nodiscard]] bool AddWork(Work &&work); // \brief Basic solver initializer. This cannot fail. - Solver(pkgCache &Cache, pkgDepCache::Policy &Policy, EDSP::Request::Flags requestFlags); - ~Solver(); + Solver(pkgCache &Cache); + virtual ~Solver(); // Assume a literal [[nodiscard]] bool Assume(Lit lit, const Clause *reason = nullptr); // Enqueue a decision fact [[nodiscard]] bool Enqueue(Lit lit, const Clause *reason = nullptr); - // \brief Apply the selections from the dep cache to the solver - [[nodiscard]] bool FromDepCache(pkgDepCache &depcache); - // \brief Apply the solver result to the depCache - [[nodiscard]] bool ToDepCache(pkgDepCache &depcache) const; - // \brief Solve the dependencies [[nodiscard]] bool Solve(); // Print dependency chain - std::string WhyStr(Var reason) const; + virtual std::string WhyStr(Var reason) const; /** * \brief Print a long reason string @@ -466,14 +406,88 @@ class Solver * \param prefix A prefix, for indentation purposes, as this is recursive * \param seen A set of seen objects such that the output does not repeat itself (not for safety, it is acyclic) */ - std::string LongWhyStr(Var var, bool decision, const Clause *rclause, std::string prefix, std::unordered_set &seen) const; - - // \brief Temporary internal API with external linkage for the `apt why` and `apt why-not` commands. - APT_PUBLIC static std::string InternalCliWhy(pkgDepCache &depcache, pkgCache::PkgIterator Pkg, bool decision); + virtual std::string LongWhyStr(Var var, bool decision, const Clause *rclause, std::string prefix, std::unordered_set &seen) const; }; -}; // 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 DependencySolver : public Solver +{ + friend class Solver::CompareProviders3; + + // Policy is needed for determining candidate version. + pkgDepCache::Policy &policy; + // Request flags determine the behavior of the options below, make sure it comes first. + EDSP::Request::Flags requestFlags; + // Configuration options for the dependency solver + bool KeepAuto{version == "3.0" || not _config->FindB("APT::Get::AutomaticRemove")}; + bool IsUpgrade{_config->FindB("APT::Solver::Upgrade", requestFlags &EDSP::Request::UPGRADE_ALL)}; + bool AllowRemove{_config->FindB("APT::Solver::Remove", not(requestFlags & EDSP::Request::FORBID_REMOVE))}; + bool AllowRemoveManual{AllowRemove && _config->FindB("APT::Solver::RemoveManual", true)}; + bool AllowInstall{_config->FindB("APT::Solver::Install", not(requestFlags & EDSP::Request::FORBID_NEW_INSTALL))}; + bool StrictPinning{_config->FindB("APT::Solver::Strict-Pinning", true)}; + bool FixPolicyBroken{_config->FindB("APT::Get::Fix-Policy-Broken")}; + bool DeferVersionSelection{_config->FindB("APT::Solver::Defer-Version-Selection", true)}; + bool KeepRecommends{_config->FindB("APT::AutoRemove::RecommendsImportant", true)}; + bool KeepSuggests{_config->FindB("APT::AutoRemove::SuggestsImportant", true)}; + + // Helper functions for detecting obsolete packages + mutable FastContiguousCacheMap pkgObsolete; + bool Obsolete(pkgCache::PkgIterator pkg, bool AllowManual = false) const; + bool ObsoletedByNewerSourceVersion(pkgCache::VerIterator cand) const; + + // GetPriority() with caching + mutable FastContiguousCacheMap priorities; + short GetPriority(pkgCache::VerIterator ver) const + { + if (priorities[ver] == 0) + priorities[ver] = policy.GetPriority(ver); + return priorities[ver]; + } + + // GetCandidateVer() with caching + mutable ContiguousCacheMap candidates; + pkgCache::VerIterator GetCandidateVer(pkgCache::PkgIterator pkg) const + { + if (candidates[pkg].end()) + candidates[pkg] = policy.GetCandidateVer(pkg); + return candidates[pkg]; + } + + // \brief Discover variables + std::queue discoverQ; + /// \brief Discover the dependencies of the variable + void Discover(Var var) override; + /// \brief Link a clause into the watchers + const Clause *RegisterClause(Clause &&clause); + /// \brief Enqueue dependencies shared by all versions of the package. + void RegisterCommonDependencies(pkgCache::PkgIterator Pkg); + + /// \brief Translate an or group into a clause object + [[nodiscard]] Clause TranslateOrGroup(pkgCache::DepIterator start, pkgCache::DepIterator end, Var reason); + + public: + // \brief Basic solver initializer. This cannot fail. + DependencySolver(pkgCache &Cache, pkgDepCache::Policy &Policy, EDSP::Request::Flags requestFlags); + ~DependencySolver() override; + + /// \brief Apply the selections from the dep cache to the solver + [[nodiscard]] bool FromDepCache(pkgDepCache &depcache); + /// \brief Apply the solver result to the depCache + [[nodiscard]] bool ToDepCache(pkgDepCache &depcache) const; + /// \brief Temporary internal API with external linkage for the `apt why` and `apt why-not` commands. + APT_PUBLIC static std::string InternalCliWhy(pkgDepCache &depcache, pkgCache::PkgIterator Pkg, bool decision); +}; +}; // namespace APT::Solver /** * \brief A single work item * diff --git a/cmdline/apt.cc b/cmdline/apt.cc index 39ec68e71..4a0708db8 100644 --- a/cmdline/apt.cc +++ b/cmdline/apt.cc @@ -66,7 +66,7 @@ static bool DoWhy(CommandLine &CmdL) /*{{{*/ if (unlikely(not CacheFile.BuildDepCache())) return false; for (auto pkg : pkgset) - std::cout << APT::Solver::Solver::InternalCliWhy(CacheFile, pkg, decision) << std::flush; + std::cout << APT::Solver::DependencySolver::InternalCliWhy(CacheFile, pkg, decision) << std::flush; return not _error->PendingError(); } static std::vector GetCommands() /*{{{*/ -- cgit v1.2.3-70-g09d2 From bd0738fdd9aff3016230b3b5466e9498c58e4fb8 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Mon, 22 Dec 2025 22:40:12 +0100 Subject: solver3: Reorder the source code Move the DependencySolver methods and their helpers to the end of the file. --- apt-pkg/solver3.cc | 955 ++++++++++++++++++++++++++--------------------------- apt-pkg/solver3.h | 3 +- 2 files changed, 477 insertions(+), 481 deletions(-) diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index ec33cc1f6..8ef969581 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -41,164 +41,6 @@ namespace APT::Solver { -// FIXME: Helpers stolen from DepCache, please give them back. -struct Solver::CompareProviders3 /*{{{*/ -{ - pkgCache &Cache; - pkgDepCache::Policy &Policy; - pkgCache::PkgIterator const Pkg; - APT::Solver::DependencySolver &Solver; - - pkgCache::VerIterator bestVersion(pkgCache::PkgIterator pkg) - { - pkgCache::VerIterator res = pkg.VersionList(); - for (auto v = res; not v.end(); ++v) - res = std::max(res, v, *this); - return res; - } - bool operator()(Var a, Var b) - { - pkgCache::VerIterator va = a.Ver(Cache); - pkgCache::VerIterator vb = b.Ver(Cache); - if (auto pa = a.Pkg(Cache)) - va = bestVersion(pa); - if (auto pb = b.Pkg(Cache)) - vb = bestVersion(pb); - - assert(not va.end() && not vb.end()); - return (*this)(va, vb); - } - bool operator()(pkgCache::VerIterator const &AV, pkgCache::VerIterator const &BV) - { - assert(not AV.end() && not BV.end()); - pkgCache::PkgIterator const A = AV.ParentPkg(); - pkgCache::PkgIterator const B = BV.ParentPkg(); - // Compare versions for the same package. FIXME: Move this to the real implementation - if (A == B) - { - if (AV == BV) - return false; - - // Candidate wins in upgrade scenario - if (Solver.IsUpgrade) - { - auto Cand = Solver.GetCandidateVer(A); - if (AV == Cand || BV == Cand) - return (AV == Cand); - } - - // Installed version wins otherwise - if (A.CurrentVer() == AV || B.CurrentVer() == BV) - return (A.CurrentVer() == AV); - - // Rest is ordered list, first by priority - if (auto pinA = Solver.GetPriority(AV), pinB = Solver.GetPriority(BV); pinA != pinB) - return pinA > pinB; - - // Then by version - return _system->VS->CmpVersion(AV.VerStr(), BV.VerStr()) > 0; - } - // Try obsolete choices only after exhausting non-obsolete choices such that we install - // packages replacing them and don't keep back upgrades depending on the replacement to - // keep the obsolete package installed. - if (Solver.IsUpgrade) - if (auto obsoleteA = Solver.Obsolete(A), obsoleteB = Solver.Obsolete(B); obsoleteA != obsoleteB) - return obsoleteB; - // Prefer MA:same packages if other architectures for it are installed - if ((AV->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same || - (BV->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same) - { - bool instA = false; - if ((AV->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same) - { - pkgCache::GrpIterator Grp = A.Group(); - for (pkgCache::PkgIterator P = Grp.PackageList(); P.end() == false; P = Grp.NextPkg(P)) - if (P->CurrentVer != 0) - { - instA = true; - break; - } - } - bool instB = false; - if ((BV->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same) - { - pkgCache::GrpIterator Grp = B.Group(); - for (pkgCache::PkgIterator P = Grp.PackageList(); P.end() == false; P = Grp.NextPkg(P)) - { - if (P->CurrentVer != 0) - { - instB = true; - break; - } - } - } - if (instA != instB) - return instA; - } - if ((A->CurrentVer == 0 || B->CurrentVer == 0) && A->CurrentVer != B->CurrentVer) - return A->CurrentVer != 0; - // Prefer packages in the same group as the target; e.g. foo:i386, foo:amd64 - if (A->Group != B->Group && not Pkg.end()) - { - if (A->Group == Pkg->Group && B->Group != Pkg->Group) - return true; - else if (B->Group == Pkg->Group && A->Group != Pkg->Group) - return false; - } - // we like essentials - if ((A->Flags & pkgCache::Flag::Essential) != (B->Flags & pkgCache::Flag::Essential)) - { - if ((A->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential) - return true; - else if ((B->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential) - return false; - } - if ((A->Flags & pkgCache::Flag::Important) != (B->Flags & pkgCache::Flag::Important)) - { - if ((A->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important) - return true; - else if ((B->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important) - return false; - } - // prefer native architecture - if (strcmp(A.Arch(), B.Arch()) != 0) - { - if (strcmp(A.Arch(), A.Cache()->NativeArch()) == 0) - return true; - else if (strcmp(B.Arch(), B.Cache()->NativeArch()) == 0) - return false; - std::vector archs = APT::Configuration::getArchitectures(); - for (std::vector::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 Kernels; - - public: - DefaultRootSetFunc2(pkgCache *cache) : Kernels(APT::KernelAutoRemoveHelper::GetProtectedKernelsFilter(cache)) {}; - ~DefaultRootSetFunc2() override = default; - - bool InRootSet(const pkgCache::PkgIterator &pkg) override { return pkg.end() == false && ((*Kernels)(pkg) || DefaultRootSetFunc::InRootSet(pkg)); }; -}; // FIXME: DEDUP with pkgDepCache. -/*}}}*/ - Solver::Solver(pkgCache &cache) : cache(cache), rootState(new State), @@ -216,25 +58,6 @@ Solver::Solver(pkgCache &cache) Solver::~Solver() = default; -DependencySolver::DependencySolver(pkgCache &cache, pkgDepCache::Policy &policy, EDSP::Request::Flags requestFlags) - : Solver(cache), - policy(policy), - requestFlags(requestFlags), - pkgObsolete(cache), - priorities(cache), - candidates(cache) -{ - // Ensure trivially - static_assert(std::is_trivially_destructible_v); - static_assert(std::is_trivially_destructible_v); - static_assert(sizeof(Var) == sizeof(map_pointer)); - static_assert(sizeof(Var) == sizeof(map_pointer)); - // Root state is "true". - rootState->decision = LiftedBool::True; -} - -DependencySolver::~DependencySolver() = default; - // This function determines if a work item is less important than another. bool Solver::Work::operator<(Solver::Work const &b) const { @@ -512,73 +335,6 @@ std::string Solver::LongWhyStr(Var var, bool decision, const Clause *rclause, st return out.str(); } -// This is essentially asking whether any other binary in the source package has a higher candidate -// version. This pretends that each package is installed at the same source version as the package -// under consideration. -bool DependencySolver::ObsoletedByNewerSourceVersion(pkgCache::VerIterator cand) const -{ - const auto pkg = cand.ParentPkg(); - const int candPriority = GetPriority(cand); - - for (auto ver = cand.Cache()->FindGrp(cand.SourcePkgName()).VersionsInSource(); not ver.end(); ver = ver.NextInSource()) - { - // We are only interested in other packages in the same source package; built for the same architecture. - if (ver->ParentPkg == cand->ParentPkg || ver.ParentPkg()->Arch != cand.ParentPkg()->Arch || - (ver->MultiArch & pkgCache::Version::All) != (cand->MultiArch & pkgCache::Version::All) || - cache.VS->CmpVersion(ver.SourceVerStr(), cand.SourceVerStr()) <= 0) - continue; - - // We also take equal priority here, given that we have a higher version - const int priority = GetPriority(ver); - if (priority == 0 || priority < candPriority) - continue; - - pkgObsolete[pkg] = 2; - if (debug >= 3) - std::cerr << "Obsolete: " << cand.ParentPkg().FullName() << "=" << cand.VerStr() << " due to " << ver.ParentPkg().FullName() << "=" << ver.VerStr() << "\n"; - return true; - } - - return false; -} - -bool DependencySolver::Obsolete(pkgCache::PkgIterator pkg, bool AllowManual) const -{ - if ((*this)[pkg].flags.manual && not AllowManual) - return false; - if (pkgObsolete[pkg] != 0) - return pkgObsolete[pkg] == 2; - - auto ver = GetCandidateVer(pkg); - - if (ver.end() && not StrictPinning) - ver = pkg.VersionList(); - if (ver.end()) - { - if (debug >= 3) - std::cerr << "Obsolete: " << pkg.FullName() << " - not installable\n"; - pkgObsolete[pkg] = 2; - return true; - } - - if (ObsoletedByNewerSourceVersion(ver)) - return true; - - // Any version downloadable is good enough for us tbh - for (auto ver = pkg.VersionList(); not ver.end(); ++ver) - { - if (ver.Downloadable()) - { - pkgObsolete[pkg] = 1; - return false; - } - } - - if (debug >= 3) - std::cerr << "Obsolete: " << ver.ParentPkg().FullName() << "=" << ver.VerStr() << " - not installable\n"; - pkgObsolete[pkg] = 2; - return true; -} bool Solver::Assume(Lit lit, const Clause *reason) { trailLim.push_back(trail.size()); @@ -685,18 +441,388 @@ bool Solver::Propagate() return true; } -static bool SameOrGroup(pkgCache::DepIterator a, pkgCache::DepIterator b) +void Solver::Push(Var var, Work work) { - while (1) - { - if (a->DependencyData != b->DependencyData) - return false; + if (unlikely(debug >= 2)) + std::cerr << "Trying choice for " << work.toString(cache) << std::endl; - // At least one has reached the end, break - if (not(a->CompareOp & pkgCache::Dep::Or) || not(b->CompareOp & pkgCache::Dep::Or)) - break; + trailLim.push_back(trail.size()); + trail.push_back(Trail{var, std::move(work)}); +} - ++a, ++b; +void Solver::UndoOne() +{ + auto trailItem = trail.back(); + + if (unlikely(debug >= 4)) + std::cerr << "Undoing a single decision\n"; + + if (not trailItem.assigned.empty()) + { + if (unlikely(debug >= 4)) + std::cerr << "Unassign " << trailItem.assigned.toString(cache) << "\n"; + auto &state = (*this)[trailItem.assigned]; + state.decision = LiftedBool::Undefined; + state.reason = nullptr; + state.reasonStr = nullptr; + state.depth = 0; + } + + if (auto work = trailItem.work) + { + if (unlikely(debug >= 4)) + std::cerr << "Adding work item " << work->toString(cache) << std::endl; + + if (not AddWork(std::move(*work))) + abort(); + } + + trail.pop_back(); + + // FIXME: Add the undo handling here once we have watchers. +} + +bool Solver::Pop() +{ + if (decisionLevel() == 0) + return false; + + time_t now = time(nullptr); + if (startTime == 0) + startTime = now; + if (now - startTime >= Timeout) + return _error->Error("Solver timed out."); + + if (unlikely(debug >= 2)) + for (std::string msg; _error->PopMessage(msg);) + std::cerr << "Branch failed: " << msg << std::endl; + + _error->Discard(); + + // Assume() actually failed to enqueue anything, abort here + if (trailLim.back() == trail.size()) + { + trailLim.pop_back(); + return true; + } + + assert(trailLim.back() < trail.size()); + int itemsToUndo = trail.size() - trailLim.back(); + auto choice = trail[trailLim.back()].assigned; + + for (; itemsToUndo; --itemsToUndo) + UndoOne(); + + // We need to remove any work that is at a higher depth. + // FIXME: We should just mark the entries as erased and only do a compaction + // of the heap once we have a lot of erased entries in it. + trailLim.pop_back(); + work.erase(std::remove_if(work.begin(), work.end(), [this](Work &w) -> bool + { return w.depth > decisionLevel() || w.erased; }), + work.end()); + std::make_heap(work.begin(), work.end()); + + if (unlikely(debug >= 2)) + std::cerr << "Backtracking to choice " << choice.toString(cache) << "\n"; + + // FIXME: There should be a reason! + if (not choice.empty() && not Enqueue(~choice, {})) + return false; + + (*this)[choice].reasonStr = "backtracked"; + + if (unlikely(debug >= 2)) + std::cerr << "Backtracked to choice " << choice.toString(cache) << "\n"; + + return true; +} + +bool Solver::AddWork(Work &&w) +{ + if (w.clause->negative) + { + for (auto var : w.clause->solutions) + if (not Enqueue(~var, w.clause)) + return false; + } + else + { + if (unlikely(debug >= 3 && w.clause->optional)) + std::cerr << "Enqueuing Recommends " << w.clause->toString(cache) << std::endl; + if (w.clause->solutions.size() == 1 && not w.clause->optional) + return Enqueue(w.clause->solutions[0], w.clause); + + w.size = std::count_if(w.clause->solutions.begin(), w.clause->solutions.end(), [this](auto V) + { return value(V) != LiftedBool::False; }); + work.push_back(std::move(w)); + std::push_heap(work.begin(), work.end()); + } + return true; +} + +bool Solver::Solve() +{ + _error->PushToStack(); + DEFER([&]() + { _error->MergeWithStack(); }); + startTime = time(nullptr); + while (true) + { + while (not Propagate()) + { + if (not Pop()) + return false; + } + + if (work.empty()) + break; + + // *NOW* we can pop the item. + std::pop_heap(work.begin(), work.end()); + + // This item has been replaced with a new one. Remove it. + if (work.back().erased) + { + work.pop_back(); + continue; + } + auto item = std::move(work.back()); + work.pop_back(); + trail.push_back(Trail{Var(), item}); + + if (std::any_of(item.clause->solutions.begin(), item.clause->solutions.end(), [this](auto ver) + { return value(ver) == LiftedBool::True; })) + { + if (unlikely(debug >= 2)) + std::cerr << "ELIDED " << item.toString(cache) << std::endl; + continue; + } + + if (unlikely(debug >= 1)) + std::cerr << item.toString(cache) << std::endl; + + bool foundSolution = false; + for (auto &sol : item.clause->solutions) + { + if (value(sol) == LiftedBool::False) + { + if (unlikely(debug >= 3)) + std::cerr << "(existing conflict: " << sol.toString(cache) << ")\n"; + continue; + } + if (item.size > 1 || item.clause->optional) + { + Push(sol, item); + } + if (unlikely(debug >= 3)) + std::cerr << "(try it: " << sol.toString(cache) << ")\n"; + if (not Enqueue(sol, item.clause) && not Pop()) + return false; + foundSolution = true; + break; + } + if (not foundSolution && not item.clause->optional) + { + std::ostringstream err; + + err << "Unable to satisfy dependencies. Reached two conflicting decisions:" << "\n"; + std::unordered_set seen; + err << "1. " << LongWhyStr(item.clause->reason, true, (*this)[item.clause->reason].reason, " ", seen).substr(3) << "\n"; + err << "2. " << LongWhyStr(item.clause->reason, false, item.clause, " ", seen).substr(3); + _error->Error("%s", err.str().c_str()); + if (not Pop()) + return false; + } + } + + return true; +} + +// -------------------------------------------------------------------------------------------------------------------- +// -------------------------------------------- Dependency solver ----------------------------------------------------- +// -------------------------------------------------------------------------------------------------------------------- +// FIXME: Helpers stolen from DepCache, please give them back. +struct CompareProviders3 /*{{{*/ +{ + pkgCache &Cache; + pkgDepCache::Policy &Policy; + pkgCache::PkgIterator const Pkg; + APT::Solver::DependencySolver &Solver; + + pkgCache::VerIterator bestVersion(pkgCache::PkgIterator pkg) + { + pkgCache::VerIterator res = pkg.VersionList(); + for (auto v = res; not v.end(); ++v) + res = std::max(res, v, *this); + return res; + } + bool operator()(Var a, Var b) + { + pkgCache::VerIterator va = a.Ver(Cache); + pkgCache::VerIterator vb = b.Ver(Cache); + if (auto pa = a.Pkg(Cache)) + va = bestVersion(pa); + if (auto pb = b.Pkg(Cache)) + vb = bestVersion(pb); + + assert(not va.end() && not vb.end()); + return (*this)(va, vb); + } + bool operator()(pkgCache::VerIterator const &AV, pkgCache::VerIterator const &BV) + { + assert(not AV.end() && not BV.end()); + pkgCache::PkgIterator const A = AV.ParentPkg(); + pkgCache::PkgIterator const B = BV.ParentPkg(); + // Compare versions for the same package. FIXME: Move this to the real implementation + if (A == B) + { + if (AV == BV) + return false; + + // Candidate wins in upgrade scenario + if (Solver.IsUpgrade) + { + auto Cand = Solver.GetCandidateVer(A); + if (AV == Cand || BV == Cand) + return (AV == Cand); + } + + // Installed version wins otherwise + if (A.CurrentVer() == AV || B.CurrentVer() == BV) + return (A.CurrentVer() == AV); + + // Rest is ordered list, first by priority + if (auto pinA = Solver.GetPriority(AV), pinB = Solver.GetPriority(BV); pinA != pinB) + return pinA > pinB; + + // Then by version + return _system->VS->CmpVersion(AV.VerStr(), BV.VerStr()) > 0; + } + // Try obsolete choices only after exhausting non-obsolete choices such that we install + // packages replacing them and don't keep back upgrades depending on the replacement to + // keep the obsolete package installed. + if (Solver.IsUpgrade) + if (auto obsoleteA = Solver.Obsolete(A), obsoleteB = Solver.Obsolete(B); obsoleteA != obsoleteB) + return obsoleteB; + // Prefer MA:same packages if other architectures for it are installed + if ((AV->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same || + (BV->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same) + { + bool instA = false; + if ((AV->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same) + { + pkgCache::GrpIterator Grp = A.Group(); + for (pkgCache::PkgIterator P = Grp.PackageList(); P.end() == false; P = Grp.NextPkg(P)) + if (P->CurrentVer != 0) + { + instA = true; + break; + } + } + bool instB = false; + if ((BV->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same) + { + pkgCache::GrpIterator Grp = B.Group(); + for (pkgCache::PkgIterator P = Grp.PackageList(); P.end() == false; P = Grp.NextPkg(P)) + { + if (P->CurrentVer != 0) + { + instB = true; + break; + } + } + } + if (instA != instB) + return instA; + } + if ((A->CurrentVer == 0 || B->CurrentVer == 0) && A->CurrentVer != B->CurrentVer) + return A->CurrentVer != 0; + // Prefer packages in the same group as the target; e.g. foo:i386, foo:amd64 + if (A->Group != B->Group && not Pkg.end()) + { + if (A->Group == Pkg->Group && B->Group != Pkg->Group) + return true; + else if (B->Group == Pkg->Group && A->Group != Pkg->Group) + return false; + } + // we like essentials + if ((A->Flags & pkgCache::Flag::Essential) != (B->Flags & pkgCache::Flag::Essential)) + { + if ((A->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential) + return true; + else if ((B->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential) + return false; + } + if ((A->Flags & pkgCache::Flag::Important) != (B->Flags & pkgCache::Flag::Important)) + { + if ((A->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important) + return true; + else if ((B->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important) + return false; + } + // prefer native architecture + if (strcmp(A.Arch(), B.Arch()) != 0) + { + if (strcmp(A.Arch(), A.Cache()->NativeArch()) == 0) + return true; + else if (strcmp(B.Arch(), B.Cache()->NativeArch()) == 0) + return false; + std::vector archs = APT::Configuration::getArchitectures(); + for (std::vector::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 Kernels; + + public: + DefaultRootSetFunc2(pkgCache *cache) : Kernels(APT::KernelAutoRemoveHelper::GetProtectedKernelsFilter(cache)) {}; + ~DefaultRootSetFunc2() override = default; + + bool InRootSet(const pkgCache::PkgIterator &pkg) override { return pkg.end() == false && ((*Kernels)(pkg) || DefaultRootSetFunc::InRootSet(pkg)); }; +}; // FIXME: DEDUP with pkgDepCache. +/*}}}*/ + +DependencySolver::DependencySolver(pkgCache &cache, pkgDepCache::Policy &policy, EDSP::Request::Flags requestFlags) + : Solver(cache), + policy(policy), + requestFlags(requestFlags), + pkgObsolete(cache), + priorities(cache), + candidates(cache) +{ +} + +DependencySolver::~DependencySolver() = default; + +static bool SameOrGroup(pkgCache::DepIterator a, pkgCache::DepIterator b) +{ + while (1) + { + if (a->DependencyData != b->DependencyData) + return false; + + // At least one has reached the end, break + if (not(a->CompareOp & pkgCache::Dep::Or) || not(b->CompareOp & pkgCache::Dep::Or)) + break; + + ++a, ++b; } // Fully iterated over a and b return not(a->CompareOp & pkgCache::Dep::Or) && not(b->CompareOp & pkgCache::Dep::Or); @@ -731,42 +857,109 @@ const Clause *DependencySolver::RegisterClause(Clause &&clause) earlierSol) != clause.solutions.end(); })) continue; - if (earlierClause->optional == clause.optional) - { - std::erase_if(earlierClause->solutions, [&clause, this](auto earlierSol) - { return std::find(clause.solutions.begin(), - clause.solutions.end(), - earlierSol) == clause.solutions.end(); }); + if (earlierClause->optional == clause.optional) + { + std::erase_if(earlierClause->solutions, [&clause, this](auto earlierSol) + { return std::find(clause.solutions.begin(), + clause.solutions.end(), + earlierSol) == clause.solutions.end(); }); + + earlierClause->merged.push_front(clause); + merged = true; + } + else if (clause.optional) + { + // If say a Depends has fewer solution than a Recommends, remove the Recommend's extranous ones. + std::erase_if(clause.solutions, [&earlierClause, this](auto sol) + { return std::find(earlierClause->solutions.begin(), + earlierClause->solutions.end(), + sol) == earlierClause->solutions.end(); }); + + // Remove recursion here, such that we display correctly (if we ever display anywhere...) + auto earlierClauseCopy = *earlierClause; + clause.merged = std::move(earlierClauseCopy.merged); + clause.merged.push_front(earlierClauseCopy); + } + } + + if (merged) + return nullptr; + } + + clauses.push_back(std::make_unique(std::move(clause))); + auto const &inserted = clauses.back(); + for (auto var : inserted->solutions) + (*this)[var].rclauses.push_back(inserted.get()); + return inserted.get(); +} + +// This is essentially asking whether any other binary in the source package has a higher candidate +// version. This pretends that each package is installed at the same source version as the package +// under consideration. +bool DependencySolver::ObsoletedByNewerSourceVersion(pkgCache::VerIterator cand) const +{ + const auto pkg = cand.ParentPkg(); + const int candPriority = GetPriority(cand); + + for (auto ver = cand.Cache()->FindGrp(cand.SourcePkgName()).VersionsInSource(); not ver.end(); ver = ver.NextInSource()) + { + // We are only interested in other packages in the same source package; built for the same architecture. + if (ver->ParentPkg == cand->ParentPkg || ver.ParentPkg()->Arch != cand.ParentPkg()->Arch || + (ver->MultiArch & pkgCache::Version::All) != (cand->MultiArch & pkgCache::Version::All) || + cache.VS->CmpVersion(ver.SourceVerStr(), cand.SourceVerStr()) <= 0) + continue; + + // We also take equal priority here, given that we have a higher version + const int priority = GetPriority(ver); + if (priority == 0 || priority < candPriority) + continue; + + pkgObsolete[pkg] = 2; + if (debug >= 3) + std::cerr << "Obsolete: " << cand.ParentPkg().FullName() << "=" << cand.VerStr() << " due to " << ver.ParentPkg().FullName() << "=" << ver.VerStr() << "\n"; + return true; + } + + return false; +} + +bool DependencySolver::Obsolete(pkgCache::PkgIterator pkg, bool AllowManual) const +{ + if ((*this)[pkg].flags.manual && not AllowManual) + return false; + if (pkgObsolete[pkg] != 0) + return pkgObsolete[pkg] == 2; - earlierClause->merged.push_front(clause); - merged = true; - } - else if (clause.optional) - { - // If say a Depends has fewer solution than a Recommends, remove the Recommend's extranous ones. - std::erase_if(clause.solutions, [&earlierClause, this](auto sol) - { return std::find(earlierClause->solutions.begin(), - earlierClause->solutions.end(), - sol) == earlierClause->solutions.end(); }); + auto ver = GetCandidateVer(pkg); - // Remove recursion here, such that we display correctly (if we ever display anywhere...) - auto earlierClauseCopy = *earlierClause; - clause.merged = std::move(earlierClauseCopy.merged); - clause.merged.push_front(earlierClauseCopy); - } - } + if (ver.end() && not StrictPinning) + ver = pkg.VersionList(); + if (ver.end()) + { + if (debug >= 3) + std::cerr << "Obsolete: " << pkg.FullName() << " - not installable\n"; + pkgObsolete[pkg] = 2; + return true; + } - if (merged) - return nullptr; + if (ObsoletedByNewerSourceVersion(ver)) + return true; + + // Any version downloadable is good enough for us tbh + for (auto ver = pkg.VersionList(); not ver.end(); ++ver) + { + if (ver.Downloadable()) + { + pkgObsolete[pkg] = 1; + return false; + } } - clauses.push_back(std::make_unique(std::move(clause))); - auto const &inserted = clauses.back(); - for (auto var : inserted->solutions) - (*this)[var].rclauses.push_back(inserted.get()); - return inserted.get(); + if (debug >= 3) + std::cerr << "Obsolete: " << ver.ParentPkg().FullName() << "=" << ver.VerStr() << " - not installable\n"; + pkgObsolete[pkg] = 2; + return true; } - void DependencySolver::Discover(Var var) { assert(discoverQ.empty()); @@ -1007,202 +1200,6 @@ Clause DependencySolver::TranslateOrGroup(pkgCache::DepIterator start, pkgCache: return clause; } -void Solver::Push(Var var, Work work) -{ - if (unlikely(debug >= 2)) - std::cerr << "Trying choice for " << work.toString(cache) << std::endl; - - trailLim.push_back(trail.size()); - trail.push_back(Trail{var, std::move(work)}); -} - -void Solver::UndoOne() -{ - auto trailItem = trail.back(); - - if (unlikely(debug >= 4)) - std::cerr << "Undoing a single decision\n"; - - if (not trailItem.assigned.empty()) - { - if (unlikely(debug >= 4)) - std::cerr << "Unassign " << trailItem.assigned.toString(cache) << "\n"; - auto &state = (*this)[trailItem.assigned]; - state.decision = LiftedBool::Undefined; - state.reason = nullptr; - state.reasonStr = nullptr; - state.depth = 0; - } - - if (auto work = trailItem.work) - { - if (unlikely(debug >= 4)) - std::cerr << "Adding work item " << work->toString(cache) << std::endl; - - if (not AddWork(std::move(*work))) - abort(); - } - - trail.pop_back(); - - // FIXME: Add the undo handling here once we have watchers. -} - -bool Solver::Pop() -{ - if (decisionLevel() == 0) - return false; - - time_t now = time(nullptr); - if (startTime == 0) - startTime = now; - if (now - startTime >= Timeout) - return _error->Error("Solver timed out."); - - if (unlikely(debug >= 2)) - for (std::string msg; _error->PopMessage(msg);) - std::cerr << "Branch failed: " << msg << std::endl; - - _error->Discard(); - - // Assume() actually failed to enqueue anything, abort here - if (trailLim.back() == trail.size()) - { - trailLim.pop_back(); - return true; - } - - assert(trailLim.back() < trail.size()); - int itemsToUndo = trail.size() - trailLim.back(); - auto choice = trail[trailLim.back()].assigned; - - for (; itemsToUndo; --itemsToUndo) - UndoOne(); - - // We need to remove any work that is at a higher depth. - // FIXME: We should just mark the entries as erased and only do a compaction - // of the heap once we have a lot of erased entries in it. - trailLim.pop_back(); - work.erase(std::remove_if(work.begin(), work.end(), [this](Work &w) -> bool - { return w.depth > decisionLevel() || w.erased; }), - work.end()); - std::make_heap(work.begin(), work.end()); - - if (unlikely(debug >= 2)) - std::cerr << "Backtracking to choice " << choice.toString(cache) << "\n"; - - // FIXME: There should be a reason! - if (not choice.empty() && not Enqueue(~choice, {})) - return false; - - (*this)[choice].reasonStr = "backtracked"; - - if (unlikely(debug >= 2)) - std::cerr << "Backtracked to choice " << choice.toString(cache) << "\n"; - - return true; -} - -bool Solver::AddWork(Work &&w) -{ - if (w.clause->negative) - { - for (auto var : w.clause->solutions) - if (not Enqueue(~var, w.clause)) - return false; - } - else - { - if (unlikely(debug >= 3 && w.clause->optional)) - std::cerr << "Enqueuing Recommends " << w.clause->toString(cache) << std::endl; - if (w.clause->solutions.size() == 1 && not w.clause->optional) - return Enqueue(w.clause->solutions[0], w.clause); - - w.size = std::count_if(w.clause->solutions.begin(), w.clause->solutions.end(), [this](auto V) - { return value(V) != LiftedBool::False; }); - work.push_back(std::move(w)); - std::push_heap(work.begin(), work.end()); - } - return true; -} - -bool Solver::Solve() -{ - _error->PushToStack(); - DEFER([&]() { _error->MergeWithStack(); }); - startTime = time(nullptr); - while (true) - { - while (not Propagate()) - { - if (not Pop()) - return false; - } - - if (work.empty()) - break; - - // *NOW* we can pop the item. - std::pop_heap(work.begin(), work.end()); - - // This item has been replaced with a new one. Remove it. - if (work.back().erased) - { - work.pop_back(); - continue; - } - auto item = std::move(work.back()); - work.pop_back(); - trail.push_back(Trail{Var(), item}); - - if (std::any_of(item.clause->solutions.begin(), item.clause->solutions.end(), [this](auto ver) - { return value(ver) == LiftedBool::True; })) - { - if (unlikely(debug >= 2)) - std::cerr << "ELIDED " << item.toString(cache) << std::endl; - continue; - } - - if (unlikely(debug >= 1)) - std::cerr << item.toString(cache) << std::endl; - - bool foundSolution = false; - for (auto &sol : item.clause->solutions) - { - if (value(sol) == LiftedBool::False) - { - if (unlikely(debug >= 3)) - std::cerr << "(existing conflict: " << sol.toString(cache) << ")\n"; - continue; - } - if (item.size > 1 || item.clause->optional) - { - Push(sol, item); - } - if (unlikely(debug >= 3)) - std::cerr << "(try it: " << sol.toString(cache) << ")\n"; - if (not Enqueue(sol, item.clause) && not Pop()) - return false; - foundSolution = true; - break; - } - if (not foundSolution && not item.clause->optional) - { - std::ostringstream err; - - err << "Unable to satisfy dependencies. Reached two conflicting decisions:" << "\n"; - std::unordered_set seen; - err << "1. " << LongWhyStr(item.clause->reason, true, (*this)[item.clause->reason].reason, " ", seen).substr(3) << "\n"; - err << "2. " << LongWhyStr(item.clause->reason, false, item.clause, " ", seen).substr(3); - _error->Error("%s", err.str().c_str()); - if (not Pop()) - return false; - } - } - - return true; -} - // \brief Apply the selections from the dep cache to the solver bool DependencySolver::FromDepCache(pkgDepCache &depcache) { diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h index 9faa97079..23ae49297 100644 --- a/apt-pkg/solver3.h +++ b/apt-pkg/solver3.h @@ -277,7 +277,6 @@ inline LiftedBool operator~(LiftedBool decision) class Solver { protected: - struct CompareProviders3; struct State; struct Work; struct Trail; @@ -421,7 +420,7 @@ class Solver */ class DependencySolver : public Solver { - friend class Solver::CompareProviders3; + friend class CompareProviders3; // Policy is needed for determining candidate version. pkgDepCache::Policy &policy; -- cgit v1.2.3-70-g09d2 From 21d099878ed8c34f3b13747bcec380e0402e57a3 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Sun, 28 Dec 2025 16:56:28 +0100 Subject: solver3: Rename decision to assignment The previous use of decision here conflicted with the use of decision level and the general notion of having made a decision, because the assignment might have been propagated as a matter of fact. --- apt-pkg/solver3.cc | 72 +++++++++++----------- apt-pkg/solver3.h | 21 +++---- test/integration/test-apt-get-build-dep-barbarian | 6 +- test/integration/test-apt-get-build-dep-file | 2 +- test/integration/test-apt-get-install-deb | 4 +- test/integration/test-apt-get-satisfy | 2 +- test/integration/test-apt-get-source-only | 4 +- test/integration/test-apt-install-file-reltag | 2 +- test/integration/test-apt-never-markauto-sections | 2 +- ...test-bug-598669-install-postfix-gets-exim-heavy | 2 +- test/integration/test-bug-601961-install-info | 2 +- test/integration/test-bug-612557-garbage-upgrade | 2 +- .../test-bug-618848-always-respect-user-requests | 2 +- .../test-bug-632221-cross-dependency-satisfaction | 6 +- .../test-bug-675449-essential-are-protected | 2 +- .../test-bug-683786-build-dep-on-virtual-packages | 6 +- .../test-bug-723586-any-stripped-in-single-arch | 2 +- .../test-bug-735967-lib32-to-i386-unavailable | 2 +- .../test-bug-745046-candidate-propagation-fails | 2 +- test/integration/test-bug-961266-hold-means-hold | 6 +- .../test-explore-or-groups-in-markinstall | 4 +- test/integration/test-handling-broken-orgroups | 4 +- .../test-ignore-provides-if-versioned-breaks | 6 +- .../test-ignore-provides-if-versioned-conflicts | 6 +- test/integration/test-multiarch-allowed | 28 ++++----- test/integration/test-multiarch-foreign | 4 +- .../test-prefer-higher-priority-providers | 2 +- test/integration/test-release-candidate-switching | 2 +- test/integration/test-solver3-alternatives | 2 +- test/integration/test-solver3-evaluation | 4 +- .../test-solver3-show-version-selection | 4 +- .../test-specific-architecture-dependencies | 4 +- ...st-ubuntu-bug-2111792-intersecting-dependencies | 6 +- 33 files changed, 112 insertions(+), 113 deletions(-) diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index 8ef969581..ec788986c 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -53,7 +53,7 @@ Solver::Solver(pkgCache &cache) static_assert(sizeof(Var) == sizeof(map_pointer)); static_assert(sizeof(Var) == sizeof(map_pointer)); // Root state is "true". - rootState->decision = LiftedBool::True; + rootState->assignment = LiftedBool::True; } Solver::~Solver() = default; @@ -149,7 +149,7 @@ inline Var Solver::bestReason(Clause const *clause, Var var) const inline LiftedBool Solver::value(Lit lit) const { - return lit.sign() ? ~(*this)[lit.var()].decision : (*this)[lit.var()].decision; + return lit.sign() ? ~(*this)[lit.var()].assignment : (*this)[lit.var()].assignment; } // Prints an implication graph part of the form A -> B -> C, possibly with "not" @@ -173,31 +173,31 @@ std::string Solver::WhyStr(Var reason) const return outstr; } -std::string Solver::LongWhyStr(Var var, bool decision, const Clause *rclause, std::string prefix, std::unordered_set &seen) const +std::string Solver::LongWhyStr(Var var, bool assignment, const Clause *rclause, std::string prefix, std::unordered_set &seen) const { std::ostringstream out; // Helper function to nicely print more details than just "install/do not install", such as "removal", "upgrade", "downgrade", "install" - auto printSelection = [this](Var var, bool decision) + auto printSelection = [this](Var var, bool assignment) { std::string s; - if (auto pkg = var.Pkg(cache); not decision && pkg && pkg->CurrentVer) + if (auto pkg = var.Pkg(cache); not assignment && pkg && pkg->CurrentVer) strprintf(s, "%s is selected for removal", var.toString(cache).c_str()); - else if (auto ver = var.Ver(cache); decision && ver && ver.ParentPkg().CurrentVer() && ver.ParentPkg().CurrentVer() != ver) + else if (auto ver = var.Ver(cache); assignment && ver && ver.ParentPkg().CurrentVer() && ver.ParentPkg().CurrentVer() != ver) { if (cache.VS->CmpVersion(ver.ParentPkg().CurrentVer().VerStr(), ver.VerStr()) < 0) strprintf(s, "%s is selected as an upgrade", var.toString(cache).c_str()); else strprintf(s, "%s is selected as a downgrade", var.toString(cache).c_str()); } - else if (not decision) + else if (not assignment) strprintf(s, "%s is not selected for install", var.toString(cache).c_str()); else strprintf(s, "%s is selected for install", var.toString(cache).c_str()); return s; }; - // Helper: Recurse into all of the children of the clause and print the decision for them. + // Helper: Recurse into all of the children of the clause and print the assignment for them. auto recurseChildren = [&](const Clause *clause, Var skip = Var()) { if (clause->solutions.empty()) @@ -216,7 +216,7 @@ std::string Solver::LongWhyStr(Var var, bool decision, const Clause *rclause, st // Inverse version selection clauses that select the package if the version is selected, // such as pkg=ver -> pkg, are irrelevant for the user, skip them - if (var.Pkg() && decision && rclause && rclause->group == Group::SelectVersion) + if (var.Pkg() && assignment && rclause && rclause->group == Group::SelectVersion) { var = rclause->reason; rclause = (*this)[var].reason; @@ -225,25 +225,25 @@ std::string Solver::LongWhyStr(Var var, bool decision, const Clause *rclause, st // No reason given, probably a user request or manually installed or essential or whatnot. if (not rclause) { - out << prefix << printSelection(var, decision) << "\n"; + out << prefix << printSelection(var, assignment) << "\n"; return out.str(); } - // We could be called with a decision we tried to make but failed due to a conflict; - // this checks if it is the real decision. - if (value(var) != LiftedBool::Undefined && decision == (value(var) == LiftedBool::True) && (*this)[var].reason == rclause) + // We could be called with a assignment we tried to make but failed due to a conflict; + // this checks if it is the real assignment. + if (value(var) != LiftedBool::Undefined && assignment == (value(var) == LiftedBool::True) && (*this)[var].reason == rclause) { - // If we have seen the real decision before; we dont't need to print it again. + // If we have seen the real assignment before; we dont't need to print it again. if (seen.find(var) != seen.end()) { - out << prefix << printSelection(var, decision) << " as above\n"; + out << prefix << printSelection(var, assignment) << " as above\n"; return out.str(); } seen.insert(var); } // A package was decided "not install" due to a positive clause, so the clause is unsat. - if (not decision && rclause && not rclause->negative) + if (not assignment && rclause && not rclause->negative) { out << prefix << rclause->toString(cache, true) << "\n"; out << prefix << "but none of the choices are installable:\n"; @@ -251,13 +251,13 @@ std::string Solver::LongWhyStr(Var var, bool decision, const Clause *rclause, st return out.str(); } - // Build the strongest path from a root to our decision leaf + // Build the strongest path from a root to our assignment leaf std::vector path; for (auto reason = bestReason(rclause, var); not reason.empty(); reason = bestReason((*this)[reason].reason, reason)) path.push_back(reason); // Render the strong reasoning path - out << prefix << printSelection(var, decision) << " because:\n"; + out << prefix << printSelection(var, assignment) << " because:\n"; auto w = std::to_string(path.size() + 1).size(); size_t i = 1; for (auto it = path.rbegin(); it != path.rend(); ++it, ++i) @@ -273,7 +273,7 @@ std::string Solver::LongWhyStr(Var var, bool decision, const Clause *rclause, st { if ((it + 1) == path.rend() || seen.find(*(it + 1)) == seen.end()) { - out << prefix << (i == 1 ? "" : "1-") << i << ". " << printSelection(*it, state.decision == LiftedBool::True) << " as above\n"; + out << prefix << (i == 1 ? "" : "1-") << i << ". " << printSelection(*it, state.assignment == LiftedBool::True) << " as above\n"; } continue; } @@ -282,13 +282,13 @@ std::string Solver::LongWhyStr(Var var, bool decision, const Clause *rclause, st { out << prefix << std::setw(w) << i << ". " << state.reason->toString(cache, true) << "\n"; if (state.reason->solutions.size() > 1) - out << prefix << std::setw(w) << " " << " [selected " << it->toString(cache) << " for " << (state.decision == LiftedBool::True ? "install" : "remove") << "]\n"; + out << prefix << std::setw(w) << " " << " [selected " << it->toString(cache) << " for " << (state.assignment == LiftedBool::True ? "install" : "remove") << "]\n"; } else - out << prefix << std::setw(w) << i << ". " << printSelection(*it, state.decision == LiftedBool::True) << "\n"; + out << prefix << std::setw(w) << i << ". " << printSelection(*it, state.assignment == LiftedBool::True) << "\n"; } - // Print the leaf. We can't have the leaf in the path because we might be called for an attempted decision + // Print the leaf. We can't have the leaf in the path because we might be called for an attempted assignment // that conflicts with the actual assignment (to simplify: we marked X for not install, then we process Y depends X // and try to mark X and reach the conflict, we are called with "X" and the "Y depends X" clause). out << prefix << std::setw(w) << i << ". " << rclause->toString(cache, true) << "\n"; @@ -344,23 +344,23 @@ bool Solver::Assume(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; + auto assignment = lit.sign() ? LiftedBool::False : LiftedBool::True; - if (state.decision != LiftedBool::Undefined) + if (state.assignment != LiftedBool::Undefined) { - if (state.decision != decisionCast) + if (state.assignment != assignment) { std::ostringstream err; - err << "Unable to satisfy dependencies. Reached two conflicting decisions:" << "\n"; + err << "Unable to satisfy dependencies. Reached two conflicting assignments:" << "\n"; std::unordered_set seen; - err << "1. " << LongWhyStr(lit.var(), state.decision == LiftedBool::True, state.reason, " ", seen).substr(3) << "\n"; + err << "1. " << LongWhyStr(lit.var(), state.assignment == LiftedBool::True, state.reason, " ", seen).substr(3) << "\n"; err << "2. " << LongWhyStr(lit.var(), not lit.sign(), reason, " ", seen).substr(3); return _error->Error("%s", err.str().c_str()); } return true; } - state.decision = decisionCast; + state.assignment = assignment; state.depth = decisionLevel(); state.reason = reason; @@ -455,14 +455,14 @@ void Solver::UndoOne() auto trailItem = trail.back(); if (unlikely(debug >= 4)) - std::cerr << "Undoing a single decision\n"; + std::cerr << "Undoing a single assignment\n"; if (not trailItem.assigned.empty()) { if (unlikely(debug >= 4)) std::cerr << "Unassign " << trailItem.assigned.toString(cache) << "\n"; auto &state = (*this)[trailItem.assigned]; - state.decision = LiftedBool::Undefined; + state.assignment = LiftedBool::Undefined; state.reason = nullptr; state.reasonStr = nullptr; state.depth = 0; @@ -625,7 +625,7 @@ bool Solver::Solve() { std::ostringstream err; - err << "Unable to satisfy dependencies. Reached two conflicting decisions:" << "\n"; + err << "Unable to satisfy dependencies. Reached two conflicting assignments:" << "\n"; std::unordered_set seen; err << "1. " << LongWhyStr(item.clause->reason, true, (*this)[item.clause->reason].reason, " ", seen).substr(3) << "\n"; err << "2. " << LongWhyStr(item.clause->reason, false, item.clause, " ", seen).substr(3); @@ -1399,7 +1399,7 @@ bool DependencySolver::ToDepCache(pkgDepCache &depcache) const } // Command-line -std::string DependencySolver::InternalCliWhy(pkgDepCache &cache, pkgCache::PkgIterator pkg, bool decision) +std::string DependencySolver::InternalCliWhy(pkgDepCache &cache, pkgCache::PkgIterator pkg, bool assignment) { DependencySolver solver(cache.GetCache(), cache.GetPolicy(), EDSP::Request::Flags(0)); // In case nothing has a positive dependency on pkg it may not actually be discovered in a `why-not` @@ -1409,12 +1409,12 @@ std::string DependencySolver::InternalCliWhy(pkgDepCache &cache, pkgCache::PkgIt return ""; std::unordered_set seen; std::string buf; - if (solver[Var(pkg)].decision == LiftedBool::Undefined) + if (solver[Var(pkg)].assignment == LiftedBool::Undefined) return strprintf(buf, "%s is undecided\n", pkg.FullName().c_str()), buf; - if (decision && solver[Var(pkg)].decision != LiftedBool::True) + if (assignment && solver[Var(pkg)].assignment != LiftedBool::True) return strprintf(buf, "%s is not actually marked for install\n", pkg.FullName().c_str()), buf; - if (not decision && solver[Var(pkg)].decision == LiftedBool::True) + if (not assignment && solver[Var(pkg)].assignment == LiftedBool::True) return strprintf(buf, "%s is actually marked for install\n", pkg.FullName().c_str()), buf; - return solver.LongWhyStr(Var(pkg), decision, solver[Var(pkg)].reason, "", seen); + return solver.LongWhyStr(Var(pkg), assignment, solver[Var(pkg)].reason, "", seen); } } // namespace APT::Solver diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h index 23ae49297..94f70fb56 100644 --- a/apt-pkg/solver3.h +++ b/apt-pkg/solver3.h @@ -250,9 +250,9 @@ constexpr Lit Solver::Var::operator~() const return ~Lit(*this); } -inline LiftedBool operator~(LiftedBool decision) +inline LiftedBool operator~(LiftedBool value) { - switch (decision) + switch (value) { case LiftedBool::Undefined: return LiftedBool::Undefined; @@ -385,7 +385,7 @@ class Solver // Assume a literal [[nodiscard]] bool Assume(Lit lit, const Clause *reason = nullptr); - // Enqueue a decision fact + // Enqueue a fact [[nodiscard]] bool Enqueue(Lit lit, const Clause *reason = nullptr); // \brief Solve the dependencies @@ -397,15 +397,15 @@ class Solver /** * \brief Print a long reason string * - * Print a reason as to why `rclause` implies `decision` for the variable `var`. + * Print a reason as to why `rclause` implies `assignment` for the variable `var`. * * \param var The variable to print the reason for - * \param decision The assumed decision to print the reason for (may be different from actual decision if rclause is specified) + * \param assignment The assumed assignment to print the reason for (may be different from actual assignment if rclause is specified) * \param rclause The clause that caused this variable to be marked (or would be marked) * \param prefix A prefix, for indentation purposes, as this is recursive * \param seen A set of seen objects such that the output does not repeat itself (not for safety, it is acyclic) */ - virtual std::string LongWhyStr(Var var, bool decision, const Clause *rclause, std::string prefix, std::unordered_set &seen) const; + virtual std::string LongWhyStr(Var var, bool assignment, const Clause *rclause, std::string prefix, std::unordered_set &seen) const; }; /* @@ -484,7 +484,7 @@ class DependencySolver : public Solver /// \brief Apply the solver result to the depCache [[nodiscard]] bool ToDepCache(pkgDepCache &depcache) const; /// \brief Temporary internal API with external linkage for the `apt why` and `apt why-not` commands. - APT_PUBLIC static std::string InternalCliWhy(pkgDepCache &depcache, pkgCache::PkgIterator Pkg, bool decision); + APT_PUBLIC static std::string InternalCliWhy(pkgDepCache &depcache, pkgCache::PkgIterator Pkg, bool assignment); }; }; // namespace APT::Solver /** @@ -518,7 +518,7 @@ struct APT::Solver::Solver::Work /** * \brief The solver state * - * For each version, the solver records a decision at a certain level. It + * For each version, the solver records a assignment at a certain level. It * maintains an array mapping from version ID to state. */ struct APT::Solver::Solver::State @@ -538,11 +538,10 @@ struct APT::Solver::Solver::State const char *reasonStr{}; - // \brief The depth at which the decision has been taken + // \brief The depth at which the value has been assigned depth_type depth{0}; - // \brief This essentially describes the install state in RFC2119 terms. - LiftedBool decision{LiftedBool::Undefined}; + LiftedBool assignment{LiftedBool::Undefined}; // \brief Flags. struct diff --git a/test/integration/test-apt-get-build-dep-barbarian b/test/integration/test-apt-get-build-dep-barbarian index 8763e8fc7..e30390331 100755 --- a/test/integration/test-apt-get-build-dep-barbarian +++ b/test/integration/test-apt-get-build-dep-barbarian @@ -83,7 +83,7 @@ testsuccessequal "$(installsfoosamey 'amd64' 'i386')" apt build-dep cool-foo -s testsuccessequal "$(installsfoosamey 'i386' 'i386')" apt build-dep bad-amd64-foo -s -a i386 testsuccessequal "$(installsfoosamey 'amd64' 'i386')" apt build-dep bad-armel-foo -s -a i386 testsuccessequal "$(installsfoosamey 'i386' 'i386')" apt build-dep bad-amd64-armel-foo -s -a i386 -testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions: +testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. builddeps:bad-amd64-i386-foo:i386=1 is selected for install 2. builddeps:bad-amd64-i386-foo:i386 Depends foo:i386 but none of the choices are installable: @@ -105,7 +105,7 @@ The following information may help to resolve the situation: The following packages have unmet dependencies: builddeps:bad-amd64-i386-foo:i386 : Depends: foo:i386 E: Unable to correct problems, you have held broken packages.' apt build-dep bad-amd64-i386-foo -s -a i386 --solver internal -testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions: +testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. builddeps:bad-amd64-i386-armel-foo:i386=1 is selected for install 2. builddeps:bad-amd64-i386-armel-foo:i386 Depends foo:i386 but none of the choices are installable: @@ -133,7 +133,7 @@ testsuccessequal "$(installsfoosamey 'i386' 'armel')" apt build-dep bad-amd64-fo testsuccessequal "$(installsfoosamey 'amd64' 'armel')" apt build-dep bad-armel-foo -s -a armel testsuccessequal "$(installsfoosamey 'i386' 'armel')" apt build-dep bad-amd64-armel-foo -s -a armel testsuccessequal "$(installsfoosamey 'armel' 'armel')" apt build-dep bad-amd64-i386-foo -s -a armel -FAILUREMSG="E: Unable to satisfy dependencies. Reached two conflicting decisions: +FAILUREMSG="E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. builddeps:bad-amd64-i386-armel-foo:armel=1 is selected for install 2. builddeps:bad-amd64-i386-armel-foo:armel Depends foo:armel but none of the choices are installable: diff --git a/test/integration/test-apt-get-build-dep-file b/test/integration/test-apt-get-build-dep-file index fd48aef47..71da4d1dd 100755 --- a/test/integration/test-apt-get-build-dep-file +++ b/test/integration/test-apt-get-build-dep-file @@ -160,7 +160,7 @@ cd ../.. testfailureequal 'E: Must specify at least one package to check builddeps for' aptget build-dep testfailuremsg 'W: No architecture information available for armel. See apt.conf(5) APT::Architectures for setup -E: Unable to satisfy dependencies. Reached two conflicting decisions: +E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. builddeps:./foo-1.0:armel=1 is selected for install 2. builddeps:./foo-1.0:armel Depends debhelper:armel (>= 7) but none of the choices are installable: diff --git a/test/integration/test-apt-get-install-deb b/test/integration/test-apt-get-install-deb index 07de975c4..cb423cd59 100755 --- a/test/integration/test-apt-get-install-deb +++ b/test/integration/test-apt-get-install-deb @@ -32,7 +32,7 @@ done buildsimplenativepackage 'foo' 'i386,amd64' '1.0' -testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions: +testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. foo:amd64 is not selected for install because: 1. foo:i386=1.0 is selected for install 2. foo:amd64 Conflicts foo:i386 @@ -181,7 +181,7 @@ echo 'Package: /pkg-/ Pin: release a=experimental Pin-Priority: 501' > rootdir/etc/apt/preferences.d/pinit -testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions: +testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. pkg-last-line-parse:amd64=0 is selected for install 2. pkg-last-line-parse:amd64 PreDepends pkg-as-it-should-be but none of the choices are installable: diff --git a/test/integration/test-apt-get-satisfy b/test/integration/test-apt-get-satisfy index 8d57a98a8..3d215ff86 100755 --- a/test/integration/test-apt-get-satisfy +++ b/test/integration/test-apt-get-satisfy @@ -80,7 +80,7 @@ testrun 'External' 'Reading package lists... Building dependency tree... Execute external solver...' --solver apt -testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions: +testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. satisfy:command-line:i386=1 is selected for install 2. satisfy:command-line:i386 Depends depends (>= 2) but none of the choices are installable: diff --git a/test/integration/test-apt-get-source-only b/test/integration/test-apt-get-source-only index 91a157b47..052aac9b6 100755 --- a/test/integration/test-apt-get-source-only +++ b/test/integration/test-apt-get-source-only @@ -40,7 +40,7 @@ The following information may help to resolve the situation: The following packages have unmet dependencies: builddeps:foo : Depends: foo-bd but it is not installable -E: Unable to satisfy dependencies. Reached two conflicting decisions: +E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. builddeps:foo:amd64=1 is selected for install 2. builddeps:foo:amd64 Depends foo-bd but none of the choices are installable: @@ -56,7 +56,7 @@ The following information may help to resolve the situation: The following packages have unmet dependencies: builddeps:not-foo : Depends: not-foo-bd but it is not installable -E: Unable to satisfy dependencies. Reached two conflicting decisions: +E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. builddeps:not-foo:amd64=1 is selected for install 2. builddeps:not-foo:amd64 Depends not-foo-bd but none of the choices are installable: diff --git a/test/integration/test-apt-install-file-reltag b/test/integration/test-apt-install-file-reltag index 053c785fd..1b113b82f 100755 --- a/test/integration/test-apt-install-file-reltag +++ b/test/integration/test-apt-install-file-reltag @@ -31,7 +31,7 @@ buildsimplenativepackage 'foobar2' 'all' '1' 'unstable' 'Depends: foo (= 5), baz testunsat() { testfailure "$@" - testsuccess grep -E "^E: (Unable to correct problems,|Unable to satisfy dependencies. Reached two conflicting decisions)" "${TMPWORKINGDIRECTORY}/rootdir/tmp/testfailure.output" + testsuccess grep -E "^E: (Unable to correct problems,|Unable to satisfy dependencies. Reached two conflicting assignments)" "${TMPWORKINGDIRECTORY}/rootdir/tmp/testfailure.output" } ln -s "$(readlink -f ./incoming/foobar2_1_all.deb)" foobar.deb diff --git a/test/integration/test-apt-never-markauto-sections b/test/integration/test-apt-never-markauto-sections index 14ce3ae5a..ea80f8b70 100755 --- a/test/integration/test-apt-never-markauto-sections +++ b/test/integration/test-apt-never-markauto-sections @@ -49,7 +49,7 @@ Remv foreignpkg:i386 [1] Remv nosection [1] Remv texteditor [1]' aptget autoremove mydesktop -s -testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions: +testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. bad-texteditor:amd64 is selected for install because: 1. mydesktop:amd64 is selected for install 2. mydesktop:amd64 Depends mydesktop-core diff --git a/test/integration/test-bug-598669-install-postfix-gets-exim-heavy b/test/integration/test-bug-598669-install-postfix-gets-exim-heavy index a87481302..b4ad0f447 100755 --- a/test/integration/test-bug-598669-install-postfix-gets-exim-heavy +++ b/test/integration/test-bug-598669-install-postfix-gets-exim-heavy @@ -8,7 +8,7 @@ configarchitecture "i386" setupaptarchive # FIXME: Should this say selected postifx? -testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions: +testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. postfix:i386=2.7.1-1 is selected for install 2. postfix:i386=2.7.1-1 is not selected for install because: 1. exim4-daemon-light:i386 is selected for install diff --git a/test/integration/test-bug-601961-install-info b/test/integration/test-bug-601961-install-info index be55e76a7..712a9ba14 100755 --- a/test/integration/test-bug-601961-install-info +++ b/test/integration/test-bug-601961-install-info @@ -60,7 +60,7 @@ The following information may help to resolve the situation: The following packages have unmet dependencies: findutils : Depends: essentialpkg but it is not going to be installed -E: Unable to satisfy dependencies. Reached two conflicting decisions: +E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. essentialpkg:i386 is selected for removal 2. essentialpkg:i386 is selected for install because: 1. findutils:i386 is selected for install diff --git a/test/integration/test-bug-612557-garbage-upgrade b/test/integration/test-bug-612557-garbage-upgrade index ced55a5bf..9bc83cce4 100755 --- a/test/integration/test-bug-612557-garbage-upgrade +++ b/test/integration/test-bug-612557-garbage-upgrade @@ -18,7 +18,7 @@ testsuccess aptmark markauto python-uno openoffice.org-common testmarkedauto python-uno openoffice.org-common # The 3.0 solver does not remove openoffice.org-emailmerge because it is manually installed. -testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions: +testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. openoffice.org-common:i386=1:3.2.1-11+squeeze2 is not selected for install because: 1. python-uno:i386=1:3.3.0-2 is selected as an upgrade 2. python-uno:i386=1:3.3.0-2 Depends libreoffice-common diff --git a/test/integration/test-bug-618848-always-respect-user-requests b/test/integration/test-bug-618848-always-respect-user-requests index 6dd77af58..d59e458ce 100755 --- a/test/integration/test-bug-618848-always-respect-user-requests +++ b/test/integration/test-bug-618848-always-respect-user-requests @@ -14,7 +14,7 @@ insertpackage 'unstable' 'exim4-daemon-heavy' 'all' '1.0' 'Depends: libdb4.8' setupaptarchive # This does not work in 3.0 solver: We do not remove manually installed packages. -testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions: +testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. exim4-daemon-light:i386 is selected for install 2. exim4-daemon-light:i386 Depends libdb4.8 but none of the choices are installable: diff --git a/test/integration/test-bug-632221-cross-dependency-satisfaction b/test/integration/test-bug-632221-cross-dependency-satisfaction index 6e39b384c..903133cc7 100755 --- a/test/integration/test-bug-632221-cross-dependency-satisfaction +++ b/test/integration/test-bug-632221-cross-dependency-satisfaction @@ -35,7 +35,7 @@ insertsource 'unstable' 'source-specific-armel' 'armel' '1' 'Build-Depends: spec setupaptarchive -testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions: +testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. builddeps:forbidden-no:armel=1 is selected for install 2. builddeps:forbidden-no:armel Depends amdboot:any but none of the choices are installable: @@ -53,7 +53,7 @@ The following packages have unmet dependencies: builddeps:forbidden-no:armel : Depends: amdboot:any but it is not installable E: Unable to correct problems, you have held broken packages.' aptget build-dep forbidden-no -s -a armel --solver internal -testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions: +testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. builddeps:forbidden-same:armel=1 is selected for install 2. builddeps:forbidden-same:armel Depends libc6:any but none of the choices are installable: @@ -71,7 +71,7 @@ The following packages have unmet dependencies: builddeps:forbidden-same:armel : Depends: libc6:any but it is not installable E: Unable to correct problems, you have held broken packages.' aptget build-dep forbidden-same -s -a armel --solver internal -testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions: +testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. builddeps:forbidden-foreign:armel=1 is selected for install 2. builddeps:forbidden-foreign:armel Depends doxygen:any but none of the choices are installable: diff --git a/test/integration/test-bug-675449-essential-are-protected b/test/integration/test-bug-675449-essential-are-protected index c8e832d72..d7e284ece 100755 --- a/test/integration/test-bug-675449-essential-are-protected +++ b/test/integration/test-bug-675449-essential-are-protected @@ -125,7 +125,7 @@ The following information may help to resolve the situation: The following packages have unmet dependencies: foo : Depends: libfoo but it is not going to be installed -E: Unable to satisfy dependencies. Reached two conflicting decisions: +E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. libfoo:amd64 is selected for removal 2. libfoo:amd64 is selected for install because: 1. foo:amd64 is selected for install diff --git a/test/integration/test-bug-683786-build-dep-on-virtual-packages b/test/integration/test-bug-683786-build-dep-on-virtual-packages index a682a2f1a..42d4162aa 100755 --- a/test/integration/test-bug-683786-build-dep-on-virtual-packages +++ b/test/integration/test-bug-683786-build-dep-on-virtual-packages @@ -41,7 +41,7 @@ The following NEW packages will be installed: Inst po-debconf (1 unstable [all]) Conf po-debconf (1 unstable [all])' aptget build-dep dash -s -testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions: +testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. builddeps:dash:armel=1 is selected for install 2. builddeps:dash:armel Depends po-debconf:armel but none of the choices are installable: @@ -59,7 +59,7 @@ The following packages have unmet dependencies: builddeps:dash:armel : Depends: po-debconf:armel but it is not installable E: Unable to correct problems, you have held broken packages.' aptget build-dep -aarmel dash -s --solver internal -testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions: +testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. builddeps:diffutils:armel=1 is selected for install 2. builddeps:diffutils:armel Depends texi2html:armel but none of the choices are installable: @@ -86,7 +86,7 @@ The following NEW packages will be installed: Inst libselinux1-dev (1 unstable [amd64]) Conf libselinux1-dev (1 unstable [amd64])" aptget build-dep sed -s -testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions: +testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. builddeps:sed:armel=1 is selected for install 2. builddeps:sed:armel Depends libselinux-dev:armel but none of the choices are installable: diff --git a/test/integration/test-bug-723586-any-stripped-in-single-arch b/test/integration/test-bug-723586-any-stripped-in-single-arch index 191d75647..20116a653 100755 --- a/test/integration/test-bug-723586-any-stripped-in-single-arch +++ b/test/integration/test-bug-723586-any-stripped-in-single-arch @@ -41,7 +41,7 @@ The following information may help to resolve the situation: The following packages have unmet dependencies: python-mips : Depends: python3:mips but it is not installable -E: Unable to satisfy dependencies. Reached two conflicting decisions: +E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. python-mips:amd64=3 is selected for install 2. python-mips:amd64 Depends python3:mips but none of the choices are installable: diff --git a/test/integration/test-bug-735967-lib32-to-i386-unavailable b/test/integration/test-bug-735967-lib32-to-i386-unavailable index 83992e386..bd3172d68 100755 --- a/test/integration/test-bug-735967-lib32-to-i386-unavailable +++ b/test/integration/test-bug-735967-lib32-to-i386-unavailable @@ -50,7 +50,7 @@ Remv lib32nss-mdns [0.9-1] Inst libnss-mdns [0.9-1] (0.10-6 unstable [amd64]) Conf libnss-mdns (0.10-6 unstable [amd64])' aptget dist-upgrade -s --solver internal -testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions: +testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. libfoo:amd64 is selected for install because: 1. foo:amd64=1 is selected for install 2. foo:amd64 Depends libfoo diff --git a/test/integration/test-bug-745046-candidate-propagation-fails b/test/integration/test-bug-745046-candidate-propagation-fails index f4fc15e0e..3c02f55a6 100755 --- a/test/integration/test-bug-745046-candidate-propagation-fails +++ b/test/integration/test-bug-745046-candidate-propagation-fails @@ -40,7 +40,7 @@ The following information may help to resolve the situation: The following packages have unmet dependencies: gedit : Depends: common (>= 2) but it is not installable -E: Unable to satisfy dependencies. Reached two conflicting decisions: +E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. gedit:amd64=2 is selected as an upgrade 2. gedit:amd64=2 Depends common (>= 2) but none of the choices are installable: diff --git a/test/integration/test-bug-961266-hold-means-hold b/test/integration/test-bug-961266-hold-means-hold index 08c74e052..e95bb6ed6 100755 --- a/test/integration/test-bug-961266-hold-means-hold +++ b/test/integration/test-bug-961266-hold-means-hold @@ -89,7 +89,7 @@ The following information may help to resolve the situation: The following packages have unmet dependencies: git-ng : Depends: git (> 1:2.26.2) -E: Unable to satisfy dependencies. Reached two conflicting decisions: +E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. git-ng:amd64=1:2.26.2-1 is selected for install 2. git-ng:amd64 Depends git (> 1:2.26.2) and Depends git (< 1:2.26.2-.) but none of the choices are installable: @@ -135,7 +135,7 @@ The following information may help to resolve the situation: The following packages have unmet dependencies: git-ng : Depends: git (> 1:2.26.2) -E: Unable to satisfy dependencies. Reached two conflicting decisions: +E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. git-ng:amd64=1:2.26.2-1 is selected for install 2. git-ng:amd64 Depends git (> 1:2.26.2) and Depends git (< 1:2.26.2-.) but none of the choices are installable: @@ -181,7 +181,7 @@ The following information may help to resolve the situation: The following packages have unmet dependencies: git-ng : Depends: git (> 1:2.26.2) -E: Unable to satisfy dependencies. Reached two conflicting decisions: +E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. git-ng:amd64=1:2.26.2-1 is selected for install 2. git-ng:amd64 Depends git (> 1:2.26.2) and Depends git (< 1:2.26.2-.) but none of the choices are installable: diff --git a/test/integration/test-explore-or-groups-in-markinstall b/test/integration/test-explore-or-groups-in-markinstall index 77f769e77..1b5cc2823 100755 --- a/test/integration/test-explore-or-groups-in-markinstall +++ b/test/integration/test-explore-or-groups-in-markinstall @@ -161,7 +161,7 @@ testfailureequal "$BADSOLVETEXT3 The following packages have unmet dependencies: bad-upgrade-level1 : Depends: bad-upgrade-level0 (>= 2) but 1 is to be installed Depends: unneeded2 but it is not going to be installed -E: Unable to satisfy dependencies. Reached two conflicting decisions: +E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. bad-upgrade-level0:amd64=2 is selected as an upgrade because: 1. bad-upgrade-level1:amd64=2 is selected as an upgrade 2. bad-upgrade-level1:amd64=2 Depends bad-upgrade-level0 (>= 2) @@ -177,7 +177,7 @@ testfailureequal "$BADSOLVETEXT3 The following packages have unmet dependencies: bad-conflict-level2 : Depends: bad-conflict-level1 but it is not going to be installed Depends: unneeded2 but it is not going to be installed -E: Unable to satisfy dependencies. Reached two conflicting decisions: +E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. bad-conflict-level1:amd64 is selected for install because: 1. bad-conflict-level2:amd64=1 is selected for install 2. bad-conflict-level2:amd64 Depends bad-conflict-level1 diff --git a/test/integration/test-handling-broken-orgroups b/test/integration/test-handling-broken-orgroups index 5c882b516..184c84377 100755 --- a/test/integration/test-handling-broken-orgroups +++ b/test/integration/test-handling-broken-orgroups @@ -47,7 +47,7 @@ Inst coolstuff2 (1.0-1 unstable [all]) Conf stuff (1.0-1 unstable [all]) Conf coolstuff2 (1.0-1 unstable [all])' aptget install coolstuff2 -s -testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions: +testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. coolstuff-broken:i386=1.0-1 is selected for install 2. coolstuff-broken:i386 Depends cool2 | stuff2 but none of the choices are installable: @@ -99,7 +99,7 @@ Inst coolstuff-provided (1.0-1 unstable [all]) Conf extrastuff (1.0-1 unstable [all]) Conf coolstuff-provided (1.0-1 unstable [all])' aptget install coolstuff-provided -s -testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions: +testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. extrastuff:i386=1.0-1 is not selected for install 2. extrastuff:i386=1.0-1 is selected for install because: 1. coolstuff-provided-broken:i386=1.0-1 is selected for install diff --git a/test/integration/test-ignore-provides-if-versioned-breaks b/test/integration/test-ignore-provides-if-versioned-breaks index 87e609bef..a7a7d88ed 100755 --- a/test/integration/test-ignore-provides-if-versioned-breaks +++ b/test/integration/test-ignore-provides-if-versioned-breaks @@ -32,7 +32,7 @@ insertpackage 'unstable' 'foo-same-breaker-none' 'i386' '1.0' 'Breaks: foo-same' setupaptarchive -testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions: +testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. foo-breaker-none:i386=1.0 is selected for install 2. foo-breaker-none:i386 is not selected for install because: 1. foo-provider:i386=1.0 is selected for install @@ -76,7 +76,7 @@ Conf foo (4.0 unstable [i386]) Conf foo-breaker-3 (1.0 unstable [i386]) Conf foo-provider (1.0 unstable [i386])' aptget install foo-provider foo-breaker-3 -s -testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions: +testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. foo-foreign-provider:i386=1.0 is selected for install 2. foo-foreign-provider:i386=1.0 is not selected for install because: 1. foo-foreign-breaker-none:i386=1.0 is selected for install @@ -120,7 +120,7 @@ Conf foo-foreign:amd64 (4.0 unstable [amd64]) Conf foo-foreign-breaker-3 (1.0 unstable [i386]) Conf foo-foreign-provider (1.0 unstable [i386])' aptget install foo-foreign-provider foo-foreign-breaker-3 -s -testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions: +testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. foo-same-breaker-none:i386=1.0 is selected for install 2. foo-same-breaker-none:i386 is not selected for install because: 1. foo-same-provider:i386=1.0 is selected for install diff --git a/test/integration/test-ignore-provides-if-versioned-conflicts b/test/integration/test-ignore-provides-if-versioned-conflicts index cdf69656e..517436d57 100755 --- a/test/integration/test-ignore-provides-if-versioned-conflicts +++ b/test/integration/test-ignore-provides-if-versioned-conflicts @@ -33,7 +33,7 @@ insertpackage 'unstable' 'foo-same-breaker-none' 'i386' '1.0' 'Conflicts: foo-sa setupaptarchive -testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions: +testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. foo-breaker-none:i386=1.0 is selected for install 2. foo-breaker-none:i386 is not selected for install because: 1. foo-provider:i386=1.0 is selected for install @@ -77,7 +77,7 @@ Conf foo (4.0 unstable [i386]) Conf foo-breaker-3 (1.0 unstable [i386]) Conf foo-provider (1.0 unstable [i386])' aptget install foo-provider foo-breaker-3 -s -testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions: +testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. foo-foreign-provider:i386=1.0 is selected for install 2. foo-foreign-provider:i386=1.0 is not selected for install because: 1. foo-foreign-breaker-none:i386=1.0 is selected for install @@ -121,7 +121,7 @@ Conf foo-foreign:amd64 (4.0 unstable [amd64]) Conf foo-foreign-breaker-3 (1.0 unstable [i386]) Conf foo-foreign-provider (1.0 unstable [i386])' aptget install foo-foreign-provider foo-foreign-breaker-3 -s -testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions: +testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. foo-same-breaker-none:i386=1.0 is selected for install 2. foo-same-breaker-none:i386 is not selected for install because: 1. foo-same-provider:i386=1.0 is selected for install diff --git a/test/integration/test-multiarch-allowed b/test/integration/test-multiarch-allowed index 8c244ed57..c40de6cc8 100755 --- a/test/integration/test-multiarch-allowed +++ b/test/integration/test-multiarch-allowed @@ -64,7 +64,7 @@ Inst needsfoo:i386 (1 unstable [i386]) Conf foo:i386 (1 unstable [i386]) Conf needsfoo:i386 (1 unstable [i386])' aptget install needsfoo:i386 -s # FIXME: same problem, but two different unmet dependency messages depending on install order -testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions: +testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. needsfoo:i386=1 is selected for install 2. needsfoo:i386 Depends foo:i386 but none of the choices are installable: @@ -76,7 +76,7 @@ The following packages have unmet dependencies: foo : Conflicts: foo:i386 but 1 is to be installed foo:i386 : Conflicts: foo but 1 is to be installed E: Unable to correct problems, you have held broken packages." aptget install needsfoo:i386 foo:amd64 -s --solver internal -testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions: +testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. needsfoo:i386=1 is selected for install 2. needsfoo:i386 Depends foo:i386 but none of the choices are installable: @@ -87,7 +87,7 @@ testfailureequal "$BADPREFIX The following packages have unmet dependencies: needsfoo:i386 : Depends: foo:i386 but it is not installable E: Unable to correct problems, you have held broken packages." aptget install foo:amd64 needsfoo:i386 -s --solver internal -testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions: +testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. needsfoo:amd64=1 is selected for install 2. needsfoo:amd64 Depends foo but none of the choices are installable: @@ -153,7 +153,7 @@ if [ "$APT_SOLVER" != "internal" ]; then NEEDSFOO2NATIVE="$BADPREFIX The following packages have unmet dependencies: needsfoover2 : Depends: foo:any (>= 2) -E: Unable to satisfy dependencies. Reached two conflicting decisions: +E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. needsfoover2:amd64=1 is selected for install 2. needsfoover2:amd64 Depends foo:any (>= 2) but none of the choices are installable: @@ -161,7 +161,7 @@ E: Unable to satisfy dependencies. Reached two conflicting decisions: NEEDSFOO2FOREIGN="$BADPREFIX The following packages have unmet dependencies: needsfoover2:i386 : Depends: foo:any (>= 2) -E: Unable to satisfy dependencies. Reached two conflicting decisions: +E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. needsfoover2:i386=1 is selected for install 2. needsfoover2:i386 Depends foo:any (>= 2) but none of the choices are installable: @@ -182,27 +182,27 @@ testfailureequal "$NEEDSFOO2FOREIGN" aptget install needsfoover2:i386 foo:i386 - testfailureequal "$NEEDSFOO2NATIVE" aptget install needsfoover2 foo:i386 -s solveableinsinglearch2() { - testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions: + testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. foo:amd64=1 is selected for install 2. foo:amd64=1 is not selected for install because: 1. hatesfoo:amd64=1 is selected for install 2. hatesfoo:amd64 Conflicts foo' aptget install foo hatesfoo -s --solver 3.0 if [ "$(getarchitectures)" = "amd64 " ]; then - testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions: + testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. foo:amd64=1 is selected for install 2. foo:amd64=1 is not selected for install because: 1. hatesfooany:amd64=1 is selected for install 2. hatesfooany:amd64 Conflicts foo:any' aptget install foo hatesfooany -s --solver 3.0 else - testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions: + testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. foo:amd64=1 is selected for install 2. foo:amd64=1 is not selected for install because: 1. hatesfooany:amd64=1 is selected for install 2. hatesfooany:amd64 Conflicts foo:any [selected hatesfooany:amd64]' aptget install foo hatesfooany -s --solver 3.0 fi - testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions: + testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. foo:amd64=1 is selected for install 2. foo:amd64=1 is not selected for install because: 1. hatesfoonative:amd64=1 is selected for install @@ -219,7 +219,7 @@ The following packages have unmet dependencies: E: Unable to correct problems, you have held broken packages." aptget install foo hatesfoonative -s --solver internal } solveableinsinglearch2 -testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions: +testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. foo:i386=1 is selected for install 2. foo:i386=1 is not selected for install because: 1. hatesfoo:amd64=1 is selected for install @@ -228,7 +228,7 @@ testfailureequal "$BADPREFIX The following packages have unmet dependencies: hatesfoo : Conflicts: foo:i386 but 1 is to be installed E: Unable to correct problems, you have held broken packages." aptget install foo:i386 hatesfoo -s --solver internal -testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions: +testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. foo:i386=1 is selected for install 2. foo:i386=1 is not selected for install because: 1. hatesfooany:amd64=1 is selected for install @@ -248,7 +248,7 @@ Inst hatesfoonative (1 unstable [amd64]) Conf foo:i386 (1 unstable [i386]) Conf hatesfoonative (1 unstable [amd64])' aptget install foo:i386 hatesfoonative -s -testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions: +testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. needscoolfoo:i386=1 is selected for install 2. needscoolfoo:i386 Depends coolfoo:i386 but none of the choices are installable: @@ -325,7 +325,7 @@ Inst needscoolfoover1 (1 unstable [amd64]) Conf coolfoo (1 unstable [amd64]) Conf coolfoover (1 unstable [amd64]) Conf needscoolfoover1 (1 unstable [amd64])' aptget install needscoolfoover1 -s - testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions: + testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. needscoolfoover2:amd64=1 is selected for install 2. needscoolfoover2:amd64 Depends coolfoo:any (>= 2) but none of the choices are installable: @@ -334,7 +334,7 @@ Conf needscoolfoover1 (1 unstable [amd64])' aptget install needscoolfoover1 -s The following packages have unmet dependencies: needscoolfoover2 : Depends: coolfoo:any (>= 2) E: Unable to correct problems, you have held broken packages." aptget install needscoolfoover2 -s --solver internal - testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions: + testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. needscoolfoover3:amd64=1 is selected for install 2. needscoolfoover3:amd64 Depends coolfoo:any (>= 2) but none of the choices are installable: diff --git a/test/integration/test-multiarch-foreign b/test/integration/test-multiarch-foreign index a04b854a5..e71c1ae5a 100755 --- a/test/integration/test-multiarch-foreign +++ b/test/integration/test-multiarch-foreign @@ -179,7 +179,7 @@ distribution that some required packages have not yet been created or been moved out of Incoming. The following information may help to resolve the situation: ' - testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions: + testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. hates-foo:amd64=1.0 is selected for install 2. hates-foo:amd64 is not selected for install because: 1. ${1%:*}:$4=1.0 is selected for install @@ -191,7 +191,7 @@ The following packages have unmet dependencies: Conflicts: foo:i386 Conflicts: foo:armel E: Unable to correct problems, you have held broken packages." aptget install $1 hates-foo -s --solver internal - testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions: + testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. foo:$4=1.0 is selected for install 2. foo:$4=1.0 is not selected for install because: 1. $2:amd64=1.0 is selected for install diff --git a/test/integration/test-prefer-higher-priority-providers b/test/integration/test-prefer-higher-priority-providers index 87954c5d4..07a0033b1 100755 --- a/test/integration/test-prefer-higher-priority-providers +++ b/test/integration/test-prefer-higher-priority-providers @@ -91,7 +91,7 @@ Inst awesome (1 unstable [all]) Conf baz (1 unstable [all]) Conf awesome (1 unstable [all])" aptget install awesome foo- bar- -s -testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions: +testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. baz:$native is not selected for install 2. baz:$native=1 is selected for install because: 1. awesome:$native=1 is selected for install diff --git a/test/integration/test-release-candidate-switching b/test/integration/test-release-candidate-switching index 18396252f..16eb4f1ec 100755 --- a/test/integration/test-release-candidate-switching +++ b/test/integration/test-release-candidate-switching @@ -448,7 +448,7 @@ The following information may help to resolve the situation: The following packages have unmet dependencies: uninstallablepkg : Depends: libmtp8 (>= 10:0.20.1) but it is not going to be installed Depends: amarok-utils (= 2.3.2-2+exp) but it is not going to be installed -E: Unable to satisfy dependencies. Reached two conflicting decisions: +E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. amarok-utils:i386=2.3.2-2+exp is not selected for install 2. amarok-utils:i386=2.3.2-2+exp is selected for install because: 1. uninstallablepkg:i386=1.0 is selected for install diff --git a/test/integration/test-solver3-alternatives b/test/integration/test-solver3-alternatives index 8a3645f82..45b4395cd 100755 --- a/test/integration/test-solver3-alternatives +++ b/test/integration/test-solver3-alternatives @@ -15,7 +15,7 @@ insertpackage 'unstable' 'ba' 'all' '3' 'Depends: bay' insertpackage 'unstable' 'bb' 'all' '3' 'Depends: bby' setupaptarchive -testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions: +testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. bb:amd64 is selected for install because: 1. unsat:amd64=3 is selected for install 2. unsat:amd64 Depends a | b diff --git a/test/integration/test-solver3-evaluation b/test/integration/test-solver3-evaluation index f5a10f5fa..06edb4962 100755 --- a/test/integration/test-solver3-evaluation +++ b/test/integration/test-solver3-evaluation @@ -142,7 +142,7 @@ The following packages have unmet dependencies: a : Depends: c but it is not going to be installed E: Unable to correct problems, you have held broken packages. E: The following information from --solver 3.0 may provide additional context: - Unable to satisfy dependencies. Reached two conflicting decisions: + Unable to satisfy dependencies. Reached two conflicting assignments: 1. a:amd64=3 is selected for install 2. a:amd64 Depends c but none of the choices are installable: @@ -176,7 +176,7 @@ Package: apt Title: Failure: The 3.0 solver did not find a result SourcePackage: apt ErrorMessage: - Unable to satisfy dependencies. Reached two conflicting decisions: + Unable to satisfy dependencies. Reached two conflicting assignments: 1. a:amd64=3 is selected for install . 2. a:amd64 Depends c diff --git a/test/integration/test-solver3-show-version-selection b/test/integration/test-solver3-show-version-selection index 0de6600af..e0453feed 100755 --- a/test/integration/test-solver3-show-version-selection +++ b/test/integration/test-solver3-show-version-selection @@ -14,7 +14,7 @@ insertpackage 'installed,unstable' 'libgcc-s1' 'amd64' '14.2.0-18' 'Multi-Arch: setupaptarchive -testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions: +testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. libc6:s390x is selected for install because: 1. sbuild-build-depends-main-dummy:s390x=0.invalid.0 is selected for install 2. sbuild-build-depends-main-dummy:s390x Depends libgstreamer1.0-dev:s390x @@ -26,7 +26,7 @@ testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decis 2. libgcc-s1:amd64 is available in version 14.2.0-18 3. libgcc-s1:s390x Breaks libgcc-s1 (!= 14.2.0-17)" apt install sbuild-build-depends-main-dummy --solver 3.0 libgcc-s1 -s -testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions: +testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. libc6:s390x is selected for install because: 1. sbuild-build-depends-main-dummy:s390x=0.invalid.0 is selected for install 2. sbuild-build-depends-main-dummy:s390x Depends libgstreamer1.0-dev:s390x diff --git a/test/integration/test-specific-architecture-dependencies b/test/integration/test-specific-architecture-dependencies index b9ce155de..3ffa3669c 100755 --- a/test/integration/test-specific-architecture-dependencies +++ b/test/integration/test-specific-architecture-dependencies @@ -194,7 +194,7 @@ The following NEW packages will be installed: Inst foo-depender (1 unstable [amd64]) Conf foo-depender (1 unstable [amd64])' aptget install foo-depender -s -testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions: +testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. foo-depender:i386=1 is selected for install 2. foo-depender:i386 Depends foo:i386 but none of the choices are installable: @@ -317,7 +317,7 @@ Remv libold [1] Inst breaker-x64 (1 unstable [amd64]) Conf breaker-x64 (1 unstable [amd64])' aptget install breaker-x64:amd64 -s -testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions: +testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. depender-x32:amd64=1 is selected for install 2. depender-x32:amd64 Depends libc6:i386 but none of the choices are installable: diff --git a/test/integration/test-ubuntu-bug-2111792-intersecting-dependencies b/test/integration/test-ubuntu-bug-2111792-intersecting-dependencies index 4d32c0130..7e770a30d 100755 --- a/test/integration/test-ubuntu-bug-2111792-intersecting-dependencies +++ b/test/integration/test-ubuntu-bug-2111792-intersecting-dependencies @@ -96,7 +96,7 @@ The following information may help to resolve the situation: The following packages have unmet dependencies: git-ng : Depends: git (> 1:2.26.2) -E: Unable to satisfy dependencies. Reached two conflicting decisions: +E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. git-ng:amd64=1:2.26.2-1 is selected for install 2. git-ng:amd64 Depends git (> 1:2.26.2) and Depends git (< 1:2.26.2-.) but none of the choices are installable: @@ -129,7 +129,7 @@ The following information may help to resolve the situation: The following packages have unmet dependencies: git-ng : Depends: git (> 1:2.26.2) -E: Unable to satisfy dependencies. Reached two conflicting decisions: +E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. git-ng:amd64=1:2.26.2-1 is selected for install 2. git-ng:amd64 Depends git (> 1:2.26.2) and Depends git (< 1:2.26.2-.) but none of the choices are installable: @@ -163,7 +163,7 @@ The following information may help to resolve the situation: The following packages have unmet dependencies: git-ng : Depends: git (> 1:2.26.2) -E: Unable to satisfy dependencies. Reached two conflicting decisions: +E: Unable to satisfy dependencies. Reached two conflicting assignments: 1. git-ng:amd64=1:2.26.2-1 is selected for install 2. git-ng:amd64 Depends git (> 1:2.26.2) and Depends git (< 1:2.26.2-.) but none of the choices are installable: -- cgit v1.2.3-70-g09d2 From ee82f420e7a303b5d92302134401e465b386de94 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Sun, 28 Dec 2025 16:59:17 +0100 Subject: solver3: Rename depth to level Matches the rename of depth() to decisionLevel() at a shorter name. --- apt-pkg/solver3.cc | 14 +++++++------- apt-pkg/solver3.h | 32 ++++++++++++++++---------------- 2 files changed, 23 insertions(+), 23 deletions(-) diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index ec788986c..eb142435b 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -127,7 +127,7 @@ std::string Solver::Work::toString(pkgCache &cache) const out << "Erased "; if (clause->optional) out << "Optional "; - out << "Item (" << ssize_t(size <= clause->solutions.size() ? size : -1) << "@" << depth << ") "; + out << "Item (" << ssize_t(size <= clause->solutions.size() ? size : -1) << "@" << level << ") "; out << clause->toString(cache); return out.str(); } @@ -361,7 +361,7 @@ bool Solver::Enqueue(Lit lit, const Clause *reason) } state.assignment = assignment; - state.depth = decisionLevel(); + state.level = decisionLevel(); state.reason = reason; // FIXME: Adjust call to bestReason to use lit @@ -465,7 +465,7 @@ void Solver::UndoOne() state.assignment = LiftedBool::Undefined; state.reason = nullptr; state.reasonStr = nullptr; - state.depth = 0; + state.level = 0; } if (auto work = trailItem.work) @@ -513,12 +513,12 @@ bool Solver::Pop() for (; itemsToUndo; --itemsToUndo) UndoOne(); - // We need to remove any work that is at a higher depth. + // We need to remove any work that is at a higher level. // FIXME: We should just mark the entries as erased and only do a compaction // of the heap once we have a lot of erased entries in it. trailLim.pop_back(); work.erase(std::remove_if(work.begin(), work.end(), [this](Work &w) -> bool - { return w.depth > decisionLevel() || w.erased; }), + { return w.level > decisionLevel() || w.erased; }), work.end()); std::make_heap(work.begin(), work.end()); @@ -1027,10 +1027,10 @@ void DependencySolver::Discover(Var var) } } - // Recursively discover everything else that is not already FALSE by fact (False at depth 0) + // Recursively discover everything else that is not already FALSE by fact (False at level 0) for (auto const &clause : state.clauses) for (auto const &var : clause->solutions) - if (value(var) != LiftedBool::False || (*this)[var].depth > 0) + if (value(var) != LiftedBool::False || (*this)[var].level > 0) discoverQ.push(var); } } diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h index 94f70fb56..f66b3cf62 100644 --- a/apt-pkg/solver3.h +++ b/apt-pkg/solver3.h @@ -281,16 +281,16 @@ class Solver struct Work; struct Trail; - // \brief Type to record depth at. This may very well be a 16-bit + // \brief Type to record decision level at. This may very well be a 16-bit // unsigned integer, then change Solver::State::LiftedBool to be a // uint16_t class enum as well to get a more compact space. - using depth_type = unsigned int; + using level_type = unsigned int; // Documentation template using heap = std::vector; - static_assert(sizeof(depth_type) >= sizeof(map_id_t)); + static_assert(sizeof(level_type) >= sizeof(map_id_t)); // Cache is needed to construct Iterators from Version objects we see pkgCache &cache; @@ -338,7 +338,7 @@ class Solver std::vector trail; /// \brief Separator indices for different decision levels in trail - std::vector trailLim{}; + std::vector trailLim{}; // \brief Propagation queue std::queue propQ; @@ -361,10 +361,10 @@ class Solver // \brief Propagate all pending propagations [[nodiscard]] bool Propagate(); - // \brief Return the current depth (.size() with casting) - depth_type decisionLevel() + // \brief Return the current level (.size() with casting) + level_type decisionLevel() { - return static_cast(trailLim.size()); + return static_cast(trailLim.size()); } inline Var bestReason(Clause const *clause, Var var) const; inline LiftedBool value(Lit lit) const; @@ -491,7 +491,7 @@ class DependencySolver : public Solver * \brief A single work item * * A work item is a positive dependency that still needs to be resolved. Work - * is ordered, by depth, length of solutions, and optionality. + * is ordered, by level, length of solutions, and optionality. * * The work can always be recalculated from the state by iterating over dependencies * of all packages in there, finding solutions to them, and then adding all dependencies @@ -501,8 +501,8 @@ struct APT::Solver::Solver::Work { const Clause *clause; - // \brief The depth at which the item has been added - depth_type depth; + // \brief The level at which the item has been added + level_type level; /// Number of valid choices at insertion time size_t size{0}; @@ -512,7 +512,7 @@ struct APT::Solver::Solver::Work 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) {} + inline Work(const Clause *clause, level_type level) : clause(clause), level(level) {} }; /** @@ -526,11 +526,11 @@ struct APT::Solver::Solver::State // \brief The reason for causing this state (invalid for Undefined). // // Rejects may have been caused by a later state. Consider we select - // between x1 and x2 in depth = N. If we now find dependencies of x1 + // between x1 and x2 in level = N. If we now find dependencies of x1 // leading to a conflict with a package in K < N, we will record all - // of them as REJECT in depth = K. + // of them as REJECT in level = K. // - // You can follow the reason chain upwards as long as the depth + // You can follow the reason chain upwards as long as the level // doesn't increase to unwind. // // Vars < 0 are package ID, reasons > 0 are version IDs. @@ -538,8 +538,8 @@ struct APT::Solver::Solver::State const char *reasonStr{}; - // \brief The depth at which the value has been assigned - depth_type depth{0}; + // \brief The level at which the value has been assigned + level_type level{0}; LiftedBool assignment{LiftedBool::Undefined}; -- cgit v1.2.3-70-g09d2 From d0643f993d3c6c42ea10d5ce3a02d964b7693a7f Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Sun, 28 Dec 2025 21:42:32 +0100 Subject: solver3: Re-use existing error message code in Solve() We can just re-use Enqueue() here to produce our conflict message why am I being silly and duplicate this. --- apt-pkg/solver3.cc | 11 ++++------- 1 file changed, 4 insertions(+), 7 deletions(-) diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index eb142435b..54f31a797 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -623,13 +623,10 @@ bool Solver::Solve() } if (not foundSolution && not item.clause->optional) { - std::ostringstream err; - - err << "Unable to satisfy dependencies. Reached two conflicting assignments:" << "\n"; - std::unordered_set seen; - err << "1. " << LongWhyStr(item.clause->reason, true, (*this)[item.clause->reason].reason, " ", seen).substr(3) << "\n"; - err << "2. " << LongWhyStr(item.clause->reason, false, item.clause, " ", seen).substr(3); - _error->Error("%s", err.str().c_str()); + // Enqueue produces the right error message for us here, given that reason has been assigned true already... + assert(value(item.clause->reason) == LiftedBool::True); + bool res = Enqueue(~item.clause->reason, item.clause); + assert(not res); if (not Pop()) return false; } -- cgit v1.2.3-70-g09d2 From 6ceaa78088ebdaea6cb887a7e8066fc29e0f984d Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Mon, 29 Dec 2025 12:04:22 +0100 Subject: macros: Introduce must_succeed() macro This is like assert() but never compiled out so can be used with function calls that have side effects. --- apt-pkg/contrib/macros.h | 8 ++++++++ 1 file changed, 8 insertions(+) diff --git a/apt-pkg/contrib/macros.h b/apt-pkg/contrib/macros.h index 08e7aeb72..1a76ef60a 100644 --- a/apt-pkg/contrib/macros.h +++ b/apt-pkg/contrib/macros.h @@ -33,6 +33,14 @@ #define likely(x) (x) #define unlikely(x) (x) #endif + +// Asserts that the result of expr is true +#define must_succeed(expr) ({ \ + auto result = (expr); \ + if (unlikely(not result)) \ + fprintf(stderr, "%s:%d: %s: Assertion `%s` failed.\n", __FILE__, __LINE__, __FUNCTION__, #expr), abort(); \ + result; \ +}) #endif #if APT_GCC_VERSION >= 0x0300 -- cgit v1.2.3-70-g09d2 From f8dd5ea23c6a7fccf643329c50ae1f11f48b1a09 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Tue, 20 May 2025 13:13:45 +0200 Subject: solver3: Remove Push() and refactor Solve() This method is no longer needed technically speaking, we should use Assume() instead. It turns out that there is a slight bug in the propagation and some clauses that are unit end up on the heap rather than having been propagated away, so we temporarily need to keep an if for that around. To accomodate the switch from Push() to Assume() we need to make sure that the work item is pushed to our trail *after* we have assumed it, such that reverting pushes it back to the work heap. Refactor the code to consistently use Assume() rather than supporting Enqueue(), this vastly simplifies things. This is not fully accurate in the current model and leads to unnecessary decision levels, since sometimes we seem to be reaching unit clauses here. This preserves traversal order by first removing the item from the heap and then adding it back if we need to solve it again. --- apt-pkg/solver3.cc | 74 ++++++++++++++++++------------------------------------ apt-pkg/solver3.h | 2 -- 2 files changed, 24 insertions(+), 52 deletions(-) diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index 54f31a797..b7ad45f27 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -441,15 +441,6 @@ bool Solver::Propagate() return true; } -void Solver::Push(Var var, Work work) -{ - if (unlikely(debug >= 2)) - std::cerr << "Trying choice for " << work.toString(cache) << std::endl; - - trailLim.push_back(trail.size()); - trail.push_back(Trail{var, std::move(work)}); -} - void Solver::UndoOne() { auto trailItem = trail.back(); @@ -473,8 +464,7 @@ void Solver::UndoOne() if (unlikely(debug >= 4)) std::cerr << "Adding work item " << work->toString(cache) << std::endl; - if (not AddWork(std::move(*work))) - abort(); + must_succeed(AddWork(std::move(*work))); } trail.pop_back(); @@ -568,7 +558,7 @@ bool Solver::Solve() startTime = time(nullptr); while (true) { - while (not Propagate()) + while (_error->PendingError() || not Propagate()) { if (not Pop()) return false; @@ -577,59 +567,44 @@ bool Solver::Solve() if (work.empty()) break; - // *NOW* we can pop the item. + auto item = work.front(); std::pop_heap(work.begin(), work.end()); - + work.pop_back(); // This item has been replaced with a new one. Remove it. - if (work.back().erased) - { - work.pop_back(); + if (item.erased) continue; - } - auto item = std::move(work.back()); - work.pop_back(); - trail.push_back(Trail{Var(), item}); if (std::any_of(item.clause->solutions.begin(), item.clause->solutions.end(), [this](auto ver) { return value(ver) == LiftedBool::True; })) { if (unlikely(debug >= 2)) std::cerr << "ELIDED " << item.toString(cache) << std::endl; - continue; } - - if (unlikely(debug >= 1)) - std::cerr << item.toString(cache) << std::endl; - - bool foundSolution = false; - for (auto &sol : item.clause->solutions) + else if (auto candidate = std::find_if(item.clause->solutions.begin(), item.clause->solutions.end(), [this](auto ver) + { return value(ver) == LiftedBool::Undefined; }); + candidate != item.clause->solutions.end()) { - if (value(sol) == LiftedBool::False) - { - if (unlikely(debug >= 3)) - std::cerr << "(existing conflict: " << sol.toString(cache) << ")\n"; - continue; - } - if (item.size > 1 || item.clause->optional) - { - Push(sol, item); - } if (unlikely(debug >= 3)) - std::cerr << "(try it: " << sol.toString(cache) << ")\n"; - if (not Enqueue(sol, item.clause) && not Pop()) - return false; - foundSolution = true; - break; + std::cerr << item.toString(cache) << "\n" + << "(try it: " << candidate->toString(cache) << ")\n"; + must_succeed(Assume(*candidate, item.clause)); + } + else if (item.clause->optional) + { + if (unlikely(debug >= 1)) + std::cerr << item.toString(cache) << "\n"; } - if (not foundSolution && not item.clause->optional) + else { + if (unlikely(debug >= 1)) + std::cerr << item.toString(cache) << "\n"; // Enqueue produces the right error message for us here, given that reason has been assigned true already... assert(value(item.clause->reason) == LiftedBool::True); - bool res = Enqueue(~item.clause->reason, item.clause); - assert(not res); - if (not Pop()) - return false; + must_succeed(not Enqueue(~item.clause->reason, item.clause)); + assert(value(item.clause->reason) == LiftedBool::True); } + // Must push to trail after any Assume() above. + trail.push_back(Trail{Var(), item}); } return true; @@ -1323,8 +1298,7 @@ bool DependencySolver::FromDepCache(pkgDepCache &depcache) for (auto assumption : manualPackages) { if (not Assume(assumption, {}) || not Propagate()) - if (not Pop()) - abort(); + must_succeed(Pop()); } return true; diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h index f66b3cf62..facba4d39 100644 --- a/apt-pkg/solver3.h +++ b/apt-pkg/solver3.h @@ -370,8 +370,6 @@ class Solver inline LiftedBool value(Lit lit) const; public: - // \brief Create a new decision level. - void Push(Var var, Work work); // \brief Revert to the previous decision level. [[nodiscard]] bool Pop(); // \brief Undo a single assignment / trail work item -- cgit v1.2.3-70-g09d2 From f02f90021c255ef3aa578e00758cbc62e7fc82dd Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Mon, 29 Dec 2025 16:47:20 +0100 Subject: solver3: Add a strange assertion I do not know why I don't hit this --- apt-pkg/solver3.cc | 2 ++ 1 file changed, 2 insertions(+) diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index b7ad45f27..9313b433d 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -343,6 +343,8 @@ bool Solver::Assume(Lit lit, const Clause *reason) bool Solver::Enqueue(Lit lit, const Clause *reason) { + assert(not lit.empty()); + auto &state = (*this)[lit.var()]; auto assignment = lit.sign() ? LiftedBool::False : LiftedBool::True; -- cgit v1.2.3-70-g09d2 From 62fa3858d12f163de7db81f6e2be770e39783238 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Mon, 29 Dec 2025 21:26:24 +0100 Subject: solver3: Modernize std::find() to std::ranges::contains Where applicable --- apt-pkg/solver3.cc | 15 ++++++--------- apt-pkg/solver3.h | 8 ++++---- 2 files changed, 10 insertions(+), 13 deletions(-) diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index 9313b433d..096cbb521 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -826,17 +826,15 @@ const Clause *DependencySolver::RegisterClause(Clause &&clause) earlierDep.TargetPkg() != dep.TargetPkg()) continue; if (std::none_of(earlierClause->solutions.begin(), earlierClause->solutions.end(), [&clause](auto earlierSol) - { return std::find(clause.solutions.begin(), - clause.solutions.end(), - earlierSol) != clause.solutions.end(); })) + { return std::ranges::contains(clause.solutions, + earlierSol); })) continue; if (earlierClause->optional == clause.optional) { std::erase_if(earlierClause->solutions, [&clause, this](auto earlierSol) - { return std::find(clause.solutions.begin(), - clause.solutions.end(), - earlierSol) == clause.solutions.end(); }); + { return not std::ranges::contains(clause.solutions, + earlierSol); }); earlierClause->merged.push_front(clause); merged = true; @@ -845,9 +843,8 @@ const Clause *DependencySolver::RegisterClause(Clause &&clause) { // If say a Depends has fewer solution than a Recommends, remove the Recommend's extranous ones. std::erase_if(clause.solutions, [&earlierClause, this](auto sol) - { return std::find(earlierClause->solutions.begin(), - earlierClause->solutions.end(), - sol) == earlierClause->solutions.end(); }); + { return not std::ranges::contains(earlierClause->solutions, + sol); }); // Remove recursion here, such that we display correctly (if we ever display anywhere...) auto earlierClauseCopy = *earlierClause; diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h index facba4d39..6fa00933f 100644 --- a/apt-pkg/solver3.h +++ b/apt-pkg/solver3.h @@ -166,8 +166,8 @@ struct Var } // \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; } + constexpr bool operator!=(Var const other) const noexcept { return value != other.value; } + constexpr bool operator==(Var const other) const noexcept { return value == other.value; } /// \brief Negate constexpr Lit operator~() const; @@ -206,8 +206,8 @@ struct Lit // 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; } + constexpr bool operator!=(Lit const other) const noexcept { return value != other.value; } + constexpr bool operator==(Lit const other) const noexcept { return value == other.value; } std::string toString(pkgCache &cache) const { return (sign() ? "not " : "") + var().toString(cache); } }; -- cgit v1.2.3-70-g09d2 From 5bdd21f915d1af832e9d3b874ddbd3ba2a178a06 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Sun, 4 Jan 2026 17:25:38 +0100 Subject: solver3: Ensure rule-of-3 memory safety for ContiguousCacheMap --- apt-pkg/solver3.h | 4 ++++ 1 file changed, 4 insertions(+) diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h index 6fa00933f..4a2b4ac8d 100644 --- a/apt-pkg/solver3.h +++ b/apt-pkg/solver3.h @@ -59,6 +59,10 @@ class ContiguousCacheMap V &operator[](const K *key) { return data_[key->ID]; } const V &operator[](const K *key) const { return data_[key->ID]; } ~ContiguousCacheMap() { delete[] data_; } + + // Delete copy constructors for memory safety (rule of 3) + ContiguousCacheMap(const ContiguousCacheMap &) = delete; + ContiguousCacheMap &operator=(const ContiguousCacheMap &) = delete; }; /** -- cgit v1.2.3-70-g09d2