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