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