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