reth_trie_db/
changesets.rs

1//! Database-backed trie changeset computation utilities.
2//!
3//! This module reconstructs trie changesets from database state. The resulting changesets contain
4//! the old trie node values needed to revert a block or contiguous range of blocks.
5
6use crate::DatabaseHashedPostState;
7use alloy_primitives::BlockNumber;
8use reth_storage_api::{BlockNumReader, ChangeSetReader, StorageChangeSetReader};
9use reth_storage_errors::provider::ProviderError;
10use reth_trie::{
11    hashed_cursor::{HashedCursorFactory, HashedPostStateCursorFactory},
12    trie_cursor::{InMemoryTrieCursorFactory, TrieCursorFactory},
13    StateRoot,
14};
15use reth_trie_common::updates::TrieUpdatesSorted;
16use std::ops::RangeInclusive;
17use tracing::debug;
18
19/// Computes trie changesets for a block.
20///
21/// For block `N`, this reconstructs the trie as it existed after `N`, then calculates the trie
22/// updates needed to restore the state before `N`.
23///
24/// # Errors
25///
26/// Returns an error if the block exceeds the database tip, database access fails, or state root
27/// computation fails.
28pub fn compute_block_trie_changesets<Provider, StateTrieProvider>(
29    provider: &Provider,
30    state_trie_provider: &StateTrieProvider,
31    block_number: BlockNumber,
32) -> Result<TrieUpdatesSorted, ProviderError>
33where
34    Provider: ChangeSetReader + StorageChangeSetReader + BlockNumReader,
35    StateTrieProvider: TrieCursorFactory + HashedCursorFactory,
36{
37    let db_tip_block = provider.best_block_number()?;
38    compute_range_trie_changesets(
39        provider,
40        state_trie_provider,
41        block_number..=block_number,
42        db_tip_block,
43    )
44}
45
46/// Computes aggregate trie changesets for an inclusive block range.
47///
48/// The returned changesets restore the trie from the state after `range.end()` to the state before
49/// `range.start()`. `db_tip_block` must be the current database tip for `provider`.
50///
51/// # Errors
52///
53/// Returns an error if the range exceeds `db_tip_block`, database access fails, or state root
54/// computation fails.
55pub fn compute_range_trie_changesets<Provider, StateTrieProvider>(
56    provider: &Provider,
57    state_trie_provider: &StateTrieProvider,
58    range: RangeInclusive<BlockNumber>,
59    db_tip_block: BlockNumber,
60) -> Result<TrieUpdatesSorted, ProviderError>
61where
62    Provider: ChangeSetReader + StorageChangeSetReader + BlockNumReader,
63    StateTrieProvider: TrieCursorFactory + HashedCursorFactory,
64{
65    let start_block = *range.start();
66    let end_block = *range.end();
67
68    if start_block > end_block {
69        return Ok(TrieUpdatesSorted::default())
70    }
71
72    if end_block > db_tip_block {
73        return Err(ProviderError::InsufficientChangesets {
74            requested: end_block,
75            available: 0..=db_tip_block,
76        })
77    }
78
79    debug!(
80        target: "trie::changesets",
81        start_block,
82        end_block,
83        db_tip_block,
84        "Computing range trie changesets from database state"
85    );
86
87    // Collect the state revert for the requested range.
88    let range_state_revert = reth_trie::HashedPostStateSorted::from_reverts(provider, range)?;
89    let range_prefix_sets = range_state_revert.construct_prefix_sets();
90
91    let (range_nodes, range_state) = if end_block == db_tip_block {
92        debug!(
93            target: "trie::changesets",
94            start_block,
95            end_block,
96            db_tip_block,
97            "Skipping tail trie revert computation for tip-ended range"
98        );
99
100        (TrieUpdatesSorted::default(), range_state_revert)
101    } else {
102        // Collect the state revert from the database tip to just after the range.
103        let tail_state_revert = end_block
104            .checked_add(1)
105            .map(|next_block| {
106                reth_trie::HashedPostStateSorted::from_reverts(provider, next_block..)
107            })
108            .transpose()?
109            .unwrap_or_default();
110
111        // Compute trie reverts from the database tip to just after the range.
112        let tail_prefix_sets = tail_state_revert.construct_prefix_sets().freeze();
113        let tail_trie_revert = StateRoot::new(
114            state_trie_provider,
115            HashedPostStateCursorFactory::new(state_trie_provider, &tail_state_revert),
116        )
117        .with_prefix_sets(tail_prefix_sets)
118        .root_with_updates()
119        .map_err(ProviderError::other)?
120        .1
121        .into_sorted();
122
123        // Overlay the post-range trie and compute the trie revert to the pre-range state.
124        let mut pre_range_state_revert = tail_state_revert;
125        pre_range_state_revert.extend_ref_and_sort(&range_state_revert);
126
127        (tail_trie_revert, pre_range_state_revert)
128    };
129
130    let range_trie_revert = StateRoot::new(
131        InMemoryTrieCursorFactory::new(state_trie_provider, &range_nodes),
132        HashedPostStateCursorFactory::new(state_trie_provider, &range_state),
133    )
134    .with_prefix_sets(range_prefix_sets.freeze())
135    .root_with_updates()
136    .map_err(ProviderError::other)?
137    .1
138    .into_sorted();
139
140    debug!(
141        target: "trie::changesets",
142        start_block,
143        end_block,
144        num_account_nodes = range_trie_revert.account_nodes_ref().len(),
145        num_storage_tries = range_trie_revert.storage_tries_ref().len(),
146        "Computed range trie changesets successfully"
147    );
148
149    Ok(range_trie_revert)
150}
reth_trie_db/changesets.rs

reth_trie_db/
changesets.rs
