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