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