apt-pkg/algorithms.cc

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