apt-pkg/algorithms.cc

   1 // -*- mode: cpp; mode: fold -*-
   2 // Description                                                          /*{{{*/
   3 // $Id: algorithms.cc,v 1.13 1998/12/06 03:41:25 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    {
 457       if ((Flags[I->ID] & Protected) != 0)
 458          Scores[I->ID] += 10000;
 459       if ((I->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
 460          Scores[I->ID] += 5000;
 461    }
 462
 463    delete [] OldScores;
 464 }
 465                                                                         /*}}}*/
 466 // ProblemResolver::DoUpgrade - Attempt to upgrade this package         /*{{{*/
 467 // ---------------------------------------------------------------------
 468 /* This goes through and tries to reinstall packages to make this package
 469    installable */
 470 bool pkgProblemResolver::DoUpgrade(pkgCache::PkgIterator Pkg)
 471 {
 472    if ((Flags[Pkg->ID] & Upgradable) == 0 || Cache[Pkg].Upgradable() == false)
 473       return false;
 474
 475    Flags[Pkg->ID] &= ~Upgradable;
 476
 477    bool WasKept = Cache[Pkg].Keep();
 478    Cache.MarkInstall(Pkg,false);
 479
 480    // This must be a virtual package or something like that.
 481    if (Cache[Pkg].InstVerIter(Cache).end() == true)
 482       return false;
 483
 484    // Isolate the problem dependency
 485    bool Fail = false;
 486    for (pkgCache::DepIterator D = Cache[Pkg].InstVerIter(Cache).DependsList(); D.end() == false;)
 487    {
 488       // Compute a single dependency element (glob or)
 489       pkgCache::DepIterator Start = D;
 490       pkgCache::DepIterator End = D;
 491       unsigned char State = 0;
 492       for (bool LastOR = true; D.end() == false && LastOR == true; D++)
 493       {
 494          State |= Cache[D];
 495          LastOR = (D->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or;
 496          if (LastOR == true)
 497             End = D;
 498       }
 499
 500       // We only worry about critical deps.
 501       if (End.IsCritical() != true)
 502          continue;
 503
 504       // Dep is ok
 505       if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
 506          continue;
 507
 508       // Hm, the group is broken.. I have no idea how to handle this
 509       if (Start != End)
 510       {
 511          clog << "Note, a broken or group was found in " << Pkg.Name() << "." << endl;
 512          Fail = true;
 513          break;
 514       }
 515
 516       // Do not change protected packages
 517       PkgIterator P = Start.SmartTargetPkg();
 518       if ((Flags[P->ID] & Protected) == Protected)
 519       {
 520          if (Debug == true)
 521             clog << "    Reinet Failed because of protected " << P.Name() << endl;
 522          Fail = true;
 523          break;
 524       }
 525
 526       // Upgrade the package if the candidate version will fix the problem.
 527       if ((Cache[Start] & pkgDepCache::DepCVer) == pkgDepCache::DepCVer)
 528       {
 529          if (DoUpgrade(P) == false)
 530          {
 531             if (Debug == true)
 532                clog << "    Reinst Failed because of " << P.Name() << endl;
 533             Fail = true;
 534             break;
 535          }
 536       }
 537       else
 538       {
 539          /* We let the algorithm deal with conflicts on its next iteration,
 540             it is much smarter than us */
 541          if (End->Type == pkgCache::Dep::Conflicts)
 542             continue;
 543
 544          if (Debug == true)
 545             clog << "    Reinst Failed early because of " << Start.TargetPkg().Name() << endl;
 546          Fail = true;
 547          break;
 548       }
 549    }
 550
 551    // Undo our operations - it might be smart to undo everything this did..
 552    if (Fail == true)
 553    {
 554       if (WasKept == true)
 555          Cache.MarkKeep(Pkg);
 556       else
 557          Cache.MarkDelete(Pkg);
 558       return false;
 559    }
 560
 561    if (Debug == true)
 562       clog << "  Re-Instated " << Pkg.Name() << endl;
 563    return true;
 564 }
 565                                                                         /*}}}*/
 566 // ProblemResolver::Resolve - Run the resolution pass                   /*{{{*/
 567 // ---------------------------------------------------------------------
 568 /* This routines works by calculating a score for each package. The score
 569    is derived by considering the package's priority and all reverse
 570    dependents giving an integer that reflects the amount of breakage that
 571    adjusting the package will inflict.
 572
 573    It goes from highest score to lowest and corrects all of the breaks by
 574    keeping or removing the dependant packages. If that fails then it removes
 575    the package itself and goes on. The routine should be able to intelligently
 576    go from any broken state to a fixed state.
 577
 578    The BrokenFix flag enables a mode where the algorithm tries to
 579    upgrade packages to advoid problems. */
 580 bool pkgProblemResolver::Resolve(bool BrokenFix)
 581 {
 582    unsigned long Size = Cache.HeaderP->PackageCount;
 583
 584    // Record which packages are marked for install
 585    bool Again = false;
 586    do
 587    {
 588       Again = false;
 589       for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 590       {
 591          if (Cache[I].Install() == true)
 592             Flags[I->ID] |= PreInstalled;
 593          else
 594          {
 595             if (Cache[I].InstBroken() == true && BrokenFix == true)
 596             {
 597                Cache.MarkInstall(I,false);
 598                if (Cache[I].Install() == true)
 599                   Again = true;
 600             }
 601
 602             Flags[I->ID] &= ~PreInstalled;
 603          }
 604          Flags[I->ID] |= Upgradable;
 605       }
 606    }
 607    while (Again == true);
 608
 609    if (Debug == true)
 610       clog << "Starting" << endl;
 611
 612    MakeScores();
 613
 614    /* We have to order the packages so that the broken fixing pass
 615       operates from highest score to lowest. This prevents problems when
 616       high score packages cause the removal of lower score packages that
 617       would cause the removal of even lower score packages. */
 618    pkgCache::Package **PList = new pkgCache::Package *[Size];
 619    pkgCache::Package **PEnd = PList;
 620    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 621       *PEnd++ = I;
 622    This = this;
 623    qsort(PList,PEnd - PList,sizeof(*PList),&ScoreSort);
 624
 625 /* for (pkgCache::Package **K = PList; K != PEnd; K++)
 626       if (Scores[(*K)->ID] != 0)
 627       {
 628          pkgCache::PkgIterator Pkg(Cache,*K);
 629          clog << Scores[(*K)->ID] << ' ' << Pkg.Name() <<
 630             ' ' << (pkgCache::Version *)Pkg.CurrentVer() << ' ' <<
 631             Cache[Pkg].InstallVer << ' ' << Cache[Pkg].CandidateVer << endl;
 632       } */
 633
 634    if (Debug == true)
 635       clog << "Starting 2" << endl;
 636
 637    /* Now consider all broken packages. For each broken package we either
 638       remove the package or fix it's problem. We do this once, it should
 639       not be possible for a loop to form (that is a < b < c and fixing b by
 640       changing a breaks c) */
 641    bool Change = true;
 642    for (int Counter = 0; Counter != 10 && Change == true; Counter++)
 643    {
 644       Change = false;
 645       for (pkgCache::Package **K = PList; K != PEnd; K++)
 646       {
 647          pkgCache::PkgIterator I(Cache,*K);
 648
 649          /* We attempt to install this and see if any breaks result,
 650             this takes care of some strange cases */
 651          if (Cache[I].CandidateVer != Cache[I].InstallVer &&
 652              I->CurrentVer != 0 && Cache[I].InstallVer != 0 &&
 653              (Flags[I->ID] & PreInstalled) != 0 &&
 654              (Flags[I->ID] & Protected) == 0 &&
 655              (Flags[I->ID] & ReInstateTried) == 0)
 656          {
 657             if (Debug == true)
 658                clog << " Try to Re-Instate " << I.Name() << endl;
 659             unsigned long OldBreaks = Cache.BrokenCount();
 660             pkgCache::Version *OldVer = Cache[I].InstallVer;
 661             Flags[I->ID] &= ReInstateTried;
 662
 663             Cache.MarkInstall(I,false);
 664             if (Cache[I].InstBroken() == true ||
 665                 OldBreaks < Cache.BrokenCount())
 666             {
 667                if (OldVer == 0)
 668                   Cache.MarkDelete(I);
 669                else
 670                   Cache.MarkKeep(I);
 671             }
 672             else
 673                if (Debug == true)
 674                   clog << "Re-Instated " << I.Name() << " (" << OldBreaks << " vs " << Cache.BrokenCount() << ')' << endl;
 675          }
 676
 677          if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false)
 678             continue;
 679
 680          // Isolate the problem dependency
 681          PackageKill KillList[100];
 682          PackageKill *LEnd = KillList;
 683          for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false;)
 684          {
 685             // Compute a single dependency element (glob or)
 686             pkgCache::DepIterator Start;
 687             pkgCache::DepIterator End;
 688             D.GlobOr(Start,End);
 689
 690             // We only worry about critical deps.
 691             if (End.IsCritical() != true)
 692                continue;
 693
 694             // Dep is ok
 695             if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
 696                continue;
 697
 698             // Hm, the group is broken.. I have no idea how to handle this
 699             if (Start != End)
 700             {
 701                if (Debug == true)
 702                   clog << "Note, a broken or group was found in " << I.Name() << "." << endl;
 703                Cache.MarkDelete(I);
 704                break;
 705             }
 706
 707             if (Debug == true)
 708                clog << "Package " << I.Name() << " has broken dep on " << End.TargetPkg().Name() << endl;
 709
 710             /* Look across the version list. If there are no possible
 711                targets then we keep the package and bail. This is necessary
 712                if a package has a dep on another package that cant be found */
 713             pkgCache::Version **VList = End.AllTargets();
 714             if (*VList == 0 && (Flags[I->ID] & Protected) != Protected &&
 715                 End->Type != pkgCache::Dep::Conflicts &&
 716                 Cache[I].NowBroken() == false)
 717             {
 718                Change = true;
 719                Cache.MarkKeep(I);
 720                break;
 721             }
 722
 723             bool Done = false;
 724             for (pkgCache::Version **V = VList; *V != 0; V++)
 725             {
 726                pkgCache::VerIterator Ver(Cache,*V);
 727                pkgCache::PkgIterator Pkg = Ver.ParentPkg();
 728
 729                if (Debug == true)
 730                   clog << "  Considering " << Pkg.Name() << ' ' << (int)Scores[Pkg->ID] <<
 731                   " as a solution to " << I.Name() << ' ' << (int)Scores[I->ID] << endl;
 732                if (Scores[I->ID] <= Scores[Pkg->ID] ||
 733                    ((Cache[End] & pkgDepCache::DepGNow) == 0 &&
 734                     End->Type != pkgCache::Dep::Conflicts))
 735                {
 736                   if ((Flags[I->ID] & Protected) == Protected)
 737                      continue;
 738
 739                   // See if a keep will do
 740                   Cache.MarkKeep(I);
 741                   if (Cache[I].InstBroken() == false)
 742                   {
 743                      if (Debug == true)
 744                         clog << "  Holding Back " << I.Name() << " rather than change " << End.TargetPkg().Name() << endl;
 745                   }
 746                   else
 747                   {
 748                      if (BrokenFix == false || DoUpgrade(I) == false)
 749                      {
 750                         if (Debug == true)
 751                            clog << "  Removing " << I.Name() << " rather than change " << End.TargetPkg().Name() << endl;
 752                         Cache.MarkDelete(I);
 753                         if (Counter > 1)
 754                            Scores[I->ID] = Scores[Pkg->ID];
 755                      }
 756                   }
 757
 758                   Change = true;
 759                   Done = true;
 760                   break;
 761                }
 762                else
 763                {
 764                   // Skip this if it is protected
 765                   if ((Flags[Pkg->ID] & Protected) != 0)
 766                      continue;
 767
 768                   LEnd->Pkg = Pkg;
 769                   LEnd->Dep = End;
 770                   LEnd++;
 771
 772                   if (End->Type != pkgCache::Dep::Conflicts)
 773                      break;
 774                }
 775             }
 776
 777             // Hm, nothing can possibly satisify this dep. Nuke it.
 778             if (VList[0] == 0 && End->Type != pkgCache::Dep::Conflicts &&
 779                 (Flags[I->ID] & Protected) != Protected)
 780             {
 781                Cache.MarkKeep(I);
 782                if (Cache[I].InstBroken() == false)
 783                {
 784                   if (Debug == true)
 785                      clog << "  Holding Back " << I.Name() << " because I can't find " << End.TargetPkg().Name() << endl;
 786                }
 787                else
 788                {
 789                   if (Debug == true)
 790                      clog << "  Removing " << I.Name() << " because I can't find " << End.TargetPkg().Name() << endl;
 791                   Cache.MarkDelete(I);
 792                }
 793
 794                Change = true;
 795                Done = true;
 796             }
 797
 798             delete [] VList;
 799             if (Done == true)
 800                break;
 801          }
 802
 803          // Apply the kill list now
 804          if (Cache[I].InstallVer != 0)
 805             for (PackageKill *J = KillList; J != LEnd; J++)
 806          {
 807             Change = true;
 808             if ((Cache[J->Dep] & pkgDepCache::DepGNow) == 0)
 809             {
 810                if (J->Dep->Type == pkgCache::Dep::Conflicts)
 811                {
 812                   if (Debug == true)
 813                      clog << "  Fixing " << I.Name() << " via remove of " << J->Pkg.Name() << endl;
 814                   Cache.MarkDelete(J->Pkg);
 815                }
 816             }
 817             else
 818             {
 819                if (Debug == true)
 820                   clog << "  Fixing " << I.Name() << " via keep of " << J->Pkg.Name() << endl;
 821                Cache.MarkKeep(J->Pkg);
 822             }
 823
 824             if (Counter > 1)
 825                Scores[J->Pkg->ID] = Scores[I->ID];
 826          }
 827       }
 828    }
 829
 830    if (Debug == true)
 831       clog << "Done" << endl;
 832
 833    delete [] Scores;
 834    delete [] PList;
 835
 836    if (Cache.BrokenCount() != 0)
 837       return _error->Error("Internal error, pkgProblemResolver::Resolve generated breaks.");
 838
 839    return true;
 840 }
 841                                                                         /*}}}*/
 842 // ProblemResolver::ResolveByKeep - Resolve problems using keep         /*{{{*/
 843 // ---------------------------------------------------------------------
 844 /* This is the work horse of the soft upgrade routine. It is very gental
 845    in that it does not install or remove any packages. It is assumed that the
 846    system was non-broken previously. */
 847 bool pkgProblemResolver::ResolveByKeep()
 848 {
 849    unsigned long Size = Cache.HeaderP->PackageCount;
 850
 851    if (Debug == true)
 852       clog << "Entering ResolveByKeep" << endl;
 853
 854    MakeScores();
 855
 856    /* We have to order the packages so that the broken fixing pass
 857       operates from highest score to lowest. This prevents problems when
 858       high score packages cause the removal of lower score packages that
 859       would cause the removal of even lower score packages. */
 860    pkgCache::Package **PList = new pkgCache::Package *[Size];
 861    pkgCache::Package **PEnd = PList;
 862    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 863       *PEnd++ = I;
 864    This = this;
 865    qsort(PList,PEnd - PList,sizeof(*PList),&ScoreSort);
 866
 867    // Consider each broken package
 868    pkgCache::Package **LastStop = 0;
 869    for (pkgCache::Package **K = PList; K != PEnd; K++)
 870    {
 871       pkgCache::PkgIterator I(Cache,*K);
 872
 873       if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false)
 874          continue;
 875
 876       /* Keep the package. If this works then great, otherwise we have
 877          to be significantly more agressive and manipulate its dependencies */
 878       if ((Flags[I->ID] & Protected) == 0)
 879       {
 880          if (Debug == true)
 881             clog << "Keeping package " << I.Name() << endl;
 882          Cache.MarkKeep(I);
 883          if (Cache[I].InstBroken() == false)
 884          {
 885             K = PList;
 886             continue;
 887          }
 888       }
 889
 890       // Isolate the problem dependencies
 891       for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false;)
 892       {
 893          // Compute a single dependency element (glob or)
 894          pkgCache::DepIterator Start = D;
 895          pkgCache::DepIterator End = D;
 896          unsigned char State = 0;
 897          for (bool LastOR = true; D.end() == false && LastOR == true; D++)
 898          {
 899             State |= Cache[D];
 900             LastOR = (D->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or;
 901             if (LastOR == true)
 902                End = D;
 903          }
 904
 905          // We only worry about critical deps.
 906          if (End.IsCritical() != true)
 907             continue;
 908
 909          // Dep is ok
 910          if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
 911             continue;
 912
 913          // Hm, the group is broken.. I have no idea how to handle this
 914          if (Start != End)
 915          {
 916             clog << "Note, a broken or group was found in " << I.Name() << "." << endl;
 917             if ((Flags[I->ID] & Protected) == 0)
 918                Cache.MarkKeep(I);
 919             break;
 920          }
 921
 922          if (Debug == true)
 923             clog << "Package " << I.Name() << " has broken dep on " << End.TargetPkg().Name() << endl;
 924
 925          // Look at all the possible provides on this package
 926          pkgCache::Version **VList = End.AllTargets();
 927          for (pkgCache::Version **V = VList; *V != 0; V++)
 928          {
 929             pkgCache::VerIterator Ver(Cache,*V);
 930             pkgCache::PkgIterator Pkg = Ver.ParentPkg();
 931
 932             // It is not keepable
 933             if (Cache[Pkg].InstallVer == 0 ||
 934                 Pkg->CurrentVer == 0)
 935                continue;
 936
 937             if ((Flags[I->ID] & Protected) == 0)
 938             {
 939                if (Debug == true)
 940                   clog << "  Keeping Package " << Pkg.Name() << " due to dep" << endl;
 941                Cache.MarkKeep(Pkg);
 942             }
 943
 944             if (Cache[I].InstBroken() == false)
 945                break;
 946          }
 947
 948          if (Cache[I].InstBroken() == false)
 949             break;
 950       }
 951
 952       if (Cache[I].InstBroken() == true)
 953          continue;
 954
 955       // Restart again.
 956       if (K == LastStop)
 957          return _error->Error("Internal Error, pkgProblemResolver::ResolveByKeep is looping on package %s.",I.Name());
 958       LastStop = K;
 959       K = PList;
 960    }
 961
 962    return true;
 963 }
 964                                                                         /*}}}*/
 965 // ProblemResolver::InstallProtect - Install all protected packages     /*{{{*/
 966 // ---------------------------------------------------------------------
 967 /* This is used to make sure protected packages are installed */
 968 void pkgProblemResolver::InstallProtect()
 969 {
 970    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 971    {
 972       if ((Flags[I->ID] & Protected) == Protected)
 973       {
 974          if ((Flags[I->ID] & ToRemove) == ToRemove)
 975             Cache.MarkDelete(I);
 976          else
 977             Cache.MarkInstall(I,false);
 978       }
 979    }
 980 }
 981                                                                         /*}}}*/