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::{
7    DatabaseHashedCursorFactory, DatabaseStateRoot, DatabaseTrieCursorFactory, TrieTableAdapter,
8};
9use alloy_primitives::BlockNumber;
10use reth_storage_api::{
11    BlockNumReader, ChangeSetReader, DBProvider, StorageChangeSetReader, StorageSettingsCache,
12};
13use reth_storage_errors::provider::ProviderError;
14use reth_trie::TrieInputSorted;
15use reth_trie_common::updates::TrieUpdatesSorted;
16use std::{ops::RangeInclusive, sync::Arc};
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>(
29    provider: &Provider,
30    block_number: BlockNumber,
31) -> Result<TrieUpdatesSorted, ProviderError>
32where
33    Provider: DBProvider
34        + ChangeSetReader
35        + StorageChangeSetReader
36        + BlockNumReader
37        + StorageSettingsCache,
38{
39    let db_tip_block = provider.best_block_number()?;
40    crate::with_adapter!(provider, |A| {
41        compute_range_trie_changesets_inner::<_, A>(
42            provider,
43            block_number..=block_number,
44            db_tip_block,
45        )
46    })
47}
48
49/// Computes aggregate trie changesets for an inclusive block range.
50///
51/// The returned changesets restore the trie from the state after `range.end()` to the state before
52/// `range.start()`. `db_tip_block` must be the current database tip for `provider`.
53///
54/// # Errors
55///
56/// Returns an error if the range exceeds `db_tip_block`, database access fails, or state root
57/// computation fails.
58pub fn compute_range_trie_changesets<Provider>(
59    provider: &Provider,
60    range: RangeInclusive<BlockNumber>,
61    db_tip_block: BlockNumber,
62) -> Result<TrieUpdatesSorted, ProviderError>
63where
64    Provider: DBProvider
65        + ChangeSetReader
66        + StorageChangeSetReader
67        + BlockNumReader
68        + StorageSettingsCache,
69{
70    crate::with_adapter!(provider, |A| {
71        compute_range_trie_changesets_inner::<_, A>(provider, range, db_tip_block)
72    })
73}
74
75fn compute_range_trie_changesets_inner<Provider, A>(
76    provider: &Provider,
77    range: RangeInclusive<BlockNumber>,
78    db_tip_block: BlockNumber,
79) -> Result<TrieUpdatesSorted, ProviderError>
80where
81    Provider: DBProvider
82        + ChangeSetReader
83        + StorageChangeSetReader
84        + BlockNumReader
85        + StorageSettingsCache,
86    A: TrieTableAdapter,
87{
88    let start_block = *range.start();
89    let end_block = *range.end();
90
91    if start_block > end_block {
92        return Ok(TrieUpdatesSorted::default())
93    }
94
95    if end_block > db_tip_block {
96        return Err(ProviderError::InsufficientChangesets {
97            requested: end_block,
98            available: 0..=db_tip_block,
99        })
100    }
101
102    debug!(
103        target: "trie::changesets",
104        start_block,
105        end_block,
106        db_tip_block,
107        "Computing range trie changesets from database state"
108    );
109
110    // Collect the state revert for the requested range.
111    let range_state_revert = crate::state::from_reverts_auto(provider, range)?;
112    let range_prefix_sets = range_state_revert.construct_prefix_sets();
113
114    type DbStateRoot<'a, TX, A> = reth_trie::StateRoot<
115        DatabaseTrieCursorFactory<&'a TX, A>,
116        DatabaseHashedCursorFactory<&'a TX>,
117    >;
118
119    let (range_nodes, range_state) = if end_block == db_tip_block {
120        debug!(
121            target: "trie::changesets",
122            start_block,
123            end_block,
124            db_tip_block,
125            "Skipping tail trie revert computation for tip-ended range"
126        );
127
128        (Arc::default(), Arc::new(range_state_revert))
129    } else {
130        // Collect the state revert from the database tip to just after the range.
131        let tail_state_revert = end_block
132            .checked_add(1)
133            .map(|next_block| crate::state::from_reverts_auto(provider, next_block..))
134            .transpose()?
135            .unwrap_or_default();
136
137        // Compute trie reverts from the database tip to just after the range.
138        let tail_input = TrieInputSorted::new(
139            Arc::default(),
140            Arc::new(tail_state_revert.clone()),
141            tail_state_revert.construct_prefix_sets(),
142        );
143        let tail_trie_revert = DbStateRoot::<_, A>::overlay_root_from_nodes_with_updates(
144            provider.tx_ref(),
145            tail_input,
146        )
147        .map_err(ProviderError::other)?
148        .1
149        .into_sorted();
150
151        // Overlay the post-range trie and compute the trie revert to the pre-range state.
152        let mut pre_range_state_revert = tail_state_revert;
153        pre_range_state_revert.extend_ref_and_sort(&range_state_revert);
154
155        (Arc::new(tail_trie_revert), Arc::new(pre_range_state_revert))
156    };
157
158    let range_input = TrieInputSorted::new(range_nodes, range_state, range_prefix_sets);
159    let range_trie_revert =
160        DbStateRoot::<_, A>::overlay_root_from_nodes_with_updates(provider.tx_ref(), range_input)
161            .map_err(ProviderError::other)?
162            .1
163            .into_sorted();
164
165    debug!(
166        target: "trie::changesets",
167        start_block,
168        end_block,
169        num_account_nodes = range_trie_revert.account_nodes_ref().len(),
170        num_storage_tries = range_trie_revert.storage_tries_ref().len(),
171        "Computed range trie changesets successfully"
172    );
173
174    Ok(range_trie_revert)
175}
reth_trie_db/changesets.rs

reth_trie_db/
changesets.rs
