/__w/smoldot/smoldot/repo/lib/src/trie/calculate_root.rs
Line | Count | Source (jump to first uncovered line) |
1 | | // Smoldot |
2 | | // Copyright (C) 2023 Pierre Krieger |
3 | | // SPDX-License-Identifier: GPL-3.0-or-later WITH Classpath-exception-2.0 |
4 | | |
5 | | // This program is free software: you can redistribute it and/or modify |
6 | | // it under the terms of the GNU General Public License as published by |
7 | | // the Free Software Foundation, either version 3 of the License, or |
8 | | // (at your option) any later version. |
9 | | |
10 | | // This program is distributed in the hope that it will be useful, |
11 | | // but WITHOUT ANY WARRANTY; without even the implied warranty of |
12 | | // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the |
13 | | // GNU General Public License for more details. |
14 | | |
15 | | // You should have received a copy of the GNU General Public License |
16 | | // along with this program. If not, see <http://www.gnu.org/licenses/>. |
17 | | |
18 | | //! Freestanding function that calculates the root of a radix-16 Merkle-Patricia trie. |
19 | | //! |
20 | | //! See the parent module documentation for an explanation of what the trie is. |
21 | | //! |
22 | | //! This module is meant to be used in situations where all the nodes of the trie that have a |
23 | | //! storage value associated to them are known and easily accessible, and that no cache is |
24 | | //! available. |
25 | | //! |
26 | | //! # Usage |
27 | | //! |
28 | | //! Calling the [`root_merkle_value`] function creates a [`RootMerkleValueCalculation`] object |
29 | | //! which you have to drive to completion. |
30 | | //! |
31 | | //! Example: |
32 | | //! |
33 | | //! ``` |
34 | | //! use std::{collections::BTreeMap, ops::Bound}; |
35 | | //! use smoldot::trie::{HashFunction, TrieEntryVersion, calculate_root}; |
36 | | //! |
37 | | //! // In this example, the storage consists in a binary tree map. |
38 | | //! let mut storage = BTreeMap::<Vec<u8>, (Vec<u8>, TrieEntryVersion)>::new(); |
39 | | //! storage.insert(b"foo".to_vec(), (b"bar".to_vec(), TrieEntryVersion::V1)); |
40 | | //! |
41 | | //! let trie_root = { |
42 | | //! let mut calculation = calculate_root::root_merkle_value(HashFunction::Blake2); |
43 | | //! loop { |
44 | | //! match calculation { |
45 | | //! calculate_root::RootMerkleValueCalculation::Finished { hash, .. } => break hash, |
46 | | //! calculate_root::RootMerkleValueCalculation::NextKey(next_key) => { |
47 | | //! let key_before = next_key.key_before().collect::<Vec<_>>(); |
48 | | //! let lower_bound = if next_key.or_equal() { |
49 | | //! Bound::Included(key_before) |
50 | | //! } else { |
51 | | //! Bound::Excluded(key_before) |
52 | | //! }; |
53 | | //! let outcome = storage |
54 | | //! .range((lower_bound, Bound::Unbounded)) |
55 | | //! .next() |
56 | | //! .filter(|(k, _)| { |
57 | | //! k.iter() |
58 | | //! .copied() |
59 | | //! .zip(next_key.prefix()) |
60 | | //! .all(|(a, b)| a == b) |
61 | | //! }) |
62 | | //! .map(|(k, _)| k); |
63 | | //! calculation = next_key.inject_key(outcome.map(|k| k.iter().copied())); |
64 | | //! } |
65 | | //! calculate_root::RootMerkleValueCalculation::StorageValue(value_request) => { |
66 | | //! let key = value_request.key().collect::<Vec<u8>>(); |
67 | | //! calculation = value_request.inject(storage.get(&key).map(|(val, v)| (val, *v))); |
68 | | //! } |
69 | | //! } |
70 | | //! } |
71 | | //! }; |
72 | | //! |
73 | | //! assert_eq!( |
74 | | //! trie_root, |
75 | | //! [204, 86, 28, 213, 155, 206, 247, 145, 28, 169, 212, 146, 182, 159, 224, 82, |
76 | | //! 116, 162, 143, 156, 19, 43, 183, 8, 41, 178, 204, 69, 41, 37, 224, 91] |
77 | | //! ); |
78 | | //! ``` |
79 | | //! |
80 | | |
81 | | use super::{ |
82 | | branch_search, |
83 | | nibble::{nibbles_to_bytes_suffix_extend, Nibble}, |
84 | | trie_node, HashFunction, TrieEntryVersion, EMPTY_BLAKE2_TRIE_MERKLE_VALUE, |
85 | | EMPTY_KECCAK256_TRIE_MERKLE_VALUE, |
86 | | }; |
87 | | |
88 | | use alloc::vec::Vec; |
89 | | use core::array; |
90 | | |
91 | | /// Start calculating the Merkle value of the root node. |
92 | 39 | pub fn root_merkle_value(hash_function: HashFunction) -> RootMerkleValueCalculation { |
93 | 39 | CalcInner { |
94 | 39 | hash_function, |
95 | 39 | stack: Vec::with_capacity(8), |
96 | 39 | } |
97 | 39 | .next() |
98 | 39 | } _RNvNtNtCsN16ciHI6Qf_7smoldot4trie14calculate_root17root_merkle_value Line | Count | Source | 92 | 18 | pub fn root_merkle_value(hash_function: HashFunction) -> RootMerkleValueCalculation { | 93 | 18 | CalcInner { | 94 | 18 | hash_function, | 95 | 18 | stack: Vec::with_capacity(8), | 96 | 18 | } | 97 | 18 | .next() | 98 | 18 | } |
_RNvNtNtCseuYC0Zibziv_7smoldot4trie14calculate_root17root_merkle_value Line | Count | Source | 92 | 21 | pub fn root_merkle_value(hash_function: HashFunction) -> RootMerkleValueCalculation { | 93 | 21 | CalcInner { | 94 | 21 | hash_function, | 95 | 21 | stack: Vec::with_capacity(8), | 96 | 21 | } | 97 | 21 | .next() | 98 | 21 | } |
|
99 | | |
100 | | /// Current state of the [`RootMerkleValueCalculation`] and how to continue. |
101 | | #[must_use] |
102 | | pub enum RootMerkleValueCalculation { |
103 | | /// The calculation is finished. |
104 | | Finished { |
105 | | /// Root hash that has been calculated. |
106 | | hash: [u8; 32], |
107 | | }, |
108 | | |
109 | | /// Request to return the key that follows (in lexicographic order) a given one in the storage. |
110 | | /// Call [`NextKey::inject_key`] to indicate this list. |
111 | | NextKey(NextKey), |
112 | | |
113 | | /// Request the value of the node with a specific key. Call [`StorageValue::inject`] to |
114 | | /// indicate the value. |
115 | | StorageValue(StorageValue), |
116 | | } |
117 | | |
118 | | /// Calculation of the Merkle value is ready to continue. |
119 | | /// Shared by all the public-facing structs. |
120 | | struct CalcInner { |
121 | | /// Hash function used by the trie. |
122 | | hash_function: HashFunction, |
123 | | /// Stack of nodes whose value is currently being calculated. |
124 | | stack: Vec<Node>, |
125 | | } |
126 | | |
127 | | #[derive(Debug)] |
128 | | struct Node { |
129 | | /// Partial key of the node currently being calculated. |
130 | | partial_key: Vec<Nibble>, |
131 | | /// Merkle values of the children of the node. Filled up to 16 elements, then popped. Each |
132 | | /// element is `Some` or `None` depending on whether a child exists. |
133 | | children: arrayvec::ArrayVec<Option<trie_node::MerkleValueOutput>, 16>, |
134 | | } |
135 | | |
136 | | impl CalcInner { |
137 | | /// Returns the full key of the node currently being iterated. |
138 | 41.6k | fn current_iter_node_full_key(&'_ self) -> impl Iterator<Item = Nibble> + '_ { |
139 | 142k | self.stack.iter().flat_map(|node| { |
140 | 142k | let child_nibble = if node.children.len() == 16 { |
141 | 3.19k | None |
142 | | } else { |
143 | 138k | Some(Nibble::try_from(u8::try_from(node.children.len()).unwrap()).unwrap()) |
144 | | }; |
145 | | |
146 | 142k | node.partial_key.iter().copied().chain(child_nibble) |
147 | 142k | }) _RNCNvMNtNtCsN16ciHI6Qf_7smoldot4trie14calculate_rootNtB4_9CalcInner26current_iter_node_full_key0B8_ Line | Count | Source | 139 | 19.1k | self.stack.iter().flat_map(|node| { | 140 | 19.1k | let child_nibble = if node.children.len() == 16 { | 141 | 422 | None | 142 | | } else { | 143 | 18.7k | Some(Nibble::try_from(u8::try_from(node.children.len()).unwrap()).unwrap()) | 144 | | }; | 145 | | | 146 | 19.1k | node.partial_key.iter().copied().chain(child_nibble) | 147 | 19.1k | }) |
Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot4trie14calculate_rootNtB4_9CalcInner26current_iter_node_full_key0CsDDUKWWCHAU_18smoldot_light_wasm _RNCNvMNtNtCseuYC0Zibziv_7smoldot4trie14calculate_rootNtB4_9CalcInner26current_iter_node_full_key0B8_ Line | Count | Source | 139 | 122k | self.stack.iter().flat_map(|node| { | 140 | 122k | let child_nibble = if node.children.len() == 16 { | 141 | 2.77k | None | 142 | | } else { | 143 | 120k | Some(Nibble::try_from(u8::try_from(node.children.len()).unwrap()).unwrap()) | 144 | | }; | 145 | | | 146 | 122k | node.partial_key.iter().copied().chain(child_nibble) | 147 | 122k | }) |
Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot4trie14calculate_rootNtB4_9CalcInner26current_iter_node_full_key0CsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot4trie14calculate_rootNtB4_9CalcInner26current_iter_node_full_key0CscDgN54JpMGG_6author Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot4trie14calculate_rootNtB4_9CalcInner26current_iter_node_full_key0CsibGXYHQB8Ea_25json_rpc_general_requests |
148 | 41.6k | } _RNvMNtNtCsN16ciHI6Qf_7smoldot4trie14calculate_rootNtB2_9CalcInner26current_iter_node_full_key Line | Count | Source | 138 | 5.54k | fn current_iter_node_full_key(&'_ self) -> impl Iterator<Item = Nibble> + '_ { | 139 | 5.54k | self.stack.iter().flat_map(|node| { | 140 | | let child_nibble = if node.children.len() == 16 { | 141 | | None | 142 | | } else { | 143 | | Some(Nibble::try_from(u8::try_from(node.children.len()).unwrap()).unwrap()) | 144 | | }; | 145 | | | 146 | | node.partial_key.iter().copied().chain(child_nibble) | 147 | 5.54k | }) | 148 | 5.54k | } |
_RNvMNtNtCseuYC0Zibziv_7smoldot4trie14calculate_rootNtB2_9CalcInner26current_iter_node_full_key Line | Count | Source | 138 | 36.0k | fn current_iter_node_full_key(&'_ self) -> impl Iterator<Item = Nibble> + '_ { | 139 | 36.0k | self.stack.iter().flat_map(|node| { | 140 | | let child_nibble = if node.children.len() == 16 { | 141 | | None | 142 | | } else { | 143 | | Some(Nibble::try_from(u8::try_from(node.children.len()).unwrap()).unwrap()) | 144 | | }; | 145 | | | 146 | | node.partial_key.iter().copied().chain(child_nibble) | 147 | 36.0k | }) | 148 | 36.0k | } |
|
149 | | |
150 | | /// Advances the calculation to the next step. |
151 | 19.6k | fn next(mut self) -> RootMerkleValueCalculation { |
152 | 19.7k | loop { |
153 | 19.7k | // If all the children of the node at the end of the stack are known, calculate the Merkle |
154 | 19.7k | // value of that node. To do so, we need to ask the user for the storage value. |
155 | 19.7k | if self |
156 | 19.7k | .stack |
157 | 19.7k | .last() |
158 | 19.7k | .map_or(false, |node| node.children.len() == 1619.7k ) _RNCNvMNtNtCsN16ciHI6Qf_7smoldot4trie14calculate_rootNtB4_9CalcInner4next0B8_ Line | Count | Source | 158 | 2.61k | .map_or(false, |node| node.children.len() == 16) |
_RNCNvMNtNtCseuYC0Zibziv_7smoldot4trie14calculate_rootNtB4_9CalcInner4next0B8_ Line | Count | Source | 158 | 17.1k | .map_or(false, |node| node.children.len() == 16) |
|
159 | | { |
160 | | // If the key has an even number of nibbles, we need to ask the user for the |
161 | | // storage value. |
162 | 1.16k | if self.current_iter_node_full_key().count() % 2 == 0 { |
163 | 1.01k | break RootMerkleValueCalculation::StorageValue(StorageValue { |
164 | 1.01k | calculation: self, |
165 | 1.01k | }); |
166 | 146 | } |
167 | 146 | |
168 | 146 | // Otherwise we can calculate immediately. |
169 | 146 | let calculated_elem = self.stack.pop().unwrap(); |
170 | 146 | |
171 | 146 | // Calculate the Merkle value of the node. |
172 | 146 | let merkle_value = trie_node::calculate_merkle_value( |
173 | 146 | trie_node::Decoded { |
174 | 2.33k | children: array::from_fn(|n| calculated_elem.children[n].as_ref()), _RNCNvMNtNtCsN16ciHI6Qf_7smoldot4trie14calculate_rootNtB4_9CalcInner4nexts_0B8_ Line | Count | Source | 174 | 320 | children: array::from_fn(|n| calculated_elem.children[n].as_ref()), |
_RNCNvMNtNtCseuYC0Zibziv_7smoldot4trie14calculate_rootNtB4_9CalcInner4nexts_0B8_ Line | Count | Source | 174 | 2.01k | children: array::from_fn(|n| calculated_elem.children[n].as_ref()), |
|
175 | 146 | partial_key: calculated_elem.partial_key.iter().copied(), |
176 | 146 | storage_value: trie_node::StorageValue::None, |
177 | 146 | }, |
178 | 146 | self.hash_function, |
179 | 146 | self.stack.is_empty(), |
180 | 146 | ) |
181 | 146 | .unwrap_or_else(|_| unreachable!()0 ); Unexecuted instantiation: _RNCNvMNtNtCsN16ciHI6Qf_7smoldot4trie14calculate_rootNtB4_9CalcInner4nexts0_0B8_ Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot4trie14calculate_rootNtB4_9CalcInner4nexts0_0B8_ |
182 | | |
183 | | // Insert Merkle value into the stack, or, if no parent, we have our result! |
184 | 146 | if let Some(parent140 ) = self.stack.last_mut() { |
185 | 140 | parent.children.push(Some(merkle_value)); |
186 | 140 | } else { |
187 | | // Because we pass `is_root_node: true` in the calculation above, it is |
188 | | // guaranteed that the Merkle value is always 32 bytes. |
189 | 6 | let hash = *<&[u8; 32]>::try_from(merkle_value.as_ref()).unwrap(); |
190 | 6 | break RootMerkleValueCalculation::Finished { hash }; |
191 | | } |
192 | | } else { |
193 | | // Need to find the closest descendant to the first unknown child at the top of the |
194 | | // stack. |
195 | 18.6k | break RootMerkleValueCalculation::NextKey(NextKey { |
196 | 18.6k | branch_search: branch_search::start_branch_search(branch_search::Config { |
197 | 18.6k | key_before: self.current_iter_node_full_key(), |
198 | 18.6k | or_equal: true, |
199 | 18.6k | prefix: self.current_iter_node_full_key(), |
200 | 18.6k | no_branch_search: false, |
201 | 18.6k | }), |
202 | 18.6k | calculation: self, |
203 | 18.6k | }); |
204 | | } |
205 | | } |
206 | 19.6k | } _RNvMNtNtCsN16ciHI6Qf_7smoldot4trie14calculate_rootNtB2_9CalcInner4next Line | Count | Source | 151 | 2.62k | fn next(mut self) -> RootMerkleValueCalculation { | 152 | 2.63k | loop { | 153 | 2.63k | // If all the children of the node at the end of the stack are known, calculate the Merkle | 154 | 2.63k | // value of that node. To do so, we need to ask the user for the storage value. | 155 | 2.63k | if self | 156 | 2.63k | .stack | 157 | 2.63k | .last() | 158 | 2.63k | .map_or(false, |node| node.children.len() == 16) | 159 | | { | 160 | | // If the key has an even number of nibbles, we need to ask the user for the | 161 | | // storage value. | 162 | 154 | if self.current_iter_node_full_key().count() % 2 == 0 { | 163 | 134 | break RootMerkleValueCalculation::StorageValue(StorageValue { | 164 | 134 | calculation: self, | 165 | 134 | }); | 166 | 20 | } | 167 | 20 | | 168 | 20 | // Otherwise we can calculate immediately. | 169 | 20 | let calculated_elem = self.stack.pop().unwrap(); | 170 | 20 | | 171 | 20 | // Calculate the Merkle value of the node. | 172 | 20 | let merkle_value = trie_node::calculate_merkle_value( | 173 | 20 | trie_node::Decoded { | 174 | 20 | children: array::from_fn(|n| calculated_elem.children[n].as_ref()), | 175 | 20 | partial_key: calculated_elem.partial_key.iter().copied(), | 176 | 20 | storage_value: trie_node::StorageValue::None, | 177 | 20 | }, | 178 | 20 | self.hash_function, | 179 | 20 | self.stack.is_empty(), | 180 | 20 | ) | 181 | 20 | .unwrap_or_else(|_| unreachable!()); | 182 | | | 183 | | // Insert Merkle value into the stack, or, if no parent, we have our result! | 184 | 20 | if let Some(parent14 ) = self.stack.last_mut() { | 185 | 14 | parent.children.push(Some(merkle_value)); | 186 | 14 | } else { | 187 | | // Because we pass `is_root_node: true` in the calculation above, it is | 188 | | // guaranteed that the Merkle value is always 32 bytes. | 189 | 6 | let hash = *<&[u8; 32]>::try_from(merkle_value.as_ref()).unwrap(); | 190 | 6 | break RootMerkleValueCalculation::Finished { hash }; | 191 | | } | 192 | | } else { | 193 | | // Need to find the closest descendant to the first unknown child at the top of the | 194 | | // stack. | 195 | 2.48k | break RootMerkleValueCalculation::NextKey(NextKey { | 196 | 2.48k | branch_search: branch_search::start_branch_search(branch_search::Config { | 197 | 2.48k | key_before: self.current_iter_node_full_key(), | 198 | 2.48k | or_equal: true, | 199 | 2.48k | prefix: self.current_iter_node_full_key(), | 200 | 2.48k | no_branch_search: false, | 201 | 2.48k | }), | 202 | 2.48k | calculation: self, | 203 | 2.48k | }); | 204 | | } | 205 | | } | 206 | 2.62k | } |
_RNvMNtNtCseuYC0Zibziv_7smoldot4trie14calculate_rootNtB2_9CalcInner4next Line | Count | Source | 151 | 17.0k | fn next(mut self) -> RootMerkleValueCalculation { | 152 | 17.1k | loop { | 153 | 17.1k | // If all the children of the node at the end of the stack are known, calculate the Merkle | 154 | 17.1k | // value of that node. To do so, we need to ask the user for the storage value. | 155 | 17.1k | if self | 156 | 17.1k | .stack | 157 | 17.1k | .last() | 158 | 17.1k | .map_or(false, |node| node.children.len() == 16) | 159 | | { | 160 | | // If the key has an even number of nibbles, we need to ask the user for the | 161 | | // storage value. | 162 | 1.00k | if self.current_iter_node_full_key().count() % 2 == 0 { | 163 | 882 | break RootMerkleValueCalculation::StorageValue(StorageValue { | 164 | 882 | calculation: self, | 165 | 882 | }); | 166 | 126 | } | 167 | 126 | | 168 | 126 | // Otherwise we can calculate immediately. | 169 | 126 | let calculated_elem = self.stack.pop().unwrap(); | 170 | 126 | | 171 | 126 | // Calculate the Merkle value of the node. | 172 | 126 | let merkle_value = trie_node::calculate_merkle_value( | 173 | 126 | trie_node::Decoded { | 174 | 126 | children: array::from_fn(|n| calculated_elem.children[n].as_ref()), | 175 | 126 | partial_key: calculated_elem.partial_key.iter().copied(), | 176 | 126 | storage_value: trie_node::StorageValue::None, | 177 | 126 | }, | 178 | 126 | self.hash_function, | 179 | 126 | self.stack.is_empty(), | 180 | 126 | ) | 181 | 126 | .unwrap_or_else(|_| unreachable!()); | 182 | | | 183 | | // Insert Merkle value into the stack, or, if no parent, we have our result! | 184 | 126 | if let Some(parent) = self.stack.last_mut() { | 185 | 126 | parent.children.push(Some(merkle_value)); | 186 | 126 | } else { | 187 | | // Because we pass `is_root_node: true` in the calculation above, it is | 188 | | // guaranteed that the Merkle value is always 32 bytes. | 189 | 0 | let hash = *<&[u8; 32]>::try_from(merkle_value.as_ref()).unwrap(); | 190 | 0 | break RootMerkleValueCalculation::Finished { hash }; | 191 | | } | 192 | | } else { | 193 | | // Need to find the closest descendant to the first unknown child at the top of the | 194 | | // stack. | 195 | 16.1k | break RootMerkleValueCalculation::NextKey(NextKey { | 196 | 16.1k | branch_search: branch_search::start_branch_search(branch_search::Config { | 197 | 16.1k | key_before: self.current_iter_node_full_key(), | 198 | 16.1k | or_equal: true, | 199 | 16.1k | prefix: self.current_iter_node_full_key(), | 200 | 16.1k | no_branch_search: false, | 201 | 16.1k | }), | 202 | 16.1k | calculation: self, | 203 | 16.1k | }); | 204 | | } | 205 | | } | 206 | 17.0k | } |
|
207 | | } |
208 | | |
209 | | /// Request to return the key that follows (in lexicographic order) a given one in the storage. |
210 | | /// Call [`NextKey::inject_key`] to indicate this list. |
211 | | #[must_use] |
212 | | pub struct NextKey { |
213 | | calculation: CalcInner, |
214 | | |
215 | | /// Current branch search running to find the closest descendant to the node at the top of |
216 | | /// the trie. |
217 | | branch_search: branch_search::NextKey, |
218 | | } |
219 | | |
220 | | impl NextKey { |
221 | | /// Returns the key whose next key must be passed back. |
222 | 20.1k | pub fn key_before(&'_ self) -> impl Iterator<Item = u8> + '_ { |
223 | 20.1k | self.branch_search.key_before() |
224 | 20.1k | } _RNvMs_NtNtCsN16ciHI6Qf_7smoldot4trie14calculate_rootNtB4_7NextKey10key_before Line | Count | Source | 222 | 2.67k | pub fn key_before(&'_ self) -> impl Iterator<Item = u8> + '_ { | 223 | 2.67k | self.branch_search.key_before() | 224 | 2.67k | } |
_RNvMs_NtNtCseuYC0Zibziv_7smoldot4trie14calculate_rootNtB4_7NextKey10key_before Line | Count | Source | 222 | 17.4k | pub fn key_before(&'_ self) -> impl Iterator<Item = u8> + '_ { | 223 | 17.4k | self.branch_search.key_before() | 224 | 17.4k | } |
|
225 | | |
226 | | /// If `true`, then the provided value must the one superior or equal to the requested key. |
227 | | /// If `false`, then the provided value must be strictly superior to the requested key. |
228 | 20.1k | pub fn or_equal(&self) -> bool { |
229 | 20.1k | self.branch_search.or_equal() |
230 | 20.1k | } _RNvMs_NtNtCsN16ciHI6Qf_7smoldot4trie14calculate_rootNtB4_7NextKey8or_equal Line | Count | Source | 228 | 2.67k | pub fn or_equal(&self) -> bool { | 229 | 2.67k | self.branch_search.or_equal() | 230 | 2.67k | } |
_RNvMs_NtNtCseuYC0Zibziv_7smoldot4trie14calculate_rootNtB4_7NextKey8or_equal Line | Count | Source | 228 | 17.4k | pub fn or_equal(&self) -> bool { | 229 | 17.4k | self.branch_search.or_equal() | 230 | 17.4k | } |
|
231 | | |
232 | | /// Returns the prefix the next key must start with. If the next key doesn't start with the |
233 | | /// given prefix, then `None` should be provided. |
234 | 19.7k | pub fn prefix(&'_ self) -> impl Iterator<Item = u8> + '_ { |
235 | 19.7k | self.branch_search.prefix() |
236 | 19.7k | } _RNvMs_NtNtCsN16ciHI6Qf_7smoldot4trie14calculate_rootNtB4_7NextKey6prefix Line | Count | Source | 234 | 2.28k | pub fn prefix(&'_ self) -> impl Iterator<Item = u8> + '_ { | 235 | 2.28k | self.branch_search.prefix() | 236 | 2.28k | } |
_RNvMs_NtNtCseuYC0Zibziv_7smoldot4trie14calculate_rootNtB4_7NextKey6prefix Line | Count | Source | 234 | 17.4k | pub fn prefix(&'_ self) -> impl Iterator<Item = u8> + '_ { | 235 | 17.4k | self.branch_search.prefix() | 236 | 17.4k | } |
|
237 | | |
238 | | /// Injects the key. |
239 | | /// |
240 | | /// # Panic |
241 | | /// |
242 | | /// Panics if the key passed as parameter isn't strictly superior to the requested key. |
243 | | /// |
244 | 20.1k | pub fn inject_key( |
245 | 20.1k | mut self, |
246 | 20.1k | key: Option<impl Iterator<Item = u8>>, |
247 | 20.1k | ) -> RootMerkleValueCalculation { |
248 | 20.1k | match self.branch_search.inject(key) { |
249 | 1.49k | branch_search::BranchSearch::NextKey(next_key) => { |
250 | 1.49k | RootMerkleValueCalculation::NextKey(NextKey { |
251 | 1.49k | calculation: self.calculation, |
252 | 1.49k | branch_search: next_key, |
253 | 1.49k | }) |
254 | | } |
255 | | branch_search::BranchSearch::Found { |
256 | 18.6k | branch_trie_node_key, |
257 | | } => { |
258 | | // Add the closest descendant to the stack. |
259 | 18.6k | if let Some(branch_trie_node_key1.16k ) = branch_trie_node_key { |
260 | 1.16k | let partial_key = branch_trie_node_key |
261 | 1.16k | .skip(self.calculation.current_iter_node_full_key().count()) |
262 | 1.16k | .collect(); |
263 | 1.16k | self.calculation.stack.push(Node { |
264 | 1.16k | partial_key, |
265 | 1.16k | children: arrayvec::ArrayVec::new(), |
266 | 1.16k | }); |
267 | 1.16k | self.calculation.next() |
268 | 17.4k | } else if let Some(stack_top17.4k ) = self.calculation.stack.last_mut() { |
269 | 17.4k | stack_top.children.push(None); |
270 | 17.4k | self.calculation.next() |
271 | | } else { |
272 | | // Trie is completely empty. |
273 | | RootMerkleValueCalculation::Finished { |
274 | 2 | hash: match self.calculation.hash_function { |
275 | 2 | HashFunction::Blake2 => EMPTY_BLAKE2_TRIE_MERKLE_VALUE, |
276 | 0 | HashFunction::Keccak256 => EMPTY_KECCAK256_TRIE_MERKLE_VALUE, |
277 | | }, |
278 | | } |
279 | | } |
280 | | } |
281 | | } |
282 | 20.1k | } _RINvMs_NtNtCsN16ciHI6Qf_7smoldot4trie14calculate_rootNtB5_7NextKey10inject_keyINtNtNtCsdZExvAaxgia_5alloc3vec9into_iter8IntoIterhEEB9_ Line | Count | Source | 244 | 2.04k | pub fn inject_key( | 245 | 2.04k | mut self, | 246 | 2.04k | key: Option<impl Iterator<Item = u8>>, | 247 | 2.04k | ) -> RootMerkleValueCalculation { | 248 | 2.04k | match self.branch_search.inject(key) { | 249 | 154 | branch_search::BranchSearch::NextKey(next_key) => { | 250 | 154 | RootMerkleValueCalculation::NextKey(NextKey { | 251 | 154 | calculation: self.calculation, | 252 | 154 | branch_search: next_key, | 253 | 154 | }) | 254 | | } | 255 | | branch_search::BranchSearch::Found { | 256 | 1.88k | branch_trie_node_key, | 257 | | } => { | 258 | | // Add the closest descendant to the stack. | 259 | 1.88k | if let Some(branch_trie_node_key118 ) = branch_trie_node_key { | 260 | 118 | let partial_key = branch_trie_node_key | 261 | 118 | .skip(self.calculation.current_iter_node_full_key().count()) | 262 | 118 | .collect(); | 263 | 118 | self.calculation.stack.push(Node { | 264 | 118 | partial_key, | 265 | 118 | children: arrayvec::ArrayVec::new(), | 266 | 118 | }); | 267 | 118 | self.calculation.next() | 268 | 1.77k | } else if let Some(stack_top) = self.calculation.stack.last_mut() { | 269 | 1.77k | stack_top.children.push(None); | 270 | 1.77k | self.calculation.next() | 271 | | } else { | 272 | | // Trie is completely empty. | 273 | | RootMerkleValueCalculation::Finished { | 274 | 0 | hash: match self.calculation.hash_function { | 275 | 0 | HashFunction::Blake2 => EMPTY_BLAKE2_TRIE_MERKLE_VALUE, | 276 | 0 | HashFunction::Keccak256 => EMPTY_KECCAK256_TRIE_MERKLE_VALUE, | 277 | | }, | 278 | | } | 279 | | } | 280 | | } | 281 | | } | 282 | 2.04k | } |
_RINvMs_NtNtCsN16ciHI6Qf_7smoldot4trie14calculate_rootNtB5_7NextKey10inject_keyINtNtNtNtCsaYZPK01V26L_4core4iter8adapters6copied6CopiedINtNtNtB1n_5slice4iter4IterhEEEB9_ Line | Count | Source | 244 | 635 | pub fn inject_key( | 245 | 635 | mut self, | 246 | 635 | key: Option<impl Iterator<Item = u8>>, | 247 | 635 | ) -> RootMerkleValueCalculation { | 248 | 635 | match self.branch_search.inject(key) { | 249 | 42 | branch_search::BranchSearch::NextKey(next_key) => { | 250 | 42 | RootMerkleValueCalculation::NextKey(NextKey { | 251 | 42 | calculation: self.calculation, | 252 | 42 | branch_search: next_key, | 253 | 42 | }) | 254 | | } | 255 | | branch_search::BranchSearch::Found { | 256 | 593 | branch_trie_node_key, | 257 | | } => { | 258 | | // Add the closest descendant to the stack. | 259 | 593 | if let Some(branch_trie_node_key36 ) = branch_trie_node_key { | 260 | 36 | let partial_key = branch_trie_node_key | 261 | 36 | .skip(self.calculation.current_iter_node_full_key().count()) | 262 | 36 | .collect(); | 263 | 36 | self.calculation.stack.push(Node { | 264 | 36 | partial_key, | 265 | 36 | children: arrayvec::ArrayVec::new(), | 266 | 36 | }); | 267 | 36 | self.calculation.next() | 268 | 557 | } else if let Some(stack_top555 ) = self.calculation.stack.last_mut() { | 269 | 555 | stack_top.children.push(None); | 270 | 555 | self.calculation.next() | 271 | | } else { | 272 | | // Trie is completely empty. | 273 | | RootMerkleValueCalculation::Finished { | 274 | 2 | hash: match self.calculation.hash_function { | 275 | 2 | HashFunction::Blake2 => EMPTY_BLAKE2_TRIE_MERKLE_VALUE, | 276 | 0 | HashFunction::Keccak256 => EMPTY_KECCAK256_TRIE_MERKLE_VALUE, | 277 | | }, | 278 | | } | 279 | | } | 280 | | } | 281 | | } | 282 | 635 | } |
Unexecuted instantiation: _RINvMs_NtNtCseuYC0Zibziv_7smoldot4trie14calculate_rootNtB5_7NextKey10inject_keyINtNtNtNtCsaYZPK01V26L_4core4iter8adapters6copied6CopiedINtNtNtB1o_5slice4iter4IterhEEECsDDUKWWCHAU_18smoldot_light_wasm _RINvMs_NtNtCseuYC0Zibziv_7smoldot4trie14calculate_rootNtB5_7NextKey10inject_keyINtNtNtCsdZExvAaxgia_5alloc3vec9into_iter8IntoIterhEEB9_ Line | Count | Source | 244 | 17.4k | pub fn inject_key( | 245 | 17.4k | mut self, | 246 | 17.4k | key: Option<impl Iterator<Item = u8>>, | 247 | 17.4k | ) -> RootMerkleValueCalculation { | 248 | 17.4k | match self.branch_search.inject(key) { | 249 | 1.30k | branch_search::BranchSearch::NextKey(next_key) => { | 250 | 1.30k | RootMerkleValueCalculation::NextKey(NextKey { | 251 | 1.30k | calculation: self.calculation, | 252 | 1.30k | branch_search: next_key, | 253 | 1.30k | }) | 254 | | } | 255 | | branch_search::BranchSearch::Found { | 256 | 16.1k | branch_trie_node_key, | 257 | | } => { | 258 | | // Add the closest descendant to the stack. | 259 | 16.1k | if let Some(branch_trie_node_key1.00k ) = branch_trie_node_key { | 260 | 1.00k | let partial_key = branch_trie_node_key | 261 | 1.00k | .skip(self.calculation.current_iter_node_full_key().count()) | 262 | 1.00k | .collect(); | 263 | 1.00k | self.calculation.stack.push(Node { | 264 | 1.00k | partial_key, | 265 | 1.00k | children: arrayvec::ArrayVec::new(), | 266 | 1.00k | }); | 267 | 1.00k | self.calculation.next() | 268 | 15.1k | } else if let Some(stack_top) = self.calculation.stack.last_mut() { | 269 | 15.1k | stack_top.children.push(None); | 270 | 15.1k | self.calculation.next() | 271 | | } else { | 272 | | // Trie is completely empty. | 273 | | RootMerkleValueCalculation::Finished { | 274 | 0 | hash: match self.calculation.hash_function { | 275 | 0 | HashFunction::Blake2 => EMPTY_BLAKE2_TRIE_MERKLE_VALUE, | 276 | 0 | HashFunction::Keccak256 => EMPTY_KECCAK256_TRIE_MERKLE_VALUE, | 277 | | }, | 278 | | } | 279 | | } | 280 | | } | 281 | | } | 282 | 17.4k | } |
Unexecuted instantiation: _RINvMs_NtNtCseuYC0Zibziv_7smoldot4trie14calculate_rootNtB5_7NextKey10inject_keyINtNtNtNtCsaYZPK01V26L_4core4iter8adapters6copied6CopiedINtNtNtB1o_5slice4iter4IterhEEEB9_ Unexecuted instantiation: _RINvMs_NtNtCseuYC0Zibziv_7smoldot4trie14calculate_rootNtB5_7NextKey10inject_keyINtNtNtNtCsaYZPK01V26L_4core4iter8adapters6copied6CopiedINtNtNtB1o_5slice4iter4IterhEEECsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RINvMs_NtNtCseuYC0Zibziv_7smoldot4trie14calculate_rootNtB5_7NextKey10inject_keyINtNtNtNtCsaYZPK01V26L_4core4iter8adapters6copied6CopiedINtNtNtB1o_5slice4iter4IterhEEECscDgN54JpMGG_6author Unexecuted instantiation: _RINvMs_NtNtCseuYC0Zibziv_7smoldot4trie14calculate_rootNtB5_7NextKey10inject_keyINtNtNtNtCsaYZPK01V26L_4core4iter8adapters6copied6CopiedINtNtNtB1o_5slice4iter4IterhEEECsibGXYHQB8Ea_25json_rpc_general_requests |
283 | | } |
284 | | |
285 | | /// Request the value of the node with a specific key. Call [`StorageValue::inject`] to indicate |
286 | | /// the value. |
287 | | #[must_use] |
288 | | pub struct StorageValue { |
289 | | calculation: CalcInner, |
290 | | } |
291 | | |
292 | | impl StorageValue { |
293 | | /// Returns the key whose value is being requested. |
294 | 1.01k | pub fn key(&'_ self) -> impl Iterator<Item = u8> + '_ { |
295 | 1.01k | // This function can never be reached if the number of nibbles is uneven. |
296 | 1.01k | debug_assert_eq!(self.calculation.current_iter_node_full_key().count() % 2, 0); |
297 | 1.01k | nibbles_to_bytes_suffix_extend(self.calculation.current_iter_node_full_key()) |
298 | 1.01k | } _RNvMs0_NtNtCsN16ciHI6Qf_7smoldot4trie14calculate_rootNtB5_12StorageValue3key Line | Count | Source | 294 | 134 | pub fn key(&'_ self) -> impl Iterator<Item = u8> + '_ { | 295 | 134 | // This function can never be reached if the number of nibbles is uneven. | 296 | 134 | debug_assert_eq!(self.calculation.current_iter_node_full_key().count() % 2, 0); | 297 | 134 | nibbles_to_bytes_suffix_extend(self.calculation.current_iter_node_full_key()) | 298 | 134 | } |
_RNvMs0_NtNtCseuYC0Zibziv_7smoldot4trie14calculate_rootNtB5_12StorageValue3key Line | Count | Source | 294 | 882 | pub fn key(&'_ self) -> impl Iterator<Item = u8> + '_ { | 295 | 882 | // This function can never be reached if the number of nibbles is uneven. | 296 | 882 | debug_assert_eq!(self.calculation.current_iter_node_full_key().count() % 2, 0); | 297 | 882 | nibbles_to_bytes_suffix_extend(self.calculation.current_iter_node_full_key()) | 298 | 882 | } |
|
299 | | |
300 | | /// Indicates the storage value and advances the calculation. |
301 | 1.01k | pub fn inject( |
302 | 1.01k | mut self, |
303 | 1.01k | storage_value: Option<(impl AsRef<[u8]>, TrieEntryVersion)>, |
304 | 1.01k | ) -> RootMerkleValueCalculation { |
305 | 1.01k | let calculated_elem = self.calculation.stack.pop().unwrap(); |
306 | | |
307 | | // Due to some borrow checker troubles, we need to calculate the storage value |
308 | | // hash ahead of time if relevant. |
309 | 1.01k | let storage_value_hash = if let Some((value10 , TrieEntryVersion::V1)) = storage_value.as_ref() |
310 | | { |
311 | 10 | if value.as_ref().len() >= 33 { |
312 | 0 | Some(blake2_rfc::blake2b::blake2b(32, &[], value.as_ref())) |
313 | | } else { |
314 | 10 | None |
315 | | } |
316 | | } else { |
317 | 1.00k | None |
318 | | }; |
319 | | |
320 | | // Calculate the Merkle value of the node. |
321 | 1.01k | let merkle_value = trie_node::calculate_merkle_value( |
322 | | trie_node::Decoded { |
323 | 16.2k | children: array::from_fn(1.01k |n| calculated_elem.children[n].as_ref()), _RNCINvMs0_NtNtCsN16ciHI6Qf_7smoldot4trie14calculate_rootNtB8_12StorageValue6injectRINtNtCsdZExvAaxgia_5alloc3vec3VechEE0Bc_ Line | Count | Source | 323 | 160 | children: array::from_fn(|n| calculated_elem.children[n].as_ref()), |
_RNCINvMs0_NtNtCsN16ciHI6Qf_7smoldot4trie14calculate_rootNtB8_12StorageValue6injectRRShE0Bc_ Line | Count | Source | 323 | 320 | children: array::from_fn(|n| calculated_elem.children[n].as_ref()), |
_RNCINvMs0_NtNtCsN16ciHI6Qf_7smoldot4trie14calculate_rootNtB8_12StorageValue6injectRShE0Bc_ Line | Count | Source | 323 | 1.66k | children: array::from_fn(|n| calculated_elem.children[n].as_ref()), |
Unexecuted instantiation: _RNCINvMs0_NtNtCseuYC0Zibziv_7smoldot4trie14calculate_rootNtB8_12StorageValue6injectRINtNtCsdZExvAaxgia_5alloc3vec3VechEE0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCINvMs0_NtNtCseuYC0Zibziv_7smoldot4trie14calculate_rootNtB8_12StorageValue6injectRRShE0Bc_ _RNCINvMs0_NtNtCseuYC0Zibziv_7smoldot4trie14calculate_rootNtB8_12StorageValue6injectRShE0Bc_ Line | Count | Source | 323 | 14.1k | children: array::from_fn(|n| calculated_elem.children[n].as_ref()), |
Unexecuted instantiation: _RNCINvMs0_NtNtCseuYC0Zibziv_7smoldot4trie14calculate_rootNtB8_12StorageValue6injectRINtNtCsdZExvAaxgia_5alloc3vec3VechEE0CsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RNCINvMs0_NtNtCseuYC0Zibziv_7smoldot4trie14calculate_rootNtB8_12StorageValue6injectRINtNtCsdZExvAaxgia_5alloc3vec3VechEE0CscDgN54JpMGG_6author Unexecuted instantiation: _RNCINvMs0_NtNtCseuYC0Zibziv_7smoldot4trie14calculate_rootNtB8_12StorageValue6injectRINtNtCsdZExvAaxgia_5alloc3vec3VechEE0CsibGXYHQB8Ea_25json_rpc_general_requests |
324 | 1.01k | partial_key: calculated_elem.partial_key.iter().copied(), |
325 | 1.01k | storage_value: match (storage_value.as_ref(), storage_value_hash.as_ref()) { |
326 | 0 | (_, Some(storage_value_hash)) => trie_node::StorageValue::Hashed( |
327 | 0 | <&[u8; 32]>::try_from(storage_value_hash.as_bytes()) |
328 | 0 | .unwrap_or_else(|_| unreachable!()), Unexecuted instantiation: _RNCINvMs0_NtNtCsN16ciHI6Qf_7smoldot4trie14calculate_rootNtB8_12StorageValue6injectRINtNtCsdZExvAaxgia_5alloc3vec3VechEEs_0Bc_ Unexecuted instantiation: _RNCINvMs0_NtNtCsN16ciHI6Qf_7smoldot4trie14calculate_rootNtB8_12StorageValue6injectRRShEs_0Bc_ Unexecuted instantiation: _RNCINvMs0_NtNtCsN16ciHI6Qf_7smoldot4trie14calculate_rootNtB8_12StorageValue6injectRShEs_0Bc_ Unexecuted instantiation: _RNCINvMs0_NtNtCseuYC0Zibziv_7smoldot4trie14calculate_rootNtB8_12StorageValue6injectRINtNtCsdZExvAaxgia_5alloc3vec3VechEEs_0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCINvMs0_NtNtCseuYC0Zibziv_7smoldot4trie14calculate_rootNtB8_12StorageValue6injectRRShEs_0Bc_ Unexecuted instantiation: _RNCINvMs0_NtNtCseuYC0Zibziv_7smoldot4trie14calculate_rootNtB8_12StorageValue6injectRShEs_0Bc_ Unexecuted instantiation: _RNCINvMs0_NtNtCseuYC0Zibziv_7smoldot4trie14calculate_rootNtB8_12StorageValue6injectRINtNtCsdZExvAaxgia_5alloc3vec3VechEEs_0CsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RNCINvMs0_NtNtCseuYC0Zibziv_7smoldot4trie14calculate_rootNtB8_12StorageValue6injectRINtNtCsdZExvAaxgia_5alloc3vec3VechEEs_0CscDgN54JpMGG_6author Unexecuted instantiation: _RNCINvMs0_NtNtCseuYC0Zibziv_7smoldot4trie14calculate_rootNtB8_12StorageValue6injectRINtNtCsdZExvAaxgia_5alloc3vec3VechEEs_0CsibGXYHQB8Ea_25json_rpc_general_requests |
329 | 0 | ), |
330 | 851 | (Some((value, _)), _) => trie_node::StorageValue::Unhashed(value.as_ref()), |
331 | 165 | (None, _) => trie_node::StorageValue::None, |
332 | | }, |
333 | | }, |
334 | 1.01k | self.calculation.hash_function, |
335 | 1.01k | self.calculation.stack.is_empty(), |
336 | 1.01k | ) |
337 | 1.01k | .unwrap_or_else(|_| unreachable!()0 ); Unexecuted instantiation: _RNCINvMs0_NtNtCsN16ciHI6Qf_7smoldot4trie14calculate_rootNtB8_12StorageValue6injectRINtNtCsdZExvAaxgia_5alloc3vec3VechEEs0_0Bc_ Unexecuted instantiation: _RNCINvMs0_NtNtCsN16ciHI6Qf_7smoldot4trie14calculate_rootNtB8_12StorageValue6injectRRShEs0_0Bc_ Unexecuted instantiation: _RNCINvMs0_NtNtCsN16ciHI6Qf_7smoldot4trie14calculate_rootNtB8_12StorageValue6injectRShEs0_0Bc_ Unexecuted instantiation: _RNCINvMs0_NtNtCseuYC0Zibziv_7smoldot4trie14calculate_rootNtB8_12StorageValue6injectRINtNtCsdZExvAaxgia_5alloc3vec3VechEEs0_0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCINvMs0_NtNtCseuYC0Zibziv_7smoldot4trie14calculate_rootNtB8_12StorageValue6injectRRShEs0_0Bc_ Unexecuted instantiation: _RNCINvMs0_NtNtCseuYC0Zibziv_7smoldot4trie14calculate_rootNtB8_12StorageValue6injectRShEs0_0Bc_ Unexecuted instantiation: _RNCINvMs0_NtNtCseuYC0Zibziv_7smoldot4trie14calculate_rootNtB8_12StorageValue6injectRINtNtCsdZExvAaxgia_5alloc3vec3VechEEs0_0CsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RNCINvMs0_NtNtCseuYC0Zibziv_7smoldot4trie14calculate_rootNtB8_12StorageValue6injectRINtNtCsdZExvAaxgia_5alloc3vec3VechEEs0_0CscDgN54JpMGG_6author Unexecuted instantiation: _RNCINvMs0_NtNtCseuYC0Zibziv_7smoldot4trie14calculate_rootNtB8_12StorageValue6injectRINtNtCsdZExvAaxgia_5alloc3vec3VechEEs0_0CsibGXYHQB8Ea_25json_rpc_general_requests |
338 | | |
339 | | // Insert Merkle value into the stack, or, if no parent, we have our result! |
340 | 1.01k | if let Some(parent985 ) = self.calculation.stack.last_mut() { |
341 | 985 | parent.children.push(Some(merkle_value)); |
342 | 985 | self.calculation.next() |
343 | | } else { |
344 | | // Because we pass `is_root_node: true` in the calculation above, it is guaranteed |
345 | | // that the Merkle value is always 32 bytes. |
346 | 31 | let hash = *<&[u8; 32]>::try_from(merkle_value.as_ref()).unwrap(); |
347 | 31 | RootMerkleValueCalculation::Finished { hash } |
348 | | } |
349 | 1.01k | } _RINvMs0_NtNtCsN16ciHI6Qf_7smoldot4trie14calculate_rootNtB6_12StorageValue6injectRINtNtCsdZExvAaxgia_5alloc3vec3VechEEBa_ Line | Count | Source | 301 | 10 | pub fn inject( | 302 | 10 | mut self, | 303 | 10 | storage_value: Option<(impl AsRef<[u8]>, TrieEntryVersion)>, | 304 | 10 | ) -> RootMerkleValueCalculation { | 305 | 10 | let calculated_elem = self.calculation.stack.pop().unwrap(); | 306 | | | 307 | | // Due to some borrow checker troubles, we need to calculate the storage value | 308 | | // hash ahead of time if relevant. | 309 | 10 | let storage_value_hash = if let Some((value4 , TrieEntryVersion::V1)) = storage_value.as_ref() | 310 | | { | 311 | 4 | if value.as_ref().len() >= 33 { | 312 | 0 | Some(blake2_rfc::blake2b::blake2b(32, &[], value.as_ref())) | 313 | | } else { | 314 | 4 | None | 315 | | } | 316 | | } else { | 317 | 6 | None | 318 | | }; | 319 | | | 320 | | // Calculate the Merkle value of the node. | 321 | 10 | let merkle_value = trie_node::calculate_merkle_value( | 322 | | trie_node::Decoded { | 323 | 10 | children: array::from_fn(|n| calculated_elem.children[n].as_ref()), | 324 | 10 | partial_key: calculated_elem.partial_key.iter().copied(), | 325 | 10 | storage_value: match (storage_value.as_ref(), storage_value_hash.as_ref()) { | 326 | 0 | (_, Some(storage_value_hash)) => trie_node::StorageValue::Hashed( | 327 | 0 | <&[u8; 32]>::try_from(storage_value_hash.as_bytes()) | 328 | 0 | .unwrap_or_else(|_| unreachable!()), | 329 | 0 | ), | 330 | 8 | (Some((value, _)), _) => trie_node::StorageValue::Unhashed(value.as_ref()), | 331 | 2 | (None, _) => trie_node::StorageValue::None, | 332 | | }, | 333 | | }, | 334 | 10 | self.calculation.hash_function, | 335 | 10 | self.calculation.stack.is_empty(), | 336 | 10 | ) | 337 | 10 | .unwrap_or_else(|_| unreachable!()); | 338 | | | 339 | | // Insert Merkle value into the stack, or, if no parent, we have our result! | 340 | 10 | if let Some(parent4 ) = self.calculation.stack.last_mut() { | 341 | 4 | parent.children.push(Some(merkle_value)); | 342 | 4 | self.calculation.next() | 343 | | } else { | 344 | | // Because we pass `is_root_node: true` in the calculation above, it is guaranteed | 345 | | // that the Merkle value is always 32 bytes. | 346 | 6 | let hash = *<&[u8; 32]>::try_from(merkle_value.as_ref()).unwrap(); | 347 | 6 | RootMerkleValueCalculation::Finished { hash } | 348 | | } | 349 | 10 | } |
_RINvMs0_NtNtCsN16ciHI6Qf_7smoldot4trie14calculate_rootNtB6_12StorageValue6injectRRShEBa_ Line | Count | Source | 301 | 20 | pub fn inject( | 302 | 20 | mut self, | 303 | 20 | storage_value: Option<(impl AsRef<[u8]>, TrieEntryVersion)>, | 304 | 20 | ) -> RootMerkleValueCalculation { | 305 | 20 | let calculated_elem = self.calculation.stack.pop().unwrap(); | 306 | | | 307 | | // Due to some borrow checker troubles, we need to calculate the storage value | 308 | | // hash ahead of time if relevant. | 309 | 20 | let storage_value_hash = if let Some((value6 , TrieEntryVersion::V1)) = storage_value.as_ref() | 310 | | { | 311 | 6 | if value.as_ref().len() >= 33 { | 312 | 0 | Some(blake2_rfc::blake2b::blake2b(32, &[], value.as_ref())) | 313 | | } else { | 314 | 6 | None | 315 | | } | 316 | | } else { | 317 | 14 | None | 318 | | }; | 319 | | | 320 | | // Calculate the Merkle value of the node. | 321 | 20 | let merkle_value = trie_node::calculate_merkle_value( | 322 | | trie_node::Decoded { | 323 | 20 | children: array::from_fn(|n| calculated_elem.children[n].as_ref()), | 324 | 20 | partial_key: calculated_elem.partial_key.iter().copied(), | 325 | 20 | storage_value: match (storage_value.as_ref(), storage_value_hash.as_ref()) { | 326 | 0 | (_, Some(storage_value_hash)) => trie_node::StorageValue::Hashed( | 327 | 0 | <&[u8; 32]>::try_from(storage_value_hash.as_bytes()) | 328 | 0 | .unwrap_or_else(|_| unreachable!()), | 329 | 0 | ), | 330 | 20 | (Some((value, _)), _) => trie_node::StorageValue::Unhashed(value.as_ref()), | 331 | 0 | (None, _) => trie_node::StorageValue::None, | 332 | | }, | 333 | | }, | 334 | 20 | self.calculation.hash_function, | 335 | 20 | self.calculation.stack.is_empty(), | 336 | 20 | ) | 337 | 20 | .unwrap_or_else(|_| unreachable!()); | 338 | | | 339 | | // Insert Merkle value into the stack, or, if no parent, we have our result! | 340 | 20 | if let Some(parent17 ) = self.calculation.stack.last_mut() { | 341 | 17 | parent.children.push(Some(merkle_value)); | 342 | 17 | self.calculation.next() | 343 | | } else { | 344 | | // Because we pass `is_root_node: true` in the calculation above, it is guaranteed | 345 | | // that the Merkle value is always 32 bytes. | 346 | 3 | let hash = *<&[u8; 32]>::try_from(merkle_value.as_ref()).unwrap(); | 347 | 3 | RootMerkleValueCalculation::Finished { hash } | 348 | | } | 349 | 20 | } |
_RINvMs0_NtNtCsN16ciHI6Qf_7smoldot4trie14calculate_rootNtB6_12StorageValue6injectRShEBa_ Line | Count | Source | 301 | 104 | pub fn inject( | 302 | 104 | mut self, | 303 | 104 | storage_value: Option<(impl AsRef<[u8]>, TrieEntryVersion)>, | 304 | 104 | ) -> RootMerkleValueCalculation { | 305 | 104 | let calculated_elem = self.calculation.stack.pop().unwrap(); | 306 | | | 307 | | // Due to some borrow checker troubles, we need to calculate the storage value | 308 | | // hash ahead of time if relevant. | 309 | 104 | let storage_value_hash = if let Some((value0 , TrieEntryVersion::V1)) = storage_value.as_ref() | 310 | | { | 311 | 0 | if value.as_ref().len() >= 33 { | 312 | 0 | Some(blake2_rfc::blake2b::blake2b(32, &[], value.as_ref())) | 313 | | } else { | 314 | 0 | None | 315 | | } | 316 | | } else { | 317 | 104 | None | 318 | | }; | 319 | | | 320 | | // Calculate the Merkle value of the node. | 321 | 104 | let merkle_value = trie_node::calculate_merkle_value( | 322 | | trie_node::Decoded { | 323 | 104 | children: array::from_fn(|n| calculated_elem.children[n].as_ref()), | 324 | 104 | partial_key: calculated_elem.partial_key.iter().copied(), | 325 | 104 | storage_value: match (storage_value.as_ref(), storage_value_hash.as_ref()) { | 326 | 0 | (_, Some(storage_value_hash)) => trie_node::StorageValue::Hashed( | 327 | 0 | <&[u8; 32]>::try_from(storage_value_hash.as_bytes()) | 328 | 0 | .unwrap_or_else(|_| unreachable!()), | 329 | 0 | ), | 330 | 88 | (Some((value, _)), _) => trie_node::StorageValue::Unhashed(value.as_ref()), | 331 | 16 | (None, _) => trie_node::StorageValue::None, | 332 | | }, | 333 | | }, | 334 | 104 | self.calculation.hash_function, | 335 | 104 | self.calculation.stack.is_empty(), | 336 | 104 | ) | 337 | 104 | .unwrap_or_else(|_| unreachable!()); | 338 | | | 339 | | // Insert Merkle value into the stack, or, if no parent, we have our result! | 340 | 104 | if let Some(parent103 ) = self.calculation.stack.last_mut() { | 341 | 103 | parent.children.push(Some(merkle_value)); | 342 | 103 | self.calculation.next() | 343 | | } else { | 344 | | // Because we pass `is_root_node: true` in the calculation above, it is guaranteed | 345 | | // that the Merkle value is always 32 bytes. | 346 | 1 | let hash = *<&[u8; 32]>::try_from(merkle_value.as_ref()).unwrap(); | 347 | 1 | RootMerkleValueCalculation::Finished { hash } | 348 | | } | 349 | 104 | } |
Unexecuted instantiation: _RINvMs0_NtNtCseuYC0Zibziv_7smoldot4trie14calculate_rootNtB6_12StorageValue6injectRINtNtCsdZExvAaxgia_5alloc3vec3VechEECsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RINvMs0_NtNtCseuYC0Zibziv_7smoldot4trie14calculate_rootNtB6_12StorageValue6injectRRShEBa_ _RINvMs0_NtNtCseuYC0Zibziv_7smoldot4trie14calculate_rootNtB6_12StorageValue6injectRShEBa_ Line | Count | Source | 301 | 882 | pub fn inject( | 302 | 882 | mut self, | 303 | 882 | storage_value: Option<(impl AsRef<[u8]>, TrieEntryVersion)>, | 304 | 882 | ) -> RootMerkleValueCalculation { | 305 | 882 | let calculated_elem = self.calculation.stack.pop().unwrap(); | 306 | | | 307 | | // Due to some borrow checker troubles, we need to calculate the storage value | 308 | | // hash ahead of time if relevant. | 309 | 882 | let storage_value_hash = if let Some((value0 , TrieEntryVersion::V1)) = storage_value.as_ref() | 310 | | { | 311 | 0 | if value.as_ref().len() >= 33 { | 312 | 0 | Some(blake2_rfc::blake2b::blake2b(32, &[], value.as_ref())) | 313 | | } else { | 314 | 0 | None | 315 | | } | 316 | | } else { | 317 | 882 | None | 318 | | }; | 319 | | | 320 | | // Calculate the Merkle value of the node. | 321 | 882 | let merkle_value = trie_node::calculate_merkle_value( | 322 | | trie_node::Decoded { | 323 | 882 | children: array::from_fn(|n| calculated_elem.children[n].as_ref()), | 324 | 882 | partial_key: calculated_elem.partial_key.iter().copied(), | 325 | 882 | storage_value: match (storage_value.as_ref(), storage_value_hash.as_ref()) { | 326 | 0 | (_, Some(storage_value_hash)) => trie_node::StorageValue::Hashed( | 327 | 0 | <&[u8; 32]>::try_from(storage_value_hash.as_bytes()) | 328 | 0 | .unwrap_or_else(|_| unreachable!()), | 329 | 0 | ), | 330 | 735 | (Some((value, _)), _) => trie_node::StorageValue::Unhashed(value.as_ref()), | 331 | 147 | (None, _) => trie_node::StorageValue::None, | 332 | | }, | 333 | | }, | 334 | 882 | self.calculation.hash_function, | 335 | 882 | self.calculation.stack.is_empty(), | 336 | 882 | ) | 337 | 882 | .unwrap_or_else(|_| unreachable!()); | 338 | | | 339 | | // Insert Merkle value into the stack, or, if no parent, we have our result! | 340 | 882 | if let Some(parent861 ) = self.calculation.stack.last_mut() { | 341 | 861 | parent.children.push(Some(merkle_value)); | 342 | 861 | self.calculation.next() | 343 | | } else { | 344 | | // Because we pass `is_root_node: true` in the calculation above, it is guaranteed | 345 | | // that the Merkle value is always 32 bytes. | 346 | 21 | let hash = *<&[u8; 32]>::try_from(merkle_value.as_ref()).unwrap(); | 347 | 21 | RootMerkleValueCalculation::Finished { hash } | 348 | | } | 349 | 882 | } |
Unexecuted instantiation: _RINvMs0_NtNtCseuYC0Zibziv_7smoldot4trie14calculate_rootNtB6_12StorageValue6injectRINtNtCsdZExvAaxgia_5alloc3vec3VechEECsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RINvMs0_NtNtCseuYC0Zibziv_7smoldot4trie14calculate_rootNtB6_12StorageValue6injectRINtNtCsdZExvAaxgia_5alloc3vec3VechEECscDgN54JpMGG_6author Unexecuted instantiation: _RINvMs0_NtNtCseuYC0Zibziv_7smoldot4trie14calculate_rootNtB6_12StorageValue6injectRINtNtCsdZExvAaxgia_5alloc3vec3VechEECsibGXYHQB8Ea_25json_rpc_general_requests |
350 | | } |
351 | | |
352 | | #[cfg(test)] |
353 | | mod tests { |
354 | | use crate::trie::{HashFunction, TrieEntryVersion}; |
355 | | use alloc::collections::BTreeMap; |
356 | | use core::ops::Bound; |
357 | | |
358 | 8 | fn calculate_root(version: TrieEntryVersion, trie: &BTreeMap<Vec<u8>, Vec<u8>>) -> [u8; 32] { |
359 | 8 | let mut calculation = super::root_merkle_value(HashFunction::Blake2); |
360 | | |
361 | 196 | loop { |
362 | 196 | match calculation { |
363 | 8 | super::RootMerkleValueCalculation::Finished { hash } => { |
364 | 8 | return hash; |
365 | | } |
366 | 178 | super::RootMerkleValueCalculation::NextKey(next_key) => { |
367 | 178 | let lower_bound = if next_key.or_equal() { |
368 | 178 | Bound::Included(next_key.key_before().collect::<Vec<_>>()) |
369 | | } else { |
370 | 0 | Bound::Excluded(next_key.key_before().collect::<Vec<_>>()) |
371 | | }; |
372 | | |
373 | 178 | let k = trie |
374 | 178 | .range((lower_bound, Bound::Unbounded)) |
375 | 178 | .next() |
376 | 178 | .filter(|(k, _)| { |
377 | 52 | k.iter() |
378 | 52 | .copied() |
379 | 52 | .zip(next_key.prefix()) |
380 | 52 | .all(|(a, b)| a == b32 ) |
381 | 178 | }) |
382 | 178 | .map(|(k, _)| k20 ); |
383 | 178 | |
384 | 178 | calculation = next_key.inject_key(k.map(|k| k.iter().copied()20 )); |
385 | | } |
386 | 10 | super::RootMerkleValueCalculation::StorageValue(value) => { |
387 | 10 | let key = value.key().collect::<Vec<u8>>(); |
388 | 10 | calculation = value.inject(trie.get(&key).map(|v| (v, version)8 )); |
389 | 10 | } |
390 | | } |
391 | | } |
392 | 8 | } |
393 | | |
394 | | #[test] |
395 | 1 | fn trie_root_one_node() { |
396 | 1 | let mut trie = BTreeMap::new(); |
397 | 1 | trie.insert(b"abcd".to_vec(), b"hello world".to_vec()); |
398 | 1 | |
399 | 1 | let expected = [ |
400 | 1 | 122, 177, 134, 89, 211, 178, 120, 158, 242, 64, 13, 16, 113, 4, 199, 212, 251, 147, |
401 | 1 | 208, 109, 154, 182, 168, 182, 65, 165, 222, 124, 63, 236, 200, 81, |
402 | 1 | ]; |
403 | 1 | |
404 | 1 | assert_eq!(calculate_root(TrieEntryVersion::V0, &trie), &expected[..]); |
405 | 1 | assert_eq!(calculate_root(TrieEntryVersion::V1, &trie), &expected[..]); |
406 | 1 | } |
407 | | |
408 | | #[test] |
409 | 1 | fn trie_root_empty() { |
410 | 1 | let trie = BTreeMap::new(); |
411 | 1 | let expected = blake2_rfc::blake2b::blake2b(32, &[], &[0x0]); |
412 | 1 | assert_eq!( |
413 | 1 | calculate_root(TrieEntryVersion::V0, &trie), |
414 | 1 | expected.as_bytes() |
415 | 1 | ); |
416 | 1 | assert_eq!( |
417 | 1 | calculate_root(TrieEntryVersion::V1, &trie), |
418 | 1 | expected.as_bytes() |
419 | 1 | ); |
420 | 1 | } |
421 | | |
422 | | #[test] |
423 | 1 | fn trie_root_single_tuple() { |
424 | 1 | let mut trie = BTreeMap::new(); |
425 | 1 | trie.insert([0xaa].to_vec(), [0xbb].to_vec()); |
426 | 1 | |
427 | 1 | let expected = blake2_rfc::blake2b::blake2b( |
428 | 1 | 32, |
429 | 1 | &[], |
430 | 1 | &[ |
431 | 1 | 0x42, // leaf 0x40 (2^6) with (+) key of 2 nibbles (0x02) |
432 | 1 | 0xaa, // key data |
433 | 1 | 1 << 2, // length of value in bytes as Compact |
434 | 1 | 0xbb, // value data |
435 | 1 | ], |
436 | 1 | ); |
437 | 1 | |
438 | 1 | assert_eq!( |
439 | 1 | calculate_root(TrieEntryVersion::V0, &trie), |
440 | 1 | expected.as_bytes() |
441 | 1 | ); |
442 | 1 | assert_eq!( |
443 | 1 | calculate_root(TrieEntryVersion::V1, &trie), |
444 | 1 | expected.as_bytes() |
445 | 1 | ); |
446 | 1 | } |
447 | | |
448 | | #[test] |
449 | 1 | fn trie_root_example() { |
450 | 1 | let mut trie = BTreeMap::new(); |
451 | 1 | trie.insert([0x48, 0x19].to_vec(), [0xfe].to_vec()); |
452 | 1 | trie.insert([0x13, 0x14].to_vec(), [0xff].to_vec()); |
453 | 1 | |
454 | 1 | let ex = vec![ |
455 | 1 | 0x80, // branch, no value (0b_10..) no nibble |
456 | 1 | 0x12, // slots 1 & 4 are taken from 0-7 |
457 | 1 | 0x00, // no slots from 8-15 |
458 | 1 | 0x05 << 2, // first slot: LEAF, 5 bytes long. |
459 | 1 | 0x43, // leaf 0x40 with 3 nibbles |
460 | 1 | 0x03, // first nibble |
461 | 1 | 0x14, // second & third nibble |
462 | 1 | 0x01 << 2, // 1 byte data |
463 | 1 | 0xff, // value data |
464 | 1 | 0x05 << 2, // second slot: LEAF, 5 bytes long. |
465 | 1 | 0x43, // leaf with 3 nibbles |
466 | 1 | 0x08, // first nibble |
467 | 1 | 0x19, // second & third nibble |
468 | 1 | 0x01 << 2, // 1 byte data |
469 | 1 | 0xfe, // value data |
470 | 1 | ]; |
471 | 1 | |
472 | 1 | let expected = blake2_rfc::blake2b::blake2b(32, &[], &ex); |
473 | 1 | assert_eq!( |
474 | 1 | calculate_root(TrieEntryVersion::V0, &trie), |
475 | 1 | expected.as_bytes() |
476 | 1 | ); |
477 | 1 | assert_eq!( |
478 | 1 | calculate_root(TrieEntryVersion::V1, &trie), |
479 | 1 | expected.as_bytes() |
480 | 1 | ); |
481 | 1 | } |
482 | | } |