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