apt-pkg/algorithms.cc

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