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 // 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    // Important Required Standard Optional Extra
 492    signed short PrioMap[] = {
 493       0,
 494       _config->FindI("pkgProblemResolver::Scores::Important",3),
 495       _config->FindI("pkgProblemResolver::Scores::Required",2),
 496       _config->FindI("pkgProblemResolver::Scores::Standard",1),
 497       _config->FindI("pkgProblemResolver::Scores::Optional",-1),
 498       _config->FindI("pkgProblemResolver::Scores::Extra",-2)
 499    };
 500    signed short PrioEssentials = _config->FindI("pkgProblemResolver::Scores::Essentials",100);
 501    signed short PrioInstalledAndNotObsolete = _config->FindI("pkgProblemResolver::Scores::NotObsolete",1);
 502    signed short PrioDepends = _config->FindI("pkgProblemResolver::Scores::Depends",1);
 503    signed short PrioRecommends = _config->FindI("pkgProblemResolver::Scores::Recommends",1);
 504    signed short AddProtected = _config->FindI("pkgProblemResolver::Scores::AddProtected",10000);
 505    signed short AddEssential = _config->FindI("pkgProblemResolver::Scores::AddEssential",5000);
 506
 507    if (_config->FindB("Debug::pkgProblemResolver::ShowScores",false) == true)
 508       clog << "Settings used to calculate pkgProblemResolver::Scores::" << endl
 509          << "  Important => " << PrioMap[1] << endl
 510          << "  Required => " << PrioMap[2] << endl
 511          << "  Standard => " << PrioMap[3] << endl
 512          << "  Optional => " << PrioMap[4] << endl
 513          << "  Extra => " << PrioMap[5] << endl
 514          << "  Essentials => " << PrioEssentials << endl
 515          << "  InstalledAndNotObsolete => " << PrioInstalledAndNotObsolete << endl
 516          << "  Depends => " << PrioDepends << endl
 517          << "  Recommends => " << PrioRecommends << endl
 518          << "  AddProtected => " << AddProtected << endl
 519          << "  AddEssential => " << AddEssential << endl;
 520
 521    // Generate the base scores for a package based on its properties
 522    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 523    {
 524       if (Cache[I].InstallVer == 0)
 525          continue;
 526
 527       signed short &Score = Scores[I->ID];
 528
 529       /* This is arbitrary, it should be high enough to elevate an
 530          essantial package above most other packages but low enough
 531          to allow an obsolete essential packages to be removed by
 532          a conflicts on a powerfull normal package (ie libc6) */
 533       if ((I->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
 534          Score += PrioEssentials;
 535
 536       // We transform the priority
 537       if (Cache[I].InstVerIter(Cache)->Priority <= 5)
 538          Score += PrioMap[Cache[I].InstVerIter(Cache)->Priority];
 539
 540       /* This helps to fix oddball problems with conflicting packages
 541          on the same level. We enhance the score of installed packages
 542          if those are not obsolete
 543       */
 544       if (I->CurrentVer != 0 && Cache[I].CandidateVer != 0 && Cache[I].CandidateVerIter(Cache).Downloadable())
 545          Score += PrioInstalledAndNotObsolete;
 546    }
 547
 548    // Now that we have the base scores we go and propogate dependencies
 549    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 550    {
 551       if (Cache[I].InstallVer == 0)
 552          continue;
 553
 554       for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false; D++)
 555       {
 556          if (D->Type == pkgCache::Dep::Depends ||
 557              D->Type == pkgCache::Dep::PreDepends)
 558             Scores[D.TargetPkg()->ID] += PrioDepends;
 559          else if (D->Type == pkgCache::Dep::Recommends)
 560             Scores[D.TargetPkg()->ID] += PrioRecommends;
 561       }
 562    }
 563
 564    // Copy the scores to advoid additive looping
 565    SPtrArray<signed short> OldScores = new signed short[Size];
 566    memcpy(OldScores,Scores,sizeof(*Scores)*Size);
 567
 568    /* Now we cause 1 level of dependency inheritance, that is we add the
 569       score of the packages that depend on the target Package. This
 570       fortifies high scoring packages */
 571    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 572    {
 573       if (Cache[I].InstallVer == 0)
 574          continue;
 575
 576       for (pkgCache::DepIterator D = I.RevDependsList(); D.end() == false; D++)
 577       {
 578          // Only do it for the install version
 579          if ((pkgCache::Version *)D.ParentVer() != Cache[D.ParentPkg()].InstallVer ||
 580              (D->Type != pkgCache::Dep::Depends &&
 581               D->Type != pkgCache::Dep::PreDepends &&
 582               D->Type != pkgCache::Dep::Recommends))
 583             continue;
 584
 585          Scores[I->ID] += abs(OldScores[D.ParentPkg()->ID]);
 586       }
 587    }
 588
 589    /* Now we propogate along provides. This makes the packages that
 590       provide important packages extremely important */
 591    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 592    {
 593       for (pkgCache::PrvIterator P = I.ProvidesList(); P.end() == false; P++)
 594       {
 595          // Only do it once per package
 596          if ((pkgCache::Version *)P.OwnerVer() != Cache[P.OwnerPkg()].InstallVer)
 597             continue;
 598          Scores[P.OwnerPkg()->ID] += abs(Scores[I->ID] - OldScores[I->ID]);
 599       }
 600    }
 601
 602    /* Protected things are pushed really high up. This number should put them
 603       ahead of everything */
 604    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 605    {
 606       if ((Flags[I->ID] & Protected) != 0)
 607          Scores[I->ID] += AddProtected;
 608       if ((I->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
 609          Scores[I->ID] += AddEssential;
 610    }
 611 }
 612                                                                         /*}}}*/
 613 // ProblemResolver::DoUpgrade - Attempt to upgrade this package         /*{{{*/
 614 // ---------------------------------------------------------------------
 615 /* This goes through and tries to reinstall packages to make this package
 616    installable */
 617 bool pkgProblemResolver::DoUpgrade(pkgCache::PkgIterator Pkg)
 618 {
 619    pkgDepCache::ActionGroup group(Cache);
 620
 621    if ((Flags[Pkg->ID] & Upgradable) == 0 || Cache[Pkg].Upgradable() == false)
 622       return false;
 623    if ((Flags[Pkg->ID] & Protected) == Protected)
 624       return false;
 625
 626    Flags[Pkg->ID] &= ~Upgradable;
 627
 628    bool WasKept = Cache[Pkg].Keep();
 629    Cache.MarkInstall(Pkg, false, 0, false);
 630
 631    // This must be a virtual package or something like that.
 632    if (Cache[Pkg].InstVerIter(Cache).end() == true)
 633       return false;
 634
 635    // Isolate the problem dependency
 636    bool Fail = false;
 637    for (pkgCache::DepIterator D = Cache[Pkg].InstVerIter(Cache).DependsList(); D.end() == false;)
 638    {
 639       // Compute a single dependency element (glob or)
 640       pkgCache::DepIterator Start = D;
 641       pkgCache::DepIterator End = D;
 642       unsigned char State = 0;
 643       for (bool LastOR = true; D.end() == false && LastOR == true;)
 644       {
 645          State |= Cache[D];
 646          LastOR = (D->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or;
 647          D++;
 648          if (LastOR == true)
 649             End = D;
 650       }
 651
 652       // We only worry about critical deps.
 653       if (End.IsCritical() != true)
 654          continue;
 655
 656       // Iterate over all the members in the or group
 657       while (1)
 658       {
 659          // Dep is ok now
 660          if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
 661             break;
 662
 663          // Do not change protected packages
 664          PkgIterator P = Start.SmartTargetPkg();
 665          if ((Flags[P->ID] & Protected) == Protected)
 666          {
 667             if (Debug == true)
 668                clog << "    Reinst Failed because of protected " << P.Name() << endl;
 669             Fail = true;
 670          }
 671          else
 672          {
 673             // Upgrade the package if the candidate version will fix the problem.
 674             if ((Cache[Start] & pkgDepCache::DepCVer) == pkgDepCache::DepCVer)
 675             {
 676                if (DoUpgrade(P) == false)
 677                {
 678                   if (Debug == true)
 679                      clog << "    Reinst Failed because of " << P.Name() << endl;
 680                   Fail = true;
 681                }
 682                else
 683                {
 684                   Fail = false;
 685                   break;
 686                }
 687             }
 688             else
 689             {
 690                /* We let the algorithm deal with conflicts on its next iteration,
 691                 it is much smarter than us */
 692                if (Start->Type == pkgCache::Dep::Conflicts ||
 693                    Start->Type == pkgCache::Dep::DpkgBreaks ||
 694                    Start->Type == pkgCache::Dep::Obsoletes)
 695                    break;
 696
 697                if (Debug == true)
 698                   clog << "    Reinst Failed early because of " << Start.TargetPkg().Name() << endl;
 699                Fail = true;
 700             }
 701          }
 702
 703          if (Start == End)
 704             break;
 705          Start++;
 706       }
 707       if (Fail == true)
 708          break;
 709    }
 710
 711    // Undo our operations - it might be smart to undo everything this did..
 712    if (Fail == true)
 713    {
 714       if (WasKept == true)
 715          Cache.MarkKeep(Pkg, false, false);
 716       else
 717          Cache.MarkDelete(Pkg);
 718       return false;
 719    }
 720
 721    if (Debug == true)
 722       clog << "  Re-Instated " << Pkg.Name() << endl;
 723    return true;
 724 }
 725                                                                         /*}}}*/
 726 // ProblemResolver::Resolve - Run the resolution pass                   /*{{{*/
 727 // ---------------------------------------------------------------------
 728 /* This routines works by calculating a score for each package. The score
 729    is derived by considering the package's priority and all reverse
 730    dependents giving an integer that reflects the amount of breakage that
 731    adjusting the package will inflict.
 732
 733    It goes from highest score to lowest and corrects all of the breaks by
 734    keeping or removing the dependant packages. If that fails then it removes
 735    the package itself and goes on. The routine should be able to intelligently
 736    go from any broken state to a fixed state.
 737
 738    The BrokenFix flag enables a mode where the algorithm tries to
 739    upgrade packages to advoid problems. */
 740 bool pkgProblemResolver::Resolve(bool BrokenFix)
 741 {
 742    pkgDepCache::ActionGroup group(Cache);
 743
 744    unsigned long Size = Cache.Head().PackageCount;
 745
 746    // Record which packages are marked for install
 747    bool Again = false;
 748    do
 749    {
 750       Again = false;
 751       for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 752       {
 753          if (Cache[I].Install() == true)
 754             Flags[I->ID] |= PreInstalled;
 755          else
 756          {
 757             if (Cache[I].InstBroken() == true && BrokenFix == true)
 758             {
 759                Cache.MarkInstall(I, false, 0, false);
 760                if (Cache[I].Install() == true)
 761                   Again = true;
 762             }
 763
 764             Flags[I->ID] &= ~PreInstalled;
 765          }
 766          Flags[I->ID] |= Upgradable;
 767       }
 768    }
 769    while (Again == true);
 770
 771    if (Debug == true)
 772       clog << "Starting" << endl;
 773
 774    MakeScores();
 775
 776    /* We have to order the packages so that the broken fixing pass
 777       operates from highest score to lowest. This prevents problems when
 778       high score packages cause the removal of lower score packages that
 779       would cause the removal of even lower score packages. */
 780    SPtrArray<pkgCache::Package *> PList = new pkgCache::Package *[Size];
 781    pkgCache::Package **PEnd = PList;
 782    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 783       *PEnd++ = I;
 784    This = this;
 785    qsort(PList,PEnd - PList,sizeof(*PList),&ScoreSort);
 786
 787    if (_config->FindB("Debug::pkgProblemResolver::ShowScores",false) == true)
 788    {
 789       clog << "Show Scores" << endl;
 790       for (pkgCache::Package **K = PList; K != PEnd; K++)
 791          if (Scores[(*K)->ID] != 0)
 792          {
 793            pkgCache::PkgIterator Pkg(Cache,*K);
 794            clog << Scores[(*K)->ID] << ' ' << Pkg << std::endl;
 795          }
 796    }
 797
 798    if (Debug == true)
 799       clog << "Starting 2" << endl;
 800
 801    /* Now consider all broken packages. For each broken package we either
 802       remove the package or fix it's problem. We do this once, it should
 803       not be possible for a loop to form (that is a < b < c and fixing b by
 804       changing a breaks c) */
 805    bool Change = true;
 806    for (int Counter = 0; Counter != 10 && Change == true; Counter++)
 807    {
 808       Change = false;
 809       for (pkgCache::Package **K = PList; K != PEnd; K++)
 810       {
 811          pkgCache::PkgIterator I(Cache,*K);
 812
 813          /* We attempt to install this and see if any breaks result,
 814             this takes care of some strange cases */
 815          if (Cache[I].CandidateVer != Cache[I].InstallVer &&
 816              I->CurrentVer != 0 && Cache[I].InstallVer != 0 &&
 817              (Flags[I->ID] & PreInstalled) != 0 &&
 818              (Flags[I->ID] & Protected) == 0 &&
 819              (Flags[I->ID] & ReInstateTried) == 0)
 820          {
 821             if (Debug == true)
 822                clog << " Try to Re-Instate " << I.Name() << endl;
 823             unsigned long OldBreaks = Cache.BrokenCount();
 824             pkgCache::Version *OldVer = Cache[I].InstallVer;
 825             Flags[I->ID] &= ReInstateTried;
 826
 827             Cache.MarkInstall(I, false, 0, false);
 828             if (Cache[I].InstBroken() == true ||
 829                 OldBreaks < Cache.BrokenCount())
 830             {
 831                if (OldVer == 0)
 832                   Cache.MarkDelete(I);
 833                else
 834                   Cache.MarkKeep(I, false, false);
 835             }
 836             else
 837                if (Debug == true)
 838                   clog << "Re-Instated " << I.Name() << " (" << OldBreaks << " vs " << Cache.BrokenCount() << ')' << endl;
 839          }
 840
 841          if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false)
 842             continue;
 843
 844          if (Debug == true)
 845             clog << "Investigating " << I.Name() << endl;
 846
 847          // Isolate the problem dependency
 848          PackageKill KillList[100];
 849          PackageKill *LEnd = KillList;
 850          bool InOr = false;
 851          pkgCache::DepIterator Start;
 852          pkgCache::DepIterator End;
 853          PackageKill *OldEnd = LEnd;
 854
 855          enum {OrRemove,OrKeep} OrOp = OrRemove;
 856          for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList();
 857               D.end() == false || InOr == true;)
 858          {
 859             // Compute a single dependency element (glob or)
 860             if (Start == End)
 861             {
 862                // Decide what to do
 863                if (InOr == true)
 864                {
 865                   if (OldEnd == LEnd && OrOp == OrRemove)
 866                   {
 867                      if ((Flags[I->ID] & Protected) != Protected)
 868                      {
 869                         if (Debug == true)
 870                            clog << "  Or group remove for " << I.Name() << endl;
 871                         Cache.MarkDelete(I);
 872                         Change = true;
 873                      }
 874                   }
 875                   if (OldEnd == LEnd && OrOp == OrKeep)
 876                   {
 877                      if (Debug == true)
 878                         clog << "  Or group keep for " << I.Name() << endl;
 879                      Cache.MarkKeep(I, false, false);
 880                      Change = true;
 881                   }
 882                }
 883
 884                /* We do an extra loop (as above) to finalize the or group
 885                   processing */
 886                InOr = false;
 887                OrOp = OrRemove;
 888                D.GlobOr(Start,End);
 889                if (Start.end() == true)
 890                   break;
 891
 892                // We only worry about critical deps.
 893                if (End.IsCritical() != true)
 894                   continue;
 895
 896                InOr = Start != End;
 897                OldEnd = LEnd;
 898             }
 899             else
 900             {
 901                Start++;
 902                // We only worry about critical deps.
 903                if (Start.IsCritical() != true)
 904                   continue;
 905             }
 906
 907             // Dep is ok
 908             if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
 909             {
 910                InOr = false;
 911                continue;
 912             }
 913
 914             if (Debug == true)
 915                clog << "Package " << I.Name() << " has broken " << Start.DepType() << " on " << Start.TargetPkg().Name() << endl;
 916
 917             /* Look across the version list. If there are no possible
 918                targets then we keep the package and bail. This is necessary
 919                if a package has a dep on another package that cant be found */
 920             SPtrArray<pkgCache::Version *> VList = Start.AllTargets();
 921             if (*VList == 0 && (Flags[I->ID] & Protected) != Protected &&
 922                 Start->Type != pkgCache::Dep::Conflicts &&
 923                 Start->Type != pkgCache::Dep::DpkgBreaks &&
 924                 Start->Type != pkgCache::Dep::Obsoletes &&
 925                 Cache[I].NowBroken() == false)
 926             {
 927                if (InOr == true)
 928                {
 929                   /* No keep choice because the keep being OK could be the
 930                      result of another element in the OR group! */
 931                   continue;
 932                }
 933
 934                Change = true;
 935                Cache.MarkKeep(I, false, false);
 936                break;
 937             }
 938
 939             bool Done = false;
 940             for (pkgCache::Version **V = VList; *V != 0; V++)
 941             {
 942                pkgCache::VerIterator Ver(Cache,*V);
 943                pkgCache::PkgIterator Pkg = Ver.ParentPkg();
 944
 945                if (Debug == true)
 946                   clog << "  Considering " << Pkg.Name() << ' ' << (int)Scores[Pkg->ID] <<
 947                   " as a solution to " << I.Name() << ' ' << (int)Scores[I->ID] << endl;
 948
 949                /* Try to fix the package under consideration rather than
 950                   fiddle with the VList package */
 951                if (Scores[I->ID] <= Scores[Pkg->ID] ||
 952                    ((Cache[Start] & pkgDepCache::DepNow) == 0 &&
 953                     End->Type != pkgCache::Dep::Conflicts &&
 954                     End->Type != pkgCache::Dep::DpkgBreaks &&
 955                     End->Type != pkgCache::Dep::Obsoletes))
 956                {
 957                   // Try a little harder to fix protected packages..
 958                   if ((Flags[I->ID] & Protected) == Protected)
 959                   {
 960                      if (DoUpgrade(Pkg) == true)
 961                      {
 962                         if (Scores[Pkg->ID] > Scores[I->ID])
 963                            Scores[Pkg->ID] = Scores[I->ID];
 964                         break;
 965                      }
 966
 967                      continue;
 968                   }
 969
 970                   /* See if a keep will do, unless the package is protected,
 971                      then installing it will be necessary */
 972                   bool Installed = Cache[I].Install();
 973                   Cache.MarkKeep(I, false, false);
 974                   if (Cache[I].InstBroken() == false)
 975                   {
 976                      // Unwind operation will be keep now
 977                      if (OrOp == OrRemove)
 978                         OrOp = OrKeep;
 979
 980                      // Restore
 981                      if (InOr == true && Installed == true)
 982                         Cache.MarkInstall(I, false, 0, false);
 983
 984                      if (Debug == true)
 985                         clog << "  Holding Back " << I.Name() << " rather than change " << Start.TargetPkg().Name() << endl;
 986                   }
 987                   else
 988                   {
 989                      if (BrokenFix == false || DoUpgrade(I) == false)
 990                      {
 991                         // Consider other options
 992                         if (InOr == false)
 993                         {
 994                            if (Debug == true)
 995                               clog << "  Removing " << I.Name() << " rather than change " << Start.TargetPkg().Name() << endl;
 996                            Cache.MarkDelete(I);
 997                            if (Counter > 1 && Scores[Pkg->ID] > Scores[I->ID])
 998                               Scores[I->ID] = Scores[Pkg->ID];
 999                         }
1000                      }
1001                   }
1002
1003                   Change = true;
1004                   Done = true;
1005                   break;
1006                }
1007                else
1008                {
1009                   /* This is a conflicts, and the version we are looking
1010                      at is not the currently selected version of the
1011                      package, which means it is not necessary to
1012                      remove/keep */
1013                   if (Cache[Pkg].InstallVer != Ver &&
1014                       (Start->Type == pkgCache::Dep::Conflicts ||
1015                        Start->Type == pkgCache::Dep::Obsoletes))
1016                      continue;
1017
1018                   if (Start->Type == pkgCache::Dep::DpkgBreaks)
1019                   {
1020                      // first, try upgradring the package, if that
1021                      // does not help, the breaks goes onto the
1022                      // kill list
1023                      // FIXME: use DoUpgrade(Pkg) instead?
1024                      if (Cache[End] & pkgDepCache::DepGCVer)
1025                      {
1026                         if (Debug)
1027                            clog << "  Upgrading " << Pkg.Name() << " due to Breaks field in " << I.Name() << endl;
1028                         Cache.MarkInstall(Pkg, false, 0, false);
1029                         continue;
1030                      }
1031                   }
1032
1033                   // Skip adding to the kill list if it is protected
1034                   if ((Flags[Pkg->ID] & Protected) != 0)
1035                      continue;
1036
1037                   if (Debug == true)
1038                      clog << "  Added " << Pkg.Name() << " to the remove list" << endl;
1039
1040                   LEnd->Pkg = Pkg;
1041                   LEnd->Dep = End;
1042                   LEnd++;
1043
1044                   if (Start->Type != pkgCache::Dep::Conflicts &&
1045                       Start->Type != pkgCache::Dep::Obsoletes)
1046                      break;
1047                }
1048             }
1049
1050             // Hm, nothing can possibly satisify this dep. Nuke it.
1051             if (VList[0] == 0 &&
1052                 Start->Type != pkgCache::Dep::Conflicts &&
1053                 Start->Type != pkgCache::Dep::DpkgBreaks &&
1054                 Start->Type != pkgCache::Dep::Obsoletes &&
1055                 (Flags[I->ID] & Protected) != Protected)
1056             {
1057                bool Installed = Cache[I].Install();
1058                Cache.MarkKeep(I);
1059                if (Cache[I].InstBroken() == false)
1060                {
1061                   // Unwind operation will be keep now
1062                   if (OrOp == OrRemove)
1063                      OrOp = OrKeep;
1064
1065                   // Restore
1066                   if (InOr == true && Installed == true)
1067                      Cache.MarkInstall(I, false, 0, false);
1068
1069                   if (Debug == true)
1070                      clog << "  Holding Back " << I.Name() << " because I can't find " << Start.TargetPkg().Name() << endl;
1071                }
1072                else
1073                {
1074                   if (Debug == true)
1075                      clog << "  Removing " << I.Name() << " because I can't find " << Start.TargetPkg().Name() << endl;
1076                   if (InOr == false)
1077                      Cache.MarkDelete(I);
1078                }
1079
1080                Change = true;
1081                Done = true;
1082             }
1083
1084             // Try some more
1085             if (InOr == true)
1086                continue;
1087
1088             if (Done == true)
1089                break;
1090          }
1091
1092          // Apply the kill list now
1093          if (Cache[I].InstallVer != 0)
1094          {
1095             for (PackageKill *J = KillList; J != LEnd; J++)
1096             {
1097                Change = true;
1098                if ((Cache[J->Dep] & pkgDepCache::DepGNow) == 0)
1099                {
1100                   if (J->Dep->Type == pkgCache::Dep::Conflicts ||
1101                       J->Dep->Type == pkgCache::Dep::DpkgBreaks ||
1102                       J->Dep->Type == pkgCache::Dep::Obsoletes)
1103                   {
1104                      if (Debug == true)
1105                         clog << "  Fixing " << I.Name() << " via remove of " << J->Pkg.Name() << endl;
1106                      Cache.MarkDelete(J->Pkg);
1107                   }
1108                }
1109                else
1110                {
1111                   if (Debug == true)
1112                      clog << "  Fixing " << I.Name() << " via keep of " << J->Pkg.Name() << endl;
1113                   Cache.MarkKeep(J->Pkg, false, false);
1114                }
1115
1116                if (Counter > 1)
1117                {
1118                   if (Scores[I->ID] > Scores[J->Pkg->ID])
1119                      Scores[J->Pkg->ID] = Scores[I->ID];
1120                }
1121             }
1122          }
1123       }
1124    }
1125
1126    if (Debug == true)
1127       clog << "Done" << endl;
1128
1129    if (Cache.BrokenCount() != 0)
1130    {
1131       // See if this is the result of a hold
1132       pkgCache::PkgIterator I = Cache.PkgBegin();
1133       for (;I.end() != true; I++)
1134       {
1135          if (Cache[I].InstBroken() == false)
1136             continue;
1137          if ((Flags[I->ID] & Protected) != Protected)
1138             return _error->Error(_("Error, pkgProblemResolver::Resolve generated breaks, this may be caused by held packages."));
1139       }
1140       return _error->Error(_("Unable to correct problems, you have held broken packages."));
1141    }
1142
1143    // set the auto-flags (mvo: I'm not sure if we _really_ need this)
1144    pkgCache::PkgIterator I = Cache.PkgBegin();
1145    for (;I.end() != true; I++) {
1146       if (Cache[I].NewInstall() && !(Flags[I->ID] & PreInstalled)) {
1147          if(_config->FindI("Debug::pkgAutoRemove",false)) {
1148             std::clog << "Resolve installed new pkg: " << I.Name()
1149                       << " (now marking it as auto)" << std::endl;
1150          }
1151          Cache[I].Flags |= pkgCache::Flag::Auto;
1152       }
1153    }
1154
1155
1156    return true;
1157 }
1158                                                                         /*}}}*/
1159 // ProblemResolver::ResolveByKeep - Resolve problems using keep         /*{{{*/
1160 // ---------------------------------------------------------------------
1161 /* This is the work horse of the soft upgrade routine. It is very gental
1162    in that it does not install or remove any packages. It is assumed that the
1163    system was non-broken previously. */
1164 bool pkgProblemResolver::ResolveByKeep()
1165 {
1166    pkgDepCache::ActionGroup group(Cache);
1167
1168    unsigned long Size = Cache.Head().PackageCount;
1169
1170    MakeScores();
1171
1172    /* We have to order the packages so that the broken fixing pass
1173       operates from highest score to lowest. This prevents problems when
1174       high score packages cause the removal of lower score packages that
1175       would cause the removal of even lower score packages. */
1176    pkgCache::Package **PList = new pkgCache::Package *[Size];
1177    pkgCache::Package **PEnd = PList;
1178    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
1179       *PEnd++ = I;
1180    This = this;
1181    qsort(PList,PEnd - PList,sizeof(*PList),&ScoreSort);
1182
1183    if (_config->FindB("Debug::pkgProblemResolver::ShowScores",false) == true)
1184    {
1185       clog << "Show Scores" << endl;
1186       for (pkgCache::Package **K = PList; K != PEnd; K++)
1187          if (Scores[(*K)->ID] != 0)
1188          {
1189            pkgCache::PkgIterator Pkg(Cache,*K);
1190            clog << Scores[(*K)->ID] << ' ' << Pkg << std::endl;
1191          }
1192    }
1193
1194    if (Debug == true)
1195       clog << "Entering ResolveByKeep" << endl;
1196
1197    // Consider each broken package
1198    pkgCache::Package **LastStop = 0;
1199    for (pkgCache::Package **K = PList; K != PEnd; K++)
1200    {
1201       pkgCache::PkgIterator I(Cache,*K);
1202
1203       if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false)
1204          continue;
1205
1206       /* Keep the package. If this works then great, otherwise we have
1207          to be significantly more agressive and manipulate its dependencies */
1208       if ((Flags[I->ID] & Protected) == 0)
1209       {
1210          if (Debug == true)
1211             clog << "Keeping package " << I.Name() << endl;
1212          Cache.MarkKeep(I, false, false);
1213          if (Cache[I].InstBroken() == false)
1214          {
1215             K = PList - 1;
1216             continue;
1217          }
1218       }
1219
1220       // Isolate the problem dependencies
1221       for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false;)
1222       {
1223          DepIterator Start;
1224          DepIterator End;
1225          D.GlobOr(Start,End);
1226
1227          // We only worry about critical deps.
1228          if (End.IsCritical() != true)
1229             continue;
1230
1231          // Dep is ok
1232          if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
1233             continue;
1234
1235          /* Hm, the group is broken.. I suppose the best thing to do is to
1236             is to try every combination of keep/not-keep for the set, but thats
1237             slow, and this never happens, just be conservative and assume the
1238             list of ors is in preference and keep till it starts to work. */
1239          while (true)
1240          {
1241             if (Debug == true)
1242                clog << "Package " << I.Name() << " has broken " << Start.DepType() << " on " << Start.TargetPkg().Name() << endl;
1243
1244             // Look at all the possible provides on this package
1245             SPtrArray<pkgCache::Version *> VList = Start.AllTargets();
1246             for (pkgCache::Version **V = VList; *V != 0; V++)
1247             {
1248                pkgCache::VerIterator Ver(Cache,*V);
1249                pkgCache::PkgIterator Pkg = Ver.ParentPkg();
1250
1251                // It is not keepable
1252                if (Cache[Pkg].InstallVer == 0 ||
1253                    Pkg->CurrentVer == 0)
1254                   continue;
1255
1256                if ((Flags[I->ID] & Protected) == 0)
1257                {
1258                   if (Debug == true)
1259                      clog << "  Keeping Package " << Pkg.Name() << " due to " << Start.DepType() << endl;
1260                   Cache.MarkKeep(Pkg, false, false);
1261                }
1262
1263                if (Cache[I].InstBroken() == false)
1264                   break;
1265             }
1266
1267             if (Cache[I].InstBroken() == false)
1268                break;
1269
1270             if (Start == End)
1271                break;
1272             Start++;
1273          }
1274
1275          if (Cache[I].InstBroken() == false)
1276             break;
1277       }
1278
1279       if (Cache[I].InstBroken() == true)
1280          continue;
1281
1282       // Restart again.
1283       if (K == LastStop)
1284          return _error->Error("Internal Error, pkgProblemResolver::ResolveByKeep is looping on package %s.",I.Name());
1285       LastStop = K;
1286       K = PList - 1;
1287    }
1288
1289    return true;
1290 }
1291                                                                         /*}}}*/
1292 // ProblemResolver::InstallProtect - Install all protected packages     /*{{{*/
1293 // ---------------------------------------------------------------------
1294 /* This is used to make sure protected packages are installed */
1295 void pkgProblemResolver::InstallProtect()
1296 {
1297    pkgDepCache::ActionGroup group(Cache);
1298
1299    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
1300    {
1301       if ((Flags[I->ID] & Protected) == Protected)
1302       {
1303          if ((Flags[I->ID] & ToRemove) == ToRemove)
1304             Cache.MarkDelete(I);
1305          else
1306          {
1307             // preserve the information whether the package was auto
1308             // or manually installed
1309             bool autoInst = (Cache[I].Flags & pkgCache::Flag::Auto);
1310             Cache.MarkInstall(I, false, 0, !autoInst);
1311          }
1312       }
1313    }
1314 }
1315                                                                         /*}}}*/
1316 // PrioSortList - Sort a list of versions by priority                   /*{{{*/
1317 // ---------------------------------------------------------------------
1318 /* This is ment to be used in conjunction with AllTargets to get a list
1319    of versions ordered by preference. */
1320 static pkgCache *PrioCache;
1321 static int PrioComp(const void *A,const void *B)
1322 {
1323    pkgCache::VerIterator L(*PrioCache,*(pkgCache::Version **)A);
1324    pkgCache::VerIterator R(*PrioCache,*(pkgCache::Version **)B);
1325
1326    if ((L.ParentPkg()->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential &&
1327        (R.ParentPkg()->Flags & pkgCache::Flag::Essential) != pkgCache::Flag::Essential)
1328      return 1;
1329    if ((L.ParentPkg()->Flags & pkgCache::Flag::Essential) != pkgCache::Flag::Essential &&
1330        (R.ParentPkg()->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
1331      return -1;
1332
1333    if (L->Priority != R->Priority)
1334       return R->Priority - L->Priority;
1335    return strcmp(L.ParentPkg().Name(),R.ParentPkg().Name());
1336 }
1337 void pkgPrioSortList(pkgCache &Cache,pkgCache::Version **List)
1338 {
1339    unsigned long Count = 0;
1340    PrioCache = &Cache;
1341    for (pkgCache::Version **I = List; *I != 0; I++)
1342       Count++;
1343    qsort(List,Count,sizeof(*List),PrioComp);
1344 }
1345                                                                         /*}}}*/
1346 // CacheFile::ListUpdate - update the cache files                       /*{{{*/
1347 // ---------------------------------------------------------------------
1348 /* This is a simple wrapper to update the cache. it will fetch stuff
1349  * from the network (or any other sources defined in sources.list)
1350  */
1351 bool ListUpdate(pkgAcquireStatus &Stat,
1352                 pkgSourceList &List,
1353                 int PulseInterval)
1354 {
1355    pkgAcquire::RunResult res;
1356    pkgAcquire Fetcher(&Stat);
1357
1358    // Populate it with the source selection
1359    if (List.GetIndexes(&Fetcher) == false)
1360          return false;
1361
1362    // Run scripts
1363    RunScripts("APT::Update::Pre-Invoke");
1364
1365    // check arguments
1366    if(PulseInterval>0)
1367       res = Fetcher.Run(PulseInterval);
1368    else
1369       res = Fetcher.Run();
1370
1371    if (res == pkgAcquire::Failed)
1372       return false;
1373
1374    bool Failed = false;
1375    bool TransientNetworkFailure = false;
1376    for (pkgAcquire::ItemIterator I = Fetcher.ItemsBegin();
1377         I != Fetcher.ItemsEnd(); I++)
1378    {
1379       if ((*I)->Status == pkgAcquire::Item::StatDone)
1380          continue;
1381
1382       (*I)->Finished();
1383
1384       ::URI uri((*I)->DescURI());
1385       uri.User.clear();
1386       uri.Password.clear();
1387       string descUri = string(uri);
1388       _error->Warning(_("Failed to fetch %s  %s\n"), descUri.c_str(),
1389               (*I)->ErrorText.c_str());
1390
1391       if ((*I)->Status == pkgAcquire::Item::StatTransientNetworkError)
1392       {
1393          TransientNetworkFailure = true;
1394          continue;
1395       }
1396
1397       Failed = true;
1398    }
1399
1400    // Clean out any old list files
1401    // Keep "APT::Get::List-Cleanup" name for compatibility, but
1402    // this is really a global option for the APT library now
1403    if (!TransientNetworkFailure && !Failed &&
1404        (_config->FindB("APT::Get::List-Cleanup",true) == true &&
1405         _config->FindB("APT::List-Cleanup",true) == true))
1406    {
1407       if (Fetcher.Clean(_config->FindDir("Dir::State::lists")) == false ||
1408           Fetcher.Clean(_config->FindDir("Dir::State::lists") + "partial/") == false)
1409          // something went wrong with the clean
1410          return false;
1411    }
1412
1413    if (TransientNetworkFailure == true)
1414       _error->Warning(_("Some index files failed to download, they have been ignored, or old ones used instead."));
1415    else if (Failed == true)
1416       return _error->Error(_("Some index files failed to download, they have been ignored, or old ones used instead."));
1417
1418
1419    // Run the success scripts if all was fine
1420    if(!TransientNetworkFailure && !Failed)
1421       RunScripts("APT::Update::Post-Invoke-Success");
1422
1423    // Run the other scripts
1424    RunScripts("APT::Update::Post-Invoke");
1425    return true;
1426 }
1427                                                                         /*}}}*/