apt-pkg/algorithms.cc

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