apt-pkg/algorithms.cc

   1 // -*- mode: cpp; mode: fold -*-
   2 // Description                                                          /*{{{*/
   3 // $Id: algorithms.cc,v 1.8 1998/10/24 04:58:04 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             int 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 = D;
 675             pkgCache::DepIterator End = D;
 676             unsigned char State = 0;
 677             for (bool LastOR = true; D.end() == false && LastOR == true; D++)
 678             {
 679                State |= Cache[D];
 680                LastOR = (D->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or;
 681                if (LastOR == true)
 682                   End = D;
 683             }
 684
 685             // We only worry about critical deps.
 686             if (End.IsCritical() != true)
 687                continue;
 688
 689             // Dep is ok
 690             if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
 691                continue;
 692
 693             // Hm, the group is broken.. I have no idea how to handle this
 694             if (Start != End)
 695             {
 696                clog << "Note, a broken or group was found in " << I.Name() << "." << endl;
 697                Cache.MarkDelete(I);
 698                break;
 699             }
 700
 701             if (Debug == true)
 702                clog << "Package " << I.Name() << " has broken dep on " << End.TargetPkg().Name() << endl;
 703
 704             /* Conflicts is simple, decide if we should remove this package
 705                or the conflicted one */
 706             pkgCache::Version **VList = End.AllTargets();
 707             bool Done = false;
 708             for (pkgCache::Version **V = VList; *V != 0; V++)
 709             {
 710                pkgCache::VerIterator Ver(Cache,*V);
 711                pkgCache::PkgIterator Pkg = Ver.ParentPkg();
 712
 713                if (Debug == true)
 714                   clog << "  Considering " << Pkg.Name() << ' ' << (int)Scores[Pkg->ID] <<
 715                   " as a solution to " << I.Name() << ' ' << (int)Scores[I->ID] << endl;
 716                if (Scores[I->ID] <= Scores[Pkg->ID] ||
 717                    ((Cache[End] & pkgDepCache::DepGNow) == 0 &&
 718                     End->Type != pkgCache::Dep::Conflicts))
 719                {
 720                   if ((Flags[I->ID] & Protected) == Protected)
 721                      continue;
 722
 723                   // See if a keep will do
 724                   Cache.MarkKeep(I);
 725                   if (Cache[I].InstBroken() == false)
 726                   {
 727                      if (Debug == true)
 728                         clog << "  Holding Back " << I.Name() << " rather than change " << End.TargetPkg().Name() << endl;
 729                   }
 730                   else
 731                   {
 732                      if (BrokenFix == false || DoUpgrade(I) == false)
 733                      {
 734                         if (Debug == true)
 735                            clog << "  Removing " << I.Name() << " rather than change " << End.TargetPkg().Name() << endl;
 736                         Cache.MarkDelete(I);
 737                         if (Counter > 1)
 738                            Scores[I->ID] = Scores[Pkg->ID];
 739                      }
 740                   }
 741
 742                   Change = true;
 743                   Done = true;
 744                   break;
 745                }
 746                else
 747                {
 748                   // Skip this if it is protected
 749                   if ((Flags[Pkg->ID] & Protected) != 0)
 750                      continue;
 751
 752                   LEnd->Pkg = Pkg;
 753                   LEnd->Dep = End;
 754                   LEnd++;
 755
 756                   if (End->Type != pkgCache::Dep::Conflicts)
 757                      break;
 758                }
 759             }
 760
 761             // Hm, nothing can possibly satisify this dep. Nuke it.
 762             if (VList[0] == 0 && End->Type != pkgCache::Dep::Conflicts &&
 763                 (Flags[I->ID] & Protected) != Protected)
 764             {
 765                Cache.MarkKeep(I);
 766                if (Cache[I].InstBroken() == false)
 767                {
 768                   if (Debug == true)
 769                      clog << "  Holding Back " << I.Name() << " because I can't find " << End.TargetPkg().Name() << endl;
 770                }
 771                else
 772                {
 773                   if (Debug == true)
 774                      clog << "  Removing " << I.Name() << " because I can't find " << End.TargetPkg().Name() << endl;
 775                   Cache.MarkDelete(I);
 776                }
 777
 778                Change = true;
 779                Done = true;
 780             }
 781
 782             delete [] VList;
 783             if (Done == true)
 784                break;
 785          }
 786
 787          // Apply the kill list now
 788          if (Cache[I].InstallVer != 0)
 789             for (PackageKill *J = KillList; J != LEnd; J++)
 790          {
 791             Change = true;
 792             if ((Cache[J->Dep] & pkgDepCache::DepGNow) == 0)
 793             {
 794                if (J->Dep->Type == pkgCache::Dep::Conflicts)
 795                {
 796                   if (Debug == true)
 797                      clog << "  Fixing " << I.Name() << " via remove of " << J->Pkg.Name() << endl;
 798                   Cache.MarkDelete(J->Pkg);
 799                }
 800             }
 801             else
 802             {
 803                if (Debug == true)
 804                   clog << "  Fixing " << I.Name() << " via keep of " << J->Pkg.Name() << endl;
 805                Cache.MarkKeep(J->Pkg);
 806             }
 807
 808             if (Counter > 1)
 809                Scores[J->Pkg->ID] = Scores[I->ID];
 810          }
 811       }
 812    }
 813
 814    if (Debug == true)
 815       clog << "Done" << endl;
 816
 817    delete [] Scores;
 818    delete [] PList;
 819
 820    if (Cache.BrokenCount() != 0)
 821       return _error->Error("Internal error, pkgProblemResolver::Resolve generated breaks.");
 822
 823    return true;
 824 }
 825                                                                         /*}}}*/
 826 // ProblemResolver::ResolveByKeep - Resolve problems using keep         /*{{{*/
 827 // ---------------------------------------------------------------------
 828 /* This is the work horse of the soft upgrade routine. It is very gental
 829    in that it does not install or remove any packages. It is assumed that the
 830    system was non-broken previously. */
 831 bool pkgProblemResolver::ResolveByKeep()
 832 {
 833    unsigned long Size = Cache.HeaderP->PackageCount;
 834
 835    if (Debug == true)
 836       clog << "Entering ResolveByKeep" << endl;
 837
 838    MakeScores();
 839
 840    /* We have to order the packages so that the broken fixing pass
 841       operates from highest score to lowest. This prevents problems when
 842       high score packages cause the removal of lower score packages that
 843       would cause the removal of even lower score packages. */
 844    pkgCache::Package **PList = new pkgCache::Package *[Size];
 845    pkgCache::Package **PEnd = PList;
 846    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 847       *PEnd++ = I;
 848    This = this;
 849    qsort(PList,PEnd - PList,sizeof(*PList),&ScoreSort);
 850
 851    // Consider each broken package
 852    pkgCache::Package **LastStop = 0;
 853    for (pkgCache::Package **K = PList; K != PEnd; K++)
 854    {
 855       pkgCache::PkgIterator I(Cache,*K);
 856
 857       if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false)
 858          continue;
 859
 860       /* Keep the package. If this works then great, otherwise we have
 861          to be significantly more agressive and manipulate its dependencies */
 862       if ((Flags[I->ID] & Protected) == 0)
 863       {
 864          if (Debug == true)
 865             clog << "Keeping package " << I.Name() << endl;
 866          Cache.MarkKeep(I);
 867          if (Cache[I].InstBroken() == false)
 868          {
 869             K = PList;
 870             continue;
 871          }
 872       }
 873
 874       // Isolate the problem dependencies
 875       for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false;)
 876       {
 877          // Compute a single dependency element (glob or)
 878          pkgCache::DepIterator Start = D;
 879          pkgCache::DepIterator End = D;
 880          unsigned char State = 0;
 881          for (bool LastOR = true; D.end() == false && LastOR == true; D++)
 882          {
 883             State |= Cache[D];
 884             LastOR = (D->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or;
 885             if (LastOR == true)
 886                End = D;
 887          }
 888
 889          // We only worry about critical deps.
 890          if (End.IsCritical() != true)
 891             continue;
 892
 893          // Dep is ok
 894          if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
 895             continue;
 896
 897          // Hm, the group is broken.. I have no idea how to handle this
 898          if (Start != End)
 899          {
 900             clog << "Note, a broken or group was found in " << I.Name() << "." << endl;
 901             if ((Flags[I->ID] & Protected) == 0)
 902                Cache.MarkKeep(I);
 903             break;
 904          }
 905
 906          if (Debug == true)
 907             clog << "Package " << I.Name() << " has broken dep on " << End.TargetPkg().Name() << endl;
 908
 909          // Look at all the possible provides on this package
 910          pkgCache::Version **VList = End.AllTargets();
 911          for (pkgCache::Version **V = VList; *V != 0; V++)
 912          {
 913             pkgCache::VerIterator Ver(Cache,*V);
 914             pkgCache::PkgIterator Pkg = Ver.ParentPkg();
 915
 916             // It is not keepable
 917             if (Cache[Pkg].InstallVer == 0 ||
 918                 Pkg->CurrentVer == 0)
 919                continue;
 920
 921             if ((Flags[I->ID] & Protected) == 0)
 922             {
 923                if (Debug == true)
 924                   clog << "  Keeping Package " << Pkg.Name() << " due to dep" << endl;
 925                Cache.MarkKeep(Pkg);
 926             }
 927
 928             if (Cache[I].InstBroken() == false)
 929                break;
 930          }
 931
 932          if (Cache[I].InstBroken() == false)
 933             break;
 934       }
 935
 936       if (Cache[I].InstBroken() == true)
 937          continue;
 938
 939       // Restart again.
 940       if (K == LastStop)
 941          return _error->Error("Internal Error, pkgProblemResolver::ResolveByKeep is looping on package %s.",I.Name());
 942       LastStop = K;
 943       K = PList;
 944    }
 945
 946    return true;
 947 }
 948                                                                         /*}}}*/
 949 // ProblemResolver::InstallProtect - Install all protected packages     /*{{{*/
 950 // ---------------------------------------------------------------------
 951 /* This is used to make sure protected packages are installed */
 952 void pkgProblemResolver::InstallProtect()
 953 {
 954    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 955    {
 956       if ((Flags[I->ID] & Protected) == Protected)
 957       {
 958          if ((Flags[I->ID] & ToRemove) == ToRemove)
 959             Cache.MarkDelete(I);
 960          else
 961             Cache.MarkInstall(I,false);
 962       }
 963    }
 964 }
 965                                                                         /*}}}*/