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