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