From 52d0baba388a21205b323153a0d83dc6ae75bbf0 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Mon, 3 Feb 2025 15:31:47 +0100 Subject: solver3: Drop unused upgrade flag This was leftover from before the groups were added. --- apt-pkg/solver3.cc | 4 ++-- apt-pkg/solver3.h | 4 +--- 2 files changed, 3 insertions(+), 5 deletions(-) (limited to 'apt-pkg') diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index 73f7fd0c4..42e6fedce 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -222,7 +222,7 @@ void APT::Solver::Work::Dump(pkgCache &cache) std::cerr << "Erased "; if (optional) std::cerr << "Optional "; - std::cerr << "Item (" << ssize_t(size <= solutions.size() ? size : -1) << "@" << depth << (upgrade ? "u" : "") << ") "; + std::cerr << "Item (" << ssize_t(size <= solutions.size() ? size : -1) << "@" << depth << ") "; if (auto Pkg = reason.Pkg(cache); not Pkg.end()) std::cerr << Pkg.FullName(); if (auto Ver = reason.Ver(cache); not Ver.end()) @@ -1011,7 +1011,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache) } else { - Work w{Var(), depth(), Group, isOptional, Upgrade}; + Work w{Var(), depth(), Group, isOptional}; for (auto V = P.VersionList(); not V.end(); ++V) w.solutions.push_back(V); std::stable_sort(w.solutions.begin(), w.solutions.end(), CompareProviders3{cache, policy, P, *this}); diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h index 4f6f83d15..282e8865b 100644 --- a/apt-pkg/solver3.h +++ b/apt-pkg/solver3.h @@ -291,8 +291,6 @@ struct APT::Solver::Work // \brief Whether this is an optional work item, they will be processed last bool optional; - // \brief Whether this is an ugprade - bool upgrade; // \brief This item should be removed from the queue. bool erased; @@ -300,7 +298,7 @@ struct APT::Solver::Work // \brief Dump the work item to std::cerr void Dump(pkgCache &cache); - inline Work(Var reason, depth_type depth, Group group, bool optional = false, bool upgrade = false) : reason(reason), depth(depth), group(group), size(0), optional(optional), upgrade(upgrade), erased(false) {} + inline Work(Var reason, depth_type depth, Group group, bool optional = false) : reason(reason), depth(depth), group(group), size(0), optional(optional), erased(false) {} }; // \brief This essentially describes the install state in RFC2119 terms. -- cgit v1.2.3-70-g09d2 From 3c4551bbdae483d37b985b2c690d77372fb50e89 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Mon, 3 Feb 2025 16:03:17 +0100 Subject: solver3: Simplify work ordering Moving the optional != b.optional comparison ahead of the group one allows us to get a better behavior; and now we avoid the nested if. Also remove the special cases that ordered based on the reason of the work item, these have been superseded by groups a while ago. --- apt-pkg/solver3.cc | 18 ++++-------------- 1 file changed, 4 insertions(+), 14 deletions(-) (limited to 'apt-pkg') diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index 42e6fedce..15d55be38 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -196,22 +196,12 @@ bool APT::Solver::Work::operator<(APT::Solver::Work const &b) const { if ((not optional && size < 2) != (not b.optional && b.size < 2)) return not b.optional && b.size < 2; - if (group != b.group) - return group > b.group; - if (optional && b.optional) - { - if ((size < 2) != (b.size < 2)) - return b.size < 2; - if (reason.empty() != b.reason.empty()) - return reason.empty(); - } - // An optional item is less important than a required one. if (optional != b.optional) return optional; - // We enqueue common dependencies at the package level to avoid choosing versions, so let's solve package items first, - // this improves the implication graph as it now tells you that common dependencies were installed by the package. - if (reason.Pkg() != b.reason.Pkg()) - return reason.Pkg() == 0; + if (group != b.group) + return group > b.group; + if ((size < 2) != (b.size < 2)) + return b.size < 2; return false; } -- cgit v1.2.3-70-g09d2 From 466ff3cf0afc5c034ec77868781d8e19e274e7ff Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Mon, 3 Feb 2025 16:56:08 +0100 Subject: solver3: Partially generalize work items from Version to Var Store all possible solutions and choices as Var. Currently any Var in here must be a Version because CompareProviders3 cannot compare versions against packages yet, but in the future (TM), this will allow storing packages directly in clauses, which allows defering version selection to a later point. --- apt-pkg/solver3.cc | 62 +++++++++++++++++++++++++++++------------------------- apt-pkg/solver3.h | 15 +++++++++++-- 2 files changed, 46 insertions(+), 31 deletions(-) (limited to 'apt-pkg') diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index 15d55be38..87e4babc8 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -49,6 +49,15 @@ struct APT::Solver::CompareProviders3 /*{{{*/ { return (*this)(pkgCache::VerIterator(Cache, AV), pkgCache::VerIterator(Cache, BV)); } + bool operator()(Var a, Var b) + { + if (auto va = a.Ver(Cache)) + { + if (auto vb = b.Ver(Cache)) + return (*this)(va, vb); + } + abort(); + } bool operator()(pkgCache::VerIterator const &AV, pkgCache::VerIterator const &BV) { pkgCache::PkgIterator const A = AV.ParentPkg(); @@ -219,10 +228,7 @@ void APT::Solver::Work::Dump(pkgCache &cache) std::cerr << Ver.ParentPkg().FullName() << "=" << Ver.VerStr(); std::cerr << " -> "; for (auto sol : solutions) - { - auto Ver = pkgCache::VerIterator(cache, sol); - std::cerr << " | " << Ver.ParentPkg().FullName() << "=" << Ver.VerStr(); - } + std::cerr << " | " << sol.toString(cache); } // Prints an implication graph part of the form A -> B -> C, possibly with "not" @@ -375,7 +381,7 @@ bool APT::Solver::PropagateInstall(Var var) Work workItem{Var(Pkg), depth(), Group::SelectVersion}; for (auto ver = Pkg.VersionList(); not ver.end(); ver++) { - workItem.solutions.push_back(ver); + workItem.solutions.push_back(Var(ver)); if ((*this)[ver].decision != Decision::MUSTNOT) anyInstallable = true; if ((*this)[ver].decision == Decision::MUST) @@ -396,7 +402,7 @@ bool APT::Solver::PropagateInstall(Var var) if (workItem.solutions.size() > 1 || workItem.optional) AddWork(std::move(workItem)); - else if (not Enqueue(Var(pkgCache::VerIterator(cache, workItem.solutions[0])), true, workItem.reason)) + else if (not Enqueue(workItem.solutions[0], true, workItem.reason)) return false; // FIXME: We skip enqueuing duplicate common dependencies if we already selected a version, but @@ -534,7 +540,7 @@ bool APT::Solver::EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepItera { if (unlikely(debug >= 3)) std::cerr << "Adding work to item " << Ver.ParentPkg().FullName() << "=" << Ver.VerStr() << " -> " << tgti.ParentPkg().FullName() << "=" << tgti.VerStr() << "\n"; - workItem.solutions.push_back(*tgt); + workItem.solutions.push_back(Var(pkgCache::VerIterator(cache, *tgt))); } } delete[] all; @@ -553,11 +559,11 @@ bool APT::Solver::EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepItera if (not fixPolicy) std::stable_sort(workItem.solutions.begin(), workItem.solutions.end(), CompareProviders3{cache, policy, TgtPkg, *this}); - if (std::all_of(workItem.solutions.begin(), workItem.solutions.end(), [this](auto V) -> auto - { return pkgCache::VerIterator(cache, V).ParentPkg()->CurrentVer == 0; })) + if (std::all_of(workItem.solutions.begin(), workItem.solutions.end(), [this](auto var) -> auto + { return var.CastPkg(cache)->CurrentVer == 0; })) workItem.group = Group::SatisfyNew; - if (std::any_of(workItem.solutions.begin(), workItem.solutions.end(), [this](auto V) -> auto - { return Obsolete(pkgCache::VerIterator(cache, V).ParentPkg()); })) + if (std::any_of(workItem.solutions.begin(), workItem.solutions.end(), [this](auto var) -> auto + { return Obsolete(var.CastPkg(cache)); })) workItem.group = Group::SatisfyObsolete; // Try to perserve satisfied Recommends. FIXME: We should check if the Recommends was there in the installed version? if (workItem.optional && start.ParentPkg()->CurrentVer) @@ -569,8 +575,8 @@ bool APT::Solver::EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepItera if (not D.IsCritical() && not D.IsNegative() && D.TargetPkg() == start.TargetPkg()) newOptional = false, wasImportant = policy.IsImportantDep(D); - bool satisfied = std::any_of(workItem.solutions.begin(), workItem.solutions.end(), [this](auto ver) - { return pkgCache::VerIterator(cache, ver).ParentPkg().CurrentVer() == ver; }); + bool satisfied = std::any_of(workItem.solutions.begin(), workItem.solutions.end(), [this](auto var) + { return Var(var.CastPkg(cache).CurrentVer()) == var; }); if (important && wasImportant && not newOptional && not satisfied) { @@ -615,7 +621,7 @@ bool APT::Solver::EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepItera } if (workItem.optional || workItem.solutions.size() > 1) AddWork(std::move(workItem)); - else if (not Enqueue(Var(pkgCache::VerIterator(cache, workItem.solutions[0])), true, reason)) + else if (not Enqueue(workItem.solutions[0], true, reason)) return false; } else if (start.IsCritical() && not start.IsNegative()) @@ -759,7 +765,7 @@ bool APT::Solver::Pop() assert(choices.back() < solved.size()); int itemsToUndo = solved.size() - choices.back(); - pkgCache::VerIterator choice(cache, solved[choices.back()].work->choice); + auto choice = solved[choices.back()].work->choice; for (; itemsToUndo; --itemsToUndo) UndoOne(); @@ -774,14 +780,14 @@ bool APT::Solver::Pop() std::make_heap(work.begin(), work.end()); if (unlikely(debug >= 2)) - std::cerr << "Backtracking to choice " << choice.ParentPkg().FullName() << "=" << choice.VerStr() << "\n"; + std::cerr << "Backtracking to choice " << choice.toString(cache) << "\n"; // FIXME: There should be a reason! - if (not Enqueue(Var(choice), false, {})) + if (not Enqueue(choice, false, {})) return false; if (unlikely(debug >= 2)) - std::cerr << "Backtracked to choice " << choice.ParentPkg().FullName() << "=" << choice.VerStr() << "\n"; + std::cerr << "Backtracked to choice " << choice.toString(cache) << "\n"; return true; } @@ -892,21 +898,20 @@ bool APT::Solver::Solve() bool foundSolution = false; for (auto &sol : item.solutions) { - pkgCache::VerIterator ver(cache, sol); - if ((*this)[ver].decision == Decision::MUSTNOT) + if ((*this)[sol].decision == Decision::MUSTNOT) { if (unlikely(debug >= 3)) - std::cerr << "(existing conflict: " << ver.ParentPkg().FullName() << "=" << ver.VerStr() << ")\n"; + std::cerr << "(existing conflict: " << sol.toString(cache) << ")\n"; continue; } if (item.size > 1 || item.optional) { - item.choice = ver; + item.choice = sol; Push(item); } if (unlikely(debug >= 3)) - std::cerr << "(try it: " << ver.ParentPkg().FullName() << "=" << ver.VerStr() << ")\n"; - if (not Enqueue(Var(ver), true, item.reason) && not Pop()) + std::cerr << "(try it: " << sol.toString(cache) << ")\n"; + if (not Enqueue(sol, true, item.reason) && not Pop()) return false; foundSolution = true; break; @@ -916,13 +921,12 @@ bool APT::Solver::Solve() std::ostringstream dep; assert(item.solutions.size() > 0); for (auto &sol : item.solutions) - dep << (dep.tellp() == 0 ? "" : " | ") << pkgCache::VerIterator(cache, sol).ParentPkg().FullName() << "=" << pkgCache::VerIterator(cache, sol).VerStr(); + dep << (dep.tellp() == 0 ? "" : " | ") << sol.toString(cache); _error->Error("Unsatisfiable dependency: %s -> %s", WhyStr(item.reason).c_str(), dep.str().c_str()); for (auto &sol : item.solutions) if ((*this)[sol].decision == Decision::MUSTNOT) - _error->Error("Not considered: %s=%s: %s", pkgCache::VerIterator(cache, sol).ParentPkg().FullName().c_str(), - pkgCache::VerIterator(cache, sol).VerStr(), - WhyStr(Var(pkgCache::VerIterator(cache, sol))).c_str()); + _error->Error("Not considered: %s: %s", sol.toString(cache).c_str(), + WhyStr(sol).c_str()); if (not Pop()) return false; } @@ -1003,7 +1007,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache) { Work w{Var(), depth(), Group, isOptional}; for (auto V = P.VersionList(); not V.end(); ++V) - w.solutions.push_back(V); + w.solutions.push_back(Var(V)); std::stable_sort(w.solutions.begin(), w.solutions.end(), CompareProviders3{cache, policy, P, *this}); AddWork(std::move(w)); } diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h index 282e8865b..4561ffa73 100644 --- a/apt-pkg/solver3.h +++ b/apt-pkg/solver3.h @@ -7,6 +7,7 @@ * SPDX-License-Identifier: GPL-2.0+ */ +#include #include #include #include @@ -242,11 +243,21 @@ struct APT::Solver::Var { 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 + { + assert(MapPtr != 0); + return IsVersion ? Ver(cache).ParentPkg() : Pkg(cache); + } // \brief Check if there is no reason. bool empty() const { return IsVersion == 0 && MapPtr == 0; } + bool operator==(Var const other) + { + return IsVersion == other.IsVersion && MapPtr == other.MapPtr; + } std::string toString(pkgCache &cache) const { @@ -277,14 +288,14 @@ struct APT::Solver::Work // \brief The group we are in Group group; // \brief Possible solutions to this task, ordered in order of preference. - std::vector solutions{}; + std::vector solutions{}; // This is a union because we only need to store the choice we made when adding // to the choice vector, and we don't need the size of valid choices in there. union { // The choice we took - pkgCache::Version *choice; + Var choice; // Number of valid choices size_t size; }; -- cgit v1.2.3-70-g09d2 From a9aeb31833279bc7482e284da2efcd7b06bc4f3a Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Mon, 3 Feb 2025 17:09:16 +0100 Subject: solver3: Early exit when propagating satisfied clauses --- apt-pkg/solver3.cc | 9 +++++---- 1 file changed, 5 insertions(+), 4 deletions(-) (limited to 'apt-pkg') diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index 87e4babc8..3783aa96e 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -388,6 +388,10 @@ bool APT::Solver::PropagateInstall(Var var) anyMust = true; } + // One is already marked for install, nothing to propagate + if (anyMust) + return true; + if (not anyInstallable) { _error->Error("Conflict: %s -> %s but no versions are installable", @@ -405,10 +409,7 @@ bool APT::Solver::PropagateInstall(Var var) else if (not Enqueue(workItem.solutions[0], true, workItem.reason)) return false; - // FIXME: We skip enqueuing duplicate common dependencies if we already selected a version, but - // we should not have common dependencies duplicated in the version objects anyway. - if (not anyMust && not EnqueueCommonDependencies(Pkg)) - return false; + return EnqueueCommonDependencies(Pkg); } else if (auto Ver = var.Ver(cache); not Ver.end()) { -- cgit v1.2.3-70-g09d2 From 276ecdaedc80b1c7106142810a0960cbeba13796 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Mon, 3 Feb 2025 17:18:57 +0100 Subject: solver3: Annotate all bool functions with [[nodiscard]] It is very important that we check the return value of all these functions, otherwise the logic is wrong. --- apt-pkg/solver3.h | 24 ++++++++++++------------ 1 file changed, 12 insertions(+), 12 deletions(-) (limited to 'apt-pkg') diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h index 4561ffa73..1e1d8a56d 100644 --- a/apt-pkg/solver3.h +++ b/apt-pkg/solver3.h @@ -154,17 +154,17 @@ class Solver bool StrictPinning{_config->FindB("APT::Solver::Strict-Pinning", true)}; // \brief Enqueue dependencies shared by all versions of the package. - bool EnqueueCommonDependencies(pkgCache::PkgIterator Pkg); + [[nodiscard]] bool EnqueueCommonDependencies(pkgCache::PkgIterator Pkg); // \brief Reject reverse dependencies. Must call std::make_heap() after. - bool RejectReverseDependencies(pkgCache::VerIterator Ver); + [[nodiscard]] bool RejectReverseDependencies(pkgCache::VerIterator Ver); // \brief Enqueue a single or group - bool EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepIterator end, Var reason); + [[nodiscard]] bool EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepIterator end, Var reason); // \brief Propagate all pending propagations - bool Propagate(); + [[nodiscard]] bool Propagate(); // \brief Propagate a "true" value of a variable - bool PropagateInstall(Var var); + [[nodiscard]] bool PropagateInstall(Var var); // \brief Propagate a rejection of a variable - bool PropagateReject(Var var); + [[nodiscard]] bool PropagateReject(Var var); // \brief Return the current depth (choices.size() with casting) depth_type depth() @@ -176,7 +176,7 @@ class Solver // \brief Create a new decision level. void Push(Work work); // \brief Revert to the previous decision level. - bool Pop(); + [[nodiscard]] bool Pop(); // \brief Undo a single assignment / solved work item void UndoOne(); // \brief Add work to our work queue. @@ -188,17 +188,17 @@ class Solver Solver(pkgCache &Cache, pkgDepCache::Policy &Policy); // Assume that the variable is decided as specified. - bool Assume(Var var, bool decision, Var reason); + [[nodiscard]] bool Assume(Var var, bool decision, Var reason); // Enqueue a decision fact - bool Enqueue(Var var, bool decision, Var reason); + [[nodiscard]] bool Enqueue(Var var, bool decision, Var reason); // \brief Apply the selections from the dep cache to the solver - bool FromDepCache(pkgDepCache &depcache); + [[nodiscard]] bool FromDepCache(pkgDepCache &depcache); // \brief Apply the solver result to the depCache - bool ToDepCache(pkgDepCache &depcache); + [[nodiscard]] bool ToDepCache(pkgDepCache &depcache); // \brief Solve the dependencies - bool Solve(); + [[nodiscard]] bool Solve(); // Print dependency chain std::string WhyStr(Var reason); -- cgit v1.2.3-70-g09d2 From ae2fc9b5121e4a253d1f81fcf14bcd2afd59538c Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Mon, 3 Feb 2025 17:22:31 +0100 Subject: solver3: Propagate single choice clauses as facts This removes a bunch of complexity, and generalizes the propagation behavior, such that we don't need to do if (w.solutions.size() == 1 && not w.optional) Enqueue() else AddWork(w); in our callers. --- apt-pkg/solver3.cc | 20 +++++++++++--------- apt-pkg/solver3.h | 2 +- 2 files changed, 12 insertions(+), 10 deletions(-) (limited to 'apt-pkg') diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index 3783aa96e..403f7f254 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -404,9 +404,7 @@ bool APT::Solver::PropagateInstall(Var var) std::stable_sort(workItem.solutions.begin(), workItem.solutions.end(), CompareProviders3{cache, policy, Pkg, *this}); assert(workItem.solutions.size() > 0); - if (workItem.solutions.size() > 1 || workItem.optional) - AddWork(std::move(workItem)); - else if (not Enqueue(workItem.solutions[0], true, workItem.reason)) + if (not AddWork(std::move(workItem))) return false; return EnqueueCommonDependencies(Pkg); @@ -620,9 +618,7 @@ bool APT::Solver::EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepItera workItem.Dump(cache); std::cerr << "\n"; } - if (workItem.optional || workItem.solutions.size() > 1) - AddWork(std::move(workItem)); - else if (not Enqueue(workItem.solutions[0], true, reason)) + if (not AddWork(std::move(workItem))) return false; } else if (start.IsCritical() && not start.IsNegative()) @@ -745,7 +741,8 @@ void APT::Solver::UndoOne() std::cerr << "\n"; } - AddWork(std::move(*work)); + if (not AddWork(std::move(*work))) + abort(); } solved.pop_back(); @@ -793,12 +790,16 @@ bool APT::Solver::Pop() return true; } -void APT::Solver::AddWork(Work &&w) +bool APT::Solver::AddWork(Work &&w) { + if (w.solutions.size() == 1 && not w.optional) + return Enqueue(w.solutions[0], true, w.reason); + w.size = std::count_if(w.solutions.begin(), w.solutions.end(), [this](auto V) { return (*this)[V].decision != Decision::MUSTNOT; }); work.push_back(std::move(w)); std::push_heap(work.begin(), work.end()); + return true; } void APT::Solver::RescoreWorkIfNeeded() @@ -1010,7 +1011,8 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache) for (auto V = P.VersionList(); not V.end(); ++V) w.solutions.push_back(Var(V)); std::stable_sort(w.solutions.begin(), w.solutions.end(), CompareProviders3{cache, policy, P, *this}); - AddWork(std::move(w)); + if (not AddWork(std::move(w))) + return false; } } } diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h index 1e1d8a56d..548c3b777 100644 --- a/apt-pkg/solver3.h +++ b/apt-pkg/solver3.h @@ -180,7 +180,7 @@ class Solver // \brief Undo a single assignment / solved work item void UndoOne(); // \brief Add work to our work queue. - void AddWork(Work &&work); + [[nodiscard]] bool AddWork(Work &&work); // \brief Rescore the work after a reject or a pop void RescoreWorkIfNeeded(); -- cgit v1.2.3-70-g09d2 From 5b7af08e4b23f00fc1de4dfe4178d867a560553d Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Mon, 3 Feb 2025 19:22:52 +0100 Subject: solver3: Cache calls to policy It's a bit silly otherwise. --- apt-pkg/solver3.cc | 14 ++++++++------ apt-pkg/solver3.h | 14 ++++++++++++++ 2 files changed, 22 insertions(+), 6 deletions(-) (limited to 'apt-pkg') diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index 403f7f254..cab2d4371 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -71,7 +71,7 @@ struct APT::Solver::CompareProviders3 /*{{{*/ // Candidate wins in upgrade scenario if (upgrade) { - auto Cand = Policy.GetCandidateVer(A); + auto Cand = Solver.GetCandidateVer(A); if (AV == Cand || BV == Cand) return (AV == Cand); } @@ -81,7 +81,7 @@ struct APT::Solver::CompareProviders3 /*{{{*/ return (A.CurrentVer() == AV); // Rest is ordered list, first by priority - if (auto pinA = Policy.GetPriority(AV), pinB = Policy.GetPriority(BV); pinA != pinB) + if (auto pinA = Solver.GetPriority(AV), pinB = Solver.GetPriority(BV); pinA != pinB) return pinA > pinB; // Then by version @@ -193,7 +193,9 @@ APT::Solver::Solver(pkgCache &cache, pkgDepCache::Policy &policy) policy(policy), pkgStates(cache.Head().PackageCount), verStates(cache.Head().VersionCount), - pkgObsolete(cache.Head().PackageCount) + pkgObsolete(cache.Head().PackageCount), + priorities(cache.Head().VersionCount), + candidates(cache.Head().PackageCount) { static_assert(sizeof(APT::Solver::State) == 3 * sizeof(int)); static_assert(sizeof(APT::Solver::Var) == sizeof(map_pointer)); @@ -270,7 +272,7 @@ std::string APT::Solver::WhyStr(Var reason) bool APT::Solver::ObsoletedByNewerSourceVersion(pkgCache::VerIterator cand) const { const auto pkg = cand.ParentPkg(); - const int candPriority = policy.GetPriority(cand); + const int candPriority = GetPriority(cand); for (auto ver = cand.Cache()->FindGrp(cand.SourcePkgName()).VersionsInSource(); not ver.end(); ver = ver.NextInSource()) { @@ -279,7 +281,7 @@ bool APT::Solver::ObsoletedByNewerSourceVersion(pkgCache::VerIterator cand) cons continue; // We also take equal priority here, given that we have a higher version - const int priority = policy.GetPriority(ver, true); + const int priority = GetPriority(ver); if (priority == 0 || priority < candPriority) continue; @@ -297,7 +299,7 @@ bool APT::Solver::Obsolete(pkgCache::PkgIterator pkg) const if (pkgObsolete[pkg->ID] != 0) return pkgObsolete[pkg->ID] == 2; - auto ver = policy.GetCandidateVer(pkg); + auto ver = GetCandidateVer(pkg); if (ver.end() && not StrictPinning) ver = pkg.VersionList(); diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h index 548c3b777..2868616de 100644 --- a/apt-pkg/solver3.h +++ b/apt-pkg/solver3.h @@ -114,6 +114,20 @@ class Solver mutable std::vector pkgObsolete; bool Obsolete(pkgCache::PkgIterator pkg) const; bool ObsoletedByNewerSourceVersion(pkgCache::VerIterator cand) const; + mutable std::vector priorities; + short GetPriority(pkgCache::VerIterator ver) const + { + if (priorities[ver->ID] == 0) + priorities[ver->ID] = policy.GetPriority(ver); + return priorities[ver->ID]; + } + mutable std::vector candidates; + pkgCache::VerIterator GetCandidateVer(pkgCache::PkgIterator pkg) const + { + if (candidates[pkg->ID].end()) + candidates[pkg->ID] = policy.GetCandidateVer(pkg); + return candidates[pkg->ID]; + } // \brief Heap of the remaining work. // -- cgit v1.2.3-70-g09d2 From b33c6c36373f47b4c7490b0b6731233c1dc1ff05 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Tue, 4 Feb 2025 09:05:28 +0100 Subject: solver3: Cache all configuration calls --- apt-pkg/solver3.cc | 13 ++++--------- apt-pkg/solver3.h | 6 ++++++ 2 files changed, 10 insertions(+), 9 deletions(-) (limited to 'apt-pkg') diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index cab2d4371..b098d33ba 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -43,7 +43,6 @@ struct APT::Solver::CompareProviders3 /*{{{*/ pkgDepCache::Policy &Policy; pkgCache::PkgIterator const Pkg; APT::Solver &Solver; - bool upgrade{_config->FindB("APT::Solver::Upgrade", false)}; bool operator()(pkgCache::Version *AV, pkgCache::Version *BV) { @@ -69,7 +68,7 @@ struct APT::Solver::CompareProviders3 /*{{{*/ return false; // Candidate wins in upgrade scenario - if (upgrade) + if (Solver.IsUpgrade) { auto Cand = Solver.GetCandidateVer(A); if (AV == Cand || BV == Cand) @@ -90,7 +89,7 @@ struct APT::Solver::CompareProviders3 /*{{{*/ // 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 (upgrade) + 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 @@ -476,8 +475,6 @@ bool APT::Solver::PropagateReject(Var var) bool APT::Solver::EnqueueCommonDependencies(pkgCache::PkgIterator Pkg) { - if (not _config->FindB("APT::Solver::Enqueue-Common-Dependencies", true)) - return false; for (auto dep = Pkg.VersionList().DependsList(); not dep.end();) { pkgCache::DepIterator start; @@ -506,7 +503,6 @@ bool APT::Solver::EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepItera { auto TgtPkg = start.TargetPkg(); auto Ver = start.ParentVer(); - auto fixPolicy = _config->FindB("APT::Get::Fix-Policy-Broken"); // Non-important dependencies can only be installed if they are currently satisfied, see the check further // below once we have calculated all possible solutions. @@ -549,7 +545,7 @@ bool APT::Solver::EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepItera // If we are fixing the policy, we need to sort each alternative in an or group separately // FIXME: This is not really true, though, we should fix the CompareProviders to ignore the // installed state - if (fixPolicy) + if (FixPolicyBroken) std::stable_sort(workItem.solutions.begin() + begin, workItem.solutions.end(), CompareProviders3{cache, policy, TgtPkg, *this}); if (start == end) @@ -557,7 +553,7 @@ bool APT::Solver::EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepItera ++start; } while (1); - if (not fixPolicy) + if (not FixPolicyBroken) std::stable_sort(workItem.solutions.begin(), workItem.solutions.end(), CompareProviders3{cache, policy, TgtPkg, *this}); if (std::all_of(workItem.solutions.begin(), workItem.solutions.end(), [this](auto var) -> auto @@ -942,7 +938,6 @@ bool APT::Solver::Solve() // \brief Apply the selections from the dep cache to the solver bool APT::Solver::FromDepCache(pkgDepCache &depcache) { - bool AllowRemoveManual = AllowRemove && _config->FindB("APT::Solver::RemoveManual", false); DefaultRootSetFunc2 rootSet(&cache); // Enforce strict pinning rules by rejecting all forbidden versions. diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h index 2868616de..2e5c5ca13 100644 --- a/apt-pkg/solver3.h +++ b/apt-pkg/solver3.h @@ -160,12 +160,18 @@ class Solver int debug{_config->FindI("Debug::APT::Solver")}; // \brief If set, we try to keep automatically installed packages installed. bool KeepAuto{not _config->FindB("APT::Get::AutomaticRemove")}; + // \brief Determines if we are in upgrade mode. + bool IsUpgrade{_config->FindB("APT::Solver::Upgrade", false)}; // \brief If set, removals are allowed. bool AllowRemove{_config->FindB("APT::Solver::Remove", true)}; + // \brief If set, removal of manual packages is allowed. + bool AllowRemoveManual{AllowRemove && _config->FindB("APT::Solver::RemoveManual", false)}; // \brief If set, installs are allowed. bool AllowInstall{_config->FindB("APT::Solver::Install", true)}; // \brief If set, we use strict pinning. bool StrictPinning{_config->FindB("APT::Solver::Strict-Pinning", true)}; + // \brief If set, we install missing recommends and pick new best packages. + bool FixPolicyBroken{_config->FindB("APT::Get::Fix-Policy-Broken")}; // \brief Enqueue dependencies shared by all versions of the package. [[nodiscard]] bool EnqueueCommonDependencies(pkgCache::PkgIterator Pkg); -- cgit v1.2.3-70-g09d2 From a41d4ba65bc0841a28ea9c8e9fd13f2c4e00ce86 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Tue, 4 Feb 2025 09:52:59 +0100 Subject: solver3: Simplify WhyStr() Reuse the generic variable rendering --- apt-pkg/solver3.cc | 21 +++++---------------- 1 file changed, 5 insertions(+), 16 deletions(-) (limited to 'apt-pkg') diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index b098d33ba..fce7da0d6 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -239,22 +239,11 @@ std::string APT::Solver::WhyStr(Var reason) while (not reason.empty()) { - if (auto Pkg = reason.Pkg(cache); not Pkg.end()) - { - if ((*this)[Pkg].decision == Decision::MUSTNOT) - out.push_back(std::string("not ") + Pkg.FullName()); - else - out.push_back(Pkg.FullName()); - reason = (*this)[Pkg].reason; - } - if (auto Ver = reason.Ver(cache); not Ver.end()) - { - if ((*this)[Ver].decision == Decision::MUSTNOT) - out.push_back(std::string("not ") + Ver.ParentPkg().FullName() + "=" + Ver.VerStr()); - else - out.push_back(Ver.ParentPkg().FullName() + "=" + Ver.VerStr()); - reason = (*this)[Ver].reason; - } + if ((*this)[reason].decision == Decision::MUSTNOT) + out.push_back(std::string("not ") + reason.toString(cache)); + else + out.push_back(reason.toString(cache)); + reason = (*this)[reason].reason; } std::string outstr; -- cgit v1.2.3-70-g09d2 From 762d12f0ac9dd10325cae09816e5e918b7e5b039 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Tue, 4 Feb 2025 10:18:32 +0100 Subject: solver3: Extract Clause out of Work Extract clause into a separate struct and embed a copy of it in our Work class. --- apt-pkg/solver3.cc | 111 +++++++++++++++++++++++++++-------------------------- apt-pkg/solver3.h | 41 ++++++++++++++------ 2 files changed, 86 insertions(+), 66 deletions(-) (limited to 'apt-pkg') diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index fce7da0d6..3a6658200 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -204,25 +204,19 @@ APT::Solver::Solver(pkgCache &cache, pkgDepCache::Policy &policy) // This function determines if a work item is less important than another. bool APT::Solver::Work::operator<(APT::Solver::Work const &b) const { - if ((not optional && size < 2) != (not b.optional && b.size < 2)) - return not b.optional && b.size < 2; - if (optional != b.optional) - return optional; - if (group != b.group) - return group > b.group; + if ((not clause.optional && size < 2) != (not b.clause.optional && b.size < 2)) + return not b.clause.optional && b.size < 2; + if (clause.optional != b.clause.optional) + return clause.optional; + if (clause.group != b.clause.group) + return clause.group > b.clause.group; if ((size < 2) != (b.size < 2)) return b.size < 2; return false; } - -void APT::Solver::Work::Dump(pkgCache &cache) +void APT::Solver::Clause::Dump(pkgCache &cache) { - if (erased) - std::cerr << "Erased "; - if (optional) - std::cerr << "Optional "; - std::cerr << "Item (" << ssize_t(size <= solutions.size() ? size : -1) << "@" << depth << ") "; if (auto Pkg = reason.Pkg(cache); not Pkg.end()) std::cerr << Pkg.FullName(); if (auto Ver = reason.Ver(cache); not Ver.end()) @@ -231,6 +225,15 @@ void APT::Solver::Work::Dump(pkgCache &cache) for (auto sol : solutions) std::cerr << " | " << sol.toString(cache); } +void APT::Solver::Work::Dump(pkgCache &cache) +{ + if (erased) + std::cerr << "Erased "; + if (clause.optional) + std::cerr << "Optional "; + std::cerr << "Item (" << ssize_t(size <= clause.solutions.size() ? size : -1) << "@" << depth << ") "; + clause.Dump(cache); +} // Prints an implication graph part of the form A -> B -> C, possibly with "not" std::string APT::Solver::WhyStr(Var reason) @@ -368,10 +371,10 @@ bool APT::Solver::PropagateInstall(Var var) bool anyInstallable = false; bool anyMust = false; // Insert the work item. - Work workItem{Var(Pkg), depth(), Group::SelectVersion}; + Clause clause{Var(Pkg), Group::SelectVersion}; for (auto ver = Pkg.VersionList(); not ver.end(); ver++) { - workItem.solutions.push_back(Var(ver)); + clause.solutions.push_back(Var(ver)); if ((*this)[ver].decision != Decision::MUSTNOT) anyInstallable = true; if ((*this)[ver].decision == Decision::MUST) @@ -391,10 +394,10 @@ bool APT::Solver::PropagateInstall(Var var) return false; } - std::stable_sort(workItem.solutions.begin(), workItem.solutions.end(), CompareProviders3{cache, policy, Pkg, *this}); - assert(workItem.solutions.size() > 0); + std::stable_sort(clause.solutions.begin(), clause.solutions.end(), CompareProviders3{cache, policy, Pkg, *this}); + assert(clause.solutions.size() > 0); - if (not AddWork(std::move(workItem))) + if (not AddWork(Work{clause, depth()})) return false; return EnqueueCommonDependencies(Pkg); @@ -503,11 +506,11 @@ bool APT::Solver::EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepItera if (unlikely(debug >= 3)) std::cerr << "Found dependency critical " << Ver.ParentPkg().FullName() << "=" << Ver.VerStr() << " -> " << start.TargetPkg().FullName() << "\n"; - Work workItem{reason, depth(), Group::Satisfy, not start.IsCritical() /* optional */}; + Clause clause{reason, Group::Satisfy, not start.IsCritical() /* optional */}; do { - auto begin = workItem.solutions.size(); + auto begin = clause.solutions.size(); auto all = start.AllTargets(); for (auto tgt = all; *tgt; ++tgt) @@ -526,7 +529,7 @@ bool APT::Solver::EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepItera { if (unlikely(debug >= 3)) std::cerr << "Adding work to item " << Ver.ParentPkg().FullName() << "=" << Ver.VerStr() << " -> " << tgti.ParentPkg().FullName() << "=" << tgti.VerStr() << "\n"; - workItem.solutions.push_back(Var(pkgCache::VerIterator(cache, *tgt))); + clause.solutions.push_back(Var(pkgCache::VerIterator(cache, *tgt))); } } delete[] all; @@ -535,7 +538,7 @@ bool APT::Solver::EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepItera // FIXME: This is not really true, though, we should fix the CompareProviders to ignore the // installed state if (FixPolicyBroken) - std::stable_sort(workItem.solutions.begin() + begin, workItem.solutions.end(), CompareProviders3{cache, policy, TgtPkg, *this}); + std::stable_sort(clause.solutions.begin() + begin, clause.solutions.end(), CompareProviders3{cache, policy, TgtPkg, *this}); if (start == end) break; @@ -543,16 +546,16 @@ bool APT::Solver::EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepItera } while (1); if (not FixPolicyBroken) - std::stable_sort(workItem.solutions.begin(), workItem.solutions.end(), CompareProviders3{cache, policy, TgtPkg, *this}); + std::stable_sort(clause.solutions.begin(), clause.solutions.end(), CompareProviders3{cache, policy, TgtPkg, *this}); - if (std::all_of(workItem.solutions.begin(), workItem.solutions.end(), [this](auto var) -> auto + if (std::all_of(clause.solutions.begin(), clause.solutions.end(), [this](auto var) -> auto { return var.CastPkg(cache)->CurrentVer == 0; })) - workItem.group = Group::SatisfyNew; - if (std::any_of(workItem.solutions.begin(), workItem.solutions.end(), [this](auto var) -> auto + clause.group = Group::SatisfyNew; + if (std::any_of(clause.solutions.begin(), clause.solutions.end(), [this](auto var) -> auto { return Obsolete(var.CastPkg(cache)); })) - workItem.group = Group::SatisfyObsolete; + clause.group = Group::SatisfyObsolete; // Try to perserve satisfied Recommends. FIXME: We should check if the Recommends was there in the installed version? - if (workItem.optional && start.ParentPkg()->CurrentVer) + if (clause.optional && start.ParentPkg()->CurrentVer) { bool important = policy.IsImportantDep(start); bool newOptional = true; @@ -561,7 +564,7 @@ bool APT::Solver::EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepItera if (not D.IsCritical() && not D.IsNegative() && D.TargetPkg() == start.TargetPkg()) newOptional = false, wasImportant = policy.IsImportantDep(D); - bool satisfied = std::any_of(workItem.solutions.begin(), workItem.solutions.end(), [this](auto var) + bool satisfied = std::any_of(clause.solutions.begin(), clause.solutions.end(), [this](auto var) { return Var(var.CastPkg(cache).CurrentVer()) == var; }); if (important && wasImportant && not newOptional && not satisfied) @@ -569,7 +572,7 @@ bool APT::Solver::EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepItera if (unlikely(debug >= 3)) { std::cerr << "Ignoring unsatisfied Recommends "; - workItem.Dump(cache); + clause.Dump(cache); std::cerr << "\n"; } return true; @@ -579,7 +582,7 @@ bool APT::Solver::EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepItera if (unlikely(debug >= 3)) { std::cerr << "Promoting satisfied Suggests to Recommends: "; - workItem.Dump(cache); + clause.Dump(cache); std::cerr << "\n"; } important = true; @@ -589,23 +592,23 @@ bool APT::Solver::EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepItera if (unlikely(debug >= 3)) { std::cerr << "Ignoring Suggests "; - workItem.Dump(cache); + clause.Dump(cache); std::cerr << "\n"; } return true; } } - if (not workItem.solutions.empty()) + if (not clause.solutions.empty()) { - // std::stable_sort(workItem.solutions.begin(), workItem.solutions.end(), CompareProviders3{cache, TgtPkg}); - if (unlikely(debug >= 3 && workItem.optional)) + // std::stable_sort(clause.solutions.begin(), clause.solutions.end(), CompareProviders3{cache, TgtPkg}); + if (unlikely(debug >= 3 && clause.optional)) { std::cerr << "Enqueuing Recommends "; - workItem.Dump(cache); + clause.Dump(cache); std::cerr << "\n"; } - if (not AddWork(std::move(workItem))) + if (not AddWork(Work{std::move(clause), depth()})) return false; } else if (start.IsCritical() && not start.IsNegative()) @@ -779,10 +782,10 @@ bool APT::Solver::Pop() bool APT::Solver::AddWork(Work &&w) { - if (w.solutions.size() == 1 && not w.optional) - return Enqueue(w.solutions[0], true, w.reason); + if (w.clause.solutions.size() == 1 && not w.clause.optional) + return Enqueue(w.clause.solutions[0], true, w.clause.reason); - w.size = std::count_if(w.solutions.begin(), w.solutions.end(), [this](auto V) + w.size = std::count_if(w.clause.solutions.begin(), w.clause.solutions.end(), [this](auto V) { return (*this)[V].decision != Decision::MUSTNOT; }); work.push_back(std::move(w)); std::push_heap(work.begin(), work.end()); @@ -800,7 +803,7 @@ void APT::Solver::RescoreWorkIfNeeded() { if (w.erased) continue; - size_t newSize = std::count_if(w.solutions.begin(), w.solutions.end(), [this](auto V) + size_t newSize = std::count_if(w.clause.solutions.begin(), w.clause.solutions.end(), [this](auto V) { return (*this)[V].decision != Decision::MUSTNOT; }); // Notably we only insert the work into the queue if it got smaller. Work that got larger @@ -849,7 +852,7 @@ bool APT::Solver::Solve() } // If our size increased, queue again. - size_t newSize = std::count_if(work.back().solutions.begin(), work.back().solutions.end(), [this](auto V) + size_t newSize = std::count_if(work.back().clause.solutions.begin(), work.back().clause.solutions.end(), [this](auto V) { return (*this)[V].decision != Decision::MUSTNOT; }); if (newSize > work.back().size) @@ -864,7 +867,7 @@ bool APT::Solver::Solve() work.pop_back(); solved.push_back(Solved{Var(), item}); - if (std::any_of(item.solutions.begin(), item.solutions.end(), [this](auto ver) + if (std::any_of(item.clause.solutions.begin(), item.clause.solutions.end(), [this](auto ver) { return (*this)[ver].decision == Decision::MUST; })) { if (unlikely(debug >= 2)) @@ -882,10 +885,10 @@ bool APT::Solver::Solve() std::cerr << "\n"; } - assert(item.solutions.size() > 1 || item.optional); + assert(item.clause.solutions.size() > 1 || item.clause.optional); bool foundSolution = false; - for (auto &sol : item.solutions) + for (auto &sol : item.clause.solutions) { if ((*this)[sol].decision == Decision::MUSTNOT) { @@ -893,26 +896,26 @@ bool APT::Solver::Solve() std::cerr << "(existing conflict: " << sol.toString(cache) << ")\n"; continue; } - if (item.size > 1 || item.optional) + if (item.size > 1 || item.clause.optional) { item.choice = sol; Push(item); } if (unlikely(debug >= 3)) std::cerr << "(try it: " << sol.toString(cache) << ")\n"; - if (not Enqueue(sol, true, item.reason) && not Pop()) + if (not Enqueue(sol, true, item.clause.reason) && not Pop()) return false; foundSolution = true; break; } - if (not foundSolution && not item.optional) + if (not foundSolution && not item.clause.optional) { std::ostringstream dep; - assert(item.solutions.size() > 0); - for (auto &sol : item.solutions) + assert(item.clause.solutions.size() > 0); + for (auto &sol : item.clause.solutions) dep << (dep.tellp() == 0 ? "" : " | ") << sol.toString(cache); - _error->Error("Unsatisfiable dependency: %s -> %s", WhyStr(item.reason).c_str(), dep.str().c_str()); - for (auto &sol : item.solutions) + _error->Error("Unsatisfiable dependency: %s -> %s", WhyStr(item.clause.reason).c_str(), dep.str().c_str()); + for (auto &sol : item.clause.solutions) if ((*this)[sol].decision == Decision::MUSTNOT) _error->Error("Not considered: %s: %s", sol.toString(cache).c_str(), WhyStr(sol).c_str()); @@ -993,11 +996,11 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache) } else { - Work w{Var(), depth(), Group, isOptional}; + Clause w{Var(), Group, isOptional}; for (auto V = P.VersionList(); not V.end(); ++V) w.solutions.push_back(Var(V)); std::stable_sort(w.solutions.begin(), w.solutions.end(), CompareProviders3{cache, policy, P, *this}); - if (not AddWork(std::move(w))) + if (not AddWork(Work{std::move(w), depth()})) return false; } } diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h index 2e5c5ca13..bf8647921 100644 --- a/apt-pkg/solver3.h +++ b/apt-pkg/solver3.h @@ -37,6 +37,7 @@ class Solver struct Var; struct CompareProviders3; struct State; + struct Clause; struct Work; struct Solved; @@ -289,6 +290,29 @@ struct APT::Solver::Var } }; +/** + * \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 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; + + inline Clause(Var reason, Group group, bool optional = false) : reason(reason), group(group), optional(optional) {} + + // \brief Dump the clause to std::cerr + void Dump(pkgCache &cache); +}; + /** * \brief A single work item * @@ -301,14 +325,10 @@ struct APT::Solver::Var */ struct APT::Solver::Work { - // \brief Var for the work - Var reason; + Clause clause; + // \brief The depth at which the item has been added depth_type depth; - // \brief The group we are in - Group group; - // \brief Possible solutions to this task, ordered in order of preference. - std::vector solutions{}; // This is a union because we only need to store the choice we made when adding // to the choice vector, and we don't need the size of valid choices in there. @@ -317,19 +337,16 @@ struct APT::Solver::Work // The choice we took Var choice; // Number of valid choices - size_t size; + size_t size{0}; }; - // \brief Whether this is an optional work item, they will be processed last - bool optional; // \brief This item should be removed from the queue. - bool erased; + bool erased{false}; bool operator<(APT::Solver::Work const &b) const; // \brief Dump the work item to std::cerr void Dump(pkgCache &cache); - - inline Work(Var reason, depth_type depth, Group group, bool optional = false) : reason(reason), depth(depth), group(group), size(0), optional(optional), erased(false) {} + inline Work(Clause clause, depth_type depth) : clause(std::move(clause)), depth(depth) {} }; // \brief This essentially describes the install state in RFC2119 terms. -- cgit v1.2.3-70-g09d2 From dd691af845421e6e9c6f43e51e907dd54e505604 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Tue, 4 Feb 2025 12:42:17 +0100 Subject: solver3: Extract TranslateOrGroup() out of EnqueueOrGroup() This is not *purely* a refactoring, we accidentally used the version of the dependency when enqueuing conflicts rather than the reason, so the conflict string in the test case is different; the logging had the same issue. --- apt-pkg/solver3.cc | 75 +++++++++++----------- apt-pkg/solver3.h | 7 +- ...test-bug-598669-install-postfix-gets-exim-heavy | 2 +- 3 files changed, 43 insertions(+), 41 deletions(-) (limited to 'apt-pkg') diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index 3a6658200..5909bb55e 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -492,6 +492,31 @@ bool APT::Solver::EnqueueCommonDependencies(pkgCache::PkgIterator Pkg) } bool APT::Solver::EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepIterator end, Var reason) +{ + auto clause = TranslateOrGroup(start, end, reason); + if (clause.negative) + { + for (auto var : clause.solutions) + if (not Enqueue(var, false, clause.reason)) + return false; + } + else if (not clause.solutions.empty()) + { + if (unlikely(debug >= 3 && clause.optional)) + { + std::cerr << "Enqueuing Recommends "; + clause.Dump(cache); + std::cerr << "\n"; + } + return AddWork(Work{std::move(clause), depth()}); + } + else if (not clause.optional) + return _error->Error("Unsatisfiable dependency group %s -> %s", reason.toString(cache).c_str(), start.TargetPkg().FullName().c_str()); + + return true; +} + +APT::Solver::Clause APT::Solver::TranslateOrGroup(pkgCache::DepIterator start, pkgCache::DepIterator end, Var reason) { auto TgtPkg = start.TargetPkg(); auto Ver = start.ParentVer(); @@ -499,14 +524,14 @@ bool APT::Solver::EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepItera // Non-important dependencies can only be installed if they are currently satisfied, see the check further // below once we have calculated all possible solutions. if (start.ParentPkg()->CurrentVer == 0 && not policy.IsImportantDep(start)) - return true; + return Clause{reason, Group::Satisfy, true}; // Replaces and Enhances are not a real dependency. if (start->Type == pkgCache::Dep::Replaces || start->Type == pkgCache::Dep::Enhances) - return true; + return Clause{reason, Group::Satisfy, true}; if (unlikely(debug >= 3)) std::cerr << "Found dependency critical " << Ver.ParentPkg().FullName() << "=" << Ver.VerStr() << " -> " << start.TargetPkg().FullName() << "\n"; - Clause clause{reason, Group::Satisfy, not start.IsCritical() /* optional */}; + Clause clause{reason, Group::Satisfy, not start.IsCritical() /* optional */, start.IsNegative()}; do { @@ -516,21 +541,9 @@ bool APT::Solver::EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepItera for (auto tgt = all; *tgt; ++tgt) { pkgCache::VerIterator tgti(cache, *tgt); - - if (start.IsNegative()) - { - if (unlikely(debug >= 3)) - std::cerr << "Reject: " << Ver.ParentPkg().FullName() << "=" << Ver.VerStr() << " -> " << tgti.ParentPkg().FullName() << "=" << tgti.VerStr() << "\n"; - // FIXME: We should be collecting these and marking the heap only once. - if (not Enqueue(Var(pkgCache::VerIterator(cache, *tgt)), false, Var(Ver))) - return false; - } - else - { - if (unlikely(debug >= 3)) - std::cerr << "Adding work to item " << Ver.ParentPkg().FullName() << "=" << Ver.VerStr() << " -> " << tgti.ParentPkg().FullName() << "=" << tgti.VerStr() << "\n"; - clause.solutions.push_back(Var(pkgCache::VerIterator(cache, *tgt))); - } + if (unlikely(debug >= 3)) + std::cerr << "Adding work to item " << reason.toString(cache) << " -> " << tgti.ParentPkg().FullName() << "=" << tgti.VerStr() << (clause.negative ? " (negative)" : "") << "\n"; + clause.solutions.push_back(Var(pkgCache::VerIterator(cache, *tgt))); } delete[] all; @@ -575,9 +588,9 @@ bool APT::Solver::EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepItera clause.Dump(cache); std::cerr << "\n"; } - return true; + clause.solutions.clear(); } - if (not important && not wasImportant && not newOptional && satisfied) + else if (not important && not wasImportant && not newOptional && satisfied) { if (unlikely(debug >= 3)) { @@ -587,7 +600,7 @@ bool APT::Solver::EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepItera } important = true; } - if (not important) + else if (not important) { if (unlikely(debug >= 3)) { @@ -595,27 +608,11 @@ bool APT::Solver::EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepItera clause.Dump(cache); std::cerr << "\n"; } - return true; + return Clause{reason, Group::Satisfy, true}; } } - if (not clause.solutions.empty()) - { - // std::stable_sort(clause.solutions.begin(), clause.solutions.end(), CompareProviders3{cache, TgtPkg}); - if (unlikely(debug >= 3 && clause.optional)) - { - std::cerr << "Enqueuing Recommends "; - clause.Dump(cache); - std::cerr << "\n"; - } - if (not AddWork(Work{std::move(clause), depth()})) - return false; - } - else if (start.IsCritical() && not start.IsNegative()) - { - return _error->Error("Unsatisfiable dependency group %s=%s -> %s", Ver.ParentPkg().FullName().c_str(), Ver.VerStr(), TgtPkg.FullName().c_str()); - } - return true; + return clause; } // \brief Find the or group containing the given dependency. diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h index bf8647921..42cde96f5 100644 --- a/apt-pkg/solver3.h +++ b/apt-pkg/solver3.h @@ -178,6 +178,8 @@ class Solver [[nodiscard]] bool EnqueueCommonDependencies(pkgCache::PkgIterator Pkg); // \brief Reject reverse dependencies. Must call std::make_heap() after. [[nodiscard]] bool RejectReverseDependencies(pkgCache::VerIterator Ver); + // \brief Translate an or group into a clause object + [[nodiscard]] Clause TranslateOrGroup(pkgCache::DepIterator start, pkgCache::DepIterator end, Var reason); // \brief Enqueue a single or group [[nodiscard]] bool EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepIterator end, Var reason); // \brief Propagate all pending propagations @@ -307,7 +309,10 @@ struct APT::Solver::Clause // \brief An optional clause does not need to be satisfied bool optional; - inline Clause(Var reason, Group group, bool optional = false) : reason(reason), group(group), optional(optional) {} + // \brief A negative clause negates the solutions, that is X->A|B you get X->!(A|B), aka X->!A&!B + bool negative; + + inline Clause(Var reason, Group group, bool optional = false, bool negative = false) : reason(reason), group(group), optional(optional), negative(negative) {} // \brief Dump the clause to std::cerr void Dump(pkgCache &cache); 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 d721bdaa8..6c9fb60c0 100755 --- a/test/integration/test-bug-598669-install-postfix-gets-exim-heavy +++ b/test/integration/test-bug-598669-install-postfix-gets-exim-heavy @@ -7,7 +7,7 @@ setupenvironment configarchitecture "i386" setupaptarchive -testfailuremsg "E: Conflict: exim4-daemon-light:i386 -> exim4-daemon-light:i386=4.72-1 -> not postfix:i386=2.7.1-1 but postfix:i386=2.7.1-1" aptget install postfix --solver 3.0 +testfailuremsg "E: Conflict: exim4-daemon-light:i386 -> not postfix:i386=2.7.1-1 but postfix:i386=2.7.1-1" aptget install postfix --solver 3.0 allowremovemanual testfailureequal "Reading package lists... Building dependency tree... -- cgit v1.2.3-70-g09d2 From efedf5c4700bcdd22841cf6885485677a93cc31c Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Wed, 5 Feb 2025 16:29:37 +0100 Subject: solver3: Replace PropagateInstall() with Discover() Just propagate the stored clauses after we have discovered them; this is quite straightforward. We now more reliably discover common dependencies at the package level, adjust the test case accordingly. The next step is to make discovery recursive, or iterative, to build an entire recursive tree from all roots, and then we can reject reverse dependencies based on it. A bunch of refactorings are needed in the process. We remove the useless Hint enumeration and insert a flags struct into the State, such that we can record whether a package/version has been discovered, to avoid spending double time on discovery. --- apt-pkg/solver3.cc | 140 ++++++++++----------- apt-pkg/solver3.h | 36 +++--- ...est-bug-549968-install-depends-of-not-installed | 1 + 3 files changed, 84 insertions(+), 93 deletions(-) (limited to 'apt-pkg') diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index 5909bb55e..09ba920fa 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -196,7 +196,6 @@ APT::Solver::Solver(pkgCache &cache, pkgDepCache::Policy &policy) priorities(cache.Head().VersionCount), candidates(cache.Head().PackageCount) { - static_assert(sizeof(APT::Solver::State) == 3 * sizeof(int)); static_assert(sizeof(APT::Solver::Var) == sizeof(map_pointer)); static_assert(sizeof(APT::Solver::Var) == sizeof(map_pointer)); } @@ -356,61 +355,59 @@ bool APT::Solver::Propagate() { Var var = propQ.front(); propQ.pop(); - if ((*this)[var].decision == Decision::MUST && not PropagateInstall(var)) - return false; + if ((*this)[var].decision == Decision::MUST) + { + Discover(var); + for (auto &clause : (*this)[var].clauses) + if (not AddWork(Work{*clause.get(), depth()})) + return false; + } else if ((*this)[var].decision == Decision::MUSTNOT && not PropagateReject(var)) return false; } return true; } -bool APT::Solver::PropagateInstall(Var var) +void APT::Solver::RegisterClause(Clause &&clause) { + auto &clauses = (*this)[clause.reason].clauses; + clauses.push_back(std::make_unique(std::move(clause))); +} + +void APT::Solver::Discover(Var var) +{ + auto &state = (*this)[var]; + + if (state.flags.discovered) + return; + + state.flags.discovered = true; + if (auto Pkg = var.Pkg(cache); not Pkg.end()) { - bool anyInstallable = false; - bool anyMust = false; - // Insert the work item. Clause clause{Var(Pkg), Group::SelectVersion}; for (auto ver = Pkg.VersionList(); not ver.end(); ver++) - { clause.solutions.push_back(Var(ver)); - if ((*this)[ver].decision != Decision::MUSTNOT) - anyInstallable = true; - if ((*this)[ver].decision == Decision::MUST) - anyMust = true; - } - - // One is already marked for install, nothing to propagate - if (anyMust) - return true; - - if (not anyInstallable) - { - _error->Error("Conflict: %s -> %s but no versions are installable", - WhyStr((*this)[Pkg].reason).c_str(), Pkg.FullName().c_str()); - for (auto ver = Pkg.VersionList(); not ver.end(); ver++) - _error->Error("Uninstallable version: %s", WhyStr(Var(ver)).c_str()); - return false; - } std::stable_sort(clause.solutions.begin(), clause.solutions.end(), CompareProviders3{cache, policy, Pkg, *this}); - assert(clause.solutions.size() > 0); + RegisterClause(std::move(clause)); - if (not AddWork(Work{clause, depth()})) - return false; - - return EnqueueCommonDependencies(Pkg); + RegisterCommonDependencies(Pkg); } else if (auto Ver = var.Ver(cache); not Ver.end()) { - if (not Enqueue(Var(Ver.ParentPkg()), true, Var(Ver))) - return false; + Clause clause{Var(Ver), Group::SelectVersion}; + clause.solutions = {Var(Ver.ParentPkg())}; + RegisterClause(std::move(clause)); for (auto OV = Ver.ParentPkg().VersionList(); not OV.end(); ++OV) { - if (OV != Ver && not Enqueue(Var(OV), false, Var(Ver))) - return false; + if (OV == Ver) + continue; + + Clause clause{Var(Ver), Group::SelectVersion, false, true /* negative */}; + clause.solutions = {Var(OV)}; + RegisterClause(std::move(clause)); } for (auto dep = Ver.DependsList(); not dep.end();) @@ -420,12 +417,11 @@ bool APT::Solver::PropagateInstall(Var var) pkgCache::DepIterator end; dep.GlobOr(start, end); // advances dep - if (not EnqueueOrGroup(start, end, Var(Ver))) - return false; + auto clause = TranslateOrGroup(start, end, Var(Ver)); + + RegisterClause(std::move(clause)); } } - - return true; } bool APT::Solver::PropagateReject(Var var) @@ -465,7 +461,7 @@ bool APT::Solver::PropagateReject(Var var) return true; } -bool APT::Solver::EnqueueCommonDependencies(pkgCache::PkgIterator Pkg) +void APT::Solver::RegisterCommonDependencies(pkgCache::PkgIterator Pkg) { for (auto dep = Pkg.VersionList().DependsList(); not dep.end();) { @@ -484,36 +480,9 @@ bool APT::Solver::EnqueueCommonDependencies(pkgCache::PkgIterator Pkg) } if (not allHaveDep) continue; - if (not EnqueueOrGroup(start, end, Var(Pkg))) - return false; + auto clause = TranslateOrGroup(start, end, Var(Pkg)); + RegisterClause(std::move(clause)); } - - return true; -} - -bool APT::Solver::EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepIterator end, Var reason) -{ - auto clause = TranslateOrGroup(start, end, reason); - if (clause.negative) - { - for (auto var : clause.solutions) - if (not Enqueue(var, false, clause.reason)) - return false; - } - else if (not clause.solutions.empty()) - { - if (unlikely(debug >= 3 && clause.optional)) - { - std::cerr << "Enqueuing Recommends "; - clause.Dump(cache); - std::cerr << "\n"; - } - return AddWork(Work{std::move(clause), depth()}); - } - else if (not clause.optional) - return _error->Error("Unsatisfiable dependency group %s -> %s", reason.toString(cache).c_str(), start.TargetPkg().FullName().c_str()); - - return true; } APT::Solver::Clause APT::Solver::TranslateOrGroup(pkgCache::DepIterator start, pkgCache::DepIterator end, Var reason) @@ -533,6 +502,8 @@ APT::Solver::Clause APT::Solver::TranslateOrGroup(pkgCache::DepIterator start, p Clause clause{reason, Group::Satisfy, not start.IsCritical() /* optional */, start.IsNegative()}; + clause.dep = start; + do { auto begin = clause.solutions.size(); @@ -779,13 +750,32 @@ bool APT::Solver::Pop() bool APT::Solver::AddWork(Work &&w) { - if (w.clause.solutions.size() == 1 && not w.clause.optional) - return Enqueue(w.clause.solutions[0], true, w.clause.reason); + if (w.clause.negative) + { + for (auto var : w.clause.solutions) + if (not Enqueue(var, false, w.clause.reason)) + return false; + } + else if (not w.clause.solutions.empty()) + { + if (unlikely(debug >= 3 && w.clause.optional)) + { + std::cerr << "Enqueuing Recommends "; + w.clause.Dump(cache); + std::cerr << "\n"; + } + if (w.clause.solutions.size() == 1 && not w.clause.optional) + return Enqueue(w.clause.solutions[0], true, w.clause.reason); - w.size = std::count_if(w.clause.solutions.begin(), w.clause.solutions.end(), [this](auto V) - { return (*this)[V].decision != Decision::MUSTNOT; }); - work.push_back(std::move(w)); - std::push_heap(work.begin(), work.end()); + w.size = std::count_if(w.clause.solutions.begin(), w.clause.solutions.end(), [this](auto V) + { return (*this)[V].decision != Decision::MUSTNOT; }); + work.push_back(std::move(w)); + std::push_heap(work.begin(), work.end()); + } + else if (not w.clause.optional && w.clause.dep) + return _error->Error("Unsatisfiable dependency group %s -> %s", w.clause.reason.toString(cache).c_str(), pkgCache::DepIterator(cache, w.clause.dep).TargetPkg().FullName().c_str()); + else if (not w.clause.optional) + return _error->Error("Unsatisfiable dependency group %s", w.clause.reason.toString(cache).c_str()); return true; } diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h index 42cde96f5..118ea5e28 100644 --- a/apt-pkg/solver3.h +++ b/apt-pkg/solver3.h @@ -174,18 +174,19 @@ class Solver // \brief If set, we install missing recommends and pick new best packages. bool FixPolicyBroken{_config->FindB("APT::Get::Fix-Policy-Broken")}; + // \brief Discover a variable, translating the underlying dependencies to the SAT presentation + void Discover(Var var); + // \brief Link a clause into the watchers + void RegisterClause(Clause &&clause); // \brief Enqueue dependencies shared by all versions of the package. - [[nodiscard]] bool EnqueueCommonDependencies(pkgCache::PkgIterator Pkg); + void RegisterCommonDependencies(pkgCache::PkgIterator Pkg); + // \brief Reject reverse dependencies. Must call std::make_heap() after. [[nodiscard]] bool RejectReverseDependencies(pkgCache::VerIterator Ver); // \brief Translate an or group into a clause object [[nodiscard]] Clause TranslateOrGroup(pkgCache::DepIterator start, pkgCache::DepIterator end, Var reason); - // \brief Enqueue a single or group - [[nodiscard]] bool EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepIterator end, Var reason); // \brief Propagate all pending propagations [[nodiscard]] bool Propagate(); - // \brief Propagate a "true" value of a variable - [[nodiscard]] bool PropagateInstall(Var var); // \brief Propagate a rejection of a variable [[nodiscard]] bool PropagateReject(Var var); @@ -300,6 +301,8 @@ struct APT::Solver::Var */ struct APT::Solver::Clause { + // \brief Underyling dependency + pkgCache::Dependency *dep = nullptr; // \brief Var for the work Var reason; // \brief The group we are in @@ -365,17 +368,6 @@ enum class APT::Solver::Decision : uint16_t MUSTNOT, }; -// \brief Hints for the solver about the item. -enum class APT::Solver::Hint : uint16_t -{ - // \brief We have not made a choice about the package yet - NONE, - // \brief This package was listed as a Recommends of a must package, - SHOULD, - // \brief This package was listed as a Suggests of a must-not package - MAY, -}; - /** * \brief The solver state * @@ -403,8 +395,16 @@ struct APT::Solver::State // \brief This essentially describes the install state in RFC2119 terms. Decision decision{Decision::NONE}; - // \brief Any hint. - Hint hint{Hint::NONE}; + // \brief Flags. + struct + { + bool discovered{}; + } flags; + + static_assert(sizeof(flags) <= sizeof(int)); + + // \brief Clauses owned by this package/version + std::vector> clauses; }; /** diff --git a/test/integration/test-bug-549968-install-depends-of-not-installed b/test/integration/test-bug-549968-install-depends-of-not-installed index 33cbd6ee4..ec730c7b2 100755 --- a/test/integration/test-bug-549968-install-depends-of-not-installed +++ b/test/integration/test-bug-549968-install-depends-of-not-installed @@ -38,6 +38,7 @@ Delete extracoolstuff:i386 [0] Reject:extracoolstuff:i386 () [0] Install:coolstuff:i386 (coolstuff:i386=1.0) [0] Reject:extracoolstuff:i386=1.0 (not extracoolstuff:i386) +Optional Item (0@0) coolstuff:i386 -> | extracoolstuff:i386=1.0 Optional Item (0@0) coolstuff:i386=1.0 -> | extracoolstuff:i386=1.0 Recommended packages: -- cgit v1.2.3-70-g09d2 From 9b482fb51ed28ac75b6d4847729f72717f2ea431 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Wed, 5 Feb 2025 20:48:28 +0100 Subject: solver3: Support comparing packages and versions When comparing packages, we compare the best version for the package. To determine the best version, the rules for comparisons are applied normally. This allows us to mix packages and versions in a clause as the solutions for a dependency, which means we'll be able to defer the selection of a particular version of a package to a later time. --- apt-pkg/solver3.cc | 23 +++++++++++++++-------- 1 file changed, 15 insertions(+), 8 deletions(-) (limited to 'apt-pkg') diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index 09ba920fa..6288912f6 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -44,21 +44,28 @@ struct APT::Solver::CompareProviders3 /*{{{*/ pkgCache::PkgIterator const Pkg; APT::Solver &Solver; - bool operator()(pkgCache::Version *AV, pkgCache::Version *BV) + pkgCache::VerIterator bestVersion(pkgCache::PkgIterator pkg) { - return (*this)(pkgCache::VerIterator(Cache, AV), pkgCache::VerIterator(Cache, BV)); + 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) { - if (auto va = a.Ver(Cache)) - { - if (auto vb = b.Ver(Cache)) - return (*this)(va, vb); - } - abort(); + 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 -- cgit v1.2.3-70-g09d2 From 601af4e8adac4cdd57a031db5d073f61fc1033dc Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Wed, 5 Feb 2025 21:56:04 +0100 Subject: solver3: Refactor Dump() to toString() This vastly simplifies the code at the expense of performance, lol. --- apt-pkg/solver3.cc | 75 ++++++++++++++++++------------------------------------ apt-pkg/solver3.h | 6 ++--- 2 files changed, 27 insertions(+), 54 deletions(-) (limited to 'apt-pkg') diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index 6288912f6..01d93a6e3 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -221,24 +221,30 @@ bool APT::Solver::Work::operator<(APT::Solver::Work const &b) const return false; } -void APT::Solver::Clause::Dump(pkgCache &cache) + +std::string APT::Solver::Clause::toString(pkgCache &cache) { + std::string out; if (auto Pkg = reason.Pkg(cache); not Pkg.end()) - std::cerr << Pkg.FullName(); + out.append(Pkg.FullName()); if (auto Ver = reason.Ver(cache); not Ver.end()) - std::cerr << Ver.ParentPkg().FullName() << "=" << Ver.VerStr(); - std::cerr << " -> "; - for (auto sol : solutions) - std::cerr << " | " << sol.toString(cache); + out.append(Ver.ParentPkg().FullName()).append("=").append(Ver.VerStr()); + out.append(" -> "); + for (auto var : solutions) + out.append(" | ").append(var.toString(cache)); + return out; } -void APT::Solver::Work::Dump(pkgCache &cache) + +std::string APT::Solver::Work::toString(pkgCache &cache) { + std::ostringstream out; if (erased) - std::cerr << "Erased "; + out << "Erased "; if (clause.optional) - std::cerr << "Optional "; - std::cerr << "Item (" << ssize_t(size <= clause.solutions.size() ? size : -1) << "@" << depth << ") "; - clause.Dump(cache); + out << "Optional "; + out << "Item (" << ssize_t(size <= clause.solutions.size() ? size : -1) << "@" << depth << ") "; + out << clause.toString(cache); + return out.str(); } // Prints an implication graph part of the form A -> B -> C, possibly with "not" @@ -561,31 +567,19 @@ APT::Solver::Clause APT::Solver::TranslateOrGroup(pkgCache::DepIterator start, p if (important && wasImportant && not newOptional && not satisfied) { if (unlikely(debug >= 3)) - { - std::cerr << "Ignoring unsatisfied Recommends "; - clause.Dump(cache); - std::cerr << "\n"; - } + std::cerr << "Ignoring unsatisfied Recommends " << clause.toString(cache) << std::endl; clause.solutions.clear(); } else if (not important && not wasImportant && not newOptional && satisfied) { if (unlikely(debug >= 3)) - { - std::cerr << "Promoting satisfied Suggests to Recommends: "; - clause.Dump(cache); - std::cerr << "\n"; - } + std::cerr << "Promoting satisfied Suggests to Recommends: " << clause.toString(cache) << std::endl; important = true; } else if (not important) { if (unlikely(debug >= 3)) - { - std::cerr << "Ignoring Suggests "; - clause.Dump(cache); - std::cerr << "\n"; - } + std::cerr << "Ignoring Suggests " << clause.toString(cache) << std::endl; return Clause{reason, Group::Satisfy, true}; } } @@ -663,11 +657,7 @@ bool APT::Solver::RejectReverseDependencies(pkgCache::VerIterator Ver) void APT::Solver::Push(Work work) { if (unlikely(debug >= 2)) - { - std::cerr << "Trying choice for "; - work.Dump(cache); - std::cerr << "\n"; - } + std::cerr << "Trying choice for " << work.toString(cache) << std::endl; choices.push_back(solved.size()); solved.push_back(Solved{Var(), std::move(work)}); @@ -700,11 +690,7 @@ void APT::Solver::UndoOne() if (auto work = solvedItem.work) { if (unlikely(debug >= 4)) - { - std::cerr << "Adding work item "; - work->Dump(cache); - std::cerr << "\n"; - } + std::cerr << "Adding work item " << work->toString(cache) << std::endl; if (not AddWork(std::move(*work))) abort(); @@ -766,11 +752,7 @@ bool APT::Solver::AddWork(Work &&w) else if (not w.clause.solutions.empty()) { if (unlikely(debug >= 3 && w.clause.optional)) - { - std::cerr << "Enqueuing Recommends "; - w.clause.Dump(cache); - std::cerr << "\n"; - } + 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.reason); @@ -865,19 +847,12 @@ bool APT::Solver::Solve() { return (*this)[ver].decision == Decision::MUST; })) { if (unlikely(debug >= 2)) - { - std::cerr << "ELIDED "; - item.Dump(cache); - std::cerr << "\n"; - } + std::cerr << "ELIDED " << item.toString(cache) << std::endl; continue; } if (unlikely(debug >= 1)) - { - item.Dump(cache); - std::cerr << "\n"; - } + std::cerr << item.toString(cache) << std::endl; assert(item.clause.solutions.size() > 1 || item.clause.optional); diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h index 118ea5e28..fc68a5cef 100644 --- a/apt-pkg/solver3.h +++ b/apt-pkg/solver3.h @@ -317,8 +317,7 @@ struct APT::Solver::Clause inline Clause(Var reason, Group group, bool optional = false, bool negative = false) : reason(reason), group(group), optional(optional), negative(negative) {} - // \brief Dump the clause to std::cerr - void Dump(pkgCache &cache); + std::string toString(pkgCache &cache); }; /** @@ -352,8 +351,7 @@ struct APT::Solver::Work bool erased{false}; bool operator<(APT::Solver::Work const &b) const; - // \brief Dump the work item to std::cerr - void Dump(pkgCache &cache); + std::string toString(pkgCache &cache); inline Work(Clause clause, depth_type depth) : clause(std::move(clause)), depth(depth) {} }; -- cgit v1.2.3-70-g09d2 From 3d5f8042c64c30497a65e522c6e402eb4bab10c3 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Thu, 6 Feb 2025 10:44:34 +0100 Subject: solver3: Use a package clause for optional roots Instead of iterating over the version here and picking it, just enqueue the package as well, which should allow us to select the version at a later time. This also causes a funny inverse problem now, though, as was evidenced in one of the test cases: To summarize, if our optional roots are all single items, they will be considered soft-unit, causing them to be processed in order. However it can be that an optional root has a specific version selected because another version was rejected. Consider X Conflicts A (= 1) A, B have 2 versions: '2' available, '1' installed B (= n) Depends A (= n) Run `apt install X`. The expected result is for A and B to be upgraded to version 2. With only a package root, if B appears in the cache before A however, we will get: Install X Reject A (= 1) Install B Install B (= 1) # keep it installed Reject A (= 2) => A is being removed as both versions are rejected Hence we do also need to re-introduce the additional version clause, now we get: Install X Reject A (= 1) Install A (= 2) # it got "promoted" to a 'stronger' soft-unit Install B Fail B (= 1) # keep it installed Install B (= 2) Introduce a root state to hold all the clauses that don't have another owner. moo --- apt-pkg/solver3.cc | 24 ++++++++++++++++++++---- apt-pkg/solver3.h | 5 +++-- 2 files changed, 23 insertions(+), 6 deletions(-) (limited to 'apt-pkg') diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index 01d93a6e3..4ebc085a5 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -197,6 +197,7 @@ class DefaultRootSetFunc2 : public pkgDepCache::DefaultRootSetFunc APT::Solver::Solver(pkgCache &cache, pkgDepCache::Policy &policy) : cache(cache), policy(policy), + rootState(new State), pkgStates(cache.Head().PackageCount), verStates(cache.Head().VersionCount), pkgObsolete(cache.Head().PackageCount), @@ -205,6 +206,8 @@ APT::Solver::Solver(pkgCache &cache, pkgDepCache::Policy &policy) { 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; } // This function determines if a work item is less important than another. @@ -218,7 +221,8 @@ bool APT::Solver::Work::operator<(APT::Solver::Work const &b) const return clause.group > b.clause.group; if ((size < 2) != (b.size < 2)) return b.size < 2; - + if (size == 1 && b.size == 1) // Special case: 'shortcircuit' optional packages + return clause->solutions.size() < b.clause->solutions.size(); return false; } @@ -966,10 +970,22 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache) else { Clause w{Var(), Group, isOptional}; + w.solutions.push_back(Var(P)); + RegisterClause(std::move(w)); + if (not AddWork(Work{*rootState->clauses.back(), depth()})) + return false; + + // Given A->A2|A1, B->B1|B2; Bn->An, if we select `not A1`, we + // should try to install A2 before trying B so we end up with + // A2, B2, instead of removing A1 to keep B1 installed. This + // requires some special casing in Work::operator< above. + // Compare test-bug-712116-dpkg-pre-install-pkgs-hook-multiarch + Clause shortcircuit{Var(), Group, isOptional}; for (auto V = P.VersionList(); not V.end(); ++V) - w.solutions.push_back(Var(V)); - std::stable_sort(w.solutions.begin(), w.solutions.end(), CompareProviders3{cache, policy, P, *this}); - if (not AddWork(Work{std::move(w), depth()})) + shortcircuit.solutions.push_back(Var(V)); + std::stable_sort(shortcircuit.solutions.begin(), shortcircuit.solutions.end(), CompareProviders3{cache, policy, P, *this}); + RegisterClause(std::move(shortcircuit)); + if (not AddWork(Work{rootState->clauses.back().get(), depth()})) return false; } } diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h index fc68a5cef..d3e22eaba 100644 --- a/apt-pkg/solver3.h +++ b/apt-pkg/solver3.h @@ -93,6 +93,8 @@ class Solver pkgCache &cache; // Policy is needed for determining candidate version. pkgDepCache::Policy &policy; + // Root state + std::unique_ptr rootState; // States for packages std::vector pkgStates{}; // States for versions @@ -425,6 +427,5 @@ inline APT::Solver::State &APT::Solver::operator[](Var r) return (*this)[cache.PkgP + P]; if (auto V = r.Ver()) return (*this)[cache.VerP + V]; - - abort(); + return *rootState.get(); } -- cgit v1.2.3-70-g09d2 From ecb1399ca5f4917286d354b00dadb91c8075db1d Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Thu, 6 Feb 2025 11:28:07 +0100 Subject: solver3: Point to stored clauses, do not copy them This makes Work trivially destructible, and in turn solved, allowing their queues to be destructed without running destructors, and avoiding the copy should have a nice performance improvement. --- apt-pkg/solver3.cc | 75 ++++++++++++++++++++++++++++-------------------------- apt-pkg/solver3.h | 4 +-- 2 files changed, 41 insertions(+), 38 deletions(-) (limited to 'apt-pkg') diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index 4ebc085a5..f402d1ba3 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -204,6 +204,9 @@ APT::Solver::Solver(pkgCache &cache, pkgDepCache::Policy &policy) priorities(cache.Head().VersionCount), candidates(cache.Head().PackageCount) { + // 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)); // Root state is "true". @@ -213,12 +216,12 @@ APT::Solver::Solver(pkgCache &cache, pkgDepCache::Policy &policy) // This function determines if a work item is less important than another. bool APT::Solver::Work::operator<(APT::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; - if (clause.optional != b.clause.optional) - return clause.optional; - if (clause.group != b.clause.group) - return clause.group > b.clause.group; + if ((not clause->optional && size < 2) != (not b.clause->optional && b.size < 2)) + return not b.clause->optional && b.size < 2; + if (clause->optional != b.clause->optional) + return clause->optional; + if (clause->group != b.clause->group) + return clause->group > b.clause->group; if ((size < 2) != (b.size < 2)) return b.size < 2; if (size == 1 && b.size == 1) // Special case: 'shortcircuit' optional packages @@ -244,10 +247,10 @@ std::string APT::Solver::Work::toString(pkgCache &cache) std::ostringstream out; if (erased) out << "Erased "; - if (clause.optional) + if (clause->optional) out << "Optional "; - out << "Item (" << ssize_t(size <= clause.solutions.size() ? size : -1) << "@" << depth << ") "; - out << clause.toString(cache); + out << "Item (" << ssize_t(size <= clause->solutions.size() ? size : -1) << "@" << depth << ") "; + out << clause->toString(cache); return out.str(); } @@ -376,7 +379,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(), depth()})) return false; } else if ((*this)[var].decision == Decision::MUSTNOT && not PropagateReject(var)) @@ -747,28 +750,28 @@ bool APT::Solver::Pop() bool APT::Solver::AddWork(Work &&w) { - if (w.clause.negative) + if (w.clause->negative) { - for (auto var : w.clause.solutions) - if (not Enqueue(var, false, w.clause.reason)) + for (auto var : w.clause->solutions) + if (not Enqueue(var, false, w.clause->reason)) return false; } - else if (not w.clause.solutions.empty()) + else if (not w.clause->solutions.empty()) { - 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.reason); + 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->reason); - w.size = std::count_if(w.clause.solutions.begin(), w.clause.solutions.end(), [this](auto V) + w.size = std::count_if(w.clause->solutions.begin(), w.clause->solutions.end(), [this](auto V) { return (*this)[V].decision != Decision::MUSTNOT; }); work.push_back(std::move(w)); std::push_heap(work.begin(), work.end()); } - else if (not w.clause.optional && w.clause.dep) - return _error->Error("Unsatisfiable dependency group %s -> %s", w.clause.reason.toString(cache).c_str(), pkgCache::DepIterator(cache, w.clause.dep).TargetPkg().FullName().c_str()); - else if (not w.clause.optional) - return _error->Error("Unsatisfiable dependency group %s", w.clause.reason.toString(cache).c_str()); + else if (not w.clause->optional && w.clause->dep) + return _error->Error("Unsatisfiable dependency group %s -> %s", w.clause->reason.toString(cache).c_str(), pkgCache::DepIterator(cache, w.clause->dep).TargetPkg().FullName().c_str()); + else if (not w.clause->optional) + return _error->Error("Unsatisfiable dependency group %s", w.clause->reason.toString(cache).c_str()); return true; } @@ -783,7 +786,7 @@ void APT::Solver::RescoreWorkIfNeeded() { if (w.erased) continue; - size_t newSize = std::count_if(w.clause.solutions.begin(), w.clause.solutions.end(), [this](auto V) + size_t newSize = std::count_if(w.clause->solutions.begin(), w.clause->solutions.end(), [this](auto V) { return (*this)[V].decision != Decision::MUSTNOT; }); // Notably we only insert the work into the queue if it got smaller. Work that got larger @@ -832,7 +835,7 @@ bool APT::Solver::Solve() } // If our size increased, queue again. - size_t newSize = std::count_if(work.back().clause.solutions.begin(), work.back().clause.solutions.end(), [this](auto V) + size_t newSize = std::count_if(work.back().clause->solutions.begin(), work.back().clause->solutions.end(), [this](auto V) { return (*this)[V].decision != Decision::MUSTNOT; }); if (newSize > work.back().size) @@ -847,7 +850,7 @@ bool APT::Solver::Solve() work.pop_back(); solved.push_back(Solved{Var(), item}); - if (std::any_of(item.clause.solutions.begin(), item.clause.solutions.end(), [this](auto ver) + if (std::any_of(item.clause->solutions.begin(), item.clause->solutions.end(), [this](auto ver) { return (*this)[ver].decision == Decision::MUST; })) { if (unlikely(debug >= 2)) @@ -858,10 +861,10 @@ bool APT::Solver::Solve() if (unlikely(debug >= 1)) std::cerr << item.toString(cache) << std::endl; - assert(item.clause.solutions.size() > 1 || item.clause.optional); + assert(item.clause->solutions.size() > 1 || item.clause->optional); bool foundSolution = false; - for (auto &sol : item.clause.solutions) + for (auto &sol : item.clause->solutions) { if ((*this)[sol].decision == Decision::MUSTNOT) { @@ -869,26 +872,26 @@ bool APT::Solver::Solve() std::cerr << "(existing conflict: " << sol.toString(cache) << ")\n"; continue; } - if (item.size > 1 || item.clause.optional) + if (item.size > 1 || item.clause->optional) { item.choice = sol; Push(item); } if (unlikely(debug >= 3)) std::cerr << "(try it: " << sol.toString(cache) << ")\n"; - if (not Enqueue(sol, true, item.clause.reason) && not Pop()) + if (not Enqueue(sol, true, item.clause->reason) && not Pop()) return false; foundSolution = true; break; } - if (not foundSolution && not item.clause.optional) + if (not foundSolution && not item.clause->optional) { std::ostringstream dep; - assert(item.clause.solutions.size() > 0); - for (auto &sol : item.clause.solutions) + assert(item.clause->solutions.size() > 0); + for (auto &sol : item.clause->solutions) dep << (dep.tellp() == 0 ? "" : " | ") << sol.toString(cache); - _error->Error("Unsatisfiable dependency: %s -> %s", WhyStr(item.clause.reason).c_str(), dep.str().c_str()); - for (auto &sol : item.clause.solutions) + _error->Error("Unsatisfiable dependency: %s -> %s", WhyStr(item.clause->reason).c_str(), dep.str().c_str()); + for (auto &sol : item.clause->solutions) if ((*this)[sol].decision == Decision::MUSTNOT) _error->Error("Not considered: %s: %s", sol.toString(cache).c_str(), WhyStr(sol).c_str()); @@ -972,7 +975,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache) Clause w{Var(), Group, isOptional}; w.solutions.push_back(Var(P)); RegisterClause(std::move(w)); - if (not AddWork(Work{*rootState->clauses.back(), depth()})) + if (not AddWork(Work{rootState->clauses.back().get(), depth()})) return false; // Given A->A2|A1, B->B1|B2; Bn->An, if we select `not A1`, we diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h index d3e22eaba..bbe3f3d56 100644 --- a/apt-pkg/solver3.h +++ b/apt-pkg/solver3.h @@ -334,7 +334,7 @@ struct APT::Solver::Clause */ struct APT::Solver::Work { - Clause clause; + Clause *clause; // \brief The depth at which the item has been added depth_type depth; @@ -354,7 +354,7 @@ struct APT::Solver::Work bool operator<(APT::Solver::Work const &b) const; std::string toString(pkgCache &cache); - inline Work(Clause clause, depth_type depth) : clause(std::move(clause)), depth(depth) {} + inline Work(Clause *clause, depth_type depth) : clause(clause), depth(depth) {} }; // \brief This essentially describes the install state in RFC2119 terms. -- cgit v1.2.3-70-g09d2 From 8f4c09bb58b047a73328f935b9abeb4fe0b03ae1 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Thu, 6 Feb 2025 12:28:57 +0100 Subject: solver3: Add const where helpful operator[] is a bit annoying here, but oh well, what can we do? --- apt-pkg/solver3.cc | 8 ++++---- apt-pkg/solver3.h | 26 ++++++++++++++++++++------ 2 files changed, 24 insertions(+), 10 deletions(-) (limited to 'apt-pkg') diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index f402d1ba3..36bdd9aeb 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -229,7 +229,7 @@ bool APT::Solver::Work::operator<(APT::Solver::Work const &b) const return false; } -std::string APT::Solver::Clause::toString(pkgCache &cache) +std::string APT::Solver::Clause::toString(pkgCache &cache) const { std::string out; if (auto Pkg = reason.Pkg(cache); not Pkg.end()) @@ -242,7 +242,7 @@ std::string APT::Solver::Clause::toString(pkgCache &cache) return out; } -std::string APT::Solver::Work::toString(pkgCache &cache) +std::string APT::Solver::Work::toString(pkgCache &cache) const { std::ostringstream out; if (erased) @@ -255,7 +255,7 @@ std::string APT::Solver::Work::toString(pkgCache &cache) } // Prints an implication graph part of the form A -> B -> C, possibly with "not" -std::string APT::Solver::WhyStr(Var reason) +std::string APT::Solver::WhyStr(Var reason) const { std::vector out; @@ -997,7 +997,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache) return Propagate(); } -bool APT::Solver::ToDepCache(pkgDepCache &depcache) +bool APT::Solver::ToDepCache(pkgDepCache &depcache) const { pkgDepCache::ActionGroup group(depcache); for (auto P = cache.PkgBegin(); not P.end(); P++) diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h index bbe3f3d56..9059552b7 100644 --- a/apt-pkg/solver3.h +++ b/apt-pkg/solver3.h @@ -105,14 +105,23 @@ class Solver { return pkgStates[P->ID]; } + inline const State &operator[](pkgCache::Package *P) const + { + return pkgStates[P->ID]; + } // \brief Helper function for safe access to version state. inline State &operator[](pkgCache::Version *V) { return verStates[V->ID]; } + inline const State &operator[](pkgCache::Version *V) const + { + return verStates[V->ID]; + } // \brief Helper function for safe access to either state. inline State &operator[](Var r); + inline const State &operator[](Var r) const; mutable std::vector pkgObsolete; bool Obsolete(pkgCache::PkgIterator pkg) const; @@ -221,13 +230,13 @@ class Solver // \brief Apply the selections from the dep cache to the solver [[nodiscard]] bool FromDepCache(pkgDepCache &depcache); // \brief Apply the solver result to the depCache - [[nodiscard]] bool ToDepCache(pkgDepCache &depcache); + [[nodiscard]] bool ToDepCache(pkgDepCache &depcache) const; // \brief Solve the dependencies [[nodiscard]] bool Solve(); // Print dependency chain - std::string WhyStr(Var reason); + std::string WhyStr(Var reason) const; }; }; // namespace APT @@ -319,7 +328,7 @@ struct APT::Solver::Clause inline Clause(Var reason, Group group, bool optional = false, bool negative = false) : reason(reason), group(group), optional(optional), negative(negative) {} - std::string toString(pkgCache &cache); + std::string toString(pkgCache &cache) const; }; /** @@ -334,7 +343,7 @@ struct APT::Solver::Clause */ struct APT::Solver::Work { - Clause *clause; + const Clause *clause; // \brief The depth at which the item has been added depth_type depth; @@ -353,8 +362,8 @@ struct APT::Solver::Work bool erased{false}; bool operator<(APT::Solver::Work const &b) const; - std::string toString(pkgCache &cache); - inline Work(Clause *clause, depth_type depth) : clause(clause), depth(depth) {} + 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. @@ -429,3 +438,8 @@ inline APT::Solver::State &APT::Solver::operator[](Var r) return (*this)[cache.VerP + V]; return *rootState.get(); } + +inline const APT::Solver::State &APT::Solver::operator[](Var r) const +{ + return const_cast(*this)[r]; +} -- cgit v1.2.3-70-g09d2 From cce96b85691fac0bbbbb84a501c6f39a0c9125c0 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Thu, 6 Feb 2025 12:40:01 +0100 Subject: solver3: Avoid std::vector for statically sized arrays The bounds checking on the vector accesses is killing performance, so switch from vector to a basic array, given that we don't actually need _any_ functionality from vector... Of course while we are at it, let us define a safe wrapper around it so we cannot accidentally index arrays for package IDs with version IDs and whatnot. --- apt-pkg/solver3.cc | 22 ++++++++-------- apt-pkg/solver3.h | 74 +++++++++++++++++++++++++++++++++++++++++++----------- 2 files changed, 70 insertions(+), 26 deletions(-) (limited to 'apt-pkg') diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index 36bdd9aeb..ed9beb828 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -198,11 +198,11 @@ APT::Solver::Solver(pkgCache &cache, pkgDepCache::Policy &policy) : cache(cache), policy(policy), rootState(new State), - pkgStates(cache.Head().PackageCount), - verStates(cache.Head().VersionCount), - pkgObsolete(cache.Head().PackageCount), - priorities(cache.Head().VersionCount), - candidates(cache.Head().PackageCount) + pkgStates(cache), + verStates(cache), + pkgObsolete(cache), + priorities(cache), + candidates(cache) { // Ensure trivially static_assert(std::is_trivially_destructible_v); @@ -295,7 +295,7 @@ bool APT::Solver::ObsoletedByNewerSourceVersion(pkgCache::VerIterator cand) cons if (priority == 0 || priority < candPriority) continue; - pkgObsolete[pkg->ID] = 2; + pkgObsolete[pkg] = 2; if (debug >= 3) std::cerr << "Obsolete: " << cand.ParentPkg().FullName() << "=" << cand.VerStr() << " due to " << ver.ParentPkg().FullName() << "=" << ver.VerStr() << "\n"; return true; @@ -306,8 +306,8 @@ bool APT::Solver::ObsoletedByNewerSourceVersion(pkgCache::VerIterator cand) cons bool APT::Solver::Obsolete(pkgCache::PkgIterator pkg) const { - if (pkgObsolete[pkg->ID] != 0) - return pkgObsolete[pkg->ID] == 2; + if (pkgObsolete[pkg] != 0) + return pkgObsolete[pkg] == 2; auto ver = GetCandidateVer(pkg); @@ -317,7 +317,7 @@ bool APT::Solver::Obsolete(pkgCache::PkgIterator pkg) const { if (debug >= 3) std::cerr << "Obsolete: " << pkg.FullName() << " - not installable\n"; - pkgObsolete[pkg->ID] = 2; + pkgObsolete[pkg] = 2; return true; } @@ -327,12 +327,12 @@ bool APT::Solver::Obsolete(pkgCache::PkgIterator pkg) const for (auto file = ver.FileList(); !file.end(); file++) if ((file.File()->Flags & pkgCache::Flag::NotSource) == 0) { - pkgObsolete[pkg->ID] = 1; + pkgObsolete[pkg] = 1; return false; } if (debug >= 3) std::cerr << "Obsolete: " << ver.ParentPkg().FullName() << "=" << ver.VerStr() << " - not installable\n"; - pkgObsolete[pkg->ID] = 2; + pkgObsolete[pkg] = 2; return true; } bool APT::Solver::Assume(Var var, bool decision, Var reason) diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h index 9059552b7..65cd9f017 100644 --- a/apt-pkg/solver3.h +++ b/apt-pkg/solver3.h @@ -20,6 +20,48 @@ namespace APT { +/** + * \brief A simple mapping from objects in the cache to user-defined types. + * + * This default initializes an array with the specified value type for each + * object in the cache of that type. + */ +template +class ContiguousCacheMap +{ + V *data_; // Avoid std::unique_ptr() as it may check that it's non-null. + + public: + ContiguousCacheMap(pkgCache &cache) + { + static_assert(std::is_constructible_v); + if constexpr (fast) + { + static_assert(std::is_trivially_constructible_v); + static_assert(std::is_trivially_destructible_v); + } + + size_t size; + if constexpr (std::is_same_v) + size = cache.Head().VersionCount; + else if constexpr (std::is_same_v) + size = cache.Head().PackageCount; + else + static_assert(false, "Cannot construct map for key type"); + + data_ = new V[size]{}; + } + V &operator[](const K *key) { return data_[key->ID]; } + const V &operator[](const K *key) const { return data_[key->ID]; } + ~ContiguousCacheMap() { delete[] data_; } +}; + +/** + * \brief A version of ContiguousCacheMap that ensures allocation and deallocation is trivial. + */ +template +using FastContiguousCacheMap = ContiguousCacheMap; + /* * \brief APT 3.0 solver * @@ -96,49 +138,51 @@ class Solver // Root state std::unique_ptr rootState; // States for packages - std::vector pkgStates{}; + ContiguousCacheMap pkgStates; // States for versions - std::vector verStates{}; + ContiguousCacheMap verStates; // \brief Helper function for safe access to package state. inline State &operator[](pkgCache::Package *P) { - return pkgStates[P->ID]; + return pkgStates[P]; } inline const State &operator[](pkgCache::Package *P) const { - return pkgStates[P->ID]; + return pkgStates[P]; } // \brief Helper function for safe access to version state. inline State &operator[](pkgCache::Version *V) { - return verStates[V->ID]; + return verStates[V]; } inline const State &operator[](pkgCache::Version *V) const { - return verStates[V->ID]; + return verStates[V]; } // \brief Helper function for safe access to either state. inline State &operator[](Var r); inline const State &operator[](Var r) const; - mutable std::vector pkgObsolete; + mutable FastContiguousCacheMap pkgObsolete; bool Obsolete(pkgCache::PkgIterator pkg) const; bool ObsoletedByNewerSourceVersion(pkgCache::VerIterator cand) const; - mutable std::vector priorities; + + mutable FastContiguousCacheMap priorities; short GetPriority(pkgCache::VerIterator ver) const { - if (priorities[ver->ID] == 0) - priorities[ver->ID] = policy.GetPriority(ver); - return priorities[ver->ID]; + if (priorities[ver] == 0) + priorities[ver] = policy.GetPriority(ver); + return priorities[ver]; } - mutable std::vector candidates; + + mutable ContiguousCacheMap candidates; pkgCache::VerIterator GetCandidateVer(pkgCache::PkgIterator pkg) const { - if (candidates[pkg->ID].end()) - candidates[pkg->ID] = policy.GetCandidateVer(pkg); - return candidates[pkg->ID]; + if (candidates[pkg].end()) + candidates[pkg] = policy.GetCandidateVer(pkg); + return candidates[pkg]; } // \brief Heap of the remaining work. -- cgit v1.2.3-70-g09d2