solar_sema/
eval.rs

1use crate::{builtins::Builtin, hir, ty::Gcx};
2use alloy_primitives::{B256, U256, keccak256};
3use num_bigint::{BigInt, BigUint, Sign};
4use num_traits::{One, Signed, Zero};
5use solar_ast::{LitKind, StrKind};
6use solar_interface::{ByteSymbol, Span, diagnostics::ErrorGuaranteed};
7use std::fmt;
8
9const RECURSION_LIMIT: usize = 64;
10const MAX_BITS: u64 = solar_ast::TypeSize::MAX as u64;
11
12// TODO: `convertType` for truncating and extending correctly: https://github.com/argotorg/solidity/blob/de1a017ccb935d149ed6bcbdb730d89883f8ce02/libsolidity/analysis/ConstantEvaluator.cpp#L234
13
14/// Computes the ERC-7201 storage namespace base slot.
15///
16/// Reference: <https://docs.soliditylang.org/en/latest/units-and-global-variables.html#mathematical-and-cryptographic-functions>
17pub fn erc7201_slot(namespace_id: &[u8]) -> B256 {
18    let inner = keccak256(namespace_id);
19    let inner = U256::from_be_bytes(inner.0).wrapping_sub(U256::from(1));
20    let mut outer = keccak256(inner.to_be_bytes::<32>());
21    outer.0[31] = 0;
22    outer
23}
24
25/// Evaluates the given array size expression, emitting an error diagnostic if it fails.
26pub fn eval_array_len(gcx: Gcx<'_>, size: &hir::Expr<'_>) -> Result<U256, ErrorGuaranteed> {
27    match ConstantEvaluator::new(gcx).eval(size) {
28        Ok(int) => {
29            let Some(int) = int.as_u256() else {
30                let msg = "array length cannot be negative";
31                return Err(gcx.dcx().emit_err(size.span, msg));
32            };
33            if int.is_zero() {
34                let msg = "array length must be greater than zero";
35                Err(gcx.dcx().emit_err(size.span, msg))
36            } else {
37                Ok(int)
38            }
39        }
40        Err(guar) => Err(guar),
41    }
42}
43
44/// Evaluates Solidity constant expressions.
45///
46/// This supports the source-level constants needed by semantic analysis and
47/// codegen's HIR lowering pre-folds. It does not evaluate runtime-dependent
48/// expressions such as function calls or memory allocation.
49pub struct ConstantEvaluator<'gcx> {
50    pub gcx: Gcx<'gcx>,
51    depth: usize,
52}
53
54type EvalResult = Result<ConstValue, EvalError>;
55
56impl<'gcx> ConstantEvaluator<'gcx> {
57    /// Creates a new constant evaluator.
58    pub fn new(gcx: Gcx<'gcx>) -> Self {
59        Self { gcx, depth: 0 }
60    }
61
62    /// Evaluates the given expression, emitting an error diagnostic if it fails.
63    pub fn eval(&mut self, expr: &hir::Expr<'_>) -> Result<IntScalar, ErrorGuaranteed> {
64        self.try_eval(expr).map_err(|err| self.emit_eval_error(expr, err))
65    }
66
67    /// Evaluates the given expression, returning an error if it fails.
68    pub fn try_eval(&mut self, expr: &hir::Expr<'_>) -> Result<IntScalar, EvalError> {
69        self.try_eval_value(expr).and_then(ConstValue::into_integer)
70    }
71
72    /// Evaluates the given expression to a typed constant value, emitting an
73    /// error diagnostic if it fails.
74    pub fn eval_value(&mut self, expr: &hir::Expr<'_>) -> Result<ConstValue, ErrorGuaranteed> {
75        self.try_eval_value(expr).map_err(|err| self.emit_eval_error(expr, err))
76    }
77
78    /// Evaluates the given expression to a typed constant value, returning an
79    /// error if it fails.
80    pub fn try_eval_value(&mut self, expr: &hir::Expr<'_>) -> EvalResult {
81        self.depth += 1;
82        if self.depth > RECURSION_LIMIT {
83            return Err(EE::RecursionLimitReached.spanned(expr.span));
84        }
85        let mut res = self.eval_expr(expr);
86        if let Err(e) = &mut res
87            && e.span.is_dummy()
88        {
89            e.span = expr.span;
90        }
91        self.depth = self.depth.checked_sub(1).unwrap();
92        res
93    }
94
95    /// Emits a diagnostic for the given evaluation error.
96    pub fn emit_eval_error(&self, expr: &hir::Expr<'_>, err: EvalError) -> ErrorGuaranteed {
97        match err.kind {
98            EE::AlreadyEmitted(guar) => guar,
99            _ => {
100                let msg = format!("failed to evaluate constant: {}", err.kind.msg());
101                let label = "evaluation of constant value failed here";
102                self.gcx.dcx().emit_err_label(expr.span, msg, err.span, label)
103            }
104        }
105    }
106
107    fn eval_expr(&mut self, expr: &hir::Expr<'_>) -> EvalResult {
108        let expr = expr.peel_parens();
109        match expr.kind {
110            // hir::ExprKind::Array(_) => unimplemented!(),
111            // hir::ExprKind::Assign(_, _, _) => unimplemented!(),
112            hir::ExprKind::Binary(l, bin_op, r) => {
113                let l = self.try_eval_value(l)?;
114                let r = self.try_eval_value(r)?;
115                l.binop(r, bin_op.kind).map_err(Into::into)
116            }
117            hir::ExprKind::Call(callee, ref args, opts) => self.eval_call(callee, args, opts),
118            // hir::ExprKind::Delete(_) => unimplemented!(),
119            hir::ExprKind::Ident(res) => {
120                // Ignore invalid overloads since they will get correctly detected later.
121                let Some(v) = res.iter().find_map(|res| res.as_variable()) else {
122                    return Err(EE::NonConstantVar.into());
123                };
124
125                let v = self.gcx.hir.variable(v);
126                if v.mutability != Some(hir::VarMut::Constant) {
127                    return Err(EE::NonConstantVar.into());
128                }
129                self.try_eval_value(v.initializer.expect("constant variable has no initializer"))
130            }
131            // hir::ExprKind::Index(_, _) => unimplemented!(),
132            // hir::ExprKind::Slice(_, _, _) => unimplemented!(),
133            hir::ExprKind::Lit(lit) => self.eval_lit(lit),
134            // hir::ExprKind::Member(_, _) => unimplemented!(),
135            // hir::ExprKind::New(_) => unimplemented!(),
136            // hir::ExprKind::Payable(_) => unimplemented!(),
137            hir::ExprKind::Ternary(cond, t, f) => {
138                let ConstValue::Bool(cond) = self.try_eval_value(cond)? else {
139                    return Err(EE::UnsupportedExpr.into());
140                };
141                if cond { self.try_eval_value(t) } else { self.try_eval_value(f) }
142            }
143            // hir::ExprKind::Tuple(_) => unimplemented!(),
144            // hir::ExprKind::TypeCall(_) => unimplemented!(),
145            // hir::ExprKind::Type(_) => unimplemented!(),
146            hir::ExprKind::Unary(un_op, v) => {
147                let v = self.try_eval_value(v)?;
148                v.unop(un_op.kind).map_err(Into::into)
149            }
150            hir::ExprKind::Err(guar) => Err(EE::AlreadyEmitted(guar).into()),
151            _ => Err(EE::UnsupportedExpr.into()),
152        }
153    }
154
155    fn eval_call(
156        &mut self,
157        callee: &hir::Expr<'_>,
158        args: &hir::CallArgs<'_>,
159        opts: Option<&hir::CallOptions<'_>>,
160    ) -> EvalResult {
161        if opts.is_none()
162            && let hir::ExprKind::Ident(res) = callee.peel_parens().kind
163            && matches!(res.first(), Some(hir::Res::Builtin(Builtin::Erc7201)))
164            && let hir::CallArgsKind::Unnamed([arg]) = args.kind
165            && let ConstValue::String(namespace_id) = self.try_eval_value(arg)?
166        {
167            return Ok(ConstValue::Integer(IntScalar::new(
168                erc7201_slot(namespace_id.as_byte_str()).into(),
169            )));
170        }
171        Err(EE::UnsupportedExpr.into())
172    }
173
174    fn eval_lit(&mut self, lit: &hir::Lit<'_>) -> EvalResult {
175        match lit.kind {
176            LitKind::Str(StrKind::Str | StrKind::Unicode, s, _) => Ok(ConstValue::String(s)),
177            LitKind::Str(StrKind::Hex, _, _) => Err(EE::UnsupportedLiteral.into()),
178            LitKind::Number(n) => Ok(ConstValue::Integer(IntScalar::new(n))),
179            // LitKind::Rational(ratio) => todo!(),
180            LitKind::Address(address) => {
181                Ok(ConstValue::Integer(IntScalar::from_be_bytes(address.as_slice())))
182            }
183            LitKind::Bool(bool) => Ok(ConstValue::Bool(bool)),
184            LitKind::Err(guar) => Err(EE::AlreadyEmitted(guar).into()),
185            _ => Err(EE::UnsupportedLiteral.into()),
186        }
187    }
188}
189
190/// A typed Solidity constant value.
191#[derive(Debug)]
192pub enum ConstValue {
193    /// Integer-like constant value.
194    Integer(IntScalar),
195    /// Boolean constant value.
196    Bool(bool),
197    /// String constant value.
198    String(ByteSymbol),
199}
200
201impl ConstValue {
202    /// Converts this value into an integer constant.
203    pub fn into_integer(self) -> Result<IntScalar, EvalError> {
204        match self {
205            Self::Integer(value) => Ok(value),
206            Self::Bool(_) => Err(EE::UnsupportedExpr.into()),
207            Self::String(_) => Err(EE::UnsupportedLiteral.into()),
208        }
209    }
210
211    /// Applies the given unary operation to this value.
212    pub fn unop(self, op: hir::UnOpKind) -> Result<Self, EE> {
213        Ok(match (self, op) {
214            (Self::Integer(value), op) => Self::Integer(value.unop(op)?),
215            (Self::Bool(value), hir::UnOpKind::Not) => Self::Bool(!value),
216            (Self::Bool(_) | Self::String(_), _) => return Err(EE::UnsupportedUnaryOp),
217        })
218    }
219
220    /// Applies the given binary operation to this value.
221    pub fn binop(self, rhs: Self, op: hir::BinOpKind) -> Result<Self, EE> {
222        use hir::BinOpKind::*;
223        Ok(match (self, rhs) {
224            (Self::Integer(lhs), Self::Integer(rhs)) => match op {
225                Lt => Self::Bool(lhs.data < rhs.data),
226                Le => Self::Bool(lhs.data <= rhs.data),
227                Gt => Self::Bool(lhs.data > rhs.data),
228                Ge => Self::Bool(lhs.data >= rhs.data),
229                Eq => Self::Bool(lhs.data == rhs.data),
230                Ne => Self::Bool(lhs.data != rhs.data),
231                Add | Sub | Mul | Div | Rem | Pow | BitOr | BitAnd | BitXor | Shr | Shl | Sar => {
232                    Self::Integer(lhs.binop(rhs, op)?)
233                }
234                Or | And => return Err(EE::UnsupportedBinaryOp),
235            },
236            (Self::Bool(lhs), Self::Bool(rhs)) => match op {
237                And => Self::Bool(lhs && rhs),
238                Or => Self::Bool(lhs || rhs),
239                Eq => Self::Bool(lhs == rhs),
240                Ne => Self::Bool(lhs != rhs),
241                BitAnd => Self::Bool(lhs & rhs),
242                BitOr => Self::Bool(lhs | rhs),
243                BitXor => Self::Bool(lhs ^ rhs),
244                _ => return Err(EE::UnsupportedBinaryOp),
245            },
246            _ => return Err(EE::UnsupportedBinaryOp),
247        })
248    }
249}
250
251/// Represents an integer value for constant evaluation.
252#[derive(Debug)]
253pub struct IntScalar {
254    data: BigInt,
255}
256
257impl IntScalar {
258    /// Creates a new non-negative integer value.
259    pub fn new(data: U256) -> Self {
260        Self { data: Self::bigint_from_u256(data) }
261    }
262
263    /// Creates a new integer value from a boolean.
264    pub fn from_bool(value: bool) -> Self {
265        Self::new(U256::from(value as u8))
266    }
267
268    /// Creates a new integer value from big-endian bytes.
269    ///
270    /// # Panics
271    ///
272    /// Panics if `bytes` is empty or has a length greater than 32.
273    pub fn from_be_bytes(bytes: &[u8]) -> Self {
274        Self::new(U256::from_be_slice(bytes))
275    }
276
277    /// Returns the bit length of the integer value.
278    ///
279    /// This is the number of bits needed for the literal type.
280    pub fn bit_len(&self) -> u64 {
281        Self::bits(&self.data)
282    }
283
284    /// Returns whether the value is negative.
285    pub fn is_negative(&self) -> bool {
286        self.data.is_negative()
287    }
288
289    /// Returns whether the value requires a signed integer type.
290    pub fn is_signed(&self) -> bool {
291        self.is_negative()
292    }
293
294    /// Returns whether the integer value is zero.
295    pub fn is_zero(&self) -> bool {
296        self.data.is_zero()
297    }
298
299    /// Returns the non-negative integer value as unsigned data.
300    pub fn as_u256(&self) -> Option<U256> {
301        let data = self.data.to_biguint()?;
302        U256::try_from_le_slice(&data.to_bytes_le())
303    }
304
305    /// Returns the 256-bit two's-complement EVM word for this integer value.
306    pub fn as_evm_word(&self) -> U256 {
307        if let Some(value) = self.as_u256() {
308            return value;
309        }
310        let magnitude = U256::try_from_le_slice(&self.data.magnitude().to_bytes_le())
311            .expect("constant evaluator keeps integers within 256 bits");
312        U256::ZERO.wrapping_sub(magnitude)
313    }
314
315    /// Converts the integer value to a boolean.
316    pub fn to_bool(&self) -> bool {
317        !self.data.is_zero()
318    }
319
320    fn bigint_from_u256(data: U256) -> BigInt {
321        BigInt::from_bytes_be(Sign::Plus, &data.to_be_bytes::<32>())
322    }
323
324    fn checked(data: BigInt) -> Result<Self, EE> {
325        if Self::bits(&data) > MAX_BITS {
326            return Err(EE::ArithmeticOverflow);
327        }
328        Ok(Self { data })
329    }
330
331    fn bits(data: &BigInt) -> u64 {
332        if data.is_zero() {
333            return 1;
334        }
335        if data.is_positive() {
336            return data.bits();
337        }
338        let abs = data.magnitude();
339        // Signed N-bit two's-complement values cover [-2^(N - 1), 2^(N - 1) - 1].
340        // Negative powers of two therefore fit in one fewer value bit than other negatives.
341        if Self::is_power_of_two(abs) { abs.bits() } else { abs.bits() + 1 }
342    }
343
344    fn is_power_of_two(value: &BigUint) -> bool {
345        !value.is_zero() && (value & (value - BigUint::one())).is_zero()
346    }
347
348    fn negate(self) -> Result<Self, EE> {
349        Self::checked(-self.data)
350    }
351
352    fn shift_amount(r: Self) -> Option<usize> {
353        r.as_u256()?.try_into().ok()
354    }
355
356    fn bitop(self, r: Self, f: impl FnOnce(BigInt, BigInt) -> BigInt) -> Result<Self, EE> {
357        Self::checked(f(self.data, r.data))
358    }
359
360    /// Applies the given unary operation to this value.
361    pub fn unop(self, op: hir::UnOpKind) -> Result<Self, EE> {
362        Ok(match op {
363            hir::UnOpKind::PreInc
364            | hir::UnOpKind::PreDec
365            | hir::UnOpKind::PostInc
366            | hir::UnOpKind::PostDec => return Err(EE::UnsupportedUnaryOp),
367            hir::UnOpKind::Not | hir::UnOpKind::BitNot => Self::checked(!self.data)?,
368            hir::UnOpKind::Neg => self.negate()?,
369        })
370    }
371
372    /// Applies the given binary operation to this value.
373    ///
374    /// For literal arithmetic, this preserves the exact mathematical value.
375    pub fn binop(self, r: Self, op: hir::BinOpKind) -> Result<Self, EE> {
376        use hir::BinOpKind::*;
377        Ok(match op {
378            Add => Self::checked(self.data + r.data)?,
379            Sub => Self::checked(self.data - r.data)?,
380            Mul => Self::checked(self.data * r.data)?,
381            Div => {
382                if r.data.is_zero() {
383                    return Err(EE::DivisionByZero);
384                }
385                Self::checked(self.data / r.data)?
386            }
387            Rem => {
388                if r.data.is_zero() {
389                    return Err(EE::DivisionByZero);
390                }
391                Self::checked(self.data % r.data)?
392            }
393            Pow => {
394                if r.is_negative() {
395                    return Err(EE::ArithmeticOverflow);
396                }
397                self.checked_pow(r)?
398            }
399            BitOr => self.bitop(r, |a, b| a | b)?,
400            BitAnd => self.bitop(r, |a, b| a & b)?,
401            BitXor => self.bitop(r, |a, b| a ^ b)?,
402            Shr => {
403                let r = Self::shift_amount(r).ok_or(EE::ArithmeticOverflow)?;
404                Self::checked(self.data >> r)?
405            }
406            Shl => self.checked_shl(r)?,
407            Sar => return Err(EE::UnsupportedBinaryOp),
408            Lt | Le | Gt | Ge | Eq | Ne | Or | And => return Err(EE::UnsupportedBinaryOp),
409        })
410    }
411
412    fn checked_shl(self, r: Self) -> Result<Self, EE> {
413        if self.data.is_zero() {
414            return Ok(self);
415        }
416        let shift: u64 = r
417            .as_u256()
418            .ok_or(EE::ArithmeticOverflow)?
419            .try_into()
420            .map_err(|_| EE::ArithmeticOverflow)?;
421        let bits = Self::bits(&self.data);
422        if shift > MAX_BITS.saturating_sub(bits) {
423            return Err(EE::ArithmeticOverflow);
424        }
425        Self::checked(self.data << usize::try_from(shift).map_err(|_| EE::ArithmeticOverflow)?)
426    }
427
428    fn checked_pow(self, r: Self) -> Result<Self, EE> {
429        if self.data.is_zero() {
430            return Ok(self);
431        }
432        if self.data.is_one() {
433            return Ok(self);
434        }
435        if self.data == BigInt::from(-1) {
436            let exp = r.as_u256().ok_or(EE::ArithmeticOverflow)?;
437            let is_odd = exp.bit(0);
438            return Self::checked(if is_odd { self.data } else { BigInt::one() });
439        }
440        let exp = r.as_u256().ok_or(EE::ArithmeticOverflow)?;
441        if exp > U256::from(MAX_BITS) {
442            return Err(EE::ArithmeticOverflow);
443        }
444        let exp = exp.try_into().map_err(|_| EE::ArithmeticOverflow)?;
445        Self::checked(self.data.pow(exp))
446    }
447}
448
449#[derive(Debug)]
450pub enum EvalErrorKind {
451    RecursionLimitReached,
452    ArithmeticOverflow,
453    DivisionByZero,
454    UnsupportedLiteral,
455    UnsupportedUnaryOp,
456    UnsupportedBinaryOp,
457    UnsupportedExpr,
458    NonConstantVar,
459    AlreadyEmitted(ErrorGuaranteed),
460}
461use EvalErrorKind as EE;
462
463impl EvalErrorKind {
464    pub fn spanned(self, span: Span) -> EvalError {
465        EvalError { kind: self, span }
466    }
467
468    fn msg(&self) -> &'static str {
469        match self {
470            Self::RecursionLimitReached => "recursion limit reached",
471            Self::ArithmeticOverflow => "arithmetic overflow",
472            Self::DivisionByZero => "attempted to divide by zero",
473            Self::UnsupportedLiteral => "unsupported literal",
474            Self::UnsupportedUnaryOp => "unsupported unary operation",
475            Self::UnsupportedBinaryOp => "unsupported binary operation",
476            Self::UnsupportedExpr => "unsupported expression",
477            Self::NonConstantVar => "only constant variables are allowed",
478            Self::AlreadyEmitted(_) => unreachable!(),
479        }
480    }
481}
482
483#[derive(Debug)]
484pub struct EvalError {
485    pub span: Span,
486    pub kind: EvalErrorKind,
487}
488
489impl From<EE> for EvalError {
490    fn from(value: EE) -> Self {
491        Self { kind: value, span: Span::DUMMY }
492    }
493}
494
495impl fmt::Display for EvalError {
496    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
497        self.kind.msg().fmt(f)
498    }
499}
500
501impl std::error::Error for EvalError {}
502
503#[cfg(test)]
504mod tests {
505    use super::erc7201_slot;
506    use alloy_primitives::b256;
507
508    #[test]
509    fn erc7201_slot_matches_eip_example() {
510        assert_eq!(
511            erc7201_slot(b"example.main"),
512            b256!("183a6125c38840424c4a85fa12bab2ab606c4b6d0e7cc73c0c06ba5300eab500")
513        );
514    }
515
516    #[test]
517    fn erc7201_slot_subtracts_from_full_inner_hash() {
518        assert_eq!(
519            erc7201_slot(b"85"),
520            b256!("06d0d983459328e82eacb1bf2d6fadfa38a6896e9d4cbfe0e1aa41c6281bab00")
521        );
522    }
523}
solar_sema/eval.rs

solar_sema/
eval.rs
