apt-pkg/algorithms.cc

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