cargo/core/resolver/context.rs
1use super::dep_cache::RegistryQueryer;
2use super::errors::ActivateResult;
3use super::types::{ActivationsKey, ConflictMap, ConflictReason, FeaturesSet, ResolveOpts};
4use super::RequestedFeatures;
5use crate::core::{Dependency, PackageId, Summary};
6use crate::util::interning::{InternedString, INTERNED_DEFAULT};
7use crate::util::Graph;
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}