reth_trie/hashed_cursor/
post_state.rs

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