1use 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#[derive(Clone, Debug, PartialEq, Default)]
17pub struct Stack(Vec<Word>);
18
19impl Stack {
20 pub const SIZE_LIMIT: usize = 4096;
22
23 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 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 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 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 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 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 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 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 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 self.len()
137 .checked_sub(len.checked_mul(2).ok_or(StackError::IndexOutOfBounds)?)
138 .ok_or(StackError::IndexOutOfBounds)?;
139 let arr_b_index = self.len() - len;
141 if cond {
142 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 self.0.truncate(arr_b_index);
149 Ok(())
150 }
151
152 pub fn pop(&mut self) -> StackResult<Word> {
154 self.0.pop().ok_or(StackError::Empty)
155 }
156
157 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 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 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 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 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 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 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 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 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 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 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 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 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 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 pub fn reserve(&mut self, additional: usize) {
316 self.0.reserve(additional);
317 }
318}
319
320fn 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(), 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(), 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(), 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(), 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(), Stack::Push(1).into(), 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(), Stack::Push(0).into(), 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(), Stack::Push(42).into(), 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(), Stack::Push(0).into(), 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(), Stack::Push(0).into(), 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(), Stack::Push(0).into(), 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}