diff options
Diffstat (limited to 'apt-pkg/algorithms.cc')
| -rw-r--r-- | apt-pkg/algorithms.cc | 1418 |
1 files changed, 1418 insertions, 0 deletions
diff --git a/apt-pkg/algorithms.cc b/apt-pkg/algorithms.cc new file mode 100644 index 0000000..bb0e2f8 --- /dev/null +++ b/apt-pkg/algorithms.cc @@ -0,0 +1,1418 @@ +// -*- 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/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/packagemanager.h> +#include <apt-pkg/pkgcache.h> +#include <apt-pkg/prettyprinters.h> + +#include <cstdlib> +#include <iostream> +#include <string> +#include <utility> +#include <string.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; +} + /*}}}*/ +// 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::Go2(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(); D.end() == false; ++D) + { + if (DepMap[D->Type] == 0) + continue; + pkgCache::PkgIterator const T = D.TargetPkg(); + if (D->Version != 0) + { + pkgCache::VerIterator const IV = Cache[T].InstVerIter(Cache); + if (IV.end() == true || D.IsSatisfied(IV) == false) + continue; + } + Scores[T->ID] += 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) + { + for (pkgCache::PrvIterator P = I.ProvidesList(); P.end() == false; ++P) + { + // Only do it once per package + if ((pkgCache::Version *)P.OwnerVer() != Cache[P.OwnerPkg()].InstallVer) + continue; + Scores[P.OwnerPkg()->ID] += abs(Scores[I->ID] - OldScores[I->ID]); + } + } + + /* 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(); + Cache.MarkInstall(Pkg, false, 0, 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 ((Flags[P->ID] & Protected) == Protected) + { + 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); + + // 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); + std::vector<PackageKill> KillList; + for (int Counter = 0; Counter != 10 && Change == true; 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 && + (Flags[I->ID] & Protected) == 0 && + (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.resize(0); + + 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 ((Flags[I->ID] & Protected) != Protected) + { + 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 && (Flags[I->ID] & Protected) != Protected && + 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 ((Flags[I->ID] & Protected) == Protected) + { + 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); + // 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); + } + } + } + + 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 ((Flags[Pkg->ID] & Protected) != 0) + 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 && + (Flags[I->ID] & Protected) != Protected) + { + 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 J = KillList.begin(); J != KillList.end(); J++) + { + Change = true; + if ((Cache[J->Dep] & pkgDepCache::DepGNow) == 0) + { + if (J->Dep.IsNegative() == true) + { + if (Debug == true) + clog << " Fixing " << I.FullName(false) << " via remove of " << J->Pkg.FullName(false) << endl; + Cache.MarkDelete(J->Pkg, false, 0, false); + } + } + else + { + if (Debug == true) + clog << " Fixing " << I.FullName(false) << " via keep of " << J->Pkg.FullName(false) << endl; + Cache.MarkKeep(J->Pkg, false, false); + } + + if (Counter > 1) + { + if (Scores[I->ID] > Scores[J->Pkg->ID]) + Scores[J->Pkg->ID] = Scores[I->ID]; + } + } + } + } + } + + 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 ((Flags[I->ID] & Protected) != Protected) + 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; + } + } + + + 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 (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::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); + + 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 ((Flags[I->ID] & Protected) == 0) + { + 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 ((Flags[I->ID] & Protected) == 0) + { + 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; + return true; +} + /*}}}*/ +// ProblemResolver::InstallProtect - deprecated cpu-eating no-op /*{{{*/ +// --------------------------------------------------------------------- +/* Actions issued with FromUser bit set are protected from further + modification (expect by other calls with FromUser set) nowadays , so we + don't need to reissue actions here, they are already set in stone. */ +void pkgProblemResolver::InstallProtect() +{ + pkgDepCache::ActionGroup group(Cache); + + for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I) + { + if ((Flags[I->ID] & Protected) == Protected) + { + if ((Flags[I->ID] & ToRemove) == ToRemove) + Cache.MarkDelete(I); + else + { + // preserve the information whether the package was auto + // or manually installed + bool autoInst = (Cache[I].Flags & pkgCache::Flag::Auto); + Cache.MarkInstall(I, false, 0, !autoInst); + } + } + } +} + /*}}}*/ +// 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)); +} + /*}}}*/ |