summaryrefslogtreecommitdiffstats
path: root/apt-pkg/solver3.cc
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--apt-pkg/solver3.cc960
1 files changed, 960 insertions, 0 deletions
diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc
new file mode 100644
index 0000000..d43bd5b
--- /dev/null
+++ b/apt-pkg/solver3.cc
@@ -0,0 +1,960 @@
+/*
+ * solver3.cc - The APT 3.0 solver
+ *
+ * Copyright (c) 2023 Julian Andres Klode
+ * Copyright (c) 2023 Canonical Ltd
+ *
+ * SPDX-License-Identifier: GPL-2.0+
+ */
+
+#define APT_COMPILING_APT
+
+#include <config.h>
+
+#include <apt-pkg/algorithms.h>
+#include <apt-pkg/aptconfiguration.h>
+#include <apt-pkg/cachefilter.h>
+#include <apt-pkg/cacheset.h>
+#include <apt-pkg/error.h>
+#include <apt-pkg/macros.h>
+#include <apt-pkg/pkgsystem.h>
+#include <apt-pkg/solver3.h>
+#include <apt-pkg/version.h>
+
+#include <algorithm>
+#include <cassert>
+#include <sstream>
+
+// FIXME: Helpers stolen from DepCache, please give them back.
+struct CompareProviders3 /*{{{*/
+{
+ pkgCache &Cache;
+ pkgDepCache::Policy &Policy;
+ pkgCache::PkgIterator const Pkg;
+ bool upgrade{_config->FindB("APT::Solver::Upgrade", false)};
+
+ bool operator()(pkgCache::Version *AV, pkgCache::Version *BV)
+ {
+ return (*this)(pkgCache::VerIterator(Cache, AV), pkgCache::VerIterator(Cache, BV));
+ }
+ bool operator()(pkgCache::VerIterator const &AV, pkgCache::VerIterator const &BV)
+ {
+ 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;
+ if (not upgrade && A->CurrentVer != 0 && A.CurrentVer() == AV)
+ return true;
+ if (Policy.GetPriority(AV) < Policy.GetPriority(BV))
+ return false;
+
+ return _system->VS->CmpVersion(AV.VerStr(), BV.VerStr()) > 0;
+ }
+ // 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)
+ {
+ if (A->Group == Pkg->Group && B->Group != Pkg->Group)
+ return true;
+ else if (B->Group == Pkg->Group && A->Group != Pkg->Group)
+ return false;
+ }
+ // we like essentials
+ if ((A->Flags & pkgCache::Flag::Essential) != (B->Flags & pkgCache::Flag::Essential))
+ {
+ if ((A->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
+ return true;
+ else if ((B->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
+ return false;
+ }
+ if ((A->Flags & pkgCache::Flag::Important) != (B->Flags & pkgCache::Flag::Important))
+ {
+ if ((A->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important)
+ return true;
+ else if ((B->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important)
+ return false;
+ }
+ // prefer native architecture
+ if (strcmp(A.Arch(), B.Arch()) != 0)
+ {
+ if (strcmp(A.Arch(), A.Cache()->NativeArch()) == 0)
+ return true;
+ else if (strcmp(B.Arch(), B.Cache()->NativeArch()) == 0)
+ return false;
+ std::vector<std::string> archs = APT::Configuration::getArchitectures();
+ for (std::vector<std::string>::const_iterator a = archs.begin(); a != archs.end(); ++a)
+ if (*a == A.Arch())
+ return true;
+ else if (*a == B.Arch())
+ return false;
+ }
+ // higher priority seems like a good idea
+ if (AV->Priority != BV->Priority)
+ return AV->Priority < BV->Priority;
+ if (auto NameCmp = strcmp(A.Name(), B.Name()))
+ return NameCmp < 0;
+ // unable to decideā€¦
+ return A->ID > B->ID;
+ }
+};
+
+/** \brief Returns \b true for packages matching a regular
+ * expression in APT::NeverAutoRemove.
+ */
+class DefaultRootSetFunc2 : public pkgDepCache::DefaultRootSetFunc
+{
+ std::unique_ptr<APT::CacheFilter::Matcher> Kernels;
+
+ public:
+ DefaultRootSetFunc2(pkgCache *cache) : Kernels(APT::KernelAutoRemoveHelper::GetProtectedKernelsFilter(cache)){};
+ virtual ~DefaultRootSetFunc2(){};
+
+ bool InRootSet(const pkgCache::PkgIterator &pkg) APT_OVERRIDE { return pkg.end() == false && ((*Kernels)(pkg) || DefaultRootSetFunc::InRootSet(pkg)); };
+}; // FIXME: DEDUP with pkgDepCache.
+/*}}}*/
+
+APT::Solver::Solver(pkgCache &cache, pkgDepCache::Policy &policy)
+ : cache(cache),
+ policy(policy),
+ pkgStates{cache.Head().PackageCount},
+ verStates{cache.Head().VersionCount}
+{
+ static_assert(sizeof(APT::Solver::State<pkgCache::PkgIterator>) == 3 * sizeof(int));
+ static_assert(sizeof(APT::Solver::State<pkgCache::VerIterator>) == 3 * sizeof(int));
+ static_assert(sizeof(APT::Solver::Reason) == sizeof(map_pointer<pkgCache::Package>));
+ static_assert(sizeof(APT::Solver::Reason) == sizeof(map_pointer<pkgCache::Version>));
+}
+
+// This function determines if a work item is less important than another.
+bool APT::Solver::Work::operator<(APT::Solver::Work const &b) const
+{
+ if (optional && b.optional && reason.empty() && b.reason.empty() && upgrade != b.upgrade)
+ {
+ // Assuming we have libfoo-dev=5.1 Depends libfoo5.1-dev upgrade to libfoo-dev=5.3 Depends libfoo5.3-dev,
+ // We schedule libfoo-dev=5.3|libfoo-dev=5.1, libfoo5.1-dev. The latter would be resolved first, resulting
+ // in libfoo-dev being kept back.
+ //
+ // However, if we schedule not libfoo5.1-dev but bar Recommends libfoo5.1-dev, we should not be breaking that
+ // Recommends, hence we need to ensure that if we order an upgrade before an optional package that this optional
+ // package was a top level package, i.e. b.reason is empty (or our reason in the reverse case).
+ //
+ // So if we are the upgrade, and b also Depends on one of our versions, we need to satisfy b after we
+ // have scheduled the upgrade.
+ if (upgrade)
+ return std::any_of(b.solutions.begin(), b.solutions.end(), [this](auto bsol) -> bool
+ { return std::find(solutions.begin(), solutions.end(), bsol) != solutions.end(); });
+ else
+ return std::any_of(solutions.begin(), solutions.end(), [b](auto sol) -> bool
+ { return std::find(b.solutions.begin(), b.solutions.end(), sol) != b.solutions.end(); });
+ }
+ // An optional item is less important than a required one.
+ if (optional != b.optional)
+ return optional;
+ // More solutions to explore are more expensive.
+ if (size != b.size)
+ return size > b.size;
+ // 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;
+
+ return false;
+}
+
+void APT::Solver::Work::Dump(pkgCache &cache)
+{
+ if (dirty)
+ std::cerr << "Dirty ";
+ if (optional)
+ std::cerr << "Optional ";
+ std::cerr << "Item (" << size << "@" << depth << (upgrade ? "u" : "") << ") ";
+ if (auto Pkg = reason.Pkg(); Pkg != 0)
+ std::cerr << pkgCache::PkgIterator(cache, cache.PkgP + Pkg).FullName();
+ if (auto Ver = reason.Ver(); Ver != 0)
+ std::cerr << pkgCache::VerIterator(cache, cache.VerP + Ver).ParentPkg().FullName() << "=" << pkgCache::VerIterator(cache, cache.VerP + Ver).VerStr();
+ std::cerr << " -> ";
+ for (auto sol : solutions)
+ {
+ auto Ver = pkgCache::VerIterator(cache, sol);
+ std::cerr << " | " << Ver.ParentPkg().FullName() << "=" << Ver.VerStr();
+ }
+}
+
+// Prints an implication graph part of the form A -> B -> C, possibly with "not"
+std::string APT::Solver::WhyStr(Reason reason)
+{
+ std::vector<std::string> out;
+
+ while (not reason.empty())
+ {
+ if (auto Pkg = pkgCache::PkgIterator(cache, cache.PkgP + reason.Pkg()); 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 = pkgCache::VerIterator(cache, cache.VerP + reason.Ver()); 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;
+ }
+ }
+
+ std::string outstr;
+ for (auto I = out.rbegin(); I != out.rend(); ++I)
+ {
+ outstr += (outstr.size() == 0 ? "" : " -> ") + *I;
+ }
+ return outstr;
+}
+
+bool APT::Solver::Install(pkgCache::PkgIterator Pkg, Reason reason)
+{
+ if ((*this)[Pkg].decision == Decision::MUST)
+ return true;
+
+ // Check conflicting selections
+ if ((*this)[Pkg].decision == Decision::MUSTNOT)
+ return _error->Error("Conflict: %s -> %s but %s", WhyStr(reason).c_str(), Pkg.FullName().c_str(), WhyStr(Reason(Pkg)).c_str());
+
+ bool anyInstallable = false;
+ for (auto ver = Pkg.VersionList(); not ver.end(); ver++)
+ if ((*this)[ver].decision != Decision::MUSTNOT)
+ anyInstallable = true;
+
+ if (not anyInstallable)
+ {
+ _error->Error("Conflict: %s -> %s but no versions are installable",
+ WhyStr(reason).c_str(), Pkg.FullName().c_str());
+ for (auto ver = Pkg.VersionList(); not ver.end(); ver++)
+ _error->Error("Uninstallable version: %s", WhyStr(Reason(ver)).c_str());
+ return false;
+ }
+
+ // Note decision
+ if (unlikely(debug >= 1))
+ std::cerr << "[" << depth() << "] Install:" << Pkg.FullName() << " (" << WhyStr(reason) << ")\n";
+ (*this)[Pkg] = {reason, depth(), Decision::MUST,};
+
+ // Insert the work item.
+ Work workItem{Reason(Pkg), depth()};
+ for (auto ver = Pkg.VersionList(); not ver.end(); ver++)
+ if (IsAllowedVersion(ver))
+ workItem.solutions.push_back(ver);
+ std::sort(workItem.solutions.begin(), workItem.solutions.end(), CompareProviders3{cache, policy, Pkg});
+ assert(workItem.solutions.size() > 0);
+
+ if (workItem.solutions.size() > 1 || workItem.optional)
+ AddWork(std::move(workItem));
+ else if (not Install(pkgCache::VerIterator(cache, workItem.solutions[0]), workItem.reason))
+ return false;
+
+ if (not EnqueueCommonDependencies(Pkg))
+ return false;
+
+ return true;
+}
+
+bool APT::Solver::Install(pkgCache::VerIterator Ver, Reason reason)
+{
+ if ((*this)[Ver].decision == Decision::MUST)
+ return true;
+
+ if (unlikely(debug >= 1))
+ assert(IsAllowedVersion(Ver));
+
+ // Check conflicting selections
+ if ((*this)[Ver].decision == Decision::MUSTNOT)
+ return _error->Error("Conflict: %s -> %s but %s",
+ WhyStr(reason).c_str(),
+ (Ver.ParentPkg().FullName() + "=" + Ver.VerStr()).c_str(),
+ WhyStr(Reason(Ver)).c_str());
+ if ((*this)[Ver.ParentPkg()].decision == Decision::MUSTNOT)
+ return _error->Error("Conflict: %s -> %s but %s",
+ WhyStr(reason).c_str(),
+ (Ver.ParentPkg().FullName() + "=" + Ver.VerStr()).c_str(),
+ WhyStr(Reason(Ver.ParentPkg())).c_str());
+ for (auto otherVer = Ver.ParentPkg().VersionList(); not otherVer.end(); otherVer++)
+ if (otherVer->ID != Ver->ID && (*this)[otherVer].decision == Decision::MUST)
+ return _error->Error("Conflict: %s -> %s but %s",
+ WhyStr(reason).c_str(),
+ (Ver.ParentPkg().FullName() + "=" + Ver.VerStr()).c_str(),
+ WhyStr(Reason(otherVer)).c_str());
+
+ // Note decision
+ if (unlikely(debug >= 1))
+ std::cerr << "[" << depth() << "] Install:" << Ver.ParentPkg().FullName() << "=" << Ver.VerStr() << " (" << WhyStr(reason) << ")\n";
+ (*this)[Ver] = {reason, depth(), Decision::MUST,};
+ if ((*this)[Ver.ParentPkg()].decision != Decision::MUST)
+ (*this)[Ver.ParentPkg()] = {Reason(Ver), depth(), Decision::MUST,};
+
+ for (auto OV = Ver.ParentPkg().VersionList(); not OV.end(); ++OV)
+ {
+ if (OV != Ver && not Reject(OV, Reason(Ver)))
+ return false;
+ }
+
+ for (auto dep = Ver.DependsList(); not dep.end();)
+ {
+ // Compute a single dependency element (glob or)
+ pkgCache::DepIterator start;
+ pkgCache::DepIterator end;
+ dep.GlobOr(start, end); // advances dep
+
+ if (not policy.IsImportantDep(start))
+ continue;
+ if (not EnqueueOrGroup(start, end, Reason(Ver)))
+ return false;
+ }
+
+ return true;
+}
+
+bool APT::Solver::Reject(pkgCache::PkgIterator Pkg, Reason reason)
+{
+ if ((*this)[Pkg].decision == Decision::MUSTNOT)
+ return true;
+
+ // Check conflicting selections
+ for (auto ver = Pkg.VersionList(); not ver.end(); ver++)
+ if ((*this)[ver].decision == Decision::MUST)
+ return _error->Error("Conflict: %s -> not %s but %s", WhyStr(reason).c_str(), Pkg.FullName().c_str(), WhyStr(Reason(ver)).c_str());
+ if ((*this)[Pkg].decision == Decision::MUST)
+ return _error->Error("Conflict: %s -> not %s but %s", WhyStr(reason).c_str(), Pkg.FullName().c_str(), WhyStr(Reason(Pkg)).c_str());
+
+ // Reject the package and its versions.
+ if (unlikely(debug >= 1))
+ std::cerr << "[" << depth() << "] Reject:" << Pkg.FullName() << " (" << WhyStr(reason) << ")\n";
+ (*this)[Pkg] = {reason, depth(), Decision::MUSTNOT,};
+ for (auto ver = Pkg.VersionList(); not ver.end(); ver++)
+ if (not Reject(ver, Reason(Pkg)))
+ return false;
+
+ needsRescore = true;
+
+ return true;
+}
+
+// \brief Do not install this version
+bool APT::Solver::Reject(pkgCache::VerIterator Ver, Reason reason)
+{
+ if ((*this)[Ver].decision == Decision::MUSTNOT)
+ return true;
+
+ // Check conflicting choices.
+ if ((*this)[Ver].decision == Decision::MUST)
+ return _error->Error("Conflict: %s -> not %s but %s",
+ WhyStr(reason).c_str(),
+ (Ver.ParentPkg().FullName() + "=" + Ver.VerStr()).c_str(),
+ WhyStr(Reason(Ver)).c_str());
+
+ // Mark the package as rejected and propagate up as needed.
+ if (unlikely(debug >= 1))
+ std::cerr << "[" << depth() << "] Reject:" << Ver.ParentPkg().FullName() << "=" << Ver.VerStr() << " (" << WhyStr(reason) << ")\n";
+ (*this)[Ver] = {reason, depth(), Decision::MUSTNOT,};
+ if (auto pkg = Ver.ParentPkg(); (*this)[pkg].decision != Decision::MUSTNOT)
+ {
+ bool anyInstallable = false;
+ for (auto otherVer = pkg.VersionList(); not otherVer.end(); otherVer++)
+ if (otherVer->ID != Ver->ID && (*this)[otherVer].decision != Decision::MUSTNOT)
+ anyInstallable = true;
+
+ if (anyInstallable)
+ ;
+ else if ((*this)[pkg].decision == Decision::MUST) // Must install, but none available
+ {
+ _error->Error("Conflict: %s but no versions are installable",
+ WhyStr(Reason(pkg)).c_str());
+ for (auto otherVer = pkg.VersionList(); not otherVer.end(); otherVer++)
+ if ((*this)[otherVer].decision == Decision::MUSTNOT)
+ _error->Error("Uninstallable version: %s", WhyStr(Reason(otherVer)).c_str());
+ return _error->Error("Uninstallable version: %s -> not %s",
+ WhyStr(reason).c_str(),
+ (Ver.ParentPkg().FullName() + "=" + Ver.VerStr()).c_str());
+ }
+ else if ((*this)[Ver.ParentPkg()].decision != Decision::MUSTNOT) // Last installable invalidated
+ (*this)[Ver.ParentPkg()] = {Reason(Ver), depth(), Decision::MUSTNOT};
+ }
+
+ if (not RejectReverseDependencies(Ver))
+ return false;
+
+ needsRescore = true;
+
+ return true;
+}
+
+bool APT::Solver::EnqueueCommonDependencies(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;
+ pkgCache::DepIterator end;
+ dep.GlobOr(start, end); // advances dep
+
+ bool allHaveDep = true;
+ for (auto ver = Pkg.VersionList()++; not ver.end(); ver++)
+ {
+ bool haveDep = false;
+ for (auto otherDep = ver.DependsList(); not haveDep && not otherDep.end(); otherDep++)
+ haveDep = otherDep->DependencyData == start->DependencyData;
+ if (!haveDep)
+ allHaveDep = haveDep;
+ }
+ if (not allHaveDep)
+ continue;
+ if (not policy.IsImportantDep(start))
+ continue;
+ if (not EnqueueOrGroup(start, end, Reason(Pkg)))
+ return false;
+ }
+
+ return true;
+}
+
+bool APT::Solver::EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepIterator end, Reason reason)
+{
+ auto TgtPkg = start.TargetPkg();
+ auto Ver = start.ParentVer();
+ auto fixPolicy = _config->FindB("APT::Get::Fix-Policy-Broken");
+
+ if (unlikely(debug >= 3))
+ std::cerr << "Found dependency critical " << Ver.ParentPkg().FullName() << "=" << Ver.VerStr() << " -> " << start.TargetPkg().FullName() << "\n";
+
+ Work workItem{reason, depth(), not start.IsCritical() /* optional */};
+
+ do
+ {
+ auto begin = workItem.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 Reject(pkgCache::VerIterator(cache, *tgt), Reason(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";
+ if (IsAllowedVersion(*tgt))
+ workItem.solutions.push_back(*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::sort(workItem.solutions.begin() + begin, workItem.solutions.end(), CompareProviders3{cache, policy, TgtPkg});
+
+ if (start == end)
+ break;
+ ++start;
+ } while (1);
+
+ if (not fixPolicy)
+ std::sort(workItem.solutions.begin(), workItem.solutions.end(), CompareProviders3{cache, policy, TgtPkg});
+
+ // Figure out if the reason is installed
+ bool reasonInstalled = false;
+ if (auto p = workItem.reason.Pkg())
+ reasonInstalled = pkgCache::PkgIterator(cache, cache.PkgP + p)->CurrentVer != 0;
+ else if (auto v = workItem.reason.Ver())
+ reasonInstalled = pkgCache::VerIterator(cache, cache.VerP + v).ParentPkg()->CurrentVer != 0;
+
+ // Try to perserve satisfied Recommends. FIXME: We should check if the Recommends was there in the installed version?
+ if (workItem.optional && reasonInstalled && not fixPolicy &&
+ not std::any_of(workItem.solutions.begin(), workItem.solutions.end(), [this](auto ver)
+ { return pkgCache::VerIterator(cache, ver).ParentPkg()->CurrentVer != 0; }))
+ {
+ if (unlikely(debug >= 3))
+ {
+ std::cerr << "Ignoring currently unsatisfied Recommends ";
+ workItem.Dump(cache);
+ std::cerr << "\n";
+ }
+ return true;
+ }
+ if (not workItem.solutions.empty())
+ {
+ // std::sort(workItem.solutions.begin(), workItem.solutions.end(), CompareProviders3{cache, TgtPkg});
+ if (unlikely(debug >= 3 && workItem.optional))
+ {
+ std::cerr << "Enqueuing currently satisfied Recommends ";
+ workItem.Dump(cache);
+ std::cerr << "\n";
+ }
+ if (workItem.optional || workItem.solutions.size() > 1)
+ AddWork(std::move(workItem));
+ else if (not Install(pkgCache::VerIterator(cache, workItem.solutions[0]), 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;
+}
+
+// \brief Find the or group containing the given dependency.
+static void FindOrGroup(pkgCache::DepIterator const &D, pkgCache::DepIterator &start, pkgCache::DepIterator &end)
+{
+ for (auto dep = D.ParentVer().DependsList(); not dep.end();)
+ {
+ dep.GlobOr(start, end); // advances dep
+
+ for (auto member = start;;)
+ {
+ if (member == D)
+ return;
+ if (member == end)
+ break;
+ member++;
+ }
+ }
+
+ _error->Fatal("Found a dependency that does not exist in its parent version");
+ abort();
+}
+
+// This is the opposite of EnqueueOrDependencies, it rejects the reverse dependencies of the
+// given version iterator.
+bool APT::Solver::RejectReverseDependencies(pkgCache::VerIterator Ver)
+{
+ // This checks whether an or group is still satisfiable.
+ auto stillPossible = [this](pkgCache::DepIterator start, pkgCache::DepIterator end)
+ {
+ while (1)
+ {
+ std::unique_ptr<pkgCache::Version *[]> Ts{start.AllTargets()};
+ for (size_t i = 0; Ts[i] != nullptr; ++i)
+ if ((*this)[Ts[i]].decision != Decision::MUSTNOT)
+ return true;
+
+ if (start == end)
+ return false;
+
+ start++;
+ }
+ };
+
+ for (auto RD = Ver.ParentPkg().RevDependsList(); not RD.end(); ++RD)
+ {
+ auto RDV = RD.ParentVer();
+ if (RD.IsNegative() || not RD.IsCritical() || not RD.IsSatisfied(Ver))
+ continue;
+
+ if ((*this)[RDV].decision == Decision::MUSTNOT)
+ continue;
+
+ pkgCache::DepIterator start;
+ pkgCache::DepIterator end;
+ FindOrGroup(RD, start, end);
+
+ if (stillPossible(start, end))
+ continue;
+
+ if (unlikely(debug >= 3))
+ std::cerr << "Propagate NOT " << Ver.ParentPkg().FullName() << "=" << Ver.VerStr() << " to " << RDV.ParentPkg().FullName() << "=" << RDV.VerStr() << " for dependency group starting with" << start.TargetPkg().FullName() << std::endl;
+
+ if (not Reject(RDV, Reason(Ver)))
+ return false;
+ }
+ return true;
+}
+
+bool APT::Solver::IsAllowedVersion(pkgCache::Version *V)
+{
+ pkgCache::VerIterator ver(cache, V);
+ if (not StrictPinning || ver.ParentPkg().CurrentVer() == ver || policy.GetCandidateVer(ver.ParentPkg()) == ver)
+ return true;
+
+ if (unlikely(debug >= 3))
+ std::cerr << "Ignoring: " << ver.ParentPkg().FullName() << "=" << ver.VerStr() << "(neither candidate nor installed)\n";
+ return false;
+}
+
+void APT::Solver::Push(Work work)
+{
+ if (unlikely(debug >= 2))
+ {
+ std::cerr << "Trying choice for ";
+ work.Dump(cache);
+ std::cerr << "\n";
+ }
+ choices.push_back(std::move(work));
+ // Pop() will call MergeWithStack() when reverting to level 0, or RevertToStack after dumping to the debug log.
+ _error->PushToStack();
+}
+
+bool APT::Solver::Pop()
+{
+ auto depth = APT::Solver::depth();
+ if (depth == 0)
+ return false;
+
+ if (unlikely(debug >= 2))
+ for (std::string msg; _error->PopMessage(msg);)
+ std::cerr << "Branch failed: " << msg << std::endl;
+
+ _error->RevertToStack();
+
+ depth--;
+
+ // Clean up the higher level states.
+ // FIXME: Do not override the hints here.
+ for (auto &state : pkgStates)
+ if (state.depth > depth)
+ state = {};
+ for (auto &state : verStates)
+ if (state.depth > depth)
+ state = {};
+
+ // This destroys the invariants that `work` must be a heap. But this is ok:
+ // we are restoring the invariant below, because rejecting a package always
+ // calls std::make_heap.
+ work.erase(std::remove_if(work.begin(), work.end(), [depth](Work &w) -> bool
+ { return w.depth > depth || w.dirty; }),
+ work.end());
+ std::make_heap(work.begin(), work.end());
+
+ // Go over the solved items, see if any of them need to be moved back or deleted.
+ solved.erase(std::remove_if(solved.begin(), solved.end(), [this, depth](Work &w) -> bool
+ {
+ if (w.depth > depth) // Deeper decision level is no longer valid.
+ return true;
+ // This item is still solved, keep it on the solved list.
+ if (not std::any_of(w.solutions.begin(), w.solutions.end(), [this](auto ver)
+ { return (*this)[ver].decision == Decision::MUST; }))
+ return false;
+ // We are not longer solved, move it back to work.
+ AddWork(std::move(w));
+ return true; }),
+ solved.end());
+
+ Work w = std::move(choices.back());
+ choices.pop_back();
+ if (unlikely(debug >= 2))
+ {
+ std::cerr << "Backtracking to choice ";
+ w.Dump(cache);
+ std::cerr << "\n";
+ }
+ if (unlikely(debug >= 4))
+ {
+ std::cerr << "choices: ";
+ for (auto &i : choices)
+ {
+ std::cerr << pkgCache::VerIterator(cache, i.choice).ParentPkg().FullName(true) << "=" << pkgCache::VerIterator(cache, i.choice).VerStr();
+ }
+ std::cerr << std::endl;
+ }
+
+ assert(w.choice != nullptr);
+ // FIXME: There should be a reason!
+ if (not Reject(pkgCache::VerIterator(cache, w.choice), {}))
+ return false;
+
+ w.choice = nullptr;
+ AddWork(std::move(w));
+ return true;
+}
+
+void 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());
+}
+
+void APT::Solver::RescoreWorkIfNeeded()
+{
+ if (not needsRescore)
+ return;
+
+ needsRescore = false;
+ std::vector<Work> resized;
+ for (auto &w : work)
+ {
+ if (w.dirty)
+ continue;
+ size_t newSize = std::count_if(w.solutions.begin(), w.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
+ // we just move around when we get to it too early in Solve(). This reduces memory usage
+ // at the expense of counting each item we see in Solve().
+ if (newSize < w.size)
+ {
+ Work newWork(w);
+ newWork.size = newSize;
+ resized.push_back(std::move(newWork));
+ w.dirty = true;
+ }
+ }
+ if (unlikely(debug >= 2))
+ std::cerr << "Rescored: " << resized.size() << "items\n";
+ for (auto &w : resized)
+ {
+ work.push_back(std::move(w));
+ std::push_heap(work.begin(), work.end());
+ }
+}
+
+bool APT::Solver::Solve()
+{
+ while (not work.empty())
+ {
+ // Rescore the work if we need to
+ RescoreWorkIfNeeded();
+ // *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().dirty)
+ {
+ work.pop_back();
+ continue;
+ }
+
+ // If our size increased, queue again.
+ size_t newSize = std::count_if(work.back().solutions.begin(), work.back().solutions.end(), [this](auto V)
+ { return (*this)[V].decision != Decision::MUSTNOT; });
+
+ if (newSize > work.back().size)
+ {
+ work.back().size = newSize;
+ std::push_heap(work.begin(), work.end());
+ continue;
+ }
+ assert(newSize == work.back().size);
+
+ auto item = std::move(work.back());
+ work.pop_back();
+ solved.push_back(item);
+
+ if (std::any_of(item.solutions.begin(), item.solutions.end(), [this](auto ver)
+ { return (*this)[ver].decision == Decision::MUST; }))
+ {
+ if (unlikely(debug >= 2))
+ {
+ std::cerr << "ELIDED ";
+ item.Dump(cache);
+ std::cerr << "\n";
+ }
+ continue;
+ }
+
+ if (unlikely(debug >= 1))
+ {
+ item.Dump(cache);
+ std::cerr << "\n";
+ }
+
+ assert(item.solutions.size() > 1 || item.optional);
+
+ bool foundSolution = false;
+ for (auto &sol : item.solutions)
+ {
+ pkgCache::VerIterator ver(cache, sol);
+ if ((*this)[ver].decision == Decision::MUSTNOT)
+ {
+ if (unlikely(debug >= 3))
+ std::cerr << "(existing conflict: " << ver.ParentPkg().FullName() << "=" << ver.VerStr() << ")\n";
+ continue;
+ }
+ if (item.size > 1 || item.optional)
+ {
+ item.choice = ver;
+ Push(item);
+ }
+ if (unlikely(debug >= 3))
+ std::cerr << "(try it: " << ver.ParentPkg().FullName() << "=" << ver.VerStr() << ")\n";
+ if (not Install(pkgCache::VerIterator(cache, ver), item.reason) && not Pop())
+ return false;
+ foundSolution = true;
+ break;
+ }
+ if (not foundSolution && not item.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)
+ if ((*this)[sol].decision == Decision::MUSTNOT)
+ _error->Error("Not considered: %s=%s: %s", pkgCache::VerIterator(cache, sol).ParentPkg().FullName().c_str(),
+ pkgCache::VerIterator(cache, sol).VerStr(),
+ WhyStr(Reason(pkgCache::VerIterator(cache, sol))).c_str());
+ if (not Pop())
+ return false;
+ }
+ }
+
+ return true;
+}
+
+// \brief Apply the selections from the dep cache to the solver
+bool APT::Solver::FromDepCache(pkgDepCache &depcache)
+{
+ bool KeepAuto = not _config->FindB("APT::Get::AutomaticRemove");
+ bool AllowRemove = _config->FindB("APT::Solver::Remove", true);
+ bool AllowInstall = _config->FindB("APT::Solver::Install", true);
+ DefaultRootSetFunc2 rootSet(&cache);
+
+ for (auto P = cache.PkgBegin(); not P.end(); P++)
+ {
+ if (P->VersionList == nullptr)
+ continue;
+
+ auto state = depcache[P];
+ auto maybeInstall = state.Install() || (state.Keep() && P->CurrentVer);
+ auto reject = state.Delete() || (depcache[P].Keep() && not P->CurrentVer && depcache[P].Protect());
+ if (P->SelectedState == pkgCache::State::Hold && not state.Protect())
+ {
+ if (unlikely(debug >= 1))
+ std::cerr << "Hold " << P.FullName() << "\n";
+ if (P->CurrentVer ? not Install(P.CurrentVer(), {}) : not Reject(P, {}))
+ return false;
+ }
+ else if (reject)
+ {
+ if (unlikely(debug >= 1))
+ std::cerr << "Delete " << P.FullName() << "\n";
+ if (!Reject(P, {}))
+ return false;
+ }
+ else if (maybeInstall && P->Flags & (pkgCache::Flag::Essential | pkgCache::Flag::Important))
+ {
+ if (unlikely(debug >= 1))
+ std::cerr << "ESSENTIAL " << P.FullName() << "\n";
+ if (depcache[P].Keep() ? not Install(P, {}) : not Install(depcache.GetCandidateVersion(P), {}))
+ return false;
+ }
+ else if (maybeInstall && not(depcache[P].Flags & pkgCache::Flag::Auto))
+ {
+ if (unlikely(debug >= 1))
+ std::cerr << "MANUAL " << P.FullName() << "\n";
+ if (depcache[P].Keep() ? not Install(P, {}) : not Install(depcache.GetCandidateVersion(P), {}))
+ return false;
+ }
+ else if (maybeInstall && (KeepAuto || rootSet.InRootSet(P)) && (depcache[P].Flags & pkgCache::Flag::Auto))
+ {
+ auto Upgrade = depcache.GetCandidateVersion(P) != P.CurrentVer();
+ if (unlikely(debug >= 1))
+ std::cerr << "AUTOMATIC " << P.FullName() << (Upgrade ? " - upgrade" : "") << "\n";
+
+ if (not AllowRemove)
+ {
+ if (depcache[P].Keep() ? not Install(P, {}) : not Install(depcache.GetCandidateVersion(P), {}))
+ return false;
+ }
+ else
+ {
+ Work w{Reason(), depth(), true, Upgrade};
+ for (auto V = P.VersionList(); not V.end(); ++V)
+ if (IsAllowedVersion(V))
+ w.solutions.push_back(V);
+ std::sort(w.solutions.begin(), w.solutions.end(), CompareProviders3{cache, policy, P});
+ AddWork(std::move(w));
+ }
+ }
+ else if (P->CurrentVer == 0 && not AllowInstall)
+ {
+ if (unlikely(debug >= 1))
+ std::cerr << "NOT ALLOWING INSTALL OF " << P.FullName() << "\n";
+ if (not Reject(P, {}))
+ return false;
+ }
+ }
+
+ return true;
+}
+
+bool APT::Solver::ToDepCache(pkgDepCache &depcache)
+{
+ pkgDepCache::ActionGroup group(depcache);
+ for (auto P = cache.PkgBegin(); not P.end(); P++)
+ {
+ if ((*this)[P].decision == Decision::MUST)
+ {
+ for (auto V = P.VersionList(); not V.end(); V++)
+ {
+ if ((*this)[V].decision == Decision::MUST)
+ {
+ depcache.SetCandidateVersion(V);
+ break;
+ }
+ }
+ auto reason = (*this)[depcache.GetCandidateVersion(P)].reason;
+ if (auto RP = reason.Pkg(); RP == P.MapPointer())
+ reason = (*this)[P].reason;
+
+ depcache.MarkInstall(P, false, 0, reason.empty());
+ if (not P->CurrentVer)
+ depcache.MarkAuto(P, not reason.empty());
+ depcache[P].Marked = 1;
+ depcache[P].Garbage = 0;
+ }
+ else if (P->CurrentVer)
+ {
+ depcache.MarkDelete(P, false, 0, (*this)[P].reason.empty());
+ depcache[P].Marked = 0;
+ depcache[P].Garbage = 1;
+ }
+ }
+ return true;
+}