# HG changeset patch # User Georges Racinet # Date 1543763962 -3600 # Node ID ee7b7bd432a16653856d969026c514d35a3506aa # Parent 09814946cc6aefab1545ef045f9adfbeb02ba647 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 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 diff -r 09814946cc6a -r ee7b7bd432a1 rust/Cargo.lock --- 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" diff -r 09814946cc6a -r ee7b7bd432a1 rust/hg-core/Cargo.toml --- 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 = "*" diff -r 09814946cc6a -r ee7b7bd432a1 rust/hg-core/src/lib.rs --- 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 /// diff -r 09814946cc6a -r ee7b7bd432a1 rust/hg-core/tests/test_missing_ancestors.rs --- /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, + rootprob_opt: Option, + mergeprob_opt: Option, + prevprob_opt: Option, +) -> 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> { + let mut ancs: Vec> = 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), + AddBases(HashSet), + RemoveAncestorsFrom(HashSet), + MissingAncestors(HashSet), +} + +/// 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>, + graph: &'a VecGraph, // used for error reporting only + bases: HashSet, + history: Vec, + // 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>, + bases: &HashSet, + 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) { + self.bases.extend(&new_bases); + self.history + .push(MissingAncestorsAction::AddBases(new_bases)) + } + + fn remove_ancestors_from(&mut self, revs: &mut HashSet) { + 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, + ) -> Vec { + let revs_as_set: HashSet = revs.into_iter().collect(); + + let mut missing: HashSet = 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 = missing.iter().cloned().collect(); + res.sort(); + res + } + + fn assert_eq(&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( + rng: &mut R, + maxrev: Revision, + mu_opt: Option, + sigma_opt: Option, +) -> HashSet { + 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 = 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 = + sample_revs(&mut rng, graph_len, None, None); + let mut inc = MissingAncestors::::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); + } + } + } + } +}