X-Git-Url: https://git.saurik.com/apt.git/blobdiff_plain/b2e465d6d32d2dc884f58b94acb7e35f671a87fe..db1e7193fa7d5b86656c05112b9d6ad6e75845b8:/apt-pkg/algorithms.cc diff --git a/apt-pkg/algorithms.cc b/apt-pkg/algorithms.cc index fb85d12f9..98bd8dd8b 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.32 2001/02/20 07:03:17 jgg Exp $ +// $Id: algorithms.cc,v 1.44 2002/11/28 18:49:16 jgg Exp $ /* ###################################################################### Algorithms - A set of misc algorithms @@ -24,8 +24,9 @@ #include -#include +#include /*}}}*/ +using namespace std; pkgProblemResolver *pkgProblemResolver::This = 0; @@ -49,21 +50,29 @@ pkgSimulate::pkgSimulate(pkgDepCache *Cache) : pkgPackageManager(Cache), /*}}}*/ // Simulate::Describe - Describe a package /*{{{*/ // --------------------------------------------------------------------- -/* */ -void pkgSimulate::Describe(PkgIterator Pkg,ostream &out,bool Now) +/* 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); - if (Now == true) + + out << Pkg.Name(); + + if (Current == true) + { Ver = Pkg.CurrentVer(); - else - Ver = Sim[Pkg].CandidateVerIter(Sim); + if (Ver.end() == false) + out << " [" << Ver.VerStr() << ']'; + } - out << Pkg.Name(); - - if (Ver.end() == true) - return; + if (Candidate == true) + { + Ver = Sim[Pkg].CandidateVerIter(Sim); + if (Ver.end() == true) + return; - out << " (" << Ver.VerStr() << ' ' << Ver.RelStr() << ')'; + out << " (" << Ver.VerStr() << ' ' << Ver.RelStr() << ')'; + } } /*}}}*/ // Simulate::Install - Simulate unpacking of a package /*{{{*/ @@ -76,7 +85,7 @@ bool pkgSimulate::Install(PkgIterator iPkg,string /*File*/) Flags[Pkg->ID] = 1; cout << "Inst "; - Describe(Pkg,cout,false); + Describe(Pkg,cout,true,true); Sim.MarkInstall(Pkg,false); // Look for broken conflicts+predepends. @@ -150,7 +159,7 @@ bool pkgSimulate::Configure(PkgIterator iPkg) else { cout << "Conf "; - Describe(Pkg,cout,false); + Describe(Pkg,cout,false,true); } if (Sim.BrokenCount() != 0) @@ -175,7 +184,7 @@ bool pkgSimulate::Remove(PkgIterator iPkg,bool Purge) cout << "Purg "; else cout << "Remv "; - Describe(Pkg,cout,false); + Describe(Pkg,cout,true,false); if (Sim.BrokenCount() != 0) ShortBreaks(); @@ -213,16 +222,20 @@ bool pkgApplyStatus(pkgDepCache &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().Downloadable() == true) + if (I->CurrentVer != 0 && I.CurrentVer().Downloadable() == true) Cache.MarkKeep(I); else { // Is this right? Will dpkg choke on an upgrade? - if (Cache[I].CandidateVerIter(Cache).Downloadable() == true) + if (Cache[I].CandidateVer != 0 && + Cache[I].CandidateVerIter(Cache).Downloadable() == true) Cache.MarkInstall(I); else return _error->Error(_("The package %s needs to be reinstalled, " @@ -238,12 +251,13 @@ bool pkgApplyStatus(pkgDepCache &Cache) re-unpacked (probably) */ case pkgCache::State::UnPacked: case pkgCache::State::HalfConfigured: - if (I.CurrentVer().Downloadable() == true || + if ((I->CurrentVer != 0 && I.CurrentVer().Downloadable() == true) || I.State() != pkgCache::PkgIterator::NeedsUnpack) Cache.MarkKeep(I); else { - if (Cache[I].CandidateVerIter(Cache).Downloadable() == true) + if (Cache[I].CandidateVer != 0 && + Cache[I].CandidateVerIter(Cache).Downloadable() == true) Cache.MarkInstall(I); else Cache.MarkDelete(I); @@ -378,7 +392,7 @@ bool pkgMinimizeUpgrade(pkgDepCache &Cache) if (Cache.BrokenCount() != 0) return false; - // We loop indefinately to get the minimal set size. + // We loop for 10 tries to get the minimal set size. bool Change = false; unsigned int Count = 0; do @@ -553,6 +567,8 @@ bool pkgProblemResolver::DoUpgrade(pkgCache::PkgIterator Pkg) { if ((Flags[Pkg->ID] & Upgradable) == 0 || Cache[Pkg].Upgradable() == false) return false; + if ((Flags[Pkg->ID] & Protected) == Protected) + return false; Flags[Pkg->ID] &= ~Upgradable; @@ -795,6 +811,7 @@ bool pkgProblemResolver::Resolve(bool BrokenFix) if (Debug == true) clog << " Or group remove for " << I.Name() << endl; Cache.MarkDelete(I); + Change = true; } } if (OldEnd == LEnd && OrOp == OrKeep) @@ -802,6 +819,7 @@ bool pkgProblemResolver::Resolve(bool BrokenFix) if (Debug == true) clog << " Or group keep for " << I.Name() << endl; Cache.MarkKeep(I); + Change = true; } } @@ -812,21 +830,24 @@ bool pkgProblemResolver::Resolve(bool BrokenFix) D.GlobOr(Start,End); if (Start.end() == true) break; - + // We only worry about critical deps. if (End.IsCritical() != true) continue; - + InOr = Start != End; OldEnd = LEnd; - } + } else Start++; - + // Dep is ok if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall) + { + InOr = false; continue; - + } + if (Debug == true) clog << "Package " << I.Name() << " has broken dep on " << Start.TargetPkg().Name() << endl; @@ -856,10 +877,13 @@ bool pkgProblemResolver::Resolve(bool BrokenFix) { pkgCache::VerIterator Ver(Cache,*V); pkgCache::PkgIterator Pkg = Ver.ParentPkg(); - + if (Debug == true) clog << " Considering " << Pkg.Name() << ' ' << (int)Scores[Pkg->ID] << " as a solution to " << I.Name() << ' ' << (int)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->Type != pkgCache::Dep::Conflicts && @@ -920,11 +944,21 @@ bool pkgProblemResolver::Resolve(bool BrokenFix) } else { - if (Debug == true) - clog << " Added " << Pkg.Name() << " to the remove list" << endl; + /* 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->Type == pkgCache::Dep::Conflicts || + Start->Type == pkgCache::Dep::Obsoletes)) + continue; + // Skip adding to the kill list if it is protected if ((Flags[Pkg->ID] & Protected) != 0) continue; + + if (Debug == true) + clog << " Added " << Pkg.Name() << " to the remove list" << endl; LEnd->Pkg = Pkg; LEnd->Dep = End; @@ -1027,6 +1061,17 @@ bool pkgProblemResolver::Resolve(bool BrokenFix) 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, but + // I didn't managed + pkgCache::PkgIterator I = Cache.PkgBegin(); + for (;I.end() != true; I++) { + if (Cache[I].NewInstall() && !(Flags[I->ID] & PreInstalled)) { + std::cout << "Resolve installed new pkg: " << I.Name() << " (now marking it as auto)" << std::endl; + Cache[I].Flags |= pkgCache::Flag::Auto; + } + } + + return true; } /*}}}*/ @@ -1081,18 +1126,10 @@ bool pkgProblemResolver::ResolveByKeep() // 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; - } - + DepIterator Start; + DepIterator End; + D.GlobOr(Start,End); + // We only worry about critical deps. if (End.IsCritical() != true) continue; @@ -1100,42 +1137,47 @@ bool pkgProblemResolver::ResolveByKeep() // 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 - SPtrArray VList = End.AllTargets(); - for (pkgCache::Version **V = VList; *V != 0; V++) + + /* 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 thats + 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) { - pkgCache::VerIterator Ver(Cache,*V); - pkgCache::PkgIterator Pkg = Ver.ParentPkg(); - - // It is not keepable - if (Cache[Pkg].InstallVer == 0 || - Pkg->CurrentVer == 0) - continue; + if (Debug == true) + clog << "Package " << I.Name() << " has broken dep on " << Start.TargetPkg().Name() << endl; - if ((Flags[I->ID] & Protected) == 0) + // Look at all the possible provides on this package + SPtrArray VList = Start.AllTargets(); + for (pkgCache::Version **V = VList; *V != 0; V++) { - if (Debug == true) - clog << " Keeping Package " << Pkg.Name() << " due to dep" << endl; - Cache.MarkKeep(Pkg); + 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 (Start == End) + break; + Start++; + } + if (Cache[I].InstBroken() == false) break; } @@ -1182,14 +1224,14 @@ static int PrioComp(const void *A,const void *B) pkgCache::VerIterator R(*PrioCache,*(pkgCache::Version **)B); if ((L.ParentPkg()->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential && - (L.ParentPkg()->Flags & pkgCache::Flag::Essential) != pkgCache::Flag::Essential) - return 1; + (R.ParentPkg()->Flags & pkgCache::Flag::Essential) != pkgCache::Flag::Essential) + return 1; if ((L.ParentPkg()->Flags & pkgCache::Flag::Essential) != pkgCache::Flag::Essential && - (L.ParentPkg()->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential) - return -1; + (R.ParentPkg()->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential) + return -1; if (L->Priority != R->Priority) - return L->Priority - R->Priority; + return R->Priority - L->Priority; return strcmp(L.ParentPkg().Name(),R.ParentPkg().Name()); } void pkgPrioSortList(pkgCache &Cache,pkgCache::Version **List) @@ -1201,3 +1243,107 @@ void pkgPrioSortList(pkgCache &Cache,pkgCache::Version **List) qsort(List,Count,sizeof(*List),PrioComp); } /*}}}*/ + + +// pkgMarkPkgUsed - Mark used packages as dirty /*{{{*/ +// --------------------------------------------------------------------- +/* Mark all reachable packages as dirty. */ +void pkgMarkPkgUsed(pkgDepCache &Cache, pkgCache::PkgIterator Pkg, + pkgCache::State::PkgRemoveState DirtLevel) +{ + // If it is not installed, and we are in manual mode, ignore it + if ((Pkg->CurrentVer == 0 && Cache[Pkg].Install() == false || Cache[Pkg].Delete() == true) && + DirtLevel == pkgCache::State::RemoveManual) + { +// fprintf(stdout,"This one is not installed/virtual %s %d %d\n", Pkg.Name(), Pkg->AutomaticRemove, DirtLevel); + return; + } + + // If it is not installed, and it is not virtual, ignore it + if ((Pkg->CurrentVer == 0 && Cache[Pkg].Install() == false || Cache[Pkg].Delete() == true) && + Pkg->VersionList != 0) + { +// fprintf(stdout,"This one is not installed %s %d %d\n", Pkg.Name(), Pkg->AutomaticRemove, DirtLevel); + return; + } + + // If it is similar or more dirty than we are ;-), because we've been here already, don't mark it + // This is necessary because virtual packages just relay the current level, + // so it may be possible e.g. that this was already seen with ::RemoveSuggested, but + // we are ::RemoveRequired + if (Cache[Pkg].Dirty() >= DirtLevel) + { + //fprintf(stdout,"Seen already %s %d %d\n", Pkg.Name(), Pkg->AutomaticRemove, DirtLevel); + return; + } + + // If it is less important than the current DirtLevel, don't mark it + if (Cache[Pkg].AutomaticRemove != pkgCache::State::RemoveManual && + Cache[Pkg].AutomaticRemove > DirtLevel) + { +// fprintf(stdout,"We don't need %s %d %d %d\n", Pkg.Name(), Pkg->AutomaticRemove, DirtLevel, Cache[Pkg].Dirty()); + return; + } + + // Mark it as used + Cache.SetDirty(Pkg, DirtLevel); + + //fprintf(stdout,"We keep %s %d %d\n", Pkg.Name(), Pkg->AutomaticRemove, DirtLevel); + + // We are a virtual package + if (Pkg->VersionList == 0) + { +// fprintf(stdout,"We are virtual %s %d %d\n", Pkg.Name(), Pkg->AutomaticRemove, DirtLevel); + for (pkgCache::PrvIterator Prv = Pkg.ProvidesList(); ! Prv.end(); ++Prv) + pkgMarkPkgUsed (Cache, Prv.OwnerPkg(), DirtLevel); + return; + } + + // Depending on the type of dependency, follow it + for (pkgCache::DepIterator D = Cache[Pkg].InstVerIter(Cache).DependsList(); ! D.end(); ++D) + { +// fprintf(stdout,"We depend on %s %s\n", D.TargetPkg().Name(), D.DepType()); + + switch(D->Type) + { + case pkgCache::Dep::Depends: + case pkgCache::Dep::PreDepends: + pkgMarkPkgUsed (Cache, D.TargetPkg(), pkgCache::State::RemoveRequired); + break; + case pkgCache::Dep::Recommends: + pkgMarkPkgUsed (Cache, D.TargetPkg(), pkgCache::State::RemoveRecommended); + break; + case pkgCache::Dep::Suggests: + pkgMarkPkgUsed (Cache, D.TargetPkg(), pkgCache::State::RemoveSuggested); + break; + case pkgCache::Dep::Conflicts: + case pkgCache::Dep::Replaces: + case pkgCache::Dep::Obsoletes: + // We don't handle these here + break; + } + } +// fprintf(stdout,"We keep %s %d %d \n", Pkg.Name(), Pkg->AutomaticRemove, DirtLevel); +} + /*}}}*/ + +bool pkgMarkUsed(pkgDepCache &Cache) +{ + // debug only + for (pkgCache::PkgIterator Pkg = Cache.PkgBegin(); ! Pkg.end(); ++Pkg) + if(!Cache[Pkg].Dirty() && Cache[Pkg].AutomaticRemove > 0) + std::cout << "has auto-remove information: " << Pkg.Name() + << " " << (int)Cache[Pkg].AutomaticRemove + << std::endl; + + // init with defaults + for (pkgCache::PkgIterator Pkg = Cache.PkgBegin(); ! Pkg.end(); ++Pkg) + Cache.SetDirty(Pkg, pkgCache::State::RemoveUnknown); + + // go recursive over the cache + for (pkgCache::PkgIterator Pkg = Cache.PkgBegin(); ! Pkg.end(); ++Pkg) + pkgMarkPkgUsed (Cache, Pkg, pkgCache::State::RemoveManual); + + + return true; +}