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