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