X-Git-Url: https://git.saurik.com/apt.git/blobdiff_plain/b2e465d6d32d2dc884f58b94acb7e35f671a87fe..fc5aece9d8600b68cf8d654b379b6d840f2a5524:/apt-pkg/algorithms.cc diff --git a/apt-pkg/algorithms.cc b/apt-pkg/algorithms.cc index fb85d12f9..8626d33dc 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 @@ -20,12 +20,17 @@ #include #include #include +#include +#include #include + #include - -#include +#include +#include +#include /*}}}*/ +using namespace std; pkgProblemResolver *pkgProblemResolver::This = 0; @@ -49,21 +54,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 +89,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 +163,7 @@ bool pkgSimulate::Configure(PkgIterator iPkg) else { cout << "Conf "; - Describe(Pkg,cout,false); + Describe(Pkg,cout,false,true); } if (Sim.BrokenCount() != 0) @@ -175,7 +188,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 +226,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 +255,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 +396,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 +571,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 +815,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 +823,7 @@ bool pkgProblemResolver::Resolve(bool BrokenFix) if (Debug == true) clog << " Or group keep for " << I.Name() << endl; Cache.MarkKeep(I); + Change = true; } } @@ -812,21 +834,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 +881,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 +948,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 +1065,20 @@ 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)) { + if(_config->FindI("Debug::pkgAutoRemove",false)) { + std::clog << "Resolve installed new pkg: " << I.Name() + << " (now marking it as auto)" << std::endl; + } + Cache[I].Flags |= pkgCache::Flag::Auto; + } + } + + return true; } /*}}}*/ @@ -1081,18 +1133,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 +1144,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 +1231,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 +1250,238 @@ void pkgPrioSortList(pkgCache &Cache,pkgCache::Version **List) qsort(List,Count,sizeof(*List),PrioComp); } /*}}}*/ + + +// mark a single package in Mark-and-Sweep +void pkgMarkPackage(pkgDepCache &Cache, + const pkgCache::PkgIterator &pkg, + const pkgCache::VerIterator &ver, + bool follow_recommends, + bool follow_suggests) +{ + pkgDepCache::StateCache &state=Cache[pkg]; + pkgCache::VerIterator candver=state.CandidateVerIter(Cache); + pkgCache::VerIterator instver=state.InstVerIter(Cache); + +#if 0 + // If a package was garbage-collected but is now being marked, we + // should re-select it + // For cases when a pkg is set to upgrade and this trigger the + // removal of a no-longer used dependency. if the pkg is set to + // keep again later it will result in broken deps + if(state.Delete() && state.RemoveReason=pkgDepCache::Unused) + { + if(ver==candver) + mark_install(pkg, false, false, NULL); + else if(ver==pkg.CurrentVer()) + MarkKeep(pkg); + + instver=state.InstVerIter(*this); + } +#endif + + // Ignore versions other than the InstVer, and ignore packages + // that are already going to be removed or just left uninstalled. + if(!(ver==instver && !instver.end())) + return; + + // if we are marked already we are done + if(state.Marked) + return; + + //std::cout << "Setting Marked for: " << pkg.Name() << std::endl; + state.Marked=true; + + if(!ver.end()) + { + for(pkgCache::DepIterator d=ver.DependsList(); !d.end(); ++d) + { + if(d->Type==pkgCache::Dep::Depends || + d->Type==pkgCache::Dep::PreDepends || + (follow_recommends && + d->Type==pkgCache::Dep::Recommends) || + (follow_suggests && + d->Type==pkgCache::Dep::Suggests)) + { + // Try all versions of this package. + for(pkgCache::VerIterator V=d.TargetPkg().VersionList(); + !V.end(); ++V) + { + if(_system->VS->CheckDep(V.VerStr(),d->CompareOp, d.TargetVer())) + { + pkgMarkPackage(Cache, V.ParentPkg(), V, + follow_recommends, follow_suggests); + } + } + // Now try virtual packages + for(pkgCache::PrvIterator prv=d.TargetPkg().ProvidesList(); + !prv.end(); ++prv) + { + if(_system->VS->CheckDep(prv.ProvideVersion(), d->CompareOp, + d.TargetVer())) + { + pkgMarkPackage(Cache, prv.OwnerPkg(), prv.OwnerVer(), + follow_recommends, follow_suggests); + } + } + } + } + } +} + + +// Helper for APT::NeverAutoRemove, always include the packages matching +// this regexp into the root-set +inline bool +pkgMarkAlwaysInclude(pkgCache::PkgIterator p, vector alwaysMark) +{ + for(unsigned int i=0;iFindB("APT::AutoRemove::RecommendsImportant",false); + follow_suggests=_config->FindB("APT::AutoRemove::SuggestsImportant", false); + + + // init the "NeverAutoRemove" variable + vector neverAutoRemoveRegexp; + Configuration::Item const *Opts; + Opts = _config->Tree("APT::NeverAutoRemove"); + if (Opts != 0 && Opts->Child != 0) + { + Opts = Opts->Child; + for (; Opts != 0; Opts = Opts->Next) + { + if (Opts->Value.empty() == true) + continue; + + regex_t *p = new regex_t; + if(regcomp(p,Opts->Value.c_str(), + REG_EXTENDED | REG_ICASE | REG_NOSUB) != 0) + { + regfree(p); + for(unsigned int i=0;iError("Regex compilation error for APT::NeverAutoRemove"); + } + neverAutoRemoveRegexp.push_back(p); + } + } + + + // do the mark part, this is the core bit of the algorithm + for(pkgCache::PkgIterator p=Cache.PkgBegin(); !p.end(); ++p) + { + if( (func != NULL ? (*func)(p) : false) || + pkgMarkAlwaysInclude(p, neverAutoRemoveRegexp) || + !(Cache[p].Flags & pkgCache::Flag::Auto) || + (p->Flags & pkgCache::Flag::Essential)) + + { + // the package is installed (and set to keep) + if(Cache[p].Keep() && !p.CurrentVer().end()) + pkgMarkPackage(Cache, p, p.CurrentVer(), + follow_recommends, follow_suggests); + // the package is to be installed + else if(Cache[p].Install()) + pkgMarkPackage(Cache, p, Cache[p].InstVerIter(Cache), + follow_recommends, follow_suggests); + } + } + + + // do the sweep + for(pkgCache::PkgIterator p=Cache.PkgBegin(); !p.end(); ++p) + { + pkgDepCache::StateCache &state=Cache[p]; + + if(!state.Marked) + { + // mark installed but not yet marked stuff as garbage + if(p->CurrentVer != 0) { + state.Garbage=true; + std::cout << "Garbage: " << p.Name() << std::endl; + } + +#if 0 // mvo: the below bits still needs to be ported + + // Be sure not to re-delete already deleted packages. + if(delete_unused && (!p.CurrentVer().end() || state.Install()) && + !state.Delete()) + { + bool do_delete=true; + + // If the package is being upgraded, check if we're + // losing a versioned dep. If the dependency matches + // the previous version and not the new version, keep + // the package back instead of removing it. + if(!p.CurrentVer().end() && state.Install()) + { + const char *vs=p.CurrentVer().VerStr(); + + // Check direct revdeps only. THIS ASSUMES NO + // VERSIONED PROVIDES, but Debian probably won't + // have them for ages if ever. + for(pkgCache::DepIterator revdep=p.RevDependsList(); + !revdep.end(); ++revdep) + { + pkgCache::PkgIterator depender=revdep.ParentPkg(); + // Find which version of the depending package + // will be installed. + pkgCache::VerIterator instver=(*this)[depender].InstVerIter(*this); + + // Only pay attention to strong positive + // dependencies whose parents will be installed. + if(revdep.ParentVer()==instver && + (revdep->Type==pkgCache::Dep::Depends || + revdep->Type==pkgCache::Dep::PreDepends || + (revdep->Type==pkgCache::Dep::Recommends && + follow_recommends))) + { + // If the previous version matched, cancel the + // deletion. (note that I assume that the new + // version does NOT match; otherwise it would + // not be unused!) + if(_system->VS->CheckDep(vs, + revdep->CompareOp, + revdep.TargetVer())) + { + mark_keep(p, false, false, undo); + do_delete=false; + break; + } + } + } + } + + if(do_delete) + mark_delete(p, false, true, undo); + } +#endif + } + } + + // cleanup + for(unsigned int i=0;i