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<config.h>
  12
  13 #include <apt-pkg/depcache.h>
  14 #include <apt-pkg/versionmatch.h>
  15 #include <apt-pkg/error.h>
  16 #include <apt-pkg/sptr.h>
  17 #include <apt-pkg/fileutl.h>
  18 #include <apt-pkg/strutl.h>
  19 #include <apt-pkg/configuration.h>
  20 #include <apt-pkg/aptconfiguration.h>
  21 #include <apt-pkg/tagfile.h>
  22 #include <apt-pkg/progress.h>
  23 #include <apt-pkg/cacheset.h>
  24 #include <apt-pkg/pkgcache.h>
  25 #include <apt-pkg/cacheiterators.h>
  26 #include <apt-pkg/macros.h>
  27
  28 #include <stdio.h>
  29 #include <string.h>
  30 #include <list>
  31 #include <string>
  32 #include <utility>
  33 #include <vector>
  34 #include <algorithm>
  35 #include <iostream>
  36 #include <sstream>
  37 #include <set>
  38
  39 #include <sys/stat.h>
  40
  41 #include <apti18n.h>
  42                                                                         /*}}}*/
  43
  44 using std::string;
  45
  46 // helper for Install-Recommends-Sections and Never-MarkAuto-Sections   /*{{{*/
  47 static bool
  48 ConfigValueInSubTree(const char* SubTree, const char *needle)
  49 {
  50    Configuration::Item const *Opts;
  51    Opts = _config->Tree(SubTree);
  52    if (Opts != 0 && Opts->Child != 0)
  53    {
  54       Opts = Opts->Child;
  55       for (; Opts != 0; Opts = Opts->Next)
  56       {
  57          if (Opts->Value.empty() == true)
  58             continue;
  59          if (strcmp(needle, Opts->Value.c_str()) == 0)
  60             return true;
  61       }
  62    }
  63    return false;
  64 }
  65                                                                         /*}}}*/
  66 pkgDepCache::ActionGroup::ActionGroup(pkgDepCache &cache) :             /*{{{*/
  67   cache(cache), released(false)
  68 {
  69   ++cache.group_level;
  70 }
  71
  72 void pkgDepCache::ActionGroup::release()
  73 {
  74   if(!released)
  75     {
  76       if(cache.group_level == 0)
  77         std::cerr << "W: Unbalanced action groups, expect badness" << std::endl;
  78       else
  79         {
  80           --cache.group_level;
  81
  82           if(cache.group_level == 0)
  83             cache.MarkAndSweep();
  84         }
  85
  86       released = true;
  87     }
  88 }
  89
  90 pkgDepCache::ActionGroup::~ActionGroup()
  91 {
  92   release();
  93 }
  94                                                                         /*}}}*/
  95 // DepCache::pkgDepCache - Constructors                                 /*{{{*/
  96 // ---------------------------------------------------------------------
  97 /* */
  98 pkgDepCache::pkgDepCache(pkgCache *pCache,Policy *Plcy) :
  99   group_level(0), Cache(pCache), PkgState(0), DepState(0)
 100 {
 101    DebugMarker = _config->FindB("Debug::pkgDepCache::Marker", false);
 102    DebugAutoInstall = _config->FindB("Debug::pkgDepCache::AutoInstall", false);
 103    delLocalPolicy = 0;
 104    LocalPolicy = Plcy;
 105    if (LocalPolicy == 0)
 106       delLocalPolicy = LocalPolicy = new Policy;
 107 }
 108                                                                         /*}}}*/
 109 // DepCache::~pkgDepCache - Destructor                                  /*{{{*/
 110 // ---------------------------------------------------------------------
 111 /* */
 112 pkgDepCache::~pkgDepCache()
 113 {
 114    delete [] PkgState;
 115    delete [] DepState;
 116    delete delLocalPolicy;
 117 }
 118                                                                         /*}}}*/
 119 // DepCache::Init - Generate the initial extra structures.              /*{{{*/
 120 // ---------------------------------------------------------------------
 121 /* This allocats the extension buffers and initializes them. */
 122 bool pkgDepCache::Init(OpProgress *Prog)
 123 {
 124    // Suppress mark updates during this operation (just in case) and
 125    // run a mark operation when Init terminates.
 126    ActionGroup actions(*this);
 127
 128    delete [] PkgState;
 129    delete [] DepState;
 130    PkgState = new StateCache[Head().PackageCount];
 131    DepState = new unsigned char[Head().DependsCount];
 132    memset(PkgState,0,sizeof(*PkgState)*Head().PackageCount);
 133    memset(DepState,0,sizeof(*DepState)*Head().DependsCount);
 134
 135    if (Prog != 0)
 136    {
 137       Prog->OverallProgress(0,2*Head().PackageCount,Head().PackageCount,
 138                             _("Building dependency tree"));
 139       Prog->SubProgress(Head().PackageCount,_("Candidate versions"));
 140    }
 141
 142    /* Set the current state of everything. In this state all of the
 143       packages are kept exactly as is. See AllUpgrade */
 144    int Done = 0;
 145    for (PkgIterator I = PkgBegin(); I.end() != true; ++I, ++Done)
 146    {
 147       if (Prog != 0 && Done%20 == 0)
 148          Prog->Progress(Done);
 149
 150       // Find the proper cache slot
 151       StateCache &State = PkgState[I->ID];
 152       State.iFlags = 0;
 153
 154       // Figure out the install version
 155       State.CandidateVer = GetCandidateVer(I);
 156       State.InstallVer = I.CurrentVer();
 157       State.Mode = ModeKeep;
 158
 159       State.Update(I,*this);
 160    }
 161
 162    if (Prog != 0)
 163    {
 164
 165       Prog->OverallProgress(Head().PackageCount,2*Head().PackageCount,
 166                             Head().PackageCount,
 167                             _("Building dependency tree"));
 168       Prog->SubProgress(Head().PackageCount,_("Dependency generation"));
 169    }
 170
 171    Update(Prog);
 172
 173    if(Prog != 0)
 174       Prog->Done();
 175
 176    return true;
 177 }
 178                                                                         /*}}}*/
 179 bool pkgDepCache::readStateFile(OpProgress *Prog)                       /*{{{*/
 180 {
 181    FileFd state_file;
 182    string const state = _config->FindFile("Dir::State::extended_states");
 183    if(RealFileExists(state)) {
 184       state_file.Open(state, FileFd::ReadOnly);
 185       off_t const file_size = state_file.Size();
 186       if(Prog != NULL)
 187          Prog->OverallProgress(0, file_size, 1,
 188                                _("Reading state information"));
 189
 190       pkgTagFile tagfile(&state_file);
 191       pkgTagSection section;
 192       off_t amt = 0;
 193       bool const debug_autoremove = _config->FindB("Debug::pkgAutoRemove",false);
 194       while(tagfile.Step(section)) {
 195          string const pkgname = section.FindS("Package");
 196          string pkgarch = section.FindS("Architecture");
 197          if (pkgarch.empty() == true)
 198             pkgarch = "any";
 199          pkgCache::PkgIterator pkg = Cache->FindPkg(pkgname, pkgarch);
 200          // Silently ignore unknown packages and packages with no actual version.
 201          if(pkg.end() == true || pkg->VersionList == 0)
 202             continue;
 203
 204          short const reason = section.FindI("Auto-Installed", 0);
 205          if(reason > 0)
 206          {
 207             PkgState[pkg->ID].Flags |= Flag::Auto;
 208             if (unlikely(debug_autoremove))
 209                std::clog << "Auto-Installed : " << pkg.FullName() << std::endl;
 210             if (pkgarch == "any")
 211             {
 212                pkgCache::GrpIterator G = pkg.Group();
 213                for (pkg = G.NextPkg(pkg); pkg.end() != true; pkg = G.NextPkg(pkg))
 214                   if (pkg->VersionList != 0)
 215                      PkgState[pkg->ID].Flags |= Flag::Auto;
 216             }
 217          }
 218          amt += section.size();
 219          if(Prog != NULL)
 220             Prog->OverallProgress(amt, file_size, 1,
 221                                   _("Reading state information"));
 222       }
 223       if(Prog != NULL)
 224          Prog->OverallProgress(file_size, file_size, 1,
 225                                _("Reading state information"));
 226    }
 227
 228    return true;
 229 }
 230                                                                         /*}}}*/
 231 bool pkgDepCache::writeStateFile(OpProgress * /*prog*/, bool InstalledOnly)     /*{{{*/
 232 {
 233    bool const debug_autoremove = _config->FindB("Debug::pkgAutoRemove",false);
 234
 235    if(debug_autoremove)
 236       std::clog << "pkgDepCache::writeStateFile()" << std::endl;
 237
 238    FileFd StateFile;
 239    string const state = _config->FindFile("Dir::State::extended_states");
 240    if (CreateAPTDirectoryIfNeeded(_config->FindDir("Dir::State"), flNotFile(state)) == false)
 241       return false;
 242
 243    // if it does not exist, create a empty one
 244    if(!RealFileExists(state))
 245    {
 246       StateFile.Open(state, FileFd::WriteAtomic);
 247       StateFile.Close();
 248    }
 249
 250    // open it
 251    if(!StateFile.Open(state, FileFd::ReadOnly))
 252       return _error->Error(_("Failed to open StateFile %s"),
 253                            state.c_str());
 254
 255    FILE *OutFile;
 256    string const outfile = state + ".tmp";
 257    if((OutFile = fopen(outfile.c_str(),"w")) == NULL)
 258       return _error->Error(_("Failed to write temporary StateFile %s"),
 259                            outfile.c_str());
 260
 261    // first merge with the existing sections
 262    pkgTagFile tagfile(&StateFile);
 263    pkgTagSection section;
 264    std::set<string> pkgs_seen;
 265    const char *nullreorderlist[] = {0};
 266    while(tagfile.Step(section)) {
 267          string const pkgname = section.FindS("Package");
 268          string pkgarch = section.FindS("Architecture");
 269          if (pkgarch.empty() == true)
 270             pkgarch = "native";
 271          // Silently ignore unknown packages and packages with no actual
 272          // version.
 273          pkgCache::PkgIterator pkg = Cache->FindPkg(pkgname, pkgarch);
 274          if(pkg.end() || pkg.VersionList().end())
 275             continue;
 276          StateCache const &P = PkgState[pkg->ID];
 277          bool newAuto = (P.Flags & Flag::Auto);
 278          // skip not installed or now-removed ones if requested
 279          if (InstalledOnly && (
 280              (pkg->CurrentVer == 0 && P.Mode != ModeInstall) ||
 281              (pkg->CurrentVer != 0 && P.Mode == ModeDelete)))
 282          {
 283             // The section is obsolete if it contains no other tag
 284             unsigned int const count = section.Count();
 285             if (count < 2 ||
 286                 (count == 2 && section.Exists("Auto-Installed")) ||
 287                 (count == 3 && section.Exists("Auto-Installed") && section.Exists("Architecture")))
 288                continue;
 289             else
 290                newAuto = false;
 291          }
 292          if(_config->FindB("Debug::pkgAutoRemove",false))
 293             std::clog << "Update existing AutoInstall info: "
 294                       << pkg.FullName() << std::endl;
 295          TFRewriteData rewrite[3];
 296          rewrite[0].Tag = "Architecture";
 297          rewrite[0].Rewrite = pkg.Arch();
 298          rewrite[0].NewTag = 0;
 299          rewrite[1].Tag = "Auto-Installed";
 300          rewrite[1].Rewrite = newAuto ? "1" : "0";
 301          rewrite[1].NewTag = 0;
 302          rewrite[2].Tag = 0;
 303          TFRewrite(OutFile, section, nullreorderlist, rewrite);
 304          fprintf(OutFile,"\n");
 305          pkgs_seen.insert(pkg.FullName());
 306    }
 307
 308    // then write the ones we have not seen yet
 309    std::ostringstream ostr;
 310    for(pkgCache::PkgIterator pkg=Cache->PkgBegin(); !pkg.end(); ++pkg) {
 311       StateCache const &P = PkgState[pkg->ID];
 312       if(P.Flags & Flag::Auto) {
 313          if (pkgs_seen.find(pkg.FullName()) != pkgs_seen.end()) {
 314             if(debug_autoremove)
 315                std::clog << "Skipping already written " << pkg.FullName() << std::endl;
 316             continue;
 317          }
 318          // skip not installed ones if requested
 319          if (InstalledOnly && (
 320              (pkg->CurrentVer == 0 && P.Mode != ModeInstall) ||
 321              (pkg->CurrentVer != 0 && P.Mode == ModeDelete)))
 322             continue;
 323          const char* const pkgarch = pkg.Arch();
 324          if (strcmp(pkgarch, "all") == 0)
 325             continue;
 326          if(debug_autoremove)
 327             std::clog << "Writing new AutoInstall: " << pkg.FullName() << std::endl;
 328          ostr.str(string(""));
 329          ostr << "Package: " << pkg.Name()
 330               << "\nArchitecture: " << pkgarch
 331               << "\nAuto-Installed: 1\n\n";
 332          fprintf(OutFile,"%s",ostr.str().c_str());
 333       }
 334    }
 335    fclose(OutFile);
 336
 337    // move the outfile over the real file and set permissions
 338    rename(outfile.c_str(), state.c_str());
 339    chmod(state.c_str(), 0644);
 340
 341    return true;
 342 }
 343                                                                         /*}}}*/
 344 // DepCache::CheckDep - Checks a single dependency                      /*{{{*/
 345 // ---------------------------------------------------------------------
 346 /* This first checks the dependency against the main target package and
 347    then walks along the package provides list and checks if each provides
 348    will be installed then checks the provides against the dep. Res will be
 349    set to the package which was used to satisfy the dep. */
 350 bool pkgDepCache::CheckDep(DepIterator Dep,int Type,PkgIterator &Res)
 351 {
 352    Res = Dep.TargetPkg();
 353
 354    /* Check simple depends. A depends -should- never self match but
 355       we allow it anyhow because dpkg does. Technically it is a packaging
 356       bug. Conflicts may never self match */
 357    if (Dep.IsIgnorable(Res) == false)
 358    {
 359       PkgIterator Pkg = Dep.TargetPkg();
 360       // Check the base package
 361       if (Type == NowVersion && Pkg->CurrentVer != 0)
 362          if (Dep.IsSatisfied(Pkg.CurrentVer()) == true)
 363             return true;
 364
 365       if (Type == InstallVersion && PkgState[Pkg->ID].InstallVer != 0)
 366          if (Dep.IsSatisfied(PkgState[Pkg->ID].InstVerIter(*this)) == true)
 367             return true;
 368
 369       if (Type == CandidateVersion && PkgState[Pkg->ID].CandidateVer != 0)
 370          if (Dep.IsSatisfied(PkgState[Pkg->ID].CandidateVerIter(*this)) == true)
 371             return true;
 372    }
 373
 374    if (Dep->Type == Dep::Obsoletes)
 375       return false;
 376
 377    // Check the providing packages
 378    PrvIterator P = Dep.TargetPkg().ProvidesList();
 379    for (; P.end() != true; ++P)
 380    {
 381       if (Dep.IsIgnorable(P) == true)
 382          continue;
 383
 384       // Check if the provides is a hit
 385       if (Type == NowVersion)
 386       {
 387          if (P.OwnerPkg().CurrentVer() != P.OwnerVer())
 388             continue;
 389       }
 390
 391       if (Type == InstallVersion)
 392       {
 393          StateCache &State = PkgState[P.OwnerPkg()->ID];
 394          if (State.InstallVer != (Version *)P.OwnerVer())
 395             continue;
 396       }
 397
 398       if (Type == CandidateVersion)
 399       {
 400          StateCache &State = PkgState[P.OwnerPkg()->ID];
 401          if (State.CandidateVer != (Version *)P.OwnerVer())
 402             continue;
 403       }
 404
 405       // Compare the versions.
 406       if (Dep.IsSatisfied(P) == true)
 407       {
 408          Res = P.OwnerPkg();
 409          return true;
 410       }
 411    }
 412
 413    return false;
 414 }
 415                                                                         /*}}}*/
 416 // DepCache::AddSizes - Add the packages sizes to the counters          /*{{{*/
 417 // ---------------------------------------------------------------------
 418 /* Call with Inverse = true to preform the inverse opration */
 419 void pkgDepCache::AddSizes(const PkgIterator &Pkg, bool const Inverse)
 420 {
 421    StateCache &P = PkgState[Pkg->ID];
 422
 423    if (Pkg->VersionList == 0)
 424       return;
 425
 426    if (Pkg.State() == pkgCache::PkgIterator::NeedsConfigure &&
 427        P.Keep() == true)
 428       return;
 429
 430    // Compute the size data
 431    if (P.NewInstall() == true)
 432    {
 433       if (Inverse == false) {
 434          iUsrSize += P.InstVerIter(*this)->InstalledSize;
 435          iDownloadSize += P.InstVerIter(*this)->Size;
 436       } else {
 437          iUsrSize -= P.InstVerIter(*this)->InstalledSize;
 438          iDownloadSize -= P.InstVerIter(*this)->Size;
 439       }
 440       return;
 441    }
 442
 443    // Upgrading
 444    if (Pkg->CurrentVer != 0 &&
 445        (P.InstallVer != (Version *)Pkg.CurrentVer() ||
 446         (P.iFlags & ReInstall) == ReInstall) && P.InstallVer != 0)
 447    {
 448       if (Inverse == false) {
 449          iUsrSize -= Pkg.CurrentVer()->InstalledSize;
 450          iUsrSize += P.InstVerIter(*this)->InstalledSize;
 451          iDownloadSize += P.InstVerIter(*this)->Size;
 452       } else {
 453          iUsrSize -= P.InstVerIter(*this)->InstalledSize;
 454          iUsrSize += Pkg.CurrentVer()->InstalledSize;
 455          iDownloadSize -= P.InstVerIter(*this)->Size;
 456       }
 457       return;
 458    }
 459
 460    // Reinstall
 461    if (Pkg.State() == pkgCache::PkgIterator::NeedsUnpack &&
 462        P.Delete() == false)
 463    {
 464       if (Inverse == false)
 465          iDownloadSize += P.InstVerIter(*this)->Size;
 466       else
 467          iDownloadSize -= P.InstVerIter(*this)->Size;
 468       return;
 469    }
 470
 471    // Removing
 472    if (Pkg->CurrentVer != 0 && P.InstallVer == 0)
 473    {
 474       if (Inverse == false)
 475          iUsrSize -= Pkg.CurrentVer()->InstalledSize;
 476       else
 477          iUsrSize += Pkg.CurrentVer()->InstalledSize;
 478       return;
 479    }
 480 }
 481                                                                         /*}}}*/
 482 // DepCache::AddStates - Add the package to the state counter           /*{{{*/
 483 // ---------------------------------------------------------------------
 484 /* This routine is tricky to use, you must make sure that it is never
 485    called twice for the same package. This means the Remove/Add section
 486    should be as short as possible and not encompass any code that will
 487    calld Remove/Add itself. Remember, dependencies can be circular so
 488    while processing a dep for Pkg it is possible that Add/Remove
 489    will be called on Pkg */
 490 void pkgDepCache::AddStates(const PkgIterator &Pkg, bool const Invert)
 491 {
 492    signed char const Add = (Invert == false) ? 1 : -1;
 493    StateCache &State = PkgState[Pkg->ID];
 494
 495    // The Package is broken (either minimal dep or policy dep)
 496    if ((State.DepState & DepInstMin) != DepInstMin)
 497       iBrokenCount += Add;
 498    if ((State.DepState & DepInstPolicy) != DepInstPolicy)
 499       iPolicyBrokenCount += Add;
 500
 501    // Bad state
 502    if (Pkg.State() != PkgIterator::NeedsNothing)
 503       iBadCount += Add;
 504
 505    // Not installed
 506    if (Pkg->CurrentVer == 0)
 507    {
 508       if (State.Mode == ModeDelete &&
 509           (State.iFlags & Purge) == Purge && Pkg.Purge() == false)
 510          iDelCount += Add;
 511
 512       if (State.Mode == ModeInstall)
 513          iInstCount += Add;
 514       return;
 515    }
 516
 517    // Installed, no upgrade
 518    if (State.Status == 0)
 519    {
 520       if (State.Mode == ModeDelete)
 521          iDelCount += Add;
 522       else
 523          if ((State.iFlags & ReInstall) == ReInstall)
 524             iInstCount += Add;
 525
 526       return;
 527    }
 528
 529    // Alll 3 are possible
 530    if (State.Mode == ModeDelete)
 531       iDelCount += Add;
 532    if (State.Mode == ModeKeep)
 533       iKeepCount += Add;
 534    if (State.Mode == ModeInstall)
 535       iInstCount += Add;
 536 }
 537                                                                         /*}}}*/
 538 // DepCache::BuildGroupOrs - Generate the Or group dep data             /*{{{*/
 539 // ---------------------------------------------------------------------
 540 /* The or group results are stored in the last item of the or group. This
 541    allows easy detection of the state of a whole or'd group. */
 542 void pkgDepCache::BuildGroupOrs(VerIterator const &V)
 543 {
 544    unsigned char Group = 0;
 545
 546    for (DepIterator D = V.DependsList(); D.end() != true; ++D)
 547    {
 548       // Build the dependency state.
 549       unsigned char &State = DepState[D->ID];
 550
 551       /* Invert for Conflicts. We have to do this twice to get the
 552          right sense for a conflicts group */
 553       if (D.IsNegative() == true)
 554          State = ~State;
 555
 556       // Add to the group if we are within an or..
 557       State &= 0x7;
 558       Group |= State;
 559       State |= Group << 3;
 560       if ((D->CompareOp & Dep::Or) != Dep::Or)
 561          Group = 0;
 562
 563       // Invert for Conflicts
 564       if (D.IsNegative() == true)
 565          State = ~State;
 566    }
 567 }
 568                                                                         /*}}}*/
 569 // DepCache::VersionState - Perform a pass over a dependency list       /*{{{*/
 570 // ---------------------------------------------------------------------
 571 /* This is used to run over a dependency list and determine the dep
 572    state of the list, filtering it through both a Min check and a Policy
 573    check. The return result will have SetMin/SetPolicy low if a check
 574    fails. It uses the DepState cache for it's computations. */
 575 unsigned char pkgDepCache::VersionState(DepIterator D,unsigned char Check,
 576                                        unsigned char SetMin,
 577                                        unsigned char SetPolicy)
 578 {
 579    unsigned char Dep = 0xFF;
 580
 581    while (D.end() != true)
 582    {
 583       // Compute a single dependency element (glob or)
 584       DepIterator Start = D;
 585       unsigned char State = 0;
 586       for (bool LastOR = true; D.end() == false && LastOR == true; ++D)
 587       {
 588          State |= DepState[D->ID];
 589          LastOR = (D->CompareOp & Dep::Or) == Dep::Or;
 590       }
 591
 592       // Minimum deps that must be satisfied to have a working package
 593       if (Start.IsCritical() == true)
 594          if ((State & Check) != Check)
 595             Dep &= ~SetMin;
 596
 597       // Policy deps that must be satisfied to install the package
 598       if (IsImportantDep(Start) == true &&
 599           (State & Check) != Check)
 600          Dep &= ~SetPolicy;
 601    }
 602
 603    return Dep;
 604 }
 605                                                                         /*}}}*/
 606 // DepCache::DependencyState - Compute the 3 results for a dep          /*{{{*/
 607 // ---------------------------------------------------------------------
 608 /* This is the main dependency computation bit. It computes the 3 main
 609    results for a dependencys, Now, Install and Candidate. Callers must
 610    invert the result if dealing with conflicts. */
 611 unsigned char pkgDepCache::DependencyState(DepIterator &D)
 612 {
 613    unsigned char State = 0;
 614
 615    if (CheckDep(D,NowVersion) == true)
 616       State |= DepNow;
 617    if (CheckDep(D,InstallVersion) == true)
 618       State |= DepInstall;
 619    if (CheckDep(D,CandidateVersion) == true)
 620       State |= DepCVer;
 621
 622    return State;
 623 }
 624                                                                         /*}}}*/
 625 // DepCache::UpdateVerState - Compute the Dep member of the state       /*{{{*/
 626 // ---------------------------------------------------------------------
 627 /* This determines the combined dependency representation of a package
 628    for its two states now and install. This is done by using the pre-generated
 629    dependency information. */
 630 void pkgDepCache::UpdateVerState(PkgIterator Pkg)
 631 {
 632    // Empty deps are always true
 633    StateCache &State = PkgState[Pkg->ID];
 634    State.DepState = 0xFF;
 635
 636    // Check the Current state
 637    if (Pkg->CurrentVer != 0)
 638    {
 639       DepIterator D = Pkg.CurrentVer().DependsList();
 640       State.DepState &= VersionState(D,DepNow,DepNowMin,DepNowPolicy);
 641    }
 642
 643    /* Check the candidate state. We do not compare against the whole as
 644       a candidate state but check the candidate version against the
 645       install states */
 646    if (State.CandidateVer != 0)
 647    {
 648       DepIterator D = State.CandidateVerIter(*this).DependsList();
 649       State.DepState &= VersionState(D,DepInstall,DepCandMin,DepCandPolicy);
 650    }
 651
 652    // Check target state which can only be current or installed
 653    if (State.InstallVer != 0)
 654    {
 655       DepIterator D = State.InstVerIter(*this).DependsList();
 656       State.DepState &= VersionState(D,DepInstall,DepInstMin,DepInstPolicy);
 657    }
 658 }
 659                                                                         /*}}}*/
 660 // DepCache::Update - Figure out all the state information              /*{{{*/
 661 // ---------------------------------------------------------------------
 662 /* This will figure out the state of all the packages and all the
 663    dependencies based on the current policy. */
 664 void pkgDepCache::Update(OpProgress *Prog)
 665 {
 666    iUsrSize = 0;
 667    iDownloadSize = 0;
 668    iInstCount = 0;
 669    iDelCount = 0;
 670    iKeepCount = 0;
 671    iBrokenCount = 0;
 672    iPolicyBrokenCount = 0;
 673    iBadCount = 0;
 674
 675    // Perform the depends pass
 676    int Done = 0;
 677    for (PkgIterator I = PkgBegin(); I.end() != true; ++I, ++Done)
 678    {
 679       if (Prog != 0 && Done%20 == 0)
 680          Prog->Progress(Done);
 681       for (VerIterator V = I.VersionList(); V.end() != true; ++V)
 682       {
 683          unsigned char Group = 0;
 684
 685          for (DepIterator D = V.DependsList(); D.end() != true; ++D)
 686          {
 687             // Build the dependency state.
 688             unsigned char &State = DepState[D->ID];
 689             State = DependencyState(D);
 690
 691             // Add to the group if we are within an or..
 692             Group |= State;
 693             State |= Group << 3;
 694             if ((D->CompareOp & Dep::Or) != Dep::Or)
 695                Group = 0;
 696
 697             // Invert for Conflicts
 698             if (D.IsNegative() == true)
 699                State = ~State;
 700          }
 701       }
 702
 703       // Compute the package dependency state and size additions
 704       AddSizes(I);
 705       UpdateVerState(I);
 706       AddStates(I);
 707    }
 708
 709    if (Prog != 0)
 710       Prog->Progress(Done);
 711
 712    readStateFile(Prog);
 713 }
 714                                                                         /*}}}*/
 715 // DepCache::Update - Update the deps list of a package                 /*{{{*/
 716 // ---------------------------------------------------------------------
 717 /* This is a helper for update that only does the dep portion of the scan.
 718    It is mainly meant to scan reverse dependencies. */
 719 void pkgDepCache::Update(DepIterator D)
 720 {
 721    // Update the reverse deps
 722    for (;D.end() != true; ++D)
 723    {
 724       unsigned char &State = DepState[D->ID];
 725       State = DependencyState(D);
 726
 727       // Invert for Conflicts
 728       if (D.IsNegative() == true)
 729          State = ~State;
 730
 731       RemoveStates(D.ParentPkg());
 732       BuildGroupOrs(D.ParentVer());
 733       UpdateVerState(D.ParentPkg());
 734       AddStates(D.ParentPkg());
 735    }
 736 }
 737                                                                         /*}}}*/
 738 // DepCache::Update - Update the related deps of a package              /*{{{*/
 739 // ---------------------------------------------------------------------
 740 /* This is called whenever the state of a package changes. It updates
 741    all cached dependencies related to this package. */
 742 void pkgDepCache::Update(PkgIterator const &Pkg)
 743 {
 744    // Recompute the dep of the package
 745    RemoveStates(Pkg);
 746    UpdateVerState(Pkg);
 747    AddStates(Pkg);
 748
 749    // Update the reverse deps
 750    Update(Pkg.RevDependsList());
 751
 752    // Update the provides map for the current ver
 753    if (Pkg->CurrentVer != 0)
 754       for (PrvIterator P = Pkg.CurrentVer().ProvidesList();
 755            P.end() != true; ++P)
 756          Update(P.ParentPkg().RevDependsList());
 757
 758    // Update the provides map for the candidate ver
 759    if (PkgState[Pkg->ID].CandidateVer != 0)
 760       for (PrvIterator P = PkgState[Pkg->ID].CandidateVerIter(*this).ProvidesList();
 761            P.end() != true; ++P)
 762          Update(P.ParentPkg().RevDependsList());
 763 }
 764                                                                         /*}}}*/
 765 // DepCache::MarkKeep - Put the package in the keep state               /*{{{*/
 766 // ---------------------------------------------------------------------
 767 /* */
 768 bool pkgDepCache::MarkKeep(PkgIterator const &Pkg, bool Soft, bool FromUser,
 769                            unsigned long Depth)
 770 {
 771    if (IsModeChangeOk(ModeKeep, Pkg, Depth, FromUser) == false)
 772       return false;
 773
 774    /* Reject an attempt to keep a non-source broken installed package, those
 775       must be upgraded */
 776    if (Pkg.State() == PkgIterator::NeedsUnpack &&
 777        Pkg.CurrentVer().Downloadable() == false)
 778       return false;
 779
 780    /* We changed the soft state all the time so the UI is a bit nicer
 781       to use */
 782    StateCache &P = PkgState[Pkg->ID];
 783
 784    // Check that it is not already kept
 785    if (P.Mode == ModeKeep)
 786       return true;
 787
 788    if (Soft == true)
 789       P.iFlags |= AutoKept;
 790    else
 791       P.iFlags &= ~AutoKept;
 792
 793    ActionGroup group(*this);
 794
 795 #if 0 // reseting the autoflag here means we lose the
 796       // auto-mark information if a user selects a package for removal
 797       // but changes  his mind then and sets it for keep again
 798       // - this makes sense as default when all Garbage dependencies
 799       //   are automatically marked for removal (as aptitude does).
 800       //   setting a package for keep then makes it no longer autoinstalled
 801       //   for all other use-case this action is rather surprising
 802    if(FromUser && !P.Marked)
 803      P.Flags &= ~Flag::Auto;
 804 #endif
 805
 806    if (DebugMarker == true)
 807       std::clog << OutputInDepth(Depth) << "MarkKeep " << Pkg << " FU=" << FromUser << std::endl;
 808
 809    RemoveSizes(Pkg);
 810    RemoveStates(Pkg);
 811
 812    P.Mode = ModeKeep;
 813    if (Pkg->CurrentVer == 0)
 814       P.InstallVer = 0;
 815    else
 816       P.InstallVer = Pkg.CurrentVer();
 817
 818    AddStates(Pkg);
 819    Update(Pkg);
 820    AddSizes(Pkg);
 821
 822    return true;
 823 }
 824                                                                         /*}}}*/
 825 // DepCache::MarkDelete - Put the package in the delete state           /*{{{*/
 826 // ---------------------------------------------------------------------
 827 /* */
 828 bool pkgDepCache::MarkDelete(PkgIterator const &Pkg, bool rPurge,
 829                              unsigned long Depth, bool FromUser)
 830 {
 831    if (IsModeChangeOk(ModeDelete, Pkg, Depth, FromUser) == false)
 832       return false;
 833
 834    StateCache &P = PkgState[Pkg->ID];
 835
 836    // Check that it is not already marked for delete
 837    if ((P.Mode == ModeDelete || P.InstallVer == 0) &&
 838        (Pkg.Purge() == true || rPurge == false))
 839       return true;
 840
 841    // check if we are allowed to remove the package
 842    if (IsDeleteOk(Pkg,rPurge,Depth,FromUser) == false)
 843       return false;
 844
 845    P.iFlags &= ~(AutoKept | Purge);
 846    if (rPurge == true)
 847       P.iFlags |= Purge;
 848
 849    ActionGroup group(*this);
 850
 851    if (DebugMarker == true)
 852       std::clog << OutputInDepth(Depth) << (rPurge ? "MarkPurge " : "MarkDelete ") << Pkg << " FU=" << FromUser << std::endl;
 853
 854    RemoveSizes(Pkg);
 855    RemoveStates(Pkg);
 856
 857    if (Pkg->CurrentVer == 0 && (Pkg.Purge() == true || rPurge == false))
 858       P.Mode = ModeKeep;
 859    else
 860       P.Mode = ModeDelete;
 861    P.InstallVer = 0;
 862
 863    AddStates(Pkg);
 864    Update(Pkg);
 865    AddSizes(Pkg);
 866
 867    return true;
 868 }
 869                                                                         /*}}}*/
 870 // DepCache::IsDeleteOk - check if it is ok to remove this package      /*{{{*/
 871 // ---------------------------------------------------------------------
 872 /* The default implementation tries to prevent deletion of install requests.
 873    dpkg holds are enforced by the private IsModeChangeOk */
 874 bool pkgDepCache::IsDeleteOk(PkgIterator const &Pkg,bool rPurge,
 875                               unsigned long Depth, bool FromUser)
 876 {
 877    return IsDeleteOkProtectInstallRequests(Pkg, rPurge, Depth, FromUser);
 878 }
 879 bool pkgDepCache::IsDeleteOkProtectInstallRequests(PkgIterator const &Pkg,
 880       bool const /*rPurge*/, unsigned long const Depth, bool const FromUser)
 881 {
 882    if (FromUser == false && Pkg->CurrentVer == 0)
 883    {
 884       StateCache &P = PkgState[Pkg->ID];
 885       if (P.InstallVer != 0 && P.Status == 2 && (P.Flags & Flag::Auto) != Flag::Auto)
 886       {
 887          if (DebugMarker == true)
 888             std::clog << OutputInDepth(Depth) << "Manual install request prevents MarkDelete of " << Pkg << std::endl;
 889          return false;
 890       }
 891    }
 892    return true;
 893 }
 894                                                                         /*}}}*/
 895 // DepCache::IsModeChangeOk - check if it is ok to change the mode      /*{{{*/
 896 // ---------------------------------------------------------------------
 897 /* this is used by all Mark methods on the very first line to check sanity
 898    and prevents mode changes for packages on hold for example.
 899    If you want to check Mode specific stuff you can use the virtual public
 900    Is<Mode>Ok methods instead */
 901 static char const* PrintMode(char const mode)
 902 {
 903          switch (mode)
 904          {
 905          case pkgDepCache::ModeInstall: return "Install";
 906          case pkgDepCache::ModeKeep: return "Keep";
 907          case pkgDepCache::ModeDelete: return "Delete";
 908          case pkgDepCache::ModeGarbage: return "Garbage";
 909          default: return "UNKNOWN";
 910          }
 911 }
 912 bool pkgDepCache::IsModeChangeOk(ModeList const mode, PkgIterator const &Pkg,
 913                                  unsigned long const Depth, bool const FromUser)
 914 {
 915    // we are not trying to hard…
 916    if (unlikely(Depth > 100))
 917       return false;
 918
 919    // general sanity
 920    if (unlikely(Pkg.end() == true || Pkg->VersionList == 0))
 921       return false;
 922
 923    // the user is always right
 924    if (FromUser == true)
 925       return true;
 926
 927    StateCache &P = PkgState[Pkg->ID];
 928    // not changing the mode is obviously also fine as we might want to call
 929    // e.g. MarkInstall multiple times with different arguments for the same package
 930    if (P.Mode == mode)
 931       return true;
 932
 933    // if previous state was set by user only user can reset it
 934    if ((P.iFlags & Protected) == Protected)
 935    {
 936       if (unlikely(DebugMarker == true))
 937          std::clog << OutputInDepth(Depth) << "Ignore Mark" << PrintMode(mode)
 938                    << " of " << Pkg << " as its mode (" << PrintMode(P.Mode)
 939                    << ") is protected" << std::endl;
 940       return false;
 941    }
 942    // enforce dpkg holds
 943    else if (mode != ModeKeep && Pkg->SelectedState == pkgCache::State::Hold &&
 944             _config->FindB("APT::Ignore-Hold",false) == false)
 945    {
 946       if (unlikely(DebugMarker == true))
 947          std::clog << OutputInDepth(Depth) << "Hold prevents Mark" << PrintMode(mode)
 948                    << " of " << Pkg << std::endl;
 949       return false;
 950    }
 951
 952    return true;
 953 }
 954                                                                         /*}}}*/
 955 // DepCache::MarkInstall - Put the package in the install state         /*{{{*/
 956 // ---------------------------------------------------------------------
 957 /* */
 958 struct CompareProviders {
 959    pkgCache::PkgIterator const Pkg;
 960    CompareProviders(pkgCache::DepIterator const &Dep) : Pkg(Dep.TargetPkg()) {};
 961    //bool operator() (APT::VersionList::iterator const &AV, APT::VersionList::iterator const &BV)
 962    bool operator() (pkgCache::VerIterator const &AV, pkgCache::VerIterator const &BV)
 963    {
 964       pkgCache::PkgIterator const A = AV.ParentPkg();
 965       pkgCache::PkgIterator const B = BV.ParentPkg();
 966       // Prefer MA:same packages if other architectures for it are installed
 967       if ((AV->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same ||
 968           (BV->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same)
 969       {
 970          bool instA = false;
 971          if ((AV->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same)
 972          {
 973             pkgCache::GrpIterator Grp = A.Group();
 974             for (pkgCache::PkgIterator P = Grp.PackageList(); P.end() == false; P = Grp.NextPkg(P))
 975                if (P->CurrentVer != 0)
 976                {
 977                   instA = true;
 978                   break;
 979                }
 980          }
 981          bool instB = false;
 982          if ((BV->MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same)
 983          {
 984             pkgCache::GrpIterator Grp = B.Group();
 985             for (pkgCache::PkgIterator P = Grp.PackageList(); P.end() == false; P = Grp.NextPkg(P))
 986             {
 987                if (P->CurrentVer != 0)
 988                {
 989                   instB = true;
 990                   break;
 991                }
 992             }
 993          }
 994          if (instA != instB)
 995             return instA == false;
 996       }
 997       // Prefer packages in the same group as the target; e.g. foo:i386, foo:amd64
 998       if (A->Group != B->Group)
 999       {
1000          if (A->Group == Pkg->Group && B->Group != Pkg->Group)
1001             return false;
1002          else if (B->Group == Pkg->Group && A->Group != Pkg->Group)
1003             return true;
1004       }
1005       // we like essentials
1006       if ((A->Flags & pkgCache::Flag::Essential) != (B->Flags & pkgCache::Flag::Essential))
1007       {
1008          if ((A->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
1009             return false;
1010          else if ((B->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
1011             return true;
1012       }
1013       if ((A->Flags & pkgCache::Flag::Important) != (B->Flags & pkgCache::Flag::Important))
1014       {
1015          if ((A->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important)
1016             return false;
1017          else if ((B->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important)
1018             return true;
1019       }
1020       // prefer native architecture
1021       if (strcmp(A.Arch(), B.Arch()) != 0)
1022       {
1023          if (strcmp(A.Arch(), A.Cache()->NativeArch()) == 0)
1024             return false;
1025          else if (strcmp(B.Arch(), B.Cache()->NativeArch()) == 0)
1026             return true;
1027          std::vector<std::string> archs = APT::Configuration::getArchitectures();
1028          for (std::vector<std::string>::const_iterator a = archs.begin(); a != archs.end(); ++a)
1029             if (*a == A.Arch())
1030                return false;
1031             else if (*a == B.Arch())
1032                return true;
1033       }
1034       // higher priority seems like a good idea
1035       if (AV->Priority != BV->Priority)
1036          return AV->Priority > BV->Priority;
1037       // unable to decide…
1038       return A->ID < B->ID;
1039    }
1040 };
1041 bool pkgDepCache::MarkInstall(PkgIterator const &Pkg,bool AutoInst,
1042                               unsigned long Depth, bool FromUser,
1043                               bool ForceImportantDeps)
1044 {
1045    if (IsModeChangeOk(ModeInstall, Pkg, Depth, FromUser) == false)
1046       return false;
1047
1048    StateCache &P = PkgState[Pkg->ID];
1049
1050    // See if there is even any possible instalation candidate
1051    if (P.CandidateVer == 0)
1052       return false;
1053
1054    /* Check that it is not already marked for install and that it can be
1055       installed */
1056    if ((P.InstPolicyBroken() == false && P.InstBroken() == false) &&
1057        (P.Mode == ModeInstall ||
1058         P.CandidateVer == (Version *)Pkg.CurrentVer()))
1059    {
1060       if (P.CandidateVer == (Version *)Pkg.CurrentVer() && P.InstallVer == 0)
1061          return MarkKeep(Pkg, false, FromUser, Depth+1);
1062       return true;
1063    }
1064
1065    // check if we are allowed to install the package
1066    if (IsInstallOk(Pkg,AutoInst,Depth,FromUser) == false)
1067       return false;
1068
1069    ActionGroup group(*this);
1070    P.iFlags &= ~AutoKept;
1071
1072    /* Target the candidate version and remove the autoflag. We reset the
1073       autoflag below if this was called recursively. Otherwise the user
1074       should have the ability to de-auto a package by changing its state */
1075    RemoveSizes(Pkg);
1076    RemoveStates(Pkg);
1077
1078    P.Mode = ModeInstall;
1079    P.InstallVer = P.CandidateVer;
1080
1081    if(FromUser)
1082      {
1083        // Set it to manual if it's a new install or already installed,
1084        // but only if its not marked by the autoremover (aptitude depend on this behavior)
1085        // or if we do automatic installation (aptitude never does it)
1086        if(P.Status == 2 || (Pkg->CurrentVer != 0 && (AutoInst == true || P.Marked == false)))
1087          P.Flags &= ~Flag::Auto;
1088      }
1089    else
1090      {
1091        // Set it to auto if this is a new install.
1092        if(P.Status == 2)
1093          P.Flags |= Flag::Auto;
1094      }
1095    if (P.CandidateVer == (Version *)Pkg.CurrentVer())
1096       P.Mode = ModeKeep;
1097
1098    AddStates(Pkg);
1099    Update(Pkg);
1100    AddSizes(Pkg);
1101
1102    if (AutoInst == false || _config->Find("APT::Solver", "internal") != "internal")
1103       return true;
1104
1105    if (DebugMarker == true)
1106       std::clog << OutputInDepth(Depth) << "MarkInstall " << Pkg << " FU=" << FromUser << std::endl;
1107
1108    DepIterator Dep = P.InstVerIter(*this).DependsList();
1109    for (; Dep.end() != true;)
1110    {
1111       // Grok or groups
1112       DepIterator Start = Dep;
1113       bool Result = true;
1114       unsigned Ors = 0;
1115       for (bool LastOR = true; Dep.end() == false && LastOR == true; ++Dep, ++Ors)
1116       {
1117          LastOR = (Dep->CompareOp & Dep::Or) == Dep::Or;
1118
1119          if ((DepState[Dep->ID] & DepInstall) == DepInstall)
1120             Result = false;
1121       }
1122
1123       // Dep is satisfied okay.
1124       if (Result == false)
1125          continue;
1126
1127       /* Check if this dep should be consider for install. If it is a user
1128          defined important dep and we are installed a new package then
1129          it will be installed. Otherwise we only check for important
1130          deps that have changed from the installed version */
1131       if (IsImportantDep(Start) == false)
1132          continue;
1133
1134       /* If we are in an or group locate the first or that can
1135          succeed. We have already cached this… */
1136       for (; Ors > 1 && (DepState[Start->ID] & DepCVer) != DepCVer; --Ors)
1137          ++Start;
1138
1139       /* unsatisfiable dependency: IsInstallOkDependenciesSatisfiableByCandidates
1140          would have prevented us to get here if not overridden, so just skip
1141          over the problem here as the frontend will know what it is doing */
1142       if (Ors == 1 && (DepState[Start->ID] &DepCVer) != DepCVer && Start.IsNegative() == false)
1143          continue;
1144
1145       /* Check if any ImportantDep() (but not Critical) were added
1146        * since we installed the package.  Also check for deps that
1147        * were satisfied in the past: for instance, if a version
1148        * restriction in a Recommends was tightened, upgrading the
1149        * package should follow that Recommends rather than causing the
1150        * dependency to be removed. (bug #470115)
1151        */
1152       if (Pkg->CurrentVer != 0 && ForceImportantDeps == false && Start.IsCritical() == false)
1153       {
1154          bool isNewImportantDep = true;
1155          bool isPreviouslySatisfiedImportantDep = false;
1156          for (DepIterator D = Pkg.CurrentVer().DependsList(); D.end() != true; ++D)
1157          {
1158             //FIXME: Should we handle or-group better here?
1159             // We do not check if the package we look for is part of the same or-group
1160             // we might find while searching, but could that really be a problem?
1161             if (D.IsCritical() == true || IsImportantDep(D) == false ||
1162                 Start.TargetPkg() != D.TargetPkg())
1163                continue;
1164
1165             isNewImportantDep = false;
1166
1167             while ((D->CompareOp & Dep::Or) != 0)
1168                ++D;
1169
1170             isPreviouslySatisfiedImportantDep = (((*this)[D] & DepGNow) != 0);
1171             if (isPreviouslySatisfiedImportantDep == true)
1172                break;
1173          }
1174
1175          if(isNewImportantDep == true)
1176          {
1177             if (DebugAutoInstall == true)
1178                std::clog << OutputInDepth(Depth) << "new important dependency: "
1179                          << Start.TargetPkg().FullName() << std::endl;
1180          }
1181          else if(isPreviouslySatisfiedImportantDep == true)
1182          {
1183             if (DebugAutoInstall == true)
1184                std::clog << OutputInDepth(Depth) << "previously satisfied important dependency on "
1185                          << Start.TargetPkg().FullName() << std::endl;
1186          }
1187          else
1188          {
1189             if (DebugAutoInstall == true)
1190                std::clog << OutputInDepth(Depth) << "ignore old unsatisfied important dependency on "
1191                          << Start.TargetPkg().FullName() << std::endl;
1192             continue;
1193          }
1194       }
1195
1196       /* This bit is for processing the possibility of an install/upgrade
1197          fixing the problem for "positive" dependencies */
1198       if (Start.IsNegative() == false && (DepState[Start->ID] & DepCVer) == DepCVer)
1199       {
1200          APT::VersionList verlist;
1201          pkgCache::VerIterator Cand = PkgState[Start.TargetPkg()->ID].CandidateVerIter(*this);
1202          if (Cand.end() == false && Start.IsSatisfied(Cand) == true)
1203             verlist.insert(Cand);
1204          for (PrvIterator Prv = Start.TargetPkg().ProvidesList(); Prv.end() != true; ++Prv)
1205          {
1206             pkgCache::VerIterator V = Prv.OwnerVer();
1207             pkgCache::VerIterator Cand = PkgState[Prv.OwnerPkg()->ID].CandidateVerIter(*this);
1208             if (Cand.end() == true || V != Cand || Start.IsSatisfied(Prv) == false)
1209                continue;
1210             verlist.insert(Cand);
1211          }
1212          CompareProviders comp(Start);
1213
1214          do {
1215             APT::VersionList::iterator InstVer = std::max_element(verlist.begin(), verlist.end(), comp);
1216
1217             if (InstVer == verlist.end())
1218                break;
1219
1220             pkgCache::PkgIterator InstPkg = InstVer.ParentPkg();
1221             if(DebugAutoInstall == true)
1222                std::clog << OutputInDepth(Depth) << "Installing " << InstPkg.Name()
1223                          << " as " << Start.DepType() << " of " << Pkg.Name()
1224                          << std::endl;
1225             if (MarkInstall(InstPkg, true, Depth + 1, false, ForceImportantDeps) == false)
1226             {
1227                verlist.erase(InstVer);
1228                continue;
1229             }
1230             // now check if we should consider it a automatic dependency or not
1231             if(InstPkg->CurrentVer == 0 && InstVer->Section != 0 && ConfigValueInSubTree("APT::Never-MarkAuto-Sections", InstVer.Section()))
1232             {
1233                if(DebugAutoInstall == true)
1234                   std::clog << OutputInDepth(Depth) << "Setting NOT as auto-installed (direct "
1235                             << Start.DepType() << " of pkg in APT::Never-MarkAuto-Sections)" << std::endl;
1236                MarkAuto(InstPkg, false);
1237             }
1238             break;
1239          } while(true);
1240          continue;
1241       }
1242       /* Negative dependencies have no or-group
1243          If the dependency isn't versioned, we try if an upgrade might solve the problem.
1244          Otherwise we remove the offender if needed */
1245       else if (Start.IsNegative() == true && Start->Type != pkgCache::Dep::Obsoletes)
1246       {
1247          SPtrArray<Version *> List = Start.AllTargets();
1248          pkgCache::PkgIterator TrgPkg = Start.TargetPkg();
1249          for (Version **I = List; *I != 0; I++)
1250          {
1251             VerIterator Ver(*this,*I);
1252             PkgIterator Pkg = Ver.ParentPkg();
1253
1254             /* The List includes all packages providing this dependency,
1255                even providers which are not installed, so skip them. */
1256             if (PkgState[Pkg->ID].InstallVer == 0)
1257                continue;
1258
1259             /* Ignore negative dependencies that we are not going to
1260                get installed */
1261             if (PkgState[Pkg->ID].InstallVer != *I)
1262                continue;
1263
1264             if ((Start->Version != 0 || TrgPkg != Pkg) &&
1265                 PkgState[Pkg->ID].CandidateVer != PkgState[Pkg->ID].InstallVer &&
1266                 PkgState[Pkg->ID].CandidateVer != *I &&
1267                 MarkInstall(Pkg,true,Depth + 1, false, ForceImportantDeps) == true)
1268                continue;
1269             else if (Start->Type == pkgCache::Dep::Conflicts ||
1270                      Start->Type == pkgCache::Dep::DpkgBreaks)
1271             {
1272                if(DebugAutoInstall == true)
1273                   std::clog << OutputInDepth(Depth)
1274                             << " Removing: " << Pkg.Name()
1275                             << std::endl;
1276                if (MarkDelete(Pkg,false,Depth + 1, false) == false)
1277                   break;
1278             }
1279          }
1280          continue;
1281       }
1282    }
1283
1284    return Dep.end() == true;
1285 }
1286                                                                         /*}}}*/
1287 // DepCache::IsInstallOk - check if it is ok to install this package    /*{{{*/
1288 // ---------------------------------------------------------------------
1289 /* The default implementation checks if the installation of an M-A:same
1290    package would lead us into a version-screw and if so forbids it.
1291    dpkg holds are enforced by the private IsModeChangeOk */
1292 bool pkgDepCache::IsInstallOk(PkgIterator const &Pkg,bool AutoInst,
1293                               unsigned long Depth, bool FromUser)
1294 {
1295    return IsInstallOkMultiArchSameVersionSynced(Pkg,AutoInst, Depth, FromUser) &&
1296       IsInstallOkDependenciesSatisfiableByCandidates(Pkg,AutoInst, Depth, FromUser);
1297 }
1298 bool pkgDepCache::IsInstallOkMultiArchSameVersionSynced(PkgIterator const &Pkg,
1299       bool const /*AutoInst*/, unsigned long const Depth, bool const FromUser)
1300 {
1301    if (FromUser == true) // as always: user is always right
1302       return true;
1303
1304    // if we have checked before and it was okay, it will still be okay
1305    if (PkgState[Pkg->ID].Mode == ModeInstall &&
1306          PkgState[Pkg->ID].InstallVer == PkgState[Pkg->ID].CandidateVer)
1307       return true;
1308
1309    // ignore packages with none-M-A:same candidates
1310    VerIterator const CandVer = PkgState[Pkg->ID].CandidateVerIter(*this);
1311    if (unlikely(CandVer.end() == true) || CandVer == Pkg.CurrentVer() ||
1312          (CandVer->MultiArch & pkgCache::Version::Same) != pkgCache::Version::Same)
1313       return true;
1314
1315    GrpIterator const Grp = Pkg.Group();
1316    for (PkgIterator P = Grp.PackageList(); P.end() == false; P = Grp.NextPkg(P))
1317    {
1318       // not installed or self-check: fine by definition
1319       if (P->CurrentVer == 0 || P == Pkg)
1320          continue;
1321
1322       // not having a candidate or being in sync
1323       // (simple string-compare as stuff like '1' == '0:1-0' can't happen here)
1324       VerIterator CV = PkgState[P->ID].CandidateVerIter(*this);
1325       if (CV.end() == true || strcmp(Pkg.CandVersion(), CV.VerStr()) == 0)
1326          continue;
1327
1328       // packages losing M-A:same can be out-of-sync
1329       if ((CV->MultiArch & pkgCache::Version::Same) != pkgCache::Version::Same)
1330          continue;
1331
1332       // not downloadable means the package is obsolete, so allow out-of-sync
1333       if (CV.Downloadable() == false)
1334          continue;
1335
1336       PkgState[Pkg->ID].iFlags |= AutoKept;
1337       if (unlikely(DebugMarker == true))
1338          std::clog << OutputInDepth(Depth) << "Ignore MarkInstall of " << Pkg
1339             << " as it is not in sync with its M-A:same sibling " << P
1340             << " (" << Pkg.CandVersion() << " != " << CV.VerStr() << ")" << std::endl;
1341       return false;
1342    }
1343
1344    return true;
1345 }
1346 bool pkgDepCache::IsInstallOkDependenciesSatisfiableByCandidates(PkgIterator const &Pkg,
1347       bool const AutoInst, unsigned long const Depth, bool const /*FromUser*/)
1348 {
1349    if (AutoInst == false)
1350       return true;
1351
1352    VerIterator const CandVer = PkgState[Pkg->ID].CandidateVerIter(*this);
1353    if (unlikely(CandVer.end() == true) || CandVer == Pkg.CurrentVer())
1354       return true;
1355
1356    for (DepIterator Dep = CandVer.DependsList(); Dep.end() != true;)
1357    {
1358       // Grok or groups
1359       DepIterator Start = Dep;
1360       bool Result = true;
1361       unsigned Ors = 0;
1362       for (bool LastOR = true; Dep.end() == false && LastOR == true; ++Dep, ++Ors)
1363       {
1364          LastOR = (Dep->CompareOp & Dep::Or) == Dep::Or;
1365
1366          if ((DepState[Dep->ID] & DepInstall) == DepInstall)
1367             Result = false;
1368       }
1369
1370       if (Start.IsCritical() == false || Start.IsNegative() == true || Result == false)
1371          continue;
1372
1373       /* If we are in an or group locate the first or that can succeed.
1374          We have already cached this… */
1375       for (; Ors > 1 && (DepState[Start->ID] & DepCVer) != DepCVer; --Ors)
1376          ++Start;
1377
1378       if (Ors == 1 && (DepState[Start->ID] &DepCVer) != DepCVer)
1379       {
1380          if (DebugAutoInstall == true)
1381             std::clog << OutputInDepth(Depth) << Start << " can't be satisfied!" << std::endl;
1382
1383          // the dependency is critical, but can't be installed, so discard the candidate
1384          // as the problemresolver will trip over it otherwise trying to install it (#735967)
1385          if (Pkg->CurrentVer != 0 && (PkgState[Pkg->ID].iFlags & Protected) != Protected)
1386             SetCandidateVersion(Pkg.CurrentVer());
1387          return false;
1388       }
1389    }
1390
1391    return true;
1392 }
1393                                                                         /*}}}*/
1394 // DepCache::SetReInstall - Set the reinstallation flag                 /*{{{*/
1395 // ---------------------------------------------------------------------
1396 /* */
1397 void pkgDepCache::SetReInstall(PkgIterator const &Pkg,bool To)
1398 {
1399    if (unlikely(Pkg.end() == true))
1400       return;
1401
1402    APT::PackageList pkglist;
1403    if (Pkg->CurrentVer != 0 &&
1404        (Pkg.CurrentVer()-> MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same)
1405    {
1406       pkgCache::GrpIterator Grp = Pkg.Group();
1407       for (pkgCache::PkgIterator P = Grp.PackageList(); P.end() == false; P = Grp.NextPkg(P))
1408       {
1409          if (P->CurrentVer != 0)
1410             pkglist.insert(P);
1411       }
1412    }
1413    else
1414       pkglist.insert(Pkg);
1415
1416    ActionGroup group(*this);
1417
1418    for (APT::PackageList::const_iterator Pkg = pkglist.begin(); Pkg != pkglist.end(); ++Pkg)
1419    {
1420       RemoveSizes(Pkg);
1421       RemoveStates(Pkg);
1422
1423       StateCache &P = PkgState[Pkg->ID];
1424       if (To == true)
1425          P.iFlags |= ReInstall;
1426       else
1427          P.iFlags &= ~ReInstall;
1428
1429       AddStates(Pkg);
1430       AddSizes(Pkg);
1431    }
1432 }
1433                                                                         /*}}}*/
1434 // DepCache::SetCandidateVersion - Change the candidate version         /*{{{*/
1435 // ---------------------------------------------------------------------
1436 /* */
1437 void pkgDepCache::SetCandidateVersion(VerIterator TargetVer)
1438 {
1439    pkgCache::PkgIterator Pkg = TargetVer.ParentPkg();
1440    StateCache &P = PkgState[Pkg->ID];
1441
1442    if (P.CandidateVer == TargetVer)
1443       return;
1444
1445    ActionGroup group(*this);
1446
1447    RemoveSizes(Pkg);
1448    RemoveStates(Pkg);
1449
1450    if (P.CandidateVer == P.InstallVer && P.Install() == true)
1451       P.InstallVer = (Version *)TargetVer;
1452    P.CandidateVer = (Version *)TargetVer;
1453    P.Update(Pkg,*this);
1454
1455    AddStates(Pkg);
1456    Update(Pkg);
1457    AddSizes(Pkg);
1458
1459 }
1460                                                                         /*}}}*/
1461 // DepCache::SetCandidateRelease - Change the candidate version         /*{{{*/
1462 // ---------------------------------------------------------------------
1463 /* changes the candidate of a package and walks over all its dependencies
1464    to check if it needs to change the candidate of the dependency, too,
1465    to reach a installable versionstate */
1466 bool pkgDepCache::SetCandidateRelease(pkgCache::VerIterator TargetVer,
1467                                         std::string const &TargetRel)
1468 {
1469    std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> > Changed;
1470    return SetCandidateRelease(TargetVer, TargetRel, Changed);
1471 }
1472 bool pkgDepCache::SetCandidateRelease(pkgCache::VerIterator TargetVer,
1473                                         std::string const &TargetRel,
1474                                         std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> > &Changed)
1475 {
1476    ActionGroup group(*this);
1477    SetCandidateVersion(TargetVer);
1478
1479    if (TargetRel == "installed" || TargetRel == "candidate") // both doesn't make sense in this context
1480       return true;
1481
1482    pkgVersionMatch Match(TargetRel, pkgVersionMatch::Release);
1483    // save the position of the last element we will not undo - if we have to
1484    std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> >::iterator newChanged = --(Changed.end());
1485
1486    for (pkgCache::DepIterator D = TargetVer.DependsList(); D.end() == false; ++D)
1487    {
1488       if (D->Type != pkgCache::Dep::PreDepends && D->Type != pkgCache::Dep::Depends &&
1489           ((D->Type != pkgCache::Dep::Recommends && D->Type != pkgCache::Dep::Suggests) ||
1490            IsImportantDep(D) == false))
1491          continue;
1492
1493       // walk over an or-group and check if we need to do anything
1494       // for simpilicity no or-group is handled as a or-group including one dependency
1495       pkgCache::DepIterator Start = D;
1496       bool itsFine = false;
1497       for (bool stillOr = true; stillOr == true; ++Start)
1498       {
1499          stillOr = (Start->CompareOp & Dep::Or) == Dep::Or;
1500          pkgCache::PkgIterator const P = Start.TargetPkg();
1501          // virtual packages can't be a solution
1502          if (P.end() == true || (P->ProvidesList == 0 && P->VersionList == 0))
1503             continue;
1504          pkgCache::VerIterator const Cand = PkgState[P->ID].CandidateVerIter(*this);
1505          // no versioned dependency - but is it installable?
1506          if (Start.TargetVer() == 0 || Start.TargetVer()[0] == '\0')
1507          {
1508             // Check if one of the providers is installable
1509             if (P->ProvidesList != 0)
1510             {
1511                pkgCache::PrvIterator Prv = P.ProvidesList();
1512                for (; Prv.end() == false; ++Prv)
1513                {
1514                   pkgCache::VerIterator const C = PkgState[Prv.OwnerPkg()->ID].CandidateVerIter(*this);
1515                   if (C.end() == true || C != Prv.OwnerVer() ||
1516                       (VersionState(C.DependsList(), DepInstall, DepCandMin, DepCandPolicy) & DepCandMin) != DepCandMin)
1517                      continue;
1518                   break;
1519                }
1520                if (Prv.end() == true)
1521                   continue;
1522             }
1523             // no providers, so check if we have an installable candidate version
1524             else if (Cand.end() == true ||
1525                 (VersionState(Cand.DependsList(), DepInstall, DepCandMin, DepCandPolicy) & DepCandMin) != DepCandMin)
1526                continue;
1527             itsFine = true;
1528             break;
1529          }
1530          if (Cand.end() == true)
1531             continue;
1532          // check if the current candidate is enough for the versioned dependency - and installable?
1533          if (Start.IsSatisfied(Cand) == true &&
1534              (VersionState(Cand.DependsList(), DepInstall, DepCandMin, DepCandPolicy) & DepCandMin) == DepCandMin)
1535          {
1536             itsFine = true;
1537             break;
1538          }
1539       }
1540
1541       if (itsFine == true) {
1542          // something in the or-group was fine, skip all other members
1543          for (; (D->CompareOp & Dep::Or) == Dep::Or; ++D);
1544          continue;
1545       }
1546
1547       // walk again over the or-group and check each if a candidate switch would help
1548       itsFine = false;
1549       for (bool stillOr = true; stillOr == true; ++D)
1550       {
1551          stillOr = (D->CompareOp & Dep::Or) == Dep::Or;
1552          // changing candidate will not help if the dependency is not versioned
1553          if (D.TargetVer() == 0 || D.TargetVer()[0] == '\0')
1554          {
1555             if (stillOr == true)
1556                continue;
1557             break;
1558          }
1559
1560          pkgCache::VerIterator V;
1561          if (TargetRel == "newest")
1562             V = D.TargetPkg().VersionList();
1563          else
1564             V = Match.Find(D.TargetPkg());
1565
1566          // check if the version from this release could satisfy the dependency
1567          if (V.end() == true || D.IsSatisfied(V) == false)
1568          {
1569             if (stillOr == true)
1570                continue;
1571             break;
1572          }
1573
1574          pkgCache::VerIterator oldCand = PkgState[D.TargetPkg()->ID].CandidateVerIter(*this);
1575          if (V == oldCand)
1576          {
1577             // Do we already touched this Version? If so, their versioned dependencies are okay, no need to check again
1578             for (std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> >::const_iterator c = Changed.begin();
1579                  c != Changed.end(); ++c)
1580             {
1581                if (c->first->ParentPkg != V->ParentPkg)
1582                   continue;
1583                itsFine = true;
1584                break;
1585             }
1586          }
1587
1588          if (itsFine == false)
1589          {
1590             // change the candidate
1591             Changed.push_back(make_pair(V, TargetVer));
1592             if (SetCandidateRelease(V, TargetRel, Changed) == false)
1593             {
1594                if (stillOr == false)
1595                   break;
1596                // undo the candidate changing
1597                SetCandidateVersion(oldCand);
1598                Changed.pop_back();
1599                continue;
1600             }
1601             itsFine = true;
1602          }
1603
1604          // something in the or-group was fine, skip all other members
1605          for (; (D->CompareOp & Dep::Or) == Dep::Or; ++D);
1606          break;
1607       }
1608
1609       if (itsFine == false && (D->Type == pkgCache::Dep::PreDepends || D->Type == pkgCache::Dep::Depends))
1610       {
1611          // undo all changes which aren't lead to a solution
1612          for (std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> >::const_iterator c = ++newChanged;
1613               c != Changed.end(); ++c)
1614             SetCandidateVersion(c->first);
1615          Changed.erase(newChanged, Changed.end());
1616          return false;
1617       }
1618    }
1619    return true;
1620 }
1621                                                                         /*}}}*/
1622 // DepCache::MarkAuto - set the Auto flag for a package                 /*{{{*/
1623 // ---------------------------------------------------------------------
1624 /* */
1625 void pkgDepCache::MarkAuto(const PkgIterator &Pkg, bool Auto)
1626 {
1627   StateCache &state = PkgState[Pkg->ID];
1628
1629   ActionGroup group(*this);
1630
1631   if(Auto)
1632     state.Flags |= Flag::Auto;
1633   else
1634     state.Flags &= ~Flag::Auto;
1635 }
1636                                                                         /*}}}*/
1637 // StateCache::Update - Compute the various static display things       /*{{{*/
1638 // ---------------------------------------------------------------------
1639 /* This is called whenever the Candidate version changes. */
1640 void pkgDepCache::StateCache::Update(PkgIterator Pkg,pkgCache &Cache)
1641 {
1642    // Some info
1643    VerIterator Ver = CandidateVerIter(Cache);
1644
1645    // Use a null string or the version string
1646    if (Ver.end() == true)
1647       CandVersion = "";
1648    else
1649       CandVersion = Ver.VerStr();
1650
1651    // Find the current version
1652    CurVersion = "";
1653    if (Pkg->CurrentVer != 0)
1654       CurVersion = Pkg.CurrentVer().VerStr();
1655
1656    // Strip off the epochs for display
1657    CurVersion = StripEpoch(CurVersion);
1658    CandVersion = StripEpoch(CandVersion);
1659
1660    // Figure out if its up or down or equal
1661    Status = Ver.CompareVer(Pkg.CurrentVer());
1662    if (Pkg->CurrentVer == 0 || Pkg->VersionList == 0 || CandidateVer == 0)
1663      Status = 2;
1664 }
1665                                                                         /*}}}*/
1666 // StateCache::StripEpoch - Remove the epoch specifier from the version /*{{{*/
1667 // ---------------------------------------------------------------------
1668 /* */
1669 const char *pkgDepCache::StateCache::StripEpoch(const char *Ver)
1670 {
1671    if (Ver == 0)
1672       return 0;
1673
1674    // Strip any epoch
1675    for (const char *I = Ver; *I != 0; I++)
1676       if (*I == ':')
1677          return I + 1;
1678    return Ver;
1679 }
1680                                                                         /*}}}*/
1681 // Policy::GetCandidateVer - Returns the Candidate install version      /*{{{*/
1682 // ---------------------------------------------------------------------
1683 /* The default just returns the highest available version that is not
1684    a source and automatic. */
1685 pkgCache::VerIterator pkgDepCache::Policy::GetCandidateVer(PkgIterator const &Pkg)
1686 {
1687    /* Not source/not automatic versions cannot be a candidate version
1688       unless they are already installed */
1689    VerIterator Last;
1690
1691    for (VerIterator I = Pkg.VersionList(); I.end() == false; ++I)
1692    {
1693       if (Pkg.CurrentVer() == I)
1694          return I;
1695
1696       for (VerFileIterator J = I.FileList(); J.end() == false; ++J)
1697       {
1698          if ((J.File()->Flags & Flag::NotSource) != 0)
1699             continue;
1700
1701          /* Stash the highest version of a not-automatic source, we use it
1702             if there is nothing better */
1703          if ((J.File()->Flags & Flag::NotAutomatic) != 0 ||
1704              (J.File()->Flags & Flag::ButAutomaticUpgrades) != 0)
1705          {
1706             if (Last.end() == true)
1707                Last = I;
1708             continue;
1709          }
1710
1711          return I;
1712       }
1713    }
1714
1715    return Last;
1716 }
1717                                                                         /*}}}*/
1718 // Policy::IsImportantDep - True if the dependency is important         /*{{{*/
1719 // ---------------------------------------------------------------------
1720 /* */
1721 bool pkgDepCache::Policy::IsImportantDep(DepIterator const &Dep)
1722 {
1723    if(Dep.IsCritical())
1724       return true;
1725    else if(Dep->Type == pkgCache::Dep::Recommends)
1726    {
1727       if (InstallRecommends)
1728          return true;
1729       // we suport a special mode to only install-recommends for certain
1730       // sections
1731       // FIXME: this is a meant as a temporarly solution until the
1732       //        recommends are cleaned up
1733       const char *sec = Dep.ParentVer().Section();
1734       if (sec && ConfigValueInSubTree("APT::Install-Recommends-Sections", sec))
1735          return true;
1736    }
1737    else if(Dep->Type == pkgCache::Dep::Suggests)
1738       return InstallSuggests;
1739
1740    return false;
1741 }
1742                                                                         /*}}}*/
1743 // Policy::GetPriority - Get the priority of the package pin            /*{{{*/
1744 APT_CONST signed short pkgDepCache::Policy::GetPriority(pkgCache::PkgIterator const &/*Pkg*/)
1745 { return 0; }
1746 APT_CONST signed short pkgDepCache::Policy::GetPriority(pkgCache::PkgFileIterator const &/*File*/)
1747 { return 0; }
1748                                                                         /*}}}*/
1749 pkgDepCache::InRootSetFunc *pkgDepCache::GetRootSetFunc()               /*{{{*/
1750 {
1751   DefaultRootSetFunc *f = new DefaultRootSetFunc;
1752   if(f->wasConstructedSuccessfully())
1753     return f;
1754   else
1755     {
1756       delete f;
1757       return NULL;
1758     }
1759 }
1760                                                                         /*}}}*/
1761 bool pkgDepCache::MarkFollowsRecommends()
1762 {
1763   return _config->FindB("APT::AutoRemove::RecommendsImportant", true);
1764 }
1765
1766 bool pkgDepCache::MarkFollowsSuggests()
1767 {
1768   return _config->FindB("APT::AutoRemove::SuggestsImportant", true);
1769 }
1770
1771 // pkgDepCache::MarkRequired - the main mark algorithm                  /*{{{*/
1772 bool pkgDepCache::MarkRequired(InRootSetFunc &userFunc)
1773 {
1774    if (_config->Find("APT::Solver", "internal") != "internal")
1775       return true;
1776
1777    bool follow_recommends;
1778    bool follow_suggests;
1779    bool debug_autoremove = _config->FindB("Debug::pkgAutoRemove",false);
1780
1781    // init the states
1782    for(PkgIterator p = PkgBegin(); !p.end(); ++p)
1783    {
1784       PkgState[p->ID].Marked  = false;
1785       PkgState[p->ID].Garbage = false;
1786
1787       // debug output
1788       if(debug_autoremove && PkgState[p->ID].Flags & Flag::Auto)
1789          std::clog << "AutoDep: " << p.FullName() << std::endl;
1790    }
1791
1792    // init vars
1793    follow_recommends = MarkFollowsRecommends();
1794    follow_suggests   = MarkFollowsSuggests();
1795
1796    // do the mark part, this is the core bit of the algorithm
1797    for(PkgIterator p = PkgBegin(); !p.end(); ++p)
1798    {
1799       if(!(PkgState[p->ID].Flags & Flag::Auto) ||
1800           (p->Flags & Flag::Essential) ||
1801           (p->Flags & Flag::Important) ||
1802           userFunc.InRootSet(p) ||
1803           // be nice even then a required package violates the policy (#583517)
1804           // and do the full mark process also for required packages
1805           (p.CurrentVer().end() != true &&
1806            p.CurrentVer()->Priority == pkgCache::State::Required) ||
1807           // packages which can't be changed (like holds) can't be garbage
1808           (IsModeChangeOk(ModeGarbage, p, 0, false) == false))
1809       {
1810          // the package is installed (and set to keep)
1811          if(PkgState[p->ID].Keep() && !p.CurrentVer().end())
1812             MarkPackage(p, p.CurrentVer(),
1813                         follow_recommends, follow_suggests);
1814          // the package is to be installed
1815          else if(PkgState[p->ID].Install())
1816             MarkPackage(p, PkgState[p->ID].InstVerIter(*this),
1817                         follow_recommends, follow_suggests);
1818       }
1819    }
1820
1821    return true;
1822 }
1823                                                                         /*}}}*/
1824 // MarkPackage - mark a single package in Mark-and-Sweep                /*{{{*/
1825 void pkgDepCache::MarkPackage(const pkgCache::PkgIterator &pkg,
1826                               const pkgCache::VerIterator &ver,
1827                               bool const &follow_recommends,
1828                               bool const &follow_suggests)
1829 {
1830    pkgDepCache::StateCache &state = PkgState[pkg->ID];
1831
1832    // if we are marked already we are done
1833    if(state.Marked)
1834       return;
1835
1836    VerIterator const currver = pkg.CurrentVer();
1837    VerIterator const instver = state.InstVerIter(*this);
1838
1839 #if 0
1840    VerIterator const candver = state.CandidateVerIter(*this);
1841
1842    // If a package was garbage-collected but is now being marked, we
1843    // should re-select it
1844    // For cases when a pkg is set to upgrade and this trigger the
1845    // removal of a no-longer used dependency.  if the pkg is set to
1846    // keep again later it will result in broken deps
1847    if(state.Delete() && state.RemoveReason = Unused)
1848    {
1849       if(ver==candver)
1850          mark_install(pkg, false, false, NULL);
1851       else if(ver==pkg.CurrentVer())
1852          MarkKeep(pkg, false, false);
1853
1854       instver=state.InstVerIter(*this);
1855    }
1856 #endif
1857
1858    // For packages that are not going to be removed, ignore versions
1859    // other than the InstVer.  For packages that are going to be
1860    // removed, ignore versions other than the current version.
1861    if(!(ver == instver && !instver.end()) &&
1862       !(ver == currver && instver.end() && !ver.end()))
1863       return;
1864
1865    bool const debug_autoremove = _config->FindB("Debug::pkgAutoRemove", false);
1866
1867    if(debug_autoremove)
1868      {
1869        std::clog << "Marking: " << pkg.FullName();
1870        if(!ver.end())
1871          std::clog << " " << ver.VerStr();
1872        if(!currver.end())
1873          std::clog << ", Curr=" << currver.VerStr();
1874        if(!instver.end())
1875          std::clog << ", Inst=" << instver.VerStr();
1876        std::clog << std::endl;
1877      }
1878
1879    state.Marked=true;
1880
1881    if(ver.end() == true)
1882       return;
1883
1884      for(DepIterator d = ver.DependsList(); !d.end(); ++d)
1885      {
1886         if(d->Type == Dep::Depends ||
1887            d->Type == Dep::PreDepends ||
1888            (follow_recommends &&
1889             d->Type == Dep::Recommends) ||
1890            (follow_suggests &&
1891             d->Type == Dep::Suggests))
1892         {
1893            // Try all versions of this package.
1894            for(VerIterator V = d.TargetPkg().VersionList();
1895                !V.end(); ++V)
1896            {
1897               if(d.IsSatisfied(V))
1898               {
1899                 if(debug_autoremove)
1900                   {
1901                     std::clog << "Following dep: " << d.ParentPkg().FullName()
1902                               << " " << d.ParentVer().VerStr() << " "
1903                               << d.DepType() << " " << d.TargetPkg().FullName();
1904                     if((d->CompareOp & ~pkgCache::Dep::Or) != pkgCache::Dep::NoOp)
1905                       {
1906                         std::clog << " (" << d.CompType() << " "
1907                                   << d.TargetVer() << ")";
1908                       }
1909                     std::clog << std::endl;
1910                   }
1911                  MarkPackage(V.ParentPkg(), V,
1912                              follow_recommends, follow_suggests);
1913               }
1914            }
1915            // Now try virtual packages
1916            for(PrvIterator prv=d.TargetPkg().ProvidesList();
1917                !prv.end(); ++prv)
1918            {
1919               if(d.IsSatisfied(prv))
1920               {
1921                 if(debug_autoremove)
1922                   {
1923                     std::clog << "Following dep: " << d.ParentPkg().FullName() << " "
1924                               << d.ParentVer().VerStr() << " "
1925                               << d.DepType() << " " << d.TargetPkg().FullName() << " ";
1926                     if((d->CompareOp & ~pkgCache::Dep::Or) != pkgCache::Dep::NoOp)
1927                       {
1928                         std::clog << " (" << d.CompType() << " "
1929                                   << d.TargetVer() << ")";
1930                       }
1931                     std::clog << ", provided by "
1932                               << prv.OwnerPkg().FullName() << " "
1933                               << prv.OwnerVer().VerStr()
1934                               << std::endl;
1935                   }
1936
1937                  MarkPackage(prv.OwnerPkg(), prv.OwnerVer(),
1938                              follow_recommends, follow_suggests);
1939               }
1940            }
1941         }
1942      }
1943 }
1944                                                                         /*}}}*/
1945 bool pkgDepCache::Sweep()                                               /*{{{*/
1946 {
1947    bool debug_autoremove = _config->FindB("Debug::pkgAutoRemove",false);
1948
1949    // do the sweep
1950    for(PkgIterator p=PkgBegin(); !p.end(); ++p)
1951    {
1952      StateCache &state=PkgState[p->ID];
1953
1954      // skip required packages
1955      if (!p.CurrentVer().end() &&
1956          (p.CurrentVer()->Priority == pkgCache::State::Required))
1957         continue;
1958
1959      // if it is not marked and it is installed, it's garbage
1960      if(!state.Marked && (!p.CurrentVer().end() || state.Install()))
1961      {
1962         state.Garbage=true;
1963         if(debug_autoremove)
1964            std::clog << "Garbage: " << p.FullName() << std::endl;
1965      }
1966   }
1967
1968    return true;
1969 }
1970                                                                         /*}}}*/
1971 // DepCache::MarkAndSweep                                               /*{{{*/
1972 bool pkgDepCache::MarkAndSweep(InRootSetFunc &rootFunc)
1973 {
1974    return MarkRequired(rootFunc) && Sweep();
1975 }
1976 bool pkgDepCache::MarkAndSweep()
1977 {
1978    std::auto_ptr<InRootSetFunc> f(GetRootSetFunc());
1979    if(f.get() != NULL)
1980       return MarkAndSweep(*f.get());
1981    else
1982       return false;
1983 }
1984                                                                         /*}}}*/