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