revm_database/states/
reverts.rs

1use super::{
2    changes::PlainStorageRevert, AccountStatus, BundleAccount, PlainStateReverts,
3    StorageWithOriginalValues,
4};
5use core::{
6    cmp::Ordering,
7    ops::{Deref, DerefMut},
8};
9use primitives::{Address, HashMap, StorageKey, StorageValue};
10use state::AccountInfo;
11use std::vec::Vec;
12
13/// Contains reverts of multiple account in multiple transitions (Transitions as a block).
14#[derive(Clone, Debug, Default, Eq)]
15#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
16pub struct Reverts(Vec<Vec<(Address, AccountRevert)>>);
17
18impl Deref for Reverts {
19    type Target = Vec<Vec<(Address, AccountRevert)>>;
20
21    fn deref(&self) -> &Self::Target {
22        &self.0
23    }
24}
25
26impl DerefMut for Reverts {
27    fn deref_mut(&mut self) -> &mut Self::Target {
28        &mut self.0
29    }
30}
31
32impl Reverts {
33    /// Creates new reverts.
34    pub fn new(reverts: Vec<Vec<(Address, AccountRevert)>>) -> Self {
35        Self(reverts)
36    }
37
38    /// Sorts account inside transition by their address.
39    pub fn sort(&mut self) {
40        for revert in &mut self.0 {
41            revert.sort_by_key(|(address, _)| *address);
42        }
43    }
44
45    /// Extends reverts with other reverts.
46    pub fn extend(&mut self, other: Reverts) {
47        self.0.extend(other.0);
48    }
49
50    /// Generates a [`PlainStateReverts`].
51    ///
52    /// Note that account are sorted by address.
53    pub fn to_plain_state_reverts(&self) -> PlainStateReverts {
54        let mut state_reverts = PlainStateReverts::with_capacity(self.0.len());
55        for reverts in &self.0 {
56            // Pessimistically pre-allocate assuming _all_ accounts changed.
57            let mut accounts = Vec::with_capacity(reverts.len());
58            let mut storage = Vec::with_capacity(reverts.len());
59            for (address, revert_account) in reverts {
60                match &revert_account.account {
61                    AccountInfoRevert::RevertTo(acc) => {
62                        // Cloning is cheap, because account info has 3 small
63                        // fields and a Bytes
64                        accounts.push((*address, Some(acc.clone())))
65                    }
66                    AccountInfoRevert::DeleteIt => accounts.push((*address, None)),
67                    AccountInfoRevert::DoNothing => (),
68                }
69                if revert_account.wipe_storage || !revert_account.storage.is_empty() {
70                    storage.push(PlainStorageRevert {
71                        address: *address,
72                        wiped: revert_account.wipe_storage,
73                        storage_revert: revert_account
74                            .storage
75                            .iter()
76                            .map(|(k, v)| (*k, *v))
77                            .collect::<Vec<_>>(),
78                    });
79                }
80            }
81            state_reverts.accounts.push(accounts);
82            state_reverts.storage.push(storage);
83        }
84        state_reverts
85    }
86
87    /// Compare two Reverts instances, ignoring the order of elements
88    pub fn content_eq(&self, other: &Self) -> bool {
89        if self.0.len() != other.0.len() {
90            return false;
91        }
92
93        for (self_transition, other_transition) in self.0.iter().zip(other.0.iter()) {
94            if self_transition.len() != other_transition.len() {
95                return false;
96            }
97
98            let mut self_transition = self_transition.clone();
99            let mut other_transition = other_transition.clone();
100            // Sort both transitions
101            self_transition.sort_by(|(addr1, revert1), (addr2, revert2)| {
102                addr1.cmp(addr2).then_with(|| revert1.cmp(revert2))
103            });
104            other_transition.sort_by(|(addr1, revert1), (addr2, revert2)| {
105                addr1.cmp(addr2).then_with(|| revert1.cmp(revert2))
106            });
107
108            // Compare sorted transitions
109            if self_transition != other_transition {
110                return false;
111            }
112        }
113
114        true
115    }
116
117    /// Consume reverts and create [`PlainStateReverts`].
118    ///
119    /// Note that account are sorted by address.
120    #[deprecated = "Use `to_plain_state_reverts` instead"]
121    pub fn into_plain_state_reverts(self) -> PlainStateReverts {
122        self.to_plain_state_reverts()
123    }
124}
125
126impl PartialEq for Reverts {
127    fn eq(&self, other: &Self) -> bool {
128        self.content_eq(other)
129    }
130}
131
132/// Assumption is that Revert can return full state from any future state to any past state.
133///
134/// # Note
135/// It is created when new account state is applied to old account state.
136///
137/// And it is used to revert new account state to the old account state.
138///
139/// [AccountRevert] is structured in this way as we need to save it inside database.
140///
141/// And we need to be able to read it from database.
142#[derive(Clone, Default, Debug, PartialEq, Eq)]
143#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
144pub struct AccountRevert {
145    /// Account information revert.
146    pub account: AccountInfoRevert,
147    /// Storage slots to revert.
148    pub storage: HashMap<StorageKey, RevertToSlot>,
149    /// Previous account status before the change.
150    pub previous_status: AccountStatus,
151    /// Whether to wipe the storage.
152    pub wipe_storage: bool,
153}
154
155impl AccountRevert {
156    /// The approximate size of changes needed to store this account revert.
157    ///
158    /// `1 + storage_reverts_len`
159    pub fn size_hint(&self) -> usize {
160        1 + self.storage.len()
161    }
162
163    /// Very similar to new_selfdestructed but it will add additional zeros ([RevertToSlot::Destroyed])
164    /// for the storage that are set if account is again created.
165    pub fn new_selfdestructed_again(
166        status: AccountStatus,
167        account: AccountInfoRevert,
168        mut previous_storage: StorageWithOriginalValues,
169        updated_storage: StorageWithOriginalValues,
170    ) -> Self {
171        // Take present storage values as the storages that we are going to revert to.
172        // As those values got destroyed.
173        let mut previous_storage: HashMap<StorageKey, RevertToSlot> = previous_storage
174            .drain()
175            .map(|(key, value)| (key, RevertToSlot::Some(value.present_value)))
176            .collect();
177        for (key, _) in updated_storage {
178            previous_storage
179                .entry(key)
180                .or_insert(RevertToSlot::Destroyed);
181        }
182        AccountRevert {
183            account,
184            storage: previous_storage,
185            previous_status: status,
186            wipe_storage: false,
187        }
188    }
189
190    /// Creates revert for states that were before selfdestruct.
191    pub fn new_selfdestructed_from_bundle(
192        account_info_revert: AccountInfoRevert,
193        bundle_account: &mut BundleAccount,
194        updated_storage: &StorageWithOriginalValues,
195    ) -> Option<Self> {
196        match bundle_account.status {
197            AccountStatus::InMemoryChange
198            | AccountStatus::Changed
199            | AccountStatus::LoadedEmptyEIP161
200            | AccountStatus::Loaded => {
201                let mut ret = AccountRevert::new_selfdestructed_again(
202                    bundle_account.status,
203                    account_info_revert,
204                    bundle_account.storage.drain().collect(),
205                    updated_storage.clone(),
206                );
207                ret.wipe_storage = true;
208                Some(ret)
209            }
210            _ => None,
211        }
212    }
213
214    /// Create new selfdestruct revert.
215    pub fn new_selfdestructed(
216        status: AccountStatus,
217        account: AccountInfoRevert,
218        mut storage: StorageWithOriginalValues,
219    ) -> Self {
220        // Zero all present storage values and save present values to AccountRevert.
221        let previous_storage = storage
222            .iter_mut()
223            .map(|(key, value)| {
224                // Take previous value and set ZERO as storage got destroyed.
225                (*key, RevertToSlot::Some(value.present_value))
226            })
227            .collect();
228
229        Self {
230            account,
231            storage: previous_storage,
232            previous_status: status,
233            wipe_storage: true,
234        }
235    }
236
237    /// Returns `true` if there is nothing to revert,
238    /// by checking that:
239    /// * both account info and storage have been left untouched
240    /// * we don't need to wipe storage
241    pub fn is_empty(&self) -> bool {
242        self.account == AccountInfoRevert::DoNothing
243            && self.storage.is_empty()
244            && !self.wipe_storage
245    }
246}
247
248/// Implements partial ordering for AccountRevert
249impl PartialOrd for AccountRevert {
250    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
251        Some(self.cmp(other))
252    }
253}
254
255/// Implements total ordering for AccountRevert
256impl Ord for AccountRevert {
257    fn cmp(&self, other: &Self) -> Ordering {
258        // First compare accounts
259        if let Some(ord) = self.account.partial_cmp(&other.account) {
260            if ord != Ordering::Equal {
261                return ord;
262            }
263        }
264
265        // Convert HashMaps to sorted vectors for comparison
266        let mut self_storage: Vec<_> = self.storage.iter().collect();
267        let mut other_storage: Vec<_> = other.storage.iter().collect();
268
269        // Sort by key and then by value
270        self_storage.sort_by(|(k1, v1), (k2, v2)| k1.cmp(k2).then_with(|| v1.cmp(v2)));
271        other_storage.sort_by(|(k1, v1), (k2, v2)| k1.cmp(k2).then_with(|| v1.cmp(v2)));
272
273        // Compare each element
274        for (self_entry, other_entry) in self_storage.iter().zip(other_storage.iter()) {
275            let key_ord = self_entry.0.cmp(other_entry.0);
276            if key_ord != Ordering::Equal {
277                return key_ord;
278            }
279            let value_ord = self_entry.1.cmp(other_entry.1);
280            if value_ord != Ordering::Equal {
281                return value_ord;
282            }
283        }
284
285        // If one vector is longer than the other, or if all elements are equal
286        self_storage
287            .len()
288            .cmp(&other_storage.len())
289            .then_with(|| self.previous_status.cmp(&other.previous_status))
290            .then_with(|| self.wipe_storage.cmp(&other.wipe_storage))
291    }
292}
293
294/// Depending on previous state of account info this
295/// will tell us what to do on revert.
296#[derive(Clone, Default, Debug, PartialEq, Eq, Hash, PartialOrd, Ord)]
297#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
298pub enum AccountInfoRevert {
299    #[default]
300    /// Nothing changed
301    DoNothing,
302    /// Account was created and on revert we need to remove it with all storage.
303    DeleteIt,
304    /// Account was changed and on revert we need to put old state.
305    RevertTo(AccountInfo),
306}
307
308/// So storage can have multiple types:
309/// * Zero, on revert remove plain state.
310/// * Value, on revert set this value
311/// * Destroyed, should be removed on revert but on Revert set it as zero.
312///
313/// **Note**: It is completely different state if Storage is Zero or Some or if Storage was
314/// Destroyed.
315///
316/// Because if it is destroyed, previous values can be found in database or it can be zero.
317#[derive(Clone, Debug, Copy, PartialEq, Eq, Hash, PartialOrd, Ord)]
318#[cfg_attr(feature = "serde", derive(serde::Serialize, serde::Deserialize))]
319pub enum RevertToSlot {
320    /// Revert to this value.
321    Some(StorageValue),
322    /// Storage was destroyed.
323    Destroyed,
324}
325
326impl RevertToSlot {
327    /// Returns the previous value to set on revert.
328    pub fn to_previous_value(self) -> StorageValue {
329        match self {
330            RevertToSlot::Some(value) => value,
331            RevertToSlot::Destroyed => StorageValue::ZERO,
332        }
333    }
334}