apt-pkg/depcache.cc

   1 // -*- mode: cpp; mode: fold -*-
   2 // Description                                                          /*{{{*/
   3 // $Id: depcache.cc,v 1.25 2001/05/27 05:36:04 jgg Exp $
   4 /* ######################################################################
   5
   6    Dependency Cache - Caches Dependency information.
   7
   8    ##################################################################### */
   9                                                                         /*}}}*/
  10 // Include Files                                                        /*{{{*/
  11 #ifdef __GNUG__
  12 #pragma implementation "apt-pkg/depcache.h"
  13 #endif
  14 #include <apt-pkg/depcache.h>
  15 #include <apt-pkg/version.h>
  16 #include <apt-pkg/error.h>
  17 #include <apt-pkg/sptr.h>
  18 #include <apt-pkg/algorithms.h>
  19
  20 #include <apt-pkg/fileutl.h>
  21 #include <apt-pkg/configuration.h>
  22 #include <apt-pkg/pkgsystem.h>
  23 #include <apt-pkg/tagfile.h>
  24
  25 #include <iostream>
  26 #include <sstream>
  27 #include <set>
  28
  29 #include <apti18n.h>
  30
  31 pkgDepCache::ActionGroup::ActionGroup(pkgDepCache &cache) :
  32   cache(cache), released(false)
  33 {
  34   ++cache.group_level;
  35 }
  36
  37 void pkgDepCache::ActionGroup::release()
  38 {
  39   if(!released)
  40     {
  41       if(cache.group_level == 0)
  42         std::cerr << "W: Unbalanced action groups, expect badness" << std::endl;
  43       else
  44         {
  45           --cache.group_level;
  46
  47           if(cache.group_level == 0)
  48             cache.MarkAndSweep();
  49         }
  50
  51       released = false;
  52     }
  53 }
  54
  55 pkgDepCache::ActionGroup::~ActionGroup()
  56 {
  57   release();
  58 }
  59
  60 // DepCache::pkgDepCache - Constructors                                 /*{{{*/
  61 // ---------------------------------------------------------------------
  62 /* */
  63 pkgDepCache::pkgDepCache(pkgCache *pCache,Policy *Plcy) :
  64   group_level(0), Cache(pCache), PkgState(0), DepState(0)
  65 {
  66    delLocalPolicy = 0;
  67    LocalPolicy = Plcy;
  68    if (LocalPolicy == 0)
  69       delLocalPolicy = LocalPolicy = new Policy;
  70 }
  71                                                                         /*}}}*/
  72 // DepCache::~pkgDepCache - Destructor                                  /*{{{*/
  73 // ---------------------------------------------------------------------
  74 /* */
  75 pkgDepCache::~pkgDepCache()
  76 {
  77    delete [] PkgState;
  78    delete [] DepState;
  79    delete delLocalPolicy;
  80 }
  81                                                                         /*}}}*/
  82 // DepCache::Init - Generate the initial extra structures.              /*{{{*/
  83 // ---------------------------------------------------------------------
  84 /* This allocats the extension buffers and initializes them. */
  85 bool pkgDepCache::Init(OpProgress *Prog)
  86 {
  87    // Suppress mark updates during this operation (just in case) and
  88    // run a mark operation when Init terminates.
  89    ActionGroup actions(*this);
  90
  91    delete [] PkgState;
  92    delete [] DepState;
  93    PkgState = new StateCache[Head().PackageCount];
  94    DepState = new unsigned char[Head().DependsCount];
  95    memset(PkgState,0,sizeof(*PkgState)*Head().PackageCount);
  96    memset(DepState,0,sizeof(*DepState)*Head().DependsCount);
  97
  98    if (Prog != 0)
  99    {
 100       Prog->OverallProgress(0,2*Head().PackageCount,Head().PackageCount,
 101                             _("Building dependency tree"));
 102       Prog->SubProgress(Head().PackageCount,_("Candidate versions"));
 103    }
 104
 105    /* Set the current state of everything. In this state all of the
 106       packages are kept exactly as is. See AllUpgrade */
 107    int Done = 0;
 108    for (PkgIterator I = PkgBegin(); I.end() != true; I++,Done++)
 109    {
 110       if (Prog != 0)
 111          Prog->Progress(Done);
 112
 113       // Find the proper cache slot
 114       StateCache &State = PkgState[I->ID];
 115       State.iFlags = 0;
 116
 117       // Figure out the install version
 118       State.CandidateVer = GetCandidateVer(I);
 119       State.InstallVer = I.CurrentVer();
 120       State.Mode = ModeKeep;
 121
 122       State.Update(I,*this);
 123    }
 124
 125    if (Prog != 0)
 126    {
 127
 128       Prog->OverallProgress(Head().PackageCount,2*Head().PackageCount,
 129                             Head().PackageCount,
 130                             _("Building dependency tree"));
 131       Prog->SubProgress(Head().PackageCount,_("Dependency generation"));
 132    }
 133
 134    Update(Prog);
 135
 136    if(Prog != 0)
 137       Prog->Done();
 138
 139    return true;
 140 }
 141                                                                         /*}}}*/
 142
 143 bool pkgDepCache::readStateFile(OpProgress *Prog)
 144 {
 145    FileFd state_file;
 146    string state = _config->FindDir("Dir::State") + "extended_states";
 147    if(FileExists(state)) {
 148       state_file.Open(state, FileFd::ReadOnly);
 149       int file_size = state_file.Size();
 150       if(Prog != NULL)
 151          Prog->OverallProgress(0, file_size, 1,
 152                                _("Reading state information"));
 153
 154       pkgTagFile tagfile(&state_file);
 155       pkgTagSection section;
 156       int amt=0;
 157       while(tagfile.Step(section)) {
 158          string pkgname = section.FindS("Package");
 159          pkgCache::PkgIterator pkg=Cache->FindPkg(pkgname);
 160          // Silently ignore unknown packages and packages with no actual
 161          // version.
 162          if(!pkg.end() && !pkg.VersionList().end()) {
 163             short reason = section.FindI("Auto-Installed", 0);
 164             if(reason > 0)
 165                PkgState[pkg->ID].Flags  |= Flag::Auto;
 166             if(_config->FindB("Debug::pkgAutoRemove",false))
 167                std::cout << "Auto-Installed : " << pkgname << std::endl;
 168             amt+=section.size();
 169             if(Prog != NULL)
 170                Prog->OverallProgress(amt, file_size, 1,
 171                                      _("Reading state information"));
 172          }
 173          if(Prog != NULL)
 174             Prog->OverallProgress(file_size, file_size, 1,
 175                                   _("Reading state information"));
 176       }
 177    }
 178
 179    return true;
 180 }
 181
 182 bool pkgDepCache::writeStateFile(OpProgress *prog, bool InstalledOnly)
 183 {
 184    if(_config->FindB("Debug::pkgAutoRemove",false))
 185       std::clog << "pkgDepCache::writeStateFile()" << std::endl;
 186
 187    FileFd StateFile;
 188    string state = _config->FindDir("Dir::State") + "extended_states";
 189
 190    // if it does not exist, create a empty one
 191    if(!FileExists(state))
 192    {
 193       StateFile.Open(state, FileFd::WriteEmpty);
 194       StateFile.Close();
 195    }
 196
 197    // open it
 198    if(!StateFile.Open(state, FileFd::ReadOnly))
 199       return _error->Error(_("Failed to open StateFile %s"),
 200                            state.c_str());
 201
 202    FILE *OutFile;
 203    string outfile = state + ".tmp";
 204    if((OutFile = fopen(outfile.c_str(),"w")) == NULL)
 205       return _error->Error(_("Failed to write temporary StateFile %s"),
 206                            outfile.c_str());
 207
 208    // first merge with the existing sections
 209    pkgTagFile tagfile(&StateFile);
 210    pkgTagSection section;
 211    std::set<string> pkgs_seen;
 212    const char *nullreorderlist[] = {0};
 213    while(tagfile.Step(section)) {
 214          string pkgname = section.FindS("Package");
 215          // Silently ignore unknown packages and packages with no actual
 216          // version.
 217          pkgCache::PkgIterator pkg=Cache->FindPkg(pkgname);
 218          if(pkg.end() || pkg.VersionList().end())
 219             continue;
 220          bool oldAuto = section.FindI("Auto-Installed");
 221          bool newAuto = (PkgState[pkg->ID].Flags & Flag::Auto);
 222          if(_config->FindB("Debug::pkgAutoRemove",false))
 223             std::clog << "Update exisiting AutoInstall info: "
 224                       << pkg.Name() << std::endl;
 225          TFRewriteData rewrite[2];
 226          rewrite[0].Tag = "Auto-Installed";
 227          rewrite[0].Rewrite = newAuto ? "1" : "0";
 228          rewrite[0].NewTag = 0;
 229          rewrite[1].Tag = 0;
 230          TFRewrite(OutFile, section, nullreorderlist, rewrite);
 231          fprintf(OutFile,"\n");
 232          pkgs_seen.insert(pkgname);
 233    }
 234
 235    // then write the ones we have not seen yet
 236    std::ostringstream ostr;
 237    for(pkgCache::PkgIterator pkg=Cache->PkgBegin(); !pkg.end(); pkg++) {
 238       if(PkgState[pkg->ID].Flags & Flag::Auto) {
 239          if (pkgs_seen.find(pkg.Name()) != pkgs_seen.end()) {
 240             if(_config->FindB("Debug::pkgAutoRemove",false))
 241                std::clog << "Skipping already written " << pkg.Name() << std::endl;
 242             continue;
 243          }
 244          // skip not installed ones if requested
 245          if(InstalledOnly && pkg->CurrentVer == 0)
 246             continue;
 247          if(_config->FindB("Debug::pkgAutoRemove",false))
 248             std::clog << "Writing new AutoInstall: "
 249                       << pkg.Name() << std::endl;
 250          ostr.str(string(""));
 251          ostr << "Package: " << pkg.Name()
 252               << "\nAuto-Installed: 1\n\n";
 253          fprintf(OutFile,ostr.str().c_str());
 254          fprintf(OutFile,"\n");
 255       }
 256    }
 257    fclose(OutFile);
 258
 259    // move the outfile over the real file
 260    rename(outfile.c_str(), state.c_str());
 261
 262    return true;
 263 }
 264
 265 // DepCache::CheckDep - Checks a single dependency                      /*{{{*/
 266 // ---------------------------------------------------------------------
 267 /* This first checks the dependency against the main target package and
 268    then walks along the package provides list and checks if each provides
 269    will be installed then checks the provides against the dep. Res will be
 270    set to the package which was used to satisfy the dep. */
 271 bool pkgDepCache::CheckDep(DepIterator Dep,int Type,PkgIterator &Res)
 272 {
 273    Res = Dep.TargetPkg();
 274
 275    /* Check simple depends. A depends -should- never self match but
 276       we allow it anyhow because dpkg does. Technically it is a packaging
 277       bug. Conflicts may never self match */
 278    if (Dep.TargetPkg() != Dep.ParentPkg() ||
 279        (Dep->Type != Dep::Conflicts && Dep->Type != Dep::DpkgBreaks && Dep->Type != Dep::Obsoletes))
 280    {
 281       PkgIterator Pkg = Dep.TargetPkg();
 282       // Check the base package
 283       if (Type == NowVersion && Pkg->CurrentVer != 0)
 284          if (VS().CheckDep(Pkg.CurrentVer().VerStr(),Dep->CompareOp,
 285                                  Dep.TargetVer()) == true)
 286             return true;
 287
 288       if (Type == InstallVersion && PkgState[Pkg->ID].InstallVer != 0)
 289          if (VS().CheckDep(PkgState[Pkg->ID].InstVerIter(*this).VerStr(),
 290                                  Dep->CompareOp,Dep.TargetVer()) == true)
 291             return true;
 292
 293       if (Type == CandidateVersion && PkgState[Pkg->ID].CandidateVer != 0)
 294          if (VS().CheckDep(PkgState[Pkg->ID].CandidateVerIter(*this).VerStr(),
 295                                  Dep->CompareOp,Dep.TargetVer()) == true)
 296             return true;
 297    }
 298
 299    if (Dep->Type == Dep::Obsoletes)
 300       return false;
 301
 302    // Check the providing packages
 303    PrvIterator P = Dep.TargetPkg().ProvidesList();
 304    PkgIterator Pkg = Dep.ParentPkg();
 305    for (; P.end() != true; P++)
 306    {
 307       /* Provides may never be applied against the same package if it is
 308          a conflicts. See the comment above. */
 309       if (P.OwnerPkg() == Pkg &&
 310           (Dep->Type == Dep::Conflicts || Dep->Type == Dep::DpkgBreaks))
 311          continue;
 312
 313       // Check if the provides is a hit
 314       if (Type == NowVersion)
 315       {
 316          if (P.OwnerPkg().CurrentVer() != P.OwnerVer())
 317             continue;
 318       }
 319
 320       if (Type == InstallVersion)
 321       {
 322          StateCache &State = PkgState[P.OwnerPkg()->ID];
 323          if (State.InstallVer != (Version *)P.OwnerVer())
 324             continue;
 325       }
 326
 327       if (Type == CandidateVersion)
 328       {
 329          StateCache &State = PkgState[P.OwnerPkg()->ID];
 330          if (State.CandidateVer != (Version *)P.OwnerVer())
 331             continue;
 332       }
 333
 334       // Compare the versions.
 335       if (VS().CheckDep(P.ProvideVersion(),Dep->CompareOp,Dep.TargetVer()) == true)
 336       {
 337          Res = P.OwnerPkg();
 338          return true;
 339       }
 340    }
 341
 342    return false;
 343 }
 344                                                                         /*}}}*/
 345 // DepCache::AddSizes - Add the packages sizes to the counters          /*{{{*/
 346 // ---------------------------------------------------------------------
 347 /* Call with Mult = -1 to preform the inverse opration */
 348 void pkgDepCache::AddSizes(const PkgIterator &Pkg,signed long Mult)
 349 {
 350    StateCache &P = PkgState[Pkg->ID];
 351
 352    if (Pkg->VersionList == 0)
 353       return;
 354
 355    if (Pkg.State() == pkgCache::PkgIterator::NeedsConfigure &&
 356        P.Keep() == true)
 357       return;
 358
 359    // Compute the size data
 360    if (P.NewInstall() == true)
 361    {
 362       iUsrSize += (signed)(Mult*P.InstVerIter(*this)->InstalledSize);
 363       iDownloadSize += (signed)(Mult*P.InstVerIter(*this)->Size);
 364       return;
 365    }
 366
 367    // Upgrading
 368    if (Pkg->CurrentVer != 0 &&
 369        (P.InstallVer != (Version *)Pkg.CurrentVer() ||
 370         (P.iFlags & ReInstall) == ReInstall) && P.InstallVer != 0)
 371    {
 372       iUsrSize += (signed)(Mult*((signed)P.InstVerIter(*this)->InstalledSize -
 373                         (signed)Pkg.CurrentVer()->InstalledSize));
 374       iDownloadSize += (signed)(Mult*P.InstVerIter(*this)->Size);
 375       return;
 376    }
 377
 378    // Reinstall
 379    if (Pkg.State() == pkgCache::PkgIterator::NeedsUnpack &&
 380        P.Delete() == false)
 381    {
 382       iDownloadSize += (signed)(Mult*P.InstVerIter(*this)->Size);
 383       return;
 384    }
 385
 386    // Removing
 387    if (Pkg->CurrentVer != 0 && P.InstallVer == 0)
 388    {
 389       iUsrSize -= (signed)(Mult*Pkg.CurrentVer()->InstalledSize);
 390       return;
 391    }
 392 }
 393                                                                         /*}}}*/
 394 // DepCache::AddStates - Add the package to the state counter           /*{{{*/
 395 // ---------------------------------------------------------------------
 396 /* This routine is tricky to use, you must make sure that it is never
 397    called twice for the same package. This means the Remove/Add section
 398    should be as short as possible and not encompass any code that will
 399    calld Remove/Add itself. Remember, dependencies can be circular so
 400    while processing a dep for Pkg it is possible that Add/Remove
 401    will be called on Pkg */
 402 void pkgDepCache::AddStates(const PkgIterator &Pkg,int Add)
 403 {
 404    StateCache &State = PkgState[Pkg->ID];
 405
 406    // The Package is broken (either minimal dep or policy dep)
 407    if ((State.DepState & DepInstMin) != DepInstMin)
 408       iBrokenCount += Add;
 409    if ((State.DepState & DepInstPolicy) != DepInstPolicy)
 410       iPolicyBrokenCount += Add;
 411
 412    // Bad state
 413    if (Pkg.State() != PkgIterator::NeedsNothing)
 414       iBadCount += Add;
 415
 416    // Not installed
 417    if (Pkg->CurrentVer == 0)
 418    {
 419       if (State.Mode == ModeDelete &&
 420           (State.iFlags | Purge) == Purge && Pkg.Purge() == false)
 421          iDelCount += Add;
 422
 423       if (State.Mode == ModeInstall)
 424          iInstCount += Add;
 425       return;
 426    }
 427
 428    // Installed, no upgrade
 429    if (State.Status == 0)
 430    {
 431       if (State.Mode == ModeDelete)
 432          iDelCount += Add;
 433       else
 434          if ((State.iFlags & ReInstall) == ReInstall)
 435             iInstCount += Add;
 436
 437       return;
 438    }
 439
 440    // Alll 3 are possible
 441    if (State.Mode == ModeDelete)
 442       iDelCount += Add;
 443    if (State.Mode == ModeKeep)
 444       iKeepCount += Add;
 445    if (State.Mode == ModeInstall)
 446       iInstCount += Add;
 447 }
 448                                                                         /*}}}*/
 449 // DepCache::BuildGroupOrs - Generate the Or group dep data             /*{{{*/
 450 // ---------------------------------------------------------------------
 451 /* The or group results are stored in the last item of the or group. This
 452    allows easy detection of the state of a whole or'd group. */
 453 void pkgDepCache::BuildGroupOrs(VerIterator const &V)
 454 {
 455    unsigned char Group = 0;
 456
 457    for (DepIterator D = V.DependsList(); D.end() != true; D++)
 458    {
 459       // Build the dependency state.
 460       unsigned char &State = DepState[D->ID];
 461
 462       /* Invert for Conflicts. We have to do this twice to get the
 463          right sense for a conflicts group */
 464       if (D->Type == Dep::Conflicts ||
 465           D->Type == Dep::DpkgBreaks ||
 466           D->Type == Dep::Obsoletes)
 467          State = ~State;
 468
 469       // Add to the group if we are within an or..
 470       State &= 0x7;
 471       Group |= State;
 472       State |= Group << 3;
 473       if ((D->CompareOp & Dep::Or) != Dep::Or)
 474          Group = 0;
 475
 476       // Invert for Conflicts
 477       if (D->Type == Dep::Conflicts ||
 478           D->Type == Dep::DpkgBreaks ||
 479           D->Type == Dep::Obsoletes)
 480          State = ~State;
 481    }
 482 }
 483                                                                         /*}}}*/
 484 // DepCache::VersionState - Perform a pass over a dependency list       /*{{{*/
 485 // ---------------------------------------------------------------------
 486 /* This is used to run over a dependency list and determine the dep
 487    state of the list, filtering it through both a Min check and a Policy
 488    check. The return result will have SetMin/SetPolicy low if a check
 489    fails. It uses the DepState cache for it's computations. */
 490 unsigned char pkgDepCache::VersionState(DepIterator D,unsigned char Check,
 491                                        unsigned char SetMin,
 492                                        unsigned char SetPolicy)
 493 {
 494    unsigned char Dep = 0xFF;
 495
 496    while (D.end() != true)
 497    {
 498       // Compute a single dependency element (glob or)
 499       DepIterator Start = D;
 500       unsigned char State = 0;
 501       for (bool LastOR = true; D.end() == false && LastOR == true; D++)
 502       {
 503          State |= DepState[D->ID];
 504          LastOR = (D->CompareOp & Dep::Or) == Dep::Or;
 505       }
 506
 507       // Minimum deps that must be satisfied to have a working package
 508       if (Start.IsCritical() == true)
 509          if ((State & Check) != Check)
 510             Dep &= ~SetMin;
 511
 512       // Policy deps that must be satisfied to install the package
 513       if (IsImportantDep(Start) == true &&
 514           (State & Check) != Check)
 515          Dep &= ~SetPolicy;
 516    }
 517
 518    return Dep;
 519 }
 520                                                                         /*}}}*/
 521 // DepCache::DependencyState - Compute the 3 results for a dep          /*{{{*/
 522 // ---------------------------------------------------------------------
 523 /* This is the main dependency computation bit. It computes the 3 main
 524    results for a dependencys, Now, Install and Candidate. Callers must
 525    invert the result if dealing with conflicts. */
 526 unsigned char pkgDepCache::DependencyState(DepIterator &D)
 527 {
 528    unsigned char State = 0;
 529
 530    if (CheckDep(D,NowVersion) == true)
 531       State |= DepNow;
 532    if (CheckDep(D,InstallVersion) == true)
 533       State |= DepInstall;
 534    if (CheckDep(D,CandidateVersion) == true)
 535       State |= DepCVer;
 536
 537    return State;
 538 }
 539                                                                         /*}}}*/
 540 // DepCache::UpdateVerState - Compute the Dep member of the state       /*{{{*/
 541 // ---------------------------------------------------------------------
 542 /* This determines the combined dependency representation of a package
 543    for its two states now and install. This is done by using the pre-generated
 544    dependency information. */
 545 void pkgDepCache::UpdateVerState(PkgIterator Pkg)
 546 {
 547    // Empty deps are always true
 548    StateCache &State = PkgState[Pkg->ID];
 549    State.DepState = 0xFF;
 550
 551    // Check the Current state
 552    if (Pkg->CurrentVer != 0)
 553    {
 554       DepIterator D = Pkg.CurrentVer().DependsList();
 555       State.DepState &= VersionState(D,DepNow,DepNowMin,DepNowPolicy);
 556    }
 557
 558    /* Check the candidate state. We do not compare against the whole as
 559       a candidate state but check the candidate version against the
 560       install states */
 561    if (State.CandidateVer != 0)
 562    {
 563       DepIterator D = State.CandidateVerIter(*this).DependsList();
 564       State.DepState &= VersionState(D,DepInstall,DepCandMin,DepCandPolicy);
 565    }
 566
 567    // Check target state which can only be current or installed
 568    if (State.InstallVer != 0)
 569    {
 570       DepIterator D = State.InstVerIter(*this).DependsList();
 571       State.DepState &= VersionState(D,DepInstall,DepInstMin,DepInstPolicy);
 572    }
 573 }
 574                                                                         /*}}}*/
 575 // DepCache::Update - Figure out all the state information              /*{{{*/
 576 // ---------------------------------------------------------------------
 577 /* This will figure out the state of all the packages and all the
 578    dependencies based on the current policy. */
 579 void pkgDepCache::Update(OpProgress *Prog)
 580 {
 581    iUsrSize = 0;
 582    iDownloadSize = 0;
 583    iDelCount = 0;
 584    iInstCount = 0;
 585    iKeepCount = 0;
 586    iBrokenCount = 0;
 587    iBadCount = 0;
 588
 589    // Perform the depends pass
 590    int Done = 0;
 591    for (PkgIterator I = PkgBegin(); I.end() != true; I++,Done++)
 592    {
 593       if (Prog != 0 && Done%20 == 0)
 594          Prog->Progress(Done);
 595       for (VerIterator V = I.VersionList(); V.end() != true; V++)
 596       {
 597          unsigned char Group = 0;
 598
 599          for (DepIterator D = V.DependsList(); D.end() != true; D++)
 600          {
 601             // Build the dependency state.
 602             unsigned char &State = DepState[D->ID];
 603             State = DependencyState(D);
 604
 605             // Add to the group if we are within an or..
 606             Group |= State;
 607             State |= Group << 3;
 608             if ((D->CompareOp & Dep::Or) != Dep::Or)
 609                Group = 0;
 610
 611             // Invert for Conflicts
 612             if (D->Type == Dep::Conflicts ||
 613                 D->Type == Dep::DpkgBreaks ||
 614                 D->Type == Dep::Obsoletes)
 615                State = ~State;
 616          }
 617       }
 618
 619       // Compute the pacakge dependency state and size additions
 620       AddSizes(I);
 621       UpdateVerState(I);
 622       AddStates(I);
 623    }
 624
 625    if (Prog != 0)
 626       Prog->Progress(Done);
 627
 628    readStateFile(Prog);
 629 }
 630                                                                         /*}}}*/
 631 // DepCache::Update - Update the deps list of a package                 /*{{{*/
 632 // ---------------------------------------------------------------------
 633 /* This is a helper for update that only does the dep portion of the scan.
 634    It is mainly meant to scan reverse dependencies. */
 635 void pkgDepCache::Update(DepIterator D)
 636 {
 637    // Update the reverse deps
 638    for (;D.end() != true; D++)
 639    {
 640       unsigned char &State = DepState[D->ID];
 641       State = DependencyState(D);
 642
 643       // Invert for Conflicts
 644       if (D->Type == Dep::Conflicts ||
 645           D->Type == Dep::DpkgBreaks ||
 646           D->Type == Dep::Obsoletes)
 647          State = ~State;
 648
 649       RemoveStates(D.ParentPkg());
 650       BuildGroupOrs(D.ParentVer());
 651       UpdateVerState(D.ParentPkg());
 652       AddStates(D.ParentPkg());
 653    }
 654 }
 655                                                                         /*}}}*/
 656 // DepCache::Update - Update the related deps of a package              /*{{{*/
 657 // ---------------------------------------------------------------------
 658 /* This is called whenever the state of a package changes. It updates
 659    all cached dependencies related to this package. */
 660 void pkgDepCache::Update(PkgIterator const &Pkg)
 661 {
 662    // Recompute the dep of the package
 663    RemoveStates(Pkg);
 664    UpdateVerState(Pkg);
 665    AddStates(Pkg);
 666
 667    // Update the reverse deps
 668    Update(Pkg.RevDependsList());
 669
 670    // Update the provides map for the current ver
 671    if (Pkg->CurrentVer != 0)
 672       for (PrvIterator P = Pkg.CurrentVer().ProvidesList();
 673            P.end() != true; P++)
 674          Update(P.ParentPkg().RevDependsList());
 675
 676    // Update the provides map for the candidate ver
 677    if (PkgState[Pkg->ID].CandidateVer != 0)
 678       for (PrvIterator P = PkgState[Pkg->ID].CandidateVerIter(*this).ProvidesList();
 679            P.end() != true; P++)
 680          Update(P.ParentPkg().RevDependsList());
 681 }
 682
 683                                                                         /*}}}*/
 684
 685 // DepCache::MarkKeep - Put the package in the keep state               /*{{{*/
 686 // ---------------------------------------------------------------------
 687 /* */
 688 void pkgDepCache::MarkKeep(PkgIterator const &Pkg, bool Soft, bool FromUser)
 689 {
 690    // Simplifies other routines.
 691    if (Pkg.end() == true)
 692       return;
 693
 694    /* Reject an attempt to keep a non-source broken installed package, those
 695       must be upgraded */
 696    if (Pkg.State() == PkgIterator::NeedsUnpack &&
 697        Pkg.CurrentVer().Downloadable() == false)
 698       return;
 699
 700    /** \todo Can this be moved later in the method? */
 701    ActionGroup group(*this);
 702
 703    /* We changed the soft state all the time so the UI is a bit nicer
 704       to use */
 705    StateCache &P = PkgState[Pkg->ID];
 706    if (Soft == true)
 707       P.iFlags |= AutoKept;
 708    else
 709       P.iFlags &= ~AutoKept;
 710
 711    // Check that it is not already kept
 712    if (P.Mode == ModeKeep)
 713       return;
 714
 715    // We dont even try to keep virtual packages..
 716    if (Pkg->VersionList == 0)
 717       return;
 718
 719 #if 0 // reseting the autoflag here means we lose the
 720       // auto-mark information if a user selects a package for removal
 721       // but changes  his mind then and sets it for keep again
 722       // - this makes sense as default when all Garbage dependencies
 723       //   are automatically marked for removal (as aptitude does).
 724       //   setting a package for keep then makes it no longer autoinstalled
 725       //   for all other use-case this action is rather suprising
 726    if(FromUser && !P.Marked)
 727      P.Flags &= ~Flag::Auto;
 728 #endif
 729
 730    RemoveSizes(Pkg);
 731    RemoveStates(Pkg);
 732
 733    P.Mode = ModeKeep;
 734    if (Pkg->CurrentVer == 0)
 735       P.InstallVer = 0;
 736    else
 737       P.InstallVer = Pkg.CurrentVer();
 738
 739    AddStates(Pkg);
 740
 741    Update(Pkg);
 742
 743    AddSizes(Pkg);
 744 }
 745                                                                         /*}}}*/
 746 // DepCache::MarkDelete - Put the package in the delete state           /*{{{*/
 747 // ---------------------------------------------------------------------
 748 /* */
 749 void pkgDepCache::MarkDelete(PkgIterator const &Pkg, bool rPurge)
 750 {
 751    // Simplifies other routines.
 752    if (Pkg.end() == true)
 753       return;
 754
 755    ActionGroup group(*this);
 756
 757    // Check that it is not already marked for delete
 758    StateCache &P = PkgState[Pkg->ID];
 759    P.iFlags &= ~(AutoKept | Purge);
 760    if (rPurge == true)
 761       P.iFlags |= Purge;
 762
 763    if ((P.Mode == ModeDelete || P.InstallVer == 0) &&
 764        (Pkg.Purge() == true || rPurge == false))
 765       return;
 766
 767    // We dont even try to delete virtual packages..
 768    if (Pkg->VersionList == 0)
 769       return;
 770
 771    RemoveSizes(Pkg);
 772    RemoveStates(Pkg);
 773
 774    if (Pkg->CurrentVer == 0 && (Pkg.Purge() == true || rPurge == false))
 775       P.Mode = ModeKeep;
 776    else
 777       P.Mode = ModeDelete;
 778    P.InstallVer = 0;
 779
 780    AddStates(Pkg);
 781    Update(Pkg);
 782    AddSizes(Pkg);
 783 }
 784                                                                         /*}}}*/
 785 // DepCache::MarkInstall - Put the package in the install state         /*{{{*/
 786 // ---------------------------------------------------------------------
 787 /* */
 788 void pkgDepCache::MarkInstall(PkgIterator const &Pkg,bool AutoInst,
 789                               unsigned long Depth, bool FromUser,
 790                               bool ForceImportantDeps)
 791 {
 792    if (Depth > 100)
 793       return;
 794
 795    // Simplifies other routines.
 796    if (Pkg.end() == true)
 797       return;
 798
 799    ActionGroup group(*this);
 800
 801    /* Check that it is not already marked for install and that it can be
 802       installed */
 803    StateCache &P = PkgState[Pkg->ID];
 804    P.iFlags &= ~AutoKept;
 805    if ((P.InstPolicyBroken() == false && P.InstBroken() == false) &&
 806        (P.Mode == ModeInstall ||
 807         P.CandidateVer == (Version *)Pkg.CurrentVer()))
 808    {
 809       if (P.CandidateVer == (Version *)Pkg.CurrentVer() && P.InstallVer == 0)
 810          MarkKeep(Pkg, false, FromUser);
 811       return;
 812    }
 813
 814    // See if there is even any possible instalation candidate
 815    if (P.CandidateVer == 0)
 816       return;
 817    // We dont even try to install virtual packages..
 818    if (Pkg->VersionList == 0)
 819       return;
 820    /* Target the candidate version and remove the autoflag. We reset the
 821       autoflag below if this was called recursively. Otherwise the user
 822       should have the ability to de-auto a package by changing its state */
 823    RemoveSizes(Pkg);
 824    RemoveStates(Pkg);
 825
 826    P.Mode = ModeInstall;
 827    P.InstallVer = P.CandidateVer;
 828
 829    if(FromUser)
 830      {
 831        // Set it to manual if it's a new install or cancelling the
 832        // removal of a garbage package.
 833        if(P.Status == 2 || (!Pkg.CurrentVer().end() && !P.Marked))
 834          P.Flags &= ~Flag::Auto;
 835      }
 836    else
 837      {
 838        // Set it to auto if this is a new install.
 839        if(P.Status == 2)
 840          P.Flags |= Flag::Auto;
 841      }
 842    if (P.CandidateVer == (Version *)Pkg.CurrentVer())
 843       P.Mode = ModeKeep;
 844
 845    AddStates(Pkg);
 846    Update(Pkg);
 847    AddSizes(Pkg);
 848
 849    if (AutoInst == false)
 850       return;
 851
 852    DepIterator Dep = P.InstVerIter(*this).DependsList();
 853    for (; Dep.end() != true;)
 854    {
 855       // Grok or groups
 856       DepIterator Start = Dep;
 857       bool Result = true;
 858       unsigned Ors = 0;
 859       for (bool LastOR = true; Dep.end() == false && LastOR == true; Dep++,Ors++)
 860       {
 861          LastOR = (Dep->CompareOp & Dep::Or) == Dep::Or;
 862
 863          if ((DepState[Dep->ID] & DepInstall) == DepInstall)
 864             Result = false;
 865       }
 866
 867       // Dep is satisfied okay.
 868       if (Result == false)
 869          continue;
 870
 871       /* Check if this dep should be consider for install. If it is a user
 872          defined important dep and we are installed a new package then
 873          it will be installed. Otherwise we only check for important
 874          deps that have changed from the installed version
 875       */
 876       if (IsImportantDep(Start) == false)
 877          continue;
 878
 879       /* check if any ImportantDep() (but not Critial) where added
 880        * since we installed the package
 881        */
 882       bool isNewImportantDep = false;
 883       if(!ForceImportantDeps && !Start.IsCritical())
 884       {
 885          bool found=false;
 886          VerIterator instVer = Pkg.CurrentVer();
 887          if(!instVer.end())
 888          {
 889             for (DepIterator D = instVer.DependsList(); D.end() != true; D++)
 890             {
 891                //FIXME: deal better with or-groups(?)
 892                DepIterator LocalStart = D;
 893
 894                if(IsImportantDep(D) && Start.TargetPkg() == D.TargetPkg())
 895                   found=true;
 896             }
 897             // this is a new dep if it was not found to be already
 898             // a important dep of the installed pacakge
 899             isNewImportantDep = !found;
 900          }
 901       }
 902       if(isNewImportantDep)
 903          if(_config->FindB("Debug::pkgDepCache::AutoInstall",false) == true)
 904             std::clog << "new important dependency: "
 905                       << Start.TargetPkg().Name() << std::endl;
 906
 907       // skip important deps if the package is already installed
 908       if (Pkg->CurrentVer != 0 && Start.IsCritical() == false
 909           && !isNewImportantDep && !ForceImportantDeps)
 910          continue;
 911
 912       /* If we are in an or group locate the first or that can
 913          succeed. We have already cached this.. */
 914       for (; Ors > 1 && (DepState[Start->ID] & DepCVer) != DepCVer; Ors--)
 915          Start++;
 916
 917       /* This bit is for processing the possibilty of an install/upgrade
 918          fixing the problem */
 919       SPtrArray<Version *> List = Start.AllTargets();
 920       if (Start->Type != Dep::DpkgBreaks &&
 921           (DepState[Start->ID] & DepCVer) == DepCVer)
 922       {
 923          // Right, find the best version to install..
 924          Version **Cur = List;
 925          PkgIterator P = Start.TargetPkg();
 926          PkgIterator InstPkg(*Cache,0);
 927
 928          // See if there are direct matches (at the start of the list)
 929          for (; *Cur != 0 && (*Cur)->ParentPkg == P.Index(); Cur++)
 930          {
 931             PkgIterator Pkg(*Cache,Cache->PkgP + (*Cur)->ParentPkg);
 932             if (PkgState[Pkg->ID].CandidateVer != *Cur)
 933                continue;
 934             InstPkg = Pkg;
 935             break;
 936          }
 937
 938          // Select the highest priority providing package
 939          if (InstPkg.end() == true)
 940          {
 941             pkgPrioSortList(*Cache,Cur);
 942             for (; *Cur != 0; Cur++)
 943             {
 944                PkgIterator Pkg(*Cache,Cache->PkgP + (*Cur)->ParentPkg);
 945                if (PkgState[Pkg->ID].CandidateVer != *Cur)
 946                   continue;
 947                InstPkg = Pkg;
 948                break;
 949             }
 950          }
 951
 952          if (InstPkg.end() == false)
 953          {
 954             if(_config->FindB("Debug::pkgDepCache::AutoInstall",false) == true)
 955                std::clog << "Installing " << InstPkg.Name()
 956                          << " as dep of " << Pkg.Name()
 957                          << std::endl;
 958             MarkInstall(InstPkg,true,Depth + 1, false, ForceImportantDeps);
 959
 960             // Set the autoflag, after MarkInstall because MarkInstall unsets it
 961             if (P->CurrentVer == 0)
 962                PkgState[InstPkg->ID].Flags |= Flag::Auto;
 963          }
 964          continue;
 965       }
 966
 967       /* For conflicts we just de-install the package and mark as auto,
 968          Conflicts may not have or groups.  For dpkg's Breaks we try to
 969          upgrade the package. */
 970       if (Start->Type == Dep::Conflicts || Start->Type == Dep::Obsoletes ||
 971           Start->Type == Dep::DpkgBreaks)
 972       {
 973          for (Version **I = List; *I != 0; I++)
 974          {
 975             VerIterator Ver(*this,*I);
 976             PkgIterator Pkg = Ver.ParentPkg();
 977
 978             if (Start->Type != Dep::DpkgBreaks)
 979                MarkDelete(Pkg);
 980             else
 981                if (PkgState[Pkg->ID].CandidateVer != *I)
 982                   MarkInstall(Pkg,true,Depth + 1, false, ForceImportantDeps);
 983          }
 984          continue;
 985       }
 986    }
 987 }
 988                                                                         /*}}}*/
 989 // DepCache::SetReInstall - Set the reinstallation flag                 /*{{{*/
 990 // ---------------------------------------------------------------------
 991 /* */
 992 void pkgDepCache::SetReInstall(PkgIterator const &Pkg,bool To)
 993 {
 994    ActionGroup group(*this);
 995
 996    RemoveSizes(Pkg);
 997    RemoveStates(Pkg);
 998
 999    StateCache &P = PkgState[Pkg->ID];
1000    if (To == true)
1001       P.iFlags |= ReInstall;
1002    else
1003       P.iFlags &= ~ReInstall;
1004
1005    AddStates(Pkg);
1006    AddSizes(Pkg);
1007 }
1008                                                                         /*}}}*/
1009 // DepCache::SetCandidateVersion - Change the candidate version         /*{{{*/
1010 // ---------------------------------------------------------------------
1011 /* */
1012 void pkgDepCache::SetCandidateVersion(VerIterator TargetVer)
1013 {
1014    ActionGroup group(*this);
1015
1016    pkgCache::PkgIterator Pkg = TargetVer.ParentPkg();
1017    StateCache &P = PkgState[Pkg->ID];
1018
1019    RemoveSizes(Pkg);
1020    RemoveStates(Pkg);
1021
1022    if (P.CandidateVer == P.InstallVer)
1023       P.InstallVer = (Version *)TargetVer;
1024    P.CandidateVer = (Version *)TargetVer;
1025    P.Update(Pkg,*this);
1026
1027    AddStates(Pkg);
1028    Update(Pkg);
1029    AddSizes(Pkg);
1030 }
1031
1032 void pkgDepCache::MarkAuto(const PkgIterator &Pkg, bool Auto)
1033 {
1034   StateCache &state = PkgState[Pkg->ID];
1035
1036   ActionGroup group(*this);
1037
1038   if(Auto)
1039     state.Flags |= Flag::Auto;
1040   else
1041     state.Flags &= ~Flag::Auto;
1042 }
1043                                                                         /*}}}*/
1044 // StateCache::Update - Compute the various static display things       /*{{{*/
1045 // ---------------------------------------------------------------------
1046 /* This is called whenever the Candidate version changes. */
1047 void pkgDepCache::StateCache::Update(PkgIterator Pkg,pkgCache &Cache)
1048 {
1049    // Some info
1050    VerIterator Ver = CandidateVerIter(Cache);
1051
1052    // Use a null string or the version string
1053    if (Ver.end() == true)
1054       CandVersion = "";
1055    else
1056       CandVersion = Ver.VerStr();
1057
1058    // Find the current version
1059    CurVersion = "";
1060    if (Pkg->CurrentVer != 0)
1061       CurVersion = Pkg.CurrentVer().VerStr();
1062
1063    // Strip off the epochs for display
1064    CurVersion = StripEpoch(CurVersion);
1065    CandVersion = StripEpoch(CandVersion);
1066
1067    // Figure out if its up or down or equal
1068    Status = Ver.CompareVer(Pkg.CurrentVer());
1069    if (Pkg->CurrentVer == 0 || Pkg->VersionList == 0 || CandidateVer == 0)
1070      Status = 2;
1071 }
1072                                                                         /*}}}*/
1073 // StateCache::StripEpoch - Remove the epoch specifier from the version /*{{{*/
1074 // ---------------------------------------------------------------------
1075 /* */
1076 const char *pkgDepCache::StateCache::StripEpoch(const char *Ver)
1077 {
1078    if (Ver == 0)
1079       return 0;
1080
1081    // Strip any epoch
1082    for (const char *I = Ver; *I != 0; I++)
1083       if (*I == ':')
1084          return I + 1;
1085    return Ver;
1086 }
1087                                                                         /*}}}*/
1088
1089 // Policy::GetCandidateVer - Returns the Candidate install version      /*{{{*/
1090 // ---------------------------------------------------------------------
1091 /* The default just returns the highest available version that is not
1092    a source and automatic. */
1093 pkgCache::VerIterator pkgDepCache::Policy::GetCandidateVer(PkgIterator Pkg)
1094 {
1095    /* Not source/not automatic versions cannot be a candidate version
1096       unless they are already installed */
1097    VerIterator Last(*(pkgCache *)this,0);
1098
1099    for (VerIterator I = Pkg.VersionList(); I.end() == false; I++)
1100    {
1101       if (Pkg.CurrentVer() == I)
1102          return I;
1103
1104       for (VerFileIterator J = I.FileList(); J.end() == false; J++)
1105       {
1106          if ((J.File()->Flags & Flag::NotSource) != 0)
1107             continue;
1108
1109          /* Stash the highest version of a not-automatic source, we use it
1110             if there is nothing better */
1111          if ((J.File()->Flags & Flag::NotAutomatic) != 0)
1112          {
1113             if (Last.end() == true)
1114                Last = I;
1115             continue;
1116          }
1117
1118          return I;
1119       }
1120    }
1121
1122    return Last;
1123 }
1124                                                                         /*}}}*/
1125                                                                         /*}}}*/
1126
1127 pkgDepCache::DefaultRootSetFunc::DefaultRootSetFunc()
1128   : constructedSuccessfully(false)
1129 {
1130   Configuration::Item const *Opts;
1131   Opts = _config->Tree("APT::NeverAutoRemove");
1132   if (Opts != 0 && Opts->Child != 0)
1133     {
1134       Opts = Opts->Child;
1135       for (; Opts != 0; Opts = Opts->Next)
1136         {
1137           if (Opts->Value.empty() == true)
1138             continue;
1139
1140           regex_t *p = new regex_t;
1141           if(regcomp(p,Opts->Value.c_str(),
1142                      REG_EXTENDED | REG_ICASE | REG_NOSUB) != 0)
1143             {
1144               regfree(p);
1145               delete p;
1146               _error->Error("Regex compilation error for APT::NeverAutoRemove");
1147               return;
1148             }
1149
1150           rootSetRegexp.push_back(p);
1151         }
1152     }
1153
1154   constructedSuccessfully = true;
1155 }
1156
1157 pkgDepCache::DefaultRootSetFunc::~DefaultRootSetFunc()
1158 {
1159   for(unsigned int i = 0; i < rootSetRegexp.size(); i++)
1160     {
1161       regfree(rootSetRegexp[i]);
1162       delete rootSetRegexp[i];
1163     }
1164 }
1165
1166
1167 bool pkgDepCache::DefaultRootSetFunc::InRootSet(const pkgCache::PkgIterator &pkg)
1168 {
1169    for(unsigned int i = 0; i < rootSetRegexp.size(); i++)
1170       if (regexec(rootSetRegexp[i], pkg.Name(), 0, 0, 0) == 0)
1171          return true;
1172
1173    return false;
1174 }
1175
1176 pkgDepCache::InRootSetFunc *pkgDepCache::GetRootSetFunc()
1177 {
1178   DefaultRootSetFunc *f = new DefaultRootSetFunc;
1179   if(f->wasConstructedSuccessfully())
1180     return f;
1181   else
1182     {
1183       delete f;
1184       return NULL;
1185     }
1186 }
1187
1188 bool pkgDepCache::MarkFollowsRecommends()
1189 {
1190   return _config->FindB("APT::AutoRemove::RecommendsImportant", true);
1191 }
1192
1193 bool pkgDepCache::MarkFollowsSuggests()
1194 {
1195   return _config->FindB("APT::AutoRemove::SuggestsImportant", false);
1196 }
1197
1198 // the main mark algorithm
1199 bool pkgDepCache::MarkRequired(InRootSetFunc &userFunc)
1200 {
1201    bool follow_recommends;
1202    bool follow_suggests;
1203
1204    // init the states
1205    for(PkgIterator p = PkgBegin(); !p.end(); ++p)
1206    {
1207       PkgState[p->ID].Marked  = false;
1208       PkgState[p->ID].Garbage = false;
1209
1210       // debug output
1211       if(_config->FindB("Debug::pkgAutoRemove",false)
1212          && PkgState[p->ID].Flags & Flag::Auto)
1213          std::clog << "AutoDep: " << p.Name() << std::endl;
1214    }
1215
1216    // init vars
1217    follow_recommends = MarkFollowsRecommends();
1218    follow_suggests   = MarkFollowsSuggests();
1219
1220
1221
1222    // do the mark part, this is the core bit of the algorithm
1223    for(PkgIterator p = PkgBegin(); !p.end(); ++p)
1224    {
1225       if(!(PkgState[p->ID].Flags & Flag::Auto) ||
1226           (p->Flags & Flag::Essential) ||
1227           userFunc.InRootSet(p))
1228
1229       {
1230          // the package is installed (and set to keep)
1231          if(PkgState[p->ID].Keep() && !p.CurrentVer().end())
1232             MarkPackage(p, p.CurrentVer(),
1233                         follow_recommends, follow_suggests);
1234          // the package is to be installed
1235          else if(PkgState[p->ID].Install())
1236             MarkPackage(p, PkgState[p->ID].InstVerIter(*this),
1237                         follow_recommends, follow_suggests);
1238       }
1239    }
1240
1241    return true;
1242 }
1243
1244 // mark a single package in Mark-and-Sweep
1245 void pkgDepCache::MarkPackage(const pkgCache::PkgIterator &pkg,
1246                               const pkgCache::VerIterator &ver,
1247                               bool follow_recommends,
1248                               bool follow_suggests)
1249 {
1250    pkgDepCache::StateCache &state = PkgState[pkg->ID];
1251    VerIterator candver            = state.CandidateVerIter(*this);
1252    VerIterator instver            = state.InstVerIter(*this);
1253
1254 #if 0
1255    // If a package was garbage-collected but is now being marked, we
1256    // should re-select it
1257    // For cases when a pkg is set to upgrade and this trigger the
1258    // removal of a no-longer used dependency.  if the pkg is set to
1259    // keep again later it will result in broken deps
1260    if(state.Delete() && state.RemoveReason = Unused)
1261    {
1262       if(ver==candver)
1263          mark_install(pkg, false, false, NULL);
1264       else if(ver==pkg.CurrentVer())
1265          MarkKeep(pkg, false, false);
1266
1267       instver=state.InstVerIter(*this);
1268    }
1269 #endif
1270
1271    // Ignore versions other than the InstVer, and ignore packages
1272    // that are already going to be removed or just left uninstalled.
1273    if(!(ver == instver && !instver.end()))
1274       return;
1275
1276    // if we are marked already we are done
1277    if(state.Marked)
1278       return;
1279
1280    //std::cout << "Setting Marked for: " << pkg.Name() << std::endl;
1281    state.Marked=true;
1282
1283    if(!ver.end())
1284    {
1285      for(DepIterator d = ver.DependsList(); !d.end(); ++d)
1286      {
1287         if(d->Type == Dep::Depends ||
1288            d->Type == Dep::PreDepends ||
1289            (follow_recommends &&
1290             d->Type == Dep::Recommends) ||
1291            (follow_suggests &&
1292             d->Type == Dep::Suggests))
1293         {
1294            // Try all versions of this package.
1295            for(VerIterator V = d.TargetPkg().VersionList();
1296                !V.end(); ++V)
1297            {
1298               if(_system->VS->CheckDep(V.VerStr(), d->CompareOp, d.TargetVer()))
1299               {
1300                  MarkPackage(V.ParentPkg(), V,
1301                              follow_recommends, follow_suggests);
1302               }
1303            }
1304            // Now try virtual packages
1305            for(PrvIterator prv=d.TargetPkg().ProvidesList();
1306                !prv.end(); ++prv)
1307            {
1308               if(_system->VS->CheckDep(prv.ProvideVersion(), d->CompareOp,
1309                                        d.TargetVer()))
1310               {
1311                  MarkPackage(prv.OwnerPkg(), prv.OwnerVer(),
1312                              follow_recommends, follow_suggests);
1313               }
1314            }
1315         }
1316      }
1317    }
1318 }
1319
1320 bool pkgDepCache::Sweep()
1321 {
1322    // do the sweep
1323    for(PkgIterator p=PkgBegin(); !p.end(); ++p)
1324   {
1325      StateCache &state=PkgState[p->ID];
1326
1327      // skip required packages
1328      if (!p.CurrentVer().end() &&
1329          (p.CurrentVer()->Priority == pkgCache::State::Required))
1330         continue;
1331
1332      // if it is not marked and it is installed, it's garbage
1333      if(!state.Marked && (!p.CurrentVer().end() || state.Install()))
1334      {
1335         state.Garbage=true;
1336         if(_config->FindB("Debug::pkgAutoRemove",false))
1337            std::cout << "Garbage: " << p.Name() << std::endl;
1338      }
1339   }
1340
1341    return true;
1342 }
1343
1344 // Policy::IsImportantDep - True if the dependency is important         /*{{{*/
1345 // ---------------------------------------------------------------------
1346 /* */
1347 bool pkgDepCache::Policy::IsImportantDep(DepIterator Dep)
1348 {
1349    if(Dep.IsCritical())
1350       return true;
1351    else if(Dep->Type == pkgCache::Dep::Recommends)
1352    {
1353       if ( _config->FindB("APT::Install-Recommends", false))
1354          return true;
1355       // we suport a special mode to only install-recommends for certain
1356       // sections
1357       // FIXME: this is a meant as a temporarly solution until the
1358       //        recommends are cleaned up
1359       string s = _config->Find("APT::Install-Recommends-Section","");
1360       if(s.size() > 0)
1361       {
1362          const char *sec = Dep.ParentVer().Section();
1363          if (sec && strcmp(sec, s.c_str()) == 0)
1364             return true;
1365       }
1366    }
1367    else if(Dep->Type == pkgCache::Dep::Suggests)
1368      return _config->FindB("APT::Install-Suggests", false);
1369
1370    return false;
1371 }
1372                                                                         /*}}}*/