mercurial-scm/hg: rust/hg-core/src/ancestors.rs annotate

annotate rust/hg-core/src/ancestors.rs @ 48674:f7086f6173f8 stable

dirstate-v2: rename the configuration to enable the format The rename of the old experimental name was overlooked before the 6.0 release. We rename everything to use the new name (and keep the released name as an alias for compatibility). Differential Revision: https://phab.mercurial-scm.org/D12129

author	Pierre-Yves David <pierre-yves.david@octobus.net>
date	Tue, 01 Feb 2022 16:36:20 +0100
parents	26114bd6ec60
children	791f5d5f7a96

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};
42327 e8f3740cc067 rust-filepatterns: add a Rust implementation of pattern-related utils Rapha?l Gom?s <rgomes@octobus.net> parents: 41717 diff changeset	11 use crate::dagops;
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 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
41054 ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	29 /// Lazy ancestors set, backed by AncestorsIterator
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	30 pub struct LazyAncestors<G: Graph + Clone> {
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	31 graph: G,
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	32 containsiter: AncestorsIterator<G>,
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	33 initrevs: Vec<Revision>,
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	34 stoprev: Revision,
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	35 inclusive: bool,
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	36 }
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	37
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	38 pub struct MissingAncestors<G: Graph> {
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	39 graph: G,
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	40 bases: HashSet<Revision>,
41717 9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	41 max_base: Revision,
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	42 }
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 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.
41105 35ee590b1892 rust: use 'impl Trait' in method argument of AncestorsIterator Yuya Nishihara <yuya@tcha.org> parents: 41104 diff changeset	49 pub fn new(
40271 dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	50 graph: G,
41105 35ee590b1892 rust: use 'impl Trait' in method argument of AncestorsIterator Yuya Nishihara <yuya@tcha.org> parents: 41104 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,
41105 35ee590b1892 rust: use 'impl Trait' in method argument of AncestorsIterator Yuya Nishihara <yuya@tcha.org> parents: 41104 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();
44973 26114bd6ec60 rust: do a clippy pass Rapha?l Gom?s <rgomes@octobus.net> parents: 42841 diff changeset	58 let seen = visit.iter().cloned().collect();
40271 dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	59 return Ok(AncestorsIterator {
44973 26114bd6ec60 rust: do a clippy pass Rapha?l Gom?s <rgomes@octobus.net> parents: 42841 diff changeset	60 visit,
26114bd6ec60 rust: do a clippy pass Rapha?l Gom?s <rgomes@octobus.net> parents: 42841 diff changeset	61 seen,
26114bd6ec60 rust: do a clippy pass Rapha?l Gom?s <rgomes@octobus.net> parents: 42841 diff changeset	62 stoprev,
26114bd6ec60 rust: do a clippy pass Rapha?l Gom?s <rgomes@octobus.net> parents: 42841 diff changeset	63 graph,
40271 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(),
44973 26114bd6ec60 rust: do a clippy pass Rapha?l Gom?s <rgomes@octobus.net> parents: 42841 diff changeset	69 stoprev,
26114bd6ec60 rust: do a clippy pass Rapha?l Gom?s <rgomes@octobus.net> parents: 42841 diff changeset	70 graph,
40271 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 {
40933 18513d6ef7d4 rust: changed Graph.parents to return [Revision; 2] Georges Racinet <gracinet@anybox.fr> parents: 40932 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: 40932 diff changeset	75 this.conditionally_push_rev(parent);
18513d6ef7d4 rust: changed Graph.parents to return [Revision; 2] Georges Racinet <gracinet@anybox.fr> parents: 40932 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) {
41714 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
40863 443eb4bc41af rust: propagate error of index_get_parents() properly Yuya Nishihara <yuya@tcha.org> parents: 40832 diff changeset	93 pub fn contains(&mut self, target: Revision) -> Result<bool, GraphError> {
40300 72b94f946e90 rust: rustlazyancestors.__contains__ Georges Racinet <gracinet@anybox.fr> parents: 40271 diff changeset	94 if self.seen.contains(&target) && target != NULL_REVISION {
40863 443eb4bc41af rust: propagate error of index_get_parents() properly Yuya Nishihara <yuya@tcha.org> parents: 40832 diff changeset	95 return Ok(true);
40300 72b94f946e90 rust: rustlazyancestors.__contains__ Georges Racinet <gracinet@anybox.fr> parents: 40271 diff changeset	96 }
40863 443eb4bc41af rust: propagate error of index_get_parents() properly Yuya Nishihara <yuya@tcha.org> parents: 40832 diff changeset	97 for item in self {
443eb4bc41af rust: propagate error of index_get_parents() properly Yuya Nishihara <yuya@tcha.org> parents: 40832 diff changeset	98 let rev = item?;
40300 72b94f946e90 rust: rustlazyancestors.__contains__ Georges Racinet <gracinet@anybox.fr> parents: 40271 diff changeset	99 if rev == target {
40863 443eb4bc41af rust: propagate error of index_get_parents() properly Yuya Nishihara <yuya@tcha.org> parents: 40832 diff changeset	100 return Ok(true);
40300 72b94f946e90 rust: rustlazyancestors.__contains__ Georges Racinet <gracinet@anybox.fr> parents: 40271 diff changeset	101 }
72b94f946e90 rust: rustlazyancestors.__contains__ Georges Racinet <gracinet@anybox.fr> parents: 40271 diff changeset	102 if rev < target {
40863 443eb4bc41af rust: propagate error of index_get_parents() properly Yuya Nishihara <yuya@tcha.org> parents: 40832 diff changeset	103 return Ok(false);
40300 72b94f946e90 rust: rustlazyancestors.__contains__ Georges Racinet <gracinet@anybox.fr> parents: 40271 diff changeset	104 }
72b94f946e90 rust: rustlazyancestors.__contains__ Georges Racinet <gracinet@anybox.fr> parents: 40271 diff changeset	105 }
40863 443eb4bc41af rust: propagate error of index_get_parents() properly Yuya Nishihara <yuya@tcha.org> parents: 40832 diff changeset	106 Ok(false)
40300 72b94f946e90 rust: rustlazyancestors.__contains__ Georges Racinet <gracinet@anybox.fr> parents: 40271 diff changeset	107 }
41054 ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	108
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	109 pub fn peek(&self) -> Option<Revision> {
44973 26114bd6ec60 rust: do a clippy pass Rapha?l Gom?s <rgomes@octobus.net> parents: 42841 diff changeset	110 self.visit.peek().cloned()
41054 ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	111 }
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	112
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	113 /// Tell if the iterator is about an empty set
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	114 ///
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	115 /// The result does not depend whether the iterator has been consumed
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	116 /// or not.
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	117 /// This is mostly meant for iterators backing a lazy ancestors set
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	118 pub fn is_empty(&self) -> bool {
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	119 if self.visit.len() > 0 {
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	120 return false;
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	121 }
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	122 if self.seen.len() > 1 {
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	123 return false;
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	124 }
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	125 // at this point, the seen set is at most a singleton.
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	126 // If not `self.inclusive`, it's still possible that it has only
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	127 // the null revision
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	128 self.seen.is_empty() \|\| self.seen.contains(&NULL_REVISION)
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	129 }
40271 dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	130 }
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	131
41054 ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	132 /// Main implementation for the iterator
40271 dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	133 ///
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	134 /// The algorithm is the same as in `_lazyancestorsiter()` from `ancestors.py`
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	135 /// with a few non crucial differences:
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	136 ///
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	137 /// - there's no filtering of invalid parent revisions. Actually, it should be
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	138 /// consistent and more efficient to filter them from the end caller.
40932 dc38d976ff4d rust: improved docstring Georges Racinet <gracinet@anybox.fr> parents: 40929 diff changeset	139 /// - we don't have the optimization for adjacent revisions (i.e., the case
dc38d976ff4d rust: improved docstring Georges Racinet <gracinet@anybox.fr> parents: 40929 diff changeset	140 /// where `p1 == rev - 1`), because it amounts to update the first element of
dc38d976ff4d rust: improved docstring Georges Racinet <gracinet@anybox.fr> parents: 40929 diff changeset	141 /// the heap without sifting, which Rust's BinaryHeap doesn't let us do.
40271 dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	142 /// - we save a few pushes by comparing with `stoprev` before pushing
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	143 impl<G: Graph> Iterator for AncestorsIterator<G> {
40863 443eb4bc41af rust: propagate error of index_get_parents() properly Yuya Nishihara <yuya@tcha.org> parents: 40832 diff changeset	144 type Item = Result<Revision, GraphError>;
40271 dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	145
40863 443eb4bc41af rust: propagate error of index_get_parents() properly Yuya Nishihara <yuya@tcha.org> parents: 40832 diff changeset	146 fn next(&mut self) -> Option<Self::Item> {
40811 e13ab4acf555 rust: peek_mut optim for lazy ancestors Georges Racinet <gracinet@anybox.fr> parents: 40300 diff changeset	147 let current = match self.visit.peek() {
40271 dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	148 None => {
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	149 return None;
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	150 }
40811 e13ab4acf555 rust: peek_mut optim for lazy ancestors Georges Racinet <gracinet@anybox.fr> parents: 40300 diff changeset	151 Some(c) => *c,
40271 dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	152 };
40933 18513d6ef7d4 rust: changed Graph.parents to return [Revision; 2] Georges Racinet <gracinet@anybox.fr> parents: 40932 diff changeset	153 let [p1, p2] = match self.graph.parents(current) {
40863 443eb4bc41af rust: propagate error of index_get_parents() properly Yuya Nishihara <yuya@tcha.org> parents: 40832 diff changeset	154 Ok(ps) => ps,
443eb4bc41af rust: propagate error of index_get_parents() properly Yuya Nishihara <yuya@tcha.org> parents: 40832 diff changeset	155 Err(e) => return Some(Err(e)),
443eb4bc41af rust: propagate error of index_get_parents() properly Yuya Nishihara <yuya@tcha.org> parents: 40832 diff changeset	156 };
41714 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) {
40811 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
40832 70976974c14a rust: rename local variables in AncestorsIterator::next Georges Racinet <georges@racinet.fr> parents: 40811 diff changeset	163 self.conditionally_push_rev(p2);
40863 443eb4bc41af rust: propagate error of index_get_parents() properly Yuya Nishihara <yuya@tcha.org> parents: 40832 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
41054 ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	168 impl<G: Graph + Clone> LazyAncestors<G> {
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	169 pub fn new(
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	170 graph: G,
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	171 initrevs: impl IntoIterator<Item = Revision>,
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	172 stoprev: Revision,
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	173 inclusive: bool,
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	174 ) -> Result<Self, GraphError> {
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	175 let v: Vec<Revision> = initrevs.into_iter().collect();
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	176 Ok(LazyAncestors {
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	177 graph: graph.clone(),
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	178 containsiter: AncestorsIterator::new(
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	179 graph,
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	180 v.iter().cloned(),
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	181 stoprev,
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	182 inclusive,
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	183 )?,
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	184 initrevs: v,
44973 26114bd6ec60 rust: do a clippy pass Rapha?l Gom?s <rgomes@octobus.net> parents: 42841 diff changeset	185 stoprev,
26114bd6ec60 rust: do a clippy pass Rapha?l Gom?s <rgomes@octobus.net> parents: 42841 diff changeset	186 inclusive,
41054 ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	187 })
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	188 }
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	189
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	190 pub fn contains(&mut self, rev: Revision) -> Result<bool, GraphError> {
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	191 self.containsiter.contains(rev)
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	192 }
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	193
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	194 pub fn is_empty(&self) -> bool {
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	195 self.containsiter.is_empty()
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	196 }
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	197
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	198 pub fn iter(&self) -> AncestorsIterator<G> {
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 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: 40959 diff changeset	200 // for sure that AncestorsIterator constructor can't fail
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	201 AncestorsIterator::new(
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	202 self.graph.clone(),
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	203 self.initrevs.iter().cloned(),
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	204 self.stoprev,
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	205 self.inclusive,
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	206 )
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	207 .unwrap()
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	208 }
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	209 }
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	210
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	211 impl<G: Graph> MissingAncestors<G> {
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	212 pub fn new(graph: G, bases: impl IntoIterator<Item = Revision>) -> Self {
41717 9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	213 let mut created = MissingAncestors {
44973 26114bd6ec60 rust: do a clippy pass Rapha?l Gom?s <rgomes@octobus.net> parents: 42841 diff changeset	214 graph,
41717 9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	215 bases: HashSet::new(),
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	216 max_base: NULL_REVISION,
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	217 };
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	218 created.add_bases(bases);
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	219 created
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	220 }
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	221
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	222 pub fn has_bases(&self) -> bool {
41716 977432970080 rust: stop putting NULL_REVISION in MissingAncestors.bases Georges Racinet <georges.racinet@octobus.net> parents: 41715 diff changeset	223 !self.bases.is_empty()
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	224 }
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	225
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	226 /// Return a reference to current bases.
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	227 ///
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 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: 40933 diff changeset	229 /// read the bases attribute of a ancestor.missingancestors instance.
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	230 pub fn get_bases<'a>(&'a self) -> &'a HashSet<Revision> {
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	231 &self.bases
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	232 }
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 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.
41717 9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	242 pub fn into_bases_heads(
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	243 mut self,
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 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
41717 9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 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: 41716 diff changeset	250 ///
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	251 /// Takes care of keeping `self.max_base` up to date.
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	252 pub fn add_bases(
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	253 &mut self,
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	254 new_bases: impl IntoIterator<Item = Revision>,
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	255 ) {
41717 9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 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: 41716 diff changeset	257 self.bases.extend(
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	258 new_bases
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	259 .into_iter()
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	260 .filter(\|&rev\| rev != NULL_REVISION)
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	261 .map(\|r\| {
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	262 if r > max_base {
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	263 max_base = r;
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	264 }
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	265 r
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	266 }),
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	267 );
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	268 self.max_base = max_base;
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	269 }
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	270
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 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: 40933 diff changeset	272 pub fn remove_ancestors_from(
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	273 &mut self,
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	274 revs: &mut HashSet<Revision>,
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	275 ) -> Result<(), GraphError> {
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	276 revs.retain(\|r\| !self.bases.contains(r));
41716 977432970080 rust: stop putting NULL_REVISION in MissingAncestors.bases Georges Racinet <georges.racinet@octobus.net> parents: 41715 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: 41715 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: 41715 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: 41715 diff changeset	280 // unconditionnally true.
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	281 revs.remove(&NULL_REVISION);
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	282 if revs.is_empty() {
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	283 return Ok(());
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	284 }
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 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: 40933 diff changeset	286 // revs <= start need to be investigated
41717 9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 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: 41716 diff changeset	288 return Ok(());
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	289 }
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	290
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	291 // whatever happens, we'll keep at least keepcount of them
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	292 // knowing this gives us a earlier stop condition than
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	293 // going all the way to the root
41717 9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	294 let keepcount = revs.iter().filter(\|r\| **r > self.max_base).count();
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	295
41717 9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	296 let mut curr = self.max_base;
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	297 while curr != NULL_REVISION && revs.len() > keepcount {
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	298 if self.bases.contains(&curr) {
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	299 revs.remove(&curr);
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	300 self.add_parents(curr)?;
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	301 }
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	302 curr -= 1;
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	303 }
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	304 Ok(())
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	305 }
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	306
41717 9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 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: 41716 diff changeset	308 ///
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	309 /// This has no effect on `self.max_base`
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	310 #[inline]
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	311 fn add_parents(&mut self, rev: Revision) -> Result<(), GraphError> {
41717 9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	312 if rev == NULL_REVISION {
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	313 return Ok(());
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	314 }
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	315 for p in self.graph.parents(rev)?.iter().cloned() {
41717 9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 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: 41716 diff changeset	317 // over
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	318 if p != NULL_REVISION {
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	319 self.bases.insert(p);
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	320 }
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	321 }
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	322 Ok(())
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	323 }
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	324
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 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: 40933 diff changeset	326 ///
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	327 /// This may include elements from revs.
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	328 ///
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 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: 40933 diff changeset	330 /// revision number order, which is a topological order.
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	331 pub fn missing_ancestors(
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	332 &mut self,
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	333 revs: impl IntoIterator<Item = Revision>,
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	334 ) -> Result<Vec<Revision>, GraphError> {
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	335 // just for convenience and comparison with Python version
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	336 let bases_visit = &mut self.bases;
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	337 let mut revs: HashSet<Revision> = revs
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	338 .into_iter()
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	339 .filter(\|r\| !bases_visit.contains(r))
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	340 .collect();
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	341 let revs_visit = &mut revs;
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	342 let mut both_visit: HashSet<Revision> =
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	343 revs_visit.intersection(&bases_visit).cloned().collect();
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	344 if revs_visit.is_empty() {
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	345 return Ok(Vec::new());
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	346 }
41717 9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 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: 41716 diff changeset	348 let start = max(self.max_base, max_revs);
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	349
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	350 // TODO heuristics for with_capacity()?
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	351 let mut missing: Vec<Revision> = Vec::new();
41104 247f51cfc668 rust: use .rev() for reverse range Yuya Nishihara <yuya@tcha.org> parents: 41054 diff changeset	352 for curr in (0..=start).rev() {
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	353 if revs_visit.is_empty() {
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	354 break;
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	355 }
41715 fccb61a1777b rust: less set lookups in MissingAncestors Georges Racinet <georges.racinet@octobus.net> parents: 41714 diff changeset	356 if both_visit.remove(&curr) {
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 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: 40933 diff changeset	358 // another path
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	359 for p in self.graph.parents(curr)?.iter().cloned() {
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	360 if p == NULL_REVISION {
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	361 continue;
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	362 }
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	363 revs_visit.remove(&p);
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	364 bases_visit.insert(p);
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	365 both_visit.insert(p);
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	366 }
41134 17a195676472 rust-ancestors: adjust branches and inline comments per previous change Yuya Nishihara <yuya@tcha.org> parents: 41133 diff changeset	367 } else if revs_visit.remove(&curr) {
41131 486908e691be rust-ancestors: adjust indent level to make next change easier to follow Yuya Nishihara <yuya@tcha.org> parents: 41105 diff changeset	368 missing.push(curr);
486908e691be rust-ancestors: adjust indent level to make next change easier to follow Yuya Nishihara <yuya@tcha.org> parents: 41105 diff changeset	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: 41105 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: 41105 diff changeset	371 continue;
486908e691be rust-ancestors: adjust indent level to make next change easier to follow Yuya Nishihara <yuya@tcha.org> parents: 41105 diff changeset	372 }
41715 fccb61a1777b rust: less set lookups in MissingAncestors Georges Racinet <georges.racinet@octobus.net> parents: 41714 diff changeset	373 if bases_visit.contains(&p) {
fccb61a1777b rust: less set lookups in MissingAncestors Georges Racinet <georges.racinet@octobus.net> parents: 41714 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: 41714 diff changeset	375 revs_visit.remove(&p);
fccb61a1777b rust: less set lookups in MissingAncestors Georges Racinet <georges.racinet@octobus.net> parents: 41714 diff changeset	376 both_visit.insert(p);
fccb61a1777b rust: less set lookups in MissingAncestors Georges Racinet <georges.racinet@octobus.net> parents: 41714 diff changeset	377 } else if both_visit.contains(&p) {
fccb61a1777b rust: less set lookups in MissingAncestors Georges Racinet <georges.racinet@octobus.net> parents: 41714 diff changeset	378 // p should have been in bases_visit
41131 486908e691be rust-ancestors: adjust indent level to make next change easier to follow Yuya Nishihara <yuya@tcha.org> parents: 41105 diff changeset	379 revs_visit.remove(&p);
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	380 bases_visit.insert(p);
41131 486908e691be rust-ancestors: adjust indent level to make next change easier to follow Yuya Nishihara <yuya@tcha.org> parents: 41105 diff changeset	381 } else {
486908e691be rust-ancestors: adjust indent level to make next change easier to follow Yuya Nishihara <yuya@tcha.org> parents: 41105 diff changeset	382 // visit later
41133 a1b3800c8a19 rust-ancestors: remove unreachable conditions from missing_ancestors() Yuya Nishihara <yuya@tcha.org> parents: 41132 diff changeset	383 revs_visit.insert(p);
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	384 }
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	385 }
41132 55dc1da8df2f rust-ancestors: duplicate loop that visits parents of revs/bases Yuya Nishihara <yuya@tcha.org> parents: 41131 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: 41131 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: 41131 diff changeset	388 if p == NULL_REVISION {
55dc1da8df2f rust-ancestors: duplicate loop that visits parents of revs/bases Yuya Nishihara <yuya@tcha.org> parents: 41131 diff changeset	389 continue;
55dc1da8df2f rust-ancestors: duplicate loop that visits parents of revs/bases Yuya Nishihara <yuya@tcha.org> parents: 41131 diff changeset	390 }
41715 fccb61a1777b rust: less set lookups in MissingAncestors Georges Racinet <georges.racinet@octobus.net> parents: 41714 diff changeset	391 if revs_visit.remove(&p) \|\| both_visit.contains(&p) {
41134 17a195676472 rust-ancestors: adjust branches and inline comments per previous change Yuya Nishihara <yuya@tcha.org> parents: 41133 diff changeset	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: 41133 diff changeset	393 // in revs_visit, which means p is ::revs & ::bases.
41132 55dc1da8df2f rust-ancestors: duplicate loop that visits parents of revs/bases Yuya Nishihara <yuya@tcha.org> parents: 41131 diff changeset	394 bases_visit.insert(p);
55dc1da8df2f rust-ancestors: duplicate loop that visits parents of revs/bases Yuya Nishihara <yuya@tcha.org> parents: 41131 diff changeset	395 both_visit.insert(p);
55dc1da8df2f rust-ancestors: duplicate loop that visits parents of revs/bases Yuya Nishihara <yuya@tcha.org> parents: 41131 diff changeset	396 } else {
41133 a1b3800c8a19 rust-ancestors: remove unreachable conditions from missing_ancestors() Yuya Nishihara <yuya@tcha.org> parents: 41132 diff changeset	397 bases_visit.insert(p);
41132 55dc1da8df2f rust-ancestors: duplicate loop that visits parents of revs/bases Yuya Nishihara <yuya@tcha.org> parents: 41131 diff changeset	398 }
55dc1da8df2f rust-ancestors: duplicate loop that visits parents of revs/bases Yuya Nishihara <yuya@tcha.org> parents: 41131 diff changeset	399 }
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	400 }
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	401 }
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	402 missing.reverse();
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	403 Ok(missing)
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	404 }
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	405 }
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 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: 41134 diff changeset	411 use crate::testing::{SampleGraph, VecGraph};
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 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()
40929 43ca24b772d6 rust: adapted hg-core tests for iteration over Result Georges Racinet <gracinet@anybox.fr> parents: 40927 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: 41134 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: 41134 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: 41134 diff changeset	436 list_ancestors(SampleGraph, vec![1, 3], 0, false),
168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	437 vec![1, 0]
168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	438 );
168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	439 assert_eq!(
168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 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: 41134 diff changeset	444 list_ancestors(SampleGraph, vec![11, 13], 6, false),
168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	445 vec![8, 7]
168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	446 );
168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	447 assert_eq!(
168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 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: 41134 diff changeset	451 assert_eq!(
168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	452 list_ancestors(SampleGraph, vec![11, 13], 11, true),
168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	453 vec![13, 11]
168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 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: 41134 diff changeset	456 list_ancestors(SampleGraph, vec![11, 13], 12, true),
168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	457 vec![13]
168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	458 );
168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	459 assert_eq!(
168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 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: 41134 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: 41134 diff changeset	479 AncestorsIterator::new(SampleGraph, vec![10, 1], 0, true).unwrap();
40929 43ca24b772d6 rust: adapted hg-core tests for iteration over Result Georges Racinet <gracinet@anybox.fr> parents: 40927 diff changeset	480 assert!(lazy.contains(1).unwrap());
43ca24b772d6 rust: adapted hg-core tests for iteration over Result Georges Racinet <gracinet@anybox.fr> parents: 40927 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: 41134 diff changeset	484 AncestorsIterator::new(SampleGraph, vec![0], 0, false).unwrap();
40929 43ca24b772d6 rust: adapted hg-core tests for iteration over Result Georges Racinet <gracinet@anybox.fr> parents: 40927 diff changeset	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
41054 ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	488 #[test]
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	489 fn test_peek() {
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	490 let mut iter =
41241 168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	491 AncestorsIterator::new(SampleGraph, vec![10], 0, true).unwrap();
41054 ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	492 // peek() gives us the next value
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	493 assert_eq!(iter.peek(), Some(10));
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	494 // but it's not been consumed
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	495 assert_eq!(iter.next(), Some(Ok(10)));
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	496 // and iteration resumes normally
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	497 assert_eq!(iter.next(), Some(Ok(5)));
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	498
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 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: 40959 diff changeset	500 while iter.next().is_some() {}
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	501 assert_eq!(iter.peek(), None);
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	502 }
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	503
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	504 #[test]
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	505 fn test_empty() {
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	506 let mut iter =
41241 168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	507 AncestorsIterator::new(SampleGraph, vec![10], 0, true).unwrap();
41054 ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	508 assert!(!iter.is_empty());
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	509 while iter.next().is_some() {}
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	510 assert!(!iter.is_empty());
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	511
41241 168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	512 let iter =
168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	513 AncestorsIterator::new(SampleGraph, vec![], 0, true).unwrap();
41054 ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	514 assert!(iter.is_empty());
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	515
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	516 // case where iter.seen == {NULL_REVISION}
41241 168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	517 let iter =
168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	518 AncestorsIterator::new(SampleGraph, vec![0], 0, false).unwrap();
41054 ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	519 assert!(iter.is_empty());
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	520 }
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 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
41054 ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 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 {
40933 18513d6ef7d4 rust: changed Graph.parents to return [Revision; 2] Georges Racinet <gracinet@anybox.fr> parents: 40932 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 {
40933 18513d6ef7d4 rust: changed Graph.parents to return [Revision; 2] Georges Racinet <gracinet@anybox.fr> parents: 40932 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: 41134 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();
40929 43ca24b772d6 rust: adapted hg-core tests for iteration over Result Georges Racinet <gracinet@anybox.fr> parents: 40927 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 }
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	551
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	552 #[test]
41054 ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	553 fn test_lazy_iter_contains() {
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	554 let mut lazy =
41241 168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	555 LazyAncestors::new(SampleGraph, vec![11, 13], 0, false).unwrap();
41054 ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	556
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 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: 40959 diff changeset	558 // compare with iterator tests on the same initial revisions
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 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: 40959 diff changeset	560
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	561 // contains() results are correct, unaffected by the fact that
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	562 // we consumed entirely an iterator out of lazy
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	563 assert_eq!(lazy.contains(2), Ok(true));
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	564 assert_eq!(lazy.contains(9), Ok(false));
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	565 }
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	566
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	567 #[test]
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	568 fn test_lazy_contains_iter() {
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	569 let mut lazy =
41241 168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	570 LazyAncestors::new(SampleGraph, vec![11, 13], 0, false).unwrap(); // reminder: [8, 7, 4, 3, 2, 1, 0]
41054 ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	571
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	572 assert_eq!(lazy.contains(2), Ok(true));
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	573 assert_eq!(lazy.contains(6), Ok(false));
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	574
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 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: 40959 diff changeset	576 // consistent
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	577 assert_eq!(lazy.contains(2), Ok(true));
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	578 assert_eq!(lazy.contains(5), Ok(false));
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	579
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	580 // iter() still gives us a fresh iterator
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 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: 40959 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: 40959 diff changeset	583 }
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	584
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 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> {
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	588 let mut missing_ancestors =
41241 168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	589 MissingAncestors::new(SampleGraph, [5, 3, 1, 3].iter().cloned());
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	590 let mut as_vec: Vec<Revision> =
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	591 missing_ancestors.get_bases().iter().cloned().collect();
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	592 as_vec.sort();
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	593 assert_eq!(as_vec, [1, 3, 5]);
41717 9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	594 assert_eq!(missing_ancestors.max_base, 5);
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	595
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	596 missing_ancestors.add_bases([3, 7, 8].iter().cloned());
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	597 as_vec = missing_ancestors.get_bases().iter().cloned().collect();
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	598 as_vec.sort();
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	599 assert_eq!(as_vec, [1, 3, 5, 7, 8]);
41717 9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 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(())
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	606 }
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	607
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	608 fn assert_missing_remove(
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	609 bases: &[Revision],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	610 revs: &[Revision],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	611 expected: &[Revision],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	612 ) {
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	613 let mut missing_ancestors =
41241 168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	614 MissingAncestors::new(SampleGraph, bases.iter().cloned());
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	615 let mut revset: HashSet<Revision> = revs.iter().cloned().collect();
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	616 missing_ancestors
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	617 .remove_ancestors_from(&mut revset)
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	618 .unwrap();
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	619 let mut as_vec: Vec<Revision> = revset.into_iter().collect();
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	620 as_vec.sort();
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	621 assert_eq!(as_vec.as_slice(), expected);
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	622 }
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	623
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	624 #[test]
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	625 fn test_missing_remove() {
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	626 assert_missing_remove(
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	627 &[1, 2, 3, 4, 7],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	628 Vec::from_iter(1..10).as_slice(),
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	629 &[5, 6, 8, 9],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	630 );
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 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: 40933 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: 40933 diff changeset	633 }
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	634
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	635 fn assert_missing_ancestors(
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	636 bases: &[Revision],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	637 revs: &[Revision],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	638 expected: &[Revision],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	639 ) {
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	640 let mut missing_ancestors =
41241 168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	641 MissingAncestors::new(SampleGraph, bases.iter().cloned());
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	642 let missing = missing_ancestors
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	643 .missing_ancestors(revs.iter().cloned())
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	644 .unwrap();
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	645 assert_eq!(missing.as_slice(), expected);
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	646 }
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	647
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	648 #[test]
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	649 fn test_missing_ancestors() {
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	650 // examples taken from test-ancestors.py by having it run
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	651 // on the same graph (both naive and fast Python algs)
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	652 assert_missing_ancestors(&[10], &[11], &[3, 7, 11]);
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	653 assert_missing_ancestors(&[11], &[10], &[5, 10]);
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	654 assert_missing_ancestors(&[7], &[9, 11], &[3, 6, 9, 11]);
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	655 }
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	656
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	657 /// An interesting case found by a random generator similar to
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 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: 40933 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: 40933 diff changeset	660 /// catched it.
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	661 #[test]
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	662 fn test_remove_ancestors_from_case1() {
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	663 let graph: VecGraph = vec![
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	664 [NULL_REVISION, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	665 [0, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	666 [1, 0],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	667 [2, 1],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	668 [3, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	669 [4, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	670 [5, 1],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	671 [2, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	672 [7, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	673 [8, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	674 [9, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	675 [10, 1],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	676 [3, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	677 [12, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	678 [13, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	679 [14, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	680 [4, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	681 [16, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	682 [17, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	683 [18, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	684 [19, 11],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	685 [20, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	686 [21, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	687 [22, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	688 [23, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	689 [2, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	690 [3, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	691 [26, 24],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	692 [27, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	693 [28, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	694 [12, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	695 [1, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	696 [1, 9],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	697 [32, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	698 [33, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	699 [34, 31],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	700 [35, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	701 [36, 26],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	702 [37, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	703 [38, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	704 [39, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	705 [40, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	706 [41, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	707 [42, 26],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	708 [0, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	709 [44, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	710 [45, 4],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	711 [40, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	712 [47, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	713 [36, 0],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	714 [49, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	715 [NULL_REVISION, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	716 [51, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	717 [52, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	718 [53, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	719 [14, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	720 [55, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	721 [15, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	722 [23, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	723 [58, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	724 [59, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	725 [2, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	726 [61, 59],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	727 [62, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	728 [63, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	729 [NULL_REVISION, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	730 [65, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	731 [66, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	732 [67, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	733 [68, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	734 [37, 28],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	735 [69, 25],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	736 [71, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	737 [72, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	738 [50, 2],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	739 [74, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	740 [12, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	741 [18, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	742 [77, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	743 [78, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	744 [79, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	745 [43, 33],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	746 [81, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	747 [82, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	748 [83, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	749 [84, 45],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	750 [85, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	751 [86, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	752 [NULL_REVISION, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	753 [88, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	754 [NULL_REVISION, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	755 [76, 83],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	756 [44, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	757 [92, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	758 [93, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	759 [9, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	760 [95, 67],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	761 [96, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	762 [97, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	763 [NULL_REVISION, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	764 ];
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	765 let problem_rev = 28 as Revision;
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	766 let problem_base = 70 as Revision;
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 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: 40933 diff changeset	768 assert_eq!(graph.parents(problem_base).unwrap()[1], problem_rev);
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	769
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	770 let mut missing_ancestors: MissingAncestors<VecGraph> =
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	771 MissingAncestors::new(
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	772 graph,
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 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: 40933 diff changeset	774 .iter()
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	775 .cloned(),
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	776 );
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	777 assert!(missing_ancestors.bases.contains(&problem_base));
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	778
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	779 let mut revs: HashSet<Revision> =
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	780 [4, 12, 41, 28, 68, 38, 1, 30, 56, 44]
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	781 .iter()
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	782 .cloned()
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	783 .collect();
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	784 missing_ancestors.remove_ancestors_from(&mut revs).unwrap();
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	785 assert!(!revs.contains(&problem_rev));
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	786 }
40271 dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	787 }

Mercurial > public > mercurial-scm > hg

annotate rust/hg-core/src/ancestors.rs @ 48674:f7086f6173f8 stable