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