crates/hir_ty/src/consteval.rs

   1 //! Constant evaluation details
   2
   3 use std::{collections::HashMap, convert::TryInto, fmt::Display};
   4
   5 use chalk_ir::{IntTy, Scalar};
   6 use hir_def::{
   7     expr::{ArithOp, BinaryOp, Expr, Literal, Pat},
   8     type_ref::ConstScalar,
   9 };
  10 use hir_expand::name::Name;
  11 use la_arena::{Arena, Idx};
  12
  13 use crate::{Const, ConstData, ConstValue, Interner, Ty, TyKind};
  14
  15 /// Extension trait for [`Const`]
  16 pub trait ConstExt {
  17     /// Is a [`Const`] unknown?
  18     fn is_unknown(&self) -> bool;
  19 }
  20
  21 impl ConstExt for Const {
  22     fn is_unknown(&self) -> bool {
  23         match self.data(Interner).value {
  24             // interned Unknown
  25             chalk_ir::ConstValue::Concrete(chalk_ir::ConcreteConst {
  26                 interned: ConstScalar::Unknown,
  27             }) => true,
  28
  29             // interned concrete anything else
  30             chalk_ir::ConstValue::Concrete(..) => false,
  31
  32             _ => {
  33                 tracing::error!(
  34                     "is_unknown was called on a non-concrete constant value! {:?}",
  35                     self
  36                 );
  37                 true
  38             }
  39         }
  40     }
  41 }
  42
  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,
  48 }
  49
  50 #[derive(Debug, Clone)]
  51 pub enum ConstEvalError {
  52     NotSupported(&'static str),
  53     TypeError,
  54     IncompleteExpr,
  55     Panic(String),
  56 }
  57
  58 #[derive(Debug, Clone)]
  59 pub enum ComputedExpr {
  60     Literal(Literal),
  61     Tuple(Box<[ComputedExpr]>),
  62 }
  63
  64 impl Display for ComputedExpr {
  65     fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
  66         match self {
  67             ComputedExpr::Literal(l) => match l {
  68                 Literal::Int(x, _) => {
  69                     if *x >= 16 {
  70                         write!(f, "{} ({:#X})", x, x)
  71                     } else {
  72                         write!(f, "{}", x)
  73                     }
  74                 }
  75                 Literal::Uint(x, _) => {
  76                     if *x >= 16 {
  77                         write!(f, "{} ({:#X})", x, x)
  78                     } else {
  79                         write!(f, "{}", x)
  80                     }
  81                 }
  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),
  87             },
  88             ComputedExpr::Tuple(t) => {
  89                 write!(f, "(")?;
  90                 for x in &**t {
  91                     write!(f, "{}, ", x)?;
  92                 }
  93                 write!(f, ")")
  94             }
  95         }
  96     }
  97 }
  98
  99 fn scalar_max(scalar: &Scalar) -> i128 {
 100     match scalar {
 101         Scalar::Bool => 1,
 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,
 110         },
 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
 118         },
 119         Scalar::Float(_) => 0,
 120     }
 121 }
 122
 123 fn is_valid(scalar: &Scalar, value: i128) -> bool {
 124     if value < 0 {
 125         !matches!(scalar, Scalar::Uint(_)) && -scalar_max(scalar) - 1 <= value
 126     } else {
 127         value <= scalar_max(scalar)
 128     }
 129 }
 130
 131 pub fn eval_const(expr: &Expr, ctx: &mut ConstEvalCtx<'_>) -> Result<ComputedExpr, ConstEvalError> {
 132     match expr {
 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)?;
 137             match op {
 138                 hir_def::expr::UnaryOp::Deref => Err(ConstEvalError::NotSupported("deref")),
 139                 hir_def::expr::UnaryOp::Not => {
 140                     let v = match ev {
 141                         ComputedExpr::Literal(Literal::Bool(b)) => {
 142                             return Ok(ComputedExpr::Literal(Literal::Bool(!b)))
 143                         }
 144                         ComputedExpr::Literal(Literal::Int(v, _)) => v,
 145                         ComputedExpr::Literal(Literal::Uint(v, _)) => v
 146                             .try_into()
 147                             .map_err(|_| ConstEvalError::NotSupported("too big u128"))?,
 148                         _ => return Err(ConstEvalError::NotSupported("this kind of operator")),
 149                     };
 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"))
 158                             }
 159                             chalk_ir::UintTy::Usize => !(v as usize) as i128,
 160                         },
 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,
 168                         },
 169                         _ => return Err(ConstEvalError::NotSupported("unreachable?")),
 170                     };
 171                     Ok(ComputedExpr::Literal(Literal::Int(r, None)))
 172                 }
 173                 hir_def::expr::UnaryOp::Neg => {
 174                     let v = match ev {
 175                         ComputedExpr::Literal(Literal::Int(v, _)) => v,
 176                         ComputedExpr::Literal(Literal::Uint(v, _)) => v
 177                             .try_into()
 178                             .map_err(|_| ConstEvalError::NotSupported("too big u128"))?,
 179                         _ => return Err(ConstEvalError::NotSupported("this kind of operator")),
 180                     };
 181                     Ok(ComputedExpr::Literal(Literal::Int(
 182                         v.checked_neg().ok_or_else(|| {
 183                             ConstEvalError::Panic("overflow in negation".to_string())
 184                         })?,
 185                         None,
 186                     )))
 187                 }
 188             }
 189         }
 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)?;
 195             let v1 = match lhs {
 196                 ComputedExpr::Literal(Literal::Int(v, _)) => v,
 197                 ComputedExpr::Literal(Literal::Uint(v, _)) => {
 198                     v.try_into().map_err(|_| ConstEvalError::NotSupported("too big u128"))?
 199                 }
 200                 _ => return Err(ConstEvalError::NotSupported("this kind of operator")),
 201             };
 202             let v2 = match rhs {
 203                 ComputedExpr::Literal(Literal::Int(v, _)) => v,
 204                 ComputedExpr::Literal(Literal::Uint(v, _)) => {
 205                     v.try_into().map_err(|_| ConstEvalError::NotSupported("too big u128"))?
 206                 }
 207                 _ => return Err(ConstEvalError::NotSupported("this kind of operator")),
 208             };
 209             match op {
 210                 BinaryOp::ArithOp(b) => {
 211                     let panic_arith = ConstEvalError::Panic(
 212                         "attempt to run invalid arithmetic operation".to_string(),
 213                     );
 214                     let r = match b {
 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())?,
 220                         ArithOp::Shl => v1
 221                             .checked_shl(v2.try_into().map_err(|_| panic_arith.clone())?)
 222                             .ok_or_else(|| panic_arith.clone())?,
 223                         ArithOp::Shr => v1
 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,
 229                     };
 230                     if let TyKind::Scalar(s) = ty.kind(Interner) {
 231                         if !is_valid(s, r) {
 232                             return Err(panic_arith);
 233                         }
 234                     }
 235                     Ok(ComputedExpr::Literal(Literal::Int(r, None)))
 236                 }
 237                 BinaryOp::LogicOp(_) => Err(ConstEvalError::TypeError),
 238                 _ => return Err(ConstEvalError::NotSupported("bin op on this operators")),
 239             }
 240         }
 241         Expr::Block { statements, tail, .. } => {
 242             let mut prev_values = HashMap::<Name, Option<ComputedExpr>>::default();
 243             for statement in &**statements {
 244                 match statement {
 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(),
 249                             _ => {
 250                                 return Err(ConstEvalError::NotSupported("complex patterns in let"))
 251                             }
 252                         };
 253                         let value = match initializer {
 254                             Some(x) => eval_const(&ctx.exprs[x], ctx)?,
 255                             None => continue,
 256                         };
 257                         if !prev_values.contains_key(&name) {
 258                             let prev = ctx.local_data.insert(name.clone(), value);
 259                             prev_values.insert(name, prev);
 260                         } else {
 261                             ctx.local_data.insert(name, value);
 262                         }
 263                     }
 264                     &hir_def::expr::Statement::Expr { .. } => {
 265                         return Err(ConstEvalError::NotSupported("this kind of statement"))
 266                     }
 267                 }
 268             }
 269             let r = match tail {
 270                 &Some(x) => eval_const(&ctx.exprs[x], ctx),
 271                 None => Ok(ComputedExpr::Tuple(Box::new([]))),
 272             };
 273             // clean up local data, so caller will receive the exact map that passed to us
 274             for (name, val) in prev_values {
 275                 match val {
 276                     Some(x) => ctx.local_data.insert(name, x),
 277                     None => ctx.local_data.remove(&name),
 278                 };
 279             }
 280             r
 281         }
 282         Expr::Path(p) => {
 283             let name = p.mod_path().as_ident().ok_or(ConstEvalError::NotSupported("big paths"))?;
 284             let r = ctx
 285                 .local_data
 286                 .get(name)
 287                 .ok_or(ConstEvalError::NotSupported("Non local name resolution"))?;
 288             Ok(r.clone())
 289         }
 290         _ => Err(ConstEvalError::NotSupported("This kind of expression")),
 291     }
 292 }
 293
 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) {
 297         match ce {
 298             ComputedExpr::Literal(Literal::Int(x, _)) => return x.try_into().ok(),
 299             ComputedExpr::Literal(Literal::Uint(x, _)) => return x.try_into().ok(),
 300             _ => {}
 301         }
 302     }
 303     None
 304 }
 305
 306 /// Interns a possibly-unknown target usize
 307 pub fn usize_const(value: Option<u64>) -> Const {
 308     ConstData {
 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),
 312         }),
 313     }
 314     .intern(Interner)
 315 }