summaryrefslogtreecommitdiffstats
path: root/apt-pkg/algorithms.cc
diff options
context:
space:
mode:
Diffstat (limited to '')
-rw-r--r--apt-pkg/algorithms.cc1654
1 files changed, 1654 insertions, 0 deletions
diff --git a/apt-pkg/algorithms.cc b/apt-pkg/algorithms.cc
new file mode 100644
index 0000000..5869668
--- /dev/null
+++ b/apt-pkg/algorithms.cc
@@ -0,0 +1,1654 @@
+// -*- mode: cpp; mode: fold -*-
+// Description /*{{{*/
+/* ######################################################################
+
+ Algorithms - A set of misc algorithms
+
+ The pkgProblemResolver class has become insanely complex and
+ very sophisticated, it handles every test case I have thrown at it
+ to my satisfaction. Understanding exactly why all the steps the class
+ does are required is difficult and changing though not very risky
+ may result in other cases not working.
+
+ ##################################################################### */
+ /*}}}*/
+// Include Files /*{{{*/
+#include <config.h>
+
+#include <apt-pkg/algorithms.h>
+#include <apt-pkg/cachefilter.h>
+#include <apt-pkg/configuration.h>
+#include <apt-pkg/depcache.h>
+#include <apt-pkg/dpkgpm.h>
+#include <apt-pkg/edsp.h>
+#include <apt-pkg/error.h>
+#include <apt-pkg/macros.h>
+#include <apt-pkg/packagemanager.h>
+#include <apt-pkg/pkgcache.h>
+#include <apt-pkg/string_view.h>
+#include <apt-pkg/strutl.h>
+#include <apt-pkg/version.h>
+
+#include <apt-pkg/prettyprinters.h>
+
+#include <cstdlib>
+#include <cstring>
+#include <iostream>
+#include <map>
+#include <set>
+#include <sstream>
+#include <string>
+#include <utility>
+#include <vector>
+#include <sys/utsname.h>
+
+#include <apti18n.h>
+ /*}}}*/
+using namespace std;
+
+class APT_HIDDEN pkgSimulatePrivate
+{
+public:
+ std::vector<pkgDPkgPM::Item> List;
+};
+// Simulate::Simulate - Constructor /*{{{*/
+// ---------------------------------------------------------------------
+/* The legacy translations here of input Pkg iterators is obsolete,
+ this is not necessary since the pkgCaches are fully shared now. */
+pkgSimulate::pkgSimulate(pkgDepCache *Cache) : pkgPackageManager(Cache),
+ d(new pkgSimulatePrivate()), iPolicy(Cache),
+ Sim(&Cache->GetCache(),&iPolicy),
+ group(Sim)
+{
+ Sim.Init(0);
+ auto PackageCount = Cache->Head().PackageCount;
+ Flags = new unsigned char[PackageCount];
+ memset(Flags,0,sizeof(*Flags)*PackageCount);
+
+ // Fake a filename so as not to activate the media swapping
+ string Jnk = "SIMULATE";
+ for (decltype(PackageCount) I = 0; I != PackageCount; ++I)
+ FileNames[I] = Jnk;
+
+ Cache->CheckConsistency("simulate");
+}
+ /*}}}*/
+// Simulate::~Simulate - Destructor /*{{{*/
+pkgSimulate::~pkgSimulate()
+{
+ delete[] Flags;
+ delete d;
+}
+ /*}}}*/
+// Simulate::Describe - Describe a package /*{{{*/
+// ---------------------------------------------------------------------
+/* Parameter Current == true displays the current package version,
+ Parameter Candidate == true displays the candidate package version */
+void pkgSimulate::Describe(PkgIterator Pkg,ostream &out,bool Current,bool Candidate)
+{
+ VerIterator Ver(Sim);
+
+ out << Pkg.FullName(true);
+
+ if (Current == true)
+ {
+ Ver = Pkg.CurrentVer();
+ if (Ver.end() == false)
+ out << " [" << Ver.VerStr() << ']';
+ }
+
+ if (Candidate == true)
+ {
+ Ver = Sim[Pkg].CandidateVerIter(Sim);
+ if (Ver.end() == true)
+ return;
+
+ out << " (" << Ver.VerStr() << ' ' << Ver.RelStr() << ')';
+ }
+}
+ /*}}}*/
+// Simulate::Install - Simulate unpacking of a package /*{{{*/
+// ---------------------------------------------------------------------
+/* */
+bool pkgSimulate::Install(PkgIterator iPkg,string File)
+{
+ if (iPkg.end() || File.empty())
+ return false;
+ d->List.emplace_back(pkgDPkgPM::Item::Install, iPkg, File);
+ return true;
+}
+bool pkgSimulate::RealInstall(PkgIterator iPkg,string /*File*/)
+{
+ // Adapt the iterator
+ PkgIterator Pkg = Sim.FindPkg(iPkg.Name(), iPkg.Arch());
+ Flags[Pkg->ID] = 1;
+
+ cout << "Inst ";
+ Describe(Pkg,cout,true,true);
+ Sim.MarkInstall(Pkg,false);
+
+ // Look for broken conflicts+predepends.
+ for (PkgIterator I = Sim.PkgBegin(); I.end() == false; ++I)
+ {
+ if (Sim[I].InstallVer == 0)
+ continue;
+
+ for (DepIterator D = Sim[I].InstVerIter(Sim).DependsList(); D.end() == false;)
+ {
+ DepIterator Start;
+ DepIterator End;
+ D.GlobOr(Start,End);
+ if (Start.IsNegative() == true ||
+ End->Type == pkgCache::Dep::PreDepends)
+ {
+ if ((Sim[End] & pkgDepCache::DepGInstall) == 0)
+ {
+ cout << " [" << I.FullName(false) << " on " << Start.TargetPkg().FullName(false) << ']';
+ if (Start->Type == pkgCache::Dep::Conflicts)
+ _error->Error("Fatal, conflicts violated %s",I.FullName(false).c_str());
+ }
+ }
+ }
+ }
+
+ if (Sim.BrokenCount() != 0)
+ ShortBreaks();
+ else
+ cout << endl;
+ return true;
+}
+ /*}}}*/
+// Simulate::Configure - Simulate configuration of a Package /*{{{*/
+// ---------------------------------------------------------------------
+/* This is not an accurate simulation of relatity, we should really not
+ install the package.. For some investigations it may be necessary
+ however. */
+bool pkgSimulate::Configure(PkgIterator iPkg)
+{
+ if (iPkg.end())
+ return false;
+ d->List.emplace_back(pkgDPkgPM::Item::Configure, iPkg);
+ return true;
+}
+bool pkgSimulate::RealConfigure(PkgIterator iPkg)
+{
+ // Adapt the iterator
+ PkgIterator Pkg = Sim.FindPkg(iPkg.Name(), iPkg.Arch());
+
+ Flags[Pkg->ID] = 2;
+
+ if (Sim[Pkg].InstBroken() == true)
+ {
+ cout << "Conf " << Pkg.FullName(false) << " broken" << endl;
+
+ Sim.Update();
+
+ // Print out each package and the failed dependencies
+ for (pkgCache::DepIterator D = Sim[Pkg].InstVerIter(Sim).DependsList(); D.end() == false; ++D)
+ {
+ if (Sim.IsImportantDep(D) == false ||
+ (Sim[D] & pkgDepCache::DepInstall) != 0)
+ continue;
+
+ if (D->Type == pkgCache::Dep::Obsoletes)
+ cout << " Obsoletes:" << D.TargetPkg().FullName(false);
+ else if (D->Type == pkgCache::Dep::Conflicts)
+ cout << " Conflicts:" << D.TargetPkg().FullName(false);
+ else if (D->Type == pkgCache::Dep::DpkgBreaks)
+ cout << " Breaks:" << D.TargetPkg().FullName(false);
+ else
+ cout << " Depends:" << D.TargetPkg().FullName(false);
+ }
+ cout << endl;
+
+ _error->Error("Conf Broken %s",Pkg.FullName(false).c_str());
+ }
+ else
+ {
+ cout << "Conf ";
+ Describe(Pkg,cout,false,true);
+ }
+
+ if (Sim.BrokenCount() != 0)
+ ShortBreaks();
+ else
+ cout << endl;
+
+ return true;
+}
+ /*}}}*/
+// Simulate::Remove - Simulate the removal of a package /*{{{*/
+// ---------------------------------------------------------------------
+/* */
+bool pkgSimulate::Remove(PkgIterator iPkg,bool Purge)
+{
+ if (iPkg.end())
+ return false;
+ d->List.emplace_back(Purge ? pkgDPkgPM::Item::Purge : pkgDPkgPM::Item::Remove, iPkg);
+ return true;
+}
+bool pkgSimulate::RealRemove(PkgIterator iPkg,bool Purge)
+{
+ // Adapt the iterator
+ PkgIterator Pkg = Sim.FindPkg(iPkg.Name(), iPkg.Arch());
+ if (Pkg.end() == true)
+ {
+ std::cerr << (Purge ? "Purg" : "Remv") << " invalid package " << iPkg.FullName() << std::endl;
+ return false;
+ }
+
+ Flags[Pkg->ID] = 3;
+ Sim.MarkDelete(Pkg);
+
+ if (Purge == true)
+ cout << "Purg ";
+ else
+ cout << "Remv ";
+ Describe(Pkg,cout,true,false);
+
+ if (Sim.BrokenCount() != 0)
+ ShortBreaks();
+ else
+ cout << endl;
+
+ return true;
+}
+ /*}}}*/
+// Simulate::ShortBreaks - Print out a short line describing all breaks /*{{{*/
+// ---------------------------------------------------------------------
+/* */
+void pkgSimulate::ShortBreaks()
+{
+ cout << " [";
+ for (PkgIterator I = Sim.PkgBegin(); I.end() == false; ++I)
+ {
+ if (Sim[I].InstBroken() == true)
+ {
+ if (Flags[I->ID] == 0)
+ cout << I.FullName(false) << ' ';
+/* else
+ cout << I.Name() << "! ";*/
+ }
+ }
+ cout << ']' << endl;
+}
+ /*}}}*/
+bool pkgSimulate::Go(APT::Progress::PackageManager *) /*{{{*/
+{
+ if (pkgDPkgPM::ExpandPendingCalls(d->List, Cache) == false)
+ return false;
+ for (auto && I : d->List)
+ switch (I.Op)
+ {
+ case pkgDPkgPM::Item::Install:
+ if (RealInstall(I.Pkg, I.File) == false)
+ return false;
+ break;
+ case pkgDPkgPM::Item::Configure:
+ if (RealConfigure(I.Pkg) == false)
+ return false;
+ break;
+ case pkgDPkgPM::Item::Remove:
+ if (RealRemove(I.Pkg, false) == false)
+ return false;
+ break;
+ case pkgDPkgPM::Item::Purge:
+ if (RealRemove(I.Pkg, true) == false)
+ return false;
+ break;
+ case pkgDPkgPM::Item::ConfigurePending:
+ case pkgDPkgPM::Item::TriggersPending:
+ case pkgDPkgPM::Item::RemovePending:
+ case pkgDPkgPM::Item::PurgePending:
+ return _error->Error("Internal error, simulation encountered unexpected pending item");
+ }
+ return true;
+}
+ /*}}}*/
+// ApplyStatus - Adjust for non-ok packages /*{{{*/
+// ---------------------------------------------------------------------
+/* We attempt to change the state of the all packages that have failed
+ installation toward their real state. The ordering code will perform
+ the necessary calculations to deal with the problems. */
+bool pkgApplyStatus(pkgDepCache &Cache)
+{
+ pkgDepCache::ActionGroup group(Cache);
+
+ for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
+ {
+ if (I->VersionList == 0)
+ continue;
+
+ // Only choice for a ReInstReq package is to reinstall
+ if (I->InstState == pkgCache::State::ReInstReq ||
+ I->InstState == pkgCache::State::HoldReInstReq)
+ {
+ if (I->CurrentVer != 0 && I.CurrentVer().Downloadable() == true)
+ Cache.MarkKeep(I, false, false);
+ else
+ {
+ // Is this right? Will dpkg choke on an upgrade?
+ if (Cache[I].CandidateVer != 0 &&
+ Cache[I].CandidateVerIter(Cache).Downloadable() == true)
+ Cache.MarkInstall(I, false, 0, false);
+ else
+ return _error->Error(_("The package %s needs to be reinstalled, "
+ "but I can't find an archive for it."),I.FullName(true).c_str());
+ }
+
+ continue;
+ }
+
+ switch (I->CurrentState)
+ {
+ /* This means installation failed somehow - it does not need to be
+ re-unpacked (probably) */
+ case pkgCache::State::UnPacked:
+ case pkgCache::State::HalfConfigured:
+ case pkgCache::State::TriggersAwaited:
+ case pkgCache::State::TriggersPending:
+ if ((I->CurrentVer != 0 && I.CurrentVer().Downloadable() == true) ||
+ I.State() != pkgCache::PkgIterator::NeedsUnpack)
+ Cache.MarkKeep(I, false, false);
+ else
+ {
+ if (Cache[I].CandidateVer != 0 &&
+ Cache[I].CandidateVerIter(Cache).Downloadable() == true)
+ Cache.MarkInstall(I, true, 0, false);
+ else
+ Cache.MarkDelete(I, false, 0, false);
+ }
+ break;
+
+ // This means removal failed
+ case pkgCache::State::HalfInstalled:
+ Cache.MarkDelete(I, false, 0, false);
+ break;
+
+ default:
+ if (I->InstState != pkgCache::State::Ok)
+ return _error->Error("The package %s is not ok and I "
+ "don't know how to fix it!",I.FullName(false).c_str());
+ }
+ }
+ return true;
+}
+ /*}}}*/
+// FixBroken - Fix broken packages /*{{{*/
+// ---------------------------------------------------------------------
+/* This autoinstalls every broken package and then runs the problem resolver
+ on the result. */
+bool pkgFixBroken(pkgDepCache &Cache)
+{
+ pkgDepCache::ActionGroup group(Cache);
+
+ // Auto upgrade all broken packages
+ for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
+ if (Cache[I].NowBroken() == true)
+ Cache.MarkInstall(I, true, 0, false);
+
+ /* Fix packages that are in a NeedArchive state but don't have a
+ downloadable install version */
+ for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
+ {
+ if (I.State() != pkgCache::PkgIterator::NeedsUnpack ||
+ Cache[I].Delete() == true)
+ continue;
+
+ if (Cache[I].InstVerIter(Cache).Downloadable() == false)
+ continue;
+
+ Cache.MarkInstall(I, true, 0, false);
+ }
+
+ pkgProblemResolver Fix(&Cache);
+ return Fix.Resolve(true);
+}
+ /*}}}*/
+// ProblemResolver::pkgProblemResolver - Constructor /*{{{*/
+// ---------------------------------------------------------------------
+/* */
+pkgProblemResolver::pkgProblemResolver(pkgDepCache *pCache) : d(NULL), Cache(*pCache)
+{
+ // Allocate memory
+ auto const Size = Cache.Head().PackageCount;
+ Scores = new int[Size];
+ Flags = new unsigned char[Size];
+ memset(Flags,0,sizeof(*Flags)*Size);
+
+ // Set debug to true to see its decision logic
+ Debug = _config->FindB("Debug::pkgProblemResolver",false);
+}
+ /*}}}*/
+// ProblemResolver::~pkgProblemResolver - Destructor /*{{{*/
+// ---------------------------------------------------------------------
+/* */
+pkgProblemResolver::~pkgProblemResolver()
+{
+ delete [] Scores;
+ delete [] Flags;
+}
+ /*}}}*/
+// ProblemResolver::ScoreSort - Sort the list by score /*{{{*/
+// ---------------------------------------------------------------------
+/* */
+int pkgProblemResolver::ScoreSort(Package const *A,Package const *B)
+{
+ if (Scores[A->ID] > Scores[B->ID])
+ return -1;
+ if (Scores[A->ID] < Scores[B->ID])
+ return 1;
+ return 0;
+}
+ /*}}}*/
+// ProblemResolver::MakeScores - Make the score table /*{{{*/
+// ---------------------------------------------------------------------
+/* */
+void pkgProblemResolver::MakeScores()
+{
+ auto const Size = Cache.Head().PackageCount;
+ memset(Scores,0,sizeof(*Scores)*Size);
+
+ // maps to pkgCache::State::VerPriority:
+ // Required Important Standard Optional Extra
+ int PrioMap[] = {
+ 0,
+ _config->FindI("pkgProblemResolver::Scores::Required",3),
+ _config->FindI("pkgProblemResolver::Scores::Important",2),
+ _config->FindI("pkgProblemResolver::Scores::Standard",1),
+ _config->FindI("pkgProblemResolver::Scores::Optional",-1),
+ _config->FindI("pkgProblemResolver::Scores::Extra",-2)
+ };
+ int PrioEssentials = _config->FindI("pkgProblemResolver::Scores::Essentials",100);
+ int PrioInstalledAndNotObsolete = _config->FindI("pkgProblemResolver::Scores::NotObsolete",1);
+ int DepMap[] = {
+ 0,
+ _config->FindI("pkgProblemResolver::Scores::Depends",1),
+ _config->FindI("pkgProblemResolver::Scores::PreDepends",1),
+ _config->FindI("pkgProblemResolver::Scores::Suggests",0),
+ _config->FindI("pkgProblemResolver::Scores::Recommends",1),
+ _config->FindI("pkgProblemResolver::Scores::Conflicts",-1),
+ _config->FindI("pkgProblemResolver::Scores::Replaces",0),
+ _config->FindI("pkgProblemResolver::Scores::Obsoletes",0),
+ _config->FindI("pkgProblemResolver::Scores::Breaks",-1),
+ _config->FindI("pkgProblemResolver::Scores::Enhances",0)
+ };
+ int AddProtected = _config->FindI("pkgProblemResolver::Scores::AddProtected",10000);
+ int AddEssential = _config->FindI("pkgProblemResolver::Scores::AddEssential",5000);
+
+ if (_config->FindB("Debug::pkgProblemResolver::ShowScores",false) == true)
+ clog << "Settings used to calculate pkgProblemResolver::Scores::" << endl
+ << " Required => " << PrioMap[pkgCache::State::Required] << endl
+ << " Important => " << PrioMap[pkgCache::State::Important] << endl
+ << " Standard => " << PrioMap[pkgCache::State::Standard] << endl
+ << " Optional => " << PrioMap[pkgCache::State::Optional] << endl
+ << " Extra => " << PrioMap[pkgCache::State::Extra] << endl
+ << " Essentials => " << PrioEssentials << endl
+ << " InstalledAndNotObsolete => " << PrioInstalledAndNotObsolete << endl
+ << " Pre-Depends => " << DepMap[pkgCache::Dep::PreDepends] << endl
+ << " Depends => " << DepMap[pkgCache::Dep::Depends] << endl
+ << " Recommends => " << DepMap[pkgCache::Dep::Recommends] << endl
+ << " Suggests => " << DepMap[pkgCache::Dep::Suggests] << endl
+ << " Conflicts => " << DepMap[pkgCache::Dep::Conflicts] << endl
+ << " Breaks => " << DepMap[pkgCache::Dep::DpkgBreaks] << endl
+ << " Replaces => " << DepMap[pkgCache::Dep::Replaces] << endl
+ << " Obsoletes => " << DepMap[pkgCache::Dep::Obsoletes] << endl
+ << " Enhances => " << DepMap[pkgCache::Dep::Enhances] << endl
+ << " AddProtected => " << AddProtected << endl
+ << " AddEssential => " << AddEssential << endl;
+
+ // Generate the base scores for a package based on its properties
+ for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
+ {
+ if (Cache[I].InstallVer == 0)
+ continue;
+
+ int &Score = Scores[I->ID];
+
+ /* This is arbitrary, it should be high enough to elevate an
+ essantial package above most other packages but low enough
+ to allow an obsolete essential packages to be removed by
+ a conflicts on a powerful normal package (ie libc6) */
+ if ((I->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential
+ || (I->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important)
+ Score += PrioEssentials;
+
+ pkgCache::VerIterator const InstVer = Cache[I].InstVerIter(Cache);
+ // We apply priorities only to downloadable packages, all others are prio:extra
+ // as an obsolete prio:standard package can't be that standard anymore…
+ if (InstVer->Priority <= pkgCache::State::Extra && InstVer.Downloadable() == true)
+ Score += PrioMap[InstVer->Priority];
+ else
+ Score += PrioMap[pkgCache::State::Extra];
+
+ /* This helps to fix oddball problems with conflicting packages
+ on the same level. We enhance the score of installed packages
+ if those are not obsolete */
+ if (I->CurrentVer != 0 && Cache[I].CandidateVer != 0 && Cache[I].CandidateVerIter(Cache).Downloadable())
+ Score += PrioInstalledAndNotObsolete;
+
+ // propagate score points along dependencies
+ for (pkgCache::DepIterator D = InstVer.DependsList(); not D.end(); ++D)
+ {
+ if (DepMap[D->Type] == 0)
+ continue;
+ pkgCache::PkgIterator const T = D.TargetPkg();
+ if (not D.IsIgnorable(T))
+ {
+ if (D->Version != 0)
+ {
+ pkgCache::VerIterator const IV = Cache[T].InstVerIter(Cache);
+ if (IV.end() || not D.IsSatisfied(IV))
+ continue;
+ }
+ Scores[T->ID] += DepMap[D->Type];
+ }
+
+ std::vector<map_id_t> providers;
+ for (auto Prv = T.ProvidesList(); not Prv.end(); ++Prv)
+ {
+ if (D.IsIgnorable(Prv))
+ continue;
+ auto const PV = Prv.OwnerVer();
+ auto const PP = PV.ParentPkg();
+ if (PV != Cache[PP].InstVerIter(Cache) || not D.IsSatisfied(Prv))
+ continue;
+ providers.push_back(PP->ID);
+ }
+ std::sort(providers.begin(), providers.end());
+ providers.erase(std::unique(providers.begin(), providers.end()), providers.end());
+ for (auto const prv : providers)
+ Scores[prv] += DepMap[D->Type];
+ }
+ }
+
+ // Copy the scores to advoid additive looping
+ std::unique_ptr<int[]> OldScores(new int[Size]);
+ memcpy(OldScores.get(),Scores,sizeof(*Scores)*Size);
+
+ /* Now we cause 1 level of dependency inheritance, that is we add the
+ score of the packages that depend on the target Package. This
+ fortifies high scoring packages */
+ for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
+ {
+ if (Cache[I].InstallVer == 0)
+ continue;
+
+ for (pkgCache::DepIterator D = I.RevDependsList(); D.end() == false; ++D)
+ {
+ // Only do it for the install version
+ if ((pkgCache::Version *)D.ParentVer() != Cache[D.ParentPkg()].InstallVer ||
+ (D->Type != pkgCache::Dep::Depends &&
+ D->Type != pkgCache::Dep::PreDepends &&
+ D->Type != pkgCache::Dep::Recommends))
+ continue;
+
+ // Do not propagate negative scores otherwise
+ // an extra (-2) package might score better than an optional (-1)
+ if (OldScores[D.ParentPkg()->ID] > 0)
+ Scores[I->ID] += OldScores[D.ParentPkg()->ID];
+ }
+ }
+
+ /* Now we propagate along provides. This makes the packages that
+ provide important packages extremely important */
+ for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
+ {
+ auto const transfer = abs(Scores[I->ID] - OldScores[I->ID]);
+ if (transfer == 0)
+ continue;
+
+ std::vector<map_id_t> providers;
+ for (auto Prv = I.ProvidesList(); not Prv.end(); ++Prv)
+ {
+ if (Prv.IsMultiArchImplicit())
+ continue;
+ auto const PV = Prv.OwnerVer();
+ auto const PP = PV.ParentPkg();
+ if (PV != Cache[PP].InstVerIter(Cache))
+ continue;
+ providers.push_back(PP->ID);
+ }
+ std::sort(providers.begin(), providers.end());
+ providers.erase(std::unique(providers.begin(), providers.end()), providers.end());
+ for (auto const prv : providers)
+ Scores[prv] += transfer;
+ }
+
+ /* Protected things are pushed really high up. This number should put them
+ ahead of everything */
+ for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
+ {
+ if ((Flags[I->ID] & Protected) != 0)
+ Scores[I->ID] += AddProtected;
+ if ((I->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential ||
+ (I->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important)
+ Scores[I->ID] += AddEssential;
+ }
+}
+ /*}}}*/
+// ProblemResolver::DoUpgrade - Attempt to upgrade this package /*{{{*/
+// ---------------------------------------------------------------------
+/* This goes through and tries to reinstall packages to make this package
+ installable */
+bool pkgProblemResolver::DoUpgrade(pkgCache::PkgIterator Pkg)
+{
+ pkgDepCache::ActionGroup group(Cache);
+
+ if ((Flags[Pkg->ID] & Upgradable) == 0 || Cache[Pkg].Upgradable() == false)
+ return false;
+ if ((Flags[Pkg->ID] & Protected) == Protected)
+ return false;
+
+ Flags[Pkg->ID] &= ~Upgradable;
+
+ bool WasKept = Cache[Pkg].Keep();
+ if (not Cache.MarkInstall(Pkg, false, 0, false))
+ return false;
+
+ // This must be a virtual package or something like that.
+ if (Cache[Pkg].InstVerIter(Cache).end() == true)
+ return false;
+
+ // Isolate the problem dependency
+ bool Fail = false;
+ for (pkgCache::DepIterator D = Cache[Pkg].InstVerIter(Cache).DependsList(); D.end() == false;)
+ {
+ // Compute a single dependency element (glob or)
+ pkgCache::DepIterator Start = D;
+ pkgCache::DepIterator End = D;
+ for (bool LastOR = true; D.end() == false && LastOR == true;)
+ {
+ LastOR = (D->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or;
+ ++D;
+ if (LastOR == true)
+ End = D;
+ }
+
+ // We only worry about critical deps.
+ if (End.IsCritical() != true)
+ continue;
+
+ // Iterate over all the members in the or group
+ while (1)
+ {
+ // Dep is ok now
+ if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
+ break;
+
+ // Do not change protected packages
+ PkgIterator P = Start.SmartTargetPkg();
+ if (Cache[P].Protect())
+ {
+ if (Debug == true)
+ clog << " Reinst Failed because of protected " << P.FullName(false) << endl;
+ Fail = true;
+ }
+ else
+ {
+ // Upgrade the package if the candidate version will fix the problem.
+ if ((Cache[Start] & pkgDepCache::DepCVer) == pkgDepCache::DepCVer)
+ {
+ if (DoUpgrade(P) == false)
+ {
+ if (Debug == true)
+ clog << " Reinst Failed because of " << P.FullName(false) << endl;
+ Fail = true;
+ }
+ else
+ {
+ Fail = false;
+ break;
+ }
+ }
+ else
+ {
+ /* We let the algorithm deal with conflicts on its next iteration,
+ it is much smarter than us */
+ if (Start.IsNegative() == true)
+ break;
+
+ if (Debug == true)
+ clog << " Reinst Failed early because of " << Start.TargetPkg().FullName(false) << endl;
+ Fail = true;
+ }
+ }
+
+ if (Start == End)
+ break;
+ ++Start;
+ }
+ if (Fail == true)
+ break;
+ }
+
+ // Undo our operations - it might be smart to undo everything this did..
+ if (Fail == true)
+ {
+ if (WasKept == true)
+ Cache.MarkKeep(Pkg, false, false);
+ else
+ Cache.MarkDelete(Pkg, false, 0, false);
+ return false;
+ }
+
+ if (Debug == true)
+ clog << " Re-Instated " << Pkg.FullName(false) << endl;
+ return true;
+}
+ /*}}}*/
+// ProblemResolver::Resolve - calls a resolver to fix the situation /*{{{*/
+bool pkgProblemResolver::Resolve(bool BrokenFix, OpProgress * const Progress)
+{
+ std::string const solver = _config->Find("APT::Solver", "internal");
+ auto const ret = EDSP::ResolveExternal(solver.c_str(), Cache, 0, Progress);
+ if (solver != "internal")
+ return ret;
+ return ResolveInternal(BrokenFix);
+}
+ /*}}}*/
+// ProblemResolver::ResolveInternal - Run the resolution pass /*{{{*/
+// ---------------------------------------------------------------------
+/* This routines works by calculating a score for each package. The score
+ is derived by considering the package's priority and all reverse
+ dependents giving an integer that reflects the amount of breakage that
+ adjusting the package will inflict.
+
+ It goes from highest score to lowest and corrects all of the breaks by
+ keeping or removing the dependent packages. If that fails then it removes
+ the package itself and goes on. The routine should be able to intelligently
+ go from any broken state to a fixed state.
+
+ The BrokenFix flag enables a mode where the algorithm tries to
+ upgrade packages to advoid problems. */
+bool pkgProblemResolver::ResolveInternal(bool const BrokenFix)
+{
+ pkgDepCache::ActionGroup group(Cache);
+
+ if (Debug)
+ Cache.CheckConsistency("resolve start");
+
+ // Record which packages are marked for install
+ bool Again = false;
+ do
+ {
+ Again = false;
+ for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
+ {
+ if (Cache[I].Install() == true)
+ Flags[I->ID] |= PreInstalled;
+ else
+ {
+ if (Cache[I].InstBroken() == true && BrokenFix == true)
+ {
+ Cache.MarkInstall(I, false, 0, false);
+ if (Cache[I].Install() == true)
+ Again = true;
+ }
+
+ Flags[I->ID] &= ~PreInstalled;
+ }
+ Flags[I->ID] |= Upgradable;
+ }
+ }
+ while (Again == true);
+
+ if (Debug == true) {
+ clog << "Starting pkgProblemResolver with broken count: "
+ << Cache.BrokenCount() << endl;
+ }
+
+ MakeScores();
+
+ auto const Size = Cache.Head().PackageCount;
+
+ /* We have to order the packages so that the broken fixing pass
+ operates from highest score to lowest. This prevents problems when
+ high score packages cause the removal of lower score packages that
+ would cause the removal of even lower score packages. */
+ std::unique_ptr<pkgCache::Package *[]> PList(new pkgCache::Package *[Size]);
+ pkgCache::Package **PEnd = PList.get();
+ for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
+ *PEnd++ = I;
+
+ std::sort(PList.get(), PEnd, [this](Package *a, Package *b) { return ScoreSort(a, b) < 0; });
+
+ if (_config->FindB("Debug::pkgProblemResolver::ShowScores",false) == true)
+ {
+ clog << "Show Scores" << endl;
+ for (pkgCache::Package **K = PList.get(); K != PEnd; K++)
+ if (Scores[(*K)->ID] != 0)
+ {
+ pkgCache::PkgIterator Pkg(Cache,*K);
+ clog << Scores[(*K)->ID] << ' ' << APT::PrettyPkg(&Cache, Pkg) << std::endl;
+ }
+ }
+
+ if (Debug == true) {
+ clog << "Starting 2 pkgProblemResolver with broken count: "
+ << Cache.BrokenCount() << endl;
+ }
+
+ /* Now consider all broken packages. For each broken package we either
+ remove the package or fix it's problem. We do this once, it should
+ not be possible for a loop to form (that is a < b < c and fixing b by
+ changing a breaks c) */
+ bool Change = true;
+ bool const TryFixByInstall = _config->FindB("pkgProblemResolver::FixByInstall", true);
+ int const MaxCounter = _config->FindI("pkgProblemResolver::MaxCounter", 20);
+ std::vector<PackageKill> KillList;
+ for (int Counter = 0; Counter < MaxCounter && Change; ++Counter)
+ {
+ Change = false;
+ for (pkgCache::Package **K = PList.get(); K != PEnd; K++)
+ {
+ pkgCache::PkgIterator I(Cache,*K);
+
+ /* We attempt to install this and see if any breaks result,
+ this takes care of some strange cases */
+ if (Cache[I].CandidateVer != Cache[I].InstallVer &&
+ I->CurrentVer != 0 && Cache[I].InstallVer != 0 &&
+ (Flags[I->ID] & PreInstalled) != 0 &&
+ not Cache[I].Protect() &&
+ (Flags[I->ID] & ReInstateTried) == 0)
+ {
+ if (Debug == true)
+ clog << " Try to Re-Instate (" << Counter << ") " << I.FullName(false) << endl;
+ auto const OldBreaks = Cache.BrokenCount();
+ pkgCache::Version *OldVer = Cache[I].InstallVer;
+ Flags[I->ID] &= ReInstateTried;
+
+ Cache.MarkInstall(I, false, 0, false);
+ if (Cache[I].InstBroken() == true ||
+ OldBreaks < Cache.BrokenCount())
+ {
+ if (OldVer == 0)
+ Cache.MarkDelete(I, false, 0, false);
+ else
+ Cache.MarkKeep(I, false, false);
+ }
+ else
+ if (Debug == true)
+ clog << "Re-Instated " << I.FullName(false) << " (" << OldBreaks << " vs " << Cache.BrokenCount() << ')' << endl;
+ }
+
+ if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false)
+ continue;
+
+ if (Debug == true)
+ clog << "Investigating (" << Counter << ") " << APT::PrettyPkg(&Cache, I) << endl;
+
+ // Isolate the problem dependency
+ bool InOr = false;
+ pkgCache::DepIterator Start;
+ pkgCache::DepIterator End;
+ size_t OldSize = 0;
+
+ KillList.clear();
+
+ enum {OrRemove,OrKeep} OrOp = OrRemove;
+ for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList();
+ D.end() == false || InOr == true;)
+ {
+ // Compute a single dependency element (glob or)
+ if (Start == End)
+ {
+ // Decide what to do
+ if (InOr == true && OldSize == KillList.size())
+ {
+ if (OrOp == OrRemove)
+ {
+ if (not Cache[I].Protect())
+ {
+ if (Debug == true)
+ clog << " Or group remove for " << I.FullName(false) << endl;
+ Cache.MarkDelete(I, false, 0, false);
+ Change = true;
+ }
+ }
+ else if (OrOp == OrKeep)
+ {
+ if (Debug == true)
+ clog << " Or group keep for " << I.FullName(false) << endl;
+ Cache.MarkKeep(I, false, false);
+ Change = true;
+ }
+ }
+
+ /* We do an extra loop (as above) to finalize the or group
+ processing */
+ InOr = false;
+ OrOp = OrRemove;
+ D.GlobOr(Start,End);
+ if (Start.end() == true)
+ break;
+
+ // We only worry about critical deps.
+ if (End.IsCritical() != true)
+ continue;
+
+ InOr = Start != End;
+ OldSize = KillList.size();
+ }
+ else
+ {
+ ++Start;
+ // We only worry about critical deps.
+ if (Start.IsCritical() != true)
+ continue;
+ }
+
+ // Dep is ok
+ if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
+ {
+ InOr = false;
+ continue;
+ }
+
+ if (Debug == true)
+ clog << "Broken " << APT::PrettyDep(&Cache, Start) << endl;
+
+ /* Look across the version list. If there are no possible
+ targets then we keep the package and bail. This is necessary
+ if a package has a dep on another package that can't be found */
+ std::unique_ptr<pkgCache::Version *[]> VList(Start.AllTargets());
+ if (VList[0] == 0 && not Cache[I].Protect() &&
+ Start.IsNegative() == false &&
+ Cache[I].NowBroken() == false)
+ {
+ if (InOr == true)
+ {
+ /* No keep choice because the keep being OK could be the
+ result of another element in the OR group! */
+ continue;
+ }
+
+ Change = true;
+ Cache.MarkKeep(I, false, false);
+ break;
+ }
+
+ bool Done = false;
+ for (pkgCache::Version **V = VList.get(); *V != 0; V++)
+ {
+ pkgCache::VerIterator Ver(Cache,*V);
+ pkgCache::PkgIterator Pkg = Ver.ParentPkg();
+
+ /* This is a conflicts, and the version we are looking
+ at is not the currently selected version of the
+ package, which means it is not necessary to
+ remove/keep */
+ if (Cache[Pkg].InstallVer != Ver && Start.IsNegative() == true)
+ {
+ if (Debug)
+ clog << " Conflicts//Breaks against version "
+ << Ver.VerStr() << " for " << Pkg.Name()
+ << " but that is not InstVer, ignoring"
+ << endl;
+ continue;
+ }
+
+ if (Debug == true)
+ clog << " Considering " << Pkg.FullName(false) << ' ' << Scores[Pkg->ID] <<
+ " as a solution to " << I.FullName(false) << ' ' << Scores[I->ID] << endl;
+
+ /* Try to fix the package under consideration rather than
+ fiddle with the VList package */
+ if (Scores[I->ID] <= Scores[Pkg->ID] ||
+ ((Cache[Start] & pkgDepCache::DepNow) == 0 &&
+ End.IsNegative() == false))
+ {
+ // Try a little harder to fix protected packages..
+ if (Cache[I].Protect())
+ {
+ if (DoUpgrade(Pkg) == true)
+ {
+ if (Scores[Pkg->ID] > Scores[I->ID])
+ Scores[Pkg->ID] = Scores[I->ID];
+ break;
+ }
+
+ continue;
+ }
+
+ /* See if a keep will do, unless the package is protected,
+ then installing it will be necessary */
+ bool Installed = Cache[I].Install();
+ Cache.MarkKeep(I, false, false);
+ if (Cache[I].InstBroken() == false)
+ {
+ // Unwind operation will be keep now
+ if (OrOp == OrRemove)
+ OrOp = OrKeep;
+
+ // Restore
+ if (InOr == true && Installed == true)
+ Cache.MarkInstall(I, false, 0, false);
+
+ if (Debug == true)
+ clog << " Holding Back " << I.FullName(false) << " rather than change " << Start.TargetPkg().FullName(false) << endl;
+ }
+ else
+ {
+ if (BrokenFix == false || DoUpgrade(I) == false)
+ {
+ // Consider other options
+ if (InOr == false || Cache[I].Garbage == true)
+ {
+ if (Debug == true)
+ clog << " Removing " << I.FullName(false) << " rather than change " << Start.TargetPkg().FullName(false) << endl;
+ Cache.MarkDelete(I, false, 0, false);
+ if (Counter > 1 && Scores[Pkg->ID] > Scores[I->ID])
+ Scores[I->ID] = Scores[Pkg->ID];
+ }
+ else if (TryFixByInstall == true &&
+ Start.TargetPkg()->CurrentVer == 0 &&
+ Cache[Start.TargetPkg()].Delete() == false &&
+ (Flags[Start.TargetPkg()->ID] & ToRemove) != ToRemove &&
+ Cache.GetCandidateVersion(Start.TargetPkg()).end() == false)
+ {
+ /* Before removing or keeping the package with the broken dependency
+ try instead to install the first not previously installed package
+ solving this dependency. This helps every time a previous solver
+ is removed by the resolver because of a conflict or alike but it is
+ dangerous as it could trigger new breaks/conflicts… */
+ if (Debug == true)
+ clog << " Try Installing " << APT::PrettyPkg(&Cache, Start.TargetPkg()) << " before changing " << I.FullName(false) << std::endl;
+ auto const OldBroken = Cache.BrokenCount();
+ Cache.MarkInstall(Start.TargetPkg(), true, 1, false);
+ OrOp = OrKeep;
+ // FIXME: we should undo the complete MarkInstall process here
+ if (Cache[Start.TargetPkg()].InstBroken() == true || Cache.BrokenCount() > OldBroken) {
+ Cache.MarkDelete(Start.TargetPkg(), false, 1, false);
+ OrOp = OrRemove;
+ }
+ }
+ }
+ }
+
+ Change = true;
+ Done = true;
+ break;
+ }
+ else
+ {
+ if (Start->Type == pkgCache::Dep::DpkgBreaks)
+ {
+ // first, try upgradring the package, if that
+ // does not help, the breaks goes onto the
+ // kill list
+ //
+ // FIXME: use DoUpgrade(Pkg) instead?
+ if (Cache[End] & pkgDepCache::DepGCVer)
+ {
+ if (Debug)
+ clog << " Upgrading " << Pkg.FullName(false) << " due to Breaks field in " << I.FullName(false) << endl;
+ Cache.MarkInstall(Pkg, false, 0, false);
+ continue;
+ }
+ }
+
+ // Skip adding to the kill list if it is protected
+ if (Cache[Pkg].Protect() && Cache[Pkg].Mode != pkgDepCache::ModeDelete)
+ continue;
+
+ if (Debug == true)
+ clog << " Added " << Pkg.FullName(false) << " to the remove list" << endl;
+
+ KillList.push_back({Pkg, End});
+
+ if (Start.IsNegative() == false)
+ break;
+ }
+ }
+
+ // Hm, nothing can possibly satisfy this dep. Nuke it.
+ if (VList[0] == 0 &&
+ Start.IsNegative() == false &&
+ not Cache[I].Protect())
+ {
+ bool Installed = Cache[I].Install();
+ Cache.MarkKeep(I);
+ if (Cache[I].InstBroken() == false)
+ {
+ // Unwind operation will be keep now
+ if (OrOp == OrRemove)
+ OrOp = OrKeep;
+
+ // Restore
+ if (InOr == true && Installed == true)
+ Cache.MarkInstall(I, false, 0, false);
+
+ if (Debug == true)
+ clog << " Holding Back " << I.FullName(false) << " because I can't find " << Start.TargetPkg().FullName(false) << endl;
+ }
+ else
+ {
+ if (Debug == true)
+ clog << " Removing " << I.FullName(false) << " because I can't find " << Start.TargetPkg().FullName(false) << endl;
+ if (InOr == false)
+ Cache.MarkDelete(I, false, 0, false);
+ }
+
+ Change = true;
+ Done = true;
+ }
+
+ // Try some more
+ if (InOr == true)
+ continue;
+
+ if (Done == true)
+ break;
+ }
+
+ // Apply the kill list now
+ if (Cache[I].InstallVer != 0)
+ {
+ for (auto const &J : KillList)
+ {
+ bool foundSomething = false;
+ if ((Cache[J.Dep] & pkgDepCache::DepGNow) == 0)
+ {
+ if (J.Dep.IsNegative() && Cache.MarkDelete(J.Pkg, false, 0, false))
+ {
+ if (Debug)
+ std::clog << " Fixing " << I.FullName(false) << " via remove of " << J.Pkg.FullName(false) << '\n';
+ foundSomething = true;
+ }
+ }
+ else if (Cache.MarkKeep(J.Pkg, false, false))
+ {
+ if (Debug)
+ std::clog << " Fixing " << I.FullName(false) << " via keep of " << J.Pkg.FullName(false) << '\n';
+ foundSomething = true;
+ }
+
+ if (not foundSomething || Counter > 1)
+ {
+ if (Scores[I->ID] > Scores[J.Pkg->ID])
+ {
+ Scores[J.Pkg->ID] = Scores[I->ID];
+ Change = true;
+ }
+ }
+ if (foundSomething)
+ Change = true;
+ }
+ }
+ }
+ }
+
+ if (Debug == true)
+ clog << "Done" << endl;
+
+ if (Cache.BrokenCount() != 0)
+ {
+ // See if this is the result of a hold
+ pkgCache::PkgIterator I = Cache.PkgBegin();
+ for (;I.end() != true; ++I)
+ {
+ if (Cache[I].InstBroken() == false)
+ continue;
+ if (not Cache[I].Protect())
+ return _error->Error(_("Error, pkgProblemResolver::Resolve generated breaks, this may be caused by held packages."));
+ }
+ return _error->Error(_("Unable to correct problems, you have held broken packages."));
+ }
+
+ // set the auto-flags (mvo: I'm not sure if we _really_ need this)
+ pkgCache::PkgIterator I = Cache.PkgBegin();
+ for (;I.end() != true; ++I) {
+ if (Cache[I].NewInstall() && !(Flags[I->ID] & PreInstalled)) {
+ if(_config->FindB("Debug::pkgAutoRemove",false)) {
+ std::clog << "Resolve installed new pkg: " << I.FullName(false)
+ << " (now marking it as auto)" << std::endl;
+ }
+ Cache[I].Flags |= pkgCache::Flag::Auto;
+ }
+ }
+
+ if (Debug)
+ Cache.CheckConsistency("resolve done");
+
+ return true;
+}
+ /*}}}*/
+// ProblemResolver::BreaksInstOrPolicy - Check if the given pkg is broken/*{{{*/
+// ---------------------------------------------------------------------
+/* This checks if the given package is broken either by a hard dependency
+ (InstBroken()) or by introducing a new policy breakage e.g. new
+ unsatisfied recommends for a package that was in "policy-good" state
+
+ Note that this is not perfect as it will ignore further breakage
+ for already broken policy (recommends)
+*/
+bool pkgProblemResolver::InstOrNewPolicyBroken(pkgCache::PkgIterator I)
+{
+ // a broken install is always a problem
+ if (Cache[I].InstBroken() == true)
+ {
+ if (Debug == true)
+ std::clog << " Dependencies are not satisfied for " << APT::PrettyPkg(&Cache, I) << std::endl;
+ return true;
+ }
+
+ // a newly broken policy (recommends/suggests) is a problem
+ if ((Flags[I->ID] & BrokenPolicyAllowed) == 0 &&
+ Cache[I].NowPolicyBroken() == false &&
+ Cache[I].InstPolicyBroken() == true)
+ {
+ if (Debug == true)
+ std::clog << " Policy breaks with upgrade of " << APT::PrettyPkg(&Cache, I) << std::endl;
+ return true;
+ }
+
+ return false;
+}
+ /*}}}*/
+// ProblemResolver::KeepPhasedUpdates - Keep back phased updates /*{{{*/
+// ---------------------------------------------------------------------
+// Hold back upgrades to phased versions of already installed packages, unless
+// they are security updates
+bool pkgProblemResolver::KeepPhasedUpdates()
+{
+ for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
+ {
+ if (not Cache.PhasingApplied(I))
+ continue;
+
+ Cache.MarkKeep(I, false, false);
+ Cache.MarkProtected(I);
+ Protect(I);
+ }
+
+ return true;
+}
+
+ /*}}}*/
+// ProblemResolver::ResolveByKeep - Resolve problems using keep /*{{{*/
+// ---------------------------------------------------------------------
+/* This is the work horse of the soft upgrade routine. It is very gentle
+ in that it does not install or remove any packages. It is assumed that the
+ system was non-broken previously. */
+bool pkgProblemResolver::ResolveByKeep(OpProgress * const Progress)
+{
+ std::string const solver = _config->Find("APT::Solver", "internal");
+ constexpr auto flags = EDSP::Request::UPGRADE_ALL | EDSP::Request::FORBID_NEW_INSTALL | EDSP::Request::FORBID_REMOVE;
+ auto const ret = EDSP::ResolveExternal(solver.c_str(), Cache, flags, Progress);
+ if (solver != "internal")
+ return ret;
+ return ResolveByKeepInternal();
+}
+ /*}}}*/
+// ProblemResolver::ResolveByKeepInternal - Resolve problems using keep /*{{{*/
+// ---------------------------------------------------------------------
+/* This is the work horse of the soft upgrade routine. It is very gentle
+ in that it does not install or remove any packages. It is assumed that the
+ system was non-broken previously. */
+bool pkgProblemResolver::ResolveByKeepInternal()
+{
+ pkgDepCache::ActionGroup group(Cache);
+
+ if (Debug)
+ Cache.CheckConsistency("keep start");
+
+ MakeScores();
+
+ /* We have to order the packages so that the broken fixing pass
+ operates from highest score to lowest. This prevents problems when
+ high score packages cause the removal of lower score packages that
+ would cause the removal of even lower score packages. */
+ auto Size = Cache.Head().PackageCount;
+ pkgCache::Package **PList = new pkgCache::Package *[Size];
+ pkgCache::Package **PEnd = PList;
+ for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
+ *PEnd++ = I;
+
+ std::sort(PList,PEnd,[this](Package *a, Package *b) { return ScoreSort(a, b) < 0; });
+
+
+ if (_config->FindB("Debug::pkgProblemResolver::ShowScores",false) == true)
+ {
+ clog << "Show Scores" << endl;
+ for (pkgCache::Package **K = PList; K != PEnd; K++)
+ if (Scores[(*K)->ID] != 0)
+ {
+ pkgCache::PkgIterator Pkg(Cache,*K);
+ clog << Scores[(*K)->ID] << ' ' << APT::PrettyPkg(&Cache, Pkg) << std::endl;
+ }
+ }
+
+ if (Debug == true)
+ clog << "Entering ResolveByKeep" << endl;
+
+ // Consider each broken package
+ pkgCache::Package **LastStop = 0;
+ for (pkgCache::Package **K = PList; K != PEnd; K++)
+ {
+ pkgCache::PkgIterator I(Cache,*K);
+
+ if (Cache[I].InstallVer == 0)
+ continue;
+
+ if (InstOrNewPolicyBroken(I) == false)
+ continue;
+
+ /* Keep the package. If this works then great, otherwise we have
+ to be significantly more aggressive and manipulate its dependencies */
+ if (not Cache[I].Protect())
+ {
+ if (Debug == true)
+ clog << "Keeping package " << I.FullName(false) << endl;
+ Cache.MarkKeep(I, false, false);
+ if (InstOrNewPolicyBroken(I) == false)
+ {
+ K = PList - 1;
+ continue;
+ }
+ }
+
+ // Isolate the problem dependencies
+ for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false;)
+ {
+ DepIterator Start;
+ DepIterator End;
+ D.GlobOr(Start,End);
+
+ // We only worry about critical deps.
+ if (End.IsCritical() != true)
+ continue;
+
+ // Dep is ok
+ if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
+ continue;
+
+ /* Hm, the group is broken.. I suppose the best thing to do is to
+ is to try every combination of keep/not-keep for the set, but that's
+ slow, and this never happens, just be conservative and assume the
+ list of ors is in preference and keep till it starts to work. */
+ while (true)
+ {
+ if (Debug == true)
+ clog << "Package " << I.FullName(false) << " " << APT::PrettyDep(&Cache, Start) << endl;
+
+ // Look at all the possible provides on this package
+ std::unique_ptr<pkgCache::Version *[]> VList(Start.AllTargets());
+ for (pkgCache::Version **V = VList.get(); *V != 0; V++)
+ {
+ pkgCache::VerIterator Ver(Cache,*V);
+ pkgCache::PkgIterator Pkg = Ver.ParentPkg();
+
+ // It is not keepable
+ if (Cache[Pkg].InstallVer == 0 ||
+ Pkg->CurrentVer == 0)
+ continue;
+
+ if (not Cache[Pkg].Protect())
+ {
+ if (Debug == true)
+ clog << " Keeping Package " << Pkg.FullName(false) << " due to " << Start.DepType() << endl;
+ Cache.MarkKeep(Pkg, false, false);
+ }
+
+ if (InstOrNewPolicyBroken(I) == false)
+ break;
+ }
+
+ if (InstOrNewPolicyBroken(I) == false)
+ break;
+
+ if (Start == End)
+ break;
+ ++Start;
+ }
+
+ if (InstOrNewPolicyBroken(I) == false)
+ break;
+ }
+
+ if (InstOrNewPolicyBroken(I) == true)
+ continue;
+
+ // Restart again.
+ if (K == LastStop) {
+ // I is an iterator based off our temporary package list,
+ // so copy the name we need before deleting the temporary list
+ std::string const LoopingPackage = I.FullName(false);
+ delete[] PList;
+ return _error->Error("Internal Error, pkgProblemResolver::ResolveByKeep is looping on package %s.", LoopingPackage.c_str());
+ }
+ LastStop = K;
+ K = PList - 1;
+ }
+
+ delete[] PList;
+
+ if (Debug)
+ Cache.CheckConsistency("keep done");
+
+ return true;
+}
+ /*}}}*/
+// PrioSortList - Sort a list of versions by priority /*{{{*/
+// ---------------------------------------------------------------------
+/* This is meant to be used in conjunction with AllTargets to get a list
+ of versions ordered by preference. */
+
+struct PrioComp {
+ pkgCache &PrioCache;
+
+ explicit PrioComp(pkgCache &PrioCache) : PrioCache(PrioCache) {
+ }
+
+ bool operator() (pkgCache::Version * const &A, pkgCache::Version * const &B) {
+ return compare(A, B) < 0;
+ }
+
+ int compare(pkgCache::Version * const &A, pkgCache::Version * const &B) {
+ pkgCache::VerIterator L(PrioCache,A);
+ pkgCache::VerIterator R(PrioCache,B);
+
+ if ((L.ParentPkg()->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential &&
+ (R.ParentPkg()->Flags & pkgCache::Flag::Essential) != pkgCache::Flag::Essential)
+ return 1;
+ if ((L.ParentPkg()->Flags & pkgCache::Flag::Essential) != pkgCache::Flag::Essential &&
+ (R.ParentPkg()->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
+ return -1;
+
+ if ((L.ParentPkg()->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important &&
+ (R.ParentPkg()->Flags & pkgCache::Flag::Important) != pkgCache::Flag::Important)
+ return 1;
+ if ((L.ParentPkg()->Flags & pkgCache::Flag::Important) != pkgCache::Flag::Important &&
+ (R.ParentPkg()->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important)
+ return -1;
+
+ if (L->Priority != R->Priority)
+ return R->Priority - L->Priority;
+ return strcmp(L.ParentPkg().Name(),R.ParentPkg().Name());
+ }
+};
+
+void pkgPrioSortList(pkgCache &Cache,pkgCache::Version **List)
+{
+ unsigned long Count = 0;
+ for (pkgCache::Version **I = List; *I != 0; I++)
+ Count++;
+ std::sort(List,List+Count,PrioComp(Cache));
+}
+ /*}}}*/
+
+namespace APT
+{
+
+namespace KernelAutoRemoveHelper
+{
+
+// \brief Returns the uname from a kernel package name, or "" for non-kernel packages.
+std::string getUname(std::string const &packageName)
+{
+
+ static const constexpr char *const prefixes[] = {
+ "linux-image-",
+ "kfreebsd-image-",
+ "gnumach-image-",
+ };
+
+ for (auto prefix : prefixes)
+ {
+ if (likely(not APT::String::Startswith(packageName, prefix)))
+ continue;
+ if (unlikely(APT::String::Endswith(packageName, "-dbgsym")))
+ continue;
+ if (unlikely(APT::String::Endswith(packageName, "-dbg")))
+ continue;
+
+ auto aUname = packageName.substr(strlen(prefix));
+
+ // aUname must start with [0-9]+\.
+ if (aUname.length() < 2)
+ continue;
+ if (strchr("0123456789", aUname[0]) == nullptr)
+ continue;
+ auto dot = aUname.find_first_not_of("0123456789");
+ if (dot == aUname.npos || aUname[dot] != '.')
+ continue;
+
+ return aUname;
+ }
+
+ return "";
+}
+std::string GetProtectedKernelsRegex(pkgCache *cache, bool ReturnRemove)
+{
+ if (_config->FindB("APT::Protect-Kernels", true) == false)
+ return "";
+
+ struct CompareKernel
+ {
+ pkgCache *cache;
+ bool operator()(const std::string &a, const std::string &b) const
+ {
+ return cache->VS->CmpVersion(a, b) < 0;
+ }
+ };
+ bool Debug = _config->FindB("Debug::pkgAutoRemove", false);
+ // kernel version -> list of unames
+ std::map<std::string, std::vector<std::string>, CompareKernel> version2unames(CompareKernel{cache});
+ // needs to be initialized to 0s, might not be set up.
+ utsname uts{};
+ std::string bootedVersion;
+
+ // Get currently booted version, but only when not on reproducible build.
+ if (getenv("SOURCE_DATE_EPOCH") == 0)
+ {
+ if (uname(&uts) != 0)
+ abort();
+ }
+
+ auto VirtualKernelPkg = cache->FindPkg("$kernel", "any");
+ if (VirtualKernelPkg.end())
+ return "";
+
+ for (pkgCache::PrvIterator Prv = VirtualKernelPkg.ProvidesList(); Prv.end() == false; ++Prv)
+ {
+ auto Pkg = Prv.OwnerPkg();
+ if (likely(Pkg->CurrentVer == 0))
+ continue;
+
+ auto pkgUname = APT::KernelAutoRemoveHelper::getUname(Pkg.Name());
+ auto pkgVersion = Pkg.CurrentVer().VerStr();
+
+ if (pkgUname.empty())
+ continue;
+
+ if (Debug)
+ std::clog << "Found kernel " << pkgUname << "(" << pkgVersion << ")" << std::endl;
+
+ version2unames[pkgVersion].push_back(pkgUname);
+
+ if (pkgUname == uts.release)
+ bootedVersion = pkgVersion;
+ }
+
+ if (version2unames.size() == 0)
+ return "";
+
+ auto versions = version2unames.rbegin();
+ std::set<std::string> keep;
+
+ auto keepKernels = (unsigned long)_config->FindI("APT::NeverAutoRemove::KernelCount", 2);
+ if (keepKernels < 2)
+ keepKernels = 2;
+
+ if (Debug)
+ std::clog << "Amount of kernels to keep " << keepKernels << std::endl;
+
+ if (not bootedVersion.empty())
+ {
+ if (Debug)
+ std::clog << "Keeping booted kernel " << bootedVersion << std::endl;
+ keep.insert(bootedVersion);
+ }
+
+ while (keep.size() < keepKernels && versions != version2unames.rend())
+ {
+ auto v = versions->first;
+ if (v == bootedVersion)
+ {
+ versions++;
+ continue;
+ }
+ if (Debug)
+ std::clog << "Keeping previous kernel " << v << std::endl;
+ keep.insert(v);
+ versions++;
+ }
+
+ // Escape special characters '.' and '+' in version strings so we can build a regular expression
+ auto escapeSpecial = [](std::string input) -> std::string {
+ for (size_t pos = 0; (pos = input.find_first_of(".+", pos)) != input.npos; pos += 2) {
+ input.insert(pos, 1, '\\');
+ }
+ return input;
+ };
+ std::ostringstream ss;
+ for (auto &pattern : _config->FindVector("APT::VersionedKernelPackages"))
+ {
+ // Legacy compatibility: Always protected the booted uname and last installed uname
+ if (*uts.release)
+ ss << "|^" << pattern << "-" << escapeSpecial(uts.release) << "$";
+ for (auto const &kernel : version2unames)
+ {
+ if (ReturnRemove ? keep.find(kernel.first) == keep.end() : keep.find(kernel.first) != keep.end())
+ {
+ for (auto const &uname : kernel.second)
+ ss << "|^" << pattern << "-" << escapeSpecial(uname) << "$";
+ }
+ }
+ }
+
+ auto re_with_leading_or = ss.str();
+
+ if (re_with_leading_or.empty())
+ return "";
+
+ auto re = re_with_leading_or.substr(1);
+ if (Debug)
+ std::clog << "Kernel protection regex: " << re << "\n";
+
+ return re;
+}
+
+std::unique_ptr<APT::CacheFilter::Matcher> GetProtectedKernelsFilter(pkgCache *cache, bool returnRemove)
+{
+ auto regex = GetProtectedKernelsRegex(cache, returnRemove);
+
+ if (regex.empty())
+ return std::make_unique<APT::CacheFilter::FalseMatcher>();
+
+ return std::make_unique<APT::CacheFilter::PackageNameMatchesRegEx>(regex);
+}
+
+} // namespace KernelAutoRemoveHelper
+} // namespace APT
generated by cgit v1.2.3 (git 2.39.1) at 2024-11-15 07:39:48 +0000