X-Git-Url: https://git.saurik.com/apt.git/blobdiff_plain/15657fcc72462aed8e5b361fe52450484229ec5d..bccb344412a0e97afdf0aaaf41a31124c84f6eaa:/apt-pkg/orderlist.cc

diff --git a/apt-pkg/orderlist.cc b/apt-pkg/orderlist.cc
index 19661fc2d..bfdc50e6c 100644
--- a/apt-pkg/orderlist.cc
+++ b/apt-pkg/orderlist.cc
@@ -63,33 +63,34 @@
    ##################################################################### */
 									/*}}}*/
 // Include Files							/*{{{*/
+#include<config.h>
+
 #include <apt-pkg/orderlist.h>
 #include <apt-pkg/depcache.h>
 #include <apt-pkg/error.h>
-#include <apt-pkg/version.h>
-#include <apt-pkg/sptr.h>
 #include <apt-pkg/configuration.h>
+#include <apt-pkg/cacheiterators.h>
+#include <apt-pkg/pkgcache.h>
 
+#include <stdlib.h>
+#include <string.h>
+#include <algorithm>
 #include <iostream>
 									/*}}}*/
 
 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;
@@ -138,33 +139,33 @@ bool pkgOrderList::DoRun()
 {   
    // Temp list
    unsigned long Size = Cache.Head().PackageCount;
-   SPtrArray<Package *> NList = new Package *[Size];
-   SPtrArray<Package *> AfterList = new Package *[Size];
-   AfterEnd = AfterList;
+   std::unique_ptr<Package *[]> NList(new Package *[Size]);
+   std::unique_ptr<Package *[]> 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;
 }
 									/*}}}*/
@@ -184,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;
@@ -197,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)
@@ -222,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)
@@ -237,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;
@@ -255,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;
 
@@ -270,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)
@@ -301,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;
 
@@ -323,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;
 }
 									/*}}}*/
@@ -379,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;
    }*/
    
@@ -405,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;
@@ -421,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)
@@ -434,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)
@@ -442,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;
@@ -488,40 +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 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++)
+{
+   std::unique_ptr<Version *[]> 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.IsNegative() == false &&
 	  Cache[Pkg].InstallVer != *I)
 	 continue;
-      
+
       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;
 }
 									/*}}}*/
@@ -529,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)
@@ -541,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++;
@@ -615,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)
       {
@@ -636,7 +672,7 @@ bool pkgOrderList::DepUnPackCrit(DepIterator D)
 	 if (CheckDep(D) == true)
 	    continue;
 
-	 if (VisitNode(D.ParentPkg()) == false)
+	 if (VisitNode(D.ParentPkg(), "UnPackCrit") == false)
 	    return false;
       }
       else
@@ -693,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;
@@ -736,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
@@ -787,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)
@@ -803,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;
 	    
@@ -811,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
@@ -825,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;
 	    }
 	 }
@@ -846,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;
@@ -855,149 +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. */
-	 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) == 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()) == 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()) == 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()) == 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;
 }
 									/*}}}*/
@@ -1021,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;
 }
 									/*}}}*/
@@ -1045,9 +1070,9 @@ void pkgOrderList::WipeFlags(unsigned long F)
    this fails to produce a suitable result. */
 bool pkgOrderList::CheckDep(DepIterator D)
 {
-   SPtrArray<Version *> List = D.AllTargets();
+   std::unique_ptr<Version *[]> 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();
@@ -1073,7 +1098,7 @@ bool pkgOrderList::CheckDep(DepIterator D)
          just needs one */
       if (D.IsNegative() == false)
       {
-	 // ignore provides by older versions of this package
+      	 // 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)