Mercurial > public > mercurial-scm > hg
annotate rust/hg-core/src/ancestors.rs @ 40271:dbc28c91f7ff
rust: pure Rust lazyancestors iterator
This is the first of a patch series aiming to provide an
alternative implementation in the Rust programming language
of the _lazyancestorsiter from the ancestor module.
This iterator has been brought to our attention by the people at
Octobus, as a potential good candidate for incremental "oxydation"
(rewriting in Rust), because it has shown performance issues lately
and it merely deals with ints (revision numbers) obtained by calling
the index, whih should be directly callable from Rust code,
being itself implemented as a C extension.
The idea behind this series is to provide a minimal example of Rust code
collaborating with existing C and Python code. To open the way to gradually
rewriting more of Mercurial's Python code in Rust, without being forced to pay
a large initial cost of rewriting the existing fast core into Rust.
This patch does not introduce any bindings to other Mercurial code
yet. Instead, it introduces the necessary abstractions to address the problem
independently, and unit-test it.
Since this is the first use of Rust as a Python module within Mercurial,
the hg-core crate gets created within this patch. See its Cargo.toml for more
details.
Someone with a rustc/cargo installation may chdir into rust/hg-core and
run the tests by issuing:
cargo test --lib
The algorithm is a bit simplified (see details in docstrings),
and at its simplest becomes rather trivial, showcasing that Rust has
batteries included too: BinaryHeap, the Rust analog of Python's heapq
does actually all the work.
The implementation can be further optimized and probably be made more
idiomatic Rust.
author | Georges Racinet <gracinet@anybox.fr> |
---|---|
date | Thu, 27 Sep 2018 17:03:16 +0200 |
parents | |
children | 72b94f946e90 |
rev | line source |
---|---|
40271
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
1 // ancestors.rs |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
2 // |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
3 // Copyright 2018 Georges Racinet <gracinet@anybox.fr> |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
4 // |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
5 // This software may be used and distributed according to the terms of the |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
6 // GNU General Public License version 2 or any later version. |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
7 |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
8 //! Rust versions of generic DAG ancestors algorithms for Mercurial |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
9 |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
10 use super::{Graph, GraphError, Revision, NULL_REVISION}; |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
11 use std::collections::{BinaryHeap, HashSet}; |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
12 |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
13 /// Iterator over the ancestors of a given list of revisions |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
14 /// This is a generic type, defined and implemented for any Graph, so that |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
15 /// it's easy to |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
16 /// |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
17 /// - unit test in pure Rust |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
18 /// - bind to main Mercurial code, potentially in several ways and have these |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
19 /// bindings evolve over time |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
20 pub struct AncestorsIterator<G: Graph> { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
21 graph: G, |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
22 visit: BinaryHeap<Revision>, |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
23 seen: HashSet<Revision>, |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
24 stoprev: Revision, |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
25 } |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
26 |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
27 impl<G: Graph> AncestorsIterator<G> { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
28 /// Constructor. |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
29 /// |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
30 /// if `inclusive` is true, then the init revisions are emitted in |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
31 /// particular, otherwise iteration starts from their parents. |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
32 pub fn new<I>( |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
33 graph: G, |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
34 initrevs: I, |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
35 stoprev: Revision, |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
36 inclusive: bool, |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
37 ) -> Result<Self, GraphError> |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
38 where |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
39 I: IntoIterator<Item = Revision>, |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
40 { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
41 let filtered_initrevs = initrevs.into_iter().filter(|&r| r >= stoprev); |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
42 if inclusive { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
43 let visit: BinaryHeap<Revision> = filtered_initrevs.collect(); |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
44 let seen = visit.iter().map(|&x| x).collect(); |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
45 return Ok(AncestorsIterator { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
46 visit: visit, |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
47 seen: seen, |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
48 stoprev: stoprev, |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
49 graph: graph, |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
50 }); |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
51 } |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
52 let mut this = AncestorsIterator { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
53 visit: BinaryHeap::new(), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
54 seen: HashSet::new(), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
55 stoprev: stoprev, |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
56 graph: graph, |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
57 }; |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
58 this.seen.insert(NULL_REVISION); |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
59 for rev in filtered_initrevs { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
60 this.conditionally_push_parents(rev)?; |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
61 } |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
62 Ok(this) |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
63 } |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
64 |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
65 #[inline] |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
66 fn conditionally_push_rev(&mut self, rev: Revision) { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
67 if self.stoprev <= rev && !self.seen.contains(&rev) { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
68 self.seen.insert(rev); |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
69 self.visit.push(rev); |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
70 } |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
71 } |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
72 |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
73 #[inline] |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
74 fn conditionally_push_parents( |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
75 &mut self, |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
76 rev: Revision, |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
77 ) -> Result<(), GraphError> { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
78 let parents = self.graph.parents(rev)?; |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
79 self.conditionally_push_rev(parents.0); |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
80 self.conditionally_push_rev(parents.1); |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
81 Ok(()) |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
82 } |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
83 } |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
84 |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
85 /// Main implementation. |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
86 /// |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
87 /// The algorithm is the same as in `_lazyancestorsiter()` from `ancestors.py` |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
88 /// with a few non crucial differences: |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
89 /// |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
90 /// - there's no filtering of invalid parent revisions. Actually, it should be |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
91 /// consistent and more efficient to filter them from the end caller. |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
92 /// - we don't use the equivalent of `heapq.heapreplace()`, but we should, for |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
93 /// the same reasons (using `peek_mut`) |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
94 /// - we don't have the optimization for adjacent revs (case where p1 == rev-1) |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
95 /// - we save a few pushes by comparing with `stoprev` before pushing |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
96 /// |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
97 /// Error treatment: |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
98 /// We swallow the possible GraphError of conditionally_push_parents() to |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
99 /// respect the Iterator trait in a simple manner: never emitting parents |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
100 /// for the returned revision. We finds this good enough for now, because: |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
101 /// |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
102 /// - there's a good chance that invalid revisionss are fed from the start, |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
103 /// and `new()` doesn't swallow the error result. |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
104 /// - this is probably what the Python implementation produces anyway, due |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
105 /// to filtering at each step, and Python code is currently the only |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
106 /// concrete caller we target, so we shouldn't need a finer error treatment |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
107 /// for the time being. |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
108 impl<G: Graph> Iterator for AncestorsIterator<G> { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
109 type Item = Revision; |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
110 |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
111 fn next(&mut self) -> Option<Revision> { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
112 let current = match self.visit.pop() { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
113 None => { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
114 return None; |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
115 } |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
116 Some(i) => i, |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
117 }; |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
118 self.conditionally_push_parents(current).unwrap_or(()); |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
119 Some(current) |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
120 } |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
121 } |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
122 |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
123 #[cfg(test)] |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
124 mod tests { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
125 |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
126 use super::*; |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
127 |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
128 #[derive(Clone, Debug)] |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
129 struct Stub; |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
130 |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
131 /// This is the same as the dict from test-ancestors.py |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
132 impl Graph for Stub { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
133 fn parents( |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
134 &self, |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
135 rev: Revision, |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
136 ) -> Result<(Revision, Revision), GraphError> { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
137 match rev { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
138 0 => Ok((-1, -1)), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
139 1 => Ok((0, -1)), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
140 2 => Ok((1, -1)), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
141 3 => Ok((1, -1)), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
142 4 => Ok((2, -1)), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
143 5 => Ok((4, -1)), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
144 6 => Ok((4, -1)), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
145 7 => Ok((4, -1)), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
146 8 => Ok((-1, -1)), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
147 9 => Ok((6, 7)), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
148 10 => Ok((5, -1)), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
149 11 => Ok((3, 7)), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
150 12 => Ok((9, -1)), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
151 13 => Ok((8, -1)), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
152 r => Err(GraphError::ParentOutOfRange(r)), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
153 } |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
154 } |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
155 } |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
156 |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
157 fn list_ancestors<G: Graph>( |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
158 graph: G, |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
159 initrevs: Vec<Revision>, |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
160 stoprev: Revision, |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
161 inclusive: bool, |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
162 ) -> Vec<Revision> { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
163 AncestorsIterator::new(graph, initrevs, stoprev, inclusive) |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
164 .unwrap() |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
165 .collect() |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
166 } |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
167 |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
168 #[test] |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
169 /// Same tests as test-ancestor.py, without membership |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
170 /// (see also test-ancestor.py.out) |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
171 fn test_list_ancestor() { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
172 assert_eq!(list_ancestors(Stub, vec![], 0, false), vec![]); |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
173 assert_eq!( |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
174 list_ancestors(Stub, vec![11, 13], 0, false), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
175 vec![8, 7, 4, 3, 2, 1, 0] |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
176 ); |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
177 assert_eq!(list_ancestors(Stub, vec![1, 3], 0, false), vec![1, 0]); |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
178 assert_eq!( |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
179 list_ancestors(Stub, vec![11, 13], 0, true), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
180 vec![13, 11, 8, 7, 4, 3, 2, 1, 0] |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
181 ); |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
182 assert_eq!(list_ancestors(Stub, vec![11, 13], 6, false), vec![8, 7]); |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
183 assert_eq!( |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
184 list_ancestors(Stub, vec![11, 13], 6, true), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
185 vec![13, 11, 8, 7] |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
186 ); |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
187 assert_eq!(list_ancestors(Stub, vec![11, 13], 11, true), vec![13, 11]); |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
188 assert_eq!(list_ancestors(Stub, vec![11, 13], 12, true), vec![13]); |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
189 assert_eq!( |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
190 list_ancestors(Stub, vec![10, 1], 0, true), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
191 vec![10, 5, 4, 2, 1, 0] |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
192 ); |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
193 } |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
194 |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
195 #[test] |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
196 /// Corner case that's not directly in test-ancestors.py, but |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
197 /// that happens quite often, as demonstrated by running the whole |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
198 /// suite. |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
199 /// For instance, run tests/test-obsolete-checkheads.t |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
200 fn test_nullrev_input() { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
201 let mut iter = |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
202 AncestorsIterator::new(Stub, vec![-1], 0, false).unwrap(); |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
203 assert_eq!(iter.next(), None) |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
204 } |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
205 |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
206 /// A corrupted Graph, supporting error handling tests |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
207 struct Corrupted; |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
208 |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
209 impl Graph for Corrupted { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
210 fn parents( |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
211 &self, |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
212 rev: Revision, |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
213 ) -> Result<(Revision, Revision), GraphError> { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
214 match rev { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
215 1 => Ok((0, -1)), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
216 r => Err(GraphError::ParentOutOfRange(r)), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
217 } |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
218 } |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
219 } |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
220 |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
221 #[test] |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
222 fn test_initrev_out_of_range() { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
223 // inclusive=false looks up initrev's parents right away |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
224 match AncestorsIterator::new(Stub, vec![25], 0, false) { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
225 Ok(_) => panic!("Should have been ParentOutOfRange"), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
226 Err(e) => assert_eq!(e, GraphError::ParentOutOfRange(25)), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
227 } |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
228 } |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
229 |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
230 #[test] |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
231 fn test_next_out_of_range() { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
232 // inclusive=false looks up initrev's parents right away |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
233 let mut iter = |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
234 AncestorsIterator::new(Corrupted, vec![1], 0, false).unwrap(); |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
235 assert_eq!(iter.next(), Some(0)); |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
236 assert_eq!(iter.next(), None); |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
237 } |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
238 } |