compiler/rustc_trait_selection/src/traits/const_evaluatable.rs

   1 #![allow(warnings)]
   2 use rustc_hir::def::DefKind;
   3 use rustc_index::bit_set::BitSet;
   4 use rustc_index::vec::IndexVec;
   5 use rustc_infer::infer::InferCtxt;
   6 use rustc_middle::mir::abstract_const::{Node, NodeId};
   7 use rustc_middle::mir::interpret::ErrorHandled;
   8 use rustc_middle::mir::visit::Visitor;
   9 use rustc_middle::mir::{self, Rvalue, StatementKind, TerminatorKind};
  10 use rustc_middle::ty::subst::Subst;
  11 use rustc_middle::ty::subst::SubstsRef;
  12 use rustc_middle::ty::{self, TyCtxt, TypeFoldable};
  13 use rustc_session::lint;
  14 use rustc_span::def_id::{DefId, LocalDefId};
  15 use rustc_span::Span;
  16
  17 pub fn is_const_evaluatable<'cx, 'tcx>(
  18     infcx: &InferCtxt<'cx, 'tcx>,
  19     def: ty::WithOptConstParam<DefId>,
  20     substs: SubstsRef<'tcx>,
  21     param_env: ty::ParamEnv<'tcx>,
  22     span: Span,
  23 ) -> Result<(), ErrorHandled> {
  24     debug!("is_const_evaluatable({:?}, {:?})", def, substs);
  25     if infcx.tcx.features().const_evaluatable_checked {
  26         if let Some(ct) = AbstractConst::new(infcx.tcx, def, substs) {
  27             for pred in param_env.caller_bounds() {
  28                 match pred.skip_binders() {
  29                     ty::PredicateAtom::ConstEvaluatable(b_def, b_substs) => {
  30                         debug!("is_const_evaluatable: caller_bound={:?}, {:?}", b_def, b_substs);
  31                         if b_def == def && b_substs == substs {
  32                             debug!("is_const_evaluatable: caller_bound ~~> ok");
  33                             return Ok(());
  34                         } else if AbstractConst::new(infcx.tcx, b_def, b_substs)
  35                             .map_or(false, |b_ct| try_unify(infcx.tcx, ct, b_ct))
  36                         {
  37                             debug!("is_const_evaluatable: abstract_const ~~> ok");
  38                             return Ok(());
  39                         }
  40                     }
  41                     _ => {} // don't care
  42                 }
  43             }
  44         }
  45     }
  46
  47     let future_compat_lint = || {
  48         if let Some(local_def_id) = def.did.as_local() {
  49             infcx.tcx.struct_span_lint_hir(
  50                 lint::builtin::CONST_EVALUATABLE_UNCHECKED,
  51                 infcx.tcx.hir().local_def_id_to_hir_id(local_def_id),
  52                 span,
  53                 |err| {
  54                     err.build("cannot use constants which depend on generic parameters in types")
  55                         .emit();
  56                 },
  57             );
  58         }
  59     };
  60
  61     // FIXME: We should only try to evaluate a given constant here if it is fully concrete
  62     // as we don't want to allow things like `[u8; std::mem::size_of::<*mut T>()]`.
  63     //
  64     // We previously did not check this, so we only emit a future compat warning if
  65     // const evaluation succeeds and the given constant is still polymorphic for now
  66     // and hopefully soon change this to an error.
  67     //
  68     // See #74595 for more details about this.
  69     let concrete = infcx.const_eval_resolve(param_env, def, substs, None, Some(span));
  70
  71     if concrete.is_ok() && substs.has_param_types_or_consts() {
  72         match infcx.tcx.def_kind(def.did) {
  73             DefKind::AnonConst => {
  74                 let mir_body = if let Some(def) = def.as_const_arg() {
  75                     infcx.tcx.optimized_mir_of_const_arg(def)
  76                 } else {
  77                     infcx.tcx.optimized_mir(def.did)
  78                 };
  79
  80                 if mir_body.is_polymorphic {
  81                     future_compat_lint();
  82                 }
  83             }
  84             _ => future_compat_lint(),
  85         }
  86     }
  87
  88     debug!(?concrete, "is_const_evaluatable");
  89     concrete.map(drop)
  90 }
  91
  92 /// A tree representing an anonymous constant.
  93 ///
  94 /// This is only able to represent a subset of `MIR`,
  95 /// and should not leak any information about desugarings.
  96 #[derive(Clone, Copy)]
  97 pub struct AbstractConst<'tcx> {
  98     // FIXME: Consider adding something like `IndexSlice`
  99     // and use this here.
 100     inner: &'tcx [Node<'tcx>],
 101     substs: SubstsRef<'tcx>,
 102 }
 103
 104 impl AbstractConst<'tcx> {
 105     pub fn new(
 106         tcx: TyCtxt<'tcx>,
 107         def: ty::WithOptConstParam<DefId>,
 108         substs: SubstsRef<'tcx>,
 109     ) -> Option<AbstractConst<'tcx>> {
 110         let inner = match (def.did.as_local(), def.const_param_did) {
 111             (Some(did), Some(param_did)) => {
 112                 tcx.mir_abstract_const_of_const_arg((did, param_did))?
 113             }
 114             _ => tcx.mir_abstract_const(def.did)?,
 115         };
 116
 117         Some(AbstractConst { inner, substs })
 118     }
 119
 120     #[inline]
 121     pub fn subtree(self, node: NodeId) -> AbstractConst<'tcx> {
 122         AbstractConst { inner: &self.inner[..=node.index()], substs: self.substs }
 123     }
 124
 125     #[inline]
 126     pub fn root(self) -> Node<'tcx> {
 127         self.inner.last().copied().unwrap()
 128     }
 129 }
 130
 131 struct AbstractConstBuilder<'a, 'tcx> {
 132     tcx: TyCtxt<'tcx>,
 133     body: &'a mir::Body<'tcx>,
 134     nodes: IndexVec<NodeId, Node<'tcx>>,
 135     locals: IndexVec<mir::Local, NodeId>,
 136     checked_op_locals: BitSet<mir::Local>,
 137 }
 138
 139 impl<'a, 'tcx> AbstractConstBuilder<'a, 'tcx> {
 140     fn new(tcx: TyCtxt<'tcx>, body: &'a mir::Body<'tcx>) -> Option<AbstractConstBuilder<'a, 'tcx>> {
 141         if body.is_cfg_cyclic() {
 142             return None;
 143         }
 144
 145         Some(AbstractConstBuilder {
 146             tcx,
 147             body,
 148             nodes: IndexVec::new(),
 149             locals: IndexVec::from_elem(NodeId::MAX, &body.local_decls),
 150             checked_op_locals: BitSet::new_empty(body.local_decls.len()),
 151         })
 152     }
 153
 154     fn operand_to_node(&mut self, op: &mir::Operand<'tcx>) -> Option<NodeId> {
 155         debug!("operand_to_node: op={:?}", op);
 156         const ZERO_FIELD: mir::Field = mir::Field::from_usize(0);
 157         match op {
 158             mir::Operand::Copy(p) | mir::Operand::Move(p) => {
 159                 if let Some(p) = p.as_local() {
 160                     debug_assert!(!self.checked_op_locals.contains(p));
 161                     Some(self.locals[p])
 162                 } else if let &[mir::ProjectionElem::Field(ZERO_FIELD, _)] = p.projection.as_ref() {
 163                     // Only allow field accesses on the result of checked operations.
 164                     if self.checked_op_locals.contains(p.local) {
 165                         Some(self.locals[p.local])
 166                     } else {
 167                         None
 168                     }
 169                 } else {
 170                     None
 171                 }
 172             }
 173             mir::Operand::Constant(ct) => Some(self.nodes.push(Node::Leaf(ct.literal))),
 174         }
 175     }
 176
 177     /// We do not allow all binary operations in abstract consts, so filter disallowed ones.
 178     fn check_binop(op: mir::BinOp) -> bool {
 179         use mir::BinOp::*;
 180         match op {
 181             Add | Sub | Mul | Div | Rem | BitXor | BitAnd | BitOr | Shl | Shr | Eq | Lt | Le
 182             | Ne | Ge | Gt => true,
 183             Offset => false,
 184         }
 185     }
 186
 187     /// While we currently allow all unary operations, we still want to explicitly guard against
 188     /// future changes here.
 189     fn check_unop(op: mir::UnOp) -> bool {
 190         use mir::UnOp::*;
 191         match op {
 192             Not | Neg => true,
 193         }
 194     }
 195
 196     fn build_statement(&mut self, stmt: &mir::Statement<'tcx>) -> Option<()> {
 197         debug!("AbstractConstBuilder: stmt={:?}", stmt);
 198         match stmt.kind {
 199             StatementKind::Assign(box (ref place, ref rvalue)) => {
 200                 let local = place.as_local()?;
 201                 match *rvalue {
 202                     Rvalue::Use(ref operand) => {
 203                         self.locals[local] = self.operand_to_node(operand)?;
 204                         Some(())
 205                     }
 206                     Rvalue::BinaryOp(op, ref lhs, ref rhs) if Self::check_binop(op) => {
 207                         let lhs = self.operand_to_node(lhs)?;
 208                         let rhs = self.operand_to_node(rhs)?;
 209                         self.locals[local] = self.nodes.push(Node::Binop(op, lhs, rhs));
 210                         if op.is_checkable() {
 211                             bug!("unexpected unchecked checkable binary operation");
 212                         } else {
 213                             Some(())
 214                         }
 215                     }
 216                     Rvalue::CheckedBinaryOp(op, ref lhs, ref rhs) if Self::check_binop(op) => {
 217                         let lhs = self.operand_to_node(lhs)?;
 218                         let rhs = self.operand_to_node(rhs)?;
 219                         self.locals[local] = self.nodes.push(Node::Binop(op, lhs, rhs));
 220                         self.checked_op_locals.insert(local);
 221                         Some(())
 222                     }
 223                     Rvalue::UnaryOp(op, ref operand) if Self::check_unop(op) => {
 224                         let operand = self.operand_to_node(operand)?;
 225                         self.locals[local] = self.nodes.push(Node::UnaryOp(op, operand));
 226                         Some(())
 227                     }
 228                     _ => None,
 229                 }
 230             }
 231             // These are not actually relevant for us here, so we can ignore them.
 232             StatementKind::StorageLive(_) | StatementKind::StorageDead(_) => Some(()),
 233             _ => None,
 234         }
 235     }
 236
 237     fn build_terminator(
 238         &mut self,
 239         terminator: &mir::Terminator<'tcx>,
 240     ) -> Option<Option<mir::BasicBlock>> {
 241         debug!("AbstractConstBuilder: terminator={:?}", terminator);
 242         match terminator.kind {
 243             TerminatorKind::Goto { target } => Some(Some(target)),
 244             TerminatorKind::Return => Some(None),
 245             TerminatorKind::Assert { ref cond, expected: false, target, .. } => {
 246                 let p = match cond {
 247                     mir::Operand::Copy(p) | mir::Operand::Move(p) => p,
 248                     mir::Operand::Constant(_) => bug!("Unexpected assert"),
 249                 };
 250
 251                 const ONE_FIELD: mir::Field = mir::Field::from_usize(1);
 252                 debug!("proj: {:?}", p.projection);
 253                 if let &[mir::ProjectionElem::Field(ONE_FIELD, _)] = p.projection.as_ref() {
 254                     // Only allow asserts checking the result of a checked operation.
 255                     if self.checked_op_locals.contains(p.local) {
 256                         return Some(Some(target));
 257                     }
 258                 }
 259
 260                 None
 261             }
 262             _ => None,
 263         }
 264     }
 265
 266     fn build(mut self) -> Option<&'tcx [Node<'tcx>]> {
 267         let mut block = &self.body.basic_blocks()[mir::START_BLOCK];
 268         loop {
 269             debug!("AbstractConstBuilder: block={:?}", block);
 270             for stmt in block.statements.iter() {
 271                 self.build_statement(stmt)?;
 272             }
 273
 274             if let Some(next) = self.build_terminator(block.terminator())? {
 275                 block = &self.body.basic_blocks()[next];
 276             } else {
 277                 return Some(self.tcx.arena.alloc_from_iter(self.nodes));
 278             }
 279         }
 280     }
 281 }
 282
 283 /// Builds an abstract const, do not use this directly, but use `AbstractConst::new` instead.
 284 pub(super) fn mir_abstract_const<'tcx>(
 285     tcx: TyCtxt<'tcx>,
 286     def: ty::WithOptConstParam<LocalDefId>,
 287 ) -> Option<&'tcx [Node<'tcx>]> {
 288     if tcx.features().const_evaluatable_checked {
 289         let body = tcx.mir_const(def).borrow();
 290         AbstractConstBuilder::new(tcx, &body)?.build()
 291     } else {
 292         None
 293     }
 294 }
 295
 296 pub(super) fn try_unify_abstract_consts<'tcx>(
 297     tcx: TyCtxt<'tcx>,
 298     ((a, a_substs), (b, b_substs)): (
 299         (ty::WithOptConstParam<DefId>, SubstsRef<'tcx>),
 300         (ty::WithOptConstParam<DefId>, SubstsRef<'tcx>),
 301     ),
 302 ) -> bool {
 303     if let Some(a) = AbstractConst::new(tcx, a, a_substs) {
 304         if let Some(b) = AbstractConst::new(tcx, b, b_substs) {
 305             return try_unify(tcx, a, b);
 306         }
 307     }
 308
 309     false
 310 }
 311
 312 pub(super) fn try_unify<'tcx>(
 313     tcx: TyCtxt<'tcx>,
 314     a: AbstractConst<'tcx>,
 315     b: AbstractConst<'tcx>,
 316 ) -> bool {
 317     match (a.root(), b.root()) {
 318         (Node::Leaf(a_ct), Node::Leaf(b_ct)) => {
 319             let a_ct = a_ct.subst(tcx, a.substs);
 320             let b_ct = b_ct.subst(tcx, b.substs);
 321             match (a_ct.val, b_ct.val) {
 322                 (ty::ConstKind::Param(a_param), ty::ConstKind::Param(b_param)) => {
 323                     a_param == b_param
 324                 }
 325                 (ty::ConstKind::Value(a_val), ty::ConstKind::Value(b_val)) => a_val == b_val,
 326                 // If we have `fn a<const N: usize>() -> [u8; N + 1]` and `fn b<const M: usize>() -> [u8; 1 + M]`
 327                 // we do not want to use `assert_eq!(a(), b())` to infer that `N` and `M` have to be `1`. This
 328                 // means that we can't do anything with inference variables here.
 329                 (ty::ConstKind::Infer(_), _) | (_, ty::ConstKind::Infer(_)) => false,
 330                 // FIXME(const_evaluatable_checked): We may want to either actually try
 331                 // to evaluate `a_ct` and `b_ct` if they are are fully concrete or something like
 332                 // this, for now we just return false here.
 333                 _ => false,
 334             }
 335         }
 336         (Node::Binop(a_op, al, ar), Node::Binop(b_op, bl, br)) if a_op == b_op => {
 337             try_unify(tcx, a.subtree(al), b.subtree(bl))
 338                 && try_unify(tcx, a.subtree(ar), b.subtree(br))
 339         }
 340         (Node::UnaryOp(a_op, av), Node::UnaryOp(b_op, bv)) if a_op == b_op => {
 341             try_unify(tcx, a.subtree(av), b.subtree(bv))
 342         }
 343         (Node::FunctionCall(a_f, a_args), Node::FunctionCall(b_f, b_args))
 344             if a_args.len() == b_args.len() =>
 345         {
 346             try_unify(tcx, a.subtree(a_f), b.subtree(b_f))
 347                 && a_args
 348                     .iter()
 349                     .zip(b_args)
 350                     .all(|(&an, &bn)| try_unify(tcx, a.subtree(an), b.subtree(bn)))
 351         }
 352         _ => false,
 353     }
 354 }