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