11961978007

Committed 21 Nov 2024 09:29PM UTC coverage: 68.045% (-21.7%) from 89.696%

Build # 11961978007

Build Type

Pull #239

github

Committed by

web-flow

Commit Message

Merge ef39de3b0 into 178a48f80

Pull Request Pull Request #239: [WIP] [Refactor] 3: Switch legacy to coordinator

Run Details

146 of 504 new or added lines in 13 files covered. (28.97%)

52 existing lines in 4 files now uncovered.

1761 of 2588 relevant lines covered (68.04%)

2189.37 hits per line

Source File
Press 'n' to go to next uncovered line, 'b' for previous

94.09

/crates/shared/src/coordinator/tiered_view_map.rs

//! This module contains an optimizide implementation of a
//! [`BuilderStateId`] to [`BuilderState`] map.

use std::{
    collections::{btree_map::Entry, BTreeMap},
    hash::Hash,
    ops::RangeBounds,
};

use hotshot_types::{
    traits::node_implementation::{ConsensusTime, NodeType},
    utils::BuilderCommitment,
    vid::VidCommitment,
};
use nonempty_collections::{nem, NEMap};

use crate::block::{BlockId, BuilderStateId};

/// A map from [`ViewCompositeKey`] to arbitrary value, implemented as a tiered map
/// with the first tier being [`BTreeMap`] keyed by view number of [`ViewCompositeKey`]
/// and the second [`NEMap`] keyed by subkey of [`ViewCompositeKey`].
///
/// Usage of [`BTreeMap`] means that the map has an convenient property of always being
/// sorted by view number, which makes common operations such as pruning old views more efficient.
///
/// Second tier being non-empty by construction [`NEMap`] ensures that we can't accidentally
/// create phantom entries with empty maps in the first tier.
#[derive(Debug)]
pub struct TieredViewMap<K, V>(BTreeMap<K::View, NEMap<K::Subkey, V>>)
where
    K: ViewCompositeKey;

/// A two-component key, of which one component is [`ConsensusTime`]
///
/// See [`TieredViewMap`] documentation for more information
pub trait ViewCompositeKey {
    type Subkey: Hash + Eq;
    type View: ConsensusTime;
    fn view(&self) -> &Self::View;
    fn subkey(&self) -> &Self::Subkey;
    fn into_subkey(self) -> Self::Subkey;
}

impl<Types: NodeType> ViewCompositeKey for BlockId<Types> {
    type Subkey = BuilderCommitment;
    type View = Types::View;

    fn view(&self) -> &<Types as NodeType>::View {
        &self.view
    }

    fn subkey(&self) -> &Self::Subkey {
        &self.hash
    }

    fn into_subkey(self) -> Self::Subkey {
        self.hash
    }
}

impl<Types: NodeType> ViewCompositeKey for BuilderStateId<Types> {
    type Subkey = VidCommitment;
    type View = Types::View;

    fn view(&self) -> &<Types as NodeType>::View {
        &self.parent_view
    }

    fn subkey(&self) -> &Self::Subkey {
        &self.parent_commitment
    }

    fn into_subkey(self) -> Self::Subkey {
        self.parent_commitment
    }
}

impl<K, V> TieredViewMap<K, V>
where
    K: ViewCompositeKey,
{
    /// Create a new empty map
    pub fn new() -> Self {
        Self(BTreeMap::new())
    }

    /// Returns an iterator visiting all values in this map
    pub fn values(&self) -> impl Iterator<Item = &V> {
        self.0
            .values()
            .flat_map(|bucket| bucket.values().into_iter())
    }

    /// Returns a nested iterator visiting all [`BuilderState`]s for view numbers in given range
    pub fn range<R>(&self, range: R) -> impl Iterator<Item = impl Iterator<Item = &V>>
    where
        R: RangeBounds<K::View>,
    {
        self.0
            .range(range)
            .map(|(_, bucket)| bucket.values().into_iter())
    }

    /// Returns an iterator visiting all [`BuilderState`]s for given view number
    pub fn bucket(&self, view_number: &K::View) -> impl Iterator<Item = &V> {
        self.0
            .get(view_number)
            .into_iter()
            .flat_map(|bucket| bucket.values().into_iter())
    }

    /// Returns the number of builder states stored
    pub fn len(&self) -> usize {
        self.0.values().map(|bucket| bucket.len().get()).sum()
    }

    /// Returns whether this map is empty
    pub fn is_empty(&self) -> bool {
        self.0.len() == 0
    }

    /// Get builder state by ID
    pub fn get(&self, key: &K) -> Option<&V> {
        self.0.get(key.view())?.get(key.subkey())
    }

    /// Get builder state by ID
    pub fn get_mut(&mut self, key: &K) -> Option<&mut V> {
        self.0.get_mut(key.view())?.get_mut(key.subkey())
    }

    /// Get highest view builder state
    ///
    /// Returns `None` if the map is empty
    pub fn highest_view_builder(&self) -> Option<&V> {
        Some(&self.0.last_key_value()?.1.head_val)
    }

    /// Insert a new builder state
    pub fn insert(&mut self, key: K, value: V) {
        match self.0.entry(*key.view()) {
            Entry::Vacant(entry) => {
                entry.insert(nem![key.into_subkey() => value]);
            }
            Entry::Occupied(mut entry) => {
                entry.get_mut().insert(key.into_subkey(), value);
            }
        }
    }

    /// Returns highest view number for which we have a builder state
    pub fn highest_view(&self) -> Option<K::View> {
        Some(*self.0.last_key_value()?.0)
    }

    /// Returns lowest view number for which we have a builder state
    pub fn lowest_view(&self) -> Option<K::View> {
        Some(*self.0.first_key_value()?.0)
    }

    /// Removes every view lower than the `cutoff_view` (exclusive) from self and returns all removed views.
    pub fn prune(&mut self, cutoff_view: K::View) -> Self {
        let high = self.0.split_off(&cutoff_view);
        let low = std::mem::replace(&mut self.0, high);
        Self(low)
    }
}

impl<K, V> Default for TieredViewMap<K, V>
where
    K: ViewCompositeKey,
{
    fn default() -> Self {
        Self::new()
    }
}

#[cfg(test)]
mod tests {
    use std::{cmp::Ordering, ops::Bound, sync::Arc};

    use crate::{state::BuilderState, testing::mock};

    use super::*;
    use hotshot_example_types::node_types::TestTypes;
    use hotshot_types::{data::ViewNumber, traits::node_implementation::ConsensusTime};
    use rand::{distributions::Standard, thread_rng, Rng};

    type View = ViewNumber;
    type BuilderStateMap =
        super::TieredViewMap<BuilderStateId<TestTypes>, Arc<BuilderState<TestTypes>>>;

    #[test]
    fn test_new_map() {
        let new_map = BuilderStateMap::new();
        assert!(new_map.is_empty());
        assert_eq!(new_map.len(), 0);

        let default_map = BuilderStateMap::default();
        assert!(default_map.is_empty());
        assert_eq!(default_map.len(), 0);
    }

    #[test]
    fn test_insert_and_get() {
        let mut map = BuilderStateMap::new();

        let builder_state = mock::builder_state(1);
        let state_id = builder_state.id();

        map.insert(state_id.clone(), Arc::clone(&builder_state));

        assert!(!map.is_empty());
        assert_eq!(map.len(), 1);
        assert!(Arc::ptr_eq(map.get(&state_id).unwrap(), &builder_state));
    }

    #[test]
    fn test_range_iteration() {
        let mut map = BuilderStateMap::new();

        for i in 0..5 {
            let builder_state = mock::builder_state(i);
            map.insert(builder_state.id(), builder_state);
        }

        let start = View::new(1);
        let end = View::new(3);

        let collected: Vec<_> = map
            .range((Bound::Included(start), Bound::Excluded(end)))
            .flatten()
            .collect();

        assert_eq!(collected.len(), 2);
        assert_eq!(*collected[0].parent_block_references.view_number, 1);
        assert_eq!(*collected[1].parent_block_references.view_number, 2);
    }

    #[test]
    fn test_pruning() {
        let view_count = 11;
        let states_per_view = 13;
        let cutoff = 7;

        let mut map = BuilderStateMap::new();

        for view in 0..view_count {
            for _ in 0..states_per_view {
                let state = mock::builder_state(view);
                map.insert(state.id(), state);
            }
        }

        let pruned_map = map.prune(View::new(cutoff));
        assert_eq!(pruned_map.len() as u64, cutoff * states_per_view);
        assert_eq!(map.len() as u64, (view_count - cutoff) * states_per_view);

        assert!(pruned_map.bucket(&View::new(cutoff - 1)).next().is_some());
        assert!(map.bucket(&View::new(cutoff)).next().is_some());

        assert!(pruned_map.bucket(&View::new(cutoff)).next().is_none());
        assert!(map.bucket(&View::new(cutoff - 1)).next().is_none());
    }

    #[test]
    fn test_highest_and_lowest_view() {
        let mut map = BuilderStateMap::new();
        assert_eq!(map.highest_view(), None);
        assert_eq!(map.lowest_view(), None);

        for i in 3..13 {
            let state = mock::builder_state(i);
            map.insert(state.id(), state);
        }

        assert_eq!(*map.highest_view().unwrap(), 12);
        assert_eq!(*map.lowest_view().unwrap(), 3);
    }

    #[test]
    fn test_highest_view_builder() {
        let mut map = BuilderStateMap::new();
        assert!(map.highest_view_builder().is_none());

        let mut states: Vec<_> = thread_rng()
            .sample_iter(Standard)
            .take(100)
            .map(mock::builder_state)
            .collect();

        for state in states.iter() {
            map.insert(state.id(), Arc::clone(state));
        }

        states.sort_by(|a, b| {
            a.parent_block_references
                .view_number
                .cmp(&b.parent_block_references.view_number)
        });

        assert_eq!(
            map.highest_view_builder()
                .unwrap()
                .parent_block_references
                .view_number,
            states.last().unwrap().parent_block_references.view_number
        );
    }

    #[test]
    fn test_iterator() {
        let mut map = BuilderStateMap::new();

        let mut states: Vec<_> = thread_rng()
            .sample_iter(Standard)
            .take(100)
            .map(mock::builder_state)
            .collect();
        assert_eq!(states.len(), 100);

        for state in states.iter() {
            map.insert(state.id(), Arc::clone(state));
        }

        states.sort_by(compare_builders);

        let mut map_states = map.values().cloned().collect::<Vec<_>>();
        map_states.sort_by(compare_builders);

        for (original_state, map_state) in states.into_iter().zip(map_states) {
            assert!(Arc::ptr_eq(&original_state, &map_state));
        }
    }

    fn compare_builders(
        a: &Arc<BuilderState<TestTypes>>,
        b: &Arc<BuilderState<TestTypes>>,
    ) -> Ordering {
        a.parent_block_references
            .view_number
            .cmp(&b.parent_block_references.view_number)
            .then(
                a.parent_block_references
                    .vid_commitment
                    .cmp(&b.parent_block_references.vid_commitment),
            )
    }
}

1	//! This module contains an optimizide implementation of a
2	//! [`BuilderStateId`] to [`BuilderState`] map.
3
4	use std::{
5	collections::{btree_map::Entry, BTreeMap},
6	hash::Hash,
7	ops::RangeBounds,
8	};
9
10	use hotshot_types::{
11	traits::node_implementation::{ConsensusTime, NodeType},
12	utils::BuilderCommitment,
13	vid::VidCommitment,
14	};
15	use nonempty_collections::{nem, NEMap};
16
17	use crate::block::{BlockId, BuilderStateId};
18
19	/// A map from [`ViewCompositeKey`] to arbitrary value, implemented as a tiered map
20	/// with the first tier being [`BTreeMap`] keyed by view number of [`ViewCompositeKey`]
21	/// and the second [`NEMap`] keyed by subkey of [`ViewCompositeKey`].
22	///
23	/// Usage of [`BTreeMap`] means that the map has an convenient property of always being
24	/// sorted by view number, which makes common operations such as pruning old views more efficient.
25	///
26	/// Second tier being non-empty by construction [`NEMap`] ensures that we can't accidentally
27	/// create phantom entries with empty maps in the first tier.
28	#[derive(Debug)]
29	pub struct TieredViewMap<K, V>(BTreeMap<K::View, NEMap<K::Subkey, V>>)
30	where
31	K: ViewCompositeKey;
32
33	/// A two-component key, of which one component is [`ConsensusTime`]
34	///
35	/// See [`TieredViewMap`] documentation for more information
36	pub trait ViewCompositeKey {
37	type Subkey: Hash + Eq;
38	type View: ConsensusTime;
39	fn view(&self) -> &Self::View;
40	fn subkey(&self) -> &Self::Subkey;
41	fn into_subkey(self) -> Self::Subkey;
42	}
43
44	impl<Types: NodeType> ViewCompositeKey for BlockId<Types> {
45	type Subkey = BuilderCommitment;
46	type View = Types::View;
47
NEW 48	fn view(&self) -> &<Types as NodeType>::View {	×
NEW 49	&self.view	×
NEW 50	}	×
51
NEW 52	fn subkey(&self) -> &Self::Subkey {	×
NEW 53	&self.hash	×
NEW 54	}	×
55
NEW 56	fn into_subkey(self) -> Self::Subkey {	×
NEW 57	self.hash	×
NEW 58	}	×
59	}
60
61	impl<Types: NodeType> ViewCompositeKey for BuilderStateId<Types> {
62	type Subkey = VidCommitment;
63	type View = Types::View;
64
65	fn view(&self) -> &<Types as NodeType>::View {	698✔
66	&self.parent_view	698✔
67	}	698✔
68
69	fn subkey(&self) -> &Self::Subkey {	47✔
70	&self.parent_commitment	47✔
71	}	47✔
72
73	fn into_subkey(self) -> Self::Subkey {	504✔
74	self.parent_commitment	504✔
75	}	504✔
76	}
77
78	impl<K, V> TieredViewMap<K, V>
79	where
80	K: ViewCompositeKey,
81	{
82	/// Create a new empty map
83	pub fn new() -> Self {	19✔
84	Self(BTreeMap::new())	19✔
85	}	19✔
86
87	/// Returns an iterator visiting all values in this map
88	pub fn values(&self) -> impl Iterator<Item = &V> {	1✔
89	self.0	1✔
90	.values()	1✔
91	.flat_map(\|bucket\| bucket.values().into_iter())	100✔
92	}	1✔
93
94	/// Returns a nested iterator visiting all [`BuilderState`]s for view numbers in given range
95	pub fn range<R>(&self, range: R) -> impl Iterator<Item = impl Iterator<Item = &V>>	108✔
96	where	108✔
97	R: RangeBounds<K::View>,	108✔
98	{	108✔
99	self.0	108✔
100	.range(range)	108✔
101	.map(\|(_, bucket)\| bucket.values().into_iter())	108✔
102	}	108✔
103
104	/// Returns an iterator visiting all [`BuilderState`]s for given view number
105	pub fn bucket(&self, view_number: &K::View) -> impl Iterator<Item = &V> {	138✔
106	self.0	138✔
107	.get(view_number)	138✔
108	.into_iter()	138✔
109	.flat_map(\|bucket\| bucket.values().into_iter())	138✔
110	}	138✔
111
112	/// Returns the number of builder states stored
113	pub fn len(&self) -> usize {	17✔
114	self.0.values().map(\|bucket\| bucket.len().get()).sum()	127✔
115	}	17✔
116
117	/// Returns whether this map is empty
118	pub fn is_empty(&self) -> bool {	3✔
119	self.0.len() == 0	3✔
120	}	3✔
121
122	/// Get builder state by ID
123	pub fn get(&self, key: &K) -> Option<&V> {	194✔
124	self.0.get(key.view())?.get(key.subkey())	194✔
125	}	194✔
126
127	/// Get builder state by ID
NEW 128	pub fn get_mut(&mut self, key: &K) -> Option<&mut V> {	×
NEW 129	self.0.get_mut(key.view())?.get_mut(key.subkey())	×
130	}	×
131
132	/// Get highest view builder state
133	///
134	/// Returns `None` if the map is empty
135	pub fn highest_view_builder(&self) -> Option<&V> {	10✔
136	Some(&self.0.last_key_value()?.1.head_val)	10✔
137	}	10✔
138
139	/// Insert a new builder state
140	pub fn insert(&mut self, key: K, value: V) {	504✔
141	match self.0.entry(*key.view()) {	504✔
142	Entry::Vacant(entry) => {	364✔
143	entry.insert(nem![key.into_subkey() => value]);	364✔
144	}	364✔
145	Entry::Occupied(mut entry) => {	140✔
146	entry.get_mut().insert(key.into_subkey(), value);	140✔
147	}	140✔
148	}
149	}	504✔
150
151	/// Returns highest view number for which we have a builder state
152	pub fn highest_view(&self) -> Option<K::View> {	4✔
153	Some(*self.0.last_key_value()?.0)	4✔
154	}	4✔
155
156	/// Returns lowest view number for which we have a builder state
157	pub fn lowest_view(&self) -> Option<K::View> {	26✔
158	Some(*self.0.first_key_value()?.0)	26✔
159	}	26✔
160
161	/// Removes every view lower than the `cutoff_view` (exclusive) from self and returns all removed views.
162	pub fn prune(&mut self, cutoff_view: K::View) -> Self {	3✔
163	let high = self.0.split_off(&cutoff_view);	3✔
164	let low = std::mem::replace(&mut self.0, high);	3✔
165	Self(low)	3✔
166	}	3✔
167	}
168
169	impl<K, V> Default for TieredViewMap<K, V>
170	where
171	K: ViewCompositeKey,
172	{
173	fn default() -> Self {	1✔
174	Self::new()	1✔
175	}	1✔
176	}
177
178	#[cfg(test)]
179	mod tests {
180	use std::{cmp::Ordering, ops::Bound, sync::Arc};
181
182	use crate::{state::BuilderState, testing::mock};
183
184	use super::*;
185	use hotshot_example_types::node_types::TestTypes;
186	use hotshot_types::{data::ViewNumber, traits::node_implementation::ConsensusTime};
187	use rand::{distributions::Standard, thread_rng, Rng};
188
189	type View = ViewNumber;
190	type BuilderStateMap =
191	super::TieredViewMap<BuilderStateId<TestTypes>, Arc<BuilderState<TestTypes>>>;
192
193	#[test]
194	fn test_new_map() {	1✔
195	let new_map = BuilderStateMap::new();	1✔
196	assert!(new_map.is_empty());	1✔
197	assert_eq!(new_map.len(), 0);	1✔
198
199	let default_map = BuilderStateMap::default();	1✔
200	assert!(default_map.is_empty());	1✔
201	assert_eq!(default_map.len(), 0);	1✔
202	}	1✔
203
204	#[test]
205	fn test_insert_and_get() {	1✔
206	let mut map = BuilderStateMap::new();	1✔
207		1✔
208	let builder_state = mock::builder_state(1);	1✔
209	let state_id = builder_state.id();	1✔
210		1✔
211	map.insert(state_id.clone(), Arc::clone(&builder_state));	1✔
212		1✔
213	assert!(!map.is_empty());	1✔
214	assert_eq!(map.len(), 1);	1✔
215	assert!(Arc::ptr_eq(map.get(&state_id).unwrap(), &builder_state));	1✔
216	}	1✔
217
218	#[test]
219	fn test_range_iteration() {	1✔
220	let mut map = BuilderStateMap::new();	1✔
221
222	for i in 0..5 {	6✔
223	let builder_state = mock::builder_state(i);	5✔
224	map.insert(builder_state.id(), builder_state);	5✔
225	}	5✔
226
227	let start = View::new(1);	1✔
228	let end = View::new(3);	1✔
229		1✔
230	let collected: Vec<_> = map	1✔
231	.range((Bound::Included(start), Bound::Excluded(end)))	1✔
232	.flatten()	1✔
233	.collect();	1✔
234		1✔
235	assert_eq!(collected.len(), 2);	1✔
236	assert_eq!(*collected[0].parent_block_references.view_number, 1);	1✔
237	assert_eq!(*collected[1].parent_block_references.view_number, 2);	1✔
238	}	1✔
239
240	#[test]
241	fn test_pruning() {	1✔
242	let view_count = 11;	1✔
243	let states_per_view = 13;	1✔
244	let cutoff = 7;	1✔
245		1✔
246	let mut map = BuilderStateMap::new();	1✔
247
248	for view in 0..view_count {	11✔
249	for _ in 0..states_per_view {	143✔
250	let state = mock::builder_state(view);	143✔
251	map.insert(state.id(), state);	143✔
252	}	143✔
253	}
254
255	let pruned_map = map.prune(View::new(cutoff));	1✔
256	assert_eq!(pruned_map.len() as u64, cutoff * states_per_view);	1✔
257	assert_eq!(map.len() as u64, (view_count - cutoff) * states_per_view);	1✔
258
259	assert!(pruned_map.bucket(&View::new(cutoff - 1)).next().is_some());	1✔
260	assert!(map.bucket(&View::new(cutoff)).next().is_some());	1✔
261
262	assert!(pruned_map.bucket(&View::new(cutoff)).next().is_none());	1✔
263	assert!(map.bucket(&View::new(cutoff - 1)).next().is_none());	1✔
264	}	1✔
265
266	#[test]
267	fn test_highest_and_lowest_view() {	1✔
268	let mut map = BuilderStateMap::new();	1✔
269	assert_eq!(map.highest_view(), None);	1✔
270	assert_eq!(map.lowest_view(), None);	1✔
271
272	for i in 3..13 {	11✔
273	let state = mock::builder_state(i);	10✔
274	map.insert(state.id(), state);	10✔
275	}	10✔
276
277	assert_eq!(*map.highest_view().unwrap(), 12);	1✔
278	assert_eq!(*map.lowest_view().unwrap(), 3);	1✔
279	}	1✔
280
281	#[test]
282	fn test_highest_view_builder() {	1✔
283	let mut map = BuilderStateMap::new();	1✔
284	assert!(map.highest_view_builder().is_none());	1✔
285
286	let mut states: Vec<_> = thread_rng()	1✔
287	.sample_iter(Standard)	1✔
288	.take(100)	1✔
289	.map(mock::builder_state)	1✔
290	.collect();	1✔
291
292	for state in states.iter() {	100✔
293	map.insert(state.id(), Arc::clone(state));	100✔
294	}	100✔
295
296	states.sort_by(\|a, b\| {	709✔
297	a.parent_block_references	709✔
298	.view_number	709✔
299	.cmp(&b.parent_block_references.view_number)	709✔
300	});	709✔
301		1✔
302	assert_eq!(	1✔
303	map.highest_view_builder()	1✔
304	.unwrap()	1✔
305	.parent_block_references	1✔
306	.view_number,	1✔
307	states.last().unwrap().parent_block_references.view_number	1✔
308	);	1✔
309	}	1✔
310
311	#[test]
312	fn test_iterator() {	1✔
313	let mut map = BuilderStateMap::new();	1✔
314		1✔
315	let mut states: Vec<_> = thread_rng()	1✔
316	.sample_iter(Standard)	1✔
317	.take(100)	1✔
318	.map(mock::builder_state)	1✔
319	.collect();	1✔
320	assert_eq!(states.len(), 100);	1✔
321
322	for state in states.iter() {	100✔
323	map.insert(state.id(), Arc::clone(state));	100✔
324	}	100✔
325
326	states.sort_by(compare_builders);	1✔
327		1✔
328	let mut map_states = map.values().cloned().collect::<Vec<_>>();	1✔
329	map_states.sort_by(compare_builders);	1✔
330
331	for (original_state, map_state) in states.into_iter().zip(map_states) {	100✔
332	assert!(Arc::ptr_eq(&original_state, &map_state));	100✔
333	}
334	}	1✔
335
336	fn compare_builders(	837✔
337	a: &Arc<BuilderState<TestTypes>>,	837✔
338	b: &Arc<BuilderState<TestTypes>>,	837✔
339	) -> Ordering {	837✔
340	a.parent_block_references	837✔
341	.view_number	837✔
342	.cmp(&b.parent_block_references.view_number)	837✔
343	.then(	837✔
344	a.parent_block_references	837✔
345	.vid_commitment	837✔
346	.cmp(&b.parent_block_references.vid_commitment),	837✔
347	)	837✔
348	}	837✔
349	}

EspressoSystems / marketplace-builder-core / 11961978007

Source File Press 'n' to go to next uncovered line, 'b' for previous

Source File
Press 'n' to go to next uncovered line, 'b' for previous