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             // now check if we should consider it a automatic dependency or not
 952             string sec = _config->Find("APT::Never-MarkAuto-Section","");
 953             if(Pkg.Section() && (string(Pkg.Section()) ==  sec))
 954             {
 955                if(_config->FindB("Debug::pkgDepCache::AutoInstall",false) == true)
 956                   std::clog << "Setting NOT as auto-installed because its a direct dep of a package in section " << sec << std::endl;
 957                MarkInstall(InstPkg,true,Depth + 1, true);
 958             }
 959             else
 960             {
 961                // mark automatic dependency
 962                MarkInstall(InstPkg,true,Depth + 1, false, ForceImportantDeps);
 963                // Set the autoflag, after MarkInstall because MarkInstall unsets it
 964                if (P->CurrentVer == 0)
 965                   PkgState[InstPkg->ID].Flags |= Flag::Auto;
 966             }
 967          }
 968          continue;
 969       }
 970
 971       /* For conflicts we just de-install the package and mark as auto,
 972          Conflicts may not have or groups.  For dpkg's Breaks we try to
 973          upgrade the package. */
 974       if (Start->Type == Dep::Conflicts || Start->Type == Dep::Obsoletes ||
 975           Start->Type == Dep::DpkgBreaks)
 976       {
 977          for (Version **I = List; *I != 0; I++)
 978          {
 979             VerIterator Ver(*this,*I);
 980             PkgIterator Pkg = Ver.ParentPkg();
 981
 982             if (Start->Type != Dep::DpkgBreaks)
 983                MarkDelete(Pkg);
 984             else
 985                if (PkgState[Pkg->ID].CandidateVer != *I)
 986                   MarkInstall(Pkg,true,Depth + 1, false, ForceImportantDeps);
 987          }
 988          continue;
 989       }
 990    }
 991 }
 992                                                                         /*}}}*/
 993 // DepCache::SetReInstall - Set the reinstallation flag                 /*{{{*/
 994 // ---------------------------------------------------------------------
 995 /* */
 996 void pkgDepCache::SetReInstall(PkgIterator const &Pkg,bool To)
 997 {
 998    ActionGroup group(*this);
 999
1000    RemoveSizes(Pkg);
1001    RemoveStates(Pkg);
1002
1003    StateCache &P = PkgState[Pkg->ID];
1004    if (To == true)
1005       P.iFlags |= ReInstall;
1006    else
1007       P.iFlags &= ~ReInstall;
1008
1009    AddStates(Pkg);
1010    AddSizes(Pkg);
1011 }
1012                                                                         /*}}}*/
1013 // DepCache::SetCandidateVersion - Change the candidate version         /*{{{*/
1014 // ---------------------------------------------------------------------
1015 /* */
1016 void pkgDepCache::SetCandidateVersion(VerIterator TargetVer)
1017 {
1018    ActionGroup group(*this);
1019
1020    pkgCache::PkgIterator Pkg = TargetVer.ParentPkg();
1021    StateCache &P = PkgState[Pkg->ID];
1022
1023    RemoveSizes(Pkg);
1024    RemoveStates(Pkg);
1025
1026    if (P.CandidateVer == P.InstallVer)
1027       P.InstallVer = (Version *)TargetVer;
1028    P.CandidateVer = (Version *)TargetVer;
1029    P.Update(Pkg,*this);
1030
1031    AddStates(Pkg);
1032    Update(Pkg);
1033    AddSizes(Pkg);
1034 }
1035
1036 void pkgDepCache::MarkAuto(const PkgIterator &Pkg, bool Auto)
1037 {
1038   StateCache &state = PkgState[Pkg->ID];
1039
1040   ActionGroup group(*this);
1041
1042   if(Auto)
1043     state.Flags |= Flag::Auto;
1044   else
1045     state.Flags &= ~Flag::Auto;
1046 }
1047                                                                         /*}}}*/
1048 // StateCache::Update - Compute the various static display things       /*{{{*/
1049 // ---------------------------------------------------------------------
1050 /* This is called whenever the Candidate version changes. */
1051 void pkgDepCache::StateCache::Update(PkgIterator Pkg,pkgCache &Cache)
1052 {
1053    // Some info
1054    VerIterator Ver = CandidateVerIter(Cache);
1055
1056    // Use a null string or the version string
1057    if (Ver.end() == true)
1058       CandVersion = "";
1059    else
1060       CandVersion = Ver.VerStr();
1061
1062    // Find the current version
1063    CurVersion = "";
1064    if (Pkg->CurrentVer != 0)
1065       CurVersion = Pkg.CurrentVer().VerStr();
1066
1067    // Strip off the epochs for display
1068    CurVersion = StripEpoch(CurVersion);
1069    CandVersion = StripEpoch(CandVersion);
1070
1071    // Figure out if its up or down or equal
1072    Status = Ver.CompareVer(Pkg.CurrentVer());
1073    if (Pkg->CurrentVer == 0 || Pkg->VersionList == 0 || CandidateVer == 0)
1074      Status = 2;
1075 }
1076                                                                         /*}}}*/
1077 // StateCache::StripEpoch - Remove the epoch specifier from the version /*{{{*/
1078 // ---------------------------------------------------------------------
1079 /* */
1080 const char *pkgDepCache::StateCache::StripEpoch(const char *Ver)
1081 {
1082    if (Ver == 0)
1083       return 0;
1084
1085    // Strip any epoch
1086    for (const char *I = Ver; *I != 0; I++)
1087       if (*I == ':')
1088          return I + 1;
1089    return Ver;
1090 }
1091                                                                         /*}}}*/
1092
1093 // Policy::GetCandidateVer - Returns the Candidate install version      /*{{{*/
1094 // ---------------------------------------------------------------------
1095 /* The default just returns the highest available version that is not
1096    a source and automatic. */
1097 pkgCache::VerIterator pkgDepCache::Policy::GetCandidateVer(PkgIterator Pkg)
1098 {
1099    /* Not source/not automatic versions cannot be a candidate version
1100       unless they are already installed */
1101    VerIterator Last(*(pkgCache *)this,0);
1102
1103    for (VerIterator I = Pkg.VersionList(); I.end() == false; I++)
1104    {
1105       if (Pkg.CurrentVer() == I)
1106          return I;
1107
1108       for (VerFileIterator J = I.FileList(); J.end() == false; J++)
1109       {
1110          if ((J.File()->Flags & Flag::NotSource) != 0)
1111             continue;
1112
1113          /* Stash the highest version of a not-automatic source, we use it
1114             if there is nothing better */
1115          if ((J.File()->Flags & Flag::NotAutomatic) != 0)
1116          {
1117             if (Last.end() == true)
1118                Last = I;
1119             continue;
1120          }
1121
1122          return I;
1123       }
1124    }
1125
1126    return Last;
1127 }
1128                                                                         /*}}}*/
1129 // Policy::IsImportantDep - True if the dependency is important         /*{{{*/
1130 // ---------------------------------------------------------------------
1131 /* */
1132 bool pkgDepCache::Policy::IsImportantDep(DepIterator Dep)
1133 {
1134    if(Dep.IsCritical())
1135       return true;
1136    else if(Dep->Type == pkgCache::Dep::Recommends)
1137    {
1138       if ( _config->FindB("APT::Install-Recommends", false))
1139          return true;
1140       // we suport a special mode to only install-recommends for certain
1141       // sections
1142       // FIXME: this is a meant as a temporarly solution until the
1143       //        recommends are cleaned up
1144       string s = _config->Find("APT::Install-Recommends-Section","");
1145       if(s.size() > 0)
1146       {
1147          const char *sec = Dep.TargetPkg().Section();
1148          if (sec && strcmp(sec, s.c_str()) == 0)
1149             return true;
1150       }
1151    }
1152    else if(Dep->Type == pkgCache::Dep::Suggests)
1153      return _config->FindB("APT::Install-Suggests", false);
1154
1155    return false;
1156 }
1157                                                                         /*}}}*/
1158
1159 pkgDepCache::DefaultRootSetFunc::DefaultRootSetFunc()
1160   : constructedSuccessfully(false)
1161 {
1162   Configuration::Item const *Opts;
1163   Opts = _config->Tree("APT::NeverAutoRemove");
1164   if (Opts != 0 && Opts->Child != 0)
1165     {
1166       Opts = Opts->Child;
1167       for (; Opts != 0; Opts = Opts->Next)
1168         {
1169           if (Opts->Value.empty() == true)
1170             continue;
1171
1172           regex_t *p = new regex_t;
1173           if(regcomp(p,Opts->Value.c_str(),
1174                      REG_EXTENDED | REG_ICASE | REG_NOSUB) != 0)
1175             {
1176               regfree(p);
1177               delete p;
1178               _error->Error("Regex compilation error for APT::NeverAutoRemove");
1179               return;
1180             }
1181
1182           rootSetRegexp.push_back(p);
1183         }
1184     }
1185
1186   constructedSuccessfully = true;
1187 }
1188
1189 pkgDepCache::DefaultRootSetFunc::~DefaultRootSetFunc()
1190 {
1191   for(unsigned int i = 0; i < rootSetRegexp.size(); i++)
1192     {
1193       regfree(rootSetRegexp[i]);
1194       delete rootSetRegexp[i];
1195     }
1196 }
1197
1198
1199 bool pkgDepCache::DefaultRootSetFunc::InRootSet(const pkgCache::PkgIterator &pkg)
1200 {
1201    for(unsigned int i = 0; i < rootSetRegexp.size(); i++)
1202       if (regexec(rootSetRegexp[i], pkg.Name(), 0, 0, 0) == 0)
1203          return true;
1204
1205    return false;
1206 }
1207
1208 pkgDepCache::InRootSetFunc *pkgDepCache::GetRootSetFunc()
1209 {
1210   DefaultRootSetFunc *f = new DefaultRootSetFunc;
1211   if(f->wasConstructedSuccessfully())
1212     return f;
1213   else
1214     {
1215       delete f;
1216       return NULL;
1217     }
1218 }
1219
1220 bool pkgDepCache::MarkFollowsRecommends()
1221 {
1222   return _config->FindB("APT::AutoRemove::RecommendsImportant", true);
1223 }
1224
1225 bool pkgDepCache::MarkFollowsSuggests()
1226 {
1227   return _config->FindB("APT::AutoRemove::SuggestsImportant", false);
1228 }
1229
1230 // the main mark algorithm
1231 bool pkgDepCache::MarkRequired(InRootSetFunc &userFunc)
1232 {
1233    bool follow_recommends;
1234    bool follow_suggests;
1235
1236    // init the states
1237    for(PkgIterator p = PkgBegin(); !p.end(); ++p)
1238    {
1239       PkgState[p->ID].Marked  = false;
1240       PkgState[p->ID].Garbage = false;
1241
1242       // debug output
1243       if(_config->FindB("Debug::pkgAutoRemove",false)
1244          && PkgState[p->ID].Flags & Flag::Auto)
1245          std::clog << "AutoDep: " << p.Name() << std::endl;
1246    }
1247
1248    // init vars
1249    follow_recommends = MarkFollowsRecommends();
1250    follow_suggests   = MarkFollowsSuggests();
1251
1252
1253
1254    // do the mark part, this is the core bit of the algorithm
1255    for(PkgIterator p = PkgBegin(); !p.end(); ++p)
1256    {
1257       if(!(PkgState[p->ID].Flags & Flag::Auto) ||
1258           (p->Flags & Flag::Essential) ||
1259           userFunc.InRootSet(p))
1260
1261       {
1262          // the package is installed (and set to keep)
1263          if(PkgState[p->ID].Keep() && !p.CurrentVer().end())
1264             MarkPackage(p, p.CurrentVer(),
1265                         follow_recommends, follow_suggests);
1266          // the package is to be installed
1267          else if(PkgState[p->ID].Install())
1268             MarkPackage(p, PkgState[p->ID].InstVerIter(*this),
1269                         follow_recommends, follow_suggests);
1270       }
1271    }
1272
1273    return true;
1274 }
1275
1276 // mark a single package in Mark-and-Sweep
1277 void pkgDepCache::MarkPackage(const pkgCache::PkgIterator &pkg,
1278                               const pkgCache::VerIterator &ver,
1279                               bool follow_recommends,
1280                               bool follow_suggests)
1281 {
1282    pkgDepCache::StateCache &state = PkgState[pkg->ID];
1283    VerIterator candver            = state.CandidateVerIter(*this);
1284    VerIterator instver            = state.InstVerIter(*this);
1285
1286 #if 0
1287    // If a package was garbage-collected but is now being marked, we
1288    // should re-select it
1289    // For cases when a pkg is set to upgrade and this trigger the
1290    // removal of a no-longer used dependency.  if the pkg is set to
1291    // keep again later it will result in broken deps
1292    if(state.Delete() && state.RemoveReason = Unused)
1293    {
1294       if(ver==candver)
1295          mark_install(pkg, false, false, NULL);
1296       else if(ver==pkg.CurrentVer())
1297          MarkKeep(pkg, false, false);
1298
1299       instver=state.InstVerIter(*this);
1300    }
1301 #endif
1302
1303    // Ignore versions other than the InstVer, and ignore packages
1304    // that are already going to be removed or just left uninstalled.
1305    if(!(ver == instver && !instver.end()))
1306       return;
1307
1308    // if we are marked already we are done
1309    if(state.Marked)
1310       return;
1311
1312    //std::cout << "Setting Marked for: " << pkg.Name() << std::endl;
1313    state.Marked=true;
1314
1315    if(!ver.end())
1316    {
1317      for(DepIterator d = ver.DependsList(); !d.end(); ++d)
1318      {
1319         if(d->Type == Dep::Depends ||
1320            d->Type == Dep::PreDepends ||
1321            (follow_recommends &&
1322             d->Type == Dep::Recommends) ||
1323            (follow_suggests &&
1324             d->Type == Dep::Suggests))
1325         {
1326            // Try all versions of this package.
1327            for(VerIterator V = d.TargetPkg().VersionList();
1328                !V.end(); ++V)
1329            {
1330               if(_system->VS->CheckDep(V.VerStr(), d->CompareOp, d.TargetVer()))
1331               {
1332                  MarkPackage(V.ParentPkg(), V,
1333                              follow_recommends, follow_suggests);
1334               }
1335            }
1336            // Now try virtual packages
1337            for(PrvIterator prv=d.TargetPkg().ProvidesList();
1338                !prv.end(); ++prv)
1339            {
1340               if(_system->VS->CheckDep(prv.ProvideVersion(), d->CompareOp,
1341                                        d.TargetVer()))
1342               {
1343                  MarkPackage(prv.OwnerPkg(), prv.OwnerVer(),
1344                              follow_recommends, follow_suggests);
1345               }
1346            }
1347         }
1348      }
1349    }
1350 }
1351
1352 bool pkgDepCache::Sweep()
1353 {
1354    // do the sweep
1355    for(PkgIterator p=PkgBegin(); !p.end(); ++p)
1356   {
1357      StateCache &state=PkgState[p->ID];
1358
1359      // skip required packages
1360      if (!p.CurrentVer().end() &&
1361          (p.CurrentVer()->Priority == pkgCache::State::Required))
1362         continue;
1363
1364      // if it is not marked and it is installed, it's garbage
1365      if(!state.Marked && (!p.CurrentVer().end() || state.Install()))
1366      {
1367         state.Garbage=true;
1368         if(_config->FindB("Debug::pkgAutoRemove",false))
1369            std::cout << "Garbage: " << p.Name() << std::endl;
1370      }
1371   }
1372
1373    return true;
1374 }