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