cairo_vm/types/
program.rs

1use crate::{
2    serde::{
3        deserialize_program::{parse_program_json, ProgramJson},
4        serialize_program::ProgramSerializer,
5    },
6    stdlib::{
7        collections::{BTreeMap, HashMap},
8        prelude::*,
9        sync::Arc,
10    },
11    vm::runners::cairo_pie::StrippedProgram,
12};
13
14#[cfg(feature = "cairo-1-hints")]
15use crate::serde::deserialize_program::{ApTracking, FlowTrackingData};
16use crate::utils::PRIME_STR;
17use crate::Felt252;
18use crate::{
19    hint_processor::hint_processor_definition::HintReference,
20    serde::deserialize_program::{
21        deserialize_and_parse_program, Attribute, HintParams, Identifier, InstructionLocation,
22        OffsetValue, ReferenceManager,
23    },
24    types::{
25        errors::program_errors::ProgramError, instruction::Register, relocatable::MaybeRelocatable,
26    },
27};
28#[cfg(feature = "cairo-1-hints")]
29use cairo_lang_starknet_classes::casm_contract_class::CasmContractClass;
30use core::num::NonZeroUsize;
31
32#[cfg(feature = "std")]
33use std::path::Path;
34
35use super::builtin_name::BuiltinName;
36#[cfg(feature = "extensive_hints")]
37use super::relocatable::Relocatable;
38#[cfg(feature = "test_utils")]
39use arbitrary::{Arbitrary, Unstructured};
40
41// NOTE: `Program` has been split in two containing some data that will be deep-copied
42// and some that will be allocated on the heap inside an `Arc<_>`.
43// This is because it has been reported that cloning the whole structure when creating
44// a `CairoRunner` becomes a bottleneck, but the following solutions were tried and
45// discarded:
46// - Store only a reference in `CairoRunner` rather than cloning; this doesn't work
47//   because then we need to introduce explicit lifetimes, which broke `cairo-vm-py`
48//   since PyO3 doesn't support Python objects containing structures with lifetimes.
49// - Directly pass an `Arc<Program>` to `CairoRunner::new()` and simply copy that:
50//   there was a prohibitive performance hit of 10-15% when doing so, most likely
51//   either because of branch mispredictions or the extra level of indirection going
52//   through a random location on the heap rather than the likely-to-be-cached spot
53//   on the stack.
54//
55// So, the compromise was to identify which data was less used and avoid copying that,
56// using `Arc<_>`, while the most accessed fields remain on the stack for the main
57// loop to access. The fields in `SharedProgramData` are either preprocessed and
58// copied explicitly (_in addition_ to the clone of `Program`) or are used only in
59// exceptional circumstances, such as when reconstructing a backtrace on execution
60// failures.
61// Fields in `Program` (other than `SharedProgramData` itself) are used by the main logic.
62#[derive(Clone, Default, Debug, PartialEq, Eq)]
63pub struct SharedProgramData {
64    pub(crate) data: Vec<MaybeRelocatable>,
65    pub hints_collection: HintsCollection,
66    pub(crate) main: Option<usize>,
67    //start and end labels will only be used in proof-mode
68    pub(crate) start: Option<usize>,
69    pub(crate) end: Option<usize>,
70    pub(crate) error_message_attributes: Vec<Attribute>,
71    pub(crate) instruction_locations: Option<HashMap<usize, InstructionLocation>>,
72    pub(crate) identifiers: HashMap<String, Identifier>,
73    pub reference_manager: Vec<HintReference>,
74}
75
76#[cfg(feature = "test_utils")]
77impl<'a> Arbitrary<'a> for SharedProgramData {
78    /// Create an arbitary [`SharedProgramData`] using `HintsCollection::new` to generate `hints` and
79    /// `hints_ranges`
80    fn arbitrary(u: &mut Unstructured<'a>) -> arbitrary::Result<Self> {
81        let mut data = Vec::new();
82        let len = usize::arbitrary(u)?;
83        for i in 0..len {
84            let instruction = u64::arbitrary(u)?;
85            data.push(MaybeRelocatable::from(Felt252::from(instruction)));
86            // Check if the Imm flag is on and add an immediate value if it is
87            if instruction & 0x0004000000000000 != 0 && i < len - 1 {
88                data.push(MaybeRelocatable::from(Felt252::arbitrary(u)?));
89            }
90        }
91
92        let raw_hints = BTreeMap::<usize, Vec<HintParams>>::arbitrary(u)?;
93        let hints_collection = HintsCollection::new(&raw_hints, data.len())
94            .map_err(|_| arbitrary::Error::IncorrectFormat)?;
95        Ok(SharedProgramData {
96            data,
97            hints_collection,
98            main: Option::<usize>::arbitrary(u)?,
99            start: Option::<usize>::arbitrary(u)?,
100            end: Option::<usize>::arbitrary(u)?,
101            error_message_attributes: Vec::<Attribute>::arbitrary(u)?,
102            instruction_locations: Option::<HashMap<usize, InstructionLocation>>::arbitrary(u)?,
103            identifiers: HashMap::<String, Identifier>::arbitrary(u)?,
104            reference_manager: Vec::<HintReference>::arbitrary(u)?,
105        })
106    }
107}
108
109#[derive(Clone, Default, Debug, PartialEq, Eq)]
110pub struct HintsCollection {
111    pub hints: Vec<HintParams>,
112    /// This maps a PC to the range of hints in `hints` that correspond to it.
113    #[cfg(not(feature = "extensive_hints"))]
114    pub(crate) hints_ranges: Vec<HintRange>,
115    #[cfg(feature = "extensive_hints")]
116    pub hints_ranges: HashMap<Relocatable, HintRange>,
117}
118
119impl HintsCollection {
120    pub(crate) fn new(
121        hints: &BTreeMap<usize, Vec<HintParams>>,
122        program_length: usize,
123    ) -> Result<Self, ProgramError> {
124        let bounds = hints
125            .iter()
126            .map(|(pc, hs)| (*pc, hs.len()))
127            .reduce(|(max_hint_pc, full_len), (pc, len)| (max_hint_pc.max(pc), full_len + len));
128
129        let Some((max_hint_pc, full_len)) = bounds else {
130            return Ok(HintsCollection {
131                hints: Vec::new(),
132                hints_ranges: Default::default(),
133            });
134        };
135
136        if max_hint_pc >= program_length {
137            return Err(ProgramError::InvalidHintPc(max_hint_pc, program_length));
138        }
139
140        let mut hints_values = Vec::with_capacity(full_len);
141        #[cfg(not(feature = "extensive_hints"))]
142        let mut hints_ranges = vec![None; max_hint_pc + 1];
143        #[cfg(feature = "extensive_hints")]
144        let mut hints_ranges = HashMap::default();
145        for (pc, hs) in hints.iter().filter(|(_, hs)| !hs.is_empty()) {
146            let range = (
147                hints_values.len(),
148                NonZeroUsize::new(hs.len()).expect("empty vecs already filtered"),
149            );
150            #[cfg(not(feature = "extensive_hints"))]
151            {
152                hints_ranges[*pc] = Some(range);
153            }
154            #[cfg(feature = "extensive_hints")]
155            hints_ranges.insert(Relocatable::from((0_isize, *pc)), range);
156            hints_values.extend_from_slice(&hs[..]);
157        }
158
159        Ok(HintsCollection {
160            hints: hints_values,
161            hints_ranges,
162        })
163    }
164
165    pub fn iter_hints(&self) -> impl Iterator<Item = &HintParams> {
166        self.hints.iter()
167    }
168
169    #[cfg(not(feature = "extensive_hints"))]
170    pub fn get_hint_range_for_pc(&self, pc: usize) -> Option<HintRange> {
171        self.hints_ranges.get(pc).cloned()
172    }
173}
174
175impl From<&HintsCollection> for BTreeMap<usize, Vec<HintParams>> {
176    fn from(hc: &HintsCollection) -> Self {
177        let mut hint_map = BTreeMap::new();
178        #[cfg(not(feature = "extensive_hints"))]
179        for (i, r) in hc.hints_ranges.iter().enumerate() {
180            let Some(r) = r else {
181                continue;
182            };
183            hint_map.insert(i, hc.hints[r.0..r.0 + r.1.get()].to_owned());
184        }
185        #[cfg(feature = "extensive_hints")]
186        for (pc, r) in hc.hints_ranges.iter() {
187            hint_map.insert(pc.offset, hc.hints[r.0..r.0 + r.1.get()].to_owned());
188        }
189        hint_map
190    }
191}
192
193/// Represents a range of hints corresponding to a PC as a  tuple `(start, length)`.
194#[cfg(not(feature = "extensive_hints"))]
195/// Is [`None`] if the range is empty, and it is [`Some`] tuple `(start, length)` otherwise.
196type HintRange = Option<(usize, NonZeroUsize)>;
197#[cfg(feature = "extensive_hints")]
198pub type HintRange = (usize, NonZeroUsize);
199
200#[cfg_attr(feature = "test_utils", derive(Arbitrary))]
201#[derive(Clone, Debug, PartialEq, Eq)]
202pub struct Program {
203    pub shared_program_data: Arc<SharedProgramData>,
204    pub constants: Arc<HashMap<String, Felt252>>,
205    pub(crate) builtins: Vec<BuiltinName>,
206}
207
208impl Program {
209    #[allow(clippy::too_many_arguments)]
210    pub fn new(
211        builtins: Vec<BuiltinName>,
212        data: Vec<MaybeRelocatable>,
213        main: Option<usize>,
214        hints: HashMap<usize, Vec<HintParams>>,
215        reference_manager: ReferenceManager,
216        identifiers: HashMap<String, Identifier>,
217        error_message_attributes: Vec<Attribute>,
218        instruction_locations: Option<HashMap<usize, InstructionLocation>>,
219    ) -> Result<Program, ProgramError> {
220        let constants = Self::extract_constants(&identifiers)?;
221
222        let hints: BTreeMap<_, _> = hints.into_iter().collect();
223        let hints_collection = HintsCollection::new(&hints, data.len())?;
224
225        let shared_program_data = SharedProgramData {
226            data,
227            main,
228            start: None,
229            end: None,
230            hints_collection,
231            error_message_attributes,
232            instruction_locations,
233            identifiers,
234            reference_manager: Self::get_reference_list(&reference_manager),
235        };
236        Ok(Self {
237            shared_program_data: Arc::new(shared_program_data),
238            constants: Arc::new(constants),
239            builtins,
240        })
241    }
242    #[allow(clippy::too_many_arguments)]
243    pub fn new_for_proof(
244        builtins: Vec<BuiltinName>,
245        data: Vec<MaybeRelocatable>,
246        start: usize,
247        end: usize,
248        hints: HashMap<usize, Vec<HintParams>>,
249        reference_manager: ReferenceManager,
250        identifiers: HashMap<String, Identifier>,
251        error_message_attributes: Vec<Attribute>,
252        instruction_locations: Option<HashMap<usize, InstructionLocation>>,
253    ) -> Result<Program, ProgramError> {
254        let constants = Self::extract_constants(&identifiers)?;
255
256        let hints: BTreeMap<_, _> = hints.into_iter().collect();
257        let hints_collection = HintsCollection::new(&hints, data.len())?;
258
259        let shared_program_data = SharedProgramData {
260            data,
261            main: None,
262            start: Some(start),
263            end: Some(end),
264            hints_collection,
265            error_message_attributes,
266            instruction_locations,
267            identifiers,
268            reference_manager: Self::get_reference_list(&reference_manager),
269        };
270        Ok(Self {
271            shared_program_data: Arc::new(shared_program_data),
272            constants: Arc::new(constants),
273            builtins,
274        })
275    }
276
277    #[cfg(feature = "std")]
278    pub fn from_file(path: &Path, entrypoint: Option<&str>) -> Result<Program, ProgramError> {
279        let file_content = std::fs::read(path)?;
280        deserialize_and_parse_program(&file_content, entrypoint)
281    }
282
283    pub fn from_bytes(bytes: &[u8], entrypoint: Option<&str>) -> Result<Program, ProgramError> {
284        deserialize_and_parse_program(bytes, entrypoint)
285    }
286
287    pub fn prime(&self) -> &str {
288        _ = self;
289        PRIME_STR
290    }
291
292    pub fn iter_builtins(&self) -> impl Iterator<Item = &BuiltinName> {
293        self.builtins.iter()
294    }
295
296    pub fn iter_data(&self) -> impl Iterator<Item = &MaybeRelocatable> {
297        self.shared_program_data.data.iter()
298    }
299
300    pub fn data_len(&self) -> usize {
301        self.shared_program_data.data.len()
302    }
303
304    pub fn builtins_len(&self) -> usize {
305        self.builtins.len()
306    }
307
308    pub fn get_identifier(&self, id: &str) -> Option<&Identifier> {
309        self.shared_program_data.identifiers.get(id)
310    }
311
312    pub fn get_relocated_instruction_locations(
313        &self,
314        relocation_table: &[usize],
315    ) -> Option<HashMap<usize, InstructionLocation>> {
316        self.shared_program_data.instruction_locations.as_ref()?;
317        let relocated_instructions = self
318            .shared_program_data
319            .instruction_locations
320            .as_ref()
321            .unwrap()
322            .iter()
323            .map(|(k, v)| (k + relocation_table[0], v.clone()))
324            .collect();
325        Some(relocated_instructions)
326    }
327
328    pub fn iter_identifiers(&self) -> impl Iterator<Item = (&str, &Identifier)> {
329        self.shared_program_data
330            .identifiers
331            .iter()
332            .map(|(cairo_type, identifier)| (cairo_type.as_str(), identifier))
333    }
334
335    pub(crate) fn get_reference_list(reference_manager: &ReferenceManager) -> Vec<HintReference> {
336        reference_manager
337            .references
338            .iter()
339            .map(|r| {
340                HintReference {
341                    offset1: r.value_address.offset1.clone(),
342                    offset2: r.value_address.offset2.clone(),
343                    outer_dereference: r.value_address.outer_dereference,
344                    inner_dereference: r.value_address.inner_dereference,
345                    // only store `ap` tracking data if the reference is referred to it
346                    ap_tracking_data: match (&r.value_address.offset1, &r.value_address.offset2) {
347                        (OffsetValue::Reference(Register::AP, _, _, _), _)
348                        | (_, OffsetValue::Reference(Register::AP, _, _, _)) => {
349                            Some(r.ap_tracking_data.clone())
350                        }
351                        _ => None,
352                    },
353                    cairo_type: Some(r.value_address.value_type.clone()),
354                }
355            })
356            .collect()
357    }
358
359    pub(crate) fn extract_constants(
360        identifiers: &HashMap<String, Identifier>,
361    ) -> Result<HashMap<String, Felt252>, ProgramError> {
362        let mut constants = HashMap::new();
363        for (key, value) in identifiers.iter() {
364            if value.type_.as_deref() == Some("const") {
365                let value = value
366                    .value
367                    .ok_or_else(|| ProgramError::ConstWithoutValue(key.clone()))?;
368                constants.insert(key.clone(), value);
369            }
370        }
371        Ok(constants)
372    }
373
374    // Obtains a reduced version of the program
375    // Doesn't contain hints
376    // Can be used for verifying execution.
377    pub fn get_stripped_program(&self) -> Result<StrippedProgram, ProgramError> {
378        Ok(StrippedProgram {
379            data: self.shared_program_data.data.clone(),
380            builtins: self.builtins.clone(),
381            main: self
382                .shared_program_data
383                .main
384                .ok_or(ProgramError::StrippedProgramNoMain)?,
385            prime: (),
386        })
387    }
388
389    pub fn from_stripped_program(stripped: &StrippedProgram) -> Program {
390        Program {
391            shared_program_data: Arc::new(SharedProgramData {
392                data: stripped.data.clone(),
393                main: Some(stripped.main),
394                ..Default::default()
395            }),
396            constants: Default::default(),
397            builtins: stripped.builtins.clone(),
398        }
399    }
400
401    pub fn serialize(&self) -> Result<Vec<u8>, ProgramError> {
402        let program_serializer: ProgramSerializer = ProgramSerializer::from(self);
403        let bytes: Vec<u8> = serde_json::to_vec(&program_serializer)?;
404        Ok(bytes)
405    }
406
407    pub fn deserialize(
408        program_serializer_bytes: &[u8],
409        entrypoint: Option<&str>,
410    ) -> Result<Program, ProgramError> {
411        let program_serializer: ProgramSerializer =
412            serde_json::from_slice(program_serializer_bytes)?;
413        let program_json = ProgramJson::from(program_serializer);
414        let program = parse_program_json(program_json, entrypoint)?;
415        Ok(program)
416    }
417}
418
419impl Default for Program {
420    fn default() -> Self {
421        Self {
422            shared_program_data: Arc::new(SharedProgramData::default()),
423            constants: Arc::new(HashMap::new()),
424            builtins: Vec::new(),
425        }
426    }
427}
428
429#[cfg(feature = "cairo-1-hints")]
430// Note: This Program will only work when using run_from_entrypoint, and the Cairo1Hintprocesso
431impl TryFrom<CasmContractClass> for Program {
432    type Error = ProgramError;
433    fn try_from(value: CasmContractClass) -> Result<Self, ProgramError> {
434        let data = value
435            .bytecode
436            .iter()
437            .map(|x| MaybeRelocatable::from(Felt252::from(&x.value)))
438            .collect();
439        //Hint data is going to be hosted processor-side, hints field will only store the pc where hints are located.
440        // Only one pc will be stored, so the hint processor will be responsible for executing all hints for a given pc
441        let hints = value
442            .hints
443            .iter()
444            .map(|(x, _)| {
445                (
446                    *x,
447                    vec![HintParams {
448                        code: x.to_string(),
449                        accessible_scopes: Vec::new(),
450                        flow_tracking_data: FlowTrackingData {
451                            ap_tracking: ApTracking::default(),
452                            reference_ids: HashMap::new(),
453                        },
454                    }],
455                )
456            })
457            .collect();
458        let error_message_attributes = Vec::new();
459        let reference_manager = ReferenceManager {
460            references: Vec::new(),
461        };
462        Self::new(
463            vec![],
464            data,
465            None,
466            hints,
467            reference_manager,
468            HashMap::new(),
469            error_message_attributes,
470            None,
471        )
472    }
473}
474
475#[cfg(test)]
476impl HintsCollection {
477    pub fn iter(&self) -> impl Iterator<Item = (usize, &[HintParams])> {
478        #[cfg(not(feature = "extensive_hints"))]
479        let iter = self
480            .hints_ranges
481            .iter()
482            .enumerate()
483            .filter_map(|(pc, range)| {
484                range.and_then(|(start, len)| {
485                    let end = start + len.get();
486                    if end <= self.hints.len() {
487                        Some((pc, &self.hints[start..end]))
488                    } else {
489                        None
490                    }
491                })
492            });
493        #[cfg(feature = "extensive_hints")]
494        let iter = self.hints_ranges.iter().filter_map(|(pc, (start, len))| {
495            let end = start + len.get();
496            if end <= self.hints.len() {
497                Some((pc.offset, &self.hints[*start..end]))
498            } else {
499                None
500            }
501        });
502        iter
503    }
504}
505
506#[cfg(test)]
507mod tests {
508    use core::ops::Neg;
509
510    use super::*;
511    use crate::felt_hex;
512    use crate::serde::deserialize_program::{ApTracking, FlowTrackingData, InputFile, Location};
513    use crate::utils::test_utils::*;
514
515    use assert_matches::assert_matches;
516
517    #[cfg(target_arch = "wasm32")]
518    use wasm_bindgen_test::*;
519
520    #[test]
521    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
522    fn new() {
523        let reference_manager = ReferenceManager {
524            references: Vec::new(),
525        };
526
527        let builtins: Vec<BuiltinName> = Vec::new();
528        let data: Vec<MaybeRelocatable> = vec![
529            mayberelocatable!(5189976364521848832),
530            mayberelocatable!(1000),
531            mayberelocatable!(5189976364521848832),
532            mayberelocatable!(2000),
533            mayberelocatable!(5201798304953696256),
534            mayberelocatable!(2345108766317314046),
535        ];
536
537        let program = Program::new(
538            builtins.clone(),
539            data.clone(),
540            None,
541            HashMap::new(),
542            reference_manager,
543            HashMap::new(),
544            Vec::new(),
545            None,
546        )
547        .unwrap();
548
549        assert_eq!(program.builtins, builtins);
550        assert_eq!(program.shared_program_data.data, data);
551        assert_eq!(program.shared_program_data.main, None);
552        assert_eq!(program.shared_program_data.identifiers, HashMap::new());
553        assert_eq!(
554            program.shared_program_data.hints_collection.hints,
555            Vec::new()
556        );
557        assert!(program
558            .shared_program_data
559            .hints_collection
560            .hints_ranges
561            .is_empty());
562    }
563
564    #[test]
565    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
566    fn new_for_proof() {
567        let reference_manager = ReferenceManager {
568            references: Vec::new(),
569        };
570
571        let builtins: Vec<BuiltinName> = Vec::new();
572        let data: Vec<MaybeRelocatable> = vec![
573            mayberelocatable!(5189976364521848832),
574            mayberelocatable!(1000),
575            mayberelocatable!(5189976364521848832),
576            mayberelocatable!(2000),
577            mayberelocatable!(5201798304953696256),
578            mayberelocatable!(2345108766317314046),
579        ];
580
581        let program = Program::new_for_proof(
582            builtins.clone(),
583            data.clone(),
584            0,
585            1,
586            HashMap::new(),
587            reference_manager,
588            HashMap::new(),
589            Vec::new(),
590            None,
591        )
592        .unwrap();
593
594        assert_eq!(program.builtins, builtins);
595        assert_eq!(program.shared_program_data.data, data);
596        assert_eq!(program.shared_program_data.main, None);
597        assert_eq!(program.shared_program_data.start, Some(0));
598        assert_eq!(program.shared_program_data.end, Some(1));
599        assert_eq!(program.shared_program_data.identifiers, HashMap::new());
600        assert_eq!(
601            program.shared_program_data.hints_collection.hints,
602            Vec::new()
603        );
604        assert!(program
605            .shared_program_data
606            .hints_collection
607            .hints_ranges
608            .is_empty());
609    }
610
611    #[test]
612    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
613    fn new_program_with_hints() {
614        let reference_manager = ReferenceManager {
615            references: Vec::new(),
616        };
617
618        let builtins: Vec<BuiltinName> = Vec::new();
619        let data: Vec<MaybeRelocatable> = vec![
620            mayberelocatable!(5189976364521848832),
621            mayberelocatable!(1000),
622            mayberelocatable!(5189976364521848832),
623            mayberelocatable!(2000),
624            mayberelocatable!(5201798304953696256),
625            mayberelocatable!(2345108766317314046),
626        ];
627
628        let str_to_hint_param = |s: &str| HintParams {
629            code: s.to_string(),
630            accessible_scopes: vec![],
631            flow_tracking_data: FlowTrackingData {
632                ap_tracking: ApTracking {
633                    group: 0,
634                    offset: 0,
635                },
636                reference_ids: HashMap::new(),
637            },
638        };
639
640        let hints = HashMap::from([
641            (5, vec![str_to_hint_param("c"), str_to_hint_param("d")]),
642            (1, vec![str_to_hint_param("a")]),
643            (4, vec![str_to_hint_param("b")]),
644        ]);
645
646        let program = Program::new(
647            builtins.clone(),
648            data.clone(),
649            None,
650            hints.clone(),
651            reference_manager,
652            HashMap::new(),
653            Vec::new(),
654            None,
655        )
656        .unwrap();
657
658        assert_eq!(program.builtins, builtins);
659        assert_eq!(program.shared_program_data.data, data);
660        assert_eq!(program.shared_program_data.main, None);
661        assert_eq!(program.shared_program_data.identifiers, HashMap::new());
662
663        #[cfg(not(feature = "extensive_hints"))]
664        let program_hints: HashMap<_, _> = program
665            .shared_program_data
666            .hints_collection
667            .hints_ranges
668            .iter()
669            .enumerate()
670            .filter_map(|(pc, r)| r.map(|(s, l)| (pc, (s, s + l.get()))))
671            .map(|(pc, (s, e))| {
672                (
673                    pc,
674                    program.shared_program_data.hints_collection.hints[s..e].to_vec(),
675                )
676            })
677            .collect();
678        #[cfg(feature = "extensive_hints")]
679        let program_hints: HashMap<_, _> = program
680            .shared_program_data
681            .hints_collection
682            .hints_ranges
683            .iter()
684            .map(|(pc, (s, l))| {
685                (
686                    pc.offset,
687                    program.shared_program_data.hints_collection.hints[*s..(s + l.get())].to_vec(),
688                )
689            })
690            .collect();
691        assert_eq!(program_hints, hints);
692    }
693
694    #[test]
695    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
696    fn new_program_with_identifiers() {
697        let reference_manager = ReferenceManager {
698            references: Vec::new(),
699        };
700
701        let builtins: Vec<BuiltinName> = Vec::new();
702
703        let data: Vec<MaybeRelocatable> = vec![
704            mayberelocatable!(5189976364521848832),
705            mayberelocatable!(1000),
706            mayberelocatable!(5189976364521848832),
707            mayberelocatable!(2000),
708            mayberelocatable!(5201798304953696256),
709            mayberelocatable!(2345108766317314046),
710        ];
711
712        let mut identifiers: HashMap<String, Identifier> = HashMap::new();
713
714        identifiers.insert(
715            String::from("__main__.main"),
716            Identifier {
717                pc: Some(0),
718                type_: Some(String::from("function")),
719                value: None,
720                full_name: None,
721                members: None,
722                cairo_type: None,
723                size: None,
724                destination: None,
725            },
726        );
727
728        identifiers.insert(
729            String::from("__main__.main.SIZEOF_LOCALS"),
730            Identifier {
731                pc: None,
732                type_: Some(String::from("const")),
733                value: Some(Felt252::ZERO),
734                full_name: None,
735                members: None,
736                cairo_type: None,
737                size: None,
738                destination: None,
739            },
740        );
741
742        let program = Program::new(
743            builtins.clone(),
744            data.clone(),
745            None,
746            HashMap::new(),
747            reference_manager,
748            identifiers.clone(),
749            Vec::new(),
750            None,
751        )
752        .unwrap();
753
754        assert_eq!(program.builtins, builtins);
755        assert_eq!(program.shared_program_data.data, data);
756        assert_eq!(program.shared_program_data.main, None);
757        assert_eq!(program.shared_program_data.identifiers, identifiers);
758        assert_eq!(
759            program.constants,
760            [("__main__.main.SIZEOF_LOCALS", Felt252::ZERO)]
761                .into_iter()
762                .map(|(key, value)| (key.to_string(), value))
763                .collect::<HashMap<_, _>>()
764                .into(),
765        );
766    }
767
768    #[test]
769    fn extract_constants() {
770        let mut identifiers: HashMap<String, Identifier> = HashMap::new();
771
772        identifiers.insert(
773            String::from("__main__.main"),
774            Identifier {
775                pc: Some(0),
776                type_: Some(String::from("function")),
777                value: None,
778                full_name: None,
779                members: None,
780                cairo_type: None,
781                size: None,
782                destination: None,
783            },
784        );
785
786        identifiers.insert(
787            String::from("__main__.main.SIZEOF_LOCALS"),
788            Identifier {
789                pc: None,
790                type_: Some(String::from("const")),
791                value: Some(Felt252::ZERO),
792                full_name: None,
793                members: None,
794                cairo_type: None,
795                size: None,
796                destination: None,
797            },
798        );
799
800        assert_eq!(
801            Program::extract_constants(&identifiers).unwrap(),
802            [("__main__.main.SIZEOF_LOCALS", Felt252::ZERO)]
803                .into_iter()
804                .map(|(key, value)| (key.to_string(), value))
805                .collect::<HashMap<_, _>>(),
806        );
807    }
808
809    #[test]
810    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
811    fn get_prime() {
812        let program = Program::default();
813        assert_eq!(PRIME_STR, program.prime());
814    }
815
816    #[test]
817    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
818    fn iter_builtins() {
819        let reference_manager = ReferenceManager {
820            references: Vec::new(),
821        };
822
823        let builtins: Vec<_> = vec![BuiltinName::range_check, BuiltinName::bitwise];
824        let data: Vec<_> = vec![
825            mayberelocatable!(5189976364521848832),
826            mayberelocatable!(1000),
827            mayberelocatable!(5189976364521848832),
828            mayberelocatable!(2000),
829            mayberelocatable!(5201798304953696256),
830            mayberelocatable!(2345108766317314046),
831        ];
832
833        let program = Program::new(
834            builtins.clone(),
835            data,
836            None,
837            HashMap::new(),
838            reference_manager,
839            HashMap::new(),
840            Vec::new(),
841            None,
842        )
843        .unwrap();
844
845        assert_eq!(
846            program.iter_builtins().cloned().collect::<Vec<_>>(),
847            builtins
848        );
849
850        assert_eq!(program.builtins_len(), 2);
851    }
852
853    #[test]
854    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
855    fn iter_data() {
856        let reference_manager = ReferenceManager {
857            references: Vec::new(),
858        };
859
860        let builtins: Vec<BuiltinName> = Vec::new();
861        let data: Vec<MaybeRelocatable> = vec![
862            mayberelocatable!(5189976364521848832),
863            mayberelocatable!(1000),
864            mayberelocatable!(5189976364521848832),
865            mayberelocatable!(2000),
866            mayberelocatable!(5201798304953696256),
867            mayberelocatable!(2345108766317314046),
868        ];
869
870        let program = Program::new(
871            builtins,
872            data.clone(),
873            None,
874            HashMap::new(),
875            reference_manager,
876            HashMap::new(),
877            Vec::new(),
878            None,
879        )
880        .unwrap();
881
882        assert_eq!(program.iter_data().cloned().collect::<Vec<_>>(), data);
883    }
884
885    #[test]
886    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
887    fn data_len() {
888        let reference_manager = ReferenceManager {
889            references: Vec::new(),
890        };
891
892        let builtins: Vec<BuiltinName> = Vec::new();
893        let data: Vec<MaybeRelocatable> = vec![
894            mayberelocatable!(5189976364521848832),
895            mayberelocatable!(1000),
896            mayberelocatable!(5189976364521848832),
897            mayberelocatable!(2000),
898            mayberelocatable!(5201798304953696256),
899            mayberelocatable!(2345108766317314046),
900        ];
901
902        let program = Program::new(
903            builtins,
904            data.clone(),
905            None,
906            HashMap::new(),
907            reference_manager,
908            HashMap::new(),
909            Vec::new(),
910            None,
911        )
912        .unwrap();
913
914        assert_eq!(program.data_len(), data.len());
915    }
916
917    #[test]
918    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
919    fn get_identifier() {
920        let reference_manager = ReferenceManager {
921            references: Vec::new(),
922        };
923
924        let builtins: Vec<BuiltinName> = Vec::new();
925
926        let data: Vec<MaybeRelocatable> = vec![
927            mayberelocatable!(5189976364521848832),
928            mayberelocatable!(1000),
929            mayberelocatable!(5189976364521848832),
930            mayberelocatable!(2000),
931            mayberelocatable!(5201798304953696256),
932            mayberelocatable!(2345108766317314046),
933        ];
934
935        let mut identifiers: HashMap<String, Identifier> = HashMap::new();
936
937        identifiers.insert(
938            String::from("__main__.main"),
939            Identifier {
940                pc: Some(0),
941                type_: Some(String::from("function")),
942                value: None,
943                full_name: None,
944                members: None,
945                cairo_type: None,
946                size: None,
947                destination: None,
948            },
949        );
950
951        identifiers.insert(
952            String::from("__main__.main.SIZEOF_LOCALS"),
953            Identifier {
954                pc: None,
955                type_: Some(String::from("const")),
956                value: Some(Felt252::ZERO),
957                full_name: None,
958                members: None,
959                cairo_type: None,
960                size: None,
961                destination: None,
962            },
963        );
964
965        let program = Program::new(
966            builtins,
967            data,
968            None,
969            HashMap::new(),
970            reference_manager,
971            identifiers.clone(),
972            Vec::new(),
973            None,
974        )
975        .unwrap();
976
977        assert_eq!(
978            program.get_identifier("__main__.main"),
979            identifiers.get("__main__.main"),
980        );
981        assert_eq!(
982            program.get_identifier("__main__.main.SIZEOF_LOCALS"),
983            identifiers.get("__main__.main.SIZEOF_LOCALS"),
984        );
985        assert_eq!(
986            program.get_identifier("missing"),
987            identifiers.get("missing"),
988        );
989    }
990
991    #[test]
992    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
993    fn get_relocated_instruction_locations() {
994        fn build_instruction_location_for_test(start_line: u32) -> InstructionLocation {
995            InstructionLocation {
996                inst: Location {
997                    end_line: 0,
998                    end_col: 0,
999                    input_file: InputFile {
1000                        filename: String::from("test"),
1001                    },
1002                    parent_location: None,
1003                    start_line,
1004                    start_col: 0,
1005                },
1006                hints: vec![],
1007            }
1008        }
1009
1010        let reference_manager = ReferenceManager {
1011            references: Vec::new(),
1012        };
1013        let builtins: Vec<BuiltinName> = Vec::new();
1014        let data: Vec<MaybeRelocatable> = vec![];
1015        let identifiers: HashMap<String, Identifier> = HashMap::new();
1016        let mut instruction_locations: HashMap<usize, InstructionLocation> = HashMap::new();
1017
1018        let il_1 = build_instruction_location_for_test(0);
1019        let il_2 = build_instruction_location_for_test(2);
1020        let il_3 = build_instruction_location_for_test(3);
1021        instruction_locations.insert(5, il_1.clone());
1022        instruction_locations.insert(10, il_2.clone());
1023        instruction_locations.insert(12, il_3.clone());
1024
1025        let program = Program::new(
1026            builtins,
1027            data,
1028            None,
1029            HashMap::new(),
1030            reference_manager,
1031            identifiers,
1032            Vec::new(),
1033            Some(instruction_locations),
1034        )
1035        .unwrap();
1036
1037        let relocated_instructions = program.get_relocated_instruction_locations(&[2]);
1038        assert!(relocated_instructions.is_some());
1039        let relocated_instructions = relocated_instructions.unwrap();
1040        assert_eq!(relocated_instructions.len(), 3);
1041        assert_eq!(relocated_instructions.get(&7), Some(&il_1));
1042        assert_eq!(relocated_instructions.get(&12), Some(&il_2));
1043        assert_eq!(relocated_instructions.get(&14), Some(&il_3));
1044    }
1045
1046    #[test]
1047    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1048    fn iter_identifiers() {
1049        let reference_manager = ReferenceManager {
1050            references: Vec::new(),
1051        };
1052
1053        let builtins: Vec<BuiltinName> = Vec::new();
1054
1055        let data: Vec<MaybeRelocatable> = vec![
1056            mayberelocatable!(5189976364521848832),
1057            mayberelocatable!(1000),
1058            mayberelocatable!(5189976364521848832),
1059            mayberelocatable!(2000),
1060            mayberelocatable!(5201798304953696256),
1061            mayberelocatable!(2345108766317314046),
1062        ];
1063
1064        let mut identifiers: HashMap<String, Identifier> = HashMap::new();
1065
1066        identifiers.insert(
1067            String::from("__main__.main"),
1068            Identifier {
1069                pc: Some(0),
1070                type_: Some(String::from("function")),
1071                value: None,
1072                full_name: None,
1073                members: None,
1074                cairo_type: None,
1075                size: None,
1076                destination: None,
1077            },
1078        );
1079
1080        identifiers.insert(
1081            String::from("__main__.main.SIZEOF_LOCALS"),
1082            Identifier {
1083                pc: None,
1084                type_: Some(String::from("const")),
1085                value: Some(Felt252::ZERO),
1086                full_name: None,
1087                members: None,
1088                cairo_type: None,
1089                size: None,
1090                destination: None,
1091            },
1092        );
1093
1094        let program = Program::new(
1095            builtins,
1096            data,
1097            None,
1098            HashMap::new(),
1099            reference_manager,
1100            identifiers.clone(),
1101            Vec::new(),
1102            None,
1103        )
1104        .unwrap();
1105
1106        let collected_identifiers: HashMap<_, _> = program
1107            .iter_identifiers()
1108            .map(|(cairo_type, identifier)| (cairo_type.to_string(), identifier.clone()))
1109            .collect();
1110
1111        assert_eq!(collected_identifiers, identifiers);
1112    }
1113
1114    #[test]
1115    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1116    fn new_program_with_invalid_identifiers() {
1117        let reference_manager = ReferenceManager {
1118            references: Vec::new(),
1119        };
1120
1121        let builtins: Vec<BuiltinName> = Vec::new();
1122
1123        let data: Vec<MaybeRelocatable> = vec![
1124            mayberelocatable!(5189976364521848832),
1125            mayberelocatable!(1000),
1126            mayberelocatable!(5189976364521848832),
1127            mayberelocatable!(2000),
1128            mayberelocatable!(5201798304953696256),
1129            mayberelocatable!(2345108766317314046),
1130        ];
1131
1132        let mut identifiers: HashMap<String, Identifier> = HashMap::new();
1133
1134        identifiers.insert(
1135            String::from("__main__.main"),
1136            Identifier {
1137                pc: Some(0),
1138                type_: Some(String::from("function")),
1139                value: None,
1140                full_name: None,
1141                members: None,
1142                cairo_type: None,
1143                size: None,
1144                destination: None,
1145            },
1146        );
1147
1148        identifiers.insert(
1149            String::from("__main__.main.SIZEOF_LOCALS"),
1150            Identifier {
1151                pc: None,
1152                type_: Some(String::from("const")),
1153                value: None,
1154                full_name: None,
1155                members: None,
1156                cairo_type: None,
1157                size: None,
1158                destination: None,
1159            },
1160        );
1161
1162        let program = Program::new(
1163            builtins,
1164            data,
1165            None,
1166            HashMap::new(),
1167            reference_manager,
1168            identifiers.clone(),
1169            Vec::new(),
1170            None,
1171        );
1172
1173        assert!(program.is_err());
1174    }
1175
1176    #[test]
1177    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1178    fn deserialize_program_test() {
1179        let program = Program::from_bytes(
1180            include_bytes!("../../../cairo_programs/manually_compiled/valid_program_a.json"),
1181            Some("main"),
1182        )
1183        .unwrap();
1184
1185        let builtins: Vec<BuiltinName> = Vec::new();
1186        let data: Vec<MaybeRelocatable> = vec![
1187            mayberelocatable!(5189976364521848832),
1188            mayberelocatable!(1000),
1189            mayberelocatable!(5189976364521848832),
1190            mayberelocatable!(2000),
1191            mayberelocatable!(5201798304953696256),
1192            mayberelocatable!(2345108766317314046),
1193        ];
1194
1195        let mut identifiers: HashMap<String, Identifier> = HashMap::new();
1196
1197        identifiers.insert(
1198            String::from("__main__.main"),
1199            Identifier {
1200                pc: Some(0),
1201                type_: Some(String::from("function")),
1202                value: None,
1203                full_name: None,
1204                members: None,
1205                cairo_type: None,
1206                size: None,
1207                destination: None,
1208            },
1209        );
1210        identifiers.insert(
1211            String::from("__main__.main.Args"),
1212            Identifier {
1213                pc: None,
1214                type_: Some(String::from("struct")),
1215                value: None,
1216                full_name: Some("__main__.main.Args".to_string()),
1217                members: Some(HashMap::new()),
1218                cairo_type: None,
1219                size: Some(0),
1220                destination: None,
1221            },
1222        );
1223        identifiers.insert(
1224            String::from("__main__.main.ImplicitArgs"),
1225            Identifier {
1226                pc: None,
1227                type_: Some(String::from("struct")),
1228                value: None,
1229                full_name: Some("__main__.main.ImplicitArgs".to_string()),
1230                members: Some(HashMap::new()),
1231                cairo_type: None,
1232                size: Some(0),
1233                destination: None,
1234            },
1235        );
1236        identifiers.insert(
1237            String::from("__main__.main.Return"),
1238            Identifier {
1239                pc: None,
1240                type_: Some(String::from("struct")),
1241                value: None,
1242                full_name: Some("__main__.main.Return".to_string()),
1243                members: Some(HashMap::new()),
1244                cairo_type: None,
1245                size: Some(0),
1246                destination: None,
1247            },
1248        );
1249        identifiers.insert(
1250            String::from("__main__.main.SIZEOF_LOCALS"),
1251            Identifier {
1252                pc: None,
1253                type_: Some(String::from("const")),
1254                value: Some(Felt252::ZERO),
1255                full_name: None,
1256                members: None,
1257                cairo_type: None,
1258                size: None,
1259                destination: None,
1260            },
1261        );
1262
1263        assert_eq!(program.builtins, builtins);
1264        assert_eq!(program.shared_program_data.data, data);
1265        assert_eq!(program.shared_program_data.main, Some(0));
1266        assert_eq!(program.shared_program_data.identifiers, identifiers);
1267    }
1268
1269    /// Deserialize a program without an entrypoint.
1270    #[test]
1271    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1272    fn deserialize_program_without_entrypoint_test() {
1273        let program = Program::from_bytes(
1274            include_bytes!("../../../cairo_programs/manually_compiled/valid_program_a.json"),
1275            None,
1276        )
1277        .unwrap();
1278
1279        let builtins: Vec<BuiltinName> = Vec::new();
1280
1281        let error_message_attributes: Vec<Attribute> = vec![Attribute {
1282            name: String::from("error_message"),
1283            start_pc: 379,
1284            end_pc: 381,
1285            value: String::from("SafeUint256: addition overflow"),
1286            flow_tracking_data: Some(FlowTrackingData {
1287                ap_tracking: ApTracking {
1288                    group: 14,
1289                    offset: 35,
1290                },
1291                reference_ids: HashMap::new(),
1292            }),
1293        }];
1294
1295        let data: Vec<MaybeRelocatable> = vec![
1296            mayberelocatable!(5189976364521848832),
1297            mayberelocatable!(1000),
1298            mayberelocatable!(5189976364521848832),
1299            mayberelocatable!(2000),
1300            mayberelocatable!(5201798304953696256),
1301            mayberelocatable!(2345108766317314046),
1302        ];
1303
1304        let mut identifiers: HashMap<String, Identifier> = HashMap::new();
1305
1306        identifiers.insert(
1307            String::from("__main__.main"),
1308            Identifier {
1309                pc: Some(0),
1310                type_: Some(String::from("function")),
1311                value: None,
1312                full_name: None,
1313                members: None,
1314                cairo_type: None,
1315                size: None,
1316                destination: None,
1317            },
1318        );
1319        identifiers.insert(
1320            String::from("__main__.main.Args"),
1321            Identifier {
1322                pc: None,
1323                type_: Some(String::from("struct")),
1324                value: None,
1325                full_name: Some("__main__.main.Args".to_string()),
1326                members: Some(HashMap::new()),
1327                cairo_type: None,
1328                size: Some(0),
1329                destination: None,
1330            },
1331        );
1332        identifiers.insert(
1333            String::from("__main__.main.ImplicitArgs"),
1334            Identifier {
1335                pc: None,
1336                type_: Some(String::from("struct")),
1337                value: None,
1338                full_name: Some("__main__.main.ImplicitArgs".to_string()),
1339                members: Some(HashMap::new()),
1340                cairo_type: None,
1341                size: Some(0),
1342                destination: None,
1343            },
1344        );
1345        identifiers.insert(
1346            String::from("__main__.main.Return"),
1347            Identifier {
1348                pc: None,
1349                type_: Some(String::from("struct")),
1350                value: None,
1351                full_name: Some("__main__.main.Return".to_string()),
1352                members: Some(HashMap::new()),
1353                cairo_type: None,
1354                size: Some(0),
1355                destination: None,
1356            },
1357        );
1358        identifiers.insert(
1359            String::from("__main__.main.SIZEOF_LOCALS"),
1360            Identifier {
1361                pc: None,
1362                type_: Some(String::from("const")),
1363                value: Some(Felt252::ZERO),
1364                full_name: None,
1365                members: None,
1366                cairo_type: None,
1367                size: None,
1368                destination: None,
1369            },
1370        );
1371
1372        assert_eq!(program.builtins, builtins);
1373        assert_eq!(program.shared_program_data.data, data);
1374        assert_eq!(program.shared_program_data.main, None);
1375        assert_eq!(program.shared_program_data.identifiers, identifiers);
1376        assert_eq!(
1377            program.shared_program_data.error_message_attributes,
1378            error_message_attributes
1379        )
1380    }
1381
1382    #[test]
1383    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1384    fn deserialize_program_constants_test() {
1385        let program = Program::from_bytes(
1386            include_bytes!(
1387                "../../../cairo_programs/manually_compiled/deserialize_constant_test.json"
1388            ),
1389            Some("main"),
1390        )
1391        .unwrap();
1392
1393        let constants = [
1394            ("__main__.compare_abs_arrays.SIZEOF_LOCALS", Felt252::ZERO),
1395            (
1396                "starkware.cairo.common.cairo_keccak.packed_keccak.ALL_ONES",
1397                felt_hex!("0x7ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"),
1398            ),
1399            (
1400                "starkware.cairo.common.cairo_keccak.packed_keccak.BLOCK_SIZE",
1401                Felt252::from(3),
1402            ),
1403            (
1404                "starkware.cairo.common.alloc.alloc.SIZEOF_LOCALS",
1405                felt_hex!("0x800000000000011000000000000000000000000000000000000000000000001")
1406                    .neg(),
1407            ),
1408            (
1409                "starkware.cairo.common.uint256.SHIFT",
1410                felt_hex!("0x100000000000000000000000000000000"),
1411            ),
1412        ]
1413        .into_iter()
1414        .map(|(key, value)| (key.to_string(), value))
1415        .collect::<HashMap<_, _>>();
1416
1417        assert_eq!(program.constants, constants.into());
1418    }
1419
1420    #[test]
1421    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1422    fn default_program() {
1423        let hints_collection = HintsCollection {
1424            hints: Vec::new(),
1425            hints_ranges: Default::default(),
1426        };
1427
1428        let shared_program_data = SharedProgramData {
1429            data: Vec::new(),
1430            hints_collection,
1431            main: None,
1432            start: None,
1433            end: None,
1434            error_message_attributes: Vec::new(),
1435            instruction_locations: None,
1436            identifiers: HashMap::new(),
1437            reference_manager: Program::get_reference_list(&ReferenceManager {
1438                references: Vec::new(),
1439            }),
1440        };
1441        let program = Program {
1442            shared_program_data: Arc::new(shared_program_data),
1443            constants: Arc::new(HashMap::new()),
1444            builtins: Vec::new(),
1445        };
1446
1447        assert_eq!(program, Program::default());
1448    }
1449
1450    #[test]
1451    fn get_stripped_program() {
1452        let program_content = include_bytes!("../../../cairo_programs/pedersen_test.json");
1453        let program = Program::from_bytes(program_content, Some("main")).unwrap();
1454        let stripped_program = program.get_stripped_program().unwrap();
1455        assert_eq!(stripped_program.builtins, program.builtins);
1456        assert_eq!(stripped_program.data, program.shared_program_data.data);
1457        assert_eq!(
1458            stripped_program.main,
1459            program.shared_program_data.main.unwrap()
1460        );
1461    }
1462
1463    #[test]
1464    fn get_stripped_no_main() {
1465        let program_content =
1466            include_bytes!("../../../cairo_programs/proof_programs/fibonacci.json");
1467        let program = Program::from_bytes(program_content, None).unwrap();
1468        assert_matches!(
1469            program.get_stripped_program(),
1470            Err(ProgramError::StrippedProgramNoMain)
1471        );
1472    }
1473}
cairo_vm/types/program.rs

cairo_vm/types/
program.rs
