apt-pkg/algorithms.cc

   1 // -*- mode: cpp; mode: fold -*-
   2 // Description                                                          /*{{{*/
   3 // $Id: algorithms.cc,v 1.1 1998/07/07 04:17:00 jgg Exp $
   4 /* ######################################################################
   5
   6    Algorithms - A set of misc algorithms
   7
   8    ##################################################################### */
   9                                                                         /*}}}*/
  10 // Include Files                                                        /*{{{*/
  11 #ifdef __GNUG__
  12 #pragma implementation "pkglib/algorithms.h"
  13 #endif
  14 #include <pkglib/algorithms.h>
  15 #include <pkglib/error.h>
  16 #include <pkglib/pkgelement.h>
  17 #include <iostream.h>
  18                                                                         /*}}}*/
  19
  20 pkgProblemResolver *pkgProblemResolver::This = 0;
  21
  22 // Simulate::Simulate - Constructor                                     /*{{{*/
  23 // ---------------------------------------------------------------------
  24 /* */
  25 pkgSimulate::pkgSimulate(pkgDepCache &Cache) : pkgPackageManager(Cache),
  26                             Sim(true,true)
  27 {
  28    Flags = new unsigned char[Cache.HeaderP->PackageCount];
  29    memset(Flags,0,sizeof(*Flags)*Cache.HeaderP->PackageCount);
  30 }
  31                                                                         /*}}}*/
  32 // Simulate::Install - Simulate unpacking of a package                  /*{{{*/
  33 // ---------------------------------------------------------------------
  34 /* */
  35 bool pkgSimulate::Install(PkgIterator iPkg,string /*File*/)
  36 {
  37    // Adapt the iterator
  38    PkgIterator Pkg = Sim.FindPkg(iPkg.Name());
  39    Flags[Pkg->ID] = 1;
  40
  41    cout << "Inst " << Pkg.Name();
  42    Sim.MarkInstall(Pkg,false);
  43
  44    // Look for broken conflicts+predepends.
  45    for (PkgIterator I = Sim.PkgBegin(); I.end() == false; I++)
  46    {
  47       if (Sim[I].InstallVer == 0)
  48          continue;
  49
  50       for (DepIterator D = Sim[I].InstVerIter(Sim).DependsList(); D.end() == false; D++)
  51          if (D->Type == pkgDEP_Conflicts || D->Type == pkgDEP_PreDepends)
  52          {
  53             if ((Sim[D] & pkgDepCache::DepInstall) == 0)
  54             {
  55                cout << " [" << I.Name() << " on " << D.TargetPkg().Name() << ']';
  56                if (D->Type == pkgDEP_Conflicts)
  57                   _error->Error("Fatal, conflicts violated %s",I.Name());
  58             }
  59          }
  60    }
  61
  62    if (Sim.BrokenCount() != 0)
  63       ShortBreaks();
  64    else
  65       cout << endl;
  66    return true;
  67 }
  68                                                                         /*}}}*/
  69 // Simulate::Configure - Simulate configuration of a Package            /*{{{*/
  70 // ---------------------------------------------------------------------
  71 /* This is not an acurate simulation of relatity, we should really not
  72    install the package.. For some investigations it may be necessary
  73    however. */
  74 bool pkgSimulate::Configure(PkgIterator iPkg)
  75 {
  76    // Adapt the iterator
  77    PkgIterator Pkg = Sim.FindPkg(iPkg.Name());
  78
  79    Flags[Pkg->ID] = 2;
  80 //   Sim.MarkInstall(Pkg,false);
  81    if (Sim[Pkg].InstBroken() == true)
  82    {
  83       cout << "Conf " << Pkg.Name() << " broken" << endl;
  84
  85       Sim.Update();
  86
  87       // Print out each package and the failed dependencies
  88       for (pkgCache::DepIterator D = Sim[Pkg].InstVerIter(Sim).DependsList(); D.end() == false; D++)
  89       {
  90          if (Sim.IsImportantDep(D) == false ||
  91              (Sim[D] & pkgDepCache::DepInstall) != 0)
  92             continue;
  93
  94          if (D->Type == pkgDEP_Conflicts)
  95             cout << " Conflicts:" << D.TargetPkg().Name();
  96          else
  97             cout << " Depends:" << D.TargetPkg().Name();
  98       }
  99       cout << endl;
 100
 101       _error->Error("Conf Broken %s",Pkg.Name());
 102    }
 103    else
 104       cout << "Conf " <<  Pkg.Name();
 105
 106    if (Sim.BrokenCount() != 0)
 107       ShortBreaks();
 108    else
 109       cout << endl;
 110
 111    return true;
 112 }
 113                                                                         /*}}}*/
 114 // Simulate::Remove - Simulate the removal of a package                 /*{{{*/
 115 // ---------------------------------------------------------------------
 116 /* */
 117 bool pkgSimulate::Remove(PkgIterator iPkg)
 118 {
 119    // Adapt the iterator
 120    PkgIterator Pkg = Sim.FindPkg(iPkg.Name());
 121
 122    Flags[Pkg->ID] = 3;
 123    Sim.MarkDelete(Pkg);
 124    cout << "Remv " << Pkg.Name();
 125
 126    if (Sim.BrokenCount() != 0)
 127       ShortBreaks();
 128    else
 129       cout << endl;
 130
 131    return true;
 132 }
 133                                                                         /*}}}*/
 134 // Simulate::ShortBreaks - Print out a short line describing all breaks /*{{{*/
 135 // ---------------------------------------------------------------------
 136 /* */
 137 void pkgSimulate::ShortBreaks()
 138 {
 139    cout << " [";
 140    for (PkgIterator I = Sim.PkgBegin(); I.end() == false; I++)
 141    {
 142       if (Sim[I].InstBroken() == true)
 143       {
 144          if (Flags[I->ID] == 0)
 145             cout << I.Name() << ' ';
 146 /*       else
 147             cout << I.Name() << "! ";*/
 148       }
 149    }
 150    cout << ']' << endl;
 151 }
 152                                                                         /*}}}*/
 153 // ApplyStatus - Adjust for non-ok packages                             /*{{{*/
 154 // ---------------------------------------------------------------------
 155 /* We attempt to change the state of the all packages that have failed
 156    installation toward their real state. The ordering code will perform
 157    the necessary calculations to deal with the problems. */
 158 bool pkgApplyStatus(pkgDepCache &Cache)
 159 {
 160    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 161    {
 162       switch (I->CurrentState)
 163       {
 164          // This means installation failed somehow
 165          case pkgSTATE_UnPacked:
 166          case pkgSTATE_HalfConfigured:
 167          Cache.MarkKeep(I);
 168          break;
 169
 170          // This means removal failed
 171          case pkgSTATE_HalfInstalled:
 172          Cache.MarkDelete(I);
 173          break;
 174
 175          default:
 176          if (I->InstState != pkgSTATE_Ok)
 177             return _error->Error("The package %s is not ok and I "
 178                                  "don't know how to fix it!",I.Name());
 179       }
 180    }
 181    return true;
 182 }
 183                                                                         /*}}}*/
 184 // FixBroken - Fix broken packages                                      /*{{{*/
 185 // ---------------------------------------------------------------------
 186 /* This autoinstalls every broken package and then runs ScoredFix on the
 187    result. */
 188 bool pkgFixBroken(pkgDepCache &Cache)
 189 {
 190    // Auto upgrade all broken packages
 191    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 192       if (Cache[I].NowBroken() == true)
 193          Cache.MarkInstall(I,true);
 194
 195    /* Fix packages that are in a NeedArchive state but don't have a
 196       downloadable install version */
 197    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 198    {
 199       if (I.State() != pkgCache::PkgIterator::NeedsUnpack ||
 200           Cache[I].Delete() == true)
 201          continue;
 202
 203       if ((Cache[I].InstVerIter(Cache).File()->Flags & pkgFLAG_NotSource) == 0)
 204          continue;
 205
 206       Cache.MarkInstall(I,true);
 207    }
 208
 209    pkgProblemResolver Fix(Cache);
 210    return Fix.Resolve(true);
 211 }
 212                                                                         /*}}}*/
 213 // DistUpgrade - Distribution upgrade                                   /*{{{*/
 214 // ---------------------------------------------------------------------
 215 /* This autoinstalls every package and then force installs every
 216    pre-existing package. This creates the initial set of conditions which
 217    most likely contain problems because too many things were installed.
 218
 219    ScoredFix is used to resolve the problems.
 220  */
 221 bool pkgDistUpgrade(pkgDepCache &Cache)
 222 {
 223    /* Auto upgrade all installed packages, this provides the basis
 224       for the installation */
 225    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 226       if (I->CurrentVer != 0)
 227          Cache.MarkInstall(I,true);
 228
 229    /* Now, auto upgrade all essential packages - this ensures that
 230       the essential packages are present and working */
 231    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 232       if ((I->Flags & pkgFLAG_Essential) == pkgFLAG_Essential)
 233          Cache.MarkInstall(I,true);
 234
 235    /* We do it again over all previously installed packages to force
 236       conflict resolution on them all. */
 237    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 238       if (I->CurrentVer != 0)
 239          Cache.MarkInstall(I,false);
 240
 241    pkgProblemResolver Fix(Cache);
 242
 243    // Hold back held packages.
 244    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 245    {
 246       if (I->SelectedState == pkgSTATE_Hold)
 247       {
 248          Fix.Protect(I);
 249          Cache.MarkKeep(I);
 250       }
 251    }
 252
 253    return Fix.Resolve();
 254 }
 255                                                                         /*}}}*/
 256
 257 // ProblemResolver::pkgProblemResolver - Constructor                    /*{{{*/
 258 // ---------------------------------------------------------------------
 259 /* */
 260 pkgProblemResolver::pkgProblemResolver(pkgDepCache &Cache) : Cache(Cache)
 261 {
 262    // Allocate memory
 263    unsigned long Size = Cache.HeaderP->PackageCount;
 264    Scores = new signed short[Size];
 265    Flags = new unsigned char[Size];
 266    memset(Flags,0,sizeof(*Flags)*Size);
 267
 268    // Set debug to true to see its decision logic
 269    Debug = false;
 270 }
 271                                                                         /*}}}*/
 272 // ProblemResolver::ScoreSort - Sort the list by score                  /*{{{*/
 273 // ---------------------------------------------------------------------
 274 /* */
 275 int pkgProblemResolver::ScoreSort(const void *a,const void *b)
 276 {
 277    Package const **A = (Package const **)a;
 278    Package const **B = (Package const **)b;
 279    if (This->Scores[(*A)->ID] > This->Scores[(*B)->ID])
 280       return -1;
 281    if (This->Scores[(*A)->ID] < This->Scores[(*B)->ID])
 282       return 1;
 283    return 0;
 284 }
 285                                                                         /*}}}*/
 286 // ProblemResolver::MakeScores - Make the score table                   /*{{{*/
 287 // ---------------------------------------------------------------------
 288 /* */
 289 void pkgProblemResolver::MakeScores()
 290 {
 291    unsigned long Size = Cache.HeaderP->PackageCount;
 292    memset(Scores,0,sizeof(*Scores)*Size);
 293
 294    // Generate the base scores for a package based on its properties
 295    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 296    {
 297       if (Cache[I].InstallVer == 0)
 298          continue;
 299
 300       signed short &Score = Scores[I->ID];
 301
 302       /* This is arbitary, it should be high enough to elevate an
 303          essantial package above most other packages but low enough
 304          to allow an obsolete essential packages to be removed by
 305          a conflicts on a powerfull normal package (ie libc6) */
 306       if ((I->Flags & pkgFLAG_Essential) == pkgFLAG_Essential)
 307          Score += 100;
 308
 309       // We transform the priority
 310       // Important Required Standard Optional Extra
 311       signed short PrioMap[] = {0,3,2,1,-1,-2};
 312       if (Cache[I].InstVerIter(Cache)->Priority <= 5)
 313          Score += PrioMap[Cache[I].InstVerIter(Cache)->Priority];
 314
 315       /* This helps to fix oddball problems with conflicting packages
 316          on the same level. We enhance the score of installed packages */
 317       if (I->CurrentVer != 0)
 318          Score += 1;
 319    }
 320
 321    // Now that we have the base scores we go and propogate dependencies
 322    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 323    {
 324       if (Cache[I].InstallVer == 0)
 325          continue;
 326
 327       for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false; D++)
 328       {
 329          if (D->Type == pkgDEP_Depends || D->Type == pkgDEP_PreDepends)
 330             Scores[D.TargetPkg()->ID]++;
 331       }
 332    }
 333
 334    // Copy the scores to advoid additive looping
 335    signed short *OldScores = new signed short[Size];
 336    memcpy(OldScores,Scores,sizeof(*Scores)*Size);
 337
 338    /* Now we cause 1 level of dependency inheritance, that is we add the
 339       score of the packages that depend on the target Package. This
 340       fortifies high scoring packages */
 341    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 342    {
 343       if (Cache[I].InstallVer == 0)
 344          continue;
 345
 346       for (pkgCache::DepIterator D = I.RevDependsList(); D.end() == false; D++)
 347       {
 348          // Only do it for the install version
 349          if ((pkgCache::Version *)D.ParentVer() != Cache[D.ParentPkg()].InstallVer ||
 350              (D->Type != pkgDEP_Depends && D->Type != pkgDEP_PreDepends))
 351             continue;
 352
 353          Scores[I->ID] += abs(OldScores[D.ParentPkg()->ID]);
 354       }
 355    }
 356
 357    /* Now we propogate along provides. This makes the packages that
 358       provide important packages extremely important */
 359    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 360    {
 361       for (pkgCache::PrvIterator P = I.ProvidesList(); P.end() == false; P++)
 362       {
 363          // Only do it once per package
 364          if ((pkgCache::Version *)P.OwnerVer() != Cache[P.OwnerPkg()].InstallVer)
 365             continue;
 366          Scores[P.OwnerPkg()->ID] += abs(Scores[I->ID] - OldScores[I->ID]);
 367       }
 368    }
 369
 370    /* Protected things are pushed really high up. This number should put them
 371       ahead of everything */
 372    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 373       if ((Flags[I->ID] & Protected) != 0)
 374          Scores[I->ID] += 10000;
 375
 376    delete [] OldScores;
 377 }
 378                                                                         /*}}}*/
 379 // ProblemResolver::DoUpgrade - Attempt to upgrade this package         /*{{{*/
 380 // ---------------------------------------------------------------------
 381 /* This goes through and tries to reinstall packages to make this package
 382    installable */
 383 bool pkgProblemResolver::DoUpgrade(pkgCache::PkgIterator Pkg)
 384 {
 385    if ((Flags[Pkg->ID] & Upgradable) == 0 || Cache[Pkg].Upgradable() == false)
 386       return false;
 387    Flags[Pkg->ID] &= ~Upgradable;
 388
 389    bool WasKept = Cache[Pkg].Keep();
 390    Cache.MarkInstall(Pkg,false);
 391
 392    // Isolate the problem dependency
 393    bool Fail = false;
 394    for (pkgCache::DepIterator D = Cache[Pkg].InstVerIter(Cache).DependsList(); D.end() == false;)
 395    {
 396       // Compute a single dependency element (glob or)
 397       pkgCache::DepIterator Start = D;
 398       pkgCache::DepIterator End = D;
 399       unsigned char State = 0;
 400       for (bool LastOR = true; D.end() == false && LastOR == true; D++)
 401       {
 402          State |= Cache[D];
 403          LastOR = (D->CompareOp & pkgOP_OR) == pkgOP_OR;
 404          if (LastOR == true)
 405             End = D;
 406       }
 407
 408       // We only worry about critical deps.
 409       if (End.IsCritical() != true)
 410          continue;
 411
 412       // Dep is ok
 413       if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
 414          continue;
 415
 416       // Hm, the group is broken.. I have no idea how to handle this
 417       if (Start != End)
 418       {
 419          cout << "Note, a broken or group was found in " << Pkg.Name() << "." << endl;
 420          Fail = true;
 421          break;
 422       }
 423
 424       // Upgrade the package if the candidate version will fix the problem.
 425       if ((Cache[Start] & pkgDepCache::DepCVer) == pkgDepCache::DepCVer)
 426       {
 427          PkgIterator P = Start.SmartTargetPkg();
 428          if (DoUpgrade(P) == false)
 429          {
 430             if (Debug == true)
 431                cout << "    Reinst Failed because of " << P.Name() << endl;
 432             Fail = true;
 433             break;
 434          }
 435       }
 436       else
 437       {
 438          /* We let the algorithm deal with conflicts on its next iteration,
 439             it is much smarter than us */
 440          if (End->Type == pkgDEP_Conflicts)
 441             continue;
 442
 443          if (Debug == true)
 444             cout << "    Reinst Failed early because of " << Start.TargetPkg().Name() << endl;
 445          Fail = true;
 446          break;
 447       }
 448    }
 449
 450    // Undo our operations - it might be smart to undo everything this did..
 451    if (Fail == true)
 452    {
 453       if (WasKept == true)
 454          Cache.MarkKeep(Pkg);
 455       else
 456          Cache.MarkDelete(Pkg);
 457       return false;
 458    }
 459
 460    if (Debug == true)
 461       cout << "  Re-Instated " << Pkg.Name() << endl;
 462    return true;
 463 }
 464                                                                         /*}}}*/
 465 // ProblemResolver::Resolve - Run the resolution pass                   /*{{{*/
 466 // ---------------------------------------------------------------------
 467 /* This routines works by calculating a score for each package. The score
 468    is derived by considering the package's priority and all reverse
 469    dependents giving an integer that reflects the amount of breakage that
 470    adjusting the package will inflict.
 471
 472    It goes from highest score to lowest and corrects all of the breaks by
 473    keeping or removing the dependant packages. If that fails then it removes
 474    the package itself and goes on. The routine should be able to intelligently
 475    go from any broken state to a fixed state.
 476
 477    The BrokenFix flag enables a mode where the algorithm tries to
 478    upgrade packages to advoid problems. */
 479 bool pkgProblemResolver::Resolve(bool BrokenFix)
 480 {
 481  unsigned long Size = Cache.HeaderP->PackageCount;
 482
 483    // Record which packages are marked for install
 484    bool Again = false;
 485    do
 486    {
 487       Again = false;
 488       for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 489       {
 490          if (Cache[I].Install() == true)
 491             Flags[I->ID] |= PreInstalled;
 492          else
 493          {
 494             if (Cache[I].InstBroken() == true && BrokenFix == true)
 495             {
 496                Cache.MarkInstall(I,false);
 497                if (Cache[I].Install() == true)
 498                   Again = true;
 499             }
 500
 501             Flags[I->ID] &= ~PreInstalled;
 502          }
 503          Flags[I->ID] |= Upgradable;
 504       }
 505    }
 506    while (Again == true);
 507
 508    if (Debug == true)
 509       cout << "Starting" << endl;
 510
 511    MakeScores();
 512
 513    /* We have to order the packages so that the broken fixing pass
 514       operates from highest score to lowest. This prevents problems when
 515       high score packages cause the removal of lower score packages that
 516       would cause the removal of even lower score packages. */
 517    pkgCache::Package **PList = new pkgCache::Package *[Size];
 518    pkgCache::Package **PEnd = PList;
 519    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 520       *PEnd++ = I;
 521    This = this;
 522    qsort(PList,PEnd - PList,sizeof(*PList),&ScoreSort);
 523
 524 /* for (pkgCache::Package **K = PList; K != PEnd; K++)
 525       if (Scores[(*K)->ID] != 0)
 526       {
 527          pkgCache::PkgIterator Pkg(Cache,*K);
 528          cout << Scores[(*K)->ID] << ' ' << Pkg.Name() <<
 529             ' ' << (pkgCache::Version *)Pkg.CurrentVer() << ' ' <<
 530             Cache[Pkg].InstallVer << ' ' << Cache[Pkg].CandidateVer << endl;
 531       } */
 532
 533    if (Debug == true)
 534       cout << "Starting 2" << endl;
 535
 536    /* Now consider all broken packages. For each broken package we either
 537       remove the package or fix it's problem. We do this once, it should
 538       not be possible for a loop to form (that is a < b < c and fixing b by
 539       changing a breaks c) */
 540    bool Change = true;
 541    for (int Counter = 0; Counter != 10 && Change == true; Counter++)
 542    {
 543       Change = false;
 544       for (pkgCache::Package **K = PList; K != PEnd; K++)
 545       {
 546          pkgCache::PkgIterator I(Cache,*K);
 547
 548          /* We attempt to install this and see if any breaks result,
 549             this takes care of some strange cases */
 550          if (Cache[I].CandidateVer != Cache[I].InstallVer &&
 551              I->CurrentVer != 0 && Cache[I].InstallVer != 0 &&
 552              (Flags[I->ID] & PreInstalled) != 0 &&
 553              (Flags[I->ID] & Protected) == 0)
 554          {
 555             if (Debug == true)
 556                cout << " Try to Re-Instate " << I.Name() << endl;
 557             int OldBreaks = Cache.BrokenCount();
 558             pkgCache::Version *OldVer = Cache[I].InstallVer;
 559
 560             Cache.MarkInstall(I,false);
 561             if (Cache[I].InstBroken() == true ||
 562                 OldBreaks < Cache.BrokenCount())
 563             {
 564                if (OldVer == 0)
 565                   Cache.MarkDelete(I);
 566                else
 567                   Cache.MarkKeep(I);
 568             }
 569             else
 570                if (Debug == true)
 571                   cout << "Re-Instated " << I.Name() << endl;
 572          }
 573
 574          if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false)
 575             continue;
 576
 577          // Isolate the problem dependency
 578          PackageKill KillList[100];
 579          PackageKill *LEnd = KillList;
 580          for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false;)
 581          {
 582             // Compute a single dependency element (glob or)
 583             pkgCache::DepIterator Start = D;
 584             pkgCache::DepIterator End = D;
 585             unsigned char State = 0;
 586             for (bool LastOR = true; D.end() == false && LastOR == true; D++)
 587             {
 588                State |= Cache[D];
 589                LastOR = (D->CompareOp & pkgOP_OR) == pkgOP_OR;
 590                if (LastOR == true)
 591                   End = D;
 592             }
 593
 594             // We only worry about critical deps.
 595             if (End.IsCritical() != true)
 596                continue;
 597
 598             // Dep is ok
 599             if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
 600                continue;
 601
 602             // Hm, the group is broken.. I have no idea how to handle this
 603             if (Start != End)
 604             {
 605                cout << "Note, a broken or group was found in " << I.Name() << "." << endl;
 606                Cache.MarkDelete(I);
 607                break;
 608             }
 609
 610             if (Debug == true)
 611                cout << "Package " << I.Name() << " has broken dep on " << End.TargetPkg().Name() << endl;
 612
 613             /* Conflicts is simple, decide if we should remove this package
 614                or the conflicted one */
 615             pkgCache::Version **VList = End.AllTargets();
 616             bool Done = false;
 617             for (pkgCache::Version **V = VList; *V != 0; V++)
 618             {
 619                pkgCache::VerIterator Ver(Cache,*V);
 620                pkgCache::PkgIterator Pkg = Ver.ParentPkg();
 621
 622                if (Debug == true)
 623                   cout << "  Considering " << Pkg.Name() << ' ' << (int)Scores[Pkg->ID] <<
 624                   " as a solution to " << I.Name() << ' ' << (int)Scores[I->ID] << endl;
 625                if (Scores[I->ID] <= Scores[Pkg->ID] ||
 626                    ((Cache[End] & pkgDepCache::DepGNow) == 0 &&
 627                     End->Type != pkgDEP_Conflicts))
 628                {
 629                   if ((Flags[I->ID] & Protected) != 0)
 630                      continue;
 631
 632                   // See if a keep will do
 633                   Cache.MarkKeep(I);
 634                   if (Cache[I].InstBroken() == false)
 635                   {
 636                      if (Debug == true)
 637                         cout << "  Holding Back " << I.Name() << " rather than change " << End.TargetPkg().Name() << endl;
 638                   }
 639                   else
 640                   {
 641                      if (BrokenFix == false || DoUpgrade(I) == false)
 642                      {
 643                         if (Debug == true)
 644                            cout << "  Removing " << I.Name() << " rather than change " << End.TargetPkg().Name() << endl;
 645                         Cache.MarkDelete(I);
 646                         if (Counter > 1)
 647                            Scores[I->ID] = Scores[Pkg->ID];
 648                      }
 649                   }
 650
 651                   Change = true;
 652                   Done = true;
 653                   break;
 654                }
 655                else
 656                {
 657                   // Skip this if it is protected
 658                   if ((Flags[Pkg->ID] & Protected) != 0)
 659                      continue;
 660
 661                   LEnd->Pkg = Pkg;
 662                   LEnd->Dep = End;
 663                   LEnd++;
 664                   if (End->Type != pkgDEP_Conflicts)
 665                      break;
 666                }
 667             }
 668
 669             // Hm, nothing can possibly satisify this dep. Nuke it.
 670             if (VList[0] == 0 && End->Type != pkgDEP_Conflicts)
 671             {
 672                Cache.MarkKeep(I);
 673                if (Cache[I].InstBroken() == false)
 674                {
 675                   if (Debug == true)
 676                      cout << "  Holding Back " << I.Name() << " because I can't find " << End.TargetPkg().Name() << endl;
 677                }
 678                else
 679                {
 680                   if (Debug == true)
 681                      cout << "  Removing " << I.Name() << " because I can't find " << End.TargetPkg().Name() << endl;
 682                   Cache.MarkDelete(I);
 683                }
 684
 685                Change = true;
 686                Done = true;
 687             }
 688
 689             delete [] VList;
 690             if (Done == true)
 691                break;
 692          }
 693
 694          // Apply the kill list now
 695          if (Cache[I].InstallVer != 0)
 696             for (PackageKill *J = KillList; J != LEnd; J++)
 697          {
 698             Change = true;
 699             if ((Cache[J->Dep] & pkgDepCache::DepGNow) == 0)
 700             {
 701                if (J->Dep->Type == pkgDEP_Conflicts)
 702                {
 703                   if (Debug == true)
 704                      cout << "  Fixing " << I.Name() << " via remove of " << J->Pkg.Name() << endl;
 705                   Cache.MarkDelete(J->Pkg);
 706                }
 707             }
 708             else
 709             {
 710                if (Debug == true)
 711                   cout << "  Fixing " << I.Name() << " via keep of " << J->Pkg.Name() << endl;
 712                Cache.MarkKeep(J->Pkg);
 713             }
 714
 715             if (Counter > 1)
 716                Scores[J->Pkg->ID] = Scores[I->ID];
 717          }
 718       }
 719    }
 720
 721    if (Debug == true)
 722       cout << "Done" << endl;
 723
 724    delete [] Scores;
 725    delete [] PList;
 726
 727    if (Cache.BrokenCount() != 0)
 728       return _error->Error("Internal error, ScoredFix generated breaks.");
 729
 730    return true;
 731 }
 732                                                                         /*}}}*/