circom_lsp_program_structure/utils/
memory_slice.rs

1use num_bigint_dig::BigInt;
2use std::fmt::{Display, Formatter};
3
4pub enum TypeInvalidAccess{
5    MissingInputs(String),
6    MissingInputTags(String),
7    NoInitializedComponent,
8    NoInitializedSignal
9}
10
11pub enum TypeAssignmentError{
12    MultipleAssignments,
13    AssignmentOutput
14}
15
16pub enum MemoryError {
17    OutOfBoundsError,
18    AssignmentError(TypeAssignmentError),
19    InvalidAccess(TypeInvalidAccess),
20    UnknownSizeDimension,
21    MismatchedDimensions(usize, usize),
22    MismatchedDimensionsWeak(usize, usize),
23    AssignmentMissingTags(String),
24    AssignmentTagAfterInit,
25    AssignmentTagTwice,
26    AssignmentTagInput,
27    TagValueNotInitializedAccess,
28    MissingInputs(String)
29}
30pub type SliceCapacity = usize;
31pub type SimpleSlice = MemorySlice<BigInt>;
32/*
33    Represents the value stored in a element of a circom program.
34    The attribute route stores the dimensions of the slice, used to navigate through them.
35    The length of values is equal to multiplying all the values in route.
36*/
37#[derive(Eq, PartialEq)]
38pub struct MemorySlice<C> {
39    route: Vec<SliceCapacity>,
40    values: Vec<C>,
41}
42
43impl<C: Clone> Clone for MemorySlice<C> {
44    fn clone(&self) -> Self {
45        MemorySlice { route: self.route.clone(), values: self.values.clone() }
46    }
47}
48
49impl<C: Default + Clone + Display + Eq> Display for MemorySlice<C> {
50    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
51        if self.values.is_empty() {
52            f.write_str("[]")
53        } else if self.values.len() == 1 {
54            f.write_str(&format!("{}", self.values[0]))
55        } else {
56            let mut msg = format!("[{}", self.values[0]);
57            for i in 1..self.values.len() {
58                msg.push_str(&format!(",{}", self.values[i]));
59            }
60            msg.push_str("]");
61            f.write_str(&msg)
62        }
63    }
64}
65
66impl<C: Clone> MemorySlice<C> {
67    // Raw manipulations of the slice
68    fn get_initial_cell(
69        memory_slice: &MemorySlice<C>,
70        access: &[SliceCapacity],
71    ) -> Result<SliceCapacity, MemoryError> {
72        
73        if access.len() > memory_slice.route.len() {
74            return Result::Err(MemoryError::OutOfBoundsError);
75        }
76
77        let mut cell = 0;
78        let mut cell_jump = memory_slice.values.len();
79        let mut i: SliceCapacity = 0;
80        while i < access.len() {
81            if access[i] >= memory_slice.route[i] {
82                return Result::Err(MemoryError::OutOfBoundsError);
83            }
84            cell_jump /= memory_slice.route[i];
85            cell += cell_jump * access[i];
86            i += 1;
87        }
88        Result::Ok(cell)
89    }
90    pub fn check_correct_dims(
91        memory_slice: &MemorySlice<C>,
92        access: &[SliceCapacity],
93        new_values: &MemorySlice<C>,
94        is_strict: bool,
95    ) -> Result<(), MemoryError> {
96
97        if access.len() + new_values.route.len() > memory_slice.route.len() {
98            return Result::Err(MemoryError::OutOfBoundsError);
99        }
100
101        let mut i: SliceCapacity = 0;
102        
103        while i < access.len() {
104            if access[i] >= memory_slice.route[i] {
105                return Result::Err(MemoryError::OutOfBoundsError);
106            }
107            i += 1;
108        }
109
110        let initial_index_new: SliceCapacity = i;
111        i = 0;
112
113        while i < new_values.route.len() {
114            if new_values.route[i] < memory_slice.route[initial_index_new + i] {
115                if is_strict{ // case signals: we do not allow 
116                    return Result::Err(MemoryError::MismatchedDimensions(new_values.route[i], memory_slice.route[initial_index_new + i]));
117                } else{ // case variables: we allow the assignment of smaller arrays
118                    return Result::Err(MemoryError::MismatchedDimensionsWeak(new_values.route[i], memory_slice.route[initial_index_new + i]));
119                }
120            }
121            if new_values.route[i] > memory_slice.route[initial_index_new + i] {
122                return Result::Err(MemoryError::MismatchedDimensions(new_values.route[i], memory_slice.route[initial_index_new + i]));
123            }
124            i += 1;
125        }
126        Result::Ok(())
127    }
128
129    // Returns the new route and the total number of cells
130    // that a slice with such route will have
131    fn generate_new_route_from_access(
132        memory_slice: &MemorySlice<C>,
133        access: &[SliceCapacity],
134    ) -> Result<(Vec<SliceCapacity>, SliceCapacity), MemoryError> {
135        if access.len() > memory_slice.route.len() {
136            return Result::Err(MemoryError::OutOfBoundsError);
137        }
138
139        let mut size = Vec::new();
140        let mut number_of_cells = 1;
141        for i in access.len()..memory_slice.route.len() {
142            number_of_cells *= memory_slice.route[i];
143            size.push(memory_slice.route[i]);
144        }
145        Result::Ok((size, number_of_cells))
146    }
147
148    fn generate_slice_from_access(
149        memory_slice: &MemorySlice<C>,
150        access: &[SliceCapacity],
151    ) -> Result<MemorySlice<C>, MemoryError> {
152        if access.is_empty() {
153            return Result::Ok(memory_slice.clone());
154        }
155
156        let (size, number_of_cells) =
157            MemorySlice::generate_new_route_from_access(memory_slice, access)?;
158        let mut values = Vec::with_capacity(number_of_cells);
159        let initial_cell = MemorySlice::get_initial_cell(memory_slice, access)?;
160        let mut offset = 0;
161        while offset < number_of_cells {
162            let new_value = memory_slice.values[initial_cell + offset].clone();
163            values.push(new_value);
164            offset += 1;
165        }
166
167        Result::Ok(MemorySlice { route: size, values })
168    }
169
170    // User operations
171    pub fn new(initial_value: &C) -> MemorySlice<C> {
172        MemorySlice::new_with_route(&[], initial_value)
173    }
174    pub fn new_array(route: Vec<SliceCapacity>, values: Vec<C>) -> MemorySlice<C> {
175        MemorySlice { route, values }
176    }
177    pub fn new_with_route(route: &[SliceCapacity], initial_value: &C) -> MemorySlice<C> {
178        let mut length = 1;
179        for i in route {
180            length *= *i;
181        }
182
183        let mut values = Vec::with_capacity(length);
184        for _i in 0..length {
185            values.push(initial_value.clone());
186        }
187
188        MemorySlice { route: route.to_vec(), values }
189    }
190    pub fn insert_values(
191        memory_slice: &mut MemorySlice<C>,
192        access: &[SliceCapacity],
193        new_values: &MemorySlice<C>,
194        is_strict:bool,
195    ) -> Result<(), MemoryError> {
196        match MemorySlice::check_correct_dims(memory_slice, access, new_values, is_strict){
197            Result::Ok(_) => {
198                let mut cell = MemorySlice::get_initial_cell(memory_slice, access)?;
199
200                // if MemorySlice::get_number_of_cells(new_values)
201                //     > (MemorySlice::get_number_of_cells(memory_slice) - cell)
202                // {
203                //     return Result::Err(MemoryError::OutOfBoundsError);
204
205                for value in new_values.values.iter() {
206                    memory_slice.values[cell] = value.clone();
207                    cell += 1;
208                }
209                Result::Ok(())
210            },
211            Result::Err(MemoryError::MismatchedDimensionsWeak(dim_1, dim_2)) => {
212                let mut cell = MemorySlice::get_initial_cell(memory_slice, access)?;
213                // if MemorySlice::get_number_of_cells(new_values)
214                //     > (MemorySlice::get_number_of_cells(memory_slice) - cell)
215                // {
216                //     return Result::Err(MemoryError::OutOfBoundsError);
217                // }
218                for value in new_values.values.iter() {
219                    memory_slice.values[cell] = value.clone();
220                    cell += 1;
221                }
222                Result::Err(MemoryError::MismatchedDimensionsWeak(dim_1, dim_2))
223            },
224            Result::Err(error) => return Err(error),
225        }
226    }
227
228    pub fn insert_value_by_index(
229        memory_slice: &mut MemorySlice<C>,
230        index: usize,
231        new_value: C,
232    )-> Result<(), MemoryError> {
233        if index > MemorySlice::get_number_of_cells(memory_slice) {
234            return Result::Err(MemoryError::OutOfBoundsError);
235        }
236        memory_slice.values[index] = new_value;
237        return Result::Ok(());
238    }
239
240    pub fn get_access_index(
241        memory_slice: &MemorySlice<C>,
242        index: usize,
243    ) -> Result<Vec<SliceCapacity>, MemoryError>{
244        let mut number_cells = MemorySlice::get_number_of_cells(memory_slice);
245        if index > number_cells {
246            return Result::Err(MemoryError::OutOfBoundsError);
247        }
248        else{
249            let mut access = vec![];
250            let mut index_aux = index;
251            for pos in &memory_slice.route{
252                number_cells = number_cells/pos;
253                access.push(index_aux / number_cells);
254                index_aux = index_aux % number_cells;
255            }
256            return Result::Ok(access);
257        }
258    }
259
260    pub fn access_values(
261        memory_slice: &MemorySlice<C>,
262        access: &[SliceCapacity],
263    ) -> Result<MemorySlice<C>, MemoryError> {
264        MemorySlice::generate_slice_from_access(memory_slice, access)
265    }
266    pub fn access_value_by_index(
267        memory_slice: &MemorySlice<C>,
268        index: usize,
269    )-> Result<C, MemoryError> {
270        if index > MemorySlice::get_number_of_cells(memory_slice) {
271            return Result::Err(MemoryError::OutOfBoundsError);
272        }
273        return Result::Ok(memory_slice.values[index].clone());
274    }
275
276    pub fn get_reference_to_single_value<'a>(
277        memory_slice: &'a MemorySlice<C>,
278        access: &[SliceCapacity],
279    ) -> Result<&'a C, MemoryError> {
280        assert_eq!(memory_slice.route.len(), access.len());
281        let cell = MemorySlice::get_initial_cell(memory_slice, access)?;
282        Result::Ok(&memory_slice.values[cell])
283    }
284    pub fn get_reference_to_single_value_by_index<'a>(
285        memory_slice: &'a MemorySlice<C>,
286        index: usize,
287    ) -> Result<&'a C, MemoryError> {
288        if index > MemorySlice::get_number_of_cells(memory_slice) {
289            return Result::Err(MemoryError::OutOfBoundsError);
290        }
291        Result::Ok(&memory_slice.values[index])
292    }
293    pub fn get_reference_to_single_value_by_index_or_break<'a>(
294        memory_slice: &'a MemorySlice<C>,
295        index: usize,
296    ) -> &'a C {
297        if index > MemorySlice::get_number_of_cells(memory_slice) {
298            unreachable!("The index is too big for the slice");
299        }
300        &memory_slice.values[index]
301    }
302    pub fn get_mut_reference_to_single_value<'a>(
303        memory_slice: &'a mut MemorySlice<C>,
304        access: &[SliceCapacity],
305    ) -> Result<&'a mut C, MemoryError> {
306        assert_eq!(memory_slice.route.len(), access.len());
307        let cell = MemorySlice::get_initial_cell(memory_slice, access)?;
308        Result::Ok(&mut memory_slice.values[cell])
309    }
310    pub fn get_number_of_cells(memory_slice: &MemorySlice<C>) -> SliceCapacity {
311        memory_slice.values.len()
312    }
313    pub fn route(&self) -> &[SliceCapacity] {
314        &self.route
315    }
316    pub fn is_single(&self) -> bool {
317        self.route.is_empty()
318    }
319    /*
320        !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
321        !   Calling this function with a MemorySlice  !
322        !   that has more than one cell will cause    !
323        !   the compiler to panic.  Use carefully     !
324        !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
325    */
326    pub fn unwrap_to_single(memory_slice: MemorySlice<C>) -> C {
327        assert!(memory_slice.is_single());
328        let mut memory_slice = memory_slice;
329        memory_slice.values.pop().unwrap()
330    }
331    pub fn destruct(self) -> (Vec<SliceCapacity>, Vec<C>) {
332        (self.route, self.values)
333    }
334}
335
336#[cfg(test)]
337mod tests {
338    use super::*;
339    type U32Slice = MemorySlice<u32>;
340
341    #[test]
342    fn memory_slice_vector_initialization() {
343        let route = vec![3, 4];
344        let slice = U32Slice::new_with_route(&route, &0);
345        assert_eq!(U32Slice::get_number_of_cells(&slice), 12);
346        for (dim_0, dim_1) in slice.route.iter().zip(&route) {
347            assert_eq!(*dim_0, *dim_1);
348        }
349        for f in 0..3 {
350            for c in 0..4 {
351                let result = U32Slice::get_reference_to_single_value(&slice, &[f, c]);
352                if let Result::Ok(v) = result {
353                    assert_eq!(*v, 0);
354                } else {
355                    assert!(false);
356                }
357            }
358        }
359    }
360    #[test]
361    fn memory_slice_single_initialization() {
362        let slice = U32Slice::new(&4);
363        assert_eq!(U32Slice::get_number_of_cells(&slice), 1);
364        let memory_response = U32Slice::get_reference_to_single_value(&slice, &[]);
365        if let Result::Ok(val) = memory_response {
366            assert_eq!(*val, 4);
367        } else {
368            assert!(false);
369        }
370    }
371    #[test]
372    fn memory_slice_multiple_insertion() {
373        let route = vec![3, 4];
374        let mut slice = U32Slice::new_with_route(&route, &0);
375        let new_row = U32Slice::new_with_route(&[4], &4);
376
377        let res = U32Slice::insert_values(&mut slice, &[2], &new_row);
378        if let Result::Ok(_) = res {
379            for c in 0..4 {
380                let memory_result = U32Slice::get_reference_to_single_value(&slice, &[2, c]);
381                if let Result::Ok(val) = memory_result {
382                    assert_eq!(*val, 4);
383                } else {
384                    assert!(false);
385                }
386            }
387        } else {
388            assert!(false);
389        }
390    }
391}
circom_lsp_program_structure/utils/memory_slice.rs

circom_lsp_program_structure/utils/
memory_slice.rs
