apt-pkg/algorithms.cc

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