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