This is an archive of the discontinued Mercurial Phabricator instance.

Differential D5440

rust: core implementation for lazyancestors
ClosedPublic

Authored by gracinet on Dec 15 2018, 6:42 AM.

Details

Reviewers
kevincox
Group Reviewers
hg-reviewers
Commits
rHGef54bd33b476: rust: core implementation for lazyancestors
Summary

Once exposed through appropriate bindings, this
should be able to replace ancestor.lazyancestors
entirely.

Diff Detail

Repository
rHG Mercurial
Lint
Lint Skipped
Unit
Unit Tests Skipped

Event Timeline

gracinet created this revision.Dec 15 2018, 6:42 AM
kevincox accepted this revision.Dec 15 2018, 8:08 AM
kevincox added inline comments.
rust/hg-core/src/ancestors.rs
120

Can you clarify this is_empty to match rust convention?

121

if !self.visit.is_empty()

124

I think this variable makes the code harder to read. I would just repeat the calls to .len().

196

In general I wouldn't add these without careful benchmarking. In this case the compiler can trivially notice that this method is a good inlining candidate.

yuja added a subscriber: yuja.Dec 15 2018, 11:45 PM
  • 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;

Nit: it's in prelude.

/// The simplest expression of what we need of Mercurial DAGs.
-pub trait Graph {
+pub trait Graph: Clone {

I think it's the requirement of the caller, i.e. G: Graph + Clone.
Not all graphs have to be clone-able.

Alternatively, maybe the LazyAncestor can be moved to the cpython crate,
where PyClone is available.

+ / 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 {

Nit: s/empty/is_empty/ because empty() can be a verb.

gracinet marked 4 inline comments as done.Dec 22 2018, 11:24 AM
gracinet updated this revision to Diff 12951.
gracinet added a comment.Dec 22 2018, 11:24 AM

@yuja, yes a Graph not implementing Clone is already a good thing, as it avoids to implement Clone in hg-direct-ffi prematurely. I think the whole hg::LazyAncestors can end up being useful from core Rust code, too, that's why I prefer that to a hg-cpython only implementation.

rust/hg-core/src/ancestors.rs
124

agreed, and made a clearer version of the last lines as an OR statement using self.seen.is_empty()

gracinet updated this revision to Diff 12954.Dec 22 2018, 11:24 AM
Closed by commit rHGef54bd33b476: rust: core implementation for lazyancestors (authored by gracinet). · Explain WhyDec 24 2018, 12:00 AM
This revision was automatically updated to reflect the committed changes.

Revision Contents
Changeset List

Diff 12877

rust/hg-core/src/ancestors.rs

/// bindings evolve over time /// bindings evolve over time
pub struct AncestorsIterator<G: Graph> { pub struct AncestorsIterator<G: Graph> {
graph: G, graph: G,
visit: BinaryHeap<Revision>, visit: BinaryHeap<Revision>,
seen: HashSet<Revision>, seen: HashSet<Revision>,
stoprev: Revision, 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> { pub struct MissingAncestors<G: Graph> {
graph: G, graph: G,
bases: HashSet<Revision>, bases: HashSet<Revision>,
} }
impl<G: Graph> AncestorsIterator<G> { impl<G: Graph> AncestorsIterator<G> {
/// Constructor. /// Constructor.
/// ///
return Ok(true); return Ok(true);
} }
if rev < target { if rev < target {
return Ok(false); return Ok(false);
} }
} }
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 empty(&self) -> bool {
kevincoxUnsubmitted
Done

Can you clarify this is_empty to match rust convention?

kevincox: Can you clarify this `is_empty` to match rust convention?
if self.visit.len() > 0 {
kevincoxUnsubmitted
Done

if !self.visit.is_empty()

kevincox: `if !self.visit.is_empty()`
return false;
}
let seen = self.seen.len();
kevincoxUnsubmitted
Done

I think this variable makes the code harder to read. I would just repeat the calls to .len().

kevincox: I think this variable makes the code harder to read. I would just repeat the calls to `.len()`.
gracinetAuthorUnsubmitted
Not Done

agreed, and made a clearer version of the last lines as an OR statement using self.seen.is_empty()

gracinet: agreed, and made a clearer version of the last lines as an OR statement using `self.seen.
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` /// The algorithm is the same as in `_lazyancestorsiter()` from `ancestors.py`
/// with a few non crucial differences: /// with a few non crucial differences:
/// ///
/// - there's no filtering of invalid parent revisions. Actually, it should be /// - there's no filtering of invalid parent revisions. Actually, it should be
/// consistent and more efficient to filter them from the end caller. /// consistent and more efficient to filter them from the end caller.
/// - we don't have the optimization for adjacent revisions (i.e., the case /// - 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 /// where `p1 == rev - 1`), because it amounts to update the first element of
self.seen.insert(p1); self.seen.insert(p1);
}; };
self.conditionally_push_rev(p2); self.conditionally_push_rev(p2);
Some(Ok(current)) Some(Ok(current))
} }
} }
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]
kevincoxUnsubmitted
Done

In general I wouldn't add these without careful benchmarking. In this case the compiler can trivially notice that this method is a good inlining candidate.

kevincox: In general I wouldn't add these without careful benchmarking. In this case the compiler can…
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> { impl<G: Graph> MissingAncestors<G> {
pub fn new(graph: G, bases: impl IntoIterator<Item = Revision>) -> Self { pub fn new(graph: G, bases: impl IntoIterator<Item = Revision>) -> Self {
let mut bases: HashSet<Revision> = bases.into_iter().collect(); let mut bases: HashSet<Revision> = bases.into_iter().collect();
if bases.is_empty() { if bases.is_empty() {
bases.insert(NULL_REVISION); bases.insert(NULL_REVISION);
} }
MissingAncestors { graph, bases } MissingAncestors { graph, bases }
} }
assert!(lazy.contains(1).unwrap()); assert!(lazy.contains(1).unwrap());
assert!(!lazy.contains(3).unwrap()); assert!(!lazy.contains(3).unwrap());
let mut lazy = let mut lazy =
AncestorsIterator::new(Stub, vec![0], 0, false).unwrap(); AncestorsIterator::new(Stub, vec![0], 0, false).unwrap();
assert!(!lazy.contains(NULL_REVISION).unwrap()); 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 /// A corrupted Graph, supporting error handling tests
#[derive(Clone, Debug)]
struct Corrupted; struct Corrupted;
impl Graph for Corrupted { impl Graph for Corrupted {
fn parents(&self, rev: Revision) -> Result<[Revision; 2], GraphError> { fn parents(&self, rev: Revision) -> Result<[Revision; 2], GraphError> {
match rev { match rev {
1 => Ok([0, -1]), 1 => Ok([0, -1]),
r => Err(GraphError::ParentOutOfRange(r)), r => Err(GraphError::ParentOutOfRange(r)),
} }
fn test_next_out_of_range() { fn test_next_out_of_range() {
// inclusive=false looks up initrev's parents right away // inclusive=false looks up initrev's parents right away
let mut iter = let mut iter =
AncestorsIterator::new(Corrupted, vec![1], 0, false).unwrap(); AncestorsIterator::new(Corrupted, vec![1], 0, false).unwrap();
assert_eq!(iter.next(), Some(Err(GraphError::ParentOutOfRange(0)))); assert_eq!(iter.next(), Some(Err(GraphError::ParentOutOfRange(0))));
} }
#[test] #[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 /// Test constructor, add/get bases
fn test_missing_bases() { fn test_missing_bases() {
let mut missing_ancestors = let mut missing_ancestors =
MissingAncestors::new(Stub, [5, 3, 1, 3].iter().cloned()); MissingAncestors::new(Stub, [5, 3, 1, 3].iter().cloned());
let mut as_vec: Vec<Revision> = let mut as_vec: Vec<Revision> =
missing_ancestors.get_bases().iter().cloned().collect(); missing_ancestors.get_bases().iter().cloned().collect();
as_vec.sort(); as_vec.sort();
assert_eq!(as_vec, [1, 3, 5]); assert_eq!(as_vec, [1, 3, 5]);

rust/hg-core/src/lib.rs

// Copyright 2018 Georges Racinet <gracinet@anybox.fr> // Copyright 2018 Georges Racinet <gracinet@anybox.fr>
// //
// This software may be used and distributed according to the terms of the // This software may be used and distributed according to the terms of the
// GNU General Public License version 2 or any later version. // GNU General Public License version 2 or any later version.
use std::clone::Clone;
mod ancestors; mod ancestors;
pub use ancestors::{AncestorsIterator, MissingAncestors}; pub use ancestors::{AncestorsIterator, LazyAncestors, MissingAncestors};
/// Mercurial revision numbers /// Mercurial revision numbers
/// ///
/// As noted in revlog.c, revision numbers are actually encoded in /// As noted in revlog.c, revision numbers are actually encoded in
/// 4 bytes, and are liberally converted to ints, whence the i32 /// 4 bytes, and are liberally converted to ints, whence the i32
pub type Revision = i32; pub type Revision = i32;
pub const NULL_REVISION: Revision = -1; pub const NULL_REVISION: Revision = -1;
/// The simplest expression of what we need of Mercurial DAGs. /// 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`. /// Return the two parents of the given `Revision`.
/// ///
/// Each of the parents can be independently `NULL_REVISION` /// Each of the parents can be independently `NULL_REVISION`
fn parents(&self, Revision) -> Result<[Revision; 2], GraphError>; fn parents(&self, Revision) -> Result<[Revision; 2], GraphError>;
} }
#[derive(Clone, Debug, PartialEq)] #[derive(Clone, Debug, PartialEq)]
pub enum GraphError { pub enum GraphError {
ParentOutOfRange(Revision), ParentOutOfRange(Revision),
} }

rust/hg-cpython/src/cindex.rs

//! Ideally, we should use an Index entirely implemented in Rust, //! Ideally, we should use an Index entirely implemented in Rust,
//! but this will take some time to get there. //! but this will take some time to get there.
#[cfg(feature = "python27")] #[cfg(feature = "python27")]
extern crate python27_sys as python_sys; extern crate python27_sys as python_sys;
#[cfg(feature = "python3")] #[cfg(feature = "python3")]
extern crate python3_sys as python_sys; extern crate python3_sys as python_sys;
use self::python_sys::PyCapsule_Import; 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 hg::{Graph, GraphError, Revision};
use libc::{c_int, ssize_t}; use libc::{c_int, ssize_t};
use std::ffi::CStr; use std::ffi::CStr;
use std::mem::transmute; use std::mem::transmute;
type IndexParentsFn = unsafe extern "C" fn( type IndexParentsFn = unsafe extern "C" fn(
index: *mut python_sys::PyObject, index: *mut python_sys::PyObject,
rev: ssize_t, rev: ssize_t,
pub fn new(py: Python, index: PyObject) -> PyResult<Self> { pub fn new(py: Python, index: PyObject) -> PyResult<Self> {
Ok(Index { Ok(Index {
index: index, index: index,
parents: decapsule_parents_fn(py)?, parents: decapsule_parents_fn(py)?,
}) })
} }
} }
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 { impl Graph for Index {
/// wrap a call to the C extern parents function /// wrap a call to the C extern parents function
fn parents(&self, rev: Revision) -> Result<[Revision; 2], GraphError> { fn parents(&self, rev: Revision) -> Result<[Revision; 2], GraphError> {
let mut res: [c_int; 2] = [0; 2]; let mut res: [c_int; 2] = [0; 2];
let code = unsafe { let code = unsafe {
(self.parents)( (self.parents)(
self.index.as_ptr(), self.index.as_ptr(),
rev as ssize_t, rev as ssize_t,

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

) -> c_int; ) -> c_int;
} }
/// A Graph backed up by objects and functions from revlog.c /// A Graph backed up by objects and functions from revlog.c
/// ///
/// This implementation of the Graph trait, relies on (pointers to) /// This implementation of the Graph trait, relies on (pointers to)
/// - the C index object (`index` member) /// - the C index object (`index` member)
/// - the `index_get_parents()` function (`parents` 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 { pub struct Index {
index: IndexPtr, index: IndexPtr,
} }
impl Index { impl Index {
pub fn new(index: IndexPtr) -> Self { pub fn new(index: IndexPtr) -> Self {
Index { Index {
index: index, index: index,