X-Git-Url: https://git.saurik.com/apt.git/blobdiff_plain/200f8c52f6fb977265e0e9b3cdeb5c3214f80dd3..00b47c98ca4a4349686a082eba6d77decbb03a4d:/apt-pkg/algorithms.cc?ds=sidebyside diff --git a/apt-pkg/algorithms.cc b/apt-pkg/algorithms.cc index 60da32d78..7f7cb204f 100644 --- a/apt-pkg/algorithms.cc +++ b/apt-pkg/algorithms.cc @@ -1,6 +1,6 @@ // -*- mode: cpp; mode: fold -*- // Description /*{{{*/ -// $Id: algorithms.cc,v 1.19 1999/06/28 03:11:24 jgg Exp $ +// $Id: algorithms.cc,v 1.31 2000/10/03 23:59:05 jgg Exp $ /* ###################################################################### Algorithms - A set of misc algorithms @@ -33,6 +33,11 @@ pkgSimulate::pkgSimulate(pkgDepCache &Cache) : pkgPackageManager(Cache), { 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 /*{{{*/ @@ -120,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(); @@ -276,7 +284,7 @@ bool pkgDistUpgrade(pkgDepCache &Cache) pkgProblemResolver Fix(Cache); // Hold back held packages. - if (_config->FindB("APT::Ingore-Hold",false) == false) + if (_config->FindB("APT::Ignore-Hold",false) == false) { for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++) { @@ -332,6 +340,7 @@ bool pkgMinimizeUpgrade(pkgDepCache &Cache) // We loop indefinately to get the minimal set size. bool Change = false; + unsigned int Count = 0; do { Change = false; @@ -340,16 +349,21 @@ bool pkgMinimizeUpgrade(pkgDepCache &Cache) // 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 - Change = true; + { + // If keep didnt actually do anything then there was no change.. + if (Cache[I].Upgrade() == false) + Change = true; + } } + Count++; } - while (Change == true); + while (Change == true && Count < 10); if (Cache.BrokenCount() != 0) return _error->Error("Internal Error in pkgMinimizeUpgrade"); @@ -510,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 & pkgCache::Dep::Or) == pkgCache::Dep::Or; + D++; if (LastOR == true) End = D; } @@ -521,52 +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) - { - clog << "Note, a broken or group was found in " << Pkg.Name() << "." << endl; - Fail = true; - break; - } - - // Do not change protected packages - PkgIterator P = Start.SmartTargetPkg(); - if ((Flags[P->ID] & Protected) == Protected) + + // Iterate over all the members in the or group + while (1) { - if (Debug == true) - clog << " Reinet Failed because of protected " << P.Name() << endl; - Fail = true; - break; - } - - // Upgrade the package if the candidate version will fix the problem. - if ((Cache[Start] & pkgDepCache::DepCVer) == pkgDepCache::DepCVer) - { - if (DoUpgrade(P) == false) + // 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 " << 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 == pkgCache::Dep::Conflicts) - continue; - - if (Debug == true) - clog << " 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.. @@ -698,47 +719,84 @@ bool pkgProblemResolver::Resolve(bool BrokenFix) 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; - pkgCache::DepIterator End; - D.GlobOr(Start,End); - // We only worry about critical deps. - if (End.IsCritical() != true) + if (D.IsCritical() != true) + { + D++; 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) - { - if (Debug == true) - clog << "Note, a broken or group was found in " << I.Name() << "." << endl; - if ((Flags[I->ID] & Protected) != Protected) - Cache.MarkDelete(I); - break; - } if (Debug == true) - clog << "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 = End.AllTargets(); + pkgCache::Version **VList = Start.AllTargets(); if (*VList == 0 && (Flags[I->ID] & Protected) != Protected && - End->Type != pkgCache::Dep::Conflicts && + 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); + Cache.MarkKeep(I); break; } @@ -749,37 +807,54 @@ bool pkgProblemResolver::Resolve(bool BrokenFix) pkgCache::PkgIterator Pkg = Ver.ParentPkg(); if (Debug == true) - clog << " 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 && + ((Cache[Start] & pkgDepCache::DepNow) == 0 && End->Type != pkgCache::Dep::Conflicts)) { // 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, unless the package is protected, - then installing it will be necessary */ + 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) - clog << " 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) - clog << " 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]; + } } } @@ -789,7 +864,9 @@ bool pkgProblemResolver::Resolve(bool BrokenFix) } 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; @@ -797,26 +874,36 @@ bool pkgProblemResolver::Resolve(bool BrokenFix) LEnd->Dep = End; LEnd++; - if (End->Type != pkgCache::Dep::Conflicts) + if (Start->Type != pkgCache::Dep::Conflicts) break; } } // Hm, nothing can possibly satisify this dep. Nuke it. - if (VList[0] == 0 && End->Type != pkgCache::Dep::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) - clog << " 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) - clog << " 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; @@ -824,35 +911,42 @@ 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 == pkgCache::Dep::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) - clog << " 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) - clog << " 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)