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

triton_isa/
op_stack.rs
