apt-pkg/algorithms.cc

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