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