/__w/smoldot/smoldot/repo/lib/src/executor/trie_root_calculator.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 | | //! Given as input a partial base trie and a diff, calculates the new root of the trie. |
19 | | //! |
20 | | //! # Implementation |
21 | | //! |
22 | | //! The algorithm for calculating the trie root is roughly: |
23 | | //! |
24 | | //! ```notrust |
25 | | //! TrieRoot = ClosestDescendantMerkleValue(∅, False) || EmptyTrieRootHash |
26 | | //! |
27 | | //! ClosestDescendantMerkleValue(Key, ForceRecalculate) = |
28 | | //! If !ForceRecalculate AND !DiffContainsEntryWithPrefix(Key) |
29 | | //! MaybeMerkleValue := BaseTrieClosestDescendantMerkleValue(Key) |
30 | | //! If MaybeMerkleValue |
31 | | //! return MaybeMerkleValue |
32 | | //! |
33 | | //! Btcd := BaseTrieClosestDescendant(Key) |
34 | | //! MaybeNodeKey := LongestCommonDenominator(Btcd, ...DiffInsertsNodesWithPrefix(Key)) |
35 | | //! MaybeChildren := Array(ClosestDescendantMerkleValue(Concat(MaybeNodeKey, 0), MaybeNodeKey != Btcd), ..., ClosestDescendantMerkleValue(Concat(MaybeNodeKey, 15), MaybeNodeKey != Btcd)) |
36 | | //! MaybeStorageValue := DiffInserts(MaybeNodeKey) || (BaseTrieStorageValue(MaybeNodeKey) - DiffErases(MaybeNodeKey)) |
37 | | //! |
38 | | //! If MaybeStorageValue = ∅ AND NumChildren(MaybeChildren) == 0 |
39 | | //! ∅ |
40 | | //! ElseIf NumChildren(MaybeChildren) == 1 AND BaseTrieStorageValue(MaybeNodeKey) != ∅ AND MaybeStorageValue = ∅ |
41 | | //! # Because the partial key of the child has changed, we have to recalculate it. |
42 | | //! ClosestDescendantMerkleValue(ChildThatExists(MaybeChildren), True) |
43 | | //! ElseIf NumChildren(MaybeChildren) == 1 AND BaseTrieStorageValue(MaybeNodeKey) = ∅ AND MaybeStorageValue = ∅ |
44 | | //! ChildThatExists(MaybeChildren) |
45 | | //! Else |
46 | | //! Encode(MaybeStorageValue, MaybeChildren) |
47 | | //! ``` |
48 | | //! |
49 | | //! The public API functions are thus `BaseTrieClosestDescendant`, |
50 | | //! `BaseTrieClosestDescendantMerkleValue`, and `BaseTrieStorageValue`. |
51 | | //! |
52 | | //! The algorithm above is recursive. In order to implement it, we instead maintain a stack of |
53 | | //! nodes that are currently being calculated. |
54 | | //! |
55 | | |
56 | | use alloc::{boxed::Box, vec::Vec}; |
57 | | use core::{array, iter, ops}; |
58 | | |
59 | | use super::storage_diff::TrieDiff; |
60 | | use crate::trie; |
61 | | |
62 | | pub use trie::{Nibble, TrieEntryVersion}; |
63 | | |
64 | | mod tests; |
65 | | |
66 | | /// Configuration for [`trie_root_calculator`]. |
67 | | pub struct Config { |
68 | | /// Diff that is being applied on top of the base trie. |
69 | | pub diff: TrieDiff, |
70 | | |
71 | | /// Version to use for the storage values written by [`Config::diff`]. |
72 | | pub diff_trie_entries_version: TrieEntryVersion, |
73 | | |
74 | | /// Depth level of the deepest node whose value needs to be calculated. The root node has a |
75 | | /// depth level of 1, its children a depth level of 2, etc. |
76 | | /// |
77 | | /// Used as a hint to pre-allocate a container. Getting the value wrong has no ill |
78 | | /// consequence except a very small performance hit. |
79 | | pub max_trie_recalculation_depth_hint: usize, |
80 | | } |
81 | | |
82 | | /// Starts a new calculation. |
83 | 32.7k | pub fn trie_root_calculator(config: Config) -> InProgress { |
84 | 32.7k | Box::new(Inner { |
85 | 32.7k | stack: Vec::with_capacity(config.max_trie_recalculation_depth_hint), |
86 | 32.7k | diff: config.diff, |
87 | 32.7k | diff_trie_entries_version: config.diff_trie_entries_version, |
88 | 32.7k | }) |
89 | 32.7k | .next() |
90 | 32.7k | } _RNvNtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculator20trie_root_calculator Line | Count | Source | 83 | 32.7k | pub fn trie_root_calculator(config: Config) -> InProgress { | 84 | 32.7k | Box::new(Inner { | 85 | 32.7k | stack: Vec::with_capacity(config.max_trie_recalculation_depth_hint), | 86 | 32.7k | diff: config.diff, | 87 | 32.7k | diff_trie_entries_version: config.diff_trie_entries_version, | 88 | 32.7k | }) | 89 | 32.7k | .next() | 90 | 32.7k | } |
Unexecuted instantiation: _RNvNtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculator20trie_root_calculator |
91 | | |
92 | | /// Trie root calculation in progress. |
93 | | pub enum InProgress { |
94 | | /// Calculation has successfully finished. |
95 | | Finished { |
96 | | /// Calculated trie root hash. |
97 | | trie_root_hash: [u8; 32], |
98 | | }, |
99 | | /// See [`ClosestDescendant`]. |
100 | | ClosestDescendant(ClosestDescendant), |
101 | | /// See [`StorageValue`]. |
102 | | StorageValue(StorageValue), |
103 | | /// See [`ClosestDescendantMerkleValue`]. |
104 | | ClosestDescendantMerkleValue(ClosestDescendantMerkleValue), |
105 | | /// See [`TrieNodeInsertUpdateEvent`]. |
106 | | // TODO: consider guaranteeing an ordering in the events? |
107 | | TrieNodeInsertUpdateEvent(TrieNodeInsertUpdateEvent), |
108 | | /// See [`TrieNodeRemoveEvent`]. |
109 | | TrieNodeRemoveEvent(TrieNodeRemoveEvent), |
110 | | } |
111 | | |
112 | | /// In order to continue the calculation, must find in the base trie the closest descendant |
113 | | /// (including branch node) to a certain key in the trie. This can be equal to the requested key |
114 | | /// itself. |
115 | | pub struct ClosestDescendant { |
116 | | inner: Box<Inner>, |
117 | | /// Extra nibbles to append at the end of what `self.key()` returns. |
118 | | key_extra_nibbles: Vec<Nibble>, |
119 | | /// `Some` if the diff inserts a value that is equal or a descendant of `self.key()`. If |
120 | | /// `Some`, contains the least common denominator shared amongst all these insertions. |
121 | | diff_inserts_lcd: Option<Vec<Nibble>>, |
122 | | } |
123 | | |
124 | | impl ClosestDescendant { |
125 | | /// Returns an iterator of slices, which, when joined together, form the full key of the trie |
126 | | /// node whose closest descendant must be fetched. |
127 | 8.76M | pub fn key(&'_ self) -> impl Iterator<Item = impl AsRef<[Nibble]> + '_> + '_ { |
128 | 8.76M | self.inner |
129 | 8.76M | .current_node_full_key() |
130 | 8.76M | .map(either::Left) |
131 | 8.76M | .chain(iter::once(either::Right(&self.key_extra_nibbles))) |
132 | 8.76M | } _RNvMNtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB2_17ClosestDescendant3key Line | Count | Source | 127 | 8.76M | pub fn key(&'_ self) -> impl Iterator<Item = impl AsRef<[Nibble]> + '_> + '_ { | 128 | 8.76M | self.inner | 129 | 8.76M | .current_node_full_key() | 130 | 8.76M | .map(either::Left) | 131 | 8.76M | .chain(iter::once(either::Right(&self.key_extra_nibbles))) | 132 | 8.76M | } |
Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB2_17ClosestDescendant3key |
133 | | |
134 | | /// Returns the same value as [`ClosestDescendant::key`] but as a `Vec`. |
135 | 8.75M | pub fn key_as_vec(&self) -> Vec<Nibble> { |
136 | 48.0M | self.key().fold(Vec::new(), |mut a, b| { |
137 | 48.0M | a.extend_from_slice(b.as_ref()); |
138 | 48.0M | a |
139 | 48.0M | }) _RNCNvMNtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB4_17ClosestDescendant10key_as_vec0B8_ Line | Count | Source | 136 | 48.0M | self.key().fold(Vec::new(), |mut a, b| { | 137 | 48.0M | a.extend_from_slice(b.as_ref()); | 138 | 48.0M | a | 139 | 48.0M | }) |
Unexecuted instantiation: _RNCNvMNtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB4_17ClosestDescendant10key_as_vec0B8_ |
140 | 8.75M | } _RNvMNtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB2_17ClosestDescendant10key_as_vec Line | Count | Source | 135 | 8.75M | pub fn key_as_vec(&self) -> Vec<Nibble> { | 136 | 8.75M | self.key().fold(Vec::new(), |mut a, b| { | 137 | | a.extend_from_slice(b.as_ref()); | 138 | | a | 139 | 8.75M | }) | 140 | 8.75M | } |
Unexecuted instantiation: _RNvMNtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB2_17ClosestDescendant10key_as_vec |
141 | | |
142 | | /// Indicates the key of the closest descendant to the key indicated by |
143 | | /// [`ClosestDescendant::key`] and resume the calculation. |
144 | 5.88M | pub fn inject( |
145 | 5.88M | mut self, |
146 | 5.88M | closest_descendant: Option<impl Iterator<Item = Nibble>>, |
147 | 5.88M | ) -> InProgress { |
148 | 5.88M | // We are after a call to `BaseTrieClosestDescendant`. |
149 | 5.88M | debug_assert!(self |
150 | 5.88M | .inner |
151 | 5.88M | .stack |
152 | 5.88M | .last() |
153 | 5.88M | .map_or(true, |n| n.children.len() != 165.84M )); Unexecuted instantiation: _RNCINvMNtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB5_17ClosestDescendant6injectINtNtNtB9_4trie12proof_decode12EntryKeyIterINtNtCsdZExvAaxgia_5alloc3vec3VechEEEs_0B9_ _RNCINvMNtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB5_17ClosestDescendant6injectINtNtNtNtCsaYZPK01V26L_4core4iter7sources5empty5EmptyNtNtNtB9_4trie6nibble6NibbleEEs_0B9_ Line | Count | Source | 153 | 16 | .map_or(true, |n| n.children.len() != 16)); |
_RNCINvMNtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB5_17ClosestDescendant6injectINtNtNtNtCsaYZPK01V26L_4core4iter8adapters7flatten7FlatMapINtNtB1z_5chain5ChainINtNtB1z_4skip4SkipINtNtNtB1B_7sources10successors10SuccessorsjNCNvMNtNtB9_4trie14trie_structureINtB3R_13TrieStructureTINtNtB1D_6option6OptionTINtNtCsdZExvAaxgia_5alloc3vec3VechENtB3T_16TrieEntryVersionEEIB4H_NtNtB3T_9trie_node17MerkleValueOutputEEE9node_path0EEINtNtB39_4once4OncejEEIB2r_INtNtB1z_3map3MapINtB4J_8IntoIterTjNtNtB3T_6nibble6NibbleEENCNCNvB3Q_13node_full_key00EINtNtB1z_6cloned6ClonedINtNtNtB1D_5slice4iter4IterB7Z_EEENCB8r_0EEs_0B9_ Line | Count | Source | 153 | 5.83M | .map_or(true, |n| n.children.len() != 16)); |
_RNCINvMNtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB5_17ClosestDescendant6injectNtNtNtB9_4trie13branch_search21BranchTrieNodeKeyIterEs_0B9_ Line | Count | Source | 153 | 8.22k | .map_or(true, |n| n.children.len() != 16)); |
Unexecuted instantiation: _RNCINvMNtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB5_17ClosestDescendant6injectINtNtNtB9_4trie12proof_decode12EntryKeyIterINtNtNtCsdZExvAaxgia_5alloc3vec9into_iter8IntoIterhEEEs_0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCINvMNtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB5_17ClosestDescendant6injectINtNtNtB9_4trie12proof_decode12EntryKeyIterRShEEs_0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCINvMNtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB5_17ClosestDescendant6injectINtNtNtNtCsaYZPK01V26L_4core4iter8adapters3map3MapINtNtNtCsdZExvAaxgia_5alloc3vec9into_iter8IntoIterhENCNCNvMNtNtB9_8database11full_sqliteNtB3g_18SqliteFullDatabase20to_chain_informations_00EEs_0B9_ Unexecuted instantiation: _RNCINvMNtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB5_17ClosestDescendant6injectINtNtNtB9_4trie12proof_decode12EntryKeyIterINtNtNtCsdZExvAaxgia_5alloc3vec9into_iter8IntoIterhEEEs_0CsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RNCINvMNtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB5_17ClosestDescendant6injectINtNtNtNtCsaYZPK01V26L_4core4iter8adapters3map3MapINtNtNtCsdZExvAaxgia_5alloc3vec9into_iter8IntoIterhENCNCNCNvMs_NtCsiUjFBJteJ7x_17smoldot_full_node17consensus_serviceNtB3k_14SyncBackground12author_block0s6_00EEs_0CsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RNCINvMNtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB5_17ClosestDescendant6injectINtNtNtNtCsaYZPK01V26L_4core4iter8adapters3map3MapINtNtNtCsdZExvAaxgia_5alloc3vec9into_iter8IntoIterhENCNCNCNvNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service12runtime_call0s7_00EEs_0CsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RNCINvMNtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB5_17ClosestDescendant6injectINtNtNtNtCsaYZPK01V26L_4core4iter8adapters3map3MapINtNtNtCsdZExvAaxgia_5alloc3vec9into_iter8IntoIterhENCNCNCNvNtNtCsiUjFBJteJ7x_17smoldot_full_node16json_rpc_service16requests_handler22spawn_requests_handler0se_00EEs_0B3l_ Unexecuted instantiation: _RNCINvMNtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB5_17ClosestDescendant6injectINtNtNtB9_4trie12proof_decode12EntryKeyIterINtNtNtCsdZExvAaxgia_5alloc3vec9into_iter8IntoIterhEEEs_0CscDgN54JpMGG_6author Unexecuted instantiation: _RNCINvMNtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB5_17ClosestDescendant6injectINtNtNtNtCsaYZPK01V26L_4core4iter8adapters3map3MapINtNtNtCsdZExvAaxgia_5alloc3vec9into_iter8IntoIterhENCNCNCNvMs_NtCsiUjFBJteJ7x_17smoldot_full_node17consensus_serviceNtB3k_14SyncBackground12author_block0s6_00EEs_0CscDgN54JpMGG_6author Unexecuted instantiation: _RNCINvMNtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB5_17ClosestDescendant6injectINtNtNtNtCsaYZPK01V26L_4core4iter8adapters3map3MapINtNtNtCsdZExvAaxgia_5alloc3vec9into_iter8IntoIterhENCNCNCNvNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service12runtime_call0s7_00EEs_0CscDgN54JpMGG_6author Unexecuted instantiation: _RNCINvMNtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB5_17ClosestDescendant6injectINtNtNtB9_4trie12proof_decode12EntryKeyIterINtNtNtCsdZExvAaxgia_5alloc3vec9into_iter8IntoIterhEEEs_0CsibGXYHQB8Ea_25json_rpc_general_requests Unexecuted instantiation: _RNCINvMNtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB5_17ClosestDescendant6injectINtNtNtNtCsaYZPK01V26L_4core4iter8adapters3map3MapINtNtNtCsdZExvAaxgia_5alloc3vec9into_iter8IntoIterhENCNCNCNvMs_NtCsiUjFBJteJ7x_17smoldot_full_node17consensus_serviceNtB3k_14SyncBackground12author_block0s6_00EEs_0CsibGXYHQB8Ea_25json_rpc_general_requests Unexecuted instantiation: _RNCINvMNtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB5_17ClosestDescendant6injectINtNtNtNtCsaYZPK01V26L_4core4iter8adapters3map3MapINtNtNtCsdZExvAaxgia_5alloc3vec9into_iter8IntoIterhENCNCNCNvNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service12runtime_call0s7_00EEs_0CsibGXYHQB8Ea_25json_rpc_general_requests |
154 | | |
155 | | // Length of the key of the currently-iterated node. |
156 | 5.88M | let iter_key_len = self |
157 | 5.88M | .inner |
158 | 5.88M | .current_node_full_key() |
159 | 26.4M | .fold(0, |acc, k| acc + k.as_ref().len())5.88M ; Unexecuted instantiation: _RNCINvMNtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB5_17ClosestDescendant6injectINtNtNtB9_4trie12proof_decode12EntryKeyIterINtNtCsdZExvAaxgia_5alloc3vec3VechEEE0B9_ _RNCINvMNtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB5_17ClosestDescendant6injectINtNtNtNtCsaYZPK01V26L_4core4iter7sources5empty5EmptyNtNtNtB9_4trie6nibble6NibbleEE0B9_ Line | Count | Source | 159 | 32 | .fold(0, |acc, k| acc + k.as_ref().len()); |
_RNCINvMNtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB5_17ClosestDescendant6injectINtNtNtNtCsaYZPK01V26L_4core4iter8adapters7flatten7FlatMapINtNtB1z_5chain5ChainINtNtB1z_4skip4SkipINtNtNtB1B_7sources10successors10SuccessorsjNCNvMNtNtB9_4trie14trie_structureINtB3R_13TrieStructureTINtNtB1D_6option6OptionTINtNtCsdZExvAaxgia_5alloc3vec3VechENtB3T_16TrieEntryVersionEEIB4H_NtNtB3T_9trie_node17MerkleValueOutputEEE9node_path0EEINtNtB39_4once4OncejEEIB2r_INtNtB1z_3map3MapINtB4J_8IntoIterTjNtNtB3T_6nibble6NibbleEENCNCNvB3Q_13node_full_key00EINtNtB1z_6cloned6ClonedINtNtNtB1D_5slice4iter4IterB7Z_EEENCB8r_0EE0B9_ Line | Count | Source | 159 | 26.3M | .fold(0, |acc, k| acc + k.as_ref().len()); |
_RNCINvMNtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB5_17ClosestDescendant6injectNtNtNtB9_4trie13branch_search21BranchTrieNodeKeyIterE0B9_ Line | Count | Source | 159 | 65.2k | .fold(0, |acc, k| acc + k.as_ref().len()); |
Unexecuted instantiation: _RNCINvMNtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB5_17ClosestDescendant6injectINtNtNtB9_4trie12proof_decode12EntryKeyIterINtNtNtCsdZExvAaxgia_5alloc3vec9into_iter8IntoIterhEEE0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCINvMNtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB5_17ClosestDescendant6injectINtNtNtB9_4trie12proof_decode12EntryKeyIterRShEE0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCINvMNtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB5_17ClosestDescendant6injectINtNtNtNtCsaYZPK01V26L_4core4iter8adapters3map3MapINtNtNtCsdZExvAaxgia_5alloc3vec9into_iter8IntoIterhENCNCNvMNtNtB9_8database11full_sqliteNtB3g_18SqliteFullDatabase20to_chain_informations_00EE0B9_ Unexecuted instantiation: _RNCINvMNtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB5_17ClosestDescendant6injectINtNtNtB9_4trie12proof_decode12EntryKeyIterINtNtNtCsdZExvAaxgia_5alloc3vec9into_iter8IntoIterhEEE0CsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RNCINvMNtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB5_17ClosestDescendant6injectINtNtNtNtCsaYZPK01V26L_4core4iter8adapters3map3MapINtNtNtCsdZExvAaxgia_5alloc3vec9into_iter8IntoIterhENCNCNCNvMs_NtCsiUjFBJteJ7x_17smoldot_full_node17consensus_serviceNtB3k_14SyncBackground12author_block0s6_00EE0CsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RNCINvMNtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB5_17ClosestDescendant6injectINtNtNtNtCsaYZPK01V26L_4core4iter8adapters3map3MapINtNtNtCsdZExvAaxgia_5alloc3vec9into_iter8IntoIterhENCNCNCNvNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service12runtime_call0s7_00EE0CsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RNCINvMNtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB5_17ClosestDescendant6injectINtNtNtNtCsaYZPK01V26L_4core4iter8adapters3map3MapINtNtNtCsdZExvAaxgia_5alloc3vec9into_iter8IntoIterhENCNCNCNvNtNtCsiUjFBJteJ7x_17smoldot_full_node16json_rpc_service16requests_handler22spawn_requests_handler0se_00EE0B3l_ Unexecuted instantiation: _RNCINvMNtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB5_17ClosestDescendant6injectINtNtNtB9_4trie12proof_decode12EntryKeyIterINtNtNtCsdZExvAaxgia_5alloc3vec9into_iter8IntoIterhEEE0CscDgN54JpMGG_6author Unexecuted instantiation: _RNCINvMNtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB5_17ClosestDescendant6injectINtNtNtNtCsaYZPK01V26L_4core4iter8adapters3map3MapINtNtNtCsdZExvAaxgia_5alloc3vec9into_iter8IntoIterhENCNCNCNvMs_NtCsiUjFBJteJ7x_17smoldot_full_node17consensus_serviceNtB3k_14SyncBackground12author_block0s6_00EE0CscDgN54JpMGG_6author Unexecuted instantiation: _RNCINvMNtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB5_17ClosestDescendant6injectINtNtNtNtCsaYZPK01V26L_4core4iter8adapters3map3MapINtNtNtCsdZExvAaxgia_5alloc3vec9into_iter8IntoIterhENCNCNCNvNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service12runtime_call0s7_00EE0CscDgN54JpMGG_6author Unexecuted instantiation: _RNCINvMNtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB5_17ClosestDescendant6injectINtNtNtB9_4trie12proof_decode12EntryKeyIterINtNtNtCsdZExvAaxgia_5alloc3vec9into_iter8IntoIterhEEE0CsibGXYHQB8Ea_25json_rpc_general_requests Unexecuted instantiation: _RNCINvMNtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB5_17ClosestDescendant6injectINtNtNtNtCsaYZPK01V26L_4core4iter8adapters3map3MapINtNtNtCsdZExvAaxgia_5alloc3vec9into_iter8IntoIterhENCNCNCNvMs_NtCsiUjFBJteJ7x_17smoldot_full_node17consensus_serviceNtB3k_14SyncBackground12author_block0s6_00EE0CsibGXYHQB8Ea_25json_rpc_general_requests Unexecuted instantiation: _RNCINvMNtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB5_17ClosestDescendant6injectINtNtNtNtCsaYZPK01V26L_4core4iter8adapters3map3MapINtNtNtCsdZExvAaxgia_5alloc3vec9into_iter8IntoIterhENCNCNCNvNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service12runtime_call0s7_00EE0CsibGXYHQB8Ea_25json_rpc_general_requests |
160 | | |
161 | | // Find the value of `MaybeNode`. |
162 | 366k | let (maybe_node_partial_key, children_partial_key_changed) = |
163 | 5.88M | match (self.diff_inserts_lcd, closest_descendant) { |
164 | 50.8k | (Some(inserted_key), Some(base_trie_key)) => { |
165 | 50.8k | // `children_partial_key_changed` is `true` if |
166 | 50.8k | // `diff_inserts_lcd < closest_descendant`. |
167 | 50.8k | let mut inserted_key_iter = inserted_key.iter().copied().skip(iter_key_len); |
168 | 50.8k | let mut base_trie_key = base_trie_key.skip(iter_key_len); |
169 | 50.8k | let mut maybe_node_pk = |
170 | 50.8k | Vec::with_capacity(inserted_key.len() - iter_key_len + 8); |
171 | 50.8k | let mut children_pk_changed = false; |
172 | | loop { |
173 | 55.3k | match (inserted_key_iter.next(), base_trie_key.next()) { |
174 | 17.7k | (Some(inib), Some(bnib4.54k )) if inib == bnib => maybe_node_pk.push(inib)4.54k , |
175 | | (Some(_), Some(_)) | (None, Some(_)) => { |
176 | 16.8k | children_pk_changed = true; |
177 | 16.8k | break; |
178 | | } |
179 | 33.9k | (Some(_), None) | (None, None) => break, |
180 | | } |
181 | | } |
182 | 50.8k | (maybe_node_pk, children_pk_changed) |
183 | | } |
184 | 282k | (Some(inserted_key), None) => ( |
185 | 282k | inserted_key |
186 | 282k | .into_iter() |
187 | 282k | .skip(iter_key_len) |
188 | 282k | .collect::<Vec<_>>(), |
189 | 282k | true, |
190 | 282k | ), |
191 | 33.1k | (None, Some(base_trie_key)) => (base_trie_key.skip(iter_key_len).collect(), false), |
192 | | (None, None) => { |
193 | | // If neither the base trie nor the diff contain any descendant, then skip ahead. |
194 | 5.51M | return if let Some(parent_node5.51M ) = self.inner.stack.last_mut() { |
195 | | // If the element has a parent, indicate that the current iterated node |
196 | | // doesn't exist and continue the algorithm. |
197 | 5.51M | debug_assert_ne!(parent_node.children.len(), 16); |
198 | 5.51M | parent_node.children.push(None); |
199 | 5.51M | self.inner.next() |
200 | | } else { |
201 | | // If the element doesn't have a parent, then the trie is completely empty. |
202 | 1 | InProgress::Finished { |
203 | 1 | trie_root_hash: trie::EMPTY_BLAKE2_TRIE_MERKLE_VALUE, |
204 | 1 | } |
205 | | }; |
206 | | } |
207 | | }; |
208 | | |
209 | | // Push `MaybeNode` onto the stack and continue the algorithm. |
210 | 366k | self.inner.stack.push(InProgressNode { |
211 | 366k | partial_key: maybe_node_partial_key, |
212 | 366k | children_partial_key_changed, |
213 | 366k | children: arrayvec::ArrayVec::new(), |
214 | 366k | }); |
215 | 366k | self.inner.next() |
216 | 5.88M | } Unexecuted instantiation: _RINvMNtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB3_17ClosestDescendant6injectINtNtNtB7_4trie12proof_decode12EntryKeyIterINtNtCsdZExvAaxgia_5alloc3vec3VechEEEB7_ _RINvMNtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB3_17ClosestDescendant6injectINtNtNtNtCsaYZPK01V26L_4core4iter7sources5empty5EmptyNtNtNtB7_4trie6nibble6NibbleEEB7_ Line | Count | Source | 144 | 18 | pub fn inject( | 145 | 18 | mut self, | 146 | 18 | closest_descendant: Option<impl Iterator<Item = Nibble>>, | 147 | 18 | ) -> InProgress { | 148 | 18 | // We are after a call to `BaseTrieClosestDescendant`. | 149 | 18 | debug_assert!(self | 150 | 18 | .inner | 151 | 18 | .stack | 152 | 18 | .last() | 153 | 18 | .map_or(true, |n| n.children.len() != 16)); | 154 | | | 155 | | // Length of the key of the currently-iterated node. | 156 | 18 | let iter_key_len = self | 157 | 18 | .inner | 158 | 18 | .current_node_full_key() | 159 | 18 | .fold(0, |acc, k| acc + k.as_ref().len()); | 160 | | | 161 | | // Find the value of `MaybeNode`. | 162 | 1 | let (maybe_node_partial_key, children_partial_key_changed) = | 163 | 18 | match (self.diff_inserts_lcd, closest_descendant) { | 164 | 0 | (Some(inserted_key), Some(base_trie_key)) => { | 165 | 0 | // `children_partial_key_changed` is `true` if | 166 | 0 | // `diff_inserts_lcd < closest_descendant`. | 167 | 0 | let mut inserted_key_iter = inserted_key.iter().copied().skip(iter_key_len); | 168 | 0 | let mut base_trie_key = base_trie_key.skip(iter_key_len); | 169 | 0 | let mut maybe_node_pk = | 170 | 0 | Vec::with_capacity(inserted_key.len() - iter_key_len + 8); | 171 | 0 | let mut children_pk_changed = false; | 172 | | loop { | 173 | 0 | match (inserted_key_iter.next(), base_trie_key.next()) { | 174 | 0 | (Some(inib), Some(bnib)) if inib == bnib => maybe_node_pk.push(inib), | 175 | | (Some(_), Some(_)) | (None, Some(_)) => { | 176 | 0 | children_pk_changed = true; | 177 | 0 | break; | 178 | | } | 179 | 0 | (Some(_), None) | (None, None) => break, | 180 | | } | 181 | | } | 182 | 0 | (maybe_node_pk, children_pk_changed) | 183 | | } | 184 | 1 | (Some(inserted_key), None) => ( | 185 | 1 | inserted_key | 186 | 1 | .into_iter() | 187 | 1 | .skip(iter_key_len) | 188 | 1 | .collect::<Vec<_>>(), | 189 | 1 | true, | 190 | 1 | ), | 191 | 0 | (None, Some(base_trie_key)) => (base_trie_key.skip(iter_key_len).collect(), false), | 192 | | (None, None) => { | 193 | | // If neither the base trie nor the diff contain any descendant, then skip ahead. | 194 | 17 | return if let Some(parent_node16 ) = self.inner.stack.last_mut() { | 195 | | // If the element has a parent, indicate that the current iterated node | 196 | | // doesn't exist and continue the algorithm. | 197 | 16 | debug_assert_ne!(parent_node.children.len(), 16); | 198 | 16 | parent_node.children.push(None); | 199 | 16 | self.inner.next() | 200 | | } else { | 201 | | // If the element doesn't have a parent, then the trie is completely empty. | 202 | 1 | InProgress::Finished { | 203 | 1 | trie_root_hash: trie::EMPTY_BLAKE2_TRIE_MERKLE_VALUE, | 204 | 1 | } | 205 | | }; | 206 | | } | 207 | | }; | 208 | | | 209 | | // Push `MaybeNode` onto the stack and continue the algorithm. | 210 | 1 | self.inner.stack.push(InProgressNode { | 211 | 1 | partial_key: maybe_node_partial_key, | 212 | 1 | children_partial_key_changed, | 213 | 1 | children: arrayvec::ArrayVec::new(), | 214 | 1 | }); | 215 | 1 | self.inner.next() | 216 | 18 | } |
_RINvMNtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB3_17ClosestDescendant6injectINtNtNtNtCsaYZPK01V26L_4core4iter8adapters7flatten7FlatMapINtNtB1x_5chain5ChainINtNtB1x_4skip4SkipINtNtNtB1z_7sources10successors10SuccessorsjNCNvMNtNtB7_4trie14trie_structureINtB3P_13TrieStructureTINtNtB1B_6option6OptionTINtNtCsdZExvAaxgia_5alloc3vec3VechENtB3R_16TrieEntryVersionEEIB4F_NtNtB3R_9trie_node17MerkleValueOutputEEE9node_path0EEINtNtB37_4once4OncejEEIB2p_INtNtB1x_3map3MapINtB4H_8IntoIterTjNtNtB3R_6nibble6NibbleEENCNCNvB3O_13node_full_key00EINtNtB1x_6cloned6ClonedINtNtNtB1B_5slice4iter4IterB7X_EEENCB8p_0EEB7_ Line | Count | Source | 144 | 5.87M | pub fn inject( | 145 | 5.87M | mut self, | 146 | 5.87M | closest_descendant: Option<impl Iterator<Item = Nibble>>, | 147 | 5.87M | ) -> InProgress { | 148 | 5.87M | // We are after a call to `BaseTrieClosestDescendant`. | 149 | 5.87M | debug_assert!(self | 150 | 5.87M | .inner | 151 | 5.87M | .stack | 152 | 5.87M | .last() | 153 | 5.87M | .map_or(true, |n| n.children.len() != 16)); | 154 | | | 155 | | // Length of the key of the currently-iterated node. | 156 | 5.87M | let iter_key_len = self | 157 | 5.87M | .inner | 158 | 5.87M | .current_node_full_key() | 159 | 5.87M | .fold(0, |acc, k| acc + k.as_ref().len()); | 160 | | | 161 | | // Find the value of `MaybeNode`. | 162 | 366k | let (maybe_node_partial_key, children_partial_key_changed) = | 163 | 5.87M | match (self.diff_inserts_lcd, closest_descendant) { | 164 | 50.6k | (Some(inserted_key), Some(base_trie_key)) => { | 165 | 50.6k | // `children_partial_key_changed` is `true` if | 166 | 50.6k | // `diff_inserts_lcd < closest_descendant`. | 167 | 50.6k | let mut inserted_key_iter = inserted_key.iter().copied().skip(iter_key_len); | 168 | 50.6k | let mut base_trie_key = base_trie_key.skip(iter_key_len); | 169 | 50.6k | let mut maybe_node_pk = | 170 | 50.6k | Vec::with_capacity(inserted_key.len() - iter_key_len + 8); | 171 | 50.6k | let mut children_pk_changed = false; | 172 | | loop { | 173 | 51.5k | match (inserted_key_iter.next(), base_trie_key.next()) { | 174 | 14.0k | (Some(inib), Some(bnib830 )) if inib == bnib => maybe_node_pk.push(inib)830 , | 175 | | (Some(_), Some(_)) | (None, Some(_)) => { | 176 | 16.8k | children_pk_changed = true; | 177 | 16.8k | break; | 178 | | } | 179 | 33.8k | (Some(_), None) | (None, None) => break, | 180 | | } | 181 | | } | 182 | 50.6k | (maybe_node_pk, children_pk_changed) | 183 | | } | 184 | 282k | (Some(inserted_key), None) => ( | 185 | 282k | inserted_key | 186 | 282k | .into_iter() | 187 | 282k | .skip(iter_key_len) | 188 | 282k | .collect::<Vec<_>>(), | 189 | 282k | true, | 190 | 282k | ), | 191 | 32.8k | (None, Some(base_trie_key)) => (base_trie_key.skip(iter_key_len).collect(), false), | 192 | | (None, None) => { | 193 | | // If neither the base trie nor the diff contain any descendant, then skip ahead. | 194 | 5.50M | return if let Some(parent_node) = self.inner.stack.last_mut() { | 195 | | // If the element has a parent, indicate that the current iterated node | 196 | | // doesn't exist and continue the algorithm. | 197 | 5.50M | debug_assert_ne!(parent_node.children.len(), 16); | 198 | 5.50M | parent_node.children.push(None); | 199 | 5.50M | self.inner.next() | 200 | | } else { | 201 | | // If the element doesn't have a parent, then the trie is completely empty. | 202 | 0 | InProgress::Finished { | 203 | 0 | trie_root_hash: trie::EMPTY_BLAKE2_TRIE_MERKLE_VALUE, | 204 | 0 | } | 205 | | }; | 206 | | } | 207 | | }; | 208 | | | 209 | | // Push `MaybeNode` onto the stack and continue the algorithm. | 210 | 366k | self.inner.stack.push(InProgressNode { | 211 | 366k | partial_key: maybe_node_partial_key, | 212 | 366k | children_partial_key_changed, | 213 | 366k | children: arrayvec::ArrayVec::new(), | 214 | 366k | }); | 215 | 366k | self.inner.next() | 216 | 5.87M | } |
_RINvMNtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB3_17ClosestDescendant6injectNtNtNtB7_4trie13branch_search21BranchTrieNodeKeyIterEB7_ Line | Count | Source | 144 | 8.23k | pub fn inject( | 145 | 8.23k | mut self, | 146 | 8.23k | closest_descendant: Option<impl Iterator<Item = Nibble>>, | 147 | 8.23k | ) -> InProgress { | 148 | 8.23k | // We are after a call to `BaseTrieClosestDescendant`. | 149 | 8.23k | debug_assert!(self | 150 | 8.23k | .inner | 151 | 8.23k | .stack | 152 | 8.23k | .last() | 153 | 8.23k | .map_or(true, |n| n.children.len() != 16)); | 154 | | | 155 | | // Length of the key of the currently-iterated node. | 156 | 8.23k | let iter_key_len = self | 157 | 8.23k | .inner | 158 | 8.23k | .current_node_full_key() | 159 | 8.23k | .fold(0, |acc, k| acc + k.as_ref().len()); | 160 | | | 161 | | // Find the value of `MaybeNode`. | 162 | 514 | let (maybe_node_partial_key, children_partial_key_changed) = | 163 | 8.23k | match (self.diff_inserts_lcd, closest_descendant) { | 164 | 144 | (Some(inserted_key), Some(base_trie_key)) => { | 165 | 144 | // `children_partial_key_changed` is `true` if | 166 | 144 | // `diff_inserts_lcd < closest_descendant`. | 167 | 144 | let mut inserted_key_iter = inserted_key.iter().copied().skip(iter_key_len); | 168 | 144 | let mut base_trie_key = base_trie_key.skip(iter_key_len); | 169 | 144 | let mut maybe_node_pk = | 170 | 144 | Vec::with_capacity(inserted_key.len() - iter_key_len + 8); | 171 | 144 | let mut children_pk_changed = false; | 172 | | loop { | 173 | 3.85k | match (inserted_key_iter.next(), base_trie_key.next()) { | 174 | 3.72k | (Some(inib), Some(bnib3.71k )) if inib == bnib => maybe_node_pk.push(inib)3.71k , | 175 | | (Some(_), Some(_)) | (None, Some(_)) => { | 176 | 20 | children_pk_changed = true; | 177 | 20 | break; | 178 | | } | 179 | 124 | (Some(_), None) | (None, None) => break, | 180 | | } | 181 | | } | 182 | 144 | (maybe_node_pk, children_pk_changed) | 183 | | } | 184 | 59 | (Some(inserted_key), None) => ( | 185 | 59 | inserted_key | 186 | 59 | .into_iter() | 187 | 59 | .skip(iter_key_len) | 188 | 59 | .collect::<Vec<_>>(), | 189 | 59 | true, | 190 | 59 | ), | 191 | 311 | (None, Some(base_trie_key)) => (base_trie_key.skip(iter_key_len).collect(), false), | 192 | | (None, None) => { | 193 | | // If neither the base trie nor the diff contain any descendant, then skip ahead. | 194 | 7.72k | return if let Some(parent_node) = self.inner.stack.last_mut() { | 195 | | // If the element has a parent, indicate that the current iterated node | 196 | | // doesn't exist and continue the algorithm. | 197 | 7.72k | debug_assert_ne!(parent_node.children.len(), 16); | 198 | 7.72k | parent_node.children.push(None); | 199 | 7.72k | self.inner.next() | 200 | | } else { | 201 | | // If the element doesn't have a parent, then the trie is completely empty. | 202 | 0 | InProgress::Finished { | 203 | 0 | trie_root_hash: trie::EMPTY_BLAKE2_TRIE_MERKLE_VALUE, | 204 | 0 | } | 205 | | }; | 206 | | } | 207 | | }; | 208 | | | 209 | | // Push `MaybeNode` onto the stack and continue the algorithm. | 210 | 514 | self.inner.stack.push(InProgressNode { | 211 | 514 | partial_key: maybe_node_partial_key, | 212 | 514 | children_partial_key_changed, | 213 | 514 | children: arrayvec::ArrayVec::new(), | 214 | 514 | }); | 215 | 514 | self.inner.next() | 216 | 8.23k | } |
Unexecuted instantiation: _RINvMNtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB3_17ClosestDescendant6injectINtNtNtB7_4trie12proof_decode12EntryKeyIterINtNtNtCsdZExvAaxgia_5alloc3vec9into_iter8IntoIterhEEECsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RINvMNtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB3_17ClosestDescendant6injectINtNtNtB7_4trie12proof_decode12EntryKeyIterRShEECsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RINvMNtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB3_17ClosestDescendant6injectINtNtNtNtCsaYZPK01V26L_4core4iter8adapters3map3MapINtNtNtCsdZExvAaxgia_5alloc3vec9into_iter8IntoIterhENCNCNvMNtNtB7_8database11full_sqliteNtB3e_18SqliteFullDatabase20to_chain_informations_00EEB7_ Unexecuted instantiation: _RINvMNtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB3_17ClosestDescendant6injectINtNtNtB7_4trie12proof_decode12EntryKeyIterINtNtNtCsdZExvAaxgia_5alloc3vec9into_iter8IntoIterhEEECsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RINvMNtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB3_17ClosestDescendant6injectINtNtNtNtCsaYZPK01V26L_4core4iter8adapters3map3MapINtNtNtCsdZExvAaxgia_5alloc3vec9into_iter8IntoIterhENCNCNCNvMs_NtCsiUjFBJteJ7x_17smoldot_full_node17consensus_serviceNtB3i_14SyncBackground12author_block0s6_00EECsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RINvMNtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB3_17ClosestDescendant6injectINtNtNtNtCsaYZPK01V26L_4core4iter8adapters3map3MapINtNtNtCsdZExvAaxgia_5alloc3vec9into_iter8IntoIterhENCNCNCNvNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service12runtime_call0s7_00EECsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RINvMNtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB3_17ClosestDescendant6injectINtNtNtNtCsaYZPK01V26L_4core4iter8adapters3map3MapINtNtNtCsdZExvAaxgia_5alloc3vec9into_iter8IntoIterhENCNCNCNvNtNtCsiUjFBJteJ7x_17smoldot_full_node16json_rpc_service16requests_handler22spawn_requests_handler0se_00EEB3j_ Unexecuted instantiation: _RINvMNtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB3_17ClosestDescendant6injectINtNtNtB7_4trie12proof_decode12EntryKeyIterINtNtNtCsdZExvAaxgia_5alloc3vec9into_iter8IntoIterhEEECscDgN54JpMGG_6author Unexecuted instantiation: _RINvMNtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB3_17ClosestDescendant6injectINtNtNtNtCsaYZPK01V26L_4core4iter8adapters3map3MapINtNtNtCsdZExvAaxgia_5alloc3vec9into_iter8IntoIterhENCNCNCNvMs_NtCsiUjFBJteJ7x_17smoldot_full_node17consensus_serviceNtB3i_14SyncBackground12author_block0s6_00EECscDgN54JpMGG_6author Unexecuted instantiation: _RINvMNtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB3_17ClosestDescendant6injectINtNtNtNtCsaYZPK01V26L_4core4iter8adapters3map3MapINtNtNtCsdZExvAaxgia_5alloc3vec9into_iter8IntoIterhENCNCNCNvNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service12runtime_call0s7_00EECscDgN54JpMGG_6author Unexecuted instantiation: _RINvMNtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB3_17ClosestDescendant6injectINtNtNtB7_4trie12proof_decode12EntryKeyIterINtNtNtCsdZExvAaxgia_5alloc3vec9into_iter8IntoIterhEEECsibGXYHQB8Ea_25json_rpc_general_requests Unexecuted instantiation: _RINvMNtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB3_17ClosestDescendant6injectINtNtNtNtCsaYZPK01V26L_4core4iter8adapters3map3MapINtNtNtCsdZExvAaxgia_5alloc3vec9into_iter8IntoIterhENCNCNCNvMs_NtCsiUjFBJteJ7x_17smoldot_full_node17consensus_serviceNtB3i_14SyncBackground12author_block0s6_00EECsibGXYHQB8Ea_25json_rpc_general_requests Unexecuted instantiation: _RINvMNtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB3_17ClosestDescendant6injectINtNtNtNtCsaYZPK01V26L_4core4iter8adapters3map3MapINtNtNtCsdZExvAaxgia_5alloc3vec9into_iter8IntoIterhENCNCNCNvNtCsiUjFBJteJ7x_17smoldot_full_node17consensus_service12runtime_call0s7_00EECsibGXYHQB8Ea_25json_rpc_general_requests |
217 | | } |
218 | | |
219 | | /// In order to continue, must fetch the storage value of the given key in the base trie. |
220 | | pub struct StorageValue(Box<Inner>); |
221 | | |
222 | | impl StorageValue { |
223 | | /// Returns an iterator of slices, which, when joined together, form the full key of the trie |
224 | | /// node whose storage value must be fetched. |
225 | 1.05M | pub fn key(&'_ self) -> impl Iterator<Item = impl AsRef<[Nibble]> + '_> + '_ { |
226 | 1.05M | self.0.current_node_full_key() |
227 | 1.05M | } _RNvMs_NtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB4_12StorageValue3key Line | Count | Source | 225 | 1.05M | pub fn key(&'_ self) -> impl Iterator<Item = impl AsRef<[Nibble]> + '_> + '_ { | 226 | 1.05M | self.0.current_node_full_key() | 227 | 1.05M | } |
Unexecuted instantiation: _RNvMs_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB4_12StorageValue3key |
228 | | |
229 | | /// Returns the same value as [`ClosestDescendant::key`] but as a `Vec`. |
230 | 366k | pub fn key_as_vec(&self) -> Vec<Nibble> { |
231 | 1.28M | self.key().fold(Vec::new(), |mut a, b| { |
232 | 1.28M | a.extend_from_slice(b.as_ref()); |
233 | 1.28M | a |
234 | 1.28M | }) _RNCNvMs_NtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB6_12StorageValue10key_as_vec0Ba_ Line | Count | Source | 231 | 1.28M | self.key().fold(Vec::new(), |mut a, b| { | 232 | 1.28M | a.extend_from_slice(b.as_ref()); | 233 | 1.28M | a | 234 | 1.28M | }) |
Unexecuted instantiation: _RNCNvMs_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB6_12StorageValue10key_as_vec0Ba_ |
235 | 366k | } _RNvMs_NtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB4_12StorageValue10key_as_vec Line | Count | Source | 230 | 366k | pub fn key_as_vec(&self) -> Vec<Nibble> { | 231 | 366k | self.key().fold(Vec::new(), |mut a, b| { | 232 | | a.extend_from_slice(b.as_ref()); | 233 | | a | 234 | 366k | }) | 235 | 366k | } |
Unexecuted instantiation: _RNvMs_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB4_12StorageValue10key_as_vec |
236 | | |
237 | | /// Indicate the storage value and trie entry version of the trie node indicated by |
238 | | /// [`StorageValue::key`] and resume the calculation. |
239 | 366k | pub fn inject_value( |
240 | 366k | mut self, |
241 | 366k | base_trie_storage_value: Option<(&[u8], TrieEntryVersion)>, |
242 | 366k | ) -> InProgress { |
243 | | // We have finished obtaining `BaseTrieStorageValue` and we are at the last step of |
244 | | // `ClosestDescendantMerkleValue` in the algorithm shown at the top. |
245 | | |
246 | | // Adjust the storage value to take the diff into account. |
247 | | // In other words, we calculate `MaybeStorageValue` from `BaseTrieStorageValue`. |
248 | 1.28M | let maybe_storage_value366k = if self.key().fold(0, 366k |a, b| a + b.as_ref().len()) % 2 == 0366k { _RNCNvMs_NtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB6_12StorageValue12inject_value0Ba_ Line | Count | Source | 248 | 1.28M | let maybe_storage_value = if self.key().fold(0, |a, b| a + b.as_ref().len()) % 2 == 0 { |
Unexecuted instantiation: _RNCNvMs_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB6_12StorageValue12inject_value0Ba_ |
249 | | // TODO: could be optimized? |
250 | 1.12M | let key_nibbles = self.key().fold(Vec::new(), 312k |mut a, b| { |
251 | 1.12M | a.extend_from_slice(b.as_ref()); |
252 | 1.12M | a |
253 | 1.12M | }); _RNCNvMs_NtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB6_12StorageValue12inject_values_0Ba_ Line | Count | Source | 250 | 1.12M | let key_nibbles = self.key().fold(Vec::new(), |mut a, b| { | 251 | 1.12M | a.extend_from_slice(b.as_ref()); | 252 | 1.12M | a | 253 | 1.12M | }); |
Unexecuted instantiation: _RNCNvMs_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB6_12StorageValue12inject_values_0Ba_ |
254 | 312k | debug_assert_eq!(key_nibbles.len() % 2, 0); |
255 | 312k | let key_as_u8 = |
256 | 312k | trie::nibbles_to_bytes_suffix_extend(key_nibbles.into_iter()).collect::<Vec<_>>(); |
257 | 312k | if let Some((value277k , _)) = self.0.diff.diff_get(&key_as_u8) { |
258 | 277k | value.map(|v| (v, self.0.diff_trie_entries_version)266k ) _RNCNvMs_NtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB6_12StorageValue12inject_values0_0Ba_ Line | Count | Source | 258 | 266k | value.map(|v| (v, self.0.diff_trie_entries_version)) |
Unexecuted instantiation: _RNCNvMs_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB6_12StorageValue12inject_values0_0Ba_ |
259 | | } else { |
260 | 34.6k | base_trie_storage_value |
261 | | } |
262 | | } else { |
263 | 54.0k | base_trie_storage_value |
264 | | }; |
265 | | |
266 | | // Remove the element that is being calculated from the stack, as we finish the |
267 | | // calculation down below. |
268 | 366k | let calculated_elem = self.0.stack.pop().unwrap_or_else(|| panic!()0 ); Unexecuted instantiation: _RNCNvMs_NtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB6_12StorageValue12inject_values1_0Ba_ Unexecuted instantiation: _RNCNvMs_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB6_12StorageValue12inject_values1_0Ba_ |
269 | 366k | debug_assert_eq!(calculated_elem.children.len(), 16); |
270 | | |
271 | 366k | let node_num_children = calculated_elem |
272 | 366k | .children |
273 | 366k | .iter() |
274 | 5.86M | .filter(|c| c.is_some()) _RNCNvMs_NtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB6_12StorageValue12inject_values2_0Ba_ Line | Count | Source | 274 | 5.86M | .filter(|c| c.is_some()) |
Unexecuted instantiation: _RNCNvMs_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB6_12StorageValue12inject_values2_0Ba_ |
275 | 366k | .count(); |
276 | 366k | |
277 | 366k | let parent_node = self.0.stack.last_mut(); |
278 | 366k | debug_assert!(parent_node.map_or(true, |p| p.children.len() != 16333k )); _RNCNvMs_NtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB6_12StorageValue12inject_values6_0Ba_ Line | Count | Source | 278 | 333k | debug_assert!(parent_node.map_or(true, |p| p.children.len() != 16)); |
Unexecuted instantiation: _RNCNvMs_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB6_12StorageValue12inject_values6_0Ba_ |
279 | | |
280 | | match ( |
281 | 366k | base_trie_storage_value, |
282 | 366k | maybe_storage_value, |
283 | 366k | node_num_children, |
284 | 366k | self.0.stack.last_mut(), |
285 | | ) { |
286 | 92 | (_, None, 0, Some(_parent_node)) => { |
287 | 92 | // Trie node no longer exists after the diff has been applied. |
288 | 92 | // This path is only reached if the trie node has a parent, as otherwise the trie |
289 | 92 | // node is the trie root and thus necessarily exists. |
290 | 92 | InProgress::TrieNodeRemoveEvent(TrieNodeRemoveEvent { |
291 | 92 | inner: self.0, |
292 | 92 | calculated_elem, |
293 | 92 | ty: TrieNodeRemoveEventTy::NoChildrenLeft, |
294 | 92 | }) |
295 | | } |
296 | | |
297 | 23 | (_, None, 1, _parent_node) if !calculated_elem.children_partial_key_changed => { |
298 | 23 | // Trie node doesn't exists after the diff has been applied because it has exactly |
299 | 23 | // one child. |
300 | 23 | // Since `children_partial_key_changed` is `true`, we know that the node existed |
301 | 23 | // and generate a `TrieNodeRemoveEvent`. |
302 | 23 | // Unfortunately, the child Merkle value is wrong as its partial key has changed |
303 | 23 | // and has to be recalculated. |
304 | 23 | |
305 | 23 | // To handle this situation, we back jump to `ClosestDescendant` but this time |
306 | 23 | // make sure to skip over `calculated_elem`. |
307 | 23 | // This isn't done here but in `TrieNodeRemoveEvent::resume`. |
308 | 23 | InProgress::TrieNodeRemoveEvent(TrieNodeRemoveEvent { |
309 | 23 | inner: self.0, |
310 | 23 | calculated_elem, |
311 | 23 | ty: TrieNodeRemoveEventTy::ReplacedWithSingleChild, |
312 | 23 | }) |
313 | | } |
314 | | |
315 | 19 | (_, None, 1, _parent_node) => { |
316 | 19 | // Same as the previous block, except that `children_partial_key_changed` is |
317 | 19 | // `false`. Therefore the node didn't exist in the base trie, and no event shall |
318 | 19 | // be generated. Instead, we immediately call `resume` in order to continue |
319 | 19 | // execution without notifying the user. |
320 | 19 | TrieNodeRemoveEvent { |
321 | 19 | inner: self.0, |
322 | 19 | calculated_elem, |
323 | 19 | ty: TrieNodeRemoveEventTy::ReplacedWithSingleChild, |
324 | 19 | } |
325 | 19 | .resume() |
326 | | } |
327 | | |
328 | | (Some(_), None, 0, None) => { |
329 | | // Root node of the trie was deleted and trie is now empty. |
330 | 3 | InProgress::TrieNodeRemoveEvent(TrieNodeRemoveEvent { |
331 | 3 | inner: self.0, |
332 | 3 | calculated_elem, |
333 | 3 | ty: TrieNodeRemoveEventTy::NoChildrenLeft, |
334 | 3 | }) |
335 | | } |
336 | | |
337 | | (None, None, 0, None) => { |
338 | | // Trie is empty. |
339 | | // This case is handled separately in order to not generate |
340 | | // a `TrieNodeInsertUpdateEvent` for a node that doesn't actually exist. |
341 | 0 | InProgress::Finished { |
342 | 0 | trie_root_hash: trie::EMPTY_BLAKE2_TRIE_MERKLE_VALUE, |
343 | 0 | } |
344 | | } |
345 | | |
346 | 366k | (_, _, _, parent_node) => { |
347 | | // Trie node still exists or was created. Calculate its Merkle value. |
348 | | |
349 | | // Due to some borrow checker troubles, we need to calculate the storage value |
350 | | // hash ahead of time if relevant. |
351 | 366k | let storage_value_hash = |
352 | 366k | if let Some((value148k , TrieEntryVersion::V1)) = maybe_storage_value { |
353 | 148k | if value.len() >= 33 { |
354 | 100 | Some(blake2_rfc::blake2b::blake2b(32, &[], value)) |
355 | | } else { |
356 | 148k | None |
357 | | } |
358 | | } else { |
359 | 217k | None |
360 | | }; |
361 | 366k | let merkle_value = trie::trie_node::calculate_merkle_value( |
362 | | trie::trie_node::Decoded { |
363 | 5.86M | children: array::from_fn(366k |n| calculated_elem.children[n].as_ref()), _RNCNvMs_NtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB6_12StorageValue12inject_values3_0Ba_ Line | Count | Source | 363 | 5.86M | children: array::from_fn(|n| calculated_elem.children[n].as_ref()), |
Unexecuted instantiation: _RNCNvMs_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB6_12StorageValue12inject_values3_0Ba_ |
364 | 366k | partial_key: calculated_elem.partial_key.iter().copied(), |
365 | 366k | storage_value: match (maybe_storage_value, storage_value_hash.as_ref()) { |
366 | 100 | (_, Some(storage_value_hash)) => trie::trie_node::StorageValue::Hashed( |
367 | 100 | <&[u8; 32]>::try_from(storage_value_hash.as_bytes()) |
368 | 100 | .unwrap_or_else(|_| panic!()0 ), Unexecuted instantiation: _RNCNvMs_NtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB6_12StorageValue12inject_values4_0Ba_ Unexecuted instantiation: _RNCNvMs_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB6_12StorageValue12inject_values4_0Ba_ |
369 | 100 | ), |
370 | 299k | (Some((value, _)), None) => { |
371 | 299k | trie::trie_node::StorageValue::Unhashed(value) |
372 | | } |
373 | 67.1k | (None, _) => trie::trie_node::StorageValue::None, |
374 | | }, |
375 | | }, |
376 | 366k | trie::HashFunction::Blake2, |
377 | 366k | parent_node.is_none(), |
378 | 366k | ) |
379 | 366k | .unwrap_or_else(|_| panic!()0 ); Unexecuted instantiation: _RNCNvMs_NtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB6_12StorageValue12inject_values5_0Ba_ Unexecuted instantiation: _RNCNvMs_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB6_12StorageValue12inject_values5_0Ba_ |
380 | 366k | |
381 | 366k | // The stack is updated in `TrieNodeInsertUpdateEvent::resume`. |
382 | 366k | InProgress::TrieNodeInsertUpdateEvent(TrieNodeInsertUpdateEvent { |
383 | 366k | inner: self.0, |
384 | 366k | children: calculated_elem.children, |
385 | 366k | inserted_elem_partial_key: calculated_elem.partial_key, |
386 | 366k | merkle_value, |
387 | 366k | }) |
388 | | } |
389 | | } |
390 | 366k | } _RNvMs_NtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB4_12StorageValue12inject_value Line | Count | Source | 239 | 366k | pub fn inject_value( | 240 | 366k | mut self, | 241 | 366k | base_trie_storage_value: Option<(&[u8], TrieEntryVersion)>, | 242 | 366k | ) -> InProgress { | 243 | | // We have finished obtaining `BaseTrieStorageValue` and we are at the last step of | 244 | | // `ClosestDescendantMerkleValue` in the algorithm shown at the top. | 245 | | | 246 | | // Adjust the storage value to take the diff into account. | 247 | | // In other words, we calculate `MaybeStorageValue` from `BaseTrieStorageValue`. | 248 | 366k | let maybe_storage_value = if self.key().fold(0, |a, b| a + b.as_ref().len()) % 2 == 0 { | 249 | | // TODO: could be optimized? | 250 | 312k | let key_nibbles = self.key().fold(Vec::new(), |mut a, b| { | 251 | | a.extend_from_slice(b.as_ref()); | 252 | | a | 253 | 312k | }); | 254 | 312k | debug_assert_eq!(key_nibbles.len() % 2, 0); | 255 | 312k | let key_as_u8 = | 256 | 312k | trie::nibbles_to_bytes_suffix_extend(key_nibbles.into_iter()).collect::<Vec<_>>(); | 257 | 312k | if let Some((value277k , _)) = self.0.diff.diff_get(&key_as_u8) { | 258 | 277k | value.map(|v| (v, self.0.diff_trie_entries_version)) | 259 | | } else { | 260 | 34.6k | base_trie_storage_value | 261 | | } | 262 | | } else { | 263 | 54.0k | base_trie_storage_value | 264 | | }; | 265 | | | 266 | | // Remove the element that is being calculated from the stack, as we finish the | 267 | | // calculation down below. | 268 | 366k | let calculated_elem = self.0.stack.pop().unwrap_or_else(|| panic!()); | 269 | 366k | debug_assert_eq!(calculated_elem.children.len(), 16); | 270 | | | 271 | 366k | let node_num_children = calculated_elem | 272 | 366k | .children | 273 | 366k | .iter() | 274 | 366k | .filter(|c| c.is_some()) | 275 | 366k | .count(); | 276 | 366k | | 277 | 366k | let parent_node = self.0.stack.last_mut(); | 278 | 366k | debug_assert!(parent_node.map_or(true, |p| p.children.len() != 16)); | 279 | | | 280 | | match ( | 281 | 366k | base_trie_storage_value, | 282 | 366k | maybe_storage_value, | 283 | 366k | node_num_children, | 284 | 366k | self.0.stack.last_mut(), | 285 | | ) { | 286 | 92 | (_, None, 0, Some(_parent_node)) => { | 287 | 92 | // Trie node no longer exists after the diff has been applied. | 288 | 92 | // This path is only reached if the trie node has a parent, as otherwise the trie | 289 | 92 | // node is the trie root and thus necessarily exists. | 290 | 92 | InProgress::TrieNodeRemoveEvent(TrieNodeRemoveEvent { | 291 | 92 | inner: self.0, | 292 | 92 | calculated_elem, | 293 | 92 | ty: TrieNodeRemoveEventTy::NoChildrenLeft, | 294 | 92 | }) | 295 | | } | 296 | | | 297 | 23 | (_, None, 1, _parent_node) if !calculated_elem.children_partial_key_changed => { | 298 | 23 | // Trie node doesn't exists after the diff has been applied because it has exactly | 299 | 23 | // one child. | 300 | 23 | // Since `children_partial_key_changed` is `true`, we know that the node existed | 301 | 23 | // and generate a `TrieNodeRemoveEvent`. | 302 | 23 | // Unfortunately, the child Merkle value is wrong as its partial key has changed | 303 | 23 | // and has to be recalculated. | 304 | 23 | | 305 | 23 | // To handle this situation, we back jump to `ClosestDescendant` but this time | 306 | 23 | // make sure to skip over `calculated_elem`. | 307 | 23 | // This isn't done here but in `TrieNodeRemoveEvent::resume`. | 308 | 23 | InProgress::TrieNodeRemoveEvent(TrieNodeRemoveEvent { | 309 | 23 | inner: self.0, | 310 | 23 | calculated_elem, | 311 | 23 | ty: TrieNodeRemoveEventTy::ReplacedWithSingleChild, | 312 | 23 | }) | 313 | | } | 314 | | | 315 | 19 | (_, None, 1, _parent_node) => { | 316 | 19 | // Same as the previous block, except that `children_partial_key_changed` is | 317 | 19 | // `false`. Therefore the node didn't exist in the base trie, and no event shall | 318 | 19 | // be generated. Instead, we immediately call `resume` in order to continue | 319 | 19 | // execution without notifying the user. | 320 | 19 | TrieNodeRemoveEvent { | 321 | 19 | inner: self.0, | 322 | 19 | calculated_elem, | 323 | 19 | ty: TrieNodeRemoveEventTy::ReplacedWithSingleChild, | 324 | 19 | } | 325 | 19 | .resume() | 326 | | } | 327 | | | 328 | | (Some(_), None, 0, None) => { | 329 | | // Root node of the trie was deleted and trie is now empty. | 330 | 3 | InProgress::TrieNodeRemoveEvent(TrieNodeRemoveEvent { | 331 | 3 | inner: self.0, | 332 | 3 | calculated_elem, | 333 | 3 | ty: TrieNodeRemoveEventTy::NoChildrenLeft, | 334 | 3 | }) | 335 | | } | 336 | | | 337 | | (None, None, 0, None) => { | 338 | | // Trie is empty. | 339 | | // This case is handled separately in order to not generate | 340 | | // a `TrieNodeInsertUpdateEvent` for a node that doesn't actually exist. | 341 | 0 | InProgress::Finished { | 342 | 0 | trie_root_hash: trie::EMPTY_BLAKE2_TRIE_MERKLE_VALUE, | 343 | 0 | } | 344 | | } | 345 | | | 346 | 366k | (_, _, _, parent_node) => { | 347 | | // Trie node still exists or was created. Calculate its Merkle value. | 348 | | | 349 | | // Due to some borrow checker troubles, we need to calculate the storage value | 350 | | // hash ahead of time if relevant. | 351 | 366k | let storage_value_hash = | 352 | 366k | if let Some((value148k , TrieEntryVersion::V1)) = maybe_storage_value { | 353 | 148k | if value.len() >= 33 { | 354 | 100 | Some(blake2_rfc::blake2b::blake2b(32, &[], value)) | 355 | | } else { | 356 | 148k | None | 357 | | } | 358 | | } else { | 359 | 217k | None | 360 | | }; | 361 | 366k | let merkle_value = trie::trie_node::calculate_merkle_value( | 362 | | trie::trie_node::Decoded { | 363 | 366k | children: array::from_fn(|n| calculated_elem.children[n].as_ref()), | 364 | 366k | partial_key: calculated_elem.partial_key.iter().copied(), | 365 | 366k | storage_value: match (maybe_storage_value, storage_value_hash.as_ref()) { | 366 | 100 | (_, Some(storage_value_hash)) => trie::trie_node::StorageValue::Hashed( | 367 | 100 | <&[u8; 32]>::try_from(storage_value_hash.as_bytes()) | 368 | 100 | .unwrap_or_else(|_| panic!()), | 369 | 100 | ), | 370 | 299k | (Some((value, _)), None) => { | 371 | 299k | trie::trie_node::StorageValue::Unhashed(value) | 372 | | } | 373 | 67.1k | (None, _) => trie::trie_node::StorageValue::None, | 374 | | }, | 375 | | }, | 376 | 366k | trie::HashFunction::Blake2, | 377 | 366k | parent_node.is_none(), | 378 | 366k | ) | 379 | 366k | .unwrap_or_else(|_| panic!()); | 380 | 366k | | 381 | 366k | // The stack is updated in `TrieNodeInsertUpdateEvent::resume`. | 382 | 366k | InProgress::TrieNodeInsertUpdateEvent(TrieNodeInsertUpdateEvent { | 383 | 366k | inner: self.0, | 384 | 366k | children: calculated_elem.children, | 385 | 366k | inserted_elem_partial_key: calculated_elem.partial_key, | 386 | 366k | merkle_value, | 387 | 366k | }) | 388 | | } | 389 | | } | 390 | 366k | } |
Unexecuted instantiation: _RNvMs_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB4_12StorageValue12inject_value |
391 | | } |
392 | | |
393 | | /// In order to continue, must fetch the Merkle value of the closest descendant to the given key |
394 | | /// in the base trie. |
395 | | /// |
396 | | /// It is possible to continue the calculation even if the Merkle value is unknown, in which case |
397 | | /// the calculation will walk down the trie in order to calculate the Merkle value manually. |
398 | | pub struct ClosestDescendantMerkleValue { |
399 | | inner: Box<Inner>, |
400 | | } |
401 | | |
402 | | impl ClosestDescendantMerkleValue { |
403 | | /// Returns an iterator of slices, which, when joined together, form the full key of the trie |
404 | | /// node whose closest descendant Merkle value must be fetched. |
405 | 653k | pub fn key(&'_ self) -> impl Iterator<Item = impl AsRef<[Nibble]> + '_> + '_ { |
406 | 653k | // A `ClosestDescendantMerkleValue` is created directly in response to a `ClosestAncestor` without |
407 | 653k | // updating the `Inner`. |
408 | 653k | self.inner.current_node_full_key() |
409 | 653k | } _RNvMs0_NtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB5_28ClosestDescendantMerkleValue3key Line | Count | Source | 405 | 653k | pub fn key(&'_ self) -> impl Iterator<Item = impl AsRef<[Nibble]> + '_> + '_ { | 406 | 653k | // A `ClosestDescendantMerkleValue` is created directly in response to a `ClosestAncestor` without | 407 | 653k | // updating the `Inner`. | 408 | 653k | self.inner.current_node_full_key() | 409 | 653k | } |
Unexecuted instantiation: _RNvMs0_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB5_28ClosestDescendantMerkleValue3key |
410 | | |
411 | | /// Returns the same value as [`ClosestDescendantMerkleValue::key`] but as a `Vec`. |
412 | 653k | pub fn key_as_vec(&self) -> Vec<Nibble> { |
413 | 2.57M | self.key().fold(Vec::new(), |mut a, b| { |
414 | 2.57M | a.extend_from_slice(b.as_ref()); |
415 | 2.57M | a |
416 | 2.57M | }) _RNCNvMs0_NtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB7_28ClosestDescendantMerkleValue10key_as_vec0Bb_ Line | Count | Source | 413 | 2.57M | self.key().fold(Vec::new(), |mut a, b| { | 414 | 2.57M | a.extend_from_slice(b.as_ref()); | 415 | 2.57M | a | 416 | 2.57M | }) |
Unexecuted instantiation: _RNCNvMs0_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB7_28ClosestDescendantMerkleValue10key_as_vec0Bb_ |
417 | 653k | } _RNvMs0_NtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB5_28ClosestDescendantMerkleValue10key_as_vec Line | Count | Source | 412 | 653k | pub fn key_as_vec(&self) -> Vec<Nibble> { | 413 | 653k | self.key().fold(Vec::new(), |mut a, b| { | 414 | | a.extend_from_slice(b.as_ref()); | 415 | | a | 416 | 653k | }) | 417 | 653k | } |
Unexecuted instantiation: _RNvMs0_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB5_28ClosestDescendantMerkleValue10key_as_vec |
418 | | |
419 | | /// Indicate that the closest descendant or its Merkle value is unknown and resume the |
420 | | /// calculation. |
421 | | /// |
422 | | /// This function be used if you are unaware of the Merkle value. The algorithm will perform |
423 | | /// the calculation of this Merkle value manually, which takes more time. |
424 | 860k | pub fn resume_unknown(self) -> InProgress { |
425 | 860k | // The element currently being iterated was `Btcd`, and is now switched to being |
426 | 860k | // `MaybeNodeKey`. Because a `ClosestDescendantMerkleValue` is only ever created if the diff doesn't |
427 | 860k | // contain any entry that descends the currently iterated node, we know for sure that |
428 | 860k | // `MaybeNodeKey` is equal to `Btcd`. |
429 | 860k | InProgress::ClosestDescendant(ClosestDescendant { |
430 | 860k | inner: self.inner, |
431 | 860k | key_extra_nibbles: Vec::new(), |
432 | 860k | diff_inserts_lcd: None, |
433 | 860k | }) |
434 | 860k | } _RNvMs0_NtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB5_28ClosestDescendantMerkleValue14resume_unknown Line | Count | Source | 424 | 860k | pub fn resume_unknown(self) -> InProgress { | 425 | 860k | // The element currently being iterated was `Btcd`, and is now switched to being | 426 | 860k | // `MaybeNodeKey`. Because a `ClosestDescendantMerkleValue` is only ever created if the diff doesn't | 427 | 860k | // contain any entry that descends the currently iterated node, we know for sure that | 428 | 860k | // `MaybeNodeKey` is equal to `Btcd`. | 429 | 860k | InProgress::ClosestDescendant(ClosestDescendant { | 430 | 860k | inner: self.inner, | 431 | 860k | key_extra_nibbles: Vec::new(), | 432 | 860k | diff_inserts_lcd: None, | 433 | 860k | }) | 434 | 860k | } |
Unexecuted instantiation: _RNvMs0_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB5_28ClosestDescendantMerkleValue14resume_unknown |
435 | | |
436 | | /// Indicate the Merkle value of closest descendant of the trie node indicated by |
437 | | /// [`ClosestDescendantMerkleValue::key`] and resume the calculation. |
438 | 16.2k | pub fn inject_merkle_value(mut self, merkle_value: &[u8]) -> InProgress { |
439 | 16.2k | // We are after a call to `BaseTrieClosestDescendantMerkleValue` in the algorithm shown |
440 | 16.2k | // at the top. |
441 | 16.2k | |
442 | 16.2k | // Check with a debug_assert! that this is a valid Merkle value. While this algorithm |
443 | 16.2k | // doesn't actually care about the content, providing a wrong value clearly indicates a |
444 | 16.2k | // bug somewhere in the API user's code. |
445 | 16.2k | debug_assert!(merkle_value.len() == 32 || trie::trie_node::decode(merkle_value).is_ok()15.7k ); |
446 | | |
447 | 16.2k | if let Some(parent_node) = self.inner.stack.last_mut() { |
448 | | // If the element has a parent, add the Merkle value to its children and resume the |
449 | | // algorithm. |
450 | 16.2k | debug_assert_ne!(parent_node.children.len(), 16); |
451 | 16.2k | parent_node |
452 | 16.2k | .children |
453 | 16.2k | .push(Some(trie::trie_node::MerkleValueOutput::from_bytes( |
454 | 16.2k | AsRef::as_ref(&merkle_value), |
455 | 16.2k | ))); |
456 | 16.2k | self.inner.next() |
457 | | } else { |
458 | | // If the element doesn't have a parent, then the Merkle value is the root of trie! |
459 | | // This should only ever happen if the diff is empty. |
460 | 0 | debug_assert_eq!(self.inner.diff.diff_range_ordered::<Vec<u8>>(..).count(), 0); |
461 | | |
462 | | // The trie root hash is always 32 bytes. If not, it indicates a bug in the API user's |
463 | | // code. |
464 | 0 | let trie_root_hash = <[u8; 32]>::try_from(AsRef::as_ref(&merkle_value)) |
465 | 0 | .unwrap_or_else(|_| panic!("invalid node value provided")); Unexecuted instantiation: _RNCNvMs0_NtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB7_28ClosestDescendantMerkleValue19inject_merkle_value0Bb_ Unexecuted instantiation: _RNCNvMs0_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB7_28ClosestDescendantMerkleValue19inject_merkle_value0Bb_ |
466 | 0 | InProgress::Finished { trie_root_hash } |
467 | | } |
468 | 16.2k | } _RNvMs0_NtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB5_28ClosestDescendantMerkleValue19inject_merkle_value Line | Count | Source | 438 | 16.2k | pub fn inject_merkle_value(mut self, merkle_value: &[u8]) -> InProgress { | 439 | 16.2k | // We are after a call to `BaseTrieClosestDescendantMerkleValue` in the algorithm shown | 440 | 16.2k | // at the top. | 441 | 16.2k | | 442 | 16.2k | // Check with a debug_assert! that this is a valid Merkle value. While this algorithm | 443 | 16.2k | // doesn't actually care about the content, providing a wrong value clearly indicates a | 444 | 16.2k | // bug somewhere in the API user's code. | 445 | 16.2k | debug_assert!(merkle_value.len() == 32 || trie::trie_node::decode(merkle_value).is_ok()15.7k ); | 446 | | | 447 | 16.2k | if let Some(parent_node) = self.inner.stack.last_mut() { | 448 | | // If the element has a parent, add the Merkle value to its children and resume the | 449 | | // algorithm. | 450 | 16.2k | debug_assert_ne!(parent_node.children.len(), 16); | 451 | 16.2k | parent_node | 452 | 16.2k | .children | 453 | 16.2k | .push(Some(trie::trie_node::MerkleValueOutput::from_bytes( | 454 | 16.2k | AsRef::as_ref(&merkle_value), | 455 | 16.2k | ))); | 456 | 16.2k | self.inner.next() | 457 | | } else { | 458 | | // If the element doesn't have a parent, then the Merkle value is the root of trie! | 459 | | // This should only ever happen if the diff is empty. | 460 | 0 | debug_assert_eq!(self.inner.diff.diff_range_ordered::<Vec<u8>>(..).count(), 0); | 461 | | | 462 | | // The trie root hash is always 32 bytes. If not, it indicates a bug in the API user's | 463 | | // code. | 464 | 0 | let trie_root_hash = <[u8; 32]>::try_from(AsRef::as_ref(&merkle_value)) | 465 | 0 | .unwrap_or_else(|_| panic!("invalid node value provided")); | 466 | 0 | InProgress::Finished { trie_root_hash } | 467 | | } | 468 | 16.2k | } |
Unexecuted instantiation: _RNvMs0_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB5_28ClosestDescendantMerkleValue19inject_merkle_value |
469 | | } |
470 | | |
471 | | /// Event indicating that a trie node has been inserted or updated. |
472 | | /// |
473 | | /// The API user has nothing to do, but they can use this event to update their local version of |
474 | | /// the trie. |
475 | | pub struct TrieNodeInsertUpdateEvent { |
476 | | inner: Box<Inner>, |
477 | | |
478 | | /// Partial key of the node that was inserted or updated. |
479 | | inserted_elem_partial_key: Vec<Nibble>, |
480 | | |
481 | | /// Merkle values of the children of the node that was inserted or updated. |
482 | | children: arrayvec::ArrayVec<Option<trie::trie_node::MerkleValueOutput>, 16>, |
483 | | |
484 | | /// Merkle value of the node that was inserted or updated. |
485 | | merkle_value: trie::trie_node::MerkleValueOutput, |
486 | | } |
487 | | |
488 | | impl TrieNodeInsertUpdateEvent { |
489 | | /// Returns the key of the trie node that was inserted or updated. |
490 | 366k | pub fn key(&self) -> impl Iterator<Item = impl AsRef<[Nibble]> + '_> + '_ { |
491 | 366k | self.inner |
492 | 366k | .current_node_full_key() |
493 | 366k | .map(either::Left) |
494 | 366k | .chain(iter::once(either::Right(&self.inserted_elem_partial_key))) |
495 | 366k | } _RNvMs1_NtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB5_25TrieNodeInsertUpdateEvent3key Line | Count | Source | 490 | 366k | pub fn key(&self) -> impl Iterator<Item = impl AsRef<[Nibble]> + '_> + '_ { | 491 | 366k | self.inner | 492 | 366k | .current_node_full_key() | 493 | 366k | .map(either::Left) | 494 | 366k | .chain(iter::once(either::Right(&self.inserted_elem_partial_key))) | 495 | 366k | } |
Unexecuted instantiation: _RNvMs1_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB5_25TrieNodeInsertUpdateEvent3key |
496 | | |
497 | | /// Returns the same value as [`TrieNodeInsertUpdateEvent::key`] but as a `Vec`. |
498 | 500 | pub fn key_as_vec(&self) -> Vec<Nibble> { |
499 | 3.45k | self.key().fold(Vec::new(), |mut a, b| { |
500 | 3.45k | a.extend_from_slice(b.as_ref()); |
501 | 3.45k | a |
502 | 3.45k | }) _RNCNvMs1_NtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB7_25TrieNodeInsertUpdateEvent10key_as_vec0Bb_ Line | Count | Source | 499 | 3.45k | self.key().fold(Vec::new(), |mut a, b| { | 500 | 3.45k | a.extend_from_slice(b.as_ref()); | 501 | 3.45k | a | 502 | 3.45k | }) |
Unexecuted instantiation: _RNCNvMs1_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB7_25TrieNodeInsertUpdateEvent10key_as_vec0Bb_ |
503 | 500 | } _RNvMs1_NtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB5_25TrieNodeInsertUpdateEvent10key_as_vec Line | Count | Source | 498 | 500 | pub fn key_as_vec(&self) -> Vec<Nibble> { | 499 | 500 | self.key().fold(Vec::new(), |mut a, b| { | 500 | | a.extend_from_slice(b.as_ref()); | 501 | | a | 502 | 500 | }) | 503 | 500 | } |
Unexecuted instantiation: _RNvMs1_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB5_25TrieNodeInsertUpdateEvent10key_as_vec |
504 | | |
505 | | /// Returns the new Merkle value of the trie node that was inserted or updated. |
506 | 366k | pub fn merkle_value(&self) -> &[u8] { |
507 | 366k | self.merkle_value.as_ref() |
508 | 366k | } _RNvMs1_NtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB5_25TrieNodeInsertUpdateEvent12merkle_value Line | Count | Source | 506 | 366k | pub fn merkle_value(&self) -> &[u8] { | 507 | 366k | self.merkle_value.as_ref() | 508 | 366k | } |
Unexecuted instantiation: _RNvMs1_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB5_25TrieNodeInsertUpdateEvent12merkle_value |
509 | | |
510 | | /// Returns the Merkle values of the children of the trie node that was inserted or updated. |
511 | | /// |
512 | | /// The iterator always yields exactly 16 elements. The yielded element is `None` if there is |
513 | | /// no child at this position. |
514 | 500 | pub fn children_merkle_values(&self) -> impl ExactSizeIterator<Item = Option<&[u8]>> { |
515 | 500 | self.children |
516 | 500 | .iter() |
517 | 8.00k | .map(|child| child.as_ref().map(|merkle_value| merkle_value.as_ref()489 )) _RNCNvMs1_NtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB7_25TrieNodeInsertUpdateEvent22children_merkle_values0Bb_ Line | Count | Source | 517 | 8.00k | .map(|child| child.as_ref().map(|merkle_value| merkle_value.as_ref())) |
Unexecuted instantiation: _RNCNvMs1_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB7_25TrieNodeInsertUpdateEvent22children_merkle_values0Bb_ _RNCNCNvMs1_NtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB9_25TrieNodeInsertUpdateEvent22children_merkle_values00Bd_ Line | Count | Source | 517 | 489 | .map(|child| child.as_ref().map(|merkle_value| merkle_value.as_ref())) |
Unexecuted instantiation: _RNCNCNvMs1_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB9_25TrieNodeInsertUpdateEvent22children_merkle_values00Bd_ |
518 | 500 | } _RNvMs1_NtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB5_25TrieNodeInsertUpdateEvent22children_merkle_values Line | Count | Source | 514 | 500 | pub fn children_merkle_values(&self) -> impl ExactSizeIterator<Item = Option<&[u8]>> { | 515 | 500 | self.children | 516 | 500 | .iter() | 517 | 500 | .map(|child| child.as_ref().map(|merkle_value| merkle_value.as_ref())) | 518 | 500 | } |
Unexecuted instantiation: _RNvMs1_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB5_25TrieNodeInsertUpdateEvent22children_merkle_values |
519 | | |
520 | | /// Returns the partial key of the trie node that was inserted or updated. |
521 | 500 | pub fn partial_key(&self) -> &[Nibble] { |
522 | 500 | &self.inserted_elem_partial_key |
523 | 500 | } _RNvMs1_NtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB5_25TrieNodeInsertUpdateEvent11partial_key Line | Count | Source | 521 | 500 | pub fn partial_key(&self) -> &[Nibble] { | 522 | 500 | &self.inserted_elem_partial_key | 523 | 500 | } |
Unexecuted instantiation: _RNvMs1_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB5_25TrieNodeInsertUpdateEvent11partial_key |
524 | | |
525 | | /// Resume the computation. |
526 | 366k | pub fn resume(mut self) -> InProgress { |
527 | 366k | if let Some(parent_node333k ) = self.inner.stack.last_mut() { |
528 | 333k | parent_node.children.push(Some(self.merkle_value)); |
529 | 333k | self.inner.next() |
530 | | } else { |
531 | | // No more node in the stack means that this was the root node. The calculated |
532 | | // Merkle value is the trie root hash. |
533 | 32.7k | InProgress::Finished { |
534 | 32.7k | // Guaranteed to never panic for the root node. |
535 | 32.7k | trie_root_hash: self.merkle_value.try_into().unwrap_or_else(|_| panic!()0 ), Unexecuted instantiation: _RNCNvMs1_NtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB7_25TrieNodeInsertUpdateEvent6resume0Bb_ Unexecuted instantiation: _RNCNvMs1_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB7_25TrieNodeInsertUpdateEvent6resume0Bb_ |
536 | 32.7k | } |
537 | | } |
538 | 366k | } _RNvMs1_NtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB5_25TrieNodeInsertUpdateEvent6resume Line | Count | Source | 526 | 366k | pub fn resume(mut self) -> InProgress { | 527 | 366k | if let Some(parent_node333k ) = self.inner.stack.last_mut() { | 528 | 333k | parent_node.children.push(Some(self.merkle_value)); | 529 | 333k | self.inner.next() | 530 | | } else { | 531 | | // No more node in the stack means that this was the root node. The calculated | 532 | | // Merkle value is the trie root hash. | 533 | 32.7k | InProgress::Finished { | 534 | 32.7k | // Guaranteed to never panic for the root node. | 535 | 32.7k | trie_root_hash: self.merkle_value.try_into().unwrap_or_else(|_| panic!()), | 536 | 32.7k | } | 537 | | } | 538 | 366k | } |
Unexecuted instantiation: _RNvMs1_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB5_25TrieNodeInsertUpdateEvent6resume |
539 | | } |
540 | | |
541 | | /// Event indicating that a trie node has been destroyed. |
542 | | /// |
543 | | /// The API user has nothing to do, but they can use this event to update their local version of |
544 | | /// the trie. |
545 | | pub struct TrieNodeRemoveEvent { |
546 | | inner: Box<Inner>, |
547 | | |
548 | | /// Element that was removed from the stack and that we know no longer exists. |
549 | | calculated_elem: InProgressNode, |
550 | | |
551 | | /// Why the node was removed. |
552 | | ty: TrieNodeRemoveEventTy, |
553 | | } |
554 | | |
555 | | enum TrieNodeRemoveEventTy { |
556 | | NoChildrenLeft, |
557 | | ReplacedWithSingleChild, |
558 | | } |
559 | | |
560 | | impl TrieNodeRemoveEvent { |
561 | | /// Returns the key of the trie node that was removed. |
562 | 118 | pub fn key(&self) -> impl Iterator<Item = impl AsRef<[Nibble]> + '_> + '_ { |
563 | 118 | self.inner |
564 | 118 | .current_node_full_key() |
565 | 118 | .map(either::Left) |
566 | 118 | .chain(iter::once(either::Right(&self.calculated_elem.partial_key))) |
567 | 118 | } _RNvMs2_NtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB5_19TrieNodeRemoveEvent3key Line | Count | Source | 562 | 118 | pub fn key(&self) -> impl Iterator<Item = impl AsRef<[Nibble]> + '_> + '_ { | 563 | 118 | self.inner | 564 | 118 | .current_node_full_key() | 565 | 118 | .map(either::Left) | 566 | 118 | .chain(iter::once(either::Right(&self.calculated_elem.partial_key))) | 567 | 118 | } |
Unexecuted instantiation: _RNvMs2_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB5_19TrieNodeRemoveEvent3key |
568 | | |
569 | | /// Returns the same value as [`TrieNodeRemoveEvent::key`] but as a `Vec`. |
570 | 13 | pub fn key_as_vec(&self) -> Vec<Nibble> { |
571 | 101 | self.key().fold(Vec::new(), |mut a, b| { |
572 | 101 | a.extend_from_slice(b.as_ref()); |
573 | 101 | a |
574 | 101 | }) _RNCNvMs2_NtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB7_19TrieNodeRemoveEvent10key_as_vec0Bb_ Line | Count | Source | 571 | 101 | self.key().fold(Vec::new(), |mut a, b| { | 572 | 101 | a.extend_from_slice(b.as_ref()); | 573 | 101 | a | 574 | 101 | }) |
Unexecuted instantiation: _RNCNvMs2_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB7_19TrieNodeRemoveEvent10key_as_vec0Bb_ |
575 | 13 | } _RNvMs2_NtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB5_19TrieNodeRemoveEvent10key_as_vec Line | Count | Source | 570 | 13 | pub fn key_as_vec(&self) -> Vec<Nibble> { | 571 | 13 | self.key().fold(Vec::new(), |mut a, b| { | 572 | | a.extend_from_slice(b.as_ref()); | 573 | | a | 574 | 13 | }) | 575 | 13 | } |
Unexecuted instantiation: _RNvMs2_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB5_19TrieNodeRemoveEvent10key_as_vec |
576 | | |
577 | | /// Resume the computation. |
578 | 137 | pub fn resume(mut self) -> InProgress { |
579 | 137 | match self.ty { |
580 | | TrieNodeRemoveEventTy::NoChildrenLeft => { |
581 | 95 | if let Some(parent_node92 ) = self.inner.stack.last_mut() { |
582 | 92 | parent_node.children.push(None); |
583 | 92 | self.inner.next() |
584 | | } else { |
585 | 3 | InProgress::Finished { |
586 | 3 | trie_root_hash: trie::EMPTY_BLAKE2_TRIE_MERKLE_VALUE, |
587 | 3 | } |
588 | | } |
589 | | } |
590 | | TrieNodeRemoveEventTy::ReplacedWithSingleChild => { |
591 | 42 | let child_index = self |
592 | 42 | .calculated_elem |
593 | 42 | .children |
594 | 42 | .iter() |
595 | 371 | .position(|c| c.is_some()) _RNCNvMs2_NtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB7_19TrieNodeRemoveEvent6resume0Bb_ Line | Count | Source | 595 | 371 | .position(|c| c.is_some()) |
Unexecuted instantiation: _RNCNvMs2_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB7_19TrieNodeRemoveEvent6resume0Bb_ |
596 | 42 | .unwrap_or_else(|| panic!()0 ); Unexecuted instantiation: _RNCNvMs2_NtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB7_19TrieNodeRemoveEvent6resumes_0Bb_ Unexecuted instantiation: _RNCNvMs2_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB7_19TrieNodeRemoveEvent6resumes_0Bb_ |
597 | 42 | |
598 | 42 | let mut partial_key = self.calculated_elem.partial_key; |
599 | 42 | partial_key.push( |
600 | 42 | Nibble::try_from(u8::try_from(child_index).unwrap_or_else(|_| panic!()0 )) Unexecuted instantiation: _RNCNvMs2_NtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB7_19TrieNodeRemoveEvent6resumes0_0Bb_ Unexecuted instantiation: _RNCNvMs2_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB7_19TrieNodeRemoveEvent6resumes0_0Bb_ |
601 | 42 | .unwrap_or_else(|_| panic!()0 ), Unexecuted instantiation: _RNCNvMs2_NtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB7_19TrieNodeRemoveEvent6resumes1_0Bb_ Unexecuted instantiation: _RNCNvMs2_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB7_19TrieNodeRemoveEvent6resumes1_0Bb_ |
602 | 42 | ); |
603 | 42 | |
604 | 42 | // Now calculate `LongestCommonDenominator(DiffInsertsNodesWithPrefix)`. |
605 | 42 | let (_, diff_inserts_lcd) = diff_inserts_least_common_denominator( |
606 | 42 | &self.inner.diff, |
607 | 42 | self.inner |
608 | 42 | .current_node_full_key() |
609 | 42 | .map(either::Left) |
610 | 42 | .chain(iter::once(either::Right(&partial_key))), |
611 | 42 | ); |
612 | 42 | |
613 | 42 | InProgress::ClosestDescendant(ClosestDescendant { |
614 | 42 | inner: self.inner, |
615 | 42 | key_extra_nibbles: partial_key, |
616 | 42 | diff_inserts_lcd, |
617 | 42 | }) |
618 | | } |
619 | | } |
620 | 137 | } _RNvMs2_NtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB5_19TrieNodeRemoveEvent6resume Line | Count | Source | 578 | 137 | pub fn resume(mut self) -> InProgress { | 579 | 137 | match self.ty { | 580 | | TrieNodeRemoveEventTy::NoChildrenLeft => { | 581 | 95 | if let Some(parent_node92 ) = self.inner.stack.last_mut() { | 582 | 92 | parent_node.children.push(None); | 583 | 92 | self.inner.next() | 584 | | } else { | 585 | 3 | InProgress::Finished { | 586 | 3 | trie_root_hash: trie::EMPTY_BLAKE2_TRIE_MERKLE_VALUE, | 587 | 3 | } | 588 | | } | 589 | | } | 590 | | TrieNodeRemoveEventTy::ReplacedWithSingleChild => { | 591 | 42 | let child_index = self | 592 | 42 | .calculated_elem | 593 | 42 | .children | 594 | 42 | .iter() | 595 | 42 | .position(|c| c.is_some()) | 596 | 42 | .unwrap_or_else(|| panic!()); | 597 | 42 | | 598 | 42 | let mut partial_key = self.calculated_elem.partial_key; | 599 | 42 | partial_key.push( | 600 | 42 | Nibble::try_from(u8::try_from(child_index).unwrap_or_else(|_| panic!())) | 601 | 42 | .unwrap_or_else(|_| panic!()), | 602 | 42 | ); | 603 | 42 | | 604 | 42 | // Now calculate `LongestCommonDenominator(DiffInsertsNodesWithPrefix)`. | 605 | 42 | let (_, diff_inserts_lcd) = diff_inserts_least_common_denominator( | 606 | 42 | &self.inner.diff, | 607 | 42 | self.inner | 608 | 42 | .current_node_full_key() | 609 | 42 | .map(either::Left) | 610 | 42 | .chain(iter::once(either::Right(&partial_key))), | 611 | 42 | ); | 612 | 42 | | 613 | 42 | InProgress::ClosestDescendant(ClosestDescendant { | 614 | 42 | inner: self.inner, | 615 | 42 | key_extra_nibbles: partial_key, | 616 | 42 | diff_inserts_lcd, | 617 | 42 | }) | 618 | | } | 619 | | } | 620 | 137 | } |
Unexecuted instantiation: _RNvMs2_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB5_19TrieNodeRemoveEvent6resume |
621 | | } |
622 | | |
623 | | struct Inner { |
624 | | /// Stack of node entries whose value is currently being calculated. Every time |
625 | | /// `BaseTrieClosestDescendant` returns we push an element here. |
626 | | /// |
627 | | /// The node currently being iterated is either `Btcd` or `MaybeNodeValue` depending on where |
628 | | /// we are in the algorithm. |
629 | | /// |
630 | | /// If the entry at the top of the stack has `children.len() == 16`, then the node currently |
631 | | /// being iterated is the one at the top of the stack, otherwise it's the child of the one at |
632 | | /// the top of the stack whose entry is past the end of `children`. |
633 | | stack: Vec<InProgressNode>, |
634 | | |
635 | | /// Same value as [`Config::diff`]. |
636 | | diff: TrieDiff, |
637 | | |
638 | | /// Same value as [`Config::diff_trie_entries_version`]. |
639 | | diff_trie_entries_version: TrieEntryVersion, |
640 | | } |
641 | | |
642 | | #[derive(Debug)] |
643 | | struct InProgressNode { |
644 | | /// Partial key of the node currently being calculated. |
645 | | partial_key: Vec<Nibble>, |
646 | | |
647 | | /// If `true`, the partial keys of the children of this node have changed compared to their |
648 | | /// values in the base trie. |
649 | | children_partial_key_changed: bool, |
650 | | |
651 | | /// Merkle values of the children of the node. Filled up to 16 elements, then the storage |
652 | | /// value is requested. Each element is `Some` or `None` depending on whether a child exists. |
653 | | children: arrayvec::ArrayVec<Option<trie::trie_node::MerkleValueOutput>, 16>, |
654 | | } |
655 | | |
656 | | impl Inner { |
657 | | /// Analyzes the content of the [`Inner`] and progresses the algorithm. |
658 | 6.26M | fn next(self: Box<Self>) -> InProgress { |
659 | 6.26M | if self.stack.last().map_or(false, |n| n.children.len() == 166.23M ) { _RNCNvMs3_NtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB7_5Inner4next0Bb_ Line | Count | Source | 659 | 6.23M | if self.stack.last().map_or(false, |n| n.children.len() == 16) { |
Unexecuted instantiation: _RNCNvMs3_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB7_5Inner4next0Bb_ |
660 | | // Finished obtaining `MaybeChildren` and jumping to obtaining `MaybeStorageValue`. |
661 | 366k | return InProgress::StorageValue(StorageValue(self)); |
662 | 5.89M | } |
663 | 5.89M | |
664 | 5.89M | // In the paths below, we want to obtain `MaybeChildren` and thus we're going to return |
665 | 5.89M | // a `ClosestDescendant`. |
666 | 5.89M | // Now calculate `ForceCalculate` and |
667 | 5.89M | // `LongestCommonDenominator(DiffInsertsNodesWithPrefix)`. |
668 | 5.89M | let (force_recalculate, diff_inserts_lcd) = |
669 | 5.89M | diff_inserts_least_common_denominator(&self.diff, self.current_node_full_key()); |
670 | 5.89M | |
671 | 5.89M | // If the diff doesn't contain any descendant, jump to calling `BaseTrieMerkleValue`. |
672 | 5.89M | if !force_recalculate |
673 | 5.56M | && diff_inserts_lcd.is_none() |
674 | 5.56M | && self |
675 | 5.56M | .stack |
676 | 5.56M | .last() |
677 | 5.56M | .map_or(true, |n| !n.children_partial_key_changed5.56M ) _RNCNvMs3_NtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB7_5Inner4nexts_0Bb_ Line | Count | Source | 677 | 5.56M | .map_or(true, |n| !n.children_partial_key_changed) |
Unexecuted instantiation: _RNCNvMs3_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB7_5Inner4nexts_0Bb_ |
678 | | { |
679 | 876k | return InProgress::ClosestDescendantMerkleValue(ClosestDescendantMerkleValue { |
680 | 876k | inner: self, |
681 | 876k | }); |
682 | 5.02M | } |
683 | 5.02M | |
684 | 5.02M | InProgress::ClosestDescendant(ClosestDescendant { |
685 | 5.02M | inner: self, |
686 | 5.02M | key_extra_nibbles: Vec::new(), |
687 | 5.02M | diff_inserts_lcd, |
688 | 5.02M | }) |
689 | 6.26M | } _RNvMs3_NtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB5_5Inner4next Line | Count | Source | 658 | 6.26M | fn next(self: Box<Self>) -> InProgress { | 659 | 6.26M | if self.stack.last().map_or(false, |n| n.children.len() == 16) { | 660 | | // Finished obtaining `MaybeChildren` and jumping to obtaining `MaybeStorageValue`. | 661 | 366k | return InProgress::StorageValue(StorageValue(self)); | 662 | 5.89M | } | 663 | 5.89M | | 664 | 5.89M | // In the paths below, we want to obtain `MaybeChildren` and thus we're going to return | 665 | 5.89M | // a `ClosestDescendant`. | 666 | 5.89M | // Now calculate `ForceCalculate` and | 667 | 5.89M | // `LongestCommonDenominator(DiffInsertsNodesWithPrefix)`. | 668 | 5.89M | let (force_recalculate, diff_inserts_lcd) = | 669 | 5.89M | diff_inserts_least_common_denominator(&self.diff, self.current_node_full_key()); | 670 | 5.89M | | 671 | 5.89M | // If the diff doesn't contain any descendant, jump to calling `BaseTrieMerkleValue`. | 672 | 5.89M | if !force_recalculate | 673 | 5.56M | && diff_inserts_lcd.is_none() | 674 | 5.56M | && self | 675 | 5.56M | .stack | 676 | 5.56M | .last() | 677 | 5.56M | .map_or(true, |n| !n.children_partial_key_changed) | 678 | | { | 679 | 876k | return InProgress::ClosestDescendantMerkleValue(ClosestDescendantMerkleValue { | 680 | 876k | inner: self, | 681 | 876k | }); | 682 | 5.02M | } | 683 | 5.02M | | 684 | 5.02M | InProgress::ClosestDescendant(ClosestDescendant { | 685 | 5.02M | inner: self, | 686 | 5.02M | key_extra_nibbles: Vec::new(), | 687 | 5.02M | diff_inserts_lcd, | 688 | 5.02M | }) | 689 | 6.26M | } |
Unexecuted instantiation: _RNvMs3_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB5_5Inner4next |
690 | | |
691 | | /// Iterator of arrays which, when joined together, form the full key of the node currently |
692 | | /// being iterated. |
693 | 22.6M | fn current_node_full_key(&'_ self) -> impl Iterator<Item = impl AsRef<[Nibble]> + '_> + '_ { |
694 | 50.2M | self.stack.iter().flat_map(move |node| { |
695 | 50.2M | let maybe_child_nibble_u8 = |
696 | 50.2M | u8::try_from(node.children.len()).unwrap_or_else(|_| unreachable!()0 ); Unexecuted instantiation: _RNCNCNvMs3_NtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB9_5Inner21current_node_full_key00Bd_ Unexecuted instantiation: _RNCNCNvMs3_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB9_5Inner21current_node_full_key00CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNCNvMs3_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB9_5Inner21current_node_full_key00Bd_ Unexecuted instantiation: _RNCNCNvMs3_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB9_5Inner21current_node_full_key00CsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RNCNCNvMs3_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB9_5Inner21current_node_full_key00CsiUjFBJteJ7x_17smoldot_full_node Unexecuted instantiation: _RNCNCNvMs3_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB9_5Inner21current_node_full_key00CscDgN54JpMGG_6author Unexecuted instantiation: _RNCNCNvMs3_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB9_5Inner21current_node_full_key00CsibGXYHQB8Ea_25json_rpc_general_requests |
697 | 50.2M | let child_nibble = Nibble::try_from(maybe_child_nibble_u8).ok(); |
698 | 50.2M | |
699 | 50.2M | iter::once(either::Right(&node.partial_key)) |
700 | 50.2M | .chain(child_nibble.map(|n| either::Left([n])49.2M )) _RNCNCNvMs3_NtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB9_5Inner21current_node_full_key0s_0Bd_ Line | Count | Source | 700 | 49.2M | .chain(child_nibble.map(|n| either::Left([n]))) |
Unexecuted instantiation: _RNCNCNvMs3_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB9_5Inner21current_node_full_key0s_0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNCNvMs3_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB9_5Inner21current_node_full_key0s_0Bd_ Unexecuted instantiation: _RNCNCNvMs3_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB9_5Inner21current_node_full_key0s_0CsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RNCNCNvMs3_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB9_5Inner21current_node_full_key0s_0CsiUjFBJteJ7x_17smoldot_full_node Unexecuted instantiation: _RNCNCNvMs3_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB9_5Inner21current_node_full_key0s_0CscDgN54JpMGG_6author Unexecuted instantiation: _RNCNCNvMs3_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB9_5Inner21current_node_full_key0s_0CsibGXYHQB8Ea_25json_rpc_general_requests |
701 | 50.2M | }) _RNCNvMs3_NtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB7_5Inner21current_node_full_key0Bb_ Line | Count | Source | 694 | 50.2M | self.stack.iter().flat_map(move |node| { | 695 | 50.2M | let maybe_child_nibble_u8 = | 696 | 50.2M | u8::try_from(node.children.len()).unwrap_or_else(|_| unreachable!()); | 697 | 50.2M | let child_nibble = Nibble::try_from(maybe_child_nibble_u8).ok(); | 698 | 50.2M | | 699 | 50.2M | iter::once(either::Right(&node.partial_key)) | 700 | 50.2M | .chain(child_nibble.map(|n| either::Left([n]))) | 701 | 50.2M | }) |
Unexecuted instantiation: _RNCNvMs3_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB7_5Inner21current_node_full_key0CsDDUKWWCHAU_18smoldot_light_wasm Unexecuted instantiation: _RNCNvMs3_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB7_5Inner21current_node_full_key0Bb_ Unexecuted instantiation: _RNCNvMs3_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB7_5Inner21current_node_full_key0CsiLzmwikkc22_14json_rpc_basic Unexecuted instantiation: _RNCNvMs3_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB7_5Inner21current_node_full_key0CsiUjFBJteJ7x_17smoldot_full_node Unexecuted instantiation: _RNCNvMs3_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB7_5Inner21current_node_full_key0CscDgN54JpMGG_6author Unexecuted instantiation: _RNCNvMs3_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB7_5Inner21current_node_full_key0CsibGXYHQB8Ea_25json_rpc_general_requests |
702 | 22.6M | } _RNvMs3_NtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculatorNtB5_5Inner21current_node_full_key Line | Count | Source | 693 | 22.6M | fn current_node_full_key(&'_ self) -> impl Iterator<Item = impl AsRef<[Nibble]> + '_> + '_ { | 694 | 22.6M | self.stack.iter().flat_map(move |node| { | 695 | | let maybe_child_nibble_u8 = | 696 | | u8::try_from(node.children.len()).unwrap_or_else(|_| unreachable!()); | 697 | | let child_nibble = Nibble::try_from(maybe_child_nibble_u8).ok(); | 698 | | | 699 | | iter::once(either::Right(&node.partial_key)) | 700 | | .chain(child_nibble.map(|n| either::Left([n]))) | 701 | 22.6M | }) | 702 | 22.6M | } |
Unexecuted instantiation: _RNvMs3_NtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculatorNtB5_5Inner21current_node_full_key |
703 | | } |
704 | | |
705 | | /// Given a diff and a prefix, returns: |
706 | | /// |
707 | | /// - Whether the diff contains any entry starts with this prefix. |
708 | | /// - The least common denominator of all the insertions that start with this prefix, or `None` if |
709 | | /// there is no insertion. |
710 | | /// |
711 | 5.89M | fn diff_inserts_least_common_denominator( |
712 | 5.89M | diff: &TrieDiff, |
713 | 5.89M | prefix: impl Iterator<Item = impl AsRef<[Nibble]>>, |
714 | 5.89M | ) -> (bool, Option<Vec<Nibble>>) { |
715 | 5.89M | let mut force_recalculate = false; |
716 | 5.89M | let mut diff_inserts_lcd = None::<Vec<Nibble>>; |
717 | 5.89M | |
718 | 5.89M | // TODO: could be optimized? |
719 | 26.4M | let prefix_nibbles = prefix.fold(Vec::new(), |mut a, b| { |
720 | 26.4M | a.extend_from_slice(b.as_ref()); |
721 | 26.4M | a |
722 | 26.4M | }); _RNCINvNtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculator37diff_inserts_least_common_denominatorINtCs1qmLyiTSqYF_6either6EitherANtNtNtB8_4trie6nibble6Nibblej1_RINtNtCsdZExvAaxgia_5alloc3vec3VecB27_EEINtNtNtNtCsaYZPK01V26L_4core4iter8adapters7flatten7FlatMapINtNtNtB3p_5slice4iter4IterNtB4_14InProgressNodeEINtNtB3l_5chain5ChainINtNtNtB3n_7sources4once4OnceB1B_EINtNtB3p_6option8IntoIterB1B_EENCNvMs3_B4_NtB4_5Inner21current_node_full_key0EE0B8_ Line | Count | Source | 719 | 26.4M | let prefix_nibbles = prefix.fold(Vec::new(), |mut a, b| { | 720 | 26.4M | a.extend_from_slice(b.as_ref()); | 721 | 26.4M | a | 722 | 26.4M | }); |
_RNCINvNtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculator37diff_inserts_least_common_denominatorINtCs1qmLyiTSqYF_6either6EitherIB1C_ANtNtNtB8_4trie6nibble6Nibblej1_RINtNtCsdZExvAaxgia_5alloc3vec3VecB2c_EEB2H_EINtNtNtNtCsaYZPK01V26L_4core4iter8adapters5chain5ChainINtNtB3v_3map3MapINtNtB3v_7flatten7FlatMapINtNtNtB3z_5slice4iter4IterNtB4_14InProgressNodeEIB3r_INtNtNtB3x_7sources4once4OnceB26_EINtNtB3z_6option8IntoIterB26_EENCNvMs3_B4_NtB4_5Inner21current_node_full_key0ENcNtB1B_4Left0EIB5R_B1B_EEE0B8_ Line | Count | Source | 719 | 106 | let prefix_nibbles = prefix.fold(Vec::new(), |mut a, b| { | 720 | 106 | a.extend_from_slice(b.as_ref()); | 721 | 106 | a | 722 | 106 | }); |
Unexecuted instantiation: _RNCINvNtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculator37diff_inserts_least_common_denominatorINtCs1qmLyiTSqYF_6either6EitherANtNtNtB8_4trie6nibble6Nibblej1_RINtNtCsdZExvAaxgia_5alloc3vec3VecB28_EEINtNtNtNtCsaYZPK01V26L_4core4iter8adapters7flatten7FlatMapINtNtNtB3q_5slice4iter4IterNtB4_14InProgressNodeEINtNtB3m_5chain5ChainINtNtNtB3o_7sources4once4OnceB1C_EINtNtB3q_6option8IntoIterB1C_EENCNvMs3_B4_NtB4_5Inner21current_node_full_key0EE0B8_ Unexecuted instantiation: _RNCINvNtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculator37diff_inserts_least_common_denominatorINtCs1qmLyiTSqYF_6either6EitherIB1D_ANtNtNtB8_4trie6nibble6Nibblej1_RINtNtCsdZExvAaxgia_5alloc3vec3VecB2d_EEB2I_EINtNtNtNtCsaYZPK01V26L_4core4iter8adapters5chain5ChainINtNtB3w_3map3MapINtNtB3w_7flatten7FlatMapINtNtNtB3A_5slice4iter4IterNtB4_14InProgressNodeEIB3s_INtNtNtB3y_7sources4once4OnceB27_EINtNtB3A_6option8IntoIterB27_EENCNvMs3_B4_NtB4_5Inner21current_node_full_key0ENcNtB1C_4Left0EIB5S_B1C_EEE0B8_ |
723 | 5.89M | let prefix = |
724 | 5.89M | trie::nibbles_to_bytes_suffix_extend(prefix_nibbles.iter().copied()).collect::<Vec<_>>(); |
725 | 5.76M | for (key, inserts_entry) in |
726 | 5.89M | diff.diff_range_ordered::<[u8]>((ops::Bound::Included(&prefix[..]), ops::Bound::Unbounded)) |
727 | | { |
728 | 5.76M | let key = trie::bytes_to_nibbles(key.iter().copied()).collect::<Vec<_>>(); |
729 | 5.76M | if !key.starts_with(&prefix_nibbles) { |
730 | 5.13M | break; |
731 | 629k | } |
732 | 629k | |
733 | 629k | force_recalculate = true; |
734 | 629k | |
735 | 629k | if inserts_entry { |
736 | 617k | diff_inserts_lcd = match diff_inserts_lcd.take() { |
737 | 284k | Some(mut v) => { |
738 | 284k | let lcd = key.iter().zip(v.iter()).take_while(|(a, b)| a == b118k ).count(); _RNCINvNtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculator37diff_inserts_least_common_denominatorINtCs1qmLyiTSqYF_6either6EitherANtNtNtB8_4trie6nibble6Nibblej1_RINtNtCsdZExvAaxgia_5alloc3vec3VecB27_EEINtNtNtNtCsaYZPK01V26L_4core4iter8adapters7flatten7FlatMapINtNtNtB3p_5slice4iter4IterNtB4_14InProgressNodeEINtNtB3l_5chain5ChainINtNtNtB3n_7sources4once4OnceB1B_EINtNtB3p_6option8IntoIterB1B_EENCNvMs3_B4_NtB4_5Inner21current_node_full_key0EEs_0B8_ Line | Count | Source | 738 | 118k | let lcd = key.iter().zip(v.iter()).take_while(|(a, b)| a == b).count(); |
_RNCINvNtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculator37diff_inserts_least_common_denominatorINtCs1qmLyiTSqYF_6either6EitherIB1C_ANtNtNtB8_4trie6nibble6Nibblej1_RINtNtCsdZExvAaxgia_5alloc3vec3VecB2c_EEB2H_EINtNtNtNtCsaYZPK01V26L_4core4iter8adapters5chain5ChainINtNtB3v_3map3MapINtNtB3v_7flatten7FlatMapINtNtNtB3z_5slice4iter4IterNtB4_14InProgressNodeEIB3r_INtNtNtB3x_7sources4once4OnceB26_EINtNtB3z_6option8IntoIterB26_EENCNvMs3_B4_NtB4_5Inner21current_node_full_key0ENcNtB1B_4Left0EIB5R_B1B_EEEs_0B8_ Line | Count | Source | 738 | 4 | let lcd = key.iter().zip(v.iter()).take_while(|(a, b)| a == b).count(); |
Unexecuted instantiation: _RNCINvNtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculator37diff_inserts_least_common_denominatorINtCs1qmLyiTSqYF_6either6EitherANtNtNtB8_4trie6nibble6Nibblej1_RINtNtCsdZExvAaxgia_5alloc3vec3VecB28_EEINtNtNtNtCsaYZPK01V26L_4core4iter8adapters7flatten7FlatMapINtNtNtB3q_5slice4iter4IterNtB4_14InProgressNodeEINtNtB3m_5chain5ChainINtNtNtB3o_7sources4once4OnceB1C_EINtNtB3q_6option8IntoIterB1C_EENCNvMs3_B4_NtB4_5Inner21current_node_full_key0EEs_0B8_ Unexecuted instantiation: _RNCINvNtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculator37diff_inserts_least_common_denominatorINtCs1qmLyiTSqYF_6either6EitherIB1D_ANtNtNtB8_4trie6nibble6Nibblej1_RINtNtCsdZExvAaxgia_5alloc3vec3VecB2d_EEB2I_EINtNtNtNtCsaYZPK01V26L_4core4iter8adapters5chain5ChainINtNtB3w_3map3MapINtNtB3w_7flatten7FlatMapINtNtNtB3A_5slice4iter4IterNtB4_14InProgressNodeEIB3s_INtNtNtB3y_7sources4once4OnceB27_EINtNtB3A_6option8IntoIterB27_EENCNvMs3_B4_NtB4_5Inner21current_node_full_key0ENcNtB1C_4Left0EIB5S_B1C_EEEs_0B8_ |
739 | 284k | debug_assert!(lcd >= prefix_nibbles.len()); |
740 | 284k | debug_assert_eq!(&key[..lcd], &v[..lcd]); |
741 | 284k | v.truncate(lcd); |
742 | 284k | Some(v) |
743 | | } |
744 | 333k | None => Some(key), |
745 | | }; |
746 | 11.7k | } |
747 | | } |
748 | | |
749 | 5.89M | (force_recalculate, diff_inserts_lcd) |
750 | 5.89M | } _RINvNtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculator37diff_inserts_least_common_denominatorINtCs1qmLyiTSqYF_6either6EitherANtNtNtB6_4trie6nibble6Nibblej1_RINtNtCsdZExvAaxgia_5alloc3vec3VecB25_EEINtNtNtNtCsaYZPK01V26L_4core4iter8adapters7flatten7FlatMapINtNtNtB3n_5slice4iter4IterNtB2_14InProgressNodeEINtNtB3j_5chain5ChainINtNtNtB3l_7sources4once4OnceB1z_EINtNtB3n_6option8IntoIterB1z_EENCNvMs3_B2_NtB2_5Inner21current_node_full_key0EEB6_ Line | Count | Source | 711 | 5.89M | fn diff_inserts_least_common_denominator( | 712 | 5.89M | diff: &TrieDiff, | 713 | 5.89M | prefix: impl Iterator<Item = impl AsRef<[Nibble]>>, | 714 | 5.89M | ) -> (bool, Option<Vec<Nibble>>) { | 715 | 5.89M | let mut force_recalculate = false; | 716 | 5.89M | let mut diff_inserts_lcd = None::<Vec<Nibble>>; | 717 | 5.89M | | 718 | 5.89M | // TODO: could be optimized? | 719 | 5.89M | let prefix_nibbles = prefix.fold(Vec::new(), |mut a, b| { | 720 | | a.extend_from_slice(b.as_ref()); | 721 | | a | 722 | 5.89M | }); | 723 | 5.89M | let prefix = | 724 | 5.89M | trie::nibbles_to_bytes_suffix_extend(prefix_nibbles.iter().copied()).collect::<Vec<_>>(); | 725 | 5.76M | for (key, inserts_entry) in | 726 | 5.89M | diff.diff_range_ordered::<[u8]>((ops::Bound::Included(&prefix[..]), ops::Bound::Unbounded)) | 727 | | { | 728 | 5.76M | let key = trie::bytes_to_nibbles(key.iter().copied()).collect::<Vec<_>>(); | 729 | 5.76M | if !key.starts_with(&prefix_nibbles) { | 730 | 5.13M | break; | 731 | 629k | } | 732 | 629k | | 733 | 629k | force_recalculate = true; | 734 | 629k | | 735 | 629k | if inserts_entry { | 736 | 617k | diff_inserts_lcd = match diff_inserts_lcd.take() { | 737 | 284k | Some(mut v) => { | 738 | 284k | let lcd = key.iter().zip(v.iter()).take_while(|(a, b)| a == b).count(); | 739 | 284k | debug_assert!(lcd >= prefix_nibbles.len()); | 740 | 284k | debug_assert_eq!(&key[..lcd], &v[..lcd]); | 741 | 284k | v.truncate(lcd); | 742 | 284k | Some(v) | 743 | | } | 744 | 333k | None => Some(key), | 745 | | }; | 746 | 11.7k | } | 747 | | } | 748 | | | 749 | 5.89M | (force_recalculate, diff_inserts_lcd) | 750 | 5.89M | } |
_RINvNtNtCsN16ciHI6Qf_7smoldot8executor20trie_root_calculator37diff_inserts_least_common_denominatorINtCs1qmLyiTSqYF_6either6EitherIB1A_ANtNtNtB6_4trie6nibble6Nibblej1_RINtNtCsdZExvAaxgia_5alloc3vec3VecB2a_EEB2F_EINtNtNtNtCsaYZPK01V26L_4core4iter8adapters5chain5ChainINtNtB3t_3map3MapINtNtB3t_7flatten7FlatMapINtNtNtB3x_5slice4iter4IterNtB2_14InProgressNodeEIB3p_INtNtNtB3v_7sources4once4OnceB24_EINtNtB3x_6option8IntoIterB24_EENCNvMs3_B2_NtB2_5Inner21current_node_full_key0ENcNtB1z_4Left0EIB5P_B1z_EEEB6_ Line | Count | Source | 711 | 42 | fn diff_inserts_least_common_denominator( | 712 | 42 | diff: &TrieDiff, | 713 | 42 | prefix: impl Iterator<Item = impl AsRef<[Nibble]>>, | 714 | 42 | ) -> (bool, Option<Vec<Nibble>>) { | 715 | 42 | let mut force_recalculate = false; | 716 | 42 | let mut diff_inserts_lcd = None::<Vec<Nibble>>; | 717 | 42 | | 718 | 42 | // TODO: could be optimized? | 719 | 42 | let prefix_nibbles = prefix.fold(Vec::new(), |mut a, b| { | 720 | | a.extend_from_slice(b.as_ref()); | 721 | | a | 722 | 42 | }); | 723 | 42 | let prefix = | 724 | 42 | trie::nibbles_to_bytes_suffix_extend(prefix_nibbles.iter().copied()).collect::<Vec<_>>(); | 725 | 57 | for (key, inserts_entry) in | 726 | 42 | diff.diff_range_ordered::<[u8]>((ops::Bound::Included(&prefix[..]), ops::Bound::Unbounded)) | 727 | | { | 728 | 57 | let key = trie::bytes_to_nibbles(key.iter().copied()).collect::<Vec<_>>(); | 729 | 57 | if !key.starts_with(&prefix_nibbles) { | 730 | 22 | break; | 731 | 35 | } | 732 | 35 | | 733 | 35 | force_recalculate = true; | 734 | 35 | | 735 | 35 | if inserts_entry { | 736 | 35 | diff_inserts_lcd = match diff_inserts_lcd.take() { | 737 | 2 | Some(mut v) => { | 738 | 2 | let lcd = key.iter().zip(v.iter()).take_while(|(a, b)| a == b).count(); | 739 | 2 | debug_assert!(lcd >= prefix_nibbles.len()); | 740 | 2 | debug_assert_eq!(&key[..lcd], &v[..lcd]); | 741 | 2 | v.truncate(lcd); | 742 | 2 | Some(v) | 743 | | } | 744 | 33 | None => Some(key), | 745 | | }; | 746 | 0 | } | 747 | | } | 748 | | | 749 | 42 | (force_recalculate, diff_inserts_lcd) | 750 | 42 | } |
Unexecuted instantiation: _RINvNtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculator37diff_inserts_least_common_denominatorINtCs1qmLyiTSqYF_6either6EitherANtNtNtB6_4trie6nibble6Nibblej1_RINtNtCsdZExvAaxgia_5alloc3vec3VecB26_EEINtNtNtNtCsaYZPK01V26L_4core4iter8adapters7flatten7FlatMapINtNtNtB3o_5slice4iter4IterNtB2_14InProgressNodeEINtNtB3k_5chain5ChainINtNtNtB3m_7sources4once4OnceB1A_EINtNtB3o_6option8IntoIterB1A_EENCNvMs3_B2_NtB2_5Inner21current_node_full_key0EEB6_ Unexecuted instantiation: _RINvNtNtCseuYC0Zibziv_7smoldot8executor20trie_root_calculator37diff_inserts_least_common_denominatorINtCs1qmLyiTSqYF_6either6EitherIB1B_ANtNtNtB6_4trie6nibble6Nibblej1_RINtNtCsdZExvAaxgia_5alloc3vec3VecB2b_EEB2G_EINtNtNtNtCsaYZPK01V26L_4core4iter8adapters5chain5ChainINtNtB3u_3map3MapINtNtB3u_7flatten7FlatMapINtNtNtB3y_5slice4iter4IterNtB2_14InProgressNodeEIB3q_INtNtNtB3w_7sources4once4OnceB25_EINtNtB3y_6option8IntoIterB25_EENCNvMs3_B2_NtB2_5Inner21current_node_full_key0ENcNtB1A_4Left0EIB5Q_B1A_EEEB6_ |