X-Git-Url: https://git.saurik.com/apt.git/blobdiff_plain/6c139d6e362f04a1582e8a8f511f8aeab031fecf..00b47c98ca4a4349686a082eba6d77decbb03a4d:/apt-pkg/algorithms.cc diff --git a/apt-pkg/algorithms.cc b/apt-pkg/algorithms.cc index e3012489d..7f7cb204f 100644 --- a/apt-pkg/algorithms.cc +++ b/apt-pkg/algorithms.cc @@ -1,19 +1,25 @@ // -*- mode: cpp; mode: fold -*- // Description /*{{{*/ -// $Id: algorithms.cc,v 1.1 1998/07/07 04:17:00 jgg Exp $ +// $Id: algorithms.cc,v 1.31 2000/10/03 23:59:05 jgg Exp $ /* ###################################################################### 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 /*{{{*/ #ifdef __GNUG__ -#pragma implementation "pkglib/algorithms.h" +#pragma implementation "apt-pkg/algorithms.h" #endif -#include -#include -#include +#include +#include +#include #include /*}}}*/ @@ -23,10 +29,15 @@ pkgProblemResolver *pkgProblemResolver::This = 0; // --------------------------------------------------------------------- /* */ pkgSimulate::pkgSimulate(pkgDepCache &Cache) : pkgPackageManager(Cache), - Sim(true,true) + Sim(Cache.GetMap()) { Flags = new unsigned char[Cache.HeaderP->PackageCount]; memset(Flags,0,sizeof(*Flags)*Cache.HeaderP->PackageCount); + + // Fake a filename so as not to activate the media swapping + string Jnk = "SIMULATE"; + for (unsigned int I = 0; I != Cache.Head().PackageCount; I++) + FileNames[I] = Jnk; } /*}}}*/ // Simulate::Install - Simulate unpacking of a package /*{{{*/ @@ -48,12 +59,12 @@ bool pkgSimulate::Install(PkgIterator iPkg,string /*File*/) continue; for (DepIterator D = Sim[I].InstVerIter(Sim).DependsList(); D.end() == false; D++) - if (D->Type == pkgDEP_Conflicts || D->Type == pkgDEP_PreDepends) + if (D->Type == pkgCache::Dep::Conflicts || D->Type == pkgCache::Dep::PreDepends) { if ((Sim[D] & pkgDepCache::DepInstall) == 0) { cout << " [" << I.Name() << " on " << D.TargetPkg().Name() << ']'; - if (D->Type == pkgDEP_Conflicts) + if (D->Type == pkgCache::Dep::Conflicts) _error->Error("Fatal, conflicts violated %s",I.Name()); } } @@ -91,7 +102,7 @@ bool pkgSimulate::Configure(PkgIterator iPkg) (Sim[D] & pkgDepCache::DepInstall) != 0) continue; - if (D->Type == pkgDEP_Conflicts) + if (D->Type == pkgCache::Dep::Conflicts) cout << " Conflicts:" << D.TargetPkg().Name(); else cout << " Depends:" << D.TargetPkg().Name(); @@ -114,14 +125,17 @@ bool pkgSimulate::Configure(PkgIterator iPkg) // Simulate::Remove - Simulate the removal of a package /*{{{*/ // --------------------------------------------------------------------- /* */ -bool pkgSimulate::Remove(PkgIterator iPkg) +bool pkgSimulate::Remove(PkgIterator iPkg,bool Purge) { // Adapt the iterator PkgIterator Pkg = Sim.FindPkg(iPkg.Name()); Flags[Pkg->ID] = 3; Sim.MarkDelete(Pkg); - cout << "Remv " << Pkg.Name(); + if (Purge == true) + cout << "Purg " << Pkg.Name(); + else + cout << "Remv " << Pkg.Name(); if (Sim.BrokenCount() != 0) ShortBreaks(); @@ -159,21 +173,50 @@ bool pkgApplyStatus(pkgDepCache &Cache) { for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++) { + // Only choice for a ReInstReq package is to reinstall + if (I->InstState == pkgCache::State::ReInstReq || + I->InstState == pkgCache::State::HoldReInstReq) + { + if (I.CurrentVer().Downloadable() == true) + Cache.MarkKeep(I); + else + { + // Is this right? Will dpkg choke on an upgrade? + if (Cache[I].CandidateVerIter(Cache).Downloadable() == true) + Cache.MarkInstall(I); + else + return _error->Error("The package %s needs to be reinstalled, " + "but I can't find an archive for it.",I.Name()); + } + + continue; + } + switch (I->CurrentState) { - // This means installation failed somehow - case pkgSTATE_UnPacked: - case pkgSTATE_HalfConfigured: - Cache.MarkKeep(I); + /* This means installation failed somehow - it does not need to be + re-unpacked (probably) */ + case pkgCache::State::UnPacked: + case pkgCache::State::HalfConfigured: + if (I.CurrentVer().Downloadable() == true || + I.State() != pkgCache::PkgIterator::NeedsUnpack) + Cache.MarkKeep(I); + else + { + if (Cache[I].CandidateVerIter(Cache).Downloadable() == true) + Cache.MarkInstall(I); + else + Cache.MarkDelete(I); + } break; // This means removal failed - case pkgSTATE_HalfInstalled: + case pkgCache::State::HalfInstalled: Cache.MarkDelete(I); break; default: - if (I->InstState != pkgSTATE_Ok) + 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.Name()); } @@ -183,15 +226,15 @@ bool pkgApplyStatus(pkgDepCache &Cache) /*}}}*/ // FixBroken - Fix broken packages /*{{{*/ // --------------------------------------------------------------------- -/* This autoinstalls every broken package and then runs ScoredFix on the - result. */ +/* This autoinstalls every broken package and then runs the problem resolver + 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++) @@ -200,10 +243,10 @@ bool pkgFixBroken(pkgDepCache &Cache) Cache[I].Delete() == true) continue; - if ((Cache[I].InstVerIter(Cache).File()->Flags & pkgFLAG_NotSource) == 0) + if (Cache[I].InstVerIter(Cache).Downloadable() == false) continue; - Cache.MarkInstall(I,true); + Cache.MarkInstall(I,true); } pkgProblemResolver Fix(Cache); @@ -216,7 +259,7 @@ bool pkgFixBroken(pkgDepCache &Cache) 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. + The problem resolver is used to resolve the problems. */ bool pkgDistUpgrade(pkgDepCache &Cache) { @@ -229,7 +272,7 @@ bool pkgDistUpgrade(pkgDepCache &Cache) /* 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) + if ((I->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential) Cache.MarkInstall(I,true); /* We do it again over all previously installed packages to force @@ -239,20 +282,95 @@ bool pkgDistUpgrade(pkgDepCache &Cache) Cache.MarkInstall(I,false); pkgProblemResolver Fix(Cache); - + // Hold back held packages. - for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++) + if (_config->FindB("APT::Ignore-Hold",false) == false) { - if (I->SelectedState == pkgSTATE_Hold) + for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++) { - Fix.Protect(I); - Cache.MarkKeep(I); + if (I->SelectedState == pkgCache::State::Hold) + { + Fix.Protect(I); + Cache.MarkKeep(I); + } } } return Fix.Resolve(); } /*}}}*/ +// AllUpgrade - Upgrade as many packages as possible /*{{{*/ +// --------------------------------------------------------------------- +/* Right now the system must be consistent before this can be called. + It also will not change packages marked for install, it only tries + to install packages not marked for install */ +bool pkgAllUpgrade(pkgDepCache &Cache) +{ + pkgProblemResolver Fix(Cache); + + if (Cache.BrokenCount() != 0) + return false; + + // Upgrade all installed packages + for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++) + { + if (Cache[I].Install() == true) + Fix.Protect(I); + + if (_config->FindB("APT::Ingore-Hold",false) == false) + if (I->SelectedState == pkgCache::State::Hold) + continue; + + if (I->CurrentVer != 0 && Cache[I].InstallVer != 0) + Cache.MarkInstall(I,false); + } + + return Fix.ResolveByKeep(); +} + /*}}}*/ +// MinimizeUpgrade - Minimizes the set of packages to be upgraded /*{{{*/ +// --------------------------------------------------------------------- +/* This simply goes over the entire set of packages and tries to keep + each package marked for upgrade. If a conflict is generated then + the package is restored. */ +bool pkgMinimizeUpgrade(pkgDepCache &Cache) +{ + if (Cache.BrokenCount() != 0) + return false; + + // We loop indefinately to get the minimal set size. + bool Change = false; + unsigned int Count = 0; + do + { + Change = false; + for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++) + { + // Not interesting + if (Cache[I].Upgrade() == false || Cache[I].NewInstall() == true) + continue; + + // Keep it and see if that is OK + Cache.MarkKeep(I); + if (Cache.BrokenCount() != 0) + Cache.MarkInstall(I,false); + else + { + // If keep didnt actually do anything then there was no change.. + if (Cache[I].Upgrade() == false) + Change = true; + } + } + Count++; + } + while (Change == true && Count < 10); + + if (Cache.BrokenCount() != 0) + return _error->Error("Internal Error in pkgMinimizeUpgrade"); + + return true; +} + /*}}}*/ // ProblemResolver::pkgProblemResolver - Constructor /*{{{*/ // --------------------------------------------------------------------- @@ -266,7 +384,7 @@ pkgProblemResolver::pkgProblemResolver(pkgDepCache &Cache) : Cache(Cache) memset(Flags,0,sizeof(*Flags)*Size); // Set debug to true to see its decision logic - Debug = false; + Debug = _config->FindB("Debug::pkgProblemResolver",false); } /*}}}*/ // ProblemResolver::ScoreSort - Sort the list by score /*{{{*/ @@ -303,7 +421,7 @@ void pkgProblemResolver::MakeScores() 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) + if ((I->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential) Score += 100; // We transform the priority @@ -326,7 +444,7 @@ void pkgProblemResolver::MakeScores() for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false; D++) { - if (D->Type == pkgDEP_Depends || D->Type == pkgDEP_PreDepends) + if (D->Type == pkgCache::Dep::Depends || D->Type == pkgCache::Dep::PreDepends) Scores[D.TargetPkg()->ID]++; } } @@ -347,7 +465,7 @@ void pkgProblemResolver::MakeScores() { // Only do it for the install version if ((pkgCache::Version *)D.ParentVer() != Cache[D.ParentPkg()].InstallVer || - (D->Type != pkgDEP_Depends && D->Type != pkgDEP_PreDepends)) + (D->Type != pkgCache::Dep::Depends && D->Type != pkgCache::Dep::PreDepends)) continue; Scores[I->ID] += abs(OldScores[D.ParentPkg()->ID]); @@ -370,8 +488,12 @@ void pkgProblemResolver::MakeScores() /* 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; + if ((I->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential) + Scores[I->ID] += 5000; + } delete [] OldScores; } @@ -384,11 +506,16 @@ 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); + // 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;) @@ -397,10 +524,11 @@ bool pkgProblemResolver::DoUpgrade(pkgCache::PkgIterator Pkg) pkgCache::DepIterator Start = D; pkgCache::DepIterator End = D; unsigned char State = 0; - for (bool LastOR = true; D.end() == false && LastOR == true; D++) + for (bool LastOR = true; D.end() == false && LastOR == true;) { State |= Cache[D]; - LastOR = (D->CompareOp & pkgOP_OR) == pkgOP_OR; + LastOR = (D->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or; + D++; if (LastOR == true) End = D; } @@ -408,43 +536,58 @@ bool pkgProblemResolver::DoUpgrade(pkgCache::PkgIterator Pkg) // 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) + // 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 (DoUpgrade(P) == false) + if ((Flags[P->ID] & Protected) == Protected) { if (Debug == true) - cout << " Reinst Failed because of " << P.Name() << endl; + clog << " Reinst Failed because of protected " << P.Name() << 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.Name() << 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->Type == pkgCache::Dep::Conflicts) + break; + + if (Debug == true) + clog << " Reinst Failed early because of " << Start.TargetPkg().Name() << endl; + Fail = true; + } + } + + if (Start == End) break; - } + Start++; } - 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; + if (Fail == true) break; - } } // Undo our operations - it might be smart to undo everything this did.. @@ -458,7 +601,7 @@ bool pkgProblemResolver::DoUpgrade(pkgCache::PkgIterator Pkg) } if (Debug == true) - cout << " Re-Instated " << Pkg.Name() << endl; + clog << " Re-Instated " << Pkg.Name() << endl; return true; } /*}}}*/ @@ -478,7 +621,7 @@ bool pkgProblemResolver::DoUpgrade(pkgCache::PkgIterator Pkg) upgrade packages to advoid problems. */ bool pkgProblemResolver::Resolve(bool BrokenFix) { - unsigned long Size = Cache.HeaderP->PackageCount; + unsigned long Size = Cache.HeaderP->PackageCount; // Record which packages are marked for install bool Again = false; @@ -506,7 +649,7 @@ bool pkgProblemResolver::Resolve(bool BrokenFix) while (Again == true); if (Debug == true) - cout << "Starting" << endl; + clog << "Starting" << endl; MakeScores(); @@ -525,13 +668,13 @@ bool pkgProblemResolver::Resolve(bool BrokenFix) if (Scores[(*K)->ID] != 0) { pkgCache::PkgIterator Pkg(Cache,*K); - cout << Scores[(*K)->ID] << ' ' << Pkg.Name() << + clog << Scores[(*K)->ID] << ' ' << Pkg.Name() << ' ' << (pkgCache::Version *)Pkg.CurrentVer() << ' ' << Cache[Pkg].InstallVer << ' ' << Cache[Pkg].CandidateVer << endl; } */ if (Debug == true) - cout << "Starting 2" << endl; + clog << "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 @@ -550,13 +693,15 @@ bool pkgProblemResolver::Resolve(bool BrokenFix) 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] & Protected) == 0 && + (Flags[I->ID] & ReInstateTried) == 0) { if (Debug == true) - cout << " Try to Re-Instate " << I.Name() << endl; - int OldBreaks = Cache.BrokenCount(); + clog << " Try to Re-Instate " << I.Name() << endl; + unsigned long OldBreaks = Cache.BrokenCount(); pkgCache::Version *OldVer = Cache[I].InstallVer; - + Flags[I->ID] &= ReInstateTried; + Cache.MarkInstall(I,false); if (Cache[I].InstBroken() == true || OldBreaks < Cache.BrokenCount()) @@ -568,51 +713,93 @@ bool pkgProblemResolver::Resolve(bool BrokenFix) } else if (Debug == true) - cout << "Re-Instated " << I.Name() << endl; + clog << "Re-Instated " << I.Name() << " (" << OldBreaks << " vs " << Cache.BrokenCount() << ')' << endl; } if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false) continue; + if (Debug == true) + cout << "Investigating " << I.Name() << endl; + // Isolate the problem dependency PackageKill KillList[100]; PackageKill *LEnd = KillList; - for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false;) + bool InOr = false; + pkgCache::DepIterator Start; + pkgCache::DepIterator End; + PackageKill *OldEnd; + + 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) - pkgCache::DepIterator Start = D; - pkgCache::DepIterator End = D; - unsigned char State = 0; - for (bool LastOR = true; D.end() == false && LastOR == true; D++) + // We only worry about critical deps. + if (D.IsCritical() != true) { - State |= Cache[D]; - LastOR = (D->CompareOp & pkgOP_OR) == pkgOP_OR; - if (LastOR == true) - End = D; + D++; + continue; } - // We only worry about critical deps. - if (End.IsCritical() != true) - continue; + // Compute a single dependency element (glob or) + if (Start == End) + { + // Decide what to do + if (InOr == true) + { + if (OldEnd == LEnd && OrOp == OrRemove) + { + if ((Flags[I->ID] & Protected) != Protected) + { + if (Debug == true) + clog << " Or group remove for " << I.Name() << endl; + Cache.MarkDelete(I); + } + } + if (OldEnd == LEnd && OrOp == OrKeep) + { + if (Debug == true) + clog << " Or group keep for " << I.Name() << endl; + Cache.MarkKeep(I); + } + } + + OrOp = OrRemove; + D.GlobOr(Start,End); + InOr = Start != End; + cout << Start.TargetPkg().Name() << ',' << End.TargetPkg().Name() << ',' << InOr << endl; + OldEnd = LEnd; + } + else + Start++; // 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; + clog << "Package " << I.Name() << " has broken dep on " << Start.TargetPkg().Name() << 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 cant be found */ + pkgCache::Version **VList = Start.AllTargets(); + if (*VList == 0 && (Flags[I->ID] & Protected) != Protected && + Start->Type != pkgCache::Dep::Conflicts && + 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); + break; + } - /* 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++) { @@ -620,66 +807,103 @@ bool pkgProblemResolver::Resolve(bool BrokenFix) pkgCache::PkgIterator Pkg = Ver.ParentPkg(); if (Debug == true) - cout << " Considering " << Pkg.Name() << ' ' << (int)Scores[Pkg->ID] << + clog << " 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)) + ((Cache[Start] & pkgDepCache::DepNow) == 0 && + End->Type != pkgCache::Dep::Conflicts)) { - if ((Flags[I->ID] & Protected) != 0) + // Try a little harder to fix protected packages.. + if ((Flags[I->ID] & Protected) == Protected) + { + if (DoUpgrade(Pkg) == true) + { + Scores[Pkg->ID] = Scores[I->ID]; + break; + } + continue; + } - // See if a keep will do + /* 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); 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); + if (Debug == true) - cout << " Holding Back " << I.Name() << " rather than change " << End.TargetPkg().Name() << endl; + clog << " Holding Back " << I.Name() << " rather than change " << Start.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]; - } + // Consider other options + if (InOr == false) + { + if (Debug == true) + clog << " Removing " << I.Name() << " rather than change " << Start.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 (Debug == true) + clog << " Added " << Pkg.Name() << " to the remove list" << endl; + // Skip adding to the kill list if it is protected if ((Flags[Pkg->ID] & Protected) != 0) continue; LEnd->Pkg = Pkg; LEnd->Dep = End; LEnd++; - if (End->Type != pkgDEP_Conflicts) + + if (Start->Type != pkgCache::Dep::Conflicts) break; } } // Hm, nothing can possibly satisify this dep. Nuke it. - if (VList[0] == 0 && End->Type != pkgDEP_Conflicts) + if (VList[0] == 0 && Start->Type != pkgCache::Dep::Conflicts && + (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); + if (Debug == true) - cout << " Holding Back " << I.Name() << " because I can't find " << End.TargetPkg().Name() << endl; + clog << " Holding Back " << I.Name() << " because I can't find " << Start.TargetPkg().Name() << endl; } else { if (Debug == true) - cout << " Removing " << I.Name() << " because I can't find " << End.TargetPkg().Name() << endl; - Cache.MarkDelete(I); + clog << " Removing " << I.Name() << " because I can't find " << Start.TargetPkg().Name() << endl; + if (InOr == false) + Cache.MarkDelete(I); } Change = true; @@ -687,46 +911,204 @@ bool pkgProblemResolver::Resolve(bool BrokenFix) } delete [] VList; + + // Try some more + if (InOr == true) + continue; + 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) + Change = true; + if ((Cache[J->Dep] & pkgDepCache::DepGNow) == 0) + { + if (J->Dep->Type == pkgCache::Dep::Conflicts) + { + if (Debug == true) + clog << " Fixing " << I.Name() << " via remove of " << J->Pkg.Name() << endl; + Cache.MarkDelete(J->Pkg); + } + } + else { if (Debug == true) - cout << " Fixing " << I.Name() << " via remove of " << J->Pkg.Name() << endl; - Cache.MarkDelete(J->Pkg); + clog << " Fixing " << I.Name() << " via keep of " << J->Pkg.Name() << endl; + Cache.MarkKeep(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 (Counter > 1) + Scores[J->Pkg->ID] = Scores[I->ID]; + } + } + } } if (Debug == true) - cout << "Done" << endl; + clog << "Done" << endl; delete [] Scores; delete [] PList; if (Cache.BrokenCount() != 0) - return _error->Error("Internal error, ScoredFix generated breaks."); + { + // 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."); + } + + return true; +} + /*}}}*/ +// ProblemResolver::ResolveByKeep - Resolve problems using keep /*{{{*/ +// --------------------------------------------------------------------- +/* This is the work horse of the soft upgrade routine. It is very gental + in that it does not install or remove any packages. It is assumed that the + system was non-broken previously. */ +bool pkgProblemResolver::ResolveByKeep() +{ + unsigned long Size = Cache.HeaderP->PackageCount; + + if (Debug == true) + clog << "Entering ResolveByKeep" << 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); + + // 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 || Cache[I].InstBroken() == false) + continue; + + /* Keep the package. If this works then great, otherwise we have + to be significantly more agressive and manipulate its dependencies */ + if ((Flags[I->ID] & Protected) == 0) + { + if (Debug == true) + clog << "Keeping package " << I.Name() << endl; + Cache.MarkKeep(I); + if (Cache[I].InstBroken() == false) + { + K = PList; + continue; + } + } + + // Isolate the problem dependencies + 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 & pkgCache::Dep::Or) == pkgCache::Dep::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) + { + clog << "Note, a broken or group was found in " << I.Name() << "." << endl; + if ((Flags[I->ID] & Protected) == 0) + Cache.MarkKeep(I); + break; + } + + if (Debug == true) + clog << "Package " << I.Name() << " has broken dep on " << End.TargetPkg().Name() << endl; + + // Look at all the possible provides on this package + pkgCache::Version **VList = End.AllTargets(); + for (pkgCache::Version **V = VList; *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.Name() << " due to dep" << endl; + Cache.MarkKeep(Pkg); + } + + if (Cache[I].InstBroken() == false) + break; + } + + if (Cache[I].InstBroken() == false) + break; + } + + if (Cache[I].InstBroken() == true) + continue; + + // Restart again. + if (K == LastStop) + return _error->Error("Internal Error, pkgProblemResolver::ResolveByKeep is looping on package %s.",I.Name()); + LastStop = K; + K = PList; + } return true; } /*}}}*/ +// ProblemResolver::InstallProtect - Install all protected packages /*{{{*/ +// --------------------------------------------------------------------- +/* This is used to make sure protected packages are installed */ +void pkgProblemResolver::InstallProtect() +{ + 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 + Cache.MarkInstall(I,false); + } + } +} + /*}}}*/