231 } |
231 } |
232 Ok(()) |
232 Ok(()) |
233 } |
233 } |
234 |
234 |
235 /// Register revisions known as being missing |
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 pub fn add_missing_revisions( |
245 pub fn add_missing_revisions( |
237 &mut self, |
246 &mut self, |
238 missing: impl IntoIterator<Item = Revision>, |
247 missing: impl IntoIterator<Item = Revision>, |
239 ) -> Result<(), GraphError> { |
248 ) -> Result<(), GraphError> { |
240 self.ensure_undecided()?; |
249 self.ensure_children_cache()?; |
241 let range = dagops::range( |
250 self.ensure_undecided()?; // for safety of possible future refactors |
242 &self.graph, |
251 let children = self.children_cache.as_ref().unwrap(); |
243 missing, |
252 let mut seen: HashSet<Revision> = HashSet::new(); |
244 self.undecided.as_ref().unwrap().iter().cloned(), |
253 let mut tovisit: VecDeque<Revision> = missing.into_iter().collect(); |
245 )?; |
|
246 let undecided_mut = self.undecided.as_mut().unwrap(); |
254 let undecided_mut = self.undecided.as_mut().unwrap(); |
247 for missrev in range { |
255 while let Some(rev) = tovisit.pop_front() { |
248 self.missing.insert(missrev); |
256 if !self.missing.insert(rev) { |
249 undecided_mut.remove(&missrev); |
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 Ok(()) |
278 Ok(()) |
252 } |
279 } |
253 |
280 |
254 /// Do we have any information about the peer? |
281 /// Do we have any information about the peer? |
545 assert_eq!(sorted_common_heads(&disco)?, vec![5, 11, 12]); |
572 assert_eq!(sorted_common_heads(&disco)?, vec![5, 11, 12]); |
546 Ok(()) |
573 Ok(()) |
547 } |
574 } |
548 |
575 |
549 #[test] |
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 fn test_limit_sample_no_need_to() { |
593 fn test_limit_sample_no_need_to() { |
551 let sample = vec![1, 2, 3, 4]; |
594 let sample = vec![1, 2, 3, 4]; |
552 assert_eq!(full_disco().limit_sample(sample, 10), vec![1, 2, 3, 4]); |
595 assert_eq!(full_disco().limit_sample(sample, 10), vec![1, 2, 3, 4]); |
553 } |
596 } |
554 |
597 |