essential_vm/
stack.rs

1//! Stack operation and related stack manipulation implementations.
2
3use crate::{
4    asm::Word,
5    error::{LenWordsError, StackError, StackResult},
6};
7use essential_types::convert::bool_from_word;
8
9#[cfg(test)]
10mod frame_tests;
11
12/// The VM's `Stack`, i.e. a `Vec` of `Word`s updated during each step of execution.
13///
14/// A light wrapper around `Vec<Word>` providing helper methods specific to
15/// essential VM execution.
16#[derive(Clone, Debug, PartialEq, Default)]
17pub struct Stack(Vec<Word>);
18
19impl Stack {
20    /// Limit the stack size to 32KB to avoid memory bloat during parallel constraint checking.
21    pub const SIZE_LIMIT: usize = 4096;
22
23    /// Push a word to the stack.
24    ///
25    /// Errors in the case that pushing an element would cause the stack to overflow.
26    pub fn push(&mut self, word: Word) -> StackResult<()> {
27        if self.len() >= Self::SIZE_LIMIT {
28            return Err(StackError::Overflow);
29        }
30        self.0.push(word);
31        Ok(())
32    }
33
34    /// Extend the stack by with the given iterator yielding words.
35    ///
36    /// Errors in the case that pushing an element would cause the stack to overflow.
37    pub fn extend(&mut self, words: impl IntoIterator<Item = Word>) -> StackResult<()> {
38        for word in words {
39            self.push(word)?;
40        }
41        Ok(())
42    }
43
44    /// Reserve a length of zeroed words on the stack.
45    pub(crate) fn reserve_zeroed(&mut self) -> StackResult<()> {
46        let len = self.pop()?;
47        let len = usize::try_from(len).map_err(|_| StackError::IndexOutOfBounds)?;
48        let start = self.len();
49        let new_len = start.saturating_add(len);
50        if new_len > Self::SIZE_LIMIT {
51            return Err(StackError::IndexOutOfBounds);
52        }
53        self.0.resize(new_len, 0);
54        let start = Word::try_from(start).map_err(|_| StackError::IndexOutOfBounds)?;
55        self.push(start)?;
56        Ok(())
57    }
58
59    /// Load a word from the given index.
60    pub(crate) fn load(&mut self) -> StackResult<()> {
61        let ix = self.pop()?;
62        let ix = usize::try_from(ix).map_err(|_| StackError::IndexOutOfBounds)?;
63        let word = self
64            .0
65            .get(ix)
66            .copied()
67            .ok_or(StackError::IndexOutOfBounds)?;
68        self.push(word)
69    }
70
71    /// Store a word at the given index.
72    pub(crate) fn store(&mut self) -> StackResult<()> {
73        let [word, ix] = self.pop2()?;
74        let ix = usize::try_from(ix).map_err(|_| StackError::IndexOutOfBounds)?;
75        let Some(w) = self.0.get_mut(ix) else {
76            return Err(StackError::IndexOutOfBounds);
77        };
78        *w = word;
79        Ok(())
80    }
81
82    /// The DupFrom op implementation.
83    pub(crate) fn dup_from(&mut self) -> StackResult<()> {
84        let rev_ix_w = self.pop()?;
85        let rev_ix = usize::try_from(rev_ix_w).map_err(|_| StackError::IndexOutOfBounds)?;
86        let ix = self
87            .len()
88            .checked_sub(rev_ix)
89            .and_then(|i| i.checked_sub(1))
90            .ok_or(StackError::IndexOutOfBounds)?;
91        let w = *self.get(ix).ok_or(StackError::IndexOutOfBounds)?;
92        self.push(w)?;
93        Ok(())
94    }
95
96    /// The SwapIndex op implementation.
97    pub(crate) fn swap_index(&mut self) -> StackResult<()> {
98        let rev_ix_w = self.pop()?;
99        let top_ix = self
100            .len()
101            .checked_sub(1)
102            .ok_or(StackError::IndexOutOfBounds)?;
103        let rev_ix = usize::try_from(rev_ix_w).map_err(|_| StackError::IndexOutOfBounds)?;
104        let ix = top_ix
105            .checked_sub(rev_ix)
106            .ok_or(StackError::IndexOutOfBounds)?;
107        self.0.swap(ix, top_ix);
108        Ok(())
109    }
110
111    /// The Select op implementation.
112    pub(crate) fn select(&mut self) -> StackResult<()> {
113        self.pop().and_then(|cond_w| {
114            self.pop2_push1(|w0, w1| {
115                Ok(
116                    if bool_from_word(cond_w).ok_or(StackError::InvalidCondition(cond_w))? {
117                        w1
118                    } else {
119                        w0
120                    },
121                )
122            })
123        })?;
124        Ok(())
125    }
126
127    /// The SelectRange op implementation.
128    pub(crate) fn select_range(&mut self) -> StackResult<()> {
129        let cond_w = self.pop()?;
130        let cond = bool_from_word(cond_w).ok_or(StackError::InvalidCondition(cond_w))?;
131        let len = self.pop_len()?;
132        if len == 0 {
133            return Ok(());
134        }
135        // check that `len` is at most half the stack length
136        self.len()
137            .checked_sub(len.checked_mul(2).ok_or(StackError::IndexOutOfBounds)?)
138            .ok_or(StackError::IndexOutOfBounds)?;
139        // stack: [arr_a_0, ..arr_a_N, arr_b_0, ..arr_b_N]
140        let arr_b_index = self.len() - len;
141        if cond {
142            // copy arr_b to the space arr_a holds
143            let arr_a_index = arr_b_index - len;
144            self.0
145                .copy_within(arr_b_index..(arr_b_index + len), arr_a_index);
146        }
147        // pop the topmost range that is arr_b
148        self.0.truncate(arr_b_index);
149        Ok(())
150    }
151
152    /// A wrapper around `Vec::pop`, producing an error in the case that the stack is empty.
153    pub fn pop(&mut self) -> StackResult<Word> {
154        self.0.pop().ok_or(StackError::Empty)
155    }
156
157    /// Pop the top 2 values from the stack.
158    ///
159    /// The last values popped appear first in the returned fixed-size array.
160    pub fn pop2(&mut self) -> StackResult<[Word; 2]> {
161        let w1 = self.pop()?;
162        let w0 = self.pop()?;
163        Ok([w0, w1])
164    }
165
166    /// Pop the top 3 values from the stack.
167    ///
168    /// The last values popped appear first in the returned fixed-size array.
169    pub fn pop3(&mut self) -> StackResult<[Word; 3]> {
170        let w2 = self.pop()?;
171        let [w0, w1] = self.pop2()?;
172        Ok([w0, w1, w2])
173    }
174
175    /// Pop the top 4 values from the stack.
176    ///
177    /// The last values popped appear first in the returned fixed-size array.
178    pub fn pop4(&mut self) -> StackResult<[Word; 4]> {
179        let w3 = self.pop()?;
180        let [w0, w1, w2] = self.pop3()?;
181        Ok([w0, w1, w2, w3])
182    }
183
184    /// Pop the top 8 values from the stack.
185    ///
186    /// The last values popped appear first in the returned fixed-size array.
187    pub fn pop8(&mut self) -> StackResult<[Word; 8]> {
188        let [w4, w5, w6, w7] = self.pop4()?;
189        let [w0, w1, w2, w3] = self.pop4()?;
190        Ok([w0, w1, w2, w3, w4, w5, w6, w7])
191    }
192
193    /// Pop 1 word from the stack, apply the given function and push the returned word.
194    pub fn pop1_push1<F, E>(&mut self, f: F) -> Result<(), E>
195    where
196        F: FnOnce(Word) -> Result<Word, E>,
197        E: From<StackError>,
198    {
199        let w = self.pop()?;
200        let x = f(w)?;
201        self.push(x)?;
202        Ok(())
203    }
204
205    /// Pop 2 words from the stack, apply the given function and push the returned word.
206    pub fn pop2_push1<F, E>(&mut self, f: F) -> Result<(), E>
207    where
208        F: FnOnce(Word, Word) -> Result<Word, E>,
209        E: From<StackError>,
210    {
211        let [w0, w1] = self.pop2()?;
212        let x = f(w0, w1)?;
213        self.push(x)?;
214        Ok(())
215    }
216
217    /// Pop 8 words from the stack, apply the given function and push the returned word.
218    pub fn pop8_push1<F, E>(&mut self, f: F) -> Result<(), E>
219    where
220        F: FnOnce([Word; 8]) -> Result<Word, E>,
221        E: From<StackError>,
222    {
223        let ws = self.pop8()?;
224        let x = f(ws)?;
225        self.push(x)?;
226        Ok(())
227    }
228
229    /// Pop 1 word from the stack, apply the given function and push the 2 returned words.
230    pub fn pop1_push2<F, E>(&mut self, f: F) -> Result<(), E>
231    where
232        F: FnOnce(Word) -> Result<[Word; 2], E>,
233        E: From<StackError>,
234    {
235        let w = self.pop()?;
236        let xs = f(w)?;
237        self.extend(xs)?;
238        Ok(())
239    }
240
241    /// Pop 2 words from the stack, apply the given function and push the 2 returned words.
242    pub fn pop2_push2<F, E>(&mut self, f: F) -> Result<(), E>
243    where
244        F: FnOnce(Word, Word) -> Result<[Word; 2], E>,
245        E: From<StackError>,
246    {
247        let [w0, w1] = self.pop2()?;
248        let xs = f(w0, w1)?;
249        self.extend(xs)?;
250        Ok(())
251    }
252
253    /// Pop 2 words from the stack, apply the given function and push the 4 returned words.
254    pub fn pop2_push4<F, E>(&mut self, f: F) -> Result<(), E>
255    where
256        F: FnOnce(Word, Word) -> Result<[Word; 4], E>,
257        E: From<StackError>,
258    {
259        let [w0, w1] = self.pop2()?;
260        let xs = f(w0, w1)?;
261        self.extend(xs)?;
262        Ok(())
263    }
264
265    /// Pop a length value from the top of the stack and return it.
266    pub fn pop_len(&mut self) -> StackResult<usize> {
267        let len_word = self.pop()?;
268        let len = usize::try_from(len_word).map_err(|_| StackError::IndexOutOfBounds)?;
269        Ok(len)
270    }
271
272    /// Pop the length from the top of the stack, then pop and provide that many
273    /// words to the given function.
274    pub fn pop_len_words<F, O, E>(&mut self, f: F) -> Result<O, E>
275    where
276        F: FnOnce(&[Word]) -> Result<O, E>,
277        E: From<StackError>,
278    {
279        let (rest, slice) = slice_split_len_words(self).map_err(StackError::LenWords)?;
280        let out = f(slice)?;
281        self.0.truncate(rest.len());
282        Ok(out)
283    }
284
285    /// Provide the number of words from the top of the stack to the given function.
286    /// Then pop those words off the stack.
287    pub fn pop_words<F, O, E>(&mut self, num_words: usize, f: F) -> Result<O, E>
288    where
289        F: FnOnce(&[Word]) -> Result<O, E>,
290        E: From<StackError>,
291    {
292        let (rest, slice) = slice_split_len(self, num_words).map_err(StackError::LenWords)?;
293        let out = f(slice)?;
294        self.0.truncate(rest.len());
295        Ok(out)
296    }
297
298    /// Pop two slices from the top of the stack, each followed by one word
299    /// describing their length, and pass them to the given function.
300    /// The top slice is provided to the rhs, the bottom slice is provided to the lhs.
301    pub fn pop_len_words2<F, O, E>(&mut self, f: F) -> Result<O, E>
302    where
303        F: FnOnce(&[Word], &[Word]) -> Result<O, E>,
304        E: From<StackError>,
305    {
306        let (rest, rhs) = slice_split_len_words(self).map_err(StackError::LenWords)?;
307        let (rest, lhs) = slice_split_len_words(rest).map_err(StackError::LenWords)?;
308        let out = f(lhs, rhs)?;
309        self.0.truncate(rest.len());
310        Ok(out)
311    }
312
313    /// Reserve additional capacity for the stack.
314    /// Noop if capacity already exists.
315    pub fn reserve(&mut self, additional: usize) {
316        self.0.reserve(additional);
317    }
318}
319
320/// Split a length from the top of the stack slice, then split off a slice of
321/// that length.
322///
323/// Returns `Some((remaining, slice_of_len))`.
324///
325/// Returns `None` if the slice is empty, or the length is greater than the rest
326/// of the slice.
327fn slice_split_len_words(slice: &[Word]) -> Result<(&[Word], &[Word]), LenWordsError> {
328    let (len, rest) = slice.split_last().ok_or(LenWordsError::MissingLength)?;
329    let len = usize::try_from(*len).map_err(|_| LenWordsError::InvalidLength(*len))?;
330    slice_split_len(rest, len)
331}
332
333fn slice_split_len(slice: &[Word], len: usize) -> Result<(&[Word], &[Word]), LenWordsError> {
334    let ix = slice
335        .len()
336        .checked_sub(len)
337        .ok_or(LenWordsError::OutOfBounds(len as Word))?;
338    Ok(slice.split_at(ix))
339}
340
341impl From<Stack> for Vec<Word> {
342    fn from(stack: Stack) -> Self {
343        stack.0
344    }
345}
346
347impl TryFrom<Vec<Word>> for Stack {
348    type Error = StackError;
349    fn try_from(vec: Vec<Word>) -> Result<Self, Self::Error> {
350        if vec.len() > Self::SIZE_LIMIT {
351            Err(StackError::Overflow)
352        } else {
353            Ok(Self(vec))
354        }
355    }
356}
357
358impl core::ops::Deref for Stack {
359    type Target = Vec<Word>;
360    fn deref(&self) -> &Self::Target {
361        &self.0
362    }
363}
364
365#[cfg(test)]
366mod tests {
367    use crate::{
368        asm::Stack,
369        error::{ExecError, OpError, StackError},
370        sync::test_util::*,
371        utils::EmptyState,
372        GasLimit, Op, Vm,
373    };
374
375    #[test]
376    fn dup_from_1() {
377        let ops = &[
378            Stack::Push(42).into(),
379            Stack::Push(2).into(),
380            Stack::Push(1).into(),
381            Stack::Push(0).into(),
382            Stack::Push(3).into(), // Index `3` should be the `42` value.
383            Stack::DupFrom.into(),
384        ];
385        let op_gas_cost = &|_: &Op| 1;
386        let mut vm = Vm::default();
387        vm.exec_ops(
388            ops,
389            test_access().clone(),
390            &EmptyState,
391            op_gas_cost,
392            GasLimit::UNLIMITED,
393        )
394        .unwrap();
395        assert_eq!(&vm.stack[..], &[42, 2, 1, 0, 42]);
396    }
397
398    #[test]
399    fn dup_from_2() {
400        let ops = &[
401            Stack::Push(3).into(),
402            Stack::Push(2).into(),
403            Stack::Push(1).into(),
404            Stack::Push(42).into(),
405            Stack::Push(0).into(), // Index `0` should be the `42` value.
406            Stack::DupFrom.into(),
407        ];
408        let op_gas_cost = &|_: &Op| 1;
409        let mut vm = Vm::default();
410        vm.exec_ops(
411            ops,
412            test_access().clone(),
413            &EmptyState,
414            op_gas_cost,
415            GasLimit::UNLIMITED,
416        )
417        .unwrap();
418        assert_eq!(&vm.stack[..], &[3, 2, 1, 42, 42]);
419    }
420
421    #[test]
422    fn push1() {
423        let ops = &[Stack::Push(42).into()];
424        let op_gas_cost = &|_: &Op| 1;
425        let mut vm = Vm::default();
426        vm.exec_ops(
427            ops,
428            test_access().clone(),
429            &EmptyState,
430            op_gas_cost,
431            GasLimit::UNLIMITED,
432        )
433        .unwrap();
434        assert_eq!(&vm.stack[..], &[42]);
435    }
436
437    #[test]
438    fn push2_pop_push() {
439        let ops = &[
440            Stack::Push(1).into(),
441            Stack::Push(2).into(),
442            Stack::Pop.into(),
443            Stack::Push(3).into(),
444        ];
445        let op_gas_cost = &|_: &Op| 1;
446        let mut vm = Vm::default();
447        vm.exec_ops(
448            ops,
449            test_access().clone(),
450            &EmptyState,
451            op_gas_cost,
452            GasLimit::UNLIMITED,
453        )
454        .unwrap();
455        assert_eq!(&vm.stack[..], &[1, 3]);
456    }
457
458    #[test]
459    fn pop_empty() {
460        let ops = &[Stack::Pop.into()];
461        let op_gas_cost = &|_: &Op| 1;
462        match Vm::default().exec_ops(
463            ops,
464            test_access().clone(),
465            &EmptyState,
466            op_gas_cost,
467            GasLimit::UNLIMITED,
468        ) {
469            Err(ExecError(0, OpError::Stack(StackError::Empty))) => (),
470            _ => panic!("expected empty stack error"),
471        }
472    }
473
474    #[test]
475    fn index_oob() {
476        let ops = &[Stack::Push(0).into(), Stack::DupFrom.into()];
477        let op_gas_cost = &|_: &Op| 1;
478        match Vm::default().exec_ops(
479            ops,
480            test_access().clone(),
481            &EmptyState,
482            op_gas_cost,
483            GasLimit::UNLIMITED,
484        ) {
485            Err(ExecError(1, OpError::Stack(StackError::IndexOutOfBounds))) => (),
486            _ => panic!("expected index out-of-bounds stack error"),
487        }
488    }
489
490    #[test]
491    fn swap_index() {
492        let ops = &[
493            Stack::Push(3).into(),
494            Stack::Push(4).into(),
495            Stack::Push(5).into(),
496            Stack::Push(42).into(),
497            Stack::Push(2).into(), // Index `2` should be swapped with the `42` value.
498            Stack::SwapIndex.into(),
499        ];
500        let op_gas_cost = &|_: &Op| 1;
501        let mut vm = Vm::default();
502        vm.exec_ops(
503            ops,
504            test_access().clone(),
505            &EmptyState,
506            op_gas_cost,
507            GasLimit::UNLIMITED,
508        )
509        .unwrap();
510        assert_eq!(&vm.stack[..], &[3, 42, 5, 4]);
511    }
512
513    #[test]
514    fn swap_index_oob() {
515        let ops = &[
516            Stack::Push(3).into(),
517            Stack::Push(4).into(),
518            Stack::Push(2).into(), // Index `2` is out of range.
519            Stack::SwapIndex.into(),
520        ];
521        let op_gas_cost = &|_: &Op| 1;
522        match Vm::default().exec_ops(
523            ops,
524            test_access().clone(),
525            &EmptyState,
526            op_gas_cost,
527            GasLimit::UNLIMITED,
528        ) {
529            Err(ExecError(3, OpError::Stack(StackError::IndexOutOfBounds))) => (),
530            _ => panic!("expected index out-of-bounds stack error"),
531        }
532    }
533
534    #[test]
535    fn select() {
536        let ops = &[
537            Stack::Push(3).into(),
538            Stack::Push(4).into(),
539            Stack::Push(1).into(),
540            Stack::Select.into(),
541        ];
542        let op_gas_cost = &|_: &Op| 1;
543        let mut vm = Vm::default();
544        vm.exec_ops(
545            ops,
546            test_access().clone(),
547            &EmptyState,
548            op_gas_cost,
549            GasLimit::UNLIMITED,
550        )
551        .unwrap();
552        assert_eq!(&vm.stack[..], &[4]);
553    }
554
555    #[test]
556    fn select_range_cond_1() {
557        let ops = &[
558            Stack::Push(4).into(),
559            Stack::Push(4).into(),
560            Stack::Push(4).into(),
561            Stack::Push(5).into(),
562            Stack::Push(5).into(),
563            Stack::Push(5).into(),
564            Stack::Push(3).into(), // len
565            Stack::Push(1).into(), // cond
566            Stack::SelectRange.into(),
567        ];
568        let op_gas_cost = &|_: &Op| 1;
569        let mut vm = Vm::default();
570        vm.exec_ops(
571            ops,
572            test_access().clone(),
573            &EmptyState,
574            op_gas_cost,
575            GasLimit::UNLIMITED,
576        )
577        .unwrap();
578        assert_eq!(&vm.stack[..], &[5, 5, 5]);
579    }
580
581    #[test]
582    fn select_range_cond_0() {
583        let ops = &[
584            Stack::Push(4).into(),
585            Stack::Push(4).into(),
586            Stack::Push(4).into(),
587            Stack::Push(5).into(),
588            Stack::Push(5).into(),
589            Stack::Push(5).into(),
590            Stack::Push(3).into(), // len
591            Stack::Push(0).into(), // cond
592            Stack::SelectRange.into(),
593        ];
594        let op_gas_cost = &|_: &Op| 1;
595        let mut vm = Vm::default();
596        vm.exec_ops(
597            ops,
598            test_access().clone(),
599            &EmptyState,
600            op_gas_cost,
601            GasLimit::UNLIMITED,
602        )
603        .unwrap();
604        assert_eq!(&vm.stack[..], &[4, 4, 4]);
605    }
606
607    #[test]
608    fn select_range_cond_invalid() {
609        let ops = &[
610            Stack::Push(4).into(),
611            Stack::Push(5).into(),
612            Stack::Push(1).into(),  // len
613            Stack::Push(42).into(), // cond
614            Stack::SelectRange.into(),
615        ];
616        let op_gas_cost = &|_: &Op| 1;
617        match Vm::default().exec_ops(
618            ops,
619            test_access().clone(),
620            &EmptyState,
621            op_gas_cost,
622            GasLimit::UNLIMITED,
623        ) {
624            Err(ExecError(4, OpError::Stack(StackError::InvalidCondition(42)))) => (),
625            _ => panic!("expected invalid condition stack error"),
626        }
627    }
628
629    #[test]
630    fn select_range_len_0() {
631        let ops = &[
632            Stack::Push(4).into(),
633            Stack::Push(5).into(),
634            Stack::Push(0).into(), // len
635            Stack::Push(0).into(), // cond
636            Stack::SelectRange.into(),
637        ];
638        let op_gas_cost = &|_: &Op| 1;
639        let mut vm = Vm::default();
640        vm.exec_ops(
641            ops,
642            test_access().clone(),
643            &EmptyState,
644            op_gas_cost,
645            GasLimit::UNLIMITED,
646        )
647        .unwrap();
648        assert_eq!(&vm.stack[..], &[4, 5]);
649    }
650
651    #[test]
652    fn select_range_len_negative() {
653        let ops = &[
654            Stack::Push(-42).into(), // len
655            Stack::Push(0).into(),   // cond
656            Stack::SelectRange.into(),
657        ];
658        let op_gas_cost = &|_: &Op| 1;
659        match Vm::default().exec_ops(
660            ops,
661            test_access().clone(),
662            &EmptyState,
663            op_gas_cost,
664            GasLimit::UNLIMITED,
665        ) {
666            Err(ExecError(2, OpError::Stack(StackError::IndexOutOfBounds))) => (),
667            _ => panic!("expected index out of bounds stack error"),
668        }
669    }
670
671    #[test]
672    fn select_range_len_too_big() {
673        let ops = &[
674            Stack::Push(4).into(),
675            Stack::Push(4).into(),
676            Stack::Push(5).into(),
677            Stack::Push(2).into(), // len
678            Stack::Push(0).into(), // cond
679            Stack::SelectRange.into(),
680        ];
681        let op_gas_cost = &|_: &Op| 1;
682        match Vm::default().exec_ops(
683            ops,
684            test_access().clone(),
685            &EmptyState,
686            op_gas_cost,
687            GasLimit::UNLIMITED,
688        ) {
689            Err(ExecError(5, OpError::Stack(StackError::IndexOutOfBounds))) => (),
690            _ => panic!("expected index out of bounds stack error"),
691        }
692    }
693}