src/tools/rust-analyzer/crates/hir-ty/src/consteval.rs

   1 //! Constant evaluation details
   2
   3 use std::{
   4     collections::HashMap,
   5     fmt::{Display, Write},
   6 };
   7
   8 use chalk_ir::{BoundVar, DebruijnIndex, GenericArgData, IntTy, Scalar};
   9 use hir_def::{
  10     builtin_type::BuiltinInt,
  11     expr::{ArithOp, BinaryOp, Expr, ExprId, Literal, Pat, PatId},
  12     path::ModPath,
  13     resolver::{resolver_for_expr, ResolveValueResult, Resolver, ValueNs},
  14     src::HasChildSource,
  15     type_ref::ConstScalar,
  16     ConstId, DefWithBodyId, EnumVariantId, Lookup,
  17 };
  18 use la_arena::{Arena, Idx, RawIdx};
  19 use stdx::never;
  20 use syntax::ast::HasName;
  21
  22 use crate::{
  23     db::HirDatabase, infer::InferenceContext, lower::ParamLoweringMode, to_placeholder_idx,
  24     utils::Generics, Const, ConstData, ConstValue, GenericArg, InferenceResult, Interner, Ty,
  25     TyBuilder, TyKind,
  26 };
  27
  28 /// Extension trait for [`Const`]
  29 pub trait ConstExt {
  30     /// Is a [`Const`] unknown?
  31     fn is_unknown(&self) -> bool;
  32 }
  33
  34 impl ConstExt for Const {
  35     fn is_unknown(&self) -> bool {
  36         match self.data(Interner).value {
  37             // interned Unknown
  38             chalk_ir::ConstValue::Concrete(chalk_ir::ConcreteConst {
  39                 interned: ConstScalar::Unknown,
  40             }) => true,
  41
  42             // interned concrete anything else
  43             chalk_ir::ConstValue::Concrete(..) => false,
  44
  45             _ => {
  46                 tracing::error!(
  47                     "is_unknown was called on a non-concrete constant value! {:?}",
  48                     self
  49                 );
  50                 true
  51             }
  52         }
  53     }
  54 }
  55
  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,
  63 }
  64
  65 impl ConstEvalCtx<'_> {
  66     fn expr_ty(&mut self, expr: ExprId) -> Ty {
  67         self.infer[expr].clone()
  68     }
  69 }
  70
  71 #[derive(Debug, Clone, PartialEq, Eq)]
  72 pub enum ConstEvalError {
  73     NotSupported(&'static str),
  74     SemanticError(&'static str),
  75     Loop,
  76     IncompleteExpr,
  77     Panic(String),
  78 }
  79
  80 #[derive(Debug, Clone, PartialEq, Eq)]
  81 pub enum ComputedExpr {
  82     Literal(Literal),
  83     Enum(String, EnumVariantId, Literal),
  84     Tuple(Box<[ComputedExpr]>),
  85 }
  86
  87 impl Display for ComputedExpr {
  88     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
  89         match self {
  90             ComputedExpr::Literal(l) => match l {
  91                 Literal::Int(x, _) => {
  92                     if *x >= 10 {
  93                         write!(f, "{x} ({x:#X})")
  94                     } else {
  95                         x.fmt(f)
  96                     }
  97                 }
  98                 Literal::Uint(x, _) => {
  99                     if *x >= 10 {
 100                         write!(f, "{x} ({x:#X})")
 101                     } else {
 102                         x.fmt(f)
 103                     }
 104                 }
 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),
 110             },
 111             ComputedExpr::Enum(name, _, _) => name.fmt(f),
 112             ComputedExpr::Tuple(t) => {
 113                 f.write_char('(')?;
 114                 for x in &**t {
 115                     x.fmt(f)?;
 116                     f.write_str(", ")?;
 117                 }
 118                 f.write_char(')')
 119             }
 120         }
 121     }
 122 }
 123
 124 fn scalar_max(scalar: &Scalar) -> i128 {
 125     match scalar {
 126         Scalar::Bool => 1,
 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,
 135         },
 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, // ignore too big u128 for now
 143         },
 144         Scalar::Float(_) => 0,
 145     }
 146 }
 147
 148 fn is_valid(scalar: &Scalar, value: i128) -> bool {
 149     if value < 0 {
 150         !matches!(scalar, Scalar::Uint(_)) && -scalar_max(scalar) - 1 <= value
 151     } else {
 152         value <= scalar_max(scalar)
 153     }
 154 }
 155
 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());
 160
 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()
 164 }
 165
 166 pub fn eval_const(
 167     expr_id: ExprId,
 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"))
 172     };
 173
 174     let expr = &ctx.exprs[expr_id];
 175     match expr {
 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 {
 183                     Some(local_id) => {
 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)?,
 188                             _ => {
 189                                 return Err(ConstEvalError::NotSupported(
 190                                     "Enum can't contain this kind of value",
 191                                 ))
 192                             }
 193                         }
 194                     }
 195                     _ => 0,
 196                 };
 197                 Ok(ComputedExpr::Literal(Literal::Int(value, Some(BuiltinInt::I128))))
 198             }
 199             _ => Err(ConstEvalError::IncompleteExpr),
 200         },
 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)?;
 205             match op {
 206                 hir_def::expr::UnaryOp::Deref => Err(ConstEvalError::NotSupported("deref")),
 207                 hir_def::expr::UnaryOp::Not => {
 208                     let v = match ev {
 209                         ComputedExpr::Literal(Literal::Bool(b)) => {
 210                             return Ok(ComputedExpr::Literal(Literal::Bool(!b)))
 211                         }
 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")),
 215                     };
 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"))
 224                             }
 225                             chalk_ir::UintTy::Usize => !(v as usize) as i128,
 226                         },
 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,
 234                         },
 235                         _ => return Err(ConstEvalError::NotSupported("unreachable?")),
 236                     };
 237                     Ok(ComputedExpr::Literal(Literal::Int(r, None)))
 238                 }
 239                 hir_def::expr::UnaryOp::Neg => {
 240                     let v = match ev {
 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")),
 244                     };
 245                     Ok(ComputedExpr::Literal(Literal::Int(
 246                         v.checked_neg().ok_or_else(|| {
 247                             ConstEvalError::Panic("overflow in negation".to_string())
 248                         })?,
 249                         None,
 250                     )))
 251                 }
 252             }
 253         }
 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)?;
 259             let v1 = match lhs {
 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")),
 263             };
 264             let v2 = match rhs {
 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")),
 268             };
 269             match op {
 270                 BinaryOp::ArithOp(b) => {
 271                     let panic_arith = ConstEvalError::Panic(
 272                         "attempt to run invalid arithmetic operation".to_string(),
 273                     );
 274                     let r = match b {
 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())?,
 280                         ArithOp::Shl => v1
 281                             .checked_shl(v2.try_into().map_err(|_| panic_arith.clone())?)
 282                             .ok_or_else(|| panic_arith.clone())?,
 283                         ArithOp::Shr => v1
 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,
 289                     };
 290                     if let TyKind::Scalar(s) = ty.kind(Interner) {
 291                         if !is_valid(s, r) {
 292                             return Err(panic_arith);
 293                         }
 294                     }
 295                     Ok(ComputedExpr::Literal(Literal::Int(r, None)))
 296                 }
 297                 BinaryOp::LogicOp(_) => Err(ConstEvalError::SemanticError("logic op on numbers")),
 298                 _ => Err(ConstEvalError::NotSupported("bin op on this operators")),
 299             }
 300         }
 301         Expr::Block { statements, tail, .. } => {
 302             let mut prev_values = HashMap::<PatId, Option<ComputedExpr>>::default();
 303             for statement in &**statements {
 304                 match *statement {
 305                     hir_def::expr::Statement::Let { pat: pat_id, initializer, .. } => {
 306                         let pat = &ctx.pats[pat_id];
 307                         match pat {
 308                             Pat::Bind { subpat, .. } if subpat.is_none() => (),
 309                             _ => {
 310                                 return Err(ConstEvalError::NotSupported("complex patterns in let"))
 311                             }
 312                         };
 313                         let value = match initializer {
 314                             Some(x) => eval_const(x, ctx)?,
 315                             None => continue,
 316                         };
 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);
 320                         } else {
 321                             ctx.local_data.insert(pat_id, value);
 322                         }
 323                     }
 324                     hir_def::expr::Statement::Expr { .. } => {
 325                         return Err(ConstEvalError::NotSupported("this kind of statement"))
 326                     }
 327                 }
 328             }
 329             let r = match tail {
 330                 &Some(x) => eval_const(x, ctx),
 331                 None => Ok(ComputedExpr::Tuple(Box::new([]))),
 332             };
 333             // clean up local data, so caller will receive the exact map that passed to us
 334             for (name, val) in prev_values {
 335                 match val {
 336                     Some(x) => ctx.local_data.insert(name, x),
 337                     None => ctx.local_data.remove(&name),
 338                 };
 339             }
 340             r
 341         }
 342         Expr::Path(p) => {
 343             let resolver = resolver_for_expr(ctx.db.upcast(), ctx.owner, expr_id);
 344             let pr = resolver
 345                 .resolve_path_in_value_ns(ctx.db.upcast(), p.mod_path())
 346                 .ok_or(ConstEvalError::SemanticError("unresolved path"))?;
 347             let pr = match pr {
 348                 ResolveValueResult::ValueNs(v) => v,
 349                 ResolveValueResult::Partial(..) => {
 350                     return match ctx
 351                         .infer
 352                         .assoc_resolutions_for_expr(expr_id)
 353                         .ok_or(ConstEvalError::SemanticError("unresolved assoc item"))?
 354                         .0
 355                     {
 356                         hir_def::AssocItemId::FunctionId(_) => {
 357                             Err(ConstEvalError::NotSupported("assoc function"))
 358                         }
 359                         // FIXME use actual impl for trait assoc const
 360                         hir_def::AssocItemId::ConstId(c) => ctx.db.const_eval(c),
 361                         hir_def::AssocItemId::TypeAliasId(_) => {
 362                             Err(ConstEvalError::NotSupported("assoc type alias"))
 363                         }
 364                     };
 365                 }
 366             };
 367             match pr {
 368                 ValueNs::LocalBinding(pat_id) => {
 369                     let r = ctx
 370                         .local_data
 371                         .get(&pat_id)
 372                         .ok_or(ConstEvalError::NotSupported("Unexpected missing local"))?;
 373                     Ok(r.clone())
 374                 }
 375                 ValueNs::ConstId(id) => ctx.db.const_eval(id),
 376                 ValueNs::GenericParam(_) => {
 377                     Err(ConstEvalError::NotSupported("const generic without substitution"))
 378                 }
 379                 ValueNs::EnumVariantId(id) => match ctx.db.const_eval_variant(id)? {
 380                     ComputedExpr::Literal(lit) => {
 381                         Ok(ComputedExpr::Enum(get_name(ctx, id), id, lit))
 382                     }
 383                     _ => Err(ConstEvalError::NotSupported(
 384                         "Enums can't evalute to anything but numbers",
 385                     )),
 386                 },
 387                 _ => Err(ConstEvalError::NotSupported("path that are not const or local")),
 388             }
 389         }
 390         // FIXME: Handle the cast target
 391         &Expr::Cast { expr, .. } => match eval_const(expr, ctx)? {
 392             ComputedExpr::Enum(_, _, lit) => Ok(ComputedExpr::Literal(lit)),
 393             _ => Err(ConstEvalError::NotSupported("Can't cast these types")),
 394         },
 395         _ => Err(ConstEvalError::NotSupported("This kind of expression")),
 396     }
 397 }
 398
 399 pub(crate) fn path_to_const(
 400     db: &dyn HirDatabase,
 401     resolver: &Resolver,
 402     path: &ModPath,
 403     mode: ParamLoweringMode,
 404     args_lazy: impl FnOnce() -> Generics,
 405     debruijn: DebruijnIndex,
 406 ) -> Option<Const> {
 407     match resolver.resolve_path_in_value_ns_fully(db.upcast(), path) {
 408         Some(ValueNs::GenericParam(p)) => {
 409             let ty = db.const_param_ty(p);
 410             let args = args_lazy();
 411             let value = match mode {
 412                 ParamLoweringMode::Placeholder => {
 413                     ConstValue::Placeholder(to_placeholder_idx(db, p.into()))
 414                 }
 415                 ParamLoweringMode::Variable => match args.param_idx(p.into()) {
 416                     Some(x) => ConstValue::BoundVar(BoundVar::new(debruijn, x)),
 417                     None => {
 418                         never!(
 419                             "Generic list doesn't contain this param: {:?}, {}, {:?}",
 420                             args,
 421                             path,
 422                             p
 423                         );
 424                         return None;
 425                     }
 426                 },
 427             };
 428             Some(ConstData { ty, value }.intern(Interner))
 429         }
 430         _ => None,
 431     }
 432 }
 433
 434 pub fn unknown_const(ty: Ty) -> Const {
 435     ConstData {
 436         ty,
 437         value: ConstValue::Concrete(chalk_ir::ConcreteConst { interned: ConstScalar::Unknown }),
 438     }
 439     .intern(Interner)
 440 }
 441
 442 pub fn unknown_const_as_generic(ty: Ty) -> GenericArg {
 443     GenericArgData::Const(unknown_const(ty)).intern(Interner)
 444 }
 445
 446 /// Interns a constant scalar with the given type
 447 pub fn intern_const_scalar(value: ConstScalar, ty: Ty) -> Const {
 448     ConstData { ty, value: ConstValue::Concrete(chalk_ir::ConcreteConst { interned: value }) }
 449         .intern(Interner)
 450 }
 451
 452 /// Interns a possibly-unknown target usize
 453 pub fn usize_const(value: Option<u128>) -> Const {
 454     intern_const_scalar(value.map_or(ConstScalar::Unknown, ConstScalar::UInt), TyBuilder::usize())
 455 }
 456
 457 pub(crate) fn const_eval_recover(
 458     _: &dyn HirDatabase,
 459     _: &[String],
 460     _: &ConstId,
 461 ) -> Result<ComputedExpr, ConstEvalError> {
 462     Err(ConstEvalError::Loop)
 463 }
 464
 465 pub(crate) fn const_eval_variant_recover(
 466     _: &dyn HirDatabase,
 467     _: &[String],
 468     _: &EnumVariantId,
 469 ) -> Result<ComputedExpr, ConstEvalError> {
 470     Err(ConstEvalError::Loop)
 471 }
 472
 473 pub(crate) fn const_eval_variant_query(
 474     db: &dyn HirDatabase,
 475     const_id: ConstId,
 476 ) -> Result<ComputedExpr, ConstEvalError> {
 477     let def = const_id.into();
 478     let body = db.body(def);
 479     let infer = &db.infer(def);
 480     let result = eval_const(
 481         body.body_expr,
 482         &mut ConstEvalCtx {
 483             db,
 484             owner: const_id.into(),
 485             exprs: &body.exprs,
 486             pats: &body.pats,
 487             local_data: HashMap::default(),
 488             infer,
 489         },
 490     );
 491     result
 492 }
 493
 494 pub(crate) fn const_eval_query_variant(
 495     db: &dyn HirDatabase,
 496     variant_id: EnumVariantId,
 497 ) -> Result<ComputedExpr, ConstEvalError> {
 498     let def = variant_id.into();
 499     let body = db.body(def);
 500     let infer = &db.infer(def);
 501     eval_const(
 502         body.body_expr,
 503         &mut ConstEvalCtx {
 504             db,
 505             owner: def,
 506             exprs: &body.exprs,
 507             pats: &body.pats,
 508             local_data: HashMap::default(),
 509             infer,
 510         },
 511     )
 512 }
 513
 514 pub(crate) fn eval_to_const(
 515     expr: Idx<Expr>,
 516     mode: ParamLoweringMode,
 517     ctx: &mut InferenceContext<'_>,
 518     args: impl FnOnce() -> Generics,
 519     debruijn: DebruijnIndex,
 520 ) -> Const {
 521     if let Expr::Path(p) = &ctx.body.exprs[expr] {
 522         let db = ctx.db;
 523         let resolver = &ctx.resolver;
 524         if let Some(c) = path_to_const(db, resolver, p.mod_path(), mode, args, debruijn) {
 525             return c;
 526         }
 527     }
 528     let body = ctx.body.clone();
 529     let mut ctx = ConstEvalCtx {
 530         db: ctx.db,
 531         owner: ctx.owner,
 532         exprs: &body.exprs,
 533         pats: &body.pats,
 534         local_data: HashMap::default(),
 535         infer: &ctx.result,
 536     };
 537     let computed_expr = eval_const(expr, &mut ctx);
 538     let const_scalar = match computed_expr {
 539         Ok(ComputedExpr::Literal(literal)) => literal.into(),
 540         _ => ConstScalar::Unknown,
 541     };
 542     intern_const_scalar(const_scalar, TyBuilder::usize())
 543 }
 544
 545 #[cfg(test)]
 546 mod tests;