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