1 //! Constant evaluation details
8 use chalk_ir::{BoundVar, DebruijnIndex, GenericArgData, IntTy, Scalar};
10 builtin_type::BuiltinInt,
11 expr::{ArithOp, BinaryOp, Expr, ExprId, Literal, Pat, PatId},
13 resolver::{resolver_for_expr, ResolveValueResult, Resolver, ValueNs},
15 type_ref::ConstScalar,
16 ConstId, DefWithBodyId, EnumVariantId, Lookup,
18 use la_arena::{Arena, Idx, RawIdx};
20 use syntax::ast::HasName;
23 db::HirDatabase, infer::InferenceContext, lower::ParamLoweringMode, to_placeholder_idx,
24 utils::Generics, Const, ConstData, ConstValue, GenericArg, InferenceResult, Interner, Ty,
28 /// Extension trait for [`Const`]
30 /// Is a [`Const`] unknown?
31 fn is_unknown(&self) -> bool;
34 impl ConstExt for Const {
35 fn is_unknown(&self) -> bool {
36 match self.data(Interner).value {
38 chalk_ir::ConstValue::Concrete(chalk_ir::ConcreteConst {
39 interned: ConstScalar::Unknown,
42 // interned concrete anything else
43 chalk_ir::ConstValue::Concrete(..) => false,
47 "is_unknown was called on a non-concrete constant value! {:?}",
56 pub struct ConstEvalCtx<'a> {
57 pub db: &'a dyn HirDatabase,
58 pub owner: DefWithBodyId,
59 pub exprs: &'a Arena<Expr>,
60 pub pats: &'a Arena<Pat>,
61 pub local_data: HashMap<PatId, ComputedExpr>,
62 infer: &'a InferenceResult,
65 impl ConstEvalCtx<'_> {
66 fn expr_ty(&mut self, expr: ExprId) -> Ty {
67 self.infer[expr].clone()
71 #[derive(Debug, Clone, PartialEq, Eq)]
72 pub enum ConstEvalError {
73 NotSupported(&'static str),
74 SemanticError(&'static str),
80 #[derive(Debug, Clone, PartialEq, Eq)]
81 pub enum ComputedExpr {
83 Enum(String, EnumVariantId, Literal),
84 Tuple(Box<[ComputedExpr]>),
87 impl Display for ComputedExpr {
88 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
90 ComputedExpr::Literal(l) => match l {
91 Literal::Int(x, _) => {
93 write!(f, "{} ({:#X})", x, x)
98 Literal::Uint(x, _) => {
100 write!(f, "{} ({:#X})", x, x)
105 Literal::Float(x, _) => x.fmt(f),
106 Literal::Bool(x) => x.fmt(f),
107 Literal::Char(x) => std::fmt::Debug::fmt(x, f),
108 Literal::String(x) => std::fmt::Debug::fmt(x, f),
109 Literal::ByteString(x) => std::fmt::Debug::fmt(x, f),
111 ComputedExpr::Enum(name, _, _) => name.fmt(f),
112 ComputedExpr::Tuple(t) => {
124 fn scalar_max(scalar: &Scalar) -> i128 {
127 Scalar::Char => u32::MAX as i128,
128 Scalar::Int(x) => match x {
129 IntTy::Isize => isize::MAX as i128,
130 IntTy::I8 => i8::MAX as i128,
131 IntTy::I16 => i16::MAX as i128,
132 IntTy::I32 => i32::MAX as i128,
133 IntTy::I64 => i64::MAX as i128,
134 IntTy::I128 => i128::MAX as i128,
136 Scalar::Uint(x) => match x {
137 chalk_ir::UintTy::Usize => usize::MAX as i128,
138 chalk_ir::UintTy::U8 => u8::MAX as i128,
139 chalk_ir::UintTy::U16 => u16::MAX as i128,
140 chalk_ir::UintTy::U32 => u32::MAX as i128,
141 chalk_ir::UintTy::U64 => u64::MAX as i128,
142 chalk_ir::UintTy::U128 => i128::MAX as i128, // ignore too big u128 for now
144 Scalar::Float(_) => 0,
148 fn is_valid(scalar: &Scalar, value: i128) -> bool {
150 !matches!(scalar, Scalar::Uint(_)) && -scalar_max(scalar) - 1 <= value
152 value <= scalar_max(scalar)
156 fn get_name(ctx: &mut ConstEvalCtx<'_>, variant: EnumVariantId) -> String {
157 let loc = variant.parent.lookup(ctx.db.upcast());
158 let children = variant.parent.child_source(ctx.db.upcast());
159 let item_tree = loc.id.item_tree(ctx.db.upcast());
161 let variant_name = children.value[variant.local_id].name();
162 let enum_name = item_tree[loc.id.value].name.to_string();
163 enum_name + "::" + &variant_name.unwrap().to_string()
168 ctx: &mut ConstEvalCtx<'_>,
169 ) -> Result<ComputedExpr, ConstEvalError> {
170 let u128_to_i128 = |it: u128| -> Result<i128, ConstEvalError> {
171 it.try_into().map_err(|_| ConstEvalError::NotSupported("u128 is too big"))
174 let expr = &ctx.exprs[expr_id];
176 Expr::Missing => match ctx.owner {
177 // evaluate the implicit variant index of an enum variant without expression
178 // FIXME: This should return the type of the enum representation
179 DefWithBodyId::VariantId(variant) => {
180 let prev_idx: u32 = variant.local_id.into_raw().into();
181 let prev_idx = prev_idx.checked_sub(1).map(RawIdx::from).map(Idx::from_raw);
182 let value = match prev_idx {
184 let prev_variant = EnumVariantId { local_id, parent: variant.parent };
185 1 + match ctx.db.const_eval_variant(prev_variant)? {
186 ComputedExpr::Literal(Literal::Int(v, _)) => v,
187 ComputedExpr::Literal(Literal::Uint(v, _)) => u128_to_i128(v)?,
189 return Err(ConstEvalError::NotSupported(
190 "Enum can't contain this kind of value",
197 Ok(ComputedExpr::Literal(Literal::Int(value, Some(BuiltinInt::I128))))
199 _ => Err(ConstEvalError::IncompleteExpr),
201 Expr::Literal(l) => Ok(ComputedExpr::Literal(l.clone())),
202 &Expr::UnaryOp { expr, op } => {
203 let ty = &ctx.expr_ty(expr);
204 let ev = eval_const(expr, ctx)?;
206 hir_def::expr::UnaryOp::Deref => Err(ConstEvalError::NotSupported("deref")),
207 hir_def::expr::UnaryOp::Not => {
209 ComputedExpr::Literal(Literal::Bool(b)) => {
210 return Ok(ComputedExpr::Literal(Literal::Bool(!b)))
212 ComputedExpr::Literal(Literal::Int(v, _)) => v,
213 ComputedExpr::Literal(Literal::Uint(v, _)) => u128_to_i128(v)?,
214 _ => return Err(ConstEvalError::NotSupported("this kind of operator")),
216 let r = match ty.kind(Interner) {
217 TyKind::Scalar(Scalar::Uint(x)) => match x {
218 chalk_ir::UintTy::U8 => !(v as u8) as i128,
219 chalk_ir::UintTy::U16 => !(v as u16) as i128,
220 chalk_ir::UintTy::U32 => !(v as u32) as i128,
221 chalk_ir::UintTy::U64 => !(v as u64) as i128,
222 chalk_ir::UintTy::U128 => {
223 return Err(ConstEvalError::NotSupported("negation of u128"))
225 chalk_ir::UintTy::Usize => !(v as usize) as i128,
227 TyKind::Scalar(Scalar::Int(x)) => match x {
228 chalk_ir::IntTy::I8 => !(v as i8) as i128,
229 chalk_ir::IntTy::I16 => !(v as i16) as i128,
230 chalk_ir::IntTy::I32 => !(v as i32) as i128,
231 chalk_ir::IntTy::I64 => !(v as i64) as i128,
232 chalk_ir::IntTy::I128 => !v,
233 chalk_ir::IntTy::Isize => !(v as isize) as i128,
235 _ => return Err(ConstEvalError::NotSupported("unreachable?")),
237 Ok(ComputedExpr::Literal(Literal::Int(r, None)))
239 hir_def::expr::UnaryOp::Neg => {
241 ComputedExpr::Literal(Literal::Int(v, _)) => v,
242 ComputedExpr::Literal(Literal::Uint(v, _)) => u128_to_i128(v)?,
243 _ => return Err(ConstEvalError::NotSupported("this kind of operator")),
245 Ok(ComputedExpr::Literal(Literal::Int(
246 v.checked_neg().ok_or_else(|| {
247 ConstEvalError::Panic("overflow in negation".to_string())
254 &Expr::BinaryOp { lhs, rhs, op } => {
255 let ty = &ctx.expr_ty(lhs);
256 let lhs = eval_const(lhs, ctx)?;
257 let rhs = eval_const(rhs, ctx)?;
258 let op = op.ok_or(ConstEvalError::IncompleteExpr)?;
260 ComputedExpr::Literal(Literal::Int(v, _)) => v,
261 ComputedExpr::Literal(Literal::Uint(v, _)) => u128_to_i128(v)?,
262 _ => return Err(ConstEvalError::NotSupported("this kind of operator")),
265 ComputedExpr::Literal(Literal::Int(v, _)) => v,
266 ComputedExpr::Literal(Literal::Uint(v, _)) => u128_to_i128(v)?,
267 _ => return Err(ConstEvalError::NotSupported("this kind of operator")),
270 BinaryOp::ArithOp(b) => {
271 let panic_arith = ConstEvalError::Panic(
272 "attempt to run invalid arithmetic operation".to_string(),
275 ArithOp::Add => v1.checked_add(v2).ok_or_else(|| panic_arith.clone())?,
276 ArithOp::Mul => v1.checked_mul(v2).ok_or_else(|| panic_arith.clone())?,
277 ArithOp::Sub => v1.checked_sub(v2).ok_or_else(|| panic_arith.clone())?,
278 ArithOp::Div => v1.checked_div(v2).ok_or_else(|| panic_arith.clone())?,
279 ArithOp::Rem => v1.checked_rem(v2).ok_or_else(|| panic_arith.clone())?,
281 .checked_shl(v2.try_into().map_err(|_| panic_arith.clone())?)
282 .ok_or_else(|| panic_arith.clone())?,
284 .checked_shr(v2.try_into().map_err(|_| panic_arith.clone())?)
285 .ok_or_else(|| panic_arith.clone())?,
286 ArithOp::BitXor => v1 ^ v2,
287 ArithOp::BitOr => v1 | v2,
288 ArithOp::BitAnd => v1 & v2,
290 if let TyKind::Scalar(s) = ty.kind(Interner) {
292 return Err(panic_arith);
295 Ok(ComputedExpr::Literal(Literal::Int(r, None)))
297 BinaryOp::LogicOp(_) => Err(ConstEvalError::SemanticError("logic op on numbers")),
298 _ => Err(ConstEvalError::NotSupported("bin op on this operators")),
301 Expr::Block { statements, tail, .. } => {
302 let mut prev_values = HashMap::<PatId, Option<ComputedExpr>>::default();
303 for statement in &**statements {
305 hir_def::expr::Statement::Let { pat: pat_id, initializer, .. } => {
306 let pat = &ctx.pats[pat_id];
308 Pat::Bind { subpat, .. } if subpat.is_none() => (),
310 return Err(ConstEvalError::NotSupported("complex patterns in let"))
313 let value = match initializer {
314 Some(x) => eval_const(x, ctx)?,
317 if !prev_values.contains_key(&pat_id) {
318 let prev = ctx.local_data.insert(pat_id, value);
319 prev_values.insert(pat_id, prev);
321 ctx.local_data.insert(pat_id, value);
324 hir_def::expr::Statement::Expr { .. } => {
325 return Err(ConstEvalError::NotSupported("this kind of statement"))
330 &Some(x) => eval_const(x, ctx),
331 None => Ok(ComputedExpr::Tuple(Box::new([]))),
333 // clean up local data, so caller will receive the exact map that passed to us
334 for (name, val) in prev_values {
336 Some(x) => ctx.local_data.insert(name, x),
337 None => ctx.local_data.remove(&name),
343 let resolver = resolver_for_expr(ctx.db.upcast(), ctx.owner, expr_id);
345 .resolve_path_in_value_ns(ctx.db.upcast(), p.mod_path())
346 .ok_or(ConstEvalError::SemanticError("unresolved path"))?;
348 ResolveValueResult::ValueNs(v) => v,
349 ResolveValueResult::Partial(..) => {
352 .assoc_resolutions_for_expr(expr_id)
353 .ok_or(ConstEvalError::SemanticError("unresolved assoc item"))?
355 hir_def::AssocItemId::FunctionId(_) => {
356 Err(ConstEvalError::NotSupported("assoc function"))
358 hir_def::AssocItemId::ConstId(c) => ctx.db.const_eval(c),
359 hir_def::AssocItemId::TypeAliasId(_) => {
360 Err(ConstEvalError::NotSupported("assoc type alias"))
366 ValueNs::LocalBinding(pat_id) => {
370 .ok_or(ConstEvalError::NotSupported("Unexpected missing local"))?;
373 ValueNs::ConstId(id) => ctx.db.const_eval(id),
374 ValueNs::GenericParam(_) => {
375 Err(ConstEvalError::NotSupported("const generic without substitution"))
377 ValueNs::EnumVariantId(id) => match ctx.db.const_eval_variant(id)? {
378 ComputedExpr::Literal(lit) => {
379 Ok(ComputedExpr::Enum(get_name(ctx, id), id, lit))
381 _ => Err(ConstEvalError::NotSupported(
382 "Enums can't evalute to anything but numbers",
385 _ => Err(ConstEvalError::NotSupported("path that are not const or local")),
388 // FIXME: Handle the cast target
389 &Expr::Cast { expr, .. } => match eval_const(expr, ctx)? {
390 ComputedExpr::Enum(_, _, lit) => Ok(ComputedExpr::Literal(lit)),
391 _ => Err(ConstEvalError::NotSupported("Can't cast these types")),
393 _ => Err(ConstEvalError::NotSupported("This kind of expression")),
397 pub(crate) fn path_to_const(
398 db: &dyn HirDatabase,
401 mode: ParamLoweringMode,
402 args_lazy: impl FnOnce() -> Generics,
403 debruijn: DebruijnIndex,
405 match resolver.resolve_path_in_value_ns_fully(db.upcast(), &path) {
406 Some(ValueNs::GenericParam(p)) => {
407 let ty = db.const_param_ty(p);
408 let args = args_lazy();
409 let value = match mode {
410 ParamLoweringMode::Placeholder => {
411 ConstValue::Placeholder(to_placeholder_idx(db, p.into()))
413 ParamLoweringMode::Variable => match args.param_idx(p.into()) {
414 Some(x) => ConstValue::BoundVar(BoundVar::new(debruijn, x)),
417 "Generic list doesn't contain this param: {:?}, {}, {:?}",
426 Some(ConstData { ty, value }.intern(Interner))
432 pub fn unknown_const(ty: Ty) -> Const {
435 value: ConstValue::Concrete(chalk_ir::ConcreteConst { interned: ConstScalar::Unknown }),
440 pub fn unknown_const_as_generic(ty: Ty) -> GenericArg {
441 GenericArgData::Const(unknown_const(ty)).intern(Interner)
444 /// Interns a constant scalar with the given type
445 pub fn intern_const_scalar(value: ConstScalar, ty: Ty) -> Const {
446 ConstData { ty, value: ConstValue::Concrete(chalk_ir::ConcreteConst { interned: value }) }
450 /// Interns a possibly-unknown target usize
451 pub fn usize_const(value: Option<u128>) -> Const {
452 intern_const_scalar(value.map_or(ConstScalar::Unknown, ConstScalar::UInt), TyBuilder::usize())
455 pub(crate) fn const_eval_recover(
459 ) -> Result<ComputedExpr, ConstEvalError> {
460 Err(ConstEvalError::Loop)
463 pub(crate) fn const_eval_variant_recover(
467 ) -> Result<ComputedExpr, ConstEvalError> {
468 Err(ConstEvalError::Loop)
471 pub(crate) fn const_eval_variant_query(
472 db: &dyn HirDatabase,
474 ) -> Result<ComputedExpr, ConstEvalError> {
475 let def = const_id.into();
476 let body = db.body(def);
477 let infer = &db.infer(def);
478 let result = eval_const(
482 owner: const_id.into(),
485 local_data: HashMap::default(),
492 pub(crate) fn const_eval_query_variant(
493 db: &dyn HirDatabase,
494 variant_id: EnumVariantId,
495 ) -> Result<ComputedExpr, ConstEvalError> {
496 let def = variant_id.into();
497 let body = db.body(def);
498 let infer = &db.infer(def);
506 local_data: HashMap::default(),
512 pub(crate) fn eval_to_const<'a>(
514 mode: ParamLoweringMode,
515 ctx: &mut InferenceContext<'a>,
516 args: impl FnOnce() -> Generics,
517 debruijn: DebruijnIndex,
519 if let Expr::Path(p) = &ctx.body.exprs[expr] {
521 let resolver = &ctx.resolver;
522 if let Some(c) = path_to_const(db, resolver, p.mod_path(), mode, args, debruijn) {
526 let body = ctx.body.clone();
527 let mut ctx = ConstEvalCtx {
532 local_data: HashMap::default(),
535 let computed_expr = eval_const(expr, &mut ctx);
536 let const_scalar = match computed_expr {
537 Ok(ComputedExpr::Literal(literal)) => literal.into(),
538 _ => ConstScalar::Unknown,
540 intern_const_scalar(const_scalar, TyBuilder::usize())