compiler/rustc_middle/src/mir/mod.rs

   1 //! MIR datatypes and passes. See the [rustc dev guide] for more info.
   2 //!
   3 //! [rustc dev guide]: https://rustc-dev-guide.rust-lang.org/mir/index.html
   4
   5 use crate::mir::interpret::{
   6     AllocRange, ConstAllocation, ConstValue, GlobalAlloc, LitToConstInput, Scalar,
   7 };
   8 use crate::mir::visit::MirVisitable;
   9 use crate::ty::codec::{TyDecoder, TyEncoder};
  10 use crate::ty::fold::{FallibleTypeFolder, TypeFoldable, TypeSuperFoldable};
  11 use crate::ty::print::{FmtPrinter, Printer};
  12 use crate::ty::subst::{GenericArg, InternalSubsts, Subst, SubstsRef};
  13 use crate::ty::visit::{TypeSuperVisitable, TypeVisitable, TypeVisitor};
  14 use crate::ty::{self, List, Ty, TyCtxt};
  15 use crate::ty::{AdtDef, InstanceDef, ScalarInt, UserTypeAnnotationIndex};
  16
  17 use rustc_data_structures::captures::Captures;
  18 use rustc_errors::ErrorGuaranteed;
  19 use rustc_hir::def::{CtorKind, Namespace};
  20 use rustc_hir::def_id::{DefId, LocalDefId, CRATE_DEF_ID};
  21 use rustc_hir::{self, GeneratorKind, ImplicitSelfKind};
  22 use rustc_hir::{self as hir, HirId};
  23 use rustc_session::Session;
  24 use rustc_target::abi::{Size, VariantIdx};
  25
  26 use polonius_engine::Atom;
  27 pub use rustc_ast::Mutability;
  28 use rustc_data_structures::fx::FxHashSet;
  29 use rustc_data_structures::graph::dominators::Dominators;
  30 use rustc_index::bit_set::BitMatrix;
  31 use rustc_index::vec::{Idx, IndexVec};
  32 use rustc_serialize::{Decodable, Encodable};
  33 use rustc_span::symbol::Symbol;
  34 use rustc_span::{Span, DUMMY_SP};
  35
  36 use either::Either;
  37
  38 use std::borrow::Cow;
  39 use std::convert::TryInto;
  40 use std::fmt::{self, Debug, Display, Formatter, Write};
  41 use std::ops::{ControlFlow, Index, IndexMut};
  42 use std::{iter, mem};
  43
  44 pub use self::query::*;
  45 pub use basic_blocks::BasicBlocks;
  46
  47 mod basic_blocks;
  48 pub mod coverage;
  49 mod generic_graph;
  50 pub mod generic_graphviz;
  51 mod graph_cyclic_cache;
  52 pub mod graphviz;
  53 pub mod interpret;
  54 pub mod mono;
  55 pub mod patch;
  56 mod predecessors;
  57 pub mod pretty;
  58 mod query;
  59 pub mod spanview;
  60 mod syntax;
  61 pub use syntax::*;
  62 mod switch_sources;
  63 pub mod tcx;
  64 pub mod terminator;
  65 pub use terminator::*;
  66
  67 pub mod traversal;
  68 mod type_foldable;
  69 mod type_visitable;
  70 pub mod visit;
  71
  72 pub use self::generic_graph::graphviz_safe_def_name;
  73 pub use self::graphviz::write_mir_graphviz;
  74 pub use self::pretty::{
  75     create_dump_file, display_allocation, dump_enabled, dump_mir, write_mir_pretty, PassWhere,
  76 };
  77
  78 /// Types for locals
  79 pub type LocalDecls<'tcx> = IndexVec<Local, LocalDecl<'tcx>>;
  80
  81 pub trait HasLocalDecls<'tcx> {
  82     fn local_decls(&self) -> &LocalDecls<'tcx>;
  83 }
  84
  85 impl<'tcx> HasLocalDecls<'tcx> for LocalDecls<'tcx> {
  86     #[inline]
  87     fn local_decls(&self) -> &LocalDecls<'tcx> {
  88         self
  89     }
  90 }
  91
  92 impl<'tcx> HasLocalDecls<'tcx> for Body<'tcx> {
  93     #[inline]
  94     fn local_decls(&self) -> &LocalDecls<'tcx> {
  95         &self.local_decls
  96     }
  97 }
  98
  99 /// A streamlined trait that you can implement to create a pass; the
 100 /// pass will be named after the type, and it will consist of a main
 101 /// loop that goes over each available MIR and applies `run_pass`.
 102 pub trait MirPass<'tcx> {
 103     fn name(&self) -> Cow<'_, str> {
 104         let name = std::any::type_name::<Self>();
 105         if let Some(tail) = name.rfind(':') {
 106             Cow::from(&name[tail + 1..])
 107         } else {
 108             Cow::from(name)
 109         }
 110     }
 111
 112     /// Returns `true` if this pass is enabled with the current combination of compiler flags.
 113     fn is_enabled(&self, _sess: &Session) -> bool {
 114         true
 115     }
 116
 117     fn run_pass(&self, tcx: TyCtxt<'tcx>, body: &mut Body<'tcx>);
 118
 119     /// If this pass causes the MIR to enter a new phase, return that phase.
 120     fn phase_change(&self) -> Option<MirPhase> {
 121         None
 122     }
 123
 124     fn is_mir_dump_enabled(&self) -> bool {
 125         true
 126     }
 127 }
 128
 129 impl MirPhase {
 130     /// Gets the index of the current MirPhase within the set of all `MirPhase`s.
 131     ///
 132     /// FIXME(JakobDegen): Return a `(usize, usize)` instead.
 133     pub fn phase_index(&self) -> usize {
 134         const BUILT_PHASE_COUNT: usize = 1;
 135         const ANALYSIS_PHASE_COUNT: usize = 2;
 136         match self {
 137             MirPhase::Built => 1,
 138             MirPhase::Analysis(analysis_phase) => {
 139                 1 + BUILT_PHASE_COUNT + (*analysis_phase as usize)
 140             }
 141             MirPhase::Runtime(runtime_phase) => {
 142                 1 + BUILT_PHASE_COUNT + ANALYSIS_PHASE_COUNT + (*runtime_phase as usize)
 143             }
 144         }
 145     }
 146 }
 147
 148 /// Where a specific `mir::Body` comes from.
 149 #[derive(Copy, Clone, Debug, PartialEq, Eq)]
 150 #[derive(HashStable, TyEncodable, TyDecodable, TypeFoldable, TypeVisitable)]
 151 pub struct MirSource<'tcx> {
 152     pub instance: InstanceDef<'tcx>,
 153
 154     /// If `Some`, this is a promoted rvalue within the parent function.
 155     pub promoted: Option<Promoted>,
 156 }
 157
 158 impl<'tcx> MirSource<'tcx> {
 159     pub fn item(def_id: DefId) -> Self {
 160         MirSource {
 161             instance: InstanceDef::Item(ty::WithOptConstParam::unknown(def_id)),
 162             promoted: None,
 163         }
 164     }
 165
 166     pub fn from_instance(instance: InstanceDef<'tcx>) -> Self {
 167         MirSource { instance, promoted: None }
 168     }
 169
 170     pub fn with_opt_param(self) -> ty::WithOptConstParam<DefId> {
 171         self.instance.with_opt_param()
 172     }
 173
 174     #[inline]
 175     pub fn def_id(&self) -> DefId {
 176         self.instance.def_id()
 177     }
 178 }
 179
 180 #[derive(Clone, TyEncodable, TyDecodable, Debug, HashStable, TypeFoldable, TypeVisitable)]
 181 pub struct GeneratorInfo<'tcx> {
 182     /// The yield type of the function, if it is a generator.
 183     pub yield_ty: Option<Ty<'tcx>>,
 184
 185     /// Generator drop glue.
 186     pub generator_drop: Option<Body<'tcx>>,
 187
 188     /// The layout of a generator. Produced by the state transformation.
 189     pub generator_layout: Option<GeneratorLayout<'tcx>>,
 190
 191     /// If this is a generator then record the type of source expression that caused this generator
 192     /// to be created.
 193     pub generator_kind: GeneratorKind,
 194 }
 195
 196 /// The lowered representation of a single function.
 197 #[derive(Clone, TyEncodable, TyDecodable, Debug, HashStable, TypeFoldable, TypeVisitable)]
 198 pub struct Body<'tcx> {
 199     /// A list of basic blocks. References to basic block use a newtyped index type [`BasicBlock`]
 200     /// that indexes into this vector.
 201     pub basic_blocks: BasicBlocks<'tcx>,
 202
 203     /// Records how far through the "desugaring and optimization" process this particular
 204     /// MIR has traversed. This is particularly useful when inlining, since in that context
 205     /// we instantiate the promoted constants and add them to our promoted vector -- but those
 206     /// promoted items have already been optimized, whereas ours have not. This field allows
 207     /// us to see the difference and forego optimization on the inlined promoted items.
 208     pub phase: MirPhase,
 209
 210     pub source: MirSource<'tcx>,
 211
 212     /// A list of source scopes; these are referenced by statements
 213     /// and used for debuginfo. Indexed by a `SourceScope`.
 214     pub source_scopes: IndexVec<SourceScope, SourceScopeData<'tcx>>,
 215
 216     pub generator: Option<Box<GeneratorInfo<'tcx>>>,
 217
 218     /// Declarations of locals.
 219     ///
 220     /// The first local is the return value pointer, followed by `arg_count`
 221     /// locals for the function arguments, followed by any user-declared
 222     /// variables and temporaries.
 223     pub local_decls: LocalDecls<'tcx>,
 224
 225     /// User type annotations.
 226     pub user_type_annotations: ty::CanonicalUserTypeAnnotations<'tcx>,
 227
 228     /// The number of arguments this function takes.
 229     ///
 230     /// Starting at local 1, `arg_count` locals will be provided by the caller
 231     /// and can be assumed to be initialized.
 232     ///
 233     /// If this MIR was built for a constant, this will be 0.
 234     pub arg_count: usize,
 235
 236     /// Mark an argument local (which must be a tuple) as getting passed as
 237     /// its individual components at the LLVM level.
 238     ///
 239     /// This is used for the "rust-call" ABI.
 240     pub spread_arg: Option<Local>,
 241
 242     /// Debug information pertaining to user variables, including captures.
 243     pub var_debug_info: Vec<VarDebugInfo<'tcx>>,
 244
 245     /// A span representing this MIR, for error reporting.
 246     pub span: Span,
 247
 248     /// Constants that are required to evaluate successfully for this MIR to be well-formed.
 249     /// We hold in this field all the constants we are not able to evaluate yet.
 250     pub required_consts: Vec<Constant<'tcx>>,
 251
 252     /// Does this body use generic parameters. This is used for the `ConstEvaluatable` check.
 253     ///
 254     /// Note that this does not actually mean that this body is not computable right now.
 255     /// The repeat count in the following example is polymorphic, but can still be evaluated
 256     /// without knowing anything about the type parameter `T`.
 257     ///
 258     /// ```rust
 259     /// fn test<T>() {
 260     ///     let _ = [0; std::mem::size_of::<*mut T>()];
 261     /// }
 262     /// ```
 263     ///
 264     /// **WARNING**: Do not change this flags after the MIR was originally created, even if an optimization
 265     /// removed the last mention of all generic params. We do not want to rely on optimizations and
 266     /// potentially allow things like `[u8; std::mem::size_of::<T>() * 0]` due to this.
 267     pub is_polymorphic: bool,
 268
 269     pub tainted_by_errors: Option<ErrorGuaranteed>,
 270 }
 271
 272 impl<'tcx> Body<'tcx> {
 273     pub fn new(
 274         source: MirSource<'tcx>,
 275         basic_blocks: IndexVec<BasicBlock, BasicBlockData<'tcx>>,
 276         source_scopes: IndexVec<SourceScope, SourceScopeData<'tcx>>,
 277         local_decls: LocalDecls<'tcx>,
 278         user_type_annotations: ty::CanonicalUserTypeAnnotations<'tcx>,
 279         arg_count: usize,
 280         var_debug_info: Vec<VarDebugInfo<'tcx>>,
 281         span: Span,
 282         generator_kind: Option<GeneratorKind>,
 283         tainted_by_errors: Option<ErrorGuaranteed>,
 284     ) -> Self {
 285         // We need `arg_count` locals, and one for the return place.
 286         assert!(
 287             local_decls.len() > arg_count,
 288             "expected at least {} locals, got {}",
 289             arg_count + 1,
 290             local_decls.len()
 291         );
 292
 293         let mut body = Body {
 294             phase: MirPhase::Built,
 295             source,
 296             basic_blocks: BasicBlocks::new(basic_blocks),
 297             source_scopes,
 298             generator: generator_kind.map(|generator_kind| {
 299                 Box::new(GeneratorInfo {
 300                     yield_ty: None,
 301                     generator_drop: None,
 302                     generator_layout: None,
 303                     generator_kind,
 304                 })
 305             }),
 306             local_decls,
 307             user_type_annotations,
 308             arg_count,
 309             spread_arg: None,
 310             var_debug_info,
 311             span,
 312             required_consts: Vec::new(),
 313             is_polymorphic: false,
 314             tainted_by_errors,
 315         };
 316         body.is_polymorphic = body.has_param_types_or_consts();
 317         body
 318     }
 319
 320     /// Returns a partially initialized MIR body containing only a list of basic blocks.
 321     ///
 322     /// The returned MIR contains no `LocalDecl`s (even for the return place) or source scopes. It
 323     /// is only useful for testing but cannot be `#[cfg(test)]` because it is used in a different
 324     /// crate.
 325     pub fn new_cfg_only(basic_blocks: IndexVec<BasicBlock, BasicBlockData<'tcx>>) -> Self {
 326         let mut body = Body {
 327             phase: MirPhase::Built,
 328             source: MirSource::item(CRATE_DEF_ID.to_def_id()),
 329             basic_blocks: BasicBlocks::new(basic_blocks),
 330             source_scopes: IndexVec::new(),
 331             generator: None,
 332             local_decls: IndexVec::new(),
 333             user_type_annotations: IndexVec::new(),
 334             arg_count: 0,
 335             spread_arg: None,
 336             span: DUMMY_SP,
 337             required_consts: Vec::new(),
 338             var_debug_info: Vec::new(),
 339             is_polymorphic: false,
 340             tainted_by_errors: None,
 341         };
 342         body.is_polymorphic = body.has_param_types_or_consts();
 343         body
 344     }
 345
 346     #[inline]
 347     pub fn basic_blocks_mut(&mut self) -> &mut IndexVec<BasicBlock, BasicBlockData<'tcx>> {
 348         self.basic_blocks.as_mut()
 349     }
 350
 351     #[inline]
 352     pub fn local_kind(&self, local: Local) -> LocalKind {
 353         let index = local.as_usize();
 354         if index == 0 {
 355             debug_assert!(
 356                 self.local_decls[local].mutability == Mutability::Mut,
 357                 "return place should be mutable"
 358             );
 359
 360             LocalKind::ReturnPointer
 361         } else if index < self.arg_count + 1 {
 362             LocalKind::Arg
 363         } else if self.local_decls[local].is_user_variable() {
 364             LocalKind::Var
 365         } else {
 366             LocalKind::Temp
 367         }
 368     }
 369
 370     /// Returns an iterator over all user-declared mutable locals.
 371     #[inline]
 372     pub fn mut_vars_iter<'a>(&'a self) -> impl Iterator<Item = Local> + Captures<'tcx> + 'a {
 373         (self.arg_count + 1..self.local_decls.len()).filter_map(move |index| {
 374             let local = Local::new(index);
 375             let decl = &self.local_decls[local];
 376             if decl.is_user_variable() && decl.mutability == Mutability::Mut {
 377                 Some(local)
 378             } else {
 379                 None
 380             }
 381         })
 382     }
 383
 384     /// Returns an iterator over all user-declared mutable arguments and locals.
 385     #[inline]
 386     pub fn mut_vars_and_args_iter<'a>(
 387         &'a self,
 388     ) -> impl Iterator<Item = Local> + Captures<'tcx> + 'a {
 389         (1..self.local_decls.len()).filter_map(move |index| {
 390             let local = Local::new(index);
 391             let decl = &self.local_decls[local];
 392             if (decl.is_user_variable() || index < self.arg_count + 1)
 393                 && decl.mutability == Mutability::Mut
 394             {
 395                 Some(local)
 396             } else {
 397                 None
 398             }
 399         })
 400     }
 401
 402     /// Returns an iterator over all function arguments.
 403     #[inline]
 404     pub fn args_iter(&self) -> impl Iterator<Item = Local> + ExactSizeIterator {
 405         (1..self.arg_count + 1).map(Local::new)
 406     }
 407
 408     /// Returns an iterator over all user-defined variables and compiler-generated temporaries (all
 409     /// locals that are neither arguments nor the return place).
 410     #[inline]
 411     pub fn vars_and_temps_iter(
 412         &self,
 413     ) -> impl DoubleEndedIterator<Item = Local> + ExactSizeIterator {
 414         (self.arg_count + 1..self.local_decls.len()).map(Local::new)
 415     }
 416
 417     #[inline]
 418     pub fn drain_vars_and_temps<'a>(&'a mut self) -> impl Iterator<Item = LocalDecl<'tcx>> + 'a {
 419         self.local_decls.drain(self.arg_count + 1..)
 420     }
 421
 422     /// Returns the source info associated with `location`.
 423     pub fn source_info(&self, location: Location) -> &SourceInfo {
 424         let block = &self[location.block];
 425         let stmts = &block.statements;
 426         let idx = location.statement_index;
 427         if idx < stmts.len() {
 428             &stmts[idx].source_info
 429         } else {
 430             assert_eq!(idx, stmts.len());
 431             &block.terminator().source_info
 432         }
 433     }
 434
 435     /// Returns the return type; it always return first element from `local_decls` array.
 436     #[inline]
 437     pub fn return_ty(&self) -> Ty<'tcx> {
 438         self.local_decls[RETURN_PLACE].ty
 439     }
 440
 441     /// Returns the return type; it always return first element from `local_decls` array.
 442     #[inline]
 443     pub fn bound_return_ty(&self) -> ty::EarlyBinder<Ty<'tcx>> {
 444         ty::EarlyBinder(self.local_decls[RETURN_PLACE].ty)
 445     }
 446
 447     /// Gets the location of the terminator for the given block.
 448     #[inline]
 449     pub fn terminator_loc(&self, bb: BasicBlock) -> Location {
 450         Location { block: bb, statement_index: self[bb].statements.len() }
 451     }
 452
 453     pub fn stmt_at(&self, location: Location) -> Either<&Statement<'tcx>, &Terminator<'tcx>> {
 454         let Location { block, statement_index } = location;
 455         let block_data = &self.basic_blocks[block];
 456         block_data
 457             .statements
 458             .get(statement_index)
 459             .map(Either::Left)
 460             .unwrap_or_else(|| Either::Right(block_data.terminator()))
 461     }
 462
 463     #[inline]
 464     pub fn yield_ty(&self) -> Option<Ty<'tcx>> {
 465         self.generator.as_ref().and_then(|generator| generator.yield_ty)
 466     }
 467
 468     #[inline]
 469     pub fn generator_layout(&self) -> Option<&GeneratorLayout<'tcx>> {
 470         self.generator.as_ref().and_then(|generator| generator.generator_layout.as_ref())
 471     }
 472
 473     #[inline]
 474     pub fn generator_drop(&self) -> Option<&Body<'tcx>> {
 475         self.generator.as_ref().and_then(|generator| generator.generator_drop.as_ref())
 476     }
 477
 478     #[inline]
 479     pub fn generator_kind(&self) -> Option<GeneratorKind> {
 480         self.generator.as_ref().map(|generator| generator.generator_kind)
 481     }
 482 }
 483
 484 #[derive(Copy, Clone, PartialEq, Eq, Debug, TyEncodable, TyDecodable, HashStable)]
 485 pub enum Safety {
 486     Safe,
 487     /// Unsafe because of compiler-generated unsafe code, like `await` desugaring
 488     BuiltinUnsafe,
 489     /// Unsafe because of an unsafe fn
 490     FnUnsafe,
 491     /// Unsafe because of an `unsafe` block
 492     ExplicitUnsafe(hir::HirId),
 493 }
 494
 495 impl<'tcx> Index<BasicBlock> for Body<'tcx> {
 496     type Output = BasicBlockData<'tcx>;
 497
 498     #[inline]
 499     fn index(&self, index: BasicBlock) -> &BasicBlockData<'tcx> {
 500         &self.basic_blocks[index]
 501     }
 502 }
 503
 504 impl<'tcx> IndexMut<BasicBlock> for Body<'tcx> {
 505     #[inline]
 506     fn index_mut(&mut self, index: BasicBlock) -> &mut BasicBlockData<'tcx> {
 507         &mut self.basic_blocks.as_mut()[index]
 508     }
 509 }
 510
 511 #[derive(Copy, Clone, Debug, HashStable, TypeFoldable, TypeVisitable)]
 512 pub enum ClearCrossCrate<T> {
 513     Clear,
 514     Set(T),
 515 }
 516
 517 impl<T> ClearCrossCrate<T> {
 518     pub fn as_ref(&self) -> ClearCrossCrate<&T> {
 519         match self {
 520             ClearCrossCrate::Clear => ClearCrossCrate::Clear,
 521             ClearCrossCrate::Set(v) => ClearCrossCrate::Set(v),
 522         }
 523     }
 524
 525     pub fn assert_crate_local(self) -> T {
 526         match self {
 527             ClearCrossCrate::Clear => bug!("unwrapping cross-crate data"),
 528             ClearCrossCrate::Set(v) => v,
 529         }
 530     }
 531 }
 532
 533 const TAG_CLEAR_CROSS_CRATE_CLEAR: u8 = 0;
 534 const TAG_CLEAR_CROSS_CRATE_SET: u8 = 1;
 535
 536 impl<E: TyEncoder, T: Encodable<E>> Encodable<E> for ClearCrossCrate<T> {
 537     #[inline]
 538     fn encode(&self, e: &mut E) {
 539         if E::CLEAR_CROSS_CRATE {
 540             return;
 541         }
 542
 543         match *self {
 544             ClearCrossCrate::Clear => TAG_CLEAR_CROSS_CRATE_CLEAR.encode(e),
 545             ClearCrossCrate::Set(ref val) => {
 546                 TAG_CLEAR_CROSS_CRATE_SET.encode(e);
 547                 val.encode(e);
 548             }
 549         }
 550     }
 551 }
 552 impl<D: TyDecoder, T: Decodable<D>> Decodable<D> for ClearCrossCrate<T> {
 553     #[inline]
 554     fn decode(d: &mut D) -> ClearCrossCrate<T> {
 555         if D::CLEAR_CROSS_CRATE {
 556             return ClearCrossCrate::Clear;
 557         }
 558
 559         let discr = u8::decode(d);
 560
 561         match discr {
 562             TAG_CLEAR_CROSS_CRATE_CLEAR => ClearCrossCrate::Clear,
 563             TAG_CLEAR_CROSS_CRATE_SET => {
 564                 let val = T::decode(d);
 565                 ClearCrossCrate::Set(val)
 566             }
 567             tag => panic!("Invalid tag for ClearCrossCrate: {:?}", tag),
 568         }
 569     }
 570 }
 571
 572 /// Grouped information about the source code origin of a MIR entity.
 573 /// Intended to be inspected by diagnostics and debuginfo.
 574 /// Most passes can work with it as a whole, within a single function.
 575 // The unofficial Cranelift backend, at least as of #65828, needs `SourceInfo` to implement `Eq` and
 576 // `Hash`. Please ping @bjorn3 if removing them.
 577 #[derive(Copy, Clone, Debug, Eq, PartialEq, TyEncodable, TyDecodable, Hash, HashStable)]
 578 pub struct SourceInfo {
 579     /// The source span for the AST pertaining to this MIR entity.
 580     pub span: Span,
 581
 582     /// The source scope, keeping track of which bindings can be
 583     /// seen by debuginfo, active lint levels, `unsafe {...}`, etc.
 584     pub scope: SourceScope,
 585 }
 586
 587 impl SourceInfo {
 588     #[inline]
 589     pub fn outermost(span: Span) -> Self {
 590         SourceInfo { span, scope: OUTERMOST_SOURCE_SCOPE }
 591     }
 592 }
 593
 594 ///////////////////////////////////////////////////////////////////////////
 595 // Variables and temps
 596
 597 rustc_index::newtype_index! {
 598     pub struct Local {
 599         derive [HashStable]
 600         DEBUG_FORMAT = "_{}",
 601         const RETURN_PLACE = 0,
 602     }
 603 }
 604
 605 impl Atom for Local {
 606     fn index(self) -> usize {
 607         Idx::index(self)
 608     }
 609 }
 610
 611 /// Classifies locals into categories. See `Body::local_kind`.
 612 #[derive(Clone, Copy, PartialEq, Eq, Debug, HashStable)]
 613 pub enum LocalKind {
 614     /// User-declared variable binding.
 615     Var,
 616     /// Compiler-introduced temporary.
 617     Temp,
 618     /// Function argument.
 619     Arg,
 620     /// Location of function's return value.
 621     ReturnPointer,
 622 }
 623
 624 #[derive(Clone, Debug, TyEncodable, TyDecodable, HashStable)]
 625 pub struct VarBindingForm<'tcx> {
 626     /// Is variable bound via `x`, `mut x`, `ref x`, or `ref mut x`?
 627     pub binding_mode: ty::BindingMode,
 628     /// If an explicit type was provided for this variable binding,
 629     /// this holds the source Span of that type.
 630     ///
 631     /// NOTE: if you want to change this to a `HirId`, be wary that
 632     /// doing so breaks incremental compilation (as of this writing),
 633     /// while a `Span` does not cause our tests to fail.
 634     pub opt_ty_info: Option<Span>,
 635     /// Place of the RHS of the =, or the subject of the `match` where this
 636     /// variable is initialized. None in the case of `let PATTERN;`.
 637     /// Some((None, ..)) in the case of and `let [mut] x = ...` because
 638     /// (a) the right-hand side isn't evaluated as a place expression.
 639     /// (b) it gives a way to separate this case from the remaining cases
 640     ///     for diagnostics.
 641     pub opt_match_place: Option<(Option<Place<'tcx>>, Span)>,
 642     /// The span of the pattern in which this variable was bound.
 643     pub pat_span: Span,
 644 }
 645
 646 #[derive(Clone, Debug, TyEncodable, TyDecodable)]
 647 pub enum BindingForm<'tcx> {
 648     /// This is a binding for a non-`self` binding, or a `self` that has an explicit type.
 649     Var(VarBindingForm<'tcx>),
 650     /// Binding for a `self`/`&self`/`&mut self` binding where the type is implicit.
 651     ImplicitSelf(ImplicitSelfKind),
 652     /// Reference used in a guard expression to ensure immutability.
 653     RefForGuard,
 654 }
 655
 656 TrivialTypeTraversalAndLiftImpls! { BindingForm<'tcx>, }
 657
 658 mod binding_form_impl {
 659     use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
 660     use rustc_query_system::ich::StableHashingContext;
 661
 662     impl<'a, 'tcx> HashStable<StableHashingContext<'a>> for super::BindingForm<'tcx> {
 663         fn hash_stable(&self, hcx: &mut StableHashingContext<'a>, hasher: &mut StableHasher) {
 664             use super::BindingForm::*;
 665             std::mem::discriminant(self).hash_stable(hcx, hasher);
 666
 667             match self {
 668                 Var(binding) => binding.hash_stable(hcx, hasher),
 669                 ImplicitSelf(kind) => kind.hash_stable(hcx, hasher),
 670                 RefForGuard => (),
 671             }
 672         }
 673     }
 674 }
 675
 676 /// `BlockTailInfo` is attached to the `LocalDecl` for temporaries
 677 /// created during evaluation of expressions in a block tail
 678 /// expression; that is, a block like `{ STMT_1; STMT_2; EXPR }`.
 679 ///
 680 /// It is used to improve diagnostics when such temporaries are
 681 /// involved in borrow_check errors, e.g., explanations of where the
 682 /// temporaries come from, when their destructors are run, and/or how
 683 /// one might revise the code to satisfy the borrow checker's rules.
 684 #[derive(Clone, Debug, TyEncodable, TyDecodable, HashStable)]
 685 pub struct BlockTailInfo {
 686     /// If `true`, then the value resulting from evaluating this tail
 687     /// expression is ignored by the block's expression context.
 688     ///
 689     /// Examples include `{ ...; tail };` and `let _ = { ...; tail };`
 690     /// but not e.g., `let _x = { ...; tail };`
 691     pub tail_result_is_ignored: bool,
 692
 693     /// `Span` of the tail expression.
 694     pub span: Span,
 695 }
 696
 697 /// A MIR local.
 698 ///
 699 /// This can be a binding declared by the user, a temporary inserted by the compiler, a function
 700 /// argument, or the return place.
 701 #[derive(Clone, Debug, TyEncodable, TyDecodable, HashStable, TypeFoldable, TypeVisitable)]
 702 pub struct LocalDecl<'tcx> {
 703     /// Whether this is a mutable binding (i.e., `let x` or `let mut x`).
 704     ///
 705     /// Temporaries and the return place are always mutable.
 706     pub mutability: Mutability,
 707
 708     // FIXME(matthewjasper) Don't store in this in `Body`
 709     pub local_info: Option<Box<LocalInfo<'tcx>>>,
 710
 711     /// `true` if this is an internal local.
 712     ///
 713     /// These locals are not based on types in the source code and are only used
 714     /// for a few desugarings at the moment.
 715     ///
 716     /// The generator transformation will sanity check the locals which are live
 717     /// across a suspension point against the type components of the generator
 718     /// which type checking knows are live across a suspension point. We need to
 719     /// flag drop flags to avoid triggering this check as they are introduced
 720     /// outside of type inference.
 721     ///
 722     /// This should be sound because the drop flags are fully algebraic, and
 723     /// therefore don't affect the auto-trait or outlives properties of the
 724     /// generator.
 725     pub internal: bool,
 726
 727     /// If this local is a temporary and `is_block_tail` is `Some`,
 728     /// then it is a temporary created for evaluation of some
 729     /// subexpression of some block's tail expression (with no
 730     /// intervening statement context).
 731     // FIXME(matthewjasper) Don't store in this in `Body`
 732     pub is_block_tail: Option<BlockTailInfo>,
 733
 734     /// The type of this local.
 735     pub ty: Ty<'tcx>,
 736
 737     /// If the user manually ascribed a type to this variable,
 738     /// e.g., via `let x: T`, then we carry that type here. The MIR
 739     /// borrow checker needs this information since it can affect
 740     /// region inference.
 741     // FIXME(matthewjasper) Don't store in this in `Body`
 742     pub user_ty: Option<Box<UserTypeProjections>>,
 743
 744     /// The *syntactic* (i.e., not visibility) source scope the local is defined
 745     /// in. If the local was defined in a let-statement, this
 746     /// is *within* the let-statement, rather than outside
 747     /// of it.
 748     ///
 749     /// This is needed because the visibility source scope of locals within
 750     /// a let-statement is weird.
 751     ///
 752     /// The reason is that we want the local to be *within* the let-statement
 753     /// for lint purposes, but we want the local to be *after* the let-statement
 754     /// for names-in-scope purposes.
 755     ///
 756     /// That's it, if we have a let-statement like the one in this
 757     /// function:
 758     ///
 759     /// ```
 760     /// fn foo(x: &str) {
 761     ///     #[allow(unused_mut)]
 762     ///     let mut x: u32 = { // <- one unused mut
 763     ///         let mut y: u32 = x.parse().unwrap();
 764     ///         y + 2
 765     ///     };
 766     ///     drop(x);
 767     /// }
 768     /// ```
 769     ///
 770     /// Then, from a lint point of view, the declaration of `x: u32`
 771     /// (and `y: u32`) are within the `#[allow(unused_mut)]` scope - the
 772     /// lint scopes are the same as the AST/HIR nesting.
 773     ///
 774     /// However, from a name lookup point of view, the scopes look more like
 775     /// as if the let-statements were `match` expressions:
 776     ///
 777     /// ```
 778     /// fn foo(x: &str) {
 779     ///     match {
 780     ///         match x.parse::<u32>().unwrap() {
 781     ///             y => y + 2
 782     ///         }
 783     ///     } {
 784     ///         x => drop(x)
 785     ///     };
 786     /// }
 787     /// ```
 788     ///
 789     /// We care about the name-lookup scopes for debuginfo - if the
 790     /// debuginfo instruction pointer is at the call to `x.parse()`, we
 791     /// want `x` to refer to `x: &str`, but if it is at the call to
 792     /// `drop(x)`, we want it to refer to `x: u32`.
 793     ///
 794     /// To allow both uses to work, we need to have more than a single scope
 795     /// for a local. We have the `source_info.scope` represent the "syntactic"
 796     /// lint scope (with a variable being under its let block) while the
 797     /// `var_debug_info.source_info.scope` represents the "local variable"
 798     /// scope (where the "rest" of a block is under all prior let-statements).
 799     ///
 800     /// The end result looks like this:
 801     ///
 802     /// ```text
 803     /// ROOT SCOPE
 804     ///  │{ argument x: &str }
 805     ///  │
 806     ///  │ │{ #[allow(unused_mut)] } // This is actually split into 2 scopes
 807     ///  │ │                         // in practice because I'm lazy.
 808     ///  │ │
 809     ///  │ │← x.source_info.scope
 810     ///  │ │← `x.parse().unwrap()`
 811     ///  │ │
 812     ///  │ │ │← y.source_info.scope
 813     ///  │ │
 814     ///  │ │ │{ let y: u32 }
 815     ///  │ │ │
 816     ///  │ │ │← y.var_debug_info.source_info.scope
 817     ///  │ │ │← `y + 2`
 818     ///  │
 819     ///  │ │{ let x: u32 }
 820     ///  │ │← x.var_debug_info.source_info.scope
 821     ///  │ │← `drop(x)` // This accesses `x: u32`.
 822     /// ```
 823     pub source_info: SourceInfo,
 824 }
 825
 826 /// Extra information about a some locals that's used for diagnostics and for
 827 /// classifying variables into local variables, statics, etc, which is needed e.g.
 828 /// for unsafety checking.
 829 ///
 830 /// Not used for non-StaticRef temporaries, the return place, or anonymous
 831 /// function parameters.
 832 #[derive(Clone, Debug, TyEncodable, TyDecodable, HashStable, TypeFoldable, TypeVisitable)]
 833 pub enum LocalInfo<'tcx> {
 834     /// A user-defined local variable or function parameter
 835     ///
 836     /// The `BindingForm` is solely used for local diagnostics when generating
 837     /// warnings/errors when compiling the current crate, and therefore it need
 838     /// not be visible across crates.
 839     User(ClearCrossCrate<BindingForm<'tcx>>),
 840     /// A temporary created that references the static with the given `DefId`.
 841     StaticRef { def_id: DefId, is_thread_local: bool },
 842     /// A temporary created that references the const with the given `DefId`
 843     ConstRef { def_id: DefId },
 844     /// A temporary created during the creation of an aggregate
 845     /// (e.g. a temporary for `foo` in `MyStruct { my_field: foo }`)
 846     AggregateTemp,
 847     /// A temporary created during the pass `Derefer` to avoid it's retagging
 848     DerefTemp,
 849 }
 850
 851 impl<'tcx> LocalDecl<'tcx> {
 852     /// Returns `true` only if local is a binding that can itself be
 853     /// made mutable via the addition of the `mut` keyword, namely
 854     /// something like the occurrences of `x` in:
 855     /// - `fn foo(x: Type) { ... }`,
 856     /// - `let x = ...`,
 857     /// - or `match ... { C(x) => ... }`
 858     pub fn can_be_made_mutable(&self) -> bool {
 859         matches!(
 860             self.local_info,
 861             Some(box LocalInfo::User(ClearCrossCrate::Set(
 862                 BindingForm::Var(VarBindingForm {
 863                     binding_mode: ty::BindingMode::BindByValue(_),
 864                     opt_ty_info: _,
 865                     opt_match_place: _,
 866                     pat_span: _,
 867                 }) | BindingForm::ImplicitSelf(ImplicitSelfKind::Imm),
 868             )))
 869         )
 870     }
 871
 872     /// Returns `true` if local is definitely not a `ref ident` or
 873     /// `ref mut ident` binding. (Such bindings cannot be made into
 874     /// mutable bindings, but the inverse does not necessarily hold).
 875     pub fn is_nonref_binding(&self) -> bool {
 876         matches!(
 877             self.local_info,
 878             Some(box LocalInfo::User(ClearCrossCrate::Set(
 879                 BindingForm::Var(VarBindingForm {
 880                     binding_mode: ty::BindingMode::BindByValue(_),
 881                     opt_ty_info: _,
 882                     opt_match_place: _,
 883                     pat_span: _,
 884                 }) | BindingForm::ImplicitSelf(_),
 885             )))
 886         )
 887     }
 888
 889     /// Returns `true` if this variable is a named variable or function
 890     /// parameter declared by the user.
 891     #[inline]
 892     pub fn is_user_variable(&self) -> bool {
 893         matches!(self.local_info, Some(box LocalInfo::User(_)))
 894     }
 895
 896     /// Returns `true` if this is a reference to a variable bound in a `match`
 897     /// expression that is used to access said variable for the guard of the
 898     /// match arm.
 899     pub fn is_ref_for_guard(&self) -> bool {
 900         matches!(
 901             self.local_info,
 902             Some(box LocalInfo::User(ClearCrossCrate::Set(BindingForm::RefForGuard)))
 903         )
 904     }
 905
 906     /// Returns `Some` if this is a reference to a static item that is used to
 907     /// access that static.
 908     pub fn is_ref_to_static(&self) -> bool {
 909         matches!(self.local_info, Some(box LocalInfo::StaticRef { .. }))
 910     }
 911
 912     /// Returns `Some` if this is a reference to a thread-local static item that is used to
 913     /// access that static.
 914     pub fn is_ref_to_thread_local(&self) -> bool {
 915         match self.local_info {
 916             Some(box LocalInfo::StaticRef { is_thread_local, .. }) => is_thread_local,
 917             _ => false,
 918         }
 919     }
 920
 921     /// Returns `true` if this is a DerefTemp
 922     pub fn is_deref_temp(&self) -> bool {
 923         match self.local_info {
 924             Some(box LocalInfo::DerefTemp) => return true,
 925             _ => (),
 926         }
 927         return false;
 928     }
 929
 930     /// Returns `true` is the local is from a compiler desugaring, e.g.,
 931     /// `__next` from a `for` loop.
 932     #[inline]
 933     pub fn from_compiler_desugaring(&self) -> bool {
 934         self.source_info.span.desugaring_kind().is_some()
 935     }
 936
 937     /// Creates a new `LocalDecl` for a temporary: mutable, non-internal.
 938     #[inline]
 939     pub fn new(ty: Ty<'tcx>, span: Span) -> Self {
 940         Self::with_source_info(ty, SourceInfo::outermost(span))
 941     }
 942
 943     /// Like `LocalDecl::new`, but takes a `SourceInfo` instead of a `Span`.
 944     #[inline]
 945     pub fn with_source_info(ty: Ty<'tcx>, source_info: SourceInfo) -> Self {
 946         LocalDecl {
 947             mutability: Mutability::Mut,
 948             local_info: None,
 949             internal: false,
 950             is_block_tail: None,
 951             ty,
 952             user_ty: None,
 953             source_info,
 954         }
 955     }
 956
 957     /// Converts `self` into same `LocalDecl` except tagged as internal.
 958     #[inline]
 959     pub fn internal(mut self) -> Self {
 960         self.internal = true;
 961         self
 962     }
 963
 964     /// Converts `self` into same `LocalDecl` except tagged as immutable.
 965     #[inline]
 966     pub fn immutable(mut self) -> Self {
 967         self.mutability = Mutability::Not;
 968         self
 969     }
 970
 971     /// Converts `self` into same `LocalDecl` except tagged as internal temporary.
 972     #[inline]
 973     pub fn block_tail(mut self, info: BlockTailInfo) -> Self {
 974         assert!(self.is_block_tail.is_none());
 975         self.is_block_tail = Some(info);
 976         self
 977     }
 978 }
 979
 980 #[derive(Clone, TyEncodable, TyDecodable, HashStable, TypeFoldable, TypeVisitable)]
 981 pub enum VarDebugInfoContents<'tcx> {
 982     /// NOTE(eddyb) There's an unenforced invariant that this `Place` is
 983     /// based on a `Local`, not a `Static`, and contains no indexing.
 984     Place(Place<'tcx>),
 985     Const(Constant<'tcx>),
 986 }
 987
 988 impl<'tcx> Debug for VarDebugInfoContents<'tcx> {
 989     fn fmt(&self, fmt: &mut Formatter<'_>) -> fmt::Result {
 990         match self {
 991             VarDebugInfoContents::Const(c) => write!(fmt, "{}", c),
 992             VarDebugInfoContents::Place(p) => write!(fmt, "{:?}", p),
 993         }
 994     }
 995 }
 996
 997 /// Debug information pertaining to a user variable.
 998 #[derive(Clone, Debug, TyEncodable, TyDecodable, HashStable, TypeFoldable, TypeVisitable)]
 999 pub struct VarDebugInfo<'tcx> {
1000     pub name: Symbol,
1001
1002     /// Source info of the user variable, including the scope
1003     /// within which the variable is visible (to debuginfo)
1004     /// (see `LocalDecl`'s `source_info` field for more details).
1005     pub source_info: SourceInfo,
1006
1007     /// Where the data for this user variable is to be found.
1008     pub value: VarDebugInfoContents<'tcx>,
1009 }
1010
1011 ///////////////////////////////////////////////////////////////////////////
1012 // BasicBlock
1013
1014 rustc_index::newtype_index! {
1015     /// A node in the MIR [control-flow graph][CFG].
1016     ///
1017     /// There are no branches (e.g., `if`s, function calls, etc.) within a basic block, which makes
1018     /// it easier to do [data-flow analyses] and optimizations. Instead, branches are represented
1019     /// as an edge in a graph between basic blocks.
1020     ///
1021     /// Basic blocks consist of a series of [statements][Statement], ending with a
1022     /// [terminator][Terminator]. Basic blocks can have multiple predecessors and successors,
1023     /// however there is a MIR pass ([`CriticalCallEdges`]) that removes *critical edges*, which
1024     /// are edges that go from a multi-successor node to a multi-predecessor node. This pass is
1025     /// needed because some analyses require that there are no critical edges in the CFG.
1026     ///
1027     /// Note that this type is just an index into [`Body.basic_blocks`](Body::basic_blocks);
1028     /// the actual data that a basic block holds is in [`BasicBlockData`].
1029     ///
1030     /// Read more about basic blocks in the [rustc-dev-guide][guide-mir].
1031     ///
1032     /// [CFG]: https://rustc-dev-guide.rust-lang.org/appendix/background.html#cfg
1033     /// [data-flow analyses]:
1034     ///     https://rustc-dev-guide.rust-lang.org/appendix/background.html#what-is-a-dataflow-analysis
1035     /// [`CriticalCallEdges`]: ../../rustc_const_eval/transform/add_call_guards/enum.AddCallGuards.html#variant.CriticalCallEdges
1036     /// [guide-mir]: https://rustc-dev-guide.rust-lang.org/mir/
1037     pub struct BasicBlock {
1038         derive [HashStable]
1039         DEBUG_FORMAT = "bb{}",
1040         const START_BLOCK = 0,
1041     }
1042 }
1043
1044 impl BasicBlock {
1045     pub fn start_location(self) -> Location {
1046         Location { block: self, statement_index: 0 }
1047     }
1048 }
1049
1050 ///////////////////////////////////////////////////////////////////////////
1051 // BasicBlockData
1052
1053 /// Data for a basic block, including a list of its statements.
1054 ///
1055 /// See [`BasicBlock`] for documentation on what basic blocks are at a high level.
1056 #[derive(Clone, Debug, TyEncodable, TyDecodable, HashStable, TypeFoldable, TypeVisitable)]
1057 pub struct BasicBlockData<'tcx> {
1058     /// List of statements in this block.
1059     pub statements: Vec<Statement<'tcx>>,
1060
1061     /// Terminator for this block.
1062     ///
1063     /// N.B., this should generally ONLY be `None` during construction.
1064     /// Therefore, you should generally access it via the
1065     /// `terminator()` or `terminator_mut()` methods. The only
1066     /// exception is that certain passes, such as `simplify_cfg`, swap
1067     /// out the terminator temporarily with `None` while they continue
1068     /// to recurse over the set of basic blocks.
1069     pub terminator: Option<Terminator<'tcx>>,
1070
1071     /// If true, this block lies on an unwind path. This is used
1072     /// during codegen where distinct kinds of basic blocks may be
1073     /// generated (particularly for MSVC cleanup). Unwind blocks must
1074     /// only branch to other unwind blocks.
1075     pub is_cleanup: bool,
1076 }
1077
1078 impl<'tcx> BasicBlockData<'tcx> {
1079     pub fn new(terminator: Option<Terminator<'tcx>>) -> BasicBlockData<'tcx> {
1080         BasicBlockData { statements: vec![], terminator, is_cleanup: false }
1081     }
1082
1083     /// Accessor for terminator.
1084     ///
1085     /// Terminator may not be None after construction of the basic block is complete. This accessor
1086     /// provides a convenient way to reach the terminator.
1087     #[inline]
1088     pub fn terminator(&self) -> &Terminator<'tcx> {
1089         self.terminator.as_ref().expect("invalid terminator state")
1090     }
1091
1092     #[inline]
1093     pub fn terminator_mut(&mut self) -> &mut Terminator<'tcx> {
1094         self.terminator.as_mut().expect("invalid terminator state")
1095     }
1096
1097     pub fn retain_statements<F>(&mut self, mut f: F)
1098     where
1099         F: FnMut(&mut Statement<'_>) -> bool,
1100     {
1101         for s in &mut self.statements {
1102             if !f(s) {
1103                 s.make_nop();
1104             }
1105         }
1106     }
1107
1108     pub fn expand_statements<F, I>(&mut self, mut f: F)
1109     where
1110         F: FnMut(&mut Statement<'tcx>) -> Option<I>,
1111         I: iter::TrustedLen<Item = Statement<'tcx>>,
1112     {
1113         // Gather all the iterators we'll need to splice in, and their positions.
1114         let mut splices: Vec<(usize, I)> = vec![];
1115         let mut extra_stmts = 0;
1116         for (i, s) in self.statements.iter_mut().enumerate() {
1117             if let Some(mut new_stmts) = f(s) {
1118                 if let Some(first) = new_stmts.next() {
1119                     // We can already store the first new statement.
1120                     *s = first;
1121
1122                     // Save the other statements for optimized splicing.
1123                     let remaining = new_stmts.size_hint().0;
1124                     if remaining > 0 {
1125                         splices.push((i + 1 + extra_stmts, new_stmts));
1126                         extra_stmts += remaining;
1127                     }
1128                 } else {
1129                     s.make_nop();
1130                 }
1131             }
1132         }
1133
1134         // Splice in the new statements, from the end of the block.
1135         // FIXME(eddyb) This could be more efficient with a "gap buffer"
1136         // where a range of elements ("gap") is left uninitialized, with
1137         // splicing adding new elements to the end of that gap and moving
1138         // existing elements from before the gap to the end of the gap.
1139         // For now, this is safe code, emulating a gap but initializing it.
1140         let mut gap = self.statements.len()..self.statements.len() + extra_stmts;
1141         self.statements.resize(
1142             gap.end,
1143             Statement { source_info: SourceInfo::outermost(DUMMY_SP), kind: StatementKind::Nop },
1144         );
1145         for (splice_start, new_stmts) in splices.into_iter().rev() {
1146             let splice_end = splice_start + new_stmts.size_hint().0;
1147             while gap.end > splice_end {
1148                 gap.start -= 1;
1149                 gap.end -= 1;
1150                 self.statements.swap(gap.start, gap.end);
1151             }
1152             self.statements.splice(splice_start..splice_end, new_stmts);
1153             gap.end = splice_start;
1154         }
1155     }
1156
1157     pub fn visitable(&self, index: usize) -> &dyn MirVisitable<'tcx> {
1158         if index < self.statements.len() { &self.statements[index] } else { &self.terminator }
1159     }
1160 }
1161
1162 impl<O> AssertKind<O> {
1163     /// Getting a description does not require `O` to be printable, and does not
1164     /// require allocation.
1165     /// The caller is expected to handle `BoundsCheck` separately.
1166     pub fn description(&self) -> &'static str {
1167         use AssertKind::*;
1168         match self {
1169             Overflow(BinOp::Add, _, _) => "attempt to add with overflow",
1170             Overflow(BinOp::Sub, _, _) => "attempt to subtract with overflow",
1171             Overflow(BinOp::Mul, _, _) => "attempt to multiply with overflow",
1172             Overflow(BinOp::Div, _, _) => "attempt to divide with overflow",
1173             Overflow(BinOp::Rem, _, _) => "attempt to calculate the remainder with overflow",
1174             OverflowNeg(_) => "attempt to negate with overflow",
1175             Overflow(BinOp::Shr, _, _) => "attempt to shift right with overflow",
1176             Overflow(BinOp::Shl, _, _) => "attempt to shift left with overflow",
1177             Overflow(op, _, _) => bug!("{:?} cannot overflow", op),
1178             DivisionByZero(_) => "attempt to divide by zero",
1179             RemainderByZero(_) => "attempt to calculate the remainder with a divisor of zero",
1180             ResumedAfterReturn(GeneratorKind::Gen) => "generator resumed after completion",
1181             ResumedAfterReturn(GeneratorKind::Async(_)) => "`async fn` resumed after completion",
1182             ResumedAfterPanic(GeneratorKind::Gen) => "generator resumed after panicking",
1183             ResumedAfterPanic(GeneratorKind::Async(_)) => "`async fn` resumed after panicking",
1184             BoundsCheck { .. } => bug!("Unexpected AssertKind"),
1185         }
1186     }
1187
1188     /// Format the message arguments for the `assert(cond, msg..)` terminator in MIR printing.
1189     pub fn fmt_assert_args<W: Write>(&self, f: &mut W) -> fmt::Result
1190     where
1191         O: Debug,
1192     {
1193         use AssertKind::*;
1194         match self {
1195             BoundsCheck { ref len, ref index } => write!(
1196                 f,
1197                 "\"index out of bounds: the length is {{}} but the index is {{}}\", {:?}, {:?}",
1198                 len, index
1199             ),
1200
1201             OverflowNeg(op) => {
1202                 write!(f, "\"attempt to negate `{{}}`, which would overflow\", {:?}", op)
1203             }
1204             DivisionByZero(op) => write!(f, "\"attempt to divide `{{}}` by zero\", {:?}", op),
1205             RemainderByZero(op) => write!(
1206                 f,
1207                 "\"attempt to calculate the remainder of `{{}}` with a divisor of zero\", {:?}",
1208                 op
1209             ),
1210             Overflow(BinOp::Add, l, r) => write!(
1211                 f,
1212                 "\"attempt to compute `{{}} + {{}}`, which would overflow\", {:?}, {:?}",
1213                 l, r
1214             ),
1215             Overflow(BinOp::Sub, l, r) => write!(
1216                 f,
1217                 "\"attempt to compute `{{}} - {{}}`, which would overflow\", {:?}, {:?}",
1218                 l, r
1219             ),
1220             Overflow(BinOp::Mul, l, r) => write!(
1221                 f,
1222                 "\"attempt to compute `{{}} * {{}}`, which would overflow\", {:?}, {:?}",
1223                 l, r
1224             ),
1225             Overflow(BinOp::Div, l, r) => write!(
1226                 f,
1227                 "\"attempt to compute `{{}} / {{}}`, which would overflow\", {:?}, {:?}",
1228                 l, r
1229             ),
1230             Overflow(BinOp::Rem, l, r) => write!(
1231                 f,
1232                 "\"attempt to compute the remainder of `{{}} % {{}}`, which would overflow\", {:?}, {:?}",
1233                 l, r
1234             ),
1235             Overflow(BinOp::Shr, _, r) => {
1236                 write!(f, "\"attempt to shift right by `{{}}`, which would overflow\", {:?}", r)
1237             }
1238             Overflow(BinOp::Shl, _, r) => {
1239                 write!(f, "\"attempt to shift left by `{{}}`, which would overflow\", {:?}", r)
1240             }
1241             _ => write!(f, "\"{}\"", self.description()),
1242         }
1243     }
1244 }
1245
1246 impl<O: fmt::Debug> fmt::Debug for AssertKind<O> {
1247     fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
1248         use AssertKind::*;
1249         match self {
1250             BoundsCheck { ref len, ref index } => write!(
1251                 f,
1252                 "index out of bounds: the length is {:?} but the index is {:?}",
1253                 len, index
1254             ),
1255             OverflowNeg(op) => write!(f, "attempt to negate `{:#?}`, which would overflow", op),
1256             DivisionByZero(op) => write!(f, "attempt to divide `{:#?}` by zero", op),
1257             RemainderByZero(op) => write!(
1258                 f,
1259                 "attempt to calculate the remainder of `{:#?}` with a divisor of zero",
1260                 op
1261             ),
1262             Overflow(BinOp::Add, l, r) => {
1263                 write!(f, "attempt to compute `{:#?} + {:#?}`, which would overflow", l, r)
1264             }
1265             Overflow(BinOp::Sub, l, r) => {
1266                 write!(f, "attempt to compute `{:#?} - {:#?}`, which would overflow", l, r)
1267             }
1268             Overflow(BinOp::Mul, l, r) => {
1269                 write!(f, "attempt to compute `{:#?} * {:#?}`, which would overflow", l, r)
1270             }
1271             Overflow(BinOp::Div, l, r) => {
1272                 write!(f, "attempt to compute `{:#?} / {:#?}`, which would overflow", l, r)
1273             }
1274             Overflow(BinOp::Rem, l, r) => write!(
1275                 f,
1276                 "attempt to compute the remainder of `{:#?} % {:#?}`, which would overflow",
1277                 l, r
1278             ),
1279             Overflow(BinOp::Shr, _, r) => {
1280                 write!(f, "attempt to shift right by `{:#?}`, which would overflow", r)
1281             }
1282             Overflow(BinOp::Shl, _, r) => {
1283                 write!(f, "attempt to shift left by `{:#?}`, which would overflow", r)
1284             }
1285             _ => write!(f, "{}", self.description()),
1286         }
1287     }
1288 }
1289
1290 ///////////////////////////////////////////////////////////////////////////
1291 // Statements
1292
1293 /// A statement in a basic block, including information about its source code.
1294 #[derive(Clone, TyEncodable, TyDecodable, HashStable, TypeFoldable, TypeVisitable)]
1295 pub struct Statement<'tcx> {
1296     pub source_info: SourceInfo,
1297     pub kind: StatementKind<'tcx>,
1298 }
1299
1300 impl Statement<'_> {
1301     /// Changes a statement to a nop. This is both faster than deleting instructions and avoids
1302     /// invalidating statement indices in `Location`s.
1303     pub fn make_nop(&mut self) {
1304         self.kind = StatementKind::Nop
1305     }
1306
1307     /// Changes a statement to a nop and returns the original statement.
1308     #[must_use = "If you don't need the statement, use `make_nop` instead"]
1309     pub fn replace_nop(&mut self) -> Self {
1310         Statement {
1311             source_info: self.source_info,
1312             kind: mem::replace(&mut self.kind, StatementKind::Nop),
1313         }
1314     }
1315 }
1316
1317 impl Debug for Statement<'_> {
1318     fn fmt(&self, fmt: &mut Formatter<'_>) -> fmt::Result {
1319         use self::StatementKind::*;
1320         match self.kind {
1321             Assign(box (ref place, ref rv)) => write!(fmt, "{:?} = {:?}", place, rv),
1322             FakeRead(box (ref cause, ref place)) => {
1323                 write!(fmt, "FakeRead({:?}, {:?})", cause, place)
1324             }
1325             Retag(ref kind, ref place) => write!(
1326                 fmt,
1327                 "Retag({}{:?})",
1328                 match kind {
1329                     RetagKind::FnEntry => "[fn entry] ",
1330                     RetagKind::TwoPhase => "[2phase] ",
1331                     RetagKind::Raw => "[raw] ",
1332                     RetagKind::Default => "",
1333                 },
1334                 place,
1335             ),
1336             StorageLive(ref place) => write!(fmt, "StorageLive({:?})", place),
1337             StorageDead(ref place) => write!(fmt, "StorageDead({:?})", place),
1338             SetDiscriminant { ref place, variant_index } => {
1339                 write!(fmt, "discriminant({:?}) = {:?}", place, variant_index)
1340             }
1341             Deinit(ref place) => write!(fmt, "Deinit({:?})", place),
1342             AscribeUserType(box (ref place, ref c_ty), ref variance) => {
1343                 write!(fmt, "AscribeUserType({:?}, {:?}, {:?})", place, variance, c_ty)
1344             }
1345             Coverage(box self::Coverage { ref kind, code_region: Some(ref rgn) }) => {
1346                 write!(fmt, "Coverage::{:?} for {:?}", kind, rgn)
1347             }
1348             Coverage(box ref coverage) => write!(fmt, "Coverage::{:?}", coverage.kind),
1349             Intrinsic(box ref intrinsic) => write!(fmt, "{intrinsic}"),
1350             Nop => write!(fmt, "nop"),
1351         }
1352     }
1353 }
1354
1355 impl<'tcx> StatementKind<'tcx> {
1356     pub fn as_assign_mut(&mut self) -> Option<&mut (Place<'tcx>, Rvalue<'tcx>)> {
1357         match self {
1358             StatementKind::Assign(x) => Some(x),
1359             _ => None,
1360         }
1361     }
1362
1363     pub fn as_assign(&self) -> Option<&(Place<'tcx>, Rvalue<'tcx>)> {
1364         match self {
1365             StatementKind::Assign(x) => Some(x),
1366             _ => None,
1367         }
1368     }
1369 }
1370
1371 ///////////////////////////////////////////////////////////////////////////
1372 // Places
1373
1374 impl<V, T> ProjectionElem<V, T> {
1375     /// Returns `true` if the target of this projection may refer to a different region of memory
1376     /// than the base.
1377     fn is_indirect(&self) -> bool {
1378         match self {
1379             Self::Deref => true,
1380
1381             Self::Field(_, _)
1382             | Self::Index(_)
1383             | Self::ConstantIndex { .. }
1384             | Self::Subslice { .. }
1385             | Self::Downcast(_, _) => false,
1386         }
1387     }
1388
1389     /// Returns `true` if this is a `Downcast` projection with the given `VariantIdx`.
1390     pub fn is_downcast_to(&self, v: VariantIdx) -> bool {
1391         matches!(*self, Self::Downcast(_, x) if x == v)
1392     }
1393
1394     /// Returns `true` if this is a `Field` projection with the given index.
1395     pub fn is_field_to(&self, f: Field) -> bool {
1396         matches!(*self, Self::Field(x, _) if x == f)
1397     }
1398 }
1399
1400 /// Alias for projections as they appear in `UserTypeProjection`, where we
1401 /// need neither the `V` parameter for `Index` nor the `T` for `Field`.
1402 pub type ProjectionKind = ProjectionElem<(), ()>;
1403
1404 rustc_index::newtype_index! {
1405     /// A [newtype'd][wrapper] index type in the MIR [control-flow graph][CFG]
1406     ///
1407     /// A field (e.g., `f` in `_1.f`) is one variant of [`ProjectionElem`]. Conceptually,
1408     /// rustc can identify that a field projection refers to either two different regions of memory
1409     /// or the same one between the base and the 'projection element'.
1410     /// Read more about projections in the [rustc-dev-guide][mir-datatypes]
1411     ///
1412     /// [wrapper]: https://rustc-dev-guide.rust-lang.org/appendix/glossary.html#newtype
1413     /// [CFG]: https://rustc-dev-guide.rust-lang.org/appendix/background.html#cfg
1414     /// [mir-datatypes]: https://rustc-dev-guide.rust-lang.org/mir/index.html#mir-data-types
1415     pub struct Field {
1416         derive [HashStable]
1417         DEBUG_FORMAT = "field[{}]"
1418     }
1419 }
1420
1421 #[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
1422 pub struct PlaceRef<'tcx> {
1423     pub local: Local,
1424     pub projection: &'tcx [PlaceElem<'tcx>],
1425 }
1426
1427 // Once we stop implementing `Ord` for `DefId`,
1428 // this impl will be unnecessary. Until then, we'll
1429 // leave this impl in place to prevent re-adding a
1430 // dependency on the `Ord` impl for `DefId`
1431 impl<'tcx> !PartialOrd for PlaceRef<'tcx> {}
1432
1433 impl<'tcx> Place<'tcx> {
1434     // FIXME change this to a const fn by also making List::empty a const fn.
1435     pub fn return_place() -> Place<'tcx> {
1436         Place { local: RETURN_PLACE, projection: List::empty() }
1437     }
1438
1439     /// Returns `true` if this `Place` contains a `Deref` projection.
1440     ///
1441     /// If `Place::is_indirect` returns false, the caller knows that the `Place` refers to the
1442     /// same region of memory as its base.
1443     pub fn is_indirect(&self) -> bool {
1444         self.projection.iter().any(|elem| elem.is_indirect())
1445     }
1446
1447     /// If MirPhase >= Derefered and if projection contains Deref,
1448     /// It's guaranteed to be in the first place
1449     pub fn has_deref(&self) -> bool {
1450         // To make sure this is not accidently used in wrong mir phase
1451         debug_assert!(
1452             self.projection.is_empty() || !self.projection[1..].contains(&PlaceElem::Deref)
1453         );
1454         self.projection.first() == Some(&PlaceElem::Deref)
1455     }
1456
1457     /// Finds the innermost `Local` from this `Place`, *if* it is either a local itself or
1458     /// a single deref of a local.
1459     #[inline(always)]
1460     pub fn local_or_deref_local(&self) -> Option<Local> {
1461         self.as_ref().local_or_deref_local()
1462     }
1463
1464     /// If this place represents a local variable like `_X` with no
1465     /// projections, return `Some(_X)`.
1466     #[inline(always)]
1467     pub fn as_local(&self) -> Option<Local> {
1468         self.as_ref().as_local()
1469     }
1470
1471     #[inline]
1472     pub fn as_ref(&self) -> PlaceRef<'tcx> {
1473         PlaceRef { local: self.local, projection: &self.projection }
1474     }
1475
1476     /// Iterate over the projections in evaluation order, i.e., the first element is the base with
1477     /// its projection and then subsequently more projections are added.
1478     /// As a concrete example, given the place a.b.c, this would yield:
1479     /// - (a, .b)
1480     /// - (a.b, .c)
1481     ///
1482     /// Given a place without projections, the iterator is empty.
1483     #[inline]
1484     pub fn iter_projections(
1485         self,
1486     ) -> impl Iterator<Item = (PlaceRef<'tcx>, PlaceElem<'tcx>)> + DoubleEndedIterator {
1487         self.as_ref().iter_projections()
1488     }
1489
1490     /// Generates a new place by appending `more_projections` to the existing ones
1491     /// and interning the result.
1492     pub fn project_deeper(self, more_projections: &[PlaceElem<'tcx>], tcx: TyCtxt<'tcx>) -> Self {
1493         if more_projections.is_empty() {
1494             return self;
1495         }
1496
1497         let mut v: Vec<PlaceElem<'tcx>>;
1498
1499         let new_projections = if self.projection.is_empty() {
1500             more_projections
1501         } else {
1502             v = Vec::with_capacity(self.projection.len() + more_projections.len());
1503             v.extend(self.projection);
1504             v.extend(more_projections);
1505             &v
1506         };
1507
1508         Place { local: self.local, projection: tcx.intern_place_elems(new_projections) }
1509     }
1510 }
1511
1512 impl From<Local> for Place<'_> {
1513     #[inline]
1514     fn from(local: Local) -> Self {
1515         Place { local, projection: List::empty() }
1516     }
1517 }
1518
1519 impl<'tcx> PlaceRef<'tcx> {
1520     /// Finds the innermost `Local` from this `Place`, *if* it is either a local itself or
1521     /// a single deref of a local.
1522     pub fn local_or_deref_local(&self) -> Option<Local> {
1523         match *self {
1524             PlaceRef { local, projection: [] }
1525             | PlaceRef { local, projection: [ProjectionElem::Deref] } => Some(local),
1526             _ => None,
1527         }
1528     }
1529
1530     /// If MirPhase >= Derefered and if projection contains Deref,
1531     /// It's guaranteed to be in the first place
1532     pub fn has_deref(&self) -> bool {
1533         self.projection.first() == Some(&PlaceElem::Deref)
1534     }
1535
1536     /// If this place represents a local variable like `_X` with no
1537     /// projections, return `Some(_X)`.
1538     #[inline]
1539     pub fn as_local(&self) -> Option<Local> {
1540         match *self {
1541             PlaceRef { local, projection: [] } => Some(local),
1542             _ => None,
1543         }
1544     }
1545
1546     #[inline]
1547     pub fn last_projection(&self) -> Option<(PlaceRef<'tcx>, PlaceElem<'tcx>)> {
1548         if let &[ref proj_base @ .., elem] = self.projection {
1549             Some((PlaceRef { local: self.local, projection: proj_base }, elem))
1550         } else {
1551             None
1552         }
1553     }
1554
1555     /// Iterate over the projections in evaluation order, i.e., the first element is the base with
1556     /// its projection and then subsequently more projections are added.
1557     /// As a concrete example, given the place a.b.c, this would yield:
1558     /// - (a, .b)
1559     /// - (a.b, .c)
1560     ///
1561     /// Given a place without projections, the iterator is empty.
1562     #[inline]
1563     pub fn iter_projections(
1564         self,
1565     ) -> impl Iterator<Item = (PlaceRef<'tcx>, PlaceElem<'tcx>)> + DoubleEndedIterator {
1566         self.projection.iter().enumerate().map(move |(i, proj)| {
1567             let base = PlaceRef { local: self.local, projection: &self.projection[..i] };
1568             (base, *proj)
1569         })
1570     }
1571 }
1572
1573 impl Debug for Place<'_> {
1574     fn fmt(&self, fmt: &mut Formatter<'_>) -> fmt::Result {
1575         for elem in self.projection.iter().rev() {
1576             match elem {
1577                 ProjectionElem::Downcast(_, _) | ProjectionElem::Field(_, _) => {
1578                     write!(fmt, "(").unwrap();
1579                 }
1580                 ProjectionElem::Deref => {
1581                     write!(fmt, "(*").unwrap();
1582                 }
1583                 ProjectionElem::Index(_)
1584                 | ProjectionElem::ConstantIndex { .. }
1585                 | ProjectionElem::Subslice { .. } => {}
1586             }
1587         }
1588
1589         write!(fmt, "{:?}", self.local)?;
1590
1591         for elem in self.projection.iter() {
1592             match elem {
1593                 ProjectionElem::Downcast(Some(name), _index) => {
1594                     write!(fmt, " as {})", name)?;
1595                 }
1596                 ProjectionElem::Downcast(None, index) => {
1597                     write!(fmt, " as variant#{:?})", index)?;
1598                 }
1599                 ProjectionElem::Deref => {
1600                     write!(fmt, ")")?;
1601                 }
1602                 ProjectionElem::Field(field, ty) => {
1603                     write!(fmt, ".{:?}: {:?})", field.index(), ty)?;
1604                 }
1605                 ProjectionElem::Index(ref index) => {
1606                     write!(fmt, "[{:?}]", index)?;
1607                 }
1608                 ProjectionElem::ConstantIndex { offset, min_length, from_end: false } => {
1609                     write!(fmt, "[{:?} of {:?}]", offset, min_length)?;
1610                 }
1611                 ProjectionElem::ConstantIndex { offset, min_length, from_end: true } => {
1612                     write!(fmt, "[-{:?} of {:?}]", offset, min_length)?;
1613                 }
1614                 ProjectionElem::Subslice { from, to, from_end: true } if to == 0 => {
1615                     write!(fmt, "[{:?}:]", from)?;
1616                 }
1617                 ProjectionElem::Subslice { from, to, from_end: true } if from == 0 => {
1618                     write!(fmt, "[:-{:?}]", to)?;
1619                 }
1620                 ProjectionElem::Subslice { from, to, from_end: true } => {
1621                     write!(fmt, "[{:?}:-{:?}]", from, to)?;
1622                 }
1623                 ProjectionElem::Subslice { from, to, from_end: false } => {
1624                     write!(fmt, "[{:?}..{:?}]", from, to)?;
1625                 }
1626             }
1627         }
1628
1629         Ok(())
1630     }
1631 }
1632
1633 ///////////////////////////////////////////////////////////////////////////
1634 // Scopes
1635
1636 rustc_index::newtype_index! {
1637     pub struct SourceScope {
1638         derive [HashStable]
1639         DEBUG_FORMAT = "scope[{}]",
1640         const OUTERMOST_SOURCE_SCOPE = 0,
1641     }
1642 }
1643
1644 impl SourceScope {
1645     /// Finds the original HirId this MIR item came from.
1646     /// This is necessary after MIR optimizations, as otherwise we get a HirId
1647     /// from the function that was inlined instead of the function call site.
1648     pub fn lint_root<'tcx>(
1649         self,
1650         source_scopes: &IndexVec<SourceScope, SourceScopeData<'tcx>>,
1651     ) -> Option<HirId> {
1652         let mut data = &source_scopes[self];
1653         // FIXME(oli-obk): we should be able to just walk the `inlined_parent_scope`, but it
1654         // does not work as I thought it would. Needs more investigation and documentation.
1655         while data.inlined.is_some() {
1656             trace!(?data);
1657             data = &source_scopes[data.parent_scope.unwrap()];
1658         }
1659         trace!(?data);
1660         match &data.local_data {
1661             ClearCrossCrate::Set(data) => Some(data.lint_root),
1662             ClearCrossCrate::Clear => None,
1663         }
1664     }
1665
1666     /// The instance this source scope was inlined from, if any.
1667     #[inline]
1668     pub fn inlined_instance<'tcx>(
1669         self,
1670         source_scopes: &IndexVec<SourceScope, SourceScopeData<'tcx>>,
1671     ) -> Option<ty::Instance<'tcx>> {
1672         let scope_data = &source_scopes[self];
1673         if let Some((inlined_instance, _)) = scope_data.inlined {
1674             Some(inlined_instance)
1675         } else if let Some(inlined_scope) = scope_data.inlined_parent_scope {
1676             Some(source_scopes[inlined_scope].inlined.unwrap().0)
1677         } else {
1678             None
1679         }
1680     }
1681 }
1682
1683 #[derive(Clone, Debug, TyEncodable, TyDecodable, HashStable, TypeFoldable, TypeVisitable)]
1684 pub struct SourceScopeData<'tcx> {
1685     pub span: Span,
1686     pub parent_scope: Option<SourceScope>,
1687
1688     /// Whether this scope is the root of a scope tree of another body,
1689     /// inlined into this body by the MIR inliner.
1690     /// `ty::Instance` is the callee, and the `Span` is the call site.
1691     pub inlined: Option<(ty::Instance<'tcx>, Span)>,
1692
1693     /// Nearest (transitive) parent scope (if any) which is inlined.
1694     /// This is an optimization over walking up `parent_scope`
1695     /// until a scope with `inlined: Some(...)` is found.
1696     pub inlined_parent_scope: Option<SourceScope>,
1697
1698     /// Crate-local information for this source scope, that can't (and
1699     /// needn't) be tracked across crates.
1700     pub local_data: ClearCrossCrate<SourceScopeLocalData>,
1701 }
1702
1703 #[derive(Clone, Debug, TyEncodable, TyDecodable, HashStable)]
1704 pub struct SourceScopeLocalData {
1705     /// An `HirId` with lint levels equivalent to this scope's lint levels.
1706     pub lint_root: hir::HirId,
1707     /// The unsafe block that contains this node.
1708     pub safety: Safety,
1709 }
1710
1711 ///////////////////////////////////////////////////////////////////////////
1712 // Operands
1713
1714 impl<'tcx> Debug for Operand<'tcx> {
1715     fn fmt(&self, fmt: &mut Formatter<'_>) -> fmt::Result {
1716         use self::Operand::*;
1717         match *self {
1718             Constant(ref a) => write!(fmt, "{:?}", a),
1719             Copy(ref place) => write!(fmt, "{:?}", place),
1720             Move(ref place) => write!(fmt, "move {:?}", place),
1721         }
1722     }
1723 }
1724
1725 impl<'tcx> Operand<'tcx> {
1726     /// Convenience helper to make a constant that refers to the fn
1727     /// with given `DefId` and substs. Since this is used to synthesize
1728     /// MIR, assumes `user_ty` is None.
1729     pub fn function_handle(
1730         tcx: TyCtxt<'tcx>,
1731         def_id: DefId,
1732         substs: SubstsRef<'tcx>,
1733         span: Span,
1734     ) -> Self {
1735         let ty = tcx.bound_type_of(def_id).subst(tcx, substs);
1736         Operand::Constant(Box::new(Constant {
1737             span,
1738             user_ty: None,
1739             literal: ConstantKind::Val(ConstValue::ZeroSized, ty),
1740         }))
1741     }
1742
1743     pub fn is_move(&self) -> bool {
1744         matches!(self, Operand::Move(..))
1745     }
1746
1747     /// Convenience helper to make a literal-like constant from a given scalar value.
1748     /// Since this is used to synthesize MIR, assumes `user_ty` is None.
1749     pub fn const_from_scalar(
1750         tcx: TyCtxt<'tcx>,
1751         ty: Ty<'tcx>,
1752         val: Scalar,
1753         span: Span,
1754     ) -> Operand<'tcx> {
1755         debug_assert!({
1756             let param_env_and_ty = ty::ParamEnv::empty().and(ty);
1757             let type_size = tcx
1758                 .layout_of(param_env_and_ty)
1759                 .unwrap_or_else(|e| panic!("could not compute layout for {:?}: {:?}", ty, e))
1760                 .size;
1761             let scalar_size = match val {
1762                 Scalar::Int(int) => int.size(),
1763                 _ => panic!("Invalid scalar type {:?}", val),
1764             };
1765             scalar_size == type_size
1766         });
1767         Operand::Constant(Box::new(Constant {
1768             span,
1769             user_ty: None,
1770             literal: ConstantKind::Val(ConstValue::Scalar(val), ty),
1771         }))
1772     }
1773
1774     pub fn to_copy(&self) -> Self {
1775         match *self {
1776             Operand::Copy(_) | Operand::Constant(_) => self.clone(),
1777             Operand::Move(place) => Operand::Copy(place),
1778         }
1779     }
1780
1781     /// Returns the `Place` that is the target of this `Operand`, or `None` if this `Operand` is a
1782     /// constant.
1783     pub fn place(&self) -> Option<Place<'tcx>> {
1784         match self {
1785             Operand::Copy(place) | Operand::Move(place) => Some(*place),
1786             Operand::Constant(_) => None,
1787         }
1788     }
1789
1790     /// Returns the `Constant` that is the target of this `Operand`, or `None` if this `Operand` is a
1791     /// place.
1792     pub fn constant(&self) -> Option<&Constant<'tcx>> {
1793         match self {
1794             Operand::Constant(x) => Some(&**x),
1795             Operand::Copy(_) | Operand::Move(_) => None,
1796         }
1797     }
1798
1799     /// Gets the `ty::FnDef` from an operand if it's a constant function item.
1800     ///
1801     /// While this is unlikely in general, it's the normal case of what you'll
1802     /// find as the `func` in a [`TerminatorKind::Call`].
1803     pub fn const_fn_def(&self) -> Option<(DefId, SubstsRef<'tcx>)> {
1804         let const_ty = self.constant()?.literal.ty();
1805         if let ty::FnDef(def_id, substs) = *const_ty.kind() { Some((def_id, substs)) } else { None }
1806     }
1807 }
1808
1809 ///////////////////////////////////////////////////////////////////////////
1810 /// Rvalues
1811
1812 impl<'tcx> Rvalue<'tcx> {
1813     /// Returns true if rvalue can be safely removed when the result is unused.
1814     #[inline]
1815     pub fn is_safe_to_remove(&self) -> bool {
1816         match self {
1817             // Pointer to int casts may be side-effects due to exposing the provenance.
1818             // While the model is undecided, we should be conservative. See
1819             // <https://www.ralfj.de/blog/2022/04/11/provenance-exposed.html>
1820             Rvalue::Cast(CastKind::PointerExposeAddress, _, _) => false,
1821             Rvalue::Cast(CastKind::DynStar, _, _) => false,
1822
1823             Rvalue::Use(_)
1824             | Rvalue::CopyForDeref(_)
1825             | Rvalue::Repeat(_, _)
1826             | Rvalue::Ref(_, _, _)
1827             | Rvalue::ThreadLocalRef(_)
1828             | Rvalue::AddressOf(_, _)
1829             | Rvalue::Len(_)
1830             | Rvalue::Cast(
1831                 CastKind::Misc | CastKind::Pointer(_) | CastKind::PointerFromExposedAddress,
1832                 _,
1833                 _,
1834             )
1835             | Rvalue::BinaryOp(_, _)
1836             | Rvalue::CheckedBinaryOp(_, _)
1837             | Rvalue::NullaryOp(_, _)
1838             | Rvalue::UnaryOp(_, _)
1839             | Rvalue::Discriminant(_)
1840             | Rvalue::Aggregate(_, _)
1841             | Rvalue::ShallowInitBox(_, _) => true,
1842         }
1843     }
1844 }
1845
1846 impl BorrowKind {
1847     pub fn allows_two_phase_borrow(&self) -> bool {
1848         match *self {
1849             BorrowKind::Shared | BorrowKind::Shallow | BorrowKind::Unique => false,
1850             BorrowKind::Mut { allow_two_phase_borrow } => allow_two_phase_borrow,
1851         }
1852     }
1853
1854     pub fn describe_mutability(&self) -> &str {
1855         match *self {
1856             BorrowKind::Shared | BorrowKind::Shallow | BorrowKind::Unique => "immutable",
1857             BorrowKind::Mut { .. } => "mutable",
1858         }
1859     }
1860 }
1861
1862 impl BinOp {
1863     pub fn is_checkable(self) -> bool {
1864         use self::BinOp::*;
1865         matches!(self, Add | Sub | Mul | Shl | Shr)
1866     }
1867 }
1868
1869 impl<'tcx> Debug for Rvalue<'tcx> {
1870     fn fmt(&self, fmt: &mut Formatter<'_>) -> fmt::Result {
1871         use self::Rvalue::*;
1872
1873         match *self {
1874             Use(ref place) => write!(fmt, "{:?}", place),
1875             Repeat(ref a, b) => {
1876                 write!(fmt, "[{:?}; ", a)?;
1877                 pretty_print_const(b, fmt, false)?;
1878                 write!(fmt, "]")
1879             }
1880             Len(ref a) => write!(fmt, "Len({:?})", a),
1881             Cast(ref kind, ref place, ref ty) => {
1882                 write!(fmt, "{:?} as {:?} ({:?})", place, ty, kind)
1883             }
1884             BinaryOp(ref op, box (ref a, ref b)) => write!(fmt, "{:?}({:?}, {:?})", op, a, b),
1885             CheckedBinaryOp(ref op, box (ref a, ref b)) => {
1886                 write!(fmt, "Checked{:?}({:?}, {:?})", op, a, b)
1887             }
1888             UnaryOp(ref op, ref a) => write!(fmt, "{:?}({:?})", op, a),
1889             Discriminant(ref place) => write!(fmt, "discriminant({:?})", place),
1890             NullaryOp(ref op, ref t) => write!(fmt, "{:?}({:?})", op, t),
1891             ThreadLocalRef(did) => ty::tls::with(|tcx| {
1892                 let muta = tcx.static_mutability(did).unwrap().prefix_str();
1893                 write!(fmt, "&/*tls*/ {}{}", muta, tcx.def_path_str(did))
1894             }),
1895             Ref(region, borrow_kind, ref place) => {
1896                 let kind_str = match borrow_kind {
1897                     BorrowKind::Shared => "",
1898                     BorrowKind::Shallow => "shallow ",
1899                     BorrowKind::Mut { .. } | BorrowKind::Unique => "mut ",
1900                 };
1901
1902                 // When printing regions, add trailing space if necessary.
1903                 let print_region = ty::tls::with(|tcx| {
1904                     tcx.sess.verbose() || tcx.sess.opts.unstable_opts.identify_regions
1905                 });
1906                 let region = if print_region {
1907                     let mut region = region.to_string();
1908                     if !region.is_empty() {
1909                         region.push(' ');
1910                     }
1911                     region
1912                 } else {
1913                     // Do not even print 'static
1914                     String::new()
1915                 };
1916                 write!(fmt, "&{}{}{:?}", region, kind_str, place)
1917             }
1918
1919             CopyForDeref(ref place) => write!(fmt, "deref_copy {:#?}", place),
1920
1921             AddressOf(mutability, ref place) => {
1922                 let kind_str = match mutability {
1923                     Mutability::Mut => "mut",
1924                     Mutability::Not => "const",
1925                 };
1926
1927                 write!(fmt, "&raw {} {:?}", kind_str, place)
1928             }
1929
1930             Aggregate(ref kind, ref places) => {
1931                 let fmt_tuple = |fmt: &mut Formatter<'_>, name: &str| {
1932                     let mut tuple_fmt = fmt.debug_tuple(name);
1933                     for place in places {
1934                         tuple_fmt.field(place);
1935                     }
1936                     tuple_fmt.finish()
1937                 };
1938
1939                 match **kind {
1940                     AggregateKind::Array(_) => write!(fmt, "{:?}", places),
1941
1942                     AggregateKind::Tuple => {
1943                         if places.is_empty() {
1944                             write!(fmt, "()")
1945                         } else {
1946                             fmt_tuple(fmt, "")
1947                         }
1948                     }
1949
1950                     AggregateKind::Adt(adt_did, variant, substs, _user_ty, _) => {
1951                         ty::tls::with(|tcx| {
1952                             let variant_def = &tcx.adt_def(adt_did).variant(variant);
1953                             let substs = tcx.lift(substs).expect("could not lift for printing");
1954                             let name = FmtPrinter::new(tcx, Namespace::ValueNS)
1955                                 .print_def_path(variant_def.def_id, substs)?
1956                                 .into_buffer();
1957
1958                             match variant_def.ctor_kind {
1959                                 CtorKind::Const => fmt.write_str(&name),
1960                                 CtorKind::Fn => fmt_tuple(fmt, &name),
1961                                 CtorKind::Fictive => {
1962                                     let mut struct_fmt = fmt.debug_struct(&name);
1963                                     for (field, place) in iter::zip(&variant_def.fields, places) {
1964                                         struct_fmt.field(field.name.as_str(), place);
1965                                     }
1966                                     struct_fmt.finish()
1967                                 }
1968                             }
1969                         })
1970                     }
1971
1972                     AggregateKind::Closure(def_id, substs) => ty::tls::with(|tcx| {
1973                         let name = if tcx.sess.opts.unstable_opts.span_free_formats {
1974                             let substs = tcx.lift(substs).unwrap();
1975                             format!(
1976                                 "[closure@{}]",
1977                                 tcx.def_path_str_with_substs(def_id.to_def_id(), substs),
1978                             )
1979                         } else {
1980                             let span = tcx.def_span(def_id);
1981                             format!(
1982                                 "[closure@{}]",
1983                                 tcx.sess.source_map().span_to_diagnostic_string(span)
1984                             )
1985                         };
1986                         let mut struct_fmt = fmt.debug_struct(&name);
1987
1988                         // FIXME(project-rfc-2229#48): This should be a list of capture names/places
1989                         if let Some(upvars) = tcx.upvars_mentioned(def_id) {
1990                             for (&var_id, place) in iter::zip(upvars.keys(), places) {
1991                                 let var_name = tcx.hir().name(var_id);
1992                                 struct_fmt.field(var_name.as_str(), place);
1993                             }
1994                         }
1995
1996                         struct_fmt.finish()
1997                     }),
1998
1999                     AggregateKind::Generator(def_id, _, _) => ty::tls::with(|tcx| {
2000                         let name = format!("[generator@{:?}]", tcx.def_span(def_id));
2001                         let mut struct_fmt = fmt.debug_struct(&name);
2002
2003                         // FIXME(project-rfc-2229#48): This should be a list of capture names/places
2004                         if let Some(upvars) = tcx.upvars_mentioned(def_id) {
2005                             for (&var_id, place) in iter::zip(upvars.keys(), places) {
2006                                 let var_name = tcx.hir().name(var_id);
2007                                 struct_fmt.field(var_name.as_str(), place);
2008                             }
2009                         }
2010
2011                         struct_fmt.finish()
2012                     }),
2013                 }
2014             }
2015
2016             ShallowInitBox(ref place, ref ty) => {
2017                 write!(fmt, "ShallowInitBox({:?}, {:?})", place, ty)
2018             }
2019         }
2020     }
2021 }
2022
2023 ///////////////////////////////////////////////////////////////////////////
2024 /// Constants
2025 ///
2026 /// Two constants are equal if they are the same constant. Note that
2027 /// this does not necessarily mean that they are `==` in Rust. In
2028 /// particular, one must be wary of `NaN`!
2029
2030 #[derive(Clone, Copy, PartialEq, TyEncodable, TyDecodable, Hash, HashStable)]
2031 pub struct Constant<'tcx> {
2032     pub span: Span,
2033
2034     /// Optional user-given type: for something like
2035     /// `collect::<Vec<_>>`, this would be present and would
2036     /// indicate that `Vec<_>` was explicitly specified.
2037     ///
2038     /// Needed for NLL to impose user-given type constraints.
2039     pub user_ty: Option<UserTypeAnnotationIndex>,
2040
2041     pub literal: ConstantKind<'tcx>,
2042 }
2043
2044 #[derive(Clone, Copy, PartialEq, Eq, TyEncodable, TyDecodable, Hash, HashStable, Debug)]
2045 #[derive(Lift)]
2046 pub enum ConstantKind<'tcx> {
2047     /// This constant came from the type system
2048     Ty(ty::Const<'tcx>),
2049     /// This constant cannot go back into the type system, as it represents
2050     /// something the type system cannot handle (e.g. pointers).
2051     Val(interpret::ConstValue<'tcx>, Ty<'tcx>),
2052 }
2053
2054 impl<'tcx> Constant<'tcx> {
2055     pub fn check_static_ptr(&self, tcx: TyCtxt<'_>) -> Option<DefId> {
2056         match self.literal.try_to_scalar() {
2057             Some(Scalar::Ptr(ptr, _size)) => match tcx.global_alloc(ptr.provenance) {
2058                 GlobalAlloc::Static(def_id) => {
2059                     assert!(!tcx.is_thread_local_static(def_id));
2060                     Some(def_id)
2061                 }
2062                 _ => None,
2063             },
2064             _ => None,
2065         }
2066     }
2067     #[inline]
2068     pub fn ty(&self) -> Ty<'tcx> {
2069         self.literal.ty()
2070     }
2071 }
2072
2073 impl<'tcx> ConstantKind<'tcx> {
2074     /// Returns `None` if the constant is not trivially safe for use in the type system.
2075     #[inline]
2076     pub fn const_for_ty(&self) -> Option<ty::Const<'tcx>> {
2077         match self {
2078             ConstantKind::Ty(c) => Some(*c),
2079             ConstantKind::Val(..) => None,
2080         }
2081     }
2082
2083     #[inline(always)]
2084     pub fn ty(&self) -> Ty<'tcx> {
2085         match self {
2086             ConstantKind::Ty(c) => c.ty(),
2087             ConstantKind::Val(_, ty) => *ty,
2088         }
2089     }
2090
2091     #[inline]
2092     pub fn try_to_value(self, tcx: TyCtxt<'tcx>) -> Option<interpret::ConstValue<'tcx>> {
2093         match self {
2094             ConstantKind::Ty(c) => match c.kind() {
2095                 ty::ConstKind::Value(valtree) => Some(tcx.valtree_to_const_val((c.ty(), valtree))),
2096                 _ => None,
2097             },
2098             ConstantKind::Val(val, _) => Some(val),
2099         }
2100     }
2101
2102     #[inline]
2103     pub fn try_to_scalar(self) -> Option<Scalar> {
2104         match self {
2105             ConstantKind::Ty(c) => match c.kind() {
2106                 ty::ConstKind::Value(valtree) => match valtree {
2107                     ty::ValTree::Leaf(scalar_int) => Some(Scalar::Int(scalar_int)),
2108                     ty::ValTree::Branch(_) => None,
2109                 },
2110                 _ => None,
2111             },
2112             ConstantKind::Val(val, _) => val.try_to_scalar(),
2113         }
2114     }
2115
2116     #[inline]
2117     pub fn try_to_scalar_int(self) -> Option<ScalarInt> {
2118         Some(self.try_to_scalar()?.assert_int())
2119     }
2120
2121     #[inline]
2122     pub fn try_to_bits(self, size: Size) -> Option<u128> {
2123         self.try_to_scalar_int()?.to_bits(size).ok()
2124     }
2125
2126     #[inline]
2127     pub fn try_to_bool(self) -> Option<bool> {
2128         self.try_to_scalar_int()?.try_into().ok()
2129     }
2130
2131     #[inline]
2132     pub fn eval(self, tcx: TyCtxt<'tcx>, param_env: ty::ParamEnv<'tcx>) -> Self {
2133         match self {
2134             Self::Ty(c) => {
2135                 if let Some(val) = c.kind().try_eval_for_mir(tcx, param_env) {
2136                     match val {
2137                         Ok(val) => Self::Val(val, c.ty()),
2138                         Err(_) => Self::Ty(tcx.const_error(self.ty())),
2139                     }
2140                 } else {
2141                     self
2142                 }
2143             }
2144             Self::Val(_, _) => self,
2145         }
2146     }
2147
2148     /// Panics if the value cannot be evaluated or doesn't contain a valid integer of the given type.
2149     #[inline]
2150     pub fn eval_bits(self, tcx: TyCtxt<'tcx>, param_env: ty::ParamEnv<'tcx>, ty: Ty<'tcx>) -> u128 {
2151         self.try_eval_bits(tcx, param_env, ty)
2152             .unwrap_or_else(|| bug!("expected bits of {:#?}, got {:#?}", ty, self))
2153     }
2154
2155     #[inline]
2156     pub fn try_eval_bits(
2157         &self,
2158         tcx: TyCtxt<'tcx>,
2159         param_env: ty::ParamEnv<'tcx>,
2160         ty: Ty<'tcx>,
2161     ) -> Option<u128> {
2162         match self {
2163             Self::Ty(ct) => ct.try_eval_bits(tcx, param_env, ty),
2164             Self::Val(val, t) => {
2165                 assert_eq!(*t, ty);
2166                 let size =
2167                     tcx.layout_of(param_env.with_reveal_all_normalized(tcx).and(ty)).ok()?.size;
2168                 val.try_to_bits(size)
2169             }
2170         }
2171     }
2172
2173     #[inline]
2174     pub fn try_eval_bool(&self, tcx: TyCtxt<'tcx>, param_env: ty::ParamEnv<'tcx>) -> Option<bool> {
2175         match self {
2176             Self::Ty(ct) => ct.try_eval_bool(tcx, param_env),
2177             Self::Val(val, _) => val.try_to_bool(),
2178         }
2179     }
2180
2181     #[inline]
2182     pub fn try_eval_usize(&self, tcx: TyCtxt<'tcx>, param_env: ty::ParamEnv<'tcx>) -> Option<u64> {
2183         match self {
2184             Self::Ty(ct) => ct.try_eval_usize(tcx, param_env),
2185             Self::Val(val, _) => val.try_to_machine_usize(tcx),
2186         }
2187     }
2188
2189     #[inline]
2190     pub fn from_value(val: ConstValue<'tcx>, ty: Ty<'tcx>) -> Self {
2191         Self::Val(val, ty)
2192     }
2193
2194     pub fn from_bits(
2195         tcx: TyCtxt<'tcx>,
2196         bits: u128,
2197         param_env_ty: ty::ParamEnvAnd<'tcx, Ty<'tcx>>,
2198     ) -> Self {
2199         let size = tcx
2200             .layout_of(param_env_ty)
2201             .unwrap_or_else(|e| {
2202                 bug!("could not compute layout for {:?}: {:?}", param_env_ty.value, e)
2203             })
2204             .size;
2205         let cv = ConstValue::Scalar(Scalar::from_uint(bits, size));
2206
2207         Self::Val(cv, param_env_ty.value)
2208     }
2209
2210     #[inline]
2211     pub fn from_bool(tcx: TyCtxt<'tcx>, v: bool) -> Self {
2212         let cv = ConstValue::from_bool(v);
2213         Self::Val(cv, tcx.types.bool)
2214     }
2215
2216     #[inline]
2217     pub fn zero_sized(ty: Ty<'tcx>) -> Self {
2218         let cv = ConstValue::ZeroSized;
2219         Self::Val(cv, ty)
2220     }
2221
2222     pub fn from_usize(tcx: TyCtxt<'tcx>, n: u64) -> Self {
2223         let ty = tcx.types.usize;
2224         Self::from_bits(tcx, n as u128, ty::ParamEnv::empty().and(ty))
2225     }
2226
2227     #[inline]
2228     pub fn from_scalar(_tcx: TyCtxt<'tcx>, s: Scalar, ty: Ty<'tcx>) -> Self {
2229         let val = ConstValue::Scalar(s);
2230         Self::Val(val, ty)
2231     }
2232
2233     /// Literals are converted to `ConstantKindVal`, const generic parameters are eagerly
2234     /// converted to a constant, everything else becomes `Unevaluated`.
2235     pub fn from_anon_const(
2236         tcx: TyCtxt<'tcx>,
2237         def_id: LocalDefId,
2238         param_env: ty::ParamEnv<'tcx>,
2239     ) -> Self {
2240         Self::from_opt_const_arg_anon_const(tcx, ty::WithOptConstParam::unknown(def_id), param_env)
2241     }
2242
2243     #[instrument(skip(tcx), level = "debug", ret)]
2244     pub fn from_inline_const(tcx: TyCtxt<'tcx>, def_id: LocalDefId) -> Self {
2245         let hir_id = tcx.hir().local_def_id_to_hir_id(def_id);
2246         let body_id = match tcx.hir().get(hir_id) {
2247             hir::Node::AnonConst(ac) => ac.body,
2248             _ => span_bug!(
2249                 tcx.def_span(def_id.to_def_id()),
2250                 "from_inline_const can only process anonymous constants"
2251             ),
2252         };
2253         let expr = &tcx.hir().body(body_id).value;
2254         let ty = tcx.typeck(def_id).node_type(hir_id);
2255
2256         let lit_input = match expr.kind {
2257             hir::ExprKind::Lit(ref lit) => Some(LitToConstInput { lit: &lit.node, ty, neg: false }),
2258             hir::ExprKind::Unary(hir::UnOp::Neg, ref expr) => match expr.kind {
2259                 hir::ExprKind::Lit(ref lit) => {
2260                     Some(LitToConstInput { lit: &lit.node, ty, neg: true })
2261                 }
2262                 _ => None,
2263             },
2264             _ => None,
2265         };
2266         if let Some(lit_input) = lit_input {
2267             // If an error occurred, ignore that it's a literal and leave reporting the error up to
2268             // mir.
2269             match tcx.at(expr.span).lit_to_mir_constant(lit_input) {
2270                 Ok(c) => return c,
2271                 Err(_) => {}
2272             }
2273         }
2274
2275         let typeck_root_def_id = tcx.typeck_root_def_id(def_id.to_def_id());
2276         let parent_substs =
2277             tcx.erase_regions(InternalSubsts::identity_for_item(tcx, typeck_root_def_id));
2278         let substs =
2279             ty::InlineConstSubsts::new(tcx, ty::InlineConstSubstsParts { parent_substs, ty })
2280                 .substs;
2281         debug_assert!(!substs.has_free_regions());
2282         Self::Ty(tcx.mk_const(ty::ConstS {
2283             kind: ty::ConstKind::Unevaluated(ty::Unevaluated {
2284                 def: ty::WithOptConstParam::unknown(def_id).to_global(),
2285                 substs,
2286                 promoted: None,
2287             }),
2288             ty,
2289         }))
2290     }
2291
2292     #[instrument(skip(tcx), level = "debug", ret)]
2293     fn from_opt_const_arg_anon_const(
2294         tcx: TyCtxt<'tcx>,
2295         def: ty::WithOptConstParam<LocalDefId>,
2296         param_env: ty::ParamEnv<'tcx>,
2297     ) -> Self {
2298         let body_id = match tcx.hir().get_by_def_id(def.did) {
2299             hir::Node::AnonConst(ac) => ac.body,
2300             _ => span_bug!(
2301                 tcx.def_span(def.did.to_def_id()),
2302                 "from_anon_const can only process anonymous constants"
2303             ),
2304         };
2305
2306         let expr = &tcx.hir().body(body_id).value;
2307         debug!(?expr);
2308
2309         // Unwrap a block, so that e.g. `{ P }` is recognised as a parameter. Const arguments
2310         // currently have to be wrapped in curly brackets, so it's necessary to special-case.
2311         let expr = match &expr.kind {
2312             hir::ExprKind::Block(block, _) if block.stmts.is_empty() && block.expr.is_some() => {
2313                 block.expr.as_ref().unwrap()
2314             }
2315             _ => expr,
2316         };
2317         debug!("expr.kind: {:?}", expr.kind);
2318
2319         let ty = tcx.type_of(def.def_id_for_type_of());
2320         debug!(?ty);
2321
2322         // FIXME(const_generics): We currently have to special case parameters because `min_const_generics`
2323         // does not provide the parents generics to anonymous constants. We still allow generic const
2324         // parameters by themselves however, e.g. `N`.  These constants would cause an ICE if we were to
2325         // ever try to substitute the generic parameters in their bodies.
2326         //
2327         // While this doesn't happen as these constants are always used as `ty::ConstKind::Param`, it does
2328         // cause issues if we were to remove that special-case and try to evaluate the constant instead.
2329         use hir::{def::DefKind::ConstParam, def::Res, ExprKind, Path, QPath};
2330         match expr.kind {
2331             ExprKind::Path(QPath::Resolved(_, &Path { res: Res::Def(ConstParam, def_id), .. })) => {
2332                 // Find the name and index of the const parameter by indexing the generics of
2333                 // the parent item and construct a `ParamConst`.
2334                 let hir_id = tcx.hir().local_def_id_to_hir_id(def_id.expect_local());
2335                 let item_id = tcx.hir().get_parent_node(hir_id);
2336                 let item_def_id = tcx.hir().local_def_id(item_id);
2337                 let generics = tcx.generics_of(item_def_id.to_def_id());
2338                 let index = generics.param_def_id_to_index[&def_id];
2339                 let name = tcx.hir().name(hir_id);
2340                 let ty_const = tcx.mk_const(ty::ConstS {
2341                     kind: ty::ConstKind::Param(ty::ParamConst::new(index, name)),
2342                     ty,
2343                 });
2344                 debug!(?ty_const);
2345
2346                 return Self::Ty(ty_const);
2347             }
2348             _ => {}
2349         }
2350
2351         let hir_id = tcx.hir().local_def_id_to_hir_id(def.did);
2352         let parent_substs = if let Some(parent_hir_id) = tcx.hir().find_parent_node(hir_id) {
2353             if let Some(parent_did) = tcx.hir().opt_local_def_id(parent_hir_id) {
2354                 InternalSubsts::identity_for_item(tcx, parent_did.to_def_id())
2355             } else {
2356                 tcx.mk_substs(Vec::<GenericArg<'tcx>>::new().into_iter())
2357             }
2358         } else {
2359             tcx.mk_substs(Vec::<GenericArg<'tcx>>::new().into_iter())
2360         };
2361         debug!(?parent_substs);
2362
2363         let did = def.did.to_def_id();
2364         let child_substs = InternalSubsts::identity_for_item(tcx, did);
2365         let substs = tcx.mk_substs(parent_substs.into_iter().chain(child_substs.into_iter()));
2366         debug!(?substs);
2367
2368         let hir_id = tcx.hir().local_def_id_to_hir_id(def.did);
2369         let span = tcx.hir().span(hir_id);
2370         let uneval = ty::Unevaluated::new(def.to_global(), substs);
2371         debug!(?span, ?param_env);
2372
2373         match tcx.const_eval_resolve(param_env, uneval, Some(span)) {
2374             Ok(val) => {
2375                 debug!("evaluated const value");
2376                 Self::Val(val, ty)
2377             }
2378             Err(_) => {
2379                 debug!("error encountered during evaluation");
2380                 // Error was handled in `const_eval_resolve`. Here we just create a
2381                 // new unevaluated const and error hard later in codegen
2382                 Self::Ty(tcx.mk_const(ty::ConstS {
2383                     kind: ty::ConstKind::Unevaluated(ty::Unevaluated {
2384                         def: def.to_global(),
2385                         substs: InternalSubsts::identity_for_item(tcx, def.did.to_def_id()),
2386                         promoted: None,
2387                     }),
2388                     ty,
2389                 }))
2390             }
2391         }
2392     }
2393
2394     pub fn from_const(c: ty::Const<'tcx>, tcx: TyCtxt<'tcx>) -> Self {
2395         match c.kind() {
2396             ty::ConstKind::Value(valtree) => {
2397                 let const_val = tcx.valtree_to_const_val((c.ty(), valtree));
2398                 Self::Val(const_val, c.ty())
2399             }
2400             _ => Self::Ty(c),
2401         }
2402     }
2403 }
2404
2405 /// A collection of projections into user types.
2406 ///
2407 /// They are projections because a binding can occur a part of a
2408 /// parent pattern that has been ascribed a type.
2409 ///
2410 /// Its a collection because there can be multiple type ascriptions on
2411 /// the path from the root of the pattern down to the binding itself.
2412 ///
2413 /// An example:
2414 ///
2415 /// ```ignore (illustrative)
2416 /// struct S<'a>((i32, &'a str), String);
2417 /// let S((_, w): (i32, &'static str), _): S = ...;
2418 /// //    ------  ^^^^^^^^^^^^^^^^^^^ (1)
2419 /// //  ---------------------------------  ^ (2)
2420 /// ```
2421 ///
2422 /// The highlights labelled `(1)` show the subpattern `(_, w)` being
2423 /// ascribed the type `(i32, &'static str)`.
2424 ///
2425 /// The highlights labelled `(2)` show the whole pattern being
2426 /// ascribed the type `S`.
2427 ///
2428 /// In this example, when we descend to `w`, we will have built up the
2429 /// following two projected types:
2430 ///
2431 ///   * base: `S`,                   projection: `(base.0).1`
2432 ///   * base: `(i32, &'static str)`, projection: `base.1`
2433 ///
2434 /// The first will lead to the constraint `w: &'1 str` (for some
2435 /// inferred region `'1`). The second will lead to the constraint `w:
2436 /// &'static str`.
2437 #[derive(Clone, Debug, TyEncodable, TyDecodable, HashStable, TypeFoldable, TypeVisitable)]
2438 pub struct UserTypeProjections {
2439     pub contents: Vec<(UserTypeProjection, Span)>,
2440 }
2441
2442 impl<'tcx> UserTypeProjections {
2443     pub fn none() -> Self {
2444         UserTypeProjections { contents: vec![] }
2445     }
2446
2447     pub fn is_empty(&self) -> bool {
2448         self.contents.is_empty()
2449     }
2450
2451     pub fn projections_and_spans(
2452         &self,
2453     ) -> impl Iterator<Item = &(UserTypeProjection, Span)> + ExactSizeIterator {
2454         self.contents.iter()
2455     }
2456
2457     pub fn projections(&self) -> impl Iterator<Item = &UserTypeProjection> + ExactSizeIterator {
2458         self.contents.iter().map(|&(ref user_type, _span)| user_type)
2459     }
2460
2461     pub fn push_projection(mut self, user_ty: &UserTypeProjection, span: Span) -> Self {
2462         self.contents.push((user_ty.clone(), span));
2463         self
2464     }
2465
2466     fn map_projections(
2467         mut self,
2468         mut f: impl FnMut(UserTypeProjection) -> UserTypeProjection,
2469     ) -> Self {
2470         self.contents = self.contents.into_iter().map(|(proj, span)| (f(proj), span)).collect();
2471         self
2472     }
2473
2474     pub fn index(self) -> Self {
2475         self.map_projections(|pat_ty_proj| pat_ty_proj.index())
2476     }
2477
2478     pub fn subslice(self, from: u64, to: u64) -> Self {
2479         self.map_projections(|pat_ty_proj| pat_ty_proj.subslice(from, to))
2480     }
2481
2482     pub fn deref(self) -> Self {
2483         self.map_projections(|pat_ty_proj| pat_ty_proj.deref())
2484     }
2485
2486     pub fn leaf(self, field: Field) -> Self {
2487         self.map_projections(|pat_ty_proj| pat_ty_proj.leaf(field))
2488     }
2489
2490     pub fn variant(self, adt_def: AdtDef<'tcx>, variant_index: VariantIdx, field: Field) -> Self {
2491         self.map_projections(|pat_ty_proj| pat_ty_proj.variant(adt_def, variant_index, field))
2492     }
2493 }
2494
2495 /// Encodes the effect of a user-supplied type annotation on the
2496 /// subcomponents of a pattern. The effect is determined by applying the
2497 /// given list of projections to some underlying base type. Often,
2498 /// the projection element list `projs` is empty, in which case this
2499 /// directly encodes a type in `base`. But in the case of complex patterns with
2500 /// subpatterns and bindings, we want to apply only a *part* of the type to a variable,
2501 /// in which case the `projs` vector is used.
2502 ///
2503 /// Examples:
2504 ///
2505 /// * `let x: T = ...` -- here, the `projs` vector is empty.
2506 ///
2507 /// * `let (x, _): T = ...` -- here, the `projs` vector would contain
2508 ///   `field[0]` (aka `.0`), indicating that the type of `s` is
2509 ///   determined by finding the type of the `.0` field from `T`.
2510 #[derive(Clone, Debug, TyEncodable, TyDecodable, Hash, HashStable, PartialEq)]
2511 pub struct UserTypeProjection {
2512     pub base: UserTypeAnnotationIndex,
2513     pub projs: Vec<ProjectionKind>,
2514 }
2515
2516 impl Copy for ProjectionKind {}
2517
2518 impl UserTypeProjection {
2519     pub(crate) fn index(mut self) -> Self {
2520         self.projs.push(ProjectionElem::Index(()));
2521         self
2522     }
2523
2524     pub(crate) fn subslice(mut self, from: u64, to: u64) -> Self {
2525         self.projs.push(ProjectionElem::Subslice { from, to, from_end: true });
2526         self
2527     }
2528
2529     pub(crate) fn deref(mut self) -> Self {
2530         self.projs.push(ProjectionElem::Deref);
2531         self
2532     }
2533
2534     pub(crate) fn leaf(mut self, field: Field) -> Self {
2535         self.projs.push(ProjectionElem::Field(field, ()));
2536         self
2537     }
2538
2539     pub(crate) fn variant(
2540         mut self,
2541         adt_def: AdtDef<'_>,
2542         variant_index: VariantIdx,
2543         field: Field,
2544     ) -> Self {
2545         self.projs.push(ProjectionElem::Downcast(
2546             Some(adt_def.variant(variant_index).name),
2547             variant_index,
2548         ));
2549         self.projs.push(ProjectionElem::Field(field, ()));
2550         self
2551     }
2552 }
2553
2554 TrivialTypeTraversalAndLiftImpls! { ProjectionKind, }
2555
2556 impl<'tcx> TypeFoldable<'tcx> for UserTypeProjection {
2557     fn try_fold_with<F: FallibleTypeFolder<'tcx>>(self, folder: &mut F) -> Result<Self, F::Error> {
2558         Ok(UserTypeProjection {
2559             base: self.base.try_fold_with(folder)?,
2560             projs: self.projs.try_fold_with(folder)?,
2561         })
2562     }
2563 }
2564
2565 impl<'tcx> TypeVisitable<'tcx> for UserTypeProjection {
2566     fn visit_with<Vs: TypeVisitor<'tcx>>(&self, visitor: &mut Vs) -> ControlFlow<Vs::BreakTy> {
2567         self.base.visit_with(visitor)
2568         // Note: there's nothing in `self.proj` to visit.
2569     }
2570 }
2571
2572 rustc_index::newtype_index! {
2573     pub struct Promoted {
2574         derive [HashStable]
2575         DEBUG_FORMAT = "promoted[{}]"
2576     }
2577 }
2578
2579 impl<'tcx> Debug for Constant<'tcx> {
2580     fn fmt(&self, fmt: &mut Formatter<'_>) -> fmt::Result {
2581         write!(fmt, "{}", self)
2582     }
2583 }
2584
2585 impl<'tcx> Display for Constant<'tcx> {
2586     fn fmt(&self, fmt: &mut Formatter<'_>) -> fmt::Result {
2587         match self.ty().kind() {
2588             ty::FnDef(..) => {}
2589             _ => write!(fmt, "const ")?,
2590         }
2591         Display::fmt(&self.literal, fmt)
2592     }
2593 }
2594
2595 impl<'tcx> Display for ConstantKind<'tcx> {
2596     fn fmt(&self, fmt: &mut Formatter<'_>) -> fmt::Result {
2597         match *self {
2598             ConstantKind::Ty(c) => pretty_print_const(c, fmt, true),
2599             ConstantKind::Val(val, ty) => pretty_print_const_value(val, ty, fmt, true),
2600         }
2601     }
2602 }
2603
2604 fn pretty_print_const<'tcx>(
2605     c: ty::Const<'tcx>,
2606     fmt: &mut Formatter<'_>,
2607     print_types: bool,
2608 ) -> fmt::Result {
2609     use crate::ty::print::PrettyPrinter;
2610     ty::tls::with(|tcx| {
2611         let literal = tcx.lift(c).unwrap();
2612         let mut cx = FmtPrinter::new(tcx, Namespace::ValueNS);
2613         cx.print_alloc_ids = true;
2614         let cx = cx.pretty_print_const(literal, print_types)?;
2615         fmt.write_str(&cx.into_buffer())?;
2616         Ok(())
2617     })
2618 }
2619
2620 fn pretty_print_byte_str(fmt: &mut Formatter<'_>, byte_str: &[u8]) -> fmt::Result {
2621     write!(fmt, "b\"{}\"", byte_str.escape_ascii())
2622 }
2623
2624 fn comma_sep<'tcx>(fmt: &mut Formatter<'_>, elems: Vec<ConstantKind<'tcx>>) -> fmt::Result {
2625     let mut first = true;
2626     for elem in elems {
2627         if !first {
2628             fmt.write_str(", ")?;
2629         }
2630         fmt.write_str(&format!("{}", elem))?;
2631         first = false;
2632     }
2633     Ok(())
2634 }
2635
2636 // FIXME: Move that into `mir/pretty.rs`.
2637 fn pretty_print_const_value<'tcx>(
2638     ct: ConstValue<'tcx>,
2639     ty: Ty<'tcx>,
2640     fmt: &mut Formatter<'_>,
2641     print_ty: bool,
2642 ) -> fmt::Result {
2643     use crate::ty::print::PrettyPrinter;
2644
2645     ty::tls::with(|tcx| {
2646         let ct = tcx.lift(ct).unwrap();
2647         let ty = tcx.lift(ty).unwrap();
2648
2649         if tcx.sess.verbose() {
2650             fmt.write_str(&format!("ConstValue({:?}: {})", ct, ty))?;
2651             return Ok(());
2652         }
2653
2654         let u8_type = tcx.types.u8;
2655         match (ct, ty.kind()) {
2656             // Byte/string slices, printed as (byte) string literals.
2657             (ConstValue::Slice { data, start, end }, ty::Ref(_, inner, _)) => {
2658                 match inner.kind() {
2659                     ty::Slice(t) => {
2660                         if *t == u8_type {
2661                             // The `inspect` here is okay since we checked the bounds, and `u8` carries
2662                             // no provenance (we have an active slice reference here). We don't use
2663                             // this result to affect interpreter execution.
2664                             let byte_str = data
2665                                 .inner()
2666                                 .inspect_with_uninit_and_ptr_outside_interpreter(start..end);
2667                             pretty_print_byte_str(fmt, byte_str)?;
2668                             return Ok(());
2669                         }
2670                     }
2671                     ty::Str => {
2672                         // The `inspect` here is okay since we checked the bounds, and `str` carries
2673                         // no provenance (we have an active `str` reference here). We don't use this
2674                         // result to affect interpreter execution.
2675                         let slice = data
2676                             .inner()
2677                             .inspect_with_uninit_and_ptr_outside_interpreter(start..end);
2678                         fmt.write_str(&format!("{:?}", String::from_utf8_lossy(slice)))?;
2679                         return Ok(());
2680                     }
2681                     _ => {}
2682                 }
2683             }
2684             (ConstValue::ByRef { alloc, offset }, ty::Array(t, n)) if *t == u8_type => {
2685                 let n = n.kind().try_to_bits(tcx.data_layout.pointer_size).unwrap();
2686                 // cast is ok because we already checked for pointer size (32 or 64 bit) above
2687                 let range = AllocRange { start: offset, size: Size::from_bytes(n) };
2688                 let byte_str = alloc.inner().get_bytes_strip_provenance(&tcx, range).unwrap();
2689                 fmt.write_str("*")?;
2690                 pretty_print_byte_str(fmt, byte_str)?;
2691                 return Ok(());
2692             }
2693             // Aggregates, printed as array/tuple/struct/variant construction syntax.
2694             //
2695             // NB: the `has_param_types_or_consts` check ensures that we can use
2696             // the `destructure_const` query with an empty `ty::ParamEnv` without
2697             // introducing ICEs (e.g. via `layout_of`) from missing bounds.
2698             // E.g. `transmute([0usize; 2]): (u8, *mut T)` needs to know `T: Sized`
2699             // to be able to destructure the tuple into `(0u8, *mut T)
2700             //
2701             // FIXME(eddyb) for `--emit=mir`/`-Z dump-mir`, we should provide the
2702             // correct `ty::ParamEnv` to allow printing *all* constant values.
2703             (_, ty::Array(..) | ty::Tuple(..) | ty::Adt(..)) if !ty.has_param_types_or_consts() => {
2704                 let ct = tcx.lift(ct).unwrap();
2705                 let ty = tcx.lift(ty).unwrap();
2706                 if let Some(contents) = tcx.try_destructure_mir_constant(
2707                     ty::ParamEnv::reveal_all().and(ConstantKind::Val(ct, ty)),
2708                 ) {
2709                     let fields = contents.fields.iter().copied().collect::<Vec<_>>();
2710                     match *ty.kind() {
2711                         ty::Array(..) => {
2712                             fmt.write_str("[")?;
2713                             comma_sep(fmt, fields)?;
2714                             fmt.write_str("]")?;
2715                         }
2716                         ty::Tuple(..) => {
2717                             fmt.write_str("(")?;
2718                             comma_sep(fmt, fields)?;
2719                             if contents.fields.len() == 1 {
2720                                 fmt.write_str(",")?;
2721                             }
2722                             fmt.write_str(")")?;
2723                         }
2724                         ty::Adt(def, _) if def.variants().is_empty() => {
2725                             fmt.write_str(&format!("{{unreachable(): {}}}", ty))?;
2726                         }
2727                         ty::Adt(def, substs) => {
2728                             let variant_idx = contents
2729                                 .variant
2730                                 .expect("destructed mir constant of adt without variant idx");
2731                             let variant_def = &def.variant(variant_idx);
2732                             let substs = tcx.lift(substs).unwrap();
2733                             let mut cx = FmtPrinter::new(tcx, Namespace::ValueNS);
2734                             cx.print_alloc_ids = true;
2735                             let cx = cx.print_value_path(variant_def.def_id, substs)?;
2736                             fmt.write_str(&cx.into_buffer())?;
2737
2738                             match variant_def.ctor_kind {
2739                                 CtorKind::Const => {}
2740                                 CtorKind::Fn => {
2741                                     fmt.write_str("(")?;
2742                                     comma_sep(fmt, fields)?;
2743                                     fmt.write_str(")")?;
2744                                 }
2745                                 CtorKind::Fictive => {
2746                                     fmt.write_str(" {{ ")?;
2747                                     let mut first = true;
2748                                     for (field_def, field) in iter::zip(&variant_def.fields, fields)
2749                                     {
2750                                         if !first {
2751                                             fmt.write_str(", ")?;
2752                                         }
2753                                         fmt.write_str(&format!("{}: {}", field_def.name, field))?;
2754                                         first = false;
2755                                     }
2756                                     fmt.write_str(" }}")?;
2757                                 }
2758                             }
2759                         }
2760                         _ => unreachable!(),
2761                     }
2762                     return Ok(());
2763                 } else {
2764                     // Fall back to debug pretty printing for invalid constants.
2765                     fmt.write_str(&format!("{:?}", ct))?;
2766                     if print_ty {
2767                         fmt.write_str(&format!(": {}", ty))?;
2768                     }
2769                     return Ok(());
2770                 };
2771             }
2772             (ConstValue::Scalar(scalar), _) => {
2773                 let mut cx = FmtPrinter::new(tcx, Namespace::ValueNS);
2774                 cx.print_alloc_ids = true;
2775                 let ty = tcx.lift(ty).unwrap();
2776                 cx = cx.pretty_print_const_scalar(scalar, ty, print_ty)?;
2777                 fmt.write_str(&cx.into_buffer())?;
2778                 return Ok(());
2779             }
2780             (ConstValue::ZeroSized, ty::FnDef(d, s)) => {
2781                 let mut cx = FmtPrinter::new(tcx, Namespace::ValueNS);
2782                 cx.print_alloc_ids = true;
2783                 let cx = cx.print_value_path(*d, s)?;
2784                 fmt.write_str(&cx.into_buffer())?;
2785                 return Ok(());
2786             }
2787             // FIXME(oli-obk): also pretty print arrays and other aggregate constants by reading
2788             // their fields instead of just dumping the memory.
2789             _ => {}
2790         }
2791         // fallback
2792         fmt.write_str(&format!("{:?}", ct))?;
2793         if print_ty {
2794             fmt.write_str(&format!(": {}", ty))?;
2795         }
2796         Ok(())
2797     })
2798 }
2799
2800 /// `Location` represents the position of the start of the statement; or, if
2801 /// `statement_index` equals the number of statements, then the start of the
2802 /// terminator.
2803 #[derive(Copy, Clone, PartialEq, Eq, Hash, Ord, PartialOrd, HashStable)]
2804 pub struct Location {
2805     /// The block that the location is within.
2806     pub block: BasicBlock,
2807
2808     pub statement_index: usize,
2809 }
2810
2811 impl fmt::Debug for Location {
2812     fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
2813         write!(fmt, "{:?}[{}]", self.block, self.statement_index)
2814     }
2815 }
2816
2817 impl Location {
2818     pub const START: Location = Location { block: START_BLOCK, statement_index: 0 };
2819
2820     /// Returns the location immediately after this one within the enclosing block.
2821     ///
2822     /// Note that if this location represents a terminator, then the
2823     /// resulting location would be out of bounds and invalid.
2824     pub fn successor_within_block(&self) -> Location {
2825         Location { block: self.block, statement_index: self.statement_index + 1 }
2826     }
2827
2828     /// Returns `true` if `other` is earlier in the control flow graph than `self`.
2829     pub fn is_predecessor_of<'tcx>(&self, other: Location, body: &Body<'tcx>) -> bool {
2830         // If we are in the same block as the other location and are an earlier statement
2831         // then we are a predecessor of `other`.
2832         if self.block == other.block && self.statement_index < other.statement_index {
2833             return true;
2834         }
2835
2836         let predecessors = body.basic_blocks.predecessors();
2837
2838         // If we're in another block, then we want to check that block is a predecessor of `other`.
2839         let mut queue: Vec<BasicBlock> = predecessors[other.block].to_vec();
2840         let mut visited = FxHashSet::default();
2841
2842         while let Some(block) = queue.pop() {
2843             // If we haven't visited this block before, then make sure we visit its predecessors.
2844             if visited.insert(block) {
2845                 queue.extend(predecessors[block].iter().cloned());
2846             } else {
2847                 continue;
2848             }
2849
2850             // If we found the block that `self` is in, then we are a predecessor of `other` (since
2851             // we found that block by looking at the predecessors of `other`).
2852             if self.block == block {
2853                 return true;
2854             }
2855         }
2856
2857         false
2858     }
2859
2860     pub fn dominates(&self, other: Location, dominators: &Dominators<BasicBlock>) -> bool {
2861         if self.block == other.block {
2862             self.statement_index <= other.statement_index
2863         } else {
2864             dominators.is_dominated_by(other.block, self.block)
2865         }
2866     }
2867 }
2868
2869 // Some nodes are used a lot. Make sure they don't unintentionally get bigger.
2870 #[cfg(all(target_arch = "x86_64", target_pointer_width = "64"))]
2871 mod size_asserts {
2872     use super::*;
2873     use rustc_data_structures::static_assert_size;
2874     // These are in alphabetical order, which is easy to maintain.
2875     static_assert_size!(BasicBlockData<'_>, 144);
2876     static_assert_size!(LocalDecl<'_>, 56);
2877     static_assert_size!(Statement<'_>, 32);
2878     static_assert_size!(StatementKind<'_>, 16);
2879     static_assert_size!(Terminator<'_>, 112);
2880     static_assert_size!(TerminatorKind<'_>, 96);
2881 }