diff options
Diffstat (limited to 'apt-pkg/solver3.cc')
| -rw-r--r-- | apt-pkg/solver3.cc | 1035 |
1 files changed, 513 insertions, 522 deletions
diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index 4d7e0ff0b..096cbb521 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -38,188 +38,28 @@ #include <iomanip> #include <sstream> -// FIXME: Helpers stolen from DepCache, please give them back. -struct APT::Solver::CompareProviders3 /*{{{*/ -{ - pkgCache &Cache; - pkgDepCache::Policy &Policy; - pkgCache::PkgIterator const Pkg; - APT::Solver &Solver; - - pkgCache::VerIterator bestVersion(pkgCache::PkgIterator pkg) - { - pkgCache::VerIterator res = pkg.VersionList(); - for (auto v = res; not v.end(); ++v) - res = std::max(res, v, *this); - return res; - } - bool operator()(Var a, Var b) - { - pkgCache::VerIterator va = a.Ver(Cache); - pkgCache::VerIterator vb = b.Ver(Cache); - if (auto pa = a.Pkg(Cache)) - va = bestVersion(pa); - if (auto pb = b.Pkg(Cache)) - vb = bestVersion(pb); - - assert(not va.end() && not vb.end()); - return (*this)(va, vb); - } - bool operator()(pkgCache::VerIterator const &AV, pkgCache::VerIterator const &BV) - { - assert(not AV.end() && not BV.end()); - pkgCache::PkgIterator const A = AV.ParentPkg(); - pkgCache::PkgIterator const B = BV.ParentPkg(); - // Compare versions for the same package. FIXME: Move this to the real implementation - if (A == B) - { - if (AV == BV) - return false; - - // Candidate wins in upgrade scenario - if (Solver.IsUpgrade) - { - auto Cand = Solver.GetCandidateVer(A); - if (AV == Cand || BV == Cand) - return (AV == Cand); - } - - // Installed version wins otherwise - if (A.CurrentVer() == AV || B.CurrentVer() == BV) - return (A.CurrentVer() == AV); - - // Rest is ordered list, first by priority - if (auto pinA = Solver.GetPriority(AV), pinB = Solver.GetPriority(BV); pinA != pinB) - return pinA > pinB; - - // Then by version - return _system->VS->CmpVersion(AV.VerStr(), BV.VerStr()) > 0; - } - // Try obsolete choices only after exhausting non-obsolete choices such that we install - // packages replacing them and don't keep back upgrades depending on the replacement to - // keep the obsolete package installed. - if (Solver.IsUpgrade) - if (auto obsoleteA = Solver.Obsolete(A), obsoleteB = Solver.Obsolete(B); obsoleteA != obsoleteB) - return obsoleteB; - // Prefer MA:same packages if other architectures for it are installed - if ((AV->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same || - (BV->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same) - { - bool instA = false; - if ((AV->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same) - { - pkgCache::GrpIterator Grp = A.Group(); - for (pkgCache::PkgIterator P = Grp.PackageList(); P.end() == false; P = Grp.NextPkg(P)) - if (P->CurrentVer != 0) - { - instA = true; - break; - } - } - bool instB = false; - if ((BV->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same) - { - pkgCache::GrpIterator Grp = B.Group(); - for (pkgCache::PkgIterator P = Grp.PackageList(); P.end() == false; P = Grp.NextPkg(P)) - { - if (P->CurrentVer != 0) - { - instB = true; - break; - } - } - } - if (instA != instB) - return instA; - } - if ((A->CurrentVer == 0 || B->CurrentVer == 0) && A->CurrentVer != B->CurrentVer) - return A->CurrentVer != 0; - // Prefer packages in the same group as the target; e.g. foo:i386, foo:amd64 - if (A->Group != B->Group && not Pkg.end()) - { - if (A->Group == Pkg->Group && B->Group != Pkg->Group) - return true; - else if (B->Group == Pkg->Group && A->Group != Pkg->Group) - return false; - } - // we like essentials - if ((A->Flags & pkgCache::Flag::Essential) != (B->Flags & pkgCache::Flag::Essential)) - { - if ((A->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential) - return true; - else if ((B->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential) - return false; - } - if ((A->Flags & pkgCache::Flag::Important) != (B->Flags & pkgCache::Flag::Important)) - { - if ((A->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important) - return true; - else if ((B->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important) - return false; - } - // prefer native architecture - if (strcmp(A.Arch(), B.Arch()) != 0) - { - if (strcmp(A.Arch(), A.Cache()->NativeArch()) == 0) - return true; - else if (strcmp(B.Arch(), B.Cache()->NativeArch()) == 0) - return false; - std::vector<std::string> archs = APT::Configuration::getArchitectures(); - for (std::vector<std::string>::const_iterator a = archs.begin(); a != archs.end(); ++a) - if (*a == A.Arch()) - return true; - else if (*a == B.Arch()) - return false; - } - // higher priority seems like a good idea - if (AV->Priority != BV->Priority) - return AV->Priority < BV->Priority; - if (auto NameCmp = strcmp(A.Name(), B.Name())) - return NameCmp < 0; - // unable to decide… - return A->ID > B->ID; - } -}; - -/** \brief Returns \b true for packages matching a regular - * expression in APT::NeverAutoRemove. - */ -class DefaultRootSetFunc2 : public pkgDepCache::DefaultRootSetFunc +namespace APT::Solver { - std::unique_ptr<APT::CacheFilter::Matcher> Kernels; - - public: - DefaultRootSetFunc2(pkgCache *cache) : Kernels(APT::KernelAutoRemoveHelper::GetProtectedKernelsFilter(cache)) {}; - ~DefaultRootSetFunc2() override = default; - bool InRootSet(const pkgCache::PkgIterator &pkg) override { return pkg.end() == false && ((*Kernels)(pkg) || DefaultRootSetFunc::InRootSet(pkg)); }; -}; // FIXME: DEDUP with pkgDepCache. -/*}}}*/ - -APT::Solver::Solver(pkgCache &cache, pkgDepCache::Policy &policy, EDSP::Request::Flags requestFlags) +Solver::Solver(pkgCache &cache) : cache(cache), - policy(policy), rootState(new State), pkgStates(cache), - verStates(cache), - pkgObsolete(cache), - priorities(cache), - candidates(cache), - requestFlags(requestFlags) + verStates(cache) { // Ensure trivially static_assert(std::is_trivially_destructible_v<Work>); - static_assert(std::is_trivially_destructible_v<Solved>); - static_assert(sizeof(APT::Solver::Var) == sizeof(map_pointer<pkgCache::Package>)); - static_assert(sizeof(APT::Solver::Var) == sizeof(map_pointer<pkgCache::Version>)); + static_assert(std::is_trivially_destructible_v<Trail>); + static_assert(sizeof(Var) == sizeof(map_pointer<pkgCache::Package>)); + static_assert(sizeof(Var) == sizeof(map_pointer<pkgCache::Version>)); // Root state is "true". - rootState->decision = Decision::MUST; + rootState->assignment = LiftedBool::True; } -APT::Solver::~Solver() = default; +Solver::~Solver() = default; // This function determines if a work item is less important than another. -bool APT::Solver::Work::operator<(APT::Solver::Work const &b) const +bool Solver::Work::operator<(Solver::Work const &b) const { if ((not clause->optional && size < 2) != (not b.clause->optional && b.size < 2)) return not b.clause->optional && b.size < 2; @@ -280,40 +120,45 @@ std::string APT::Solver::Clause::toString(pkgCache &cache, bool pretty, bool sho return out; } -std::string APT::Solver::Work::toString(pkgCache &cache) const +std::string Solver::Work::toString(pkgCache &cache) const { std::ostringstream out; if (erased) out << "Erased "; if (clause->optional) out << "Optional "; - out << "Item (" << ssize_t(size <= clause->solutions.size() ? size : -1) << "@" << depth << ") "; + out << "Item (" << ssize_t(size <= clause->solutions.size() ? size : -1) << "@" << level << ") "; out << clause->toString(cache); return out.str(); } -inline APT::Solver::Var APT::Solver::bestReason(APT::Solver::Clause const *clause, APT::Solver::Var var) const +inline Var Solver::bestReason(Clause const *clause, Var var) const { if (not clause) return Var{}; if (clause->reason == var) for (auto choice : clause->solutions) { - if (clause->negative && (*this)[choice].decision == Decision::MUST) + if (clause->negative && value(choice) == LiftedBool::True) return choice; - if (not clause->negative && (*this)[choice].decision == Decision::MUSTNOT) + if (not clause->negative && value(choice) == LiftedBool::False) return choice; } return clause->reason; } +inline LiftedBool Solver::value(Lit lit) const +{ + return lit.sign() ? ~(*this)[lit.var()].assignment : (*this)[lit.var()].assignment; +} + // Prints an implication graph part of the form A -> B -> C, possibly with "not" -std::string APT::Solver::WhyStr(Var reason) const +std::string Solver::WhyStr(Var reason) const { std::vector<std::string> out; while (not reason.empty()) { - if ((*this)[reason].decision == Decision::MUSTNOT) + if (value(reason) == LiftedBool::False) out.push_back(std::string("not ") + reason.toString(cache)); else out.push_back(reason.toString(cache)); @@ -328,31 +173,31 @@ std::string APT::Solver::WhyStr(Var reason) const return outstr; } -std::string APT::Solver::LongWhyStr(Var var, bool decision, const Clause *rclause, std::string prefix, std::unordered_set<Var> &seen) const +std::string Solver::LongWhyStr(Var var, bool assignment, const Clause *rclause, std::string prefix, std::unordered_set<Var> &seen) const { std::ostringstream out; // Helper function to nicely print more details than just "install/do not install", such as "removal", "upgrade", "downgrade", "install" - auto printSelection = [this](Var var, bool decision) + auto printSelection = [this](Var var, bool assignment) { std::string s; - if (auto pkg = var.Pkg(cache); not decision && pkg && pkg->CurrentVer) + if (auto pkg = var.Pkg(cache); not assignment && pkg && pkg->CurrentVer) strprintf(s, "%s is selected for removal", var.toString(cache).c_str()); - else if (auto ver = var.Ver(cache); decision && ver && ver.ParentPkg().CurrentVer() && ver.ParentPkg().CurrentVer() != ver) + else if (auto ver = var.Ver(cache); assignment && ver && ver.ParentPkg().CurrentVer() && ver.ParentPkg().CurrentVer() != ver) { if (cache.VS->CmpVersion(ver.ParentPkg().CurrentVer().VerStr(), ver.VerStr()) < 0) strprintf(s, "%s is selected as an upgrade", var.toString(cache).c_str()); else strprintf(s, "%s is selected as a downgrade", var.toString(cache).c_str()); } - else if (not decision) + else if (not assignment) strprintf(s, "%s is not selected for install", var.toString(cache).c_str()); else strprintf(s, "%s is selected for install", var.toString(cache).c_str()); return s; }; - // Helper: Recurse into all of the children of the clause and print the decision for them. + // Helper: Recurse into all of the children of the clause and print the assignment for them. auto recurseChildren = [&](const Clause *clause, Var skip = Var()) { if (clause->solutions.empty()) @@ -362,16 +207,16 @@ std::string APT::Solver::LongWhyStr(Var var, bool decision, const Clause *rclaus if (choice == skip) continue; - if ((*this)[choice].decision == Decision::NONE) + if (value(choice) == LiftedBool::Undefined) out << prefix << "- " << choice.toString(cache) << " is undecided\n"; else - out << prefix << "- " << LongWhyStr(choice, (*this)[choice].decision == Decision::MUST, (*this)[choice].reason, prefix + " ", seen).substr(prefix.size() + 2); + out << prefix << "- " << LongWhyStr(choice, value(choice) == LiftedBool::True, (*this)[choice].reason, prefix + " ", seen).substr(prefix.size() + 2); } }; // Inverse version selection clauses that select the package if the version is selected, // such as pkg=ver -> pkg, are irrelevant for the user, skip them - if (var.Pkg() && decision && rclause && rclause->group == Group::SelectVersion) + if (var.Pkg() && assignment && rclause && rclause->group == Group::SelectVersion) { var = rclause->reason; rclause = (*this)[var].reason; @@ -380,25 +225,25 @@ std::string APT::Solver::LongWhyStr(Var var, bool decision, const Clause *rclaus // No reason given, probably a user request or manually installed or essential or whatnot. if (not rclause) { - out << prefix << printSelection(var, decision) << "\n"; + out << prefix << printSelection(var, assignment) << "\n"; return out.str(); } - // We could be called with a decision we tried to make but failed due to a conflict; - // this checks if it is the real decision. - if ((*this)[var].decision != Decision::NONE && decision == ((*this)[var].decision == Decision::MUST) && (*this)[var].reason == rclause) + // We could be called with a assignment we tried to make but failed due to a conflict; + // this checks if it is the real assignment. + if (value(var) != LiftedBool::Undefined && assignment == (value(var) == LiftedBool::True) && (*this)[var].reason == rclause) { - // If we have seen the real decision before; we dont't need to print it again. + // If we have seen the real assignment before; we dont't need to print it again. if (seen.find(var) != seen.end()) { - out << prefix << printSelection(var, decision) << " as above\n"; + out << prefix << printSelection(var, assignment) << " as above\n"; return out.str(); } seen.insert(var); } // A package was decided "not install" due to a positive clause, so the clause is unsat. - if (not decision && rclause && not rclause->negative) + if (not assignment && rclause && not rclause->negative) { out << prefix << rclause->toString(cache, true) << "\n"; out << prefix << "but none of the choices are installable:\n"; @@ -406,13 +251,13 @@ std::string APT::Solver::LongWhyStr(Var var, bool decision, const Clause *rclaus return out.str(); } - // Build the strongest path from a root to our decision leaf + // Build the strongest path from a root to our assignment leaf std::vector<Var> path; for (auto reason = bestReason(rclause, var); not reason.empty(); reason = bestReason((*this)[reason].reason, reason)) path.push_back(reason); // Render the strong reasoning path - out << prefix << printSelection(var, decision) << " because:\n"; + out << prefix << printSelection(var, assignment) << " because:\n"; auto w = std::to_string(path.size() + 1).size(); size_t i = 1; for (auto it = path.rbegin(); it != path.rend(); ++it, ++i) @@ -428,7 +273,7 @@ std::string APT::Solver::LongWhyStr(Var var, bool decision, const Clause *rclaus { if ((it + 1) == path.rend() || seen.find(*(it + 1)) == seen.end()) { - out << prefix << (i == 1 ? "" : "1-") << i << ". " << printSelection(*it, state.decision == Decision::MUST) << " as above\n"; + out << prefix << (i == 1 ? "" : "1-") << i << ". " << printSelection(*it, state.assignment == LiftedBool::True) << " as above\n"; } continue; } @@ -437,13 +282,13 @@ std::string APT::Solver::LongWhyStr(Var var, bool decision, const Clause *rclaus { out << prefix << std::setw(w) << i << ". " << state.reason->toString(cache, true) << "\n"; if (state.reason->solutions.size() > 1) - out << prefix << std::setw(w) << " " << " [selected " << it->toString(cache) << " for " << (state.decision == Decision::MUST ? "install" : "remove") << "]\n"; + out << prefix << std::setw(w) << " " << " [selected " << it->toString(cache) << " for " << (state.assignment == LiftedBool::True ? "install" : "remove") << "]\n"; } else - out << prefix << std::setw(w) << i << ". " << printSelection(*it, state.decision == Decision::MUST) << "\n"; + out << prefix << std::setw(w) << i << ". " << printSelection(*it, state.assignment == LiftedBool::True) << "\n"; } - // Print the leaf. We can't have the leaf in the path because we might be called for an attempted decision + // Print the leaf. We can't have the leaf in the path because we might be called for an attempted assignment // that conflicts with the actual assignment (to simplify: we marked X for not install, then we process Y depends X // and try to mark X and reach the conflict, we are called with "X" and the "Y depends X" clause). out << prefix << std::setw(w) << i << ". " << rclause->toString(cache, true) << "\n"; @@ -490,122 +335,58 @@ std::string APT::Solver::LongWhyStr(Var var, bool decision, const Clause *rclaus return out.str(); } -// This is essentially asking whether any other binary in the source package has a higher candidate -// version. This pretends that each package is installed at the same source version as the package -// under consideration. -bool APT::Solver::ObsoletedByNewerSourceVersion(pkgCache::VerIterator cand) const +bool Solver::Assume(Lit lit, const Clause *reason) { - const auto pkg = cand.ParentPkg(); - const int candPriority = GetPriority(cand); - - for (auto ver = cand.Cache()->FindGrp(cand.SourcePkgName()).VersionsInSource(); not ver.end(); ver = ver.NextInSource()) - { - // We are only interested in other packages in the same source package; built for the same architecture. - if (ver->ParentPkg == cand->ParentPkg || ver.ParentPkg()->Arch != cand.ParentPkg()->Arch || - (ver->MultiArch & pkgCache::Version::All) != (cand->MultiArch & pkgCache::Version::All) || - cache.VS->CmpVersion(ver.SourceVerStr(), cand.SourceVerStr()) <= 0) - continue; - - // We also take equal priority here, given that we have a higher version - const int priority = GetPriority(ver); - if (priority == 0 || priority < candPriority) - continue; - - pkgObsolete[pkg] = 2; - if (debug >= 3) - std::cerr << "Obsolete: " << cand.ParentPkg().FullName() << "=" << cand.VerStr() << " due to " << ver.ParentPkg().FullName() << "=" << ver.VerStr() << "\n"; - return true; - } - - return false; + trailLim.push_back(trail.size()); + return Enqueue(lit, std::move(reason)); } -bool APT::Solver::Obsolete(pkgCache::PkgIterator pkg, bool AllowManual) const +bool Solver::Enqueue(Lit lit, const Clause *reason) { - if ((*this)[pkg].flags.manual && not AllowManual) - return false; - if (pkgObsolete[pkg] != 0) - return pkgObsolete[pkg] == 2; + assert(not lit.empty()); - auto ver = GetCandidateVer(pkg); + auto &state = (*this)[lit.var()]; + auto assignment = lit.sign() ? LiftedBool::False : LiftedBool::True; - if (ver.end() && not StrictPinning) - ver = pkg.VersionList(); - if (ver.end()) + if (state.assignment != LiftedBool::Undefined) { - if (debug >= 3) - std::cerr << "Obsolete: " << pkg.FullName() << " - not installable\n"; - pkgObsolete[pkg] = 2; - return true; - } - - if (ObsoletedByNewerSourceVersion(ver)) - return true; - - // Any version downloadable is good enough for us tbh - for (auto ver = pkg.VersionList(); not ver.end(); ++ver) - { - if (ver.Downloadable()) - { - pkgObsolete[pkg] = 1; - return false; - } - } - - if (debug >= 3) - std::cerr << "Obsolete: " << ver.ParentPkg().FullName() << "=" << ver.VerStr() << " - not installable\n"; - pkgObsolete[pkg] = 2; - return true; -} -bool APT::Solver::Assume(Var var, bool decision, const Clause *reason) -{ - choices.push_back(solved.size()); - return Enqueue(var, decision, std::move(reason)); -} - -bool APT::Solver::Enqueue(Var var, bool decision, const Clause *reason) -{ - auto &state = (*this)[var]; - auto decisionCast = decision ? Decision::MUST : Decision::MUSTNOT; - - if (state.decision != Decision::NONE) - { - if (state.decision != decisionCast) + if (state.assignment != assignment) { std::ostringstream err; - err << "Unable to satisfy dependencies. Reached two conflicting decisions:" << "\n"; + err << "Unable to satisfy dependencies. Reached two conflicting assignments:" << "\n"; std::unordered_set<Var> seen; - err << "1. " << LongWhyStr(var, state.decision == Decision::MUST, state.reason, " ", seen).substr(3) << "\n"; - err << "2. " << LongWhyStr(var, decision, reason, " ", seen).substr(3); + err << "1. " << LongWhyStr(lit.var(), state.assignment == LiftedBool::True, state.reason, " ", seen).substr(3) << "\n"; + err << "2. " << LongWhyStr(lit.var(), not lit.sign(), reason, " ", seen).substr(3); return _error->Error("%s", err.str().c_str()); } return true; } - state.decision = decisionCast; - state.depth = depth(); + state.assignment = assignment; + state.level = decisionLevel(); state.reason = reason; + // FIXME: Adjust call to bestReason to use lit if (unlikely(debug >= 1)) - std::cerr << "[" << depth() << "] " << (decision ? "Install" : "Reject") << ":" << var.toString(cache) << " (" << WhyStr(bestReason(reason, var)) << ")\n"; + std::cerr << "[" << decisionLevel() << "] " << (lit.sign() ? "Reject" : "Install") << ":" << lit.var().toString(cache) << " (" << WhyStr(bestReason(reason, lit.var())) << ")\n"; - solved.push_back(Solved{var, std::nullopt}); - propQ.push(var); + trail.push_back(Trail{lit.var(), std::nullopt}); + propQ.push(lit.var()); return true; } -bool APT::Solver::Propagate() +bool Solver::Propagate() { while (!propQ.empty()) { Var var = propQ.front(); propQ.pop(); - if ((*this)[var].decision == Decision::MUST) + if (value(var) == LiftedBool::True) { Discover(var); for (auto &clause : (*this)[var].clauses) - if (not AddWork(Work{clause.get(), depth()})) + if (not AddWork(Work{clause.get(), decisionLevel()})) return false; for (auto rclause : (*this)[var].rclauses) { @@ -613,37 +394,37 @@ bool APT::Solver::Propagate() continue; if (unlikely(debug >= 3)) std::cerr << "Propagate " << var.toString(cache) << " to NOT " << rclause->reason.toString(cache) << " for dep " << const_cast<Clause *>(rclause)->toString(cache) << std::endl; - if (not Enqueue(rclause->reason, false, rclause)) + if (not Enqueue(~rclause->reason, rclause)) return false; } } - else if ((*this)[var].decision == Decision::MUSTNOT) + else if (value(var) == LiftedBool::False) { for (auto rclause : (*this)[var].rclauses) { if (rclause->negative || rclause->reason.empty()) continue; - if ((*this)[rclause->reason].decision == Decision::MUSTNOT) + if (value(rclause->reason) == LiftedBool::False) continue; auto count = std::count_if(rclause->solutions.begin(), rclause->solutions.end(), [this](auto var) - { return (*this)[var].decision != Decision::MUSTNOT; }); + { return value(var) != LiftedBool::False; }); - if (count == 1 && (*this)[rclause->reason].decision == Decision::MUST) + if (count == 1 && value(rclause->reason) == LiftedBool::True) { if (unlikely(debug >= 3)) std::cerr << "Propagate NOT " << var.toString(cache) << " to unit clause " << rclause->toString(cache); if (rclause->optional) { // Enqueue duplicated item, this will ensure we see it at the correct time - if (not AddWork(Work{rclause, depth()})) + if (not AddWork(Work{rclause, decisionLevel()})) return false; } else { // Find the variable that must be chosen and enqueue it as a fact for (auto sol : rclause->solutions) - if ((*this)[sol].decision == Decision::NONE && not Enqueue(sol, true, rclause)) + if (value(sol) == LiftedBool::Undefined && not Enqueue(sol, rclause)) return false; } continue; @@ -654,7 +435,7 @@ bool APT::Solver::Propagate() if (unlikely(debug >= 3)) std::cerr << "Propagate NOT " << var.toString(cache) << " to " << rclause->reason.toString(cache) << " for dep " << const_cast<Clause *>(rclause)->toString(cache) << std::endl; - if (not Enqueue(rclause->reason, false, rclause)) // Last version invalidated + if (not Enqueue(~rclause->reason, rclause)) // Last version invalidated return false; } } @@ -662,6 +443,348 @@ bool APT::Solver::Propagate() return true; } +void Solver::UndoOne() +{ + auto trailItem = trail.back(); + + if (unlikely(debug >= 4)) + std::cerr << "Undoing a single assignment\n"; + + if (not trailItem.assigned.empty()) + { + if (unlikely(debug >= 4)) + std::cerr << "Unassign " << trailItem.assigned.toString(cache) << "\n"; + auto &state = (*this)[trailItem.assigned]; + state.assignment = LiftedBool::Undefined; + state.reason = nullptr; + state.reasonStr = nullptr; + state.level = 0; + } + + if (auto work = trailItem.work) + { + if (unlikely(debug >= 4)) + std::cerr << "Adding work item " << work->toString(cache) << std::endl; + + must_succeed(AddWork(std::move(*work))); + } + + trail.pop_back(); + + // FIXME: Add the undo handling here once we have watchers. +} + +bool Solver::Pop() +{ + if (decisionLevel() == 0) + return false; + + time_t now = time(nullptr); + if (startTime == 0) + startTime = now; + if (now - startTime >= Timeout) + return _error->Error("Solver timed out."); + + if (unlikely(debug >= 2)) + for (std::string msg; _error->PopMessage(msg);) + std::cerr << "Branch failed: " << msg << std::endl; + + _error->Discard(); + + // Assume() actually failed to enqueue anything, abort here + if (trailLim.back() == trail.size()) + { + trailLim.pop_back(); + return true; + } + + assert(trailLim.back() < trail.size()); + int itemsToUndo = trail.size() - trailLim.back(); + auto choice = trail[trailLim.back()].assigned; + + for (; itemsToUndo; --itemsToUndo) + UndoOne(); + + // We need to remove any work that is at a higher level. + // FIXME: We should just mark the entries as erased and only do a compaction + // of the heap once we have a lot of erased entries in it. + trailLim.pop_back(); + work.erase(std::remove_if(work.begin(), work.end(), [this](Work &w) -> bool + { return w.level > decisionLevel() || w.erased; }), + work.end()); + std::make_heap(work.begin(), work.end()); + + if (unlikely(debug >= 2)) + std::cerr << "Backtracking to choice " << choice.toString(cache) << "\n"; + + // FIXME: There should be a reason! + if (not choice.empty() && not Enqueue(~choice, {})) + return false; + + (*this)[choice].reasonStr = "backtracked"; + + if (unlikely(debug >= 2)) + std::cerr << "Backtracked to choice " << choice.toString(cache) << "\n"; + + return true; +} + +bool Solver::AddWork(Work &&w) +{ + if (w.clause->negative) + { + for (auto var : w.clause->solutions) + if (not Enqueue(~var, w.clause)) + return false; + } + else + { + if (unlikely(debug >= 3 && w.clause->optional)) + std::cerr << "Enqueuing Recommends " << w.clause->toString(cache) << std::endl; + if (w.clause->solutions.size() == 1 && not w.clause->optional) + return Enqueue(w.clause->solutions[0], w.clause); + + w.size = std::count_if(w.clause->solutions.begin(), w.clause->solutions.end(), [this](auto V) + { return value(V) != LiftedBool::False; }); + work.push_back(std::move(w)); + std::push_heap(work.begin(), work.end()); + } + return true; +} + +bool Solver::Solve() +{ + _error->PushToStack(); + DEFER([&]() + { _error->MergeWithStack(); }); + startTime = time(nullptr); + while (true) + { + while (_error->PendingError() || not Propagate()) + { + if (not Pop()) + return false; + } + + if (work.empty()) + break; + + auto item = work.front(); + std::pop_heap(work.begin(), work.end()); + work.pop_back(); + // This item has been replaced with a new one. Remove it. + if (item.erased) + continue; + + if (std::any_of(item.clause->solutions.begin(), item.clause->solutions.end(), [this](auto ver) + { return value(ver) == LiftedBool::True; })) + { + if (unlikely(debug >= 2)) + std::cerr << "ELIDED " << item.toString(cache) << std::endl; + } + else if (auto candidate = std::find_if(item.clause->solutions.begin(), item.clause->solutions.end(), [this](auto ver) + { return value(ver) == LiftedBool::Undefined; }); + candidate != item.clause->solutions.end()) + { + if (unlikely(debug >= 3)) + std::cerr << item.toString(cache) << "\n" + << "(try it: " << candidate->toString(cache) << ")\n"; + must_succeed(Assume(*candidate, item.clause)); + } + else if (item.clause->optional) + { + if (unlikely(debug >= 1)) + std::cerr << item.toString(cache) << "\n"; + } + else + { + if (unlikely(debug >= 1)) + std::cerr << item.toString(cache) << "\n"; + // Enqueue produces the right error message for us here, given that reason has been assigned true already... + assert(value(item.clause->reason) == LiftedBool::True); + must_succeed(not Enqueue(~item.clause->reason, item.clause)); + assert(value(item.clause->reason) == LiftedBool::True); + } + // Must push to trail after any Assume() above. + trail.push_back(Trail{Var(), item}); + } + + return true; +} + +// -------------------------------------------------------------------------------------------------------------------- +// -------------------------------------------- Dependency solver ----------------------------------------------------- +// -------------------------------------------------------------------------------------------------------------------- +// FIXME: Helpers stolen from DepCache, please give them back. +struct CompareProviders3 /*{{{*/ +{ + pkgCache &Cache; + pkgDepCache::Policy &Policy; + pkgCache::PkgIterator const Pkg; + APT::Solver::DependencySolver &Solver; + + pkgCache::VerIterator bestVersion(pkgCache::PkgIterator pkg) + { + pkgCache::VerIterator res = pkg.VersionList(); + for (auto v = res; not v.end(); ++v) + res = std::max(res, v, *this); + return res; + } + bool operator()(Var a, Var b) + { + pkgCache::VerIterator va = a.Ver(Cache); + pkgCache::VerIterator vb = b.Ver(Cache); + if (auto pa = a.Pkg(Cache)) + va = bestVersion(pa); + if (auto pb = b.Pkg(Cache)) + vb = bestVersion(pb); + + assert(not va.end() && not vb.end()); + return (*this)(va, vb); + } + bool operator()(pkgCache::VerIterator const &AV, pkgCache::VerIterator const &BV) + { + assert(not AV.end() && not BV.end()); + pkgCache::PkgIterator const A = AV.ParentPkg(); + pkgCache::PkgIterator const B = BV.ParentPkg(); + // Compare versions for the same package. FIXME: Move this to the real implementation + if (A == B) + { + if (AV == BV) + return false; + + // Candidate wins in upgrade scenario + if (Solver.IsUpgrade) + { + auto Cand = Solver.GetCandidateVer(A); + if (AV == Cand || BV == Cand) + return (AV == Cand); + } + + // Installed version wins otherwise + if (A.CurrentVer() == AV || B.CurrentVer() == BV) + return (A.CurrentVer() == AV); + + // Rest is ordered list, first by priority + if (auto pinA = Solver.GetPriority(AV), pinB = Solver.GetPriority(BV); pinA != pinB) + return pinA > pinB; + + // Then by version + return _system->VS->CmpVersion(AV.VerStr(), BV.VerStr()) > 0; + } + // Try obsolete choices only after exhausting non-obsolete choices such that we install + // packages replacing them and don't keep back upgrades depending on the replacement to + // keep the obsolete package installed. + if (Solver.IsUpgrade) + if (auto obsoleteA = Solver.Obsolete(A), obsoleteB = Solver.Obsolete(B); obsoleteA != obsoleteB) + return obsoleteB; + // Prefer MA:same packages if other architectures for it are installed + if ((AV->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same || + (BV->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same) + { + bool instA = false; + if ((AV->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same) + { + pkgCache::GrpIterator Grp = A.Group(); + for (pkgCache::PkgIterator P = Grp.PackageList(); P.end() == false; P = Grp.NextPkg(P)) + if (P->CurrentVer != 0) + { + instA = true; + break; + } + } + bool instB = false; + if ((BV->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same) + { + pkgCache::GrpIterator Grp = B.Group(); + for (pkgCache::PkgIterator P = Grp.PackageList(); P.end() == false; P = Grp.NextPkg(P)) + { + if (P->CurrentVer != 0) + { + instB = true; + break; + } + } + } + if (instA != instB) + return instA; + } + if ((A->CurrentVer == 0 || B->CurrentVer == 0) && A->CurrentVer != B->CurrentVer) + return A->CurrentVer != 0; + // Prefer packages in the same group as the target; e.g. foo:i386, foo:amd64 + if (A->Group != B->Group && not Pkg.end()) + { + if (A->Group == Pkg->Group && B->Group != Pkg->Group) + return true; + else if (B->Group == Pkg->Group && A->Group != Pkg->Group) + return false; + } + // we like essentials + if ((A->Flags & pkgCache::Flag::Essential) != (B->Flags & pkgCache::Flag::Essential)) + { + if ((A->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential) + return true; + else if ((B->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential) + return false; + } + if ((A->Flags & pkgCache::Flag::Important) != (B->Flags & pkgCache::Flag::Important)) + { + if ((A->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important) + return true; + else if ((B->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important) + return false; + } + // prefer native architecture + if (strcmp(A.Arch(), B.Arch()) != 0) + { + if (strcmp(A.Arch(), A.Cache()->NativeArch()) == 0) + return true; + else if (strcmp(B.Arch(), B.Cache()->NativeArch()) == 0) + return false; + std::vector<std::string> archs = APT::Configuration::getArchitectures(); + for (std::vector<std::string>::const_iterator a = archs.begin(); a != archs.end(); ++a) + if (*a == A.Arch()) + return true; + else if (*a == B.Arch()) + return false; + } + // higher priority seems like a good idea + if (AV->Priority != BV->Priority) + return AV->Priority < BV->Priority; + if (auto NameCmp = strcmp(A.Name(), B.Name())) + return NameCmp < 0; + // unable to decide… + return A->ID > B->ID; + } +}; + +/** \brief Returns \b true for packages matching a regular + * expression in APT::NeverAutoRemove. + */ +class DefaultRootSetFunc2 : public pkgDepCache::DefaultRootSetFunc +{ + std::unique_ptr<APT::CacheFilter::Matcher> Kernels; + + public: + DefaultRootSetFunc2(pkgCache *cache) : Kernels(APT::KernelAutoRemoveHelper::GetProtectedKernelsFilter(cache)) {}; + ~DefaultRootSetFunc2() override = default; + + bool InRootSet(const pkgCache::PkgIterator &pkg) override { return pkg.end() == false && ((*Kernels)(pkg) || DefaultRootSetFunc::InRootSet(pkg)); }; +}; // FIXME: DEDUP with pkgDepCache. +/*}}}*/ + +DependencySolver::DependencySolver(pkgCache &cache, pkgDepCache::Policy &policy, EDSP::Request::Flags requestFlags) + : Solver(cache), + policy(policy), + requestFlags(requestFlags), + pkgObsolete(cache), + priorities(cache), + candidates(cache) +{ +} + +DependencySolver::~DependencySolver() = default; + static bool SameOrGroup(pkgCache::DepIterator a, pkgCache::DepIterator b) { while (1) @@ -679,7 +802,7 @@ static bool SameOrGroup(pkgCache::DepIterator a, pkgCache::DepIterator b) return not(a->CompareOp & pkgCache::Dep::Or) && not(b->CompareOp & pkgCache::Dep::Or); } -const APT::Solver::Clause *APT::Solver::RegisterClause(Clause &&clause) +const Clause *DependencySolver::RegisterClause(Clause &&clause) { auto &clauses = (*this)[clause.reason].clauses; pkgCache::DepIterator dep(cache, clause.dep); @@ -703,17 +826,15 @@ const APT::Solver::Clause *APT::Solver::RegisterClause(Clause &&clause) earlierDep.TargetPkg() != dep.TargetPkg()) continue; if (std::none_of(earlierClause->solutions.begin(), earlierClause->solutions.end(), [&clause](auto earlierSol) - { return std::find(clause.solutions.begin(), - clause.solutions.end(), - earlierSol) != clause.solutions.end(); })) + { return std::ranges::contains(clause.solutions, + earlierSol); })) continue; if (earlierClause->optional == clause.optional) { std::erase_if(earlierClause->solutions, [&clause, this](auto earlierSol) - { return std::find(clause.solutions.begin(), - clause.solutions.end(), - earlierSol) == clause.solutions.end(); }); + { return not std::ranges::contains(clause.solutions, + earlierSol); }); earlierClause->merged.push_front(clause); merged = true; @@ -722,9 +843,8 @@ const APT::Solver::Clause *APT::Solver::RegisterClause(Clause &&clause) { // If say a Depends has fewer solution than a Recommends, remove the Recommend's extranous ones. std::erase_if(clause.solutions, [&earlierClause, this](auto sol) - { return std::find(earlierClause->solutions.begin(), - earlierClause->solutions.end(), - sol) == earlierClause->solutions.end(); }); + { return not std::ranges::contains(earlierClause->solutions, + sol); }); // Remove recursion here, such that we display correctly (if we ever display anywhere...) auto earlierClauseCopy = *earlierClause; @@ -744,7 +864,74 @@ const APT::Solver::Clause *APT::Solver::RegisterClause(Clause &&clause) return inserted.get(); } -void APT::Solver::Discover(Var var) +// This is essentially asking whether any other binary in the source package has a higher candidate +// version. This pretends that each package is installed at the same source version as the package +// under consideration. +bool DependencySolver::ObsoletedByNewerSourceVersion(pkgCache::VerIterator cand) const +{ + const auto pkg = cand.ParentPkg(); + const int candPriority = GetPriority(cand); + + for (auto ver = cand.Cache()->FindGrp(cand.SourcePkgName()).VersionsInSource(); not ver.end(); ver = ver.NextInSource()) + { + // We are only interested in other packages in the same source package; built for the same architecture. + if (ver->ParentPkg == cand->ParentPkg || ver.ParentPkg()->Arch != cand.ParentPkg()->Arch || + (ver->MultiArch & pkgCache::Version::All) != (cand->MultiArch & pkgCache::Version::All) || + cache.VS->CmpVersion(ver.SourceVerStr(), cand.SourceVerStr()) <= 0) + continue; + + // We also take equal priority here, given that we have a higher version + const int priority = GetPriority(ver); + if (priority == 0 || priority < candPriority) + continue; + + pkgObsolete[pkg] = 2; + if (debug >= 3) + std::cerr << "Obsolete: " << cand.ParentPkg().FullName() << "=" << cand.VerStr() << " due to " << ver.ParentPkg().FullName() << "=" << ver.VerStr() << "\n"; + return true; + } + + return false; +} + +bool DependencySolver::Obsolete(pkgCache::PkgIterator pkg, bool AllowManual) const +{ + if ((*this)[pkg].flags.manual && not AllowManual) + return false; + if (pkgObsolete[pkg] != 0) + return pkgObsolete[pkg] == 2; + + auto ver = GetCandidateVer(pkg); + + if (ver.end() && not StrictPinning) + ver = pkg.VersionList(); + if (ver.end()) + { + if (debug >= 3) + std::cerr << "Obsolete: " << pkg.FullName() << " - not installable\n"; + pkgObsolete[pkg] = 2; + return true; + } + + if (ObsoletedByNewerSourceVersion(ver)) + return true; + + // Any version downloadable is good enough for us tbh + for (auto ver = pkg.VersionList(); not ver.end(); ++ver) + { + if (ver.Downloadable()) + { + pkgObsolete[pkg] = 1; + return false; + } + } + + if (debug >= 3) + std::cerr << "Obsolete: " << ver.ParentPkg().FullName() << "=" << ver.VerStr() << " - not installable\n"; + pkgObsolete[pkg] = 2; + return true; +} +void DependencySolver::Discover(Var var) { assert(discoverQ.empty()); discoverQ.push(var); @@ -811,15 +998,15 @@ void APT::Solver::Discover(Var var) } } - // Recursively discover everything else that is not already FALSE by fact (MUSTNOT at depth 0) + // Recursively discover everything else that is not already FALSE by fact (False at level 0) for (auto const &clause : state.clauses) for (auto const &var : clause->solutions) - if ((*this)[var].decision != Decision::MUSTNOT || (*this)[var].depth > 0) + if (value(var) != LiftedBool::False || (*this)[var].level > 0) discoverQ.push(var); } } -void APT::Solver::RegisterCommonDependencies(pkgCache::PkgIterator Pkg) +void DependencySolver::RegisterCommonDependencies(pkgCache::PkgIterator Pkg) { for (auto dep = Pkg.VersionList().DependsList(); not dep.end();) { @@ -846,7 +1033,7 @@ void APT::Solver::RegisterCommonDependencies(pkgCache::PkgIterator Pkg) } } -APT::Solver::Clause APT::Solver::TranslateOrGroup(pkgCache::DepIterator start, pkgCache::DepIterator end, Var reason) +Clause DependencySolver::TranslateOrGroup(pkgCache::DepIterator start, pkgCache::DepIterator end, Var reason) { // Non-important dependencies can only be installed if they are currently satisfied, see the check further // below once we have calculated all possible solutions. @@ -984,204 +1171,8 @@ APT::Solver::Clause APT::Solver::TranslateOrGroup(pkgCache::DepIterator start, p return clause; } -void APT::Solver::Push(Var var, Work work) -{ - if (unlikely(debug >= 2)) - std::cerr << "Trying choice for " << work.toString(cache) << std::endl; - - choices.push_back(solved.size()); - solved.push_back(Solved{var, std::move(work)}); -} - -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)) - std::cerr << "Unassign " << solvedItem.assigned.toString(cache) << "\n"; - auto &state = (*this)[solvedItem.assigned]; - state.decision = Decision::NONE; - state.reason = nullptr; - state.reasonStr = nullptr; - state.depth = 0; - } - - if (auto work = solvedItem.work) - { - if (unlikely(debug >= 4)) - std::cerr << "Adding work item " << work->toString(cache) << std::endl; - - if (not AddWork(std::move(*work))) - abort(); - } - - solved.pop_back(); - - // FIXME: Add the undo handling here once we have watchers. -} - -bool APT::Solver::Pop() -{ - if (depth() == 0) - return false; - - time_t now = time(nullptr); - if (startTime == 0) - startTime = now; - if (now - startTime >= Timeout) - return _error->Error("Solver timed out."); - - if (unlikely(debug >= 2)) - for (std::string msg; _error->PopMessage(msg);) - std::cerr << "Branch failed: " << msg << std::endl; - - _error->Discard(); - - // Assume() actually failed to enqueue anything, abort here - if (choices.back() == solved.size()) - { - choices.pop_back(); - return true; - } - - assert(choices.back() < solved.size()); - int itemsToUndo = solved.size() - choices.back(); - auto choice = solved[choices.back()].assigned; - - for (; itemsToUndo; --itemsToUndo) - UndoOne(); - - // We need to remove any work that is at a higher depth. - // FIXME: We should just mark the entries as erased and only do a compaction - // of the heap once we have a lot of erased entries in it. - choices.pop_back(); - work.erase(std::remove_if(work.begin(), work.end(), [this](Work &w) -> bool - { return w.depth > depth() || w.erased; }), - work.end()); - std::make_heap(work.begin(), work.end()); - - if (unlikely(debug >= 2)) - std::cerr << "Backtracking to choice " << choice.toString(cache) << "\n"; - - // FIXME: There should be a reason! - if (not choice.empty() && not Enqueue(choice, false, {})) - return false; - - (*this)[choice].reasonStr = "backtracked"; - - if (unlikely(debug >= 2)) - std::cerr << "Backtracked to choice " << choice.toString(cache) << "\n"; - - return true; -} - -bool APT::Solver::AddWork(Work &&w) -{ - if (w.clause->negative) - { - for (auto var : w.clause->solutions) - if (not Enqueue(var, false, w.clause)) - return false; - } - else - { - if (unlikely(debug >= 3 && w.clause->optional)) - std::cerr << "Enqueuing Recommends " << w.clause->toString(cache) << std::endl; - if (w.clause->solutions.size() == 1 && not w.clause->optional) - return Enqueue(w.clause->solutions[0], true, w.clause); - - 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()); - } - return true; -} - -bool APT::Solver::Solve() -{ - _error->PushToStack(); - DEFER([&]() { _error->MergeWithStack(); }); - startTime = time(nullptr); - while (true) - { - while (not Propagate()) - { - if (not Pop()) - return false; - } - - if (work.empty()) - break; - - // *NOW* we can pop the item. - std::pop_heap(work.begin(), work.end()); - - // This item has been replaced with a new one. Remove it. - if (work.back().erased) - { - work.pop_back(); - continue; - } - auto item = std::move(work.back()); - work.pop_back(); - solved.push_back(Solved{Var(), item}); - - if (std::any_of(item.clause->solutions.begin(), item.clause->solutions.end(), [this](auto ver) - { return (*this)[ver].decision == Decision::MUST; })) - { - if (unlikely(debug >= 2)) - std::cerr << "ELIDED " << item.toString(cache) << std::endl; - continue; - } - - if (unlikely(debug >= 1)) - std::cerr << item.toString(cache) << std::endl; - - bool foundSolution = false; - for (auto &sol : item.clause->solutions) - { - if ((*this)[sol].decision == Decision::MUSTNOT) - { - if (unlikely(debug >= 3)) - std::cerr << "(existing conflict: " << sol.toString(cache) << ")\n"; - continue; - } - if (item.size > 1 || item.clause->optional) - { - Push(sol, item); - } - if (unlikely(debug >= 3)) - std::cerr << "(try it: " << sol.toString(cache) << ")\n"; - if (not Enqueue(sol, true, item.clause) && not Pop()) - return false; - foundSolution = true; - break; - } - if (not foundSolution && not item.clause->optional) - { - std::ostringstream err; - - err << "Unable to satisfy dependencies. Reached two conflicting decisions:" << "\n"; - std::unordered_set<Var> seen; - err << "1. " << LongWhyStr(item.clause->reason, true, (*this)[item.clause->reason].reason, " ", seen).substr(3) << "\n"; - err << "2. " << LongWhyStr(item.clause->reason, false, item.clause, " ", seen).substr(3); - _error->Error("%s", err.str().c_str()); - if (not Pop()) - return false; - } - } - - return true; -} - // \brief Apply the selections from the dep cache to the solver -bool APT::Solver::FromDepCache(pkgDepCache &depcache) +bool DependencySolver::FromDepCache(pkgDepCache &depcache) { DefaultRootSetFunc2 rootSet(&cache); std::vector<Var> manualPackages; @@ -1195,7 +1186,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache) bool isPhasing = IsUpgrade && depcache.PhasingApplied(P) && not isForced; for (auto V = P.VersionList(); not V.end(); ++V) if (P.CurrentVer() != V && (depcache.GetCandidateVersion(P) != V || isPhasing)) - if (not Enqueue(Var(V), false, {})) + if (not Enqueue(~Var(V), {})) return false; } } @@ -1215,7 +1206,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache) { if (unlikely(debug >= 1)) std::cerr << "Hold " << P.FullName() << "\n"; - if (P->CurrentVer ? not Enqueue(Var(P.CurrentVer()), true) : not Enqueue(Var(P), false)) + if (P->CurrentVer ? not Enqueue(Var(P.CurrentVer())) : not Enqueue(~Var(P))) return false; } else if (state.Delete() // Normal delete request. @@ -1225,7 +1216,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache) { if (unlikely(debug >= 1)) std::cerr << "Delete " << P.FullName() << "\n"; - if (not Enqueue(Var(P), false)) + if (not Enqueue(~Var(P))) return false; } else if (state.Install() || (state.Keep() && P->CurrentVer)) @@ -1251,7 +1242,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache) if (not isOptional) { // Pre-empt the non-optional requests, as we don't want to queue them, we can just "unit propagate" here. - if (depcache[P].Keep() ? not Enqueue(Var(P), true) : not Enqueue(Var(depcache.GetCandidateVersion(P)), true)) + if (depcache[P].Keep() ? not Enqueue(Var(P)) : not Enqueue(Var(depcache.GetCandidateVersion(P)))) return false; } else @@ -1259,7 +1250,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache) Clause w{Var(), Group, isOptional}; w.solutions.push_back(Var(P)); auto insertedW = RegisterClause(std::move(w)); - if (insertedW && not AddWork(Work{insertedW, depth()})) + if (insertedW && not AddWork(Work{insertedW, decisionLevel()})) return false; if (not isAuto) @@ -1275,7 +1266,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache) shortcircuit.solutions.push_back(Var(V)); std::stable_sort(shortcircuit.solutions.begin(), shortcircuit.solutions.end(), CompareProviders3{cache, policy, P, *this}); auto insertedShort = RegisterClause(std::move(shortcircuit)); - if (insertedShort && not AddWork(Work{insertedShort, depth()})) + if (insertedShort && not AddWork(Work{insertedShort, decisionLevel()})) return false; // Discovery here is needed so the shortcircuit clause can actually become unit. @@ -1294,7 +1285,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache) if (unlikely(debug >= 1)) std::cerr << "Install essential package " << P << std::endl; auto inserted = RegisterClause(std::move(w)); - if (inserted && not AddWork(Work{inserted, depth()})) + if (inserted && not AddWork(Work{inserted, decisionLevel()})) return false; } } @@ -1305,15 +1296,14 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache) std::stable_sort(manualPackages.begin(), manualPackages.end(), CompareProviders3{cache, policy, {}, *this}); for (auto assumption : manualPackages) { - if (not Assume(assumption, true, {}) || not Propagate()) - if (not Pop()) - abort(); + if (not Assume(assumption, {}) || not Propagate()) + must_succeed(Pop()); } return true; } -bool APT::Solver::ToDepCache(pkgDepCache &depcache) const +bool DependencySolver::ToDepCache(pkgDepCache &depcache) const { FastContiguousCacheMap<pkgCache::Package, bool> movedManual(cache); pkgDepCache::ActionGroup group(depcache); @@ -1321,11 +1311,11 @@ bool APT::Solver::ToDepCache(pkgDepCache &depcache) const { depcache[P].Marked = 0; depcache[P].Garbage = 0; - if ((*this)[P].decision == Decision::MUST) + if (value(Var(P)) == LiftedBool::True) { pkgCache::VerIterator cand; for (auto V = P.VersionList(); cand.end() && not V.end(); V++) - if ((*this)[V].decision == Decision::MUST) + if (value(Var(V)) == LiftedBool::True) cand = V; auto reasonClause = (*this)[cand].reason; @@ -1379,9 +1369,9 @@ bool APT::Solver::ToDepCache(pkgDepCache &depcache) const } // Command-line -std::string APT::Solver::InternalCliWhy(pkgDepCache &cache, pkgCache::PkgIterator pkg, bool decision) +std::string DependencySolver::InternalCliWhy(pkgDepCache &cache, pkgCache::PkgIterator pkg, bool assignment) { - APT::Solver solver(cache.GetCache(), cache.GetPolicy(), EDSP::Request::Flags(0)); + DependencySolver solver(cache.GetCache(), cache.GetPolicy(), EDSP::Request::Flags(0)); // In case nothing has a positive dependency on pkg it may not actually be discovered in a `why-not` // scenario, so make sure we discover it explicitly. solver.Discover(Var(pkg)); @@ -1389,11 +1379,12 @@ std::string APT::Solver::InternalCliWhy(pkgDepCache &cache, pkgCache::PkgIterato return ""; std::unordered_set<Var> seen; std::string buf; - if (solver[Var(pkg)].decision == Decision::NONE) + if (solver[Var(pkg)].assignment == LiftedBool::Undefined) return strprintf(buf, "%s is undecided\n", pkg.FullName().c_str()), buf; - if (decision && solver[Var(pkg)].decision != Decision::MUST) + if (assignment && solver[Var(pkg)].assignment != LiftedBool::True) return strprintf(buf, "%s is not actually marked for install\n", pkg.FullName().c_str()), buf; - if (not decision && solver[Var(pkg)].decision == Decision::MUST) + if (not assignment && solver[Var(pkg)].assignment == LiftedBool::True) return strprintf(buf, "%s is actually marked for install\n", pkg.FullName().c_str()), buf; - return solver.LongWhyStr(Var(pkg), decision, solver[Var(pkg)].reason, "", seen); + return solver.LongWhyStr(Var(pkg), assignment, solver[Var(pkg)].reason, "", seen); } +} // namespace APT::Solver |