apt-pkg/algorithms.cc

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