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