#
cargo/core/resolver/
types.rs

    1use super::features::{CliFeatures, RequestedFeatures};
    2use crate::core::{Dependency, PackageId, SourceId, Summary};
    3use crate::util::errors::CargoResult;
    4use crate::util::interning::InternedString;
    5use crate::util::GlobalContext;
    6use std::cmp::Ordering;
    7use std::collections::{BTreeMap, BTreeSet};
    8use std::num::NonZeroU64;
    9use std::rc::Rc;
    10use std::time::{Duration, Instant};
    11
    12pub struct ResolverProgress {
    13    ticks: u16,
    14    start: Instant,
    15    time_to_print: Duration,
    16    printed: bool,
    17    deps_time: Duration,
    18    /// Provides an escape hatch for machine with slow CPU for debugging and
    19    /// testing Cargo itself.
    20    /// See [rust-lang/cargo#6596](https://github.com/rust-lang/cargo/pull/6596) for more.
    21    #[cfg(debug_assertions)]
    22    slow_cpu_multiplier: u64,
    23}
    24
    25impl ResolverProgress {
    26    pub fn new() -> ResolverProgress {
    27        ResolverProgress {
    28            ticks: 0,
    29            start: Instant::now(),
    30            time_to_print: Duration::from_millis(500),
    31            printed: false,
    32            deps_time: Duration::new(0, 0),
    33            // Some CI setups are much slower then the equipment used by Cargo itself.
    34            // Architectures that do not have a modern processor, hardware emulation, etc.
    35            // In the test code we have `slow_cpu_multiplier`, but that is not accessible here.
    36            #[cfg(debug_assertions)]
    37            // ALLOWED: For testing cargo itself only. However, it was communicated as an public
    38            // interface to other developers, so keep it as-is, shouldn't add `__CARGO` prefix.
    39            #[allow(clippy::disallowed_methods)]
    40            slow_cpu_multiplier: std::env::var("CARGO_TEST_SLOW_CPU_MULTIPLIER")
    41                .ok()
    42                .and_then(|m| m.parse().ok())
    43                .unwrap_or(1),
    44        }
    45    }
    46    pub fn shell_status(&mut self, gctx: Option<&GlobalContext>) -> CargoResult<()> {
    47        // If we spend a lot of time here (we shouldn't in most cases) then give
    48        // a bit of a visual indicator as to what we're doing. Only enable this
    49        // when stderr is a tty (a human is likely to be watching) to ensure we
    50        // get deterministic output otherwise when observed by tools.
    51        //
    52        // Also note that we hit this loop a lot, so it's fairly performance
    53        // sensitive. As a result try to defer a possibly expensive operation
    54        // like `Instant::now` by only checking every N iterations of this loop
    55        // to amortize the cost of the current time lookup.
    56        self.ticks += 1;
    57        if let Some(config) = gctx {
    58            if config.shell().is_err_tty()
    59                && !self.printed
    60                && self.ticks % 1000 == 0
    61                && self.start.elapsed() - self.deps_time > self.time_to_print
    62            {
    63                self.printed = true;
    64                config.shell().status("Resolving", "dependency graph...")?;
    65            }
    66        }
    67        #[cfg(debug_assertions)]
    68        {
    69            // The largest test in our suite takes less then 5000 ticks
    70            // with all the algorithm improvements.
    71            // If any of them are removed then it takes more than I am willing to measure.
    72            // So lets fail the test fast if we have been running for too long.
    73            assert!(
    74                self.ticks < 50_000,
    75                "got to 50_000 ticks in {:?}",
    76                self.start.elapsed()
    77            );
    78            // The largest test in our suite takes less then 30 sec
    79            // with all the improvements to how fast a tick can go.
    80            // If any of them are removed then it takes more than I am willing to measure.
    81            // So lets fail the test fast if we have been running for too long.
    82            if self.ticks % 1000 == 0 {
    83                assert!(
    84                    self.start.elapsed() - self.deps_time
    85                        < Duration::from_secs(self.slow_cpu_multiplier * 90)
    86                );
    87            }
    88        }
    89        Ok(())
    90    }
    91    pub fn elapsed(&mut self, dur: Duration) {
    92        self.deps_time += dur;
    93    }
    94}
    95
    96/// The preferred way to store the set of activated features for a package.
    97/// This is sorted so that it impls Hash, and owns its contents,
    98/// needed so it can be part of the key for caching in the `DepsCache`.
    99/// It is also cloned often as part of `Context`, hence the `RC`.
    100/// `im-rs::OrdSet` was slower of small sets like this,
    101/// but this can change with improvements to std, im, or llvm.
    102/// Using a consistent type for this allows us to use the highly
    103/// optimized comparison operators like `is_subset` at the interfaces.
    104pub type FeaturesSet = Rc<BTreeSet<InternedString>>;
    105
    106/// Resolver behavior, used to opt-in to new behavior that is
    107/// backwards-incompatible via the `resolver` field in the manifest.
    108#[derive(Copy, Clone, Debug, Eq, PartialEq, Hash)]
    109pub enum ResolveBehavior {
    110    /// V1 is the original resolver behavior.
    111    V1,
    112    /// V2 adds the new feature resolver.
    113    V2,
    114    /// V3 changes version preferences
    115    V3,
    116}
    117
    118impl ResolveBehavior {
    119    pub fn from_manifest(resolver: &str) -> CargoResult<ResolveBehavior> {
    120        match resolver {
    121            "1" => Ok(ResolveBehavior::V1),
    122            "2" => Ok(ResolveBehavior::V2),
    123            "3" => Ok(ResolveBehavior::V3),
    124            s => anyhow::bail!(
    125                "`resolver` setting `{}` is not valid, valid options are \"1\", \"2\" or \"3\"",
    126                s
    127            ),
    128        }
    129    }
    130
    131    pub fn to_manifest(&self) -> String {
    132        match self {
    133            ResolveBehavior::V1 => "1",
    134            ResolveBehavior::V2 => "2",
    135            ResolveBehavior::V3 => "3",
    136        }
    137        .to_owned()
    138    }
    139}
    140
    141/// Options for how the resolve should work.
    142#[derive(Clone, Debug, Eq, PartialEq, Hash)]
    143pub struct ResolveOpts {
    144    /// Whether or not dev-dependencies should be included.
    145    ///
    146    /// This may be set to `false` by things like `cargo install` or `-Z avoid-dev-deps`.
    147    /// It also gets set to `false` when activating dependencies in the resolver.
    148    pub dev_deps: bool,
    149    /// Set of features requested on the command-line.
    150    pub features: RequestedFeatures,
    151}
    152
    153impl ResolveOpts {
    154    /// Creates a `ResolveOpts` that resolves everything.
    155    pub fn everything() -> ResolveOpts {
    156        ResolveOpts {
    157            dev_deps: true,
    158            features: RequestedFeatures::CliFeatures(CliFeatures::new_all(true)),
    159        }
    160    }
    161
    162    pub fn new(dev_deps: bool, features: RequestedFeatures) -> ResolveOpts {
    163        ResolveOpts { dev_deps, features }
    164    }
    165}
    166
    167/// A key that when stord in a hash map ensures that there is only one
    168/// semver compatible version of each crate.
    169/// Find the activated version of a crate based on the name, source, and semver compatibility.
    170#[derive(Clone, PartialEq, Eq, Debug, Ord, PartialOrd)]
    171pub struct ActivationsKey(InternedString, SemverCompatibility, SourceId);
    172
    173impl ActivationsKey {
    174    pub fn new(
    175        name: InternedString,
    176        ver: SemverCompatibility,
    177        source_id: SourceId,
    178    ) -> ActivationsKey {
    179        ActivationsKey(name, ver, source_id)
    180    }
    181}
    182
    183impl std::hash::Hash for ActivationsKey {
    184    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
    185        self.0.hash(state);
    186        self.1.hash(state);
    187        // self.2.hash(state); // Packages that only differ by SourceId are rare enough to not be worth hashing
    188    }
    189}
    190
    191/// A type that represents when cargo treats two Versions as compatible.
    192/// Versions `a` and `b` are compatible if their left-most nonzero digit is the
    193/// same.
    194#[derive(Clone, Copy, Eq, PartialEq, Hash, Debug, PartialOrd, Ord)]
    195pub enum SemverCompatibility {
    196    Major(NonZeroU64),
    197    Minor(NonZeroU64),
    198    Patch(u64),
    199}
    200
    201impl From<&semver::Version> for SemverCompatibility {
    202    fn from(ver: &semver::Version) -> Self {
    203        if let Some(m) = NonZeroU64::new(ver.major) {
    204            return SemverCompatibility::Major(m);
    205        }
    206        if let Some(m) = NonZeroU64::new(ver.minor) {
    207            return SemverCompatibility::Minor(m);
    208        }
    209        SemverCompatibility::Patch(ver.patch)
    210    }
    211}
    212
    213impl PackageId {
    214    pub fn as_activations_key(self) -> ActivationsKey {
    215        ActivationsKey(self.name(), self.version().into(), self.source_id())
    216    }
    217}
    218
    219#[derive(Clone)]
    220pub struct DepsFrame {
    221    pub parent: Summary,
    222    pub just_for_error_messages: bool,
    223    pub remaining_siblings: RcVecIter<DepInfo>,
    224}
    225
    226impl DepsFrame {
    227    /// Returns the least number of candidates that any of this frame's siblings
    228    /// has.
    229    ///
    230    /// The `remaining_siblings` array is already sorted with the smallest
    231    /// number of candidates at the front, so we just return the number of
    232    /// candidates in that entry.
    233    fn min_candidates(&self) -> usize {
    234        self.remaining_siblings
    235            .peek()
    236            .map(|(_, candidates, _)| candidates.len())
    237            .unwrap_or(0)
    238    }
    239
    240    pub fn flatten(&self) -> impl Iterator<Item = (PackageId, &Dependency)> + '_ {
    241        self.remaining_siblings
    242            .remaining()
    243            .map(move |(d, _, _)| (self.parent.package_id(), d))
    244    }
    245}
    246
    247impl PartialEq for DepsFrame {
    248    fn eq(&self, other: &DepsFrame) -> bool {
    249        self.just_for_error_messages == other.just_for_error_messages
    250            && self.min_candidates() == other.min_candidates()
    251    }
    252}
    253
    254impl Eq for DepsFrame {}
    255
    256impl PartialOrd for DepsFrame {
    257    fn partial_cmp(&self, other: &DepsFrame) -> Option<Ordering> {
    258        Some(self.cmp(other))
    259    }
    260}
    261
    262impl Ord for DepsFrame {
    263    fn cmp(&self, other: &DepsFrame) -> Ordering {
    264        self.just_for_error_messages
    265            .cmp(&other.just_for_error_messages)
    266            .reverse()
    267            .then_with(|| self.min_candidates().cmp(&other.min_candidates()))
    268    }
    269}
    270
    271/// Note that an `OrdSet` is used for the remaining dependencies that need
    272/// activation. This set is sorted by how many candidates each dependency has.
    273///
    274/// This helps us get through super constrained portions of the dependency
    275/// graph quickly and hopefully lock down what later larger dependencies can
    276/// use (those with more candidates).
    277#[derive(Clone)]
    278pub struct RemainingDeps {
    279    /// a monotonic counter, increased for each new insertion.
    280    time: u32,
    281    /// the data is augmented by the insertion time.
    282    /// This insures that no two items will cmp eq.
    283    /// Forcing the `OrdSet` into a multi set.
    284    data: im_rc::OrdSet<(DepsFrame, u32)>,
    285}
    286
    287impl RemainingDeps {
    288    pub fn new() -> RemainingDeps {
    289        RemainingDeps {
    290            time: 0,
    291            data: im_rc::OrdSet::new(),
    292        }
    293    }
    294    pub fn push(&mut self, x: DepsFrame) {
    295        let insertion_time = self.time;
    296        self.data.insert((x, insertion_time));
    297        self.time += 1;
    298    }
    299    pub fn pop_most_constrained(&mut self) -> Option<(bool, (Summary, DepInfo))> {
    300        while let Some((mut deps_frame, insertion_time)) = self.data.remove_min() {
    301            let just_here_for_the_error_messages = deps_frame.just_for_error_messages;
    302
    303            // Figure out what our next dependency to activate is, and if nothing is
    304            // listed then we're entirely done with this frame (yay!) and we can
    305            // move on to the next frame.
    306            let sibling = deps_frame.remaining_siblings.iter().next().cloned();
    307            if let Some(sibling) = sibling {
    308                let parent = Summary::clone(&deps_frame.parent);
    309                self.data.insert((deps_frame, insertion_time));
    310                return Some((just_here_for_the_error_messages, (parent, sibling)));
    311            }
    312        }
    313        None
    314    }
    315    pub fn iter(&mut self) -> impl Iterator<Item = (PackageId, &Dependency)> + '_ {
    316        self.data.iter().flat_map(|(other, _)| other.flatten())
    317    }
    318}
    319
    320/// Information about the dependencies for a crate, a tuple of:
    321///
    322/// (dependency info, candidates, features activated)
    323pub type DepInfo = (Dependency, Rc<Vec<Summary>>, FeaturesSet);
    324
    325/// All possible reasons that a package might fail to activate.
    326///
    327/// We maintain a list of conflicts for error reporting as well as backtracking
    328/// purposes. Each reason here is why candidates may be rejected or why we may
    329/// fail to resolve a dependency.
    330#[derive(Debug, Clone, PartialOrd, Ord, PartialEq, Eq)]
    331pub enum ConflictReason {
    332    /// There was a semver conflict, for example we tried to activate a package
    333    /// 1.0.2 but 1.1.0 was already activated (aka a compatible semver version
    334    /// is already activated)
    335    Semver,
    336
    337    /// The `links` key is being violated. For example one crate in the
    338    /// dependency graph has `links = "foo"` but this crate also had that, and
    339    /// we're only allowed one per dependency graph.
    340    Links(InternedString),
    341
    342    /// A dependency listed a feature that wasn't actually available on the
    343    /// candidate. For example we tried to activate feature `foo` but the
    344    /// candidate we're activating didn't actually have the feature `foo`.
    345    MissingFeature(InternedString),
    346
    347    /// A dependency listed a feature that ended up being a required dependency.
    348    /// For example we tried to activate feature `foo` but the
    349    /// candidate we're activating didn't actually have the feature `foo`
    350    /// it had a dependency `foo` instead.
    351    RequiredDependencyAsFeature(InternedString),
    352
    353    /// A dependency listed a feature for an optional dependency, but that
    354    /// optional dependency is "hidden" using namespaced `dep:` syntax.
    355    NonImplicitDependencyAsFeature(InternedString),
    356}
    357
    358impl ConflictReason {
    359    pub fn is_links(&self) -> bool {
    360        matches!(self, ConflictReason::Links(_))
    361    }
    362
    363    pub fn is_missing_feature(&self) -> bool {
    364        matches!(self, ConflictReason::MissingFeature(_))
    365    }
    366
    367    pub fn is_required_dependency_as_features(&self) -> bool {
    368        matches!(self, ConflictReason::RequiredDependencyAsFeature(_))
    369    }
    370}
    371
    372/// A list of packages that have gotten in the way of resolving a dependency.
    373/// If resolving a dependency fails then this represents an incompatibility,
    374/// that dependency will never be resolve while all of these packages are active.
    375/// This is useless if the packages can't be simultaneously activated for other reasons.
    376pub type ConflictMap = BTreeMap<PackageId, ConflictReason>;
    377
    378pub struct RcVecIter<T> {
    379    vec: Rc<Vec<T>>,
    380    offset: usize,
    381}
    382
    383impl<T> RcVecIter<T> {
    384    pub fn new(vec: Rc<Vec<T>>) -> RcVecIter<T> {
    385        RcVecIter { vec, offset: 0 }
    386    }
    387
    388    pub fn peek(&self) -> Option<&T> {
    389        self.vec.get(self.offset)
    390    }
    391
    392    pub fn remaining(&self) -> impl Iterator<Item = &T> + '_ {
    393        self.vec.get(self.offset..).into_iter().flatten()
    394    }
    395
    396    pub fn iter(&mut self) -> impl Iterator<Item = &T> + '_ {
    397        let iter = self.vec.get(self.offset..).into_iter().flatten();
    398        // This call to `ìnspect()` is used to increment `self.offset` when iterating the inner `Vec`,
    399        // while keeping the `ExactSizeIterator` property.
    400        iter.inspect(|_| self.offset += 1)
    401    }
    402}
    403
    404// Not derived to avoid `T: Clone`
    405impl<T> Clone for RcVecIter<T> {
    406    fn clone(&self) -> RcVecIter<T> {
    407        RcVecIter {
    408            vec: self.vec.clone(),
    409            offset: self.offset,
    410        }
    411    }
    412}