apt-pkg/depcache.cc

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