Mercurial > hg
annotate rust/hg-core/src/ancestors.rs @ 41246:619ee4039bd4
rust: MissingAncestors.basesheads()
This new API method on `MissingAncestors` leverages directly the
Rust implementation for relative heads of a set, and also
lowers the cost of returning the results to Python in the context of
discovery.
These interchange costs can probably be further reduced by implementing
the `partialdiscovery` class in Rust, but that will be investigated in the
5.0 development cycle.
Differential Revision: https://phab.mercurial-scm.org/D5584
author | Georges Racinet <georges.racinet@octobus.net> |
---|---|
date | Mon, 14 Jan 2019 17:07:39 +0100 |
parents | 168041fa6d5f |
children | 70827ebba453 |
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}; |
40959
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
11 use std::cmp::max; |
40271
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
12 use std::collections::{BinaryHeap, HashSet}; |
41246
619ee4039bd4
rust: MissingAncestors.basesheads()
Georges Racinet <georges.racinet@octobus.net>
parents:
41241
diff
changeset
|
13 use crate::dagops; |
40271
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
14 |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
15 /// Iterator over the ancestors of a given list of revisions |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
16 /// 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
|
17 /// it's easy to |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
18 /// |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
19 /// - unit test in pure Rust |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
20 /// - 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
|
21 /// bindings evolve over time |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
22 pub struct AncestorsIterator<G: Graph> { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
23 graph: G, |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
24 visit: BinaryHeap<Revision>, |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
25 seen: HashSet<Revision>, |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
26 stoprev: Revision, |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
27 } |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
28 |
41054
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
29 /// Lazy ancestors set, backed by AncestorsIterator |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
30 pub struct LazyAncestors<G: Graph + Clone> { |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
31 graph: G, |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
32 containsiter: AncestorsIterator<G>, |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
33 initrevs: Vec<Revision>, |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
34 stoprev: Revision, |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
35 inclusive: bool, |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
36 } |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
37 |
40959
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
38 pub struct MissingAncestors<G: Graph> { |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
39 graph: G, |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
40 bases: HashSet<Revision>, |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
41 } |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
42 |
40271
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
43 impl<G: Graph> AncestorsIterator<G> { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
44 /// Constructor. |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
45 /// |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
46 /// 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
|
47 /// particular, otherwise iteration starts from their parents. |
41105
35ee590b1892
rust: use 'impl Trait' in method argument of AncestorsIterator
Yuya Nishihara <yuya@tcha.org>
parents:
41104
diff
changeset
|
48 pub fn new( |
40271
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
49 graph: G, |
41105
35ee590b1892
rust: use 'impl Trait' in method argument of AncestorsIterator
Yuya Nishihara <yuya@tcha.org>
parents:
41104
diff
changeset
|
50 initrevs: impl IntoIterator<Item = Revision>, |
40271
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
51 stoprev: Revision, |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
52 inclusive: bool, |
41105
35ee590b1892
rust: use 'impl Trait' in method argument of AncestorsIterator
Yuya Nishihara <yuya@tcha.org>
parents:
41104
diff
changeset
|
53 ) -> Result<Self, GraphError> { |
40271
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
54 let filtered_initrevs = initrevs.into_iter().filter(|&r| r >= stoprev); |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
55 if inclusive { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
56 let visit: BinaryHeap<Revision> = filtered_initrevs.collect(); |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
57 let seen = visit.iter().map(|&x| x).collect(); |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
58 return Ok(AncestorsIterator { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
59 visit: visit, |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
60 seen: seen, |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
61 stoprev: stoprev, |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
62 graph: graph, |
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 let mut this = AncestorsIterator { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
66 visit: BinaryHeap::new(), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
67 seen: HashSet::new(), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
68 stoprev: stoprev, |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
69 graph: graph, |
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 this.seen.insert(NULL_REVISION); |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
72 for rev in filtered_initrevs { |
40933
18513d6ef7d4
rust: changed Graph.parents to return [Revision; 2]
Georges Racinet <gracinet@anybox.fr>
parents:
40932
diff
changeset
|
73 for parent in this.graph.parents(rev)?.iter().cloned() { |
18513d6ef7d4
rust: changed Graph.parents to return [Revision; 2]
Georges Racinet <gracinet@anybox.fr>
parents:
40932
diff
changeset
|
74 this.conditionally_push_rev(parent); |
18513d6ef7d4
rust: changed Graph.parents to return [Revision; 2]
Georges Racinet <gracinet@anybox.fr>
parents:
40932
diff
changeset
|
75 } |
40271
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
76 } |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
77 Ok(this) |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
78 } |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
79 |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
80 #[inline] |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
81 fn conditionally_push_rev(&mut self, rev: Revision) { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
82 if self.stoprev <= rev && !self.seen.contains(&rev) { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
83 self.seen.insert(rev); |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
84 self.visit.push(rev); |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
85 } |
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 |
40300
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
88 /// Consumes partially the iterator to tell if the given target |
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
89 /// revision |
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
90 /// is in the ancestors it emits. |
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
91 /// This is meant for iterators actually dedicated to that kind of |
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
92 /// purpose |
40863
443eb4bc41af
rust: propagate error of index_get_parents() properly
Yuya Nishihara <yuya@tcha.org>
parents:
40832
diff
changeset
|
93 pub fn contains(&mut self, target: Revision) -> Result<bool, GraphError> { |
40300
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
94 if self.seen.contains(&target) && target != NULL_REVISION { |
40863
443eb4bc41af
rust: propagate error of index_get_parents() properly
Yuya Nishihara <yuya@tcha.org>
parents:
40832
diff
changeset
|
95 return Ok(true); |
40300
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
96 } |
40863
443eb4bc41af
rust: propagate error of index_get_parents() properly
Yuya Nishihara <yuya@tcha.org>
parents:
40832
diff
changeset
|
97 for item in self { |
443eb4bc41af
rust: propagate error of index_get_parents() properly
Yuya Nishihara <yuya@tcha.org>
parents:
40832
diff
changeset
|
98 let rev = item?; |
40300
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
99 if rev == target { |
40863
443eb4bc41af
rust: propagate error of index_get_parents() properly
Yuya Nishihara <yuya@tcha.org>
parents:
40832
diff
changeset
|
100 return Ok(true); |
40300
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
101 } |
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
102 if rev < target { |
40863
443eb4bc41af
rust: propagate error of index_get_parents() properly
Yuya Nishihara <yuya@tcha.org>
parents:
40832
diff
changeset
|
103 return Ok(false); |
40300
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
104 } |
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
105 } |
40863
443eb4bc41af
rust: propagate error of index_get_parents() properly
Yuya Nishihara <yuya@tcha.org>
parents:
40832
diff
changeset
|
106 Ok(false) |
40300
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
107 } |
41054
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
108 |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
109 pub fn peek(&self) -> Option<Revision> { |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
110 self.visit.peek().map(|&r| r) |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
111 } |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
112 |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
113 /// Tell if the iterator is about an empty set |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
114 /// |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
115 /// The result does not depend whether the iterator has been consumed |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
116 /// or not. |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
117 /// This is mostly meant for iterators backing a lazy ancestors set |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
118 pub fn is_empty(&self) -> bool { |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
119 if self.visit.len() > 0 { |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
120 return false; |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
121 } |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
122 if self.seen.len() > 1 { |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
123 return false; |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
124 } |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
125 // at this point, the seen set is at most a singleton. |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
126 // If not `self.inclusive`, it's still possible that it has only |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
127 // the null revision |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
128 self.seen.is_empty() || self.seen.contains(&NULL_REVISION) |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
129 } |
40271
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 |
41054
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
132 /// Main implementation for the iterator |
40271
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
133 /// |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
134 /// 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
|
135 /// with a few non crucial differences: |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
136 /// |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
137 /// - 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
|
138 /// consistent and more efficient to filter them from the end caller. |
40932
dc38d976ff4d
rust: improved docstring
Georges Racinet <gracinet@anybox.fr>
parents:
40929
diff
changeset
|
139 /// - we don't have the optimization for adjacent revisions (i.e., the case |
dc38d976ff4d
rust: improved docstring
Georges Racinet <gracinet@anybox.fr>
parents:
40929
diff
changeset
|
140 /// where `p1 == rev - 1`), because it amounts to update the first element of |
dc38d976ff4d
rust: improved docstring
Georges Racinet <gracinet@anybox.fr>
parents:
40929
diff
changeset
|
141 /// 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
|
142 /// - 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
|
143 impl<G: Graph> Iterator for AncestorsIterator<G> { |
40863
443eb4bc41af
rust: propagate error of index_get_parents() properly
Yuya Nishihara <yuya@tcha.org>
parents:
40832
diff
changeset
|
144 type Item = Result<Revision, GraphError>; |
40271
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
145 |
40863
443eb4bc41af
rust: propagate error of index_get_parents() properly
Yuya Nishihara <yuya@tcha.org>
parents:
40832
diff
changeset
|
146 fn next(&mut self) -> Option<Self::Item> { |
40811
e13ab4acf555
rust: peek_mut optim for lazy ancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40300
diff
changeset
|
147 let current = match self.visit.peek() { |
40271
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
148 None => { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
149 return None; |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
150 } |
40811
e13ab4acf555
rust: peek_mut optim for lazy ancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40300
diff
changeset
|
151 Some(c) => *c, |
40271
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
152 }; |
40933
18513d6ef7d4
rust: changed Graph.parents to return [Revision; 2]
Georges Racinet <gracinet@anybox.fr>
parents:
40932
diff
changeset
|
153 let [p1, p2] = match self.graph.parents(current) { |
40863
443eb4bc41af
rust: propagate error of index_get_parents() properly
Yuya Nishihara <yuya@tcha.org>
parents:
40832
diff
changeset
|
154 Ok(ps) => ps, |
443eb4bc41af
rust: propagate error of index_get_parents() properly
Yuya Nishihara <yuya@tcha.org>
parents:
40832
diff
changeset
|
155 Err(e) => return Some(Err(e)), |
443eb4bc41af
rust: propagate error of index_get_parents() properly
Yuya Nishihara <yuya@tcha.org>
parents:
40832
diff
changeset
|
156 }; |
40811
e13ab4acf555
rust: peek_mut optim for lazy ancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40300
diff
changeset
|
157 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
|
158 self.visit.pop(); |
e13ab4acf555
rust: peek_mut optim for lazy ancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40300
diff
changeset
|
159 } else { |
e13ab4acf555
rust: peek_mut optim for lazy ancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40300
diff
changeset
|
160 *(self.visit.peek_mut().unwrap()) = p1; |
e13ab4acf555
rust: peek_mut optim for lazy ancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40300
diff
changeset
|
161 self.seen.insert(p1); |
e13ab4acf555
rust: peek_mut optim for lazy ancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40300
diff
changeset
|
162 }; |
e13ab4acf555
rust: peek_mut optim for lazy ancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40300
diff
changeset
|
163 |
40832
70976974c14a
rust: rename local variables in AncestorsIterator::next
Georges Racinet <georges@racinet.fr>
parents:
40811
diff
changeset
|
164 self.conditionally_push_rev(p2); |
40863
443eb4bc41af
rust: propagate error of index_get_parents() properly
Yuya Nishihara <yuya@tcha.org>
parents:
40832
diff
changeset
|
165 Some(Ok(current)) |
40271
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 |
41054
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
169 impl<G: Graph + Clone> LazyAncestors<G> { |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
170 pub fn new( |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
171 graph: G, |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
172 initrevs: impl IntoIterator<Item = Revision>, |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
173 stoprev: Revision, |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
174 inclusive: bool, |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
175 ) -> Result<Self, GraphError> { |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
176 let v: Vec<Revision> = initrevs.into_iter().collect(); |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
177 Ok(LazyAncestors { |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
178 graph: graph.clone(), |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
179 containsiter: AncestorsIterator::new( |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
180 graph, |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
181 v.iter().cloned(), |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
182 stoprev, |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
183 inclusive, |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
184 )?, |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
185 initrevs: v, |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
186 stoprev: stoprev, |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
187 inclusive: inclusive, |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
188 }) |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
189 } |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
190 |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
191 pub fn contains(&mut self, rev: Revision) -> Result<bool, GraphError> { |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
192 self.containsiter.contains(rev) |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
193 } |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
194 |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
195 pub fn is_empty(&self) -> bool { |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
196 self.containsiter.is_empty() |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
197 } |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
198 |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
199 pub fn iter(&self) -> AncestorsIterator<G> { |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
200 // the arguments being the same as for self.containsiter, we know |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
201 // for sure that AncestorsIterator constructor can't fail |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
202 AncestorsIterator::new( |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
203 self.graph.clone(), |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
204 self.initrevs.iter().cloned(), |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
205 self.stoprev, |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
206 self.inclusive, |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
207 ) |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
208 .unwrap() |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
209 } |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
210 } |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
211 |
40959
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
212 impl<G: Graph> MissingAncestors<G> { |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
213 pub fn new(graph: G, bases: impl IntoIterator<Item = Revision>) -> Self { |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
214 let mut bases: HashSet<Revision> = bases.into_iter().collect(); |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
215 if bases.is_empty() { |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
216 bases.insert(NULL_REVISION); |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
217 } |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
218 MissingAncestors { graph, bases } |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
219 } |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
220 |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
221 pub fn has_bases(&self) -> bool { |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
222 self.bases.iter().any(|&b| b != NULL_REVISION) |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
223 } |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
224 |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
225 /// Return a reference to current bases. |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
226 /// |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
227 /// This is useful in unit tests, but also setdiscovery.py does |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
228 /// read the bases attribute of a ancestor.missingancestors instance. |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
229 pub fn get_bases<'a>(&'a self) -> &'a HashSet<Revision> { |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
230 &self.bases |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
231 } |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
232 |
41246
619ee4039bd4
rust: MissingAncestors.basesheads()
Georges Racinet <georges.racinet@octobus.net>
parents:
41241
diff
changeset
|
233 /// Computes the relative heads of current bases. |
619ee4039bd4
rust: MissingAncestors.basesheads()
Georges Racinet <georges.racinet@octobus.net>
parents:
41241
diff
changeset
|
234 /// |
619ee4039bd4
rust: MissingAncestors.basesheads()
Georges Racinet <georges.racinet@octobus.net>
parents:
41241
diff
changeset
|
235 /// The object is still usable after this. |
619ee4039bd4
rust: MissingAncestors.basesheads()
Georges Racinet <georges.racinet@octobus.net>
parents:
41241
diff
changeset
|
236 pub fn bases_heads(&self) -> Result<HashSet<Revision>, GraphError> { |
619ee4039bd4
rust: MissingAncestors.basesheads()
Georges Racinet <georges.racinet@octobus.net>
parents:
41241
diff
changeset
|
237 dagops::heads(&self.graph, self.bases.iter()) |
619ee4039bd4
rust: MissingAncestors.basesheads()
Georges Racinet <georges.racinet@octobus.net>
parents:
41241
diff
changeset
|
238 } |
619ee4039bd4
rust: MissingAncestors.basesheads()
Georges Racinet <georges.racinet@octobus.net>
parents:
41241
diff
changeset
|
239 |
619ee4039bd4
rust: MissingAncestors.basesheads()
Georges Racinet <georges.racinet@octobus.net>
parents:
41241
diff
changeset
|
240 /// Consumes the object and returns the relative heads of its bases. |
619ee4039bd4
rust: MissingAncestors.basesheads()
Georges Racinet <georges.racinet@octobus.net>
parents:
41241
diff
changeset
|
241 pub fn into_bases_heads(mut self) -> Result<HashSet<Revision>, GraphError> { |
619ee4039bd4
rust: MissingAncestors.basesheads()
Georges Racinet <georges.racinet@octobus.net>
parents:
41241
diff
changeset
|
242 dagops::retain_heads(&self.graph, &mut self.bases)?; |
619ee4039bd4
rust: MissingAncestors.basesheads()
Georges Racinet <georges.racinet@octobus.net>
parents:
41241
diff
changeset
|
243 Ok(self.bases) |
619ee4039bd4
rust: MissingAncestors.basesheads()
Georges Racinet <georges.racinet@octobus.net>
parents:
41241
diff
changeset
|
244 } |
619ee4039bd4
rust: MissingAncestors.basesheads()
Georges Racinet <georges.racinet@octobus.net>
parents:
41241
diff
changeset
|
245 |
40959
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
246 pub fn add_bases( |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
247 &mut self, |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
248 new_bases: impl IntoIterator<Item = Revision>, |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
249 ) { |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
250 self.bases.extend(new_bases); |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
251 } |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
252 |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
253 /// Remove all ancestors of self.bases from the revs set (in place) |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
254 pub fn remove_ancestors_from( |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
255 &mut self, |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
256 revs: &mut HashSet<Revision>, |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
257 ) -> Result<(), GraphError> { |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
258 revs.retain(|r| !self.bases.contains(r)); |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
259 // the null revision is always an ancestor |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
260 revs.remove(&NULL_REVISION); |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
261 if revs.is_empty() { |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
262 return Ok(()); |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
263 } |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
264 // anything in revs > start is definitely not an ancestor of bases |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
265 // revs <= start need to be investigated |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
266 // TODO optim: if a missingancestors is to be used several times, |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
267 // we shouldn't need to iterate each time on bases |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
268 let start = match self.bases.iter().cloned().max() { |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
269 Some(m) => m, |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
270 None => { |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
271 // bases is empty (shouldn't happen, but let's be safe) |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
272 return Ok(()); |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
273 } |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
274 }; |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
275 // whatever happens, we'll keep at least keepcount of them |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
276 // knowing this gives us a earlier stop condition than |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
277 // going all the way to the root |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
278 let keepcount = revs.iter().filter(|r| **r > start).count(); |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
279 |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
280 let mut curr = start; |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
281 while curr != NULL_REVISION && revs.len() > keepcount { |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
282 if self.bases.contains(&curr) { |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
283 revs.remove(&curr); |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
284 self.add_parents(curr)?; |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
285 } |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
286 curr -= 1; |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
287 } |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
288 Ok(()) |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
289 } |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
290 |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
291 /// Add rev's parents to self.bases |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
292 #[inline] |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
293 fn add_parents(&mut self, rev: Revision) -> Result<(), GraphError> { |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
294 // No need to bother the set with inserting NULL_REVISION over and |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
295 // over |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
296 for p in self.graph.parents(rev)?.iter().cloned() { |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
297 if p != NULL_REVISION { |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
298 self.bases.insert(p); |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
299 } |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
300 } |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
301 Ok(()) |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
302 } |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
303 |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
304 /// Return all the ancestors of revs that are not ancestors of self.bases |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
305 /// |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
306 /// This may include elements from revs. |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
307 /// |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
308 /// Equivalent to the revset (::revs - ::self.bases). Revs are returned in |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
309 /// revision number order, which is a topological order. |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
310 pub fn missing_ancestors( |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
311 &mut self, |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
312 revs: impl IntoIterator<Item = Revision>, |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
313 ) -> Result<Vec<Revision>, GraphError> { |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
314 // just for convenience and comparison with Python version |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
315 let bases_visit = &mut self.bases; |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
316 let mut revs: HashSet<Revision> = revs |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
317 .into_iter() |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
318 .filter(|r| !bases_visit.contains(r)) |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
319 .collect(); |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
320 let revs_visit = &mut revs; |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
321 let mut both_visit: HashSet<Revision> = |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
322 revs_visit.intersection(&bases_visit).cloned().collect(); |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
323 if revs_visit.is_empty() { |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
324 return Ok(Vec::new()); |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
325 } |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
326 |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
327 let max_bases = |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
328 bases_visit.iter().cloned().max().unwrap_or(NULL_REVISION); |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
329 let max_revs = |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
330 revs_visit.iter().cloned().max().unwrap_or(NULL_REVISION); |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
331 let start = max(max_bases, max_revs); |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
332 |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
333 // TODO heuristics for with_capacity()? |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
334 let mut missing: Vec<Revision> = Vec::new(); |
41104
247f51cfc668
rust: use .rev() for reverse range
Yuya Nishihara <yuya@tcha.org>
parents:
41054
diff
changeset
|
335 for curr in (0..=start).rev() { |
40959
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
336 if revs_visit.is_empty() { |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
337 break; |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
338 } |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
339 if both_visit.contains(&curr) { |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
340 // curr's parents might have made it into revs_visit through |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
341 // another path |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
342 // TODO optim: Rust's HashSet.remove returns a boolean telling |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
343 // if it happened. This will spare us one set lookup |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
344 both_visit.remove(&curr); |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
345 for p in self.graph.parents(curr)?.iter().cloned() { |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
346 if p == NULL_REVISION { |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
347 continue; |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
348 } |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
349 revs_visit.remove(&p); |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
350 bases_visit.insert(p); |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
351 both_visit.insert(p); |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
352 } |
41134
17a195676472
rust-ancestors: adjust branches and inline comments per previous change
Yuya Nishihara <yuya@tcha.org>
parents:
41133
diff
changeset
|
353 } else if revs_visit.remove(&curr) { |
41131
486908e691be
rust-ancestors: adjust indent level to make next change easier to follow
Yuya Nishihara <yuya@tcha.org>
parents:
41105
diff
changeset
|
354 missing.push(curr); |
486908e691be
rust-ancestors: adjust indent level to make next change easier to follow
Yuya Nishihara <yuya@tcha.org>
parents:
41105
diff
changeset
|
355 for p in self.graph.parents(curr)?.iter().cloned() { |
486908e691be
rust-ancestors: adjust indent level to make next change easier to follow
Yuya Nishihara <yuya@tcha.org>
parents:
41105
diff
changeset
|
356 if p == NULL_REVISION { |
486908e691be
rust-ancestors: adjust indent level to make next change easier to follow
Yuya Nishihara <yuya@tcha.org>
parents:
41105
diff
changeset
|
357 continue; |
486908e691be
rust-ancestors: adjust indent level to make next change easier to follow
Yuya Nishihara <yuya@tcha.org>
parents:
41105
diff
changeset
|
358 } |
41133
a1b3800c8a19
rust-ancestors: remove unreachable conditions from missing_ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
41132
diff
changeset
|
359 if bases_visit.contains(&p) || both_visit.contains(&p) { |
41134
17a195676472
rust-ancestors: adjust branches and inline comments per previous change
Yuya Nishihara <yuya@tcha.org>
parents:
41133
diff
changeset
|
360 // p is an ancestor of revs_visit, and is implicitly |
17a195676472
rust-ancestors: adjust branches and inline comments per previous change
Yuya Nishihara <yuya@tcha.org>
parents:
41133
diff
changeset
|
361 // in bases_visit, which means p is ::revs & ::bases. |
41131
486908e691be
rust-ancestors: adjust indent level to make next change easier to follow
Yuya Nishihara <yuya@tcha.org>
parents:
41105
diff
changeset
|
362 // TODO optim: hence if bothvisit, we look up twice |
486908e691be
rust-ancestors: adjust indent level to make next change easier to follow
Yuya Nishihara <yuya@tcha.org>
parents:
41105
diff
changeset
|
363 revs_visit.remove(&p); |
40959
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
364 bases_visit.insert(p); |
41131
486908e691be
rust-ancestors: adjust indent level to make next change easier to follow
Yuya Nishihara <yuya@tcha.org>
parents:
41105
diff
changeset
|
365 both_visit.insert(p); |
486908e691be
rust-ancestors: adjust indent level to make next change easier to follow
Yuya Nishihara <yuya@tcha.org>
parents:
41105
diff
changeset
|
366 } else { |
486908e691be
rust-ancestors: adjust indent level to make next change easier to follow
Yuya Nishihara <yuya@tcha.org>
parents:
41105
diff
changeset
|
367 // visit later |
41133
a1b3800c8a19
rust-ancestors: remove unreachable conditions from missing_ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
41132
diff
changeset
|
368 revs_visit.insert(p); |
40959
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
369 } |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
370 } |
41132
55dc1da8df2f
rust-ancestors: duplicate loop that visits parents of revs/bases
Yuya Nishihara <yuya@tcha.org>
parents:
41131
diff
changeset
|
371 } else if bases_visit.contains(&curr) { |
55dc1da8df2f
rust-ancestors: duplicate loop that visits parents of revs/bases
Yuya Nishihara <yuya@tcha.org>
parents:
41131
diff
changeset
|
372 for p in self.graph.parents(curr)?.iter().cloned() { |
55dc1da8df2f
rust-ancestors: duplicate loop that visits parents of revs/bases
Yuya Nishihara <yuya@tcha.org>
parents:
41131
diff
changeset
|
373 if p == NULL_REVISION { |
55dc1da8df2f
rust-ancestors: duplicate loop that visits parents of revs/bases
Yuya Nishihara <yuya@tcha.org>
parents:
41131
diff
changeset
|
374 continue; |
55dc1da8df2f
rust-ancestors: duplicate loop that visits parents of revs/bases
Yuya Nishihara <yuya@tcha.org>
parents:
41131
diff
changeset
|
375 } |
41133
a1b3800c8a19
rust-ancestors: remove unreachable conditions from missing_ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
41132
diff
changeset
|
376 if revs_visit.contains(&p) || both_visit.contains(&p) { |
41134
17a195676472
rust-ancestors: adjust branches and inline comments per previous change
Yuya Nishihara <yuya@tcha.org>
parents:
41133
diff
changeset
|
377 // p is an ancestor of bases_visit, and is implicitly |
17a195676472
rust-ancestors: adjust branches and inline comments per previous change
Yuya Nishihara <yuya@tcha.org>
parents:
41133
diff
changeset
|
378 // in revs_visit, which means p is ::revs & ::bases. |
41132
55dc1da8df2f
rust-ancestors: duplicate loop that visits parents of revs/bases
Yuya Nishihara <yuya@tcha.org>
parents:
41131
diff
changeset
|
379 // TODO optim: hence if bothvisit, we look up twice |
55dc1da8df2f
rust-ancestors: duplicate loop that visits parents of revs/bases
Yuya Nishihara <yuya@tcha.org>
parents:
41131
diff
changeset
|
380 revs_visit.remove(&p); |
55dc1da8df2f
rust-ancestors: duplicate loop that visits parents of revs/bases
Yuya Nishihara <yuya@tcha.org>
parents:
41131
diff
changeset
|
381 bases_visit.insert(p); |
55dc1da8df2f
rust-ancestors: duplicate loop that visits parents of revs/bases
Yuya Nishihara <yuya@tcha.org>
parents:
41131
diff
changeset
|
382 both_visit.insert(p); |
55dc1da8df2f
rust-ancestors: duplicate loop that visits parents of revs/bases
Yuya Nishihara <yuya@tcha.org>
parents:
41131
diff
changeset
|
383 } else { |
41133
a1b3800c8a19
rust-ancestors: remove unreachable conditions from missing_ancestors()
Yuya Nishihara <yuya@tcha.org>
parents:
41132
diff
changeset
|
384 bases_visit.insert(p); |
41132
55dc1da8df2f
rust-ancestors: duplicate loop that visits parents of revs/bases
Yuya Nishihara <yuya@tcha.org>
parents:
41131
diff
changeset
|
385 } |
55dc1da8df2f
rust-ancestors: duplicate loop that visits parents of revs/bases
Yuya Nishihara <yuya@tcha.org>
parents:
41131
diff
changeset
|
386 } |
40959
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
387 } |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
388 } |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
389 missing.reverse(); |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
390 Ok(missing) |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
391 } |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
392 } |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
393 |
40271
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
394 #[cfg(test)] |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
395 mod tests { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
396 |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
397 use super::*; |
41241
168041fa6d5f
rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents:
41134
diff
changeset
|
398 use crate::testing::{SampleGraph, VecGraph}; |
40959
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
399 use std::iter::FromIterator; |
40271
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
400 |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
401 fn list_ancestors<G: Graph>( |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
402 graph: G, |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
403 initrevs: Vec<Revision>, |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
404 stoprev: Revision, |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
405 inclusive: bool, |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
406 ) -> Vec<Revision> { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
407 AncestorsIterator::new(graph, initrevs, stoprev, inclusive) |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
408 .unwrap() |
40929
43ca24b772d6
rust: adapted hg-core tests for iteration over Result
Georges Racinet <gracinet@anybox.fr>
parents:
40927
diff
changeset
|
409 .map(|res| res.unwrap()) |
40271
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
410 .collect() |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
411 } |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
412 |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
413 #[test] |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
414 /// Same tests as test-ancestor.py, without membership |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
415 /// (see also test-ancestor.py.out) |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
416 fn test_list_ancestor() { |
41241
168041fa6d5f
rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents:
41134
diff
changeset
|
417 assert_eq!(list_ancestors(SampleGraph, vec![], 0, false), vec![]); |
40271
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
418 assert_eq!( |
41241
168041fa6d5f
rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents:
41134
diff
changeset
|
419 list_ancestors(SampleGraph, vec![11, 13], 0, false), |
40271
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
420 vec![8, 7, 4, 3, 2, 1, 0] |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
421 ); |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
422 assert_eq!( |
41241
168041fa6d5f
rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents:
41134
diff
changeset
|
423 list_ancestors(SampleGraph, vec![1, 3], 0, false), |
168041fa6d5f
rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents:
41134
diff
changeset
|
424 vec![1, 0] |
168041fa6d5f
rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents:
41134
diff
changeset
|
425 ); |
168041fa6d5f
rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents:
41134
diff
changeset
|
426 assert_eq!( |
168041fa6d5f
rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents:
41134
diff
changeset
|
427 list_ancestors(SampleGraph, vec![11, 13], 0, true), |
40271
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
428 vec![13, 11, 8, 7, 4, 3, 2, 1, 0] |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
429 ); |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
430 assert_eq!( |
41241
168041fa6d5f
rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents:
41134
diff
changeset
|
431 list_ancestors(SampleGraph, vec![11, 13], 6, false), |
168041fa6d5f
rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents:
41134
diff
changeset
|
432 vec![8, 7] |
168041fa6d5f
rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents:
41134
diff
changeset
|
433 ); |
168041fa6d5f
rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents:
41134
diff
changeset
|
434 assert_eq!( |
168041fa6d5f
rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents:
41134
diff
changeset
|
435 list_ancestors(SampleGraph, vec![11, 13], 6, true), |
40271
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
436 vec![13, 11, 8, 7] |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
437 ); |
41241
168041fa6d5f
rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents:
41134
diff
changeset
|
438 assert_eq!( |
168041fa6d5f
rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents:
41134
diff
changeset
|
439 list_ancestors(SampleGraph, vec![11, 13], 11, true), |
168041fa6d5f
rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents:
41134
diff
changeset
|
440 vec![13, 11] |
168041fa6d5f
rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents:
41134
diff
changeset
|
441 ); |
40271
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
442 assert_eq!( |
41241
168041fa6d5f
rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents:
41134
diff
changeset
|
443 list_ancestors(SampleGraph, vec![11, 13], 12, true), |
168041fa6d5f
rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents:
41134
diff
changeset
|
444 vec![13] |
168041fa6d5f
rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents:
41134
diff
changeset
|
445 ); |
168041fa6d5f
rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents:
41134
diff
changeset
|
446 assert_eq!( |
168041fa6d5f
rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents:
41134
diff
changeset
|
447 list_ancestors(SampleGraph, vec![10, 1], 0, true), |
40271
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
448 vec![10, 5, 4, 2, 1, 0] |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
449 ); |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
450 } |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
451 |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
452 #[test] |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
453 /// 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
|
454 /// that happens quite often, as demonstrated by running the whole |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
455 /// suite. |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
456 /// For instance, run tests/test-obsolete-checkheads.t |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
457 fn test_nullrev_input() { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
458 let mut iter = |
41241
168041fa6d5f
rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents:
41134
diff
changeset
|
459 AncestorsIterator::new(SampleGraph, vec![-1], 0, false).unwrap(); |
40271
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
460 assert_eq!(iter.next(), None) |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
461 } |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
462 |
40300
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
463 #[test] |
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
464 fn test_contains() { |
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
465 let mut lazy = |
41241
168041fa6d5f
rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents:
41134
diff
changeset
|
466 AncestorsIterator::new(SampleGraph, vec![10, 1], 0, true).unwrap(); |
40929
43ca24b772d6
rust: adapted hg-core tests for iteration over Result
Georges Racinet <gracinet@anybox.fr>
parents:
40927
diff
changeset
|
467 assert!(lazy.contains(1).unwrap()); |
43ca24b772d6
rust: adapted hg-core tests for iteration over Result
Georges Racinet <gracinet@anybox.fr>
parents:
40927
diff
changeset
|
468 assert!(!lazy.contains(3).unwrap()); |
40300
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
469 |
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
470 let mut lazy = |
41241
168041fa6d5f
rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents:
41134
diff
changeset
|
471 AncestorsIterator::new(SampleGraph, vec![0], 0, false).unwrap(); |
40929
43ca24b772d6
rust: adapted hg-core tests for iteration over Result
Georges Racinet <gracinet@anybox.fr>
parents:
40927
diff
changeset
|
472 assert!(!lazy.contains(NULL_REVISION).unwrap()); |
40300
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
473 } |
72b94f946e90
rust: rustlazyancestors.__contains__
Georges Racinet <gracinet@anybox.fr>
parents:
40271
diff
changeset
|
474 |
41054
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
475 #[test] |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
476 fn test_peek() { |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
477 let mut iter = |
41241
168041fa6d5f
rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents:
41134
diff
changeset
|
478 AncestorsIterator::new(SampleGraph, vec![10], 0, true).unwrap(); |
41054
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
479 // peek() gives us the next value |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
480 assert_eq!(iter.peek(), Some(10)); |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
481 // but it's not been consumed |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
482 assert_eq!(iter.next(), Some(Ok(10))); |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
483 // and iteration resumes normally |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
484 assert_eq!(iter.next(), Some(Ok(5))); |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
485 |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
486 // let's drain the iterator to test peek() at the end |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
487 while iter.next().is_some() {} |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
488 assert_eq!(iter.peek(), None); |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
489 } |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
490 |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
491 #[test] |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
492 fn test_empty() { |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
493 let mut iter = |
41241
168041fa6d5f
rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents:
41134
diff
changeset
|
494 AncestorsIterator::new(SampleGraph, vec![10], 0, true).unwrap(); |
41054
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
495 assert!(!iter.is_empty()); |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
496 while iter.next().is_some() {} |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
497 assert!(!iter.is_empty()); |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
498 |
41241
168041fa6d5f
rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents:
41134
diff
changeset
|
499 let iter = |
168041fa6d5f
rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents:
41134
diff
changeset
|
500 AncestorsIterator::new(SampleGraph, vec![], 0, true).unwrap(); |
41054
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
501 assert!(iter.is_empty()); |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
502 |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
503 // case where iter.seen == {NULL_REVISION} |
41241
168041fa6d5f
rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents:
41134
diff
changeset
|
504 let iter = |
168041fa6d5f
rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents:
41134
diff
changeset
|
505 AncestorsIterator::new(SampleGraph, vec![0], 0, false).unwrap(); |
41054
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
506 assert!(iter.is_empty()); |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
507 } |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
508 |
40271
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
509 /// A corrupted Graph, supporting error handling tests |
41054
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
510 #[derive(Clone, Debug)] |
40271
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
511 struct Corrupted; |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
512 |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
513 impl Graph for Corrupted { |
40933
18513d6ef7d4
rust: changed Graph.parents to return [Revision; 2]
Georges Racinet <gracinet@anybox.fr>
parents:
40932
diff
changeset
|
514 fn parents(&self, rev: Revision) -> Result<[Revision; 2], GraphError> { |
40271
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
515 match rev { |
40933
18513d6ef7d4
rust: changed Graph.parents to return [Revision; 2]
Georges Racinet <gracinet@anybox.fr>
parents:
40932
diff
changeset
|
516 1 => Ok([0, -1]), |
40271
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
517 r => Err(GraphError::ParentOutOfRange(r)), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
518 } |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
519 } |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
520 } |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
521 |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
522 #[test] |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
523 fn test_initrev_out_of_range() { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
524 // inclusive=false looks up initrev's parents right away |
41241
168041fa6d5f
rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents:
41134
diff
changeset
|
525 match AncestorsIterator::new(SampleGraph, vec![25], 0, false) { |
40271
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
526 Ok(_) => panic!("Should have been ParentOutOfRange"), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
527 Err(e) => assert_eq!(e, GraphError::ParentOutOfRange(25)), |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
528 } |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
529 } |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
530 |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
531 #[test] |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
532 fn test_next_out_of_range() { |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
533 // inclusive=false looks up initrev's parents right away |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
534 let mut iter = |
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
535 AncestorsIterator::new(Corrupted, vec![1], 0, false).unwrap(); |
40929
43ca24b772d6
rust: adapted hg-core tests for iteration over Result
Georges Racinet <gracinet@anybox.fr>
parents:
40927
diff
changeset
|
536 assert_eq!(iter.next(), Some(Err(GraphError::ParentOutOfRange(0)))); |
40271
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
537 } |
40959
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
538 |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
539 #[test] |
41054
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
540 fn test_lazy_iter_contains() { |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
541 let mut lazy = |
41241
168041fa6d5f
rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents:
41134
diff
changeset
|
542 LazyAncestors::new(SampleGraph, vec![11, 13], 0, false).unwrap(); |
41054
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
543 |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
544 let revs: Vec<Revision> = lazy.iter().map(|r| r.unwrap()).collect(); |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
545 // compare with iterator tests on the same initial revisions |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
546 assert_eq!(revs, vec![8, 7, 4, 3, 2, 1, 0]); |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
547 |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
548 // contains() results are correct, unaffected by the fact that |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
549 // we consumed entirely an iterator out of lazy |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
550 assert_eq!(lazy.contains(2), Ok(true)); |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
551 assert_eq!(lazy.contains(9), Ok(false)); |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
552 } |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
553 |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
554 #[test] |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
555 fn test_lazy_contains_iter() { |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
556 let mut lazy = |
41241
168041fa6d5f
rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents:
41134
diff
changeset
|
557 LazyAncestors::new(SampleGraph, vec![11, 13], 0, false).unwrap(); // reminder: [8, 7, 4, 3, 2, 1, 0] |
41054
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
558 |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
559 assert_eq!(lazy.contains(2), Ok(true)); |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
560 assert_eq!(lazy.contains(6), Ok(false)); |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
561 |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
562 // after consumption of 2 by the inner iterator, results stay |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
563 // consistent |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
564 assert_eq!(lazy.contains(2), Ok(true)); |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
565 assert_eq!(lazy.contains(5), Ok(false)); |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
566 |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
567 // iter() still gives us a fresh iterator |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
568 let revs: Vec<Revision> = lazy.iter().map(|r| r.unwrap()).collect(); |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
569 assert_eq!(revs, vec![8, 7, 4, 3, 2, 1, 0]); |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
570 } |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
571 |
ef54bd33b476
rust: core implementation for lazyancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40959
diff
changeset
|
572 #[test] |
41246
619ee4039bd4
rust: MissingAncestors.basesheads()
Georges Racinet <georges.racinet@octobus.net>
parents:
41241
diff
changeset
|
573 /// Test constructor, add/get bases and heads |
619ee4039bd4
rust: MissingAncestors.basesheads()
Georges Racinet <georges.racinet@octobus.net>
parents:
41241
diff
changeset
|
574 fn test_missing_bases() -> Result<(), GraphError> { |
40959
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
575 let mut missing_ancestors = |
41241
168041fa6d5f
rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents:
41134
diff
changeset
|
576 MissingAncestors::new(SampleGraph, [5, 3, 1, 3].iter().cloned()); |
40959
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
577 let mut as_vec: Vec<Revision> = |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
578 missing_ancestors.get_bases().iter().cloned().collect(); |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
579 as_vec.sort(); |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
580 assert_eq!(as_vec, [1, 3, 5]); |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
581 |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
582 missing_ancestors.add_bases([3, 7, 8].iter().cloned()); |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
583 as_vec = missing_ancestors.get_bases().iter().cloned().collect(); |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
584 as_vec.sort(); |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
585 assert_eq!(as_vec, [1, 3, 5, 7, 8]); |
41246
619ee4039bd4
rust: MissingAncestors.basesheads()
Georges Racinet <georges.racinet@octobus.net>
parents:
41241
diff
changeset
|
586 |
619ee4039bd4
rust: MissingAncestors.basesheads()
Georges Racinet <georges.racinet@octobus.net>
parents:
41241
diff
changeset
|
587 as_vec = missing_ancestors.bases_heads()?.iter().cloned().collect(); |
619ee4039bd4
rust: MissingAncestors.basesheads()
Georges Racinet <georges.racinet@octobus.net>
parents:
41241
diff
changeset
|
588 as_vec.sort(); |
619ee4039bd4
rust: MissingAncestors.basesheads()
Georges Racinet <georges.racinet@octobus.net>
parents:
41241
diff
changeset
|
589 assert_eq!(as_vec, [3, 5, 7, 8]); |
619ee4039bd4
rust: MissingAncestors.basesheads()
Georges Racinet <georges.racinet@octobus.net>
parents:
41241
diff
changeset
|
590 Ok(()) |
40959
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
591 } |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
592 |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
593 fn assert_missing_remove( |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
594 bases: &[Revision], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
595 revs: &[Revision], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
596 expected: &[Revision], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
597 ) { |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
598 let mut missing_ancestors = |
41241
168041fa6d5f
rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents:
41134
diff
changeset
|
599 MissingAncestors::new(SampleGraph, bases.iter().cloned()); |
40959
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
600 let mut revset: HashSet<Revision> = revs.iter().cloned().collect(); |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
601 missing_ancestors |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
602 .remove_ancestors_from(&mut revset) |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
603 .unwrap(); |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
604 let mut as_vec: Vec<Revision> = revset.into_iter().collect(); |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
605 as_vec.sort(); |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
606 assert_eq!(as_vec.as_slice(), expected); |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
607 } |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
608 |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
609 #[test] |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
610 fn test_missing_remove() { |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
611 assert_missing_remove( |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
612 &[1, 2, 3, 4, 7], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
613 Vec::from_iter(1..10).as_slice(), |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
614 &[5, 6, 8, 9], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
615 ); |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
616 assert_missing_remove(&[10], &[11, 12, 13, 14], &[11, 12, 13, 14]); |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
617 assert_missing_remove(&[7], &[1, 2, 3, 4, 5], &[3, 5]); |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
618 } |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
619 |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
620 fn assert_missing_ancestors( |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
621 bases: &[Revision], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
622 revs: &[Revision], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
623 expected: &[Revision], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
624 ) { |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
625 let mut missing_ancestors = |
41241
168041fa6d5f
rust: factorized testing Graphs
Georges Racinet <georges.racinet@octobus.net>
parents:
41134
diff
changeset
|
626 MissingAncestors::new(SampleGraph, bases.iter().cloned()); |
40959
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
627 let missing = missing_ancestors |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
628 .missing_ancestors(revs.iter().cloned()) |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
629 .unwrap(); |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
630 assert_eq!(missing.as_slice(), expected); |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
631 } |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
632 |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
633 #[test] |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
634 fn test_missing_ancestors() { |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
635 // examples taken from test-ancestors.py by having it run |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
636 // on the same graph (both naive and fast Python algs) |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
637 assert_missing_ancestors(&[10], &[11], &[3, 7, 11]); |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
638 assert_missing_ancestors(&[11], &[10], &[5, 10]); |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
639 assert_missing_ancestors(&[7], &[9, 11], &[3, 6, 9, 11]); |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
640 } |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
641 |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
642 /// An interesting case found by a random generator similar to |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
643 /// the one in test-ancestor.py. An early version of Rust MissingAncestors |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
644 /// failed this, yet none of the integration tests of the whole suite |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
645 /// catched it. |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
646 #[test] |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
647 fn test_remove_ancestors_from_case1() { |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
648 let graph: VecGraph = vec![ |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
649 [NULL_REVISION, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
650 [0, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
651 [1, 0], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
652 [2, 1], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
653 [3, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
654 [4, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
655 [5, 1], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
656 [2, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
657 [7, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
658 [8, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
659 [9, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
660 [10, 1], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
661 [3, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
662 [12, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
663 [13, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
664 [14, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
665 [4, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
666 [16, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
667 [17, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
668 [18, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
669 [19, 11], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
670 [20, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
671 [21, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
672 [22, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
673 [23, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
674 [2, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
675 [3, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
676 [26, 24], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
677 [27, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
678 [28, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
679 [12, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
680 [1, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
681 [1, 9], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
682 [32, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
683 [33, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
684 [34, 31], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
685 [35, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
686 [36, 26], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
687 [37, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
688 [38, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
689 [39, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
690 [40, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
691 [41, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
692 [42, 26], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
693 [0, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
694 [44, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
695 [45, 4], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
696 [40, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
697 [47, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
698 [36, 0], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
699 [49, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
700 [NULL_REVISION, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
701 [51, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
702 [52, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
703 [53, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
704 [14, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
705 [55, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
706 [15, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
707 [23, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
708 [58, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
709 [59, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
710 [2, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
711 [61, 59], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
712 [62, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
713 [63, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
714 [NULL_REVISION, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
715 [65, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
716 [66, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
717 [67, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
718 [68, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
719 [37, 28], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
720 [69, 25], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
721 [71, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
722 [72, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
723 [50, 2], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
724 [74, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
725 [12, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
726 [18, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
727 [77, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
728 [78, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
729 [79, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
730 [43, 33], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
731 [81, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
732 [82, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
733 [83, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
734 [84, 45], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
735 [85, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
736 [86, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
737 [NULL_REVISION, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
738 [88, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
739 [NULL_REVISION, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
740 [76, 83], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
741 [44, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
742 [92, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
743 [93, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
744 [9, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
745 [95, 67], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
746 [96, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
747 [97, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
748 [NULL_REVISION, NULL_REVISION], |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
749 ]; |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
750 let problem_rev = 28 as Revision; |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
751 let problem_base = 70 as Revision; |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
752 // making the problem obvious: problem_rev is a parent of problem_base |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
753 assert_eq!(graph.parents(problem_base).unwrap()[1], problem_rev); |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
754 |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
755 let mut missing_ancestors: MissingAncestors<VecGraph> = |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
756 MissingAncestors::new( |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
757 graph, |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
758 [60, 26, 70, 3, 96, 19, 98, 49, 97, 47, 1, 6] |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
759 .iter() |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
760 .cloned(), |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
761 ); |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
762 assert!(missing_ancestors.bases.contains(&problem_base)); |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
763 |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
764 let mut revs: HashSet<Revision> = |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
765 [4, 12, 41, 28, 68, 38, 1, 30, 56, 44] |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
766 .iter() |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
767 .cloned() |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
768 .collect(); |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
769 missing_ancestors.remove_ancestors_from(&mut revs).unwrap(); |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
770 assert!(!revs.contains(&problem_rev)); |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
771 } |
d097dd0afc19
rust: translation of missingancestors
Georges Racinet <gracinet@anybox.fr>
parents:
40933
diff
changeset
|
772 |
40271
dbc28c91f7ff
rust: pure Rust lazyancestors iterator
Georges Racinet <gracinet@anybox.fr>
parents:
diff
changeset
|
773 } |