apt-pkg/algorithms.cc

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