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