reth_trie/
trie.rs

1use crate::{
2    hashed_cursor::{HashedCursor, HashedCursorFactory, HashedStorageCursor},
3    node_iter::{TrieElement, TrieNodeIter},
4    prefix_set::{PrefixSet, TriePrefixSets},
5    progress::{
6        IntermediateRootState, IntermediateStateRootState, IntermediateStorageRootState,
7        StateRootProgress, StorageRootProgress,
8    },
9    stats::TrieTracker,
10    trie_cursor::{TrieCursor, TrieCursorFactory},
11    updates::{StorageTrieUpdates, TrieUpdates},
12    walker::TrieWalker,
13    HashBuilder, Nibbles, TRIE_ACCOUNT_RLP_MAX_SIZE,
14};
15use alloy_consensus::EMPTY_ROOT_HASH;
16use alloy_primitives::{keccak256, Address, B256};
17use alloy_rlp::{BufMut, Encodable};
18use alloy_trie::proof::AddedRemovedKeys;
19use reth_execution_errors::{StateRootError, StorageRootError};
20use reth_primitives_traits::Account;
21use tracing::{debug, instrument, trace};
22
23/// The default updates after which root algorithms should return intermediate progress rather than
24/// finishing the computation.
25const DEFAULT_INTERMEDIATE_THRESHOLD: u64 = 100_000;
26
27#[cfg(feature = "metrics")]
28use crate::metrics::{StateRootMetrics, TrieRootMetrics};
29
30/// `StateRoot` is used to compute the root node of a state trie.
31#[derive(Debug)]
32pub struct StateRoot<T, H> {
33    /// The factory for trie cursors.
34    pub trie_cursor_factory: T,
35    /// The factory for hashed cursors.
36    pub hashed_cursor_factory: H,
37    /// A set of prefix sets that have changed.
38    pub prefix_sets: TriePrefixSets,
39    /// Previous intermediate state.
40    previous_state: Option<IntermediateStateRootState>,
41    /// The number of updates after which the intermediate progress should be returned.
42    threshold: u64,
43    #[cfg(feature = "metrics")]
44    /// State root metrics.
45    metrics: StateRootMetrics,
46}
47
48impl<T, H> StateRoot<T, H> {
49    /// Creates [`StateRoot`] with `trie_cursor_factory` and `hashed_cursor_factory`. All other
50    /// parameters are set to reasonable defaults.
51    ///
52    /// The cursors created by given factories are then used to walk through the accounts and
53    /// calculate the state root value with.
54    pub fn new(trie_cursor_factory: T, hashed_cursor_factory: H) -> Self {
55        Self {
56            trie_cursor_factory,
57            hashed_cursor_factory,
58            prefix_sets: TriePrefixSets::default(),
59            previous_state: None,
60            threshold: DEFAULT_INTERMEDIATE_THRESHOLD,
61            #[cfg(feature = "metrics")]
62            metrics: StateRootMetrics::default(),
63        }
64    }
65
66    /// Set the prefix sets.
67    pub fn with_prefix_sets(mut self, prefix_sets: TriePrefixSets) -> Self {
68        self.prefix_sets = prefix_sets;
69        self
70    }
71
72    /// Set the threshold.
73    pub const fn with_threshold(mut self, threshold: u64) -> Self {
74        self.threshold = threshold;
75        self
76    }
77
78    /// Set the threshold to maximum value so that intermediate progress is not returned.
79    pub const fn with_no_threshold(mut self) -> Self {
80        self.threshold = u64::MAX;
81        self
82    }
83
84    /// Set the previously recorded intermediate state.
85    pub fn with_intermediate_state(mut self, state: Option<IntermediateStateRootState>) -> Self {
86        self.previous_state = state;
87        self
88    }
89
90    /// Set the hashed cursor factory.
91    pub fn with_hashed_cursor_factory<HF>(self, hashed_cursor_factory: HF) -> StateRoot<T, HF> {
92        StateRoot {
93            trie_cursor_factory: self.trie_cursor_factory,
94            hashed_cursor_factory,
95            prefix_sets: self.prefix_sets,
96            threshold: self.threshold,
97            previous_state: self.previous_state,
98            #[cfg(feature = "metrics")]
99            metrics: self.metrics,
100        }
101    }
102
103    /// Set the trie cursor factory.
104    pub fn with_trie_cursor_factory<TF>(self, trie_cursor_factory: TF) -> StateRoot<TF, H> {
105        StateRoot {
106            trie_cursor_factory,
107            hashed_cursor_factory: self.hashed_cursor_factory,
108            prefix_sets: self.prefix_sets,
109            threshold: self.threshold,
110            previous_state: self.previous_state,
111            #[cfg(feature = "metrics")]
112            metrics: self.metrics,
113        }
114    }
115}
116
117impl<T, H> StateRoot<T, H>
118where
119    T: TrieCursorFactory + Clone,
120    H: HashedCursorFactory + Clone,
121{
122    /// Walks the intermediate nodes of existing state trie (if any) and hashed entries. Feeds the
123    /// nodes into the hash builder. Collects the updates in the process.
124    ///
125    /// Ignores the threshold.
126    ///
127    /// # Returns
128    ///
129    /// The state root and the trie updates.
130    pub fn root_with_updates(self) -> Result<(B256, TrieUpdates), StateRootError> {
131        match self.with_no_threshold().calculate(true)? {
132            StateRootProgress::Complete(root, _, updates) => Ok((root, updates)),
133            StateRootProgress::Progress(..) => unreachable!(), // unreachable threshold
134        }
135    }
136
137    /// Walks the intermediate nodes of existing state trie (if any) and hashed entries. Feeds the
138    /// nodes into the hash builder.
139    ///
140    /// # Returns
141    ///
142    /// The state root hash.
143    pub fn root(self) -> Result<B256, StateRootError> {
144        match self.calculate(false)? {
145            StateRootProgress::Complete(root, _, _) => Ok(root),
146            StateRootProgress::Progress(..) => unreachable!(), // update retention is disabled
147        }
148    }
149
150    /// Walks the intermediate nodes of existing state trie (if any) and hashed entries. Feeds the
151    /// nodes into the hash builder. Collects the updates in the process.
152    ///
153    /// # Returns
154    ///
155    /// The intermediate progress of state root computation.
156    pub fn root_with_progress(self) -> Result<StateRootProgress, StateRootError> {
157        self.calculate(true)
158    }
159
160    fn calculate(self, retain_updates: bool) -> Result<StateRootProgress, StateRootError> {
161        trace!(target: "trie::state_root", "calculating state root");
162        let mut tracker = TrieTracker::default();
163
164        let trie_cursor = self.trie_cursor_factory.account_trie_cursor()?;
165        let hashed_account_cursor = self.hashed_cursor_factory.hashed_account_cursor()?;
166
167        // create state root context once for reuse
168        let mut storage_ctx = StateRootContext::new();
169
170        // first handle any in-progress storage root calculation
171        let (mut hash_builder, mut account_node_iter) = if let Some(state) = self.previous_state {
172            let IntermediateStateRootState { account_root_state, storage_root_state } = state;
173
174            // resume account trie iteration
175            let mut hash_builder = account_root_state.hash_builder.with_updates(retain_updates);
176            let walker = TrieWalker::<_>::state_trie_from_stack(
177                trie_cursor,
178                account_root_state.walker_stack,
179                self.prefix_sets.account_prefix_set,
180            )
181            .with_deletions_retained(retain_updates);
182            let account_node_iter = TrieNodeIter::state_trie(walker, hashed_account_cursor)
183                .with_last_hashed_key(account_root_state.last_hashed_key);
184
185            // if we have an in-progress storage root, complete it first
186            if let Some(storage_state) = storage_root_state {
187                let hashed_address = account_root_state.last_hashed_key;
188                let account = storage_state.account;
189
190                debug!(
191                    target: "trie::state_root",
192                    account_nonce = account.nonce,
193                    account_balance = ?account.balance,
194                    last_hashed_key = ?account_root_state.last_hashed_key,
195                    "Resuming storage root calculation"
196                );
197
198                // resume the storage root calculation
199                let remaining_threshold = self.threshold.saturating_sub(
200                    storage_ctx.total_updates_len(&account_node_iter, &hash_builder),
201                );
202
203                let storage_root_calculator = StorageRoot::new_hashed(
204                    self.trie_cursor_factory.clone(),
205                    self.hashed_cursor_factory.clone(),
206                    hashed_address,
207                    self.prefix_sets
208                        .storage_prefix_sets
209                        .get(&hashed_address)
210                        .cloned()
211                        .unwrap_or_default(),
212                    #[cfg(feature = "metrics")]
213                    self.metrics.storage_trie.clone(),
214                )
215                .with_intermediate_state(Some(storage_state.state))
216                .with_threshold(remaining_threshold);
217
218                let storage_result = storage_root_calculator.calculate(retain_updates)?;
219                if let Some(storage_state) = storage_ctx.process_storage_root_result(
220                    storage_result,
221                    hashed_address,
222                    account,
223                    &mut hash_builder,
224                    retain_updates,
225                )? {
226                    // still in progress, need to pause again
227                    return Ok(storage_ctx.create_progress_state(
228                        account_node_iter,
229                        hash_builder,
230                        account_root_state.last_hashed_key,
231                        Some(storage_state),
232                    ))
233                }
234            }
235
236            (hash_builder, account_node_iter)
237        } else {
238            // no intermediate state, create new hash builder and node iter for state root
239            // calculation
240            let hash_builder = HashBuilder::default().with_updates(retain_updates);
241            let walker = TrieWalker::state_trie(trie_cursor, self.prefix_sets.account_prefix_set)
242                .with_deletions_retained(retain_updates);
243            let node_iter = TrieNodeIter::state_trie(walker, hashed_account_cursor);
244            (hash_builder, node_iter)
245        };
246
247        while let Some(node) = account_node_iter.try_next()? {
248            match node {
249                TrieElement::Branch(node) => {
250                    tracker.inc_branch();
251                    hash_builder.add_branch(node.key, node.value, node.children_are_in_trie);
252                }
253                TrieElement::Leaf(hashed_address, account) => {
254                    tracker.inc_leaf();
255                    storage_ctx.hashed_entries_walked += 1;
256
257                    // calculate storage root, calculating the remaining threshold so we have
258                    // bounded memory usage even while in the middle of storage root calculation
259                    let remaining_threshold = self.threshold.saturating_sub(
260                        storage_ctx.total_updates_len(&account_node_iter, &hash_builder),
261                    );
262
263                    let storage_root_calculator = StorageRoot::new_hashed(
264                        self.trie_cursor_factory.clone(),
265                        self.hashed_cursor_factory.clone(),
266                        hashed_address,
267                        self.prefix_sets
268                            .storage_prefix_sets
269                            .get(&hashed_address)
270                            .cloned()
271                            .unwrap_or_default(),
272                        #[cfg(feature = "metrics")]
273                        self.metrics.storage_trie.clone(),
274                    )
275                    .with_threshold(remaining_threshold);
276
277                    let storage_result = storage_root_calculator.calculate(retain_updates)?;
278                    if let Some(storage_state) = storage_ctx.process_storage_root_result(
279                        storage_result,
280                        hashed_address,
281                        account,
282                        &mut hash_builder,
283                        retain_updates,
284                    )? {
285                        // storage root hit threshold, need to pause
286                        return Ok(storage_ctx.create_progress_state(
287                            account_node_iter,
288                            hash_builder,
289                            hashed_address,
290                            Some(storage_state),
291                        ))
292                    }
293
294                    // decide if we need to return intermediate progress
295                    let total_updates_len =
296                        storage_ctx.total_updates_len(&account_node_iter, &hash_builder);
297                    if retain_updates && total_updates_len >= self.threshold {
298                        return Ok(storage_ctx.create_progress_state(
299                            account_node_iter,
300                            hash_builder,
301                            hashed_address,
302                            None,
303                        ))
304                    }
305                }
306            }
307        }
308
309        let root = hash_builder.root();
310
311        let removed_keys = account_node_iter.walker.take_removed_keys();
312        let StateRootContext { mut trie_updates, hashed_entries_walked, .. } = storage_ctx;
313        trie_updates.finalize(hash_builder, removed_keys, self.prefix_sets.destroyed_accounts);
314
315        let stats = tracker.finish();
316
317        #[cfg(feature = "metrics")]
318        self.metrics.state_trie.record(stats);
319
320        trace!(
321            target: "trie::state_root",
322            %root,
323            duration = ?stats.duration(),
324            branches_added = stats.branches_added(),
325            leaves_added = stats.leaves_added(),
326            "calculated state root"
327        );
328
329        Ok(StateRootProgress::Complete(root, hashed_entries_walked, trie_updates))
330    }
331}
332
333/// Contains state mutated during state root calculation and storage root result handling.
334#[derive(Debug)]
335pub(crate) struct StateRootContext {
336    /// Reusable buffer for encoding account data.
337    account_rlp: Vec<u8>,
338    /// Accumulates updates from account and storage root calculation.
339    trie_updates: TrieUpdates,
340    /// Tracks total hashed entries walked.
341    hashed_entries_walked: usize,
342    /// Counts storage trie nodes updated.
343    updated_storage_nodes: usize,
344}
345
346impl StateRootContext {
347    /// Creates a new state root context.
348    fn new() -> Self {
349        Self {
350            account_rlp: Vec::with_capacity(TRIE_ACCOUNT_RLP_MAX_SIZE),
351            trie_updates: TrieUpdates::default(),
352            hashed_entries_walked: 0,
353            updated_storage_nodes: 0,
354        }
355    }
356
357    /// Creates a [`StateRootProgress`] when the threshold is hit, from the state of the current
358    /// [`TrieNodeIter`], [`HashBuilder`], last hashed key and any storage root intermediate state.
359    fn create_progress_state<C, H, K>(
360        mut self,
361        account_node_iter: TrieNodeIter<C, H, K>,
362        hash_builder: HashBuilder,
363        last_hashed_key: B256,
364        storage_state: Option<IntermediateStorageRootState>,
365    ) -> StateRootProgress
366    where
367        C: TrieCursor,
368        H: HashedCursor,
369        K: AsRef<AddedRemovedKeys>,
370    {
371        let (walker_stack, walker_deleted_keys) = account_node_iter.walker.split();
372        self.trie_updates.removed_nodes.extend(walker_deleted_keys);
373        let (hash_builder, hash_builder_updates) = hash_builder.split();
374        self.trie_updates.account_nodes.extend(hash_builder_updates);
375
376        let account_state = IntermediateRootState { hash_builder, walker_stack, last_hashed_key };
377
378        let state = IntermediateStateRootState {
379            account_root_state: account_state,
380            storage_root_state: storage_state,
381        };
382
383        StateRootProgress::Progress(Box::new(state), self.hashed_entries_walked, self.trie_updates)
384    }
385
386    /// Calculates the total number of updated nodes.
387    fn total_updates_len<C, H, K>(
388        &self,
389        account_node_iter: &TrieNodeIter<C, H, K>,
390        hash_builder: &HashBuilder,
391    ) -> u64
392    where
393        C: TrieCursor,
394        H: HashedCursor,
395        K: AsRef<AddedRemovedKeys>,
396    {
397        (self.updated_storage_nodes +
398            account_node_iter.walker.removed_keys_len() +
399            hash_builder.updates_len()) as u64
400    }
401
402    /// Processes the result of a storage root calculation.
403    ///
404    /// Handles both completed and in-progress storage root calculations:
405    /// - For completed roots: encodes the account with the storage root, updates the hash builder
406    ///   with the new account, and updates metrics.
407    /// - For in-progress roots: returns the intermediate state for later resumption
408    ///
409    /// Returns an [`IntermediateStorageRootState`] if the calculation needs to be resumed later, or
410    /// `None` if the storage root was successfully computed and added to the trie.
411    fn process_storage_root_result(
412        &mut self,
413        storage_result: StorageRootProgress,
414        hashed_address: B256,
415        account: Account,
416        hash_builder: &mut HashBuilder,
417        retain_updates: bool,
418    ) -> Result<Option<IntermediateStorageRootState>, StateRootError> {
419        match storage_result {
420            StorageRootProgress::Complete(storage_root, storage_slots_walked, updates) => {
421                // Storage root completed
422                self.hashed_entries_walked += storage_slots_walked;
423                if retain_updates {
424                    self.updated_storage_nodes += updates.len();
425                    self.trie_updates.insert_storage_updates(hashed_address, updates);
426                }
427
428                // Encode the account with the computed storage root
429                self.account_rlp.clear();
430                let trie_account = account.into_trie_account(storage_root);
431                trie_account.encode(&mut self.account_rlp as &mut dyn BufMut);
432                hash_builder.add_leaf(Nibbles::unpack(hashed_address), &self.account_rlp);
433                Ok(None)
434            }
435            StorageRootProgress::Progress(state, storage_slots_walked, updates) => {
436                // Storage root hit threshold or resumed calculation hit threshold
437                debug!(
438                    target: "trie::state_root",
439                    ?hashed_address,
440                    storage_slots_walked,
441                    last_storage_key = ?state.last_hashed_key,
442                    ?account,
443                    "Pausing storage root calculation"
444                );
445
446                self.hashed_entries_walked += storage_slots_walked;
447                if retain_updates {
448                    self.trie_updates.insert_storage_updates(hashed_address, updates);
449                }
450
451                Ok(Some(IntermediateStorageRootState { state: *state, account }))
452            }
453        }
454    }
455}
456
457/// `StorageRoot` is used to compute the root node of an account storage trie.
458#[derive(Debug)]
459pub struct StorageRoot<T, H> {
460    /// A reference to the database transaction.
461    pub trie_cursor_factory: T,
462    /// The factory for hashed cursors.
463    pub hashed_cursor_factory: H,
464    /// The hashed address of an account.
465    pub hashed_address: B256,
466    /// The set of storage slot prefixes that have changed.
467    pub prefix_set: PrefixSet,
468    /// Previous intermediate state.
469    previous_state: Option<IntermediateRootState>,
470    /// The number of updates after which the intermediate progress should be returned.
471    threshold: u64,
472    /// Storage root metrics.
473    #[cfg(feature = "metrics")]
474    metrics: TrieRootMetrics,
475}
476
477impl<T, H> StorageRoot<T, H> {
478    /// Creates a new storage root calculator given a raw address.
479    pub fn new(
480        trie_cursor_factory: T,
481        hashed_cursor_factory: H,
482        address: Address,
483        prefix_set: PrefixSet,
484        #[cfg(feature = "metrics")] metrics: TrieRootMetrics,
485    ) -> Self {
486        Self::new_hashed(
487            trie_cursor_factory,
488            hashed_cursor_factory,
489            keccak256(address),
490            prefix_set,
491            #[cfg(feature = "metrics")]
492            metrics,
493        )
494    }
495
496    /// Creates a new storage root calculator given a hashed address.
497    pub const fn new_hashed(
498        trie_cursor_factory: T,
499        hashed_cursor_factory: H,
500        hashed_address: B256,
501        prefix_set: PrefixSet,
502        #[cfg(feature = "metrics")] metrics: TrieRootMetrics,
503    ) -> Self {
504        Self {
505            trie_cursor_factory,
506            hashed_cursor_factory,
507            hashed_address,
508            prefix_set,
509            previous_state: None,
510            threshold: DEFAULT_INTERMEDIATE_THRESHOLD,
511            #[cfg(feature = "metrics")]
512            metrics,
513        }
514    }
515
516    /// Set the changed prefixes.
517    pub fn with_prefix_set(mut self, prefix_set: PrefixSet) -> Self {
518        self.prefix_set = prefix_set;
519        self
520    }
521
522    /// Set the threshold.
523    pub const fn with_threshold(mut self, threshold: u64) -> Self {
524        self.threshold = threshold;
525        self
526    }
527
528    /// Set the threshold to maximum value so that intermediate progress is not returned.
529    pub const fn with_no_threshold(mut self) -> Self {
530        self.threshold = u64::MAX;
531        self
532    }
533
534    /// Set the previously recorded intermediate state.
535    pub fn with_intermediate_state(mut self, state: Option<IntermediateRootState>) -> Self {
536        self.previous_state = state;
537        self
538    }
539
540    /// Set the hashed cursor factory.
541    pub fn with_hashed_cursor_factory<HF>(self, hashed_cursor_factory: HF) -> StorageRoot<T, HF> {
542        StorageRoot {
543            trie_cursor_factory: self.trie_cursor_factory,
544            hashed_cursor_factory,
545            hashed_address: self.hashed_address,
546            prefix_set: self.prefix_set,
547            previous_state: self.previous_state,
548            threshold: self.threshold,
549            #[cfg(feature = "metrics")]
550            metrics: self.metrics,
551        }
552    }
553
554    /// Set the trie cursor factory.
555    pub fn with_trie_cursor_factory<TF>(self, trie_cursor_factory: TF) -> StorageRoot<TF, H> {
556        StorageRoot {
557            trie_cursor_factory,
558            hashed_cursor_factory: self.hashed_cursor_factory,
559            hashed_address: self.hashed_address,
560            prefix_set: self.prefix_set,
561            previous_state: self.previous_state,
562            threshold: self.threshold,
563            #[cfg(feature = "metrics")]
564            metrics: self.metrics,
565        }
566    }
567}
568
569impl<T, H> StorageRoot<T, H>
570where
571    T: TrieCursorFactory,
572    H: HashedCursorFactory,
573{
574    /// Walks the intermediate nodes of existing storage trie (if any) and hashed entries. Feeds the
575    /// nodes into the hash builder. Collects the updates in the process.
576    ///
577    /// # Returns
578    ///
579    /// The intermediate progress of state root computation.
580    pub fn root_with_progress(self) -> Result<StorageRootProgress, StorageRootError> {
581        self.calculate(true)
582    }
583
584    /// Walks the hashed storage table entries for a given address and calculates the storage root.
585    ///
586    /// # Returns
587    ///
588    /// The storage root and storage trie updates for a given address.
589    pub fn root_with_updates(self) -> Result<(B256, usize, StorageTrieUpdates), StorageRootError> {
590        match self.with_no_threshold().calculate(true)? {
591            StorageRootProgress::Complete(root, walked, updates) => Ok((root, walked, updates)),
592            StorageRootProgress::Progress(..) => unreachable!(), // unreachable threshold
593        }
594    }
595
596    /// Walks the hashed storage table entries for a given address and calculates the storage root.
597    ///
598    /// # Returns
599    ///
600    /// The storage root.
601    pub fn root(self) -> Result<B256, StorageRootError> {
602        match self.calculate(false)? {
603            StorageRootProgress::Complete(root, _, _) => Ok(root),
604            StorageRootProgress::Progress(..) => unreachable!(), // update retenion is disabled
605        }
606    }
607
608    /// Walks the hashed storage table entries for a given address and calculates the storage root.
609    ///
610    /// # Returns
611    ///
612    /// The storage root, number of walked entries and trie updates
613    /// for a given address if requested.
614    #[instrument(skip_all, target = "trie::storage_root", name = "Storage trie", fields(hashed_address = ?self.hashed_address))]
615    pub fn calculate(self, retain_updates: bool) -> Result<StorageRootProgress, StorageRootError> {
616        trace!(target: "trie::storage_root", "calculating storage root");
617
618        let mut hashed_storage_cursor =
619            self.hashed_cursor_factory.hashed_storage_cursor(self.hashed_address)?;
620
621        // short circuit on empty storage
622        if hashed_storage_cursor.is_storage_empty()? {
623            return Ok(StorageRootProgress::Complete(
624                EMPTY_ROOT_HASH,
625                0,
626                StorageTrieUpdates::deleted(),
627            ))
628        }
629
630        let mut tracker = TrieTracker::default();
631        let mut trie_updates = StorageTrieUpdates::default();
632
633        let trie_cursor = self.trie_cursor_factory.storage_trie_cursor(self.hashed_address)?;
634
635        let (mut hash_builder, mut storage_node_iter) = match self.previous_state {
636            Some(state) => {
637                let hash_builder = state.hash_builder.with_updates(retain_updates);
638                let walker = TrieWalker::<_>::storage_trie_from_stack(
639                    trie_cursor,
640                    state.walker_stack,
641                    self.prefix_set,
642                )
643                .with_deletions_retained(retain_updates);
644                let node_iter = TrieNodeIter::storage_trie(walker, hashed_storage_cursor)
645                    .with_last_hashed_key(state.last_hashed_key);
646                (hash_builder, node_iter)
647            }
648            None => {
649                let hash_builder = HashBuilder::default().with_updates(retain_updates);
650                let walker = TrieWalker::storage_trie(trie_cursor, self.prefix_set)
651                    .with_deletions_retained(retain_updates);
652                let node_iter = TrieNodeIter::storage_trie(walker, hashed_storage_cursor);
653                (hash_builder, node_iter)
654            }
655        };
656
657        let mut hashed_entries_walked = 0;
658        while let Some(node) = storage_node_iter.try_next()? {
659            match node {
660                TrieElement::Branch(node) => {
661                    tracker.inc_branch();
662                    hash_builder.add_branch(node.key, node.value, node.children_are_in_trie);
663                }
664                TrieElement::Leaf(hashed_slot, value) => {
665                    tracker.inc_leaf();
666                    hashed_entries_walked += 1;
667                    hash_builder.add_leaf(
668                        Nibbles::unpack(hashed_slot),
669                        alloy_rlp::encode_fixed_size(&value).as_ref(),
670                    );
671
672                    // Check if we need to return intermediate progress
673                    let total_updates_len =
674                        storage_node_iter.walker.removed_keys_len() + hash_builder.updates_len();
675                    if retain_updates && total_updates_len as u64 >= self.threshold {
676                        let (walker_stack, walker_deleted_keys) = storage_node_iter.walker.split();
677                        trie_updates.removed_nodes.extend(walker_deleted_keys);
678                        let (hash_builder, hash_builder_updates) = hash_builder.split();
679                        trie_updates.storage_nodes.extend(hash_builder_updates);
680
681                        let state = IntermediateRootState {
682                            hash_builder,
683                            walker_stack,
684                            last_hashed_key: hashed_slot,
685                        };
686
687                        return Ok(StorageRootProgress::Progress(
688                            Box::new(state),
689                            hashed_entries_walked,
690                            trie_updates,
691                        ))
692                    }
693                }
694            }
695        }
696
697        let root = hash_builder.root();
698
699        let removed_keys = storage_node_iter.walker.take_removed_keys();
700        trie_updates.finalize(hash_builder, removed_keys);
701
702        let stats = tracker.finish();
703
704        #[cfg(feature = "metrics")]
705        self.metrics.record(stats);
706
707        trace!(
708            target: "trie::storage_root",
709            %root,
710            hashed_address = %self.hashed_address,
711            duration = ?stats.duration(),
712            branches_added = stats.branches_added(),
713            leaves_added = stats.leaves_added(),
714            "calculated storage root"
715        );
716
717        let storage_slots_walked = stats.leaves_added() as usize;
718        Ok(StorageRootProgress::Complete(root, storage_slots_walked, trie_updates))
719    }
720}
721
722/// Trie type for differentiating between various trie calculations.
723#[derive(Clone, Copy, Debug)]
724pub enum TrieType {
725    /// State trie type.
726    State,
727    /// Storage trie type.
728    Storage,
729}
730
731impl TrieType {
732    #[cfg(feature = "metrics")]
733    pub(crate) const fn as_str(&self) -> &'static str {
734        match self {
735            Self::State => "state",
736            Self::Storage => "storage",
737        }
738    }
739}