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, DelaySpanBugEmitted, 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             let reported =
 181                 infcx.tcx.sess.delay_span_bug(span, "constant in type had error reported as lint");
 182             Err(NotConstEvaluatable::Error(reported))
 183         }
 184         Err(ErrorHandled::Reported(e)) => Err(NotConstEvaluatable::Error(e)),
 185         Ok(_) => Ok(()),
 186     }
 187 }
 188
 189 fn satisfied_from_param_env<'tcx>(
 190     tcx: TyCtxt<'tcx>,
 191     ct: AbstractConst<'tcx>,
 192     param_env: ty::ParamEnv<'tcx>,
 193 ) -> Result<bool, NotConstEvaluatable> {
 194     for pred in param_env.caller_bounds() {
 195         match pred.kind().skip_binder() {
 196             ty::PredicateKind::ConstEvaluatable(uv) => {
 197                 if let Some(b_ct) = AbstractConst::new(tcx, uv)? {
 198                     // Try to unify with each subtree in the AbstractConst to allow for
 199                     // `N + 1` being const evaluatable even if theres only a `ConstEvaluatable`
 200                     // predicate for `(N + 1) * 2`
 201                     let result =
 202                         walk_abstract_const(tcx, b_ct, |b_ct| match try_unify(tcx, ct, b_ct) {
 203                             true => ControlFlow::BREAK,
 204                             false => ControlFlow::CONTINUE,
 205                         });
 206
 207                     if let ControlFlow::Break(()) = result {
 208                         debug!("is_const_evaluatable: abstract_const ~~> ok");
 209                         return Ok(true);
 210                     }
 211                 }
 212             }
 213             _ => {} // don't care
 214         }
 215     }
 216
 217     Ok(false)
 218 }
 219
 220 /// A tree representing an anonymous constant.
 221 ///
 222 /// This is only able to represent a subset of `MIR`,
 223 /// and should not leak any information about desugarings.
 224 #[derive(Debug, Clone, Copy)]
 225 pub struct AbstractConst<'tcx> {
 226     // FIXME: Consider adding something like `IndexSlice`
 227     // and use this here.
 228     inner: &'tcx [Node<'tcx>],
 229     substs: SubstsRef<'tcx>,
 230 }
 231
 232 impl<'tcx> AbstractConst<'tcx> {
 233     pub fn new(
 234         tcx: TyCtxt<'tcx>,
 235         uv: ty::Unevaluated<'tcx, ()>,
 236     ) -> Result<Option<AbstractConst<'tcx>>, ErrorGuaranteed> {
 237         let inner = tcx.thir_abstract_const_opt_const_arg(uv.def)?;
 238         debug!("AbstractConst::new({:?}) = {:?}", uv, inner);
 239         Ok(inner.map(|inner| AbstractConst { inner, substs: uv.substs }))
 240     }
 241
 242     pub fn from_const(
 243         tcx: TyCtxt<'tcx>,
 244         ct: ty::Const<'tcx>,
 245     ) -> Result<Option<AbstractConst<'tcx>>, ErrorGuaranteed> {
 246         match ct.val() {
 247             ty::ConstKind::Unevaluated(uv) => AbstractConst::new(tcx, uv.shrink()),
 248             ty::ConstKind::Error(DelaySpanBugEmitted { reported, .. }) => Err(reported),
 249             _ => Ok(None),
 250         }
 251     }
 252
 253     #[inline]
 254     pub fn subtree(self, node: NodeId) -> AbstractConst<'tcx> {
 255         AbstractConst { inner: &self.inner[..=node.index()], substs: self.substs }
 256     }
 257
 258     #[inline]
 259     pub fn root(self, tcx: TyCtxt<'tcx>) -> Node<'tcx> {
 260         let node = self.inner.last().copied().unwrap();
 261         match node {
 262             Node::Leaf(leaf) => Node::Leaf(leaf.subst(tcx, self.substs)),
 263             Node::Cast(kind, operand, ty) => Node::Cast(kind, operand, ty.subst(tcx, self.substs)),
 264             // Don't perform substitution on the following as they can't directly contain generic params
 265             Node::Binop(_, _, _) | Node::UnaryOp(_, _) | Node::FunctionCall(_, _) => node,
 266         }
 267     }
 268 }
 269
 270 struct AbstractConstBuilder<'a, 'tcx> {
 271     tcx: TyCtxt<'tcx>,
 272     body_id: thir::ExprId,
 273     body: &'a thir::Thir<'tcx>,
 274     /// The current WIP node tree.
 275     nodes: IndexVec<NodeId, Node<'tcx>>,
 276 }
 277
 278 impl<'a, 'tcx> AbstractConstBuilder<'a, 'tcx> {
 279     fn root_span(&self) -> Span {
 280         self.body.exprs[self.body_id].span
 281     }
 282
 283     fn error(&mut self, span: Span, msg: &str) -> Result<!, ErrorGuaranteed> {
 284         let reported = self
 285             .tcx
 286             .sess
 287             .struct_span_err(self.root_span(), "overly complex generic constant")
 288             .span_label(span, msg)
 289             .help("consider moving this anonymous constant into a `const` function")
 290             .emit();
 291
 292         Err(reported)
 293     }
 294     fn maybe_supported_error(&mut self, span: Span, msg: &str) -> Result<!, ErrorGuaranteed> {
 295         let reported = self
 296             .tcx
 297             .sess
 298             .struct_span_err(self.root_span(), "overly complex generic constant")
 299             .span_label(span, msg)
 300             .help("consider moving this anonymous constant into a `const` function")
 301             .note("this operation may be supported in the future")
 302             .emit();
 303
 304         Err(reported)
 305     }
 306
 307     fn new(
 308         tcx: TyCtxt<'tcx>,
 309         (body, body_id): (&'a thir::Thir<'tcx>, thir::ExprId),
 310     ) -> Result<Option<AbstractConstBuilder<'a, 'tcx>>, ErrorGuaranteed> {
 311         let builder = AbstractConstBuilder { tcx, body_id, body, nodes: IndexVec::new() };
 312
 313         struct IsThirPolymorphic<'a, 'tcx> {
 314             is_poly: bool,
 315             thir: &'a thir::Thir<'tcx>,
 316         }
 317
 318         use thir::visit;
 319         impl<'a, 'tcx: 'a> visit::Visitor<'a, 'tcx> for IsThirPolymorphic<'a, 'tcx> {
 320             fn thir(&self) -> &'a thir::Thir<'tcx> {
 321                 &self.thir
 322             }
 323
 324             fn visit_expr(&mut self, expr: &thir::Expr<'tcx>) {
 325                 self.is_poly |= expr.ty.has_param_types_or_consts();
 326                 if !self.is_poly {
 327                     visit::walk_expr(self, expr)
 328                 }
 329             }
 330
 331             fn visit_pat(&mut self, pat: &thir::Pat<'tcx>) {
 332                 self.is_poly |= pat.ty.has_param_types_or_consts();
 333                 if !self.is_poly {
 334                     visit::walk_pat(self, pat);
 335                 }
 336             }
 337
 338             fn visit_const(&mut self, ct: ty::Const<'tcx>) {
 339                 self.is_poly |= ct.has_param_types_or_consts();
 340             }
 341         }
 342
 343         let mut is_poly_vis = IsThirPolymorphic { is_poly: false, thir: body };
 344         visit::walk_expr(&mut is_poly_vis, &body[body_id]);
 345         debug!("AbstractConstBuilder: is_poly={}", is_poly_vis.is_poly);
 346         if !is_poly_vis.is_poly {
 347             return Ok(None);
 348         }
 349
 350         Ok(Some(builder))
 351     }
 352
 353     /// We do not allow all binary operations in abstract consts, so filter disallowed ones.
 354     fn check_binop(op: mir::BinOp) -> bool {
 355         use mir::BinOp::*;
 356         match op {
 357             Add | Sub | Mul | Div | Rem | BitXor | BitAnd | BitOr | Shl | Shr | Eq | Lt | Le
 358             | Ne | Ge | Gt => true,
 359             Offset => false,
 360         }
 361     }
 362
 363     /// While we currently allow all unary operations, we still want to explicitly guard against
 364     /// future changes here.
 365     fn check_unop(op: mir::UnOp) -> bool {
 366         use mir::UnOp::*;
 367         match op {
 368             Not | Neg => true,
 369         }
 370     }
 371
 372     /// Builds the abstract const by walking the thir and bailing out when
 373     /// encountering an unspported operation.
 374     fn build(mut self) -> Result<&'tcx [Node<'tcx>], ErrorGuaranteed> {
 375         debug!("Abstractconstbuilder::build: body={:?}", &*self.body);
 376         self.recurse_build(self.body_id)?;
 377
 378         for n in self.nodes.iter() {
 379             if let Node::Leaf(ty::Const(Interned(
 380                 ty::ConstS { val: ty::ConstKind::Unevaluated(ct), ty: _ },
 381                 _,
 382             ))) = n
 383             {
 384                 // `AbstractConst`s should not contain any promoteds as they require references which
 385                 // are not allowed.
 386                 assert_eq!(ct.promoted, None);
 387             }
 388         }
 389
 390         Ok(self.tcx.arena.alloc_from_iter(self.nodes.into_iter()))
 391     }
 392
 393     fn recurse_build(&mut self, node: thir::ExprId) -> Result<NodeId, ErrorGuaranteed> {
 394         use thir::ExprKind;
 395         let node = &self.body.exprs[node];
 396         debug!("recurse_build: node={:?}", node);
 397         Ok(match &node.kind {
 398             // I dont know if handling of these 3 is correct
 399             &ExprKind::Scope { value, .. } => self.recurse_build(value)?,
 400             &ExprKind::PlaceTypeAscription { source, .. }
 401             | &ExprKind::ValueTypeAscription { source, .. } => self.recurse_build(source)?,
 402
 403             // subtle: associated consts are literals this arm handles
 404             // `<T as Trait>::ASSOC` as well as `12`
 405             &ExprKind::Literal { literal, .. } => self.nodes.push(Node::Leaf(literal)),
 406
 407             ExprKind::Call { fun, args, .. } => {
 408                 let fun = self.recurse_build(*fun)?;
 409
 410                 let mut new_args = Vec::<NodeId>::with_capacity(args.len());
 411                 for &id in args.iter() {
 412                     new_args.push(self.recurse_build(id)?);
 413                 }
 414                 let new_args = self.tcx.arena.alloc_slice(&new_args);
 415                 self.nodes.push(Node::FunctionCall(fun, new_args))
 416             }
 417             &ExprKind::Binary { op, lhs, rhs } if Self::check_binop(op) => {
 418                 let lhs = self.recurse_build(lhs)?;
 419                 let rhs = self.recurse_build(rhs)?;
 420                 self.nodes.push(Node::Binop(op, lhs, rhs))
 421             }
 422             &ExprKind::Unary { op, arg } if Self::check_unop(op) => {
 423                 let arg = self.recurse_build(arg)?;
 424                 self.nodes.push(Node::UnaryOp(op, arg))
 425             }
 426             // This is necessary so that the following compiles:
 427             //
 428             // ```
 429             // fn foo<const N: usize>(a: [(); N + 1]) {
 430             //     bar::<{ N + 1 }>();
 431             // }
 432             // ```
 433             ExprKind::Block { body: thir::Block { stmts: box [], expr: Some(e), .. } } => {
 434                 self.recurse_build(*e)?
 435             }
 436             // `ExprKind::Use` happens when a `hir::ExprKind::Cast` is a
 437             // "coercion cast" i.e. using a coercion or is a no-op.
 438             // This is important so that `N as usize as usize` doesnt unify with `N as usize`. (untested)
 439             &ExprKind::Use { source } => {
 440                 let arg = self.recurse_build(source)?;
 441                 self.nodes.push(Node::Cast(abstract_const::CastKind::Use, arg, node.ty))
 442             }
 443             &ExprKind::Cast { source } => {
 444                 let arg = self.recurse_build(source)?;
 445                 self.nodes.push(Node::Cast(abstract_const::CastKind::As, arg, node.ty))
 446             }
 447             ExprKind::Borrow{ arg, ..} => {
 448                 let arg_node = &self.body.exprs[*arg];
 449
 450                 // Skip reborrows for now until we allow Deref/Borrow/AddressOf
 451                 // expressions.
 452                 // FIXME(generic_const_exprs): Verify/explain why this is sound
 453                 if let ExprKind::Deref {arg} = arg_node.kind {
 454                     self.recurse_build(arg)?
 455                 } else {
 456                     self.maybe_supported_error(
 457                         node.span,
 458                         "borrowing is not supported in generic constants",
 459                     )?
 460                 }
 461             }
 462             // FIXME(generic_const_exprs): We may want to support these.
 463             ExprKind::AddressOf { .. } | ExprKind::Deref {..}=> self.maybe_supported_error(
 464                 node.span,
 465                 "dereferencing or taking the address is not supported in generic constants",
 466             )?,
 467             ExprKind::Repeat { .. } | ExprKind::Array { .. } =>  self.maybe_supported_error(
 468                 node.span,
 469                 "array construction is not supported in generic constants",
 470             )?,
 471             ExprKind::Block { .. } => self.maybe_supported_error(
 472                 node.span,
 473                 "blocks are not supported in generic constant",
 474             )?,
 475             ExprKind::NeverToAny { .. } => self.maybe_supported_error(
 476                 node.span,
 477                 "converting nevers to any is not supported in generic constant",
 478             )?,
 479             ExprKind::Tuple { .. } => self.maybe_supported_error(
 480                 node.span,
 481                 "tuple construction is not supported in generic constants",
 482             )?,
 483             ExprKind::Index { .. } => self.maybe_supported_error(
 484                 node.span,
 485                 "indexing is not supported in generic constant",
 486             )?,
 487             ExprKind::Field { .. } => self.maybe_supported_error(
 488                 node.span,
 489                 "field access is not supported in generic constant",
 490             )?,
 491             ExprKind::ConstBlock { .. } => self.maybe_supported_error(
 492                 node.span,
 493                 "const blocks are not supported in generic constant",
 494             )?,
 495             ExprKind::Adt(_) => self.maybe_supported_error(
 496                 node.span,
 497                 "struct/enum construction is not supported in generic constants",
 498             )?,
 499             // dont know if this is correct
 500             ExprKind::Pointer { .. } =>
 501                 self.error(node.span, "pointer casts are not allowed in generic constants")?,
 502             ExprKind::Yield { .. } =>
 503                 self.error(node.span, "generator control flow is not allowed in generic constants")?,
 504             ExprKind::Continue { .. } | ExprKind::Break { .. } | ExprKind::Loop { .. } => self
 505                 .error(
 506                     node.span,
 507                     "loops and loop control flow are not supported in generic constants",
 508                 )?,
 509             ExprKind::Box { .. } =>
 510                 self.error(node.span, "allocations are not allowed in generic constants")?,
 511
 512             ExprKind::Unary { .. } => unreachable!(),
 513             // we handle valid unary/binary ops above
 514             ExprKind::Binary { .. } =>
 515                 self.error(node.span, "unsupported binary operation in generic constants")?,
 516             ExprKind::LogicalOp { .. } =>
 517                 self.error(node.span, "unsupported operation in generic constants, short-circuiting operations would imply control flow")?,
 518             ExprKind::Assign { .. } | ExprKind::AssignOp { .. } => {
 519                 self.error(node.span, "assignment is not supported in generic constants")?
 520             }
 521             ExprKind::Closure { .. } | ExprKind::Return { .. } => self.error(
 522                 node.span,
 523                 "closures and function keywords are not supported in generic constants",
 524             )?,
 525             // let expressions imply control flow
 526             ExprKind::Match { .. } | ExprKind::If { .. } | ExprKind::Let { .. } =>
 527                 self.error(node.span, "control flow is not supported in generic constants")?,
 528             ExprKind::InlineAsm { .. } => {
 529                 self.error(node.span, "assembly is not supported in generic constants")?
 530             }
 531
 532             // we dont permit let stmts so `VarRef` and `UpvarRef` cant happen
 533             ExprKind::VarRef { .. }
 534             | ExprKind::UpvarRef { .. }
 535             | ExprKind::StaticRef { .. }
 536             | ExprKind::ThreadLocalRef(_) => {
 537                 self.error(node.span, "unsupported operation in generic constant")?
 538             }
 539         })
 540     }
 541 }
 542
 543 /// Builds an abstract const, do not use this directly, but use `AbstractConst::new` instead.
 544 pub(super) fn thir_abstract_const<'tcx>(
 545     tcx: TyCtxt<'tcx>,
 546     def: ty::WithOptConstParam<LocalDefId>,
 547 ) -> Result<Option<&'tcx [thir::abstract_const::Node<'tcx>]>, ErrorGuaranteed> {
 548     if tcx.features().generic_const_exprs {
 549         match tcx.def_kind(def.did) {
 550             // FIXME(generic_const_exprs): We currently only do this for anonymous constants,
 551             // meaning that we do not look into associated constants. I(@lcnr) am not yet sure whether
 552             // we want to look into them or treat them as opaque projections.
 553             //
 554             // Right now we do neither of that and simply always fail to unify them.
 555             DefKind::AnonConst | DefKind::InlineConst => (),
 556             _ => return Ok(None),
 557         }
 558
 559         let body = tcx.thir_body(def)?;
 560
 561         AbstractConstBuilder::new(tcx, (&*body.0.borrow(), body.1))?
 562             .map(AbstractConstBuilder::build)
 563             .transpose()
 564     } else {
 565         Ok(None)
 566     }
 567 }
 568
 569 pub(super) fn try_unify_abstract_consts<'tcx>(
 570     tcx: TyCtxt<'tcx>,
 571     (a, b): (ty::Unevaluated<'tcx, ()>, ty::Unevaluated<'tcx, ()>),
 572 ) -> bool {
 573     (|| {
 574         if let Some(a) = AbstractConst::new(tcx, a)? {
 575             if let Some(b) = AbstractConst::new(tcx, b)? {
 576                 return Ok(try_unify(tcx, a, b));
 577             }
 578         }
 579
 580         Ok(false)
 581     })()
 582     .unwrap_or_else(|_: ErrorGuaranteed| true)
 583     // FIXME(generic_const_exprs): We should instead have this
 584     // method return the resulting `ty::Const` and return `ConstKind::Error`
 585     // on `ErrorGuaranteed`.
 586 }
 587
 588 pub fn walk_abstract_const<'tcx, R, F>(
 589     tcx: TyCtxt<'tcx>,
 590     ct: AbstractConst<'tcx>,
 591     mut f: F,
 592 ) -> ControlFlow<R>
 593 where
 594     F: FnMut(AbstractConst<'tcx>) -> ControlFlow<R>,
 595 {
 596     fn recurse<'tcx, R>(
 597         tcx: TyCtxt<'tcx>,
 598         ct: AbstractConst<'tcx>,
 599         f: &mut dyn FnMut(AbstractConst<'tcx>) -> ControlFlow<R>,
 600     ) -> ControlFlow<R> {
 601         f(ct)?;
 602         let root = ct.root(tcx);
 603         match root {
 604             Node::Leaf(_) => ControlFlow::CONTINUE,
 605             Node::Binop(_, l, r) => {
 606                 recurse(tcx, ct.subtree(l), f)?;
 607                 recurse(tcx, ct.subtree(r), f)
 608             }
 609             Node::UnaryOp(_, v) => recurse(tcx, ct.subtree(v), f),
 610             Node::FunctionCall(func, args) => {
 611                 recurse(tcx, ct.subtree(func), f)?;
 612                 args.iter().try_for_each(|&arg| recurse(tcx, ct.subtree(arg), f))
 613             }
 614             Node::Cast(_, operand, _) => recurse(tcx, ct.subtree(operand), f),
 615         }
 616     }
 617
 618     recurse(tcx, ct, &mut f)
 619 }
 620
 621 /// Tries to unify two abstract constants using structural equality.
 622 pub(super) fn try_unify<'tcx>(
 623     tcx: TyCtxt<'tcx>,
 624     mut a: AbstractConst<'tcx>,
 625     mut b: AbstractConst<'tcx>,
 626 ) -> bool {
 627     // We substitute generics repeatedly to allow AbstractConsts to unify where a
 628     // ConstKind::Unevalated could be turned into an AbstractConst that would unify e.g.
 629     // Param(N) should unify with Param(T), substs: [Unevaluated("T2", [Unevaluated("T3", [Param(N)])])]
 630     while let Node::Leaf(a_ct) = a.root(tcx) {
 631         match AbstractConst::from_const(tcx, a_ct) {
 632             Ok(Some(a_act)) => a = a_act,
 633             Ok(None) => break,
 634             Err(_) => return true,
 635         }
 636     }
 637     while let Node::Leaf(b_ct) = b.root(tcx) {
 638         match AbstractConst::from_const(tcx, b_ct) {
 639             Ok(Some(b_act)) => b = b_act,
 640             Ok(None) => break,
 641             Err(_) => return true,
 642         }
 643     }
 644
 645     match (a.root(tcx), b.root(tcx)) {
 646         (Node::Leaf(a_ct), Node::Leaf(b_ct)) => {
 647             if a_ct.ty() != b_ct.ty() {
 648                 return false;
 649             }
 650
 651             match (a_ct.val(), b_ct.val()) {
 652                 // We can just unify errors with everything to reduce the amount of
 653                 // emitted errors here.
 654                 (ty::ConstKind::Error(_), _) | (_, ty::ConstKind::Error(_)) => true,
 655                 (ty::ConstKind::Param(a_param), ty::ConstKind::Param(b_param)) => {
 656                     a_param == b_param
 657                 }
 658                 (ty::ConstKind::Value(a_val), ty::ConstKind::Value(b_val)) => a_val == b_val,
 659                 // If we have `fn a<const N: usize>() -> [u8; N + 1]` and `fn b<const M: usize>() -> [u8; 1 + M]`
 660                 // we do not want to use `assert_eq!(a(), b())` to infer that `N` and `M` have to be `1`. This
 661                 // means that we only allow inference variables if they are equal.
 662                 (ty::ConstKind::Infer(a_val), ty::ConstKind::Infer(b_val)) => a_val == b_val,
 663                 // We expand generic anonymous constants at the start of this function, so this
 664                 // branch should only be taking when dealing with associated constants, at
 665                 // which point directly comparing them seems like the desired behavior.
 666                 //
 667                 // FIXME(generic_const_exprs): This isn't actually the case.
 668                 // We also take this branch for concrete anonymous constants and
 669                 // expand generic anonymous constants with concrete substs.
 670                 (ty::ConstKind::Unevaluated(a_uv), ty::ConstKind::Unevaluated(b_uv)) => {
 671                     a_uv == b_uv
 672                 }
 673                 // FIXME(generic_const_exprs): We may want to either actually try
 674                 // to evaluate `a_ct` and `b_ct` if they are are fully concrete or something like
 675                 // this, for now we just return false here.
 676                 _ => false,
 677             }
 678         }
 679         (Node::Binop(a_op, al, ar), Node::Binop(b_op, bl, br)) if a_op == b_op => {
 680             try_unify(tcx, a.subtree(al), b.subtree(bl))
 681                 && try_unify(tcx, a.subtree(ar), b.subtree(br))
 682         }
 683         (Node::UnaryOp(a_op, av), Node::UnaryOp(b_op, bv)) if a_op == b_op => {
 684             try_unify(tcx, a.subtree(av), b.subtree(bv))
 685         }
 686         (Node::FunctionCall(a_f, a_args), Node::FunctionCall(b_f, b_args))
 687             if a_args.len() == b_args.len() =>
 688         {
 689             try_unify(tcx, a.subtree(a_f), b.subtree(b_f))
 690                 && iter::zip(a_args, b_args)
 691                     .all(|(&an, &bn)| try_unify(tcx, a.subtree(an), b.subtree(bn)))
 692         }
 693         (Node::Cast(a_kind, a_operand, a_ty), Node::Cast(b_kind, b_operand, b_ty))
 694             if (a_ty == b_ty) && (a_kind == b_kind) =>
 695         {
 696             try_unify(tcx, a.subtree(a_operand), b.subtree(b_operand))
 697         }
 698         // use this over `_ => false` to make adding variants to `Node` less error prone
 699         (Node::Cast(..), _)
 700         | (Node::FunctionCall(..), _)
 701         | (Node::UnaryOp(..), _)
 702         | (Node::Binop(..), _)
 703         | (Node::Leaf(..), _) => false,
 704     }
 705 }