#
cargo/core/resolver/
context.rs

    1use super::RequestedFeatures;
    2use super::dep_cache::RegistryQueryer;
    3use super::errors::ActivateResult;
    4use super::types::{ActivationsKey, ConflictMap, ConflictReason, FeaturesSet, ResolveOpts};
    5use crate::core::{Dependency, PackageId, Summary};
    6use crate::util::Graph;
    7use crate::util::interning::{INTERNED_DEFAULT, InternedString};
    8use anyhow::format_err;
    9use std::collections::{BTreeSet, HashMap};
    10use tracing::debug;
    11
    12// A `Context` is basically a bunch of local resolution information which is
    13// kept around for all `BacktrackFrame` instances. As a result, this runs the
    14// risk of being cloned *a lot* so we want to make this as cheap to clone as
    15// possible.
    16#[derive(Clone)]
    17pub struct ResolverContext {
    18    pub age: ContextAge,
    19    pub activations: Activations,
    20    /// list the features that are activated for each package
    21    pub resolve_features: im_rc::HashMap<PackageId, FeaturesSet, rustc_hash::FxBuildHasher>,
    22    /// get the package that will be linking to a native library by its links attribute
    23    pub links: im_rc::HashMap<InternedString, PackageId, rustc_hash::FxBuildHasher>,
    24
    25    /// a way to look up for a package in activations what packages required it
    26    /// and all of the exact deps that it fulfilled.
    27    pub parents: Graph<PackageId, im_rc::HashSet<Dependency, rustc_hash::FxBuildHasher>>,
    28}
    29
    30/// When backtracking it can be useful to know how far back to go.
    31/// The `ContextAge` of a `Context` is a monotonically increasing counter of the number
    32/// of decisions made to get to this state.
    33/// Several structures store the `ContextAge` when it was added,
    34/// to be used in `find_candidate` for backtracking.
    35pub type ContextAge = usize;
    36
    37/// Find the activated version of a crate based on the name, source, and semver compatibility.
    38/// By storing this in a hash map we ensure that there is only one
    39/// semver compatible version of each crate.
    40/// This all so stores the `ContextAge`.
    41pub type Activations =
    42    im_rc::HashMap<ActivationsKey, (Summary, ContextAge), rustc_hash::FxBuildHasher>;
    43
    44impl ResolverContext {
    45    pub fn new() -> ResolverContext {
    46        ResolverContext {
    47            age: 0,
    48            resolve_features: im_rc::HashMap::default(),
    49            links: im_rc::HashMap::default(),
    50            parents: Graph::new(),
    51            activations: im_rc::HashMap::default(),
    52        }
    53    }
    54
    55    /// Activate this summary by inserting it into our list of known activations.
    56    ///
    57    /// The `parent` passed in here is the parent summary/dependency edge which
    58    /// cased `summary` to get activated. This may not be present for the root
    59    /// crate, for example.
    60    ///
    61    /// Returns `true` if this summary with the given features is already activated.
    62    pub fn flag_activated(
    63        &mut self,
    64        summary: &Summary,
    65        opts: &ResolveOpts,
    66        parent: Option<(&Summary, &Dependency)>,
    67    ) -> ActivateResult<bool> {
    68        let id = summary.package_id();
    69        let age: ContextAge = self.age;
    70        match self.activations.entry(id.as_activations_key()) {
    71            im_rc::hashmap::Entry::Occupied(o) => {
    72                debug_assert_eq!(
    73                    &o.get().0,
    74                    summary,
    75                    "cargo does not allow two semver compatible versions"
    76                );
    77            }
    78            im_rc::hashmap::Entry::Vacant(v) => {
    79                if let Some(link) = summary.links() {
    80                    if self.links.insert(link, id).is_some() {
    81                        return Err(format_err!(
    82                            "Attempting to resolve a dependency with more than \
    83                             one crate with links={}.\nThis will not build as \
    84                             is. Consider rebuilding the .lock file.",
    85                            &*link
    86                        )
    87                        .into());
    88                    }
    89                }
    90                v.insert((summary.clone(), age));
    91
    92                // If we've got a parent dependency which activated us, *and*
    93                // the dependency has a different source id listed than the
    94                // `summary` itself, then things get interesting. This basically
    95                // means that a `[patch]` was used to augment `dep.source_id()`
    96                // with `summary`.
    97                //
    98                // In this scenario we want to consider the activation key, as
    99                // viewed from the perspective of `dep.source_id()`, as being
    100                // fulfilled. This means that we need to add a second entry in
    101                // the activations map for the source that was patched, in
    102                // addition to the source of the actual `summary` itself.
    103                //
    104                // Without this it would be possible to have both 1.0.0 and
    105                // 1.1.0 "from crates.io" in a dependency graph if one of those
    106                // versions came from a `[patch]` source.
    107                if let Some((_, dep)) = parent {
    108                    if dep.source_id() != id.source_id() {
    109                        let key =
    110                            ActivationsKey::new(id.name(), id.version().into(), dep.source_id());
    111                        let prev = self.activations.insert(key, (summary.clone(), age));
    112                        if let Some((previous_summary, _)) = prev {
    113                            return Err(
    114                                (previous_summary.package_id(), ConflictReason::Semver).into()
    115                            );
    116                        }
    117                    }
    118                }
    119
    120                return Ok(false);
    121            }
    122        }
    123        debug!("checking if {} is already activated", summary.package_id());
    124        let empty_features = BTreeSet::new();
    125        match &opts.features {
    126            // This returns `false` for CliFeatures just for simplicity. It
    127            // would take a bit of work to compare since they are not in the
    128            // same format as DepFeatures (and that may be expensive
    129            // performance-wise). Also, it should only occur once for a root
    130            // package. The only drawback is that it may re-activate a root
    131            // package again, which should only affect performance, but that
    132            // should be rare. Cycles should still be detected since those
    133            // will have `DepFeatures` edges.
    134            RequestedFeatures::CliFeatures(_) => Ok(false),
    135            RequestedFeatures::DepFeatures {
    136                features,
    137                uses_default_features,
    138            } => {
    139                let has_default_feature = summary.features().contains_key(&INTERNED_DEFAULT);
    140                let prev = self
    141                    .resolve_features
    142                    .get(&id)
    143                    .map(|f| &**f)
    144                    .unwrap_or(&empty_features);
    145                Ok(features.is_subset(prev)
    146                    && (!uses_default_features
    147                        || prev.contains(&INTERNED_DEFAULT)
    148                        || !has_default_feature))
    149            }
    150        }
    151    }
    152
    153    /// If the package is active returns the `ContextAge` when it was added
    154    pub fn is_active(&self, id: PackageId) -> Option<ContextAge> {
    155        self.activations
    156            .get(&id.as_activations_key())
    157            .and_then(|(s, l)| if s.package_id() == id { Some(*l) } else { None })
    158    }
    159
    160    /// Checks whether all of `parent` and the keys of `conflicting activations`
    161    /// are still active.
    162    /// If so returns the `ContextAge` when the newest one was added.
    163    pub fn is_conflicting(
    164        &self,
    165        parent: Option<PackageId>,
    166        conflicting_activations: &ConflictMap,
    167    ) -> Option<usize> {
    168        let mut max = 0;
    169        if let Some(parent) = parent {
    170            max = std::cmp::max(max, self.is_active(parent)?);
    171        }
    172
    173        for id in conflicting_activations.keys() {
    174            max = std::cmp::max(max, self.is_active(*id)?);
    175        }
    176        Some(max)
    177    }
    178
    179    pub fn resolve_replacements(
    180        &self,
    181        registry: &RegistryQueryer<'_>,
    182    ) -> HashMap<PackageId, PackageId> {
    183        self.activations
    184            .values()
    185            .filter_map(|(s, _)| registry.used_replacement_for(s.package_id()))
    186            .collect()
    187    }
    188
    189    pub fn graph(&self) -> Graph<PackageId, std::collections::HashSet<Dependency>> {
    190        let mut graph: Graph<PackageId, std::collections::HashSet<Dependency>> = Graph::new();
    191        self.activations
    192            .values()
    193            .for_each(|(r, _)| graph.add(r.package_id()));
    194        for i in self.parents.iter() {
    195            graph.add(*i);
    196            for (o, e) in self.parents.edges(i) {
    197                let old_link = graph.link(*o, *i);
    198                assert!(old_link.is_empty());
    199                *old_link = e.iter().cloned().collect();
    200            }
    201        }
    202        graph
    203    }
    204}