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(CandVer.VerStr(), 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             << " (" << CandVer.VerStr() << " != " << 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          {
1425             SetCandidateVersion(Pkg.CurrentVer());
1426             StateCache &State = PkgState[Pkg->ID];
1427             if (State.Mode != ModeDelete)
1428             {
1429                State.Mode = ModeKeep;
1430                State.Update(Pkg, *this);
1431             }
1432          }
1433          return false;
1434       }
1435    }
1436
1437    return true;
1438 }
1439                                                                         /*}}}*/
1440 // DepCache::SetReInstall - Set the reinstallation flag                 /*{{{*/
1441 // ---------------------------------------------------------------------
1442 /* */
1443 void pkgDepCache::SetReInstall(PkgIterator const &Pkg,bool To)
1444 {
1445    if (unlikely(Pkg.end() == true))
1446       return;
1447
1448    APT::PackageList pkglist;
1449    if (Pkg->CurrentVer != 0 &&
1450        (Pkg.CurrentVer()-> MultiArch & pkgCache::Version::Same) == pkgCache::Version::Same)
1451    {
1452       pkgCache::GrpIterator Grp = Pkg.Group();
1453       for (pkgCache::PkgIterator P = Grp.PackageList(); P.end() == false; P = Grp.NextPkg(P))
1454       {
1455          if (P->CurrentVer != 0)
1456             pkglist.insert(P);
1457       }
1458    }
1459    else
1460       pkglist.insert(Pkg);
1461
1462    ActionGroup group(*this);
1463
1464    for (APT::PackageList::const_iterator Pkg = pkglist.begin(); Pkg != pkglist.end(); ++Pkg)
1465    {
1466       RemoveSizes(Pkg);
1467       RemoveStates(Pkg);
1468
1469       StateCache &P = PkgState[Pkg->ID];
1470       if (To == true)
1471          P.iFlags |= ReInstall;
1472       else
1473          P.iFlags &= ~ReInstall;
1474
1475       AddStates(Pkg);
1476       AddSizes(Pkg);
1477    }
1478 }
1479                                                                         /*}}}*/
1480 pkgCache::VerIterator pkgDepCache::GetCandidateVersion(PkgIterator const &Pkg)/*{{{*/
1481 {
1482    return PkgState[Pkg->ID].CandidateVerIter(*this);
1483 }
1484                                                                         /*}}}*/
1485 // DepCache::SetCandidateVersion - Change the candidate version         /*{{{*/
1486 // ---------------------------------------------------------------------
1487 /* */
1488 void pkgDepCache::SetCandidateVersion(VerIterator TargetVer)
1489 {
1490    pkgCache::PkgIterator Pkg = TargetVer.ParentPkg();
1491    StateCache &P = PkgState[Pkg->ID];
1492
1493    if (P.CandidateVer == TargetVer)
1494       return;
1495
1496    ActionGroup group(*this);
1497
1498    RemoveSizes(Pkg);
1499    RemoveStates(Pkg);
1500
1501    if (P.CandidateVer == P.InstallVer && P.Install() == true)
1502       P.InstallVer = (Version *)TargetVer;
1503    P.CandidateVer = (Version *)TargetVer;
1504    P.Update(Pkg,*this);
1505
1506    AddStates(Pkg);
1507    Update(Pkg);
1508    AddSizes(Pkg);
1509
1510 }
1511                                                                         /*}}}*/
1512 // DepCache::SetCandidateRelease - Change the candidate version         /*{{{*/
1513 // ---------------------------------------------------------------------
1514 /* changes the candidate of a package and walks over all its dependencies
1515    to check if it needs to change the candidate of the dependency, too,
1516    to reach a installable versionstate */
1517 bool pkgDepCache::SetCandidateRelease(pkgCache::VerIterator TargetVer,
1518                                         std::string const &TargetRel)
1519 {
1520    std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> > Changed;
1521    return SetCandidateRelease(TargetVer, TargetRel, Changed);
1522 }
1523 bool pkgDepCache::SetCandidateRelease(pkgCache::VerIterator TargetVer,
1524                                         std::string const &TargetRel,
1525                                         std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> > &Changed)
1526 {
1527    ActionGroup group(*this);
1528    SetCandidateVersion(TargetVer);
1529
1530    if (TargetRel == "installed" || TargetRel == "candidate") // both doesn't make sense in this context
1531       return true;
1532
1533    pkgVersionMatch Match(TargetRel, pkgVersionMatch::Release);
1534    // save the position of the last element we will not undo - if we have to
1535    std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> >::iterator newChanged = --(Changed.end());
1536
1537    for (pkgCache::DepIterator D = TargetVer.DependsList(); D.end() == false; ++D)
1538    {
1539       if (D->Type != pkgCache::Dep::PreDepends && D->Type != pkgCache::Dep::Depends &&
1540           ((D->Type != pkgCache::Dep::Recommends && D->Type != pkgCache::Dep::Suggests) ||
1541            IsImportantDep(D) == false))
1542          continue;
1543
1544       // walk over an or-group and check if we need to do anything
1545       // for simpilicity no or-group is handled as a or-group including one dependency
1546       pkgCache::DepIterator Start = D;
1547       bool itsFine = false;
1548       for (bool stillOr = true; stillOr == true; ++Start)
1549       {
1550          stillOr = (Start->CompareOp & Dep::Or) == Dep::Or;
1551          pkgCache::PkgIterator const P = Start.TargetPkg();
1552          // virtual packages can't be a solution
1553          if (P.end() == true || (P->ProvidesList == 0 && P->VersionList == 0))
1554             continue;
1555          pkgCache::VerIterator const Cand = PkgState[P->ID].CandidateVerIter(*this);
1556          // no versioned dependency - but is it installable?
1557          if (Start.TargetVer() == 0 || Start.TargetVer()[0] == '\0')
1558          {
1559             // Check if one of the providers is installable
1560             if (P->ProvidesList != 0)
1561             {
1562                pkgCache::PrvIterator Prv = P.ProvidesList();
1563                for (; Prv.end() == false; ++Prv)
1564                {
1565                   pkgCache::VerIterator const C = PkgState[Prv.OwnerPkg()->ID].CandidateVerIter(*this);
1566                   if (C.end() == true || C != Prv.OwnerVer() ||
1567                       (VersionState(C.DependsList(), DepInstall, DepCandMin, DepCandPolicy) & DepCandMin) != DepCandMin)
1568                      continue;
1569                   break;
1570                }
1571                if (Prv.end() == true)
1572                   continue;
1573             }
1574             // no providers, so check if we have an installable candidate version
1575             else if (Cand.end() == true ||
1576                 (VersionState(Cand.DependsList(), DepInstall, DepCandMin, DepCandPolicy) & DepCandMin) != DepCandMin)
1577                continue;
1578             itsFine = true;
1579             break;
1580          }
1581          if (Cand.end() == true)
1582             continue;
1583          // check if the current candidate is enough for the versioned dependency - and installable?
1584          if (Start.IsSatisfied(Cand) == true &&
1585              (VersionState(Cand.DependsList(), DepInstall, DepCandMin, DepCandPolicy) & DepCandMin) == DepCandMin)
1586          {
1587             itsFine = true;
1588             break;
1589          }
1590       }
1591
1592       if (itsFine == true) {
1593          // something in the or-group was fine, skip all other members
1594          for (; (D->CompareOp & Dep::Or) == Dep::Or; ++D);
1595          continue;
1596       }
1597
1598       // walk again over the or-group and check each if a candidate switch would help
1599       itsFine = false;
1600       for (bool stillOr = true; stillOr == true; ++D)
1601       {
1602          stillOr = (D->CompareOp & Dep::Or) == Dep::Or;
1603          // changing candidate will not help if the dependency is not versioned
1604          if (D.TargetVer() == 0 || D.TargetVer()[0] == '\0')
1605          {
1606             if (stillOr == true)
1607                continue;
1608             break;
1609          }
1610
1611          pkgCache::VerIterator V;
1612          if (TargetRel == "newest")
1613             V = D.TargetPkg().VersionList();
1614          else
1615             V = Match.Find(D.TargetPkg());
1616
1617          // check if the version from this release could satisfy the dependency
1618          if (V.end() == true || D.IsSatisfied(V) == false)
1619          {
1620             if (stillOr == true)
1621                continue;
1622             break;
1623          }
1624
1625          pkgCache::VerIterator oldCand = PkgState[D.TargetPkg()->ID].CandidateVerIter(*this);
1626          if (V == oldCand)
1627          {
1628             // Do we already touched this Version? If so, their versioned dependencies are okay, no need to check again
1629             for (std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> >::const_iterator c = Changed.begin();
1630                  c != Changed.end(); ++c)
1631             {
1632                if (c->first->ParentPkg != V->ParentPkg)
1633                   continue;
1634                itsFine = true;
1635                break;
1636             }
1637          }
1638
1639          if (itsFine == false)
1640          {
1641             // change the candidate
1642             Changed.push_back(make_pair(V, TargetVer));
1643             if (SetCandidateRelease(V, TargetRel, Changed) == false)
1644             {
1645                if (stillOr == false)
1646                   break;
1647                // undo the candidate changing
1648                SetCandidateVersion(oldCand);
1649                Changed.pop_back();
1650                continue;
1651             }
1652             itsFine = true;
1653          }
1654
1655          // something in the or-group was fine, skip all other members
1656          for (; (D->CompareOp & Dep::Or) == Dep::Or; ++D);
1657          break;
1658       }
1659
1660       if (itsFine == false && (D->Type == pkgCache::Dep::PreDepends || D->Type == pkgCache::Dep::Depends))
1661       {
1662          // undo all changes which aren't lead to a solution
1663          for (std::list<std::pair<pkgCache::VerIterator, pkgCache::VerIterator> >::const_iterator c = ++newChanged;
1664               c != Changed.end(); ++c)
1665             SetCandidateVersion(c->first);
1666          Changed.erase(newChanged, Changed.end());
1667          return false;
1668       }
1669    }
1670    return true;
1671 }
1672                                                                         /*}}}*/
1673 // DepCache::MarkAuto - set the Auto flag for a package                 /*{{{*/
1674 // ---------------------------------------------------------------------
1675 /* */
1676 void pkgDepCache::MarkAuto(const PkgIterator &Pkg, bool Auto)
1677 {
1678   StateCache &state = PkgState[Pkg->ID];
1679
1680   ActionGroup group(*this);
1681
1682   if(Auto)
1683     state.Flags |= Flag::Auto;
1684   else
1685     state.Flags &= ~Flag::Auto;
1686 }
1687                                                                         /*}}}*/
1688 // StateCache::Update - Compute the various static display things       /*{{{*/
1689 // ---------------------------------------------------------------------
1690 /* This is called whenever the Candidate version changes. */
1691 void pkgDepCache::StateCache::Update(PkgIterator Pkg,pkgCache &Cache)
1692 {
1693    // Some info
1694    VerIterator Ver = CandidateVerIter(Cache);
1695
1696    // Use a null string or the version string
1697    if (Ver.end() == true)
1698       CandVersion = "";
1699    else
1700       CandVersion = Ver.VerStr();
1701
1702    // Find the current version
1703    CurVersion = "";
1704    if (Pkg->CurrentVer != 0)
1705       CurVersion = Pkg.CurrentVer().VerStr();
1706
1707    // Figure out if its up or down or equal
1708    Status = Ver.CompareVer(Pkg.CurrentVer());
1709    if (Pkg->CurrentVer == 0 || Pkg->VersionList == 0 || CandidateVer == 0)
1710      Status = 2;
1711 }
1712                                                                         /*}}}*/
1713 // StateCache::StripEpoch - Remove the epoch specifier from the version /*{{{*/
1714 // ---------------------------------------------------------------------
1715 /* */
1716 const char *pkgDepCache::StateCache::StripEpoch(const char *Ver)
1717 {
1718    if (Ver == 0)
1719       return 0;
1720
1721    // Strip any epoch
1722    char const * const I = strchr(Ver, ':');
1723    if (I == nullptr)
1724       return Ver;
1725    return I + 1;
1726 }
1727                                                                         /*}}}*/
1728 // Policy::GetCandidateVer - Returns the Candidate install version      /*{{{*/
1729 // ---------------------------------------------------------------------
1730 /* The default just returns the highest available version that is not
1731    a source and automatic. */
1732 pkgCache::VerIterator pkgDepCache::Policy::GetCandidateVer(PkgIterator const &Pkg)
1733 {
1734    /* Not source/not automatic versions cannot be a candidate version
1735       unless they are already installed */
1736    VerIterator Last;
1737
1738    for (VerIterator I = Pkg.VersionList(); I.end() == false; ++I)
1739    {
1740       if (Pkg.CurrentVer() == I)
1741          return I;
1742
1743       for (VerFileIterator J = I.FileList(); J.end() == false; ++J)
1744       {
1745          if (J.File().Flagged(Flag::NotSource))
1746             continue;
1747
1748          /* Stash the highest version of a not-automatic source, we use it
1749             if there is nothing better */
1750          if (J.File().Flagged(Flag::NotAutomatic) ||
1751              J.File().Flagged(Flag::ButAutomaticUpgrades))
1752          {
1753             if (Last.end() == true)
1754                Last = I;
1755             continue;
1756          }
1757
1758          return I;
1759       }
1760    }
1761
1762    return Last;
1763 }
1764                                                                         /*}}}*/
1765 // Policy::IsImportantDep - True if the dependency is important         /*{{{*/
1766 // ---------------------------------------------------------------------
1767 /* */
1768 bool pkgDepCache::Policy::IsImportantDep(DepIterator const &Dep) const
1769 {
1770    if(Dep.IsCritical())
1771       return true;
1772    else if(Dep->Type == pkgCache::Dep::Recommends)
1773    {
1774       if (InstallRecommends)
1775          return true;
1776       // we suport a special mode to only install-recommends for certain
1777       // sections
1778       // FIXME: this is a meant as a temporarly solution until the
1779       //        recommends are cleaned up
1780       const char *sec = Dep.ParentVer().Section();
1781       if (sec && ConfigValueInSubTree("APT::Install-Recommends-Sections", sec))
1782          return true;
1783    }
1784    else if(Dep->Type == pkgCache::Dep::Suggests)
1785       return InstallSuggests;
1786
1787    return false;
1788 }
1789                                                                         /*}}}*/
1790 // Policy::GetPriority - Get the priority of the package pin            /*{{{*/
1791 APT_CONST signed short pkgDepCache::Policy::GetPriority(pkgCache::PkgIterator const &/*Pkg*/)
1792 { return 0; }
1793 APT_CONST signed short pkgDepCache::Policy::GetPriority(pkgCache::VerIterator const &/*Ver*/, bool /*ConsiderFiles*/)
1794 { return 0; }
1795 APT_CONST signed short pkgDepCache::Policy::GetPriority(pkgCache::PkgFileIterator const &/*File*/)
1796 { return 0; }
1797                                                                         /*}}}*/
1798 pkgDepCache::InRootSetFunc *pkgDepCache::GetRootSetFunc()               /*{{{*/
1799 {
1800   DefaultRootSetFunc *f = new DefaultRootSetFunc;
1801   if(f->wasConstructedSuccessfully())
1802     return f;
1803   else
1804     {
1805       delete f;
1806       return NULL;
1807     }
1808 }
1809                                                                         /*}}}*/
1810 bool pkgDepCache::MarkFollowsRecommends()
1811 {
1812   return _config->FindB("APT::AutoRemove::RecommendsImportant", true);
1813 }
1814
1815 bool pkgDepCache::MarkFollowsSuggests()
1816 {
1817   return _config->FindB("APT::AutoRemove::SuggestsImportant", true);
1818 }
1819
1820 // pkgDepCache::MarkRequired - the main mark algorithm                  /*{{{*/
1821 bool pkgDepCache::MarkRequired(InRootSetFunc &userFunc)
1822 {
1823    if (_config->Find("APT::Solver", "internal") != "internal")
1824       return true;
1825
1826    bool const debug_autoremove = _config->FindB("Debug::pkgAutoRemove",false);
1827
1828    // init the states
1829    map_id_t const PackagesCount = Head().PackageCount;
1830    for(map_id_t i = 0; i < PackagesCount; ++i)
1831    {
1832       PkgState[i].Marked  = false;
1833       PkgState[i].Garbage = false;
1834    }
1835    if (debug_autoremove)
1836       for(PkgIterator p = PkgBegin(); !p.end(); ++p)
1837          if(PkgState[p->ID].Flags & Flag::Auto)
1838             std::clog << "AutoDep: " << p.FullName() << std::endl;
1839
1840    bool const follow_recommends = MarkFollowsRecommends();
1841    bool const follow_suggests   = MarkFollowsSuggests();
1842
1843    // do the mark part, this is the core bit of the algorithm
1844    for(PkgIterator p = PkgBegin(); !p.end(); ++p)
1845    {
1846       if(!(PkgState[p->ID].Flags & Flag::Auto) ||
1847           (p->Flags & Flag::Essential) ||
1848           (p->Flags & Flag::Important) ||
1849           userFunc.InRootSet(p) ||
1850           // be nice even then a required package violates the policy (#583517)
1851           // and do the full mark process also for required packages
1852           (p.CurrentVer().end() != true &&
1853            p.CurrentVer()->Priority == pkgCache::State::Required) ||
1854           // packages which can't be changed (like holds) can't be garbage
1855           (IsModeChangeOk(ModeGarbage, p, 0, false) == false))
1856       {
1857          // the package is installed (and set to keep)
1858          if(PkgState[p->ID].Keep() && !p.CurrentVer().end())
1859             MarkPackage(p, p.CurrentVer(),
1860                         follow_recommends, follow_suggests);
1861          // the package is to be installed
1862          else if(PkgState[p->ID].Install())
1863             MarkPackage(p, PkgState[p->ID].InstVerIter(*this),
1864                         follow_recommends, follow_suggests);
1865       }
1866    }
1867
1868    return true;
1869 }
1870                                                                         /*}}}*/
1871 // MarkPackage - mark a single package in Mark-and-Sweep                /*{{{*/
1872 void pkgDepCache::MarkPackage(const pkgCache::PkgIterator &pkg,
1873                               const pkgCache::VerIterator &ver,
1874                               bool const &follow_recommends,
1875                               bool const &follow_suggests)
1876 {
1877    pkgDepCache::StateCache &state = PkgState[pkg->ID];
1878
1879    // if we are marked already we are done
1880    if(state.Marked)
1881       return;
1882
1883    VerIterator const currver = pkg.CurrentVer();
1884    VerIterator const instver = state.InstVerIter(*this);
1885
1886 #if 0
1887    VerIterator const candver = state.CandidateVerIter(*this);
1888
1889    // If a package was garbage-collected but is now being marked, we
1890    // should re-select it
1891    // For cases when a pkg is set to upgrade and this trigger the
1892    // removal of a no-longer used dependency.  if the pkg is set to
1893    // keep again later it will result in broken deps
1894    if(state.Delete() && state.RemoveReason = Unused)
1895    {
1896       if(ver==candver)
1897          mark_install(pkg, false, false, NULL);
1898       else if(ver==pkg.CurrentVer())
1899          MarkKeep(pkg, false, false);
1900
1901       instver=state.InstVerIter(*this);
1902    }
1903 #endif
1904
1905    // For packages that are not going to be removed, ignore versions
1906    // other than the InstVer.  For packages that are going to be
1907    // removed, ignore versions other than the current version.
1908    if(!(ver == instver && !instver.end()) &&
1909       !(ver == currver && instver.end() && !ver.end()))
1910       return;
1911
1912    bool const debug_autoremove = _config->FindB("Debug::pkgAutoRemove", false);
1913
1914    if(debug_autoremove)
1915      {
1916        std::clog << "Marking: " << pkg.FullName();
1917        if(!ver.end())
1918          std::clog << " " << ver.VerStr();
1919        if(!currver.end())
1920          std::clog << ", Curr=" << currver.VerStr();
1921        if(!instver.end())
1922          std::clog << ", Inst=" << instver.VerStr();
1923        std::clog << std::endl;
1924      }
1925
1926    state.Marked=true;
1927
1928    if(ver.end() == true)
1929       return;
1930
1931      for(DepIterator d = ver.DependsList(); !d.end(); ++d)
1932      {
1933         if(d->Type == Dep::Depends ||
1934            d->Type == Dep::PreDepends ||
1935            (follow_recommends &&
1936             d->Type == Dep::Recommends) ||
1937            (follow_suggests &&
1938             d->Type == Dep::Suggests))
1939         {
1940            // Try all versions of this package.
1941            for(VerIterator V = d.TargetPkg().VersionList();
1942                !V.end(); ++V)
1943            {
1944               if(d.IsSatisfied(V))
1945               {
1946                 if(debug_autoremove)
1947                   {
1948                     std::clog << "Following dep: " << d.ParentPkg().FullName()
1949                               << " " << d.ParentVer().VerStr() << " "
1950                               << d.DepType() << " " << d.TargetPkg().FullName();
1951                     if((d->CompareOp & ~pkgCache::Dep::Or) != pkgCache::Dep::NoOp)
1952                       {
1953                         std::clog << " (" << d.CompType() << " "
1954                                   << d.TargetVer() << ")";
1955                       }
1956                     std::clog << std::endl;
1957                   }
1958                  MarkPackage(V.ParentPkg(), V,
1959                              follow_recommends, follow_suggests);
1960               }
1961            }
1962            // Now try virtual packages
1963            for(PrvIterator prv=d.TargetPkg().ProvidesList();
1964                !prv.end(); ++prv)
1965            {
1966               if(d.IsSatisfied(prv))
1967               {
1968                 if(debug_autoremove)
1969                   {
1970                     std::clog << "Following dep: " << d.ParentPkg().FullName() << " "
1971                               << d.ParentVer().VerStr() << " "
1972                               << d.DepType() << " " << d.TargetPkg().FullName() << " ";
1973                     if((d->CompareOp & ~pkgCache::Dep::Or) != pkgCache::Dep::NoOp)
1974                       {
1975                         std::clog << " (" << d.CompType() << " "
1976                                   << d.TargetVer() << ")";
1977                       }
1978                     std::clog << ", provided by "
1979                               << prv.OwnerPkg().FullName() << " "
1980                               << prv.OwnerVer().VerStr()
1981                               << std::endl;
1982                   }
1983
1984                  MarkPackage(prv.OwnerPkg(), prv.OwnerVer(),
1985                              follow_recommends, follow_suggests);
1986               }
1987            }
1988         }
1989      }
1990 }
1991                                                                         /*}}}*/
1992 bool pkgDepCache::Sweep()                                               /*{{{*/
1993 {
1994    bool debug_autoremove = _config->FindB("Debug::pkgAutoRemove",false);
1995
1996    // do the sweep
1997    for(PkgIterator p=PkgBegin(); !p.end(); ++p)
1998    {
1999      StateCache &state=PkgState[p->ID];
2000
2001      // skip required packages
2002      if (!p.CurrentVer().end() &&
2003          (p.CurrentVer()->Priority == pkgCache::State::Required))
2004         continue;
2005
2006      // if it is not marked and it is installed, it's garbage
2007      if(!state.Marked && (!p.CurrentVer().end() || state.Install()))
2008      {
2009         state.Garbage=true;
2010         if(debug_autoremove)
2011            std::clog << "Garbage: " << p.FullName() << std::endl;
2012      }
2013   }
2014
2015    return true;
2016 }
2017                                                                         /*}}}*/
2018 // DepCache::MarkAndSweep                                               /*{{{*/
2019 bool pkgDepCache::MarkAndSweep(InRootSetFunc &rootFunc)
2020 {
2021    return MarkRequired(rootFunc) && Sweep();
2022 }
2023 bool pkgDepCache::MarkAndSweep()
2024 {
2025    std::unique_ptr<InRootSetFunc> f(GetRootSetFunc());
2026    if(f.get() != NULL)
2027       return MarkAndSweep(*f.get());
2028    else
2029       return false;
2030 }
2031                                                                         /*}}}*/