apt-pkg/algorithms.cc

   1 // -*- mode: cpp; mode: fold -*-
   2 // Description                                                          /*{{{*/
   3 // $Id: algorithms.cc,v 1.26 1999/10/22 04:05:47 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                   continue;
 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                      Cache.MarkDelete(I);
 742                   if (OldEnd == LEnd && OrOp == OrKeep)
 743                      Cache.MarkKeep(I);
 744                }
 745
 746                OrOp = OrRemove;
 747                D.GlobOr(Start,End);
 748                InOr = Start != End;
 749                OldEnd = LEnd;
 750             }
 751             else
 752                Start++;
 753
 754             // We only worry about critical deps.
 755             if (End.IsCritical() != true)
 756                continue;
 757
 758             // Dep is ok
 759             if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
 760                continue;
 761
 762             if (Debug == true)
 763                clog << "Package " << I.Name() << " has broken dep on " << Start.TargetPkg().Name() << endl;
 764
 765             /* Look across the version list. If there are no possible
 766                targets then we keep the package and bail. This is necessary
 767                if a package has a dep on another package that cant be found */
 768             pkgCache::Version **VList = Start.AllTargets();
 769             if (*VList == 0 && (Flags[I->ID] & Protected) != Protected &&
 770                 Start->Type != pkgCache::Dep::Conflicts &&
 771                 Cache[I].NowBroken() == false)
 772             {
 773                if (InOr == true)
 774                {
 775                   /* No keep choice because the keep being OK could be the
 776                      result of another element in the OR group! */
 777                   continue;
 778                }
 779
 780                Change = true;
 781                Cache.MarkKeep(I);
 782                break;
 783             }
 784
 785             bool Done = false;
 786             for (pkgCache::Version **V = VList; *V != 0; V++)
 787             {
 788                pkgCache::VerIterator Ver(Cache,*V);
 789                pkgCache::PkgIterator Pkg = Ver.ParentPkg();
 790
 791                if (Debug == true)
 792                   clog << "  Considering " << Pkg.Name() << ' ' << (int)Scores[Pkg->ID] <<
 793                   " as a solution to " << I.Name() << ' ' << (int)Scores[I->ID] << endl;
 794                if (Scores[I->ID] <= Scores[Pkg->ID] ||
 795                    ((Cache[Start] & pkgDepCache::DepNow) == 0 &&
 796                     End->Type != pkgCache::Dep::Conflicts))
 797                {
 798                   // Try a little harder to fix protected packages..
 799                   if ((Flags[I->ID] & Protected) == Protected)
 800                   {
 801                      if (DoUpgrade(Pkg) == true)
 802                         Scores[Pkg->ID] = Scores[I->ID];
 803                      continue;
 804                   }
 805
 806                   /* See if a keep will do, unless the package is protected,
 807                      then installing it will be necessary */
 808                   bool Installed = Cache[I].Install();
 809                   Cache.MarkKeep(I);
 810                   if (Cache[I].InstBroken() == false)
 811                   {
 812                      // Unwind operation will be keep now
 813                      if (OrOp == OrRemove)
 814                         OrOp = OrKeep;
 815
 816                      // Restore
 817                      if (InOr == true && Installed == true)
 818                         Cache.MarkInstall(I,false);
 819
 820                      if (Debug == true)
 821                         clog << "  Holding Back " << I.Name() << " rather than change " << Start.TargetPkg().Name() << endl;
 822                   }
 823                   else
 824                   {
 825                      if (BrokenFix == false || DoUpgrade(I) == false)
 826                      {
 827                         // Consider other options
 828                         if (InOr == false)
 829                         {
 830                            if (Debug == true)
 831                               clog << "  Removing " << I.Name() << " rather than change " << Start.TargetPkg().Name() << endl;
 832                            Cache.MarkDelete(I);
 833                            if (Counter > 1)
 834                               Scores[I->ID] = Scores[Pkg->ID];
 835                         }
 836                      }
 837                   }
 838
 839                   Change = true;
 840                   Done = true;
 841                   break;
 842                }
 843                else
 844                {
 845                   // Skip adding to the kill list if it is protected
 846                   if ((Flags[Pkg->ID] & Protected) != 0)
 847                      continue;
 848
 849                   LEnd->Pkg = Pkg;
 850                   LEnd->Dep = End;
 851                   LEnd++;
 852
 853                   if (Start->Type != pkgCache::Dep::Conflicts)
 854                      break;
 855                }
 856             }
 857
 858             // Hm, nothing can possibly satisify this dep. Nuke it.
 859             if (VList[0] == 0 && Start->Type != pkgCache::Dep::Conflicts &&
 860                 (Flags[I->ID] & Protected) != Protected)
 861             {
 862                bool Installed = Cache[I].Install();
 863                Cache.MarkKeep(I);
 864                if (Cache[I].InstBroken() == false)
 865                {
 866                   // Unwind operation will be keep now
 867                   if (OrOp == OrRemove)
 868                      OrOp = OrKeep;
 869
 870                   // Restore
 871                   if (InOr == true && Installed == true)
 872                      Cache.MarkInstall(I,false);
 873
 874                   if (Debug == true)
 875                      clog << "  Holding Back " << I.Name() << " because I can't find " << Start.TargetPkg().Name() << endl;
 876                }
 877                else
 878                {
 879                   if (Debug == true)
 880                      clog << "  Removing " << I.Name() << " because I can't find " << Start.TargetPkg().Name() << endl;
 881                   if (InOr == false)
 882                      Cache.MarkDelete(I);
 883                }
 884
 885                Change = true;
 886                Done = true;
 887             }
 888
 889             delete [] VList;
 890
 891             // Try some more
 892             if (InOr == true)
 893                continue;
 894
 895             if (Done == true)
 896                break;
 897          }
 898
 899          // Apply the kill list now
 900          if (Cache[I].InstallVer != 0)
 901          {
 902             for (PackageKill *J = KillList; J != LEnd; J++)
 903             {
 904                Change = true;
 905                if ((Cache[J->Dep] & pkgDepCache::DepGNow) == 0)
 906                {
 907                   if (J->Dep->Type == pkgCache::Dep::Conflicts)
 908                   {
 909                      if (Debug == true)
 910                         clog << "  Fixing " << I.Name() << " via remove of " << J->Pkg.Name() << endl;
 911                      Cache.MarkDelete(J->Pkg);
 912                   }
 913                }
 914                else
 915                {
 916                   if (Debug == true)
 917                      clog << "  Fixing " << I.Name() << " via keep of " << J->Pkg.Name() << endl;
 918                   Cache.MarkKeep(J->Pkg);
 919                }
 920
 921                if (Counter > 1)
 922                   Scores[J->Pkg->ID] = Scores[I->ID];
 923             }
 924          }
 925       }
 926    }
 927
 928    if (Debug == true)
 929       clog << "Done" << endl;
 930
 931    delete [] Scores;
 932    delete [] PList;
 933
 934    if (Cache.BrokenCount() != 0)
 935    {
 936       // See if this is the result of a hold
 937       pkgCache::PkgIterator I = Cache.PkgBegin();
 938       for (;I.end() != true; I++)
 939       {
 940          if (Cache[I].InstBroken() == false)
 941             continue;
 942          if ((Flags[I->ID] & Protected) != Protected)
 943             return _error->Error("Error, pkgProblemResolver::Resolve generated breaks, this may be caused by held packages.");
 944       }
 945       return _error->Error("Unable to correct problems, you have held broken packages.");
 946    }
 947
 948    return true;
 949 }
 950                                                                         /*}}}*/
 951 // ProblemResolver::ResolveByKeep - Resolve problems using keep         /*{{{*/
 952 // ---------------------------------------------------------------------
 953 /* This is the work horse of the soft upgrade routine. It is very gental
 954    in that it does not install or remove any packages. It is assumed that the
 955    system was non-broken previously. */
 956 bool pkgProblemResolver::ResolveByKeep()
 957 {
 958    unsigned long Size = Cache.HeaderP->PackageCount;
 959
 960    if (Debug == true)
 961       clog << "Entering ResolveByKeep" << endl;
 962
 963    MakeScores();
 964
 965    /* We have to order the packages so that the broken fixing pass
 966       operates from highest score to lowest. This prevents problems when
 967       high score packages cause the removal of lower score packages that
 968       would cause the removal of even lower score packages. */
 969    pkgCache::Package **PList = new pkgCache::Package *[Size];
 970    pkgCache::Package **PEnd = PList;
 971    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 972       *PEnd++ = I;
 973    This = this;
 974    qsort(PList,PEnd - PList,sizeof(*PList),&ScoreSort);
 975
 976    // Consider each broken package
 977    pkgCache::Package **LastStop = 0;
 978    for (pkgCache::Package **K = PList; K != PEnd; K++)
 979    {
 980       pkgCache::PkgIterator I(Cache,*K);
 981
 982       if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false)
 983          continue;
 984
 985       /* Keep the package. If this works then great, otherwise we have
 986          to be significantly more agressive and manipulate its dependencies */
 987       if ((Flags[I->ID] & Protected) == 0)
 988       {
 989          if (Debug == true)
 990             clog << "Keeping package " << I.Name() << endl;
 991          Cache.MarkKeep(I);
 992          if (Cache[I].InstBroken() == false)
 993          {
 994             K = PList;
 995             continue;
 996          }
 997       }
 998
 999       // Isolate the problem dependencies
1000       for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false;)
1001       {
1002          // Compute a single dependency element (glob or)
1003          pkgCache::DepIterator Start = D;
1004          pkgCache::DepIterator End = D;
1005          unsigned char State = 0;
1006          for (bool LastOR = true; D.end() == false && LastOR == true; D++)
1007          {
1008             State |= Cache[D];
1009             LastOR = (D->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or;
1010             if (LastOR == true)
1011                End = D;
1012          }
1013
1014          // We only worry about critical deps.
1015          if (End.IsCritical() != true)
1016             continue;
1017
1018          // Dep is ok
1019          if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
1020             continue;
1021
1022          // Hm, the group is broken.. I have no idea how to handle this
1023          if (Start != End)
1024          {
1025             clog << "Note, a broken or group was found in " << I.Name() << "." << endl;
1026             if ((Flags[I->ID] & Protected) == 0)
1027                Cache.MarkKeep(I);
1028             break;
1029          }
1030
1031          if (Debug == true)
1032             clog << "Package " << I.Name() << " has broken dep on " << End.TargetPkg().Name() << endl;
1033
1034          // Look at all the possible provides on this package
1035          pkgCache::Version **VList = End.AllTargets();
1036          for (pkgCache::Version **V = VList; *V != 0; V++)
1037          {
1038             pkgCache::VerIterator Ver(Cache,*V);
1039             pkgCache::PkgIterator Pkg = Ver.ParentPkg();
1040
1041             // It is not keepable
1042             if (Cache[Pkg].InstallVer == 0 ||
1043                 Pkg->CurrentVer == 0)
1044                continue;
1045
1046             if ((Flags[I->ID] & Protected) == 0)
1047             {
1048                if (Debug == true)
1049                   clog << "  Keeping Package " << Pkg.Name() << " due to dep" << endl;
1050                Cache.MarkKeep(Pkg);
1051             }
1052
1053             if (Cache[I].InstBroken() == false)
1054                break;
1055          }
1056
1057          if (Cache[I].InstBroken() == false)
1058             break;
1059       }
1060
1061       if (Cache[I].InstBroken() == true)
1062          continue;
1063
1064       // Restart again.
1065       if (K == LastStop)
1066          return _error->Error("Internal Error, pkgProblemResolver::ResolveByKeep is looping on package %s.",I.Name());
1067       LastStop = K;
1068       K = PList;
1069    }
1070
1071    return true;
1072 }
1073                                                                         /*}}}*/
1074 // ProblemResolver::InstallProtect - Install all protected packages     /*{{{*/
1075 // ---------------------------------------------------------------------
1076 /* This is used to make sure protected packages are installed */
1077 void pkgProblemResolver::InstallProtect()
1078 {
1079    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
1080    {
1081       if ((Flags[I->ID] & Protected) == Protected)
1082       {
1083          if ((Flags[I->ID] & ToRemove) == ToRemove)
1084             Cache.MarkDelete(I);
1085          else
1086             Cache.MarkInstall(I,false);
1087       }
1088    }
1089 }
1090                                                                         /*}}}*/