reth_trie/hashed_cursor/
post_state.rs

1use super::{HashedCursor, HashedCursorFactory, HashedStorageCursor};
2use crate::forward_cursor::ForwardInMemoryCursor;
3use alloy_primitives::{map::B256Set, B256, U256};
4use reth_primitives_traits::Account;
5use reth_storage_errors::db::DatabaseError;
6use reth_trie_common::{HashedAccountsSorted, HashedPostStateSorted, HashedStorageSorted};
7
8/// The hashed cursor factory for the post state.
9#[derive(Clone, Debug)]
10pub struct HashedPostStateCursorFactory<CF, T> {
11    cursor_factory: CF,
12    post_state: T,
13}
14
15impl<CF, T> HashedPostStateCursorFactory<CF, T> {
16    /// Create a new factory.
17    pub const fn new(cursor_factory: CF, post_state: T) -> Self {
18        Self { cursor_factory, post_state }
19    }
20}
21
22impl<'a, CF, T> HashedCursorFactory for HashedPostStateCursorFactory<CF, &'a T>
23where
24    CF: HashedCursorFactory,
25    T: AsRef<HashedPostStateSorted>,
26{
27    type AccountCursor = HashedPostStateAccountCursor<'a, CF::AccountCursor>;
28    type StorageCursor = HashedPostStateStorageCursor<'a, CF::StorageCursor>;
29
30    fn hashed_account_cursor(&self) -> Result<Self::AccountCursor, DatabaseError> {
31        let cursor = self.cursor_factory.hashed_account_cursor()?;
32        Ok(HashedPostStateAccountCursor::new(cursor, &self.post_state.as_ref().accounts))
33    }
34
35    fn hashed_storage_cursor(
36        &self,
37        hashed_address: B256,
38    ) -> Result<Self::StorageCursor, DatabaseError> {
39        let cursor = self.cursor_factory.hashed_storage_cursor(hashed_address)?;
40        Ok(HashedPostStateStorageCursor::new(
41            cursor,
42            self.post_state.as_ref().storages.get(&hashed_address),
43        ))
44    }
45}
46
47/// The cursor to iterate over post state hashed accounts and corresponding database entries.
48/// It will always give precedence to the data from the hashed post state.
49#[derive(Debug)]
50pub struct HashedPostStateAccountCursor<'a, C> {
51    /// The database cursor.
52    cursor: C,
53    /// Forward-only in-memory cursor over accounts.
54    post_state_cursor: ForwardInMemoryCursor<'a, B256, Account>,
55    /// Reference to the collection of account keys that were destroyed.
56    destroyed_accounts: &'a B256Set,
57    /// The last hashed account that was returned by the cursor.
58    /// De facto, this is a current cursor position.
59    last_account: Option<B256>,
60}
61
62impl<'a, C> HashedPostStateAccountCursor<'a, C>
63where
64    C: HashedCursor<Value = Account>,
65{
66    /// Create new instance of [`HashedPostStateAccountCursor`].
67    pub fn new(cursor: C, post_state_accounts: &'a HashedAccountsSorted) -> Self {
68        let post_state_cursor = ForwardInMemoryCursor::new(&post_state_accounts.accounts);
69        let destroyed_accounts = &post_state_accounts.destroyed_accounts;
70        Self { cursor, post_state_cursor, destroyed_accounts, last_account: None }
71    }
72
73    /// Returns `true` if the account has been destroyed.
74    /// This check is used for evicting account keys from the state trie.
75    ///
76    /// This function only checks the post state, not the database, because the latter does not
77    /// store destroyed accounts.
78    fn is_account_cleared(&self, account: &B256) -> bool {
79        self.destroyed_accounts.contains(account)
80    }
81
82    fn seek_inner(&mut self, key: B256) -> Result<Option<(B256, Account)>, DatabaseError> {
83        // Take the next account from the post state with the key greater than or equal to the
84        // sought key.
85        let post_state_entry = self.post_state_cursor.seek(&key);
86
87        // It's an exact match, return the account from post state without looking up in the
88        // database.
89        if post_state_entry.is_some_and(|entry| entry.0 == key) {
90            return Ok(post_state_entry)
91        }
92
93        // It's not an exact match, reposition to the first greater or equal account that wasn't
94        // cleared.
95        let mut db_entry = self.cursor.seek(key)?;
96        while db_entry.as_ref().is_some_and(|(address, _)| self.is_account_cleared(address)) {
97            db_entry = self.cursor.next()?;
98        }
99
100        // Compare two entries and return the lowest.
101        Ok(Self::compare_entries(post_state_entry, db_entry))
102    }
103
104    fn next_inner(&mut self, last_account: B256) -> Result<Option<(B256, Account)>, DatabaseError> {
105        // Take the next account from the post state with the key greater than the last sought key.
106        let post_state_entry = self.post_state_cursor.first_after(&last_account);
107
108        // If post state was given precedence or account was cleared, move the cursor forward.
109        let mut db_entry = self.cursor.seek(last_account)?;
110        while db_entry.as_ref().is_some_and(|(address, _)| {
111            address <= &last_account || self.is_account_cleared(address)
112        }) {
113            db_entry = self.cursor.next()?;
114        }
115
116        // Compare two entries and return the lowest.
117        Ok(Self::compare_entries(post_state_entry, db_entry))
118    }
119
120    /// Return the account with the lowest hashed account key.
121    ///
122    /// Given the next post state and database entries, return the smallest of the two.
123    /// If the account keys are the same, the post state entry is given precedence.
124    fn compare_entries(
125        post_state_item: Option<(B256, Account)>,
126        db_item: Option<(B256, Account)>,
127    ) -> Option<(B256, Account)> {
128        if let Some((post_state_entry, db_entry)) = post_state_item.zip(db_item) {
129            // If both are not empty, return the smallest of the two
130            // Post state is given precedence if keys are equal
131            Some(if post_state_entry.0 <= db_entry.0 { post_state_entry } else { db_entry })
132        } else {
133            // Return either non-empty entry
134            db_item.or(post_state_item)
135        }
136    }
137}
138
139impl<C> HashedCursor for HashedPostStateAccountCursor<'_, C>
140where
141    C: HashedCursor<Value = Account>,
142{
143    type Value = Account;
144
145    /// Seek the next entry for a given hashed account key.
146    ///
147    /// If the post state contains the exact match for the key, return it.
148    /// Otherwise, retrieve the next entries that are greater than or equal to the key from the
149    /// database and the post state. The two entries are compared and the lowest is returned.
150    ///
151    /// The returned account key is memoized and the cursor remains positioned at that key until
152    /// [`HashedCursor::seek`] or [`HashedCursor::next`] are called.
153    fn seek(&mut self, key: B256) -> Result<Option<(B256, Self::Value)>, DatabaseError> {
154        // Find the closes account.
155        let entry = self.seek_inner(key)?;
156        self.last_account = entry.as_ref().map(|entry| entry.0);
157        Ok(entry)
158    }
159
160    /// Retrieve the next entry from the cursor.
161    ///
162    /// If the cursor is positioned at the entry, return the entry with next greater key.
163    /// Returns [None] if the previous memoized or the next greater entries are missing.
164    ///
165    /// NOTE: This function will not return any entry unless [`HashedCursor::seek`] has been
166    /// called.
167    fn next(&mut self) -> Result<Option<(B256, Self::Value)>, DatabaseError> {
168        let next = match self.last_account {
169            Some(account) => {
170                let entry = self.next_inner(account)?;
171                self.last_account = entry.as_ref().map(|entry| entry.0);
172                entry
173            }
174            // no previous entry was found
175            None => None,
176        };
177        Ok(next)
178    }
179}
180
181/// The cursor to iterate over post state hashed storages and corresponding database entries.
182/// It will always give precedence to the data from the post state.
183#[derive(Debug)]
184pub struct HashedPostStateStorageCursor<'a, C> {
185    /// The database cursor.
186    cursor: C,
187    /// Forward-only in-memory cursor over non zero-valued account storage slots.
188    post_state_cursor: Option<ForwardInMemoryCursor<'a, B256, U256>>,
189    /// Reference to the collection of storage slot keys that were cleared.
190    cleared_slots: Option<&'a B256Set>,
191    /// Flag indicating whether database storage was wiped.
192    storage_wiped: bool,
193    /// The last slot that has been returned by the cursor.
194    /// De facto, this is the cursor's position for the given account key.
195    last_slot: Option<B256>,
196}
197
198impl<'a, C> HashedPostStateStorageCursor<'a, C>
199where
200    C: HashedStorageCursor<Value = U256>,
201{
202    /// Create new instance of [`HashedPostStateStorageCursor`] for the given hashed address.
203    pub fn new(cursor: C, post_state_storage: Option<&'a HashedStorageSorted>) -> Self {
204        let post_state_cursor =
205            post_state_storage.map(|s| ForwardInMemoryCursor::new(&s.non_zero_valued_slots));
206        let cleared_slots = post_state_storage.map(|s| &s.zero_valued_slots);
207        let storage_wiped = post_state_storage.is_some_and(|s| s.wiped);
208        Self { cursor, post_state_cursor, cleared_slots, storage_wiped, last_slot: None }
209    }
210
211    /// Check if the slot was zeroed out in the post state.
212    /// The database is not checked since it already has no zero-valued slots.
213    fn is_slot_zero_valued(&self, slot: &B256) -> bool {
214        self.cleared_slots.is_some_and(|s| s.contains(slot))
215    }
216
217    /// Find the storage entry in post state or database that's greater or equal to provided subkey.
218    fn seek_inner(&mut self, subkey: B256) -> Result<Option<(B256, U256)>, DatabaseError> {
219        // Attempt to find the account's storage in post state.
220        let post_state_entry = self.post_state_cursor.as_mut().and_then(|c| c.seek(&subkey));
221
222        // If database storage was wiped or it's an exact match,
223        // return the storage slot from post state without looking up in the database.
224        if self.storage_wiped || post_state_entry.is_some_and(|entry| entry.0 == subkey) {
225            return Ok(post_state_entry)
226        }
227
228        // It's not an exact match and storage was not wiped,
229        // reposition to the first greater or equal account.
230        let mut db_entry = self.cursor.seek(subkey)?;
231        while db_entry.as_ref().is_some_and(|entry| self.is_slot_zero_valued(&entry.0)) {
232            db_entry = self.cursor.next()?;
233        }
234
235        // Compare two entries and return the lowest.
236        Ok(Self::compare_entries(post_state_entry, db_entry))
237    }
238
239    /// Find the storage entry that is right after current cursor position.
240    fn next_inner(&mut self, last_slot: B256) -> Result<Option<(B256, U256)>, DatabaseError> {
241        // Attempt to find the account's storage in post state.
242        let post_state_entry =
243            self.post_state_cursor.as_mut().and_then(|c| c.first_after(&last_slot));
244
245        // Return post state entry immediately if database was wiped.
246        if self.storage_wiped {
247            return Ok(post_state_entry)
248        }
249
250        // If post state was given precedence, move the cursor forward.
251        // If the entry was already returned or is zero-valued, move to the next.
252        let mut db_entry = self.cursor.seek(last_slot)?;
253        while db_entry
254            .as_ref()
255            .is_some_and(|entry| entry.0 == last_slot || self.is_slot_zero_valued(&entry.0))
256        {
257            db_entry = self.cursor.next()?;
258        }
259
260        // Compare two entries and return the lowest.
261        Ok(Self::compare_entries(post_state_entry, db_entry))
262    }
263
264    /// Return the storage entry with the lowest hashed storage key (hashed slot).
265    ///
266    /// Given the next post state and database entries, return the smallest of the two.
267    /// If the storage keys are the same, the post state entry is given precedence.
268    fn compare_entries(
269        post_state_item: Option<(B256, U256)>,
270        db_item: Option<(B256, U256)>,
271    ) -> Option<(B256, U256)> {
272        if let Some((post_state_entry, db_entry)) = post_state_item.zip(db_item) {
273            // If both are not empty, return the smallest of the two
274            // Post state is given precedence if keys are equal
275            Some(if post_state_entry.0 <= db_entry.0 { post_state_entry } else { db_entry })
276        } else {
277            // Return either non-empty entry
278            db_item.or(post_state_item)
279        }
280    }
281}
282
283impl<C> HashedCursor for HashedPostStateStorageCursor<'_, C>
284where
285    C: HashedStorageCursor<Value = U256>,
286{
287    type Value = U256;
288
289    /// Seek the next account storage entry for a given hashed key pair.
290    fn seek(&mut self, subkey: B256) -> Result<Option<(B256, Self::Value)>, DatabaseError> {
291        let entry = self.seek_inner(subkey)?;
292        self.last_slot = entry.as_ref().map(|entry| entry.0);
293        Ok(entry)
294    }
295
296    /// Return the next account storage entry for the current account key.
297    fn next(&mut self) -> Result<Option<(B256, Self::Value)>, DatabaseError> {
298        let next = match self.last_slot {
299            Some(last_slot) => {
300                let entry = self.next_inner(last_slot)?;
301                self.last_slot = entry.as_ref().map(|entry| entry.0);
302                entry
303            }
304            // no previous entry was found
305            None => None,
306        };
307        Ok(next)
308    }
309}
310
311impl<C> HashedStorageCursor for HashedPostStateStorageCursor<'_, C>
312where
313    C: HashedStorageCursor<Value = U256>,
314{
315    /// Returns `true` if the account has no storage entries.
316    ///
317    /// This function should be called before attempting to call [`HashedCursor::seek`] or
318    /// [`HashedCursor::next`].
319    fn is_storage_empty(&mut self) -> Result<bool, DatabaseError> {
320        let is_empty = match &self.post_state_cursor {
321            Some(cursor) => {
322                // If the storage has been wiped at any point
323                self.storage_wiped &&
324                    // and the current storage does not contain any non-zero values
325                    cursor.is_empty()
326            }
327            None => self.cursor.is_storage_empty()?,
328        };
329        Ok(is_empty)
330    }
331}
reth_trie/hashed_cursor/post_state.rs

reth_trie/hashed_cursor/
post_state.rs
