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