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