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     expr::{ArithOp, BinaryOp, Expr, ExprId, Literal, Pat, PatId},
  11     path::ModPath,
  12     resolver::{resolver_for_expr, ResolveValueResult, Resolver, ValueNs},
  13     type_ref::ConstScalar,
  14     ConstId, DefWithBodyId,
  15 };
  16 use la_arena::{Arena, Idx};
  17 use stdx::never;
  18
  19 use crate::{
  20     db::HirDatabase, infer::InferenceContext, lower::ParamLoweringMode, to_placeholder_idx,
  21     utils::Generics, Const, ConstData, ConstValue, GenericArg, InferenceResult, Interner, Ty,
  22     TyBuilder, TyKind,
  23 };
  24
  25 /// Extension trait for [`Const`]
  26 pub trait ConstExt {
  27     /// Is a [`Const`] unknown?
  28     fn is_unknown(&self) -> bool;
  29 }
  30
  31 impl ConstExt for Const {
  32     fn is_unknown(&self) -> bool {
  33         match self.data(Interner).value {
  34             // interned Unknown
  35             chalk_ir::ConstValue::Concrete(chalk_ir::ConcreteConst {
  36                 interned: ConstScalar::Unknown,
  37             }) => true,
  38
  39             // interned concrete anything else
  40             chalk_ir::ConstValue::Concrete(..) => false,
  41
  42             _ => {
  43                 tracing::error!(
  44                     "is_unknown was called on a non-concrete constant value! {:?}",
  45                     self
  46                 );
  47                 true
  48             }
  49         }
  50     }
  51 }
  52
  53 pub struct ConstEvalCtx<'a> {
  54     pub db: &'a dyn HirDatabase,
  55     pub owner: DefWithBodyId,
  56     pub exprs: &'a Arena<Expr>,
  57     pub pats: &'a Arena<Pat>,
  58     pub local_data: HashMap<PatId, ComputedExpr>,
  59     infer: &'a InferenceResult,
  60 }
  61
  62 impl ConstEvalCtx<'_> {
  63     fn expr_ty(&mut self, expr: ExprId) -> Ty {
  64         self.infer[expr].clone()
  65     }
  66 }
  67
  68 #[derive(Debug, Clone, PartialEq, Eq)]
  69 pub enum ConstEvalError {
  70     NotSupported(&'static str),
  71     SemanticError(&'static str),
  72     Loop,
  73     IncompleteExpr,
  74     Panic(String),
  75 }
  76
  77 #[derive(Debug, Clone, PartialEq, Eq)]
  78 pub enum ComputedExpr {
  79     Literal(Literal),
  80     Tuple(Box<[ComputedExpr]>),
  81 }
  82
  83 impl Display for ComputedExpr {
  84     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
  85         match self {
  86             ComputedExpr::Literal(l) => match l {
  87                 Literal::Int(x, _) => {
  88                     if *x >= 10 {
  89                         write!(f, "{} ({:#X})", x, x)
  90                     } else {
  91                         x.fmt(f)
  92                     }
  93                 }
  94                 Literal::Uint(x, _) => {
  95                     if *x >= 10 {
  96                         write!(f, "{} ({:#X})", x, x)
  97                     } else {
  98                         x.fmt(f)
  99                     }
 100                 }
 101                 Literal::Float(x, _) => x.fmt(f),
 102                 Literal::Bool(x) => x.fmt(f),
 103                 Literal::Char(x) => std::fmt::Debug::fmt(x, f),
 104                 Literal::String(x) => std::fmt::Debug::fmt(x, f),
 105                 Literal::ByteString(x) => std::fmt::Debug::fmt(x, f),
 106             },
 107             ComputedExpr::Tuple(t) => {
 108                 f.write_char('(')?;
 109                 for x in &**t {
 110                     x.fmt(f)?;
 111                     f.write_str(", ")?;
 112                 }
 113                 f.write_char(')')
 114             }
 115         }
 116     }
 117 }
 118
 119 fn scalar_max(scalar: &Scalar) -> i128 {
 120     match scalar {
 121         Scalar::Bool => 1,
 122         Scalar::Char => u32::MAX as i128,
 123         Scalar::Int(x) => match x {
 124             IntTy::Isize => isize::MAX as i128,
 125             IntTy::I8 => i8::MAX as i128,
 126             IntTy::I16 => i16::MAX as i128,
 127             IntTy::I32 => i32::MAX as i128,
 128             IntTy::I64 => i64::MAX as i128,
 129             IntTy::I128 => i128::MAX as i128,
 130         },
 131         Scalar::Uint(x) => match x {
 132             chalk_ir::UintTy::Usize => usize::MAX as i128,
 133             chalk_ir::UintTy::U8 => u8::MAX as i128,
 134             chalk_ir::UintTy::U16 => u16::MAX as i128,
 135             chalk_ir::UintTy::U32 => u32::MAX as i128,
 136             chalk_ir::UintTy::U64 => u64::MAX as i128,
 137             chalk_ir::UintTy::U128 => i128::MAX as i128, // ignore too big u128 for now
 138         },
 139         Scalar::Float(_) => 0,
 140     }
 141 }
 142
 143 fn is_valid(scalar: &Scalar, value: i128) -> bool {
 144     if value < 0 {
 145         !matches!(scalar, Scalar::Uint(_)) && -scalar_max(scalar) - 1 <= value
 146     } else {
 147         value <= scalar_max(scalar)
 148     }
 149 }
 150
 151 pub fn eval_const(
 152     expr_id: ExprId,
 153     ctx: &mut ConstEvalCtx<'_>,
 154 ) -> Result<ComputedExpr, ConstEvalError> {
 155     let expr = &ctx.exprs[expr_id];
 156     match expr {
 157         Expr::Missing => Err(ConstEvalError::IncompleteExpr),
 158         Expr::Literal(l) => Ok(ComputedExpr::Literal(l.clone())),
 159         &Expr::UnaryOp { expr, op } => {
 160             let ty = &ctx.expr_ty(expr);
 161             let ev = eval_const(expr, ctx)?;
 162             match op {
 163                 hir_def::expr::UnaryOp::Deref => Err(ConstEvalError::NotSupported("deref")),
 164                 hir_def::expr::UnaryOp::Not => {
 165                     let v = match ev {
 166                         ComputedExpr::Literal(Literal::Bool(b)) => {
 167                             return Ok(ComputedExpr::Literal(Literal::Bool(!b)))
 168                         }
 169                         ComputedExpr::Literal(Literal::Int(v, _)) => v,
 170                         ComputedExpr::Literal(Literal::Uint(v, _)) => v
 171                             .try_into()
 172                             .map_err(|_| ConstEvalError::NotSupported("too big u128"))?,
 173                         _ => return Err(ConstEvalError::NotSupported("this kind of operator")),
 174                     };
 175                     let r = match ty.kind(Interner) {
 176                         TyKind::Scalar(Scalar::Uint(x)) => match x {
 177                             chalk_ir::UintTy::U8 => !(v as u8) as i128,
 178                             chalk_ir::UintTy::U16 => !(v as u16) as i128,
 179                             chalk_ir::UintTy::U32 => !(v as u32) as i128,
 180                             chalk_ir::UintTy::U64 => !(v as u64) as i128,
 181                             chalk_ir::UintTy::U128 => {
 182                                 return Err(ConstEvalError::NotSupported("negation of u128"))
 183                             }
 184                             chalk_ir::UintTy::Usize => !(v as usize) as i128,
 185                         },
 186                         TyKind::Scalar(Scalar::Int(x)) => match x {
 187                             chalk_ir::IntTy::I8 => !(v as i8) as i128,
 188                             chalk_ir::IntTy::I16 => !(v as i16) as i128,
 189                             chalk_ir::IntTy::I32 => !(v as i32) as i128,
 190                             chalk_ir::IntTy::I64 => !(v as i64) as i128,
 191                             chalk_ir::IntTy::I128 => !v,
 192                             chalk_ir::IntTy::Isize => !(v as isize) as i128,
 193                         },
 194                         _ => return Err(ConstEvalError::NotSupported("unreachable?")),
 195                     };
 196                     Ok(ComputedExpr::Literal(Literal::Int(r, None)))
 197                 }
 198                 hir_def::expr::UnaryOp::Neg => {
 199                     let v = match ev {
 200                         ComputedExpr::Literal(Literal::Int(v, _)) => v,
 201                         ComputedExpr::Literal(Literal::Uint(v, _)) => v
 202                             .try_into()
 203                             .map_err(|_| ConstEvalError::NotSupported("too big u128"))?,
 204                         _ => return Err(ConstEvalError::NotSupported("this kind of operator")),
 205                     };
 206                     Ok(ComputedExpr::Literal(Literal::Int(
 207                         v.checked_neg().ok_or_else(|| {
 208                             ConstEvalError::Panic("overflow in negation".to_string())
 209                         })?,
 210                         None,
 211                     )))
 212                 }
 213             }
 214         }
 215         &Expr::BinaryOp { lhs, rhs, op } => {
 216             let ty = &ctx.expr_ty(lhs);
 217             let lhs = eval_const(lhs, ctx)?;
 218             let rhs = eval_const(rhs, ctx)?;
 219             let op = op.ok_or(ConstEvalError::IncompleteExpr)?;
 220             let v1 = match lhs {
 221                 ComputedExpr::Literal(Literal::Int(v, _)) => v,
 222                 ComputedExpr::Literal(Literal::Uint(v, _)) => {
 223                     v.try_into().map_err(|_| ConstEvalError::NotSupported("too big u128"))?
 224                 }
 225                 _ => return Err(ConstEvalError::NotSupported("this kind of operator")),
 226             };
 227             let v2 = match rhs {
 228                 ComputedExpr::Literal(Literal::Int(v, _)) => v,
 229                 ComputedExpr::Literal(Literal::Uint(v, _)) => {
 230                     v.try_into().map_err(|_| ConstEvalError::NotSupported("too big u128"))?
 231                 }
 232                 _ => return Err(ConstEvalError::NotSupported("this kind of operator")),
 233             };
 234             match op {
 235                 BinaryOp::ArithOp(b) => {
 236                     let panic_arith = ConstEvalError::Panic(
 237                         "attempt to run invalid arithmetic operation".to_string(),
 238                     );
 239                     let r = match b {
 240                         ArithOp::Add => v1.checked_add(v2).ok_or_else(|| panic_arith.clone())?,
 241                         ArithOp::Mul => v1.checked_mul(v2).ok_or_else(|| panic_arith.clone())?,
 242                         ArithOp::Sub => v1.checked_sub(v2).ok_or_else(|| panic_arith.clone())?,
 243                         ArithOp::Div => v1.checked_div(v2).ok_or_else(|| panic_arith.clone())?,
 244                         ArithOp::Rem => v1.checked_rem(v2).ok_or_else(|| panic_arith.clone())?,
 245                         ArithOp::Shl => v1
 246                             .checked_shl(v2.try_into().map_err(|_| panic_arith.clone())?)
 247                             .ok_or_else(|| panic_arith.clone())?,
 248                         ArithOp::Shr => v1
 249                             .checked_shr(v2.try_into().map_err(|_| panic_arith.clone())?)
 250                             .ok_or_else(|| panic_arith.clone())?,
 251                         ArithOp::BitXor => v1 ^ v2,
 252                         ArithOp::BitOr => v1 | v2,
 253                         ArithOp::BitAnd => v1 & v2,
 254                     };
 255                     if let TyKind::Scalar(s) = ty.kind(Interner) {
 256                         if !is_valid(s, r) {
 257                             return Err(panic_arith);
 258                         }
 259                     }
 260                     Ok(ComputedExpr::Literal(Literal::Int(r, None)))
 261                 }
 262                 BinaryOp::LogicOp(_) => Err(ConstEvalError::SemanticError("logic op on numbers")),
 263                 _ => Err(ConstEvalError::NotSupported("bin op on this operators")),
 264             }
 265         }
 266         Expr::Block { statements, tail, .. } => {
 267             let mut prev_values = HashMap::<PatId, Option<ComputedExpr>>::default();
 268             for statement in &**statements {
 269                 match *statement {
 270                     hir_def::expr::Statement::Let { pat: pat_id, initializer, .. } => {
 271                         let pat = &ctx.pats[pat_id];
 272                         match pat {
 273                             Pat::Bind { subpat, .. } if subpat.is_none() => (),
 274                             _ => {
 275                                 return Err(ConstEvalError::NotSupported("complex patterns in let"))
 276                             }
 277                         };
 278                         let value = match initializer {
 279                             Some(x) => eval_const(x, ctx)?,
 280                             None => continue,
 281                         };
 282                         if !prev_values.contains_key(&pat_id) {
 283                             let prev = ctx.local_data.insert(pat_id, value);
 284                             prev_values.insert(pat_id, prev);
 285                         } else {
 286                             ctx.local_data.insert(pat_id, value);
 287                         }
 288                     }
 289                     hir_def::expr::Statement::Expr { .. } => {
 290                         return Err(ConstEvalError::NotSupported("this kind of statement"))
 291                     }
 292                 }
 293             }
 294             let r = match tail {
 295                 &Some(x) => eval_const(x, ctx),
 296                 None => Ok(ComputedExpr::Tuple(Box::new([]))),
 297             };
 298             // clean up local data, so caller will receive the exact map that passed to us
 299             for (name, val) in prev_values {
 300                 match val {
 301                     Some(x) => ctx.local_data.insert(name, x),
 302                     None => ctx.local_data.remove(&name),
 303                 };
 304             }
 305             r
 306         }
 307         Expr::Path(p) => {
 308             let resolver = resolver_for_expr(ctx.db.upcast(), ctx.owner, expr_id);
 309             let pr = resolver
 310                 .resolve_path_in_value_ns(ctx.db.upcast(), p.mod_path())
 311                 .ok_or(ConstEvalError::SemanticError("unresolved path"))?;
 312             let pr = match pr {
 313                 ResolveValueResult::ValueNs(v) => v,
 314                 ResolveValueResult::Partial(..) => {
 315                     return match ctx
 316                         .infer
 317                         .assoc_resolutions_for_expr(expr_id)
 318                         .ok_or(ConstEvalError::SemanticError("unresolved assoc item"))?
 319                     {
 320                         hir_def::AssocItemId::FunctionId(_) => {
 321                             Err(ConstEvalError::NotSupported("assoc function"))
 322                         }
 323                         hir_def::AssocItemId::ConstId(c) => ctx.db.const_eval(c),
 324                         hir_def::AssocItemId::TypeAliasId(_) => {
 325                             Err(ConstEvalError::NotSupported("assoc type alias"))
 326                         }
 327                     }
 328                 }
 329             };
 330             match pr {
 331                 ValueNs::LocalBinding(pat_id) => {
 332                     let r = ctx
 333                         .local_data
 334                         .get(&pat_id)
 335                         .ok_or(ConstEvalError::NotSupported("Unexpected missing local"))?;
 336                     Ok(r.clone())
 337                 }
 338                 ValueNs::ConstId(id) => ctx.db.const_eval(id),
 339                 ValueNs::GenericParam(_) => {
 340                     Err(ConstEvalError::NotSupported("const generic without substitution"))
 341                 }
 342                 _ => Err(ConstEvalError::NotSupported("path that are not const or local")),
 343             }
 344         }
 345         _ => Err(ConstEvalError::NotSupported("This kind of expression")),
 346     }
 347 }
 348
 349 pub(crate) fn path_to_const(
 350     db: &dyn HirDatabase,
 351     resolver: &Resolver,
 352     path: &ModPath,
 353     mode: ParamLoweringMode,
 354     args_lazy: impl FnOnce() -> Generics,
 355     debruijn: DebruijnIndex,
 356 ) -> Option<Const> {
 357     match resolver.resolve_path_in_value_ns_fully(db.upcast(), &path) {
 358         Some(ValueNs::GenericParam(p)) => {
 359             let ty = db.const_param_ty(p);
 360             let args = args_lazy();
 361             let value = match mode {
 362                 ParamLoweringMode::Placeholder => {
 363                     ConstValue::Placeholder(to_placeholder_idx(db, p.into()))
 364                 }
 365                 ParamLoweringMode::Variable => match args.param_idx(p.into()) {
 366                     Some(x) => ConstValue::BoundVar(BoundVar::new(debruijn, x)),
 367                     None => {
 368                         never!(
 369                             "Generic list doesn't contain this param: {:?}, {}, {:?}",
 370                             args,
 371                             path,
 372                             p
 373                         );
 374                         return None;
 375                     }
 376                 },
 377             };
 378             Some(ConstData { ty, value }.intern(Interner))
 379         }
 380         _ => None,
 381     }
 382 }
 383
 384 pub fn unknown_const(ty: Ty) -> Const {
 385     ConstData {
 386         ty,
 387         value: ConstValue::Concrete(chalk_ir::ConcreteConst { interned: ConstScalar::Unknown }),
 388     }
 389     .intern(Interner)
 390 }
 391
 392 pub fn unknown_const_as_generic(ty: Ty) -> GenericArg {
 393     GenericArgData::Const(unknown_const(ty)).intern(Interner)
 394 }
 395
 396 /// Interns a constant scalar with the given type
 397 pub fn intern_const_scalar(value: ConstScalar, ty: Ty) -> Const {
 398     ConstData { ty, value: ConstValue::Concrete(chalk_ir::ConcreteConst { interned: value }) }
 399         .intern(Interner)
 400 }
 401
 402 /// Interns a possibly-unknown target usize
 403 pub fn usize_const(value: Option<u128>) -> Const {
 404     intern_const_scalar(value.map_or(ConstScalar::Unknown, ConstScalar::UInt), TyBuilder::usize())
 405 }
 406
 407 pub(crate) fn const_eval_recover(
 408     _: &dyn HirDatabase,
 409     _: &[String],
 410     _: &ConstId,
 411 ) -> Result<ComputedExpr, ConstEvalError> {
 412     Err(ConstEvalError::Loop)
 413 }
 414
 415 pub(crate) fn const_eval_query(
 416     db: &dyn HirDatabase,
 417     const_id: ConstId,
 418 ) -> Result<ComputedExpr, ConstEvalError> {
 419     let def = const_id.into();
 420     let body = db.body(def);
 421     let infer = &db.infer(def);
 422     let result = eval_const(
 423         body.body_expr,
 424         &mut ConstEvalCtx {
 425             db,
 426             owner: const_id.into(),
 427             exprs: &body.exprs,
 428             pats: &body.pats,
 429             local_data: HashMap::default(),
 430             infer,
 431         },
 432     );
 433     result
 434 }
 435
 436 pub(crate) fn eval_to_const<'a>(
 437     expr: Idx<Expr>,
 438     mode: ParamLoweringMode,
 439     ctx: &mut InferenceContext<'a>,
 440     args: impl FnOnce() -> Generics,
 441     debruijn: DebruijnIndex,
 442 ) -> Const {
 443     if let Expr::Path(p) = &ctx.body.exprs[expr] {
 444         let db = ctx.db;
 445         let resolver = &ctx.resolver;
 446         if let Some(c) = path_to_const(db, resolver, p.mod_path(), mode, args, debruijn) {
 447             return c;
 448         }
 449     }
 450     let body = ctx.body.clone();
 451     let mut ctx = ConstEvalCtx {
 452         db: ctx.db,
 453         owner: ctx.owner,
 454         exprs: &body.exprs,
 455         pats: &body.pats,
 456         local_data: HashMap::default(),
 457         infer: &ctx.result,
 458     };
 459     let computed_expr = eval_const(expr, &mut ctx);
 460     let const_scalar = match computed_expr {
 461         Ok(ComputedExpr::Literal(literal)) => literal.into(),
 462         _ => ConstScalar::Unknown,
 463     };
 464     intern_const_scalar(const_scalar, TyBuilder::usize())
 465 }
 466
 467 #[cfg(test)]
 468 mod tests;