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 Critical) were added
 899        * since we installed the package.  Also check for deps that
 900        * were satisfied in the past: for instance, if a version
 901        * restriction in a Recommends was tightened, upgrading the
 902        * package should follow that Recommends rather than causing the
 903        * dependency to be removed. (bug #470115)
 904        */
 905       bool isNewImportantDep = false;
 906       bool isPreviouslySatisfiedImportantDep = false;
 907       if(!ForceImportantDeps && !Start.IsCritical())
 908       {
 909          bool found=false;
 910          VerIterator instVer = Pkg.CurrentVer();
 911          if(!instVer.end())
 912          {
 913            for (DepIterator D = instVer.DependsList(); D.end() != true; D++)
 914              {
 915                //FIXME: deal better with or-groups(?)
 916                DepIterator LocalStart = D;
 917
 918                if(IsImportantDep(D) && !D.IsCritical() &&
 919                   Start.TargetPkg() == D.TargetPkg())
 920                  {
 921                    if(!isPreviouslySatisfiedImportantDep)
 922                      {
 923                        DepIterator D2 = D;
 924                        while((D2->CompareOp & Dep::Or) != 0)
 925                          ++D2;
 926
 927                        isPreviouslySatisfiedImportantDep =
 928                          (((*this)[D2] & DepGNow) != 0);
 929                      }
 930
 931                    found=true;
 932                  }
 933              }
 934             // this is a new dep if it was not found to be already
 935             // a important dep of the installed pacakge
 936             isNewImportantDep = !found;
 937          }
 938       }
 939       if(isNewImportantDep)
 940          if(_config->FindB("Debug::pkgDepCache::AutoInstall",false) == true)
 941             std::clog << "new important dependency: "
 942                       << Start.TargetPkg().Name() << std::endl;
 943       if(isPreviouslySatisfiedImportantDep)
 944         if(_config->FindB("Debug::pkgDepCache::AutoInstall", false) == true)
 945           std::clog << "previously satisfied important dependency on "
 946                     << Start.TargetPkg().Name() << std::endl;
 947
 948       // skip important deps if the package is already installed
 949       if (Pkg->CurrentVer != 0 && Start.IsCritical() == false
 950           && !isNewImportantDep && !isPreviouslySatisfiedImportantDep
 951           && !ForceImportantDeps)
 952          continue;
 953
 954       /* If we are in an or group locate the first or that can
 955          succeed. We have already cached this.. */
 956       for (; Ors > 1 && (DepState[Start->ID] & DepCVer) != DepCVer; Ors--)
 957          Start++;
 958
 959       /* This bit is for processing the possibilty of an install/upgrade
 960          fixing the problem */
 961       SPtrArray<Version *> List = Start.AllTargets();
 962       if (Start->Type != Dep::DpkgBreaks &&
 963           (DepState[Start->ID] & DepCVer) == DepCVer)
 964       {
 965          // Right, find the best version to install..
 966          Version **Cur = List;
 967          PkgIterator P = Start.TargetPkg();
 968          PkgIterator InstPkg(*Cache,0);
 969
 970          // See if there are direct matches (at the start of the list)
 971          for (; *Cur != 0 && (*Cur)->ParentPkg == P.Index(); Cur++)
 972          {
 973             PkgIterator Pkg(*Cache,Cache->PkgP + (*Cur)->ParentPkg);
 974             if (PkgState[Pkg->ID].CandidateVer != *Cur)
 975                continue;
 976             InstPkg = Pkg;
 977             break;
 978          }
 979
 980          // Select the highest priority providing package
 981          if (InstPkg.end() == true)
 982          {
 983             pkgPrioSortList(*Cache,Cur);
 984             for (; *Cur != 0; Cur++)
 985             {
 986                PkgIterator Pkg(*Cache,Cache->PkgP + (*Cur)->ParentPkg);
 987                if (PkgState[Pkg->ID].CandidateVer != *Cur)
 988                   continue;
 989                InstPkg = Pkg;
 990                break;
 991             }
 992          }
 993
 994          if (InstPkg.end() == false)
 995          {
 996             if(_config->FindB("Debug::pkgDepCache::AutoInstall",false) == true)
 997                std::clog << "Installing " << InstPkg.Name()
 998                          << " as dep of " << Pkg.Name()
 999                          << std::endl;
1000             // now check if we should consider it a automatic dependency or not
1001             if(Pkg.Section() && ConfigValueInSubTree("APT::Never-MarkAuto-Sections", Pkg.Section()))
1002             {
1003                if(_config->FindB("Debug::pkgDepCache::AutoInstall",false) == true)
1004                   std::clog << "Setting NOT as auto-installed (direct dep of pkg in APT::Never-MarkAuto-Section)" << std::endl;
1005                MarkInstall(InstPkg,true,Depth + 1, true);
1006             }
1007             else
1008             {
1009                // mark automatic dependency
1010                MarkInstall(InstPkg,true,Depth + 1, false, ForceImportantDeps);
1011                // Set the autoflag, after MarkInstall because MarkInstall unsets it
1012                if (P->CurrentVer == 0)
1013                   PkgState[InstPkg->ID].Flags |= Flag::Auto;
1014             }
1015          }
1016          continue;
1017       }
1018
1019       /* For conflicts we just de-install the package and mark as auto,
1020          Conflicts may not have or groups.  For dpkg's Breaks we try to
1021          upgrade the package. */
1022       if (Start->Type == Dep::Conflicts || Start->Type == Dep::Obsoletes ||
1023           Start->Type == Dep::DpkgBreaks)
1024       {
1025          for (Version **I = List; *I != 0; I++)
1026          {
1027             VerIterator Ver(*this,*I);
1028             PkgIterator Pkg = Ver.ParentPkg();
1029
1030             if (Start->Type != Dep::DpkgBreaks)
1031                MarkDelete(Pkg);
1032             else
1033                if (PkgState[Pkg->ID].CandidateVer != *I)
1034                   MarkInstall(Pkg,true,Depth + 1, false, ForceImportantDeps);
1035          }
1036          continue;
1037       }
1038    }
1039 }
1040                                                                         /*}}}*/
1041 // DepCache::SetReInstall - Set the reinstallation flag                 /*{{{*/
1042 // ---------------------------------------------------------------------
1043 /* */
1044 void pkgDepCache::SetReInstall(PkgIterator const &Pkg,bool To)
1045 {
1046    ActionGroup group(*this);
1047
1048    RemoveSizes(Pkg);
1049    RemoveStates(Pkg);
1050
1051    StateCache &P = PkgState[Pkg->ID];
1052    if (To == true)
1053       P.iFlags |= ReInstall;
1054    else
1055       P.iFlags &= ~ReInstall;
1056
1057    AddStates(Pkg);
1058    AddSizes(Pkg);
1059 }
1060                                                                         /*}}}*/
1061 // DepCache::SetCandidateVersion - Change the candidate version         /*{{{*/
1062 // ---------------------------------------------------------------------
1063 /* */
1064 void pkgDepCache::SetCandidateVersion(VerIterator TargetVer)
1065 {
1066    ActionGroup group(*this);
1067
1068    pkgCache::PkgIterator Pkg = TargetVer.ParentPkg();
1069    StateCache &P = PkgState[Pkg->ID];
1070
1071    RemoveSizes(Pkg);
1072    RemoveStates(Pkg);
1073
1074    if (P.CandidateVer == P.InstallVer)
1075       P.InstallVer = (Version *)TargetVer;
1076    P.CandidateVer = (Version *)TargetVer;
1077    P.Update(Pkg,*this);
1078
1079    AddStates(Pkg);
1080    Update(Pkg);
1081    AddSizes(Pkg);
1082 }
1083
1084 void pkgDepCache::MarkAuto(const PkgIterator &Pkg, bool Auto)
1085 {
1086   StateCache &state = PkgState[Pkg->ID];
1087
1088   ActionGroup group(*this);
1089
1090   if(Auto)
1091     state.Flags |= Flag::Auto;
1092   else
1093     state.Flags &= ~Flag::Auto;
1094 }
1095                                                                         /*}}}*/
1096 // StateCache::Update - Compute the various static display things       /*{{{*/
1097 // ---------------------------------------------------------------------
1098 /* This is called whenever the Candidate version changes. */
1099 void pkgDepCache::StateCache::Update(PkgIterator Pkg,pkgCache &Cache)
1100 {
1101    // Some info
1102    VerIterator Ver = CandidateVerIter(Cache);
1103
1104    // Use a null string or the version string
1105    if (Ver.end() == true)
1106       CandVersion = "";
1107    else
1108       CandVersion = Ver.VerStr();
1109
1110    // Find the current version
1111    CurVersion = "";
1112    if (Pkg->CurrentVer != 0)
1113       CurVersion = Pkg.CurrentVer().VerStr();
1114
1115    // Strip off the epochs for display
1116    CurVersion = StripEpoch(CurVersion);
1117    CandVersion = StripEpoch(CandVersion);
1118
1119    // Figure out if its up or down or equal
1120    Status = Ver.CompareVer(Pkg.CurrentVer());
1121    if (Pkg->CurrentVer == 0 || Pkg->VersionList == 0 || CandidateVer == 0)
1122      Status = 2;
1123 }
1124                                                                         /*}}}*/
1125 // StateCache::StripEpoch - Remove the epoch specifier from the version /*{{{*/
1126 // ---------------------------------------------------------------------
1127 /* */
1128 const char *pkgDepCache::StateCache::StripEpoch(const char *Ver)
1129 {
1130    if (Ver == 0)
1131       return 0;
1132
1133    // Strip any epoch
1134    for (const char *I = Ver; *I != 0; I++)
1135       if (*I == ':')
1136          return I + 1;
1137    return Ver;
1138 }
1139                                                                         /*}}}*/
1140
1141 // Policy::GetCandidateVer - Returns the Candidate install version      /*{{{*/
1142 // ---------------------------------------------------------------------
1143 /* The default just returns the highest available version that is not
1144    a source and automatic. */
1145 pkgCache::VerIterator pkgDepCache::Policy::GetCandidateVer(PkgIterator Pkg)
1146 {
1147    /* Not source/not automatic versions cannot be a candidate version
1148       unless they are already installed */
1149    VerIterator Last(*(pkgCache *)this,0);
1150
1151    for (VerIterator I = Pkg.VersionList(); I.end() == false; I++)
1152    {
1153       if (Pkg.CurrentVer() == I)
1154          return I;
1155
1156       for (VerFileIterator J = I.FileList(); J.end() == false; J++)
1157       {
1158          if ((J.File()->Flags & Flag::NotSource) != 0)
1159             continue;
1160
1161          /* Stash the highest version of a not-automatic source, we use it
1162             if there is nothing better */
1163          if ((J.File()->Flags & Flag::NotAutomatic) != 0)
1164          {
1165             if (Last.end() == true)
1166                Last = I;
1167             continue;
1168          }
1169
1170          return I;
1171       }
1172    }
1173
1174    return Last;
1175 }
1176                                                                         /*}}}*/
1177
1178 // Policy::IsImportantDep - True if the dependency is important         /*{{{*/
1179 // ---------------------------------------------------------------------
1180 /* */
1181 bool pkgDepCache::Policy::IsImportantDep(DepIterator Dep)
1182 {
1183    if(Dep.IsCritical())
1184       return true;
1185    else if(Dep->Type == pkgCache::Dep::Recommends)
1186    {
1187       if ( _config->FindB("APT::Install-Recommends", false))
1188          return true;
1189       // we suport a special mode to only install-recommends for certain
1190       // sections
1191       // FIXME: this is a meant as a temporarly solution until the
1192       //        recommends are cleaned up
1193       const char *sec = Dep.ParentVer().Section();
1194       if (sec && ConfigValueInSubTree("APT::Install-Recommends-Sections", sec))
1195          return true;
1196    }
1197    else if(Dep->Type == pkgCache::Dep::Suggests)
1198      return _config->FindB("APT::Install-Suggests", false);
1199
1200    return false;
1201 }
1202                                                                         /*}}}*/
1203
1204 pkgDepCache::DefaultRootSetFunc::DefaultRootSetFunc()
1205   : constructedSuccessfully(false)
1206 {
1207   Configuration::Item const *Opts;
1208   Opts = _config->Tree("APT::NeverAutoRemove");
1209   if (Opts != 0 && Opts->Child != 0)
1210     {
1211       Opts = Opts->Child;
1212       for (; Opts != 0; Opts = Opts->Next)
1213         {
1214           if (Opts->Value.empty() == true)
1215             continue;
1216
1217           regex_t *p = new regex_t;
1218           if(regcomp(p,Opts->Value.c_str(),
1219                      REG_EXTENDED | REG_ICASE | REG_NOSUB) != 0)
1220             {
1221               regfree(p);
1222               delete p;
1223               _error->Error("Regex compilation error for APT::NeverAutoRemove");
1224               return;
1225             }
1226
1227           rootSetRegexp.push_back(p);
1228         }
1229     }
1230
1231   constructedSuccessfully = true;
1232 }
1233
1234 pkgDepCache::DefaultRootSetFunc::~DefaultRootSetFunc()
1235 {
1236   for(unsigned int i = 0; i < rootSetRegexp.size(); i++)
1237     {
1238       regfree(rootSetRegexp[i]);
1239       delete rootSetRegexp[i];
1240     }
1241 }
1242
1243
1244 bool pkgDepCache::DefaultRootSetFunc::InRootSet(const pkgCache::PkgIterator &pkg)
1245 {
1246    for(unsigned int i = 0; i < rootSetRegexp.size(); i++)
1247       if (regexec(rootSetRegexp[i], pkg.Name(), 0, 0, 0) == 0)
1248          return true;
1249
1250    return false;
1251 }
1252
1253 pkgDepCache::InRootSetFunc *pkgDepCache::GetRootSetFunc()
1254 {
1255   DefaultRootSetFunc *f = new DefaultRootSetFunc;
1256   if(f->wasConstructedSuccessfully())
1257     return f;
1258   else
1259     {
1260       delete f;
1261       return NULL;
1262     }
1263 }
1264
1265 bool pkgDepCache::MarkFollowsRecommends()
1266 {
1267   return _config->FindB("APT::AutoRemove::RecommendsImportant", true);
1268 }
1269
1270 bool pkgDepCache::MarkFollowsSuggests()
1271 {
1272   return _config->FindB("APT::AutoRemove::SuggestsImportant", false);
1273 }
1274
1275 // the main mark algorithm
1276 bool pkgDepCache::MarkRequired(InRootSetFunc &userFunc)
1277 {
1278    bool follow_recommends;
1279    bool follow_suggests;
1280
1281    // init the states
1282    for(PkgIterator p = PkgBegin(); !p.end(); ++p)
1283    {
1284       PkgState[p->ID].Marked  = false;
1285       PkgState[p->ID].Garbage = false;
1286
1287       // debug output
1288       if(_config->FindB("Debug::pkgAutoRemove",false)
1289          && PkgState[p->ID].Flags & Flag::Auto)
1290          std::clog << "AutoDep: " << p.Name() << std::endl;
1291    }
1292
1293    // init vars
1294    follow_recommends = MarkFollowsRecommends();
1295    follow_suggests   = MarkFollowsSuggests();
1296
1297
1298
1299    // do the mark part, this is the core bit of the algorithm
1300    for(PkgIterator p = PkgBegin(); !p.end(); ++p)
1301    {
1302       if(!(PkgState[p->ID].Flags & Flag::Auto) ||
1303           (p->Flags & Flag::Essential) ||
1304           userFunc.InRootSet(p))
1305
1306       {
1307          // the package is installed (and set to keep)
1308          if(PkgState[p->ID].Keep() && !p.CurrentVer().end())
1309             MarkPackage(p, p.CurrentVer(),
1310                         follow_recommends, follow_suggests);
1311          // the package is to be installed
1312          else if(PkgState[p->ID].Install())
1313             MarkPackage(p, PkgState[p->ID].InstVerIter(*this),
1314                         follow_recommends, follow_suggests);
1315       }
1316    }
1317
1318    return true;
1319 }
1320
1321 // mark a single package in Mark-and-Sweep
1322 void pkgDepCache::MarkPackage(const pkgCache::PkgIterator &pkg,
1323                               const pkgCache::VerIterator &ver,
1324                               bool follow_recommends,
1325                               bool follow_suggests)
1326 {
1327    pkgDepCache::StateCache &state = PkgState[pkg->ID];
1328    VerIterator currver            = pkg.CurrentVer();
1329    VerIterator candver            = state.CandidateVerIter(*this);
1330    VerIterator instver            = state.InstVerIter(*this);
1331
1332 #if 0
1333    // If a package was garbage-collected but is now being marked, we
1334    // should re-select it
1335    // For cases when a pkg is set to upgrade and this trigger the
1336    // removal of a no-longer used dependency.  if the pkg is set to
1337    // keep again later it will result in broken deps
1338    if(state.Delete() && state.RemoveReason = Unused)
1339    {
1340       if(ver==candver)
1341          mark_install(pkg, false, false, NULL);
1342       else if(ver==pkg.CurrentVer())
1343          MarkKeep(pkg, false, false);
1344
1345       instver=state.InstVerIter(*this);
1346    }
1347 #endif
1348
1349    // For packages that are not going to be removed, ignore versions
1350    // other than the InstVer.  For packages that are going to be
1351    // removed, ignore versions other than the current version.
1352    if(!(ver == instver && !instver.end()) &&
1353       !(ver == currver && instver.end() && !ver.end()))
1354       return;
1355
1356    // if we are marked already we are done
1357    if(state.Marked)
1358       return;
1359
1360    if(_config->FindB("Debug::pkgAutoRemove",false))
1361      {
1362        std::clog << "Marking: " << pkg.Name();
1363        if(!ver.end())
1364          std::clog << " " << ver.VerStr();
1365        if(!currver.end())
1366          std::clog << ", Curr=" << currver.VerStr();
1367        if(!instver.end())
1368          std::clog << ", Inst=" << instver.VerStr();
1369        std::clog << std::endl;
1370      }
1371
1372    state.Marked=true;
1373
1374    if(!ver.end())
1375    {
1376      for(DepIterator d = ver.DependsList(); !d.end(); ++d)
1377      {
1378         if(d->Type == Dep::Depends ||
1379            d->Type == Dep::PreDepends ||
1380            (follow_recommends &&
1381             d->Type == Dep::Recommends) ||
1382            (follow_suggests &&
1383             d->Type == Dep::Suggests))
1384         {
1385            // Try all versions of this package.
1386            for(VerIterator V = d.TargetPkg().VersionList();
1387                !V.end(); ++V)
1388            {
1389               if(_system->VS->CheckDep(V.VerStr(), d->CompareOp, d.TargetVer()))
1390               {
1391                 if(_config->FindB("Debug::pkgAutoRemove",false))
1392                   {
1393                     std::clog << "Following dep: " << d.ParentPkg().Name()
1394                               << " " << d.ParentVer().VerStr() << " "
1395                               << d.DepType() << " "
1396                               << d.TargetPkg().Name();
1397                     if((d->CompareOp & ~pkgCache::Dep::Or) != pkgCache::Dep::NoOp)
1398                       {
1399                         std::clog << " (" << d.CompType() << " "
1400                                   << d.TargetVer() << ")";
1401                       }
1402                     std::clog << std::endl;
1403                   }
1404                  MarkPackage(V.ParentPkg(), V,
1405                              follow_recommends, follow_suggests);
1406               }
1407            }
1408            // Now try virtual packages
1409            for(PrvIterator prv=d.TargetPkg().ProvidesList();
1410                !prv.end(); ++prv)
1411            {
1412               if(_system->VS->CheckDep(prv.ProvideVersion(), d->CompareOp,
1413                                        d.TargetVer()))
1414               {
1415                 if(_config->FindB("Debug::pkgAutoRemove",false))
1416                   {
1417                     std::clog << "Following dep: " << d.ParentPkg().Name()
1418                               << " " << d.ParentVer().VerStr() << " "
1419                               << d.DepType() << " "
1420                               << d.TargetPkg().Name();
1421                     if((d->CompareOp & ~pkgCache::Dep::Or) != pkgCache::Dep::NoOp)
1422                       {
1423                         std::clog << " (" << d.CompType() << " "
1424                                   << d.TargetVer() << ")";
1425                       }
1426                     std::clog << ", provided by "
1427                               << prv.OwnerPkg().Name() << " "
1428                               << prv.OwnerVer().VerStr()
1429                               << std::endl;
1430                   }
1431
1432                  MarkPackage(prv.OwnerPkg(), prv.OwnerVer(),
1433                              follow_recommends, follow_suggests);
1434               }
1435            }
1436         }
1437      }
1438    }
1439 }
1440
1441 bool pkgDepCache::Sweep()
1442 {
1443    // do the sweep
1444    for(PkgIterator p=PkgBegin(); !p.end(); ++p)
1445   {
1446      StateCache &state=PkgState[p->ID];
1447
1448      // skip required packages
1449      if (!p.CurrentVer().end() &&
1450          (p.CurrentVer()->Priority == pkgCache::State::Required))
1451         continue;
1452
1453      // if it is not marked and it is installed, it's garbage
1454      if(!state.Marked && (!p.CurrentVer().end() || state.Install()))
1455      {
1456         state.Garbage=true;
1457         if(_config->FindB("Debug::pkgAutoRemove",false))
1458            std::cout << "Garbage: " << p.Name() << std::endl;
1459      }
1460   }
1461
1462    return true;
1463 }