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