X-Git-Url: https://git.saurik.com/apt.git/blobdiff_plain/408a4726131e9db26ff868623a5d216a26c45a50..f55602cb0cd7403206752479b2ec11c6367e2f6d:/apt-pkg/orderlist.cc?ds=sidebyside diff --git a/apt-pkg/orderlist.cc b/apt-pkg/orderlist.cc index 61d8d914e..0ac9a83e3 100644 --- a/apt-pkg/orderlist.cc +++ b/apt-pkg/orderlist.cc @@ -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. @@ -63,9 +63,8 @@ ##################################################################### */ /*}}}*/ // Include Files /*{{{*/ -#ifdef __GNUG__ -#pragma implementation "apt-pkg/orderlist.h" -#endif +#include + #include #include #include @@ -120,7 +119,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; @@ -129,10 +129,10 @@ bool pkgOrderList::IsMissing(PkgIterator Pkg) if (FileList[Pkg->ID].empty() == false) return false; + return true; } /*}}}*/ - // OrderList::DoRun - Does an order run /*{{{*/ // --------------------------------------------------------------------- /* The caller is expeted to have setup the desired probe state */ @@ -147,14 +147,14 @@ bool pkgOrderList::DoRun() 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) + for (iterator I = List; I != OldEnd; ++I) + if (VisitNode(PkgIterator(Cache,*I), "DoRun") == false) { End = OldEnd; return false; @@ -178,22 +178,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; } /*}}}*/ @@ -209,16 +222,16 @@ bool pkgOrderList::OrderUnpack(string *FileList) if (FileList != 0) { 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) Flag(*I,After); } } - + Primary = &pkgOrderList::DepUnPackCrit; Secondary = &pkgOrderList::DepConfigure; RevDepends = &pkgOrderList::DepUnPackDep; @@ -233,7 +246,7 @@ bool pkgOrderList::OrderUnpack(string *FileList) clog << "** Pass A" << endl; if (DoRun() == false) return false; - + if (Debug == true) clog << "** Pass B" << endl; Secondary = 0; @@ -247,7 +260,7 @@ bool pkgOrderList::OrderUnpack(string *FileList) Remove = 0; // Otherwise the libreadline remove problem occures if (DoRun() == false) return false; - + if (Debug == true) clog << "** Pass D" << endl; LoopCount = 0; @@ -259,13 +272,13 @@ 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) - clog << P.Name() << ' ' << IsMissing(P) << ',' << IsFlag(P,After) << endl; + clog << " " << P.FullName() << ' ' << IsMissing(P) << ',' << IsFlag(P,After) << endl; } - } + } return true; } @@ -285,35 +298,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 += 10; - - for (DepIterator D = Cache[Pkg].InstVerIter(Cache).DependsList(); - D.end() == false; D++) + Score += ScoreImmediate; + + 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) @@ -391,6 +409,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; @@ -427,6 +446,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; @@ -436,7 +456,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 @@ -471,44 +490,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++) + for (Version **I = List; *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, "Provides-1") == false) + return false; + } + if (D.IsNegative() == false) + return true; + for (Version **I = List; *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) == false) + if (VisitNode(Pkg, "Provides-2") == false) return false; } + return true; } /*}}}*/ @@ -517,7 +568,7 @@ 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) +bool pkgOrderList::VisitNode(PkgIterator Pkg, char const* from) { // Looping or irrelevent. // This should probably trancend not installed packages @@ -528,7 +579,7 @@ bool pkgOrderList::VisitNode(PkgIterator Pkg) if (Debug == true) { for (int j = 0; j != Depth; j++) clog << ' '; - clog << "Visit " << Pkg.Name() << endl; + clog << "Visit " << Pkg.FullName() << " from " << from << endl; } Depth++; @@ -587,13 +638,12 @@ bool pkgOrderList::VisitNode(PkgIterator Pkg) if (Debug == true) { for (int j = 0; j != Depth; j++) clog << ' '; - clog << "Leave " << Pkg.Name() << ' ' << IsFlag(Pkg,Added) << ',' << IsFlag(Pkg,AddPending) << endl; + 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 @@ -603,7 +653,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) { @@ -624,16 +674,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; @@ -671,20 +719,19 @@ bool pkgOrderList::DepUnPackCrit(DepIterator D) } return true; } - + /*}}}*/ // OrderList::DepUnPackPreD - Critical UnPacking ordering with depends /*{{{*/ // --------------------------------------------------------------------- /* 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) { if (D.Reverse() == true) return DepUnPackCrit(D); - for (; D.end() == false; D++) + for (; D.end() == false; ++D) { if (D.IsCritical() == false) continue; @@ -727,7 +774,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 @@ -782,7 +829,7 @@ bool pkgOrderList::DepUnPackPre(DepIterator D) bool pkgOrderList::DepUnPackDep(DepIterator D) { - for (; D.end() == false; D++) + for (; D.end() == false; ++D) if (D.IsCritical() == true) { if (D.Reverse() == true) @@ -802,7 +849,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 @@ -816,7 +863,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; } } @@ -837,7 +884,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; @@ -859,7 +906,7 @@ bool pkgOrderList::DepRemove(DepIterator D) { if (D.Reverse() == false) return true; - for (; D.end() == false; D++) + for (; D.end() == false; ++D) if (D->Type == pkgCache::Dep::Depends || D->Type == pkgCache::Dep::PreDepends) { // Duplication elimination, consider the current version only @@ -867,13 +914,16 @@ bool pkgOrderList::DepRemove(DepIterator D) continue; /* We wish to see if the dep on the parent package is okay - in the removed (install) state of the target pkg. */ + in the removed (install) state of the target pkg. */ + bool tryFixDeps = false; if (CheckDep(D) == true) { // We want to catch loops with the code below. if (IsFlag(D.ParentPkg(),AddPending) == false) continue; } + else + tryFixDeps = true; // This is the loop detection if (IsFlag(D.ParentPkg(),Added) == true || @@ -884,18 +934,111 @@ bool pkgOrderList::DepRemove(DepIterator D) continue; } + if (tryFixDeps == true) + { + for (pkgCache::DepIterator F = D.ParentPkg().CurrentVer().DependsList(); + F.end() == false; ++F) + { + if (F->Type != pkgCache::Dep::Depends && F->Type != pkgCache::Dep::PreDepends) + 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) + continue; + // Lets see if the package is part of the Or group + pkgCache::DepIterator S = F; + for (; S.end() == false; ++S) + { + if (S.TargetPkg() == D.TargetPkg()) + 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) + { + 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; + 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; + } + } + // Skip over missing files if (IsMissing(D.ParentPkg()) == true) continue; - if (VisitNode(D.ParentPkg()) == false) + if (VisitNode(D.ParentPkg(), "Remove-Parent") == false) return false; } return true; } /*}}}*/ - // OrderList::AddLoop - Add a loop to the loop list /*{{{*/ // --------------------------------------------------------------------- /* We record the loops. This is a relic since loop breaking is done @@ -916,8 +1059,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; } /*}}}*/ @@ -966,10 +1111,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)