1 //! Constant evaluation details
3 use std::{collections::HashMap, convert::TryInto, fmt::Display};
5 use chalk_ir::{IntTy, Scalar};
7 expr::{ArithOp, BinaryOp, Expr, Literal, Pat},
10 use hir_expand::name::Name;
11 use la_arena::{Arena, Idx};
13 use crate::{Const, ConstData, ConstValue, Interner, Ty, TyKind};
15 /// Extension trait for [`Const`]
17 /// Is a [`Const`] unknown?
18 fn is_unknown(&self) -> bool;
21 impl ConstExt for Const {
22 fn is_unknown(&self) -> bool {
23 match self.data(Interner).value {
25 chalk_ir::ConstValue::Concrete(chalk_ir::ConcreteConst {
26 interned: ConstScalar::Unknown,
29 // interned concrete anything else
30 chalk_ir::ConstValue::Concrete(..) => false,
34 "is_unknown was called on a non-concrete constant value! {:?}",
43 pub struct ConstEvalCtx<'a> {
44 pub exprs: &'a Arena<Expr>,
45 pub pats: &'a Arena<Pat>,
46 pub local_data: HashMap<Name, ComputedExpr>,
47 pub infer: &'a mut dyn FnMut(Idx<Expr>) -> Ty,
50 #[derive(Debug, Clone)]
51 pub enum ConstEvalError {
52 NotSupported(&'static str),
58 #[derive(Debug, Clone)]
59 pub enum ComputedExpr {
61 Tuple(Box<[ComputedExpr]>),
64 impl Display for ComputedExpr {
65 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
67 ComputedExpr::Literal(l) => match l {
68 Literal::Int(x, _) => {
70 write!(f, "{} ({:#X})", x, x)
75 Literal::Uint(x, _) => {
77 write!(f, "{} ({:#X})", x, x)
82 Literal::Float(x, _) => write!(f, "{}", x),
83 Literal::Bool(x) => write!(f, "{}", x),
84 Literal::Char(x) => write!(f, "{:?}", x),
85 Literal::String(x) => write!(f, "{:?}", x),
86 Literal::ByteString(x) => write!(f, "{:?}", x),
88 ComputedExpr::Tuple(t) => {
91 write!(f, "{}, ", x)?;
99 fn scalar_max(scalar: &Scalar) -> i128 {
102 Scalar::Char => u32::MAX as i128,
103 Scalar::Int(x) => match x {
104 IntTy::Isize => isize::MAX as i128,
105 IntTy::I8 => i8::MAX as i128,
106 IntTy::I16 => i16::MAX as i128,
107 IntTy::I32 => i32::MAX as i128,
108 IntTy::I64 => i64::MAX as i128,
109 IntTy::I128 => i128::MAX as i128,
111 Scalar::Uint(x) => match x {
112 chalk_ir::UintTy::Usize => usize::MAX as i128,
113 chalk_ir::UintTy::U8 => u8::MAX as i128,
114 chalk_ir::UintTy::U16 => u16::MAX as i128,
115 chalk_ir::UintTy::U32 => u32::MAX as i128,
116 chalk_ir::UintTy::U64 => u64::MAX as i128,
117 chalk_ir::UintTy::U128 => i128::MAX as i128, // ignore too big u128 for now
119 Scalar::Float(_) => 0,
123 fn is_valid(scalar: &Scalar, value: i128) -> bool {
125 !matches!(scalar, Scalar::Uint(_)) && -scalar_max(scalar) - 1 <= value
127 value <= scalar_max(scalar)
131 pub fn eval_const(expr: &Expr, ctx: &mut ConstEvalCtx<'_>) -> Result<ComputedExpr, ConstEvalError> {
133 Expr::Literal(l) => Ok(ComputedExpr::Literal(l.clone())),
134 &Expr::UnaryOp { expr, op } => {
135 let ty = &(ctx.infer)(expr);
136 let ev = eval_const(&ctx.exprs[expr], ctx)?;
138 hir_def::expr::UnaryOp::Deref => Err(ConstEvalError::NotSupported("deref")),
139 hir_def::expr::UnaryOp::Not => {
141 ComputedExpr::Literal(Literal::Bool(b)) => {
142 return Ok(ComputedExpr::Literal(Literal::Bool(!b)))
144 ComputedExpr::Literal(Literal::Int(v, _)) => v,
145 ComputedExpr::Literal(Literal::Uint(v, _)) => v
147 .map_err(|_| ConstEvalError::NotSupported("too big u128"))?,
148 _ => return Err(ConstEvalError::NotSupported("this kind of operator")),
150 let r = match ty.kind(Interner) {
151 TyKind::Scalar(Scalar::Uint(x)) => match x {
152 chalk_ir::UintTy::U8 => !(v as u8) as i128,
153 chalk_ir::UintTy::U16 => !(v as u16) as i128,
154 chalk_ir::UintTy::U32 => !(v as u32) as i128,
155 chalk_ir::UintTy::U64 => !(v as u64) as i128,
156 chalk_ir::UintTy::U128 => {
157 return Err(ConstEvalError::NotSupported("negation of u128"))
159 chalk_ir::UintTy::Usize => !(v as usize) as i128,
161 TyKind::Scalar(Scalar::Int(x)) => match x {
162 chalk_ir::IntTy::I8 => !(v as i8) as i128,
163 chalk_ir::IntTy::I16 => !(v as i16) as i128,
164 chalk_ir::IntTy::I32 => !(v as i32) as i128,
165 chalk_ir::IntTy::I64 => !(v as i64) as i128,
166 chalk_ir::IntTy::I128 => !v,
167 chalk_ir::IntTy::Isize => !(v as isize) as i128,
169 _ => return Err(ConstEvalError::NotSupported("unreachable?")),
171 Ok(ComputedExpr::Literal(Literal::Int(r, None)))
173 hir_def::expr::UnaryOp::Neg => {
175 ComputedExpr::Literal(Literal::Int(v, _)) => v,
176 ComputedExpr::Literal(Literal::Uint(v, _)) => v
178 .map_err(|_| ConstEvalError::NotSupported("too big u128"))?,
179 _ => return Err(ConstEvalError::NotSupported("this kind of operator")),
181 Ok(ComputedExpr::Literal(Literal::Int(
182 v.checked_neg().ok_or_else(|| {
183 ConstEvalError::Panic("overflow in negation".to_string())
190 &Expr::BinaryOp { lhs, rhs, op } => {
191 let ty = &(ctx.infer)(lhs);
192 let lhs = eval_const(&ctx.exprs[lhs], ctx)?;
193 let rhs = eval_const(&ctx.exprs[rhs], ctx)?;
194 let op = op.ok_or(ConstEvalError::IncompleteExpr)?;
196 ComputedExpr::Literal(Literal::Int(v, _)) => v,
197 ComputedExpr::Literal(Literal::Uint(v, _)) => {
198 v.try_into().map_err(|_| ConstEvalError::NotSupported("too big u128"))?
200 _ => return Err(ConstEvalError::NotSupported("this kind of operator")),
203 ComputedExpr::Literal(Literal::Int(v, _)) => v,
204 ComputedExpr::Literal(Literal::Uint(v, _)) => {
205 v.try_into().map_err(|_| ConstEvalError::NotSupported("too big u128"))?
207 _ => return Err(ConstEvalError::NotSupported("this kind of operator")),
210 BinaryOp::ArithOp(b) => {
211 let panic_arith = ConstEvalError::Panic(
212 "attempt to run invalid arithmetic operation".to_string(),
215 ArithOp::Add => v1.checked_add(v2).ok_or_else(|| panic_arith.clone())?,
216 ArithOp::Mul => v1.checked_mul(v2).ok_or_else(|| panic_arith.clone())?,
217 ArithOp::Sub => v1.checked_sub(v2).ok_or_else(|| panic_arith.clone())?,
218 ArithOp::Div => v1.checked_div(v2).ok_or_else(|| panic_arith.clone())?,
219 ArithOp::Rem => v1.checked_rem(v2).ok_or_else(|| panic_arith.clone())?,
221 .checked_shl(v2.try_into().map_err(|_| panic_arith.clone())?)
222 .ok_or_else(|| panic_arith.clone())?,
224 .checked_shr(v2.try_into().map_err(|_| panic_arith.clone())?)
225 .ok_or_else(|| panic_arith.clone())?,
226 ArithOp::BitXor => v1 ^ v2,
227 ArithOp::BitOr => v1 | v2,
228 ArithOp::BitAnd => v1 & v2,
230 if let TyKind::Scalar(s) = ty.kind(Interner) {
232 return Err(panic_arith);
235 Ok(ComputedExpr::Literal(Literal::Int(r, None)))
237 BinaryOp::LogicOp(_) => Err(ConstEvalError::TypeError),
238 _ => return Err(ConstEvalError::NotSupported("bin op on this operators")),
241 Expr::Block { statements, tail, .. } => {
242 let mut prev_values = HashMap::<Name, Option<ComputedExpr>>::default();
243 for statement in &**statements {
245 &hir_def::expr::Statement::Let { pat, initializer, .. } => {
246 let pat = &ctx.pats[pat];
247 let name = match pat {
248 Pat::Bind { name, subpat, .. } if subpat.is_none() => name.clone(),
250 return Err(ConstEvalError::NotSupported("complex patterns in let"))
253 let value = match initializer {
254 Some(x) => eval_const(&ctx.exprs[x], ctx)?,
257 if !prev_values.contains_key(&name) {
258 let prev = ctx.local_data.insert(name.clone(), value);
259 prev_values.insert(name, prev);
261 ctx.local_data.insert(name, value);
264 &hir_def::expr::Statement::Expr { .. } => {
265 return Err(ConstEvalError::NotSupported("this kind of statement"))
270 &Some(x) => eval_const(&ctx.exprs[x], ctx),
271 None => Ok(ComputedExpr::Tuple(Box::new([]))),
273 // clean up local data, so caller will receive the exact map that passed to us
274 for (name, val) in prev_values {
276 Some(x) => ctx.local_data.insert(name, x),
277 None => ctx.local_data.remove(&name),
283 let name = p.mod_path().as_ident().ok_or(ConstEvalError::NotSupported("big paths"))?;
287 .ok_or(ConstEvalError::NotSupported("Non local name resolution"))?;
290 _ => Err(ConstEvalError::NotSupported("This kind of expression")),
294 pub fn eval_usize(expr: Idx<Expr>, mut ctx: ConstEvalCtx<'_>) -> Option<u64> {
295 let expr = &ctx.exprs[expr];
296 if let Ok(ce) = eval_const(&expr, &mut ctx) {
298 ComputedExpr::Literal(Literal::Int(x, _)) => return x.try_into().ok(),
299 ComputedExpr::Literal(Literal::Uint(x, _)) => return x.try_into().ok(),
306 /// Interns a possibly-unknown target usize
307 pub fn usize_const(value: Option<u64>) -> Const {
309 ty: TyKind::Scalar(chalk_ir::Scalar::Uint(chalk_ir::UintTy::Usize)).intern(Interner),
310 value: ConstValue::Concrete(chalk_ir::ConcreteConst {
311 interned: value.map(ConstScalar::Usize).unwrap_or(ConstScalar::Unknown),