apt-pkg/depcache.cc.orig

   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 static bool DebugMarker;
  84 static bool DebugAutoInstall;
  85
  86 pkgDepCache::pkgDepCache(pkgCache *pCache,Policy *Plcy) :
  87   group_level(0), Cache(pCache), PkgState(0), DepState(0)
  88 {
  89    DebugMarker = _config->FindB("Debug::pkgDepCache::Marker", false);
  90    DebugAutoInstall = _config->FindB("Debug::pkgDepCache::AutoInstall", false);
  91    delLocalPolicy = 0;
  92    LocalPolicy = Plcy;
  93    if (LocalPolicy == 0)
  94       delLocalPolicy = LocalPolicy = new Policy;
  95 }
  96                                                                         /*}}}*/
  97 // DepCache::~pkgDepCache - Destructor                                  /*{{{*/
  98 // ---------------------------------------------------------------------
  99 /* */
 100 pkgDepCache::~pkgDepCache()
 101 {
 102    delete [] PkgState;
 103    delete [] DepState;
 104    delete delLocalPolicy;
 105 }
 106                                                                         /*}}}*/
 107 // DepCache::Init - Generate the initial extra structures.              /*{{{*/
 108 // ---------------------------------------------------------------------
 109 /* This allocats the extension buffers and initializes them. */
 110 bool pkgDepCache::Init(OpProgress *Prog)
 111 {
 112    // Suppress mark updates during this operation (just in case) and
 113    // run a mark operation when Init terminates.
 114    ActionGroup actions(*this);
 115
 116    delete [] PkgState;
 117    delete [] DepState;
 118    PkgState = new StateCache[Head().PackageCount];
 119    DepState = new unsigned char[Head().DependsCount];
 120    memset(PkgState,0,sizeof(*PkgState)*Head().PackageCount);
 121    memset(DepState,0,sizeof(*DepState)*Head().DependsCount);
 122
 123    if (Prog != 0)
 124    {
 125       Prog->OverallProgress(0,2*Head().PackageCount,Head().PackageCount,
 126                             _("Building dependency tree"));
 127       Prog->SubProgress(Head().PackageCount,_("Candidate versions"));
 128    }
 129
 130    /* Set the current state of everything. In this state all of the
 131       packages are kept exactly as is. See AllUpgrade */
 132    int Done = 0;
 133    for (PkgIterator I = PkgBegin(); I.end() != true; I++,Done++)
 134    {
 135       if (Prog != 0 && Done%20 == 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 existing 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    for (PkgIterator I = PkgBegin(); I.end() != true; I++,Done++)
 619    {
 620       if (Prog != 0 && Done%20 == 0)
 621          Prog->Progress(Done);
 622       for (VerIterator V = I.VersionList(); V.end() != true; V++)
 623       {
 624          unsigned char Group = 0;
 625
 626          for (DepIterator D = V.DependsList(); D.end() != true; D++)
 627          {
 628             // Build the dependency state.
 629             unsigned char &State = DepState[D->ID];
 630             State = DependencyState(D);
 631
 632             // Add to the group if we are within an or..
 633             Group |= State;
 634             State |= Group << 3;
 635             if ((D->CompareOp & Dep::Or) != Dep::Or)
 636                Group = 0;
 637
 638             // Invert for Conflicts
 639             if (D->Type == Dep::Conflicts ||
 640                 D->Type == Dep::DpkgBreaks ||
 641                 D->Type == Dep::Obsoletes)
 642                State = ~State;
 643          }
 644       }
 645
 646       // Compute the pacakge dependency state and size additions
 647       AddSizes(I);
 648       UpdateVerState(I);
 649       AddStates(I);
 650    }
 651
 652    if (Prog != 0)
 653       Prog->Progress(Done);
 654
 655    readStateFile(Prog);
 656 }
 657                                                                         /*}}}*/
 658 // DepCache::Update - Update the deps list of a package                 /*{{{*/
 659 // ---------------------------------------------------------------------
 660 /* This is a helper for update that only does the dep portion of the scan.
 661    It is mainly meant to scan reverse dependencies. */
 662 void pkgDepCache::Update(DepIterator D)
 663 {
 664    // Update the reverse deps
 665    for (;D.end() != true; D++)
 666    {
 667       unsigned char &State = DepState[D->ID];
 668       State = DependencyState(D);
 669
 670       // Invert for Conflicts
 671       if (D->Type == Dep::Conflicts ||
 672           D->Type == Dep::DpkgBreaks ||
 673           D->Type == Dep::Obsoletes)
 674          State = ~State;
 675
 676       RemoveStates(D.ParentPkg());
 677       BuildGroupOrs(D.ParentVer());
 678       UpdateVerState(D.ParentPkg());
 679       AddStates(D.ParentPkg());
 680    }
 681 }
 682                                                                         /*}}}*/
 683 // DepCache::Update - Update the related deps of a package              /*{{{*/
 684 // ---------------------------------------------------------------------
 685 /* This is called whenever the state of a package changes. It updates
 686    all cached dependencies related to this package. */
 687 void pkgDepCache::Update(PkgIterator const &Pkg)
 688 {
 689    // Recompute the dep of the package
 690    RemoveStates(Pkg);
 691    UpdateVerState(Pkg);
 692    AddStates(Pkg);
 693
 694    // Update the reverse deps
 695    Update(Pkg.RevDependsList());
 696
 697    // Update the provides map for the current ver
 698    if (Pkg->CurrentVer != 0)
 699       for (PrvIterator P = Pkg.CurrentVer().ProvidesList();
 700            P.end() != true; P++)
 701          Update(P.ParentPkg().RevDependsList());
 702
 703    // Update the provides map for the candidate ver
 704    if (PkgState[Pkg->ID].CandidateVer != 0)
 705       for (PrvIterator P = PkgState[Pkg->ID].CandidateVerIter(*this).ProvidesList();
 706            P.end() != true; P++)
 707          Update(P.ParentPkg().RevDependsList());
 708 }
 709                                                                         /*}}}*/
 710 // DepCache::MarkKeep - Put the package in the keep state               /*{{{*/
 711 // ---------------------------------------------------------------------
 712 /* */
 713 void pkgDepCache::MarkKeep(PkgIterator const &Pkg, bool Soft, bool FromUser,
 714                            unsigned long Depth)
 715 {
 716    // Simplifies other routines.
 717    if (Pkg.end() == true)
 718       return;
 719
 720    /* Reject an attempt to keep a non-source broken installed package, those
 721       must be upgraded */
 722    if (Pkg.State() == PkgIterator::NeedsUnpack &&
 723        Pkg.CurrentVer().Downloadable() == false)
 724       return;
 725
 726    /** \todo Can this be moved later in the method? */
 727    ActionGroup group(*this);
 728
 729    /* We changed the soft state all the time so the UI is a bit nicer
 730       to use */
 731    StateCache &P = PkgState[Pkg->ID];
 732    if (Soft == true)
 733       P.iFlags |= AutoKept;
 734    else
 735       P.iFlags &= ~AutoKept;
 736
 737    // Check that it is not already kept
 738    if (P.Mode == ModeKeep)
 739       return;
 740
 741    // We dont even try to keep virtual packages..
 742    if (Pkg->VersionList == 0)
 743       return;
 744 #if 0 // reseting the autoflag here means we lose the
 745       // auto-mark information if a user selects a package for removal
 746       // but changes  his mind then and sets it for keep again
 747       // - this makes sense as default when all Garbage dependencies
 748       //   are automatically marked for removal (as aptitude does).
 749       //   setting a package for keep then makes it no longer autoinstalled
 750       //   for all other use-case this action is rather suprising
 751    if(FromUser && !P.Marked)
 752      P.Flags &= ~Flag::Auto;
 753 #endif
 754
 755    if (DebugMarker == true)
 756       std::clog << OutputInDepth(Depth) << "MarkKeep " << Pkg << " FU=" << FromUser << std::endl;
 757
 758    RemoveSizes(Pkg);
 759    RemoveStates(Pkg);
 760
 761    P.Mode = ModeKeep;
 762    if (Pkg->CurrentVer == 0)
 763       P.InstallVer = 0;
 764    else
 765       P.InstallVer = Pkg.CurrentVer();
 766
 767    AddStates(Pkg);
 768
 769    Update(Pkg);
 770
 771    AddSizes(Pkg);
 772 }
 773                                                                         /*}}}*/
 774 // DepCache::MarkDelete - Put the package in the delete state           /*{{{*/
 775 // ---------------------------------------------------------------------
 776 /* */
 777 void pkgDepCache::MarkDelete(PkgIterator const &Pkg, bool Purge) {
 778    MarkDelete(Pkg, Purge, 0);
 779 }
 780
 781 void pkgDepCache::MarkDelete(PkgIterator const &Pkg, bool rPurge,
 782                              unsigned long Depth, bool FromUser)
 783 {
 784    // Simplifies other routines.
 785    if (Pkg.end() == true)
 786       return;
 787
 788    ActionGroup group(*this);
 789
 790    // Check that it is not already marked for delete
 791    StateCache &P = PkgState[Pkg->ID];
 792    P.iFlags &= ~(AutoKept | Purge);
 793    if (rPurge == true)
 794       P.iFlags |= Purge;
 795
 796    if ((P.Mode == ModeDelete || P.InstallVer == 0) &&
 797        (Pkg.Purge() == true || rPurge == false))
 798       return;
 799
 800    // We dont even try to delete virtual packages..
 801    if (Pkg->VersionList == 0)
 802       return;
 803
 804    // check if we are allowed to install the package
 805    if (IsDeleteOk(Pkg,rPurge,Depth,FromUser) == false)
 806       return;
 807
 808    if (DebugMarker == true)
 809       std::clog << OutputInDepth(Depth) << "MarkDelete " << Pkg << " FU=" << FromUser << std::endl;
 810
 811    RemoveSizes(Pkg);
 812    RemoveStates(Pkg);
 813
 814    if (Pkg->CurrentVer == 0 && (Pkg.Purge() == true || rPurge == false))
 815       P.Mode = ModeKeep;
 816    else
 817       P.Mode = ModeDelete;
 818    P.InstallVer = 0;
 819
 820    AddStates(Pkg);
 821    Update(Pkg);
 822    AddSizes(Pkg);
 823 }
 824                                                                         /*}}}*/
 825 // DepCache::IsDeleteOk - check if it is ok to remove this package      /*{{{*/
 826 // ---------------------------------------------------------------------
 827 /* The default implementation just honors dpkg hold
 828    But an application using this library can override this method
 829    to control the MarkDelete behaviour */
 830 bool pkgDepCache::IsDeleteOk(PkgIterator const &Pkg,bool rPurge,
 831                               unsigned long Depth, bool FromUser)
 832 {
 833    if (FromUser == false && Pkg->SelectedState == pkgCache::State::Hold && _config->FindB("APT::Ignore-Hold",false) == false)
 834    {
 835       if (DebugMarker == true)
 836          std::clog << OutputInDepth(Depth) << "Hold prevents MarkDelete of " << Pkg << " FU=" << FromUser << std::endl;
 837       return false;
 838    }
 839    return true;
 840 }
 841                                                                         /*}}}*/
 842 // DepCache::MarkInstall - Put the package in the install state         /*{{{*/
 843 // ---------------------------------------------------------------------
 844 /* */
 845 void pkgDepCache::MarkInstall(PkgIterator const &Pkg,bool AutoInst,
 846                               unsigned long Depth, bool FromUser,
 847                               bool ForceImportantDeps)
 848 {
 849    if (Depth > 100)
 850       return;
 851
 852    // Simplifies other routines.
 853    if (Pkg.end() == true)
 854       return;
 855
 856    ActionGroup group(*this);
 857
 858    /* Check that it is not already marked for install and that it can be
 859       installed */
 860    StateCache &P = PkgState[Pkg->ID];
 861    P.iFlags &= ~AutoKept;
 862    if ((P.InstPolicyBroken() == false && P.InstBroken() == false) &&
 863        (P.Mode == ModeInstall ||
 864         P.CandidateVer == (Version *)Pkg.CurrentVer()))
 865    {
 866       if (P.CandidateVer == (Version *)Pkg.CurrentVer() && P.InstallVer == 0)
 867          MarkKeep(Pkg, false, FromUser, Depth+1);
 868       return;
 869    }
 870
 871    // See if there is even any possible instalation candidate
 872    if (P.CandidateVer == 0)
 873       return;
 874    // We dont even try to install virtual packages..
 875    if (Pkg->VersionList == 0)
 876       return;
 877
 878    // check if we are allowed to install the package
 879    if (IsInstallOk(Pkg,AutoInst,Depth,FromUser) == false)
 880       return;
 881
 882    /* Target the candidate version and remove the autoflag. We reset the
 883       autoflag below if this was called recursively. Otherwise the user
 884       should have the ability to de-auto a package by changing its state */
 885    RemoveSizes(Pkg);
 886    RemoveStates(Pkg);
 887
 888    P.Mode = ModeInstall;
 889    P.InstallVer = P.CandidateVer;
 890
 891    if(FromUser)
 892      {
 893        // Set it to manual if it's a new install or cancelling the
 894        // removal of a garbage package.
 895        if(P.Status == 2 || (!Pkg.CurrentVer().end() && !P.Marked))
 896          P.Flags &= ~Flag::Auto;
 897      }
 898    else
 899      {
 900        // Set it to auto if this is a new install.
 901        if(P.Status == 2)
 902          P.Flags |= Flag::Auto;
 903      }
 904    if (P.CandidateVer == (Version *)Pkg.CurrentVer())
 905       P.Mode = ModeKeep;
 906
 907    AddStates(Pkg);
 908    Update(Pkg);
 909    AddSizes(Pkg);
 910
 911    if (AutoInst == false)
 912       return;
 913
 914    if (DebugMarker == true)
 915       std::clog << OutputInDepth(Depth) << "MarkInstall " << Pkg << " FU=" << FromUser << std::endl;
 916
 917    DepIterator Dep = P.InstVerIter(*this).DependsList();
 918    for (; Dep.end() != true;)
 919    {
 920       // Grok or groups
 921       DepIterator Start = Dep;
 922       bool Result = true;
 923       unsigned Ors = 0;
 924       for (bool LastOR = true; Dep.end() == false && LastOR == true; Dep++,Ors++)
 925       {
 926          LastOR = (Dep->CompareOp & Dep::Or) == Dep::Or;
 927
 928          if ((DepState[Dep->ID] & DepInstall) == DepInstall)
 929             Result = false;
 930       }
 931
 932       // Dep is satisfied okay.
 933       if (Result == false)
 934          continue;
 935
 936       /* Check if this dep should be consider for install. If it is a user
 937          defined important dep and we are installed a new package then
 938          it will be installed. Otherwise we only check for important
 939          deps that have changed from the installed version
 940       */
 941       if (IsImportantDep(Start) == false)
 942          continue;
 943
 944       /* Check if any ImportantDep() (but not Critical) were added
 945        * since we installed the package.  Also check for deps that
 946        * were satisfied in the past: for instance, if a version
 947        * restriction in a Recommends was tightened, upgrading the
 948        * package should follow that Recommends rather than causing the
 949        * dependency to be removed. (bug #470115)
 950        */
 951       bool isNewImportantDep = false;
 952       bool isPreviouslySatisfiedImportantDep = false;
 953       if(!ForceImportantDeps && !Start.IsCritical())
 954       {
 955          bool found=false;
 956          VerIterator instVer = Pkg.CurrentVer();
 957          if(!instVer.end())
 958          {
 959            for (DepIterator D = instVer.DependsList(); D.end() != true; D++)
 960              {
 961                //FIXME: deal better with or-groups(?)
 962                DepIterator LocalStart = D;
 963
 964                if(IsImportantDep(D) && !D.IsCritical() &&
 965                   Start.TargetPkg() == D.TargetPkg())
 966                  {
 967                    if(!isPreviouslySatisfiedImportantDep)
 968                      {
 969                        DepIterator D2 = D;
 970                        while((D2->CompareOp & Dep::Or) != 0)
 971                          ++D2;
 972
 973                        isPreviouslySatisfiedImportantDep =
 974                          (((*this)[D2] & DepGNow) != 0);
 975                      }
 976
 977                    found=true;
 978                  }
 979              }
 980             // this is a new dep if it was not found to be already
 981             // a important dep of the installed pacakge
 982             isNewImportantDep = !found;
 983          }
 984       }
 985       if(isNewImportantDep)
 986          if(DebugAutoInstall == true)
 987             std::clog << OutputInDepth(Depth) << "new important dependency: "
 988                       << Start.TargetPkg().Name() << std::endl;
 989       if(isPreviouslySatisfiedImportantDep)
 990         if(DebugAutoInstall == true)
 991           std::clog << OutputInDepth(Depth) << "previously satisfied important dependency on "
 992                     << Start.TargetPkg().Name() << std::endl;
 993
 994       // skip important deps if the package is already installed
 995       if (Pkg->CurrentVer != 0 && Start.IsCritical() == false
 996           && !isNewImportantDep && !isPreviouslySatisfiedImportantDep
 997           && !ForceImportantDeps)
 998          continue;
 999
1000       /* If we are in an or group locate the first or that can
1001          succeed. We have already cached this.. */
1002       for (; Ors > 1 && (DepState[Start->ID] & DepCVer) != DepCVer; Ors--)
1003          Start++;
1004
1005       /* This bit is for processing the possibilty of an install/upgrade
1006          fixing the problem */
1007       SPtrArray<Version *> List = Start.AllTargets();
1008       if (Start->Type != Dep::DpkgBreaks &&
1009           (DepState[Start->ID] & DepCVer) == DepCVer)
1010       {
1011          // Right, find the best version to install..
1012          Version **Cur = List;
1013          PkgIterator P = Start.TargetPkg();
1014          PkgIterator InstPkg(*Cache,0);
1015
1016          // See if there are direct matches (at the start of the list)
1017          for (; *Cur != 0 && (*Cur)->ParentPkg == P.Index(); Cur++)
1018          {
1019             PkgIterator Pkg(*Cache,Cache->PkgP + (*Cur)->ParentPkg);
1020             if (PkgState[Pkg->ID].CandidateVer != *Cur)
1021                continue;
1022             InstPkg = Pkg;
1023             break;
1024          }
1025
1026          // Select the highest priority providing package
1027          if (InstPkg.end() == true)
1028          {
1029             pkgPrioSortList(*Cache,Cur);
1030             for (; *Cur != 0; Cur++)
1031             {
1032                PkgIterator Pkg(*Cache,Cache->PkgP + (*Cur)->ParentPkg);
1033                if (PkgState[Pkg->ID].CandidateVer != *Cur)
1034                   continue;
1035                InstPkg = Pkg;
1036                break;
1037             }
1038          }
1039
1040          if (InstPkg.end() == false)
1041          {
1042             if(DebugAutoInstall == true)
1043                std::clog << OutputInDepth(Depth) << "Installing " << InstPkg.Name()
1044                          << " as " << Start.DepType() << " of " << Pkg.Name()
1045                          << std::endl;
1046             // now check if we should consider it a automatic dependency or not
1047             if(Pkg.Section() && ConfigValueInSubTree("APT::Never-MarkAuto-Sections", Pkg.Section()))
1048             {
1049                if(DebugAutoInstall == true)
1050                   std::clog << OutputInDepth(Depth) << "Setting NOT as auto-installed (direct "
1051                             << Start.DepType() << " of pkg in APT::Never-MarkAuto-Sections)" << std::endl;
1052                MarkInstall(InstPkg,true,Depth + 1, true);
1053             }
1054             else
1055             {
1056                // mark automatic dependency
1057                MarkInstall(InstPkg,true,Depth + 1, false, ForceImportantDeps);
1058                // Set the autoflag, after MarkInstall because MarkInstall unsets it
1059                if (P->CurrentVer == 0)
1060                   PkgState[InstPkg->ID].Flags |= Flag::Auto;
1061             }
1062          }
1063          continue;
1064       }
1065
1066       /* For conflicts we just de-install the package and mark as auto,
1067          Conflicts may not have or groups.  For dpkg's Breaks we try to
1068          upgrade the package. */
1069       if (Start->Type == Dep::Conflicts || Start->Type == Dep::Obsoletes ||
1070           Start->Type == Dep::DpkgBreaks)
1071       {
1072          for (Version **I = List; *I != 0; I++)
1073          {
1074             VerIterator Ver(*this,*I);
1075             PkgIterator Pkg = Ver.ParentPkg();
1076
1077             if (Start->Type != Dep::DpkgBreaks)
1078                MarkDelete(Pkg,false,Depth + 1, false);
1079             else if (PkgState[Pkg->ID].CandidateVer != *I)
1080                MarkInstall(Pkg,true,Depth + 1, false, ForceImportantDeps);
1081          }
1082          continue;
1083       }
1084    }
1085 }
1086                                                                         /*}}}*/
1087 // DepCache::IsInstallOk - check if it is ok to install this package    /*{{{*/
1088 // ---------------------------------------------------------------------
1089 /* The default implementation just honors dpkg hold
1090    But an application using this library can override this method
1091    to control the MarkInstall behaviour */
1092 bool pkgDepCache::IsInstallOk(PkgIterator const &Pkg,bool AutoInst,
1093                               unsigned long Depth, bool FromUser)
1094 {
1095    if (FromUser == false && Pkg->SelectedState == pkgCache::State::Hold && _config->FindB("APT::Ignore-Hold",false) == false)
1096    {
1097       if (DebugMarker == true)
1098          std::clog << OutputInDepth(Depth) << "Hold prevents MarkInstall of " << Pkg << " FU=" << FromUser << std::endl;
1099       return false;
1100    }
1101    return true;
1102 }
1103                                                                         /*}}}*/
1104 // DepCache::SetReInstall - Set the reinstallation flag                 /*{{{*/
1105 // ---------------------------------------------------------------------
1106 /* */
1107 void pkgDepCache::SetReInstall(PkgIterator const &Pkg,bool To)
1108 {
1109    ActionGroup group(*this);
1110
1111    RemoveSizes(Pkg);
1112    RemoveStates(Pkg);
1113
1114    StateCache &P = PkgState[Pkg->ID];
1115    if (To == true)
1116       P.iFlags |= ReInstall;
1117    else
1118       P.iFlags &= ~ReInstall;
1119
1120    AddStates(Pkg);
1121    AddSizes(Pkg);
1122 }
1123                                                                         /*}}}*/
1124 // DepCache::SetCandidateVersion - Change the candidate version         /*{{{*/
1125 // ---------------------------------------------------------------------
1126 /* */
1127 void pkgDepCache::SetCandidateVersion(VerIterator TargetVer)
1128 {
1129    ActionGroup group(*this);
1130
1131    pkgCache::PkgIterator Pkg = TargetVer.ParentPkg();
1132    StateCache &P = PkgState[Pkg->ID];
1133
1134    RemoveSizes(Pkg);
1135    RemoveStates(Pkg);
1136
1137    if (P.CandidateVer == P.InstallVer)
1138       P.InstallVer = (Version *)TargetVer;
1139    P.CandidateVer = (Version *)TargetVer;
1140    P.Update(Pkg,*this);
1141
1142    AddStates(Pkg);
1143    Update(Pkg);
1144    AddSizes(Pkg);
1145 }
1146
1147 void pkgDepCache::MarkAuto(const PkgIterator &Pkg, bool Auto)
1148 {
1149   StateCache &state = PkgState[Pkg->ID];
1150
1151   ActionGroup group(*this);
1152
1153   if(Auto)
1154     state.Flags |= Flag::Auto;
1155   else
1156     state.Flags &= ~Flag::Auto;
1157 }
1158                                                                         /*}}}*/
1159 // StateCache::Update - Compute the various static display things       /*{{{*/
1160 // ---------------------------------------------------------------------
1161 /* This is called whenever the Candidate version changes. */
1162 void pkgDepCache::StateCache::Update(PkgIterator Pkg,pkgCache &Cache)
1163 {
1164    // Some info
1165    VerIterator Ver = CandidateVerIter(Cache);
1166
1167    // Use a null string or the version string
1168    if (Ver.end() == true)
1169       CandVersion = "";
1170    else
1171       CandVersion = Ver.VerStr();
1172
1173    // Find the current version
1174    CurVersion = "";
1175    if (Pkg->CurrentVer != 0)
1176       CurVersion = Pkg.CurrentVer().VerStr();
1177
1178    // Strip off the epochs for display
1179    CurVersion = StripEpoch(CurVersion);
1180    CandVersion = StripEpoch(CandVersion);
1181
1182    // Figure out if its up or down or equal
1183    Status = Ver.CompareVer(Pkg.CurrentVer());
1184    if (Pkg->CurrentVer == 0 || Pkg->VersionList == 0 || CandidateVer == 0)
1185      Status = 2;
1186 }
1187                                                                         /*}}}*/
1188 // StateCache::StripEpoch - Remove the epoch specifier from the version /*{{{*/
1189 // ---------------------------------------------------------------------
1190 /* */
1191 const char *pkgDepCache::StateCache::StripEpoch(const char *Ver)
1192 {
1193    if (Ver == 0)
1194       return 0;
1195
1196    // Strip any epoch
1197    for (const char *I = Ver; *I != 0; I++)
1198       if (*I == ':')
1199          return I + 1;
1200    return Ver;
1201 }
1202                                                                         /*}}}*/
1203 // Policy::GetCandidateVer - Returns the Candidate install version      /*{{{*/
1204 // ---------------------------------------------------------------------
1205 /* The default just returns the highest available version that is not
1206    a source and automatic. */
1207 pkgCache::VerIterator pkgDepCache::Policy::GetCandidateVer(PkgIterator Pkg)
1208 {
1209    /* Not source/not automatic versions cannot be a candidate version
1210       unless they are already installed */
1211    VerIterator Last(*(pkgCache *)this,0);
1212
1213    for (VerIterator I = Pkg.VersionList(); I.end() == false; I++)
1214    {
1215       if (Pkg.CurrentVer() == I)
1216          return I;
1217
1218       for (VerFileIterator J = I.FileList(); J.end() == false; J++)
1219       {
1220          if ((J.File()->Flags & Flag::NotSource) != 0)
1221             continue;
1222
1223          /* Stash the highest version of a not-automatic source, we use it
1224             if there is nothing better */
1225          if ((J.File()->Flags & Flag::NotAutomatic) != 0)
1226          {
1227             if (Last.end() == true)
1228                Last = I;
1229             continue;
1230          }
1231
1232          return I;
1233       }
1234    }
1235
1236    return Last;
1237 }
1238                                                                         /*}}}*/
1239 // Policy::IsImportantDep - True if the dependency is important         /*{{{*/
1240 // ---------------------------------------------------------------------
1241 /* */
1242 bool pkgDepCache::Policy::IsImportantDep(DepIterator Dep)
1243 {
1244    if(Dep.IsCritical())
1245       return true;
1246    else if(Dep->Type == pkgCache::Dep::Recommends)
1247    {
1248       if ( _config->FindB("APT::Install-Recommends", false))
1249          return true;
1250       // we suport a special mode to only install-recommends for certain
1251       // sections
1252       // FIXME: this is a meant as a temporarly solution until the
1253       //        recommends are cleaned up
1254       const char *sec = Dep.ParentVer().Section();
1255       if (sec && ConfigValueInSubTree("APT::Install-Recommends-Sections", sec))
1256          return true;
1257    }
1258    else if(Dep->Type == pkgCache::Dep::Suggests)
1259      return _config->FindB("APT::Install-Suggests", false);
1260
1261    return false;
1262 }
1263                                                                         /*}}}*/
1264 pkgDepCache::DefaultRootSetFunc::DefaultRootSetFunc()                   /*{{{*/
1265   : constructedSuccessfully(false)
1266 {
1267   Configuration::Item const *Opts;
1268   Opts = _config->Tree("APT::NeverAutoRemove");
1269   if (Opts != 0 && Opts->Child != 0)
1270     {
1271       Opts = Opts->Child;
1272       for (; Opts != 0; Opts = Opts->Next)
1273         {
1274           if (Opts->Value.empty() == true)
1275             continue;
1276
1277           regex_t *p = new regex_t;
1278           if(regcomp(p,Opts->Value.c_str(),
1279                      REG_EXTENDED | REG_ICASE | REG_NOSUB) != 0)
1280             {
1281               regfree(p);
1282               delete p;
1283               _error->Error("Regex compilation error for APT::NeverAutoRemove");
1284               return;
1285             }
1286
1287           rootSetRegexp.push_back(p);
1288         }
1289     }
1290
1291   constructedSuccessfully = true;
1292 }
1293                                                                         /*}}}*/
1294 pkgDepCache::DefaultRootSetFunc::~DefaultRootSetFunc()                  /*{{{*/
1295 {
1296   for(unsigned int i = 0; i < rootSetRegexp.size(); i++)
1297     {
1298       regfree(rootSetRegexp[i]);
1299       delete rootSetRegexp[i];
1300     }
1301 }
1302                                                                         /*}}}*/
1303 bool pkgDepCache::DefaultRootSetFunc::InRootSet(const pkgCache::PkgIterator &pkg) /*{{{*/
1304 {
1305    for(unsigned int i = 0; i < rootSetRegexp.size(); i++)
1306       if (regexec(rootSetRegexp[i], pkg.Name(), 0, 0, 0) == 0)
1307          return true;
1308
1309    return false;
1310 }
1311                                                                         /*}}}*/
1312 pkgDepCache::InRootSetFunc *pkgDepCache::GetRootSetFunc()               /*{{{*/
1313 {
1314   DefaultRootSetFunc *f = new DefaultRootSetFunc;
1315   if(f->wasConstructedSuccessfully())
1316     return f;
1317   else
1318     {
1319       delete f;
1320       return NULL;
1321     }
1322 }
1323                                                                         /*}}}*/
1324 bool pkgDepCache::MarkFollowsRecommends()
1325 {
1326   return _config->FindB("APT::AutoRemove::RecommendsImportant", true);
1327 }
1328
1329 bool pkgDepCache::MarkFollowsSuggests()
1330 {
1331   return _config->FindB("APT::AutoRemove::SuggestsImportant", false);
1332 }
1333
1334 // pkgDepCache::MarkRequired - the main mark algorithm                  /*{{{*/
1335 bool pkgDepCache::MarkRequired(InRootSetFunc &userFunc)
1336 {
1337    bool follow_recommends;
1338    bool follow_suggests;
1339    bool debug_autoremove = _config->FindB("Debug::pkgAutoRemove",false);
1340
1341    // init the states
1342    for(PkgIterator p = PkgBegin(); !p.end(); ++p)
1343    {
1344       PkgState[p->ID].Marked  = false;
1345       PkgState[p->ID].Garbage = false;
1346
1347       // debug output
1348       if(debug_autoremove && PkgState[p->ID].Flags & Flag::Auto)
1349          std::clog << "AutoDep: " << p.Name() << std::endl;
1350    }
1351
1352    // init vars
1353    follow_recommends = MarkFollowsRecommends();
1354    follow_suggests   = MarkFollowsSuggests();
1355
1356
1357
1358    // do the mark part, this is the core bit of the algorithm
1359    for(PkgIterator p = PkgBegin(); !p.end(); ++p)
1360    {
1361       if(!(PkgState[p->ID].Flags & Flag::Auto) ||
1362           (p->Flags & Flag::Essential) ||
1363           userFunc.InRootSet(p))
1364
1365       {
1366          // the package is installed (and set to keep)
1367          if(PkgState[p->ID].Keep() && !p.CurrentVer().end())
1368             MarkPackage(p, p.CurrentVer(),
1369                         follow_recommends, follow_suggests);
1370          // the package is to be installed
1371          else if(PkgState[p->ID].Install())
1372             MarkPackage(p, PkgState[p->ID].InstVerIter(*this),
1373                         follow_recommends, follow_suggests);
1374       }
1375    }
1376
1377    return true;
1378 }
1379                                                                         /*}}}*/
1380 // MarkPackage - mark a single package in Mark-and-Sweep                /*{{{*/
1381 void pkgDepCache::MarkPackage(const pkgCache::PkgIterator &pkg,
1382                               const pkgCache::VerIterator &ver,
1383                               bool follow_recommends,
1384                               bool follow_suggests)
1385 {
1386    pkgDepCache::StateCache &state = PkgState[pkg->ID];
1387    VerIterator currver            = pkg.CurrentVer();
1388    VerIterator candver            = state.CandidateVerIter(*this);
1389    VerIterator instver            = state.InstVerIter(*this);
1390
1391 #if 0
1392    // If a package was garbage-collected but is now being marked, we
1393    // should re-select it
1394    // For cases when a pkg is set to upgrade and this trigger the
1395    // removal of a no-longer used dependency.  if the pkg is set to
1396    // keep again later it will result in broken deps
1397    if(state.Delete() && state.RemoveReason = Unused)
1398    {
1399       if(ver==candver)
1400          mark_install(pkg, false, false, NULL);
1401       else if(ver==pkg.CurrentVer())
1402          MarkKeep(pkg, false, false);
1403
1404       instver=state.InstVerIter(*this);
1405    }
1406 #endif
1407
1408    // For packages that are not going to be removed, ignore versions
1409    // other than the InstVer.  For packages that are going to be
1410    // removed, ignore versions other than the current version.
1411    if(!(ver == instver && !instver.end()) &&
1412       !(ver == currver && instver.end() && !ver.end()))
1413       return;
1414
1415    // if we are marked already we are done
1416    if(state.Marked)
1417       return;
1418
1419    bool debug_autoremove = _config->FindB("Debug::pkgAutoRemove", false);
1420
1421    if(debug_autoremove)
1422      {
1423        std::clog << "Marking: " << pkg.Name();
1424        if(!ver.end())
1425          std::clog << " " << ver.VerStr();
1426        if(!currver.end())
1427          std::clog << ", Curr=" << currver.VerStr();
1428        if(!instver.end())
1429          std::clog << ", Inst=" << instver.VerStr();
1430        std::clog << std::endl;
1431      }
1432
1433    state.Marked=true;
1434
1435    if(!ver.end())
1436    {
1437      for(DepIterator d = ver.DependsList(); !d.end(); ++d)
1438      {
1439         if(d->Type == Dep::Depends ||
1440            d->Type == Dep::PreDepends ||
1441            (follow_recommends &&
1442             d->Type == Dep::Recommends) ||
1443            (follow_suggests &&
1444             d->Type == Dep::Suggests))
1445         {
1446            // Try all versions of this package.
1447            for(VerIterator V = d.TargetPkg().VersionList();
1448                !V.end(); ++V)
1449            {
1450               if(_system->VS->CheckDep(V.VerStr(), d->CompareOp, d.TargetVer()))
1451               {
1452                 if(debug_autoremove)
1453                   {
1454                     std::clog << "Following dep: " << d.ParentPkg().Name()
1455                               << " " << d.ParentVer().VerStr() << " "
1456                               << d.DepType() << " "
1457                               << d.TargetPkg().Name();
1458                     if((d->CompareOp & ~pkgCache::Dep::Or) != pkgCache::Dep::NoOp)
1459                       {
1460                         std::clog << " (" << d.CompType() << " "
1461                                   << d.TargetVer() << ")";
1462                       }
1463                     std::clog << std::endl;
1464                   }
1465                  MarkPackage(V.ParentPkg(), V,
1466                              follow_recommends, follow_suggests);
1467               }
1468            }
1469            // Now try virtual packages
1470            for(PrvIterator prv=d.TargetPkg().ProvidesList();
1471                !prv.end(); ++prv)
1472            {
1473               if(_system->VS->CheckDep(prv.ProvideVersion(), d->CompareOp,
1474                                        d.TargetVer()))
1475               {
1476                 if(debug_autoremove)
1477                   {
1478                     std::clog << "Following dep: " << d.ParentPkg().Name()
1479                               << " " << d.ParentVer().VerStr() << " "
1480                               << d.DepType() << " "
1481                               << d.TargetPkg().Name();
1482                     if((d->CompareOp & ~pkgCache::Dep::Or) != pkgCache::Dep::NoOp)
1483                       {
1484                         std::clog << " (" << d.CompType() << " "
1485                                   << d.TargetVer() << ")";
1486                       }
1487                     std::clog << ", provided by "
1488                               << prv.OwnerPkg().Name() << " "
1489                               << prv.OwnerVer().VerStr()
1490                               << std::endl;
1491                   }
1492
1493                  MarkPackage(prv.OwnerPkg(), prv.OwnerVer(),
1494                              follow_recommends, follow_suggests);
1495               }
1496            }
1497         }
1498      }
1499    }
1500 }
1501                                                                         /*}}}*/
1502 bool pkgDepCache::Sweep()                                               /*{{{*/
1503 {
1504    bool debug_autoremove = _config->FindB("Debug::pkgAutoRemove",false);
1505
1506    // do the sweep
1507    for(PkgIterator p=PkgBegin(); !p.end(); ++p)
1508    {
1509      StateCache &state=PkgState[p->ID];
1510
1511      // skip required packages
1512      if (!p.CurrentVer().end() &&
1513          (p.CurrentVer()->Priority == pkgCache::State::Required))
1514         continue;
1515
1516      // if it is not marked and it is installed, it's garbage
1517      if(!state.Marked && (!p.CurrentVer().end() || state.Install()))
1518      {
1519         state.Garbage=true;
1520         if(debug_autoremove)
1521            std::cout << "Garbage: " << p.Name() << std::endl;
1522      }
1523   }
1524
1525    return true;
1526 }
1527                                                                         /*}}}*/