Mercurial > hg
annotate rust/hg-core/tests/test_missing_ancestors.rs @ 42609:326fdce22fb2
rust: switch hg-core and hg-cpython to rust 2018 edition
Many interesting changes have happened in Rust since the Oxidation Plan was
introduced, like the 2018 edition and procedural macros:
- Opting in to the 2018 edition is a clear benefit in terms of future
proofing, new (nice to have) syntactical sugar notwithstanding. It
also has a new non-lexical, non-AST based borrow checker that has
fewer bugs(!) and allows us to write correct code that in some cases
would have been rejected by the old one.
- Procedural macros allow us to use the PyO3 crate which maintainers have
expressed the clear goal of compiling on stable, which would help in
code maintainability compared to rust-cpython.
In this patch are the following changes:
- Removing most `extern crate` uses
- Updating `use` clauses (`crate` keyword, nested `use`)
- Removing `mod.rs` in favor of an aptly named module file
Like discussed in the mailing list (
https://www.mercurial-scm.org/pipermail/mercurial-devel/2019-July/132316.html
), until Rust integration in Mercurial is considered to be out of the
experimental phase, the maximum version of Rust allowed is whatever the latest
version Debian packages.
Differential Revision: https://phab.mercurial-scm.org/D6597
author | Raphaël Gomès <rgomes@octobus.net> |
---|---|
date | Tue, 02 Jul 2019 17:15:03 +0200 |
parents | ee7b7bd432a1 |
children | d31d1c0685be |
rev | line source |
---|---|
41692
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::*; |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
4 use rand::distributions::{Distribution, LogNormal, Uniform}; |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
5 use rand::{thread_rng, Rng, RngCore, SeedableRng}; |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
6 use std::cmp::min; |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
7 use std::collections::HashSet; |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
8 use std::env; |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
9 use std::fmt::Debug; |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
10 |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
11 fn build_random_graph( |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
12 nodes_opt: Option<usize>, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
13 rootprob_opt: Option<f64>, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
14 mergeprob_opt: Option<f64>, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
15 prevprob_opt: Option<f64>, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
16 ) -> VecGraph { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
17 let nodes = nodes_opt.unwrap_or(100); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
18 let rootprob = rootprob_opt.unwrap_or(0.05); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
19 let mergeprob = mergeprob_opt.unwrap_or(0.2); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
20 let prevprob = prevprob_opt.unwrap_or(0.7); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
21 |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
22 let mut rng = thread_rng(); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
23 let mut vg: VecGraph = Vec::with_capacity(nodes); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
24 for i in 0..nodes { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
25 if i == 0 || rng.gen_bool(rootprob) { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
26 vg.push([NULL_REVISION, NULL_REVISION]) |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
27 } else if i == 1 { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
28 vg.push([0, NULL_REVISION]) |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
29 } else if rng.gen_bool(mergeprob) { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
30 let p1 = { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
31 if i == 2 || rng.gen_bool(prevprob) { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
32 (i - 1) as Revision |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
33 } else { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
34 rng.gen_range(0, i - 1) as Revision |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
35 } |
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 // 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
|
38 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
|
39 if p2 >= p1 { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
40 p2 = p2 + 1; |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
41 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
42 vg.push([p1, p2]); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
43 } else if rng.gen_bool(prevprob) { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
44 vg.push([(i - 1) as Revision, NULL_REVISION]) |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
45 } else { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
46 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
|
47 } |
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 vg |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
50 } |
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 /// 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
|
53 fn ancestors_sets(vg: &VecGraph) -> Vec<HashSet<Revision>> { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
54 let mut ancs: Vec<HashSet<Revision>> = Vec::new(); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
55 for i in 0..vg.len() { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
56 let mut ancs_i = HashSet::new(); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
57 ancs_i.insert(i as Revision); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
58 for p in vg[i].iter().cloned() { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
59 if p != NULL_REVISION { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
60 ancs_i.extend(&ancs[p as usize]); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
61 } |
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 ancs.push(ancs_i); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
64 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
65 ancs |
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 |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
68 #[derive(Clone, Debug)] |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
69 enum MissingAncestorsAction { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
70 InitialBases(HashSet<Revision>), |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
71 AddBases(HashSet<Revision>), |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
72 RemoveAncestorsFrom(HashSet<Revision>), |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
73 MissingAncestors(HashSet<Revision>), |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
74 } |
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 /// An instrumented naive yet obviously correct implementation |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
77 /// |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
78 /// 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
|
79 /// of problematic cases |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
80 struct NaiveMissingAncestors<'a> { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
81 ancestors_sets: &'a Vec<HashSet<Revision>>, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
82 graph: &'a VecGraph, // used for error reporting only |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
83 bases: HashSet<Revision>, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
84 history: Vec<MissingAncestorsAction>, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
85 // 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
|
86 random_seed: String, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
87 } |
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 impl<'a> NaiveMissingAncestors<'a> { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
90 fn new( |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
91 graph: &'a VecGraph, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
92 ancestors_sets: &'a Vec<HashSet<Revision>>, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
93 bases: &HashSet<Revision>, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
94 random_seed: &str, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
95 ) -> Self { |
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 ancestors_sets: ancestors_sets, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
98 bases: bases.clone(), |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
99 graph: graph, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
100 history: vec![MissingAncestorsAction::InitialBases(bases.clone())], |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
101 random_seed: random_seed.into(), |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
102 } |
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 fn add_bases(&mut self, new_bases: HashSet<Revision>) { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
106 self.bases.extend(&new_bases); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
107 self.history |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
108 .push(MissingAncestorsAction::AddBases(new_bases)) |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
109 } |
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 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
|
112 revs.remove(&NULL_REVISION); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
113 self.history |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
114 .push(MissingAncestorsAction::RemoveAncestorsFrom(revs.clone())); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
115 for base in self.bases.iter().cloned() { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
116 if base != NULL_REVISION { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
117 for rev in &self.ancestors_sets[base as usize] { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
118 revs.remove(&rev); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
119 } |
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 fn missing_ancestors( |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
125 &mut self, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
126 revs: impl IntoIterator<Item = Revision>, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
127 ) -> Vec<Revision> { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
128 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
|
129 |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
130 let mut missing: HashSet<Revision> = HashSet::new(); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
131 for rev in revs_as_set.iter().cloned() { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
132 if rev != NULL_REVISION { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
133 missing.extend(&self.ancestors_sets[rev as usize]) |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
134 } |
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 self.history |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
137 .push(MissingAncestorsAction::MissingAncestors(revs_as_set)); |
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 for base in self.bases.iter().cloned() { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
140 if base != NULL_REVISION { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
141 for rev in &self.ancestors_sets[base as usize] { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
142 missing.remove(&rev); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
143 } |
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 let mut res: Vec<Revision> = missing.iter().cloned().collect(); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
147 res.sort(); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
148 res |
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 |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
151 fn assert_eq<T>(&self, left: T, right: T) |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
152 where |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
153 T: PartialEq + Debug, |
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 if left == right { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
156 return; |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
157 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
158 panic!(format!( |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
159 "Equality assertion failed (left != right) |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
160 left={:?} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
161 right={:?} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
162 graph={:?} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
163 current bases={:?} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
164 history={:?} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
165 random seed={} |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
166 ", |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
167 left, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
168 right, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
169 self.graph, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
170 self.bases, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
171 self.history, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
172 self.random_seed, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
173 )); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
174 } |
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 /// Choose a set of random revisions |
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 /// 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
|
180 /// 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
|
181 /// test this is taken from: |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
182 /// 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
|
183 /// single-digit counts (including 0) with some higher ones |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
184 /// The sample may include NULL_REVISION |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
185 fn sample_revs<R: RngCore>( |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
186 rng: &mut R, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
187 maxrev: Revision, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
188 mu_opt: Option<f64>, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
189 sigma_opt: Option<f64>, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
190 ) -> HashSet<Revision> { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
191 let mu = mu_opt.unwrap_or(1.1); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
192 let sigma = sigma_opt.unwrap_or(0.8); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
193 |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
194 let log_normal = LogNormal::new(mu, sigma); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
195 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
|
196 |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
197 let dist = Uniform::from(NULL_REVISION..maxrev); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
198 return rng.sample_iter(&dist).take(nb).collect(); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
199 } |
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 /// Produces the hexadecimal representation of a slice of bytes |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
202 fn hex_bytes(bytes: &[u8]) -> String { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
203 let mut s = String::with_capacity(bytes.len() * 2); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
204 for b in bytes { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
205 s.push_str(&format!("{:x}", b)); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
206 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
207 s |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
208 } |
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 /// Fill a random seed from its hexadecimal representation. |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
211 /// |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
212 /// 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
|
213 fn seed_parse_in(hex: &str, seed: &mut [u8]) { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
214 if hex.len() != 32 { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
215 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
|
216 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
217 for i in 0..8 { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
218 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
|
219 .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
|
220 } |
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 /// Parse the parameters for `test_missing_ancestors()` |
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 /// Returns (graphs, instances, calls per instance) |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
226 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
|
227 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
|
228 let params: Vec<usize> = var |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
229 .split(',') |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
230 .map(|n| n.trim().parse().expect(err_msg)) |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
231 .collect(); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
232 if params.len() != 3 { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
233 panic!(err_msg); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
234 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
235 (params[0], params[1], params[2]) |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
236 } |
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 #[test] |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
239 /// This test creates lots of random VecGraphs, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
240 /// and compare a bunch of MissingAncestors for them with |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
241 /// NaiveMissingAncestors that rely on precomputed transitive closures of |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
242 /// these VecGraphs (ancestors_sets). |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
243 /// |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
244 /// For each generater graph, several instances of `MissingAncestors` are |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
245 /// 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
|
246 /// |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
247 /// This test can be parametrized by two environment variables: |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
248 /// |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
249 /// - TEST_RANDOM_SEED: must be 128 bits in hexadecimal |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
250 /// - TEST_MISSING_ANCESTORS: "GRAPHS,INSTANCES,CALLS". The default is |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
251 /// "100,10,10" |
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 /// 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
|
254 /// default parameters with a plain `cargo --test`. |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
255 /// |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
256 /// 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
|
257 /// parameters, use `cargo test --release`. |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
258 /// 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
|
259 fn test_missing_ancestors_compare_naive() { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
260 let (graphcount, testcount, inccount) = |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
261 match env::var("TEST_MISSING_ANCESTORS") { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
262 Err(env::VarError::NotPresent) => (100, 10, 10), |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
263 Ok(val) => parse_test_missing_ancestors_params(&val), |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
264 Err(env::VarError::NotUnicode(_)) => { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
265 panic!("TEST_MISSING_ANCESTORS is invalid"); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
266 } |
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 let mut seed: [u8; 16] = [0; 16]; |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
269 match env::var("TEST_RANDOM_SEED") { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
270 Ok(val) => { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
271 seed_parse_in(&val, &mut seed); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
272 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
273 Err(env::VarError::NotPresent) => { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
274 thread_rng().fill_bytes(&mut seed); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
275 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
276 Err(env::VarError::NotUnicode(_)) => { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
277 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
|
278 } |
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 let hex_seed = hex_bytes(&seed); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
281 eprintln!("Random seed: {}", hex_seed); |
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 let mut rng = rand_pcg::Pcg32::from_seed(seed); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
284 |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
285 eprint!("Checking MissingAncestors against brute force implementation "); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
286 eprint!("for {} random graphs, ", graphcount); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
287 eprintln!( |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
288 "with {} instances for each and {} calls per instance", |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
289 testcount, inccount, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
290 ); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
291 for g in 0..graphcount { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
292 if g != 0 && g % 100 == 0 { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
293 eprintln!("Tested with {} graphs", g); |
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 let graph = build_random_graph(None, None, None, None); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
296 let graph_len = graph.len() as Revision; |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
297 let ancestors_sets = ancestors_sets(&graph); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
298 for _testno in 0..testcount { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
299 let bases: HashSet<Revision> = |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
300 sample_revs(&mut rng, graph_len, None, None); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
301 let mut inc = MissingAncestors::<VecGraph>::new( |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
302 graph.clone(), |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
303 bases.clone(), |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
304 ); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
305 let mut naive = NaiveMissingAncestors::new( |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
306 &graph, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
307 &ancestors_sets, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
308 &bases, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
309 &hex_seed, |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
310 ); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
311 for _m in 0..inccount { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
312 if rng.gen_bool(0.2) { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
313 let new_bases = |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
314 sample_revs(&mut rng, graph_len, None, None); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
315 inc.add_bases(new_bases.iter().cloned()); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
316 naive.add_bases(new_bases); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
317 } |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
318 if rng.gen_bool(0.4) { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
319 // 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
|
320 let mut hrevs = |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
321 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
|
322 let mut rrevs = hrevs.clone(); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
323 inc.remove_ancestors_from(&mut hrevs).unwrap(); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
324 naive.remove_ancestors_from(&mut rrevs); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
325 naive.assert_eq(hrevs, rrevs); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
326 } else { |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
327 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
|
328 let hm = |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
329 inc.missing_ancestors(revs.iter().cloned()).unwrap(); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
330 let rm = naive.missing_ancestors(revs.iter().cloned()); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
331 naive.assert_eq(hm, rm); |
ee7b7bd432a1
rust: translated random test of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
332 } |
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 } |