This is an archive of the discontinued Mercurial Phabricator instance.

Differential D5415

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

Authored by gracinet on Dec 12 2018, 10:11 AM.

Details

Reviewers
None
Group Reviewers
hg-reviewers
Commits
rHG18513d6ef7d4: rust: changed Graph.parents to return [Revision; 2]
rHGa6ba978d9ffb: rust: changed Graph.parents to return [Revision; 2]
Summary

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.

Diff Detail

Repository
rHG Mercurial
Lint
Lint Skipped
Unit
Unit Tests Skipped

Event Timeline

gracinet created this revision.Dec 12 2018, 10:11 AM
kevincox added a comment.Dec 12 2018, 11:11 AM

This is a nice improvement. It still seems odd to me to return a list of two parents when there could be 0, 1 or 2 parents. I guess this is for performance reasons?

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

I would do let [p1, p2] still as it shows the reader that you handled all the nodes. Alternatively loop over them all.

for parent in this.graph.parents(rev)? {
  this.conditionally_push_rev(parent);
}
118
let [p1, p2] = ...
gracinet updated this revision to Diff 12831.Dec 12 2018, 11:26 AM
gracinet marked 2 inline comments as done.Dec 12 2018, 11:37 AM
gracinet added a subscriber: yuja.

Thanks ! About the fact to always returning two elements, I've been hesitating about that. This is what the C function we're wrapping provides anyway, so you could say it's for simplicity. I don't take any risks either wrt performance. But it's true it would be also simpler for callers not to worry about that at all. Another point is that there is no firm guarantee that a valid revision occurs before NULL_REVISION. I've found examples in revlog.c where the second parent is (seemlingly on purpose) not ignored if the first is NULL_REVISION, but I wouldn't want at this point to impose it from the parents() method right away.

As @yuja said on D5370, we could make a utility function to filter out NULL_REVISION later on. Or (why not) an iterator that does all needed sanitizing.

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

I like the looping.

118

oh, great, didn't know it would work, should have tried !

gracinet marked 2 inline comments as done.Dec 13 2018, 7:33 AM
Closed by commit rHGa6ba978d9ffb: rust: changed Graph.parents to return [Revision; 2] (authored by gracinet). · Explain Why
This revision was automatically updated to reflect the committed changes.
yuja added a comment.Dec 13 2018, 7:36 AM

Queued the first two, thanks.

This is a nice improvement. It still seems odd to me to return a list of two parents when there could be 0, 1 or 2 parents. I guess this is for performance reasons?

It's a direct mapping from the revlog storage. I think [Revision; 2]
is good enough at this layer as I see the Graph trait is actually an
abstraction for storage-level objects.

yuja added a comment.Dec 13 2018, 7:36 AM

Another point is that there is no firm guarantee that a valid revision occurs before NULL_REVISION. I've found examples in revlog.c where the second parent is (seemlingly on purpose) not ignored if the first is NULL_REVISION, but I wouldn't want at this point to impose it from the parents() method right away.

Curious. Can you point out which? I think many things would be broken if
p1 is null but p2 isn't.

Revision Contents
Changeset List

Diff 12828

rust/hg-core/src/ancestors.rs

visit: BinaryHeap::new(), visit: BinaryHeap::new(),
seen: HashSet::new(), seen: HashSet::new(),
stoprev: stoprev, stoprev: stoprev,
graph: graph, graph: graph,
}; };
this.seen.insert(NULL_REVISION); this.seen.insert(NULL_REVISION);
for rev in filtered_initrevs { for rev in filtered_initrevs {
let parents = this.graph.parents(rev)?; let parents = this.graph.parents(rev)?;
this.conditionally_push_rev(parents.0); this.conditionally_push_rev(parents[0]);
this.conditionally_push_rev(parents.1); this.conditionally_push_rev(parents[1]);
kevincoxUnsubmitted
Done

I would do let [p1, p2] still as it shows the reader that you handled all the nodes. Alternatively loop over them all.

for parent in this.graph.parents(rev)? {
  this.conditionally_push_rev(parent);
}
kevincox: I would do `let [p1, p2]` still as it shows the reader that you handled all the nodes.
gracinetAuthorUnsubmitted
Not Done

I like the looping.

gracinet: I like the looping.
} }
Ok(this) Ok(this)
} }
#[inline] #[inline]
fn conditionally_push_rev(&mut self, rev: Revision) { fn conditionally_push_rev(&mut self, rev: Revision) {
if self.stoprev <= rev && !self.seen.contains(&rev) { if self.stoprev <= rev && !self.seen.contains(&rev) {
self.seen.insert(rev); self.seen.insert(rev);
fn next(&mut self) -> Option<Self::Item> { fn next(&mut self) -> Option<Self::Item> {
let current = match self.visit.peek() { let current = match self.visit.peek() {
None => { None => {
return None; return None;
} }
Some(c) => *c, Some(c) => *c,
}; };
let (p1, p2) = match self.graph.parents(current) { let parents = match self.graph.parents(current) {
kevincoxUnsubmitted
Done
let [p1, p2] = ...
kevincox: ``` let [p1, p2] = ... ```
gracinetAuthorUnsubmitted
Not Done

oh, great, didn't know it would work, should have tried !

gracinet: oh, great, didn't know it would work, should have tried !
Ok(ps) => ps, Ok(ps) => ps,
Err(e) => return Some(Err(e)), Err(e) => return Some(Err(e)),
}; };
let (p1, p2) = (parents[0], parents[1]);
if p1 < self.stoprev || self.seen.contains(&p1) { if p1 < self.stoprev || self.seen.contains(&p1) {
self.visit.pop(); self.visit.pop();
} else { } else {
*(self.visit.peek_mut().unwrap()) = p1; *(self.visit.peek_mut().unwrap()) = p1;
self.seen.insert(p1); self.seen.insert(p1);
}; };
self.conditionally_push_rev(p2); self.conditionally_push_rev(p2);
Some(Ok(current)) Some(Ok(current))
} }
} }
#[cfg(test)] #[cfg(test)]
mod tests { mod tests {
use super::*; use super::*;
#[derive(Clone, Debug)] #[derive(Clone, Debug)]
struct Stub; struct Stub;
/// This is the same as the dict from test-ancestors.py /// This is the same as the dict from test-ancestors.py
impl Graph for Stub { impl Graph for Stub {
fn parents( fn parents(&self, rev: Revision) -> Result<[Revision; 2], GraphError> {
&self,
rev: Revision,
) -> Result<(Revision, Revision), GraphError> {
match rev { match rev {
0 => Ok((-1, -1)), 0 => Ok([-1, -1]),
1 => Ok((0, -1)), 1 => Ok([0, -1]),
2 => Ok((1, -1)), 2 => Ok([1, -1]),
3 => Ok((1, -1)), 3 => Ok([1, -1]),
4 => Ok((2, -1)), 4 => Ok([2, -1]),
5 => Ok((4, -1)), 5 => Ok([4, -1]),
6 => Ok((4, -1)), 6 => Ok([4, -1]),
7 => Ok((4, -1)), 7 => Ok([4, -1]),
8 => Ok((-1, -1)), 8 => Ok([-1, -1]),
9 => Ok((6, 7)), 9 => Ok([6, 7]),
10 => Ok((5, -1)), 10 => Ok([5, -1]),
11 => Ok((3, 7)), 11 => Ok([3, 7]),
12 => Ok((9, -1)), 12 => Ok([9, -1]),
13 => Ok((8, -1)), 13 => Ok([8, -1]),
r => Err(GraphError::ParentOutOfRange(r)), r => Err(GraphError::ParentOutOfRange(r)),
} }
} }
} }
fn list_ancestors<G: Graph>( fn list_ancestors<G: Graph>(
graph: G, graph: G,
initrevs: Vec<Revision>, initrevs: Vec<Revision>,
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());
} }
/// A corrupted Graph, supporting error handling tests /// A corrupted Graph, supporting error handling tests
struct Corrupted; struct Corrupted;
impl Graph for Corrupted { impl Graph for Corrupted {
fn parents( fn parents(&self, rev: Revision) -> Result<[Revision; 2], GraphError> {
&self,
rev: Revision,
) -> Result<(Revision, Revision), GraphError> {
match rev { match rev {
1 => Ok((0, -1)), 1 => Ok([0, -1]),
r => Err(GraphError::ParentOutOfRange(r)), r => Err(GraphError::ParentOutOfRange(r)),
} }
} }
} }
#[test] #[test]
fn test_initrev_out_of_range() { fn test_initrev_out_of_range() {
// inclusive=false looks up initrev's parents right away // inclusive=false looks up initrev's parents right away

rust/hg-core/src/lib.rs

/// 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 {
fn parents(&self, Revision) -> Result<(Revision, Revision), 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-direct-ffi/src/ancestors.rs

Index { Index {
index: index, index: index,
} }
} }
} }
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, Revision), 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 = let code =
unsafe { HgRevlogIndex_GetParents(self.index, rev, &mut res as *mut [c_int; 2]) }; unsafe { HgRevlogIndex_GetParents(self.index, rev, &mut res as *mut [c_int; 2]) };
match code { match code {
0 => Ok((res[0], res[1])), 0 => Ok(res),
_ => Err(GraphError::ParentOutOfRange(rev)), _ => Err(GraphError::ParentOutOfRange(rev)),
} }
} }
} }
/// Wrapping of AncestorsIterator<Index> constructor, for C callers. /// Wrapping of AncestorsIterator<Index> constructor, for C callers.
/// ///
/// Besides `initrevs`, `stoprev` and `inclusive`, that are converted /// Besides `initrevs`, `stoprev` and `inclusive`, that are converted
mod tests { mod tests {
use super::*; use super::*;
use std::thread; use std::thread;
#[derive(Clone, Debug)] #[derive(Clone, Debug)]
struct Stub; struct Stub;
impl Graph for 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 { match r {
25 => Err(GraphError::ParentOutOfRange(25)), 25 => Err(GraphError::ParentOutOfRange(25)),
_ => Ok((1, 2)), _ => Ok([1, 2]),
} }
} }
} }
/// Helper for test_init_next() /// Helper for test_init_next()
fn stub_raw_init( fn stub_raw_init(
initrevslen: usize, initrevslen: usize,
initrevs: usize, initrevs: usize,