apt-pkg/algorithms.cc

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