apt-pkg/algorithms.cc

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