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