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