tet_core/
changes_trie.rs

1// This file is part of Tetcore.
2
3// Copyright (C) 2018-2021 Parity Technologies (UK) Ltd.
4// SPDX-License-Identifier: Apache-2.0
5
6// Licensed under the Apache License, Version 2.0 (the "License");
7// you may not use this file except in compliance with the License.
8// You may obtain a copy of the License at
9//
10// 	http://www.apache.org/licenses/LICENSE-2.0
11//
12// Unless required by applicable law or agreed to in writing, software
13// distributed under the License is distributed on an "AS IS" BASIS,
14// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
15// See the License for the specific language governing permissions and
16// limitations under the License.
17
18//! Tetcore changes trie configuration.
19
20#[cfg(any(feature = "std", test))]
21use serde::{Serialize, Deserialize};
22use codec::{Encode, Decode};
23use num_traits::Zero;
24
25/// Tetcore changes trie configuration.
26#[cfg_attr(any(feature = "std", test), derive(Serialize, Deserialize, tetsy_util_mem::MallocSizeOf))]
27#[derive(Debug, Clone, PartialEq, Eq, Default, Encode, Decode)]
28pub struct ChangesTrieConfiguration {
29	/// Interval (in blocks) at which level1-digests are created. Digests are not
30	/// created when this is less or equal to 1.
31	pub digest_interval: u32,
32	/// Maximal number of digest levels in hierarchy. 0 means that digests are not
33	/// created at all (even level1 digests). 1 means only level1-digests are created.
34	/// 2 means that every digest_interval^2 there will be a level2-digest, and so on.
35	/// Please ensure that maximum digest interval (i.e. digest_interval^digest_levels)
36	/// is within `u32` limits. Otherwise you'll never see digests covering such intervals
37	/// && maximal digests interval will be truncated to the last interval that fits
38	/// `u32` limits.
39	pub digest_levels: u32,
40}
41
42/// Tetcore changes trie configuration range.
43#[derive(Debug, Clone, PartialEq, Eq)]
44pub struct ChangesTrieConfigurationRange<Number, Hash> {
45	/// Zero block of configuration.
46	pub zero: (Number, Hash),
47	/// Last block of configuration (if configuration has been deactivated at some point).
48	pub end: Option<(Number, Hash)>,
49	/// The configuration itself. None if changes tries were disabled in this range.
50	pub config: Option<ChangesTrieConfiguration>,
51}
52
53impl ChangesTrieConfiguration {
54	/// Create new configuration given digest interval and levels.
55	pub fn new(digest_interval: u32, digest_levels: u32) -> Self {
56		Self { digest_interval, digest_levels }
57	}
58
59	/// Is digest build enabled?
60	pub fn is_digest_build_enabled(&self) -> bool {
61		self.digest_interval > 1 && self.digest_levels > 0
62	}
63
64	/// Do we need to build digest at given block?
65	pub fn is_digest_build_required_at_block<Number>(
66		&self,
67		zero: Number,
68		block: Number,
69	) -> bool
70		where
71			Number: From<u32> + PartialEq +
72			::tetcore_std::ops::Rem<Output=Number> + ::tetcore_std::ops::Sub<Output=Number> +
73			::tetcore_std::cmp::PartialOrd + Zero,
74	{
75		block > zero
76			&& self.is_digest_build_enabled()
77			&& ((block - zero) % self.digest_interval.into()).is_zero()
78	}
79
80	/// Returns max digest interval. One if digests are not created at all.
81	pub fn max_digest_interval(&self) -> u32 {
82		if !self.is_digest_build_enabled() {
83			return 1;
84		}
85
86		// we'll get >1 loop iteration only when bad configuration parameters are selected
87		let mut current_level = self.digest_levels;
88		loop {
89			if let Some(max_digest_interval) = self.digest_interval.checked_pow(current_level) {
90				return max_digest_interval;
91			}
92
93			current_level = current_level - 1;
94		}
95	}
96
97	/// Returns max level digest block number that has been created at block <= passed block number.
98	///
99	/// Returns None if digests are not created at all.
100	pub fn prev_max_level_digest_block<Number>(
101		&self,
102		zero: Number,
103		block: Number,
104	) -> Option<Number>
105		where
106			Number: Clone + From<u32> + PartialOrd + PartialEq +
107			::tetcore_std::ops::Add<Output=Number> + ::tetcore_std::ops::Sub<Output=Number> +
108			::tetcore_std::ops::Div<Output=Number> + ::tetcore_std::ops::Mul<Output=Number> + Zero,
109	{
110		if block <= zero {
111			return None;
112		}
113
114		let (next_begin, next_end) = self.next_max_level_digest_range(zero.clone(), block.clone())?;
115
116		// if 'next' digest includes our block, then it is a also a previous digest
117		if next_end == block {
118			return Some(block);
119		}
120
121		// if previous digest ends at zero block, then there are no previous digest
122		let prev_end = next_begin - 1.into();
123		if prev_end == zero {
124			None
125		} else {
126			Some(prev_end)
127		}
128	}
129
130	/// Returns max level digest blocks range (inclusive) which includes passed block.
131	///
132	/// Returns None if digests are not created at all.
133	/// It will return the first max-level digest if block is <= zero.
134	pub fn next_max_level_digest_range<Number>(
135		&self,
136		zero: Number,
137		mut block: Number,
138	) -> Option<(Number, Number)>
139		where
140			Number: Clone + From<u32> + PartialOrd + PartialEq +
141			::tetcore_std::ops::Add<Output=Number> + ::tetcore_std::ops::Sub<Output=Number> +
142			::tetcore_std::ops::Div<Output=Number> + ::tetcore_std::ops::Mul<Output=Number>,
143	{
144		if !self.is_digest_build_enabled() {
145			return None;
146		}
147
148		if block <= zero {
149			block = zero.clone() + 1.into();
150		}
151
152		let max_digest_interval: Number = self.max_digest_interval().into();
153		let max_digests_since_zero = (block.clone() - zero.clone()) / max_digest_interval.clone();
154		if max_digests_since_zero == 0.into() {
155			return Some((zero.clone() + 1.into(), zero + max_digest_interval));
156		}
157		let last_max_digest_block = zero + max_digests_since_zero * max_digest_interval.clone();
158		Some(if block == last_max_digest_block {
159			(block.clone() - max_digest_interval + 1.into(), block)
160		} else {
161			(last_max_digest_block.clone() + 1.into(), last_max_digest_block + max_digest_interval)
162		})
163	}
164
165	/// Returns Some if digest must be built at given block number.
166	/// The tuple is:
167	/// (
168	///  digest level
169	///  digest interval (in blocks)
170	///  step between blocks we're interested in when digest is built
171	/// )
172	pub fn digest_level_at_block<Number>(&self, zero: Number, block: Number) -> Option<(u32, u32, u32)>
173		where
174			Number: Clone + From<u32> + PartialEq +
175			::tetcore_std::ops::Rem<Output=Number> + ::tetcore_std::ops::Sub<Output=Number> +
176			::tetcore_std::cmp::PartialOrd + Zero,
177	{
178		if !self.is_digest_build_required_at_block(zero.clone(), block.clone()) {
179			return None;
180		}
181
182		let relative_block = block - zero;
183		let mut digest_interval = self.digest_interval;
184		let mut current_level = 1u32;
185		let mut digest_step = 1u32;
186		while current_level < self.digest_levels {
187			let new_digest_interval = match digest_interval.checked_mul(self.digest_interval) {
188				Some(new_digest_interval) if (relative_block.clone() % new_digest_interval.into()).is_zero()
189					=> new_digest_interval,
190				_ => break,
191			};
192
193			digest_step = digest_interval;
194			digest_interval = new_digest_interval;
195			current_level = current_level + 1;
196		}
197
198		Some((
199			current_level,
200			digest_interval,
201			digest_step,
202		))
203	}
204}
205
206#[cfg(test)]
207mod tests {
208	use super::ChangesTrieConfiguration;
209
210	fn config(interval: u32, levels: u32) -> ChangesTrieConfiguration {
211		ChangesTrieConfiguration {
212			digest_interval: interval,
213			digest_levels: levels,
214		}
215	}
216
217	#[test]
218	fn is_digest_build_enabled_works() {
219		assert!(!config(0, 100).is_digest_build_enabled());
220		assert!(!config(1, 100).is_digest_build_enabled());
221		assert!(config(2, 100).is_digest_build_enabled());
222		assert!(!config(100, 0).is_digest_build_enabled());
223		assert!(config(100, 1).is_digest_build_enabled());
224	}
225
226	#[test]
227	fn is_digest_build_required_at_block_works() {
228		fn test_with_zero(zero: u64) {
229			assert!(!config(8, 4).is_digest_build_required_at_block(zero, zero + 0u64));
230			assert!(!config(8, 4).is_digest_build_required_at_block(zero, zero + 1u64));
231			assert!(!config(8, 4).is_digest_build_required_at_block(zero, zero + 2u64));
232			assert!(!config(8, 4).is_digest_build_required_at_block(zero, zero + 4u64));
233			assert!(config(8, 4).is_digest_build_required_at_block(zero, zero + 8u64));
234			assert!(!config(8, 4).is_digest_build_required_at_block(zero, zero + 9u64));
235			assert!(config(8, 4).is_digest_build_required_at_block(zero, zero + 64u64));
236			assert!(config(8, 4).is_digest_build_required_at_block(zero, zero + 64u64));
237			assert!(config(8, 4).is_digest_build_required_at_block(zero, zero + 512u64));
238			assert!(config(8, 4).is_digest_build_required_at_block(zero, zero + 4096u64));
239			assert!(!config(8, 4).is_digest_build_required_at_block(zero, zero + 4103u64));
240			assert!(config(8, 4).is_digest_build_required_at_block(zero, zero + 4104u64));
241			assert!(!config(8, 4).is_digest_build_required_at_block(zero, zero + 4108u64));
242		}
243
244		test_with_zero(0);
245		test_with_zero(8);
246		test_with_zero(17);
247	}
248
249	#[test]
250	fn digest_level_at_block_works() {
251		fn test_with_zero(zero: u64) {
252			assert_eq!(config(8, 4).digest_level_at_block(zero, zero + 0u64), None);
253			assert_eq!(config(8, 4).digest_level_at_block(zero, zero + 7u64), None);
254			assert_eq!(config(8, 4).digest_level_at_block(zero, zero + 63u64), None);
255			assert_eq!(config(8, 4).digest_level_at_block(zero, zero + 8u64), Some((1, 8, 1)));
256			assert_eq!(config(8, 4).digest_level_at_block(zero, zero + 64u64), Some((2, 64, 8)));
257			assert_eq!(config(8, 4).digest_level_at_block(zero, zero + 512u64), Some((3, 512, 64)));
258			assert_eq!(config(8, 4).digest_level_at_block(zero, zero + 4096u64), Some((4, 4096, 512)));
259			assert_eq!(config(8, 4).digest_level_at_block(zero, zero + 4112u64), Some((1, 8, 1)));
260		}
261
262		test_with_zero(0);
263		test_with_zero(8);
264		test_with_zero(17);
265	}
266
267	#[test]
268	fn max_digest_interval_works() {
269		assert_eq!(config(0, 0).max_digest_interval(), 1);
270		assert_eq!(config(2, 2).max_digest_interval(), 4);
271		assert_eq!(config(8, 4).max_digest_interval(), 4096);
272		assert_eq!(config(::std::u32::MAX, 1024).max_digest_interval(), ::std::u32::MAX);
273	}
274
275	#[test]
276	fn next_max_level_digest_range_works() {
277		assert_eq!(config(0, 0).next_max_level_digest_range(0u64, 16), None);
278		assert_eq!(config(1, 1).next_max_level_digest_range(0u64, 16), None);
279		assert_eq!(config(2, 1).next_max_level_digest_range(0u64, 16), Some((15, 16)));
280		assert_eq!(config(4, 1).next_max_level_digest_range(0u64, 16), Some((13, 16)));
281		assert_eq!(config(32, 1).next_max_level_digest_range(0u64, 16), Some((1, 32)));
282		assert_eq!(config(2, 3).next_max_level_digest_range(0u64, 10), Some((9, 16)));
283		assert_eq!(config(2, 3).next_max_level_digest_range(0u64, 8), Some((1, 8)));
284		assert_eq!(config(2, 1).next_max_level_digest_range(1u64, 1), Some((2, 3)));
285		assert_eq!(config(2, 2).next_max_level_digest_range(7u64, 9), Some((8, 11)));
286
287		assert_eq!(config(2, 2).next_max_level_digest_range(7u64, 5), Some((8, 11)));
288	}
289
290	#[test]
291	fn prev_max_level_digest_block_works() {
292		assert_eq!(config(0, 0).prev_max_level_digest_block(0u64, 16), None);
293		assert_eq!(config(1, 1).prev_max_level_digest_block(0u64, 16), None);
294		assert_eq!(config(2, 1).prev_max_level_digest_block(0u64, 16), Some(16));
295		assert_eq!(config(4, 1).prev_max_level_digest_block(0u64, 16), Some(16));
296		assert_eq!(config(4, 2).prev_max_level_digest_block(0u64, 16), Some(16));
297		assert_eq!(config(4, 2).prev_max_level_digest_block(0u64, 17), Some(16));
298		assert_eq!(config(4, 2).prev_max_level_digest_block(0u64, 33), Some(32));
299		assert_eq!(config(32, 1).prev_max_level_digest_block(0u64, 16), None);
300		assert_eq!(config(2, 3).prev_max_level_digest_block(0u64, 10), Some(8));
301		assert_eq!(config(2, 3).prev_max_level_digest_block(0u64, 8), Some(8));
302		assert_eq!(config(2, 2).prev_max_level_digest_block(7u64, 8), None);
303
304		assert_eq!(config(2, 2).prev_max_level_digest_block(7u64, 5), None);
305	}
306}