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             cout << "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                      continue;
 990                   }
 991
 992                   // Skip adding to the kill list if it is protected
 993                   if ((Flags[Pkg->ID] & Protected) != 0)
 994                      continue;
 995
 996                   if (Debug == true)
 997                      clog << "  Added " << Pkg.Name() << " to the remove list" << endl;
 998
 999                   LEnd->Pkg = Pkg;
1000                   LEnd->Dep = End;
1001                   LEnd++;
1002
1003                   if (Start->Type != pkgCache::Dep::Conflicts &&
1004                       Start->Type != pkgCache::Dep::Obsoletes)
1005                      break;
1006                }
1007             }
1008
1009             // Hm, nothing can possibly satisify this dep. Nuke it.
1010             if (VList[0] == 0 &&
1011                 Start->Type != pkgCache::Dep::Conflicts &&
1012                 Start->Type != pkgCache::Dep::DpkgBreaks &&
1013                 Start->Type != pkgCache::Dep::Obsoletes &&
1014                 (Flags[I->ID] & Protected) != Protected)
1015             {
1016                bool Installed = Cache[I].Install();
1017                Cache.MarkKeep(I);
1018                if (Cache[I].InstBroken() == false)
1019                {
1020                   // Unwind operation will be keep now
1021                   if (OrOp == OrRemove)
1022                      OrOp = OrKeep;
1023
1024                   // Restore
1025                   if (InOr == true && Installed == true)
1026                      Cache.MarkInstall(I, false, 0, false);
1027
1028                   if (Debug == true)
1029                      clog << "  Holding Back " << I.Name() << " because I can't find " << Start.TargetPkg().Name() << endl;
1030                }
1031                else
1032                {
1033                   if (Debug == true)
1034                      clog << "  Removing " << I.Name() << " because I can't find " << Start.TargetPkg().Name() << endl;
1035                   if (InOr == false)
1036                      Cache.MarkDelete(I);
1037                }
1038
1039                Change = true;
1040                Done = true;
1041             }
1042
1043             // Try some more
1044             if (InOr == true)
1045                continue;
1046
1047             if (Done == true)
1048                break;
1049          }
1050
1051          // Apply the kill list now
1052          if (Cache[I].InstallVer != 0)
1053          {
1054             for (PackageKill *J = KillList; J != LEnd; J++)
1055             {
1056                Change = true;
1057                if ((Cache[J->Dep] & pkgDepCache::DepGNow) == 0)
1058                {
1059                   if (J->Dep->Type == pkgCache::Dep::Conflicts ||
1060                       J->Dep->Type == pkgCache::Dep::Obsoletes)
1061                   {
1062                      if (Debug == true)
1063                         clog << "  Fixing " << I.Name() << " via remove of " << J->Pkg.Name() << endl;
1064                      Cache.MarkDelete(J->Pkg);
1065                   }
1066                }
1067                else
1068                {
1069                   if (Debug == true)
1070                      clog << "  Fixing " << I.Name() << " via keep of " << J->Pkg.Name() << endl;
1071                   Cache.MarkKeep(J->Pkg, false, false);
1072                }
1073
1074                if (Counter > 1)
1075                {
1076                   if (Scores[I->ID] > Scores[J->Pkg->ID])
1077                      Scores[J->Pkg->ID] = Scores[I->ID];
1078                }
1079             }
1080          }
1081       }
1082    }
1083
1084    if (Debug == true)
1085       clog << "Done" << endl;
1086
1087    if (Cache.BrokenCount() != 0)
1088    {
1089       // See if this is the result of a hold
1090       pkgCache::PkgIterator I = Cache.PkgBegin();
1091       for (;I.end() != true; I++)
1092       {
1093          if (Cache[I].InstBroken() == false)
1094             continue;
1095          if ((Flags[I->ID] & Protected) != Protected)
1096             return _error->Error(_("Error, pkgProblemResolver::Resolve generated breaks, this may be caused by held packages."));
1097       }
1098       return _error->Error(_("Unable to correct problems, you have held broken packages."));
1099    }
1100
1101    // set the auto-flags (mvo: I'm not sure if we _really_ need this, but
1102    // I didn't managed
1103    pkgCache::PkgIterator I = Cache.PkgBegin();
1104    for (;I.end() != true; I++) {
1105       if (Cache[I].NewInstall() && !(Flags[I->ID] & PreInstalled)) {
1106          if(_config->FindI("Debug::pkgAutoRemove",false)) {
1107             std::clog << "Resolve installed new pkg: " << I.Name()
1108                       << " (now marking it as auto)" << std::endl;
1109          }
1110          Cache[I].Flags |= pkgCache::Flag::Auto;
1111       }
1112    }
1113
1114
1115    return true;
1116 }
1117                                                                         /*}}}*/
1118 // ProblemResolver::ResolveByKeep - Resolve problems using keep         /*{{{*/
1119 // ---------------------------------------------------------------------
1120 /* This is the work horse of the soft upgrade routine. It is very gental
1121    in that it does not install or remove any packages. It is assumed that the
1122    system was non-broken previously. */
1123 bool pkgProblemResolver::ResolveByKeep()
1124 {
1125    pkgDepCache::ActionGroup group(Cache);
1126
1127    unsigned long Size = Cache.Head().PackageCount;
1128
1129    if (Debug == true)
1130       clog << "Entering ResolveByKeep" << endl;
1131
1132    MakeScores();
1133
1134    /* We have to order the packages so that the broken fixing pass
1135       operates from highest score to lowest. This prevents problems when
1136       high score packages cause the removal of lower score packages that
1137       would cause the removal of even lower score packages. */
1138    pkgCache::Package **PList = new pkgCache::Package *[Size];
1139    pkgCache::Package **PEnd = PList;
1140    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
1141       *PEnd++ = I;
1142    This = this;
1143    qsort(PList,PEnd - PList,sizeof(*PList),&ScoreSort);
1144
1145    // Consider each broken package
1146    pkgCache::Package **LastStop = 0;
1147    for (pkgCache::Package **K = PList; K != PEnd; K++)
1148    {
1149       pkgCache::PkgIterator I(Cache,*K);
1150
1151       if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false)
1152          continue;
1153
1154       /* Keep the package. If this works then great, otherwise we have
1155          to be significantly more agressive and manipulate its dependencies */
1156       if ((Flags[I->ID] & Protected) == 0)
1157       {
1158          if (Debug == true)
1159             clog << "Keeping package " << I.Name() << endl;
1160          Cache.MarkKeep(I, false, false);
1161          if (Cache[I].InstBroken() == false)
1162          {
1163             K = PList - 1;
1164             continue;
1165          }
1166       }
1167
1168       // Isolate the problem dependencies
1169       for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false;)
1170       {
1171          DepIterator Start;
1172          DepIterator End;
1173          D.GlobOr(Start,End);
1174
1175          // We only worry about critical deps.
1176          if (End.IsCritical() != true)
1177             continue;
1178
1179          // Dep is ok
1180          if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
1181             continue;
1182
1183          /* Hm, the group is broken.. I suppose the best thing to do is to
1184             is to try every combination of keep/not-keep for the set, but thats
1185             slow, and this never happens, just be conservative and assume the
1186             list of ors is in preference and keep till it starts to work. */
1187          while (true)
1188          {
1189             if (Debug == true)
1190                clog << "Package " << I.Name() << " has broken dep on " << Start.TargetPkg().Name() << endl;
1191
1192             // Look at all the possible provides on this package
1193             SPtrArray<pkgCache::Version *> VList = Start.AllTargets();
1194             for (pkgCache::Version **V = VList; *V != 0; V++)
1195             {
1196                pkgCache::VerIterator Ver(Cache,*V);
1197                pkgCache::PkgIterator Pkg = Ver.ParentPkg();
1198
1199                // It is not keepable
1200                if (Cache[Pkg].InstallVer == 0 ||
1201                    Pkg->CurrentVer == 0)
1202                   continue;
1203
1204                if ((Flags[I->ID] & Protected) == 0)
1205                {
1206                   if (Debug == true)
1207                      clog << "  Keeping Package " << Pkg.Name() << " due to dep" << endl;
1208                   Cache.MarkKeep(Pkg, false, false);
1209                }
1210
1211                if (Cache[I].InstBroken() == false)
1212                   break;
1213             }
1214
1215             if (Cache[I].InstBroken() == false)
1216                break;
1217
1218             if (Start == End)
1219                break;
1220             Start++;
1221          }
1222
1223          if (Cache[I].InstBroken() == false)
1224             break;
1225       }
1226
1227       if (Cache[I].InstBroken() == true)
1228          continue;
1229
1230       // Restart again.
1231       if (K == LastStop)
1232          return _error->Error("Internal Error, pkgProblemResolver::ResolveByKeep is looping on package %s.",I.Name());
1233       LastStop = K;
1234       K = PList - 1;
1235    }
1236
1237    return true;
1238 }
1239                                                                         /*}}}*/
1240 // ProblemResolver::InstallProtect - Install all protected packages     /*{{{*/
1241 // ---------------------------------------------------------------------
1242 /* This is used to make sure protected packages are installed */
1243 void pkgProblemResolver::InstallProtect()
1244 {
1245    pkgDepCache::ActionGroup group(Cache);
1246
1247    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
1248    {
1249       if ((Flags[I->ID] & Protected) == Protected)
1250       {
1251          if ((Flags[I->ID] & ToRemove) == ToRemove)
1252             Cache.MarkDelete(I);
1253          else
1254          {
1255             // preserver the information if the package was auto
1256             // or manual installed
1257             bool autoInst = (Cache[I].Flags & pkgCache::Flag::Auto);
1258             Cache.MarkInstall(I, false, 0, !autoInst);
1259          }
1260       }
1261    }
1262 }
1263                                                                         /*}}}*/
1264
1265 // PrioSortList - Sort a list of versions by priority                   /*{{{*/
1266 // ---------------------------------------------------------------------
1267 /* This is ment to be used in conjunction with AllTargets to get a list
1268    of versions ordered by preference. */
1269 static pkgCache *PrioCache;
1270 static int PrioComp(const void *A,const void *B)
1271 {
1272    pkgCache::VerIterator L(*PrioCache,*(pkgCache::Version **)A);
1273    pkgCache::VerIterator R(*PrioCache,*(pkgCache::Version **)B);
1274
1275    if ((L.ParentPkg()->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential &&
1276        (R.ParentPkg()->Flags & pkgCache::Flag::Essential) != pkgCache::Flag::Essential)
1277      return 1;
1278    if ((L.ParentPkg()->Flags & pkgCache::Flag::Essential) != pkgCache::Flag::Essential &&
1279        (R.ParentPkg()->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
1280      return -1;
1281
1282    if (L->Priority != R->Priority)
1283       return R->Priority - L->Priority;
1284    return strcmp(L.ParentPkg().Name(),R.ParentPkg().Name());
1285 }
1286 void pkgPrioSortList(pkgCache &Cache,pkgCache::Version **List)
1287 {
1288    unsigned long Count = 0;
1289    PrioCache = &Cache;
1290    for (pkgCache::Version **I = List; *I != 0; I++)
1291       Count++;
1292    qsort(List,Count,sizeof(*List),PrioComp);
1293 }
1294                                                                         /*}}}*/
1295