author | Sushil khanchi <sushilkhanchi97@gmail.com> |
Wed, 06 Oct 2021 13:32:07 +0530 | |
changeset 48185 | 1d70fb83ff4a |
parent 47299 | 16b48ebf656e |
child 48582 | 0dc698c91ca0 |
permissions | -rw-r--r-- |
41703
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
1 |
use hg::testing::VecGraph; |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
2 |
use hg::Revision; |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
3 |
use hg::*; |
44606
d31d1c0685be
rust: update all dependencies
Raphaël Gomès <rgomes@octobus.net>
parents:
42609
diff
changeset
|
4 |
use rand::distributions::{Distribution, Uniform}; |
41703
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
5 |
use rand::{thread_rng, Rng, RngCore, SeedableRng}; |
44606
d31d1c0685be
rust: update all dependencies
Raphaël Gomès <rgomes@octobus.net>
parents:
42609
diff
changeset
|
6 |
use rand_distr::LogNormal; |
41703
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
7 |
use std::cmp::min; |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
8 |
use std::collections::HashSet; |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
9 |
use std::env; |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
10 |
use std::fmt::Debug; |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
11 |
|
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
12 |
fn build_random_graph( |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
13 |
nodes_opt: Option<usize>, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
14 |
rootprob_opt: Option<f64>, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
15 |
mergeprob_opt: Option<f64>, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
16 |
prevprob_opt: Option<f64>, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
17 |
) -> VecGraph { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
18 |
let nodes = nodes_opt.unwrap_or(100); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
19 |
let rootprob = rootprob_opt.unwrap_or(0.05); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
20 |
let mergeprob = mergeprob_opt.unwrap_or(0.2); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
21 |
let prevprob = prevprob_opt.unwrap_or(0.7); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
22 |
|
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
23 |
let mut rng = thread_rng(); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
24 |
let mut vg: VecGraph = Vec::with_capacity(nodes); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
25 |
for i in 0..nodes { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
26 |
if i == 0 || rng.gen_bool(rootprob) { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
27 |
vg.push([NULL_REVISION, NULL_REVISION]) |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
28 |
} else if i == 1 { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
29 |
vg.push([0, NULL_REVISION]) |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
30 |
} else if rng.gen_bool(mergeprob) { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
31 |
let p1 = { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
32 |
if i == 2 || rng.gen_bool(prevprob) { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
33 |
(i - 1) as Revision |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
34 |
} else { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
35 |
rng.gen_range(0, i - 1) as Revision |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
36 |
} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
37 |
}; |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
38 |
// 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
|
39 |
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
|
40 |
if p2 >= p1 { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
41 |
p2 = p2 + 1; |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
42 |
} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
43 |
vg.push([p1, p2]); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
44 |
} else if rng.gen_bool(prevprob) { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
45 |
vg.push([(i - 1) as Revision, NULL_REVISION]) |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
46 |
} else { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
47 |
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
|
48 |
} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
49 |
} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
50 |
vg |
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 |
/// 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
|
54 |
fn ancestors_sets(vg: &VecGraph) -> Vec<HashSet<Revision>> { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
55 |
let mut ancs: Vec<HashSet<Revision>> = Vec::new(); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
56 |
for i in 0..vg.len() { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
57 |
let mut ancs_i = HashSet::new(); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
58 |
ancs_i.insert(i as Revision); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
59 |
for p in vg[i].iter().cloned() { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
60 |
if p != NULL_REVISION { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
61 |
ancs_i.extend(&ancs[p as usize]); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
62 |
} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
63 |
} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
64 |
ancs.push(ancs_i); |
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 |
ancs |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
67 |
} |
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 |
#[derive(Clone, Debug)] |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
70 |
enum MissingAncestorsAction { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
71 |
InitialBases(HashSet<Revision>), |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
72 |
AddBases(HashSet<Revision>), |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
73 |
RemoveAncestorsFrom(HashSet<Revision>), |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
74 |
MissingAncestors(HashSet<Revision>), |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
75 |
} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
76 |
|
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
77 |
/// An instrumented naive yet obviously correct implementation |
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 |
/// 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
|
80 |
/// of problematic cases |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
81 |
struct NaiveMissingAncestors<'a> { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
82 |
ancestors_sets: &'a Vec<HashSet<Revision>>, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
83 |
graph: &'a VecGraph, // used for error reporting only |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
84 |
bases: HashSet<Revision>, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
85 |
history: Vec<MissingAncestorsAction>, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
86 |
// 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
|
87 |
random_seed: String, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
88 |
} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
89 |
|
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
90 |
impl<'a> NaiveMissingAncestors<'a> { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
91 |
fn new( |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
92 |
graph: &'a VecGraph, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
93 |
ancestors_sets: &'a Vec<HashSet<Revision>>, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
94 |
bases: &HashSet<Revision>, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
95 |
random_seed: &str, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
96 |
) -> Self { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
97 |
Self { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
98 |
ancestors_sets: ancestors_sets, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
99 |
bases: bases.clone(), |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
100 |
graph: graph, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
101 |
history: vec![MissingAncestorsAction::InitialBases(bases.clone())], |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
102 |
random_seed: random_seed.into(), |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
103 |
} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
104 |
} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
105 |
|
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
106 |
fn add_bases(&mut self, new_bases: HashSet<Revision>) { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
107 |
self.bases.extend(&new_bases); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
108 |
self.history |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
109 |
.push(MissingAncestorsAction::AddBases(new_bases)) |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
110 |
} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
111 |
|
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
112 |
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
|
113 |
revs.remove(&NULL_REVISION); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
114 |
self.history |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
115 |
.push(MissingAncestorsAction::RemoveAncestorsFrom(revs.clone())); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
116 |
for base in self.bases.iter().cloned() { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
117 |
if base != NULL_REVISION { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
118 |
for rev in &self.ancestors_sets[base as usize] { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
119 |
revs.remove(&rev); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
120 |
} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
121 |
} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
122 |
} |
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 |
fn missing_ancestors( |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
126 |
&mut self, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
127 |
revs: impl IntoIterator<Item = Revision>, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
128 |
) -> Vec<Revision> { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
129 |
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
|
130 |
|
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
131 |
let mut missing: HashSet<Revision> = HashSet::new(); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
132 |
for rev in revs_as_set.iter().cloned() { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
133 |
if rev != NULL_REVISION { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
134 |
missing.extend(&self.ancestors_sets[rev as usize]) |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
135 |
} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
136 |
} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
137 |
self.history |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
138 |
.push(MissingAncestorsAction::MissingAncestors(revs_as_set)); |
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 |
for base in self.bases.iter().cloned() { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
141 |
if base != NULL_REVISION { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
142 |
for rev in &self.ancestors_sets[base as usize] { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
143 |
missing.remove(&rev); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
144 |
} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
145 |
} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
146 |
} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
147 |
let mut res: Vec<Revision> = missing.iter().cloned().collect(); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
148 |
res.sort(); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
149 |
res |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
150 |
} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
151 |
|
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
152 |
fn assert_eq<T>(&self, left: T, right: T) |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
153 |
where |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
154 |
T: PartialEq + Debug, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
155 |
{ |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
156 |
if left == right { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
157 |
return; |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
158 |
} |
47299
16b48ebf656e
rust: Fix "panic message is not a string literal" warnings
Simon Sapin <simon.sapin@octobus.net>
parents:
44606
diff
changeset
|
159 |
panic!( |
41703
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
160 |
"Equality assertion failed (left != right) |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
161 |
left={:?} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
162 |
right={:?} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
163 |
graph={:?} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
164 |
current bases={:?} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
165 |
history={:?} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
166 |
random seed={} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
167 |
", |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
168 |
left, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
169 |
right, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
170 |
self.graph, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
171 |
self.bases, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
172 |
self.history, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
173 |
self.random_seed, |
47299
16b48ebf656e
rust: Fix "panic message is not a string literal" warnings
Simon Sapin <simon.sapin@octobus.net>
parents:
44606
diff
changeset
|
174 |
); |
41703
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
175 |
} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
176 |
} |
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 |
/// Choose a set of random revisions |
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 |
/// 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
|
181 |
/// 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
|
182 |
/// test this is taken from: |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
183 |
/// 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
|
184 |
/// single-digit counts (including 0) with some higher ones |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
185 |
/// The sample may include NULL_REVISION |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
186 |
fn sample_revs<R: RngCore>( |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
187 |
rng: &mut R, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
188 |
maxrev: Revision, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
189 |
mu_opt: Option<f64>, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
190 |
sigma_opt: Option<f64>, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
191 |
) -> HashSet<Revision> { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
192 |
let mu = mu_opt.unwrap_or(1.1); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
193 |
let sigma = sigma_opt.unwrap_or(0.8); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
194 |
|
44606
d31d1c0685be
rust: update all dependencies
Raphaël Gomès <rgomes@octobus.net>
parents:
42609
diff
changeset
|
195 |
let log_normal = LogNormal::new(mu, sigma).unwrap(); |
41703
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
196 |
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
|
197 |
|
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
198 |
let dist = Uniform::from(NULL_REVISION..maxrev); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
199 |
return rng.sample_iter(&dist).take(nb).collect(); |
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 |
|
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
202 |
/// Produces the hexadecimal representation of a slice of bytes |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
203 |
fn hex_bytes(bytes: &[u8]) -> String { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
204 |
let mut s = String::with_capacity(bytes.len() * 2); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
205 |
for b in bytes { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
206 |
s.push_str(&format!("{:x}", b)); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
207 |
} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
208 |
s |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
209 |
} |
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 |
/// Fill a random seed from its hexadecimal representation. |
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 |
/// 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
|
214 |
fn seed_parse_in(hex: &str, seed: &mut [u8]) { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
215 |
if hex.len() != 32 { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
216 |
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
|
217 |
} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
218 |
for i in 0..8 { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
219 |
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
|
220 |
.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
|
221 |
} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
222 |
} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
223 |
|
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
224 |
/// Parse the parameters for `test_missing_ancestors()` |
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 |
/// Returns (graphs, instances, calls per instance) |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
227 |
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
|
228 |
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
|
229 |
let params: Vec<usize> = var |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
230 |
.split(',') |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
231 |
.map(|n| n.trim().parse().expect(err_msg)) |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
232 |
.collect(); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
233 |
if params.len() != 3 { |
47299
16b48ebf656e
rust: Fix "panic message is not a string literal" warnings
Simon Sapin <simon.sapin@octobus.net>
parents:
44606
diff
changeset
|
234 |
panic!("{}", err_msg); |
41703
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
235 |
} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
236 |
(params[0], params[1], params[2]) |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
237 |
} |
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 |
#[test] |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
240 |
/// This test creates lots of random VecGraphs, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
241 |
/// and compare a bunch of MissingAncestors for them with |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
242 |
/// NaiveMissingAncestors that rely on precomputed transitive closures of |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
243 |
/// these VecGraphs (ancestors_sets). |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
244 |
/// |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
245 |
/// For each generater graph, several instances of `MissingAncestors` are |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
246 |
/// 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
|
247 |
/// |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
248 |
/// This test can be parametrized by two environment variables: |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
249 |
/// |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
250 |
/// - TEST_RANDOM_SEED: must be 128 bits in hexadecimal |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
251 |
/// - TEST_MISSING_ANCESTORS: "GRAPHS,INSTANCES,CALLS". The default is |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
252 |
/// "100,10,10" |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
253 |
/// |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
254 |
/// 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
|
255 |
/// default parameters with a plain `cargo --test`. |
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 |
/// 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
|
258 |
/// parameters, use `cargo test --release`. |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
259 |
/// 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
|
260 |
fn test_missing_ancestors_compare_naive() { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
261 |
let (graphcount, testcount, inccount) = |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
262 |
match env::var("TEST_MISSING_ANCESTORS") { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
263 |
Err(env::VarError::NotPresent) => (100, 10, 10), |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
264 |
Ok(val) => parse_test_missing_ancestors_params(&val), |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
265 |
Err(env::VarError::NotUnicode(_)) => { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
266 |
panic!("TEST_MISSING_ANCESTORS is invalid"); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
267 |
} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
268 |
}; |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
269 |
let mut seed: [u8; 16] = [0; 16]; |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
270 |
match env::var("TEST_RANDOM_SEED") { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
271 |
Ok(val) => { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
272 |
seed_parse_in(&val, &mut seed); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
273 |
} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
274 |
Err(env::VarError::NotPresent) => { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
275 |
thread_rng().fill_bytes(&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::NotUnicode(_)) => { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
278 |
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
|
279 |
} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
280 |
} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
281 |
let hex_seed = hex_bytes(&seed); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
282 |
eprintln!("Random seed: {}", hex_seed); |
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 mut rng = rand_pcg::Pcg32::from_seed(seed); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
285 |
|
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
286 |
eprint!("Checking MissingAncestors against brute force implementation "); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
287 |
eprint!("for {} random graphs, ", graphcount); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
288 |
eprintln!( |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
289 |
"with {} instances for each and {} calls per instance", |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
290 |
testcount, inccount, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
291 |
); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
292 |
for g in 0..graphcount { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
293 |
if g != 0 && g % 100 == 0 { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
294 |
eprintln!("Tested with {} graphs", g); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
295 |
} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
296 |
let graph = build_random_graph(None, None, None, None); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
297 |
let graph_len = graph.len() as Revision; |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
298 |
let ancestors_sets = ancestors_sets(&graph); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
299 |
for _testno in 0..testcount { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
300 |
let bases: HashSet<Revision> = |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
301 |
sample_revs(&mut rng, graph_len, None, None); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
302 |
let mut inc = MissingAncestors::<VecGraph>::new( |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
303 |
graph.clone(), |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
304 |
bases.clone(), |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
305 |
); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
306 |
let mut naive = NaiveMissingAncestors::new( |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
307 |
&graph, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
308 |
&ancestors_sets, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
309 |
&bases, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
310 |
&hex_seed, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
311 |
); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
312 |
for _m in 0..inccount { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
313 |
if rng.gen_bool(0.2) { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
314 |
let new_bases = |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
315 |
sample_revs(&mut rng, graph_len, None, None); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
316 |
inc.add_bases(new_bases.iter().cloned()); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
317 |
naive.add_bases(new_bases); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
318 |
} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
319 |
if rng.gen_bool(0.4) { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
320 |
// 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
|
321 |
let mut hrevs = |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
322 |
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
|
323 |
let mut rrevs = hrevs.clone(); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
324 |
inc.remove_ancestors_from(&mut hrevs).unwrap(); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
325 |
naive.remove_ancestors_from(&mut rrevs); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
326 |
naive.assert_eq(hrevs, rrevs); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
327 |
} else { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
328 |
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
|
329 |
let hm = |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
330 |
inc.missing_ancestors(revs.iter().cloned()).unwrap(); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
331 |
let rm = naive.missing_ancestors(revs.iter().cloned()); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
332 |
naive.assert_eq(hm, rm); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
333 |
} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
334 |
} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
335 |
} |
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 |
} |