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 those are not obsolete
 514       */
 515       if (I->CurrentVer != 0 && Cache[I].CandidateVer != 0 && Cache[I].CandidateVerIter(Cache).Downloadable())
 516          Score += 1;
 517    }
 518
 519    // Now that we have the base scores we go and propogate dependencies
 520    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 521    {
 522       if (Cache[I].InstallVer == 0)
 523          continue;
 524
 525       for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false; D++)
 526       {
 527          if (D->Type == pkgCache::Dep::Depends || D->Type == pkgCache::Dep::PreDepends)
 528             Scores[D.TargetPkg()->ID]++;
 529       }
 530    }
 531
 532    // Copy the scores to advoid additive looping
 533    SPtrArray<signed short> OldScores = new signed short[Size];
 534    memcpy(OldScores,Scores,sizeof(*Scores)*Size);
 535
 536    /* Now we cause 1 level of dependency inheritance, that is we add the
 537       score of the packages that depend on the target Package. This
 538       fortifies high scoring packages */
 539    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 540    {
 541       if (Cache[I].InstallVer == 0)
 542          continue;
 543
 544       for (pkgCache::DepIterator D = I.RevDependsList(); D.end() == false; D++)
 545       {
 546          // Only do it for the install version
 547          if ((pkgCache::Version *)D.ParentVer() != Cache[D.ParentPkg()].InstallVer ||
 548              (D->Type != pkgCache::Dep::Depends && D->Type != pkgCache::Dep::PreDepends))
 549             continue;
 550
 551          Scores[I->ID] += abs(OldScores[D.ParentPkg()->ID]);
 552       }
 553    }
 554
 555    /* Now we propogate along provides. This makes the packages that
 556       provide important packages extremely important */
 557    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 558    {
 559       for (pkgCache::PrvIterator P = I.ProvidesList(); P.end() == false; P++)
 560       {
 561          // Only do it once per package
 562          if ((pkgCache::Version *)P.OwnerVer() != Cache[P.OwnerPkg()].InstallVer)
 563             continue;
 564          Scores[P.OwnerPkg()->ID] += abs(Scores[I->ID] - OldScores[I->ID]);
 565       }
 566    }
 567
 568    /* Protected things are pushed really high up. This number should put them
 569       ahead of everything */
 570    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 571    {
 572       if ((Flags[I->ID] & Protected) != 0)
 573          Scores[I->ID] += 10000;
 574       if ((I->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
 575          Scores[I->ID] += 5000;
 576    }
 577 }
 578                                                                         /*}}}*/
 579 // ProblemResolver::DoUpgrade - Attempt to upgrade this package         /*{{{*/
 580 // ---------------------------------------------------------------------
 581 /* This goes through and tries to reinstall packages to make this package
 582    installable */
 583 bool pkgProblemResolver::DoUpgrade(pkgCache::PkgIterator Pkg)
 584 {
 585    pkgDepCache::ActionGroup group(Cache);
 586
 587    if ((Flags[Pkg->ID] & Upgradable) == 0 || Cache[Pkg].Upgradable() == false)
 588       return false;
 589    if ((Flags[Pkg->ID] & Protected) == Protected)
 590       return false;
 591
 592    Flags[Pkg->ID] &= ~Upgradable;
 593
 594    bool WasKept = Cache[Pkg].Keep();
 595    Cache.MarkInstall(Pkg, false, 0, false);
 596
 597    // This must be a virtual package or something like that.
 598    if (Cache[Pkg].InstVerIter(Cache).end() == true)
 599       return false;
 600
 601    // Isolate the problem dependency
 602    bool Fail = false;
 603    for (pkgCache::DepIterator D = Cache[Pkg].InstVerIter(Cache).DependsList(); D.end() == false;)
 604    {
 605       // Compute a single dependency element (glob or)
 606       pkgCache::DepIterator Start = D;
 607       pkgCache::DepIterator End = D;
 608       unsigned char State = 0;
 609       for (bool LastOR = true; D.end() == false && LastOR == true;)
 610       {
 611          State |= Cache[D];
 612          LastOR = (D->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or;
 613          D++;
 614          if (LastOR == true)
 615             End = D;
 616       }
 617
 618       // We only worry about critical deps.
 619       if (End.IsCritical() != true)
 620          continue;
 621
 622       // Iterate over all the members in the or group
 623       while (1)
 624       {
 625          // Dep is ok now
 626          if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
 627             break;
 628
 629          // Do not change protected packages
 630          PkgIterator P = Start.SmartTargetPkg();
 631          if ((Flags[P->ID] & Protected) == Protected)
 632          {
 633             if (Debug == true)
 634                clog << "    Reinst Failed because of protected " << P.Name() << endl;
 635             Fail = true;
 636          }
 637          else
 638          {
 639             // Upgrade the package if the candidate version will fix the problem.
 640             if ((Cache[Start] & pkgDepCache::DepCVer) == pkgDepCache::DepCVer)
 641             {
 642                if (DoUpgrade(P) == false)
 643                {
 644                   if (Debug == true)
 645                      clog << "    Reinst Failed because of " << P.Name() << endl;
 646                   Fail = true;
 647                }
 648                else
 649                {
 650                   Fail = false;
 651                   break;
 652                }
 653             }
 654             else
 655             {
 656                /* We let the algorithm deal with conflicts on its next iteration,
 657                 it is much smarter than us */
 658                if (Start->Type == pkgCache::Dep::Conflicts ||
 659                    Start->Type == pkgCache::Dep::DpkgBreaks ||
 660                    Start->Type == pkgCache::Dep::Obsoletes)
 661                    break;
 662
 663                if (Debug == true)
 664                   clog << "    Reinst Failed early because of " << Start.TargetPkg().Name() << endl;
 665                Fail = true;
 666             }
 667          }
 668
 669          if (Start == End)
 670             break;
 671          Start++;
 672       }
 673       if (Fail == true)
 674          break;
 675    }
 676
 677    // Undo our operations - it might be smart to undo everything this did..
 678    if (Fail == true)
 679    {
 680       if (WasKept == true)
 681          Cache.MarkKeep(Pkg, false, false);
 682       else
 683          Cache.MarkDelete(Pkg);
 684       return false;
 685    }
 686
 687    if (Debug == true)
 688       clog << "  Re-Instated " << Pkg.Name() << endl;
 689    return true;
 690 }
 691                                                                         /*}}}*/
 692 // ProblemResolver::Resolve - Run the resolution pass                   /*{{{*/
 693 // ---------------------------------------------------------------------
 694 /* This routines works by calculating a score for each package. The score
 695    is derived by considering the package's priority and all reverse
 696    dependents giving an integer that reflects the amount of breakage that
 697    adjusting the package will inflict.
 698
 699    It goes from highest score to lowest and corrects all of the breaks by
 700    keeping or removing the dependant packages. If that fails then it removes
 701    the package itself and goes on. The routine should be able to intelligently
 702    go from any broken state to a fixed state.
 703
 704    The BrokenFix flag enables a mode where the algorithm tries to
 705    upgrade packages to advoid problems. */
 706 bool pkgProblemResolver::Resolve(bool BrokenFix)
 707 {
 708    pkgDepCache::ActionGroup group(Cache);
 709
 710    unsigned long Size = Cache.Head().PackageCount;
 711
 712    // Record which packages are marked for install
 713    bool Again = false;
 714    do
 715    {
 716       Again = false;
 717       for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 718       {
 719          if (Cache[I].Install() == true)
 720             Flags[I->ID] |= PreInstalled;
 721          else
 722          {
 723             if (Cache[I].InstBroken() == true && BrokenFix == true)
 724             {
 725                Cache.MarkInstall(I, false, 0, false);
 726                if (Cache[I].Install() == true)
 727                   Again = true;
 728             }
 729
 730             Flags[I->ID] &= ~PreInstalled;
 731          }
 732          Flags[I->ID] |= Upgradable;
 733       }
 734    }
 735    while (Again == true);
 736
 737    if (Debug == true)
 738       clog << "Starting" << endl;
 739
 740    MakeScores();
 741
 742    /* We have to order the packages so that the broken fixing pass
 743       operates from highest score to lowest. This prevents problems when
 744       high score packages cause the removal of lower score packages that
 745       would cause the removal of even lower score packages. */
 746    SPtrArray<pkgCache::Package *> PList = new pkgCache::Package *[Size];
 747    pkgCache::Package **PEnd = PList;
 748    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 749       *PEnd++ = I;
 750    This = this;
 751    qsort(PList,PEnd - PList,sizeof(*PList),&ScoreSort);
 752
 753 /* for (pkgCache::Package **K = PList; K != PEnd; K++)
 754       if (Scores[(*K)->ID] != 0)
 755       {
 756          pkgCache::PkgIterator Pkg(Cache,*K);
 757          clog << Scores[(*K)->ID] << ' ' << Pkg.Name() <<
 758             ' ' << (pkgCache::Version *)Pkg.CurrentVer() << ' ' <<
 759             Cache[Pkg].InstallVer << ' ' << Cache[Pkg].CandidateVer << endl;
 760       } */
 761
 762    if (Debug == true)
 763       clog << "Starting 2" << endl;
 764
 765    /* Now consider all broken packages. For each broken package we either
 766       remove the package or fix it's problem. We do this once, it should
 767       not be possible for a loop to form (that is a < b < c and fixing b by
 768       changing a breaks c) */
 769    bool Change = true;
 770    for (int Counter = 0; Counter != 10 && Change == true; Counter++)
 771    {
 772       Change = false;
 773       for (pkgCache::Package **K = PList; K != PEnd; K++)
 774       {
 775          pkgCache::PkgIterator I(Cache,*K);
 776
 777          /* We attempt to install this and see if any breaks result,
 778             this takes care of some strange cases */
 779          if (Cache[I].CandidateVer != Cache[I].InstallVer &&
 780              I->CurrentVer != 0 && Cache[I].InstallVer != 0 &&
 781              (Flags[I->ID] & PreInstalled) != 0 &&
 782              (Flags[I->ID] & Protected) == 0 &&
 783              (Flags[I->ID] & ReInstateTried) == 0)
 784          {
 785             if (Debug == true)
 786                clog << " Try to Re-Instate " << I.Name() << endl;
 787             unsigned long OldBreaks = Cache.BrokenCount();
 788             pkgCache::Version *OldVer = Cache[I].InstallVer;
 789             Flags[I->ID] &= ReInstateTried;
 790
 791             Cache.MarkInstall(I, false, 0, false);
 792             if (Cache[I].InstBroken() == true ||
 793                 OldBreaks < Cache.BrokenCount())
 794             {
 795                if (OldVer == 0)
 796                   Cache.MarkDelete(I);
 797                else
 798                   Cache.MarkKeep(I, false, false);
 799             }
 800             else
 801                if (Debug == true)
 802                   clog << "Re-Instated " << I.Name() << " (" << OldBreaks << " vs " << Cache.BrokenCount() << ')' << endl;
 803          }
 804
 805          if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false)
 806             continue;
 807
 808          if (Debug == true)
 809             clog << "Investigating " << I.Name() << endl;
 810
 811          // Isolate the problem dependency
 812          PackageKill KillList[100];
 813          PackageKill *LEnd = KillList;
 814          bool InOr = false;
 815          pkgCache::DepIterator Start;
 816          pkgCache::DepIterator End;
 817          PackageKill *OldEnd = LEnd;
 818
 819          enum {OrRemove,OrKeep} OrOp = OrRemove;
 820          for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList();
 821               D.end() == false || InOr == true;)
 822          {
 823             // Compute a single dependency element (glob or)
 824             if (Start == End)
 825             {
 826                // Decide what to do
 827                if (InOr == true)
 828                {
 829                   if (OldEnd == LEnd && OrOp == OrRemove)
 830                   {
 831                      if ((Flags[I->ID] & Protected) != Protected)
 832                      {
 833                         if (Debug == true)
 834                            clog << "  Or group remove for " << I.Name() << endl;
 835                         Cache.MarkDelete(I);
 836                         Change = true;
 837                      }
 838                   }
 839                   if (OldEnd == LEnd && OrOp == OrKeep)
 840                   {
 841                      if (Debug == true)
 842                         clog << "  Or group keep for " << I.Name() << endl;
 843                      Cache.MarkKeep(I, false, false);
 844                      Change = true;
 845                   }
 846                }
 847
 848                /* We do an extra loop (as above) to finalize the or group
 849                   processing */
 850                InOr = false;
 851                OrOp = OrRemove;
 852                D.GlobOr(Start,End);
 853                if (Start.end() == true)
 854                   break;
 855
 856                // We only worry about critical deps.
 857                if (End.IsCritical() != true)
 858                   continue;
 859
 860                InOr = Start != End;
 861                OldEnd = LEnd;
 862             }
 863             else
 864             {
 865                Start++;
 866                // We only worry about critical deps.
 867                if (Start.IsCritical() != true)
 868                   continue;
 869             }
 870
 871             // Dep is ok
 872             if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
 873             {
 874                InOr = false;
 875                continue;
 876             }
 877
 878             if (Debug == true)
 879                clog << "Package " << I.Name() << " has broken dep on " << Start.TargetPkg().Name() << endl;
 880
 881             /* Look across the version list. If there are no possible
 882                targets then we keep the package and bail. This is necessary
 883                if a package has a dep on another package that cant be found */
 884             SPtrArray<pkgCache::Version *> VList = Start.AllTargets();
 885             if (*VList == 0 && (Flags[I->ID] & Protected) != Protected &&
 886                 Start->Type != pkgCache::Dep::Conflicts &&
 887                 Start->Type != pkgCache::Dep::DpkgBreaks &&
 888                 Start->Type != pkgCache::Dep::Obsoletes &&
 889                 Cache[I].NowBroken() == false)
 890             {
 891                if (InOr == true)
 892                {
 893                   /* No keep choice because the keep being OK could be the
 894                      result of another element in the OR group! */
 895                   continue;
 896                }
 897
 898                Change = true;
 899                Cache.MarkKeep(I, false, false);
 900                break;
 901             }
 902
 903             bool Done = false;
 904             for (pkgCache::Version **V = VList; *V != 0; V++)
 905             {
 906                pkgCache::VerIterator Ver(Cache,*V);
 907                pkgCache::PkgIterator Pkg = Ver.ParentPkg();
 908
 909                if (Debug == true)
 910                   clog << "  Considering " << Pkg.Name() << ' ' << (int)Scores[Pkg->ID] <<
 911                   " as a solution to " << I.Name() << ' ' << (int)Scores[I->ID] << endl;
 912
 913                /* Try to fix the package under consideration rather than
 914                   fiddle with the VList package */
 915                if (Scores[I->ID] <= Scores[Pkg->ID] ||
 916                    ((Cache[Start] & pkgDepCache::DepNow) == 0 &&
 917                     End->Type != pkgCache::Dep::Conflicts &&
 918                     End->Type != pkgCache::Dep::DpkgBreaks &&
 919                     End->Type != pkgCache::Dep::Obsoletes))
 920                {
 921                   // Try a little harder to fix protected packages..
 922                   if ((Flags[I->ID] & Protected) == Protected)
 923                   {
 924                      if (DoUpgrade(Pkg) == true)
 925                      {
 926                         if (Scores[Pkg->ID] > Scores[I->ID])
 927                            Scores[Pkg->ID] = Scores[I->ID];
 928                         break;
 929                      }
 930
 931                      continue;
 932                   }
 933
 934                   /* See if a keep will do, unless the package is protected,
 935                      then installing it will be necessary */
 936                   bool Installed = Cache[I].Install();
 937                   Cache.MarkKeep(I, false, false);
 938                   if (Cache[I].InstBroken() == false)
 939                   {
 940                      // Unwind operation will be keep now
 941                      if (OrOp == OrRemove)
 942                         OrOp = OrKeep;
 943
 944                      // Restore
 945                      if (InOr == true && Installed == true)
 946                         Cache.MarkInstall(I, false, 0, false);
 947
 948                      if (Debug == true)
 949                         clog << "  Holding Back " << I.Name() << " rather than change " << Start.TargetPkg().Name() << endl;
 950                   }
 951                   else
 952                   {
 953                      if (BrokenFix == false || DoUpgrade(I) == false)
 954                      {
 955                         // Consider other options
 956                         if (InOr == false)
 957                         {
 958                            if (Debug == true)
 959                               clog << "  Removing " << I.Name() << " rather than change " << Start.TargetPkg().Name() << endl;
 960                            Cache.MarkDelete(I);
 961                            if (Counter > 1)
 962                            {
 963                               if (Scores[Pkg->ID] > Scores[I->ID])
 964                                  Scores[I->ID] = Scores[Pkg->ID];
 965                            }
 966                         }
 967                      }
 968                   }
 969
 970                   Change = true;
 971                   Done = true;
 972                   break;
 973                }
 974                else
 975                {
 976                   /* This is a conflicts, and the version we are looking
 977                      at is not the currently selected version of the
 978                      package, which means it is not necessary to
 979                      remove/keep */
 980                   if (Cache[Pkg].InstallVer != Ver &&
 981                       (Start->Type == pkgCache::Dep::Conflicts ||
 982                        Start->Type == pkgCache::Dep::Obsoletes))
 983                      continue;
 984
 985                   if (Start->Type == pkgCache::Dep::DpkgBreaks)
 986                   {
 987                      /* Would it help if we upgraded? */
 988                      if (Cache[End] & pkgDepCache::DepGCVer) {
 989                         if (Debug)
 990                            clog << "  Upgrading " << Pkg.Name() << " due to Breaks field in " << I.Name() << endl;
 991                         Cache.MarkInstall(Pkg, false, 0, false);
 992                         continue;
 993                      }
 994                      if (Debug)
 995                         clog << "  Will not break " << Pkg.Name() << " as stated in Breaks field in " << I.Name() <<endl;
 996                      Cache.MarkKeep(I, false, false);
 997                      continue;
 998                   }
 999
1000                   // Skip adding to the kill list if it is protected
1001                   if ((Flags[Pkg->ID] & Protected) != 0)
1002                      continue;
1003
1004                   if (Debug == true)
1005                      clog << "  Added " << Pkg.Name() << " to the remove list" << endl;
1006
1007                   LEnd->Pkg = Pkg;
1008                   LEnd->Dep = End;
1009                   LEnd++;
1010
1011                   if (Start->Type != pkgCache::Dep::Conflicts &&
1012                       Start->Type != pkgCache::Dep::Obsoletes)
1013                      break;
1014                }
1015             }
1016
1017             // Hm, nothing can possibly satisify this dep. Nuke it.
1018             if (VList[0] == 0 &&
1019                 Start->Type != pkgCache::Dep::Conflicts &&
1020                 Start->Type != pkgCache::Dep::DpkgBreaks &&
1021                 Start->Type != pkgCache::Dep::Obsoletes &&
1022                 (Flags[I->ID] & Protected) != Protected)
1023             {
1024                bool Installed = Cache[I].Install();
1025                Cache.MarkKeep(I);
1026                if (Cache[I].InstBroken() == false)
1027                {
1028                   // Unwind operation will be keep now
1029                   if (OrOp == OrRemove)
1030                      OrOp = OrKeep;
1031
1032                   // Restore
1033                   if (InOr == true && Installed == true)
1034                      Cache.MarkInstall(I, false, 0, false);
1035
1036                   if (Debug == true)
1037                      clog << "  Holding Back " << I.Name() << " because I can't find " << Start.TargetPkg().Name() << endl;
1038                }
1039                else
1040                {
1041                   if (Debug == true)
1042                      clog << "  Removing " << I.Name() << " because I can't find " << Start.TargetPkg().Name() << endl;
1043                   if (InOr == false)
1044                      Cache.MarkDelete(I);
1045                }
1046
1047                Change = true;
1048                Done = true;
1049             }
1050
1051             // Try some more
1052             if (InOr == true)
1053                continue;
1054
1055             if (Done == true)
1056                break;
1057          }
1058
1059          // Apply the kill list now
1060          if (Cache[I].InstallVer != 0)
1061          {
1062             for (PackageKill *J = KillList; J != LEnd; J++)
1063             {
1064                Change = true;
1065                if ((Cache[J->Dep] & pkgDepCache::DepGNow) == 0)
1066                {
1067                   if (J->Dep->Type == pkgCache::Dep::Conflicts ||
1068                       J->Dep->Type == pkgCache::Dep::Obsoletes)
1069                   {
1070                      if (Debug == true)
1071                         clog << "  Fixing " << I.Name() << " via remove of " << J->Pkg.Name() << endl;
1072                      Cache.MarkDelete(J->Pkg);
1073                   }
1074                }
1075                else
1076                {
1077                   if (Debug == true)
1078                      clog << "  Fixing " << I.Name() << " via keep of " << J->Pkg.Name() << endl;
1079                   Cache.MarkKeep(J->Pkg, false, false);
1080                }
1081
1082                if (Counter > 1)
1083                {
1084                   if (Scores[I->ID] > Scores[J->Pkg->ID])
1085                      Scores[J->Pkg->ID] = Scores[I->ID];
1086                }
1087             }
1088          }
1089       }
1090    }
1091
1092    if (Debug == true)
1093       clog << "Done" << endl;
1094
1095    if (Cache.BrokenCount() != 0)
1096    {
1097       // See if this is the result of a hold
1098       pkgCache::PkgIterator I = Cache.PkgBegin();
1099       for (;I.end() != true; I++)
1100       {
1101          if (Cache[I].InstBroken() == false)
1102             continue;
1103          if ((Flags[I->ID] & Protected) != Protected)
1104             return _error->Error(_("Error, pkgProblemResolver::Resolve generated breaks, this may be caused by held packages."));
1105       }
1106       return _error->Error(_("Unable to correct problems, you have held broken packages."));
1107    }
1108
1109    // set the auto-flags (mvo: I'm not sure if we _really_ need this, but
1110    // I didn't managed
1111    pkgCache::PkgIterator I = Cache.PkgBegin();
1112    for (;I.end() != true; I++) {
1113       if (Cache[I].NewInstall() && !(Flags[I->ID] & PreInstalled)) {
1114          if(_config->FindI("Debug::pkgAutoRemove",false)) {
1115             std::clog << "Resolve installed new pkg: " << I.Name()
1116                       << " (now marking it as auto)" << std::endl;
1117          }
1118          Cache[I].Flags |= pkgCache::Flag::Auto;
1119       }
1120    }
1121
1122
1123    return true;
1124 }
1125                                                                         /*}}}*/
1126 // ProblemResolver::ResolveByKeep - Resolve problems using keep         /*{{{*/
1127 // ---------------------------------------------------------------------
1128 /* This is the work horse of the soft upgrade routine. It is very gental
1129    in that it does not install or remove any packages. It is assumed that the
1130    system was non-broken previously. */
1131 bool pkgProblemResolver::ResolveByKeep()
1132 {
1133    pkgDepCache::ActionGroup group(Cache);
1134
1135    unsigned long Size = Cache.Head().PackageCount;
1136
1137    if (Debug == true)
1138       clog << "Entering ResolveByKeep" << endl;
1139
1140    MakeScores();
1141
1142    /* We have to order the packages so that the broken fixing pass
1143       operates from highest score to lowest. This prevents problems when
1144       high score packages cause the removal of lower score packages that
1145       would cause the removal of even lower score packages. */
1146    pkgCache::Package **PList = new pkgCache::Package *[Size];
1147    pkgCache::Package **PEnd = PList;
1148    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
1149       *PEnd++ = I;
1150    This = this;
1151    qsort(PList,PEnd - PList,sizeof(*PList),&ScoreSort);
1152
1153    // Consider each broken package
1154    pkgCache::Package **LastStop = 0;
1155    for (pkgCache::Package **K = PList; K != PEnd; K++)
1156    {
1157       pkgCache::PkgIterator I(Cache,*K);
1158
1159       if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false)
1160          continue;
1161
1162       /* Keep the package. If this works then great, otherwise we have
1163          to be significantly more agressive and manipulate its dependencies */
1164       if ((Flags[I->ID] & Protected) == 0)
1165       {
1166          if (Debug == true)
1167             clog << "Keeping package " << I.Name() << endl;
1168          Cache.MarkKeep(I, false, false);
1169          if (Cache[I].InstBroken() == false)
1170          {
1171             K = PList - 1;
1172             continue;
1173          }
1174       }
1175
1176       // Isolate the problem dependencies
1177       for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false;)
1178       {
1179          DepIterator Start;
1180          DepIterator End;
1181          D.GlobOr(Start,End);
1182
1183          // We only worry about critical deps.
1184          if (End.IsCritical() != true)
1185             continue;
1186
1187          // Dep is ok
1188          if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
1189             continue;
1190
1191          /* Hm, the group is broken.. I suppose the best thing to do is to
1192             is to try every combination of keep/not-keep for the set, but thats
1193             slow, and this never happens, just be conservative and assume the
1194             list of ors is in preference and keep till it starts to work. */
1195          while (true)
1196          {
1197             if (Debug == true)
1198                clog << "Package " << I.Name() << " has broken dep on " << Start.TargetPkg().Name() << endl;
1199
1200             // Look at all the possible provides on this package
1201             SPtrArray<pkgCache::Version *> VList = Start.AllTargets();
1202             for (pkgCache::Version **V = VList; *V != 0; V++)
1203             {
1204                pkgCache::VerIterator Ver(Cache,*V);
1205                pkgCache::PkgIterator Pkg = Ver.ParentPkg();
1206
1207                // It is not keepable
1208                if (Cache[Pkg].InstallVer == 0 ||
1209                    Pkg->CurrentVer == 0)
1210                   continue;
1211
1212                if ((Flags[I->ID] & Protected) == 0)
1213                {
1214                   if (Debug == true)
1215                      clog << "  Keeping Package " << Pkg.Name() << " due to dep" << endl;
1216                   Cache.MarkKeep(Pkg, false, false);
1217                }
1218
1219                if (Cache[I].InstBroken() == false)
1220                   break;
1221             }
1222
1223             if (Cache[I].InstBroken() == false)
1224                break;
1225
1226             if (Start == End)
1227                break;
1228             Start++;
1229          }
1230
1231          if (Cache[I].InstBroken() == false)
1232             break;
1233       }
1234
1235       if (Cache[I].InstBroken() == true)
1236          continue;
1237
1238       // Restart again.
1239       if (K == LastStop)
1240          return _error->Error("Internal Error, pkgProblemResolver::ResolveByKeep is looping on package %s.",I.Name());
1241       LastStop = K;
1242       K = PList - 1;
1243    }
1244
1245    return true;
1246 }
1247                                                                         /*}}}*/
1248 // ProblemResolver::InstallProtect - Install all protected packages     /*{{{*/
1249 // ---------------------------------------------------------------------
1250 /* This is used to make sure protected packages are installed */
1251 void pkgProblemResolver::InstallProtect()
1252 {
1253    pkgDepCache::ActionGroup group(Cache);
1254
1255    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
1256    {
1257       if ((Flags[I->ID] & Protected) == Protected)
1258       {
1259          if ((Flags[I->ID] & ToRemove) == ToRemove)
1260             Cache.MarkDelete(I);
1261          else
1262          {
1263             // preserver the information if the package was auto
1264             // or manual installed
1265             bool autoInst = (Cache[I].Flags & pkgCache::Flag::Auto);
1266             Cache.MarkInstall(I, false, 0, !autoInst);
1267          }
1268       }
1269    }
1270 }
1271                                                                         /*}}}*/
1272
1273 // PrioSortList - Sort a list of versions by priority                   /*{{{*/
1274 // ---------------------------------------------------------------------
1275 /* This is ment to be used in conjunction with AllTargets to get a list
1276    of versions ordered by preference. */
1277 static pkgCache *PrioCache;
1278 static int PrioComp(const void *A,const void *B)
1279 {
1280    pkgCache::VerIterator L(*PrioCache,*(pkgCache::Version **)A);
1281    pkgCache::VerIterator R(*PrioCache,*(pkgCache::Version **)B);
1282
1283    if ((L.ParentPkg()->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential &&
1284        (R.ParentPkg()->Flags & pkgCache::Flag::Essential) != pkgCache::Flag::Essential)
1285      return 1;
1286    if ((L.ParentPkg()->Flags & pkgCache::Flag::Essential) != pkgCache::Flag::Essential &&
1287        (R.ParentPkg()->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
1288      return -1;
1289
1290    if (L->Priority != R->Priority)
1291       return R->Priority - L->Priority;
1292    return strcmp(L.ParentPkg().Name(),R.ParentPkg().Name());
1293 }
1294 void pkgPrioSortList(pkgCache &Cache,pkgCache::Version **List)
1295 {
1296    unsigned long Count = 0;
1297    PrioCache = &Cache;
1298    for (pkgCache::Version **I = List; *I != 0; I++)
1299       Count++;
1300    qsort(List,Count,sizeof(*List),PrioComp);
1301 }
1302                                                                         /*}}}*/
1303