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