diff options
Diffstat (limited to 'apt-pkg')
| -rw-r--r-- | apt-pkg/solver3.cc | 468 | ||||
| -rw-r--r-- | apt-pkg/solver3.h | 212 |
2 files changed, 381 insertions, 299 deletions
diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index 73f7fd0c4..ed9beb828 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -43,14 +43,29 @@ struct APT::Solver::CompareProviders3 /*{{{*/ pkgDepCache::Policy &Policy; pkgCache::PkgIterator const Pkg; APT::Solver &Solver; - bool upgrade{_config->FindB("APT::Solver::Upgrade", false)}; - bool operator()(pkgCache::Version *AV, pkgCache::Version *BV) + pkgCache::VerIterator bestVersion(pkgCache::PkgIterator pkg) { - return (*this)(pkgCache::VerIterator(Cache, AV), pkgCache::VerIterator(Cache, BV)); + pkgCache::VerIterator res = pkg.VersionList(); + for (auto v = res; not v.end(); ++v) + res = std::max(res, v, *this); + return res; + } + bool operator()(Var a, Var b) + { + 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 @@ -60,9 +75,9 @@ struct APT::Solver::CompareProviders3 /*{{{*/ return false; // Candidate wins in upgrade scenario - if (upgrade) + if (Solver.IsUpgrade) { - auto Cand = Policy.GetCandidateVer(A); + auto Cand = Solver.GetCandidateVer(A); if (AV == Cand || BV == Cand) return (AV == Cand); } @@ -72,7 +87,7 @@ struct APT::Solver::CompareProviders3 /*{{{*/ return (A.CurrentVer() == AV); // Rest is ordered list, first by priority - if (auto pinA = Policy.GetPriority(AV), pinB = Policy.GetPriority(BV); pinA != pinB) + if (auto pinA = Solver.GetPriority(AV), pinB = Solver.GetPriority(BV); pinA != pinB) return pinA > pinB; // Then by version @@ -81,7 +96,7 @@ struct APT::Solver::CompareProviders3 /*{{{*/ // Try obsolete choices only after exhausting non-obsolete choices such that we install // packages replacing them and don't keep back upgrades depending on the replacement to // keep the obsolete package installed. - if (upgrade) + if (Solver.IsUpgrade) if (auto obsoleteA = Solver.Obsolete(A), obsoleteB = Solver.Obsolete(B); obsoleteA != obsoleteB) return obsoleteB; // Prefer MA:same packages if other architectures for it are installed @@ -182,82 +197,75 @@ class DefaultRootSetFunc2 : public pkgDepCache::DefaultRootSetFunc APT::Solver::Solver(pkgCache &cache, pkgDepCache::Policy &policy) : cache(cache), policy(policy), - pkgStates(cache.Head().PackageCount), - verStates(cache.Head().VersionCount), - pkgObsolete(cache.Head().PackageCount) + rootState(new State), + pkgStates(cache), + verStates(cache), + pkgObsolete(cache), + priorities(cache), + candidates(cache) { - static_assert(sizeof(APT::Solver::State) == 3 * sizeof(int)); + // 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>)); + // Root state is "true". + rootState->decision = Decision::MUST; } // This function determines if a work item is less important than another. bool APT::Solver::Work::operator<(APT::Solver::Work const &b) const { - if ((not optional && size < 2) != (not b.optional && b.size < 2)) - return not b.optional && b.size < 2; - if (group != b.group) - return group > b.group; - if (optional && b.optional) - { - if ((size < 2) != (b.size < 2)) - return b.size < 2; - if (reason.empty() != b.reason.empty()) - return reason.empty(); - } - // An optional item is less important than a required one. - if (optional != b.optional) - return optional; - // We enqueue common dependencies at the package level to avoid choosing versions, so let's solve package items first, - // this improves the implication graph as it now tells you that common dependencies were installed by the package. - if (reason.Pkg() != b.reason.Pkg()) - return reason.Pkg() == 0; - + if ((not clause->optional && size < 2) != (not b.clause->optional && b.size < 2)) + return not b.clause->optional && b.size < 2; + if (clause->optional != b.clause->optional) + return clause->optional; + if (clause->group != b.clause->group) + return clause->group > b.clause->group; + if ((size < 2) != (b.size < 2)) + return b.size < 2; + if (size == 1 && b.size == 1) // Special case: 'shortcircuit' optional packages + return clause->solutions.size() < b.clause->solutions.size(); return false; } -void APT::Solver::Work::Dump(pkgCache &cache) +std::string APT::Solver::Clause::toString(pkgCache &cache) const { - if (erased) - std::cerr << "Erased "; - if (optional) - std::cerr << "Optional "; - std::cerr << "Item (" << ssize_t(size <= solutions.size() ? size : -1) << "@" << depth << (upgrade ? "u" : "") << ") "; + std::string out; if (auto Pkg = reason.Pkg(cache); not Pkg.end()) - std::cerr << Pkg.FullName(); + out.append(Pkg.FullName()); if (auto Ver = reason.Ver(cache); not Ver.end()) - std::cerr << Ver.ParentPkg().FullName() << "=" << Ver.VerStr(); - std::cerr << " -> "; - for (auto sol : solutions) - { - auto Ver = pkgCache::VerIterator(cache, sol); - std::cerr << " | " << Ver.ParentPkg().FullName() << "=" << Ver.VerStr(); - } + out.append(Ver.ParentPkg().FullName()).append("=").append(Ver.VerStr()); + out.append(" -> "); + for (auto var : solutions) + out.append(" | ").append(var.toString(cache)); + return out; +} + +std::string APT::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 << clause->toString(cache); + return out.str(); } // Prints an implication graph part of the form A -> B -> C, possibly with "not" -std::string APT::Solver::WhyStr(Var reason) +std::string APT::Solver::WhyStr(Var reason) const { std::vector<std::string> out; while (not reason.empty()) { - if (auto Pkg = reason.Pkg(cache); not Pkg.end()) - { - if ((*this)[Pkg].decision == Decision::MUSTNOT) - out.push_back(std::string("not ") + Pkg.FullName()); - else - out.push_back(Pkg.FullName()); - reason = (*this)[Pkg].reason; - } - if (auto Ver = reason.Ver(cache); not Ver.end()) - { - if ((*this)[Ver].decision == Decision::MUSTNOT) - out.push_back(std::string("not ") + Ver.ParentPkg().FullName() + "=" + Ver.VerStr()); - else - out.push_back(Ver.ParentPkg().FullName() + "=" + Ver.VerStr()); - reason = (*this)[Ver].reason; - } + if ((*this)[reason].decision == Decision::MUSTNOT) + out.push_back(std::string("not ") + reason.toString(cache)); + else + out.push_back(reason.toString(cache)); + reason = (*this)[reason].reason; } std::string outstr; @@ -274,7 +282,7 @@ std::string APT::Solver::WhyStr(Var reason) bool APT::Solver::ObsoletedByNewerSourceVersion(pkgCache::VerIterator cand) const { const auto pkg = cand.ParentPkg(); - const int candPriority = policy.GetPriority(cand); + const int candPriority = GetPriority(cand); for (auto ver = cand.Cache()->FindGrp(cand.SourcePkgName()).VersionsInSource(); not ver.end(); ver = ver.NextInSource()) { @@ -283,11 +291,11 @@ bool APT::Solver::ObsoletedByNewerSourceVersion(pkgCache::VerIterator cand) cons continue; // We also take equal priority here, given that we have a higher version - const int priority = policy.GetPriority(ver, true); + const int priority = GetPriority(ver); if (priority == 0 || priority < candPriority) continue; - pkgObsolete[pkg->ID] = 2; + pkgObsolete[pkg] = 2; if (debug >= 3) std::cerr << "Obsolete: " << cand.ParentPkg().FullName() << "=" << cand.VerStr() << " due to " << ver.ParentPkg().FullName() << "=" << ver.VerStr() << "\n"; return true; @@ -298,10 +306,10 @@ bool APT::Solver::ObsoletedByNewerSourceVersion(pkgCache::VerIterator cand) cons bool APT::Solver::Obsolete(pkgCache::PkgIterator pkg) const { - if (pkgObsolete[pkg->ID] != 0) - return pkgObsolete[pkg->ID] == 2; + if (pkgObsolete[pkg] != 0) + return pkgObsolete[pkg] == 2; - auto ver = policy.GetCandidateVer(pkg); + auto ver = GetCandidateVer(pkg); if (ver.end() && not StrictPinning) ver = pkg.VersionList(); @@ -309,7 +317,7 @@ bool APT::Solver::Obsolete(pkgCache::PkgIterator pkg) const { if (debug >= 3) std::cerr << "Obsolete: " << pkg.FullName() << " - not installable\n"; - pkgObsolete[pkg->ID] = 2; + pkgObsolete[pkg] = 2; return true; } @@ -319,12 +327,12 @@ bool APT::Solver::Obsolete(pkgCache::PkgIterator pkg) const for (auto file = ver.FileList(); !file.end(); file++) if ((file.File()->Flags & pkgCache::Flag::NotSource) == 0) { - pkgObsolete[pkg->ID] = 1; + pkgObsolete[pkg] = 1; return false; } if (debug >= 3) std::cerr << "Obsolete: " << ver.ParentPkg().FullName() << "=" << ver.VerStr() << " - not installable\n"; - pkgObsolete[pkg->ID] = 2; + pkgObsolete[pkg] = 2; return true; } bool APT::Solver::Assume(Var var, bool decision, Var reason) @@ -367,62 +375,59 @@ bool APT::Solver::Propagate() { Var var = propQ.front(); propQ.pop(); - if ((*this)[var].decision == Decision::MUST && not PropagateInstall(var)) - return false; + if ((*this)[var].decision == Decision::MUST) + { + Discover(var); + for (auto &clause : (*this)[var].clauses) + if (not AddWork(Work{clause.get(), depth()})) + return false; + } else if ((*this)[var].decision == Decision::MUSTNOT && not PropagateReject(var)) return false; } return true; } -bool APT::Solver::PropagateInstall(Var var) +void APT::Solver::RegisterClause(Clause &&clause) +{ + auto &clauses = (*this)[clause.reason].clauses; + clauses.push_back(std::make_unique<Clause>(std::move(clause))); +} + +void APT::Solver::Discover(Var var) { + auto &state = (*this)[var]; + + if (state.flags.discovered) + return; + + state.flags.discovered = true; + if (auto Pkg = var.Pkg(cache); not Pkg.end()) { - bool anyInstallable = false; - bool anyMust = false; - // Insert the work item. - Work workItem{Var(Pkg), depth(), Group::SelectVersion}; + Clause clause{Var(Pkg), Group::SelectVersion}; for (auto ver = Pkg.VersionList(); not ver.end(); ver++) - { - workItem.solutions.push_back(ver); - if ((*this)[ver].decision != Decision::MUSTNOT) - anyInstallable = true; - if ((*this)[ver].decision == Decision::MUST) - anyMust = true; - } - - if (not anyInstallable) - { - _error->Error("Conflict: %s -> %s but no versions are installable", - WhyStr((*this)[Pkg].reason).c_str(), Pkg.FullName().c_str()); - for (auto ver = Pkg.VersionList(); not ver.end(); ver++) - _error->Error("Uninstallable version: %s", WhyStr(Var(ver)).c_str()); - return false; - } - - std::stable_sort(workItem.solutions.begin(), workItem.solutions.end(), CompareProviders3{cache, policy, Pkg, *this}); - assert(workItem.solutions.size() > 0); + clause.solutions.push_back(Var(ver)); - if (workItem.solutions.size() > 1 || workItem.optional) - AddWork(std::move(workItem)); - else if (not Enqueue(Var(pkgCache::VerIterator(cache, workItem.solutions[0])), true, workItem.reason)) - return false; + std::stable_sort(clause.solutions.begin(), clause.solutions.end(), CompareProviders3{cache, policy, Pkg, *this}); + RegisterClause(std::move(clause)); - // FIXME: We skip enqueuing duplicate common dependencies if we already selected a version, but - // we should not have common dependencies duplicated in the version objects anyway. - if (not anyMust && not EnqueueCommonDependencies(Pkg)) - return false; + RegisterCommonDependencies(Pkg); } else if (auto Ver = var.Ver(cache); not Ver.end()) { - if (not Enqueue(Var(Ver.ParentPkg()), true, Var(Ver))) - return false; + Clause clause{Var(Ver), Group::SelectVersion}; + clause.solutions = {Var(Ver.ParentPkg())}; + RegisterClause(std::move(clause)); for (auto OV = Ver.ParentPkg().VersionList(); not OV.end(); ++OV) { - if (OV != Ver && not Enqueue(Var(OV), false, Var(Ver))) - return false; + if (OV == Ver) + continue; + + Clause clause{Var(Ver), Group::SelectVersion, false, true /* negative */}; + clause.solutions = {Var(OV)}; + RegisterClause(std::move(clause)); } for (auto dep = Ver.DependsList(); not dep.end();) @@ -432,12 +437,11 @@ bool APT::Solver::PropagateInstall(Var var) pkgCache::DepIterator end; dep.GlobOr(start, end); // advances dep - if (not EnqueueOrGroup(start, end, Var(Ver))) - return false; + auto clause = TranslateOrGroup(start, end, Var(Ver)); + + RegisterClause(std::move(clause)); } } - - return true; } bool APT::Solver::PropagateReject(Var var) @@ -477,10 +481,8 @@ bool APT::Solver::PropagateReject(Var var) return true; } -bool APT::Solver::EnqueueCommonDependencies(pkgCache::PkgIterator Pkg) +void APT::Solver::RegisterCommonDependencies(pkgCache::PkgIterator Pkg) { - if (not _config->FindB("APT::Solver::Enqueue-Common-Dependencies", true)) - return false; for (auto dep = Pkg.VersionList().DependsList(); not dep.end();) { pkgCache::DepIterator start; @@ -498,79 +500,66 @@ bool APT::Solver::EnqueueCommonDependencies(pkgCache::PkgIterator Pkg) } if (not allHaveDep) continue; - if (not EnqueueOrGroup(start, end, Var(Pkg))) - return false; + auto clause = TranslateOrGroup(start, end, Var(Pkg)); + RegisterClause(std::move(clause)); } - - return true; } -bool APT::Solver::EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepIterator end, Var reason) +APT::Solver::Clause APT::Solver::TranslateOrGroup(pkgCache::DepIterator start, pkgCache::DepIterator end, Var reason) { auto TgtPkg = start.TargetPkg(); auto Ver = start.ParentVer(); - auto fixPolicy = _config->FindB("APT::Get::Fix-Policy-Broken"); // Non-important dependencies can only be installed if they are currently satisfied, see the check further // below once we have calculated all possible solutions. if (start.ParentPkg()->CurrentVer == 0 && not policy.IsImportantDep(start)) - return true; + return Clause{reason, Group::Satisfy, true}; // Replaces and Enhances are not a real dependency. if (start->Type == pkgCache::Dep::Replaces || start->Type == pkgCache::Dep::Enhances) - return true; + return Clause{reason, Group::Satisfy, true}; if (unlikely(debug >= 3)) std::cerr << "Found dependency critical " << Ver.ParentPkg().FullName() << "=" << Ver.VerStr() << " -> " << start.TargetPkg().FullName() << "\n"; - Work workItem{reason, depth(), Group::Satisfy, not start.IsCritical() /* optional */}; + Clause clause{reason, Group::Satisfy, not start.IsCritical() /* optional */, start.IsNegative()}; + + clause.dep = start; do { - auto begin = workItem.solutions.size(); + auto begin = clause.solutions.size(); auto all = start.AllTargets(); for (auto tgt = all; *tgt; ++tgt) { pkgCache::VerIterator tgti(cache, *tgt); - - if (start.IsNegative()) - { - if (unlikely(debug >= 3)) - std::cerr << "Reject: " << Ver.ParentPkg().FullName() << "=" << Ver.VerStr() << " -> " << tgti.ParentPkg().FullName() << "=" << tgti.VerStr() << "\n"; - // FIXME: We should be collecting these and marking the heap only once. - if (not Enqueue(Var(pkgCache::VerIterator(cache, *tgt)), false, Var(Ver))) - return false; - } - else - { - if (unlikely(debug >= 3)) - std::cerr << "Adding work to item " << Ver.ParentPkg().FullName() << "=" << Ver.VerStr() << " -> " << tgti.ParentPkg().FullName() << "=" << tgti.VerStr() << "\n"; - workItem.solutions.push_back(*tgt); - } + if (unlikely(debug >= 3)) + std::cerr << "Adding work to item " << reason.toString(cache) << " -> " << tgti.ParentPkg().FullName() << "=" << tgti.VerStr() << (clause.negative ? " (negative)" : "") << "\n"; + clause.solutions.push_back(Var(pkgCache::VerIterator(cache, *tgt))); } delete[] all; // If we are fixing the policy, we need to sort each alternative in an or group separately // FIXME: This is not really true, though, we should fix the CompareProviders to ignore the // installed state - if (fixPolicy) - std::stable_sort(workItem.solutions.begin() + begin, workItem.solutions.end(), CompareProviders3{cache, policy, TgtPkg, *this}); + if (FixPolicyBroken) + std::stable_sort(clause.solutions.begin() + begin, clause.solutions.end(), CompareProviders3{cache, policy, TgtPkg, *this}); if (start == end) break; ++start; } while (1); - if (not fixPolicy) - std::stable_sort(workItem.solutions.begin(), workItem.solutions.end(), CompareProviders3{cache, policy, TgtPkg, *this}); + if (not FixPolicyBroken) + std::stable_sort(clause.solutions.begin(), clause.solutions.end(), CompareProviders3{cache, policy, TgtPkg, *this}); - if (std::all_of(workItem.solutions.begin(), workItem.solutions.end(), [this](auto V) -> auto - { return pkgCache::VerIterator(cache, V).ParentPkg()->CurrentVer == 0; })) - workItem.group = Group::SatisfyNew; - if (std::any_of(workItem.solutions.begin(), workItem.solutions.end(), [this](auto V) -> auto - { return Obsolete(pkgCache::VerIterator(cache, V).ParentPkg()); })) - workItem.group = Group::SatisfyObsolete; + if (std::all_of(clause.solutions.begin(), clause.solutions.end(), [this](auto var) -> auto + { return var.CastPkg(cache)->CurrentVer == 0; })) + clause.group = Group::SatisfyNew; + if (std::any_of(clause.solutions.begin(), clause.solutions.end(), [this](auto var) -> auto + { return Obsolete(var.CastPkg(cache)); })) + clause.group = Group::SatisfyObsolete; // Try to perserve satisfied Recommends. FIXME: We should check if the Recommends was there in the installed version? - if (workItem.optional && start.ParentPkg()->CurrentVer) + if (clause.optional && start.ParentPkg()->CurrentVer) { bool important = policy.IsImportantDep(start); bool newOptional = true; @@ -579,60 +568,30 @@ bool APT::Solver::EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepItera if (not D.IsCritical() && not D.IsNegative() && D.TargetPkg() == start.TargetPkg()) newOptional = false, wasImportant = policy.IsImportantDep(D); - bool satisfied = std::any_of(workItem.solutions.begin(), workItem.solutions.end(), [this](auto ver) - { return pkgCache::VerIterator(cache, ver).ParentPkg().CurrentVer() == ver; }); + bool satisfied = std::any_of(clause.solutions.begin(), clause.solutions.end(), [this](auto var) + { return Var(var.CastPkg(cache).CurrentVer()) == var; }); if (important && wasImportant && not newOptional && not satisfied) { if (unlikely(debug >= 3)) - { - std::cerr << "Ignoring unsatisfied Recommends "; - workItem.Dump(cache); - std::cerr << "\n"; - } - return true; + std::cerr << "Ignoring unsatisfied Recommends " << clause.toString(cache) << std::endl; + clause.solutions.clear(); } - if (not important && not wasImportant && not newOptional && satisfied) + else if (not important && not wasImportant && not newOptional && satisfied) { if (unlikely(debug >= 3)) - { - std::cerr << "Promoting satisfied Suggests to Recommends: "; - workItem.Dump(cache); - std::cerr << "\n"; - } + std::cerr << "Promoting satisfied Suggests to Recommends: " << clause.toString(cache) << std::endl; important = true; } - if (not important) + else if (not important) { if (unlikely(debug >= 3)) - { - std::cerr << "Ignoring Suggests "; - workItem.Dump(cache); - std::cerr << "\n"; - } - return true; + std::cerr << "Ignoring Suggests " << clause.toString(cache) << std::endl; + return Clause{reason, Group::Satisfy, true}; } } - if (not workItem.solutions.empty()) - { - // std::stable_sort(workItem.solutions.begin(), workItem.solutions.end(), CompareProviders3{cache, TgtPkg}); - if (unlikely(debug >= 3 && workItem.optional)) - { - std::cerr << "Enqueuing Recommends "; - workItem.Dump(cache); - std::cerr << "\n"; - } - if (workItem.optional || workItem.solutions.size() > 1) - AddWork(std::move(workItem)); - else if (not Enqueue(Var(pkgCache::VerIterator(cache, workItem.solutions[0])), true, reason)) - return false; - } - else if (start.IsCritical() && not start.IsNegative()) - { - return _error->Error("Unsatisfiable dependency group %s=%s -> %s", Ver.ParentPkg().FullName().c_str(), Ver.VerStr(), TgtPkg.FullName().c_str()); - } - return true; + return clause; } // \brief Find the or group containing the given dependency. @@ -705,11 +664,7 @@ bool APT::Solver::RejectReverseDependencies(pkgCache::VerIterator Ver) void APT::Solver::Push(Work work) { if (unlikely(debug >= 2)) - { - std::cerr << "Trying choice for "; - work.Dump(cache); - std::cerr << "\n"; - } + std::cerr << "Trying choice for " << work.toString(cache) << std::endl; choices.push_back(solved.size()); solved.push_back(Solved{Var(), std::move(work)}); @@ -742,13 +697,10 @@ void APT::Solver::UndoOne() if (auto work = solvedItem.work) { if (unlikely(debug >= 4)) - { - std::cerr << "Adding work item "; - work->Dump(cache); - std::cerr << "\n"; - } + std::cerr << "Adding work item " << work->toString(cache) << std::endl; - AddWork(std::move(*work)); + if (not AddWork(std::move(*work))) + abort(); } solved.pop_back(); @@ -769,7 +721,7 @@ bool APT::Solver::Pop() assert(choices.back() < solved.size()); int itemsToUndo = solved.size() - choices.back(); - pkgCache::VerIterator choice(cache, solved[choices.back()].work->choice); + auto choice = solved[choices.back()].work->choice; for (; itemsToUndo; --itemsToUndo) UndoOne(); @@ -784,24 +736,43 @@ bool APT::Solver::Pop() std::make_heap(work.begin(), work.end()); if (unlikely(debug >= 2)) - std::cerr << "Backtracking to choice " << choice.ParentPkg().FullName() << "=" << choice.VerStr() << "\n"; + std::cerr << "Backtracking to choice " << choice.toString(cache) << "\n"; // FIXME: There should be a reason! - if (not Enqueue(Var(choice), false, {})) + if (not Enqueue(choice, false, {})) return false; if (unlikely(debug >= 2)) - std::cerr << "Backtracked to choice " << choice.ParentPkg().FullName() << "=" << choice.VerStr() << "\n"; + std::cerr << "Backtracked to choice " << choice.toString(cache) << "\n"; return true; } -void APT::Solver::AddWork(Work &&w) +bool APT::Solver::AddWork(Work &&w) { - w.size = std::count_if(w.solutions.begin(), w.solutions.end(), [this](auto V) - { return (*this)[V].decision != Decision::MUSTNOT; }); - work.push_back(std::move(w)); - std::push_heap(work.begin(), work.end()); + if (w.clause->negative) + { + for (auto var : w.clause->solutions) + if (not Enqueue(var, false, w.clause->reason)) + return false; + } + else if (not w.clause->solutions.empty()) + { + if (unlikely(debug >= 3 && w.clause->optional)) + std::cerr << "Enqueuing Recommends " << w.clause->toString(cache) << std::endl; + if (w.clause->solutions.size() == 1 && not w.clause->optional) + return Enqueue(w.clause->solutions[0], true, w.clause->reason); + + w.size = std::count_if(w.clause->solutions.begin(), w.clause->solutions.end(), [this](auto V) + { return (*this)[V].decision != Decision::MUSTNOT; }); + work.push_back(std::move(w)); + std::push_heap(work.begin(), work.end()); + } + else if (not w.clause->optional && w.clause->dep) + return _error->Error("Unsatisfiable dependency group %s -> %s", w.clause->reason.toString(cache).c_str(), pkgCache::DepIterator(cache, w.clause->dep).TargetPkg().FullName().c_str()); + else if (not w.clause->optional) + return _error->Error("Unsatisfiable dependency group %s", w.clause->reason.toString(cache).c_str()); + return true; } void APT::Solver::RescoreWorkIfNeeded() @@ -815,7 +786,7 @@ void APT::Solver::RescoreWorkIfNeeded() { if (w.erased) continue; - size_t newSize = std::count_if(w.solutions.begin(), w.solutions.end(), [this](auto V) + size_t newSize = std::count_if(w.clause->solutions.begin(), w.clause->solutions.end(), [this](auto V) { return (*this)[V].decision != Decision::MUSTNOT; }); // Notably we only insert the work into the queue if it got smaller. Work that got larger @@ -864,7 +835,7 @@ bool APT::Solver::Solve() } // If our size increased, queue again. - size_t newSize = std::count_if(work.back().solutions.begin(), work.back().solutions.end(), [this](auto V) + size_t newSize = std::count_if(work.back().clause->solutions.begin(), work.back().clause->solutions.end(), [this](auto V) { return (*this)[V].decision != Decision::MUSTNOT; }); if (newSize > work.back().size) @@ -879,60 +850,51 @@ bool APT::Solver::Solve() work.pop_back(); solved.push_back(Solved{Var(), item}); - if (std::any_of(item.solutions.begin(), item.solutions.end(), [this](auto ver) + if (std::any_of(item.clause->solutions.begin(), item.clause->solutions.end(), [this](auto ver) { return (*this)[ver].decision == Decision::MUST; })) { if (unlikely(debug >= 2)) - { - std::cerr << "ELIDED "; - item.Dump(cache); - std::cerr << "\n"; - } + std::cerr << "ELIDED " << item.toString(cache) << std::endl; continue; } if (unlikely(debug >= 1)) - { - item.Dump(cache); - std::cerr << "\n"; - } + std::cerr << item.toString(cache) << std::endl; - assert(item.solutions.size() > 1 || item.optional); + assert(item.clause->solutions.size() > 1 || item.clause->optional); bool foundSolution = false; - for (auto &sol : item.solutions) + for (auto &sol : item.clause->solutions) { - pkgCache::VerIterator ver(cache, sol); - if ((*this)[ver].decision == Decision::MUSTNOT) + if ((*this)[sol].decision == Decision::MUSTNOT) { if (unlikely(debug >= 3)) - std::cerr << "(existing conflict: " << ver.ParentPkg().FullName() << "=" << ver.VerStr() << ")\n"; + std::cerr << "(existing conflict: " << sol.toString(cache) << ")\n"; continue; } - if (item.size > 1 || item.optional) + if (item.size > 1 || item.clause->optional) { - item.choice = ver; + item.choice = sol; Push(item); } if (unlikely(debug >= 3)) - std::cerr << "(try it: " << ver.ParentPkg().FullName() << "=" << ver.VerStr() << ")\n"; - if (not Enqueue(Var(ver), true, item.reason) && not Pop()) + std::cerr << "(try it: " << sol.toString(cache) << ")\n"; + if (not Enqueue(sol, true, item.clause->reason) && not Pop()) return false; foundSolution = true; break; } - if (not foundSolution && not item.optional) + if (not foundSolution && not item.clause->optional) { std::ostringstream dep; - assert(item.solutions.size() > 0); - for (auto &sol : item.solutions) - dep << (dep.tellp() == 0 ? "" : " | ") << pkgCache::VerIterator(cache, sol).ParentPkg().FullName() << "=" << pkgCache::VerIterator(cache, sol).VerStr(); - _error->Error("Unsatisfiable dependency: %s -> %s", WhyStr(item.reason).c_str(), dep.str().c_str()); - for (auto &sol : item.solutions) + assert(item.clause->solutions.size() > 0); + for (auto &sol : item.clause->solutions) + dep << (dep.tellp() == 0 ? "" : " | ") << sol.toString(cache); + _error->Error("Unsatisfiable dependency: %s -> %s", WhyStr(item.clause->reason).c_str(), dep.str().c_str()); + for (auto &sol : item.clause->solutions) if ((*this)[sol].decision == Decision::MUSTNOT) - _error->Error("Not considered: %s=%s: %s", pkgCache::VerIterator(cache, sol).ParentPkg().FullName().c_str(), - pkgCache::VerIterator(cache, sol).VerStr(), - WhyStr(Var(pkgCache::VerIterator(cache, sol))).c_str()); + _error->Error("Not considered: %s: %s", sol.toString(cache).c_str(), + WhyStr(sol).c_str()); if (not Pop()) return false; } @@ -944,7 +906,6 @@ bool APT::Solver::Solve() // \brief Apply the selections from the dep cache to the solver bool APT::Solver::FromDepCache(pkgDepCache &depcache) { - bool AllowRemoveManual = AllowRemove && _config->FindB("APT::Solver::RemoveManual", false); DefaultRootSetFunc2 rootSet(&cache); // Enforce strict pinning rules by rejecting all forbidden versions. @@ -1011,11 +972,24 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache) } else { - Work w{Var(), depth(), Group, isOptional, Upgrade}; + Clause w{Var(), Group, isOptional}; + w.solutions.push_back(Var(P)); + RegisterClause(std::move(w)); + if (not AddWork(Work{rootState->clauses.back().get(), depth()})) + return false; + + // Given A->A2|A1, B->B1|B2; Bn->An, if we select `not A1`, we + // should try to install A2 before trying B so we end up with + // A2, B2, instead of removing A1 to keep B1 installed. This + // requires some special casing in Work::operator< above. + // Compare test-bug-712116-dpkg-pre-install-pkgs-hook-multiarch + Clause shortcircuit{Var(), Group, isOptional}; for (auto V = P.VersionList(); not V.end(); ++V) - w.solutions.push_back(V); - std::stable_sort(w.solutions.begin(), w.solutions.end(), CompareProviders3{cache, policy, P, *this}); - AddWork(std::move(w)); + shortcircuit.solutions.push_back(Var(V)); + std::stable_sort(shortcircuit.solutions.begin(), shortcircuit.solutions.end(), CompareProviders3{cache, policy, P, *this}); + RegisterClause(std::move(shortcircuit)); + if (not AddWork(Work{rootState->clauses.back().get(), depth()})) + return false; } } } @@ -1023,7 +997,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache) return Propagate(); } -bool APT::Solver::ToDepCache(pkgDepCache &depcache) +bool APT::Solver::ToDepCache(pkgDepCache &depcache) const { pkgDepCache::ActionGroup group(depcache); for (auto P = cache.PkgBegin(); not P.end(); P++) diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h index 4f6f83d15..65cd9f017 100644 --- a/apt-pkg/solver3.h +++ b/apt-pkg/solver3.h @@ -7,6 +7,7 @@ * SPDX-License-Identifier: GPL-2.0+ */ +#include <cassert> #include <optional> #include <queue> #include <vector> @@ -19,6 +20,48 @@ namespace APT { +/** + * \brief A simple mapping from objects in the cache to user-defined types. + * + * This default initializes an array with the specified value type for each + * object in the cache of that type. + */ +template <typename K, typename V, bool fast = false> +class ContiguousCacheMap +{ + V *data_; // Avoid std::unique_ptr() as it may check that it's non-null. + + public: + ContiguousCacheMap(pkgCache &cache) + { + static_assert(std::is_constructible_v<V>); + if constexpr (fast) + { + static_assert(std::is_trivially_constructible_v<V>); + static_assert(std::is_trivially_destructible_v<V>); + } + + size_t size; + if constexpr (std::is_same_v<K, pkgCache::Version>) + size = cache.Head().VersionCount; + else if constexpr (std::is_same_v<K, pkgCache::Package>) + size = cache.Head().PackageCount; + else + static_assert(false, "Cannot construct map for key type"); + + data_ = new V[size]{}; + } + V &operator[](const K *key) { return data_[key->ID]; } + const V &operator[](const K *key) const { return data_[key->ID]; } + ~ContiguousCacheMap() { delete[] data_; } +}; + +/** + * \brief A version of ContiguousCacheMap that ensures allocation and deallocation is trivial. + */ +template <typename K, typename V> +using FastContiguousCacheMap = ContiguousCacheMap<K, V, true>; + /* * \brief APT 3.0 solver * @@ -36,6 +79,7 @@ class Solver struct Var; struct CompareProviders3; struct State; + struct Clause; struct Work; struct Solved; @@ -91,29 +135,56 @@ class Solver pkgCache &cache; // Policy is needed for determining candidate version. pkgDepCache::Policy &policy; + // Root state + std::unique_ptr<State> rootState; // States for packages - std::vector<State> pkgStates{}; + ContiguousCacheMap<pkgCache::Package, State> pkgStates; // States for versions - std::vector<State> verStates{}; + ContiguousCacheMap<pkgCache::Version, State> verStates; // \brief Helper function for safe access to package state. inline State &operator[](pkgCache::Package *P) { - return pkgStates[P->ID]; + return pkgStates[P]; + } + inline const State &operator[](pkgCache::Package *P) const + { + return pkgStates[P]; } // \brief Helper function for safe access to version state. inline State &operator[](pkgCache::Version *V) { - return verStates[V->ID]; + return verStates[V]; + } + inline const State &operator[](pkgCache::Version *V) const + { + return verStates[V]; } // \brief Helper function for safe access to either state. inline State &operator[](Var r); + inline const State &operator[](Var r) const; - mutable std::vector<char> pkgObsolete; + mutable FastContiguousCacheMap<pkgCache::Package, char> pkgObsolete; bool Obsolete(pkgCache::PkgIterator pkg) const; bool ObsoletedByNewerSourceVersion(pkgCache::VerIterator cand) const; + mutable FastContiguousCacheMap<pkgCache::Version, short> priorities; + short GetPriority(pkgCache::VerIterator ver) const + { + if (priorities[ver] == 0) + priorities[ver] = policy.GetPriority(ver); + return priorities[ver]; + } + + mutable ContiguousCacheMap<pkgCache::Package, pkgCache::VerIterator> candidates; + pkgCache::VerIterator GetCandidateVer(pkgCache::PkgIterator pkg) const + { + if (candidates[pkg].end()) + candidates[pkg] = policy.GetCandidateVer(pkg); + return candidates[pkg]; + } + // \brief Heap of the remaining work. // // We are using an std::vector with std::make_heap(), std::push_heap(), @@ -145,25 +216,34 @@ class Solver int debug{_config->FindI("Debug::APT::Solver")}; // \brief If set, we try to keep automatically installed packages installed. bool KeepAuto{not _config->FindB("APT::Get::AutomaticRemove")}; + // \brief Determines if we are in upgrade mode. + bool IsUpgrade{_config->FindB("APT::Solver::Upgrade", false)}; // \brief If set, removals are allowed. bool AllowRemove{_config->FindB("APT::Solver::Remove", true)}; + // \brief If set, removal of manual packages is allowed. + bool AllowRemoveManual{AllowRemove && _config->FindB("APT::Solver::RemoveManual", false)}; // \brief If set, installs are allowed. bool AllowInstall{_config->FindB("APT::Solver::Install", true)}; // \brief If set, we use strict pinning. bool StrictPinning{_config->FindB("APT::Solver::Strict-Pinning", true)}; + // \brief If set, we install missing recommends and pick new best packages. + bool FixPolicyBroken{_config->FindB("APT::Get::Fix-Policy-Broken")}; + // \brief Discover a variable, translating the underlying dependencies to the SAT presentation + void Discover(Var var); + // \brief Link a clause into the watchers + void RegisterClause(Clause &&clause); // \brief Enqueue dependencies shared by all versions of the package. - bool EnqueueCommonDependencies(pkgCache::PkgIterator Pkg); + void RegisterCommonDependencies(pkgCache::PkgIterator Pkg); + // \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, Var reason); + [[nodiscard]] bool RejectReverseDependencies(pkgCache::VerIterator Ver); + // \brief Translate an or group into a clause object + [[nodiscard]] Clause TranslateOrGroup(pkgCache::DepIterator start, pkgCache::DepIterator end, Var reason); // \brief Propagate all pending propagations - bool Propagate(); - // \brief Propagate a "true" value of a variable - bool PropagateInstall(Var var); + [[nodiscard]] bool Propagate(); // \brief Propagate a rejection of a variable - bool PropagateReject(Var var); + [[nodiscard]] bool PropagateReject(Var var); // \brief Return the current depth (choices.size() with casting) depth_type depth() @@ -175,11 +255,11 @@ class Solver // \brief Create a new decision level. void Push(Work work); // \brief Revert to the previous decision level. - bool Pop(); + [[nodiscard]] bool Pop(); // \brief Undo a single assignment / solved work item void UndoOne(); // \brief Add work to our work queue. - void AddWork(Work &&work); + [[nodiscard]] bool AddWork(Work &&work); // \brief Rescore the work after a reject or a pop void RescoreWorkIfNeeded(); @@ -187,20 +267,20 @@ class Solver Solver(pkgCache &Cache, pkgDepCache::Policy &Policy); // Assume that the variable is decided as specified. - bool Assume(Var var, bool decision, Var reason); + [[nodiscard]] bool Assume(Var var, bool decision, Var reason); // Enqueue a decision fact - bool Enqueue(Var var, bool decision, Var reason); + [[nodiscard]] bool Enqueue(Var var, bool decision, Var reason); // \brief Apply the selections from the dep cache to the solver - bool FromDepCache(pkgDepCache &depcache); + [[nodiscard]] bool FromDepCache(pkgDepCache &depcache); // \brief Apply the solver result to the depCache - bool ToDepCache(pkgDepCache &depcache); + [[nodiscard]] bool ToDepCache(pkgDepCache &depcache) const; // \brief Solve the dependencies - bool Solve(); + [[nodiscard]] bool Solve(); // Print dependency chain - std::string WhyStr(Var reason); + std::string WhyStr(Var reason) const; }; }; // namespace APT @@ -242,11 +322,21 @@ struct APT::Solver::Var { return IsVersion ? pkgCache::VerIterator(cache, cache.VerP + Ver()) : pkgCache::VerIterator(); } + // \brief Return a package, cast from version if needed + pkgCache::PkgIterator CastPkg(pkgCache &cache) const + { + assert(MapPtr != 0); + return IsVersion ? Ver(cache).ParentPkg() : Pkg(cache); + } // \brief Check if there is no reason. bool empty() const { return IsVersion == 0 && MapPtr == 0; } + bool operator==(Var const other) + { + return IsVersion == other.IsVersion && MapPtr == other.MapPtr; + } std::string toString(pkgCache &cache) const { @@ -259,6 +349,33 @@ struct APT::Solver::Var }; /** + * \brief A single clause + * + * A clause is a normalized, expanded dependency, translated into an implication + * in terms of Var objects, that is, `reason -> solutions[0] | ... | solutions[n]` + */ +struct APT::Solver::Clause +{ + // \brief Underyling dependency + pkgCache::Dependency *dep = nullptr; + // \brief Var for the work + Var reason; + // \brief The group we are in + Group group; + // \brief Possible solutions to this task, ordered in order of preference. + std::vector<Var> solutions{}; + // \brief An optional clause does not need to be satisfied + bool optional; + + // \brief A negative clause negates the solutions, that is X->A|B you get X->!(A|B), aka X->!A&!B + bool negative; + + inline Clause(Var reason, Group group, bool optional = false, bool negative = false) : reason(reason), group(group), optional(optional), negative(negative) {} + + std::string toString(pkgCache &cache) const; +}; + +/** * \brief A single work item * * A work item is a positive dependency that still needs to be resolved. Work @@ -270,37 +387,27 @@ struct APT::Solver::Var */ struct APT::Solver::Work { - // \brief Var for the work - Var reason; + const Clause *clause; + // \brief The depth at which the item has been added depth_type depth; - // \brief The group we are in - Group group; - // \brief Possible solutions to this task, ordered in order of preference. - std::vector<pkgCache::Version *> solutions{}; // This is a union because we only need to store the choice we made when adding // to the choice vector, and we don't need the size of valid choices in there. union { // The choice we took - pkgCache::Version *choice; + Var choice; // Number of valid choices - size_t size; + size_t size{0}; }; - // \brief Whether this is an optional work item, they will be processed last - bool optional; - // \brief Whether this is an ugprade - bool upgrade; // \brief This item should be removed from the queue. - bool erased; + bool erased{false}; bool operator<(APT::Solver::Work const &b) const; - // \brief Dump the work item to std::cerr - void Dump(pkgCache &cache); - - inline Work(Var reason, depth_type depth, Group group, bool optional = false, bool upgrade = false) : reason(reason), depth(depth), group(group), size(0), optional(optional), upgrade(upgrade), erased(false) {} + std::string toString(pkgCache &cache) const; + inline Work(const Clause *clause, depth_type depth) : clause(clause), depth(depth) {} }; // \brief This essentially describes the install state in RFC2119 terms. @@ -314,17 +421,6 @@ enum class APT::Solver::Decision : uint16_t MUSTNOT, }; -// \brief Hints for the solver about the item. -enum class APT::Solver::Hint : uint16_t -{ - // \brief We have not made a choice about the package yet - NONE, - // \brief This package was listed as a Recommends of a must package, - SHOULD, - // \brief This package was listed as a Suggests of a must-not package - MAY, -}; - /** * \brief The solver state * @@ -352,8 +448,16 @@ struct APT::Solver::State // \brief This essentially describes the install state in RFC2119 terms. Decision decision{Decision::NONE}; - // \brief Any hint. - Hint hint{Hint::NONE}; + // \brief Flags. + struct + { + bool discovered{}; + } flags; + + static_assert(sizeof(flags) <= sizeof(int)); + + // \brief Clauses owned by this package/version + std::vector<std::unique_ptr<Clause>> clauses; }; /** @@ -376,6 +480,10 @@ inline APT::Solver::State &APT::Solver::operator[](Var r) return (*this)[cache.PkgP + P]; if (auto V = r.Ver()) return (*this)[cache.VerP + V]; + return *rootState.get(); +} - abort(); +inline const APT::Solver::State &APT::Solver::operator[](Var r) const +{ + return const_cast<Solver &>(*this)[r]; } |