apt-pkg/algorithms.cc

   1 // -*- mode: cpp; mode: fold -*-
   2 // Description                                                          /*{{{*/
   3 // $Id: algorithms.cc,v 1.24 1999/09/30 06:30:34 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          bool InOr = false;
 719          pkgCache::DepIterator Start;
 720          pkgCache::DepIterator End;
 721          for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList();
 722               D.end() == false || InOr == true;)
 723          {
 724             // Compute a single dependency element (glob or)
 725             if (InOr == false)
 726                D.GlobOr(Start,End);
 727             else
 728                Start++;
 729
 730             // We only worry about critical deps.
 731             if (End.IsCritical() != true)
 732                continue;
 733
 734             // Dep is ok
 735             if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
 736                continue;
 737
 738             InOr = Start != End;
 739
 740             // Hm, the group is broken.. I have no idea how to handle this
 741 /*          if (Start != End)
 742             {
 743                if (Debug == true)
 744                   clog << "Note, a broken or group was found in " << I.Name() << "." << endl;
 745                if ((Flags[I->ID] & Protected) != Protected)
 746                   Cache.MarkDelete(I);
 747                break;
 748             }*/
 749
 750             if (Debug == true)
 751                clog << "Package " << I.Name() << " has broken dep on " << Start.TargetPkg().Name() << endl;
 752
 753             /* Look across the version list. If there are no possible
 754                targets then we keep the package and bail. This is necessary
 755                if a package has a dep on another package that cant be found */
 756             pkgCache::Version **VList = Start.AllTargets();
 757             if (*VList == 0 && (Flags[I->ID] & Protected) != Protected &&
 758                 Start->Type != pkgCache::Dep::Conflicts &&
 759                 Cache[I].NowBroken() == false)
 760             {
 761                Change = true;
 762                Cache.MarkKeep(I);
 763                break;
 764             }
 765
 766             bool Done = false;
 767             for (pkgCache::Version **V = VList; *V != 0; V++)
 768             {
 769                pkgCache::VerIterator Ver(Cache,*V);
 770                pkgCache::PkgIterator Pkg = Ver.ParentPkg();
 771
 772                if (Debug == true)
 773                   clog << "  Considering " << Pkg.Name() << ' ' << (int)Scores[Pkg->ID] <<
 774                   " as a solution to " << I.Name() << ' ' << (int)Scores[I->ID] << endl;
 775                if (Scores[I->ID] <= Scores[Pkg->ID] ||
 776                    ((Cache[Start] & pkgDepCache::DepNow) == 0 &&
 777                     End->Type != pkgCache::Dep::Conflicts))
 778                {
 779                   // Try a little harder to fix protected packages..
 780                   if ((Flags[I->ID] & Protected) == Protected)
 781                   {
 782                      if (DoUpgrade(Pkg) == true)
 783                         Scores[Pkg->ID] = Scores[I->ID];
 784                      continue;
 785                   }
 786
 787                   /* See if a keep will do, unless the package is protected,
 788                      then installing it will be necessary */
 789                   Cache.MarkKeep(I);
 790                   if (Cache[I].InstBroken() == false)
 791                   {
 792                      if (Debug == true)
 793                         clog << "  Holding Back " << I.Name() << " rather than change " << Start.TargetPkg().Name() << endl;
 794                   }
 795                   else
 796                   {
 797                      if (BrokenFix == false || DoUpgrade(I) == false)
 798                      {
 799                         // Consider other options
 800                         if (InOr == false)
 801                         {
 802                            if (Debug == true)
 803                               clog << "  Removing " << I.Name() << " rather than change " << Start.TargetPkg().Name() << endl;
 804                            Cache.MarkDelete(I);
 805                            if (Counter > 1)
 806                               Scores[I->ID] = Scores[Pkg->ID];
 807                         }
 808                      }
 809                   }
 810
 811                   Change = true;
 812                   Done = true;
 813                   break;
 814                }
 815                else
 816                {
 817                   // Skip this if it is protected
 818                   if ((Flags[Pkg->ID] & Protected) != 0)
 819                      continue;
 820
 821                   LEnd->Pkg = Pkg;
 822                   LEnd->Dep = End;
 823                   LEnd++;
 824
 825                   if (Start->Type != pkgCache::Dep::Conflicts)
 826                      break;
 827                }
 828             }
 829
 830             // Hm, nothing can possibly satisify this dep. Nuke it.
 831             if (VList[0] == 0 && Start->Type != pkgCache::Dep::Conflicts &&
 832                 (Flags[I->ID] & Protected) != Protected && InOr == false)
 833             {
 834                Cache.MarkKeep(I);
 835                if (Cache[I].InstBroken() == false)
 836                {
 837                   if (Debug == true)
 838                      clog << "  Holding Back " << I.Name() << " because I can't find " << Start.TargetPkg().Name() << endl;
 839                }
 840                else
 841                {
 842                   if (Debug == true)
 843                      clog << "  Removing " << I.Name() << " because I can't find " << Start.TargetPkg().Name() << endl;
 844                   Cache.MarkDelete(I);
 845                }
 846
 847                Change = true;
 848                Done = true;
 849             }
 850
 851             // Try some more
 852             if (InOr == true)
 853                continue;
 854
 855             delete [] VList;
 856             if (Done == true)
 857                break;
 858          }
 859
 860          // Apply the kill list now
 861          if (Cache[I].InstallVer != 0)
 862             for (PackageKill *J = KillList; J != LEnd; J++)
 863          {
 864             Change = true;
 865             if ((Cache[J->Dep] & pkgDepCache::DepGNow) == 0)
 866             {
 867                if (J->Dep->Type == pkgCache::Dep::Conflicts)
 868                {
 869                   if (Debug == true)
 870                      clog << "  Fixing " << I.Name() << " via remove of " << J->Pkg.Name() << endl;
 871                   Cache.MarkDelete(J->Pkg);
 872                }
 873             }
 874             else
 875             {
 876                if (Debug == true)
 877                   clog << "  Fixing " << I.Name() << " via keep of " << J->Pkg.Name() << endl;
 878                Cache.MarkKeep(J->Pkg);
 879             }
 880
 881             if (Counter > 1)
 882                Scores[J->Pkg->ID] = Scores[I->ID];
 883          }
 884       }
 885    }
 886
 887    if (Debug == true)
 888       clog << "Done" << endl;
 889
 890    delete [] Scores;
 891    delete [] PList;
 892
 893    if (Cache.BrokenCount() != 0)
 894    {
 895       // See if this is the result of a hold
 896       pkgCache::PkgIterator I = Cache.PkgBegin();
 897       for (;I.end() != true; I++)
 898       {
 899          if (Cache[I].InstBroken() == false)
 900             continue;
 901          if ((Flags[I->ID] & Protected) != Protected)
 902             return _error->Error("Error, pkgProblemResolver::Resolve generated breaks, this may be caused by held packages.");
 903       }
 904       return _error->Error("Unable to correct problems, you have held broken packages.");
 905    }
 906
 907    return true;
 908 }
 909                                                                         /*}}}*/
 910 // ProblemResolver::ResolveByKeep - Resolve problems using keep         /*{{{*/
 911 // ---------------------------------------------------------------------
 912 /* This is the work horse of the soft upgrade routine. It is very gental
 913    in that it does not install or remove any packages. It is assumed that the
 914    system was non-broken previously. */
 915 bool pkgProblemResolver::ResolveByKeep()
 916 {
 917    unsigned long Size = Cache.HeaderP->PackageCount;
 918
 919    if (Debug == true)
 920       clog << "Entering ResolveByKeep" << endl;
 921
 922    MakeScores();
 923
 924    /* We have to order the packages so that the broken fixing pass
 925       operates from highest score to lowest. This prevents problems when
 926       high score packages cause the removal of lower score packages that
 927       would cause the removal of even lower score packages. */
 928    pkgCache::Package **PList = new pkgCache::Package *[Size];
 929    pkgCache::Package **PEnd = PList;
 930    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
 931       *PEnd++ = I;
 932    This = this;
 933    qsort(PList,PEnd - PList,sizeof(*PList),&ScoreSort);
 934
 935    // Consider each broken package
 936    pkgCache::Package **LastStop = 0;
 937    for (pkgCache::Package **K = PList; K != PEnd; K++)
 938    {
 939       pkgCache::PkgIterator I(Cache,*K);
 940
 941       if (Cache[I].InstallVer == 0 || Cache[I].InstBroken() == false)
 942          continue;
 943
 944       /* Keep the package. If this works then great, otherwise we have
 945          to be significantly more agressive and manipulate its dependencies */
 946       if ((Flags[I->ID] & Protected) == 0)
 947       {
 948          if (Debug == true)
 949             clog << "Keeping package " << I.Name() << endl;
 950          Cache.MarkKeep(I);
 951          if (Cache[I].InstBroken() == false)
 952          {
 953             K = PList;
 954             continue;
 955          }
 956       }
 957
 958       // Isolate the problem dependencies
 959       for (pkgCache::DepIterator D = Cache[I].InstVerIter(Cache).DependsList(); D.end() == false;)
 960       {
 961          // Compute a single dependency element (glob or)
 962          pkgCache::DepIterator Start = D;
 963          pkgCache::DepIterator End = D;
 964          unsigned char State = 0;
 965          for (bool LastOR = true; D.end() == false && LastOR == true; D++)
 966          {
 967             State |= Cache[D];
 968             LastOR = (D->CompareOp & pkgCache::Dep::Or) == pkgCache::Dep::Or;
 969             if (LastOR == true)
 970                End = D;
 971          }
 972
 973          // We only worry about critical deps.
 974          if (End.IsCritical() != true)
 975             continue;
 976
 977          // Dep is ok
 978          if ((Cache[End] & pkgDepCache::DepGInstall) == pkgDepCache::DepGInstall)
 979             continue;
 980
 981          // Hm, the group is broken.. I have no idea how to handle this
 982          if (Start != End)
 983          {
 984             clog << "Note, a broken or group was found in " << I.Name() << "." << endl;
 985             if ((Flags[I->ID] & Protected) == 0)
 986                Cache.MarkKeep(I);
 987             break;
 988          }
 989
 990          if (Debug == true)
 991             clog << "Package " << I.Name() << " has broken dep on " << End.TargetPkg().Name() << endl;
 992
 993          // Look at all the possible provides on this package
 994          pkgCache::Version **VList = End.AllTargets();
 995          for (pkgCache::Version **V = VList; *V != 0; V++)
 996          {
 997             pkgCache::VerIterator Ver(Cache,*V);
 998             pkgCache::PkgIterator Pkg = Ver.ParentPkg();
 999
1000             // It is not keepable
1001             if (Cache[Pkg].InstallVer == 0 ||
1002                 Pkg->CurrentVer == 0)
1003                continue;
1004
1005             if ((Flags[I->ID] & Protected) == 0)
1006             {
1007                if (Debug == true)
1008                   clog << "  Keeping Package " << Pkg.Name() << " due to dep" << endl;
1009                Cache.MarkKeep(Pkg);
1010             }
1011
1012             if (Cache[I].InstBroken() == false)
1013                break;
1014          }
1015
1016          if (Cache[I].InstBroken() == false)
1017             break;
1018       }
1019
1020       if (Cache[I].InstBroken() == true)
1021          continue;
1022
1023       // Restart again.
1024       if (K == LastStop)
1025          return _error->Error("Internal Error, pkgProblemResolver::ResolveByKeep is looping on package %s.",I.Name());
1026       LastStop = K;
1027       K = PList;
1028    }
1029
1030    return true;
1031 }
1032                                                                         /*}}}*/
1033 // ProblemResolver::InstallProtect - Install all protected packages     /*{{{*/
1034 // ---------------------------------------------------------------------
1035 /* This is used to make sure protected packages are installed */
1036 void pkgProblemResolver::InstallProtect()
1037 {
1038    for (pkgCache::PkgIterator I = Cache.PkgBegin(); I.end() == false; I++)
1039    {
1040       if ((Flags[I->ID] & Protected) == Protected)
1041       {
1042          if ((Flags[I->ID] & ToRemove) == ToRemove)
1043             Cache.MarkDelete(I);
1044          else
1045             Cache.MarkInstall(I,false);
1046       }
1047    }
1048 }
1049                                                                         /*}}}*/