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(&registry);
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}