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
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
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 }