apt-pkg/algorithms.cc

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