diff options
Diffstat (limited to 'crates/resolver-tests/src/lib.rs')
| -rw-r--r-- | crates/resolver-tests/src/lib.rs | 991 |
1 files changed, 991 insertions, 0 deletions
diff --git a/crates/resolver-tests/src/lib.rs b/crates/resolver-tests/src/lib.rs new file mode 100644 index 0000000..3ffb6c5 --- /dev/null +++ b/crates/resolver-tests/src/lib.rs @@ -0,0 +1,991 @@ +#![allow(clippy::all)] + +use std::cell::RefCell; +use std::cmp::PartialEq; +use std::cmp::{max, min}; +use std::collections::{BTreeMap, BTreeSet, HashMap, HashSet}; +use std::fmt; +use std::fmt::Write; +use std::rc::Rc; +use std::task::Poll; +use std::time::Instant; + +use cargo::core::dependency::DepKind; +use cargo::core::resolver::{self, ResolveOpts, VersionPreferences}; +use cargo::core::source::{GitReference, QueryKind, SourceId}; +use cargo::core::Resolve; +use cargo::core::{Dependency, PackageId, Registry, Summary}; +use cargo::util::{CargoResult, Config, Graph, IntoUrl}; + +use proptest::collection::{btree_map, vec}; +use proptest::prelude::*; +use proptest::sample::Index; +use proptest::string::string_regex; +use varisat::{self, ExtendFormula}; + +pub fn resolve(deps: Vec<Dependency>, registry: &[Summary]) -> CargoResult<Vec<PackageId>> { + resolve_with_config(deps, registry, &Config::default().unwrap()) +} + +pub fn resolve_and_validated( + deps: Vec<Dependency>, + registry: &[Summary], + sat_resolve: Option<SatResolve>, +) -> CargoResult<Vec<PackageId>> { + let resolve = resolve_with_config_raw(deps.clone(), registry, &Config::default().unwrap()); + + match resolve { + Err(e) => { + let sat_resolve = sat_resolve.unwrap_or_else(|| SatResolve::new(registry)); + if sat_resolve.sat_resolve(&deps) { + panic!( + "the resolve err but the sat_resolve thinks this will work:\n{}", + sat_resolve.use_packages().unwrap() + ); + } + Err(e) + } + Ok(resolve) => { + let mut stack = vec![pkg_id("root")]; + let mut used = HashSet::new(); + let mut links = HashSet::new(); + while let Some(p) = stack.pop() { + assert!(resolve.contains(&p)); + if used.insert(p) { + // in the tests all `links` crates end in `-sys` + if p.name().ends_with("-sys") { + assert!(links.insert(p.name())); + } + stack.extend(resolve.deps(p).map(|(dp, deps)| { + for d in deps { + assert!(d.matches_id(dp)); + } + dp + })); + } + } + 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!( + "the sat_resolve err but the resolve thinks this will work:\n{:?}", + resolve + ); + } + Ok(out) + } + } +} + +pub fn resolve_with_config( + deps: Vec<Dependency>, + registry: &[Summary], + config: &Config, +) -> CargoResult<Vec<PackageId>> { + let resolve = resolve_with_config_raw(deps, registry, config)?; + Ok(resolve.sort()) +} + +pub fn resolve_with_config_raw( + deps: Vec<Dependency>, + registry: &[Summary], + config: &Config, +) -> CargoResult<Resolve> { + struct MyRegistry<'a> { + list: &'a [Summary], + used: HashSet<PackageId>, + } + impl<'a> Registry for MyRegistry<'a> { + fn query( + &mut self, + dep: &Dependency, + kind: QueryKind, + f: &mut dyn FnMut(Summary), + ) -> Poll<CargoResult<()>> { + for summary in self.list.iter() { + let matched = match kind { + QueryKind::Exact => dep.matches(summary), + QueryKind::Fuzzy => true, + }; + if matched { + self.used.insert(summary.package_id()); + f(summary.clone()); + } + } + Poll::Ready(Ok(())) + } + + fn describe_source(&self, _src: SourceId) -> String { + String::new() + } + + fn is_replaced(&self, _src: SourceId) -> bool { + false + } + + fn block_until_ready(&mut self) -> CargoResult<()> { + Ok(()) + } + } + impl<'a> Drop for MyRegistry<'a> { + fn drop(&mut self) { + if std::thread::panicking() && self.list.len() != self.used.len() { + // we found a case that causes a panic and did not use all of the input. + // lets print the part of the input that was used for minimization. + println!( + "{:?}", + PrettyPrintRegistry( + self.list + .iter() + .filter(|s| { self.used.contains(&s.package_id()) }) + .cloned() + .collect() + ) + ); + } + } + } + let mut registry = MyRegistry { + list: registry, + used: HashSet::new(), + }; + let summary = Summary::new( + config, + pkg_id("root"), + deps, + &BTreeMap::new(), + None::<&String>, + ) + .unwrap(); + let opts = ResolveOpts::everything(); + let start = Instant::now(); + let resolve = resolver::resolve( + &[(summary, opts)], + &[], + &mut registry, + &VersionPreferences::default(), + Some(config), + true, + ); + + // The largest test in our suite takes less then 30 sec. + // So lets fail the test if we have ben running for two long. + assert!(start.elapsed().as_secs() < 60); + resolve +} + +const fn num_bits<T>() -> usize { + std::mem::size_of::<T>() * 8 +} + +fn log_bits(x: usize) -> usize { + if x == 0 { + return 0; + } + assert!(x > 0); + (num_bits::<usize>() as u32 - x.leading_zeros()) as usize +} + +fn sat_at_most_one(solver: &mut impl varisat::ExtendFormula, vars: &[varisat::Var]) { + if vars.len() <= 1 { + return; + } else if vars.len() == 2 { + solver.add_clause(&[vars[0].negative(), vars[1].negative()]); + return; + } else if vars.len() == 3 { + solver.add_clause(&[vars[0].negative(), vars[1].negative()]); + solver.add_clause(&[vars[0].negative(), vars[2].negative()]); + solver.add_clause(&[vars[1].negative(), vars[2].negative()]); + return; + } + // use the "Binary Encoding" from + // https://www.it.uu.se/research/group/astra/ModRef10/papers/Alan%20M.%20Frisch%20and%20Paul%20A.%20Giannoros.%20SAT%20Encodings%20of%20the%20At-Most-k%20Constraint%20-%20ModRef%202010.pdf + let bits: Vec<varisat::Var> = solver.new_var_iter(log_bits(vars.len())).collect(); + for (i, p) in vars.iter().enumerate() { + for b in 0..bits.len() { + solver.add_clause(&[p.negative(), bits[b].lit(((1 << b) & i) > 0)]); + } + } +} + +fn sat_at_most_one_by_key<K: std::hash::Hash + Eq>( + cnf: &mut impl varisat::ExtendFormula, + data: impl Iterator<Item = (K, varisat::Var)>, +) -> HashMap<K, Vec<varisat::Var>> { + // no two packages with the same links set + let mut by_keys: HashMap<K, Vec<varisat::Var>> = HashMap::new(); + for (p, v) in data { + by_keys.entry(p).or_default().push(v) + } + for key in by_keys.values() { + sat_at_most_one(cnf, key); + } + by_keys +} + +/// Resolution can be reduced to the SAT problem. So this is an alternative implementation +/// of the resolver that uses a SAT library for the hard work. This is intended to be easy to read, +/// as compared to the real resolver. +/// +/// For the subset of functionality that are currently made by `registry_strategy` this will, +/// find a valid resolution if one exists. The big thing that the real resolver does, +/// that this one does not do is work with features and optional dependencies. +/// +/// The SAT library dose not optimize for the newer version, +/// so the selected packages may not match the real resolver. +#[derive(Clone)] +pub struct SatResolve(Rc<RefCell<SatResolveInner>>); +struct SatResolveInner { + solver: varisat::Solver<'static>, + var_for_is_packages_used: HashMap<PackageId, varisat::Var>, + by_name: HashMap<&'static str, Vec<PackageId>>, +} + +impl SatResolve { + pub fn new(registry: &[Summary]) -> Self { + let mut cnf = varisat::CnfFormula::new(); + let var_for_is_packages_used: HashMap<PackageId, varisat::Var> = registry + .iter() + .map(|s| (s.package_id(), cnf.new_var())) + .collect(); + + // no two packages with the same links set + sat_at_most_one_by_key( + &mut cnf, + registry + .iter() + .map(|s| (s.links(), var_for_is_packages_used[&s.package_id()])) + .filter(|(l, _)| l.is_some()), + ); + + // no two semver compatible versions of the same package + let by_activations_keys = sat_at_most_one_by_key( + &mut cnf, + var_for_is_packages_used + .iter() + .map(|(p, &v)| (p.as_activations_key(), v)), + ); + + let mut by_name: HashMap<&'static str, Vec<PackageId>> = HashMap::new(); + + for p in registry.iter() { + by_name + .entry(p.name().as_str()) + .or_default() + .push(p.package_id()) + } + + 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 + .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())) + .collect(); + 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); + + // We dont need to `solve` now. We know that "use nothing" will satisfy all the clauses so far. + // But things run faster if we let it spend some time figuring out how the constraints interact before we add assumptions. + solver + .solve() + .expect("docs say it can't error in default config"); + SatResolve(Rc::new(RefCell::new(SatResolveInner { + solver, + var_for_is_packages_used, + by_name, + }))) + } + pub fn sat_resolve(&self, deps: &[Dependency]) -> bool { + let mut s = self.0.borrow_mut(); + let mut assumption = vec![]; + let mut this_call = None; + + // the starting `deps` need to be satisfied + for dep in deps.iter() { + let empty_vec = vec![]; + let matches: Vec<varisat::Lit> = s + .by_name + .get(dep.package_name().as_str()) + .unwrap_or(&empty_vec) + .iter() + .filter(|&p| dep.matches_id(*p)) + .map(|p| s.var_for_is_packages_used[p].positive()) + .collect(); + if matches.is_empty() { + return false; + } else if matches.len() == 1 { + assumption.extend_from_slice(&matches) + } else { + if this_call.is_none() { + let new_var = s.solver.new_var(); + this_call = Some(new_var); + assumption.push(new_var.positive()); + } + let mut matches = matches; + matches.push(this_call.unwrap().negative()); + s.solver.add_clause(&matches); + } + } + + s.solver.assume(&assumption); + + s.solver + .solve() + .expect("docs say it can't error in default config") + } + pub fn sat_is_valid_solution(&self, pids: &[PackageId]) -> bool { + let mut s = self.0.borrow_mut(); + for p in pids { + if p.name().as_str() != "root" && !s.var_for_is_packages_used.contains_key(p) { + return false; + } + } + let assumption: Vec<_> = s + .var_for_is_packages_used + .iter() + .map(|(p, v)| v.lit(pids.contains(p))) + .collect(); + + s.solver.assume(&assumption); + + s.solver + .solve() + .expect("docs say it can't error in default config") + } + fn use_packages(&self) -> Option<String> { + self.0.borrow().solver.model().map(|lits| { + let lits: HashSet<_> = lits + .iter() + .filter(|l| l.is_positive()) + .map(|l| l.var()) + .collect(); + let mut out = String::new(); + out.push_str("used:\n"); + for (p, v) in self.0.borrow().var_for_is_packages_used.iter() { + if lits.contains(v) { + writeln!(&mut out, " {}", p).unwrap(); + } + } + out + }) + } +} + +pub trait ToDep { + fn to_dep(self) -> Dependency; +} + +impl ToDep for &'static str { + fn to_dep(self) -> Dependency { + Dependency::parse(self, Some("1.0.0"), registry_loc()).unwrap() + } +} + +impl ToDep for Dependency { + fn to_dep(self) -> Dependency { + self + } +} + +pub trait ToPkgId { + fn to_pkgid(&self) -> PackageId; +} + +impl ToPkgId for PackageId { + fn to_pkgid(&self) -> PackageId { + *self + } +} + +impl<'a> ToPkgId for &'a str { + fn to_pkgid(&self) -> PackageId { + PackageId::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() + } +} + +#[macro_export] +macro_rules! pkg { + ($pkgid:expr => [$($deps:expr),+ $(,)* ]) => ({ + let d: Vec<Dependency> = vec![$($deps.to_dep()),+]; + $crate::pkg_dep($pkgid, d) + }); + + ($pkgid:expr) => ({ + $crate::pkg($pkgid) + }) +} + +fn registry_loc() -> SourceId { + lazy_static::lazy_static! { + static ref EXAMPLE_DOT_COM: SourceId = + SourceId::for_registry(&"https://example.com".into_url().unwrap()).unwrap(); + } + *EXAMPLE_DOT_COM +} + +pub fn pkg<T: ToPkgId>(name: T) -> Summary { + pkg_dep(name, Vec::new()) +} + +pub fn pkg_dep<T: ToPkgId>(name: T, dep: Vec<Dependency>) -> Summary { + let pkgid = name.to_pkgid(); + let link = if pkgid.name().ends_with("-sys") { + Some(pkgid.name().as_str()) + } else { + None + }; + Summary::new( + &Config::default().unwrap(), + name.to_pkgid(), + dep, + &BTreeMap::new(), + link, + ) + .unwrap() +} + +pub fn pkg_id(name: &str) -> PackageId { + PackageId::new(name, "1.0.0", registry_loc()).unwrap() +} + +fn pkg_id_loc(name: &str, loc: &str) -> PackageId { + let remote = loc.into_url(); + 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() +} + +pub fn pkg_loc(name: &str, loc: &str) -> Summary { + let link = if name.ends_with("-sys") { + Some(name) + } else { + None + }; + Summary::new( + &Config::default().unwrap(), + pkg_id_loc(name, loc), + Vec::new(), + &BTreeMap::new(), + link, + ) + .unwrap() +} + +pub fn remove_dep(sum: &Summary, ind: usize) -> Summary { + let mut deps = sum.dependencies().to_vec(); + deps.remove(ind); + // note: more things will need to be copied over in the future, but it works for now. + Summary::new( + &Config::default().unwrap(), + sum.package_id(), + deps, + &BTreeMap::new(), + sum.links().map(|a| a.as_str()), + ) + .unwrap() +} + +pub fn dep(name: &str) -> Dependency { + dep_req(name, "*") +} +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 { + let mut dep = dep_req(name, req); + dep.set_kind(kind); + dep.set_public(public); + dep +} + +pub fn dep_loc(name: &str, location: &str) -> Dependency { + let url = location.into_url().unwrap(); + let master = GitReference::Branch("master".to_string()); + let source_id = SourceId::for_git(&url, master).unwrap(); + Dependency::parse(name, Some("1.0.0"), source_id).unwrap() +} +pub fn dep_kind(name: &str, kind: DepKind) -> Dependency { + dep(name).set_kind(kind).clone() +} + +pub fn registry(pkgs: Vec<Summary>) -> Vec<Summary> { + pkgs +} + +pub fn names<P: ToPkgId>(names: &[P]) -> Vec<PackageId> { + names.iter().map(|name| name.to_pkgid()).collect() +} + +pub fn loc_names(names: &[(&'static str, &'static str)]) -> Vec<PackageId> { + names + .iter() + .map(|&(name, loc)| pkg_id_loc(name, loc)) + .collect() +} + +/// By default `Summary` and `Dependency` have a very verbose `Debug` representation. +/// This replaces with a representation that uses constructors from this file. +/// +/// If `registry_strategy` is improved to modify more fields +/// then this needs to update to display the corresponding constructor. +pub struct PrettyPrintRegistry(pub Vec<Summary>); + +impl fmt::Debug for PrettyPrintRegistry { + fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { + write!(f, "vec![")?; + for s in &self.0 { + if s.dependencies().is_empty() { + write!(f, "pkg!((\"{}\", \"{}\")),", s.name(), s.version())?; + } else { + write!(f, "pkg!((\"{}\", \"{}\") => [", s.name(), s.version())?; + for d in s.dependencies() { + if d.kind() == DepKind::Normal + && &d.version_req().to_string() == "*" + && !d.is_public() + { + write!(f, "dep(\"{}\"),", d.name_in_toml())?; + } else if d.kind() == DepKind::Normal && !d.is_public() { + write!( + f, + "dep_req(\"{}\", \"{}\"),", + d.name_in_toml(), + d.version_req() + )?; + } else { + write!( + f, + "dep_req_kind(\"{}\", \"{}\", {}, {}),", + d.name_in_toml(), + d.version_req(), + match d.kind() { + DepKind::Development => "DepKind::Development", + DepKind::Build => "DepKind::Build", + DepKind::Normal => "DepKind::Normal", + }, + d.is_public() + )?; + } + } + write!(f, "]),")?; + } + } + write!(f, "]") + } +} + +#[test] +fn meta_test_deep_pretty_print_registry() { + assert_eq!( + &format!( + "{:?}", + PrettyPrintRegistry(vec![ + pkg!(("foo", "1.0.1") => [dep_req("bar", "1")]), + pkg!(("foo", "1.0.0") => [dep_req("bar", "2")]), + pkg!(("foo", "2.0.0") => [dep_req("bar", "*")]), + pkg!(("bar", "1.0.0") => [dep_req("baz", "=1.0.2"), + dep_req("other", "1")]), + 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!(("dep_req", "1.0.0")), + pkg!(("dep_req", "2.0.0")), + ]) + ), + "vec![pkg!((\"foo\", \"1.0.1\") => [dep_req(\"bar\", \"^1\"),]),\ + pkg!((\"foo\", \"1.0.0\") => [dep_req(\"bar\", \"^2\"),]),\ + pkg!((\"foo\", \"2.0.0\") => [dep(\"bar\"),]),\ + pkg!((\"bar\", \"1.0.0\") => [dep_req(\"baz\", \"=1.0.2\"),dep_req(\"other\", \"^1\"),]),\ + 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!((\"dep_req\", \"1.0.0\")),\ + pkg!((\"dep_req\", \"2.0.0\")),]" + ) +} + +/// This generates a random registry index. +/// Unlike vec((Name, Ver, vec((Name, VerRq), ..), ..) +/// This strategy has a high probability of having valid dependencies +pub fn registry_strategy( + max_crates: usize, + max_versions: usize, + shrinkage: usize, +) -> impl Strategy<Value = PrettyPrintRegistry> { + let name = string_regex("[A-Za-z][A-Za-z0-9_-]*(-sys)?").unwrap(); + + let raw_version = ..max_versions.pow(3); + let version_from_raw = move |r: usize| { + let major = ((r / max_versions) / max_versions) % max_versions; + let minor = (r / max_versions) % max_versions; + let patch = r % max_versions; + format!("{}.{}.{}", major, minor, patch) + }; + + // If this is false then the crate will depend on the nonexistent "bad" + // instead of the complex set we generated for it. + let allow_deps = prop::bool::weighted(0.99); + + let list_of_versions = + btree_map(raw_version, allow_deps, 1..=max_versions).prop_map(move |ver| { + ver.into_iter() + .map(|a| (version_from_raw(a.0), a.1)) + .collect::<Vec<_>>() + }); + + let list_of_crates_with_versions = + btree_map(name, list_of_versions, 1..=max_crates).prop_map(|mut vers| { + // root is the name of the thing being compiled + // so it would be confusing to have it in the index + vers.remove("root"); + // bad is a name reserved for a dep that won't work + vers.remove("bad"); + vers + }); + + // each version of each crate can depend on each crate smaller then it. + // In theory shrinkage should be 2, but in practice we get better trees with a larger value. + 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 + ); + + fn order_index(a: Index, b: Index, size: usize) -> (usize, usize) { + let (a, b) = (a.index(size), b.index(size)); + (min(a, b), max(a, b)) + } + + let list_of_raw_dependency = vec(raw_dependency, ..=max_deps); + + // By default a package depends only on other packages that have a smaller name, + // this helps make sure that all things in the resulting index are DAGs. + // If this is true then the DAG is maintained with grater instead. + let reverse_alphabetical = any::<bool>().no_shrink(); + + ( + list_of_crates_with_versions, + list_of_raw_dependency, + reverse_alphabetical, + ) + .prop_map( + |(crate_vers_by_name, raw_dependencies, reverse_alphabetical)| { + let list_of_pkgid: Vec<_> = crate_vers_by_name + .iter() + .flat_map(|(name, vers)| vers.iter().map(move |x| ((name.as_str(), &x.0), x.1))) + .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 { + 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]; + if (list_of_pkgid[b].0).0 == dep_name { + continue; + } + let s = &crate_vers_by_name[dep_name]; + let s_last_index = s.len() - 1; + let (c, d) = order_index(c, d, s.len()); + + dependency_by_pkgid[b].push(dep_req_kind( + dep_name, + &if c == 0 && d == s_last_index { + "*".to_string() + } else if c == 0 { + format!("<={}", s[d].0) + } else if d == s_last_index { + format!(">={}", s[c].0) + } else if c == d { + format!("={}", s[c].0) + } else { + format!(">={}, <={}", s[c].0, s[d].0) + }, + match k { + 0 => DepKind::Normal, + 1 => DepKind::Build, + // => DepKind::Development, // Development has no impact so don't gen + _ => panic!("bad index for DepKind"), + }, + p && k == 0, + )) + } + + let mut out: Vec<Summary> = list_of_pkgid + .into_iter() + .zip(dependency_by_pkgid.into_iter()) + .map(|(((name, ver), allow_deps), deps)| { + pkg_dep( + (name, ver).to_pkgid(), + if !allow_deps { + vec![dep_req("bad", "*")] + } else { + let mut deps = deps; + deps.sort_by_key(|d| d.name_in_toml()); + deps.dedup_by_key(|d| d.name_in_toml()); + deps + }, + ) + }) + .collect(); + + if reverse_alphabetical { + // make sure the complicated cases are at the end + out.reverse(); + } + + PrettyPrintRegistry(out) + }, + ) +} + +/// This test is to test the generator to ensure +/// that it makes registries with large dependency trees +#[test] +fn meta_test_deep_trees_from_strategy() { + use proptest::strategy::ValueTree; + use proptest::test_runner::TestRunner; + + let mut dis = [0; 21]; + + let strategy = registry_strategy(50, 20, 60); + let mut test_runner = TestRunner::deterministic(); + for _ in 0..128 { + let PrettyPrintRegistry(input) = strategy + .new_tree(&mut TestRunner::new_with_rng( + Default::default(), + test_runner.new_rng(), + )) + .unwrap() + .current(); + let reg = registry(input.clone()); + for this in input.iter().rev().take(10) { + let res = resolve( + vec![dep_req(&this.name(), &format!("={}", this.version()))], + ®, + ); + dis[res + .as_ref() + .map(|x| min(x.len(), dis.len()) - 1) + .unwrap_or(0)] += 1; + if dis.iter().all(|&x| x > 0) { + return; + } + } + } + + panic!( + "In 1280 tries we did not see a wide enough distribution of dependency trees! dis: {:?}", + dis + ); +} + +/// This test is to test the generator to ensure +/// that it makes registries that include multiple versions of the same library +#[test] +fn meta_test_multiple_versions_strategy() { + use proptest::strategy::ValueTree; + use proptest::test_runner::TestRunner; + + let mut dis = [0; 10]; + + let strategy = registry_strategy(50, 20, 60); + let mut test_runner = TestRunner::deterministic(); + for _ in 0..128 { + let PrettyPrintRegistry(input) = strategy + .new_tree(&mut TestRunner::new_with_rng( + Default::default(), + test_runner.new_rng(), + )) + .unwrap() + .current(); + let reg = registry(input.clone()); + for this in input.iter().rev().take(10) { + let res = resolve( + vec![dep_req(&this.name(), &format!("={}", this.version()))], + ®, + ); + if let Ok(mut res) = res { + let res_len = res.len(); + res.sort_by_key(|s| s.name()); + res.dedup_by_key(|s| s.name()); + dis[min(res_len - res.len(), dis.len() - 1)] += 1; + } + if dis.iter().all(|&x| x > 0) { + return; + } + } + } + panic!( + "In 1280 tries we did not see a wide enough distribution of multiple versions of the same library! dis: {:?}", + dis + ); +} + +/// Assert `xs` contains `elems` +#[track_caller] +pub fn assert_contains<A: PartialEq>(xs: &[A], elems: &[A]) { + for elem in elems { + assert!(xs.contains(elem)); + } +} + +#[track_caller] +pub fn assert_same<A: PartialEq>(a: &[A], b: &[A]) { + assert_eq!(a.len(), b.len()); + assert_contains(b, a); +} |