diff options
Diffstat (limited to 'apt-pkg/algorithms.cc')
| -rw-r--r-- | apt-pkg/algorithms.cc | 732 |
1 files changed, 732 insertions, 0 deletions
diff --git a/apt-pkg/algorithms.cc b/apt-pkg/algorithms.cc new file mode 100644 index 000000000..e3012489d --- /dev/null +++ b/apt-pkg/algorithms.cc @@ -0,0 +1,732 @@ +// -*- mode: cpp; mode: fold -*- +// Description /*{{{*/ +// $Id: algorithms.cc,v 1.1 1998/07/07 04:17:00 jgg Exp $ +/* ###################################################################### + + Algorithms - A set of misc algorithms + + ##################################################################### */ + /*}}}*/ +// Include Files /*{{{*/ +#ifdef __GNUG__ +#pragma implementation "pkglib/algorithms.h" +#endif +#include <pkglib/algorithms.h> +#include <pkglib/error.h> +#include <pkglib/pkgelement.h> +#include <iostream.h> + /*}}}*/ + +pkgProblemResolver *pkgProblemResolver::This = 0; + +// Simulate::Simulate - Constructor /*{{{*/ +// --------------------------------------------------------------------- +/* */ +pkgSimulate::pkgSimulate(pkgDepCache &Cache) : pkgPackageManager(Cache), + Sim(true,true) +{ + Flags = new unsigned char[Cache.HeaderP->PackageCount]; + memset(Flags,0,sizeof(*Flags)*Cache.HeaderP->PackageCount); +} + /*}}}*/ +// Simulate::Install - Simulate unpacking of a package /*{{{*/ +// --------------------------------------------------------------------- +/* */ +bool pkgSimulate::Install(PkgIterator iPkg,string /*File*/) +{ + // Adapt the iterator + PkgIterator Pkg = Sim.FindPkg(iPkg.Name()); + Flags[Pkg->ID] = 1; + + cout << "Inst " << Pkg.Name(); + 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; D++) + if (D->Type == pkgDEP_Conflicts || D->Type == pkgDEP_PreDepends) + { + if ((Sim[D] & pkgDepCache::DepInstall) == 0) + { + cout << " [" << I.Name() << " on " << D.TargetPkg().Name() << ']'; + if (D->Type == pkgDEP_Conflicts) + _error->Error("Fatal, conflicts violated %s",I.Name()); + } + } + } + + if (Sim.BrokenCount() != 0) + ShortBreaks(); + else + cout << endl; + return true; +} + /*}}}*/ +// Simulate::Configure - Simulate configuration of a Package /*{{{*/ +// --------------------------------------------------------------------- +/* This is not an acurate simulation of relatity, we should really not + install the package.. For some investigations it may be necessary + however. */ +bool pkgSimulate::Configure(PkgIterator iPkg) +{ + // Adapt the iterator + PkgIterator Pkg = Sim.FindPkg(iPkg.Name()); + + Flags[Pkg->ID] = 2; +// Sim.MarkInstall(Pkg,false); + if (Sim[Pkg].InstBroken() == true) + { + cout << "Conf " << Pkg.Name() << " 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 == pkgDEP_Conflicts) + cout << " Conflicts:" << D.TargetPkg().Name(); + else + cout << " Depends:" << D.TargetPkg().Name(); + } + cout << endl; + + _error->Error("Conf Broken %s",Pkg.Name()); + } + else + cout << "Conf " << Pkg.Name(); + + if (Sim.BrokenCount() != 0) + ShortBreaks(); + else + cout << endl; + + return true; +} + /*}}}*/ +// Simulate::Remove - Simulate the removal of a package /*{{{*/ +// --------------------------------------------------------------------- +/* */ +bool pkgSimulate::Remove(PkgIterator iPkg) +{ + // Adapt the iterator + PkgIterator Pkg = Sim.FindPkg(iPkg.Name()); + + Flags[Pkg->ID] = 3; + Sim.MarkDelete(Pkg); + cout << "Remv " << Pkg.Name(); + + 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.Name() << ' '; +/* else + cout << I.Name() << "! ";*/ + } + } + cout << ']' << endl; +} + /*}}}*/ +// 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) +{ + for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++) + { + switch (I->CurrentState) + { + // This means installation failed somehow + case pkgSTATE_UnPacked: + case pkgSTATE_HalfConfigured: + Cache.MarkKeep(I); + break; + + // This means removal failed + case pkgSTATE_HalfInstalled: + Cache.MarkDelete(I); + break; + + default: + if (I->InstState != pkgSTATE_Ok) + return _error->Error("The package %s is not ok and I " + "don't know how to fix it!",I.Name()); + } + } + return true; +} + /*}}}*/ +// FixBroken - Fix broken packages /*{{{*/ +// --------------------------------------------------------------------- +/* This autoinstalls every broken package and then runs ScoredFix on the + result. */ +bool pkgFixBroken(pkgDepCache &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); + + /* 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).File()->Flags & pkgFLAG_NotSource) == 0) + continue; + + Cache.MarkInstall(I,true); + } + + pkgProblemResolver Fix(Cache); + return Fix.Resolve(true); +} + /*}}}*/ +// DistUpgrade - Distribution upgrade /*{{{*/ +// --------------------------------------------------------------------- +/* This autoinstalls every package and then force installs every + pre-existing package. This creates the initial set of conditions which + most likely contain problems because too many things were installed. + + ScoredFix is used to resolve the problems. + */ +bool pkgDistUpgrade(pkgDepCache &Cache) +{ + /* Auto upgrade all installed packages, this provides the basis + for the installation */ + for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++) + if (I->CurrentVer != 0) + Cache.MarkInstall(I,true); + + /* Now, auto upgrade all essential packages - this ensures that + the essential packages are present and working */ + for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++) + if ((I->Flags & pkgFLAG_Essential) == pkgFLAG_Essential) + Cache.MarkInstall(I,true); + + /* We do it again over all previously installed packages to force + conflict resolution on them all. */ + for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++) + if (I->CurrentVer != 0) + Cache.MarkInstall(I,false); + + pkgProblemResolver Fix(Cache); + + // Hold back held packages. + for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++) + { + if (I->SelectedState == pkgSTATE_Hold) + { + Fix.Protect(I); + Cache.MarkKeep(I); + } + } + + return Fix.Resolve(); +} + /*}}}*/ + +// ProblemResolver::pkgProblemResolver - Constructor /*{{{*/ +// --------------------------------------------------------------------- +/* */ +pkgProblemResolver::pkgProblemResolver(pkgDepCache &Cache) : Cache(Cache) +{ + // Allocate memory + unsigned long Size = Cache.HeaderP->PackageCount; + Scores = new signed short[Size]; + Flags = new unsigned char[Size]; + memset(Flags,0,sizeof(*Flags)*Size); + + // Set debug to true to see its decision logic + Debug = false; +} + /*}}}*/ +// ProblemResolver::ScoreSort - Sort the list by score /*{{{*/ +// --------------------------------------------------------------------- +/* */ +int pkgProblemResolver::ScoreSort(const void *a,const void *b) +{ + Package const **A = (Package const **)a; + Package const **B = (Package const **)b; + if (This->Scores[(*A)->ID] > This->Scores[(*B)->ID]) + return -1; + if (This->Scores[(*A)->ID] < This->Scores[(*B)->ID]) + return 1; + return 0; +} + /*}}}*/ +// ProblemResolver::MakeScores - Make the score table /*{{{*/ +// --------------------------------------------------------------------- +/* */ +void pkgProblemResolver::MakeScores() +{ + unsigned long Size = Cache.HeaderP->PackageCount; + memset(Scores,0,sizeof(*Scores)*Size); + + // 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; + + signed short &Score = Scores[I->ID]; + + /* This is arbitary, 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 powerfull normal package (ie libc6) */ + if ((I->Flags & pkgFLAG_Essential) == pkgFLAG_Essential) + Score += 100; + + // We transform the priority + // Important Required Standard Optional Extra + signed short PrioMap[] = {0,3,2,1,-1,-2}; + if (Cache[I].InstVerIter(Cache)->Priority <= 5) + Score += PrioMap[Cache[I].InstVerIter(Cache)->Priority]; + + /* This helps to fix oddball problems with conflicting packages + on the same level. We enhance the score of installed packages */ + if (I->CurrentVer != 0) + Score += 1; + } + + // Now that we have the base scores we go and propogate dependencies + for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++) + { + if (Cache[I].InstallVer == 0) + continue; + + for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false; D++) + { + if (D->Type == pkgDEP_Depends || D->Type == pkgDEP_PreDepends) + Scores[D.TargetPkg()->ID]++; + } + } + + // Copy the scores to advoid additive looping + signed short *OldScores = new signed short[Size]; + memcpy(OldScores,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 != pkgDEP_Depends && D->Type != pkgDEP_PreDepends)) + continue; + + Scores[I->ID] += abs(OldScores[D.ParentPkg()->ID]); + } + } + + /* Now we propogate 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] += 10000; + + delete [] OldScores; +} + /*}}}*/ +// 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) +{ + if ((Flags[Pkg->ID] & Upgradable) == 0 || Cache[Pkg].Upgradable() == false) + return false; + Flags[Pkg->ID] &= ~Upgradable; + + bool WasKept = Cache[Pkg].Keep(); + Cache.MarkInstall(Pkg,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; + unsigned char State = 0; + for (bool LastOR = true; D.end() == false && LastOR == true; D++) + { + State |= Cache[D]; + LastOR = (D->CompareOp & pkgOP_OR) == pkgOP_OR; + if (LastOR == true) + End = D; + } + + // 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 have no idea how to handle this + if (Start != End) + { + cout << "Note, a broken or group was found in " << Pkg.Name() << "." << endl; + Fail = true; + break; + } + + // Upgrade the package if the candidate version will fix the problem. + if ((Cache[Start] & pkgDepCache::DepCVer) == pkgDepCache::DepCVer) + { + PkgIterator P = Start.SmartTargetPkg(); + if (DoUpgrade(P) == false) + { + if (Debug == true) + cout << " Reinst Failed because of " << P.Name() << endl; + Fail = true; + break; + } + } + else + { + /* We let the algorithm deal with conflicts on its next iteration, + it is much smarter than us */ + if (End->Type == pkgDEP_Conflicts) + continue; + + if (Debug == true) + cout << " Reinst Failed early because of " << Start.TargetPkg().Name() << endl; + Fail = true; + break; + } + } + + // Undo our operations - it might be smart to undo everything this did.. + if (Fail == true) + { + if (WasKept == true) + Cache.MarkKeep(Pkg); + else + Cache.MarkDelete(Pkg); + return false; + } + + if (Debug == true) + cout << " Re-Instated " << Pkg.Name() << endl; + return true; +} + /*}}}*/ +// ProblemResolver::Resolve - 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 dependant 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::Resolve(bool BrokenFix) +{ + unsigned long Size = Cache.HeaderP->PackageCount; + + // 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); + if (Cache[I].Install() == true) + Again = true; + } + + Flags[I->ID] &= ~PreInstalled; + } + Flags[I->ID] |= Upgradable; + } + } + while (Again == true); + + if (Debug == true) + cout << "Starting" << endl; + + 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. */ + pkgCache::Package **PList = new pkgCache::Package *[Size]; + pkgCache::Package **PEnd = PList; + for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++) + *PEnd++ = I; + This = this; + qsort(PList,PEnd - PList,sizeof(*PList),&ScoreSort); + +/* for (pkgCache::Package **K = PList; K != PEnd; K++) + if (Scores[(*K)->ID] != 0) + { + pkgCache::PkgIterator Pkg(Cache,*K); + cout << Scores[(*K)->ID] << ' ' << Pkg.Name() << + ' ' << (pkgCache::Version *)Pkg.CurrentVer() << ' ' << + Cache[Pkg].InstallVer << ' ' << Cache[Pkg].CandidateVer << endl; + } */ + + if (Debug == true) + cout << "Starting 2" << 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; + for (int Counter = 0; Counter != 10 && Change == true; Counter++) + { + Change = false; + for (pkgCache::Package **K = PList; 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) + { + if (Debug == true) + cout << " Try to Re-Instate " << I.Name() << endl; + int OldBreaks = Cache.BrokenCount(); + pkgCache::Version *OldVer = Cache[I].InstallVer; + + Cache.MarkInstall(I,false); + if (Cache[I].InstBroken() == true || + OldBreaks < Cache.BrokenCount()) + { + if (OldVer == 0) + Cache.MarkDelete(I); + else + Cache.MarkKeep(I); + } + else + if (Debug == true) + cout << "Re-Instated " << I.Name() << endl; + } + + if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false) + continue; + + // Isolate the problem dependency + PackageKill KillList[100]; + PackageKill *LEnd = KillList; + for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false;) + { + // Compute a single dependency element (glob or) + pkgCache::DepIterator Start = D; + pkgCache::DepIterator End = D; + unsigned char State = 0; + for (bool LastOR = true; D.end() == false && LastOR == true; D++) + { + State |= Cache[D]; + LastOR = (D->CompareOp & pkgOP_OR) == pkgOP_OR; + if (LastOR == true) + End = D; + } + + // 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 have no idea how to handle this + if (Start != End) + { + cout << "Note, a broken or group was found in " << I.Name() << "." << endl; + Cache.MarkDelete(I); + break; + } + + if (Debug == true) + cout << "Package " << I.Name() << " has broken dep on " << End.TargetPkg().Name() << endl; + + /* Conflicts is simple, decide if we should remove this package + or the conflicted one */ + pkgCache::Version **VList = End.AllTargets(); + bool Done = false; + for (pkgCache::Version **V = VList; *V != 0; V++) + { + pkgCache::VerIterator Ver(Cache,*V); + pkgCache::PkgIterator Pkg = Ver.ParentPkg(); + + if (Debug == true) + cout << " Considering " << Pkg.Name() << ' ' << (int)Scores[Pkg->ID] << + " as a solution to " << I.Name() << ' ' << (int)Scores[I->ID] << endl; + if (Scores[I->ID] <= Scores[Pkg->ID] || + ((Cache[End] & pkgDepCache::DepGNow) == 0 && + End->Type != pkgDEP_Conflicts)) + { + if ((Flags[I->ID] & Protected) != 0) + continue; + + // See if a keep will do + Cache.MarkKeep(I); + if (Cache[I].InstBroken() == false) + { + if (Debug == true) + cout << " Holding Back " << I.Name() << " rather than change " << End.TargetPkg().Name() << endl; + } + else + { + if (BrokenFix == false || DoUpgrade(I) == false) + { + if (Debug == true) + cout << " Removing " << I.Name() << " rather than change " << End.TargetPkg().Name() << endl; + Cache.MarkDelete(I); + if (Counter > 1) + Scores[I->ID] = Scores[Pkg->ID]; + } + } + + Change = true; + Done = true; + break; + } + else + { + // Skip this if it is protected + if ((Flags[Pkg->ID] & Protected) != 0) + continue; + + LEnd->Pkg = Pkg; + LEnd->Dep = End; + LEnd++; + if (End->Type != pkgDEP_Conflicts) + break; + } + } + + // Hm, nothing can possibly satisify this dep. Nuke it. + if (VList[0] == 0 && End->Type != pkgDEP_Conflicts) + { + Cache.MarkKeep(I); + if (Cache[I].InstBroken() == false) + { + if (Debug == true) + cout << " Holding Back " << I.Name() << " because I can't find " << End.TargetPkg().Name() << endl; + } + else + { + if (Debug == true) + cout << " Removing " << I.Name() << " because I can't find " << End.TargetPkg().Name() << endl; + Cache.MarkDelete(I); + } + + Change = true; + Done = true; + } + + delete [] VList; + if (Done == true) + break; + } + + // Apply the kill list now + if (Cache[I].InstallVer != 0) + for (PackageKill *J = KillList; J != LEnd; J++) + { + Change = true; + if ((Cache[J->Dep] & pkgDepCache::DepGNow) == 0) + { + if (J->Dep->Type == pkgDEP_Conflicts) + { + if (Debug == true) + cout << " Fixing " << I.Name() << " via remove of " << J->Pkg.Name() << endl; + Cache.MarkDelete(J->Pkg); + } + } + else + { + if (Debug == true) + cout << " Fixing " << I.Name() << " via keep of " << J->Pkg.Name() << endl; + Cache.MarkKeep(J->Pkg); + } + + if (Counter > 1) + Scores[J->Pkg->ID] = Scores[I->ID]; + } + } + } + + if (Debug == true) + cout << "Done" << endl; + + delete [] Scores; + delete [] PList; + + if (Cache.BrokenCount() != 0) + return _error->Error("Internal error, ScoredFix generated breaks."); + + return true; +} + /*}}}*/ |