revm_interpreter/interpreter/
stack.rs

1use crate::InstructionResult;
2use core::{fmt, ptr};
3use primitives::U256;
4use std::vec::Vec;
5
6use super::StackTr;
7
8/// EVM interpreter stack limit.
9pub const STACK_LIMIT: usize = 1024;
10
11/// EVM stack with [STACK_LIMIT] capacity of words.
12#[derive(Debug, PartialEq, Eq, Hash)]
13#[cfg_attr(feature = "serde", derive(serde::Serialize))]
14pub struct Stack {
15    /// The underlying data of the stack.
16    data: Vec<U256>,
17}
18
19impl fmt::Display for Stack {
20    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
21        f.write_str("[")?;
22        for (i, x) in self.data.iter().enumerate() {
23            if i > 0 {
24                f.write_str(", ")?;
25            }
26            write!(f, "{x}")?;
27        }
28        f.write_str("]")
29    }
30}
31
32impl Default for Stack {
33    #[inline]
34    fn default() -> Self {
35        Self::new()
36    }
37}
38
39impl Clone for Stack {
40    fn clone(&self) -> Self {
41        // Use `Self::new()` to ensure the cloned Stack maintains the STACK_LIMIT capacity,
42        // and then copy the data. This preserves the invariant that Stack always has
43        // STACK_LIMIT capacity, which is crucial for the safety and correctness of other methods.
44        let mut new_stack = Self::new();
45        new_stack.data.extend_from_slice(&self.data);
46        new_stack
47    }
48}
49
50impl StackTr for Stack {
51    #[inline]
52    fn len(&self) -> usize {
53        self.len()
54    }
55
56    #[inline]
57    fn clear(&mut self) {
58        self.data.clear();
59    }
60
61    #[inline]
62    fn popn<const N: usize>(&mut self) -> Option<[U256; N]> {
63        if self.len() < N {
64            return None;
65        }
66        // SAFETY: Stack length is checked above.
67        Some(unsafe { self.popn::<N>() })
68    }
69
70    #[inline]
71    fn popn_top<const POPN: usize>(&mut self) -> Option<([U256; POPN], &mut U256)> {
72        if self.len() < POPN + 1 {
73            return None;
74        }
75        // SAFETY: Stack length is checked above.
76        Some(unsafe { self.popn_top::<POPN>() })
77    }
78
79    #[inline]
80    fn exchange(&mut self, n: usize, m: usize) -> bool {
81        self.exchange(n, m)
82    }
83
84    #[inline]
85    fn dup(&mut self, n: usize) -> bool {
86        self.dup(n)
87    }
88
89    #[inline]
90    fn push(&mut self, value: U256) -> bool {
91        self.push(value)
92    }
93
94    #[inline]
95    fn push_slice(&mut self, slice: &[u8]) -> bool {
96        self.push_slice_(slice)
97    }
98}
99
100impl Stack {
101    /// Instantiate a new stack with the [default stack limit][STACK_LIMIT].
102    #[inline]
103    pub fn new() -> Self {
104        Self {
105            // SAFETY: Expansion functions assume that capacity is `STACK_LIMIT`.
106            data: Vec::with_capacity(STACK_LIMIT),
107        }
108    }
109
110    /// Instantiate a new invalid Stack.
111    #[inline]
112    pub fn invalid() -> Self {
113        Self { data: Vec::new() }
114    }
115
116    /// Returns the length of the stack in words.
117    #[inline]
118    pub fn len(&self) -> usize {
119        self.data.len()
120    }
121
122    /// Returns whether the stack is empty.
123    #[inline]
124    pub fn is_empty(&self) -> bool {
125        self.data.is_empty()
126    }
127
128    /// Returns a reference to the underlying data buffer.
129    #[inline]
130    pub fn data(&self) -> &Vec<U256> {
131        &self.data
132    }
133
134    /// Returns a mutable reference to the underlying data buffer.
135    #[inline]
136    pub fn data_mut(&mut self) -> &mut Vec<U256> {
137        &mut self.data
138    }
139
140    /// Consumes the stack and returns the underlying data buffer.
141    #[inline]
142    pub fn into_data(self) -> Vec<U256> {
143        self.data
144    }
145
146    /// Removes the topmost element from the stack and returns it, or `StackUnderflow` if it is
147    /// empty.
148    #[inline]
149    #[cfg_attr(debug_assertions, track_caller)]
150    pub fn pop(&mut self) -> Result<U256, InstructionResult> {
151        self.data.pop().ok_or(InstructionResult::StackUnderflow)
152    }
153
154    /// Removes the topmost element from the stack and returns it.
155    ///
156    /// # Safety
157    ///
158    /// The caller is responsible for checking the length of the stack.
159    #[inline]
160    #[cfg_attr(debug_assertions, track_caller)]
161    pub unsafe fn pop_unsafe(&mut self) -> U256 {
162        assume!(!self.data.is_empty());
163        self.data.pop().unwrap_unchecked()
164    }
165
166    /// Peeks the top of the stack.
167    ///
168    /// # Safety
169    ///
170    /// The caller is responsible for checking the length of the stack.
171    #[inline]
172    #[cfg_attr(debug_assertions, track_caller)]
173    pub unsafe fn top_unsafe(&mut self) -> &mut U256 {
174        assume!(!self.data.is_empty());
175        self.data.last_mut().unwrap_unchecked()
176    }
177
178    /// Pops `N` values from the stack.
179    ///
180    /// # Safety
181    ///
182    /// The caller is responsible for checking the length of the stack.
183    #[inline]
184    #[cfg_attr(debug_assertions, track_caller)]
185    pub unsafe fn popn<const N: usize>(&mut self) -> [U256; N] {
186        assume!(self.data.len() >= N);
187        core::array::from_fn(|_| unsafe { self.pop_unsafe() })
188    }
189
190    /// Pops `N` values from the stack and returns the top of the stack.
191    ///
192    /// # Safety
193    ///
194    /// The caller is responsible for checking the length of the stack.
195    #[inline]
196    #[cfg_attr(debug_assertions, track_caller)]
197    pub unsafe fn popn_top<const POPN: usize>(&mut self) -> ([U256; POPN], &mut U256) {
198        let result = self.popn::<POPN>();
199        let top = self.top_unsafe();
200        (result, top)
201    }
202
203    /// Push a new value onto the stack.
204    ///
205    /// If it will exceed the stack limit, returns false and leaves the stack
206    /// unchanged.
207    #[inline]
208    #[must_use]
209    #[cfg_attr(debug_assertions, track_caller)]
210    pub fn push(&mut self, value: U256) -> bool {
211        // Allows the compiler to optimize out the `Vec::push` capacity check.
212        assume!(self.data.capacity() == STACK_LIMIT);
213        if self.data.len() == STACK_LIMIT {
214            return false;
215        }
216        self.data.push(value);
217        true
218    }
219
220    /// Peek a value at given index for the stack, where the top of
221    /// the stack is at index `0`. If the index is too large,
222    /// `StackError::Underflow` is returned.
223    #[inline]
224    pub fn peek(&self, no_from_top: usize) -> Result<U256, InstructionResult> {
225        if self.data.len() > no_from_top {
226            Ok(self.data[self.data.len() - no_from_top - 1])
227        } else {
228            Err(InstructionResult::StackUnderflow)
229        }
230    }
231
232    /// Duplicates the `N`th value from the top of the stack.
233    ///
234    /// # Panics
235    ///
236    /// Panics if `n` is 0.
237    #[inline]
238    #[must_use]
239    #[cfg_attr(debug_assertions, track_caller)]
240    pub fn dup(&mut self, n: usize) -> bool {
241        assume!(n > 0, "attempted to dup 0");
242        let len = self.data.len();
243        if len < n || len + 1 > STACK_LIMIT {
244            false
245        } else {
246            // SAFETY: Check for out of bounds is done above and it makes this safe to do.
247            unsafe {
248                let ptr = self.data.as_mut_ptr().add(len);
249                ptr::copy_nonoverlapping(ptr.sub(n), ptr, 1);
250                self.data.set_len(len + 1);
251            }
252            true
253        }
254    }
255
256    /// Swaps the topmost value with the `N`th value from the top.
257    ///
258    /// # Panics
259    ///
260    /// Panics if `n` is 0.
261    #[inline(always)]
262    #[cfg_attr(debug_assertions, track_caller)]
263    pub fn swap(&mut self, n: usize) -> bool {
264        self.exchange(0, n)
265    }
266
267    /// Exchange two values on the stack.
268    ///
269    /// `n` is the first index, and the second index is calculated as `n + m`.
270    ///
271    /// # Panics
272    ///
273    /// Panics if `m` is zero.
274    #[inline]
275    #[cfg_attr(debug_assertions, track_caller)]
276    pub fn exchange(&mut self, n: usize, m: usize) -> bool {
277        assume!(m > 0, "overlapping exchange");
278        let len = self.data.len();
279        let n_m_index = n + m;
280        if n_m_index >= len {
281            return false;
282        }
283        // SAFETY: `n` and `n_m` are checked to be within bounds, and they don't overlap.
284        unsafe {
285            // Note: `ptr::swap_nonoverlapping` is more efficient than `slice::swap` or `ptr::swap`
286            // because it operates under the assumption that the pointers do not overlap,
287            // eliminating an intermediate copy,
288            // which is a condition we know to be true in this context.
289            let top = self.data.as_mut_ptr().add(len - 1);
290            core::ptr::swap_nonoverlapping(top.sub(n), top.sub(n_m_index), 1);
291        }
292        true
293    }
294
295    /// Pushes an arbitrary length slice of bytes onto the stack, padding the last word with zeros
296    /// if necessary.
297    #[inline]
298    pub fn push_slice(&mut self, slice: &[u8]) -> Result<(), InstructionResult> {
299        if self.push_slice_(slice) {
300            Ok(())
301        } else {
302            Err(InstructionResult::StackOverflow)
303        }
304    }
305
306    /// Pushes an arbitrary length slice of bytes onto the stack, padding the last word with zeros
307    /// if necessary.
308    #[inline]
309    fn push_slice_(&mut self, slice: &[u8]) -> bool {
310        if slice.is_empty() {
311            return true;
312        }
313
314        let n_words = slice.len().div_ceil(32);
315        let new_len = self.data.len() + n_words;
316        if new_len > STACK_LIMIT {
317            return false;
318        }
319
320        // SAFETY: Length checked above.
321        unsafe {
322            let dst = self.data.as_mut_ptr().add(self.data.len()).cast::<u64>();
323            self.data.set_len(new_len);
324
325            let mut i = 0;
326
327            // Write full words
328            let words = slice.chunks_exact(32);
329            let partial_last_word = words.remainder();
330            for word in words {
331                // Note: We unroll `U256::from_be_bytes` here to write directly into the buffer,
332                // instead of creating a 32 byte array on the stack and then copying it over.
333                for l in word.rchunks_exact(8) {
334                    dst.add(i).write(u64::from_be_bytes(l.try_into().unwrap()));
335                    i += 1;
336                }
337            }
338
339            if partial_last_word.is_empty() {
340                return true;
341            }
342
343            // Write limbs of partial last word
344            let limbs = partial_last_word.rchunks_exact(8);
345            let partial_last_limb = limbs.remainder();
346            for l in limbs {
347                dst.add(i).write(u64::from_be_bytes(l.try_into().unwrap()));
348                i += 1;
349            }
350
351            // Write partial last limb by padding with zeros
352            if !partial_last_limb.is_empty() {
353                let mut tmp = [0u8; 8];
354                tmp[8 - partial_last_limb.len()..].copy_from_slice(partial_last_limb);
355                dst.add(i).write(u64::from_be_bytes(tmp));
356                i += 1;
357            }
358
359            debug_assert_eq!(i.div_ceil(4), n_words, "wrote too much");
360
361            // Zero out upper bytes of last word
362            let m = i % 4; // 32 / 8
363            if m != 0 {
364                dst.add(i).write_bytes(0, 4 - m);
365            }
366        }
367
368        true
369    }
370
371    /// Set a value at given index for the stack, where the top of the
372    /// stack is at index `0`. If the index is too large,
373    /// `StackError::Underflow` is returned.
374    #[inline]
375    pub fn set(&mut self, no_from_top: usize, val: U256) -> Result<(), InstructionResult> {
376        if self.data.len() > no_from_top {
377            let len = self.data.len();
378            self.data[len - no_from_top - 1] = val;
379            Ok(())
380        } else {
381            Err(InstructionResult::StackUnderflow)
382        }
383    }
384}
385
386#[cfg(feature = "serde")]
387impl<'de> serde::Deserialize<'de> for Stack {
388    fn deserialize<D>(deserializer: D) -> Result<Self, D::Error>
389    where
390        D: serde::Deserializer<'de>,
391    {
392        let mut data = Vec::<U256>::deserialize(deserializer)?;
393        if data.len() > STACK_LIMIT {
394            return Err(serde::de::Error::custom(std::format!(
395                "stack size exceeds limit: {} > {}",
396                data.len(),
397                STACK_LIMIT
398            )));
399        }
400        data.reserve(STACK_LIMIT - data.len());
401        Ok(Self { data })
402    }
403}
404
405#[cfg(test)]
406mod tests {
407    use super::*;
408
409    fn run(f: impl FnOnce(&mut Stack)) {
410        let mut stack = Stack::new();
411        // Fill capacity with non-zero values
412        unsafe {
413            stack.data.set_len(STACK_LIMIT);
414            stack.data.fill(U256::MAX);
415            stack.data.set_len(0);
416        }
417        f(&mut stack);
418    }
419
420    #[test]
421    fn push_slices() {
422        // No-op
423        run(|stack| {
424            stack.push_slice(b"").unwrap();
425            assert!(stack.data.is_empty());
426        });
427
428        // One word
429        run(|stack| {
430            stack.push_slice(&[42]).unwrap();
431            assert_eq!(stack.data, [U256::from(42)]);
432        });
433
434        let n = 0x1111_2222_3333_4444_5555_6666_7777_8888_u128;
435        run(|stack| {
436            stack.push_slice(&n.to_be_bytes()).unwrap();
437            assert_eq!(stack.data, [U256::from(n)]);
438        });
439
440        // More than one word
441        run(|stack| {
442            let b = [U256::from(n).to_be_bytes::<32>(); 2].concat();
443            stack.push_slice(&b).unwrap();
444            assert_eq!(stack.data, [U256::from(n); 2]);
445        });
446
447        run(|stack| {
448            let b = [&[0; 32][..], &[42u8]].concat();
449            stack.push_slice(&b).unwrap();
450            assert_eq!(stack.data, [U256::ZERO, U256::from(42)]);
451        });
452
453        run(|stack| {
454            let b = [&[0; 32][..], &n.to_be_bytes()].concat();
455            stack.push_slice(&b).unwrap();
456            assert_eq!(stack.data, [U256::ZERO, U256::from(n)]);
457        });
458
459        run(|stack| {
460            let b = [&[0; 64][..], &n.to_be_bytes()].concat();
461            stack.push_slice(&b).unwrap();
462            assert_eq!(stack.data, [U256::ZERO, U256::ZERO, U256::from(n)]);
463        });
464    }
465
466    #[test]
467    fn stack_clone() {
468        // Test cloning an empty stack
469        let empty_stack = Stack::new();
470        let cloned_empty = empty_stack.clone();
471        assert_eq!(empty_stack, cloned_empty);
472        assert_eq!(cloned_empty.len(), 0);
473        assert_eq!(cloned_empty.data().capacity(), STACK_LIMIT);
474
475        // Test cloning a partially filled stack
476        let mut partial_stack = Stack::new();
477        for i in 0..10 {
478            assert!(partial_stack.push(U256::from(i)));
479        }
480        let mut cloned_partial = partial_stack.clone();
481        assert_eq!(partial_stack, cloned_partial);
482        assert_eq!(cloned_partial.len(), 10);
483        assert_eq!(cloned_partial.data().capacity(), STACK_LIMIT);
484
485        // Test that modifying the clone doesn't affect the original
486        assert!(cloned_partial.push(U256::from(100)));
487        assert_ne!(partial_stack, cloned_partial);
488        assert_eq!(partial_stack.len(), 10);
489        assert_eq!(cloned_partial.len(), 11);
490
491        // Test cloning a full stack
492        let mut full_stack = Stack::new();
493        for i in 0..STACK_LIMIT {
494            assert!(full_stack.push(U256::from(i)));
495        }
496        let mut cloned_full = full_stack.clone();
497        assert_eq!(full_stack, cloned_full);
498        assert_eq!(cloned_full.len(), STACK_LIMIT);
499        assert_eq!(cloned_full.data().capacity(), STACK_LIMIT);
500
501        // Test push to the full original or cloned stack should return StackOverflow
502        assert!(!full_stack.push(U256::from(100)));
503        assert!(!cloned_full.push(U256::from(100)));
504    }
505}
revm_interpreter/interpreter/stack.rs

revm_interpreter/interpreter/
stack.rs
