openvm_native_compiler/ir/
types.rs

Help
1use alloc::{format, rc::Rc};
2use core::marker::PhantomData;
3use std::{cell::RefCell, collections::HashMap, hash::Hash};
4
5use openvm_stark_backend::p3_field::{
6    ExtensionField, Field, FieldAlgebra, FieldExtensionAlgebra, PrimeField,
7};
8use serde::{Deserialize, Serialize};
9
10use super::{
11    utils::prime_field_to_usize, Builder, Config, DslIr, ExtConst, FromConstant, MemIndex,
12    MemVariable, Ptr, RVar, SymbolicExt, SymbolicFelt, SymbolicVar, Variable,
13};
14
15/// A variable that represents a native field element.
16///
17/// Used for counters, simple loops, etc.
18#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
19pub struct Var<N>(pub u32, pub PhantomData<N>);
20
21/// A variable that represents an emulated field element.
22///
23/// Used to do field arithmetic for recursive verification.
24#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
25pub struct Felt<F>(pub u32, pub PhantomData<F>);
26
27/// A variable that represents an emulated extension field element.
28///
29/// Used to do extension field arithmetic for recursive verification.
30#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash, Serialize, Deserialize)]
31pub struct Ext<F, EF>(pub u32, pub PhantomData<(F, EF)>);
32
33/// A variable that represents either a constant or variable counter.
34#[derive(Debug, Clone, PartialEq, Eq, Serialize, Deserialize)]
35pub enum Usize<N> {
36    /// A compile time variable. It should only be used in static mode.
37    Const(Rc<RefCell<N>>),
38    Var(Var<N>),
39}
40
41#[derive(Debug, Clone, Default, Serialize, Deserialize)]
42pub struct Witness<C: Config> {
43    pub vars: Vec<C::N>,
44    pub felts: Vec<C::F>,
45    pub exts: Vec<C::EF>,
46}
47
48impl<C: Config> Witness<C> {
49    pub fn size(&self) -> usize {
50        self.vars.len() + self.felts.len() + self.exts.len() + 2
51    }
52}
53
54#[derive(Debug, Clone, Copy)]
55pub enum WitnessRef {
56    Var(u32),
57    Felt(u32),
58    Ext(u32),
59}
60
61impl<N> From<Var<N>> for WitnessRef {
62    fn from(var: Var<N>) -> Self {
63        Self::Var(var.0)
64    }
65}
66
67impl<F> From<Felt<F>> for WitnessRef {
68    fn from(felt: Felt<F>) -> Self {
69        Self::Felt(felt.0)
70    }
71}
72
73impl<F, EF> From<Ext<F, EF>> for WitnessRef {
74    fn from(ext: Ext<F, EF>) -> Self {
75        Self::Ext(ext.0)
76    }
77}
78
79impl<N> From<WitnessRef> for Var<N> {
80    fn from(witness_ref: WitnessRef) -> Self {
81        match witness_ref {
82            WitnessRef::Var(id) => Var(id, Default::default()),
83            _ => panic!("Type doesn't match!"),
84        }
85    }
86}
87impl<F> From<WitnessRef> for Felt<F> {
88    fn from(witness_ref: WitnessRef) -> Self {
89        match witness_ref {
90            WitnessRef::Felt(id) => Felt(id, Default::default()),
91            _ => panic!("Type doesn't match!"),
92        }
93    }
94}
95
96impl<F, EF> From<WitnessRef> for Ext<F, EF> {
97    fn from(witness_ref: WitnessRef) -> Self {
98        match witness_ref {
99            WitnessRef::Ext(id) => Ext(id, Default::default()),
100            _ => panic!("Type doesn't match!"),
101        }
102    }
103}
104
105impl<N: PrimeField> Usize<N> {
106    pub fn is_const(&self) -> bool {
107        match self {
108            Usize::Const(_) => true,
109            Usize::Var(_) => false,
110        }
111    }
112
113    pub fn value(&self) -> usize {
114        match self {
115            Usize::Const(c) => prime_field_to_usize(*c.borrow()),
116            Usize::Var(_) => panic!("Cannot get the value of a variable"),
117        }
118    }
119
120    pub fn get_var(&self) -> Var<N> {
121        match self {
122            Usize::Const(_) => panic!("Cannot get the variable of a constant"),
123            Usize::Var(v) => *v,
124        }
125    }
126
127    pub fn from_field(value: N) -> Self {
128        Usize::Const(Rc::new(RefCell::new(value)))
129    }
130}
131
132impl<N: PrimeField> From<Var<N>> for Usize<N> {
133    fn from(v: Var<N>) -> Self {
134        Usize::Var(v)
135    }
136}
137
138impl<N: PrimeField> From<usize> for Usize<N> {
139    fn from(c: usize) -> Self {
140        Usize::Const(Rc::new(RefCell::new(N::from_canonical_usize(c))))
141    }
142}
143
144impl<N: PrimeField> From<Usize<N>> for RVar<N> {
145    fn from(u: Usize<N>) -> Self {
146        match u {
147            Usize::Const(c) => RVar::Const(*c.borrow()),
148            Usize::Var(v) => RVar::Val(v),
149        }
150    }
151}
152
153impl<N> Var<N> {
154    pub const fn new(id: u32) -> Self {
155        Self(id, PhantomData)
156    }
157
158    pub fn id(&self) -> String {
159        format!("var{}", self.0)
160    }
161
162    pub fn loc(&self) -> String {
163        self.0.to_string()
164    }
165}
166
167impl<F> Felt<F> {
168    pub const fn new(id: u32) -> Self {
169        Self(id, PhantomData)
170    }
171
172    pub fn id(&self) -> String {
173        format!("felt{}", self.0)
174    }
175
176    pub fn loc(&self) -> String {
177        self.0.to_string()
178    }
179
180    pub fn inverse(&self) -> SymbolicFelt<F>
181    where
182        F: Field,
183    {
184        SymbolicFelt::<F>::ONE / *self
185    }
186}
187
188impl<F, EF> Ext<F, EF> {
189    pub const fn new(id: u32) -> Self {
190        Self(id, PhantomData)
191    }
192
193    pub fn id(&self) -> String {
194        format!("ext{}", self.0)
195    }
196
197    pub fn loc(&self) -> String {
198        self.0.to_string()
199    }
200
201    pub fn inverse(&self) -> SymbolicExt<F, EF>
202    where
203        F: Field,
204        EF: ExtensionField<F>,
205    {
206        SymbolicExt::<F, EF>::ONE / *self
207    }
208}
209
210impl<C: Config> Variable<C> for Usize<C::N> {
211    type Expression = SymbolicVar<C::N>;
212
213    fn uninit(builder: &mut Builder<C>) -> Self {
214        if builder.flags.static_only {
215            Usize::Const(Rc::new(RefCell::new(C::N::ZERO)))
216        } else {
217            builder.uninit::<Var<C::N>>().into()
218        }
219    }
220
221    fn assign(&self, src: Self::Expression, builder: &mut Builder<C>) {
222        match self {
223            Usize::Const(c) => {
224                *c.borrow_mut() = if let SymbolicVar::Const(c, _) = src {
225                    if !builder.is_sub_builder {
226                        c
227                    } else {
228                        panic!("cannot assign Usize::Const inside a closure")
229                    }
230                } else {
231                    panic!("cannot assign Usize::Const with a variable")
232                }
233            }
234            Usize::Var(v) => {
235                builder.assign(v, src);
236            }
237        }
238    }
239
240    fn assert_eq(
241        lhs: impl Into<Self::Expression>,
242        rhs: impl Into<Self::Expression>,
243        builder: &mut Builder<C>,
244    ) {
245        Var::<C::N>::assert_eq(lhs, rhs, builder);
246    }
247
248    fn eval(builder: &mut Builder<C>, expr: impl Into<Self::Expression>) -> Self {
249        let expr = expr.into();
250        match expr {
251            SymbolicVar::Const(c, _) => {
252                // Usize::Const should only be used in static mode.
253                if builder.flags.static_only {
254                    Usize::from_field(c)
255                } else {
256                    Usize::Var(builder.eval(c))
257                }
258            }
259            _ => Usize::Var(builder.eval(expr)),
260        }
261    }
262}
263
264impl<N: Field> Var<N> {
265    fn assign_with_cache<C: Config<N = N>>(
266        &self,
267        src: SymbolicVar<N>,
268        builder: &mut Builder<C>,
269        cache: &mut HashMap<SymbolicVar<N>, Self>,
270    ) {
271        if let Some(v) = cache.get(&src) {
272            builder.operations.push(DslIr::AddVI(*self, *v, C::N::ZERO));
273            return;
274        }
275        match src {
276            SymbolicVar::Const(c, _) => {
277                builder.operations.push(DslIr::ImmV(*self, c));
278            }
279            SymbolicVar::Val(v, _) => {
280                builder.operations.push(DslIr::AddVI(*self, v, C::N::ZERO));
281            }
282            SymbolicVar::Add(lhs, rhs, _) => match (&*lhs, &*rhs) {
283                (SymbolicVar::Const(lhs, _), SymbolicVar::Const(rhs, _)) => {
284                    let sum = *lhs + *rhs;
285                    builder.operations.push(DslIr::ImmV(*self, sum));
286                }
287                (SymbolicVar::Const(lhs, _), SymbolicVar::Val(rhs, _)) => {
288                    builder.operations.push(DslIr::AddVI(*self, *rhs, *lhs));
289                }
290                (SymbolicVar::Const(lhs, _), rhs) => {
291                    let rhs_value = Self::uninit(builder);
292                    rhs_value.assign(rhs.clone(), builder);
293                    builder.push(DslIr::AddVI(*self, rhs_value, *lhs));
294                }
295                (SymbolicVar::Val(lhs, _), SymbolicVar::Const(rhs, _)) => {
296                    builder.push(DslIr::AddVI(*self, *lhs, *rhs));
297                }
298                (SymbolicVar::Val(lhs, _), SymbolicVar::Val(rhs, _)) => {
299                    builder.push(DslIr::AddV(*self, *lhs, *rhs));
300                }
301                (SymbolicVar::Val(lhs, _), rhs) => {
302                    let rhs_value = Self::uninit(builder);
303                    rhs_value.assign(rhs.clone(), builder);
304                    builder.push(DslIr::AddV(*self, *lhs, rhs_value));
305                }
306                (lhs, SymbolicVar::Const(rhs, _)) => {
307                    let lhs_value = Self::uninit(builder);
308                    lhs_value.assign(lhs.clone(), builder);
309                    builder.push(DslIr::AddVI(*self, lhs_value, *rhs));
310                }
311                (lhs, SymbolicVar::Val(rhs, _)) => {
312                    let lhs_value = Self::uninit(builder);
313                    lhs_value.assign(lhs.clone(), builder);
314                    builder.push(DslIr::AddV(*self, lhs_value, *rhs));
315                }
316                (lhs, rhs) => {
317                    let lhs_value = Self::uninit(builder);
318                    lhs_value.assign_with_cache(lhs.clone(), builder, cache);
319                    cache.insert(lhs.clone(), lhs_value);
320                    let rhs_value = Self::uninit(builder);
321                    rhs_value.assign_with_cache(rhs.clone(), builder, cache);
322                    cache.insert(rhs.clone(), rhs_value);
323                    builder.push(DslIr::AddV(*self, lhs_value, rhs_value));
324                }
325            },
326            SymbolicVar::Mul(lhs, rhs, _) => match (&*lhs, &*rhs) {
327                (SymbolicVar::Const(lhs, _), SymbolicVar::Const(rhs, _)) => {
328                    let product = *lhs * *rhs;
329                    builder.push(DslIr::ImmV(*self, product));
330                }
331                (SymbolicVar::Const(lhs, _), SymbolicVar::Val(rhs, _)) => {
332                    builder.push(DslIr::MulVI(*self, *rhs, *lhs));
333                }
334                (SymbolicVar::Const(lhs, _), rhs) => {
335                    let rhs_value = Self::uninit(builder);
336                    rhs_value.assign_with_cache(rhs.clone(), builder, cache);
337                    cache.insert(rhs.clone(), rhs_value);
338                    builder.push(DslIr::MulVI(*self, rhs_value, *lhs));
339                }
340                (SymbolicVar::Val(lhs, _), SymbolicVar::Const(rhs, _)) => {
341                    builder.push(DslIr::MulVI(*self, *lhs, *rhs));
342                }
343                (SymbolicVar::Val(lhs, _), SymbolicVar::Val(rhs, _)) => {
344                    builder.push(DslIr::MulV(*self, *lhs, *rhs));
345                }
346                (SymbolicVar::Val(lhs, _), rhs) => {
347                    let rhs_value = Self::uninit(builder);
348                    rhs_value.assign_with_cache(rhs.clone(), builder, cache);
349                    cache.insert(rhs.clone(), rhs_value);
350                    builder.push(DslIr::MulV(*self, *lhs, rhs_value));
351                }
352                (lhs, SymbolicVar::Const(rhs, _)) => {
353                    let lhs_value = Self::uninit(builder);
354                    lhs_value.assign_with_cache(lhs.clone(), builder, cache);
355                    cache.insert(lhs.clone(), lhs_value);
356                    builder.push(DslIr::MulVI(*self, lhs_value, *rhs));
357                }
358                (lhs, SymbolicVar::Val(rhs, _)) => {
359                    let lhs_value = Self::uninit(builder);
360                    lhs_value.assign_with_cache(lhs.clone(), builder, cache);
361                    cache.insert(lhs.clone(), lhs_value);
362                    builder.push(DslIr::MulV(*self, lhs_value, *rhs));
363                }
364                (lhs, rhs) => {
365                    let lhs_value = Self::uninit(builder);
366                    lhs_value.assign_with_cache(lhs.clone(), builder, cache);
367                    cache.insert(lhs.clone(), lhs_value);
368                    let rhs_value = Self::uninit(builder);
369                    rhs_value.assign_with_cache(rhs.clone(), builder, cache);
370                    cache.insert(rhs.clone(), rhs_value);
371                    builder.push(DslIr::MulV(*self, lhs_value, rhs_value));
372                }
373            },
374            SymbolicVar::Sub(lhs, rhs, _) => match (&*lhs, &*rhs) {
375                (SymbolicVar::Const(lhs, _), SymbolicVar::Const(rhs, _)) => {
376                    let difference = *lhs - *rhs;
377                    builder.push(DslIr::ImmV(*self, difference));
378                }
379                (SymbolicVar::Const(lhs, _), SymbolicVar::Val(rhs, _)) => {
380                    builder.push(DslIr::SubVIN(*self, *lhs, *rhs));
381                }
382                (SymbolicVar::Const(lhs, _), rhs) => {
383                    let rhs_value = Self::uninit(builder);
384                    rhs_value.assign_with_cache(rhs.clone(), builder, cache);
385                    cache.insert(rhs.clone(), rhs_value);
386                    builder.push(DslIr::SubVIN(*self, *lhs, rhs_value));
387                }
388                (SymbolicVar::Val(lhs, _), SymbolicVar::Const(rhs, _)) => {
389                    builder.push(DslIr::SubVI(*self, *lhs, *rhs));
390                }
391                (SymbolicVar::Val(lhs, _), SymbolicVar::Val(rhs, _)) => {
392                    builder.push(DslIr::SubV(*self, *lhs, *rhs));
393                }
394                (SymbolicVar::Val(lhs, _), rhs) => {
395                    let rhs_value = Self::uninit(builder);
396                    rhs_value.assign_with_cache(rhs.clone(), builder, cache);
397                    cache.insert(rhs.clone(), rhs_value);
398                    builder.push(DslIr::SubV(*self, *lhs, rhs_value));
399                }
400                (lhs, SymbolicVar::Const(rhs, _)) => {
401                    let lhs_value = Self::uninit(builder);
402                    lhs_value.assign_with_cache(lhs.clone(), builder, cache);
403                    cache.insert(lhs.clone(), lhs_value);
404                    builder.push(DslIr::SubVI(*self, lhs_value, *rhs));
405                }
406                (lhs, SymbolicVar::Val(rhs, _)) => {
407                    let lhs_value = Self::uninit(builder);
408                    lhs_value.assign_with_cache(lhs.clone(), builder, cache);
409                    cache.insert(lhs.clone(), lhs_value);
410                    builder.push(DslIr::SubV(*self, lhs_value, *rhs));
411                }
412                (lhs, rhs) => {
413                    let lhs_value = Self::uninit(builder);
414                    lhs_value.assign_with_cache(lhs.clone(), builder, cache);
415                    cache.insert(lhs.clone(), lhs_value);
416                    let rhs_value = Self::uninit(builder);
417                    rhs_value.assign_with_cache(rhs.clone(), builder, cache);
418                    cache.insert(rhs.clone(), rhs_value);
419                    builder.push(DslIr::SubV(*self, lhs_value, rhs_value));
420                }
421            },
422            SymbolicVar::Neg(operand, _) => match &*operand {
423                SymbolicVar::Const(operand, _) => {
424                    let negated = -*operand;
425                    builder.push(DslIr::ImmV(*self, negated));
426                }
427                SymbolicVar::Val(operand, _) => {
428                    builder.push(DslIr::SubVIN(*self, C::N::ZERO, *operand));
429                }
430                operand => {
431                    let operand_value = Self::uninit(builder);
432                    operand_value.assign_with_cache(operand.clone(), builder, cache);
433                    cache.insert(operand.clone(), operand_value);
434                    builder.push(DslIr::SubVIN(*self, C::N::ZERO, operand_value));
435                }
436            },
437        }
438    }
439}
440
441impl<C: Config> Variable<C> for Var<C::N> {
442    type Expression = SymbolicVar<C::N>;
443
444    fn uninit(builder: &mut Builder<C>) -> Self {
445        builder.var_count += 1;
446        Var(builder.var_count, PhantomData)
447    }
448
449    fn assign(&self, src: Self::Expression, builder: &mut Builder<C>) {
450        self.assign_with_cache(src, builder, &mut HashMap::new());
451    }
452
453    fn assert_eq(
454        lhs: impl Into<Self::Expression>,
455        rhs: impl Into<Self::Expression>,
456        builder: &mut Builder<C>,
457    ) {
458        let lhs = lhs.into();
459        let rhs = rhs.into();
460
461        match (lhs, rhs) {
462            (SymbolicVar::Const(lhs, _), SymbolicVar::Const(rhs, _)) => {
463                assert_eq!(lhs, rhs, "Assertion failed at compile time");
464            }
465            (SymbolicVar::Const(lhs, _), SymbolicVar::Val(rhs, _)) => {
466                builder.trace_push(DslIr::AssertEqVI(rhs, lhs));
467            }
468            (SymbolicVar::Const(lhs, _), rhs) => {
469                let rhs_value = Self::uninit(builder);
470                rhs_value.assign(rhs, builder);
471                builder.trace_push(DslIr::AssertEqVI(rhs_value, lhs));
472            }
473            (SymbolicVar::Val(lhs, _), SymbolicVar::Const(rhs, _)) => {
474                builder.trace_push(DslIr::AssertEqVI(lhs, rhs));
475            }
476            (SymbolicVar::Val(lhs, _), SymbolicVar::Val(rhs, _)) => {
477                builder.trace_push(DslIr::AssertEqV(lhs, rhs));
478            }
479            (SymbolicVar::Val(lhs, _), rhs) => {
480                let rhs_value = Self::uninit(builder);
481                rhs_value.assign(rhs, builder);
482                builder.trace_push(DslIr::AssertEqV(lhs, rhs_value));
483            }
484            (lhs, rhs) => {
485                let lhs_value = Self::uninit(builder);
486                lhs_value.assign(lhs, builder);
487                let rhs_value = Self::uninit(builder);
488                rhs_value.assign(rhs, builder);
489                builder.trace_push(DslIr::AssertEqV(lhs_value, rhs_value));
490            }
491        }
492    }
493}
494
495impl<C: Config> MemVariable<C> for Var<C::N> {
496    fn size_of() -> usize {
497        1
498    }
499
500    fn load(&self, ptr: Ptr<C::N>, index: MemIndex<C::N>, builder: &mut Builder<C>) {
501        builder.push(DslIr::LoadV(*self, ptr, index));
502    }
503
504    fn store(&self, ptr: Ptr<<C as Config>::N>, index: MemIndex<C::N>, builder: &mut Builder<C>) {
505        builder.push(DslIr::StoreV(*self, ptr, index));
506    }
507}
508
509impl<C: Config> MemVariable<C> for Usize<C::N> {
510    fn size_of() -> usize {
511        1
512    }
513
514    fn load(&self, ptr: Ptr<C::N>, index: MemIndex<C::N>, builder: &mut Builder<C>) {
515        match self {
516            Usize::Const(_) => {
517                panic!("Usize::Const should not be loaded");
518            }
519            Usize::Var(v) => {
520                builder.push(DslIr::LoadV(*v, ptr, index));
521            }
522        }
523    }
524
525    fn store(&self, ptr: Ptr<<C as Config>::N>, index: MemIndex<C::N>, builder: &mut Builder<C>) {
526        match self {
527            Usize::Const(_) => {
528                panic!("Usize::Const should not be stored");
529            }
530            Usize::Var(v) => {
531                builder.push(DslIr::StoreV(*v, ptr, index));
532            }
533        }
534    }
535}
536
537impl<F: Field> Felt<F> {
538    fn assign_with_cache<C: Config<F = F>>(
539        &self,
540        src: SymbolicFelt<F>,
541        builder: &mut Builder<C>,
542        cache: &mut HashMap<SymbolicFelt<F>, Self>,
543    ) {
544        if let Some(v) = cache.get(&src) {
545            builder.operations.push(DslIr::AddFI(*self, *v, C::F::ZERO));
546            return;
547        }
548        match src {
549            SymbolicFelt::Const(c, _) => {
550                builder.operations.push(DslIr::ImmF(*self, c));
551            }
552            SymbolicFelt::Val(v, _) => {
553                builder.operations.push(DslIr::AddFI(*self, v, C::F::ZERO));
554            }
555            SymbolicFelt::Add(lhs, rhs, _) => match (&*lhs, &*rhs) {
556                (SymbolicFelt::Const(lhs, _), SymbolicFelt::Const(rhs, _)) => {
557                    let sum = *lhs + *rhs;
558                    builder.operations.push(DslIr::ImmF(*self, sum));
559                }
560                (SymbolicFelt::Const(lhs, _), SymbolicFelt::Val(rhs, _)) => {
561                    builder.operations.push(DslIr::AddFI(*self, *rhs, *lhs));
562                }
563                (SymbolicFelt::Const(lhs, _), rhs) => {
564                    let rhs_value = Self::uninit(builder);
565                    rhs_value.assign_with_cache(rhs.clone(), builder, cache);
566                    cache.insert(rhs.clone(), rhs_value);
567                    builder.push(DslIr::AddFI(*self, rhs_value, *lhs));
568                }
569                (SymbolicFelt::Val(lhs, _), SymbolicFelt::Const(rhs, _)) => {
570                    builder.push(DslIr::AddFI(*self, *lhs, *rhs));
571                }
572                (SymbolicFelt::Val(lhs, _), SymbolicFelt::Val(rhs, _)) => {
573                    builder.push(DslIr::AddF(*self, *lhs, *rhs));
574                }
575                (SymbolicFelt::Val(lhs, _), rhs) => {
576                    let rhs_value = Self::uninit(builder);
577                    rhs_value.assign_with_cache(rhs.clone(), builder, cache);
578                    cache.insert(rhs.clone(), rhs_value);
579                    builder.push(DslIr::AddF(*self, *lhs, rhs_value));
580                }
581                (lhs, SymbolicFelt::Const(rhs, _)) => {
582                    let lhs_value = Self::uninit(builder);
583                    lhs_value.assign_with_cache(lhs.clone(), builder, cache);
584                    cache.insert(lhs.clone(), lhs_value);
585                    builder.push(DslIr::AddFI(*self, lhs_value, *rhs));
586                }
587                (lhs, SymbolicFelt::Val(rhs, _)) => {
588                    let lhs_value = Self::uninit(builder);
589                    lhs_value.assign_with_cache(lhs.clone(), builder, cache);
590                    cache.insert(lhs.clone(), lhs_value);
591                    builder.push(DslIr::AddF(*self, lhs_value, *rhs));
592                }
593                (lhs, rhs) => {
594                    let lhs_value = Self::uninit(builder);
595                    lhs_value.assign_with_cache(lhs.clone(), builder, cache);
596                    cache.insert(lhs.clone(), lhs_value);
597                    let rhs_value = Self::uninit(builder);
598                    rhs_value.assign_with_cache(rhs.clone(), builder, cache);
599                    cache.insert(rhs.clone(), rhs_value);
600                    builder.push(DslIr::AddF(*self, lhs_value, rhs_value));
601                }
602            },
603            SymbolicFelt::Mul(lhs, rhs, _) => match (&*lhs, &*rhs) {
604                (SymbolicFelt::Const(lhs, _), SymbolicFelt::Const(rhs, _)) => {
605                    let product = *lhs * *rhs;
606                    builder.push(DslIr::ImmF(*self, product));
607                }
608                (SymbolicFelt::Const(lhs, _), SymbolicFelt::Val(rhs, _)) => {
609                    builder.push(DslIr::MulFI(*self, *rhs, *lhs));
610                }
611                (SymbolicFelt::Const(lhs, _), rhs) => {
612                    let rhs_value = Self::uninit(builder);
613                    rhs_value.assign_with_cache(rhs.clone(), builder, cache);
614                    cache.insert(rhs.clone(), rhs_value);
615                    builder.push(DslIr::MulFI(*self, rhs_value, *lhs));
616                }
617                (SymbolicFelt::Val(lhs, _), SymbolicFelt::Const(rhs, _)) => {
618                    builder.push(DslIr::MulFI(*self, *lhs, *rhs));
619                }
620                (SymbolicFelt::Val(lhs, _), SymbolicFelt::Val(rhs, _)) => {
621                    builder.push(DslIr::MulF(*self, *lhs, *rhs));
622                }
623                (SymbolicFelt::Val(lhs, _), rhs) => {
624                    let rhs_value = Self::uninit(builder);
625                    rhs_value.assign_with_cache(rhs.clone(), builder, cache);
626                    cache.insert(rhs.clone(), rhs_value);
627                    builder.push(DslIr::MulF(*self, *lhs, rhs_value));
628                }
629                (lhs, SymbolicFelt::Const(rhs, _)) => {
630                    let lhs_value = Self::uninit(builder);
631                    lhs_value.assign_with_cache(lhs.clone(), builder, cache);
632                    cache.insert(lhs.clone(), lhs_value);
633                    builder.push(DslIr::MulFI(*self, lhs_value, *rhs));
634                }
635                (lhs, SymbolicFelt::Val(rhs, _)) => {
636                    let lhs_value = Self::uninit(builder);
637                    lhs_value.assign_with_cache(lhs.clone(), builder, cache);
638                    cache.insert(lhs.clone(), lhs_value);
639                    builder.push(DslIr::MulF(*self, lhs_value, *rhs));
640                }
641                (lhs, rhs) => {
642                    let lhs_value = Self::uninit(builder);
643                    lhs_value.assign_with_cache(lhs.clone(), builder, cache);
644                    cache.insert(lhs.clone(), lhs_value);
645                    let rhs_value = Self::uninit(builder);
646                    rhs_value.assign_with_cache(rhs.clone(), builder, cache);
647                    cache.insert(rhs.clone(), rhs_value);
648                    builder.push(DslIr::MulF(*self, lhs_value, rhs_value));
649                }
650            },
651            SymbolicFelt::Sub(lhs, rhs, _) => match (&*lhs, &*rhs) {
652                (SymbolicFelt::Const(lhs, _), SymbolicFelt::Const(rhs, _)) => {
653                    let difference = *lhs - *rhs;
654                    builder.push(DslIr::ImmF(*self, difference));
655                }
656                (SymbolicFelt::Const(lhs, _), SymbolicFelt::Val(rhs, _)) => {
657                    builder.push(DslIr::SubFIN(*self, *lhs, *rhs));
658                }
659                (SymbolicFelt::Const(lhs, _), rhs) => {
660                    let rhs_value = Self::uninit(builder);
661                    rhs_value.assign_with_cache(rhs.clone(), builder, cache);
662                    cache.insert(rhs.clone(), rhs_value);
663                    builder.push(DslIr::SubFIN(*self, *lhs, rhs_value));
664                }
665                (SymbolicFelt::Val(lhs, _), SymbolicFelt::Const(rhs, _)) => {
666                    builder.push(DslIr::SubFI(*self, *lhs, *rhs));
667                }
668                (SymbolicFelt::Val(lhs, _), SymbolicFelt::Val(rhs, _)) => {
669                    builder.push(DslIr::SubF(*self, *lhs, *rhs));
670                }
671                (SymbolicFelt::Val(lhs, _), rhs) => {
672                    let rhs_value = Self::uninit(builder);
673                    rhs_value.assign_with_cache(rhs.clone(), builder, cache);
674                    cache.insert(rhs.clone(), rhs_value);
675                    builder.push(DslIr::SubF(*self, *lhs, rhs_value));
676                }
677                (lhs, SymbolicFelt::Const(rhs, _)) => {
678                    let lhs_value = Self::uninit(builder);
679                    lhs_value.assign_with_cache(lhs.clone(), builder, cache);
680                    cache.insert(lhs.clone(), lhs_value);
681                    builder.push(DslIr::SubFI(*self, lhs_value, *rhs));
682                }
683                (lhs, SymbolicFelt::Val(rhs, _)) => {
684                    let lhs_value = Self::uninit(builder);
685                    lhs_value.assign_with_cache(lhs.clone(), builder, cache);
686                    cache.insert(lhs.clone(), lhs_value);
687                    builder.push(DslIr::SubF(*self, lhs_value, *rhs));
688                }
689                (lhs, rhs) => {
690                    let lhs_value = Self::uninit(builder);
691                    lhs_value.assign_with_cache(lhs.clone(), builder, cache);
692                    cache.insert(lhs.clone(), lhs_value);
693                    let rhs_value = Self::uninit(builder);
694                    rhs_value.assign_with_cache(rhs.clone(), builder, cache);
695                    cache.insert(rhs.clone(), rhs_value);
696                    builder.push(DslIr::SubF(*self, lhs_value, rhs_value));
697                }
698            },
699            SymbolicFelt::Div(lhs, rhs, _) => match (&*lhs, &*rhs) {
700                (SymbolicFelt::Const(lhs, _), SymbolicFelt::Const(rhs, _)) => {
701                    let quotient = *lhs / *rhs;
702                    builder.push(DslIr::ImmF(*self, quotient));
703                }
704                (SymbolicFelt::Const(lhs, _), SymbolicFelt::Val(rhs, _)) => {
705                    builder.push(DslIr::DivFIN(*self, *lhs, *rhs));
706                }
707                (SymbolicFelt::Const(lhs, _), rhs) => {
708                    let rhs_value = Self::uninit(builder);
709                    rhs_value.assign_with_cache(rhs.clone(), builder, cache);
710                    cache.insert(rhs.clone(), rhs_value);
711                    builder.push(DslIr::DivFIN(*self, *lhs, rhs_value));
712                }
713                (SymbolicFelt::Val(lhs, _), SymbolicFelt::Const(rhs, _)) => {
714                    builder.push(DslIr::DivFI(*self, *lhs, *rhs));
715                }
716                (SymbolicFelt::Val(lhs, _), SymbolicFelt::Val(rhs, _)) => {
717                    builder.push(DslIr::DivF(*self, *lhs, *rhs));
718                }
719                (SymbolicFelt::Val(lhs, _), rhs) => {
720                    let rhs_value = Self::uninit(builder);
721                    rhs_value.assign_with_cache(rhs.clone(), builder, cache);
722                    cache.insert(rhs.clone(), rhs_value);
723                    builder.push(DslIr::DivF(*self, *lhs, rhs_value));
724                }
725                (lhs, SymbolicFelt::Const(rhs, _)) => {
726                    let lhs_value = Self::uninit(builder);
727                    lhs_value.assign_with_cache(lhs.clone(), builder, cache);
728                    cache.insert(lhs.clone(), lhs_value);
729                    builder.push(DslIr::DivFI(*self, lhs_value, *rhs));
730                }
731                (lhs, SymbolicFelt::Val(rhs, _)) => {
732                    let lhs_value = Self::uninit(builder);
733                    lhs_value.assign_with_cache(lhs.clone(), builder, cache);
734                    cache.insert(lhs.clone(), lhs_value);
735                    builder.push(DslIr::DivF(*self, lhs_value, *rhs));
736                }
737                (lhs, rhs) => {
738                    let lhs_value = Self::uninit(builder);
739                    lhs_value.assign_with_cache(lhs.clone(), builder, cache);
740                    cache.insert(lhs.clone(), lhs_value);
741                    let rhs_value = Self::uninit(builder);
742                    rhs_value.assign_with_cache(rhs.clone(), builder, cache);
743                    cache.insert(rhs.clone(), rhs_value);
744                    builder.push(DslIr::DivF(*self, lhs_value, rhs_value));
745                }
746            },
747            SymbolicFelt::Neg(operand, _) => match &*operand {
748                SymbolicFelt::Const(operand, _) => {
749                    let negated = -*operand;
750                    builder.push(DslIr::ImmF(*self, negated));
751                }
752                SymbolicFelt::Val(operand, _) => {
753                    builder.push(DslIr::SubFIN(*self, C::F::ZERO, *operand));
754                }
755                operand => {
756                    let operand_value = Self::uninit(builder);
757                    operand_value.assign_with_cache(operand.clone(), builder, cache);
758                    cache.insert(operand.clone(), operand_value);
759                    builder.push(DslIr::SubFIN(*self, C::F::ZERO, operand_value));
760                }
761            },
762        }
763    }
764}
765
766impl<C: Config> Variable<C> for Felt<C::F> {
767    type Expression = SymbolicFelt<C::F>;
768
769    fn uninit(builder: &mut Builder<C>) -> Self {
770        builder.felt_count += 1;
771        Felt(builder.felt_count, PhantomData)
772    }
773
774    fn assign(&self, src: Self::Expression, builder: &mut Builder<C>) {
775        self.assign_with_cache(src, builder, &mut HashMap::new());
776    }
777
778    fn assert_eq(
779        lhs: impl Into<Self::Expression>,
780        rhs: impl Into<Self::Expression>,
781        builder: &mut Builder<C>,
782    ) {
783        let lhs = lhs.into();
784        let rhs = rhs.into();
785
786        match (lhs, rhs) {
787            (SymbolicFelt::Const(lhs, _), SymbolicFelt::Const(rhs, _)) => {
788                assert_eq!(lhs, rhs, "Assertion failed at compile time");
789            }
790            (SymbolicFelt::Const(lhs, _), SymbolicFelt::Val(rhs, _)) => {
791                builder.trace_push(DslIr::AssertEqFI(rhs, lhs));
792            }
793            (SymbolicFelt::Const(lhs, _), rhs) => {
794                let rhs_value = Self::uninit(builder);
795                rhs_value.assign(rhs, builder);
796                builder.trace_push(DslIr::AssertEqFI(rhs_value, lhs));
797            }
798            (SymbolicFelt::Val(lhs, _), SymbolicFelt::Const(rhs, _)) => {
799                builder.trace_push(DslIr::AssertEqFI(lhs, rhs));
800            }
801            (SymbolicFelt::Val(lhs, _), SymbolicFelt::Val(rhs, _)) => {
802                builder.trace_push(DslIr::AssertEqF(lhs, rhs));
803            }
804            (SymbolicFelt::Val(lhs, _), rhs) => {
805                let rhs_value = Self::uninit(builder);
806                rhs_value.assign(rhs, builder);
807                builder.trace_push(DslIr::AssertEqF(lhs, rhs_value));
808            }
809            (lhs, rhs) => {
810                let lhs_value = Self::uninit(builder);
811                lhs_value.assign(lhs, builder);
812                let rhs_value = Self::uninit(builder);
813                rhs_value.assign(rhs, builder);
814                builder.trace_push(DslIr::AssertEqF(lhs_value, rhs_value));
815            }
816        }
817    }
818}
819
820impl<C: Config> MemVariable<C> for Felt<C::F> {
821    fn size_of() -> usize {
822        1
823    }
824
825    fn load(&self, ptr: Ptr<C::N>, index: MemIndex<C::N>, builder: &mut Builder<C>) {
826        builder.push(DslIr::LoadF(*self, ptr, index));
827    }
828
829    fn store(&self, ptr: Ptr<<C as Config>::N>, index: MemIndex<C::N>, builder: &mut Builder<C>) {
830        builder.push(DslIr::StoreF(*self, ptr, index));
831    }
832}
833
834impl<F: Field, EF: ExtensionField<F>> Ext<F, EF> {
835    fn assign_with_caches<C: Config<F = F, EF = EF>>(
836        &self,
837        src: SymbolicExt<F, EF>,
838        builder: &mut Builder<C>,
839        ext_cache: &mut HashMap<SymbolicExt<F, EF>, Ext<F, EF>>,
840        base_cache: &mut HashMap<SymbolicFelt<F>, Felt<F>>,
841    ) {
842        if let Some(v) = ext_cache.get(&src) {
843            builder
844                .operations
845                .push(DslIr::AddEI(*self, *v, C::EF::ZERO));
846            return;
847        }
848        match src {
849            SymbolicExt::Base(v, _) => match &*v {
850                SymbolicFelt::Const(c, _) => {
851                    builder
852                        .operations
853                        .push(DslIr::ImmE(*self, C::EF::from_base(*c)));
854                }
855                SymbolicFelt::Val(v, _) => {
856                    builder
857                        .operations
858                        .push(DslIr::AddEFFI(*self, *v, C::EF::ZERO));
859                }
860                v => {
861                    let v_value = Felt::uninit(builder);
862                    v_value.assign(v.clone(), builder);
863                    builder.push(DslIr::AddEFFI(*self, v_value, C::EF::ZERO));
864                }
865            },
866            SymbolicExt::Const(c, _) => {
867                builder.operations.push(DslIr::ImmE(*self, c));
868            }
869            SymbolicExt::Val(v, _) => {
870                builder.operations.push(DslIr::AddEI(*self, v, C::EF::ZERO));
871            }
872            SymbolicExt::Add(lhs, rhs, _) => match (&*lhs, &*rhs) {
873                (SymbolicExt::Const(lhs, _), SymbolicExt::Const(rhs, _)) => {
874                    let sum = *lhs + *rhs;
875                    builder.operations.push(DslIr::ImmE(*self, sum));
876                }
877                (SymbolicExt::Const(lhs, _), SymbolicExt::Val(rhs, _)) => {
878                    builder.operations.push(DslIr::AddEI(*self, *rhs, *lhs));
879                }
880                (SymbolicExt::Const(lhs, _), SymbolicExt::Base(rhs, _)) => match rhs.as_ref() {
881                    SymbolicFelt::Const(rhs, _) => {
882                        let sum = *lhs + C::EF::from_base(*rhs);
883                        builder.operations.push(DslIr::ImmE(*self, sum));
884                    }
885                    SymbolicFelt::Val(rhs, _) => {
886                        builder.operations.push(DslIr::AddEFFI(*self, *rhs, *lhs));
887                    }
888                    rhs => {
889                        let rhs_value: Felt<_> = Felt::uninit(builder);
890                        rhs_value.assign_with_cache(rhs.clone(), builder, base_cache);
891                        base_cache.insert(rhs.clone(), rhs_value);
892                        builder
893                            .operations
894                            .push(DslIr::AddEFFI(*self, rhs_value, *lhs));
895                    }
896                },
897                (SymbolicExt::Const(lhs, _), rhs) => {
898                    let rhs_value = Self::uninit(builder);
899                    rhs_value.assign_with_caches(rhs.clone(), builder, ext_cache, base_cache);
900                    ext_cache.insert(rhs.clone(), rhs_value);
901                    builder.push(DslIr::AddEI(*self, rhs_value, *lhs));
902                }
903                (SymbolicExt::Val(lhs, _), SymbolicExt::Const(rhs, _)) => {
904                    builder.push(DslIr::AddEI(*self, *lhs, *rhs));
905                }
906                (SymbolicExt::Val(lhs, _), SymbolicExt::Base(rhs, _)) => match rhs.as_ref() {
907                    SymbolicFelt::Const(rhs, _) => {
908                        builder.push(DslIr::AddEFI(*self, *lhs, *rhs));
909                    }
910                    SymbolicFelt::Val(rhs, _) => {
911                        builder.push(DslIr::AddEF(*self, *lhs, *rhs));
912                    }
913                    rhs => {
914                        let rhs = builder.eval(rhs.clone());
915                        builder.push(DslIr::AddEF(*self, *lhs, rhs));
916                    }
917                },
918                (SymbolicExt::Val(lhs, _), SymbolicExt::Val(rhs, _)) => {
919                    builder.push(DslIr::AddE(*self, *lhs, *rhs));
920                }
921                (SymbolicExt::Val(lhs, _), rhs) => {
922                    let rhs_value = Self::uninit(builder);
923                    rhs_value.assign_with_caches(rhs.clone(), builder, ext_cache, base_cache);
924                    ext_cache.insert(rhs.clone(), rhs_value);
925                    builder.push(DslIr::AddE(*self, *lhs, rhs_value));
926                }
927                (lhs, SymbolicExt::Const(rhs, _)) => {
928                    let lhs_value = Self::uninit(builder);
929                    lhs_value.assign_with_caches(lhs.clone(), builder, ext_cache, base_cache);
930                    ext_cache.insert(lhs.clone(), lhs_value);
931                    builder.push(DslIr::AddEI(*self, lhs_value, *rhs));
932                }
933                (lhs, SymbolicExt::Val(rhs, _)) => {
934                    let lhs_value = Self::uninit(builder);
935                    lhs_value.assign_with_caches(lhs.clone(), builder, ext_cache, base_cache);
936                    ext_cache.insert(lhs.clone(), lhs_value);
937                    builder.push(DslIr::AddE(*self, lhs_value, *rhs));
938                }
939                (lhs, rhs) => {
940                    let lhs_value = Self::uninit(builder);
941                    lhs_value.assign_with_caches(lhs.clone(), builder, ext_cache, base_cache);
942                    ext_cache.insert(lhs.clone(), lhs_value);
943                    let rhs_value = Self::uninit(builder);
944                    rhs_value.assign_with_caches(rhs.clone(), builder, ext_cache, base_cache);
945                    ext_cache.insert(rhs.clone(), rhs_value);
946                    builder.push(DslIr::AddE(*self, lhs_value, rhs_value));
947                }
948            },
949            SymbolicExt::Mul(lhs, rhs, _) => match (&*lhs, &*rhs) {
950                (SymbolicExt::Const(lhs, _), SymbolicExt::Const(rhs, _)) => {
951                    let product = *lhs * *rhs;
952                    builder.push(DslIr::ImmE(*self, product));
953                }
954                (SymbolicExt::Const(lhs, _), SymbolicExt::Val(rhs, _)) => {
955                    builder.push(DslIr::MulEI(*self, *rhs, *lhs));
956                }
957                (SymbolicExt::Const(lhs, _), rhs) => {
958                    let rhs_value = Self::uninit(builder);
959                    rhs_value.assign_with_caches(rhs.clone(), builder, ext_cache, base_cache);
960                    ext_cache.insert(rhs.clone(), rhs_value);
961                    builder.push(DslIr::MulEI(*self, rhs_value, *lhs));
962                }
963                (SymbolicExt::Val(lhs, _), SymbolicExt::Const(rhs, _)) => {
964                    builder.push(DslIr::MulEI(*self, *lhs, *rhs));
965                }
966                (SymbolicExt::Val(lhs, _), SymbolicExt::Val(rhs, _)) => {
967                    builder.push(DslIr::MulE(*self, *lhs, *rhs));
968                }
969                (SymbolicExt::Val(lhs, _), SymbolicExt::Base(rhs, _)) => match rhs.as_ref() {
970                    SymbolicFelt::Const(rhs, _) => {
971                        builder.push(DslIr::MulEFI(*self, *lhs, *rhs));
972                    }
973                    SymbolicFelt::Val(rhs, _) => {
974                        builder.push(DslIr::MulEF(*self, *lhs, *rhs));
975                    }
976                    rhs => {
977                        let rhs = builder.eval(rhs.clone());
978                        builder.push(DslIr::MulEF(*self, *lhs, rhs));
979                    }
980                },
981                (SymbolicExt::Val(lhs, _), rhs) => {
982                    let rhs_value = Self::uninit(builder);
983                    rhs_value.assign_with_caches(rhs.clone(), builder, ext_cache, base_cache);
984                    ext_cache.insert(rhs.clone(), rhs_value);
985                    builder.push(DslIr::MulE(*self, *lhs, rhs_value));
986                }
987                (lhs, SymbolicExt::Const(rhs, _)) => {
988                    let lhs_value = Self::uninit(builder);
989                    lhs_value.assign_with_caches(lhs.clone(), builder, ext_cache, base_cache);
990                    ext_cache.insert(lhs.clone(), lhs_value);
991                    builder.push(DslIr::MulEI(*self, lhs_value, *rhs));
992                }
993                (lhs, SymbolicExt::Val(rhs, _)) => {
994                    let lhs_value = Self::uninit(builder);
995                    lhs_value.assign_with_caches(lhs.clone(), builder, ext_cache, base_cache);
996                    ext_cache.insert(lhs.clone(), lhs_value);
997                    builder.push(DslIr::MulE(*self, lhs_value, *rhs));
998                }
999                (lhs, rhs) => {
1000                    let lhs_value = Self::uninit(builder);
1001                    lhs_value.assign_with_caches(lhs.clone(), builder, ext_cache, base_cache);
1002                    ext_cache.insert(lhs.clone(), lhs_value);
1003                    let rhs_value = Self::uninit(builder);
1004                    rhs_value.assign_with_caches(rhs.clone(), builder, ext_cache, base_cache);
1005                    ext_cache.insert(rhs.clone(), rhs_value);
1006                    builder.push(DslIr::MulE(*self, lhs_value, rhs_value));
1007                }
1008            },
1009            SymbolicExt::Sub(lhs, rhs, _) => match (&*lhs, &*rhs) {
1010                (SymbolicExt::Const(lhs, _), SymbolicExt::Const(rhs, _)) => {
1011                    let difference = *lhs - *rhs;
1012                    builder.push(DslIr::ImmE(*self, difference));
1013                }
1014                (SymbolicExt::Const(lhs, _), SymbolicExt::Val(rhs, _)) => {
1015                    builder.push(DslIr::SubEIN(*self, *lhs, *rhs));
1016                }
1017                (SymbolicExt::Const(lhs, _), rhs) => {
1018                    let rhs_value = Self::uninit(builder);
1019                    rhs_value.assign_with_caches(rhs.clone(), builder, ext_cache, base_cache);
1020                    ext_cache.insert(rhs.clone(), rhs_value);
1021                    builder.push(DslIr::SubEIN(*self, *lhs, rhs_value));
1022                }
1023                (SymbolicExt::Val(lhs, _), SymbolicExt::Const(rhs, _)) => {
1024                    builder.push(DslIr::SubEI(*self, *lhs, *rhs));
1025                }
1026                (SymbolicExt::Val(lhs, _), SymbolicExt::Val(rhs, _)) => {
1027                    builder.push(DslIr::SubE(*self, *lhs, *rhs));
1028                }
1029                (SymbolicExt::Val(lhs, _), SymbolicExt::Base(rhs, _)) => match rhs.as_ref() {
1030                    SymbolicFelt::Const(rhs, _) => {
1031                        builder.push(DslIr::SubEFI(*self, *lhs, *rhs));
1032                    }
1033                    SymbolicFelt::Val(rhs, _) => {
1034                        builder.push(DslIr::SubEF(*self, *lhs, *rhs));
1035                    }
1036                    rhs => {
1037                        let rhs = builder.eval(rhs.clone());
1038                        builder.push(DslIr::SubEF(*self, *lhs, rhs));
1039                    }
1040                },
1041                (SymbolicExt::Val(lhs, _), rhs) => {
1042                    let rhs_value = Self::uninit(builder);
1043                    rhs_value.assign_with_caches(rhs.clone(), builder, ext_cache, base_cache);
1044                    ext_cache.insert(rhs.clone(), rhs_value);
1045                    builder.push(DslIr::SubE(*self, *lhs, rhs_value));
1046                }
1047                (lhs, SymbolicExt::Const(rhs, _)) => {
1048                    let lhs_value = Self::uninit(builder);
1049                    lhs_value.assign_with_caches(lhs.clone(), builder, ext_cache, base_cache);
1050                    ext_cache.insert(lhs.clone(), lhs_value);
1051                    builder.push(DslIr::SubEI(*self, lhs_value, *rhs));
1052                }
1053                (lhs, SymbolicExt::Val(rhs, _)) => {
1054                    let lhs_value = Self::uninit(builder);
1055                    lhs_value.assign_with_caches(lhs.clone(), builder, ext_cache, base_cache);
1056                    ext_cache.insert(lhs.clone(), lhs_value);
1057                    builder.push(DslIr::SubE(*self, lhs_value, *rhs));
1058                }
1059                (lhs, rhs) => {
1060                    let lhs_value = Self::uninit(builder);
1061                    lhs_value.assign_with_caches(lhs.clone(), builder, ext_cache, base_cache);
1062                    ext_cache.insert(lhs.clone(), lhs_value);
1063                    let rhs_value = Self::uninit(builder);
1064                    rhs_value.assign_with_caches(rhs.clone(), builder, ext_cache, base_cache);
1065                    builder.push(DslIr::SubE(*self, lhs_value, rhs_value));
1066                }
1067            },
1068            SymbolicExt::Div(lhs, rhs, _) => match (&*lhs, &*rhs) {
1069                (SymbolicExt::Const(lhs, _), SymbolicExt::Const(rhs, _)) => {
1070                    let quotient = *lhs / *rhs;
1071                    builder.push(DslIr::ImmE(*self, quotient));
1072                }
1073                (SymbolicExt::Const(lhs, _), SymbolicExt::Val(rhs, _)) => {
1074                    builder.push(DslIr::DivEIN(*self, *lhs, *rhs));
1075                }
1076                (SymbolicExt::Const(lhs, _), rhs) => {
1077                    let rhs_value = Self::uninit(builder);
1078                    rhs_value.assign_with_caches(rhs.clone(), builder, ext_cache, base_cache);
1079                    ext_cache.insert(rhs.clone(), rhs_value);
1080                    builder.push(DslIr::DivEIN(*self, *lhs, rhs_value));
1081                }
1082                (SymbolicExt::Val(lhs, _), SymbolicExt::Const(rhs, _)) => {
1083                    builder.push(DslIr::DivEI(*self, *lhs, *rhs));
1084                }
1085                (SymbolicExt::Val(lhs, _), SymbolicExt::Val(rhs, _)) => {
1086                    builder.push(DslIr::DivE(*self, *lhs, *rhs));
1087                }
1088                (SymbolicExt::Val(lhs, _), SymbolicExt::Base(rhs, _)) => match rhs.as_ref() {
1089                    SymbolicFelt::Const(rhs, _) => {
1090                        builder.push(DslIr::DivEFI(*self, *lhs, *rhs));
1091                    }
1092                    SymbolicFelt::Val(rhs, _) => {
1093                        builder.push(DslIr::DivEF(*self, *lhs, *rhs));
1094                    }
1095                    rhs => {
1096                        let rhs = builder.eval(rhs.clone());
1097                        builder.push(DslIr::DivEF(*self, *lhs, rhs));
1098                    }
1099                },
1100                (SymbolicExt::Val(lhs, _), rhs) => {
1101                    let rhs_value = Self::uninit(builder);
1102                    rhs_value.assign_with_caches(rhs.clone(), builder, ext_cache, base_cache);
1103                    ext_cache.insert(rhs.clone(), rhs_value);
1104                    builder.push(DslIr::DivE(*self, *lhs, rhs_value));
1105                }
1106                (lhs, SymbolicExt::Const(rhs, _)) => {
1107                    let lhs_value = Self::uninit(builder);
1108                    lhs_value.assign_with_caches(lhs.clone(), builder, ext_cache, base_cache);
1109                    ext_cache.insert(lhs.clone(), lhs_value);
1110                    builder.push(DslIr::DivEI(*self, lhs_value, *rhs));
1111                }
1112                (lhs, SymbolicExt::Val(rhs, _)) => {
1113                    let lhs_value = Self::uninit(builder);
1114                    lhs_value.assign_with_caches(lhs.clone(), builder, ext_cache, base_cache);
1115                    ext_cache.insert(lhs.clone(), lhs_value);
1116                    builder.push(DslIr::DivE(*self, lhs_value, *rhs));
1117                }
1118                (lhs, rhs) => {
1119                    let lhs_value = Self::uninit(builder);
1120                    lhs_value.assign_with_caches(lhs.clone(), builder, ext_cache, base_cache);
1121                    ext_cache.insert(lhs.clone(), lhs_value);
1122                    let rhs_value = Self::uninit(builder);
1123                    rhs_value.assign_with_caches(rhs.clone(), builder, ext_cache, base_cache);
1124                    ext_cache.insert(rhs.clone(), rhs_value);
1125                    builder.push(DslIr::DivE(*self, lhs_value, rhs_value));
1126                }
1127            },
1128            SymbolicExt::Neg(operand, _) => match &*operand {
1129                SymbolicExt::Const(operand, _) => {
1130                    let negated = -*operand;
1131                    builder.push(DslIr::ImmE(*self, negated));
1132                }
1133                SymbolicExt::Val(operand, _) => {
1134                    builder.push(DslIr::NegE(*self, *operand));
1135                }
1136                operand => {
1137                    let operand_value = Self::uninit(builder);
1138                    operand_value.assign_with_caches(
1139                        operand.clone(),
1140                        builder,
1141                        ext_cache,
1142                        base_cache,
1143                    );
1144                    ext_cache.insert(operand.clone(), operand_value);
1145                    builder.push(DslIr::NegE(*self, operand_value));
1146                }
1147            },
1148        }
1149    }
1150}
1151
1152impl<C: Config> Variable<C> for Ext<C::F, C::EF> {
1153    type Expression = SymbolicExt<C::F, C::EF>;
1154
1155    fn uninit(builder: &mut Builder<C>) -> Self {
1156        builder.ext_count += 1;
1157        Ext(builder.ext_count, PhantomData)
1158    }
1159
1160    fn assign(&self, src: Self::Expression, builder: &mut Builder<C>) {
1161        self.assign_with_caches(src, builder, &mut HashMap::new(), &mut HashMap::new());
1162    }
1163
1164    fn assert_eq(
1165        lhs: impl Into<Self::Expression>,
1166        rhs: impl Into<Self::Expression>,
1167        builder: &mut Builder<C>,
1168    ) {
1169        let lhs = lhs.into();
1170        let rhs = rhs.into();
1171
1172        match (lhs, rhs) {
1173            (SymbolicExt::Const(lhs, _), SymbolicExt::Const(rhs, _)) => {
1174                assert_eq!(lhs, rhs, "Assertion failed at compile time");
1175            }
1176            (SymbolicExt::Const(lhs, _), SymbolicExt::Val(rhs, _)) => {
1177                builder.trace_push(DslIr::AssertEqEI(rhs, lhs));
1178            }
1179            (SymbolicExt::Const(lhs, _), rhs) => {
1180                let rhs_value = Self::uninit(builder);
1181                rhs_value.assign(rhs, builder);
1182                builder.trace_push(DslIr::AssertEqEI(rhs_value, lhs));
1183            }
1184            (SymbolicExt::Val(lhs, _), SymbolicExt::Const(rhs, _)) => {
1185                builder.trace_push(DslIr::AssertEqEI(lhs, rhs));
1186            }
1187            (SymbolicExt::Val(lhs, _), SymbolicExt::Val(rhs, _)) => {
1188                builder.trace_push(DslIr::AssertEqE(lhs, rhs));
1189            }
1190            (SymbolicExt::Val(lhs, _), rhs) => {
1191                let rhs_value = Self::uninit(builder);
1192                rhs_value.assign(rhs, builder);
1193                builder.trace_push(DslIr::AssertEqE(lhs, rhs_value));
1194            }
1195            (lhs, rhs) => {
1196                let lhs_value = Self::uninit(builder);
1197                lhs_value.assign(lhs, builder);
1198                let rhs_value = Self::uninit(builder);
1199                rhs_value.assign(rhs, builder);
1200                builder.trace_push(DslIr::AssertEqE(lhs_value, rhs_value));
1201            }
1202        }
1203    }
1204}
1205
1206impl<C: Config> MemVariable<C> for Ext<C::F, C::EF> {
1207    fn size_of() -> usize {
1208        C::EF::D
1209    }
1210
1211    fn load(&self, ptr: Ptr<C::N>, index: MemIndex<C::N>, builder: &mut Builder<C>) {
1212        builder.push(DslIr::LoadE(*self, ptr, index));
1213    }
1214
1215    fn store(&self, ptr: Ptr<<C as Config>::N>, index: MemIndex<C::N>, builder: &mut Builder<C>) {
1216        builder.push(DslIr::StoreE(*self, ptr, index));
1217    }
1218}
1219
1220impl<C: Config> FromConstant<C> for Var<C::N> {
1221    type Constant = C::N;
1222
1223    fn constant(value: Self::Constant, builder: &mut Builder<C>) -> Self {
1224        builder.eval(value)
1225    }
1226}
1227
1228impl<C: Config> FromConstant<C> for Felt<C::F> {
1229    type Constant = C::F;
1230
1231    fn constant(value: Self::Constant, builder: &mut Builder<C>) -> Self {
1232        builder.eval(value)
1233    }
1234}
1235
1236impl<C: Config> FromConstant<C> for Ext<C::F, C::EF> {
1237    type Constant = C::EF;
1238
1239    fn constant(value: Self::Constant, builder: &mut Builder<C>) -> Self {
1240        builder.eval(value.cons())
1241    }
1242}
openvm_native_compiler/ir/types.rs

openvm_native_compiler/ir/
types.rs
