reth_trie_common/
ordered_root.rs

1//! Incremental ordered trie root computation.
2//!
3//! This module provides builders for computing ordered trie roots incrementally as items
4//! arrive, rather than requiring all items upfront. This is useful for receipt root
5//! calculation during block execution, where we know the total count but receive receipts
6//! one by one as transactions are executed.
7
8use crate::{HashBuilder, Nibbles, EMPTY_ROOT_HASH};
9use alloc::vec::Vec;
10use alloy_primitives::B256;
11use alloy_trie::root::adjust_index_for_rlp;
12use core::fmt;
13
14/// Error returned when using [`OrderedTrieRootEncodedBuilder`].
15#[derive(Debug, Clone, Copy, PartialEq, Eq)]
16pub enum OrderedRootError {
17    /// Called `finalize()` before all items were pushed.
18    Incomplete {
19        /// The expected number of items.
20        expected: usize,
21        /// The number of items received.
22        received: usize,
23    },
24    /// Index is out of bounds.
25    IndexOutOfBounds {
26        /// The index that was provided.
27        index: usize,
28        /// The expected length.
29        len: usize,
30    },
31    /// Item at this index was already pushed.
32    DuplicateIndex {
33        /// The duplicate index.
34        index: usize,
35    },
36}
37
38impl OrderedRootError {
39    /// Returns `true` if the error is [`OrderedRootError::Incomplete`].
40    #[inline]
41    pub const fn is_incomplete(&self) -> bool {
42        matches!(self, Self::Incomplete { .. })
43    }
44
45    /// Returns `true` if the error is [`OrderedRootError::IndexOutOfBounds`].
46    #[inline]
47    pub const fn is_index_out_of_bounds(&self) -> bool {
48        matches!(self, Self::IndexOutOfBounds { .. })
49    }
50
51    /// Returns `true` if the error is [`OrderedRootError::DuplicateIndex`].
52    #[inline]
53    pub const fn is_duplicate_index(&self) -> bool {
54        matches!(self, Self::DuplicateIndex { .. })
55    }
56
57    /// Returns the index associated with the error, if any.
58    #[inline]
59    pub const fn index(&self) -> Option<usize> {
60        match self {
61            Self::Incomplete { .. } => None,
62            Self::IndexOutOfBounds { index, .. } | Self::DuplicateIndex { index } => Some(*index),
63        }
64    }
65}
66
67impl fmt::Display for OrderedRootError {
68    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
69        match self {
70            Self::Incomplete { expected, received } => {
71                write!(f, "incomplete: expected {expected} items, received {received}")
72            }
73            Self::IndexOutOfBounds { index, len } => {
74                write!(f, "index {index} out of bounds for length {len}")
75            }
76            Self::DuplicateIndex { index } => {
77                write!(f, "duplicate item at index {index}")
78            }
79        }
80    }
81}
82
83#[cfg(feature = "std")]
84impl std::error::Error for OrderedRootError {}
85
86/// A builder for computing ordered trie roots incrementally from pre-encoded items.
87///
88/// This builder allows pushing items one by one as they become available
89/// (e.g., receipts after each transaction execution), rather than requiring
90/// all items upfront.
91///
92/// # Use Case
93///
94/// When executing a block, the receipt root must be computed from all transaction
95/// receipts. With the standard `ordered_trie_root`, you must wait until all
96/// transactions are executed before computing the root. This builder enables
97/// **incremental computation** - you can start building the trie as soon as
98/// receipts become available, potentially in parallel with continued execution.
99///
100/// The builder requires knowing the total item count upfront (the number of
101/// transactions in the block), but items can be pushed in any order by index.
102///
103/// # How It Works
104///
105/// Items can be pushed in any order by specifying their index. The builder
106/// internally buffers items and flushes them to the underlying [`HashBuilder`]
107/// in the correct order for RLP key encoding (as determined by [`adjust_index_for_rlp`]).
108///
109/// # Memory
110///
111/// Each pushed item is stored in an internal buffer until it can be flushed.
112/// In the worst case (e.g., pushing index 0 last), all items except one will
113/// be buffered. For receipt roots, index 0 is typically flushed late due to
114/// RLP key ordering, so expect to buffer most items until near the end.
115///
116/// # Example
117///
118/// ```
119/// use reth_trie_common::ordered_root::OrderedTrieRootEncodedBuilder;
120///
121/// // Create a builder for 2 pre-encoded items
122/// let mut builder = OrderedTrieRootEncodedBuilder::new(2);
123///
124/// // Push pre-encoded items as they arrive (can be out of order)
125/// builder.push(1, b"encoded_item_1").unwrap();
126/// builder.push(0, b"encoded_item_0").unwrap();
127///
128/// // Finalize to get the root hash
129/// let root = builder.finalize().unwrap();
130/// ```
131#[derive(Debug)]
132pub struct OrderedTrieRootEncodedBuilder {
133    /// Total expected number of items.
134    len: usize,
135    /// Number of items received so far.
136    received: usize,
137    /// Next insertion loop counter (determines which adjusted index to flush next).
138    next_insert_i: usize,
139    /// Buffer for pending items, indexed by execution index.
140    pending: Vec<Option<Vec<u8>>>,
141    /// The underlying hash builder.
142    hb: HashBuilder,
143}
144
145impl OrderedTrieRootEncodedBuilder {
146    /// Creates a new builder for `len` pre-encoded items.
147    pub fn new(len: usize) -> Self {
148        Self {
149            len,
150            received: 0,
151            next_insert_i: 0,
152            pending: alloc::vec![None; len],
153            hb: HashBuilder::default(),
154        }
155    }
156
157    /// Pushes a pre-encoded item at the given index to the builder.
158    ///
159    /// Items can be pushed in any order. The builder will automatically
160    /// flush items to the underlying [`HashBuilder`] when they become
161    /// available in the correct order.
162    ///
163    /// # Errors
164    ///
165    /// - [`OrderedRootError::IndexOutOfBounds`] if `index >= len`
166    /// - [`OrderedRootError::DuplicateIndex`] if an item was already pushed at this index
167    #[inline]
168    pub fn push(&mut self, index: usize, bytes: &[u8]) -> Result<(), OrderedRootError> {
169        if index >= self.len {
170            return Err(OrderedRootError::IndexOutOfBounds { index, len: self.len });
171        }
172
173        if self.pending[index].is_some() {
174            return Err(OrderedRootError::DuplicateIndex { index });
175        }
176
177        self.push_unchecked(index, bytes);
178        Ok(())
179    }
180
181    /// Pushes a pre-encoded item at the given index without bounds or duplicate checking.
182    ///
183    /// This is a performance-critical method for callers that can guarantee:
184    /// - `index < len`
185    /// - No item has been pushed at this index before
186    ///
187    /// # Panics
188    ///
189    /// Panics in debug mode if `index >= len`.
190    #[inline]
191    pub fn push_unchecked(&mut self, index: usize, bytes: &[u8]) {
192        debug_assert!(index < self.len, "index {index} out of bounds for length {}", self.len);
193        debug_assert!(self.pending[index].is_none(), "duplicate item at index {index}");
194
195        self.pending[index] = Some(bytes.to_vec());
196        self.received += 1;
197
198        self.flush();
199    }
200
201    /// Attempts to flush pending items to the hash builder.
202    fn flush(&mut self) {
203        while self.next_insert_i < self.len {
204            let exec_index_needed = adjust_index_for_rlp(self.next_insert_i, self.len);
205
206            let Some(value) = self.pending[exec_index_needed].take() else {
207                break;
208            };
209
210            let index_buffer = alloy_rlp::encode_fixed_size(&exec_index_needed);
211            self.hb.add_leaf(Nibbles::unpack(&index_buffer), &value);
212
213            self.next_insert_i += 1;
214        }
215    }
216
217    /// Returns `true` if all items have been pushed.
218    #[inline]
219    pub const fn is_complete(&self) -> bool {
220        self.received == self.len
221    }
222
223    /// Returns the number of items pushed so far.
224    #[inline]
225    pub const fn pushed_count(&self) -> usize {
226        self.received
227    }
228
229    /// Returns the expected total number of items.
230    #[inline]
231    pub const fn expected_count(&self) -> usize {
232        self.len
233    }
234
235    /// Finalizes the builder and returns the trie root.
236    ///
237    /// # Errors
238    ///
239    /// Returns [`OrderedRootError::Incomplete`] if not all items have been pushed.
240    pub fn finalize(mut self) -> Result<B256, OrderedRootError> {
241        if self.len == 0 {
242            return Ok(EMPTY_ROOT_HASH);
243        }
244
245        if self.received != self.len {
246            return Err(OrderedRootError::Incomplete {
247                expected: self.len,
248                received: self.received,
249            });
250        }
251
252        debug_assert_eq!(self.next_insert_i, self.len, "not all items were flushed");
253
254        Ok(self.hb.root())
255    }
256}
257
258#[cfg(test)]
259mod tests {
260    use super::*;
261    use alloy_trie::root::ordered_trie_root_encoded;
262
263    #[test]
264    fn test_ordered_encoded_builder_equivalence() {
265        for len in [0, 1, 2, 3, 10, 127, 128, 129, 130, 200] {
266            let items: Vec<Vec<u8>> =
267                (0..len).map(|i| format!("item_{i}_data").into_bytes()).collect();
268
269            let expected = ordered_trie_root_encoded(&items);
270
271            let mut builder = OrderedTrieRootEncodedBuilder::new(len);
272
273            for (i, item) in items.iter().enumerate() {
274                builder.push(i, item).unwrap();
275            }
276
277            let actual = builder.finalize().unwrap();
278            assert_eq!(
279                expected, actual,
280                "mismatch for len={len}: expected {expected:?}, got {actual:?}"
281            );
282        }
283    }
284
285    #[test]
286    fn test_ordered_builder_out_of_order() {
287        for len in [2, 3, 5, 10, 50] {
288            let items: Vec<Vec<u8>> =
289                (0..len).map(|i| format!("item_{i}_data").into_bytes()).collect();
290
291            let expected = ordered_trie_root_encoded(&items);
292
293            // Push in reverse order
294            let mut builder = OrderedTrieRootEncodedBuilder::new(len);
295            for i in (0..len).rev() {
296                builder.push(i, &items[i]).unwrap();
297            }
298            let actual = builder.finalize().unwrap();
299            assert_eq!(expected, actual, "mismatch for reverse order len={len}");
300
301            // Push odds first, then evens
302            let mut builder = OrderedTrieRootEncodedBuilder::new(len);
303            for i in (1..len).step_by(2) {
304                builder.push(i, &items[i]).unwrap();
305            }
306            for i in (0..len).step_by(2) {
307                builder.push(i, &items[i]).unwrap();
308            }
309            let actual = builder.finalize().unwrap();
310            assert_eq!(expected, actual, "mismatch for odd/even order len={len}");
311        }
312    }
313
314    #[test]
315    fn test_ordered_builder_empty() {
316        let builder = OrderedTrieRootEncodedBuilder::new(0);
317        assert!(builder.is_complete());
318        assert_eq!(builder.finalize().unwrap(), EMPTY_ROOT_HASH);
319    }
320
321    #[test]
322    fn test_ordered_builder_incomplete_error() {
323        let mut builder = OrderedTrieRootEncodedBuilder::new(3);
324
325        builder.push(0, b"item_0").unwrap();
326        builder.push(1, b"item_1").unwrap();
327
328        assert!(!builder.is_complete());
329        assert_eq!(
330            builder.finalize(),
331            Err(OrderedRootError::Incomplete { expected: 3, received: 2 })
332        );
333    }
334
335    #[test]
336    fn test_ordered_builder_index_errors() {
337        let mut builder = OrderedTrieRootEncodedBuilder::new(2);
338
339        assert_eq!(
340            builder.push(5, b"item"),
341            Err(OrderedRootError::IndexOutOfBounds { index: 5, len: 2 })
342        );
343
344        builder.push(0, b"item_0").unwrap();
345
346        assert_eq!(
347            builder.push(0, b"item_0_dup"),
348            Err(OrderedRootError::DuplicateIndex { index: 0 })
349        );
350
351        builder.push(1, b"item_1").unwrap();
352        assert!(builder.is_complete());
353    }
354}
reth_trie_common/ordered_root.rs

reth_trie_common/
ordered_root.rs
