X-Git-Url: https://git.saurik.com/apt.git/blobdiff_plain/6dd8400ca787ef832d87121f304f98ad152dc3a6..06a8e0dcb37796136be983b247c5d1bbfdf47a2e:/apt-pkg/orderlist.cc diff --git a/apt-pkg/orderlist.cc b/apt-pkg/orderlist.cc index 7c950292a..bfdc50e6c 100644 --- a/apt-pkg/orderlist.cc +++ b/apt-pkg/orderlist.cc @@ -63,33 +63,34 @@ ##################################################################### */ /*}}}*/ // Include Files /*{{{*/ +#include + #include #include #include -#include -#include #include +#include +#include +#include +#include +#include #include /*}}}*/ using namespace std; -pkgOrderList *pkgOrderList::Me = 0; - // OrderList::pkgOrderList - Constructor /*{{{*/ // --------------------------------------------------------------------- /* */ -pkgOrderList::pkgOrderList(pkgDepCache *pCache) : Cache(*pCache) +pkgOrderList::pkgOrderList(pkgDepCache *pCache) : d(NULL), Cache(*pCache), + Primary(NULL), Secondary(NULL), + RevDepends(NULL), Remove(NULL), + AfterEnd(NULL), FileList(NULL), + LoopCount(-1), Depth(0) { - FileList = 0; - Primary = 0; - Secondary = 0; - 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.Head().PackageCount; @@ -117,7 +118,8 @@ bool pkgOrderList::IsMissing(PkgIterator Pkg) return false; // Skip Packages that need configure only. - if (Pkg.State() == pkgCache::PkgIterator::NeedsConfigure && + if ((Pkg.State() == pkgCache::PkgIterator::NeedsConfigure || + Pkg.State() == pkgCache::PkgIterator::NeedsNothing) && Cache[Pkg].Keep() == true) return false; @@ -127,10 +129,6 @@ bool pkgOrderList::IsMissing(PkgIterator Pkg) 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; } /*}}}*/ @@ -141,33 +139,33 @@ bool pkgOrderList::DoRun() { // Temp list unsigned long Size = Cache.Head().PackageCount; - SPtrArray NList = new Package *[Size]; - SPtrArray AfterList = new Package *[Size]; - AfterEnd = AfterList; + std::unique_ptr NList(new Package *[Size]); + std::unique_ptr AfterList(new Package *[Size]); + AfterEnd = AfterList.get(); Depth = 0; WipeFlags(Added | AddPending | Loop | InList); - for (iterator I = List; I != End; I++) + for (iterator I = List; I != End; ++I) Flag(*I,InList); // Rebuild the main list into the temp list. iterator OldEnd = End; - End = NList; - for (iterator I = List; I != OldEnd; I++) - if (VisitNode(PkgIterator(Cache,*I)) == false) + End = NList.get(); + for (iterator I = List; I != OldEnd; ++I) + if (VisitNode(PkgIterator(Cache,*I), "DoRun") == false) { End = OldEnd; return false; } // Copy the after list to the end of the main list - for (Package **I = AfterList; I != AfterEnd; I++) + for (Package **I = AfterList.get(); I != AfterEnd; I++) *End++ = *I; // Swap the main list to the new list delete [] List; - List = NList.UnGuard(); + List = NList.release(); return true; } /*}}}*/ @@ -187,8 +185,7 @@ bool pkgOrderList::OrderCritical() LoopCount = 0; // Sort - Me = this; - qsort(List,End - List,sizeof(*List),&OrderCompareB); + std::sort(List,End, [this](Package *a, Package *b) { return OrderCompareB(a, b) < 0; } ); if (DoRun() == false) return false; @@ -200,7 +197,7 @@ bool pkgOrderList::OrderCritical() { clog << "** Critical Unpack ordering done" << endl; - for (iterator I = List; I != End; I++) + for (iterator I = List; I != End; ++I) { PkgIterator P(Cache,*I); if (IsNow(P) == true) @@ -225,7 +222,7 @@ bool pkgOrderList::OrderUnpack(string *FileList) WipeFlags(After); // Set the inlist flag - for (iterator I = List; I != End; I++) + for (iterator I = List; I != End; ++I) { PkgIterator P(Cache,*I); if (IsMissing(P) == true && IsNow(P) == true) @@ -240,8 +237,7 @@ bool pkgOrderList::OrderUnpack(string *FileList) LoopCount = -1; // Sort - Me = this; - qsort(List,End - List,sizeof(*List),&OrderCompareA); + std::sort(List,End, [this](Package *a, Package *b) { return OrderCompareA(a, b) < 0; }); if (Debug == true) clog << "** Pass A" << endl; @@ -258,7 +254,7 @@ bool pkgOrderList::OrderUnpack(string *FileList) clog << "** Pass C" << endl; LoopCount = 0; RevDepends = 0; - Remove = 0; // Otherwise the libreadline remove problem occures + Remove = 0; // Otherwise the libreadline remove problem occurs if (DoRun() == false) return false; @@ -273,7 +269,7 @@ bool pkgOrderList::OrderUnpack(string *FileList) { clog << "** Unpack ordering done" << endl; - for (iterator I = List; I != End; I++) + for (iterator I = List; I != End; ++I) { PkgIterator P(Cache,*I); if (IsNow(P) == true) @@ -304,9 +300,8 @@ bool pkgOrderList::OrderConfigure() /* Higher scores order earlier */ int pkgOrderList::Score(PkgIterator Pkg) { - static int const ScoreDelete = _config->FindI("OrderList::Score::Delete", 500); - - // Removal is always done first + // Removals should be done after we dealt with essentials + static int const ScoreDelete = _config->FindI("OrderList::Score::Delete", 100); if (Cache[Pkg].Delete() == true) return ScoreDelete; @@ -326,17 +321,19 @@ int pkgOrderList::Score(PkgIterator Pkg) Score += ScoreImmediate; for (DepIterator D = Cache[Pkg].InstVerIter(Cache).DependsList(); - D.end() == false; D++) + D.end() == false; ++D) if (D->Type == pkgCache::Dep::PreDepends) { Score += ScorePreDepends; break; } - // Important Required Standard Optional Extra - signed short PrioMap[] = {0,5,4,3,1,0}; + // Required Important Standard Optional Extra if (Cache[Pkg].InstVerIter(Cache)->Priority <= 5) + { + signed short PrioMap[] = {0,5,4,3,1,0}; Score += PrioMap[Cache[Pkg].InstVerIter(Cache)->Priority]; + } return Score; } /*}}}*/ @@ -382,21 +379,21 @@ static int BoolCompare(bool A,bool B) // --------------------------------------------------------------------- /* This provides a first-pass sort of the list and gives a decent starting point for further complete ordering. It is used by OrderUnpack only */ -int pkgOrderList::OrderCompareA(const void *a, const void *b) +int pkgOrderList::OrderCompareA(Package *a, Package *b) { - PkgIterator A(Me->Cache,*(Package **)a); - PkgIterator B(Me->Cache,*(Package **)b); + PkgIterator A(Cache,a); + PkgIterator B(Cache,b); // We order packages with a set state toward the front int Res; - if ((Res = BoolCompare(Me->IsNow(A),Me->IsNow(B))) != 0) + if ((Res = BoolCompare(IsNow(A),IsNow(B))) != 0) return -1*Res; // We order missing files to toward the end -/* if (Me->FileList != 0) +/* if (FileList != 0) { - if ((Res = BoolCompare(Me->IsMissing(A), - Me->IsMissing(B))) != 0) + if ((Res = BoolCompare(IsMissing(A), + IsMissing(B))) != 0) return Res; }*/ @@ -408,8 +405,8 @@ int pkgOrderList::OrderCompareA(const void *a, const void *b) B.State() != pkgCache::PkgIterator::NeedsNothing) return 1; - int ScoreA = Me->Score(A); - int ScoreB = Me->Score(B); + int ScoreA = Score(A); + int ScoreB = Score(B); if (ScoreA > ScoreB) return -1; @@ -424,10 +421,10 @@ int pkgOrderList::OrderCompareA(const void *a, const void *b) // --------------------------------------------------------------------- /* This orders by installation source. This is useful to handle inter-source breaks */ -int pkgOrderList::OrderCompareB(const void *a, const void *b) +int pkgOrderList::OrderCompareB(Package *a, Package *b) { - PkgIterator A(Me->Cache,*(Package **)a); - PkgIterator B(Me->Cache,*(Package **)b); + PkgIterator A(Cache,a); + PkgIterator B(Cache,b); if (A.State() != pkgCache::PkgIterator::NeedsNothing && B.State() == pkgCache::PkgIterator::NeedsNothing) @@ -437,7 +434,7 @@ int pkgOrderList::OrderCompareB(const void *a, const void *b) B.State() != pkgCache::PkgIterator::NeedsNothing) return 1; - int F = Me->FileCmp(A,B); + int F = FileCmp(A,B); if (F != 0) { if (F > 0) @@ -445,8 +442,8 @@ int pkgOrderList::OrderCompareB(const void *a, const void *b) return 1; } - int ScoreA = Me->Score(A); - int ScoreB = Me->Score(B); + int ScoreA = Score(A); + int ScoreB = Score(B); if (ScoreA > ScoreB) return -1; @@ -491,44 +488,76 @@ bool pkgOrderList::VisitRProvides(DepFunc F,VerIterator Ver) return true; bool Res = true; - for (PrvIterator P = Ver.ProvidesList(); P.end() == false; P++) + for (PrvIterator P = Ver.ProvidesList(); P.end() == false; ++P) Res &= (this->*F)(P.ParentPkg().RevDependsList()); - return true; + return Res; } /*}}}*/ // OrderList::VisitProvides - Visit all of the providing packages /*{{{*/ // --------------------------------------------------------------------- -/* This routine calls visit on all providing packages. */ +/* This routine calls visit on all providing packages. + + If the dependency is negative it first visits packages which are + intended to be removed and after that all other packages. + It does so to avoid situations in which this package is used to + satisfy a (or-group/provides) dependency of another package which + could have been satisfied also by upgrading another package - + otherwise we have more broken packages dpkg needs to auto- + deconfigure and in very complicated situations it even decides + against it! */ bool pkgOrderList::VisitProvides(DepIterator D,bool Critical) -{ - SPtrArray List = D.AllTargets(); - for (Version **I = List; *I != 0; I++) +{ + std::unique_ptr List(D.AllTargets()); + for (Version **I = List.get(); *I != 0; ++I) { VerIterator Ver(Cache,*I); PkgIterator Pkg = Ver.ParentPkg(); + if (D.IsNegative() == true && Cache[Pkg].Delete() == false) + continue; + if (Cache[Pkg].Keep() == true && Pkg.State() == PkgIterator::NeedsNothing) continue; - - if (D->Type != pkgCache::Dep::Conflicts && - D->Type != pkgCache::Dep::DpkgBreaks && - D->Type != pkgCache::Dep::Obsoletes && + + if (D.IsNegative() == false && Cache[Pkg].InstallVer != *I) continue; - - if ((D->Type == pkgCache::Dep::Conflicts || - D->Type == pkgCache::Dep::DpkgBreaks || - D->Type == pkgCache::Dep::Obsoletes) && + + if (D.IsNegative() == true && (Version *)Pkg.CurrentVer() != *I) continue; - + // Skip over missing files if (Critical == false && IsMissing(D.ParentPkg()) == true) continue; - if (VisitNode(Pkg) == false) + if (VisitNode(Pkg, "Provides-1") == false) return false; } + if (D.IsNegative() == false) + return true; + for (Version **I = List.get(); *I != 0; ++I) + { + VerIterator Ver(Cache,*I); + PkgIterator Pkg = Ver.ParentPkg(); + + if (Cache[Pkg].Delete() == true) + continue; + + if (Cache[Pkg].Keep() == true && Pkg.State() == PkgIterator::NeedsNothing) + continue; + + if ((Version *)Pkg.CurrentVer() != *I) + continue; + + // Skip over missing files + if (Critical == false && IsMissing(D.ParentPkg()) == true) + continue; + + if (VisitNode(Pkg, "Provides-2") == false) + return false; + } + return true; } /*}}}*/ @@ -536,10 +565,10 @@ bool pkgOrderList::VisitProvides(DepIterator D,bool Critical) // --------------------------------------------------------------------- /* This is the core ordering routine. It calls the set dependency consideration functions which then potentialy call this again. Finite - depth is achived through the colouring mechinism. */ -bool pkgOrderList::VisitNode(PkgIterator Pkg) + depth is achieved through the colouring mechinism. */ +bool pkgOrderList::VisitNode(PkgIterator Pkg, char const* from) { - // Looping or irrelevent. + // Looping or irrelevant. // This should probably trancend not installed packages if (Pkg.end() == true || IsFlag(Pkg,Added) == true || IsFlag(Pkg,AddPending) == true || IsFlag(Pkg,InList) == false) @@ -548,7 +577,7 @@ bool pkgOrderList::VisitNode(PkgIterator Pkg) if (Debug == true) { for (int j = 0; j != Depth; j++) clog << ' '; - clog << "Visit " << Pkg.FullName() << endl; + clog << "Visit " << Pkg.FullName() << " from " << from << endl; } Depth++; @@ -622,7 +651,7 @@ bool pkgOrderList::VisitNode(PkgIterator Pkg) Loops are preprocessed and logged. */ bool pkgOrderList::DepUnPackCrit(DepIterator D) { - for (; D.end() == false; D++) + for (; D.end() == false; ++D) { if (D.Reverse() == true) { @@ -643,16 +672,14 @@ bool pkgOrderList::DepUnPackCrit(DepIterator D) if (CheckDep(D) == true) continue; - if (VisitNode(D.ParentPkg()) == false) + if (VisitNode(D.ParentPkg(), "UnPackCrit") == false) return false; } else { /* Forward critical dependencies MUST be correct before the package can be unpacked. */ - if (D->Type != pkgCache::Dep::Conflicts && - D->Type != pkgCache::Dep::DpkgBreaks && - D->Type != pkgCache::Dep::Obsoletes && + if (D.IsNegative() == false && D->Type != pkgCache::Dep::PreDepends) continue; @@ -702,7 +729,7 @@ bool pkgOrderList::DepUnPackPreD(DepIterator D) if (D.Reverse() == true) return DepUnPackCrit(D); - for (; D.end() == false; D++) + for (; D.end() == false; ++D) { if (D.IsCritical() == false) continue; @@ -745,7 +772,7 @@ bool pkgOrderList::DepUnPackPre(DepIterator D) if (D.Reverse() == true) return true; - for (; D.end() == false; D++) + for (; D.end() == false; ++D) { /* Only consider the PreDepends or Depends. Depends are only considered at the lowest depth or in the case of immediate @@ -796,11 +823,11 @@ bool pkgOrderList::DepUnPackPre(DepIterator D) The forwards depends loop is designed to bring the packages dependents close to the package. This helps reduce deconfigure time. - Loops are irrelevent to this. */ + Loops are irrelevant to this. */ bool pkgOrderList::DepUnPackDep(DepIterator D) { - for (; D.end() == false; D++) + for (; D.end() == false; ++D) if (D.IsCritical() == true) { if (D.Reverse() == true) @@ -812,7 +839,7 @@ bool pkgOrderList::DepUnPackDep(DepIterator D) D.ParentPkg().CurrentVer() != D.ParentVer()) continue; - // The dep will not break so it is irrelevent. + // The dep will not break so it is irrelevant. if (CheckDep(D) == true) continue; @@ -820,7 +847,7 @@ bool pkgOrderList::DepUnPackDep(DepIterator D) if (IsMissing(D.ParentPkg()) == true) continue; - if (VisitNode(D.ParentPkg()) == false) + if (VisitNode(D.ParentPkg(), "UnPackDep-Parent") == false) return false; } else @@ -834,7 +861,7 @@ bool pkgOrderList::DepUnPackDep(DepIterator D) if (CheckDep(D) == true) continue; - if (VisitNode(D.TargetPkg()) == false) + if (VisitNode(D.TargetPkg(), "UnPackDep-Target") == false) return false; } } @@ -855,7 +882,7 @@ bool pkgOrderList::DepConfigure(DepIterator D) if (D.Reverse() == true) return true; - for (; D.end() == false; D++) + for (; D.end() == false; ++D) if (D->Type == pkgCache::Dep::Depends) if (VisitProvides(D,false) == false) return false; @@ -864,52 +891,136 @@ bool pkgOrderList::DepConfigure(DepIterator D) /*}}}*/ // OrderList::DepRemove - Removal ordering /*{{{*/ // --------------------------------------------------------------------- -/* Removal visits all reverse depends. It considers if the dependency - of the Now state version to see if it is okay with removing this - package. This check should always fail, but is provided for symetery - with the other critical handlers. - - Loops are preprocessed and logged. Removal loops can also be - detected in the critical handler. They are characterized by an - old version of A depending on B but the new version of A conflicting - with B, thus either A or B must break to install. */ -bool pkgOrderList::DepRemove(DepIterator D) +/* Checks all given dependencies if they are broken by the remove of a + package and if so fix it by visiting another provider or or-group + member to ensure that the dependee keeps working which is especially + important for Immediate packages like e.g. those depending on an + awk implementation. If the dependency can't be fixed with another + package this means an upgrade of the package will solve the problem. */ +bool pkgOrderList::DepRemove(DepIterator Broken) { - if (D.Reverse() == false) + if (Broken.Reverse() == false) return true; - for (; D.end() == false; D++) - if (D->Type == pkgCache::Dep::Depends || D->Type == pkgCache::Dep::PreDepends) + + for (; Broken.end() == false; ++Broken) + { + if (Broken->Type != pkgCache::Dep::Depends && + Broken->Type != pkgCache::Dep::PreDepends) + continue; + + PkgIterator BrokenPkg = Broken.ParentPkg(); + // uninstalled packages can't break via a remove + if (BrokenPkg->CurrentVer == 0) + continue; + + // if its already added, we can't do anything useful + if (IsFlag(BrokenPkg, AddPending) == true || IsFlag(BrokenPkg, Added) == true) + continue; + + // if the dependee is going to be removed, visit it now + if (Cache[BrokenPkg].Delete() == true) + return VisitNode(BrokenPkg, "Remove-Dependee"); + + // The package stays around, so find out how this is possible + for (DepIterator D = BrokenPkg.CurrentVer().DependsList(); D.end() == false;) { - // Duplication elimination, consider the current version only - if (D.ParentPkg().CurrentVer() != D.ParentVer()) + // only important or-groups need fixing + if (D->Type != pkgCache::Dep::Depends && + D->Type != pkgCache::Dep::PreDepends) + { + ++D; continue; + } - /* We wish to see if the dep on the parent package is okay - in the removed (install) state of the target pkg. */ - if (CheckDep(D) == true) + // Start is the beginning of the or-group, D is the first one after or + DepIterator Start = D; + bool foundBroken = false; + for (bool LastOR = true; D.end() == false && LastOR == true; ++D) { - // We want to catch loops with the code below. - if (IsFlag(D.ParentPkg(),AddPending) == false) - continue; + LastOR = (D->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or; + if (D == Broken) + foundBroken = true; } - // This is the loop detection - if (IsFlag(D.ParentPkg(),Added) == true || - IsFlag(D.ParentPkg(),AddPending) == true) - { - if (IsFlag(D.ParentPkg(),AddPending) == true) - AddLoop(D); + // this or-group isn't the broken one: keep searching + if (foundBroken == false) continue; + + // iterate over all members of the or-group searching for a ready replacement + bool readyReplacement = false; + for (DepIterator OrMember = Start; OrMember != D && readyReplacement == false; ++OrMember) + { + Version ** Replacements = OrMember.AllTargets(); + for (Version **R = Replacements; *R != 0; ++R) + { + VerIterator Ver(Cache,*R); + // only currently installed packages can be a replacement + PkgIterator RPkg = Ver.ParentPkg(); + if (RPkg.CurrentVer() != Ver) + continue; + + // packages going to be removed can't be a replacement + if (Cache[RPkg].Delete() == true) + continue; + + readyReplacement = true; + break; + } + delete[] Replacements; } - // Skip over missing files - if (IsMissing(D.ParentPkg()) == true) + // something else is ready to take over, do nothing + if (readyReplacement == true) continue; - - if (VisitNode(D.ParentPkg()) == false) + + // see if we can visit a replacement + bool visitReplacement = false; + for (DepIterator OrMember = Start; OrMember != D && visitReplacement == false; ++OrMember) + { + Version ** Replacements = OrMember.AllTargets(); + for (Version **R = Replacements; *R != 0; ++R) + { + VerIterator Ver(Cache,*R); + // consider only versions we plan to install + PkgIterator RPkg = Ver.ParentPkg(); + if (Cache[RPkg].Install() == false || Cache[RPkg].InstallVer != Ver) + continue; + + // loops are not going to help us, so don't create them + if (IsFlag(RPkg, AddPending) == true) + continue; + + if (IsMissing(RPkg) == true) + continue; + + visitReplacement = true; + if (IsFlag(BrokenPkg, Immediate) == false) + { + if (VisitNode(RPkg, "Remove-Rep") == true) + break; + } + else + { + Flag(RPkg, Immediate); + if (VisitNode(RPkg, "Remove-ImmRep") == true) + break; + } + visitReplacement = false; + } + delete[] Replacements; + } + if (visitReplacement == true) + continue; + + // the broken package in current version can't be fixed, so install new version + if (IsMissing(BrokenPkg) == true) + break; + + if (VisitNode(BrokenPkg, "Remove-Upgrade") == false) return false; } - + } + return true; } /*}}}*/ @@ -933,8 +1044,10 @@ bool pkgOrderList::AddLoop(DepIterator D) Loops[LoopCount++] = D; // Mark the packages as being part of a loop. - Flag(D.TargetPkg(),Loop); - Flag(D.ParentPkg(),Loop); + //Flag(D.TargetPkg(),Loop); + //Flag(D.ParentPkg(),Loop); + /* This is currently disabled because the Loop flag is being used for + loop management in the package manager. Check the orderlist.h file for more info */ return true; } /*}}}*/ @@ -957,9 +1070,9 @@ void pkgOrderList::WipeFlags(unsigned long F) this fails to produce a suitable result. */ bool pkgOrderList::CheckDep(DepIterator D) { - SPtrArray List = D.AllTargets(); + std::unique_ptr List(D.AllTargets()); bool Hit = false; - for (Version **I = List; *I != 0; I++) + for (Version **I = List.get(); *I != 0; I++) { VerIterator Ver(Cache,*I); PkgIterator Pkg = Ver.ParentPkg(); @@ -983,10 +1096,14 @@ bool pkgOrderList::CheckDep(DepIterator D) /* Conflicts requires that all versions are not present, depends just needs one */ - if (D->Type != pkgCache::Dep::Conflicts && - D->Type != pkgCache::Dep::DpkgBreaks && - D->Type != pkgCache::Dep::Obsoletes) + if (D.IsNegative() == false) { + // ignore provides by older versions of this package + if (((D.Reverse() == false && Pkg == D.ParentPkg()) || + (D.Reverse() == true && Pkg == D.TargetPkg())) && + Cache[Pkg].InstallVer != *I) + continue; + /* Try to find something that does not have the after flag set if at all possible */ if (IsFlag(Pkg,After) == true)