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: 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,
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,
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: 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        );
765    }
766
767    #[test]
768    fn extract_constants() {
769        let mut identifiers: HashMap<String, Identifier> = HashMap::new();
770
771        identifiers.insert(
772            String::from("__main__.main"),
773            Identifier {
774                pc: Some(0),
775                type_: Some(String::from("function")),
776                value: None,
777                full_name: None,
778                members: None,
779                cairo_type: None,
780                size: None,
781                destination: None,
782            },
783        );
784
785        identifiers.insert(
786            String::from("__main__.main.SIZEOF_LOCALS"),
787            Identifier {
788                pc: None,
789                type_: Some(String::from("const")),
790                value: Some(Felt252::ZERO),
791                full_name: None,
792                members: None,
793                cairo_type: None,
794                size: None,
795                destination: None,
796            },
797        );
798
799        assert_eq!(
800            Program::extract_constants(&identifiers).unwrap(),
801            [("__main__.main.SIZEOF_LOCALS", Felt252::ZERO)]
802                .into_iter()
803                .map(|(key, value)| (key.to_string(), value))
804                .collect::<HashMap<_, _>>(),
805        );
806    }
807
808    #[test]
809    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
810    fn get_prime() {
811        let program = Program::default();
812        assert_eq!(PRIME_STR, program.prime());
813    }
814
815    #[test]
816    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
817    fn iter_builtins() {
818        let reference_manager = ReferenceManager {
819            references: Vec::new(),
820        };
821
822        let builtins: Vec<_> = vec![BuiltinName::range_check, BuiltinName::bitwise];
823        let data: Vec<_> = vec![
824            mayberelocatable!(5189976364521848832),
825            mayberelocatable!(1000),
826            mayberelocatable!(5189976364521848832),
827            mayberelocatable!(2000),
828            mayberelocatable!(5201798304953696256),
829            mayberelocatable!(2345108766317314046),
830        ];
831
832        let program = Program::new(
833            builtins.clone(),
834            data,
835            None,
836            HashMap::new(),
837            reference_manager,
838            HashMap::new(),
839            Vec::new(),
840            None,
841        )
842        .unwrap();
843
844        assert_eq!(
845            program.iter_builtins().cloned().collect::<Vec<_>>(),
846            builtins
847        );
848
849        assert_eq!(program.builtins_len(), 2);
850    }
851
852    #[test]
853    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
854    fn iter_data() {
855        let reference_manager = ReferenceManager {
856            references: Vec::new(),
857        };
858
859        let builtins: Vec<BuiltinName> = Vec::new();
860        let data: Vec<MaybeRelocatable> = vec![
861            mayberelocatable!(5189976364521848832),
862            mayberelocatable!(1000),
863            mayberelocatable!(5189976364521848832),
864            mayberelocatable!(2000),
865            mayberelocatable!(5201798304953696256),
866            mayberelocatable!(2345108766317314046),
867        ];
868
869        let program = Program::new(
870            builtins,
871            data.clone(),
872            None,
873            HashMap::new(),
874            reference_manager,
875            HashMap::new(),
876            Vec::new(),
877            None,
878        )
879        .unwrap();
880
881        assert_eq!(program.iter_data().cloned().collect::<Vec<_>>(), data);
882    }
883
884    #[test]
885    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
886    fn data_len() {
887        let reference_manager = ReferenceManager {
888            references: Vec::new(),
889        };
890
891        let builtins: Vec<BuiltinName> = Vec::new();
892        let data: Vec<MaybeRelocatable> = vec![
893            mayberelocatable!(5189976364521848832),
894            mayberelocatable!(1000),
895            mayberelocatable!(5189976364521848832),
896            mayberelocatable!(2000),
897            mayberelocatable!(5201798304953696256),
898            mayberelocatable!(2345108766317314046),
899        ];
900
901        let program = Program::new(
902            builtins,
903            data.clone(),
904            None,
905            HashMap::new(),
906            reference_manager,
907            HashMap::new(),
908            Vec::new(),
909            None,
910        )
911        .unwrap();
912
913        assert_eq!(program.data_len(), data.len());
914    }
915
916    #[test]
917    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
918    fn get_identifier() {
919        let reference_manager = ReferenceManager {
920            references: Vec::new(),
921        };
922
923        let builtins: Vec<BuiltinName> = Vec::new();
924
925        let data: Vec<MaybeRelocatable> = vec![
926            mayberelocatable!(5189976364521848832),
927            mayberelocatable!(1000),
928            mayberelocatable!(5189976364521848832),
929            mayberelocatable!(2000),
930            mayberelocatable!(5201798304953696256),
931            mayberelocatable!(2345108766317314046),
932        ];
933
934        let mut identifiers: HashMap<String, Identifier> = HashMap::new();
935
936        identifiers.insert(
937            String::from("__main__.main"),
938            Identifier {
939                pc: Some(0),
940                type_: Some(String::from("function")),
941                value: None,
942                full_name: None,
943                members: None,
944                cairo_type: None,
945                size: None,
946                destination: None,
947            },
948        );
949
950        identifiers.insert(
951            String::from("__main__.main.SIZEOF_LOCALS"),
952            Identifier {
953                pc: None,
954                type_: Some(String::from("const")),
955                value: Some(Felt252::ZERO),
956                full_name: None,
957                members: None,
958                cairo_type: None,
959                size: None,
960                destination: None,
961            },
962        );
963
964        let program = Program::new(
965            builtins,
966            data,
967            None,
968            HashMap::new(),
969            reference_manager,
970            identifiers.clone(),
971            Vec::new(),
972            None,
973        )
974        .unwrap();
975
976        assert_eq!(
977            program.get_identifier("__main__.main"),
978            identifiers.get("__main__.main"),
979        );
980        assert_eq!(
981            program.get_identifier("__main__.main.SIZEOF_LOCALS"),
982            identifiers.get("__main__.main.SIZEOF_LOCALS"),
983        );
984        assert_eq!(
985            program.get_identifier("missing"),
986            identifiers.get("missing"),
987        );
988    }
989
990    #[test]
991    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
992    fn get_relocated_instruction_locations() {
993        fn build_instruction_location_for_test(start_line: u32) -> InstructionLocation {
994            InstructionLocation {
995                inst: Location {
996                    end_line: 0,
997                    end_col: 0,
998                    input_file: InputFile {
999                        filename: String::from("test"),
1000                    },
1001                    parent_location: None,
1002                    start_line,
1003                    start_col: 0,
1004                },
1005                hints: vec![],
1006            }
1007        }
1008
1009        let reference_manager = ReferenceManager {
1010            references: Vec::new(),
1011        };
1012        let builtins: Vec<BuiltinName> = Vec::new();
1013        let data: Vec<MaybeRelocatable> = vec![];
1014        let identifiers: HashMap<String, Identifier> = HashMap::new();
1015        let mut instruction_locations: HashMap<usize, InstructionLocation> = HashMap::new();
1016
1017        let il_1 = build_instruction_location_for_test(0);
1018        let il_2 = build_instruction_location_for_test(2);
1019        let il_3 = build_instruction_location_for_test(3);
1020        instruction_locations.insert(5, il_1.clone());
1021        instruction_locations.insert(10, il_2.clone());
1022        instruction_locations.insert(12, il_3.clone());
1023
1024        let program = Program::new(
1025            builtins,
1026            data,
1027            None,
1028            HashMap::new(),
1029            reference_manager,
1030            identifiers,
1031            Vec::new(),
1032            Some(instruction_locations),
1033        )
1034        .unwrap();
1035
1036        let relocated_instructions = program.get_relocated_instruction_locations(&[2]);
1037        assert!(relocated_instructions.is_some());
1038        let relocated_instructions = relocated_instructions.unwrap();
1039        assert_eq!(relocated_instructions.len(), 3);
1040        assert_eq!(relocated_instructions.get(&7), Some(&il_1));
1041        assert_eq!(relocated_instructions.get(&12), Some(&il_2));
1042        assert_eq!(relocated_instructions.get(&14), Some(&il_3));
1043    }
1044
1045    #[test]
1046    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1047    fn iter_identifiers() {
1048        let reference_manager = ReferenceManager {
1049            references: Vec::new(),
1050        };
1051
1052        let builtins: Vec<BuiltinName> = Vec::new();
1053
1054        let data: Vec<MaybeRelocatable> = vec![
1055            mayberelocatable!(5189976364521848832),
1056            mayberelocatable!(1000),
1057            mayberelocatable!(5189976364521848832),
1058            mayberelocatable!(2000),
1059            mayberelocatable!(5201798304953696256),
1060            mayberelocatable!(2345108766317314046),
1061        ];
1062
1063        let mut identifiers: HashMap<String, Identifier> = HashMap::new();
1064
1065        identifiers.insert(
1066            String::from("__main__.main"),
1067            Identifier {
1068                pc: Some(0),
1069                type_: Some(String::from("function")),
1070                value: None,
1071                full_name: None,
1072                members: None,
1073                cairo_type: None,
1074                size: None,
1075                destination: None,
1076            },
1077        );
1078
1079        identifiers.insert(
1080            String::from("__main__.main.SIZEOF_LOCALS"),
1081            Identifier {
1082                pc: None,
1083                type_: Some(String::from("const")),
1084                value: Some(Felt252::ZERO),
1085                full_name: None,
1086                members: None,
1087                cairo_type: None,
1088                size: None,
1089                destination: None,
1090            },
1091        );
1092
1093        let program = Program::new(
1094            builtins,
1095            data,
1096            None,
1097            HashMap::new(),
1098            reference_manager,
1099            identifiers.clone(),
1100            Vec::new(),
1101            None,
1102        )
1103        .unwrap();
1104
1105        let collected_identifiers: HashMap<_, _> = program
1106            .iter_identifiers()
1107            .map(|(cairo_type, identifier)| (cairo_type.to_string(), identifier.clone()))
1108            .collect();
1109
1110        assert_eq!(collected_identifiers, identifiers);
1111    }
1112
1113    #[test]
1114    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1115    fn new_program_with_invalid_identifiers() {
1116        let reference_manager = ReferenceManager {
1117            references: Vec::new(),
1118        };
1119
1120        let builtins: Vec<BuiltinName> = Vec::new();
1121
1122        let data: Vec<MaybeRelocatable> = vec![
1123            mayberelocatable!(5189976364521848832),
1124            mayberelocatable!(1000),
1125            mayberelocatable!(5189976364521848832),
1126            mayberelocatable!(2000),
1127            mayberelocatable!(5201798304953696256),
1128            mayberelocatable!(2345108766317314046),
1129        ];
1130
1131        let mut identifiers: HashMap<String, Identifier> = HashMap::new();
1132
1133        identifiers.insert(
1134            String::from("__main__.main"),
1135            Identifier {
1136                pc: Some(0),
1137                type_: Some(String::from("function")),
1138                value: None,
1139                full_name: None,
1140                members: None,
1141                cairo_type: None,
1142                size: None,
1143                destination: None,
1144            },
1145        );
1146
1147        identifiers.insert(
1148            String::from("__main__.main.SIZEOF_LOCALS"),
1149            Identifier {
1150                pc: None,
1151                type_: Some(String::from("const")),
1152                value: None,
1153                full_name: None,
1154                members: None,
1155                cairo_type: None,
1156                size: None,
1157                destination: None,
1158            },
1159        );
1160
1161        let program = Program::new(
1162            builtins,
1163            data,
1164            None,
1165            HashMap::new(),
1166            reference_manager,
1167            identifiers.clone(),
1168            Vec::new(),
1169            None,
1170        );
1171
1172        assert!(program.is_err());
1173    }
1174
1175    #[test]
1176    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1177    fn deserialize_program_test() {
1178        let program = Program::from_bytes(
1179            include_bytes!("../../../cairo_programs/manually_compiled/valid_program_a.json"),
1180            Some("main"),
1181        )
1182        .unwrap();
1183
1184        let builtins: Vec<BuiltinName> = Vec::new();
1185        let data: Vec<MaybeRelocatable> = vec![
1186            mayberelocatable!(5189976364521848832),
1187            mayberelocatable!(1000),
1188            mayberelocatable!(5189976364521848832),
1189            mayberelocatable!(2000),
1190            mayberelocatable!(5201798304953696256),
1191            mayberelocatable!(2345108766317314046),
1192        ];
1193
1194        let mut identifiers: HashMap<String, Identifier> = HashMap::new();
1195
1196        identifiers.insert(
1197            String::from("__main__.main"),
1198            Identifier {
1199                pc: Some(0),
1200                type_: Some(String::from("function")),
1201                value: None,
1202                full_name: None,
1203                members: None,
1204                cairo_type: None,
1205                size: None,
1206                destination: None,
1207            },
1208        );
1209        identifiers.insert(
1210            String::from("__main__.main.Args"),
1211            Identifier {
1212                pc: None,
1213                type_: Some(String::from("struct")),
1214                value: None,
1215                full_name: Some("__main__.main.Args".to_string()),
1216                members: Some(HashMap::new()),
1217                cairo_type: None,
1218                size: Some(0),
1219                destination: None,
1220            },
1221        );
1222        identifiers.insert(
1223            String::from("__main__.main.ImplicitArgs"),
1224            Identifier {
1225                pc: None,
1226                type_: Some(String::from("struct")),
1227                value: None,
1228                full_name: Some("__main__.main.ImplicitArgs".to_string()),
1229                members: Some(HashMap::new()),
1230                cairo_type: None,
1231                size: Some(0),
1232                destination: None,
1233            },
1234        );
1235        identifiers.insert(
1236            String::from("__main__.main.Return"),
1237            Identifier {
1238                pc: None,
1239                type_: Some(String::from("struct")),
1240                value: None,
1241                full_name: Some("__main__.main.Return".to_string()),
1242                members: Some(HashMap::new()),
1243                cairo_type: None,
1244                size: Some(0),
1245                destination: None,
1246            },
1247        );
1248        identifiers.insert(
1249            String::from("__main__.main.SIZEOF_LOCALS"),
1250            Identifier {
1251                pc: None,
1252                type_: Some(String::from("const")),
1253                value: Some(Felt252::ZERO),
1254                full_name: None,
1255                members: None,
1256                cairo_type: None,
1257                size: None,
1258                destination: None,
1259            },
1260        );
1261
1262        assert_eq!(program.builtins, builtins);
1263        assert_eq!(program.shared_program_data.data, data);
1264        assert_eq!(program.shared_program_data.main, Some(0));
1265        assert_eq!(program.shared_program_data.identifiers, identifiers);
1266    }
1267
1268    /// Deserialize a program without an entrypoint.
1269    #[test]
1270    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1271    fn deserialize_program_without_entrypoint_test() {
1272        let program = Program::from_bytes(
1273            include_bytes!("../../../cairo_programs/manually_compiled/valid_program_a.json"),
1274            None,
1275        )
1276        .unwrap();
1277
1278        let builtins: Vec<BuiltinName> = Vec::new();
1279
1280        let error_message_attributes: Vec<Attribute> = vec![Attribute {
1281            name: String::from("error_message"),
1282            start_pc: 379,
1283            end_pc: 381,
1284            value: String::from("SafeUint256: addition overflow"),
1285            flow_tracking_data: Some(FlowTrackingData {
1286                ap_tracking: ApTracking {
1287                    group: 14,
1288                    offset: 35,
1289                },
1290                reference_ids: HashMap::new(),
1291            }),
1292        }];
1293
1294        let data: Vec<MaybeRelocatable> = vec![
1295            mayberelocatable!(5189976364521848832),
1296            mayberelocatable!(1000),
1297            mayberelocatable!(5189976364521848832),
1298            mayberelocatable!(2000),
1299            mayberelocatable!(5201798304953696256),
1300            mayberelocatable!(2345108766317314046),
1301        ];
1302
1303        let mut identifiers: HashMap<String, Identifier> = HashMap::new();
1304
1305        identifiers.insert(
1306            String::from("__main__.main"),
1307            Identifier {
1308                pc: Some(0),
1309                type_: Some(String::from("function")),
1310                value: None,
1311                full_name: None,
1312                members: None,
1313                cairo_type: None,
1314                size: None,
1315                destination: None,
1316            },
1317        );
1318        identifiers.insert(
1319            String::from("__main__.main.Args"),
1320            Identifier {
1321                pc: None,
1322                type_: Some(String::from("struct")),
1323                value: None,
1324                full_name: Some("__main__.main.Args".to_string()),
1325                members: Some(HashMap::new()),
1326                cairo_type: None,
1327                size: Some(0),
1328                destination: None,
1329            },
1330        );
1331        identifiers.insert(
1332            String::from("__main__.main.ImplicitArgs"),
1333            Identifier {
1334                pc: None,
1335                type_: Some(String::from("struct")),
1336                value: None,
1337                full_name: Some("__main__.main.ImplicitArgs".to_string()),
1338                members: Some(HashMap::new()),
1339                cairo_type: None,
1340                size: Some(0),
1341                destination: None,
1342            },
1343        );
1344        identifiers.insert(
1345            String::from("__main__.main.Return"),
1346            Identifier {
1347                pc: None,
1348                type_: Some(String::from("struct")),
1349                value: None,
1350                full_name: Some("__main__.main.Return".to_string()),
1351                members: Some(HashMap::new()),
1352                cairo_type: None,
1353                size: Some(0),
1354                destination: None,
1355            },
1356        );
1357        identifiers.insert(
1358            String::from("__main__.main.SIZEOF_LOCALS"),
1359            Identifier {
1360                pc: None,
1361                type_: Some(String::from("const")),
1362                value: Some(Felt252::ZERO),
1363                full_name: None,
1364                members: None,
1365                cairo_type: None,
1366                size: None,
1367                destination: None,
1368            },
1369        );
1370
1371        assert_eq!(program.builtins, builtins);
1372        assert_eq!(program.shared_program_data.data, data);
1373        assert_eq!(program.shared_program_data.main, None);
1374        assert_eq!(program.shared_program_data.identifiers, identifiers);
1375        assert_eq!(
1376            program.shared_program_data.error_message_attributes,
1377            error_message_attributes
1378        )
1379    }
1380
1381    #[test]
1382    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1383    fn deserialize_program_constants_test() {
1384        let program = Program::from_bytes(
1385            include_bytes!(
1386                "../../../cairo_programs/manually_compiled/deserialize_constant_test.json"
1387            ),
1388            Some("main"),
1389        )
1390        .unwrap();
1391
1392        let constants = [
1393            ("__main__.compare_abs_arrays.SIZEOF_LOCALS", Felt252::ZERO),
1394            (
1395                "starkware.cairo.common.cairo_keccak.packed_keccak.ALL_ONES",
1396                felt_hex!("0x7ffffffffffffffffffffffffffffffffffffffffffffffffffffffffffffff"),
1397            ),
1398            (
1399                "starkware.cairo.common.cairo_keccak.packed_keccak.BLOCK_SIZE",
1400                Felt252::from(3),
1401            ),
1402            (
1403                "starkware.cairo.common.alloc.alloc.SIZEOF_LOCALS",
1404                felt_hex!("0x800000000000011000000000000000000000000000000000000000000000001")
1405                    .neg(),
1406            ),
1407            (
1408                "starkware.cairo.common.uint256.SHIFT",
1409                felt_hex!("0x100000000000000000000000000000000"),
1410            ),
1411        ]
1412        .into_iter()
1413        .map(|(key, value)| (key.to_string(), value))
1414        .collect::<HashMap<_, _>>();
1415
1416        assert_eq!(program.constants, constants);
1417    }
1418
1419    #[test]
1420    #[cfg_attr(target_arch = "wasm32", wasm_bindgen_test)]
1421    fn default_program() {
1422        let hints_collection = HintsCollection {
1423            hints: Vec::new(),
1424            hints_ranges: Default::default(),
1425        };
1426
1427        let shared_program_data = SharedProgramData {
1428            data: Vec::new(),
1429            hints_collection,
1430            main: None,
1431            start: None,
1432            end: None,
1433            error_message_attributes: Vec::new(),
1434            instruction_locations: None,
1435            identifiers: HashMap::new(),
1436            reference_manager: Program::get_reference_list(&ReferenceManager {
1437                references: Vec::new(),
1438            }),
1439        };
1440        let program = Program {
1441            shared_program_data: Arc::new(shared_program_data),
1442            constants: HashMap::new(),
1443            builtins: Vec::new(),
1444        };
1445
1446        assert_eq!(program, Program::default());
1447    }
1448
1449    #[test]
1450    fn get_stripped_program() {
1451        let program_content = include_bytes!("../../../cairo_programs/pedersen_test.json");
1452        let program = Program::from_bytes(program_content, Some("main")).unwrap();
1453        let stripped_program = program.get_stripped_program().unwrap();
1454        assert_eq!(stripped_program.builtins, program.builtins);
1455        assert_eq!(stripped_program.data, program.shared_program_data.data);
1456        assert_eq!(
1457            stripped_program.main,
1458            program.shared_program_data.main.unwrap()
1459        );
1460    }
1461
1462    #[test]
1463    fn get_stripped_no_main() {
1464        let program_content =
1465            include_bytes!("../../../cairo_programs/proof_programs/fibonacci.json");
1466        let program = Program::from_bytes(program_content, None).unwrap();
1467        assert_matches!(
1468            program.get_stripped_program(),
1469            Err(ProgramError::StrippedProgramNoMain)
1470        );
1471    }
1472}
cairo_vm/types/program.rs

cairo_vm/types/
program.rs
