X-Git-Url: https://git.saurik.com/apt.git/blobdiff_plain/7296e47e10687e554a4756f65e9c842f88e696e3..fcffe89d8344e699267210badac53ff24dd41148:/apt-pkg/orderlist.cc diff --git a/apt-pkg/orderlist.cc b/apt-pkg/orderlist.cc index 3a179b2a2..d1118e319 100644 --- a/apt-pkg/orderlist.cc +++ b/apt-pkg/orderlist.cc @@ -68,10 +68,12 @@ #include #include #include -#include -#include #include +#include +#include +#include +#include #include /*}}}*/ @@ -82,7 +84,7 @@ 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), @@ -138,9 +140,9 @@ 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); @@ -150,7 +152,7 @@ bool pkgOrderList::DoRun() // Rebuild the main list into the temp list. iterator OldEnd = End; - End = NList; + End = NList.get(); for (iterator I = List; I != OldEnd; ++I) if (VisitNode(PkgIterator(Cache,*I), "DoRun") == false) { @@ -159,12 +161,12 @@ bool pkgOrderList::DoRun() } // 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; } /*}}}*/ @@ -255,7 +257,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; @@ -301,9 +303,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; @@ -331,9 +332,11 @@ int pkgOrderList::Score(PkgIterator Pkg) } // Important Required Standard Optional Extra - signed short PrioMap[] = {0,5,4,3,1,0}; 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; } /*}}}*/ @@ -507,8 +510,8 @@ bool pkgOrderList::VisitRProvides(DepFunc F,VerIterator Ver) 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(); @@ -536,7 +539,7 @@ bool pkgOrderList::VisitProvides(DepIterator D,bool Critical) } if (D.IsNegative() == false) return true; - for (Version **I = List; *I != 0; ++I) + for (Version **I = List.get(); *I != 0; ++I) { VerIterator Ver(Cache,*I); PkgIterator Pkg = Ver.ParentPkg(); @@ -565,10 +568,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. */ + 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) @@ -823,7 +826,7 @@ 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) { @@ -839,7 +842,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; @@ -891,149 +894,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. */ - bool tryFixDeps = false; - 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; } - else - tryFixDeps = 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; } - if (tryFixDeps == true) + // something else is ready to take over, do nothing + if (readyReplacement == true) + continue; + + // see if we can visit a replacement + bool visitReplacement = false; + for (DepIterator OrMember = Start; OrMember != D && visitReplacement == false; ++OrMember) { - for (pkgCache::DepIterator F = D.ParentPkg().CurrentVer().DependsList(); - F.end() == false; ++F) + Version ** Replacements = OrMember.AllTargets(); + for (Version **R = Replacements; *R != 0; ++R) { - if (F->Type != pkgCache::Dep::Depends && F->Type != pkgCache::Dep::PreDepends) + 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; - // Check the Providers - if (F.TargetPkg()->ProvidesList != 0) - { - pkgCache::PrvIterator Prov = F.TargetPkg().ProvidesList(); - for (; Prov.end() == false; ++Prov) - { - pkgCache::PkgIterator const P = Prov.OwnerPkg(); - if (IsFlag(P, InList) == true && - IsFlag(P, AddPending) == true && - IsFlag(P, Added) == false && - Cache[P].InstallVer == 0) - break; - } - if (Prov.end() == false) - for (pkgCache::PrvIterator Prv = F.TargetPkg().ProvidesList(); - Prv.end() == false; ++Prv) - { - pkgCache::PkgIterator const P = Prv.OwnerPkg(); - if (IsFlag(P, InList) == true && - IsFlag(P, AddPending) == false && - Cache[P].InstallVer != 0 && - VisitNode(P, "Remove-P") == true) - { - Flag(P, Immediate); - tryFixDeps = false; - break; - } - } - if (tryFixDeps == false) - break; - } - // Check for Or groups - if ((F->CompareOp & pkgCache::Dep::Or) != pkgCache::Dep::Or) + // loops are not going to help us, so don't create them + if (IsFlag(RPkg, AddPending) == true) continue; - // Lets see if the package is part of the Or group - pkgCache::DepIterator S = F; - for (; S.end() == false; ++S) + + if (IsMissing(RPkg) == true) + continue; + + visitReplacement = true; + if (IsFlag(BrokenPkg, Immediate) == false) { - if (S.TargetPkg() == D.TargetPkg()) + if (VisitNode(RPkg, "Remove-Rep") == true) break; - if ((S->CompareOp & pkgCache::Dep::Or) != pkgCache::Dep::Or || - CheckDep(S)) // Or group is satisfied by another package - for (;S.end() == false; ++S); } - if (S.end() == true) - continue; - // skip to the end of the or group - for (;S.end() == false && (S->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or; ++S); - ++S; - // The soon to be removed is part of the Or group - // start again in the or group and find something which will serve as replacement - for (; F.end() == false && F != S; ++F) + else { - if (IsFlag(F.TargetPkg(), InList) == true && - IsFlag(F.TargetPkg(), AddPending) == false && - Cache[F.TargetPkg()].InstallVer != 0 && - VisitNode(F.TargetPkg(), "Remove-Target") == true) - { - Flag(F.TargetPkg(), Immediate); - tryFixDeps = false; + Flag(RPkg, Immediate); + if (VisitNode(RPkg, "Remove-ImmRep") == true) break; - } - else if (F.TargetPkg()->ProvidesList != 0) - { - pkgCache::PrvIterator Prv = F.TargetPkg().ProvidesList(); - for (; Prv.end() == false; ++Prv) - { - if (IsFlag(Prv.OwnerPkg(), InList) == true && - IsFlag(Prv.OwnerPkg(), AddPending) == false && - Cache[Prv.OwnerPkg()].InstallVer != 0 && - VisitNode(Prv.OwnerPkg(), "Remove-Owner") == true) - { - Flag(Prv.OwnerPkg(), Immediate); - tryFixDeps = false; - break; - } - } - if (Prv.end() == false) - break; - } } - if (tryFixDeps == false) - break; + visitReplacement = false; } + delete[] Replacements; } - - // Skip over missing files - if (IsMissing(D.ParentPkg()) == true) + if (visitReplacement == true) continue; - - if (VisitNode(D.ParentPkg(), "Remove-Parent") == false) + + // 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; } /*}}}*/ @@ -1083,9 +1073,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();