diff -r 8783710b1d58 -r dbc28c91f7ff rust/hg-core/src/ancestors.rs --- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/rust/hg-core/src/ancestors.rs Thu Sep 27 17:03:16 2018 +0200 @@ -0,0 +1,238 @@ +// ancestors.rs +// +// Copyright 2018 Georges Racinet +// +// This software may be used and distributed according to the terms of the +// GNU General Public License version 2 or any later version. + +//! Rust versions of generic DAG ancestors algorithms for Mercurial + +use super::{Graph, GraphError, Revision, NULL_REVISION}; +use std::collections::{BinaryHeap, HashSet}; + +/// Iterator over the ancestors of a given list of revisions +/// This is a generic type, defined and implemented for any Graph, so that +/// it's easy to +/// +/// - unit test in pure Rust +/// - bind to main Mercurial code, potentially in several ways and have these +/// bindings evolve over time +pub struct AncestorsIterator { + graph: G, + visit: BinaryHeap, + seen: HashSet, + stoprev: Revision, +} + +impl AncestorsIterator { + /// Constructor. + /// + /// if `inclusive` is true, then the init revisions are emitted in + /// particular, otherwise iteration starts from their parents. + pub fn new( + graph: G, + initrevs: I, + stoprev: Revision, + inclusive: bool, + ) -> Result + where + I: IntoIterator, + { + let filtered_initrevs = initrevs.into_iter().filter(|&r| r >= stoprev); + if inclusive { + let visit: BinaryHeap = filtered_initrevs.collect(); + let seen = visit.iter().map(|&x| x).collect(); + return Ok(AncestorsIterator { + visit: visit, + seen: seen, + stoprev: stoprev, + graph: graph, + }); + } + let mut this = AncestorsIterator { + visit: BinaryHeap::new(), + seen: HashSet::new(), + stoprev: stoprev, + graph: graph, + }; + this.seen.insert(NULL_REVISION); + for rev in filtered_initrevs { + this.conditionally_push_parents(rev)?; + } + Ok(this) + } + + #[inline] + fn conditionally_push_rev(&mut self, rev: Revision) { + if self.stoprev <= rev && !self.seen.contains(&rev) { + self.seen.insert(rev); + self.visit.push(rev); + } + } + + #[inline] + fn conditionally_push_parents( + &mut self, + rev: Revision, + ) -> Result<(), GraphError> { + let parents = self.graph.parents(rev)?; + self.conditionally_push_rev(parents.0); + self.conditionally_push_rev(parents.1); + Ok(()) + } +} + +/// Main implementation. +/// +/// The algorithm is the same as in `_lazyancestorsiter()` from `ancestors.py` +/// with a few non crucial differences: +/// +/// - there's no filtering of invalid parent revisions. Actually, it should be +/// consistent and more efficient to filter them from the end caller. +/// - we don't use the equivalent of `heapq.heapreplace()`, but we should, for +/// the same reasons (using `peek_mut`) +/// - we don't have the optimization for adjacent revs (case where p1 == rev-1) +/// - we save a few pushes by comparing with `stoprev` before pushing +/// +/// Error treatment: +/// We swallow the possible GraphError of conditionally_push_parents() to +/// respect the Iterator trait in a simple manner: never emitting parents +/// for the returned revision. We finds this good enough for now, because: +/// +/// - there's a good chance that invalid revisionss are fed from the start, +/// and `new()` doesn't swallow the error result. +/// - this is probably what the Python implementation produces anyway, due +/// to filtering at each step, and Python code is currently the only +/// concrete caller we target, so we shouldn't need a finer error treatment +/// for the time being. +impl Iterator for AncestorsIterator { + type Item = Revision; + + fn next(&mut self) -> Option { + let current = match self.visit.pop() { + None => { + return None; + } + Some(i) => i, + }; + self.conditionally_push_parents(current).unwrap_or(()); + Some(current) + } +} + +#[cfg(test)] +mod tests { + + use super::*; + + #[derive(Clone, Debug)] + struct Stub; + + /// This is the same as the dict from test-ancestors.py + impl Graph for Stub { + fn parents( + &self, + rev: Revision, + ) -> Result<(Revision, Revision), GraphError> { + match rev { + 0 => Ok((-1, -1)), + 1 => Ok((0, -1)), + 2 => Ok((1, -1)), + 3 => Ok((1, -1)), + 4 => Ok((2, -1)), + 5 => Ok((4, -1)), + 6 => Ok((4, -1)), + 7 => Ok((4, -1)), + 8 => Ok((-1, -1)), + 9 => Ok((6, 7)), + 10 => Ok((5, -1)), + 11 => Ok((3, 7)), + 12 => Ok((9, -1)), + 13 => Ok((8, -1)), + r => Err(GraphError::ParentOutOfRange(r)), + } + } + } + + fn list_ancestors( + graph: G, + initrevs: Vec, + stoprev: Revision, + inclusive: bool, + ) -> Vec { + AncestorsIterator::new(graph, initrevs, stoprev, inclusive) + .unwrap() + .collect() + } + + #[test] + /// Same tests as test-ancestor.py, without membership + /// (see also test-ancestor.py.out) + fn test_list_ancestor() { + assert_eq!(list_ancestors(Stub, vec![], 0, false), vec![]); + assert_eq!( + list_ancestors(Stub, vec![11, 13], 0, false), + vec![8, 7, 4, 3, 2, 1, 0] + ); + assert_eq!(list_ancestors(Stub, vec![1, 3], 0, false), vec![1, 0]); + assert_eq!( + list_ancestors(Stub, vec![11, 13], 0, true), + vec![13, 11, 8, 7, 4, 3, 2, 1, 0] + ); + assert_eq!(list_ancestors(Stub, vec![11, 13], 6, false), vec![8, 7]); + assert_eq!( + list_ancestors(Stub, vec![11, 13], 6, true), + vec![13, 11, 8, 7] + ); + assert_eq!(list_ancestors(Stub, vec![11, 13], 11, true), vec![13, 11]); + assert_eq!(list_ancestors(Stub, vec![11, 13], 12, true), vec![13]); + assert_eq!( + list_ancestors(Stub, vec![10, 1], 0, true), + vec![10, 5, 4, 2, 1, 0] + ); + } + + #[test] + /// Corner case that's not directly in test-ancestors.py, but + /// that happens quite often, as demonstrated by running the whole + /// suite. + /// For instance, run tests/test-obsolete-checkheads.t + fn test_nullrev_input() { + let mut iter = + AncestorsIterator::new(Stub, vec![-1], 0, false).unwrap(); + assert_eq!(iter.next(), None) + } + + /// A corrupted Graph, supporting error handling tests + struct Corrupted; + + impl Graph for Corrupted { + fn parents( + &self, + rev: Revision, + ) -> Result<(Revision, Revision), GraphError> { + match rev { + 1 => Ok((0, -1)), + r => Err(GraphError::ParentOutOfRange(r)), + } + } + } + + #[test] + fn test_initrev_out_of_range() { + // inclusive=false looks up initrev's parents right away + match AncestorsIterator::new(Stub, vec![25], 0, false) { + Ok(_) => panic!("Should have been ParentOutOfRange"), + Err(e) => assert_eq!(e, GraphError::ParentOutOfRange(25)), + } + } + + #[test] + fn test_next_out_of_range() { + // inclusive=false looks up initrev's parents right away + let mut iter = + AncestorsIterator::new(Corrupted, vec![1], 0, false).unwrap(); + assert_eq!(iter.next(), Some(0)); + assert_eq!(iter.next(), None); + } +}