cairo_vm/vm/
vm_core.rs

1use crate::math_utils::signed_felt;
2use crate::types::builtin_name::BuiltinName;
3#[cfg(feature = "extensive_hints")]
4use crate::types::program::HintRange;
5use crate::vm::vm_memory::memory::MemoryCell;
6use crate::{
7    hint_processor::{
8        builtin_hint_processor::blake2s_hash::blake2s_compress,
9        hint_processor_definition::HintProcessor,
10    },
11    typed_operations::{typed_add, typed_div, typed_mul, typed_sub},
12    types::{
13        errors::math_errors::MathError,
14        exec_scope::ExecutionScopes,
15        instruction::{
16            is_call_instruction, ApUpdate, FpUpdate, Instruction, Opcode, OpcodeExtension,
17            PcUpdate, Res,
18        },
19        relocatable::{MaybeRelocatable, Relocatable},
20    },
21    vm::{
22        context::run_context::RunContext,
23        decoding::decoder::decode_instruction,
24        errors::{
25            exec_scope_errors::ExecScopeError, memory_errors::MemoryError,
26            vm_errors::VirtualMachineError,
27        },
28        runners::builtin_runner::{
29            BuiltinRunner, OutputBuiltinRunner, RangeCheckBuiltinRunner, SignatureBuiltinRunner,
30        },
31        trace::trace_entry::TraceEntry,
32        vm_memory::memory_segments::MemorySegmentManager,
33    },
34};
35use std::{any::Any, borrow::Cow, collections::HashMap};
36
37use crate::Felt252;
38use core::cmp::Ordering;
39#[cfg(feature = "extensive_hints")]
40use core::num::NonZeroUsize;
41use num_traits::{ToPrimitive, Zero};
42
43use super::errors::runner_errors::RunnerError;
44use super::runners::builtin_runner::{ModBuiltinRunner, RC_N_PARTS_STANDARD};
45use super::runners::cairo_pie::CairoPie;
46
47const MAX_TRACEBACK_ENTRIES: u32 = 20;
48
49#[derive(PartialEq, Eq, Debug)]
50pub struct Operands {
51    dst: MaybeRelocatable,
52    res: Option<MaybeRelocatable>,
53    op0: MaybeRelocatable,
54    op1: MaybeRelocatable,
55}
56
57#[derive(PartialEq, Eq, Debug)]
58pub struct OperandsAddresses {
59    dst_addr: Relocatable,
60    op0_addr: Relocatable,
61    op1_addr: Relocatable,
62}
63
64#[derive(Clone, Debug, Copy, PartialEq, Eq, Hash)]
65pub enum ExtendedExecutionResourceType {
66    /// Describe opcode extensions that are not a builtin, yet imply added resources to the
67    /// execution.
68    BlakeFinalize,
69    Blake,
70}
71
72impl TryFrom<OpcodeExtension> for ExtendedExecutionResourceType {
73    type Error = &'static str; // Using a simple string instead of a custom struct
74
75    fn try_from(value: OpcodeExtension) -> Result<Self, Self::Error> {
76        match value {
77            OpcodeExtension::Blake => Ok(ExtendedExecutionResourceType::Blake),
78            OpcodeExtension::BlakeFinalize => Ok(ExtendedExecutionResourceType::BlakeFinalize),
79            _ => Err("Unsupported OpcodeExtension for ExtendedExecutionResourceType"),
80        }
81    }
82}
83
84#[derive(Default, Debug, Clone, Copy)]
85pub struct DeducedOperands(u8);
86
87impl DeducedOperands {
88    fn set_dst(&mut self, value: bool) {
89        self.0 |= value as u8;
90    }
91    fn set_op0(&mut self, value: bool) {
92        self.0 |= (value as u8) << 1;
93    }
94    fn set_op1(&mut self, value: bool) {
95        self.0 |= (value as u8) << 2;
96    }
97
98    fn was_dest_deducted(&self) -> bool {
99        self.0 & 1 != 0
100    }
101    fn was_op0_deducted(&self) -> bool {
102        self.0 & (1 << 1) != 0
103    }
104    fn was_op1_deducted(&self) -> bool {
105        self.0 & (1 << 2) != 0
106    }
107}
108
109pub struct VirtualMachine {
110    pub(crate) run_context: RunContext,
111    pub builtin_runners: Vec<BuiltinRunner>,
112    /// A simulated builtin is being verified in the executed Cairo
113    /// code (so proving them only involves proving cairo steps), rather
114    /// than being outputted as their own segment and proven later using
115    /// dedicated AIRs.
116    ///
117    /// These builtins won't be included in the layout, hence the builtin
118    /// segment pointer won't be passed as argument to the program. The program
119    /// needs a mechanism for obtaining the segment pointer. See example
120    /// implementation of this mechanism in `simulated_builtins.cairo`, or
121    /// cairo-lang's `simple_bootloader.cairo`.
122    pub simulated_builtin_runners: Vec<BuiltinRunner>,
123    pub(crate) extended_resource_counter: HashMap<ExtendedExecutionResourceType, u32>,
124    pub segments: MemorySegmentManager,
125    pub(crate) trace: Option<Vec<TraceEntry>>,
126    pub(crate) current_step: usize,
127    pub(crate) rc_limits: Option<(isize, isize)>,
128    skip_instruction_execution: bool,
129    run_finished: bool,
130    // This flag is a parallel to the one in `struct CairoRunConfig`.
131    pub(crate) disable_trace_padding: bool,
132    instruction_cache: Vec<Option<Instruction>>,
133    #[cfg(feature = "test_utils")]
134    pub(crate) hooks: Option<Box<dyn crate::vm::hooks::StepHooks>>,
135    pub(crate) relocation_table: Option<Vec<usize>>,
136}
137
138impl VirtualMachine {
139    pub fn new(trace_enabled: bool, disable_trace_padding: bool) -> VirtualMachine {
140        let run_context = RunContext {
141            pc: Relocatable::from((0, 0)),
142            ap: 0,
143            fp: 0,
144        };
145
146        let trace = if trace_enabled {
147            Some(Vec::<TraceEntry>::new())
148        } else {
149            None
150        };
151
152        VirtualMachine {
153            run_context,
154            builtin_runners: Vec::new(),
155            simulated_builtin_runners: Vec::new(),
156            extended_resource_counter: HashMap::new(),
157            trace,
158            current_step: 0,
159            skip_instruction_execution: false,
160            segments: MemorySegmentManager::new(),
161            rc_limits: None,
162            run_finished: false,
163            disable_trace_padding,
164            instruction_cache: Vec::new(),
165            #[cfg(feature = "test_utils")]
166            hooks: None,
167            relocation_table: None,
168        }
169    }
170
171    pub fn compute_segments_effective_sizes(&mut self) {
172        self.segments.compute_effective_sizes();
173    }
174
175    fn update_fp(
176        &mut self,
177        instruction: &Instruction,
178        operands: &Operands,
179    ) -> Result<(), VirtualMachineError> {
180        let new_fp_offset: usize = match instruction.fp_update {
181            FpUpdate::APPlus2 => self.run_context.ap + 2,
182            FpUpdate::Dst => match operands.dst {
183                MaybeRelocatable::RelocatableValue(ref rel) => rel.offset,
184                MaybeRelocatable::Int(ref num) => num
185                    .to_usize()
186                    .ok_or_else(|| MathError::Felt252ToUsizeConversion(Box::new(*num)))?,
187            },
188            FpUpdate::Regular => return Ok(()),
189        };
190        self.run_context.fp = new_fp_offset;
191        Ok(())
192    }
193
194    fn update_ap(
195        &mut self,
196        instruction: &Instruction,
197        operands: &Operands,
198    ) -> Result<(), VirtualMachineError> {
199        let new_apset: usize = match instruction.ap_update {
200            ApUpdate::Add => match &operands.res {
201                Some(res) => (self.run_context.get_ap() + res)?.offset,
202                None => return Err(VirtualMachineError::UnconstrainedResAdd),
203            },
204            ApUpdate::Add1 => self.run_context.ap + 1,
205            ApUpdate::Add2 => self.run_context.ap + 2,
206            ApUpdate::Regular => return Ok(()),
207        };
208        self.run_context.ap = new_apset;
209        Ok(())
210    }
211
212    fn update_pc(
213        &mut self,
214        instruction: &Instruction,
215        operands: &Operands,
216    ) -> Result<(), VirtualMachineError> {
217        let new_pc: Relocatable = match instruction.pc_update {
218            PcUpdate::Regular => (self.run_context.pc + instruction.size())?,
219            PcUpdate::Jump => match operands.res.as_ref().and_then(|x| x.get_relocatable()) {
220                Some(ref res) => *res,
221                None => return Err(VirtualMachineError::UnconstrainedResJump),
222            },
223            PcUpdate::JumpRel => match &operands.res {
224                Some(res) => match res {
225                    MaybeRelocatable::Int(num_res) => (self.run_context.pc + num_res)?,
226                    _ => return Err(VirtualMachineError::JumpRelNotInt),
227                },
228                None => return Err(VirtualMachineError::UnconstrainedResJumpRel),
229            },
230            PcUpdate::Jnz => match VirtualMachine::is_zero(&operands.dst) {
231                true => (self.run_context.pc + instruction.size())?,
232                false => (self.run_context.pc + &operands.op1)?,
233            },
234        };
235        self.run_context.pc = new_pc;
236        Ok(())
237    }
238
239    fn update_registers(
240        &mut self,
241        instruction: &Instruction,
242        operands: Operands,
243    ) -> Result<(), VirtualMachineError> {
244        self.update_fp(instruction, &operands)?;
245        self.update_ap(instruction, &operands)?;
246        self.update_pc(instruction, &operands)?;
247        Ok(())
248    }
249
250    /// Returns true if the value is zero
251    /// Used for JNZ instructions
252    fn is_zero(addr: &MaybeRelocatable) -> bool {
253        match addr {
254            MaybeRelocatable::Int(num) => num.is_zero(),
255            _ => false,
256        }
257    }
258
259    ///Returns a tuple (deduced_op0, deduced_res).
260    ///Deduces the value of op0 if possible (based on dst and op1). Otherwise, returns None.
261    ///If res was already deduced, returns its deduced value as well.
262    fn deduce_op0(
263        &self,
264        instruction: &Instruction,
265        dst: Option<&MaybeRelocatable>,
266        op1: Option<&MaybeRelocatable>,
267    ) -> Result<(Option<MaybeRelocatable>, Option<MaybeRelocatable>), VirtualMachineError> {
268        match instruction.opcode {
269            Opcode::Call => Ok((
270                Some(MaybeRelocatable::from(
271                    (self.run_context.pc + instruction.size())?,
272                )),
273                None,
274            )),
275            Opcode::AssertEq => match (&instruction.res, dst, op1) {
276                (Res::Add, Some(dst_addr), Some(op1_addr)) => Ok((
277                    Some(typed_sub(dst_addr, op1_addr, instruction.opcode_extension)?),
278                    dst.cloned(),
279                )),
280                (
281                    Res::Mul,
282                    Some(MaybeRelocatable::Int(num_dst)),
283                    Some(MaybeRelocatable::Int(num_op1)),
284                ) if !num_op1.is_zero() => {
285                    let num_op0 = typed_div(num_dst, num_op1, instruction.opcode_extension)?;
286                    Ok((Some(MaybeRelocatable::Int(num_op0)), dst.cloned()))
287                }
288                _ => Ok((None, None)),
289            },
290            _ => Ok((None, None)),
291        }
292    }
293
294    /// Returns a tuple (deduced_op1, deduced_res).
295    ///Deduces the value of op1 if possible (based on dst and op0). Otherwise, returns None.
296    ///If res was already deduced, returns its deduced value as well.
297    fn deduce_op1(
298        &self,
299        instruction: &Instruction,
300        dst: Option<&MaybeRelocatable>,
301        op0: Option<MaybeRelocatable>,
302    ) -> Result<(Option<MaybeRelocatable>, Option<MaybeRelocatable>), VirtualMachineError> {
303        if let Opcode::AssertEq = instruction.opcode {
304            match instruction.res {
305                Res::Op1 => return Ok((dst.cloned(), dst.cloned())),
306                Res::Add => {
307                    return Ok((
308                        dst.zip(op0).and_then(|(dst, op0)| {
309                            typed_sub(dst, &op0, instruction.opcode_extension).ok()
310                        }),
311                        dst.cloned(),
312                    ))
313                }
314                Res::Mul => match (dst, op0) {
315                    (
316                        Some(MaybeRelocatable::Int(num_dst)),
317                        Some(MaybeRelocatable::Int(num_op0)),
318                    ) if !num_op0.is_zero() => {
319                        let num_op1 = typed_div(num_dst, &num_op0, instruction.opcode_extension)?;
320                        return Ok((Some(MaybeRelocatable::Int(num_op1)), dst.cloned()));
321                    }
322                    _ => (),
323                },
324                _ => (),
325            };
326        };
327        Ok((None, None))
328    }
329
330    fn deduce_memory_cell(
331        &self,
332        address: Relocatable,
333    ) -> Result<Option<MaybeRelocatable>, VirtualMachineError> {
334        let memory = &self.segments.memory;
335
336        for runner in self
337            .builtin_runners
338            .iter()
339            .chain(self.simulated_builtin_runners.iter())
340        {
341            if runner.base() as isize == address.segment_index {
342                return runner
343                    .deduce_memory_cell(address, memory)
344                    .map_err(VirtualMachineError::RunnerError);
345            }
346        }
347        Ok(None)
348    }
349
350    ///Computes the value of res if possible
351    fn compute_res(
352        &self,
353        instruction: &Instruction,
354        op0: &MaybeRelocatable,
355        op1: &MaybeRelocatable,
356    ) -> Result<Option<MaybeRelocatable>, VirtualMachineError> {
357        match instruction.res {
358            Res::Op1 => Ok(Some(op1.clone())),
359            Res::Add => Ok(Some(typed_add(op0, op1, instruction.opcode_extension)?)),
360            Res::Mul => Ok(Some(typed_mul(op0, op1, instruction.opcode_extension)?)),
361            Res::Unconstrained => Ok(None),
362        }
363    }
364
365    fn deduce_dst(
366        &self,
367        instruction: &Instruction,
368        res: &Option<MaybeRelocatable>,
369    ) -> Result<MaybeRelocatable, VirtualMachineError> {
370        let dst = match (instruction.opcode, res) {
371            (Opcode::AssertEq, Some(res)) => res.clone(),
372            (Opcode::Call, _) => MaybeRelocatable::from(self.run_context.get_fp()),
373            _ => return Err(VirtualMachineError::NoDst),
374        };
375        Ok(dst)
376    }
377
378    fn opcode_assertions(
379        &self,
380        instruction: &Instruction,
381        operands: &Operands,
382    ) -> Result<(), VirtualMachineError> {
383        match instruction.opcode {
384            Opcode::AssertEq => match &operands.res {
385                None => Err(VirtualMachineError::UnconstrainedResAssertEq),
386                Some(res) if res != &operands.dst => Err(VirtualMachineError::DiffAssertValues(
387                    Box::new((operands.dst.clone(), res.clone())),
388                )),
389                _ => Ok(()),
390            },
391            Opcode::Call => {
392                let return_pc = MaybeRelocatable::from((self.run_context.pc + instruction.size())?);
393                if operands.op0 != return_pc {
394                    return Err(VirtualMachineError::CantWriteReturnPc(Box::new((
395                        operands.op0.clone(),
396                        return_pc,
397                    ))));
398                };
399
400                if MaybeRelocatable::from(self.run_context.get_fp()) != operands.dst {
401                    return Err(VirtualMachineError::CantWriteReturnFp(Box::new((
402                        operands.dst.clone(),
403                        MaybeRelocatable::from(self.run_context.get_fp()),
404                    ))));
405                };
406                Ok(())
407            }
408            _ => Ok(()),
409        }
410    }
411
412    fn insert_deduced_operands(
413        &mut self,
414        deduced_operands: DeducedOperands,
415        operands: &Operands,
416        operands_addresses: &OperandsAddresses,
417    ) -> Result<(), VirtualMachineError> {
418        if deduced_operands.was_op0_deducted() {
419            self.segments
420                .memory
421                .insert(operands_addresses.op0_addr, &operands.op0)
422                .map_err(VirtualMachineError::Memory)?;
423        }
424        if deduced_operands.was_op1_deducted() {
425            self.segments
426                .memory
427                .insert(operands_addresses.op1_addr, &operands.op1)
428                .map_err(VirtualMachineError::Memory)?;
429        }
430        if deduced_operands.was_dest_deducted() {
431            self.segments
432                .memory
433                .insert(operands_addresses.dst_addr, &operands.dst)
434                .map_err(VirtualMachineError::Memory)?;
435        }
436
437        Ok(())
438    }
439
440    fn run_instruction(&mut self, instruction: &Instruction) -> Result<(), VirtualMachineError> {
441        let (operands, operands_addresses, deduced_operands) =
442            self.compute_operands(instruction)?;
443        self.insert_deduced_operands(deduced_operands, &operands, &operands_addresses)?;
444        self.opcode_assertions(instruction, &operands)?;
445
446        if let Some(ref mut trace) = &mut self.trace {
447            trace.push(TraceEntry {
448                pc: self.run_context.pc,
449                ap: self.run_context.ap,
450                fp: self.run_context.fp,
451            });
452        }
453
454        // Update range check limits
455        const OFFSET_BITS: u32 = 16;
456        let (off0, off1, off2) = (
457            instruction.off0 + (1_isize << (OFFSET_BITS - 1)),
458            instruction.off1 + (1_isize << (OFFSET_BITS - 1)),
459            instruction.off2 + (1_isize << (OFFSET_BITS - 1)),
460        );
461        let (min, max) = self.rc_limits.unwrap_or((off0, off0));
462        self.rc_limits = Some((
463            min.min(off0).min(off1).min(off2),
464            max.max(off0).max(off1).max(off2),
465        ));
466
467        self.segments
468            .memory
469            .mark_as_accessed(operands_addresses.dst_addr);
470        self.segments
471            .memory
472            .mark_as_accessed(operands_addresses.op0_addr);
473        self.segments
474            .memory
475            .mark_as_accessed(operands_addresses.op1_addr);
476        self.segments.memory.mark_as_accessed(self.run_context.pc);
477
478        if instruction.opcode_extension == OpcodeExtension::Blake
479            || instruction.opcode_extension == OpcodeExtension::BlakeFinalize
480        {
481            self.handle_blake2s_instruction(
482                &operands_addresses,
483                instruction.opcode_extension == OpcodeExtension::BlakeFinalize,
484            )?;
485
486            let resource_type = <ExtendedExecutionResourceType as TryFrom<_>>::try_from(
487                instruction.opcode_extension,
488            )
489            .expect("OpcodeExtension Blake and BlakeFinalize should always map to ExtendedExecutionResourceType");
490
491            *self
492                .extended_resource_counter
493                .entry(resource_type)
494                .or_insert(0) += 1;
495        }
496
497        self.update_registers(instruction, operands)?;
498        self.current_step += 1;
499
500        Ok(())
501    }
502
503    /// Executes a Blake2s or Blake2sLastBlock instruction.
504    /// Expects operands to be RelocatableValue and to point to segments of memory.
505    /// op0 is expected to point to a sequence of 8 u32 values (state).
506    /// op1 is expected to point to a sequence of 16 u32 values (message).
507    /// dst is expected hold the u32 value of the counter (t).
508    /// [ap] is expected to point to a sequence of 8 cells each being either unitialised or
509    /// containing the Blake2s compression output at that index.
510    /// Deviation from the aforementioned expectations will result in an error.
511    /// The instruction will update the memory segment pointed by [ap] with the new state.
512    /// Note: the byte counter should count the number of message bytes processed so far including
513    /// the current portion of the message (i.e. it starts at 64, not 0).
514    fn handle_blake2s_instruction(
515        &mut self,
516        operands_addresses: &OperandsAddresses,
517        is_last_block: bool,
518    ) -> Result<(), VirtualMachineError> {
519        let counter = self.segments.memory.get_u32(operands_addresses.dst_addr)?;
520
521        let state: [u32; 8] = (self.get_u32_range(
522            self.segments
523                .memory
524                .get_relocatable(operands_addresses.op0_addr)?,
525            8,
526        )?)
527        .try_into()
528        .map_err(|_| VirtualMachineError::Blake2sInvalidOperand(0, 8))?;
529
530        let message: [u32; 16] = (self.get_u32_range(
531            self.segments
532                .memory
533                .get_relocatable(operands_addresses.op1_addr)?,
534            16,
535        )?)
536        .try_into()
537        .map_err(|_| VirtualMachineError::Blake2sInvalidOperand(1, 16))?;
538
539        let f0 = if is_last_block { 0xffffffff } else { 0 };
540
541        let ap = self.run_context.get_ap();
542        let output_address = self.segments.memory.get_relocatable(ap)?;
543
544        let new_state = blake2s_compress(&state, &message, counter, 0, f0, 0);
545
546        for (i, &val) in new_state.iter().enumerate() {
547            self.segments.memory.insert_as_accessed(
548                (output_address + i)?,
549                MaybeRelocatable::Int(Felt252::from(val)),
550            )?;
551        }
552
553        Ok(())
554    }
555
556    fn decode_current_instruction(&self) -> Result<Instruction, VirtualMachineError> {
557        let instruction = self
558            .segments
559            .memory
560            .get_integer(self.run_context.pc)?
561            .to_u128()
562            .ok_or(VirtualMachineError::InvalidInstructionEncoding)?;
563        decode_instruction(instruction)
564    }
565
566    #[cfg(not(feature = "extensive_hints"))]
567    pub fn step_hint(
568        &mut self,
569        hint_processor: &mut dyn HintProcessor,
570        exec_scopes: &mut ExecutionScopes,
571        hint_datas: &[Box<dyn Any>],
572    ) -> Result<(), VirtualMachineError> {
573        for (hint_index, hint_data) in hint_datas.iter().enumerate() {
574            hint_processor
575                .execute_hint(self, exec_scopes, hint_data)
576                .map_err(|err| VirtualMachineError::Hint(Box::new((hint_index, err))))?
577        }
578        Ok(())
579    }
580
581    #[cfg(feature = "extensive_hints")]
582    pub fn step_hint(
583        &mut self,
584        hint_processor: &mut dyn HintProcessor,
585        exec_scopes: &mut ExecutionScopes,
586        hint_datas: &mut Vec<Box<dyn Any>>,
587        hint_ranges: &mut HashMap<Relocatable, HintRange>,
588    ) -> Result<(), VirtualMachineError> {
589        // Check if there is a hint range for the current pc
590        if let Some((s, l)) = hint_ranges.get(&self.run_context.pc) {
591            // Re-binding to avoid mutability problems
592            let s = *s;
593            // Execute each hint for the given range
594            for idx in s..(s + l.get()) {
595                let hint_extension = hint_processor
596                    .execute_hint_extensive(
597                        self,
598                        exec_scopes,
599                        hint_datas.get(idx).ok_or(VirtualMachineError::Unexpected)?,
600                    )
601                    .map_err(|err| VirtualMachineError::Hint(Box::new((idx - s, err))))?;
602                // Update the hint_ranges & hint_datas with the hints added by the executed hint
603                for (hint_pc, hints) in hint_extension {
604                    if let Ok(len) = NonZeroUsize::try_from(hints.len()) {
605                        hint_ranges.insert(hint_pc, (hint_datas.len(), len));
606                        hint_datas.extend(hints);
607                    }
608                }
609            }
610        }
611        Ok(())
612    }
613
614    pub fn step_instruction(&mut self) -> Result<(), VirtualMachineError> {
615        if self.run_context.pc.segment_index == 0 {
616            // Run instructions from program segment, using instruction cache
617            let pc = self.run_context.pc.offset;
618
619            if self.segments.memory.data[0].len() <= pc {
620                return Err(MemoryError::UnknownMemoryCell(Box::new((0, pc).into())))?;
621            }
622
623            let mut inst_cache = core::mem::take(&mut self.instruction_cache);
624            inst_cache.resize((pc + 1).max(inst_cache.len()), None);
625
626            let instruction = inst_cache.get_mut(pc).unwrap();
627            if instruction.is_none() {
628                *instruction = Some(self.decode_current_instruction()?);
629            }
630            let instruction = instruction.as_ref().unwrap();
631
632            if !self.skip_instruction_execution {
633                self.run_instruction(instruction)?;
634            } else {
635                self.run_context.pc += instruction.size();
636                self.skip_instruction_execution = false;
637            }
638            self.instruction_cache = inst_cache;
639        } else {
640            // Run instructions from programs loaded in other segments, without instruction cache
641            let instruction = self.decode_current_instruction()?;
642
643            if !self.skip_instruction_execution {
644                self.run_instruction(&instruction)?;
645            } else {
646                self.run_context.pc += instruction.size();
647                self.skip_instruction_execution = false;
648            }
649        }
650        Ok(())
651    }
652
653    pub fn step(
654        &mut self,
655        hint_processor: &mut dyn HintProcessor,
656        exec_scopes: &mut ExecutionScopes,
657        #[cfg(feature = "extensive_hints")] hint_datas: &mut Vec<Box<dyn Any>>,
658        #[cfg(not(feature = "extensive_hints"))] hint_datas: &[Box<dyn Any>],
659        #[cfg(feature = "extensive_hints")] hint_ranges: &mut HashMap<Relocatable, HintRange>,
660        #[cfg(feature = "test_utils")] constants: &HashMap<String, Felt252>,
661    ) -> Result<(), VirtualMachineError> {
662        self.step_hint(
663            hint_processor,
664            exec_scopes,
665            hint_datas,
666            #[cfg(feature = "extensive_hints")]
667            hint_ranges,
668        )?;
669
670        #[cfg(feature = "test_utils")]
671        self.execute_pre_step_instruction(hint_processor, exec_scopes, hint_datas, constants)?;
672        self.step_instruction()?;
673        #[cfg(feature = "test_utils")]
674        self.execute_post_step_instruction(hint_processor, exec_scopes, hint_datas, constants)?;
675
676        Ok(())
677    }
678
679    fn compute_op0_deductions(
680        &self,
681        op0_addr: Relocatable,
682        res: &mut Option<MaybeRelocatable>,
683        instruction: &Instruction,
684        dst_op: &Option<MaybeRelocatable>,
685        op1_op: &Option<MaybeRelocatable>,
686    ) -> Result<MaybeRelocatable, VirtualMachineError> {
687        let op0_op = match self.deduce_memory_cell(op0_addr)? {
688            None => {
689                let op0;
690                (op0, *res) = self.deduce_op0(instruction, dst_op.as_ref(), op1_op.as_ref())?;
691                op0
692            }
693            deduced_memory_cell => deduced_memory_cell,
694        };
695        let op0 = op0_op.ok_or_else(|| {
696            VirtualMachineError::FailedToComputeOperands(Box::new(("op0".to_string(), op0_addr)))
697        })?;
698        Ok(op0)
699    }
700
701    fn compute_op1_deductions(
702        &self,
703        op1_addr: Relocatable,
704        res: &mut Option<MaybeRelocatable>,
705        instruction: &Instruction,
706        dst_op: &Option<MaybeRelocatable>,
707        op0: &MaybeRelocatable,
708    ) -> Result<MaybeRelocatable, VirtualMachineError> {
709        let op1_op = match self.deduce_memory_cell(op1_addr)? {
710            None => {
711                let (op1, deduced_res) =
712                    self.deduce_op1(instruction, dst_op.as_ref(), Some(op0.clone()))?;
713                if res.is_none() {
714                    *res = deduced_res
715                }
716                op1
717            }
718            deduced_memory_cell => deduced_memory_cell,
719        };
720        let op1 = op1_op.ok_or_else(|| {
721            VirtualMachineError::FailedToComputeOperands(Box::new(("op1".to_string(), op1_addr)))
722        })?;
723        Ok(op1)
724    }
725
726    /// Compute operands and result, trying to deduce them if normal memory access returns a None
727    /// value.
728    pub fn compute_operands(
729        &self,
730        instruction: &Instruction,
731    ) -> Result<(Operands, OperandsAddresses, DeducedOperands), VirtualMachineError> {
732        //Get operands from memory
733        let dst_addr = self.run_context.compute_dst_addr(instruction)?;
734        let dst_op = self.segments.memory.get(&dst_addr).map(Cow::into_owned);
735
736        let op0_addr = self.run_context.compute_op0_addr(instruction)?;
737        let op0_op = self.segments.memory.get(&op0_addr).map(Cow::into_owned);
738
739        let op1_addr = self
740            .run_context
741            .compute_op1_addr(instruction, op0_op.as_ref())?;
742        let op1_op = self.segments.memory.get(&op1_addr).map(Cow::into_owned);
743
744        let mut res: Option<MaybeRelocatable> = None;
745
746        let mut deduced_operands = DeducedOperands::default();
747
748        //Deduce op0 if it wasnt previously computed
749        let op0 = match op0_op {
750            Some(op0) => op0,
751            None => {
752                deduced_operands.set_op0(true);
753                self.compute_op0_deductions(op0_addr, &mut res, instruction, &dst_op, &op1_op)?
754            }
755        };
756
757        //Deduce op1 if it wasnt previously computed
758        let op1 = match op1_op {
759            Some(op1) => op1,
760            None => {
761                deduced_operands.set_op1(true);
762                self.compute_op1_deductions(op1_addr, &mut res, instruction, &dst_op, &op0)?
763            }
764        };
765
766        //Compute res if it wasnt previously deduced
767        if res.is_none() {
768            res = self.compute_res(instruction, &op0, &op1)?;
769        }
770
771        //Deduce dst if it wasnt previously computed
772        let dst = match dst_op {
773            Some(dst) => dst,
774            None => {
775                deduced_operands.set_dst(true);
776                self.deduce_dst(instruction, &res)?
777            }
778        };
779        let accessed_addresses = OperandsAddresses {
780            dst_addr,
781            op0_addr,
782            op1_addr,
783        };
784        Ok((
785            Operands { dst, op0, op1, res },
786            accessed_addresses,
787            deduced_operands,
788        ))
789    }
790
791    /// Updates the memory with missing built-in deductions and verifies the existing ones.
792    pub fn complete_builtin_auto_deductions(&mut self) -> Result<(), VirtualMachineError> {
793        for builtin in self.builtin_runners.iter() {
794            let builtin_index: usize = builtin.base();
795
796            // Output and SegmentArena do not need to be auto-deduced in the memory.
797            if matches!(
798                builtin,
799                BuiltinRunner::Output(_) | BuiltinRunner::SegmentArena(_)
800            ) {
801                continue;
802            }
803
804            // Extend the segment size to a multiple of the number of cells per instance.
805            let current_builtin_segment = &mut self.segments.memory.data[builtin_index];
806            let len = current_builtin_segment.len();
807            let cells_per_instance = builtin.cells_per_instance() as usize;
808            current_builtin_segment.resize(
809                len.div_ceil(cells_per_instance) * cells_per_instance,
810                MemoryCell::NONE,
811            );
812
813            let mut missing_values: Vec<(usize, MemoryCell)> = vec![];
814
815            for (offset, cell) in self.segments.memory.data[builtin_index].iter().enumerate() {
816                if let Some(deduced_memory_cell) = builtin
817                    .deduce_memory_cell(
818                        Relocatable::from((builtin_index as isize, offset)),
819                        &self.segments.memory,
820                    )
821                    .map_err(VirtualMachineError::RunnerError)?
822                {
823                    match cell.get_value() {
824                        Some(memory_value) => {
825                            // Checks that the value in the memory is correct.
826                            if memory_value != deduced_memory_cell {
827                                return Err(VirtualMachineError::InconsistentAutoDeduction(
828                                    Box::new((
829                                        builtin.name(),
830                                        deduced_memory_cell,
831                                        Some(memory_value),
832                                    )),
833                                ));
834                            }
835                        }
836                        None => {
837                            // Collect value to be stored in memory.
838                            missing_values.push((offset, MemoryCell::new(deduced_memory_cell)));
839                        }
840                    }
841                }
842            }
843
844            for (offset, value) in missing_values {
845                self.segments.memory.data[builtin_index][offset] = value;
846            }
847        }
848        Ok(())
849    }
850
851    ///Makes sure that all assigned memory cells are consistent with their auto deduction rules.
852    pub fn verify_auto_deductions(&self) -> Result<(), VirtualMachineError> {
853        for builtin in self.builtin_runners.iter() {
854            let index: usize = builtin.base();
855            for (offset, value) in self.segments.memory.data[index].iter().enumerate() {
856                if let Some(deduced_memory_cell) = builtin
857                    .deduce_memory_cell(
858                        Relocatable::from((index as isize, offset)),
859                        &self.segments.memory,
860                    )
861                    .map_err(VirtualMachineError::RunnerError)?
862                {
863                    let value = value.get_value();
864                    if Some(&deduced_memory_cell) != value.as_ref() && value.is_some() {
865                        return Err(VirtualMachineError::InconsistentAutoDeduction(Box::new((
866                            builtin.name(),
867                            deduced_memory_cell,
868                            value,
869                        ))));
870                    }
871                }
872            }
873        }
874        Ok(())
875    }
876
877    //Makes sure that the value at the given address is consistent with the auto deduction rules.
878    pub fn verify_auto_deductions_for_addr(
879        &self,
880        addr: Relocatable,
881        builtin: &BuiltinRunner,
882    ) -> Result<(), VirtualMachineError> {
883        let value = match builtin.deduce_memory_cell(addr, &self.segments.memory)? {
884            Some(value) => value,
885            None => return Ok(()),
886        };
887        let current_value = match self.segments.memory.get(&addr) {
888            Some(value) => value.into_owned(),
889            None => return Ok(()),
890        };
891        if value != current_value {
892            return Err(VirtualMachineError::InconsistentAutoDeduction(Box::new((
893                builtin.name(),
894                value,
895                Some(current_value),
896            ))));
897        }
898        Ok(())
899    }
900
901    pub fn end_run(
902        &mut self,
903        exec_scopes: &ExecutionScopes,
904        fill_holes: bool,
905    ) -> Result<(), VirtualMachineError> {
906        if fill_holes {
907            self.complete_builtin_auto_deductions()?;
908        } else {
909            self.verify_auto_deductions()?;
910        }
911        self.run_finished = true;
912        match exec_scopes.data.len() {
913            1 => Ok(()),
914            _ => Err(ExecScopeError::NoScopeError.into()),
915        }
916    }
917
918    pub fn mark_address_range_as_accessed(
919        &mut self,
920        base: Relocatable,
921        len: usize,
922    ) -> Result<(), VirtualMachineError> {
923        if !self.run_finished {
924            return Err(VirtualMachineError::RunNotFinished);
925        }
926        for i in 0..len {
927            self.segments.memory.mark_as_accessed((base + i)?);
928        }
929        Ok(())
930    }
931
932    /// Returns the values (fp, pc) corresponding to each call instruction in the traceback.
933    /// Returns the most recent call last.
934    pub fn get_traceback_entries(&self) -> Vec<(Relocatable, Relocatable)> {
935        let mut entries = Vec::<(Relocatable, Relocatable)>::new();
936        let mut fp = Relocatable::from((1, self.run_context.fp));
937        // Fetch the fp and pc traceback entries
938        for _ in 0..MAX_TRACEBACK_ENTRIES {
939            // Get return pc
940            let ret_pc = match (fp - 1)
941                .ok()
942                .map(|r| self.segments.memory.get_relocatable(r))
943            {
944                Some(Ok(opt_pc)) => opt_pc,
945                _ => break,
946            };
947            // Get fp traceback
948            match (fp - 2)
949                .ok()
950                .map(|r| self.segments.memory.get_relocatable(r))
951            {
952                Some(Ok(opt_fp)) if opt_fp != fp => fp = opt_fp,
953                _ => break,
954            }
955            // Try to check if the call instruction is (instruction0, instruction1) or just
956            // instruction1 (with no immediate).
957            let call_pc = match (ret_pc - 1)
958                .ok()
959                .map(|r| self.segments.memory.get_integer(r))
960            {
961                Some(Ok(instruction1)) => {
962                    match is_call_instruction(&instruction1) {
963                        true => (ret_pc - 1).unwrap(), // This unwrap wont fail as it is checked before
964                        false => {
965                            match (ret_pc - 2)
966                                .ok()
967                                .map(|r| self.segments.memory.get_integer(r))
968                            {
969                                Some(Ok(instruction0)) => {
970                                    match is_call_instruction(&instruction0) {
971                                        true => (ret_pc - 2).unwrap(), // This unwrap wont fail as it is checked before
972                                        false => break,
973                                    }
974                                }
975                                _ => break,
976                            }
977                        }
978                    }
979                }
980                _ => break,
981            };
982            // Append traceback entries
983            entries.push((fp, call_pc))
984        }
985        entries.reverse();
986        entries
987    }
988
989    ///Adds a new segment and to the memory and returns its starting location as a Relocatable value.
990    pub fn add_memory_segment(&mut self) -> Relocatable {
991        self.segments.add()
992    }
993
994    pub fn get_ap(&self) -> Relocatable {
995        self.run_context.get_ap()
996    }
997
998    pub fn get_fp(&self) -> Relocatable {
999        self.run_context.get_fp()
1000    }
1001
1002    pub fn get_pc(&self) -> Relocatable {
1003        self.run_context.get_pc()
1004    }
1005
1006    pub fn get_current_step(&self) -> usize {
1007        self.current_step
1008    }
1009
1010    ///Gets the integer value corresponding to the Relocatable address
1011    pub fn get_integer(&'_ self, key: Relocatable) -> Result<Cow<'_, Felt252>, MemoryError> {
1012        self.segments.memory.get_integer(key)
1013    }
1014
1015    ///Gets the relocatable value corresponding to the Relocatable address
1016    pub fn get_relocatable(&self, key: Relocatable) -> Result<Relocatable, MemoryError> {
1017        self.segments.memory.get_relocatable(key)
1018    }
1019
1020    ///Gets a MaybeRelocatable value from memory indicated by a generic address
1021    pub fn get_maybe<'a, 'b: 'a, K: 'a>(&'b self, key: &'a K) -> Option<MaybeRelocatable>
1022    where
1023        Relocatable: TryFrom<&'a K>,
1024    {
1025        self.segments.memory.get(key).map(|x| x.into_owned())
1026    }
1027
1028    /// Returns a reference to the vector with all builtins present in the virtual machine
1029    pub fn get_builtin_runners(&self) -> &Vec<BuiltinRunner> {
1030        &self.builtin_runners
1031    }
1032
1033    /// Returns a mutable reference to the vector with all builtins present in the virtual machine
1034    pub fn get_builtin_runners_as_mut(&mut self) -> &mut Vec<BuiltinRunner> {
1035        &mut self.builtin_runners
1036    }
1037
1038    /// Returns a mutable iterator over all builtin runners used. That is, both builtin_runners and
1039    /// simulated_builtin_runners.
1040    pub fn get_all_builtin_runners_as_mut_iter(
1041        &mut self,
1042    ) -> impl Iterator<Item = &mut BuiltinRunner> {
1043        self.builtin_runners
1044            .iter_mut()
1045            .chain(self.simulated_builtin_runners.iter_mut())
1046    }
1047
1048    ///Inserts a value into a memory address given by a Relocatable value
1049    pub fn insert_value<T: Into<MaybeRelocatable>>(
1050        &mut self,
1051        key: Relocatable,
1052        val: T,
1053    ) -> Result<(), MemoryError> {
1054        self.segments.memory.insert_value(key, val)
1055    }
1056
1057    /// Removes (unsets) a value from a memory cell that was not accessed by the VM.
1058    ///
1059    /// This function can be used to implement lazy opening of merkelized contracts. The full
1060    /// program is initially loaded into memory via a hint. After execution, any entry points to
1061    /// contract segments that were not accessed are replaced with an invalid opcode.
1062    ///
1063    /// [Use case](https://github.com/starkware-libs/cairo-lang/blob/master/src/starkware/starknet/core/os/contract_class/compiled_class.cairo#L244-L253)
1064    pub fn delete_unaccessed(&mut self, addr: Relocatable) -> Result<(), MemoryError> {
1065        self.segments.memory.delete_unaccessed(addr)
1066    }
1067
1068    ///Writes data into the memory from address ptr and returns the first address after the data.
1069    pub fn load_data(
1070        &mut self,
1071        ptr: Relocatable,
1072        data: &[MaybeRelocatable],
1073    ) -> Result<Relocatable, MemoryError> {
1074        if ptr.segment_index == 0 {
1075            self.instruction_cache.resize(data.len(), None);
1076        }
1077        self.segments.load_data(ptr, data)
1078    }
1079
1080    /// Writes args into the memory from address ptr and returns the first address after the data.
1081    pub fn write_arg(
1082        &mut self,
1083        ptr: Relocatable,
1084        arg: &dyn Any,
1085    ) -> Result<MaybeRelocatable, MemoryError> {
1086        self.segments.write_arg(ptr, arg)
1087    }
1088
1089    pub fn memcmp(&self, lhs: Relocatable, rhs: Relocatable, len: usize) -> (Ordering, usize) {
1090        self.segments.memory.memcmp(lhs, rhs, len)
1091    }
1092
1093    pub fn mem_eq(&self, lhs: Relocatable, rhs: Relocatable, len: usize) -> bool {
1094        self.segments.memory.mem_eq(lhs, rhs, len)
1095    }
1096
1097    pub fn is_accessed(&self, addr: &Relocatable) -> Result<bool, MemoryError> {
1098        self.segments.is_accessed(addr)
1099    }
1100
1101    ///Gets `n_ret` return values from memory
1102    pub fn get_return_values(&self, n_ret: usize) -> Result<Vec<MaybeRelocatable>, MemoryError> {
1103        let addr = (self.run_context.get_ap() - n_ret)
1104            .map_err(|_| MemoryError::FailedToGetReturnValues(Box::new((n_ret, self.get_ap()))))?;
1105        self.segments.memory.get_continuous_range(addr, n_ret)
1106    }
1107
1108    ///Gets n elements from memory starting from addr (n being size)
1109    pub fn get_range(
1110        &'_ self,
1111        addr: Relocatable,
1112        size: usize,
1113    ) -> Vec<Option<Cow<'_, MaybeRelocatable>>> {
1114        self.segments.memory.get_range(addr, size)
1115    }
1116
1117    ///Gets n elements from memory starting from addr (n being size)
1118    pub fn get_continuous_range(
1119        &self,
1120        addr: Relocatable,
1121        size: usize,
1122    ) -> Result<Vec<MaybeRelocatable>, MemoryError> {
1123        self.segments.memory.get_continuous_range(addr, size)
1124    }
1125
1126    ///Gets n integer values from memory starting from addr (n being size),
1127    pub fn get_integer_range(
1128        &'_ self,
1129        addr: Relocatable,
1130        size: usize,
1131    ) -> Result<Vec<Cow<'_, Felt252>>, MemoryError> {
1132        self.segments.memory.get_integer_range(addr, size)
1133    }
1134
1135    /// Gets n u32 values from memory starting from addr (n being size).
1136    /// Returns an error if any of the values inside the range is missing (memory gap) or is not a u32.
1137    pub fn get_u32_range(&self, addr: Relocatable, size: usize) -> Result<Vec<u32>, MemoryError> {
1138        self.segments.memory.get_u32_range(addr, size)
1139    }
1140
1141    pub fn get_range_check_builtin(
1142        &self,
1143    ) -> Result<&RangeCheckBuiltinRunner<RC_N_PARTS_STANDARD>, VirtualMachineError> {
1144        for builtin in &self.builtin_runners {
1145            if let BuiltinRunner::RangeCheck(range_check_builtin) = builtin {
1146                return Ok(range_check_builtin);
1147            };
1148        }
1149        Err(VirtualMachineError::NoRangeCheckBuiltin)
1150    }
1151
1152    pub fn get_signature_builtin(
1153        &mut self,
1154    ) -> Result<&mut SignatureBuiltinRunner, VirtualMachineError> {
1155        for builtin in self.get_all_builtin_runners_as_mut_iter() {
1156            if let BuiltinRunner::Signature(signature_builtin) = builtin {
1157                return Ok(signature_builtin);
1158            };
1159        }
1160
1161        Err(VirtualMachineError::NoSignatureBuiltin)
1162    }
1163
1164    pub fn get_output_builtin_mut(
1165        &mut self,
1166    ) -> Result<&mut OutputBuiltinRunner, VirtualMachineError> {
1167        for builtin in self.get_builtin_runners_as_mut() {
1168            if let BuiltinRunner::Output(output_builtin) = builtin {
1169                return Ok(output_builtin);
1170            };
1171        }
1172
1173        Err(VirtualMachineError::NoOutputBuiltin)
1174    }
1175
1176    #[cfg(feature = "tracer")]
1177    pub fn relocate_segments(&self) -> Result<Vec<usize>, MemoryError> {
1178        self.segments.relocate_segments()
1179    }
1180
1181    #[doc(hidden)]
1182    pub fn skip_next_instruction_execution(&mut self) {
1183        self.skip_instruction_execution = true;
1184    }
1185
1186    #[doc(hidden)]
1187    pub fn set_ap(&mut self, ap: usize) {
1188        self.run_context.set_ap(ap)
1189    }
1190
1191    #[doc(hidden)]
1192    pub fn set_fp(&mut self, fp: usize) {
1193        self.run_context.set_fp(fp)
1194    }
1195
1196    #[doc(hidden)]
1197    pub fn set_pc(&mut self, pc: Relocatable) {
1198        self.run_context.set_pc(pc)
1199    }
1200
1201    pub fn get_segment_used_size(&self, index: usize) -> Option<usize> {
1202        self.segments.get_segment_used_size(index)
1203    }
1204
1205    pub fn get_segment_size(&self, index: usize) -> Option<usize> {
1206        self.segments.get_segment_size(index)
1207    }
1208
1209    pub fn add_temporary_segment(&mut self) -> Relocatable {
1210        self.segments.add_temporary_segment()
1211    }
1212
1213    /// Add a new relocation rule.
1214    ///
1215    /// When using feature "extensive_hints" the destination is allowed to be an Integer (via
1216    /// MaybeRelocatable). Relocating memory to anything other than a `Relocatable` is generally
1217    /// not useful, but it does make the implementation consistent with the pythonic version.
1218    ///
1219    /// Will return an error if any of the following conditions are not met:
1220    ///   - Source address's segment must be negative (temporary).
1221    ///   - Source address's offset must be zero.
1222    ///   - There shouldn't already be relocation at the source segment.
1223    pub fn add_relocation_rule(
1224        &mut self,
1225        src_ptr: Relocatable,
1226        #[cfg(not(feature = "extensive_hints"))] dst_ptr: Relocatable,
1227        #[cfg(feature = "extensive_hints")] dst_ptr: MaybeRelocatable,
1228    ) -> Result<(), MemoryError> {
1229        self.segments.memory.add_relocation_rule(src_ptr, dst_ptr)
1230    }
1231
1232    pub fn gen_arg(&mut self, arg: &dyn Any) -> Result<MaybeRelocatable, MemoryError> {
1233        self.segments.gen_arg(arg)
1234    }
1235
1236    /// Write the values hosted in the output builtin's segment.
1237    /// Does nothing if the output builtin is not present in the program.
1238    pub fn write_output(
1239        &mut self,
1240        writer: &mut impl core::fmt::Write,
1241    ) -> Result<(), VirtualMachineError> {
1242        let builtin = match self
1243            .builtin_runners
1244            .iter()
1245            .find(|b| b.name() == BuiltinName::output)
1246        {
1247            Some(x) => x,
1248            _ => return Ok(()),
1249        };
1250
1251        let segment_used_sizes = self.segments.compute_effective_sizes();
1252        let segment_index = builtin.base();
1253        for i in 0..segment_used_sizes[segment_index] {
1254            let formatted_value = match self
1255                .segments
1256                .memory
1257                .get(&Relocatable::from((segment_index as isize, i)))
1258            {
1259                Some(val) => match val.as_ref() {
1260                    MaybeRelocatable::Int(num) => format!("{}", signed_felt(*num)),
1261                    MaybeRelocatable::RelocatableValue(rel) => format!("{}", rel),
1262                },
1263                _ => "<missing>".to_string(),
1264            };
1265            writeln!(writer, "{formatted_value}")
1266                .map_err(|_| VirtualMachineError::FailedToWriteOutput)?;
1267        }
1268
1269        Ok(())
1270    }
1271
1272    /// Returns a list of addresses of memory cells that constitute the public memory.
1273    pub fn get_public_memory_addresses(&self) -> Result<Vec<(usize, usize)>, VirtualMachineError> {
1274        if let Some(relocation_table) = &self.relocation_table {
1275            self.segments
1276                .get_public_memory_addresses(relocation_table)
1277                .map_err(VirtualMachineError::Memory)
1278        } else {
1279            Err(MemoryError::UnrelocatedMemory.into())
1280        }
1281    }
1282
1283    #[doc(hidden)]
1284    pub fn builtins_final_stack_from_stack_pointer_dict(
1285        &mut self,
1286        builtin_name_to_stack_pointer: &HashMap<BuiltinName, Relocatable>,
1287        skip_output: bool,
1288    ) -> Result<(), RunnerError> {
1289        for builtin in self.builtin_runners.iter_mut() {
1290            if matches!(builtin, BuiltinRunner::Output(_)) && skip_output {
1291                continue;
1292            }
1293            builtin.final_stack(
1294                &self.segments,
1295                builtin_name_to_stack_pointer
1296                    .get(&builtin.name())
1297                    .cloned()
1298                    .unwrap_or_default(),
1299            )?;
1300        }
1301        Ok(())
1302    }
1303
1304    #[doc(hidden)]
1305    pub fn set_output_stop_ptr_offset(&mut self, offset: usize) {
1306        if let Some(BuiltinRunner::Output(builtin)) = self.builtin_runners.first_mut() {
1307            builtin.set_stop_ptr_offset(offset);
1308            if let Some(segment_used_sizes) = &mut self.segments.segment_used_sizes {
1309                segment_used_sizes[builtin.base()] = offset;
1310            }
1311        }
1312    }
1313
1314    /// Fetches add_mod & mul_mod builtins according to the optional arguments and executes `fill_memory`
1315    /// Returns an error if either of this optional parameters is true but the corresponding builtin is not present
1316    /// Verifies that both builtin's (if present) batch sizes match the batch_size arg if set
1317    // This method is needed as running `fill_memory` direclty from outside the vm struct would require cloning the builtin runners to avoid double borrowing
1318    pub fn mod_builtin_fill_memory(
1319        &mut self,
1320        add_mod_ptr_n: Option<(Relocatable, usize)>,
1321        mul_mod_ptr_n: Option<(Relocatable, usize)>,
1322        batch_size: Option<usize>,
1323    ) -> Result<(), VirtualMachineError> {
1324        let fetch_builtin_params = |mod_params: Option<(Relocatable, usize)>,
1325                                    mod_name: BuiltinName|
1326         -> Result<
1327            Option<(Relocatable, &ModBuiltinRunner, usize)>,
1328            VirtualMachineError,
1329        > {
1330            if let Some((ptr, n)) = mod_params {
1331                let mod_builtin = self
1332                    .builtin_runners
1333                    .iter()
1334                    .find_map(|b| match b {
1335                        BuiltinRunner::Mod(b) if b.name() == mod_name => Some(b),
1336                        _ => None,
1337                    })
1338                    .ok_or_else(|| VirtualMachineError::NoModBuiltin(mod_name))?;
1339                if let Some(batch_size) = batch_size {
1340                    if mod_builtin.batch_size() != batch_size {
1341                        return Err(VirtualMachineError::ModBuiltinBatchSize(Box::new((
1342                            mod_builtin.name(),
1343                            batch_size,
1344                        ))));
1345                    }
1346                }
1347                Ok(Some((ptr, mod_builtin, n)))
1348            } else {
1349                Ok(None)
1350            }
1351        };
1352
1353        ModBuiltinRunner::fill_memory(
1354            &mut self.segments.memory,
1355            fetch_builtin_params(add_mod_ptr_n, BuiltinName::add_mod)?,
1356            fetch_builtin_params(mul_mod_ptr_n, BuiltinName::mul_mod)?,
1357        )
1358        .map_err(VirtualMachineError::RunnerError)
1359    }
1360
1361    pub(crate) fn finalize_segments_by_cairo_pie(&mut self, pie: &CairoPie) {
1362        let mut segment_infos = vec![
1363            &pie.metadata.program_segment,
1364            &pie.metadata.execution_segment,
1365            &pie.metadata.ret_fp_segment,
1366            &pie.metadata.ret_pc_segment,
1367        ];
1368        segment_infos.extend(pie.metadata.builtin_segments.values());
1369        segment_infos.extend(pie.metadata.extra_segments.iter());
1370        for info in segment_infos {
1371            self.segments
1372                .finalize(Some(info.size), info.index as usize, None)
1373        }
1374    }
1375}
1376
1377pub struct VirtualMachineBuilder {
1378    pub(crate) run_context: RunContext,
1379    pub(crate) builtin_runners: Vec<BuiltinRunner>,
1380    pub(crate) segments: MemorySegmentManager,
1381    pub(crate) trace: Option<Vec<TraceEntry>>,
1382    pub(crate) current_step: usize,
1383    skip_instruction_execution: bool,
1384    run_finished: bool,
1385    #[cfg(feature = "test_utils")]
1386    pub(crate) hooks: Option<Box<dyn crate::vm::hooks::StepHooks>>,
1387}
1388
1389impl Default for VirtualMachineBuilder {
1390    fn default() -> Self {
1391        let run_context = RunContext {
1392            pc: Relocatable::from((0, 0)),
1393            ap: 0,
1394            fp: 0,
1395        };
1396
1397        VirtualMachineBuilder {
1398            run_context,
1399            builtin_runners: Vec::new(),
1400            trace: None,
1401            current_step: 0,
1402            skip_instruction_execution: false,
1403            segments: MemorySegmentManager::new(),
1404            run_finished: false,
1405            #[cfg(feature = "test_utils")]
1406            hooks: None,
1407        }
1408    }
1409}
1410
1411impl VirtualMachineBuilder {
1412    pub fn run_context(mut self, run_context: RunContext) -> VirtualMachineBuilder {
1413        self.run_context = run_context;
1414        self
1415    }
1416
1417    pub fn builtin_runners(mut self, builtin_runners: Vec<BuiltinRunner>) -> VirtualMachineBuilder {
1418        self.builtin_runners = builtin_runners;
1419        self
1420    }
1421
1422    pub fn segments(mut self, segments: MemorySegmentManager) -> VirtualMachineBuilder {
1423        self.segments = segments;
1424        self
1425    }
1426
1427    pub fn trace(mut self, trace: Option<Vec<TraceEntry>>) -> VirtualMachineBuilder {
1428        self.trace = trace;
1429        self
1430    }
1431
1432    pub fn current_step(mut self, current_step: usize) -> VirtualMachineBuilder {
1433        self.current_step = current_step;
1434        self
1435    }
1436
1437    pub fn skip_instruction_execution(
1438        mut self,
1439        skip_instruction_execution: bool,
1440    ) -> VirtualMachineBuilder {
1441        self.skip_instruction_execution = skip_instruction_execution;
1442        self
1443    }
1444
1445    pub fn run_finished(mut self, run_finished: bool) -> VirtualMachineBuilder {
1446        self.run_finished = run_finished;
1447        self
1448    }
1449
1450    #[cfg(feature = "test_utils")]
1451    pub fn hooks(mut self, hooks: Box<dyn crate::vm::hooks::StepHooks>) -> VirtualMachineBuilder {
1452        self.hooks = Some(hooks);
1453        self
1454    }
1455
1456    pub fn build(self) -> VirtualMachine {
1457        VirtualMachine {
1458            run_context: self.run_context,
1459            builtin_runners: self.builtin_runners,
1460            simulated_builtin_runners: Vec::new(),
1461            extended_resource_counter: HashMap::new(),
1462            trace: self.trace,
1463            current_step: self.current_step,
1464            skip_instruction_execution: self.skip_instruction_execution,
1465            segments: self.segments,
1466            rc_limits: None,
1467            run_finished: self.run_finished,
1468            instruction_cache: Vec::new(),
1469            #[cfg(feature = "test_utils")]
1470            hooks: self.hooks,
1471            relocation_table: None,
1472            disable_trace_padding: false,
1473        }
1474    }
1475}
1476
1477#[cfg(test)]
1478mod tests {
1479    use super::*;
1480    use crate::felt_hex;
1481    use crate::math_utils::STWO_PRIME;
1482    use crate::types::instruction::OpcodeExtension;
1483    use crate::types::layout_name::LayoutName;
1484    use crate::types::program::Program;
1485    use crate::{
1486        any_box,
1487        hint_processor::builtin_hint_processor::builtin_hint_processor_definition::{
1488            BuiltinHintProcessor, HintProcessorData,
1489        },
1490        relocatable,
1491        types::{
1492            instruction::{Op1Addr, Register},
1493            relocatable::Relocatable,
1494        },
1495        utils::test_utils::*,
1496        vm::{
1497            errors::memory_errors::MemoryError,
1498            runners::builtin_runner::{BitwiseBuiltinRunner, EcOpBuiltinRunner, HashBuiltinRunner},
1499        },
1500    };
1501    use assert_matches::assert_matches;
1502    use std::collections::HashMap;
1503
1504    use starknet_types_core::qm31::QM31;
1505
1506    #[test]
1507    fn update_fp_ap_plus2() {
1508        let instruction = Instruction {
1509            off0: 1,
1510            off1: 2,
1511            off2: 3,
1512            dst_register: Register::FP,
1513            op0_register: Register::AP,
1514            op1_addr: Op1Addr::AP,
1515            res: Res::Add,
1516            pc_update: PcUpdate::Regular,
1517            ap_update: ApUpdate::Regular,
1518            fp_update: FpUpdate::APPlus2,
1519            opcode: Opcode::NOp,
1520            opcode_extension: OpcodeExtension::Stone,
1521        };
1522
1523        let operands = Operands {
1524            dst: MaybeRelocatable::Int(Felt252::from(11)),
1525            res: Some(MaybeRelocatable::Int(Felt252::from(8))),
1526            op0: MaybeRelocatable::Int(Felt252::from(9)),
1527            op1: MaybeRelocatable::Int(Felt252::from(10)),
1528        };
1529
1530        let mut vm = vm!();
1531        run_context!(vm, 4, 5, 6);
1532        assert_matches!(
1533            vm.update_fp(&instruction, &operands),
1534            Ok::<(), VirtualMachineError>(())
1535        );
1536        assert_eq!(vm.run_context.fp, 7)
1537    }
1538
1539    #[test]
1540    fn update_fp_dst() {
1541        let instruction = Instruction {
1542            off0: 1,
1543            off1: 2,
1544            off2: 3,
1545            dst_register: Register::FP,
1546            op0_register: Register::AP,
1547            op1_addr: Op1Addr::AP,
1548            res: Res::Add,
1549            pc_update: PcUpdate::Regular,
1550            ap_update: ApUpdate::Regular,
1551            fp_update: FpUpdate::Dst,
1552            opcode: Opcode::NOp,
1553            opcode_extension: OpcodeExtension::Stone,
1554        };
1555
1556        let operands = Operands {
1557            dst: mayberelocatable!(1, 6),
1558            res: Some(mayberelocatable!(8)),
1559            op0: mayberelocatable!(9),
1560            op1: mayberelocatable!(10),
1561        };
1562
1563        let mut vm = vm!();
1564
1565        assert_matches!(
1566            vm.update_fp(&instruction, &operands),
1567            Ok::<(), VirtualMachineError>(())
1568        );
1569        assert_eq!(vm.run_context.fp, 6)
1570    }
1571
1572    #[test]
1573    fn update_fp_regular() {
1574        let instruction = Instruction {
1575            off0: 1,
1576            off1: 2,
1577            off2: 3,
1578            dst_register: Register::FP,
1579            op0_register: Register::AP,
1580            op1_addr: Op1Addr::AP,
1581            res: Res::Add,
1582            pc_update: PcUpdate::Regular,
1583            ap_update: ApUpdate::Regular,
1584            fp_update: FpUpdate::Regular,
1585            opcode: Opcode::NOp,
1586            opcode_extension: OpcodeExtension::Stone,
1587        };
1588
1589        let operands = Operands {
1590            dst: MaybeRelocatable::Int(Felt252::from(11_u64)),
1591            res: Some(MaybeRelocatable::Int(Felt252::from(8_u64))),
1592            op0: MaybeRelocatable::Int(Felt252::from(9_u64)),
1593            op1: MaybeRelocatable::Int(Felt252::from(10_u64)),
1594        };
1595
1596        let mut vm = vm!();
1597
1598        assert_matches!(
1599            vm.update_fp(&instruction, &operands),
1600            Ok::<(), VirtualMachineError>(())
1601        );
1602        assert_eq!(vm.run_context.fp, 0)
1603    }
1604
1605    #[test]
1606    fn update_fp_dst_num() {
1607        let instruction = Instruction {
1608            off0: 1,
1609            off1: 2,
1610            off2: 3,
1611            dst_register: Register::FP,
1612            op0_register: Register::AP,
1613            op1_addr: Op1Addr::AP,
1614            res: Res::Add,
1615            pc_update: PcUpdate::Regular,
1616            ap_update: ApUpdate::Regular,
1617            fp_update: FpUpdate::Dst,
1618            opcode: Opcode::NOp,
1619            opcode_extension: OpcodeExtension::Stone,
1620        };
1621
1622        let operands = Operands {
1623            dst: MaybeRelocatable::Int(Felt252::from(11)),
1624            res: Some(MaybeRelocatable::Int(Felt252::from(8))),
1625            op0: MaybeRelocatable::Int(Felt252::from(9)),
1626            op1: MaybeRelocatable::Int(Felt252::from(10)),
1627        };
1628
1629        let mut vm = vm!();
1630        run_context!(vm, 4, 5, 6);
1631
1632        assert_matches!(
1633            vm.update_fp(&instruction, &operands),
1634            Ok::<(), VirtualMachineError>(())
1635        );
1636        assert_eq!(vm.run_context.fp, 11)
1637    }
1638
1639    #[test]
1640    fn update_ap_add_with_res() {
1641        let instruction = Instruction {
1642            off0: 1,
1643            off1: 2,
1644            off2: 3,
1645            dst_register: Register::FP,
1646            op0_register: Register::AP,
1647            op1_addr: Op1Addr::AP,
1648            res: Res::Add,
1649            pc_update: PcUpdate::Regular,
1650            ap_update: ApUpdate::Add,
1651            fp_update: FpUpdate::Regular,
1652            opcode: Opcode::NOp,
1653            opcode_extension: OpcodeExtension::Stone,
1654        };
1655
1656        let operands = Operands {
1657            dst: MaybeRelocatable::Int(Felt252::from(11)),
1658            res: Some(MaybeRelocatable::Int(Felt252::from(8))),
1659            op0: MaybeRelocatable::Int(Felt252::from(9)),
1660            op1: MaybeRelocatable::Int(Felt252::from(10)),
1661        };
1662
1663        let mut vm = VirtualMachine::new(false, false);
1664        vm.run_context.pc = Relocatable::from((0, 4));
1665        vm.run_context.ap = 5;
1666        vm.run_context.fp = 6;
1667
1668        assert_matches!(
1669            vm.update_ap(&instruction, &operands),
1670            Ok::<(), VirtualMachineError>(())
1671        );
1672        assert_eq!(vm.run_context.ap, 13);
1673    }
1674
1675    #[test]
1676    fn update_ap_add_without_res() {
1677        let instruction = Instruction {
1678            off0: 1,
1679            off1: 2,
1680            off2: 3,
1681            dst_register: Register::FP,
1682            op0_register: Register::AP,
1683            op1_addr: Op1Addr::AP,
1684            res: Res::Add,
1685            pc_update: PcUpdate::Regular,
1686            ap_update: ApUpdate::Add,
1687            fp_update: FpUpdate::Regular,
1688            opcode: Opcode::NOp,
1689            opcode_extension: OpcodeExtension::Stone,
1690        };
1691
1692        let operands = Operands {
1693            dst: MaybeRelocatable::Int(Felt252::from(11)),
1694            res: None,
1695            op0: MaybeRelocatable::Int(Felt252::from(9)),
1696            op1: MaybeRelocatable::Int(Felt252::from(10)),
1697        };
1698
1699        let mut vm = vm!();
1700        vm.run_context.pc = Relocatable::from((0, 4));
1701        vm.run_context.ap = 5;
1702        vm.run_context.fp = 6;
1703
1704        assert_matches!(
1705            vm.update_ap(&instruction, &operands),
1706            Err(VirtualMachineError::UnconstrainedResAdd)
1707        );
1708    }
1709
1710    #[test]
1711    fn update_ap_add1() {
1712        let instruction = Instruction {
1713            off0: 1,
1714            off1: 2,
1715            off2: 3,
1716            dst_register: Register::FP,
1717            op0_register: Register::AP,
1718            op1_addr: Op1Addr::AP,
1719            res: Res::Add,
1720            pc_update: PcUpdate::Regular,
1721            ap_update: ApUpdate::Add1,
1722            fp_update: FpUpdate::Regular,
1723            opcode: Opcode::NOp,
1724            opcode_extension: OpcodeExtension::Stone,
1725        };
1726
1727        let operands = Operands {
1728            dst: MaybeRelocatable::Int(Felt252::from(11)),
1729            res: Some(MaybeRelocatable::Int(Felt252::from(8))),
1730            op0: MaybeRelocatable::Int(Felt252::from(9)),
1731            op1: MaybeRelocatable::Int(Felt252::from(10)),
1732        };
1733
1734        let mut vm = vm!();
1735        vm.run_context.pc = Relocatable::from((0, 4));
1736        vm.run_context.ap = 5;
1737        vm.run_context.fp = 6;
1738
1739        assert_matches!(
1740            vm.update_ap(&instruction, &operands),
1741            Ok::<(), VirtualMachineError>(())
1742        );
1743        assert_eq!(vm.run_context.ap, 6);
1744    }
1745
1746    #[test]
1747    fn update_ap_add2() {
1748        let instruction = Instruction {
1749            off0: 1,
1750            off1: 2,
1751            off2: 3,
1752            dst_register: Register::FP,
1753            op0_register: Register::AP,
1754            op1_addr: Op1Addr::AP,
1755            res: Res::Add,
1756            pc_update: PcUpdate::Regular,
1757            ap_update: ApUpdate::Add2,
1758            fp_update: FpUpdate::Regular,
1759            opcode: Opcode::NOp,
1760            opcode_extension: OpcodeExtension::Stone,
1761        };
1762
1763        let operands = Operands {
1764            dst: MaybeRelocatable::Int(Felt252::from(11_u64)),
1765            res: Some(MaybeRelocatable::Int(Felt252::from(8_u64))),
1766            op0: MaybeRelocatable::Int(Felt252::from(9_u64)),
1767            op1: MaybeRelocatable::Int(Felt252::from(10_u64)),
1768        };
1769
1770        let mut vm = vm!();
1771        vm.run_context.pc = Relocatable::from((0, 4));
1772        vm.run_context.ap = 5;
1773        vm.run_context.fp = 6;
1774
1775        assert_matches!(
1776            vm.update_ap(&instruction, &operands),
1777            Ok::<(), VirtualMachineError>(())
1778        );
1779        assert_eq!(vm.run_context.ap, 7);
1780    }
1781
1782    #[test]
1783    fn update_ap_regular() {
1784        let instruction = Instruction {
1785            off0: 1,
1786            off1: 2,
1787            off2: 3,
1788            dst_register: Register::FP,
1789            op0_register: Register::AP,
1790            op1_addr: Op1Addr::AP,
1791            res: Res::Add,
1792            pc_update: PcUpdate::Regular,
1793            ap_update: ApUpdate::Regular,
1794            fp_update: FpUpdate::Regular,
1795            opcode: Opcode::NOp,
1796            opcode_extension: OpcodeExtension::Stone,
1797        };
1798
1799        let operands = Operands {
1800            dst: MaybeRelocatable::Int(Felt252::from(11)),
1801            res: Some(MaybeRelocatable::Int(Felt252::from(8))),
1802            op0: MaybeRelocatable::Int(Felt252::from(9)),
1803            op1: MaybeRelocatable::Int(Felt252::from(10)),
1804        };
1805
1806        let mut vm = vm!();
1807        vm.run_context.pc = Relocatable::from((0, 4));
1808        vm.run_context.ap = 5;
1809        vm.run_context.fp = 6;
1810
1811        assert_matches!(
1812            vm.update_ap(&instruction, &operands),
1813            Ok::<(), VirtualMachineError>(())
1814        );
1815        assert_eq!(vm.run_context.ap, 5);
1816    }
1817
1818    #[test]
1819    fn update_pc_regular_instruction_no_imm() {
1820        let instruction = Instruction {
1821            off0: 1,
1822            off1: 2,
1823            off2: 3,
1824            dst_register: Register::FP,
1825            op0_register: Register::AP,
1826            op1_addr: Op1Addr::AP,
1827            res: Res::Add,
1828            pc_update: PcUpdate::Regular,
1829            ap_update: ApUpdate::Regular,
1830            fp_update: FpUpdate::Regular,
1831            opcode: Opcode::NOp,
1832            opcode_extension: OpcodeExtension::Stone,
1833        };
1834
1835        let operands = Operands {
1836            dst: MaybeRelocatable::Int(Felt252::from(11)),
1837            res: Some(MaybeRelocatable::Int(Felt252::from(8))),
1838            op0: MaybeRelocatable::Int(Felt252::from(9)),
1839            op1: MaybeRelocatable::Int(Felt252::from(10)),
1840        };
1841
1842        let mut vm = vm!();
1843
1844        assert_matches!(
1845            vm.update_pc(&instruction, &operands),
1846            Ok::<(), VirtualMachineError>(())
1847        );
1848        assert_eq!(vm.run_context.pc, Relocatable::from((0, 1)));
1849    }
1850
1851    #[test]
1852    fn update_pc_regular_instruction_has_imm() {
1853        let instruction = Instruction {
1854            off0: 1,
1855            off1: 2,
1856            off2: 3,
1857            dst_register: Register::FP,
1858            op0_register: Register::AP,
1859            op1_addr: Op1Addr::Imm,
1860            res: Res::Add,
1861            pc_update: PcUpdate::Regular,
1862            ap_update: ApUpdate::Regular,
1863            fp_update: FpUpdate::Regular,
1864            opcode: Opcode::NOp,
1865            opcode_extension: OpcodeExtension::Stone,
1866        };
1867
1868        let operands = Operands {
1869            dst: MaybeRelocatable::Int(Felt252::from(11)),
1870            res: Some(MaybeRelocatable::Int(Felt252::from(8))),
1871            op0: MaybeRelocatable::Int(Felt252::from(9)),
1872            op1: MaybeRelocatable::Int(Felt252::from(10)),
1873        };
1874
1875        let mut vm = vm!();
1876
1877        assert_matches!(
1878            vm.update_pc(&instruction, &operands),
1879            Ok::<(), VirtualMachineError>(())
1880        );
1881        assert_eq!(vm.run_context.pc, Relocatable::from((0, 2)));
1882    }
1883
1884    #[test]
1885    fn update_pc_jump_with_res() {
1886        let instruction = Instruction {
1887            off0: 1,
1888            off1: 2,
1889            off2: 3,
1890            dst_register: Register::FP,
1891            op0_register: Register::AP,
1892            op1_addr: Op1Addr::AP,
1893            res: Res::Add,
1894            pc_update: PcUpdate::Jump,
1895            ap_update: ApUpdate::Regular,
1896            fp_update: FpUpdate::Regular,
1897            opcode: Opcode::NOp,
1898            opcode_extension: OpcodeExtension::Stone,
1899        };
1900
1901        let operands = Operands {
1902            dst: mayberelocatable!(1, 11),
1903            res: Some(mayberelocatable!(0, 8)),
1904            op0: MaybeRelocatable::Int(Felt252::from(9)),
1905            op1: MaybeRelocatable::Int(Felt252::from(10)),
1906        };
1907
1908        let mut vm = vm!();
1909
1910        assert_matches!(
1911            vm.update_pc(&instruction, &operands),
1912            Ok::<(), VirtualMachineError>(())
1913        );
1914        assert_eq!(vm.run_context.pc, Relocatable::from((0, 8)));
1915    }
1916
1917    #[test]
1918    fn update_pc_jump_without_res() {
1919        let instruction = Instruction {
1920            off0: 1,
1921            off1: 2,
1922            off2: 3,
1923            dst_register: Register::FP,
1924            op0_register: Register::AP,
1925            op1_addr: Op1Addr::AP,
1926            res: Res::Add,
1927            pc_update: PcUpdate::Jump,
1928            ap_update: ApUpdate::Regular,
1929            fp_update: FpUpdate::Regular,
1930            opcode: Opcode::NOp,
1931            opcode_extension: OpcodeExtension::Stone,
1932        };
1933
1934        let operands = Operands {
1935            dst: MaybeRelocatable::Int(Felt252::from(11)),
1936            res: None,
1937            op0: MaybeRelocatable::Int(Felt252::from(9)),
1938            op1: MaybeRelocatable::Int(Felt252::from(10)),
1939        };
1940
1941        let mut vm = vm!();
1942        vm.run_context.pc = Relocatable::from((0, 4));
1943        vm.run_context.ap = 5;
1944        vm.run_context.fp = 6;
1945
1946        assert_matches!(
1947            vm.update_pc(&instruction, &operands),
1948            Err(VirtualMachineError::UnconstrainedResJump)
1949        );
1950    }
1951
1952    #[test]
1953    fn update_pc_jump_rel_with_int_res() {
1954        let instruction = Instruction {
1955            off0: 1,
1956            off1: 2,
1957            off2: 3,
1958            dst_register: Register::FP,
1959            op0_register: Register::AP,
1960            op1_addr: Op1Addr::AP,
1961            res: Res::Add,
1962            pc_update: PcUpdate::JumpRel,
1963            ap_update: ApUpdate::Regular,
1964            fp_update: FpUpdate::Regular,
1965            opcode: Opcode::NOp,
1966            opcode_extension: OpcodeExtension::Stone,
1967        };
1968
1969        let operands = Operands {
1970            dst: MaybeRelocatable::Int(Felt252::from(11)),
1971            res: Some(MaybeRelocatable::Int(Felt252::from(8))),
1972            op0: MaybeRelocatable::Int(Felt252::from(9)),
1973            op1: MaybeRelocatable::Int(Felt252::from(10)),
1974        };
1975
1976        let mut vm = vm!();
1977        run_context!(vm, 1, 1, 1);
1978
1979        assert_matches!(
1980            vm.update_pc(&instruction, &operands),
1981            Ok::<(), VirtualMachineError>(())
1982        );
1983        assert_eq!(vm.run_context.pc, Relocatable::from((0, 9)));
1984    }
1985
1986    #[test]
1987    fn update_pc_jump_rel_without_res() {
1988        let instruction = Instruction {
1989            off0: 1,
1990            off1: 2,
1991            off2: 3,
1992            dst_register: Register::FP,
1993            op0_register: Register::AP,
1994            op1_addr: Op1Addr::AP,
1995            res: Res::Add,
1996            pc_update: PcUpdate::JumpRel,
1997            ap_update: ApUpdate::Regular,
1998            fp_update: FpUpdate::Regular,
1999            opcode: Opcode::NOp,
2000            opcode_extension: OpcodeExtension::Stone,
2001        };
2002
2003        let operands = Operands {
2004            dst: MaybeRelocatable::Int(Felt252::from(11)),
2005            res: None,
2006            op0: MaybeRelocatable::Int(Felt252::from(9)),
2007            op1: MaybeRelocatable::Int(Felt252::from(10)),
2008        };
2009
2010        let mut vm = vm!();
2011
2012        assert_matches!(
2013            vm.update_pc(&instruction, &operands),
2014            Err(VirtualMachineError::UnconstrainedResJumpRel)
2015        );
2016    }
2017
2018    #[test]
2019    fn update_pc_jump_rel_with_non_int_res() {
2020        let instruction = Instruction {
2021            off0: 1,
2022            off1: 2,
2023            off2: 3,
2024            dst_register: Register::FP,
2025            op0_register: Register::AP,
2026            op1_addr: Op1Addr::AP,
2027            res: Res::Add,
2028            pc_update: PcUpdate::JumpRel,
2029            ap_update: ApUpdate::Regular,
2030            fp_update: FpUpdate::Regular,
2031            opcode: Opcode::NOp,
2032            opcode_extension: OpcodeExtension::Stone,
2033        };
2034
2035        let operands = Operands {
2036            dst: MaybeRelocatable::Int(Felt252::from(11)),
2037            res: Some(MaybeRelocatable::from((1, 4))),
2038            op0: MaybeRelocatable::Int(Felt252::from(9)),
2039            op1: MaybeRelocatable::Int(Felt252::from(10)),
2040        };
2041
2042        let mut vm = vm!();
2043        assert_matches!(
2044            vm.update_pc(&instruction, &operands),
2045            Err::<(), VirtualMachineError>(VirtualMachineError::JumpRelNotInt)
2046        );
2047    }
2048
2049    #[test]
2050    fn update_pc_jnz_dst_is_zero() {
2051        let instruction = Instruction {
2052            off0: 1,
2053            off1: 2,
2054            off2: 3,
2055            dst_register: Register::FP,
2056            op0_register: Register::AP,
2057            op1_addr: Op1Addr::AP,
2058            res: Res::Add,
2059            pc_update: PcUpdate::Jnz,
2060            ap_update: ApUpdate::Regular,
2061            fp_update: FpUpdate::Regular,
2062            opcode: Opcode::NOp,
2063            opcode_extension: OpcodeExtension::Stone,
2064        };
2065
2066        let operands = Operands {
2067            dst: MaybeRelocatable::Int(Felt252::from(0)),
2068            res: Some(MaybeRelocatable::Int(Felt252::from(0))),
2069            op0: MaybeRelocatable::Int(Felt252::from(9)),
2070            op1: MaybeRelocatable::Int(Felt252::from(10)),
2071        };
2072
2073        let mut vm = vm!();
2074
2075        assert_matches!(
2076            vm.update_pc(&instruction, &operands),
2077            Ok::<(), VirtualMachineError>(())
2078        );
2079        assert_eq!(vm.run_context.pc, Relocatable::from((0, 1)));
2080    }
2081
2082    #[test]
2083    fn update_pc_jnz_dst_is_not_zero() {
2084        let instruction = Instruction {
2085            off0: 1,
2086            off1: 2,
2087            off2: 3,
2088            dst_register: Register::FP,
2089            op0_register: Register::AP,
2090            op1_addr: Op1Addr::AP,
2091            res: Res::Add,
2092            pc_update: PcUpdate::Jnz,
2093            ap_update: ApUpdate::Regular,
2094            fp_update: FpUpdate::Regular,
2095            opcode: Opcode::NOp,
2096            opcode_extension: OpcodeExtension::Stone,
2097        };
2098
2099        let operands = Operands {
2100            dst: MaybeRelocatable::Int(Felt252::from(11)),
2101            res: Some(MaybeRelocatable::Int(Felt252::from(8))),
2102            op0: MaybeRelocatable::Int(Felt252::from(9)),
2103            op1: MaybeRelocatable::Int(Felt252::from(10)),
2104        };
2105
2106        let mut vm = vm!();
2107
2108        assert_matches!(
2109            vm.update_pc(&instruction, &operands),
2110            Ok::<(), VirtualMachineError>(())
2111        );
2112        assert_eq!(vm.run_context.pc, Relocatable::from((0, 10)));
2113    }
2114
2115    #[test]
2116    fn update_registers_all_regular() {
2117        let instruction = Instruction {
2118            off0: 1,
2119            off1: 2,
2120            off2: 3,
2121            dst_register: Register::FP,
2122            op0_register: Register::AP,
2123            op1_addr: Op1Addr::AP,
2124            res: Res::Add,
2125            pc_update: PcUpdate::Regular,
2126            ap_update: ApUpdate::Regular,
2127            fp_update: FpUpdate::Regular,
2128            opcode: Opcode::NOp,
2129            opcode_extension: OpcodeExtension::Stone,
2130        };
2131
2132        let operands = Operands {
2133            dst: MaybeRelocatable::Int(Felt252::from(11)),
2134            res: Some(MaybeRelocatable::Int(Felt252::from(8))),
2135            op0: MaybeRelocatable::Int(Felt252::from(9)),
2136            op1: MaybeRelocatable::Int(Felt252::from(10)),
2137        };
2138
2139        let mut vm = vm!();
2140        vm.run_context.pc = Relocatable::from((0, 4));
2141        vm.run_context.ap = 5;
2142        vm.run_context.fp = 6;
2143
2144        assert_matches!(
2145            vm.update_registers(&instruction, operands),
2146            Ok::<(), VirtualMachineError>(())
2147        );
2148        assert_eq!(vm.run_context.pc, Relocatable::from((0, 5)));
2149        assert_eq!(vm.run_context.ap, 5);
2150        assert_eq!(vm.run_context.fp, 6);
2151    }
2152
2153    #[test]
2154    fn update_registers_mixed_types() {
2155        let instruction = Instruction {
2156            off0: 1,
2157            off1: 2,
2158            off2: 3,
2159            dst_register: Register::FP,
2160            op0_register: Register::AP,
2161            op1_addr: Op1Addr::AP,
2162            res: Res::Add,
2163            pc_update: PcUpdate::JumpRel,
2164            ap_update: ApUpdate::Add2,
2165            fp_update: FpUpdate::Dst,
2166            opcode: Opcode::NOp,
2167            opcode_extension: OpcodeExtension::Stone,
2168        };
2169
2170        let operands = Operands {
2171            dst: MaybeRelocatable::from((1, 11)),
2172            res: Some(MaybeRelocatable::Int(Felt252::from(8))),
2173            op0: MaybeRelocatable::Int(Felt252::from(9)),
2174            op1: MaybeRelocatable::Int(Felt252::from(10)),
2175        };
2176
2177        let mut vm = vm!();
2178        run_context!(vm, 4, 5, 6);
2179
2180        assert_matches!(
2181            vm.update_registers(&instruction, operands),
2182            Ok::<(), VirtualMachineError>(())
2183        );
2184        assert_eq!(vm.run_context.pc, Relocatable::from((0, 12)));
2185        assert_eq!(vm.run_context.ap, 7);
2186        assert_eq!(vm.run_context.fp, 11);
2187    }
2188
2189    #[test]
2190    fn is_zero_int_value() {
2191        let value = MaybeRelocatable::Int(Felt252::from(1));
2192        assert!(!VirtualMachine::is_zero(&value));
2193    }
2194
2195    #[test]
2196    fn is_zero_relocatable_value() {
2197        let value = MaybeRelocatable::from((1, 2));
2198        assert!(!VirtualMachine::is_zero(&value));
2199    }
2200
2201    #[test]
2202    fn deduce_op0_opcode_call() {
2203        let instruction = Instruction {
2204            off0: 1,
2205            off1: 2,
2206            off2: 3,
2207            dst_register: Register::FP,
2208            op0_register: Register::AP,
2209            op1_addr: Op1Addr::AP,
2210            res: Res::Add,
2211            pc_update: PcUpdate::Jump,
2212            ap_update: ApUpdate::Regular,
2213            fp_update: FpUpdate::Regular,
2214            opcode: Opcode::Call,
2215            opcode_extension: OpcodeExtension::Stone,
2216        };
2217
2218        let vm = vm!();
2219
2220        assert_matches!(
2221            vm.deduce_op0(&instruction, None, None),
2222            Ok::<(Option<MaybeRelocatable>, Option<MaybeRelocatable>), VirtualMachineError>((
2223                Some(x),
2224                None
2225            )) if x == MaybeRelocatable::from((0, 1))
2226        );
2227    }
2228
2229    #[test]
2230    fn deduce_op0_opcode_assert_eq_res_add_with_optionals() {
2231        let instruction = Instruction {
2232            off0: 1,
2233            off1: 2,
2234            off2: 3,
2235            dst_register: Register::FP,
2236            op0_register: Register::AP,
2237            op1_addr: Op1Addr::AP,
2238            res: Res::Add,
2239            pc_update: PcUpdate::Jump,
2240            ap_update: ApUpdate::Regular,
2241            fp_update: FpUpdate::Regular,
2242            opcode: Opcode::AssertEq,
2243            opcode_extension: OpcodeExtension::Stone,
2244        };
2245
2246        let vm = vm!();
2247
2248        let dst = MaybeRelocatable::Int(Felt252::from(3));
2249        let op1 = MaybeRelocatable::Int(Felt252::from(2));
2250
2251        assert_matches!(
2252            vm.deduce_op0(&instruction, Some(&dst), Some(&op1)),
2253            Ok::<(Option<MaybeRelocatable>, Option<MaybeRelocatable>), VirtualMachineError>((
2254                x,
2255                y
2256            )) if x == Some(MaybeRelocatable::Int(Felt252::from(1))) &&
2257                    y == Some(MaybeRelocatable::Int(Felt252::from(3)))
2258        );
2259    }
2260
2261    #[test]
2262    fn deduce_op0_opcode_assert_eq_res_add_without_optionals() {
2263        let instruction = Instruction {
2264            off0: 1,
2265            off1: 2,
2266            off2: 3,
2267            dst_register: Register::FP,
2268            op0_register: Register::AP,
2269            op1_addr: Op1Addr::AP,
2270            res: Res::Add,
2271            pc_update: PcUpdate::Jump,
2272            ap_update: ApUpdate::Regular,
2273            fp_update: FpUpdate::Regular,
2274            opcode: Opcode::AssertEq,
2275            opcode_extension: OpcodeExtension::Stone,
2276        };
2277
2278        let vm = vm!();
2279
2280        assert_matches!(
2281            vm.deduce_op0(&instruction, None, None),
2282            Ok::<(Option<MaybeRelocatable>, Option<MaybeRelocatable>), VirtualMachineError>((
2283                None, None
2284            ))
2285        );
2286    }
2287
2288    #[test]
2289    fn deduce_op0_opcode_assert_eq_res_mul_non_zero_op1() {
2290        let instruction = Instruction {
2291            off0: 1,
2292            off1: 2,
2293            off2: 3,
2294            dst_register: Register::FP,
2295            op0_register: Register::AP,
2296            op1_addr: Op1Addr::AP,
2297            res: Res::Mul,
2298            pc_update: PcUpdate::Jump,
2299            ap_update: ApUpdate::Regular,
2300            fp_update: FpUpdate::Regular,
2301            opcode: Opcode::AssertEq,
2302            opcode_extension: OpcodeExtension::Stone,
2303        };
2304
2305        let vm = vm!();
2306
2307        let dst = MaybeRelocatable::Int(Felt252::from(4));
2308        let op1 = MaybeRelocatable::Int(Felt252::from(2));
2309
2310        assert_matches!(
2311            vm.deduce_op0(&instruction, Some(&dst), Some(&op1)),
2312            Ok::<(Option<MaybeRelocatable>, Option<MaybeRelocatable>), VirtualMachineError>((
2313                Some(x),
2314                Some(y)
2315            )) if x == MaybeRelocatable::Int(Felt252::from(2)) &&
2316                    y == MaybeRelocatable::Int(Felt252::from(4))
2317        );
2318    }
2319
2320    #[test]
2321    fn deduce_op0_opcode_assert_eq_res_mul_zero_op1() {
2322        let instruction = Instruction {
2323            off0: 1,
2324            off1: 2,
2325            off2: 3,
2326            dst_register: Register::FP,
2327            op0_register: Register::AP,
2328            op1_addr: Op1Addr::AP,
2329            res: Res::Mul,
2330            pc_update: PcUpdate::Jump,
2331            ap_update: ApUpdate::Regular,
2332            fp_update: FpUpdate::Regular,
2333            opcode: Opcode::AssertEq,
2334            opcode_extension: OpcodeExtension::Stone,
2335        };
2336
2337        let vm = vm!();
2338
2339        let dst = MaybeRelocatable::Int(Felt252::from(4));
2340        let op1 = MaybeRelocatable::Int(Felt252::from(0));
2341        assert_matches!(
2342            vm.deduce_op0(&instruction, Some(&dst), Some(&op1)),
2343            Ok::<(Option<MaybeRelocatable>, Option<MaybeRelocatable>), VirtualMachineError>((
2344                None, None
2345            ))
2346        );
2347    }
2348
2349    #[test]
2350    fn deduce_op0_opcode_assert_eq_res_op1() {
2351        let instruction = Instruction {
2352            off0: 1,
2353            off1: 2,
2354            off2: 3,
2355            dst_register: Register::FP,
2356            op0_register: Register::AP,
2357            op1_addr: Op1Addr::AP,
2358            res: Res::Op1,
2359            pc_update: PcUpdate::Jump,
2360            ap_update: ApUpdate::Regular,
2361            fp_update: FpUpdate::Regular,
2362            opcode: Opcode::AssertEq,
2363            opcode_extension: OpcodeExtension::Stone,
2364        };
2365
2366        let vm = vm!();
2367
2368        let dst = MaybeRelocatable::Int(Felt252::from(4));
2369        let op1 = MaybeRelocatable::Int(Felt252::from(0));
2370        assert_matches!(
2371            vm.deduce_op0(&instruction, Some(&dst), Some(&op1)),
2372            Ok::<(Option<MaybeRelocatable>, Option<MaybeRelocatable>), VirtualMachineError>((
2373                None, None
2374            ))
2375        );
2376    }
2377
2378    #[test]
2379    fn deduce_op0_opcode_ret() {
2380        let instruction = Instruction {
2381            off0: 1,
2382            off1: 2,
2383            off2: 3,
2384            dst_register: Register::FP,
2385            op0_register: Register::AP,
2386            op1_addr: Op1Addr::AP,
2387            res: Res::Mul,
2388            pc_update: PcUpdate::Jump,
2389            ap_update: ApUpdate::Regular,
2390            fp_update: FpUpdate::Regular,
2391            opcode: Opcode::Ret,
2392            opcode_extension: OpcodeExtension::Stone,
2393        };
2394
2395        let vm = vm!();
2396
2397        let dst = MaybeRelocatable::Int(Felt252::from(4));
2398        let op1 = MaybeRelocatable::Int(Felt252::from(0));
2399
2400        assert_matches!(
2401            vm.deduce_op0(&instruction, Some(&dst), Some(&op1)),
2402            Ok::<(Option<MaybeRelocatable>, Option<MaybeRelocatable>), VirtualMachineError>((
2403                None, None
2404            ))
2405        );
2406    }
2407
2408    #[test]
2409    fn deduce_op0_qm31_add_int_operands() {
2410        let instruction = Instruction {
2411            off0: 1,
2412            off1: 2,
2413            off2: 3,
2414            dst_register: Register::FP,
2415            op0_register: Register::AP,
2416            op1_addr: Op1Addr::AP,
2417            res: Res::Add,
2418            pc_update: PcUpdate::Regular,
2419            ap_update: ApUpdate::Regular,
2420            fp_update: FpUpdate::Regular,
2421            opcode: Opcode::AssertEq,
2422            opcode_extension: OpcodeExtension::QM31Operation,
2423        };
2424
2425        let vm = vm!();
2426
2427        let op1_qm31 = QM31::from_coefficients(STWO_PRIME - 10, 5, STWO_PRIME - 5, 1);
2428        let dst_qm31 = QM31::from_coefficients(STWO_PRIME - 4, 2, 12, 3);
2429
2430        let op1 = MaybeRelocatable::Int(op1_qm31.pack_into_felt());
2431        let dst = MaybeRelocatable::Int(dst_qm31.pack_into_felt());
2432        assert_matches!(
2433            vm.deduce_op0(&instruction, Some(&dst), Some(&op1)),
2434            Ok::<(Option<MaybeRelocatable>, Option<MaybeRelocatable>), VirtualMachineError>((
2435                x,
2436                y
2437            )) if  QM31::unpack_from_felt(x.clone().unwrap().get_int_ref().unwrap()).unwrap() == QM31::from_coefficients(6, STWO_PRIME - 3, 17, 2) &&
2438                     QM31::unpack_from_felt(y.clone().unwrap().get_int_ref().unwrap()).unwrap() == dst_qm31
2439        );
2440    }
2441
2442    #[test]
2443    fn deduce_op0_qm31_mul_int_operands() {
2444        let instruction = Instruction {
2445            off0: 1,
2446            off1: 2,
2447            off2: 3,
2448            dst_register: Register::FP,
2449            op0_register: Register::AP,
2450            op1_addr: Op1Addr::AP,
2451            res: Res::Mul,
2452            pc_update: PcUpdate::Regular,
2453            ap_update: ApUpdate::Regular,
2454            fp_update: FpUpdate::Regular,
2455            opcode: Opcode::AssertEq,
2456            opcode_extension: OpcodeExtension::QM31Operation,
2457        };
2458
2459        let vm = vm!();
2460
2461        let op1_qm31 = QM31::from_coefficients(0, 0, 1, 0);
2462        let dst_qm31 = QM31::from_coefficients(0, 0, 0, 1);
2463        let op1 = MaybeRelocatable::Int(op1_qm31.pack_into_felt());
2464        let dst = MaybeRelocatable::Int(dst_qm31.pack_into_felt());
2465        assert_matches!(
2466            vm.deduce_op0(&instruction, Some(&dst), Some(&op1)),
2467            Ok::<(Option<MaybeRelocatable>, Option<MaybeRelocatable>), VirtualMachineError>((
2468                x,
2469                y
2470            )) if QM31::unpack_from_felt(x.clone().unwrap().get_int_ref().unwrap()).unwrap() == QM31::from_coefficients(0, 1, 0, 0) &&
2471                    QM31::unpack_from_felt(y.clone().unwrap().get_int_ref().unwrap()).unwrap() == dst_qm31
2472        );
2473    }
2474
2475    #[test]
2476    fn deduce_op0_blake_finalize_add_int_operands() {
2477        let instruction = Instruction {
2478            off0: 1,
2479            off1: 2,
2480            off2: 3,
2481            dst_register: Register::FP,
2482            op0_register: Register::AP,
2483            op1_addr: Op1Addr::AP,
2484            res: Res::Add,
2485            pc_update: PcUpdate::Regular,
2486            ap_update: ApUpdate::Regular,
2487            fp_update: FpUpdate::Regular,
2488            opcode: Opcode::AssertEq,
2489            opcode_extension: OpcodeExtension::BlakeFinalize,
2490        };
2491
2492        let vm = vm!();
2493
2494        let op1 = MaybeRelocatable::Int(Felt252::from(5));
2495        let dst = MaybeRelocatable::Int(Felt252::from(15));
2496        assert_matches!(
2497            vm.deduce_op0(&instruction, Some(&dst), Some(&op1)),
2498            Err(VirtualMachineError::InvalidTypedOperationOpcodeExtension(ref message)) if message.as_ref() == "typed_sub"
2499        );
2500    }
2501
2502    #[test]
2503    fn deduce_op1_opcode_call() {
2504        let instruction = Instruction {
2505            off0: 1,
2506            off1: 2,
2507            off2: 3,
2508            dst_register: Register::FP,
2509            op0_register: Register::AP,
2510            op1_addr: Op1Addr::AP,
2511            res: Res::Add,
2512            pc_update: PcUpdate::Jump,
2513            ap_update: ApUpdate::Regular,
2514            fp_update: FpUpdate::Regular,
2515            opcode: Opcode::Call,
2516            opcode_extension: OpcodeExtension::Stone,
2517        };
2518
2519        let vm = vm!();
2520
2521        assert_matches!(
2522            vm.deduce_op1(&instruction, None, None),
2523            Ok::<(Option<MaybeRelocatable>, Option<MaybeRelocatable>), VirtualMachineError>((
2524                None, None
2525            ))
2526        );
2527    }
2528
2529    #[test]
2530    fn deduce_op1_opcode_assert_eq_res_add_with_optionals() {
2531        let instruction = Instruction {
2532            off0: 1,
2533            off1: 2,
2534            off2: 3,
2535            dst_register: Register::FP,
2536            op0_register: Register::AP,
2537            op1_addr: Op1Addr::AP,
2538            res: Res::Add,
2539            pc_update: PcUpdate::Jump,
2540            ap_update: ApUpdate::Regular,
2541            fp_update: FpUpdate::Regular,
2542            opcode: Opcode::AssertEq,
2543            opcode_extension: OpcodeExtension::Stone,
2544        };
2545
2546        let vm = vm!();
2547
2548        let dst = MaybeRelocatable::Int(Felt252::from(3));
2549        let op0 = MaybeRelocatable::Int(Felt252::from(2));
2550        assert_matches!(
2551            vm.deduce_op1(&instruction, Some(&dst), Some(op0)),
2552            Ok::<(Option<MaybeRelocatable>, Option<MaybeRelocatable>), VirtualMachineError>((
2553                x,
2554                y
2555            )) if x == Some(MaybeRelocatable::Int(Felt252::from(1))) &&
2556                    y == Some(MaybeRelocatable::Int(Felt252::from(3)))
2557        );
2558    }
2559
2560    #[test]
2561    fn deduce_op1_opcode_assert_eq_res_add_without_optionals() {
2562        let instruction = Instruction {
2563            off0: 1,
2564            off1: 2,
2565            off2: 3,
2566            dst_register: Register::FP,
2567            op0_register: Register::AP,
2568            op1_addr: Op1Addr::AP,
2569            res: Res::Add,
2570            pc_update: PcUpdate::Jump,
2571            ap_update: ApUpdate::Regular,
2572            fp_update: FpUpdate::Regular,
2573            opcode: Opcode::AssertEq,
2574            opcode_extension: OpcodeExtension::Stone,
2575        };
2576
2577        let vm = vm!();
2578        assert_matches!(
2579            vm.deduce_op1(&instruction, None, None),
2580            Ok::<(Option<MaybeRelocatable>, Option<MaybeRelocatable>), VirtualMachineError>((
2581                None, None
2582            ))
2583        );
2584    }
2585
2586    #[test]
2587    fn deduce_op1_opcode_assert_eq_res_mul_non_zero_op0() {
2588        let instruction = Instruction {
2589            off0: 1,
2590            off1: 2,
2591            off2: 3,
2592            dst_register: Register::FP,
2593            op0_register: Register::AP,
2594            op1_addr: Op1Addr::AP,
2595            res: Res::Mul,
2596            pc_update: PcUpdate::Jump,
2597            ap_update: ApUpdate::Regular,
2598            fp_update: FpUpdate::Regular,
2599            opcode: Opcode::AssertEq,
2600            opcode_extension: OpcodeExtension::Stone,
2601        };
2602
2603        let vm = vm!();
2604
2605        let dst = MaybeRelocatable::Int(Felt252::from(4));
2606        let op0 = MaybeRelocatable::Int(Felt252::from(2));
2607        assert_matches!(
2608            vm.deduce_op1(&instruction, Some(&dst), Some(op0)),
2609            Ok::<(Option<MaybeRelocatable>, Option<MaybeRelocatable>), VirtualMachineError>((
2610                x,
2611                y
2612            )) if x == Some(MaybeRelocatable::Int(Felt252::from(2))) &&
2613                    y == Some(MaybeRelocatable::Int(Felt252::from(4)))
2614        );
2615    }
2616
2617    #[test]
2618    fn deduce_op1_opcode_assert_eq_res_mul_zero_op0() {
2619        let instruction = Instruction {
2620            off0: 1,
2621            off1: 2,
2622            off2: 3,
2623            dst_register: Register::FP,
2624            op0_register: Register::AP,
2625            op1_addr: Op1Addr::AP,
2626            res: Res::Mul,
2627            pc_update: PcUpdate::Jump,
2628            ap_update: ApUpdate::Regular,
2629            fp_update: FpUpdate::Regular,
2630            opcode: Opcode::AssertEq,
2631            opcode_extension: OpcodeExtension::Stone,
2632        };
2633
2634        let vm = vm!();
2635
2636        let dst = MaybeRelocatable::Int(Felt252::from(4));
2637        let op0 = MaybeRelocatable::Int(Felt252::from(0));
2638        assert_matches!(
2639            vm.deduce_op1(&instruction, Some(&dst), Some(op0)),
2640            Ok::<(Option<MaybeRelocatable>, Option<MaybeRelocatable>), VirtualMachineError>((
2641                None, None
2642            ))
2643        );
2644    }
2645
2646    #[test]
2647    fn deduce_op1_opcode_assert_eq_res_op1_without_dst() {
2648        let instruction = Instruction {
2649            off0: 1,
2650            off1: 2,
2651            off2: 3,
2652            dst_register: Register::FP,
2653            op0_register: Register::AP,
2654            op1_addr: Op1Addr::AP,
2655            res: Res::Op1,
2656            pc_update: PcUpdate::Jump,
2657            ap_update: ApUpdate::Regular,
2658            fp_update: FpUpdate::Regular,
2659            opcode: Opcode::AssertEq,
2660            opcode_extension: OpcodeExtension::Stone,
2661        };
2662
2663        let vm = vm!();
2664
2665        let op0 = MaybeRelocatable::Int(Felt252::from(0));
2666        assert_matches!(
2667            vm.deduce_op1(&instruction, None, Some(op0)),
2668            Ok::<(Option<MaybeRelocatable>, Option<MaybeRelocatable>), VirtualMachineError>((
2669                None, None
2670            ))
2671        );
2672    }
2673
2674    #[test]
2675    fn deduce_op1_opcode_assert_eq_res_op1_with_dst() {
2676        let instruction = Instruction {
2677            off0: 1,
2678            off1: 2,
2679            off2: 3,
2680            dst_register: Register::FP,
2681            op0_register: Register::AP,
2682            op1_addr: Op1Addr::AP,
2683            res: Res::Op1,
2684            pc_update: PcUpdate::Jump,
2685            ap_update: ApUpdate::Regular,
2686            fp_update: FpUpdate::Regular,
2687            opcode: Opcode::AssertEq,
2688            opcode_extension: OpcodeExtension::Stone,
2689        };
2690
2691        let vm = vm!();
2692
2693        let dst = MaybeRelocatable::Int(Felt252::from(7));
2694        assert_matches!(
2695            vm.deduce_op1(&instruction, Some(&dst), None),
2696            Ok::<(Option<MaybeRelocatable>, Option<MaybeRelocatable>), VirtualMachineError>((
2697                x,
2698                y
2699            )) if x == Some(MaybeRelocatable::Int(Felt252::from(7))) &&
2700                    y == Some(MaybeRelocatable::Int(Felt252::from(7)))
2701        );
2702    }
2703
2704    #[test]
2705    fn deduce_op1_qm31_add_int_operands() {
2706        let instruction = Instruction {
2707            off0: 1,
2708            off1: 2,
2709            off2: 3,
2710            dst_register: Register::FP,
2711            op0_register: Register::AP,
2712            op1_addr: Op1Addr::AP,
2713            res: Res::Add,
2714            pc_update: PcUpdate::Regular,
2715            ap_update: ApUpdate::Regular,
2716            fp_update: FpUpdate::Regular,
2717            opcode: Opcode::AssertEq,
2718            opcode_extension: OpcodeExtension::QM31Operation,
2719        };
2720
2721        let vm = vm!();
2722
2723        let op0_qm31 = QM31::from_coefficients(4, STWO_PRIME - 13, 3, 7);
2724        let dst_qm31 = QM31::from_coefficients(8, 7, 6, 5);
2725        let op0 = MaybeRelocatable::Int(op0_qm31.pack_into_felt());
2726        let dst = MaybeRelocatable::Int(dst_qm31.pack_into_felt());
2727        assert_matches!(
2728            vm.deduce_op1(&instruction, Some(&dst), Some(op0)),
2729            Ok::<(Option<MaybeRelocatable>, Option<MaybeRelocatable>), VirtualMachineError>((
2730                x,
2731                y
2732            )) if  QM31::unpack_from_felt(x.clone().unwrap().get_int_ref().unwrap()).unwrap() == QM31::from_coefficients(4, 20, 3, STWO_PRIME - 2) &&
2733                     QM31::unpack_from_felt(y.clone().unwrap().get_int_ref().unwrap()).unwrap() == dst_qm31
2734        );
2735    }
2736
2737    #[test]
2738    fn deduce_op1_qm31_mul_int_operands() {
2739        let instruction = Instruction {
2740            off0: 1,
2741            off1: 2,
2742            off2: 3,
2743            dst_register: Register::FP,
2744            op0_register: Register::AP,
2745            op1_addr: Op1Addr::AP,
2746            res: Res::Mul,
2747            pc_update: PcUpdate::Regular,
2748            ap_update: ApUpdate::Regular,
2749            fp_update: FpUpdate::Regular,
2750            opcode: Opcode::AssertEq,
2751            opcode_extension: OpcodeExtension::QM31Operation,
2752        };
2753
2754        let vm = vm!();
2755
2756        let op0_qm31 = QM31::from_coefficients(0, 1, 0, 0);
2757        let dst_qm31 = QM31::from_coefficients(STWO_PRIME - 1, 0, 0, 0);
2758        let op0 = MaybeRelocatable::Int(op0_qm31.pack_into_felt());
2759        let dst = MaybeRelocatable::Int(dst_qm31.pack_into_felt());
2760        assert_matches!(
2761            vm.deduce_op1(&instruction, Some(&dst), Some(op0)),
2762            Ok::<(Option<MaybeRelocatable>, Option<MaybeRelocatable>), VirtualMachineError>((
2763                x,
2764                y
2765            )) if QM31::unpack_from_felt(x.clone().unwrap().get_int_ref().unwrap()).unwrap() == QM31::from_coefficients(0, 1, 0, 0) &&
2766                    QM31::unpack_from_felt(y.clone().unwrap().get_int_ref().unwrap()).unwrap() == dst_qm31
2767        );
2768    }
2769
2770    #[test]
2771    fn deduce_op1_blake_mul_int_operands() {
2772        let instruction = Instruction {
2773            off0: 1,
2774            off1: 2,
2775            off2: 3,
2776            dst_register: Register::FP,
2777            op0_register: Register::AP,
2778            op1_addr: Op1Addr::AP,
2779            res: Res::Mul,
2780            pc_update: PcUpdate::Regular,
2781            ap_update: ApUpdate::Regular,
2782            fp_update: FpUpdate::Regular,
2783            opcode: Opcode::AssertEq,
2784            opcode_extension: OpcodeExtension::Blake,
2785        };
2786
2787        let vm = vm!();
2788
2789        let op0 = MaybeRelocatable::Int(Felt252::from(4));
2790        let dst = MaybeRelocatable::Int(Felt252::from(16));
2791        assert_matches!(
2792            vm.deduce_op1(&instruction, Some(&dst), Some(op0)),
2793            Err(VirtualMachineError::InvalidTypedOperationOpcodeExtension(ref message)) if message.as_ref() == "typed_div"
2794        );
2795    }
2796
2797    #[test]
2798    fn compute_res_op1() {
2799        let instruction = Instruction {
2800            off0: 1,
2801            off1: 2,
2802            off2: 3,
2803            dst_register: Register::FP,
2804            op0_register: Register::AP,
2805            op1_addr: Op1Addr::AP,
2806            res: Res::Op1,
2807            pc_update: PcUpdate::Jump,
2808            ap_update: ApUpdate::Regular,
2809            fp_update: FpUpdate::Regular,
2810            opcode: Opcode::AssertEq,
2811            opcode_extension: OpcodeExtension::Stone,
2812        };
2813
2814        let vm = vm!();
2815
2816        let op1 = MaybeRelocatable::Int(Felt252::from(7));
2817        let op0 = MaybeRelocatable::Int(Felt252::from(9));
2818        assert_matches!(
2819            vm.compute_res(&instruction, &op0, &op1),
2820            Ok::<Option<MaybeRelocatable>, VirtualMachineError>(Some(MaybeRelocatable::Int(
2821                x
2822            ))) if x == Felt252::from(7)
2823        );
2824    }
2825
2826    #[test]
2827    fn compute_res_add() {
2828        let instruction = Instruction {
2829            off0: 1,
2830            off1: 2,
2831            off2: 3,
2832            dst_register: Register::FP,
2833            op0_register: Register::AP,
2834            op1_addr: Op1Addr::AP,
2835            res: Res::Add,
2836            pc_update: PcUpdate::Jump,
2837            ap_update: ApUpdate::Regular,
2838            fp_update: FpUpdate::Regular,
2839            opcode: Opcode::AssertEq,
2840            opcode_extension: OpcodeExtension::Stone,
2841        };
2842
2843        let vm = vm!();
2844
2845        let op1 = MaybeRelocatable::Int(Felt252::from(7));
2846        let op0 = MaybeRelocatable::Int(Felt252::from(9));
2847        assert_matches!(
2848            vm.compute_res(&instruction, &op0, &op1),
2849            Ok::<Option<MaybeRelocatable>, VirtualMachineError>(Some(MaybeRelocatable::Int(
2850                x
2851            ))) if x == Felt252::from(16)
2852        );
2853    }
2854
2855    #[test]
2856    fn compute_res_mul_int_operands() {
2857        let instruction = Instruction {
2858            off0: 1,
2859            off1: 2,
2860            off2: 3,
2861            dst_register: Register::FP,
2862            op0_register: Register::AP,
2863            op1_addr: Op1Addr::AP,
2864            res: Res::Mul,
2865            pc_update: PcUpdate::Jump,
2866            ap_update: ApUpdate::Regular,
2867            fp_update: FpUpdate::Regular,
2868            opcode: Opcode::AssertEq,
2869            opcode_extension: OpcodeExtension::Stone,
2870        };
2871
2872        let vm = vm!();
2873
2874        let op1 = MaybeRelocatable::Int(Felt252::from(7));
2875        let op0 = MaybeRelocatable::Int(Felt252::from(9));
2876        assert_matches!(
2877            vm.compute_res(&instruction, &op0, &op1),
2878            Ok::<Option<MaybeRelocatable>, VirtualMachineError>(Some(MaybeRelocatable::Int(
2879                x
2880            ))) if x == Felt252::from(63)
2881        );
2882    }
2883
2884    #[test]
2885    fn compute_res_mul_relocatable_values() {
2886        let instruction = Instruction {
2887            off0: 1,
2888            off1: 2,
2889            off2: 3,
2890            dst_register: Register::FP,
2891            op0_register: Register::AP,
2892            op1_addr: Op1Addr::AP,
2893            res: Res::Mul,
2894            pc_update: PcUpdate::Jump,
2895            ap_update: ApUpdate::Regular,
2896            fp_update: FpUpdate::Regular,
2897            opcode: Opcode::AssertEq,
2898            opcode_extension: OpcodeExtension::Stone,
2899        };
2900
2901        let vm = vm!();
2902
2903        let op1 = MaybeRelocatable::from((2, 3));
2904        let op0 = MaybeRelocatable::from((2, 6));
2905        assert_matches!(
2906            vm.compute_res(&instruction, &op0, &op1),
2907            Err(VirtualMachineError::ComputeResRelocatableMul(bx)) if *bx == (op0, op1)
2908        );
2909    }
2910
2911    #[test]
2912    fn compute_res_qm31_add_relocatable_values() {
2913        let instruction = Instruction {
2914            off0: 1,
2915            off1: 2,
2916            off2: 3,
2917            dst_register: Register::FP,
2918            op0_register: Register::AP,
2919            op1_addr: Op1Addr::AP,
2920            res: Res::Add,
2921            pc_update: PcUpdate::Regular,
2922            ap_update: ApUpdate::Regular,
2923            fp_update: FpUpdate::Regular,
2924            opcode: Opcode::AssertEq,
2925            opcode_extension: OpcodeExtension::QM31Operation,
2926        };
2927
2928        let vm = vm!();
2929
2930        let op1 = MaybeRelocatable::from((2, 3));
2931        let op0 = MaybeRelocatable::from(7);
2932        assert_matches!(
2933            vm.compute_res(&instruction, &op0, &op1),
2934            Err(VirtualMachineError::Math(MathError::RelocatableQM31Add(bx))) if *bx == (op0, op1)
2935        );
2936    }
2937
2938    #[test]
2939    fn compute_res_qm31_add_int_operands() {
2940        let instruction = Instruction {
2941            off0: 1,
2942            off1: 2,
2943            off2: 3,
2944            dst_register: Register::FP,
2945            op0_register: Register::AP,
2946            op1_addr: Op1Addr::AP,
2947            res: Res::Add,
2948            pc_update: PcUpdate::Regular,
2949            ap_update: ApUpdate::Regular,
2950            fp_update: FpUpdate::Regular,
2951            opcode: Opcode::AssertEq,
2952            opcode_extension: OpcodeExtension::QM31Operation,
2953        };
2954
2955        let vm = vm!();
2956
2957        let op1_qm31 = QM31::from_coefficients(1, 2, 3, 4);
2958        let op0_qm31 = QM31::from_coefficients(10, 11, STWO_PRIME - 1, 13);
2959        let op1 = MaybeRelocatable::Int(op1_qm31.pack_into_felt());
2960        let op0 = MaybeRelocatable::Int(op0_qm31.pack_into_felt());
2961        assert_matches!(
2962            vm.compute_res(&instruction, &op0, &op1),
2963            Ok::<Option<MaybeRelocatable>, VirtualMachineError>(Some(MaybeRelocatable::Int(
2964                x
2965            ))) if QM31::unpack_from_felt(&x).unwrap() == QM31::from_coefficients(11, 13, 2, 17)
2966        );
2967    }
2968
2969    #[test]
2970    fn compute_res_qm31_mul_int_operands() {
2971        let instruction = Instruction {
2972            off0: 1,
2973            off1: 2,
2974            off2: 3,
2975            dst_register: Register::FP,
2976            op0_register: Register::AP,
2977            op1_addr: Op1Addr::AP,
2978            res: Res::Mul,
2979            pc_update: PcUpdate::Regular,
2980            ap_update: ApUpdate::Regular,
2981            fp_update: FpUpdate::Regular,
2982            opcode: Opcode::AssertEq,
2983            opcode_extension: OpcodeExtension::QM31Operation,
2984        };
2985
2986        let vm = vm!();
2987
2988        let op1_qm31 = QM31::from_coefficients(0, 0, 1, 0);
2989        let op0_qm31 = QM31::from_coefficients(0, 0, 1, 0);
2990        let op1 = MaybeRelocatable::Int(op1_qm31.pack_into_felt());
2991        let op0 = MaybeRelocatable::Int(op0_qm31.pack_into_felt());
2992        assert_matches!(
2993            vm.compute_res(&instruction, &op0, &op1),
2994            Ok::<Option<MaybeRelocatable>, VirtualMachineError>(Some(MaybeRelocatable::Int(
2995                x
2996            ))) if QM31::unpack_from_felt(&x).unwrap() == QM31::from_coefficients(2, 1, 0, 0)
2997        );
2998    }
2999
3000    #[test]
3001    fn compute_res_blake_mul_int_operands() {
3002        let instruction = Instruction {
3003            off0: 1,
3004            off1: 2,
3005            off2: 3,
3006            dst_register: Register::FP,
3007            op0_register: Register::AP,
3008            op1_addr: Op1Addr::AP,
3009            res: Res::Mul,
3010            pc_update: PcUpdate::Regular,
3011            ap_update: ApUpdate::Regular,
3012            fp_update: FpUpdate::Regular,
3013            opcode: Opcode::AssertEq,
3014            opcode_extension: OpcodeExtension::Blake,
3015        };
3016
3017        let vm = vm!();
3018
3019        let op1 = MaybeRelocatable::Int(Felt252::from(11));
3020        let op0 = MaybeRelocatable::Int(Felt252::from(12));
3021        assert_matches!(
3022            vm.compute_res(&instruction, &op0, &op1),
3023            Err(VirtualMachineError::InvalidTypedOperationOpcodeExtension(ref message)) if message.as_ref() == "typed_mul"
3024        );
3025    }
3026
3027    #[test]
3028    fn compute_res_unconstrained() {
3029        let instruction = Instruction {
3030            off0: 1,
3031            off1: 2,
3032            off2: 3,
3033            dst_register: Register::FP,
3034            op0_register: Register::AP,
3035            op1_addr: Op1Addr::AP,
3036            res: Res::Unconstrained,
3037            pc_update: PcUpdate::Jump,
3038            ap_update: ApUpdate::Regular,
3039            fp_update: FpUpdate::Regular,
3040            opcode: Opcode::AssertEq,
3041            opcode_extension: OpcodeExtension::Stone,
3042        };
3043
3044        let vm = vm!();
3045
3046        let op1 = MaybeRelocatable::Int(Felt252::from(7));
3047        let op0 = MaybeRelocatable::Int(Felt252::from(9));
3048        assert_matches!(
3049            vm.compute_res(&instruction, &op0, &op1),
3050            Ok::<Option<MaybeRelocatable>, VirtualMachineError>(None)
3051        );
3052    }
3053
3054    #[test]
3055    fn deduce_dst_opcode_assert_eq_with_res() {
3056        let instruction = Instruction {
3057            off0: 1,
3058            off1: 2,
3059            off2: 3,
3060            dst_register: Register::FP,
3061            op0_register: Register::AP,
3062            op1_addr: Op1Addr::AP,
3063            res: Res::Unconstrained,
3064            pc_update: PcUpdate::Jump,
3065            ap_update: ApUpdate::Regular,
3066            fp_update: FpUpdate::Regular,
3067            opcode: Opcode::AssertEq,
3068            opcode_extension: OpcodeExtension::Stone,
3069        };
3070
3071        let vm = vm!();
3072
3073        let res = MaybeRelocatable::Int(Felt252::from(7));
3074        assert_eq!(
3075            MaybeRelocatable::Int(Felt252::from(7)),
3076            vm.deduce_dst(&instruction, &Some(res)).unwrap()
3077        );
3078    }
3079
3080    #[test]
3081    fn deduce_dst_opcode_assert_eq_without_res() {
3082        let instruction = Instruction {
3083            off0: 1,
3084            off1: 2,
3085            off2: 3,
3086            dst_register: Register::FP,
3087            op0_register: Register::AP,
3088            op1_addr: Op1Addr::AP,
3089            res: Res::Unconstrained,
3090            pc_update: PcUpdate::Jump,
3091            ap_update: ApUpdate::Regular,
3092            fp_update: FpUpdate::Regular,
3093            opcode: Opcode::AssertEq,
3094            opcode_extension: OpcodeExtension::Stone,
3095        };
3096
3097        let vm = vm!();
3098
3099        assert!(vm.deduce_dst(&instruction, &None).is_err());
3100    }
3101
3102    #[test]
3103    fn deduce_dst_opcode_call() {
3104        let instruction = Instruction {
3105            off0: 1,
3106            off1: 2,
3107            off2: 3,
3108            dst_register: Register::FP,
3109            op0_register: Register::AP,
3110            op1_addr: Op1Addr::AP,
3111            res: Res::Unconstrained,
3112            pc_update: PcUpdate::Jump,
3113            ap_update: ApUpdate::Regular,
3114            fp_update: FpUpdate::Regular,
3115            opcode: Opcode::Call,
3116            opcode_extension: OpcodeExtension::Stone,
3117        };
3118
3119        let vm = vm!();
3120
3121        assert_eq!(
3122            MaybeRelocatable::from((1, 0)),
3123            vm.deduce_dst(&instruction, &None).unwrap()
3124        );
3125    }
3126
3127    #[test]
3128    fn deduce_dst_opcode_ret() {
3129        let instruction = Instruction {
3130            off0: 1,
3131            off1: 2,
3132            off2: 3,
3133            dst_register: Register::FP,
3134            op0_register: Register::AP,
3135            op1_addr: Op1Addr::AP,
3136            res: Res::Unconstrained,
3137            pc_update: PcUpdate::Jump,
3138            ap_update: ApUpdate::Regular,
3139            fp_update: FpUpdate::Regular,
3140            opcode: Opcode::Ret,
3141            opcode_extension: OpcodeExtension::Stone,
3142        };
3143
3144        let vm = vm!();
3145
3146        assert!(vm.deduce_dst(&instruction, &None).is_err());
3147    }
3148
3149    #[test]
3150    fn compute_operands_add_ap() {
3151        let inst = Instruction {
3152            off0: 0,
3153            off1: 1,
3154            off2: 2,
3155            dst_register: Register::AP,
3156            op0_register: Register::AP,
3157            op1_addr: Op1Addr::AP,
3158            res: Res::Add,
3159            pc_update: PcUpdate::Regular,
3160            ap_update: ApUpdate::Regular,
3161            fp_update: FpUpdate::Regular,
3162            opcode: Opcode::NOp,
3163            opcode_extension: OpcodeExtension::Stone,
3164        };
3165
3166        let mut vm = vm!();
3167        for _ in 0..2 {
3168            vm.segments.add();
3169        }
3170
3171        vm.segments.memory.data.push(Vec::new());
3172        let dst_addr = Relocatable::from((1, 0));
3173        let dst_addr_value = MaybeRelocatable::Int(Felt252::from(5));
3174        let op0_addr = Relocatable::from((1, 1));
3175        let op0_addr_value = MaybeRelocatable::Int(Felt252::from(2));
3176        let op1_addr = Relocatable::from((1, 2));
3177        let op1_addr_value = MaybeRelocatable::Int(Felt252::from(3));
3178        vm.segments
3179            .memory
3180            .insert(dst_addr, &dst_addr_value)
3181            .unwrap();
3182        vm.segments
3183            .memory
3184            .insert(op0_addr, &op0_addr_value)
3185            .unwrap();
3186        vm.segments
3187            .memory
3188            .insert(op1_addr, &op1_addr_value)
3189            .unwrap();
3190
3191        let expected_operands = Operands {
3192            dst: dst_addr_value.clone(),
3193            res: Some(dst_addr_value.clone()),
3194            op0: op0_addr_value.clone(),
3195            op1: op1_addr_value.clone(),
3196        };
3197
3198        let expected_addresses = OperandsAddresses {
3199            dst_addr,
3200            op0_addr,
3201            op1_addr,
3202        };
3203
3204        let (operands, addresses, _) = vm.compute_operands(&inst).unwrap();
3205        assert!(operands == expected_operands);
3206        assert!(addresses == expected_addresses);
3207    }
3208
3209    #[test]
3210    fn compute_operands_mul_fp() {
3211        let inst = Instruction {
3212            off0: 0,
3213            off1: 1,
3214            off2: 2,
3215            dst_register: Register::FP,
3216            op0_register: Register::FP,
3217            op1_addr: Op1Addr::FP,
3218            res: Res::Mul,
3219            pc_update: PcUpdate::Regular,
3220            ap_update: ApUpdate::Regular,
3221            fp_update: FpUpdate::Regular,
3222            opcode: Opcode::NOp,
3223            opcode_extension: OpcodeExtension::Stone,
3224        };
3225        let mut vm = vm!();
3226        //Create program and execution segments
3227        for _ in 0..2 {
3228            vm.segments.add();
3229        }
3230        vm.segments.memory.data.push(Vec::new());
3231        let dst_addr = relocatable!(1, 0);
3232        let dst_addr_value = mayberelocatable!(6);
3233        let op0_addr = relocatable!(1, 1);
3234        let op0_addr_value = mayberelocatable!(2);
3235        let op1_addr = relocatable!(1, 2);
3236        let op1_addr_value = mayberelocatable!(3);
3237        vm.segments
3238            .memory
3239            .insert(dst_addr, &dst_addr_value)
3240            .unwrap();
3241        vm.segments
3242            .memory
3243            .insert(op0_addr, &op0_addr_value)
3244            .unwrap();
3245        vm.segments
3246            .memory
3247            .insert(op1_addr, &op1_addr_value)
3248            .unwrap();
3249
3250        let expected_operands = Operands {
3251            dst: dst_addr_value.clone(),
3252            res: Some(dst_addr_value.clone()),
3253            op0: op0_addr_value.clone(),
3254            op1: op1_addr_value.clone(),
3255        };
3256
3257        let expected_addresses = OperandsAddresses {
3258            dst_addr,
3259            op0_addr,
3260            op1_addr,
3261        };
3262
3263        let (operands, addresses, _) = vm.compute_operands(&inst).unwrap();
3264        assert!(operands == expected_operands);
3265        assert!(addresses == expected_addresses);
3266    }
3267
3268    #[test]
3269    fn compute_jnz() {
3270        let instruction = Instruction {
3271            off0: 1,
3272            off1: 1,
3273            off2: 1,
3274            dst_register: Register::AP,
3275            op0_register: Register::AP,
3276            op1_addr: Op1Addr::Imm,
3277            res: Res::Unconstrained,
3278            pc_update: PcUpdate::Jnz,
3279            ap_update: ApUpdate::Regular,
3280            fp_update: FpUpdate::Regular,
3281            opcode: Opcode::NOp,
3282            opcode_extension: OpcodeExtension::Stone,
3283        };
3284
3285        let mut vm = vm!();
3286        vm.segments = segments![
3287            ((0, 0), 0x206800180018001_i64),
3288            ((1, 1), 0x4),
3289            ((0, 1), 0x4)
3290        ];
3291
3292        let expected_operands = Operands {
3293            dst: mayberelocatable!(4),
3294            res: None,
3295            op0: mayberelocatable!(4),
3296            op1: mayberelocatable!(4),
3297        };
3298
3299        let expected_addresses = OperandsAddresses {
3300            dst_addr: relocatable!(1, 1),
3301            op0_addr: relocatable!(1, 1),
3302            op1_addr: relocatable!(0, 1),
3303        };
3304
3305        let (operands, addresses, _) = vm.compute_operands(&instruction).unwrap();
3306        assert!(operands == expected_operands);
3307        assert!(addresses == expected_addresses);
3308        let mut hint_processor = BuiltinHintProcessor::new_empty();
3309        assert_matches!(
3310            vm.step(
3311                &mut hint_processor,
3312                exec_scopes_ref!(),
3313                &mut Vec::new(),
3314                #[cfg(feature = "extensive_hints")]
3315                &mut HashMap::new(),
3316                #[cfg(feature = "test_utils")]
3317                &HashMap::new(),
3318            ),
3319            Ok(())
3320        );
3321        assert_eq!(vm.run_context.pc, relocatable!(0, 4));
3322    }
3323
3324    #[test]
3325    fn compute_operands_deduce_dst_none() {
3326        let instruction = Instruction {
3327            off0: 2,
3328            off1: 0,
3329            off2: 0,
3330            dst_register: Register::FP,
3331            op0_register: Register::AP,
3332            op1_addr: Op1Addr::AP,
3333            res: Res::Unconstrained,
3334            pc_update: PcUpdate::Regular,
3335            ap_update: ApUpdate::Regular,
3336            fp_update: FpUpdate::Regular,
3337            opcode: Opcode::NOp,
3338            opcode_extension: OpcodeExtension::Stone,
3339        };
3340
3341        let mut vm = vm!();
3342
3343        vm.segments = segments!(((1, 0), 145944781867024385_i64));
3344
3345        let error = vm.compute_operands(&instruction).unwrap_err();
3346        assert_matches!(error, VirtualMachineError::NoDst);
3347    }
3348
3349    #[test]
3350    fn opcode_assertions_res_unconstrained() {
3351        let instruction = Instruction {
3352            off0: 1,
3353            off1: 2,
3354            off2: 3,
3355            dst_register: Register::FP,
3356            op0_register: Register::AP,
3357            op1_addr: Op1Addr::AP,
3358            res: Res::Add,
3359            pc_update: PcUpdate::Regular,
3360            ap_update: ApUpdate::Regular,
3361            fp_update: FpUpdate::APPlus2,
3362            opcode: Opcode::AssertEq,
3363            opcode_extension: OpcodeExtension::Stone,
3364        };
3365
3366        let operands = Operands {
3367            dst: MaybeRelocatable::Int(Felt252::from(8)),
3368            res: None,
3369            op0: MaybeRelocatable::Int(Felt252::from(9)),
3370            op1: MaybeRelocatable::Int(Felt252::from(10)),
3371        };
3372
3373        let vm = vm!();
3374
3375        let error = vm.opcode_assertions(&instruction, &operands);
3376        assert_matches!(error, Err(VirtualMachineError::UnconstrainedResAssertEq));
3377    }
3378
3379    #[test]
3380    fn opcode_assertions_instruction_failed() {
3381        let instruction = Instruction {
3382            off0: 1,
3383            off1: 2,
3384            off2: 3,
3385            dst_register: Register::FP,
3386            op0_register: Register::AP,
3387            op1_addr: Op1Addr::AP,
3388            res: Res::Add,
3389            pc_update: PcUpdate::Regular,
3390            ap_update: ApUpdate::Regular,
3391            fp_update: FpUpdate::APPlus2,
3392            opcode: Opcode::AssertEq,
3393            opcode_extension: OpcodeExtension::Stone,
3394        };
3395
3396        let operands = Operands {
3397            dst: MaybeRelocatable::Int(Felt252::from(9_i32)),
3398            res: Some(MaybeRelocatable::Int(Felt252::from(8_i32))),
3399            op0: MaybeRelocatable::Int(Felt252::from(9_i32)),
3400            op1: MaybeRelocatable::Int(Felt252::from(10_i32)),
3401        };
3402
3403        let vm = vm!();
3404
3405        assert_matches!(
3406            vm.opcode_assertions(&instruction, &operands),
3407            Err(VirtualMachineError::DiffAssertValues(bx))
3408            if *bx == (MaybeRelocatable::Int(Felt252::from(9_i32)),
3409                 MaybeRelocatable::Int(Felt252::from(8_i32)))
3410        );
3411    }
3412
3413    #[test]
3414    fn opcode_assertions_instruction_failed_relocatables() {
3415        let instruction = Instruction {
3416            off0: 1,
3417            off1: 2,
3418            off2: 3,
3419            dst_register: Register::FP,
3420            op0_register: Register::AP,
3421            op1_addr: Op1Addr::AP,
3422            res: Res::Add,
3423            pc_update: PcUpdate::Regular,
3424            ap_update: ApUpdate::Regular,
3425            fp_update: FpUpdate::APPlus2,
3426            opcode: Opcode::AssertEq,
3427            opcode_extension: OpcodeExtension::Stone,
3428        };
3429
3430        let operands = Operands {
3431            dst: MaybeRelocatable::from((1, 1)),
3432            res: Some(MaybeRelocatable::from((1, 2))),
3433            op0: MaybeRelocatable::Int(Felt252::from(9_i32)),
3434            op1: MaybeRelocatable::Int(Felt252::from(10_i32)),
3435        };
3436
3437        let vm = vm!();
3438
3439        assert_matches!(
3440            vm.opcode_assertions(&instruction, &operands),
3441            Err(VirtualMachineError::DiffAssertValues(bx)) if *bx == (MaybeRelocatable::from((1, 1)), MaybeRelocatable::from((1, 2)))
3442        );
3443    }
3444
3445    #[test]
3446    fn opcode_assertions_inconsistent_op0() {
3447        let instruction = Instruction {
3448            off0: 1,
3449            off1: 2,
3450            off2: 3,
3451            dst_register: Register::FP,
3452            op0_register: Register::AP,
3453            op1_addr: Op1Addr::AP,
3454            res: Res::Add,
3455            pc_update: PcUpdate::Regular,
3456            ap_update: ApUpdate::Regular,
3457            fp_update: FpUpdate::APPlus2,
3458            opcode: Opcode::Call,
3459            opcode_extension: OpcodeExtension::Stone,
3460        };
3461
3462        let operands = Operands {
3463            dst: mayberelocatable!(0, 8),
3464            res: Some(mayberelocatable!(8)),
3465            op0: mayberelocatable!(9),
3466            op1: mayberelocatable!(10),
3467        };
3468
3469        let mut vm = vm!();
3470        vm.run_context.pc = relocatable!(0, 4);
3471
3472        assert_matches!(
3473            vm.opcode_assertions(&instruction, &operands),
3474            Err(VirtualMachineError::CantWriteReturnPc(bx)) if *bx == (mayberelocatable!(9), mayberelocatable!(0, 5))
3475        );
3476    }
3477
3478    #[test]
3479    fn opcode_assertions_inconsistent_dst() {
3480        let instruction = Instruction {
3481            off0: 1,
3482            off1: 2,
3483            off2: 3,
3484            dst_register: Register::FP,
3485            op0_register: Register::AP,
3486            op1_addr: Op1Addr::AP,
3487            res: Res::Add,
3488            pc_update: PcUpdate::Regular,
3489            ap_update: ApUpdate::Regular,
3490            fp_update: FpUpdate::APPlus2,
3491            opcode: Opcode::Call,
3492            opcode_extension: OpcodeExtension::Stone,
3493        };
3494
3495        let operands = Operands {
3496            dst: mayberelocatable!(8),
3497            res: Some(mayberelocatable!(8)),
3498            op0: mayberelocatable!(0, 1),
3499            op1: mayberelocatable!(10),
3500        };
3501        let mut vm = vm!();
3502        vm.run_context.fp = 6;
3503
3504        assert_matches!(
3505            vm.opcode_assertions(&instruction, &operands),
3506            Err(VirtualMachineError::CantWriteReturnFp(bx)) if *bx == (mayberelocatable!(8), mayberelocatable!(1, 6))
3507        );
3508    }
3509
3510    #[test]
3511    /// Test for a simple program execution
3512    /// Used program code:
3513    /// func main():
3514    ///     let a = 1
3515    ///     let b = 2
3516    ///     let c = a + b
3517    ///     return()
3518    /// end
3519    /// Memory taken from original vm
3520    /// {RelocatableValue(segment_index=0, offset=0): 2345108766317314046,
3521    ///  RelocatableValue(segment_index=1, offset=0): RelocatableValue(segment_index=2, offset=0),
3522    ///  RelocatableValue(segment_index=1, offset=1): RelocatableValue(segment_index=3, offset=0)}
3523    /// Current register values:
3524    /// AP 1:2
3525    /// FP 1:2
3526    /// PC 0:0
3527    fn test_step_for_preset_memory() {
3528        let mut vm = vm!(true);
3529
3530        let mut hint_processor = BuiltinHintProcessor::new_empty();
3531
3532        run_context!(vm, 0, 2, 2);
3533
3534        vm.segments = segments![
3535            ((0, 0), 2345108766317314046_u64),
3536            ((1, 0), (2, 0)),
3537            ((1, 1), (3, 0))
3538        ];
3539
3540        assert_matches!(
3541            vm.step(
3542                &mut hint_processor,
3543                exec_scopes_ref!(),
3544                &mut Vec::new(),
3545                #[cfg(feature = "extensive_hints")]
3546                &mut HashMap::new(),
3547                #[cfg(feature = "test_utils")]
3548                &HashMap::new(),
3549            ),
3550            Ok(())
3551        );
3552        let trace = vm.trace.unwrap();
3553        trace_check(&trace, &[((0, 0).into(), 2, 2)]);
3554
3555        assert_eq!(vm.run_context.pc, Relocatable::from((3, 0)));
3556        assert_eq!(vm.run_context.ap, 2);
3557        assert_eq!(vm.run_context.fp, 0);
3558
3559        //Check that the following addresses have been accessed:
3560        // Addresses have been copied from python execution:
3561        let mem = vm.segments.memory.data;
3562        assert!(mem[1][0].is_accessed());
3563        assert!(mem[1][1].is_accessed());
3564    }
3565
3566    #[test]
3567    /*
3568    Test for a simple program execution
3569    Used program code:
3570        func myfunc(a: felt) -> (r: felt):
3571            let b = a * 2
3572            return(b)
3573        end
3574        func main():
3575            let a = 1
3576            let b = myfunc(a)
3577            return()
3578        end
3579    Memory taken from original vm:
3580    {RelocatableValue(segment_index=0, offset=0): 5207990763031199744,
3581    RelocatableValue(segment_index=0, offset=1): 2,
3582    RelocatableValue(segment_index=0, offset=2): 2345108766317314046,
3583    RelocatableValue(segment_index=0, offset=3): 5189976364521848832,
3584    RelocatableValue(segment_index=0, offset=4): 1,
3585    RelocatableValue(segment_index=0, offset=5): 1226245742482522112,
3586    RelocatableValue(segment_index=0, offset=6): 3618502788666131213697322783095070105623107215331596699973092056135872020476,
3587    RelocatableValue(segment_index=0, offset=7): 2345108766317314046,
3588    RelocatableValue(segment_index=1, offset=0): RelocatableValue(segment_index=2, offset=0),
3589    RelocatableValue(segment_index=1, offset=1): RelocatableValue(segment_index=3, offset=0)}
3590    Current register values:
3591    AP 1:2
3592    FP 1:2
3593    PC 0:3
3594    Final Pc (not executed): 3:0
3595    This program consists of 5 steps
3596    */
3597    fn test_step_for_preset_memory_function_call() {
3598        let mut vm = vm!(true);
3599
3600        run_context!(vm, 3, 2, 2);
3601
3602        //Insert values into memory
3603        vm.segments.memory =
3604            memory![
3605            ((0, 0), 5207990763031199744_i64),
3606            ((0, 1), 2),
3607            ((0, 2), 2345108766317314046_i64),
3608            ((0, 3), 5189976364521848832_i64),
3609            ((0, 4), 1),
3610            ((0, 5), 1226245742482522112_i64),
3611            (
3612                (0, 6),
3613                ("3618502788666131213697322783095070105623107215331596699973092056135872020476",10)
3614            ),
3615            ((0, 7), 2345108766317314046_i64),
3616            ((1, 0), (2, 0)),
3617            ((1, 1), (3, 0))
3618        ];
3619
3620        let final_pc = Relocatable::from((3, 0));
3621        let mut hint_processor = BuiltinHintProcessor::new_empty();
3622        //Run steps
3623        while vm.run_context.pc != final_pc {
3624            assert_matches!(
3625                vm.step(
3626                    &mut hint_processor,
3627                    exec_scopes_ref!(),
3628                    &mut Vec::new(),
3629                    #[cfg(feature = "extensive_hints")]
3630                    &mut HashMap::new(),
3631                    #[cfg(feature = "test_utils")]
3632                    &HashMap::new()
3633                ),
3634                Ok(())
3635            );
3636        }
3637
3638        //Check final register values
3639        assert_eq!(vm.run_context.pc, Relocatable::from((3, 0)));
3640
3641        assert_eq!(vm.run_context.ap, 6);
3642
3643        assert_eq!(vm.run_context.fp, 0);
3644        //Check each TraceEntry in trace
3645        let trace = vm.trace.unwrap();
3646        assert_eq!(trace.len(), 5);
3647        trace_check(
3648            &trace,
3649            &[
3650                ((0, 3).into(), 2, 2),
3651                ((0, 5).into(), 3, 2),
3652                ((0, 0).into(), 5, 5),
3653                ((0, 2).into(), 6, 5),
3654                ((0, 7).into(), 6, 2),
3655            ],
3656        );
3657        //Check that the following addresses have been accessed:
3658        // Addresses have been copied from python execution + addresses of accessed code:
3659        let mem = &vm.segments.memory.data;
3660        assert!(mem[0][0].is_accessed());
3661        assert!(mem[0][1].is_accessed());
3662        assert!(mem[0][2].is_accessed());
3663        assert!(mem[0][3].is_accessed());
3664        assert!(mem[0][4].is_accessed());
3665        assert!(mem[0][5].is_accessed());
3666        assert!(mem[0][6].is_accessed());
3667        assert!(mem[0][7].is_accessed());
3668        assert!(mem[1][0].is_accessed());
3669        assert!(mem[1][1].is_accessed());
3670        assert!(mem[1][2].is_accessed());
3671        assert!(mem[1][3].is_accessed());
3672        assert!(mem[1][4].is_accessed());
3673        assert!(mem[1][5].is_accessed());
3674        assert_eq!(
3675            vm.segments
3676                .memory
3677                .get_amount_of_accessed_addresses_for_segment(0),
3678            Some(8)
3679        );
3680        assert_eq!(
3681            vm.segments
3682                .memory
3683                .get_amount_of_accessed_addresses_for_segment(1),
3684            Some(6)
3685        );
3686    }
3687
3688    #[test]
3689    /// Test the following program:
3690    /// ...
3691    /// [ap] = 4
3692    /// ap += 1
3693    /// [ap] = 5; ap++
3694    /// [ap] = [ap - 1] * [ap - 2]
3695    /// ...
3696    /// Original vm memory:
3697    /// RelocatableValue(segment_index=0, offset=0): '0x400680017fff8000',
3698    /// RelocatableValue(segment_index=0, offset=1): '0x4',
3699    /// RelocatableValue(segment_index=0, offset=2): '0x40780017fff7fff',
3700    /// RelocatableValue(segment_index=0, offset=3): '0x1',
3701    /// RelocatableValue(segment_index=0, offset=4): '0x480680017fff8000',
3702    /// RelocatableValue(segment_index=0, offset=5): '0x5',
3703    /// RelocatableValue(segment_index=0, offset=6): '0x40507ffe7fff8000',
3704    /// RelocatableValue(segment_index=0, offset=7): '0x208b7fff7fff7ffe',
3705    /// RelocatableValue(segment_index=1, offset=0): RelocatableValue(segment_index=2, offset=0),
3706    /// RelocatableValue(segment_index=1, offset=1): RelocatableValue(segment_index=3, offset=0),
3707    /// RelocatableValue(segment_index=1, offset=2): '0x4',
3708    /// RelocatableValue(segment_index=1, offset=3): '0x5',
3709    /// RelocatableValue(segment_index=1, offset=4): '0x14'
3710    fn multiplication_and_different_ap_increase() {
3711        let mut vm = vm!();
3712        vm.segments = segments![
3713            ((0, 0), 0x400680017fff8000_i64),
3714            ((0, 1), 0x4),
3715            ((0, 2), 0x40780017fff7fff_i64),
3716            ((0, 3), 0x1),
3717            ((0, 4), 0x480680017fff8000_i64),
3718            ((0, 5), 0x5),
3719            ((0, 6), 0x40507ffe7fff8000_i64),
3720            ((0, 7), 0x208b7fff7fff7ffe_i64),
3721            ((1, 0), (2, 0)),
3722            ((1, 1), (3, 0)),
3723            ((1, 2), 0x4),
3724            ((1, 3), 0x5),
3725            ((1, 4), 0x14)
3726        ];
3727
3728        run_context!(vm, 0, 2, 2);
3729
3730        assert_eq!(vm.run_context.pc, Relocatable::from((0, 0)));
3731        assert_eq!(vm.run_context.ap, 2);
3732        let mut hint_processor = BuiltinHintProcessor::new_empty();
3733        assert_matches!(
3734            vm.step(
3735                &mut hint_processor,
3736                exec_scopes_ref!(),
3737                &mut Vec::new(),
3738                #[cfg(feature = "extensive_hints")]
3739                &mut HashMap::new(),
3740                #[cfg(feature = "test_utils")]
3741                &HashMap::new()
3742            ),
3743            Ok(())
3744        );
3745        assert_eq!(vm.run_context.pc, Relocatable::from((0, 2)));
3746        assert_eq!(vm.run_context.ap, 2);
3747
3748        assert_eq!(
3749            vm.segments
3750                .memory
3751                .get(&vm.run_context.get_ap())
3752                .unwrap()
3753                .as_ref(),
3754            &MaybeRelocatable::Int(Felt252::from(0x4)),
3755        );
3756        let mut hint_processor = BuiltinHintProcessor::new_empty();
3757        assert_matches!(
3758            vm.step(
3759                &mut hint_processor,
3760                exec_scopes_ref!(),
3761                &mut Vec::new(),
3762                #[cfg(feature = "extensive_hints")]
3763                &mut HashMap::new(),
3764                #[cfg(feature = "test_utils")]
3765                &HashMap::new()
3766            ),
3767            Ok(())
3768        );
3769        assert_eq!(vm.run_context.pc, Relocatable::from((0, 4)));
3770        assert_eq!(vm.run_context.ap, 3);
3771
3772        assert_eq!(
3773            vm.segments
3774                .memory
3775                .get(&vm.run_context.get_ap())
3776                .unwrap()
3777                .as_ref(),
3778            &MaybeRelocatable::Int(Felt252::from(0x5))
3779        );
3780
3781        let mut hint_processor = BuiltinHintProcessor::new_empty();
3782        assert_matches!(
3783            vm.step(
3784                &mut hint_processor,
3785                exec_scopes_ref!(),
3786                &mut Vec::new(),
3787                #[cfg(feature = "extensive_hints")]
3788                &mut HashMap::new(),
3789                #[cfg(feature = "test_utils")]
3790                &HashMap::new()
3791            ),
3792            Ok(())
3793        );
3794        assert_eq!(vm.run_context.pc, Relocatable::from((0, 6)));
3795        assert_eq!(vm.run_context.ap, 4);
3796
3797        assert_eq!(
3798            vm.segments
3799                .memory
3800                .get(&vm.run_context.get_ap())
3801                .unwrap()
3802                .as_ref(),
3803            &MaybeRelocatable::Int(Felt252::from(0x14)),
3804        );
3805    }
3806
3807    #[test]
3808    fn deduce_memory_cell_no_pedersen_builtin() {
3809        let vm = vm!();
3810        assert_matches!(vm.deduce_memory_cell(Relocatable::from((0, 0))), Ok(None));
3811    }
3812
3813    #[test]
3814    fn deduce_memory_cell_pedersen_builtin_valid() {
3815        let mut vm = vm!();
3816        let builtin = HashBuiltinRunner::new(Some(8), true);
3817        vm.builtin_runners.push(builtin.into());
3818        vm.segments = segments![((0, 3), 32), ((0, 4), 72), ((0, 5), 0)];
3819        assert_matches!(
3820            vm.deduce_memory_cell(Relocatable::from((0, 5))),
3821            Ok(i) if i == Some(MaybeRelocatable::from(crate::felt_hex!(
3822                "0x73b3ec210cccbb970f80c6826fb1c40ae9f487617696234ff147451405c339f"
3823            )))
3824        );
3825    }
3826
3827    #[test]
3828    /* Program used:
3829    %builtins output pedersen
3830    from starkware.cairo.common.cairo_builtins import HashBuiltin
3831    from starkware.cairo.common.hash import hash2
3832    from starkware.cairo.common.serialize import serialize_word
3833
3834    func foo(hash_ptr : HashBuiltin*) -> (
3835        hash_ptr : HashBuiltin*, z
3836    ):
3837        # Use a with-statement, since 'hash_ptr' is not an
3838        # implicit argument.
3839        with hash_ptr:
3840            let (z) = hash2(32, 72)
3841        end
3842        return (hash_ptr=hash_ptr, z=z)
3843    end
3844
3845    func main{output_ptr: felt*, pedersen_ptr: HashBuiltin*}():
3846        let (pedersen_ptr, a) = foo(pedersen_ptr)
3847        serialize_word(a)
3848        return()
3849    end
3850     */
3851    fn compute_operands_pedersen() {
3852        let instruction = Instruction {
3853            off0: 0,
3854            off1: -5,
3855            off2: 2,
3856            dst_register: Register::AP,
3857            op0_register: Register::FP,
3858            op1_addr: Op1Addr::Op0,
3859            res: Res::Op1,
3860            pc_update: PcUpdate::Regular,
3861            ap_update: ApUpdate::Add1,
3862            fp_update: FpUpdate::Regular,
3863            opcode: Opcode::AssertEq,
3864            opcode_extension: OpcodeExtension::Stone,
3865        };
3866        let mut builtin = HashBuiltinRunner::new(Some(8), true);
3867        builtin.base = 3;
3868        let mut vm = vm!();
3869        vm.builtin_runners.push(builtin.into());
3870        run_context!(vm, 0, 13, 12);
3871
3872        //Insert values into memory (excluding those from the program segment (instructions))
3873        vm.segments = segments![
3874            ((3, 0), 32),
3875            ((3, 1), 72),
3876            ((1, 0), (2, 0)),
3877            ((1, 1), (3, 0)),
3878            ((1, 2), (4, 0)),
3879            ((1, 3), (5, 0)),
3880            ((1, 4), (3, 0)),
3881            ((1, 5), (1, 4)),
3882            ((1, 6), (0, 21)),
3883            ((1, 7), (3, 0)),
3884            ((1, 8), 32),
3885            ((1, 9), 72),
3886            ((1, 10), (1, 7)),
3887            ((1, 11), (0, 17)),
3888            ((1, 12), (3, 3))
3889        ];
3890
3891        let expected_operands = Operands {
3892            dst: MaybeRelocatable::from(crate::felt_hex!(
3893                "0x73b3ec210cccbb970f80c6826fb1c40ae9f487617696234ff147451405c339f"
3894            )),
3895            res: Some(MaybeRelocatable::from(crate::felt_hex!(
3896                "0x73b3ec210cccbb970f80c6826fb1c40ae9f487617696234ff147451405c339f"
3897            ))),
3898            op0: MaybeRelocatable::from((3, 0)),
3899            op1: MaybeRelocatable::from(crate::felt_hex!(
3900                "0x73b3ec210cccbb970f80c6826fb1c40ae9f487617696234ff147451405c339f"
3901            )),
3902        };
3903        let expected_operands_mem_addresses = OperandsAddresses {
3904            dst_addr: Relocatable::from((1, 13)),
3905            op0_addr: Relocatable::from((1, 7)),
3906            op1_addr: Relocatable::from((3, 2)),
3907        };
3908        let (operands, operands_mem_address, _) = vm.compute_operands(&instruction).unwrap();
3909        assert_eq!(operands, expected_operands);
3910        assert_eq!(operands_mem_address, expected_operands_mem_addresses);
3911    }
3912
3913    #[test]
3914    fn deduce_memory_cell_bitwise_builtin_valid_and() {
3915        let mut vm = vm!();
3916        let builtin = BitwiseBuiltinRunner::new(Some(256), true);
3917        vm.builtin_runners.push(builtin.into());
3918        vm.segments = segments![((0, 5), 10), ((0, 6), 12), ((0, 7), 0)];
3919        assert_matches!(
3920            vm.deduce_memory_cell(Relocatable::from((0, 7))),
3921            Ok(i) if i == Some(MaybeRelocatable::from(Felt252::from(8_i32)))
3922        );
3923    }
3924
3925    #[test]
3926    /* Program used:
3927    %builtins bitwise
3928    from starkware.cairo.common.bitwise import bitwise_and
3929    from starkware.cairo.common.cairo_builtins import BitwiseBuiltin
3930
3931    func main{bitwise_ptr: BitwiseBuiltin*}():
3932        let (result) = bitwise_and(12, 10)  # Binary (1100, 1010).
3933        assert result = 8  # Binary 1000.
3934        return()
3935    end
3936    */
3937    fn compute_operands_bitwise() {
3938        let instruction = Instruction {
3939            off0: 0,
3940            off1: -5,
3941            off2: 2,
3942            dst_register: Register::AP,
3943            op0_register: Register::FP,
3944            op1_addr: Op1Addr::Op0,
3945            res: Res::Op1,
3946            pc_update: PcUpdate::Regular,
3947            ap_update: ApUpdate::Add1,
3948            fp_update: FpUpdate::Regular,
3949            opcode: Opcode::AssertEq,
3950            opcode_extension: OpcodeExtension::Stone,
3951        };
3952
3953        let mut builtin = BitwiseBuiltinRunner::new(Some(256), true);
3954        builtin.base = 2;
3955        let mut vm = vm!();
3956
3957        vm.builtin_runners.push(builtin.into());
3958        run_context!(vm, 0, 9, 8);
3959
3960        //Insert values into memory (excluding those from the program segment (instructions))
3961        vm.segments = segments![
3962            ((2, 0), 12),
3963            ((2, 1), 10),
3964            ((1, 0), (2, 0)),
3965            ((1, 1), (3, 0)),
3966            ((1, 2), (4, 0)),
3967            ((1, 3), (2, 0)),
3968            ((1, 4), 12),
3969            ((1, 5), 10),
3970            ((1, 6), (1, 3)),
3971            ((1, 7), (0, 13))
3972        ];
3973
3974        let expected_operands = Operands {
3975            dst: MaybeRelocatable::from(Felt252::from(8_i32)),
3976            res: Some(MaybeRelocatable::from(Felt252::from(8_i32))),
3977            op0: MaybeRelocatable::from((2, 0)),
3978            op1: MaybeRelocatable::from(Felt252::from(8_i32)),
3979        };
3980        let expected_operands_mem_addresses = OperandsAddresses {
3981            dst_addr: Relocatable::from((1, 9)),
3982            op0_addr: Relocatable::from((1, 3)),
3983            op1_addr: Relocatable::from((2, 2)),
3984        };
3985        let (operands, operands_mem_address, _) = vm.compute_operands(&instruction).unwrap();
3986        assert_eq!(operands, expected_operands);
3987        assert_eq!(operands_mem_address, expected_operands_mem_addresses);
3988    }
3989
3990    #[test]
3991    fn deduce_memory_cell_ec_op_builtin_valid() {
3992        let mut vm = vm!();
3993        let builtin = EcOpBuiltinRunner::new(Some(256), true);
3994        vm.builtin_runners.push(builtin.into());
3995
3996        vm.segments = segments![
3997            (
3998                (0, 0),
3999                (
4000                    "0x68caa9509b7c2e90b4d92661cbf7c465471c1e8598c5f989691eef6653e0f38",
4001                    16
4002                )
4003            ),
4004            (
4005                (0, 1),
4006                (
4007                    "0x79a8673f498531002fc549e06ff2010ffc0c191cceb7da5532acb95cdcb591",
4008                    16
4009                )
4010            ),
4011            (
4012                (0, 2),
4013                (
4014                    "0x1ef15c18599971b7beced415a40f0c7deacfd9b0d1819e03d723d8bc943cfca",
4015                    16
4016                )
4017            ),
4018            (
4019                (0, 3),
4020                (
4021                    "0x5668060aa49730b7be4801df46ec62de53ecd11abe43a32873000c36e8dc1f",
4022                    16
4023                )
4024            ),
4025            ((0, 4), 34),
4026            (
4027                (0, 5),
4028                (
4029                    "0x6245403e2fafe5df3b79ea28d050d477771bc560fc59e915b302cc9b70a92f5",
4030                    16
4031                )
4032            )
4033        ];
4034
4035        assert_matches!(
4036            vm.deduce_memory_cell(Relocatable::from((0, 6))),
4037            Ok(i) if i == Some(MaybeRelocatable::from(felt_hex!(
4038                "0x7f49de2c3a7d1671437406869edb1805ba43e1c0173b35f8c2e8fcc13c3fa6d"
4039            )))
4040        );
4041    }
4042
4043    #[test]
4044    /* Data taken from this program execution:
4045       %builtins output ec_op
4046       from starkware.cairo.common.cairo_builtins import EcOpBuiltin
4047       from starkware.cairo.common.serialize import serialize_word
4048       from starkware.cairo.common.ec_point import EcPoint
4049       from starkware.cairo.common.ec import ec_op
4050
4051       func main{output_ptr: felt*, ec_op_ptr: EcOpBuiltin*}():
4052           let x: EcPoint = EcPoint(2089986280348253421170679821480865132823066470938446095505822317253594081284, 1713931329540660377023406109199410414810705867260802078187082345529207694986)
4053
4054           let y: EcPoint = EcPoint(874739451078007766457464989774322083649278607533249481151382481072868806602,152666792071518830868575557812948353041420400780739481342941381225525861407)
4055           let z: EcPoint = ec_op(x,34, y)
4056           serialize_word(z.x)
4057           return()
4058           end
4059    */
4060    fn verify_auto_deductions_for_ec_op_builtin_valid() {
4061        let mut builtin = EcOpBuiltinRunner::new(Some(256), true);
4062        builtin.base = 3;
4063        let mut vm = vm!();
4064        vm.builtin_runners.push(builtin.into());
4065        vm.segments = segments![
4066            (
4067                (3, 0),
4068                (
4069                    "2962412995502985605007699495352191122971573493113767820301112397466445942584",
4070                    10
4071                )
4072            ),
4073            (
4074                (3, 1),
4075                (
4076                    "214950771763870898744428659242275426967582168179217139798831865603966154129",
4077                    10
4078                )
4079            ),
4080            (
4081                (3, 2),
4082                (
4083                    "874739451078007766457464989774322083649278607533249481151382481072868806602",
4084                    10
4085                )
4086            ),
4087            (
4088                (3, 3),
4089                (
4090                    "152666792071518830868575557812948353041420400780739481342941381225525861407",
4091                    10
4092                )
4093            ),
4094            ((3, 4), 34),
4095            (
4096                (3, 5),
4097                (
4098                    "2778063437308421278851140253538604815869848682781135193774472480292420096757",
4099                    10
4100                )
4101            )
4102        ];
4103        assert_matches!(vm.verify_auto_deductions(), Ok(()));
4104    }
4105
4106    #[test]
4107    fn verify_auto_deductions_for_ec_op_builtin_valid_points_invalid_result() {
4108        let mut builtin = EcOpBuiltinRunner::new(Some(256), true);
4109        builtin.base = 3;
4110        let mut vm = vm!();
4111        vm.builtin_runners.push(builtin.into());
4112        vm.segments = segments![
4113            (
4114                (3, 0),
4115                (
4116                    "2962412995502985605007699495352191122971573493113767820301112397466445942584",
4117                    10
4118                )
4119            ),
4120            (
4121                (3, 1),
4122                (
4123                    "214950771763870898744428659242275426967582168179217139798831865603966154129",
4124                    10
4125                )
4126            ),
4127            (
4128                (3, 2),
4129                (
4130                    "2089986280348253421170679821480865132823066470938446095505822317253594081284",
4131                    10
4132                )
4133            ),
4134            (
4135                (3, 3),
4136                (
4137                    "1713931329540660377023406109199410414810705867260802078187082345529207694986",
4138                    10
4139                )
4140            ),
4141            ((3, 4), 34),
4142            (
4143                (3, 5),
4144                (
4145                    "2778063437308421278851140253538604815869848682781135193774472480292420096757",
4146                    10
4147                )
4148            )
4149        ];
4150        let error = vm.verify_auto_deductions();
4151        assert_matches!(
4152            error,
4153            Err(VirtualMachineError::InconsistentAutoDeduction(bx))
4154            if *bx == (BuiltinName::ec_op,
4155                    MaybeRelocatable::Int(crate::felt_str!(
4156                        "2739017437753868763038285897969098325279422804143820990343394856167768859289"
4157                    )),
4158                    Some(MaybeRelocatable::Int(crate::felt_str!(
4159                        "2778063437308421278851140253538604815869848682781135193774472480292420096757"
4160                    ))))
4161        );
4162    }
4163
4164    #[test]
4165    /* Program used:
4166    %builtins bitwise
4167    from starkware.cairo.common.bitwise import bitwise_and
4168    from starkware.cairo.common.cairo_builtins import BitwiseBuiltin
4169
4170    func main{bitwise_ptr: BitwiseBuiltin*}():
4171        let (result) = bitwise_and(12, 10)  # Binary (1100, 1010).
4172        assert result = 8  # Binary 1000.
4173        return()
4174    end
4175    */
4176    fn verify_auto_deductions_bitwise() {
4177        let mut builtin = BitwiseBuiltinRunner::new(Some(256), true);
4178        builtin.base = 2;
4179        let mut vm = vm!();
4180        vm.builtin_runners.push(builtin.into());
4181        vm.segments = segments![((2, 0), 12), ((2, 1), 10)];
4182        assert_matches!(vm.verify_auto_deductions(), Ok(()));
4183    }
4184
4185    #[test]
4186    /* Program used:
4187    %builtins bitwise
4188    from starkware.cairo.common.bitwise import bitwise_and
4189    from starkware.cairo.common.cairo_builtins import BitwiseBuiltin
4190
4191    func main{bitwise_ptr: BitwiseBuiltin*}():
4192        let (result) = bitwise_and(12, 10)  # Binary (1100, 1010).
4193        assert result = 8  # Binary 1000.
4194        return()
4195    end
4196    */
4197    fn verify_auto_deductions_for_addr_bitwise() {
4198        let mut builtin = BitwiseBuiltinRunner::new(Some(256), true);
4199        builtin.base = 2;
4200        let builtin: BuiltinRunner = builtin.into();
4201        let mut vm = vm!();
4202        vm.segments = segments![((2, 0), 12), ((2, 1), 10)];
4203        assert_matches!(
4204            vm.verify_auto_deductions_for_addr(relocatable!(2, 0), &builtin),
4205            Ok(())
4206        );
4207        assert_matches!(
4208            vm.verify_auto_deductions_for_addr(relocatable!(2, 1), &builtin),
4209            Ok(())
4210        );
4211    }
4212
4213    #[test]
4214    /* Program used:
4215    %builtins output pedersen
4216    from starkware.cairo.common.cairo_builtins import HashBuiltin
4217    from starkware.cairo.common.hash import hash2
4218    from starkware.cairo.common.serialize import serialize_word
4219
4220    func foo(hash_ptr : HashBuiltin*) -> (
4221        hash_ptr : HashBuiltin*, z
4222    ):
4223        # Use a with-statement, since 'hash_ptr' is not an
4224        # implicit argument.
4225        with hash_ptr:
4226            let (z) = hash2(32, 72)
4227        end
4228        return (hash_ptr=hash_ptr, z=z)
4229    end
4230
4231    func main{output_ptr: felt*, pedersen_ptr: HashBuiltin*}():
4232        let (pedersen_ptr, a) = foo(pedersen_ptr)
4233        serialize_word(a)
4234        return()
4235    end
4236     */
4237    fn verify_auto_deductions_pedersen() {
4238        let mut builtin = HashBuiltinRunner::new(Some(8), true);
4239        builtin.base = 3;
4240        let mut vm = vm!();
4241        vm.builtin_runners.push(builtin.into());
4242        vm.segments = segments![((3, 0), 32), ((3, 1), 72)];
4243        assert_matches!(vm.verify_auto_deductions(), Ok(()));
4244    }
4245
4246    #[test]
4247    fn can_get_return_values() {
4248        let mut vm = vm!();
4249        vm.set_ap(4);
4250        vm.segments = segments![((1, 0), 1), ((1, 1), 2), ((1, 2), 3), ((1, 3), 4)];
4251        let expected = vec![
4252            MaybeRelocatable::Int(Felt252::from(1_i32)),
4253            MaybeRelocatable::Int(Felt252::from(2_i32)),
4254            MaybeRelocatable::Int(Felt252::from(3_i32)),
4255            MaybeRelocatable::Int(Felt252::from(4_i32)),
4256        ];
4257        assert_eq!(vm.get_return_values(4).unwrap(), expected);
4258    }
4259
4260    #[test]
4261    fn get_return_values_fails_when_ap_is_0() {
4262        let mut vm = vm!();
4263        vm.segments = segments![((1, 0), 1), ((1, 1), 2), ((1, 2), 3), ((1, 3), 4)];
4264        assert_matches!(vm.get_return_values(3),
4265            Err(MemoryError::FailedToGetReturnValues(bx))
4266            if *bx == (3, Relocatable::from((1,0))));
4267    }
4268
4269    /*
4270    Program used for this test:
4271    from starkware.cairo.common.alloc import alloc
4272    func main{}():
4273        let vec: felt* = alloc()
4274        assert vec[0] = 1
4275        return()
4276    end
4277    Memory: {RelocatableValue(segment_index=0, offset=0): 290341444919459839,
4278        RelocatableValue(segment_index=0, offset=1): 1,
4279        RelocatableValue(segment_index=0, offset=2): 2345108766317314046,
4280        RelocatableValue(segment_index=0, offset=3): 1226245742482522112,
4281        RelocatableValue(segment_index=0, offset=4): 3618502788666131213697322783095070105623107215331596699973092056135872020478,
4282        RelocatableValue(segment_index=0, offset=5): 5189976364521848832,
4283        RelocatableValue(segment_index=0, offset=6): 1,
4284        RelocatableValue(segment_index=0, offset=7): 4611826758063128575,
4285        RelocatableValue(segment_index=0, offset=8): 2345108766317314046,
4286        RelocatableValue(segment_index=1, offset=0): RelocatableValue(segment_index=2, offset=0),
4287        RelocatableValue(segment_index=1, offset=1): RelocatableValue(segment_index=3, offset=0)}
4288     */
4289
4290    #[test]
4291    fn test_step_for_preset_memory_with_alloc_hint() {
4292        let mut vm = vm!(true);
4293        let hint_data = vec![any_box!(HintProcessorData::new_default(
4294            "memory[ap] = segments.add()".to_string(),
4295            HashMap::new(),
4296        ))];
4297
4298        //Initialzie registers
4299        run_context!(vm, 3, 2, 2);
4300
4301        //Create program and execution segments
4302        for _ in 0..2 {
4303            vm.segments.add();
4304        }
4305        //Initialize memory
4306
4307        let mut hint_processor = BuiltinHintProcessor::new_empty();
4308
4309        vm.segments = segments![
4310            ((0, 0), 290341444919459839_i64),
4311            ((0, 1), 1),
4312            ((0, 2), 2345108766317314046_i64),
4313            ((0, 3), 1226245742482522112_i64),
4314            (
4315                (0, 4),
4316                (
4317                    "3618502788666131213697322783095070105623107215331596699973092056135872020478",
4318                    10
4319                )
4320            ),
4321            ((0, 5), 5189976364521848832_i64),
4322            ((0, 6), 1),
4323            ((0, 7), 4611826758063128575_i64),
4324            ((0, 8), 2345108766317314046_i64),
4325            ((1, 0), (2, 0)),
4326            ((1, 1), (3, 0))
4327        ];
4328
4329        #[cfg(feature = "extensive_hints")]
4330        let mut hint_data = hint_data;
4331
4332        //Run Steps
4333        for _ in 0..6 {
4334            #[cfg(not(feature = "extensive_hints"))]
4335            let mut hint_data = if vm.run_context.pc == (0, 0).into() {
4336                &hint_data[0..]
4337            } else {
4338                &hint_data[0..0]
4339            };
4340            assert_matches!(
4341                vm.step(
4342                    &mut hint_processor,
4343                    exec_scopes_ref!(),
4344                    &mut hint_data,
4345                    #[cfg(feature = "extensive_hints")]
4346                    &mut HashMap::from([(
4347                        Relocatable::from((0, 0)),
4348                        (0_usize, NonZeroUsize::new(1).unwrap())
4349                    )]),
4350                    #[cfg(feature = "test_utils")]
4351                    &HashMap::new(),
4352                ),
4353                Ok(())
4354            );
4355        }
4356        //Compare trace
4357        let trace = vm.trace.unwrap();
4358        trace_check(
4359            &trace,
4360            &[
4361                ((0, 3).into(), 2, 2),
4362                ((0, 0).into(), 4, 4),
4363                ((0, 2).into(), 5, 4),
4364                ((0, 5).into(), 5, 2),
4365                ((0, 7).into(), 6, 2),
4366                ((0, 8).into(), 6, 2),
4367            ],
4368        );
4369
4370        //Compare final register values
4371        assert_eq!(vm.run_context.pc, Relocatable::from((3, 0)));
4372        assert_eq!(vm.run_context.ap, 6);
4373        assert_eq!(vm.run_context.fp, 0);
4374
4375        //Check that the array created through alloc contains the element we inserted
4376        //As there are no builtins present, the next segment crated will have the index 2
4377        check_memory!(vm.segments.memory, ((2, 0), 1));
4378    }
4379
4380    #[test]
4381    fn test_get_builtin_runners() {
4382        let mut vm = vm!();
4383        let hash_builtin = HashBuiltinRunner::new(Some(8), true);
4384        let bitwise_builtin = BitwiseBuiltinRunner::new(Some(256), true);
4385        vm.builtin_runners.push(hash_builtin.into());
4386        vm.builtin_runners.push(bitwise_builtin.into());
4387
4388        let builtins = vm.get_builtin_runners();
4389
4390        assert_eq!(builtins[0].name(), BuiltinName::pedersen);
4391        assert_eq!(builtins[1].name(), BuiltinName::bitwise);
4392    }
4393
4394    #[test]
4395    fn test_get_output_builtin_mut() {
4396        let mut vm = vm!();
4397
4398        assert_matches!(
4399            vm.get_output_builtin_mut(),
4400            Err(VirtualMachineError::NoOutputBuiltin)
4401        );
4402
4403        let output_builtin = OutputBuiltinRunner::new(true);
4404        vm.builtin_runners.push(output_builtin.clone().into());
4405
4406        let vm_output_builtin = vm
4407            .get_output_builtin_mut()
4408            .expect("Output builtin should be returned");
4409
4410        assert_eq!(vm_output_builtin.base(), output_builtin.base());
4411        assert_eq!(vm_output_builtin.pages, output_builtin.pages);
4412        assert_eq!(vm_output_builtin.attributes, output_builtin.attributes);
4413        assert_eq!(vm_output_builtin.stop_ptr, output_builtin.stop_ptr);
4414        assert_eq!(vm_output_builtin.included, output_builtin.included);
4415    }
4416
4417    #[test]
4418    fn get_range_for_continuous_memory() {
4419        let mut vm = vm!();
4420        vm.segments = segments![((1, 0), 2), ((1, 1), 3), ((1, 2), 4)];
4421
4422        let value1 = MaybeRelocatable::from(Felt252::from(2_i32));
4423        let value2 = MaybeRelocatable::from(Felt252::from(3_i32));
4424        let value3 = MaybeRelocatable::from(Felt252::from(4_i32));
4425
4426        let expected_vec = vec![
4427            Some(Cow::Borrowed(&value1)),
4428            Some(Cow::Borrowed(&value2)),
4429            Some(Cow::Borrowed(&value3)),
4430        ];
4431        assert_eq!(vm.get_range(Relocatable::from((1, 0)), 3), expected_vec);
4432    }
4433
4434    #[test]
4435    fn get_range_for_non_continuous_memory() {
4436        let mut vm = vm!();
4437        vm.segments = segments![((1, 0), 2), ((1, 1), 3), ((1, 3), 4)];
4438
4439        let value1 = MaybeRelocatable::from(Felt252::from(2_i32));
4440        let value2 = MaybeRelocatable::from(Felt252::from(3_i32));
4441        let value3 = MaybeRelocatable::from(Felt252::from(4_i32));
4442
4443        let expected_vec = vec![
4444            Some(Cow::Borrowed(&value1)),
4445            Some(Cow::Borrowed(&value2)),
4446            None,
4447            Some(Cow::Borrowed(&value3)),
4448        ];
4449        assert_eq!(vm.get_range(Relocatable::from((1, 0)), 4), expected_vec);
4450    }
4451
4452    #[test]
4453    fn get_continuous_range_for_continuous_memory() {
4454        let mut vm = vm!();
4455        vm.segments = segments![((1, 0), 2), ((1, 1), 3), ((1, 2), 4)];
4456
4457        let value1 = MaybeRelocatable::from(Felt252::from(2_i32));
4458        let value2 = MaybeRelocatable::from(Felt252::from(3_i32));
4459        let value3 = MaybeRelocatable::from(Felt252::from(4_i32));
4460
4461        let expected_vec = vec![value1, value2, value3];
4462        assert_eq!(
4463            vm.get_continuous_range(Relocatable::from((1, 0)), 3),
4464            Ok(expected_vec)
4465        );
4466    }
4467
4468    #[test]
4469    fn get_continuous_range_for_non_continuous_memory() {
4470        let mut vm = vm!();
4471        vm.segments = segments![((1, 0), 2), ((1, 1), 3), ((1, 3), 4)];
4472
4473        assert_eq!(
4474            vm.get_continuous_range(Relocatable::from((1, 0)), 3),
4475            Err(MemoryError::GetRangeMemoryGap(Box::new(((1, 0).into(), 3))))
4476        );
4477    }
4478
4479    #[test]
4480    fn get_segment_used_size_after_computing_used() {
4481        let mut vm = vm!();
4482        vm.segments = segments![
4483            ((0, 2), 1),
4484            ((0, 5), 1),
4485            ((0, 7), 1),
4486            ((1, 1), 1),
4487            ((2, 2), 1),
4488            ((2, 4), 1),
4489            ((2, 7), 1)
4490        ];
4491        vm.segments.compute_effective_sizes();
4492        assert_eq!(Some(8), vm.get_segment_used_size(2));
4493    }
4494
4495    #[test]
4496    fn get_segment_size_before_computing_used() {
4497        let vm = vm!();
4498        assert_eq!(None, vm.get_segment_size(2));
4499    }
4500
4501    #[test]
4502    fn get_segment_size_before_computing_used_set_size() {
4503        let mut vm = vm!();
4504        vm.segments.segment_sizes.insert(2, 2);
4505        assert_eq!(Some(2), vm.get_segment_size(2));
4506    }
4507
4508    #[test]
4509    fn get_segment_size_after_computing_used() {
4510        let mut vm = vm!();
4511        vm.segments = segments![
4512            ((0, 2), 1),
4513            ((0, 5), 1),
4514            ((0, 7), 1),
4515            ((1, 1), 1),
4516            ((2, 2), 1),
4517            ((2, 4), 1),
4518            ((2, 7), 1)
4519        ];
4520        vm.segments.compute_effective_sizes();
4521        assert_eq!(Some(8), vm.get_segment_size(2));
4522    }
4523
4524    #[test]
4525    fn get_segment_used_size_before_computing_used() {
4526        let vm = vm!();
4527        assert_eq!(None, vm.get_segment_used_size(2));
4528    }
4529
4530    #[test]
4531    fn get_and_set_pc() {
4532        let mut vm = vm!();
4533        vm.set_pc(Relocatable {
4534            segment_index: 3,
4535            offset: 4,
4536        });
4537        assert_eq!(
4538            vm.get_pc(),
4539            Relocatable {
4540                segment_index: 3,
4541                offset: 4
4542            }
4543        )
4544    }
4545
4546    #[test]
4547    fn get_and_set_fp() {
4548        let mut vm = vm!();
4549        vm.set_fp(3);
4550        assert_eq!(
4551            vm.get_fp(),
4552            Relocatable {
4553                segment_index: 1,
4554                offset: 3
4555            }
4556        )
4557    }
4558
4559    #[test]
4560    fn get_maybe_key_not_in_memory() {
4561        let vm = vm!();
4562        assert_eq!(
4563            vm.get_maybe(&Relocatable {
4564                segment_index: 5,
4565                offset: 2
4566            }),
4567            None
4568        );
4569    }
4570
4571    #[test]
4572    fn get_maybe_error() {
4573        let vm = vm!();
4574        assert_eq!(
4575            vm.get_maybe(&MaybeRelocatable::Int(Felt252::from(0_i32))),
4576            None,
4577        );
4578    }
4579
4580    #[test]
4581    fn end_run_error() {
4582        let mut vm = vm!();
4583        let scopes = exec_scopes_ref!();
4584        scopes.enter_scope(HashMap::new());
4585
4586        assert_matches!(
4587            vm.end_run(scopes, false),
4588            Err(VirtualMachineError::MainScopeError(
4589                ExecScopeError::NoScopeError
4590            ))
4591        );
4592    }
4593
4594    #[test]
4595    fn add_temporary_segments() {
4596        let mut vm = vm!();
4597        let mut _base = vm.add_temporary_segment();
4598        assert_eq!(
4599            _base,
4600            Relocatable {
4601                segment_index: -1,
4602                offset: 0
4603            }
4604        );
4605        let mut _base = vm.add_temporary_segment();
4606        assert_eq!(
4607            _base,
4608            Relocatable {
4609                segment_index: -2,
4610                offset: 0
4611            }
4612        );
4613    }
4614
4615    #[test]
4616    fn decode_current_instruction_invalid_encoding() {
4617        let mut vm = vm!();
4618        vm.segments = segments![((0, 0), ("112233445566778899112233445566778899", 16))];
4619        assert_matches!(
4620            vm.decode_current_instruction(),
4621            Err(VirtualMachineError::InvalidInstructionEncoding)
4622        );
4623    }
4624
4625    #[test]
4626    fn add_relocation_rule_test() {
4627        let mut vm = vm!();
4628
4629        assert_eq!(
4630            vm.add_relocation_rule((-1, 0).into(), (1, 2).into()),
4631            Ok(()),
4632        );
4633        assert_eq!(
4634            vm.add_relocation_rule((-2, 0).into(), (-1, 1).into()),
4635            Ok(()),
4636        );
4637        assert_eq!(
4638            vm.add_relocation_rule((5, 0).into(), (0, 0).into()),
4639            Err(MemoryError::AddressNotInTemporarySegment(5)),
4640        );
4641        assert_eq!(
4642            vm.add_relocation_rule((-3, 6).into(), (0, 0).into()),
4643            Err(MemoryError::NonZeroOffset(6)),
4644        );
4645        assert_eq!(
4646            vm.add_relocation_rule((-1, 0).into(), (0, 0).into()),
4647            Err(MemoryError::DuplicatedRelocation(-1)),
4648        );
4649    }
4650
4651    #[test]
4652    fn gen_arg_relocatable() {
4653        let mut vm = vm!();
4654
4655        assert_matches!(
4656            vm.gen_arg(&mayberelocatable!(0, 0)),
4657            Ok(x) if x == mayberelocatable!(0, 0)
4658        );
4659    }
4660
4661    /// Test that the call to .gen_arg() with a bigint and no prime number just
4662    /// passes the value through.
4663    #[test]
4664    fn gen_arg_bigint() {
4665        let mut vm = vm!();
4666
4667        assert_matches!(
4668            vm.gen_arg(&mayberelocatable!(1234)),
4669            Ok(x) if x == mayberelocatable!(1234)
4670        );
4671    }
4672
4673    /// Test that the call to .gen_arg() with a bigint and a prime number passes
4674    /// the value through after applying the modulo.
4675    #[test]
4676    fn gen_arg_bigint_prime() {
4677        let mut vm = vm!();
4678        let prime = felt_hex!(crate::utils::PRIME_STR);
4679        let prime_maybe = MaybeRelocatable::from(prime);
4680
4681        assert_matches!(vm.gen_arg(&prime_maybe), Ok(x) if x == mayberelocatable!(0));
4682    }
4683
4684    /// Test that the call to .gen_arg() with a Vec<MaybeRelocatable> writes its
4685    /// contents into a new segment and returns a pointer to it.
4686    #[test]
4687    fn gen_arg_vec() {
4688        let mut vm = vm!();
4689
4690        assert_matches!(
4691            vm.gen_arg(&vec![
4692                mayberelocatable!(0),
4693                mayberelocatable!(1),
4694                mayberelocatable!(2),
4695                mayberelocatable!(3),
4696                mayberelocatable!(0, 0),
4697                mayberelocatable!(0, 1),
4698                mayberelocatable!(0, 2),
4699                mayberelocatable!(0, 3),
4700            ]),
4701            Ok(x) if x == mayberelocatable!(0, 0)
4702        );
4703    }
4704
4705    /// Test that compute_effective_sizes() works as intended.
4706    #[test]
4707    fn compute_effective_sizes() {
4708        let mut vm = vm!();
4709
4710        let segment = vm.segments.add();
4711        vm.load_data(
4712            segment,
4713            &[
4714                mayberelocatable!(1),
4715                mayberelocatable!(2),
4716                mayberelocatable!(3),
4717                mayberelocatable!(4),
4718            ],
4719        )
4720        .expect("Could not load data into memory.");
4721
4722        assert_eq!(vm.segments.compute_effective_sizes(), &vec![4]);
4723    }
4724
4725    /// Test that compute_segment_effective_sizes() works as intended.
4726    #[test]
4727    fn compute_segment_effective_sizes() {
4728        let mut vm = vm!();
4729
4730        let segment = vm.segments.add();
4731        vm.load_data(
4732            segment,
4733            &[
4734                mayberelocatable!(1),
4735                mayberelocatable!(2),
4736                mayberelocatable!(3),
4737                mayberelocatable!(4),
4738            ],
4739        )
4740        .expect("Could not load data into memory.");
4741
4742        assert_eq!(vm.segments.compute_effective_sizes(), &vec![4]);
4743    }
4744
4745    #[test]
4746    fn test_delete_unaccessed() {
4747        let mut vm = vm!();
4748
4749        let segment0 = vm.segments.add();
4750        let segment1 = vm.segments.add();
4751        let segment2 = vm.segments.add();
4752        let segment3 = vm.segments.add();
4753        let tmp_segment = vm.add_temporary_segment();
4754        assert_eq!(segment0.segment_index, 0);
4755        assert_eq!(segment1.segment_index, 1);
4756        assert_eq!(segment2.segment_index, 2);
4757        assert_eq!(segment3.segment_index, 3);
4758        assert_eq!(tmp_segment.segment_index, -1);
4759        vm.segments.memory = memory![
4760            ((0, 1), 1),
4761            ((1, 0), 3),
4762            ((1, 1), 4),
4763            ((2, 0), 7),
4764            ((3, 0), 7),
4765            ((-1, 0), 5),
4766            ((-1, 1), 5),
4767            ((-1, 2), 5)
4768        ];
4769        vm.run_finished = true;
4770
4771        vm.mark_address_range_as_accessed((2, 0).into(), 1).unwrap();
4772
4773        let cell0 = Relocatable::from((0, 0));
4774        let cell1 = Relocatable::from((1, 1));
4775        let cell2 = Relocatable::from((2, 0));
4776        let cell3 = Relocatable::from((3, 7));
4777        let cell7 = Relocatable::from((7, 17));
4778        let cell_tmp = Relocatable::from((-1, 1));
4779        vm.delete_unaccessed(cell0).unwrap();
4780        vm.delete_unaccessed(cell1).unwrap();
4781        vm.delete_unaccessed(cell_tmp).unwrap();
4782
4783        // Check that the cells were set to NONE.
4784        assert!(vm
4785            .segments
4786            .memory
4787            .get_cell_for_testing(cell0)
4788            .unwrap()
4789            .is_none());
4790        assert!(vm
4791            .segments
4792            .memory
4793            .get_cell_for_testing(cell1)
4794            .unwrap()
4795            .is_none());
4796        assert!(vm
4797            .segments
4798            .memory
4799            .get_cell_for_testing(cell_tmp)
4800            .unwrap()
4801            .is_none());
4802        // Segment 3 cell was out of offset range, so it should not be modified or allocated.
4803        assert!(vm.segments.memory.get_cell_for_testing(cell3).is_none());
4804        // Segment 2 cell was accessed, so attempting to unset the memory should result in error.
4805        assert_matches!(
4806            vm.delete_unaccessed(cell2).unwrap_err(),
4807            MemoryError::UnsetAccessedCell(relocatable) if relocatable == cell2
4808        );
4809        // Segment 3 is unallocated, so attempting to unset the memory should result in error.
4810        assert_matches!(
4811            vm.delete_unaccessed(cell3).unwrap_err(),
4812            MemoryError::UnsetUnallocatedCell(relocatable) if relocatable == cell3
4813        );
4814        // Segment 7 was not allocated, so attempting to unset the memory should result in error.
4815        assert_matches!(
4816            vm.delete_unaccessed(cell7).unwrap_err(),
4817            MemoryError::UnallocatedSegment(boxed)
4818            if *boxed == (cell7.segment_index.try_into().unwrap(), vm.segments.memory.data.len())
4819        );
4820    }
4821
4822    #[test]
4823    fn mark_as_accessed() {
4824        let mut vm = vm!();
4825        vm.run_finished = true;
4826        vm.segments.memory = memory![
4827            ((0, 0), 0),
4828            ((0, 1), 0),
4829            ((0, 2), 1),
4830            ((0, 10), 10),
4831            ((1, 1), 1),
4832            ((1, 2), 0),
4833            ((2, 0), 0),
4834            ((-1, 0), 0),
4835            ((-1, 1), 0)
4836        ];
4837        vm.mark_address_range_as_accessed((0, 0).into(), 3).unwrap();
4838        vm.mark_address_range_as_accessed((0, 10).into(), 2)
4839            .unwrap();
4840        vm.mark_address_range_as_accessed((1, 1).into(), 1).unwrap();
4841        vm.mark_address_range_as_accessed((-1, 0).into(), 1)
4842            .unwrap();
4843        //Check that the following addresses have been accessed:
4844        // Addresses have been copied from python execution:
4845        let mem = &vm.segments.memory.data;
4846        assert!(mem[0][0].is_accessed());
4847        assert!(mem[0][1].is_accessed());
4848        assert!(mem[0][2].is_accessed());
4849        assert!(mem[0][10].is_accessed());
4850        assert!(mem[1][1].is_accessed());
4851        assert_eq!(
4852            vm.segments
4853                .memory
4854                .get_amount_of_accessed_addresses_for_segment(0),
4855            Some(4)
4856        );
4857        assert_eq!(
4858            vm.segments
4859                .memory
4860                .get_amount_of_accessed_addresses_for_segment(1),
4861            Some(1)
4862        );
4863        assert!(vm.is_accessed(&Relocatable::from((0, 0))).unwrap());
4864        assert!(vm.is_accessed(&Relocatable::from((0, 2))).unwrap());
4865        assert!(vm.is_accessed(&Relocatable::from((0, 10))).unwrap());
4866        assert!(vm.is_accessed(&Relocatable::from((1, 1))).unwrap());
4867        assert!(!vm.is_accessed(&Relocatable::from((1, 2))).unwrap());
4868        assert!(!vm.is_accessed(&Relocatable::from((2, 0))).unwrap());
4869        assert!(vm.is_accessed(&Relocatable::from((-1, 0))).unwrap());
4870        assert!(!vm.is_accessed(&Relocatable::from((-1, 1))).unwrap());
4871    }
4872
4873    #[test]
4874    fn mark_as_accessed_run_not_finished() {
4875        let mut vm = vm!();
4876        assert_matches!(
4877            vm.mark_address_range_as_accessed((0, 0).into(), 3),
4878            Err(VirtualMachineError::RunNotFinished)
4879        );
4880    }
4881
4882    #[test]
4883    fn mark_as_accessed_missing_accessed_addresses() {
4884        let mut vm = vm!();
4885        assert_matches!(
4886            vm.mark_address_range_as_accessed((0, 0).into(), 3),
4887            Err(VirtualMachineError::RunNotFinished)
4888        );
4889    }
4890
4891    #[test]
4892    fn get_u32_range_ok() {
4893        let mut vm = vm!();
4894        vm.segments.memory = memory![((0, 0), 0), ((0, 1), 1), ((0, 2), 4294967295), ((0, 3), 3)];
4895        let expected_vector = vec![1, 4294967295];
4896        assert_eq!(vm.get_u32_range((0, 1).into(), 2), Ok(expected_vector));
4897    }
4898
4899    #[test]
4900    fn get_u32_range_relocatable() {
4901        let mut vm = vm!();
4902        vm.segments.memory = memory![((0, 0), 0), ((0, 1), 1), ((0, 2), (0, 0)), ((0, 3), 3)];
4903        assert_matches!(vm.get_u32_range((0, 1).into(), 2), Err(MemoryError::ExpectedInteger(bx)) if *bx == (0, 2).into());
4904    }
4905
4906    #[test]
4907    fn get_u32_range_over_32_bits() {
4908        let mut vm = vm!();
4909        vm.segments.memory = memory![((0, 0), 0), ((0, 1), 1), ((0, 2), 4294967296), ((0, 3), 3)];
4910        assert_matches!(vm.get_u32_range((0, 1).into(), 2), Err(MemoryError::Math(MathError::Felt252ToU32Conversion(bx))) if *bx == Felt252::from(4294967296_u64));
4911    }
4912
4913    #[test]
4914    fn get_u32_range_memory_gap() {
4915        let mut vm = vm!();
4916        vm.segments.memory = memory![((0, 0), 0), ((0, 1), 1), ((0, 3), 3)];
4917        assert_matches!(vm.get_u32_range((0, 1).into(), 3), Err(MemoryError::UnknownMemoryCell(bx)) if *bx == (0, 2).into());
4918    }
4919
4920    #[test]
4921    fn handle_blake2s_instruction_state_too_short() {
4922        let mut vm = vm!();
4923        vm.segments.memory = memory![
4924            ((0, 0), 0),
4925            ((0, 1), 0),
4926            ((0, 2), 0),
4927            ((0, 3), 0),
4928            ((0, 4), 0),
4929            ((0, 5), 0),
4930            ((0, 6), 0),
4931            ((2, 0), (0, 0))
4932        ];
4933        let operands_addresses = OperandsAddresses {
4934            dst_addr: (0, 0).into(),
4935            op0_addr: (2, 0).into(),
4936            op1_addr: (2, 0).into(),
4937        };
4938        vm.run_context = RunContext {
4939            pc: (0, 0).into(),
4940            ap: 0,
4941            fp: 0,
4942        };
4943
4944        assert_matches!(
4945            vm.handle_blake2s_instruction(&operands_addresses, false),
4946            Err(VirtualMachineError::Memory(MemoryError::UnknownMemoryCell(bx))) if *bx == (0, 7).into()
4947        );
4948    }
4949
4950    #[test]
4951    fn handle_blake2s_instruction_message_too_short() {
4952        let mut vm = vm!();
4953        vm.segments.memory = memory![
4954            ((0, 0), 0),
4955            ((0, 1), 0),
4956            ((0, 2), 0),
4957            ((0, 3), 0),
4958            ((0, 4), 0),
4959            ((0, 5), 0),
4960            ((0, 6), 0),
4961            ((0, 7), 0),
4962            ((2, 0), (0, 0))
4963        ];
4964        let operands_addresses = OperandsAddresses {
4965            dst_addr: (0, 0).into(),
4966            op0_addr: (2, 0).into(),
4967            op1_addr: (2, 0).into(),
4968        };
4969        vm.run_context = RunContext {
4970            pc: (0, 0).into(),
4971            ap: 0,
4972            fp: 0,
4973        };
4974
4975        assert_matches!(
4976            vm.handle_blake2s_instruction(&operands_addresses, false),
4977            Err(VirtualMachineError::Memory(MemoryError::UnknownMemoryCell(bx))) if *bx == (0, 8).into()
4978        );
4979    }
4980
4981    #[test]
4982    fn handle_blake2s_instruction_ap_points_to_inconsistent_memory() {
4983        let mut vm = vm!();
4984        vm.segments.memory = memory![
4985            ((0, 0), 0),
4986            ((0, 1), 0),
4987            ((0, 2), 0),
4988            ((0, 3), 0),
4989            ((0, 4), 0),
4990            ((0, 5), 0),
4991            ((0, 6), 0),
4992            ((0, 7), 0),
4993            ((0, 8), 0),
4994            ((0, 9), 0),
4995            ((0, 10), 0),
4996            ((0, 11), 0),
4997            ((0, 12), 0),
4998            ((0, 13), 0),
4999            ((0, 14), 0),
5000            ((0, 15), 0),
5001            ((1, 0), (0, 0))
5002        ];
5003        let operands_addresses = OperandsAddresses {
5004            dst_addr: (0, 0).into(),
5005            op0_addr: (1, 0).into(),
5006            op1_addr: (1, 0).into(),
5007        };
5008        vm.run_context = RunContext {
5009            pc: (0, 0).into(),
5010            ap: 0,
5011            fp: 0,
5012        };
5013
5014        assert_matches!(
5015            vm.handle_blake2s_instruction(&operands_addresses, false),
5016            Err(VirtualMachineError::Memory(MemoryError::InconsistentMemory(bx))) if *bx == ((0, 0).into(),0.into(),1848029226.into())
5017        );
5018    }
5019
5020    #[test]
5021    fn handle_blake2s_instruction_ok() {
5022        let mut vm = vm!();
5023        vm.segments.memory = memory![
5024            // State
5025            ((0, 0), 0x6B08E647),
5026            ((0, 1), 0xBB67AE85),
5027            ((0, 2), 0x3C6EF372),
5028            ((0, 3), 0xA54FF53A),
5029            ((0, 4), 0x510E527F),
5030            ((0, 5), 0x9B05688C),
5031            ((0, 6), 0x1F83D9AB),
5032            ((0, 7), 0x5BE0CD19),
5033            // Message
5034            ((0, 8), 930933030),
5035            ((0, 9), 1766240503),
5036            ((0, 10), 3660871006),
5037            ((0, 11), 388409270),
5038            ((0, 12), 1948594622),
5039            ((0, 13), 3119396969),
5040            ((0, 14), 3924579183),
5041            ((0, 15), 2089920034),
5042            ((0, 16), 3857888532),
5043            ((0, 17), 929304360),
5044            ((0, 18), 1810891574),
5045            ((0, 19), 860971754),
5046            ((0, 20), 1822893775),
5047            ((0, 21), 2008495810),
5048            ((0, 22), 2958962335),
5049            ((0, 23), 2340515744),
5050            // Counter
5051            ((0, 24), 64),
5052            // AP
5053            ((1, 0), (0, 25)),
5054            ((2, 0), (0, 0)),
5055            ((2, 1), (0, 8))
5056        ];
5057        let operands_addresses = OperandsAddresses {
5058            dst_addr: (0, 24).into(),
5059            op0_addr: (2, 0).into(),
5060            op1_addr: (2, 1).into(),
5061        };
5062        vm.run_context = RunContext {
5063            pc: (0, 0).into(),
5064            ap: 0,
5065            fp: 0,
5066        };
5067        assert_matches!(
5068            vm.handle_blake2s_instruction(&operands_addresses, false),
5069            Ok(())
5070        );
5071
5072        let state: [u32; 8] = vm
5073            .get_u32_range((0, 0).into(), 8)
5074            .unwrap()
5075            .try_into()
5076            .unwrap();
5077        let message: [u32; 16] = vm
5078            .get_u32_range((0, 8).into(), 16)
5079            .unwrap()
5080            .try_into()
5081            .unwrap();
5082        let counter = vm.segments.memory.get_u32((0, 24).into()).unwrap();
5083
5084        let expected_new_state: [u32; 8] = blake2s_compress(&state, &message, counter, 0, 0, 0)
5085            .try_into()
5086            .unwrap();
5087
5088        let new_state: [u32; 8] = vm
5089            .get_u32_range((0, 25).into(), 8)
5090            .unwrap()
5091            .try_into()
5092            .unwrap();
5093        assert_eq!(new_state, expected_new_state);
5094    }
5095
5096    #[test]
5097    fn handle_blake2s_last_block_instruction_ok() {
5098        let mut vm = vm!();
5099        vm.segments.memory = memory![
5100            // State
5101            ((0, 0), 0x6B08E647),
5102            ((0, 1), 0xBB67AE85),
5103            ((0, 2), 0x3C6EF372),
5104            ((0, 3), 0xA54FF53A),
5105            ((0, 4), 0x510E527F),
5106            ((0, 5), 0x9B05688C),
5107            ((0, 6), 0x1F83D9AB),
5108            ((0, 7), 0x5BE0CD19),
5109            // Message
5110            ((0, 8), 930933030),
5111            ((0, 9), 1766240503),
5112            ((0, 10), 3660871006),
5113            ((0, 11), 388409270),
5114            ((0, 12), 1948594622),
5115            ((0, 13), 3119396969),
5116            ((0, 14), 3924579183),
5117            ((0, 15), 2089920034),
5118            ((0, 16), 3857888532),
5119            ((0, 17), 929304360),
5120            ((0, 18), 1810891574),
5121            ((0, 19), 860971754),
5122            ((0, 20), 1822893775),
5123            ((0, 21), 2008495810),
5124            ((0, 22), 2958962335),
5125            ((0, 23), 2340515744),
5126            // Counter
5127            ((0, 24), 64),
5128            // AP
5129            ((1, 0), (0, 25)),
5130            ((2, 0), (0, 0)),
5131            ((2, 1), (0, 8))
5132        ];
5133        let operands_addresses = OperandsAddresses {
5134            dst_addr: (0, 24).into(),
5135            op0_addr: (2, 0).into(),
5136            op1_addr: (2, 1).into(),
5137        };
5138        vm.run_context = RunContext {
5139            pc: (0, 0).into(),
5140            ap: 0,
5141            fp: 0,
5142        };
5143        assert_matches!(
5144            vm.handle_blake2s_instruction(&operands_addresses, true),
5145            Ok(())
5146        );
5147
5148        let state: [u32; 8] = vm
5149            .get_u32_range((0, 0).into(), 8)
5150            .unwrap()
5151            .try_into()
5152            .unwrap();
5153        let message: [u32; 16] = vm
5154            .get_u32_range((0, 8).into(), 16)
5155            .unwrap()
5156            .try_into()
5157            .unwrap();
5158        let counter = vm.segments.memory.get_u32((0, 24).into()).unwrap();
5159
5160        let expected_new_state: [u32; 8] =
5161            blake2s_compress(&state, &message, counter, 0, 0xffffffff, 0)
5162                .try_into()
5163                .unwrap();
5164
5165        let new_state: [u32; 8] = vm
5166            .get_u32_range((0, 25).into(), 8)
5167            .unwrap()
5168            .try_into()
5169            .unwrap();
5170        assert_eq!(new_state, expected_new_state);
5171    }
5172
5173    #[test]
5174    fn get_traceback_entries_bad_usort() {
5175        let program = Program::from_bytes(
5176            include_bytes!("../../../cairo_programs/bad_programs/bad_usort.json"),
5177            Some("main"),
5178        )
5179        .unwrap();
5180
5181        let mut hint_processor = BuiltinHintProcessor::new_empty();
5182        let mut cairo_runner = cairo_runner!(program, LayoutName::all_cairo, false);
5183
5184        let end = cairo_runner.initialize(false).unwrap();
5185        assert!(cairo_runner.run_until_pc(end, &mut hint_processor).is_err());
5186        let expected_traceback = vec![
5187            (Relocatable::from((1, 3)), Relocatable::from((0, 97))),
5188            (Relocatable::from((1, 14)), Relocatable::from((0, 30))),
5189            (Relocatable::from((1, 26)), Relocatable::from((0, 60))),
5190        ];
5191        assert_eq!(cairo_runner.vm.get_traceback_entries(), expected_traceback);
5192    }
5193
5194    #[test]
5195    fn get_traceback_entries_bad_dict_update() {
5196        let program = Program::from_bytes(
5197            include_bytes!("../../../cairo_programs/bad_programs/bad_dict_update.json"),
5198            Some("main"),
5199        )
5200        .unwrap();
5201
5202        let mut hint_processor = BuiltinHintProcessor::new_empty();
5203        let mut cairo_runner = cairo_runner!(program, LayoutName::all_cairo, false);
5204
5205        let end = cairo_runner.initialize(false).unwrap();
5206        assert!(cairo_runner.run_until_pc(end, &mut hint_processor).is_err());
5207        let expected_traceback = vec![(Relocatable::from((1, 2)), Relocatable::from((0, 34)))];
5208        assert_eq!(cairo_runner.vm.get_traceback_entries(), expected_traceback);
5209    }
5210
5211    #[test]
5212    fn builder_test() {
5213        let virtual_machine_builder: VirtualMachineBuilder = VirtualMachineBuilder::default()
5214            .run_finished(true)
5215            .current_step(12)
5216            .builtin_runners(vec![BuiltinRunner::from(HashBuiltinRunner::new(
5217                Some(12),
5218                true,
5219            ))])
5220            .run_context(RunContext {
5221                pc: Relocatable::from((0, 0)),
5222                ap: 18,
5223                fp: 0,
5224            })
5225            .segments({
5226                let mut segments = MemorySegmentManager::new();
5227                segments.segment_used_sizes = Some(vec![1]);
5228                segments
5229            })
5230            .skip_instruction_execution(true)
5231            .trace(Some(vec![TraceEntry {
5232                pc: (0, 1).into(),
5233                ap: 1,
5234                fp: 1,
5235            }]));
5236
5237        #[cfg(feature = "test_utils")]
5238        fn before_first_step_hook(
5239            _vm: &mut VirtualMachine,
5240            _hint_data: &[Box<dyn Any>],
5241        ) -> Result<(), VirtualMachineError> {
5242            Err(VirtualMachineError::Unexpected)
5243        }
5244        #[cfg(feature = "test_utils")]
5245        let virtual_machine_builder =
5246            virtual_machine_builder.hooks(Box::new(crate::vm::hooks::Hooks::new(
5247                Some(std::sync::Arc::new(before_first_step_hook)),
5248                None,
5249                None,
5250            )));
5251
5252        #[allow(unused_mut)]
5253        let mut virtual_machine_from_builder = virtual_machine_builder.build();
5254
5255        assert!(virtual_machine_from_builder.run_finished);
5256        assert_eq!(virtual_machine_from_builder.get_current_step(), 12);
5257        assert_eq!(
5258            virtual_machine_from_builder
5259                .builtin_runners
5260                .first()
5261                .unwrap()
5262                .name(),
5263            BuiltinName::pedersen
5264        );
5265        assert_eq!(virtual_machine_from_builder.run_context.ap, 18,);
5266        assert_eq!(
5267            virtual_machine_from_builder.segments.segment_used_sizes,
5268            Some(vec![1])
5269        );
5270        assert!(virtual_machine_from_builder.skip_instruction_execution,);
5271        assert_eq!(
5272            virtual_machine_from_builder.trace,
5273            Some(vec![TraceEntry {
5274                pc: (0, 1).into(),
5275                ap: 1,
5276                fp: 1,
5277            }])
5278        );
5279        #[cfg(feature = "test_utils")]
5280        {
5281            let program = crate::types::program::Program::from_bytes(
5282                include_bytes!("../../../cairo_programs/sqrt.json"),
5283                Some("main"),
5284            )
5285            .expect("Call to `Program::from_file()` failed.");
5286            let mut hint_processor = BuiltinHintProcessor::new_empty();
5287            let mut cairo_runner = cairo_runner!(program);
5288            cairo_runner.vm = virtual_machine_from_builder;
5289            let end = cairo_runner.initialize(false).unwrap();
5290
5291            assert!(cairo_runner.run_until_pc(end, &mut hint_processor).is_err());
5292        }
5293    }
5294
5295    #[test]
5296    /// Test for a simple program execution
5297    /// Used program code:
5298    /// func main():
5299    ///     let a = 1
5300    ///     let b = 2
5301    ///     let c = a + b
5302    ///     return()
5303    /// end
5304    /// Memory taken from original vm
5305    /// {RelocatableValue(segment_index=0, offset=0): 2345108766317314046,
5306    ///  RelocatableValue(segment_index=1, offset=0): RelocatableValue(segment_index=2, offset=0),
5307    ///  RelocatableValue(segment_index=1, offset=1): RelocatableValue(segment_index=3, offset=0)}
5308    /// Current register values:
5309    /// AP 1:2
5310    /// FP 1:2
5311    /// PC 0:0
5312    fn test_step_for_preset_memory_program_loaded_into_user_segment() {
5313        let mut vm = vm!(true);
5314
5315        let mut hint_processor = BuiltinHintProcessor::new_empty();
5316
5317        run_context!(vm, 0, 2, 2);
5318
5319        vm.segments = segments![
5320            ((2, 0), 2345108766317314046_u64), // Load program into new segment
5321            ((1, 0), (2, 0)),
5322            ((1, 1), (3, 0))
5323        ];
5324        // set starting pc on new segemt to run loaded program
5325        vm.run_context.pc.segment_index = 2;
5326
5327        assert_matches!(
5328            vm.step(
5329                &mut hint_processor,
5330                exec_scopes_ref!(),
5331                &mut Vec::new(),
5332                #[cfg(feature = "extensive_hints")]
5333                &mut HashMap::new(),
5334                #[cfg(feature = "test_utils")]
5335                &HashMap::new()
5336            ),
5337            Ok(())
5338        );
5339        let trace = vm.trace.unwrap();
5340        trace_check(&trace, &[((2, 0).into(), 2, 2)]);
5341
5342        assert_eq!(vm.run_context.pc, Relocatable::from((3, 0)));
5343        assert_eq!(vm.run_context.ap, 2);
5344        assert_eq!(vm.run_context.fp, 0);
5345
5346        //Check that the following addresses have been accessed:
5347        // Addresses have been copied from python execution:
5348        let mem = vm.segments.memory.data;
5349        assert!(mem[1][0].is_accessed());
5350        assert!(mem[1][1].is_accessed());
5351    }
5352
5353    #[test]
5354    /*
5355    Test for a simple program execution
5356    Used program code:
5357        func myfunc(a: felt) -> (r: felt):
5358            let b = a * 2
5359            return(b)
5360        end
5361        func main():
5362            let a = 1
5363            let b = myfunc(a)
5364            return()
5365        end
5366    Memory taken from original vm:
5367    {RelocatableValue(segment_index=0, offset=0): 5207990763031199744,
5368    RelocatableValue(segment_index=0, offset=1): 2,
5369    RelocatableValue(segment_index=0, offset=2): 2345108766317314046,
5370    RelocatableValue(segment_index=0, offset=3): 5189976364521848832,
5371    RelocatableValue(segment_index=0, offset=4): 1,
5372    RelocatableValue(segment_index=0, offset=5): 1226245742482522112,
5373    RelocatableValue(segment_index=0, offset=6): 3618502788666131213697322783095070105623107215331596699973092056135872020476,
5374    RelocatableValue(segment_index=0, offset=7): 2345108766317314046,
5375    RelocatableValue(segment_index=1, offset=0): RelocatableValue(segment_index=2, offset=0),
5376    RelocatableValue(segment_index=1, offset=1): RelocatableValue(segment_index=3, offset=0)}
5377    Current register values:
5378    AP 1:2
5379    FP 1:2
5380    PC 0:3
5381    Final Pc (not executed): 3:0
5382    This program consists of 5 steps
5383    */
5384    fn test_step_for_preset_memory_function_call_program_loaded_into_user_segment() {
5385        let mut vm = vm!(true);
5386
5387        run_context!(vm, 3, 2, 2);
5388        // set starting pc on new segemt to run loaded program
5389        vm.run_context.pc.segment_index = 4;
5390
5391        //Insert values into memory
5392        vm.segments.memory =
5393            memory![
5394            // Load program into new segment
5395            ((4, 0), 5207990763031199744_i64),
5396            ((4, 1), 2),
5397            ((4, 2), 2345108766317314046_i64),
5398            ((4, 3), 5189976364521848832_i64),
5399            ((4, 4), 1),
5400            ((4, 5), 1226245742482522112_i64),
5401            (
5402                (4, 6),
5403                ("3618502788666131213697322783095070105623107215331596699973092056135872020476",10)
5404            ),
5405            ((4, 7), 2345108766317314046_i64),
5406            ((1, 0), (2, 0)),
5407            ((1, 1), (3, 0))
5408        ];
5409
5410        let final_pc = Relocatable::from((3, 0));
5411        let mut hint_processor = BuiltinHintProcessor::new_empty();
5412        //Run steps
5413        while vm.run_context.pc != final_pc {
5414            assert_matches!(
5415                vm.step(
5416                    &mut hint_processor,
5417                    exec_scopes_ref!(),
5418                    &mut Vec::new(),
5419                    #[cfg(feature = "extensive_hints")]
5420                    &mut HashMap::new(),
5421                    #[cfg(feature = "test_utils")]
5422                    &HashMap::new()
5423                ),
5424                Ok(())
5425            );
5426        }
5427
5428        //Check final register values
5429        assert_eq!(vm.run_context.pc, Relocatable::from((3, 0)));
5430
5431        assert_eq!(vm.run_context.ap, 6);
5432
5433        assert_eq!(vm.run_context.fp, 0);
5434        //Check each TraceEntry in trace
5435        let trace = vm.trace.unwrap();
5436        assert_eq!(trace.len(), 5);
5437        trace_check(
5438            &trace,
5439            &[
5440                ((4, 3).into(), 2, 2),
5441                ((4, 5).into(), 3, 2),
5442                ((4, 0).into(), 5, 5),
5443                ((4, 2).into(), 6, 5),
5444                ((4, 7).into(), 6, 2),
5445            ],
5446        );
5447        //Check that the following addresses have been accessed:
5448        // Addresses have been copied from python execution + addresses of accessed code:
5449        let mem = &vm.segments.memory.data;
5450        assert!(mem[4][0].is_accessed());
5451        assert!(mem[4][1].is_accessed());
5452        assert!(mem[4][2].is_accessed());
5453        assert!(mem[4][3].is_accessed());
5454        assert!(mem[4][4].is_accessed());
5455        assert!(mem[4][5].is_accessed());
5456        assert!(mem[4][6].is_accessed());
5457        assert!(mem[4][7].is_accessed());
5458        assert!(mem[1][0].is_accessed());
5459        assert!(mem[1][1].is_accessed());
5460        assert!(mem[1][2].is_accessed());
5461        assert!(mem[1][3].is_accessed());
5462        assert!(mem[1][4].is_accessed());
5463        assert!(mem[1][5].is_accessed());
5464        assert_eq!(
5465            vm.segments
5466                .memory
5467                .get_amount_of_accessed_addresses_for_segment(4),
5468            Some(8)
5469        );
5470        assert_eq!(
5471            vm.segments
5472                .memory
5473                .get_amount_of_accessed_addresses_for_segment(1),
5474            Some(6)
5475        );
5476    }
5477
5478    #[test]
5479    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
5480    fn test_extended_execution_resources() {
5481        let result = ExtendedExecutionResourceType::try_from(OpcodeExtension::Stone);
5482
5483        assert_eq!(
5484            result,
5485            Err("Unsupported OpcodeExtension for ExtendedExecutionResourceType")
5486        );
5487    }
5488}
cairo_vm/vm/vm_core.rs

cairo_vm/vm/
vm_core.rs
