From 5c244e1c4b88480df9c3f15026c33e8435430ce2 Mon Sep 17 00:00:00 2001 From: Aidan Hobson Sayers Date: Mon, 18 Dec 2017 17:06:45 +0000 Subject: [PATCH] Make resolution backtracking smarter There's no need to try every candidate for every dependency - instead, only try alternative candidates if they *could* change the eventual failure that caused backtracking in the first place. --- src/cargo/core/resolver/mod.rs | 23 +++++++++- tests/resolve.rs | 80 ++++++++++++++++++++++++++++++++++ 2 files changed, 101 insertions(+), 2 deletions(-) diff --git a/src/cargo/core/resolver/mod.rs b/src/cargo/core/resolver/mod.rs index 02a26a9f7..3522df18b 100644 --- a/src/cargo/core/resolver/mod.rs +++ b/src/cargo/core/resolver/mod.rs @@ -745,8 +745,13 @@ fn activate_deps_loop<'a>(mut cx: Context<'a>, Ok(cx) } -// Searches up `backtrack_stack` until it finds a dependency with remaining -// candidates. Resets `cx` and `remaining_deps` to that level and returns the +// Looks through the states in `backtrack_stack` for dependencies with +// remaining candidates. For each one, also checks if rolling back +// could change the outcome of the failed resolution that caused backtracking +// in the first place - namely, if we've backtracked past the parent of the +// failed dep, or the previous number of activations of the failed dep has +// changed (possibly relaxing version constraints). If the outcome could differ, +// resets `cx` and `remaining_deps` to that level and returns the // next candidate. If all candidates have been exhausted, returns None. fn find_candidate<'a>(backtrack_stack: &mut Vec>, cx: &mut Context<'a>, @@ -755,12 +760,18 @@ fn find_candidate<'a>(backtrack_stack: &mut Vec>, cur: &mut usize, dep: &mut Dependency, features: &mut Rc>) -> Option { + let num_dep_prev_active = cx.prev_active(dep).len(); while let Some(mut frame) = backtrack_stack.pop() { let (next, has_another) = { let prev_active = frame.context_backup.prev_active(&frame.dep); (frame.remaining_candidates.next(prev_active), frame.remaining_candidates.clone().next(prev_active).is_some()) }; + let maychange = !frame.context_backup.is_active(parent) || + frame.context_backup.prev_active(dep).len() != num_dep_prev_active; + if !maychange { + continue + } if let Some(candidate) = next { *cur = frame.cur; if has_another { @@ -1178,6 +1189,14 @@ impl<'a> Context<'a> { .unwrap_or(&[]) } + fn is_active(&mut self, summary: &Summary) -> bool { + let id = summary.package_id(); + self.activations.get(id.name()) + .and_then(|v| v.get(id.source_id())) + .map(|v| v.iter().any(|s| s == summary)) + .unwrap_or(false) + } + /// Return all dependencies and the features we want from them. fn resolve_features<'b>(&mut self, s: &'b Summary, diff --git a/tests/resolve.rs b/tests/resolve.rs index 42a67dd37..411c39300 100644 --- a/tests/resolve.rs +++ b/tests/resolve.rs @@ -74,6 +74,13 @@ impl ToPkgId for (&'static str, &'static str) { } } +impl ToPkgId for (&'static str, String) { + fn to_pkgid(&self) -> PackageId { + let (name, ref vers) = *self; + PackageId::new(name, vers, ®istry_loc()).unwrap() + } +} + macro_rules! pkg { ($pkgid:expr => [$($deps:expr),+]) => ({ let d: Vec = vec![$($deps.to_dep()),+]; @@ -364,6 +371,79 @@ fn resolving_with_deep_backtracking() { ("baz", "1.0.1")]))); } +#[test] +fn resolving_with_constrained_sibling_backtrack_parent() { + // There is no point in considering all of the backtrack_trap{1,2} + // candidates since they can't change the result of failing to + // resolve 'constrained'. Cargo should skip past them and resume + // resolution once the activation of the parent, 'bar', is rolled back. + let mut reglist = vec![ + pkg!(("foo", "1.0.0") => [dep_req("bar", "1.0"), + dep_req("constrained", "=1.0.0")]), + + pkg!(("bar", "1.0.0") => [dep_req("backtrack_trap1", "1.0.2"), + dep_req("backtrack_trap2", "1.0.2"), + dep_req("constrained", "1.0.0")]), + pkg!(("constrained", "1.0.0")), + pkg!(("backtrack_trap1", "1.0.0")), + pkg!(("backtrack_trap2", "1.0.0")), + ]; + for i in 1..50 { + let vsn = format!("1.0.{}", i); + reglist.push(pkg!(("bar", vsn.clone()) => [dep_req("backtrack_trap1", "1.0.2"), + dep_req("backtrack_trap2", "1.0.2"), + dep_req("constrained", "1.0.1")])); + reglist.push(pkg!(("backtrack_trap1", vsn.clone()))); + reglist.push(pkg!(("backtrack_trap2", vsn.clone()))); + reglist.push(pkg!(("constrained", vsn.clone()))); + } + let reg = registry(reglist); + + let res = resolve(&pkg_id("root"), vec![ + dep_req("foo", "1"), + ], ®).unwrap(); + + assert_that(&res, contains(names(&[("root", "1.0.0"), + ("foo", "1.0.0"), + ("bar", "1.0.0"), + ("constrained", "1.0.0")]))); +} + +#[test] +fn resolving_with_constrained_sibling_backtrack_activation() { + // It makes sense to resolve most-constrained deps first, but + // with that logic the backtrack traps here come between the two + // attempted resolutions of 'constrained'. When backtracking, + // cargo should skip past them and resume resolution once the + // number of activations for 'constrained' changes. + let mut reglist = vec![ + pkg!(("foo", "1.0.0") => [dep_req("bar", "=1.0.0"), + dep_req("backtrack_trap1", "1.0"), + dep_req("backtrack_trap2", "1.0"), + dep_req("constrained", "<=1.0.60")]), + pkg!(("bar", "1.0.0") => [dep_req("constrained", ">=1.0.60")]), + ]; + for i in 0..45 { + let vsn = format!("1.0.{}", i); + reglist.push(pkg!(("backtrack_trap1", vsn.clone()))); + reglist.push(pkg!(("backtrack_trap2", vsn.clone()))); + } + for i in 0..100 { + let vsn = format!("1.0.{}", i); + reglist.push(pkg!(("constrained", vsn.clone()))); + } + let reg = registry(reglist); + + let res = resolve(&pkg_id("root"), vec![ + dep_req("foo", "1"), + ], ®).unwrap(); + + assert_that(&res, contains(names(&[("root", "1.0.0"), + ("foo", "1.0.0"), + ("bar", "1.0.0"), + ("constrained", "1.0.60")]))); +} + #[test] fn resolving_but_no_exists() { let reg = registry(vec![ -- 2.30.2