summaryrefslogtreecommitdiff
path: root/apt-pkg
diff options
context:
space:
mode:
Diffstat (limited to 'apt-pkg')
-rw-r--r--apt-pkg/solver3.cc54
-rw-r--r--apt-pkg/solver3.h40
2 files changed, 67 insertions, 27 deletions
diff --git a/apt-pkg/solver3.cc b/apt-pkg/solver3.cc
index f851a98b8..336a24a2d 100644
--- a/apt-pkg/solver3.cc
+++ b/apt-pkg/solver3.cc
@@ -170,6 +170,10 @@ APT::Solver::Solver(pkgCache &cache, pkgDepCache::Policy &policy)
// This function determines if a work item is less important than another.
bool APT::Solver::Work::operator<(APT::Solver::Work const &b) const
{
+ if ((not optional && size < 2) != (not b.optional && b.size < 2))
+ return not b.optional && b.size < 2;
+ if (group != b.group)
+ return group > b.group;
if (optional && b.optional && 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,
@@ -257,7 +261,7 @@ std::string APT::Solver::WhyStr(Reason reason)
return outstr;
}
-bool APT::Solver::Install(pkgCache::PkgIterator Pkg, Reason reason)
+bool APT::Solver::Install(pkgCache::PkgIterator Pkg, Reason reason, Group group)
{
if ((*this)[Pkg].decision == Decision::MUST)
return true;
@@ -286,7 +290,7 @@ bool APT::Solver::Install(pkgCache::PkgIterator Pkg, Reason reason)
(*this)[Pkg] = {reason, depth(), Decision::MUST,};
// Insert the work item.
- Work workItem{Reason(Pkg), depth()};
+ Work workItem{Reason(Pkg), depth(), group};
for (auto ver = Pkg.VersionList(); not ver.end(); ver++)
if (IsAllowedVersion(ver))
workItem.solutions.push_back(ver);
@@ -295,7 +299,7 @@ bool APT::Solver::Install(pkgCache::PkgIterator Pkg, Reason reason)
if (workItem.solutions.size() > 1 || workItem.optional)
AddWork(std::move(workItem));
- else if (not Install(pkgCache::VerIterator(cache, workItem.solutions[0]), workItem.reason))
+ else if (not Install(pkgCache::VerIterator(cache, workItem.solutions[0]), workItem.reason, group))
return false;
if (not EnqueueCommonDependencies(Pkg))
@@ -304,7 +308,7 @@ bool APT::Solver::Install(pkgCache::PkgIterator Pkg, Reason reason)
return true;
}
-bool APT::Solver::Install(pkgCache::VerIterator Ver, Reason reason)
+bool APT::Solver::Install(pkgCache::VerIterator Ver, Reason reason, Group group)
{
if ((*this)[Ver].decision == Decision::MUST)
return true;
@@ -339,7 +343,7 @@ bool APT::Solver::Install(pkgCache::VerIterator Ver, Reason reason)
for (auto OV = Ver.ParentPkg().VersionList(); not OV.end(); ++OV)
{
- if (OV != Ver && not Reject(OV, Reason(Ver)))
+ if (OV != Ver && not Reject(OV, Reason(Ver), group))
return false;
}
@@ -357,7 +361,7 @@ bool APT::Solver::Install(pkgCache::VerIterator Ver, Reason reason)
return true;
}
-bool APT::Solver::Reject(pkgCache::PkgIterator Pkg, Reason reason)
+bool APT::Solver::Reject(pkgCache::PkgIterator Pkg, Reason reason, Group group)
{
if ((*this)[Pkg].decision == Decision::MUSTNOT)
return true;
@@ -374,7 +378,7 @@ bool APT::Solver::Reject(pkgCache::PkgIterator Pkg, Reason reason)
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)))
+ if (not Reject(ver, Reason(Pkg), group))
return false;
needsRescore = true;
@@ -383,8 +387,10 @@ bool APT::Solver::Reject(pkgCache::PkgIterator Pkg, Reason reason)
}
// \brief Do not install this version
-bool APT::Solver::Reject(pkgCache::VerIterator Ver, Reason reason)
+bool APT::Solver::Reject(pkgCache::VerIterator Ver, Reason reason, Group group)
{
+ (void) group;
+
if ((*this)[Ver].decision == Decision::MUSTNOT)
return true;
@@ -473,7 +479,7 @@ bool APT::Solver::EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepItera
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 */};
+ Work workItem{reason, depth(), Group::Satisfy, not start.IsCritical() /* optional */};
do
{
@@ -489,7 +495,7 @@ bool APT::Solver::EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepItera
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)))
+ if (not Reject(pkgCache::VerIterator(cache, *tgt), Reason(Ver), Group::HoldOrDelete))
return false;
}
else
@@ -560,6 +566,8 @@ bool APT::Solver::EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepItera
return true;
}
}
+ else if (workItem.optional && start.ParentPkg()->CurrentVer == 0)
+ workItem.group = Group::NewUnsatRecommends;
if (not workItem.solutions.empty())
{
@@ -572,7 +580,7 @@ bool APT::Solver::EnqueueOrGroup(pkgCache::DepIterator start, pkgCache::DepItera
}
if (workItem.optional || workItem.solutions.size() > 1)
AddWork(std::move(workItem));
- else if (not Install(pkgCache::VerIterator(cache, workItem.solutions[0]), reason))
+ else if (not Install(pkgCache::VerIterator(cache, workItem.solutions[0]), reason, workItem.group))
return false;
}
else if (start.IsCritical() && not start.IsNegative())
@@ -643,7 +651,7 @@ bool APT::Solver::RejectReverseDependencies(pkgCache::VerIterator Ver)
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)))
+ if (not Reject(RDV, Reason(Ver), Group::HoldOrDelete))
return false;
}
return true;
@@ -738,7 +746,7 @@ bool APT::Solver::Pop()
assert(w.choice != nullptr);
// FIXME: There should be a reason!
- if (not Reject(pkgCache::VerIterator(cache, w.choice), {}))
+ if (not Reject(pkgCache::VerIterator(cache, w.choice), {}, Group::HoldOrDelete))
return false;
w.choice = nullptr;
@@ -857,7 +865,7 @@ bool APT::Solver::Solve()
}
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())
+ if (not Install(pkgCache::VerIterator(cache, ver), item.reason, Group::Satisfy) && not Pop())
return false;
foundSolution = true;
break;
@@ -905,44 +913,48 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache)
{
if (unlikely(debug >= 1))
std::cerr << "Hold " << P.FullName() << "\n";
- if (P->CurrentVer ? not Install(P.CurrentVer(), {}) : not Reject(P, {}))
+ if (P->CurrentVer ? not Install(P.CurrentVer(), {}, Group::HoldOrDelete) : not Reject(P, {}, Group::HoldOrDelete))
return false;
}
else if (reject)
{
if (unlikely(debug >= 1))
std::cerr << "Delete " << P.FullName() << "\n";
- if (!Reject(P, {}))
+ if (!Reject(P, {}, Group::HoldOrDelete))
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), {}))
+ if (depcache[P].Keep() ? not Install(P, {}, Group::InstallManual) : not Install(depcache.GetCandidateVersion(P), {}, Group::InstallManual))
return false;
}
else if (maybeInstall && not isOptional)
{
+ auto Upgrade = depcache.GetCandidateVersion(P) != P.CurrentVer();
+ auto Group = (Upgrade ? Group::UpgradeManual : Group::InstallManual);
if (unlikely(debug >= 1))
std::cerr << "MANUAL " << P.FullName() << "\n";
- if (depcache[P].Keep() ? not Install(P, {}) : not Install(depcache.GetCandidateVersion(P), {}))
+ if (depcache[P].Keep() ? not Install(P, {}, Group) : not Install(depcache.GetCandidateVersion(P), {}, Group))
return false;
}
else if (maybeInstall && isOptional && (KeepAuto || rootSet.InRootSet(P) || not isAuto))
{
auto Upgrade = depcache.GetCandidateVersion(P) != P.CurrentVer();
+ auto Group = isAuto ? (Upgrade ? Group::UpgradeAuto : Group::KeepAuto)
+ : (Upgrade ? Group::UpgradeManual : Group::InstallManual);
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), {}))
+ if (depcache[P].Keep() ? not Install(P, {}, Group) : not Install(depcache.GetCandidateVersion(P), {}, Group))
return false;
}
else
{
- Work w{Reason(), depth(), true, Upgrade};
+ Work w{Reason(), depth(), Group, true, Upgrade};
for (auto V = P.VersionList(); not V.end(); ++V)
if (IsAllowedVersion(V))
w.solutions.push_back(V);
@@ -954,7 +966,7 @@ bool APT::Solver::FromDepCache(pkgDepCache &depcache)
{
if (unlikely(debug >= 1))
std::cerr << "NOT ALLOWING INSTALL OF " << P.FullName() << "\n";
- if (not Reject(P, {}))
+ if (not Reject(P, {}, Group::HoldOrDelete))
return false;
}
}
diff --git a/apt-pkg/solver3.h b/apt-pkg/solver3.h
index cf2fb2ecc..c3f191b18 100644
--- a/apt-pkg/solver3.h
+++ b/apt-pkg/solver3.h
@@ -36,6 +36,33 @@ class Solver
struct State;
struct Work;
+ // \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,
+ NewUnsatRecommends,
+ Satisfy,
+
+ // 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
+ };
+
// \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.
@@ -131,13 +158,13 @@ class Solver
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);
+ bool Install(pkgCache::PkgIterator Pkg, Reason reason, Group group);
// \brief Install a version.
- bool Install(pkgCache::VerIterator Ver, Reason reason);
+ bool Install(pkgCache::VerIterator Ver, Reason reason, Group group);
// \brief Do not install this package
- bool Reject(pkgCache::PkgIterator Pkg, Reason reason);
+ bool Reject(pkgCache::PkgIterator Pkg, Reason reason, Group group);
// \brief Do not install this version.
- bool Reject(pkgCache::VerIterator Ver, Reason reason);
+ bool Reject(pkgCache::VerIterator Ver, Reason reason, Group group);
// \brief Apply the selections from the dep cache to the solver
bool FromDepCache(pkgDepCache &depcache);
@@ -203,7 +230,8 @@ struct APT::Solver::Work
Reason reason;
// \brief The depth at which the item has been added
depth_type depth;
-
+ // \brief The group we are in
+ Group group;
// \brief Possible solutions to this task, ordered in order of preference.
std::vector<pkgCache::Version *> solutions{};
@@ -228,7 +256,7 @@ struct APT::Solver::Work
// \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) {}
+ inline Work(Reason reason, depth_type depth, Group group, bool optional = false, bool upgrade = false) : reason(reason), depth(depth), group(group), size(0), optional(optional), upgrade(upgrade), dirty(false) {}
};
// \brief This essentially describes the install state in RFC2119 terms.
generated by cgit v1.2.3-70-g09d2 (git 2.46.0) at 2026-07-18 23:14:24 +0000