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