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