apt-pkg/depcache.cc

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