Show More
@@ -1,653 +1,696 b'' | |||
|
1 | 1 | // discovery.rs |
|
2 | 2 | // |
|
3 | 3 | // Copyright 2019 Georges Racinet <georges.racinet@octobus.net> |
|
4 | 4 | // |
|
5 | 5 | // This software may be used and distributed according to the terms of the |
|
6 | 6 | // GNU General Public License version 2 or any later version. |
|
7 | 7 | |
|
8 | 8 | //! Discovery operations |
|
9 | 9 | //! |
|
10 | 10 | //! This is a Rust counterpart to the `partialdiscovery` class of |
|
11 | 11 | //! `mercurial.setdiscovery` |
|
12 | 12 | |
|
13 | 13 | extern crate rand; |
|
14 | 14 | extern crate rand_pcg; |
|
15 | 15 | use self::rand::seq::SliceRandom; |
|
16 | 16 | use self::rand::{thread_rng, RngCore, SeedableRng}; |
|
17 | 17 | use super::{Graph, GraphError, Revision, NULL_REVISION}; |
|
18 | 18 | use crate::ancestors::MissingAncestors; |
|
19 | 19 | use crate::dagops; |
|
20 | 20 | use std::cmp::{max, min}; |
|
21 | 21 | use std::collections::{HashMap, HashSet, VecDeque}; |
|
22 | 22 | |
|
23 | 23 | type Rng = self::rand_pcg::Pcg32; |
|
24 | 24 | |
|
25 | 25 | pub struct PartialDiscovery<G: Graph + Clone> { |
|
26 | 26 | target_heads: Option<Vec<Revision>>, |
|
27 | 27 | graph: G, // plays the role of self._repo |
|
28 | 28 | common: MissingAncestors<G>, |
|
29 | 29 | undecided: Option<HashSet<Revision>>, |
|
30 | 30 | children_cache: Option<HashMap<Revision, Vec<Revision>>>, |
|
31 | 31 | missing: HashSet<Revision>, |
|
32 | 32 | rng: Rng, |
|
33 | 33 | respect_size: bool, |
|
34 | 34 | randomize: bool, |
|
35 | 35 | } |
|
36 | 36 | |
|
37 | 37 | pub struct DiscoveryStats { |
|
38 | 38 | pub undecided: Option<usize>, |
|
39 | 39 | } |
|
40 | 40 | |
|
41 | 41 | /// Update an existing sample to match the expected size |
|
42 | 42 | /// |
|
43 | 43 | /// The sample is updated with revisions exponentially distant from each |
|
44 | 44 | /// element of `heads`. |
|
45 | 45 | /// |
|
46 | 46 | /// If a target size is specified, the sampling will stop once this size is |
|
47 | 47 | /// reached. Otherwise sampling will happen until roots of the <revs> set are |
|
48 | 48 | /// reached. |
|
49 | 49 | /// |
|
50 | 50 | /// - `revs`: set of revs we want to discover (if None, `assume` the whole dag |
|
51 | 51 | /// represented by `parentfn` |
|
52 | 52 | /// - `heads`: set of DAG head revs |
|
53 | 53 | /// - `sample`: a sample to update |
|
54 | 54 | /// - `parentfn`: a callable to resolve parents for a revision |
|
55 | 55 | /// - `quicksamplesize`: optional target size of the sample |
|
56 | 56 | fn update_sample<I>( |
|
57 | 57 | revs: Option<&HashSet<Revision>>, |
|
58 | 58 | heads: impl IntoIterator<Item = Revision>, |
|
59 | 59 | sample: &mut HashSet<Revision>, |
|
60 | 60 | parentsfn: impl Fn(Revision) -> Result<I, GraphError>, |
|
61 | 61 | quicksamplesize: Option<usize>, |
|
62 | 62 | ) -> Result<(), GraphError> |
|
63 | 63 | where |
|
64 | 64 | I: Iterator<Item = Revision>, |
|
65 | 65 | { |
|
66 | 66 | let mut distances: HashMap<Revision, u32> = HashMap::new(); |
|
67 | 67 | let mut visit: VecDeque<Revision> = heads.into_iter().collect(); |
|
68 | 68 | let mut factor: u32 = 1; |
|
69 | 69 | let mut seen: HashSet<Revision> = HashSet::new(); |
|
70 | 70 | loop { |
|
71 | 71 | let current = match visit.pop_front() { |
|
72 | 72 | None => { |
|
73 | 73 | break; |
|
74 | 74 | } |
|
75 | 75 | Some(r) => r, |
|
76 | 76 | }; |
|
77 | 77 | if !seen.insert(current) { |
|
78 | 78 | continue; |
|
79 | 79 | } |
|
80 | 80 | |
|
81 | 81 | let d = *distances.entry(current).or_insert(1); |
|
82 | 82 | if d > factor { |
|
83 | 83 | factor *= 2; |
|
84 | 84 | } |
|
85 | 85 | if d == factor { |
|
86 | 86 | sample.insert(current); |
|
87 | 87 | if let Some(sz) = quicksamplesize { |
|
88 | 88 | if sample.len() >= sz { |
|
89 | 89 | return Ok(()); |
|
90 | 90 | } |
|
91 | 91 | } |
|
92 | 92 | } |
|
93 | 93 | for p in parentsfn(current)? { |
|
94 | 94 | if let Some(revs) = revs { |
|
95 | 95 | if !revs.contains(&p) { |
|
96 | 96 | continue; |
|
97 | 97 | } |
|
98 | 98 | } |
|
99 | 99 | distances.entry(p).or_insert(d + 1); |
|
100 | 100 | visit.push_back(p); |
|
101 | 101 | } |
|
102 | 102 | } |
|
103 | 103 | Ok(()) |
|
104 | 104 | } |
|
105 | 105 | |
|
106 | 106 | struct ParentsIterator { |
|
107 | 107 | parents: [Revision; 2], |
|
108 | 108 | cur: usize, |
|
109 | 109 | } |
|
110 | 110 | |
|
111 | 111 | impl ParentsIterator { |
|
112 | 112 | fn graph_parents( |
|
113 | 113 | graph: &impl Graph, |
|
114 | 114 | r: Revision, |
|
115 | 115 | ) -> Result<ParentsIterator, GraphError> { |
|
116 | 116 | Ok(ParentsIterator { |
|
117 | 117 | parents: graph.parents(r)?, |
|
118 | 118 | cur: 0, |
|
119 | 119 | }) |
|
120 | 120 | } |
|
121 | 121 | } |
|
122 | 122 | |
|
123 | 123 | impl Iterator for ParentsIterator { |
|
124 | 124 | type Item = Revision; |
|
125 | 125 | |
|
126 | 126 | fn next(&mut self) -> Option<Revision> { |
|
127 | 127 | if self.cur > 1 { |
|
128 | 128 | return None; |
|
129 | 129 | } |
|
130 | 130 | let rev = self.parents[self.cur]; |
|
131 | 131 | self.cur += 1; |
|
132 | 132 | if rev == NULL_REVISION { |
|
133 | 133 | return self.next(); |
|
134 | 134 | } |
|
135 | 135 | Some(rev) |
|
136 | 136 | } |
|
137 | 137 | } |
|
138 | 138 | |
|
139 | 139 | impl<G: Graph + Clone> PartialDiscovery<G> { |
|
140 | 140 | /// Create a PartialDiscovery object, with the intent |
|
141 | 141 | /// of comparing our `::<target_heads>` revset to the contents of another |
|
142 | 142 | /// repo. |
|
143 | 143 | /// |
|
144 | 144 | /// For now `target_heads` is passed as a vector, and will be used |
|
145 | 145 | /// at the first call to `ensure_undecided()`. |
|
146 | 146 | /// |
|
147 | 147 | /// If we want to make the signature more flexible, |
|
148 | 148 | /// we'll have to make it a type argument of `PartialDiscovery` or a trait |
|
149 | 149 | /// object since we'll keep it in the meanwhile |
|
150 | 150 | /// |
|
151 | 151 | /// The `respect_size` boolean controls how the sampling methods |
|
152 | 152 | /// will interpret the size argument requested by the caller. If it's |
|
153 | 153 | /// `false`, they are allowed to produce a sample whose size is more |
|
154 | 154 | /// appropriate to the situation (typically bigger). |
|
155 | 155 | /// |
|
156 | 156 | /// The `randomize` boolean affects sampling, and specifically how |
|
157 | 157 | /// limiting or last-minute expanding is been done: |
|
158 | 158 | /// |
|
159 | 159 | /// If `true`, both will perform random picking from `self.undecided`. |
|
160 | 160 | /// This is currently the best for actual discoveries. |
|
161 | 161 | /// |
|
162 | 162 | /// If `false`, a reproductible picking strategy is performed. This is |
|
163 | 163 | /// useful for integration tests. |
|
164 | 164 | pub fn new( |
|
165 | 165 | graph: G, |
|
166 | 166 | target_heads: Vec<Revision>, |
|
167 | 167 | respect_size: bool, |
|
168 | 168 | randomize: bool, |
|
169 | 169 | ) -> Self { |
|
170 | 170 | let mut seed: [u8; 16] = [0; 16]; |
|
171 | 171 | if randomize { |
|
172 | 172 | thread_rng().fill_bytes(&mut seed); |
|
173 | 173 | } |
|
174 | 174 | Self::new_with_seed(graph, target_heads, seed, respect_size, randomize) |
|
175 | 175 | } |
|
176 | 176 | |
|
177 | 177 | pub fn new_with_seed( |
|
178 | 178 | graph: G, |
|
179 | 179 | target_heads: Vec<Revision>, |
|
180 | 180 | seed: [u8; 16], |
|
181 | 181 | respect_size: bool, |
|
182 | 182 | randomize: bool, |
|
183 | 183 | ) -> Self { |
|
184 | 184 | PartialDiscovery { |
|
185 | 185 | undecided: None, |
|
186 | 186 | children_cache: None, |
|
187 | 187 | target_heads: Some(target_heads), |
|
188 | 188 | graph: graph.clone(), |
|
189 | 189 | common: MissingAncestors::new(graph, vec![]), |
|
190 | 190 | missing: HashSet::new(), |
|
191 | 191 | rng: Rng::from_seed(seed), |
|
192 | 192 | respect_size: respect_size, |
|
193 | 193 | randomize: randomize, |
|
194 | 194 | } |
|
195 | 195 | } |
|
196 | 196 | |
|
197 | 197 | /// Extract at most `size` random elements from sample and return them |
|
198 | 198 | /// as a vector |
|
199 | 199 | fn limit_sample( |
|
200 | 200 | &mut self, |
|
201 | 201 | mut sample: Vec<Revision>, |
|
202 | 202 | size: usize, |
|
203 | 203 | ) -> Vec<Revision> { |
|
204 | 204 | if !self.randomize { |
|
205 | 205 | sample.sort(); |
|
206 | 206 | sample.truncate(size); |
|
207 | 207 | return sample; |
|
208 | 208 | } |
|
209 | 209 | let sample_len = sample.len(); |
|
210 | 210 | if sample_len <= size { |
|
211 | 211 | return sample; |
|
212 | 212 | } |
|
213 | 213 | let rng = &mut self.rng; |
|
214 | 214 | let dropped_size = sample_len - size; |
|
215 | 215 | let limited_slice = if size < dropped_size { |
|
216 | 216 | sample.partial_shuffle(rng, size).0 |
|
217 | 217 | } else { |
|
218 | 218 | sample.partial_shuffle(rng, dropped_size).1 |
|
219 | 219 | }; |
|
220 | 220 | limited_slice.to_owned() |
|
221 | 221 | } |
|
222 | 222 | |
|
223 | 223 | /// Register revisions known as being common |
|
224 | 224 | pub fn add_common_revisions( |
|
225 | 225 | &mut self, |
|
226 | 226 | common: impl IntoIterator<Item = Revision>, |
|
227 | 227 | ) -> Result<(), GraphError> { |
|
228 | 228 | self.common.add_bases(common); |
|
229 | 229 | if let Some(ref mut undecided) = self.undecided { |
|
230 | 230 | self.common.remove_ancestors_from(undecided)?; |
|
231 | 231 | } |
|
232 | 232 | Ok(()) |
|
233 | 233 | } |
|
234 | 234 | |
|
235 | 235 | /// Register revisions known as being missing |
|
236 | /// | |
|
237 | /// # Performance note | |
|
238 | /// | |
|
239 | /// Except in the most trivial case, the first call of this method has | |
|
240 | /// the side effect of computing `self.undecided` set for the first time, | |
|
241 | /// and the related caches it might need for efficiency of its internal | |
|
242 | /// computation. This is typically faster if more information is | |
|
243 | /// available in `self.common`. Therefore, for good performance, the | |
|
244 | /// caller should avoid calling this too early. | |
|
236 | 245 | pub fn add_missing_revisions( |
|
237 | 246 | &mut self, |
|
238 | 247 | missing: impl IntoIterator<Item = Revision>, |
|
239 | 248 | ) -> Result<(), GraphError> { |
|
240 |
self.ensure_ |
|
|
241 | let range = dagops::range( | |
|
242 | &self.graph, | |
|
243 | missing, | |
|
244 | self.undecided.as_ref().unwrap().iter().cloned(), | |
|
245 | )?; | |
|
249 | self.ensure_children_cache()?; | |
|
250 | self.ensure_undecided()?; // for safety of possible future refactors | |
|
251 | let children = self.children_cache.as_ref().unwrap(); | |
|
252 | let mut seen: HashSet<Revision> = HashSet::new(); | |
|
253 | let mut tovisit: VecDeque<Revision> = missing.into_iter().collect(); | |
|
246 | 254 | let undecided_mut = self.undecided.as_mut().unwrap(); |
|
247 | for missrev in range { | |
|
248 |
self.missing.insert( |
|
|
249 | undecided_mut.remove(&missrev); | |
|
255 | while let Some(rev) = tovisit.pop_front() { | |
|
256 | if !self.missing.insert(rev) { | |
|
257 | // either it's known to be missing from a previous | |
|
258 | // invocation, and there's no need to iterate on its | |
|
259 | // children (we now they are all missing) | |
|
260 | // or it's from a previous iteration of this loop | |
|
261 | // and its children have already been queued | |
|
262 | continue; | |
|
263 | } | |
|
264 | undecided_mut.remove(&rev); | |
|
265 | match children.get(&rev) { | |
|
266 | None => { | |
|
267 | continue; | |
|
268 | } | |
|
269 | Some(this_children) => { | |
|
270 | for child in this_children.iter().cloned() { | |
|
271 | if seen.insert(child) { | |
|
272 | tovisit.push_back(child); | |
|
273 | } | |
|
274 | } | |
|
275 | } | |
|
276 | } | |
|
250 | 277 | } |
|
251 | 278 | Ok(()) |
|
252 | 279 | } |
|
253 | 280 | |
|
254 | 281 | /// Do we have any information about the peer? |
|
255 | 282 | pub fn has_info(&self) -> bool { |
|
256 | 283 | self.common.has_bases() |
|
257 | 284 | } |
|
258 | 285 | |
|
259 | 286 | /// Did we acquire full knowledge of our Revisions that the peer has? |
|
260 | 287 | pub fn is_complete(&self) -> bool { |
|
261 | 288 | self.undecided.as_ref().map_or(false, |s| s.is_empty()) |
|
262 | 289 | } |
|
263 | 290 | |
|
264 | 291 | /// Return the heads of the currently known common set of revisions. |
|
265 | 292 | /// |
|
266 | 293 | /// If the discovery process is not complete (see `is_complete()`), the |
|
267 | 294 | /// caller must be aware that this is an intermediate state. |
|
268 | 295 | /// |
|
269 | 296 | /// On the other hand, if it is complete, then this is currently |
|
270 | 297 | /// the only way to retrieve the end results of the discovery process. |
|
271 | 298 | /// |
|
272 | 299 | /// We may introduce in the future an `into_common_heads` call that |
|
273 | 300 | /// would be more appropriate for normal Rust callers, dropping `self` |
|
274 | 301 | /// if it is complete. |
|
275 | 302 | pub fn common_heads(&self) -> Result<HashSet<Revision>, GraphError> { |
|
276 | 303 | self.common.bases_heads() |
|
277 | 304 | } |
|
278 | 305 | |
|
279 | 306 | /// Force first computation of `self.undecided` |
|
280 | 307 | /// |
|
281 | 308 | /// After this, `self.undecided.as_ref()` and `.as_mut()` can be |
|
282 | 309 | /// unwrapped to get workable immutable or mutable references without |
|
283 | 310 | /// any panic. |
|
284 | 311 | /// |
|
285 | 312 | /// This is an imperative call instead of an access with added lazyness |
|
286 | 313 | /// to reduce easily the scope of mutable borrow for the caller, |
|
287 | 314 | /// compared to undecided(&'a mut self) -> &'a⦠that would keep it |
|
288 | 315 | /// as long as the resulting immutable one. |
|
289 | 316 | fn ensure_undecided(&mut self) -> Result<(), GraphError> { |
|
290 | 317 | if self.undecided.is_some() { |
|
291 | 318 | return Ok(()); |
|
292 | 319 | } |
|
293 | 320 | let tgt = self.target_heads.take().unwrap(); |
|
294 | 321 | self.undecided = |
|
295 | 322 | Some(self.common.missing_ancestors(tgt)?.into_iter().collect()); |
|
296 | 323 | Ok(()) |
|
297 | 324 | } |
|
298 | 325 | |
|
299 | 326 | fn ensure_children_cache(&mut self) -> Result<(), GraphError> { |
|
300 | 327 | if self.children_cache.is_some() { |
|
301 | 328 | return Ok(()); |
|
302 | 329 | } |
|
303 | 330 | self.ensure_undecided()?; |
|
304 | 331 | |
|
305 | 332 | let mut children: HashMap<Revision, Vec<Revision>> = HashMap::new(); |
|
306 | 333 | for &rev in self.undecided.as_ref().unwrap() { |
|
307 | 334 | for p in ParentsIterator::graph_parents(&self.graph, rev)? { |
|
308 | 335 | children.entry(p).or_insert_with(|| Vec::new()).push(rev); |
|
309 | 336 | } |
|
310 | 337 | } |
|
311 | 338 | self.children_cache = Some(children); |
|
312 | 339 | Ok(()) |
|
313 | 340 | } |
|
314 | 341 | |
|
315 | 342 | /// Provide statistics about the current state of the discovery process |
|
316 | 343 | pub fn stats(&self) -> DiscoveryStats { |
|
317 | 344 | DiscoveryStats { |
|
318 | 345 | undecided: self.undecided.as_ref().map(|s| s.len()), |
|
319 | 346 | } |
|
320 | 347 | } |
|
321 | 348 | |
|
322 | 349 | pub fn take_quick_sample( |
|
323 | 350 | &mut self, |
|
324 | 351 | headrevs: impl IntoIterator<Item = Revision>, |
|
325 | 352 | size: usize, |
|
326 | 353 | ) -> Result<Vec<Revision>, GraphError> { |
|
327 | 354 | self.ensure_undecided()?; |
|
328 | 355 | let mut sample = { |
|
329 | 356 | let undecided = self.undecided.as_ref().unwrap(); |
|
330 | 357 | if undecided.len() <= size { |
|
331 | 358 | return Ok(undecided.iter().cloned().collect()); |
|
332 | 359 | } |
|
333 | 360 | dagops::heads(&self.graph, undecided.iter())? |
|
334 | 361 | }; |
|
335 | 362 | if sample.len() >= size { |
|
336 | 363 | return Ok(self.limit_sample(sample.into_iter().collect(), size)); |
|
337 | 364 | } |
|
338 | 365 | update_sample( |
|
339 | 366 | None, |
|
340 | 367 | headrevs, |
|
341 | 368 | &mut sample, |
|
342 | 369 | |r| ParentsIterator::graph_parents(&self.graph, r), |
|
343 | 370 | Some(size), |
|
344 | 371 | )?; |
|
345 | 372 | Ok(sample.into_iter().collect()) |
|
346 | 373 | } |
|
347 | 374 | |
|
348 | 375 | /// Extract a sample from `self.undecided`, going from its heads and roots. |
|
349 | 376 | /// |
|
350 | 377 | /// The `size` parameter is used to avoid useless computations if |
|
351 | 378 | /// it turns out to be bigger than the whole set of undecided Revisions. |
|
352 | 379 | /// |
|
353 | 380 | /// The sample is taken by using `update_sample` from the heads, then |
|
354 | 381 | /// from the roots, working on the reverse DAG, |
|
355 | 382 | /// expressed by `self.children_cache`. |
|
356 | 383 | /// |
|
357 | 384 | /// No effort is being made to complete or limit the sample to `size` |
|
358 | 385 | /// but this method returns another interesting size that it derives |
|
359 | 386 | /// from its knowledge of the structure of the various sets, leaving |
|
360 | 387 | /// to the caller the decision to use it or not. |
|
361 | 388 | fn bidirectional_sample( |
|
362 | 389 | &mut self, |
|
363 | 390 | size: usize, |
|
364 | 391 | ) -> Result<(HashSet<Revision>, usize), GraphError> { |
|
365 | 392 | self.ensure_undecided()?; |
|
366 | 393 | { |
|
367 | 394 | // we don't want to compute children_cache before this |
|
368 | 395 | // but doing it after extracting self.undecided takes a mutable |
|
369 | 396 | // ref to self while a shareable one is still active. |
|
370 | 397 | let undecided = self.undecided.as_ref().unwrap(); |
|
371 | 398 | if undecided.len() <= size { |
|
372 | 399 | return Ok((undecided.clone(), size)); |
|
373 | 400 | } |
|
374 | 401 | } |
|
375 | 402 | |
|
376 | 403 | self.ensure_children_cache()?; |
|
377 | 404 | let revs = self.undecided.as_ref().unwrap(); |
|
378 | 405 | let mut sample: HashSet<Revision> = revs.clone(); |
|
379 | 406 | |
|
380 | 407 | // it's possible that leveraging the children cache would be more |
|
381 | 408 | // efficient here |
|
382 | 409 | dagops::retain_heads(&self.graph, &mut sample)?; |
|
383 | 410 | let revsheads = sample.clone(); // was again heads(revs) in python |
|
384 | 411 | |
|
385 | 412 | // update from heads |
|
386 | 413 | update_sample( |
|
387 | 414 | Some(revs), |
|
388 | 415 | revsheads.iter().cloned(), |
|
389 | 416 | &mut sample, |
|
390 | 417 | |r| ParentsIterator::graph_parents(&self.graph, r), |
|
391 | 418 | None, |
|
392 | 419 | )?; |
|
393 | 420 | |
|
394 | 421 | // update from roots |
|
395 | 422 | let revroots: HashSet<Revision> = |
|
396 | 423 | dagops::roots(&self.graph, revs)?.into_iter().collect(); |
|
397 | 424 | let prescribed_size = max(size, min(revroots.len(), revsheads.len())); |
|
398 | 425 | |
|
399 | 426 | let children = self.children_cache.as_ref().unwrap(); |
|
400 | 427 | let empty_vec: Vec<Revision> = Vec::new(); |
|
401 | 428 | update_sample( |
|
402 | 429 | Some(revs), |
|
403 | 430 | revroots, |
|
404 | 431 | &mut sample, |
|
405 | 432 | |r| Ok(children.get(&r).unwrap_or(&empty_vec).iter().cloned()), |
|
406 | 433 | None, |
|
407 | 434 | )?; |
|
408 | 435 | Ok((sample, prescribed_size)) |
|
409 | 436 | } |
|
410 | 437 | |
|
411 | 438 | /// Fill up sample up to the wished size with random undecided Revisions. |
|
412 | 439 | /// |
|
413 | 440 | /// This is intended to be used as a last resort completion if the |
|
414 | 441 | /// regular sampling algorithm returns too few elements. |
|
415 | 442 | fn random_complete_sample( |
|
416 | 443 | &mut self, |
|
417 | 444 | sample: &mut Vec<Revision>, |
|
418 | 445 | size: usize, |
|
419 | 446 | ) { |
|
420 | 447 | let sample_len = sample.len(); |
|
421 | 448 | if size <= sample_len { |
|
422 | 449 | return; |
|
423 | 450 | } |
|
424 | 451 | let take_from: Vec<Revision> = self |
|
425 | 452 | .undecided |
|
426 | 453 | .as_ref() |
|
427 | 454 | .unwrap() |
|
428 | 455 | .iter() |
|
429 | 456 | .filter(|&r| !sample.contains(r)) |
|
430 | 457 | .cloned() |
|
431 | 458 | .collect(); |
|
432 | 459 | sample.extend(self.limit_sample(take_from, size - sample_len)); |
|
433 | 460 | } |
|
434 | 461 | |
|
435 | 462 | pub fn take_full_sample( |
|
436 | 463 | &mut self, |
|
437 | 464 | size: usize, |
|
438 | 465 | ) -> Result<Vec<Revision>, GraphError> { |
|
439 | 466 | let (sample_set, prescribed_size) = self.bidirectional_sample(size)?; |
|
440 | 467 | let size = if self.respect_size { |
|
441 | 468 | size |
|
442 | 469 | } else { |
|
443 | 470 | prescribed_size |
|
444 | 471 | }; |
|
445 | 472 | let mut sample = |
|
446 | 473 | self.limit_sample(sample_set.into_iter().collect(), size); |
|
447 | 474 | self.random_complete_sample(&mut sample, size); |
|
448 | 475 | Ok(sample) |
|
449 | 476 | } |
|
450 | 477 | } |
|
451 | 478 | |
|
452 | 479 | #[cfg(test)] |
|
453 | 480 | mod tests { |
|
454 | 481 | use super::*; |
|
455 | 482 | use crate::testing::SampleGraph; |
|
456 | 483 | |
|
457 | 484 | /// A PartialDiscovery as for pushing all the heads of `SampleGraph` |
|
458 | 485 | /// |
|
459 | 486 | /// To avoid actual randomness in these tests, we give it a fixed |
|
460 | 487 | /// random seed, but by default we'll test the random version. |
|
461 | 488 | fn full_disco() -> PartialDiscovery<SampleGraph> { |
|
462 | 489 | PartialDiscovery::new_with_seed( |
|
463 | 490 | SampleGraph, |
|
464 | 491 | vec![10, 11, 12, 13], |
|
465 | 492 | [0; 16], |
|
466 | 493 | true, |
|
467 | 494 | true, |
|
468 | 495 | ) |
|
469 | 496 | } |
|
470 | 497 | |
|
471 | 498 | /// A PartialDiscovery as for pushing the 12 head of `SampleGraph` |
|
472 | 499 | /// |
|
473 | 500 | /// To avoid actual randomness in tests, we give it a fixed random seed. |
|
474 | 501 | fn disco12() -> PartialDiscovery<SampleGraph> { |
|
475 | 502 | PartialDiscovery::new_with_seed( |
|
476 | 503 | SampleGraph, |
|
477 | 504 | vec![12], |
|
478 | 505 | [0; 16], |
|
479 | 506 | true, |
|
480 | 507 | true, |
|
481 | 508 | ) |
|
482 | 509 | } |
|
483 | 510 | |
|
484 | 511 | fn sorted_undecided( |
|
485 | 512 | disco: &PartialDiscovery<SampleGraph>, |
|
486 | 513 | ) -> Vec<Revision> { |
|
487 | 514 | let mut as_vec: Vec<Revision> = |
|
488 | 515 | disco.undecided.as_ref().unwrap().iter().cloned().collect(); |
|
489 | 516 | as_vec.sort(); |
|
490 | 517 | as_vec |
|
491 | 518 | } |
|
492 | 519 | |
|
493 | 520 | fn sorted_missing(disco: &PartialDiscovery<SampleGraph>) -> Vec<Revision> { |
|
494 | 521 | let mut as_vec: Vec<Revision> = |
|
495 | 522 | disco.missing.iter().cloned().collect(); |
|
496 | 523 | as_vec.sort(); |
|
497 | 524 | as_vec |
|
498 | 525 | } |
|
499 | 526 | |
|
500 | 527 | fn sorted_common_heads( |
|
501 | 528 | disco: &PartialDiscovery<SampleGraph>, |
|
502 | 529 | ) -> Result<Vec<Revision>, GraphError> { |
|
503 | 530 | let mut as_vec: Vec<Revision> = |
|
504 | 531 | disco.common_heads()?.iter().cloned().collect(); |
|
505 | 532 | as_vec.sort(); |
|
506 | 533 | Ok(as_vec) |
|
507 | 534 | } |
|
508 | 535 | |
|
509 | 536 | #[test] |
|
510 | 537 | fn test_add_common_get_undecided() -> Result<(), GraphError> { |
|
511 | 538 | let mut disco = full_disco(); |
|
512 | 539 | assert_eq!(disco.undecided, None); |
|
513 | 540 | assert!(!disco.has_info()); |
|
514 | 541 | assert_eq!(disco.stats().undecided, None); |
|
515 | 542 | |
|
516 | 543 | disco.add_common_revisions(vec![11, 12])?; |
|
517 | 544 | assert!(disco.has_info()); |
|
518 | 545 | assert!(!disco.is_complete()); |
|
519 | 546 | assert!(disco.missing.is_empty()); |
|
520 | 547 | |
|
521 | 548 | // add_common_revisions did not trigger a premature computation |
|
522 | 549 | // of `undecided`, let's check that and ask for them |
|
523 | 550 | assert_eq!(disco.undecided, None); |
|
524 | 551 | disco.ensure_undecided()?; |
|
525 | 552 | assert_eq!(sorted_undecided(&disco), vec![5, 8, 10, 13]); |
|
526 | 553 | assert_eq!(disco.stats().undecided, Some(4)); |
|
527 | 554 | Ok(()) |
|
528 | 555 | } |
|
529 | 556 | |
|
530 | 557 | /// in this test, we pretend that our peer misses exactly (8+10):: |
|
531 | 558 | /// and we're comparing all our repo to it (as in a bare push) |
|
532 | 559 | #[test] |
|
533 | 560 | fn test_discovery() -> Result<(), GraphError> { |
|
534 | 561 | let mut disco = full_disco(); |
|
535 | 562 | disco.add_common_revisions(vec![11, 12])?; |
|
536 | 563 | disco.add_missing_revisions(vec![8, 10])?; |
|
537 | 564 | assert_eq!(sorted_undecided(&disco), vec![5]); |
|
538 | 565 | assert_eq!(sorted_missing(&disco), vec![8, 10, 13]); |
|
539 | 566 | assert!(!disco.is_complete()); |
|
540 | 567 | |
|
541 | 568 | disco.add_common_revisions(vec![5])?; |
|
542 | 569 | assert_eq!(sorted_undecided(&disco), vec![]); |
|
543 | 570 | assert_eq!(sorted_missing(&disco), vec![8, 10, 13]); |
|
544 | 571 | assert!(disco.is_complete()); |
|
545 | 572 | assert_eq!(sorted_common_heads(&disco)?, vec![5, 11, 12]); |
|
546 | 573 | Ok(()) |
|
547 | 574 | } |
|
548 | 575 | |
|
549 | 576 | #[test] |
|
577 | fn test_add_missing_early_continue() -> Result<(), GraphError> { | |
|
578 | eprintln!("test_add_missing_early_stop"); | |
|
579 | let mut disco = full_disco(); | |
|
580 | disco.add_common_revisions(vec![13, 3, 4])?; | |
|
581 | disco.ensure_children_cache()?; | |
|
582 | // 12 is grand-child of 6 through 9 | |
|
583 | // passing them in this order maximizes the chances of the | |
|
584 | // early continue to do the wrong thing | |
|
585 | disco.add_missing_revisions(vec![6, 9, 12])?; | |
|
586 | assert_eq!(sorted_undecided(&disco), vec![5, 7, 10, 11]); | |
|
587 | assert_eq!(sorted_missing(&disco), vec![6, 9, 12]); | |
|
588 | assert!(!disco.is_complete()); | |
|
589 | Ok(()) | |
|
590 | } | |
|
591 | ||
|
592 | #[test] | |
|
550 | 593 | fn test_limit_sample_no_need_to() { |
|
551 | 594 | let sample = vec![1, 2, 3, 4]; |
|
552 | 595 | assert_eq!(full_disco().limit_sample(sample, 10), vec![1, 2, 3, 4]); |
|
553 | 596 | } |
|
554 | 597 | |
|
555 | 598 | #[test] |
|
556 | 599 | fn test_limit_sample_less_than_half() { |
|
557 | 600 | assert_eq!(full_disco().limit_sample((1..6).collect(), 2), vec![4, 2]); |
|
558 | 601 | } |
|
559 | 602 | |
|
560 | 603 | #[test] |
|
561 | 604 | fn test_limit_sample_more_than_half() { |
|
562 | 605 | assert_eq!(full_disco().limit_sample((1..4).collect(), 2), vec![3, 2]); |
|
563 | 606 | } |
|
564 | 607 | |
|
565 | 608 | #[test] |
|
566 | 609 | fn test_limit_sample_no_random() { |
|
567 | 610 | let mut disco = full_disco(); |
|
568 | 611 | disco.randomize = false; |
|
569 | 612 | assert_eq!( |
|
570 | 613 | disco.limit_sample(vec![1, 8, 13, 5, 7, 3], 4), |
|
571 | 614 | vec![1, 3, 5, 7] |
|
572 | 615 | ); |
|
573 | 616 | } |
|
574 | 617 | |
|
575 | 618 | #[test] |
|
576 | 619 | fn test_quick_sample_enough_undecided_heads() -> Result<(), GraphError> { |
|
577 | 620 | let mut disco = full_disco(); |
|
578 | 621 | disco.undecided = Some((1..=13).collect()); |
|
579 | 622 | |
|
580 | 623 | let mut sample_vec = disco.take_quick_sample(vec![], 4)?; |
|
581 | 624 | sample_vec.sort(); |
|
582 | 625 | assert_eq!(sample_vec, vec![10, 11, 12, 13]); |
|
583 | 626 | Ok(()) |
|
584 | 627 | } |
|
585 | 628 | |
|
586 | 629 | #[test] |
|
587 | 630 | fn test_quick_sample_climbing_from_12() -> Result<(), GraphError> { |
|
588 | 631 | let mut disco = disco12(); |
|
589 | 632 | disco.ensure_undecided()?; |
|
590 | 633 | |
|
591 | 634 | let mut sample_vec = disco.take_quick_sample(vec![12], 4)?; |
|
592 | 635 | sample_vec.sort(); |
|
593 | 636 | // r12's only parent is r9, whose unique grand-parent through the |
|
594 | 637 | // diamond shape is r4. This ends there because the distance from r4 |
|
595 | 638 | // to the root is only 3. |
|
596 | 639 | assert_eq!(sample_vec, vec![4, 9, 12]); |
|
597 | 640 | Ok(()) |
|
598 | 641 | } |
|
599 | 642 | |
|
600 | 643 | #[test] |
|
601 | 644 | fn test_children_cache() -> Result<(), GraphError> { |
|
602 | 645 | let mut disco = full_disco(); |
|
603 | 646 | disco.ensure_children_cache()?; |
|
604 | 647 | |
|
605 | 648 | let cache = disco.children_cache.unwrap(); |
|
606 | 649 | assert_eq!(cache.get(&2).cloned(), Some(vec![4])); |
|
607 | 650 | assert_eq!(cache.get(&10).cloned(), None); |
|
608 | 651 | |
|
609 | 652 | let mut children_4 = cache.get(&4).cloned().unwrap(); |
|
610 | 653 | children_4.sort(); |
|
611 | 654 | assert_eq!(children_4, vec![5, 6, 7]); |
|
612 | 655 | |
|
613 | 656 | let mut children_7 = cache.get(&7).cloned().unwrap(); |
|
614 | 657 | children_7.sort(); |
|
615 | 658 | assert_eq!(children_7, vec![9, 11]); |
|
616 | 659 | |
|
617 | 660 | Ok(()) |
|
618 | 661 | } |
|
619 | 662 | |
|
620 | 663 | #[test] |
|
621 | 664 | fn test_complete_sample() { |
|
622 | 665 | let mut disco = full_disco(); |
|
623 | 666 | let undecided: HashSet<Revision> = |
|
624 | 667 | [4, 7, 9, 2, 3].iter().cloned().collect(); |
|
625 | 668 | disco.undecided = Some(undecided); |
|
626 | 669 | |
|
627 | 670 | let mut sample = vec![0]; |
|
628 | 671 | disco.random_complete_sample(&mut sample, 3); |
|
629 | 672 | assert_eq!(sample.len(), 3); |
|
630 | 673 | |
|
631 | 674 | let mut sample = vec![2, 4, 7]; |
|
632 | 675 | disco.random_complete_sample(&mut sample, 1); |
|
633 | 676 | assert_eq!(sample.len(), 3); |
|
634 | 677 | } |
|
635 | 678 | |
|
636 | 679 | #[test] |
|
637 | 680 | fn test_bidirectional_sample() -> Result<(), GraphError> { |
|
638 | 681 | let mut disco = full_disco(); |
|
639 | 682 | disco.undecided = Some((0..=13).into_iter().collect()); |
|
640 | 683 | |
|
641 | 684 | let (sample_set, size) = disco.bidirectional_sample(7)?; |
|
642 | 685 | assert_eq!(size, 7); |
|
643 | 686 | let mut sample: Vec<Revision> = sample_set.into_iter().collect(); |
|
644 | 687 | sample.sort(); |
|
645 | 688 | // our DAG is a bit too small for the results to be really interesting |
|
646 | 689 | // at least it shows that |
|
647 | 690 | // - we went both ways |
|
648 | 691 | // - we didn't take all Revisions (6 is not in the sample) |
|
649 | 692 | assert_eq!(sample, vec![0, 1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 12, 13]); |
|
650 | 693 | Ok(()) |
|
651 | 694 | } |
|
652 | 695 | |
|
653 | 696 | } |
General Comments 0
You need to be logged in to leave comments.
Login now