openvm_native_compiler/ir/
symbolic.rs

1use alloc::sync::Arc;
2use core::{
3    any::Any,
4    ops::{Add, Div, Mul, Neg, Sub},
5};
6use std::{
7    any::TypeId,
8    hash::Hash,
9    iter::{Product, Sum},
10    mem,
11    ops::{AddAssign, DivAssign, MulAssign, SubAssign},
12};
13
14use openvm_stark_backend::p3_field::{ExtensionField, Field, FieldAlgebra, FieldArray, PrimeField};
15use serde::{Deserialize, Serialize};
16
17use super::{utils::prime_field_to_usize, Ext, Felt, Usize, Var};
18
19const NUM_RANDOM_ELEMENTS: usize = 4;
20
21pub type Digest<T> = FieldArray<T, NUM_RANDOM_ELEMENTS>;
22
23pub fn elements<F: Field>() -> Digest<F> {
24    let powers = [1671541671, 1254988180, 442438744, 1716490559];
25    let generator = F::GENERATOR;
26
27    Digest::from(powers.map(|p| generator.exp_u64(p)))
28}
29
30pub fn ext_elements<F: Field, EF: ExtensionField<F>>() -> Digest<EF> {
31    let powers = [1021539871, 1430550064, 447478069, 1248903325];
32    let generator = EF::GENERATOR;
33
34    Digest::from(powers.map(|p| generator.exp_u64(p)))
35}
36
37fn digest_id<F: Field>(id: u32) -> Digest<F> {
38    let elements = elements();
39    Digest::from(elements.0.map(|e: F| {
40        (e + F::from_canonical_u32(id))
41            .try_inverse()
42            .unwrap_or(F::ONE)
43    }))
44}
45
46fn digest_id_ext<F: Field, EF: ExtensionField<F>>(id: u32) -> Digest<EF> {
47    let elements = ext_elements();
48    Digest::from(elements.0.map(|e: EF| {
49        (e + EF::from_canonical_u32(id))
50            .try_inverse()
51            .unwrap_or(EF::ONE)
52    }))
53}
54
55fn div_digests<F: Field>(a: Digest<F>, b: Digest<F>) -> Digest<F> {
56    Digest::from(core::array::from_fn(|i| a.0[i] / b.0[i]))
57}
58
59/// A symbolic variable. For any binary operator, at least one of the operands must be variable.
60#[derive(Debug, Clone)]
61pub enum SymbolicVar<N: Field> {
62    Const(N, Digest<N>),
63    Val(Var<N>, Digest<N>),
64    Add(Arc<SymbolicVar<N>>, Arc<SymbolicVar<N>>, Digest<N>),
65    Mul(Arc<SymbolicVar<N>>, Arc<SymbolicVar<N>>, Digest<N>),
66    Sub(Arc<SymbolicVar<N>>, Arc<SymbolicVar<N>>, Digest<N>),
67    Neg(Arc<SymbolicVar<N>>, Digest<N>),
68}
69
70#[derive(Debug, Clone)]
71pub enum SymbolicFelt<F: Field> {
72    Const(F, Digest<F>),
73    Val(Felt<F>, Digest<F>),
74    Add(Arc<SymbolicFelt<F>>, Arc<SymbolicFelt<F>>, Digest<F>),
75    Mul(Arc<SymbolicFelt<F>>, Arc<SymbolicFelt<F>>, Digest<F>),
76    Sub(Arc<SymbolicFelt<F>>, Arc<SymbolicFelt<F>>, Digest<F>),
77    Div(Arc<SymbolicFelt<F>>, Arc<SymbolicFelt<F>>, Digest<F>),
78    Neg(Arc<SymbolicFelt<F>>, Digest<F>),
79}
80
81#[derive(Debug, Clone)]
82pub enum SymbolicExt<F: Field, EF: Field> {
83    Const(EF, Digest<EF>),
84    Base(Arc<SymbolicFelt<F>>, Digest<EF>),
85    Val(Ext<F, EF>, Digest<EF>),
86    Add(Arc<SymbolicExt<F, EF>>, Arc<SymbolicExt<F, EF>>, Digest<EF>),
87    Mul(Arc<SymbolicExt<F, EF>>, Arc<SymbolicExt<F, EF>>, Digest<EF>),
88    Sub(Arc<SymbolicExt<F, EF>>, Arc<SymbolicExt<F, EF>>, Digest<EF>),
89    Div(Arc<SymbolicExt<F, EF>>, Arc<SymbolicExt<F, EF>>, Digest<EF>),
90    Neg(Arc<SymbolicExt<F, EF>>, Digest<EF>),
91}
92
93/// A right value of Var. It should never be assigned with a value.
94#[derive(Debug, Copy, Clone, Serialize, Deserialize)]
95pub enum RVar<N> {
96    Const(N),
97    Val(Var<N>),
98}
99
100impl<N: PrimeField> RVar<N> {
101    pub fn zero() -> Self {
102        RVar::Const(N::ZERO)
103    }
104    pub fn one() -> Self {
105        RVar::Const(N::ONE)
106    }
107    pub fn from_field(n: N) -> Self {
108        RVar::Const(n)
109    }
110    pub fn is_const(&self) -> bool {
111        match self {
112            RVar::Const(_) => true,
113            RVar::Val(_) => false,
114        }
115    }
116    pub fn value(&self) -> usize {
117        match self {
118            RVar::Const(c) => prime_field_to_usize(*c),
119            _ => panic!("RVar::value() called on non-const value"),
120        }
121    }
122    pub fn field_value(&self) -> N {
123        match self {
124            RVar::Const(c) => *c,
125            _ => panic!("RVar::field_value() called on non-const value"),
126        }
127    }
128
129    pub fn variable(&self) -> Var<N> {
130        match self {
131            RVar::Const(_) => panic!("RVar::variable() called on const value"),
132            RVar::Val(var) => *var,
133        }
134    }
135}
136
137impl<N: Field> Hash for SymbolicVar<N> {
138    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
139        for elem in self.digest().0.iter() {
140            elem.hash(state);
141        }
142    }
143}
144
145impl<N: Field> PartialEq for SymbolicVar<N> {
146    fn eq(&self, other: &Self) -> bool {
147        if self.digest() != other.digest() {
148            return false;
149        }
150        match (self, other) {
151            (SymbolicVar::Const(a, _), SymbolicVar::Const(b, _)) => a == b,
152            (SymbolicVar::Val(a, _), SymbolicVar::Val(b, _)) => a == b,
153            (SymbolicVar::Add(a, b, _), SymbolicVar::Add(c, d, _)) => a == c && b == d,
154            (SymbolicVar::Mul(a, b, _), SymbolicVar::Mul(c, d, _)) => a == c && b == d,
155            (SymbolicVar::Sub(a, b, _), SymbolicVar::Sub(c, d, _)) => a == c && b == d,
156            (SymbolicVar::Neg(a, _), SymbolicVar::Neg(b, _)) => a == b,
157            _ => false,
158        }
159    }
160}
161
162impl<N: Field> Eq for SymbolicVar<N> {}
163
164impl<F: Field> Hash for SymbolicFelt<F> {
165    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
166        for elem in self.digest().0.iter() {
167            elem.hash(state);
168        }
169    }
170}
171
172impl<F: Field> PartialEq for SymbolicFelt<F> {
173    fn eq(&self, other: &Self) -> bool {
174        if self.digest() != other.digest() {
175            return false;
176        }
177        match (self, other) {
178            (SymbolicFelt::Const(a, _), SymbolicFelt::Const(b, _)) => a == b,
179            (SymbolicFelt::Val(a, _), SymbolicFelt::Val(b, _)) => a == b,
180            (SymbolicFelt::Add(a, b, _), SymbolicFelt::Add(c, d, _)) => a == c && b == d,
181            (SymbolicFelt::Mul(a, b, _), SymbolicFelt::Mul(c, d, _)) => a == c && b == d,
182            (SymbolicFelt::Sub(a, b, _), SymbolicFelt::Sub(c, d, _)) => a == c && b == d,
183            (SymbolicFelt::Div(a, b, _), SymbolicFelt::Div(c, d, _)) => a == c && b == d,
184            (SymbolicFelt::Neg(a, _), SymbolicFelt::Neg(b, _)) => a == b,
185            _ => false,
186        }
187    }
188}
189
190impl<F: Field> Eq for SymbolicFelt<F> {}
191
192impl<F: Field, EF: Field> Hash for SymbolicExt<F, EF> {
193    fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
194        for elem in self.digest().0.iter() {
195            elem.hash(state);
196        }
197    }
198}
199
200impl<F: Field, EF: Field> PartialEq for SymbolicExt<F, EF> {
201    fn eq(&self, other: &Self) -> bool {
202        if self.digest() != other.digest() {
203            return false;
204        }
205        match (self, other) {
206            (SymbolicExt::Const(a, _), SymbolicExt::Const(b, _)) => a == b,
207            (SymbolicExt::Base(a, _), SymbolicExt::Base(b, _)) => a == b,
208            (SymbolicExt::Val(a, _), SymbolicExt::Val(b, _)) => a == b,
209            (SymbolicExt::Add(a, b, _), SymbolicExt::Add(c, d, _)) => a == c && b == d,
210            (SymbolicExt::Mul(a, b, _), SymbolicExt::Mul(c, d, _)) => a == c && b == d,
211            (SymbolicExt::Sub(a, b, _), SymbolicExt::Sub(c, d, _)) => a == c && b == d,
212            (SymbolicExt::Div(a, b, _), SymbolicExt::Div(c, d, _)) => a == c && b == d,
213            (SymbolicExt::Neg(a, _), SymbolicExt::Neg(b, _)) => a == b,
214            _ => false,
215        }
216    }
217}
218
219impl<F: Field, EF: Field> Eq for SymbolicExt<F, EF> {}
220
221impl<N: Field> SymbolicVar<N> {
222    pub(crate) const fn digest(&self) -> Digest<N> {
223        match self {
224            SymbolicVar::Const(_, d) => *d,
225            SymbolicVar::Val(_, d) => *d,
226            SymbolicVar::Add(_, _, d) => *d,
227            SymbolicVar::Mul(_, _, d) => *d,
228            SymbolicVar::Sub(_, _, d) => *d,
229            SymbolicVar::Neg(_, d) => *d,
230        }
231    }
232}
233
234impl<F: Field> SymbolicFelt<F> {
235    pub(crate) const fn digest(&self) -> Digest<F> {
236        match self {
237            SymbolicFelt::Const(_, d) => *d,
238            SymbolicFelt::Val(_, d) => *d,
239            SymbolicFelt::Add(_, _, d) => *d,
240            SymbolicFelt::Mul(_, _, d) => *d,
241            SymbolicFelt::Sub(_, _, d) => *d,
242            SymbolicFelt::Div(_, _, d) => *d,
243            SymbolicFelt::Neg(_, d) => *d,
244        }
245    }
246}
247
248impl<F: Field, EF: Field> SymbolicExt<F, EF> {
249    pub(crate) const fn digest(&self) -> Digest<EF> {
250        match self {
251            SymbolicExt::Const(_, d) => *d,
252            SymbolicExt::Base(_, d) => *d,
253            SymbolicExt::Val(_, d) => *d,
254            SymbolicExt::Add(_, _, d) => *d,
255            SymbolicExt::Mul(_, _, d) => *d,
256            SymbolicExt::Sub(_, _, d) => *d,
257            SymbolicExt::Div(_, _, d) => *d,
258            SymbolicExt::Neg(_, d) => *d,
259        }
260    }
261}
262
263#[derive(Debug, Clone)]
264pub enum ExtOperand<F: Field, EF: ExtensionField<F>> {
265    Base(F),
266    Const(EF),
267    Felt(Felt<F>),
268    Ext(Ext<F, EF>),
269    SymFelt(SymbolicFelt<F>),
270    Sym(SymbolicExt<F, EF>),
271}
272
273impl<F: Field, EF: ExtensionField<F>> ExtOperand<F, EF> {
274    pub fn digest(&self) -> Digest<EF> {
275        match self {
276            ExtOperand::Base(f) => SymbolicFelt::from(*f).digest().0.map(EF::from_base).into(),
277            ExtOperand::Const(ef) => (*ef).into(),
278            ExtOperand::Felt(f) => SymbolicFelt::from(*f).digest().0.map(EF::from_base).into(),
279            ExtOperand::Ext(e) => digest_id_ext::<F, EF>(e.0),
280            ExtOperand::SymFelt(f) => f.digest().0.map(EF::from_base).into(),
281            ExtOperand::Sym(e) => e.digest(),
282        }
283    }
284
285    pub fn symbolic(self) -> SymbolicExt<F, EF> {
286        let digest = self.digest();
287        match self {
288            ExtOperand::Base(f) => SymbolicExt::Base(Arc::new(SymbolicFelt::from(f)), digest),
289            ExtOperand::Const(ef) => SymbolicExt::Const(ef, digest),
290            ExtOperand::Felt(f) => SymbolicExt::Base(Arc::new(SymbolicFelt::from(f)), digest),
291            ExtOperand::Ext(e) => SymbolicExt::Val(e, digest),
292            ExtOperand::SymFelt(f) => SymbolicExt::Base(Arc::new(f), digest),
293            ExtOperand::Sym(e) => e,
294        }
295    }
296}
297
298pub trait ExtConst<F: Field, EF: ExtensionField<F>> {
299    fn cons(self) -> SymbolicExt<F, EF>;
300}
301
302impl<F: Field, EF: ExtensionField<F>> ExtConst<F, EF> for EF {
303    fn cons(self) -> SymbolicExt<F, EF> {
304        SymbolicExt::Const(self, self.into())
305    }
306}
307
308pub trait ExtensionOperand<F: Field, EF: ExtensionField<F>> {
309    fn to_operand(self) -> ExtOperand<F, EF>;
310}
311
312impl<N: Field> FieldAlgebra for SymbolicVar<N> {
313    type F = N;
314
315    const ZERO: Self = SymbolicVar::Const(N::ZERO, FieldArray([N::ZERO; 4]));
316    const ONE: Self = SymbolicVar::Const(N::ONE, FieldArray([N::ONE; 4]));
317    const TWO: Self = SymbolicVar::Const(N::TWO, FieldArray([N::TWO; 4]));
318    const NEG_ONE: Self = SymbolicVar::Const(N::NEG_ONE, FieldArray([N::NEG_ONE; 4]));
319
320    fn from_f(f: Self::F) -> Self {
321        SymbolicVar::from(f)
322    }
323    fn from_bool(b: bool) -> Self {
324        SymbolicVar::from(N::from_bool(b))
325    }
326    fn from_canonical_u8(n: u8) -> Self {
327        SymbolicVar::from(N::from_canonical_u8(n))
328    }
329    fn from_canonical_u16(n: u16) -> Self {
330        SymbolicVar::from(N::from_canonical_u16(n))
331    }
332    fn from_canonical_u32(n: u32) -> Self {
333        SymbolicVar::from(N::from_canonical_u32(n))
334    }
335    fn from_canonical_u64(n: u64) -> Self {
336        SymbolicVar::from(N::from_canonical_u64(n))
337    }
338    fn from_canonical_usize(n: usize) -> Self {
339        SymbolicVar::from(N::from_canonical_usize(n))
340    }
341
342    fn from_wrapped_u32(n: u32) -> Self {
343        SymbolicVar::from(N::from_wrapped_u32(n))
344    }
345    fn from_wrapped_u64(n: u64) -> Self {
346        SymbolicVar::from(N::from_wrapped_u64(n))
347    }
348}
349
350/// Trait to exclude SymbolicVar in generic parameters.
351trait NotSymbolicVar {}
352impl<N: Field> NotSymbolicVar for N {}
353impl<N: Field> NotSymbolicVar for Var<N> {}
354impl<N: PrimeField> NotSymbolicVar for Usize<N> {}
355impl<N: Field> NotSymbolicVar for RVar<N> {}
356
357impl<F: Field> FieldAlgebra for SymbolicFelt<F> {
358    type F = F;
359
360    const ZERO: Self = SymbolicFelt::Const(F::ZERO, FieldArray([F::ZERO; 4]));
361    const ONE: Self = SymbolicFelt::Const(F::ONE, FieldArray([F::ONE; 4]));
362    const TWO: Self = SymbolicFelt::Const(F::TWO, FieldArray([F::TWO; 4]));
363    const NEG_ONE: Self = SymbolicFelt::Const(F::NEG_ONE, FieldArray([F::NEG_ONE; 4]));
364
365    fn from_f(f: Self::F) -> Self {
366        SymbolicFelt::from(f)
367    }
368    fn from_bool(b: bool) -> Self {
369        SymbolicFelt::from(F::from_bool(b))
370    }
371    fn from_canonical_u8(n: u8) -> Self {
372        SymbolicFelt::from(F::from_canonical_u8(n))
373    }
374    fn from_canonical_u16(n: u16) -> Self {
375        SymbolicFelt::from(F::from_canonical_u16(n))
376    }
377    fn from_canonical_u32(n: u32) -> Self {
378        SymbolicFelt::from(F::from_canonical_u32(n))
379    }
380    fn from_canonical_u64(n: u64) -> Self {
381        SymbolicFelt::from(F::from_canonical_u64(n))
382    }
383    fn from_canonical_usize(n: usize) -> Self {
384        SymbolicFelt::from(F::from_canonical_usize(n))
385    }
386
387    fn from_wrapped_u32(n: u32) -> Self {
388        SymbolicFelt::from(F::from_wrapped_u32(n))
389    }
390    fn from_wrapped_u64(n: u64) -> Self {
391        SymbolicFelt::from(F::from_wrapped_u64(n))
392    }
393}
394
395impl<F: Field, EF: ExtensionField<F>> FieldAlgebra for SymbolicExt<F, EF> {
396    type F = EF;
397
398    const ZERO: Self = SymbolicExt::Const(EF::ZERO, FieldArray([EF::ZERO; 4]));
399    const ONE: Self =
400        SymbolicExt::Const(EF::ONE, FieldArray([EF::ZERO, EF::ZERO, EF::ZERO, EF::ONE]));
401    const TWO: Self =
402        SymbolicExt::Const(EF::TWO, FieldArray([EF::ZERO, EF::ZERO, EF::ZERO, EF::TWO]));
403    const NEG_ONE: Self = SymbolicExt::Const(
404        EF::NEG_ONE,
405        FieldArray([EF::ZERO, EF::ZERO, EF::ZERO, EF::NEG_ONE]),
406    );
407
408    fn from_f(f: Self::F) -> Self {
409        SymbolicExt::Const(f, f.into())
410    }
411    fn from_bool(b: bool) -> Self {
412        SymbolicExt::from_f(EF::from_bool(b))
413    }
414    fn from_canonical_u8(n: u8) -> Self {
415        SymbolicExt::from_f(EF::from_canonical_u8(n))
416    }
417    fn from_canonical_u16(n: u16) -> Self {
418        SymbolicExt::from_f(EF::from_canonical_u16(n))
419    }
420    fn from_canonical_u32(n: u32) -> Self {
421        SymbolicExt::from_f(EF::from_canonical_u32(n))
422    }
423    fn from_canonical_u64(n: u64) -> Self {
424        SymbolicExt::from_f(EF::from_canonical_u64(n))
425    }
426    fn from_canonical_usize(n: usize) -> Self {
427        SymbolicExt::from_f(EF::from_canonical_usize(n))
428    }
429
430    fn from_wrapped_u32(n: u32) -> Self {
431        SymbolicExt::from_f(EF::from_wrapped_u32(n))
432    }
433    fn from_wrapped_u64(n: u64) -> Self {
434        SymbolicExt::from_f(EF::from_wrapped_u64(n))
435    }
436}
437
438// Implement all conversions from constants N, F, EF, to the corresponding symbolic types
439
440impl<N: Field> From<N> for SymbolicVar<N> {
441    fn from(n: N) -> Self {
442        SymbolicVar::Const(n, n.into())
443    }
444}
445
446impl<F: Field> From<F> for SymbolicFelt<F> {
447    fn from(f: F) -> Self {
448        SymbolicFelt::Const(f, f.into())
449    }
450}
451
452impl<F: Field, EF: ExtensionField<F>> From<F> for SymbolicExt<F, EF> {
453    fn from(f: F) -> Self {
454        f.to_operand().symbolic()
455    }
456}
457
458// Implement all conversions from Var<N>, Felt<F>, Ext<F, EF> to the corresponding symbolic types
459
460impl<N: Field> From<Var<N>> for SymbolicVar<N> {
461    fn from(v: Var<N>) -> Self {
462        SymbolicVar::Val(v, digest_id(v.0))
463    }
464}
465
466impl<F: Field> From<Felt<F>> for SymbolicFelt<F> {
467    fn from(f: Felt<F>) -> Self {
468        SymbolicFelt::Val(f, digest_id(f.0))
469    }
470}
471
472impl<F: Field, EF: ExtensionField<F>> From<Ext<F, EF>> for SymbolicExt<F, EF> {
473    fn from(e: Ext<F, EF>) -> Self {
474        e.to_operand().symbolic()
475    }
476}
477
478// Implement all operations for SymbolicVar<N>, SymbolicFelt<F>, SymbolicExt<F, EF>
479
480impl<N: Field> Add for SymbolicVar<N> {
481    type Output = Self;
482
483    fn add(self, rhs: Self) -> Self::Output {
484        let digest = self.digest() + rhs.digest();
485        match (&self, &rhs) {
486            (SymbolicVar::Const(a, _), SymbolicVar::Const(b, _)) => {
487                return SymbolicVar::Const(*a + *b, digest);
488            }
489            (SymbolicVar::Const(a, _), _) => {
490                if a.is_zero() {
491                    return rhs;
492                }
493            }
494            (_, SymbolicVar::Const(b, _)) => {
495                if b.is_zero() {
496                    return self;
497                }
498            }
499            _ => (),
500        }
501        SymbolicVar::Add(Arc::new(self), Arc::new(rhs), digest)
502    }
503}
504
505impl<N: Field, RHS: Into<SymbolicVar<N>> + NotSymbolicVar> Add<RHS> for SymbolicVar<N> {
506    type Output = Self;
507
508    fn add(self, rhs: RHS) -> Self::Output {
509        self + rhs.into()
510    }
511}
512
513impl<F: Field> Add for SymbolicFelt<F> {
514    type Output = Self;
515
516    fn add(self, rhs: Self) -> Self::Output {
517        let digest = self.digest() + rhs.digest();
518        SymbolicFelt::Add(Arc::new(self), Arc::new(rhs), digest)
519    }
520}
521
522impl<F: Field, EF: ExtensionField<F>, E: ExtensionOperand<F, EF>> Add<E> for SymbolicExt<F, EF> {
523    type Output = Self;
524
525    fn add(self, rhs: E) -> Self::Output {
526        let rhs = rhs.to_operand().symbolic();
527        let digest = self.digest() + rhs.digest();
528        SymbolicExt::Add(Arc::new(self), Arc::new(rhs), digest)
529    }
530}
531
532impl<N: Field> Mul for SymbolicVar<N> {
533    type Output = Self;
534
535    fn mul(self, rhs: Self) -> Self::Output {
536        let digest = self.digest() * rhs.digest();
537        match (&self, &rhs) {
538            (SymbolicVar::Const(a, _), SymbolicVar::Const(b, _)) => {
539                return SymbolicVar::Const(*a * *b, digest);
540            }
541            (SymbolicVar::Const(a, _), _) => {
542                if a.is_zero() {
543                    return self;
544                }
545                if a.is_one() {
546                    return rhs;
547                }
548            }
549            (_, SymbolicVar::Const(b, _)) => {
550                if b.is_zero() {
551                    return rhs;
552                }
553                if b.is_one() {
554                    return self;
555                }
556            }
557            _ => (),
558        }
559        SymbolicVar::Mul(Arc::new(self), Arc::new(rhs), digest)
560    }
561}
562
563impl<N: Field, RHS: Into<SymbolicVar<N>> + NotSymbolicVar> Mul<RHS> for SymbolicVar<N> {
564    type Output = Self;
565
566    fn mul(self, rhs: RHS) -> Self::Output {
567        self * rhs.into()
568    }
569}
570
571impl<F: Field> Mul for SymbolicFelt<F> {
572    type Output = Self;
573
574    fn mul(self, rhs: Self) -> Self::Output {
575        let digest = self.digest() * rhs.digest();
576        SymbolicFelt::Mul(Arc::new(self), Arc::new(rhs), digest)
577    }
578}
579
580impl<F: Field, EF: ExtensionField<F>, E: Any> Mul<E> for SymbolicExt<F, EF> {
581    type Output = Self;
582
583    fn mul(self, rhs: E) -> Self::Output {
584        let rhs = rhs.to_operand();
585        let rhs_digest = rhs.digest();
586        let prod_digest = self.digest() * rhs_digest;
587        match rhs {
588            ExtOperand::Base(f) => SymbolicExt::Mul(
589                Arc::new(self),
590                Arc::new(SymbolicExt::Base(
591                    Arc::new(SymbolicFelt::from(f)),
592                    rhs_digest,
593                )),
594                prod_digest,
595            ),
596            ExtOperand::Const(ef) => SymbolicExt::Mul(
597                Arc::new(self),
598                Arc::new(SymbolicExt::Const(ef, rhs_digest)),
599                prod_digest,
600            ),
601            ExtOperand::Felt(f) => SymbolicExt::Mul(
602                Arc::new(self),
603                Arc::new(SymbolicExt::Base(
604                    Arc::new(SymbolicFelt::from(f)),
605                    rhs_digest,
606                )),
607                prod_digest,
608            ),
609            ExtOperand::Ext(e) => SymbolicExt::Mul(
610                Arc::new(self),
611                Arc::new(SymbolicExt::Val(e, rhs_digest)),
612                prod_digest,
613            ),
614            ExtOperand::SymFelt(f) => SymbolicExt::Mul(
615                Arc::new(self),
616                Arc::new(SymbolicExt::Base(Arc::new(f), rhs_digest)),
617                prod_digest,
618            ),
619            ExtOperand::Sym(e) => SymbolicExt::Mul(Arc::new(self), Arc::new(e), prod_digest),
620        }
621    }
622}
623
624impl<N: Field> Sub for SymbolicVar<N> {
625    type Output = Self;
626
627    fn sub(self, rhs: Self) -> Self::Output {
628        let digest = self.digest() - rhs.digest();
629        match (&self, &rhs) {
630            (SymbolicVar::Const(a, _), SymbolicVar::Const(b, _)) => {
631                return SymbolicVar::Const(*a - *b, digest);
632            }
633            (SymbolicVar::Const(a, _), _) => {
634                if a.is_zero() {
635                    return rhs;
636                }
637            }
638            (_, SymbolicVar::Const(b, _)) => {
639                if b.is_zero() {
640                    return self;
641                }
642            }
643            _ => (),
644        }
645        SymbolicVar::Sub(Arc::new(self), Arc::new(rhs), digest)
646    }
647}
648
649impl<N: Field, RHS: Into<SymbolicVar<N>> + NotSymbolicVar> Sub<RHS> for SymbolicVar<N> {
650    type Output = Self;
651
652    fn sub(self, rhs: RHS) -> Self::Output {
653        self - rhs.into()
654    }
655}
656
657impl<F: Field> Sub for SymbolicFelt<F> {
658    type Output = Self;
659
660    fn sub(self, rhs: Self) -> Self::Output {
661        let digest = self.digest() - rhs.digest();
662        SymbolicFelt::Sub(Arc::new(self), Arc::new(rhs), digest)
663    }
664}
665
666impl<F: Field, EF: ExtensionField<F>, E: Any> Sub<E> for SymbolicExt<F, EF> {
667    type Output = Self;
668
669    fn sub(self, rhs: E) -> Self::Output {
670        let rhs = rhs.to_operand();
671        let rhs_digest = rhs.digest();
672        let digest = self.digest() - rhs_digest;
673        match rhs {
674            ExtOperand::Base(f) => SymbolicExt::Sub(
675                Arc::new(self),
676                Arc::new(SymbolicExt::Base(
677                    Arc::new(SymbolicFelt::from(f)),
678                    rhs_digest,
679                )),
680                digest,
681            ),
682            ExtOperand::Const(ef) => SymbolicExt::Sub(
683                Arc::new(self),
684                Arc::new(SymbolicExt::Const(ef, rhs_digest)),
685                digest,
686            ),
687            ExtOperand::Felt(f) => SymbolicExt::Sub(
688                Arc::new(self),
689                Arc::new(SymbolicExt::Base(
690                    Arc::new(SymbolicFelt::from(f)),
691                    rhs_digest,
692                )),
693                digest,
694            ),
695            ExtOperand::Ext(e) => SymbolicExt::Sub(
696                Arc::new(self),
697                Arc::new(SymbolicExt::Val(e, rhs_digest)),
698                digest,
699            ),
700            ExtOperand::SymFelt(f) => SymbolicExt::Sub(
701                Arc::new(self),
702                Arc::new(SymbolicExt::Base(Arc::new(f), rhs_digest)),
703                digest,
704            ),
705            ExtOperand::Sym(e) => SymbolicExt::Sub(Arc::new(self), Arc::new(e), digest),
706        }
707    }
708}
709
710impl<F: Field> Div for SymbolicFelt<F> {
711    type Output = Self;
712
713    fn div(self, rhs: Self) -> Self::Output {
714        let self_digest = self.digest();
715        let rhs_digest = rhs.digest();
716        let digest = div_digests(self_digest, rhs_digest);
717        SymbolicFelt::Div(Arc::new(self), Arc::new(rhs), digest)
718    }
719}
720
721impl<F: Field, EF: ExtensionField<F>, E: Any> Div<E> for SymbolicExt<F, EF> {
722    type Output = Self;
723
724    fn div(self, rhs: E) -> Self::Output {
725        let rhs = rhs.to_operand();
726        let rhs_digest = rhs.digest();
727        let digest = div_digests(self.digest(), rhs_digest);
728        match rhs {
729            ExtOperand::Base(f) => SymbolicExt::Div(
730                Arc::new(self),
731                Arc::new(SymbolicExt::Base(
732                    Arc::new(SymbolicFelt::from(f)),
733                    rhs_digest,
734                )),
735                digest,
736            ),
737            ExtOperand::Const(ef) => SymbolicExt::Div(
738                Arc::new(self),
739                Arc::new(SymbolicExt::Const(ef, rhs_digest)),
740                digest,
741            ),
742            ExtOperand::Felt(f) => SymbolicExt::Div(
743                Arc::new(self),
744                Arc::new(SymbolicExt::Base(
745                    Arc::new(SymbolicFelt::from(f)),
746                    rhs_digest,
747                )),
748                digest,
749            ),
750            ExtOperand::Ext(e) => SymbolicExt::Div(
751                Arc::new(self),
752                Arc::new(SymbolicExt::Val(e, rhs_digest)),
753                digest,
754            ),
755            ExtOperand::SymFelt(f) => SymbolicExt::Div(
756                Arc::new(self),
757                Arc::new(SymbolicExt::Base(Arc::new(f), rhs_digest)),
758                digest,
759            ),
760            ExtOperand::Sym(e) => SymbolicExt::Div(Arc::new(self), Arc::new(e), digest),
761        }
762    }
763}
764
765impl<N: Field> Neg for SymbolicVar<N> {
766    type Output = Self;
767
768    fn neg(self) -> Self::Output {
769        let digest = -self.digest();
770        match &self {
771            SymbolicVar::Const(c, _) => SymbolicVar::Const(-*c, digest),
772            _ => SymbolicVar::Neg(Arc::new(self), digest),
773        }
774    }
775}
776
777impl<F: Field> Neg for SymbolicFelt<F> {
778    type Output = Self;
779
780    fn neg(self) -> Self::Output {
781        let digest = -self.digest();
782        SymbolicFelt::Neg(Arc::new(self), digest)
783    }
784}
785
786impl<F: Field, EF: ExtensionField<F>> Neg for SymbolicExt<F, EF> {
787    type Output = Self;
788
789    fn neg(self) -> Self::Output {
790        let digest = -self.digest();
791        SymbolicExt::Neg(Arc::new(self), digest)
792    }
793}
794
795// Implement all operations between N, F, EF, and SymbolicVar<N>, SymbolicFelt<F>, SymbolicExt<F, EF>
796
797impl<F: Field> Add<F> for SymbolicFelt<F> {
798    type Output = Self;
799
800    fn add(self, rhs: F) -> Self::Output {
801        self + SymbolicFelt::from(rhs)
802    }
803}
804
805impl<F: Field> Mul<F> for SymbolicFelt<F> {
806    type Output = Self;
807
808    fn mul(self, rhs: F) -> Self::Output {
809        self * SymbolicFelt::from(rhs)
810    }
811}
812
813impl<F: Field> Sub<F> for SymbolicFelt<F> {
814    type Output = Self;
815
816    fn sub(self, rhs: F) -> Self::Output {
817        self - SymbolicFelt::from(rhs)
818    }
819}
820
821// Implement all operations between SymbolicVar<N>, SymbolicFelt<F>, SymbolicExt<F, EF>, and Var<N>,
822//  Felt<F>, Ext<F, EF>.
823
824impl<F: Field> Add<Felt<F>> for SymbolicFelt<F> {
825    type Output = SymbolicFelt<F>;
826
827    fn add(self, rhs: Felt<F>) -> Self::Output {
828        self + SymbolicFelt::from(rhs)
829    }
830}
831
832impl<F: Field> Mul<Felt<F>> for SymbolicFelt<F> {
833    type Output = SymbolicFelt<F>;
834
835    fn mul(self, rhs: Felt<F>) -> Self::Output {
836        self * SymbolicFelt::from(rhs)
837    }
838}
839
840impl<F: Field> Sub<Felt<F>> for SymbolicFelt<F> {
841    type Output = SymbolicFelt<F>;
842
843    fn sub(self, rhs: Felt<F>) -> Self::Output {
844        self - SymbolicFelt::from(rhs)
845    }
846}
847
848impl<F: Field> Div<SymbolicFelt<F>> for Felt<F> {
849    type Output = SymbolicFelt<F>;
850
851    fn div(self, rhs: SymbolicFelt<F>) -> Self::Output {
852        SymbolicFelt::<F>::from(self) / rhs
853    }
854}
855
856// Implement operations between constants N, F, EF, and Var<N>, Felt<F>, Ext<F, EF>.
857
858impl<F: Field> Add for Felt<F> {
859    type Output = SymbolicFelt<F>;
860
861    fn add(self, rhs: Self) -> Self::Output {
862        SymbolicFelt::<F>::from(self) + rhs
863    }
864}
865
866impl<F: Field> Add<F> for Felt<F> {
867    type Output = SymbolicFelt<F>;
868
869    fn add(self, rhs: F) -> Self::Output {
870        SymbolicFelt::from(self) + rhs
871    }
872}
873
874impl<N: Field> Mul for Var<N> {
875    type Output = SymbolicVar<N>;
876
877    fn mul(self, rhs: Self) -> Self::Output {
878        SymbolicVar::<N>::from(self) * rhs
879    }
880}
881
882impl<N: Field> Mul<N> for Var<N> {
883    type Output = SymbolicVar<N>;
884
885    fn mul(self, rhs: N) -> Self::Output {
886        SymbolicVar::from(self) * rhs
887    }
888}
889
890impl<F: Field> Mul for Felt<F> {
891    type Output = SymbolicFelt<F>;
892
893    fn mul(self, rhs: Self) -> Self::Output {
894        SymbolicFelt::<F>::from(self) * rhs
895    }
896}
897
898impl<F: Field> Mul<F> for Felt<F> {
899    type Output = SymbolicFelt<F>;
900
901    fn mul(self, rhs: F) -> Self::Output {
902        SymbolicFelt::from(self) * rhs
903    }
904}
905
906impl<F: Field> Sub for Felt<F> {
907    type Output = SymbolicFelt<F>;
908
909    fn sub(self, rhs: Self) -> Self::Output {
910        SymbolicFelt::<F>::from(self) - rhs
911    }
912}
913
914impl<F: Field> Sub<F> for Felt<F> {
915    type Output = SymbolicFelt<F>;
916
917    fn sub(self, rhs: F) -> Self::Output {
918        SymbolicFelt::from(self) - rhs
919    }
920}
921
922impl<F: Field, EF: ExtensionField<F>, E: Any> Add<E> for Ext<F, EF> {
923    type Output = SymbolicExt<F, EF>;
924
925    fn add(self, rhs: E) -> Self::Output {
926        let rhs: ExtOperand<F, EF> = rhs.to_operand();
927        let self_sym = self.to_operand().symbolic();
928        self_sym + rhs
929    }
930}
931
932impl<F: Field, EF: ExtensionField<F>, E: Any> Mul<E> for Ext<F, EF> {
933    type Output = SymbolicExt<F, EF>;
934
935    fn mul(self, rhs: E) -> Self::Output {
936        let self_sym = self.to_operand().symbolic();
937        self_sym * rhs
938    }
939}
940
941impl<F: Field, EF: ExtensionField<F>, E: Any> Sub<E> for Ext<F, EF> {
942    type Output = SymbolicExt<F, EF>;
943
944    fn sub(self, rhs: E) -> Self::Output {
945        let self_sym = self.to_operand().symbolic();
946        self_sym - rhs
947    }
948}
949
950impl<F: Field, EF: ExtensionField<F>, E: Any> Div<E> for Ext<F, EF> {
951    type Output = SymbolicExt<F, EF>;
952
953    fn div(self, rhs: E) -> Self::Output {
954        let self_sym = self.to_operand().symbolic();
955        self_sym / rhs
956    }
957}
958
959impl<F: Field, EF: ExtensionField<F>> Add<SymbolicExt<F, EF>> for Felt<F> {
960    type Output = SymbolicExt<F, EF>;
961
962    fn add(self, rhs: SymbolicExt<F, EF>) -> Self::Output {
963        let self_sym = self.to_operand().symbolic();
964        self_sym + rhs
965    }
966}
967
968impl<F: Field, EF: ExtensionField<F>> Mul<SymbolicExt<F, EF>> for Felt<F> {
969    type Output = SymbolicExt<F, EF>;
970
971    fn mul(self, rhs: SymbolicExt<F, EF>) -> Self::Output {
972        let self_sym = self.to_operand().symbolic();
973        self_sym * rhs
974    }
975}
976
977impl<F: Field, EF: ExtensionField<F>> Sub<SymbolicExt<F, EF>> for Felt<F> {
978    type Output = SymbolicExt<F, EF>;
979
980    fn sub(self, rhs: SymbolicExt<F, EF>) -> Self::Output {
981        let self_sym = self.to_operand().symbolic();
982        self_sym - rhs
983    }
984}
985
986impl<F: Field, EF: ExtensionField<F>> Div<SymbolicExt<F, EF>> for Felt<F> {
987    type Output = SymbolicExt<F, EF>;
988
989    fn div(self, rhs: SymbolicExt<F, EF>) -> Self::Output {
990        let self_sym = self.to_operand().symbolic();
991        self_sym / rhs
992    }
993}
994
995impl<F: Field> Div for Felt<F> {
996    type Output = SymbolicFelt<F>;
997
998    fn div(self, rhs: Self) -> Self::Output {
999        SymbolicFelt::<F>::from(self) / rhs
1000    }
1001}
1002
1003impl<F: Field> Div<F> for Felt<F> {
1004    type Output = SymbolicFelt<F>;
1005
1006    fn div(self, rhs: F) -> Self::Output {
1007        SymbolicFelt::from(self) / rhs
1008    }
1009}
1010
1011impl<F: Field> Div<Felt<F>> for SymbolicFelt<F> {
1012    type Output = SymbolicFelt<F>;
1013
1014    fn div(self, rhs: Felt<F>) -> Self::Output {
1015        self / SymbolicFelt::from(rhs)
1016    }
1017}
1018
1019impl<F: Field> Div<F> for SymbolicFelt<F> {
1020    type Output = SymbolicFelt<F>;
1021
1022    fn div(self, rhs: F) -> Self::Output {
1023        self / SymbolicFelt::from(rhs)
1024    }
1025}
1026
1027impl<N: Field> Product for SymbolicVar<N> {
1028    fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
1029        iter.fold(SymbolicVar::ONE, |acc, x| acc * x)
1030    }
1031}
1032
1033impl<N: Field> Sum for SymbolicVar<N> {
1034    fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
1035        iter.fold(SymbolicVar::ZERO, |acc, x| acc + x)
1036    }
1037}
1038
1039impl<N: Field> AddAssign for SymbolicVar<N> {
1040    fn add_assign(&mut self, rhs: Self) {
1041        *self = self.clone() + rhs;
1042    }
1043}
1044
1045impl<N: Field> SubAssign for SymbolicVar<N> {
1046    fn sub_assign(&mut self, rhs: Self) {
1047        *self = self.clone() - rhs;
1048    }
1049}
1050
1051impl<N: Field> MulAssign for SymbolicVar<N> {
1052    fn mul_assign(&mut self, rhs: Self) {
1053        *self = self.clone() * rhs;
1054    }
1055}
1056
1057impl<N: Field> Default for SymbolicVar<N> {
1058    fn default() -> Self {
1059        SymbolicVar::ZERO
1060    }
1061}
1062
1063impl<F: Field> Sum for SymbolicFelt<F> {
1064    fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
1065        iter.fold(SymbolicFelt::ZERO, |acc, x| acc + x)
1066    }
1067}
1068
1069impl<F: Field> Product for SymbolicFelt<F> {
1070    fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
1071        iter.fold(SymbolicFelt::ONE, |acc, x| acc * x)
1072    }
1073}
1074
1075impl<F: Field> AddAssign for SymbolicFelt<F> {
1076    fn add_assign(&mut self, rhs: Self) {
1077        *self = self.clone() + rhs;
1078    }
1079}
1080
1081impl<F: Field> SubAssign for SymbolicFelt<F> {
1082    fn sub_assign(&mut self, rhs: Self) {
1083        *self = self.clone() - rhs;
1084    }
1085}
1086
1087impl<F: Field> MulAssign for SymbolicFelt<F> {
1088    fn mul_assign(&mut self, rhs: Self) {
1089        *self = self.clone() * rhs;
1090    }
1091}
1092
1093impl<F: Field> Default for SymbolicFelt<F> {
1094    fn default() -> Self {
1095        SymbolicFelt::ZERO
1096    }
1097}
1098
1099impl<F: Field, EF: ExtensionField<F>> Sum for SymbolicExt<F, EF> {
1100    fn sum<I: Iterator<Item = Self>>(iter: I) -> Self {
1101        iter.fold(SymbolicExt::ZERO, |acc, x| acc + x)
1102    }
1103}
1104
1105impl<F: Field, EF: ExtensionField<F>> Product for SymbolicExt<F, EF> {
1106    fn product<I: Iterator<Item = Self>>(iter: I) -> Self {
1107        iter.fold(SymbolicExt::ONE, |acc, x| acc * x)
1108    }
1109}
1110
1111impl<F: Field, EF: ExtensionField<F>> Default for SymbolicExt<F, EF> {
1112    fn default() -> Self {
1113        SymbolicExt::ZERO
1114    }
1115}
1116
1117impl<F: Field, EF: ExtensionField<F>, E: Any> AddAssign<E> for SymbolicExt<F, EF> {
1118    fn add_assign(&mut self, rhs: E) {
1119        *self = self.clone() + rhs;
1120    }
1121}
1122
1123impl<F: Field, EF: ExtensionField<F>, E: Any> SubAssign<E> for SymbolicExt<F, EF> {
1124    fn sub_assign(&mut self, rhs: E) {
1125        *self = self.clone() - rhs;
1126    }
1127}
1128
1129impl<F: Field, EF: ExtensionField<F>, E: Any> MulAssign<E> for SymbolicExt<F, EF> {
1130    fn mul_assign(&mut self, rhs: E) {
1131        *self = self.clone() * rhs;
1132    }
1133}
1134
1135impl<F: Field, EF: ExtensionField<F>, E: Any> DivAssign<E> for SymbolicExt<F, EF> {
1136    fn div_assign(&mut self, rhs: E) {
1137        *self = self.clone() / rhs;
1138    }
1139}
1140
1141impl<F: Field, EF: ExtensionField<F>, E: Any> ExtensionOperand<F, EF> for E {
1142    fn to_operand(self) -> ExtOperand<F, EF> {
1143        match self.type_id() {
1144            ty if ty == TypeId::of::<F>() => {
1145                // *Safety*: We know that E is a F and we can transmute it to F which implements
1146                // the Copy trait.
1147                let value = unsafe { mem::transmute_copy::<E, F>(&self) };
1148                ExtOperand::<F, EF>::Base(value)
1149            }
1150            ty if ty == TypeId::of::<EF>() => {
1151                // *Safety*: We know that E is a EF and we can transmute it to EF which implements
1152                // the Copy trait.
1153                let value = unsafe { mem::transmute_copy::<E, EF>(&self) };
1154                ExtOperand::<F, EF>::Const(value)
1155            }
1156            ty if ty == TypeId::of::<Felt<F>>() => {
1157                // *Safety*: We know that E is a Felt<F> and we can transmute it to Felt<F> which
1158                // implements the Copy trait.
1159                let value = unsafe { mem::transmute_copy::<E, Felt<F>>(&self) };
1160                ExtOperand::<F, EF>::Felt(value)
1161            }
1162            ty if ty == TypeId::of::<Ext<F, EF>>() => {
1163                // *Safety*: We know that E is a Ext<F, EF> and we can transmute it to Ext<F, EF>
1164                // which implements the Copy trait.
1165                let value = unsafe { mem::transmute_copy::<E, Ext<F, EF>>(&self) };
1166                ExtOperand::<F, EF>::Ext(value)
1167            }
1168            ty if ty == TypeId::of::<SymbolicFelt<F>>() => {
1169                // *Safety*: We know that E is a Symbolic Felt<F> and we can transmute it to
1170                // SymbolicFelt<F> but we need to clone the pointer.
1171                let value_ref = unsafe { mem::transmute::<&E, &SymbolicFelt<F>>(&self) };
1172                let value = value_ref.clone();
1173                ExtOperand::<F, EF>::SymFelt(value)
1174            }
1175            ty if ty == TypeId::of::<SymbolicExt<F, EF>>() => {
1176                // *Safety*: We know that E is a SymbolicExt<F, EF> and we can transmute it to
1177                // SymbolicExt<F, EF> but we need to clone the pointer.
1178                let value_ref = unsafe { mem::transmute::<&E, &SymbolicExt<F, EF>>(&self) };
1179                let value = value_ref.clone();
1180                ExtOperand::<F, EF>::Sym(value)
1181            }
1182            ty if ty == TypeId::of::<ExtOperand<F, EF>>() => {
1183                let value_ref = unsafe { mem::transmute::<&E, &ExtOperand<F, EF>>(&self) };
1184                value_ref.clone()
1185            }
1186            _ => unimplemented!("unsupported type"),
1187        }
1188    }
1189}
1190
1191impl<F: Field> Add<SymbolicFelt<F>> for Felt<F> {
1192    type Output = SymbolicFelt<F>;
1193
1194    fn add(self, rhs: SymbolicFelt<F>) -> Self::Output {
1195        SymbolicFelt::<F>::from(self) + rhs
1196    }
1197}
1198
1199impl<F: Field, EF: ExtensionField<F>> From<Felt<F>> for SymbolicExt<F, EF> {
1200    fn from(value: Felt<F>) -> Self {
1201        value.to_operand().symbolic()
1202    }
1203}
1204
1205impl<F: Field, EF: ExtensionField<F>> Neg for Ext<F, EF> {
1206    type Output = SymbolicExt<F, EF>;
1207    fn neg(self) -> Self::Output {
1208        -SymbolicExt::from(self)
1209    }
1210}
1211
1212impl<F: Field> Neg for Felt<F> {
1213    type Output = SymbolicFelt<F>;
1214
1215    fn neg(self) -> Self::Output {
1216        -SymbolicFelt::from(self)
1217    }
1218}
1219
1220impl<N: Field> Neg for Var<N> {
1221    type Output = SymbolicVar<N>;
1222
1223    fn neg(self) -> Self::Output {
1224        -SymbolicVar::from(self)
1225    }
1226}
1227
1228impl<F: Field> MulAssign<Felt<F>> for SymbolicFelt<F> {
1229    fn mul_assign(&mut self, rhs: Felt<F>) {
1230        *self = self.clone() * Self::from(rhs);
1231    }
1232}
1233
1234impl<F: Field> Mul<SymbolicFelt<F>> for Felt<F> {
1235    type Output = SymbolicFelt<F>;
1236
1237    fn mul(self, rhs: SymbolicFelt<F>) -> Self::Output {
1238        SymbolicFelt::<F>::from(self) * rhs
1239    }
1240}
1241
1242impl<N: Field> Mul<SymbolicVar<N>> for Var<N> {
1243    type Output = SymbolicVar<N>;
1244
1245    fn mul(self, rhs: SymbolicVar<N>) -> Self::Output {
1246        SymbolicVar::<N>::from(self) * rhs
1247    }
1248}
1249
1250impl<N: Field, RHS: Into<SymbolicVar<N>>> Add<RHS> for Var<N> {
1251    type Output = SymbolicVar<N>;
1252
1253    fn add(self, rhs: RHS) -> Self::Output {
1254        SymbolicVar::from(self) + rhs.into()
1255    }
1256}
1257
1258impl<N: Field, RHS: Into<SymbolicVar<N>>> Sub<RHS> for Var<N> {
1259    type Output = SymbolicVar<N>;
1260
1261    fn sub(self, rhs: RHS) -> Self::Output {
1262        SymbolicVar::from(self) - rhs.into()
1263    }
1264}
1265
1266impl<N: PrimeField, RHS: Into<SymbolicVar<N>>> Add<RHS> for Usize<N> {
1267    type Output = SymbolicVar<N>;
1268
1269    fn add(self, rhs: RHS) -> Self::Output {
1270        SymbolicVar::from(self) + rhs.into()
1271    }
1272}
1273
1274impl<N: PrimeField, RHS: Into<SymbolicVar<N>>> Sub<RHS> for Usize<N> {
1275    type Output = SymbolicVar<N>;
1276
1277    fn sub(self, rhs: RHS) -> Self::Output {
1278        SymbolicVar::from(self) - rhs.into()
1279    }
1280}
1281
1282impl<N: PrimeField, RHS: Into<SymbolicVar<N>>> Mul<RHS> for Usize<N> {
1283    type Output = SymbolicVar<N>;
1284
1285    fn mul(self, rhs: RHS) -> Self::Output {
1286        SymbolicVar::from(self) * rhs.into()
1287    }
1288}
1289
1290impl<N: PrimeField> From<Usize<N>> for SymbolicVar<N> {
1291    fn from(value: Usize<N>) -> Self {
1292        match value {
1293            Usize::Const(n) => SymbolicVar::from(*n.borrow()),
1294            Usize::Var(n) => SymbolicVar::from(n),
1295        }
1296    }
1297}
1298
1299impl<N: PrimeField, RHS: Into<SymbolicVar<N>>> Add<RHS> for RVar<N> {
1300    type Output = SymbolicVar<N>;
1301
1302    fn add(self, rhs: RHS) -> Self::Output {
1303        SymbolicVar::from(self) + rhs.into()
1304    }
1305}
1306
1307impl<N: PrimeField, RHS: Into<SymbolicVar<N>>> Sub<RHS> for RVar<N> {
1308    type Output = SymbolicVar<N>;
1309
1310    fn sub(self, rhs: RHS) -> Self::Output {
1311        SymbolicVar::from(self) - rhs.into()
1312    }
1313}
1314
1315impl<N: PrimeField, RHS: Into<SymbolicVar<N>>> Mul<RHS> for RVar<N> {
1316    type Output = SymbolicVar<N>;
1317
1318    fn mul(self, rhs: RHS) -> Self::Output {
1319        SymbolicVar::from(self) * rhs.into()
1320    }
1321}
1322
1323impl<N: Field> From<RVar<N>> for SymbolicVar<N> {
1324    fn from(value: RVar<N>) -> Self {
1325        match value {
1326            RVar::Const(n) => SymbolicVar::from(n),
1327            RVar::Val(n) => SymbolicVar::from(n),
1328        }
1329    }
1330}
1331
1332impl<N: PrimeField> From<usize> for RVar<N> {
1333    fn from(value: usize) -> Self {
1334        Self::from_field(N::from_canonical_usize(value))
1335    }
1336}
1337
1338impl<N: Field> From<Var<N>> for RVar<N> {
1339    fn from(value: Var<N>) -> Self {
1340        RVar::Val(value)
1341    }
1342}