reth_trie/hashed_cursor/
post_state.rs

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

reth_trie/hashed_cursor/
post_state.rs
