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