Show More
@@ -1,261 +1,255 b'' | |||||
1 | // ancestors.rs |
|
1 | // ancestors.rs | |
2 | // |
|
2 | // | |
3 | // Copyright 2018 Georges Racinet <gracinet@anybox.fr> |
|
3 | // Copyright 2018 Georges Racinet <gracinet@anybox.fr> | |
4 | // |
|
4 | // | |
5 | // This software may be used and distributed according to the terms of the |
|
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. |
|
6 | // GNU General Public License version 2 or any later version. | |
7 |
|
7 | |||
8 | //! Rust versions of generic DAG ancestors algorithms for Mercurial |
|
8 | //! Rust versions of generic DAG ancestors algorithms for Mercurial | |
9 |
|
9 | |||
10 | use super::{Graph, GraphError, Revision, NULL_REVISION}; |
|
10 | use super::{Graph, GraphError, Revision, NULL_REVISION}; | |
11 | use std::collections::{BinaryHeap, HashSet}; |
|
11 | use std::collections::{BinaryHeap, HashSet}; | |
12 |
|
12 | |||
13 | /// Iterator over the ancestors of a given list of revisions |
|
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 |
|
14 | /// This is a generic type, defined and implemented for any Graph, so that | |
15 | /// it's easy to |
|
15 | /// it's easy to | |
16 | /// |
|
16 | /// | |
17 | /// - unit test in pure Rust |
|
17 | /// - unit test in pure Rust | |
18 | /// - bind to main Mercurial code, potentially in several ways and have these |
|
18 | /// - bind to main Mercurial code, potentially in several ways and have these | |
19 | /// bindings evolve over time |
|
19 | /// bindings evolve over time | |
20 | pub struct AncestorsIterator<G: Graph> { |
|
20 | pub struct AncestorsIterator<G: Graph> { | |
21 | graph: G, |
|
21 | graph: G, | |
22 | visit: BinaryHeap<Revision>, |
|
22 | visit: BinaryHeap<Revision>, | |
23 | seen: HashSet<Revision>, |
|
23 | seen: HashSet<Revision>, | |
24 | stoprev: Revision, |
|
24 | stoprev: Revision, | |
25 | } |
|
25 | } | |
26 |
|
26 | |||
27 | impl<G: Graph> AncestorsIterator<G> { |
|
27 | impl<G: Graph> AncestorsIterator<G> { | |
28 | /// Constructor. |
|
28 | /// Constructor. | |
29 | /// |
|
29 | /// | |
30 | /// if `inclusive` is true, then the init revisions are emitted in |
|
30 | /// if `inclusive` is true, then the init revisions are emitted in | |
31 | /// particular, otherwise iteration starts from their parents. |
|
31 | /// particular, otherwise iteration starts from their parents. | |
32 | pub fn new<I>( |
|
32 | pub fn new<I>( | |
33 | graph: G, |
|
33 | graph: G, | |
34 | initrevs: I, |
|
34 | initrevs: I, | |
35 | stoprev: Revision, |
|
35 | stoprev: Revision, | |
36 | inclusive: bool, |
|
36 | inclusive: bool, | |
37 | ) -> Result<Self, GraphError> |
|
37 | ) -> Result<Self, GraphError> | |
38 | where |
|
38 | where | |
39 | I: IntoIterator<Item = Revision>, |
|
39 | I: IntoIterator<Item = Revision>, | |
40 | { |
|
40 | { | |
41 | let filtered_initrevs = initrevs.into_iter().filter(|&r| r >= stoprev); |
|
41 | let filtered_initrevs = initrevs.into_iter().filter(|&r| r >= stoprev); | |
42 | if inclusive { |
|
42 | if inclusive { | |
43 | let visit: BinaryHeap<Revision> = filtered_initrevs.collect(); |
|
43 | let visit: BinaryHeap<Revision> = filtered_initrevs.collect(); | |
44 | let seen = visit.iter().map(|&x| x).collect(); |
|
44 | let seen = visit.iter().map(|&x| x).collect(); | |
45 | return Ok(AncestorsIterator { |
|
45 | return Ok(AncestorsIterator { | |
46 | visit: visit, |
|
46 | visit: visit, | |
47 | seen: seen, |
|
47 | seen: seen, | |
48 | stoprev: stoprev, |
|
48 | stoprev: stoprev, | |
49 | graph: graph, |
|
49 | graph: graph, | |
50 | }); |
|
50 | }); | |
51 | } |
|
51 | } | |
52 | let mut this = AncestorsIterator { |
|
52 | let mut this = AncestorsIterator { | |
53 | visit: BinaryHeap::new(), |
|
53 | visit: BinaryHeap::new(), | |
54 | seen: HashSet::new(), |
|
54 | seen: HashSet::new(), | |
55 | stoprev: stoprev, |
|
55 | stoprev: stoprev, | |
56 | graph: graph, |
|
56 | graph: graph, | |
57 | }; |
|
57 | }; | |
58 | this.seen.insert(NULL_REVISION); |
|
58 | this.seen.insert(NULL_REVISION); | |
59 | for rev in filtered_initrevs { |
|
59 | for rev in filtered_initrevs { | |
60 |
|
|
60 | for parent in this.graph.parents(rev)?.iter().cloned() { | |
61 |
this.conditionally_push_rev(parent |
|
61 | this.conditionally_push_rev(parent); | |
62 | this.conditionally_push_rev(parents.1); |
|
62 | } | |
63 | } |
|
63 | } | |
64 | Ok(this) |
|
64 | Ok(this) | |
65 | } |
|
65 | } | |
66 |
|
66 | |||
67 | #[inline] |
|
67 | #[inline] | |
68 | fn conditionally_push_rev(&mut self, rev: Revision) { |
|
68 | fn conditionally_push_rev(&mut self, rev: Revision) { | |
69 | if self.stoprev <= rev && !self.seen.contains(&rev) { |
|
69 | if self.stoprev <= rev && !self.seen.contains(&rev) { | |
70 | self.seen.insert(rev); |
|
70 | self.seen.insert(rev); | |
71 | self.visit.push(rev); |
|
71 | self.visit.push(rev); | |
72 | } |
|
72 | } | |
73 | } |
|
73 | } | |
74 |
|
74 | |||
75 | /// Consumes partially the iterator to tell if the given target |
|
75 | /// Consumes partially the iterator to tell if the given target | |
76 | /// revision |
|
76 | /// revision | |
77 | /// is in the ancestors it emits. |
|
77 | /// is in the ancestors it emits. | |
78 | /// This is meant for iterators actually dedicated to that kind of |
|
78 | /// This is meant for iterators actually dedicated to that kind of | |
79 | /// purpose |
|
79 | /// purpose | |
80 | pub fn contains(&mut self, target: Revision) -> Result<bool, GraphError> { |
|
80 | pub fn contains(&mut self, target: Revision) -> Result<bool, GraphError> { | |
81 | if self.seen.contains(&target) && target != NULL_REVISION { |
|
81 | if self.seen.contains(&target) && target != NULL_REVISION { | |
82 | return Ok(true); |
|
82 | return Ok(true); | |
83 | } |
|
83 | } | |
84 | for item in self { |
|
84 | for item in self { | |
85 | let rev = item?; |
|
85 | let rev = item?; | |
86 | if rev == target { |
|
86 | if rev == target { | |
87 | return Ok(true); |
|
87 | return Ok(true); | |
88 | } |
|
88 | } | |
89 | if rev < target { |
|
89 | if rev < target { | |
90 | return Ok(false); |
|
90 | return Ok(false); | |
91 | } |
|
91 | } | |
92 | } |
|
92 | } | |
93 | Ok(false) |
|
93 | Ok(false) | |
94 | } |
|
94 | } | |
95 | } |
|
95 | } | |
96 |
|
96 | |||
97 | /// Main implementation. |
|
97 | /// Main implementation. | |
98 | /// |
|
98 | /// | |
99 | /// The algorithm is the same as in `_lazyancestorsiter()` from `ancestors.py` |
|
99 | /// The algorithm is the same as in `_lazyancestorsiter()` from `ancestors.py` | |
100 | /// with a few non crucial differences: |
|
100 | /// with a few non crucial differences: | |
101 | /// |
|
101 | /// | |
102 | /// - there's no filtering of invalid parent revisions. Actually, it should be |
|
102 | /// - there's no filtering of invalid parent revisions. Actually, it should be | |
103 | /// consistent and more efficient to filter them from the end caller. |
|
103 | /// consistent and more efficient to filter them from the end caller. | |
104 | /// - we don't have the optimization for adjacent revisions (i.e., the case |
|
104 | /// - we don't have the optimization for adjacent revisions (i.e., the case | |
105 | /// where `p1 == rev - 1`), because it amounts to update the first element of |
|
105 | /// where `p1 == rev - 1`), because it amounts to update the first element of | |
106 | /// the heap without sifting, which Rust's BinaryHeap doesn't let us do. |
|
106 | /// the heap without sifting, which Rust's BinaryHeap doesn't let us do. | |
107 | /// - we save a few pushes by comparing with `stoprev` before pushing |
|
107 | /// - we save a few pushes by comparing with `stoprev` before pushing | |
108 | impl<G: Graph> Iterator for AncestorsIterator<G> { |
|
108 | impl<G: Graph> Iterator for AncestorsIterator<G> { | |
109 | type Item = Result<Revision, GraphError>; |
|
109 | type Item = Result<Revision, GraphError>; | |
110 |
|
110 | |||
111 | fn next(&mut self) -> Option<Self::Item> { |
|
111 | fn next(&mut self) -> Option<Self::Item> { | |
112 | let current = match self.visit.peek() { |
|
112 | let current = match self.visit.peek() { | |
113 | None => { |
|
113 | None => { | |
114 | return None; |
|
114 | return None; | |
115 | } |
|
115 | } | |
116 | Some(c) => *c, |
|
116 | Some(c) => *c, | |
117 | }; |
|
117 | }; | |
118 |
let |
|
118 | let [p1, p2] = match self.graph.parents(current) { | |
119 | Ok(ps) => ps, |
|
119 | Ok(ps) => ps, | |
120 | Err(e) => return Some(Err(e)), |
|
120 | Err(e) => return Some(Err(e)), | |
121 | }; |
|
121 | }; | |
122 | if p1 < self.stoprev || self.seen.contains(&p1) { |
|
122 | if p1 < self.stoprev || self.seen.contains(&p1) { | |
123 | self.visit.pop(); |
|
123 | self.visit.pop(); | |
124 | } else { |
|
124 | } else { | |
125 | *(self.visit.peek_mut().unwrap()) = p1; |
|
125 | *(self.visit.peek_mut().unwrap()) = p1; | |
126 | self.seen.insert(p1); |
|
126 | self.seen.insert(p1); | |
127 | }; |
|
127 | }; | |
128 |
|
128 | |||
129 | self.conditionally_push_rev(p2); |
|
129 | self.conditionally_push_rev(p2); | |
130 | Some(Ok(current)) |
|
130 | Some(Ok(current)) | |
131 | } |
|
131 | } | |
132 | } |
|
132 | } | |
133 |
|
133 | |||
134 | #[cfg(test)] |
|
134 | #[cfg(test)] | |
135 | mod tests { |
|
135 | mod tests { | |
136 |
|
136 | |||
137 | use super::*; |
|
137 | use super::*; | |
138 |
|
138 | |||
139 | #[derive(Clone, Debug)] |
|
139 | #[derive(Clone, Debug)] | |
140 | struct Stub; |
|
140 | struct Stub; | |
141 |
|
141 | |||
142 | /// This is the same as the dict from test-ancestors.py |
|
142 | /// This is the same as the dict from test-ancestors.py | |
143 | impl Graph for Stub { |
|
143 | impl Graph for Stub { | |
144 | fn parents( |
|
144 | fn parents(&self, rev: Revision) -> Result<[Revision; 2], GraphError> { | |
145 | &self, |
|
|||
146 | rev: Revision, |
|
|||
147 | ) -> Result<(Revision, Revision), GraphError> { |
|
|||
148 | match rev { |
|
145 | match rev { | |
149 |
0 => Ok( |
|
146 | 0 => Ok([-1, -1]), | |
150 |
1 => Ok( |
|
147 | 1 => Ok([0, -1]), | |
151 |
2 => Ok( |
|
148 | 2 => Ok([1, -1]), | |
152 |
3 => Ok( |
|
149 | 3 => Ok([1, -1]), | |
153 |
4 => Ok( |
|
150 | 4 => Ok([2, -1]), | |
154 |
5 => Ok( |
|
151 | 5 => Ok([4, -1]), | |
155 |
6 => Ok( |
|
152 | 6 => Ok([4, -1]), | |
156 |
7 => Ok( |
|
153 | 7 => Ok([4, -1]), | |
157 |
8 => Ok( |
|
154 | 8 => Ok([-1, -1]), | |
158 |
9 => Ok( |
|
155 | 9 => Ok([6, 7]), | |
159 |
10 => Ok( |
|
156 | 10 => Ok([5, -1]), | |
160 |
11 => Ok( |
|
157 | 11 => Ok([3, 7]), | |
161 |
12 => Ok( |
|
158 | 12 => Ok([9, -1]), | |
162 |
13 => Ok( |
|
159 | 13 => Ok([8, -1]), | |
163 | r => Err(GraphError::ParentOutOfRange(r)), |
|
160 | r => Err(GraphError::ParentOutOfRange(r)), | |
164 | } |
|
161 | } | |
165 | } |
|
162 | } | |
166 | } |
|
163 | } | |
167 |
|
164 | |||
168 | fn list_ancestors<G: Graph>( |
|
165 | fn list_ancestors<G: Graph>( | |
169 | graph: G, |
|
166 | graph: G, | |
170 | initrevs: Vec<Revision>, |
|
167 | initrevs: Vec<Revision>, | |
171 | stoprev: Revision, |
|
168 | stoprev: Revision, | |
172 | inclusive: bool, |
|
169 | inclusive: bool, | |
173 | ) -> Vec<Revision> { |
|
170 | ) -> Vec<Revision> { | |
174 | AncestorsIterator::new(graph, initrevs, stoprev, inclusive) |
|
171 | AncestorsIterator::new(graph, initrevs, stoprev, inclusive) | |
175 | .unwrap() |
|
172 | .unwrap() | |
176 | .map(|res| res.unwrap()) |
|
173 | .map(|res| res.unwrap()) | |
177 | .collect() |
|
174 | .collect() | |
178 | } |
|
175 | } | |
179 |
|
176 | |||
180 | #[test] |
|
177 | #[test] | |
181 | /// Same tests as test-ancestor.py, without membership |
|
178 | /// Same tests as test-ancestor.py, without membership | |
182 | /// (see also test-ancestor.py.out) |
|
179 | /// (see also test-ancestor.py.out) | |
183 | fn test_list_ancestor() { |
|
180 | fn test_list_ancestor() { | |
184 | assert_eq!(list_ancestors(Stub, vec![], 0, false), vec![]); |
|
181 | assert_eq!(list_ancestors(Stub, vec![], 0, false), vec![]); | |
185 | assert_eq!( |
|
182 | assert_eq!( | |
186 | list_ancestors(Stub, vec![11, 13], 0, false), |
|
183 | list_ancestors(Stub, vec![11, 13], 0, false), | |
187 | vec![8, 7, 4, 3, 2, 1, 0] |
|
184 | vec![8, 7, 4, 3, 2, 1, 0] | |
188 | ); |
|
185 | ); | |
189 | assert_eq!(list_ancestors(Stub, vec![1, 3], 0, false), vec![1, 0]); |
|
186 | assert_eq!(list_ancestors(Stub, vec![1, 3], 0, false), vec![1, 0]); | |
190 | assert_eq!( |
|
187 | assert_eq!( | |
191 | list_ancestors(Stub, vec![11, 13], 0, true), |
|
188 | list_ancestors(Stub, vec![11, 13], 0, true), | |
192 | vec![13, 11, 8, 7, 4, 3, 2, 1, 0] |
|
189 | vec![13, 11, 8, 7, 4, 3, 2, 1, 0] | |
193 | ); |
|
190 | ); | |
194 | assert_eq!(list_ancestors(Stub, vec![11, 13], 6, false), vec![8, 7]); |
|
191 | assert_eq!(list_ancestors(Stub, vec![11, 13], 6, false), vec![8, 7]); | |
195 | assert_eq!( |
|
192 | assert_eq!( | |
196 | list_ancestors(Stub, vec![11, 13], 6, true), |
|
193 | list_ancestors(Stub, vec![11, 13], 6, true), | |
197 | vec![13, 11, 8, 7] |
|
194 | vec![13, 11, 8, 7] | |
198 | ); |
|
195 | ); | |
199 | assert_eq!(list_ancestors(Stub, vec![11, 13], 11, true), vec![13, 11]); |
|
196 | assert_eq!(list_ancestors(Stub, vec![11, 13], 11, true), vec![13, 11]); | |
200 | assert_eq!(list_ancestors(Stub, vec![11, 13], 12, true), vec![13]); |
|
197 | assert_eq!(list_ancestors(Stub, vec![11, 13], 12, true), vec![13]); | |
201 | assert_eq!( |
|
198 | assert_eq!( | |
202 | list_ancestors(Stub, vec![10, 1], 0, true), |
|
199 | list_ancestors(Stub, vec![10, 1], 0, true), | |
203 | vec![10, 5, 4, 2, 1, 0] |
|
200 | vec![10, 5, 4, 2, 1, 0] | |
204 | ); |
|
201 | ); | |
205 | } |
|
202 | } | |
206 |
|
203 | |||
207 | #[test] |
|
204 | #[test] | |
208 | /// Corner case that's not directly in test-ancestors.py, but |
|
205 | /// Corner case that's not directly in test-ancestors.py, but | |
209 | /// that happens quite often, as demonstrated by running the whole |
|
206 | /// that happens quite often, as demonstrated by running the whole | |
210 | /// suite. |
|
207 | /// suite. | |
211 | /// For instance, run tests/test-obsolete-checkheads.t |
|
208 | /// For instance, run tests/test-obsolete-checkheads.t | |
212 | fn test_nullrev_input() { |
|
209 | fn test_nullrev_input() { | |
213 | let mut iter = |
|
210 | let mut iter = | |
214 | AncestorsIterator::new(Stub, vec![-1], 0, false).unwrap(); |
|
211 | AncestorsIterator::new(Stub, vec![-1], 0, false).unwrap(); | |
215 | assert_eq!(iter.next(), None) |
|
212 | assert_eq!(iter.next(), None) | |
216 | } |
|
213 | } | |
217 |
|
214 | |||
218 | #[test] |
|
215 | #[test] | |
219 | fn test_contains() { |
|
216 | fn test_contains() { | |
220 | let mut lazy = |
|
217 | let mut lazy = | |
221 | AncestorsIterator::new(Stub, vec![10, 1], 0, true).unwrap(); |
|
218 | AncestorsIterator::new(Stub, vec![10, 1], 0, true).unwrap(); | |
222 | assert!(lazy.contains(1).unwrap()); |
|
219 | assert!(lazy.contains(1).unwrap()); | |
223 | assert!(!lazy.contains(3).unwrap()); |
|
220 | assert!(!lazy.contains(3).unwrap()); | |
224 |
|
221 | |||
225 | let mut lazy = |
|
222 | let mut lazy = | |
226 | AncestorsIterator::new(Stub, vec![0], 0, false).unwrap(); |
|
223 | AncestorsIterator::new(Stub, vec![0], 0, false).unwrap(); | |
227 | assert!(!lazy.contains(NULL_REVISION).unwrap()); |
|
224 | assert!(!lazy.contains(NULL_REVISION).unwrap()); | |
228 | } |
|
225 | } | |
229 |
|
226 | |||
230 | /// A corrupted Graph, supporting error handling tests |
|
227 | /// A corrupted Graph, supporting error handling tests | |
231 | struct Corrupted; |
|
228 | struct Corrupted; | |
232 |
|
229 | |||
233 | impl Graph for Corrupted { |
|
230 | impl Graph for Corrupted { | |
234 | fn parents( |
|
231 | fn parents(&self, rev: Revision) -> Result<[Revision; 2], GraphError> { | |
235 | &self, |
|
|||
236 | rev: Revision, |
|
|||
237 | ) -> Result<(Revision, Revision), GraphError> { |
|
|||
238 | match rev { |
|
232 | match rev { | |
239 |
1 => Ok( |
|
233 | 1 => Ok([0, -1]), | |
240 | r => Err(GraphError::ParentOutOfRange(r)), |
|
234 | r => Err(GraphError::ParentOutOfRange(r)), | |
241 | } |
|
235 | } | |
242 | } |
|
236 | } | |
243 | } |
|
237 | } | |
244 |
|
238 | |||
245 | #[test] |
|
239 | #[test] | |
246 | fn test_initrev_out_of_range() { |
|
240 | fn test_initrev_out_of_range() { | |
247 | // inclusive=false looks up initrev's parents right away |
|
241 | // inclusive=false looks up initrev's parents right away | |
248 | match AncestorsIterator::new(Stub, vec![25], 0, false) { |
|
242 | match AncestorsIterator::new(Stub, vec![25], 0, false) { | |
249 | Ok(_) => panic!("Should have been ParentOutOfRange"), |
|
243 | Ok(_) => panic!("Should have been ParentOutOfRange"), | |
250 | Err(e) => assert_eq!(e, GraphError::ParentOutOfRange(25)), |
|
244 | Err(e) => assert_eq!(e, GraphError::ParentOutOfRange(25)), | |
251 | } |
|
245 | } | |
252 | } |
|
246 | } | |
253 |
|
247 | |||
254 | #[test] |
|
248 | #[test] | |
255 | fn test_next_out_of_range() { |
|
249 | fn test_next_out_of_range() { | |
256 | // inclusive=false looks up initrev's parents right away |
|
250 | // inclusive=false looks up initrev's parents right away | |
257 | let mut iter = |
|
251 | let mut iter = | |
258 | AncestorsIterator::new(Corrupted, vec![1], 0, false).unwrap(); |
|
252 | AncestorsIterator::new(Corrupted, vec![1], 0, false).unwrap(); | |
259 | assert_eq!(iter.next(), Some(Err(GraphError::ParentOutOfRange(0)))); |
|
253 | assert_eq!(iter.next(), Some(Err(GraphError::ParentOutOfRange(0)))); | |
260 | } |
|
254 | } | |
261 | } |
|
255 | } |
@@ -1,24 +1,24 b'' | |||||
1 | // Copyright 2018 Georges Racinet <gracinet@anybox.fr> |
|
1 | // Copyright 2018 Georges Racinet <gracinet@anybox.fr> | |
2 | // |
|
2 | // | |
3 | // This software may be used and distributed according to the terms of the |
|
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. |
|
4 | // GNU General Public License version 2 or any later version. | |
5 | mod ancestors; |
|
5 | mod ancestors; | |
6 | pub use ancestors::AncestorsIterator; |
|
6 | pub use ancestors::AncestorsIterator; | |
7 |
|
7 | |||
8 | /// Mercurial revision numbers |
|
8 | /// Mercurial revision numbers | |
9 | /// |
|
9 | /// | |
10 | /// As noted in revlog.c, revision numbers are actually encoded in |
|
10 | /// As noted in revlog.c, revision numbers are actually encoded in | |
11 | /// 4 bytes, and are liberally converted to ints, whence the i32 |
|
11 | /// 4 bytes, and are liberally converted to ints, whence the i32 | |
12 | pub type Revision = i32; |
|
12 | pub type Revision = i32; | |
13 |
|
13 | |||
14 | pub const NULL_REVISION: Revision = -1; |
|
14 | pub const NULL_REVISION: Revision = -1; | |
15 |
|
15 | |||
16 | /// The simplest expression of what we need of Mercurial DAGs. |
|
16 | /// The simplest expression of what we need of Mercurial DAGs. | |
17 | pub trait Graph { |
|
17 | pub trait Graph { | |
18 |
fn parents(&self, Revision) -> Result< |
|
18 | fn parents(&self, Revision) -> Result<[Revision; 2], GraphError>; | |
19 | } |
|
19 | } | |
20 |
|
20 | |||
21 | #[derive(Clone, Debug, PartialEq)] |
|
21 | #[derive(Clone, Debug, PartialEq)] | |
22 | pub enum GraphError { |
|
22 | pub enum GraphError { | |
23 | ParentOutOfRange(Revision), |
|
23 | ParentOutOfRange(Revision), | |
24 | } |
|
24 | } |
@@ -1,271 +1,271 b'' | |||||
1 | // Copyright 2018 Georges Racinet <gracinet@anybox.fr> |
|
1 | // Copyright 2018 Georges Racinet <gracinet@anybox.fr> | |
2 | // |
|
2 | // | |
3 | // This software may be used and distributed according to the terms of the |
|
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. |
|
4 | // GNU General Public License version 2 or any later version. | |
5 |
|
5 | |||
6 | //! Bindings for CPython extension code |
|
6 | //! Bindings for CPython extension code | |
7 | //! |
|
7 | //! | |
8 | //! This exposes methods to build and use a `rustlazyancestors` iterator |
|
8 | //! This exposes methods to build and use a `rustlazyancestors` iterator | |
9 | //! from C code, using an index and its parents function that are passed |
|
9 | //! from C code, using an index and its parents function that are passed | |
10 | //! from the caller at instantiation. |
|
10 | //! from the caller at instantiation. | |
11 |
|
11 | |||
12 | use hg::AncestorsIterator; |
|
12 | use hg::AncestorsIterator; | |
13 | use hg::{Graph, GraphError, Revision, NULL_REVISION}; |
|
13 | use hg::{Graph, GraphError, Revision, NULL_REVISION}; | |
14 | use libc::{c_int, c_long, c_void, ssize_t}; |
|
14 | use libc::{c_int, c_long, c_void, ssize_t}; | |
15 | use std::ptr::null_mut; |
|
15 | use std::ptr::null_mut; | |
16 | use std::slice; |
|
16 | use std::slice; | |
17 |
|
17 | |||
18 | type IndexPtr = *mut c_void; |
|
18 | type IndexPtr = *mut c_void; | |
19 |
|
19 | |||
20 | extern "C" { |
|
20 | extern "C" { | |
21 | fn HgRevlogIndex_GetParents( |
|
21 | fn HgRevlogIndex_GetParents( | |
22 | op: IndexPtr, |
|
22 | op: IndexPtr, | |
23 | rev: c_int, |
|
23 | rev: c_int, | |
24 | parents: *mut [c_int; 2], |
|
24 | parents: *mut [c_int; 2], | |
25 | ) -> c_int; |
|
25 | ) -> c_int; | |
26 | } |
|
26 | } | |
27 |
|
27 | |||
28 | /// A Graph backed up by objects and functions from revlog.c |
|
28 | /// A Graph backed up by objects and functions from revlog.c | |
29 | /// |
|
29 | /// | |
30 | /// This implementation of the Graph trait, relies on (pointers to) |
|
30 | /// This implementation of the Graph trait, relies on (pointers to) | |
31 | /// - the C index object (`index` member) |
|
31 | /// - the C index object (`index` member) | |
32 | /// - the `index_get_parents()` function (`parents` member) |
|
32 | /// - the `index_get_parents()` function (`parents` member) | |
33 | pub struct Index { |
|
33 | pub struct Index { | |
34 | index: IndexPtr, |
|
34 | index: IndexPtr, | |
35 | } |
|
35 | } | |
36 |
|
36 | |||
37 | impl Index { |
|
37 | impl Index { | |
38 | pub fn new(index: IndexPtr) -> Self { |
|
38 | pub fn new(index: IndexPtr) -> Self { | |
39 | Index { |
|
39 | Index { | |
40 | index: index, |
|
40 | index: index, | |
41 | } |
|
41 | } | |
42 | } |
|
42 | } | |
43 | } |
|
43 | } | |
44 |
|
44 | |||
45 | impl Graph for Index { |
|
45 | impl Graph for Index { | |
46 | /// wrap a call to the C extern parents function |
|
46 | /// wrap a call to the C extern parents function | |
47 |
fn parents(&self, rev: Revision) -> Result< |
|
47 | fn parents(&self, rev: Revision) -> Result<[Revision; 2], GraphError> { | |
48 | let mut res: [c_int; 2] = [0; 2]; |
|
48 | let mut res: [c_int; 2] = [0; 2]; | |
49 | let code = |
|
49 | let code = | |
50 | unsafe { HgRevlogIndex_GetParents(self.index, rev, &mut res as *mut [c_int; 2]) }; |
|
50 | unsafe { HgRevlogIndex_GetParents(self.index, rev, &mut res as *mut [c_int; 2]) }; | |
51 | match code { |
|
51 | match code { | |
52 |
0 => Ok( |
|
52 | 0 => Ok(res), | |
53 | _ => Err(GraphError::ParentOutOfRange(rev)), |
|
53 | _ => Err(GraphError::ParentOutOfRange(rev)), | |
54 | } |
|
54 | } | |
55 | } |
|
55 | } | |
56 | } |
|
56 | } | |
57 |
|
57 | |||
58 | /// Wrapping of AncestorsIterator<Index> constructor, for C callers. |
|
58 | /// Wrapping of AncestorsIterator<Index> constructor, for C callers. | |
59 | /// |
|
59 | /// | |
60 | /// Besides `initrevs`, `stoprev` and `inclusive`, that are converted |
|
60 | /// Besides `initrevs`, `stoprev` and `inclusive`, that are converted | |
61 | /// we receive the index and the parents function as pointers |
|
61 | /// we receive the index and the parents function as pointers | |
62 | #[no_mangle] |
|
62 | #[no_mangle] | |
63 | pub extern "C" fn rustlazyancestors_init( |
|
63 | pub extern "C" fn rustlazyancestors_init( | |
64 | index: IndexPtr, |
|
64 | index: IndexPtr, | |
65 | initrevslen: ssize_t, |
|
65 | initrevslen: ssize_t, | |
66 | initrevs: *mut c_long, |
|
66 | initrevs: *mut c_long, | |
67 | stoprev: c_long, |
|
67 | stoprev: c_long, | |
68 | inclusive: c_int, |
|
68 | inclusive: c_int, | |
69 | ) -> *mut AncestorsIterator<Index> { |
|
69 | ) -> *mut AncestorsIterator<Index> { | |
70 | assert!(initrevslen >= 0); |
|
70 | assert!(initrevslen >= 0); | |
71 | unsafe { |
|
71 | unsafe { | |
72 | raw_init( |
|
72 | raw_init( | |
73 | Index::new(index), |
|
73 | Index::new(index), | |
74 | initrevslen as usize, |
|
74 | initrevslen as usize, | |
75 | initrevs, |
|
75 | initrevs, | |
76 | stoprev, |
|
76 | stoprev, | |
77 | inclusive, |
|
77 | inclusive, | |
78 | ) |
|
78 | ) | |
79 | } |
|
79 | } | |
80 | } |
|
80 | } | |
81 |
|
81 | |||
82 | /// Testable (for any Graph) version of rustlazyancestors_init |
|
82 | /// Testable (for any Graph) version of rustlazyancestors_init | |
83 | #[inline] |
|
83 | #[inline] | |
84 | unsafe fn raw_init<G: Graph>( |
|
84 | unsafe fn raw_init<G: Graph>( | |
85 | graph: G, |
|
85 | graph: G, | |
86 | initrevslen: usize, |
|
86 | initrevslen: usize, | |
87 | initrevs: *mut c_long, |
|
87 | initrevs: *mut c_long, | |
88 | stoprev: c_long, |
|
88 | stoprev: c_long, | |
89 | inclusive: c_int, |
|
89 | inclusive: c_int, | |
90 | ) -> *mut AncestorsIterator<G> { |
|
90 | ) -> *mut AncestorsIterator<G> { | |
91 | let inclb = match inclusive { |
|
91 | let inclb = match inclusive { | |
92 | 0 => false, |
|
92 | 0 => false, | |
93 | 1 => true, |
|
93 | 1 => true, | |
94 | _ => { |
|
94 | _ => { | |
95 | return null_mut(); |
|
95 | return null_mut(); | |
96 | } |
|
96 | } | |
97 | }; |
|
97 | }; | |
98 |
|
98 | |||
99 | let slice = slice::from_raw_parts(initrevs, initrevslen); |
|
99 | let slice = slice::from_raw_parts(initrevs, initrevslen); | |
100 |
|
100 | |||
101 | Box::into_raw(Box::new(match AncestorsIterator::new( |
|
101 | Box::into_raw(Box::new(match AncestorsIterator::new( | |
102 | graph, |
|
102 | graph, | |
103 | slice.into_iter().map(|&r| r as Revision), |
|
103 | slice.into_iter().map(|&r| r as Revision), | |
104 | stoprev as Revision, |
|
104 | stoprev as Revision, | |
105 | inclb, |
|
105 | inclb, | |
106 | ) { |
|
106 | ) { | |
107 | Ok(it) => it, |
|
107 | Ok(it) => it, | |
108 | Err(_) => { |
|
108 | Err(_) => { | |
109 | return null_mut(); |
|
109 | return null_mut(); | |
110 | } |
|
110 | } | |
111 | })) |
|
111 | })) | |
112 | } |
|
112 | } | |
113 |
|
113 | |||
114 | /// Deallocator to be called from C code |
|
114 | /// Deallocator to be called from C code | |
115 | #[no_mangle] |
|
115 | #[no_mangle] | |
116 | pub extern "C" fn rustlazyancestors_drop(raw_iter: *mut AncestorsIterator<Index>) { |
|
116 | pub extern "C" fn rustlazyancestors_drop(raw_iter: *mut AncestorsIterator<Index>) { | |
117 | raw_drop(raw_iter); |
|
117 | raw_drop(raw_iter); | |
118 | } |
|
118 | } | |
119 |
|
119 | |||
120 | /// Testable (for any Graph) version of rustlazayancestors_drop |
|
120 | /// Testable (for any Graph) version of rustlazayancestors_drop | |
121 | #[inline] |
|
121 | #[inline] | |
122 | fn raw_drop<G: Graph>(raw_iter: *mut AncestorsIterator<G>) { |
|
122 | fn raw_drop<G: Graph>(raw_iter: *mut AncestorsIterator<G>) { | |
123 | unsafe { |
|
123 | unsafe { | |
124 | Box::from_raw(raw_iter); |
|
124 | Box::from_raw(raw_iter); | |
125 | } |
|
125 | } | |
126 | } |
|
126 | } | |
127 |
|
127 | |||
128 | /// Iteration main method to be called from C code |
|
128 | /// Iteration main method to be called from C code | |
129 | /// |
|
129 | /// | |
130 | /// We convert the end of iteration into NULL_REVISION, |
|
130 | /// We convert the end of iteration into NULL_REVISION, | |
131 | /// it will be up to the C wrapper to convert that back into a Python end of |
|
131 | /// it will be up to the C wrapper to convert that back into a Python end of | |
132 | /// iteration |
|
132 | /// iteration | |
133 | #[no_mangle] |
|
133 | #[no_mangle] | |
134 | pub extern "C" fn rustlazyancestors_next(raw: *mut AncestorsIterator<Index>) -> c_long { |
|
134 | pub extern "C" fn rustlazyancestors_next(raw: *mut AncestorsIterator<Index>) -> c_long { | |
135 | raw_next(raw) |
|
135 | raw_next(raw) | |
136 | } |
|
136 | } | |
137 |
|
137 | |||
138 | /// Testable (for any Graph) version of rustlazayancestors_next |
|
138 | /// Testable (for any Graph) version of rustlazayancestors_next | |
139 | #[inline] |
|
139 | #[inline] | |
140 | fn raw_next<G: Graph>(raw: *mut AncestorsIterator<G>) -> c_long { |
|
140 | fn raw_next<G: Graph>(raw: *mut AncestorsIterator<G>) -> c_long { | |
141 | let as_ref = unsafe { &mut *raw }; |
|
141 | let as_ref = unsafe { &mut *raw }; | |
142 | let rev = match as_ref.next() { |
|
142 | let rev = match as_ref.next() { | |
143 | Some(Ok(rev)) => rev, |
|
143 | Some(Ok(rev)) => rev, | |
144 | Some(Err(_)) | None => NULL_REVISION, |
|
144 | Some(Err(_)) | None => NULL_REVISION, | |
145 | }; |
|
145 | }; | |
146 | rev as c_long |
|
146 | rev as c_long | |
147 | } |
|
147 | } | |
148 |
|
148 | |||
149 | #[no_mangle] |
|
149 | #[no_mangle] | |
150 | pub extern "C" fn rustlazyancestors_contains( |
|
150 | pub extern "C" fn rustlazyancestors_contains( | |
151 | raw: *mut AncestorsIterator<Index>, |
|
151 | raw: *mut AncestorsIterator<Index>, | |
152 | target: c_long, |
|
152 | target: c_long, | |
153 | ) -> c_int { |
|
153 | ) -> c_int { | |
154 | raw_contains(raw, target) |
|
154 | raw_contains(raw, target) | |
155 | } |
|
155 | } | |
156 |
|
156 | |||
157 | /// Testable (for any Graph) version of rustlazayancestors_next |
|
157 | /// Testable (for any Graph) version of rustlazayancestors_next | |
158 | #[inline] |
|
158 | #[inline] | |
159 | fn raw_contains<G: Graph>( |
|
159 | fn raw_contains<G: Graph>( | |
160 | raw: *mut AncestorsIterator<G>, |
|
160 | raw: *mut AncestorsIterator<G>, | |
161 | target: c_long, |
|
161 | target: c_long, | |
162 | ) -> c_int { |
|
162 | ) -> c_int { | |
163 | let as_ref = unsafe { &mut *raw }; |
|
163 | let as_ref = unsafe { &mut *raw }; | |
164 | match as_ref.contains(target as Revision) { |
|
164 | match as_ref.contains(target as Revision) { | |
165 | Ok(r) => r as c_int, |
|
165 | Ok(r) => r as c_int, | |
166 | Err(_) => -1, |
|
166 | Err(_) => -1, | |
167 | } |
|
167 | } | |
168 | } |
|
168 | } | |
169 |
|
169 | |||
170 | #[cfg(test)] |
|
170 | #[cfg(test)] | |
171 | mod tests { |
|
171 | mod tests { | |
172 | use super::*; |
|
172 | use super::*; | |
173 | use std::thread; |
|
173 | use std::thread; | |
174 |
|
174 | |||
175 | #[derive(Clone, Debug)] |
|
175 | #[derive(Clone, Debug)] | |
176 | struct Stub; |
|
176 | struct Stub; | |
177 |
|
177 | |||
178 | impl Graph for Stub { |
|
178 | impl Graph for Stub { | |
179 |
fn parents(&self, r: Revision) -> Result< |
|
179 | fn parents(&self, r: Revision) -> Result<[Revision; 2], GraphError> { | |
180 | match r { |
|
180 | match r { | |
181 | 25 => Err(GraphError::ParentOutOfRange(25)), |
|
181 | 25 => Err(GraphError::ParentOutOfRange(25)), | |
182 |
_ => Ok( |
|
182 | _ => Ok([1, 2]), | |
183 | } |
|
183 | } | |
184 | } |
|
184 | } | |
185 | } |
|
185 | } | |
186 |
|
186 | |||
187 | /// Helper for test_init_next() |
|
187 | /// Helper for test_init_next() | |
188 | fn stub_raw_init( |
|
188 | fn stub_raw_init( | |
189 | initrevslen: usize, |
|
189 | initrevslen: usize, | |
190 | initrevs: usize, |
|
190 | initrevs: usize, | |
191 | stoprev: c_long, |
|
191 | stoprev: c_long, | |
192 | inclusive: c_int, |
|
192 | inclusive: c_int, | |
193 | ) -> usize { |
|
193 | ) -> usize { | |
194 | unsafe { |
|
194 | unsafe { | |
195 | raw_init( |
|
195 | raw_init( | |
196 | Stub, |
|
196 | Stub, | |
197 | initrevslen, |
|
197 | initrevslen, | |
198 | initrevs as *mut c_long, |
|
198 | initrevs as *mut c_long, | |
199 | stoprev, |
|
199 | stoprev, | |
200 | inclusive, |
|
200 | inclusive, | |
201 | ) as usize |
|
201 | ) as usize | |
202 | } |
|
202 | } | |
203 | } |
|
203 | } | |
204 |
|
204 | |||
205 | fn stub_raw_init_from_vec( |
|
205 | fn stub_raw_init_from_vec( | |
206 | mut initrevs: Vec<c_long>, |
|
206 | mut initrevs: Vec<c_long>, | |
207 | stoprev: c_long, |
|
207 | stoprev: c_long, | |
208 | inclusive: c_int, |
|
208 | inclusive: c_int, | |
209 | ) -> *mut AncestorsIterator<Stub> { |
|
209 | ) -> *mut AncestorsIterator<Stub> { | |
210 | unsafe { |
|
210 | unsafe { | |
211 | raw_init( |
|
211 | raw_init( | |
212 | Stub, |
|
212 | Stub, | |
213 | initrevs.len(), |
|
213 | initrevs.len(), | |
214 | initrevs.as_mut_ptr(), |
|
214 | initrevs.as_mut_ptr(), | |
215 | stoprev, |
|
215 | stoprev, | |
216 | inclusive, |
|
216 | inclusive, | |
217 | ) |
|
217 | ) | |
218 | } |
|
218 | } | |
219 | } |
|
219 | } | |
220 |
|
220 | |||
221 | #[test] |
|
221 | #[test] | |
222 | // Test what happens when we init an Iterator as with the exposed C ABI |
|
222 | // Test what happens when we init an Iterator as with the exposed C ABI | |
223 | // and try to use it afterwards |
|
223 | // and try to use it afterwards | |
224 | // We spawn new threads, in order to make memory consistency harder |
|
224 | // We spawn new threads, in order to make memory consistency harder | |
225 | // but this forces us to convert the pointers into shareable usizes. |
|
225 | // but this forces us to convert the pointers into shareable usizes. | |
226 | fn test_init_next() { |
|
226 | fn test_init_next() { | |
227 | let mut initrevs: Vec<c_long> = vec![11, 13]; |
|
227 | let mut initrevs: Vec<c_long> = vec![11, 13]; | |
228 | let initrevs_len = initrevs.len(); |
|
228 | let initrevs_len = initrevs.len(); | |
229 | let initrevs_ptr = initrevs.as_mut_ptr() as usize; |
|
229 | let initrevs_ptr = initrevs.as_mut_ptr() as usize; | |
230 | let handler = thread::spawn(move || stub_raw_init(initrevs_len, initrevs_ptr, 0, 1)); |
|
230 | let handler = thread::spawn(move || stub_raw_init(initrevs_len, initrevs_ptr, 0, 1)); | |
231 | let raw = handler.join().unwrap() as *mut AncestorsIterator<Stub>; |
|
231 | let raw = handler.join().unwrap() as *mut AncestorsIterator<Stub>; | |
232 |
|
232 | |||
233 | assert_eq!(raw_next(raw), 13); |
|
233 | assert_eq!(raw_next(raw), 13); | |
234 | assert_eq!(raw_next(raw), 11); |
|
234 | assert_eq!(raw_next(raw), 11); | |
235 | assert_eq!(raw_next(raw), 2); |
|
235 | assert_eq!(raw_next(raw), 2); | |
236 | assert_eq!(raw_next(raw), 1); |
|
236 | assert_eq!(raw_next(raw), 1); | |
237 | assert_eq!(raw_next(raw), NULL_REVISION as c_long); |
|
237 | assert_eq!(raw_next(raw), NULL_REVISION as c_long); | |
238 | raw_drop(raw); |
|
238 | raw_drop(raw); | |
239 | } |
|
239 | } | |
240 |
|
240 | |||
241 | #[test] |
|
241 | #[test] | |
242 | fn test_init_wrong_bool() { |
|
242 | fn test_init_wrong_bool() { | |
243 | assert_eq!(stub_raw_init_from_vec(vec![11, 13], 0, 2), null_mut()); |
|
243 | assert_eq!(stub_raw_init_from_vec(vec![11, 13], 0, 2), null_mut()); | |
244 | } |
|
244 | } | |
245 |
|
245 | |||
246 | #[test] |
|
246 | #[test] | |
247 | fn test_empty() { |
|
247 | fn test_empty() { | |
248 | let raw = stub_raw_init_from_vec(vec![], 0, 1); |
|
248 | let raw = stub_raw_init_from_vec(vec![], 0, 1); | |
249 | assert_eq!(raw_next(raw), NULL_REVISION as c_long); |
|
249 | assert_eq!(raw_next(raw), NULL_REVISION as c_long); | |
250 | raw_drop(raw); |
|
250 | raw_drop(raw); | |
251 | } |
|
251 | } | |
252 |
|
252 | |||
253 | #[test] |
|
253 | #[test] | |
254 | fn test_init_err_out_of_range() { |
|
254 | fn test_init_err_out_of_range() { | |
255 | assert!(stub_raw_init_from_vec(vec![25], 0, 0).is_null()); |
|
255 | assert!(stub_raw_init_from_vec(vec![25], 0, 0).is_null()); | |
256 | } |
|
256 | } | |
257 |
|
257 | |||
258 | #[test] |
|
258 | #[test] | |
259 | fn test_contains() { |
|
259 | fn test_contains() { | |
260 | let raw = stub_raw_init_from_vec(vec![5, 6], 0, 1); |
|
260 | let raw = stub_raw_init_from_vec(vec![5, 6], 0, 1); | |
261 | assert_eq!(raw_contains(raw, 5), 1); |
|
261 | assert_eq!(raw_contains(raw, 5), 1); | |
262 | assert_eq!(raw_contains(raw, 2), 1); |
|
262 | assert_eq!(raw_contains(raw, 2), 1); | |
263 | } |
|
263 | } | |
264 |
|
264 | |||
265 | #[test] |
|
265 | #[test] | |
266 | fn test_contains_exclusive() { |
|
266 | fn test_contains_exclusive() { | |
267 | let raw = stub_raw_init_from_vec(vec![5, 6], 0, 0); |
|
267 | let raw = stub_raw_init_from_vec(vec![5, 6], 0, 0); | |
268 | assert_eq!(raw_contains(raw, 5), 0); |
|
268 | assert_eq!(raw_contains(raw, 5), 0); | |
269 | assert_eq!(raw_contains(raw, 2), 1); |
|
269 | assert_eq!(raw_contains(raw, 2), 1); | |
270 | } |
|
270 | } | |
271 | } |
|
271 | } |
General Comments 0
You need to be logged in to leave comments.
Login now