apt-pkg/algorithms.cc

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