From b81238fa02b2348f3fbb90e4d5e54a3ad8d78ac4 Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Tue, 14 May 2024 21:18:38 +0200 Subject: Adding upstream version 2.9.3. Signed-off-by: Daniel Baumann --- apt-pkg/solver3.h | 286 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 286 insertions(+) create mode 100644 apt-pkg/solver3.h (limited to 'apt-pkg/solver3.h') diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h new file mode 100644 index 0000000..cf2fb2e --- /dev/null +++ b/apt-pkg/solver3.h @@ -0,0 +1,286 @@ +/* + * solver3.h - The APT 3.0 solver + * + * Copyright (c) 2023 Julian Andres Klode + * Copyright (c) 2023 Canonical Ltd + * + * SPDX-License-Identifier: GPL-2.0+ + */ + +#include + +#include +#include +#include +#include + +namespace APT +{ + +/* + * \brief APT 3.0 solver + * + * This is a simple solver focused on understandability and sensible results, it + * will not generally find all solutions to the problem but will try to find the best + * ones. + * + * It is a brute force solver with heuristics, conflicts learning, and 2**32 levels + * of backtracking. + */ +class Solver +{ + enum class Decision : uint16_t; + enum class Hint : uint16_t; + struct Reason; + template + struct State; + struct Work; + + // \brief Type to record depth at. This may very well be a 16-bit + // unsigned integer, then change Solver::State::Decision to be a + // uint16_t class enum as well to get a more compact space. + using depth_type = unsigned int; + + // Documentation + template + using heap = std::vector; + + static_assert(sizeof(depth_type) >= sizeof(map_id_t)); + + // Cache is needed to construct Iterators from Version objects we see + pkgCache &cache; + // Policy is needed for determining candidate version. + pkgDepCache::Policy &policy; + // States for packages + std::vector> pkgStates{}; + // States for versions + std::vector> verStates{}; + + // \brief Helper function for safe access to package state. + inline State &operator[](pkgCache::Package *P) + { + return pkgStates[P->ID]; + } + + // \brief Helper function for safe access to version state. + inline State &operator[](pkgCache::Version *V) + { + return verStates[V->ID]; + } + + // \brief Heap of the remaining work. + // + // We are using an std::vector with std::make_heap(), std::push_heap(), + // and std::pop_heap() rather than a priority_queue because we need to + // be able to iterate over the queued work and see if a choice would + // invalidate any work. + heap work{}; + // \brief Whether RescoreWork() actually needs to rescore the work. + bool needsRescore{false}; + + // \brief Current decision level. + // + // Each time a decision needs to be made we can push the item under + // consideration to our backlog of choices made and then later we can + // restore it easily. + std::vector choices{}; + // \brief Backlog of solved work. + // + // Solved work may become invalidated when backtracking, so store it + // here to revisit it later. + std::vector solved{}; + + /// Various configuration options + // \brief Debug level + 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 If set, removals are allowed. + bool AllowRemove{_config->FindB("APT::Solver::Remove", true)}; + // \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 Enqueue dependencies shared by all versions of the package. + bool EnqueueCommonDependencies(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, Reason reason); + // \brief Check if a version is allowed by policy. + bool IsAllowedVersion(pkgCache::Version *V); + + // \brief Return the current depth (choices.size() with casting) + depth_type depth() + { + return static_cast(choices.size()); + } + + public: + // \brief Create a new decision level. + bool Pop(); + // \brief Revert to the previous decision level. + void Push(Work work); + // \brief Add work to our work queue. + void AddWork(Work &&work); + // \brief Rescore the work after a reject or a pop + void RescoreWorkIfNeeded(); + + // \brief Basic solver initializer. This cannot fail. + Solver(pkgCache &Cache, pkgDepCache::Policy &Policy); + + // \brief Mark the package for install. This is annoying as it incurs a decision + bool Install(pkgCache::PkgIterator Pkg, Reason reason); + // \brief Install a version. + bool Install(pkgCache::VerIterator Ver, Reason reason); + // \brief Do not install this package + bool Reject(pkgCache::PkgIterator Pkg, Reason reason); + // \brief Do not install this version. + bool Reject(pkgCache::VerIterator Ver, Reason reason); + + // \brief Apply the selections from the dep cache to the solver + bool FromDepCache(pkgDepCache &depcache); + // \brief Apply the solver result to the depCache + bool ToDepCache(pkgDepCache &depcache); + + // \brief Solve the dependencies + bool Solve(); + + // Print dependency chain + std::string WhyStr(Reason reason); +}; + +}; // namespace APT + +/** + * \brief Tagged union holding either a package, version, or nothing; representing the reason for installing something. + * + * We want to keep track of the reason why things are being installed such that + * we can have sensible debugging abilities. + * + * If the reason is empty, this means the package is automatically installed. + */ +struct APT::Solver::Reason +{ + uint32_t IsVersion : 1; + uint32_t MapPtr : 31; + + Reason() : IsVersion(0), MapPtr(0) {} + explicit Reason(pkgCache::PkgIterator const &Pkg) : IsVersion(0), MapPtr(Pkg.MapPointer()) {} + explicit Reason(pkgCache::VerIterator const &Ver) : IsVersion(1), MapPtr(Ver.MapPointer()) {} + + // \brief Return the package, if any, otherwise 0. + map_pointer Pkg() const + { + return IsVersion ? 0 : map_pointer{(uint32_t)MapPtr}; + } + // \brief Return the version, if any, otherwise 0. + map_pointer Ver() const + { + return IsVersion ? map_pointer{(uint32_t)MapPtr} : 0; + } + // \brief Check if there is no reason. + bool empty() const + { + return IsVersion == 0 && MapPtr == 0; + } +}; + +/** + * \brief A single work item + * + * A work item is a positive dependency that still needs to be resolved. Work + * is ordered, by depth, length of solutions, and optionality. + * + * The work can always be recalculated from the state by iterating over dependencies + * of all packages in there, finding solutions to them, and then adding all dependencies + * not yet resolved to the work queue. + */ +struct APT::Solver::Work +{ + // \brief Reason for the work + Reason reason; + // \brief The depth at which the item has been added + depth_type depth; + + // \brief Possible solutions to this task, ordered in order of preference. + std::vector 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; + // Number of valid choices + size_t size; + }; + + // \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 dirty; + + bool operator<(APT::Solver::Work const &b) const; + // \brief Dump the work item to std::cerr + void Dump(pkgCache &cache); + + inline Work(Reason reason, depth_type depth, bool optional = false, bool upgrade = false) : reason(reason), depth(depth), size(0), optional(optional), upgrade(upgrade), dirty(false) {} +}; + +// \brief This essentially describes the install state in RFC2119 terms. +enum class APT::Solver::Decision : uint16_t +{ + // \brief We have not made a choice about the package yet + NONE, + // \brief We need to install this package + MUST, + // \brief We cannot install this package (need conflicts with it) + 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 + * + * For each version, the solver records a decision at a certain level. It + * maintains an array mapping from version ID to state. + */ +template +struct APT::Solver::State +{ + // \brief The reason for causing this state (invalid for NONE). + // + // Rejects may have been caused by a later state. Consider we select + // between x1 and x2 in depth = N. If we now find dependencies of x1 + // leading to a conflict with a package in K < N, we will record all + // of them as REJECT in depth = K. + // + // You can follow the reason chain upwards as long as the depth + // doesn't increase to unwind. + // + // Reasons < 0 are package ID, reasons > 0 are version IDs. + Reason reason{}; + + // \brief The depth at which the decision has been taken + depth_type depth{0}; + + // \brief This essentially describes the install state in RFC2119 terms. + Decision decision{Decision::NONE}; + + // \brief Any hint. + Hint hint{Hint::NONE}; +}; -- cgit v1.2.3