apt-pkg/algorithms.cc

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