apt-pkg/algorithms.cc

   1 // -*- mode: cpp; mode: fold -*-
   2 // Description                                                          /*{{{*/
   3 // $Id: algorithms.cc,v 1.12 1998/11/23 07:02:58 jgg Exp $
   4 /* ######################################################################
   5
   6    Algorithms - A set of misc algorithms
   7
   8    The pkgProblemResolver class has become insanely complex and
   9    very sophisticated, it handles every test case I have thrown at it
  10    to my satisfaction. Understanding exactly why all the steps the class
  11    does are required is difficult and changing though not very risky
  12    may result in other cases not working.
  13
  14    ##################################################################### */
  15                                                                         /*}}}*/
  16 // Include Files                                                        /*{{{*/
  17 #ifdef __GNUG__
  18 #pragma implementation "apt-pkg/algorithms.h"
  19 #endif
  20 #include <apt-pkg/algorithms.h>
  21 #include <apt-pkg/error.h>
  22 #include <apt-pkg/configuration.h>
  23 #include <iostream.h>
  24                                                                         /*}}}*/
  25
  26 pkgProblemResolver *pkgProblemResolver::This = 0;
  27
  28 // Simulate::Simulate - Constructor                                     /*{{{*/
  29 // ---------------------------------------------------------------------
  30 /* */
  31 pkgSimulate::pkgSimulate(pkgDepCache &Cache) : pkgPackageManager(Cache),
  32                             Sim(Cache)
  33 {
  34    Flags = new unsigned char[Cache.HeaderP->PackageCount];
  35    memset(Flags,0,sizeof(*Flags)*Cache.HeaderP->PackageCount);
  36 }
  37                                                                         /*}}}*/
  38 // Simulate::Install - Simulate unpacking of a package                  /*{{{*/
  39 // ---------------------------------------------------------------------
  40 /* */
  41 bool pkgSimulate::Install(PkgIterator iPkg,string /*File*/)
  42 {
  43    // Adapt the iterator
  44    PkgIterator Pkg = Sim.FindPkg(iPkg.Name());
  45    Flags[Pkg->ID] = 1;
  46
  47    clog << "Inst " << Pkg.Name();
  48    Sim.MarkInstall(Pkg,false);
  49
  50    // Look for broken conflicts+predepends.
  51    for (PkgIterator I = Sim.PkgBegin(); I.end() == false; I++)
  52    {
  53       if (Sim[I].InstallVer == 0)
  54          continue;
  55
  56       for (DepIterator D = Sim[I].InstVerIter(Sim).DependsList(); D.end() == false; D++)
  57          if (D->Type == pkgCache::Dep::Conflicts || D->Type == pkgCache::Dep::PreDepends)
  58          {
  59             if ((Sim[D] & pkgDepCache::DepInstall) == 0)
  60             {
  61                clog << " [" << I.Name() << " on " << D.TargetPkg().Name() << ']';
  62                if (D->Type == pkgCache::Dep::Conflicts)
  63                   _error->Error("Fatal, conflicts violated %s",I.Name());
  64             }
  65          }
  66    }
  67
  68    if (Sim.BrokenCount() != 0)
  69       ShortBreaks();
  70    else
  71       clog << endl;
  72    return true;
  73 }
  74                                                                         /*}}}*/
  75 // Simulate::Configure - Simulate configuration of a Package            /*{{{*/
  76 // ---------------------------------------------------------------------
  77 /* This is not an acurate simulation of relatity, we should really not
  78    install the package.. For some investigations it may be necessary
  79    however. */
  80 bool pkgSimulate::Configure(PkgIterator iPkg)
  81 {
  82    // Adapt the iterator
  83    PkgIterator Pkg = Sim.FindPkg(iPkg.Name());
  84
  85    Flags[Pkg->ID] = 2;
  86 //   Sim.MarkInstall(Pkg,false);
  87    if (Sim[Pkg].InstBroken() == true)
  88    {
  89       clog << "Conf " << Pkg.Name() << " broken" << endl;
  90
  91       Sim.Update();
  92
  93       // Print out each package and the failed dependencies
  94       for (pkgCache::DepIterator D = Sim[Pkg].InstVerIter(Sim).DependsList(); D.end() == false; D++)
  95       {
  96          if (Sim.IsImportantDep(D) == false ||
  97              (Sim[D] & pkgDepCache::DepInstall) != 0)
  98             continue;
  99
 100          if (D->Type == pkgCache::Dep::Conflicts)
 101             clog << " Conflicts:" << D.TargetPkg().Name();
 102          else
 103             clog << " Depends:" << D.TargetPkg().Name();
 104       }
 105       clog << endl;
 106
 107       _error->Error("Conf Broken %s",Pkg.Name());
 108    }
 109    else
 110       clog << "Conf " <<  Pkg.Name();
 111
 112    if (Sim.BrokenCount() != 0)
 113       ShortBreaks();
 114    else
 115       clog << endl;
 116
 117    return true;
 118 }
 119                                                                         /*}}}*/
 120 // Simulate::Remove - Simulate the removal of a package                 /*{{{*/
 121 // ---------------------------------------------------------------------
 122 /* */
 123 bool pkgSimulate::Remove(PkgIterator iPkg)
 124 {
 125    // Adapt the iterator
 126    PkgIterator Pkg = Sim.FindPkg(iPkg.Name());
 127
 128    Flags[Pkg->ID] = 3;
 129    Sim.MarkDelete(Pkg);
 130    clog << "Remv " << Pkg.Name();
 131
 132    if (Sim.BrokenCount() != 0)
 133       ShortBreaks();
 134    else
 135       clog << endl;
 136
 137    return true;
 138 }
 139                                                                         /*}}}*/
 140 // Simulate::ShortBreaks - Print out a short line describing all breaks /*{{{*/
 141 // ---------------------------------------------------------------------
 142 /* */
 143 void pkgSimulate::ShortBreaks()
 144 {
 145    clog << " [";
 146    for (PkgIterator I = Sim.PkgBegin(); I.end() == false; I++)
 147    {
 148       if (Sim[I].InstBroken() == true)
 149       {
 150          if (Flags[I->ID] == 0)
 151             clog << I.Name() << ' ';
 152 /*       else
 153             clog << I.Name() << "! ";*/
 154       }
 155    }
 156    clog << ']' << endl;
 157 }
 158                                                                         /*}}}*/
 159 // ApplyStatus - Adjust for non-ok packages                             /*{{{*/
 160 // ---------------------------------------------------------------------
 161 /* We attempt to change the state of the all packages that have failed
 162    installation toward their real state. The ordering code will perform
 163    the necessary calculations to deal with the problems. */
 164 bool pkgApplyStatus(pkgDepCache &Cache)
 165 {
 166    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 167    {
 168       // Only choice for a ReInstReq package is to reinstall
 169       if (I->InstState == pkgCache::State::ReInstReq ||
 170           I->InstState == pkgCache::State::HoldReInstReq)
 171       {
 172          Cache.MarkKeep(I);
 173          continue;
 174       }
 175
 176       switch (I->CurrentState)
 177       {
 178          // This means installation failed somehow
 179          case pkgCache::State::UnPacked:
 180          case pkgCache::State::HalfConfigured:
 181          Cache.MarkKeep(I);
 182          break;
 183
 184          // This means removal failed
 185          case pkgCache::State::HalfInstalled:
 186          Cache.MarkDelete(I);
 187          break;
 188
 189          default:
 190          if (I->InstState != pkgCache::State::Ok)
 191             return _error->Error("The package %s is not ok and I "
 192                                  "don't know how to fix it!",I.Name());
 193       }
 194    }
 195    return true;
 196 }
 197                                                                         /*}}}*/
 198 // FixBroken - Fix broken packages                                      /*{{{*/
 199 // ---------------------------------------------------------------------
 200 /* This autoinstalls every broken package and then runs the problem resolver
 201    on the result. */
 202 bool pkgFixBroken(pkgDepCache &Cache)
 203 {
 204    // Auto upgrade all broken packages
 205    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 206       if (Cache[I].NowBroken() == true)
 207          Cache.MarkInstall(I,true);
 208
 209    /* Fix packages that are in a NeedArchive state but don't have a
 210       downloadable install version */
 211    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 212    {
 213       if (I.State() != pkgCache::PkgIterator::NeedsUnpack ||
 214           Cache[I].Delete() == true)
 215          continue;
 216
 217       if (Cache[I].InstVerIter(Cache).Downloadable() == false)
 218          continue;
 219
 220       Cache.MarkInstall(I,true);
 221    }
 222
 223    pkgProblemResolver Fix(Cache);
 224    return Fix.Resolve(true);
 225 }
 226                                                                         /*}}}*/
 227 // DistUpgrade - Distribution upgrade                                   /*{{{*/
 228 // ---------------------------------------------------------------------
 229 /* This autoinstalls every package and then force installs every
 230    pre-existing package. This creates the initial set of conditions which
 231    most likely contain problems because too many things were installed.
 232
 233    The problem resolver is used to resolve the problems.
 234  */
 235 bool pkgDistUpgrade(pkgDepCache &Cache)
 236 {
 237    /* Auto upgrade all installed packages, this provides the basis
 238       for the installation */
 239    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 240       if (I->CurrentVer != 0)
 241          Cache.MarkInstall(I,true);
 242
 243    /* Now, auto upgrade all essential packages - this ensures that
 244       the essential packages are present and working */
 245    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 246       if ((I->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
 247          Cache.MarkInstall(I,true);
 248
 249    /* We do it again over all previously installed packages to force
 250       conflict resolution on them all. */
 251    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 252       if (I->CurrentVer != 0)
 253          Cache.MarkInstall(I,false);
 254
 255    pkgProblemResolver Fix(Cache);
 256
 257    // Hold back held packages.
 258    if (_config->FindB("APT::Ingore-Hold",false) == false)
 259    {
 260       for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 261       {
 262          if (I->SelectedState == pkgCache::State::Hold)
 263          {
 264             Fix.Protect(I);
 265             Cache.MarkKeep(I);
 266          }
 267       }
 268    }
 269
 270    return Fix.Resolve();
 271 }
 272                                                                         /*}}}*/
 273 // AllUpgrade - Upgrade as many packages as possible                    /*{{{*/
 274 // ---------------------------------------------------------------------
 275 /* Right now the system must be consistent before this can be called.
 276    It also will not change packages marked for install, it only tries
 277    to install packages not marked for install */
 278 bool pkgAllUpgrade(pkgDepCache &Cache)
 279 {
 280    pkgProblemResolver Fix(Cache);
 281
 282    if (Cache.BrokenCount() != 0)
 283       return false;
 284
 285    // Upgrade all installed packages
 286    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 287    {
 288       if (Cache[I].Install() == true)
 289          Fix.Protect(I);
 290
 291       if (_config->FindB("APT::Ingore-Hold",false) == false)
 292          if (I->SelectedState == pkgCache::State::Hold)
 293             continue;
 294
 295       if (I->CurrentVer != 0 && Cache[I].InstallVer != 0)
 296          Cache.MarkInstall(I,false);
 297    }
 298
 299    return Fix.ResolveByKeep();
 300 }
 301                                                                         /*}}}*/
 302 // MinimizeUpgrade - Minimizes the set of packages to be upgraded       /*{{{*/
 303 // ---------------------------------------------------------------------
 304 /* This simply goes over the entire set of packages and tries to keep
 305    each package marked for upgrade. If a conflict is generated then
 306    the package is restored. */
 307 bool pkgMinimizeUpgrade(pkgDepCache &Cache)
 308 {
 309    if (Cache.BrokenCount() != 0)
 310       return false;
 311
 312    // We loop indefinately to get the minimal set size.
 313    bool Change = false;
 314    do
 315    {
 316       Change = false;
 317       for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 318       {
 319          // Not interesting
 320          if (Cache[I].Upgrade() == false || Cache[I].NewInstall() == true)
 321             continue;
 322
 323          // Keep it and see if that is OK
 324          Cache.MarkKeep(I);
 325          if (Cache.BrokenCount() != 0)
 326             Cache.MarkInstall(I,false);
 327          else
 328             Change = true;
 329       }
 330    }
 331    while (Change == true);
 332
 333    if (Cache.BrokenCount() != 0)
 334       return _error->Error("Internal Error in pkgMinimizeUpgrade");
 335
 336    return true;
 337 }
 338                                                                         /*}}}*/
 339
 340 // ProblemResolver::pkgProblemResolver - Constructor                    /*{{{*/
 341 // ---------------------------------------------------------------------
 342 /* */
 343 pkgProblemResolver::pkgProblemResolver(pkgDepCache &Cache) : Cache(Cache)
 344 {
 345    // Allocate memory
 346    unsigned long Size = Cache.HeaderP->PackageCount;
 347    Scores = new signed short[Size];
 348    Flags = new unsigned char[Size];
 349    memset(Flags,0,sizeof(*Flags)*Size);
 350
 351    // Set debug to true to see its decision logic
 352    Debug = _config->FindB("Debug::pkgProblemResolver",false);
 353 }
 354                                                                         /*}}}*/
 355 // ProblemResolver::ScoreSort - Sort the list by score                  /*{{{*/
 356 // ---------------------------------------------------------------------
 357 /* */
 358 int pkgProblemResolver::ScoreSort(const void *a,const void *b)
 359 {
 360    Package const **A = (Package const **)a;
 361    Package const **B = (Package const **)b;
 362    if (This->Scores[(*A)->ID] > This->Scores[(*B)->ID])
 363       return -1;
 364    if (This->Scores[(*A)->ID] < This->Scores[(*B)->ID])
 365       return 1;
 366    return 0;
 367 }
 368                                                                         /*}}}*/
 369 // ProblemResolver::MakeScores - Make the score table                   /*{{{*/
 370 // ---------------------------------------------------------------------
 371 /* */
 372 void pkgProblemResolver::MakeScores()
 373 {
 374    unsigned long Size = Cache.HeaderP->PackageCount;
 375    memset(Scores,0,sizeof(*Scores)*Size);
 376
 377    // Generate the base scores for a package based on its properties
 378    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 379    {
 380       if (Cache[I].InstallVer == 0)
 381          continue;
 382
 383       signed short &Score = Scores[I->ID];
 384
 385       /* This is arbitary, it should be high enough to elevate an
 386          essantial package above most other packages but low enough
 387          to allow an obsolete essential packages to be removed by
 388          a conflicts on a powerfull normal package (ie libc6) */
 389       if ((I->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
 390          Score += 100;
 391
 392       // We transform the priority
 393       // Important Required Standard Optional Extra
 394       signed short PrioMap[] = {0,3,2,1,-1,-2};
 395       if (Cache[I].InstVerIter(Cache)->Priority <= 5)
 396          Score += PrioMap[Cache[I].InstVerIter(Cache)->Priority];
 397
 398       /* This helps to fix oddball problems with conflicting packages
 399          on the same level. We enhance the score of installed packages */
 400       if (I->CurrentVer != 0)
 401          Score += 1;
 402    }
 403
 404    // Now that we have the base scores we go and propogate dependencies
 405    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 406    {
 407       if (Cache[I].InstallVer == 0)
 408          continue;
 409
 410       for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false; D++)
 411       {
 412          if (D->Type == pkgCache::Dep::Depends || D->Type == pkgCache::Dep::PreDepends)
 413             Scores[D.TargetPkg()->ID]++;
 414       }
 415    }
 416
 417    // Copy the scores to advoid additive looping
 418    signed short *OldScores = new signed short[Size];
 419    memcpy(OldScores,Scores,sizeof(*Scores)*Size);
 420
 421    /* Now we cause 1 level of dependency inheritance, that is we add the
 422       score of the packages that depend on the target Package. This
 423       fortifies high scoring packages */
 424    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 425    {
 426       if (Cache[I].InstallVer == 0)
 427          continue;
 428
 429       for (pkgCache::DepIterator D = I.RevDependsList(); D.end() == false; D++)
 430       {
 431          // Only do it for the install version
 432          if ((pkgCache::Version *)D.ParentVer() != Cache[D.ParentPkg()].InstallVer ||
 433              (D->Type != pkgCache::Dep::Depends && D->Type != pkgCache::Dep::PreDepends))
 434             continue;
 435
 436          Scores[I->ID] += abs(OldScores[D.ParentPkg()->ID]);
 437       }
 438    }
 439
 440    /* Now we propogate along provides. This makes the packages that
 441       provide important packages extremely important */
 442    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 443    {
 444       for (pkgCache::PrvIterator P = I.ProvidesList(); P.end() == false; P++)
 445       {
 446          // Only do it once per package
 447          if ((pkgCache::Version *)P.OwnerVer() != Cache[P.OwnerPkg()].InstallVer)
 448             continue;
 449          Scores[P.OwnerPkg()->ID] += abs(Scores[I->ID] - OldScores[I->ID]);
 450       }
 451    }
 452
 453    /* Protected things are pushed really high up. This number should put them
 454       ahead of everything */
 455    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 456       if ((Flags[I->ID] & Protected) != 0)
 457          Scores[I->ID] += 10000;
 458
 459    delete [] OldScores;
 460 }
 461                                                                         /*}}}*/
 462 // ProblemResolver::DoUpgrade - Attempt to upgrade this package         /*{{{*/
 463 // ---------------------------------------------------------------------
 464 /* This goes through and tries to reinstall packages to make this package
 465    installable */
 466 bool pkgProblemResolver::DoUpgrade(pkgCache::PkgIterator Pkg)
 467 {
 468    if ((Flags[Pkg->ID] & Upgradable) == 0 || Cache[Pkg].Upgradable() == false)
 469       return false;
 470
 471    Flags[Pkg->ID] &= ~Upgradable;
 472
 473    bool WasKept = Cache[Pkg].Keep();
 474    Cache.MarkInstall(Pkg,false);
 475
 476    // This must be a virtual package or something like that.
 477    if (Cache[Pkg].InstVerIter(Cache).end() == true)
 478       return false;
 479
 480    // Isolate the problem dependency
 481    bool Fail = false;
 482    for (pkgCache::DepIterator D = Cache[Pkg].InstVerIter(Cache).DependsList(); D.end() == false;)
 483    {
 484       // Compute a single dependency element (glob or)
 485       pkgCache::DepIterator Start = D;
 486       pkgCache::DepIterator End = D;
 487       unsigned char State = 0;
 488       for (bool LastOR = true; D.end() == false && LastOR == true; D++)
 489       {
 490          State |= Cache[D];
 491          LastOR = (D->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or;
 492          if (LastOR == true)
 493             End = D;
 494       }
 495
 496       // We only worry about critical deps.
 497       if (End.IsCritical() != true)
 498          continue;
 499
 500       // Dep is ok
 501       if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
 502          continue;
 503
 504       // Hm, the group is broken.. I have no idea how to handle this
 505       if (Start != End)
 506       {
 507          clog << "Note, a broken or group was found in " << Pkg.Name() << "." << endl;
 508          Fail = true;
 509          break;
 510       }
 511
 512       // Do not change protected packages
 513       PkgIterator P = Start.SmartTargetPkg();
 514       if ((Flags[P->ID] & Protected) == Protected)
 515       {
 516          if (Debug == true)
 517             clog << "    Reinet Failed because of protected " << P.Name() << endl;
 518          Fail = true;
 519          break;
 520       }
 521
 522       // Upgrade the package if the candidate version will fix the problem.
 523       if ((Cache[Start] & pkgDepCache::DepCVer) == pkgDepCache::DepCVer)
 524       {
 525          if (DoUpgrade(P) == false)
 526          {
 527             if (Debug == true)
 528                clog << "    Reinst Failed because of " << P.Name() << endl;
 529             Fail = true;
 530             break;
 531          }
 532       }
 533       else
 534       {
 535          /* We let the algorithm deal with conflicts on its next iteration,
 536             it is much smarter than us */
 537          if (End->Type == pkgCache::Dep::Conflicts)
 538             continue;
 539
 540          if (Debug == true)
 541             clog << "    Reinst Failed early because of " << Start.TargetPkg().Name() << endl;
 542          Fail = true;
 543          break;
 544       }
 545    }
 546
 547    // Undo our operations - it might be smart to undo everything this did..
 548    if (Fail == true)
 549    {
 550       if (WasKept == true)
 551          Cache.MarkKeep(Pkg);
 552       else
 553          Cache.MarkDelete(Pkg);
 554       return false;
 555    }
 556
 557    if (Debug == true)
 558       clog << "  Re-Instated " << Pkg.Name() << endl;
 559    return true;
 560 }
 561                                                                         /*}}}*/
 562 // ProblemResolver::Resolve - Run the resolution pass                   /*{{{*/
 563 // ---------------------------------------------------------------------
 564 /* This routines works by calculating a score for each package. The score
 565    is derived by considering the package's priority and all reverse
 566    dependents giving an integer that reflects the amount of breakage that
 567    adjusting the package will inflict.
 568
 569    It goes from highest score to lowest and corrects all of the breaks by
 570    keeping or removing the dependant packages. If that fails then it removes
 571    the package itself and goes on. The routine should be able to intelligently
 572    go from any broken state to a fixed state.
 573
 574    The BrokenFix flag enables a mode where the algorithm tries to
 575    upgrade packages to advoid problems. */
 576 bool pkgProblemResolver::Resolve(bool BrokenFix)
 577 {
 578    unsigned long Size = Cache.HeaderP->PackageCount;
 579
 580    // Record which packages are marked for install
 581    bool Again = false;
 582    do
 583    {
 584       Again = false;
 585       for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 586       {
 587          if (Cache[I].Install() == true)
 588             Flags[I->ID] |= PreInstalled;
 589          else
 590          {
 591             if (Cache[I].InstBroken() == true && BrokenFix == true)
 592             {
 593                Cache.MarkInstall(I,false);
 594                if (Cache[I].Install() == true)
 595                   Again = true;
 596             }
 597
 598             Flags[I->ID] &= ~PreInstalled;
 599          }
 600          Flags[I->ID] |= Upgradable;
 601       }
 602    }
 603    while (Again == true);
 604
 605    if (Debug == true)
 606       clog << "Starting" << endl;
 607
 608    MakeScores();
 609
 610    /* We have to order the packages so that the broken fixing pass
 611       operates from highest score to lowest. This prevents problems when
 612       high score packages cause the removal of lower score packages that
 613       would cause the removal of even lower score packages. */
 614    pkgCache::Package **PList = new pkgCache::Package *[Size];
 615    pkgCache::Package **PEnd = PList;
 616    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 617       *PEnd++ = I;
 618    This = this;
 619    qsort(PList,PEnd - PList,sizeof(*PList),&ScoreSort);
 620
 621 /* for (pkgCache::Package **K = PList; K != PEnd; K++)
 622       if (Scores[(*K)->ID] != 0)
 623       {
 624          pkgCache::PkgIterator Pkg(Cache,*K);
 625          clog << Scores[(*K)->ID] << ' ' << Pkg.Name() <<
 626             ' ' << (pkgCache::Version *)Pkg.CurrentVer() << ' ' <<
 627             Cache[Pkg].InstallVer << ' ' << Cache[Pkg].CandidateVer << endl;
 628       } */
 629
 630    if (Debug == true)
 631       clog << "Starting 2" << endl;
 632
 633    /* Now consider all broken packages. For each broken package we either
 634       remove the package or fix it's problem. We do this once, it should
 635       not be possible for a loop to form (that is a < b < c and fixing b by
 636       changing a breaks c) */
 637    bool Change = true;
 638    for (int Counter = 0; Counter != 10 && Change == true; Counter++)
 639    {
 640       Change = false;
 641       for (pkgCache::Package **K = PList; K != PEnd; K++)
 642       {
 643          pkgCache::PkgIterator I(Cache,*K);
 644
 645          /* We attempt to install this and see if any breaks result,
 646             this takes care of some strange cases */
 647          if (Cache[I].CandidateVer != Cache[I].InstallVer &&
 648              I->CurrentVer != 0 && Cache[I].InstallVer != 0 &&
 649              (Flags[I->ID] & PreInstalled) != 0 &&
 650              (Flags[I->ID] & Protected) == 0 &&
 651              (Flags[I->ID] & ReInstateTried) == 0)
 652          {
 653             if (Debug == true)
 654                clog << " Try to Re-Instate " << I.Name() << endl;
 655             unsigned long OldBreaks = Cache.BrokenCount();
 656             pkgCache::Version *OldVer = Cache[I].InstallVer;
 657             Flags[I->ID] &= ReInstateTried;
 658
 659             Cache.MarkInstall(I,false);
 660             if (Cache[I].InstBroken() == true ||
 661                 OldBreaks < Cache.BrokenCount())
 662             {
 663                if (OldVer == 0)
 664                   Cache.MarkDelete(I);
 665                else
 666                   Cache.MarkKeep(I);
 667             }
 668             else
 669                if (Debug == true)
 670                   clog << "Re-Instated " << I.Name() << " (" << OldBreaks << " vs " << Cache.BrokenCount() << ')' << endl;
 671          }
 672
 673          if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false)
 674             continue;
 675
 676          // Isolate the problem dependency
 677          PackageKill KillList[100];
 678          PackageKill *LEnd = KillList;
 679          for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false;)
 680          {
 681             // Compute a single dependency element (glob or)
 682             pkgCache::DepIterator Start;
 683             pkgCache::DepIterator End;
 684             D.GlobOr(Start,End);
 685
 686             // We only worry about critical deps.
 687             if (End.IsCritical() != true)
 688                continue;
 689
 690             // Dep is ok
 691             if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
 692                continue;
 693
 694             // Hm, the group is broken.. I have no idea how to handle this
 695             if (Start != End)
 696             {
 697                clog << "Note, a broken or group was found in " << I.Name() << "." << endl;
 698                Cache.MarkDelete(I);
 699                break;
 700             }
 701
 702             if (Debug == true)
 703                clog << "Package " << I.Name() << " has broken dep on " << End.TargetPkg().Name() << endl;
 704
 705             /* Look across the version list. If there are no possible
 706                targets then we keep the package and bail. This is necessary
 707                if a package has a dep on another package that cant be found */
 708             pkgCache::Version **VList = End.AllTargets();
 709             if (*VList == 0 && (Flags[I->ID] & Protected) != Protected &&
 710                 End->Type != pkgCache::Dep::Conflicts &&
 711                 Cache[I].NowBroken() == false)
 712             {
 713                Change = true;
 714                Cache.MarkKeep(I);
 715                break;
 716             }
 717
 718             bool Done = false;
 719             for (pkgCache::Version **V = VList; *V != 0; V++)
 720             {
 721                pkgCache::VerIterator Ver(Cache,*V);
 722                pkgCache::PkgIterator Pkg = Ver.ParentPkg();
 723
 724                if (Debug == true)
 725                   clog << "  Considering " << Pkg.Name() << ' ' << (int)Scores[Pkg->ID] <<
 726                   " as a solution to " << I.Name() << ' ' << (int)Scores[I->ID] << endl;
 727                if (Scores[I->ID] <= Scores[Pkg->ID] ||
 728                    ((Cache[End] & pkgDepCache::DepGNow) == 0 &&
 729                     End->Type != pkgCache::Dep::Conflicts))
 730                {
 731                   if ((Flags[I->ID] & Protected) == Protected)
 732                      continue;
 733
 734                   // See if a keep will do
 735                   Cache.MarkKeep(I);
 736                   if (Cache[I].InstBroken() == false)
 737                   {
 738                      if (Debug == true)
 739                         clog << "  Holding Back " << I.Name() << " rather than change " << End.TargetPkg().Name() << endl;
 740                   }
 741                   else
 742                   {
 743                      if (BrokenFix == false || DoUpgrade(I) == false)
 744                      {
 745                         if (Debug == true)
 746                            clog << "  Removing " << I.Name() << " rather than change " << End.TargetPkg().Name() << endl;
 747                         Cache.MarkDelete(I);
 748                         if (Counter > 1)
 749                            Scores[I->ID] = Scores[Pkg->ID];
 750                      }
 751                   }
 752
 753                   Change = true;
 754                   Done = true;
 755                   break;
 756                }
 757                else
 758                {
 759                   // Skip this if it is protected
 760                   if ((Flags[Pkg->ID] & Protected) != 0)
 761                      continue;
 762
 763                   LEnd->Pkg = Pkg;
 764                   LEnd->Dep = End;
 765                   LEnd++;
 766
 767                   if (End->Type != pkgCache::Dep::Conflicts)
 768                      break;
 769                }
 770             }
 771
 772             // Hm, nothing can possibly satisify this dep. Nuke it.
 773             if (VList[0] == 0 && End->Type != pkgCache::Dep::Conflicts &&
 774                 (Flags[I->ID] & Protected) != Protected)
 775             {
 776                Cache.MarkKeep(I);
 777                if (Cache[I].InstBroken() == false)
 778                {
 779                   if (Debug == true)
 780                      clog << "  Holding Back " << I.Name() << " because I can't find " << End.TargetPkg().Name() << endl;
 781                }
 782                else
 783                {
 784                   if (Debug == true)
 785                      clog << "  Removing " << I.Name() << " because I can't find " << End.TargetPkg().Name() << endl;
 786                   Cache.MarkDelete(I);
 787                }
 788
 789                Change = true;
 790                Done = true;
 791             }
 792
 793             delete [] VList;
 794             if (Done == true)
 795                break;
 796          }
 797
 798          // Apply the kill list now
 799          if (Cache[I].InstallVer != 0)
 800             for (PackageKill *J = KillList; J != LEnd; J++)
 801          {
 802             Change = true;
 803             if ((Cache[J->Dep] & pkgDepCache::DepGNow) == 0)
 804             {
 805                if (J->Dep->Type == pkgCache::Dep::Conflicts)
 806                {
 807                   if (Debug == true)
 808                      clog << "  Fixing " << I.Name() << " via remove of " << J->Pkg.Name() << endl;
 809                   Cache.MarkDelete(J->Pkg);
 810                }
 811             }
 812             else
 813             {
 814                if (Debug == true)
 815                   clog << "  Fixing " << I.Name() << " via keep of " << J->Pkg.Name() << endl;
 816                Cache.MarkKeep(J->Pkg);
 817             }
 818
 819             if (Counter > 1)
 820                Scores[J->Pkg->ID] = Scores[I->ID];
 821          }
 822       }
 823    }
 824
 825    if (Debug == true)
 826       clog << "Done" << endl;
 827
 828    delete [] Scores;
 829    delete [] PList;
 830
 831    if (Cache.BrokenCount() != 0)
 832       return _error->Error("Internal error, pkgProblemResolver::Resolve generated breaks.");
 833
 834    return true;
 835 }
 836                                                                         /*}}}*/
 837 // ProblemResolver::ResolveByKeep - Resolve problems using keep         /*{{{*/
 838 // ---------------------------------------------------------------------
 839 /* This is the work horse of the soft upgrade routine. It is very gental
 840    in that it does not install or remove any packages. It is assumed that the
 841    system was non-broken previously. */
 842 bool pkgProblemResolver::ResolveByKeep()
 843 {
 844    unsigned long Size = Cache.HeaderP->PackageCount;
 845
 846    if (Debug == true)
 847       clog << "Entering ResolveByKeep" << endl;
 848
 849    MakeScores();
 850
 851    /* We have to order the packages so that the broken fixing pass
 852       operates from highest score to lowest. This prevents problems when
 853       high score packages cause the removal of lower score packages that
 854       would cause the removal of even lower score packages. */
 855    pkgCache::Package **PList = new pkgCache::Package *[Size];
 856    pkgCache::Package **PEnd = PList;
 857    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 858       *PEnd++ = I;
 859    This = this;
 860    qsort(PList,PEnd - PList,sizeof(*PList),&ScoreSort);
 861
 862    // Consider each broken package
 863    pkgCache::Package **LastStop = 0;
 864    for (pkgCache::Package **K = PList; K != PEnd; K++)
 865    {
 866       pkgCache::PkgIterator I(Cache,*K);
 867
 868       if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false)
 869          continue;
 870
 871       /* Keep the package. If this works then great, otherwise we have
 872          to be significantly more agressive and manipulate its dependencies */
 873       if ((Flags[I->ID] & Protected) == 0)
 874       {
 875          if (Debug == true)
 876             clog << "Keeping package " << I.Name() << endl;
 877          Cache.MarkKeep(I);
 878          if (Cache[I].InstBroken() == false)
 879          {
 880             K = PList;
 881             continue;
 882          }
 883       }
 884
 885       // Isolate the problem dependencies
 886       for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false;)
 887       {
 888          // Compute a single dependency element (glob or)
 889          pkgCache::DepIterator Start = D;
 890          pkgCache::DepIterator End = D;
 891          unsigned char State = 0;
 892          for (bool LastOR = true; D.end() == false && LastOR == true; D++)
 893          {
 894             State |= Cache[D];
 895             LastOR = (D->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or;
 896             if (LastOR == true)
 897                End = D;
 898          }
 899
 900          // We only worry about critical deps.
 901          if (End.IsCritical() != true)
 902             continue;
 903
 904          // Dep is ok
 905          if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
 906             continue;
 907
 908          // Hm, the group is broken.. I have no idea how to handle this
 909          if (Start != End)
 910          {
 911             clog << "Note, a broken or group was found in " << I.Name() << "." << endl;
 912             if ((Flags[I->ID] & Protected) == 0)
 913                Cache.MarkKeep(I);
 914             break;
 915          }
 916
 917          if (Debug == true)
 918             clog << "Package " << I.Name() << " has broken dep on " << End.TargetPkg().Name() << endl;
 919
 920          // Look at all the possible provides on this package
 921          pkgCache::Version **VList = End.AllTargets();
 922          for (pkgCache::Version **V = VList; *V != 0; V++)
 923          {
 924             pkgCache::VerIterator Ver(Cache,*V);
 925             pkgCache::PkgIterator Pkg = Ver.ParentPkg();
 926
 927             // It is not keepable
 928             if (Cache[Pkg].InstallVer == 0 ||
 929                 Pkg->CurrentVer == 0)
 930                continue;
 931
 932             if ((Flags[I->ID] & Protected) == 0)
 933             {
 934                if (Debug == true)
 935                   clog << "  Keeping Package " << Pkg.Name() << " due to dep" << endl;
 936                Cache.MarkKeep(Pkg);
 937             }
 938
 939             if (Cache[I].InstBroken() == false)
 940                break;
 941          }
 942
 943          if (Cache[I].InstBroken() == false)
 944             break;
 945       }
 946
 947       if (Cache[I].InstBroken() == true)
 948          continue;
 949
 950       // Restart again.
 951       if (K == LastStop)
 952          return _error->Error("Internal Error, pkgProblemResolver::ResolveByKeep is looping on package %s.",I.Name());
 953       LastStop = K;
 954       K = PList;
 955    }
 956
 957    return true;
 958 }
 959                                                                         /*}}}*/
 960 // ProblemResolver::InstallProtect - Install all protected packages     /*{{{*/
 961 // ---------------------------------------------------------------------
 962 /* This is used to make sure protected packages are installed */
 963 void pkgProblemResolver::InstallProtect()
 964 {
 965    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 966    {
 967       if ((Flags[I->ID] & Protected) == Protected)
 968       {
 969          if ((Flags[I->ID] & ToRemove) == ToRemove)
 970             Cache.MarkDelete(I);
 971          else
 972             Cache.MarkInstall(I,false);
 973       }
 974    }
 975 }
 976                                                                         /*}}}*/