cairo_vm/vm/
vm_core.rs

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

cairo_vm/vm/
vm_core.rs
