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
Automatic diff as part of commit; lint not applicable.
Unit
Automatic diff as part of commit; unit tests not applicable.

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().

193

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 12968

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 + Clone> {
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 is_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;
}
if self.seen.len() > 1 {
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.
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. /// 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 + 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> {
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…
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> { 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.is_empty());
while iter.next().is_some() {}
assert!(!iter.is_empty());
let iter = AncestorsIterator::new(Stub, vec![], 0, true).unwrap();
assert!(iter.is_empty());
// case where iter.seen == {NULL_REVISION}
let iter = AncestorsIterator::new(Stub, vec![0], 0, false).unwrap();
assert!(iter.is_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.
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;

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; use libc::c_int;
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: c_int, rev: c_int,
/// objects (a serious change of the `hg-core` API): /// objects (a serious change of the `hg-core` API):
/// either exposing ways to mutate the `Graph`, or making it a non persistent /// either exposing ways to mutate the `Graph`, or making it a non persistent
/// parameter in the relevant methods that need one. /// parameter in the relevant methods that need one.
/// ///
/// Another possibility would be to introduce an abstract lock handle into /// Another possibility would be to introduce an abstract lock handle into
/// the core API, that would be tied to `GILGuard` / `Python<'p>` /// the core API, that would be tied to `GILGuard` / `Python<'p>`
/// in the case of the `cpython` crate bindings yet could leave room for other /// in the case of the `cpython` crate bindings yet could leave room for other
/// mechanisms in other contexts. /// mechanisms in other contexts.
pub struct Index { pub struct Index {
index: PyObject, index: PyObject,
parents: IndexParentsFn, parents: IndexParentsFn,
} }
impl Index { impl Index {
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 c_int, rev as c_int,