tasm_lib/list/
pop.rs

1use std::collections::HashMap;
2
3use triton_vm::prelude::*;
4
5use crate::list::get::Get;
6use crate::prelude::*;
7use crate::traits::basic_snippet::Reviewer;
8use crate::traits::basic_snippet::SignOffFingerprint;
9
10/// Pop an element from a list. Performs bounds check.
11///
12/// Only supports lists with [statically sized](BFieldCodec::static_length)
13/// elements.
14///
15/// ### Behavior
16///
17/// ```text
18/// BEFORE: _ *list
19/// AFTER:  _ [element: ElementType]
20/// ```
21///
22/// ### Preconditions
23///
24/// - the argument `*list` points to a properly [`BFieldCodec`]-encoded list
25/// - the list `*list` points must be non-empty
26/// - all input arguments are properly [`BFieldCodec`] encoded
27///
28/// ### Postconditions
29///
30/// None.
31#[derive(Debug, Clone, Eq, PartialEq, Hash)]
32pub struct Pop {
33    element_type: DataType,
34}
35
36impl Pop {
37    pub const EMPTY_LIST_ERROR_ID: i128 = 400;
38
39    /// Any part of the list is outside the allocated memory page.
40    /// See the [memory convention][crate::memory] for more details.
41    pub const MEM_PAGE_ACCESS_VIOLATION_ERROR_ID: i128 = 401;
42
43    /// # Panics
44    ///
45    /// Panics if the element has [dynamic length][BFieldCodec::static_length], or
46    /// if the static length is 0.
47    pub fn new(element_type: DataType) -> Self {
48        Get::assert_element_type_is_supported(&element_type);
49
50        Self { element_type }
51    }
52}
53
54impl BasicSnippet for Pop {
55    fn parameters(&self) -> Vec<(DataType, String)> {
56        let list_type = DataType::List(Box::new(self.element_type.clone()));
57        vec![(list_type, "*list".to_string())]
58    }
59
60    fn return_values(&self) -> Vec<(DataType, String)> {
61        vec![(self.element_type.clone(), "element".to_string())]
62    }
63
64    fn entrypoint(&self) -> String {
65        let element_type = self.element_type.label_friendly_name();
66        format!("tasmlib_list_pop___{element_type}")
67    }
68
69    fn code(&self, _: &mut Library) -> Vec<LabelledInstruction> {
70        let mul_with_element_size = match self.element_type.stack_size() {
71            1 => triton_asm!(), // no-op
72            n => triton_asm!(push {n} mul),
73        };
74
75        triton_asm!(
76            // BEFORE: _ *list
77            // AFTER:  _ [element]
78            {self.entrypoint()}:
79                /* assert that length is not 0 */
80                read_mem 1
81                addi 1          // _ length *list
82                dup 1
83                push 0
84                eq              // _ length *list (length == 0)
85                push 0
86                eq              // _ length *list (length != 0)
87                assert error_id {Self::EMPTY_LIST_ERROR_ID}
88                                // _ length *list
89
90                /* decrement list length */
91                dup 1
92                addi -1         // _ length *list new_length
93                pick 1
94                write_mem 1     // _ length *first_element
95                                // _ index  *first_element
96
97                /* compute element's word offset */
98                pick 1
99                {&mul_with_element_size}
100                                // _ *first_element offset
101
102                /* assert access is within one memory page */
103                dup 0
104                split
105                pop 1
106                push 0
107                eq
108                assert error_id {Self::MEM_PAGE_ACCESS_VIOLATION_ERROR_ID}
109                                // _ *first_element offset
110
111                /* finally, read that thing */
112                add             // _ *next_element
113                addi -1         // _ *last_element_last_word
114                {&self.element_type.read_value_from_memory_pop_pointer()}
115                                // _ [elements]
116
117                return
118        )
119    }
120
121    fn sign_offs(&self) -> HashMap<Reviewer, SignOffFingerprint> {
122        let mut sign_offs = HashMap::new();
123        match self.element_type.stack_size() {
124            1 => _ = sign_offs.insert(Reviewer("ferdinand"), 0x3d7287a7a71d27d0.into()),
125            2 => _ = sign_offs.insert(Reviewer("ferdinand"), 0x87273e433f2d09bf.into()),
126            3 => _ = sign_offs.insert(Reviewer("ferdinand"), 0xd502e59ed7251525.into()),
127            5 => _ = sign_offs.insert(Reviewer("ferdinand"), 0xf8ed5295f3d8a9c7.into()),
128            _ => (),
129        }
130
131        sign_offs
132    }
133}
134
135#[cfg(test)]
136mod tests {
137    use super::*;
138    use crate::rust_shadowing_helper_functions::list::insert_random_list;
139    use crate::rust_shadowing_helper_functions::list::list_pop;
140    use crate::test_prelude::*;
141
142    impl Pop {
143        fn set_up_initial_state(
144            &self,
145            list_length: usize,
146            list_pointer: BFieldElement,
147        ) -> FunctionInitialState {
148            let mut memory = HashMap::default();
149            insert_random_list(&self.element_type, list_pointer, list_length, &mut memory);
150
151            let mut stack = self.init_stack_for_isolated_run();
152            stack.push(list_pointer);
153
154            FunctionInitialState { stack, memory }
155        }
156    }
157
158    impl Function for Pop {
159        fn rust_shadow(
160            &self,
161            stack: &mut Vec<BFieldElement>,
162            memory: &mut HashMap<BFieldElement, BFieldElement>,
163        ) -> Result<(), RustShadowError> {
164            let list_address = stack.pop().ok_or(RustShadowError::StackUnderflow)?;
165            let element = list_pop(list_address, memory, self.element_type.stack_size())?;
166            stack.extend(element.into_iter().rev());
167            Ok(())
168        }
169
170        fn pseudorandom_initial_state(
171            &self,
172            seed: [u8; 32],
173            _: Option<BenchmarkCase>,
174        ) -> FunctionInitialState {
175            let mut rng = StdRng::from_seed(seed);
176            let list_length = rng.random_range(1..1 << 12);
177            let list_pointer = rng.random();
178
179            self.set_up_initial_state(list_length, list_pointer)
180        }
181    }
182
183    #[macro_rules_attr::apply(test)]
184    fn rust_shadow() {
185        for ty in [
186            DataType::Bool,
187            DataType::Bfe,
188            DataType::U32,
189            DataType::U64,
190            DataType::Xfe,
191            DataType::Digest,
192        ] {
193            ShadowedFunction::new(Pop::new(ty)).test();
194        }
195    }
196
197    #[macro_rules_attr::apply(proptest)]
198    fn empty_list_crashes_vm(#[strategy(arb())] list_pointer: BFieldElement) {
199        let pop = Pop::new(DataType::Digest);
200        let initial_state = pop.set_up_initial_state(0, list_pointer);
201        test_assertion_failure(
202            &ShadowedFunction::new(pop),
203            initial_state.into(),
204            &[Pop::EMPTY_LIST_ERROR_ID],
205        );
206    }
207
208    /// See similar test for [`Get`] for an explanation.
209    #[macro_rules_attr::apply(proptest(cases = 100))]
210    fn too_large_lists_crash_vm(
211        #[strategy(1_u64 << 22..1 << 32)] list_length: u64,
212        #[strategy(arb())] list_pointer: BFieldElement,
213    ) {
214        // spare host machine RAM: pretend every element is all-zeros
215        let mut memory = HashMap::default();
216        memory.insert(list_pointer, bfe!(list_length));
217
218        // type with a large stack size in Triton VM without breaking the host machine
219        let tuple_ty = DataType::Tuple(vec![DataType::Bfe; 1 << 10]);
220        let set = Pop::new(tuple_ty);
221
222        let mut stack = set.init_stack_for_isolated_run();
223        stack.push(list_pointer);
224        let initial_state = AccessorInitialState { stack, memory };
225
226        test_assertion_failure(
227            &ShadowedFunction::new(set),
228            initial_state.into(),
229            &[Pop::MEM_PAGE_ACCESS_VIOLATION_ERROR_ID],
230        );
231    }
232}
233
234#[cfg(test)]
235mod benches {
236    use super::*;
237    use crate::test_prelude::*;
238
239    #[macro_rules_attr::apply(test)]
240    fn benchmark() {
241        ShadowedFunction::new(Pop::new(DataType::Digest)).bench();
242    }
243}
tasm_lib/list/pop.rs

tasm_lib/list/
pop.rs
