compiler/rustc_middle/src/ty/abstract_const.rs

   1 //! A subset of a mir body used for const evaluatability checking.
   2 use crate::mir;
   3 use crate::ty::visit::TypeVisitable;
   4 use crate::ty::{self, subst::Subst, DelaySpanBugEmitted, EarlyBinder, SubstsRef, Ty, TyCtxt};
   5 use rustc_errors::ErrorGuaranteed;
   6 use rustc_hir::def_id::DefId;
   7 use std::cmp;
   8 use std::ops::ControlFlow;
   9
  10 rustc_index::newtype_index! {
  11     /// An index into an `AbstractConst`.
  12     pub struct NodeId {
  13         derive [HashStable]
  14         DEBUG_FORMAT = "n{}",
  15     }
  16 }
  17
  18 /// A tree representing an anonymous constant.
  19 ///
  20 /// This is only able to represent a subset of `MIR`,
  21 /// and should not leak any information about desugarings.
  22 #[derive(Debug, Clone, Copy)]
  23 pub struct AbstractConst<'tcx> {
  24     // FIXME: Consider adding something like `IndexSlice`
  25     // and use this here.
  26     inner: &'tcx [Node<'tcx>],
  27     substs: SubstsRef<'tcx>,
  28 }
  29
  30 impl<'tcx> AbstractConst<'tcx> {
  31     pub fn new(
  32         tcx: TyCtxt<'tcx>,
  33         uv: ty::Unevaluated<'tcx, ()>,
  34     ) -> Result<Option<AbstractConst<'tcx>>, ErrorGuaranteed> {
  35         let inner = tcx.thir_abstract_const_opt_const_arg(uv.def)?;
  36         debug!("AbstractConst::new({:?}) = {:?}", uv, inner);
  37         Ok(inner.map(|inner| AbstractConst { inner, substs: tcx.erase_regions(uv.substs) }))
  38     }
  39
  40     pub fn from_const(
  41         tcx: TyCtxt<'tcx>,
  42         ct: ty::Const<'tcx>,
  43     ) -> Result<Option<AbstractConst<'tcx>>, ErrorGuaranteed> {
  44         match ct.kind() {
  45             ty::ConstKind::Unevaluated(uv) => AbstractConst::new(tcx, uv.shrink()),
  46             ty::ConstKind::Error(DelaySpanBugEmitted { reported, .. }) => Err(reported),
  47             _ => Ok(None),
  48         }
  49     }
  50
  51     #[inline]
  52     pub fn subtree(self, node: NodeId) -> AbstractConst<'tcx> {
  53         AbstractConst { inner: &self.inner[..=node.index()], substs: self.substs }
  54     }
  55
  56     #[inline]
  57     pub fn root(self, tcx: TyCtxt<'tcx>) -> Node<'tcx> {
  58         let node = self.inner.last().copied().unwrap();
  59         match node {
  60             Node::Leaf(leaf) => Node::Leaf(EarlyBinder(leaf).subst(tcx, self.substs)),
  61             Node::Cast(kind, operand, ty) => {
  62                 Node::Cast(kind, operand, EarlyBinder(ty).subst(tcx, self.substs))
  63             }
  64             // Don't perform substitution on the following as they can't directly contain generic params
  65             Node::Binop(_, _, _) | Node::UnaryOp(_, _) | Node::FunctionCall(_, _) => node,
  66         }
  67     }
  68
  69     pub fn unify_failure_kind(self, tcx: TyCtxt<'tcx>) -> FailureKind {
  70         let mut failure_kind = FailureKind::Concrete;
  71         walk_abstract_const::<!, _>(tcx, self, |node| {
  72             match node.root(tcx) {
  73                 Node::Leaf(leaf) => {
  74                     if leaf.has_infer_types_or_consts() {
  75                         failure_kind = FailureKind::MentionsInfer;
  76                     } else if leaf.has_param_types_or_consts() {
  77                         failure_kind = cmp::min(failure_kind, FailureKind::MentionsParam);
  78                     }
  79                 }
  80                 Node::Cast(_, _, ty) => {
  81                     if ty.has_infer_types_or_consts() {
  82                         failure_kind = FailureKind::MentionsInfer;
  83                     } else if ty.has_param_types_or_consts() {
  84                         failure_kind = cmp::min(failure_kind, FailureKind::MentionsParam);
  85                     }
  86                 }
  87                 Node::Binop(_, _, _) | Node::UnaryOp(_, _) | Node::FunctionCall(_, _) => {}
  88             }
  89             ControlFlow::CONTINUE
  90         });
  91         failure_kind
  92     }
  93 }
  94
  95 #[derive(Debug, Clone, Copy, PartialEq, Eq, HashStable, TyEncodable, TyDecodable)]
  96 pub enum CastKind {
  97     /// thir::ExprKind::As
  98     As,
  99     /// thir::ExprKind::Use
 100     Use,
 101 }
 102
 103 /// A node of an `AbstractConst`.
 104 #[derive(Debug, Clone, Copy, PartialEq, Eq, HashStable, TyEncodable, TyDecodable)]
 105 pub enum Node<'tcx> {
 106     Leaf(ty::Const<'tcx>),
 107     Binop(mir::BinOp, NodeId, NodeId),
 108     UnaryOp(mir::UnOp, NodeId),
 109     FunctionCall(NodeId, &'tcx [NodeId]),
 110     Cast(CastKind, NodeId, Ty<'tcx>),
 111 }
 112
 113 #[derive(Debug, Copy, Clone, PartialEq, Eq, HashStable, TyEncodable, TyDecodable)]
 114 pub enum NotConstEvaluatable {
 115     Error(ErrorGuaranteed),
 116     MentionsInfer,
 117     MentionsParam,
 118 }
 119
 120 impl From<ErrorGuaranteed> for NotConstEvaluatable {
 121     fn from(e: ErrorGuaranteed) -> NotConstEvaluatable {
 122         NotConstEvaluatable::Error(e)
 123     }
 124 }
 125
 126 TrivialTypeTraversalAndLiftImpls! {
 127     NotConstEvaluatable,
 128 }
 129
 130 impl<'tcx> TyCtxt<'tcx> {
 131     #[inline]
 132     pub fn thir_abstract_const_opt_const_arg(
 133         self,
 134         def: ty::WithOptConstParam<DefId>,
 135     ) -> Result<Option<&'tcx [Node<'tcx>]>, ErrorGuaranteed> {
 136         if let Some((did, param_did)) = def.as_const_arg() {
 137             self.thir_abstract_const_of_const_arg((did, param_did))
 138         } else {
 139             self.thir_abstract_const(def.did)
 140         }
 141     }
 142 }
 143
 144 #[instrument(skip(tcx, f), level = "debug")]
 145 pub fn walk_abstract_const<'tcx, R, F>(
 146     tcx: TyCtxt<'tcx>,
 147     ct: AbstractConst<'tcx>,
 148     mut f: F,
 149 ) -> ControlFlow<R>
 150 where
 151     F: FnMut(AbstractConst<'tcx>) -> ControlFlow<R>,
 152 {
 153     #[instrument(skip(tcx, f), level = "debug")]
 154     fn recurse<'tcx, R>(
 155         tcx: TyCtxt<'tcx>,
 156         ct: AbstractConst<'tcx>,
 157         f: &mut dyn FnMut(AbstractConst<'tcx>) -> ControlFlow<R>,
 158     ) -> ControlFlow<R> {
 159         f(ct)?;
 160         let root = ct.root(tcx);
 161         debug!(?root);
 162         match root {
 163             Node::Leaf(_) => ControlFlow::CONTINUE,
 164             Node::Binop(_, l, r) => {
 165                 recurse(tcx, ct.subtree(l), f)?;
 166                 recurse(tcx, ct.subtree(r), f)
 167             }
 168             Node::UnaryOp(_, v) => recurse(tcx, ct.subtree(v), f),
 169             Node::FunctionCall(func, args) => {
 170                 recurse(tcx, ct.subtree(func), f)?;
 171                 args.iter().try_for_each(|&arg| recurse(tcx, ct.subtree(arg), f))
 172             }
 173             Node::Cast(_, operand, _) => recurse(tcx, ct.subtree(operand), f),
 174         }
 175     }
 176
 177     recurse(tcx, ct, &mut f)
 178 }
 179
 180 // We were unable to unify the abstract constant with
 181 // a constant found in the caller bounds, there are
 182 // now three possible cases here.
 183 #[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord)]
 184 pub enum FailureKind {
 185     /// The abstract const still references an inference
 186     /// variable, in this case we return `TooGeneric`.
 187     MentionsInfer,
 188     /// The abstract const references a generic parameter,
 189     /// this means that we emit an error here.
 190     MentionsParam,
 191     /// The substs are concrete enough that we can simply
 192     /// try and evaluate the given constant.
 193     Concrete,
 194 }