apt-pkg/algorithms.cc

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