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

annotate rust/hg-core/src/discovery.rs @ 42744:c5748c6969b9

rust-discovery: optimization of add commons/missings for empty arguments These two cases have to be catched early for different reasons. In the case of add_missing_revisions, we don't want to trigger the computation of the undecided set (and the children cache) too early: the later the better. In the case of add_common_revisions, the inner `MissingAncestors` object wouldn't know that all ancestors of its bases have already been removed from the undecided. In principle, that would in itself be a lead for further improvement: this remove_ancestors_from could be more incremental, but the current performance seems to be good enough. Differential Revision: https://phab.mercurial-scm.org/D6429

author	Georges Racinet on percheron.racinet.fr <georges@racinet.fr>
date	Tue, 21 May 2019 12:46:38 +0200
parents	8c9a6adec67a
children	04c3b76fa7a3

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 extern crate rand;
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	14 extern crate rand_pcg;
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	15 use self::rand::seq::SliceRandom;
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	16 use self::rand::{thread_rng, RngCore, SeedableRng};
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	17 use super::{Graph, GraphError, Revision, NULL_REVISION};
42178 10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	18 use crate::ancestors::MissingAncestors;
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	19 use crate::dagops;
42738 8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	20 use std::cmp::{max, min};
42737 388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	21 use std::collections::{HashMap, HashSet, VecDeque};
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	22
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	23 type Rng = self::rand_pcg::Pcg32;
42178 10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	24
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	25 pub struct PartialDiscovery<G: Graph + Clone> {
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	26 target_heads: Option<Vec<Revision>>,
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	27 graph: G, // plays the role of self._repo
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	28 common: MissingAncestors<G>,
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	29 undecided: Option<HashSet<Revision>>,
42738 8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	30 children_cache: Option<HashMap<Revision, Vec<Revision>>>,
42178 10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	31 missing: HashSet<Revision>,
42737 388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	32 rng: Rng,
42738 8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	33 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	34 randomize: bool,
42178 10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	35 }
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	36
42180 1b0be75cb61f rust-discovery: implementing and exposing stats() Georges Racinet <georges.racinet@octobus.net> parents: 42178 diff changeset	37 pub struct DiscoveryStats {
1b0be75cb61f rust-discovery: implementing and exposing stats() Georges Racinet <georges.racinet@octobus.net> parents: 42178 diff changeset	38 pub undecided: Option<usize>,
1b0be75cb61f rust-discovery: implementing and exposing stats() Georges Racinet <georges.racinet@octobus.net> parents: 42178 diff changeset	39 }
1b0be75cb61f rust-discovery: implementing and exposing stats() Georges Racinet <georges.racinet@octobus.net> parents: 42178 diff changeset	40
42737 388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	41 /// 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	42 ///
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	43 /// 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	44 /// element of `heads`.
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	45 ///
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	46 /// 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	47 /// 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	48 /// reached.
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	49 ///
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	50 /// - `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	51 /// represented by `parentfn`
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	52 /// - `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	53 /// - `sample`: a sample to update
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	54 /// - `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	55 /// - `quicksamplesize`: optional target size of the sample
42738 8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	56 fn update_sample<I>(
42737 388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	57 revs: Option<&HashSet<Revision>>,
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	58 heads: impl IntoIterator<Item = Revision>,
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	59 sample: &mut HashSet<Revision>,
42738 8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	60 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	61 quicksamplesize: Option<usize>,
42738 8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	62 ) -> Result<(), GraphError>
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	63 where
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	64 I: Iterator<Item = Revision>,
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	65 {
42737 388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	66 let mut distances: HashMap<Revision, u32> = HashMap::new();
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	67 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	68 let mut factor: u32 = 1;
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	69 let mut seen: HashSet<Revision> = HashSet::new();
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	70 loop {
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	71 let current = match visit.pop_front() {
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	72 None => {
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	73 break;
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	74 }
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	75 Some(r) => r,
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 !seen.insert(current) {
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	78 continue;
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	79 }
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	80
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	81 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	82 if d > factor {
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	83 factor *= 2;
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	84 }
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	85 if d == factor {
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	86 sample.insert(current);
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	87 if let Some(sz) = quicksamplesize {
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	88 if sample.len() >= sz {
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	89 return Ok(());
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 }
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	92 }
42738 8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	93 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	94 if let Some(revs) = revs {
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	95 if !revs.contains(&p) {
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	96 continue;
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	97 }
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	98 }
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	99 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	100 visit.push_back(p);
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	101 }
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	102 }
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	103 Ok(())
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	104 }
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	105
42738 8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	106 struct ParentsIterator {
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	107 parents: [Revision; 2],
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	108 cur: usize,
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	109 }
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	110
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	111 impl ParentsIterator {
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	112 fn graph_parents(
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	113 graph: &impl Graph,
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	114 r: Revision,
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	115 ) -> Result<ParentsIterator, GraphError> {
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	116 Ok(ParentsIterator {
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	117 parents: graph.parents(r)?,
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	118 cur: 0,
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	119 })
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	120 }
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
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	123 impl Iterator for ParentsIterator {
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	124 type Item = Revision;
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	125
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	126 fn next(&mut self) -> Option<Revision> {
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	127 if self.cur > 1 {
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	128 return None;
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 let rev = self.parents[self.cur];
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	131 self.cur += 1;
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	132 if rev == NULL_REVISION {
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	133 return self.next();
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	134 }
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	135 Some(rev)
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	136 }
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	137 }
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	138
42178 10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	139 impl<G: Graph + Clone> PartialDiscovery<G> {
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	140 /// Create a PartialDiscovery object, with the intent
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	141 /// 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	142 /// repo.
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	143 ///
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	144 /// 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	145 /// at the first call to `ensure_undecided()`.
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	146 ///
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	147 /// If we want to make the signature more flexible,
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	148 /// 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	149 /// 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	150 ///
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	151 /// 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	152 /// 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	153 /// `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	154 /// 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	155 ///
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	156 /// 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	157 /// 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	158 ///
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	159 /// 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	160 /// 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	161 ///
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	162 /// 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	163 /// useful for integration tests.
42738 8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	164 pub fn new(
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	165 graph: G,
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	166 target_heads: Vec<Revision>,
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	167 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	168 randomize: bool,
42738 8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	169 ) -> Self {
42737 388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	170 let mut seed: [u8; 16] = [0; 16];
42741 4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	171 if randomize {
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	172 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	173 }
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	174 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	175 }
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	176
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	177 pub fn new_with_seed(
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	178 graph: G,
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	179 target_heads: Vec<Revision>,
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	180 seed: [u8; 16],
42738 8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	181 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	182 randomize: bool,
42737 388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	183 ) -> Self {
42178 10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	184 PartialDiscovery {
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	185 undecided: None,
42738 8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	186 children_cache: None,
42178 10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	187 target_heads: Some(target_heads),
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	188 graph: graph.clone(),
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	189 common: MissingAncestors::new(graph, vec![]),
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	190 missing: HashSet::new(),
42737 388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	191 rng: Rng::from_seed(seed),
42738 8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	192 respect_size: respect_size,
42741 4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	193 randomize: randomize,
42178 10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	194 }
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	195 }
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	196
42737 388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	197 /// 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	198 /// as a vector
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	199 fn limit_sample(
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	200 &mut self,
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	201 mut sample: Vec<Revision>,
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	202 size: usize,
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	203 ) -> Vec<Revision> {
42741 4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	204 if !self.randomize {
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	205 sample.sort();
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	206 sample.truncate(size);
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	207 return sample;
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	208 }
42737 388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	209 let sample_len = sample.len();
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	210 if sample_len <= size {
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	211 return sample;
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	212 }
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	213 let rng = &mut self.rng;
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	214 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	215 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	216 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	217 } else {
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	218 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	219 };
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	220 limited_slice.to_owned()
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	221 }
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	222
42178 10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	223 /// Register revisions known as being common
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	224 pub fn add_common_revisions(
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	225 &mut self,
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	226 common: impl IntoIterator<Item = Revision>,
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	227 ) -> 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	228 let before_len = self.common.get_bases().len();
42178 10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	229 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	230 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	231 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	232 }
42178 10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	233 if let Some(ref mut undecided) = self.undecided {
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	234 self.common.remove_ancestors_from(undecided)?;
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	235 }
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	236 Ok(())
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	237 }
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	238
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	239 /// 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	240 ///
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	241 /// # Performance note
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	242 ///
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	243 /// 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	244 /// 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	245 /// 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	246 /// 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	247 /// 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	248 /// caller should avoid calling this too early.
42178 10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	249 pub fn add_missing_revisions(
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	250 &mut self,
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	251 missing: impl IntoIterator<Item = Revision>,
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	252 ) -> 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	253 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	254 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	255 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	256 }
42743 8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	257 self.ensure_children_cache()?;
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	258 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	259 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	260 let mut seen: HashSet<Revision> = HashSet::new();
42178 10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	261 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	262 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	263 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	264 // 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	265 // 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	266 // 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	267 // 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	268 // 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	269 continue;
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	270 }
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	271 undecided_mut.remove(&rev);
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	272 match children.get(&rev) {
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	273 None => {
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	274 continue;
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	275 }
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	276 Some(this_children) => {
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	277 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	278 if seen.insert(child) {
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	279 tovisit.push_back(child);
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	280 }
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	281 }
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	282 }
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	283 }
42178 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 Ok(())
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	286 }
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	287
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	288 /// Do we have any information about the peer?
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	289 pub fn has_info(&self) -> bool {
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	290 self.common.has_bases()
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
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	293 /// 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	294 pub fn is_complete(&self) -> bool {
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	295 self.undecided.as_ref().map_or(false, \|s\| s.is_empty())
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	296 }
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 /// 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	299 ///
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	300 /// 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	301 /// 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	302 ///
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	303 /// 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	304 /// 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	305 ///
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	306 /// 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	307 /// 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	308 /// if it is complete.
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	309 pub fn common_heads(&self) -> Result<HashSet<Revision>, GraphError> {
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	310 self.common.bases_heads()
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	311 }
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	312
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	313 /// Force first computation of `self.undecided`
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	314 ///
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	315 /// 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	316 /// unwrapped to get workable immutable or mutable references without
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	317 /// any panic.
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 /// 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	320 /// 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	321 /// 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	322 /// as long as the resulting immutable one.
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	323 fn ensure_undecided(&mut self) -> Result<(), GraphError> {
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	324 if self.undecided.is_some() {
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	325 return Ok(());
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	326 }
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	327 let tgt = self.target_heads.take().unwrap();
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	328 self.undecided =
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	329 Some(self.common.missing_ancestors(tgt)?.into_iter().collect());
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	330 Ok(())
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	331 }
42180 1b0be75cb61f rust-discovery: implementing and exposing stats() Georges Racinet <georges.racinet@octobus.net> parents: 42178 diff changeset	332
42738 8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	333 fn ensure_children_cache(&mut self) -> Result<(), GraphError> {
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	334 if self.children_cache.is_some() {
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	335 return Ok(());
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 self.ensure_undecided()?;
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	338
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	339 let mut children: HashMap<Revision, Vec<Revision>> = HashMap::new();
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	340 for &rev in self.undecided.as_ref().unwrap() {
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	341 for p in ParentsIterator::graph_parents(&self.graph, rev)? {
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	342 children.entry(p).or_insert_with(\|\| Vec::new()).push(rev);
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	343 }
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	344 }
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	345 self.children_cache = Some(children);
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	346 Ok(())
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	347 }
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	348
42180 1b0be75cb61f rust-discovery: implementing and exposing stats() Georges Racinet <georges.racinet@octobus.net> parents: 42178 diff changeset	349 /// 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	350 pub fn stats(&self) -> DiscoveryStats {
1b0be75cb61f rust-discovery: implementing and exposing stats() Georges Racinet <georges.racinet@octobus.net> parents: 42178 diff changeset	351 DiscoveryStats {
1b0be75cb61f rust-discovery: implementing and exposing stats() Georges Racinet <georges.racinet@octobus.net> parents: 42178 diff changeset	352 undecided: self.undecided.as_ref().map(\|s\| s.len()),
1b0be75cb61f rust-discovery: implementing and exposing stats() Georges Racinet <georges.racinet@octobus.net> parents: 42178 diff changeset	353 }
1b0be75cb61f rust-discovery: implementing and exposing stats() Georges Racinet <georges.racinet@octobus.net> parents: 42178 diff changeset	354 }
42737 388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	355
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	356 pub fn take_quick_sample(
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	357 &mut self,
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	358 headrevs: impl IntoIterator<Item = Revision>,
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	359 size: usize,
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	360 ) -> Result<Vec<Revision>, GraphError> {
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	361 self.ensure_undecided()?;
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	362 let mut sample = {
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	363 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	364 if undecided.len() <= size {
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	365 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	366 }
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	367 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	368 };
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	369 if sample.len() >= size {
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	370 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	371 }
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	372 update_sample(
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	373 None,
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	374 headrevs,
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	375 &mut sample,
42738 8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	376 \|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	377 Some(size),
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	378 )?;
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	379 Ok(sample.into_iter().collect())
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	380 }
42738 8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	381
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	382 /// 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	383 ///
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	384 /// 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	385 /// 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	386 ///
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	387 /// 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	388 /// from the roots, working on the reverse DAG,
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	389 /// expressed by `self.children_cache`.
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	390 ///
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	391 /// 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	392 /// 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	393 /// 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	394 /// 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	395 fn bidirectional_sample(
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	396 &mut self,
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	397 size: usize,
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	398 ) -> Result<(HashSet<Revision>, usize), GraphError> {
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	399 self.ensure_undecided()?;
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 // 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	402 // 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	403 // 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	404 let undecided = self.undecided.as_ref().unwrap();
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	405 if undecided.len() <= size {
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	406 return Ok((undecided.clone(), size));
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	407 }
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	408 }
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	409
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	410 self.ensure_children_cache()?;
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	411 let revs = self.undecided.as_ref().unwrap();
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	412 let mut sample: HashSet<Revision> = revs.clone();
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	413
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	414 // 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	415 // efficient here
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	416 dagops::retain_heads(&self.graph, &mut sample)?;
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	417 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	418
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	419 // update from heads
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	420 update_sample(
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	421 Some(revs),
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	422 revsheads.iter().cloned(),
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	423 &mut sample,
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	424 \|r\| ParentsIterator::graph_parents(&self.graph, r),
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	425 None,
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	426 )?;
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	427
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	428 // update from roots
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	429 let revroots: HashSet<Revision> =
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	430 dagops::roots(&self.graph, revs)?.into_iter().collect();
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	431 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	432
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	433 let children = self.children_cache.as_ref().unwrap();
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	434 let empty_vec: Vec<Revision> = Vec::new();
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	435 update_sample(
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	436 Some(revs),
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	437 revroots,
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	438 &mut sample,
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	439 \|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	440 None,
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	441 )?;
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	442 Ok((sample, prescribed_size))
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	443 }
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	444
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	445 /// 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	446 ///
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	447 /// 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	448 /// regular sampling algorithm returns too few elements.
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	449 fn random_complete_sample(
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	450 &mut self,
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	451 sample: &mut Vec<Revision>,
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	452 size: usize,
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	453 ) {
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	454 let sample_len = sample.len();
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	455 if size <= sample_len {
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	456 return;
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	457 }
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	458 let take_from: Vec<Revision> = self
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	459 .undecided
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	460 .as_ref()
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	461 .unwrap()
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	462 .iter()
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	463 .filter(\|&r\| !sample.contains(r))
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	464 .cloned()
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	465 .collect();
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	466 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	467 }
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	468
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	469 pub fn take_full_sample(
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	470 &mut self,
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	471 size: usize,
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	472 ) -> Result<Vec<Revision>, GraphError> {
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	473 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	474 let size = if self.respect_size {
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	475 size
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	476 } else {
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	477 prescribed_size
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	478 };
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	479 let mut sample =
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	480 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	481 self.random_complete_sample(&mut sample, size);
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	482 Ok(sample)
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	483 }
42178 10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	484 }
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	485
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	486 #[cfg(test)]
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	487 mod tests {
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	488 use super::*;
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	489 use crate::testing::SampleGraph;
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	490
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	491 /// 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	492 ///
42741 4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	493 /// 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	494 /// 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	495 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	496 PartialDiscovery::new_with_seed(
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	497 SampleGraph,
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	498 vec![10, 11, 12, 13],
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	499 [0; 16],
42738 8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	500 true,
42741 4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	501 true,
42737 388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	502 )
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	503 }
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	504
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	505 /// 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	506 ///
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	507 /// 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	508 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	509 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	510 SampleGraph,
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	511 vec![12],
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	512 [0; 16],
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	513 true,
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	514 true,
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	515 )
42178 10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	516 }
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	517
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	518 fn sorted_undecided(
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	519 disco: &PartialDiscovery<SampleGraph>,
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	520 ) -> 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.undecided.as_ref().unwrap().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_missing(disco: &PartialDiscovery<SampleGraph>) -> Vec<Revision> {
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	528 let mut as_vec: Vec<Revision> =
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	529 disco.missing.iter().cloned().collect();
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	530 as_vec.sort();
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	531 as_vec
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	532 }
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	533
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	534 fn sorted_common_heads(
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	535 disco: &PartialDiscovery<SampleGraph>,
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	536 ) -> Result<Vec<Revision>, GraphError> {
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	537 let mut as_vec: Vec<Revision> =
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	538 disco.common_heads()?.iter().cloned().collect();
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	539 as_vec.sort();
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	540 Ok(as_vec)
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	541 }
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 #[test]
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	544 fn test_add_common_get_undecided() -> Result<(), GraphError> {
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	545 let mut disco = full_disco();
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	546 assert_eq!(disco.undecided, None);
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	547 assert!(!disco.has_info());
42180 1b0be75cb61f rust-discovery: implementing and exposing stats() Georges Racinet <georges.racinet@octobus.net> parents: 42178 diff changeset	548 assert_eq!(disco.stats().undecided, None);
42178 10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	549
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	550 disco.add_common_revisions(vec![11, 12])?;
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	551 assert!(disco.has_info());
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	552 assert!(!disco.is_complete());
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	553 assert!(disco.missing.is_empty());
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	554
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	555 // add_common_revisions did not trigger a premature computation
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	556 // 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	557 assert_eq!(disco.undecided, None);
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	558 disco.ensure_undecided()?;
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	559 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	560 assert_eq!(disco.stats().undecided, Some(4));
42178 10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	561 Ok(())
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	562 }
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	563
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	564 /// 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	565 /// 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	566 #[test]
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	567 fn test_discovery() -> Result<(), GraphError> {
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	568 let mut disco = full_disco();
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	569 disco.add_common_revisions(vec![11, 12])?;
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	570 disco.add_missing_revisions(vec![8, 10])?;
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	571 assert_eq!(sorted_undecided(&disco), vec![5]);
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	572 assert_eq!(sorted_missing(&disco), vec![8, 10, 13]);
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	573 assert!(!disco.is_complete());
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	574
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	575 disco.add_common_revisions(vec![5])?;
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	576 assert_eq!(sorted_undecided(&disco), vec![]);
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	577 assert_eq!(sorted_missing(&disco), vec![8, 10, 13]);
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	578 assert!(disco.is_complete());
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	579 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	580 Ok(())
10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	581 }
42737 388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	582
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	583 #[test]
42743 8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	584 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	585 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	586 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	587 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	588 disco.ensure_children_cache()?;
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	589 // 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	590 // 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	591 // 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	592 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	593 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	594 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	595 assert!(!disco.is_complete());
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	596 Ok(())
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	597 }
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	598
8c9a6adec67a rust-discovery: using the children cache in add_missing Georges Racinet <georges.racinet@octobus.net> parents: 42741 diff changeset	599 #[test]
42737 388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	600 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	601 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	602 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	603 }
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	604
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	605 #[test]
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	606 fn test_limit_sample_less_than_half() {
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	607 assert_eq!(full_disco().limit_sample((1..6).collect(), 2), vec![4, 2]);
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	608 }
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	609
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	610 #[test]
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	611 fn test_limit_sample_more_than_half() {
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	612 assert_eq!(full_disco().limit_sample((1..4).collect(), 2), vec![3, 2]);
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	613 }
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	614
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	615 #[test]
42741 4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	616 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	617 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	618 disco.randomize = false;
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	619 assert_eq!(
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	620 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	621 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	622 );
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	623 }
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	624
4e7bd6180b53 rust-discovery: optionally don't randomize at all, for tests Georges Racinet <georges.racinet@octobus.net> parents: 42738 diff changeset	625 #[test]
42737 388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	626 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	627 let mut disco = full_disco();
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	628 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	629
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	630 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	631 sample_vec.sort();
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	632 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	633 Ok(())
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	634 }
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	635
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	636 #[test]
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	637 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	638 let mut disco = disco12();
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	639 disco.ensure_undecided()?;
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	640
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	641 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	642 sample_vec.sort();
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	643 // 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	644 // 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	645 // 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	646 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	647 Ok(())
388622cbc911 rust-discovery: core implementation for take_quick_sample() Georges Racinet <georges.racinet@octobus.net> parents: 42180 diff changeset	648 }
42738 8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	649
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	650 #[test]
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	651 fn test_children_cache() -> Result<(), GraphError> {
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	652 let mut disco = full_disco();
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	653 disco.ensure_children_cache()?;
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	654
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	655 let cache = disco.children_cache.unwrap();
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	656 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	657 assert_eq!(cache.get(&10).cloned(), None);
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	658
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	659 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	660 children_4.sort();
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	661 assert_eq!(children_4, vec![5, 6, 7]);
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 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	664 children_7.sort();
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	665 assert_eq!(children_7, vec![9, 11]);
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	666
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	667 Ok(())
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	668 }
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 #[test]
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	671 fn test_complete_sample() {
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	672 let mut disco = full_disco();
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	673 let undecided: HashSet<Revision> =
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	674 [4, 7, 9, 2, 3].iter().cloned().collect();
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	675 disco.undecided = Some(undecided);
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	676
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	677 let mut sample = vec![0];
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	678 disco.random_complete_sample(&mut sample, 3);
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	679 assert_eq!(sample.len(), 3);
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	680
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	681 let mut sample = vec![2, 4, 7];
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	682 disco.random_complete_sample(&mut sample, 1);
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	683 assert_eq!(sample.len(), 3);
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	684 }
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	685
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	686 #[test]
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	687 fn test_bidirectional_sample() -> Result<(), GraphError> {
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	688 let mut disco = full_disco();
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	689 disco.undecided = Some((0..=13).into_iter().collect());
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	690
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	691 let (sample_set, size) = disco.bidirectional_sample(7)?;
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	692 assert_eq!(size, 7);
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	693 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	694 sample.sort();
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	695 // 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	696 // at least it shows that
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	697 // - we went both ways
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	698 // - 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	699 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	700 Ok(())
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	701 }
8041a1b45163 rust-discovery: takefullsample() core implementation Georges Racinet <georges.racinet@octobus.net> parents: 42737 diff changeset	702
42178 10b465d61556 rust-discovery: starting core implementation Georges Racinet <georges.racinet@octobus.net> parents: diff changeset	703 }

Mercurial > public > mercurial-scm > hg

annotate rust/hg-core/src/discovery.rs @ 42744:c5748c6969b9