apt-pkg/algorithms.cc

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