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].CandidateVer != 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             {
 845                Start++;
 846                // We only worry about critical deps.
 847                if (Start.IsCritical() != true)
 848                   continue;
 849             }
 850
 851             // Dep is ok
 852             if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
 853             {
 854                InOr = false;
 855                continue;
 856             }
 857
 858             if (Debug == true)
 859                clog << "Package " << I.Name() << " has broken dep on " << Start.TargetPkg().Name() << endl;
 860
 861             /* Look across the version list. If there are no possible
 862                targets then we keep the package and bail. This is necessary
 863                if a package has a dep on another package that cant be found */
 864             SPtrArray<pkgCache::Version *> VList = Start.AllTargets();
 865             if (*VList == 0 && (Flags[I->ID] & Protected) != Protected &&
 866                 Start->Type != pkgCache::Dep::Conflicts &&
 867                 Start->Type != pkgCache::Dep::Obsoletes &&
 868                 Cache[I].NowBroken() == false)
 869             {
 870                if (InOr == true)
 871                {
 872                   /* No keep choice because the keep being OK could be the
 873                      result of another element in the OR group! */
 874                   continue;
 875                }
 876
 877                Change = true;
 878                Cache.MarkKeep(I);
 879                break;
 880             }
 881
 882             bool Done = false;
 883             for (pkgCache::Version **V = VList; *V != 0; V++)
 884             {
 885                pkgCache::VerIterator Ver(Cache,*V);
 886                pkgCache::PkgIterator Pkg = Ver.ParentPkg();
 887
 888                if (Debug == true)
 889                   clog << "  Considering " << Pkg.Name() << ' ' << (int)Scores[Pkg->ID] <<
 890                   " as a solution to " << I.Name() << ' ' << (int)Scores[I->ID] << endl;
 891
 892                /* Try to fix the package under consideration rather than
 893                   fiddle with the VList package */
 894                if (Scores[I->ID] <= Scores[Pkg->ID] ||
 895                    ((Cache[Start] & pkgDepCache::DepNow) == 0 &&
 896                     End->Type != pkgCache::Dep::Conflicts &&
 897                     End->Type != pkgCache::Dep::Obsoletes))
 898                {
 899                   // Try a little harder to fix protected packages..
 900                   if ((Flags[I->ID] & Protected) == Protected)
 901                   {
 902                      if (DoUpgrade(Pkg) == true)
 903                      {
 904                         if (Scores[Pkg->ID] > Scores[I->ID])
 905                            Scores[Pkg->ID] = Scores[I->ID];
 906                         break;
 907                      }
 908
 909                      continue;
 910                   }
 911
 912                   /* See if a keep will do, unless the package is protected,
 913                      then installing it will be necessary */
 914                   bool Installed = Cache[I].Install();
 915                   Cache.MarkKeep(I);
 916                   if (Cache[I].InstBroken() == false)
 917                   {
 918                      // Unwind operation will be keep now
 919                      if (OrOp == OrRemove)
 920                         OrOp = OrKeep;
 921
 922                      // Restore
 923                      if (InOr == true && Installed == true)
 924                         Cache.MarkInstall(I,false);
 925
 926                      if (Debug == true)
 927                         clog << "  Holding Back " << I.Name() << " rather than change " << Start.TargetPkg().Name() << endl;
 928                   }
 929                   else
 930                   {
 931                      if (BrokenFix == false || DoUpgrade(I) == false)
 932                      {
 933                         // Consider other options
 934                         if (InOr == false)
 935                         {
 936                            if (Debug == true)
 937                               clog << "  Removing " << I.Name() << " rather than change " << Start.TargetPkg().Name() << endl;
 938                            Cache.MarkDelete(I);
 939                            if (Counter > 1)
 940                            {
 941                               if (Scores[Pkg->ID] > Scores[I->ID])
 942                                  Scores[I->ID] = Scores[Pkg->ID];
 943                            }
 944                         }
 945                      }
 946                   }
 947
 948                   Change = true;
 949                   Done = true;
 950                   break;
 951                }
 952                else
 953                {
 954                   /* This is a conflicts, and the version we are looking
 955                      at is not the currently selected version of the
 956                      package, which means it is not necessary to
 957                      remove/keep */
 958                   if (Cache[Pkg].InstallVer != Ver &&
 959                       (Start->Type == pkgCache::Dep::Conflicts ||
 960                        Start->Type == pkgCache::Dep::Obsoletes))
 961                      continue;
 962
 963                   // Skip adding to the kill list if it is protected
 964                   if ((Flags[Pkg->ID] & Protected) != 0)
 965                      continue;
 966
 967                   if (Debug == true)
 968                      clog << "  Added " << Pkg.Name() << " to the remove list" << endl;
 969
 970                   LEnd->Pkg = Pkg;
 971                   LEnd->Dep = End;
 972                   LEnd++;
 973
 974                   if (Start->Type != pkgCache::Dep::Conflicts &&
 975                       Start->Type != pkgCache::Dep::Obsoletes)
 976                      break;
 977                }
 978             }
 979
 980             // Hm, nothing can possibly satisify this dep. Nuke it.
 981             if (VList[0] == 0 &&
 982                 Start->Type != pkgCache::Dep::Conflicts &&
 983                 Start->Type != pkgCache::Dep::Obsoletes &&
 984                 (Flags[I->ID] & Protected) != Protected)
 985             {
 986                bool Installed = Cache[I].Install();
 987                Cache.MarkKeep(I);
 988                if (Cache[I].InstBroken() == false)
 989                {
 990                   // Unwind operation will be keep now
 991                   if (OrOp == OrRemove)
 992                      OrOp = OrKeep;
 993
 994                   // Restore
 995                   if (InOr == true && Installed == true)
 996                      Cache.MarkInstall(I,false);
 997
 998                   if (Debug == true)
 999                      clog << "  Holding Back " << I.Name() << " because I can't find " << Start.TargetPkg().Name() << endl;
1000                }
1001                else
1002                {
1003                   if (Debug == true)
1004                      clog << "  Removing " << I.Name() << " because I can't find " << Start.TargetPkg().Name() << endl;
1005                   if (InOr == false)
1006                      Cache.MarkDelete(I);
1007                }
1008
1009                Change = true;
1010                Done = true;
1011             }
1012
1013             // Try some more
1014             if (InOr == true)
1015                continue;
1016
1017             if (Done == true)
1018                break;
1019          }
1020
1021          // Apply the kill list now
1022          if (Cache[I].InstallVer != 0)
1023          {
1024             for (PackageKill *J = KillList; J != LEnd; J++)
1025             {
1026                Change = true;
1027                if ((Cache[J->Dep] & pkgDepCache::DepGNow) == 0)
1028                {
1029                   if (J->Dep->Type == pkgCache::Dep::Conflicts ||
1030                       J->Dep->Type == pkgCache::Dep::Obsoletes)
1031                   {
1032                      if (Debug == true)
1033                         clog << "  Fixing " << I.Name() << " via remove of " << J->Pkg.Name() << endl;
1034                      Cache.MarkDelete(J->Pkg);
1035                   }
1036                }
1037                else
1038                {
1039                   if (Debug == true)
1040                      clog << "  Fixing " << I.Name() << " via keep of " << J->Pkg.Name() << endl;
1041                   Cache.MarkKeep(J->Pkg);
1042                }
1043
1044                if (Counter > 1)
1045                {
1046                   if (Scores[I->ID] > Scores[J->Pkg->ID])
1047                      Scores[J->Pkg->ID] = Scores[I->ID];
1048                }
1049             }
1050          }
1051       }
1052    }
1053
1054    if (Debug == true)
1055       clog << "Done" << endl;
1056
1057    if (Cache.BrokenCount() != 0)
1058    {
1059       // See if this is the result of a hold
1060       pkgCache::PkgIterator I = Cache.PkgBegin();
1061       for (;I.end() != true; I++)
1062       {
1063          if (Cache[I].InstBroken() == false)
1064             continue;
1065          if ((Flags[I->ID] & Protected) != Protected)
1066             return _error->Error(_("Error, pkgProblemResolver::Resolve generated breaks, this may be caused by held packages."));
1067       }
1068       return _error->Error(_("Unable to correct problems, you have held broken packages."));
1069    }
1070
1071    return true;
1072 }
1073                                                                         /*}}}*/
1074 // ProblemResolver::ResolveByKeep - Resolve problems using keep         /*{{{*/
1075 // ---------------------------------------------------------------------
1076 /* This is the work horse of the soft upgrade routine. It is very gental
1077    in that it does not install or remove any packages. It is assumed that the
1078    system was non-broken previously. */
1079 bool pkgProblemResolver::ResolveByKeep()
1080 {
1081    unsigned long Size = Cache.Head().PackageCount;
1082
1083    if (Debug == true)
1084       clog << "Entering ResolveByKeep" << endl;
1085
1086    MakeScores();
1087
1088    /* We have to order the packages so that the broken fixing pass
1089       operates from highest score to lowest. This prevents problems when
1090       high score packages cause the removal of lower score packages that
1091       would cause the removal of even lower score packages. */
1092    pkgCache::Package **PList = new pkgCache::Package *[Size];
1093    pkgCache::Package **PEnd = PList;
1094    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
1095       *PEnd++ = I;
1096    This = this;
1097    qsort(PList,PEnd - PList,sizeof(*PList),&ScoreSort);
1098
1099    // Consider each broken package
1100    pkgCache::Package **LastStop = 0;
1101    for (pkgCache::Package **K = PList; K != PEnd; K++)
1102    {
1103       pkgCache::PkgIterator I(Cache,*K);
1104
1105       if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false)
1106          continue;
1107
1108       /* Keep the package. If this works then great, otherwise we have
1109          to be significantly more agressive and manipulate its dependencies */
1110       if ((Flags[I->ID] & Protected) == 0)
1111       {
1112          if (Debug == true)
1113             clog << "Keeping package " << I.Name() << endl;
1114          Cache.MarkKeep(I);
1115          if (Cache[I].InstBroken() == false)
1116          {
1117             K = PList - 1;
1118             continue;
1119          }
1120       }
1121
1122       // Isolate the problem dependencies
1123       for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false;)
1124       {
1125          DepIterator Start;
1126          DepIterator End;
1127          D.GlobOr(Start,End);
1128
1129          // We only worry about critical deps.
1130          if (End.IsCritical() != true)
1131             continue;
1132
1133          // Dep is ok
1134          if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
1135             continue;
1136
1137          /* Hm, the group is broken.. I suppose the best thing to do is to
1138             is to try every combination of keep/not-keep for the set, but thats
1139             slow, and this never happens, just be conservative and assume the
1140             list of ors is in preference and keep till it starts to work. */
1141          while (true)
1142          {
1143             if (Debug == true)
1144                clog << "Package " << I.Name() << " has broken dep on " << Start.TargetPkg().Name() << endl;
1145
1146             // Look at all the possible provides on this package
1147             SPtrArray<pkgCache::Version *> VList = Start.AllTargets();
1148             for (pkgCache::Version **V = VList; *V != 0; V++)
1149             {
1150                pkgCache::VerIterator Ver(Cache,*V);
1151                pkgCache::PkgIterator Pkg = Ver.ParentPkg();
1152
1153                // It is not keepable
1154                if (Cache[Pkg].InstallVer == 0 ||
1155                    Pkg->CurrentVer == 0)
1156                   continue;
1157
1158                if ((Flags[I->ID] & Protected) == 0)
1159                {
1160                   if (Debug == true)
1161                      clog << "  Keeping Package " << Pkg.Name() << " due to dep" << endl;
1162                   Cache.MarkKeep(Pkg);
1163                }
1164
1165                if (Cache[I].InstBroken() == false)
1166                   break;
1167             }
1168
1169             if (Cache[I].InstBroken() == false)
1170                break;
1171
1172             if (Start == End)
1173                break;
1174             Start++;
1175          }
1176
1177          if (Cache[I].InstBroken() == false)
1178             break;
1179       }
1180
1181       if (Cache[I].InstBroken() == true)
1182          continue;
1183
1184       // Restart again.
1185       if (K == LastStop)
1186          return _error->Error("Internal Error, pkgProblemResolver::ResolveByKeep is looping on package %s.",I.Name());
1187       LastStop = K;
1188       K = PList - 1;
1189    }
1190
1191    return true;
1192 }
1193                                                                         /*}}}*/
1194 // ProblemResolver::InstallProtect - Install all protected packages     /*{{{*/
1195 // ---------------------------------------------------------------------
1196 /* This is used to make sure protected packages are installed */
1197 void pkgProblemResolver::InstallProtect()
1198 {
1199    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
1200    {
1201       if ((Flags[I->ID] & Protected) == Protected)
1202       {
1203          if ((Flags[I->ID] & ToRemove) == ToRemove)
1204             Cache.MarkDelete(I);
1205          else
1206             Cache.MarkInstall(I,false);
1207       }
1208    }
1209 }
1210                                                                         /*}}}*/
1211
1212 // PrioSortList - Sort a list of versions by priority                   /*{{{*/
1213 // ---------------------------------------------------------------------
1214 /* This is ment to be used in conjunction with AllTargets to get a list
1215    of versions ordered by preference. */
1216 static pkgCache *PrioCache;
1217 static int PrioComp(const void *A,const void *B)
1218 {
1219    pkgCache::VerIterator L(*PrioCache,*(pkgCache::Version **)A);
1220    pkgCache::VerIterator R(*PrioCache,*(pkgCache::Version **)B);
1221
1222    if ((L.ParentPkg()->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential &&
1223        (R.ParentPkg()->Flags & pkgCache::Flag::Essential) != pkgCache::Flag::Essential)
1224      return 1;
1225    if ((L.ParentPkg()->Flags & pkgCache::Flag::Essential) != pkgCache::Flag::Essential &&
1226        (R.ParentPkg()->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
1227      return -1;
1228
1229    if (L->Priority != R->Priority)
1230       return R->Priority - L->Priority;
1231    return strcmp(L.ParentPkg().Name(),R.ParentPkg().Name());
1232 }
1233 void pkgPrioSortList(pkgCache &Cache,pkgCache::Version **List)
1234 {
1235    unsigned long Count = 0;
1236    PrioCache = &Cache;
1237    for (pkgCache::Version **I = List; *I != 0; I++)
1238       Count++;
1239    qsort(List,Count,sizeof(*List),PrioComp);
1240 }
1241                                                                         /*}}}*/