diff options
Diffstat (limited to 'src/tools/cargo/crates/resolver-tests')
| -rw-r--r-- | src/tools/cargo/crates/resolver-tests/Cargo.toml | 3 | ||||
| -rw-r--r-- | src/tools/cargo/crates/resolver-tests/src/lib.rs | 174 | ||||
| -rw-r--r-- | src/tools/cargo/crates/resolver-tests/tests/resolve.rs | 225 |
3 files changed, 26 insertions, 376 deletions
diff --git a/src/tools/cargo/crates/resolver-tests/Cargo.toml b/src/tools/cargo/crates/resolver-tests/Cargo.toml index 8750a3d97..947c44569 100644 --- a/src/tools/cargo/crates/resolver-tests/Cargo.toml +++ b/src/tools/cargo/crates/resolver-tests/Cargo.toml @@ -10,3 +10,6 @@ cargo.workspace = true cargo-util.workspace = true proptest.workspace = true varisat.workspace = true + +[lints] +workspace = true diff --git a/src/tools/cargo/crates/resolver-tests/src/lib.rs b/src/tools/cargo/crates/resolver-tests/src/lib.rs index e2cbcee62..2df7a36bb 100644 --- a/src/tools/cargo/crates/resolver-tests/src/lib.rs +++ b/src/tools/cargo/crates/resolver-tests/src/lib.rs @@ -1,9 +1,9 @@ -#![allow(clippy::all)] +#![allow(clippy::print_stderr)] use std::cell::RefCell; use std::cmp::PartialEq; use std::cmp::{max, min}; -use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet}; +use std::collections::{BTreeMap, HashMap, HashSet}; use std::fmt; use std::fmt::Write; use std::rc::Rc; @@ -17,7 +17,9 @@ use cargo::core::Resolve; use cargo::core::{Dependency, PackageId, Registry, Summary}; use cargo::core::{GitReference, SourceId}; use cargo::sources::source::QueryKind; -use cargo::util::{CargoResult, Config, Graph, IntoUrl, RustVersion}; +use cargo::sources::IndexSummary; +use cargo::util::{CargoResult, Config, IntoUrl}; +use cargo::util_schemas::manifest::RustVersion; use proptest::collection::{btree_map, vec}; use proptest::prelude::*; @@ -69,33 +71,6 @@ pub fn resolve_and_validated( let out = resolve.sort(); assert_eq!(out.len(), used.len()); - let mut pub_deps: HashMap<PackageId, HashSet<_>> = HashMap::new(); - for &p in out.iter() { - // make the list of `p` public dependencies - let mut self_pub_dep = HashSet::new(); - self_pub_dep.insert(p); - for (dp, deps) in resolve.deps(p) { - if deps.iter().any(|d| d.is_public()) { - self_pub_dep.extend(pub_deps[&dp].iter().cloned()) - } - } - pub_deps.insert(p, self_pub_dep); - - // check if `p` has a public dependencies conflicts - let seen_dep: BTreeSet<_> = resolve - .deps(p) - .flat_map(|(dp, _)| pub_deps[&dp].iter().cloned()) - .collect(); - let seen_dep: Vec<_> = seen_dep.iter().collect(); - for a in seen_dep.windows(2) { - if a[0].name() == a[1].name() { - panic!( - "the package {:?} can publicly see {:?} and {:?}", - p, a[0], a[1] - ) - } - } - } let sat_resolve = sat_resolve.unwrap_or_else(|| SatResolve::new(registry)); if !sat_resolve.sat_is_valid_solution(&out) { panic!( @@ -131,7 +106,7 @@ pub fn resolve_with_config_raw( &mut self, dep: &Dependency, kind: QueryKind, - f: &mut dyn FnMut(Summary), + f: &mut dyn FnMut(IndexSummary), ) -> Poll<CargoResult<()>> { for summary in self.list.iter() { let matched = match kind { @@ -140,7 +115,7 @@ pub fn resolve_with_config_raw( }; if matched { self.used.insert(summary.package_id()); - f(summary.clone()); + f(IndexSummary::Candidate(summary.clone())); } } Poll::Ready(Ok(())) @@ -200,7 +175,6 @@ pub fn resolve_with_config_raw( &mut registry, &version_prefs, Some(config), - true, ); // The largest test in our suite takes less then 30 sec. @@ -294,7 +268,7 @@ impl SatResolve { ); // no two semver compatible versions of the same package - let by_activations_keys = sat_at_most_one_by_key( + sat_at_most_one_by_key( &mut cnf, var_for_is_packages_used .iter() @@ -312,119 +286,22 @@ impl SatResolve { let empty_vec = vec![]; - let mut graph: Graph<PackageId, ()> = Graph::new(); - - let mut version_selected_for: HashMap< - PackageId, - HashMap<Dependency, HashMap<_, varisat::Var>>, - > = HashMap::new(); // active packages need each of there `deps` to be satisfied for p in registry.iter() { - graph.add(p.package_id()); for dep in p.dependencies() { - // This can more easily be written as: - // !is_active(p) or one of the things that match dep is_active - // All the complexity, from here to the end, is to support public and private dependencies! - let mut by_key: HashMap<_, Vec<varisat::Lit>> = HashMap::new(); - for &m in by_name + let mut matches: Vec<varisat::Lit> = by_name .get(dep.package_name().as_str()) .unwrap_or(&empty_vec) .iter() .filter(|&p| dep.matches_id(*p)) - { - graph.link(p.package_id(), m); - by_key - .entry(m.as_activations_key()) - .or_default() - .push(var_for_is_packages_used[&m].positive()); - } - let keys: HashMap<_, _> = by_key.keys().map(|&k| (k, cnf.new_var())).collect(); - - // if `p` is active then we need to select one of the keys - let matches: Vec<_> = keys - .values() - .map(|v| v.positive()) - .chain(Some(var_for_is_packages_used[&p.package_id()].negative())) + .map(|p| var_for_is_packages_used[&p].positive()) .collect(); + // ^ the `dep` is satisfied or `p` is not active + matches.push(var_for_is_packages_used[&p.package_id()].negative()); cnf.add_clause(&matches); - - // if a key is active then we need to select one of the versions - for (key, vars) in by_key.iter() { - let mut matches = vars.clone(); - matches.push(keys[key].negative()); - cnf.add_clause(&matches); - } - - version_selected_for - .entry(p.package_id()) - .or_default() - .insert(dep.clone(), keys); } } - let topological_order = graph.sort(); - - // we already ensure there is only one version for each `activations_key` so we can think of - // `publicly_exports` as being in terms of a set of `activations_key`s - let mut publicly_exports: HashMap<_, HashMap<_, varisat::Var>> = HashMap::new(); - - for &key in by_activations_keys.keys() { - // everything publicly depends on itself - let var = publicly_exports - .entry(key) - .or_default() - .entry(key) - .or_insert_with(|| cnf.new_var()); - cnf.add_clause(&[var.positive()]); - } - - // if a `dep` is public then `p` `publicly_exports` all the things that the selected version `publicly_exports` - for &p in topological_order.iter() { - if let Some(deps) = version_selected_for.get(&p) { - let mut p_exports = publicly_exports.remove(&p.as_activations_key()).unwrap(); - for (_, versions) in deps.iter().filter(|(d, _)| d.is_public()) { - for (ver, sel) in versions { - for (&export_pid, &export_var) in publicly_exports[ver].iter() { - let our_var = - p_exports.entry(export_pid).or_insert_with(|| cnf.new_var()); - cnf.add_clause(&[ - sel.negative(), - export_var.negative(), - our_var.positive(), - ]); - } - } - } - publicly_exports.insert(p.as_activations_key(), p_exports); - } - } - - // we already ensure there is only one version for each `activations_key` so we can think of - // `can_see` as being in terms of a set of `activations_key`s - // and if `p` `publicly_exports` `export` then it `can_see` `export` - let mut can_see: HashMap<_, HashMap<_, varisat::Var>> = HashMap::new(); - - // if `p` has a `dep` that selected `ver` then it `can_see` all the things that the selected version `publicly_exports` - for (&p, deps) in version_selected_for.iter() { - let p_can_see = can_see.entry(p).or_default(); - for (_, versions) in deps.iter() { - for (&ver, sel) in versions { - for (&export_pid, &export_var) in publicly_exports[&ver].iter() { - let our_var = p_can_see.entry(export_pid).or_insert_with(|| cnf.new_var()); - cnf.add_clause(&[ - sel.negative(), - export_var.negative(), - our_var.positive(), - ]); - } - } - } - } - - // a package `can_see` only one version by each name - for (_, see) in can_see.iter() { - sat_at_most_one_by_key(&mut cnf, see.iter().map(|((name, _, _), &v)| (name, v))); - } let mut solver = varisat::Solver::new(); solver.add_formula(&cnf); @@ -543,14 +420,14 @@ impl ToPkgId for PackageId { impl<'a> ToPkgId for &'a str { fn to_pkgid(&self) -> PackageId { - PackageId::new(*self, "1.0.0", registry_loc()).unwrap() + PackageId::try_new(*self, "1.0.0", registry_loc()).unwrap() } } impl<T: AsRef<str>, U: AsRef<str>> ToPkgId for (T, U) { fn to_pkgid(&self) -> PackageId { let (name, vers) = self; - PackageId::new(name.as_ref(), vers.as_ref(), registry_loc()).unwrap() + PackageId::try_new(name.as_ref(), vers.as_ref(), registry_loc()).unwrap() } } @@ -596,7 +473,7 @@ pub fn pkg_dep<T: ToPkgId>(name: T, dep: Vec<Dependency>) -> Summary { } pub fn pkg_id(name: &str) -> PackageId { - PackageId::new(name, "1.0.0", registry_loc()).unwrap() + PackageId::try_new(name, "1.0.0", registry_loc()).unwrap() } fn pkg_id_loc(name: &str, loc: &str) -> PackageId { @@ -604,7 +481,7 @@ fn pkg_id_loc(name: &str, loc: &str) -> PackageId { let master = GitReference::Branch("master".to_string()); let source_id = SourceId::for_git(&remote.unwrap(), master).unwrap(); - PackageId::new(name, "1.0.0", source_id).unwrap() + PackageId::try_new(name, "1.0.0", source_id).unwrap() } pub fn pkg_loc(name: &str, loc: &str) -> Summary { @@ -643,10 +520,9 @@ pub fn dep(name: &str) -> Dependency { pub fn dep_req(name: &str, req: &str) -> Dependency { Dependency::parse(name, Some(req), registry_loc()).unwrap() } -pub fn dep_req_kind(name: &str, req: &str, kind: DepKind, public: bool) -> Dependency { +pub fn dep_req_kind(name: &str, req: &str, kind: DepKind) -> Dependency { let mut dep = dep_req(name, req); dep.set_kind(kind); - dep.set_public(public); dep } @@ -739,8 +615,8 @@ fn meta_test_deep_pretty_print_registry() { pkg!(("bar", "2.0.0") => [dep_req("baz", "=1.0.1")]), pkg!(("baz", "1.0.2") => [dep_req("other", "2")]), pkg!(("baz", "1.0.1")), - pkg!(("cat", "1.0.2") => [dep_req_kind("other", "2", DepKind::Build, false)]), - pkg!(("cat", "1.0.3") => [dep_req_kind("other", "2", DepKind::Development, false)]), + pkg!(("cat", "1.0.2") => [dep_req_kind("other", "2", DepKind::Build)]), + pkg!(("cat", "1.0.3") => [dep_req_kind("other", "2", DepKind::Development)]), pkg!(("dep_req", "1.0.0")), pkg!(("dep_req", "2.0.0")), ]) @@ -803,14 +679,7 @@ pub fn registry_strategy( let max_deps = max_versions * (max_crates * (max_crates - 1)) / shrinkage; let raw_version_range = (any::<Index>(), any::<Index>()); - let raw_dependency = ( - any::<Index>(), - any::<Index>(), - raw_version_range, - 0..=1, - Just(false), - // TODO: ^ this needs to be set back to `any::<bool>()` and work before public & private dependencies can stabilize - ); + let raw_dependency = (any::<Index>(), any::<Index>(), raw_version_range, 0..=1); fn order_index(a: Index, b: Index, size: usize) -> (usize, usize) { let (a, b) = (a.index(size), b.index(size)); @@ -837,7 +706,7 @@ pub fn registry_strategy( .collect(); let len_all_pkgid = list_of_pkgid.len(); let mut dependency_by_pkgid = vec![vec![]; len_all_pkgid]; - for (a, b, (c, d), k, p) in raw_dependencies { + for (a, b, (c, d), k) in raw_dependencies { let (a, b) = order_index(a, b, len_all_pkgid); let (a, b) = if reverse_alphabetical { (b, a) } else { (a, b) }; let ((dep_name, _), _) = list_of_pkgid[a]; @@ -867,7 +736,6 @@ pub fn registry_strategy( // => DepKind::Development, // Development has no impact so don't gen _ => panic!("bad index for DepKind"), }, - p && k == 0, )) } diff --git a/src/tools/cargo/crates/resolver-tests/tests/resolve.rs b/src/tools/cargo/crates/resolver-tests/tests/resolve.rs index dd21502d8..662bad90f 100644 --- a/src/tools/cargo/crates/resolver-tests/tests/resolve.rs +++ b/src/tools/cargo/crates/resolver-tests/tests/resolve.rs @@ -6,8 +6,8 @@ use cargo::util::Config; use cargo_util::is_ci; use resolver_tests::{ - assert_contains, assert_same, dep, dep_kind, dep_loc, dep_req, dep_req_kind, loc_names, names, - pkg, pkg_id, pkg_loc, registry, registry_strategy, remove_dep, resolve, resolve_and_validated, + assert_contains, assert_same, dep, dep_kind, dep_loc, dep_req, loc_names, names, pkg, pkg_id, + pkg_loc, registry, registry_strategy, remove_dep, resolve, resolve_and_validated, resolve_with_config, PrettyPrintRegistry, SatResolve, ToDep, ToPkgId, }; @@ -288,192 +288,6 @@ proptest! { } #[test] -#[should_panic(expected = "pub dep")] // The error handling is not yet implemented. -fn pub_fail() { - let input = vec![ - pkg!(("a", "0.0.4")), - pkg!(("a", "0.0.5")), - pkg!(("e", "0.0.6") => [dep_req_kind("a", "<= 0.0.4", DepKind::Normal, true),]), - pkg!(("kB", "0.0.3") => [dep_req("a", ">= 0.0.5"),dep("e"),]), - ]; - let reg = registry(input); - assert!(resolve_and_validated(vec![dep("kB")], ®, None).is_err()); -} - -#[test] -fn basic_public_dependency() { - let reg = registry(vec![ - pkg!(("A", "0.1.0")), - pkg!(("A", "0.2.0")), - pkg!("B" => [dep_req_kind("A", "0.1", DepKind::Normal, true)]), - pkg!("C" => [dep("A"), dep("B")]), - ]); - - let res = resolve_and_validated(vec![dep("C")], ®, None).unwrap(); - assert_same( - &res, - &names(&[ - ("root", "1.0.0"), - ("C", "1.0.0"), - ("B", "1.0.0"), - ("A", "0.1.0"), - ]), - ); -} - -#[test] -fn public_dependency_filling_in() { - // The resolver has an optimization where if a candidate to resolve a dependency - // has already bean activated then we skip looking at the candidates dependencies. - // However, we have to be careful as the new path may make pub dependencies invalid. - - // Triggering this case requires dependencies to be resolved in a specific order. - // Fuzzing found this unintuitive case, that triggers this unfortunate order of operations: - // 1. `d`'s dep on `c` is resolved - // 2. `d`'s dep on `a` is resolved with `0.1.1` - // 3. `c`'s dep on `b` is resolved with `0.0.2` - // 4. `b`'s dep on `a` is resolved with `0.0.6` no pub dev conflict as `b` is private to `c` - // 5. `d`'s dep on `b` is resolved with `0.0.2` triggering the optimization. - // Do we notice that `d` has a pub dep conflict on `a`? Lets try it and see. - let reg = registry(vec![ - pkg!(("a", "0.0.6")), - pkg!(("a", "0.1.1")), - pkg!(("b", "0.0.0") => [dep("bad")]), - pkg!(("b", "0.0.1") => [dep("bad")]), - pkg!(("b", "0.0.2") => [dep_req_kind("a", "=0.0.6", DepKind::Normal, true)]), - pkg!("c" => [dep_req("b", ">=0.0.1")]), - pkg!("d" => [dep("c"), dep("a"), dep("b")]), - ]); - - let res = resolve_and_validated(vec![dep("d")], ®, None).unwrap(); - assert_same( - &res, - &names(&[ - ("root", "1.0.0"), - ("d", "1.0.0"), - ("c", "1.0.0"), - ("b", "0.0.2"), - ("a", "0.0.6"), - ]), - ); -} - -#[test] -fn public_dependency_filling_in_and_update() { - // The resolver has an optimization where if a candidate to resolve a dependency - // has already bean activated then we skip looking at the candidates dependencies. - // However, we have to be careful as the new path may make pub dependencies invalid. - - // Triggering this case requires dependencies to be resolved in a specific order. - // Fuzzing found this unintuitive case, that triggers this unfortunate order of operations: - // 1. `D`'s dep on `B` is resolved - // 2. `D`'s dep on `C` is resolved - // 3. `B`'s dep on `A` is resolved with `0.0.0` - // 4. `C`'s dep on `B` triggering the optimization. - // So did we add `A 0.0.0` to the deps `C` can see? - // Or are we going to resolve `C`'s dep on `A` with `0.0.2`? - // Lets try it and see. - let reg = registry(vec![ - pkg!(("A", "0.0.0")), - pkg!(("A", "0.0.2")), - pkg!("B" => [dep_req_kind("A", "=0.0.0", DepKind::Normal, true),]), - pkg!("C" => [dep("A"),dep("B")]), - pkg!("D" => [dep("B"),dep("C")]), - ]); - let res = resolve_and_validated(vec![dep("D")], ®, None).unwrap(); - assert_same( - &res, - &names(&[ - ("root", "1.0.0"), - ("D", "1.0.0"), - ("C", "1.0.0"), - ("B", "1.0.0"), - ("A", "0.0.0"), - ]), - ); -} - -#[test] -fn public_dependency_skipping() { - // When backtracking due to a failed dependency, if Cargo is - // trying to be clever and skip irrelevant dependencies, care must - // the effects of pub dep must be accounted for. - let input = vec![ - pkg!(("a", "0.2.0")), - pkg!(("a", "2.0.0")), - pkg!(("b", "0.0.0") => [dep("bad")]), - pkg!(("b", "0.2.1") => [dep_req_kind("a", "0.2.0", DepKind::Normal, true)]), - pkg!("c" => [dep("a"),dep("b")]), - ]; - let reg = registry(input); - - resolve_and_validated(vec![dep("c")], ®, None).unwrap(); -} - -#[test] -fn public_dependency_skipping_in_backtracking() { - // When backtracking due to a failed dependency, if Cargo is - // trying to be clever and skip irrelevant dependencies, care must - // the effects of pub dep must be accounted for. - let input = vec![ - pkg!(("A", "0.0.0") => [dep("bad")]), - pkg!(("A", "0.0.1") => [dep("bad")]), - pkg!(("A", "0.0.2") => [dep("bad")]), - pkg!(("A", "0.0.3") => [dep("bad")]), - pkg!(("A", "0.0.4")), - pkg!(("A", "0.0.5")), - pkg!("B" => [dep_req_kind("A", ">= 0.0.3", DepKind::Normal, true)]), - pkg!("C" => [dep_req("A", "<= 0.0.4"), dep("B")]), - ]; - let reg = registry(input); - - resolve_and_validated(vec![dep("C")], ®, None).unwrap(); -} - -#[test] -fn public_sat_topological_order() { - let input = vec![ - pkg!(("a", "0.0.1")), - pkg!(("a", "0.0.0")), - pkg!(("b", "0.0.1") => [dep_req_kind("a", "= 0.0.1", DepKind::Normal, true),]), - pkg!(("b", "0.0.0") => [dep("bad"),]), - pkg!("A" => [dep_req("a", "= 0.0.0"),dep_req_kind("b", "*", DepKind::Normal, true)]), - ]; - - let reg = registry(input); - assert!(resolve_and_validated(vec![dep("A")], ®, None).is_err()); -} - -#[test] -fn public_sat_unused_makes_things_pub() { - let input = vec![ - pkg!(("a", "0.0.1")), - pkg!(("a", "0.0.0")), - pkg!(("b", "8.0.1") => [dep_req_kind("a", "= 0.0.1", DepKind::Normal, true),]), - pkg!(("b", "8.0.0") => [dep_req("a", "= 0.0.1"),]), - pkg!("c" => [dep_req("b", "= 8.0.0"),dep_req("a", "= 0.0.0"),]), - ]; - let reg = registry(input); - - resolve_and_validated(vec![dep("c")], ®, None).unwrap(); -} - -#[test] -fn public_sat_unused_makes_things_pub_2() { - let input = vec![ - pkg!(("c", "0.0.2")), - pkg!(("c", "0.0.1")), - pkg!(("a-sys", "0.0.2")), - pkg!(("a-sys", "0.0.1") => [dep_req_kind("c", "= 0.0.1", DepKind::Normal, true),]), - pkg!("P" => [dep_req_kind("a-sys", "*", DepKind::Normal, true),dep_req("c", "= 0.0.1"),]), - pkg!("A" => [dep("P"),dep_req("c", "= 0.0.2"),]), - ]; - let reg = registry(input); - - resolve_and_validated(vec![dep("A")], ®, None).unwrap(); -} - -#[test] #[should_panic(expected = "assertion failed: !name.is_empty()")] fn test_dependency_with_empty_name() { // Bug 5229, dependency-names must not be empty @@ -1116,41 +930,6 @@ fn resolving_with_constrained_sibling_backtrack_activation() { } #[test] -fn resolving_with_public_constrained_sibling() { - // 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", "<=60")]), - pkg!(("bar", "1.0.0") => [dep_req_kind("constrained", ">=60", DepKind::Normal, true)]), - ]; - // Bump these to make the test harder, but you'll also need to - // change the version constraints on `constrained` above. To correctly - // exercise Cargo, the relationship between the values is: - // NUM_CONSTRAINED - vsn < NUM_TRAPS < vsn - // to make sure the traps are resolved between `constrained`. - const NUM_TRAPS: usize = 45; // min 1 - const NUM_CONSTRAINED: usize = 100; // min 1 - for i in 0..NUM_TRAPS { - let vsn = format!("1.0.{}", i); - reglist.push(pkg!(("backtrack_trap1", vsn.clone()))); - reglist.push(pkg!(("backtrack_trap2", vsn.clone()))); - } - for i in 0..NUM_CONSTRAINED { - let vsn = format!("{}.0.0", i); - reglist.push(pkg!(("constrained", vsn.clone()))); - } - let reg = registry(reglist); - - let _ = resolve_and_validated(vec![dep_req("foo", "1")], ®, None); -} - -#[test] fn resolving_with_constrained_sibling_transitive_dep_effects() { // When backtracking due to a failed dependency, if Cargo is // trying to be clever and skip irrelevant dependencies, care must |