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