1 //! There are 2 sources of facts for the resolver:
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.
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.
10 //! This module impl that cache in all the gory details
12 use crate::core
::resolver
::context
::Context
;
13 use crate::core
::resolver
::errors
::describe_path_in_context
;
14 use crate::core
::resolver
::types
::{ConflictReason, DepInfo, FeaturesSet}
;
15 use crate::core
::resolver
::{
16 ActivateError
, ActivateResult
, CliFeatures
, RequestedFeatures
, ResolveOpts
, VersionOrdering
,
19 use crate::core
::{Dependency, FeatureValue, PackageId, PackageIdSpec, Registry, Summary}
;
20 use crate::util
::errors
::CargoResult
;
21 use crate::util
::interning
::InternedString
;
23 use anyhow
::Context
as _
;
25 use std
::collections
::{BTreeSet, HashMap, HashSet}
;
28 pub struct RegistryQueryer
<'a
> {
29 pub registry
: &'a
mut (dyn Registry
+ 'a
),
30 replacements
: &'a
[(PackageIdSpec
, Dependency
)],
31 version_prefs
: &'a VersionPreferences
,
32 /// If set the list of dependency candidates will be sorted by minimal
33 /// versions first. That allows `cargo update -Z minimal-versions` which will
34 /// specify minimum dependency versions to be used.
35 minimal_versions
: bool
,
36 /// a cache of `Candidate`s that fulfil a `Dependency`
37 registry_cache
: HashMap
<Dependency
, Rc
<Vec
<Summary
>>>,
38 /// a cache of `Dependency`s that are required for a `Summary`
39 summary_cache
: HashMap
<
40 (Option
<PackageId
>, Summary
, ResolveOpts
),
41 Rc
<(HashSet
<InternedString
>, Rc
<Vec
<DepInfo
>>)>,
43 /// all the cases we ended up using a supplied replacement
44 used_replacements
: HashMap
<PackageId
, Summary
>,
47 impl<'a
> RegistryQueryer
<'a
> {
49 registry
: &'a
mut dyn Registry
,
50 replacements
: &'a
[(PackageIdSpec
, Dependency
)],
51 version_prefs
: &'a VersionPreferences
,
52 minimal_versions
: bool
,
59 registry_cache
: HashMap
::new(),
60 summary_cache
: HashMap
::new(),
61 used_replacements
: HashMap
::new(),
65 pub fn used_replacement_for(&self, p
: PackageId
) -> Option
<(PackageId
, PackageId
)> {
66 self.used_replacements
.get(&p
).map(|r
| (p
, r
.package_id()))
69 pub fn replacement_summary(&self, p
: PackageId
) -> Option
<&Summary
> {
70 self.used_replacements
.get(&p
)
73 /// Queries the `registry` to return a list of candidates for `dep`.
75 /// This method is the location where overrides are taken into account. If
76 /// any candidates are returned which match an override then the override is
77 /// applied by performing a second query for what the override should
79 pub fn query(&mut self, dep
: &Dependency
) -> CargoResult
<Rc
<Vec
<Summary
>>> {
80 if let Some(out
) = self.registry_cache
.get(dep
).cloned() {
84 let mut ret
= Vec
::new();
92 for summary
in ret
.iter_mut() {
93 let mut potential_matches
= self
96 .filter(|&&(ref spec
, _
)| spec
.matches(summary
.package_id()));
98 let &(ref spec
, ref dep
) = match potential_matches
.next() {
100 Some(replacement
) => replacement
,
103 "found an override for {} {}",
108 let mut summaries
= self.registry
.query_vec(dep
, false)?
.into_iter();
109 let s
= summaries
.next().ok_or_else(|| {
111 "no matching package for override `{}` found\n\
112 location searched: {}\n\
113 version required: {}",
119 let summaries
= summaries
.collect
::<Vec
<_
>>();
120 if !summaries
.is_empty() {
121 let bullets
= summaries
123 .map(|s
| format
!(" * {}", s
.package_id()))
124 .collect
::<Vec
<_
>>();
126 "the replacement specification `{}` matched \
127 multiple packages:\n * {}\n{}",
134 // The dependency should be hard-coded to have the same name and an
135 // exact version requirement, so both of these assertions should
137 assert_eq
!(s
.version(), summary
.version());
138 assert_eq
!(s
.name(), summary
.name());
140 let replace
= if s
.source_id() == summary
.source_id() {
141 debug
!("Preventing\n{:?}\nfrom replacing\n{:?}", summary
, s
);
146 let matched_spec
= spec
.clone();
148 // Make sure no duplicates
149 if let Some(&(ref spec
, _
)) = potential_matches
.next() {
151 "overlapping replacement specifications found:\n\n \
152 * {}\n * {}\n\nboth specifications match: {}",
159 for dep
in summary
.dependencies() {
160 debug
!("\t{} => {}", dep
.package_name(), dep
.version_req());
162 if let Some(r
) = replace
{
163 self.used_replacements
.insert(summary
.package_id(), r
);
167 // When we attempt versions for a package we'll want to do so in a sorted fashion to pick
168 // the "best candidates" first. VersionPreferences implements this notion.
169 self.version_prefs
.sort_summaries(
171 if self.minimal_versions
{
172 VersionOrdering
::MinimumVersionsFirst
174 VersionOrdering
::MaximumVersionsFirst
178 let out
= Rc
::new(ret
);
180 self.registry_cache
.insert(dep
.clone(), out
.clone());
185 /// Find out what dependencies will be added by activating `candidate`,
186 /// with features described in `opts`. Then look up in the `registry`
187 /// the candidates that will fulfil each of these dependencies, as it is the
188 /// next obvious question.
192 parent
: Option
<PackageId
>,
195 ) -> ActivateResult
<Rc
<(HashSet
<InternedString
>, Rc
<Vec
<DepInfo
>>)>> {
196 // if we have calculated a result before, then we can just return it,
197 // as it is a "pure" query of its arguments.
198 if let Some(out
) = self
200 .get(&(parent
, candidate
.clone(), opts
.clone()))
205 // First, figure out our set of dependencies based on the requested set
206 // of features. This also calculates what features we're going to enable
207 // for our own dependencies.
208 let (used_features
, deps
) = resolve_features(parent
, candidate
, opts
)?
;
210 // Next, transform all dependencies into a list of possible candidates
211 // which can satisfy that dependency.
214 .map(|(dep
, features
)| {
215 let candidates
= self.query(&dep
).with_context(|| {
217 "failed to get `{}` as a dependency of {}",
219 describe_path_in_context(cx
, &candidate
.package_id()),
222 Ok((dep
, candidates
, features
))
224 .collect
::<CargoResult
<Vec
<DepInfo
>>>()?
;
226 // Attempt to resolve dependencies with fewer candidates before trying
227 // dependencies with more candidates. This way if the dependency with
228 // only one candidate can't be resolved we don't have to do a bunch of
229 // work before we figure that out.
230 deps
.sort_by_key(|&(_
, ref a
, _
)| a
.len());
232 let out
= Rc
::new((used_features
, Rc
::new(deps
)));
234 // If we succeed we add the result to the cache so we can use it again next time.
235 // We don't cache the failure cases as they don't impl Clone.
237 .insert((parent
, candidate
.clone(), opts
.clone()), out
.clone());
243 /// Returns the features we ended up using and
244 /// all dependencies and the features we want from each of them.
245 pub fn resolve_features
<'b
>(
246 parent
: Option
<PackageId
>,
248 opts
: &'b ResolveOpts
,
249 ) -> ActivateResult
<(HashSet
<InternedString
>, Vec
<(Dependency
, FeaturesSet
)>)> {
250 // First, filter by dev-dependencies.
251 let deps
= s
.dependencies();
252 let deps
= deps
.iter().filter(|d
| d
.is_transitive() || opts
.dev_deps
);
254 let reqs
= build_requirements(parent
, s
, opts
)?
;
255 let mut ret
= Vec
::new();
256 let default_dep
= BTreeSet
::new();
257 let mut valid_dep_names
= HashSet
::new();
259 // Next, collect all actually enabled dependencies and their features.
261 // Skip optional dependencies, but not those enabled through a
263 if dep
.is_optional() && !reqs
.deps
.contains_key(&dep
.name_in_toml()) {
266 valid_dep_names
.insert(dep
.name_in_toml());
267 // So we want this dependency. Move the features we want from
268 // `feature_deps` to `ret` and register ourselves as using this
272 .get(&dep
.name_in_toml())
273 .unwrap_or(&default_dep
)
275 base
.extend(dep
.features().iter());
276 ret
.push((dep
.clone(), Rc
::new(base
)));
279 // This is a special case for command-line `--features
280 // dep_name/feat_name` where `dep_name` does not exist. All other
281 // validation is done either in `build_requirements` or
282 // `build_feature_map`.
283 if parent
.is_none() {
284 for dep_name
in reqs
.deps
.keys() {
285 if !valid_dep_names
.contains(dep_name
) {
286 let e
= RequirementError
::MissingDependency(*dep_name
);
287 return Err(e
.into_activate_error(parent
, s
));
292 Ok((reqs
.into_features(), ret
))
295 /// Takes requested features for a single package from the input `ResolveOpts` and
296 /// recurses to find all requested features, dependencies and requested
297 /// dependency features in a `Requirements` object, returning it to the resolver.
298 fn build_requirements
<'a
, 'b
: 'a
>(
299 parent
: Option
<PackageId
>,
301 opts
: &'b ResolveOpts
,
302 ) -> ActivateResult
<Requirements
<'a
>> {
303 let mut reqs
= Requirements
::new(s
);
305 let handle_default
= |uses_default_features
, reqs
: &mut Requirements
<'_
>| {
306 if uses_default_features
&& s
.features().contains_key("default") {
307 if let Err(e
) = reqs
.require_feature(InternedString
::new("default")) {
308 return Err(e
.into_activate_error(parent
, s
));
314 match &opts
.features
{
315 RequestedFeatures
::CliFeatures(CliFeatures
{
318 uses_default_features
,
321 for key
in s
.features().keys() {
322 if let Err(e
) = reqs
.require_feature(*key
) {
323 return Err(e
.into_activate_error(parent
, s
));
327 for fv
in features
.iter() {
328 if let Err(e
) = reqs
.require_value(fv
) {
329 return Err(e
.into_activate_error(parent
, s
));
332 handle_default(*uses_default_features
, &mut reqs
)?
;
335 RequestedFeatures
::DepFeatures
{
337 uses_default_features
,
339 for feature
in features
.iter() {
340 if let Err(e
) = reqs
.require_feature(*feature
) {
341 return Err(e
.into_activate_error(parent
, s
));
344 handle_default(*uses_default_features
, &mut reqs
)?
;
351 /// Set of feature and dependency requirements for a package.
353 struct Requirements
<'a
> {
354 summary
: &'a Summary
,
355 /// The deps map is a mapping of dependency name to list of features enabled.
357 /// The resolver will activate all of these dependencies, with the given
358 /// features enabled.
359 deps
: HashMap
<InternedString
, BTreeSet
<InternedString
>>,
360 /// The set of features enabled on this package which is later used when
361 /// compiling to instruct the code what features were enabled.
362 features
: HashSet
<InternedString
>,
365 /// An error for a requirement.
367 /// This will later be converted to an `ActivateError` depending on whether or
368 /// not this is a dependency or a root package.
369 enum RequirementError
{
370 /// The package does not have the requested feature.
371 MissingFeature(InternedString
),
372 /// The package does not have the requested dependency.
373 MissingDependency(InternedString
),
374 /// A feature has a direct cycle to itself.
376 /// Note that cycles through multiple features are allowed (but perhaps
377 /// they shouldn't be?).
378 Cycle(InternedString
),
381 impl Requirements
<'_
> {
382 fn new(summary
: &Summary
) -> Requirements
<'_
> {
385 deps
: HashMap
::new(),
386 features
: HashSet
::new(),
390 fn into_features(self) -> HashSet
<InternedString
> {
394 fn require_dep_feature(
396 package
: InternedString
,
397 feat
: InternedString
,
399 ) -> Result
<(), RequirementError
> {
400 // If `package` is indeed an optional dependency then we activate the
401 // feature named `package`, but otherwise if `package` is a required
402 // dependency then there's no feature associated with it.
408 .any(|dep
| dep
.name_in_toml() == package
&& dep
.is_optional())
410 self.require_feature(package
)?
;
412 self.deps
.entry(package
).or_default().insert(feat
);
416 fn require_dependency(&mut self, pkg
: InternedString
) {
417 self.deps
.entry(pkg
).or_default();
420 fn require_feature(&mut self, feat
: InternedString
) -> Result
<(), RequirementError
> {
421 if !self.features
.insert(feat
) {
422 // Already seen this feature.
426 let fvs
= match self.summary
.features().get(&feat
) {
428 None
=> return Err(RequirementError
::MissingFeature(feat
)),
432 if let FeatureValue
::Feature(dep_feat
) = fv
{
433 if *dep_feat
== feat
{
434 return Err(RequirementError
::Cycle(feat
));
437 self.require_value(fv
)?
;
442 fn require_value(&mut self, fv
: &FeatureValue
) -> Result
<(), RequirementError
> {
444 FeatureValue
::Feature(feat
) => self.require_feature(*feat
)?
,
445 FeatureValue
::Dep { dep_name }
=> self.require_dependency(*dep_name
),
446 FeatureValue
::DepFeature
{
449 // Weak features are always activated in the dependency
450 // resolver. They will be narrowed inside the new feature
453 } => self.require_dep_feature(*dep_name
, *dep_feature
, *weak
)?
,
459 impl RequirementError
{
460 fn into_activate_error(self, parent
: Option
<PackageId
>, summary
: &Summary
) -> ActivateError
{
462 RequirementError
::MissingFeature(feat
) => {
463 let deps
: Vec
<_
> = summary
466 .filter(|dep
| dep
.name_in_toml() == feat
)
469 return match parent
{
470 None
=> ActivateError
::Fatal(anyhow
::format_err
!(
471 "Package `{}` does not have the feature `{}`",
472 summary
.package_id(),
475 Some(p
) => ActivateError
::Conflict(
477 ConflictReason
::MissingFeatures(feat
.to_string()),
481 if deps
.iter().any(|dep
| dep
.is_optional()) {
483 None
=> ActivateError
::Fatal(anyhow
::format_err
!(
484 "Package `{}` does not have feature `{}`. It has an optional dependency \
485 with that name, but that dependency uses the \"dep:\" \
486 syntax in the features table, so it does not have an implicit feature with that name.",
487 summary
.package_id(),
490 Some(p
) => ActivateError
::Conflict(
492 ConflictReason
::NonImplicitDependencyAsFeature(feat
),
497 None
=> ActivateError
::Fatal(anyhow
::format_err
!(
498 "Package `{}` does not have feature `{}`. It has a required dependency \
499 with that name, but only optional dependencies can be used as features.",
500 summary
.package_id(),
503 Some(p
) => ActivateError
::Conflict(
505 ConflictReason
::RequiredDependencyAsFeature(feat
),
510 RequirementError
::MissingDependency(dep_name
) => {
512 None
=> ActivateError
::Fatal(anyhow
::format_err
!(
513 "package `{}` does not have a dependency named `{}`",
514 summary
.package_id(),
517 // This code path currently isn't used, since `foo/bar`
518 // and `dep:` syntax is not allowed in a dependency.
519 Some(p
) => ActivateError
::Conflict(
521 ConflictReason
::MissingFeatures(dep_name
.to_string()),
525 RequirementError
::Cycle(feat
) => ActivateError
::Fatal(anyhow
::format_err
!(
526 "cyclic feature dependency: feature `{}` depends on itself",