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