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

cairo_vm/vm/vm_memory/
memory.rs
