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