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