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

reth_trie/hashed_cursor/
post_state.rs
