apt-pkg/algorithms.cc

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