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

annotate rust/hg-core/src/ancestors.rs @ 48973:e2f8ed37201c stable

rust-status: cap the number of concurrent threads to 16 During benchmarking it was determined that the use of more threads is very advantageous... until we use more than 16. This is most likely due to some resource contention (thrashing, etc.). Until we have time to figure out and fix the underlying cause, let's just cap at 16 threads. Differential Revision: https://phab.mercurial-scm.org/D12384

author	Rapha?l Gom?s <rgomes@octobus.net>
date	Fri, 18 Mar 2022 16:15:44 +0100
parents	791f5d5f7a96
children	c7fb9b74e753

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
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	29 pub struct MissingAncestors<G: Graph> {
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	30 graph: G,
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	31 bases: HashSet<Revision>,
41717 9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	32 max_base: Revision,
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	33 }
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	34
40271 dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	35 impl<G: Graph> AncestorsIterator<G> {
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	36 /// Constructor.
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	37 ///
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	38 /// 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	39 /// 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	40 pub fn new(
40271 dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	41 graph: G,
41105 35ee590b1892 rust: use 'impl Trait' in method argument of AncestorsIterator Yuya Nishihara <yuya@tcha.org> parents: 41104 diff changeset	42 initrevs: impl IntoIterator<Item = Revision>,
40271 dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	43 stoprev: Revision,
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	44 inclusive: bool,
41105 35ee590b1892 rust: use 'impl Trait' in method argument of AncestorsIterator Yuya Nishihara <yuya@tcha.org> parents: 41104 diff changeset	45 ) -> Result<Self, GraphError> {
40271 dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	46 let filtered_initrevs = initrevs.into_iter().filter(\|&r\| r >= stoprev);
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	47 if inclusive {
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	48 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	49 let seen = visit.iter().cloned().collect();
40271 dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	50 return Ok(AncestorsIterator {
44973 26114bd6ec60 rust: do a clippy pass Rapha?l Gom?s <rgomes@octobus.net> parents: 42841 diff changeset	51 visit,
26114bd6ec60 rust: do a clippy pass Rapha?l Gom?s <rgomes@octobus.net> parents: 42841 diff changeset	52 seen,
26114bd6ec60 rust: do a clippy pass Rapha?l Gom?s <rgomes@octobus.net> parents: 42841 diff changeset	53 stoprev,
26114bd6ec60 rust: do a clippy pass Rapha?l Gom?s <rgomes@octobus.net> parents: 42841 diff changeset	54 graph,
40271 dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	55 });
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	56 }
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	57 let mut this = AncestorsIterator {
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	58 visit: BinaryHeap::new(),
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	59 seen: HashSet::new(),
44973 26114bd6ec60 rust: do a clippy pass Rapha?l Gom?s <rgomes@octobus.net> parents: 42841 diff changeset	60 stoprev,
26114bd6ec60 rust: do a clippy pass Rapha?l Gom?s <rgomes@octobus.net> parents: 42841 diff changeset	61 graph,
40271 dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	62 };
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	63 this.seen.insert(NULL_REVISION);
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	64 for rev in filtered_initrevs {
40933 18513d6ef7d4 rust: changed Graph.parents to return [Revision; 2] Georges Racinet <gracinet@anybox.fr> parents: 40932 diff changeset	65 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	66 this.conditionally_push_rev(parent);
18513d6ef7d4 rust: changed Graph.parents to return [Revision; 2] Georges Racinet <gracinet@anybox.fr> parents: 40932 diff changeset	67 }
40271 dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	68 }
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	69 Ok(this)
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	70 }
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	71
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	72 #[inline]
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	73 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	74 if self.stoprev <= rev && self.seen.insert(rev) {
40271 dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	75 self.visit.push(rev);
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	76 }
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	77 }
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	78
40300 72b94f946e90 rust: rustlazyancestors.__contains__ Georges Racinet <gracinet@anybox.fr> parents: 40271 diff changeset	79 /// Consumes partially the iterator to tell if the given target
72b94f946e90 rust: rustlazyancestors.__contains__ Georges Racinet <gracinet@anybox.fr> parents: 40271 diff changeset	80 /// revision
72b94f946e90 rust: rustlazyancestors.__contains__ Georges Racinet <gracinet@anybox.fr> parents: 40271 diff changeset	81 /// is in the ancestors it emits.
72b94f946e90 rust: rustlazyancestors.__contains__ Georges Racinet <gracinet@anybox.fr> parents: 40271 diff changeset	82 /// This is meant for iterators actually dedicated to that kind of
72b94f946e90 rust: rustlazyancestors.__contains__ Georges Racinet <gracinet@anybox.fr> parents: 40271 diff changeset	83 /// purpose
40863 443eb4bc41af rust: propagate error of index_get_parents() properly Yuya Nishihara <yuya@tcha.org> parents: 40832 diff changeset	84 pub fn contains(&mut self, target: Revision) -> Result<bool, GraphError> {
40300 72b94f946e90 rust: rustlazyancestors.__contains__ Georges Racinet <gracinet@anybox.fr> parents: 40271 diff changeset	85 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	86 return Ok(true);
40300 72b94f946e90 rust: rustlazyancestors.__contains__ Georges Racinet <gracinet@anybox.fr> parents: 40271 diff changeset	87 }
40863 443eb4bc41af rust: propagate error of index_get_parents() properly Yuya Nishihara <yuya@tcha.org> parents: 40832 diff changeset	88 for item in self {
443eb4bc41af rust: propagate error of index_get_parents() properly Yuya Nishihara <yuya@tcha.org> parents: 40832 diff changeset	89 let rev = item?;
40300 72b94f946e90 rust: rustlazyancestors.__contains__ Georges Racinet <gracinet@anybox.fr> parents: 40271 diff changeset	90 if rev == target {
40863 443eb4bc41af rust: propagate error of index_get_parents() properly Yuya Nishihara <yuya@tcha.org> parents: 40832 diff changeset	91 return Ok(true);
40300 72b94f946e90 rust: rustlazyancestors.__contains__ Georges Racinet <gracinet@anybox.fr> parents: 40271 diff changeset	92 }
72b94f946e90 rust: rustlazyancestors.__contains__ Georges Racinet <gracinet@anybox.fr> parents: 40271 diff changeset	93 if rev < target {
40863 443eb4bc41af rust: propagate error of index_get_parents() properly Yuya Nishihara <yuya@tcha.org> parents: 40832 diff changeset	94 return Ok(false);
40300 72b94f946e90 rust: rustlazyancestors.__contains__ Georges Racinet <gracinet@anybox.fr> parents: 40271 diff changeset	95 }
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 Ok(false)
40300 72b94f946e90 rust: rustlazyancestors.__contains__ Georges Racinet <gracinet@anybox.fr> parents: 40271 diff changeset	98 }
41054 ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	99
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	100 pub fn peek(&self) -> Option<Revision> {
44973 26114bd6ec60 rust: do a clippy pass Rapha?l Gom?s <rgomes@octobus.net> parents: 42841 diff changeset	101 self.visit.peek().cloned()
41054 ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	102 }
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	103
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	104 /// Tell if the iterator is about an empty set
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	105 ///
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	106 /// 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	107 /// or not.
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	108 /// 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	109 pub fn is_empty(&self) -> bool {
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	110 if self.visit.len() > 0 {
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	111 return false;
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 if self.seen.len() > 1 {
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	114 return false;
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	115 }
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	116 // 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	117 // 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	118 // the null revision
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	119 self.seen.is_empty() \|\| self.seen.contains(&NULL_REVISION)
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	120 }
40271 dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	121 }
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	122
41054 ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	123 /// Main implementation for the iterator
40271 dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	124 ///
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	125 /// 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	126 /// with a few non crucial differences:
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	127 ///
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	128 /// - 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	129 /// 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	130 /// - 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	131 /// 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	132 /// 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	133 /// - 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	134 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	135 type Item = Result<Revision, GraphError>;
40271 dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	136
40863 443eb4bc41af rust: propagate error of index_get_parents() properly Yuya Nishihara <yuya@tcha.org> parents: 40832 diff changeset	137 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	138 let current = match self.visit.peek() {
40271 dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	139 None => {
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	140 return None;
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	141 }
40811 e13ab4acf555 rust: peek_mut optim for lazy ancestors Georges Racinet <gracinet@anybox.fr> parents: 40300 diff changeset	142 Some(c) => *c,
40271 dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	143 };
40933 18513d6ef7d4 rust: changed Graph.parents to return [Revision; 2] Georges Racinet <gracinet@anybox.fr> parents: 40932 diff changeset	144 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	145 Ok(ps) => ps,
443eb4bc41af rust: propagate error of index_get_parents() properly Yuya Nishihara <yuya@tcha.org> parents: 40832 diff changeset	146 Err(e) => return Some(Err(e)),
443eb4bc41af rust: propagate error of index_get_parents() properly Yuya Nishihara <yuya@tcha.org> parents: 40832 diff changeset	147 };
41714 70827ebba453 rust: less set lookups in AncestorsIterator Georges Racinet <georges.racinet@octobus.net> parents: 41246 diff changeset	148 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	149 self.visit.pop();
e13ab4acf555 rust: peek_mut optim for lazy ancestors Georges Racinet <gracinet@anybox.fr> parents: 40300 diff changeset	150 } else {
e13ab4acf555 rust: peek_mut optim for lazy ancestors Georges Racinet <gracinet@anybox.fr> parents: 40300 diff changeset	151 *(self.visit.peek_mut().unwrap()) = p1;
e13ab4acf555 rust: peek_mut optim for lazy ancestors Georges Racinet <gracinet@anybox.fr> parents: 40300 diff changeset	152 };
e13ab4acf555 rust: peek_mut optim for lazy ancestors Georges Racinet <gracinet@anybox.fr> parents: 40300 diff changeset	153
40832 70976974c14a rust: rename local variables in AncestorsIterator::next Georges Racinet <georges@racinet.fr> parents: 40811 diff changeset	154 self.conditionally_push_rev(p2);
40863 443eb4bc41af rust: propagate error of index_get_parents() properly Yuya Nishihara <yuya@tcha.org> parents: 40832 diff changeset	155 Some(Ok(current))
40271 dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	156 }
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	157 }
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	158
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	159 impl<G: Graph> MissingAncestors<G> {
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	160 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	161 let mut created = MissingAncestors {
44973 26114bd6ec60 rust: do a clippy pass Rapha?l Gom?s <rgomes@octobus.net> parents: 42841 diff changeset	162 graph,
41717 9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	163 bases: HashSet::new(),
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	164 max_base: NULL_REVISION,
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	165 };
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	166 created.add_bases(bases);
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	167 created
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	168 }
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	169
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	170 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	171 !self.bases.is_empty()
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	172 }
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	173
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	174 /// Return a reference to current bases.
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	175 ///
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	176 /// 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	177 /// read the bases attribute of a ancestor.missingancestors instance.
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	178 pub fn get_bases<'a>(&'a self) -> &'a HashSet<Revision> {
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	179 &self.bases
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	180 }
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	181
41246 619ee4039bd4 rust: MissingAncestors.basesheads() Georges Racinet <georges.racinet@octobus.net> parents: 41241 diff changeset	182 /// Computes the relative heads of current bases.
619ee4039bd4 rust: MissingAncestors.basesheads() Georges Racinet <georges.racinet@octobus.net> parents: 41241 diff changeset	183 ///
619ee4039bd4 rust: MissingAncestors.basesheads() Georges Racinet <georges.racinet@octobus.net> parents: 41241 diff changeset	184 /// The object is still usable after this.
619ee4039bd4 rust: MissingAncestors.basesheads() Georges Racinet <georges.racinet@octobus.net> parents: 41241 diff changeset	185 pub fn bases_heads(&self) -> Result<HashSet<Revision>, GraphError> {
619ee4039bd4 rust: MissingAncestors.basesheads() Georges Racinet <georges.racinet@octobus.net> parents: 41241 diff changeset	186 dagops::heads(&self.graph, self.bases.iter())
619ee4039bd4 rust: MissingAncestors.basesheads() Georges Racinet <georges.racinet@octobus.net> parents: 41241 diff changeset	187 }
619ee4039bd4 rust: MissingAncestors.basesheads() Georges Racinet <georges.racinet@octobus.net> parents: 41241 diff changeset	188
619ee4039bd4 rust: MissingAncestors.basesheads() Georges Racinet <georges.racinet@octobus.net> parents: 41241 diff changeset	189 /// 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	190 pub fn into_bases_heads(
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	191 mut self,
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	192 ) -> Result<HashSet<Revision>, GraphError> {
41246 619ee4039bd4 rust: MissingAncestors.basesheads() Georges Racinet <georges.racinet@octobus.net> parents: 41241 diff changeset	193 dagops::retain_heads(&self.graph, &mut self.bases)?;
619ee4039bd4 rust: MissingAncestors.basesheads() Georges Racinet <georges.racinet@octobus.net> parents: 41241 diff changeset	194 Ok(self.bases)
619ee4039bd4 rust: MissingAncestors.basesheads() Georges Racinet <georges.racinet@octobus.net> parents: 41241 diff changeset	195 }
619ee4039bd4 rust: MissingAncestors.basesheads() Georges Racinet <georges.racinet@octobus.net> parents: 41241 diff changeset	196
41717 9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	197 /// 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	198 ///
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	199 /// 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	200 pub fn add_bases(
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	201 &mut self,
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	202 new_bases: impl IntoIterator<Item = Revision>,
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	203 ) {
41717 9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	204 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	205 self.bases.extend(
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	206 new_bases
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	207 .into_iter()
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	208 .filter(\|&rev\| rev != NULL_REVISION)
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	209 .map(\|r\| {
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	210 if r > max_base {
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	211 max_base = r;
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	212 }
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	213 r
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	214 }),
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	215 );
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	216 self.max_base = max_base;
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	217 }
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	218
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	219 /// 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	220 pub fn remove_ancestors_from(
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	221 &mut self,
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	222 revs: &mut HashSet<Revision>,
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	223 ) -> Result<(), GraphError> {
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	224 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	225 // 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	226 // 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	227 // 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	228 // unconditionnally true.
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	229 revs.remove(&NULL_REVISION);
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	230 if revs.is_empty() {
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	231 return Ok(());
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 // 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	234 // 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	235 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	236 return Ok(());
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	237 }
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	238
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	239 // whatever happens, we'll keep at least keepcount of them
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	240 // knowing this gives us a earlier stop condition than
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	241 // 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	242 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	243
41717 9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	244 let mut curr = self.max_base;
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	245 while curr != NULL_REVISION && revs.len() > keepcount {
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	246 if self.bases.contains(&curr) {
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	247 revs.remove(&curr);
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	248 self.add_parents(curr)?;
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	249 }
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	250 curr -= 1;
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	251 }
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	252 Ok(())
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	253 }
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	254
41717 9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	255 /// 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	256 ///
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	257 /// This has no effect on `self.max_base`
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	258 #[inline]
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	259 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	260 if rev == NULL_REVISION {
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	261 return Ok(());
9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	262 }
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	263 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	264 // 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	265 // over
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	266 if p != NULL_REVISION {
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	267 self.bases.insert(p);
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	268 }
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 Ok(())
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	271 }
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	272
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	273 /// 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	274 ///
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	275 /// This may include elements from revs.
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	276 ///
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	277 /// 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	278 /// revision number order, which is a topological order.
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	279 pub fn missing_ancestors(
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	280 &mut self,
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	281 revs: impl IntoIterator<Item = Revision>,
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	282 ) -> Result<Vec<Revision>, GraphError> {
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	283 // just for convenience and comparison with Python version
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	284 let bases_visit = &mut self.bases;
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	285 let mut revs: HashSet<Revision> = revs
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	286 .into_iter()
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	287 .filter(\|r\| !bases_visit.contains(r))
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	288 .collect();
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	289 let revs_visit = &mut revs;
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	290 let mut both_visit: HashSet<Revision> =
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	291 revs_visit.intersection(&bases_visit).cloned().collect();
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	292 if revs_visit.is_empty() {
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	293 return Ok(Vec::new());
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	294 }
41717 9060af281be7 rust: itering less on MissingAncestors.bases for max() Georges Racinet <georges.racinet@octobus.net> parents: 41716 diff changeset	295 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	296 let start = max(self.max_base, max_revs);
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	297
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	298 // TODO heuristics for with_capacity()?
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	299 let mut missing: Vec<Revision> = Vec::new();
41104 247f51cfc668 rust: use .rev() for reverse range Yuya Nishihara <yuya@tcha.org> parents: 41054 diff changeset	300 for curr in (0..=start).rev() {
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	301 if revs_visit.is_empty() {
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	302 break;
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	303 }
41715 fccb61a1777b rust: less set lookups in MissingAncestors Georges Racinet <georges.racinet@octobus.net> parents: 41714 diff changeset	304 if both_visit.remove(&curr) {
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	305 // 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	306 // another path
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	307 for p in self.graph.parents(curr)?.iter().cloned() {
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	308 if p == NULL_REVISION {
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	309 continue;
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	310 }
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	311 revs_visit.remove(&p);
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	312 bases_visit.insert(p);
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	313 both_visit.insert(p);
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	314 }
41134 17a195676472 rust-ancestors: adjust branches and inline comments per previous change Yuya Nishihara <yuya@tcha.org> parents: 41133 diff changeset	315 } 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	316 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	317 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	318 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	319 continue;
486908e691be rust-ancestors: adjust indent level to make next change easier to follow Yuya Nishihara <yuya@tcha.org> parents: 41105 diff changeset	320 }
41715 fccb61a1777b rust: less set lookups in MissingAncestors Georges Racinet <georges.racinet@octobus.net> parents: 41714 diff changeset	321 if bases_visit.contains(&p) {
fccb61a1777b rust: less set lookups in MissingAncestors Georges Racinet <georges.racinet@octobus.net> parents: 41714 diff changeset	322 // 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	323 revs_visit.remove(&p);
fccb61a1777b rust: less set lookups in MissingAncestors Georges Racinet <georges.racinet@octobus.net> parents: 41714 diff changeset	324 both_visit.insert(p);
fccb61a1777b rust: less set lookups in MissingAncestors Georges Racinet <georges.racinet@octobus.net> parents: 41714 diff changeset	325 } else if both_visit.contains(&p) {
fccb61a1777b rust: less set lookups in MissingAncestors Georges Racinet <georges.racinet@octobus.net> parents: 41714 diff changeset	326 // 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	327 revs_visit.remove(&p);
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	328 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	329 } else {
486908e691be rust-ancestors: adjust indent level to make next change easier to follow Yuya Nishihara <yuya@tcha.org> parents: 41105 diff changeset	330 // visit later
41133 a1b3800c8a19 rust-ancestors: remove unreachable conditions from missing_ancestors() Yuya Nishihara <yuya@tcha.org> parents: 41132 diff changeset	331 revs_visit.insert(p);
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	332 }
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	333 }
41132 55dc1da8df2f rust-ancestors: duplicate loop that visits parents of revs/bases Yuya Nishihara <yuya@tcha.org> parents: 41131 diff changeset	334 } 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	335 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	336 if p == NULL_REVISION {
55dc1da8df2f rust-ancestors: duplicate loop that visits parents of revs/bases Yuya Nishihara <yuya@tcha.org> parents: 41131 diff changeset	337 continue;
55dc1da8df2f rust-ancestors: duplicate loop that visits parents of revs/bases Yuya Nishihara <yuya@tcha.org> parents: 41131 diff changeset	338 }
41715 fccb61a1777b rust: less set lookups in MissingAncestors Georges Racinet <georges.racinet@octobus.net> parents: 41714 diff changeset	339 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	340 // 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	341 // 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	342 bases_visit.insert(p);
55dc1da8df2f rust-ancestors: duplicate loop that visits parents of revs/bases Yuya Nishihara <yuya@tcha.org> parents: 41131 diff changeset	343 both_visit.insert(p);
55dc1da8df2f rust-ancestors: duplicate loop that visits parents of revs/bases Yuya Nishihara <yuya@tcha.org> parents: 41131 diff changeset	344 } else {
41133 a1b3800c8a19 rust-ancestors: remove unreachable conditions from missing_ancestors() Yuya Nishihara <yuya@tcha.org> parents: 41132 diff changeset	345 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	346 }
55dc1da8df2f rust-ancestors: duplicate loop that visits parents of revs/bases Yuya Nishihara <yuya@tcha.org> parents: 41131 diff changeset	347 }
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	348 }
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	349 }
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	350 missing.reverse();
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	351 Ok(missing)
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	352 }
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	353 }
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	354
40271 dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	355 #[cfg(test)]
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	356 mod tests {
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	357
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	358 use super::*;
41241 168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	359 use crate::testing::{SampleGraph, VecGraph};
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	360 use std::iter::FromIterator;
40271 dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	361
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	362 fn list_ancestors<G: Graph>(
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	363 graph: G,
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	364 initrevs: Vec<Revision>,
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	365 stoprev: Revision,
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	366 inclusive: bool,
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	367 ) -> Vec<Revision> {
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	368 AncestorsIterator::new(graph, initrevs, stoprev, inclusive)
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	369 .unwrap()
40929 43ca24b772d6 rust: adapted hg-core tests for iteration over Result Georges Racinet <gracinet@anybox.fr> parents: 40927 diff changeset	370 .map(\|res\| res.unwrap())
40271 dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	371 .collect()
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	372 }
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	373
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	374 #[test]
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	375 /// Same tests as test-ancestor.py, without membership
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	376 /// (see also test-ancestor.py.out)
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	377 fn test_list_ancestor() {
41241 168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	378 assert_eq!(list_ancestors(SampleGraph, vec![], 0, false), vec![]);
40271 dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	379 assert_eq!(
41241 168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	380 list_ancestors(SampleGraph, vec![11, 13], 0, false),
40271 dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	381 vec![8, 7, 4, 3, 2, 1, 0]
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	382 );
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	383 assert_eq!(
41241 168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	384 list_ancestors(SampleGraph, vec![1, 3], 0, false),
168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	385 vec![1, 0]
168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	386 );
168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	387 assert_eq!(
168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	388 list_ancestors(SampleGraph, vec![11, 13], 0, true),
40271 dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	389 vec![13, 11, 8, 7, 4, 3, 2, 1, 0]
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	390 );
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	391 assert_eq!(
41241 168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	392 list_ancestors(SampleGraph, vec![11, 13], 6, false),
168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	393 vec![8, 7]
168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	394 );
168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	395 assert_eq!(
168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	396 list_ancestors(SampleGraph, vec![11, 13], 6, true),
40271 dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	397 vec![13, 11, 8, 7]
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	398 );
41241 168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	399 assert_eq!(
168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	400 list_ancestors(SampleGraph, vec![11, 13], 11, true),
168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	401 vec![13, 11]
168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	402 );
40271 dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	403 assert_eq!(
41241 168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	404 list_ancestors(SampleGraph, vec![11, 13], 12, true),
168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	405 vec![13]
168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	406 );
168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	407 assert_eq!(
168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	408 list_ancestors(SampleGraph, vec![10, 1], 0, true),
40271 dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	409 vec![10, 5, 4, 2, 1, 0]
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	410 );
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	411 }
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	412
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	413 #[test]
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	414 /// 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	415 /// that happens quite often, as demonstrated by running the whole
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	416 /// suite.
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	417 /// For instance, run tests/test-obsolete-checkheads.t
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	418 fn test_nullrev_input() {
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	419 let mut iter =
41241 168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	420 AncestorsIterator::new(SampleGraph, vec![-1], 0, false).unwrap();
40271 dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	421 assert_eq!(iter.next(), None)
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	422 }
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	423
40300 72b94f946e90 rust: rustlazyancestors.__contains__ Georges Racinet <gracinet@anybox.fr> parents: 40271 diff changeset	424 #[test]
72b94f946e90 rust: rustlazyancestors.__contains__ Georges Racinet <gracinet@anybox.fr> parents: 40271 diff changeset	425 fn test_contains() {
72b94f946e90 rust: rustlazyancestors.__contains__ Georges Racinet <gracinet@anybox.fr> parents: 40271 diff changeset	426 let mut lazy =
41241 168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	427 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	428 assert!(lazy.contains(1).unwrap());
43ca24b772d6 rust: adapted hg-core tests for iteration over Result Georges Racinet <gracinet@anybox.fr> parents: 40927 diff changeset	429 assert!(!lazy.contains(3).unwrap());
40300 72b94f946e90 rust: rustlazyancestors.__contains__ Georges Racinet <gracinet@anybox.fr> parents: 40271 diff changeset	430
72b94f946e90 rust: rustlazyancestors.__contains__ Georges Racinet <gracinet@anybox.fr> parents: 40271 diff changeset	431 let mut lazy =
41241 168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	432 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	433 assert!(!lazy.contains(NULL_REVISION).unwrap());
40300 72b94f946e90 rust: rustlazyancestors.__contains__ Georges Racinet <gracinet@anybox.fr> parents: 40271 diff changeset	434 }
72b94f946e90 rust: rustlazyancestors.__contains__ Georges Racinet <gracinet@anybox.fr> parents: 40271 diff changeset	435
41054 ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	436 #[test]
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	437 fn test_peek() {
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	438 let mut iter =
41241 168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	439 AncestorsIterator::new(SampleGraph, vec![10], 0, true).unwrap();
41054 ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	440 // peek() gives us the next value
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	441 assert_eq!(iter.peek(), Some(10));
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	442 // but it's not been consumed
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	443 assert_eq!(iter.next(), Some(Ok(10)));
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	444 // and iteration resumes normally
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	445 assert_eq!(iter.next(), Some(Ok(5)));
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	446
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	447 // 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	448 while iter.next().is_some() {}
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	449 assert_eq!(iter.peek(), None);
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	450 }
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	451
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	452 #[test]
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	453 fn test_empty() {
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	454 let mut iter =
41241 168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	455 AncestorsIterator::new(SampleGraph, vec![10], 0, true).unwrap();
41054 ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	456 assert!(!iter.is_empty());
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	457 while iter.next().is_some() {}
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	458 assert!(!iter.is_empty());
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	459
41241 168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	460 let iter =
168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	461 AncestorsIterator::new(SampleGraph, vec![], 0, true).unwrap();
41054 ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	462 assert!(iter.is_empty());
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	463
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	464 // case where iter.seen == {NULL_REVISION}
41241 168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	465 let iter =
168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	466 AncestorsIterator::new(SampleGraph, vec![0], 0, false).unwrap();
41054 ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	467 assert!(iter.is_empty());
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	468 }
ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	469
40271 dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	470 /// A corrupted Graph, supporting error handling tests
41054 ef54bd33b476 rust: core implementation for lazyancestors Georges Racinet <gracinet@anybox.fr> parents: 40959 diff changeset	471 #[derive(Clone, Debug)]
40271 dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	472 struct Corrupted;
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	473
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	474 impl Graph for Corrupted {
40933 18513d6ef7d4 rust: changed Graph.parents to return [Revision; 2] Georges Racinet <gracinet@anybox.fr> parents: 40932 diff changeset	475 fn parents(&self, rev: Revision) -> Result<[Revision; 2], GraphError> {
40271 dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	476 match rev {
40933 18513d6ef7d4 rust: changed Graph.parents to return [Revision; 2] Georges Racinet <gracinet@anybox.fr> parents: 40932 diff changeset	477 1 => Ok([0, -1]),
40271 dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	478 r => Err(GraphError::ParentOutOfRange(r)),
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	479 }
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	480 }
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	481 }
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	482
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	483 #[test]
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	484 fn test_initrev_out_of_range() {
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	485 // 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	486 match AncestorsIterator::new(SampleGraph, vec![25], 0, false) {
40271 dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	487 Ok(_) => panic!("Should have been ParentOutOfRange"),
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	488 Err(e) => assert_eq!(e, GraphError::ParentOutOfRange(25)),
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	489 }
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	490 }
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	491
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	492 #[test]
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	493 fn test_next_out_of_range() {
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	494 // inclusive=false looks up initrev's parents right away
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	495 let mut iter =
dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	496 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	497 assert_eq!(iter.next(), Some(Err(GraphError::ParentOutOfRange(0))));
40271 dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	498 }
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	499
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	500 #[test]
41246 619ee4039bd4 rust: MissingAncestors.basesheads() Georges Racinet <georges.racinet@octobus.net> parents: 41241 diff changeset	501 /// Test constructor, add/get bases and heads
619ee4039bd4 rust: MissingAncestors.basesheads() Georges Racinet <georges.racinet@octobus.net> parents: 41241 diff changeset	502 fn test_missing_bases() -> Result<(), GraphError> {
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	503 let mut missing_ancestors =
41241 168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	504 MissingAncestors::new(SampleGraph, [5, 3, 1, 3].iter().cloned());
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	505 let mut as_vec: Vec<Revision> =
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	506 missing_ancestors.get_bases().iter().cloned().collect();
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	507 as_vec.sort();
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	508 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	509 assert_eq!(missing_ancestors.max_base, 5);
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	510
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	511 missing_ancestors.add_bases([3, 7, 8].iter().cloned());
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	512 as_vec = missing_ancestors.get_bases().iter().cloned().collect();
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	513 as_vec.sort();
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	514 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	515 assert_eq!(missing_ancestors.max_base, 8);
41246 619ee4039bd4 rust: MissingAncestors.basesheads() Georges Racinet <georges.racinet@octobus.net> parents: 41241 diff changeset	516
619ee4039bd4 rust: MissingAncestors.basesheads() Georges Racinet <georges.racinet@octobus.net> parents: 41241 diff changeset	517 as_vec = missing_ancestors.bases_heads()?.iter().cloned().collect();
619ee4039bd4 rust: MissingAncestors.basesheads() Georges Racinet <georges.racinet@octobus.net> parents: 41241 diff changeset	518 as_vec.sort();
619ee4039bd4 rust: MissingAncestors.basesheads() Georges Racinet <georges.racinet@octobus.net> parents: 41241 diff changeset	519 assert_eq!(as_vec, [3, 5, 7, 8]);
619ee4039bd4 rust: MissingAncestors.basesheads() Georges Racinet <georges.racinet@octobus.net> parents: 41241 diff changeset	520 Ok(())
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	521 }
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	522
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	523 fn assert_missing_remove(
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	524 bases: &[Revision],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	525 revs: &[Revision],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	526 expected: &[Revision],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	527 ) {
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	528 let mut missing_ancestors =
41241 168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	529 MissingAncestors::new(SampleGraph, bases.iter().cloned());
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	530 let mut revset: HashSet<Revision> = revs.iter().cloned().collect();
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	531 missing_ancestors
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	532 .remove_ancestors_from(&mut revset)
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	533 .unwrap();
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	534 let mut as_vec: Vec<Revision> = revset.into_iter().collect();
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	535 as_vec.sort();
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	536 assert_eq!(as_vec.as_slice(), expected);
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	537 }
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	538
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	539 #[test]
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	540 fn test_missing_remove() {
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	541 assert_missing_remove(
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	542 &[1, 2, 3, 4, 7],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	543 Vec::from_iter(1..10).as_slice(),
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	544 &[5, 6, 8, 9],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	545 );
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	546 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	547 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	548 }
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	549
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	550 fn assert_missing_ancestors(
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	551 bases: &[Revision],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	552 revs: &[Revision],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	553 expected: &[Revision],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	554 ) {
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	555 let mut missing_ancestors =
41241 168041fa6d5f rust: factorized testing Graphs Georges Racinet <georges.racinet@octobus.net> parents: 41134 diff changeset	556 MissingAncestors::new(SampleGraph, bases.iter().cloned());
40959 d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	557 let missing = missing_ancestors
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	558 .missing_ancestors(revs.iter().cloned())
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	559 .unwrap();
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	560 assert_eq!(missing.as_slice(), expected);
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	561 }
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	562
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	563 #[test]
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	564 fn test_missing_ancestors() {
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	565 // examples taken from test-ancestors.py by having it run
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	566 // on the same graph (both naive and fast Python algs)
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	567 assert_missing_ancestors(&[10], &[11], &[3, 7, 11]);
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	568 assert_missing_ancestors(&[11], &[10], &[5, 10]);
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	569 assert_missing_ancestors(&[7], &[9, 11], &[3, 6, 9, 11]);
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	570 }
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	571
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	572 /// An interesting case found by a random generator similar to
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	573 /// 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	574 /// 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	575 /// catched it.
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	576 #[test]
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	577 fn test_remove_ancestors_from_case1() {
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	578 let graph: VecGraph = vec![
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	579 [NULL_REVISION, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	580 [0, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	581 [1, 0],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	582 [2, 1],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	583 [3, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	584 [4, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	585 [5, 1],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	586 [2, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	587 [7, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	588 [8, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	589 [9, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	590 [10, 1],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	591 [3, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	592 [12, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	593 [13, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	594 [14, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	595 [4, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	596 [16, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	597 [17, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	598 [18, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	599 [19, 11],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	600 [20, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	601 [21, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	602 [22, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	603 [23, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	604 [2, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	605 [3, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	606 [26, 24],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	607 [27, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	608 [28, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	609 [12, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	610 [1, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	611 [1, 9],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	612 [32, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	613 [33, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	614 [34, 31],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	615 [35, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	616 [36, 26],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	617 [37, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	618 [38, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	619 [39, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	620 [40, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	621 [41, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	622 [42, 26],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	623 [0, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	624 [44, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	625 [45, 4],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	626 [40, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	627 [47, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	628 [36, 0],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	629 [49, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	630 [NULL_REVISION, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	631 [51, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	632 [52, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	633 [53, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	634 [14, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	635 [55, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	636 [15, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	637 [23, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	638 [58, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	639 [59, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	640 [2, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	641 [61, 59],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	642 [62, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	643 [63, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	644 [NULL_REVISION, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	645 [65, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	646 [66, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	647 [67, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	648 [68, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	649 [37, 28],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	650 [69, 25],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	651 [71, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	652 [72, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	653 [50, 2],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	654 [74, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	655 [12, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	656 [18, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	657 [77, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	658 [78, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	659 [79, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	660 [43, 33],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	661 [81, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	662 [82, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	663 [83, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	664 [84, 45],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	665 [85, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	666 [86, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	667 [NULL_REVISION, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	668 [88, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	669 [NULL_REVISION, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	670 [76, 83],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	671 [44, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	672 [92, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	673 [93, 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 [95, 67],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	676 [96, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	677 [97, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	678 [NULL_REVISION, NULL_REVISION],
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	679 ];
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	680 let problem_rev = 28 as Revision;
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	681 let problem_base = 70 as Revision;
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	682 // 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	683 assert_eq!(graph.parents(problem_base).unwrap()[1], problem_rev);
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	684
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	685 let mut missing_ancestors: MissingAncestors<VecGraph> =
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	686 MissingAncestors::new(
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	687 graph,
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	688 [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	689 .iter()
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	690 .cloned(),
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	691 );
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	692 assert!(missing_ancestors.bases.contains(&problem_base));
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	693
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	694 let mut revs: HashSet<Revision> =
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	695 [4, 12, 41, 28, 68, 38, 1, 30, 56, 44]
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	696 .iter()
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	697 .cloned()
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	698 .collect();
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	699 missing_ancestors.remove_ancestors_from(&mut revs).unwrap();
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	700 assert!(!revs.contains(&problem_rev));
d097dd0afc19 rust: translation of missingancestors Georges Racinet <gracinet@anybox.fr> parents: 40933 diff changeset	701 }
40271 dbc28c91f7ff rust: pure Rust lazyancestors iterator Georges Racinet <gracinet@anybox.fr> parents: diff changeset	702 }

Mercurial > public > mercurial-scm > hg

annotate rust/hg-core/src/ancestors.rs @ 48973:e2f8ed37201c stable