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