Fixed or handling bug

[apt.git] / apt-pkg / algorithms.cc

diff --git a/apt-pkg/algorithms.cc b/apt-pkg/algorithms.cc
index 21db989419d4b91a72dbeec97f7e7649494ab3d7..7f7cb204faaaff8527d8bbbf5a6a5e115863b3bf 100644 (file)
--- a/apt-pkg/algorithms.cc
+++ b/apt-pkg/algorithms.cc
@@ -1,6 +1,6 @@
 // -*- mode: cpp; mode: fold -*-
 // Description                                                         /*{{{*/
 // -*- mode: cpp; mode: fold -*-
 // Description                                                         /*{{{*/

-// $Id: algorithms.cc,v 1.20 1999/07/03 03:10:35 jgg Exp $
+// $Id: algorithms.cc,v 1.31 2000/10/03 23:59:05 jgg Exp $

 /* ######################################################################
 
    Algorithms - A set of misc algorithms
 /* ######################################################################
 
    Algorithms - A set of misc algorithms


@@ -36,7 +36,7 @@ pkgSimulate::pkgSimulate(pkgDepCache &Cache) : pkgPackageManager(Cache),
 
    // Fake a filename so as not to activate the media swapping
    string Jnk = "SIMULATE";
 
    // Fake a filename so as not to activate the media swapping
    string Jnk = "SIMULATE";

-   for (int I = 0; I != Cache.Head().PackageCount; I++)
+   for (unsigned int I = 0; I != Cache.Head().PackageCount; I++)

       FileNames[I] = Jnk;
 }
                                                                        /*}}}*/
       FileNames[I] = Jnk;
 }
                                                                        /*}}}*/


@@ -125,14 +125,17 @@ bool pkgSimulate::Configure(PkgIterator iPkg)
 // Simulate::Remove - Simulate the removal of a package                        /*{{{*/
 // ---------------------------------------------------------------------
 /* */
 // Simulate::Remove - Simulate the removal of a package                        /*{{{*/
 // ---------------------------------------------------------------------
 /* */

-bool pkgSimulate::Remove(PkgIterator iPkg)
+bool pkgSimulate::Remove(PkgIterator iPkg,bool Purge)

 {
    // Adapt the iterator
    PkgIterator Pkg = Sim.FindPkg(iPkg.Name());
 
    Flags[Pkg->ID] = 3;
    Sim.MarkDelete(Pkg);
 {
    // Adapt the iterator
    PkgIterator Pkg = Sim.FindPkg(iPkg.Name());
 
    Flags[Pkg->ID] = 3;
    Sim.MarkDelete(Pkg);

-   cout << "Remv " << Pkg.Name();
+   if (Purge == true)
+      cout << "Purg " << Pkg.Name();
+   else
+      cout << "Remv " << Pkg.Name();

 
    if (Sim.BrokenCount() != 0)
       ShortBreaks();
 
    if (Sim.BrokenCount() != 0)
       ShortBreaks();


@@ -281,7 +284,7 @@ bool pkgDistUpgrade(pkgDepCache &Cache)
    pkgProblemResolver Fix(Cache);
 
    // Hold back held packages.
    pkgProblemResolver Fix(Cache);
 
    // Hold back held packages.

-   if (_config->FindB("APT::Ingore-Hold",false) == false)
+   if (_config->FindB("APT::Ignore-Hold",false) == false)

    {
       for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
       {
    {
       for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
       {


@@ -337,6 +340,7 @@ bool pkgMinimizeUpgrade(pkgDepCache &Cache)
    
    // We loop indefinately to get the minimal set size.
    bool Change = false;
    
    // We loop indefinately to get the minimal set size.
    bool Change = false;

+   unsigned int Count = 0;

    do
    {
       Change = false;
    do
    {
       Change = false;


@@ -345,16 +349,21 @@ bool pkgMinimizeUpgrade(pkgDepCache &Cache)
         // Not interesting
         if (Cache[I].Upgrade() == false || Cache[I].NewInstall() == true)
            continue;
         // Not interesting
         if (Cache[I].Upgrade() == false || Cache[I].NewInstall() == true)
            continue;

-        
+

         // Keep it and see if that is OK
         Cache.MarkKeep(I);
         if (Cache.BrokenCount() != 0)
            Cache.MarkInstall(I,false);
         else
         // Keep it and see if that is OK
         Cache.MarkKeep(I);
         if (Cache.BrokenCount() != 0)
            Cache.MarkInstall(I,false);
         else

-           Change = true;
+        {
+           // If keep didnt actually do anything then there was no change..
+           if (Cache[I].Upgrade() == false)
+              Change = true;
+        }       

       }      
       }      

+      Count++;

    }
    }

-   while (Change == true);
+   while (Change == true && Count < 10);

 
    if (Cache.BrokenCount() != 0)
       return _error->Error("Internal Error in pkgMinimizeUpgrade");
 
    if (Cache.BrokenCount() != 0)
       return _error->Error("Internal Error in pkgMinimizeUpgrade");


@@ -515,10 +524,11 @@ bool pkgProblemResolver::DoUpgrade(pkgCache::PkgIterator Pkg)
       pkgCache::DepIterator Start = D;
       pkgCache::DepIterator End = D;
       unsigned char State = 0;
       pkgCache::DepIterator Start = D;
       pkgCache::DepIterator End = D;
       unsigned char State = 0;

-      for (bool LastOR = true; D.end() == false && LastOR == true; D++)
+      for (bool LastOR = true; D.end() == false && LastOR == true;)

       {
         State |= Cache[D];
         LastOR = (D->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or;
       {
         State |= Cache[D];
         LastOR = (D->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or;

+        D++;

         if (LastOR == true)
            End = D;
       }
         if (LastOR == true)
            End = D;
       }


@@ -526,52 +536,58 @@ bool pkgProblemResolver::DoUpgrade(pkgCache::PkgIterator Pkg)
       // We only worry about critical deps.
       if (End.IsCritical() != true)
         continue;
       // We only worry about critical deps.
       if (End.IsCritical() != true)
         continue;

-      
-      // Dep is ok
-      if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
-        continue;
-      
-      // Hm, the group is broken.. I have no idea how to handle this
-      if (Start != End)
+            
+      // Iterate over all the members in the or group
+      while (1)

       {
       {

-        clog << "Note, a broken or group was found in " << Pkg.Name() << "." << endl;
-        Fail = true;
-        break;
-      }
-
-      // Do not change protected packages
-      PkgIterator P = Start.SmartTargetPkg();
-      if ((Flags[P->ID] & Protected) == Protected)
-      {
-        if (Debug == true)
-           clog << "    Reinet Failed because of protected " << P.Name() << endl;
-        Fail = true;
-        break;
-      }      
-      
-      // Upgrade the package if the candidate version will fix the problem.
-      if ((Cache[Start] & pkgDepCache::DepCVer) == pkgDepCache::DepCVer)
-      {
-        if (DoUpgrade(P) == false)
+        // Dep is ok now
+        if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
+           break;
+        
+        // Do not change protected packages
+        PkgIterator P = Start.SmartTargetPkg();
+        if ((Flags[P->ID] & Protected) == Protected)

         {
            if (Debug == true)
         {
            if (Debug == true)

-              clog << "    Reinst Failed because of " << P.Name() << endl;
+              clog << "    Reinst Failed because of protected " << P.Name() << endl;

            Fail = true;
            Fail = true;

+        }      
+        else
+        {
+           // Upgrade the package if the candidate version will fix the problem.
+           if ((Cache[Start] & pkgDepCache::DepCVer) == pkgDepCache::DepCVer)
+           {
+              if (DoUpgrade(P) == false)
+              {
+                 if (Debug == true)
+                    clog << "    Reinst Failed because of " << P.Name() << endl;
+                 Fail = true;
+              }
+              else
+              {
+                 Fail = false;
+                 break;
+              }            
+           }
+           else
+           {
+              /* We let the algorithm deal with conflicts on its next iteration,
+               it is much smarter than us */
+              if (Start->Type == pkgCache::Dep::Conflicts)
+                 break;
+              
+              if (Debug == true)
+                 clog << "    Reinst Failed early because of " << Start.TargetPkg().Name() << endl;
+              Fail = true;
+           }     
+        }
+        
+        if (Start == End)

            break;
            break;

-        }       
+        Start++;

       }
       }

-      else
-      {
-        /* We let the algorithm deal with conflicts on its next iteration,
-           it is much smarter than us */
-        if (End->Type == pkgCache::Dep::Conflicts)
-           continue;
-        
-        if (Debug == true)
-           clog << "    Reinst Failed early because of " << Start.TargetPkg().Name() << endl;
-        Fail = true;
+      if (Fail == true)

         break;
         break;

-      }      

    }
    
    // Undo our operations - it might be smart to undo everything this did..
    }
    
    // Undo our operations - it might be smart to undo everything this did..


@@ -703,47 +719,84 @@ bool pkgProblemResolver::Resolve(bool BrokenFix)
         if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false)
            continue;
         
         if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false)
            continue;
         

+        if (Debug == true)
+           cout << "Investigating " << I.Name() << endl;
+        

         // Isolate the problem dependency
         PackageKill KillList[100];
         PackageKill *LEnd = KillList;
         // Isolate the problem dependency
         PackageKill KillList[100];
         PackageKill *LEnd = KillList;

-        for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false;)
+        bool InOr = false;
+        pkgCache::DepIterator Start;
+        pkgCache::DepIterator End;
+        PackageKill *OldEnd;
+        
+        enum {OrRemove,OrKeep} OrOp = OrRemove;
+        for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList();
+             D.end() == false || InOr == true;)

         {
         {

-           // Compute a single dependency element (glob or)
-           pkgCache::DepIterator Start;
-           pkgCache::DepIterator End;
-           D.GlobOr(Start,End);
-           

            // We only worry about critical deps.
            // We only worry about critical deps.

-           if (End.IsCritical() != true)
+           if (D.IsCritical() != true)
+           {
+              D++;

               continue;
               continue;

+           }
+           
+           // Compute a single dependency element (glob or)
+           if (Start == End)
+           {
+              // Decide what to do
+              if (InOr == true)
+              {
+                 if (OldEnd == LEnd && OrOp == OrRemove)
+                 {
+                    if ((Flags[I->ID] & Protected) != Protected)
+                    {
+                       if (Debug == true)
+                          clog << "  Or group remove for " << I.Name() << endl;
+                       Cache.MarkDelete(I);
+                    }               
+                 }               
+                 if (OldEnd == LEnd && OrOp == OrKeep)
+                 {
+                    if (Debug == true)
+                       clog << "  Or group keep for " << I.Name() << endl;
+                    Cache.MarkKeep(I);
+                 }               
+              }
+              
+              OrOp = OrRemove;
+              D.GlobOr(Start,End);
+              InOr = Start != End;
+              cout << Start.TargetPkg().Name() << ',' << End.TargetPkg().Name() << ',' << InOr << endl;
+              OldEnd = LEnd;
+           }       
+           else
+              Start++;

            
            // Dep is ok
            if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
               continue;
            
            // Dep is ok
            if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
               continue;

-           
-           // Hm, the group is broken.. I have no idea how to handle this
-           if (Start != End)
-           {
-              if (Debug == true)
-                 clog << "Note, a broken or group was found in " << I.Name() << "." << endl;
-              if ((Flags[I->ID] & Protected) != Protected)
-                 Cache.MarkDelete(I);
-              break;
-           }

                    
            if (Debug == true)
                    
            if (Debug == true)

-              clog << "Package " << I.Name() << " has broken dep on " << End.TargetPkg().Name() << endl;
+              clog << "Package " << I.Name() << " has broken dep on " << Start.TargetPkg().Name() << endl;

 
            /* Look across the version list. If there are no possible
               targets then we keep the package and bail. This is necessary
               if a package has a dep on another package that cant be found */
 
            /* Look across the version list. If there are no possible
               targets then we keep the package and bail. This is necessary
               if a package has a dep on another package that cant be found */

-           pkgCache::Version **VList = End.AllTargets();
+           pkgCache::Version **VList = Start.AllTargets();

            if (*VList == 0 && (Flags[I->ID] & Protected) != Protected &&
            if (*VList == 0 && (Flags[I->ID] & Protected) != Protected &&

-               End->Type != pkgCache::Dep::Conflicts && 
+               Start->Type != pkgCache::Dep::Conflicts &&

                Cache[I].NowBroken() == false)
                Cache[I].NowBroken() == false)

-           {
+           {          
+              if (InOr == true)
+              {
+                 /* No keep choice because the keep being OK could be the
+                    result of another element in the OR group! */
+                 continue;
+              }
+              

               Change = true;
               Change = true;

-              Cache.MarkKeep(I);
+              Cache.MarkKeep(I);                 

               break;
            }
            
               break;
            }
            


@@ -754,37 +807,54 @@ bool pkgProblemResolver::Resolve(bool BrokenFix)
               pkgCache::PkgIterator Pkg = Ver.ParentPkg();
            
               if (Debug == true)
               pkgCache::PkgIterator Pkg = Ver.ParentPkg();
            
               if (Debug == true)

-                 clog << "  Considering " << Pkg.Name() << ' ' << (int)Scores[Pkg->ID] << 
+                 clog << "  Considering " << Pkg.Name() << ' ' << (int)Scores[Pkg->ID] <<

                  " as a solution to " << I.Name() << ' ' << (int)Scores[I->ID] << endl;
               if (Scores[I->ID] <= Scores[Pkg->ID] ||
                  " as a solution to " << I.Name() << ' ' << (int)Scores[I->ID] << endl;
               if (Scores[I->ID] <= Scores[Pkg->ID] ||

-                  ((Cache[End] & pkgDepCache::DepGNow) == 0 &&
+                  ((Cache[Start] & pkgDepCache::DepNow) == 0 &&

                    End->Type != pkgCache::Dep::Conflicts))
               {
                  // Try a little harder to fix protected packages..
                  if ((Flags[I->ID] & Protected) == Protected)
                  {
                     if (DoUpgrade(Pkg) == true)
                    End->Type != pkgCache::Dep::Conflicts))
               {
                  // Try a little harder to fix protected packages..
                  if ((Flags[I->ID] & Protected) == Protected)
                  {
                     if (DoUpgrade(Pkg) == true)

+                    {

                        Scores[Pkg->ID] = Scores[I->ID];
                        Scores[Pkg->ID] = Scores[I->ID];

+                       break;
+                    }
+                    

                     continue;
                  }
                  
                  /* See if a keep will do, unless the package is protected,
                     continue;
                  }
                  
                  /* See if a keep will do, unless the package is protected,

-                    then installing it will be necessary */    
+                    then installing it will be necessary */
+                 bool Installed = Cache[I].Install();

                  Cache.MarkKeep(I);
                  if (Cache[I].InstBroken() == false)
                  {
                  Cache.MarkKeep(I);
                  if (Cache[I].InstBroken() == false)
                  {

+                    // Unwind operation will be keep now
+                    if (OrOp == OrRemove)
+                       OrOp = OrKeep;
+                    
+                    // Restore
+                    if (InOr == true && Installed == true)
+                       Cache.MarkInstall(I,false);
+                    

                     if (Debug == true)
                     if (Debug == true)

-                       clog << "  Holding Back " << I.Name() << " rather than change " << End.TargetPkg().Name() << endl;
+                       clog << "  Holding Back " << I.Name() << " rather than change " << Start.TargetPkg().Name() << endl;

                  }               
                  else
                  }               
                  else

-                 {
+                 {                  

                     if (BrokenFix == false || DoUpgrade(I) == false)
                     {
                     if (BrokenFix == false || DoUpgrade(I) == false)
                     {

-                       if (Debug == true)
-                          clog << "  Removing " << I.Name() << " rather than change " << End.TargetPkg().Name() << endl;
-                       Cache.MarkDelete(I);
-                       if (Counter > 1)
-                          Scores[I->ID] = Scores[Pkg->ID];
+                       // Consider other options
+                       if (InOr == false)
+                       {
+                          if (Debug == true)
+                             clog << "  Removing " << I.Name() << " rather than change " << Start.TargetPkg().Name() << endl;
+                          Cache.MarkDelete(I);
+                          if (Counter > 1)
+                             Scores[I->ID] = Scores[Pkg->ID];
+                       }                       

                     }
                  }
                                  
                     }
                  }
                                  


@@ -794,7 +864,9 @@ bool pkgProblemResolver::Resolve(bool BrokenFix)
               }
               else
               {
               }
               else
               {

-                 // Skip this if it is protected
+                 if (Debug == true)
+                    clog << "  Added " << Pkg.Name() << " to the remove list" << endl;
+                 // Skip adding to the kill list if it is protected

                  if ((Flags[Pkg->ID] & Protected) != 0)
                     continue;
                  
                  if ((Flags[Pkg->ID] & Protected) != 0)
                     continue;
                  


@@ -802,26 +874,36 @@ bool pkgProblemResolver::Resolve(bool BrokenFix)
                  LEnd->Dep = End;
                  LEnd++;
                  
                  LEnd->Dep = End;
                  LEnd++;
                  

-                 if (End->Type != pkgCache::Dep::Conflicts)
+                 if (Start->Type != pkgCache::Dep::Conflicts)

                     break;
               }
            }
 
            // Hm, nothing can possibly satisify this dep. Nuke it.
                     break;
               }
            }
 
            // Hm, nothing can possibly satisify this dep. Nuke it.

-           if (VList[0] == 0 && End->Type != pkgCache::Dep::Conflicts &&
+           if (VList[0] == 0 && Start->Type != pkgCache::Dep::Conflicts &&

                (Flags[I->ID] & Protected) != Protected)
            {
                (Flags[I->ID] & Protected) != Protected)
            {

+              bool Installed = Cache[I].Install();

               Cache.MarkKeep(I);
               if (Cache[I].InstBroken() == false)
               {
               Cache.MarkKeep(I);
               if (Cache[I].InstBroken() == false)
               {

+                 // Unwind operation will be keep now
+                 if (OrOp == OrRemove)
+                    OrOp = OrKeep;
+                 
+                 // Restore
+                 if (InOr == true && Installed == true)
+                    Cache.MarkInstall(I,false);
+                 

                  if (Debug == true)
                  if (Debug == true)

-                    clog << "  Holding Back " << I.Name() << " because I can't find " << End.TargetPkg().Name() << endl;
+                    clog << "  Holding Back " << I.Name() << " because I can't find " << Start.TargetPkg().Name() << endl;

               }               
               else
               {
                  if (Debug == true)
               }               
               else
               {
                  if (Debug == true)

-                    clog << "  Removing " << I.Name() << " because I can't find " << End.TargetPkg().Name() << endl;
-                 Cache.MarkDelete(I);
+                    clog << "  Removing " << I.Name() << " because I can't find " << Start.TargetPkg().Name() << endl;
+                 if (InOr == false)
+                    Cache.MarkDelete(I);

               }
 
               Change = true;
               }
 
               Change = true;


@@ -829,35 +911,42 @@ bool pkgProblemResolver::Resolve(bool BrokenFix)
            }
            
            delete [] VList;
            }
            
            delete [] VList;

+           
+           // Try some more
+           if (InOr == true)
+              continue;
+           

            if (Done == true)
               break;
         }
         
         // Apply the kill list now
         if (Cache[I].InstallVer != 0)
            if (Done == true)
               break;
         }
         
         // Apply the kill list now
         if (Cache[I].InstallVer != 0)

+        {

            for (PackageKill *J = KillList; J != LEnd; J++)
            for (PackageKill *J = KillList; J != LEnd; J++)

-         {
-           Change = true;
-           if ((Cache[J->Dep] & pkgDepCache::DepGNow) == 0)

            {
            {

-              if (J->Dep->Type == pkgCache::Dep::Conflicts)
+              Change = true;
+              if ((Cache[J->Dep] & pkgDepCache::DepGNow) == 0)
+              {
+                 if (J->Dep->Type == pkgCache::Dep::Conflicts)
+                 {
+                    if (Debug == true)
+                       clog << "  Fixing " << I.Name() << " via remove of " << J->Pkg.Name() << endl;
+                    Cache.MarkDelete(J->Pkg);
+                 }
+              }
+              else

               {
                  if (Debug == true)
               {
                  if (Debug == true)

-                    clog << "  Fixing " << I.Name() << " via remove of " << J->Pkg.Name() << endl;
-                 Cache.MarkDelete(J->Pkg);
+                    clog << "  Fixing " << I.Name() << " via keep of " << J->Pkg.Name() << endl;
+                 Cache.MarkKeep(J->Pkg);

               }
               }

-           }
-           else
-           {
-              if (Debug == true)
-                 clog << "  Fixing " << I.Name() << " via keep of " << J->Pkg.Name() << endl;
-              Cache.MarkKeep(J->Pkg);
-           }
-           
-           if (Counter > 1)
-              Scores[J->Pkg->ID] = Scores[I->ID];
-        }      
-      }
+              
+              if (Counter > 1)
+                 Scores[J->Pkg->ID] = Scores[I->ID];
+           }      
+        }
+      }      

    }
 
    if (Debug == true)
    }
 
    if (Debug == true)