tasm_lib/list/
get.rs

1use triton_vm::prelude::*;
2
3use crate::list::length::Length;
4use crate::prelude::*;
5
6/// Read an element from a list. Performs bounds check.
7///
8/// Only supports lists with [statically sized](BFieldCodec::static_length)
9/// elements.
10///
11/// ### Behavior
12///
13/// ```text
14/// BEFORE: _ *list [index: u32]
15/// AFTER:  _ [element: ElementType]
16/// ```
17///
18/// ### Preconditions
19///
20/// - the argument `*list` points to a properly [`BFieldCodec`]-encoded list
21/// - all input arguments are properly [`BFieldCodec`] encoded
22///
23/// ### Postconditions
24///
25/// None.
26#[derive(Debug, Clone, Eq, PartialEq, Hash)]
27pub struct Get {
28    element_type: DataType,
29}
30
31impl Get {
32    pub const INDEX_OUT_OF_BOUNDS_ERROR_ID: i128 = 380;
33
34    /// Any part of the list is outside the allocated memory page.
35    /// See the [memory convention][crate::memory] for more details.
36    pub const MEM_PAGE_ACCESS_VIOLATION_ERROR_ID: i128 = 381;
37
38    /// # Panics
39    ///
40    /// Panics if the element has [dynamic length][BFieldCodec::static_length], or
41    /// if the static length is 0.
42    pub fn new(element_type: DataType) -> Self {
43        Self::assert_element_type_is_supported(&element_type);
44
45        Self { element_type }
46    }
47
48    /// # Panics
49    ///
50    /// Panics if the element has [dynamic length][BFieldCodec::static_length], or
51    /// if the static length is 0.
52    pub(crate) fn assert_element_type_is_supported(element_type: &DataType) {
53        let Some(static_len) = element_type.static_length() else {
54            panic!("element should have static length");
55        };
56        assert_ne!(0, static_len, "element must not be zero-sized");
57    }
58}
59
60impl BasicSnippet for Get {
61    fn parameters(&self) -> Vec<(DataType, String)> {
62        let list_type = DataType::List(Box::new(self.element_type.clone()));
63
64        vec![
65            (list_type, "*list".to_string()),
66            (DataType::U32, "index".to_string()),
67        ]
68    }
69
70    fn return_values(&self) -> Vec<(DataType, String)> {
71        vec![(self.element_type.clone(), "element".to_string())]
72    }
73
74    fn entrypoint(&self) -> String {
75        let element_type = self.element_type.label_friendly_name();
76        format!("tasmlib_list_get_element___{element_type}")
77    }
78
79    fn code(&self, library: &mut Library) -> Vec<LabelledInstruction> {
80        let list_length = library.import(Box::new(Length));
81        let mul_with_element_size = match self.element_type.stack_size() {
82            1 => triton_asm!(), // no-op
83            n => triton_asm!(push {n} mul),
84        };
85
86        triton_asm!(
87            // BEFORE: _ *list index
88            // AFTER:  _ [element: self.element_type]
89            {self.entrypoint()}:
90                /* assert access is in bounds */
91                dup 1
92                call {list_length}  // _ *list index len
93                dup 1
94                lt                  // _ *list index (index < len)
95                assert error_id {Self::INDEX_OUT_OF_BOUNDS_ERROR_ID}
96
97                addi 1
98                {&mul_with_element_size}
99                                    // _ *list last_word_offset
100
101                /* assert access is within one memory page */
102                split
103                pick 1
104                push 0
105                eq
106                assert error_id {Self::MEM_PAGE_ACCESS_VIOLATION_ERROR_ID}
107                                    // _ *list last_word_offset
108
109                add                 // _ *element_last_word
110                {&self.element_type.read_value_from_memory_pop_pointer()}
111                                    // _ element
112                return
113        )
114    }
115}
116
117#[cfg(test)]
118pub(crate) mod tests {
119    use super::*;
120    use crate::U32_TO_USIZE_ERR;
121    use crate::rust_shadowing_helper_functions::list::insert_random_list;
122    use crate::rust_shadowing_helper_functions::list::list_get;
123    use crate::test_prelude::*;
124
125    impl Get {
126        fn set_up_initial_state(
127            &self,
128            list_length: usize,
129            index: usize,
130            list_pointer: BFieldElement,
131        ) -> AccessorInitialState {
132            let mut memory = HashMap::default();
133            insert_random_list(&self.element_type, list_pointer, list_length, &mut memory);
134
135            let mut stack = self.init_stack_for_isolated_run();
136            stack.push(list_pointer);
137            stack.push(bfe!(index));
138
139            AccessorInitialState { stack, memory }
140        }
141
142        pub fn random_len_idx_ptr(
143            bench_case: Option<BenchmarkCase>,
144            rng: &mut impl Rng,
145        ) -> (usize, usize, BFieldElement) {
146            let (index, list_length) = match bench_case {
147                Some(BenchmarkCase::CommonCase) => (16, 32),
148                Some(BenchmarkCase::WorstCase) => (63, 64),
149                None => {
150                    let list_length = rng.random_range(1..=100);
151                    (rng.random_range(0..list_length), list_length)
152                }
153            };
154            let list_pointer = rng.random();
155
156            (list_length, index, list_pointer)
157        }
158    }
159
160    impl Accessor for Get {
161        fn rust_shadow(
162            &self,
163            stack: &mut Vec<BFieldElement>,
164            memory: &HashMap<BFieldElement, BFieldElement>,
165        ) -> Result<(), RustShadowError> {
166            let index: u32 = stack
167                .pop()
168                .ok_or(RustShadowError::StackUnderflow)?
169                .try_into()
170                .map_err(|_| RustShadowError::U64ToU32Error)?;
171            let list_pointer = stack.pop().ok_or(RustShadowError::StackUnderflow)?;
172
173            let index: usize = index.try_into().expect(U32_TO_USIZE_ERR);
174            let element_length = self
175                .element_type
176                .static_length()
177                .ok_or(RustShadowError::Other)?;
178            let element = list_get(list_pointer, index, memory, element_length)?;
179
180            stack.extend(element.into_iter().rev());
181            Ok(())
182        }
183
184        fn pseudorandom_initial_state(
185            &self,
186            seed: [u8; 32],
187            bench_case: Option<BenchmarkCase>,
188        ) -> AccessorInitialState {
189            let (list_length, index, list_pointer) =
190                Self::random_len_idx_ptr(bench_case, &mut StdRng::from_seed(seed));
191
192            self.set_up_initial_state(list_length, index, list_pointer)
193        }
194    }
195
196    #[macro_rules_attr::apply(test)]
197    fn rust_shadow() {
198        for ty in [DataType::Bfe, DataType::Digest, DataType::I128] {
199            ShadowedAccessor::new(Get::new(ty)).test();
200        }
201    }
202
203    #[macro_rules_attr::apply(proptest)]
204    fn out_of_bounds_access_crashes_vm(
205        #[strategy(0_usize..=1_000)] list_length: usize,
206        #[strategy(#list_length..=u32::MAX.try_into().unwrap())] index: usize,
207        #[strategy(arb())] list_pointer: BFieldElement,
208    ) {
209        let get = Get::new(DataType::Bfe);
210        let initial_state = get.set_up_initial_state(list_length, index, list_pointer);
211        test_assertion_failure(
212            &ShadowedAccessor::new(get),
213            initial_state.into(),
214            &[Get::INDEX_OUT_OF_BOUNDS_ERROR_ID],
215        );
216    }
217
218    // Don't test on `wasm32`: too large indices cannot be represented there.
219    #[test_strategy::proptest]
220    #[cfg(not(target_arch = "wasm32"))]
221    fn too_large_indices_crash_vm(
222        #[strategy(1_usize << 32..)] index: usize,
223        #[strategy(arb())] list_pointer: BFieldElement,
224    ) {
225        use triton_vm::error::OpStackError::FailedU32Conversion;
226
227        let list_length = 0;
228        let get = Get::new(DataType::Bfe);
229        let initial_state = get.set_up_initial_state(list_length, index, list_pointer);
230        let expected_error = InstructionError::OpStackError(FailedU32Conversion(bfe!(index)));
231        crate::test_helpers::negative_test(
232            &ShadowedAccessor::new(get),
233            initial_state.into(),
234            &[expected_error],
235        );
236    }
237
238    /// Create a rather long list containing elements of rather large size, then
239    /// try to access one of the higher-index elements and watch the VM crash.
240    ///
241    /// The goal is to access memory beyond the limit of one [page size]. The
242    /// element type's size is chosen to be large-ish to allow for a somewhat
243    /// shorter list. For Triton VM to crash (and this test to pass), the total list
244    /// size must exceed the page size, and an element outside the page size bound
245    /// must be accessed. In order to trigger the _correct_ failure, the element's
246    /// index must not be too large. In particular, both the list length and the
247    /// element index must be at most [u32::MAX].
248    ///
249    /// [page size]: crate::memory::dyn_malloc::DYN_MALLOC_PAGE_SIZE
250    #[macro_rules_attr::apply(proptest(cases = 100))]
251    fn too_large_lists_crash_vm(
252        #[strategy(1_u64 << 22..1 << 32)] list_length: u64,
253        #[strategy((1 << 22) - 1..#list_length)] index: u64,
254        #[strategy(arb())] list_pointer: BFieldElement,
255    ) {
256        // spare host machine RAM: pretend every element is all-zeros
257        let mut memory = HashMap::default();
258        memory.insert(list_pointer, bfe!(list_length));
259
260        // type with a large stack size in Triton VM without breaking the host machine
261        let tuple_ty = DataType::Tuple(vec![DataType::Bfe; 1 << 10]);
262        let get = Get::new(tuple_ty);
263        let mut stack = get.init_stack_for_isolated_run();
264        stack.push(list_pointer);
265        stack.push(bfe!(index));
266        let initial_state = AccessorInitialState { stack, memory };
267
268        test_assertion_failure(
269            &ShadowedAccessor::new(get),
270            initial_state.into(),
271            &[Get::MEM_PAGE_ACCESS_VIOLATION_ERROR_ID],
272        );
273    }
274}
275
276#[cfg(test)]
277mod benches {
278    use super::*;
279    use crate::test_prelude::*;
280
281    #[macro_rules_attr::apply(test)]
282    fn benchmark() {
283        ShadowedAccessor::new(Get::new(DataType::Digest)).bench();
284    }
285}
tasm_lib/list/get.rs

tasm_lib/list/
get.rs
