X-Git-Url: https://git.saurik.com/apt.git/blobdiff_plain/63d3141a1f9875ad970ad7850e56a9bf97256895..6b2f7a60c3d7d22d1d6b0e300ef526d48ff20048:/apt-pkg/orderlist.cc?ds=sidebyside diff --git a/apt-pkg/orderlist.cc b/apt-pkg/orderlist.cc index b46056128..7c950292a 100644 --- a/apt-pkg/orderlist.cc +++ b/apt-pkg/orderlist.cc @@ -1,13 +1,13 @@ // -*- mode: cpp; mode: fold -*- // Description /*{{{*/ -// $Id: orderlist.cc,v 1.11 2000/01/16 08:45:47 jgg Exp $ +// $Id: orderlist.cc,v 1.14 2001/05/07 05:49:43 jgg Exp $ /* ###################################################################### Order List - Represents and Manipulates an ordered list of packages. A list of packages can be ordered by a number of conflicting criteria each given a specific priority. Each package also has a set of flags - indicating some usefull things about it that are derived in the + indicating some useful things about it that are derived in the course of sorting. The pkgPackageManager class uses this class for all of it's installation ordering needs. @@ -39,7 +39,7 @@ ordering. Each of the features can be enabled in the sorting routine at an - arbitary priority to give quite abit of control over the final unpacking + arbitrary priority to give quite abit of control over the final unpacking order. The rules listed above may never be violated and are called Critical. @@ -54,24 +54,33 @@ after flag set. This forces them and all their dependents to be ordered toward the end. + There are complications in this algorithm when presented with cycles. + For all known practical cases it works, all cases where it doesn't work + is fixable by tweaking the package descriptions. However, it should be + possible to impove this further to make some better choices when + presented with cycles. + ##################################################################### */ /*}}}*/ // Include Files /*{{{*/ -#ifdef __GNUG__ -#pragma implementation "apt-pkg/orderlist.h" -#endif #include #include #include #include +#include +#include + +#include /*}}}*/ +using namespace std; + pkgOrderList *pkgOrderList::Me = 0; // OrderList::pkgOrderList - Constructor /*{{{*/ // --------------------------------------------------------------------- /* */ -pkgOrderList::pkgOrderList(pkgDepCache &Cache) : Cache(Cache) +pkgOrderList::pkgOrderList(pkgDepCache *pCache) : Cache(*pCache) { FileList = 0; Primary = 0; @@ -79,10 +88,11 @@ pkgOrderList::pkgOrderList(pkgDepCache &Cache) : Cache(Cache) RevDepends = 0; Remove = 0; LoopCount = -1; - + Debug = _config->FindB("Debug::pkgOrderList",false); + /* Construct the arrays, egcs 1.0.1 bug requires the package count hack */ - unsigned long Size = Cache.HeaderP->PackageCount; + unsigned long Size = Cache.Head().PackageCount; Flags = new unsigned short[Size]; End = List = new Package *[Size]; memset(Flags,0,sizeof(*Flags)*Size); @@ -110,22 +120,29 @@ bool pkgOrderList::IsMissing(PkgIterator Pkg) if (Pkg.State() == pkgCache::PkgIterator::NeedsConfigure && Cache[Pkg].Keep() == true) return false; + + if (FileList == 0) + return false; - if (FileList != 0 && FileList[Pkg->ID].empty() == false) + if (FileList[Pkg->ID].empty() == false) return false; + + // Missing Pseudo packages are missing if the real package is missing + if (pkgCache::VerIterator(Cache, Cache[Pkg].CandidateVer).Pseudo() == true) + return IsMissing(Pkg.Group().FindPkg("all")); + return true; } /*}}}*/ - // OrderList::DoRun - Does an order run /*{{{*/ // --------------------------------------------------------------------- /* The caller is expeted to have setup the desired probe state */ bool pkgOrderList::DoRun() { // Temp list - unsigned long Size = Cache.HeaderP->PackageCount; - Package **NList = new Package *[Size]; - AfterList = new Package *[Size]; + unsigned long Size = Cache.Head().PackageCount; + SPtrArray NList = new Package *[Size]; + SPtrArray AfterList = new Package *[Size]; AfterEnd = AfterList; Depth = 0; @@ -141,8 +158,6 @@ bool pkgOrderList::DoRun() if (VisitNode(PkgIterator(Cache,*I)) == false) { End = OldEnd; - delete [] NList; - delete [] AfterList; return false; } @@ -152,8 +167,7 @@ bool pkgOrderList::DoRun() // Swap the main list to the new list delete [] List; - delete [] AfterList; - List = NList; + List = NList.UnGuard(); return true; } /*}}}*/ @@ -165,22 +179,35 @@ bool pkgOrderList::DoRun() bool pkgOrderList::OrderCritical() { FileList = 0; - - Primary = &pkgOrderList::DepUnPackPre; + + Primary = &pkgOrderList::DepUnPackPreD; Secondary = 0; RevDepends = 0; Remove = 0; LoopCount = 0; - + // Sort Me = this; - qsort(List,End - List,sizeof(*List),&OrderCompareB); - + qsort(List,End - List,sizeof(*List),&OrderCompareB); + if (DoRun() == false) return false; - + if (LoopCount != 0) return _error->Error("Fatal, predepends looping detected"); + + if (Debug == true) + { + clog << "** Critical Unpack ordering done" << endl; + + for (iterator I = List; I != End; I++) + { + PkgIterator P(Cache,*I); + if (IsNow(P) == true) + clog << " " << P.FullName() << ' ' << IsMissing(P) << ',' << IsFlag(P,After) << endl; + } + } + return true; } /*}}}*/ @@ -196,7 +223,7 @@ bool pkgOrderList::OrderUnpack(string *FileList) if (FileList != 0) { WipeFlags(After); - + // Set the inlist flag for (iterator I = List; I != End; I++) { @@ -205,7 +232,7 @@ bool pkgOrderList::OrderUnpack(string *FileList) Flag(*I,After); } } - + Primary = &pkgOrderList::DepUnPackCrit; Secondary = &pkgOrderList::DepConfigure; RevDepends = &pkgOrderList::DepUnPackDep; @@ -216,32 +243,43 @@ bool pkgOrderList::OrderUnpack(string *FileList) Me = this; qsort(List,End - List,sizeof(*List),&OrderCompareA); + if (Debug == true) + clog << "** Pass A" << endl; if (DoRun() == false) return false; - + + if (Debug == true) + clog << "** Pass B" << endl; Secondary = 0; if (DoRun() == false) return false; + if (Debug == true) + clog << "** Pass C" << endl; LoopCount = 0; RevDepends = 0; Remove = 0; // Otherwise the libreadline remove problem occures if (DoRun() == false) return false; + if (Debug == true) + clog << "** Pass D" << endl; LoopCount = 0; Primary = &pkgOrderList::DepUnPackPre; if (DoRun() == false) return false; -/* cout << "----------END" << endl; - - for (iterator I = List; I != End; I++) + if (Debug == true) { - PkgIterator P(Cache,*I); - if (IsNow(P) == true) - cout << P.Name() << ' ' << IsMissing(P) << ',' << IsFlag(P,After) << endl; - }*/ + clog << "** Unpack ordering done" << endl; + + for (iterator I = List; I != End; I++) + { + PkgIterator P(Cache,*I); + if (IsNow(P) == true) + clog << " " << P.FullName() << ' ' << IsMissing(P) << ',' << IsFlag(P,After) << endl; + } + } return true; } @@ -261,32 +299,40 @@ bool pkgOrderList::OrderConfigure() return DoRun(); } /*}}}*/ - // OrderList::Score - Score the package for sorting /*{{{*/ // --------------------------------------------------------------------- /* Higher scores order earlier */ int pkgOrderList::Score(PkgIterator Pkg) { + static int const ScoreDelete = _config->FindI("OrderList::Score::Delete", 500); + // Removal is always done first if (Cache[Pkg].Delete() == true) - return 200; - + return ScoreDelete; + // This should never happen.. if (Cache[Pkg].InstVerIter(Cache).end() == true) return -1; - + + static int const ScoreEssential = _config->FindI("OrderList::Score::Essential", 200); + static int const ScoreImmediate = _config->FindI("OrderList::Score::Immediate", 10); + static int const ScorePreDepends = _config->FindI("OrderList::Score::PreDepends", 50); + int Score = 0; if ((Pkg->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential) - Score += 100; + Score += ScoreEssential; + + if (IsFlag(Pkg,Immediate) == true) + Score += ScoreImmediate; - for (DepIterator D = Cache[Pkg].InstVerIter(Cache).DependsList(); + for (DepIterator D = Cache[Pkg].InstVerIter(Cache).DependsList(); D.end() == false; D++) if (D->Type == pkgCache::Dep::PreDepends) { - Score += 50; + Score += ScorePreDepends; break; } - + // Important Required Standard Optional Extra signed short PrioMap[] = {0,5,4,3,1,0}; if (Cache[Pkg].InstVerIter(Cache)->Priority <= 5) @@ -364,6 +410,7 @@ int pkgOrderList::OrderCompareA(const void *a, const void *b) int ScoreA = Me->Score(A); int ScoreB = Me->Score(B); + if (ScoreA > ScoreB) return -1; @@ -375,7 +422,7 @@ int pkgOrderList::OrderCompareA(const void *a, const void *b) /*}}}*/ // OrderList::OrderCompareB - Order the installation by source /*{{{*/ // --------------------------------------------------------------------- -/* This orders by installation source. This is usefull to handle +/* This orders by installation source. This is useful to handle inter-source breaks */ int pkgOrderList::OrderCompareB(const void *a, const void *b) { @@ -400,6 +447,7 @@ int pkgOrderList::OrderCompareB(const void *a, const void *b) int ScoreA = Me->Score(A); int ScoreB = Me->Score(B); + if (ScoreA > ScoreB) return -1; @@ -409,7 +457,6 @@ int pkgOrderList::OrderCompareB(const void *a, const void *b) return strcmp(A.Name(),B.Name()); } /*}}}*/ - // OrderList::VisitDeps - Visit forward install dependencies /*{{{*/ // --------------------------------------------------------------------- /* This calls the dependency function for the normal forwards dependencies @@ -454,7 +501,7 @@ bool pkgOrderList::VisitRProvides(DepFunc F,VerIterator Ver) /* This routine calls visit on all providing packages. */ bool pkgOrderList::VisitProvides(DepIterator D,bool Critical) { - Version **List = D.AllTargets(); + SPtrArray List = D.AllTargets(); for (Version **I = List; *I != 0; I++) { VerIterator Ver(Cache,*I); @@ -463,10 +510,16 @@ bool pkgOrderList::VisitProvides(DepIterator D,bool Critical) if (Cache[Pkg].Keep() == true && Pkg.State() == PkgIterator::NeedsNothing) continue; - if (D->Type != pkgCache::Dep::Conflicts && Cache[Pkg].InstallVer != *I) + if (D->Type != pkgCache::Dep::Conflicts && + D->Type != pkgCache::Dep::DpkgBreaks && + D->Type != pkgCache::Dep::Obsoletes && + Cache[Pkg].InstallVer != *I) continue; - if (D->Type == pkgCache::Dep::Conflicts && (Version *)Pkg.CurrentVer() != *I) + if ((D->Type == pkgCache::Dep::Conflicts || + D->Type == pkgCache::Dep::DpkgBreaks || + D->Type == pkgCache::Dep::Obsoletes) && + (Version *)Pkg.CurrentVer() != *I) continue; // Skip over missing files @@ -474,12 +527,8 @@ bool pkgOrderList::VisitProvides(DepIterator D,bool Critical) continue; if (VisitNode(Pkg) == false) - { - delete [] List; return false; - } } - delete [] List; return true; } /*}}}*/ @@ -496,8 +545,12 @@ bool pkgOrderList::VisitNode(PkgIterator Pkg) IsFlag(Pkg,AddPending) == true || IsFlag(Pkg,InList) == false) return true; -/* for (int j = 0; j != Depth; j++) cout << ' '; - cout << "Visit " << Pkg.Name() << endl;*/ + if (Debug == true) + { + for (int j = 0; j != Depth; j++) clog << ' '; + clog << "Visit " << Pkg.FullName() << endl; + } + Depth++; // Color grey @@ -550,14 +603,16 @@ bool pkgOrderList::VisitNode(PkgIterator Pkg) Primary = Old; Depth--; - -/* for (int j = 0; j != Depth; j++) cout << ' '; - cout << "Leave " << Pkg.Name() << ' ' << IsFlag(Pkg,Added) << ',' << IsFlag(Pkg,AddPending) << endl;*/ + if (Debug == true) + { + for (int j = 0; j != Depth; j++) clog << ' '; + clog << "Leave " << Pkg.FullName() << ' ' << IsFlag(Pkg,Added) << ',' << IsFlag(Pkg,AddPending) << endl; + } + return true; } /*}}}*/ - // OrderList::DepUnPackCrit - Critical UnPacking ordering /*{{{*/ // --------------------------------------------------------------------- /* Critical unpacking ordering strives to satisfy Conflicts: and @@ -573,7 +628,8 @@ bool pkgOrderList::DepUnPackCrit(DepIterator D) { /* Reverse depenanices are only interested in conflicts, predepend breakage is ignored here */ - if (D->Type != pkgCache::Dep::Conflicts) + if (D->Type != pkgCache::Dep::Conflicts && + D->Type != pkgCache::Dep::Obsoletes) continue; // Duplication elimination, consider only the current version @@ -594,7 +650,10 @@ bool pkgOrderList::DepUnPackCrit(DepIterator D) { /* Forward critical dependencies MUST be correct before the package can be unpacked. */ - if (D->Type != pkgCache::Dep::Conflicts && D->Type != pkgCache::Dep::PreDepends) + if (D->Type != pkgCache::Dep::Conflicts && + D->Type != pkgCache::Dep::DpkgBreaks && + D->Type != pkgCache::Dep::Obsoletes && + D->Type != pkgCache::Dep::PreDepends) continue; /* We wish to check if the dep is okay in the now state of the @@ -636,8 +695,7 @@ bool pkgOrderList::DepUnPackCrit(DepIterator D) // --------------------------------------------------------------------- /* Critical PreDepends (also configure immediate and essential) strives to ensure not only that all conflicts+predepends are met but that this - package will be immediately configurable when it is unpacked. - + package will be immediately configurable when it is unpacked. Loops are preprocessed and logged. */ bool pkgOrderList::DepUnPackPreD(DepIterator D) { @@ -702,7 +760,7 @@ bool pkgOrderList::DepUnPackPre(DepIterator D) else continue; } - + /* We wish to check if the dep is okay in the now state of the target package against the install state of this package. */ if (CheckDep(D) == true) @@ -712,7 +770,7 @@ bool pkgOrderList::DepUnPackPre(DepIterator D) if (IsFlag(D.TargetPkg(),AddPending) == false) continue; } - + // This is the loop detection if (IsFlag(D.TargetPkg(),Added) == true || IsFlag(D.TargetPkg(),AddPending) == true) @@ -766,9 +824,20 @@ bool pkgOrderList::DepUnPackDep(DepIterator D) return false; } else + { if (D->Type == pkgCache::Dep::Depends) if (VisitProvides(D,false) == false) return false; + + if (D->Type == pkgCache::Dep::DpkgBreaks) + { + if (CheckDep(D) == true) + continue; + + if (VisitNode(D.TargetPkg()) == false) + return false; + } + } } return true; } @@ -844,7 +913,6 @@ bool pkgOrderList::DepRemove(DepIterator D) return true; } /*}}}*/ - // OrderList::AddLoop - Add a loop to the loop list /*{{{*/ // --------------------------------------------------------------------- /* We record the loops. This is a relic since loop breaking is done @@ -875,7 +943,7 @@ bool pkgOrderList::AddLoop(DepIterator D) /* */ void pkgOrderList::WipeFlags(unsigned long F) { - unsigned long Size = Cache.HeaderP->PackageCount; + unsigned long Size = Cache.Head().PackageCount; for (unsigned long I = 0; I != Size; I++) Flags[I] &= ~F; } @@ -889,7 +957,7 @@ void pkgOrderList::WipeFlags(unsigned long F) this fails to produce a suitable result. */ bool pkgOrderList::CheckDep(DepIterator D) { - Version **List = D.AllTargets(); + SPtrArray List = D.AllTargets(); bool Hit = false; for (Version **I = List; *I != 0; I++) { @@ -912,10 +980,12 @@ bool pkgOrderList::CheckDep(DepIterator D) if ((Version *)Pkg.CurrentVer() != *I || Pkg.State() != PkgIterator::NeedsNothing) continue; - + /* Conflicts requires that all versions are not present, depends just needs one */ - if (D->Type != pkgCache::Dep::Conflicts) + if (D->Type != pkgCache::Dep::Conflicts && + D->Type != pkgCache::Dep::DpkgBreaks && + D->Type != pkgCache::Dep::Obsoletes) { /* Try to find something that does not have the after flag set if at all possible */ @@ -925,7 +995,6 @@ bool pkgOrderList::CheckDep(DepIterator D) continue; } - delete [] List; return true; } else @@ -933,11 +1002,9 @@ bool pkgOrderList::CheckDep(DepIterator D) if (IsFlag(Pkg,After) == true) Flag(D.ParentPkg(),After); - delete [] List; return false; } } - delete [] List; // We found a hit, but it had the after flag set if (Hit == true && D->Type == pkgCache::Dep::PreDepends) @@ -948,7 +1015,8 @@ bool pkgOrderList::CheckDep(DepIterator D) /* Conflicts requires that all versions are not present, depends just needs one */ - if (D->Type == pkgCache::Dep::Conflicts) + if (D->Type == pkgCache::Dep::Conflicts || + D->Type == pkgCache::Dep::Obsoletes) return true; return false; }