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