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