gracinet created this revision. Herald added subscribers: mercurial-devel, kevincox, durin42. Herald added a reviewer: hg-reviewers.
REVISION SUMMARY Once exposed through appropriate bindings, this should be able to replace ancestor.lazyancestors entirely. REPOSITORY rHG Mercurial REVISION DETAIL https://phab.mercurial-scm.org/D5440 AFFECTED FILES rust/hg-core/src/ancestors.rs rust/hg-core/src/lib.rs rust/hg-cpython/src/cindex.rs rust/hg-direct-ffi/src/ancestors.rs CHANGE DETAILS diff --git a/rust/hg-direct-ffi/src/ancestors.rs b/rust/hg-direct-ffi/src/ancestors.rs --- a/rust/hg-direct-ffi/src/ancestors.rs +++ b/rust/hg-direct-ffi/src/ancestors.rs @@ -30,6 +30,12 @@ /// This implementation of the Graph trait, relies on (pointers to) /// - the C index object (`index` member) /// - the `index_get_parents()` function (`parents` member) +/// +/// In case of `.clone()` (would be from a full binding for `LazyAncestors` +/// that doesn't exist at the time of this writing), reference increasing +/// and decreasing would be the responsibility of the caller, same as it +/// is for `AncestorsIterator` +#[derive(Clone, Debug)] pub struct Index { index: IndexPtr, } diff --git a/rust/hg-cpython/src/cindex.rs b/rust/hg-cpython/src/cindex.rs --- a/rust/hg-cpython/src/cindex.rs +++ b/rust/hg-cpython/src/cindex.rs @@ -15,7 +15,7 @@ extern crate python3_sys as python_sys; use self::python_sys::PyCapsule_Import; -use cpython::{PyErr, PyObject, PyResult, Python}; +use cpython::{PyClone, PyErr, PyObject, PyResult, Python}; use hg::{Graph, GraphError, Revision}; use libc::{c_int, ssize_t}; use std::ffi::CStr; @@ -47,6 +47,16 @@ } } +impl Clone for Index { + fn clone(&self) -> Self { + let guard = Python::acquire_gil(); + Index { + index: self.index.clone_ref(guard.python()), + parents: self.parents.clone(), + } + } +} + impl Graph for Index { /// wrap a call to the C extern parents function fn parents(&self, rev: Revision) -> Result<[Revision; 2], GraphError> { diff --git a/rust/hg-core/src/lib.rs b/rust/hg-core/src/lib.rs --- a/rust/hg-core/src/lib.rs +++ b/rust/hg-core/src/lib.rs @@ -2,8 +2,10 @@ // // This software may be used and distributed according to the terms of the // GNU General Public License version 2 or any later version. +use std::clone::Clone; + mod ancestors; -pub use ancestors::{AncestorsIterator, MissingAncestors}; +pub use ancestors::{AncestorsIterator, LazyAncestors, MissingAncestors}; /// Mercurial revision numbers /// @@ -14,7 +16,7 @@ pub const NULL_REVISION: Revision = -1; /// The simplest expression of what we need of Mercurial DAGs. -pub trait Graph { +pub trait Graph: Clone { /// Return the two parents of the given `Revision`. /// /// Each of the parents can be independently `NULL_REVISION` diff --git a/rust/hg-core/src/ancestors.rs b/rust/hg-core/src/ancestors.rs --- a/rust/hg-core/src/ancestors.rs +++ b/rust/hg-core/src/ancestors.rs @@ -25,6 +25,15 @@ stoprev: Revision, } +/// Lazy ancestors set, backed by AncestorsIterator +pub struct LazyAncestors<G: Graph> { + graph: G, + containsiter: AncestorsIterator<G>, + initrevs: Vec<Revision>, + stoprev: Revision, + inclusive: bool, +} + pub struct MissingAncestors<G: Graph> { graph: G, bases: HashSet<Revision>, @@ -98,9 +107,34 @@ } 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 empty(&self) -> bool { + if self.visit.len() > 0 { + return false; + } + let seen = self.seen.len(); + if seen > 1 { + return false; + } + // at this point, the seen set is a singleton. If not self.inclusive, + // then its only element can be the null revision + if seen == 0 || self.seen.contains(&NULL_REVISION) { + return true; + } + false + } } -/// Main implementation. +/// Main implementation for the iterator /// /// The algorithm is the same as in `_lazyancestorsiter()` from `ancestors.py` /// with a few non crucial differences: @@ -137,6 +171,51 @@ } } +impl<G: Graph> 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, + }) + } + + #[inline] + pub fn contains(&mut self, rev: Revision) -> Result<bool, GraphError> { + self.containsiter.contains(rev) + } + + #[inline] + pub fn is_empty(&self) -> bool { + self.containsiter.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 { let mut bases: HashSet<Revision> = bases.into_iter().collect(); @@ -407,7 +486,40 @@ assert!(!lazy.contains(NULL_REVISION).unwrap()); } + #[test] + fn test_peek() { + let mut iter = + AncestorsIterator::new(Stub, 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(Stub, vec![10], 0, true).unwrap(); + assert!(!iter.empty()); + while iter.next().is_some() {} + assert!(!iter.empty()); + + let iter = AncestorsIterator::new(Stub, vec![], 0, true).unwrap(); + assert!(iter.empty()); + + // case where iter.seen == {NULL_REVISION} + let iter = AncestorsIterator::new(Stub, vec![0], 0, false).unwrap(); + assert!(iter.empty()); + } + /// A corrupted Graph, supporting error handling tests + #[derive(Clone, Debug)] struct Corrupted; impl Graph for Corrupted { @@ -437,6 +549,39 @@ } #[test] + fn test_lazy_iter_contains() { + let mut lazy = + LazyAncestors::new(Stub, 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(Stub, 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 fn test_missing_bases() { let mut missing_ancestors = To: gracinet, #hg-reviewers Cc: durin42, kevincox, mercurial-devel _______________________________________________ Mercurial-devel mailing list Mercurial-devel@mercurial-scm.org https://www.mercurial-scm.org/mailman/listinfo/mercurial-devel
