reth_trie/hashed_cursor/
post_state.rs

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

reth_trie/hashed_cursor/
post_state.rs
