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 (I->CurrentVer != 0)
 499          Score += 1;
 500    }
 501
 502    // Now that we have the base scores we go and propogate dependencies
 503    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 504    {
 505       if (Cache[I].InstallVer == 0)
 506          continue;
 507
 508       for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false; D++)
 509       {
 510          if (D->Type == pkgCache::Dep::Depends || D->Type == pkgCache::Dep::PreDepends)
 511             Scores[D.TargetPkg()->ID]++;
 512       }
 513    }
 514
 515    // Copy the scores to advoid additive looping
 516    SPtrArray<signed short> OldScores = new signed short[Size];
 517    memcpy(OldScores,Scores,sizeof(*Scores)*Size);
 518
 519    /* Now we cause 1 level of dependency inheritance, that is we add the
 520       score of the packages that depend on the target Package. This
 521       fortifies high scoring packages */
 522    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 523    {
 524       if (Cache[I].InstallVer == 0)
 525          continue;
 526
 527       for (pkgCache::DepIterator D = I.RevDependsList(); D.end() == false; D++)
 528       {
 529          // Only do it for the install version
 530          if ((pkgCache::Version *)D.ParentVer() != Cache[D.ParentPkg()].InstallVer ||
 531              (D->Type != pkgCache::Dep::Depends && D->Type != pkgCache::Dep::PreDepends))
 532             continue;
 533
 534          Scores[I->ID] += abs(OldScores[D.ParentPkg()->ID]);
 535       }
 536    }
 537
 538    /* Now we propogate along provides. This makes the packages that
 539       provide important packages extremely important */
 540    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 541    {
 542       for (pkgCache::PrvIterator P = I.ProvidesList(); P.end() == false; P++)
 543       {
 544          // Only do it once per package
 545          if ((pkgCache::Version *)P.OwnerVer() != Cache[P.OwnerPkg()].InstallVer)
 546             continue;
 547          Scores[P.OwnerPkg()->ID] += abs(Scores[I->ID] - OldScores[I->ID]);
 548       }
 549    }
 550
 551    /* Protected things are pushed really high up. This number should put them
 552       ahead of everything */
 553    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 554    {
 555       if ((Flags[I->ID] & Protected) != 0)
 556          Scores[I->ID] += 10000;
 557       if ((I->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
 558          Scores[I->ID] += 5000;
 559    }
 560 }
 561                                                                         /*}}}*/
 562 // ProblemResolver::DoUpgrade - Attempt to upgrade this package         /*{{{*/
 563 // ---------------------------------------------------------------------
 564 /* This goes through and tries to reinstall packages to make this package
 565    installable */
 566 bool pkgProblemResolver::DoUpgrade(pkgCache::PkgIterator Pkg)
 567 {
 568    if ((Flags[Pkg->ID] & Upgradable) == 0 || Cache[Pkg].Upgradable() == false)
 569       return false;
 570    if ((Flags[Pkg->ID] & Protected) == Protected)
 571       return false;
 572
 573    Flags[Pkg->ID] &= ~Upgradable;
 574
 575    bool WasKept = Cache[Pkg].Keep();
 576    Cache.MarkInstall(Pkg,false);
 577
 578    // This must be a virtual package or something like that.
 579    if (Cache[Pkg].InstVerIter(Cache).end() == true)
 580       return false;
 581
 582    // Isolate the problem dependency
 583    bool Fail = false;
 584    for (pkgCache::DepIterator D = Cache[Pkg].InstVerIter(Cache).DependsList(); D.end() == false;)
 585    {
 586       // Compute a single dependency element (glob or)
 587       pkgCache::DepIterator Start = D;
 588       pkgCache::DepIterator End = D;
 589       unsigned char State = 0;
 590       for (bool LastOR = true; D.end() == false && LastOR == true;)
 591       {
 592          State |= Cache[D];
 593          LastOR = (D->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or;
 594          D++;
 595          if (LastOR == true)
 596             End = D;
 597       }
 598
 599       // We only worry about critical deps.
 600       if (End.IsCritical() != true)
 601          continue;
 602
 603       // Iterate over all the members in the or group
 604       while (1)
 605       {
 606          // Dep is ok now
 607          if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
 608             break;
 609
 610          // Do not change protected packages
 611          PkgIterator P = Start.SmartTargetPkg();
 612          if ((Flags[P->ID] & Protected) == Protected)
 613          {
 614             if (Debug == true)
 615                clog << "    Reinst Failed because of protected " << P.Name() << endl;
 616             Fail = true;
 617          }
 618          else
 619          {
 620             // Upgrade the package if the candidate version will fix the problem.
 621             if ((Cache[Start] & pkgDepCache::DepCVer) == pkgDepCache::DepCVer)
 622             {
 623                if (DoUpgrade(P) == false)
 624                {
 625                   if (Debug == true)
 626                      clog << "    Reinst Failed because of " << P.Name() << endl;
 627                   Fail = true;
 628                }
 629                else
 630                {
 631                   Fail = false;
 632                   break;
 633                }
 634             }
 635             else
 636             {
 637                /* We let the algorithm deal with conflicts on its next iteration,
 638                 it is much smarter than us */
 639                if (Start->Type == pkgCache::Dep::Conflicts ||
 640                    Start->Type == pkgCache::Dep::Obsoletes)
 641                    break;
 642
 643                if (Debug == true)
 644                   clog << "    Reinst Failed early because of " << Start.TargetPkg().Name() << endl;
 645                Fail = true;
 646             }
 647          }
 648
 649          if (Start == End)
 650             break;
 651          Start++;
 652       }
 653       if (Fail == true)
 654          break;
 655    }
 656
 657    // Undo our operations - it might be smart to undo everything this did..
 658    if (Fail == true)
 659    {
 660       if (WasKept == true)
 661          Cache.MarkKeep(Pkg);
 662       else
 663          Cache.MarkDelete(Pkg);
 664       return false;
 665    }
 666
 667    if (Debug == true)
 668       clog << "  Re-Instated " << Pkg.Name() << endl;
 669    return true;
 670 }
 671                                                                         /*}}}*/
 672 // ProblemResolver::Resolve - Run the resolution pass                   /*{{{*/
 673 // ---------------------------------------------------------------------
 674 /* This routines works by calculating a score for each package. The score
 675    is derived by considering the package's priority and all reverse
 676    dependents giving an integer that reflects the amount of breakage that
 677    adjusting the package will inflict.
 678
 679    It goes from highest score to lowest and corrects all of the breaks by
 680    keeping or removing the dependant packages. If that fails then it removes
 681    the package itself and goes on. The routine should be able to intelligently
 682    go from any broken state to a fixed state.
 683
 684    The BrokenFix flag enables a mode where the algorithm tries to
 685    upgrade packages to advoid problems. */
 686 bool pkgProblemResolver::Resolve(bool BrokenFix)
 687 {
 688    unsigned long Size = Cache.Head().PackageCount;
 689
 690    // Record which packages are marked for install
 691    bool Again = false;
 692    do
 693    {
 694       Again = false;
 695       for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 696       {
 697          if (Cache[I].Install() == true)
 698             Flags[I->ID] |= PreInstalled;
 699          else
 700          {
 701             if (Cache[I].InstBroken() == true && BrokenFix == true)
 702             {
 703                Cache.MarkInstall(I,false);
 704                if (Cache[I].Install() == true)
 705                   Again = true;
 706             }
 707
 708             Flags[I->ID] &= ~PreInstalled;
 709          }
 710          Flags[I->ID] |= Upgradable;
 711       }
 712    }
 713    while (Again == true);
 714
 715    if (Debug == true)
 716       clog << "Starting" << endl;
 717
 718    MakeScores();
 719
 720    /* We have to order the packages so that the broken fixing pass
 721       operates from highest score to lowest. This prevents problems when
 722       high score packages cause the removal of lower score packages that
 723       would cause the removal of even lower score packages. */
 724    SPtrArray<pkgCache::Package *> PList = new pkgCache::Package *[Size];
 725    pkgCache::Package **PEnd = PList;
 726    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 727       *PEnd++ = I;
 728    This = this;
 729    qsort(PList,PEnd - PList,sizeof(*PList),&ScoreSort);
 730
 731 /* for (pkgCache::Package **K = PList; K != PEnd; K++)
 732       if (Scores[(*K)->ID] != 0)
 733       {
 734          pkgCache::PkgIterator Pkg(Cache,*K);
 735          clog << Scores[(*K)->ID] << ' ' << Pkg.Name() <<
 736             ' ' << (pkgCache::Version *)Pkg.CurrentVer() << ' ' <<
 737             Cache[Pkg].InstallVer << ' ' << Cache[Pkg].CandidateVer << endl;
 738       } */
 739
 740    if (Debug == true)
 741       clog << "Starting 2" << endl;
 742
 743    /* Now consider all broken packages. For each broken package we either
 744       remove the package or fix it's problem. We do this once, it should
 745       not be possible for a loop to form (that is a < b < c and fixing b by
 746       changing a breaks c) */
 747    bool Change = true;
 748    for (int Counter = 0; Counter != 10 && Change == true; Counter++)
 749    {
 750       Change = false;
 751       for (pkgCache::Package **K = PList; K != PEnd; K++)
 752       {
 753          pkgCache::PkgIterator I(Cache,*K);
 754
 755          /* We attempt to install this and see if any breaks result,
 756             this takes care of some strange cases */
 757          if (Cache[I].CandidateVer != Cache[I].InstallVer &&
 758              I->CurrentVer != 0 && Cache[I].InstallVer != 0 &&
 759              (Flags[I->ID] & PreInstalled) != 0 &&
 760              (Flags[I->ID] & Protected) == 0 &&
 761              (Flags[I->ID] & ReInstateTried) == 0)
 762          {
 763             if (Debug == true)
 764                clog << " Try to Re-Instate " << I.Name() << endl;
 765             unsigned long OldBreaks = Cache.BrokenCount();
 766             pkgCache::Version *OldVer = Cache[I].InstallVer;
 767             Flags[I->ID] &= ReInstateTried;
 768
 769             Cache.MarkInstall(I,false);
 770             if (Cache[I].InstBroken() == true ||
 771                 OldBreaks < Cache.BrokenCount())
 772             {
 773                if (OldVer == 0)
 774                   Cache.MarkDelete(I);
 775                else
 776                   Cache.MarkKeep(I);
 777             }
 778             else
 779                if (Debug == true)
 780                   clog << "Re-Instated " << I.Name() << " (" << OldBreaks << " vs " << Cache.BrokenCount() << ')' << endl;
 781          }
 782
 783          if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false)
 784             continue;
 785
 786          if (Debug == true)
 787             clog << "Investigating " << I.Name() << endl;
 788
 789          // Isolate the problem dependency
 790          PackageKill KillList[100];
 791          PackageKill *LEnd = KillList;
 792          bool InOr = false;
 793          pkgCache::DepIterator Start;
 794          pkgCache::DepIterator End;
 795          PackageKill *OldEnd = LEnd;
 796
 797          enum {OrRemove,OrKeep} OrOp = OrRemove;
 798          for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList();
 799               D.end() == false || InOr == true;)
 800          {
 801             // Compute a single dependency element (glob or)
 802             if (Start == End)
 803             {
 804                // Decide what to do
 805                if (InOr == true)
 806                {
 807                   if (OldEnd == LEnd && OrOp == OrRemove)
 808                   {
 809                      if ((Flags[I->ID] & Protected) != Protected)
 810                      {
 811                         if (Debug == true)
 812                            clog << "  Or group remove for " << I.Name() << endl;
 813                         Cache.MarkDelete(I);
 814                         Change = true;
 815                      }
 816                   }
 817                   if (OldEnd == LEnd && OrOp == OrKeep)
 818                   {
 819                      if (Debug == true)
 820                         clog << "  Or group keep for " << I.Name() << endl;
 821                      Cache.MarkKeep(I);
 822                      Change = true;
 823                   }
 824                }
 825
 826                /* We do an extra loop (as above) to finalize the or group
 827                   processing */
 828                InOr = false;
 829                OrOp = OrRemove;
 830                D.GlobOr(Start,End);
 831                if (Start.end() == true)
 832                   break;
 833
 834                // We only worry about critical deps.
 835                if (End.IsCritical() != true)
 836                   continue;
 837
 838                InOr = Start != End;
 839                OldEnd = LEnd;
 840             }
 841             else
 842                Start++;
 843
 844             // Dep is ok
 845             if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
 846             {
 847                InOr = false;
 848                continue;
 849             }
 850
 851             if (Debug == true)
 852                clog << "Package " << I.Name() << " has broken dep on " << Start.TargetPkg().Name() << endl;
 853
 854             /* Look across the version list. If there are no possible
 855                targets then we keep the package and bail. This is necessary
 856                if a package has a dep on another package that cant be found */
 857             SPtrArray<pkgCache::Version *> VList = Start.AllTargets();
 858             if (*VList == 0 && (Flags[I->ID] & Protected) != Protected &&
 859                 Start->Type != pkgCache::Dep::Conflicts &&
 860                 Start->Type != pkgCache::Dep::Obsoletes &&
 861                 Cache[I].NowBroken() == false)
 862             {
 863                if (InOr == true)
 864                {
 865                   /* No keep choice because the keep being OK could be the
 866                      result of another element in the OR group! */
 867                   continue;
 868                }
 869
 870                Change = true;
 871                Cache.MarkKeep(I);
 872                break;
 873             }
 874
 875             bool Done = false;
 876             for (pkgCache::Version **V = VList; *V != 0; V++)
 877             {
 878                pkgCache::VerIterator Ver(Cache,*V);
 879                pkgCache::PkgIterator Pkg = Ver.ParentPkg();
 880
 881                if (Debug == true)
 882                   clog << "  Considering " << Pkg.Name() << ' ' << (int)Scores[Pkg->ID] <<
 883                   " as a solution to " << I.Name() << ' ' << (int)Scores[I->ID] << endl;
 884
 885                /* Try to fix the package under consideration rather than
 886                   fiddle with the VList package */
 887                if (Scores[I->ID] <= Scores[Pkg->ID] ||
 888                    ((Cache[Start] & pkgDepCache::DepNow) == 0 &&
 889                     End->Type != pkgCache::Dep::Conflicts &&
 890                     End->Type != pkgCache::Dep::Obsoletes))
 891                {
 892                   // Try a little harder to fix protected packages..
 893                   if ((Flags[I->ID] & Protected) == Protected)
 894                   {
 895                      if (DoUpgrade(Pkg) == true)
 896                      {
 897                         if (Scores[Pkg->ID] > Scores[I->ID])
 898                            Scores[Pkg->ID] = Scores[I->ID];
 899                         break;
 900                      }
 901
 902                      continue;
 903                   }
 904
 905                   /* See if a keep will do, unless the package is protected,
 906                      then installing it will be necessary */
 907                   bool Installed = Cache[I].Install();
 908                   Cache.MarkKeep(I);
 909                   if (Cache[I].InstBroken() == false)
 910                   {
 911                      // Unwind operation will be keep now
 912                      if (OrOp == OrRemove)
 913                         OrOp = OrKeep;
 914
 915                      // Restore
 916                      if (InOr == true && Installed == true)
 917                         Cache.MarkInstall(I,false);
 918
 919                      if (Debug == true)
 920                         clog << "  Holding Back " << I.Name() << " rather than change " << Start.TargetPkg().Name() << endl;
 921                   }
 922                   else
 923                   {
 924                      if (BrokenFix == false || DoUpgrade(I) == false)
 925                      {
 926                         // Consider other options
 927                         if (InOr == false)
 928                         {
 929                            if (Debug == true)
 930                               clog << "  Removing " << I.Name() << " rather than change " << Start.TargetPkg().Name() << endl;
 931                            Cache.MarkDelete(I);
 932                            if (Counter > 1)
 933                            {
 934                               if (Scores[Pkg->ID] > Scores[I->ID])
 935                                  Scores[I->ID] = Scores[Pkg->ID];
 936                            }
 937                         }
 938                      }
 939                   }
 940
 941                   Change = true;
 942                   Done = true;
 943                   break;
 944                }
 945                else
 946                {
 947                   /* This is a conflicts, and the version we are looking
 948                      at is not the currently selected version of the
 949                      package, which means it is not necessary to
 950                      remove/keep */
 951                   if (Cache[Pkg].InstallVer != Ver &&
 952                       (Start->Type == pkgCache::Dep::Conflicts ||
 953                        Start->Type == pkgCache::Dep::Obsoletes))
 954                      continue;
 955
 956                   // Skip adding to the kill list if it is protected
 957                   if ((Flags[Pkg->ID] & Protected) != 0)
 958                      continue;
 959
 960                   if (Debug == true)
 961                      clog << "  Added " << Pkg.Name() << " to the remove list" << endl;
 962
 963                   LEnd->Pkg = Pkg;
 964                   LEnd->Dep = End;
 965                   LEnd++;
 966
 967                   if (Start->Type != pkgCache::Dep::Conflicts &&
 968                       Start->Type != pkgCache::Dep::Obsoletes)
 969                      break;
 970                }
 971             }
 972
 973             // Hm, nothing can possibly satisify this dep. Nuke it.
 974             if (VList[0] == 0 &&
 975                 Start->Type != pkgCache::Dep::Conflicts &&
 976                 Start->Type != pkgCache::Dep::Obsoletes &&
 977                 (Flags[I->ID] & Protected) != Protected)
 978             {
 979                bool Installed = Cache[I].Install();
 980                Cache.MarkKeep(I);
 981                if (Cache[I].InstBroken() == false)
 982                {
 983                   // Unwind operation will be keep now
 984                   if (OrOp == OrRemove)
 985                      OrOp = OrKeep;
 986
 987                   // Restore
 988                   if (InOr == true && Installed == true)
 989                      Cache.MarkInstall(I,false);
 990
 991                   if (Debug == true)
 992                      clog << "  Holding Back " << I.Name() << " because I can't find " << Start.TargetPkg().Name() << endl;
 993                }
 994                else
 995                {
 996                   if (Debug == true)
 997                      clog << "  Removing " << I.Name() << " because I can't find " << Start.TargetPkg().Name() << endl;
 998                   if (InOr == false)
 999                      Cache.MarkDelete(I);
1000                }
1001
1002                Change = true;
1003                Done = true;
1004             }
1005
1006             // Try some more
1007             if (InOr == true)
1008                continue;
1009
1010             if (Done == true)
1011                break;
1012          }
1013
1014          // Apply the kill list now
1015          if (Cache[I].InstallVer != 0)
1016          {
1017             for (PackageKill *J = KillList; J != LEnd; J++)
1018             {
1019                Change = true;
1020                if ((Cache[J->Dep] & pkgDepCache::DepGNow) == 0)
1021                {
1022                   if (J->Dep->Type == pkgCache::Dep::Conflicts ||
1023                       J->Dep->Type == pkgCache::Dep::Obsoletes)
1024                   {
1025                      if (Debug == true)
1026                         clog << "  Fixing " << I.Name() << " via remove of " << J->Pkg.Name() << endl;
1027                      Cache.MarkDelete(J->Pkg);
1028                   }
1029                }
1030                else
1031                {
1032                   if (Debug == true)
1033                      clog << "  Fixing " << I.Name() << " via keep of " << J->Pkg.Name() << endl;
1034                   Cache.MarkKeep(J->Pkg);
1035                }
1036
1037                if (Counter > 1)
1038                {
1039                   if (Scores[I->ID] > Scores[J->Pkg->ID])
1040                      Scores[J->Pkg->ID] = Scores[I->ID];
1041                }
1042             }
1043          }
1044       }
1045    }
1046
1047    if (Debug == true)
1048       clog << "Done" << endl;
1049
1050    if (Cache.BrokenCount() != 0)
1051    {
1052       // See if this is the result of a hold
1053       pkgCache::PkgIterator I = Cache.PkgBegin();
1054       for (;I.end() != true; I++)
1055       {
1056          if (Cache[I].InstBroken() == false)
1057             continue;
1058          if ((Flags[I->ID] & Protected) != Protected)
1059             return _error->Error(_("Error, pkgProblemResolver::Resolve generated breaks, this may be caused by held packages."));
1060       }
1061       return _error->Error(_("Unable to correct problems, you have held broken packages."));
1062    }
1063
1064    return true;
1065 }
1066                                                                         /*}}}*/
1067 // ProblemResolver::ResolveByKeep - Resolve problems using keep         /*{{{*/
1068 // ---------------------------------------------------------------------
1069 /* This is the work horse of the soft upgrade routine. It is very gental
1070    in that it does not install or remove any packages. It is assumed that the
1071    system was non-broken previously. */
1072 bool pkgProblemResolver::ResolveByKeep()
1073 {
1074    unsigned long Size = Cache.Head().PackageCount;
1075
1076    if (Debug == true)
1077       clog << "Entering ResolveByKeep" << endl;
1078
1079    MakeScores();
1080
1081    /* We have to order the packages so that the broken fixing pass
1082       operates from highest score to lowest. This prevents problems when
1083       high score packages cause the removal of lower score packages that
1084       would cause the removal of even lower score packages. */
1085    pkgCache::Package **PList = new pkgCache::Package *[Size];
1086    pkgCache::Package **PEnd = PList;
1087    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
1088       *PEnd++ = I;
1089    This = this;
1090    qsort(PList,PEnd - PList,sizeof(*PList),&ScoreSort);
1091
1092    // Consider each broken package
1093    pkgCache::Package **LastStop = 0;
1094    for (pkgCache::Package **K = PList; K != PEnd; K++)
1095    {
1096       pkgCache::PkgIterator I(Cache,*K);
1097
1098       if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false)
1099          continue;
1100
1101       /* Keep the package. If this works then great, otherwise we have
1102          to be significantly more agressive and manipulate its dependencies */
1103       if ((Flags[I->ID] & Protected) == 0)
1104       {
1105          if (Debug == true)
1106             clog << "Keeping package " << I.Name() << endl;
1107          Cache.MarkKeep(I);
1108          if (Cache[I].InstBroken() == false)
1109          {
1110             K = PList - 1;
1111             continue;
1112          }
1113       }
1114
1115       // Isolate the problem dependencies
1116       for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false;)
1117       {
1118          DepIterator Start;
1119          DepIterator End;
1120          D.GlobOr(Start,End);
1121
1122          // We only worry about critical deps.
1123          if (End.IsCritical() != true)
1124             continue;
1125
1126          // Dep is ok
1127          if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
1128             continue;
1129
1130          /* Hm, the group is broken.. I suppose the best thing to do is to
1131             is to try every combination of keep/not-keep for the set, but thats
1132             slow, and this never happens, just be conservative and assume the
1133             list of ors is in preference and keep till it starts to work. */
1134          while (true)
1135          {
1136             if (Debug == true)
1137                clog << "Package " << I.Name() << " has broken dep on " << Start.TargetPkg().Name() << endl;
1138
1139             // Look at all the possible provides on this package
1140             SPtrArray<pkgCache::Version *> VList = Start.AllTargets();
1141             for (pkgCache::Version **V = VList; *V != 0; V++)
1142             {
1143                pkgCache::VerIterator Ver(Cache,*V);
1144                pkgCache::PkgIterator Pkg = Ver.ParentPkg();
1145
1146                // It is not keepable
1147                if (Cache[Pkg].InstallVer == 0 ||
1148                    Pkg->CurrentVer == 0)
1149                   continue;
1150
1151                if ((Flags[I->ID] & Protected) == 0)
1152                {
1153                   if (Debug == true)
1154                      clog << "  Keeping Package " << Pkg.Name() << " due to dep" << endl;
1155                   Cache.MarkKeep(Pkg);
1156                }
1157
1158                if (Cache[I].InstBroken() == false)
1159                   break;
1160             }
1161
1162             if (Cache[I].InstBroken() == false)
1163                break;
1164
1165             if (Start == End)
1166                break;
1167             Start++;
1168          }
1169
1170          if (Cache[I].InstBroken() == false)
1171             break;
1172       }
1173
1174       if (Cache[I].InstBroken() == true)
1175          continue;
1176
1177       // Restart again.
1178       if (K == LastStop)
1179          return _error->Error("Internal Error, pkgProblemResolver::ResolveByKeep is looping on package %s.",I.Name());
1180       LastStop = K;
1181       K = PList - 1;
1182    }
1183
1184    return true;
1185 }
1186                                                                         /*}}}*/
1187 // ProblemResolver::InstallProtect - Install all protected packages     /*{{{*/
1188 // ---------------------------------------------------------------------
1189 /* This is used to make sure protected packages are installed */
1190 void pkgProblemResolver::InstallProtect()
1191 {
1192    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
1193    {
1194       if ((Flags[I->ID] & Protected) == Protected)
1195       {
1196          if ((Flags[I->ID] & ToRemove) == ToRemove)
1197             Cache.MarkDelete(I);
1198          else
1199             Cache.MarkInstall(I,false);
1200       }
1201    }
1202 }
1203                                                                         /*}}}*/
1204
1205 // PrioSortList - Sort a list of versions by priority                   /*{{{*/
1206 // ---------------------------------------------------------------------
1207 /* This is ment to be used in conjunction with AllTargets to get a list
1208    of versions ordered by preference. */
1209 static pkgCache *PrioCache;
1210 static int PrioComp(const void *A,const void *B)
1211 {
1212    pkgCache::VerIterator L(*PrioCache,*(pkgCache::Version **)A);
1213    pkgCache::VerIterator R(*PrioCache,*(pkgCache::Version **)B);
1214
1215    if ((L.ParentPkg()->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential &&
1216        (R.ParentPkg()->Flags & pkgCache::Flag::Essential) != pkgCache::Flag::Essential)
1217      return 1;
1218    if ((L.ParentPkg()->Flags & pkgCache::Flag::Essential) != pkgCache::Flag::Essential &&
1219        (R.ParentPkg()->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
1220      return -1;
1221
1222    if (L->Priority != R->Priority)
1223       return R->Priority - L->Priority;
1224    return strcmp(L.ParentPkg().Name(),R.ParentPkg().Name());
1225 }
1226 void pkgPrioSortList(pkgCache &Cache,pkgCache::Version **List)
1227 {
1228    unsigned long Count = 0;
1229    PrioCache = &Cache;
1230    for (pkgCache::Version **I = List; *I != 0; I++)
1231       Count++;
1232    qsort(List,Count,sizeof(*List),PrioComp);
1233 }
1234                                                                         /*}}}*/