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 #include <apt-pkg/depcache.h>
  12 #include <apt-pkg/version.h>
  13 #include <apt-pkg/error.h>
  14 #include <apt-pkg/sptr.h>
  15 #include <apt-pkg/algorithms.h>
  16
  17 #include <apt-pkg/fileutl.h>
  18 #include <apt-pkg/configuration.h>
  19 #include <apt-pkg/pkgsystem.h>
  20 #include <apt-pkg/tagfile.h>
  21
  22 #include <iostream>
  23 #include <sstream>
  24 #include <set>
  25
  26 #include <sys/stat.h>
  27
  28 #include <apti18n.h>
  29
  30 pkgDepCache::ActionGroup::ActionGroup(pkgDepCache &cache) :
  31   cache(cache), released(false)
  32 {
  33   ++cache.group_level;
  34 }
  35
  36 void pkgDepCache::ActionGroup::release()
  37 {
  38   if(!released)
  39     {
  40       if(cache.group_level == 0)
  41         std::cerr << "W: Unbalanced action groups, expect badness" << std::endl;
  42       else
  43         {
  44           --cache.group_level;
  45
  46           if(cache.group_level == 0)
  47             cache.MarkAndSweep();
  48         }
  49
  50       released = false;
  51     }
  52 }
  53
  54 pkgDepCache::ActionGroup::~ActionGroup()
  55 {
  56   release();
  57 }
  58
  59 // DepCache::pkgDepCache - Constructors                                 /*{{{*/
  60 // ---------------------------------------------------------------------
  61 /* */
  62 pkgDepCache::pkgDepCache(pkgCache *pCache,Policy *Plcy) :
  63   group_level(0), Cache(pCache), PkgState(0), DepState(0)
  64 {
  65    delLocalPolicy = 0;
  66    LocalPolicy = Plcy;
  67    if (LocalPolicy == 0)
  68       delLocalPolicy = LocalPolicy = new Policy;
  69 }
  70                                                                         /*}}}*/
  71 // DepCache::~pkgDepCache - Destructor                                  /*{{{*/
  72 // ---------------------------------------------------------------------
  73 /* */
  74 pkgDepCache::~pkgDepCache()
  75 {
  76    delete [] PkgState;
  77    delete [] DepState;
  78    delete delLocalPolicy;
  79 }
  80                                                                         /*}}}*/
  81 // DepCache::Init - Generate the initial extra structures.              /*{{{*/
  82 // ---------------------------------------------------------------------
  83 /* This allocats the extension buffers and initializes them. */
  84 bool pkgDepCache::Init(OpProgress *Prog)
  85 {
  86    // Suppress mark updates during this operation (just in case) and
  87    // run a mark operation when Init terminates.
  88    ActionGroup actions(*this);
  89
  90    delete [] PkgState;
  91    delete [] DepState;
  92    PkgState = new StateCache[Head().PackageCount];
  93    DepState = new unsigned char[Head().DependsCount];
  94    memset(PkgState,0,sizeof(*PkgState)*Head().PackageCount);
  95    memset(DepState,0,sizeof(*DepState)*Head().DependsCount);
  96
  97    if (Prog != 0)
  98    {
  99       Prog->OverallProgress(0,2*Head().PackageCount,Head().PackageCount,
 100                             _("Building dependency tree"));
 101       Prog->SubProgress(Head().PackageCount,_("Candidate versions"));
 102    }
 103
 104    /* Set the current state of everything. In this state all of the
 105       packages are kept exactly as is. See AllUpgrade */
 106    int Done = 0;
 107    for (PkgIterator I = PkgBegin(); I.end() != true; I++,Done++)
 108    {
 109       if (Prog != 0)
 110          Prog->Progress(Done);
 111
 112       // Find the proper cache slot
 113       StateCache &State = PkgState[I->ID];
 114       State.iFlags = 0;
 115
 116       // Figure out the install version
 117       State.CandidateVer = GetCandidateVer(I);
 118       State.InstallVer = I.CurrentVer();
 119       State.Mode = ModeKeep;
 120
 121       State.Update(I,*this);
 122    }
 123
 124    if (Prog != 0)
 125    {
 126
 127       Prog->OverallProgress(Head().PackageCount,2*Head().PackageCount,
 128                             Head().PackageCount,
 129                             _("Building dependency tree"));
 130       Prog->SubProgress(Head().PackageCount,_("Dependency generation"));
 131    }
 132
 133    Update(Prog);
 134
 135    if(Prog != 0)
 136       Prog->Done();
 137
 138    return true;
 139 }
 140                                                                         /*}}}*/
 141
 142 bool pkgDepCache::readStateFile(OpProgress *Prog)
 143 {
 144    FileFd state_file;
 145    string state = _config->FindDir("Dir::State") + "extended_states";
 146    if(FileExists(state)) {
 147       state_file.Open(state, FileFd::ReadOnly);
 148       int file_size = state_file.Size();
 149       if(Prog != NULL)
 150          Prog->OverallProgress(0, file_size, 1,
 151                                _("Reading state information"));
 152
 153       pkgTagFile tagfile(&state_file);
 154       pkgTagSection section;
 155       int amt=0;
 156       while(tagfile.Step(section)) {
 157          string pkgname = section.FindS("Package");
 158          pkgCache::PkgIterator pkg=Cache->FindPkg(pkgname);
 159          // Silently ignore unknown packages and packages with no actual
 160          // version.
 161          if(!pkg.end() && !pkg.VersionList().end()) {
 162             short reason = section.FindI("Auto-Installed", 0);
 163             if(reason > 0)
 164                PkgState[pkg->ID].Flags  |= Flag::Auto;
 165             if(_config->FindB("Debug::pkgAutoRemove",false))
 166                std::cout << "Auto-Installed : " << pkgname << std::endl;
 167             amt+=section.size();
 168             if(Prog != NULL)
 169                Prog->OverallProgress(amt, file_size, 1,
 170                                      _("Reading state information"));
 171          }
 172          if(Prog != NULL)
 173             Prog->OverallProgress(file_size, file_size, 1,
 174                                   _("Reading state information"));
 175       }
 176    }
 177
 178    return true;
 179 }
 180
 181 bool pkgDepCache::writeStateFile(OpProgress *prog)
 182 {
 183    if(_config->FindB("Debug::pkgAutoRemove",false))
 184       std::clog << "pkgDepCache::writeStateFile()" << std::endl;
 185
 186    FileFd StateFile;
 187    string state = _config->FindDir("Dir::State") + "extended_states";
 188
 189    // if it does not exist, create a empty one
 190    if(!FileExists(state))
 191    {
 192       StateFile.Open(state, FileFd::WriteEmpty);
 193       StateFile.Close();
 194    }
 195
 196    // open it
 197    if(!StateFile.Open(state, FileFd::ReadOnly))
 198       return _error->Error(_("Failed to open StateFile %s"),
 199                            state.c_str());
 200
 201    FILE *OutFile;
 202    string outfile = state + ".tmp";
 203    if((OutFile = fopen(outfile.c_str(),"w")) == NULL)
 204       return _error->Error(_("Failed to write temporary StateFile %s"),
 205                            outfile.c_str());
 206
 207    // first merge with the existing sections
 208    pkgTagFile tagfile(&StateFile);
 209    pkgTagSection section;
 210    std::set<string> pkgs_seen;
 211    const char *nullreorderlist[] = {0};
 212    while(tagfile.Step(section)) {
 213          string pkgname = section.FindS("Package");
 214          // Silently ignore unknown packages and packages with no actual
 215          // version.
 216          pkgCache::PkgIterator pkg=Cache->FindPkg(pkgname);
 217          if(pkg.end() || pkg.VersionList().end())
 218             continue;
 219          bool oldAuto = section.FindI("Auto-Installed");
 220          bool newAuto = (PkgState[pkg->ID].Flags & Flag::Auto);
 221          if(_config->FindB("Debug::pkgAutoRemove",false))
 222             std::clog << "Update exisiting AutoInstall info: "
 223                       << pkg.Name() << std::endl;
 224          TFRewriteData rewrite[2];
 225          rewrite[0].Tag = "Auto-Installed";
 226          rewrite[0].Rewrite = newAuto ? "1" : "0";
 227          rewrite[0].NewTag = 0;
 228          rewrite[1].Tag = 0;
 229          TFRewrite(OutFile, section, nullreorderlist, rewrite);
 230          fprintf(OutFile,"\n");
 231          pkgs_seen.insert(pkgname);
 232    }
 233
 234    // then write the ones we have not seen yet
 235    std::ostringstream ostr;
 236    for(pkgCache::PkgIterator pkg=Cache->PkgBegin(); !pkg.end(); pkg++) {
 237       if(PkgState[pkg->ID].Flags & Flag::Auto) {
 238          if (pkgs_seen.find(pkg.Name()) != pkgs_seen.end()) {
 239             if(_config->FindB("Debug::pkgAutoRemove",false))
 240                std::clog << "Skipping already written " << pkg.Name() << std::endl;
 241             continue;
 242          }
 243          // skip not installed ones if requested
 244          if(InstalledOnly && pkg->CurrentVer == 0)
 245             continue;
 246          if(_config->FindB("Debug::pkgAutoRemove",false))
 247             std::clog << "Writing new AutoInstall: "
 248                       << pkg.Name() << std::endl;
 249          ostr.str(string(""));
 250          ostr << "Package: " << pkg.Name()
 251               << "\nAuto-Installed: 1\n\n";
 252          fprintf(OutFile,ostr.str().c_str());
 253          fprintf(OutFile,"\n");
 254       }
 255    }
 256    fclose(OutFile);
 257
 258    // move the outfile over the real file and set permissions
 259    rename(outfile.c_str(), state.c_str());
 260    chmod(state.c_str(), 0644);
 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 #if 0 // reseting the autoflag here means we lose the
 719       // auto-mark information if a user selects a package for removal
 720       // but changes  his mind then and sets it for keep again
 721       // - this makes sense as default when all Garbage dependencies
 722       //   are automatically marked for removal (as aptitude does).
 723       //   setting a package for keep then makes it no longer autoinstalled
 724       //   for all other use-case this action is rather suprising
 725    if(FromUser && !P.Marked)
 726      P.Flags &= ~Flag::Auto;
 727 #endif
 728
 729    RemoveSizes(Pkg);
 730    RemoveStates(Pkg);
 731
 732    P.Mode = ModeKeep;
 733    if (Pkg->CurrentVer == 0)
 734       P.InstallVer = 0;
 735    else
 736       P.InstallVer = Pkg.CurrentVer();
 737
 738    AddStates(Pkg);
 739
 740    Update(Pkg);
 741
 742    AddSizes(Pkg);
 743 }
 744                                                                         /*}}}*/
 745 // DepCache::MarkDelete - Put the package in the delete state           /*{{{*/
 746 // ---------------------------------------------------------------------
 747 /* */
 748 void pkgDepCache::MarkDelete(PkgIterator const &Pkg, bool rPurge)
 749 {
 750    // Simplifies other routines.
 751    if (Pkg.end() == true)
 752       return;
 753
 754    ActionGroup group(*this);
 755
 756    // Check that it is not already marked for delete
 757    StateCache &P = PkgState[Pkg->ID];
 758    P.iFlags &= ~(AutoKept | Purge);
 759    if (rPurge == true)
 760       P.iFlags |= Purge;
 761
 762    if ((P.Mode == ModeDelete || P.InstallVer == 0) &&
 763        (Pkg.Purge() == true || rPurge == false))
 764       return;
 765
 766    // We dont even try to delete virtual packages..
 767    if (Pkg->VersionList == 0)
 768       return;
 769
 770    RemoveSizes(Pkg);
 771    RemoveStates(Pkg);
 772
 773    if (Pkg->CurrentVer == 0 && (Pkg.Purge() == true || rPurge == false))
 774       P.Mode = ModeKeep;
 775    else
 776       P.Mode = ModeDelete;
 777    P.InstallVer = 0;
 778
 779    AddStates(Pkg);
 780    Update(Pkg);
 781    AddSizes(Pkg);
 782 }
 783                                                                         /*}}}*/
 784 // DepCache::MarkInstall - Put the package in the install state         /*{{{*/
 785 // ---------------------------------------------------------------------
 786 /* */
 787 void pkgDepCache::MarkInstall(PkgIterator const &Pkg,bool AutoInst,
 788                               unsigned long Depth, bool FromUser,
 789                               bool ForceImportantDeps)
 790 {
 791    if (Depth > 100)
 792       return;
 793
 794    // Simplifies other routines.
 795    if (Pkg.end() == true)
 796       return;
 797
 798    ActionGroup group(*this);
 799
 800    /* Check that it is not already marked for install and that it can be
 801       installed */
 802    StateCache &P = PkgState[Pkg->ID];
 803    P.iFlags &= ~AutoKept;
 804    if ((P.InstPolicyBroken() == false && P.InstBroken() == false) &&
 805        (P.Mode == ModeInstall ||
 806         P.CandidateVer == (Version *)Pkg.CurrentVer()))
 807    {
 808       if (P.CandidateVer == (Version *)Pkg.CurrentVer() && P.InstallVer == 0)
 809          MarkKeep(Pkg, false, FromUser);
 810       return;
 811    }
 812
 813    // See if there is even any possible instalation candidate
 814    if (P.CandidateVer == 0)
 815       return;
 816    // We dont even try to install virtual packages..
 817    if (Pkg->VersionList == 0)
 818       return;
 819    /* Target the candidate version and remove the autoflag. We reset the
 820       autoflag below if this was called recursively. Otherwise the user
 821       should have the ability to de-auto a package by changing its state */
 822    RemoveSizes(Pkg);
 823    RemoveStates(Pkg);
 824
 825    P.Mode = ModeInstall;
 826    P.InstallVer = P.CandidateVer;
 827
 828    if(FromUser)
 829      {
 830        // Set it to manual if it's a new install or cancelling the
 831        // removal of a garbage package.
 832        if(P.Status == 2 || (!Pkg.CurrentVer().end() && !P.Marked))
 833          P.Flags &= ~Flag::Auto;
 834      }
 835    else
 836      {
 837        // Set it to auto if this is a new install.
 838        if(P.Status == 2)
 839          P.Flags |= Flag::Auto;
 840      }
 841    if (P.CandidateVer == (Version *)Pkg.CurrentVer())
 842       P.Mode = ModeKeep;
 843
 844    AddStates(Pkg);
 845    Update(Pkg);
 846    AddSizes(Pkg);
 847
 848    if (AutoInst == false)
 849       return;
 850
 851    DepIterator Dep = P.InstVerIter(*this).DependsList();
 852    for (; Dep.end() != true;)
 853    {
 854       // Grok or groups
 855       DepIterator Start = Dep;
 856       bool Result = true;
 857       unsigned Ors = 0;
 858       for (bool LastOR = true; Dep.end() == false && LastOR == true; Dep++,Ors++)
 859       {
 860          LastOR = (Dep->CompareOp & Dep::Or) == Dep::Or;
 861
 862          if ((DepState[Dep->ID] & DepInstall) == DepInstall)
 863             Result = false;
 864       }
 865
 866       // Dep is satisfied okay.
 867       if (Result == false)
 868          continue;
 869
 870       /* Check if this dep should be consider for install. If it is a user
 871          defined important dep and we are installed a new package then
 872          it will be installed. Otherwise we only check for important
 873          deps that have changed from the installed version
 874       */
 875       if (IsImportantDep(Start) == false)
 876          continue;
 877
 878       /* check if any ImportantDep() (but not Critial) where added
 879        * since we installed the package
 880        */
 881       bool isNewImportantDep = false;
 882       if(!ForceImportantDeps && !Start.IsCritical())
 883       {
 884          bool found=false;
 885          VerIterator instVer = Pkg.CurrentVer();
 886          if(!instVer.end())
 887          {
 888             for (DepIterator D = instVer.DependsList(); D.end() != true; D++)
 889             {
 890                //FIXME: deal better with or-groups(?)
 891                DepIterator LocalStart = D;
 892
 893                if(IsImportantDep(D) && Start.TargetPkg() == D.TargetPkg())
 894                   found=true;
 895             }
 896             // this is a new dep if it was not found to be already
 897             // a important dep of the installed pacakge
 898             isNewImportantDep = !found;
 899          }
 900       }
 901       if(isNewImportantDep)
 902          if(_config->FindB("Debug::pkgDepCache::AutoInstall",false) == true)
 903             std::clog << "new important dependency: "
 904                       << Start.TargetPkg().Name() << std::endl;
 905
 906       // skip important deps if the package is already installed
 907       if (Pkg->CurrentVer != 0 && Start.IsCritical() == false
 908           && !isNewImportantDep && !ForceImportantDeps)
 909          continue;
 910
 911       /* If we are in an or group locate the first or that can
 912          succeed. We have already cached this.. */
 913       for (; Ors > 1 && (DepState[Start->ID] & DepCVer) != DepCVer; Ors--)
 914          Start++;
 915
 916       /* This bit is for processing the possibilty of an install/upgrade
 917          fixing the problem */
 918       SPtrArray<Version *> List = Start.AllTargets();
 919       if (Start->Type != Dep::DpkgBreaks &&
 920           (DepState[Start->ID] & DepCVer) == DepCVer)
 921       {
 922          // Right, find the best version to install..
 923          Version **Cur = List;
 924          PkgIterator P = Start.TargetPkg();
 925          PkgIterator InstPkg(*Cache,0);
 926
 927          // See if there are direct matches (at the start of the list)
 928          for (; *Cur != 0 && (*Cur)->ParentPkg == P.Index(); Cur++)
 929          {
 930             PkgIterator Pkg(*Cache,Cache->PkgP + (*Cur)->ParentPkg);
 931             if (PkgState[Pkg->ID].CandidateVer != *Cur)
 932                continue;
 933             InstPkg = Pkg;
 934             break;
 935          }
 936
 937          // Select the highest priority providing package
 938          if (InstPkg.end() == true)
 939          {
 940             pkgPrioSortList(*Cache,Cur);
 941             for (; *Cur != 0; Cur++)
 942             {
 943                PkgIterator Pkg(*Cache,Cache->PkgP + (*Cur)->ParentPkg);
 944                if (PkgState[Pkg->ID].CandidateVer != *Cur)
 945                   continue;
 946                InstPkg = Pkg;
 947                break;
 948             }
 949          }
 950
 951          if (InstPkg.end() == false)
 952          {
 953             if(_config->FindB("Debug::pkgDepCache::AutoInstall",false) == true)
 954                std::clog << "Installing " << InstPkg.Name()
 955                          << " as dep of " << Pkg.Name()
 956                          << std::endl;
 957             // now check if we should consider it a automatic dependency or not
 958             string sec = _config->Find("APT::Never-MarkAuto-Section","");
 959             if(Pkg.Section() && (string(Pkg.Section()) ==  sec))
 960             {
 961                if(_config->FindB("Debug::pkgDepCache::AutoInstall",false) == true)
 962                   std::clog << "Setting NOT as auto-installed because its a direct dep of a package in section " << sec << std::endl;
 963                MarkInstall(InstPkg,true,Depth + 1, true);
 964             }
 965             else
 966             {
 967                // mark automatic dependency
 968                MarkInstall(InstPkg,true,Depth + 1, false, ForceImportantDeps);
 969                // Set the autoflag, after MarkInstall because MarkInstall unsets it
 970                if (P->CurrentVer == 0)
 971                   PkgState[InstPkg->ID].Flags |= Flag::Auto;
 972             }
 973          }
 974          continue;
 975       }
 976
 977       /* For conflicts we just de-install the package and mark as auto,
 978          Conflicts may not have or groups.  For dpkg's Breaks we try to
 979          upgrade the package. */
 980       if (Start->Type == Dep::Conflicts || Start->Type == Dep::Obsoletes ||
 981           Start->Type == Dep::DpkgBreaks)
 982       {
 983          for (Version **I = List; *I != 0; I++)
 984          {
 985             VerIterator Ver(*this,*I);
 986             PkgIterator Pkg = Ver.ParentPkg();
 987
 988             if (Start->Type != Dep::DpkgBreaks)
 989                MarkDelete(Pkg);
 990             else
 991                if (PkgState[Pkg->ID].CandidateVer != *I)
 992                   MarkInstall(Pkg,true,Depth + 1, false, ForceImportantDeps);
 993          }
 994          continue;
 995       }
 996    }
 997 }
 998                                                                         /*}}}*/
 999 // DepCache::SetReInstall - Set the reinstallation flag                 /*{{{*/
1000 // ---------------------------------------------------------------------
1001 /* */
1002 void pkgDepCache::SetReInstall(PkgIterator const &Pkg,bool To)
1003 {
1004    ActionGroup group(*this);
1005
1006    RemoveSizes(Pkg);
1007    RemoveStates(Pkg);
1008
1009    StateCache &P = PkgState[Pkg->ID];
1010    if (To == true)
1011       P.iFlags |= ReInstall;
1012    else
1013       P.iFlags &= ~ReInstall;
1014
1015    AddStates(Pkg);
1016    AddSizes(Pkg);
1017 }
1018                                                                         /*}}}*/
1019 // DepCache::SetCandidateVersion - Change the candidate version         /*{{{*/
1020 // ---------------------------------------------------------------------
1021 /* */
1022 void pkgDepCache::SetCandidateVersion(VerIterator TargetVer)
1023 {
1024    ActionGroup group(*this);
1025
1026    pkgCache::PkgIterator Pkg = TargetVer.ParentPkg();
1027    StateCache &P = PkgState[Pkg->ID];
1028
1029    RemoveSizes(Pkg);
1030    RemoveStates(Pkg);
1031
1032    if (P.CandidateVer == P.InstallVer)
1033       P.InstallVer = (Version *)TargetVer;
1034    P.CandidateVer = (Version *)TargetVer;
1035    P.Update(Pkg,*this);
1036
1037    AddStates(Pkg);
1038    Update(Pkg);
1039    AddSizes(Pkg);
1040 }
1041
1042 void pkgDepCache::MarkAuto(const PkgIterator &Pkg, bool Auto)
1043 {
1044   StateCache &state = PkgState[Pkg->ID];
1045
1046   ActionGroup group(*this);
1047
1048   if(Auto)
1049     state.Flags |= Flag::Auto;
1050   else
1051     state.Flags &= ~Flag::Auto;
1052 }
1053                                                                         /*}}}*/
1054 // StateCache::Update - Compute the various static display things       /*{{{*/
1055 // ---------------------------------------------------------------------
1056 /* This is called whenever the Candidate version changes. */
1057 void pkgDepCache::StateCache::Update(PkgIterator Pkg,pkgCache &Cache)
1058 {
1059    // Some info
1060    VerIterator Ver = CandidateVerIter(Cache);
1061
1062    // Use a null string or the version string
1063    if (Ver.end() == true)
1064       CandVersion = "";
1065    else
1066       CandVersion = Ver.VerStr();
1067
1068    // Find the current version
1069    CurVersion = "";
1070    if (Pkg->CurrentVer != 0)
1071       CurVersion = Pkg.CurrentVer().VerStr();
1072
1073    // Strip off the epochs for display
1074    CurVersion = StripEpoch(CurVersion);
1075    CandVersion = StripEpoch(CandVersion);
1076
1077    // Figure out if its up or down or equal
1078    Status = Ver.CompareVer(Pkg.CurrentVer());
1079    if (Pkg->CurrentVer == 0 || Pkg->VersionList == 0 || CandidateVer == 0)
1080      Status = 2;
1081 }
1082                                                                         /*}}}*/
1083 // StateCache::StripEpoch - Remove the epoch specifier from the version /*{{{*/
1084 // ---------------------------------------------------------------------
1085 /* */
1086 const char *pkgDepCache::StateCache::StripEpoch(const char *Ver)
1087 {
1088    if (Ver == 0)
1089       return 0;
1090
1091    // Strip any epoch
1092    for (const char *I = Ver; *I != 0; I++)
1093       if (*I == ':')
1094          return I + 1;
1095    return Ver;
1096 }
1097                                                                         /*}}}*/
1098
1099 // Policy::GetCandidateVer - Returns the Candidate install version      /*{{{*/
1100 // ---------------------------------------------------------------------
1101 /* The default just returns the highest available version that is not
1102    a source and automatic. */
1103 pkgCache::VerIterator pkgDepCache::Policy::GetCandidateVer(PkgIterator Pkg)
1104 {
1105    /* Not source/not automatic versions cannot be a candidate version
1106       unless they are already installed */
1107    VerIterator Last(*(pkgCache *)this,0);
1108
1109    for (VerIterator I = Pkg.VersionList(); I.end() == false; I++)
1110    {
1111       if (Pkg.CurrentVer() == I)
1112          return I;
1113
1114       for (VerFileIterator J = I.FileList(); J.end() == false; J++)
1115       {
1116          if ((J.File()->Flags & Flag::NotSource) != 0)
1117             continue;
1118
1119          /* Stash the highest version of a not-automatic source, we use it
1120             if there is nothing better */
1121          if ((J.File()->Flags & Flag::NotAutomatic) != 0)
1122          {
1123             if (Last.end() == true)
1124                Last = I;
1125             continue;
1126          }
1127
1128          return I;
1129       }
1130    }
1131
1132    return Last;
1133 }
1134                                                                         /*}}}*/
1135 // Policy::IsImportantDep - True if the dependency is important         /*{{{*/
1136 // ---------------------------------------------------------------------
1137 /* */
1138 bool pkgDepCache::Policy::IsImportantDep(DepIterator Dep)
1139 {
1140    if(Dep.IsCritical())
1141       return true;
1142    else if(Dep->Type == pkgCache::Dep::Recommends)
1143    {
1144       if ( _config->FindB("APT::Install-Recommends", false))
1145          return true;
1146       // we suport a special mode to only install-recommends for certain
1147       // sections
1148       // FIXME: this is a meant as a temporarly solution until the
1149       //        recommends are cleaned up
1150       string s = _config->Find("APT::Install-Recommends-Section","");
1151       if(s.size() > 0)
1152       {
1153          const char *sec = Dep.TargetPkg().Section();
1154          if (sec && strcmp(sec, s.c_str()) == 0)
1155             return true;
1156       }
1157    }
1158    else if(Dep->Type == pkgCache::Dep::Suggests)
1159      return _config->FindB("APT::Install-Suggests", false);
1160
1161    return false;
1162 }
1163                                                                         /*}}}*/
1164
1165 pkgDepCache::DefaultRootSetFunc::DefaultRootSetFunc()
1166   : constructedSuccessfully(false)
1167 {
1168   Configuration::Item const *Opts;
1169   Opts = _config->Tree("APT::NeverAutoRemove");
1170   if (Opts != 0 && Opts->Child != 0)
1171     {
1172       Opts = Opts->Child;
1173       for (; Opts != 0; Opts = Opts->Next)
1174         {
1175           if (Opts->Value.empty() == true)
1176             continue;
1177
1178           regex_t *p = new regex_t;
1179           if(regcomp(p,Opts->Value.c_str(),
1180                      REG_EXTENDED | REG_ICASE | REG_NOSUB) != 0)
1181             {
1182               regfree(p);
1183               delete p;
1184               _error->Error("Regex compilation error for APT::NeverAutoRemove");
1185               return;
1186             }
1187
1188           rootSetRegexp.push_back(p);
1189         }
1190     }
1191
1192   constructedSuccessfully = true;
1193 }
1194
1195 pkgDepCache::DefaultRootSetFunc::~DefaultRootSetFunc()
1196 {
1197   for(unsigned int i = 0; i < rootSetRegexp.size(); i++)
1198     {
1199       regfree(rootSetRegexp[i]);
1200       delete rootSetRegexp[i];
1201     }
1202 }
1203
1204
1205 bool pkgDepCache::DefaultRootSetFunc::InRootSet(const pkgCache::PkgIterator &pkg)
1206 {
1207    for(unsigned int i = 0; i < rootSetRegexp.size(); i++)
1208       if (regexec(rootSetRegexp[i], pkg.Name(), 0, 0, 0) == 0)
1209          return true;
1210
1211    return false;
1212 }
1213
1214 pkgDepCache::InRootSetFunc *pkgDepCache::GetRootSetFunc()
1215 {
1216   DefaultRootSetFunc *f = new DefaultRootSetFunc;
1217   if(f->wasConstructedSuccessfully())
1218     return f;
1219   else
1220     {
1221       delete f;
1222       return NULL;
1223     }
1224 }
1225
1226 bool pkgDepCache::MarkFollowsRecommends()
1227 {
1228   return _config->FindB("APT::AutoRemove::RecommendsImportant", true);
1229 }
1230
1231 bool pkgDepCache::MarkFollowsSuggests()
1232 {
1233   return _config->FindB("APT::AutoRemove::SuggestsImportant", false);
1234 }
1235
1236 // the main mark algorithm
1237 bool pkgDepCache::MarkRequired(InRootSetFunc &userFunc)
1238 {
1239    bool follow_recommends;
1240    bool follow_suggests;
1241
1242    // init the states
1243    for(PkgIterator p = PkgBegin(); !p.end(); ++p)
1244    {
1245       PkgState[p->ID].Marked  = false;
1246       PkgState[p->ID].Garbage = false;
1247
1248       // debug output
1249       if(_config->FindB("Debug::pkgAutoRemove",false)
1250          && PkgState[p->ID].Flags & Flag::Auto)
1251          std::clog << "AutoDep: " << p.Name() << std::endl;
1252    }
1253
1254    // init vars
1255    follow_recommends = MarkFollowsRecommends();
1256    follow_suggests   = MarkFollowsSuggests();
1257
1258
1259
1260    // do the mark part, this is the core bit of the algorithm
1261    for(PkgIterator p = PkgBegin(); !p.end(); ++p)
1262    {
1263       if(!(PkgState[p->ID].Flags & Flag::Auto) ||
1264           (p->Flags & Flag::Essential) ||
1265           userFunc.InRootSet(p))
1266
1267       {
1268          // the package is installed (and set to keep)
1269          if(PkgState[p->ID].Keep() && !p.CurrentVer().end())
1270             MarkPackage(p, p.CurrentVer(),
1271                         follow_recommends, follow_suggests);
1272          // the package is to be installed
1273          else if(PkgState[p->ID].Install())
1274             MarkPackage(p, PkgState[p->ID].InstVerIter(*this),
1275                         follow_recommends, follow_suggests);
1276       }
1277    }
1278
1279    return true;
1280 }
1281
1282 // mark a single package in Mark-and-Sweep
1283 void pkgDepCache::MarkPackage(const pkgCache::PkgIterator &pkg,
1284                               const pkgCache::VerIterator &ver,
1285                               bool follow_recommends,
1286                               bool follow_suggests)
1287 {
1288    pkgDepCache::StateCache &state = PkgState[pkg->ID];
1289    VerIterator candver            = state.CandidateVerIter(*this);
1290    VerIterator instver            = state.InstVerIter(*this);
1291
1292 #if 0
1293    // If a package was garbage-collected but is now being marked, we
1294    // should re-select it
1295    // For cases when a pkg is set to upgrade and this trigger the
1296    // removal of a no-longer used dependency.  if the pkg is set to
1297    // keep again later it will result in broken deps
1298    if(state.Delete() && state.RemoveReason = Unused)
1299    {
1300       if(ver==candver)
1301          mark_install(pkg, false, false, NULL);
1302       else if(ver==pkg.CurrentVer())
1303          MarkKeep(pkg, false, false);
1304
1305       instver=state.InstVerIter(*this);
1306    }
1307 #endif
1308
1309    // Ignore versions other than the InstVer, and ignore packages
1310    // that are already going to be removed or just left uninstalled.
1311    if(!(ver == instver && !instver.end()))
1312       return;
1313
1314    // if we are marked already we are done
1315    if(state.Marked)
1316       return;
1317
1318    //std::cout << "Setting Marked for: " << pkg.Name() << std::endl;
1319    state.Marked=true;
1320
1321    if(!ver.end())
1322    {
1323      for(DepIterator d = ver.DependsList(); !d.end(); ++d)
1324      {
1325         if(d->Type == Dep::Depends ||
1326            d->Type == Dep::PreDepends ||
1327            (follow_recommends &&
1328             d->Type == Dep::Recommends) ||
1329            (follow_suggests &&
1330             d->Type == Dep::Suggests))
1331         {
1332            // Try all versions of this package.
1333            for(VerIterator V = d.TargetPkg().VersionList();
1334                !V.end(); ++V)
1335            {
1336               if(_system->VS->CheckDep(V.VerStr(), d->CompareOp, d.TargetVer()))
1337               {
1338                  MarkPackage(V.ParentPkg(), V,
1339                              follow_recommends, follow_suggests);
1340               }
1341            }
1342            // Now try virtual packages
1343            for(PrvIterator prv=d.TargetPkg().ProvidesList();
1344                !prv.end(); ++prv)
1345            {
1346               if(_system->VS->CheckDep(prv.ProvideVersion(), d->CompareOp,
1347                                        d.TargetVer()))
1348               {
1349                  MarkPackage(prv.OwnerPkg(), prv.OwnerVer(),
1350                              follow_recommends, follow_suggests);
1351               }
1352            }
1353         }
1354      }
1355    }
1356 }
1357
1358 bool pkgDepCache::Sweep()
1359 {
1360    // do the sweep
1361    for(PkgIterator p=PkgBegin(); !p.end(); ++p)
1362   {
1363      StateCache &state=PkgState[p->ID];
1364
1365      // skip required packages
1366      if (!p.CurrentVer().end() &&
1367          (p.CurrentVer()->Priority == pkgCache::State::Required))
1368         continue;
1369
1370      // if it is not marked and it is installed, it's garbage
1371      if(!state.Marked && (!p.CurrentVer().end() || state.Install()))
1372      {
1373         state.Garbage=true;
1374         if(_config->FindB("Debug::pkgAutoRemove",false))
1375            std::cout << "Garbage: " << p.Name() << std::endl;
1376      }
1377   }
1378
1379    return true;
1380 }