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    auto const ret = EDSP::ResolveExternal(solver.c_str(), Cache, 0, Progress);
 640    if (solver != "internal")
 641       return ret;
 642    return ResolveInternal(BrokenFix);
 643 }
 644                                                                         /*}}}*/
 645 // ProblemResolver::ResolveInternal - Run the resolution pass           /*{{{*/
 646 // ---------------------------------------------------------------------
 647 /* This routines works by calculating a score for each package. The score
 648    is derived by considering the package's priority and all reverse
 649    dependents giving an integer that reflects the amount of breakage that
 650    adjusting the package will inflict.
 651
 652    It goes from highest score to lowest and corrects all of the breaks by
 653    keeping or removing the dependent packages. If that fails then it removes
 654    the package itself and goes on. The routine should be able to intelligently
 655    go from any broken state to a fixed state.
 656
 657    The BrokenFix flag enables a mode where the algorithm tries to
 658    upgrade packages to advoid problems. */
 659 bool pkgProblemResolver::ResolveInternal(bool const BrokenFix)
 660 {
 661    pkgDepCache::ActionGroup group(Cache);
 662
 663    // Record which packages are marked for install
 664    bool Again = false;
 665    do
 666    {
 667       Again = false;
 668       for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
 669       {
 670          if (Cache[I].Install() == true)
 671             Flags[I->ID] |= PreInstalled;
 672          else
 673          {
 674             if (Cache[I].InstBroken() == true && BrokenFix == true)
 675             {
 676                Cache.MarkInstall(I, false, 0, false);
 677                if (Cache[I].Install() == true)
 678                   Again = true;
 679             }
 680
 681             Flags[I->ID] &= ~PreInstalled;
 682          }
 683          Flags[I->ID] |= Upgradable;
 684       }
 685    }
 686    while (Again == true);
 687
 688    if (Debug == true) {
 689       clog << "Starting pkgProblemResolver with broken count: "
 690            << Cache.BrokenCount() << endl;
 691    }
 692
 693    MakeScores();
 694
 695    unsigned long const Size = Cache.Head().PackageCount;
 696
 697    /* We have to order the packages so that the broken fixing pass
 698       operates from highest score to lowest. This prevents problems when
 699       high score packages cause the removal of lower score packages that
 700       would cause the removal of even lower score packages. */
 701    std::unique_ptr<pkgCache::Package *[]> PList(new pkgCache::Package *[Size]);
 702    pkgCache::Package **PEnd = PList.get();
 703    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
 704       *PEnd++ = I;
 705
 706    std::sort(PList.get(), PEnd, [this](Package *a, Package *b) { return ScoreSort(a, b) < 0; });
 707
 708    if (_config->FindB("Debug::pkgProblemResolver::ShowScores",false) == true)
 709    {
 710       clog << "Show Scores" << endl;
 711       for (pkgCache::Package **K = PList.get(); K != PEnd; K++)
 712          if (Scores[(*K)->ID] != 0)
 713          {
 714            pkgCache::PkgIterator Pkg(Cache,*K);
 715            clog << Scores[(*K)->ID] << ' ' << APT::PrettyPkg(&Cache, Pkg) << std::endl;
 716          }
 717    }
 718
 719    if (Debug == true) {
 720       clog << "Starting 2 pkgProblemResolver with broken count: "
 721            << Cache.BrokenCount() << endl;
 722    }
 723
 724    /* Now consider all broken packages. For each broken package we either
 725       remove the package or fix it's problem. We do this once, it should
 726       not be possible for a loop to form (that is a < b < c and fixing b by
 727       changing a breaks c) */
 728    bool Change = true;
 729    bool const TryFixByInstall = _config->FindB("pkgProblemResolver::FixByInstall", true);
 730    std::vector<PackageKill> KillList;
 731    for (int Counter = 0; Counter != 10 && Change == true; Counter++)
 732    {
 733       Change = false;
 734       for (pkgCache::Package **K = PList.get(); K != PEnd; K++)
 735       {
 736          pkgCache::PkgIterator I(Cache,*K);
 737
 738          /* We attempt to install this and see if any breaks result,
 739             this takes care of some strange cases */
 740          if (Cache[I].CandidateVer != Cache[I].InstallVer &&
 741              I->CurrentVer != 0 && Cache[I].InstallVer != 0 &&
 742              (Flags[I->ID] & PreInstalled) != 0 &&
 743              (Flags[I->ID] & Protected) == 0 &&
 744              (Flags[I->ID] & ReInstateTried) == 0)
 745          {
 746             if (Debug == true)
 747                clog << " Try to Re-Instate (" << Counter << ") " << I.FullName(false) << endl;
 748             unsigned long OldBreaks = Cache.BrokenCount();
 749             pkgCache::Version *OldVer = Cache[I].InstallVer;
 750             Flags[I->ID] &= ReInstateTried;
 751
 752             Cache.MarkInstall(I, false, 0, false);
 753             if (Cache[I].InstBroken() == true ||
 754                 OldBreaks < Cache.BrokenCount())
 755             {
 756                if (OldVer == 0)
 757                   Cache.MarkDelete(I, false, 0, false);
 758                else
 759                   Cache.MarkKeep(I, false, false);
 760             }
 761             else
 762                if (Debug == true)
 763                   clog << "Re-Instated " << I.FullName(false) << " (" << OldBreaks << " vs " << Cache.BrokenCount() << ')' << endl;
 764          }
 765
 766          if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false)
 767             continue;
 768
 769          if (Debug == true)
 770             clog << "Investigating (" << Counter << ") " << APT::PrettyPkg(&Cache, I) << endl;
 771
 772          // Isolate the problem dependency
 773          bool InOr = false;
 774          pkgCache::DepIterator Start;
 775          pkgCache::DepIterator End;
 776          size_t OldSize = 0;
 777
 778          KillList.resize(0);
 779
 780          enum {OrRemove,OrKeep} OrOp = OrRemove;
 781          for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList();
 782               D.end() == false || InOr == true;)
 783          {
 784             // Compute a single dependency element (glob or)
 785             if (Start == End)
 786             {
 787                // Decide what to do
 788                if (InOr == true && OldSize == KillList.size())
 789                {
 790                   if (OrOp == OrRemove)
 791                   {
 792                      if ((Flags[I->ID] & Protected) != Protected)
 793                      {
 794                         if (Debug == true)
 795                            clog << "  Or group remove for " << I.FullName(false) << endl;
 796                         Cache.MarkDelete(I, false, 0, false);
 797                         Change = true;
 798                      }
 799                   }
 800                   else if (OrOp == OrKeep)
 801                   {
 802                      if (Debug == true)
 803                         clog << "  Or group keep for " << I.FullName(false) << endl;
 804                      Cache.MarkKeep(I, false, false);
 805                      Change = true;
 806                   }
 807                }
 808
 809                /* We do an extra loop (as above) to finalize the or group
 810                   processing */
 811                InOr = false;
 812                OrOp = OrRemove;
 813                D.GlobOr(Start,End);
 814                if (Start.end() == true)
 815                   break;
 816
 817                // We only worry about critical deps.
 818                if (End.IsCritical() != true)
 819                   continue;
 820
 821                InOr = Start != End;
 822                OldSize = KillList.size();
 823             }
 824             else
 825             {
 826                ++Start;
 827                // We only worry about critical deps.
 828                if (Start.IsCritical() != true)
 829                   continue;
 830             }
 831
 832             // Dep is ok
 833             if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
 834             {
 835                InOr = false;
 836                continue;
 837             }
 838
 839             if (Debug == true)
 840                clog << "Broken " << APT::PrettyDep(&Cache, Start) << endl;
 841
 842             /* Look across the version list. If there are no possible
 843                targets then we keep the package and bail. This is necessary
 844                if a package has a dep on another package that can't be found */
 845             std::unique_ptr<pkgCache::Version *[]> VList(Start.AllTargets());
 846             if (VList[0] == 0 && (Flags[I->ID] & Protected) != Protected &&
 847                 Start.IsNegative() == false &&
 848                 Cache[I].NowBroken() == false)
 849             {
 850                if (InOr == true)
 851                {
 852                   /* No keep choice because the keep being OK could be the
 853                      result of another element in the OR group! */
 854                   continue;
 855                }
 856
 857                Change = true;
 858                Cache.MarkKeep(I, false, false);
 859                break;
 860             }
 861
 862             bool Done = false;
 863             for (pkgCache::Version **V = VList.get(); *V != 0; V++)
 864             {
 865                pkgCache::VerIterator Ver(Cache,*V);
 866                pkgCache::PkgIterator Pkg = Ver.ParentPkg();
 867
 868                /* This is a conflicts, and the version we are looking
 869                   at is not the currently selected version of the
 870                   package, which means it is not necessary to
 871                   remove/keep */
 872                if (Cache[Pkg].InstallVer != Ver && Start.IsNegative() == true)
 873                {
 874                   if (Debug)
 875                      clog << "  Conflicts//Breaks against version "
 876                           << Ver.VerStr() << " for " << Pkg.Name()
 877                           << " but that is not InstVer, ignoring"
 878                           << endl;
 879                   continue;
 880                }
 881
 882                if (Debug == true)
 883                   clog << "  Considering " << Pkg.FullName(false) << ' ' << Scores[Pkg->ID] <<
 884                   " as a solution to " << I.FullName(false) << ' ' << Scores[I->ID] << endl;
 885
 886                /* Try to fix the package under consideration rather than
 887                   fiddle with the VList package */
 888                if (Scores[I->ID] <= Scores[Pkg->ID] ||
 889                    ((Cache[Start] & pkgDepCache::DepNow) == 0 &&
 890                     End.IsNegative() == false))
 891                {
 892                   // Try a little harder to fix protected packages..
 893                   if ((Flags[I->ID] & Protected) == Protected)
 894                   {
 895                      if (DoUpgrade(Pkg) == true)
 896                      {
 897                         if (Scores[Pkg->ID] > Scores[I->ID])
 898                            Scores[Pkg->ID] = Scores[I->ID];
 899                         break;
 900                      }
 901
 902                      continue;
 903                   }
 904
 905                   /* See if a keep will do, unless the package is protected,
 906                      then installing it will be necessary */
 907                   bool Installed = Cache[I].Install();
 908                   Cache.MarkKeep(I, false, false);
 909                   if (Cache[I].InstBroken() == false)
 910                   {
 911                      // Unwind operation will be keep now
 912                      if (OrOp == OrRemove)
 913                         OrOp = OrKeep;
 914
 915                      // Restore
 916                      if (InOr == true && Installed == true)
 917                         Cache.MarkInstall(I, false, 0, false);
 918
 919                      if (Debug == true)
 920                         clog << "  Holding Back " << I.FullName(false) << " rather than change " << Start.TargetPkg().FullName(false) << endl;
 921                   }
 922                   else
 923                   {
 924                      if (BrokenFix == false || DoUpgrade(I) == false)
 925                      {
 926                         // Consider other options
 927                         if (InOr == false || Cache[I].Garbage == true)
 928                         {
 929                            if (Debug == true)
 930                               clog << "  Removing " << I.FullName(false) << " rather than change " << Start.TargetPkg().FullName(false) << endl;
 931                            Cache.MarkDelete(I, false, 0, false);
 932                            if (Counter > 1 && Scores[Pkg->ID] > Scores[I->ID])
 933                               Scores[I->ID] = Scores[Pkg->ID];
 934                         }
 935                         else if (TryFixByInstall == true &&
 936                                  Start.TargetPkg()->CurrentVer == 0 &&
 937                                  Cache[Start.TargetPkg()].Delete() == false &&
 938                                  (Flags[Start.TargetPkg()->ID] & ToRemove) != ToRemove &&
 939                                  Cache.GetCandidateVersion(Start.TargetPkg()).end() == false)
 940                         {
 941                            /* Before removing or keeping the package with the broken dependency
 942                               try instead to install the first not previously installed package
 943                               solving this dependency. This helps every time a previous solver
 944                               is removed by the resolver because of a conflict or alike but it is
 945                               dangerous as it could trigger new breaks/conflicts… */
 946                            if (Debug == true)
 947                               clog << "  Try Installing " << APT::PrettyPkg(&Cache, Start.TargetPkg()) << " before changing " << I.FullName(false) << std::endl;
 948                            unsigned long const OldBroken = Cache.BrokenCount();
 949                            Cache.MarkInstall(Start.TargetPkg(), true, 1, false);
 950                            // FIXME: we should undo the complete MarkInstall process here
 951                            if (Cache[Start.TargetPkg()].InstBroken() == true || Cache.BrokenCount() > OldBroken)
 952                               Cache.MarkDelete(Start.TargetPkg(), false, 1, false);
 953                         }
 954                      }
 955                   }
 956
 957                   Change = true;
 958                   Done = true;
 959                   break;
 960                }
 961                else
 962                {
 963                   if (Start->Type == pkgCache::Dep::DpkgBreaks)
 964                   {
 965                      // first, try upgradring the package, if that
 966                      // does not help, the breaks goes onto the
 967                      // kill list
 968                      //
 969                      // FIXME: use DoUpgrade(Pkg) instead?
 970                      if (Cache[End] & pkgDepCache::DepGCVer)
 971                      {
 972                         if (Debug)
 973                            clog << "  Upgrading " << Pkg.FullName(false) << " due to Breaks field in " << I.FullName(false) << endl;
 974                         Cache.MarkInstall(Pkg, false, 0, false);
 975                         continue;
 976                      }
 977                   }
 978
 979                   // Skip adding to the kill list if it is protected
 980                   if ((Flags[Pkg->ID] & Protected) != 0)
 981                      continue;
 982
 983                   if (Debug == true)
 984                      clog << "  Added " << Pkg.FullName(false) << " to the remove list" << endl;
 985
 986                   KillList.push_back({Pkg, End});
 987
 988                   if (Start.IsNegative() == false)
 989                      break;
 990                }
 991             }
 992
 993             // Hm, nothing can possibly satisify this dep. Nuke it.
 994             if (VList[0] == 0 &&
 995                 Start.IsNegative() == false &&
 996                 (Flags[I->ID] & Protected) != Protected)
 997             {
 998                bool Installed = Cache[I].Install();
 999                Cache.MarkKeep(I);
1000                if (Cache[I].InstBroken() == false)
1001                {
1002                   // Unwind operation will be keep now
1003                   if (OrOp == OrRemove)
1004                      OrOp = OrKeep;
1005
1006                   // Restore
1007                   if (InOr == true && Installed == true)
1008                      Cache.MarkInstall(I, false, 0, false);
1009
1010                   if (Debug == true)
1011                      clog << "  Holding Back " << I.FullName(false) << " because I can't find " << Start.TargetPkg().FullName(false) << endl;
1012                }
1013                else
1014                {
1015                   if (Debug == true)
1016                      clog << "  Removing " << I.FullName(false) << " because I can't find " << Start.TargetPkg().FullName(false) << endl;
1017                   if (InOr == false)
1018                      Cache.MarkDelete(I, false, 0, false);
1019                }
1020
1021                Change = true;
1022                Done = true;
1023             }
1024
1025             // Try some more
1026             if (InOr == true)
1027                continue;
1028
1029             if (Done == true)
1030                break;
1031          }
1032
1033          // Apply the kill list now
1034          if (Cache[I].InstallVer != 0)
1035          {
1036             for (auto J = KillList.begin(); J != KillList.end(); J++)
1037             {
1038                Change = true;
1039                if ((Cache[J->Dep] & pkgDepCache::DepGNow) == 0)
1040                {
1041                   if (J->Dep.IsNegative() == true)
1042                   {
1043                      if (Debug == true)
1044                         clog << "  Fixing " << I.FullName(false) << " via remove of " << J->Pkg.FullName(false) << endl;
1045                      Cache.MarkDelete(J->Pkg, false, 0, false);
1046                   }
1047                }
1048                else
1049                {
1050                   if (Debug == true)
1051                      clog << "  Fixing " << I.FullName(false) << " via keep of " << J->Pkg.FullName(false) << endl;
1052                   Cache.MarkKeep(J->Pkg, false, false);
1053                }
1054
1055                if (Counter > 1)
1056                {
1057                   if (Scores[I->ID] > Scores[J->Pkg->ID])
1058                      Scores[J->Pkg->ID] = Scores[I->ID];
1059                }
1060             }
1061          }
1062       }
1063    }
1064
1065    if (Debug == true)
1066       clog << "Done" << endl;
1067
1068    if (Cache.BrokenCount() != 0)
1069    {
1070       // See if this is the result of a hold
1071       pkgCache::PkgIterator I = Cache.PkgBegin();
1072       for (;I.end() != true; ++I)
1073       {
1074          if (Cache[I].InstBroken() == false)
1075             continue;
1076          if ((Flags[I->ID] & Protected) != Protected)
1077             return _error->Error(_("Error, pkgProblemResolver::Resolve generated breaks, this may be caused by held packages."));
1078       }
1079       return _error->Error(_("Unable to correct problems, you have held broken packages."));
1080    }
1081
1082    // set the auto-flags (mvo: I'm not sure if we _really_ need this)
1083    pkgCache::PkgIterator I = Cache.PkgBegin();
1084    for (;I.end() != true; ++I) {
1085       if (Cache[I].NewInstall() && !(Flags[I->ID] & PreInstalled)) {
1086          if(_config->FindI("Debug::pkgAutoRemove",false)) {
1087             std::clog << "Resolve installed new pkg: " << I.FullName(false)
1088                       << " (now marking it as auto)" << std::endl;
1089          }
1090          Cache[I].Flags |= pkgCache::Flag::Auto;
1091       }
1092    }
1093
1094
1095    return true;
1096 }
1097                                                                         /*}}}*/
1098 // ProblemResolver::BreaksInstOrPolicy - Check if the given pkg is broken/*{{{*/
1099 // ---------------------------------------------------------------------
1100 /* This checks if the given package is broken either by a hard dependency
1101    (InstBroken()) or by introducing a new policy breakage e.g. new
1102    unsatisfied recommends for a package that was in "policy-good" state
1103
1104    Note that this is not perfect as it will ignore further breakage
1105    for already broken policy (recommends)
1106 */
1107 bool pkgProblemResolver::InstOrNewPolicyBroken(pkgCache::PkgIterator I)
1108 {
1109    // a broken install is always a problem
1110    if (Cache[I].InstBroken() == true)
1111    {
1112       if (Debug == true)
1113          std::clog << "  Dependencies are not satisfied for " << APT::PrettyPkg(&Cache, I) << std::endl;
1114       return true;
1115    }
1116
1117    // a newly broken policy (recommends/suggests) is a problem
1118    if (Cache[I].NowPolicyBroken() == false &&
1119        Cache[I].InstPolicyBroken() == true)
1120    {
1121       if (Debug == true)
1122          std::clog << "  Policy breaks with upgrade of " << APT::PrettyPkg(&Cache, I) << std::endl;
1123       return true;
1124    }
1125
1126    return false;
1127 }
1128                                                                         /*}}}*/
1129 // ProblemResolver::ResolveByKeep - Resolve problems using keep         /*{{{*/
1130 // ---------------------------------------------------------------------
1131 /* This is the work horse of the soft upgrade routine. It is very gental
1132    in that it does not install or remove any packages. It is assumed that the
1133    system was non-broken previously. */
1134 bool pkgProblemResolver::ResolveByKeep(OpProgress * const Progress)
1135 {
1136    std::string const solver = _config->Find("APT::Solver", "internal");
1137    constexpr auto flags = EDSP::Request::UPGRADE_ALL | EDSP::Request::FORBID_NEW_INSTALL | EDSP::Request::FORBID_REMOVE;
1138    auto const ret = EDSP::ResolveExternal(solver.c_str(), Cache, flags, Progress);
1139    if (solver != "internal")
1140       return ret;
1141    return ResolveByKeepInternal();
1142 }
1143                                                                         /*}}}*/
1144 // ProblemResolver::ResolveByKeepInternal - Resolve problems using keep /*{{{*/
1145 // ---------------------------------------------------------------------
1146 /* This is the work horse of the soft upgrade routine. It is very gental
1147    in that it does not install or remove any packages. It is assumed that the
1148    system was non-broken previously. */
1149 bool pkgProblemResolver::ResolveByKeepInternal()
1150 {
1151    pkgDepCache::ActionGroup group(Cache);
1152
1153    unsigned long Size = Cache.Head().PackageCount;
1154
1155    MakeScores();
1156
1157    /* We have to order the packages so that the broken fixing pass
1158       operates from highest score to lowest. This prevents problems when
1159       high score packages cause the removal of lower score packages that
1160       would cause the removal of even lower score packages. */
1161    pkgCache::Package **PList = new pkgCache::Package *[Size];
1162    pkgCache::Package **PEnd = PList;
1163    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
1164       *PEnd++ = I;
1165
1166    std::sort(PList,PEnd,[this](Package *a, Package *b) { return ScoreSort(a, b) < 0; });
1167
1168
1169    if (_config->FindB("Debug::pkgProblemResolver::ShowScores",false) == true)
1170    {
1171       clog << "Show Scores" << endl;
1172       for (pkgCache::Package **K = PList; K != PEnd; K++)
1173          if (Scores[(*K)->ID] != 0)
1174          {
1175            pkgCache::PkgIterator Pkg(Cache,*K);
1176            clog << Scores[(*K)->ID] << ' ' << APT::PrettyPkg(&Cache, Pkg) << std::endl;
1177          }
1178    }
1179
1180    if (Debug == true)
1181       clog << "Entering ResolveByKeep" << endl;
1182
1183    // Consider each broken package
1184    pkgCache::Package **LastStop = 0;
1185    for (pkgCache::Package **K = PList; K != PEnd; K++)
1186    {
1187       pkgCache::PkgIterator I(Cache,*K);
1188
1189       if (Cache[I].InstallVer == 0)
1190          continue;
1191
1192       if (InstOrNewPolicyBroken(I) == false)
1193          continue;
1194
1195       /* Keep the package. If this works then great, otherwise we have
1196          to be significantly more aggressive and manipulate its dependencies */
1197       if ((Flags[I->ID] & Protected) == 0)
1198       {
1199          if (Debug == true)
1200             clog << "Keeping package " << I.FullName(false) << endl;
1201          Cache.MarkKeep(I, false, false);
1202          if (InstOrNewPolicyBroken(I) == false)
1203          {
1204             K = PList - 1;
1205             continue;
1206          }
1207       }
1208
1209       // Isolate the problem dependencies
1210       for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false;)
1211       {
1212          DepIterator Start;
1213          DepIterator End;
1214          D.GlobOr(Start,End);
1215
1216          // We only worry about critical deps.
1217          if (End.IsCritical() != true)
1218             continue;
1219
1220          // Dep is ok
1221          if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
1222             continue;
1223
1224          /* Hm, the group is broken.. I suppose the best thing to do is to
1225             is to try every combination of keep/not-keep for the set, but thats
1226             slow, and this never happens, just be conservative and assume the
1227             list of ors is in preference and keep till it starts to work. */
1228          while (true)
1229          {
1230             if (Debug == true)
1231                clog << "Package " << I.FullName(false) << " " << APT::PrettyDep(&Cache, Start) << endl;
1232
1233             // Look at all the possible provides on this package
1234             std::unique_ptr<pkgCache::Version *[]> VList(Start.AllTargets());
1235             for (pkgCache::Version **V = VList.get(); *V != 0; V++)
1236             {
1237                pkgCache::VerIterator Ver(Cache,*V);
1238                pkgCache::PkgIterator Pkg = Ver.ParentPkg();
1239
1240                // It is not keepable
1241                if (Cache[Pkg].InstallVer == 0 ||
1242                    Pkg->CurrentVer == 0)
1243                   continue;
1244
1245                if ((Flags[I->ID] & Protected) == 0)
1246                {
1247                   if (Debug == true)
1248                      clog << "  Keeping Package " << Pkg.FullName(false) << " due to " << Start.DepType() << endl;
1249                   Cache.MarkKeep(Pkg, false, false);
1250                }
1251
1252                if (InstOrNewPolicyBroken(I) == false)
1253                   break;
1254             }
1255
1256             if (InstOrNewPolicyBroken(I) == false)
1257                break;
1258
1259             if (Start == End)
1260                break;
1261             ++Start;
1262          }
1263
1264          if (InstOrNewPolicyBroken(I) == false)
1265             break;
1266       }
1267
1268       if (InstOrNewPolicyBroken(I) == true)
1269          continue;
1270
1271       // Restart again.
1272       if (K == LastStop) {
1273           // I is an iterator based off our temporary package list,
1274           // so copy the name we need before deleting the temporary list
1275           std::string const LoopingPackage = I.FullName(false);
1276           delete[] PList;
1277           return _error->Error("Internal Error, pkgProblemResolver::ResolveByKeep is looping on package %s.", LoopingPackage.c_str());
1278       }
1279       LastStop = K;
1280       K = PList - 1;
1281    }
1282
1283    delete[] PList;
1284    return true;
1285 }
1286                                                                         /*}}}*/
1287 // ProblemResolver::InstallProtect - deprecated cpu-eating no-op        /*{{{*/
1288 // ---------------------------------------------------------------------
1289 /* Actions issued with FromUser bit set are protected from further
1290    modification (expect by other calls with FromUser set) nowadays , so we
1291    don't need to reissue actions here, they are already set in stone. */
1292 void pkgProblemResolver::InstallProtect()
1293 {
1294    pkgDepCache::ActionGroup group(Cache);
1295
1296    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
1297    {
1298       if ((Flags[I->ID] & Protected) == Protected)
1299       {
1300          if ((Flags[I->ID] & ToRemove) == ToRemove)
1301             Cache.MarkDelete(I);
1302          else
1303          {
1304             // preserve the information whether the package was auto
1305             // or manually installed
1306             bool autoInst = (Cache[I].Flags & pkgCache::Flag::Auto);
1307             Cache.MarkInstall(I, false, 0, !autoInst);
1308          }
1309       }
1310    }
1311 }
1312                                                                         /*}}}*/
1313 // PrioSortList - Sort a list of versions by priority                   /*{{{*/
1314 // ---------------------------------------------------------------------
1315 /* This is ment to be used in conjunction with AllTargets to get a list
1316    of versions ordered by preference. */
1317
1318 struct PrioComp {
1319    pkgCache &PrioCache;
1320
1321    explicit PrioComp(pkgCache &PrioCache) : PrioCache(PrioCache) {
1322    }
1323
1324    bool operator() (pkgCache::Version * const &A, pkgCache::Version * const &B) {
1325       return compare(A, B) < 0;
1326    }
1327
1328    int compare(pkgCache::Version * const &A, pkgCache::Version * const &B) {
1329       pkgCache::VerIterator L(PrioCache,A);
1330       pkgCache::VerIterator R(PrioCache,B);
1331
1332       if ((L.ParentPkg()->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential &&
1333           (R.ParentPkg()->Flags & pkgCache::Flag::Essential) != pkgCache::Flag::Essential)
1334         return 1;
1335       if ((L.ParentPkg()->Flags & pkgCache::Flag::Essential) != pkgCache::Flag::Essential &&
1336           (R.ParentPkg()->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
1337         return -1;
1338
1339       if ((L.ParentPkg()->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important &&
1340           (R.ParentPkg()->Flags & pkgCache::Flag::Important) != pkgCache::Flag::Important)
1341         return 1;
1342       if ((L.ParentPkg()->Flags & pkgCache::Flag::Important) != pkgCache::Flag::Important &&
1343           (R.ParentPkg()->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important)
1344         return -1;
1345
1346       if (L->Priority != R->Priority)
1347          return R->Priority - L->Priority;
1348       return strcmp(L.ParentPkg().Name(),R.ParentPkg().Name());
1349    }
1350 };
1351
1352 void pkgPrioSortList(pkgCache &Cache,pkgCache::Version **List)
1353 {
1354    unsigned long Count = 0;
1355    for (pkgCache::Version **I = List; *I != 0; I++)
1356       Count++;
1357    std::sort(List,List+Count,PrioComp(Cache));
1358 }
1359                                                                         /*}}}*/