Mercurial > hg
annotate rust/hg-core/tests/test_missing_ancestors.rs @ 41692:ee7b7bd432a1
rust: translated random test of missingancestors
This is a Rust implementation of the random
DAG generator and related incrementalmissingancestors
tests against a naive brute force implementation.
It is provided as an integration test, so that it
won't run by default if any unit test fails.
In case of a failed example, all needed information
for reproduction is included in the panic message,
(this is how
`test_remove_ancestors_from_case1()` has been generated),
as well as the random seed.
The whole test is rerunnable by passing the random seed
in the TEST_RANDOM_SEED environment variable.
The other parameters (numbers of iterations) can be passed
in the TEST_MISSING_ANCESTORS environment variable.
An alternative would have been to expose to Python
MissingAncestors<VecGraphs> but that would have meant
pollution of the release build used from Python,
whereas we do it in this changeset within the tests submodule
Differential Revision: https://phab.mercurial-scm.org/D5417
author | Georges Racinet <gracinet@anybox.fr> |
---|---|
date | Sun, 02 Dec 2018 16:19:22 +0100 |
parents | |
children | 326fdce22fb2 |
rev | line source |
---|---|
41692
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
1 extern crate hg; |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
2 extern crate rand; |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
3 extern crate rand_pcg; |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
4 |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
5 use hg::testing::VecGraph; |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
6 use hg::Revision; |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
7 use hg::*; |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
8 use rand::distributions::{Distribution, LogNormal, Uniform}; |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
9 use rand::{thread_rng, Rng, RngCore, SeedableRng}; |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
10 use std::cmp::min; |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
11 use std::collections::HashSet; |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
12 use std::env; |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
13 use std::fmt::Debug; |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
14 |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
15 fn build_random_graph( |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
16 nodes_opt: Option<usize>, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
17 rootprob_opt: Option<f64>, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
18 mergeprob_opt: Option<f64>, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
19 prevprob_opt: Option<f64>, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
20 ) -> VecGraph { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
21 let nodes = nodes_opt.unwrap_or(100); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
22 let rootprob = rootprob_opt.unwrap_or(0.05); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
23 let mergeprob = mergeprob_opt.unwrap_or(0.2); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
24 let prevprob = prevprob_opt.unwrap_or(0.7); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
25 |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
26 let mut rng = thread_rng(); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
27 let mut vg: VecGraph = Vec::with_capacity(nodes); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
28 for i in 0..nodes { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
29 if i == 0 || rng.gen_bool(rootprob) { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
30 vg.push([NULL_REVISION, NULL_REVISION]) |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
31 } else if i == 1 { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
32 vg.push([0, NULL_REVISION]) |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
33 } else if rng.gen_bool(mergeprob) { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
34 let p1 = { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
35 if i == 2 || rng.gen_bool(prevprob) { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
36 (i - 1) as Revision |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
37 } else { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
38 rng.gen_range(0, i - 1) as Revision |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
39 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
40 }; |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
41 // p2 is a random revision lower than i and different from p1 |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
42 let mut p2 = rng.gen_range(0, i - 1) as Revision; |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
43 if p2 >= p1 { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
44 p2 = p2 + 1; |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
45 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
46 vg.push([p1, p2]); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
47 } else if rng.gen_bool(prevprob) { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
48 vg.push([(i - 1) as Revision, NULL_REVISION]) |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
49 } else { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
50 vg.push([rng.gen_range(0, i - 1) as Revision, NULL_REVISION]) |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
51 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
52 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
53 vg |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
54 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
55 |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
56 /// Compute the ancestors set of all revisions of a VecGraph |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
57 fn ancestors_sets(vg: &VecGraph) -> Vec<HashSet<Revision>> { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
58 let mut ancs: Vec<HashSet<Revision>> = Vec::new(); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
59 for i in 0..vg.len() { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
60 let mut ancs_i = HashSet::new(); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
61 ancs_i.insert(i as Revision); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
62 for p in vg[i].iter().cloned() { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
63 if p != NULL_REVISION { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
64 ancs_i.extend(&ancs[p as usize]); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
65 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
66 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
67 ancs.push(ancs_i); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
68 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
69 ancs |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
70 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
71 |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
72 #[derive(Clone, Debug)] |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
73 enum MissingAncestorsAction { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
74 InitialBases(HashSet<Revision>), |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
75 AddBases(HashSet<Revision>), |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
76 RemoveAncestorsFrom(HashSet<Revision>), |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
77 MissingAncestors(HashSet<Revision>), |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
78 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
79 |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
80 /// An instrumented naive yet obviously correct implementation |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
81 /// |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
82 /// It also records all its actions for easy reproduction for replay |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
83 /// of problematic cases |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
84 struct NaiveMissingAncestors<'a> { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
85 ancestors_sets: &'a Vec<HashSet<Revision>>, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
86 graph: &'a VecGraph, // used for error reporting only |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
87 bases: HashSet<Revision>, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
88 history: Vec<MissingAncestorsAction>, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
89 // for error reporting, assuming we are in a random test |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
90 random_seed: String, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
91 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
92 |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
93 impl<'a> NaiveMissingAncestors<'a> { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
94 fn new( |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
95 graph: &'a VecGraph, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
96 ancestors_sets: &'a Vec<HashSet<Revision>>, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
97 bases: &HashSet<Revision>, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
98 random_seed: &str, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
99 ) -> Self { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
100 Self { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
101 ancestors_sets: ancestors_sets, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
102 bases: bases.clone(), |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
103 graph: graph, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
104 history: vec![MissingAncestorsAction::InitialBases(bases.clone())], |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
105 random_seed: random_seed.into(), |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
106 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
107 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
108 |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
109 fn add_bases(&mut self, new_bases: HashSet<Revision>) { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
110 self.bases.extend(&new_bases); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
111 self.history |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
112 .push(MissingAncestorsAction::AddBases(new_bases)) |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
113 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
114 |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
115 fn remove_ancestors_from(&mut self, revs: &mut HashSet<Revision>) { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
116 revs.remove(&NULL_REVISION); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
117 self.history |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
118 .push(MissingAncestorsAction::RemoveAncestorsFrom(revs.clone())); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
119 for base in self.bases.iter().cloned() { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
120 if base != NULL_REVISION { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
121 for rev in &self.ancestors_sets[base as usize] { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
122 revs.remove(&rev); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
123 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
124 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
125 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
126 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
127 |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
128 fn missing_ancestors( |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
129 &mut self, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
130 revs: impl IntoIterator<Item = Revision>, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
131 ) -> Vec<Revision> { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
132 let revs_as_set: HashSet<Revision> = revs.into_iter().collect(); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
133 |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
134 let mut missing: HashSet<Revision> = HashSet::new(); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
135 for rev in revs_as_set.iter().cloned() { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
136 if rev != NULL_REVISION { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
137 missing.extend(&self.ancestors_sets[rev as usize]) |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
138 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
139 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
140 self.history |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
141 .push(MissingAncestorsAction::MissingAncestors(revs_as_set)); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
142 |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
143 for base in self.bases.iter().cloned() { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
144 if base != NULL_REVISION { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
145 for rev in &self.ancestors_sets[base as usize] { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
146 missing.remove(&rev); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
147 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
148 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
149 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
150 let mut res: Vec<Revision> = missing.iter().cloned().collect(); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
151 res.sort(); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
152 res |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
153 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
154 |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
155 fn assert_eq<T>(&self, left: T, right: T) |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
156 where |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
157 T: PartialEq + Debug, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
158 { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
159 if left == right { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
160 return; |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
161 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
162 panic!(format!( |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
163 "Equality assertion failed (left != right) |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
164 left={:?} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
165 right={:?} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
166 graph={:?} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
167 current bases={:?} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
168 history={:?} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
169 random seed={} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
170 ", |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
171 left, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
172 right, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
173 self.graph, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
174 self.bases, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
175 self.history, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
176 self.random_seed, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
177 )); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
178 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
179 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
180 |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
181 /// Choose a set of random revisions |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
182 /// |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
183 /// The size of the set is taken from a LogNormal distribution |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
184 /// with default mu=1.1 and default sigma=0.8. Quoting the Python |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
185 /// test this is taken from: |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
186 /// the default mu and sigma give us a nice distribution of mostly |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
187 /// single-digit counts (including 0) with some higher ones |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
188 /// The sample may include NULL_REVISION |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
189 fn sample_revs<R: RngCore>( |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
190 rng: &mut R, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
191 maxrev: Revision, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
192 mu_opt: Option<f64>, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
193 sigma_opt: Option<f64>, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
194 ) -> HashSet<Revision> { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
195 let mu = mu_opt.unwrap_or(1.1); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
196 let sigma = sigma_opt.unwrap_or(0.8); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
197 |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
198 let log_normal = LogNormal::new(mu, sigma); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
199 let nb = min(maxrev as usize, log_normal.sample(rng).floor() as usize); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
200 |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
201 let dist = Uniform::from(NULL_REVISION..maxrev); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
202 return rng.sample_iter(&dist).take(nb).collect(); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
203 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
204 |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
205 /// Produces the hexadecimal representation of a slice of bytes |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
206 fn hex_bytes(bytes: &[u8]) -> String { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
207 let mut s = String::with_capacity(bytes.len() * 2); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
208 for b in bytes { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
209 s.push_str(&format!("{:x}", b)); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
210 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
211 s |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
212 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
213 |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
214 /// Fill a random seed from its hexadecimal representation. |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
215 /// |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
216 /// This signature is meant to be consistent with `RngCore::fill_bytes` |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
217 fn seed_parse_in(hex: &str, seed: &mut [u8]) { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
218 if hex.len() != 32 { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
219 panic!("Seed {} is too short for 128 bits hex", hex); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
220 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
221 for i in 0..8 { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
222 seed[i] = u8::from_str_radix(&hex[2 * i..2 * (i + 1)], 16) |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
223 .unwrap_or_else(|_e| panic!("Seed {} is not 128 bits hex", hex)); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
224 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
225 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
226 |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
227 /// Parse the parameters for `test_missing_ancestors()` |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
228 /// |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
229 /// Returns (graphs, instances, calls per instance) |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
230 fn parse_test_missing_ancestors_params(var: &str) -> (usize, usize, usize) { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
231 let err_msg = "TEST_MISSING_ANCESTORS format: GRAPHS,INSTANCES,CALLS"; |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
232 let params: Vec<usize> = var |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
233 .split(',') |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
234 .map(|n| n.trim().parse().expect(err_msg)) |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
235 .collect(); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
236 if params.len() != 3 { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
237 panic!(err_msg); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
238 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
239 (params[0], params[1], params[2]) |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
240 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
241 |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
242 #[test] |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
243 /// This test creates lots of random VecGraphs, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
244 /// and compare a bunch of MissingAncestors for them with |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
245 /// NaiveMissingAncestors that rely on precomputed transitive closures of |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
246 /// these VecGraphs (ancestors_sets). |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
247 /// |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
248 /// For each generater graph, several instances of `MissingAncestors` are |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
249 /// created, whose methods are called and checked a given number of times. |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
250 /// |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
251 /// This test can be parametrized by two environment variables: |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
252 /// |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
253 /// - TEST_RANDOM_SEED: must be 128 bits in hexadecimal |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
254 /// - TEST_MISSING_ANCESTORS: "GRAPHS,INSTANCES,CALLS". The default is |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
255 /// "100,10,10" |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
256 /// |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
257 /// This is slow: it runs on my workstation in about 5 seconds with the |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
258 /// default parameters with a plain `cargo --test`. |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
259 /// |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
260 /// If you want to run it faster, especially if you're changing the |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
261 /// parameters, use `cargo test --release`. |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
262 /// For me, that gets it down to 0.15 seconds with the default parameters |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
263 fn test_missing_ancestors_compare_naive() { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
264 let (graphcount, testcount, inccount) = |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
265 match env::var("TEST_MISSING_ANCESTORS") { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
266 Err(env::VarError::NotPresent) => (100, 10, 10), |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
267 Ok(val) => parse_test_missing_ancestors_params(&val), |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
268 Err(env::VarError::NotUnicode(_)) => { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
269 panic!("TEST_MISSING_ANCESTORS is invalid"); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
270 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
271 }; |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
272 let mut seed: [u8; 16] = [0; 16]; |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
273 match env::var("TEST_RANDOM_SEED") { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
274 Ok(val) => { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
275 seed_parse_in(&val, &mut seed); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
276 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
277 Err(env::VarError::NotPresent) => { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
278 thread_rng().fill_bytes(&mut seed); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
279 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
280 Err(env::VarError::NotUnicode(_)) => { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
281 panic!("TEST_RANDOM_SEED must be 128 bits in hex"); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
282 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
283 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
284 let hex_seed = hex_bytes(&seed); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
285 eprintln!("Random seed: {}", hex_seed); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
286 |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
287 let mut rng = rand_pcg::Pcg32::from_seed(seed); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
288 |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
289 eprint!("Checking MissingAncestors against brute force implementation "); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
290 eprint!("for {} random graphs, ", graphcount); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
291 eprintln!( |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
292 "with {} instances for each and {} calls per instance", |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
293 testcount, inccount, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
294 ); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
295 for g in 0..graphcount { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
296 if g != 0 && g % 100 == 0 { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
297 eprintln!("Tested with {} graphs", g); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
298 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
299 let graph = build_random_graph(None, None, None, None); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
300 let graph_len = graph.len() as Revision; |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
301 let ancestors_sets = ancestors_sets(&graph); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
302 for _testno in 0..testcount { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
303 let bases: HashSet<Revision> = |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
304 sample_revs(&mut rng, graph_len, None, None); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
305 let mut inc = MissingAncestors::<VecGraph>::new( |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
306 graph.clone(), |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
307 bases.clone(), |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
308 ); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
309 let mut naive = NaiveMissingAncestors::new( |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
310 &graph, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
311 &ancestors_sets, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
312 &bases, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
313 &hex_seed, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
314 ); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
315 for _m in 0..inccount { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
316 if rng.gen_bool(0.2) { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
317 let new_bases = |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
318 sample_revs(&mut rng, graph_len, None, None); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
319 inc.add_bases(new_bases.iter().cloned()); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
320 naive.add_bases(new_bases); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
321 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
322 if rng.gen_bool(0.4) { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
323 // larger set so that there are more revs to remove from |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
324 let mut hrevs = |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
325 sample_revs(&mut rng, graph_len, Some(1.5), None); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
326 let mut rrevs = hrevs.clone(); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
327 inc.remove_ancestors_from(&mut hrevs).unwrap(); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
328 naive.remove_ancestors_from(&mut rrevs); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
329 naive.assert_eq(hrevs, rrevs); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
330 } else { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
331 let revs = sample_revs(&mut rng, graph_len, None, None); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
332 let hm = |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
333 inc.missing_ancestors(revs.iter().cloned()).unwrap(); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
334 let rm = naive.missing_ancestors(revs.iter().cloned()); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
335 naive.assert_eq(hm, rm); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
336 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
337 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
338 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
339 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
340 } |