openvm_native_compiler/ir/
types.rs

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    BasedVectorSpace, ExtensionField, Field, PrimeCharacteristicRing, 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_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: PrimeField,
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.operations.push(DslIr::ImmE(*self, (*c).into()));
852                }
853                SymbolicFelt::Val(v, _) => {
854                    builder
855                        .operations
856                        .push(DslIr::AddEFFI(*self, *v, C::EF::ZERO));
857                }
858                v => {
859                    let v_value = Felt::uninit(builder);
860                    v_value.assign(v.clone(), builder);
861                    builder.push(DslIr::AddEFFI(*self, v_value, C::EF::ZERO));
862                }
863            },
864            SymbolicExt::Const(c, _) => {
865                builder.operations.push(DslIr::ImmE(*self, c));
866            }
867            SymbolicExt::Val(v, _) => {
868                builder.operations.push(DslIr::AddEI(*self, v, C::EF::ZERO));
869            }
870            SymbolicExt::Add(lhs, rhs, _) => match (&*lhs, &*rhs) {
871                (SymbolicExt::Const(lhs, _), SymbolicExt::Const(rhs, _)) => {
872                    let sum = *lhs + *rhs;
873                    builder.operations.push(DslIr::ImmE(*self, sum));
874                }
875                (SymbolicExt::Const(lhs, _), SymbolicExt::Val(rhs, _)) => {
876                    builder.operations.push(DslIr::AddEI(*self, *rhs, *lhs));
877                }
878                (SymbolicExt::Const(lhs, _), SymbolicExt::Base(rhs, _)) => match rhs.as_ref() {
879                    SymbolicFelt::Const(rhs, _) => {
880                        let sum = *lhs + EF::from(*rhs);
881                        builder.operations.push(DslIr::ImmE(*self, sum));
882                    }
883                    SymbolicFelt::Val(rhs, _) => {
884                        builder.operations.push(DslIr::AddEFFI(*self, *rhs, *lhs));
885                    }
886                    rhs => {
887                        let rhs_value: Felt<_> = Felt::uninit(builder);
888                        rhs_value.assign_with_cache(rhs.clone(), builder, base_cache);
889                        base_cache.insert(rhs.clone(), rhs_value);
890                        builder
891                            .operations
892                            .push(DslIr::AddEFFI(*self, rhs_value, *lhs));
893                    }
894                },
895                (SymbolicExt::Const(lhs, _), rhs) => {
896                    let rhs_value = Self::uninit(builder);
897                    rhs_value.assign_with_caches(rhs.clone(), builder, ext_cache, base_cache);
898                    ext_cache.insert(rhs.clone(), rhs_value);
899                    builder.push(DslIr::AddEI(*self, rhs_value, *lhs));
900                }
901                (SymbolicExt::Val(lhs, _), SymbolicExt::Const(rhs, _)) => {
902                    builder.push(DslIr::AddEI(*self, *lhs, *rhs));
903                }
904                (SymbolicExt::Val(lhs, _), SymbolicExt::Base(rhs, _)) => match rhs.as_ref() {
905                    SymbolicFelt::Const(rhs, _) => {
906                        builder.push(DslIr::AddEFI(*self, *lhs, *rhs));
907                    }
908                    SymbolicFelt::Val(rhs, _) => {
909                        builder.push(DslIr::AddEF(*self, *lhs, *rhs));
910                    }
911                    rhs => {
912                        let rhs = builder.eval(rhs.clone());
913                        builder.push(DslIr::AddEF(*self, *lhs, rhs));
914                    }
915                },
916                (SymbolicExt::Val(lhs, _), SymbolicExt::Val(rhs, _)) => {
917                    builder.push(DslIr::AddE(*self, *lhs, *rhs));
918                }
919                (SymbolicExt::Val(lhs, _), rhs) => {
920                    let rhs_value = Self::uninit(builder);
921                    rhs_value.assign_with_caches(rhs.clone(), builder, ext_cache, base_cache);
922                    ext_cache.insert(rhs.clone(), rhs_value);
923                    builder.push(DslIr::AddE(*self, *lhs, rhs_value));
924                }
925                (lhs, SymbolicExt::Const(rhs, _)) => {
926                    let lhs_value = Self::uninit(builder);
927                    lhs_value.assign_with_caches(lhs.clone(), builder, ext_cache, base_cache);
928                    ext_cache.insert(lhs.clone(), lhs_value);
929                    builder.push(DslIr::AddEI(*self, lhs_value, *rhs));
930                }
931                (lhs, SymbolicExt::Val(rhs, _)) => {
932                    let lhs_value = Self::uninit(builder);
933                    lhs_value.assign_with_caches(lhs.clone(), builder, ext_cache, base_cache);
934                    ext_cache.insert(lhs.clone(), lhs_value);
935                    builder.push(DslIr::AddE(*self, lhs_value, *rhs));
936                }
937                (lhs, rhs) => {
938                    let lhs_value = Self::uninit(builder);
939                    lhs_value.assign_with_caches(lhs.clone(), builder, ext_cache, base_cache);
940                    ext_cache.insert(lhs.clone(), lhs_value);
941                    let rhs_value = Self::uninit(builder);
942                    rhs_value.assign_with_caches(rhs.clone(), builder, ext_cache, base_cache);
943                    ext_cache.insert(rhs.clone(), rhs_value);
944                    builder.push(DslIr::AddE(*self, lhs_value, rhs_value));
945                }
946            },
947            SymbolicExt::Mul(lhs, rhs, _) => match (&*lhs, &*rhs) {
948                (SymbolicExt::Const(lhs, _), SymbolicExt::Const(rhs, _)) => {
949                    let product = *lhs * *rhs;
950                    builder.push(DslIr::ImmE(*self, product));
951                }
952                (SymbolicExt::Const(lhs, _), SymbolicExt::Val(rhs, _)) => {
953                    builder.push(DslIr::MulEI(*self, *rhs, *lhs));
954                }
955                (SymbolicExt::Const(lhs, _), rhs) => {
956                    let rhs_value = Self::uninit(builder);
957                    rhs_value.assign_with_caches(rhs.clone(), builder, ext_cache, base_cache);
958                    ext_cache.insert(rhs.clone(), rhs_value);
959                    builder.push(DslIr::MulEI(*self, rhs_value, *lhs));
960                }
961                (SymbolicExt::Val(lhs, _), SymbolicExt::Const(rhs, _)) => {
962                    builder.push(DslIr::MulEI(*self, *lhs, *rhs));
963                }
964                (SymbolicExt::Val(lhs, _), SymbolicExt::Val(rhs, _)) => {
965                    builder.push(DslIr::MulE(*self, *lhs, *rhs));
966                }
967                (SymbolicExt::Val(lhs, _), SymbolicExt::Base(rhs, _)) => match rhs.as_ref() {
968                    SymbolicFelt::Const(rhs, _) => {
969                        builder.push(DslIr::MulEFI(*self, *lhs, *rhs));
970                    }
971                    SymbolicFelt::Val(rhs, _) => {
972                        builder.push(DslIr::MulEF(*self, *lhs, *rhs));
973                    }
974                    rhs => {
975                        let rhs = builder.eval(rhs.clone());
976                        builder.push(DslIr::MulEF(*self, *lhs, rhs));
977                    }
978                },
979                (SymbolicExt::Val(lhs, _), rhs) => {
980                    let rhs_value = Self::uninit(builder);
981                    rhs_value.assign_with_caches(rhs.clone(), builder, ext_cache, base_cache);
982                    ext_cache.insert(rhs.clone(), rhs_value);
983                    builder.push(DslIr::MulE(*self, *lhs, rhs_value));
984                }
985                (lhs, SymbolicExt::Const(rhs, _)) => {
986                    let lhs_value = Self::uninit(builder);
987                    lhs_value.assign_with_caches(lhs.clone(), builder, ext_cache, base_cache);
988                    ext_cache.insert(lhs.clone(), lhs_value);
989                    builder.push(DslIr::MulEI(*self, lhs_value, *rhs));
990                }
991                (lhs, SymbolicExt::Val(rhs, _)) => {
992                    let lhs_value = Self::uninit(builder);
993                    lhs_value.assign_with_caches(lhs.clone(), builder, ext_cache, base_cache);
994                    ext_cache.insert(lhs.clone(), lhs_value);
995                    builder.push(DslIr::MulE(*self, lhs_value, *rhs));
996                }
997                (lhs, rhs) => {
998                    let lhs_value = Self::uninit(builder);
999                    lhs_value.assign_with_caches(lhs.clone(), builder, ext_cache, base_cache);
1000                    ext_cache.insert(lhs.clone(), lhs_value);
1001                    let rhs_value = Self::uninit(builder);
1002                    rhs_value.assign_with_caches(rhs.clone(), builder, ext_cache, base_cache);
1003                    ext_cache.insert(rhs.clone(), rhs_value);
1004                    builder.push(DslIr::MulE(*self, lhs_value, rhs_value));
1005                }
1006            },
1007            SymbolicExt::Sub(lhs, rhs, _) => match (&*lhs, &*rhs) {
1008                (SymbolicExt::Const(lhs, _), SymbolicExt::Const(rhs, _)) => {
1009                    let difference = *lhs - *rhs;
1010                    builder.push(DslIr::ImmE(*self, difference));
1011                }
1012                (SymbolicExt::Const(lhs, _), SymbolicExt::Val(rhs, _)) => {
1013                    builder.push(DslIr::SubEIN(*self, *lhs, *rhs));
1014                }
1015                (SymbolicExt::Const(lhs, _), rhs) => {
1016                    let rhs_value = Self::uninit(builder);
1017                    rhs_value.assign_with_caches(rhs.clone(), builder, ext_cache, base_cache);
1018                    ext_cache.insert(rhs.clone(), rhs_value);
1019                    builder.push(DslIr::SubEIN(*self, *lhs, rhs_value));
1020                }
1021                (SymbolicExt::Val(lhs, _), SymbolicExt::Const(rhs, _)) => {
1022                    builder.push(DslIr::SubEI(*self, *lhs, *rhs));
1023                }
1024                (SymbolicExt::Val(lhs, _), SymbolicExt::Val(rhs, _)) => {
1025                    builder.push(DslIr::SubE(*self, *lhs, *rhs));
1026                }
1027                (SymbolicExt::Val(lhs, _), SymbolicExt::Base(rhs, _)) => match rhs.as_ref() {
1028                    SymbolicFelt::Const(rhs, _) => {
1029                        builder.push(DslIr::SubEFI(*self, *lhs, *rhs));
1030                    }
1031                    SymbolicFelt::Val(rhs, _) => {
1032                        builder.push(DslIr::SubEF(*self, *lhs, *rhs));
1033                    }
1034                    rhs => {
1035                        let rhs = builder.eval(rhs.clone());
1036                        builder.push(DslIr::SubEF(*self, *lhs, rhs));
1037                    }
1038                },
1039                (SymbolicExt::Val(lhs, _), rhs) => {
1040                    let rhs_value = Self::uninit(builder);
1041                    rhs_value.assign_with_caches(rhs.clone(), builder, ext_cache, base_cache);
1042                    ext_cache.insert(rhs.clone(), rhs_value);
1043                    builder.push(DslIr::SubE(*self, *lhs, rhs_value));
1044                }
1045                (lhs, SymbolicExt::Const(rhs, _)) => {
1046                    let lhs_value = Self::uninit(builder);
1047                    lhs_value.assign_with_caches(lhs.clone(), builder, ext_cache, base_cache);
1048                    ext_cache.insert(lhs.clone(), lhs_value);
1049                    builder.push(DslIr::SubEI(*self, lhs_value, *rhs));
1050                }
1051                (lhs, SymbolicExt::Val(rhs, _)) => {
1052                    let lhs_value = Self::uninit(builder);
1053                    lhs_value.assign_with_caches(lhs.clone(), builder, ext_cache, base_cache);
1054                    ext_cache.insert(lhs.clone(), lhs_value);
1055                    builder.push(DslIr::SubE(*self, lhs_value, *rhs));
1056                }
1057                (lhs, rhs) => {
1058                    let lhs_value = Self::uninit(builder);
1059                    lhs_value.assign_with_caches(lhs.clone(), builder, ext_cache, base_cache);
1060                    ext_cache.insert(lhs.clone(), lhs_value);
1061                    let rhs_value = Self::uninit(builder);
1062                    rhs_value.assign_with_caches(rhs.clone(), builder, ext_cache, base_cache);
1063                    builder.push(DslIr::SubE(*self, lhs_value, rhs_value));
1064                }
1065            },
1066            SymbolicExt::Div(lhs, rhs, _) => match (&*lhs, &*rhs) {
1067                (SymbolicExt::Const(lhs, _), SymbolicExt::Const(rhs, _)) => {
1068                    let quotient = *lhs / *rhs;
1069                    builder.push(DslIr::ImmE(*self, quotient));
1070                }
1071                (SymbolicExt::Const(lhs, _), SymbolicExt::Val(rhs, _)) => {
1072                    builder.push(DslIr::DivEIN(*self, *lhs, *rhs));
1073                }
1074                (SymbolicExt::Const(lhs, _), rhs) => {
1075                    let rhs_value = Self::uninit(builder);
1076                    rhs_value.assign_with_caches(rhs.clone(), builder, ext_cache, base_cache);
1077                    ext_cache.insert(rhs.clone(), rhs_value);
1078                    builder.push(DslIr::DivEIN(*self, *lhs, rhs_value));
1079                }
1080                (SymbolicExt::Val(lhs, _), SymbolicExt::Const(rhs, _)) => {
1081                    builder.push(DslIr::DivEI(*self, *lhs, *rhs));
1082                }
1083                (SymbolicExt::Val(lhs, _), SymbolicExt::Val(rhs, _)) => {
1084                    builder.push(DslIr::DivE(*self, *lhs, *rhs));
1085                }
1086                (SymbolicExt::Val(lhs, _), SymbolicExt::Base(rhs, _)) => match rhs.as_ref() {
1087                    SymbolicFelt::Const(rhs, _) => {
1088                        builder.push(DslIr::DivEFI(*self, *lhs, *rhs));
1089                    }
1090                    SymbolicFelt::Val(rhs, _) => {
1091                        builder.push(DslIr::DivEF(*self, *lhs, *rhs));
1092                    }
1093                    rhs => {
1094                        let rhs = builder.eval(rhs.clone());
1095                        builder.push(DslIr::DivEF(*self, *lhs, rhs));
1096                    }
1097                },
1098                (SymbolicExt::Val(lhs, _), rhs) => {
1099                    let rhs_value = Self::uninit(builder);
1100                    rhs_value.assign_with_caches(rhs.clone(), builder, ext_cache, base_cache);
1101                    ext_cache.insert(rhs.clone(), rhs_value);
1102                    builder.push(DslIr::DivE(*self, *lhs, rhs_value));
1103                }
1104                (lhs, SymbolicExt::Const(rhs, _)) => {
1105                    let lhs_value = Self::uninit(builder);
1106                    lhs_value.assign_with_caches(lhs.clone(), builder, ext_cache, base_cache);
1107                    ext_cache.insert(lhs.clone(), lhs_value);
1108                    builder.push(DslIr::DivEI(*self, lhs_value, *rhs));
1109                }
1110                (lhs, SymbolicExt::Val(rhs, _)) => {
1111                    let lhs_value = Self::uninit(builder);
1112                    lhs_value.assign_with_caches(lhs.clone(), builder, ext_cache, base_cache);
1113                    ext_cache.insert(lhs.clone(), lhs_value);
1114                    builder.push(DslIr::DivE(*self, lhs_value, *rhs));
1115                }
1116                (lhs, rhs) => {
1117                    let lhs_value = Self::uninit(builder);
1118                    lhs_value.assign_with_caches(lhs.clone(), builder, ext_cache, base_cache);
1119                    ext_cache.insert(lhs.clone(), lhs_value);
1120                    let rhs_value = Self::uninit(builder);
1121                    rhs_value.assign_with_caches(rhs.clone(), builder, ext_cache, base_cache);
1122                    ext_cache.insert(rhs.clone(), rhs_value);
1123                    builder.push(DslIr::DivE(*self, lhs_value, rhs_value));
1124                }
1125            },
1126            SymbolicExt::Neg(operand, _) => match &*operand {
1127                SymbolicExt::Const(operand, _) => {
1128                    let negated = -*operand;
1129                    builder.push(DslIr::ImmE(*self, negated));
1130                }
1131                SymbolicExt::Val(operand, _) => {
1132                    builder.push(DslIr::NegE(*self, *operand));
1133                }
1134                operand => {
1135                    let operand_value = Self::uninit(builder);
1136                    operand_value.assign_with_caches(
1137                        operand.clone(),
1138                        builder,
1139                        ext_cache,
1140                        base_cache,
1141                    );
1142                    ext_cache.insert(operand.clone(), operand_value);
1143                    builder.push(DslIr::NegE(*self, operand_value));
1144                }
1145            },
1146        }
1147    }
1148}
1149
1150impl<C: Config> Variable<C> for Ext<C::F, C::EF> {
1151    type Expression = SymbolicExt<C::F, C::EF>;
1152
1153    fn uninit(builder: &mut Builder<C>) -> Self {
1154        builder.ext_count += 1;
1155        Ext(builder.ext_count, PhantomData)
1156    }
1157
1158    fn assign(&self, src: Self::Expression, builder: &mut Builder<C>) {
1159        self.assign_with_caches(src, builder, &mut HashMap::new(), &mut HashMap::new());
1160    }
1161
1162    fn assert_eq(
1163        lhs: impl Into<Self::Expression>,
1164        rhs: impl Into<Self::Expression>,
1165        builder: &mut Builder<C>,
1166    ) {
1167        let lhs = lhs.into();
1168        let rhs = rhs.into();
1169
1170        match (lhs, rhs) {
1171            (SymbolicExt::Const(lhs, _), SymbolicExt::Const(rhs, _)) => {
1172                assert_eq!(lhs, rhs, "Assertion failed at compile time");
1173            }
1174            (SymbolicExt::Const(lhs, _), SymbolicExt::Val(rhs, _)) => {
1175                builder.trace_push(DslIr::AssertEqEI(rhs, lhs));
1176            }
1177            (SymbolicExt::Const(lhs, _), rhs) => {
1178                let rhs_value = Self::uninit(builder);
1179                rhs_value.assign(rhs, builder);
1180                builder.trace_push(DslIr::AssertEqEI(rhs_value, lhs));
1181            }
1182            (SymbolicExt::Val(lhs, _), SymbolicExt::Const(rhs, _)) => {
1183                builder.trace_push(DslIr::AssertEqEI(lhs, rhs));
1184            }
1185            (SymbolicExt::Val(lhs, _), SymbolicExt::Val(rhs, _)) => {
1186                builder.trace_push(DslIr::AssertEqE(lhs, rhs));
1187            }
1188            (SymbolicExt::Val(lhs, _), rhs) => {
1189                let rhs_value = Self::uninit(builder);
1190                rhs_value.assign(rhs, builder);
1191                builder.trace_push(DslIr::AssertEqE(lhs, rhs_value));
1192            }
1193            (lhs, rhs) => {
1194                let lhs_value = Self::uninit(builder);
1195                lhs_value.assign(lhs, builder);
1196                let rhs_value = Self::uninit(builder);
1197                rhs_value.assign(rhs, builder);
1198                builder.trace_push(DslIr::AssertEqE(lhs_value, rhs_value));
1199            }
1200        }
1201    }
1202}
1203
1204impl<C: Config> MemVariable<C> for Ext<C::F, C::EF> {
1205    fn size_of() -> usize {
1206        C::EF::DIMENSION
1207    }
1208
1209    fn load(&self, ptr: Ptr<C::N>, index: MemIndex<C::N>, builder: &mut Builder<C>) {
1210        builder.push(DslIr::LoadE(*self, ptr, index));
1211    }
1212
1213    fn store(&self, ptr: Ptr<<C as Config>::N>, index: MemIndex<C::N>, builder: &mut Builder<C>) {
1214        builder.push(DslIr::StoreE(*self, ptr, index));
1215    }
1216}
1217
1218impl<C: Config> FromConstant<C> for Var<C::N> {
1219    type Constant = C::N;
1220
1221    fn constant(value: Self::Constant, builder: &mut Builder<C>) -> Self {
1222        builder.eval(value)
1223    }
1224}
1225
1226impl<C: Config> FromConstant<C> for Felt<C::F> {
1227    type Constant = C::F;
1228
1229    fn constant(value: Self::Constant, builder: &mut Builder<C>) -> Self {
1230        builder.eval(value)
1231    }
1232}
1233
1234impl<C: Config> FromConstant<C> for Ext<C::F, C::EF> {
1235    type Constant = C::EF;
1236
1237    fn constant(value: Self::Constant, builder: &mut Builder<C>) -> Self {
1238        builder.eval(value.cons())
1239    }
1240}
openvm_native_compiler/ir/types.rs

openvm_native_compiler/ir/
types.rs
