apt-pkg/depcache.cc

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