compiler/rustc_trait_selection/src/traits/const_evaluatable.rs

   1 //! Checking that constant values used in types can be successfully evaluated.
   2 //!
   3 //! For concrete constants, this is fairly simple as we can just try and evaluate it.
   4 //!
   5 //! When dealing with polymorphic constants, for example `std::mem::size_of::<T>() - 1`,
   6 //! this is not as easy.
   7 //!
   8 //! In this case we try to build an abstract representation of this constant using
   9 //! `thir_abstract_const` which can then be checked for structural equality with other
  10 //! generic constants mentioned in the `caller_bounds` of the current environment.
  11 use rustc_data_structures::intern::Interned;
  12 use rustc_errors::ErrorGuaranteed;
  13 use rustc_hir::def::DefKind;
  14 use rustc_index::vec::IndexVec;
  15 use rustc_infer::infer::InferCtxt;
  16 use rustc_middle::mir;
  17 use rustc_middle::mir::interpret::ErrorHandled;
  18 use rustc_middle::thir;
  19 use rustc_middle::thir::abstract_const::{self, Node, NodeId, NotConstEvaluatable};
  20 use rustc_middle::ty::subst::{Subst, SubstsRef};
  21 use rustc_middle::ty::{self, TyCtxt, TypeFoldable};
  22 use rustc_session::lint;
  23 use rustc_span::def_id::LocalDefId;
  24 use rustc_span::Span;
  25
  26 use std::cmp;
  27 use std::iter;
  28 use std::ops::ControlFlow;
  29
  30 /// Check if a given constant can be evaluated.
  31 pub fn is_const_evaluatable<'cx, 'tcx>(
  32     infcx: &InferCtxt<'cx, 'tcx>,
  33     uv: ty::Unevaluated<'tcx, ()>,
  34     param_env: ty::ParamEnv<'tcx>,
  35     span: Span,
  36 ) -> Result<(), NotConstEvaluatable> {
  37     debug!("is_const_evaluatable({:?})", uv);
  38     let tcx = infcx.tcx;
  39
  40     if tcx.features().generic_const_exprs {
  41         match AbstractConst::new(tcx, uv)? {
  42             // We are looking at a generic abstract constant.
  43             Some(ct) => {
  44                 if satisfied_from_param_env(tcx, ct, param_env)? {
  45                     return Ok(());
  46                 }
  47
  48                 // We were unable to unify the abstract constant with
  49                 // a constant found in the caller bounds, there are
  50                 // now three possible cases here.
  51                 #[derive(Debug, Copy, Clone, PartialEq, Eq, PartialOrd, Ord)]
  52                 enum FailureKind {
  53                     /// The abstract const still references an inference
  54                     /// variable, in this case we return `TooGeneric`.
  55                     MentionsInfer,
  56                     /// The abstract const references a generic parameter,
  57                     /// this means that we emit an error here.
  58                     MentionsParam,
  59                     /// The substs are concrete enough that we can simply
  60                     /// try and evaluate the given constant.
  61                     Concrete,
  62                 }
  63                 let mut failure_kind = FailureKind::Concrete;
  64                 walk_abstract_const::<!, _>(tcx, ct, |node| match node.root(tcx) {
  65                     Node::Leaf(leaf) => {
  66                         if leaf.has_infer_types_or_consts() {
  67                             failure_kind = FailureKind::MentionsInfer;
  68                         } else if leaf.has_param_types_or_consts() {
  69                             failure_kind = cmp::min(failure_kind, FailureKind::MentionsParam);
  70                         }
  71
  72                         ControlFlow::CONTINUE
  73                     }
  74                     Node::Cast(_, _, ty) => {
  75                         if ty.has_infer_types_or_consts() {
  76                             failure_kind = FailureKind::MentionsInfer;
  77                         } else if ty.has_param_types_or_consts() {
  78                             failure_kind = cmp::min(failure_kind, FailureKind::MentionsParam);
  79                         }
  80
  81                         ControlFlow::CONTINUE
  82                     }
  83                     Node::Binop(_, _, _) | Node::UnaryOp(_, _) | Node::FunctionCall(_, _) => {
  84                         ControlFlow::CONTINUE
  85                     }
  86                 });
  87
  88                 match failure_kind {
  89                     FailureKind::MentionsInfer => {
  90                         return Err(NotConstEvaluatable::MentionsInfer);
  91                     }
  92                     FailureKind::MentionsParam => {
  93                         return Err(NotConstEvaluatable::MentionsParam);
  94                     }
  95                     FailureKind::Concrete => {
  96                         // Dealt with below by the same code which handles this
  97                         // without the feature gate.
  98                     }
  99                 }
 100             }
 101             None => {
 102                 // If we are dealing with a concrete constant, we can
 103                 // reuse the old code path and try to evaluate
 104                 // the constant.
 105             }
 106         }
 107     }
 108
 109     let future_compat_lint = || {
 110         if let Some(local_def_id) = uv.def.did.as_local() {
 111             infcx.tcx.struct_span_lint_hir(
 112                 lint::builtin::CONST_EVALUATABLE_UNCHECKED,
 113                 infcx.tcx.hir().local_def_id_to_hir_id(local_def_id),
 114                 span,
 115                 |err| {
 116                     err.build("cannot use constants which depend on generic parameters in types")
 117                         .emit();
 118                 },
 119             );
 120         }
 121     };
 122
 123     // FIXME: We should only try to evaluate a given constant here if it is fully concrete
 124     // as we don't want to allow things like `[u8; std::mem::size_of::<*mut T>()]`.
 125     //
 126     // We previously did not check this, so we only emit a future compat warning if
 127     // const evaluation succeeds and the given constant is still polymorphic for now
 128     // and hopefully soon change this to an error.
 129     //
 130     // See #74595 for more details about this.
 131     let concrete = infcx.const_eval_resolve(param_env, uv.expand(), Some(span));
 132
 133     if concrete.is_ok() && uv.substs.has_param_types_or_consts() {
 134         match infcx.tcx.def_kind(uv.def.did) {
 135             DefKind::AnonConst | DefKind::InlineConst => {
 136                 let mir_body = infcx.tcx.mir_for_ctfe_opt_const_arg(uv.def);
 137
 138                 if mir_body.is_polymorphic {
 139                     future_compat_lint();
 140                 }
 141             }
 142             _ => future_compat_lint(),
 143         }
 144     }
 145
 146     // If we're evaluating a foreign constant, under a nightly compiler without generic
 147     // const exprs, AND it would've passed if that expression had been evaluated with
 148     // generic const exprs, then suggest using generic const exprs.
 149     if concrete.is_err()
 150         && tcx.sess.is_nightly_build()
 151         && !uv.def.did.is_local()
 152         && !tcx.features().generic_const_exprs
 153         && let Ok(Some(ct)) = AbstractConst::new(tcx, uv)
 154         && satisfied_from_param_env(tcx, ct, param_env) == Ok(true)
 155     {
 156         tcx.sess
 157             .struct_span_fatal(
 158                 // Slightly better span than just using `span` alone
 159                 if span == rustc_span::DUMMY_SP { tcx.def_span(uv.def.did) } else { span },
 160                 "failed to evaluate generic const expression",
 161             )
 162             .note("the crate this constant originates from uses `#![feature(generic_const_exprs)]`")
 163             .span_suggestion_verbose(
 164                 rustc_span::DUMMY_SP,
 165                 "consider enabling this feature",
 166                 "#![feature(generic_const_exprs)]\n".to_string(),
 167                 rustc_errors::Applicability::MaybeIncorrect,
 168             )
 169             .emit();
 170         rustc_errors::FatalError.raise();
 171     }
 172
 173     debug!(?concrete, "is_const_evaluatable");
 174     match concrete {
 175         Err(ErrorHandled::TooGeneric) => Err(match uv.has_infer_types_or_consts() {
 176             true => NotConstEvaluatable::MentionsInfer,
 177             false => NotConstEvaluatable::MentionsParam,
 178         }),
 179         Err(ErrorHandled::Linted) => {
 180             infcx.tcx.sess.delay_span_bug(span, "constant in type had error reported as lint");
 181             Err(NotConstEvaluatable::Error(ErrorGuaranteed))
 182         }
 183         Err(ErrorHandled::Reported(e)) => Err(NotConstEvaluatable::Error(e)),
 184         Ok(_) => Ok(()),
 185     }
 186 }
 187
 188 fn satisfied_from_param_env<'tcx>(
 189     tcx: TyCtxt<'tcx>,
 190     ct: AbstractConst<'tcx>,
 191     param_env: ty::ParamEnv<'tcx>,
 192 ) -> Result<bool, NotConstEvaluatable> {
 193     for pred in param_env.caller_bounds() {
 194         match pred.kind().skip_binder() {
 195             ty::PredicateKind::ConstEvaluatable(uv) => {
 196                 if let Some(b_ct) = AbstractConst::new(tcx, uv)? {
 197                     // Try to unify with each subtree in the AbstractConst to allow for
 198                     // `N + 1` being const evaluatable even if theres only a `ConstEvaluatable`
 199                     // predicate for `(N + 1) * 2`
 200                     let result =
 201                         walk_abstract_const(tcx, b_ct, |b_ct| match try_unify(tcx, ct, b_ct) {
 202                             true => ControlFlow::BREAK,
 203                             false => ControlFlow::CONTINUE,
 204                         });
 205
 206                     if let ControlFlow::Break(()) = result {
 207                         debug!("is_const_evaluatable: abstract_const ~~> ok");
 208                         return Ok(true);
 209                     }
 210                 }
 211             }
 212             _ => {} // don't care
 213         }
 214     }
 215
 216     Ok(false)
 217 }
 218
 219 /// A tree representing an anonymous constant.
 220 ///
 221 /// This is only able to represent a subset of `MIR`,
 222 /// and should not leak any information about desugarings.
 223 #[derive(Debug, Clone, Copy)]
 224 pub struct AbstractConst<'tcx> {
 225     // FIXME: Consider adding something like `IndexSlice`
 226     // and use this here.
 227     inner: &'tcx [Node<'tcx>],
 228     substs: SubstsRef<'tcx>,
 229 }
 230
 231 impl<'tcx> AbstractConst<'tcx> {
 232     pub fn new(
 233         tcx: TyCtxt<'tcx>,
 234         uv: ty::Unevaluated<'tcx, ()>,
 235     ) -> Result<Option<AbstractConst<'tcx>>, ErrorGuaranteed> {
 236         let inner = tcx.thir_abstract_const_opt_const_arg(uv.def)?;
 237         debug!("AbstractConst::new({:?}) = {:?}", uv, inner);
 238         Ok(inner.map(|inner| AbstractConst { inner, substs: uv.substs }))
 239     }
 240
 241     pub fn from_const(
 242         tcx: TyCtxt<'tcx>,
 243         ct: ty::Const<'tcx>,
 244     ) -> Result<Option<AbstractConst<'tcx>>, ErrorGuaranteed> {
 245         match ct.val() {
 246             ty::ConstKind::Unevaluated(uv) => AbstractConst::new(tcx, uv.shrink()),
 247             ty::ConstKind::Error(_) => Err(ErrorGuaranteed),
 248             _ => Ok(None),
 249         }
 250     }
 251
 252     #[inline]
 253     pub fn subtree(self, node: NodeId) -> AbstractConst<'tcx> {
 254         AbstractConst { inner: &self.inner[..=node.index()], substs: self.substs }
 255     }
 256
 257     #[inline]
 258     pub fn root(self, tcx: TyCtxt<'tcx>) -> Node<'tcx> {
 259         let node = self.inner.last().copied().unwrap();
 260         match node {
 261             Node::Leaf(leaf) => Node::Leaf(leaf.subst(tcx, self.substs)),
 262             Node::Cast(kind, operand, ty) => Node::Cast(kind, operand, ty.subst(tcx, self.substs)),
 263             // Don't perform substitution on the following as they can't directly contain generic params
 264             Node::Binop(_, _, _) | Node::UnaryOp(_, _) | Node::FunctionCall(_, _) => node,
 265         }
 266     }
 267 }
 268
 269 struct AbstractConstBuilder<'a, 'tcx> {
 270     tcx: TyCtxt<'tcx>,
 271     body_id: thir::ExprId,
 272     body: &'a thir::Thir<'tcx>,
 273     /// The current WIP node tree.
 274     nodes: IndexVec<NodeId, Node<'tcx>>,
 275 }
 276
 277 impl<'a, 'tcx> AbstractConstBuilder<'a, 'tcx> {
 278     fn root_span(&self) -> Span {
 279         self.body.exprs[self.body_id].span
 280     }
 281
 282     fn error(&mut self, span: Span, msg: &str) -> Result<!, ErrorGuaranteed> {
 283         self.tcx
 284             .sess
 285             .struct_span_err(self.root_span(), "overly complex generic constant")
 286             .span_label(span, msg)
 287             .help("consider moving this anonymous constant into a `const` function")
 288             .emit();
 289
 290         Err(ErrorGuaranteed)
 291     }
 292     fn maybe_supported_error(&mut self, span: Span, msg: &str) -> Result<!, ErrorGuaranteed> {
 293         self.tcx
 294             .sess
 295             .struct_span_err(self.root_span(), "overly complex generic constant")
 296             .span_label(span, msg)
 297             .help("consider moving this anonymous constant into a `const` function")
 298             .note("this operation may be supported in the future")
 299             .emit();
 300
 301         Err(ErrorGuaranteed)
 302     }
 303
 304     fn new(
 305         tcx: TyCtxt<'tcx>,
 306         (body, body_id): (&'a thir::Thir<'tcx>, thir::ExprId),
 307     ) -> Result<Option<AbstractConstBuilder<'a, 'tcx>>, ErrorGuaranteed> {
 308         let builder = AbstractConstBuilder { tcx, body_id, body, nodes: IndexVec::new() };
 309
 310         struct IsThirPolymorphic<'a, 'tcx> {
 311             is_poly: bool,
 312             thir: &'a thir::Thir<'tcx>,
 313         }
 314
 315         use thir::visit;
 316         impl<'a, 'tcx: 'a> visit::Visitor<'a, 'tcx> for IsThirPolymorphic<'a, 'tcx> {
 317             fn thir(&self) -> &'a thir::Thir<'tcx> {
 318                 &self.thir
 319             }
 320
 321             fn visit_expr(&mut self, expr: &thir::Expr<'tcx>) {
 322                 self.is_poly |= expr.ty.has_param_types_or_consts();
 323                 if !self.is_poly {
 324                     visit::walk_expr(self, expr)
 325                 }
 326             }
 327
 328             fn visit_pat(&mut self, pat: &thir::Pat<'tcx>) {
 329                 self.is_poly |= pat.ty.has_param_types_or_consts();
 330                 if !self.is_poly {
 331                     visit::walk_pat(self, pat);
 332                 }
 333             }
 334
 335             fn visit_const(&mut self, ct: ty::Const<'tcx>) {
 336                 self.is_poly |= ct.has_param_types_or_consts();
 337             }
 338         }
 339
 340         let mut is_poly_vis = IsThirPolymorphic { is_poly: false, thir: body };
 341         visit::walk_expr(&mut is_poly_vis, &body[body_id]);
 342         debug!("AbstractConstBuilder: is_poly={}", is_poly_vis.is_poly);
 343         if !is_poly_vis.is_poly {
 344             return Ok(None);
 345         }
 346
 347         Ok(Some(builder))
 348     }
 349
 350     /// We do not allow all binary operations in abstract consts, so filter disallowed ones.
 351     fn check_binop(op: mir::BinOp) -> bool {
 352         use mir::BinOp::*;
 353         match op {
 354             Add | Sub | Mul | Div | Rem | BitXor | BitAnd | BitOr | Shl | Shr | Eq | Lt | Le
 355             | Ne | Ge | Gt => true,
 356             Offset => false,
 357         }
 358     }
 359
 360     /// While we currently allow all unary operations, we still want to explicitly guard against
 361     /// future changes here.
 362     fn check_unop(op: mir::UnOp) -> bool {
 363         use mir::UnOp::*;
 364         match op {
 365             Not | Neg => true,
 366         }
 367     }
 368
 369     /// Builds the abstract const by walking the thir and bailing out when
 370     /// encountering an unspported operation.
 371     fn build(mut self) -> Result<&'tcx [Node<'tcx>], ErrorGuaranteed> {
 372         debug!("Abstractconstbuilder::build: body={:?}", &*self.body);
 373         self.recurse_build(self.body_id)?;
 374
 375         for n in self.nodes.iter() {
 376             if let Node::Leaf(ty::Const(Interned(
 377                 ty::ConstS { val: ty::ConstKind::Unevaluated(ct), ty: _ },
 378                 _,
 379             ))) = n
 380             {
 381                 // `AbstractConst`s should not contain any promoteds as they require references which
 382                 // are not allowed.
 383                 assert_eq!(ct.promoted, None);
 384             }
 385         }
 386
 387         Ok(self.tcx.arena.alloc_from_iter(self.nodes.into_iter()))
 388     }
 389
 390     fn recurse_build(&mut self, node: thir::ExprId) -> Result<NodeId, ErrorGuaranteed> {
 391         use thir::ExprKind;
 392         let node = &self.body.exprs[node];
 393         debug!("recurse_build: node={:?}", node);
 394         Ok(match &node.kind {
 395             // I dont know if handling of these 3 is correct
 396             &ExprKind::Scope { value, .. } => self.recurse_build(value)?,
 397             &ExprKind::PlaceTypeAscription { source, .. }
 398             | &ExprKind::ValueTypeAscription { source, .. } => self.recurse_build(source)?,
 399
 400             // subtle: associated consts are literals this arm handles
 401             // `<T as Trait>::ASSOC` as well as `12`
 402             &ExprKind::Literal { literal, .. } => self.nodes.push(Node::Leaf(literal)),
 403
 404             ExprKind::Call { fun, args, .. } => {
 405                 let fun = self.recurse_build(*fun)?;
 406
 407                 let mut new_args = Vec::<NodeId>::with_capacity(args.len());
 408                 for &id in args.iter() {
 409                     new_args.push(self.recurse_build(id)?);
 410                 }
 411                 let new_args = self.tcx.arena.alloc_slice(&new_args);
 412                 self.nodes.push(Node::FunctionCall(fun, new_args))
 413             }
 414             &ExprKind::Binary { op, lhs, rhs } if Self::check_binop(op) => {
 415                 let lhs = self.recurse_build(lhs)?;
 416                 let rhs = self.recurse_build(rhs)?;
 417                 self.nodes.push(Node::Binop(op, lhs, rhs))
 418             }
 419             &ExprKind::Unary { op, arg } if Self::check_unop(op) => {
 420                 let arg = self.recurse_build(arg)?;
 421                 self.nodes.push(Node::UnaryOp(op, arg))
 422             }
 423             // This is necessary so that the following compiles:
 424             //
 425             // ```
 426             // fn foo<const N: usize>(a: [(); N + 1]) {
 427             //     bar::<{ N + 1 }>();
 428             // }
 429             // ```
 430             ExprKind::Block { body: thir::Block { stmts: box [], expr: Some(e), .. } } => {
 431                 self.recurse_build(*e)?
 432             }
 433             // `ExprKind::Use` happens when a `hir::ExprKind::Cast` is a
 434             // "coercion cast" i.e. using a coercion or is a no-op.
 435             // This is important so that `N as usize as usize` doesnt unify with `N as usize`. (untested)
 436             &ExprKind::Use { source } => {
 437                 let arg = self.recurse_build(source)?;
 438                 self.nodes.push(Node::Cast(abstract_const::CastKind::Use, arg, node.ty))
 439             }
 440             &ExprKind::Cast { source } => {
 441                 let arg = self.recurse_build(source)?;
 442                 self.nodes.push(Node::Cast(abstract_const::CastKind::As, arg, node.ty))
 443             }
 444             ExprKind::Borrow{ arg, ..} => {
 445                 let arg_node = &self.body.exprs[*arg];
 446
 447                 // Skip reborrows for now until we allow Deref/Borrow/AddressOf
 448                 // expressions.
 449                 // FIXME(generic_const_exprs): Verify/explain why this is sound
 450                 if let ExprKind::Deref {arg} = arg_node.kind {
 451                     self.recurse_build(arg)?
 452                 } else {
 453                     self.maybe_supported_error(
 454                         node.span,
 455                         "borrowing is not supported in generic constants",
 456                     )?
 457                 }
 458             }
 459             // FIXME(generic_const_exprs): We may want to support these.
 460             ExprKind::AddressOf { .. } | ExprKind::Deref {..}=> self.maybe_supported_error(
 461                 node.span,
 462                 "dereferencing or taking the address is not supported in generic constants",
 463             )?,
 464             ExprKind::Repeat { .. } | ExprKind::Array { .. } =>  self.maybe_supported_error(
 465                 node.span,
 466                 "array construction is not supported in generic constants",
 467             )?,
 468             ExprKind::Block { .. } => self.maybe_supported_error(
 469                 node.span,
 470                 "blocks are not supported in generic constant",
 471             )?,
 472             ExprKind::NeverToAny { .. } => self.maybe_supported_error(
 473                 node.span,
 474                 "converting nevers to any is not supported in generic constant",
 475             )?,
 476             ExprKind::Tuple { .. } => self.maybe_supported_error(
 477                 node.span,
 478                 "tuple construction is not supported in generic constants",
 479             )?,
 480             ExprKind::Index { .. } => self.maybe_supported_error(
 481                 node.span,
 482                 "indexing is not supported in generic constant",
 483             )?,
 484             ExprKind::Field { .. } => self.maybe_supported_error(
 485                 node.span,
 486                 "field access is not supported in generic constant",
 487             )?,
 488             ExprKind::ConstBlock { .. } => self.maybe_supported_error(
 489                 node.span,
 490                 "const blocks are not supported in generic constant",
 491             )?,
 492             ExprKind::Adt(_) => self.maybe_supported_error(
 493                 node.span,
 494                 "struct/enum construction is not supported in generic constants",
 495             )?,
 496             // dont know if this is correct
 497             ExprKind::Pointer { .. } =>
 498                 self.error(node.span, "pointer casts are not allowed in generic constants")?,
 499             ExprKind::Yield { .. } =>
 500                 self.error(node.span, "generator control flow is not allowed in generic constants")?,
 501             ExprKind::Continue { .. } | ExprKind::Break { .. } | ExprKind::Loop { .. } => self
 502                 .error(
 503                     node.span,
 504                     "loops and loop control flow are not supported in generic constants",
 505                 )?,
 506             ExprKind::Box { .. } =>
 507                 self.error(node.span, "allocations are not allowed in generic constants")?,
 508
 509             ExprKind::Unary { .. } => unreachable!(),
 510             // we handle valid unary/binary ops above
 511             ExprKind::Binary { .. } =>
 512                 self.error(node.span, "unsupported binary operation in generic constants")?,
 513             ExprKind::LogicalOp { .. } =>
 514                 self.error(node.span, "unsupported operation in generic constants, short-circuiting operations would imply control flow")?,
 515             ExprKind::Assign { .. } | ExprKind::AssignOp { .. } => {
 516                 self.error(node.span, "assignment is not supported in generic constants")?
 517             }
 518             ExprKind::Closure { .. } | ExprKind::Return { .. } => self.error(
 519                 node.span,
 520                 "closures and function keywords are not supported in generic constants",
 521             )?,
 522             // let expressions imply control flow
 523             ExprKind::Match { .. } | ExprKind::If { .. } | ExprKind::Let { .. } =>
 524                 self.error(node.span, "control flow is not supported in generic constants")?,
 525             ExprKind::InlineAsm { .. } => {
 526                 self.error(node.span, "assembly is not supported in generic constants")?
 527             }
 528
 529             // we dont permit let stmts so `VarRef` and `UpvarRef` cant happen
 530             ExprKind::VarRef { .. }
 531             | ExprKind::UpvarRef { .. }
 532             | ExprKind::StaticRef { .. }
 533             | ExprKind::ThreadLocalRef(_) => {
 534                 self.error(node.span, "unsupported operation in generic constant")?
 535             }
 536         })
 537     }
 538 }
 539
 540 /// Builds an abstract const, do not use this directly, but use `AbstractConst::new` instead.
 541 pub(super) fn thir_abstract_const<'tcx>(
 542     tcx: TyCtxt<'tcx>,
 543     def: ty::WithOptConstParam<LocalDefId>,
 544 ) -> Result<Option<&'tcx [thir::abstract_const::Node<'tcx>]>, ErrorGuaranteed> {
 545     if tcx.features().generic_const_exprs {
 546         match tcx.def_kind(def.did) {
 547             // FIXME(generic_const_exprs): We currently only do this for anonymous constants,
 548             // meaning that we do not look into associated constants. I(@lcnr) am not yet sure whether
 549             // we want to look into them or treat them as opaque projections.
 550             //
 551             // Right now we do neither of that and simply always fail to unify them.
 552             DefKind::AnonConst | DefKind::InlineConst => (),
 553             _ => return Ok(None),
 554         }
 555
 556         let body = tcx.thir_body(def);
 557         if body.0.borrow().exprs.is_empty() {
 558             // type error in constant, there is no thir
 559             return Err(ErrorGuaranteed);
 560         }
 561
 562         AbstractConstBuilder::new(tcx, (&*body.0.borrow(), body.1))?
 563             .map(AbstractConstBuilder::build)
 564             .transpose()
 565     } else {
 566         Ok(None)
 567     }
 568 }
 569
 570 pub(super) fn try_unify_abstract_consts<'tcx>(
 571     tcx: TyCtxt<'tcx>,
 572     (a, b): (ty::Unevaluated<'tcx, ()>, ty::Unevaluated<'tcx, ()>),
 573 ) -> bool {
 574     (|| {
 575         if let Some(a) = AbstractConst::new(tcx, a)? {
 576             if let Some(b) = AbstractConst::new(tcx, b)? {
 577                 return Ok(try_unify(tcx, a, b));
 578             }
 579         }
 580
 581         Ok(false)
 582     })()
 583     .unwrap_or_else(|ErrorGuaranteed| true)
 584     // FIXME(generic_const_exprs): We should instead have this
 585     // method return the resulting `ty::Const` and return `ConstKind::Error`
 586     // on `ErrorGuaranteed`.
 587 }
 588
 589 pub fn walk_abstract_const<'tcx, R, F>(
 590     tcx: TyCtxt<'tcx>,
 591     ct: AbstractConst<'tcx>,
 592     mut f: F,
 593 ) -> ControlFlow<R>
 594 where
 595     F: FnMut(AbstractConst<'tcx>) -> ControlFlow<R>,
 596 {
 597     fn recurse<'tcx, R>(
 598         tcx: TyCtxt<'tcx>,
 599         ct: AbstractConst<'tcx>,
 600         f: &mut dyn FnMut(AbstractConst<'tcx>) -> ControlFlow<R>,
 601     ) -> ControlFlow<R> {
 602         f(ct)?;
 603         let root = ct.root(tcx);
 604         match root {
 605             Node::Leaf(_) => ControlFlow::CONTINUE,
 606             Node::Binop(_, l, r) => {
 607                 recurse(tcx, ct.subtree(l), f)?;
 608                 recurse(tcx, ct.subtree(r), f)
 609             }
 610             Node::UnaryOp(_, v) => recurse(tcx, ct.subtree(v), f),
 611             Node::FunctionCall(func, args) => {
 612                 recurse(tcx, ct.subtree(func), f)?;
 613                 args.iter().try_for_each(|&arg| recurse(tcx, ct.subtree(arg), f))
 614             }
 615             Node::Cast(_, operand, _) => recurse(tcx, ct.subtree(operand), f),
 616         }
 617     }
 618
 619     recurse(tcx, ct, &mut f)
 620 }
 621
 622 /// Tries to unify two abstract constants using structural equality.
 623 pub(super) fn try_unify<'tcx>(
 624     tcx: TyCtxt<'tcx>,
 625     mut a: AbstractConst<'tcx>,
 626     mut b: AbstractConst<'tcx>,
 627 ) -> bool {
 628     // We substitute generics repeatedly to allow AbstractConsts to unify where a
 629     // ConstKind::Unevalated could be turned into an AbstractConst that would unify e.g.
 630     // Param(N) should unify with Param(T), substs: [Unevaluated("T2", [Unevaluated("T3", [Param(N)])])]
 631     while let Node::Leaf(a_ct) = a.root(tcx) {
 632         match AbstractConst::from_const(tcx, a_ct) {
 633             Ok(Some(a_act)) => a = a_act,
 634             Ok(None) => break,
 635             Err(_) => return true,
 636         }
 637     }
 638     while let Node::Leaf(b_ct) = b.root(tcx) {
 639         match AbstractConst::from_const(tcx, b_ct) {
 640             Ok(Some(b_act)) => b = b_act,
 641             Ok(None) => break,
 642             Err(_) => return true,
 643         }
 644     }
 645
 646     match (a.root(tcx), b.root(tcx)) {
 647         (Node::Leaf(a_ct), Node::Leaf(b_ct)) => {
 648             if a_ct.ty() != b_ct.ty() {
 649                 return false;
 650             }
 651
 652             match (a_ct.val(), b_ct.val()) {
 653                 // We can just unify errors with everything to reduce the amount of
 654                 // emitted errors here.
 655                 (ty::ConstKind::Error(_), _) | (_, ty::ConstKind::Error(_)) => true,
 656                 (ty::ConstKind::Param(a_param), ty::ConstKind::Param(b_param)) => {
 657                     a_param == b_param
 658                 }
 659                 (ty::ConstKind::Value(a_val), ty::ConstKind::Value(b_val)) => a_val == b_val,
 660                 // If we have `fn a<const N: usize>() -> [u8; N + 1]` and `fn b<const M: usize>() -> [u8; 1 + M]`
 661                 // we do not want to use `assert_eq!(a(), b())` to infer that `N` and `M` have to be `1`. This
 662                 // means that we only allow inference variables if they are equal.
 663                 (ty::ConstKind::Infer(a_val), ty::ConstKind::Infer(b_val)) => a_val == b_val,
 664                 // We expand generic anonymous constants at the start of this function, so this
 665                 // branch should only be taking when dealing with associated constants, at
 666                 // which point directly comparing them seems like the desired behavior.
 667                 //
 668                 // FIXME(generic_const_exprs): This isn't actually the case.
 669                 // We also take this branch for concrete anonymous constants and
 670                 // expand generic anonymous constants with concrete substs.
 671                 (ty::ConstKind::Unevaluated(a_uv), ty::ConstKind::Unevaluated(b_uv)) => {
 672                     a_uv == b_uv
 673                 }
 674                 // FIXME(generic_const_exprs): We may want to either actually try
 675                 // to evaluate `a_ct` and `b_ct` if they are are fully concrete or something like
 676                 // this, for now we just return false here.
 677                 _ => false,
 678             }
 679         }
 680         (Node::Binop(a_op, al, ar), Node::Binop(b_op, bl, br)) if a_op == b_op => {
 681             try_unify(tcx, a.subtree(al), b.subtree(bl))
 682                 && try_unify(tcx, a.subtree(ar), b.subtree(br))
 683         }
 684         (Node::UnaryOp(a_op, av), Node::UnaryOp(b_op, bv)) if a_op == b_op => {
 685             try_unify(tcx, a.subtree(av), b.subtree(bv))
 686         }
 687         (Node::FunctionCall(a_f, a_args), Node::FunctionCall(b_f, b_args))
 688             if a_args.len() == b_args.len() =>
 689         {
 690             try_unify(tcx, a.subtree(a_f), b.subtree(b_f))
 691                 && iter::zip(a_args, b_args)
 692                     .all(|(&an, &bn)| try_unify(tcx, a.subtree(an), b.subtree(bn)))
 693         }
 694         (Node::Cast(a_kind, a_operand, a_ty), Node::Cast(b_kind, b_operand, b_ty))
 695             if (a_ty == b_ty) && (a_kind == b_kind) =>
 696         {
 697             try_unify(tcx, a.subtree(a_operand), b.subtree(b_operand))
 698         }
 699         // use this over `_ => false` to make adding variants to `Node` less error prone
 700         (Node::Cast(..), _)
 701         | (Node::FunctionCall(..), _)
 702         | (Node::UnaryOp(..), _)
 703         | (Node::Binop(..), _)
 704         | (Node::Leaf(..), _) => false,
 705     }
 706 }