apt-pkg/algorithms.cc

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