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