apt-pkg/algorithms.cc

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