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

cairo_vm/types/
program.rs
