1#[cfg(any(feature = "std", test))]
21use serde::{Serialize, Deserialize};
22use codec::{Encode, Decode};
23use num_traits::Zero;
24
25#[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 pub digest_interval: u32,
32 pub digest_levels: u32,
40}
41
42#[derive(Debug, Clone, PartialEq, Eq)]
44pub struct ChangesTrieConfigurationRange<Number, Hash> {
45 pub zero: (Number, Hash),
47 pub end: Option<(Number, Hash)>,
49 pub config: Option<ChangesTrieConfiguration>,
51}
52
53impl ChangesTrieConfiguration {
54 pub fn new(digest_interval: u32, digest_levels: u32) -> Self {
56 Self { digest_interval, digest_levels }
57 }
58
59 pub fn is_digest_build_enabled(&self) -> bool {
61 self.digest_interval > 1 && self.digest_levels > 0
62 }
63
64 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 pub fn max_digest_interval(&self) -> u32 {
82 if !self.is_digest_build_enabled() {
83 return 1;
84 }
85
86 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 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_end == block {
118 return Some(block);
119 }
120
121 let prev_end = next_begin - 1.into();
123 if prev_end == zero {
124 None
125 } else {
126 Some(prev_end)
127 }
128 }
129
130 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 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}