Mercurial > hg
annotate rust/hg-core/src/ancestors.rs @ 40811:e13ab4acf555
rust: peek_mut optim for lazy ancestors
This is one of the two optimizations that are also
present in the Python code: replacing pairs of pop/push
on the BinaryHeap by single updates, hence having it
under the hood maintain its consistency (sift) only once.
On Mozilla central, the measured gain (see details below)
is around 7%.
Creating the PeekMut object by calling peek_mut() right away
instead of peek() first is less efficient (gain is only 4%, stats
not included).
Our interpretation is that its creation has a cost which is vasted
in the cases where it ends by droping the value (Peekmut::pop()
just does self.heap.pop() anyway). On the other hand, the immutable
peek() is very fast: it's just taking a reference in the
underlying vector.
The Python version still has another optimization:
if parent(current) == current-1, then the heap doesn't need
to maintain its consistency, since we already know that
it's bigger than all the others in the heap.
Rust's BinaryHeap doesn't allow us to mutate its biggest
element with no housekeeping, but we tried it anyway, with a
copy of the BinaryHeap implementation with a dedicaded added
method: it's not worth the technical debt in our opinion
(we measured only a further 1.6% improvement).
One possible explanation would be that the sift is really fast
anyway in that case, whereas it's not in the case of Python,
because it's at least partly done in slow Python code.
Still it's possible that replacing BinaryHeap by something more
dedicated to discrete ordered types could be faster.
Measurements on mozilla-central:
Three runs of 'hg perfancestors' on the parent changeset:
Moyenne des médianes: 0.100587
! wall 0.100062 comb 0.100000 user 0.100000 sys 0.000000 (best of 98)
! wall 0.135804 comb 0.130000 user 0.130000 sys 0.000000 (max of 98)
! wall 0.102864 comb 0.102755 user 0.099286 sys 0.003469 (avg of 98)
! wall 0.101486 comb 0.110000 user 0.110000 sys 0.000000 (median of 98)
! wall 0.096804 comb 0.090000 user 0.090000 sys 0.000000 (best of 100)
! wall 0.132235 comb 0.130000 user 0.120000 sys 0.010000 (max of 100)
! wall 0.100258 comb 0.100300 user 0.096000 sys 0.004300 (avg of 100)
! wall 0.098384 comb 0.100000 user 0.100000 sys 0.000000 (median of 100)
! wall 0.099925 comb 0.100000 user 0.100000 sys 0.000000 (best of 98)
! wall 0.133518 comb 0.140000 user 0.130000 sys 0.010000 (max of 98)
! wall 0.102381 comb 0.102449 user 0.098265 sys 0.004184 (avg of 98)
! wall 0.101891 comb 0.090000 user 0.090000 sys 0.000000 (median of 98)
Mean of the medians: 0.100587
On the present changeset:
! wall 0.091344 comb 0.090000 user 0.090000 sys 0.000000 (best of 100)
! wall 0.122728 comb 0.120000 user 0.110000 sys 0.010000 (max of 100)
! wall 0.093268 comb 0.093300 user 0.089300 sys 0.004000 (avg of 100)
! wall 0.092567 comb 0.100000 user 0.090000 sys 0.010000 (median of 100)
! wall 0.093294 comb 0.080000 user 0.080000 sys 0.000000 (best of 100)
! wall 0.144887 comb 0.150000 user 0.140000 sys 0.010000 (max of 100)
! wall 0.097708 comb 0.097700 user 0.093400 sys 0.004300 (avg of 100)
! wall 0.094980 comb 0.100000 user 0.090000 sys 0.010000 (median of 100)
! wall 0.091262 comb 0.090000 user 0.080000 sys 0.010000 (best of 100)
! wall 0.123772 comb 0.130000 user 0.120000 sys 0.010000 (max of 100)
! wall 0.093188 comb 0.093200 user 0.089300 sys 0.003900 (avg of 100)
! wall 0.092364 comb 0.100000 user 0.090000 sys 0.010000 (median of 100)
Mean of the medians is 0.0933
Differential Revision: https://phab.mercurial-scm.org/D5358
author | Georges Racinet <gracinet@anybox.fr> |
---|---|
date | Thu, 29 Nov 2018 09:13:13 +0000 |
parents | 72b94f946e90 |
children | 70976974c14a |
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 { |
40811
e13ab4acf555
rust: peek_mut optim for lazy ancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40300
diff
changeset
|
60 let parents = this.graph.parents(rev)?; |
e13ab4acf555
rust: peek_mut optim for lazy ancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40300
diff
changeset
|
61 this.conditionally_push_rev(parents.0); |
e13ab4acf555
rust: peek_mut optim for lazy ancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40300
diff
changeset
|
62 this.conditionally_push_rev(parents.1); |
40271
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 Ok(this) |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
65 } |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
66 |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
67 #[inline] |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
68 fn conditionally_push_rev(&mut self, rev: Revision) { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
69 if self.stoprev <= rev && !self.seen.contains(&rev) { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
70 self.seen.insert(rev); |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
71 self.visit.push(rev); |
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 } |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
74 |
40300
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
75 /// Consumes partially the iterator to tell if the given target |
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
76 /// revision |
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
77 /// is in the ancestors it emits. |
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
78 /// This is meant for iterators actually dedicated to that kind of |
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
79 /// purpose |
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
80 pub fn contains(&mut self, target: Revision) -> bool { |
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
81 if self.seen.contains(&target) && target != NULL_REVISION { |
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
82 return true; |
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
83 } |
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
84 for rev in self { |
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
85 if rev == target { |
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
86 return true; |
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
87 } |
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
88 if rev < target { |
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
89 return false; |
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
90 } |
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
91 } |
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
92 false |
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
93 } |
40271
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
94 } |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
95 |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
96 /// Main implementation. |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
97 /// |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
98 /// 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
|
99 /// with a few non crucial differences: |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
100 /// |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
101 /// - 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
|
102 /// consistent and more efficient to filter them from the end caller. |
40811
e13ab4acf555
rust: peek_mut optim for lazy ancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40300
diff
changeset
|
103 /// - we don't have the optimization for adjacent revs |
e13ab4acf555
rust: peek_mut optim for lazy ancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40300
diff
changeset
|
104 /// (case where p1 == rev-1), because it amounts to update the first element |
e13ab4acf555
rust: peek_mut optim for lazy ancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40300
diff
changeset
|
105 /// of the heap without sifting, which Rust's BinaryHeap doesn't let us do. |
40271
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
106 /// - 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
|
107 /// |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
108 /// Error treatment: |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
109 /// We swallow the possible GraphError of conditionally_push_parents() to |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
110 /// 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
|
111 /// 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
|
112 /// |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
113 /// - 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
|
114 /// and `new()` doesn't swallow the error result. |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
115 /// - this is probably what the Python implementation produces anyway, due |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
116 /// 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
|
117 /// 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
|
118 /// for the time being. |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
119 impl<G: Graph> Iterator for AncestorsIterator<G> { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
120 type Item = Revision; |
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 fn next(&mut self) -> Option<Revision> { |
40811
e13ab4acf555
rust: peek_mut optim for lazy ancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40300
diff
changeset
|
123 let current = match self.visit.peek() { |
40271
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
124 None => { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
125 return None; |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
126 } |
40811
e13ab4acf555
rust: peek_mut optim for lazy ancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40300
diff
changeset
|
127 Some(c) => *c, |
40271
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
128 }; |
40811
e13ab4acf555
rust: peek_mut optim for lazy ancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40300
diff
changeset
|
129 let parents = self |
e13ab4acf555
rust: peek_mut optim for lazy ancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40300
diff
changeset
|
130 .graph |
e13ab4acf555
rust: peek_mut optim for lazy ancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40300
diff
changeset
|
131 .parents(current) |
e13ab4acf555
rust: peek_mut optim for lazy ancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40300
diff
changeset
|
132 .unwrap_or((NULL_REVISION, NULL_REVISION)); |
e13ab4acf555
rust: peek_mut optim for lazy ancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40300
diff
changeset
|
133 let p1 = parents.0; |
e13ab4acf555
rust: peek_mut optim for lazy ancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40300
diff
changeset
|
134 if p1 < self.stoprev || self.seen.contains(&p1) { |
e13ab4acf555
rust: peek_mut optim for lazy ancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40300
diff
changeset
|
135 self.visit.pop(); |
e13ab4acf555
rust: peek_mut optim for lazy ancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40300
diff
changeset
|
136 } else { |
e13ab4acf555
rust: peek_mut optim for lazy ancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40300
diff
changeset
|
137 *(self.visit.peek_mut().unwrap()) = p1; |
e13ab4acf555
rust: peek_mut optim for lazy ancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40300
diff
changeset
|
138 self.seen.insert(p1); |
e13ab4acf555
rust: peek_mut optim for lazy ancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40300
diff
changeset
|
139 }; |
e13ab4acf555
rust: peek_mut optim for lazy ancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40300
diff
changeset
|
140 |
e13ab4acf555
rust: peek_mut optim for lazy ancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40300
diff
changeset
|
141 self.conditionally_push_rev(parents.1); |
40271
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
142 Some(current) |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
143 } |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
144 } |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
145 |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
146 #[cfg(test)] |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
147 mod tests { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
148 |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
149 use super::*; |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
150 |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
151 #[derive(Clone, Debug)] |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
152 struct Stub; |
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 /// 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
|
155 impl Graph for Stub { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
156 fn parents( |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
157 &self, |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
158 rev: Revision, |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
159 ) -> Result<(Revision, Revision), GraphError> { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
160 match rev { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
161 0 => Ok((-1, -1)), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
162 1 => Ok((0, -1)), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
163 2 => Ok((1, -1)), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
164 3 => Ok((1, -1)), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
165 4 => Ok((2, -1)), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
166 5 => Ok((4, -1)), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
167 6 => Ok((4, -1)), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
168 7 => Ok((4, -1)), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
169 8 => Ok((-1, -1)), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
170 9 => Ok((6, 7)), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
171 10 => Ok((5, -1)), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
172 11 => Ok((3, 7)), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
173 12 => Ok((9, -1)), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
174 13 => Ok((8, -1)), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
175 r => Err(GraphError::ParentOutOfRange(r)), |
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 } |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
178 } |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
179 |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
180 fn list_ancestors<G: Graph>( |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
181 graph: G, |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
182 initrevs: Vec<Revision>, |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
183 stoprev: Revision, |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
184 inclusive: bool, |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
185 ) -> Vec<Revision> { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
186 AncestorsIterator::new(graph, initrevs, stoprev, inclusive) |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
187 .unwrap() |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
188 .collect() |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
189 } |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
190 |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
191 #[test] |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
192 /// Same tests as test-ancestor.py, without membership |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
193 /// (see also test-ancestor.py.out) |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
194 fn test_list_ancestor() { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
195 assert_eq!(list_ancestors(Stub, vec![], 0, false), vec![]); |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
196 assert_eq!( |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
197 list_ancestors(Stub, vec![11, 13], 0, false), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
198 vec![8, 7, 4, 3, 2, 1, 0] |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
199 ); |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
200 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
|
201 assert_eq!( |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
202 list_ancestors(Stub, vec![11, 13], 0, true), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
203 vec![13, 11, 8, 7, 4, 3, 2, 1, 0] |
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 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
|
206 assert_eq!( |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
207 list_ancestors(Stub, vec![11, 13], 6, true), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
208 vec![13, 11, 8, 7] |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
209 ); |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
210 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
|
211 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
|
212 assert_eq!( |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
213 list_ancestors(Stub, vec![10, 1], 0, true), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
214 vec![10, 5, 4, 2, 1, 0] |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
215 ); |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
216 } |
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 #[test] |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
219 /// 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
|
220 /// that happens quite often, as demonstrated by running the whole |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
221 /// suite. |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
222 /// For instance, run tests/test-obsolete-checkheads.t |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
223 fn test_nullrev_input() { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
224 let mut iter = |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
225 AncestorsIterator::new(Stub, vec![-1], 0, false).unwrap(); |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
226 assert_eq!(iter.next(), None) |
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 |
40300
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
229 #[test] |
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
230 fn test_contains() { |
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
231 let mut lazy = |
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
232 AncestorsIterator::new(Stub, vec![10, 1], 0, true).unwrap(); |
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
233 assert!(lazy.contains(1)); |
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
234 assert!(!lazy.contains(3)); |
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
235 |
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
236 let mut lazy = |
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
237 AncestorsIterator::new(Stub, vec![0], 0, false).unwrap(); |
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
238 assert!(!lazy.contains(NULL_REVISION)); |
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
239 } |
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
240 |
40271
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
241 /// A corrupted Graph, supporting error handling tests |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
242 struct Corrupted; |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
243 |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
244 impl Graph for Corrupted { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
245 fn parents( |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
246 &self, |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
247 rev: Revision, |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
248 ) -> Result<(Revision, Revision), GraphError> { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
249 match rev { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
250 1 => Ok((0, -1)), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
251 r => Err(GraphError::ParentOutOfRange(r)), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
252 } |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
253 } |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
254 } |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
255 |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
256 #[test] |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
257 fn test_initrev_out_of_range() { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
258 // inclusive=false looks up initrev's parents right away |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
259 match AncestorsIterator::new(Stub, vec![25], 0, false) { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
260 Ok(_) => panic!("Should have been ParentOutOfRange"), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
261 Err(e) => assert_eq!(e, GraphError::ParentOutOfRange(25)), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
262 } |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
263 } |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
264 |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
265 #[test] |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
266 fn test_next_out_of_range() { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
267 // inclusive=false looks up initrev's parents right away |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
268 let mut iter = |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
269 AncestorsIterator::new(Corrupted, vec![1], 0, false).unwrap(); |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
270 assert_eq!(iter.next(), Some(0)); |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
271 assert_eq!(iter.next(), None); |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
272 } |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
273 } |