Mercurial > hg-stable
changeset 41703:ee7b7bd432a1
rust: translated random test of missingancestors
This is a Rust implementation of the random
DAG generator and related incrementalmissingancestors
tests against a naive brute force implementation.
It is provided as an integration test, so that it
won't run by default if any unit test fails.
In case of a failed example, all needed information
for reproduction is included in the panic message,
(this is how
`test_remove_ancestors_from_case1()` has been generated),
as well as the random seed.
The whole test is rerunnable by passing the random seed
in the TEST_RANDOM_SEED environment variable.
The other parameters (numbers of iterations) can be passed
in the TEST_MISSING_ANCESTORS environment variable.
An alternative would have been to expose to Python
MissingAncestors<VecGraphs> but that would have meant
pollution of the release build used from Python,
whereas we do it in this changeset within the tests submodule
Differential Revision: https://phab.mercurial-scm.org/D5417
| author | Georges Racinet <gracinet@anybox.fr> |
|---|---|
| date | Sun, 02 Dec 2018 16:19:22 +0100 |
| parents | 09814946cc6a |
| children | 060c030c9993 |
| files | rust/Cargo.lock rust/hg-core/Cargo.toml rust/hg-core/src/lib.rs rust/hg-core/tests/test_missing_ancestors.rs |
| diffstat | 4 files changed, 537 insertions(+), 2 deletions(-) [+] |
line wrap: on
line diff
--- a/rust/Cargo.lock Tue Feb 12 13:46:38 2019 -0800 +++ b/rust/Cargo.lock Sun Dec 02 16:19:22 2018 +0100 @@ -7,11 +7,29 @@ ] [[package]] +name = "autocfg" +version = "0.1.2" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "bitflags" +version = "1.0.4" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] name = "cfg-if" version = "0.1.6" source = "registry+https://github.com/rust-lang/crates.io-index" [[package]] +name = "cloudabi" +version = "0.0.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "bitflags 1.0.4 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] name = "cpython" version = "0.2.1" source = "registry+https://github.com/rust-lang/crates.io-index" @@ -23,8 +41,17 @@ ] [[package]] +name = "fuchsia-cprng" +version = "0.1.0" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] name = "hg-core" version = "0.1.0" +dependencies = [ + "rand 0.6.5 (registry+https://github.com/rust-lang/crates.io-index)", + "rand_pcg 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)", +] [[package]] name = "hg-cpython" @@ -89,6 +116,110 @@ ] [[package]] +name = "rand" +version = "0.6.5" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "autocfg 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)", + "libc 0.2.45 (registry+https://github.com/rust-lang/crates.io-index)", + "rand_chacha 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)", + "rand_core 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)", + "rand_hc 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)", + "rand_isaac 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)", + "rand_jitter 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)", + "rand_os 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)", + "rand_pcg 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)", + "rand_xorshift 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)", + "winapi 0.3.6 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "rand_chacha" +version = "0.1.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "autocfg 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)", + "rand_core 0.3.1 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "rand_core" +version = "0.3.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "rand_core 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "rand_core" +version = "0.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "rand_hc" +version = "0.1.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "rand_core 0.3.1 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "rand_isaac" +version = "0.1.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "rand_core 0.3.1 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "rand_jitter" +version = "0.1.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "libc 0.2.45 (registry+https://github.com/rust-lang/crates.io-index)", + "rand_core 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)", + "winapi 0.3.6 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "rand_os" +version = "0.1.2" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "cloudabi 0.0.3 (registry+https://github.com/rust-lang/crates.io-index)", + "fuchsia-cprng 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)", + "libc 0.2.45 (registry+https://github.com/rust-lang/crates.io-index)", + "rand_core 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)", + "rdrand 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)", + "winapi 0.3.6 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "rand_pcg" +version = "0.1.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "rand_core 0.3.1 (registry+https://github.com/rust-lang/crates.io-index)", + "rustc_version 0.2.3 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "rand_xorshift" +version = "0.1.1" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "rand_core 0.3.1 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "rdrand" +version = "0.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "rand_core 0.3.1 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] name = "regex" version = "1.1.0" source = "registry+https://github.com/rust-lang/crates.io-index" @@ -109,6 +240,27 @@ ] [[package]] +name = "rustc_version" +version = "0.2.3" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "semver 0.9.0 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "semver" +version = "0.9.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "semver-parser 0.7.0 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "semver-parser" +version = "0.7.0" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] name = "thread_local" version = "0.3.6" source = "registry+https://github.com/rust-lang/crates.io-index" @@ -131,19 +283,59 @@ version = "0.1.5" source = "registry+https://github.com/rust-lang/crates.io-index" +[[package]] +name = "winapi" +version = "0.3.6" +source = "registry+https://github.com/rust-lang/crates.io-index" +dependencies = [ + "winapi-i686-pc-windows-gnu 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)", + "winapi-x86_64-pc-windows-gnu 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)", +] + +[[package]] +name = "winapi-i686-pc-windows-gnu" +version = "0.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" + +[[package]] +name = "winapi-x86_64-pc-windows-gnu" +version = "0.4.0" +source = "registry+https://github.com/rust-lang/crates.io-index" + [metadata] "checksum aho-corasick 0.6.9 (registry+https://github.com/rust-lang/crates.io-index)" = "1e9a933f4e58658d7b12defcf96dc5c720f20832deebe3e0a19efd3b6aaeeb9e" +"checksum autocfg 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)" = "a6d640bee2da49f60a4068a7fae53acde8982514ab7bae8b8cea9e88cbcfd799" +"checksum bitflags 1.0.4 (registry+https://github.com/rust-lang/crates.io-index)" = "228047a76f468627ca71776ecdebd732a3423081fcf5125585bcd7c49886ce12" "checksum cfg-if 0.1.6 (registry+https://github.com/rust-lang/crates.io-index)" = "082bb9b28e00d3c9d39cc03e64ce4cea0f1bb9b3fde493f0cbc008472d22bdf4" +"checksum cloudabi 0.0.3 (registry+https://github.com/rust-lang/crates.io-index)" = "ddfc5b9aa5d4507acaf872de71051dfd0e309860e88966e1051e462a077aac4f" "checksum cpython 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)" = "b489034e723e7f5109fecd19b719e664f89ef925be785885252469e9822fa940" +"checksum fuchsia-cprng 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "81f7f8eb465745ea9b02e2704612a9946a59fa40572086c6fd49d6ddcf30bf31" "checksum lazy_static 1.2.0 (registry+https://github.com/rust-lang/crates.io-index)" = "a374c89b9db55895453a74c1e38861d9deec0b01b405a82516e9d5de4820dea1" "checksum libc 0.2.45 (registry+https://github.com/rust-lang/crates.io-index)" = "2d2857ec59fadc0773853c664d2d18e7198e83883e7060b63c924cb077bd5c74" "checksum memchr 2.1.2 (registry+https://github.com/rust-lang/crates.io-index)" = "db4c41318937f6e76648f42826b1d9ade5c09cafb5aef7e351240a70f39206e9" "checksum num-traits 0.2.6 (registry+https://github.com/rust-lang/crates.io-index)" = "0b3a5d7cc97d6d30d8b9bc8fa19bf45349ffe46241e8816f50f62f6d6aaabee1" "checksum python27-sys 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)" = "56114c37d4dca82526d74009df7782a28c871ac9d36b19d4cb9e67672258527e" "checksum python3-sys 0.2.1 (registry+https://github.com/rust-lang/crates.io-index)" = "61e4aac43f833fd637e429506cb2ac9d7df672c4b68f2eaaa163649b7fdc0444" +"checksum rand 0.6.5 (registry+https://github.com/rust-lang/crates.io-index)" = "6d71dacdc3c88c1fde3885a3be3fbab9f35724e6ce99467f7d9c5026132184ca" +"checksum rand_chacha 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "556d3a1ca6600bfcbab7c7c91ccb085ac7fbbcd70e008a98742e7847f4f7bcef" +"checksum rand_core 0.3.1 (registry+https://github.com/rust-lang/crates.io-index)" = "7a6fdeb83b075e8266dcc8762c22776f6877a63111121f5f8c7411e5be7eed4b" +"checksum rand_core 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "d0e7a549d590831370895ab7ba4ea0c1b6b011d106b5ff2da6eee112615e6dc0" +"checksum rand_hc 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "7b40677c7be09ae76218dc623efbf7b18e34bced3f38883af07bb75630a21bc4" +"checksum rand_isaac 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "ded997c9d5f13925be2a6fd7e66bf1872597f759fd9dd93513dd7e92e5a5ee08" +"checksum rand_jitter 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)" = "080723c6145e37503a2224f801f252e14ac5531cb450f4502698542d188cb3c0" +"checksum rand_os 0.1.2 (registry+https://github.com/rust-lang/crates.io-index)" = "b7c690732391ae0abafced5015ffb53656abfaec61b342290e5eb56b286a679d" +"checksum rand_pcg 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "086bd09a33c7044e56bb44d5bdde5a60e7f119a9e95b0775f545de759a32fe05" +"checksum rand_xorshift 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "cbf7e9e623549b0e21f6e97cf8ecf247c1a8fd2e8a992ae265314300b2455d5c" +"checksum rdrand 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "678054eb77286b51581ba43620cc911abf02758c91f93f479767aed0f90458b2" "checksum regex 1.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "37e7cbbd370869ce2e8dff25c7018702d10b21a20ef7135316f8daecd6c25b7f" "checksum regex-syntax 0.6.4 (registry+https://github.com/rust-lang/crates.io-index)" = "4e47a2ed29da7a9e1960e1639e7a982e6edc6d49be308a3b02daf511504a16d1" +"checksum rustc_version 0.2.3 (registry+https://github.com/rust-lang/crates.io-index)" = "138e3e0acb6c9fb258b19b67cb8abd63c00679d2851805ea151465464fe9030a" +"checksum semver 0.9.0 (registry+https://github.com/rust-lang/crates.io-index)" = "1d7eb9ef2c18661902cc47e535f9bc51b78acd254da71d375c2f6720d9a40403" +"checksum semver-parser 0.7.0 (registry+https://github.com/rust-lang/crates.io-index)" = "388a1df253eca08550bef6c72392cfe7c30914bf41df5269b68cbd6ff8f570a3" "checksum thread_local 0.3.6 (registry+https://github.com/rust-lang/crates.io-index)" = "c6b53e329000edc2b34dbe8545fd20e55a333362d0a321909685a19bd28c3f1b" "checksum ucd-util 0.1.3 (registry+https://github.com/rust-lang/crates.io-index)" = "535c204ee4d8434478593480b8f86ab45ec9aae0e83c568ca81abf0fd0e88f86" "checksum utf8-ranges 1.0.2 (registry+https://github.com/rust-lang/crates.io-index)" = "796f7e48bef87609f7ade7e06495a87d5cd06c7866e6a5cbfceffc558a243737" "checksum version_check 0.1.5 (registry+https://github.com/rust-lang/crates.io-index)" = "914b1a6776c4c929a602fafd8bc742e06365d4bcbe48c30f9cca5824f70dc9dd" +"checksum winapi 0.3.6 (registry+https://github.com/rust-lang/crates.io-index)" = "92c1eb33641e276cfa214a0522acad57be5c56b10cb348b3c5117db75f3ac4b0" +"checksum winapi-i686-pc-windows-gnu 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "ac3b87c63620426dd9b991e5ce0329eff545bccbbb34f3be09ff6fb6ab51b7b6" +"checksum winapi-x86_64-pc-windows-gnu 0.4.0 (registry+https://github.com/rust-lang/crates.io-index)" = "712e227841d057c1ee1cd2fb22fa7e5a5461ae8e48fa2ca79ec42cfc1931183f"
--- a/rust/hg-core/Cargo.toml Tue Feb 12 13:46:38 2019 -0800 +++ b/rust/hg-core/Cargo.toml Sun Dec 02 16:19:22 2018 +0100 @@ -6,3 +6,7 @@ [lib] name = "hg" + +[dev-dependencies] +rand = "*" +rand_pcg = "*"
--- a/rust/hg-core/src/lib.rs Tue Feb 12 13:46:38 2019 -0800 +++ b/rust/hg-core/src/lib.rs Sun Dec 02 16:19:22 2018 +0100 @@ -5,8 +5,7 @@ mod ancestors; pub mod dagops; pub use ancestors::{AncestorsIterator, LazyAncestors, MissingAncestors}; -#[cfg(test)] -pub mod testing; +pub mod testing; // unconditionally built, for use from integration tests /// Mercurial revision numbers ///
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/rust/hg-core/tests/test_missing_ancestors.rs Sun Dec 02 16:19:22 2018 +0100 @@ -0,0 +1,340 @@ +extern crate hg; +extern crate rand; +extern crate rand_pcg; + +use hg::testing::VecGraph; +use hg::Revision; +use hg::*; +use rand::distributions::{Distribution, LogNormal, Uniform}; +use rand::{thread_rng, Rng, RngCore, SeedableRng}; +use std::cmp::min; +use std::collections::HashSet; +use std::env; +use std::fmt::Debug; + +fn build_random_graph( + nodes_opt: Option<usize>, + rootprob_opt: Option<f64>, + mergeprob_opt: Option<f64>, + prevprob_opt: Option<f64>, +) -> VecGraph { + let nodes = nodes_opt.unwrap_or(100); + let rootprob = rootprob_opt.unwrap_or(0.05); + let mergeprob = mergeprob_opt.unwrap_or(0.2); + let prevprob = prevprob_opt.unwrap_or(0.7); + + let mut rng = thread_rng(); + let mut vg: VecGraph = Vec::with_capacity(nodes); + for i in 0..nodes { + if i == 0 || rng.gen_bool(rootprob) { + vg.push([NULL_REVISION, NULL_REVISION]) + } else if i == 1 { + vg.push([0, NULL_REVISION]) + } else if rng.gen_bool(mergeprob) { + let p1 = { + if i == 2 || rng.gen_bool(prevprob) { + (i - 1) as Revision + } else { + rng.gen_range(0, i - 1) as Revision + } + }; + // p2 is a random revision lower than i and different from p1 + let mut p2 = rng.gen_range(0, i - 1) as Revision; + if p2 >= p1 { + p2 = p2 + 1; + } + vg.push([p1, p2]); + } else if rng.gen_bool(prevprob) { + vg.push([(i - 1) as Revision, NULL_REVISION]) + } else { + vg.push([rng.gen_range(0, i - 1) as Revision, NULL_REVISION]) + } + } + vg +} + +/// Compute the ancestors set of all revisions of a VecGraph +fn ancestors_sets(vg: &VecGraph) -> Vec<HashSet<Revision>> { + let mut ancs: Vec<HashSet<Revision>> = Vec::new(); + for i in 0..vg.len() { + let mut ancs_i = HashSet::new(); + ancs_i.insert(i as Revision); + for p in vg[i].iter().cloned() { + if p != NULL_REVISION { + ancs_i.extend(&ancs[p as usize]); + } + } + ancs.push(ancs_i); + } + ancs +} + +#[derive(Clone, Debug)] +enum MissingAncestorsAction { + InitialBases(HashSet<Revision>), + AddBases(HashSet<Revision>), + RemoveAncestorsFrom(HashSet<Revision>), + MissingAncestors(HashSet<Revision>), +} + +/// An instrumented naive yet obviously correct implementation +/// +/// It also records all its actions for easy reproduction for replay +/// of problematic cases +struct NaiveMissingAncestors<'a> { + ancestors_sets: &'a Vec<HashSet<Revision>>, + graph: &'a VecGraph, // used for error reporting only + bases: HashSet<Revision>, + history: Vec<MissingAncestorsAction>, + // for error reporting, assuming we are in a random test + random_seed: String, +} + +impl<'a> NaiveMissingAncestors<'a> { + fn new( + graph: &'a VecGraph, + ancestors_sets: &'a Vec<HashSet<Revision>>, + bases: &HashSet<Revision>, + random_seed: &str, + ) -> Self { + Self { + ancestors_sets: ancestors_sets, + bases: bases.clone(), + graph: graph, + history: vec![MissingAncestorsAction::InitialBases(bases.clone())], + random_seed: random_seed.into(), + } + } + + fn add_bases(&mut self, new_bases: HashSet<Revision>) { + self.bases.extend(&new_bases); + self.history + .push(MissingAncestorsAction::AddBases(new_bases)) + } + + fn remove_ancestors_from(&mut self, revs: &mut HashSet<Revision>) { + revs.remove(&NULL_REVISION); + self.history + .push(MissingAncestorsAction::RemoveAncestorsFrom(revs.clone())); + for base in self.bases.iter().cloned() { + if base != NULL_REVISION { + for rev in &self.ancestors_sets[base as usize] { + revs.remove(&rev); + } + } + } + } + + fn missing_ancestors( + &mut self, + revs: impl IntoIterator<Item = Revision>, + ) -> Vec<Revision> { + let revs_as_set: HashSet<Revision> = revs.into_iter().collect(); + + let mut missing: HashSet<Revision> = HashSet::new(); + for rev in revs_as_set.iter().cloned() { + if rev != NULL_REVISION { + missing.extend(&self.ancestors_sets[rev as usize]) + } + } + self.history + .push(MissingAncestorsAction::MissingAncestors(revs_as_set)); + + for base in self.bases.iter().cloned() { + if base != NULL_REVISION { + for rev in &self.ancestors_sets[base as usize] { + missing.remove(&rev); + } + } + } + let mut res: Vec<Revision> = missing.iter().cloned().collect(); + res.sort(); + res + } + + fn assert_eq<T>(&self, left: T, right: T) + where + T: PartialEq + Debug, + { + if left == right { + return; + } + panic!(format!( + "Equality assertion failed (left != right) + left={:?} + right={:?} + graph={:?} + current bases={:?} + history={:?} + random seed={} + ", + left, + right, + self.graph, + self.bases, + self.history, + self.random_seed, + )); + } +} + +/// Choose a set of random revisions +/// +/// The size of the set is taken from a LogNormal distribution +/// with default mu=1.1 and default sigma=0.8. Quoting the Python +/// test this is taken from: +/// the default mu and sigma give us a nice distribution of mostly +/// single-digit counts (including 0) with some higher ones +/// The sample may include NULL_REVISION +fn sample_revs<R: RngCore>( + rng: &mut R, + maxrev: Revision, + mu_opt: Option<f64>, + sigma_opt: Option<f64>, +) -> HashSet<Revision> { + let mu = mu_opt.unwrap_or(1.1); + let sigma = sigma_opt.unwrap_or(0.8); + + let log_normal = LogNormal::new(mu, sigma); + let nb = min(maxrev as usize, log_normal.sample(rng).floor() as usize); + + let dist = Uniform::from(NULL_REVISION..maxrev); + return rng.sample_iter(&dist).take(nb).collect(); +} + +/// Produces the hexadecimal representation of a slice of bytes +fn hex_bytes(bytes: &[u8]) -> String { + let mut s = String::with_capacity(bytes.len() * 2); + for b in bytes { + s.push_str(&format!("{:x}", b)); + } + s +} + +/// Fill a random seed from its hexadecimal representation. +/// +/// This signature is meant to be consistent with `RngCore::fill_bytes` +fn seed_parse_in(hex: &str, seed: &mut [u8]) { + if hex.len() != 32 { + panic!("Seed {} is too short for 128 bits hex", hex); + } + for i in 0..8 { + seed[i] = u8::from_str_radix(&hex[2 * i..2 * (i + 1)], 16) + .unwrap_or_else(|_e| panic!("Seed {} is not 128 bits hex", hex)); + } +} + +/// Parse the parameters for `test_missing_ancestors()` +/// +/// Returns (graphs, instances, calls per instance) +fn parse_test_missing_ancestors_params(var: &str) -> (usize, usize, usize) { + let err_msg = "TEST_MISSING_ANCESTORS format: GRAPHS,INSTANCES,CALLS"; + let params: Vec<usize> = var + .split(',') + .map(|n| n.trim().parse().expect(err_msg)) + .collect(); + if params.len() != 3 { + panic!(err_msg); + } + (params[0], params[1], params[2]) +} + +#[test] +/// This test creates lots of random VecGraphs, +/// and compare a bunch of MissingAncestors for them with +/// NaiveMissingAncestors that rely on precomputed transitive closures of +/// these VecGraphs (ancestors_sets). +/// +/// For each generater graph, several instances of `MissingAncestors` are +/// created, whose methods are called and checked a given number of times. +/// +/// This test can be parametrized by two environment variables: +/// +/// - TEST_RANDOM_SEED: must be 128 bits in hexadecimal +/// - TEST_MISSING_ANCESTORS: "GRAPHS,INSTANCES,CALLS". The default is +/// "100,10,10" +/// +/// This is slow: it runs on my workstation in about 5 seconds with the +/// default parameters with a plain `cargo --test`. +/// +/// If you want to run it faster, especially if you're changing the +/// parameters, use `cargo test --release`. +/// For me, that gets it down to 0.15 seconds with the default parameters +fn test_missing_ancestors_compare_naive() { + let (graphcount, testcount, inccount) = + match env::var("TEST_MISSING_ANCESTORS") { + Err(env::VarError::NotPresent) => (100, 10, 10), + Ok(val) => parse_test_missing_ancestors_params(&val), + Err(env::VarError::NotUnicode(_)) => { + panic!("TEST_MISSING_ANCESTORS is invalid"); + } + }; + let mut seed: [u8; 16] = [0; 16]; + match env::var("TEST_RANDOM_SEED") { + Ok(val) => { + seed_parse_in(&val, &mut seed); + } + Err(env::VarError::NotPresent) => { + thread_rng().fill_bytes(&mut seed); + } + Err(env::VarError::NotUnicode(_)) => { + panic!("TEST_RANDOM_SEED must be 128 bits in hex"); + } + } + let hex_seed = hex_bytes(&seed); + eprintln!("Random seed: {}", hex_seed); + + let mut rng = rand_pcg::Pcg32::from_seed(seed); + + eprint!("Checking MissingAncestors against brute force implementation "); + eprint!("for {} random graphs, ", graphcount); + eprintln!( + "with {} instances for each and {} calls per instance", + testcount, inccount, + ); + for g in 0..graphcount { + if g != 0 && g % 100 == 0 { + eprintln!("Tested with {} graphs", g); + } + let graph = build_random_graph(None, None, None, None); + let graph_len = graph.len() as Revision; + let ancestors_sets = ancestors_sets(&graph); + for _testno in 0..testcount { + let bases: HashSet<Revision> = + sample_revs(&mut rng, graph_len, None, None); + let mut inc = MissingAncestors::<VecGraph>::new( + graph.clone(), + bases.clone(), + ); + let mut naive = NaiveMissingAncestors::new( + &graph, + &ancestors_sets, + &bases, + &hex_seed, + ); + for _m in 0..inccount { + if rng.gen_bool(0.2) { + let new_bases = + sample_revs(&mut rng, graph_len, None, None); + inc.add_bases(new_bases.iter().cloned()); + naive.add_bases(new_bases); + } + if rng.gen_bool(0.4) { + // larger set so that there are more revs to remove from + let mut hrevs = + sample_revs(&mut rng, graph_len, Some(1.5), None); + let mut rrevs = hrevs.clone(); + inc.remove_ancestors_from(&mut hrevs).unwrap(); + naive.remove_ancestors_from(&mut rrevs); + naive.assert_eq(hrevs, rrevs); + } else { + let revs = sample_revs(&mut rng, graph_len, None, None); + let hm = + inc.missing_ancestors(revs.iter().cloned()).unwrap(); + let rm = naive.missing_ancestors(revs.iter().cloned()); + naive.assert_eq(hm, rm); + } + } + } + } +}