1 //! Constant evaluation details
9 use chalk_ir::{BoundVar, DebruijnIndex, GenericArgData, IntTy, Scalar};
11 expr::{ArithOp, BinaryOp, Expr, ExprId, Literal, Pat, PatId},
13 resolver::{resolver_for_expr, ResolveValueResult, Resolver, ValueNs},
14 type_ref::ConstScalar,
15 ConstId, DefWithBodyId,
17 use la_arena::{Arena, Idx};
21 db::HirDatabase, infer::InferenceContext, lower::ParamLoweringMode, to_placeholder_idx,
22 utils::Generics, Const, ConstData, ConstValue, GenericArg, InferenceResult, Interner, Ty,
26 /// Extension trait for [`Const`]
28 /// Is a [`Const`] unknown?
29 fn is_unknown(&self) -> bool;
32 impl ConstExt for Const {
33 fn is_unknown(&self) -> bool {
34 match self.data(Interner).value {
36 chalk_ir::ConstValue::Concrete(chalk_ir::ConcreteConst {
37 interned: ConstScalar::Unknown,
40 // interned concrete anything else
41 chalk_ir::ConstValue::Concrete(..) => false,
45 "is_unknown was called on a non-concrete constant value! {:?}",
54 pub struct ConstEvalCtx<'a> {
55 pub db: &'a dyn HirDatabase,
56 pub owner: DefWithBodyId,
57 pub exprs: &'a Arena<Expr>,
58 pub pats: &'a Arena<Pat>,
59 pub local_data: HashMap<PatId, ComputedExpr>,
60 infer: &'a InferenceResult,
63 impl ConstEvalCtx<'_> {
64 fn expr_ty(&mut self, expr: ExprId) -> Ty {
65 self.infer[expr].clone()
69 #[derive(Debug, Clone, PartialEq, Eq)]
70 pub enum ConstEvalError {
71 NotSupported(&'static str),
72 SemanticError(&'static str),
78 #[derive(Debug, Clone, PartialEq, Eq)]
79 pub enum ComputedExpr {
81 Tuple(Box<[ComputedExpr]>),
84 impl Display for ComputedExpr {
85 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
87 ComputedExpr::Literal(l) => match l {
88 Literal::Int(x, _) => {
90 write!(f, "{} ({:#X})", x, x)
95 Literal::Uint(x, _) => {
97 write!(f, "{} ({:#X})", x, x)
102 Literal::Float(x, _) => x.fmt(f),
103 Literal::Bool(x) => x.fmt(f),
104 Literal::Char(x) => std::fmt::Debug::fmt(x, f),
105 Literal::String(x) => std::fmt::Debug::fmt(x, f),
106 Literal::ByteString(x) => std::fmt::Debug::fmt(x, f),
108 ComputedExpr::Tuple(t) => {
120 fn scalar_max(scalar: &Scalar) -> i128 {
123 Scalar::Char => u32::MAX as i128,
124 Scalar::Int(x) => match x {
125 IntTy::Isize => isize::MAX as i128,
126 IntTy::I8 => i8::MAX as i128,
127 IntTy::I16 => i16::MAX as i128,
128 IntTy::I32 => i32::MAX as i128,
129 IntTy::I64 => i64::MAX as i128,
130 IntTy::I128 => i128::MAX as i128,
132 Scalar::Uint(x) => match x {
133 chalk_ir::UintTy::Usize => usize::MAX as i128,
134 chalk_ir::UintTy::U8 => u8::MAX as i128,
135 chalk_ir::UintTy::U16 => u16::MAX as i128,
136 chalk_ir::UintTy::U32 => u32::MAX as i128,
137 chalk_ir::UintTy::U64 => u64::MAX as i128,
138 chalk_ir::UintTy::U128 => i128::MAX as i128, // ignore too big u128 for now
140 Scalar::Float(_) => 0,
144 fn is_valid(scalar: &Scalar, value: i128) -> bool {
146 !matches!(scalar, Scalar::Uint(_)) && -scalar_max(scalar) - 1 <= value
148 value <= scalar_max(scalar)
154 ctx: &mut ConstEvalCtx<'_>,
155 ) -> Result<ComputedExpr, ConstEvalError> {
156 let expr = &ctx.exprs[expr_id];
158 Expr::Missing => Err(ConstEvalError::IncompleteExpr),
159 Expr::Literal(l) => Ok(ComputedExpr::Literal(l.clone())),
160 &Expr::UnaryOp { expr, op } => {
161 let ty = &ctx.expr_ty(expr);
162 let ev = eval_const(expr, ctx)?;
164 hir_def::expr::UnaryOp::Deref => Err(ConstEvalError::NotSupported("deref")),
165 hir_def::expr::UnaryOp::Not => {
167 ComputedExpr::Literal(Literal::Bool(b)) => {
168 return Ok(ComputedExpr::Literal(Literal::Bool(!b)))
170 ComputedExpr::Literal(Literal::Int(v, _)) => v,
171 ComputedExpr::Literal(Literal::Uint(v, _)) => v
173 .map_err(|_| ConstEvalError::NotSupported("too big u128"))?,
174 _ => return Err(ConstEvalError::NotSupported("this kind of operator")),
176 let r = match ty.kind(Interner) {
177 TyKind::Scalar(Scalar::Uint(x)) => match x {
178 chalk_ir::UintTy::U8 => !(v as u8) as i128,
179 chalk_ir::UintTy::U16 => !(v as u16) as i128,
180 chalk_ir::UintTy::U32 => !(v as u32) as i128,
181 chalk_ir::UintTy::U64 => !(v as u64) as i128,
182 chalk_ir::UintTy::U128 => {
183 return Err(ConstEvalError::NotSupported("negation of u128"))
185 chalk_ir::UintTy::Usize => !(v as usize) as i128,
187 TyKind::Scalar(Scalar::Int(x)) => match x {
188 chalk_ir::IntTy::I8 => !(v as i8) as i128,
189 chalk_ir::IntTy::I16 => !(v as i16) as i128,
190 chalk_ir::IntTy::I32 => !(v as i32) as i128,
191 chalk_ir::IntTy::I64 => !(v as i64) as i128,
192 chalk_ir::IntTy::I128 => !v,
193 chalk_ir::IntTy::Isize => !(v as isize) as i128,
195 _ => return Err(ConstEvalError::NotSupported("unreachable?")),
197 Ok(ComputedExpr::Literal(Literal::Int(r, None)))
199 hir_def::expr::UnaryOp::Neg => {
201 ComputedExpr::Literal(Literal::Int(v, _)) => v,
202 ComputedExpr::Literal(Literal::Uint(v, _)) => v
204 .map_err(|_| ConstEvalError::NotSupported("too big u128"))?,
205 _ => return Err(ConstEvalError::NotSupported("this kind of operator")),
207 Ok(ComputedExpr::Literal(Literal::Int(
208 v.checked_neg().ok_or_else(|| {
209 ConstEvalError::Panic("overflow in negation".to_string())
216 &Expr::BinaryOp { lhs, rhs, op } => {
217 let ty = &ctx.expr_ty(lhs);
218 let lhs = eval_const(lhs, ctx)?;
219 let rhs = eval_const(rhs, ctx)?;
220 let op = op.ok_or(ConstEvalError::IncompleteExpr)?;
222 ComputedExpr::Literal(Literal::Int(v, _)) => v,
223 ComputedExpr::Literal(Literal::Uint(v, _)) => {
224 v.try_into().map_err(|_| ConstEvalError::NotSupported("too big u128"))?
226 _ => return Err(ConstEvalError::NotSupported("this kind of operator")),
229 ComputedExpr::Literal(Literal::Int(v, _)) => v,
230 ComputedExpr::Literal(Literal::Uint(v, _)) => {
231 v.try_into().map_err(|_| ConstEvalError::NotSupported("too big u128"))?
233 _ => return Err(ConstEvalError::NotSupported("this kind of operator")),
236 BinaryOp::ArithOp(b) => {
237 let panic_arith = ConstEvalError::Panic(
238 "attempt to run invalid arithmetic operation".to_string(),
241 ArithOp::Add => v1.checked_add(v2).ok_or_else(|| panic_arith.clone())?,
242 ArithOp::Mul => v1.checked_mul(v2).ok_or_else(|| panic_arith.clone())?,
243 ArithOp::Sub => v1.checked_sub(v2).ok_or_else(|| panic_arith.clone())?,
244 ArithOp::Div => v1.checked_div(v2).ok_or_else(|| panic_arith.clone())?,
245 ArithOp::Rem => v1.checked_rem(v2).ok_or_else(|| panic_arith.clone())?,
247 .checked_shl(v2.try_into().map_err(|_| panic_arith.clone())?)
248 .ok_or_else(|| panic_arith.clone())?,
250 .checked_shr(v2.try_into().map_err(|_| panic_arith.clone())?)
251 .ok_or_else(|| panic_arith.clone())?,
252 ArithOp::BitXor => v1 ^ v2,
253 ArithOp::BitOr => v1 | v2,
254 ArithOp::BitAnd => v1 & v2,
256 if let TyKind::Scalar(s) = ty.kind(Interner) {
258 return Err(panic_arith);
261 Ok(ComputedExpr::Literal(Literal::Int(r, None)))
263 BinaryOp::LogicOp(_) => Err(ConstEvalError::SemanticError("logic op on numbers")),
264 _ => Err(ConstEvalError::NotSupported("bin op on this operators")),
267 Expr::Block { statements, tail, .. } => {
268 let mut prev_values = HashMap::<PatId, Option<ComputedExpr>>::default();
269 for statement in &**statements {
271 hir_def::expr::Statement::Let { pat: pat_id, initializer, .. } => {
272 let pat = &ctx.pats[pat_id];
274 Pat::Bind { subpat, .. } if subpat.is_none() => (),
276 return Err(ConstEvalError::NotSupported("complex patterns in let"))
279 let value = match initializer {
280 Some(x) => eval_const(x, ctx)?,
283 if !prev_values.contains_key(&pat_id) {
284 let prev = ctx.local_data.insert(pat_id, value);
285 prev_values.insert(pat_id, prev);
287 ctx.local_data.insert(pat_id, value);
290 hir_def::expr::Statement::Expr { .. } => {
291 return Err(ConstEvalError::NotSupported("this kind of statement"))
296 &Some(x) => eval_const(x, ctx),
297 None => Ok(ComputedExpr::Tuple(Box::new([]))),
299 // clean up local data, so caller will receive the exact map that passed to us
300 for (name, val) in prev_values {
302 Some(x) => ctx.local_data.insert(name, x),
303 None => ctx.local_data.remove(&name),
309 let resolver = resolver_for_expr(ctx.db.upcast(), ctx.owner, expr_id);
311 .resolve_path_in_value_ns(ctx.db.upcast(), p.mod_path())
312 .ok_or(ConstEvalError::SemanticError("unresolved path"))?;
314 ResolveValueResult::ValueNs(v) => v,
315 ResolveValueResult::Partial(..) => {
318 .assoc_resolutions_for_expr(expr_id)
319 .ok_or(ConstEvalError::SemanticError("unresolved assoc item"))?
321 hir_def::AssocItemId::FunctionId(_) => {
322 Err(ConstEvalError::NotSupported("assoc function"))
324 hir_def::AssocItemId::ConstId(c) => ctx.db.const_eval(c),
325 hir_def::AssocItemId::TypeAliasId(_) => {
326 Err(ConstEvalError::NotSupported("assoc type alias"))
332 ValueNs::LocalBinding(pat_id) => {
336 .ok_or(ConstEvalError::NotSupported("Unexpected missing local"))?;
339 ValueNs::ConstId(id) => ctx.db.const_eval(id),
340 ValueNs::GenericParam(_) => {
341 Err(ConstEvalError::NotSupported("const generic without substitution"))
343 _ => Err(ConstEvalError::NotSupported("path that are not const or local")),
346 _ => Err(ConstEvalError::NotSupported("This kind of expression")),
350 pub(crate) fn path_to_const(
351 db: &dyn HirDatabase,
354 mode: ParamLoweringMode,
355 args_lazy: impl FnOnce() -> Generics,
356 debruijn: DebruijnIndex,
358 match resolver.resolve_path_in_value_ns_fully(db.upcast(), &path) {
359 Some(ValueNs::GenericParam(p)) => {
360 let ty = db.const_param_ty(p);
361 let args = args_lazy();
362 let value = match mode {
363 ParamLoweringMode::Placeholder => {
364 ConstValue::Placeholder(to_placeholder_idx(db, p.into()))
366 ParamLoweringMode::Variable => match args.param_idx(p.into()) {
367 Some(x) => ConstValue::BoundVar(BoundVar::new(debruijn, x)),
370 "Generic list doesn't contain this param: {:?}, {}, {:?}",
379 Some(ConstData { ty, value }.intern(Interner))
385 pub fn unknown_const(ty: Ty) -> Const {
388 value: ConstValue::Concrete(chalk_ir::ConcreteConst { interned: ConstScalar::Unknown }),
393 pub fn unknown_const_as_generic(ty: Ty) -> GenericArg {
394 GenericArgData::Const(unknown_const(ty)).intern(Interner)
397 /// Interns a constant scalar with the given type
398 pub fn intern_const_scalar(value: ConstScalar, ty: Ty) -> Const {
399 ConstData { ty, value: ConstValue::Concrete(chalk_ir::ConcreteConst { interned: value }) }
403 /// Interns a possibly-unknown target usize
404 pub fn usize_const(value: Option<u128>) -> Const {
405 intern_const_scalar(value.map_or(ConstScalar::Unknown, ConstScalar::UInt), TyBuilder::usize())
408 pub(crate) fn const_eval_recover(
412 ) -> Result<ComputedExpr, ConstEvalError> {
413 Err(ConstEvalError::Loop)
416 pub(crate) fn const_eval_query(
417 db: &dyn HirDatabase,
419 ) -> Result<ComputedExpr, ConstEvalError> {
420 let def = const_id.into();
421 let body = db.body(def);
422 let infer = &db.infer(def);
423 let result = eval_const(
427 owner: const_id.into(),
430 local_data: HashMap::default(),
437 pub(crate) fn eval_to_const<'a>(
439 mode: ParamLoweringMode,
440 ctx: &mut InferenceContext<'a>,
441 args: impl FnOnce() -> Generics,
442 debruijn: DebruijnIndex,
444 if let Expr::Path(p) = &ctx.body.exprs[expr] {
446 let resolver = &ctx.resolver;
447 if let Some(c) = path_to_const(db, resolver, p.mod_path(), mode, args, debruijn) {
451 let body = ctx.body.clone();
452 let mut ctx = ConstEvalCtx {
457 local_data: HashMap::default(),
460 let computed_expr = eval_const(expr, &mut ctx);
461 let const_scalar = match computed_expr {
462 Ok(ComputedExpr::Literal(literal)) => literal.into(),
463 _ => ConstScalar::Unknown,
465 intern_const_scalar(const_scalar, TyBuilder::usize())