##// END OF EJS Templates
rust: pure Rust lazyancestors iterator...
Georges Racinet -
r40307:dbc28c91 default
parent child Browse files
Show More
@@ -0,0 +1,8 b''
1 [package]
2 name = "hg-core"
3 version = "0.1.0"
4 authors = ["Georges Racinet <gracinet@anybox.fr>"]
5 description = "Mercurial pure Rust core library, with no assumption on Python bindings (FFI)"
6
7 [lib]
8 name = "hg"
@@ -0,0 +1,3 b''
1 max_width = 79
2 wrap_comments = true
3 error_on_line_overflow = true
@@ -0,0 +1,238 b''
1 // ancestors.rs
2 //
3 // Copyright 2018 Georges Racinet <gracinet@anybox.fr>
4 //
5 // This software may be used and distributed according to the terms of the
6 // GNU General Public License version 2 or any later version.
7
8 //! Rust versions of generic DAG ancestors algorithms for Mercurial
9
10 use super::{Graph, GraphError, Revision, NULL_REVISION};
11 use std::collections::{BinaryHeap, HashSet};
12
13 /// Iterator over the ancestors of a given list of revisions
14 /// This is a generic type, defined and implemented for any Graph, so that
15 /// it's easy to
16 ///
17 /// - unit test in pure Rust
18 /// - bind to main Mercurial code, potentially in several ways and have these
19 /// bindings evolve over time
20 pub struct AncestorsIterator<G: Graph> {
21 graph: G,
22 visit: BinaryHeap<Revision>,
23 seen: HashSet<Revision>,
24 stoprev: Revision,
25 }
26
27 impl<G: Graph> AncestorsIterator<G> {
28 /// Constructor.
29 ///
30 /// if `inclusive` is true, then the init revisions are emitted in
31 /// particular, otherwise iteration starts from their parents.
32 pub fn new<I>(
33 graph: G,
34 initrevs: I,
35 stoprev: Revision,
36 inclusive: bool,
37 ) -> Result<Self, GraphError>
38 where
39 I: IntoIterator<Item = Revision>,
40 {
41 let filtered_initrevs = initrevs.into_iter().filter(|&r| r >= stoprev);
42 if inclusive {
43 let visit: BinaryHeap<Revision> = filtered_initrevs.collect();
44 let seen = visit.iter().map(|&x| x).collect();
45 return Ok(AncestorsIterator {
46 visit: visit,
47 seen: seen,
48 stoprev: stoprev,
49 graph: graph,
50 });
51 }
52 let mut this = AncestorsIterator {
53 visit: BinaryHeap::new(),
54 seen: HashSet::new(),
55 stoprev: stoprev,
56 graph: graph,
57 };
58 this.seen.insert(NULL_REVISION);
59 for rev in filtered_initrevs {
60 this.conditionally_push_parents(rev)?;
61 }
62 Ok(this)
63 }
64
65 #[inline]
66 fn conditionally_push_rev(&mut self, rev: Revision) {
67 if self.stoprev <= rev && !self.seen.contains(&rev) {
68 self.seen.insert(rev);
69 self.visit.push(rev);
70 }
71 }
72
73 #[inline]
74 fn conditionally_push_parents(
75 &mut self,
76 rev: Revision,
77 ) -> Result<(), GraphError> {
78 let parents = self.graph.parents(rev)?;
79 self.conditionally_push_rev(parents.0);
80 self.conditionally_push_rev(parents.1);
81 Ok(())
82 }
83 }
84
85 /// Main implementation.
86 ///
87 /// The algorithm is the same as in `_lazyancestorsiter()` from `ancestors.py`
88 /// with a few non crucial differences:
89 ///
90 /// - there's no filtering of invalid parent revisions. Actually, it should be
91 /// consistent and more efficient to filter them from the end caller.
92 /// - we don't use the equivalent of `heapq.heapreplace()`, but we should, for
93 /// the same reasons (using `peek_mut`)
94 /// - we don't have the optimization for adjacent revs (case where p1 == rev-1)
95 /// - we save a few pushes by comparing with `stoprev` before pushing
96 ///
97 /// Error treatment:
98 /// We swallow the possible GraphError of conditionally_push_parents() to
99 /// respect the Iterator trait in a simple manner: never emitting parents
100 /// for the returned revision. We finds this good enough for now, because:
101 ///
102 /// - there's a good chance that invalid revisionss are fed from the start,
103 /// and `new()` doesn't swallow the error result.
104 /// - this is probably what the Python implementation produces anyway, due
105 /// to filtering at each step, and Python code is currently the only
106 /// concrete caller we target, so we shouldn't need a finer error treatment
107 /// for the time being.
108 impl<G: Graph> Iterator for AncestorsIterator<G> {
109 type Item = Revision;
110
111 fn next(&mut self) -> Option<Revision> {
112 let current = match self.visit.pop() {
113 None => {
114 return None;
115 }
116 Some(i) => i,
117 };
118 self.conditionally_push_parents(current).unwrap_or(());
119 Some(current)
120 }
121 }
122
123 #[cfg(test)]
124 mod tests {
125
126 use super::*;
127
128 #[derive(Clone, Debug)]
129 struct Stub;
130
131 /// This is the same as the dict from test-ancestors.py
132 impl Graph for Stub {
133 fn parents(
134 &self,
135 rev: Revision,
136 ) -> Result<(Revision, Revision), GraphError> {
137 match rev {
138 0 => Ok((-1, -1)),
139 1 => Ok((0, -1)),
140 2 => Ok((1, -1)),
141 3 => Ok((1, -1)),
142 4 => Ok((2, -1)),
143 5 => Ok((4, -1)),
144 6 => Ok((4, -1)),
145 7 => Ok((4, -1)),
146 8 => Ok((-1, -1)),
147 9 => Ok((6, 7)),
148 10 => Ok((5, -1)),
149 11 => Ok((3, 7)),
150 12 => Ok((9, -1)),
151 13 => Ok((8, -1)),
152 r => Err(GraphError::ParentOutOfRange(r)),
153 }
154 }
155 }
156
157 fn list_ancestors<G: Graph>(
158 graph: G,
159 initrevs: Vec<Revision>,
160 stoprev: Revision,
161 inclusive: bool,
162 ) -> Vec<Revision> {
163 AncestorsIterator::new(graph, initrevs, stoprev, inclusive)
164 .unwrap()
165 .collect()
166 }
167
168 #[test]
169 /// Same tests as test-ancestor.py, without membership
170 /// (see also test-ancestor.py.out)
171 fn test_list_ancestor() {
172 assert_eq!(list_ancestors(Stub, vec![], 0, false), vec![]);
173 assert_eq!(
174 list_ancestors(Stub, vec![11, 13], 0, false),
175 vec![8, 7, 4, 3, 2, 1, 0]
176 );
177 assert_eq!(list_ancestors(Stub, vec![1, 3], 0, false), vec![1, 0]);
178 assert_eq!(
179 list_ancestors(Stub, vec![11, 13], 0, true),
180 vec![13, 11, 8, 7, 4, 3, 2, 1, 0]
181 );
182 assert_eq!(list_ancestors(Stub, vec![11, 13], 6, false), vec![8, 7]);
183 assert_eq!(
184 list_ancestors(Stub, vec![11, 13], 6, true),
185 vec![13, 11, 8, 7]
186 );
187 assert_eq!(list_ancestors(Stub, vec![11, 13], 11, true), vec![13, 11]);
188 assert_eq!(list_ancestors(Stub, vec![11, 13], 12, true), vec![13]);
189 assert_eq!(
190 list_ancestors(Stub, vec![10, 1], 0, true),
191 vec![10, 5, 4, 2, 1, 0]
192 );
193 }
194
195 #[test]
196 /// Corner case that's not directly in test-ancestors.py, but
197 /// that happens quite often, as demonstrated by running the whole
198 /// suite.
199 /// For instance, run tests/test-obsolete-checkheads.t
200 fn test_nullrev_input() {
201 let mut iter =
202 AncestorsIterator::new(Stub, vec![-1], 0, false).unwrap();
203 assert_eq!(iter.next(), None)
204 }
205
206 /// A corrupted Graph, supporting error handling tests
207 struct Corrupted;
208
209 impl Graph for Corrupted {
210 fn parents(
211 &self,
212 rev: Revision,
213 ) -> Result<(Revision, Revision), GraphError> {
214 match rev {
215 1 => Ok((0, -1)),
216 r => Err(GraphError::ParentOutOfRange(r)),
217 }
218 }
219 }
220
221 #[test]
222 fn test_initrev_out_of_range() {
223 // inclusive=false looks up initrev's parents right away
224 match AncestorsIterator::new(Stub, vec![25], 0, false) {
225 Ok(_) => panic!("Should have been ParentOutOfRange"),
226 Err(e) => assert_eq!(e, GraphError::ParentOutOfRange(25)),
227 }
228 }
229
230 #[test]
231 fn test_next_out_of_range() {
232 // inclusive=false looks up initrev's parents right away
233 let mut iter =
234 AncestorsIterator::new(Corrupted, vec![1], 0, false).unwrap();
235 assert_eq!(iter.next(), Some(0));
236 assert_eq!(iter.next(), None);
237 }
238 }
@@ -0,0 +1,24 b''
1 // Copyright 2018 Georges Racinet <gracinet@anybox.fr>
2 //
3 // This software may be used and distributed according to the terms of the
4 // GNU General Public License version 2 or any later version.
5 mod ancestors;
6 pub use ancestors::AncestorsIterator;
7
8 /// Mercurial revision numbers
9 ///
10 /// As noted in revlog.c, revision numbers are actually encoded in
11 /// 4 bytes, and are liberally converted to ints, whence the i32
12 pub type Revision = i32;
13
14 pub const NULL_REVISION: Revision = -1;
15
16 /// The simplest expression of what we need of Mercurial DAGs.
17 pub trait Graph {
18 fn parents(&self, Revision) -> Result<(Revision, Revision), GraphError>;
19 }
20
21 #[derive(Clone, Debug, PartialEq)]
22 pub enum GraphError {
23 ParentOutOfRange(Revision),
24 }
@@ -17,6 +17,10 b' dependencies = ['
17 17 ]
18 18
19 19 [[package]]
20 name = "hg-core"
21 version = "0.1.0"
22
23 [[package]]
20 24 name = "hgcli"
21 25 version = "0.1.0"
22 26 dependencies = [
@@ -1,3 +1,3 b''
1 1 [workspace]
2 members = ["hgcli"]
2 members = ["hgcli", "hg-core"]
3 3 exclude = ["chg"]
General Comments 0
You need to be logged in to leave comments. Login now