Show More
@@ -233,20 +233,47 b' impl<G: Graph + Clone> PartialDiscovery<' | |||
|
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 | } |
@@ -547,6 +574,22 b' mod tests {' | |||
|
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]); |
General Comments 0
You need to be logged in to leave comments.
Login now