Mercurial > public > mercurial-scm > hg-stable

annotate rust/hg-core/src/ancestors.rs @ 43013:198b51d453fe

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