cairo_vm/types/
program.rs

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

cairo_vm/types/
program.rs
