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       // We transform the priority
 449       if (Cache[I].InstVerIter(Cache)->Priority <= 5)
 450          Score += PrioMap[Cache[I].InstVerIter(Cache)->Priority];
 451
 452       /* This helps to fix oddball problems with conflicting packages
 453          on the same level. We enhance the score of installed packages
 454          if those are not obsolete
 455       */
 456       if (I->CurrentVer != 0 && Cache[I].CandidateVer != 0 && Cache[I].CandidateVerIter(Cache).Downloadable())
 457          Score += PrioInstalledAndNotObsolete;
 458
 459       // propagate score points along dependencies
 460       for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false; ++D)
 461       {
 462          if (DepMap[D->Type] == 0)
 463             continue;
 464          pkgCache::PkgIterator const T = D.TargetPkg();
 465          if (D->Version != 0)
 466          {
 467             pkgCache::VerIterator const IV = Cache[T].InstVerIter(Cache);
 468             if (IV.end() == true || D.IsSatisfied(IV) != D.IsNegative())
 469                continue;
 470          }
 471          Scores[T->ID] += DepMap[D->Type];
 472       }
 473    }
 474
 475    // Copy the scores to advoid additive looping
 476    SPtrArray<int> OldScores = new int[Size];
 477    memcpy(OldScores,Scores,sizeof(*Scores)*Size);
 478
 479    /* Now we cause 1 level of dependency inheritance, that is we add the
 480       score of the packages that depend on the target Package. This
 481       fortifies high scoring packages */
 482    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
 483    {
 484       if (Cache[I].InstallVer == 0)
 485          continue;
 486
 487       for (pkgCache::DepIterator D = I.RevDependsList(); D.end() == false; ++D)
 488       {
 489          // Only do it for the install version
 490          if ((pkgCache::Version *)D.ParentVer() != Cache[D.ParentPkg()].InstallVer ||
 491              (D->Type != pkgCache::Dep::Depends &&
 492               D->Type != pkgCache::Dep::PreDepends &&
 493               D->Type != pkgCache::Dep::Recommends))
 494             continue;
 495
 496          // Do not propagate negative scores otherwise
 497          // an extra (-2) package might score better than an optional (-1)
 498          if (OldScores[D.ParentPkg()->ID] > 0)
 499              Scores[I->ID] += OldScores[D.ParentPkg()->ID];
 500       }
 501    }
 502
 503    /* Now we propagate along provides. This makes the packages that
 504       provide important packages extremely important */
 505    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
 506    {
 507       for (pkgCache::PrvIterator P = I.ProvidesList(); P.end() == false; ++P)
 508       {
 509          // Only do it once per package
 510          if ((pkgCache::Version *)P.OwnerVer() != Cache[P.OwnerPkg()].InstallVer)
 511             continue;
 512          Scores[P.OwnerPkg()->ID] += abs(Scores[I->ID] - OldScores[I->ID]);
 513       }
 514    }
 515
 516    /* Protected things are pushed really high up. This number should put them
 517       ahead of everything */
 518    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
 519    {
 520       if ((Flags[I->ID] & Protected) != 0)
 521          Scores[I->ID] += AddProtected;
 522       if ((I->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential ||
 523           (I->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important)
 524          Scores[I->ID] += AddEssential;
 525    }
 526 }
 527                                                                         /*}}}*/
 528 // ProblemResolver::DoUpgrade - Attempt to upgrade this package         /*{{{*/
 529 // ---------------------------------------------------------------------
 530 /* This goes through and tries to reinstall packages to make this package
 531    installable */
 532 bool pkgProblemResolver::DoUpgrade(pkgCache::PkgIterator Pkg)
 533 {
 534    pkgDepCache::ActionGroup group(Cache);
 535
 536    if ((Flags[Pkg->ID] & Upgradable) == 0 || Cache[Pkg].Upgradable() == false)
 537       return false;
 538    if ((Flags[Pkg->ID] & Protected) == Protected)
 539       return false;
 540
 541    Flags[Pkg->ID] &= ~Upgradable;
 542
 543    bool WasKept = Cache[Pkg].Keep();
 544    Cache.MarkInstall(Pkg, false, 0, false);
 545
 546    // This must be a virtual package or something like that.
 547    if (Cache[Pkg].InstVerIter(Cache).end() == true)
 548       return false;
 549
 550    // Isolate the problem dependency
 551    bool Fail = false;
 552    for (pkgCache::DepIterator D = Cache[Pkg].InstVerIter(Cache).DependsList(); D.end() == false;)
 553    {
 554       // Compute a single dependency element (glob or)
 555       pkgCache::DepIterator Start = D;
 556       pkgCache::DepIterator End = D;
 557       for (bool LastOR = true; D.end() == false && LastOR == true;)
 558       {
 559          LastOR = (D->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or;
 560          ++D;
 561          if (LastOR == true)
 562             End = D;
 563       }
 564
 565       // We only worry about critical deps.
 566       if (End.IsCritical() != true)
 567          continue;
 568
 569       // Iterate over all the members in the or group
 570       while (1)
 571       {
 572          // Dep is ok now
 573          if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
 574             break;
 575
 576          // Do not change protected packages
 577          PkgIterator P = Start.SmartTargetPkg();
 578          if ((Flags[P->ID] & Protected) == Protected)
 579          {
 580             if (Debug == true)
 581                clog << "    Reinst Failed because of protected " << P.FullName(false) << endl;
 582             Fail = true;
 583          }
 584          else
 585          {
 586             // Upgrade the package if the candidate version will fix the problem.
 587             if ((Cache[Start] & pkgDepCache::DepCVer) == pkgDepCache::DepCVer)
 588             {
 589                if (DoUpgrade(P) == false)
 590                {
 591                   if (Debug == true)
 592                      clog << "    Reinst Failed because of " << P.FullName(false) << endl;
 593                   Fail = true;
 594                }
 595                else
 596                {
 597                   Fail = false;
 598                   break;
 599                }
 600             }
 601             else
 602             {
 603                /* We let the algorithm deal with conflicts on its next iteration,
 604                 it is much smarter than us */
 605                if (Start.IsNegative() == true)
 606                    break;
 607
 608                if (Debug == true)
 609                   clog << "    Reinst Failed early because of " << Start.TargetPkg().FullName(false) << endl;
 610                Fail = true;
 611             }
 612          }
 613
 614          if (Start == End)
 615             break;
 616          ++Start;
 617       }
 618       if (Fail == true)
 619          break;
 620    }
 621
 622    // Undo our operations - it might be smart to undo everything this did..
 623    if (Fail == true)
 624    {
 625       if (WasKept == true)
 626          Cache.MarkKeep(Pkg, false, false);
 627       else
 628          Cache.MarkDelete(Pkg, false, 0, false);
 629       return false;
 630    }
 631
 632    if (Debug == true)
 633       clog << "  Re-Instated " << Pkg.FullName(false) << endl;
 634    return true;
 635 }
 636                                                                         /*}}}*/
 637 // ProblemResolver::Resolve - calls a resolver to fix the situation     /*{{{*/
 638 // ---------------------------------------------------------------------
 639 /* */
 640 bool pkgProblemResolver::Resolve(bool BrokenFix)
 641 {
 642    std::string const solver = _config->Find("APT::Solver", "internal");
 643    if (solver != "internal") {
 644       OpTextProgress Prog(*_config);
 645       return EDSP::ResolveExternal(solver.c_str(), Cache, false, false, false, &Prog);
 646    }
 647    return ResolveInternal(BrokenFix);
 648 }
 649                                                                         /*}}}*/
 650 // ProblemResolver::ResolveInternal - Run the resolution pass           /*{{{*/
 651 // ---------------------------------------------------------------------
 652 /* This routines works by calculating a score for each package. The score
 653    is derived by considering the package's priority and all reverse
 654    dependents giving an integer that reflects the amount of breakage that
 655    adjusting the package will inflict.
 656
 657    It goes from highest score to lowest and corrects all of the breaks by
 658    keeping or removing the dependent packages. If that fails then it removes
 659    the package itself and goes on. The routine should be able to intelligently
 660    go from any broken state to a fixed state.
 661
 662    The BrokenFix flag enables a mode where the algorithm tries to
 663    upgrade packages to advoid problems. */
 664 bool pkgProblemResolver::ResolveInternal(bool const BrokenFix)
 665 {
 666    pkgDepCache::ActionGroup group(Cache);
 667
 668    // Record which packages are marked for install
 669    bool Again = false;
 670    do
 671    {
 672       Again = false;
 673       for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
 674       {
 675          if (Cache[I].Install() == true)
 676             Flags[I->ID] |= PreInstalled;
 677          else
 678          {
 679             if (Cache[I].InstBroken() == true && BrokenFix == true)
 680             {
 681                Cache.MarkInstall(I, false, 0, false);
 682                if (Cache[I].Install() == true)
 683                   Again = true;
 684             }
 685
 686             Flags[I->ID] &= ~PreInstalled;
 687          }
 688          Flags[I->ID] |= Upgradable;
 689       }
 690    }
 691    while (Again == true);
 692
 693    if (Debug == true) {
 694       clog << "Starting pkgProblemResolver with broken count: "
 695            << Cache.BrokenCount() << endl;
 696    }
 697
 698    MakeScores();
 699
 700    unsigned long const Size = Cache.Head().PackageCount;
 701
 702    /* We have to order the packages so that the broken fixing pass
 703       operates from highest score to lowest. This prevents problems when
 704       high score packages cause the removal of lower score packages that
 705       would cause the removal of even lower score packages. */
 706    SPtrArray<pkgCache::Package *> PList = new pkgCache::Package *[Size];
 707    pkgCache::Package **PEnd = PList;
 708    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
 709       *PEnd++ = I;
 710    This = this;
 711    qsort(PList,PEnd - PList,sizeof(*PList),&ScoreSort);
 712
 713    if (_config->FindB("Debug::pkgProblemResolver::ShowScores",false) == true)
 714    {
 715       clog << "Show Scores" << endl;
 716       for (pkgCache::Package **K = PList; K != PEnd; K++)
 717          if (Scores[(*K)->ID] != 0)
 718          {
 719            pkgCache::PkgIterator Pkg(Cache,*K);
 720            clog << Scores[(*K)->ID] << ' ' << Pkg << std::endl;
 721          }
 722    }
 723
 724    if (Debug == true) {
 725       clog << "Starting 2 pkgProblemResolver with broken count: "
 726            << Cache.BrokenCount() << endl;
 727    }
 728
 729    /* Now consider all broken packages. For each broken package we either
 730       remove the package or fix it's problem. We do this once, it should
 731       not be possible for a loop to form (that is a < b < c and fixing b by
 732       changing a breaks c) */
 733    bool Change = true;
 734    bool const TryFixByInstall = _config->FindB("pkgProblemResolver::FixByInstall", true);
 735    for (int Counter = 0; Counter != 10 && Change == true; Counter++)
 736    {
 737       Change = false;
 738       for (pkgCache::Package **K = PList; K != PEnd; K++)
 739       {
 740          pkgCache::PkgIterator I(Cache,*K);
 741
 742          /* We attempt to install this and see if any breaks result,
 743             this takes care of some strange cases */
 744          if (Cache[I].CandidateVer != Cache[I].InstallVer &&
 745              I->CurrentVer != 0 && Cache[I].InstallVer != 0 &&
 746              (Flags[I->ID] & PreInstalled) != 0 &&
 747              (Flags[I->ID] & Protected) == 0 &&
 748              (Flags[I->ID] & ReInstateTried) == 0)
 749          {
 750             if (Debug == true)
 751                clog << " Try to Re-Instate (" << Counter << ") " << I.FullName(false) << endl;
 752             unsigned long OldBreaks = Cache.BrokenCount();
 753             pkgCache::Version *OldVer = Cache[I].InstallVer;
 754             Flags[I->ID] &= ReInstateTried;
 755
 756             Cache.MarkInstall(I, false, 0, false);
 757             if (Cache[I].InstBroken() == true ||
 758                 OldBreaks < Cache.BrokenCount())
 759             {
 760                if (OldVer == 0)
 761                   Cache.MarkDelete(I, false, 0, false);
 762                else
 763                   Cache.MarkKeep(I, false, false);
 764             }
 765             else
 766                if (Debug == true)
 767                   clog << "Re-Instated " << I.FullName(false) << " (" << OldBreaks << " vs " << Cache.BrokenCount() << ')' << endl;
 768          }
 769
 770          if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false)
 771             continue;
 772
 773          if (Debug == true)
 774             clog << "Investigating (" << Counter << ") " << I << endl;
 775
 776          // Isolate the problem dependency
 777          PackageKill KillList[100];
 778          PackageKill *LEnd = KillList;
 779          bool InOr = false;
 780          pkgCache::DepIterator Start;
 781          pkgCache::DepIterator End;
 782          PackageKill *OldEnd = LEnd;
 783
 784          enum {OrRemove,OrKeep} OrOp = OrRemove;
 785          for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList();
 786               D.end() == false || InOr == true;)
 787          {
 788             // Compute a single dependency element (glob or)
 789             if (Start == End)
 790             {
 791                // Decide what to do
 792                if (InOr == true && OldEnd == LEnd)
 793                {
 794                   if (OrOp == OrRemove)
 795                   {
 796                      if ((Flags[I->ID] & Protected) != Protected)
 797                      {
 798                         if (Debug == true)
 799                            clog << "  Or group remove for " << I.FullName(false) << endl;
 800                         Cache.MarkDelete(I, false, 0, false);
 801                         Change = true;
 802                      }
 803                   }
 804                   else if (OrOp == OrKeep)
 805                   {
 806                      if (Debug == true)
 807                         clog << "  Or group keep for " << I.FullName(false) << endl;
 808                      Cache.MarkKeep(I, false, false);
 809                      Change = true;
 810                   }
 811                }
 812
 813                /* We do an extra loop (as above) to finalize the or group
 814                   processing */
 815                InOr = false;
 816                OrOp = OrRemove;
 817                D.GlobOr(Start,End);
 818                if (Start.end() == true)
 819                   break;
 820
 821                // We only worry about critical deps.
 822                if (End.IsCritical() != true)
 823                   continue;
 824
 825                InOr = Start != End;
 826                OldEnd = LEnd;
 827             }
 828             else
 829             {
 830                ++Start;
 831                // We only worry about critical deps.
 832                if (Start.IsCritical() != true)
 833                   continue;
 834             }
 835
 836             // Dep is ok
 837             if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
 838             {
 839                InOr = false;
 840                continue;
 841             }
 842
 843             if (Debug == true)
 844                clog << "Broken " << Start << endl;
 845
 846             /* Look across the version list. If there are no possible
 847                targets then we keep the package and bail. This is necessary
 848                if a package has a dep on another package that can't be found */
 849             SPtrArray<pkgCache::Version *> VList = Start.AllTargets();
 850             if (*VList == 0 && (Flags[I->ID] & Protected) != Protected &&
 851                 Start.IsNegative() == false &&
 852                 Cache[I].NowBroken() == false)
 853             {
 854                if (InOr == true)
 855                {
 856                   /* No keep choice because the keep being OK could be the
 857                      result of another element in the OR group! */
 858                   continue;
 859                }
 860
 861                Change = true;
 862                Cache.MarkKeep(I, false, false);
 863                break;
 864             }
 865
 866             bool Done = false;
 867             for (pkgCache::Version **V = VList; *V != 0; V++)
 868             {
 869                pkgCache::VerIterator Ver(Cache,*V);
 870                pkgCache::PkgIterator Pkg = Ver.ParentPkg();
 871
 872                /* This is a conflicts, and the version we are looking
 873                   at is not the currently selected version of the
 874                   package, which means it is not necessary to
 875                   remove/keep */
 876                if (Cache[Pkg].InstallVer != Ver && Start.IsNegative() == true)
 877                {
 878                   if (Debug)
 879                      clog << "  Conflicts//Breaks against version "
 880                           << Ver.VerStr() << " for " << Pkg.Name()
 881                           << " but that is not InstVer, ignoring"
 882                           << endl;
 883                   continue;
 884                }
 885
 886                if (Debug == true)
 887                   clog << "  Considering " << Pkg.FullName(false) << ' ' << Scores[Pkg->ID] <<
 888                   " as a solution to " << I.FullName(false) << ' ' << Scores[I->ID] << endl;
 889
 890                /* Try to fix the package under consideration rather than
 891                   fiddle with the VList package */
 892                if (Scores[I->ID] <= Scores[Pkg->ID] ||
 893                    ((Cache[Start] & pkgDepCache::DepNow) == 0 &&
 894                     End.IsNegative() == false))
 895                {
 896                   // Try a little harder to fix protected packages..
 897                   if ((Flags[I->ID] & Protected) == Protected)
 898                   {
 899                      if (DoUpgrade(Pkg) == true)
 900                      {
 901                         if (Scores[Pkg->ID] > Scores[I->ID])
 902                            Scores[Pkg->ID] = Scores[I->ID];
 903                         break;
 904                      }
 905
 906                      continue;
 907                   }
 908
 909                   /* See if a keep will do, unless the package is protected,
 910                      then installing it will be necessary */
 911                   bool Installed = Cache[I].Install();
 912                   Cache.MarkKeep(I, false, false);
 913                   if (Cache[I].InstBroken() == false)
 914                   {
 915                      // Unwind operation will be keep now
 916                      if (OrOp == OrRemove)
 917                         OrOp = OrKeep;
 918
 919                      // Restore
 920                      if (InOr == true && Installed == true)
 921                         Cache.MarkInstall(I, false, 0, false);
 922
 923                      if (Debug == true)
 924                         clog << "  Holding Back " << I.FullName(false) << " rather than change " << Start.TargetPkg().FullName(false) << endl;
 925                   }
 926                   else
 927                   {
 928                      if (BrokenFix == false || DoUpgrade(I) == false)
 929                      {
 930                         // Consider other options
 931                         if (InOr == false || Cache[I].Garbage == true)
 932                         {
 933                            if (Debug == true)
 934                               clog << "  Removing " << I.FullName(false) << " rather than change " << Start.TargetPkg().FullName(false) << endl;
 935                            Cache.MarkDelete(I, false, 0, false);
 936                            if (Counter > 1 && Scores[Pkg->ID] > Scores[I->ID])
 937                               Scores[I->ID] = Scores[Pkg->ID];
 938                         }
 939                         else if (TryFixByInstall == true &&
 940                                  Start.TargetPkg()->CurrentVer == 0 &&
 941                                  Cache[Start.TargetPkg()].Delete() == false &&
 942                                  (Flags[Start.TargetPkg()->ID] & ToRemove) != ToRemove &&
 943                                  Cache.GetCandidateVer(Start.TargetPkg()).end() == false)
 944                         {
 945                            /* Before removing or keeping the package with the broken dependency
 946                               try instead to install the first not previously installed package
 947                               solving this dependency. This helps every time a previous solver
 948                               is removed by the resolver because of a conflict or alike but it is
 949                               dangerous as it could trigger new breaks/conflicts… */
 950                            if (Debug == true)
 951                               clog << "  Try Installing " << Start.TargetPkg() << " before changing " << I.FullName(false) << std::endl;
 952                            unsigned long const OldBroken = Cache.BrokenCount();
 953                            Cache.MarkInstall(Start.TargetPkg(), true, 1, false);
 954                            // FIXME: we should undo the complete MarkInstall process here
 955                            if (Cache[Start.TargetPkg()].InstBroken() == true || Cache.BrokenCount() > OldBroken)
 956                               Cache.MarkDelete(Start.TargetPkg(), false, 1, false);
 957                         }
 958                      }
 959                   }
 960
 961                   Change = true;
 962                   Done = true;
 963                   break;
 964                }
 965                else
 966                {
 967                   if (Start->Type == pkgCache::Dep::DpkgBreaks)
 968                   {
 969                      // first, try upgradring the package, if that
 970                      // does not help, the breaks goes onto the
 971                      // kill list
 972                      //
 973                      // FIXME: use DoUpgrade(Pkg) instead?
 974                      if (Cache[End] & pkgDepCache::DepGCVer)
 975                      {
 976                         if (Debug)
 977                            clog << "  Upgrading " << Pkg.FullName(false) << " due to Breaks field in " << I.FullName(false) << endl;
 978                         Cache.MarkInstall(Pkg, false, 0, false);
 979                         continue;
 980                      }
 981                   }
 982
 983                   // Skip adding to the kill list if it is protected
 984                   if ((Flags[Pkg->ID] & Protected) != 0)
 985                      continue;
 986
 987                   if (Debug == true)
 988                      clog << "  Added " << Pkg.FullName(false) << " to the remove list" << endl;
 989
 990                   LEnd->Pkg = Pkg;
 991                   LEnd->Dep = End;
 992                   LEnd++;
 993
 994                   if (Start.IsNegative() == false)
 995                      break;
 996                }
 997             }
 998
 999             // Hm, nothing can possibly satisify this dep. Nuke it.
1000             if (VList[0] == 0 &&
1001                 Start.IsNegative() == false &&
1002                 (Flags[I->ID] & Protected) != Protected)
1003             {
1004                bool Installed = Cache[I].Install();
1005                Cache.MarkKeep(I);
1006                if (Cache[I].InstBroken() == false)
1007                {
1008                   // Unwind operation will be keep now
1009                   if (OrOp == OrRemove)
1010                      OrOp = OrKeep;
1011
1012                   // Restore
1013                   if (InOr == true && Installed == true)
1014                      Cache.MarkInstall(I, false, 0, false);
1015
1016                   if (Debug == true)
1017                      clog << "  Holding Back " << I.FullName(false) << " because I can't find " << Start.TargetPkg().FullName(false) << endl;
1018                }
1019                else
1020                {
1021                   if (Debug == true)
1022                      clog << "  Removing " << I.FullName(false) << " because I can't find " << Start.TargetPkg().FullName(false) << endl;
1023                   if (InOr == false)
1024                      Cache.MarkDelete(I, false, 0, false);
1025                }
1026
1027                Change = true;
1028                Done = true;
1029             }
1030
1031             // Try some more
1032             if (InOr == true)
1033                continue;
1034
1035             if (Done == true)
1036                break;
1037          }
1038
1039          // Apply the kill list now
1040          if (Cache[I].InstallVer != 0)
1041          {
1042             for (PackageKill *J = KillList; J != LEnd; J++)
1043             {
1044                Change = true;
1045                if ((Cache[J->Dep] & pkgDepCache::DepGNow) == 0)
1046                {
1047                   if (J->Dep.IsNegative() == true)
1048                   {
1049                      if (Debug == true)
1050                         clog << "  Fixing " << I.FullName(false) << " via remove of " << J->Pkg.FullName(false) << endl;
1051                      Cache.MarkDelete(J->Pkg, false, 0, false);
1052                   }
1053                }
1054                else
1055                {
1056                   if (Debug == true)
1057                      clog << "  Fixing " << I.FullName(false) << " via keep of " << J->Pkg.FullName(false) << endl;
1058                   Cache.MarkKeep(J->Pkg, false, false);
1059                }
1060
1061                if (Counter > 1)
1062                {
1063                   if (Scores[I->ID] > Scores[J->Pkg->ID])
1064                      Scores[J->Pkg->ID] = Scores[I->ID];
1065                }
1066             }
1067          }
1068       }
1069    }
1070
1071    if (Debug == true)
1072       clog << "Done" << endl;
1073
1074    if (Cache.BrokenCount() != 0)
1075    {
1076       // See if this is the result of a hold
1077       pkgCache::PkgIterator I = Cache.PkgBegin();
1078       for (;I.end() != true; ++I)
1079       {
1080          if (Cache[I].InstBroken() == false)
1081             continue;
1082          if ((Flags[I->ID] & Protected) != Protected)
1083             return _error->Error(_("Error, pkgProblemResolver::Resolve generated breaks, this may be caused by held packages."));
1084       }
1085       return _error->Error(_("Unable to correct problems, you have held broken packages."));
1086    }
1087
1088    // set the auto-flags (mvo: I'm not sure if we _really_ need this)
1089    pkgCache::PkgIterator I = Cache.PkgBegin();
1090    for (;I.end() != true; ++I) {
1091       if (Cache[I].NewInstall() && !(Flags[I->ID] & PreInstalled)) {
1092          if(_config->FindI("Debug::pkgAutoRemove",false)) {
1093             std::clog << "Resolve installed new pkg: " << I.FullName(false)
1094                       << " (now marking it as auto)" << std::endl;
1095          }
1096          Cache[I].Flags |= pkgCache::Flag::Auto;
1097       }
1098    }
1099
1100
1101    return true;
1102 }
1103                                                                         /*}}}*/
1104 // ProblemResolver::BreaksInstOrPolicy - Check if the given pkg is broken/*{{{*/
1105 // ---------------------------------------------------------------------
1106 /* This checks if the given package is broken either by a hard dependency
1107    (InstBroken()) or by introducing a new policy breakage e.g. new
1108    unsatisfied recommends for a package that was in "policy-good" state
1109
1110    Note that this is not perfect as it will ignore further breakage
1111    for already broken policy (recommends)
1112 */
1113 bool pkgProblemResolver::InstOrNewPolicyBroken(pkgCache::PkgIterator I)
1114 {
1115    // a broken install is always a problem
1116    if (Cache[I].InstBroken() == true)
1117    {
1118       if (Debug == true)
1119          std::clog << "  Dependencies are not satisfied for " << I << std::endl;
1120       return true;
1121    }
1122
1123    // a newly broken policy (recommends/suggests) is a problem
1124    if (Cache[I].NowPolicyBroken() == false &&
1125        Cache[I].InstPolicyBroken() == true)
1126    {
1127       if (Debug == true)
1128          std::clog << "  Policy breaks with upgrade of " << I << std::endl;
1129       return true;
1130    }
1131
1132    return false;
1133 }
1134                                                                         /*}}}*/
1135 // ProblemResolver::ResolveByKeep - Resolve problems using keep         /*{{{*/
1136 // ---------------------------------------------------------------------
1137 /* This is the work horse of the soft upgrade routine. It is very gental
1138    in that it does not install or remove any packages. It is assumed that the
1139    system was non-broken previously. */
1140 bool pkgProblemResolver::ResolveByKeep()
1141 {
1142    std::string const solver = _config->Find("APT::Solver", "internal");
1143    if (solver != "internal") {
1144       OpTextProgress Prog(*_config);
1145       return EDSP::ResolveExternal(solver.c_str(), Cache, true, false, false, &Prog);
1146    }
1147    return ResolveByKeepInternal();
1148 }
1149                                                                         /*}}}*/
1150 // ProblemResolver::ResolveByKeepInternal - Resolve problems using keep /*{{{*/
1151 // ---------------------------------------------------------------------
1152 /* This is the work horse of the soft upgrade routine. It is very gental
1153    in that it does not install or remove any packages. It is assumed that the
1154    system was non-broken previously. */
1155 bool pkgProblemResolver::ResolveByKeepInternal()
1156 {
1157    pkgDepCache::ActionGroup group(Cache);
1158
1159    unsigned long Size = Cache.Head().PackageCount;
1160
1161    MakeScores();
1162
1163    /* We have to order the packages so that the broken fixing pass
1164       operates from highest score to lowest. This prevents problems when
1165       high score packages cause the removal of lower score packages that
1166       would cause the removal of even lower score packages. */
1167    pkgCache::Package **PList = new pkgCache::Package *[Size];
1168    pkgCache::Package **PEnd = PList;
1169    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
1170       *PEnd++ = I;
1171    This = this;
1172    qsort(PList,PEnd - PList,sizeof(*PList),&ScoreSort);
1173
1174    if (_config->FindB("Debug::pkgProblemResolver::ShowScores",false) == true)
1175    {
1176       clog << "Show Scores" << endl;
1177       for (pkgCache::Package **K = PList; K != PEnd; K++)
1178          if (Scores[(*K)->ID] != 0)
1179          {
1180            pkgCache::PkgIterator Pkg(Cache,*K);
1181            clog << Scores[(*K)->ID] << ' ' << Pkg << std::endl;
1182          }
1183    }
1184
1185    if (Debug == true)
1186       clog << "Entering ResolveByKeep" << endl;
1187
1188    // Consider each broken package
1189    pkgCache::Package **LastStop = 0;
1190    for (pkgCache::Package **K = PList; K != PEnd; K++)
1191    {
1192       pkgCache::PkgIterator I(Cache,*K);
1193
1194       if (Cache[I].InstallVer == 0)
1195          continue;
1196
1197       if (InstOrNewPolicyBroken(I) == false)
1198          continue;
1199
1200       /* Keep the package. If this works then great, otherwise we have
1201          to be significantly more aggressive and manipulate its dependencies */
1202       if ((Flags[I->ID] & Protected) == 0)
1203       {
1204          if (Debug == true)
1205             clog << "Keeping package " << I.FullName(false) << endl;
1206          Cache.MarkKeep(I, false, false);
1207          if (InstOrNewPolicyBroken(I) == false)
1208          {
1209             K = PList - 1;
1210             continue;
1211          }
1212       }
1213
1214       // Isolate the problem dependencies
1215       for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false;)
1216       {
1217          DepIterator Start;
1218          DepIterator End;
1219          D.GlobOr(Start,End);
1220
1221          // We only worry about critical deps.
1222          if (End.IsCritical() != true)
1223             continue;
1224
1225          // Dep is ok
1226          if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
1227             continue;
1228
1229          /* Hm, the group is broken.. I suppose the best thing to do is to
1230             is to try every combination of keep/not-keep for the set, but thats
1231             slow, and this never happens, just be conservative and assume the
1232             list of ors is in preference and keep till it starts to work. */
1233          while (true)
1234          {
1235             if (Debug == true)
1236                clog << "Package " << I.FullName(false) << " " << Start << endl;
1237
1238             // Look at all the possible provides on this package
1239             SPtrArray<pkgCache::Version *> VList = Start.AllTargets();
1240             for (pkgCache::Version **V = VList; *V != 0; V++)
1241             {
1242                pkgCache::VerIterator Ver(Cache,*V);
1243                pkgCache::PkgIterator Pkg = Ver.ParentPkg();
1244
1245                // It is not keepable
1246                if (Cache[Pkg].InstallVer == 0 ||
1247                    Pkg->CurrentVer == 0)
1248                   continue;
1249
1250                if ((Flags[I->ID] & Protected) == 0)
1251                {
1252                   if (Debug == true)
1253                      clog << "  Keeping Package " << Pkg.FullName(false) << " due to " << Start.DepType() << endl;
1254                   Cache.MarkKeep(Pkg, false, false);
1255                }
1256
1257                if (InstOrNewPolicyBroken(I) == false)
1258                   break;
1259             }
1260
1261             if (InstOrNewPolicyBroken(I) == false)
1262                break;
1263
1264             if (Start == End)
1265                break;
1266             ++Start;
1267          }
1268
1269          if (InstOrNewPolicyBroken(I) == false)
1270             break;
1271       }
1272
1273       if (InstOrNewPolicyBroken(I) == true)
1274          continue;
1275
1276       // Restart again.
1277       if (K == LastStop) {
1278           // I is an iterator based off our temporary package list,
1279           // so copy the name we need before deleting the temporary list
1280           std::string const LoopingPackage = I.FullName(false);
1281           delete[] PList;
1282           return _error->Error("Internal Error, pkgProblemResolver::ResolveByKeep is looping on package %s.", LoopingPackage.c_str());
1283       }
1284       LastStop = K;
1285       K = PList - 1;
1286    }
1287
1288    delete[] PList;
1289    return true;
1290 }
1291                                                                         /*}}}*/
1292 // ProblemResolver::InstallProtect - deprecated cpu-eating no-op        /*{{{*/
1293 // ---------------------------------------------------------------------
1294 /* Actions issued with FromUser bit set are protected from further
1295    modification (expect by other calls with FromUser set) nowadays , so we
1296    don't need to reissue actions here, they are already set in stone. */
1297 void pkgProblemResolver::InstallProtect()
1298 {
1299    pkgDepCache::ActionGroup group(Cache);
1300
1301    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; ++I)
1302    {
1303       if ((Flags[I->ID] & Protected) == Protected)
1304       {
1305          if ((Flags[I->ID] & ToRemove) == ToRemove)
1306             Cache.MarkDelete(I);
1307          else
1308          {
1309             // preserve the information whether the package was auto
1310             // or manually installed
1311             bool autoInst = (Cache[I].Flags & pkgCache::Flag::Auto);
1312             Cache.MarkInstall(I, false, 0, !autoInst);
1313          }
1314       }
1315    }
1316 }
1317                                                                         /*}}}*/
1318 // PrioSortList - Sort a list of versions by priority                   /*{{{*/
1319 // ---------------------------------------------------------------------
1320 /* This is ment to be used in conjunction with AllTargets to get a list
1321    of versions ordered by preference. */
1322 static pkgCache *PrioCache;
1323 static int PrioComp(const void *A,const void *B)
1324 {
1325    pkgCache::VerIterator L(*PrioCache,*(pkgCache::Version **)A);
1326    pkgCache::VerIterator R(*PrioCache,*(pkgCache::Version **)B);
1327
1328    if ((L.ParentPkg()->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential &&
1329        (R.ParentPkg()->Flags & pkgCache::Flag::Essential) != pkgCache::Flag::Essential)
1330      return 1;
1331    if ((L.ParentPkg()->Flags & pkgCache::Flag::Essential) != pkgCache::Flag::Essential &&
1332        (R.ParentPkg()->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
1333      return -1;
1334
1335    if ((L.ParentPkg()->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important &&
1336        (R.ParentPkg()->Flags & pkgCache::Flag::Important) != pkgCache::Flag::Important)
1337      return 1;
1338    if ((L.ParentPkg()->Flags & pkgCache::Flag::Important) != pkgCache::Flag::Important &&
1339        (R.ParentPkg()->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important)
1340      return -1;
1341
1342    if (L->Priority != R->Priority)
1343       return R->Priority - L->Priority;
1344    return strcmp(L.ParentPkg().Name(),R.ParentPkg().Name());
1345 }
1346 void pkgPrioSortList(pkgCache &Cache,pkgCache::Version **List)
1347 {
1348    unsigned long Count = 0;
1349    PrioCache = &Cache;
1350    for (pkgCache::Version **I = List; *I != 0; I++)
1351       Count++;
1352    qsort(List,Count,sizeof(*List),PrioComp);
1353 }
1354                                                                         /*}}}*/