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 inputs(&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 outputs(&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 triton_vm::error::OpStackError::FailedU32Conversion;
120
121    use super::*;
122    use crate::U32_TO_USIZE_ERR;
123    use crate::rust_shadowing_helper_functions::list::insert_random_list;
124    use crate::rust_shadowing_helper_functions::list::list_get;
125    use crate::test_helpers::negative_test;
126    use crate::test_prelude::*;
127
128    impl Get {
129        fn set_up_initial_state(
130            &self,
131            list_length: usize,
132            index: usize,
133            list_pointer: BFieldElement,
134        ) -> AccessorInitialState {
135            let mut memory = HashMap::default();
136            insert_random_list(&self.element_type, list_pointer, list_length, &mut memory);
137
138            let mut stack = self.init_stack_for_isolated_run();
139            stack.push(list_pointer);
140            stack.push(bfe!(index));
141
142            AccessorInitialState { stack, memory }
143        }
144
145        pub fn random_len_idx_ptr(
146            bench_case: Option<BenchmarkCase>,
147            rng: &mut impl rand::Rng,
148        ) -> (usize, usize, BFieldElement) {
149            let (index, list_length) = match bench_case {
150                Some(BenchmarkCase::CommonCase) => (16, 32),
151                Some(BenchmarkCase::WorstCase) => (63, 64),
152                None => {
153                    let list_length = rng.random_range(1..=100);
154                    (rng.random_range(0..list_length), list_length)
155                }
156            };
157            let list_pointer = rng.random();
158
159            (list_length, index, list_pointer)
160        }
161    }
162
163    impl Accessor for Get {
164        fn rust_shadow(
165            &self,
166            stack: &mut Vec<BFieldElement>,
167            memory: &HashMap<BFieldElement, BFieldElement>,
168        ) {
169            let index: u32 = stack.pop().unwrap().try_into().unwrap();
170            let list_pointer = stack.pop().unwrap();
171
172            let index: usize = index.try_into().expect(U32_TO_USIZE_ERR);
173            let element_length = self.element_type.static_length().unwrap();
174            let element = list_get(list_pointer, index, memory, element_length);
175
176            stack.extend(element.into_iter().rev());
177        }
178
179        fn pseudorandom_initial_state(
180            &self,
181            seed: [u8; 32],
182            bench_case: Option<BenchmarkCase>,
183        ) -> AccessorInitialState {
184            let (list_length, index, list_pointer) =
185                Self::random_len_idx_ptr(bench_case, &mut StdRng::from_seed(seed));
186
187            self.set_up_initial_state(list_length, index, list_pointer)
188        }
189    }
190
191    #[test]
192    fn rust_shadow() {
193        for ty in [DataType::Bfe, DataType::Digest, DataType::I128] {
194            ShadowedAccessor::new(Get::new(ty)).test();
195        }
196    }
197
198    #[proptest]
199    fn out_of_bounds_access_crashes_vm(
200        #[strategy(0_usize..=1_000)] list_length: usize,
201        #[strategy(#list_length..1 << 32)] index: usize,
202        #[strategy(arb())] list_pointer: BFieldElement,
203    ) {
204        let get = Get::new(DataType::Bfe);
205        let initial_state = get.set_up_initial_state(list_length, index, list_pointer);
206        test_assertion_failure(
207            &ShadowedAccessor::new(get),
208            initial_state.into(),
209            &[Get::INDEX_OUT_OF_BOUNDS_ERROR_ID],
210        );
211    }
212
213    #[proptest]
214    fn too_large_indices_crash_vm(
215        #[strategy(1_usize << 32..)] index: usize,
216        #[strategy(arb())] list_pointer: BFieldElement,
217    ) {
218        let list_length = 0;
219        let get = Get::new(DataType::Bfe);
220        let initial_state = get.set_up_initial_state(list_length, index, list_pointer);
221        let expected_error = InstructionError::OpStackError(FailedU32Conversion(bfe!(index)));
222        negative_test(
223            &ShadowedAccessor::new(get),
224            initial_state.into(),
225            &[expected_error],
226        );
227    }
228
229    /// Create a rather long list containing elements of rather large size, then
230    /// try to access one of the higher-index elements and watch the VM crash.
231    ///
232    /// The goal is to access memory beyond the limit of one [page size]. The
233    /// element type's size is chosen to be large-ish to allow for a somewhat
234    /// shorter list. For Triton VM to crash (and this test to pass), the total list
235    /// size must exceed the page size, and an element outside the page size bound
236    /// must be accessed. In order to trigger the _correct_ failure, the element's
237    /// index must not be too large. In particular, both the list length and the
238    /// element index must be at most [u32::MAX].
239    ///
240    /// [page size]: crate::memory::dyn_malloc::DYN_MALLOC_PAGE_SIZE
241    #[proptest(cases = 100)]
242    fn too_large_lists_crash_vm(
243        #[strategy(1_u64 << 22..1 << 32)] list_length: u64,
244        #[strategy((1 << 22) - 1..#list_length)] index: u64,
245        #[strategy(arb())] list_pointer: BFieldElement,
246    ) {
247        // spare host machine RAM: pretend every element is all-zeros
248        let mut memory = HashMap::default();
249        memory.insert(list_pointer, bfe!(list_length));
250
251        // type with a large stack size in Triton VM without breaking the host machine
252        let tuple_ty = DataType::Tuple(vec![DataType::Bfe; 1 << 10]);
253        let get = Get::new(tuple_ty);
254        let mut stack = get.init_stack_for_isolated_run();
255        stack.push(list_pointer);
256        stack.push(bfe!(index));
257        let initial_state = AccessorInitialState { stack, memory };
258
259        test_assertion_failure(
260            &ShadowedAccessor::new(get),
261            initial_state.into(),
262            &[Get::MEM_PAGE_ACCESS_VIOLATION_ERROR_ID],
263        );
264    }
265}
266
267#[cfg(test)]
268mod benches {
269    use super::*;
270    use crate::test_prelude::*;
271
272    #[test]
273    fn benchmark() {
274        ShadowedAccessor::new(Get::new(DataType::Digest)).bench();
275    }
276}
tasm_lib/list/get.rs

tasm_lib/list/
get.rs
