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(buffer, CellExpression::BinOp {
362            op: CellOperator::Add,
363            a: cell,
364            b: deref_or_immediate!(BigInt::from(offset) + 1),
365        });
366        self.add_var(CellExpression::DoubleDeref(cell, offset))
367    }
368
369    /// Increments a buffer and returning the previous value it pointed to.
370    /// Useful for writing, reading and referencing values.
371    /// `buffer` must be a cell reference, or a cell reference with a small added constant.
372    fn buffer_get_and_inc(&mut self, buffer: Var) -> (CellRef, i16) {
373        let (base, offset) = match self.get_value(buffer, false) {
374            CellExpression::Deref(cell) => (cell, 0),
375            CellExpression::BinOp {
376                op: CellOperator::Add,
377                a,
378                b: DerefOrImmediate::Immediate(imm),
379            } => (a, imm.value.try_into().expect("Too many buffer writes.")),
380            _ => panic!("Not a valid buffer."),
381        };
382        self.main_state.vars.insert(buffer, CellExpression::BinOp {
383            op: CellOperator::Add,
384            a: base,
385            b: deref_or_immediate!(offset + 1),
386        });
387        (base, offset)
388    }
389
390    /// Increases AP by `size`.
391    pub fn add_ap(&mut self, size: usize) {
392        let instruction = self.next_instruction(
393            InstructionBody::AddAp(AddApInstruction { operand: BigInt::from(size).into() }),
394            false,
395        );
396        self.statements.push(Statement::Final(instruction));
397        self.main_state.ap_change += size;
398    }
399
400    /// Increases the AP change by `size`, without adding an instruction.
401    pub fn increase_ap_change(&mut self, amount: usize) {
402        self.main_state.ap_change += amount;
403        self.main_state.allocated += amount.into_or_panic::<i16>();
404    }
405
406    /// Returns a variable that is the `op` of `lhs` and `rhs`.
407    /// `lhs` must be a cell reference and `rhs` must be deref or immediate.
408    pub fn bin_op(&mut self, op: CellOperator, lhs: Var, rhs: Var) -> Var {
409        let (a, b) = match self.get_value(lhs, false) {
410            // Regular `bin_op` support.
411            CellExpression::Deref(cell) => (cell, self.as_deref_or_imm(rhs, false)),
412            // `add_with_const` + `imm` support.
413            CellExpression::BinOp {
414                op: CellOperator::Add,
415                a,
416                b: DerefOrImmediate::Immediate(imm),
417            } if op == CellOperator::Add => (
418                a,
419                DerefOrImmediate::Immediate(
420                    (imm.value
421                        + extract_matches!(self.get_value(rhs, false), CellExpression::Immediate))
422                    .into(),
423                ),
424            ),
425            _ => panic!(
426                "`bin_op` is supported only between a `deref` and a `deref_or_imm`, or a \
427                 `add_with_const` and `imm`."
428            ),
429        };
430        self.add_var(CellExpression::BinOp { op, a, b })
431    }
432
433    /// Returns a variable that is `[[var] + offset]`.
434    /// `var` must be a cell reference, or a cell ref plus a small constant.
435    pub fn double_deref(&mut self, var: Var, offset: i16) -> Var {
436        let (cell, full_offset) = self.as_cell_ref_plus_const(var, offset, false);
437        self.add_var(CellExpression::DoubleDeref(cell, full_offset))
438    }
439
440    /// Sets the label to have the set states, otherwise tests if the state matches the existing one
441    /// by merging.
442    fn set_or_test_label_state(&mut self, label: String, state: State) {
443        match self.label_state.entry(label) {
444            Entry::Occupied(e) => {
445                let read_only = self.read_labels.contains(e.key());
446                e.into_mut().intersect(&state, read_only);
447            }
448            Entry::Vacant(e) => {
449                e.insert(state);
450            }
451        }
452    }
453
454    /// Add a statement to jump to `label`.
455    pub fn jump(&mut self, label: String) {
456        let instruction = self.next_instruction(
457            InstructionBody::Jump(JumpInstruction {
458                target: deref_or_immediate!(0),
459                relative: true,
460            }),
461            true,
462        );
463        self.statements.push(Statement::Jump(label.clone(), instruction));
464        let mut state = State::default();
465        core::mem::swap(&mut state, &mut self.main_state);
466        self.set_or_test_label_state(label, state);
467        self.reachable = false;
468    }
469
470    /// Add a statement to jump to `label` if `condition != 0`.
471    /// `condition` must be a cell reference.
472    pub fn jump_nz(&mut self, condition: Var, label: String) {
473        let cell = self.as_cell_ref(condition, true);
474        let instruction = self.next_instruction(
475            InstructionBody::Jnz(JnzInstruction {
476                condition: cell,
477                jump_offset: deref_or_immediate!(0),
478            }),
479            true,
480        );
481        self.statements.push(Statement::Jump(label.clone(), instruction));
482        self.set_or_test_label_state(label, self.main_state.clone());
483    }
484
485    /// Adds a label here named `name`.
486    pub fn label(&mut self, name: String) {
487        if self.reachable {
488            self.set_or_test_label_state(name.clone(), self.main_state.clone());
489        }
490        self.read_labels.insert(name.clone());
491        self.main_state = self
492            .label_state
493            .get(&name)
494            .unwrap_or_else(|| panic!("No known value for state on reaching {name}."))
495            .clone();
496        self.statements.push(Statement::Label(name, 0));
497        self.reachable = true;
498    }
499
500    /// Adds a label `name` in distance `offset` from the current point.
501    /// Useful for calling code outside of the builder's context.
502    pub fn future_label(&mut self, name: String, offset: usize) {
503        self.statements.push(Statement::Label(name, offset));
504    }
505
506    /// Rescoping the values, while ignoring all vars not stated in `vars` and giving the vars on
507    /// the left side the values of the vars on the right side.
508    pub fn rescope<const VAR_COUNT: usize>(&mut self, vars: [(Var, Var); VAR_COUNT]) {
509        self.main_state.validate_finality();
510        let values =
511            vars.map(|(new_var, value_var)| (new_var, self.main_state.get_adjusted(value_var)));
512        self.main_state.ap_change = 0;
513        self.main_state.allocated = 0;
514        self.main_state.vars.clear();
515        self.main_state.vars.extend(values);
516    }
517
518    /// Adds a call command to 'label'. All AP based variables are passed to the called function
519    /// state and dropped from the calling function state.
520    pub fn call(&mut self, label: String) {
521        self.main_state.validate_finality();
522        // Vars to be passed to the called function state.
523        let mut function_vars = OrderedHashMap::<Var, CellExpression>::default();
524        // FP based vars which will remain in the current state.
525        let mut main_vars = OrderedHashMap::<Var, CellExpression>::default();
526        let ap_change = self.main_state.ap_change;
527        let cell_to_var_flags = |cell: &CellRef| {
528            if cell.register == Register::AP { (true, false) } else { (false, true) }
529        };
530        for (var, value) in self.main_state.vars.iter() {
531            let (function_var, main_var) = match value {
532                CellExpression::DoubleDeref(cell, _) | CellExpression::Deref(cell) => {
533                    cell_to_var_flags(cell)
534                }
535                CellExpression::Immediate(_) => (true, true),
536                CellExpression::BinOp { op: _, a, b } => match b {
537                    DerefOrImmediate::Deref(cell) => {
538                        if a.register == cell.register {
539                            cell_to_var_flags(cell)
540                        } else {
541                            // Mixed FP and AP based, dropped from both states.
542                            (false, false)
543                        }
544                    }
545                    DerefOrImmediate::Immediate(_) => (true, true),
546                },
547            };
548            if function_var {
549                // Apply ap change (+2 because of the call statement) and change to FP based before
550                // the function call.
551                let mut value = value.clone().unchecked_apply_known_ap_change(ap_change + 2);
552                match &mut value {
553                    CellExpression::DoubleDeref(cell, _) | CellExpression::Deref(cell) => {
554                        cell.register = Register::FP
555                    }
556                    CellExpression::Immediate(_) => {}
557                    CellExpression::BinOp { a, b, .. } => {
558                        a.register = Register::FP;
559                        match b {
560                            DerefOrImmediate::Deref(cell) => cell.register = Register::FP,
561                            DerefOrImmediate::Immediate(_) => {}
562                        }
563                    }
564                }
565                function_vars.insert(*var, value);
566            }
567            if main_var {
568                main_vars.insert(*var, value.clone());
569            }
570        }
571
572        let instruction = self.next_instruction(
573            InstructionBody::Call(CallInstruction {
574                relative: true,
575                target: deref_or_immediate!(0),
576            }),
577            false,
578        );
579        self.statements.push(Statement::Jump(label.clone(), instruction));
580
581        self.main_state.vars = main_vars;
582        self.main_state.allocated = 0;
583        self.main_state.ap_change = 0;
584        let function_state = State { vars: function_vars, ..Default::default() };
585        self.set_or_test_label_state(label, function_state);
586    }
587
588    /// A return statement in the code.
589    pub fn ret(&mut self) {
590        self.main_state.validate_finality();
591        let instruction = self.next_instruction(InstructionBody::Ret(RetInstruction {}), false);
592        self.statements.push(Statement::Final(instruction));
593        self.reachable = false;
594    }
595
596    /// The number of steps at the last added statement.
597    pub fn steps(&self) -> usize {
598        self.main_state.steps
599    }
600
601    /// Resets the steps counter.
602    pub fn reset_steps(&mut self) {
603        self.main_state.steps = 0;
604    }
605
606    /// Create an assert that would always fail.
607    pub fn fail(&mut self) {
608        let cell = CellRef { offset: -1, register: Register::FP };
609        let instruction = self.next_instruction(
610            InstructionBody::AssertEq(AssertEqInstruction {
611                a: cell,
612                b: ResOperand::BinOp(BinOpOperand {
613                    op: Operation::Add,
614                    a: cell,
615                    b: DerefOrImmediate::Immediate(BigInt::one().into()),
616                }),
617            }),
618            false,
619        );
620        self.statements.push(Statement::Final(instruction));
621        self.mark_unreachable();
622    }
623
624    /// Marks the current state as unreachable.
625    /// Useful for removing bookkeeping after unsatisfiable conditions.
626    pub fn mark_unreachable(&mut self) {
627        self.reachable = false;
628    }
629
630    /// Returns `var`s value, with fixed ap if `adjust_ap` is true.
631    pub fn get_value(&self, var: Var, adjust_ap: bool) -> CellExpression {
632        if adjust_ap { self.main_state.get_adjusted(var) } else { self.main_state.get_value(var) }
633    }
634
635    /// Returns `var`s value as a cell reference, with fixed ap if `adjust_ap` is true.
636    fn as_cell_ref(&self, var: Var, adjust_ap: bool) -> CellRef {
637        extract_matches!(self.get_value(var, adjust_ap), CellExpression::Deref)
638    }
639
640    /// Returns `var`s value as a cell reference or immediate, with fixed ap if `adjust_ap` is true.
641    fn as_deref_or_imm(&self, var: Var, adjust_ap: bool) -> DerefOrImmediate {
642        match self.get_value(var, adjust_ap) {
643            CellExpression::Deref(cell) => DerefOrImmediate::Deref(cell),
644            CellExpression::Immediate(imm) => DerefOrImmediate::Immediate(imm.into()),
645            CellExpression::DoubleDeref(_, _) | CellExpression::BinOp { .. } => {
646                panic!("wrong usage.")
647            }
648        }
649    }
650
651    /// Returns `var`s value as a cell reference plus a small const offset, with fixed ap if
652    /// `adjust_ap` is true.
653    fn as_cell_ref_plus_const(
654        &self,
655        var: Var,
656        additional_offset: i16,
657        adjust_ap: bool,
658    ) -> (CellRef, i16) {
659        match self.get_value(var, adjust_ap) {
660            CellExpression::Deref(cell) => (cell, additional_offset),
661            CellExpression::BinOp {
662                op: CellOperator::Add,
663                a,
664                b: DerefOrImmediate::Immediate(imm),
665            } => (
666                a,
667                (imm.value + additional_offset).try_into().expect("Offset too large for deref."),
668            ),
669            _ => panic!("Not a valid ptr."),
670        }
671    }
672
673    /// Returns an instruction wrapping the instruction body, and updates the state.
674    /// If `inc_ap_supported` may add an `ap++` to the instruction.
675    fn next_instruction(&mut self, body: InstructionBody, inc_ap_supported: bool) -> Instruction {
676        assert!(self.reachable, "Cannot add instructions at unreachable code.");
677        let inc_ap =
678            inc_ap_supported && self.main_state.allocated as usize > self.main_state.ap_change;
679        if inc_ap {
680            self.main_state.ap_change += 1;
681        }
682        self.main_state.steps += 1;
683        let mut hints = vec![];
684        core::mem::swap(&mut hints, &mut self.current_hints);
685        Instruction { body, inc_ap, hints }
686    }
687}
688
689impl Default for CasmBuilder {
690    fn default() -> Self {
691        Self {
692            label_state: Default::default(),
693            read_labels: Default::default(),
694            main_state: Default::default(),
695            statements: Default::default(),
696            current_hints: Default::default(),
697            var_count: Default::default(),
698            reachable: true,
699        }
700    }
701}
702
703#[macro_export]
704macro_rules! casm_build_extend {
705    ($builder:ident,) => {};
706    ($builder:ident, tempvar $var:ident; $($tok:tt)*) => {
707        let $var = $builder.alloc_var(false);
708        $crate::casm_build_extend!($builder, $($tok)*)
709    };
710    ($builder:ident, localvar $var:ident; $($tok:tt)*) => {
711        let $var = $builder.alloc_var(true);
712        $crate::casm_build_extend!($builder, $($tok)*)
713    };
714    ($builder:ident, ap += $value:expr; $($tok:tt)*) => {
715        $builder.add_ap($value);
716        $crate::casm_build_extend!($builder, $($tok)*)
717    };
718    ($builder:ident, const $imm:ident = $value:expr; $($tok:tt)*) => {
719        let $imm = $builder.add_var($crate::cell_expression::CellExpression::Immediate(($value).into()));
720        $crate::casm_build_extend!($builder, $($tok)*)
721    };
722    ($builder:ident, assert $dst:ident = $res:ident; $($tok:tt)*) => {
723        $builder.assert_vars_eq($dst, $res);
724        $crate::casm_build_extend!($builder, $($tok)*)
725    };
726    ($builder:ident, assert $dst:ident = $a:ident + $b:ident; $($tok:tt)*) => {
727        {
728            let __sum = $builder.bin_op($crate::cell_expression::CellOperator::Add, $a, $b);
729            $builder.assert_vars_eq($dst, __sum);
730        }
731        $crate::casm_build_extend!($builder, $($tok)*)
732    };
733    ($builder:ident, assert $dst:ident = $a:ident * $b:ident; $($tok:tt)*) => {
734        {
735            let __product = $builder.bin_op($crate::cell_expression::CellOperator::Mul, $a, $b);
736            $builder.assert_vars_eq($dst, __product);
737        }
738        $crate::casm_build_extend!($builder, $($tok)*)
739    };
740    ($builder:ident, assert $dst:ident = $a:ident - $b:ident; $($tok:tt)*) => {
741        {
742            let __diff = $builder.bin_op($crate::cell_expression::CellOperator::Sub, $a, $b);
743            $builder.assert_vars_eq($dst, __diff);
744        }
745        $crate::casm_build_extend!($builder, $($tok)*)
746    };
747    ($builder:ident, assert $dst:ident = $a:ident / $b:ident; $($tok:tt)*) => {
748        {
749            let __division = $builder.bin_op($crate::cell_expression::CellOperator::Div, $a, $b);
750            $builder.assert_vars_eq($dst, __division);
751        }
752        $crate::casm_build_extend!($builder, $($tok)*)
753    };
754    ($builder:ident, assert $dst:ident = $buffer:ident [ $offset:expr ] ; $($tok:tt)*) => {
755        {
756            let __deref = $builder.double_deref($buffer, $offset);
757            $builder.assert_vars_eq($dst, __deref);
758        }
759        $crate::casm_build_extend!($builder, $($tok)*)
760    };
761    ($builder:ident, assert $dst:ident = * $buffer:ident; $($tok:tt)*) => {
762        {
763            let __deref = $builder.double_deref($buffer, 0);
764            $builder.assert_vars_eq($dst, __deref);
765        }
766        $crate::casm_build_extend!($builder, $($tok)*)
767    };
768    ($builder:ident, assert $value:ident = * ( $buffer:ident ++ ); $($tok:tt)*) => {
769        $builder.buffer_write_and_inc($buffer, $value);
770        $crate::casm_build_extend!($builder, $($tok)*)
771    };
772    ($builder:ident, tempvar $var:ident = $value:ident; $($tok:tt)*) => {
773        $crate::casm_build_extend!($builder, tempvar $var; assert $var = $value; $($tok)*);
774    };
775    ($builder:ident, tempvar $var:ident = $lhs:ident + $rhs:ident; $($tok:tt)*) => {
776        $crate::casm_build_extend!($builder, tempvar $var; assert $var = $lhs + $rhs; $($tok)*);
777    };
778    ($builder:ident, tempvar $var:ident = $lhs:ident * $rhs:ident; $($tok:tt)*) => {
779        $crate::casm_build_extend!($builder, tempvar $var; assert $var = $lhs * $rhs; $($tok)*);
780    };
781    ($builder:ident, 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:ident, 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:ident, tempvar $var:ident = * ( $buffer:ident ++ ); $($tok:tt)*) => {
788        $crate::casm_build_extend!($builder, tempvar $var; assert $var = *($buffer++); $($tok)*);
789    };
790    ($builder:ident, tempvar $var:ident = $buffer:ident [ $offset:expr ]; $($tok:tt)*) => {
791        $crate::casm_build_extend!($builder, tempvar $var; assert $var = $buffer[$offset]; $($tok)*);
792    };
793    ($builder:ident, tempvar $var:ident = * $buffer:ident ; $($tok:tt)*) => {
794        $crate::casm_build_extend!($builder, tempvar $var; assert $var = *$buffer; $($tok)*);
795    };
796    ($builder:ident, maybe_tempvar $var:ident = $value:ident; $($tok:tt)*) => {
797        let $var = $builder.maybe_add_tempvar($value);
798        $crate::casm_build_extend!($builder, $($tok)*);
799    };
800    ($builder:ident, maybe_tempvar $var:ident = $lhs:ident + $rhs:ident; $($tok:tt)*) => {
801        $crate::casm_build_extend! {$builder,
802            let $var = $lhs + $rhs;
803            maybe_tempvar $var = $var;
804            $($tok)*
805        };
806    };
807    ($builder:ident, maybe_tempvar $var:ident = $lhs:ident * $rhs:ident; $($tok:tt)*) => {
808        $crate::casm_build_extend! {$builder,
809            let $var = $lhs * $rhs;
810            maybe_tempvar $var = $var;
811            $($tok)*
812        };
813    };
814    ($builder:ident, maybe_tempvar $var:ident = $lhs:ident - $rhs:ident; $($tok:tt)*) => {
815        $crate::casm_build_extend! {$builder,
816            let $var = $lhs - $rhs;
817            maybe_tempvar $var = $var;
818            $($tok)*
819        };
820    };
821    ($builder:ident, maybe_tempvar $var:ident = $lhs:ident / $rhs:ident; $($tok:tt)*) => {
822        $crate::casm_build_extend! {$builder,
823            let $var = $lhs / $rhs;
824            maybe_tempvar $var = $var;
825            $($tok)*
826        };
827    };
828    ($builder:ident, localvar $var:ident = $value:ident; $($tok:tt)*) => {
829        $crate::casm_build_extend!($builder, localvar $var; assert $var = $value; $($tok)*);
830    };
831    ($builder:ident, localvar $var:ident = $lhs:ident + $rhs:ident; $($tok:tt)*) => {
832        $crate::casm_build_extend!($builder, localvar $var; assert $var = $lhs + $rhs; $($tok)*);
833    };
834    ($builder:ident, localvar $var:ident = $lhs:ident * $rhs:ident; $($tok:tt)*) => {
835        $crate::casm_build_extend!($builder, localvar $var; assert $var = $lhs * $rhs; $($tok)*);
836    };
837    ($builder:ident, 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:ident, 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:ident, localvar $var:ident = * ( $buffer:ident ++ ); $($tok:tt)*) => {
844        $crate::casm_build_extend!($builder, localvar $var; assert $var = *($buffer++); $($tok)*);
845    };
846    ($builder:ident, localvar $var:ident = $buffer:ident [ $offset:expr ]; $($tok:tt)*) => {
847        $crate::casm_build_extend!($builder, localvar $var; assert $var = $buffer[$offset]; $($tok)*);
848    };
849    ($builder:ident, localvar $var:ident = * $buffer:ident ; $($tok:tt)*) => {
850        $crate::casm_build_extend!($builder, localvar $var; assert $var = *$buffer; $($tok)*);
851    };
852    ($builder:ident, let $dst:ident = $a:ident + $b:ident; $($tok:tt)*) => {
853        let $dst = $builder.bin_op($crate::cell_expression::CellOperator::Add, $a, $b);
854        $crate::casm_build_extend!($builder, $($tok)*)
855    };
856    ($builder:ident, let $dst:ident = $a:ident * $b:ident; $($tok:tt)*) => {
857        let $dst = $builder.bin_op($crate::cell_expression::CellOperator::Mul, $a, $b);
858        $crate::casm_build_extend!($builder, $($tok)*)
859    };
860    ($builder:ident, let $dst:ident = $a:ident - $b:ident; $($tok:tt)*) => {
861        let $dst = $builder.bin_op($crate::cell_expression::CellOperator::Sub, $a, $b);
862        $crate::casm_build_extend!($builder, $($tok)*)
863    };
864    ($builder:ident, let $dst:ident = $a:ident / $b:ident; $($tok:tt)*) => {
865        let $dst = $builder.bin_op($crate::cell_expression::CellOperator::Div, $a, $b);
866        $crate::casm_build_extend!($builder, $($tok)*)
867    };
868    ($builder:ident, let $dst:ident = * ( $buffer:ident ++ ); $($tok:tt)*) => {
869        let $dst = $builder.get_ref_and_inc($buffer);
870        $crate::casm_build_extend!($builder, $($tok)*)
871    };
872    ($builder:ident, let $dst:ident = $buffer:ident [ $offset:expr ] ; $($tok:tt)*) => {
873        let $dst = $builder.double_deref($buffer, $offset);
874        $crate::casm_build_extend!($builder, $($tok)*)
875    };
876    ($builder:ident, let $dst:ident = *$buffer:ident; $($tok:tt)*) => {
877        let $dst = $builder.double_deref($buffer, 0);
878        $crate::casm_build_extend!($builder, $($tok)*)
879    };
880    ($builder:ident, let $dst:ident = $src:ident; $($tok:tt)*) => {
881        let $dst = $builder.duplicate_var($src);
882        $crate::casm_build_extend!($builder, $($tok)*)
883    };
884    ($builder:ident, jump $target:ident; $($tok:tt)*) => {
885        $builder.jump($crate::builder::ToOwned::to_owned(core::stringify!($target)));
886        $crate::casm_build_extend!($builder, $($tok)*)
887    };
888    ($builder:ident, jump $target:ident if $condition:ident != 0; $($tok:tt)*) => {
889        $builder.jump_nz($condition, $crate::builder::ToOwned::to_owned(core::stringify!($target)));
890        $crate::casm_build_extend!($builder, $($tok)*)
891    };
892    ($builder:ident, let ($($var_name:ident),*) = call $target:ident; $($tok:tt)*) => {
893        $builder.call($crate::builder::ToOwned::to_owned(core::stringify!($target)));
894
895        let __var_count = {0i16 $(+ (stringify!($var_name), 1i16).1)*};
896        let mut __var_index = 0;
897        $(
898            let $var_name = $builder.add_var($crate::cell_expression::CellExpression::Deref($crate::operand::CellRef {
899                offset: __var_index - __var_count,
900                register: $crate::operand::Register::AP,
901            }));
902            __var_index += 1;
903        )*
904        $crate::casm_build_extend!($builder, $($tok)*)
905    };
906    ($builder:ident, ret; $($tok:tt)*) => {
907        $builder.ret();
908        $crate::casm_build_extend!($builder, $($tok)*)
909    };
910    ($builder:ident, $label:ident: $($tok:tt)*) => {
911        $builder.label($crate::builder::ToOwned::to_owned(core::stringify!($label)));
912        $crate::casm_build_extend!($builder, $($tok)*)
913    };
914    ($builder:ident, fail; $($tok:tt)*) => {
915        $builder.fail();
916        $crate::casm_build_extend!($builder, $($tok)*)
917    };
918    ($builder:ident, unsatisfiable_assert $dst:ident = $res:ident; $($tok:tt)*) => {
919        $crate::casm_build_extend!($builder, assert $dst = $res;);
920        $builder.mark_unreachable();
921        $crate::casm_build_extend!($builder, $($tok)*)
922    };
923    ($builder:ident, hint $hint_head:ident$(::$hint_tail:ident)+ {
924            $($input_name:ident $(: $input_value:ident)?),*
925        } into {
926            $($output_name:ident $(: $output_value:ident)?),*
927        }; $($tok:tt)*) => {
928        $builder.add_hint(
929            |[$($input_name),*], [$($output_name),*]| $hint_head$(::$hint_tail)+ {
930                $($input_name,)* $($output_name,)*
931            },
932            [$($crate::casm_build_hint_param_value!($input_name  $(: $input_value)?),)*],
933            [$($crate::casm_build_hint_param_value!($output_name  $(: $output_value)?),)*],
934        );
935        $crate::casm_build_extend!($builder, $($tok)*)
936    };
937    ($builder:ident, hint $hint_name:ident { $($inputs:tt)* } into { $($outputs:tt)* }; $($tok:tt)*) => {
938        $crate::casm_build_extend! {$builder,
939            hint $crate::hints::CoreHint::$hint_name { $($inputs)* } into { $($outputs)* };
940            $($tok)*
941        }
942    };
943    ($builder:ident, hint $hint_head:ident$(::$hint_tail:ident)* { $($inputs:tt)* }; $($tok:tt)*) => {
944        $crate::casm_build_extend! {$builder,
945            hint $hint_head$(::$hint_tail)* { $($inputs)* } into {};
946            $($tok)*
947        }
948    };
949    ($builder:ident, hint $hint_head:ident$(::$hint_tail:ident)* into { $($outputs:tt)* }; $($tok:tt)*) => {
950        $crate::casm_build_extend! {$builder,
951            hint $hint_head$(::$hint_tail)* {} into { $($outputs)* };
952            $($tok)*
953        }
954    };
955    ($builder:ident, rescope { $($new_var:ident = $value_var:ident),* }; $($tok:tt)*) => {
956        $builder.rescope([$(($new_var, $value_var)),*]);
957        $crate::casm_build_extend!($builder, $($tok)*)
958    };
959    ($builder:ident, #{ validate steps == $count:expr; } $($tok:tt)*) => {
960        assert_eq!($builder.steps(), $count);
961        $crate::casm_build_extend!($builder, $($tok)*)
962    };
963    ($builder:ident, #{ steps = 0; } $($tok:tt)*) => {
964        $builder.reset_steps();
965        $crate::casm_build_extend!($builder, $($tok)*)
966    };
967    ($builder:ident, #{ $counter:ident += steps; steps = 0; } $($tok:tt)*) => {
968        $counter += $builder.steps() as i32;
969        $builder.reset_steps();
970        $crate::casm_build_extend!($builder, $($tok)*)
971    };
972}
973
974#[macro_export]
975macro_rules! casm_build_hint_param_value {
976    ($_name:ident : $value:ident) => {
977        $value
978    };
979    ($name:ident) => {
980        $name
981    };
982}
cairo_lang_casm/builder.rs

cairo_lang_casm/
builder.rs
