diff options
Diffstat (limited to 'apt-pkg/solver3.cc')
| -rw-r--r-- | apt-pkg/solver3.cc | 468 |
1 files changed, 221 insertions, 247 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++) |