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