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