apt-pkg/algorithms.cc

   1 // -*- mode: cpp; mode: fold -*-
   2 // Description                                                          /*{{{*/
   3 // $Id: algorithms.cc,v 1.25 1999/10/02 04:14:53 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;)
 528       {
 529          State |= Cache[D];
 530          LastOR = (D->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or;
 531          D++;
 532          if (LastOR == true)
 533             End = D;
 534       }
 535
 536       // We only worry about critical deps.
 537       if (End.IsCritical() != true)
 538          continue;
 539
 540       // Iterate over all the members in the or group
 541       while (1)
 542       {
 543          // Dep is ok now
 544          if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
 545             break;
 546
 547          // Do not change protected packages
 548          PkgIterator P = Start.SmartTargetPkg();
 549          if ((Flags[P->ID] & Protected) == Protected)
 550          {
 551             if (Debug == true)
 552                clog << "    Reinet Failed because of protected " << P.Name() << endl;
 553             Fail = true;
 554             break;
 555          }
 556
 557          // Upgrade the package if the candidate version will fix the problem.
 558          if ((Cache[Start] & pkgDepCache::DepCVer) == pkgDepCache::DepCVer)
 559          {
 560             if (DoUpgrade(P) == false)
 561             {
 562                if (Debug == true)
 563                   clog << "    Reinst Failed because of " << P.Name() << endl;
 564                Fail = true;
 565                break;
 566             }
 567          }
 568          else
 569          {
 570             /* We let the algorithm deal with conflicts on its next iteration,
 571                it is much smarter than us */
 572             if (Start->Type == pkgCache::Dep::Conflicts)
 573                continue;
 574
 575             if (Debug == true)
 576                clog << "    Reinst Failed early because of " << Start.TargetPkg().Name() << endl;
 577             Fail = true;
 578             break;
 579          }
 580
 581          if (Start == End)
 582             break;
 583          Start++;
 584       }
 585       if (Fail == true)
 586          break;
 587    }
 588
 589    // Undo our operations - it might be smart to undo everything this did..
 590    if (Fail == true)
 591    {
 592       if (WasKept == true)
 593          Cache.MarkKeep(Pkg);
 594       else
 595          Cache.MarkDelete(Pkg);
 596       return false;
 597    }
 598
 599    if (Debug == true)
 600       clog << "  Re-Instated " << Pkg.Name() << endl;
 601    return true;
 602 }
 603                                                                         /*}}}*/
 604 // ProblemResolver::Resolve - Run the resolution pass                   /*{{{*/
 605 // ---------------------------------------------------------------------
 606 /* This routines works by calculating a score for each package. The score
 607    is derived by considering the package's priority and all reverse
 608    dependents giving an integer that reflects the amount of breakage that
 609    adjusting the package will inflict.
 610
 611    It goes from highest score to lowest and corrects all of the breaks by
 612    keeping or removing the dependant packages. If that fails then it removes
 613    the package itself and goes on. The routine should be able to intelligently
 614    go from any broken state to a fixed state.
 615
 616    The BrokenFix flag enables a mode where the algorithm tries to
 617    upgrade packages to advoid problems. */
 618 bool pkgProblemResolver::Resolve(bool BrokenFix)
 619 {
 620    unsigned long Size = Cache.HeaderP->PackageCount;
 621
 622    // Record which packages are marked for install
 623    bool Again = false;
 624    do
 625    {
 626       Again = false;
 627       for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 628       {
 629          if (Cache[I].Install() == true)
 630             Flags[I->ID] |= PreInstalled;
 631          else
 632          {
 633             if (Cache[I].InstBroken() == true && BrokenFix == true)
 634             {
 635                Cache.MarkInstall(I,false);
 636                if (Cache[I].Install() == true)
 637                   Again = true;
 638             }
 639
 640             Flags[I->ID] &= ~PreInstalled;
 641          }
 642          Flags[I->ID] |= Upgradable;
 643       }
 644    }
 645    while (Again == true);
 646
 647    if (Debug == true)
 648       clog << "Starting" << endl;
 649
 650    MakeScores();
 651
 652    /* We have to order the packages so that the broken fixing pass
 653       operates from highest score to lowest. This prevents problems when
 654       high score packages cause the removal of lower score packages that
 655       would cause the removal of even lower score packages. */
 656    pkgCache::Package **PList = new pkgCache::Package *[Size];
 657    pkgCache::Package **PEnd = PList;
 658    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 659       *PEnd++ = I;
 660    This = this;
 661    qsort(PList,PEnd - PList,sizeof(*PList),&ScoreSort);
 662
 663 /* for (pkgCache::Package **K = PList; K != PEnd; K++)
 664       if (Scores[(*K)->ID] != 0)
 665       {
 666          pkgCache::PkgIterator Pkg(Cache,*K);
 667          clog << Scores[(*K)->ID] << ' ' << Pkg.Name() <<
 668             ' ' << (pkgCache::Version *)Pkg.CurrentVer() << ' ' <<
 669             Cache[Pkg].InstallVer << ' ' << Cache[Pkg].CandidateVer << endl;
 670       } */
 671
 672    if (Debug == true)
 673       clog << "Starting 2" << endl;
 674
 675    /* Now consider all broken packages. For each broken package we either
 676       remove the package or fix it's problem. We do this once, it should
 677       not be possible for a loop to form (that is a < b < c and fixing b by
 678       changing a breaks c) */
 679    bool Change = true;
 680    for (int Counter = 0; Counter != 10 && Change == true; Counter++)
 681    {
 682       Change = false;
 683       for (pkgCache::Package **K = PList; K != PEnd; K++)
 684       {
 685          pkgCache::PkgIterator I(Cache,*K);
 686
 687          /* We attempt to install this and see if any breaks result,
 688             this takes care of some strange cases */
 689          if (Cache[I].CandidateVer != Cache[I].InstallVer &&
 690              I->CurrentVer != 0 && Cache[I].InstallVer != 0 &&
 691              (Flags[I->ID] & PreInstalled) != 0 &&
 692              (Flags[I->ID] & Protected) == 0 &&
 693              (Flags[I->ID] & ReInstateTried) == 0)
 694          {
 695             if (Debug == true)
 696                clog << " Try to Re-Instate " << I.Name() << endl;
 697             unsigned long OldBreaks = Cache.BrokenCount();
 698             pkgCache::Version *OldVer = Cache[I].InstallVer;
 699             Flags[I->ID] &= ReInstateTried;
 700
 701             Cache.MarkInstall(I,false);
 702             if (Cache[I].InstBroken() == true ||
 703                 OldBreaks < Cache.BrokenCount())
 704             {
 705                if (OldVer == 0)
 706                   Cache.MarkDelete(I);
 707                else
 708                   Cache.MarkKeep(I);
 709             }
 710             else
 711                if (Debug == true)
 712                   clog << "Re-Instated " << I.Name() << " (" << OldBreaks << " vs " << Cache.BrokenCount() << ')' << endl;
 713          }
 714
 715          if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false)
 716             continue;
 717
 718          // Isolate the problem dependency
 719          PackageKill KillList[100];
 720          PackageKill *LEnd = KillList;
 721          bool InOr = false;
 722          pkgCache::DepIterator Start;
 723          pkgCache::DepIterator End;
 724          for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList();
 725               D.end() == false || InOr == true;)
 726          {
 727             // Compute a single dependency element (glob or)
 728             if (InOr == false)
 729                D.GlobOr(Start,End);
 730             else
 731                Start++;
 732
 733             // We only worry about critical deps.
 734             if (End.IsCritical() != true)
 735                continue;
 736
 737             // Dep is ok
 738             if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
 739                continue;
 740
 741             InOr = Start != End;
 742
 743             if (Debug == true)
 744                clog << "Package " << I.Name() << " has broken dep on " << Start.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 = Start.AllTargets();
 750             if (*VList == 0 && (Flags[I->ID] & Protected) != Protected &&
 751                 Start->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[Start] & pkgDepCache::DepNow) == 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 " << Start.TargetPkg().Name() << endl;
 787                   }
 788                   else
 789                   {
 790                      if (BrokenFix == false || DoUpgrade(I) == false)
 791                      {
 792                         // Consider other options
 793                         if (InOr == false)
 794                         {
 795                            if (Debug == true)
 796                               clog << "  Removing " << I.Name() << " rather than change " << Start.TargetPkg().Name() << endl;
 797                            Cache.MarkDelete(I);
 798                            if (Counter > 1)
 799                               Scores[I->ID] = Scores[Pkg->ID];
 800                         }
 801                      }
 802                   }
 803
 804                   Change = true;
 805                   Done = true;
 806                   break;
 807                }
 808                else
 809                {
 810                   // Skip this if it is protected
 811                   if ((Flags[Pkg->ID] & Protected) != 0)
 812                      continue;
 813
 814                   LEnd->Pkg = Pkg;
 815                   LEnd->Dep = End;
 816                   LEnd++;
 817
 818                   if (Start->Type != pkgCache::Dep::Conflicts)
 819                      break;
 820                }
 821             }
 822
 823             // Hm, nothing can possibly satisify this dep. Nuke it.
 824             if (VList[0] == 0 && Start->Type != pkgCache::Dep::Conflicts &&
 825                 (Flags[I->ID] & Protected) != Protected && InOr == false)
 826             {
 827                Cache.MarkKeep(I);
 828                if (Cache[I].InstBroken() == false)
 829                {
 830                   if (Debug == true)
 831                      clog << "  Holding Back " << I.Name() << " because I can't find " << Start.TargetPkg().Name() << endl;
 832                }
 833                else
 834                {
 835                   if (Debug == true)
 836                      clog << "  Removing " << I.Name() << " because I can't find " << Start.TargetPkg().Name() << endl;
 837                   Cache.MarkDelete(I);
 838                }
 839
 840                Change = true;
 841                Done = true;
 842             }
 843
 844             // Try some more
 845             if (InOr == true)
 846                continue;
 847
 848             delete [] VList;
 849             if (Done == true)
 850                break;
 851          }
 852
 853          // Apply the kill list now
 854          if (Cache[I].InstallVer != 0)
 855             for (PackageKill *J = KillList; J != LEnd; J++)
 856          {
 857             Change = true;
 858             if ((Cache[J->Dep] & pkgDepCache::DepGNow) == 0)
 859             {
 860                if (J->Dep->Type == pkgCache::Dep::Conflicts)
 861                {
 862                   if (Debug == true)
 863                      clog << "  Fixing " << I.Name() << " via remove of " << J->Pkg.Name() << endl;
 864                   Cache.MarkDelete(J->Pkg);
 865                }
 866             }
 867             else
 868             {
 869                if (Debug == true)
 870                   clog << "  Fixing " << I.Name() << " via keep of " << J->Pkg.Name() << endl;
 871                Cache.MarkKeep(J->Pkg);
 872             }
 873
 874             if (Counter > 1)
 875                Scores[J->Pkg->ID] = Scores[I->ID];
 876          }
 877       }
 878    }
 879
 880    if (Debug == true)
 881       clog << "Done" << endl;
 882
 883    delete [] Scores;
 884    delete [] PList;
 885
 886    if (Cache.BrokenCount() != 0)
 887    {
 888       // See if this is the result of a hold
 889       pkgCache::PkgIterator I = Cache.PkgBegin();
 890       for (;I.end() != true; I++)
 891       {
 892          if (Cache[I].InstBroken() == false)
 893             continue;
 894          if ((Flags[I->ID] & Protected) != Protected)
 895             return _error->Error("Error, pkgProblemResolver::Resolve generated breaks, this may be caused by held packages.");
 896       }
 897       return _error->Error("Unable to correct problems, you have held broken packages.");
 898    }
 899
 900    return true;
 901 }
 902                                                                         /*}}}*/
 903 // ProblemResolver::ResolveByKeep - Resolve problems using keep         /*{{{*/
 904 // ---------------------------------------------------------------------
 905 /* This is the work horse of the soft upgrade routine. It is very gental
 906    in that it does not install or remove any packages. It is assumed that the
 907    system was non-broken previously. */
 908 bool pkgProblemResolver::ResolveByKeep()
 909 {
 910    unsigned long Size = Cache.HeaderP->PackageCount;
 911
 912    if (Debug == true)
 913       clog << "Entering ResolveByKeep" << endl;
 914
 915    MakeScores();
 916
 917    /* We have to order the packages so that the broken fixing pass
 918       operates from highest score to lowest. This prevents problems when
 919       high score packages cause the removal of lower score packages that
 920       would cause the removal of even lower score packages. */
 921    pkgCache::Package **PList = new pkgCache::Package *[Size];
 922    pkgCache::Package **PEnd = PList;
 923    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 924       *PEnd++ = I;
 925    This = this;
 926    qsort(PList,PEnd - PList,sizeof(*PList),&ScoreSort);
 927
 928    // Consider each broken package
 929    pkgCache::Package **LastStop = 0;
 930    for (pkgCache::Package **K = PList; K != PEnd; K++)
 931    {
 932       pkgCache::PkgIterator I(Cache,*K);
 933
 934       if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false)
 935          continue;
 936
 937       /* Keep the package. If this works then great, otherwise we have
 938          to be significantly more agressive and manipulate its dependencies */
 939       if ((Flags[I->ID] & Protected) == 0)
 940       {
 941          if (Debug == true)
 942             clog << "Keeping package " << I.Name() << endl;
 943          Cache.MarkKeep(I);
 944          if (Cache[I].InstBroken() == false)
 945          {
 946             K = PList;
 947             continue;
 948          }
 949       }
 950
 951       // Isolate the problem dependencies
 952       for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false;)
 953       {
 954          // Compute a single dependency element (glob or)
 955          pkgCache::DepIterator Start = D;
 956          pkgCache::DepIterator End = D;
 957          unsigned char State = 0;
 958          for (bool LastOR = true; D.end() == false && LastOR == true; D++)
 959          {
 960             State |= Cache[D];
 961             LastOR = (D->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or;
 962             if (LastOR == true)
 963                End = D;
 964          }
 965
 966          // We only worry about critical deps.
 967          if (End.IsCritical() != true)
 968             continue;
 969
 970          // Dep is ok
 971          if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
 972             continue;
 973
 974          // Hm, the group is broken.. I have no idea how to handle this
 975          if (Start != End)
 976          {
 977             clog << "Note, a broken or group was found in " << I.Name() << "." << endl;
 978             if ((Flags[I->ID] & Protected) == 0)
 979                Cache.MarkKeep(I);
 980             break;
 981          }
 982
 983          if (Debug == true)
 984             clog << "Package " << I.Name() << " has broken dep on " << End.TargetPkg().Name() << endl;
 985
 986          // Look at all the possible provides on this package
 987          pkgCache::Version **VList = End.AllTargets();
 988          for (pkgCache::Version **V = VList; *V != 0; V++)
 989          {
 990             pkgCache::VerIterator Ver(Cache,*V);
 991             pkgCache::PkgIterator Pkg = Ver.ParentPkg();
 992
 993             // It is not keepable
 994             if (Cache[Pkg].InstallVer == 0 ||
 995                 Pkg->CurrentVer == 0)
 996                continue;
 997
 998             if ((Flags[I->ID] & Protected) == 0)
 999             {
1000                if (Debug == true)
1001                   clog << "  Keeping Package " << Pkg.Name() << " due to dep" << endl;
1002                Cache.MarkKeep(Pkg);
1003             }
1004
1005             if (Cache[I].InstBroken() == false)
1006                break;
1007          }
1008
1009          if (Cache[I].InstBroken() == false)
1010             break;
1011       }
1012
1013       if (Cache[I].InstBroken() == true)
1014          continue;
1015
1016       // Restart again.
1017       if (K == LastStop)
1018          return _error->Error("Internal Error, pkgProblemResolver::ResolveByKeep is looping on package %s.",I.Name());
1019       LastStop = K;
1020       K = PList;
1021    }
1022
1023    return true;
1024 }
1025                                                                         /*}}}*/
1026 // ProblemResolver::InstallProtect - Install all protected packages     /*{{{*/
1027 // ---------------------------------------------------------------------
1028 /* This is used to make sure protected packages are installed */
1029 void pkgProblemResolver::InstallProtect()
1030 {
1031    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
1032    {
1033       if ((Flags[I->ID] & Protected) == Protected)
1034       {
1035          if ((Flags[I->ID] & ToRemove) == ToRemove)
1036             Cache.MarkDelete(I);
1037          else
1038             Cache.MarkInstall(I,false);
1039       }
1040    }
1041 }
1042                                                                         /*}}}*/