apt-pkg/algorithms.cc

   1 // -*- mode: cpp; mode: fold -*-
   2 // Description                                                          /*{{{*/
   3 // $Id: algorithms.cc,v 1.23 1999/07/30 02:54:25 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 (unsigned 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    unsigned int Count = 0;
 344    do
 345    {
 346       Change = false;
 347       for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 348       {
 349          // Not interesting
 350          if (Cache[I].Upgrade() == false || Cache[I].NewInstall() == true)
 351             continue;
 352
 353          // Keep it and see if that is OK
 354          Cache.MarkKeep(I);
 355          if (Cache.BrokenCount() != 0)
 356             Cache.MarkInstall(I,false);
 357          else
 358          {
 359             // If keep didnt actually do anything then there was no change..
 360             if (Cache[I].Upgrade() == false)
 361                Change = true;
 362          }
 363       }
 364       Count++;
 365    }
 366    while (Change == true && Count < 10);
 367
 368    if (Cache.BrokenCount() != 0)
 369       return _error->Error("Internal Error in pkgMinimizeUpgrade");
 370
 371    return true;
 372 }
 373                                                                         /*}}}*/
 374
 375 // ProblemResolver::pkgProblemResolver - Constructor                    /*{{{*/
 376 // ---------------------------------------------------------------------
 377 /* */
 378 pkgProblemResolver::pkgProblemResolver(pkgDepCache &Cache) : Cache(Cache)
 379 {
 380    // Allocate memory
 381    unsigned long Size = Cache.HeaderP->PackageCount;
 382    Scores = new signed short[Size];
 383    Flags = new unsigned char[Size];
 384    memset(Flags,0,sizeof(*Flags)*Size);
 385
 386    // Set debug to true to see its decision logic
 387    Debug = _config->FindB("Debug::pkgProblemResolver",false);
 388 }
 389                                                                         /*}}}*/
 390 // ProblemResolver::ScoreSort - Sort the list by score                  /*{{{*/
 391 // ---------------------------------------------------------------------
 392 /* */
 393 int pkgProblemResolver::ScoreSort(const void *a,const void *b)
 394 {
 395    Package const **A = (Package const **)a;
 396    Package const **B = (Package const **)b;
 397    if (This->Scores[(*A)->ID] > This->Scores[(*B)->ID])
 398       return -1;
 399    if (This->Scores[(*A)->ID] < This->Scores[(*B)->ID])
 400       return 1;
 401    return 0;
 402 }
 403                                                                         /*}}}*/
 404 // ProblemResolver::MakeScores - Make the score table                   /*{{{*/
 405 // ---------------------------------------------------------------------
 406 /* */
 407 void pkgProblemResolver::MakeScores()
 408 {
 409    unsigned long Size = Cache.HeaderP->PackageCount;
 410    memset(Scores,0,sizeof(*Scores)*Size);
 411
 412    // Generate the base scores for a package based on its properties
 413    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 414    {
 415       if (Cache[I].InstallVer == 0)
 416          continue;
 417
 418       signed short &Score = Scores[I->ID];
 419
 420       /* This is arbitary, it should be high enough to elevate an
 421          essantial package above most other packages but low enough
 422          to allow an obsolete essential packages to be removed by
 423          a conflicts on a powerfull normal package (ie libc6) */
 424       if ((I->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
 425          Score += 100;
 426
 427       // We transform the priority
 428       // Important Required Standard Optional Extra
 429       signed short PrioMap[] = {0,3,2,1,-1,-2};
 430       if (Cache[I].InstVerIter(Cache)->Priority <= 5)
 431          Score += PrioMap[Cache[I].InstVerIter(Cache)->Priority];
 432
 433       /* This helps to fix oddball problems with conflicting packages
 434          on the same level. We enhance the score of installed packages */
 435       if (I->CurrentVer != 0)
 436          Score += 1;
 437    }
 438
 439    // Now that we have the base scores we go and propogate dependencies
 440    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 441    {
 442       if (Cache[I].InstallVer == 0)
 443          continue;
 444
 445       for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false; D++)
 446       {
 447          if (D->Type == pkgCache::Dep::Depends || D->Type == pkgCache::Dep::PreDepends)
 448             Scores[D.TargetPkg()->ID]++;
 449       }
 450    }
 451
 452    // Copy the scores to advoid additive looping
 453    signed short *OldScores = new signed short[Size];
 454    memcpy(OldScores,Scores,sizeof(*Scores)*Size);
 455
 456    /* Now we cause 1 level of dependency inheritance, that is we add the
 457       score of the packages that depend on the target Package. This
 458       fortifies high scoring packages */
 459    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 460    {
 461       if (Cache[I].InstallVer == 0)
 462          continue;
 463
 464       for (pkgCache::DepIterator D = I.RevDependsList(); D.end() == false; D++)
 465       {
 466          // Only do it for the install version
 467          if ((pkgCache::Version *)D.ParentVer() != Cache[D.ParentPkg()].InstallVer ||
 468              (D->Type != pkgCache::Dep::Depends && D->Type != pkgCache::Dep::PreDepends))
 469             continue;
 470
 471          Scores[I->ID] += abs(OldScores[D.ParentPkg()->ID]);
 472       }
 473    }
 474
 475    /* Now we propogate along provides. This makes the packages that
 476       provide important packages extremely important */
 477    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 478    {
 479       for (pkgCache::PrvIterator P = I.ProvidesList(); P.end() == false; P++)
 480       {
 481          // Only do it once per package
 482          if ((pkgCache::Version *)P.OwnerVer() != Cache[P.OwnerPkg()].InstallVer)
 483             continue;
 484          Scores[P.OwnerPkg()->ID] += abs(Scores[I->ID] - OldScores[I->ID]);
 485       }
 486    }
 487
 488    /* Protected things are pushed really high up. This number should put them
 489       ahead of everything */
 490    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 491    {
 492       if ((Flags[I->ID] & Protected) != 0)
 493          Scores[I->ID] += 10000;
 494       if ((I->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
 495          Scores[I->ID] += 5000;
 496    }
 497
 498    delete [] OldScores;
 499 }
 500                                                                         /*}}}*/
 501 // ProblemResolver::DoUpgrade - Attempt to upgrade this package         /*{{{*/
 502 // ---------------------------------------------------------------------
 503 /* This goes through and tries to reinstall packages to make this package
 504    installable */
 505 bool pkgProblemResolver::DoUpgrade(pkgCache::PkgIterator Pkg)
 506 {
 507    if ((Flags[Pkg->ID] & Upgradable) == 0 || Cache[Pkg].Upgradable() == false)
 508       return false;
 509
 510    Flags[Pkg->ID] &= ~Upgradable;
 511
 512    bool WasKept = Cache[Pkg].Keep();
 513    Cache.MarkInstall(Pkg,false);
 514
 515    // This must be a virtual package or something like that.
 516    if (Cache[Pkg].InstVerIter(Cache).end() == true)
 517       return false;
 518
 519    // Isolate the problem dependency
 520    bool Fail = false;
 521    for (pkgCache::DepIterator D = Cache[Pkg].InstVerIter(Cache).DependsList(); D.end() == false;)
 522    {
 523       // Compute a single dependency element (glob or)
 524       pkgCache::DepIterator Start = D;
 525       pkgCache::DepIterator End = D;
 526       unsigned char State = 0;
 527       for (bool LastOR = true; D.end() == false && LastOR == true; D++)
 528       {
 529          State |= Cache[D];
 530          LastOR = (D->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or;
 531          if (LastOR == true)
 532             End = D;
 533       }
 534
 535       // We only worry about critical deps.
 536       if (End.IsCritical() != true)
 537          continue;
 538
 539       // Dep is ok
 540       if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
 541          continue;
 542
 543       // Hm, the group is broken.. I have no idea how to handle this
 544       if (Start != End)
 545       {
 546          clog << "Note, a broken or group was found in " << Pkg.Name() << "." << endl;
 547          Fail = true;
 548          break;
 549       }
 550
 551       // Do not change protected packages
 552       PkgIterator P = Start.SmartTargetPkg();
 553       if ((Flags[P->ID] & Protected) == Protected)
 554       {
 555          if (Debug == true)
 556             clog << "    Reinet Failed because of protected " << P.Name() << endl;
 557          Fail = true;
 558          break;
 559       }
 560
 561       // Upgrade the package if the candidate version will fix the problem.
 562       if ((Cache[Start] & pkgDepCache::DepCVer) == pkgDepCache::DepCVer)
 563       {
 564          if (DoUpgrade(P) == false)
 565          {
 566             if (Debug == true)
 567                clog << "    Reinst Failed because of " << P.Name() << endl;
 568             Fail = true;
 569             break;
 570          }
 571       }
 572       else
 573       {
 574          /* We let the algorithm deal with conflicts on its next iteration,
 575             it is much smarter than us */
 576          if (End->Type == pkgCache::Dep::Conflicts)
 577             continue;
 578
 579          if (Debug == true)
 580             clog << "    Reinst Failed early because of " << Start.TargetPkg().Name() << endl;
 581          Fail = true;
 582          break;
 583       }
 584    }
 585
 586    // Undo our operations - it might be smart to undo everything this did..
 587    if (Fail == true)
 588    {
 589       if (WasKept == true)
 590          Cache.MarkKeep(Pkg);
 591       else
 592          Cache.MarkDelete(Pkg);
 593       return false;
 594    }
 595
 596    if (Debug == true)
 597       clog << "  Re-Instated " << Pkg.Name() << endl;
 598    return true;
 599 }
 600                                                                         /*}}}*/
 601 // ProblemResolver::Resolve - Run the resolution pass                   /*{{{*/
 602 // ---------------------------------------------------------------------
 603 /* This routines works by calculating a score for each package. The score
 604    is derived by considering the package's priority and all reverse
 605    dependents giving an integer that reflects the amount of breakage that
 606    adjusting the package will inflict.
 607
 608    It goes from highest score to lowest and corrects all of the breaks by
 609    keeping or removing the dependant packages. If that fails then it removes
 610    the package itself and goes on. The routine should be able to intelligently
 611    go from any broken state to a fixed state.
 612
 613    The BrokenFix flag enables a mode where the algorithm tries to
 614    upgrade packages to advoid problems. */
 615 bool pkgProblemResolver::Resolve(bool BrokenFix)
 616 {
 617    unsigned long Size = Cache.HeaderP->PackageCount;
 618
 619    // Record which packages are marked for install
 620    bool Again = false;
 621    do
 622    {
 623       Again = false;
 624       for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 625       {
 626          if (Cache[I].Install() == true)
 627             Flags[I->ID] |= PreInstalled;
 628          else
 629          {
 630             if (Cache[I].InstBroken() == true && BrokenFix == true)
 631             {
 632                Cache.MarkInstall(I,false);
 633                if (Cache[I].Install() == true)
 634                   Again = true;
 635             }
 636
 637             Flags[I->ID] &= ~PreInstalled;
 638          }
 639          Flags[I->ID] |= Upgradable;
 640       }
 641    }
 642    while (Again == true);
 643
 644    if (Debug == true)
 645       clog << "Starting" << endl;
 646
 647    MakeScores();
 648
 649    /* We have to order the packages so that the broken fixing pass
 650       operates from highest score to lowest. This prevents problems when
 651       high score packages cause the removal of lower score packages that
 652       would cause the removal of even lower score packages. */
 653    pkgCache::Package **PList = new pkgCache::Package *[Size];
 654    pkgCache::Package **PEnd = PList;
 655    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 656       *PEnd++ = I;
 657    This = this;
 658    qsort(PList,PEnd - PList,sizeof(*PList),&ScoreSort);
 659
 660 /* for (pkgCache::Package **K = PList; K != PEnd; K++)
 661       if (Scores[(*K)->ID] != 0)
 662       {
 663          pkgCache::PkgIterator Pkg(Cache,*K);
 664          clog << Scores[(*K)->ID] << ' ' << Pkg.Name() <<
 665             ' ' << (pkgCache::Version *)Pkg.CurrentVer() << ' ' <<
 666             Cache[Pkg].InstallVer << ' ' << Cache[Pkg].CandidateVer << endl;
 667       } */
 668
 669    if (Debug == true)
 670       clog << "Starting 2" << endl;
 671
 672    /* Now consider all broken packages. For each broken package we either
 673       remove the package or fix it's problem. We do this once, it should
 674       not be possible for a loop to form (that is a < b < c and fixing b by
 675       changing a breaks c) */
 676    bool Change = true;
 677    for (int Counter = 0; Counter != 10 && Change == true; Counter++)
 678    {
 679       Change = false;
 680       for (pkgCache::Package **K = PList; K != PEnd; K++)
 681       {
 682          pkgCache::PkgIterator I(Cache,*K);
 683
 684          /* We attempt to install this and see if any breaks result,
 685             this takes care of some strange cases */
 686          if (Cache[I].CandidateVer != Cache[I].InstallVer &&
 687              I->CurrentVer != 0 && Cache[I].InstallVer != 0 &&
 688              (Flags[I->ID] & PreInstalled) != 0 &&
 689              (Flags[I->ID] & Protected) == 0 &&
 690              (Flags[I->ID] & ReInstateTried) == 0)
 691          {
 692             if (Debug == true)
 693                clog << " Try to Re-Instate " << I.Name() << endl;
 694             unsigned long OldBreaks = Cache.BrokenCount();
 695             pkgCache::Version *OldVer = Cache[I].InstallVer;
 696             Flags[I->ID] &= ReInstateTried;
 697
 698             Cache.MarkInstall(I,false);
 699             if (Cache[I].InstBroken() == true ||
 700                 OldBreaks < Cache.BrokenCount())
 701             {
 702                if (OldVer == 0)
 703                   Cache.MarkDelete(I);
 704                else
 705                   Cache.MarkKeep(I);
 706             }
 707             else
 708                if (Debug == true)
 709                   clog << "Re-Instated " << I.Name() << " (" << OldBreaks << " vs " << Cache.BrokenCount() << ')' << endl;
 710          }
 711
 712          if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false)
 713             continue;
 714
 715          // Isolate the problem dependency
 716          PackageKill KillList[100];
 717          PackageKill *LEnd = KillList;
 718          for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false;)
 719          {
 720             // Compute a single dependency element (glob or)
 721             pkgCache::DepIterator Start;
 722             pkgCache::DepIterator End;
 723             D.GlobOr(Start,End);
 724
 725             // We only worry about critical deps.
 726             if (End.IsCritical() != true)
 727                continue;
 728
 729             // Dep is ok
 730             if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
 731                continue;
 732
 733             // Hm, the group is broken.. I have no idea how to handle this
 734             if (Start != End)
 735             {
 736                if (Debug == true)
 737                   clog << "Note, a broken or group was found in " << I.Name() << "." << endl;
 738                if ((Flags[I->ID] & Protected) != Protected)
 739                   Cache.MarkDelete(I);
 740                break;
 741             }
 742
 743             if (Debug == true)
 744                clog << "Package " << I.Name() << " has broken dep on " << End.TargetPkg().Name() << endl;
 745
 746             /* Look across the version list. If there are no possible
 747                targets then we keep the package and bail. This is necessary
 748                if a package has a dep on another package that cant be found */
 749             pkgCache::Version **VList = End.AllTargets();
 750             if (*VList == 0 && (Flags[I->ID] & Protected) != Protected &&
 751                 End->Type != pkgCache::Dep::Conflicts &&
 752                 Cache[I].NowBroken() == false)
 753             {
 754                Change = true;
 755                Cache.MarkKeep(I);
 756                break;
 757             }
 758
 759             bool Done = false;
 760             for (pkgCache::Version **V = VList; *V != 0; V++)
 761             {
 762                pkgCache::VerIterator Ver(Cache,*V);
 763                pkgCache::PkgIterator Pkg = Ver.ParentPkg();
 764
 765                if (Debug == true)
 766                   clog << "  Considering " << Pkg.Name() << ' ' << (int)Scores[Pkg->ID] <<
 767                   " as a solution to " << I.Name() << ' ' << (int)Scores[I->ID] << endl;
 768                if (Scores[I->ID] <= Scores[Pkg->ID] ||
 769                    ((Cache[End] & pkgDepCache::DepGNow) == 0 &&
 770                     End->Type != pkgCache::Dep::Conflicts))
 771                {
 772                   // Try a little harder to fix protected packages..
 773                   if ((Flags[I->ID] & Protected) == Protected)
 774                   {
 775                      if (DoUpgrade(Pkg) == true)
 776                         Scores[Pkg->ID] = Scores[I->ID];
 777                      continue;
 778                   }
 779
 780                   /* See if a keep will do, unless the package is protected,
 781                      then installing it will be necessary */
 782                   Cache.MarkKeep(I);
 783                   if (Cache[I].InstBroken() == false)
 784                   {
 785                      if (Debug == true)
 786                         clog << "  Holding Back " << I.Name() << " rather than change " << End.TargetPkg().Name() << endl;
 787                   }
 788                   else
 789                   {
 790                      if (BrokenFix == false || DoUpgrade(I) == false)
 791                      {
 792                         if (Debug == true)
 793                            clog << "  Removing " << I.Name() << " rather than change " << End.TargetPkg().Name() << endl;
 794                         Cache.MarkDelete(I);
 795                         if (Counter > 1)
 796                            Scores[I->ID] = Scores[Pkg->ID];
 797                      }
 798                   }
 799
 800                   Change = true;
 801                   Done = true;
 802                   break;
 803                }
 804                else
 805                {
 806                   // Skip this if it is protected
 807                   if ((Flags[Pkg->ID] & Protected) != 0)
 808                      continue;
 809
 810                   LEnd->Pkg = Pkg;
 811                   LEnd->Dep = End;
 812                   LEnd++;
 813
 814                   if (End->Type != pkgCache::Dep::Conflicts)
 815                      break;
 816                }
 817             }
 818
 819             // Hm, nothing can possibly satisify this dep. Nuke it.
 820             if (VList[0] == 0 && End->Type != pkgCache::Dep::Conflicts &&
 821                 (Flags[I->ID] & Protected) != Protected)
 822             {
 823                Cache.MarkKeep(I);
 824                if (Cache[I].InstBroken() == false)
 825                {
 826                   if (Debug == true)
 827                      clog << "  Holding Back " << I.Name() << " because I can't find " << End.TargetPkg().Name() << endl;
 828                }
 829                else
 830                {
 831                   if (Debug == true)
 832                      clog << "  Removing " << I.Name() << " because I can't find " << End.TargetPkg().Name() << endl;
 833                   Cache.MarkDelete(I);
 834                }
 835
 836                Change = true;
 837                Done = true;
 838             }
 839
 840             delete [] VList;
 841             if (Done == true)
 842                break;
 843          }
 844
 845          // Apply the kill list now
 846          if (Cache[I].InstallVer != 0)
 847             for (PackageKill *J = KillList; J != LEnd; J++)
 848          {
 849             Change = true;
 850             if ((Cache[J->Dep] & pkgDepCache::DepGNow) == 0)
 851             {
 852                if (J->Dep->Type == pkgCache::Dep::Conflicts)
 853                {
 854                   if (Debug == true)
 855                      clog << "  Fixing " << I.Name() << " via remove of " << J->Pkg.Name() << endl;
 856                   Cache.MarkDelete(J->Pkg);
 857                }
 858             }
 859             else
 860             {
 861                if (Debug == true)
 862                   clog << "  Fixing " << I.Name() << " via keep of " << J->Pkg.Name() << endl;
 863                Cache.MarkKeep(J->Pkg);
 864             }
 865
 866             if (Counter > 1)
 867                Scores[J->Pkg->ID] = Scores[I->ID];
 868          }
 869       }
 870    }
 871
 872    if (Debug == true)
 873       clog << "Done" << endl;
 874
 875    delete [] Scores;
 876    delete [] PList;
 877
 878    if (Cache.BrokenCount() != 0)
 879    {
 880       // See if this is the result of a hold
 881       pkgCache::PkgIterator I = Cache.PkgBegin();
 882       for (;I.end() != true; I++)
 883       {
 884          if (Cache[I].InstBroken() == false)
 885             continue;
 886          if ((Flags[I->ID] & Protected) != Protected)
 887             return _error->Error("Error, pkgProblemResolver::Resolve generated breaks, this may be caused by held packages.");
 888       }
 889       return _error->Error("Unable to correct problems, you have held broken packages.");
 890    }
 891
 892    return true;
 893 }
 894                                                                         /*}}}*/
 895 // ProblemResolver::ResolveByKeep - Resolve problems using keep         /*{{{*/
 896 // ---------------------------------------------------------------------
 897 /* This is the work horse of the soft upgrade routine. It is very gental
 898    in that it does not install or remove any packages. It is assumed that the
 899    system was non-broken previously. */
 900 bool pkgProblemResolver::ResolveByKeep()
 901 {
 902    unsigned long Size = Cache.HeaderP->PackageCount;
 903
 904    if (Debug == true)
 905       clog << "Entering ResolveByKeep" << endl;
 906
 907    MakeScores();
 908
 909    /* We have to order the packages so that the broken fixing pass
 910       operates from highest score to lowest. This prevents problems when
 911       high score packages cause the removal of lower score packages that
 912       would cause the removal of even lower score packages. */
 913    pkgCache::Package **PList = new pkgCache::Package *[Size];
 914    pkgCache::Package **PEnd = PList;
 915    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 916       *PEnd++ = I;
 917    This = this;
 918    qsort(PList,PEnd - PList,sizeof(*PList),&ScoreSort);
 919
 920    // Consider each broken package
 921    pkgCache::Package **LastStop = 0;
 922    for (pkgCache::Package **K = PList; K != PEnd; K++)
 923    {
 924       pkgCache::PkgIterator I(Cache,*K);
 925
 926       if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false)
 927          continue;
 928
 929       /* Keep the package. If this works then great, otherwise we have
 930          to be significantly more agressive and manipulate its dependencies */
 931       if ((Flags[I->ID] & Protected) == 0)
 932       {
 933          if (Debug == true)
 934             clog << "Keeping package " << I.Name() << endl;
 935          Cache.MarkKeep(I);
 936          if (Cache[I].InstBroken() == false)
 937          {
 938             K = PList;
 939             continue;
 940          }
 941       }
 942
 943       // Isolate the problem dependencies
 944       for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false;)
 945       {
 946          // Compute a single dependency element (glob or)
 947          pkgCache::DepIterator Start = D;
 948          pkgCache::DepIterator End = D;
 949          unsigned char State = 0;
 950          for (bool LastOR = true; D.end() == false && LastOR == true; D++)
 951          {
 952             State |= Cache[D];
 953             LastOR = (D->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or;
 954             if (LastOR == true)
 955                End = D;
 956          }
 957
 958          // We only worry about critical deps.
 959          if (End.IsCritical() != true)
 960             continue;
 961
 962          // Dep is ok
 963          if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
 964             continue;
 965
 966          // Hm, the group is broken.. I have no idea how to handle this
 967          if (Start != End)
 968          {
 969             clog << "Note, a broken or group was found in " << I.Name() << "." << endl;
 970             if ((Flags[I->ID] & Protected) == 0)
 971                Cache.MarkKeep(I);
 972             break;
 973          }
 974
 975          if (Debug == true)
 976             clog << "Package " << I.Name() << " has broken dep on " << End.TargetPkg().Name() << endl;
 977
 978          // Look at all the possible provides on this package
 979          pkgCache::Version **VList = End.AllTargets();
 980          for (pkgCache::Version **V = VList; *V != 0; V++)
 981          {
 982             pkgCache::VerIterator Ver(Cache,*V);
 983             pkgCache::PkgIterator Pkg = Ver.ParentPkg();
 984
 985             // It is not keepable
 986             if (Cache[Pkg].InstallVer == 0 ||
 987                 Pkg->CurrentVer == 0)
 988                continue;
 989
 990             if ((Flags[I->ID] & Protected) == 0)
 991             {
 992                if (Debug == true)
 993                   clog << "  Keeping Package " << Pkg.Name() << " due to dep" << endl;
 994                Cache.MarkKeep(Pkg);
 995             }
 996
 997             if (Cache[I].InstBroken() == false)
 998                break;
 999          }
1000
1001          if (Cache[I].InstBroken() == false)
1002             break;
1003       }
1004
1005       if (Cache[I].InstBroken() == true)
1006          continue;
1007
1008       // Restart again.
1009       if (K == LastStop)
1010          return _error->Error("Internal Error, pkgProblemResolver::ResolveByKeep is looping on package %s.",I.Name());
1011       LastStop = K;
1012       K = PList;
1013    }
1014
1015    return true;
1016 }
1017                                                                         /*}}}*/
1018 // ProblemResolver::InstallProtect - Install all protected packages     /*{{{*/
1019 // ---------------------------------------------------------------------
1020 /* This is used to make sure protected packages are installed */
1021 void pkgProblemResolver::InstallProtect()
1022 {
1023    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
1024    {
1025       if ((Flags[I->ID] & Protected) == Protected)
1026       {
1027          if ((Flags[I->ID] & ToRemove) == ToRemove)
1028             Cache.MarkDelete(I);
1029          else
1030             Cache.MarkInstall(I,false);
1031       }
1032    }
1033 }
1034                                                                         /*}}}*/