#
cargo/core/resolver/
conflict_cache.rs

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    61
    62
    63
    64
    65
    66
    67
    68
    69
    70
    71
    72
    73
    74
    75
    76
    77
    78
    79
    80
    81
    82
    83
    84
    85
    86
    87
    88
    89
    90
    91
    92
    93
    94
    95
    96
    97
    98
    99
    100
    101
    102
    103
    104
    105
    106
    107
    108
    109
    110
    111
    112
    113
    114
    115
    116
    117
    118
    119
    120
    121
    122
    123
    124
    125
    126
    127
    128
    129
    130
    131
    132
    133
    134
    135
    136
    137
    138
    139
    140
    141
    142
    143
    144
    145
    146
    147
    148
    149
    150
    151
    152
    153
    154
    155
    156
    157
    158
    159
    160
    161
    162
    163
    164
    165
    166
    167
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218

    use std::collections::{BTreeMap, HashMap};

    use rustc_hash::{FxHashMap, FxHashSet};
    use tracing::trace;

    use super::types::ConflictMap;
    use crate::core::resolver::ResolverContext;
    use crate::core::{Dependency, PackageId};

    /// This is a trie for storing a large number of sets designed to
    /// efficiently see if any of the stored sets are a subset of a search set.
    enum ConflictStoreTrie {
        /// One of the stored sets.
        Leaf(ConflictMap),
        /// A map from an element to a subtrie where
        /// all the sets in the subtrie contains that element.
        Node(BTreeMap<PackageId, ConflictStoreTrie>),
    }

    impl ConflictStoreTrie {
        /// Finds any known set of conflicts, if any,
        /// where all elements return some from `is_active` and contain `PackageId` specified.
        /// If more than one are activated, then it will return
        /// one that will allow for the most jump-back.
        fn find(
            &self,
            is_active: &impl Fn(PackageId) -> Option<usize>,
            must_contain: Option<PackageId>,
            mut max_age: usize,
        ) -> Option<(&ConflictMap, usize)> {
            match self {
                ConflictStoreTrie::Leaf(c) => {
                    if must_contain.is_none() {
                        Some((c, 0))
                    } else {
                        // We did not find `must_contain`, so we need to keep looking.
                        None
                    }
                }
                ConflictStoreTrie::Node(m) => {
                    let mut out = None;
                    for (&pid, store) in must_contain
                        .map(|f| m.range(..=f))
                        .unwrap_or_else(|| m.range(..))
                    {
                        // If the key is active, then we need to check all of the corresponding subtrie.
                        if let Some(age_this) = is_active(pid) {
                            if age_this >= max_age && must_contain != Some(pid) {
                                // not worth looking at, it is to old.
                                continue;
                            }
                            if let Some((o, age_o)) =
                                store.find(is_active, must_contain.filter(|&f| f != pid), max_age)
                            {
                                let age = if must_contain == Some(pid) {
                                    // all the results will include `must_contain`
                                    // so the age of must_contain is not relevant to find the best result.
                                    age_o
                                } else {
                                    std::cmp::max(age_this, age_o)
                                };
                                if max_age > age {
                                    // we found one that can jump-back further so replace the out.
                                    out = Some((o, age));
                                    // and don't look at anything older
                                    max_age = age
                                }
                            }
                        }
                        // Else, if it is not active then there is no way any of the corresponding
                        // subtrie will be conflicting.
                    }
                    out
                }
            }
        }

        fn insert(&mut self, mut iter: impl Iterator<Item = PackageId>, con: ConflictMap) {
            if let Some(pid) = iter.next() {
                if let ConflictStoreTrie::Node(p) = self {
                    p.entry(pid)
                        .or_insert_with(|| ConflictStoreTrie::Node(BTreeMap::new()))
                        .insert(iter, con);
                }
            // Else, we already have a subset of this in the `ConflictStore`.
            } else {
                // We are at the end of the set we are adding, there are three cases for what to do
                // next:
                // 1. `self` is an empty dummy Node inserted by `or_insert_with`
                //      in witch case we should replace it with `Leaf(con)`.
                // 2. `self` is a `Node` because we previously inserted a superset of
                //      the thing we are working on (I don't know if this happens in practice)
                //      but the subset that we are working on will
                //      always match any time the larger set would have
                //      in witch case we can replace it with `Leaf(con)`.
                // 3. `self` is a `Leaf` that is in the same spot in the structure as
                //      the thing we are working on. So it is equivalent.
                //      We can replace it with `Leaf(con)`.
                if cfg!(debug_assertions) {
                    if let ConflictStoreTrie::Leaf(c) = self {
                        let a: Vec<_> = con.keys().collect();
                        let b: Vec<_> = c.keys().collect();
                        assert_eq!(a, b);
                    }
                }
                *self = ConflictStoreTrie::Leaf(con)
            }
        }
    }

    pub(super) struct ConflictCache {
        // `con_from_dep` is a cache of the reasons for each time we
        // backtrack. For example after several backtracks we may have:
        //
        //  con_from_dep[`foo = "^1.0.2"`] = map!{
        //      `foo=1.0.1`: map!{`foo=1.0.1`: Semver},
        //      `foo=1.0.0`: map!{`foo=1.0.0`: Semver},
        //  };
        //
        // This can be read as "we cannot find a candidate for dep `foo = "^1.0.2"`
        // if either `foo=1.0.1` OR `foo=1.0.0` are activated".
        //
        // Another example after several backtracks we may have:
        //
        //  con_from_dep[`foo = ">=0.8.2, <=0.9.3"`] = map!{
        //      `foo=0.8.1`: map!{
        //          `foo=0.9.4`: map!{`foo=0.8.1`: Semver, `foo=0.9.4`: Semver},
        //      }
        //  };
        //
        // This can be read as "we cannot find a candidate for dep `foo = ">=0.8.2,
        // <=0.9.3"` if both `foo=0.8.1` AND `foo=0.9.4` are activated".
        //
        // This is used to make sure we don't queue work we know will fail. See the
        // discussion in https://github.com/rust-lang/cargo/pull/5168 for why this
        // is so important. The nested HashMaps act as a kind of btree, that lets us
        // look up which entries are still active without
        // linearly scanning through the full list.
        //
        // Also, as a final note, this map is **not** ever removed from. This remains
        // as a global cache which we never delete from. Any entry in this map is
        // unconditionally true regardless of our resolution history of how we got
        // here.
        con_from_dep: FxHashMap<Dependency, ConflictStoreTrie>,
        // `dep_from_pid` is an inverse-index of `con_from_dep`.
        // For every `PackageId` this lists the `Dependency`s that mention it in `dep_from_pid`.
        dep_from_pid: FxHashMap<PackageId, FxHashSet<Dependency>>,
    }

    impl ConflictCache {
        pub fn new() -> ConflictCache {
            ConflictCache {
                con_from_dep: HashMap::default(),
                dep_from_pid: HashMap::default(),
            }
        }
        pub fn find(
            &self,
            dep: &Dependency,
            is_active: &impl Fn(PackageId) -> Option<usize>,
            must_contain: Option<PackageId>,
            max_age: usize,
        ) -> Option<&ConflictMap> {
            self.con_from_dep
                .get(dep)?
                .find(is_active, must_contain, max_age)
                .map(|(c, _)| c)
        }
        /// Finds any known set of conflicts, if any,
        /// which are activated in `cx` and contain `PackageId` specified.
        /// If more than one are activated, then it will return
        /// one that will allow for the most jump-back.
        pub fn find_conflicting(
            &self,
            cx: &ResolverContext,
            dep: &Dependency,
            must_contain: Option<PackageId>,
        ) -> Option<&ConflictMap> {
            let out = self.find(dep, &|id| cx.is_active(id), must_contain, usize::MAX);
            if cfg!(debug_assertions) {
                if let Some(c) = &out {
                    assert!(cx.is_conflicting(None, c).is_some());
                    if let Some(f) = must_contain {
                        assert!(c.contains_key(&f));
                    }
                }
            }
            out
        }
        pub fn conflicting(&self, cx: &ResolverContext, dep: &Dependency) -> Option<&ConflictMap> {
            self.find_conflicting(cx, dep, None)
        }

        /// Adds to the cache a conflict of the form:
        /// `dep` is known to be unresolvable if
        /// all the `PackageId` entries are activated.
        pub fn insert(&mut self, dep: &Dependency, con: &ConflictMap) {
            self.con_from_dep
                .entry(dep.clone())
                .or_insert_with(|| ConflictStoreTrie::Node(BTreeMap::new()))
                .insert(con.keys().cloned(), con.clone());

            trace!(
                "{} = \"{}\" adding a skip {:?}",
                dep.package_name(),
                dep.version_req(),
                con
            );

            for c in con.keys() {
                self.dep_from_pid.entry(*c).or_default().insert(dep.clone());
            }
        }

        pub fn dependencies_conflicting_with(&self, pid: PackageId) -> Option<&FxHashSet<Dependency>> {
            self.dep_from_pid.get(&pid)
        }
    }