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