From bd0738fdd9aff3016230b3b5466e9498c58e4fb8 Mon Sep 17 00:00:00 2001 From: Julian Andres Klode Date: Mon, 22 Dec 2025 22:40:12 +0100 Subject: solver3: Reorder the source code Move the DependencySolver methods and their helpers to the end of the file. --- apt-pkg/solver3.cc | 955 ++++++++++++++++++++++++++--------------------------- apt-pkg/solver3.h | 3 +- 2 files changed, 477 insertions(+), 481 deletions(-) (limited to 'apt-pkg') diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc index ec33cc1f6..8ef969581 100644 --- a/apt-pkg/solver3.cc +++ b/apt-pkg/solver3.cc @@ -41,164 +41,6 @@ namespace APT::Solver { -// FIXME: Helpers stolen from DepCache, please give them back. -struct Solver::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 archs = APT::Configuration::getArchitectures(); - for (std::vector::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 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. -/*}}}*/ - Solver::Solver(pkgCache &cache) : cache(cache), rootState(new State), @@ -216,25 +58,6 @@ Solver::Solver(pkgCache &cache) Solver::~Solver() = default; -DependencySolver::DependencySolver(pkgCache &cache, pkgDepCache::Policy &policy, EDSP::Request::Flags requestFlags) - : Solver(cache), - policy(policy), - requestFlags(requestFlags), - pkgObsolete(cache), - priorities(cache), - candidates(cache) -{ - // Ensure trivially - static_assert(std::is_trivially_destructible_v); - static_assert(std::is_trivially_destructible_v); - static_assert(sizeof(Var) == sizeof(map_pointer)); - static_assert(sizeof(Var) == sizeof(map_pointer)); - // Root state is "true". - rootState->decision = LiftedBool::True; -} - -DependencySolver::~DependencySolver() = default; - // This function determines if a work item is less important than another. bool Solver::Work::operator<(Solver::Work const &b) const { @@ -512,73 +335,6 @@ std::string Solver::LongWhyStr(Var var, bool decision, const Clause *rclause, st 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 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; -} bool Solver::Assume(Lit lit, const Clause *reason) { trailLim.push_back(trail.size()); @@ -685,18 +441,388 @@ bool Solver::Propagate() return true; } -static bool SameOrGroup(pkgCache::DepIterator a, pkgCache::DepIterator b) +void Solver::Push(Var var, Work work) { - while (1) - { - if (a->DependencyData != b->DependencyData) - return false; + if (unlikely(debug >= 2)) + std::cerr << "Trying choice for " << work.toString(cache) << std::endl; - // At least one has reached the end, break - if (not(a->CompareOp & pkgCache::Dep::Or) || not(b->CompareOp & pkgCache::Dep::Or)) - break; + trailLim.push_back(trail.size()); + trail.push_back(Trail{var, std::move(work)}); +} - ++a, ++b; +void Solver::UndoOne() +{ + auto trailItem = trail.back(); + + if (unlikely(debug >= 4)) + std::cerr << "Undoing a single decision\n"; + + if (not trailItem.assigned.empty()) + { + if (unlikely(debug >= 4)) + std::cerr << "Unassign " << trailItem.assigned.toString(cache) << "\n"; + auto &state = (*this)[trailItem.assigned]; + state.decision = LiftedBool::Undefined; + state.reason = nullptr; + state.reasonStr = nullptr; + state.depth = 0; + } + + if (auto work = trailItem.work) + { + if (unlikely(debug >= 4)) + std::cerr << "Adding work item " << work->toString(cache) << std::endl; + + if (not AddWork(std::move(*work))) + abort(); + } + + 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 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. + trailLim.pop_back(); + work.erase(std::remove_if(work.begin(), work.end(), [this](Work &w) -> bool + { return w.depth > 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 (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(); + trail.push_back(Trail{Var(), item}); + + 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; + continue; + } + + if (unlikely(debug >= 1)) + std::cerr << item.toString(cache) << std::endl; + + bool foundSolution = false; + for (auto &sol : item.clause->solutions) + { + if (value(sol) == LiftedBool::False) + { + 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, 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 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; +} + +// -------------------------------------------------------------------------------------------------------------------- +// -------------------------------------------- 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 archs = APT::Configuration::getArchitectures(); + for (std::vector::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 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) + { + if (a->DependencyData != b->DependencyData) + return false; + + // At least one has reached the end, break + if (not(a->CompareOp & pkgCache::Dep::Or) || not(b->CompareOp & pkgCache::Dep::Or)) + break; + + ++a, ++b; } // Fully iterated over a and b return not(a->CompareOp & pkgCache::Dep::Or) && not(b->CompareOp & pkgCache::Dep::Or); @@ -731,42 +857,109 @@ const Clause *DependencySolver::RegisterClause(Clause &&clause) earlierSol) != clause.solutions.end(); })) 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(); }); + 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(); }); + + earlierClause->merged.push_front(clause); + merged = true; + } + else if (clause.optional) + { + // 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(); }); + + // Remove recursion here, such that we display correctly (if we ever display anywhere...) + auto earlierClauseCopy = *earlierClause; + clause.merged = std::move(earlierClauseCopy.merged); + clause.merged.push_front(earlierClauseCopy); + } + } + + if (merged) + return nullptr; + } + + clauses.push_back(std::make_unique(std::move(clause))); + auto const &inserted = clauses.back(); + for (auto var : inserted->solutions) + (*this)[var].rclauses.push_back(inserted.get()); + return inserted.get(); +} + +// 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; - earlierClause->merged.push_front(clause); - merged = true; - } - else if (clause.optional) - { - // 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(); }); + auto ver = GetCandidateVer(pkg); - // Remove recursion here, such that we display correctly (if we ever display anywhere...) - auto earlierClauseCopy = *earlierClause; - clause.merged = std::move(earlierClauseCopy.merged); - clause.merged.push_front(earlierClauseCopy); - } - } + 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 (merged) - return nullptr; + 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; + } } - clauses.push_back(std::make_unique(std::move(clause))); - auto const &inserted = clauses.back(); - for (auto var : inserted->solutions) - (*this)[var].rclauses.push_back(inserted.get()); - return inserted.get(); + 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()); @@ -1007,202 +1200,6 @@ Clause DependencySolver::TranslateOrGroup(pkgCache::DepIterator start, pkgCache: return clause; } -void Solver::Push(Var var, Work work) -{ - if (unlikely(debug >= 2)) - std::cerr << "Trying choice for " << work.toString(cache) << std::endl; - - trailLim.push_back(trail.size()); - trail.push_back(Trail{var, std::move(work)}); -} - -void Solver::UndoOne() -{ - auto trailItem = trail.back(); - - if (unlikely(debug >= 4)) - std::cerr << "Undoing a single decision\n"; - - if (not trailItem.assigned.empty()) - { - if (unlikely(debug >= 4)) - std::cerr << "Unassign " << trailItem.assigned.toString(cache) << "\n"; - auto &state = (*this)[trailItem.assigned]; - state.decision = LiftedBool::Undefined; - state.reason = nullptr; - state.reasonStr = nullptr; - state.depth = 0; - } - - if (auto work = trailItem.work) - { - if (unlikely(debug >= 4)) - std::cerr << "Adding work item " << work->toString(cache) << std::endl; - - if (not AddWork(std::move(*work))) - abort(); - } - - 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 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. - trailLim.pop_back(); - work.erase(std::remove_if(work.begin(), work.end(), [this](Work &w) -> bool - { return w.depth > 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 (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(); - trail.push_back(Trail{Var(), item}); - - 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; - continue; - } - - if (unlikely(debug >= 1)) - std::cerr << item.toString(cache) << std::endl; - - bool foundSolution = false; - for (auto &sol : item.clause->solutions) - { - if (value(sol) == LiftedBool::False) - { - 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, 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 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 DependencySolver::FromDepCache(pkgDepCache &depcache) { diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h index 9faa97079..23ae49297 100644 --- a/apt-pkg/solver3.h +++ b/apt-pkg/solver3.h @@ -277,7 +277,6 @@ inline LiftedBool operator~(LiftedBool decision) class Solver { protected: - struct CompareProviders3; struct State; struct Work; struct Trail; @@ -421,7 +420,7 @@ class Solver */ class DependencySolver : public Solver { - friend class Solver::CompareProviders3; + friend class CompareProviders3; // Policy is needed for determining candidate version. pkgDepCache::Policy &policy; -- cgit v1.2.3-70-g09d2