cargo/core/resolver/mod.rs
1//! Resolution of the entire dependency graph for a crate.
2//!
3//! This module implements the core logic in taking the world of crates and
4//! constraints and creating a resolved graph with locked versions for all
5//! crates and their dependencies. This is separate from the registry module
6//! which is more worried about discovering crates from various sources, this
7//! module just uses the Registry trait as a source to learn about crates from.
8//!
9//! Actually solving a constraint graph is an NP-hard problem. This algorithm
10//! is basically a nice heuristic to make sure we get roughly the best answer
11//! most of the time. The constraints that we're working with are:
12//!
13//! 1. Each crate can have any number of dependencies. Each dependency can
14//! declare a version range that it is compatible with.
15//! 2. Crates can be activated with multiple version (e.g., show up in the
16//! dependency graph twice) so long as each pairwise instance have
17//! semver-incompatible versions.
18//!
19//! The algorithm employed here is fairly simple, we simply do a DFS, activating
20//! the "newest crate" (highest version) first and then going to the next
21//! option. The heuristics we employ are:
22//!
23//! * Never try to activate a crate version which is incompatible. This means we
24//! only try crates which will actually satisfy a dependency and we won't ever
25//! try to activate a crate that's semver compatible with something else
26//! activated (as we're only allowed to have one) nor try to activate a crate
27//! that has the same links attribute as something else
28//! activated.
29//! * Always try to activate the highest version crate first. The default
30//! dependency in Cargo (e.g., when you write `foo = "0.1.2"`) is
31//! semver-compatible, so selecting the highest version possible will allow us
32//! to hopefully satisfy as many dependencies at once.
33//!
34//! Beyond that, what's implemented below is just a naive backtracking version
35//! which should in theory try all possible combinations of dependencies and
36//! versions to see if one works. The first resolution that works causes
37//! everything to bail out immediately and return success, and only if *nothing*
38//! works do we actually return an error up the stack.
39//!
40//! Resolution is currently performed twice
41//! 1. With all features enabled (this is what gets saved to `Cargo.lock`)
42//! 2. With only the specific features the user selected on the command-line. Ideally this
43//! run will get removed in the future when transitioning to the new feature resolver.
44//!
45//! A new feature-specific resolver was added in 2020 which adds more sophisticated feature
46//! resolution. It is located in the [`features`] module. The original dependency resolver still
47//! performs feature unification, as it can help reduce the dependencies it has to consider during
48//! resolution (rather than assuming every optional dependency of every package is enabled).
49//! Checking if a feature is enabled must go through the new feature resolver.
50//!
51//! ## Performance
52//!
53//! Note that this is a relatively performance-critical portion of Cargo. The
54//! data that we're processing is proportional to the size of the dependency
55//! graph, which can often be quite large (e.g., take a look at Servo). To make
56//! matters worse the DFS algorithm we're implemented is inherently quite
57//! inefficient. When we add the requirement of backtracking on top it means
58//! that we're implementing something that probably shouldn't be allocating all
59//! over the place.
60
61use std::collections::{BTreeMap, HashMap, HashSet};
62use std::rc::Rc;
63use std::time::{Duration, Instant};
64
65use tracing::{debug, trace};
66
67use crate::core::PackageIdSpec;
68use crate::core::{Dependency, PackageId, Registry, Summary};
69use crate::util::context::GlobalContext;
70use crate::util::errors::CargoResult;
71use crate::util::network::PollExt;
72
73use self::context::ResolverContext;
74use self::dep_cache::RegistryQueryer;
75use self::features::RequestedFeatures;
76use self::types::{ConflictMap, ConflictReason, DepsFrame};
77use self::types::{FeaturesSet, RcVecIter, RemainingDeps, ResolverProgress};
78
79pub use self::errors::{ActivateError, ActivateResult, ResolveError};
80pub use self::features::{CliFeatures, ForceAllTargets, HasDevUnits};
81pub use self::resolve::{Resolve, ResolveVersion};
82pub use self::types::{ResolveBehavior, ResolveOpts};
83pub use self::version_prefs::{VersionOrdering, VersionPreferences};
84
85mod conflict_cache;
86mod context;
87mod dep_cache;
88pub(crate) mod encode;
89pub(crate) mod errors;
90pub mod features;
91mod resolve;
92mod types;
93mod version_prefs;
94
95/// Builds the list of all packages required to build the first argument.
96///
97/// * `summaries` - the list of package summaries along with how to resolve
98/// their features. This is a list of all top-level packages that are intended
99/// to be part of the lock file (resolve output). These typically are a list
100/// of all workspace members.
101///
102/// * `replacements` - this is a list of `[replace]` directives found in the
103/// root of the workspace. The list here is a `PackageIdSpec` of what to
104/// replace and a `Dependency` to replace that with. In general it's not
105/// recommended to use `[replace]` any more and use `[patch]` instead, which
106/// is supported elsewhere.
107///
108/// * `registry` - this is the source from which all package summaries are
109/// loaded. It's expected that this is extensively configured ahead of time
110/// and is idempotent with our requests to it (aka returns the same results
111/// for the same query every time). Typically this is an instance of a
112/// `PackageRegistry`.
113///
114/// * `version_prefs` - this represents a preference for some versions over others,
115/// based on the lock file or other reasons such as `[patch]`es.
116///
117/// * `resolve_version` - this controls how the lockfile will be serialized.
118///
119/// * `config` - a location to print warnings and such, or `None` if no warnings
120/// should be printed
121#[tracing::instrument(skip_all)]
122pub fn resolve(
123 summaries: &[(Summary, ResolveOpts)],
124 replacements: &[(PackageIdSpec, Dependency)],
125 registry: &mut dyn Registry,
126 version_prefs: &VersionPreferences,
127 resolve_version: ResolveVersion,
128 gctx: Option<&GlobalContext>,
129) -> CargoResult<Resolve> {
130 let first_version = match gctx {
131 Some(config) if config.cli_unstable().direct_minimal_versions => {
132 Some(VersionOrdering::MinimumVersionsFirst)
133 }
134 _ => None,
135 };
136 let mut registry = RegistryQueryer::new(registry, replacements, version_prefs);
137
138 // Global cache of the reasons for each time we backtrack.
139 let mut past_conflicting_activations = conflict_cache::ConflictCache::new();
140
141 let resolver_ctx = loop {
142 let resolver_ctx = activate_deps_loop(
143 &mut registry,
144 summaries,
145 first_version,
146 gctx,
147 &mut past_conflicting_activations,
148 )?;
149 if registry.reset_pending() {
150 break resolver_ctx;
151 } else {
152 registry.registry.block_until_ready()?;
153 }
154 };
155
156 let mut cksums = HashMap::new();
157 for (summary, _) in resolver_ctx.activations.values() {
158 let cksum = summary.checksum().map(|s| s.to_string());
159 cksums.insert(summary.package_id(), cksum);
160 }
161 let graph = resolver_ctx.graph();
162 let replacements = resolver_ctx.resolve_replacements(®istry);
163 let features = resolver_ctx
164 .resolve_features
165 .iter()
166 .map(|(k, v)| (*k, v.iter().cloned().collect()))
167 .collect();
168 let summaries = resolver_ctx
169 .activations
170 .into_iter()
171 .map(|(_key, (summary, _age))| (summary.package_id(), summary))
172 .collect();
173 let resolve = Resolve::new(
174 graph,
175 replacements,
176 features,
177 cksums,
178 BTreeMap::new(),
179 Vec::new(),
180 resolve_version,
181 summaries,
182 );
183
184 check_cycles(&resolve)?;
185 check_duplicate_pkgs_in_lockfile(&resolve)?;
186 trace!("resolved: {:?}", resolve);
187
188 Ok(resolve)
189}
190
191/// Recursively activates the dependencies for `summaries`, in depth-first order,
192/// backtracking across possible candidates for each dependency as necessary.
193///
194/// If all dependencies can be activated and resolved to a version in the
195/// dependency graph, `cx` is returned.
196fn activate_deps_loop(
197 registry: &mut RegistryQueryer<'_>,
198 summaries: &[(Summary, ResolveOpts)],
199 first_version: Option<VersionOrdering>,
200 gctx: Option<&GlobalContext>,
201 past_conflicting_activations: &mut conflict_cache::ConflictCache,
202) -> CargoResult<ResolverContext> {
203 let mut resolver_ctx = ResolverContext::new();
204 let mut backtrack_stack = Vec::new();
205 let mut remaining_deps = RemainingDeps::new();
206
207 // Activate all the initial summaries to kick off some work.
208 for (summary, opts) in summaries {
209 debug!("initial activation: {}", summary.package_id());
210 let res = activate(
211 &mut resolver_ctx,
212 registry,
213 None,
214 summary.clone(),
215 first_version,
216 opts,
217 );
218 match res {
219 Ok(Some((frame, _))) => remaining_deps.push(frame),
220 Ok(None) => (),
221 Err(ActivateError::Fatal(e)) => return Err(e),
222 Err(ActivateError::Conflict(_, _)) => panic!("bad error from activate"),
223 }
224 }
225
226 let mut printed = ResolverProgress::new();
227
228 // Main resolution loop, this is the workhorse of the resolution algorithm.
229 //
230 // You'll note that a few stacks are maintained on the side, which might
231 // seem odd when this algorithm looks like it could be implemented
232 // recursively. While correct, this is implemented iteratively to avoid
233 // blowing the stack (the recursion depth is proportional to the size of the
234 // input).
235 //
236 // The general sketch of this loop is to run until there are no dependencies
237 // left to activate, and for each dependency to attempt to activate all of
238 // its own dependencies in turn. The `backtrack_stack` is a side table of
239 // backtracking states where if we hit an error we can return to in order to
240 // attempt to continue resolving.
241 while let Some((just_here_for_the_error_messages, frame)) =
242 remaining_deps.pop_most_constrained()
243 {
244 let (mut parent, (mut dep, candidates, mut features)) = frame;
245
246 // If we spend a lot of time here (we shouldn't in most cases) then give
247 // a bit of a visual indicator as to what we're doing.
248 printed.shell_status(gctx)?;
249
250 trace!(
251 "{}[{}]>{} {} candidates",
252 parent.name(),
253 resolver_ctx.age,
254 dep.package_name(),
255 candidates.len()
256 );
257
258 let just_here_for_the_error_messages = just_here_for_the_error_messages
259 && past_conflicting_activations
260 .conflicting(&resolver_ctx, &dep)
261 .is_some();
262
263 let mut remaining_candidates = RemainingCandidates::new(&candidates);
264
265 // `conflicting_activations` stores all the reasons we were unable to
266 // activate candidates. One of these reasons will have to go away for
267 // backtracking to find a place to restart. It is also the list of
268 // things to explain in the error message if we fail to resolve.
269 //
270 // This is a map of package ID to a reason why that packaged caused a
271 // conflict for us.
272 let mut conflicting_activations = ConflictMap::new();
273
274 // When backtracking we don't fully update `conflicting_activations`
275 // especially for the cases that we didn't make a backtrack frame in the
276 // first place. This `backtracked` var stores whether we are continuing
277 // from a restored backtrack frame so that we can skip caching
278 // `conflicting_activations` in `past_conflicting_activations`
279 let mut backtracked = false;
280
281 loop {
282 let next = remaining_candidates.next(&mut conflicting_activations, &resolver_ctx);
283
284 let (candidate, has_another) = next.ok_or(()).or_else(|_| {
285 // If we get here then our `remaining_candidates` was just
286 // exhausted, so `dep` failed to activate.
287 //
288 // It's our job here to backtrack, if possible, and find a
289 // different candidate to activate. If we can't find any
290 // candidates whatsoever then it's time to bail entirely.
291 trace!(
292 "{}[{}]>{} -- no candidates",
293 parent.name(),
294 resolver_ctx.age,
295 dep.package_name()
296 );
297
298 // Use our list of `conflicting_activations` to add to our
299 // global list of past conflicting activations, effectively
300 // globally poisoning `dep` if `conflicting_activations` ever
301 // shows up again. We'll use the `past_conflicting_activations`
302 // below to determine if a dependency is poisoned and skip as
303 // much work as possible.
304 //
305 // If we're only here for the error messages then there's no
306 // need to try this as this dependency is already known to be
307 // bad.
308 //
309 // As we mentioned above with the `backtracked` variable if this
310 // local is set to `true` then our `conflicting_activations` may
311 // not be right, so we can't push into our global cache.
312 let mut generalize_conflicting_activations = None;
313 if !just_here_for_the_error_messages && !backtracked {
314 past_conflicting_activations.insert(&dep, &conflicting_activations);
315 if let Some(c) = generalize_conflicting(
316 &resolver_ctx,
317 registry,
318 past_conflicting_activations,
319 &parent,
320 &dep,
321 &conflicting_activations,
322 ) {
323 generalize_conflicting_activations = Some(c);
324 }
325 }
326
327 match find_candidate(
328 &resolver_ctx,
329 &mut backtrack_stack,
330 &parent,
331 backtracked,
332 generalize_conflicting_activations
333 .as_ref()
334 .unwrap_or(&conflicting_activations),
335 ) {
336 Some((candidate, has_another, frame)) => {
337 // Reset all of our local variables used with the
338 // contents of `frame` to complete our backtrack.
339 resolver_ctx = frame.context;
340 remaining_deps = frame.remaining_deps;
341 remaining_candidates = frame.remaining_candidates;
342 parent = frame.parent;
343 dep = frame.dep;
344 features = frame.features;
345 conflicting_activations = frame.conflicting_activations;
346 backtracked = true;
347 Ok((candidate, has_another))
348 }
349 None => {
350 debug!("no candidates found");
351 Err(errors::activation_error(
352 &resolver_ctx,
353 registry.registry,
354 &parent,
355 &dep,
356 &conflicting_activations,
357 &candidates,
358 gctx,
359 ))
360 }
361 }
362 })?;
363
364 // If we're only here for the error messages then we know that this
365 // activation will fail one way or another. To that end if we've got
366 // more candidates we want to fast-forward to the last one as
367 // otherwise we'll just backtrack here anyway (helping us to skip
368 // some work).
369 if just_here_for_the_error_messages && !backtracked && has_another {
370 continue;
371 }
372
373 // We have a `candidate`. Create a `BacktrackFrame` so we can add it
374 // to the `backtrack_stack` later if activation succeeds.
375 //
376 // Note that if we don't actually have another candidate then there
377 // will be nothing to backtrack to so we skip construction of the
378 // frame. This is a relatively important optimization as a number of
379 // the `clone` calls below can be quite expensive, so we avoid them
380 // if we can.
381 let backtrack = if has_another {
382 Some(BacktrackFrame {
383 context: ResolverContext::clone(&resolver_ctx),
384 remaining_deps: remaining_deps.clone(),
385 remaining_candidates: remaining_candidates.clone(),
386 parent: Summary::clone(&parent),
387 dep: Dependency::clone(&dep),
388 features: Rc::clone(&features),
389 conflicting_activations: conflicting_activations.clone(),
390 })
391 } else {
392 None
393 };
394
395 let pid = candidate.package_id();
396 let opts = ResolveOpts {
397 dev_deps: false,
398 features: RequestedFeatures::DepFeatures {
399 features: Rc::clone(&features),
400 uses_default_features: dep.uses_default_features(),
401 },
402 };
403 trace!(
404 "{}[{}]>{} trying {}",
405 parent.name(),
406 resolver_ctx.age,
407 dep.package_name(),
408 candidate.version()
409 );
410 let first_version = None; // this is an indirect dependency
411 let res = activate(
412 &mut resolver_ctx,
413 registry,
414 Some((&parent, &dep)),
415 candidate,
416 first_version,
417 &opts,
418 );
419
420 let successfully_activated = match res {
421 // Success! We've now activated our `candidate` in our context
422 // and we're almost ready to move on. We may want to scrap this
423 // frame in the end if it looks like it's not going to end well,
424 // so figure that out here.
425 Ok(Some((mut frame, dur))) => {
426 printed.elapsed(dur);
427
428 // Our `frame` here is a new package with its own list of
429 // dependencies. Do a sanity check here of all those
430 // dependencies by cross-referencing our global
431 // `past_conflicting_activations`. Recall that map is a
432 // global cache which lists sets of packages where, when
433 // activated, the dependency is unresolvable.
434 //
435 // If any our frame's dependencies fit in that bucket,
436 // aka known unresolvable, then we extend our own set of
437 // conflicting activations with theirs. We can do this
438 // because the set of conflicts we found implies the
439 // dependency can't be activated which implies that we
440 // ourselves can't be activated, so we know that they
441 // conflict with us.
442 let mut has_past_conflicting_dep = just_here_for_the_error_messages;
443 if !has_past_conflicting_dep {
444 if let Some(conflicting) =
445 frame
446 .remaining_siblings
447 .remaining()
448 .find_map(|(new_dep, _, _)| {
449 past_conflicting_activations.conflicting(&resolver_ctx, new_dep)
450 })
451 {
452 // If one of our deps is known unresolvable
453 // then we will not succeed.
454 // How ever if we are part of the reason that
455 // one of our deps conflicts then
456 // we can make a stronger statement
457 // because we will definitely be activated when
458 // we try our dep.
459 conflicting_activations.extend(
460 conflicting
461 .iter()
462 .filter(|&(p, _)| p != &pid)
463 .map(|(&p, r)| (p, r.clone())),
464 );
465
466 has_past_conflicting_dep = true;
467 }
468 }
469 // If any of `remaining_deps` are known unresolvable with
470 // us activated, then we extend our own set of
471 // conflicting activations with theirs and its parent. We can do this
472 // because the set of conflicts we found implies the
473 // dependency can't be activated which implies that we
474 // ourselves are incompatible with that dep, so we know that deps
475 // parent conflict with us.
476 if !has_past_conflicting_dep {
477 if let Some(known_related_bad_deps) =
478 past_conflicting_activations.dependencies_conflicting_with(pid)
479 {
480 if let Some((other_parent, conflict)) = remaining_deps
481 .iter()
482 // for deps related to us
483 .filter(|(_, other_dep)| known_related_bad_deps.contains(other_dep))
484 .filter_map(|(other_parent, other_dep)| {
485 past_conflicting_activations
486 .find_conflicting(&resolver_ctx, &other_dep, Some(pid))
487 .map(|con| (other_parent, con))
488 })
489 .next()
490 {
491 let rel = conflict.get(&pid).unwrap().clone();
492
493 // The conflict we found is
494 // "other dep will not succeed if we are activated."
495 // We want to add
496 // "our dep will not succeed if other dep is in remaining_deps"
497 // but that is not how the cache is set up.
498 // So we add the less general but much faster,
499 // "our dep will not succeed if other dep's parent is activated".
500 conflicting_activations.extend(
501 conflict
502 .iter()
503 .filter(|&(p, _)| p != &pid)
504 .map(|(&p, r)| (p, r.clone())),
505 );
506 conflicting_activations.insert(other_parent, rel);
507 has_past_conflicting_dep = true;
508 }
509 }
510 }
511
512 // Ok if we're in a "known failure" state for this frame we
513 // may want to skip it altogether though. We don't want to
514 // skip it though in the case that we're displaying error
515 // messages to the user!
516 //
517 // Here we need to figure out if the user will see if we
518 // skipped this candidate (if it's known to fail, aka has a
519 // conflicting dep and we're the last candidate). If we're
520 // here for the error messages, we can't skip it (but we can
521 // prune extra work). If we don't have any candidates in our
522 // backtrack stack then we're the last line of defense, so
523 // we'll want to present an error message for sure.
524 let activate_for_error_message = has_past_conflicting_dep && !has_another && {
525 just_here_for_the_error_messages || {
526 find_candidate(
527 &resolver_ctx,
528 &mut backtrack_stack.clone(),
529 &parent,
530 backtracked,
531 &conflicting_activations,
532 )
533 .is_none()
534 }
535 };
536
537 // If we're only here for the error messages then we know
538 // one of our candidate deps will fail, meaning we will
539 // fail and that none of the backtrack frames will find a
540 // candidate that will help. Consequently let's clean up the
541 // no longer needed backtrack frames.
542 if activate_for_error_message {
543 backtrack_stack.clear();
544 }
545
546 // If we don't know for a fact that we'll fail or if we're
547 // just here for the error message then we push this frame
548 // onto our list of to-be-resolve, which will generate more
549 // work for us later on.
550 //
551 // Otherwise we're guaranteed to fail and were not here for
552 // error messages, so we skip work and don't push anything
553 // onto our stack.
554 frame.just_for_error_messages = has_past_conflicting_dep;
555 if !has_past_conflicting_dep || activate_for_error_message {
556 remaining_deps.push(frame);
557 true
558 } else {
559 trace!(
560 "{}[{}]>{} skipping {} ",
561 parent.name(),
562 resolver_ctx.age,
563 dep.package_name(),
564 pid.version()
565 );
566 false
567 }
568 }
569
570 // This candidate's already activated, so there's no extra work
571 // for us to do. Let's keep going.
572 Ok(None) => true,
573
574 // We failed with a super fatal error (like a network error), so
575 // bail out as quickly as possible as we can't reliably
576 // backtrack from errors like these
577 Err(ActivateError::Fatal(e)) => return Err(e),
578
579 // We failed due to a bland conflict, bah! Record this in our
580 // frame's list of conflicting activations as to why this
581 // candidate failed, and then move on.
582 Err(ActivateError::Conflict(id, reason)) => {
583 conflicting_activations.insert(id, reason);
584 false
585 }
586 };
587
588 // If we've successfully activated then save off the backtrack frame
589 // if one was created, and otherwise break out of the inner
590 // activation loop as we're ready to move to the next dependency
591 if successfully_activated {
592 backtrack_stack.extend(backtrack);
593 break;
594 }
595
596 // We've failed to activate this dependency, oh dear! Our call to
597 // `activate` above may have altered our `cx` local variable, so
598 // restore it back if we've got a backtrack frame.
599 //
600 // If we don't have a backtrack frame then we're just using the `cx`
601 // for error messages anyway so we can live with a little
602 // imprecision.
603 if let Some(b) = backtrack {
604 resolver_ctx = b.context;
605 }
606 }
607
608 // Ok phew, that loop was a big one! If we've broken out then we've
609 // successfully activated a candidate. Our stacks are all in place that
610 // we're ready to move on to the next dependency that needs activation,
611 // so loop back to the top of the function here.
612 }
613
614 Ok(resolver_ctx)
615}
616
617/// Attempts to activate the summary `candidate` in the context `cx`.
618///
619/// This function will pull dependency summaries from the registry provided, and
620/// the dependencies of the package will be determined by the `opts` provided.
621/// If `candidate` was activated, this function returns the dependency frame to
622/// iterate through next.
623fn activate(
624 cx: &mut ResolverContext,
625 registry: &mut RegistryQueryer<'_>,
626 parent: Option<(&Summary, &Dependency)>,
627 candidate: Summary,
628 first_version: Option<VersionOrdering>,
629 opts: &ResolveOpts,
630) -> ActivateResult<Option<(DepsFrame, Duration)>> {
631 let candidate_pid = candidate.package_id();
632 cx.age += 1;
633 if let Some((parent, dep)) = parent {
634 let parent_pid = parent.package_id();
635 // add an edge from candidate to parent in the parents graph
636 cx.parents
637 .link(candidate_pid, parent_pid)
638 // and associate dep with that edge
639 .insert(dep.clone());
640 }
641
642 let activated = cx.flag_activated(&candidate, opts, parent)?;
643
644 let candidate = match registry.replacement_summary(candidate_pid) {
645 Some(replace) => {
646 // Note the `None` for parent here since `[replace]` is a bit wonky
647 // and doesn't activate the same things that `[patch]` typically
648 // does. TBH it basically cause panics in the test suite if
649 // `parent` is passed through here and `[replace]` is otherwise
650 // on life support so it's not critical to fix bugs anyway per se.
651 if cx.flag_activated(replace, opts, None)? && activated {
652 return Ok(None);
653 }
654 trace!(
655 "activating {} (replacing {})",
656 replace.package_id(),
657 candidate_pid
658 );
659 replace.clone()
660 }
661 None => {
662 if activated {
663 return Ok(None);
664 }
665 trace!("activating {}", candidate_pid);
666 candidate
667 }
668 };
669
670 let now = Instant::now();
671 let (used_features, deps) = &*registry.build_deps(
672 cx,
673 parent.map(|p| p.0.package_id()),
674 &candidate,
675 opts,
676 first_version,
677 )?;
678
679 // Record what list of features is active for this package.
680 if !used_features.is_empty() {
681 Rc::make_mut(
682 cx.resolve_features
683 .entry(candidate.package_id())
684 .or_default(),
685 )
686 .extend(used_features);
687 }
688
689 let frame = DepsFrame {
690 parent: candidate,
691 just_for_error_messages: false,
692 remaining_siblings: RcVecIter::new(Rc::clone(deps)),
693 };
694 Ok(Some((frame, now.elapsed())))
695}
696
697#[derive(Clone)]
698struct BacktrackFrame {
699 context: ResolverContext,
700 remaining_deps: RemainingDeps,
701 remaining_candidates: RemainingCandidates,
702 parent: Summary,
703 dep: Dependency,
704 features: FeaturesSet,
705 conflicting_activations: ConflictMap,
706}
707
708/// A helper "iterator" used to extract candidates within a current `Context` of
709/// a dependency graph.
710///
711/// This struct doesn't literally implement the `Iterator` trait (requires a few
712/// more inputs) but in general acts like one. Each `RemainingCandidates` is
713/// created with a list of candidates to choose from. When attempting to iterate
714/// over the list of candidates only *valid* candidates are returned. Validity
715/// is defined within a `Context`.
716///
717/// Candidates passed to `new` may not be returned from `next` as they could be
718/// filtered out, and as they are filtered the causes will be added to `conflicting_prev_active`.
719#[derive(Clone)]
720struct RemainingCandidates {
721 remaining: RcVecIter<Summary>,
722 // This is an inlined peekable generator
723 has_another: Option<Summary>,
724}
725
726impl RemainingCandidates {
727 fn new(candidates: &Rc<Vec<Summary>>) -> RemainingCandidates {
728 RemainingCandidates {
729 remaining: RcVecIter::new(Rc::clone(candidates)),
730 has_another: None,
731 }
732 }
733
734 /// Attempts to find another candidate to check from this list.
735 ///
736 /// This method will attempt to move this iterator forward, returning a
737 /// candidate that's possible to activate. The `cx` argument is the current
738 /// context which determines validity for candidates returned, and the `dep`
739 /// is the dependency listing that we're activating for.
740 ///
741 /// If successful a `(Candidate, bool)` pair will be returned. The
742 /// `Candidate` is the candidate to attempt to activate, and the `bool` is
743 /// an indicator of whether there are remaining candidates to try of if
744 /// we've reached the end of iteration.
745 ///
746 /// If we've reached the end of the iterator here then `Err` will be
747 /// returned. The error will contain a map of package ID to conflict reason,
748 /// where each package ID caused a candidate to be filtered out from the
749 /// original list for the reason listed.
750 fn next(
751 &mut self,
752 conflicting_prev_active: &mut ConflictMap,
753 cx: &ResolverContext,
754 ) -> Option<(Summary, bool)> {
755 for b in self.remaining.iter() {
756 let b_id = b.package_id();
757
758 // The condition for being a valid candidate relies on
759 // semver. Cargo dictates that you can't duplicate multiple
760 // semver-compatible versions of a crate. For example we can't
761 // simultaneously activate `foo 1.0.2` and `foo 1.2.0`. We can,
762 // however, activate `1.0.2` and `2.0.0`.
763 //
764 // Here we throw out our candidate if it's *compatible*, yet not
765 // equal, to all previously activated versions.
766 if let Some((a, _)) = cx.activations.get(&b_id.as_activations_key()) {
767 if a != b {
768 conflicting_prev_active
769 .entry(a.package_id())
770 .or_insert(ConflictReason::Semver);
771 continue;
772 }
773 }
774
775 // Otherwise the `links` key in the manifest dictates that there's only one
776 // package in a dependency graph, globally, with that particular
777 // `links` key. If this candidate links to something that's already
778 // linked to by a different package then we've gotta skip this.
779 if let Some(link) = b.links() {
780 if let Some(&a) = cx.links.get(&link) {
781 if a != b_id {
782 conflicting_prev_active
783 .entry(a)
784 .or_insert_with(|| ConflictReason::Links(link));
785 continue;
786 }
787 }
788 }
789
790 // Well if we made it this far then we've got a valid dependency. We
791 // want this iterator to be inherently "peekable" so we don't
792 // necessarily return the item just yet. Instead we stash it away to
793 // get returned later, and if we replaced something then that was
794 // actually the candidate to try first so we return that.
795 if let Some(r) = self.has_another.replace(b.clone()) {
796 return Some((r, true));
797 }
798 }
799
800 // Alright we've entirely exhausted our list of candidates. If we've got
801 // something stashed away return that here (also indicating that there's
802 // nothing else).
803 self.has_another.take().map(|r| (r, false))
804 }
805}
806
807/// Attempts to find a new conflict that allows a `find_candidate` better then the input one.
808/// It will add the new conflict to the cache if one is found.
809fn generalize_conflicting(
810 cx: &ResolverContext,
811 registry: &mut RegistryQueryer<'_>,
812 past_conflicting_activations: &mut conflict_cache::ConflictCache,
813 parent: &Summary,
814 dep: &Dependency,
815 conflicting_activations: &ConflictMap,
816) -> Option<ConflictMap> {
817 // We need to determine the `ContextAge` that this `conflicting_activations` will jump to, and why.
818 let (backtrack_critical_age, backtrack_critical_id) = shortcircuit_max(
819 conflicting_activations
820 .keys()
821 .map(|&c| cx.is_active(c).map(|a| (a, c))),
822 )?;
823 let backtrack_critical_reason: ConflictReason =
824 conflicting_activations[&backtrack_critical_id].clone();
825
826 if cx
827 .parents
828 .is_path_from_to(&parent.package_id(), &backtrack_critical_id)
829 {
830 // We are a descendant of the trigger of the problem.
831 // The best generalization of this is to let things bubble up
832 // and let `backtrack_critical_id` figure this out.
833 return None;
834 }
835 // What parents does that critical activation have
836 for (critical_parent, critical_parents_deps) in
837 cx.parents.edges(&backtrack_critical_id).filter(|(p, _)| {
838 // it will only help backjump further if it is older then the critical_age
839 cx.is_active(**p).expect("parent not currently active!?") < backtrack_critical_age
840 })
841 {
842 for critical_parents_dep in critical_parents_deps.iter() {
843 // We only want `first_version.is_some()` for direct dependencies of workspace
844 // members which isn't the case here as this has a `parent`
845 let first_version = None;
846 // A dep is equivalent to one of the things it can resolve to.
847 // Thus, if all the things it can resolve to have already ben determined
848 // to be conflicting, then we can just say that we conflict with the parent.
849 if let Some(others) = registry
850 .query(critical_parents_dep, first_version)
851 .expect("an already used dep now error!?")
852 .expect("an already used dep now pending!?")
853 .iter()
854 .rev() // the last one to be tried is the least likely to be in the cache, so start with that.
855 .map(|other| {
856 past_conflicting_activations
857 .find(
858 dep,
859 &|id| {
860 if id == other.package_id() {
861 // we are imagining that we used other instead
862 Some(backtrack_critical_age)
863 } else {
864 cx.is_active(id)
865 }
866 },
867 Some(other.package_id()),
868 // we only care about things that are newer then critical_age
869 backtrack_critical_age,
870 )
871 .map(|con| (other.package_id(), con))
872 })
873 .collect::<Option<Vec<(PackageId, &ConflictMap)>>>()
874 {
875 let mut con = conflicting_activations.clone();
876 // It is always valid to combine previously inserted conflicts.
877 // A, B are both known bad states each that can never be activated.
878 // A + B is redundant but can't be activated, as if
879 // A + B is active then A is active and we know that is not ok.
880 for (_, other) in &others {
881 con.extend(other.iter().map(|(&id, re)| (id, re.clone())));
882 }
883 // Now that we have this combined conflict, we can do a substitution:
884 // A dep is equivalent to one of the things it can resolve to.
885 // So we can remove all the things that it resolves to and replace with the parent.
886 for (other_id, _) in &others {
887 con.remove(other_id);
888 }
889 con.insert(*critical_parent, backtrack_critical_reason);
890
891 if cfg!(debug_assertions) {
892 // the entire point is to find an older conflict, so let's make sure we did
893 let new_age = con
894 .keys()
895 .map(|&c| cx.is_active(c).expect("not currently active!?"))
896 .max()
897 .unwrap();
898 assert!(
899 new_age < backtrack_critical_age,
900 "new_age {} < backtrack_critical_age {}",
901 new_age,
902 backtrack_critical_age
903 );
904 }
905 past_conflicting_activations.insert(dep, &con);
906 return Some(con);
907 }
908 }
909 }
910 None
911}
912
913/// Returns Some of the largest item in the iterator.
914/// Returns None if any of the items are None or the iterator is empty.
915fn shortcircuit_max<I: Ord>(iter: impl Iterator<Item = Option<I>>) -> Option<I> {
916 let mut out = None;
917 for i in iter {
918 if i.is_none() {
919 return None;
920 }
921 out = std::cmp::max(out, i);
922 }
923 out
924}
925
926/// Looks through the states in `backtrack_stack` for dependencies with
927/// remaining candidates. For each one, also checks if rolling back
928/// could change the outcome of the failed resolution that caused backtracking
929/// in the first place. Namely, if we've backtracked past the parent of the
930/// failed dep, or any of the packages flagged as giving us trouble in
931/// `conflicting_activations`.
932///
933/// Read <https://github.com/rust-lang/cargo/pull/4834>
934/// For several more detailed explanations of the logic here.
935fn find_candidate(
936 cx: &ResolverContext,
937 backtrack_stack: &mut Vec<BacktrackFrame>,
938 parent: &Summary,
939 backtracked: bool,
940 conflicting_activations: &ConflictMap,
941) -> Option<(Summary, bool, BacktrackFrame)> {
942 // When we're calling this method we know that `parent` failed to
943 // activate. That means that some dependency failed to get resolved for
944 // whatever reason. Normally, that means that all of those reasons
945 // (plus maybe some extras) are listed in `conflicting_activations`.
946 //
947 // The abnormal situations are things that do not put all of the reasons in `conflicting_activations`:
948 // If we backtracked we do not know how our `conflicting_activations` related to
949 // the cause of that backtrack, so we do not update it.
950 let age = if !backtracked {
951 // we don't have abnormal situations. So we can ask `cx` for how far back we need to go.
952 // If the `conflicting_activations` does not apply to `cx`,
953 // we will just fall back to laboriously trying all possibilities witch
954 // will give us the correct answer.
955 cx.is_conflicting(Some(parent.package_id()), conflicting_activations)
956 } else {
957 None
958 };
959 let mut new_frame = None;
960 if let Some(age) = age {
961 while let Some(frame) = backtrack_stack.pop() {
962 // If all members of `conflicting_activations` are still
963 // active in this back up we know that we're guaranteed to not actually
964 // make any progress. As a result if we hit this condition we can
965 // completely skip this backtrack frame and move on to the next.
966
967 // Above we use `cx` to determine if this is going to be conflicting.
968 // But lets just double check if the `pop`ed frame agrees.
969 let frame_too_new = frame.context.age >= age;
970 debug_assert!(
971 frame
972 .context
973 .is_conflicting(Some(parent.package_id()), conflicting_activations)
974 == frame_too_new.then_some(age)
975 );
976
977 if !frame_too_new {
978 new_frame = Some(frame);
979 break;
980 }
981 trace!(
982 "{} = \"{}\" skip as not solving {}: {:?}",
983 frame.dep.package_name(),
984 frame.dep.version_req(),
985 parent.package_id(),
986 conflicting_activations
987 );
988 }
989 } else {
990 // If we're here then we are in abnormal situations and need to just go one frame at a time.
991 new_frame = backtrack_stack.pop();
992 }
993
994 new_frame.map(|mut frame| {
995 let (candidate, has_another) = frame
996 .remaining_candidates
997 .next(&mut frame.conflicting_activations, &frame.context)
998 .expect("why did we save a frame that has no next?");
999 (candidate, has_another, frame)
1000 })
1001}
1002
1003fn check_cycles(resolve: &Resolve) -> CargoResult<()> {
1004 // Perform a simple cycle check by visiting all nodes.
1005 // We visit each node at most once and we keep
1006 // track of the path through the graph as we walk it. If we walk onto the
1007 // same node twice that's a cycle.
1008 let mut checked = HashSet::with_capacity(resolve.len());
1009 let mut path = Vec::with_capacity(4);
1010 let mut visited = HashSet::with_capacity(4);
1011 for pkg in resolve.iter() {
1012 if !checked.contains(&pkg) {
1013 visit(&resolve, pkg, &mut visited, &mut path, &mut checked)?
1014 }
1015 }
1016 return Ok(());
1017
1018 fn visit(
1019 resolve: &Resolve,
1020 id: PackageId,
1021 visited: &mut HashSet<PackageId>,
1022 path: &mut Vec<PackageId>,
1023 checked: &mut HashSet<PackageId>,
1024 ) -> CargoResult<()> {
1025 if !visited.insert(id) {
1026 // We found a cycle and need to construct an error. Performance is no longer top priority.
1027 let iter = path.iter().rev().scan(id, |child, parent| {
1028 let dep = resolve.transitive_deps_not_replaced(*parent).find_map(
1029 |(dep_id, transitive_dep)| {
1030 (*child == dep_id || Some(*child) == resolve.replacement(dep_id))
1031 .then_some(transitive_dep)
1032 },
1033 );
1034 *child = *parent;
1035 Some((parent, dep))
1036 });
1037 let iter = std::iter::once((&id, None)).chain(iter);
1038 let describe_path = errors::describe_path(iter);
1039 anyhow::bail!(
1040 "cyclic package dependency: package `{id}` depends on itself. Cycle:\n{describe_path}"
1041 );
1042 }
1043
1044 if checked.insert(id) {
1045 path.push(id);
1046 for (dep_id, _transitive_dep) in resolve.transitive_deps_not_replaced(id) {
1047 visit(resolve, dep_id, visited, path, checked)?;
1048 if let Some(replace_id) = resolve.replacement(dep_id) {
1049 visit(resolve, replace_id, visited, path, checked)?;
1050 }
1051 }
1052 path.pop();
1053 }
1054
1055 visited.remove(&id);
1056 Ok(())
1057 }
1058}
1059
1060/// Checks that packages are unique when written to lock file.
1061///
1062/// When writing package ID's to lock file, we apply lossy encoding. In
1063/// particular, we don't store paths of path dependencies. That means that
1064/// *different* packages may collide in the lock file, hence this check.
1065fn check_duplicate_pkgs_in_lockfile(resolve: &Resolve) -> CargoResult<()> {
1066 let mut unique_pkg_ids = HashMap::new();
1067 let state = encode::EncodeState::new(resolve);
1068 for pkg_id in resolve.iter() {
1069 let encodable_pkd_id = encode::encodable_package_id(pkg_id, &state, resolve.version());
1070 if let Some(prev_pkg_id) = unique_pkg_ids.insert(encodable_pkd_id, pkg_id) {
1071 anyhow::bail!(
1072 "package collision in the lockfile: packages {} and {} are different, \
1073 but only one can be written to lockfile unambiguously",
1074 prev_pkg_id,
1075 pkg_id
1076 )
1077 }
1078 }
1079 Ok(())
1080}