apt-pkg/algorithms.cc

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