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