apt-pkg/algorithms.cc

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