revm_interpreter/interpreter/
stack.rs1use crate::InstructionResult;
2use core::{fmt, ptr};
3use primitives::U256;
4use std::vec::Vec;
5
6use super::StackTr;
7
8pub const STACK_LIMIT: usize = 1024;
10
11#[derive(Debug, PartialEq, Eq, Hash)]
13#[cfg_attr(feature = "serde", derive(serde::Serialize))]
14pub struct Stack {
15 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 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 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 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 #[inline]
103 pub fn new() -> Self {
104 Self {
105 data: Vec::with_capacity(STACK_LIMIT),
107 }
108 }
109
110 #[inline]
112 pub fn invalid() -> Self {
113 Self { data: Vec::new() }
114 }
115
116 #[inline]
118 pub fn len(&self) -> usize {
119 self.data.len()
120 }
121
122 #[inline]
124 pub fn is_empty(&self) -> bool {
125 self.data.is_empty()
126 }
127
128 #[inline]
130 pub fn data(&self) -> &Vec<U256> {
131 &self.data
132 }
133
134 #[inline]
136 pub fn data_mut(&mut self) -> &mut Vec<U256> {
137 &mut self.data
138 }
139
140 #[inline]
142 pub fn into_data(self) -> Vec<U256> {
143 self.data
144 }
145
146 #[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 #[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 #[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 #[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 #[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 #[inline]
208 #[must_use]
209 #[cfg_attr(debug_assertions, track_caller)]
210 pub fn push(&mut self, value: U256) -> bool {
211 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 #[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 #[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 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 #[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 #[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 unsafe {
285 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 #[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 #[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 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 let words = slice.chunks_exact(32);
329 let partial_last_word = words.remainder();
330 for word in words {
331 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 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 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 let m = i % 4; if m != 0 {
364 dst.add(i).write_bytes(0, 4 - m);
365 }
366 }
367
368 true
369 }
370
371 #[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 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 run(|stack| {
424 stack.push_slice(b"").unwrap();
425 assert_eq!(stack.data, []);
426 });
427
428 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 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 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 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 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 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 assert!(!full_stack.push(U256::from(100)));
503 assert!(!cloned_full.push(U256::from(100)));
504 }
505}