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)
1112    pkgCache::PkgIterator I = Cache.PkgBegin();
1113    for (;I.end() != true; I++) {
1114       if (Cache[I].NewInstall() && !(Flags[I->ID] & PreInstalled)) {
1115          if(_config->FindI("Debug::pkgAutoRemove",false)) {
1116             std::clog << "Resolve installed new pkg: " << I.Name()
1117                       << " (now marking it as auto)" << std::endl;
1118          }
1119          Cache[I].Flags |= pkgCache::Flag::Auto;
1120       }
1121    }
1122
1123
1124    return true;
1125 }
1126                                                                         /*}}}*/
1127 // ProblemResolver::ResolveByKeep - Resolve problems using keep         /*{{{*/
1128 // ---------------------------------------------------------------------
1129 /* This is the work horse of the soft upgrade routine. It is very gental
1130    in that it does not install or remove any packages. It is assumed that the
1131    system was non-broken previously. */
1132 bool pkgProblemResolver::ResolveByKeep()
1133 {
1134    pkgDepCache::ActionGroup group(Cache);
1135
1136    unsigned long Size = Cache.Head().PackageCount;
1137
1138    if (Debug == true)
1139       clog << "Entering ResolveByKeep" << endl;
1140
1141    MakeScores();
1142
1143    /* We have to order the packages so that the broken fixing pass
1144       operates from highest score to lowest. This prevents problems when
1145       high score packages cause the removal of lower score packages that
1146       would cause the removal of even lower score packages. */
1147    pkgCache::Package **PList = new pkgCache::Package *[Size];
1148    pkgCache::Package **PEnd = PList;
1149    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
1150       *PEnd++ = I;
1151    This = this;
1152    qsort(PList,PEnd - PList,sizeof(*PList),&ScoreSort);
1153
1154    // Consider each broken package
1155    pkgCache::Package **LastStop = 0;
1156    for (pkgCache::Package **K = PList; K != PEnd; K++)
1157    {
1158       pkgCache::PkgIterator I(Cache,*K);
1159
1160       if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false)
1161          continue;
1162
1163       /* Keep the package. If this works then great, otherwise we have
1164          to be significantly more agressive and manipulate its dependencies */
1165       if ((Flags[I->ID] & Protected) == 0)
1166       {
1167          if (Debug == true)
1168             clog << "Keeping package " << I.Name() << endl;
1169          Cache.MarkKeep(I, false, false);
1170          if (Cache[I].InstBroken() == false)
1171          {
1172             K = PList - 1;
1173             continue;
1174          }
1175       }
1176
1177       // Isolate the problem dependencies
1178       for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false;)
1179       {
1180          DepIterator Start;
1181          DepIterator End;
1182          D.GlobOr(Start,End);
1183
1184          // We only worry about critical deps.
1185          if (End.IsCritical() != true)
1186             continue;
1187
1188          // Dep is ok
1189          if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
1190             continue;
1191
1192          /* Hm, the group is broken.. I suppose the best thing to do is to
1193             is to try every combination of keep/not-keep for the set, but thats
1194             slow, and this never happens, just be conservative and assume the
1195             list of ors is in preference and keep till it starts to work. */
1196          while (true)
1197          {
1198             if (Debug == true)
1199                clog << "Package " << I.Name() << " has broken dep on " << Start.TargetPkg().Name() << endl;
1200
1201             // Look at all the possible provides on this package
1202             SPtrArray<pkgCache::Version *> VList = Start.AllTargets();
1203             for (pkgCache::Version **V = VList; *V != 0; V++)
1204             {
1205                pkgCache::VerIterator Ver(Cache,*V);
1206                pkgCache::PkgIterator Pkg = Ver.ParentPkg();
1207
1208                // It is not keepable
1209                if (Cache[Pkg].InstallVer == 0 ||
1210                    Pkg->CurrentVer == 0)
1211                   continue;
1212
1213                if ((Flags[I->ID] & Protected) == 0)
1214                {
1215                   if (Debug == true)
1216                      clog << "  Keeping Package " << Pkg.Name() << " due to dep" << endl;
1217                   Cache.MarkKeep(Pkg, false, false);
1218                }
1219
1220                if (Cache[I].InstBroken() == false)
1221                   break;
1222             }
1223
1224             if (Cache[I].InstBroken() == false)
1225                break;
1226
1227             if (Start == End)
1228                break;
1229             Start++;
1230          }
1231
1232          if (Cache[I].InstBroken() == false)
1233             break;
1234       }
1235
1236       if (Cache[I].InstBroken() == true)
1237          continue;
1238
1239       // Restart again.
1240       if (K == LastStop)
1241          return _error->Error("Internal Error, pkgProblemResolver::ResolveByKeep is looping on package %s.",I.Name());
1242       LastStop = K;
1243       K = PList - 1;
1244    }
1245
1246    return true;
1247 }
1248                                                                         /*}}}*/
1249 // ProblemResolver::InstallProtect - Install all protected packages     /*{{{*/
1250 // ---------------------------------------------------------------------
1251 /* This is used to make sure protected packages are installed */
1252 void pkgProblemResolver::InstallProtect()
1253 {
1254    pkgDepCache::ActionGroup group(Cache);
1255
1256    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
1257    {
1258       if ((Flags[I->ID] & Protected) == Protected)
1259       {
1260          if ((Flags[I->ID] & ToRemove) == ToRemove)
1261             Cache.MarkDelete(I);
1262          else
1263          {
1264             // preserve the information whether the package was auto
1265             // or manually installed
1266             bool autoInst = (Cache[I].Flags & pkgCache::Flag::Auto);
1267             Cache.MarkInstall(I, false, 0, !autoInst);
1268          }
1269       }
1270    }
1271 }
1272                                                                         /*}}}*/
1273
1274 // PrioSortList - Sort a list of versions by priority                   /*{{{*/
1275 // ---------------------------------------------------------------------
1276 /* This is ment to be used in conjunction with AllTargets to get a list
1277    of versions ordered by preference. */
1278 static pkgCache *PrioCache;
1279 static int PrioComp(const void *A,const void *B)
1280 {
1281    pkgCache::VerIterator L(*PrioCache,*(pkgCache::Version **)A);
1282    pkgCache::VerIterator R(*PrioCache,*(pkgCache::Version **)B);
1283
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    if ((L.ParentPkg()->Flags & pkgCache::Flag::Essential) != pkgCache::Flag::Essential &&
1288        (R.ParentPkg()->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
1289      return -1;
1290
1291    if (L->Priority != R->Priority)
1292       return R->Priority - L->Priority;
1293    return strcmp(L.ParentPkg().Name(),R.ParentPkg().Name());
1294 }
1295 void pkgPrioSortList(pkgCache &Cache,pkgCache::Version **List)
1296 {
1297    unsigned long Count = 0;
1298    PrioCache = &Cache;
1299    for (pkgCache::Version **I = List; *I != 0; I++)
1300       Count++;
1301    qsort(List,Count,sizeof(*List),PrioComp);
1302 }
1303                                                                         /*}}}*/
1304
1305 // CacheFile::ListUpdate - update the cache files                       /*{{{*/
1306 // ---------------------------------------------------------------------
1307 /* This is a simple wrapper to update the cache. it will fetch stuff
1308  * from the network (or any other sources defined in sources.list)
1309  */
1310 bool ListUpdate(pkgAcquireStatus &Stat,
1311                 pkgSourceList &List,
1312                 int PulseInterval)
1313 {
1314    pkgAcquire::RunResult res;
1315    pkgAcquire Fetcher(&Stat);
1316
1317    // Populate it with the source selection
1318    if (List.GetIndexes(&Fetcher) == false)
1319          return false;
1320
1321    // Run scripts
1322    RunScripts("APT::Update::Pre-Invoke");
1323
1324    // check arguments
1325    if(PulseInterval>0)
1326       res = Fetcher.Run(PulseInterval);
1327    else
1328       res = Fetcher.Run();
1329
1330    if (res == pkgAcquire::Failed)
1331       return false;
1332
1333    bool Failed = false;
1334    bool TransientNetworkFailure = false;
1335    for (pkgAcquire::ItemIterator I = Fetcher.ItemsBegin();
1336         I != Fetcher.ItemsEnd(); I++)
1337    {
1338       if ((*I)->Status == pkgAcquire::Item::StatDone)
1339          continue;
1340
1341       (*I)->Finished();
1342
1343       _error->Warning(_("Failed to fetch %s  %s\n"),(*I)->DescURI().c_str(),
1344               (*I)->ErrorText.c_str());
1345
1346       if ((*I)->Status == pkgAcquire::Item::StatTransientNetworkError)
1347       {
1348          TransientNetworkFailure = true;
1349          continue;
1350       }
1351
1352       Failed = true;
1353    }
1354
1355    // Clean out any old list files
1356    // Keep "APT::Get::List-Cleanup" name for compatibility, but
1357    // this is really a global option for the APT library now
1358    if (!TransientNetworkFailure && !Failed &&
1359        (_config->FindB("APT::Get::List-Cleanup",true) == true &&
1360         _config->FindB("APT::List-Cleanup",true) == true))
1361    {
1362       if (Fetcher.Clean(_config->FindDir("Dir::State::lists")) == false ||
1363           Fetcher.Clean(_config->FindDir("Dir::State::lists") + "partial/") == false)
1364          // something went wrong with the clean
1365          return false;
1366    }
1367
1368    if (TransientNetworkFailure == true)
1369       _error->Warning(_("Some index files failed to download, they have been ignored, or old ones used instead."));
1370    else if (Failed == true)
1371       return _error->Error(_("Some index files failed to download, they have been ignored, or old ones used instead."));
1372
1373
1374    // Run the scripts if all was fine
1375    RunScripts("APT::Update::Post-Invoke");
1376    return true;
1377 }
1378                                                                         /*}}}*/