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

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 12954

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,