]> git.saurik.com Git - apt.git/blobdiff - apt-pkg/orderlist.cc
- provide a {Package,Version}List similar to {Package,Version}Set
[apt.git] / apt-pkg / orderlist.cc
index ca18f1d7574211a10f14d7ba02d960f499b8a835..0ac9a83e3b14c1971e7dc863022d00279ad2d042 100644 (file)
@@ -63,6 +63,8 @@
    ##################################################################### */
                                                                        /*}}}*/
 // Include Files                                                       /*{{{*/
+#include<config.h>
+
 #include <apt-pkg/orderlist.h>
 #include <apt-pkg/depcache.h>
 #include <apt-pkg/error.h>
@@ -117,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;
 
@@ -126,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 */
@@ -144,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;
@@ -175,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;
 }
                                                                        /*}}}*/
@@ -206,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;
@@ -230,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;
@@ -244,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;
@@ -256,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;
 }
@@ -282,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)
@@ -388,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;
    
@@ -424,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;
    
@@ -433,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
@@ -468,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<Version *> 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;
 }
                                                                        /*}}}*/
@@ -514,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
@@ -525,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++;
@@ -584,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 
@@ -600,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)
       {
@@ -621,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;
                                 
@@ -668,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;
@@ -724,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
@@ -779,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)
@@ -799,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
@@ -813,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;
            }
         }
@@ -834,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;
@@ -856,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
@@ -864,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 || 
@@ -881,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 
@@ -913,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;
 }
                                                                        /*}}}*/
@@ -963,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)