#
cargo/core/resolver/
dep_cache.rs

    1//! There are 2 sources of facts for the resolver:
    2//!
    3//! - The `Registry` tells us for a `Dependency` what versions are available to fulfil it.
    4//! - The `Summary` tells us for a version (and features) what dependencies need to be fulfilled for it to be activated.
    5//!
    6//! These constitute immutable facts, the soled ground truth that all other inference depends on.
    7//! Theoretically this could all be enumerated ahead of time, but we want to be lazy and only
    8//! look up things we need to. The compromise is to cache the results as they are computed.
    9//!
    10//! This module impl that cache in all the gory details
    11
    12use crate::core::resolver::context::ResolverContext;
    13use crate::core::resolver::errors::describe_path_in_context;
    14use crate::core::resolver::types::{ConflictReason, DepInfo, FeaturesSet};
    15use crate::core::resolver::{
    16    ActivateError, ActivateResult, CliFeatures, RequestedFeatures, ResolveOpts, VersionOrdering,
    17    VersionPreferences,
    18};
    19use crate::core::{
    20    Dependency, FeatureValue, PackageId, PackageIdSpec, PackageIdSpecQuery, Registry, Summary,
    21};
    22use crate::sources::source::QueryKind;
    23use crate::util::closest_msg;
    24use crate::util::errors::CargoResult;
    25use crate::util::interning::{INTERNED_DEFAULT, InternedString};
    26
    27use anyhow::Context as _;
    28use std::collections::{BTreeSet, HashMap, HashSet};
    29use std::fmt::Write;
    30use std::rc::Rc;
    31use std::task::Poll;
    32use tracing::debug;
    33
    34pub struct RegistryQueryer<'a> {
    35    pub registry: &'a mut (dyn Registry + 'a),
    36    replacements: &'a [(PackageIdSpec, Dependency)],
    37    version_prefs: &'a VersionPreferences,
    38    /// a cache of `Candidate`s that fulfil a `Dependency` (and whether `first_version`)
    39    registry_cache: HashMap<(Dependency, Option<VersionOrdering>), Poll<Rc<Vec<Summary>>>>,
    40    /// a cache of `Dependency`s that are required for a `Summary`
    41    ///
    42    /// HACK: `first_version` is not kept in the cache key is it is 1:1 with
    43    /// `parent.is_none()` (the first element of the cache key) as it doesn't change through
    44    /// execution.
    45    summary_cache: HashMap<
    46        (Option<PackageId>, Summary, ResolveOpts),
    47        (Rc<(HashSet<InternedString>, Rc<Vec<DepInfo>>)>, bool),
    48    >,
    49    /// all the cases we ended up using a supplied replacement
    50    used_replacements: HashMap<PackageId, Summary>,
    51}
    52
    53impl<'a> RegistryQueryer<'a> {
    54    pub fn new(
    55        registry: &'a mut dyn Registry,
    56        replacements: &'a [(PackageIdSpec, Dependency)],
    57        version_prefs: &'a VersionPreferences,
    58    ) -> Self {
    59        RegistryQueryer {
    60            registry,
    61            replacements,
    62            version_prefs,
    63            registry_cache: HashMap::new(),
    64            summary_cache: HashMap::new(),
    65            used_replacements: HashMap::new(),
    66        }
    67    }
    68
    69    pub fn reset_pending(&mut self) -> bool {
    70        let mut all_ready = true;
    71        self.registry_cache.retain(|_, r| {
    72            if !r.is_ready() {
    73                all_ready = false;
    74            }
    75            r.is_ready()
    76        });
    77        self.summary_cache.retain(|_, (_, r)| {
    78            if !*r {
    79                all_ready = false;
    80            }
    81            *r
    82        });
    83        all_ready
    84    }
    85
    86    pub fn used_replacement_for(&self, p: PackageId) -> Option<(PackageId, PackageId)> {
    87        self.used_replacements.get(&p).map(|r| (p, r.package_id()))
    88    }
    89
    90    pub fn replacement_summary(&self, p: PackageId) -> Option<&Summary> {
    91        self.used_replacements.get(&p)
    92    }
    93
    94    /// Queries the `registry` to return a list of candidates for `dep`.
    95    ///
    96    /// This method is the location where overrides are taken into account. If
    97    /// any candidates are returned which match an override then the override is
    98    /// applied by performing a second query for what the override should
    99    /// return.
    100    pub fn query(
    101        &mut self,
    102        dep: &Dependency,
    103        first_version: Option<VersionOrdering>,
    104    ) -> Poll<CargoResult<Rc<Vec<Summary>>>> {
    105        let registry_cache_key = (dep.clone(), first_version);
    106        if let Some(out) = self.registry_cache.get(&registry_cache_key).cloned() {
    107            return out.map(Result::Ok);
    108        }
    109
    110        let mut ret = Vec::new();
    111        let ready = self.registry.query(dep, QueryKind::Exact, &mut |s| {
    112            ret.push(s.into_summary());
    113        })?;
    114        if ready.is_pending() {
    115            self.registry_cache
    116                .insert((dep.clone(), first_version), Poll::Pending);
    117            return Poll::Pending;
    118        }
    119        for summary in ret.iter() {
    120            let mut potential_matches = self
    121                .replacements
    122                .iter()
    123                .filter(|(spec, _)| spec.matches(summary.package_id()));
    124
    125            let Some((spec, dep)) = potential_matches.next() else {
    126                continue;
    127            };
    128            debug!(
    129                "found an override for {} {}",
    130                dep.package_name(),
    131                dep.version_req()
    132            );
    133
    134            let mut summaries = match self.registry.query_vec(dep, QueryKind::Exact)? {
    135                Poll::Ready(s) => s.into_iter(),
    136                Poll::Pending => {
    137                    self.registry_cache
    138                        .insert((dep.clone(), first_version), Poll::Pending);
    139                    return Poll::Pending;
    140                }
    141            };
    142            let s = summaries
    143                .next()
    144                .ok_or_else(|| {
    145                    anyhow::format_err!(
    146                        "no matching package for override `{}` found\n\
    147                     location searched: {}\n\
    148                     version required: {}",
    149                        spec,
    150                        dep.source_id(),
    151                        dep.version_req()
    152                    )
    153                })?
    154                .into_summary();
    155            let summaries = summaries.collect::<Vec<_>>();
    156            if !summaries.is_empty() {
    157                let bullets = summaries
    158                    .iter()
    159                    .map(|s| format!("  * {}", s.package_id()))
    160                    .collect::<Vec<_>>();
    161                return Poll::Ready(Err(anyhow::anyhow!(
    162                    "the replacement specification `{}` matched \
    163                     multiple packages:\n  * {}\n{}",
    164                    spec,
    165                    s.package_id(),
    166                    bullets.join("\n")
    167                )));
    168            }
    169
    170            assert_eq!(
    171                s.name(),
    172                summary.name(),
    173                "dependency should be hard coded to have the same name"
    174            );
    175            if s.version() != summary.version() {
    176                return Poll::Ready(Err(anyhow::anyhow!(
    177                    "replacement specification `{}` matched {} and tried to override it with {}\n\
    178                     avoid matching unrelated packages by being more specific",
    179                    spec,
    180                    summary.version(),
    181                    s.version(),
    182                )));
    183            }
    184
    185            let replace = if s.source_id() == summary.source_id() {
    186                debug!("Preventing\n{:?}\nfrom replacing\n{:?}", summary, s);
    187                None
    188            } else {
    189                Some(s)
    190            };
    191            let matched_spec = spec.clone();
    192
    193            // Make sure no duplicates
    194            if let Some((spec, _)) = potential_matches.next() {
    195                return Poll::Ready(Err(anyhow::anyhow!(
    196                    "overlapping replacement specifications found:\n\n  \
    197                     * {}\n  * {}\n\nboth specifications match: {}",
    198                    matched_spec,
    199                    spec,
    200                    summary.package_id()
    201                )));
    202            }
    203
    204            for dep in summary.dependencies() {
    205                debug!("\t{} => {}", dep.package_name(), dep.version_req());
    206            }
    207            if let Some(r) = replace {
    208                self.used_replacements.insert(summary.package_id(), r);
    209            }
    210        }
    211
    212        self.version_prefs.sort_summaries(&mut ret, first_version);
    213
    214        let out = Poll::Ready(Rc::new(ret));
    215
    216        self.registry_cache.insert(registry_cache_key, out.clone());
    217
    218        out.map(Result::Ok)
    219    }
    220
    221    /// Find out what dependencies will be added by activating `candidate`,
    222    /// with features described in `opts`. Then look up in the `registry`
    223    /// the candidates that will fulfil each of these dependencies, as it is the
    224    /// next obvious question.
    225    pub fn build_deps(
    226        &mut self,
    227        cx: &ResolverContext,
    228        parent: Option<PackageId>,
    229        candidate: &Summary,
    230        opts: &ResolveOpts,
    231        first_version: Option<VersionOrdering>,
    232    ) -> ActivateResult<Rc<(HashSet<InternedString>, Rc<Vec<DepInfo>>)>> {
    233        // if we have calculated a result before, then we can just return it,
    234        // as it is a "pure" query of its arguments.
    235        if let Some(out) = self
    236            .summary_cache
    237            .get(&(parent, candidate.clone(), opts.clone()))
    238        {
    239            return Ok(out.0.clone());
    240        }
    241        // First, figure out our set of dependencies based on the requested set
    242        // of features. This also calculates what features we're going to enable
    243        // for our own dependencies.
    244        let (used_features, deps) = resolve_features(parent, candidate, opts)?;
    245
    246        // Next, transform all dependencies into a list of possible candidates
    247        // which can satisfy that dependency.
    248        let mut all_ready = true;
    249        let mut deps = deps
    250            .into_iter()
    251            .filter_map(|(dep, features)| match self.query(&dep, first_version) {
    252                Poll::Ready(Ok(candidates)) => Some(Ok((dep, candidates, features))),
    253                Poll::Pending => {
    254                    all_ready = false;
    255                    // we can ignore Pending deps, resolve will be repeatedly called
    256                    // until there are none to ignore
    257                    None
    258                }
    259                Poll::Ready(Err(e)) => Some(Err(e).with_context(|| {
    260                    format!(
    261                        "failed to get `{}` as a dependency of {}",
    262                        dep.package_name(),
    263                        describe_path_in_context(cx, &candidate.package_id()),
    264                    )
    265                })),
    266            })
    267            .collect::<CargoResult<Vec<DepInfo>>>()?;
    268
    269        // Attempt to resolve dependencies with fewer candidates before trying
    270        // dependencies with more candidates. This way if the dependency with
    271        // only one candidate can't be resolved we don't have to do a bunch of
    272        // work before we figure that out.
    273        deps.sort_by_key(|(_, a, _)| a.len());
    274
    275        let out = Rc::new((used_features, Rc::new(deps)));
    276
    277        // If we succeed we add the result to the cache so we can use it again next time.
    278        // We don't cache the failure cases as they don't impl Clone.
    279        self.summary_cache.insert(
    280            (parent, candidate.clone(), opts.clone()),
    281            (out.clone(), all_ready),
    282        );
    283
    284        Ok(out)
    285    }
    286}
    287
    288/// Returns the features we ended up using and
    289/// all dependencies and the features we want from each of them.
    290pub fn resolve_features<'b>(
    291    parent: Option<PackageId>,
    292    s: &'b Summary,
    293    opts: &'b ResolveOpts,
    294) -> ActivateResult<(HashSet<InternedString>, Vec<(Dependency, FeaturesSet)>)> {
    295    // First, filter by dev-dependencies.
    296    let deps = s.dependencies();
    297    let deps = deps.iter().filter(|d| d.is_transitive() || opts.dev_deps);
    298
    299    let reqs = build_requirements(parent, s, opts)?;
    300    let mut ret = Vec::new();
    301    let default_dep = BTreeSet::new();
    302    let mut valid_dep_names = HashSet::new();
    303
    304    // Next, collect all actually enabled dependencies and their features.
    305    for dep in deps {
    306        // Skip optional dependencies, but not those enabled through a
    307        // feature
    308        if dep.is_optional() && !reqs.deps.contains_key(&dep.name_in_toml()) {
    309            continue;
    310        }
    311        valid_dep_names.insert(dep.name_in_toml());
    312        // So we want this dependency. Move the features we want from
    313        // `feature_deps` to `ret` and register ourselves as using this
    314        // name.
    315        let mut base = reqs
    316            .deps
    317            .get(&dep.name_in_toml())
    318            .unwrap_or(&default_dep)
    319            .clone();
    320        base.extend(dep.features().iter());
    321        ret.push((dep.clone(), Rc::new(base)));
    322    }
    323
    324    // This is a special case for command-line `--features
    325    // dep_name/feat_name` where `dep_name` does not exist. All other
    326    // validation is done either in `build_requirements` or
    327    // `build_feature_map`.
    328    if parent.is_none() {
    329        for dep_name in reqs.deps.keys() {
    330            if !valid_dep_names.contains(dep_name) {
    331                let e = RequirementError::MissingDependency(*dep_name);
    332                return Err(e.into_activate_error(parent, s));
    333            }
    334        }
    335    }
    336
    337    Ok((reqs.into_features(), ret))
    338}
    339
    340/// Takes requested features for a single package from the input `ResolveOpts` and
    341/// recurses to find all requested features, dependencies and requested
    342/// dependency features in a `Requirements` object, returning it to the resolver.
    343fn build_requirements<'a, 'b: 'a>(
    344    parent: Option<PackageId>,
    345    s: &'a Summary,
    346    opts: &'b ResolveOpts,
    347) -> ActivateResult<Requirements<'a>> {
    348    let mut reqs = Requirements::new(s);
    349
    350    let handle_default = |uses_default_features, reqs: &mut Requirements<'_>| {
    351        if uses_default_features && s.features().contains_key("default") {
    352            if let Err(e) = reqs.require_feature(INTERNED_DEFAULT) {
    353                return Err(e.into_activate_error(parent, s));
    354            }
    355        }
    356        Ok(())
    357    };
    358
    359    match &opts.features {
    360        RequestedFeatures::CliFeatures(CliFeatures {
    361            features,
    362            all_features,
    363            uses_default_features,
    364        }) => {
    365            if *all_features {
    366                for key in s.features().keys() {
    367                    if let Err(e) = reqs.require_feature(*key) {
    368                        return Err(e.into_activate_error(parent, s));
    369                    }
    370                }
    371            }
    372
    373            for fv in features.iter() {
    374                if let Err(e) = reqs.require_value(fv) {
    375                    return Err(e.into_activate_error(parent, s));
    376                }
    377            }
    378            handle_default(*uses_default_features, &mut reqs)?;
    379        }
    380        RequestedFeatures::DepFeatures {
    381            features,
    382            uses_default_features,
    383        } => {
    384            for feature in features.iter() {
    385                if let Err(e) = reqs.require_feature(*feature) {
    386                    return Err(e.into_activate_error(parent, s));
    387                }
    388            }
    389            handle_default(*uses_default_features, &mut reqs)?;
    390        }
    391    }
    392
    393    Ok(reqs)
    394}
    395
    396/// Set of feature and dependency requirements for a package.
    397#[derive(Debug)]
    398struct Requirements<'a> {
    399    summary: &'a Summary,
    400    /// The deps map is a mapping of dependency name to list of features enabled.
    401    ///
    402    /// The resolver will activate all of these dependencies, with the given
    403    /// features enabled.
    404    deps: HashMap<InternedString, BTreeSet<InternedString>>,
    405    /// The set of features enabled on this package which is later used when
    406    /// compiling to instruct the code what features were enabled.
    407    features: HashSet<InternedString>,
    408}
    409
    410/// An error for a requirement.
    411///
    412/// This will later be converted to an `ActivateError` depending on whether or
    413/// not this is a dependency or a root package.
    414enum RequirementError {
    415    /// The package does not have the requested feature.
    416    MissingFeature(InternedString),
    417    /// The package does not have the requested dependency.
    418    MissingDependency(InternedString),
    419    /// A feature has a direct cycle to itself.
    420    ///
    421    /// Note that cycles through multiple features are allowed (but perhaps
    422    /// they shouldn't be?).
    423    Cycle(InternedString),
    424}
    425
    426impl Requirements<'_> {
    427    fn new(summary: &Summary) -> Requirements<'_> {
    428        Requirements {
    429            summary,
    430            deps: HashMap::new(),
    431            features: HashSet::new(),
    432        }
    433    }
    434
    435    fn into_features(self) -> HashSet<InternedString> {
    436        self.features
    437    }
    438
    439    fn require_dep_feature(
    440        &mut self,
    441        package: InternedString,
    442        feat: InternedString,
    443        weak: bool,
    444    ) -> Result<(), RequirementError> {
    445        // If `package` is indeed an optional dependency then we activate the
    446        // feature named `package`, but otherwise if `package` is a required
    447        // dependency then there's no feature associated with it.
    448        if !weak
    449            && self
    450                .summary
    451                .dependencies()
    452                .iter()
    453                .any(|dep| dep.name_in_toml() == package && dep.is_optional())
    454        {
    455            // This optional dependency may not have an implicit feature of
    456            // the same name if the `dep:` syntax is used to avoid creating
    457            // that implicit feature.
    458            if self.summary.features().contains_key(&package) {
    459                self.require_feature(package)?;
    460            }
    461        }
    462        self.deps.entry(package).or_default().insert(feat);
    463        Ok(())
    464    }
    465
    466    fn require_dependency(&mut self, pkg: InternedString) {
    467        self.deps.entry(pkg).or_default();
    468    }
    469
    470    fn require_feature(&mut self, feat: InternedString) -> Result<(), RequirementError> {
    471        if !self.features.insert(feat) {
    472            // Already seen this feature.
    473            return Ok(());
    474        }
    475
    476        let Some(fvs) = self.summary.features().get(&feat) else {
    477            return Err(RequirementError::MissingFeature(feat));
    478        };
    479
    480        for fv in fvs {
    481            if let FeatureValue::Feature(dep_feat) = fv {
    482                if *dep_feat == feat {
    483                    return Err(RequirementError::Cycle(feat));
    484                }
    485            }
    486            self.require_value(fv)?;
    487        }
    488        Ok(())
    489    }
    490
    491    fn require_value(&mut self, fv: &FeatureValue) -> Result<(), RequirementError> {
    492        match fv {
    493            FeatureValue::Feature(feat) => self.require_feature(*feat)?,
    494            FeatureValue::Dep { dep_name } => self.require_dependency(*dep_name),
    495            FeatureValue::DepFeature {
    496                dep_name,
    497                dep_feature,
    498                // Weak features are always activated in the dependency
    499                // resolver. They will be narrowed inside the new feature
    500                // resolver.
    501                weak,
    502            } => self.require_dep_feature(*dep_name, *dep_feature, *weak)?,
    503        };
    504        Ok(())
    505    }
    506}
    507
    508impl RequirementError {
    509    fn into_activate_error(self, parent: Option<PackageId>, summary: &Summary) -> ActivateError {
    510        match self {
    511            RequirementError::MissingFeature(feat) => {
    512                let deps: Vec<_> = summary
    513                    .dependencies()
    514                    .iter()
    515                    .filter(|dep| dep.name_in_toml() == feat)
    516                    .collect();
    517                if deps.is_empty() {
    518                    return match parent {
    519                        None => {
    520                            let closest = closest_msg(
    521                                &feat.as_str(),
    522                                summary.features().keys(),
    523                                |key| &key,
    524                                "feature",
    525                            );
    526                            ActivateError::Fatal(anyhow::format_err!(
    527                                "package `{}` does not have the feature `{}`{}",
    528                                summary.package_id(),
    529                                feat,
    530                                closest
    531                            ))
    532                        }
    533                        Some(p) => ActivateError::Conflict(p, ConflictReason::MissingFeature(feat)),
    534                    };
    535                }
    536                if deps.iter().any(|dep| dep.is_optional()) {
    537                    match parent {
    538                        None => {
    539                            let mut features =
    540                                features_enabling_dependency_sorted(summary, feat).peekable();
    541                            let mut suggestion = String::new();
    542                            if features.peek().is_some() {
    543                                suggestion = format!(
    544                                    "\nDependency `{}` would be enabled by these features:",
    545                                    feat
    546                                );
    547                                for feature in (&mut features).take(3) {
    548                                    let _ = write!(&mut suggestion, "\n\t- `{}`", feature);
    549                                }
    550                                if features.peek().is_some() {
    551                                    suggestion.push_str("\n\t  ...");
    552                                }
    553                            }
    554                            ActivateError::Fatal(anyhow::format_err!(
    555                                "\
    556package `{}` does not have feature `{}`
    557
    558help: an optional dependency \
    559with that name exists, but the `features` table includes it with the \"dep:\" \
    560syntax so it does not have an implicit feature with that name{}",
    561                                summary.package_id(),
    562                                feat,
    563                                suggestion
    564                            ))
    565                        }
    566                        Some(p) => ActivateError::Conflict(
    567                            p,
    568                            ConflictReason::NonImplicitDependencyAsFeature(feat),
    569                        ),
    570                    }
    571                } else {
    572                    match parent {
    573                        None => ActivateError::Fatal(anyhow::format_err!(
    574                            "package `{}` does not have feature `{}`
    575
    576help: a depednency with that name exists but it is required dependency and only optional dependencies can be used as features.",
    577                            summary.package_id(),
    578                            feat,
    579                        )),
    580                        Some(p) => ActivateError::Conflict(
    581                            p,
    582                            ConflictReason::RequiredDependencyAsFeature(feat),
    583                        ),
    584                    }
    585                }
    586            }
    587            RequirementError::MissingDependency(dep_name) => {
    588                match parent {
    589                    None => ActivateError::Fatal(anyhow::format_err!(
    590                        "package `{}` does not have a dependency named `{}`",
    591                        summary.package_id(),
    592                        dep_name
    593                    )),
    594                    // This code path currently isn't used, since `foo/bar`
    595                    // and `dep:` syntax is not allowed in a dependency.
    596                    Some(p) => ActivateError::Conflict(p, ConflictReason::MissingFeature(dep_name)),
    597                }
    598            }
    599            RequirementError::Cycle(feat) => ActivateError::Fatal(anyhow::format_err!(
    600                "cyclic feature dependency: feature `{}` depends on itself",
    601                feat
    602            )),
    603        }
    604    }
    605}
    606
    607/// Collect any features which enable the optional dependency "target_dep".
    608///
    609/// The returned value will be sorted.
    610fn features_enabling_dependency_sorted(
    611    summary: &Summary,
    612    target_dep: InternedString,
    613) -> impl Iterator<Item = InternedString> + '_ {
    614    let iter = summary
    615        .features()
    616        .iter()
    617        .filter(move |(_, values)| {
    618            for value in *values {
    619                match value {
    620                    FeatureValue::Dep { dep_name }
    621                    | FeatureValue::DepFeature {
    622                        dep_name,
    623                        weak: false,
    624                        ..
    625                    } if dep_name == &target_dep => return true,
    626                    _ => (),
    627                }
    628            }
    629            false
    630        })
    631        .map(|(name, _)| *name);
    632    // iter is already sorted because it was constructed from a BTreeMap.
    633    iter
    634}