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