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