rust: itering less on MissingAncestors.bases for max()

Instead of iterating on the whole `self.bases` each time to find
its max, we keep the latter in a separate member attribute and
keep it up to date in `add_bases()`

On a perfdiscovery done on PyPy, with repos prepared with
`contrib/discovery-helper.sh 50 100`, this gives a slight
improvement (around 0.5% on wall time, but 10% on CPU)

before:
! wall 0.172801 comb 0.180000 user 0.180000 sys 0.000000 (median of 541)
after:
! wall 0.171798 comb 0.160000 user 0.160000 sys 0.000000 (median of 551)

(perf command run time upped because of bigger variability during this test).

Differential Revision: https://phab.mercurial-scm.org/D5945

rust/hg-core/src/ancestors.rs

@@ -1,766 +1,788 b''
 // ancestors.rs
 //
 // Copyright 2018 Georges Racinet <[e-mail]>
 //
 // This software may be used and distributed according to the terms of the
 // GNU General Public License version 2 or any later version.
 
 //! Rust versions of generic DAG ancestors algorithms for Mercurial
 
 use super::{Graph, GraphError, Revision, NULL_REVISION};
 use std::cmp::max;
 use std::collections::{BinaryHeap, HashSet};
 use crate::dagops;
 
 /// Iterator over the ancestors of a given list of revisions
 /// This is a generic type, defined and implemented for any Graph, so that
 /// it's easy to
 ///
 /// - unit test in pure Rust
 /// - bind to main Mercurial code, potentially in several ways and have these
 ///   bindings evolve over time
 pub struct AncestorsIterator<G: Graph> {
     graph: G,
     visit: BinaryHeap<Revision>,
     seen: HashSet<Revision>,
     stoprev: Revision,
 }
 
 /// Lazy ancestors set, backed by AncestorsIterator
 pub struct LazyAncestors<G: Graph + Clone> {
     graph: G,
     containsiter: AncestorsIterator<G>,
     initrevs: Vec<Revision>,
     stoprev: Revision,
     inclusive: bool,
 }
 
 pub struct MissingAncestors<G: Graph> {
     graph: G,
     bases: HashSet<Revision>,
+    max_base: Revision,
 }
 
 impl<G: Graph> AncestorsIterator<G> {
     /// Constructor.
     ///
     /// if `inclusive` is true, then the init revisions are emitted in
     /// particular, otherwise iteration starts from their parents.
     pub fn new(
         graph: G,
         initrevs: impl IntoIterator<Item = Revision>,
         stoprev: Revision,
         inclusive: bool,
     ) -> Result<Self, GraphError> {
         let filtered_initrevs = initrevs.into_iter().filter(|&r| r >= stoprev);
         if inclusive {
             let visit: BinaryHeap<Revision> = filtered_initrevs.collect();
             let seen = visit.iter().map(|&x| x).collect();
             return Ok(AncestorsIterator {
                 visit: visit,
                 seen: seen,
                 stoprev: stoprev,
                 graph: graph,
             });
         }
         let mut this = AncestorsIterator {
             visit: BinaryHeap::new(),
             seen: HashSet::new(),
             stoprev: stoprev,
             graph: graph,
         };
         this.seen.insert(NULL_REVISION);
         for rev in filtered_initrevs {
             for parent in this.graph.parents(rev)?.iter().cloned() {
                 this.conditionally_push_rev(parent);
             }
         }
         Ok(this)
     }
 
     #[inline]
     fn conditionally_push_rev(&mut self, rev: Revision) {
         if self.stoprev <= rev && self.seen.insert(rev) {
             self.visit.push(rev);
         }
     }
 
     /// Consumes partially the iterator to tell if the given target
     /// revision
     /// is in the ancestors it emits.
     /// This is meant for iterators actually dedicated to that kind of
     /// purpose
     pub fn contains(&mut self, target: Revision) -> Result<bool, GraphError> {
         if self.seen.contains(&target) && target != NULL_REVISION {
             return Ok(true);
         }
         for item in self {
             let rev = item?;
             if rev == target {
                 return Ok(true);
             }
             if rev < target {
                 return Ok(false);
             }
         }
         Ok(false)
     }
 
     pub fn peek(&self) -> Option<Revision> {
         self.visit.peek().map(|&r| r)
     }
 
     /// Tell if the iterator is about an empty set
     ///
     /// The result does not depend whether the iterator has been consumed
     /// or not.
     /// This is mostly meant for iterators backing a lazy ancestors set
     pub fn is_empty(&self) -> bool {
         if self.visit.len() > 0 {
             return false;
         }
         if self.seen.len() > 1 {
             return false;
         }
         // at this point, the seen set is at most a singleton.
         // If not `self.inclusive`, it's still possible that it has only
         // the null revision
         self.seen.is_empty() || self.seen.contains(&NULL_REVISION)
     }
 }
 
 /// Main implementation for the iterator
 ///
 /// The algorithm is the same as in `_lazyancestorsiter()` from `ancestors.py`
 /// with a few non crucial differences:
 ///
 /// - there's no filtering of invalid parent revisions. Actually, it should be
 ///   consistent and more efficient to filter them from the end caller.
 /// - we don't have the optimization for adjacent revisions (i.e., the case
 ///   where `p1 == rev - 1`), because it amounts to update the first element of
 ///   the heap without sifting, which Rust's BinaryHeap doesn't let us do.
 /// - we save a few pushes by comparing with `stoprev` before pushing
 impl<G: Graph> Iterator for AncestorsIterator<G> {
     type Item = Result<Revision, GraphError>;
 
     fn next(&mut self) -> Option<Self::Item> {
         let current = match self.visit.peek() {
             None => {
                 return None;
             }
             Some(c) => *c,
         };
         let [p1, p2] = match self.graph.parents(current) {
             Ok(ps) => ps,
             Err(e) => return Some(Err(e)),
         };
         if p1 < self.stoprev || !self.seen.insert(p1) {
             self.visit.pop();
         } else {
             *(self.visit.peek_mut().unwrap()) = p1;
         };
 
         self.conditionally_push_rev(p2);
         Some(Ok(current))
     }
 }
 
 impl<G: Graph + Clone> LazyAncestors<G> {
     pub fn new(
         graph: G,
         initrevs: impl IntoIterator<Item = Revision>,
         stoprev: Revision,
         inclusive: bool,
     ) -> Result<Self, GraphError> {
         let v: Vec<Revision> = initrevs.into_iter().collect();
         Ok(LazyAncestors {
             graph: graph.clone(),
             containsiter: AncestorsIterator::new(
                 graph,
                 v.iter().cloned(),
                 stoprev,
                 inclusive,
             )?,
             initrevs: v,
             stoprev: stoprev,
             inclusive: inclusive,
         })
     }
 
     pub fn contains(&mut self, rev: Revision) -> Result<bool, GraphError> {
         self.containsiter.contains(rev)
     }
 
     pub fn is_empty(&self) -> bool {
         self.containsiter.is_empty()
     }
 
     pub fn iter(&self) -> AncestorsIterator<G> {
         // the arguments being the same as for self.containsiter, we know
         // for sure that AncestorsIterator constructor can't fail
         AncestorsIterator::new(
             self.graph.clone(),
             self.initrevs.iter().cloned(),
             self.stoprev,
             self.inclusive,
         )
         .unwrap()
     }
 }
 
 impl<G: Graph> MissingAncestors<G> {
     pub fn new(graph: G, bases: impl IntoIterator<Item = Revision>) -> Self {
-        MissingAncestors { graph: graph, bases: bases.into_iter().collect() }
+        let mut created = MissingAncestors {
+            graph: graph,
+            bases: HashSet::new(),
+            max_base: NULL_REVISION,
+        };
+        created.add_bases(bases);
+        created
     }
 
     pub fn has_bases(&self) -> bool {
         !self.bases.is_empty()
     }
 
     /// Return a reference to current bases.
     ///
     /// This is useful in unit tests, but also setdiscovery.py does
     /// read the bases attribute of a ancestor.missingancestors instance.
     pub fn get_bases<'a>(&'a self) -> &'a HashSet<Revision> {
         &self.bases
     }
 
     /// Computes the relative heads of current bases.
     ///
     /// The object is still usable after this.
     pub fn bases_heads(&self) -> Result<HashSet<Revision>, GraphError> {
         dagops::heads(&self.graph, self.bases.iter())
     }
 
     /// Consumes the object and returns the relative heads of its bases.
-    pub fn into_bases_heads(mut self) -> Result<HashSet<Revision>, GraphError> {
+    pub fn into_bases_heads(
+        mut self,
+    ) -> Result<HashSet<Revision>, GraphError> {
         dagops::retain_heads(&self.graph, &mut self.bases)?;
         Ok(self.bases)
     }
 
+    /// Add some revisions to `self.bases`
+    ///
+    /// Takes care of keeping `self.max_base` up to date.
     pub fn add_bases(
         &mut self,
         new_bases: impl IntoIterator<Item = Revision>,
     ) {
-        self.bases
-            .extend(new_bases.into_iter().filter(|&rev| rev != NULL_REVISION));
+        let mut max_base = self.max_base;
+        self.bases.extend(
+            new_bases
+                .into_iter()
+                .filter(|&rev| rev != NULL_REVISION)
+                .map(|r| {
+                    if r > max_base {
+                        max_base = r;
+                    }
+                    r
+                }),
+        );
+        self.max_base = max_base;
     }
 
     /// Remove all ancestors of self.bases from the revs set (in place)
     pub fn remove_ancestors_from(
         &mut self,
         revs: &mut HashSet<Revision>,
     ) -> Result<(), GraphError> {
         revs.retain(|r| !self.bases.contains(r));
         // the null revision is always an ancestor. Logically speaking
         // it's debatable in case bases is empty, but the Python
         // implementation always adds NULL_REVISION to bases, making it
         // unconditionnally true.
         revs.remove(&NULL_REVISION);
         if revs.is_empty() {
             return Ok(());
         }
         // anything in revs > start is definitely not an ancestor of bases
         // revs <= start need to be investigated
-        // TODO optim: if a missingancestors is to be used several times,
-        // we shouldn't need to iterate each time on bases
-        let start = match self.bases.iter().cloned().max() {
-            Some(m) => m,
-            None => {  // self.bases is empty
+        if self.max_base == NULL_REVISION {
                 return Ok(());
             }
-        };
+
         // whatever happens, we'll keep at least keepcount of them
         // knowing this gives us a earlier stop condition than
         // going all the way to the root
-        let keepcount = revs.iter().filter(|r| **r > start).count();
+        let keepcount = revs.iter().filter(|r| **r > self.max_base).count();
 
-        let mut curr = start;
+        let mut curr = self.max_base;
         while curr != NULL_REVISION && revs.len() > keepcount {
             if self.bases.contains(&curr) {
                 revs.remove(&curr);
                 self.add_parents(curr)?;
             }
             curr -= 1;
         }
         Ok(())
     }
 
-    /// Add rev's parents to self.bases
+    /// Add the parents of `rev` to `self.bases`
+    ///
+    /// This has no effect on `self.max_base`
     #[inline]
     fn add_parents(&mut self, rev: Revision) -> Result<(), GraphError> {
+        if rev == NULL_REVISION {
+            return Ok(());
+        }
+        for p in self.graph.parents(rev)?.iter().cloned() {
         // No need to bother the set with inserting NULL_REVISION over and
         // over
-        for p in self.graph.parents(rev)?.iter().cloned() {
             if p != NULL_REVISION {
                 self.bases.insert(p);
             }
         }
         Ok(())
     }
 
     /// Return all the ancestors of revs that are not ancestors of self.bases
     ///
     /// This may include elements from revs.
     ///
     /// Equivalent to the revset (::revs - ::self.bases). Revs are returned in
     /// revision number order, which is a topological order.
     pub fn missing_ancestors(
         &mut self,
         revs: impl IntoIterator<Item = Revision>,
     ) -> Result<Vec<Revision>, GraphError> {
         // just for convenience and comparison with Python version
         let bases_visit = &mut self.bases;
         let mut revs: HashSet<Revision> = revs
             .into_iter()
             .filter(|r| !bases_visit.contains(r))
             .collect();
         let revs_visit = &mut revs;
         let mut both_visit: HashSet<Revision> =
             revs_visit.intersection(&bases_visit).cloned().collect();
         if revs_visit.is_empty() {
             return Ok(Vec::new());
         }
-
-        let max_bases =
-            bases_visit.iter().cloned().max().unwrap_or(NULL_REVISION);
-        let max_revs =
-            revs_visit.iter().cloned().max().unwrap_or(NULL_REVISION);
-        let start = max(max_bases, max_revs);
+        let max_revs = revs_visit.iter().cloned().max().unwrap();
+        let start = max(self.max_base, max_revs);
 
         // TODO heuristics for with_capacity()?
         let mut missing: Vec<Revision> = Vec::new();
         for curr in (0..=start).rev() {
             if revs_visit.is_empty() {
                 break;
             }
             if both_visit.remove(&curr) {
                 // curr's parents might have made it into revs_visit through
                 // another path
                 for p in self.graph.parents(curr)?.iter().cloned() {
                     if p == NULL_REVISION {
                         continue;
                     }
                     revs_visit.remove(&p);
                     bases_visit.insert(p);
                     both_visit.insert(p);
                 }
             } else if revs_visit.remove(&curr) {
                 missing.push(curr);
                 for p in self.graph.parents(curr)?.iter().cloned() {
                     if p == NULL_REVISION {
                         continue;
                     }
                     if bases_visit.contains(&p) {
                         // p is already known to be an ancestor of revs_visit
                         revs_visit.remove(&p);
                         both_visit.insert(p);
                     } else if both_visit.contains(&p) {
                         // p should have been in bases_visit
                         revs_visit.remove(&p);
                         bases_visit.insert(p);
                     } else {
                         // visit later
                         revs_visit.insert(p);
                     }
                 }
             } else if bases_visit.contains(&curr) {
                 for p in self.graph.parents(curr)?.iter().cloned() {
                     if p == NULL_REVISION {
                         continue;
                     }
                     if revs_visit.remove(&p) || both_visit.contains(&p) {
                         // p is an ancestor of bases_visit, and is implicitly
                         // in revs_visit, which means p is ::revs & ::bases.
                         bases_visit.insert(p);
                         both_visit.insert(p);
                     } else {
                         bases_visit.insert(p);
                     }
                 }
             }
         }
         missing.reverse();
         Ok(missing)
     }
 }
 
 #[cfg(test)]
 mod tests {
 
     use super::*;
     use crate::testing::{SampleGraph, VecGraph};
     use std::iter::FromIterator;
 
     fn list_ancestors<G: Graph>(
         graph: G,
         initrevs: Vec<Revision>,
         stoprev: Revision,
         inclusive: bool,
     ) -> Vec<Revision> {
         AncestorsIterator::new(graph, initrevs, stoprev, inclusive)
             .unwrap()
             .map(|res| res.unwrap())
             .collect()
     }
 
     #[test]
     /// Same tests as test-ancestor.py, without membership
     /// (see also test-ancestor.py.out)
     fn test_list_ancestor() {
         assert_eq!(list_ancestors(SampleGraph, vec![], 0, false), vec![]);
         assert_eq!(
             list_ancestors(SampleGraph, vec![11, 13], 0, false),
             vec![8, 7, 4, 3, 2, 1, 0]
         );
         assert_eq!(
             list_ancestors(SampleGraph, vec![1, 3], 0, false),
             vec![1, 0]
         );
         assert_eq!(
             list_ancestors(SampleGraph, vec![11, 13], 0, true),
             vec![13, 11, 8, 7, 4, 3, 2, 1, 0]
         );
         assert_eq!(
             list_ancestors(SampleGraph, vec![11, 13], 6, false),
             vec![8, 7]
         );
         assert_eq!(
             list_ancestors(SampleGraph, vec![11, 13], 6, true),
             vec![13, 11, 8, 7]
         );
         assert_eq!(
             list_ancestors(SampleGraph, vec![11, 13], 11, true),
             vec![13, 11]
         );
         assert_eq!(
             list_ancestors(SampleGraph, vec![11, 13], 12, true),
             vec![13]
         );
         assert_eq!(
             list_ancestors(SampleGraph, vec![10, 1], 0, true),
             vec![10, 5, 4, 2, 1, 0]
         );
     }
 
     #[test]
     /// Corner case that's not directly in test-ancestors.py, but
     /// that happens quite often, as demonstrated by running the whole
     /// suite.
     /// For instance, run tests/test-obsolete-checkheads.t
     fn test_nullrev_input() {
         let mut iter =
             AncestorsIterator::new(SampleGraph, vec![-1], 0, false).unwrap();
         assert_eq!(iter.next(), None)
     }
 
     #[test]
     fn test_contains() {
         let mut lazy =
             AncestorsIterator::new(SampleGraph, vec![10, 1], 0, true).unwrap();
         assert!(lazy.contains(1).unwrap());
         assert!(!lazy.contains(3).unwrap());
 
         let mut lazy =
             AncestorsIterator::new(SampleGraph, vec![0], 0, false).unwrap();
         assert!(!lazy.contains(NULL_REVISION).unwrap());
     }
 
     #[test]
     fn test_peek() {
         let mut iter =
             AncestorsIterator::new(SampleGraph, vec![10], 0, true).unwrap();
         // peek() gives us the next value
         assert_eq!(iter.peek(), Some(10));
         // but it's not been consumed
         assert_eq!(iter.next(), Some(Ok(10)));
         // and iteration resumes normally
         assert_eq!(iter.next(), Some(Ok(5)));
 
         // let's drain the iterator to test peek() at the end
         while iter.next().is_some() {}
         assert_eq!(iter.peek(), None);
     }
 
     #[test]
     fn test_empty() {
         let mut iter =
             AncestorsIterator::new(SampleGraph, vec![10], 0, true).unwrap();
         assert!(!iter.is_empty());
         while iter.next().is_some() {}
         assert!(!iter.is_empty());
 
         let iter =
             AncestorsIterator::new(SampleGraph, vec![], 0, true).unwrap();
         assert!(iter.is_empty());
 
         // case where iter.seen == {NULL_REVISION}
         let iter =
             AncestorsIterator::new(SampleGraph, vec![0], 0, false).unwrap();
         assert!(iter.is_empty());
     }
 
     /// A corrupted Graph, supporting error handling tests
     #[derive(Clone, Debug)]
     struct Corrupted;
 
     impl Graph for Corrupted {
         fn parents(&self, rev: Revision) -> Result<[Revision; 2], GraphError> {
             match rev {
                 1 => Ok([0, -1]),
                 r => Err(GraphError::ParentOutOfRange(r)),
             }
         }
     }
 
     #[test]
     fn test_initrev_out_of_range() {
         // inclusive=false looks up initrev's parents right away
         match AncestorsIterator::new(SampleGraph, vec![25], 0, false) {
             Ok(_) => panic!("Should have been ParentOutOfRange"),
             Err(e) => assert_eq!(e, GraphError::ParentOutOfRange(25)),
         }
     }
 
     #[test]
     fn test_next_out_of_range() {
         // inclusive=false looks up initrev's parents right away
         let mut iter =
             AncestorsIterator::new(Corrupted, vec![1], 0, false).unwrap();
         assert_eq!(iter.next(), Some(Err(GraphError::ParentOutOfRange(0))));
     }
 
     #[test]
     fn test_lazy_iter_contains() {
         let mut lazy =
             LazyAncestors::new(SampleGraph, vec![11, 13], 0, false).unwrap();
 
         let revs: Vec<Revision> = lazy.iter().map(|r| r.unwrap()).collect();
         // compare with iterator tests on the same initial revisions
         assert_eq!(revs, vec![8, 7, 4, 3, 2, 1, 0]);
 
         // contains() results are correct, unaffected by the fact that
         // we consumed entirely an iterator out of lazy
         assert_eq!(lazy.contains(2), Ok(true));
         assert_eq!(lazy.contains(9), Ok(false));
     }
 
     #[test]
     fn test_lazy_contains_iter() {
         let mut lazy =
             LazyAncestors::new(SampleGraph, vec![11, 13], 0, false).unwrap(); // reminder: [8, 7, 4, 3, 2, 1, 0]
 
         assert_eq!(lazy.contains(2), Ok(true));
         assert_eq!(lazy.contains(6), Ok(false));
 
         // after consumption of 2 by the inner iterator, results stay
         // consistent
         assert_eq!(lazy.contains(2), Ok(true));
         assert_eq!(lazy.contains(5), Ok(false));
 
         // iter() still gives us a fresh iterator
         let revs: Vec<Revision> = lazy.iter().map(|r| r.unwrap()).collect();
         assert_eq!(revs, vec![8, 7, 4, 3, 2, 1, 0]);
     }
 
     #[test]
     /// Test constructor, add/get bases and heads
     fn test_missing_bases() -> Result<(), GraphError> {
         let mut missing_ancestors =
             MissingAncestors::new(SampleGraph, [5, 3, 1, 3].iter().cloned());
         let mut as_vec: Vec<Revision> =
             missing_ancestors.get_bases().iter().cloned().collect();
         as_vec.sort();
         assert_eq!(as_vec, [1, 3, 5]);
+        assert_eq!(missing_ancestors.max_base, 5);
 
         missing_ancestors.add_bases([3, 7, 8].iter().cloned());
         as_vec = missing_ancestors.get_bases().iter().cloned().collect();
         as_vec.sort();
         assert_eq!(as_vec, [1, 3, 5, 7, 8]);
+        assert_eq!(missing_ancestors.max_base, 8);
 
         as_vec = missing_ancestors.bases_heads()?.iter().cloned().collect();
         as_vec.sort();
         assert_eq!(as_vec, [3, 5, 7, 8]);
         Ok(())
     }
 
     fn assert_missing_remove(
         bases: &[Revision],
         revs: &[Revision],
         expected: &[Revision],
     ) {
         let mut missing_ancestors =
             MissingAncestors::new(SampleGraph, bases.iter().cloned());
         let mut revset: HashSet<Revision> = revs.iter().cloned().collect();
         missing_ancestors
             .remove_ancestors_from(&mut revset)
             .unwrap();
         let mut as_vec: Vec<Revision> = revset.into_iter().collect();
         as_vec.sort();
         assert_eq!(as_vec.as_slice(), expected);
     }
 
     #[test]
     fn test_missing_remove() {
         assert_missing_remove(
             &[1, 2, 3, 4, 7],
             Vec::from_iter(1..10).as_slice(),
             &[5, 6, 8, 9],
         );
         assert_missing_remove(&[10], &[11, 12, 13, 14], &[11, 12, 13, 14]);
         assert_missing_remove(&[7], &[1, 2, 3, 4, 5], &[3, 5]);
     }
 
     fn assert_missing_ancestors(
         bases: &[Revision],
         revs: &[Revision],
         expected: &[Revision],
     ) {
         let mut missing_ancestors =
             MissingAncestors::new(SampleGraph, bases.iter().cloned());
         let missing = missing_ancestors
             .missing_ancestors(revs.iter().cloned())
             .unwrap();
         assert_eq!(missing.as_slice(), expected);
     }
 
     #[test]
     fn test_missing_ancestors() {
         // examples taken from test-ancestors.py by having it run
         // on the same graph (both naive and fast Python algs)
         assert_missing_ancestors(&[10], &[11], &[3, 7, 11]);
         assert_missing_ancestors(&[11], &[10], &[5, 10]);
         assert_missing_ancestors(&[7], &[9, 11], &[3, 6, 9, 11]);
     }
 
     /// An interesting case found by a random generator similar to
     /// the one in test-ancestor.py. An early version of Rust MissingAncestors
     /// failed this, yet none of the integration tests of the whole suite
     /// catched it.
     #[test]
     fn test_remove_ancestors_from_case1() {
         let graph: VecGraph = vec![
             [NULL_REVISION, NULL_REVISION],
             [0, NULL_REVISION],
             [1, 0],
             [2, 1],
             [3, NULL_REVISION],
             [4, NULL_REVISION],
             [5, 1],
             [2, NULL_REVISION],
             [7, NULL_REVISION],
             [8, NULL_REVISION],
             [9, NULL_REVISION],
             [10, 1],
             [3, NULL_REVISION],
             [12, NULL_REVISION],
             [13, NULL_REVISION],
             [14, NULL_REVISION],
             [4, NULL_REVISION],
             [16, NULL_REVISION],
             [17, NULL_REVISION],
             [18, NULL_REVISION],
             [19, 11],
             [20, NULL_REVISION],
             [21, NULL_REVISION],
             [22, NULL_REVISION],
             [23, NULL_REVISION],
             [2, NULL_REVISION],
             [3, NULL_REVISION],
             [26, 24],
             [27, NULL_REVISION],
             [28, NULL_REVISION],
             [12, NULL_REVISION],
             [1, NULL_REVISION],
             [1, 9],
             [32, NULL_REVISION],
             [33, NULL_REVISION],
             [34, 31],
             [35, NULL_REVISION],
             [36, 26],
             [37, NULL_REVISION],
             [38, NULL_REVISION],
             [39, NULL_REVISION],
             [40, NULL_REVISION],
             [41, NULL_REVISION],
             [42, 26],
             [0, NULL_REVISION],
             [44, NULL_REVISION],
             [45, 4],
             [40, NULL_REVISION],
             [47, NULL_REVISION],
             [36, 0],
             [49, NULL_REVISION],
             [NULL_REVISION, NULL_REVISION],
             [51, NULL_REVISION],
             [52, NULL_REVISION],
             [53, NULL_REVISION],
             [14, NULL_REVISION],
             [55, NULL_REVISION],
             [15, NULL_REVISION],
             [23, NULL_REVISION],
             [58, NULL_REVISION],
             [59, NULL_REVISION],
             [2, NULL_REVISION],
             [61, 59],
             [62, NULL_REVISION],
             [63, NULL_REVISION],
             [NULL_REVISION, NULL_REVISION],
             [65, NULL_REVISION],
             [66, NULL_REVISION],
             [67, NULL_REVISION],
             [68, NULL_REVISION],
             [37, 28],
             [69, 25],
             [71, NULL_REVISION],
             [72, NULL_REVISION],
             [50, 2],
             [74, NULL_REVISION],
             [12, NULL_REVISION],
             [18, NULL_REVISION],
             [77, NULL_REVISION],
             [78, NULL_REVISION],
             [79, NULL_REVISION],
             [43, 33],
             [81, NULL_REVISION],
             [82, NULL_REVISION],
             [83, NULL_REVISION],
             [84, 45],
             [85, NULL_REVISION],
             [86, NULL_REVISION],
             [NULL_REVISION, NULL_REVISION],
             [88, NULL_REVISION],
             [NULL_REVISION, NULL_REVISION],
             [76, 83],
             [44, NULL_REVISION],
             [92, NULL_REVISION],
             [93, NULL_REVISION],
             [9, NULL_REVISION],
             [95, 67],
             [96, NULL_REVISION],
             [97, NULL_REVISION],
             [NULL_REVISION, NULL_REVISION],
         ];
         let problem_rev = 28 as Revision;
         let problem_base = 70 as Revision;
         // making the problem obvious: problem_rev is a parent of problem_base
         assert_eq!(graph.parents(problem_base).unwrap()[1], problem_rev);
 
         let mut missing_ancestors: MissingAncestors<VecGraph> =
             MissingAncestors::new(
                 graph,
                 [60, 26, 70, 3, 96, 19, 98, 49, 97, 47, 1, 6]
                     .iter()
                     .cloned(),
             );
         assert!(missing_ancestors.bases.contains(&problem_base));
 
         let mut revs: HashSet<Revision> =
             [4, 12, 41, 28, 68, 38, 1, 30, 56, 44]
                 .iter()
                 .cloned()
                 .collect();
         missing_ancestors.remove_ancestors_from(&mut revs).unwrap();
         assert!(!revs.contains(&problem_rev));
     }
 
 }

rust/hg-core/src/dagops.rs

@@ -1,136 +1,140 b''
 // dagops.rs
 //
 // Copyright 2019 Georges Racinet <[e-mail]>
 //
 // This software may be used and distributed according to the terms of the
 // GNU General Public License version 2 or any later version.
 
 //! Miscellaneous DAG operations
 //!
 //! # Terminology
 //! - By *relative heads* of a collection of revision numbers (`Revision`),
 //!   we mean those revisions that have no children among the collection.
 //! - Similarly *relative roots* of a collection of `Revision`, we mean
 //!   those whose parents, if any, don't belong to the collection.
 use super::{Graph, GraphError, Revision, NULL_REVISION};
 use std::collections::HashSet;
 
 fn remove_parents(
     graph: &impl Graph,
     rev: Revision,
     set: &mut HashSet<Revision>,
 ) -> Result<(), GraphError> {
     for parent in graph.parents(rev)?.iter() {
         if *parent != NULL_REVISION {
             set.remove(parent);
         }
     }
     Ok(())
 }
 
 /// Relative heads out of some revisions, passed as an iterator.
 ///
 /// These heads are defined as those revisions that have no children
 /// among those emitted by the iterator.
 ///
 /// # Performance notes
 /// Internally, this clones the iterator, and builds a `HashSet` out of it.
 ///
 /// This function takes an `Iterator` instead of `impl IntoIterator` to
 /// guarantee that cloning the iterator doesn't result in cloning the full
 /// construct it comes from.
 pub fn heads<'a>(
     graph: &impl Graph,
     iter_revs: impl Clone + Iterator<Item = &'a Revision>,
 ) -> Result<HashSet<Revision>, GraphError> {
     let mut heads: HashSet<Revision> = iter_revs.clone().cloned().collect();
     heads.remove(&NULL_REVISION);
     for rev in iter_revs {
+        if *rev != NULL_REVISION {
         remove_parents(graph, *rev, &mut heads)?;
     }
+    }
     Ok(heads)
 }
 
 /// Retain in `revs` only its relative heads.
 ///
 /// This is an in-place operation, so that control of the incoming
 /// set is left to the caller.
 /// - a direct Python binding would probably need to build its own `HashSet`
 ///   from an incoming iterable, even if its sole purpose is to extract the
 ///   heads.
 /// - a Rust caller can decide whether cloning beforehand is appropriate
 ///
 /// # Performance notes
 /// Internally, this function will store a full copy of `revs` in a `Vec`.
 pub fn retain_heads(
     graph: &impl Graph,
     revs: &mut HashSet<Revision>,
 ) -> Result<(), GraphError> {
     revs.remove(&NULL_REVISION);
     // we need to construct an iterable copy of revs to avoid itering while
     // mutating
     let as_vec: Vec<Revision> = revs.iter().cloned().collect();
     for rev in as_vec {
+        if rev != NULL_REVISION {
         remove_parents(graph, rev, revs)?;
     }
+    }
     Ok(())
 }
 
 #[cfg(test)]
 mod tests {
 
     use super::*;
     use crate::testing::SampleGraph;
 
     /// Apply `retain_heads()` to the given slice and return as a sorted `Vec`
     fn retain_heads_sorted(
         graph: &impl Graph,
         revs: &[Revision],
     ) -> Result<Vec<Revision>, GraphError> {
         let mut revs: HashSet<Revision> = revs.iter().cloned().collect();
         retain_heads(graph, &mut revs)?;
         let mut as_vec: Vec<Revision> = revs.iter().cloned().collect();
         as_vec.sort();
         Ok(as_vec)
     }
 
     #[test]
     fn test_retain_heads() -> Result<(), GraphError> {
         assert_eq!(retain_heads_sorted(&SampleGraph, &[4, 5, 6])?, vec![5, 6]);
         assert_eq!(
             retain_heads_sorted(&SampleGraph, &[4, 1, 6, 12, 0])?,
             vec![1, 6, 12]
         );
         assert_eq!(
             retain_heads_sorted(&SampleGraph, &[1, 2, 3, 4, 5, 6, 7, 8, 9])?,
             vec![3, 5, 8, 9]
         );
         Ok(())
     }
 
     /// Apply `heads()` to the given slice and return as a sorted `Vec`
     fn heads_sorted(
         graph: &impl Graph,
         revs: &[Revision],
     ) -> Result<Vec<Revision>, GraphError> {
         let heads = heads(graph, revs.iter())?;
         let mut as_vec: Vec<Revision> = heads.iter().cloned().collect();
         as_vec.sort();
         Ok(as_vec)
     }
 
     #[test]
     fn test_heads() -> Result<(), GraphError> {
         assert_eq!(heads_sorted(&SampleGraph, &[4, 5, 6])?, vec![5, 6]);
         assert_eq!(
             heads_sorted(&SampleGraph, &[4, 1, 6, 12, 0])?,
             vec![1, 6, 12]
         );
         assert_eq!(
             heads_sorted(&SampleGraph, &[1, 2, 3, 4, 5, 6, 7, 8, 9])?,
             vec![3, 5, 8, 9]
         );
         Ok(())
     }
 
 }

rust/hg-core/src/lib.rs

@@ -1,36 +1,41 b''
 // Copyright 2018 Georges Racinet <[e-mail]>
 //
 // This software may be used and distributed according to the terms of the
 // GNU General Public License version 2 or any later version.
 mod ancestors;
 pub mod dagops;
 pub use ancestors::{AncestorsIterator, LazyAncestors, MissingAncestors};
 pub mod testing;  // unconditionally built, for use from integration tests
 
 /// Mercurial revision numbers
 ///
 /// As noted in revlog.c, revision numbers are actually encoded in
 /// 4 bytes, and are liberally converted to ints, whence the i32
 pub type Revision = i32;
 
+
+/// Marker expressing the absence of a parent
+///
+/// Independently of the actual representation, `NULL_REVISION` is guaranteed
+/// to be smaller that all existing revisions.
 pub const NULL_REVISION: Revision = -1;
 
 /// Same as `mercurial.node.wdirrev`
 ///
 /// This is also equal to `i32::max_value()`, but it's better to spell
 /// it out explicitely, same as in `mercurial.node`
 pub const WORKING_DIRECTORY_REVISION: Revision = 0x7fffffff;
 
 /// The simplest expression of what we need of Mercurial DAGs.
 pub trait Graph {
     /// Return the two parents of the given `Revision`.
     ///
     /// Each of the parents can be independently `NULL_REVISION`
     fn parents(&self, Revision) -> Result<[Revision; 2], GraphError>;
 }
 
 #[derive(Clone, Debug, PartialEq)]
 pub enum GraphError {
     ParentOutOfRange(Revision),
     WorkingDirectoryUnsupported,
 }