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