summaryrefslogtreecommitdiff
path: root/apt-pkg
diff options
context:
space:
mode:
Diffstat (limited to 'apt-pkg')
-rw-r--r--apt-pkg/contrib/macros.h8
-rw-r--r--apt-pkg/edsp.cc2
-rw-r--r--apt-pkg/solver3.cc1035
-rw-r--r--apt-pkg/solver3.h596
4 files changed, 857 insertions, 784 deletions
diff --git a/apt-pkg/contrib/macros.h b/apt-pkg/contrib/macros.h
index 08e7aeb72..1a76ef60a 100644
--- a/apt-pkg/contrib/macros.h
+++ b/apt-pkg/contrib/macros.h
@@ -33,6 +33,14 @@
#define likely(x) (x)
#define unlikely(x) (x)
#endif
+
+// Asserts that the result of expr is true
+#define must_succeed(expr) ({ \
+ auto result = (expr); \
+ if (unlikely(not result)) \
+ fprintf(stderr, "%s:%d: %s: Assertion `%s` failed.\n", __FILE__, __LINE__, __FUNCTION__, #expr), abort(); \
+ result; \
+})
#endif
#if APT_GCC_VERSION >= 0x0300
diff --git a/apt-pkg/edsp.cc b/apt-pkg/edsp.cc
index 6c9c3f3ee..2d7fdcc3c 100644
--- a/apt-pkg/edsp.cc
+++ b/apt-pkg/edsp.cc
@@ -796,7 +796,7 @@ bool EDSP::ResolveExternal(const char* const solver, pkgDepCache &Cache,
unsigned int const flags, OpProgress *Progress) {
if (strstr(solver, "3.") == solver)
{
- APT::Solver s(Cache.GetCache(), Cache.GetPolicy(), (EDSP::Request::Flags) flags);
+ APT::Solver::DependencySolver s(Cache.GetCache(), Cache.GetPolicy(), (EDSP::Request::Flags)flags);
FileFd output;
bool res = true;
if (Progress != NULL)
diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc
index 4d7e0ff0b..096cbb521 100644
--- a/apt-pkg/solver3.cc
+++ b/apt-pkg/solver3.cc
@@ -38,188 +38,28 @@
#include <iomanip>
#include <sstream>
-// FIXME: Helpers stolen from DepCache, please give them back.
-struct APT::Solver::CompareProviders3 /*{{{*/
-{
- pkgCache &Cache;
- pkgDepCache::Policy &Policy;
- pkgCache::PkgIterator const Pkg;
- APT::Solver &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<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
+namespace APT::Solver
{
- std::unique_ptr<APT::CacheFilter::Matcher> 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.
-/*}}}*/
-
-APT::Solver::Solver(pkgCache &cache, pkgDepCache::Policy &policy, EDSP::Request::Flags requestFlags)
+Solver::Solver(pkgCache &cache)
: cache(cache),
- policy(policy),
rootState(new State),
pkgStates(cache),
- verStates(cache),
- pkgObsolete(cache),
- priorities(cache),
- candidates(cache),
- requestFlags(requestFlags)
+ verStates(cache)
{
// 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>));
+ static_assert(std::is_trivially_destructible_v<Trail>);
+ static_assert(sizeof(Var) == sizeof(map_pointer<pkgCache::Package>));
+ static_assert(sizeof(Var) == sizeof(map_pointer<pkgCache::Version>));
// Root state is "true".
- rootState->decision = Decision::MUST;
+ rootState->assignment = LiftedBool::True;
}
-APT::Solver::~Solver() = default;
+Solver::~Solver() = default;
// This function determines if a work item is less important than another.
-bool APT::Solver::Work::operator<(APT::Solver::Work const &b) const
+bool Solver::Work::operator<(Solver::Work const &b) const
{
if ((not clause->optional && size < 2) != (not b.clause->optional && b.size < 2))
return not b.clause->optional && b.size < 2;
@@ -280,40 +120,45 @@ std::string APT::Solver::Clause::toString(pkgCache &cache, bool pretty, bool sho
return out;
}
-std::string APT::Solver::Work::toString(pkgCache &cache) const
+std::string 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 << "Item (" << ssize_t(size <= clause->solutions.size() ? size : -1) << "@" << level << ") ";
out << clause->toString(cache);
return out.str();
}
-inline APT::Solver::Var APT::Solver::bestReason(APT::Solver::Clause const *clause, APT::Solver::Var var) const
+inline Var Solver::bestReason(Clause const *clause, Var var) const
{
if (not clause)
return Var{};
if (clause->reason == var)
for (auto choice : clause->solutions)
{
- if (clause->negative && (*this)[choice].decision == Decision::MUST)
+ if (clause->negative && value(choice) == LiftedBool::True)
return choice;
- if (not clause->negative && (*this)[choice].decision == Decision::MUSTNOT)
+ if (not clause->negative && value(choice) == LiftedBool::False)
return choice;
}
return clause->reason;
}
+inline LiftedBool Solver::value(Lit lit) const
+{
+ return lit.sign() ? ~(*this)[lit.var()].assignment : (*this)[lit.var()].assignment;
+}
+
// Prints an implication graph part of the form A -> B -> C, possibly with "not"
-std::string APT::Solver::WhyStr(Var reason) const
+std::string Solver::WhyStr(Var reason) const
{
std::vector<std::string> out;
while (not reason.empty())
{
- if ((*this)[reason].decision == Decision::MUSTNOT)
+ if (value(reason) == LiftedBool::False)
out.push_back(std::string("not ") + reason.toString(cache));
else
out.push_back(reason.toString(cache));
@@ -328,31 +173,31 @@ std::string APT::Solver::WhyStr(Var reason) const
return outstr;
}
-std::string APT::Solver::LongWhyStr(Var var, bool decision, const Clause *rclause, std::string prefix, std::unordered_set<Var> &seen) const
+std::string Solver::LongWhyStr(Var var, bool assignment, const Clause *rclause, std::string prefix, std::unordered_set<Var> &seen) const
{
std::ostringstream out;
// Helper function to nicely print more details than just "install/do not install", such as "removal", "upgrade", "downgrade", "install"
- auto printSelection = [this](Var var, bool decision)
+ auto printSelection = [this](Var var, bool assignment)
{
std::string s;
- if (auto pkg = var.Pkg(cache); not decision && pkg && pkg->CurrentVer)
+ if (auto pkg = var.Pkg(cache); not assignment && pkg && pkg->CurrentVer)
strprintf(s, "%s is selected for removal", var.toString(cache).c_str());
- else if (auto ver = var.Ver(cache); decision && ver && ver.ParentPkg().CurrentVer() && ver.ParentPkg().CurrentVer() != ver)
+ else if (auto ver = var.Ver(cache); assignment && ver && ver.ParentPkg().CurrentVer() && ver.ParentPkg().CurrentVer() != ver)
{
if (cache.VS->CmpVersion(ver.ParentPkg().CurrentVer().VerStr(), ver.VerStr()) < 0)
strprintf(s, "%s is selected as an upgrade", var.toString(cache).c_str());
else
strprintf(s, "%s is selected as a downgrade", var.toString(cache).c_str());
}
- else if (not decision)
+ else if (not assignment)
strprintf(s, "%s is not selected for install", var.toString(cache).c_str());
else
strprintf(s, "%s is selected for install", var.toString(cache).c_str());
return s;
};
- // Helper: Recurse into all of the children of the clause and print the decision for them.
+ // Helper: Recurse into all of the children of the clause and print the assignment for them.
auto recurseChildren = [&](const Clause *clause, Var skip = Var())
{
if (clause->solutions.empty())
@@ -362,16 +207,16 @@ std::string APT::Solver::LongWhyStr(Var var, bool decision, const Clause *rclaus
if (choice == skip)
continue;
- if ((*this)[choice].decision == Decision::NONE)
+ if (value(choice) == LiftedBool::Undefined)
out << prefix << "- " << choice.toString(cache) << " is undecided\n";
else
- out << prefix << "- " << LongWhyStr(choice, (*this)[choice].decision == Decision::MUST, (*this)[choice].reason, prefix + " ", seen).substr(prefix.size() + 2);
+ out << prefix << "- " << LongWhyStr(choice, value(choice) == LiftedBool::True, (*this)[choice].reason, prefix + " ", seen).substr(prefix.size() + 2);
}
};
// Inverse version selection clauses that select the package if the version is selected,
// such as pkg=ver -> pkg, are irrelevant for the user, skip them
- if (var.Pkg() && decision && rclause && rclause->group == Group::SelectVersion)
+ if (var.Pkg() && assignment && rclause && rclause->group == Group::SelectVersion)
{
var = rclause->reason;
rclause = (*this)[var].reason;
@@ -380,25 +225,25 @@ std::string APT::Solver::LongWhyStr(Var var, bool decision, const Clause *rclaus
// No reason given, probably a user request or manually installed or essential or whatnot.
if (not rclause)
{
- out << prefix << printSelection(var, decision) << "\n";
+ out << prefix << printSelection(var, assignment) << "\n";
return out.str();
}
- // We could be called with a decision we tried to make but failed due to a conflict;
- // this checks if it is the real decision.
- if ((*this)[var].decision != Decision::NONE && decision == ((*this)[var].decision == Decision::MUST) && (*this)[var].reason == rclause)
+ // We could be called with a assignment we tried to make but failed due to a conflict;
+ // this checks if it is the real assignment.
+ if (value(var) != LiftedBool::Undefined && assignment == (value(var) == LiftedBool::True) && (*this)[var].reason == rclause)
{
- // If we have seen the real decision before; we dont't need to print it again.
+ // If we have seen the real assignment before; we dont't need to print it again.
if (seen.find(var) != seen.end())
{
- out << prefix << printSelection(var, decision) << " as above\n";
+ out << prefix << printSelection(var, assignment) << " as above\n";
return out.str();
}
seen.insert(var);
}
// A package was decided "not install" due to a positive clause, so the clause is unsat.
- if (not decision && rclause && not rclause->negative)
+ if (not assignment && rclause && not rclause->negative)
{
out << prefix << rclause->toString(cache, true) << "\n";
out << prefix << "but none of the choices are installable:\n";
@@ -406,13 +251,13 @@ std::string APT::Solver::LongWhyStr(Var var, bool decision, const Clause *rclaus
return out.str();
}
- // Build the strongest path from a root to our decision leaf
+ // Build the strongest path from a root to our assignment leaf
std::vector<Var> path;
for (auto reason = bestReason(rclause, var); not reason.empty(); reason = bestReason((*this)[reason].reason, reason))
path.push_back(reason);
// Render the strong reasoning path
- out << prefix << printSelection(var, decision) << " because:\n";
+ out << prefix << printSelection(var, assignment) << " because:\n";
auto w = std::to_string(path.size() + 1).size();
size_t i = 1;
for (auto it = path.rbegin(); it != path.rend(); ++it, ++i)
@@ -428,7 +273,7 @@ std::string APT::Solver::LongWhyStr(Var var, bool decision, const Clause *rclaus
{
if ((it + 1) == path.rend() || seen.find(*(it + 1)) == seen.end())
{
- out << prefix << (i == 1 ? "" : "1-") << i << ". " << printSelection(*it, state.decision == Decision::MUST) << " as above\n";
+ out << prefix << (i == 1 ? "" : "1-") << i << ". " << printSelection(*it, state.assignment == LiftedBool::True) << " as above\n";
}
continue;
}
@@ -437,13 +282,13 @@ std::string APT::Solver::LongWhyStr(Var var, bool decision, const Clause *rclaus
{
out << prefix << std::setw(w) << i << ". " << state.reason->toString(cache, true) << "\n";
if (state.reason->solutions.size() > 1)
- out << prefix << std::setw(w) << " " << " [selected " << it->toString(cache) << " for " << (state.decision == Decision::MUST ? "install" : "remove") << "]\n";
+ out << prefix << std::setw(w) << " " << " [selected " << it->toString(cache) << " for " << (state.assignment == LiftedBool::True ? "install" : "remove") << "]\n";
}
else
- out << prefix << std::setw(w) << i << ". " << printSelection(*it, state.decision == Decision::MUST) << "\n";
+ out << prefix << std::setw(w) << i << ". " << printSelection(*it, state.assignment == LiftedBool::True) << "\n";
}
- // Print the leaf. We can't have the leaf in the path because we might be called for an attempted decision
+ // Print the leaf. We can't have the leaf in the path because we might be called for an attempted assignment
// that conflicts with the actual assignment (to simplify: we marked X for not install, then we process Y depends X
// and try to mark X and reach the conflict, we are called with "X" and the "Y depends X" clause).
out << prefix << std::setw(w) << i << ". " << rclause->toString(cache, true) << "\n";
@@ -490,122 +335,58 @@ std::string APT::Solver::LongWhyStr(Var var, bool decision, const Clause *rclaus
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 APT::Solver::ObsoletedByNewerSourceVersion(pkgCache::VerIterator cand) const
+bool Solver::Assume(Lit lit, const Clause *reason)
{
- 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;
+ trailLim.push_back(trail.size());
+ return Enqueue(lit, std::move(reason));
}
-bool APT::Solver::Obsolete(pkgCache::PkgIterator pkg, bool AllowManual) const
+bool Solver::Enqueue(Lit lit, const Clause *reason)
{
- if ((*this)[pkg].flags.manual && not AllowManual)
- return false;
- if (pkgObsolete[pkg] != 0)
- return pkgObsolete[pkg] == 2;
+ assert(not lit.empty());
- auto ver = GetCandidateVer(pkg);
+ auto &state = (*this)[lit.var()];
+ auto assignment = lit.sign() ? LiftedBool::False : LiftedBool::True;
- if (ver.end() && not StrictPinning)
- ver = pkg.VersionList();
- if (ver.end())
+ if (state.assignment != LiftedBool::Undefined)
{
- 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 APT::Solver::Assume(Var var, bool decision, const Clause *reason)
-{
- choices.push_back(solved.size());
- return Enqueue(var, decision, std::move(reason));
-}
-
-bool APT::Solver::Enqueue(Var var, bool decision, const Clause *reason)
-{
- auto &state = (*this)[var];
- auto decisionCast = decision ? Decision::MUST : Decision::MUSTNOT;
-
- if (state.decision != Decision::NONE)
- {
- if (state.decision != decisionCast)
+ if (state.assignment != assignment)
{
std::ostringstream err;
- err << "Unable to satisfy dependencies. Reached two conflicting decisions:" << "\n";
+ err << "Unable to satisfy dependencies. Reached two conflicting assignments:" << "\n";
std::unordered_set<Var> seen;
- err << "1. " << LongWhyStr(var, state.decision == Decision::MUST, state.reason, " ", seen).substr(3) << "\n";
- err << "2. " << LongWhyStr(var, decision, reason, " ", seen).substr(3);
+ err << "1. " << LongWhyStr(lit.var(), state.assignment == LiftedBool::True, state.reason, " ", seen).substr(3) << "\n";
+ err << "2. " << LongWhyStr(lit.var(), not lit.sign(), reason, " ", seen).substr(3);
return _error->Error("%s", err.str().c_str());
}
return true;
}
- state.decision = decisionCast;
- state.depth = depth();
+ state.assignment = assignment;
+ state.level = decisionLevel();
state.reason = reason;
+ // FIXME: Adjust call to bestReason to use lit
if (unlikely(debug >= 1))
- std::cerr << "[" << depth() << "] " << (decision ? "Install" : "Reject") << ":" << var.toString(cache) << " (" << WhyStr(bestReason(reason, var)) << ")\n";
+ std::cerr << "[" << decisionLevel() << "] " << (lit.sign() ? "Reject" : "Install") << ":" << lit.var().toString(cache) << " (" << WhyStr(bestReason(reason, lit.var())) << ")\n";
- solved.push_back(Solved{var, std::nullopt});
- propQ.push(var);
+ trail.push_back(Trail{lit.var(), std::nullopt});
+ propQ.push(lit.var());
return true;
}
-bool APT::Solver::Propagate()
+bool Solver::Propagate()
{
while (!propQ.empty())
{
Var var = propQ.front();
propQ.pop();
- if ((*this)[var].decision == Decision::MUST)
+ if (value(var) == LiftedBool::True)
{
Discover(var);
for (auto &clause : (*this)[var].clauses)
- if (not AddWork(Work{clause.get(), depth()}))
+ if (not AddWork(Work{clause.get(), decisionLevel()}))
return false;
for (auto rclause : (*this)[var].rclauses)
{
@@ -613,37 +394,37 @@ bool APT::Solver::Propagate()
continue;
if (unlikely(debug >= 3))
std::cerr << "Propagate " << var.toString(cache) << " to NOT " << rclause->reason.toString(cache) << " for dep " << const_cast<Clause *>(rclause)->toString(cache) << std::endl;
- if (not Enqueue(rclause->reason, false, rclause))
+ if (not Enqueue(~rclause->reason, rclause))
return false;
}
}
- else if ((*this)[var].decision == Decision::MUSTNOT)
+ else if (value(var) == LiftedBool::False)
{
for (auto rclause : (*this)[var].rclauses)
{
if (rclause->negative || rclause->reason.empty())
continue;
- if ((*this)[rclause->reason].decision == Decision::MUSTNOT)
+ if (value(rclause->reason) == LiftedBool::False)
continue;
auto count = std::count_if(rclause->solutions.begin(), rclause->solutions.end(), [this](auto var)
- { return (*this)[var].decision != Decision::MUSTNOT; });
+ { return value(var) != LiftedBool::False; });
- if (count == 1 && (*this)[rclause->reason].decision == Decision::MUST)
+ if (count == 1 && value(rclause->reason) == LiftedBool::True)
{
if (unlikely(debug >= 3))
std::cerr << "Propagate NOT " << var.toString(cache) << " to unit clause " << rclause->toString(cache);
if (rclause->optional)
{
// Enqueue duplicated item, this will ensure we see it at the correct time
- if (not AddWork(Work{rclause, depth()}))
+ if (not AddWork(Work{rclause, decisionLevel()}))
return false;
}
else
{
// Find the variable that must be chosen and enqueue it as a fact
for (auto sol : rclause->solutions)
- if ((*this)[sol].decision == Decision::NONE && not Enqueue(sol, true, rclause))
+ if (value(sol) == LiftedBool::Undefined && not Enqueue(sol, rclause))
return false;
}
continue;
@@ -654,7 +435,7 @@ bool APT::Solver::Propagate()
if (unlikely(debug >= 3))
std::cerr << "Propagate NOT " << var.toString(cache) << " to " << rclause->reason.toString(cache) << " for dep " << const_cast<Clause *>(rclause)->toString(cache) << std::endl;
- if (not Enqueue(rclause->reason, false, rclause)) // Last version invalidated
+ if (not Enqueue(~rclause->reason, rclause)) // Last version invalidated
return false;
}
}
@@ -662,6 +443,348 @@ bool APT::Solver::Propagate()
return true;
}
+void Solver::UndoOne()
+{
+ auto trailItem = trail.back();
+
+ if (unlikely(debug >= 4))
+ std::cerr << "Undoing a single assignment\n";
+
+ if (not trailItem.assigned.empty())
+ {
+ if (unlikely(debug >= 4))
+ std::cerr << "Unassign " << trailItem.assigned.toString(cache) << "\n";
+ auto &state = (*this)[trailItem.assigned];
+ state.assignment = LiftedBool::Undefined;
+ state.reason = nullptr;
+ state.reasonStr = nullptr;
+ state.level = 0;
+ }
+
+ if (auto work = trailItem.work)
+ {
+ if (unlikely(debug >= 4))
+ std::cerr << "Adding work item " << work->toString(cache) << std::endl;
+
+ must_succeed(AddWork(std::move(*work)));
+ }
+
+ 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 level.
+ // 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.level > 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 (_error->PendingError() || not Propagate())
+ {
+ if (not Pop())
+ return false;
+ }
+
+ if (work.empty())
+ break;
+
+ auto item = work.front();
+ std::pop_heap(work.begin(), work.end());
+ work.pop_back();
+ // This item has been replaced with a new one. Remove it.
+ if (item.erased)
+ continue;
+
+ 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;
+ }
+ else if (auto candidate = std::find_if(item.clause->solutions.begin(), item.clause->solutions.end(), [this](auto ver)
+ { return value(ver) == LiftedBool::Undefined; });
+ candidate != item.clause->solutions.end())
+ {
+ if (unlikely(debug >= 3))
+ std::cerr << item.toString(cache) << "\n"
+ << "(try it: " << candidate->toString(cache) << ")\n";
+ must_succeed(Assume(*candidate, item.clause));
+ }
+ else if (item.clause->optional)
+ {
+ if (unlikely(debug >= 1))
+ std::cerr << item.toString(cache) << "\n";
+ }
+ else
+ {
+ if (unlikely(debug >= 1))
+ std::cerr << item.toString(cache) << "\n";
+ // Enqueue produces the right error message for us here, given that reason has been assigned true already...
+ assert(value(item.clause->reason) == LiftedBool::True);
+ must_succeed(not Enqueue(~item.clause->reason, item.clause));
+ assert(value(item.clause->reason) == LiftedBool::True);
+ }
+ // Must push to trail after any Assume() above.
+ trail.push_back(Trail{Var(), item});
+ }
+
+ 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<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)) {};
+ ~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)
@@ -679,7 +802,7 @@ static bool SameOrGroup(pkgCache::DepIterator a, pkgCache::DepIterator b)
return not(a->CompareOp & pkgCache::Dep::Or) && not(b->CompareOp & pkgCache::Dep::Or);
}
-const APT::Solver::Clause *APT::Solver::RegisterClause(Clause &&clause)
+const Clause *DependencySolver::RegisterClause(Clause &&clause)
{
auto &clauses = (*this)[clause.reason].clauses;
pkgCache::DepIterator dep(cache, clause.dep);
@@ -703,17 +826,15 @@ const APT::Solver::Clause *APT::Solver::RegisterClause(Clause &&clause)
earlierDep.TargetPkg() != dep.TargetPkg())
continue;
if (std::none_of(earlierClause->solutions.begin(), earlierClause->solutions.end(), [&clause](auto earlierSol)
- { return std::find(clause.solutions.begin(),
- clause.solutions.end(),
- earlierSol) != clause.solutions.end(); }))
+ { return std::ranges::contains(clause.solutions,
+ earlierSol); }))
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(); });
+ { return not std::ranges::contains(clause.solutions,
+ earlierSol); });
earlierClause->merged.push_front(clause);
merged = true;
@@ -722,9 +843,8 @@ const APT::Solver::Clause *APT::Solver::RegisterClause(Clause &&clause)
{
// 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(); });
+ { return not std::ranges::contains(earlierClause->solutions,
+ sol); });
// Remove recursion here, such that we display correctly (if we ever display anywhere...)
auto earlierClauseCopy = *earlierClause;
@@ -744,7 +864,74 @@ const APT::Solver::Clause *APT::Solver::RegisterClause(Clause &&clause)
return inserted.get();
}
-void APT::Solver::Discover(Var var)
+// 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;
+}
+void DependencySolver::Discover(Var var)
{
assert(discoverQ.empty());
discoverQ.push(var);
@@ -811,15 +998,15 @@ void APT::Solver::Discover(Var var)
}
}
- // Recursively discover everything else that is not already FALSE by fact (MUSTNOT at depth 0)
+ // Recursively discover everything else that is not already FALSE by fact (False at level 0)
for (auto const &clause : state.clauses)
for (auto const &var : clause->solutions)
- if ((*this)[var].decision != Decision::MUSTNOT || (*this)[var].depth > 0)
+ if (value(var) != LiftedBool::False || (*this)[var].level > 0)
discoverQ.push(var);
}
}
-void APT::Solver::RegisterCommonDependencies(pkgCache::PkgIterator Pkg)
+void DependencySolver::RegisterCommonDependencies(pkgCache::PkgIterator Pkg)
{
for (auto dep = Pkg.VersionList().DependsList(); not dep.end();)
{
@@ -846,7 +1033,7 @@ void APT::Solver::RegisterCommonDependencies(pkgCache::PkgIterator Pkg)
}
}
-APT::Solver::Clause APT::Solver::TranslateOrGroup(pkgCache::DepIterator start, pkgCache::DepIterator end, Var reason)
+Clause DependencySolver::TranslateOrGroup(pkgCache::DepIterator start, pkgCache::DepIterator end, Var reason)
{
// Non-important dependencies can only be installed if they are currently satisfied, see the check further
// below once we have calculated all possible solutions.
@@ -984,204 +1171,8 @@ APT::Solver::Clause APT::Solver::TranslateOrGroup(pkgCache::DepIterator start, p
return clause;
}
-void APT::Solver::Push(Var var, Work work)
-{
- if (unlikely(debug >= 2))
- std::cerr << "Trying choice for " << work.toString(cache) << std::endl;
-
- choices.push_back(solved.size());
- solved.push_back(Solved{var, std::move(work)});
-}
-
-void APT::Solver::UndoOne()
-{
- auto solvedItem = solved.back();
-
- if (unlikely(debug >= 4))
- std::cerr << "Undoing a single decision\n";
-
- if (not solvedItem.assigned.empty())
- {
- if (unlikely(debug >= 4))
- std::cerr << "Unassign " << solvedItem.assigned.toString(cache) << "\n";
- auto &state = (*this)[solvedItem.assigned];
- state.decision = Decision::NONE;
- state.reason = nullptr;
- state.reasonStr = nullptr;
- state.depth = 0;
- }
-
- if (auto work = solvedItem.work)
- {
- if (unlikely(debug >= 4))
- std::cerr << "Adding work item " << work->toString(cache) << std::endl;
-
- if (not AddWork(std::move(*work)))
- abort();
- }
-
- solved.pop_back();
-
- // FIXME: Add the undo handling here once we have watchers.
-}
-
-bool APT::Solver::Pop()
-{
- if (depth() == 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 (choices.back() == solved.size())
- {
- choices.pop_back();
- return true;
- }
-
- assert(choices.back() < solved.size());
- int itemsToUndo = solved.size() - choices.back();
- auto choice = solved[choices.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.
- choices.pop_back();
- work.erase(std::remove_if(work.begin(), work.end(), [this](Work &w) -> bool
- { return w.depth > depth() || 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, false, {}))
- return false;
-
- (*this)[choice].reasonStr = "backtracked";
-
- if (unlikely(debug >= 2))
- std::cerr << "Backtracked to choice " << choice.toString(cache) << "\n";
-
- return true;
-}
-
-bool APT::Solver::AddWork(Work &&w)
-{
- if (w.clause->negative)
- {
- for (auto var : w.clause->solutions)
- if (not Enqueue(var, false, 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], true, w.clause);
-
- 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());
- }
- return true;
-}
-
-bool APT::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();
- solved.push_back(Solved{Var(), item});
-
- 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.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 ((*this)[sol].decision == Decision::MUSTNOT)
- {
- 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, true, 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<Var> 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 APT::Solver::FromDepCache(pkgDepCache &depcache)
+bool DependencySolver::FromDepCache(pkgDepCache &depcache)
{
DefaultRootSetFunc2 rootSet(&cache);
std::vector<Var> manualPackages;
@@ -1195,7 +1186,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache)
bool isPhasing = IsUpgrade && depcache.PhasingApplied(P) && not isForced;
for (auto V = P.VersionList(); not V.end(); ++V)
if (P.CurrentVer() != V && (depcache.GetCandidateVersion(P) != V || isPhasing))
- if (not Enqueue(Var(V), false, {}))
+ if (not Enqueue(~Var(V), {}))
return false;
}
}
@@ -1215,7 +1206,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache)
{
if (unlikely(debug >= 1))
std::cerr << "Hold " << P.FullName() << "\n";
- if (P->CurrentVer ? not Enqueue(Var(P.CurrentVer()), true) : not Enqueue(Var(P), false))
+ if (P->CurrentVer ? not Enqueue(Var(P.CurrentVer())) : not Enqueue(~Var(P)))
return false;
}
else if (state.Delete() // Normal delete request.
@@ -1225,7 +1216,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache)
{
if (unlikely(debug >= 1))
std::cerr << "Delete " << P.FullName() << "\n";
- if (not Enqueue(Var(P), false))
+ if (not Enqueue(~Var(P)))
return false;
}
else if (state.Install() || (state.Keep() && P->CurrentVer))
@@ -1251,7 +1242,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache)
if (not isOptional)
{
// Pre-empt the non-optional requests, as we don't want to queue them, we can just "unit propagate" here.
- if (depcache[P].Keep() ? not Enqueue(Var(P), true) : not Enqueue(Var(depcache.GetCandidateVersion(P)), true))
+ if (depcache[P].Keep() ? not Enqueue(Var(P)) : not Enqueue(Var(depcache.GetCandidateVersion(P))))
return false;
}
else
@@ -1259,7 +1250,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache)
Clause w{Var(), Group, isOptional};
w.solutions.push_back(Var(P));
auto insertedW = RegisterClause(std::move(w));
- if (insertedW && not AddWork(Work{insertedW, depth()}))
+ if (insertedW && not AddWork(Work{insertedW, decisionLevel()}))
return false;
if (not isAuto)
@@ -1275,7 +1266,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache)
shortcircuit.solutions.push_back(Var(V));
std::stable_sort(shortcircuit.solutions.begin(), shortcircuit.solutions.end(), CompareProviders3{cache, policy, P, *this});
auto insertedShort = RegisterClause(std::move(shortcircuit));
- if (insertedShort && not AddWork(Work{insertedShort, depth()}))
+ if (insertedShort && not AddWork(Work{insertedShort, decisionLevel()}))
return false;
// Discovery here is needed so the shortcircuit clause can actually become unit.
@@ -1294,7 +1285,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache)
if (unlikely(debug >= 1))
std::cerr << "Install essential package " << P << std::endl;
auto inserted = RegisterClause(std::move(w));
- if (inserted && not AddWork(Work{inserted, depth()}))
+ if (inserted && not AddWork(Work{inserted, decisionLevel()}))
return false;
}
}
@@ -1305,15 +1296,14 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache)
std::stable_sort(manualPackages.begin(), manualPackages.end(), CompareProviders3{cache, policy, {}, *this});
for (auto assumption : manualPackages)
{
- if (not Assume(assumption, true, {}) || not Propagate())
- if (not Pop())
- abort();
+ if (not Assume(assumption, {}) || not Propagate())
+ must_succeed(Pop());
}
return true;
}
-bool APT::Solver::ToDepCache(pkgDepCache &depcache) const
+bool DependencySolver::ToDepCache(pkgDepCache &depcache) const
{
FastContiguousCacheMap<pkgCache::Package, bool> movedManual(cache);
pkgDepCache::ActionGroup group(depcache);
@@ -1321,11 +1311,11 @@ bool APT::Solver::ToDepCache(pkgDepCache &depcache) const
{
depcache[P].Marked = 0;
depcache[P].Garbage = 0;
- if ((*this)[P].decision == Decision::MUST)
+ if (value(Var(P)) == LiftedBool::True)
{
pkgCache::VerIterator cand;
for (auto V = P.VersionList(); cand.end() && not V.end(); V++)
- if ((*this)[V].decision == Decision::MUST)
+ if (value(Var(V)) == LiftedBool::True)
cand = V;
auto reasonClause = (*this)[cand].reason;
@@ -1379,9 +1369,9 @@ bool APT::Solver::ToDepCache(pkgDepCache &depcache) const
}
// Command-line
-std::string APT::Solver::InternalCliWhy(pkgDepCache &cache, pkgCache::PkgIterator pkg, bool decision)
+std::string DependencySolver::InternalCliWhy(pkgDepCache &cache, pkgCache::PkgIterator pkg, bool assignment)
{
- APT::Solver solver(cache.GetCache(), cache.GetPolicy(), EDSP::Request::Flags(0));
+ DependencySolver solver(cache.GetCache(), cache.GetPolicy(), EDSP::Request::Flags(0));
// In case nothing has a positive dependency on pkg it may not actually be discovered in a `why-not`
// scenario, so make sure we discover it explicitly.
solver.Discover(Var(pkg));
@@ -1389,11 +1379,12 @@ std::string APT::Solver::InternalCliWhy(pkgDepCache &cache, pkgCache::PkgIterato
return "";
std::unordered_set<Var> seen;
std::string buf;
- if (solver[Var(pkg)].decision == Decision::NONE)
+ if (solver[Var(pkg)].assignment == LiftedBool::Undefined)
return strprintf(buf, "%s is undecided\n", pkg.FullName().c_str()), buf;
- if (decision && solver[Var(pkg)].decision != Decision::MUST)
+ if (assignment && solver[Var(pkg)].assignment != LiftedBool::True)
return strprintf(buf, "%s is not actually marked for install\n", pkg.FullName().c_str()), buf;
- if (not decision && solver[Var(pkg)].decision == Decision::MUST)
+ if (not assignment && solver[Var(pkg)].assignment == LiftedBool::True)
return strprintf(buf, "%s is actually marked for install\n", pkg.FullName().c_str()), buf;
- return solver.LongWhyStr(Var(pkg), decision, solver[Var(pkg)].reason, "", seen);
+ return solver.LongWhyStr(Var(pkg), assignment, solver[Var(pkg)].reason, "", seen);
}
+} // namespace APT::Solver
diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h
index 45b55d962..4a2b4ac8d 100644
--- a/apt-pkg/solver3.h
+++ b/apt-pkg/solver3.h
@@ -22,7 +22,7 @@
template <typename T> struct always_false : std::false_type {};
-namespace APT
+namespace APT::Solver
{
/**
@@ -59,6 +59,10 @@ class ContiguousCacheMap
V &operator[](const K *key) { return data_[key->ID]; }
const V &operator[](const K *key) const { return data_[key->ID]; }
~ContiguousCacheMap() { delete[] data_; }
+
+ // Delete copy constructors for memory safety (rule of 3)
+ ContiguousCacheMap(const ContiguousCacheMap &) = delete;
+ ContiguousCacheMap &operator=(const ContiguousCacheMap &) = delete;
};
/**
@@ -67,6 +71,203 @@ class ContiguousCacheMap
template <typename K, typename V>
using FastContiguousCacheMap = ContiguousCacheMap<K, V, true>;
+struct Lit;
+
+// \brief Groups of works, these are ordered.
+//
+// Later items will be skipped if they are optional, or we will when backtracking,
+// try a different choice for them.
+enum class Group : uint8_t
+{
+ HoldOrDelete,
+
+ // Satisfying dependencies on entirely new packages first is a good idea because
+ // it may contain replacement packages like libfoo1t64 whereas we later will see
+ // Depends: libfoo1 where libfoo1t64 Provides libfoo1 and we'd have to choose.
+ SatisfyNew,
+ Satisfy,
+ // On a similar note as for SatisfyNew, if the dependency contains obsolete packages
+ // try it last.
+ SatisfyObsolete,
+
+ // Select a version of a package chosen for install.
+ SelectVersion,
+
+ // My intuition tells me that we should try to schedule upgrades first, then
+ // any non-obsolete installed packages, and only finally obsolete ones, such
+ // that newer packages guide resolution of dependencies for older ones, they
+ // may have more stringent dependencies, like a (>> 2) whereas an obsolete
+ // package may have a (>> 1), for example.
+ UpgradeManual,
+ InstallManual,
+ ObsoleteManual,
+
+ // Automatically installed packages must come last in the group, this allows
+ // us to see if they were installed as a dependency of a manually installed package,
+ // allowing a simple implementation of an autoremoval code.
+ UpgradeAuto,
+ KeepAuto,
+ ObsoleteAuto,
+
+ // Satisfy optional dependencies that were previously satisfied but won't otherwise be installed
+ SatisfySuggests,
+};
+
+// \brief This essentially describes the install state in RFC2119 terms.
+enum class LiftedBool : uint8_t
+{
+ // \brief We have not made a choice about the package yet
+ Undefined,
+ // \brief We need to install this package
+ True,
+ // \brief We cannot install this package (need conflicts with it)
+ False,
+};
+
+/**
+ * \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; and we want to generically refer to
+ * both packages and versions as variables, hence this class was added.
+ *
+ */
+struct Var
+{
+ uint32_t value;
+
+ explicit constexpr Var(uint32_t value = 0) : value{value} {}
+ explicit Var(pkgCache::PkgIterator const &Pkg) : value(uint32_t(Pkg.MapPointer()) << 1) {}
+ explicit Var(pkgCache::VerIterator const &Ver) : value(uint32_t(Ver.MapPointer()) << 1 | 1) {}
+
+ inline constexpr bool isVersion() const { return value & 1; }
+ inline constexpr uint32_t mapPtr() const { return value >> 1; }
+
+ // \brief Return the package, if any, otherwise 0.
+ map_pointer<pkgCache::Package> Pkg() const
+ {
+ return isVersion() ? 0 : map_pointer<pkgCache::Package>{mapPtr()};
+ }
+ // \brief Return the version, if any, otherwise 0.
+ map_pointer<pkgCache::Version> Ver() const
+ {
+ return isVersion() ? map_pointer<pkgCache::Version>{mapPtr()} : 0;
+ }
+ // \brief Return the package iterator if storing a package, or an empty one
+ pkgCache::PkgIterator Pkg(pkgCache &cache) const
+ {
+ return isVersion() ? pkgCache::PkgIterator() : pkgCache::PkgIterator(cache, cache.PkgP + Pkg());
+ }
+ // \brief Return the version iterator if storing a package, or an empty end.
+ pkgCache::VerIterator Ver(pkgCache &cache) const
+ {
+ return isVersion() ? pkgCache::VerIterator(cache, cache.VerP + Ver()) : pkgCache::VerIterator();
+ }
+ // \brief Return a package, cast from version if needed
+ pkgCache::PkgIterator CastPkg(pkgCache &cache) const
+ {
+ return isVersion() ? Ver(cache).ParentPkg() : Pkg(cache);
+ }
+ // \brief Check if there is no reason.
+ constexpr bool empty() const { return value == 0; }
+ constexpr bool operator!=(Var const other) const noexcept { return value != other.value; }
+ constexpr bool operator==(Var const other) const noexcept { return value == other.value; }
+
+ /// \brief Negate
+ constexpr Lit operator~() const;
+
+ std::string toString(pkgCache &cache) const
+ {
+ if (auto P = Pkg(cache); not P.end())
+ return P.FullName();
+ if (auto V = Ver(cache); not V.end())
+ return V.ParentPkg().FullName() + "=" + V.VerStr();
+ return "(root)";
+ }
+};
+
+/**
+ * \brief A literal is a variable with a sign.
+ *
+ * A literal 'A' means 'install A' whereas a literal '-A' means 'do not install A'.
+ */
+struct Lit
+{
+ private:
+ friend struct std::hash<Lit>;
+ // Private constructor from a number, to be used with operator~
+ explicit constexpr Lit(int32_t value) : value{value} {}
+ int32_t value;
+
+ public:
+ // SAFETY: value must be 31 bit, one bit is needed for the sign.
+ constexpr Lit(Var var) : value{static_cast<int32_t>(var.value)} {}
+
+ // Accessors
+ constexpr Var var() const { return Var(std::abs(value)); }
+ constexpr bool sign() const { return value < 0; }
+ constexpr Lit operator~() const { return Lit(-value); }
+
+ // Properties
+ constexpr bool empty() const { return value == 0; }
+ constexpr bool operator!=(Lit const other) const noexcept { return value != other.value; }
+ constexpr bool operator==(Lit const other) const noexcept { return value == other.value; }
+
+ std::string toString(pkgCache &cache) const { return (sign() ? "not " : "") + var().toString(cache); }
+};
+
+/**
+ * \brief A single clause
+ *
+ * A clause is a normalized, expanded dependency, translated into an implication
+ * in terms of Var objects, that is, `reason -> solutions[0] | ... | solutions[n]`
+ */
+struct Clause
+{
+ // \brief Underyling dependency
+ pkgCache::Dependency *dep = nullptr;
+ // \brief Var for the work
+ Var reason;
+ // \brief The group we are in
+ Group group;
+ // \brief Possible solutions to this task, ordered in order of preference.
+ std::vector<Var> solutions{};
+ // \brief An optional clause does not need to be satisfied
+ bool optional;
+
+ // \brief A negative clause negates the solutions, that is X->A|B you get X->!(A|B), aka X->!A&!B
+ bool negative;
+
+ // \brief An optional clause may be eager
+ bool eager;
+
+ // Clauses merged with this clause
+ std::forward_list<Clause> merged;
+
+ inline Clause(Var reason, Group group, bool optional = false, bool negative = false) : reason(reason), group(group), optional(optional), negative(negative), eager(not optional) {}
+
+ std::string toString(pkgCache &cache, bool pretty = false, bool showMerged = true) const;
+};
+
+constexpr Lit Solver::Var::operator~() const
+{
+ return ~Lit(*this);
+}
+
+inline LiftedBool operator~(LiftedBool value)
+{
+ switch (value)
+ {
+ case LiftedBool::Undefined:
+ return LiftedBool::Undefined;
+ case LiftedBool::True:
+ return LiftedBool::False;
+ case LiftedBool::False:
+ return LiftedBool::True;
+ }
+ abort();
+}
+
/*
* \brief APT 3.0 solver
*
@@ -79,71 +280,24 @@ using FastContiguousCacheMap = ContiguousCacheMap<K, V, true>;
*/
class Solver
{
- enum class Decision : uint16_t;
- enum class Hint : uint16_t;
- struct Var;
- struct CompareProviders3;
+ protected:
struct State;
- struct Clause;
struct Work;
- struct Solved;
- friend struct std::hash<APT::Solver::Var>;
+ struct Trail;
- // \brief Groups of works, these are ordered.
- //
- // Later items will be skipped if they are optional, or we will when backtracking,
- // try a different choice for them.
- enum class Group : uint8_t
- {
- HoldOrDelete,
-
- // Satisfying dependencies on entirely new packages first is a good idea because
- // it may contain replacement packages like libfoo1t64 whereas we later will see
- // Depends: libfoo1 where libfoo1t64 Provides libfoo1 and we'd have to choose.
- SatisfyNew,
- Satisfy,
- // On a similar note as for SatisfyNew, if the dependency contains obsolete packages
- // try it last.
- SatisfyObsolete,
-
- // Select a version of a package chosen for install.
- SelectVersion,
-
- // My intuition tells me that we should try to schedule upgrades first, then
- // any non-obsolete installed packages, and only finally obsolete ones, such
- // that newer packages guide resolution of dependencies for older ones, they
- // may have more stringent dependencies, like a (>> 2) whereas an obsolete
- // package may have a (>> 1), for example.
- UpgradeManual,
- InstallManual,
- ObsoleteManual,
-
- // Automatically installed packages must come last in the group, this allows
- // us to see if they were installed as a dependency of a manually installed package,
- // allowing a simple implementation of an autoremoval code.
- UpgradeAuto,
- KeepAuto,
- ObsoleteAuto,
-
- // Satisfy optional dependencies that were previously satisfied but won't otherwise be installed
- SatisfySuggests,
- };
-
- // \brief Type to record depth at. This may very well be a 16-bit
- // unsigned integer, then change Solver::State::Decision to be a
+ // \brief Type to record decision level at. This may very well be a 16-bit
+ // unsigned integer, then change Solver::State::LiftedBool to be a
// uint16_t class enum as well to get a more compact space.
- using depth_type = unsigned int;
+ using level_type = unsigned int;
// Documentation
template <typename T>
using heap = std::vector<T>;
- static_assert(sizeof(depth_type) >= sizeof(map_id_t));
+ static_assert(sizeof(level_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;
// Root state
std::unique_ptr<State> rootState;
// States for packages
@@ -174,304 +328,211 @@ class Solver
inline State &operator[](Var r);
inline const State &operator[](Var r) const;
- mutable FastContiguousCacheMap<pkgCache::Package, char> pkgObsolete;
- // \brief Check if package is obsolete.
- // \param AllowManual controls whether manual packages can be obsolete
- bool Obsolete(pkgCache::PkgIterator pkg, bool AllowManual=false) const;
- bool ObsoletedByNewerSourceVersion(pkgCache::VerIterator cand) const;
-
- mutable FastContiguousCacheMap<pkgCache::Version, short> priorities;
- short GetPriority(pkgCache::VerIterator ver) const
- {
- if (priorities[ver] == 0)
- priorities[ver] = policy.GetPriority(ver);
- return priorities[ver];
- }
-
- mutable ContiguousCacheMap<pkgCache::Package, pkgCache::VerIterator> candidates;
- pkgCache::VerIterator GetCandidateVer(pkgCache::PkgIterator pkg) const
- {
- if (candidates[pkg].end())
- candidates[pkg] = policy.GetCandidateVer(pkg);
- return candidates[pkg];
- }
-
// \brief Heap of the remaining work.
//
- // We are using an std::vector with std::make_heap(), std::push_heap(),
- // 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.
+ // In contrast to MiniSAT which picks undecided literals and decides them,
+ // we keep track of unsolved active clauses in a priority queue. This allows
+ // us to for example, solve Depends before Recommends (see Group).
heap<Work> work;
- // \brief Backlog of solved work.
- //
- // Solved work may become invalidated when backtracking, so store it
- // here to revisit it later. This is similar to what MiniSAT calls the
- // trail; one distinction is that we have both literals and our work
- // queue to be concerned about
- std::vector<Solved> solved;
+ /// \brief Trail of assignments done, and clauses solved.
+ ///
+ /// Record past assignments and solved clauses such that we can revert them when
+ /// backtracking.
+ std::vector<Trail> trail;
+
+ /// \brief Separator indices for different decision levels in trail
+ std::vector<level_type> trailLim{};
// \brief Propagation queue
std::queue<Var> propQ;
- // \brief Discover variables
- std::queue<Var> discoverQ;
-
- // \brief Current decision level.
- //
- // This is an index into the solved vector.
- std::vector<depth_type> choices{};
// \brief The time we called Solve()
time_t startTime{};
- EDSP::Request::Flags requestFlags;
/// Various configuration options
std::string version{_config->Find("APT::Solver", "3.0")};
// \brief Debug level
int debug{_config->FindI("Debug::APT::Solver")};
- // \brief If set, we try to keep automatically installed packages installed.
- bool KeepAuto{version == "3.0" || not _config->FindB("APT::Get::AutomaticRemove")};
- // \brief Determines if we are in upgrade mode.
- bool IsUpgrade{_config->FindB("APT::Solver::Upgrade", requestFlags &EDSP::Request::UPGRADE_ALL)};
- // \brief If set, removals are allowed.
- bool AllowRemove{_config->FindB("APT::Solver::Remove", not(requestFlags & EDSP::Request::FORBID_REMOVE))};
- // \brief If set, removal of manual packages is allowed.
- bool AllowRemoveManual{AllowRemove && _config->FindB("APT::Solver::RemoveManual", true)};
- // \brief If set, installs are allowed.
- bool AllowInstall{_config->FindB("APT::Solver::Install", not(requestFlags & EDSP::Request::FORBID_NEW_INSTALL))};
- // \brief If set, we use strict pinning.
- bool StrictPinning{_config->FindB("APT::Solver::Strict-Pinning", true)};
- // \brief If set, we install missing recommends and pick new best packages.
- bool FixPolicyBroken{_config->FindB("APT::Get::Fix-Policy-Broken")};
- // \brief If set, we use strict pinning.
- bool DeferVersionSelection{_config->FindB("APT::Solver::Defer-Version-Selection", true)};
// \brief If set, we use strict pinning.
int Timeout{_config->FindI("APT::Solver::Timeout", 10)};
- // \brief Keep recommends installed
- bool KeepRecommends{_config->FindB("APT::AutoRemove::RecommendsImportant", true)};
- // \brief Keep suggests installed
- bool KeepSuggests{_config->FindB("APT::AutoRemove::SuggestsImportant", true)};
-
// \brief Discover a variable, translating the underlying dependencies to the SAT presentation
//
// This does a breadth-first search of the entire dependency tree of var,
// utilizing the discoverQ above.
- void Discover(Var var);
- // \brief Link a clause into the watchers
- const Clause *RegisterClause(Clause &&clause);
- // \brief Enqueue dependencies shared by all versions of the package.
- void RegisterCommonDependencies(pkgCache::PkgIterator Pkg);
-
- // \brief Translate an or group into a clause object
- [[nodiscard]] Clause TranslateOrGroup(pkgCache::DepIterator start, pkgCache::DepIterator end, Var reason);
+ virtual void Discover(Var var) = 0;
// \brief Propagate all pending propagations
[[nodiscard]] bool Propagate();
- // \brief Return the current depth (choices.size() with casting)
- depth_type depth()
+ // \brief Return the current level (.size() with casting)
+ level_type decisionLevel()
{
- return static_cast<depth_type>(choices.size());
+ return static_cast<level_type>(trailLim.size());
}
inline Var bestReason(Clause const *clause, Var var) const;
+ inline LiftedBool value(Lit lit) const;
public:
- // \brief Create a new decision level.
- void Push(Var var, Work work);
// \brief Revert to the previous decision level.
[[nodiscard]] bool Pop();
- // \brief Undo a single assignment / solved work item
+ // \brief Undo a single assignment / trail work item
void UndoOne();
// \brief Add work to our work queue.
[[nodiscard]] bool AddWork(Work &&work);
// \brief Basic solver initializer. This cannot fail.
- Solver(pkgCache &Cache, pkgDepCache::Policy &Policy, EDSP::Request::Flags requestFlags);
- ~Solver();
-
- // Assume that the variable is decided as specified.
- [[nodiscard]] bool Assume(Var var, bool decision, const Clause *reason = nullptr);
- // Enqueue a decision fact
- [[nodiscard]] bool Enqueue(Var var, bool decision, const Clause *reason = nullptr);
+ Solver(pkgCache &Cache);
+ virtual ~Solver();
- // \brief Apply the selections from the dep cache to the solver
- [[nodiscard]] bool FromDepCache(pkgDepCache &depcache);
- // \brief Apply the solver result to the depCache
- [[nodiscard]] bool ToDepCache(pkgDepCache &depcache) const;
+ // Assume a literal
+ [[nodiscard]] bool Assume(Lit lit, const Clause *reason = nullptr);
+ // Enqueue a fact
+ [[nodiscard]] bool Enqueue(Lit lit, const Clause *reason = nullptr);
// \brief Solve the dependencies
[[nodiscard]] bool Solve();
// Print dependency chain
- std::string WhyStr(Var reason) const;
+ virtual std::string WhyStr(Var reason) const;
/**
* \brief Print a long reason string
*
- * Print a reason as to why `rclause` implies `decision` for the variable `var`.
+ * Print a reason as to why `rclause` implies `assignment` for the variable `var`.
*
* \param var The variable to print the reason for
- * \param decision The assumed decision to print the reason for (may be different from actual decision if rclause is specified)
+ * \param assignment The assumed assignment to print the reason for (may be different from actual assignment if rclause is specified)
* \param rclause The clause that caused this variable to be marked (or would be marked)
* \param prefix A prefix, for indentation purposes, as this is recursive
* \param seen A set of seen objects such that the output does not repeat itself (not for safety, it is acyclic)
*/
- std::string LongWhyStr(Var var, bool decision, const Clause *rclause, std::string prefix, std::unordered_set<Var> &seen) const;
-
- // \brief Temporary internal API with external linkage for the `apt why` and `apt why-not` commands.
- APT_PUBLIC static std::string InternalCliWhy(pkgDepCache &depcache, pkgCache::PkgIterator Pkg, bool decision);
+ virtual std::string LongWhyStr(Var var, bool assignment, const Clause *rclause, std::string prefix, std::unordered_set<Var> &seen) const;
};
-}; // namespace APT
-
-/**
- * \brief Tagged union holding either a package, version, or nothing; representing the reason for installing something.
+/*
+ * \brief APT 3.0 solver
*
- * We want to keep track of the reason why things are being installed such that
- * we can have sensible debugging abilities; and we want to generically refer to
- * both packages and versions as variables, hence this class was added.
+ * 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.
*/
-struct APT::Solver::Var
+class DependencySolver : public Solver
{
- uint32_t value;
+ friend class CompareProviders3;
- explicit constexpr Var(uint32_t value = 0) : value{value} {}
- explicit Var(pkgCache::PkgIterator const &Pkg) : value(uint32_t(Pkg.MapPointer()) << 1) {}
- explicit Var(pkgCache::VerIterator const &Ver) : value(uint32_t(Ver.MapPointer()) << 1 | 1) {}
+ // Policy is needed for determining candidate version.
+ pkgDepCache::Policy &policy;
+ // Request flags determine the behavior of the options below, make sure it comes first.
+ EDSP::Request::Flags requestFlags;
- inline constexpr bool isVersion() const { return value & 1; }
- inline constexpr uint32_t mapPtr() const { return value >> 1; }
+ // Configuration options for the dependency solver
+ bool KeepAuto{version == "3.0" || not _config->FindB("APT::Get::AutomaticRemove")};
+ bool IsUpgrade{_config->FindB("APT::Solver::Upgrade", requestFlags &EDSP::Request::UPGRADE_ALL)};
+ bool AllowRemove{_config->FindB("APT::Solver::Remove", not(requestFlags & EDSP::Request::FORBID_REMOVE))};
+ bool AllowRemoveManual{AllowRemove && _config->FindB("APT::Solver::RemoveManual", true)};
+ bool AllowInstall{_config->FindB("APT::Solver::Install", not(requestFlags & EDSP::Request::FORBID_NEW_INSTALL))};
+ bool StrictPinning{_config->FindB("APT::Solver::Strict-Pinning", true)};
+ bool FixPolicyBroken{_config->FindB("APT::Get::Fix-Policy-Broken")};
+ bool DeferVersionSelection{_config->FindB("APT::Solver::Defer-Version-Selection", true)};
+ bool KeepRecommends{_config->FindB("APT::AutoRemove::RecommendsImportant", true)};
+ bool KeepSuggests{_config->FindB("APT::AutoRemove::SuggestsImportant", true)};
- // \brief Return the package, if any, otherwise 0.
- map_pointer<pkgCache::Package> Pkg() const
- {
- return isVersion() ? 0 : map_pointer<pkgCache::Package>{mapPtr()};
- }
- // \brief Return the version, if any, otherwise 0.
- map_pointer<pkgCache::Version> Ver() const
- {
- return isVersion() ? map_pointer<pkgCache::Version>{mapPtr()} : 0;
- }
- // \brief Return the package iterator if storing a package, or an empty one
- pkgCache::PkgIterator Pkg(pkgCache &cache) const
- {
- return isVersion() ? pkgCache::PkgIterator() : pkgCache::PkgIterator(cache, cache.PkgP + Pkg());
- }
- // \brief Return the version iterator if storing a package, or an empty end.
- pkgCache::VerIterator Ver(pkgCache &cache) const
- {
- return isVersion() ? pkgCache::VerIterator(cache, cache.VerP + Ver()) : pkgCache::VerIterator();
- }
- // \brief Return a package, cast from version if needed
- pkgCache::PkgIterator CastPkg(pkgCache &cache) const
+ // Helper functions for detecting obsolete packages
+ mutable FastContiguousCacheMap<pkgCache::Package, char> pkgObsolete;
+ bool Obsolete(pkgCache::PkgIterator pkg, bool AllowManual = false) const;
+ bool ObsoletedByNewerSourceVersion(pkgCache::VerIterator cand) const;
+
+ // GetPriority() with caching
+ mutable FastContiguousCacheMap<pkgCache::Version, short> priorities;
+ short GetPriority(pkgCache::VerIterator ver) const
{
- return isVersion() ? Ver(cache).ParentPkg() : Pkg(cache);
+ if (priorities[ver] == 0)
+ priorities[ver] = policy.GetPriority(ver);
+ return priorities[ver];
}
- // \brief Check if there is no reason.
- constexpr bool empty() const { return value == 0; }
- constexpr bool operator!=(Var const other) const { return value != other.value; }
- constexpr bool operator==(Var const other) const { return value == other.value; }
- std::string toString(pkgCache &cache) const
+ // GetCandidateVer() with caching
+ mutable ContiguousCacheMap<pkgCache::Package, pkgCache::VerIterator> candidates;
+ pkgCache::VerIterator GetCandidateVer(pkgCache::PkgIterator pkg) const
{
- if (auto P = Pkg(cache); not P.end())
- return P.FullName();
- if (auto V = Ver(cache); not V.end())
- return V.ParentPkg().FullName() + "=" + V.VerStr();
- return "(root)";
+ if (candidates[pkg].end())
+ candidates[pkg] = policy.GetCandidateVer(pkg);
+ return candidates[pkg];
}
-};
-
-/**
- * \brief A single clause
- *
- * A clause is a normalized, expanded dependency, translated into an implication
- * in terms of Var objects, that is, `reason -> solutions[0] | ... | solutions[n]`
- */
-struct APT::Solver::Clause
-{
- // \brief Underyling dependency
- pkgCache::Dependency *dep = nullptr;
- // \brief Var for the work
- Var reason;
- // \brief The group we are in
- Group group;
- // \brief Possible solutions to this task, ordered in order of preference.
- std::vector<Var> solutions{};
- // \brief An optional clause does not need to be satisfied
- bool optional;
- // \brief A negative clause negates the solutions, that is X->A|B you get X->!(A|B), aka X->!A&!B
- bool negative;
-
- // \brief An optional clause may be eager
- bool eager;
+ // \brief Discover variables
+ std::queue<Var> discoverQ;
+ /// \brief Discover the dependencies of the variable
+ void Discover(Var var) override;
+ /// \brief Link a clause into the watchers
+ const Clause *RegisterClause(Clause &&clause);
+ /// \brief Enqueue dependencies shared by all versions of the package.
+ void RegisterCommonDependencies(pkgCache::PkgIterator Pkg);
- // Clauses merged with this clause
- std::forward_list<Clause> merged;
+ /// \brief Translate an or group into a clause object
+ [[nodiscard]] Clause TranslateOrGroup(pkgCache::DepIterator start, pkgCache::DepIterator end, Var reason);
- inline Clause(Var reason, Group group, bool optional = false, bool negative = false) : reason(reason), group(group), optional(optional), negative(negative), eager(not optional) {}
+ public:
+ // \brief Basic solver initializer. This cannot fail.
+ DependencySolver(pkgCache &Cache, pkgDepCache::Policy &Policy, EDSP::Request::Flags requestFlags);
+ ~DependencySolver() override;
- std::string toString(pkgCache &cache, bool pretty = false, bool showMerged = true) const;
+ /// \brief Apply the selections from the dep cache to the solver
+ [[nodiscard]] bool FromDepCache(pkgDepCache &depcache);
+ /// \brief Apply the solver result to the depCache
+ [[nodiscard]] bool ToDepCache(pkgDepCache &depcache) const;
+ /// \brief Temporary internal API with external linkage for the `apt why` and `apt why-not` commands.
+ APT_PUBLIC static std::string InternalCliWhy(pkgDepCache &depcache, pkgCache::PkgIterator Pkg, bool assignment);
};
-
+}; // namespace APT::Solver
/**
* \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.
+ * is ordered, by level, 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
+struct APT::Solver::Solver::Work
{
const Clause *clause;
- // \brief The depth at which the item has been added
- depth_type depth;
+ // \brief The level at which the item has been added
+ level_type level;
- // Number of valid choices
+ /// Number of valid choices at insertion time
size_t size{0};
// \brief This item should be removed from the queue.
bool erased{false};
- bool operator<(APT::Solver::Work const &b) const;
+ bool operator<(APT::Solver::Solver::Work const &b) const;
std::string toString(pkgCache &cache) const;
- inline Work(const Clause *clause, depth_type depth) : clause(clause), depth(depth) {}
-};
-
-// \brief This essentially describes the install state in RFC2119 terms.
-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,
+ inline Work(const Clause *clause, level_type level) : clause(clause), level(level) {}
};
/**
* \brief The solver state
*
- * For each version, the solver records a decision at a certain level. It
+ * For each version, the solver records a assignment at a certain level. It
* maintains an array mapping from version ID to state.
*/
-struct APT::Solver::State
+struct APT::Solver::Solver::State
{
- // \brief The reason for causing this state (invalid for NONE).
+ // \brief The reason for causing this state (invalid for Undefined).
//
// 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
+ // between x1 and x2 in level = 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.
+ // of them as REJECT in level = K.
//
- // You can follow the reason chain upwards as long as the depth
+ // You can follow the reason chain upwards as long as the level
// doesn't increase to unwind.
//
// Vars < 0 are package ID, reasons > 0 are version IDs.
@@ -479,11 +540,10 @@ struct APT::Solver::State
const char *reasonStr{};
- // \brief The depth at which the decision has been taken
- depth_type depth{0};
+ // \brief The level at which the value has been assigned
+ level_type level{0};
- // \brief This essentially describes the install state in RFC2119 terms.
- Decision decision{Decision::NONE};
+ LiftedBool assignment{LiftedBool::Undefined};
// \brief Flags.
struct
@@ -501,20 +561,26 @@ struct APT::Solver::State
};
/**
- * \brief A solved item.
+ * \brief A trail item.
*
- * Here we keep track of solved clauses and variable assignments such that we can easily undo
- * them.
+ * In MiniSAT, a trail item is an assigned literal. However, we store an assigned variable instead,
+ * since the assignment is still recorded when we need to access the trail; there does not appear
+ * to be a substantial value in recording the sign here; but it produces a risk for a disagreement
+ * between the actual state and the sign recorded in the trail.
+ *
+ * In addition to MiniSAT's trail, we also need to keep a trail of solved Work items; that is
+ * clauses that were being solved, as when undoing the trail, we need to mark those clauses
+ * active again by putting them back on the work heap.
*/
-struct APT::Solver::Solved
+struct APT::Solver::Solver::Trail
{
- // \brief A variable that has been assigned. We store this as a reason (FIXME: Rename Var to Var)
+ /// \brief A variable that got assigned True or False. May be reset to Undefined on backtracking.
Var assigned;
- // \brief A work item that has been solved. This needs to be put back on the queue.
+ /// \brief A work item (a clause) that was solved. Needs to be put back on the work heap on backtracking.
std::optional<Work> work;
};
-inline APT::Solver::State &APT::Solver::operator[](Var r)
+inline APT::Solver::Solver::State &APT::Solver::Solver::operator[](APT::Solver::Var r)
{
if (auto P = r.Pkg())
return (*this)[cache.PkgP + P];
@@ -523,7 +589,7 @@ inline APT::Solver::State &APT::Solver::operator[](Var r)
return *rootState.get();
}
-inline const APT::Solver::State &APT::Solver::operator[](Var r) const
+inline const APT::Solver::Solver::State &APT::Solver::Solver::operator[](APT::Solver::Var r) const
{
return const_cast<Solver &>(*this)[r];
}
@@ -535,3 +601,11 @@ struct std::hash<APT::Solver::Var>
std::hash<decltype(APT::Solver::Var::value)> hash_value;
std::size_t operator()(const APT::Solver::Var &v) const noexcept { return hash_value(v.value); }
};
+
+// Custom specialization of std::hash can be injected in namespace std.
+template <>
+struct std::hash<APT::Solver::Lit>
+{
+ std::hash<decltype(APT::Solver::Lit::value)> hash_value;
+ std::size_t operator()(const APT::Solver::Lit &v) const noexcept { return hash_value(v.value); }
+};
generated by cgit v1.2.3-70-g09d2 (git 2.46.0) at 2026-07-19 19:07:33 +0000