apt-pkg/algorithms.cc

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