#
cargo/core/resolver/
conflict_cache.rs

    1use std::collections::{BTreeMap, HashMap};
    2
    3use rustc_hash::{FxHashMap, FxHashSet};
    4use tracing::trace;
    5
    6use super::types::ConflictMap;
    7use crate::core::resolver::ResolverContext;
    8use crate::core::{Dependency, PackageId};
    9
    10/// This is a trie for storing a large number of sets designed to
    11/// efficiently see if any of the stored sets are a subset of a search set.
    12enum ConflictStoreTrie {
    13    /// One of the stored sets.
    14    Leaf(ConflictMap),
    15    /// A map from an element to a subtrie where
    16    /// all the sets in the subtrie contains that element.
    17    Node(BTreeMap<PackageId, ConflictStoreTrie>),
    18}
    19
    20impl ConflictStoreTrie {
    21    /// Finds any known set of conflicts, if any,
    22    /// where all elements return some from `is_active` and contain `PackageId` specified.
    23    /// If more than one are activated, then it will return
    24    /// one that will allow for the most jump-back.
    25    fn find(
    26        &self,
    27        is_active: &impl Fn(PackageId) -> Option<usize>,
    28        must_contain: Option<PackageId>,
    29        mut max_age: usize,
    30    ) -> Option<(&ConflictMap, usize)> {
    31        match self {
    32            ConflictStoreTrie::Leaf(c) => {
    33                if must_contain.is_none() {
    34                    Some((c, 0))
    35                } else {
    36                    // We did not find `must_contain`, so we need to keep looking.
    37                    None
    38                }
    39            }
    40            ConflictStoreTrie::Node(m) => {
    41                let mut out = None;
    42                for (&pid, store) in must_contain
    43                    .map(|f| m.range(..=f))
    44                    .unwrap_or_else(|| m.range(..))
    45                {
    46                    // If the key is active, then we need to check all of the corresponding subtrie.
    47                    if let Some(age_this) = is_active(pid) {
    48                        if age_this >= max_age && must_contain != Some(pid) {
    49                            // not worth looking at, it is to old.
    50                            continue;
    51                        }
    52                        if let Some((o, age_o)) =
    53                            store.find(is_active, must_contain.filter(|&f| f != pid), max_age)
    54                        {
    55                            let age = if must_contain == Some(pid) {
    56                                // all the results will include `must_contain`
    57                                // so the age of must_contain is not relevant to find the best result.
    58                                age_o
    59                            } else {
    60                                std::cmp::max(age_this, age_o)
    61                            };
    62                            if max_age > age {
    63                                // we found one that can jump-back further so replace the out.
    64                                out = Some((o, age));
    65                                // and don't look at anything older
    66                                max_age = age
    67                            }
    68                        }
    69                    }
    70                    // Else, if it is not active then there is no way any of the corresponding
    71                    // subtrie will be conflicting.
    72                }
    73                out
    74            }
    75        }
    76    }
    77
    78    fn insert(&mut self, mut iter: impl Iterator<Item = PackageId>, con: ConflictMap) {
    79        if let Some(pid) = iter.next() {
    80            if let ConflictStoreTrie::Node(p) = self {
    81                p.entry(pid)
    82                    .or_insert_with(|| ConflictStoreTrie::Node(BTreeMap::new()))
    83                    .insert(iter, con);
    84            }
    85        // Else, we already have a subset of this in the `ConflictStore`.
    86        } else {
    87            // We are at the end of the set we are adding, there are three cases for what to do
    88            // next:
    89            // 1. `self` is an empty dummy Node inserted by `or_insert_with`
    90            //      in witch case we should replace it with `Leaf(con)`.
    91            // 2. `self` is a `Node` because we previously inserted a superset of
    92            //      the thing we are working on (I don't know if this happens in practice)
    93            //      but the subset that we are working on will
    94            //      always match any time the larger set would have
    95            //      in witch case we can replace it with `Leaf(con)`.
    96            // 3. `self` is a `Leaf` that is in the same spot in the structure as
    97            //      the thing we are working on. So it is equivalent.
    98            //      We can replace it with `Leaf(con)`.
    99            if cfg!(debug_assertions) {
    100                if let ConflictStoreTrie::Leaf(c) = self {
    101                    let a: Vec<_> = con.keys().collect();
    102                    let b: Vec<_> = c.keys().collect();
    103                    assert_eq!(a, b);
    104                }
    105            }
    106            *self = ConflictStoreTrie::Leaf(con)
    107        }
    108    }
    109}
    110
    111pub(super) struct ConflictCache {
    112    // `con_from_dep` is a cache of the reasons for each time we
    113    // backtrack. For example after several backtracks we may have:
    114    //
    115    //  con_from_dep[`foo = "^1.0.2"`] = map!{
    116    //      `foo=1.0.1`: map!{`foo=1.0.1`: Semver},
    117    //      `foo=1.0.0`: map!{`foo=1.0.0`: Semver},
    118    //  };
    119    //
    120    // This can be read as "we cannot find a candidate for dep `foo = "^1.0.2"`
    121    // if either `foo=1.0.1` OR `foo=1.0.0` are activated".
    122    //
    123    // Another example after several backtracks we may have:
    124    //
    125    //  con_from_dep[`foo = ">=0.8.2, <=0.9.3"`] = map!{
    126    //      `foo=0.8.1`: map!{
    127    //          `foo=0.9.4`: map!{`foo=0.8.1`: Semver, `foo=0.9.4`: Semver},
    128    //      }
    129    //  };
    130    //
    131    // This can be read as "we cannot find a candidate for dep `foo = ">=0.8.2,
    132    // <=0.9.3"` if both `foo=0.8.1` AND `foo=0.9.4` are activated".
    133    //
    134    // This is used to make sure we don't queue work we know will fail. See the
    135    // discussion in https://github.com/rust-lang/cargo/pull/5168 for why this
    136    // is so important. The nested HashMaps act as a kind of btree, that lets us
    137    // look up which entries are still active without
    138    // linearly scanning through the full list.
    139    //
    140    // Also, as a final note, this map is **not** ever removed from. This remains
    141    // as a global cache which we never delete from. Any entry in this map is
    142    // unconditionally true regardless of our resolution history of how we got
    143    // here.
    144    con_from_dep: FxHashMap<Dependency, ConflictStoreTrie>,
    145    // `dep_from_pid` is an inverse-index of `con_from_dep`.
    146    // For every `PackageId` this lists the `Dependency`s that mention it in `dep_from_pid`.
    147    dep_from_pid: FxHashMap<PackageId, FxHashSet<Dependency>>,
    148}
    149
    150impl ConflictCache {
    151    pub fn new() -> ConflictCache {
    152        ConflictCache {
    153            con_from_dep: HashMap::default(),
    154            dep_from_pid: HashMap::default(),
    155        }
    156    }
    157    pub fn find(
    158        &self,
    159        dep: &Dependency,
    160        is_active: &impl Fn(PackageId) -> Option<usize>,
    161        must_contain: Option<PackageId>,
    162        max_age: usize,
    163    ) -> Option<&ConflictMap> {
    164        self.con_from_dep
    165            .get(dep)?
    166            .find(is_active, must_contain, max_age)
    167            .map(|(c, _)| c)
    168    }
    169    /// Finds any known set of conflicts, if any,
    170    /// which are activated in `cx` and contain `PackageId` specified.
    171    /// If more than one are activated, then it will return
    172    /// one that will allow for the most jump-back.
    173    pub fn find_conflicting(
    174        &self,
    175        cx: &ResolverContext,
    176        dep: &Dependency,
    177        must_contain: Option<PackageId>,
    178    ) -> Option<&ConflictMap> {
    179        let out = self.find(dep, &|id| cx.is_active(id), must_contain, usize::MAX);
    180        if cfg!(debug_assertions) {
    181            if let Some(c) = &out {
    182                assert!(cx.is_conflicting(None, c).is_some());
    183                if let Some(f) = must_contain {
    184                    assert!(c.contains_key(&f));
    185                }
    186            }
    187        }
    188        out
    189    }
    190    pub fn conflicting(&self, cx: &ResolverContext, dep: &Dependency) -> Option<&ConflictMap> {
    191        self.find_conflicting(cx, dep, None)
    192    }
    193
    194    /// Adds to the cache a conflict of the form:
    195    /// `dep` is known to be unresolvable if
    196    /// all the `PackageId` entries are activated.
    197    pub fn insert(&mut self, dep: &Dependency, con: &ConflictMap) {
    198        self.con_from_dep
    199            .entry(dep.clone())
    200            .or_insert_with(|| ConflictStoreTrie::Node(BTreeMap::new()))
    201            .insert(con.keys().cloned(), con.clone());
    202
    203        trace!(
    204            "{} = \"{}\" adding a skip {:?}",
    205            dep.package_name(),
    206            dep.version_req(),
    207            con
    208        );
    209
    210        for c in con.keys() {
    211            self.dep_from_pid.entry(*c).or_default().insert(dep.clone());
    212        }
    213    }
    214
    215    pub fn dependencies_conflicting_with(&self, pid: PackageId) -> Option<&FxHashSet<Dependency>> {
    216        self.dep_from_pid.get(&pid)
    217    }
    218}