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