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