Mercurial > public > mercurial-scm > hg

annotate rust/hg-core/src/discovery.rs @ 43881:b5655f337bd7

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