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