[rustc.git] / src / tools / rust-analyzer / crates / hir-ty / src / consteval.rs

//! Constant evaluation details

use std::{
    collections::HashMap,
    fmt::{Display, Write},
};

use chalk_ir::{BoundVar, DebruijnIndex, GenericArgData, IntTy, Scalar};
use hir_def::{
    expr::{ArithOp, BinaryOp, Expr, ExprId, Literal, Pat, PatId},
    path::ModPath,
    resolver::{resolver_for_expr, ResolveValueResult, Resolver, ValueNs},
    type_ref::ConstScalar,
    ConstId, DefWithBodyId,
};
use la_arena::{Arena, Idx};
use stdx::never;

use crate::{
    db::HirDatabase, infer::InferenceContext, lower::ParamLoweringMode, to_placeholder_idx,
    utils::Generics, Const, ConstData, ConstValue, GenericArg, InferenceResult, Interner, Ty,
    TyBuilder, TyKind,
};

/// Extension trait for [`Const`]
pub trait ConstExt {
    /// Is a [`Const`] unknown?
    fn is_unknown(&self) -> bool;
}

impl ConstExt for Const {
    fn is_unknown(&self) -> bool {
        match self.data(Interner).value {
            // interned Unknown
            chalk_ir::ConstValue::Concrete(chalk_ir::ConcreteConst {
                interned: ConstScalar::Unknown,
            }) => true,

            // interned concrete anything else
            chalk_ir::ConstValue::Concrete(..) => false,

            _ => {
                tracing::error!(
                    "is_unknown was called on a non-concrete constant value! {:?}",
                    self
                );
                true
            }
        }
    }
}

pub struct ConstEvalCtx<'a> {
    pub db: &'a dyn HirDatabase,
    pub owner: DefWithBodyId,
    pub exprs: &'a Arena<Expr>,
    pub pats: &'a Arena<Pat>,
    pub local_data: HashMap<PatId, ComputedExpr>,
    infer: &'a InferenceResult,
}

impl ConstEvalCtx<'_> {
    fn expr_ty(&mut self, expr: ExprId) -> Ty {
        self.infer[expr].clone()
    }
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub enum ConstEvalError {
    NotSupported(&'static str),
    SemanticError(&'static str),
    Loop,
    IncompleteExpr,
    Panic(String),
}

#[derive(Debug, Clone, PartialEq, Eq)]
pub enum ComputedExpr {
    Literal(Literal),
    Tuple(Box<[ComputedExpr]>),
}

impl Display for ComputedExpr {
    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
        match self {
            ComputedExpr::Literal(l) => match l {
                Literal::Int(x, _) => {
                    if *x >= 10 {
                        write!(f, "{} ({:#X})", x, x)
                    } else {
                        x.fmt(f)
                    }
                }
                Literal::Uint(x, _) => {
                    if *x >= 10 {
                        write!(f, "{} ({:#X})", x, x)
                    } else {
                        x.fmt(f)
                    }
                }
                Literal::Float(x, _) => x.fmt(f),
                Literal::Bool(x) => x.fmt(f),
                Literal::Char(x) => std::fmt::Debug::fmt(x, f),
                Literal::String(x) => std::fmt::Debug::fmt(x, f),
                Literal::ByteString(x) => std::fmt::Debug::fmt(x, f),
            },
            ComputedExpr::Tuple(t) => {
                f.write_char('(')?;
                for x in &**t {
                    x.fmt(f)?;
                    f.write_str(", ")?;
                }
                f.write_char(')')
            }
        }
    }
}

fn scalar_max(scalar: &Scalar) -> i128 {
    match scalar {
        Scalar::Bool => 1,
        Scalar::Char => u32::MAX as i128,
        Scalar::Int(x) => match x {
            IntTy::Isize => isize::MAX as i128,
            IntTy::I8 => i8::MAX as i128,
            IntTy::I16 => i16::MAX as i128,
            IntTy::I32 => i32::MAX as i128,
            IntTy::I64 => i64::MAX as i128,
            IntTy::I128 => i128::MAX as i128,
        },
        Scalar::Uint(x) => match x {
            chalk_ir::UintTy::Usize => usize::MAX as i128,
            chalk_ir::UintTy::U8 => u8::MAX as i128,
            chalk_ir::UintTy::U16 => u16::MAX as i128,
            chalk_ir::UintTy::U32 => u32::MAX as i128,
            chalk_ir::UintTy::U64 => u64::MAX as i128,
            chalk_ir::UintTy::U128 => i128::MAX as i128, // ignore too big u128 for now
        },
        Scalar::Float(_) => 0,
    }
}

fn is_valid(scalar: &Scalar, value: i128) -> bool {
    if value < 0 {
        !matches!(scalar, Scalar::Uint(_)) && -scalar_max(scalar) - 1 <= value
    } else {
        value <= scalar_max(scalar)
    }
}

pub fn eval_const(
    expr_id: ExprId,
    ctx: &mut ConstEvalCtx<'_>,
) -> Result<ComputedExpr, ConstEvalError> {
    let expr = &ctx.exprs[expr_id];
    match expr {
        Expr::Missing => Err(ConstEvalError::IncompleteExpr),
        Expr::Literal(l) => Ok(ComputedExpr::Literal(l.clone())),
        &Expr::UnaryOp { expr, op } => {
            let ty = &ctx.expr_ty(expr);
            let ev = eval_const(expr, ctx)?;
            match op {
                hir_def::expr::UnaryOp::Deref => Err(ConstEvalError::NotSupported("deref")),
                hir_def::expr::UnaryOp::Not => {
                    let v = match ev {
                        ComputedExpr::Literal(Literal::Bool(b)) => {
                            return Ok(ComputedExpr::Literal(Literal::Bool(!b)))
                        }
                        ComputedExpr::Literal(Literal::Int(v, _)) => v,
                        ComputedExpr::Literal(Literal::Uint(v, _)) => v
                            .try_into()
                            .map_err(|_| ConstEvalError::NotSupported("too big u128"))?,
                        _ => return Err(ConstEvalError::NotSupported("this kind of operator")),
                    };
                    let r = match ty.kind(Interner) {
                        TyKind::Scalar(Scalar::Uint(x)) => match x {
                            chalk_ir::UintTy::U8 => !(v as u8) as i128,
                            chalk_ir::UintTy::U16 => !(v as u16) as i128,
                            chalk_ir::UintTy::U32 => !(v as u32) as i128,
                            chalk_ir::UintTy::U64 => !(v as u64) as i128,
                            chalk_ir::UintTy::U128 => {
                                return Err(ConstEvalError::NotSupported("negation of u128"))
                            }
                            chalk_ir::UintTy::Usize => !(v as usize) as i128,
                        },
                        TyKind::Scalar(Scalar::Int(x)) => match x {
                            chalk_ir::IntTy::I8 => !(v as i8) as i128,
                            chalk_ir::IntTy::I16 => !(v as i16) as i128,
                            chalk_ir::IntTy::I32 => !(v as i32) as i128,
                            chalk_ir::IntTy::I64 => !(v as i64) as i128,
                            chalk_ir::IntTy::I128 => !v,
                            chalk_ir::IntTy::Isize => !(v as isize) as i128,
                        },
                        _ => return Err(ConstEvalError::NotSupported("unreachable?")),
                    };
                    Ok(ComputedExpr::Literal(Literal::Int(r, None)))
                }
                hir_def::expr::UnaryOp::Neg => {
                    let v = match ev {
                        ComputedExpr::Literal(Literal::Int(v, _)) => v,
                        ComputedExpr::Literal(Literal::Uint(v, _)) => v
                            .try_into()
                            .map_err(|_| ConstEvalError::NotSupported("too big u128"))?,
                        _ => return Err(ConstEvalError::NotSupported("this kind of operator")),
                    };
                    Ok(ComputedExpr::Literal(Literal::Int(
                        v.checked_neg().ok_or_else(|| {
                            ConstEvalError::Panic("overflow in negation".to_string())
                        })?,
                        None,
                    )))
                }
            }
        }
        &Expr::BinaryOp { lhs, rhs, op } => {
            let ty = &ctx.expr_ty(lhs);
            let lhs = eval_const(lhs, ctx)?;
            let rhs = eval_const(rhs, ctx)?;
            let op = op.ok_or(ConstEvalError::IncompleteExpr)?;
            let v1 = match lhs {
                ComputedExpr::Literal(Literal::Int(v, _)) => v,
                ComputedExpr::Literal(Literal::Uint(v, _)) => {
                    v.try_into().map_err(|_| ConstEvalError::NotSupported("too big u128"))?
                }
                _ => return Err(ConstEvalError::NotSupported("this kind of operator")),
            };
            let v2 = match rhs {
                ComputedExpr::Literal(Literal::Int(v, _)) => v,
                ComputedExpr::Literal(Literal::Uint(v, _)) => {
                    v.try_into().map_err(|_| ConstEvalError::NotSupported("too big u128"))?
                }
                _ => return Err(ConstEvalError::NotSupported("this kind of operator")),
            };
            match op {
                BinaryOp::ArithOp(b) => {
                    let panic_arith = ConstEvalError::Panic(
                        "attempt to run invalid arithmetic operation".to_string(),
                    );
                    let r = match b {
                        ArithOp::Add => v1.checked_add(v2).ok_or_else(|| panic_arith.clone())?,
                        ArithOp::Mul => v1.checked_mul(v2).ok_or_else(|| panic_arith.clone())?,
                        ArithOp::Sub => v1.checked_sub(v2).ok_or_else(|| panic_arith.clone())?,
                        ArithOp::Div => v1.checked_div(v2).ok_or_else(|| panic_arith.clone())?,
                        ArithOp::Rem => v1.checked_rem(v2).ok_or_else(|| panic_arith.clone())?,
                        ArithOp::Shl => v1
                            .checked_shl(v2.try_into().map_err(|_| panic_arith.clone())?)
                            .ok_or_else(|| panic_arith.clone())?,
                        ArithOp::Shr => v1
                            .checked_shr(v2.try_into().map_err(|_| panic_arith.clone())?)
                            .ok_or_else(|| panic_arith.clone())?,
                        ArithOp::BitXor => v1 ^ v2,
                        ArithOp::BitOr => v1 | v2,
                        ArithOp::BitAnd => v1 & v2,
                    };
                    if let TyKind::Scalar(s) = ty.kind(Interner) {
                        if !is_valid(s, r) {
                            return Err(panic_arith);
                        }
                    }
                    Ok(ComputedExpr::Literal(Literal::Int(r, None)))
                }
                BinaryOp::LogicOp(_) => Err(ConstEvalError::SemanticError("logic op on numbers")),
                _ => Err(ConstEvalError::NotSupported("bin op on this operators")),
            }
        }
        Expr::Block { statements, tail, .. } => {
            let mut prev_values = HashMap::<PatId, Option<ComputedExpr>>::default();
            for statement in &**statements {
                match *statement {
                    hir_def::expr::Statement::Let { pat: pat_id, initializer, .. } => {
                        let pat = &ctx.pats[pat_id];
                        match pat {
                            Pat::Bind { subpat, .. } if subpat.is_none() => (),
                            _ => {
                                return Err(ConstEvalError::NotSupported("complex patterns in let"))
                            }
                        };
                        let value = match initializer {
                            Some(x) => eval_const(x, ctx)?,
                            None => continue,
                        };
                        if !prev_values.contains_key(&pat_id) {
                            let prev = ctx.local_data.insert(pat_id, value);
                            prev_values.insert(pat_id, prev);
                        } else {
                            ctx.local_data.insert(pat_id, value);
                        }
                    }
                    hir_def::expr::Statement::Expr { .. } => {
                        return Err(ConstEvalError::NotSupported("this kind of statement"))
                    }
                }
            }
            let r = match tail {
                &Some(x) => eval_const(x, ctx),
                None => Ok(ComputedExpr::Tuple(Box::new([]))),
            };
            // clean up local data, so caller will receive the exact map that passed to us
            for (name, val) in prev_values {
                match val {
                    Some(x) => ctx.local_data.insert(name, x),
                    None => ctx.local_data.remove(&name),
                };
            }
            r
        }
        Expr::Path(p) => {
            let resolver = resolver_for_expr(ctx.db.upcast(), ctx.owner, expr_id);
            let pr = resolver
                .resolve_path_in_value_ns(ctx.db.upcast(), p.mod_path())
                .ok_or(ConstEvalError::SemanticError("unresolved path"))?;
            let pr = match pr {
                ResolveValueResult::ValueNs(v) => v,
                ResolveValueResult::Partial(..) => {
                    return match ctx
                        .infer
                        .assoc_resolutions_for_expr(expr_id)
                        .ok_or(ConstEvalError::SemanticError("unresolved assoc item"))?
                    {
                        hir_def::AssocItemId::FunctionId(_) => {
                            Err(ConstEvalError::NotSupported("assoc function"))
                        }
                        hir_def::AssocItemId::ConstId(c) => ctx.db.const_eval(c),
                        hir_def::AssocItemId::TypeAliasId(_) => {
                            Err(ConstEvalError::NotSupported("assoc type alias"))
                        }
                    }
                }
            };
            match pr {
                ValueNs::LocalBinding(pat_id) => {
                    let r = ctx
                        .local_data
                        .get(&pat_id)
                        .ok_or(ConstEvalError::NotSupported("Unexpected missing local"))?;
                    Ok(r.clone())
                }
                ValueNs::ConstId(id) => ctx.db.const_eval(id),
                ValueNs::GenericParam(_) => {
                    Err(ConstEvalError::NotSupported("const generic without substitution"))
                }
                _ => Err(ConstEvalError::NotSupported("path that are not const or local")),
            }
        }
        _ => Err(ConstEvalError::NotSupported("This kind of expression")),
    }
}

pub(crate) fn path_to_const(
    db: &dyn HirDatabase,
    resolver: &Resolver,
    path: &ModPath,
    mode: ParamLoweringMode,
    args_lazy: impl FnOnce() -> Generics,
    debruijn: DebruijnIndex,
) -> Option<Const> {
    match resolver.resolve_path_in_value_ns_fully(db.upcast(), &path) {
        Some(ValueNs::GenericParam(p)) => {
            let ty = db.const_param_ty(p);
            let args = args_lazy();
            let value = match mode {
                ParamLoweringMode::Placeholder => {
                    ConstValue::Placeholder(to_placeholder_idx(db, p.into()))
                }
                ParamLoweringMode::Variable => match args.param_idx(p.into()) {
                    Some(x) => ConstValue::BoundVar(BoundVar::new(debruijn, x)),
                    None => {
                        never!(
                            "Generic list doesn't contain this param: {:?}, {}, {:?}",
                            args,
                            path,
                            p
                        );
                        return None;
                    }
                },
            };
            Some(ConstData { ty, value }.intern(Interner))
        }
        _ => None,
    }
}

pub fn unknown_const(ty: Ty) -> Const {
    ConstData {
        ty,
        value: ConstValue::Concrete(chalk_ir::ConcreteConst { interned: ConstScalar::Unknown }),
    }
    .intern(Interner)
}

pub fn unknown_const_as_generic(ty: Ty) -> GenericArg {
    GenericArgData::Const(unknown_const(ty)).intern(Interner)
}

/// Interns a constant scalar with the given type
pub fn intern_const_scalar(value: ConstScalar, ty: Ty) -> Const {
    ConstData { ty, value: ConstValue::Concrete(chalk_ir::ConcreteConst { interned: value }) }
        .intern(Interner)
}

/// Interns a possibly-unknown target usize
pub fn usize_const(value: Option<u128>) -> Const {
    intern_const_scalar(value.map_or(ConstScalar::Unknown, ConstScalar::UInt), TyBuilder::usize())
}

pub(crate) fn const_eval_recover(
    _: &dyn HirDatabase,
    _: &[String],
    _: &ConstId,
) -> Result<ComputedExpr, ConstEvalError> {
    Err(ConstEvalError::Loop)
}

pub(crate) fn const_eval_query(
    db: &dyn HirDatabase,
    const_id: ConstId,
) -> Result<ComputedExpr, ConstEvalError> {
    let def = const_id.into();
    let body = db.body(def);
    let infer = &db.infer(def);
    let result = eval_const(
        body.body_expr,
        &mut ConstEvalCtx {
            db,
            owner: const_id.into(),
            exprs: &body.exprs,
            pats: &body.pats,
            local_data: HashMap::default(),
            infer,
        },
    );
    result
}

pub(crate) fn eval_to_const<'a>(
    expr: Idx<Expr>,
    mode: ParamLoweringMode,
    ctx: &mut InferenceContext<'a>,
    args: impl FnOnce() -> Generics,
    debruijn: DebruijnIndex,
) -> Const {
    if let Expr::Path(p) = &ctx.body.exprs[expr] {
        let db = ctx.db;
        let resolver = &ctx.resolver;
        if let Some(c) = path_to_const(db, resolver, p.mod_path(), mode, args, debruijn) {
            return c;
        }
    }
    let body = ctx.body.clone();
    let mut ctx = ConstEvalCtx {
        db: ctx.db,
        owner: ctx.owner,
        exprs: &body.exprs,
        pats: &body.pats,
        local_data: HashMap::default(),
        infer: &ctx.result,
    };
    let computed_expr = eval_const(expr, &mut ctx);
    let const_scalar = match computed_expr {
        Ok(ComputedExpr::Literal(literal)) => literal.into(),
        _ => ConstScalar::Unknown,
    };
    intern_const_scalar(const_scalar, TyBuilder::usize())
}

#[cfg(test)]
mod tests;
Commit	Line	Data
064997fb FG	1	//! Constant evaluation details
	2
	3	use std::{
	4	collections::HashMap,
064997fb FG	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;