triton_isa/
op_stack.rs

1use std::fmt::Display;
2use std::fmt::Formatter;
3use std::fmt::Result as FmtResult;
4use std::num::TryFromIntError;
5use std::ops::Index;
6use std::ops::IndexMut;
7
8use arbitrary::Arbitrary;
9use get_size2::GetSize;
10use itertools::Itertools;
11use serde::Deserialize;
12use serde::Serialize;
13use strum::EnumCount;
14use strum::EnumIter;
15use strum::IntoEnumIterator;
16use thiserror::Error;
17use twenty_first::prelude::*;
18
19type Result<T> = std::result::Result<T, OpStackError>;
20type OpStackElementResult<T> = std::result::Result<T, OpStackElementError>;
21type NumWordsResult<T> = std::result::Result<T, NumberOfWordsError>;
22
23/// The number of registers dedicated to the top of the operational stack.
24pub const NUM_OP_STACK_REGISTERS: usize = OpStackElement::COUNT;
25
26/// The operational stack of Triton VM.
27/// It always contains at least [`OpStackElement::COUNT`] elements. Initially, the bottom-most
28/// [`Digest::LEN`] elements equal the digest of the program being executed.
29/// The remaining elements are initially 0.
30///
31/// The OpStack is represented as one contiguous piece of memory, and Triton VM uses it as such.
32/// For reasons of arithmetization, however, there is a distinction between the op-stack registers
33/// and the op-stack underflow memory. The op-stack registers are the first
34/// [`OpStackElement::COUNT`] elements of the op-stack, and the op-stack underflow memory is the
35/// remaining elements.
36#[derive(Debug, Clone, Eq, PartialEq, Serialize, Deserialize, Arbitrary)]
37pub struct OpStack {
38    /// The underlying, actual stack. When manually accessing, be aware of reversed indexing:
39    /// while `op_stack[0]` is the top of the stack, `op_stack.stack[0]` is the lowest element in
40    /// the stack.
41    pub stack: Vec<BFieldElement>,
42
43    underflow_io_sequence: Vec<UnderflowIO>,
44}
45
46#[non_exhaustive]
47#[derive(Debug, Copy, Clone, Eq, PartialEq, Error)]
48pub enum OpStackError {
49    #[error("operational stack is too shallow")]
50    TooShallow,
51
52    #[error("failed to convert BFieldElement {0} into u32")]
53    FailedU32Conversion(BFieldElement),
54}
55
56impl OpStack {
57    pub fn new(program_digest: Digest) -> Self {
58        let mut stack = bfe_vec![0; OpStackElement::COUNT];
59
60        let reverse_digest = program_digest.reversed().values();
61        stack[..Digest::LEN].copy_from_slice(&reverse_digest);
62
63        Self {
64            stack,
65            underflow_io_sequence: vec![],
66        }
67    }
68
69    // If the op stack is empty, things have gone horribly wrong. Suppressing this
70    // lint is preferred to implementing a basically useless `is_empty()`.
71    #[expect(clippy::len_without_is_empty)]
72    pub fn len(&self) -> usize {
73        self.stack.len()
74    }
75
76    pub fn push(&mut self, element: BFieldElement) {
77        self.stack.push(element);
78        self.record_underflow_io(UnderflowIO::Write);
79    }
80
81    pub fn pop(&mut self) -> Result<BFieldElement> {
82        self.record_underflow_io(UnderflowIO::Read);
83        self.stack.pop().ok_or(OpStackError::TooShallow)
84    }
85
86    pub fn insert(&mut self, index: OpStackElement, element: BFieldElement) {
87        let insertion_index = self.len() - usize::from(index);
88        self.stack.insert(insertion_index, element);
89        self.record_underflow_io(UnderflowIO::Write);
90    }
91
92    pub fn remove(&mut self, index: OpStackElement) -> BFieldElement {
93        self.record_underflow_io(UnderflowIO::Read);
94        let top_of_stack = self.len() - 1;
95        let index = top_of_stack - usize::from(index);
96        self.stack.remove(index)
97    }
98
99    fn record_underflow_io(&mut self, io_type: fn(BFieldElement) -> UnderflowIO) {
100        let underflow_io = io_type(self.first_underflow_element());
101        self.underflow_io_sequence.push(underflow_io);
102    }
103
104    pub fn start_recording_underflow_io_sequence(&mut self) {
105        self.underflow_io_sequence.clear();
106    }
107
108    pub fn stop_recording_underflow_io_sequence(&mut self) -> Vec<UnderflowIO> {
109        self.underflow_io_sequence.drain(..).collect()
110    }
111
112    pub fn push_extension_field_element(&mut self, element: XFieldElement) {
113        for coefficient in element.coefficients.into_iter().rev() {
114            self.push(coefficient);
115        }
116    }
117
118    pub fn pop_extension_field_element(&mut self) -> Result<XFieldElement> {
119        let coefficients = self.pop_multiple()?;
120        Ok(xfe!(coefficients))
121    }
122
123    pub fn is_u32(&self, stack_element: OpStackElement) -> Result<()> {
124        self.get_u32(stack_element).map(|_| ())
125    }
126
127    pub fn get_u32(&self, stack_element: OpStackElement) -> Result<u32> {
128        let element = self[stack_element];
129        element
130            .try_into()
131            .map_err(|_| OpStackError::FailedU32Conversion(element))
132    }
133
134    pub fn pop_u32(&mut self) -> Result<u32> {
135        let element = self.pop()?;
136        element
137            .try_into()
138            .map_err(|_| OpStackError::FailedU32Conversion(element))
139    }
140
141    pub fn pop_multiple<const N: usize>(&mut self) -> Result<[BFieldElement; N]> {
142        let mut elements = bfe_array![0; N];
143        for element in &mut elements {
144            *element = self.pop()?;
145        }
146        Ok(elements)
147    }
148
149    pub fn peek_at_top_extension_field_element(&self) -> XFieldElement {
150        xfe!([self[0], self[1], self[2]])
151    }
152
153    pub fn would_be_too_shallow(&self, stack_delta: i32) -> bool {
154        self.len() as i32 + stack_delta < OpStackElement::COUNT as i32
155    }
156
157    /// The address of the next free address of the op-stack. Equivalent to the current length of
158    /// the op-stack.
159    pub fn pointer(&self) -> BFieldElement {
160        u64::try_from(self.len()).unwrap().into()
161    }
162
163    /// The first element of the op-stack underflow memory, or 0 if the op-stack underflow memory
164    /// is empty.
165    pub(crate) fn first_underflow_element(&self) -> BFieldElement {
166        let default = bfe!(0);
167        let Some(top_of_stack_index) = self.len().checked_sub(1) else {
168            return default;
169        };
170        let Some(underflow_start) = top_of_stack_index.checked_sub(OpStackElement::COUNT) else {
171            return default;
172        };
173        self.stack.get(underflow_start).copied().unwrap_or(default)
174    }
175}
176
177impl Index<usize> for OpStack {
178    type Output = BFieldElement;
179
180    fn index(&self, index: usize) -> &Self::Output {
181        let top_of_stack = self.len() - 1;
182        &self.stack[top_of_stack - index]
183    }
184}
185
186impl IndexMut<usize> for OpStack {
187    fn index_mut(&mut self, index: usize) -> &mut Self::Output {
188        let top_of_stack = self.len() - 1;
189        &mut self.stack[top_of_stack - index]
190    }
191}
192
193impl Index<OpStackElement> for OpStack {
194    type Output = BFieldElement;
195
196    fn index(&self, stack_element: OpStackElement) -> &Self::Output {
197        &self[usize::from(stack_element)]
198    }
199}
200
201impl IndexMut<OpStackElement> for OpStack {
202    fn index_mut(&mut self, stack_element: OpStackElement) -> &mut Self::Output {
203        &mut self[usize::from(stack_element)]
204    }
205}
206
207impl IntoIterator for OpStack {
208    type Item = BFieldElement;
209    type IntoIter = std::vec::IntoIter<Self::Item>;
210
211    fn into_iter(self) -> Self::IntoIter {
212        let mut stack = self.stack;
213        stack.reverse();
214        stack.into_iter()
215    }
216}
217
218/// Indicates changes to the op-stack underflow memory.
219#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash, Serialize, Deserialize, GetSize, Arbitrary)]
220#[must_use = "The change to underflow memory should be handled."]
221pub enum UnderflowIO {
222    Read(BFieldElement),
223    Write(BFieldElement),
224}
225
226impl UnderflowIO {
227    /// Remove spurious read/write sequences arising from temporary stack changes.
228    ///
229    /// For example, the sequence `[Read(5), Write(5), Read(7)]` can be replaced with `[Read(7)]`.
230    /// Similarly, the sequence `[Write(5), Write(3), Read(3), Read(5), Write(7)]` can be replaced
231    /// with `[Write(7)]`.
232    pub fn canonicalize_sequence(sequence: &mut Vec<Self>) {
233        while let Some(index) = Self::index_of_dual_pair(sequence) {
234            let _ = sequence.remove(index);
235            let _ = sequence.remove(index);
236        }
237    }
238
239    fn index_of_dual_pair(sequence: &[Self]) -> Option<usize> {
240        sequence
241            .iter()
242            .tuple_windows()
243            .find_position(|(&left, &right)| left.is_dual_to(right))
244            .map(|(index, _)| index)
245    }
246
247    fn is_dual_to(&self, other: Self) -> bool {
248        match (self, other) {
249            (&Self::Read(read), Self::Write(write)) => read == write,
250            (&Self::Write(write), Self::Read(read)) => read == write,
251            _ => false,
252        }
253    }
254
255    /// Whether the sequence of underflow IOs consists of either only reads or only writes.
256    pub fn is_uniform_sequence(sequence: &[Self]) -> bool {
257        sequence.iter().all(|io| io.is_same_type_as(sequence[0]))
258    }
259
260    fn is_same_type_as(&self, other: Self) -> bool {
261        matches!(
262            (self, other),
263            (&Self::Read(_), Self::Read(_)) | (&Self::Write(_), Self::Write(_))
264        )
265    }
266
267    /// Whether the sequence of underflow IOs consists of only writes.
268    pub fn is_writing_sequence(sequence: &[Self]) -> bool {
269        sequence.iter().all(|io| io.grows_stack())
270    }
271
272    /// Whether the sequence of underflow IOs consists of only reads.
273    pub fn is_reading_sequence(sequence: &[Self]) -> bool {
274        sequence.iter().all(|io| io.shrinks_stack())
275    }
276
277    pub fn shrinks_stack(&self) -> bool {
278        match self {
279            Self::Read(_) => true,
280            Self::Write(_) => false,
281        }
282    }
283
284    pub fn grows_stack(&self) -> bool {
285        match self {
286            Self::Read(_) => false,
287            Self::Write(_) => true,
288        }
289    }
290
291    pub fn payload(self) -> BFieldElement {
292        match self {
293            Self::Read(payload) => payload,
294            Self::Write(payload) => payload,
295        }
296    }
297}
298
299/// Represents the [`OpStack`] registers directly accessible by Triton VM.
300#[derive(
301    Debug,
302    Default,
303    Copy,
304    Clone,
305    Eq,
306    PartialEq,
307    Ord,
308    PartialOrd,
309    Hash,
310    Serialize,
311    Deserialize,
312    EnumCount,
313    EnumIter,
314    GetSize,
315    Arbitrary,
316)]
317pub enum OpStackElement {
318    #[default]
319    ST0,
320    ST1,
321    ST2,
322    ST3,
323    ST4,
324    ST5,
325    ST6,
326    ST7,
327    ST8,
328    ST9,
329    ST10,
330    ST11,
331    ST12,
332    ST13,
333    ST14,
334    ST15,
335}
336
337#[non_exhaustive]
338#[derive(Debug, Copy, Clone, Eq, PartialEq, Error)]
339pub enum OpStackElementError {
340    #[error("index {0} is out of range for `OpStackElement`")]
341    IndexOutOfBounds(u32),
342
343    #[error(transparent)]
344    FailedIntegerConversion(#[from] TryFromIntError),
345}
346
347impl OpStackElement {
348    pub const fn index(self) -> u32 {
349        match self {
350            OpStackElement::ST0 => 0,
351            OpStackElement::ST1 => 1,
352            OpStackElement::ST2 => 2,
353            OpStackElement::ST3 => 3,
354            OpStackElement::ST4 => 4,
355            OpStackElement::ST5 => 5,
356            OpStackElement::ST6 => 6,
357            OpStackElement::ST7 => 7,
358            OpStackElement::ST8 => 8,
359            OpStackElement::ST9 => 9,
360            OpStackElement::ST10 => 10,
361            OpStackElement::ST11 => 11,
362            OpStackElement::ST12 => 12,
363            OpStackElement::ST13 => 13,
364            OpStackElement::ST14 => 14,
365            OpStackElement::ST15 => 15,
366        }
367    }
368}
369
370impl Display for OpStackElement {
371    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
372        let index = self.index();
373        write!(f, "{index}")
374    }
375}
376
377impl From<OpStackElement> for u32 {
378    fn from(stack_element: OpStackElement) -> Self {
379        stack_element.index()
380    }
381}
382
383impl From<&OpStackElement> for u32 {
384    fn from(&stack_element: &OpStackElement) -> Self {
385        stack_element.into()
386    }
387}
388
389impl TryFrom<u32> for OpStackElement {
390    type Error = OpStackElementError;
391
392    fn try_from(stack_index: u32) -> OpStackElementResult<Self> {
393        match stack_index {
394            0 => Ok(OpStackElement::ST0),
395            1 => Ok(OpStackElement::ST1),
396            2 => Ok(OpStackElement::ST2),
397            3 => Ok(OpStackElement::ST3),
398            4 => Ok(OpStackElement::ST4),
399            5 => Ok(OpStackElement::ST5),
400            6 => Ok(OpStackElement::ST6),
401            7 => Ok(OpStackElement::ST7),
402            8 => Ok(OpStackElement::ST8),
403            9 => Ok(OpStackElement::ST9),
404            10 => Ok(OpStackElement::ST10),
405            11 => Ok(OpStackElement::ST11),
406            12 => Ok(OpStackElement::ST12),
407            13 => Ok(OpStackElement::ST13),
408            14 => Ok(OpStackElement::ST14),
409            15 => Ok(OpStackElement::ST15),
410            _ => Err(Self::Error::IndexOutOfBounds(stack_index)),
411        }
412    }
413}
414
415impl From<OpStackElement> for u64 {
416    fn from(stack_element: OpStackElement) -> Self {
417        u32::from(stack_element).into()
418    }
419}
420
421impl TryFrom<u64> for OpStackElement {
422    type Error = OpStackElementError;
423
424    fn try_from(stack_index: u64) -> OpStackElementResult<Self> {
425        u32::try_from(stack_index)?.try_into()
426    }
427}
428
429impl From<OpStackElement> for usize {
430    fn from(stack_element: OpStackElement) -> Self {
431        u32::from(stack_element) as usize
432    }
433}
434
435impl From<&OpStackElement> for usize {
436    fn from(&stack_element: &OpStackElement) -> Self {
437        stack_element.into()
438    }
439}
440
441impl From<OpStackElement> for i32 {
442    fn from(stack_element: OpStackElement) -> Self {
443        u32::from(stack_element) as i32
444    }
445}
446
447impl From<&OpStackElement> for i32 {
448    fn from(&stack_element: &OpStackElement) -> Self {
449        stack_element.into()
450    }
451}
452
453impl TryFrom<i32> for OpStackElement {
454    type Error = OpStackElementError;
455
456    fn try_from(stack_index: i32) -> OpStackElementResult<Self> {
457        u32::try_from(stack_index)?.try_into()
458    }
459}
460
461impl TryFrom<usize> for OpStackElement {
462    type Error = OpStackElementError;
463
464    fn try_from(stack_index: usize) -> OpStackElementResult<Self> {
465        u32::try_from(stack_index)?.try_into()
466    }
467}
468
469impl From<OpStackElement> for BFieldElement {
470    fn from(stack_element: OpStackElement) -> Self {
471        u32::from(stack_element).into()
472    }
473}
474
475impl From<&OpStackElement> for BFieldElement {
476    fn from(&stack_element: &OpStackElement) -> Self {
477        stack_element.into()
478    }
479}
480
481impl TryFrom<BFieldElement> for OpStackElement {
482    type Error = OpStackElementError;
483
484    fn try_from(stack_index: BFieldElement) -> OpStackElementResult<Self> {
485        u32::try_from(stack_index)?.try_into()
486    }
487}
488
489/// Represents the argument, _i.e._, the `n`, for instructions like `pop n` or `read_io n`.
490#[derive(
491    Debug,
492    Default,
493    Copy,
494    Clone,
495    Eq,
496    PartialEq,
497    Ord,
498    PartialOrd,
499    Hash,
500    Serialize,
501    Deserialize,
502    EnumCount,
503    EnumIter,
504    GetSize,
505    Arbitrary,
506)]
507pub enum NumberOfWords {
508    #[default]
509    N1,
510    N2,
511    N3,
512    N4,
513    N5,
514}
515
516#[non_exhaustive]
517#[derive(Debug, Copy, Clone, Eq, PartialEq, Error)]
518pub enum NumberOfWordsError {
519    #[error("index {0} is out of range for `NumberOfWords`")]
520    IndexOutOfBounds(usize),
521
522    #[error(transparent)]
523    FailedIntegerConversion(#[from] TryFromIntError),
524}
525
526impl NumberOfWords {
527    pub const fn num_words(self) -> usize {
528        match self {
529            Self::N1 => 1,
530            Self::N2 => 2,
531            Self::N3 => 3,
532            Self::N4 => 4,
533            Self::N5 => 5,
534        }
535    }
536
537    pub fn legal_values() -> [usize; Self::COUNT] {
538        let legal_indices = Self::iter().map(|n| n.num_words()).collect_vec();
539        legal_indices.try_into().unwrap()
540    }
541
542    pub fn illegal_values() -> [usize; OpStackElement::COUNT - Self::COUNT] {
543        let all_values = OpStackElement::iter().map(|st| st.index() as usize);
544        let illegal_values = all_values
545            .filter(|i| !Self::legal_values().contains(i))
546            .collect_vec();
547        illegal_values.try_into().unwrap()
548    }
549}
550
551impl Display for NumberOfWords {
552    fn fmt(&self, f: &mut Formatter<'_>) -> FmtResult {
553        write!(f, "{}", self.num_words())
554    }
555}
556
557impl From<NumberOfWords> for usize {
558    fn from(num_words: NumberOfWords) -> Self {
559        num_words.num_words()
560    }
561}
562
563impl From<&NumberOfWords> for usize {
564    fn from(&num_words: &NumberOfWords) -> Self {
565        num_words.into()
566    }
567}
568
569impl From<NumberOfWords> for u32 {
570    fn from(num_words: NumberOfWords) -> Self {
571        num_words.num_words() as u32
572    }
573}
574
575impl From<&NumberOfWords> for u32 {
576    fn from(&num_words: &NumberOfWords) -> Self {
577        num_words.into()
578    }
579}
580
581impl From<NumberOfWords> for u64 {
582    fn from(num_words: NumberOfWords) -> Self {
583        u32::from(num_words).into()
584    }
585}
586
587impl From<&NumberOfWords> for u64 {
588    fn from(&num_words: &NumberOfWords) -> Self {
589        num_words.into()
590    }
591}
592
593impl From<NumberOfWords> for OpStackElement {
594    fn from(num_words: NumberOfWords) -> Self {
595        OpStackElement::try_from(num_words.num_words()).unwrap()
596    }
597}
598
599impl From<&NumberOfWords> for OpStackElement {
600    fn from(&num_words: &NumberOfWords) -> Self {
601        num_words.into()
602    }
603}
604
605impl From<NumberOfWords> for BFieldElement {
606    fn from(num_words: NumberOfWords) -> Self {
607        u32::from(num_words).into()
608    }
609}
610
611impl From<&NumberOfWords> for BFieldElement {
612    fn from(&num_words: &NumberOfWords) -> Self {
613        num_words.into()
614    }
615}
616
617impl TryFrom<usize> for NumberOfWords {
618    type Error = NumberOfWordsError;
619
620    fn try_from(index: usize) -> NumWordsResult<Self> {
621        match index {
622            1 => Ok(Self::N1),
623            2 => Ok(Self::N2),
624            3 => Ok(Self::N3),
625            4 => Ok(Self::N4),
626            5 => Ok(Self::N5),
627            _ => Err(Self::Error::IndexOutOfBounds(index)),
628        }
629    }
630}
631
632impl TryFrom<u32> for NumberOfWords {
633    type Error = NumberOfWordsError;
634
635    fn try_from(index: u32) -> NumWordsResult<Self> {
636        usize::try_from(index)?.try_into()
637    }
638}
639
640impl TryFrom<i32> for NumberOfWords {
641    type Error = NumberOfWordsError;
642
643    fn try_from(index: i32) -> NumWordsResult<Self> {
644        usize::try_from(index)?.try_into()
645    }
646}
647
648impl TryFrom<OpStackElement> for NumberOfWords {
649    type Error = NumberOfWordsError;
650
651    fn try_from(index: OpStackElement) -> NumWordsResult<Self> {
652        usize::from(index).try_into()
653    }
654}
655
656impl TryFrom<u64> for NumberOfWords {
657    type Error = NumberOfWordsError;
658
659    fn try_from(index: u64) -> NumWordsResult<Self> {
660        usize::try_from(index)?.try_into()
661    }
662}
663
664impl TryFrom<BFieldElement> for NumberOfWords {
665    type Error = NumberOfWordsError;
666
667    fn try_from(index: BFieldElement) -> NumWordsResult<Self> {
668        u32::try_from(index)?.try_into()
669    }
670}
671
672impl TryFrom<&BFieldElement> for NumberOfWords {
673    type Error = NumberOfWordsError;
674
675    fn try_from(&index: &BFieldElement) -> NumWordsResult<Self> {
676        index.try_into()
677    }
678}
679
680#[cfg(test)]
681mod tests {
682    use assert2::assert;
683    use assert2::let_assert;
684    use proptest::collection::vec;
685    use proptest::prelude::*;
686    use proptest_arbitrary_interop::arb;
687    use strum::IntoEnumIterator;
688    use test_strategy::proptest;
689
690    use super::*;
691
692    impl Default for OpStack {
693        /// For testing purposes only.
694        fn default() -> Self {
695            OpStack::new(Digest::default())
696        }
697    }
698
699    #[test]
700    fn sanity() {
701        let mut op_stack = OpStack::default();
702
703        // verify height
704        assert!(op_stack.len() == 16);
705        assert!(op_stack.pointer().value() as usize == op_stack.len());
706
707        // push elements 1 through 17
708        for i in 1..=17 {
709            op_stack.push(bfe!(i));
710        }
711
712        // verify height
713        assert!(op_stack.len() == 33);
714        assert!(op_stack.pointer().value() as usize == op_stack.len());
715
716        assert!([
717            op_stack[OpStackElement::ST0],
718            op_stack[OpStackElement::ST1],
719            op_stack[OpStackElement::ST2],
720            op_stack[OpStackElement::ST3],
721            op_stack[OpStackElement::ST4],
722            op_stack[OpStackElement::ST5],
723            op_stack[OpStackElement::ST6],
724            op_stack[OpStackElement::ST7],
725            op_stack[OpStackElement::ST8],
726            op_stack[OpStackElement::ST9],
727            op_stack[OpStackElement::ST10],
728            op_stack[OpStackElement::ST11],
729            op_stack[OpStackElement::ST12],
730            op_stack[OpStackElement::ST13],
731            op_stack[OpStackElement::ST14],
732            op_stack[OpStackElement::ST15],
733            op_stack.first_underflow_element(),
734        ]
735        .into_iter()
736        .all_unique());
737
738        // pop 11 elements
739        for _ in 0..11 {
740            let _ = op_stack.pop().unwrap();
741        }
742
743        // verify height
744        assert!(op_stack.len() == 22);
745        assert!(op_stack.pointer().value() as usize == op_stack.len());
746
747        // pop 2 XFieldElements
748        let _ = op_stack.pop_extension_field_element().unwrap();
749        let _ = op_stack.pop_extension_field_element().unwrap();
750
751        // verify height
752        assert!(op_stack.len() == 16);
753        assert!(op_stack.pointer().value() as usize == op_stack.len());
754
755        // verify underflow
756        assert!(op_stack.would_be_too_shallow(-1));
757    }
758
759    #[proptest]
760    fn turning_op_stack_into_iterator_gives_top_element_first(
761        #[strategy(arb())]
762        #[filter(#op_stack.len() > 0)]
763        op_stack: OpStack,
764    ) {
765        let top_element = op_stack[OpStackElement::ST0];
766        let mut iterator = op_stack.into_iter();
767        assert!(top_element == iterator.next().unwrap());
768    }
769
770    #[test]
771    fn trying_to_access_first_underflow_element_never_panics() {
772        let mut op_stack = OpStack::default();
773        let way_too_long = 2 * op_stack.len();
774        for _ in 0..way_too_long {
775            let _ = op_stack.pop();
776            let _ = op_stack.first_underflow_element();
777        }
778    }
779
780    #[test]
781    fn conversion_from_stack_element_to_u32_and_back_is_identity() {
782        for stack_element in OpStackElement::iter() {
783            let stack_index = u32::from(stack_element);
784            let_assert!(Ok(stack_element_again) = OpStackElement::try_from(stack_index));
785            assert!(stack_element == stack_element_again);
786        }
787    }
788
789    #[test]
790    fn conversion_from_stack_element_to_i32_and_back_is_identity() {
791        for stack_element in OpStackElement::iter() {
792            let stack_index = i32::from(stack_element);
793            let_assert!(Ok(stack_element_again) = OpStackElement::try_from(stack_index));
794            assert!(stack_element == stack_element_again);
795        }
796    }
797
798    #[test]
799    fn canonicalize_empty_underflow_io_sequence() {
800        let mut sequence = vec![];
801        UnderflowIO::canonicalize_sequence(&mut sequence);
802
803        let expected_sequence = Vec::<UnderflowIO>::new();
804        assert!(expected_sequence == sequence);
805    }
806
807    #[test]
808    fn canonicalize_simple_underflow_io_sequence() {
809        let mut sequence = vec![
810            UnderflowIO::Read(bfe!(5)),
811            UnderflowIO::Write(bfe!(5)),
812            UnderflowIO::Read(bfe!(7)),
813        ];
814        UnderflowIO::canonicalize_sequence(&mut sequence);
815
816        let expected_sequence = vec![UnderflowIO::Read(bfe!(7))];
817        assert!(expected_sequence == sequence);
818    }
819
820    #[test]
821    fn canonicalize_medium_complex_underflow_io_sequence() {
822        let mut sequence = vec![
823            UnderflowIO::Write(bfe!(5)),
824            UnderflowIO::Write(bfe!(3)),
825            UnderflowIO::Read(bfe!(3)),
826            UnderflowIO::Read(bfe!(5)),
827            UnderflowIO::Write(bfe!(7)),
828        ];
829        UnderflowIO::canonicalize_sequence(&mut sequence);
830
831        let expected_sequence = vec![UnderflowIO::Write(bfe!(7))];
832        assert!(expected_sequence == sequence);
833    }
834
835    #[proptest]
836    fn underflow_io_either_shrinks_stack_or_grows_stack(
837        #[strategy(arb())] underflow_io: UnderflowIO,
838    ) {
839        let shrinks_stack = underflow_io.shrinks_stack();
840        let grows_stack = underflow_io.grows_stack();
841        assert!(shrinks_stack ^ grows_stack);
842    }
843
844    #[test]
845    fn empty_underflow_io_sequence_does_not_crash_uniformity_test() {
846        assert!(UnderflowIO::is_uniform_sequence(&[]));
847    }
848
849    #[proptest]
850    fn non_empty_uniform_underflow_io_sequence_is_either_reading_or_writing(
851        #[strategy(vec(arb(), 1..OpStackElement::COUNT))] sequence: Vec<UnderflowIO>,
852    ) {
853        let is_reading_sequence = UnderflowIO::is_reading_sequence(&sequence);
854        let is_writing_sequence = UnderflowIO::is_writing_sequence(&sequence);
855        if UnderflowIO::is_uniform_sequence(&sequence) {
856            prop_assert!(is_reading_sequence ^ is_writing_sequence);
857        } else {
858            prop_assert!(!is_reading_sequence);
859            prop_assert!(!is_writing_sequence);
860        }
861    }
862
863    #[test]
864    fn conversion_from_number_of_words_to_usize_and_back_is_identity() {
865        for num_words in NumberOfWords::iter() {
866            let stack_index = usize::from(num_words);
867            let_assert!(Ok(num_words_again) = NumberOfWords::try_from(stack_index));
868            assert!(num_words == num_words_again);
869        }
870    }
871
872    #[test]
873    fn conversion_from_number_of_words_to_u64_and_back_is_identity() {
874        for num_words in NumberOfWords::iter() {
875            let stack_index = u64::from(num_words);
876            let_assert!(Ok(num_words_again) = NumberOfWords::try_from(stack_index));
877            assert!(num_words == num_words_again);
878        }
879    }
880
881    #[test]
882    fn conversion_from_number_of_words_to_op_stack_element_and_back_is_identity() {
883        for num_words in NumberOfWords::iter() {
884            let stack_element = OpStackElement::from(num_words);
885            let_assert!(Ok(num_words_again) = NumberOfWords::try_from(stack_element));
886            assert!(num_words == num_words_again);
887        }
888    }
889
890    #[test]
891    fn convert_from_various_primitive_types_to_op_stack_element() {
892        assert!(let Ok(_) = OpStackElement::try_from(0_u32));
893        assert!(let Ok(_) = OpStackElement::try_from(0_u64));
894        assert!(let Ok(_) = OpStackElement::try_from(0_usize));
895        assert!(let Ok(_) = OpStackElement::try_from(0_i32));
896        assert!(let Ok(_) = OpStackElement::try_from(bfe!(0)));
897    }
898
899    #[test]
900    fn convert_from_various_primitive_types_to_number_of_words() {
901        assert!(let Ok(_) = NumberOfWords::try_from(1_u32));
902        assert!(let Ok(_) = NumberOfWords::try_from(1_u64));
903        assert!(let Ok(_) = NumberOfWords::try_from(1_usize));
904        assert!(let Ok(_) = NumberOfWords::try_from(bfe!(1)));
905        assert!(let Ok(_) = NumberOfWords::try_from(OpStackElement::ST1));
906    }
907
908    #[test]
909    fn convert_from_op_stack_element_to_various_primitive_types() {
910        let _ = u32::from(OpStackElement::ST0);
911        let _ = u64::from(OpStackElement::ST0);
912        let _ = usize::from(OpStackElement::ST0);
913        let _ = i32::from(OpStackElement::ST0);
914        let _ = BFieldElement::from(OpStackElement::ST0);
915        let _ = bfe!(OpStackElement::ST0);
916
917        let _ = u32::from(&OpStackElement::ST0);
918        let _ = usize::from(&OpStackElement::ST0);
919        let _ = i32::from(&OpStackElement::ST0);
920        let _ = BFieldElement::from(&OpStackElement::ST0);
921        let _ = bfe!(&OpStackElement::ST0);
922    }
923
924    #[test]
925    fn convert_from_number_of_words_to_various_primitive_types() {
926        let n1 = NumberOfWords::N1;
927
928        let _ = u32::from(n1);
929        let _ = u64::from(n1);
930        let _ = usize::from(n1);
931        let _ = BFieldElement::from(n1);
932        let _ = OpStackElement::from(n1);
933        let _ = bfe!(n1);
934
935        let _ = u32::from(&n1);
936        let _ = u64::from(&n1);
937        let _ = usize::from(&n1);
938        let _ = BFieldElement::from(&n1);
939        let _ = OpStackElement::from(&n1);
940        let _ = bfe!(&n1);
941    }
942
943    #[proptest]
944    fn out_of_range_op_stack_element_gives_error(
945        #[strategy(arb())]
946        #[filter(!OpStackElement::iter().map(|o| o.index()).contains(&(#index.value() as u32)))]
947        index: BFieldElement,
948    ) {
949        assert!(let Err(_) = OpStackElement::try_from(index));
950    }
951
952    #[proptest]
953    fn out_of_range_number_of_words_gives_error(
954        #[strategy(arb())]
955        #[filter(!NumberOfWords::legal_values().contains(&(#index.value() as usize)))]
956        index: BFieldElement,
957    ) {
958        assert!(let Err(_) = NumberOfWords::try_from(&index));
959    }
960
961    #[test]
962    fn number_of_words_to_b_field_element_gives_expected_range() {
963        let computed_range = NumberOfWords::iter()
964            .map(|num_words| bfe!(num_words).value())
965            .collect_vec();
966        let expected_range = (1..=5).collect_vec();
967        assert!(computed_range == expected_range);
968    }
969
970    #[test]
971    fn number_of_legal_number_of_words_corresponds_to_distinct_number_of_number_of_words() {
972        let legal_values = NumberOfWords::legal_values();
973        let num_distinct_values = NumberOfWords::COUNT;
974        assert!(num_distinct_values == legal_values.len());
975    }
976
977    #[test]
978    fn compute_illegal_values_of_number_of_words() {
979        let _ = NumberOfWords::illegal_values();
980    }
981
982    #[proptest]
983    fn invalid_u32s_cannot_be_retrieved_as_u32s(
984        #[strategy(arb())] st: OpStackElement,
985        #[strategy(u64::from(u32::MAX) + 1..)] non_u32: u64,
986    ) {
987        let mut op_stack = OpStack::default();
988        op_stack[st] = non_u32.into();
989
990        assert!(let Err(_) = op_stack.is_u32(st));
991        assert!(let Err(_) = op_stack.get_u32(st));
992    }
993
994    #[proptest]
995    fn valid_u32s_can_be_retrieved_as_u32s(#[strategy(arb())] st: OpStackElement, valid_u32: u32) {
996        let mut op_stack = OpStack::default();
997        op_stack[st] = valid_u32.into();
998
999        assert!(let Ok(()) = op_stack.is_u32(st));
1000        let_assert!(Ok(some_u32) = op_stack.get_u32(st));
1001        assert!(valid_u32 == some_u32);
1002    }
1003
1004    #[proptest]
1005    fn inserting_an_element_into_the_stack_puts_it_at_the_correct_position(
1006        #[strategy(arb())] insertion_index: OpStackElement,
1007        #[strategy(arb())] insertion_element: BFieldElement,
1008    ) {
1009        let mut op_stack = OpStack::default();
1010        op_stack.insert(insertion_index, insertion_element);
1011        prop_assert_eq!(insertion_element, op_stack[insertion_index]);
1012
1013        let expected_len = OpStackElement::COUNT + 1;
1014        prop_assert_eq!(expected_len, op_stack.len());
1015    }
1016
1017    #[proptest]
1018    fn removing_an_element_from_the_stack_removes_the_correct_element(
1019        #[strategy(arb())] removal_index: OpStackElement,
1020    ) {
1021        let mut op_stack = OpStack::default();
1022        for i in (0..OpStackElement::COUNT as u64).rev() {
1023            op_stack.push(bfe!(i));
1024        }
1025
1026        let expected_element = BFieldElement::from(removal_index);
1027        let removed_element = op_stack.remove(removal_index);
1028        prop_assert_eq!(expected_element, removed_element);
1029
1030        let expected_len = 2 * OpStackElement::COUNT - 1;
1031        prop_assert_eq!(expected_len, op_stack.len());
1032    }
1033}
triton_isa/op_stack.rs

triton_isa/
op_stack.rs
