#
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}