hg/
ancestors.rs

1// ancestors.rs
2//
3// Copyright 2018 Georges Racinet <gracinet@anybox.fr>
4//
5// This software may be used and distributed according to the terms of the
6// GNU General Public License version 2 or any later version.
7
8//! Rust versions of generic DAG ancestors algorithms for Mercurial
9
10use super::{Graph, GraphError, Revision, NULL_REVISION};
11use std::cmp::max;
12use std::collections::{BinaryHeap, HashSet};
13use crate::dagops;
14
15/// Iterator over the ancestors of a given list of revisions
16/// This is a generic type, defined and implemented for any Graph, so that
17/// it's easy to
18///
19/// - unit test in pure Rust
20/// - bind to main Mercurial code, potentially in several ways and have these
21///   bindings evolve over time
22pub struct AncestorsIterator<G: Graph> {
23    graph: G,
24    visit: BinaryHeap<Revision>,
25    seen: HashSet<Revision>,
26    stoprev: Revision,
27}
28
29/// Lazy ancestors set, backed by AncestorsIterator
30pub struct LazyAncestors<G: Graph + Clone> {
31    graph: G,
32    containsiter: AncestorsIterator<G>,
33    initrevs: Vec<Revision>,
34    stoprev: Revision,
35    inclusive: bool,
36}
37
38pub struct MissingAncestors<G: Graph> {
39    graph: G,
40    bases: HashSet<Revision>,
41    max_base: Revision,
42}
43
44impl<G: Graph> AncestorsIterator<G> {
45    /// Constructor.
46    ///
47    /// if `inclusive` is true, then the init revisions are emitted in
48    /// particular, otherwise iteration starts from their parents.
49    pub fn new(
50        graph: G,
51        initrevs: impl IntoIterator<Item = Revision>,
52        stoprev: Revision,
53        inclusive: bool,
54    ) -> Result<Self, GraphError> {
55        let filtered_initrevs = initrevs.into_iter().filter(|&r| r >= stoprev);
56        if inclusive {
57            let visit: BinaryHeap<Revision> = filtered_initrevs.collect();
58            let seen = visit.iter().map(|&x| x).collect();
59            return Ok(AncestorsIterator {
60                visit: visit,
61                seen: seen,
62                stoprev: stoprev,
63                graph: graph,
64            });
65        }
66        let mut this = AncestorsIterator {
67            visit: BinaryHeap::new(),
68            seen: HashSet::new(),
69            stoprev: stoprev,
70            graph: graph,
71        };
72        this.seen.insert(NULL_REVISION);
73        for rev in filtered_initrevs {
74            for parent in this.graph.parents(rev)?.iter().cloned() {
75                this.conditionally_push_rev(parent);
76            }
77        }
78        Ok(this)
79    }
80
81    #[inline]
82    fn conditionally_push_rev(&mut self, rev: Revision) {
83        if self.stoprev <= rev && self.seen.insert(rev) {
84            self.visit.push(rev);
85        }
86    }
87
88    /// Consumes partially the iterator to tell if the given target
89    /// revision
90    /// is in the ancestors it emits.
91    /// This is meant for iterators actually dedicated to that kind of
92    /// purpose
93    pub fn contains(&mut self, target: Revision) -> Result<bool, GraphError> {
94        if self.seen.contains(&target) && target != NULL_REVISION {
95            return Ok(true);
96        }
97        for item in self {
98            let rev = item?;
99            if rev == target {
100                return Ok(true);
101            }
102            if rev < target {
103                return Ok(false);
104            }
105        }
106        Ok(false)
107    }
108
109    pub fn peek(&self) -> Option<Revision> {
110        self.visit.peek().map(|&r| r)
111    }
112
113    /// Tell if the iterator is about an empty set
114    ///
115    /// The result does not depend whether the iterator has been consumed
116    /// or not.
117    /// This is mostly meant for iterators backing a lazy ancestors set
118    pub fn is_empty(&self) -> bool {
119        if self.visit.len() > 0 {
120            return false;
121        }
122        if self.seen.len() > 1 {
123            return false;
124        }
125        // at this point, the seen set is at most a singleton.
126        // If not `self.inclusive`, it's still possible that it has only
127        // the null revision
128        self.seen.is_empty() || self.seen.contains(&NULL_REVISION)
129    }
130}
131
132/// Main implementation for the iterator
133///
134/// The algorithm is the same as in `_lazyancestorsiter()` from `ancestors.py`
135/// with a few non crucial differences:
136///
137/// - there's no filtering of invalid parent revisions. Actually, it should be
138///   consistent and more efficient to filter them from the end caller.
139/// - we don't have the optimization for adjacent revisions (i.e., the case
140///   where `p1 == rev - 1`), because it amounts to update the first element of
141///   the heap without sifting, which Rust's BinaryHeap doesn't let us do.
142/// - we save a few pushes by comparing with `stoprev` before pushing
143impl<G: Graph> Iterator for AncestorsIterator<G> {
144    type Item = Result<Revision, GraphError>;
145
146    fn next(&mut self) -> Option<Self::Item> {
147        let current = match self.visit.peek() {
148            None => {
149                return None;
150            }
151            Some(c) => *c,
152        };
153        let [p1, p2] = match self.graph.parents(current) {
154            Ok(ps) => ps,
155            Err(e) => return Some(Err(e)),
156        };
157        if p1 < self.stoprev || !self.seen.insert(p1) {
158            self.visit.pop();
159        } else {
160            *(self.visit.peek_mut().unwrap()) = p1;
161        };
162
163        self.conditionally_push_rev(p2);
164        Some(Ok(current))
165    }
166}
167
168impl<G: Graph + Clone> LazyAncestors<G> {
169    pub fn new(
170        graph: G,
171        initrevs: impl IntoIterator<Item = Revision>,
172        stoprev: Revision,
173        inclusive: bool,
174    ) -> Result<Self, GraphError> {
175        let v: Vec<Revision> = initrevs.into_iter().collect();
176        Ok(LazyAncestors {
177            graph: graph.clone(),
178            containsiter: AncestorsIterator::new(
179                graph,
180                v.iter().cloned(),
181                stoprev,
182                inclusive,
183            )?,
184            initrevs: v,
185            stoprev: stoprev,
186            inclusive: inclusive,
187        })
188    }
189
190    pub fn contains(&mut self, rev: Revision) -> Result<bool, GraphError> {
191        self.containsiter.contains(rev)
192    }
193
194    pub fn is_empty(&self) -> bool {
195        self.containsiter.is_empty()
196    }
197
198    pub fn iter(&self) -> AncestorsIterator<G> {
199        // the arguments being the same as for self.containsiter, we know
200        // for sure that AncestorsIterator constructor can't fail
201        AncestorsIterator::new(
202            self.graph.clone(),
203            self.initrevs.iter().cloned(),
204            self.stoprev,
205            self.inclusive,
206        )
207        .unwrap()
208    }
209}
210
211impl<G: Graph> MissingAncestors<G> {
212    pub fn new(graph: G, bases: impl IntoIterator<Item = Revision>) -> Self {
213        let mut created = MissingAncestors {
214            graph: graph,
215            bases: HashSet::new(),
216            max_base: NULL_REVISION,
217        };
218        created.add_bases(bases);
219        created
220    }
221
222    pub fn has_bases(&self) -> bool {
223        !self.bases.is_empty()
224    }
225
226    /// Return a reference to current bases.
227    ///
228    /// This is useful in unit tests, but also setdiscovery.py does
229    /// read the bases attribute of a ancestor.missingancestors instance.
230    pub fn get_bases<'a>(&'a self) -> &'a HashSet<Revision> {
231        &self.bases
232    }
233
234    /// Computes the relative heads of current bases.
235    ///
236    /// The object is still usable after this.
237    pub fn bases_heads(&self) -> Result<HashSet<Revision>, GraphError> {
238        dagops::heads(&self.graph, self.bases.iter())
239    }
240
241    /// Consumes the object and returns the relative heads of its bases.
242    pub fn into_bases_heads(
243        mut self,
244    ) -> Result<HashSet<Revision>, GraphError> {
245        dagops::retain_heads(&self.graph, &mut self.bases)?;
246        Ok(self.bases)
247    }
248
249    /// Add some revisions to `self.bases`
250    ///
251    /// Takes care of keeping `self.max_base` up to date.
252    pub fn add_bases(
253        &mut self,
254        new_bases: impl IntoIterator<Item = Revision>,
255    ) {
256        let mut max_base = self.max_base;
257        self.bases.extend(
258            new_bases
259                .into_iter()
260                .filter(|&rev| rev != NULL_REVISION)
261                .map(|r| {
262                    if r > max_base {
263                        max_base = r;
264                    }
265                    r
266                }),
267        );
268        self.max_base = max_base;
269    }
270
271    /// Remove all ancestors of self.bases from the revs set (in place)
272    pub fn remove_ancestors_from(
273        &mut self,
274        revs: &mut HashSet<Revision>,
275    ) -> Result<(), GraphError> {
276        revs.retain(|r| !self.bases.contains(r));
277        // the null revision is always an ancestor. Logically speaking
278        // it's debatable in case bases is empty, but the Python
279        // implementation always adds NULL_REVISION to bases, making it
280        // unconditionnally true.
281        revs.remove(&NULL_REVISION);
282        if revs.is_empty() {
283            return Ok(());
284        }
285        // anything in revs > start is definitely not an ancestor of bases
286        // revs <= start need to be investigated
287        if self.max_base == NULL_REVISION {
288            return Ok(());
289        }
290
291        // whatever happens, we'll keep at least keepcount of them
292        // knowing this gives us a earlier stop condition than
293        // going all the way to the root
294        let keepcount = revs.iter().filter(|r| **r > self.max_base).count();
295
296        let mut curr = self.max_base;
297        while curr != NULL_REVISION && revs.len() > keepcount {
298            if self.bases.contains(&curr) {
299                revs.remove(&curr);
300                self.add_parents(curr)?;
301            }
302            curr -= 1;
303        }
304        Ok(())
305    }
306
307    /// Add the parents of `rev` to `self.bases`
308    ///
309    /// This has no effect on `self.max_base`
310    #[inline]
311    fn add_parents(&mut self, rev: Revision) -> Result<(), GraphError> {
312        if rev == NULL_REVISION {
313            return Ok(());
314        }
315        for p in self.graph.parents(rev)?.iter().cloned() {
316            // No need to bother the set with inserting NULL_REVISION over and
317            // over
318            if p != NULL_REVISION {
319                self.bases.insert(p);
320            }
321        }
322        Ok(())
323    }
324
325    /// Return all the ancestors of revs that are not ancestors of self.bases
326    ///
327    /// This may include elements from revs.
328    ///
329    /// Equivalent to the revset (::revs - ::self.bases). Revs are returned in
330    /// revision number order, which is a topological order.
331    pub fn missing_ancestors(
332        &mut self,
333        revs: impl IntoIterator<Item = Revision>,
334    ) -> Result<Vec<Revision>, GraphError> {
335        // just for convenience and comparison with Python version
336        let bases_visit = &mut self.bases;
337        let mut revs: HashSet<Revision> = revs
338            .into_iter()
339            .filter(|r| !bases_visit.contains(r))
340            .collect();
341        let revs_visit = &mut revs;
342        let mut both_visit: HashSet<Revision> =
343            revs_visit.intersection(&bases_visit).cloned().collect();
344        if revs_visit.is_empty() {
345            return Ok(Vec::new());
346        }
347        let max_revs = revs_visit.iter().cloned().max().unwrap();
348        let start = max(self.max_base, max_revs);
349
350        // TODO heuristics for with_capacity()?
351        let mut missing: Vec<Revision> = Vec::new();
352        for curr in (0..=start).rev() {
353            if revs_visit.is_empty() {
354                break;
355            }
356            if both_visit.remove(&curr) {
357                // curr's parents might have made it into revs_visit through
358                // another path
359                for p in self.graph.parents(curr)?.iter().cloned() {
360                    if p == NULL_REVISION {
361                        continue;
362                    }
363                    revs_visit.remove(&p);
364                    bases_visit.insert(p);
365                    both_visit.insert(p);
366                }
367            } else if revs_visit.remove(&curr) {
368                missing.push(curr);
369                for p in self.graph.parents(curr)?.iter().cloned() {
370                    if p == NULL_REVISION {
371                        continue;
372                    }
373                    if bases_visit.contains(&p) {
374                        // p is already known to be an ancestor of revs_visit
375                        revs_visit.remove(&p);
376                        both_visit.insert(p);
377                    } else if both_visit.contains(&p) {
378                        // p should have been in bases_visit
379                        revs_visit.remove(&p);
380                        bases_visit.insert(p);
381                    } else {
382                        // visit later
383                        revs_visit.insert(p);
384                    }
385                }
386            } else if bases_visit.contains(&curr) {
387                for p in self.graph.parents(curr)?.iter().cloned() {
388                    if p == NULL_REVISION {
389                        continue;
390                    }
391                    if revs_visit.remove(&p) || both_visit.contains(&p) {
392                        // p is an ancestor of bases_visit, and is implicitly
393                        // in revs_visit, which means p is ::revs & ::bases.
394                        bases_visit.insert(p);
395                        both_visit.insert(p);
396                    } else {
397                        bases_visit.insert(p);
398                    }
399                }
400            }
401        }
402        missing.reverse();
403        Ok(missing)
404    }
405}
406
407#[cfg(test)]
408mod tests {
409
410    use super::*;
411    use crate::testing::{SampleGraph, VecGraph};
412    use std::iter::FromIterator;
413
414    fn list_ancestors<G: Graph>(
415        graph: G,
416        initrevs: Vec<Revision>,
417        stoprev: Revision,
418        inclusive: bool,
419    ) -> Vec<Revision> {
420        AncestorsIterator::new(graph, initrevs, stoprev, inclusive)
421            .unwrap()
422            .map(|res| res.unwrap())
423            .collect()
424    }
425
426    #[test]
427    /// Same tests as test-ancestor.py, without membership
428    /// (see also test-ancestor.py.out)
429    fn test_list_ancestor() {
430        assert_eq!(list_ancestors(SampleGraph, vec![], 0, false), vec![]);
431        assert_eq!(
432            list_ancestors(SampleGraph, vec![11, 13], 0, false),
433            vec![8, 7, 4, 3, 2, 1, 0]
434        );
435        assert_eq!(
436            list_ancestors(SampleGraph, vec![1, 3], 0, false),
437            vec![1, 0]
438        );
439        assert_eq!(
440            list_ancestors(SampleGraph, vec![11, 13], 0, true),
441            vec![13, 11, 8, 7, 4, 3, 2, 1, 0]
442        );
443        assert_eq!(
444            list_ancestors(SampleGraph, vec![11, 13], 6, false),
445            vec![8, 7]
446        );
447        assert_eq!(
448            list_ancestors(SampleGraph, vec![11, 13], 6, true),
449            vec![13, 11, 8, 7]
450        );
451        assert_eq!(
452            list_ancestors(SampleGraph, vec![11, 13], 11, true),
453            vec![13, 11]
454        );
455        assert_eq!(
456            list_ancestors(SampleGraph, vec![11, 13], 12, true),
457            vec![13]
458        );
459        assert_eq!(
460            list_ancestors(SampleGraph, vec![10, 1], 0, true),
461            vec![10, 5, 4, 2, 1, 0]
462        );
463    }
464
465    #[test]
466    /// Corner case that's not directly in test-ancestors.py, but
467    /// that happens quite often, as demonstrated by running the whole
468    /// suite.
469    /// For instance, run tests/test-obsolete-checkheads.t
470    fn test_nullrev_input() {
471        let mut iter =
472            AncestorsIterator::new(SampleGraph, vec![-1], 0, false).unwrap();
473        assert_eq!(iter.next(), None)
474    }
475
476    #[test]
477    fn test_contains() {
478        let mut lazy =
479            AncestorsIterator::new(SampleGraph, vec![10, 1], 0, true).unwrap();
480        assert!(lazy.contains(1).unwrap());
481        assert!(!lazy.contains(3).unwrap());
482
483        let mut lazy =
484            AncestorsIterator::new(SampleGraph, vec![0], 0, false).unwrap();
485        assert!(!lazy.contains(NULL_REVISION).unwrap());
486    }
487
488    #[test]
489    fn test_peek() {
490        let mut iter =
491            AncestorsIterator::new(SampleGraph, vec![10], 0, true).unwrap();
492        // peek() gives us the next value
493        assert_eq!(iter.peek(), Some(10));
494        // but it's not been consumed
495        assert_eq!(iter.next(), Some(Ok(10)));
496        // and iteration resumes normally
497        assert_eq!(iter.next(), Some(Ok(5)));
498
499        // let's drain the iterator to test peek() at the end
500        while iter.next().is_some() {}
501        assert_eq!(iter.peek(), None);
502    }
503
504    #[test]
505    fn test_empty() {
506        let mut iter =
507            AncestorsIterator::new(SampleGraph, vec![10], 0, true).unwrap();
508        assert!(!iter.is_empty());
509        while iter.next().is_some() {}
510        assert!(!iter.is_empty());
511
512        let iter =
513            AncestorsIterator::new(SampleGraph, vec![], 0, true).unwrap();
514        assert!(iter.is_empty());
515
516        // case where iter.seen == {NULL_REVISION}
517        let iter =
518            AncestorsIterator::new(SampleGraph, vec![0], 0, false).unwrap();
519        assert!(iter.is_empty());
520    }
521
522    /// A corrupted Graph, supporting error handling tests
523    #[derive(Clone, Debug)]
524    struct Corrupted;
525
526    impl Graph for Corrupted {
527        fn parents(&self, rev: Revision) -> Result<[Revision; 2], GraphError> {
528            match rev {
529                1 => Ok([0, -1]),
530                r => Err(GraphError::ParentOutOfRange(r)),
531            }
532        }
533    }
534
535    #[test]
536    fn test_initrev_out_of_range() {
537        // inclusive=false looks up initrev's parents right away
538        match AncestorsIterator::new(SampleGraph, vec![25], 0, false) {
539            Ok(_) => panic!("Should have been ParentOutOfRange"),
540            Err(e) => assert_eq!(e, GraphError::ParentOutOfRange(25)),
541        }
542    }
543
544    #[test]
545    fn test_next_out_of_range() {
546        // inclusive=false looks up initrev's parents right away
547        let mut iter =
548            AncestorsIterator::new(Corrupted, vec![1], 0, false).unwrap();
549        assert_eq!(iter.next(), Some(Err(GraphError::ParentOutOfRange(0))));
550    }
551
552    #[test]
553    fn test_lazy_iter_contains() {
554        let mut lazy =
555            LazyAncestors::new(SampleGraph, vec![11, 13], 0, false).unwrap();
556
557        let revs: Vec<Revision> = lazy.iter().map(|r| r.unwrap()).collect();
558        // compare with iterator tests on the same initial revisions
559        assert_eq!(revs, vec![8, 7, 4, 3, 2, 1, 0]);
560
561        // contains() results are correct, unaffected by the fact that
562        // we consumed entirely an iterator out of lazy
563        assert_eq!(lazy.contains(2), Ok(true));
564        assert_eq!(lazy.contains(9), Ok(false));
565    }
566
567    #[test]
568    fn test_lazy_contains_iter() {
569        let mut lazy =
570            LazyAncestors::new(SampleGraph, vec![11, 13], 0, false).unwrap(); // reminder: [8, 7, 4, 3, 2, 1, 0]
571
572        assert_eq!(lazy.contains(2), Ok(true));
573        assert_eq!(lazy.contains(6), Ok(false));
574
575        // after consumption of 2 by the inner iterator, results stay
576        // consistent
577        assert_eq!(lazy.contains(2), Ok(true));
578        assert_eq!(lazy.contains(5), Ok(false));
579
580        // iter() still gives us a fresh iterator
581        let revs: Vec<Revision> = lazy.iter().map(|r| r.unwrap()).collect();
582        assert_eq!(revs, vec![8, 7, 4, 3, 2, 1, 0]);
583    }
584
585    #[test]
586    /// Test constructor, add/get bases and heads
587    fn test_missing_bases() -> Result<(), GraphError> {
588        let mut missing_ancestors =
589            MissingAncestors::new(SampleGraph, [5, 3, 1, 3].iter().cloned());
590        let mut as_vec: Vec<Revision> =
591            missing_ancestors.get_bases().iter().cloned().collect();
592        as_vec.sort();
593        assert_eq!(as_vec, [1, 3, 5]);
594        assert_eq!(missing_ancestors.max_base, 5);
595
596        missing_ancestors.add_bases([3, 7, 8].iter().cloned());
597        as_vec = missing_ancestors.get_bases().iter().cloned().collect();
598        as_vec.sort();
599        assert_eq!(as_vec, [1, 3, 5, 7, 8]);
600        assert_eq!(missing_ancestors.max_base, 8);
601
602        as_vec = missing_ancestors.bases_heads()?.iter().cloned().collect();
603        as_vec.sort();
604        assert_eq!(as_vec, [3, 5, 7, 8]);
605        Ok(())
606    }
607
608    fn assert_missing_remove(
609        bases: &[Revision],
610        revs: &[Revision],
611        expected: &[Revision],
612    ) {
613        let mut missing_ancestors =
614            MissingAncestors::new(SampleGraph, bases.iter().cloned());
615        let mut revset: HashSet<Revision> = revs.iter().cloned().collect();
616        missing_ancestors
617            .remove_ancestors_from(&mut revset)
618            .unwrap();
619        let mut as_vec: Vec<Revision> = revset.into_iter().collect();
620        as_vec.sort();
621        assert_eq!(as_vec.as_slice(), expected);
622    }
623
624    #[test]
625    fn test_missing_remove() {
626        assert_missing_remove(
627            &[1, 2, 3, 4, 7],
628            Vec::from_iter(1..10).as_slice(),
629            &[5, 6, 8, 9],
630        );
631        assert_missing_remove(&[10], &[11, 12, 13, 14], &[11, 12, 13, 14]);
632        assert_missing_remove(&[7], &[1, 2, 3, 4, 5], &[3, 5]);
633    }
634
635    fn assert_missing_ancestors(
636        bases: &[Revision],
637        revs: &[Revision],
638        expected: &[Revision],
639    ) {
640        let mut missing_ancestors =
641            MissingAncestors::new(SampleGraph, bases.iter().cloned());
642        let missing = missing_ancestors
643            .missing_ancestors(revs.iter().cloned())
644            .unwrap();
645        assert_eq!(missing.as_slice(), expected);
646    }
647
648    #[test]
649    fn test_missing_ancestors() {
650        // examples taken from test-ancestors.py by having it run
651        // on the same graph (both naive and fast Python algs)
652        assert_missing_ancestors(&[10], &[11], &[3, 7, 11]);
653        assert_missing_ancestors(&[11], &[10], &[5, 10]);
654        assert_missing_ancestors(&[7], &[9, 11], &[3, 6, 9, 11]);
655    }
656
657    /// An interesting case found by a random generator similar to
658    /// the one in test-ancestor.py. An early version of Rust MissingAncestors
659    /// failed this, yet none of the integration tests of the whole suite
660    /// catched it.
661    #[test]
662    fn test_remove_ancestors_from_case1() {
663        let graph: VecGraph = vec![
664            [NULL_REVISION, NULL_REVISION],
665            [0, NULL_REVISION],
666            [1, 0],
667            [2, 1],
668            [3, NULL_REVISION],
669            [4, NULL_REVISION],
670            [5, 1],
671            [2, NULL_REVISION],
672            [7, NULL_REVISION],
673            [8, NULL_REVISION],
674            [9, NULL_REVISION],
675            [10, 1],
676            [3, NULL_REVISION],
677            [12, NULL_REVISION],
678            [13, NULL_REVISION],
679            [14, NULL_REVISION],
680            [4, NULL_REVISION],
681            [16, NULL_REVISION],
682            [17, NULL_REVISION],
683            [18, NULL_REVISION],
684            [19, 11],
685            [20, NULL_REVISION],
686            [21, NULL_REVISION],
687            [22, NULL_REVISION],
688            [23, NULL_REVISION],
689            [2, NULL_REVISION],
690            [3, NULL_REVISION],
691            [26, 24],
692            [27, NULL_REVISION],
693            [28, NULL_REVISION],
694            [12, NULL_REVISION],
695            [1, NULL_REVISION],
696            [1, 9],
697            [32, NULL_REVISION],
698            [33, NULL_REVISION],
699            [34, 31],
700            [35, NULL_REVISION],
701            [36, 26],
702            [37, NULL_REVISION],
703            [38, NULL_REVISION],
704            [39, NULL_REVISION],
705            [40, NULL_REVISION],
706            [41, NULL_REVISION],
707            [42, 26],
708            [0, NULL_REVISION],
709            [44, NULL_REVISION],
710            [45, 4],
711            [40, NULL_REVISION],
712            [47, NULL_REVISION],
713            [36, 0],
714            [49, NULL_REVISION],
715            [NULL_REVISION, NULL_REVISION],
716            [51, NULL_REVISION],
717            [52, NULL_REVISION],
718            [53, NULL_REVISION],
719            [14, NULL_REVISION],
720            [55, NULL_REVISION],
721            [15, NULL_REVISION],
722            [23, NULL_REVISION],
723            [58, NULL_REVISION],
724            [59, NULL_REVISION],
725            [2, NULL_REVISION],
726            [61, 59],
727            [62, NULL_REVISION],
728            [63, NULL_REVISION],
729            [NULL_REVISION, NULL_REVISION],
730            [65, NULL_REVISION],
731            [66, NULL_REVISION],
732            [67, NULL_REVISION],
733            [68, NULL_REVISION],
734            [37, 28],
735            [69, 25],
736            [71, NULL_REVISION],
737            [72, NULL_REVISION],
738            [50, 2],
739            [74, NULL_REVISION],
740            [12, NULL_REVISION],
741            [18, NULL_REVISION],
742            [77, NULL_REVISION],
743            [78, NULL_REVISION],
744            [79, NULL_REVISION],
745            [43, 33],
746            [81, NULL_REVISION],
747            [82, NULL_REVISION],
748            [83, NULL_REVISION],
749            [84, 45],
750            [85, NULL_REVISION],
751            [86, NULL_REVISION],
752            [NULL_REVISION, NULL_REVISION],
753            [88, NULL_REVISION],
754            [NULL_REVISION, NULL_REVISION],
755            [76, 83],
756            [44, NULL_REVISION],
757            [92, NULL_REVISION],
758            [93, NULL_REVISION],
759            [9, NULL_REVISION],
760            [95, 67],
761            [96, NULL_REVISION],
762            [97, NULL_REVISION],
763            [NULL_REVISION, NULL_REVISION],
764        ];
765        let problem_rev = 28 as Revision;
766        let problem_base = 70 as Revision;
767        // making the problem obvious: problem_rev is a parent of problem_base
768        assert_eq!(graph.parents(problem_base).unwrap()[1], problem_rev);
769
770        let mut missing_ancestors: MissingAncestors<VecGraph> =
771            MissingAncestors::new(
772                graph,
773                [60, 26, 70, 3, 96, 19, 98, 49, 97, 47, 1, 6]
774                    .iter()
775                    .cloned(),
776            );
777        assert!(missing_ancestors.bases.contains(&problem_base));
778
779        let mut revs: HashSet<Revision> =
780            [4, 12, 41, 28, 68, 38, 1, 30, 56, 44]
781                .iter()
782                .cloned()
783                .collect();
784        missing_ancestors.remove_ancestors_from(&mut revs).unwrap();
785        assert!(!revs.contains(&problem_rev));
786    }
787
788}
hg/ancestors.rs

hg/
ancestors.rs
