Patchwork D5417: rust: translated random test of missingancestors

login
register
mail settings
Submitter phabricator
Date Dec. 12, 2018, 4:26 p.m.
Message ID <5a2446c8b176e94a16fb1123f8a592e1@localhost.localdomain>
Download mbox | patch
Permalink /patch/37128/
State Not Applicable
Headers show

Comments

phabricator - Dec. 12, 2018, 4:26 p.m.
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




To: gracinet, #hg-reviewers
Cc: durin42, kevincox, mercurial-devel

Patch

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"