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

annotate rust/hg-core/src/discovery.rs @ 46578:a34cd9aa3323

copies-rust: yield both p1 and p2 copies in `ChangedFiles.actions()` Instead of filtering the relevant parent inside de ChangedFiles method, we now yield all copies information and let the caller do the filtering. Soon, the filtering will be replaced by dispatching. Differential Revision: https://phab.mercurial-scm.org/D9649

author	Pierre-Yves David <pierre-yves.david@octobus.net>
date	Mon, 21 Dec 2020 10:24:16 +0100
parents	26114bd6ec60
children	e98fd81bb151

rev	line source
42178 10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	1 // discovery.rs
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	2 //
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	3 // Copyright 2019 Georges Racinet <georges.racinet@octobus.net>
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	4 //
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	5 // This software may be used and distributed according to the terms of the
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	6 // GNU General Public License version 2 or any later version.
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	7
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	8 //! Discovery operations
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	9 //!
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	10 //! This is a Rust counterpart to the `partialdiscovery` class of
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	11 //! `mercurial.setdiscovery`
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	12
42737 388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	13 use super::{Graph, GraphError, Revision, NULL_REVISION};
43826 5ac243a92e37 rust-performance: introduce FastHashMap type alias for HashMap Rapha?l Gom?s <rgomes@octobus.net> parents: 42841 diff changeset	14 use crate::{ancestors::MissingAncestors, dagops, FastHashMap};
42763 04c3b76fa7a3 rust-discovery: remove useless extern crate Yuya Nishihara <yuya@tcha.org> parents: 42744 diff changeset	15 use rand::seq::SliceRandom;
04c3b76fa7a3 rust-discovery: remove useless extern crate Yuya Nishihara <yuya@tcha.org> parents: 42744 diff changeset	16 use rand::{thread_rng, RngCore, SeedableRng};
42738 8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	17 use std::cmp::{max, min};
43826 5ac243a92e37 rust-performance: introduce FastHashMap type alias for HashMap Rapha?l Gom?s <rgomes@octobus.net> parents: 42841 diff changeset	18 use std::collections::{HashSet, VecDeque};
42737 388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	19
42763 04c3b76fa7a3 rust-discovery: remove useless extern crate Yuya Nishihara <yuya@tcha.org> parents: 42744 diff changeset	20 type Rng = rand_pcg::Pcg32;
44042 2abffea40700 rust-discovery: type alias for random generator seed Georges Racinet <georges.racinet@octobus.net> parents: 43826 diff changeset	21 type Seed = [u8; 16];
42178 10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	22
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	23 pub struct PartialDiscovery<G: Graph + Clone> {
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	24 target_heads: Option<Vec<Revision>>,
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	25 graph: G, // plays the role of self._repo
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	26 common: MissingAncestors<G>,
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	27 undecided: Option<HashSet<Revision>>,
43826 5ac243a92e37 rust-performance: introduce FastHashMap type alias for HashMap Rapha?l Gom?s <rgomes@octobus.net> parents: 42841 diff changeset	28 children_cache: Option<FastHashMap<Revision, Vec<Revision>>>,
42178 10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	29 missing: HashSet<Revision>,
42737 388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	30 rng: Rng,
42738 8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	31 respect_size: bool,
42741 4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	32 randomize: bool,
42178 10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	33 }
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	34
42180 1b0be75cb61f rust-discovery: implementing and exposing stats() Georges Racinet <georges.racinet@octobus.net> parents: 42178 diff changeset	35 pub struct DiscoveryStats {
1b0be75cb61f rust-discovery: implementing and exposing stats() Georges Racinet <georges.racinet@octobus.net> parents: 42178 diff changeset	36 pub undecided: Option<usize>,
1b0be75cb61f rust-discovery: implementing and exposing stats() Georges Racinet <georges.racinet@octobus.net> parents: 42178 diff changeset	37 }
1b0be75cb61f rust-discovery: implementing and exposing stats() Georges Racinet <georges.racinet@octobus.net> parents: 42178 diff changeset	38
42737 388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	39 /// Update an existing sample to match the expected size
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	40 ///
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	41 /// The sample is updated with revisions exponentially distant from each
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	42 /// element of `heads`.
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	43 ///
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	44 /// If a target size is specified, the sampling will stop once this size is
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	45 /// reached. Otherwise sampling will happen until roots of the <revs> set are
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	46 /// reached.
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	47 ///
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	48 /// - `revs`: set of revs we want to discover (if None, `assume` the whole dag
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	49 /// represented by `parentfn`
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	50 /// - `heads`: set of DAG head revs
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	51 /// - `sample`: a sample to update
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	52 /// - `parentfn`: a callable to resolve parents for a revision
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	53 /// - `quicksamplesize`: optional target size of the sample
42738 8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	54 fn update_sample<I>(
42737 388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	55 revs: Option<&HashSet<Revision>>,
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	56 heads: impl IntoIterator<Item = Revision>,
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	57 sample: &mut HashSet<Revision>,
42738 8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	58 parentsfn: impl Fn(Revision) -> Result<I, GraphError>,
42737 388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	59 quicksamplesize: Option<usize>,
42738 8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	60 ) -> Result<(), GraphError>
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	61 where
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	62 I: Iterator<Item = Revision>,
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	63 {
43826 5ac243a92e37 rust-performance: introduce FastHashMap type alias for HashMap Rapha?l Gom?s <rgomes@octobus.net> parents: 42841 diff changeset	64 let mut distances: FastHashMap<Revision, u32> = FastHashMap::default();
42737 388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	65 let mut visit: VecDeque<Revision> = heads.into_iter().collect();
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	66 let mut factor: u32 = 1;
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	67 let mut seen: HashSet<Revision> = HashSet::new();
42764 798b7d4b463e rust-discovery: use while loop instead of match + break Yuya Nishihara <yuya@tcha.org> parents: 42763 diff changeset	68 while let Some(current) = visit.pop_front() {
42737 388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	69 if !seen.insert(current) {
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	70 continue;
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	71 }
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	72
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	73 let d = *distances.entry(current).or_insert(1);
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	74 if d > factor {
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	75 factor *= 2;
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	76 }
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	77 if d == factor {
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	78 sample.insert(current);
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	79 if let Some(sz) = quicksamplesize {
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	80 if sample.len() >= sz {
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	81 return Ok(());
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	82 }
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	83 }
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	84 }
42738 8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	85 for p in parentsfn(current)? {
42737 388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	86 if let Some(revs) = revs {
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	87 if !revs.contains(&p) {
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	88 continue;
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	89 }
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	90 }
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	91 distances.entry(p).or_insert(d + 1);
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	92 visit.push_back(p);
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	93 }
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	94 }
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	95 Ok(())
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	96 }
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	97
42738 8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	98 struct ParentsIterator {
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	99 parents: [Revision; 2],
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	100 cur: usize,
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	101 }
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	102
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	103 impl ParentsIterator {
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	104 fn graph_parents(
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	105 graph: &impl Graph,
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	106 r: Revision,
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	107 ) -> Result<ParentsIterator, GraphError> {
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	108 Ok(ParentsIterator {
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	109 parents: graph.parents(r)?,
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	110 cur: 0,
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	111 })
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	112 }
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	113 }
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	114
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	115 impl Iterator for ParentsIterator {
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	116 type Item = Revision;
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	117
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	118 fn next(&mut self) -> Option<Revision> {
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	119 if self.cur > 1 {
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	120 return None;
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	121 }
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	122 let rev = self.parents[self.cur];
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	123 self.cur += 1;
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	124 if rev == NULL_REVISION {
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	125 return self.next();
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	126 }
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	127 Some(rev)
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	128 }
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	129 }
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	130
42178 10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	131 impl<G: Graph + Clone> PartialDiscovery<G> {
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	132 /// Create a PartialDiscovery object, with the intent
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	133 /// of comparing our `::<target_heads>` revset to the contents of another
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	134 /// repo.
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	135 ///
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	136 /// For now `target_heads` is passed as a vector, and will be used
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	137 /// at the first call to `ensure_undecided()`.
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	138 ///
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	139 /// If we want to make the signature more flexible,
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	140 /// we'll have to make it a type argument of `PartialDiscovery` or a trait
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	141 /// object since we'll keep it in the meanwhile
42738 8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	142 ///
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	143 /// The `respect_size` boolean controls how the sampling methods
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	144 /// will interpret the size argument requested by the caller. If it's
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	145 /// `false`, they are allowed to produce a sample whose size is more
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	146 /// appropriate to the situation (typically bigger).
42741 4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	147 ///
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	148 /// The `randomize` boolean affects sampling, and specifically how
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	149 /// limiting or last-minute expanding is been done:
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	150 ///
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	151 /// If `true`, both will perform random picking from `self.undecided`.
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	152 /// This is currently the best for actual discoveries.
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	153 ///
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	154 /// If `false`, a reproductible picking strategy is performed. This is
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	155 /// useful for integration tests.
42738 8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	156 pub fn new(
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	157 graph: G,
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	158 target_heads: Vec<Revision>,
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	159 respect_size: bool,
42741 4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	160 randomize: bool,
42738 8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	161 ) -> Self {
44042 2abffea40700 rust-discovery: type alias for random generator seed Georges Racinet <georges.racinet@octobus.net> parents: 43826 diff changeset	162 let mut seed = [0; 16];
42741 4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	163 if randomize {
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	164 thread_rng().fill_bytes(&mut seed);
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	165 }
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	166 Self::new_with_seed(graph, target_heads, seed, respect_size, randomize)
42737 388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	167 }
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	168
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	169 pub fn new_with_seed(
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	170 graph: G,
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	171 target_heads: Vec<Revision>,
44042 2abffea40700 rust-discovery: type alias for random generator seed Georges Racinet <georges.racinet@octobus.net> parents: 43826 diff changeset	172 seed: Seed,
42738 8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	173 respect_size: bool,
42741 4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	174 randomize: bool,
42737 388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	175 ) -> Self {
42178 10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	176 PartialDiscovery {
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	177 undecided: None,
42738 8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	178 children_cache: None,
42178 10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	179 target_heads: Some(target_heads),
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	180 graph: graph.clone(),
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	181 common: MissingAncestors::new(graph, vec![]),
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	182 missing: HashSet::new(),
42737 388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	183 rng: Rng::from_seed(seed),
44973 26114bd6ec60 rust: do a clippy pass Rapha?l Gom?s <rgomes@octobus.net> parents: 44599 diff changeset	184 respect_size,
26114bd6ec60 rust: do a clippy pass Rapha?l Gom?s <rgomes@octobus.net> parents: 44599 diff changeset	185 randomize,
42178 10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	186 }
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	187 }
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	188
42737 388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	189 /// Extract at most `size` random elements from sample and return them
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	190 /// as a vector
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	191 fn limit_sample(
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	192 &mut self,
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	193 mut sample: Vec<Revision>,
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	194 size: usize,
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	195 ) -> Vec<Revision> {
42741 4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	196 if !self.randomize {
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	197 sample.sort();
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	198 sample.truncate(size);
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	199 return sample;
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	200 }
42737 388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	201 let sample_len = sample.len();
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	202 if sample_len <= size {
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	203 return sample;
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	204 }
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	205 let rng = &mut self.rng;
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	206 let dropped_size = sample_len - size;
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	207 let limited_slice = if size < dropped_size {
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	208 sample.partial_shuffle(rng, size).0
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	209 } else {
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	210 sample.partial_shuffle(rng, dropped_size).1
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	211 };
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	212 limited_slice.to_owned()
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	213 }
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	214
42178 10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	215 /// Register revisions known as being common
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	216 pub fn add_common_revisions(
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	217 &mut self,
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	218 common: impl IntoIterator<Item = Revision>,
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	219 ) -> Result<(), GraphError> {
42744 c5748c6969b9 rust-discovery: optimization of add commons/missings for empty arguments Georges Racinet on percheron.racinet.fr <georges@racinet.fr> parents: 42743 diff changeset	220 let before_len = self.common.get_bases().len();
42178 10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	221 self.common.add_bases(common);
42744 c5748c6969b9 rust-discovery: optimization of add commons/missings for empty arguments Georges Racinet on percheron.racinet.fr <georges@racinet.fr> parents: 42743 diff changeset	222 if self.common.get_bases().len() == before_len {
c5748c6969b9 rust-discovery: optimization of add commons/missings for empty arguments Georges Racinet on percheron.racinet.fr <georges@racinet.fr> parents: 42743 diff changeset	223 return Ok(());
c5748c6969b9 rust-discovery: optimization of add commons/missings for empty arguments Georges Racinet on percheron.racinet.fr <georges@racinet.fr> parents: 42743 diff changeset	224 }
42178 10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	225 if let Some(ref mut undecided) = self.undecided {
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	226 self.common.remove_ancestors_from(undecided)?;
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	227 }
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	228 Ok(())
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	229 }
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	230
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	231 /// Register revisions known as being missing
42743 8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	232 ///
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	233 /// # Performance note
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	234 ///
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	235 /// Except in the most trivial case, the first call of this method has
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	236 /// the side effect of computing `self.undecided` set for the first time,
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	237 /// and the related caches it might need for efficiency of its internal
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	238 /// computation. This is typically faster if more information is
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	239 /// available in `self.common`. Therefore, for good performance, the
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	240 /// caller should avoid calling this too early.
42178 10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	241 pub fn add_missing_revisions(
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	242 &mut self,
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	243 missing: impl IntoIterator<Item = Revision>,
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	244 ) -> Result<(), GraphError> {
42744 c5748c6969b9 rust-discovery: optimization of add commons/missings for empty arguments Georges Racinet on percheron.racinet.fr <georges@racinet.fr> parents: 42743 diff changeset	245 let mut tovisit: VecDeque<Revision> = missing.into_iter().collect();
c5748c6969b9 rust-discovery: optimization of add commons/missings for empty arguments Georges Racinet on percheron.racinet.fr <georges@racinet.fr> parents: 42743 diff changeset	246 if tovisit.is_empty() {
c5748c6969b9 rust-discovery: optimization of add commons/missings for empty arguments Georges Racinet on percheron.racinet.fr <georges@racinet.fr> parents: 42743 diff changeset	247 return Ok(());
c5748c6969b9 rust-discovery: optimization of add commons/missings for empty arguments Georges Racinet on percheron.racinet.fr <georges@racinet.fr> parents: 42743 diff changeset	248 }
42743 8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	249 self.ensure_children_cache()?;
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	250 self.ensure_undecided()?; // for safety of possible future refactors
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	251 let children = self.children_cache.as_ref().unwrap();
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	252 let mut seen: HashSet<Revision> = HashSet::new();
42178 10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	253 let undecided_mut = self.undecided.as_mut().unwrap();
42743 8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	254 while let Some(rev) = tovisit.pop_front() {
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	255 if !self.missing.insert(rev) {
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	256 // either it's known to be missing from a previous
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	257 // invocation, and there's no need to iterate on its
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	258 // children (we now they are all missing)
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	259 // or it's from a previous iteration of this loop
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	260 // and its children have already been queued
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	261 continue;
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	262 }
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	263 undecided_mut.remove(&rev);
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	264 match children.get(&rev) {
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	265 None => {
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	266 continue;
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	267 }
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	268 Some(this_children) => {
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	269 for child in this_children.iter().cloned() {
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	270 if seen.insert(child) {
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	271 tovisit.push_back(child);
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	272 }
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	273 }
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	274 }
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	275 }
42178 10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	276 }
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	277 Ok(())
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	278 }
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	279
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	280 /// Do we have any information about the peer?
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	281 pub fn has_info(&self) -> bool {
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	282 self.common.has_bases()
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	283 }
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	284
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	285 /// Did we acquire full knowledge of our Revisions that the peer has?
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	286 pub fn is_complete(&self) -> bool {
44973 26114bd6ec60 rust: do a clippy pass Rapha?l Gom?s <rgomes@octobus.net> parents: 44599 diff changeset	287 self.undecided.as_ref().map_or(false, HashSet::is_empty)
42178 10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	288 }
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	289
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	290 /// Return the heads of the currently known common set of revisions.
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	291 ///
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	292 /// If the discovery process is not complete (see `is_complete()`), the
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	293 /// caller must be aware that this is an intermediate state.
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	294 ///
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	295 /// On the other hand, if it is complete, then this is currently
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	296 /// the only way to retrieve the end results of the discovery process.
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	297 ///
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	298 /// We may introduce in the future an `into_common_heads` call that
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	299 /// would be more appropriate for normal Rust callers, dropping `self`
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	300 /// if it is complete.
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	301 pub fn common_heads(&self) -> Result<HashSet<Revision>, GraphError> {
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	302 self.common.bases_heads()
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	303 }
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	304
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	305 /// Force first computation of `self.undecided`
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	306 ///
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	307 /// After this, `self.undecided.as_ref()` and `.as_mut()` can be
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	308 /// unwrapped to get workable immutable or mutable references without
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	309 /// any panic.
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	310 ///
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	311 /// This is an imperative call instead of an access with added lazyness
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	312 /// to reduce easily the scope of mutable borrow for the caller,
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	313 /// compared to undecided(&'a mut self) -> &'a… that would keep it
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	314 /// as long as the resulting immutable one.
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	315 fn ensure_undecided(&mut self) -> Result<(), GraphError> {
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	316 if self.undecided.is_some() {
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	317 return Ok(());
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	318 }
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	319 let tgt = self.target_heads.take().unwrap();
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	320 self.undecided =
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	321 Some(self.common.missing_ancestors(tgt)?.into_iter().collect());
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	322 Ok(())
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	323 }
42180 1b0be75cb61f rust-discovery: implementing and exposing stats() Georges Racinet <georges.racinet@octobus.net> parents: 42178 diff changeset	324
42738 8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	325 fn ensure_children_cache(&mut self) -> Result<(), GraphError> {
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	326 if self.children_cache.is_some() {
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	327 return Ok(());
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	328 }
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	329 self.ensure_undecided()?;
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	330
43826 5ac243a92e37 rust-performance: introduce FastHashMap type alias for HashMap Rapha?l Gom?s <rgomes@octobus.net> parents: 42841 diff changeset	331 let mut children: FastHashMap<Revision, Vec<Revision>> =
5ac243a92e37 rust-performance: introduce FastHashMap type alias for HashMap Rapha?l Gom?s <rgomes@octobus.net> parents: 42841 diff changeset	332 FastHashMap::default();
42738 8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	333 for &rev in self.undecided.as_ref().unwrap() {
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	334 for p in ParentsIterator::graph_parents(&self.graph, rev)? {
44973 26114bd6ec60 rust: do a clippy pass Rapha?l Gom?s <rgomes@octobus.net> parents: 44599 diff changeset	335 children.entry(p).or_insert_with(Vec::new).push(rev);
42738 8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	336 }
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	337 }
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	338 self.children_cache = Some(children);
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	339 Ok(())
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	340 }
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	341
42180 1b0be75cb61f rust-discovery: implementing and exposing stats() Georges Racinet <georges.racinet@octobus.net> parents: 42178 diff changeset	342 /// Provide statistics about the current state of the discovery process
1b0be75cb61f rust-discovery: implementing and exposing stats() Georges Racinet <georges.racinet@octobus.net> parents: 42178 diff changeset	343 pub fn stats(&self) -> DiscoveryStats {
1b0be75cb61f rust-discovery: implementing and exposing stats() Georges Racinet <georges.racinet@octobus.net> parents: 42178 diff changeset	344 DiscoveryStats {
44973 26114bd6ec60 rust: do a clippy pass Rapha?l Gom?s <rgomes@octobus.net> parents: 44599 diff changeset	345 undecided: self.undecided.as_ref().map(HashSet::len),
42180 1b0be75cb61f rust-discovery: implementing and exposing stats() Georges Racinet <georges.racinet@octobus.net> parents: 42178 diff changeset	346 }
1b0be75cb61f rust-discovery: implementing and exposing stats() Georges Racinet <georges.racinet@octobus.net> parents: 42178 diff changeset	347 }
42737 388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	348
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	349 pub fn take_quick_sample(
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	350 &mut self,
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	351 headrevs: impl IntoIterator<Item = Revision>,
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	352 size: usize,
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	353 ) -> Result<Vec<Revision>, GraphError> {
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	354 self.ensure_undecided()?;
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	355 let mut sample = {
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	356 let undecided = self.undecided.as_ref().unwrap();
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	357 if undecided.len() <= size {
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	358 return Ok(undecided.iter().cloned().collect());
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	359 }
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	360 dagops::heads(&self.graph, undecided.iter())?
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	361 };
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	362 if sample.len() >= size {
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	363 return Ok(self.limit_sample(sample.into_iter().collect(), size));
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	364 }
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	365 update_sample(
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	366 None,
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	367 headrevs,
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	368 &mut sample,
42738 8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	369 \|r\| ParentsIterator::graph_parents(&self.graph, r),
42737 388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	370 Some(size),
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	371 )?;
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	372 Ok(sample.into_iter().collect())
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	373 }
42738 8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	374
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	375 /// Extract a sample from `self.undecided`, going from its heads and roots.
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	376 ///
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	377 /// The `size` parameter is used to avoid useless computations if
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	378 /// it turns out to be bigger than the whole set of undecided Revisions.
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	379 ///
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	380 /// The sample is taken by using `update_sample` from the heads, then
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	381 /// from the roots, working on the reverse DAG,
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	382 /// expressed by `self.children_cache`.
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	383 ///
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	384 /// No effort is being made to complete or limit the sample to `size`
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	385 /// but this method returns another interesting size that it derives
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	386 /// from its knowledge of the structure of the various sets, leaving
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	387 /// to the caller the decision to use it or not.
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	388 fn bidirectional_sample(
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	389 &mut self,
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	390 size: usize,
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	391 ) -> Result<(HashSet<Revision>, usize), GraphError> {
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	392 self.ensure_undecided()?;
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	393 {
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	394 // we don't want to compute children_cache before this
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	395 // but doing it after extracting self.undecided takes a mutable
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	396 // ref to self while a shareable one is still active.
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	397 let undecided = self.undecided.as_ref().unwrap();
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	398 if undecided.len() <= size {
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	399 return Ok((undecided.clone(), size));
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	400 }
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	401 }
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	402
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	403 self.ensure_children_cache()?;
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	404 let revs = self.undecided.as_ref().unwrap();
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	405 let mut sample: HashSet<Revision> = revs.clone();
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	406
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	407 // it's possible that leveraging the children cache would be more
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	408 // efficient here
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	409 dagops::retain_heads(&self.graph, &mut sample)?;
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	410 let revsheads = sample.clone(); // was again heads(revs) in python
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	411
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	412 // update from heads
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	413 update_sample(
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	414 Some(revs),
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	415 revsheads.iter().cloned(),
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	416 &mut sample,
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	417 \|r\| ParentsIterator::graph_parents(&self.graph, r),
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	418 None,
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	419 )?;
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	420
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	421 // update from roots
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	422 let revroots: HashSet<Revision> =
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	423 dagops::roots(&self.graph, revs)?.into_iter().collect();
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	424 let prescribed_size = max(size, min(revroots.len(), revsheads.len()));
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	425
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	426 let children = self.children_cache.as_ref().unwrap();
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	427 let empty_vec: Vec<Revision> = Vec::new();
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	428 update_sample(
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	429 Some(revs),
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	430 revroots,
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	431 &mut sample,
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	432 \|r\| Ok(children.get(&r).unwrap_or(&empty_vec).iter().cloned()),
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	433 None,
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	434 )?;
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	435 Ok((sample, prescribed_size))
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	436 }
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	437
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	438 /// Fill up sample up to the wished size with random undecided Revisions.
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	439 ///
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	440 /// This is intended to be used as a last resort completion if the
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	441 /// regular sampling algorithm returns too few elements.
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	442 fn random_complete_sample(
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	443 &mut self,
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	444 sample: &mut Vec<Revision>,
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	445 size: usize,
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	446 ) {
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	447 let sample_len = sample.len();
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	448 if size <= sample_len {
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	449 return;
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	450 }
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	451 let take_from: Vec<Revision> = self
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	452 .undecided
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	453 .as_ref()
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	454 .unwrap()
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	455 .iter()
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	456 .filter(\|&r\| !sample.contains(r))
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	457 .cloned()
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	458 .collect();
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	459 sample.extend(self.limit_sample(take_from, size - sample_len));
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	460 }
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	461
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	462 pub fn take_full_sample(
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	463 &mut self,
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	464 size: usize,
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	465 ) -> Result<Vec<Revision>, GraphError> {
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	466 let (sample_set, prescribed_size) = self.bidirectional_sample(size)?;
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	467 let size = if self.respect_size {
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	468 size
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	469 } else {
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	470 prescribed_size
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	471 };
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	472 let mut sample =
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	473 self.limit_sample(sample_set.into_iter().collect(), size);
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	474 self.random_complete_sample(&mut sample, size);
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	475 Ok(sample)
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	476 }
42178 10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	477 }
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	478
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	479 #[cfg(test)]
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	480 mod tests {
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	481 use super::*;
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	482 use crate::testing::SampleGraph;
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	483
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	484 /// A PartialDiscovery as for pushing all the heads of `SampleGraph`
42737 388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	485 ///
42741 4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	486 /// To avoid actual randomness in these tests, we give it a fixed
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	487 /// random seed, but by default we'll test the random version.
42178 10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	488 fn full_disco() -> PartialDiscovery<SampleGraph> {
42737 388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	489 PartialDiscovery::new_with_seed(
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	490 SampleGraph,
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	491 vec![10, 11, 12, 13],
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	492 [0; 16],
42738 8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	493 true,
42741 4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	494 true,
42737 388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	495 )
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	496 }
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	497
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	498 /// A PartialDiscovery as for pushing the 12 head of `SampleGraph`
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	499 ///
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	500 /// To avoid actual randomness in tests, we give it a fixed random seed.
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	501 fn disco12() -> PartialDiscovery<SampleGraph> {
42741 4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	502 PartialDiscovery::new_with_seed(
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	503 SampleGraph,
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	504 vec![12],
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	505 [0; 16],
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	506 true,
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	507 true,
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	508 )
42178 10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	509 }
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	510
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	511 fn sorted_undecided(
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	512 disco: &PartialDiscovery<SampleGraph>,
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	513 ) -> Vec<Revision> {
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	514 let mut as_vec: Vec<Revision> =
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	515 disco.undecided.as_ref().unwrap().iter().cloned().collect();
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	516 as_vec.sort();
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	517 as_vec
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	518 }
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	519
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	520 fn sorted_missing(disco: &PartialDiscovery<SampleGraph>) -> Vec<Revision> {
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	521 let mut as_vec: Vec<Revision> =
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	522 disco.missing.iter().cloned().collect();
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	523 as_vec.sort();
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	524 as_vec
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	525 }
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	526
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	527 fn sorted_common_heads(
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	528 disco: &PartialDiscovery<SampleGraph>,
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	529 ) -> Result<Vec<Revision>, GraphError> {
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	530 let mut as_vec: Vec<Revision> =
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	531 disco.common_heads()?.iter().cloned().collect();
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	532 as_vec.sort();
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	533 Ok(as_vec)
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	534 }
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	535
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	536 #[test]
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	537 fn test_add_common_get_undecided() -> Result<(), GraphError> {
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	538 let mut disco = full_disco();
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	539 assert_eq!(disco.undecided, None);
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	540 assert!(!disco.has_info());
42180 1b0be75cb61f rust-discovery: implementing and exposing stats() Georges Racinet <georges.racinet@octobus.net> parents: 42178 diff changeset	541 assert_eq!(disco.stats().undecided, None);
42178 10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	542
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	543 disco.add_common_revisions(vec![11, 12])?;
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	544 assert!(disco.has_info());
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	545 assert!(!disco.is_complete());
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	546 assert!(disco.missing.is_empty());
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	547
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	548 // add_common_revisions did not trigger a premature computation
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	549 // of `undecided`, let's check that and ask for them
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	550 assert_eq!(disco.undecided, None);
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	551 disco.ensure_undecided()?;
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	552 assert_eq!(sorted_undecided(&disco), vec![5, 8, 10, 13]);
42180 1b0be75cb61f rust-discovery: implementing and exposing stats() Georges Racinet <georges.racinet@octobus.net> parents: 42178 diff changeset	553 assert_eq!(disco.stats().undecided, Some(4));
42178 10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	554 Ok(())
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	555 }
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	556
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	557 /// in this test, we pretend that our peer misses exactly (8+10)::
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	558 /// and we're comparing all our repo to it (as in a bare push)
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	559 #[test]
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	560 fn test_discovery() -> Result<(), GraphError> {
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	561 let mut disco = full_disco();
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	562 disco.add_common_revisions(vec![11, 12])?;
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	563 disco.add_missing_revisions(vec![8, 10])?;
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	564 assert_eq!(sorted_undecided(&disco), vec![5]);
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	565 assert_eq!(sorted_missing(&disco), vec![8, 10, 13]);
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	566 assert!(!disco.is_complete());
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	567
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	568 disco.add_common_revisions(vec![5])?;
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	569 assert_eq!(sorted_undecided(&disco), vec![]);
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	570 assert_eq!(sorted_missing(&disco), vec![8, 10, 13]);
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	571 assert!(disco.is_complete());
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	572 assert_eq!(sorted_common_heads(&disco)?, vec![5, 11, 12]);
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	573 Ok(())
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	574 }
42737 388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	575
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	576 #[test]
42743 8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	577 fn test_add_missing_early_continue() -> Result<(), GraphError> {
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	578 eprintln!("test_add_missing_early_stop");
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	579 let mut disco = full_disco();
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	580 disco.add_common_revisions(vec![13, 3, 4])?;
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	581 disco.ensure_children_cache()?;
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	582 // 12 is grand-child of 6 through 9
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	583 // passing them in this order maximizes the chances of the
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	584 // early continue to do the wrong thing
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	585 disco.add_missing_revisions(vec![6, 9, 12])?;
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	586 assert_eq!(sorted_undecided(&disco), vec![5, 7, 10, 11]);
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	587 assert_eq!(sorted_missing(&disco), vec![6, 9, 12]);
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	588 assert!(!disco.is_complete());
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	589 Ok(())
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	590 }
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	591
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	592 #[test]
42737 388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	593 fn test_limit_sample_no_need_to() {
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	594 let sample = vec![1, 2, 3, 4];
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	595 assert_eq!(full_disco().limit_sample(sample, 10), vec![1, 2, 3, 4]);
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	596 }
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	597
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	598 #[test]
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	599 fn test_limit_sample_less_than_half() {
44599 d31d1c0685be rust: update all dependencies Rapha?l Gom?s <rgomes@octobus.net> parents: 44042 diff changeset	600 assert_eq!(full_disco().limit_sample((1..6).collect(), 2), vec![2, 5]);
42737 388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	601 }
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	602
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	603 #[test]
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	604 fn test_limit_sample_more_than_half() {
44599 d31d1c0685be rust: update all dependencies Rapha?l Gom?s <rgomes@octobus.net> parents: 44042 diff changeset	605 assert_eq!(full_disco().limit_sample((1..4).collect(), 2), vec![1, 2]);
42737 388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	606 }
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	607
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	608 #[test]
42741 4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	609 fn test_limit_sample_no_random() {
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	610 let mut disco = full_disco();
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	611 disco.randomize = false;
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	612 assert_eq!(
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	613 disco.limit_sample(vec![1, 8, 13, 5, 7, 3], 4),
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	614 vec![1, 3, 5, 7]
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	615 );
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	616 }
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	617
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	618 #[test]
42737 388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	619 fn test_quick_sample_enough_undecided_heads() -> Result<(), GraphError> {
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	620 let mut disco = full_disco();
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	621 disco.undecided = Some((1..=13).collect());
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	622
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	623 let mut sample_vec = disco.take_quick_sample(vec![], 4)?;
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	624 sample_vec.sort();
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	625 assert_eq!(sample_vec, vec![10, 11, 12, 13]);
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	626 Ok(())
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	627 }
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	628
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	629 #[test]
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	630 fn test_quick_sample_climbing_from_12() -> Result<(), GraphError> {
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	631 let mut disco = disco12();
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	632 disco.ensure_undecided()?;
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	633
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	634 let mut sample_vec = disco.take_quick_sample(vec![12], 4)?;
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	635 sample_vec.sort();
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	636 // r12's only parent is r9, whose unique grand-parent through the
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	637 // diamond shape is r4. This ends there because the distance from r4
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	638 // to the root is only 3.
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	639 assert_eq!(sample_vec, vec![4, 9, 12]);
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	640 Ok(())
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	641 }
42738 8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	642
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	643 #[test]
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	644 fn test_children_cache() -> Result<(), GraphError> {
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	645 let mut disco = full_disco();
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	646 disco.ensure_children_cache()?;
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	647
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	648 let cache = disco.children_cache.unwrap();
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	649 assert_eq!(cache.get(&2).cloned(), Some(vec![4]));
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	650 assert_eq!(cache.get(&10).cloned(), None);
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	651
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	652 let mut children_4 = cache.get(&4).cloned().unwrap();
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	653 children_4.sort();
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	654 assert_eq!(children_4, vec![5, 6, 7]);
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	655
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	656 let mut children_7 = cache.get(&7).cloned().unwrap();
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	657 children_7.sort();
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	658 assert_eq!(children_7, vec![9, 11]);
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	659
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	660 Ok(())
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	661 }
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	662
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	663 #[test]
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	664 fn test_complete_sample() {
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	665 let mut disco = full_disco();
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	666 let undecided: HashSet<Revision> =
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	667 [4, 7, 9, 2, 3].iter().cloned().collect();
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	668 disco.undecided = Some(undecided);
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	669
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	670 let mut sample = vec![0];
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	671 disco.random_complete_sample(&mut sample, 3);
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	672 assert_eq!(sample.len(), 3);
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	673
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	674 let mut sample = vec![2, 4, 7];
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	675 disco.random_complete_sample(&mut sample, 1);
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	676 assert_eq!(sample.len(), 3);
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	677 }
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	678
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	679 #[test]
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	680 fn test_bidirectional_sample() -> Result<(), GraphError> {
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	681 let mut disco = full_disco();
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	682 disco.undecided = Some((0..=13).into_iter().collect());
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	683
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	684 let (sample_set, size) = disco.bidirectional_sample(7)?;
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	685 assert_eq!(size, 7);
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	686 let mut sample: Vec<Revision> = sample_set.into_iter().collect();
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	687 sample.sort();
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	688 // our DAG is a bit too small for the results to be really interesting
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	689 // at least it shows that
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	690 // - we went both ways
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	691 // - we didn't take all Revisions (6 is not in the sample)
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	692 assert_eq!(sample, vec![0, 1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 12, 13]);
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	693 Ok(())
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	694 }
42178 10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	695 }

Mercurial > public > mercurial-scm > hg

annotate rust/hg-core/src/discovery.rs @ 46578:a34cd9aa3323