cairo_vm/vm/vm_memory/
memory.rs

1use crate::stdlib::{borrow::Cow, collections::HashMap, fmt, prelude::*};
2
3use crate::types::errors::math_errors::MathError;
4use crate::vm::runners::cairo_pie::CairoPieMemory;
5use crate::Felt252;
6use crate::{
7    types::relocatable::{MaybeRelocatable, Relocatable},
8    utils::from_relocatable_to_indexes,
9    vm::errors::memory_errors::MemoryError,
10};
11use bitvec::prelude as bv;
12use core::cmp::Ordering;
13use num_traits::ToPrimitive;
14
15pub struct ValidationRule(
16    #[allow(clippy::type_complexity)]
17    pub  Box<dyn Fn(&Memory, Relocatable) -> Result<Vec<Relocatable>, MemoryError>>,
18);
19
20/// [`MemoryCell`] represents an optimized storage layout for the VM memory.
21/// It's specified to have both size an alignment of 32 bytes to optimize cache access.
22/// Typical cache sizes are 64 bytes, a few cases might be 128 bytes, meaning 32 bytes aligned to
23/// 32 bytes boundaries will never get split into two separate lines, avoiding double stalls and
24/// reducing false sharing and evictions.
25/// The trade off is extra computation for conversion to our "in-flight" `MaybeRelocatable` and
26/// `Felt252` as well as some extra copies. Empirically, this seems to be offset by the improved
27/// locality of the bigger structure for Lambdaworks. There is a big hit from the conversions when
28/// using the `BigUint` implementation, since those force allocations on the heap, but since that's
29/// dropped in later versions anyway it's not a priority. For Lambdaworks the new copies are mostly
30/// to the stack, which is typically already in the cache.
31/// The layout uses the 4 MSB in the first `u64` as flags:
32/// - BIT63: NONE flag, 1 when the cell is actually empty.
33/// - BIT62: ACCESS flag, 1 when the cell has been accessed in a way observable to Cairo.
34/// - BIT61: RELOCATABLE flag, 1 when the contained value is a `Relocatable`, 0 when it is a
35///   `Felt252`.
36///   `Felt252` values are stored in big-endian order to keep the flag bits free.
37///   `Relocatable` values are stored as native endian, with the 3rd word storing the segment index
38///   and the 4th word storing the offset.
39#[derive(Copy, Clone, Eq, Ord, PartialEq, PartialOrd, Debug)]
40#[repr(align(32))]
41pub(crate) struct MemoryCell([u64; 4]);
42
43impl MemoryCell {
44    pub const NONE_MASK: u64 = 1 << 63;
45    pub const ACCESS_MASK: u64 = 1 << 62;
46    pub const RELOCATABLE_MASK: u64 = 1 << 61;
47    pub const NONE: Self = Self([Self::NONE_MASK, 0, 0, 0]);
48
49    pub fn new(value: MaybeRelocatable) -> Self {
50        value.into()
51    }
52
53    pub fn is_none(&self) -> bool {
54        self.0[0] & Self::NONE_MASK == Self::NONE_MASK
55    }
56
57    pub fn is_some(&self) -> bool {
58        !self.is_none()
59    }
60
61    pub fn mark_accessed(&mut self) {
62        self.0[0] |= Self::ACCESS_MASK;
63    }
64
65    pub fn is_accessed(&self) -> bool {
66        self.0[0] & Self::ACCESS_MASK == Self::ACCESS_MASK
67    }
68
69    pub fn get_value(&self) -> Option<MaybeRelocatable> {
70        self.is_some().then(|| (*self).into())
71    }
72}
73
74impl From<MaybeRelocatable> for MemoryCell {
75    fn from(value: MaybeRelocatable) -> Self {
76        match value {
77            MaybeRelocatable::Int(x) => Self(x.to_raw()),
78            MaybeRelocatable::RelocatableValue(x) => Self([
79                Self::RELOCATABLE_MASK,
80                0,
81                // NOTE: hack around signedness
82                usize::from_ne_bytes(x.segment_index.to_ne_bytes()) as u64,
83                x.offset as u64,
84            ]),
85        }
86    }
87}
88
89impl From<MemoryCell> for MaybeRelocatable {
90    fn from(cell: MemoryCell) -> Self {
91        debug_assert!(cell.is_some());
92        let flags = cell.0[0];
93        match flags & MemoryCell::RELOCATABLE_MASK {
94            MemoryCell::RELOCATABLE_MASK => Self::from((
95                // NOTE: hack around signedness
96                isize::from_ne_bytes((cell.0[2] as usize).to_ne_bytes()),
97                cell.0[3] as usize,
98            )),
99            _ => {
100                let mut value = cell.0;
101                // Remove all flag bits
102                value[0] &= 0x0fffffffffffffff;
103                Self::Int(Felt252::from_raw(value))
104            }
105        }
106    }
107}
108
109pub struct AddressSet(Vec<bv::BitVec>);
110
111impl AddressSet {
112    pub(crate) fn new() -> Self {
113        Self(Vec::new())
114    }
115
116    pub(crate) fn contains(&self, addr: &Relocatable) -> bool {
117        let segment = addr.segment_index;
118        if segment.is_negative() {
119            return false;
120        }
121
122        self.0
123            .get(segment as usize)
124            .and_then(|segment| segment.get(addr.offset))
125            .map(|bit| *bit)
126            .unwrap_or(false)
127    }
128
129    pub(crate) fn extend(&mut self, addresses: &[Relocatable]) {
130        for addr in addresses {
131            let segment = addr.segment_index;
132            if segment.is_negative() {
133                continue;
134            }
135            let segment = segment as usize;
136            if segment >= self.0.len() {
137                self.0.resize(segment + 1, bv::BitVec::new());
138            }
139
140            let offset = addr.offset;
141            if offset >= self.0[segment].len() {
142                self.0[segment].resize(offset + 1, false);
143            }
144            self.0[segment].replace(offset, true);
145        }
146    }
147}
148
149#[cfg(test)]
150impl AddressSet {
151    pub(crate) fn len(&self) -> usize {
152        self.0
153            .iter()
154            .map(|segment| segment.iter().map(|bit| *bit as usize).sum::<usize>())
155            .sum()
156    }
157}
158
159pub struct Memory {
160    pub(crate) data: Vec<Vec<MemoryCell>>,
161    /// Temporary segments are used when it's necessary to write data, but we
162    /// don't know yet where it will be located. These segments will eventually
163    /// be relocated to the main memory according to the `relocation_rules`. For
164    /// example, dictionaries are required to be contiguous, so each is stored in a
165    /// temporary segment and eventually relocated to a single segment.
166    pub(crate) temp_data: Vec<Vec<MemoryCell>>,
167    // relocation_rules's keys map to temp_data's indices and therefore begin at
168    // zero; that is, segment_index = -1 maps to key 0, -2 to key 1...
169    #[cfg(not(feature = "extensive_hints"))]
170    pub(crate) relocation_rules: HashMap<usize, Relocatable>,
171    #[cfg(feature = "extensive_hints")]
172    pub(crate) relocation_rules: HashMap<usize, MaybeRelocatable>,
173    pub validated_addresses: AddressSet,
174    validation_rules: Vec<Option<ValidationRule>>,
175}
176
177impl Memory {
178    pub fn new() -> Memory {
179        Memory {
180            data: Vec::new(),
181            temp_data: Vec::new(),
182            relocation_rules: HashMap::new(),
183            validated_addresses: AddressSet::new(),
184            validation_rules: Vec::with_capacity(7),
185        }
186    }
187
188    fn get_segment(&mut self, key: Relocatable) -> Result<&mut Vec<MemoryCell>, MemoryError> {
189        let (value_index, _) = from_relocatable_to_indexes(key);
190        let data = if key.segment_index.is_negative() {
191            &mut self.temp_data
192        } else {
193            &mut self.data
194        };
195        let data_len = data.len();
196        data.get_mut(value_index)
197            .ok_or_else(|| MemoryError::UnallocatedSegment(Box::new((value_index, data_len))))
198    }
199
200    /// Inserts a value into a memory address
201    /// Will return an Error if the segment index given by the address corresponds to a non-allocated segment,
202    /// or if the inserted value is inconsistent with the current value at the memory cell
203    /// If the address isnt contiguous with previously inserted data, memory gaps will be represented by None values
204    pub fn insert<V>(&mut self, key: Relocatable, val: V) -> Result<(), MemoryError>
205    where
206        MaybeRelocatable: From<V>,
207    {
208        let val = MaybeRelocatable::from(val);
209        let segment = self.get_segment(key)?;
210        let (_, value_offset) = from_relocatable_to_indexes(key);
211
212        //Check if the element is inserted next to the last one on the segment
213        //Forgoing this check would allow data to be inserted in a different index
214        let (len, capacity) = (segment.len(), segment.capacity());
215        if len <= value_offset {
216            let new_len = value_offset
217                .checked_add(1)
218                .ok_or(MemoryError::VecCapacityExceeded)?;
219            segment
220                .try_reserve(new_len.saturating_sub(capacity))
221                .map_err(|_| MemoryError::VecCapacityExceeded)?;
222            segment.resize(new_len, MemoryCell::NONE);
223        }
224        // At this point there's *something* in there
225
226        match segment[value_offset].get_value() {
227            None => segment[value_offset] = MemoryCell::new(val),
228            Some(current_cell) => {
229                if current_cell != val {
230                    //Existing memory cannot be changed
231                    return Err(MemoryError::InconsistentMemory(Box::new((
232                        key,
233                        current_cell,
234                        val,
235                    ))));
236                }
237            }
238        };
239        self.validate_memory_cell(key)
240    }
241
242    pub(crate) fn delete_unaccessed(&mut self, addr: Relocatable) -> Result<(), MemoryError> {
243        let (_, offset) = from_relocatable_to_indexes(addr);
244        let segment = self.get_segment(addr)?;
245
246        // Make sure the offset exists.
247        if offset >= segment.len() {
248            return Err(MemoryError::UnsetUnallocatedCell(addr));
249        }
250
251        // Ensure the cell has not been accessed.
252        if segment[offset].is_accessed() {
253            return Err(MemoryError::UnsetAccessedCell(addr));
254        }
255
256        // Unset the cell.
257        segment[offset] = MemoryCell::NONE;
258        Ok(())
259    }
260
261    /// Retrieve a value from memory (either normal or temporary) and apply relocation rules
262    pub(crate) fn get<'a, 'b: 'a, K: 'a>(&'b self, key: &'a K) -> Option<Cow<'b, MaybeRelocatable>>
263    where
264        Relocatable: TryFrom<&'a K>,
265    {
266        let relocatable: Relocatable = key.try_into().ok()?;
267
268        let data = if relocatable.segment_index.is_negative() {
269            &self.temp_data
270        } else {
271            &self.data
272        };
273        let (i, j) = from_relocatable_to_indexes(relocatable);
274        let value = data.get(i)?.get(j)?.get_value()?;
275        Some(Cow::Owned(self.relocate_value(&value).ok()?.into_owned()))
276    }
277
278    // Version of Memory.relocate_value() that doesn't require a self reference
279    #[cfg(not(feature = "extensive_hints"))]
280    fn relocate_address(
281        addr: Relocatable,
282        relocation_rules: &HashMap<usize, Relocatable>,
283    ) -> Result<MaybeRelocatable, MemoryError> {
284        if addr.segment_index < 0 {
285            // Adjust the segment index to begin at zero, as per the struct field's
286            // comment.
287            if let Some(x) = relocation_rules.get(&(-(addr.segment_index + 1) as usize)) {
288                return Ok((*x + addr.offset)?.into());
289            }
290        }
291        Ok(addr.into())
292    }
293    #[cfg(feature = "extensive_hints")]
294    fn relocate_address(
295        addr: Relocatable,
296        relocation_rules: &HashMap<usize, MaybeRelocatable>,
297    ) -> Result<MaybeRelocatable, MemoryError> {
298        if addr.segment_index < 0 {
299            // Adjust the segment index to begin at zero, as per the struct field's
300            // comment.
301            if let Some(x) = relocation_rules.get(&(-(addr.segment_index + 1) as usize)) {
302                return Ok(match x {
303                    MaybeRelocatable::RelocatableValue(r) => (*r + addr.offset)?.into(),
304                    MaybeRelocatable::Int(i) => i.into(),
305                });
306            }
307        }
308        Ok(addr.into())
309    }
310
311    /// Relocates the memory according to the relocation rules and clears `self.relocaction_rules`.
312    pub fn relocate_memory(&mut self) -> Result<(), MemoryError> {
313        if self.relocation_rules.is_empty() || self.temp_data.is_empty() {
314            return Ok(());
315        }
316        // Relocate temporary addresses in memory
317        for segment in self.data.iter_mut().chain(self.temp_data.iter_mut()) {
318            for cell in segment.iter_mut() {
319                let value = cell.get_value();
320                match value {
321                    Some(MaybeRelocatable::RelocatableValue(addr)) if addr.segment_index < 0 => {
322                        let mut new_cell = MemoryCell::new(Memory::relocate_address(
323                            addr,
324                            &self.relocation_rules,
325                        )?);
326                        if cell.is_accessed() {
327                            new_cell.mark_accessed();
328                        }
329                        *cell = new_cell;
330                    }
331                    _ => {}
332                }
333            }
334        }
335        // Move relocated temporary memory into the real memory
336        for index in (0..self.temp_data.len()).rev() {
337            if let Some(base_addr) = self.relocation_rules.get(&index) {
338                let data_segment = self.temp_data.remove(index);
339
340                #[cfg(feature = "extensive_hints")]
341                let base_addr = match base_addr {
342                    MaybeRelocatable::RelocatableValue(addr) => addr,
343                    MaybeRelocatable::Int(_) => {
344                        continue;
345                    }
346                };
347
348                // Insert the to-be relocated segment into the real memory
349                let mut addr = *base_addr;
350                if let Some(s) = self.data.get_mut(addr.segment_index as usize) {
351                    s.reserve_exact(data_segment.len())
352                }
353                for cell in data_segment {
354                    if let Some(v) = cell.get_value() {
355                        // Rely on Memory::insert to catch memory inconsistencies
356                        self.insert(addr, v)?;
357                        // If the cell is accessed, mark the relocated one as accessed too
358                        if cell.is_accessed() {
359                            self.mark_as_accessed(addr)
360                        }
361                    }
362                    addr = (addr + 1)?;
363                }
364            }
365        }
366        self.relocation_rules.clear();
367        Ok(())
368    }
369    /// Add a new relocation rule.
370    ///
371    /// When using feature "extensive_hints" the destination is allowed to be an Integer (via
372    /// MaybeRelocatable). Relocating memory to anything other than a `Relocatable` is generally
373    /// not useful, but it does make the implementation consistent with the pythonic version.
374    ///
375    /// Will return an error if any of the following conditions are not met:
376    ///   - Source address's segment must be negative (temporary).
377    ///   - Source address's offset must be zero.
378    ///   - There shouldn't already be relocation at the source segment.
379    #[cfg(not(feature = "extensive_hints"))]
380    pub(crate) fn add_relocation_rule(
381        &mut self,
382        src_ptr: Relocatable,
383        dst_ptr: Relocatable,
384    ) -> Result<(), MemoryError> {
385        if src_ptr.segment_index >= 0 {
386            return Err(MemoryError::AddressNotInTemporarySegment(
387                src_ptr.segment_index,
388            ));
389        }
390        if src_ptr.offset != 0 {
391            return Err(MemoryError::NonZeroOffset(src_ptr.offset));
392        }
393
394        // Adjust the segment index to begin at zero, as per the struct field's
395        // comment.
396        let segment_index = -(src_ptr.segment_index + 1) as usize;
397        if self.relocation_rules.contains_key(&segment_index) {
398            return Err(MemoryError::DuplicatedRelocation(src_ptr.segment_index));
399        }
400
401        self.relocation_rules.insert(segment_index, dst_ptr);
402        Ok(())
403    }
404    #[cfg(feature = "extensive_hints")]
405    pub(crate) fn add_relocation_rule(
406        &mut self,
407        src_ptr: Relocatable,
408        dst: MaybeRelocatable,
409    ) -> Result<(), MemoryError> {
410        if src_ptr.segment_index >= 0 {
411            return Err(MemoryError::AddressNotInTemporarySegment(
412                src_ptr.segment_index,
413            ));
414        }
415        if src_ptr.offset != 0 {
416            return Err(MemoryError::NonZeroOffset(src_ptr.offset));
417        }
418
419        // Adjust the segment index to begin at zero, as per the struct field's
420        // comment.
421        let segment_index = -(src_ptr.segment_index + 1) as usize;
422        if self.relocation_rules.contains_key(&segment_index) {
423            return Err(MemoryError::DuplicatedRelocation(src_ptr.segment_index));
424        }
425
426        self.relocation_rules.insert(segment_index, dst);
427        Ok(())
428    }
429
430    /// Gets the value from memory address as a Felt252 value.
431    /// Returns an Error if the value at the memory address is missing or not a Felt252.
432    pub fn get_integer(&self, key: Relocatable) -> Result<Cow<Felt252>, MemoryError> {
433        match self
434            .get(&key)
435            .ok_or_else(|| MemoryError::UnknownMemoryCell(Box::new(key)))?
436        {
437            Cow::Borrowed(MaybeRelocatable::Int(int)) => Ok(Cow::Borrowed(int)),
438            Cow::Owned(MaybeRelocatable::Int(int)) => Ok(Cow::Owned(int)),
439            _ => Err(MemoryError::ExpectedInteger(Box::new(key))),
440        }
441    }
442
443    /// Gets a u32 value from memory address.
444    /// Returns an Error if the value at the memory address is missing or not a u32.
445    pub fn get_u32(&self, key: Relocatable) -> Result<u32, MemoryError> {
446        let felt = self.get_integer(key)?.into_owned();
447        felt.to_u32()
448            .ok_or_else(|| MemoryError::Math(MathError::Felt252ToU32Conversion(Box::new(felt))))
449    }
450
451    /// Gets the value from memory address as a usize.
452    /// Returns an Error if the value at the memory address is missing not a Felt252, or can't be converted to usize.
453    pub fn get_usize(&self, key: Relocatable) -> Result<usize, MemoryError> {
454        let felt = self.get_integer(key)?.into_owned();
455        felt.to_usize()
456            .ok_or_else(|| MemoryError::Math(MathError::Felt252ToUsizeConversion(Box::new(felt))))
457    }
458
459    /// Gets the value from memory address as a Relocatable value.
460    /// Returns an Error if the value at the memory address is missing or not a Relocatable.
461    pub fn get_relocatable(&self, key: Relocatable) -> Result<Relocatable, MemoryError> {
462        match self
463            .get(&key)
464            .ok_or_else(|| MemoryError::UnknownMemoryCell(Box::new(key)))?
465        {
466            Cow::Borrowed(MaybeRelocatable::RelocatableValue(rel)) => Ok(*rel),
467            Cow::Owned(MaybeRelocatable::RelocatableValue(rel)) => Ok(rel),
468            _ => Err(MemoryError::ExpectedRelocatable(Box::new(key))),
469        }
470    }
471
472    /// Gets the value from memory address as a MaybeRelocatable value.
473    /// Returns an Error if the value at the memory address is missing or not a MaybeRelocatable.
474    pub fn get_maybe_relocatable(&self, key: Relocatable) -> Result<MaybeRelocatable, MemoryError> {
475        match self
476            .get(&key)
477            .ok_or_else(|| MemoryError::UnknownMemoryCell(Box::new(key)))?
478        {
479            // Note: the `Borrowed` variant will never occur.
480            Cow::Borrowed(maybe_rel) => Ok(maybe_rel.clone()),
481            Cow::Owned(maybe_rel) => Ok(maybe_rel),
482        }
483    }
484
485    /// Inserts a value into memory
486    /// Returns an error if the memory cell asignment is invalid
487    pub fn insert_value<T: Into<MaybeRelocatable>>(
488        &mut self,
489        key: Relocatable,
490        val: T,
491    ) -> Result<(), MemoryError> {
492        self.insert(key, &val.into())
493    }
494
495    pub fn add_validation_rule(&mut self, segment_index: usize, rule: ValidationRule) {
496        if segment_index >= self.validation_rules.len() {
497            // Fill gaps
498            self.validation_rules
499                .resize_with(segment_index + 1, || None);
500        }
501        self.validation_rules.insert(segment_index, Some(rule));
502    }
503
504    fn validate_memory_cell(&mut self, addr: Relocatable) -> Result<(), MemoryError> {
505        if let Some(Some(rule)) = addr
506            .segment_index
507            .to_usize()
508            .and_then(|x| self.validation_rules.get(x))
509        {
510            if !self.validated_addresses.contains(&addr) {
511                self.validated_addresses
512                    .extend(rule.0(self, addr)?.as_slice());
513            }
514        }
515        Ok(())
516    }
517
518    ///Applies validation_rules to the current memory
519    pub fn validate_existing_memory(&mut self) -> Result<(), MemoryError> {
520        for (index, rule) in self.validation_rules.iter().enumerate() {
521            if index >= self.data.len() {
522                continue;
523            }
524            let Some(rule) = rule else {
525                continue;
526            };
527            for offset in 0..self.data[index].len() {
528                let addr = Relocatable::from((index as isize, offset));
529                if !self.validated_addresses.contains(&addr) {
530                    self.validated_addresses
531                        .extend(rule.0(self, addr)?.as_slice());
532                }
533            }
534        }
535        Ok(())
536    }
537
538    /// Compares two ranges of values in memory of length `len`
539    /// Returns the ordering and the first relative position at which they differ
540    /// Special cases:
541    /// - `lhs` exists in memory but `rhs` doesn't -> (Ordering::Greater, 0)
542    /// - `rhs` exists in memory but `lhs` doesn't -> (Ordering::Less, 0)
543    /// - None of `lhs` or `rhs` exist in memory -> (Ordering::Equal, 0)
544    ///   Everything else behaves much like `memcmp` in C.
545    ///   This is meant as an optimization for hints to avoid allocations.
546    pub(crate) fn memcmp(
547        &self,
548        lhs: Relocatable,
549        rhs: Relocatable,
550        len: usize,
551    ) -> (Ordering, usize) {
552        let get_segment = |idx: isize| {
553            if idx.is_negative() {
554                self.temp_data.get(-(idx + 1) as usize)
555            } else {
556                self.data.get(idx as usize)
557            }
558        };
559        match (
560            get_segment(lhs.segment_index),
561            get_segment(rhs.segment_index),
562        ) {
563            (None, None) => {
564                return (Ordering::Equal, 0);
565            }
566            (Some(_), None) => {
567                return (Ordering::Greater, 0);
568            }
569            (None, Some(_)) => {
570                return (Ordering::Less, 0);
571            }
572            (Some(lhs_segment), Some(rhs_segment)) => {
573                let (lhs_start, rhs_start) = (lhs.offset, rhs.offset);
574                for i in 0..len {
575                    let (lhs, rhs) = (
576                        lhs_segment.get(lhs_start + i),
577                        rhs_segment.get(rhs_start + i),
578                    );
579                    let ord = lhs.cmp(&rhs);
580                    if ord == Ordering::Equal {
581                        continue;
582                    }
583                    return (ord, i);
584                }
585            }
586        };
587        (Ordering::Equal, len)
588    }
589
590    /// Compares two ranges of values in memory of length `len`
591    /// Returns the ordering and the first relative position at which they differ
592    /// Special cases:
593    /// - `lhs` exists in memory but `rhs` doesn't -> (Ordering::Greater, 0)
594    /// - `rhs` exists in memory but `lhs` doesn't -> (Ordering::Less, 0)
595    /// - None of `lhs` or `rhs` exist in memory -> (Ordering::Equal, 0)
596    ///   Everything else behaves much like `memcmp` in C.
597    ///   This is meant as an optimization for hints to avoid allocations.
598    pub(crate) fn mem_eq(&self, lhs: Relocatable, rhs: Relocatable, len: usize) -> bool {
599        if lhs == rhs {
600            return true;
601        }
602        let get_segment = |idx: isize| {
603            if idx.is_negative() {
604                self.temp_data.get(-(idx + 1) as usize)
605            } else {
606                self.data.get(idx as usize)
607            }
608        };
609        match (
610            get_segment(lhs.segment_index).and_then(|s| s.get(lhs.offset..)),
611            get_segment(rhs.segment_index).and_then(|s| s.get(rhs.offset..)),
612        ) {
613            (Some(lhs), Some(rhs)) => {
614                let (lhs_len, rhs_len) = (lhs.len().min(len), rhs.len().min(len));
615                if lhs_len != rhs_len {
616                    return false;
617                }
618                lhs[..lhs_len] == rhs[..rhs_len]
619            }
620            (None, None) => true,
621            _ => false,
622        }
623    }
624
625    /// Gets a range of memory values from addr to addr + size
626    /// The outputed range may contain gaps if the original memory has them
627    pub fn get_range(&self, addr: Relocatable, size: usize) -> Vec<Option<Cow<MaybeRelocatable>>> {
628        let mut values = Vec::new();
629
630        for i in 0..size {
631            values.push((addr + i).ok().and_then(|x| self.get(&x)));
632        }
633
634        values
635    }
636
637    /// Gets a range of memory values from addr to addr + size
638    /// Fails if there if any of the values inside the range is missing (memory gap)
639    pub fn get_continuous_range(
640        &self,
641        addr: Relocatable,
642        size: usize,
643    ) -> Result<Vec<MaybeRelocatable>, MemoryError> {
644        let mut values = Vec::with_capacity(size);
645
646        for i in 0..size {
647            values.push(match self.get(&(addr + i)?) {
648                Some(elem) => elem.into_owned(),
649                None => return Err(MemoryError::GetRangeMemoryGap(Box::new((addr, size)))),
650            });
651        }
652
653        Ok(values)
654    }
655
656    /// Gets a range of Felt252 memory values from addr to addr + size
657    /// Fails if there if any of the values inside the range is missing (memory gap),
658    /// or is not a Felt252
659    pub fn get_integer_range(
660        &self,
661        addr: Relocatable,
662        size: usize,
663    ) -> Result<Vec<Cow<Felt252>>, MemoryError> {
664        let mut values = Vec::new();
665
666        for i in 0..size {
667            values.push(self.get_integer((addr + i)?)?);
668        }
669
670        Ok(values)
671    }
672
673    /// Gets a range of u32 memory values from addr to addr + size
674    /// Fails if any of the values inside the range is missing (memory gap) or is not a u32
675    pub fn get_u32_range(&self, addr: Relocatable, size: usize) -> Result<Vec<u32>, MemoryError> {
676        let mut values = Vec::new();
677
678        for i in 0..size {
679            values.push(self.get_u32((addr + i)?)?);
680        }
681
682        Ok(values)
683    }
684
685    fn get_cell(&self, addr: Relocatable) -> Option<&MemoryCell> {
686        let (i, j) = from_relocatable_to_indexes(addr);
687        let data = if addr.segment_index < 0 {
688            &self.temp_data
689        } else {
690            &self.data
691        };
692        data.get(i)?.get(j)
693    }
694
695    #[cfg(test)]
696    pub(crate) fn get_cell_for_testing(&self, addr: Relocatable) -> Option<&MemoryCell> {
697        self.get_cell(addr)
698    }
699
700    pub fn is_accessed(&self, addr: &Relocatable) -> Result<bool, MemoryError> {
701        Ok(self
702            .get_cell(*addr)
703            .ok_or(MemoryError::UnknownMemoryCell(Box::new(*addr)))?
704            .is_accessed())
705    }
706
707    pub fn mark_as_accessed(&mut self, addr: Relocatable) {
708        let (i, j) = from_relocatable_to_indexes(addr);
709        let data = if addr.segment_index < 0 {
710            &mut self.temp_data
711        } else {
712            &mut self.data
713        };
714        let cell = data.get_mut(i).and_then(|x| x.get_mut(j));
715        if let Some(cell) = cell {
716            cell.mark_accessed()
717        }
718    }
719
720    pub fn get_amount_of_accessed_addresses_for_segment(
721        &self,
722        segment_index: usize,
723    ) -> Option<usize> {
724        let segment = self.data.get(segment_index)?;
725        Some(
726            segment
727                .iter()
728                .filter(|x| x.is_some() && x.is_accessed())
729                .count(),
730        )
731    }
732
733    // Inserts a value into memory & inmediately marks it as accessed if insertion was succesful
734    // Used by ModBuiltinRunner, as it accesses memory outside of it's segment when operating
735    pub(crate) fn insert_as_accessed<V>(
736        &mut self,
737        key: Relocatable,
738        val: V,
739    ) -> Result<(), MemoryError>
740    where
741        MaybeRelocatable: From<V>,
742    {
743        self.insert(key, val)?;
744        self.mark_as_accessed(key);
745        Ok(())
746    }
747}
748
749impl From<&Memory> for CairoPieMemory {
750    fn from(mem: &Memory) -> CairoPieMemory {
751        let mut pie_memory = Vec::default();
752        for (i, segment) in mem.data.iter().enumerate() {
753            for (j, cell) in segment.iter().enumerate() {
754                if let Some(value) = cell.get_value() {
755                    pie_memory.push(((i, j), value))
756                }
757            }
758        }
759        CairoPieMemory(pie_memory)
760    }
761}
762
763impl fmt::Display for Memory {
764    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
765        for (i, segment) in self.temp_data.iter().enumerate() {
766            for (j, cell) in segment.iter().enumerate() {
767                if let Some(elem) = cell.get_value() {
768                    let temp_segment = i + 1;
769                    writeln!(f, "(-{temp_segment},{j}) : {elem}")?;
770                }
771            }
772        }
773        for (i, segment) in self.data.iter().enumerate() {
774            for (j, cell) in segment.iter().enumerate() {
775                if let Some(elem) = cell.get_value() {
776                    writeln!(f, "({i},{j}) : {elem}")?;
777                }
778            }
779        }
780        Ok(())
781    }
782}
783
784/// Applies `relocation_rules` to a value
785pub(crate) trait RelocateValue<'a, Input: 'a, Output: 'a> {
786    fn relocate_value(&self, value: Input) -> Result<Output, MemoryError>;
787}
788
789#[cfg(not(feature = "extensive_hints"))]
790impl RelocateValue<'_, Relocatable, Relocatable> for Memory {
791    fn relocate_value(&self, addr: Relocatable) -> Result<Relocatable, MemoryError> {
792        if addr.segment_index < 0 {
793            // Adjust the segment index to begin at zero, as per the struct field's
794            // comment.
795            if let Some(x) = self
796                .relocation_rules
797                .get(&(-(addr.segment_index + 1) as usize))
798            {
799                return (*x + addr.offset).map_err(MemoryError::Math);
800            }
801        }
802        Ok(addr)
803    }
804}
805#[cfg(feature = "extensive_hints")]
806impl RelocateValue<'_, Relocatable, MaybeRelocatable> for Memory {
807    fn relocate_value(&self, addr: Relocatable) -> Result<MaybeRelocatable, MemoryError> {
808        if addr.segment_index < 0 {
809            // Adjust the segment index to begin at zero, as per the struct field's
810            // comment.
811            if let Some(x) = self
812                .relocation_rules
813                .get(&(-(addr.segment_index + 1) as usize))
814            {
815                return Ok(match x {
816                    MaybeRelocatable::RelocatableValue(r) => {
817                        (*r + addr.offset).map_err(MemoryError::Math)?.into()
818                    }
819                    MaybeRelocatable::Int(i) => i.into(),
820                });
821            }
822        }
823        Ok(addr.into())
824    }
825}
826
827impl<'a> RelocateValue<'a, &'a Felt252, &'a Felt252> for Memory {
828    fn relocate_value(&self, value: &'a Felt252) -> Result<&'a Felt252, MemoryError> {
829        Ok(value)
830    }
831}
832
833impl<'a> RelocateValue<'a, &'a MaybeRelocatable, Cow<'a, MaybeRelocatable>> for Memory {
834    fn relocate_value(
835        &self,
836        value: &'a MaybeRelocatable,
837    ) -> Result<Cow<'a, MaybeRelocatable>, MemoryError> {
838        Ok(match value {
839            MaybeRelocatable::Int(_) => Cow::Borrowed(value),
840            MaybeRelocatable::RelocatableValue(addr) => {
841                #[cfg(not(feature = "extensive_hints"))]
842                let v = self.relocate_value(*addr)?.into();
843                #[cfg(feature = "extensive_hints")]
844                let v = self.relocate_value(*addr)?;
845
846                Cow::Owned(v)
847            }
848        })
849    }
850}
851
852impl Default for Memory {
853    fn default() -> Self {
854        Self::new()
855    }
856}
857
858#[cfg(test)]
859mod memory_tests {
860
861    use super::*;
862    use crate::{
863        felt_hex, relocatable,
864        utils::test_utils::*,
865        vm::{
866            runners::builtin_runner::{
867                RangeCheckBuiltinRunner, SignatureBuiltinRunner, RC_N_PARTS_STANDARD,
868            },
869            vm_memory::memory_segments::MemorySegmentManager,
870        },
871    };
872    use assert_matches::assert_matches;
873
874    use crate::vm::errors::memory_errors::MemoryError;
875
876    use crate::utils::test_utils::memory_from_memory;
877    use crate::utils::test_utils::memory_inner;
878
879    #[cfg(target_arch = "wasm32")]
880    use wasm_bindgen_test::*;
881
882    #[test]
883    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
884    fn insert_and_get_succesful() {
885        let key = Relocatable::from((0, 0));
886        let val = MaybeRelocatable::from(Felt252::from(5_u64));
887        let mut memory = Memory::new();
888        memory.data.push(Vec::new());
889        memory.insert(key, &val).unwrap();
890        assert_eq!(
891            memory.get(&key).unwrap().as_ref(),
892            &MaybeRelocatable::from(Felt252::from(5_u64))
893        );
894    }
895
896    #[test]
897    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
898    fn get_valuef_from_temp_segment() {
899        let mut memory = Memory::new();
900        memory.temp_data = vec![vec![
901            MemoryCell::NONE,
902            MemoryCell::NONE,
903            MemoryCell::new(mayberelocatable!(8)),
904        ]];
905        assert_eq!(
906            memory.get(&mayberelocatable!(-1, 2)).unwrap().as_ref(),
907            &mayberelocatable!(8),
908        );
909    }
910
911    #[test]
912    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
913    fn insert_value_in_temp_segment() {
914        let key = Relocatable::from((-1, 3));
915        let val = MaybeRelocatable::from(Felt252::from(8_u64));
916        let mut memory = Memory::new();
917        memory.temp_data.push(Vec::new());
918        memory.insert(key, &val).unwrap();
919        assert_eq!(
920            memory.temp_data[0][3],
921            MemoryCell::new(MaybeRelocatable::from(Felt252::from(8_u64)))
922        );
923    }
924
925    #[test]
926    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
927    fn insert_and_get_from_temp_segment_succesful() {
928        let key = Relocatable::from((-1, 0));
929        let val = MaybeRelocatable::from(Felt252::from(5_u64));
930        let mut memory = Memory::new();
931        memory.temp_data.push(Vec::new());
932        memory.insert(key, &val).unwrap();
933        assert_eq!(
934            memory.get(&key).unwrap().as_ref(),
935            &MaybeRelocatable::from(Felt252::from(5_u64)),
936        );
937    }
938
939    #[test]
940    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
941    fn insert_and_get_from_temp_segment_failed() {
942        let key = relocatable!(-1, 1);
943        let mut memory = Memory::new();
944        memory.temp_data = vec![vec![
945            MemoryCell::NONE,
946            MemoryCell::new(mayberelocatable!(8)),
947        ]];
948        assert_eq!(
949            memory.insert(key, &mayberelocatable!(5)),
950            Err(MemoryError::InconsistentMemory(Box::new((
951                relocatable!(-1, 1),
952                mayberelocatable!(8),
953                mayberelocatable!(5)
954            ))))
955        );
956    }
957
958    #[test]
959    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
960    fn get_non_allocated_memory() {
961        let key = Relocatable::from((0, 0));
962        let memory = Memory::new();
963        assert_eq!(memory.get(&key), None);
964    }
965
966    #[test]
967    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
968    fn get_non_existant_element() {
969        let key = Relocatable::from((0, 0));
970        let memory = Memory::new();
971        assert_eq!(memory.get(&key), None);
972    }
973
974    #[test]
975    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
976    fn insert_non_allocated_memory() {
977        let key = Relocatable::from((0, 0));
978        let val = MaybeRelocatable::from(Felt252::from(5_u64));
979        let mut memory = Memory::new();
980        let error = memory.insert(key, &val);
981        assert_eq!(
982            error,
983            Err(MemoryError::UnallocatedSegment(Box::new((0, 0))))
984        );
985    }
986
987    #[test]
988    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
989    fn insert_inconsistent_memory() {
990        let key = Relocatable::from((0, 0));
991        let val_a = MaybeRelocatable::from(Felt252::from(5_u64));
992        let val_b = MaybeRelocatable::from(Felt252::from(6_u64));
993        let mut memory = Memory::new();
994        memory.data.push(Vec::new());
995        memory
996            .insert(key, &val_a)
997            .expect("Unexpected memory insert fail");
998        let error = memory.insert(key, &val_b);
999        assert_eq!(
1000            error,
1001            Err(MemoryError::InconsistentMemory(Box::new((
1002                key, val_a, val_b
1003            ))))
1004        );
1005    }
1006
1007    #[test]
1008    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1009    fn insert_non_contiguous_element() {
1010        let key_a = Relocatable::from((0, 0));
1011        let key_b = Relocatable::from((0, 2));
1012        let val = MaybeRelocatable::from(Felt252::from(5_u64));
1013        let mut memory = Memory::new();
1014        memory.data.push(Vec::new());
1015        memory.insert(key_a, &val).unwrap();
1016        memory.insert(key_b, &val).unwrap();
1017        assert_eq!(memory.get(&key_b).unwrap().as_ref(), &val);
1018    }
1019
1020    #[test]
1021    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1022    fn insert_non_contiguous_element_memory_gaps_none() {
1023        let key_a = Relocatable::from((0, 0));
1024        let key_b = Relocatable::from((0, 5));
1025        let val = MaybeRelocatable::from(Felt252::from(5_u64));
1026        let mut memory = Memory::new();
1027        memory.data.push(Vec::new());
1028        memory.insert(key_a, &val).unwrap();
1029        memory.insert(key_b, &val).unwrap();
1030        assert_eq!(memory.get(&key_b).unwrap().as_ref(), &val);
1031        assert_eq!(memory.get(&MaybeRelocatable::from((0, 1))), None);
1032        assert_eq!(memory.get(&MaybeRelocatable::from((0, 2))), None);
1033        assert_eq!(memory.get(&MaybeRelocatable::from((0, 3))), None);
1034        assert_eq!(memory.get(&MaybeRelocatable::from((0, 4))), None);
1035    }
1036
1037    #[test]
1038    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1039    fn validate_existing_memory_for_range_check_within_bounds() {
1040        let mut builtin = RangeCheckBuiltinRunner::<RC_N_PARTS_STANDARD>::new(Some(8), true);
1041        let mut segments = MemorySegmentManager::new();
1042        builtin.initialize_segments(&mut segments);
1043        builtin.add_validation_rule(&mut segments.memory);
1044        for _ in 0..3 {
1045            segments.add();
1046        }
1047
1048        segments
1049            .memory
1050            .insert(
1051                Relocatable::from((0, 0)),
1052                &MaybeRelocatable::from(Felt252::from(45_u64)),
1053            )
1054            .unwrap();
1055        segments.memory.validate_existing_memory().unwrap();
1056        assert!(segments
1057            .memory
1058            .validated_addresses
1059            .contains(&Relocatable::from((0, 0))));
1060    }
1061
1062    #[test]
1063    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1064    fn validate_existing_memory_for_range_check_outside_bounds() {
1065        let mut builtin = RangeCheckBuiltinRunner::<RC_N_PARTS_STANDARD>::new(Some(8), true);
1066        let mut segments = MemorySegmentManager::new();
1067        segments.add();
1068        builtin.initialize_segments(&mut segments);
1069        segments
1070            .memory
1071            .insert(
1072                Relocatable::from((1, 0)),
1073                &MaybeRelocatable::from(Felt252::from(-10)),
1074            )
1075            .unwrap();
1076        builtin.add_validation_rule(&mut segments.memory);
1077        let error = segments.memory.validate_existing_memory();
1078        assert_eq!(
1079            error,
1080            Err(MemoryError::RangeCheckNumOutOfBounds(Box::new((
1081                Felt252::from(-10),
1082                Felt252::TWO.pow(128_u128)
1083            ))))
1084        );
1085    }
1086
1087    #[test]
1088    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1089    fn validate_existing_memory_for_invalid_signature() {
1090        let mut builtin = SignatureBuiltinRunner::new(Some(512), true);
1091        let mut segments = MemorySegmentManager::new();
1092        builtin.initialize_segments(&mut segments);
1093        segments.memory = memory![
1094            (
1095                (0, 0),
1096                (
1097                    "874739451078007766457464989774322083649278607533249481151382481072868806602",
1098                    10
1099                )
1100            ),
1101            (
1102                (0, 1),
1103                (
1104                    "-1472574760335685482768423018116732869320670550222259018541069375211356613248",
1105                    10
1106                )
1107            )
1108        ];
1109        builtin.add_validation_rule(&mut segments.memory);
1110        let error = segments.memory.validate_existing_memory();
1111        assert_eq!(
1112            error,
1113            Err(MemoryError::SignatureNotFound(Box::new((0, 0).into())))
1114        );
1115    }
1116
1117    #[test]
1118    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1119    fn validate_existing_memory_for_valid_signature() {
1120        let mut builtin = SignatureBuiltinRunner::new(Some(512), true);
1121
1122        let signature_r =
1123            felt_hex!("0x411494b501a98abd8262b0da1351e17899a0c4ef23dd2f96fec5ba847310b20");
1124        let signature_s =
1125            felt_hex!("0x405c3191ab3883ef2b763af35bc5f5d15b3b4e99461d70e84c654a351a7c81b");
1126
1127        builtin
1128            .add_signature(Relocatable::from((1, 0)), &(signature_r, signature_s))
1129            .unwrap();
1130
1131        let mut segments = MemorySegmentManager::new();
1132
1133        segments.memory = memory![
1134            (
1135                (1, 0),
1136                (
1137                    "874739451078007766457464989774322083649278607533249481151382481072868806602",
1138                    10
1139                )
1140            ),
1141            ((1, 1), 2)
1142        ];
1143
1144        builtin.initialize_segments(&mut segments);
1145
1146        builtin.add_validation_rule(&mut segments.memory);
1147
1148        let result = segments.memory.validate_existing_memory();
1149
1150        assert_eq!(result, Ok(()))
1151    }
1152
1153    #[test]
1154    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1155    fn validate_existing_memory_for_range_check_relocatable_value() {
1156        let mut builtin = RangeCheckBuiltinRunner::<RC_N_PARTS_STANDARD>::new(Some(8), true);
1157        let mut segments = MemorySegmentManager::new();
1158        builtin.initialize_segments(&mut segments);
1159        segments.memory = memory![((0, 0), (0, 4))];
1160        builtin.add_validation_rule(&mut segments.memory);
1161        let error = segments.memory.validate_existing_memory();
1162        assert_eq!(
1163            error,
1164            Err(MemoryError::RangeCheckFoundNonInt(Box::new(relocatable!(
1165                0, 0
1166            ))))
1167        );
1168    }
1169
1170    #[test]
1171    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1172    fn validate_existing_memory_for_range_check_out_of_bounds_diff_segment() {
1173        let mut builtin = RangeCheckBuiltinRunner::<RC_N_PARTS_STANDARD>::new(Some(8), true);
1174        let mut segments = MemorySegmentManager::new();
1175        segments.memory = Memory::new();
1176        segments.add();
1177        builtin.initialize_segments(&mut segments);
1178        segments
1179            .memory
1180            .insert(
1181                Relocatable::from((0, 0)),
1182                &MaybeRelocatable::from(Felt252::from(-45_i128)),
1183            )
1184            .unwrap();
1185        builtin.add_validation_rule(&mut segments.memory);
1186        assert_eq!(segments.memory.validate_existing_memory(), Ok(()));
1187    }
1188
1189    #[test]
1190    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1191    fn get_integer_valid() {
1192        let memory = memory![((0, 0), 10)];
1193        assert_eq!(
1194            memory
1195                .get_integer(Relocatable::from((0, 0)))
1196                .unwrap()
1197                .as_ref(),
1198            &Felt252::from(10)
1199        );
1200    }
1201
1202    #[test]
1203    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1204    fn get_integer_invalid_expected_integer() {
1205        let mut segments = MemorySegmentManager::new();
1206        segments.add();
1207        segments
1208            .memory
1209            .insert(Relocatable::from((0, 0)), &MaybeRelocatable::from((0, 10)))
1210            .unwrap();
1211        assert_matches!(
1212            segments.memory.get_integer(Relocatable::from((0, 0))),
1213            Err(MemoryError::ExpectedInteger(
1214                bx
1215            )) if *bx == Relocatable::from((0, 0))
1216        );
1217    }
1218
1219    #[test]
1220    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1221    fn get_u32_too_big() {
1222        let mut segments = MemorySegmentManager::new();
1223        segments.add();
1224        segments
1225            .memory
1226            .insert(Relocatable::from((0, 0)), &Felt252::from(1_u64 << 32))
1227            .unwrap();
1228        assert_matches!(
1229            segments.memory.get_u32(Relocatable::from((0, 0))),
1230            Err(MemoryError::Math(MathError::Felt252ToU32Conversion(
1231                bx
1232            ))) if *bx == Felt252::from(1_u64 << 32)
1233        );
1234    }
1235
1236    #[test]
1237    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1238    fn get_maybe_relocatable_valid_relocatable() {
1239        let memory = memory![((0, 0), (1, 0))];
1240        assert_eq!(
1241            memory
1242                .get_maybe_relocatable(Relocatable::from((0, 0)))
1243                .unwrap(),
1244            Relocatable::from((1, 0)).into()
1245        );
1246    }
1247
1248    #[test]
1249    fn get_maybe_relocatable_valid_integer() {
1250        let memory = memory![((0, 0), 10)];
1251        assert_eq!(
1252            memory
1253                .get_maybe_relocatable(Relocatable::from((0, 0)))
1254                .unwrap(),
1255            10.into()
1256        );
1257    }
1258
1259    #[test]
1260    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1261    fn default_memory() {
1262        let mem: Memory = Default::default();
1263        assert_eq!(mem.data.len(), 0);
1264    }
1265
1266    #[test]
1267    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1268    fn insert_and_get_temporary_succesful() {
1269        let mut memory = Memory::new();
1270        memory.temp_data.push(Vec::new());
1271
1272        let key = Relocatable::from((-1, 0));
1273        let val = MaybeRelocatable::from(Felt252::from(5));
1274        memory.insert(key, &val).unwrap();
1275
1276        assert_eq!(memory.get(&key).unwrap().as_ref(), &val);
1277    }
1278
1279    #[test]
1280    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1281    fn add_relocation_rule() {
1282        let mut memory = Memory::new();
1283
1284        assert_eq!(
1285            memory.add_relocation_rule((-1, 0).into(), (1, 2).into()),
1286            Ok(()),
1287        );
1288        assert_eq!(
1289            memory.add_relocation_rule((-2, 0).into(), (-1, 1).into()),
1290            Ok(()),
1291        );
1292        assert_eq!(
1293            memory.add_relocation_rule((5, 0).into(), (0, 0).into()),
1294            Err(MemoryError::AddressNotInTemporarySegment(5)),
1295        );
1296        assert_eq!(
1297            memory.add_relocation_rule((-3, 6).into(), (0, 0).into()),
1298            Err(MemoryError::NonZeroOffset(6)),
1299        );
1300        assert_eq!(
1301            memory.add_relocation_rule((-1, 0).into(), (0, 0).into()),
1302            Err(MemoryError::DuplicatedRelocation(-1)),
1303        );
1304    }
1305
1306    #[test]
1307    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1308    fn relocate_value_bigint() {
1309        let mut memory = Memory::new();
1310        memory
1311            .add_relocation_rule((-1, 0).into(), (2, 0).into())
1312            .unwrap();
1313        memory
1314            .add_relocation_rule((-2, 0).into(), (2, 2).into())
1315            .unwrap();
1316
1317        // Test when value is Some(BigInt):
1318        assert_eq!(
1319            memory
1320                .relocate_value(&MaybeRelocatable::Int(Felt252::from(0)))
1321                .unwrap(),
1322            Cow::Owned(MaybeRelocatable::Int(Felt252::from(0))),
1323        );
1324    }
1325
1326    #[test]
1327    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1328    fn relocate_value_mayberelocatable() {
1329        let mut memory = Memory::new();
1330        memory
1331            .add_relocation_rule((-1, 0).into(), (2, 0).into())
1332            .unwrap();
1333        memory
1334            .add_relocation_rule((-2, 0).into(), (2, 2).into())
1335            .unwrap();
1336
1337        // Test when value is Some(MaybeRelocatable) with segment_index >= 0:
1338        assert_eq!(
1339            memory
1340                .relocate_value(&MaybeRelocatable::RelocatableValue((0, 0).into()))
1341                .unwrap(),
1342            Cow::Owned(MaybeRelocatable::RelocatableValue((0, 0).into())),
1343        );
1344        assert_eq!(
1345            memory
1346                .relocate_value(&MaybeRelocatable::RelocatableValue((5, 0).into()))
1347                .unwrap(),
1348            Cow::Owned(MaybeRelocatable::RelocatableValue((5, 0).into())),
1349        );
1350    }
1351
1352    #[test]
1353    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1354    fn relocate_value_mayberelocatable_temporary_segment_no_rules() {
1355        let mut memory = Memory::new();
1356        memory
1357            .add_relocation_rule((-1, 0).into(), (2, 0).into())
1358            .unwrap();
1359        memory
1360            .add_relocation_rule((-2, 0).into(), (2, 2).into())
1361            .unwrap();
1362
1363        // Test when value is Some(MaybeRelocatable) with segment_index < 0 and
1364        // there are no applicable relocation rules:
1365        assert_eq!(
1366            memory
1367                .relocate_value(&MaybeRelocatable::RelocatableValue((-5, 0).into()))
1368                .unwrap(),
1369            Cow::Owned(MaybeRelocatable::RelocatableValue((-5, 0).into())),
1370        );
1371    }
1372
1373    #[test]
1374    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1375    fn relocate_value_mayberelocatable_temporary_segment_rules() {
1376        let mut memory = Memory::new();
1377        memory
1378            .add_relocation_rule((-1, 0).into(), (2, 0).into())
1379            .unwrap();
1380        memory
1381            .add_relocation_rule((-2, 0).into(), (2, 2).into())
1382            .unwrap();
1383
1384        // Test when value is Some(MaybeRelocatable) with segment_index < 0 and
1385        // there are applicable relocation rules:
1386        assert_eq!(
1387            memory
1388                .relocate_value(&MaybeRelocatable::RelocatableValue((-1, 0).into()))
1389                .unwrap(),
1390            Cow::Owned(MaybeRelocatable::RelocatableValue((2, 0).into())),
1391        );
1392        assert_eq!(
1393            memory
1394                .relocate_value(&MaybeRelocatable::RelocatableValue((-2, 0).into()))
1395                .unwrap(),
1396            Cow::Owned(MaybeRelocatable::RelocatableValue((2, 2).into())),
1397        );
1398        assert_eq!(
1399            memory
1400                .relocate_value(&MaybeRelocatable::RelocatableValue((-1, 5).into()))
1401                .unwrap(),
1402            Cow::Owned(MaybeRelocatable::RelocatableValue((2, 5).into())),
1403        );
1404        assert_eq!(
1405            memory
1406                .relocate_value(&MaybeRelocatable::RelocatableValue((-2, 5).into()))
1407                .unwrap(),
1408            Cow::Owned(MaybeRelocatable::RelocatableValue((2, 7).into())),
1409        );
1410    }
1411
1412    #[test]
1413    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1414    fn get_range_for_continuous_memory() {
1415        let memory = memory![((1, 0), 2), ((1, 1), 3), ((1, 2), 4)];
1416
1417        let value1 = MaybeRelocatable::from(Felt252::from(2));
1418        let value2 = MaybeRelocatable::from(Felt252::from(3));
1419        let value3 = MaybeRelocatable::from(Felt252::from(4));
1420
1421        let expected_vec = vec![
1422            Some(Cow::Borrowed(&value1)),
1423            Some(Cow::Borrowed(&value2)),
1424            Some(Cow::Borrowed(&value3)),
1425        ];
1426        assert_eq!(memory.get_range(Relocatable::from((1, 0)), 3), expected_vec);
1427    }
1428
1429    #[test]
1430    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1431    fn get_range_for_non_continuous_memory() {
1432        let memory = memory![((1, 0), 2), ((1, 1), 3), ((1, 3), 4)];
1433
1434        let value1 = MaybeRelocatable::from(Felt252::from(2));
1435        let value2 = MaybeRelocatable::from(Felt252::from(3));
1436        let value3 = MaybeRelocatable::from(Felt252::from(4));
1437
1438        let expected_vec = vec![
1439            Some(Cow::Borrowed(&value1)),
1440            Some(Cow::Borrowed(&value2)),
1441            None,
1442            Some(Cow::Borrowed(&value3)),
1443        ];
1444        assert_eq!(memory.get_range(Relocatable::from((1, 0)), 4), expected_vec);
1445    }
1446
1447    #[test]
1448    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1449    fn get_continuous_range_for_continuous_memory() {
1450        let memory = memory![((1, 0), 2), ((1, 1), 3), ((1, 2), 4)];
1451
1452        let value1 = MaybeRelocatable::from(Felt252::from(2));
1453        let value2 = MaybeRelocatable::from(Felt252::from(3));
1454        let value3 = MaybeRelocatable::from(Felt252::from(4));
1455
1456        let expected_vec = vec![value1, value2, value3];
1457        assert_eq!(
1458            memory.get_continuous_range(Relocatable::from((1, 0)), 3),
1459            Ok(expected_vec)
1460        );
1461    }
1462
1463    #[test]
1464    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1465    fn get_continuous_range_for_non_continuous_memory() {
1466        let memory = memory![((1, 0), 2), ((1, 1), 3), ((1, 3), 4)];
1467
1468        assert_eq!(
1469            memory.get_continuous_range(Relocatable::from((1, 0)), 3),
1470            Err(MemoryError::GetRangeMemoryGap(Box::new(((1, 0).into(), 3))))
1471        );
1472    }
1473
1474    #[test]
1475    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1476    fn get_u32_range_ok() {
1477        let memory = memory![((0, 0), 0), ((0, 1), 1), ((0, 2), 4294967295), ((0, 3), 3)];
1478        let expected_vector = vec![1, 4294967295];
1479        assert_eq!(memory.get_u32_range((0, 1).into(), 2), Ok(expected_vector));
1480    }
1481
1482    #[test]
1483    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1484    fn get_u32_range_relocatable() {
1485        let memory = memory![((0, 0), 0), ((0, 1), 1), ((0, 2), (0, 0)), ((0, 3), 3)];
1486        assert_matches!(memory.get_u32_range((0, 1).into(), 2), Err(MemoryError::ExpectedInteger(bx)) if *bx == (0, 2).into());
1487    }
1488
1489    #[test]
1490    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1491    fn get_u32_range_over_32_bits() {
1492        let memory = memory![((0, 0), 0), ((0, 1), 1), ((0, 2), 4294967296), ((0, 3), 3)];
1493        assert_matches!(memory.get_u32_range((0, 1).into(), 2), Err(MemoryError::Math(MathError::Felt252ToU32Conversion(bx))) if *bx == Felt252::from(4294967296_u64));
1494    }
1495
1496    #[test]
1497    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1498    fn get_u32_range_memory_gap() {
1499        let memory = memory![((0, 0), 0), ((0, 1), 1), ((0, 3), 3)];
1500        assert_matches!(memory.get_u32_range((0, 1).into(), 3), Err(MemoryError::UnknownMemoryCell(bx)) if *bx == (0, 2).into());
1501    }
1502
1503    /// Test that relocate_memory() works when there are no relocation rules.
1504    #[test]
1505    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1506    fn relocate_memory_empty_relocation_rules() {
1507        let mut memory = memory![((0, 0), 1), ((0, 1), 2), ((0, 2), 3)];
1508
1509        assert_eq!(memory.relocate_memory(), Ok(()));
1510        check_memory!(memory, ((0, 0), 1), ((0, 1), 2), ((0, 2), 3));
1511    }
1512
1513    #[test]
1514    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1515    fn relocate_memory_new_segment_with_gap() {
1516        let mut memory = memory![
1517            ((0, 0), 1),
1518            ((0, 1), (-1, 0)),
1519            ((0, 2), 3),
1520            ((1, 0), (-1, 1)),
1521            ((1, 1), 5),
1522            ((1, 2), (-1, 2)),
1523            ((-1, 0), 7),
1524            ((-1, 1), 8),
1525            ((-1, 2), 9)
1526        ];
1527        memory
1528            .add_relocation_rule((-1, 0).into(), (2, 1).into())
1529            .unwrap();
1530        memory.data.push(vec![]);
1531
1532        assert_eq!(memory.relocate_memory(), Ok(()));
1533        check_memory!(
1534            memory,
1535            ((0, 0), 1),
1536            ((0, 1), (2, 1)),
1537            ((0, 2), 3),
1538            ((1, 0), (2, 2)),
1539            ((1, 1), 5),
1540            ((1, 2), (2, 3)),
1541            ((2, 1), 7),
1542            ((2, 2), 8),
1543            ((2, 3), 9)
1544        );
1545        assert!(memory.temp_data.is_empty());
1546    }
1547
1548    #[test]
1549    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1550    fn relocate_memory_new_segment() {
1551        let mut memory = memory![
1552            ((0, 0), 1),
1553            ((0, 1), (-1, 0)),
1554            ((0, 2), 3),
1555            ((1, 0), (-1, 1)),
1556            ((1, 1), 5),
1557            ((1, 2), (-1, 2)),
1558            ((-1, 0), 7),
1559            ((-1, 1), 8),
1560            ((-1, 2), 9)
1561        ];
1562        memory
1563            .add_relocation_rule((-1, 0).into(), (2, 0).into())
1564            .unwrap();
1565        memory.data.push(vec![]);
1566
1567        assert_eq!(memory.relocate_memory(), Ok(()));
1568
1569        check_memory!(
1570            memory,
1571            ((0, 0), 1),
1572            ((0, 1), (2, 0)),
1573            ((0, 2), 3),
1574            ((1, 0), (2, 1)),
1575            ((1, 1), 5),
1576            ((1, 2), (2, 2)),
1577            ((2, 0), 7),
1578            ((2, 1), 8),
1579            ((2, 2), 9)
1580        );
1581        assert!(memory.temp_data.is_empty());
1582    }
1583
1584    #[test]
1585    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1586    fn relocate_memory_new_segment_unallocated() {
1587        let mut memory = memory![
1588            ((0, 0), 1),
1589            ((0, 1), (-1, 0)),
1590            ((0, 2), 3),
1591            ((1, 0), (-1, 1)),
1592            ((1, 1), 5),
1593            ((1, 2), (-1, 2)),
1594            ((-1, 0), 7),
1595            ((-1, 1), 8),
1596            ((-1, 2), 9)
1597        ];
1598        memory
1599            .add_relocation_rule((-1, 0).into(), (2, 0).into())
1600            .unwrap();
1601
1602        assert_eq!(
1603            memory.relocate_memory(),
1604            Err(MemoryError::UnallocatedSegment(Box::new((2, 2))))
1605        );
1606    }
1607
1608    #[test]
1609    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1610    fn relocate_memory_into_existing_segment() {
1611        let mut memory = memory![
1612            ((0, 0), 1),
1613            ((0, 1), (-1, 0)),
1614            ((0, 2), 3),
1615            ((1, 0), (-1, 1)),
1616            ((1, 1), 5),
1617            ((1, 2), (-1, 2)),
1618            ((-1, 0), 7),
1619            ((-1, 1), 8),
1620            ((-1, 2), 9)
1621        ];
1622        memory
1623            .add_relocation_rule((-1, 0).into(), (1, 3).into())
1624            .unwrap();
1625
1626        assert_eq!(memory.relocate_memory(), Ok(()));
1627
1628        check_memory!(
1629            memory,
1630            ((0, 0), 1),
1631            ((0, 1), (1, 3)),
1632            ((0, 2), 3),
1633            ((1, 0), (1, 4)),
1634            ((1, 1), 5),
1635            ((1, 2), (1, 5)),
1636            ((1, 3), 7),
1637            ((1, 4), 8),
1638            ((1, 5), 9)
1639        );
1640        assert!(memory.temp_data.is_empty());
1641    }
1642
1643    #[test]
1644    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1645    fn relocate_memory_into_existing_segment_inconsistent_memory() {
1646        let mut memory = memory![
1647            ((0, 0), 1),
1648            ((0, 1), (-1, 0)),
1649            ((0, 2), 3),
1650            ((1, 0), (-1, 1)),
1651            ((1, 1), 5),
1652            ((1, 2), (-1, 2)),
1653            ((-1, 0), 7),
1654            ((-1, 1), 8),
1655            ((-1, 2), 9)
1656        ];
1657        memory
1658            .add_relocation_rule((-1, 0).into(), (1, 0).into())
1659            .unwrap();
1660
1661        assert_eq!(
1662            memory.relocate_memory(),
1663            Err(MemoryError::InconsistentMemory(Box::new((
1664                (1, 0).into(),
1665                (1, 1).into(),
1666                7.into(),
1667            ))))
1668        );
1669    }
1670
1671    #[test]
1672    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1673    fn relocate_memory_new_segment_2_temporary_segments_one_relocated() {
1674        let mut memory = memory![
1675            ((0, 0), 1),
1676            ((0, 1), (-1, 0)),
1677            ((0, 2), 3),
1678            ((1, 0), (-1, 1)),
1679            ((1, 1), 5),
1680            ((1, 2), (-1, 2)),
1681            ((-1, 0), 7),
1682            ((-1, 1), 8),
1683            ((-1, 2), 9),
1684            ((-2, 0), 10),
1685            ((-2, 1), 11)
1686        ];
1687        memory
1688            .add_relocation_rule((-1, 0).into(), (2, 0).into())
1689            .unwrap();
1690        memory.data.push(vec![]);
1691
1692        assert_eq!(memory.relocate_memory(), Ok(()));
1693        check_memory!(
1694            memory,
1695            ((0, 0), 1),
1696            ((0, 1), (2, 0)),
1697            ((0, 2), 3),
1698            ((1, 0), (2, 1)),
1699            ((1, 1), 5),
1700            ((1, 2), (2, 2)),
1701            ((2, 0), 7),
1702            ((2, 1), 8),
1703            ((2, 2), 9),
1704            ((-1, 0), 10),
1705            ((-1, 1), 11)
1706        );
1707    }
1708
1709    #[test]
1710    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1711    fn relocate_memory_new_segment_2_temporary_segments_relocated() {
1712        let mut memory = memory![
1713            ((0, 0), 1),
1714            ((0, 1), (-1, 0)),
1715            ((0, 2), 3),
1716            ((1, 0), (-1, 1)),
1717            ((1, 1), 5),
1718            ((1, 2), (-1, 2)),
1719            ((-1, 0), 7),
1720            ((-1, 1), 8),
1721            ((-1, 2), 9),
1722            ((-2, 0), 10),
1723            ((-2, 1), 11)
1724        ];
1725        memory.data.push(vec![]);
1726        memory
1727            .add_relocation_rule((-1, 0).into(), (2, 0).into())
1728            .unwrap();
1729        memory.data.push(vec![]);
1730        memory
1731            .add_relocation_rule((-2, 0).into(), (3, 0).into())
1732            .unwrap();
1733
1734        assert_eq!(memory.relocate_memory(), Ok(()));
1735
1736        check_memory!(
1737            memory,
1738            ((0, 0), 1),
1739            ((0, 1), (2, 0)),
1740            ((0, 2), 3),
1741            ((1, 0), (2, 1)),
1742            ((1, 1), 5),
1743            ((1, 2), (2, 2)),
1744            ((2, 0), 7),
1745            ((2, 1), 8),
1746            ((2, 2), 9),
1747            ((3, 0), 10),
1748            ((3, 1), 11)
1749        );
1750        assert!(memory.temp_data.is_empty());
1751    }
1752
1753    #[test]
1754    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1755    fn test_memory_display() {
1756        let memory = memory![
1757            ((0, 0), 1),
1758            ((0, 1), (-1, 0)),
1759            ((0, 2), 3),
1760            ((1, 0), (-1, 1)),
1761            ((1, 1), 5),
1762            ((1, 2), (-1, 2)),
1763            ((-1, 0), (-1, 0)),
1764            ((-1, 1), 8),
1765            ((-1, 2), 9)
1766        ];
1767
1768        assert_eq!(
1769            format!("{}", memory),
1770            "(-1,0) : -1:0\n(-1,1) : 8\n(-1,2) : 9\n(0,0) : 1\n(0,1) : -1:0\n(0,2) : 3\n(1,0) : -1:1\n(1,1) : 5\n(1,2) : -1:2\n");
1771    }
1772
1773    #[test]
1774    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1775    fn relocate_memory_into_existing_segment_temporary_values_in_temporary_memory() {
1776        let mut memory = memory![
1777            ((0, 0), 1),
1778            ((0, 1), (-1, 0)),
1779            ((0, 2), 3),
1780            ((1, 0), (-1, 1)),
1781            ((1, 1), 5),
1782            ((1, 2), (-1, 2)),
1783            ((-1, 0), (-1, 0)),
1784            ((-1, 1), 8),
1785            ((-1, 2), 9)
1786        ];
1787        memory
1788            .add_relocation_rule((-1, 0).into(), (1, 3).into())
1789            .unwrap();
1790
1791        assert_eq!(memory.relocate_memory(), Ok(()));
1792        check_memory!(
1793            memory,
1794            ((0, 0), 1),
1795            ((0, 1), (1, 3)),
1796            ((0, 2), 3),
1797            ((1, 0), (1, 4)),
1798            ((1, 1), 5),
1799            ((1, 2), (1, 5)),
1800            ((1, 3), (1, 3)),
1801            ((1, 4), 8),
1802            ((1, 5), 9)
1803        );
1804        assert!(memory.temp_data.is_empty());
1805    }
1806
1807    #[test]
1808    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1809    fn relocate_address_with_rules() {
1810        let mut memory = Memory::new();
1811        memory
1812            .add_relocation_rule((-1, 0).into(), (2, 0).into())
1813            .unwrap();
1814        memory
1815            .add_relocation_rule((-2, 0).into(), (2, 2).into())
1816            .unwrap();
1817
1818        assert_eq!(
1819            Memory::relocate_address((-1, 0).into(), &memory.relocation_rules).unwrap(),
1820            MaybeRelocatable::RelocatableValue((2, 0).into()),
1821        );
1822        assert_eq!(
1823            Memory::relocate_address((-2, 1).into(), &memory.relocation_rules).unwrap(),
1824            MaybeRelocatable::RelocatableValue((2, 3).into()),
1825        );
1826    }
1827
1828    #[test]
1829    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1830    fn relocate_address_no_rules() {
1831        let memory = Memory::new();
1832        assert_eq!(
1833            Memory::relocate_address((-1, 0).into(), &memory.relocation_rules).unwrap(),
1834            MaybeRelocatable::RelocatableValue((-1, 0).into()),
1835        );
1836        assert_eq!(
1837            Memory::relocate_address((-2, 1).into(), &memory.relocation_rules).unwrap(),
1838            MaybeRelocatable::RelocatableValue((-2, 1).into()),
1839        );
1840    }
1841
1842    #[test]
1843    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1844    fn relocate_address_real_addr() {
1845        let memory = Memory::new();
1846        assert_eq!(
1847            Memory::relocate_address((1, 0).into(), &memory.relocation_rules).unwrap(),
1848            MaybeRelocatable::RelocatableValue((1, 0).into()),
1849        );
1850        assert_eq!(
1851            Memory::relocate_address((1, 1).into(), &memory.relocation_rules).unwrap(),
1852            MaybeRelocatable::RelocatableValue((1, 1).into()),
1853        );
1854    }
1855
1856    #[test]
1857    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1858    #[cfg(feature = "extensive_hints")]
1859    fn relocate_address_to_integer() {
1860        let mut memory = Memory::new();
1861        memory
1862            .add_relocation_rule((-1, 0).into(), 0.into())
1863            .unwrap();
1864        memory
1865            .add_relocation_rule((-2, 0).into(), 42.into())
1866            .unwrap();
1867
1868        assert_eq!(
1869            Memory::relocate_address((-1, 0).into(), &memory.relocation_rules).unwrap(),
1870            MaybeRelocatable::Int(0.into()),
1871        );
1872        assert_eq!(
1873            Memory::relocate_address((-2, 0).into(), &memory.relocation_rules).unwrap(),
1874            MaybeRelocatable::Int(42.into()),
1875        );
1876    }
1877
1878    #[test]
1879    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1880    #[cfg(feature = "extensive_hints")]
1881    fn relocate_address_integer_no_duplicates() {
1882        let mut memory = Memory::new();
1883        memory
1884            .add_relocation_rule((-1, 0).into(), 1.into())
1885            .unwrap();
1886        assert_eq!(
1887            memory.add_relocation_rule((-1, 0).into(), 42.into()),
1888            Err(MemoryError::DuplicatedRelocation(-1))
1889        );
1890        assert_eq!(
1891            memory.add_relocation_rule((-1, 0).into(), (2, 0).into()),
1892            Err(MemoryError::DuplicatedRelocation(-1))
1893        );
1894
1895        assert_eq!(
1896            Memory::relocate_address((-1, 0).into(), &memory.relocation_rules).unwrap(),
1897            MaybeRelocatable::Int(1.into()),
1898        );
1899
1900        memory
1901            .add_relocation_rule((-2, 0).into(), (3, 0).into())
1902            .unwrap();
1903        assert_eq!(
1904            memory.add_relocation_rule((-2, 0).into(), 1.into()),
1905            Err(MemoryError::DuplicatedRelocation(-2))
1906        );
1907
1908        assert_eq!(
1909            Memory::relocate_address((-2, 0).into(), &memory.relocation_rules).unwrap(),
1910            MaybeRelocatable::RelocatableValue((3, 0).into()),
1911        );
1912    }
1913
1914    #[test]
1915    fn mark_address_as_accessed() {
1916        let mut memory = memory![((0, 0), 0)];
1917        assert!(!memory.data[0][0].is_accessed());
1918        memory.mark_as_accessed(relocatable!(0, 0));
1919        assert!(memory.data[0][0].is_accessed());
1920    }
1921
1922    #[test]
1923    fn get_amount_of_accessed_addresses_for_segment_valid() {
1924        let mut memory = memory![((0, 0), 0)];
1925        assert_eq!(
1926            memory.get_amount_of_accessed_addresses_for_segment(0),
1927            Some(0)
1928        );
1929        memory.mark_as_accessed(relocatable!(0, 0));
1930        assert_eq!(
1931            memory.get_amount_of_accessed_addresses_for_segment(0),
1932            Some(1)
1933        );
1934    }
1935
1936    #[test]
1937    fn get_amount_of_accessed_addresses_for_segment_invalid_segment() {
1938        let memory = memory![((0, 0), 0)];
1939        assert_eq!(memory.get_amount_of_accessed_addresses_for_segment(1), None);
1940    }
1941
1942    #[test]
1943    fn memory_cell_new_is_not_accessed() {
1944        let cell = MemoryCell::new(mayberelocatable!(1));
1945        assert!(!cell.is_accessed())
1946    }
1947
1948    #[test]
1949    fn memory_cell_mark_accessed() {
1950        let mut cell = MemoryCell::new(mayberelocatable!(1));
1951        cell.mark_accessed();
1952        assert!(cell.is_accessed())
1953    }
1954
1955    #[test]
1956    fn memory_cell_get_value() {
1957        let cell = MemoryCell::new(mayberelocatable!(1));
1958        assert_eq!(cell.get_value(), Some(mayberelocatable!(1)));
1959    }
1960
1961    use core::cmp::Ordering::*;
1962
1963    fn check_memcmp(
1964        lhs: (isize, usize),
1965        rhs: (isize, usize),
1966        len: usize,
1967        ord: Ordering,
1968        pos: usize,
1969    ) {
1970        let mem = memory![
1971            ((-2, 0), 1),
1972            ((-2, 1), (1, 1)),
1973            ((-2, 3), 0),
1974            ((-2, 4), 0),
1975            ((-1, 0), 1),
1976            ((-1, 1), (1, 1)),
1977            ((-1, 3), 0),
1978            ((-1, 4), 3),
1979            ((0, 0), 1),
1980            ((0, 1), (1, 1)),
1981            ((0, 3), 0),
1982            ((0, 4), 0),
1983            ((1, 0), 1),
1984            ((1, 1), (1, 1)),
1985            ((1, 3), 0),
1986            ((1, 4), 3)
1987        ];
1988        assert_eq!((ord, pos), mem.memcmp(lhs.into(), rhs.into(), len));
1989    }
1990
1991    #[test]
1992    fn insert_alloc_fails_gracefully() {
1993        let mut mem = memory![((0, 0), 1)];
1994        let err = mem.insert((0, usize::MAX >> 1).into(), Felt252::ONE);
1995        assert_eq!(err, Err(MemoryError::VecCapacityExceeded));
1996    }
1997
1998    #[test]
1999    fn insert_overflow_fails_gracefully() {
2000        let mut mem = memory![((0, 0), 1)];
2001        let err = mem.insert((0, usize::MAX).into(), Felt252::ONE);
2002        assert_eq!(err, Err(MemoryError::VecCapacityExceeded));
2003    }
2004
2005    #[test]
2006    fn memcmp() {
2007        check_memcmp((0, 0), (0, 0), 3, Equal, 3);
2008        check_memcmp((0, 0), (1, 0), 3, Equal, 3);
2009        check_memcmp((0, 0), (1, 0), 5, Less, 4);
2010        check_memcmp((1, 0), (0, 0), 5, Greater, 4);
2011        check_memcmp((2, 2), (2, 5), 8, Equal, 0);
2012        check_memcmp((0, 0), (2, 5), 8, Greater, 0);
2013        check_memcmp((2, 5), (0, 0), 8, Less, 0);
2014        check_memcmp((-2, 0), (-2, 0), 3, Equal, 3);
2015        check_memcmp((-2, 0), (-1, 0), 3, Equal, 3);
2016        check_memcmp((-2, 0), (-1, 0), 5, Less, 4);
2017        check_memcmp((-1, 0), (-2, 0), 5, Greater, 4);
2018        check_memcmp((-3, 2), (-3, 5), 8, Equal, 0);
2019        check_memcmp((-2, 0), (-3, 5), 8, Greater, 0);
2020        check_memcmp((-3, 5), (-2, 0), 8, Less, 0);
2021    }
2022
2023    #[test]
2024    fn cairo_pie_memory_from_memory() {
2025        let memory = memory![((8, 9), 3), ((1, 2), 5), ((7, 6), (1, 2))];
2026
2027        assert_eq!(
2028            CairoPieMemory::from(&memory),
2029            CairoPieMemory(vec![
2030                ((1, 2), MaybeRelocatable::from(5)),
2031                ((7, 6), MaybeRelocatable::from((1, 2))),
2032                ((8, 9), MaybeRelocatable::from(3))
2033            ])
2034        )
2035    }
2036}
cairo_vm/vm/vm_memory/memory.rs

cairo_vm/vm/vm_memory/
memory.rs
