Skip to content

Commit 5e85ba1

Browse files
borsbors
committed
Auto merge of #6366 - Eh2406:faster-filtered-search, r=alexcrichton
ConflictStoreTrie: Faster filtered search This is an optimization that I was thinking of doing in #6283. I did not then as this is optimizing a not particularly hot path. I wish to do it now as it is stuck in my head, and I need that head space for more important things. This also "accidentally" fixes the [indeterminacy](#6283 (comment)) introduced in #6283, by replacing the `HashMap.iter().find()` like code with `BTreeMap.iter().find()` like code. This is not strictly needed, as @alexcrichton pointed out (In most use cases the index will change between any two invocations anyway), but does make it much easier to deal with (fuzz) test cases.
2 parents e66ae61 + eeaebfc commit 5e85ba1

File tree

4 files changed

+80
-26
lines changed

4 files changed

+80
-26
lines changed

‎src/cargo/core/resolver/conflict_cache.rs‎

Lines changed: 31 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -11,36 +11,39 @@ enum ConflictStoreTrie {
1111
Leaf(BTreeMap<PackageId, ConflictReason>),
1212
/// a Node is a map from an element to a subTrie where
1313
/// all the Sets in the subTrie contains that element.
14-
Node(HashMap<PackageId, ConflictStoreTrie>),
14+
Node(BTreeMap<PackageId, ConflictStoreTrie>),
1515
}
1616

1717
impl ConflictStoreTrie {
1818
/// Finds any known set of conflicts, if any,
1919
/// which are activated in `cx` and pass the `filter` specified?
20-
fn find_conflicting<F>(
20+
fn find_conflicting(
2121
&self,
2222
cx: &Context,
23-
filter: &F,
24-
) -> Option<&BTreeMap<PackageId, ConflictReason>>
25-
where
26-
for<'r> F: Fn(&'r &BTreeMap<PackageId, ConflictReason>) -> bool,
27-
{
23+
must_contain: Option<PackageId>,
24+
) -> Option<&BTreeMap<PackageId, ConflictReason>> {
2825
match self {
2926
ConflictStoreTrie::Leaf(c) => {
30-
if filter(&c) {
27+
if must_contain.is_none() {
3128
// is_conflicting checks that all the elements are active,
3229
// but we have checked each one by the recursion of this function.
3330
debug_assert!(cx.is_conflicting(None, c));
3431
Some(c)
3532
} else {
33+
// we did not find `must_contain` so we need to keep looking.
3634
None
3735
}
3836
}
3937
ConflictStoreTrie::Node(m) => {
40-
for (&pid, store) in m {
38+
for (&pid, store) in must_contain
39+
.map(|f| m.range(..=f))
40+
.unwrap_or_else(|| m.range(..))
41+
{
4142
// if the key is active then we need to check all of the corresponding subTrie.
4243
if cx.is_active(pid) {
43-
if let Some(o) = store.find_conflicting(cx, filter) {
44+
if let Some(o) =
45+
store.find_conflicting(cx, must_contain.filter(|&f| f != pid))
46+
{
4447
return Some(o);
4548
}
4649
} // else, if it is not active then there is no way any of the corresponding
@@ -59,7 +62,7 @@ impl ConflictStoreTrie {
5962
if let Some(pid) = iter.next() {
6063
if let ConflictStoreTrie::Node(p) = self {
6164
p.entry(pid)
62-
.or_insert_with(|| ConflictStoreTrie::Node(HashMap::new()))
65+
.or_insert_with(|| ConflictStoreTrie::Node(BTreeMap::new()))
6366
.insert(iter, con);
6467
} // else, We already have a subset of this in the ConflictStore
6568
} else {
@@ -134,23 +137,31 @@ impl ConflictCache {
134137
}
135138
/// Finds any known set of conflicts, if any,
136139
/// which are activated in `cx` and pass the `filter` specified?
137-
pub fn find_conflicting<F>(
140+
pub fn find_conflicting(
138141
&self,
139142
cx: &Context,
140143
dep: &Dependency,
141-
filter: F,
142-
) -> Option<&BTreeMap<PackageId, ConflictReason>>
143-
where
144-
for<'r> F: Fn(&'r &BTreeMap<PackageId, ConflictReason>) -> bool,
145-
{
146-
self.con_from_dep.get(dep)?.find_conflicting(cx, &filter)
144+
must_contain: Option<PackageId>,
145+
) -> Option<&BTreeMap<PackageId, ConflictReason>> {
146+
let out = self
147+
.con_from_dep
148+
.get(dep)?
149+
.find_conflicting(cx, must_contain);
150+
if cfg!(debug_assertions) {
151+
if let Some(f) = must_contain {
152+
if let Some(c) = &out {
153+
assert!(c.contains_key(&f));
154+
}
155+
}
156+
}
157+
out
147158
}
148159
pub fn conflicting(
149160
&self,
150161
cx: &Context,
151162
dep: &Dependency,
152163
) -> Option<&BTreeMap<PackageId, ConflictReason>> {
153-
self.find_conflicting(cx, dep, |_| true)
164+
self.find_conflicting(cx, dep, None)
154165
}
155166

156167
/// Add to the cache a conflict of the form:
@@ -159,7 +170,7 @@ impl ConflictCache {
159170
pub fn insert(&mut self, dep: &Dependency, con: &BTreeMap<PackageId, ConflictReason>) {
160171
self.con_from_dep
161172
.entry(dep.clone())
162-
.or_insert_with(|| ConflictStoreTrie::Node(HashMap::new()))
173+
.or_insert_with(|| ConflictStoreTrie::Node(BTreeMap::new()))
163174
.insert(con.keys().cloned(), con.clone());
164175

165176
trace!(

‎src/cargo/core/resolver/mod.rs‎

Lines changed: 1 addition & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -442,9 +442,7 @@ fn activate_deps_loop(
442442
})
443443
.filter_map(|(other_parent, other_dep)| {
444444
past_conflicting_activations
445-
.find_conflicting(&cx, &other_dep, |con| {
446-
con.contains_key(&pid)
447-
})
445+
.find_conflicting(&cx, &other_dep, Some(pid))
448446
.map(|con| (other_parent, con))
449447
})
450448
.next()

‎tests/testsuite/resolve.rs‎

Lines changed: 40 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1201,3 +1201,43 @@ fn large_conflict_cache() {
12011201
let reg = registry(input);
12021202
let _ = resolve(&pkg_id("root"), root_deps, &reg);
12031203
}
1204+
1205+
#[test]
1206+
fn conflict_store_bug() {
1207+
let input = vec![
1208+
pkg!(("A", "0.0.3")),
1209+
pkg!(("A", "0.0.5")),
1210+
pkg!(("A", "0.0.9") => [dep("bad"),]),
1211+
pkg!(("A", "0.0.10") => [dep("bad"),]),
1212+
pkg!(("L-sys", "0.0.1") => [dep("bad"),]),
1213+
pkg!(("L-sys", "0.0.5")),
1214+
pkg!(("R", "0.0.4") => [
1215+
dep_req("L-sys", "= 0.0.5"),
1216+
]),
1217+
pkg!(("R", "0.0.6")),
1218+
pkg!(("a-sys", "0.0.5")),
1219+
pkg!(("a-sys", "0.0.11")),
1220+
pkg!(("c", "0.0.12") => [
1221+
dep_req("R", ">= 0.0.3, <= 0.0.4"),
1222+
]),
1223+
pkg!(("c", "0.0.13") => [
1224+
dep_req("a-sys", ">= 0.0.8, <= 0.0.11"),
1225+
]),
1226+
pkg!(("c0", "0.0.6") => [
1227+
dep_req("L-sys", "<= 0.0.2"),
1228+
]),
1229+
pkg!(("c0", "0.0.10") => [
1230+
dep_req("A", ">= 0.0.9, <= 0.0.10"),
1231+
dep_req("a-sys", "= 0.0.5"),
1232+
]),
1233+
pkg!("j" => [
1234+
dep_req("A", ">= 0.0.3, <= 0.0.5"),
1235+
dep_req("R", ">=0.0.4, <= 0.0.6"),
1236+
dep_req("c", ">= 0.0.9"),
1237+
dep_req("c0", ">= 0.0.6"),
1238+
]),
1239+
];
1240+
1241+
let reg = registry(input.clone());
1242+
let _ = resolve_and_validated(&pkg_id("root"), vec![dep("j")], &reg);
1243+
}

‎tests/testsuite/support/resolver.rs‎

Lines changed: 8 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -355,8 +355,13 @@ pub fn registry_strategy(
355355
) -> impl Strategy<Value = PrettyPrintRegistry> {
356356
let name = string_regex("[A-Za-z][A-Za-z0-9_-]*(-sys)?").unwrap();
357357

358-
let raw_version = [..max_versions; 3];
359-
let version_from_raw = |v: &[usize; 3]| format!("{}.{}.{}", v[0], v[1], v[2]);
358+
let raw_version = ..max_versions.pow(3);
359+
let version_from_raw = move |r: usize| {
360+
let major = ((r / max_versions) / max_versions) % max_versions;
361+
let minor = (r / max_versions) % max_versions;
362+
let patch = r % max_versions;
363+
format!("{}.{}.{}", major, minor, patch)
364+
};
360365

361366
// If this is false than the crate will depend on the nonexistent "bad"
362367
// instead of the complex set we generated for it.
@@ -365,7 +370,7 @@ pub fn registry_strategy(
365370
let list_of_versions =
366371
btree_map(raw_version, allow_deps, 1..=max_versions).prop_map(move |ver| {
367372
ver.into_iter()
368-
.map(|a| (version_from_raw(&a.0), a.1))
373+
.map(|a| (version_from_raw(a.0), a.1))
369374
.collect::<Vec<_>>()
370375
});
371376

0 commit comments

Comments
 (0)