apt-pkg/algorithms.cc

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