cairo_vm/hint_processor/builtin_hint_processor/
set.rs

1use crate::stdlib::{boxed::Box, collections::HashMap, prelude::*};
2
3use crate::Felt252;
4use crate::{
5    hint_processor::{
6        builtin_hint_processor::hint_utils::{
7            get_integer_from_var_name, get_ptr_from_var_name, insert_value_from_var_name,
8        },
9        hint_processor_definition::HintReference,
10    },
11    serde::deserialize_program::ApTracking,
12    types::errors::math_errors::MathError,
13    vm::{errors::hint_errors::HintError, vm_core::VirtualMachine},
14};
15use num_traits::{ToPrimitive, Zero};
16
17pub fn set_add(
18    vm: &mut VirtualMachine,
19    ids_data: &HashMap<String, HintReference>,
20    ap_tracking: &ApTracking,
21) -> Result<(), HintError> {
22    let set_ptr = get_ptr_from_var_name("set_ptr", vm, ids_data, ap_tracking)?;
23    let elm_size =
24        get_integer_from_var_name("elm_size", vm, ids_data, ap_tracking).and_then(|x| {
25            x.to_usize()
26                .ok_or_else(|| MathError::Felt252ToUsizeConversion(Box::new(x)).into())
27        })?;
28    let elm_ptr = get_ptr_from_var_name("elm_ptr", vm, ids_data, ap_tracking)?;
29    let set_end_ptr = get_ptr_from_var_name("set_end_ptr", vm, ids_data, ap_tracking)?;
30
31    if elm_size.is_zero() {
32        Err(HintError::AssertionFailed(
33            "assert ids.elm_size > 0".to_string().into_boxed_str(),
34        ))?;
35    }
36    if set_ptr > set_end_ptr {
37        return Err(HintError::InvalidSetRange(Box::new((set_ptr, set_end_ptr))));
38    }
39
40    let range_limit = (set_end_ptr - set_ptr)?;
41
42    for i in 0..range_limit {
43        if vm.mem_eq(elm_ptr, (set_ptr + elm_size * i)?, elm_size) {
44            insert_value_from_var_name("index", Felt252::from(i), vm, ids_data, ap_tracking)?;
45            return insert_value_from_var_name(
46                "is_elm_in_set",
47                Felt252::ONE,
48                vm,
49                ids_data,
50                ap_tracking,
51            );
52        }
53    }
54    insert_value_from_var_name("is_elm_in_set", Felt252::ZERO, vm, ids_data, ap_tracking)
55}
56
57#[cfg(test)]
58mod tests {
59    use super::*;
60
61    use crate::{
62        any_box,
63        hint_processor::{
64            builtin_hint_processor::builtin_hint_processor_definition::{
65                BuiltinHintProcessor, HintProcessorData,
66            },
67            hint_processor_definition::HintProcessorLogic,
68        },
69        types::relocatable::MaybeRelocatable,
70        utils::test_utils::*,
71        vm::vm_core::VirtualMachine,
72    };
73    use assert_matches::assert_matches;
74
75    #[cfg(target_arch = "wasm32")]
76    use wasm_bindgen_test::*;
77
78    const HINT_CODE: &str = "assert ids.elm_size > 0\nassert ids.set_ptr <= ids.set_end_ptr\nelm_list = memory.get_range(ids.elm_ptr, ids.elm_size)\nfor i in range(0, ids.set_end_ptr - ids.set_ptr, ids.elm_size):\n    if memory.get_range(ids.set_ptr + i, ids.elm_size) == elm_list:\n        ids.index = i // ids.elm_size\n        ids.is_elm_in_set = 1\n        break\nelse:\n    ids.is_elm_in_set = 0";
79
80    fn init_vm_ids_data(
81        set_ptr: Option<(isize, usize)>,
82        elm_size: Option<i32>,
83        elm_a: Option<isize>,
84        elm_b: Option<usize>,
85    ) -> (VirtualMachine, HashMap<String, HintReference>) {
86        let mut vm = vm_with_range_check!();
87
88        vm.run_context.fp = 6;
89
90        let set_ptr = set_ptr.unwrap_or((2, 0));
91        let elm_size = elm_size.unwrap_or(2);
92        let elm_a = elm_a.unwrap_or(2);
93        let elm_b = elm_b.unwrap_or(3);
94
95        vm.segments = segments![
96            ((1, 2), (set_ptr.0, set_ptr.1)),
97            ((1, 3), elm_size),
98            ((1, 4), (3, 0)),
99            ((1, 5), (2, 2)),
100            ((2, 0), 1),
101            ((2, 1), 3),
102            ((2, 2), 5),
103            ((2, 3), 7),
104            ((3, 0), elm_a),
105            ((3, 1), elm_b)
106        ];
107        let ids_data = ids_data![
108            "is_elm_in_set",
109            "index",
110            "set_ptr",
111            "elm_size",
112            "elm_ptr",
113            "set_end_ptr"
114        ];
115
116        (vm, ids_data)
117    }
118
119    #[test]
120    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
121    fn set_add_new_elem() {
122        let (mut vm, ids_data) = init_vm_ids_data(None, None, None, None);
123        assert_matches!(run_hint!(vm, ids_data, HINT_CODE), Ok(()));
124        assert_eq!(
125            vm.segments
126                .memory
127                .get(&MaybeRelocatable::from((1, 0)))
128                .unwrap()
129                .as_ref(),
130            &MaybeRelocatable::Int(Felt252::ZERO)
131        )
132    }
133
134    #[test]
135    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
136    fn set_add_already_exists() {
137        let (mut vm, ids_data) = init_vm_ids_data(None, None, Some(1), Some(3));
138        assert_matches!(run_hint!(vm, ids_data, HINT_CODE), Ok(()));
139        check_memory![vm.segments.memory, ((1, 0), 1), ((1, 1), 0)];
140    }
141
142    #[test]
143    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
144    fn elm_size_negative() {
145        let (mut vm, ids_data) = init_vm_ids_data(None, Some(-2), None, None);
146        assert_matches!(
147            run_hint!(vm, ids_data, HINT_CODE),
148            Err(HintError::Math(MathError::Felt252ToUsizeConversion(_)))
149        );
150    }
151
152    #[test]
153    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
154    fn elm_size_zero() {
155        let (mut vm, ids_data) = init_vm_ids_data(None, Some(0), None, None);
156        assert_matches!(
157            run_hint!(vm, ids_data, HINT_CODE),
158            Err(HintError::AssertionFailed(
159                bx
160            )) if bx.as_ref() == "assert ids.elm_size > 0"
161        );
162    }
163    #[test]
164    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
165    fn set_ptr_gt_set_end_ptr() {
166        let (mut vm, ids_data) = init_vm_ids_data(Some((2, 3)), None, None, None);
167        assert_matches!(
168            run_hint!(vm, ids_data, HINT_CODE),
169            Err(HintError::InvalidSetRange(bx)) if *bx == ((2, 3).into(), (2, 2).into())
170        );
171    }
172}
cairo_vm/hint_processor/builtin_hint_processor/set.rs

cairo_vm/hint_processor/builtin_hint_processor/
set.rs
