D5417: rust: translated random test of missingancestors

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
15 messages Options
Reply | Threaded
Open this post in threaded view
|

D5417: rust: translated random test of missingancestors

pulkit (Pulkit Goyal)
gracinet created this revision.
Herald added subscribers: mercurial-devel, kevincox, durin42.
Herald added a reviewer: hg-reviewers.

REVISION SUMMARY
  In case of a failed example, all needed information
  for reproduction is included in the panic message,
  so that we don't need to
  seed the random generator explicitely. This is how
  `test_remove_ancestors_from_case1()` has been generated.
 
  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
  - waiting on rust-cpython bindings to be ready or doing the cumbersome direct-ffi (more pollution with unsafe C code)

REPOSITORY
  rHG Mercurial

REVISION DETAIL
  https://phab.mercurial-scm.org/D5417

AFFECTED FILES
  rust/Cargo.lock
  rust/hg-core/Cargo.toml
  rust/hg-core/src/ancestors.rs

CHANGE DETAILS

diff --git a/rust/hg-core/src/ancestors.rs b/rust/hg-core/src/ancestors.rs
--- a/rust/hg-core/src/ancestors.rs
+++ b/rust/hg-core/src/ancestors.rs
@@ -323,6 +323,11 @@
 mod tests {
 
     use super::*;
+    extern crate rand;
+    use self::rand::distributions::{Distribution, LogNormal, Uniform};
+    use self::rand::{thread_rng, Rng, RngCore};
+    use std::cmp::min;
+    use std::fmt::Debug;
     use std::iter::FromIterator;
 
     #[derive(Clone, Debug)]
@@ -621,14 +626,12 @@
         ];
         let problem_rev = 28 as Revision;
         let problem_base = 70 as Revision;
-        // making the problem evident: problem_rev is a parent of problem_base
+        // making the problem obvious: problem_rev is a parent of problem_base
         assert_eq!(graph.parents(problem_base).unwrap()[1], problem_rev);
 
         let mut missanc: MissingAncestors<VecGraph> = MissingAncestors::new(
             graph,
-            [60, 26, 70, 3, 96, 19, 98, 49, 97, 47, 1, 6]
-                .iter()
-                .cloned(),
+            [60, 26, 70, 3, 96, 19, 98, 49, 97, 47, 1, 6].iter().cloned(),
         );
         assert!(missanc.bases.contains(&problem_base));
 
@@ -641,4 +644,249 @@
         assert!(!revs.contains(&problem_rev));
     }
 
+    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>,
+    }
+
+    impl<'a> NaiveMissingAncestors<'a> {
+        fn new(
+            graph: &'a VecGraph,
+            ancestors_sets: &'a Vec<HashSet<Revision>>,
+            bases: &HashSet<Revision>,
+        ) -> Self {
+            Self {
+                ancestors_sets: ancestors_sets,
+                bases: bases.clone(),
+                graph: graph,
+                history: vec![MissingAncestorsAction::InitialBases(
+                    bases.clone(),
+                )],
+            }
+        }
+
+        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<I>(&mut self, revs: I) -> Vec<Revision>
+        where
+            I: IntoIterator<Item = 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={:?}",
+                left, right, self.graph, self.bases, self.history
+            ));
+        }
+    }
+
+    /// 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();
+    }
+
+    #[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).
+    ///
+    /// This is slow: it runs on my workstation in about 5 seconds with the
+    /// default settings.
+    /// 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 = 100;
+        let testcount = 10;
+        let inccount = 10;
+        let mut rng = thread_rng();
+        for _g in 0..graphcount {
+            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,
+                );
+                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);
+                    }
+                }
+            }
+        }
+    }
+
 }
diff --git a/rust/hg-core/Cargo.toml b/rust/hg-core/Cargo.toml
--- a/rust/hg-core/Cargo.toml
+++ b/rust/hg-core/Cargo.toml
@@ -6,3 +6,6 @@
 
 [lib]
 name = "hg"
+
+[dev-dependencies]
+rand = "*"
diff --git a/rust/Cargo.lock b/rust/Cargo.lock
--- a/rust/Cargo.lock
+++ b/rust/Cargo.lock
@@ -7,6 +7,19 @@
 ]
 
 [[package]]
+name = "bitflags"
+version = "1.0.4"
+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.1.0"
 source = "git+https://github.com/indygreg/rust-cpython.git?rev=c90d65cf84abfffce7ef54476bbfed56017a2f52#c90d65cf84abfffce7ef54476bbfed56017a2f52"
@@ -17,8 +30,25 @@
 ]
 
 [[package]]
+name = "fuchsia-zircon"
+version = "0.3.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)",
+ "fuchsia-zircon-sys 0.3.3 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
+name = "fuchsia-zircon-sys"
+version = "0.3.3"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
 name = "hg-core"
 version = "0.1.0"
+dependencies = [
+ "rand 0.6.1 (registry+https://github.com/rust-lang/crates.io-index)",
+]
 
 [[package]]
 name = "hgcli"
@@ -74,6 +104,71 @@
 ]
 
 [[package]]
+name = "rand"
+version = "0.6.1"
+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-zircon 0.3.3 (registry+https://github.com/rust-lang/crates.io-index)",
+ "libc 0.2.35 (registry+https://github.com/rust-lang/crates.io-index)",
+ "rand_chacha 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "rand_core 0.3.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_pcg 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)",
+ "rand_xorshift 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "rustc_version 0.2.3 (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.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "rand_core 0.3.0 (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_core"
+version = "0.3.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.0 (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.0 (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.0 (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.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "rand_core 0.3.0 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
 name = "regex"
 version = "0.1.80"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -91,6 +186,27 @@
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [[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-id"
 version = "2.0.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -118,22 +234,58 @@
 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-build"
 version = "0.1.1"
 source = "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.5.3 (registry+https://github.com/rust-lang/crates.io-index)" = "ca972c2ea5f742bfce5687b9aef75506a764f61d37f8f649047846a9686ddb66"
+"checksum bitflags 1.0.4 (registry+https://github.com/rust-lang/crates.io-index)" = "228047a76f468627ca71776ecdebd732a3423081fcf5125585bcd7c49886ce12"
+"checksum cloudabi 0.0.3 (registry+https://github.com/rust-lang/crates.io-index)" = "ddfc5b9aa5d4507acaf872de71051dfd0e309860e88966e1051e462a077aac4f"
 "checksum cpython 0.1.0 (git+https://github.com/indygreg/rust-cpython.git?rev=c90d65cf84abfffce7ef54476bbfed56017a2f52)" = "<none>"
+"checksum fuchsia-zircon 0.3.3 (registry+https://github.com/rust-lang/crates.io-index)" = "2e9763c69ebaae630ba35f74888db465e49e259ba1bc0eda7d06f4a067615d82"
+"checksum fuchsia-zircon-sys 0.3.3 (registry+https://github.com/rust-lang/crates.io-index)" = "3dcaa9ae7725d12cdb85b3ad99a434db70b468c09ded17e012d86b5c1010f7a7"
 "checksum kernel32-sys 0.2.2 (registry+https://github.com/rust-lang/crates.io-index)" = "7507624b29483431c0ba2d82aece8ca6cdba9382bff4ddd0f7490560c056098d"
 "checksum libc 0.2.35 (registry+https://github.com/rust-lang/crates.io-index)" = "96264e9b293e95d25bfcbbf8a88ffd1aedc85b754eba8b7d78012f638ba220eb"
 "checksum memchr 0.1.11 (registry+https://github.com/rust-lang/crates.io-index)" = "d8b629fb514376c675b98c1421e80b151d3817ac42d7c667717d282761418d20"
 "checksum num-traits 0.1.41 (registry+https://github.com/rust-lang/crates.io-index)" = "cacfcab5eb48250ee7d0c7896b51a2c5eec99c1feea5f32025635f5ae4b00070"
 "checksum python27-sys 0.1.2 (git+https://github.com/indygreg/rust-cpython.git?rev=c90d65cf84abfffce7ef54476bbfed56017a2f52)" = "<none>"
+"checksum rand 0.6.1 (registry+https://github.com/rust-lang/crates.io-index)" = "ae9d223d52ae411a33cf7e54ec6034ec165df296ccd23533d671a28252b6f66a"
+"checksum rand_chacha 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "771b009e3a508cb67e8823dda454aaa5368c7bc1c16829fb77d3e980440dd34a"
+"checksum rand_core 0.3.0 (registry+https://github.com/rust-lang/crates.io-index)" = "0905b6b7079ec73b314d4c748701f6931eb79fd97c668caa3f1899b22b32c6db"
+"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_pcg 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "086bd09a33c7044e56bb44d5bdde5a60e7f119a9e95b0775f545de759a32fe05"
+"checksum rand_xorshift 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "effa3fcaa47e18db002bdde6060944b6d2f9cfd8db471c30e873448ad9187be3"
 "checksum regex 0.1.80 (registry+https://github.com/rust-lang/crates.io-index)" = "4fd4ace6a8cf7860714a2c2280d6c1f7e6a413486c13298bbc86fd3da019402f"
 "checksum regex-syntax 0.3.9 (registry+https://github.com/rust-lang/crates.io-index)" = "f9ec002c35e86791825ed294b50008eea9ddfc8def4420124fbc6b08db834957"
+"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-id 2.0.0 (registry+https://github.com/rust-lang/crates.io-index)" = "a9539db560102d1cef46b8b78ce737ff0bb64e7e18d35b2a5688f7d097d0ff03"
 "checksum thread_local 0.2.7 (registry+https://github.com/rust-lang/crates.io-index)" = "8576dbbfcaef9641452d5cf0df9b0e7eeab7694956dd33bb61515fb8f18cfdd5"
 "checksum utf8-ranges 0.1.3 (registry+https://github.com/rust-lang/crates.io-index)" = "a1ca13c08c41c9c3e04224ed9ff80461d97e121589ff27c753a16cb10830ae0f"
 "checksum winapi 0.2.8 (registry+https://github.com/rust-lang/crates.io-index)" = "167dc9d6949a9b857f3451275e911c3f44255842c1f7a76f33c55103a909087a"
+"checksum winapi 0.3.6 (registry+https://github.com/rust-lang/crates.io-index)" = "92c1eb33641e276cfa214a0522acad57be5c56b10cb348b3c5117db75f3ac4b0"
 "checksum winapi-build 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "2d315eee3b34aca4797b2da6b13ed88266e6d612562a0c46390af8299fc699bc"
+"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"



To: gracinet, #hg-reviewers
Cc: durin42, kevincox, mercurial-devel
_______________________________________________
Mercurial-devel mailing list
[hidden email]
https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
Reply | Threaded
Open this post in threaded view
|

D5417: rust: translated random test of missingancestors

pulkit (Pulkit Goyal)
gracinet updated this revision to Diff 12833.

REPOSITORY
  rHG Mercurial

CHANGES SINCE LAST UPDATE
  https://phab.mercurial-scm.org/D5417?vs=12830&id=12833

REVISION DETAIL
  https://phab.mercurial-scm.org/D5417

AFFECTED FILES
  rust/Cargo.lock
  rust/hg-core/Cargo.toml
  rust/hg-core/src/ancestors.rs

CHANGE DETAILS

diff --git a/rust/hg-core/src/ancestors.rs b/rust/hg-core/src/ancestors.rs
--- a/rust/hg-core/src/ancestors.rs
+++ b/rust/hg-core/src/ancestors.rs
@@ -322,6 +322,11 @@
 mod tests {
 
     use super::*;
+    extern crate rand;
+    use self::rand::distributions::{Distribution, LogNormal, Uniform};
+    use self::rand::{thread_rng, Rng, RngCore};
+    use std::cmp::min;
+    use std::fmt::Debug;
     use std::iter::FromIterator;
 
     #[derive(Clone, Debug)]
@@ -620,14 +625,12 @@
         ];
         let problem_rev = 28 as Revision;
         let problem_base = 70 as Revision;
-        // making the problem evident: problem_rev is a parent of problem_base
+        // making the problem obvious: problem_rev is a parent of problem_base
         assert_eq!(graph.parents(problem_base).unwrap()[1], problem_rev);
 
         let mut missanc: MissingAncestors<VecGraph> = MissingAncestors::new(
             graph,
-            [60, 26, 70, 3, 96, 19, 98, 49, 97, 47, 1, 6]
-                .iter()
-                .cloned(),
+            [60, 26, 70, 3, 96, 19, 98, 49, 97, 47, 1, 6].iter().cloned(),
         );
         assert!(missanc.bases.contains(&problem_base));
 
@@ -640,4 +643,249 @@
         assert!(!revs.contains(&problem_rev));
     }
 
+    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>,
+    }
+
+    impl<'a> NaiveMissingAncestors<'a> {
+        fn new(
+            graph: &'a VecGraph,
+            ancestors_sets: &'a Vec<HashSet<Revision>>,
+            bases: &HashSet<Revision>,
+        ) -> Self {
+            Self {
+                ancestors_sets: ancestors_sets,
+                bases: bases.clone(),
+                graph: graph,
+                history: vec![MissingAncestorsAction::InitialBases(
+                    bases.clone(),
+                )],
+            }
+        }
+
+        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<I>(&mut self, revs: I) -> Vec<Revision>
+        where
+            I: IntoIterator<Item = 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={:?}",
+                left, right, self.graph, self.bases, self.history
+            ));
+        }
+    }
+
+    /// 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();
+    }
+
+    #[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).
+    ///
+    /// This is slow: it runs on my workstation in about 5 seconds with the
+    /// default settings.
+    /// 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 = 100;
+        let testcount = 10;
+        let inccount = 10;
+        let mut rng = thread_rng();
+        for _g in 0..graphcount {
+            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,
+                );
+                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);
+                    }
+                }
+            }
+        }
+    }
+
 }
diff --git a/rust/hg-core/Cargo.toml b/rust/hg-core/Cargo.toml
--- a/rust/hg-core/Cargo.toml
+++ b/rust/hg-core/Cargo.toml
@@ -6,3 +6,6 @@
 
 [lib]
 name = "hg"
+
+[dev-dependencies]
+rand = "*"
diff --git a/rust/Cargo.lock b/rust/Cargo.lock
--- a/rust/Cargo.lock
+++ b/rust/Cargo.lock
@@ -7,6 +7,19 @@
 ]
 
 [[package]]
+name = "bitflags"
+version = "1.0.4"
+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.1.0"
 source = "git+https://github.com/indygreg/rust-cpython.git?rev=c90d65cf84abfffce7ef54476bbfed56017a2f52#c90d65cf84abfffce7ef54476bbfed56017a2f52"
@@ -17,8 +30,25 @@
 ]
 
 [[package]]
+name = "fuchsia-zircon"
+version = "0.3.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)",
+ "fuchsia-zircon-sys 0.3.3 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
+name = "fuchsia-zircon-sys"
+version = "0.3.3"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
 name = "hg-core"
 version = "0.1.0"
+dependencies = [
+ "rand 0.6.1 (registry+https://github.com/rust-lang/crates.io-index)",
+]
 
 [[package]]
 name = "hgcli"
@@ -74,6 +104,71 @@
 ]
 
 [[package]]
+name = "rand"
+version = "0.6.1"
+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-zircon 0.3.3 (registry+https://github.com/rust-lang/crates.io-index)",
+ "libc 0.2.35 (registry+https://github.com/rust-lang/crates.io-index)",
+ "rand_chacha 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "rand_core 0.3.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_pcg 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)",
+ "rand_xorshift 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "rustc_version 0.2.3 (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.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "rand_core 0.3.0 (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_core"
+version = "0.3.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.0 (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.0 (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.0 (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.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "rand_core 0.3.0 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
 name = "regex"
 version = "0.1.80"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -91,6 +186,27 @@
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [[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-id"
 version = "2.0.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -118,22 +234,58 @@
 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-build"
 version = "0.1.1"
 source = "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.5.3 (registry+https://github.com/rust-lang/crates.io-index)" = "ca972c2ea5f742bfce5687b9aef75506a764f61d37f8f649047846a9686ddb66"
+"checksum bitflags 1.0.4 (registry+https://github.com/rust-lang/crates.io-index)" = "228047a76f468627ca71776ecdebd732a3423081fcf5125585bcd7c49886ce12"
+"checksum cloudabi 0.0.3 (registry+https://github.com/rust-lang/crates.io-index)" = "ddfc5b9aa5d4507acaf872de71051dfd0e309860e88966e1051e462a077aac4f"
 "checksum cpython 0.1.0 (git+https://github.com/indygreg/rust-cpython.git?rev=c90d65cf84abfffce7ef54476bbfed56017a2f52)" = "<none>"
+"checksum fuchsia-zircon 0.3.3 (registry+https://github.com/rust-lang/crates.io-index)" = "2e9763c69ebaae630ba35f74888db465e49e259ba1bc0eda7d06f4a067615d82"
+"checksum fuchsia-zircon-sys 0.3.3 (registry+https://github.com/rust-lang/crates.io-index)" = "3dcaa9ae7725d12cdb85b3ad99a434db70b468c09ded17e012d86b5c1010f7a7"
 "checksum kernel32-sys 0.2.2 (registry+https://github.com/rust-lang/crates.io-index)" = "7507624b29483431c0ba2d82aece8ca6cdba9382bff4ddd0f7490560c056098d"
 "checksum libc 0.2.35 (registry+https://github.com/rust-lang/crates.io-index)" = "96264e9b293e95d25bfcbbf8a88ffd1aedc85b754eba8b7d78012f638ba220eb"
 "checksum memchr 0.1.11 (registry+https://github.com/rust-lang/crates.io-index)" = "d8b629fb514376c675b98c1421e80b151d3817ac42d7c667717d282761418d20"
 "checksum num-traits 0.1.41 (registry+https://github.com/rust-lang/crates.io-index)" = "cacfcab5eb48250ee7d0c7896b51a2c5eec99c1feea5f32025635f5ae4b00070"
 "checksum python27-sys 0.1.2 (git+https://github.com/indygreg/rust-cpython.git?rev=c90d65cf84abfffce7ef54476bbfed56017a2f52)" = "<none>"
+"checksum rand 0.6.1 (registry+https://github.com/rust-lang/crates.io-index)" = "ae9d223d52ae411a33cf7e54ec6034ec165df296ccd23533d671a28252b6f66a"
+"checksum rand_chacha 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "771b009e3a508cb67e8823dda454aaa5368c7bc1c16829fb77d3e980440dd34a"
+"checksum rand_core 0.3.0 (registry+https://github.com/rust-lang/crates.io-index)" = "0905b6b7079ec73b314d4c748701f6931eb79fd97c668caa3f1899b22b32c6db"
+"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_pcg 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "086bd09a33c7044e56bb44d5bdde5a60e7f119a9e95b0775f545de759a32fe05"
+"checksum rand_xorshift 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "effa3fcaa47e18db002bdde6060944b6d2f9cfd8db471c30e873448ad9187be3"
 "checksum regex 0.1.80 (registry+https://github.com/rust-lang/crates.io-index)" = "4fd4ace6a8cf7860714a2c2280d6c1f7e6a413486c13298bbc86fd3da019402f"
 "checksum regex-syntax 0.3.9 (registry+https://github.com/rust-lang/crates.io-index)" = "f9ec002c35e86791825ed294b50008eea9ddfc8def4420124fbc6b08db834957"
+"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-id 2.0.0 (registry+https://github.com/rust-lang/crates.io-index)" = "a9539db560102d1cef46b8b78ce737ff0bb64e7e18d35b2a5688f7d097d0ff03"
 "checksum thread_local 0.2.7 (registry+https://github.com/rust-lang/crates.io-index)" = "8576dbbfcaef9641452d5cf0df9b0e7eeab7694956dd33bb61515fb8f18cfdd5"
 "checksum utf8-ranges 0.1.3 (registry+https://github.com/rust-lang/crates.io-index)" = "a1ca13c08c41c9c3e04224ed9ff80461d97e121589ff27c753a16cb10830ae0f"
 "checksum winapi 0.2.8 (registry+https://github.com/rust-lang/crates.io-index)" = "167dc9d6949a9b857f3451275e911c3f44255842c1f7a76f33c55103a909087a"
+"checksum winapi 0.3.6 (registry+https://github.com/rust-lang/crates.io-index)" = "92c1eb33641e276cfa214a0522acad57be5c56b10cb348b3c5117db75f3ac4b0"
 "checksum winapi-build 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "2d315eee3b34aca4797b2da6b13ed88266e6d612562a0c46390af8299fc699bc"
+"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"



To: gracinet, #hg-reviewers
Cc: durin42, kevincox, mercurial-devel
_______________________________________________
Mercurial-devel mailing list
[hidden email]
https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
Reply | Threaded
Open this post in threaded view
|

D5417: rust: translated random test of missingancestors

pulkit (Pulkit Goyal)
In reply to this post by pulkit (Pulkit Goyal)
gracinet updated this revision to Diff 12856.

REPOSITORY
  rHG Mercurial

CHANGES SINCE LAST UPDATE
  https://phab.mercurial-scm.org/D5417?vs=12833&id=12856

REVISION DETAIL
  https://phab.mercurial-scm.org/D5417

AFFECTED FILES
  rust/Cargo.lock
  rust/hg-core/Cargo.toml
  rust/hg-core/src/ancestors.rs

CHANGE DETAILS

diff --git a/rust/hg-core/src/ancestors.rs b/rust/hg-core/src/ancestors.rs
--- a/rust/hg-core/src/ancestors.rs
+++ b/rust/hg-core/src/ancestors.rs
@@ -318,6 +318,11 @@
 mod tests {
 
     use super::*;
+    extern crate rand;
+    use self::rand::distributions::{Distribution, LogNormal, Uniform};
+    use self::rand::{thread_rng, Rng, RngCore};
+    use std::cmp::min;
+    use std::fmt::Debug;
     use std::iter::FromIterator;
 
     #[derive(Clone, Debug)]
@@ -643,4 +648,249 @@
         assert!(!revs.contains(&problem_rev));
     }
 
+    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>,
+    }
+
+    impl<'a> NaiveMissingAncestors<'a> {
+        fn new(
+            graph: &'a VecGraph,
+            ancestors_sets: &'a Vec<HashSet<Revision>>,
+            bases: &HashSet<Revision>,
+        ) -> Self {
+            Self {
+                ancestors_sets: ancestors_sets,
+                bases: bases.clone(),
+                graph: graph,
+                history: vec![MissingAncestorsAction::InitialBases(
+                    bases.clone(),
+                )],
+            }
+        }
+
+        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.iter().cloned() {
+                if rev != NULL_REVISION {
+                    missing.extend(&self.ancestors_sets[rev as usize])
+                }
+            }
+            self.history
+                .push(MissingAncestorsAction::MissingAncestors(revs));
+
+            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={:?}",
+                left, right, self.graph, self.bases, self.history
+            ));
+        }
+    }
+
+    /// 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();
+    }
+
+    #[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).
+    ///
+    /// This is slow: it runs on my workstation in about 5 seconds with the
+    /// default settings.
+    /// 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 = 100;
+        let testcount = 10;
+        let inccount = 10;
+        let mut rng = thread_rng();
+        for _g in 0..graphcount {
+            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,
+                );
+                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);
+                    }
+                }
+            }
+        }
+    }
+
 }
diff --git a/rust/hg-core/Cargo.toml b/rust/hg-core/Cargo.toml
--- a/rust/hg-core/Cargo.toml
+++ b/rust/hg-core/Cargo.toml
@@ -6,3 +6,6 @@
 
 [lib]
 name = "hg"
+
+[dev-dependencies]
+rand = "*"
diff --git a/rust/Cargo.lock b/rust/Cargo.lock
--- a/rust/Cargo.lock
+++ b/rust/Cargo.lock
@@ -7,6 +7,19 @@
 ]
 
 [[package]]
+name = "bitflags"
+version = "1.0.4"
+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.1.0"
 source = "git+https://github.com/indygreg/rust-cpython.git?rev=c90d65cf84abfffce7ef54476bbfed56017a2f52#c90d65cf84abfffce7ef54476bbfed56017a2f52"
@@ -17,8 +30,25 @@
 ]
 
 [[package]]
+name = "fuchsia-zircon"
+version = "0.3.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)",
+ "fuchsia-zircon-sys 0.3.3 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
+name = "fuchsia-zircon-sys"
+version = "0.3.3"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+
+[[package]]
 name = "hg-core"
 version = "0.1.0"
+dependencies = [
+ "rand 0.6.1 (registry+https://github.com/rust-lang/crates.io-index)",
+]
 
 [[package]]
 name = "hgcli"
@@ -74,6 +104,71 @@
 ]
 
 [[package]]
+name = "rand"
+version = "0.6.1"
+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-zircon 0.3.3 (registry+https://github.com/rust-lang/crates.io-index)",
+ "libc 0.2.35 (registry+https://github.com/rust-lang/crates.io-index)",
+ "rand_chacha 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "rand_core 0.3.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_pcg 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)",
+ "rand_xorshift 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)",
+ "rustc_version 0.2.3 (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.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "rand_core 0.3.0 (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_core"
+version = "0.3.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.0 (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.0 (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.0 (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.0"
+source = "registry+https://github.com/rust-lang/crates.io-index"
+dependencies = [
+ "rand_core 0.3.0 (registry+https://github.com/rust-lang/crates.io-index)",
+]
+
+[[package]]
 name = "regex"
 version = "0.1.80"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -91,6 +186,27 @@
 source = "registry+https://github.com/rust-lang/crates.io-index"
 
 [[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-id"
 version = "2.0.0"
 source = "registry+https://github.com/rust-lang/crates.io-index"
@@ -118,22 +234,58 @@
 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-build"
 version = "0.1.1"
 source = "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.5.3 (registry+https://github.com/rust-lang/crates.io-index)" = "ca972c2ea5f742bfce5687b9aef75506a764f61d37f8f649047846a9686ddb66"
+"checksum bitflags 1.0.4 (registry+https://github.com/rust-lang/crates.io-index)" = "228047a76f468627ca71776ecdebd732a3423081fcf5125585bcd7c49886ce12"
+"checksum cloudabi 0.0.3 (registry+https://github.com/rust-lang/crates.io-index)" = "ddfc5b9aa5d4507acaf872de71051dfd0e309860e88966e1051e462a077aac4f"
 "checksum cpython 0.1.0 (git+https://github.com/indygreg/rust-cpython.git?rev=c90d65cf84abfffce7ef54476bbfed56017a2f52)" = "<none>"
+"checksum fuchsia-zircon 0.3.3 (registry+https://github.com/rust-lang/crates.io-index)" = "2e9763c69ebaae630ba35f74888db465e49e259ba1bc0eda7d06f4a067615d82"
+"checksum fuchsia-zircon-sys 0.3.3 (registry+https://github.com/rust-lang/crates.io-index)" = "3dcaa9ae7725d12cdb85b3ad99a434db70b468c09ded17e012d86b5c1010f7a7"
 "checksum kernel32-sys 0.2.2 (registry+https://github.com/rust-lang/crates.io-index)" = "7507624b29483431c0ba2d82aece8ca6cdba9382bff4ddd0f7490560c056098d"
 "checksum libc 0.2.35 (registry+https://github.com/rust-lang/crates.io-index)" = "96264e9b293e95d25bfcbbf8a88ffd1aedc85b754eba8b7d78012f638ba220eb"
 "checksum memchr 0.1.11 (registry+https://github.com/rust-lang/crates.io-index)" = "d8b629fb514376c675b98c1421e80b151d3817ac42d7c667717d282761418d20"
 "checksum num-traits 0.1.41 (registry+https://github.com/rust-lang/crates.io-index)" = "cacfcab5eb48250ee7d0c7896b51a2c5eec99c1feea5f32025635f5ae4b00070"
 "checksum python27-sys 0.1.2 (git+https://github.com/indygreg/rust-cpython.git?rev=c90d65cf84abfffce7ef54476bbfed56017a2f52)" = "<none>"
+"checksum rand 0.6.1 (registry+https://github.com/rust-lang/crates.io-index)" = "ae9d223d52ae411a33cf7e54ec6034ec165df296ccd23533d671a28252b6f66a"
+"checksum rand_chacha 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "771b009e3a508cb67e8823dda454aaa5368c7bc1c16829fb77d3e980440dd34a"
+"checksum rand_core 0.3.0 (registry+https://github.com/rust-lang/crates.io-index)" = "0905b6b7079ec73b314d4c748701f6931eb79fd97c668caa3f1899b22b32c6db"
+"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_pcg 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "086bd09a33c7044e56bb44d5bdde5a60e7f119a9e95b0775f545de759a32fe05"
+"checksum rand_xorshift 0.1.0 (registry+https://github.com/rust-lang/crates.io-index)" = "effa3fcaa47e18db002bdde6060944b6d2f9cfd8db471c30e873448ad9187be3"
 "checksum regex 0.1.80 (registry+https://github.com/rust-lang/crates.io-index)" = "4fd4ace6a8cf7860714a2c2280d6c1f7e6a413486c13298bbc86fd3da019402f"
 "checksum regex-syntax 0.3.9 (registry+https://github.com/rust-lang/crates.io-index)" = "f9ec002c35e86791825ed294b50008eea9ddfc8def4420124fbc6b08db834957"
+"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-id 2.0.0 (registry+https://github.com/rust-lang/crates.io-index)" = "a9539db560102d1cef46b8b78ce737ff0bb64e7e18d35b2a5688f7d097d0ff03"
 "checksum thread_local 0.2.7 (registry+https://github.com/rust-lang/crates.io-index)" = "8576dbbfcaef9641452d5cf0df9b0e7eeab7694956dd33bb61515fb8f18cfdd5"
 "checksum utf8-ranges 0.1.3 (registry+https://github.com/rust-lang/crates.io-index)" = "a1ca13c08c41c9c3e04224ed9ff80461d97e121589ff27c753a16cb10830ae0f"
 "checksum winapi 0.2.8 (registry+https://github.com/rust-lang/crates.io-index)" = "167dc9d6949a9b857f3451275e911c3f44255842c1f7a76f33c55103a909087a"
+"checksum winapi 0.3.6 (registry+https://github.com/rust-lang/crates.io-index)" = "92c1eb33641e276cfa214a0522acad57be5c56b10cb348b3c5117db75f3ac4b0"
 "checksum winapi-build 0.1.1 (registry+https://github.com/rust-lang/crates.io-index)" = "2d315eee3b34aca4797b2da6b13ed88266e6d612562a0c46390af8299fc699bc"
+"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"



To: gracinet, #hg-reviewers
Cc: durin42, kevincox, mercurial-devel
_______________________________________________
Mercurial-devel mailing list
[hidden email]
https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
Reply | Threaded
Open this post in threaded view
|

Re: D5417: rust: translated random test of missingancestors

Yuya Nishihara
In reply to this post by pulkit (Pulkit Goyal)
>   In case of a failed example, all needed information
>   for reproduction is included in the panic message,
>   so that we don't need to
>   seed the random generator explicitely. This is how
>   `test_remove_ancestors_from_case1()` has been generated.

Can we turn this into a utility command? I don't think it's good idea to
include random data in module tests. We'll probably want to loop it over
various seeds to find interesting graphs.
_______________________________________________
Mercurial-devel mailing list
[hidden email]
https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
Reply | Threaded
Open this post in threaded view
|

D5417: rust: translated random test of missingancestors

pulkit (Pulkit Goyal)
yuja added a comment.


  >   In case of a failed example, all needed information
  >   for reproduction is included in the panic message,
  >   so that we don't need to
  >   seed the random generator explicitely. This is how
  >   `test_remove_ancestors_from_case1()` has been generated.
 
  Can we turn this into a utility command? I don't think it's good idea to
  include random data in module tests. We'll probably want to loop it over
  various seeds to find interesting graphs.

REPOSITORY
  rHG Mercurial

REVISION DETAIL
  https://phab.mercurial-scm.org/D5417

To: gracinet, #hg-reviewers
Cc: yuja, durin42, kevincox, mercurial-devel
_______________________________________________
Mercurial-devel mailing list
[hidden email]
https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
Reply | Threaded
Open this post in threaded view
|

D5417: rust: translated random test of missingancestors

pulkit (Pulkit Goyal)
In reply to this post by pulkit (Pulkit Goyal)
gracinet added a comment.


  @yuja: I'll look into it, maybe that's a case for benches (I've not played with them yet).

REPOSITORY
  rHG Mercurial

REVISION DETAIL
  https://phab.mercurial-scm.org/D5417

To: gracinet, #hg-reviewers
Cc: yuja, durin42, kevincox, mercurial-devel
_______________________________________________
Mercurial-devel mailing list
[hidden email]
https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
Reply | Threaded
Open this post in threaded view
|

D5417: rust: translated random test of missingancestors

pulkit (Pulkit Goyal)
In reply to this post by pulkit (Pulkit Goyal)
gracinet added a comment.


  @yuja now that 4.9 is out, I'm getting back to this.
 
  This test is useful for me, because it's the only one that really tests the corectness of MissingAncestor, and it's not a bench either.
  I agree it feels out of place in  with the unit tests, so my proposal is to make an integration test out of it.
 
  If we don't want to run it, we can do `cargo test --lib`, and in any case `cargo test` does not run integration tests (nor doctests) if the unit tests fail.

REPOSITORY
  rHG Mercurial

REVISION DETAIL
  https://phab.mercurial-scm.org/D5417

To: gracinet, #hg-reviewers
Cc: yuja, durin42, kevincox, mercurial-devel
_______________________________________________
Mercurial-devel mailing list
[hidden email]
https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
Reply | Threaded
Open this post in threaded view
|

Re: D5417: rust: translated random test of missingancestors

Yuya Nishihara
>   This test is useful for me, because it's the only one that really tests the corectness of MissingAncestor, and it's not a bench either.
>   I agree it feels out of place in  with the unit tests, so my proposal is to make an integration test out of it.

or examples/ to build a dev-only standalone executable?

I don't know which is better, but I think we'll need a way to get around
the randomness (e.g. pass in a static random seed to reproduce a failed
example.)
_______________________________________________
Mercurial-devel mailing list
[hidden email]
https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
Reply | Threaded
Open this post in threaded view
|

D5417: rust: translated random test of missingancestors

pulkit (Pulkit Goyal)
yuja added a comment.


  >   This test is useful for me, because it's the only one that really tests the corectness of MissingAncestor, and it's not a bench either.
  >   I agree it feels out of place in  with the unit tests, so my proposal is to make an integration test out of it.
 
  or examples/ to build a dev-only standalone executable?
 
  I don't know which is better, but I think we'll need a way to get around
  the randomness (e.g. pass in a static random seed to reproduce a failed
  example.)

REPOSITORY
  rHG Mercurial

REVISION DETAIL
  https://phab.mercurial-scm.org/D5417

To: gracinet, #hg-reviewers
Cc: yuja, durin42, kevincox, mercurial-devel
_______________________________________________
Mercurial-devel mailing list
[hidden email]
https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
Reply | Threaded
Open this post in threaded view
|

D5417: rust: translated random test of missingancestors

pulkit (Pulkit Goyal)
In reply to this post by pulkit (Pulkit Goyal)
gracinet added a comment.


  @yuja we don't need a seed to reproduce: failed examples contain all the information (that's a difference with the Python version)

REPOSITORY
  rHG Mercurial

REVISION DETAIL
  https://phab.mercurial-scm.org/D5417

To: gracinet, #hg-reviewers
Cc: yuja, durin42, kevincox, mercurial-devel
_______________________________________________
Mercurial-devel mailing list
[hidden email]
https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
Reply | Threaded
Open this post in threaded view
|

Re: D5417: rust: translated random test of missingancestors

Yuya Nishihara
>   @yuja we don't need a seed to reproduce: failed examples contain all the information (that's a difference with the Python version)

Yes, but isn't it handy if we can run the same test with some debugging aids?

I didn't carefully look through the original patch, so maybe I miss the point.
But IIRC, this test had some parameters we would probably want to tune. The
random seed is just an example.
_______________________________________________
Mercurial-devel mailing list
[hidden email]
https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
Reply | Threaded
Open this post in threaded view
|

D5417: rust: translated random test of missingancestors

pulkit (Pulkit Goyal)
yuja added a comment.


  >   @yuja we don't need a seed to reproduce: failed examples contain all the information (that's a difference with the Python version)
 
  Yes, but isn't it handy if we can run the same test with some debugging aids?
 
  I didn't carefully look through the original patch, so maybe I miss the point.
  But IIRC, this test had some parameters we would probably want to tune. The
  random seed is just an example.

REPOSITORY
  rHG Mercurial

REVISION DETAIL
  https://phab.mercurial-scm.org/D5417

To: gracinet, #hg-reviewers
Cc: yuja, durin42, kevincox, mercurial-devel
_______________________________________________
Mercurial-devel mailing list
[hidden email]
https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
Reply | Threaded
Open this post in threaded view
|

D5417: rust: translated random test of missingancestors

pulkit (Pulkit Goyal)
In reply to this post by pulkit (Pulkit Goyal)
gracinet updated this revision to Diff 14044.
gracinet edited the summary of this revision.

REPOSITORY
  rHG Mercurial

CHANGES SINCE LAST UPDATE
  https://phab.mercurial-scm.org/D5417?vs=12856&id=14044

REVISION DETAIL
  https://phab.mercurial-scm.org/D5417

AFFECTED FILES
  rust/Cargo.lock
  rust/hg-core/Cargo.toml
  rust/hg-core/src/lib.rs
  rust/hg-core/tests/test_missing_ancestors.rs

CHANGE DETAILS

diff --git a/rust/hg-core/tests/test_missing_ancestors.rs b/rust/hg-core/tests/test_missing_ancestors.rs
new file mode 100644
--- /dev/null
+++ b/rust/hg-core/tests/test_missing_ancestors.rs
@@ -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);
+                }
+            }
+        }
+    }
+}
diff --git a/rust/hg-core/src/lib.rs b/rust/hg-core/src/lib.rs
--- a/rust/hg-core/src/lib.rs
+++ b/rust/hg-core/src/lib.rs
@@ -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 --git a/rust/hg-core/Cargo.toml b/rust/hg-core/Cargo.toml
--- a/rust/hg-core/Cargo.toml
+++ b/rust/hg-core/Cargo.toml
@@ -6,3 +6,7 @@
 
 [lib]
 name = "hg"
+
+[dev-dependencies]
+rand = "*"
+rand_pcg = "*"
diff --git a/rust/Cargo.lock b/rust/Cargo.lock
--- a/rust/Cargo.lock
+++ b/rust/Cargo.lock
@@ -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"



To: gracinet, #hg-reviewers
Cc: yuja, durin42, kevincox, mercurial-devel
_______________________________________________
Mercurial-devel mailing list
[hidden email]
https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
Reply | Threaded
Open this post in threaded view
|

D5417: rust: translated random test of missingancestors

pulkit (Pulkit Goyal)
In reply to this post by pulkit (Pulkit Goyal)
gracinet added a comment.


  @yuja I'm trying to find a compromise between our points of view : I'd like very much it to be run automatically (hence an integration test), and you want to be parametrizable. So, I'm pushing a version that has these two properties, working with env variables, since command-line arguments are already used by the testing framework. Hope it'll suit you, if it doesn't, I'll put it in examples and find a way to run it anyway

REPOSITORY
  rHG Mercurial

REVISION DETAIL
  https://phab.mercurial-scm.org/D5417

To: gracinet, #hg-reviewers
Cc: yuja, durin42, kevincox, mercurial-devel
_______________________________________________
Mercurial-devel mailing list
[hidden email]
https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
Reply | Threaded
Open this post in threaded view
|

D5417: rust: translated random test of missingancestors

pulkit (Pulkit Goyal)
In reply to this post by pulkit (Pulkit Goyal)
This revision was automatically updated to reflect the committed changes.
Closed by commit rHG9370f4843084: rust: translated random test of missingancestors (authored by gracinet, committed by ).

REPOSITORY
  rHG Mercurial

CHANGES SINCE LAST UPDATE
  https://phab.mercurial-scm.org/D5417?vs=14044&id=14067

REVISION DETAIL
  https://phab.mercurial-scm.org/D5417

AFFECTED FILES
  rust/Cargo.lock
  rust/hg-core/Cargo.toml
  rust/hg-core/src/lib.rs
  rust/hg-core/tests/test_missing_ancestors.rs

CHANGE DETAILS

diff --git a/rust/hg-core/tests/test_missing_ancestors.rs b/rust/hg-core/tests/test_missing_ancestors.rs
new file mode 100644
--- /dev/null
+++ b/rust/hg-core/tests/test_missing_ancestors.rs
@@ -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);
+                }
+            }
+        }
+    }
+}
diff --git a/rust/hg-core/src/lib.rs b/rust/hg-core/src/lib.rs
--- a/rust/hg-core/src/lib.rs
+++ b/rust/hg-core/src/lib.rs
@@ -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 --git a/rust/hg-core/Cargo.toml b/rust/hg-core/Cargo.toml
--- a/rust/hg-core/Cargo.toml
+++ b/rust/hg-core/Cargo.toml
@@ -6,3 +6,7 @@
 
 [lib]
 name = "hg"
+
+[dev-dependencies]
+rand = "*"
+rand_pcg = "*"
diff --git a/rust/Cargo.lock b/rust/Cargo.lock
--- a/rust/Cargo.lock
+++ b/rust/Cargo.lock
@@ -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"



To: gracinet, #hg-reviewers
Cc: yuja, durin42, kevincox, mercurial-devel
_______________________________________________
Mercurial-devel mailing list
[hidden email]
https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel