rust: changed Graph.parents to return [Revision; 2]

This will allow for simple iteration on parent revisions,
such as:

   for parent in graph.parents(rev)?.iter().cloned()

This seems to be a zero overhead abstraction once built in
release mode.

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

rust/hg-core/src/ancestors.rs

@@ -1,261 +1,255 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::collections::{BinaryHeap, HashSet};
 
 /// 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,
 }
 
 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<I>(
         graph: G,
         initrevs: I,
         stoprev: Revision,
         inclusive: bool,
     ) -> Result<Self, GraphError>
     where
         I: IntoIterator<Item = Revision>,
     {
         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 {
-            let parents = this.graph.parents(rev)?;
-            this.conditionally_push_rev(parents.0);
-            this.conditionally_push_rev(parents.1);
+            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.contains(&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)
     }
 }
 
 /// Main implementation.
 ///
 /// 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) {
+        let [p1, p2] = match self.graph.parents(current) {
             Ok(ps) => ps,
             Err(e) => return Some(Err(e)),
         };
         if p1 < self.stoprev || self.seen.contains(&p1) {
             self.visit.pop();
         } else {
             *(self.visit.peek_mut().unwrap()) = p1;
             self.seen.insert(p1);
         };
 
         self.conditionally_push_rev(p2);
         Some(Ok(current))
     }
 }
 
 #[cfg(test)]
 mod tests {
 
     use super::*;
 
     #[derive(Clone, Debug)]
     struct Stub;
 
     /// This is the same as the dict from test-ancestors.py
     impl Graph for Stub {
-        fn parents(
-            &self,
-            rev: Revision,
-        ) -> Result<(Revision, Revision), GraphError> {
+        fn parents(&self, rev: Revision) -> Result<[Revision; 2], GraphError> {
             match rev {
-                0 => Ok((-1, -1)),
-                1 => Ok((0, -1)),
-                2 => Ok((1, -1)),
-                3 => Ok((1, -1)),
-                4 => Ok((2, -1)),
-                5 => Ok((4, -1)),
-                6 => Ok((4, -1)),
-                7 => Ok((4, -1)),
-                8 => Ok((-1, -1)),
-                9 => Ok((6, 7)),
-                10 => Ok((5, -1)),
-                11 => Ok((3, 7)),
-                12 => Ok((9, -1)),
-                13 => Ok((8, -1)),
+                0 => Ok([-1, -1]),
+                1 => Ok([0, -1]),
+                2 => Ok([1, -1]),
+                3 => Ok([1, -1]),
+                4 => Ok([2, -1]),
+                5 => Ok([4, -1]),
+                6 => Ok([4, -1]),
+                7 => Ok([4, -1]),
+                8 => Ok([-1, -1]),
+                9 => Ok([6, 7]),
+                10 => Ok([5, -1]),
+                11 => Ok([3, 7]),
+                12 => Ok([9, -1]),
+                13 => Ok([8, -1]),
                 r => Err(GraphError::ParentOutOfRange(r)),
             }
         }
     }
 
     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(Stub, vec![], 0, false), vec![]);
         assert_eq!(
             list_ancestors(Stub, vec![11, 13], 0, false),
             vec![8, 7, 4, 3, 2, 1, 0]
         );
         assert_eq!(list_ancestors(Stub, vec![1, 3], 0, false), vec![1, 0]);
         assert_eq!(
             list_ancestors(Stub, vec![11, 13], 0, true),
             vec![13, 11, 8, 7, 4, 3, 2, 1, 0]
         );
         assert_eq!(list_ancestors(Stub, vec![11, 13], 6, false), vec![8, 7]);
         assert_eq!(
             list_ancestors(Stub, vec![11, 13], 6, true),
             vec![13, 11, 8, 7]
         );
         assert_eq!(list_ancestors(Stub, vec![11, 13], 11, true), vec![13, 11]);
         assert_eq!(list_ancestors(Stub, vec![11, 13], 12, true), vec![13]);
         assert_eq!(
             list_ancestors(Stub, 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(Stub, vec![-1], 0, false).unwrap();
         assert_eq!(iter.next(), None)
     }
 
     #[test]
     fn test_contains() {
         let mut lazy =
             AncestorsIterator::new(Stub, vec![10, 1], 0, true).unwrap();
         assert!(lazy.contains(1).unwrap());
         assert!(!lazy.contains(3).unwrap());
 
         let mut lazy =
             AncestorsIterator::new(Stub, vec![0], 0, false).unwrap();
         assert!(!lazy.contains(NULL_REVISION).unwrap());
     }
 
     /// A corrupted Graph, supporting error handling tests
     struct Corrupted;
 
     impl Graph for Corrupted {
-        fn parents(
-            &self,
-            rev: Revision,
-        ) -> Result<(Revision, Revision), GraphError> {
+        fn parents(&self, rev: Revision) -> Result<[Revision; 2], GraphError> {
             match rev {
-                1 => Ok((0, -1)),
+                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(Stub, 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))));
     }
 }

rust/hg-core/src/lib.rs

@@ -1,24 +1,24 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 use ancestors::AncestorsIterator;
 
 /// 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;
 
 pub const NULL_REVISION: Revision = -1;
 
 /// The simplest expression of what we need of Mercurial DAGs.
 pub trait Graph {
-    fn parents(&self, Revision) -> Result<(Revision, Revision), GraphError>;
+    fn parents(&self, Revision) -> Result<[Revision; 2], GraphError>;
 }
 
 #[derive(Clone, Debug, PartialEq)]
 pub enum GraphError {
     ParentOutOfRange(Revision),
 }

rust/hg-direct-ffi/src/ancestors.rs

@@ -1,271 +1,271 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.
 
 //! Bindings for CPython extension code
 //!
 //! This exposes methods to build and use a `rustlazyancestors` iterator
 //! from C code, using an index and its parents function that are passed
 //! from the caller at instantiation.
 
 use hg::AncestorsIterator;
 use hg::{Graph, GraphError, Revision, NULL_REVISION};
 use libc::{c_int, c_long, c_void, ssize_t};
 use std::ptr::null_mut;
 use std::slice;
 
 type IndexPtr = *mut c_void;
 
 extern "C" {
     fn HgRevlogIndex_GetParents(
         op: IndexPtr,
         rev: c_int,
         parents: *mut [c_int; 2],
     ) -> c_int;
 }
 
 /// A Graph backed up by objects and functions from revlog.c
 ///
 /// This implementation of the Graph trait, relies on (pointers to)
 /// - the C index object (`index` member)
 /// - the `index_get_parents()` function (`parents` member)
 pub struct Index {
     index: IndexPtr,
 }
 
 impl Index {
     pub fn new(index: IndexPtr) -> Self {
         Index {
             index: index,
         }
     }
 }
 
 impl Graph for Index {
     /// wrap a call to the C extern parents function
-    fn parents(&self, rev: Revision) -> Result<(Revision, Revision), GraphError> {
+    fn parents(&self, rev: Revision) -> Result<[Revision; 2], GraphError> {
         let mut res: [c_int; 2] = [0; 2];
         let code =
             unsafe { HgRevlogIndex_GetParents(self.index, rev, &mut res as *mut [c_int; 2]) };
         match code {
-            0 => Ok((res[0], res[1])),
+            0 => Ok(res),
             _ => Err(GraphError::ParentOutOfRange(rev)),
         }
     }
 }
 
 /// Wrapping of AncestorsIterator<Index> constructor, for C callers.
 ///
 /// Besides `initrevs`, `stoprev` and `inclusive`, that are converted
 /// we receive the index and the parents function as pointers
 #[no_mangle]
 pub extern "C" fn rustlazyancestors_init(
     index: IndexPtr,
     initrevslen: ssize_t,
     initrevs: *mut c_long,
     stoprev: c_long,
     inclusive: c_int,
 ) -> *mut AncestorsIterator<Index> {
     assert!(initrevslen >= 0);
     unsafe {
         raw_init(
             Index::new(index),
             initrevslen as usize,
             initrevs,
             stoprev,
             inclusive,
         )
     }
 }
 
 /// Testable (for any Graph) version of rustlazyancestors_init
 #[inline]
 unsafe fn raw_init<G: Graph>(
     graph: G,
     initrevslen: usize,
     initrevs: *mut c_long,
     stoprev: c_long,
     inclusive: c_int,
 ) -> *mut AncestorsIterator<G> {
     let inclb = match inclusive {
         0 => false,
         1 => true,
         _ => {
             return null_mut();
         }
     };
 
     let slice = slice::from_raw_parts(initrevs, initrevslen);
 
     Box::into_raw(Box::new(match AncestorsIterator::new(
         graph,
         slice.into_iter().map(|&r| r as Revision),
         stoprev as Revision,
         inclb,
     ) {
         Ok(it) => it,
         Err(_) => {
             return null_mut();
         }
     }))
 }
 
 /// Deallocator to be called from C code
 #[no_mangle]
 pub extern "C" fn rustlazyancestors_drop(raw_iter: *mut AncestorsIterator<Index>) {
     raw_drop(raw_iter);
 }
 
 /// Testable (for any Graph) version of rustlazayancestors_drop
 #[inline]
 fn raw_drop<G: Graph>(raw_iter: *mut AncestorsIterator<G>) {
     unsafe {
         Box::from_raw(raw_iter);
     }
 }
 
 /// Iteration main method to be called from C code
 ///
 /// We convert the end of iteration into NULL_REVISION,
 /// it will be up to the C wrapper to convert that back into a Python end of
 /// iteration
 #[no_mangle]
 pub extern "C" fn rustlazyancestors_next(raw: *mut AncestorsIterator<Index>) -> c_long {
     raw_next(raw)
 }
 
 /// Testable (for any Graph) version of rustlazayancestors_next
 #[inline]
 fn raw_next<G: Graph>(raw: *mut AncestorsIterator<G>) -> c_long {
     let as_ref = unsafe { &mut *raw };
     let rev = match as_ref.next() {
         Some(Ok(rev)) => rev,
         Some(Err(_)) | None => NULL_REVISION,
     };
     rev as c_long
 }
 
 #[no_mangle]
 pub extern "C" fn rustlazyancestors_contains(
     raw: *mut AncestorsIterator<Index>,
     target: c_long,
 ) -> c_int {
     raw_contains(raw, target)
 }
 
 /// Testable (for any Graph) version of rustlazayancestors_next
 #[inline]
 fn raw_contains<G: Graph>(
     raw: *mut AncestorsIterator<G>,
     target: c_long,
 ) -> c_int {
     let as_ref = unsafe { &mut *raw };
     match as_ref.contains(target as Revision) {
         Ok(r) => r as c_int,
         Err(_) => -1,
     }
 }
 
 #[cfg(test)]
 mod tests {
     use super::*;
     use std::thread;
 
     #[derive(Clone, Debug)]
     struct Stub;
 
     impl Graph for Stub {
-        fn parents(&self, r: Revision) -> Result<(Revision, Revision), GraphError> {
+        fn parents(&self, r: Revision) -> Result<[Revision; 2], GraphError> {
             match r {
                 25 => Err(GraphError::ParentOutOfRange(25)),
-                _ => Ok((1, 2)),
+                _ => Ok([1, 2]),
             }
         }
     }
 
     /// Helper for test_init_next()
     fn stub_raw_init(
         initrevslen: usize,
         initrevs: usize,
         stoprev: c_long,
         inclusive: c_int,
     ) -> usize {
         unsafe {
             raw_init(
                 Stub,
                 initrevslen,
                 initrevs as *mut c_long,
                 stoprev,
                 inclusive,
             ) as usize
         }
     }
 
     fn stub_raw_init_from_vec(
         mut initrevs: Vec<c_long>,
         stoprev: c_long,
         inclusive: c_int,
     ) -> *mut AncestorsIterator<Stub> {
         unsafe {
             raw_init(
                 Stub,
                 initrevs.len(),
                 initrevs.as_mut_ptr(),
                 stoprev,
                 inclusive,
             )
         }
     }
 
     #[test]
     // Test what happens when we init an Iterator as with the exposed C ABI
     // and try to use it afterwards
     // We spawn new threads, in order to make memory consistency harder
     // but this forces us to convert the pointers into shareable usizes.
     fn test_init_next() {
         let mut initrevs: Vec<c_long> = vec![11, 13];
         let initrevs_len = initrevs.len();
         let initrevs_ptr = initrevs.as_mut_ptr() as usize;
         let handler = thread::spawn(move || stub_raw_init(initrevs_len, initrevs_ptr, 0, 1));
         let raw = handler.join().unwrap() as *mut AncestorsIterator<Stub>;
 
         assert_eq!(raw_next(raw), 13);
         assert_eq!(raw_next(raw), 11);
         assert_eq!(raw_next(raw), 2);
         assert_eq!(raw_next(raw), 1);
         assert_eq!(raw_next(raw), NULL_REVISION as c_long);
         raw_drop(raw);
     }
 
     #[test]
     fn test_init_wrong_bool() {
         assert_eq!(stub_raw_init_from_vec(vec![11, 13], 0, 2), null_mut());
     }
 
     #[test]
     fn test_empty() {
         let raw = stub_raw_init_from_vec(vec![], 0, 1);
         assert_eq!(raw_next(raw), NULL_REVISION as c_long);
         raw_drop(raw);
     }
 
     #[test]
     fn test_init_err_out_of_range() {
         assert!(stub_raw_init_from_vec(vec![25], 0, 0).is_null());
     }
 
     #[test]
     fn test_contains() {
         let raw = stub_raw_init_from_vec(vec![5, 6], 0, 1);
         assert_eq!(raw_contains(raw, 5), 1);
         assert_eq!(raw_contains(raw, 2), 1);
     }
 
     #[test]
     fn test_contains_exclusive() {
         let raw = stub_raw_init_from_vec(vec![5, 6], 0, 0);
         assert_eq!(raw_contains(raw, 5), 0);
         assert_eq!(raw_contains(raw, 2), 1);
     }
 }