cairo_lang_casm/
builder.rs

1#[cfg(not(feature = "std"))]
2pub use alloc::borrow::ToOwned;
3#[cfg(not(feature = "std"))]
4use alloc::{string::String, vec, vec::Vec};
5#[cfg(feature = "std")]
6pub use std::borrow::ToOwned;
7
8use cairo_lang_utils::casts::IntoOrPanic;
9use cairo_lang_utils::extract_matches;
10use cairo_lang_utils::ordered_hash_map::OrderedHashMap;
11use cairo_lang_utils::unordered_hash_map::{Entry, UnorderedHashMap};
12use cairo_lang_utils::unordered_hash_set::UnorderedHashSet;
13use num_bigint::BigInt;
14use num_traits::{One, Zero};
15
16use crate::ap_change::ApplyApChange;
17use crate::cell_expression::{CellExpression, CellOperator};
18use crate::deref_or_immediate;
19use crate::hints::Hint;
20use crate::instructions::{
21    AddApInstruction, AssertEqInstruction, CallInstruction, Instruction, InstructionBody,
22    JnzInstruction, JumpInstruction, RetInstruction,
23};
24use crate::operand::{BinOpOperand, CellRef, DerefOrImmediate, Operation, Register, ResOperand};
25
26#[cfg(test)]
27#[path = "builder_test.rs"]
28mod test;
29
30/// Variables for casm builder, representing a `CellExpression`.
31#[derive(Copy, Clone, Debug, Eq, PartialEq, Hash)]
32pub struct Var(usize);
33
34/// The state of the variables at some line.
35#[derive(Clone, Debug, Default, Eq, PartialEq)]
36pub struct State {
37    /// The value per variable.
38    vars: OrderedHashMap<Var, CellExpression>,
39    /// The number of allocated variables from the beginning of the run.
40    allocated: i16,
41    /// The AP change since the beginning of the run.
42    pub ap_change: usize,
43    /// The number of casm steps since the beginning of the run.
44    pub steps: usize,
45}
46impl State {
47    /// Returns the value, in relation to the initial ap value.
48    fn get_value(&self, var: Var) -> CellExpression {
49        self.vars[&var].clone()
50    }
51
52    /// Returns the value, in relation to the current ap value.
53    pub fn get_adjusted(&self, var: Var) -> CellExpression {
54        self.get_value(var).unchecked_apply_known_ap_change(self.ap_change)
55    }
56
57    /// Returns the value, assuming it is a direct cell reference.
58    pub fn get_adjusted_as_cell_ref(&self, var: Var) -> CellRef {
59        extract_matches!(self.get_adjusted(var), CellExpression::Deref)
60    }
61
62    /// Validates that the state is valid, as it had enough ap change.
63    fn validate_finality(&self) {
64        assert!(
65            self.ap_change >= self.allocated.into_or_panic(),
66            "Not enough instructions to update ap. Add an `ap += *` instruction. ap_change: {}, \
67             allocated: {}",
68            self.ap_change,
69            self.allocated,
70        );
71    }
72
73    /// Intersect the states of branches leading to the same label, validating that the states can
74    /// intersect.
75    fn intersect(&mut self, other: &Self, read_only: bool) {
76        assert_eq!(self.ap_change, other.ap_change, "Merged branches not aligned on AP change.");
77        assert_eq!(
78            self.allocated, other.allocated,
79            "Merged branches not aligned on number of allocations."
80        );
81        if read_only {
82            assert!(self.steps >= other.steps, "Finalized branch cannot be updated.");
83        } else {
84            self.steps = self.steps.max(other.steps);
85        }
86        // Allowing removal of variables as valid code won't be producible in that case anyway, and
87        // otherwise merging branches becomes very difficult.
88        self.vars.retain(|var, value| {
89            other
90                .vars
91                .get(var)
92                .map(|x| assert_eq!(x, value, "Var mismatch between branches."))
93                .is_some()
94        });
95    }
96}
97
98/// A statement added to the builder.
99enum Statement {
100    /// A final instruction, no need for further editing.
101    Final(Instruction),
102    /// A jump or call command, requires fixing the actual target label.
103    Jump(String, Instruction),
104    /// A target label for jumps, additionally with an offset for defining the label in a position
105    /// relative to the current statement.
106    Label(String, usize),
107}
108
109/// The builder result.
110pub struct CasmBuildResult<const BRANCH_COUNT: usize> {
111    /// The actual casm code.
112    pub instructions: Vec<Instruction>,
113    /// The state and relocations per branch.
114    pub branches: [(State, Vec<usize>); BRANCH_COUNT],
115}
116
117/// Builder to more easily write casm code.
118///
119/// Allows CASM building without specifically thinking about ap changes and the sizes of opcodes.
120/// Wrong usages of it would panic instead of returning a result, as this builder assumes we are in
121/// a post validation of parameters stage.
122pub struct CasmBuilder {
123    /// The state at a point of jumping into a label, per label.
124    label_state: UnorderedHashMap<String, State>,
125    /// The set of labels that were already read, so cannot be updated.
126    read_labels: UnorderedHashSet<String>,
127    /// The state at the last added statement.
128    main_state: State,
129    /// The added statements.
130    statements: Vec<Statement>,
131    /// The current set of added hints.
132    current_hints: Vec<Hint>,
133    /// The number of vars created. Used to not reuse var names.
134    var_count: usize,
135    /// Is the current state reachable.
136    /// Example for unreachable state is after a unconditional jump, before any label is stated.
137    reachable: bool,
138}
139impl CasmBuilder {
140    /// Finalizes the builder, with the requested labels as the returning branches.
141    /// "Fallthrough" is a special case for the fallthrough case.
142    pub fn build<const BRANCH_COUNT: usize>(
143        mut self,
144        branch_names: [&str; BRANCH_COUNT],
145    ) -> CasmBuildResult<BRANCH_COUNT> {
146        assert!(
147            self.current_hints.is_empty(),
148            "Build cannot be called with hints as the last addition."
149        );
150        let label_offsets = self.compute_label_offsets();
151        if self.reachable {
152            self.label_state.insert("Fallthrough".to_owned(), self.main_state);
153        }
154        let mut instructions = vec![];
155        let mut branch_relocations = UnorderedHashMap::<String, Vec<usize>>::default();
156        let mut offset = 0;
157        for statement in self.statements {
158            match statement {
159                Statement::Final(inst) => {
160                    offset += inst.body.op_size();
161                    instructions.push(inst);
162                }
163                Statement::Jump(label, mut inst) => {
164                    match label_offsets.get(&label) {
165                        Some(label_offset) => match &mut inst.body {
166                            InstructionBody::Jnz(JnzInstruction {
167                                jump_offset: DerefOrImmediate::Immediate(value),
168                                ..
169                            })
170                            | InstructionBody::Jump(JumpInstruction {
171                                target: DerefOrImmediate::Immediate(value),
172                                ..
173                            })
174                            | InstructionBody::Call(CallInstruction {
175                                target: DerefOrImmediate::Immediate(value),
176                                ..
177                            }) => {
178                                // Updating the value, instead of assigning into it, to avoid
179                                // allocating a BigInt since it is already 0.
180                                value.value += *label_offset as i128 - offset as i128;
181                            }
182
183                            _ => unreachable!("Only jump or call statements should be here."),
184                        },
185                        None => {
186                            branch_relocations.entry(label).or_default().push(instructions.len())
187                        }
188                    }
189                    offset += inst.body.op_size();
190                    instructions.push(inst);
191                }
192                Statement::Label(name, _) => {
193                    self.label_state.remove(&name);
194                }
195            }
196        }
197        let branches = branch_names.map(|label| {
198            let state = self
199                .label_state
200                .remove(label)
201                .unwrap_or_else(|| panic!("Requested a non existing final label: {label:?}."));
202            state.validate_finality();
203            (state, branch_relocations.remove(label).unwrap_or_default())
204        });
205        assert!(self.label_state.is_empty(), "Did not use all branches.");
206        assert!(branch_relocations.is_empty(), "Did not use all branch relocations.");
207        CasmBuildResult { instructions, branches }
208    }
209
210    /// Returns the current ap change of the builder.
211    /// Useful for manual ap change handling.
212    pub fn curr_ap_change(&self) -> usize {
213        self.main_state.ap_change
214    }
215
216    /// Computes the code offsets of all the labels.
217    fn compute_label_offsets(&self) -> UnorderedHashMap<String, usize> {
218        let mut label_offsets = UnorderedHashMap::default();
219        let mut offset = 0;
220        for statement in &self.statements {
221            match statement {
222                Statement::Final(inst) | Statement::Jump(_, inst) => {
223                    offset += inst.body.op_size();
224                }
225                Statement::Label(name, extra_offset) => {
226                    label_offsets.insert(name.clone(), offset + extra_offset);
227                }
228            }
229        }
230        label_offsets
231    }
232
233    /// Adds a variable pointing to `value`.
234    pub fn add_var(&mut self, value: CellExpression) -> Var {
235        let var = Var(self.var_count);
236        self.var_count += 1;
237        self.main_state.vars.insert(var, value);
238        var
239    }
240
241    /// Allocates a new variable in memory, either local (FP-based) or temp (AP-based).
242    pub fn alloc_var(&mut self, local_var: bool) -> Var {
243        let var = self.add_var(CellExpression::Deref(CellRef {
244            offset: self.main_state.allocated,
245            register: if local_var { Register::FP } else { Register::AP },
246        }));
247        self.main_state.allocated += 1;
248        var
249    }
250
251    /// Returns an additional variable pointing to the same value.
252    pub fn duplicate_var(&mut self, var: Var) -> Var {
253        self.add_var(self.get_value(var, false))
254    }
255
256    /// Adds a hint, generated from `inputs` which are cell refs or immediates and `outputs` which
257    /// must be cell refs.
258    pub fn add_hint<
259        const INPUTS_COUNT: usize,
260        const OUTPUTS_COUNT: usize,
261        THint: Into<Hint>,
262        F: FnOnce([ResOperand; INPUTS_COUNT], [CellRef; OUTPUTS_COUNT]) -> THint,
263    >(
264        &mut self,
265        f: F,
266        inputs: [Var; INPUTS_COUNT],
267        outputs: [Var; OUTPUTS_COUNT],
268    ) {
269        self.current_hints.push(
270            f(
271                inputs.map(|v| match self.get_value(v, true) {
272                    CellExpression::Deref(cell) => ResOperand::Deref(cell),
273                    CellExpression::DoubleDeref(cell, offset) => {
274                        ResOperand::DoubleDeref(cell, offset)
275                    }
276                    CellExpression::Immediate(imm) => imm.into(),
277                    CellExpression::BinOp { op, a: other, b } => match op {
278                        CellOperator::Add => {
279                            ResOperand::BinOp(BinOpOperand { op: Operation::Add, a: other, b })
280                        }
281                        CellOperator::Mul => {
282                            ResOperand::BinOp(BinOpOperand { op: Operation::Mul, a: other, b })
283                        }
284                        CellOperator::Sub | CellOperator::Div => {
285                            panic!("hints to non ResOperand references are not supported.")
286                        }
287                    },
288                }),
289                outputs.map(|v| self.as_cell_ref(v, true)),
290            )
291            .into(),
292        );
293    }
294
295    /// Adds an assertion that `dst = res`.
296    /// `dst` must be a cell reference.
297    pub fn assert_vars_eq(&mut self, dst: Var, res: Var) {
298        let a = self.as_cell_ref(dst, true);
299        let b = self.get_value(res, true);
300        let (a, b) = match b {
301            CellExpression::Deref(cell) => (a, ResOperand::Deref(cell)),
302            CellExpression::DoubleDeref(cell, offset) => (a, ResOperand::DoubleDeref(cell, offset)),
303            CellExpression::Immediate(imm) => (a, imm.into()),
304            CellExpression::BinOp { op, a: other, b } => match op {
305                CellOperator::Add => {
306                    (a, ResOperand::BinOp(BinOpOperand { op: Operation::Add, a: other, b }))
307                }
308                CellOperator::Mul => {
309                    (a, ResOperand::BinOp(BinOpOperand { op: Operation::Mul, a: other, b }))
310                }
311                CellOperator::Sub => {
312                    (other, ResOperand::BinOp(BinOpOperand { op: Operation::Add, a, b }))
313                }
314                CellOperator::Div => {
315                    (other, ResOperand::BinOp(BinOpOperand { op: Operation::Mul, a, b }))
316                }
317            },
318        };
319        let instruction =
320            self.next_instruction(InstructionBody::AssertEq(AssertEqInstruction { a, b }), true);
321        self.statements.push(Statement::Final(instruction));
322    }
323
324    /// Writes and increments a buffer.
325    /// Useful for RangeCheck and similar buffers.
326    /// `buffer` must be a cell reference, or a cell reference with a small added constant.
327    /// `value` must be a cell reference.
328    pub fn buffer_write_and_inc(&mut self, buffer: Var, value: Var) {
329        let (cell, offset) = self.buffer_get_and_inc(buffer);
330        let location = self.add_var(CellExpression::DoubleDeref(cell, offset));
331        self.assert_vars_eq(value, location);
332    }
333
334    /// Writes `var` as a new tempvar and returns it as a variable, unless its value is already
335    /// `deref` (which includes trivial calculations as well) so it instead returns a variable
336    /// pointing to that location.
337    pub fn maybe_add_tempvar(&mut self, var: Var) -> Var {
338        self.add_var(CellExpression::Deref(match self.get_value(var, false) {
339            CellExpression::Deref(cell) => cell,
340            CellExpression::BinOp {
341                op: CellOperator::Add | CellOperator::Sub,
342                a,
343                b: DerefOrImmediate::Immediate(imm),
344            } if imm.value.is_zero() => a,
345            CellExpression::BinOp {
346                op: CellOperator::Mul | CellOperator::Div,
347                a,
348                b: DerefOrImmediate::Immediate(imm),
349            } if imm.value.is_one() => a,
350            _ => {
351                let temp = self.alloc_var(false);
352                self.assert_vars_eq(temp, var);
353                return temp;
354            }
355        }))
356    }
357
358    /// Increments a buffer and allocates and returns variable pointing to its previous value.
359    pub fn get_ref_and_inc(&mut self, buffer: Var) -> Var {
360        let (cell, offset) = self.as_cell_ref_plus_const(buffer, 0, false);
361        self.main_state.vars.insert(
362            buffer,
363            CellExpression::BinOp {
364                op: CellOperator::Add,
365                a: cell,
366                b: deref_or_immediate!(BigInt::from(offset) + 1),
367            },
368        );
369        self.add_var(CellExpression::DoubleDeref(cell, offset))
370    }
371
372    /// Increments a buffer and returning the previous value it pointed to.
373    /// Useful for writing, reading and referencing values.
374    /// `buffer` must be a cell reference, or a cell reference with a small added constant.
375    fn buffer_get_and_inc(&mut self, buffer: Var) -> (CellRef, i16) {
376        let (base, offset) = match self.get_value(buffer, false) {
377            CellExpression::Deref(cell) => (cell, 0),
378            CellExpression::BinOp {
379                op: CellOperator::Add,
380                a,
381                b: DerefOrImmediate::Immediate(imm),
382            } => (a, imm.value.try_into().expect("Too many buffer writes.")),
383            _ => panic!("Not a valid buffer."),
384        };
385        self.main_state.vars.insert(
386            buffer,
387            CellExpression::BinOp {
388                op: CellOperator::Add,
389                a: base,
390                b: deref_or_immediate!(offset + 1),
391            },
392        );
393        (base, offset)
394    }
395
396    /// Increases AP by `size`.
397    pub fn add_ap(&mut self, size: usize) {
398        let instruction = self.next_instruction(
399            InstructionBody::AddAp(AddApInstruction { operand: BigInt::from(size).into() }),
400            false,
401        );
402        self.statements.push(Statement::Final(instruction));
403        self.main_state.ap_change += size;
404    }
405
406    /// Increases the AP change by `size`, without adding an instruction.
407    pub fn increase_ap_change(&mut self, amount: usize) {
408        self.main_state.ap_change += amount;
409        self.main_state.allocated += amount.into_or_panic::<i16>();
410    }
411
412    /// Returns a variable that is the `op` of `lhs` and `rhs`.
413    /// `lhs` must be a cell reference and `rhs` must be deref or immediate.
414    pub fn bin_op(&mut self, op: CellOperator, lhs: Var, rhs: Var) -> Var {
415        let (a, b) = match self.get_value(lhs, false) {
416            // Regular `bin_op` support.
417            CellExpression::Deref(cell) => (cell, self.as_deref_or_imm(rhs, false)),
418            // `add_with_const` + `imm` support.
419            CellExpression::BinOp {
420                op: CellOperator::Add,
421                a,
422                b: DerefOrImmediate::Immediate(imm),
423            } if op == CellOperator::Add => (
424                a,
425                DerefOrImmediate::Immediate(
426                    (imm.value
427                        + extract_matches!(self.get_value(rhs, false), CellExpression::Immediate))
428                    .into(),
429                ),
430            ),
431            _ => panic!(
432                "`bin_op` is supported only between a `deref` and a `deref_or_imm`, or a \
433                 `add_with_const` and `imm`."
434            ),
435        };
436        self.add_var(CellExpression::BinOp { op, a, b })
437    }
438
439    /// Returns a variable that is `[[var] + offset]`.
440    /// `var` must be a cell reference, or a cell ref plus a small constant.
441    pub fn double_deref(&mut self, var: Var, offset: i16) -> Var {
442        let (cell, full_offset) = self.as_cell_ref_plus_const(var, offset, false);
443        self.add_var(CellExpression::DoubleDeref(cell, full_offset))
444    }
445
446    /// Sets the label to have the set states, otherwise tests if the state matches the existing one
447    /// by merging.
448    fn set_or_test_label_state(&mut self, label: String, state: State) {
449        match self.label_state.entry(label) {
450            Entry::Occupied(e) => {
451                let read_only = self.read_labels.contains(e.key());
452                e.into_mut().intersect(&state, read_only);
453            }
454            Entry::Vacant(e) => {
455                e.insert(state);
456            }
457        }
458    }
459
460    /// Add a statement to jump to `label`.
461    pub fn jump(&mut self, label: String) {
462        let instruction = self.next_instruction(
463            InstructionBody::Jump(JumpInstruction {
464                target: deref_or_immediate!(0),
465                relative: true,
466            }),
467            true,
468        );
469        self.statements.push(Statement::Jump(label.clone(), instruction));
470        let mut state = State::default();
471        core::mem::swap(&mut state, &mut self.main_state);
472        self.set_or_test_label_state(label, state);
473        self.reachable = false;
474    }
475
476    /// Add a statement to jump to `label` if `condition != 0`.
477    /// `condition` must be a cell reference.
478    pub fn jump_nz(&mut self, condition: Var, label: String) {
479        let cell = self.as_cell_ref(condition, true);
480        let instruction = self.next_instruction(
481            InstructionBody::Jnz(JnzInstruction {
482                condition: cell,
483                jump_offset: deref_or_immediate!(0),
484            }),
485            true,
486        );
487        self.statements.push(Statement::Jump(label.clone(), instruction));
488        self.set_or_test_label_state(label, self.main_state.clone());
489    }
490
491    /// Adds a label here named `name`.
492    pub fn label(&mut self, name: String) {
493        if self.reachable {
494            self.set_or_test_label_state(name.clone(), self.main_state.clone());
495        }
496        self.read_labels.insert(name.clone());
497        self.main_state = self
498            .label_state
499            .get(&name)
500            .unwrap_or_else(|| panic!("No known value for state on reaching {name}."))
501            .clone();
502        self.statements.push(Statement::Label(name, 0));
503        self.reachable = true;
504    }
505
506    /// Adds a label `name` in distance `offset` from the current point.
507    /// Useful for calling code outside of the builder's context.
508    pub fn future_label(&mut self, name: String, offset: usize) {
509        self.statements.push(Statement::Label(name, offset));
510    }
511
512    /// Rescoping the values, while ignoring all vars not stated in `vars` and giving the vars on
513    /// the left side the values of the vars on the right side.
514    pub fn rescope<const VAR_COUNT: usize>(&mut self, vars: [(Var, Var); VAR_COUNT]) {
515        self.main_state.validate_finality();
516        let values =
517            vars.map(|(new_var, value_var)| (new_var, self.main_state.get_adjusted(value_var)));
518        self.main_state.ap_change = 0;
519        self.main_state.allocated = 0;
520        self.main_state.vars.clear();
521        self.main_state.vars.extend(values);
522    }
523
524    /// Adds a call command to 'label'. All AP based variables are passed to the called function
525    /// state and dropped from the calling function state.
526    pub fn call(&mut self, label: String) {
527        self.main_state.validate_finality();
528        // Vars to be passed to the called function state.
529        let mut function_vars = OrderedHashMap::<Var, CellExpression>::default();
530        // FP based vars which will remain in the current state.
531        let mut main_vars = OrderedHashMap::<Var, CellExpression>::default();
532        let ap_change = self.main_state.ap_change;
533        let cell_to_var_flags = |cell: &CellRef| {
534            if cell.register == Register::AP { (true, false) } else { (false, true) }
535        };
536        for (var, value) in self.main_state.vars.iter() {
537            let (function_var, main_var) = match value {
538                CellExpression::DoubleDeref(cell, _) | CellExpression::Deref(cell) => {
539                    cell_to_var_flags(cell)
540                }
541                CellExpression::Immediate(_) => (true, true),
542                CellExpression::BinOp { op: _, a, b } => match b {
543                    DerefOrImmediate::Deref(cell) => {
544                        if a.register == cell.register {
545                            cell_to_var_flags(cell)
546                        } else {
547                            // Mixed FP and AP based, dropped from both states.
548                            (false, false)
549                        }
550                    }
551                    DerefOrImmediate::Immediate(_) => (true, true),
552                },
553            };
554            if function_var {
555                // Apply ap change (+2 because of the call statement) and change to FP based before
556                // the function call.
557                let mut value = value.clone().unchecked_apply_known_ap_change(ap_change + 2);
558                match &mut value {
559                    CellExpression::DoubleDeref(cell, _) | CellExpression::Deref(cell) => {
560                        cell.register = Register::FP
561                    }
562                    CellExpression::Immediate(_) => {}
563                    CellExpression::BinOp { a, b, .. } => {
564                        a.register = Register::FP;
565                        match b {
566                            DerefOrImmediate::Deref(cell) => cell.register = Register::FP,
567                            DerefOrImmediate::Immediate(_) => {}
568                        }
569                    }
570                }
571                function_vars.insert(*var, value);
572            }
573            if main_var {
574                main_vars.insert(*var, value.clone());
575            }
576        }
577
578        let instruction = self.next_instruction(
579            InstructionBody::Call(CallInstruction {
580                relative: true,
581                target: deref_or_immediate!(0),
582            }),
583            false,
584        );
585        self.statements.push(Statement::Jump(label.clone(), instruction));
586
587        self.main_state.vars = main_vars;
588        self.main_state.allocated = 0;
589        self.main_state.ap_change = 0;
590        let function_state = State { vars: function_vars, ..Default::default() };
591        self.set_or_test_label_state(label, function_state);
592    }
593
594    /// A return statement in the code.
595    pub fn ret(&mut self) {
596        self.main_state.validate_finality();
597        let instruction = self.next_instruction(InstructionBody::Ret(RetInstruction {}), false);
598        self.statements.push(Statement::Final(instruction));
599        self.reachable = false;
600    }
601
602    /// The number of steps at the last added statement.
603    pub fn steps(&self) -> usize {
604        self.main_state.steps
605    }
606
607    /// Resets the steps counter.
608    pub fn reset_steps(&mut self) {
609        self.main_state.steps = 0;
610    }
611
612    /// Create an assert that would always fail.
613    pub fn fail(&mut self) {
614        let cell = CellRef { offset: -1, register: Register::FP };
615        let instruction = self.next_instruction(
616            InstructionBody::AssertEq(AssertEqInstruction {
617                a: cell,
618                b: ResOperand::BinOp(BinOpOperand {
619                    op: Operation::Add,
620                    a: cell,
621                    b: DerefOrImmediate::Immediate(BigInt::one().into()),
622                }),
623            }),
624            false,
625        );
626        self.statements.push(Statement::Final(instruction));
627        self.mark_unreachable();
628    }
629
630    /// Marks the current state as unreachable.
631    /// Useful for removing bookkeeping after unsatisfiable conditions.
632    pub fn mark_unreachable(&mut self) {
633        self.reachable = false;
634    }
635
636    /// Returns `var`s value, with fixed ap if `adjust_ap` is true.
637    pub fn get_value(&self, var: Var, adjust_ap: bool) -> CellExpression {
638        if adjust_ap { self.main_state.get_adjusted(var) } else { self.main_state.get_value(var) }
639    }
640
641    /// Returns `var`s value as a cell reference, with fixed ap if `adjust_ap` is true.
642    fn as_cell_ref(&self, var: Var, adjust_ap: bool) -> CellRef {
643        extract_matches!(self.get_value(var, adjust_ap), CellExpression::Deref)
644    }
645
646    /// Returns `var`s value as a cell reference or immediate, with fixed ap if `adjust_ap` is true.
647    fn as_deref_or_imm(&self, var: Var, adjust_ap: bool) -> DerefOrImmediate {
648        match self.get_value(var, adjust_ap) {
649            CellExpression::Deref(cell) => DerefOrImmediate::Deref(cell),
650            CellExpression::Immediate(imm) => DerefOrImmediate::Immediate(imm.into()),
651            CellExpression::DoubleDeref(_, _) | CellExpression::BinOp { .. } => {
652                panic!("wrong usage.")
653            }
654        }
655    }
656
657    /// Returns `var`s value as a cell reference plus a small const offset, with fixed ap if
658    /// `adjust_ap` is true.
659    fn as_cell_ref_plus_const(
660        &self,
661        var: Var,
662        additional_offset: i16,
663        adjust_ap: bool,
664    ) -> (CellRef, i16) {
665        match self.get_value(var, adjust_ap) {
666            CellExpression::Deref(cell) => (cell, additional_offset),
667            CellExpression::BinOp {
668                op: CellOperator::Add,
669                a,
670                b: DerefOrImmediate::Immediate(imm),
671            } => (
672                a,
673                (imm.value + additional_offset).try_into().expect("Offset too large for deref."),
674            ),
675            _ => panic!("Not a valid ptr."),
676        }
677    }
678
679    /// Returns an instruction wrapping the instruction body, and updates the state.
680    /// If `inc_ap_supported` may add an `ap++` to the instruction.
681    fn next_instruction(&mut self, body: InstructionBody, inc_ap_supported: bool) -> Instruction {
682        assert!(self.reachable, "Cannot add instructions at unreachable code.");
683        let inc_ap =
684            inc_ap_supported && self.main_state.allocated as usize > self.main_state.ap_change;
685        if inc_ap {
686            self.main_state.ap_change += 1;
687        }
688        self.main_state.steps += 1;
689        let mut hints = vec![];
690        core::mem::swap(&mut hints, &mut self.current_hints);
691        Instruction { body, inc_ap, hints }
692    }
693}
694
695impl Default for CasmBuilder {
696    fn default() -> Self {
697        Self {
698            label_state: Default::default(),
699            read_labels: Default::default(),
700            main_state: Default::default(),
701            statements: Default::default(),
702            current_hints: Default::default(),
703            var_count: Default::default(),
704            reachable: true,
705        }
706    }
707}
708
709#[macro_export]
710macro_rules! casm_build_extend {
711    ($builder:expr,) => {};
712    ($builder:expr, tempvar $var:ident; $($tok:tt)*) => {
713        let $var = $builder.alloc_var(false);
714        $crate::casm_build_extend!($builder, $($tok)*)
715    };
716    ($builder:expr, localvar $var:ident; $($tok:tt)*) => {
717        let $var = $builder.alloc_var(true);
718        $crate::casm_build_extend!($builder, $($tok)*)
719    };
720    ($builder:expr, ap += $value:expr; $($tok:tt)*) => {
721        $builder.add_ap($value);
722        $crate::casm_build_extend!($builder, $($tok)*)
723    };
724    ($builder:expr, const $imm:ident = $value:expr; $($tok:tt)*) => {
725        let $imm = $builder.add_var($crate::cell_expression::CellExpression::Immediate(($value).into()));
726        $crate::casm_build_extend!($builder, $($tok)*)
727    };
728    ($builder:expr, assert $dst:ident = $res:ident; $($tok:tt)*) => {
729        $builder.assert_vars_eq($dst, $res);
730        $crate::casm_build_extend!($builder, $($tok)*)
731    };
732    ($builder:expr, assert $dst:ident = $a:ident + $b:ident; $($tok:tt)*) => {
733        {
734            let __sum = $builder.bin_op($crate::cell_expression::CellOperator::Add, $a, $b);
735            $builder.assert_vars_eq($dst, __sum);
736        }
737        $crate::casm_build_extend!($builder, $($tok)*)
738    };
739    ($builder:expr, assert $dst:ident = $a:ident * $b:ident; $($tok:tt)*) => {
740        {
741            let __product = $builder.bin_op($crate::cell_expression::CellOperator::Mul, $a, $b);
742            $builder.assert_vars_eq($dst, __product);
743        }
744        $crate::casm_build_extend!($builder, $($tok)*)
745    };
746    ($builder:expr, assert $dst:ident = $a:ident - $b:ident; $($tok:tt)*) => {
747        {
748            let __diff = $builder.bin_op($crate::cell_expression::CellOperator::Sub, $a, $b);
749            $builder.assert_vars_eq($dst, __diff);
750        }
751        $crate::casm_build_extend!($builder, $($tok)*)
752    };
753    ($builder:expr, assert $dst:ident = $a:ident / $b:ident; $($tok:tt)*) => {
754        {
755            let __division = $builder.bin_op($crate::cell_expression::CellOperator::Div, $a, $b);
756            $builder.assert_vars_eq($dst, __division);
757        }
758        $crate::casm_build_extend!($builder, $($tok)*)
759    };
760    ($builder:expr, assert $dst:ident = $buffer:ident [ $offset:expr ] ; $($tok:tt)*) => {
761        {
762            let __deref = $builder.double_deref($buffer, $offset);
763            $builder.assert_vars_eq($dst, __deref);
764        }
765        $crate::casm_build_extend!($builder, $($tok)*)
766    };
767    ($builder:expr, assert $dst:ident = * $buffer:ident; $($tok:tt)*) => {
768        {
769            let __deref = $builder.double_deref($buffer, 0);
770            $builder.assert_vars_eq($dst, __deref);
771        }
772        $crate::casm_build_extend!($builder, $($tok)*)
773    };
774    ($builder:expr, assert $value:ident = * ( $buffer:ident ++ ); $($tok:tt)*) => {
775        $builder.buffer_write_and_inc($buffer, $value);
776        $crate::casm_build_extend!($builder, $($tok)*)
777    };
778    ($builder:expr, tempvar $var:ident = $value:ident; $($tok:tt)*) => {
779        $crate::casm_build_extend!($builder, tempvar $var; assert $var = $value; $($tok)*);
780    };
781    ($builder:expr, tempvar $var:ident = $lhs:ident + $rhs:ident; $($tok:tt)*) => {
782        $crate::casm_build_extend!($builder, tempvar $var; assert $var = $lhs + $rhs; $($tok)*);
783    };
784    ($builder:expr, tempvar $var:ident = $lhs:ident * $rhs:ident; $($tok:tt)*) => {
785        $crate::casm_build_extend!($builder, tempvar $var; assert $var = $lhs * $rhs; $($tok)*);
786    };
787    ($builder:expr, tempvar $var:ident = $lhs:ident - $rhs:ident; $($tok:tt)*) => {
788        $crate::casm_build_extend!($builder, tempvar $var; assert $var = $lhs - $rhs; $($tok)*);
789    };
790    ($builder:expr, tempvar $var:ident = $lhs:ident / $rhs:ident; $($tok:tt)*) => {
791        $crate::casm_build_extend!($builder, tempvar $var; assert $var = $lhs / $rhs; $($tok)*);
792    };
793    ($builder:expr, tempvar $var:ident = * ( $buffer:ident ++ ); $($tok:tt)*) => {
794        $crate::casm_build_extend!($builder, tempvar $var; assert $var = *($buffer++); $($tok)*);
795    };
796    ($builder:expr, tempvar $var:ident = $buffer:ident [ $offset:expr ]; $($tok:tt)*) => {
797        $crate::casm_build_extend!($builder, tempvar $var; assert $var = $buffer[$offset]; $($tok)*);
798    };
799    ($builder:expr, tempvar $var:ident = * $buffer:ident ; $($tok:tt)*) => {
800        $crate::casm_build_extend!($builder, tempvar $var; assert $var = *$buffer; $($tok)*);
801    };
802    ($builder:expr, maybe_tempvar $var:ident = $value:ident; $($tok:tt)*) => {
803        let $var = $builder.maybe_add_tempvar($value);
804        $crate::casm_build_extend!($builder, $($tok)*);
805    };
806    ($builder:expr, maybe_tempvar $var:ident = $lhs:ident + $rhs:ident; $($tok:tt)*) => {
807        $crate::casm_build_extend! {$builder,
808            let $var = $lhs + $rhs;
809            maybe_tempvar $var = $var;
810            $($tok)*
811        };
812    };
813    ($builder:expr, maybe_tempvar $var:ident = $lhs:ident * $rhs:ident; $($tok:tt)*) => {
814        $crate::casm_build_extend! {$builder,
815            let $var = $lhs * $rhs;
816            maybe_tempvar $var = $var;
817            $($tok)*
818        };
819    };
820    ($builder:expr, maybe_tempvar $var:ident = $lhs:ident - $rhs:ident; $($tok:tt)*) => {
821        $crate::casm_build_extend! {$builder,
822            let $var = $lhs - $rhs;
823            maybe_tempvar $var = $var;
824            $($tok)*
825        };
826    };
827    ($builder:expr, maybe_tempvar $var:ident = $lhs:ident / $rhs:ident; $($tok:tt)*) => {
828        $crate::casm_build_extend! {$builder,
829            let $var = $lhs / $rhs;
830            maybe_tempvar $var = $var;
831            $($tok)*
832        };
833    };
834    ($builder:expr, localvar $var:ident = $value:ident; $($tok:tt)*) => {
835        $crate::casm_build_extend!($builder, localvar $var; assert $var = $value; $($tok)*);
836    };
837    ($builder:expr, localvar $var:ident = $lhs:ident + $rhs:ident; $($tok:tt)*) => {
838        $crate::casm_build_extend!($builder, localvar $var; assert $var = $lhs + $rhs; $($tok)*);
839    };
840    ($builder:expr, localvar $var:ident = $lhs:ident * $rhs:ident; $($tok:tt)*) => {
841        $crate::casm_build_extend!($builder, localvar $var; assert $var = $lhs * $rhs; $($tok)*);
842    };
843    ($builder:expr, localvar $var:ident = $lhs:ident - $rhs:ident; $($tok:tt)*) => {
844        $crate::casm_build_extend!($builder, localvar $var; assert $var = $lhs - $rhs; $($tok)*);
845    };
846    ($builder:expr, localvar $var:ident = $lhs:ident / $rhs:ident; $($tok:tt)*) => {
847        $crate::casm_build_extend!($builder, localvar $var; assert $var = $lhs / $rhs; $($tok)*);
848    };
849    ($builder:expr, localvar $var:ident = * ( $buffer:ident ++ ); $($tok:tt)*) => {
850        $crate::casm_build_extend!($builder, localvar $var; assert $var = *($buffer++); $($tok)*);
851    };
852    ($builder:expr, localvar $var:ident = $buffer:ident [ $offset:expr ]; $($tok:tt)*) => {
853        $crate::casm_build_extend!($builder, localvar $var; assert $var = $buffer[$offset]; $($tok)*);
854    };
855    ($builder:expr, localvar $var:ident = * $buffer:ident ; $($tok:tt)*) => {
856        $crate::casm_build_extend!($builder, localvar $var; assert $var = *$buffer; $($tok)*);
857    };
858    ($builder:expr, let $dst:ident = $a:ident + $b:ident; $($tok:tt)*) => {
859        let $dst = $builder.bin_op($crate::cell_expression::CellOperator::Add, $a, $b);
860        $crate::casm_build_extend!($builder, $($tok)*)
861    };
862    ($builder:expr, let $dst:ident = $a:ident * $b:ident; $($tok:tt)*) => {
863        let $dst = $builder.bin_op($crate::cell_expression::CellOperator::Mul, $a, $b);
864        $crate::casm_build_extend!($builder, $($tok)*)
865    };
866    ($builder:expr, let $dst:ident = $a:ident - $b:ident; $($tok:tt)*) => {
867        let $dst = $builder.bin_op($crate::cell_expression::CellOperator::Sub, $a, $b);
868        $crate::casm_build_extend!($builder, $($tok)*)
869    };
870    ($builder:expr, let $dst:ident = $a:ident / $b:ident; $($tok:tt)*) => {
871        let $dst = $builder.bin_op($crate::cell_expression::CellOperator::Div, $a, $b);
872        $crate::casm_build_extend!($builder, $($tok)*)
873    };
874    ($builder:expr, let $dst:ident = * ( $buffer:ident ++ ); $($tok:tt)*) => {
875        let $dst = $builder.get_ref_and_inc($buffer);
876        $crate::casm_build_extend!($builder, $($tok)*)
877    };
878    ($builder:expr, let $dst:ident = $buffer:ident [ $offset:expr ] ; $($tok:tt)*) => {
879        let $dst = $builder.double_deref($buffer, $offset);
880        $crate::casm_build_extend!($builder, $($tok)*)
881    };
882    ($builder:expr, let $dst:ident = *$buffer:ident; $($tok:tt)*) => {
883        let $dst = $builder.double_deref($buffer, 0);
884        $crate::casm_build_extend!($builder, $($tok)*)
885    };
886    ($builder:expr, let $dst:ident = $src:ident; $($tok:tt)*) => {
887        let $dst = $builder.duplicate_var($src);
888        $crate::casm_build_extend!($builder, $($tok)*)
889    };
890    ($builder:expr, jump $target:ident; $($tok:tt)*) => {
891        $builder.jump($crate::builder::ToOwned::to_owned(core::stringify!($target)));
892        $crate::casm_build_extend!($builder, $($tok)*)
893    };
894    ($builder:expr, jump $target:ident if $condition:ident != 0; $($tok:tt)*) => {
895        $builder.jump_nz($condition, $crate::builder::ToOwned::to_owned(core::stringify!($target)));
896        $crate::casm_build_extend!($builder, $($tok)*)
897    };
898    ($builder:expr, let ($($var_name:ident),*) = call $target:ident; $($tok:tt)*) => {
899        $builder.call($crate::builder::ToOwned::to_owned(core::stringify!($target)));
900
901        let __var_count = {0i16 $(+ (stringify!($var_name), 1i16).1)*};
902        let mut __var_index = 0;
903        $(
904            let $var_name = $builder.add_var($crate::cell_expression::CellExpression::Deref($crate::operand::CellRef {
905                offset: __var_index - __var_count,
906                register: $crate::operand::Register::AP,
907            }));
908            __var_index += 1;
909        )*
910        $crate::casm_build_extend!($builder, $($tok)*)
911    };
912    ($builder:expr, ret; $($tok:tt)*) => {
913        $builder.ret();
914        $crate::casm_build_extend!($builder, $($tok)*)
915    };
916    ($builder:expr, $label:ident: $($tok:tt)*) => {
917        $builder.label($crate::builder::ToOwned::to_owned(core::stringify!($label)));
918        $crate::casm_build_extend!($builder, $($tok)*)
919    };
920    ($builder:expr, fail; $($tok:tt)*) => {
921        $builder.fail();
922        $crate::casm_build_extend!($builder, $($tok)*)
923    };
924    ($builder:expr, unsatisfiable_assert $dst:ident = $res:ident; $($tok:tt)*) => {
925        $crate::casm_build_extend!($builder, assert $dst = $res;);
926        $builder.mark_unreachable();
927        $crate::casm_build_extend!($builder, $($tok)*)
928    };
929    ($builder:expr, hint $hint_head:ident$(::$hint_tail:ident)+ {
930            $($input_name:ident $(: $input_value:ident)?),*
931        } into {
932            $($output_name:ident $(: $output_value:ident)?),*
933        }; $($tok:tt)*) => {
934        $builder.add_hint(
935            |[$($input_name),*], [$($output_name),*]| $hint_head$(::$hint_tail)+ {
936                $($input_name,)* $($output_name,)*
937            },
938            [$($crate::casm_build_hint_param_value!($input_name  $(: $input_value)?),)*],
939            [$($crate::casm_build_hint_param_value!($output_name  $(: $output_value)?),)*],
940        );
941        $crate::casm_build_extend!($builder, $($tok)*)
942    };
943    ($builder:expr, hint $hint_name:ident { $($inputs:tt)* } into { $($outputs:tt)* }; $($tok:tt)*) => {
944        $crate::casm_build_extend! {$builder,
945            hint $crate::hints::CoreHint::$hint_name { $($inputs)* } into { $($outputs)* };
946            $($tok)*
947        }
948    };
949    ($builder:expr, hint $hint_head:ident$(::$hint_tail:ident)* { $($inputs:tt)* }; $($tok:tt)*) => {
950        $crate::casm_build_extend! {$builder,
951            hint $hint_head$(::$hint_tail)* { $($inputs)* } into {};
952            $($tok)*
953        }
954    };
955    ($builder:expr, hint $hint_head:ident$(::$hint_tail:ident)* into { $($outputs:tt)* }; $($tok:tt)*) => {
956        $crate::casm_build_extend! {$builder,
957            hint $hint_head$(::$hint_tail)* {} into { $($outputs)* };
958            $($tok)*
959        }
960    };
961    ($builder:expr, rescope { $($new_var:ident = $value_var:ident),* }; $($tok:tt)*) => {
962        $builder.rescope([$(($new_var, $value_var)),*]);
963        $crate::casm_build_extend!($builder, $($tok)*)
964    };
965    ($builder:expr, #{ validate steps == $count:expr; } $($tok:tt)*) => {
966        assert_eq!($builder.steps(), $count);
967        $crate::casm_build_extend!($builder, $($tok)*)
968    };
969    ($builder:expr, #{ steps = 0; } $($tok:tt)*) => {
970        $builder.reset_steps();
971        $crate::casm_build_extend!($builder, $($tok)*)
972    };
973    ($builder:expr, #{ $counter:ident += steps; steps = 0; } $($tok:tt)*) => {
974        $counter += $builder.steps() as i32;
975        $builder.reset_steps();
976        $crate::casm_build_extend!($builder, $($tok)*)
977    };
978}
979
980#[macro_export]
981macro_rules! casm_build_hint_param_value {
982    ($_name:ident : $value:ident) => {
983        $value
984    };
985    ($name:ident) => {
986        $name
987    };
988}
cairo_lang_casm/builder.rs

cairo_lang_casm/
builder.rs
