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       if ((A->CurrentVer == 0 || B->CurrentVer == 0) && A->CurrentVer != B->CurrentVer)
1020          return A->CurrentVer == 0;
1021       // Prefer packages in the same group as the target; e.g. foo:i386, foo:amd64
1022       if (A->Group != B->Group)
1023       {
1024          if (A->Group == Pkg->Group && B->Group != Pkg->Group)
1025             return false;
1026          else if (B->Group == Pkg->Group && A->Group != Pkg->Group)
1027             return true;
1028       }
1029       // we like essentials
1030       if ((A->Flags & pkgCache::Flag::Essential) != (B->Flags & pkgCache::Flag::Essential))
1031       {
1032          if ((A->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
1033             return false;
1034          else if ((B->Flags & pkgCache::Flag::Essential) == pkgCache::Flag::Essential)
1035             return true;
1036       }
1037       if ((A->Flags & pkgCache::Flag::Important) != (B->Flags & pkgCache::Flag::Important))
1038       {
1039          if ((A->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important)
1040             return false;
1041          else if ((B->Flags & pkgCache::Flag::Important) == pkgCache::Flag::Important)
1042             return true;
1043       }
1044       // prefer native architecture
1045       if (strcmp(A.Arch(), B.Arch()) != 0)
1046       {
1047          if (strcmp(A.Arch(), A.Cache()->NativeArch()) == 0)
1048             return false;
1049          else if (strcmp(B.Arch(), B.Cache()->NativeArch()) == 0)
1050             return true;
1051          std::vector<std::string> archs = APT::Configuration::getArchitectures();
1052          for (std::vector<std::string>::const_iterator a = archs.begin(); a != archs.end(); ++a)
1053             if (*a == A.Arch())
1054                return false;
1055             else if (*a == B.Arch())
1056                return true;
1057       }
1058       // higher priority seems like a good idea
1059       if (AV->Priority != BV->Priority)
1060          return AV->Priority > BV->Priority;
1061       // unable to decide…
1062       return A->ID < B->ID;
1063    }
1064 };
1065 bool pkgDepCache::MarkInstall(PkgIterator const &Pkg,bool AutoInst,
1066                               unsigned long Depth, bool FromUser,
1067                               bool ForceImportantDeps)
1068 {
1069    if (IsModeChangeOk(ModeInstall, Pkg, Depth, FromUser) == false)
1070       return false;
1071
1072    StateCache &P = PkgState[Pkg->ID];
1073
1074    // See if there is even any possible instalation candidate
1075    if (P.CandidateVer == 0)
1076       return false;
1077
1078    /* Check that it is not already marked for install and that it can be
1079       installed */
1080    if ((P.InstPolicyBroken() == false && P.InstBroken() == false) &&
1081        (P.Mode == ModeInstall ||
1082         P.CandidateVer == (Version *)Pkg.CurrentVer()))
1083    {
1084       if (P.CandidateVer == (Version *)Pkg.CurrentVer() && P.InstallVer == 0)
1085          return MarkKeep(Pkg, false, FromUser, Depth+1);
1086       return true;
1087    }
1088
1089    // check if we are allowed to install the package
1090    if (IsInstallOk(Pkg,AutoInst,Depth,FromUser) == false)
1091       return false;
1092
1093    ActionGroup group(*this);
1094    P.iFlags &= ~AutoKept;
1095
1096    /* Target the candidate version and remove the autoflag. We reset the
1097       autoflag below if this was called recursively. Otherwise the user
1098       should have the ability to de-auto a package by changing its state */
1099    RemoveSizes(Pkg);
1100    RemoveStates(Pkg);
1101
1102    P.Mode = ModeInstall;
1103    P.InstallVer = P.CandidateVer;
1104
1105    if(FromUser)
1106      {
1107        // Set it to manual if it's a new install or already installed,
1108        // but only if its not marked by the autoremover (aptitude depend on this behavior)
1109        // or if we do automatic installation (aptitude never does it)
1110        if(P.Status == 2 || (Pkg->CurrentVer != 0 && (AutoInst == true || P.Marked == false)))
1111          P.Flags &= ~Flag::Auto;
1112      }
1113    else
1114      {
1115        // Set it to auto if this is a new install.
1116        if(P.Status == 2)
1117          P.Flags |= Flag::Auto;
1118      }
1119    if (P.CandidateVer == (Version *)Pkg.CurrentVer())
1120       P.Mode = ModeKeep;
1121
1122    AddStates(Pkg);
1123    Update(Pkg);
1124    AddSizes(Pkg);
1125
1126    if (AutoInst == false || _config->Find("APT::Solver", "internal") != "internal")
1127       return true;
1128
1129    if (DebugMarker == true)
1130       std::clog << OutputInDepth(Depth) << "MarkInstall " << Pkg << " FU=" << FromUser << std::endl;
1131
1132    bool MoveAutoBitToDependencies = false;
1133    VerIterator const PV = P.InstVerIter(*this);
1134    if (unlikely(PV.end() == true))
1135       return false;
1136    else if (PV->Section != 0 && (P.Flags & Flag::Auto) != Flag::Auto)
1137    {
1138       VerIterator const CurVer = Pkg.CurrentVer();
1139       if (CurVer.end() == false && CurVer->Section != 0 && strcmp(CurVer.Section(), PV.Section()) != 0)
1140       {
1141          bool const CurVerInMoveSection = ConfigValueInSubTree("APT::Move-Autobit-Sections", CurVer.Section());
1142          bool const InstVerInMoveSection = ConfigValueInSubTree("APT::Move-Autobit-Sections", PV.Section());
1143          MoveAutoBitToDependencies = (CurVerInMoveSection == false && InstVerInMoveSection == true);
1144          if (MoveAutoBitToDependencies == true)
1145          {
1146             if(DebugAutoInstall == true)
1147                std::clog << OutputInDepth(Depth) << "Setting " << Pkg.FullName(false) << " as auto-installed, moving manual to its dependencies" << std::endl;
1148             MarkAuto(Pkg, true);
1149          }
1150       }
1151    }
1152
1153    DepIterator Dep = PV.DependsList();
1154    for (; Dep.end() != true;)
1155    {
1156       // Grok or groups
1157       DepIterator Start = Dep;
1158       bool Result = true;
1159       unsigned Ors = 0;
1160       for (bool LastOR = true; Dep.end() == false && LastOR == true; ++Dep, ++Ors)
1161       {
1162          LastOR = (Dep->CompareOp & Dep::Or) == Dep::Or;
1163
1164          if ((DepState[Dep->ID] & DepInstall) == DepInstall)
1165             Result = false;
1166       }
1167
1168       // Dep is satisfied okay.
1169       if (Result == false)
1170          continue;
1171
1172       /* Check if this dep should be consider for install. If it is a user
1173          defined important dep and we are installed a new package then
1174          it will be installed. Otherwise we only check for important
1175          deps that have changed from the installed version */
1176       if (IsImportantDep(Start) == false)
1177          continue;
1178
1179       /* If we are in an or group locate the first or that can
1180          succeed. We have already cached this… */
1181       for (; Ors > 1 && (DepState[Start->ID] & DepCVer) != DepCVer; --Ors)
1182          ++Start;
1183
1184       /* unsatisfiable dependency: IsInstallOkDependenciesSatisfiableByCandidates
1185          would have prevented us to get here if not overridden, so just skip
1186          over the problem here as the front-end will know what it is doing */
1187       if (Ors == 1 && (DepState[Start->ID] &DepCVer) != DepCVer && Start.IsNegative() == false)
1188          continue;
1189
1190       /* Check if any ImportantDep() (but not Critical) were added
1191        * since we installed the package.  Also check for deps that
1192        * were satisfied in the past: for instance, if a version
1193        * restriction in a Recommends was tightened, upgrading the
1194        * package should follow that Recommends rather than causing the
1195        * dependency to be removed. (bug #470115)
1196        */
1197       if (Pkg->CurrentVer != 0 && ForceImportantDeps == false && Start.IsCritical() == false)
1198       {
1199          bool isNewImportantDep = true;
1200          bool isPreviouslySatisfiedImportantDep = false;
1201          for (DepIterator D = Pkg.CurrentVer().DependsList(); D.end() != true; ++D)
1202          {
1203             //FIXME: Should we handle or-group better here?
1204             // We do not check if the package we look for is part of the same or-group
1205             // we might find while searching, but could that really be a problem?
1206             if (D.IsCritical() == true || IsImportantDep(D) == false ||
1207                 Start.TargetPkg() != D.TargetPkg())
1208                continue;
1209
1210             isNewImportantDep = false;
1211
1212             while ((D->CompareOp & Dep::Or) != 0)
1213                ++D;
1214
1215             isPreviouslySatisfiedImportantDep = (((*this)[D] & DepGNow) != 0);
1216             if (isPreviouslySatisfiedImportantDep == true)
1217                break;
1218          }
1219
1220          if(isNewImportantDep == true)
1221          {
1222             if (DebugAutoInstall == true)
1223                std::clog << OutputInDepth(Depth) << "new important dependency: "
1224                          << Start.TargetPkg().FullName() << std::endl;
1225          }
1226          else if(isPreviouslySatisfiedImportantDep == true)
1227          {
1228             if (DebugAutoInstall == true)
1229                std::clog << OutputInDepth(Depth) << "previously satisfied important dependency on "
1230                          << Start.TargetPkg().FullName() << std::endl;
1231          }
1232          else
1233          {
1234             if (DebugAutoInstall == true)
1235                std::clog << OutputInDepth(Depth) << "ignore old unsatisfied important dependency on "
1236                          << Start.TargetPkg().FullName() << std::endl;
1237             continue;
1238          }
1239       }
1240
1241       /* This bit is for processing the possibility of an install/upgrade
1242          fixing the problem for "positive" dependencies */
1243       if (Start.IsNegative() == false && (DepState[Start->ID] & DepCVer) == DepCVer)
1244       {
1245          pkgCacheFile CacheFile(this);
1246          APT::VersionList verlist = APT::VersionList::FromDependency(CacheFile, Start, APT::CacheSetHelper::CANDIDATE);
1247          CompareProviders comp(Start);
1248
1249          do {
1250             APT::VersionList::iterator InstVer = std::max_element(verlist.begin(), verlist.end(), comp);
1251
1252             if (InstVer == verlist.end())
1253                break;
1254
1255             pkgCache::PkgIterator InstPkg = InstVer.ParentPkg();
1256             if(DebugAutoInstall == true)
1257                std::clog << OutputInDepth(Depth) << "Installing " << InstPkg.Name()
1258                          << " as " << Start.DepType() << " of " << Pkg.Name()
1259                          << std::endl;
1260             if (MarkInstall(InstPkg, true, Depth + 1, false, ForceImportantDeps) == false)
1261             {
1262                verlist.erase(InstVer);
1263                continue;
1264             }
1265
1266             // now check if we should consider it a automatic dependency or not
1267             if(InstPkg->CurrentVer == 0 && MoveAutoBitToDependencies)
1268             {
1269                if(DebugAutoInstall == true)
1270                   std::clog << OutputInDepth(Depth) << "Setting " << InstPkg.FullName(false) << " NOT as auto-installed (direct "
1271                      << Start.DepType() << " of " << Pkg.FullName(false) << " which is manual and in APT::Move-Autobit-Sections)" << std::endl;
1272                MarkAuto(InstPkg, false);
1273             }
1274
1275
1276             break;
1277          } while(true);
1278          continue;
1279       }
1280       /* Negative dependencies have no or-group
1281          If the dependency isn't versioned, we try if an upgrade might solve the problem.
1282          Otherwise we remove the offender if needed */
1283       else if (Start.IsNegative() == true && Start->Type != pkgCache::Dep::Obsoletes)
1284       {
1285          std::unique_ptr<Version *[]> List(Start.AllTargets());
1286          pkgCache::PkgIterator TrgPkg = Start.TargetPkg();
1287          for (Version **I = List.get(); *I != 0; I++)
1288          {
1289             VerIterator Ver(*this,*I);
1290             PkgIterator Pkg = Ver.ParentPkg();
1291
1292             /* The List includes all packages providing this dependency,
1293                even providers which are not installed, so skip them. */
1294             if (PkgState[Pkg->ID].InstallVer == 0)
1295                continue;
1296
1297             /* Ignore negative dependencies that we are not going to
1298                get installed */
1299             if (PkgState[Pkg->ID].InstallVer != *I)
1300                continue;
1301
1302             if ((Start->Version != 0 || TrgPkg != Pkg) &&
1303                 PkgState[Pkg->ID].CandidateVer != PkgState[Pkg->ID].InstallVer &&
1304                 PkgState[Pkg->ID].CandidateVer != *I &&
1305                 MarkInstall(Pkg,true,Depth + 1, false, ForceImportantDeps) == true)
1306                continue;
1307             else if (Start->Type == pkgCache::Dep::Conflicts ||
1308                      Start->Type == pkgCache::Dep::DpkgBreaks)
1309             {
1310                if(DebugAutoInstall == true)
1311                   std::clog << OutputInDepth(Depth)
1312                             << " Removing: " << Pkg.Name()
1313                             << std::endl;
1314                if (MarkDelete(Pkg,false,Depth + 1, false) == false)
1315                   break;
1316             }
1317          }
1318          continue;
1319       }
1320    }
1321
1322    return Dep.end() == true;
1323 }
1324                                                                         /*}}}*/
1325 // DepCache::IsInstallOk - check if it is ok to install this package    /*{{{*/
1326 // ---------------------------------------------------------------------
1327 /* The default implementation checks if the installation of an M-A:same
1328    package would lead us into a version-screw and if so forbids it.
1329    dpkg holds are enforced by the private IsModeChangeOk */
1330 bool pkgDepCache::IsInstallOk(PkgIterator const &Pkg,bool AutoInst,
1331                               unsigned long Depth, bool FromUser)
1332 {
1333    return IsInstallOkMultiArchSameVersionSynced(Pkg,AutoInst, Depth, FromUser) &&
1334       IsInstallOkDependenciesSatisfiableByCandidates(Pkg,AutoInst, Depth, FromUser);
1335 }
1336 bool pkgDepCache::IsInstallOkMultiArchSameVersionSynced(PkgIterator const &Pkg,
1337       bool const /*AutoInst*/, unsigned long const Depth, bool const FromUser)
1338 {
1339    if (FromUser == true) // as always: user is always right
1340       return true;
1341
1342    // if we have checked before and it was okay, it will still be okay
1343    if (PkgState[Pkg->ID].Mode == ModeInstall &&
1344          PkgState[Pkg->ID].InstallVer == PkgState[Pkg->ID].CandidateVer)
1345       return true;
1346
1347    // ignore packages with none-M-A:same candidates
1348    VerIterator const CandVer = PkgState[Pkg->ID].CandidateVerIter(*this);
1349    if (unlikely(CandVer.end() == true) || CandVer == Pkg.CurrentVer() ||
1350          (CandVer->MultiArch & pkgCache::Version::Same) != pkgCache::Version::Same)
1351       return true;
1352
1353    GrpIterator const Grp = Pkg.Group();
1354    for (PkgIterator P = Grp.PackageList(); P.end() == false; P = Grp.NextPkg(P))
1355    {
1356       // not installed or self-check: fine by definition
1357       if (P->CurrentVer == 0 || P == Pkg)
1358          continue;
1359
1360       // not having a candidate or being in sync
1361       // (simple string-compare as stuff like '1' == '0:1-0' can't happen here)
1362       VerIterator CV = PkgState[P->ID].CandidateVerIter(*this);
1363       if (CV.end() == true || strcmp(Pkg.CandVersion(), CV.VerStr()) == 0)
1364          continue;
1365
1366       // packages losing M-A:same can be out-of-sync
1367       if ((CV->MultiArch & pkgCache::Version::Same) != pkgCache::Version::Same)
1368          continue;
1369
1370       // not downloadable means the package is obsolete, so allow out-of-sync
1371       if (CV.Downloadable() == false)
1372          continue;
1373
1374       PkgState[Pkg->ID].iFlags |= AutoKept;
1375       if (unlikely(DebugMarker == true))
1376          std::clog << OutputInDepth(Depth) << "Ignore MarkInstall of " << Pkg
1377             << " as it is not in sync with its M-A:same sibling " << P
1378             << " (" << Pkg.CandVersion() << " != " << CV.VerStr() << ")" << std::endl;
1379       return false;
1380    }
1381
1382    return true;
1383 }
1384 bool pkgDepCache::IsInstallOkDependenciesSatisfiableByCandidates(PkgIterator const &Pkg,
1385       bool const AutoInst, unsigned long const Depth, bool const /*FromUser*/)
1386 {
1387    if (AutoInst == false)
1388       return true;
1389
1390    VerIterator const CandVer = PkgState[Pkg->ID].CandidateVerIter(*this);
1391    if (unlikely(CandVer.end() == true) || CandVer == Pkg.CurrentVer())
1392       return true;
1393
1394    for (DepIterator Dep = CandVer.DependsList(); Dep.end() != true;)
1395    {
1396       // Grok or groups
1397       DepIterator Start = Dep;
1398       bool Result = true;
1399       unsigned Ors = 0;
1400       for (bool LastOR = true; Dep.end() == false && LastOR == true; ++Dep, ++Ors)
1401       {
1402          LastOR = (Dep->CompareOp & Dep::Or) == Dep::Or;
1403
1404          if ((DepState[Dep->ID] & DepInstall) == DepInstall)
1405             Result = false;
1406       }
1407
1408       if (Start.IsCritical() == false || Start.IsNegative() == true || Result == false)
1409          continue;
1410
1411       /* If we are in an or group locate the first or that can succeed.
1412          We have already cached this… */
1413       for (; Ors > 1 && (DepState[Start->ID] & DepCVer) != DepCVer; --Ors)
1414          ++Start;
1415
1416       if (Ors == 1 && (DepState[Start->ID] &DepCVer) != DepCVer)
1417       {
1418          if (DebugAutoInstall == true)
1419             std::clog << OutputInDepth(Depth) << Start << " can't be satisfied!" << std::endl;
1420
1421          // the dependency is critical, but can't be installed, so discard the candidate
1422          // as the problemresolver will trip over it otherwise trying to install it (#735967)
1423          if (Pkg->CurrentVer != 0 && (PkgState[Pkg->ID].iFlags & Protected) != Protected)
1424             SetCandidateVersion(Pkg.CurrentVer());
1425          return false;
1426       }
1427    }
1428
1429    return true;
1430 }
1431                                                                         /*}}}*/
1432 // DepCache::SetReInstall - Set the reinstallation flag                 /*{{{*/
1433 // ---------------------------------------------------------------------
1434 /* */
1435 void pkgDepCache::SetReInstall(PkgIterator const &Pkg,bool To)
1436 {
1437    if (unlikely(Pkg.end() == true))
1438       return;
1439
1440    APT::PackageList pkglist;
1441    if (Pkg->CurrentVer != 0 &&
1442        (Pkg.CurrentVer()-> MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same)
1443    {
1444       pkgCache::GrpIterator Grp = Pkg.Group();
1445       for (pkgCache::PkgIterator P = Grp.PackageList(); P.end() == false; P = Grp.NextPkg(P))
1446       {
1447          if (P->CurrentVer != 0)
1448             pkglist.insert(P);
1449       }
1450    }
1451    else
1452       pkglist.insert(Pkg);
1453
1454    ActionGroup group(*this);
1455
1456    for (APT::PackageList::const_iterator Pkg = pkglist.begin(); Pkg != pkglist.end(); ++Pkg)
1457    {
1458       RemoveSizes(Pkg);
1459       RemoveStates(Pkg);
1460
1461       StateCache &P = PkgState[Pkg->ID];
1462       if (To == true)
1463          P.iFlags |= ReInstall;
1464       else
1465          P.iFlags &= ~ReInstall;
1466
1467       AddStates(Pkg);
1468       AddSizes(Pkg);
1469    }
1470 }
1471                                                                         /*}}}*/
1472 pkgCache::VerIterator pkgDepCache::GetCandidateVersion(PkgIterator const &Pkg)/*{{{*/
1473 {
1474    return PkgState[Pkg->ID].CandidateVerIter(*this);
1475 }
1476                                                                         /*}}}*/
1477 // DepCache::SetCandidateVersion - Change the candidate version         /*{{{*/
1478 // ---------------------------------------------------------------------
1479 /* */
1480 void pkgDepCache::SetCandidateVersion(VerIterator TargetVer)
1481 {
1482    pkgCache::PkgIterator Pkg = TargetVer.ParentPkg();
1483    StateCache &P = PkgState[Pkg->ID];
1484
1485    if (P.CandidateVer == TargetVer)
1486       return;
1487
1488    ActionGroup group(*this);
1489
1490    RemoveSizes(Pkg);
1491    RemoveStates(Pkg);
1492
1493    if (P.CandidateVer == P.InstallVer && P.Install() == true)
1494       P.InstallVer = (Version *)TargetVer;
1495    P.CandidateVer = (Version *)TargetVer;
1496    P.Update(Pkg,*this);
1497
1498    AddStates(Pkg);
1499    Update(Pkg);
1500    AddSizes(Pkg);
1501
1502 }
1503                                                                         /*}}}*/
1504 // DepCache::SetCandidateRelease - Change the candidate version         /*{{{*/
1505 // ---------------------------------------------------------------------
1506 /* changes the candidate of a package and walks over all its dependencies
1507    to check if it needs to change the candidate of the dependency, too,
1508    to reach a installable versionstate */
1509 bool pkgDepCache::SetCandidateRelease(pkgCache::VerIterator TargetVer,
1510                                         std::string const &TargetRel)
1511 {
1512    std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> > Changed;
1513    return SetCandidateRelease(TargetVer, TargetRel, Changed);
1514 }
1515 bool pkgDepCache::SetCandidateRelease(pkgCache::VerIterator TargetVer,
1516                                         std::string const &TargetRel,
1517                                         std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> > &Changed)
1518 {
1519    ActionGroup group(*this);
1520    SetCandidateVersion(TargetVer);
1521
1522    if (TargetRel == "installed" || TargetRel == "candidate") // both doesn't make sense in this context
1523       return true;
1524
1525    pkgVersionMatch Match(TargetRel, pkgVersionMatch::Release);
1526    // save the position of the last element we will not undo - if we have to
1527    std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> >::iterator newChanged = --(Changed.end());
1528
1529    for (pkgCache::DepIterator D = TargetVer.DependsList(); D.end() == false; ++D)
1530    {
1531       if (D->Type != pkgCache::Dep::PreDepends && D->Type != pkgCache::Dep::Depends &&
1532           ((D->Type != pkgCache::Dep::Recommends && D->Type != pkgCache::Dep::Suggests) ||
1533            IsImportantDep(D) == false))
1534          continue;
1535
1536       // walk over an or-group and check if we need to do anything
1537       // for simpilicity no or-group is handled as a or-group including one dependency
1538       pkgCache::DepIterator Start = D;
1539       bool itsFine = false;
1540       for (bool stillOr = true; stillOr == true; ++Start)
1541       {
1542          stillOr = (Start->CompareOp & Dep::Or) == Dep::Or;
1543          pkgCache::PkgIterator const P = Start.TargetPkg();
1544          // virtual packages can't be a solution
1545          if (P.end() == true || (P->ProvidesList == 0 && P->VersionList == 0))
1546             continue;
1547          pkgCache::VerIterator const Cand = PkgState[P->ID].CandidateVerIter(*this);
1548          // no versioned dependency - but is it installable?
1549          if (Start.TargetVer() == 0 || Start.TargetVer()[0] == '\0')
1550          {
1551             // Check if one of the providers is installable
1552             if (P->ProvidesList != 0)
1553             {
1554                pkgCache::PrvIterator Prv = P.ProvidesList();
1555                for (; Prv.end() == false; ++Prv)
1556                {
1557                   pkgCache::VerIterator const C = PkgState[Prv.OwnerPkg()->ID].CandidateVerIter(*this);
1558                   if (C.end() == true || C != Prv.OwnerVer() ||
1559                       (VersionState(C.DependsList(), DepInstall, DepCandMin, DepCandPolicy) & DepCandMin) != DepCandMin)
1560                      continue;
1561                   break;
1562                }
1563                if (Prv.end() == true)
1564                   continue;
1565             }
1566             // no providers, so check if we have an installable candidate version
1567             else if (Cand.end() == true ||
1568                 (VersionState(Cand.DependsList(), DepInstall, DepCandMin, DepCandPolicy) & DepCandMin) != DepCandMin)
1569                continue;
1570             itsFine = true;
1571             break;
1572          }
1573          if (Cand.end() == true)
1574             continue;
1575          // check if the current candidate is enough for the versioned dependency - and installable?
1576          if (Start.IsSatisfied(Cand) == true &&
1577              (VersionState(Cand.DependsList(), DepInstall, DepCandMin, DepCandPolicy) & DepCandMin) == DepCandMin)
1578          {
1579             itsFine = true;
1580             break;
1581          }
1582       }
1583
1584       if (itsFine == true) {
1585          // something in the or-group was fine, skip all other members
1586          for (; (D->CompareOp & Dep::Or) == Dep::Or; ++D);
1587          continue;
1588       }
1589
1590       // walk again over the or-group and check each if a candidate switch would help
1591       itsFine = false;
1592       for (bool stillOr = true; stillOr == true; ++D)
1593       {
1594          stillOr = (D->CompareOp & Dep::Or) == Dep::Or;
1595          // changing candidate will not help if the dependency is not versioned
1596          if (D.TargetVer() == 0 || D.TargetVer()[0] == '\0')
1597          {
1598             if (stillOr == true)
1599                continue;
1600             break;
1601          }
1602
1603          pkgCache::VerIterator V;
1604          if (TargetRel == "newest")
1605             V = D.TargetPkg().VersionList();
1606          else
1607             V = Match.Find(D.TargetPkg());
1608
1609          // check if the version from this release could satisfy the dependency
1610          if (V.end() == true || D.IsSatisfied(V) == false)
1611          {
1612             if (stillOr == true)
1613                continue;
1614             break;
1615          }
1616
1617          pkgCache::VerIterator oldCand = PkgState[D.TargetPkg()->ID].CandidateVerIter(*this);
1618          if (V == oldCand)
1619          {
1620             // Do we already touched this Version? If so, their versioned dependencies are okay, no need to check again
1621             for (std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> >::const_iterator c = Changed.begin();
1622                  c != Changed.end(); ++c)
1623             {
1624                if (c->first->ParentPkg != V->ParentPkg)
1625                   continue;
1626                itsFine = true;
1627                break;
1628             }
1629          }
1630
1631          if (itsFine == false)
1632          {
1633             // change the candidate
1634             Changed.push_back(make_pair(V, TargetVer));
1635             if (SetCandidateRelease(V, TargetRel, Changed) == false)
1636             {
1637                if (stillOr == false)
1638                   break;
1639                // undo the candidate changing
1640                SetCandidateVersion(oldCand);
1641                Changed.pop_back();
1642                continue;
1643             }
1644             itsFine = true;
1645          }
1646
1647          // something in the or-group was fine, skip all other members
1648          for (; (D->CompareOp & Dep::Or) == Dep::Or; ++D);
1649          break;
1650       }
1651
1652       if (itsFine == false && (D->Type == pkgCache::Dep::PreDepends || D->Type == pkgCache::Dep::Depends))
1653       {
1654          // undo all changes which aren't lead to a solution
1655          for (std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> >::const_iterator c = ++newChanged;
1656               c != Changed.end(); ++c)
1657             SetCandidateVersion(c->first);
1658          Changed.erase(newChanged, Changed.end());
1659          return false;
1660       }
1661    }
1662    return true;
1663 }
1664                                                                         /*}}}*/
1665 // DepCache::MarkAuto - set the Auto flag for a package                 /*{{{*/
1666 // ---------------------------------------------------------------------
1667 /* */
1668 void pkgDepCache::MarkAuto(const PkgIterator &Pkg, bool Auto)
1669 {
1670   StateCache &state = PkgState[Pkg->ID];
1671
1672   ActionGroup group(*this);
1673
1674   if(Auto)
1675     state.Flags |= Flag::Auto;
1676   else
1677     state.Flags &= ~Flag::Auto;
1678 }
1679                                                                         /*}}}*/
1680 // StateCache::Update - Compute the various static display things       /*{{{*/
1681 // ---------------------------------------------------------------------
1682 /* This is called whenever the Candidate version changes. */
1683 void pkgDepCache::StateCache::Update(PkgIterator Pkg,pkgCache &Cache)
1684 {
1685    // Some info
1686    VerIterator Ver = CandidateVerIter(Cache);
1687
1688    // Use a null string or the version string
1689    if (Ver.end() == true)
1690       CandVersion = "";
1691    else
1692       CandVersion = Ver.VerStr();
1693
1694    // Find the current version
1695    CurVersion = "";
1696    if (Pkg->CurrentVer != 0)
1697       CurVersion = Pkg.CurrentVer().VerStr();
1698
1699    // Strip off the epochs for display
1700    CurVersion = StripEpoch(CurVersion);
1701    CandVersion = StripEpoch(CandVersion);
1702
1703    // Figure out if its up or down or equal
1704    Status = Ver.CompareVer(Pkg.CurrentVer());
1705    if (Pkg->CurrentVer == 0 || Pkg->VersionList == 0 || CandidateVer == 0)
1706      Status = 2;
1707 }
1708                                                                         /*}}}*/
1709 // StateCache::StripEpoch - Remove the epoch specifier from the version /*{{{*/
1710 // ---------------------------------------------------------------------
1711 /* */
1712 const char *pkgDepCache::StateCache::StripEpoch(const char *Ver)
1713 {
1714    if (Ver == 0)
1715       return 0;
1716
1717    // Strip any epoch
1718    char const * const I = strchr(Ver, ':');
1719    if (I == nullptr)
1720       return Ver;
1721    return I + 1;
1722 }
1723                                                                         /*}}}*/
1724 // Policy::GetCandidateVer - Returns the Candidate install version      /*{{{*/
1725 // ---------------------------------------------------------------------
1726 /* The default just returns the highest available version that is not
1727    a source and automatic. */
1728 pkgCache::VerIterator pkgDepCache::Policy::GetCandidateVer(PkgIterator const &Pkg)
1729 {
1730    /* Not source/not automatic versions cannot be a candidate version
1731       unless they are already installed */
1732    VerIterator Last;
1733
1734    for (VerIterator I = Pkg.VersionList(); I.end() == false; ++I)
1735    {
1736       if (Pkg.CurrentVer() == I)
1737          return I;
1738
1739       for (VerFileIterator J = I.FileList(); J.end() == false; ++J)
1740       {
1741          if (J.File().Flagged(Flag::NotSource))
1742             continue;
1743
1744          /* Stash the highest version of a not-automatic source, we use it
1745             if there is nothing better */
1746          if (J.File().Flagged(Flag::NotAutomatic) ||
1747              J.File().Flagged(Flag::ButAutomaticUpgrades))
1748          {
1749             if (Last.end() == true)
1750                Last = I;
1751             continue;
1752          }
1753
1754          return I;
1755       }
1756    }
1757
1758    return Last;
1759 }
1760                                                                         /*}}}*/
1761 // Policy::IsImportantDep - True if the dependency is important         /*{{{*/
1762 // ---------------------------------------------------------------------
1763 /* */
1764 bool pkgDepCache::Policy::IsImportantDep(DepIterator const &Dep) const
1765 {
1766    if(Dep.IsCritical())
1767       return true;
1768    else if(Dep->Type == pkgCache::Dep::Recommends)
1769    {
1770       if (InstallRecommends)
1771          return true;
1772       // we suport a special mode to only install-recommends for certain
1773       // sections
1774       // FIXME: this is a meant as a temporarly solution until the
1775       //        recommends are cleaned up
1776       const char *sec = Dep.ParentVer().Section();
1777       if (sec && ConfigValueInSubTree("APT::Install-Recommends-Sections", sec))
1778          return true;
1779    }
1780    else if(Dep->Type == pkgCache::Dep::Suggests)
1781       return InstallSuggests;
1782
1783    return false;
1784 }
1785                                                                         /*}}}*/
1786 // Policy::GetPriority - Get the priority of the package pin            /*{{{*/
1787 APT_CONST signed short pkgDepCache::Policy::GetPriority(pkgCache::PkgIterator const &/*Pkg*/)
1788 { return 0; }
1789 APT_CONST signed short pkgDepCache::Policy::GetPriority(pkgCache::VerIterator const &/*Ver*/, bool /*ConsiderFiles*/)
1790 { return 0; }
1791 APT_CONST signed short pkgDepCache::Policy::GetPriority(pkgCache::PkgFileIterator const &/*File*/)
1792 { return 0; }
1793                                                                         /*}}}*/
1794 pkgDepCache::InRootSetFunc *pkgDepCache::GetRootSetFunc()               /*{{{*/
1795 {
1796   DefaultRootSetFunc *f = new DefaultRootSetFunc;
1797   if(f->wasConstructedSuccessfully())
1798     return f;
1799   else
1800     {
1801       delete f;
1802       return NULL;
1803     }
1804 }
1805                                                                         /*}}}*/
1806 bool pkgDepCache::MarkFollowsRecommends()
1807 {
1808   return _config->FindB("APT::AutoRemove::RecommendsImportant", true);
1809 }
1810
1811 bool pkgDepCache::MarkFollowsSuggests()
1812 {
1813   return _config->FindB("APT::AutoRemove::SuggestsImportant", true);
1814 }
1815
1816 // pkgDepCache::MarkRequired - the main mark algorithm                  /*{{{*/
1817 bool pkgDepCache::MarkRequired(InRootSetFunc &userFunc)
1818 {
1819    if (_config->Find("APT::Solver", "internal") != "internal")
1820       return true;
1821
1822    bool const debug_autoremove = _config->FindB("Debug::pkgAutoRemove",false);
1823
1824    // init the states
1825    map_id_t const PackagesCount = Head().PackageCount;
1826    for(map_id_t i = 0; i < PackagesCount; ++i)
1827    {
1828       PkgState[i].Marked  = false;
1829       PkgState[i].Garbage = false;
1830    }
1831    if (debug_autoremove)
1832       for(PkgIterator p = PkgBegin(); !p.end(); ++p)
1833          if(PkgState[p->ID].Flags & Flag::Auto)
1834             std::clog << "AutoDep: " << p.FullName() << std::endl;
1835
1836    bool const follow_recommends = MarkFollowsRecommends();
1837    bool const follow_suggests   = MarkFollowsSuggests();
1838
1839    // do the mark part, this is the core bit of the algorithm
1840    for(PkgIterator p = PkgBegin(); !p.end(); ++p)
1841    {
1842       if(!(PkgState[p->ID].Flags & Flag::Auto) ||
1843           (p->Flags & Flag::Essential) ||
1844           (p->Flags & Flag::Important) ||
1845           userFunc.InRootSet(p) ||
1846           // be nice even then a required package violates the policy (#583517)
1847           // and do the full mark process also for required packages
1848           (p.CurrentVer().end() != true &&
1849            p.CurrentVer()->Priority == pkgCache::State::Required) ||
1850           // packages which can't be changed (like holds) can't be garbage
1851           (IsModeChangeOk(ModeGarbage, p, 0, false) == false))
1852       {
1853          // the package is installed (and set to keep)
1854          if(PkgState[p->ID].Keep() && !p.CurrentVer().end())
1855             MarkPackage(p, p.CurrentVer(),
1856                         follow_recommends, follow_suggests);
1857          // the package is to be installed
1858          else if(PkgState[p->ID].Install())
1859             MarkPackage(p, PkgState[p->ID].InstVerIter(*this),
1860                         follow_recommends, follow_suggests);
1861       }
1862    }
1863
1864    return true;
1865 }
1866                                                                         /*}}}*/
1867 // MarkPackage - mark a single package in Mark-and-Sweep                /*{{{*/
1868 void pkgDepCache::MarkPackage(const pkgCache::PkgIterator &pkg,
1869                               const pkgCache::VerIterator &ver,
1870                               bool const &follow_recommends,
1871                               bool const &follow_suggests)
1872 {
1873    pkgDepCache::StateCache &state = PkgState[pkg->ID];
1874
1875    // if we are marked already we are done
1876    if(state.Marked)
1877       return;
1878
1879    VerIterator const currver = pkg.CurrentVer();
1880    VerIterator const instver = state.InstVerIter(*this);
1881
1882 #if 0
1883    VerIterator const candver = state.CandidateVerIter(*this);
1884
1885    // If a package was garbage-collected but is now being marked, we
1886    // should re-select it
1887    // For cases when a pkg is set to upgrade and this trigger the
1888    // removal of a no-longer used dependency.  if the pkg is set to
1889    // keep again later it will result in broken deps
1890    if(state.Delete() && state.RemoveReason = Unused)
1891    {
1892       if(ver==candver)
1893          mark_install(pkg, false, false, NULL);
1894       else if(ver==pkg.CurrentVer())
1895          MarkKeep(pkg, false, false);
1896
1897       instver=state.InstVerIter(*this);
1898    }
1899 #endif
1900
1901    // For packages that are not going to be removed, ignore versions
1902    // other than the InstVer.  For packages that are going to be
1903    // removed, ignore versions other than the current version.
1904    if(!(ver == instver && !instver.end()) &&
1905       !(ver == currver && instver.end() && !ver.end()))
1906       return;
1907
1908    bool const debug_autoremove = _config->FindB("Debug::pkgAutoRemove", false);
1909
1910    if(debug_autoremove)
1911      {
1912        std::clog << "Marking: " << pkg.FullName();
1913        if(!ver.end())
1914          std::clog << " " << ver.VerStr();
1915        if(!currver.end())
1916          std::clog << ", Curr=" << currver.VerStr();
1917        if(!instver.end())
1918          std::clog << ", Inst=" << instver.VerStr();
1919        std::clog << std::endl;
1920      }
1921
1922    state.Marked=true;
1923
1924    if(ver.end() == true)
1925       return;
1926
1927      for(DepIterator d = ver.DependsList(); !d.end(); ++d)
1928      {
1929         if(d->Type == Dep::Depends ||
1930            d->Type == Dep::PreDepends ||
1931            (follow_recommends &&
1932             d->Type == Dep::Recommends) ||
1933            (follow_suggests &&
1934             d->Type == Dep::Suggests))
1935         {
1936            // Try all versions of this package.
1937            for(VerIterator V = d.TargetPkg().VersionList();
1938                !V.end(); ++V)
1939            {
1940               if(d.IsSatisfied(V))
1941               {
1942                 if(debug_autoremove)
1943                   {
1944                     std::clog << "Following dep: " << d.ParentPkg().FullName()
1945                               << " " << d.ParentVer().VerStr() << " "
1946                               << d.DepType() << " " << d.TargetPkg().FullName();
1947                     if((d->CompareOp & ~pkgCache::Dep::Or) != pkgCache::Dep::NoOp)
1948                       {
1949                         std::clog << " (" << d.CompType() << " "
1950                                   << d.TargetVer() << ")";
1951                       }
1952                     std::clog << std::endl;
1953                   }
1954                  MarkPackage(V.ParentPkg(), V,
1955                              follow_recommends, follow_suggests);
1956               }
1957            }
1958            // Now try virtual packages
1959            for(PrvIterator prv=d.TargetPkg().ProvidesList();
1960                !prv.end(); ++prv)
1961            {
1962               if(d.IsSatisfied(prv))
1963               {
1964                 if(debug_autoremove)
1965                   {
1966                     std::clog << "Following dep: " << d.ParentPkg().FullName() << " "
1967                               << d.ParentVer().VerStr() << " "
1968                               << d.DepType() << " " << d.TargetPkg().FullName() << " ";
1969                     if((d->CompareOp & ~pkgCache::Dep::Or) != pkgCache::Dep::NoOp)
1970                       {
1971                         std::clog << " (" << d.CompType() << " "
1972                                   << d.TargetVer() << ")";
1973                       }
1974                     std::clog << ", provided by "
1975                               << prv.OwnerPkg().FullName() << " "
1976                               << prv.OwnerVer().VerStr()
1977                               << std::endl;
1978                   }
1979
1980                  MarkPackage(prv.OwnerPkg(), prv.OwnerVer(),
1981                              follow_recommends, follow_suggests);
1982               }
1983            }
1984         }
1985      }
1986 }
1987                                                                         /*}}}*/
1988 bool pkgDepCache::Sweep()                                               /*{{{*/
1989 {
1990    bool debug_autoremove = _config->FindB("Debug::pkgAutoRemove",false);
1991
1992    // do the sweep
1993    for(PkgIterator p=PkgBegin(); !p.end(); ++p)
1994    {
1995      StateCache &state=PkgState[p->ID];
1996
1997      // skip required packages
1998      if (!p.CurrentVer().end() &&
1999          (p.CurrentVer()->Priority == pkgCache::State::Required))
2000         continue;
2001
2002      // if it is not marked and it is installed, it's garbage
2003      if(!state.Marked && (!p.CurrentVer().end() || state.Install()))
2004      {
2005         state.Garbage=true;
2006         if(debug_autoremove)
2007            std::clog << "Garbage: " << p.FullName() << std::endl;
2008      }
2009   }
2010
2011    return true;
2012 }
2013                                                                         /*}}}*/
2014 // DepCache::MarkAndSweep                                               /*{{{*/
2015 bool pkgDepCache::MarkAndSweep(InRootSetFunc &rootFunc)
2016 {
2017    return MarkRequired(rootFunc) && Sweep();
2018 }
2019 bool pkgDepCache::MarkAndSweep()
2020 {
2021    std::unique_ptr<InRootSetFunc> f(GetRootSetFunc());
2022    if(f.get() != NULL)
2023       return MarkAndSweep(*f.get());
2024    else
2025       return false;
2026 }
2027                                                                         /*}}}*/