From 761fc96fe6158d46f11137c14822545ac0b0fe91 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Thu, 1 Aug 2024 12:43:09 +0900 Subject: solver3: Track all assignments and undo them individually Adopt MiniSAT's strategy for dealing with assignments and choices, having a single step undoOne() function to undo one and record them all on the queue; this should likely speed up backtracking since we no longer need to rescan everything. --- apt-pkg/solver3.cc | 127 ++++++++++++++++++++++++++++++----------------------- apt-pkg/solver3.h | 61 ++++++++++++++++++------- 2 files changed, 116 insertions(+), 72 deletions(-) diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index 2ba6f6065..c18420d71 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -169,8 +169,7 @@ APT::Solver::Solver(pkgCache &cache, pkgDepCache::Policy &policy) verStates(cache.Head().VersionCount), pkgObsolete(cache.Head().PackageCount) { - static_assert(sizeof(APT::Solver::State) == 3 * sizeof(int)); - static_assert(sizeof(APT::Solver::State) == 3 * sizeof(int)); + static_assert(sizeof(APT::Solver::State) == 3 * sizeof(int)); static_assert(sizeof(APT::Solver::Reason) == sizeof(map_pointer)); static_assert(sizeof(APT::Solver::Reason) == sizeof(map_pointer)); } @@ -333,6 +332,7 @@ bool APT::Solver::Install(pkgCache::PkgIterator Pkg, Reason reason, Group group) if (unlikely(debug >= 1)) std::cerr << "[" << depth() << "] Install:" << Pkg.FullName() << " (" << WhyStr(reason) << ")\n"; (*this)[Pkg] = {reason, depth(), Decision::MUST}; + solved.push_back(Solved{Reason(Pkg), std::nullopt}); // Insert the work item. Work workItem{Reason(Pkg), depth(), group}; @@ -383,8 +383,12 @@ bool APT::Solver::Install(pkgCache::VerIterator Ver, Reason reason, Group group) if (unlikely(debug >= 1)) std::cerr << "[" << depth() << "] Install:" << Ver.ParentPkg().FullName() << "=" << Ver.VerStr() << " (" << WhyStr(reason) << ")\n"; (*this)[Ver] = {reason, depth(), Decision::MUST}; + solved.push_back(Solved{Reason(Ver), std::nullopt}); if ((*this)[Ver.ParentPkg()].decision != Decision::MUST) + { (*this)[Ver.ParentPkg()] = {Reason(Ver), depth(), Decision::MUST}; + solved.push_back(Solved{Reason(Ver.ParentPkg()), std::nullopt}); + } for (auto OV = Ver.ParentPkg().VersionList(); not OV.end(); ++OV) { @@ -422,6 +426,7 @@ bool APT::Solver::Reject(pkgCache::PkgIterator Pkg, Reason reason, Group group) if (unlikely(debug >= 1)) std::cerr << "[" << depth() << "] Reject:" << Pkg.FullName() << " (" << WhyStr(reason) << ")\n"; (*this)[Pkg] = {reason, depth(), Decision::MUSTNOT}; + solved.push_back(Solved{Reason(Pkg), std::nullopt}); for (auto ver = Pkg.VersionList(); not ver.end(); ver++) if (not Reject(ver, Reason(Pkg), group)) return false; @@ -450,6 +455,7 @@ bool APT::Solver::Reject(pkgCache::VerIterator Ver, Reason reason, Group group) if (unlikely(debug >= 1)) std::cerr << "[" << depth() << "] Reject:" << Ver.ParentPkg().FullName() << "=" << Ver.VerStr() << " (" << WhyStr(reason) << ")\n"; (*this)[Ver] = {reason, depth(), Decision::MUSTNOT}; + solved.push_back(Solved{Reason(Ver), std::nullopt}); if (auto pkg = Ver.ParentPkg(); (*this)[pkg].decision != Decision::MUSTNOT) { bool anyInstallable = false; @@ -471,7 +477,10 @@ bool APT::Solver::Reject(pkgCache::VerIterator Ver, Reason reason, Group group) (Ver.ParentPkg().FullName() + "=" + Ver.VerStr()).c_str()); } else if ((*this)[Ver.ParentPkg()].decision != Decision::MUSTNOT) // Last installable invalidated + { (*this)[Ver.ParentPkg()] = {Reason(Ver), depth(), Decision::MUSTNOT}; + solved.push_back(Solved{Reason(Ver), std::nullopt}); + } } if (not RejectReverseDependencies(Ver)) @@ -729,15 +738,55 @@ void APT::Solver::Push(Work work) work.Dump(cache); std::cerr << "\n"; } - choices.push_back(std::move(work)); + + choices.push_back(solved.size()); + solved.push_back(Solved{Reason(), std::move(work)}); // Pop() will call MergeWithStack() when reverting to level 0, or RevertToStack after dumping to the debug log. _error->PushToStack(); } +void APT::Solver::UndoOne() +{ + auto solvedItem = solved.back(); + + if (unlikely(debug >= 4)) + std::cerr << "Undoing a single decision\n"; + + if (not solvedItem.assigned.empty()) + { + if (unlikely(debug >= 4)) + { + if (auto P = solvedItem.assigned.Pkg(cache); not P.end()) + std::cerr << "Unassign " << P.FullName() << "\n"; + if (auto V = solvedItem.assigned.Ver(cache); not V.end()) + std::cerr << "Unassign " << V.ParentPkg().FullName() << "=" << V.VerStr() << "\n"; + } + auto &state = (*this)[solvedItem.assigned]; + state.decision = Decision::NONE; + state.reason = Reason(); + state.depth = 0; + } + + if (auto work = solvedItem.work) + { + if (unlikely(debug >= 4)) + { + std::cerr << "Adding work item "; + work->Dump(cache); + std::cerr << "\n"; + } + + AddWork(std::move(*work)); + } + + solved.pop_back(); + + // FIXME: Add the undo handling here once we have watchers. +} + bool APT::Solver::Pop() { - auto depth = APT::Solver::depth(); - if (depth == 0) + if (depth() == 0) return false; if (unlikely(debug >= 2)) @@ -746,64 +795,30 @@ bool APT::Solver::Pop() _error->RevertToStack(); - depth--; - - // Clean up the higher level states. - // FIXME: Do not override the hints here. - for (auto &state : pkgStates) - if (state.depth > depth) - state = {}; - for (auto &state : verStates) - if (state.depth > depth) - state = {}; - - // This destroys the invariants that `work` must be a heap. But this is ok: - // we are restoring the invariant below, because rejecting a package always - // calls std::make_heap. - work.erase(std::remove_if(work.begin(), work.end(), [depth](Work &w) -> bool - { return w.depth > depth || w.dirty; }), + assert(choices.back() < solved.size()); + int itemsToUndo = solved.size() - choices.back(); + pkgCache::VerIterator choice(cache, solved[choices.back()].work->choice); + + for (; itemsToUndo; --itemsToUndo) + UndoOne(); + + // We need to remove any work that is at a higher depth. + choices.pop_back(); + work.erase(std::remove_if(work.begin(), work.end(), [this](Work &w) -> bool + { return w.depth > depth() || w.dirty; }), work.end()); std::make_heap(work.begin(), work.end()); - // Go over the solved items, see if any of them need to be moved back or deleted. - solved.erase(std::remove_if(solved.begin(), solved.end(), [this, depth](Work &w) -> bool - { - if (w.depth > depth) // Deeper decision level is no longer valid. - return true; - // This item is still solved, keep it on the solved list. - if (std::any_of(w.solutions.begin(), w.solutions.end(), [this](auto ver) - { return (*this)[ver].decision == Decision::MUST; })) - return false; - // We are not longer solved, move it back to work. - AddWork(std::move(w)); - return true; }), - solved.end()); - - Work w = std::move(choices.back()); - choices.pop_back(); if (unlikely(debug >= 2)) - { - std::cerr << "Backtracking to choice "; - w.Dump(cache); - std::cerr << "\n"; - } - if (unlikely(debug >= 4)) - { - std::cerr << "choices: "; - for (auto &i : choices) - { - std::cerr << pkgCache::VerIterator(cache, i.choice).ParentPkg().FullName(true) << "=" << pkgCache::VerIterator(cache, i.choice).VerStr(); - } - std::cerr << std::endl; - } + std::cerr << "Backtracking to choice " << choice.ParentPkg().FullName() << "=" << choice.VerStr() << "\n"; - assert(w.choice != nullptr); // FIXME: There should be a reason! - if (not Reject(pkgCache::VerIterator(cache, w.choice), {}, Group::HoldOrDelete)) + if (not Reject(choice, {}, Group::HoldOrDelete)) return false; - w.choice = nullptr; - AddWork(std::move(w)); + if (unlikely(debug >= 2)) + std::cerr << "Backtracked to choice " << choice.ParentPkg().FullName() << "=" << choice.VerStr() << "\n"; + return true; } @@ -879,7 +894,7 @@ bool APT::Solver::Solve() auto item = std::move(work.back()); work.pop_back(); - solved.push_back(item); + solved.push_back(Solved{Reason(), item}); if (std::any_of(item.solutions.begin(), item.solutions.end(), [this](auto ver) { return (*this)[ver].decision == Decision::MUST; })) diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h index 33067a0ad..eb8d246bf 100644 --- a/apt-pkg/solver3.h +++ b/apt-pkg/solver3.h @@ -7,6 +7,7 @@ * SPDX-License-Identifier: GPL-2.0+ */ +#include #include #include @@ -33,9 +34,9 @@ class Solver enum class Hint : uint16_t; struct Reason; struct CompareProviders3; - template struct State; struct Work; + struct Solved; // \brief Groups of works, these are ordered. // @@ -88,21 +89,23 @@ class Solver // Policy is needed for determining candidate version. pkgDepCache::Policy &policy; // States for packages - std::vector> pkgStates{}; + std::vector pkgStates{}; // States for versions - std::vector> verStates{}; + std::vector verStates{}; // \brief Helper function for safe access to package state. - inline State &operator[](pkgCache::Package *P) + inline State &operator[](pkgCache::Package *P) { return pkgStates[P->ID]; } // \brief Helper function for safe access to version state. - inline State &operator[](pkgCache::Version *V) + inline State &operator[](pkgCache::Version *V) { return verStates[V->ID]; } + // \brief Helper function for safe access to either state. + inline State &operator[](Reason r); mutable std::vector pkgObsolete; bool Obsolete(pkgCache::PkgIterator pkg) const; @@ -118,17 +121,18 @@ class Solver // \brief Whether RescoreWork() actually needs to rescore the work. bool needsRescore{false}; - // \brief Current decision level. - // - // Each time a decision needs to be made we can push the item under - // consideration to our backlog of choices made and then later we can - // restore it easily. - std::vector choices{}; // \brief Backlog of solved work. // // Solved work may become invalidated when backtracking, so store it - // here to revisit it later. - std::vector solved{}; + // here to revisit it later. This is similar to what MiniSAT calls the + // trail; one distinction is that we have both literals and our work + // queue to be concerned about + std::vector solved{}; + + // \brief Current decision level. + // + // This is an index into the solved vector. + std::vector choices{}; /// Various configuration options // \brief Debug level @@ -159,9 +163,11 @@ class Solver public: // \brief Create a new decision level. - bool Pop(); - // \brief Revert to the previous decision level. void Push(Work work); + // \brief Revert to the previous decision level. + bool Pop(); + // \brief Undo a single assignment / solved work item + void UndoOne(); // \brief Add work to our work queue. void AddWork(Work &&work); // \brief Rescore the work after a reject or a pop @@ -310,7 +316,6 @@ enum class APT::Solver::Hint : uint16_t * For each version, the solver records a decision at a certain level. It * maintains an array mapping from version ID to state. */ -template struct APT::Solver::State { // \brief The reason for causing this state (invalid for NONE). @@ -335,3 +340,27 @@ struct APT::Solver::State // \brief Any hint. Hint hint{Hint::NONE}; }; + +/** + * \brief A solved item. + * + * Here we keep track of solved clauses and variable assignments such that we can easily undo + * them. + */ +struct APT::Solver::Solved +{ + // \brief A variable that has been assigned. We store this as a reason (FIXME: Rename Reason to Var) + Reason assigned; + // \brief A work item that has been solved. This needs to be put back on the queue. + std::optional work; +}; + +inline APT::Solver::State &APT::Solver::operator[](Reason r) +{ + if (auto P = r.Pkg()) + return (*this)[cache.PkgP + P]; + if (auto V = r.Ver()) + return (*this)[cache.VerP + V]; + + abort(); +} -- cgit v1.2.3-70-g09d2 From a5a7b6905dc021d9773229e47ec60367e3e606d8 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Thu, 1 Aug 2024 14:25:25 +0900 Subject: solver3: Rename Reason to Var --- apt-pkg/solver3.cc | 76 +++++++++++++++++++++++++++--------------------------- apt-pkg/solver3.h | 44 +++++++++++++++---------------- 2 files changed, 60 insertions(+), 60 deletions(-) diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index c18420d71..5065b9a87 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -170,8 +170,8 @@ APT::Solver::Solver(pkgCache &cache, pkgDepCache::Policy &policy) pkgObsolete(cache.Head().PackageCount) { static_assert(sizeof(APT::Solver::State) == 3 * sizeof(int)); - static_assert(sizeof(APT::Solver::Reason) == sizeof(map_pointer)); - static_assert(sizeof(APT::Solver::Reason) == sizeof(map_pointer)); + static_assert(sizeof(APT::Solver::Var) == sizeof(map_pointer)); + static_assert(sizeof(APT::Solver::Var) == sizeof(map_pointer)); } // This function determines if a work item is less important than another. @@ -214,7 +214,7 @@ void APT::Solver::Work::Dump(pkgCache &cache) } // Prints an implication graph part of the form A -> B -> C, possibly with "not" -std::string APT::Solver::WhyStr(Reason reason) +std::string APT::Solver::WhyStr(Var reason) { std::vector out; @@ -305,14 +305,14 @@ bool APT::Solver::Obsolete(pkgCache::PkgIterator pkg) const return true; } -bool APT::Solver::Install(pkgCache::PkgIterator Pkg, Reason reason, Group group) +bool APT::Solver::Install(pkgCache::PkgIterator Pkg, Var reason, Group group) { if ((*this)[Pkg].decision == Decision::MUST) return true; // Check conflicting selections if ((*this)[Pkg].decision == Decision::MUSTNOT) - return _error->Error("Conflict: %s -> %s but %s", WhyStr(reason).c_str(), Pkg.FullName().c_str(), WhyStr(Reason(Pkg)).c_str()); + return _error->Error("Conflict: %s -> %s but %s", WhyStr(reason).c_str(), Pkg.FullName().c_str(), WhyStr(Var(Pkg)).c_str()); bool anyInstallable = false; for (auto ver = Pkg.VersionList(); not ver.end(); ver++) @@ -324,7 +324,7 @@ bool APT::Solver::Install(pkgCache::PkgIterator Pkg, Reason reason, Group group) _error->Error("Conflict: %s -> %s but no versions are installable", WhyStr(reason).c_str(), Pkg.FullName().c_str()); for (auto ver = Pkg.VersionList(); not ver.end(); ver++) - _error->Error("Uninstallable version: %s", WhyStr(Reason(ver)).c_str()); + _error->Error("Uninstallable version: %s", WhyStr(Var(ver)).c_str()); return false; } @@ -332,10 +332,10 @@ bool APT::Solver::Install(pkgCache::PkgIterator Pkg, Reason reason, Group group) if (unlikely(debug >= 1)) std::cerr << "[" << depth() << "] Install:" << Pkg.FullName() << " (" << WhyStr(reason) << ")\n"; (*this)[Pkg] = {reason, depth(), Decision::MUST}; - solved.push_back(Solved{Reason(Pkg), std::nullopt}); + solved.push_back(Solved{Var(Pkg), std::nullopt}); // Insert the work item. - Work workItem{Reason(Pkg), depth(), group}; + Work workItem{Var(Pkg), depth(), group}; for (auto ver = Pkg.VersionList(); not ver.end(); ver++) if (IsAllowedVersion(ver)) workItem.solutions.push_back(ver); @@ -353,7 +353,7 @@ bool APT::Solver::Install(pkgCache::PkgIterator Pkg, Reason reason, Group group) return true; } -bool APT::Solver::Install(pkgCache::VerIterator Ver, Reason reason, Group group) +bool APT::Solver::Install(pkgCache::VerIterator Ver, Var reason, Group group) { if ((*this)[Ver].decision == Decision::MUST) return true; @@ -366,33 +366,33 @@ bool APT::Solver::Install(pkgCache::VerIterator Ver, Reason reason, Group group) return _error->Error("Conflict: %s -> %s but %s", WhyStr(reason).c_str(), (Ver.ParentPkg().FullName() + "=" + Ver.VerStr()).c_str(), - WhyStr(Reason(Ver)).c_str()); + WhyStr(Var(Ver)).c_str()); if ((*this)[Ver.ParentPkg()].decision == Decision::MUSTNOT) return _error->Error("Conflict: %s -> %s but %s", WhyStr(reason).c_str(), (Ver.ParentPkg().FullName() + "=" + Ver.VerStr()).c_str(), - WhyStr(Reason(Ver.ParentPkg())).c_str()); + WhyStr(Var(Ver.ParentPkg())).c_str()); for (auto otherVer = Ver.ParentPkg().VersionList(); not otherVer.end(); otherVer++) if (otherVer->ID != Ver->ID && (*this)[otherVer].decision == Decision::MUST) return _error->Error("Conflict: %s -> %s but %s", WhyStr(reason).c_str(), (Ver.ParentPkg().FullName() + "=" + Ver.VerStr()).c_str(), - WhyStr(Reason(otherVer)).c_str()); + WhyStr(Var(otherVer)).c_str()); // Note decision if (unlikely(debug >= 1)) std::cerr << "[" << depth() << "] Install:" << Ver.ParentPkg().FullName() << "=" << Ver.VerStr() << " (" << WhyStr(reason) << ")\n"; (*this)[Ver] = {reason, depth(), Decision::MUST}; - solved.push_back(Solved{Reason(Ver), std::nullopt}); + solved.push_back(Solved{Var(Ver), std::nullopt}); if ((*this)[Ver.ParentPkg()].decision != Decision::MUST) { - (*this)[Ver.ParentPkg()] = {Reason(Ver), depth(), Decision::MUST}; - solved.push_back(Solved{Reason(Ver.ParentPkg()), std::nullopt}); + (*this)[Ver.ParentPkg()] = {Var(Ver), depth(), Decision::MUST}; + solved.push_back(Solved{Var(Ver.ParentPkg()), std::nullopt}); } for (auto OV = Ver.ParentPkg().VersionList(); not OV.end(); ++OV) { - if (OV != Ver && not Reject(OV, Reason(Ver), group)) + if (OV != Ver && not Reject(OV, Var(Ver), group)) return false; } @@ -403,14 +403,14 @@ bool APT::Solver::Install(pkgCache::VerIterator Ver, Reason reason, Group group) pkgCache::DepIterator end; dep.GlobOr(start, end); // advances dep - if (not EnqueueOrGroup(start, end, Reason(Ver))) + if (not EnqueueOrGroup(start, end, Var(Ver))) return false; } return true; } -bool APT::Solver::Reject(pkgCache::PkgIterator Pkg, Reason reason, Group group) +bool APT::Solver::Reject(pkgCache::PkgIterator Pkg, Var reason, Group group) { if ((*this)[Pkg].decision == Decision::MUSTNOT) return true; @@ -418,17 +418,17 @@ bool APT::Solver::Reject(pkgCache::PkgIterator Pkg, Reason reason, Group group) // Check conflicting selections for (auto ver = Pkg.VersionList(); not ver.end(); ver++) if ((*this)[ver].decision == Decision::MUST) - return _error->Error("Conflict: %s -> not %s but %s", WhyStr(reason).c_str(), Pkg.FullName().c_str(), WhyStr(Reason(ver)).c_str()); + return _error->Error("Conflict: %s -> not %s but %s", WhyStr(reason).c_str(), Pkg.FullName().c_str(), WhyStr(Var(ver)).c_str()); if ((*this)[Pkg].decision == Decision::MUST) - return _error->Error("Conflict: %s -> not %s but %s", WhyStr(reason).c_str(), Pkg.FullName().c_str(), WhyStr(Reason(Pkg)).c_str()); + return _error->Error("Conflict: %s -> not %s but %s", WhyStr(reason).c_str(), Pkg.FullName().c_str(), WhyStr(Var(Pkg)).c_str()); // Reject the package and its versions. if (unlikely(debug >= 1)) std::cerr << "[" << depth() << "] Reject:" << Pkg.FullName() << " (" << WhyStr(reason) << ")\n"; (*this)[Pkg] = {reason, depth(), Decision::MUSTNOT}; - solved.push_back(Solved{Reason(Pkg), std::nullopt}); + solved.push_back(Solved{Var(Pkg), std::nullopt}); for (auto ver = Pkg.VersionList(); not ver.end(); ver++) - if (not Reject(ver, Reason(Pkg), group)) + if (not Reject(ver, Var(Pkg), group)) return false; needsRescore = true; @@ -437,7 +437,7 @@ bool APT::Solver::Reject(pkgCache::PkgIterator Pkg, Reason reason, Group group) } // \brief Do not install this version -bool APT::Solver::Reject(pkgCache::VerIterator Ver, Reason reason, Group group) +bool APT::Solver::Reject(pkgCache::VerIterator Ver, Var reason, Group group) { (void)group; @@ -449,13 +449,13 @@ bool APT::Solver::Reject(pkgCache::VerIterator Ver, Reason reason, Group group) return _error->Error("Conflict: %s -> not %s but %s", WhyStr(reason).c_str(), (Ver.ParentPkg().FullName() + "=" + Ver.VerStr()).c_str(), - WhyStr(Reason(Ver)).c_str()); + WhyStr(Var(Ver)).c_str()); // Mark the package as rejected and propagate up as needed. if (unlikely(debug >= 1)) std::cerr << "[" << depth() << "] Reject:" << Ver.ParentPkg().FullName() << "=" << Ver.VerStr() << " (" << WhyStr(reason) << ")\n"; (*this)[Ver] = {reason, depth(), Decision::MUSTNOT}; - solved.push_back(Solved{Reason(Ver), std::nullopt}); + solved.push_back(Solved{Var(Ver), std::nullopt}); if (auto pkg = Ver.ParentPkg(); (*this)[pkg].decision != Decision::MUSTNOT) { bool anyInstallable = false; @@ -468,18 +468,18 @@ bool APT::Solver::Reject(pkgCache::VerIterator Ver, Reason reason, Group group) else if ((*this)[pkg].decision == Decision::MUST) // Must install, but none available { _error->Error("Conflict: %s but no versions are installable", - WhyStr(Reason(pkg)).c_str()); + WhyStr(Var(pkg)).c_str()); for (auto otherVer = pkg.VersionList(); not otherVer.end(); otherVer++) if ((*this)[otherVer].decision == Decision::MUSTNOT) - _error->Error("Uninstallable version: %s", WhyStr(Reason(otherVer)).c_str()); + _error->Error("Uninstallable version: %s", WhyStr(Var(otherVer)).c_str()); return _error->Error("Uninstallable version: %s -> not %s", WhyStr(reason).c_str(), (Ver.ParentPkg().FullName() + "=" + Ver.VerStr()).c_str()); } else if ((*this)[Ver.ParentPkg()].decision != Decision::MUSTNOT) // Last installable invalidated { - (*this)[Ver.ParentPkg()] = {Reason(Ver), depth(), Decision::MUSTNOT}; - solved.push_back(Solved{Reason(Ver), std::nullopt}); + (*this)[Ver.ParentPkg()] = {Var(Ver), depth(), Decision::MUSTNOT}; + solved.push_back(Solved{Var(Ver), std::nullopt}); } } @@ -512,14 +512,14 @@ bool APT::Solver::EnqueueCommonDependencies(pkgCache::PkgIterator Pkg) } if (not allHaveDep) continue; - if (not EnqueueOrGroup(start, end, Reason(Pkg))) + if (not EnqueueOrGroup(start, end, Var(Pkg))) return false; } return true; } -bool APT::Solver::EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepIterator end, Reason reason) +bool APT::Solver::EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepIterator end, Var reason) { auto TgtPkg = start.TargetPkg(); auto Ver = start.ParentVer(); @@ -551,7 +551,7 @@ bool APT::Solver::EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepItera if (unlikely(debug >= 3)) std::cerr << "Reject: " << Ver.ParentPkg().FullName() << "=" << Ver.VerStr() << " -> " << tgti.ParentPkg().FullName() << "=" << tgti.VerStr() << "\n"; // FIXME: We should be collecting these and marking the heap only once. - if (not Reject(pkgCache::VerIterator(cache, *tgt), Reason(Ver), Group::HoldOrDelete)) + if (not Reject(pkgCache::VerIterator(cache, *tgt), Var(Ver), Group::HoldOrDelete)) return false; } else @@ -713,7 +713,7 @@ bool APT::Solver::RejectReverseDependencies(pkgCache::VerIterator Ver) if (unlikely(debug >= 3)) std::cerr << "Propagate NOT " << Ver.ParentPkg().FullName() << "=" << Ver.VerStr() << " to " << RDV.ParentPkg().FullName() << "=" << RDV.VerStr() << " for dependency group starting with" << start.TargetPkg().FullName() << std::endl; - if (not Reject(RDV, Reason(Ver), Group::HoldOrDelete)) + if (not Reject(RDV, Var(Ver), Group::HoldOrDelete)) return false; } return true; @@ -740,7 +740,7 @@ void APT::Solver::Push(Work work) } choices.push_back(solved.size()); - solved.push_back(Solved{Reason(), std::move(work)}); + solved.push_back(Solved{Var(), std::move(work)}); // Pop() will call MergeWithStack() when reverting to level 0, or RevertToStack after dumping to the debug log. _error->PushToStack(); } @@ -763,7 +763,7 @@ void APT::Solver::UndoOne() } auto &state = (*this)[solvedItem.assigned]; state.decision = Decision::NONE; - state.reason = Reason(); + state.reason = Var(); state.depth = 0; } @@ -894,7 +894,7 @@ bool APT::Solver::Solve() auto item = std::move(work.back()); work.pop_back(); - solved.push_back(Solved{Reason(), item}); + solved.push_back(Solved{Var(), item}); if (std::any_of(item.solutions.begin(), item.solutions.end(), [this](auto ver) { return (*this)[ver].decision == Decision::MUST; })) @@ -949,7 +949,7 @@ bool APT::Solver::Solve() if ((*this)[sol].decision == Decision::MUSTNOT) _error->Error("Not considered: %s=%s: %s", pkgCache::VerIterator(cache, sol).ParentPkg().FullName().c_str(), pkgCache::VerIterator(cache, sol).VerStr(), - WhyStr(Reason(pkgCache::VerIterator(cache, sol))).c_str()); + WhyStr(Var(pkgCache::VerIterator(cache, sol))).c_str()); if (not Pop()) return false; } @@ -1016,7 +1016,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache) } else { - Work w{Reason(), depth(), Group, isOptional, Upgrade}; + Work w{Var(), depth(), Group, isOptional, Upgrade}; for (auto V = P.VersionList(); not V.end(); ++V) if (IsAllowedVersion(V)) w.solutions.push_back(V); diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h index eb8d246bf..b0ced904a 100644 --- a/apt-pkg/solver3.h +++ b/apt-pkg/solver3.h @@ -32,7 +32,7 @@ class Solver { enum class Decision : uint16_t; enum class Hint : uint16_t; - struct Reason; + struct Var; struct CompareProviders3; struct State; struct Work; @@ -105,7 +105,7 @@ class Solver return verStates[V->ID]; } // \brief Helper function for safe access to either state. - inline State &operator[](Reason r); + inline State &operator[](Var r); mutable std::vector pkgObsolete; bool Obsolete(pkgCache::PkgIterator pkg) const; @@ -151,7 +151,7 @@ class Solver // \brief Reject reverse dependencies. Must call std::make_heap() after. bool RejectReverseDependencies(pkgCache::VerIterator Ver); // \brief Enqueue a single or group - bool EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepIterator end, Reason reason); + bool EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepIterator end, Var reason); // \brief Check if a version is allowed by policy. bool IsAllowedVersion(pkgCache::Version *V); @@ -177,13 +177,13 @@ class Solver Solver(pkgCache &Cache, pkgDepCache::Policy &Policy); // \brief Mark the package for install. This is annoying as it incurs a decision - bool Install(pkgCache::PkgIterator Pkg, Reason reason, Group group); + bool Install(pkgCache::PkgIterator Pkg, Var reason, Group group); // \brief Install a version. - bool Install(pkgCache::VerIterator Ver, Reason reason, Group group); + bool Install(pkgCache::VerIterator Ver, Var reason, Group group); // \brief Do not install this package - bool Reject(pkgCache::PkgIterator Pkg, Reason reason, Group group); + bool Reject(pkgCache::PkgIterator Pkg, Var reason, Group group); // \brief Do not install this version. - bool Reject(pkgCache::VerIterator Ver, Reason reason, Group group); + bool Reject(pkgCache::VerIterator Ver, Var reason, Group group); // \brief Apply the selections from the dep cache to the solver bool FromDepCache(pkgDepCache &depcache); @@ -194,7 +194,7 @@ class Solver bool Solve(); // Print dependency chain - std::string WhyStr(Reason reason); + std::string WhyStr(Var reason); }; }; // namespace APT @@ -203,18 +203,18 @@ class Solver * \brief Tagged union holding either a package, version, or nothing; representing the reason for installing something. * * We want to keep track of the reason why things are being installed such that - * we can have sensible debugging abilities. + * we can have sensible debugging abilities; and we want to generically refer to + * both packages and versions as variables, hence this class was added. * - * If the reason is empty, this means the package is automatically installed. */ -struct APT::Solver::Reason +struct APT::Solver::Var { uint32_t IsVersion : 1; uint32_t MapPtr : 31; - Reason() : IsVersion(0), MapPtr(0) {} - explicit Reason(pkgCache::PkgIterator const &Pkg) : IsVersion(0), MapPtr(Pkg.MapPointer()) {} - explicit Reason(pkgCache::VerIterator const &Ver) : IsVersion(1), MapPtr(Ver.MapPointer()) {} + Var() : IsVersion(0), MapPtr(0) {} + explicit Var(pkgCache::PkgIterator const &Pkg) : IsVersion(0), MapPtr(Pkg.MapPointer()) {} + explicit Var(pkgCache::VerIterator const &Ver) : IsVersion(1), MapPtr(Ver.MapPointer()) {} // \brief Return the package, if any, otherwise 0. map_pointer Pkg() const @@ -255,8 +255,8 @@ struct APT::Solver::Reason */ struct APT::Solver::Work { - // \brief Reason for the work - Reason reason; + // \brief Var for the work + Var reason; // \brief The depth at which the item has been added depth_type depth; // \brief The group we are in @@ -285,7 +285,7 @@ struct APT::Solver::Work // \brief Dump the work item to std::cerr void Dump(pkgCache &cache); - inline Work(Reason reason, depth_type depth, Group group, bool optional = false, bool upgrade = false) : reason(reason), depth(depth), group(group), size(0), optional(optional), upgrade(upgrade), dirty(false) {} + 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), dirty(false) {} }; // \brief This essentially describes the install state in RFC2119 terms. @@ -328,8 +328,8 @@ struct APT::Solver::State // You can follow the reason chain upwards as long as the depth // doesn't increase to unwind. // - // Reasons < 0 are package ID, reasons > 0 are version IDs. - Reason reason{}; + // Vars < 0 are package ID, reasons > 0 are version IDs. + Var reason{}; // \brief The depth at which the decision has been taken depth_type depth{0}; @@ -349,13 +349,13 @@ struct APT::Solver::State */ struct APT::Solver::Solved { - // \brief A variable that has been assigned. We store this as a reason (FIXME: Rename Reason to Var) - Reason assigned; + // \brief A variable that has been assigned. We store this as a reason (FIXME: Rename Var to Var) + Var assigned; // \brief A work item that has been solved. This needs to be put back on the queue. std::optional work; }; -inline APT::Solver::State &APT::Solver::operator[](Reason r) +inline APT::Solver::State &APT::Solver::operator[](Var r) { if (auto P = r.Pkg()) return (*this)[cache.PkgP + P]; -- cgit v1.2.3-70-g09d2 From c1f69a64fd5070723ef425cc1255cde2a28966ad Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Thu, 1 Aug 2024 15:51:37 +0900 Subject: solver3: Introduce new Assume() and Enqueue() helpers and use them These are taken roughly from the MiniSAT paper. We still have a bit to go in actually encoding all clauses so the reasons are still variables, and Assume() isn't fully working yet. Adjust the existing Install()/Reject() code to use these functions, we already see additional lines in the log that we failed to log before, and this ensures more consistency. This is sort of still the wrong direction: Install()/Reject() do the propagation too; but that is tbd. --- apt-pkg/solver3.cc | 64 ++++++++++++++-------- apt-pkg/solver3.h | 14 +++++ ...est-bug-549968-install-depends-of-not-installed | 1 + .../integration/test-bug-604222-new-and-autoremove | 4 ++ ...960705-propagate-protected-to-satisfied-depends | 7 +++ .../integration/test-dpkg-i-apt-install-fix-broken | 2 + 6 files changed, 69 insertions(+), 23 deletions(-) diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index 5065b9a87..a21af12f9 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -304,6 +304,35 @@ bool APT::Solver::Obsolete(pkgCache::PkgIterator pkg) const pkgObsolete[pkg->ID] = 2; return true; } +bool APT::Solver::Assume(Var var, bool decision, Var reason) +{ + choices.push_back(solved.size()); + return Enqueue(var, decision, std::move(reason)); +} + +bool APT::Solver::Enqueue(Var var, bool decision, Var reason) +{ + auto &state = (*this)[var]; + auto decisionCast = decision ? Decision::MUST : Decision::MUSTNOT; + + if (state.decision != Decision::NONE) + { + if (state.decision != decisionCast) + return _error->Error("Conflict: %s -> %s%s but %s", WhyStr(reason).c_str(), decision ? "" : "not ", var.toString(cache).c_str(), WhyStr(var).c_str()); + return true; + } + + state.decision = decisionCast; + state.depth = depth(); + state.reason = reason; + + if (unlikely(debug >= 1)) + std::cerr << "[" << depth() << "] " << (decision ? "Install" : "Reject") << ":" << var.toString(cache) << " (" << WhyStr(state.reason) << ")\n"; + + solved.push_back(Solved{var, std::nullopt}); + + return true; +} bool APT::Solver::Install(pkgCache::PkgIterator Pkg, Var reason, Group group) { @@ -329,10 +358,8 @@ bool APT::Solver::Install(pkgCache::PkgIterator Pkg, Var reason, Group group) } // Note decision - if (unlikely(debug >= 1)) - std::cerr << "[" << depth() << "] Install:" << Pkg.FullName() << " (" << WhyStr(reason) << ")\n"; - (*this)[Pkg] = {reason, depth(), Decision::MUST}; - solved.push_back(Solved{Var(Pkg), std::nullopt}); + if (not Enqueue(Var(Pkg), true, reason)) + return false; // Insert the work item. Work workItem{Var(Pkg), depth(), group}; @@ -380,15 +407,10 @@ bool APT::Solver::Install(pkgCache::VerIterator Ver, Var reason, Group group) WhyStr(Var(otherVer)).c_str()); // Note decision - if (unlikely(debug >= 1)) - std::cerr << "[" << depth() << "] Install:" << Ver.ParentPkg().FullName() << "=" << Ver.VerStr() << " (" << WhyStr(reason) << ")\n"; - (*this)[Ver] = {reason, depth(), Decision::MUST}; - solved.push_back(Solved{Var(Ver), std::nullopt}); - if ((*this)[Ver.ParentPkg()].decision != Decision::MUST) - { - (*this)[Ver.ParentPkg()] = {Var(Ver), depth(), Decision::MUST}; - solved.push_back(Solved{Var(Ver.ParentPkg()), std::nullopt}); - } + if (not Enqueue(Var(Ver), true, reason)) + return false; + if (not Enqueue(Var(Ver.ParentPkg()), true, Var(Ver))) + return false; for (auto OV = Ver.ParentPkg().VersionList(); not OV.end(); ++OV) { @@ -423,10 +445,8 @@ bool APT::Solver::Reject(pkgCache::PkgIterator Pkg, Var reason, Group group) return _error->Error("Conflict: %s -> not %s but %s", WhyStr(reason).c_str(), Pkg.FullName().c_str(), WhyStr(Var(Pkg)).c_str()); // Reject the package and its versions. - if (unlikely(debug >= 1)) - std::cerr << "[" << depth() << "] Reject:" << Pkg.FullName() << " (" << WhyStr(reason) << ")\n"; - (*this)[Pkg] = {reason, depth(), Decision::MUSTNOT}; - solved.push_back(Solved{Var(Pkg), std::nullopt}); + if (not Enqueue(Var(Pkg), false, reason)) + return false; for (auto ver = Pkg.VersionList(); not ver.end(); ver++) if (not Reject(ver, Var(Pkg), group)) return false; @@ -452,10 +472,8 @@ bool APT::Solver::Reject(pkgCache::VerIterator Ver, Var reason, Group group) WhyStr(Var(Ver)).c_str()); // Mark the package as rejected and propagate up as needed. - if (unlikely(debug >= 1)) - std::cerr << "[" << depth() << "] Reject:" << Ver.ParentPkg().FullName() << "=" << Ver.VerStr() << " (" << WhyStr(reason) << ")\n"; - (*this)[Ver] = {reason, depth(), Decision::MUSTNOT}; - solved.push_back(Solved{Var(Ver), std::nullopt}); + if (not Enqueue(Var(Ver), false, reason)) + return false; if (auto pkg = Ver.ParentPkg(); (*this)[pkg].decision != Decision::MUSTNOT) { bool anyInstallable = false; @@ -478,8 +496,8 @@ bool APT::Solver::Reject(pkgCache::VerIterator Ver, Var reason, Group group) } else if ((*this)[Ver.ParentPkg()].decision != Decision::MUSTNOT) // Last installable invalidated { - (*this)[Ver.ParentPkg()] = {Var(Ver), depth(), Decision::MUSTNOT}; - solved.push_back(Solved{Var(Ver), std::nullopt}); + if (not Enqueue(Var(Ver.ParentPkg()), false, Var(Ver))) + return false; } } diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h index b0ced904a..527e6fc22 100644 --- a/apt-pkg/solver3.h +++ b/apt-pkg/solver3.h @@ -176,6 +176,11 @@ class Solver // \brief Basic solver initializer. This cannot fail. Solver(pkgCache &Cache, pkgDepCache::Policy &Policy); + // Assume that the variable is decided as specified. + bool Assume(Var var, bool decision, Var reason); + // Enqueue a decision fact + bool Enqueue(Var var, bool decision, Var reason); + // \brief Mark the package for install. This is annoying as it incurs a decision bool Install(pkgCache::PkgIterator Pkg, Var reason, Group group); // \brief Install a version. @@ -241,6 +246,15 @@ struct APT::Solver::Var { return IsVersion == 0 && MapPtr == 0; } + + std::string toString(pkgCache &cache) const + { + if (auto P = Pkg(cache); not P.end()) + return P.FullName(); + if (auto V = Ver(cache); not V.end()) + return V.ParentPkg().FullName() + "=" + V.VerStr(); + return "(root)"; + } }; /** 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 f575f9940..76219290a 100755 --- a/test/integration/test-bug-549968-install-depends-of-not-installed +++ b/test/integration/test-bug-549968-install-depends-of-not-installed @@ -34,6 +34,7 @@ Building dependency tree... Package 'extracoolstuff' is not installed, so not removed Solving dependencies...Install coolstuff:i386 () [0] Install:coolstuff:i386=1.0 () +[0] Install:coolstuff:i386 (coolstuff:i386=1.0) Delete extracoolstuff:i386 [0] Reject:extracoolstuff:i386 () [0] Reject:extracoolstuff:i386=1.0 (not extracoolstuff:i386) diff --git a/test/integration/test-bug-604222-new-and-autoremove b/test/integration/test-bug-604222-new-and-autoremove index a53fcb76b..1090e8b93 100755 --- a/test/integration/test-bug-604222-new-and-autoremove +++ b/test/integration/test-bug-604222-new-and-autoremove @@ -98,10 +98,14 @@ CONFLICTING='Reading package lists... Building dependency tree... Solving dependencies...MANUAL dummy-archive:i386 [0] Install:dummy-archive:i386=0.invalid.0 () +[0] Install:dummy-archive:i386 (dummy-archive:i386=0.invalid.0) [0] Install:libavcodec52:i386=4:0.5.2-6 (dummy-archive:i386=0.invalid.0) +[0] Install:libavcodec52:i386 (dummy-archive:i386=0.invalid.0 -> libavcodec52:i386=4:0.5.2-6) [0] Reject:libvtk5-dev:i386=5.4.2-8 (dummy-archive:i386=0.invalid.0 -> libavcodec52:i386=4:0.5.2-6) +[0] Reject:libvtk5-dev:i386 (dummy-archive:i386=0.invalid.0 -> libavcodec52:i386=4:0.5.2-6 -> not libvtk5-dev:i386=5.4.2-8) Item (1@0) dummy-archive:i386=0.invalid.0 -> | libvtk5-dev:i386=5.4.2-8 | libopenal-dev:i386=1:1.12.854-2 [0] Install:libopenal-dev:i386=1:1.12.854-2 (dummy-archive:i386=0.invalid.0) +[0] Install:libopenal-dev:i386 (dummy-archive:i386=0.invalid.0 -> libopenal-dev:i386=1:1.12.854-2) The following additional packages will be installed: libavcodec52 libopenal-dev diff --git a/test/integration/test-bug-960705-propagate-protected-to-satisfied-depends b/test/integration/test-bug-960705-propagate-protected-to-satisfied-depends index 6ffb69bf5..e5a12986d 100755 --- a/test/integration/test-bug-960705-propagate-protected-to-satisfied-depends +++ b/test/integration/test-bug-960705-propagate-protected-to-satisfied-depends @@ -22,14 +22,21 @@ testsuccessequal "Reading package lists... Building dependency tree... Solving dependencies...Install foobar:amd64 () [0] Install:foobar:amd64=1 () +[0] Install:foobar:amd64 (foobar:amd64=1) [0] Install:requires-foo:amd64=1 (foobar:amd64=1) +[0] Install:requires-foo:amd64 (foobar:amd64=1 -> requires-foo:amd64=1) [0] Install:foo:amd64=1 (foobar:amd64=1 -> requires-foo:amd64=1) +[0] Install:foo:amd64 (foobar:amd64=1 -> requires-foo:amd64=1 -> foo:amd64=1) [0] Install:foo-depends:amd64=1 (foobar:amd64=1 -> requires-foo:amd64=1 -> foo:amd64=1) +[0] Install:foo-depends:amd64 (foobar:amd64=1 -> requires-foo:amd64=1 -> foo:amd64=1 -> foo-depends:amd64=1) Item (2@0) foobar:amd64=1 -> | conflicts-foo:amd64=1 | fine-foo:amd64=1 [1] Install:conflicts-foo:amd64=1 (foobar:amd64=1) +[1] Install:conflicts-foo:amd64 (foobar:amd64=1 -> conflicts-foo:amd64=1) [0] Reject:conflicts-foo:amd64=1 () +[0] Reject:conflicts-foo:amd64 (not conflicts-foo:amd64=1) Item (1@0) foobar:amd64=1 -> | conflicts-foo:amd64=1 | fine-foo:amd64=1 [0] Install:fine-foo:amd64=1 (foobar:amd64=1) +[0] Install:fine-foo:amd64 (foobar:amd64=1 -> fine-foo:amd64=1) The following additional packages will be installed: fine-foo foo foo-depends requires-foo diff --git a/test/integration/test-dpkg-i-apt-install-fix-broken b/test/integration/test-dpkg-i-apt-install-fix-broken index a4c3c66d9..21d8e298e 100755 --- a/test/integration/test-dpkg-i-apt-install-fix-broken +++ b/test/integration/test-dpkg-i-apt-install-fix-broken @@ -18,12 +18,14 @@ Correcting dependencies...Install autopkgtest-satdep:amd64 () [0] Install:autopkgtest-satdep:amd64 () [0] Install:autopkgtest-satdep:amd64=1 (autopkgtest-satdep:amd64) [0] Install:debhelper:amd64=1 (autopkgtest-satdep:amd64 -> autopkgtest-satdep:amd64=1) +[0] Install:debhelper:amd64 (autopkgtest-satdep:amd64 -> autopkgtest-satdep:amd64=1 -> debhelper:amd64=1) Done Solving dependencies...Install debhelper:amd64 (M) Install autopkgtest-satdep:amd64 () [0] Install:autopkgtest-satdep:amd64 () [0] Install:autopkgtest-satdep:amd64=1 (autopkgtest-satdep:amd64) [0] Install:debhelper:amd64=1 (autopkgtest-satdep:amd64 -> autopkgtest-satdep:amd64=1) +[0] Install:debhelper:amd64 (autopkgtest-satdep:amd64 -> autopkgtest-satdep:amd64=1 -> debhelper:amd64=1) The following additional packages will be installed: debhelper -- cgit v1.2.3-70-g09d2 From b4f43e48994bec07a9b5aa38d21e3fd350912d16 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Thu, 1 Aug 2024 16:03:15 +0900 Subject: solver3: Remove obsolete checks These checks are no longer needed since Enqueue() ensures the correctness for us. --- apt-pkg/solver3.cc | 49 +++++-------------------------------------------- 1 file changed, 5 insertions(+), 44 deletions(-) diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index a21af12f9..c04deadb3 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -339,9 +339,9 @@ bool APT::Solver::Install(pkgCache::PkgIterator Pkg, Var reason, Group group) if ((*this)[Pkg].decision == Decision::MUST) return true; - // Check conflicting selections - if ((*this)[Pkg].decision == Decision::MUSTNOT) - return _error->Error("Conflict: %s -> %s but %s", WhyStr(reason).c_str(), Pkg.FullName().c_str(), WhyStr(Var(Pkg)).c_str()); + // Note decision + if (not Enqueue(Var(Pkg), true, reason)) + return false; bool anyInstallable = false; for (auto ver = Pkg.VersionList(); not ver.end(); ver++) @@ -357,10 +357,6 @@ bool APT::Solver::Install(pkgCache::PkgIterator Pkg, Var reason, Group group) return false; } - // Note decision - if (not Enqueue(Var(Pkg), true, reason)) - return false; - // Insert the work item. Work workItem{Var(Pkg), depth(), group}; for (auto ver = Pkg.VersionList(); not ver.end(); ver++) @@ -388,24 +384,6 @@ bool APT::Solver::Install(pkgCache::VerIterator Ver, Var reason, Group group) if (unlikely(debug >= 1)) assert(IsAllowedVersion(Ver)); - // Check conflicting selections - if ((*this)[Ver].decision == Decision::MUSTNOT) - return _error->Error("Conflict: %s -> %s but %s", - WhyStr(reason).c_str(), - (Ver.ParentPkg().FullName() + "=" + Ver.VerStr()).c_str(), - WhyStr(Var(Ver)).c_str()); - if ((*this)[Ver.ParentPkg()].decision == Decision::MUSTNOT) - return _error->Error("Conflict: %s -> %s but %s", - WhyStr(reason).c_str(), - (Ver.ParentPkg().FullName() + "=" + Ver.VerStr()).c_str(), - WhyStr(Var(Ver.ParentPkg())).c_str()); - for (auto otherVer = Ver.ParentPkg().VersionList(); not otherVer.end(); otherVer++) - if (otherVer->ID != Ver->ID && (*this)[otherVer].decision == Decision::MUST) - return _error->Error("Conflict: %s -> %s but %s", - WhyStr(reason).c_str(), - (Ver.ParentPkg().FullName() + "=" + Ver.VerStr()).c_str(), - WhyStr(Var(otherVer)).c_str()); - // Note decision if (not Enqueue(Var(Ver), true, reason)) return false; @@ -437,13 +415,6 @@ bool APT::Solver::Reject(pkgCache::PkgIterator Pkg, Var reason, Group group) if ((*this)[Pkg].decision == Decision::MUSTNOT) return true; - // Check conflicting selections - for (auto ver = Pkg.VersionList(); not ver.end(); ver++) - if ((*this)[ver].decision == Decision::MUST) - return _error->Error("Conflict: %s -> not %s but %s", WhyStr(reason).c_str(), Pkg.FullName().c_str(), WhyStr(Var(ver)).c_str()); - if ((*this)[Pkg].decision == Decision::MUST) - return _error->Error("Conflict: %s -> not %s but %s", WhyStr(reason).c_str(), Pkg.FullName().c_str(), WhyStr(Var(Pkg)).c_str()); - // Reject the package and its versions. if (not Enqueue(Var(Pkg), false, reason)) return false; @@ -464,13 +435,6 @@ bool APT::Solver::Reject(pkgCache::VerIterator Ver, Var reason, Group group) if ((*this)[Ver].decision == Decision::MUSTNOT) return true; - // Check conflicting choices. - if ((*this)[Ver].decision == Decision::MUST) - return _error->Error("Conflict: %s -> not %s but %s", - WhyStr(reason).c_str(), - (Ver.ParentPkg().FullName() + "=" + Ver.VerStr()).c_str(), - WhyStr(Var(Ver)).c_str()); - // Mark the package as rejected and propagate up as needed. if (not Enqueue(Var(Ver), false, reason)) return false; @@ -494,11 +458,8 @@ bool APT::Solver::Reject(pkgCache::VerIterator Ver, Var reason, Group group) WhyStr(reason).c_str(), (Ver.ParentPkg().FullName() + "=" + Ver.VerStr()).c_str()); } - else if ((*this)[Ver.ParentPkg()].decision != Decision::MUSTNOT) // Last installable invalidated - { - if (not Enqueue(Var(Ver.ParentPkg()), false, Var(Ver))) - return false; - } + else if (not Enqueue(Var(Ver.ParentPkg()), false, Var(Ver))) // Last version invalidated + return false; } if (not RejectReverseDependencies(Ver)) -- cgit v1.2.3-70-g09d2 From 835fd787c24c496516965eb59fef81cbd1e304cc Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Thu, 1 Aug 2024 16:08:13 +0900 Subject: solver3: Move needsRescore from Reject to Enqueue() --- apt-pkg/solver3.cc | 7 +++---- 1 file changed, 3 insertions(+), 4 deletions(-) diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index c04deadb3..ba0dd949a 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -331,6 +331,9 @@ bool APT::Solver::Enqueue(Var var, bool decision, Var reason) solved.push_back(Solved{var, std::nullopt}); + if (not decision) + needsRescore = true; + return true; } @@ -422,8 +425,6 @@ bool APT::Solver::Reject(pkgCache::PkgIterator Pkg, Var reason, Group group) if (not Reject(ver, Var(Pkg), group)) return false; - needsRescore = true; - return true; } @@ -465,8 +466,6 @@ bool APT::Solver::Reject(pkgCache::VerIterator Ver, Var reason, Group group) if (not RejectReverseDependencies(Ver)) return false; - needsRescore = true; - return true; } -- cgit v1.2.3-70-g09d2 From cab40edc4040691fcadbddbdee77decf4bf20573 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Thu, 1 Aug 2024 16:57:28 +0900 Subject: solver3: Remove the Reject() function, propagate in Enqueue() instead Long term we should have a propagate queue, this is the minimal change to keep the behavior identical, a first step on the road. --- apt-pkg/solver3.cc | 89 +++++++++++++++++++++++------------------------------- apt-pkg/solver3.h | 7 ++--- 2 files changed, 40 insertions(+), 56 deletions(-) diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index ba0dd949a..c48077c81 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -332,7 +332,11 @@ bool APT::Solver::Enqueue(Var var, bool decision, Var reason) solved.push_back(Solved{var, std::nullopt}); if (not decision) + { + if (not PropagateReject(var)) + return false; needsRescore = true; + } return true; } @@ -395,7 +399,7 @@ bool APT::Solver::Install(pkgCache::VerIterator Ver, Var reason, Group group) for (auto OV = Ver.ParentPkg().VersionList(); not OV.end(); ++OV) { - if (OV != Ver && not Reject(OV, Var(Ver), group)) + if (OV != Ver && not Enqueue(Var(OV), false, Var(Ver))) return false; } @@ -413,59 +417,40 @@ bool APT::Solver::Install(pkgCache::VerIterator Ver, Var reason, Group group) return true; } -bool APT::Solver::Reject(pkgCache::PkgIterator Pkg, Var reason, Group group) -{ - if ((*this)[Pkg].decision == Decision::MUSTNOT) - return true; - - // Reject the package and its versions. - if (not Enqueue(Var(Pkg), false, reason)) - return false; - for (auto ver = Pkg.VersionList(); not ver.end(); ver++) - if (not Reject(ver, Var(Pkg), group)) - return false; - - return true; -} - -// \brief Do not install this version -bool APT::Solver::Reject(pkgCache::VerIterator Ver, Var reason, Group group) +bool APT::Solver::PropagateReject(Var var) { - (void)group; - - if ((*this)[Ver].decision == Decision::MUSTNOT) - return true; - - // Mark the package as rejected and propagate up as needed. - if (not Enqueue(Var(Ver), false, reason)) - return false; - if (auto pkg = Ver.ParentPkg(); (*this)[pkg].decision != Decision::MUSTNOT) + if (auto Pkg = var.Pkg(cache); not Pkg.end()) + { + for (auto ver = Pkg.VersionList(); not ver.end(); ver++) + if (not Enqueue(Var(ver), false, Var(Pkg))) + return false; + } + else if (auto Ver = var.Ver(cache); not Ver.end()) { - bool anyInstallable = false; - for (auto otherVer = pkg.VersionList(); not otherVer.end(); otherVer++) - if (otherVer->ID != Ver->ID && (*this)[otherVer].decision != Decision::MUSTNOT) - anyInstallable = true; - - if (anyInstallable) - ; - else if ((*this)[pkg].decision == Decision::MUST) // Must install, but none available + if (auto pkg = Ver.ParentPkg(); (*this)[pkg].decision != Decision::MUSTNOT) { - _error->Error("Conflict: %s but no versions are installable", - WhyStr(Var(pkg)).c_str()); + bool anyInstallable = false; for (auto otherVer = pkg.VersionList(); not otherVer.end(); otherVer++) - if ((*this)[otherVer].decision == Decision::MUSTNOT) - _error->Error("Uninstallable version: %s", WhyStr(Var(otherVer)).c_str()); - return _error->Error("Uninstallable version: %s -> not %s", - WhyStr(reason).c_str(), - (Ver.ParentPkg().FullName() + "=" + Ver.VerStr()).c_str()); + if (otherVer->ID != Ver->ID && (*this)[otherVer].decision != Decision::MUSTNOT) + anyInstallable = true; + + if (anyInstallable) + ; + else if ((*this)[pkg].decision == Decision::MUST) // Must install, but none available + { + _error->Error("Conflict: %s but no versions are installable", + WhyStr(Var(pkg)).c_str()); + for (auto otherVer = pkg.VersionList(); not otherVer.end(); otherVer++) + if ((*this)[otherVer].decision == Decision::MUSTNOT) + _error->Error("Uninstallable version: %s", WhyStr(Var(otherVer)).c_str()); + return _error->Error("Uninstallable version: %s", WhyStr(Var(Ver)).c_str()); + } + else if (not Enqueue(Var(Ver.ParentPkg()), false, Var(Ver))) // Last version invalidated + return false; } - else if (not Enqueue(Var(Ver.ParentPkg()), false, Var(Ver))) // Last version invalidated + if (not RejectReverseDependencies(Ver)) return false; } - - if (not RejectReverseDependencies(Ver)) - return false; - return true; } @@ -529,7 +514,7 @@ bool APT::Solver::EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepItera if (unlikely(debug >= 3)) std::cerr << "Reject: " << Ver.ParentPkg().FullName() << "=" << Ver.VerStr() << " -> " << tgti.ParentPkg().FullName() << "=" << tgti.VerStr() << "\n"; // FIXME: We should be collecting these and marking the heap only once. - if (not Reject(pkgCache::VerIterator(cache, *tgt), Var(Ver), Group::HoldOrDelete)) + if (not Enqueue(Var(pkgCache::VerIterator(cache, *tgt)), false, Var(Ver))) return false; } else @@ -691,7 +676,7 @@ bool APT::Solver::RejectReverseDependencies(pkgCache::VerIterator Ver) if (unlikely(debug >= 3)) std::cerr << "Propagate NOT " << Ver.ParentPkg().FullName() << "=" << Ver.VerStr() << " to " << RDV.ParentPkg().FullName() << "=" << RDV.VerStr() << " for dependency group starting with" << start.TargetPkg().FullName() << std::endl; - if (not Reject(RDV, Var(Ver), Group::HoldOrDelete)) + if (not Enqueue(Var(RDV), false, Var(Ver))) return false; } return true; @@ -791,7 +776,7 @@ bool APT::Solver::Pop() std::cerr << "Backtracking to choice " << choice.ParentPkg().FullName() << "=" << choice.VerStr() << "\n"; // FIXME: There should be a reason! - if (not Reject(choice, {}, Group::HoldOrDelete)) + if (not Enqueue(Var(choice), false, {})) return false; if (unlikely(debug >= 2)) @@ -952,7 +937,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache) { if (unlikely(debug >= 1)) std::cerr << "Hold " << P.FullName() << "\n"; - if (P->CurrentVer ? not Install(P.CurrentVer(), {}, Group::HoldOrDelete) : not Reject(P, {}, Group::HoldOrDelete)) + if (P->CurrentVer ? not Install(P.CurrentVer(), {}, Group::HoldOrDelete) : not Enqueue(Var(P), false, Var())) return false; } else if (state.Delete() // Normal delete request. @@ -962,7 +947,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache) { if (unlikely(debug >= 1)) std::cerr << "Delete " << P.FullName() << "\n"; - if (!Reject(P, {}, Group::HoldOrDelete)) + if (not Enqueue(Var(P), false, Var())) return false; } else if (state.Install() || (state.Keep() && P->CurrentVer)) diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h index 527e6fc22..7954f2f73 100644 --- a/apt-pkg/solver3.h +++ b/apt-pkg/solver3.h @@ -8,6 +8,7 @@ */ #include +#include #include #include @@ -152,6 +153,8 @@ class Solver bool RejectReverseDependencies(pkgCache::VerIterator Ver); // \brief Enqueue a single or group bool EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepIterator end, Var reason); + // \brief Propagate a rejection of a variable + bool PropagateReject(Var var); // \brief Check if a version is allowed by policy. bool IsAllowedVersion(pkgCache::Version *V); @@ -185,10 +188,6 @@ class Solver bool Install(pkgCache::PkgIterator Pkg, Var reason, Group group); // \brief Install a version. bool Install(pkgCache::VerIterator Ver, Var reason, Group group); - // \brief Do not install this package - bool Reject(pkgCache::PkgIterator Pkg, Var reason, Group group); - // \brief Do not install this version. - bool Reject(pkgCache::VerIterator Ver, Var reason, Group group); // \brief Apply the selections from the dep cache to the solver bool FromDepCache(pkgDepCache &depcache); -- cgit v1.2.3-70-g09d2 From 9d99322c14c44d73722bd580473abf67538b7c05 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Thu, 1 Aug 2024 17:08:42 +0900 Subject: solver3: Rename the 'dirty' bit to 'erased' This captures the meaning better --- apt-pkg/solver3.cc | 12 ++++++------ apt-pkg/solver3.h | 4 ++-- 2 files changed, 8 insertions(+), 8 deletions(-) diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index c48077c81..7aa0bd0b2 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -196,8 +196,8 @@ bool APT::Solver::Work::operator<(APT::Solver::Work const &b) const void APT::Solver::Work::Dump(pkgCache &cache) { - if (dirty) - std::cerr << "Dirty "; + if (erased) + std::cerr << "Erased "; if (optional) std::cerr << "Optional "; std::cerr << "Item (" << ssize_t(size <= solutions.size() ? size : -1) << "@" << depth << (upgrade ? "u" : "") << ") "; @@ -768,7 +768,7 @@ bool APT::Solver::Pop() // We need to remove any work that is at a higher depth. choices.pop_back(); work.erase(std::remove_if(work.begin(), work.end(), [this](Work &w) -> bool - { return w.depth > depth() || w.dirty; }), + { return w.depth > depth() || w.erased; }), work.end()); std::make_heap(work.begin(), work.end()); @@ -802,7 +802,7 @@ void APT::Solver::RescoreWorkIfNeeded() std::vector resized; for (auto &w : work) { - if (w.dirty) + if (w.erased) continue; size_t newSize = std::count_if(w.solutions.begin(), w.solutions.end(), [this](auto V) { return (*this)[V].decision != Decision::MUSTNOT; }); @@ -815,7 +815,7 @@ void APT::Solver::RescoreWorkIfNeeded() Work newWork(w); newWork.size = newSize; resized.push_back(std::move(newWork)); - w.dirty = true; + w.erased = true; } } if (unlikely(debug >= 2)) @@ -837,7 +837,7 @@ bool APT::Solver::Solve() std::pop_heap(work.begin(), work.end()); // This item has been replaced with a new one. Remove it. - if (work.back().dirty) + if (work.back().erased) { work.pop_back(); continue; diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h index 7954f2f73..de1bd1e73 100644 --- a/apt-pkg/solver3.h +++ b/apt-pkg/solver3.h @@ -292,13 +292,13 @@ struct APT::Solver::Work // \brief Whether this is an ugprade bool upgrade; // \brief This item should be removed from the queue. - bool dirty; + bool erased; 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, bool upgrade = false) : reason(reason), depth(depth), group(group), size(0), optional(optional), upgrade(upgrade), dirty(false) {} + 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) {} }; // \brief This essentially describes the install state in RFC2119 terms. -- cgit v1.2.3-70-g09d2 From 88cad6148797c399764333fbae3ade3036eb7dc3 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Tue, 13 Aug 2024 11:47:06 +0200 Subject: Add a FIXME around the heap compaction Our work heap is currently cleaned from deeper levels by removing the entries from the heap and then remaking the heap which is very inefficient. We should mark the items as erased instead, and only do the remove & make_heap dance if we have a lot of erased entries in there. Possibly we maybe should use a structure that actually allows removing entries, that is, an std::set, but that warrants more investigation on performance aspects. --- apt-pkg/solver3.cc | 2 ++ 1 file changed, 2 insertions(+) diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index 7aa0bd0b2..328c52f99 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -766,6 +766,8 @@ bool APT::Solver::Pop() UndoOne(); // We need to remove any work that is at a higher depth. + // FIXME: We should just mark the entries as erased and only do a compaction + // of the heap once we have a lot of erased entries in it. choices.pop_back(); work.erase(std::remove_if(work.begin(), work.end(), [this](Work &w) -> bool { return w.depth > depth() || w.erased; }), -- cgit v1.2.3-70-g09d2 From 6c98593d3e8c99c2c0dfaf18e571e567fc6b5837 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Sat, 2 Nov 2024 11:22:45 +0100 Subject: solver3: A version selected for install already is allowed. --- apt-pkg/solver3.cc | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index 328c52f99..c32a5db29 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -685,7 +685,7 @@ bool APT::Solver::RejectReverseDependencies(pkgCache::VerIterator Ver) bool APT::Solver::IsAllowedVersion(pkgCache::Version *V) { pkgCache::VerIterator ver(cache, V); - if (not StrictPinning || ver.ParentPkg().CurrentVer() == ver || policy.GetCandidateVer(ver.ParentPkg()) == ver) + if (not StrictPinning || ver.ParentPkg().CurrentVer() == ver || policy.GetCandidateVer(ver.ParentPkg()) == ver || (*this)[V].decision == Decision::MUST) return true; if (unlikely(debug >= 3)) -- cgit v1.2.3-70-g09d2 From d7dc72dd8b23f3fbedb32f8cacd9ba920d78ccc3 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Sat, 2 Nov 2024 11:44:36 +0100 Subject: solver3: Check whether installable versions are allowed We only checked if they were still installable, but not if they were allowed. We should removed the allowed version handling altogether presumably - we should just mark non-allowed versions as rejected early on. --- apt-pkg/solver3.cc | 17 ++++++++++------- 1 file changed, 10 insertions(+), 7 deletions(-) diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index c32a5db29..7f382646a 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -351,9 +351,17 @@ bool APT::Solver::Install(pkgCache::PkgIterator Pkg, Var reason, Group group) return false; bool anyInstallable = false; + // Insert the work item. + Work workItem{Var(Pkg), depth(), group}; for (auto ver = Pkg.VersionList(); not ver.end(); ver++) - if ((*this)[ver].decision != Decision::MUSTNOT) - anyInstallable = true; + { + if (IsAllowedVersion(ver)) + { + workItem.solutions.push_back(ver); + if ((*this)[ver].decision != Decision::MUSTNOT) + anyInstallable = true; + } + } if (not anyInstallable) { @@ -364,11 +372,6 @@ bool APT::Solver::Install(pkgCache::PkgIterator Pkg, Var reason, Group group) return false; } - // Insert the work item. - Work workItem{Var(Pkg), depth(), group}; - for (auto ver = Pkg.VersionList(); not ver.end(); ver++) - if (IsAllowedVersion(ver)) - workItem.solutions.push_back(ver); std::stable_sort(workItem.solutions.begin(), workItem.solutions.end(), CompareProviders3{cache, policy, Pkg, *this}); assert(workItem.solutions.size() > 0); -- cgit v1.2.3-70-g09d2 From 9f40a9a3251cc6b51bc50a5fe12c49a45a51aedd Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Sat, 2 Nov 2024 13:13:51 +0100 Subject: solver3: Refactor Install(Ver) to PropagateInstall(Ver) This is the first part of changing from Install() to Enqueue() for installs, affecting only the versions. For packages, we still have to resolve the group changing: When propagating cleanly, we don't have the information as to which group the package was part of, hence we are no longer able to queue the version selection of upgrades before obsolete packages, for example, which needs solving. --- apt-pkg/solver3.cc | 64 +++++++++++++++++++++++++++++------------------------- apt-pkg/solver3.h | 4 ++-- 2 files changed, 36 insertions(+), 32 deletions(-) diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index 7f382646a..4c1adef4b 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -322,6 +322,9 @@ bool APT::Solver::Enqueue(Var var, bool decision, Var reason) return true; } + if (auto Ver = var.Ver(cache); !Ver.end() && decision && unlikely(debug >= 1)) + assert(IsAllowedVersion(Ver)); + state.decision = decisionCast; state.depth = depth(); state.reason = reason; @@ -337,7 +340,11 @@ bool APT::Solver::Enqueue(Var var, bool decision, Var reason) return false; needsRescore = true; } - + else + { + if (not PropagateInstall(var)) + return false; + } return true; } @@ -377,7 +384,7 @@ bool APT::Solver::Install(pkgCache::PkgIterator Pkg, Var reason, Group group) if (workItem.solutions.size() > 1 || workItem.optional) AddWork(std::move(workItem)); - else if (not Install(pkgCache::VerIterator(cache, workItem.solutions[0]), workItem.reason, group)) + else if (not Enqueue(Var(pkgCache::VerIterator(cache, workItem.solutions[0])), true, workItem.reason)) return false; if (not EnqueueCommonDependencies(Pkg)) @@ -386,35 +393,32 @@ bool APT::Solver::Install(pkgCache::PkgIterator Pkg, Var reason, Group group) return true; } -bool APT::Solver::Install(pkgCache::VerIterator Ver, Var reason, Group group) +bool APT::Solver::PropagateInstall(Var var) { - if ((*this)[Ver].decision == Decision::MUST) - return true; - - if (unlikely(debug >= 1)) - assert(IsAllowedVersion(Ver)); - - // Note decision - if (not Enqueue(Var(Ver), true, reason)) - return false; - if (not Enqueue(Var(Ver.ParentPkg()), true, Var(Ver))) - return false; - - for (auto OV = Ver.ParentPkg().VersionList(); not OV.end(); ++OV) + if (auto Pkg = var.Pkg(cache); not Pkg.end()) { - if (OV != Ver && not Enqueue(Var(OV), false, Var(Ver))) - return false; } - - for (auto dep = Ver.DependsList(); not dep.end();) + else if (auto Ver = var.Ver(cache); not Ver.end()) { - // Compute a single dependency element (glob or) - pkgCache::DepIterator start; - pkgCache::DepIterator end; - dep.GlobOr(start, end); // advances dep - - if (not EnqueueOrGroup(start, end, Var(Ver))) + if (not Enqueue(Var(Ver.ParentPkg()), true, Var(Ver))) return false; + + for (auto OV = Ver.ParentPkg().VersionList(); not OV.end(); ++OV) + { + if (OV != Ver && not Enqueue(Var(OV), false, Var(Ver))) + return false; + } + + for (auto dep = Ver.DependsList(); not dep.end();) + { + // Compute a single dependency element (glob or) + pkgCache::DepIterator start; + pkgCache::DepIterator end; + dep.GlobOr(start, end); // advances dep + + if (not EnqueueOrGroup(start, end, Var(Ver))) + return false; + } } return true; @@ -608,7 +612,7 @@ bool APT::Solver::EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepItera } if (workItem.optional || workItem.solutions.size() > 1) AddWork(std::move(workItem)); - else if (not Install(pkgCache::VerIterator(cache, workItem.solutions[0]), reason, workItem.group)) + else if (not Enqueue(Var(pkgCache::VerIterator(cache, workItem.solutions[0])), true, reason)) return false; } else if (start.IsCritical() && not start.IsNegative()) @@ -901,7 +905,7 @@ bool APT::Solver::Solve() } if (unlikely(debug >= 3)) std::cerr << "(try it: " << ver.ParentPkg().FullName() << "=" << ver.VerStr() << ")\n"; - if (not Install(pkgCache::VerIterator(cache, ver), item.reason, Group::Satisfy) && not Pop()) + if (not Enqueue(Var(pkgCache::VerIterator(cache, ver)), true, item.reason) && not Pop()) return false; foundSolution = true; break; @@ -942,7 +946,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache) { if (unlikely(debug >= 1)) std::cerr << "Hold " << P.FullName() << "\n"; - if (P->CurrentVer ? not Install(P.CurrentVer(), {}, Group::HoldOrDelete) : not Enqueue(Var(P), false, Var())) + if (P->CurrentVer ? not Enqueue(Var(P.CurrentVer()), true, {}) : not Enqueue(Var(P), false, Var())) return false; } else if (state.Delete() // Normal delete request. @@ -979,7 +983,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache) if (not isOptional) { // Pre-empt the non-optional requests, as we don't want to queue them, we can just "unit propagate" here. - if (depcache[P].Keep() ? not Install(P, {}, Group) : not Install(depcache.GetCandidateVersion(P), {}, Group)) + if (depcache[P].Keep() ? not Install(P, {}, Group) : not Enqueue(Var(depcache.GetCandidateVersion(P)), true, {})) return false; } else diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h index de1bd1e73..0e6d0e2f9 100644 --- a/apt-pkg/solver3.h +++ b/apt-pkg/solver3.h @@ -153,6 +153,8 @@ class Solver bool RejectReverseDependencies(pkgCache::VerIterator Ver); // \brief Enqueue a single or group bool EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepIterator end, Var reason); + // \brief Propagate a "true" value of a variable + bool PropagateInstall(Var var); // \brief Propagate a rejection of a variable bool PropagateReject(Var var); // \brief Check if a version is allowed by policy. @@ -186,8 +188,6 @@ class Solver // \brief Mark the package for install. This is annoying as it incurs a decision bool Install(pkgCache::PkgIterator Pkg, Var reason, Group group); - // \brief Install a version. - bool Install(pkgCache::VerIterator Ver, Var reason, Group group); // \brief Apply the selections from the dep cache to the solver bool FromDepCache(pkgDepCache &depcache); -- cgit v1.2.3-70-g09d2