src/librustc/mir/mod.rs

   1 // ignore-tidy-filelength
   2
   3 //! MIR datatypes and passes. See the [rustc guide] for more info.
   4 //!
   5 //! [rustc guide]: https://rust-lang.github.io/rustc-guide/mir/index.html
   6
   7 use crate::hir::def::{CtorKind, Namespace};
   8 use crate::hir::def_id::DefId;
   9 use crate::hir::{self, GeneratorKind};
  10 use crate::mir::interpret::{GlobalAlloc, PanicInfo, Scalar};
  11 use crate::mir::visit::MirVisitable;
  12 use crate::ty::adjustment::PointerCast;
  13 use crate::ty::fold::{TypeFoldable, TypeFolder, TypeVisitor};
  14 use crate::ty::layout::VariantIdx;
  15 use crate::ty::print::{FmtPrinter, Printer};
  16 use crate::ty::subst::{Subst, SubstsRef};
  17 use crate::ty::{
  18     self, AdtDef, CanonicalUserTypeAnnotations, List, Region, Ty, TyCtxt, UserTypeAnnotationIndex,
  19 };
  20
  21 use polonius_engine::Atom;
  22 use rustc_index::bit_set::BitMatrix;
  23 use rustc_data_structures::fx::FxHashSet;
  24 use rustc_data_structures::graph::dominators::{dominators, Dominators};
  25 use rustc_data_structures::graph::{self, GraphPredecessors, GraphSuccessors};
  26 use rustc_index::vec::{Idx, IndexVec};
  27 use rustc_data_structures::sync::Lrc;
  28 use rustc_macros::HashStable;
  29 use rustc_serialize::{Encodable, Decodable};
  30 use smallvec::SmallVec;
  31 use std::borrow::Cow;
  32 use std::fmt::{self, Debug, Display, Formatter, Write};
  33 use std::ops::{Index, IndexMut};
  34 use std::slice;
  35 use std::vec::IntoIter;
  36 use std::{iter, mem, option, u32};
  37 use syntax::ast::Name;
  38 use syntax::symbol::Symbol;
  39 use syntax_pos::{Span, DUMMY_SP};
  40
  41 pub use crate::mir::interpret::AssertMessage;
  42
  43 pub mod interpret;
  44 pub mod mono;
  45 pub mod tcx;
  46 pub mod traversal;
  47 pub mod visit;
  48
  49 /// Types for locals
  50 type LocalDecls<'tcx> = IndexVec<Local, LocalDecl<'tcx>>;
  51
  52 pub trait HasLocalDecls<'tcx> {
  53     fn local_decls(&self) -> &LocalDecls<'tcx>;
  54 }
  55
  56 impl<'tcx> HasLocalDecls<'tcx> for LocalDecls<'tcx> {
  57     fn local_decls(&self) -> &LocalDecls<'tcx> {
  58         self
  59     }
  60 }
  61
  62 impl<'tcx> HasLocalDecls<'tcx> for Body<'tcx> {
  63     fn local_decls(&self) -> &LocalDecls<'tcx> {
  64         &self.local_decls
  65     }
  66 }
  67
  68 /// The various "big phases" that MIR goes through.
  69 ///
  70 /// Warning: ordering of variants is significant.
  71 #[derive(Copy, Clone, RustcEncodable, RustcDecodable, HashStable,
  72          Debug, PartialEq, Eq, PartialOrd, Ord)]
  73 pub enum MirPhase {
  74     Build = 0,
  75     Const = 1,
  76     Validated = 2,
  77     Optimized = 3,
  78 }
  79
  80 impl MirPhase {
  81     /// Gets the index of the current MirPhase within the set of all `MirPhase`s.
  82     pub fn phase_index(&self) -> usize {
  83         *self as usize
  84     }
  85 }
  86
  87 /// The lowered representation of a single function.
  88 #[derive(Clone, RustcEncodable, RustcDecodable, Debug, HashStable, TypeFoldable)]
  89 pub struct Body<'tcx> {
  90     /// A list of basic blocks. References to basic block use a newtyped index type `BasicBlock`
  91     /// that indexes into this vector.
  92     basic_blocks: IndexVec<BasicBlock, BasicBlockData<'tcx>>,
  93
  94     /// Records how far through the "desugaring and optimization" process this particular
  95     /// MIR has traversed. This is particularly useful when inlining, since in that context
  96     /// we instantiate the promoted constants and add them to our promoted vector -- but those
  97     /// promoted items have already been optimized, whereas ours have not. This field allows
  98     /// us to see the difference and forego optimization on the inlined promoted items.
  99     pub phase: MirPhase,
 100
 101     /// A list of source scopes; these are referenced by statements
 102     /// and used for debuginfo. Indexed by a `SourceScope`.
 103     pub source_scopes: IndexVec<SourceScope, SourceScopeData>,
 104
 105     /// The yield type of the function, if it is a generator.
 106     pub yield_ty: Option<Ty<'tcx>>,
 107
 108     /// Generator drop glue.
 109     pub generator_drop: Option<Box<Body<'tcx>>>,
 110
 111     /// The layout of a generator. Produced by the state transformation.
 112     pub generator_layout: Option<GeneratorLayout<'tcx>>,
 113
 114     /// If this is a generator then record the type of source expression that caused this generator
 115     /// to be created.
 116     pub generator_kind: Option<GeneratorKind>,
 117
 118     /// Declarations of locals.
 119     ///
 120     /// The first local is the return value pointer, followed by `arg_count`
 121     /// locals for the function arguments, followed by any user-declared
 122     /// variables and temporaries.
 123     pub local_decls: LocalDecls<'tcx>,
 124
 125     /// User type annotations.
 126     pub user_type_annotations: CanonicalUserTypeAnnotations<'tcx>,
 127
 128     /// The number of arguments this function takes.
 129     ///
 130     /// Starting at local 1, `arg_count` locals will be provided by the caller
 131     /// and can be assumed to be initialized.
 132     ///
 133     /// If this MIR was built for a constant, this will be 0.
 134     pub arg_count: usize,
 135
 136     /// Mark an argument local (which must be a tuple) as getting passed as
 137     /// its individual components at the LLVM level.
 138     ///
 139     /// This is used for the "rust-call" ABI.
 140     pub spread_arg: Option<Local>,
 141
 142     /// Debug information pertaining to user variables, including captures.
 143     pub var_debug_info: Vec<VarDebugInfo<'tcx>>,
 144
 145     /// Mark this MIR of a const context other than const functions as having converted a `&&` or
 146     /// `||` expression into `&` or `|` respectively. This is problematic because if we ever stop
 147     /// this conversion from happening and use short circuiting, we will cause the following code
 148     /// to change the value of `x`: `let mut x = 42; false && { x = 55; true };`
 149     ///
 150     /// List of places where control flow was destroyed. Used for error reporting.
 151     pub control_flow_destroyed: Vec<(Span, String)>,
 152
 153     /// A span representing this MIR, for error reporting.
 154     pub span: Span,
 155
 156     /// A cache for various calculations.
 157     predecessors_cache: Option<IndexVec<BasicBlock, Vec<BasicBlock>>>,
 158 }
 159
 160 impl<'tcx> Body<'tcx> {
 161     pub fn new(
 162         basic_blocks: IndexVec<BasicBlock, BasicBlockData<'tcx>>,
 163         source_scopes: IndexVec<SourceScope, SourceScopeData>,
 164         local_decls: LocalDecls<'tcx>,
 165         user_type_annotations: CanonicalUserTypeAnnotations<'tcx>,
 166         arg_count: usize,
 167         var_debug_info: Vec<VarDebugInfo<'tcx>>,
 168         span: Span,
 169         control_flow_destroyed: Vec<(Span, String)>,
 170         generator_kind : Option<GeneratorKind>,
 171     ) -> Self {
 172         // We need `arg_count` locals, and one for the return place.
 173         assert!(
 174             local_decls.len() >= arg_count + 1,
 175             "expected at least {} locals, got {}",
 176             arg_count + 1,
 177             local_decls.len()
 178         );
 179
 180         Body {
 181             phase: MirPhase::Build,
 182             basic_blocks,
 183             source_scopes,
 184             yield_ty: None,
 185             generator_drop: None,
 186             generator_layout: None,
 187             generator_kind,
 188             local_decls,
 189             user_type_annotations,
 190             arg_count,
 191             spread_arg: None,
 192             var_debug_info,
 193             span,
 194             predecessors_cache: None,
 195             control_flow_destroyed,
 196         }
 197     }
 198
 199     #[inline]
 200     pub fn basic_blocks(&self) -> &IndexVec<BasicBlock, BasicBlockData<'tcx>> {
 201         &self.basic_blocks
 202     }
 203
 204     #[inline]
 205     pub fn basic_blocks_mut(&mut self) -> &mut IndexVec<BasicBlock, BasicBlockData<'tcx>> {
 206         debug!("Clearing predecessors cache at: {:?}", self.span.data());
 207         self.predecessors_cache = None;
 208         &mut self.basic_blocks
 209     }
 210
 211     #[inline]
 212     pub fn basic_blocks_and_local_decls_mut(
 213         &mut self,
 214     ) -> (&mut IndexVec<BasicBlock, BasicBlockData<'tcx>>, &mut LocalDecls<'tcx>) {
 215         (&mut self.basic_blocks, &mut self.local_decls)
 216     }
 217
 218     #[inline]
 219     pub fn unwrap_predecessors(&self) -> &IndexVec<BasicBlock, Vec<BasicBlock>> {
 220         assert!(self.predecessors_cache.is_some(), "Expected predecessors_cache to be `Some(...)` for block at: {:?}", self.span.data());
 221         self.predecessors_cache.as_ref().unwrap()
 222     }
 223
 224     #[inline]
 225     pub fn ensure_predecessors(&mut self) {
 226         if self.predecessors_cache.is_none() {
 227             let mut result = IndexVec::from_elem(vec![], self.basic_blocks());
 228             for (bb, data) in self.basic_blocks().iter_enumerated() {
 229                 if let Some(ref term) = data.terminator {
 230                     for &tgt in term.successors() {
 231                         result[tgt].push(bb);
 232                     }
 233                 }
 234             }
 235
 236             self.predecessors_cache = Some(result)
 237         }
 238     }
 239
 240     #[inline]
 241     /// This will recompute the predecessors cache if it is not available
 242     pub fn predecessors(&mut self) -> &IndexVec<BasicBlock, Vec<BasicBlock>> {
 243         self.ensure_predecessors();
 244         self.predecessors_cache.as_ref().unwrap()
 245     }
 246
 247     #[inline]
 248     pub fn predecessors_for(&self, bb: BasicBlock) -> &[BasicBlock] {
 249         &self.unwrap_predecessors()[bb]
 250     }
 251
 252     #[inline]
 253     pub fn predecessor_locations(&self, loc: Location) -> impl Iterator<Item = Location> + '_ {
 254         let if_zero_locations = if loc.statement_index == 0 {
 255             let predecessor_blocks = self.predecessors_for(loc.block);
 256             let num_predecessor_blocks = predecessor_blocks.len();
 257             Some(
 258                 (0..num_predecessor_blocks)
 259                     .map(move |i| predecessor_blocks[i])
 260                     .map(move |bb| self.terminator_loc(bb)),
 261             )
 262         } else {
 263             None
 264         };
 265
 266         let if_not_zero_locations = if loc.statement_index == 0 {
 267             None
 268         } else {
 269             Some(Location { block: loc.block, statement_index: loc.statement_index - 1 })
 270         };
 271
 272         if_zero_locations.into_iter().flatten().chain(if_not_zero_locations)
 273     }
 274
 275     #[inline]
 276     pub fn dominators(&self) -> Dominators<BasicBlock> {
 277         dominators(self)
 278     }
 279
 280     /// Returns `true` if a cycle exists in the control-flow graph that is reachable from the
 281     /// `START_BLOCK`.
 282     pub fn is_cfg_cyclic(&self) -> bool {
 283         graph::is_cyclic(self)
 284     }
 285
 286     #[inline]
 287     pub fn local_kind(&self, local: Local) -> LocalKind {
 288         let index = local.as_usize();
 289         if index == 0 {
 290             debug_assert!(
 291                 self.local_decls[local].mutability == Mutability::Mut,
 292                 "return place should be mutable"
 293             );
 294
 295             LocalKind::ReturnPointer
 296         } else if index < self.arg_count + 1 {
 297             LocalKind::Arg
 298         } else if self.local_decls[local].is_user_variable() {
 299             LocalKind::Var
 300         } else {
 301             LocalKind::Temp
 302         }
 303     }
 304
 305     /// Returns an iterator over all temporaries.
 306     #[inline]
 307     pub fn temps_iter<'a>(&'a self) -> impl Iterator<Item = Local> + 'a {
 308         (self.arg_count + 1..self.local_decls.len()).filter_map(move |index| {
 309             let local = Local::new(index);
 310             if self.local_decls[local].is_user_variable() {
 311                 None
 312             } else {
 313                 Some(local)
 314             }
 315         })
 316     }
 317
 318     /// Returns an iterator over all user-declared locals.
 319     #[inline]
 320     pub fn vars_iter<'a>(&'a self) -> impl Iterator<Item = Local> + 'a {
 321         (self.arg_count + 1..self.local_decls.len()).filter_map(move |index| {
 322             let local = Local::new(index);
 323             if self.local_decls[local].is_user_variable() {
 324                 Some(local)
 325             } else {
 326                 None
 327             }
 328         })
 329     }
 330
 331     /// Returns an iterator over all user-declared mutable locals.
 332     #[inline]
 333     pub fn mut_vars_iter<'a>(&'a self) -> impl Iterator<Item = Local> + 'a {
 334         (self.arg_count + 1..self.local_decls.len()).filter_map(move |index| {
 335             let local = Local::new(index);
 336             let decl = &self.local_decls[local];
 337             if decl.is_user_variable() && decl.mutability == Mutability::Mut {
 338                 Some(local)
 339             } else {
 340                 None
 341             }
 342         })
 343     }
 344
 345     /// Returns an iterator over all user-declared mutable arguments and locals.
 346     #[inline]
 347     pub fn mut_vars_and_args_iter<'a>(&'a self) -> impl Iterator<Item = Local> + 'a {
 348         (1..self.local_decls.len()).filter_map(move |index| {
 349             let local = Local::new(index);
 350             let decl = &self.local_decls[local];
 351             if (decl.is_user_variable() || index < self.arg_count + 1)
 352                 && decl.mutability == Mutability::Mut
 353             {
 354                 Some(local)
 355             } else {
 356                 None
 357             }
 358         })
 359     }
 360
 361     /// Returns an iterator over all function arguments.
 362     #[inline]
 363     pub fn args_iter(&self) -> impl Iterator<Item = Local> {
 364         let arg_count = self.arg_count;
 365         (1..=arg_count).map(Local::new)
 366     }
 367
 368     /// Returns an iterator over all user-defined variables and compiler-generated temporaries (all
 369     /// locals that are neither arguments nor the return place).
 370     #[inline]
 371     pub fn vars_and_temps_iter(&self) -> impl Iterator<Item = Local> {
 372         let arg_count = self.arg_count;
 373         let local_count = self.local_decls.len();
 374         (arg_count + 1..local_count).map(Local::new)
 375     }
 376
 377     /// Changes a statement to a nop. This is both faster than deleting instructions and avoids
 378     /// invalidating statement indices in `Location`s.
 379     pub fn make_statement_nop(&mut self, location: Location) {
 380         let block = &mut self[location.block];
 381         debug_assert!(location.statement_index < block.statements.len());
 382         block.statements[location.statement_index].make_nop()
 383     }
 384
 385     /// Returns the source info associated with `location`.
 386     pub fn source_info(&self, location: Location) -> &SourceInfo {
 387         let block = &self[location.block];
 388         let stmts = &block.statements;
 389         let idx = location.statement_index;
 390         if idx < stmts.len() {
 391             &stmts[idx].source_info
 392         } else {
 393             assert_eq!(idx, stmts.len());
 394             &block.terminator().source_info
 395         }
 396     }
 397
 398     /// Checks if `sub` is a sub scope of `sup`
 399     pub fn is_sub_scope(&self, mut sub: SourceScope, sup: SourceScope) -> bool {
 400         while sub != sup {
 401             match self.source_scopes[sub].parent_scope {
 402                 None => return false,
 403                 Some(p) => sub = p,
 404             }
 405         }
 406         true
 407     }
 408
 409     /// Returns the return type; it always return first element from `local_decls` array.
 410     pub fn return_ty(&self) -> Ty<'tcx> {
 411         self.local_decls[RETURN_PLACE].ty
 412     }
 413
 414     /// Gets the location of the terminator for the given block.
 415     pub fn terminator_loc(&self, bb: BasicBlock) -> Location {
 416         Location { block: bb, statement_index: self[bb].statements.len() }
 417     }
 418 }
 419
 420 #[derive(Copy, Clone, Debug, RustcEncodable, RustcDecodable, HashStable)]
 421 pub enum Safety {
 422     Safe,
 423     /// Unsafe because of a PushUnsafeBlock
 424     BuiltinUnsafe,
 425     /// Unsafe because of an unsafe fn
 426     FnUnsafe,
 427     /// Unsafe because of an `unsafe` block
 428     ExplicitUnsafe(hir::HirId),
 429 }
 430
 431 impl<'tcx> Index<BasicBlock> for Body<'tcx> {
 432     type Output = BasicBlockData<'tcx>;
 433
 434     #[inline]
 435     fn index(&self, index: BasicBlock) -> &BasicBlockData<'tcx> {
 436         &self.basic_blocks()[index]
 437     }
 438 }
 439
 440 impl<'tcx> IndexMut<BasicBlock> for Body<'tcx> {
 441     #[inline]
 442     fn index_mut(&mut self, index: BasicBlock) -> &mut BasicBlockData<'tcx> {
 443         &mut self.basic_blocks_mut()[index]
 444     }
 445 }
 446
 447 #[derive(Copy, Clone, Debug, HashStable, TypeFoldable)]
 448 pub enum ClearCrossCrate<T> {
 449     Clear,
 450     Set(T),
 451 }
 452
 453 impl<T> ClearCrossCrate<T> {
 454     pub fn as_ref(&'a self) -> ClearCrossCrate<&'a T> {
 455         match self {
 456             ClearCrossCrate::Clear => ClearCrossCrate::Clear,
 457             ClearCrossCrate::Set(v) => ClearCrossCrate::Set(v),
 458         }
 459     }
 460
 461     pub fn assert_crate_local(self) -> T {
 462         match self {
 463             ClearCrossCrate::Clear => bug!("unwrapping cross-crate data"),
 464             ClearCrossCrate::Set(v) => v,
 465         }
 466     }
 467 }
 468
 469 impl<T: Encodable> rustc_serialize::UseSpecializedEncodable for ClearCrossCrate<T> {}
 470 impl<T: Decodable> rustc_serialize::UseSpecializedDecodable for ClearCrossCrate<T> {}
 471
 472 /// Grouped information about the source code origin of a MIR entity.
 473 /// Intended to be inspected by diagnostics and debuginfo.
 474 /// Most passes can work with it as a whole, within a single function.
 475 // The unofficial Cranelift backend, at least as of #65828, needs `SourceInfo` to implement `Eq` and
 476 // `Hash`. Please ping @bjorn3 if removing them.
 477 #[derive(Copy, Clone, Debug, Eq, PartialEq, RustcEncodable, RustcDecodable, Hash, HashStable)]
 478 pub struct SourceInfo {
 479     /// The source span for the AST pertaining to this MIR entity.
 480     pub span: Span,
 481
 482     /// The source scope, keeping track of which bindings can be
 483     /// seen by debuginfo, active lint levels, `unsafe {...}`, etc.
 484     pub scope: SourceScope,
 485 }
 486
 487 ///////////////////////////////////////////////////////////////////////////
 488 // Mutability and borrow kinds
 489
 490 #[derive(Copy, Clone, Debug, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable)]
 491 pub enum Mutability {
 492     Mut,
 493     Not,
 494 }
 495
 496 impl From<Mutability> for hir::Mutability {
 497     fn from(m: Mutability) -> Self {
 498         match m {
 499             Mutability::Mut => hir::Mutability::Mutable,
 500             Mutability::Not => hir::Mutability::Immutable,
 501         }
 502     }
 503 }
 504
 505 #[derive(
 506     Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord, RustcEncodable, RustcDecodable, HashStable,
 507 )]
 508 pub enum BorrowKind {
 509     /// Data must be immutable and is aliasable.
 510     Shared,
 511
 512     /// The immediately borrowed place must be immutable, but projections from
 513     /// it don't need to be. For example, a shallow borrow of `a.b` doesn't
 514     /// conflict with a mutable borrow of `a.b.c`.
 515     ///
 516     /// This is used when lowering matches: when matching on a place we want to
 517     /// ensure that place have the same value from the start of the match until
 518     /// an arm is selected. This prevents this code from compiling:
 519     ///
 520     ///     let mut x = &Some(0);
 521     ///     match *x {
 522     ///         None => (),
 523     ///         Some(_) if { x = &None; false } => (),
 524     ///         Some(_) => (),
 525     ///     }
 526     ///
 527     /// This can't be a shared borrow because mutably borrowing (*x as Some).0
 528     /// should not prevent `if let None = x { ... }`, for example, because the
 529     /// mutating `(*x as Some).0` can't affect the discriminant of `x`.
 530     /// We can also report errors with this kind of borrow differently.
 531     Shallow,
 532
 533     /// Data must be immutable but not aliasable. This kind of borrow
 534     /// cannot currently be expressed by the user and is used only in
 535     /// implicit closure bindings. It is needed when the closure is
 536     /// borrowing or mutating a mutable referent, e.g.:
 537     ///
 538     ///     let x: &mut isize = ...;
 539     ///     let y = || *x += 5;
 540     ///
 541     /// If we were to try to translate this closure into a more explicit
 542     /// form, we'd encounter an error with the code as written:
 543     ///
 544     ///     struct Env { x: & &mut isize }
 545     ///     let x: &mut isize = ...;
 546     ///     let y = (&mut Env { &x }, fn_ptr);  // Closure is pair of env and fn
 547     ///     fn fn_ptr(env: &mut Env) { **env.x += 5; }
 548     ///
 549     /// This is then illegal because you cannot mutate an `&mut` found
 550     /// in an aliasable location. To solve, you'd have to translate with
 551     /// an `&mut` borrow:
 552     ///
 553     ///     struct Env { x: & &mut isize }
 554     ///     let x: &mut isize = ...;
 555     ///     let y = (&mut Env { &mut x }, fn_ptr); // changed from &x to &mut x
 556     ///     fn fn_ptr(env: &mut Env) { **env.x += 5; }
 557     ///
 558     /// Now the assignment to `**env.x` is legal, but creating a
 559     /// mutable pointer to `x` is not because `x` is not mutable. We
 560     /// could fix this by declaring `x` as `let mut x`. This is ok in
 561     /// user code, if awkward, but extra weird for closures, since the
 562     /// borrow is hidden.
 563     ///
 564     /// So we introduce a "unique imm" borrow -- the referent is
 565     /// immutable, but not aliasable. This solves the problem. For
 566     /// simplicity, we don't give users the way to express this
 567     /// borrow, it's just used when translating closures.
 568     Unique,
 569
 570     /// Data is mutable and not aliasable.
 571     Mut {
 572         /// `true` if this borrow arose from method-call auto-ref
 573         /// (i.e., `adjustment::Adjust::Borrow`).
 574         allow_two_phase_borrow: bool,
 575     },
 576 }
 577
 578 impl BorrowKind {
 579     pub fn allows_two_phase_borrow(&self) -> bool {
 580         match *self {
 581             BorrowKind::Shared | BorrowKind::Shallow | BorrowKind::Unique => false,
 582             BorrowKind::Mut { allow_two_phase_borrow } => allow_two_phase_borrow,
 583         }
 584     }
 585 }
 586
 587 ///////////////////////////////////////////////////////////////////////////
 588 // Variables and temps
 589
 590 rustc_index::newtype_index! {
 591     pub struct Local {
 592         derive [HashStable]
 593         DEBUG_FORMAT = "_{}",
 594         const RETURN_PLACE = 0,
 595     }
 596 }
 597
 598 impl Atom for Local {
 599     fn index(self) -> usize {
 600         Idx::index(self)
 601     }
 602 }
 603
 604 /// Classifies locals into categories. See `Body::local_kind`.
 605 #[derive(PartialEq, Eq, Debug, HashStable)]
 606 pub enum LocalKind {
 607     /// User-declared variable binding.
 608     Var,
 609     /// Compiler-introduced temporary.
 610     Temp,
 611     /// Function argument.
 612     Arg,
 613     /// Location of function's return value.
 614     ReturnPointer,
 615 }
 616
 617 #[derive(Clone, Debug, RustcEncodable, RustcDecodable, HashStable)]
 618 pub struct VarBindingForm<'tcx> {
 619     /// Is variable bound via `x`, `mut x`, `ref x`, or `ref mut x`?
 620     pub binding_mode: ty::BindingMode,
 621     /// If an explicit type was provided for this variable binding,
 622     /// this holds the source Span of that type.
 623     ///
 624     /// NOTE: if you want to change this to a `HirId`, be wary that
 625     /// doing so breaks incremental compilation (as of this writing),
 626     /// while a `Span` does not cause our tests to fail.
 627     pub opt_ty_info: Option<Span>,
 628     /// Place of the RHS of the =, or the subject of the `match` where this
 629     /// variable is initialized. None in the case of `let PATTERN;`.
 630     /// Some((None, ..)) in the case of and `let [mut] x = ...` because
 631     /// (a) the right-hand side isn't evaluated as a place expression.
 632     /// (b) it gives a way to separate this case from the remaining cases
 633     ///     for diagnostics.
 634     pub opt_match_place: Option<(Option<Place<'tcx>>, Span)>,
 635     /// The span of the pattern in which this variable was bound.
 636     pub pat_span: Span,
 637 }
 638
 639 #[derive(Clone, Debug, RustcEncodable, RustcDecodable)]
 640 pub enum BindingForm<'tcx> {
 641     /// This is a binding for a non-`self` binding, or a `self` that has an explicit type.
 642     Var(VarBindingForm<'tcx>),
 643     /// Binding for a `self`/`&self`/`&mut self` binding where the type is implicit.
 644     ImplicitSelf(ImplicitSelfKind),
 645     /// Reference used in a guard expression to ensure immutability.
 646     RefForGuard,
 647 }
 648
 649 /// Represents what type of implicit self a function has, if any.
 650 #[derive(Clone, Copy, PartialEq, Debug, RustcEncodable, RustcDecodable, HashStable)]
 651 pub enum ImplicitSelfKind {
 652     /// Represents a `fn x(self);`.
 653     Imm,
 654     /// Represents a `fn x(mut self);`.
 655     Mut,
 656     /// Represents a `fn x(&self);`.
 657     ImmRef,
 658     /// Represents a `fn x(&mut self);`.
 659     MutRef,
 660     /// Represents when a function does not have a self argument or
 661     /// when a function has a `self: X` argument.
 662     None,
 663 }
 664
 665 CloneTypeFoldableAndLiftImpls! { BindingForm<'tcx>, }
 666
 667 mod binding_form_impl {
 668     use crate::ich::StableHashingContext;
 669     use rustc_data_structures::stable_hasher::{HashStable, StableHasher};
 670
 671     impl<'a, 'tcx> HashStable<StableHashingContext<'a>> for super::BindingForm<'tcx> {
 672         fn hash_stable(&self, hcx: &mut StableHashingContext<'a>, hasher: &mut StableHasher) {
 673             use super::BindingForm::*;
 674             ::std::mem::discriminant(self).hash_stable(hcx, hasher);
 675
 676             match self {
 677                 Var(binding) => binding.hash_stable(hcx, hasher),
 678                 ImplicitSelf(kind) => kind.hash_stable(hcx, hasher),
 679                 RefForGuard => (),
 680             }
 681         }
 682     }
 683 }
 684
 685 /// `BlockTailInfo` is attached to the `LocalDecl` for temporaries
 686 /// created during evaluation of expressions in a block tail
 687 /// expression; that is, a block like `{ STMT_1; STMT_2; EXPR }`.
 688 ///
 689 /// It is used to improve diagnostics when such temporaries are
 690 /// involved in borrow_check errors, e.g., explanations of where the
 691 /// temporaries come from, when their destructors are run, and/or how
 692 /// one might revise the code to satisfy the borrow checker's rules.
 693 #[derive(Clone, Debug, RustcEncodable, RustcDecodable, HashStable)]
 694 pub struct BlockTailInfo {
 695     /// If `true`, then the value resulting from evaluating this tail
 696     /// expression is ignored by the block's expression context.
 697     ///
 698     /// Examples include `{ ...; tail };` and `let _ = { ...; tail };`
 699     /// but not e.g., `let _x = { ...; tail };`
 700     pub tail_result_is_ignored: bool,
 701 }
 702
 703 /// A MIR local.
 704 ///
 705 /// This can be a binding declared by the user, a temporary inserted by the compiler, a function
 706 /// argument, or the return place.
 707 #[derive(Clone, Debug, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
 708 pub struct LocalDecl<'tcx> {
 709     /// Whether this is a mutable minding (i.e., `let x` or `let mut x`).
 710     ///
 711     /// Temporaries and the return place are always mutable.
 712     pub mutability: Mutability,
 713
 714     // FIXME(matthewjasper) Don't store in this in `Body`
 715     pub local_info: LocalInfo<'tcx>,
 716
 717     /// `true` if this is an internal local.
 718     ///
 719     /// These locals are not based on types in the source code and are only used
 720     /// for a few desugarings at the moment.
 721     ///
 722     /// The generator transformation will sanity check the locals which are live
 723     /// across a suspension point against the type components of the generator
 724     /// which type checking knows are live across a suspension point. We need to
 725     /// flag drop flags to avoid triggering this check as they are introduced
 726     /// after typeck.
 727     ///
 728     /// Unsafety checking will also ignore dereferences of these locals,
 729     /// so they can be used for raw pointers only used in a desugaring.
 730     ///
 731     /// This should be sound because the drop flags are fully algebraic, and
 732     /// therefore don't affect the OIBIT or outlives properties of the
 733     /// generator.
 734     pub internal: bool,
 735
 736     /// If this local is a temporary and `is_block_tail` is `Some`,
 737     /// then it is a temporary created for evaluation of some
 738     /// subexpression of some block's tail expression (with no
 739     /// intervening statement context).
 740     // FIXME(matthewjasper) Don't store in this in `Body`
 741     pub is_block_tail: Option<BlockTailInfo>,
 742
 743     /// The type of this local.
 744     pub ty: Ty<'tcx>,
 745
 746     /// If the user manually ascribed a type to this variable,
 747     /// e.g., via `let x: T`, then we carry that type here. The MIR
 748     /// borrow checker needs this information since it can affect
 749     /// region inference.
 750     // FIXME(matthewjasper) Don't store in this in `Body`
 751     pub user_ty: UserTypeProjections,
 752
 753     /// The *syntactic* (i.e., not visibility) source scope the local is defined
 754     /// in. If the local was defined in a let-statement, this
 755     /// is *within* the let-statement, rather than outside
 756     /// of it.
 757     ///
 758     /// This is needed because the visibility source scope of locals within
 759     /// a let-statement is weird.
 760     ///
 761     /// The reason is that we want the local to be *within* the let-statement
 762     /// for lint purposes, but we want the local to be *after* the let-statement
 763     /// for names-in-scope purposes.
 764     ///
 765     /// That's it, if we have a let-statement like the one in this
 766     /// function:
 767     ///
 768     /// ```
 769     /// fn foo(x: &str) {
 770     ///     #[allow(unused_mut)]
 771     ///     let mut x: u32 = { // <- one unused mut
 772     ///         let mut y: u32 = x.parse().unwrap();
 773     ///         y + 2
 774     ///     };
 775     ///     drop(x);
 776     /// }
 777     /// ```
 778     ///
 779     /// Then, from a lint point of view, the declaration of `x: u32`
 780     /// (and `y: u32`) are within the `#[allow(unused_mut)]` scope - the
 781     /// lint scopes are the same as the AST/HIR nesting.
 782     ///
 783     /// However, from a name lookup point of view, the scopes look more like
 784     /// as if the let-statements were `match` expressions:
 785     ///
 786     /// ```
 787     /// fn foo(x: &str) {
 788     ///     match {
 789     ///         match x.parse().unwrap() {
 790     ///             y => y + 2
 791     ///         }
 792     ///     } {
 793     ///         x => drop(x)
 794     ///     };
 795     /// }
 796     /// ```
 797     ///
 798     /// We care about the name-lookup scopes for debuginfo - if the
 799     /// debuginfo instruction pointer is at the call to `x.parse()`, we
 800     /// want `x` to refer to `x: &str`, but if it is at the call to
 801     /// `drop(x)`, we want it to refer to `x: u32`.
 802     ///
 803     /// To allow both uses to work, we need to have more than a single scope
 804     /// for a local. We have the `source_info.scope` represent the "syntactic"
 805     /// lint scope (with a variable being under its let block) while the
 806     /// `var_debug_info.source_info.scope` represents the "local variable"
 807     /// scope (where the "rest" of a block is under all prior let-statements).
 808     ///
 809     /// The end result looks like this:
 810     ///
 811     /// ```text
 812     /// ROOT SCOPE
 813     ///  │{ argument x: &str }
 814     ///  │
 815     ///  │ │{ #[allow(unused_mut)] } // This is actually split into 2 scopes
 816     ///  │ │                         // in practice because I'm lazy.
 817     ///  │ │
 818     ///  │ │← x.source_info.scope
 819     ///  │ │← `x.parse().unwrap()`
 820     ///  │ │
 821     ///  │ │ │← y.source_info.scope
 822     ///  │ │
 823     ///  │ │ │{ let y: u32 }
 824     ///  │ │ │
 825     ///  │ │ │← y.var_debug_info.source_info.scope
 826     ///  │ │ │← `y + 2`
 827     ///  │
 828     ///  │ │{ let x: u32 }
 829     ///  │ │← x.var_debug_info.source_info.scope
 830     ///  │ │← `drop(x)` // This accesses `x: u32`.
 831     /// ```
 832     pub source_info: SourceInfo,
 833 }
 834
 835 /// Extra information about a local that's used for diagnostics.
 836 #[derive(Clone, Debug, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
 837 pub enum LocalInfo<'tcx> {
 838     /// A user-defined local variable or function parameter
 839     ///
 840     /// The `BindingForm` is solely used for local diagnostics when generating
 841     /// warnings/errors when compiling the current crate, and therefore it need
 842     /// not be visible across crates.
 843     User(ClearCrossCrate<BindingForm<'tcx>>),
 844     /// A temporary created that references the static with the given `DefId`.
 845     StaticRef { def_id: DefId, is_thread_local: bool },
 846     /// Any other temporary, the return place, or an anonymous function parameter.
 847     Other,
 848 }
 849
 850 impl<'tcx> LocalDecl<'tcx> {
 851     /// Returns `true` only if local is a binding that can itself be
 852     /// made mutable via the addition of the `mut` keyword, namely
 853     /// something like the occurrences of `x` in:
 854     /// - `fn foo(x: Type) { ... }`,
 855     /// - `let x = ...`,
 856     /// - or `match ... { C(x) => ... }`
 857     pub fn can_be_made_mutable(&self) -> bool {
 858         match self.local_info {
 859             LocalInfo::User(ClearCrossCrate::Set(BindingForm::Var(VarBindingForm {
 860                 binding_mode: ty::BindingMode::BindByValue(_),
 861                 opt_ty_info: _,
 862                 opt_match_place: _,
 863                 pat_span: _,
 864             }))) => true,
 865
 866             LocalInfo::User(
 867                 ClearCrossCrate::Set(BindingForm::ImplicitSelf(ImplicitSelfKind::Imm)),
 868             ) => true,
 869
 870             _ => false,
 871         }
 872     }
 873
 874     /// Returns `true` if local is definitely not a `ref ident` or
 875     /// `ref mut ident` binding. (Such bindings cannot be made into
 876     /// mutable bindings, but the inverse does not necessarily hold).
 877     pub fn is_nonref_binding(&self) -> bool {
 878         match self.local_info {
 879             LocalInfo::User(ClearCrossCrate::Set(BindingForm::Var(VarBindingForm {
 880                 binding_mode: ty::BindingMode::BindByValue(_),
 881                 opt_ty_info: _,
 882                 opt_match_place: _,
 883                 pat_span: _,
 884             }))) => true,
 885
 886             LocalInfo::User(ClearCrossCrate::Set(BindingForm::ImplicitSelf(_))) => true,
 887
 888             _ => false,
 889         }
 890     }
 891
 892     /// Returns `true` if this variable is a named variable or function
 893     /// parameter declared by the user.
 894     #[inline]
 895     pub fn is_user_variable(&self) -> bool {
 896         match self.local_info {
 897             LocalInfo::User(_) => true,
 898             _ => false,
 899         }
 900     }
 901
 902     /// Returns `true` if this is a reference to a variable bound in a `match`
 903     /// expression that is used to access said variable for the guard of the
 904     /// match arm.
 905     pub fn is_ref_for_guard(&self) -> bool {
 906         match self.local_info {
 907             LocalInfo::User(ClearCrossCrate::Set(BindingForm::RefForGuard)) => true,
 908             _ => false,
 909         }
 910     }
 911
 912     /// Returns `Some` if this is a reference to a static item that is used to
 913     /// access that static
 914     pub fn is_ref_to_static(&self) -> bool {
 915         match self.local_info {
 916             LocalInfo::StaticRef { .. } => true,
 917             _ => false,
 918         }
 919     }
 920
 921     /// Returns `Some` if this is a reference to a static item that is used to
 922     /// access that static
 923     pub fn is_ref_to_thread_local(&self) -> bool {
 924         match self.local_info {
 925             LocalInfo::StaticRef { is_thread_local, .. } => is_thread_local,
 926             _ => false,
 927         }
 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.
 938     #[inline]
 939     pub fn new_temp(ty: Ty<'tcx>, span: Span) -> Self {
 940         Self::new_local(ty, Mutability::Mut, false, span)
 941     }
 942
 943     /// Converts `self` into same `LocalDecl` except tagged as immutable.
 944     #[inline]
 945     pub fn immutable(mut self) -> Self {
 946         self.mutability = Mutability::Not;
 947         self
 948     }
 949
 950     /// Converts `self` into same `LocalDecl` except tagged as internal temporary.
 951     #[inline]
 952     pub fn block_tail(mut self, info: BlockTailInfo) -> Self {
 953         assert!(self.is_block_tail.is_none());
 954         self.is_block_tail = Some(info);
 955         self
 956     }
 957
 958     /// Creates a new `LocalDecl` for a internal temporary.
 959     #[inline]
 960     pub fn new_internal(ty: Ty<'tcx>, span: Span) -> Self {
 961         Self::new_local(ty, Mutability::Mut, true, span)
 962     }
 963
 964     #[inline]
 965     fn new_local(ty: Ty<'tcx>, mutability: Mutability, internal: bool, span: Span) -> Self {
 966         LocalDecl {
 967             mutability,
 968             ty,
 969             user_ty: UserTypeProjections::none(),
 970             source_info: SourceInfo { span, scope: OUTERMOST_SOURCE_SCOPE },
 971             internal,
 972             local_info: LocalInfo::Other,
 973             is_block_tail: None,
 974         }
 975     }
 976
 977     /// Builds a `LocalDecl` for the return place.
 978     ///
 979     /// This must be inserted into the `local_decls` list as the first local.
 980     #[inline]
 981     pub fn new_return_place(return_ty: Ty<'_>, span: Span) -> LocalDecl<'_> {
 982         LocalDecl {
 983             mutability: Mutability::Mut,
 984             ty: return_ty,
 985             user_ty: UserTypeProjections::none(),
 986             source_info: SourceInfo { span, scope: OUTERMOST_SOURCE_SCOPE },
 987             internal: false,
 988             is_block_tail: None,
 989             local_info: LocalInfo::Other,
 990         }
 991     }
 992 }
 993
 994 /// Debug information pertaining to a user variable.
 995 #[derive(Clone, Debug, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
 996 pub struct VarDebugInfo<'tcx> {
 997     pub name: Name,
 998
 999     /// Source info of the user variable, including the scope
1000     /// within which the variable is visible (to debuginfo)
1001     /// (see `LocalDecl`'s `source_info` field for more details).
1002     pub source_info: SourceInfo,
1003
1004     /// Where the data for this user variable is to be found.
1005     /// NOTE(eddyb) There's an unenforced invariant that this `Place` is
1006     /// based on a `Local`, not a `Static`, and contains no indexing.
1007     pub place: Place<'tcx>,
1008 }
1009
1010 ///////////////////////////////////////////////////////////////////////////
1011 // BasicBlock
1012
1013 rustc_index::newtype_index! {
1014     pub struct BasicBlock {
1015         derive [HashStable]
1016         DEBUG_FORMAT = "bb{}",
1017         const START_BLOCK = 0,
1018     }
1019 }
1020
1021 impl BasicBlock {
1022     pub fn start_location(self) -> Location {
1023         Location { block: self, statement_index: 0 }
1024     }
1025 }
1026
1027 CloneTypeFoldableAndLiftImpls!{ BasicBlock, }
1028
1029 ///////////////////////////////////////////////////////////////////////////
1030 // BasicBlockData and Terminator
1031
1032 #[derive(Clone, Debug, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
1033 pub struct BasicBlockData<'tcx> {
1034     /// List of statements in this block.
1035     pub statements: Vec<Statement<'tcx>>,
1036
1037     /// Terminator for this block.
1038     ///
1039     /// N.B., this should generally ONLY be `None` during construction.
1040     /// Therefore, you should generally access it via the
1041     /// `terminator()` or `terminator_mut()` methods. The only
1042     /// exception is that certain passes, such as `simplify_cfg`, swap
1043     /// out the terminator temporarily with `None` while they continue
1044     /// to recurse over the set of basic blocks.
1045     pub terminator: Option<Terminator<'tcx>>,
1046
1047     /// If true, this block lies on an unwind path. This is used
1048     /// during codegen where distinct kinds of basic blocks may be
1049     /// generated (particularly for MSVC cleanup). Unwind blocks must
1050     /// only branch to other unwind blocks.
1051     pub is_cleanup: bool,
1052 }
1053
1054 #[derive(Clone, Debug, RustcEncodable, RustcDecodable, HashStable)]
1055 pub struct Terminator<'tcx> {
1056     pub source_info: SourceInfo,
1057     pub kind: TerminatorKind<'tcx>,
1058 }
1059
1060 #[derive(Clone, RustcEncodable, RustcDecodable, HashStable, PartialEq)]
1061 pub enum TerminatorKind<'tcx> {
1062     /// Block should have one successor in the graph; we jump there.
1063     Goto { target: BasicBlock },
1064
1065     /// Operand evaluates to an integer; jump depending on its value
1066     /// to one of the targets, and otherwise fallback to `otherwise`.
1067     SwitchInt {
1068         /// The discriminant value being tested.
1069         discr: Operand<'tcx>,
1070
1071         /// The type of value being tested.
1072         switch_ty: Ty<'tcx>,
1073
1074         /// Possible values. The locations to branch to in each case
1075         /// are found in the corresponding indices from the `targets` vector.
1076         values: Cow<'tcx, [u128]>,
1077
1078         /// Possible branch sites. The last element of this vector is used
1079         /// for the otherwise branch, so targets.len() == values.len() + 1
1080         /// should hold.
1081         //
1082         // This invariant is quite non-obvious and also could be improved.
1083         // One way to make this invariant is to have something like this instead:
1084         //
1085         // branches: Vec<(ConstInt, BasicBlock)>,
1086         // otherwise: Option<BasicBlock> // exhaustive if None
1087         //
1088         // However we’ve decided to keep this as-is until we figure a case
1089         // where some other approach seems to be strictly better than other.
1090         targets: Vec<BasicBlock>,
1091     },
1092
1093     /// Indicates that the landing pad is finished and unwinding should
1094     /// continue. Emitted by `build::scope::diverge_cleanup`.
1095     Resume,
1096
1097     /// Indicates that the landing pad is finished and that the process
1098     /// should abort. Used to prevent unwinding for foreign items.
1099     Abort,
1100
1101     /// Indicates a normal return. The return place should have
1102     /// been filled in by now. This should occur at most once.
1103     Return,
1104
1105     /// Indicates a terminator that can never be reached.
1106     Unreachable,
1107
1108     /// Drop the `Place`.
1109     Drop { location: Place<'tcx>, target: BasicBlock, unwind: Option<BasicBlock> },
1110
1111     /// Drop the `Place` and assign the new value over it. This ensures
1112     /// that the assignment to `P` occurs *even if* the destructor for
1113     /// place unwinds. Its semantics are best explained by the
1114     /// elaboration:
1115     ///
1116     /// ```
1117     /// BB0 {
1118     ///   DropAndReplace(P <- V, goto BB1, unwind BB2)
1119     /// }
1120     /// ```
1121     ///
1122     /// becomes
1123     ///
1124     /// ```
1125     /// BB0 {
1126     ///   Drop(P, goto BB1, unwind BB2)
1127     /// }
1128     /// BB1 {
1129     ///   // P is now uninitialized
1130     ///   P <- V
1131     /// }
1132     /// BB2 {
1133     ///   // P is now uninitialized -- its dtor panicked
1134     ///   P <- V
1135     /// }
1136     /// ```
1137     DropAndReplace {
1138         location: Place<'tcx>,
1139         value: Operand<'tcx>,
1140         target: BasicBlock,
1141         unwind: Option<BasicBlock>,
1142     },
1143
1144     /// Block ends with a call of a converging function.
1145     Call {
1146         /// The function that’s being called.
1147         func: Operand<'tcx>,
1148         /// Arguments the function is called with.
1149         /// These are owned by the callee, which is free to modify them.
1150         /// This allows the memory occupied by "by-value" arguments to be
1151         /// reused across function calls without duplicating the contents.
1152         args: Vec<Operand<'tcx>>,
1153         /// Destination for the return value. If some, the call is converging.
1154         destination: Option<(Place<'tcx>, BasicBlock)>,
1155         /// Cleanups to be done if the call unwinds.
1156         cleanup: Option<BasicBlock>,
1157         /// `true` if this is from a call in HIR rather than from an overloaded
1158         /// operator. True for overloaded function call.
1159         from_hir_call: bool,
1160     },
1161
1162     /// Jump to the target if the condition has the expected value,
1163     /// otherwise panic with a message and a cleanup target.
1164     Assert {
1165         cond: Operand<'tcx>,
1166         expected: bool,
1167         msg: AssertMessage<'tcx>,
1168         target: BasicBlock,
1169         cleanup: Option<BasicBlock>,
1170     },
1171
1172     /// A suspend point.
1173     Yield {
1174         /// The value to return.
1175         value: Operand<'tcx>,
1176         /// Where to resume to.
1177         resume: BasicBlock,
1178         /// Cleanup to be done if the generator is dropped at this suspend point.
1179         drop: Option<BasicBlock>,
1180     },
1181
1182     /// Indicates the end of the dropping of a generator.
1183     GeneratorDrop,
1184
1185     /// A block where control flow only ever takes one real path, but borrowck
1186     /// needs to be more conservative.
1187     FalseEdges {
1188         /// The target normal control flow will take.
1189         real_target: BasicBlock,
1190         /// A block control flow could conceptually jump to, but won't in
1191         /// practice.
1192         imaginary_target: BasicBlock,
1193     },
1194     /// A terminator for blocks that only take one path in reality, but where we
1195     /// reserve the right to unwind in borrowck, even if it won't happen in practice.
1196     /// This can arise in infinite loops with no function calls for example.
1197     FalseUnwind {
1198         /// The target normal control flow will take.
1199         real_target: BasicBlock,
1200         /// The imaginary cleanup block link. This particular path will never be taken
1201         /// in practice, but in order to avoid fragility we want to always
1202         /// consider it in borrowck. We don't want to accept programs which
1203         /// pass borrowck only when `panic=abort` or some assertions are disabled
1204         /// due to release vs. debug mode builds. This needs to be an `Option` because
1205         /// of the `remove_noop_landing_pads` and `no_landing_pads` passes.
1206         unwind: Option<BasicBlock>,
1207     },
1208 }
1209
1210 pub type Successors<'a> =
1211     iter::Chain<option::IntoIter<&'a BasicBlock>, slice::Iter<'a, BasicBlock>>;
1212 pub type SuccessorsMut<'a> =
1213     iter::Chain<option::IntoIter<&'a mut BasicBlock>, slice::IterMut<'a, BasicBlock>>;
1214
1215 impl<'tcx> Terminator<'tcx> {
1216     pub fn successors(&self) -> Successors<'_> {
1217         self.kind.successors()
1218     }
1219
1220     pub fn successors_mut(&mut self) -> SuccessorsMut<'_> {
1221         self.kind.successors_mut()
1222     }
1223
1224     pub fn unwind(&self) -> Option<&Option<BasicBlock>> {
1225         self.kind.unwind()
1226     }
1227
1228     pub fn unwind_mut(&mut self) -> Option<&mut Option<BasicBlock>> {
1229         self.kind.unwind_mut()
1230     }
1231 }
1232
1233 impl<'tcx> TerminatorKind<'tcx> {
1234     pub fn if_(
1235         tcx: TyCtxt<'tcx>,
1236         cond: Operand<'tcx>,
1237         t: BasicBlock,
1238         f: BasicBlock,
1239     ) -> TerminatorKind<'tcx> {
1240         static BOOL_SWITCH_FALSE: &'static [u128] = &[0];
1241         TerminatorKind::SwitchInt {
1242             discr: cond,
1243             switch_ty: tcx.types.bool,
1244             values: From::from(BOOL_SWITCH_FALSE),
1245             targets: vec![f, t],
1246         }
1247     }
1248
1249     pub fn successors(&self) -> Successors<'_> {
1250         use self::TerminatorKind::*;
1251         match *self {
1252             Resume
1253             | Abort
1254             | GeneratorDrop
1255             | Return
1256             | Unreachable
1257             | Call { destination: None, cleanup: None, .. } => None.into_iter().chain(&[]),
1258             Goto { target: ref t }
1259             | Call { destination: None, cleanup: Some(ref t), .. }
1260             | Call { destination: Some((_, ref t)), cleanup: None, .. }
1261             | Yield { resume: ref t, drop: None, .. }
1262             | DropAndReplace { target: ref t, unwind: None, .. }
1263             | Drop { target: ref t, unwind: None, .. }
1264             | Assert { target: ref t, cleanup: None, .. }
1265             | FalseUnwind { real_target: ref t, unwind: None } => Some(t).into_iter().chain(&[]),
1266             Call { destination: Some((_, ref t)), cleanup: Some(ref u), .. }
1267             | Yield { resume: ref t, drop: Some(ref u), .. }
1268             | DropAndReplace { target: ref t, unwind: Some(ref u), .. }
1269             | Drop { target: ref t, unwind: Some(ref u), .. }
1270             | Assert { target: ref t, cleanup: Some(ref u), .. }
1271             | FalseUnwind { real_target: ref t, unwind: Some(ref u) } => {
1272                 Some(t).into_iter().chain(slice::from_ref(u))
1273             }
1274             SwitchInt { ref targets, .. } => None.into_iter().chain(&targets[..]),
1275             FalseEdges { ref real_target, ref imaginary_target } => {
1276                 Some(real_target).into_iter().chain(slice::from_ref(imaginary_target))
1277             }
1278         }
1279     }
1280
1281     pub fn successors_mut(&mut self) -> SuccessorsMut<'_> {
1282         use self::TerminatorKind::*;
1283         match *self {
1284             Resume
1285             | Abort
1286             | GeneratorDrop
1287             | Return
1288             | Unreachable
1289             | Call { destination: None, cleanup: None, .. } => None.into_iter().chain(&mut []),
1290             Goto { target: ref mut t }
1291             | Call { destination: None, cleanup: Some(ref mut t), .. }
1292             | Call { destination: Some((_, ref mut t)), cleanup: None, .. }
1293             | Yield { resume: ref mut t, drop: None, .. }
1294             | DropAndReplace { target: ref mut t, unwind: None, .. }
1295             | Drop { target: ref mut t, unwind: None, .. }
1296             | Assert { target: ref mut t, cleanup: None, .. }
1297             | FalseUnwind { real_target: ref mut t, unwind: None } => {
1298                 Some(t).into_iter().chain(&mut [])
1299             }
1300             Call { destination: Some((_, ref mut t)), cleanup: Some(ref mut u), .. }
1301             | Yield { resume: ref mut t, drop: Some(ref mut u), .. }
1302             | DropAndReplace { target: ref mut t, unwind: Some(ref mut u), .. }
1303             | Drop { target: ref mut t, unwind: Some(ref mut u), .. }
1304             | Assert { target: ref mut t, cleanup: Some(ref mut u), .. }
1305             | FalseUnwind { real_target: ref mut t, unwind: Some(ref mut u) } => {
1306                 Some(t).into_iter().chain(slice::from_mut(u))
1307             }
1308             SwitchInt { ref mut targets, .. } => None.into_iter().chain(&mut targets[..]),
1309             FalseEdges { ref mut real_target, ref mut imaginary_target } => {
1310                 Some(real_target).into_iter().chain(slice::from_mut(imaginary_target))
1311             }
1312         }
1313     }
1314
1315     pub fn unwind(&self) -> Option<&Option<BasicBlock>> {
1316         match *self {
1317             TerminatorKind::Goto { .. }
1318             | TerminatorKind::Resume
1319             | TerminatorKind::Abort
1320             | TerminatorKind::Return
1321             | TerminatorKind::Unreachable
1322             | TerminatorKind::GeneratorDrop
1323             | TerminatorKind::Yield { .. }
1324             | TerminatorKind::SwitchInt { .. }
1325             | TerminatorKind::FalseEdges { .. } => None,
1326             TerminatorKind::Call { cleanup: ref unwind, .. }
1327             | TerminatorKind::Assert { cleanup: ref unwind, .. }
1328             | TerminatorKind::DropAndReplace { ref unwind, .. }
1329             | TerminatorKind::Drop { ref unwind, .. }
1330             | TerminatorKind::FalseUnwind { ref unwind, .. } => Some(unwind),
1331         }
1332     }
1333
1334     pub fn unwind_mut(&mut self) -> Option<&mut Option<BasicBlock>> {
1335         match *self {
1336             TerminatorKind::Goto { .. }
1337             | TerminatorKind::Resume
1338             | TerminatorKind::Abort
1339             | TerminatorKind::Return
1340             | TerminatorKind::Unreachable
1341             | TerminatorKind::GeneratorDrop
1342             | TerminatorKind::Yield { .. }
1343             | TerminatorKind::SwitchInt { .. }
1344             | TerminatorKind::FalseEdges { .. } => None,
1345             TerminatorKind::Call { cleanup: ref mut unwind, .. }
1346             | TerminatorKind::Assert { cleanup: ref mut unwind, .. }
1347             | TerminatorKind::DropAndReplace { ref mut unwind, .. }
1348             | TerminatorKind::Drop { ref mut unwind, .. }
1349             | TerminatorKind::FalseUnwind { ref mut unwind, .. } => Some(unwind),
1350         }
1351     }
1352 }
1353
1354 impl<'tcx> BasicBlockData<'tcx> {
1355     pub fn new(terminator: Option<Terminator<'tcx>>) -> BasicBlockData<'tcx> {
1356         BasicBlockData { statements: vec![], terminator, is_cleanup: false }
1357     }
1358
1359     /// Accessor for terminator.
1360     ///
1361     /// Terminator may not be None after construction of the basic block is complete. This accessor
1362     /// provides a convenience way to reach the terminator.
1363     pub fn terminator(&self) -> &Terminator<'tcx> {
1364         self.terminator.as_ref().expect("invalid terminator state")
1365     }
1366
1367     pub fn terminator_mut(&mut self) -> &mut Terminator<'tcx> {
1368         self.terminator.as_mut().expect("invalid terminator state")
1369     }
1370
1371     pub fn retain_statements<F>(&mut self, mut f: F)
1372     where
1373         F: FnMut(&mut Statement<'_>) -> bool,
1374     {
1375         for s in &mut self.statements {
1376             if !f(s) {
1377                 s.make_nop();
1378             }
1379         }
1380     }
1381
1382     pub fn expand_statements<F, I>(&mut self, mut f: F)
1383     where
1384         F: FnMut(&mut Statement<'tcx>) -> Option<I>,
1385         I: iter::TrustedLen<Item = Statement<'tcx>>,
1386     {
1387         // Gather all the iterators we'll need to splice in, and their positions.
1388         let mut splices: Vec<(usize, I)> = vec![];
1389         let mut extra_stmts = 0;
1390         for (i, s) in self.statements.iter_mut().enumerate() {
1391             if let Some(mut new_stmts) = f(s) {
1392                 if let Some(first) = new_stmts.next() {
1393                     // We can already store the first new statement.
1394                     *s = first;
1395
1396                     // Save the other statements for optimized splicing.
1397                     let remaining = new_stmts.size_hint().0;
1398                     if remaining > 0 {
1399                         splices.push((i + 1 + extra_stmts, new_stmts));
1400                         extra_stmts += remaining;
1401                     }
1402                 } else {
1403                     s.make_nop();
1404                 }
1405             }
1406         }
1407
1408         // Splice in the new statements, from the end of the block.
1409         // FIXME(eddyb) This could be more efficient with a "gap buffer"
1410         // where a range of elements ("gap") is left uninitialized, with
1411         // splicing adding new elements to the end of that gap and moving
1412         // existing elements from before the gap to the end of the gap.
1413         // For now, this is safe code, emulating a gap but initializing it.
1414         let mut gap = self.statements.len()..self.statements.len() + extra_stmts;
1415         self.statements.resize(
1416             gap.end,
1417             Statement {
1418                 source_info: SourceInfo { span: DUMMY_SP, scope: OUTERMOST_SOURCE_SCOPE },
1419                 kind: StatementKind::Nop,
1420             },
1421         );
1422         for (splice_start, new_stmts) in splices.into_iter().rev() {
1423             let splice_end = splice_start + new_stmts.size_hint().0;
1424             while gap.end > splice_end {
1425                 gap.start -= 1;
1426                 gap.end -= 1;
1427                 self.statements.swap(gap.start, gap.end);
1428             }
1429             self.statements.splice(splice_start..splice_end, new_stmts);
1430             gap.end = splice_start;
1431         }
1432     }
1433
1434     pub fn visitable(&self, index: usize) -> &dyn MirVisitable<'tcx> {
1435         if index < self.statements.len() {
1436             &self.statements[index]
1437         } else {
1438             &self.terminator
1439         }
1440     }
1441 }
1442
1443 impl<'tcx> Debug for TerminatorKind<'tcx> {
1444     fn fmt(&self, fmt: &mut Formatter<'_>) -> fmt::Result {
1445         self.fmt_head(fmt)?;
1446         let successor_count = self.successors().count();
1447         let labels = self.fmt_successor_labels();
1448         assert_eq!(successor_count, labels.len());
1449
1450         match successor_count {
1451             0 => Ok(()),
1452
1453             1 => write!(fmt, " -> {:?}", self.successors().nth(0).unwrap()),
1454
1455             _ => {
1456                 write!(fmt, " -> [")?;
1457                 for (i, target) in self.successors().enumerate() {
1458                     if i > 0 {
1459                         write!(fmt, ", ")?;
1460                     }
1461                     write!(fmt, "{}: {:?}", labels[i], target)?;
1462                 }
1463                 write!(fmt, "]")
1464             }
1465         }
1466     }
1467 }
1468
1469 impl<'tcx> TerminatorKind<'tcx> {
1470     /// Writes the "head" part of the terminator; that is, its name and the data it uses to pick the
1471     /// successor basic block, if any. The only information not included is the list of possible
1472     /// successors, which may be rendered differently between the text and the graphviz format.
1473     pub fn fmt_head<W: Write>(&self, fmt: &mut W) -> fmt::Result {
1474         use self::TerminatorKind::*;
1475         match *self {
1476             Goto { .. } => write!(fmt, "goto"),
1477             SwitchInt { discr: ref place, .. } => write!(fmt, "switchInt({:?})", place),
1478             Return => write!(fmt, "return"),
1479             GeneratorDrop => write!(fmt, "generator_drop"),
1480             Resume => write!(fmt, "resume"),
1481             Abort => write!(fmt, "abort"),
1482             Yield { ref value, .. } => write!(fmt, "_1 = suspend({:?})", value),
1483             Unreachable => write!(fmt, "unreachable"),
1484             Drop { ref location, .. } => write!(fmt, "drop({:?})", location),
1485             DropAndReplace { ref location, ref value, .. } => {
1486                 write!(fmt, "replace({:?} <- {:?})", location, value)
1487             }
1488             Call { ref func, ref args, ref destination, .. } => {
1489                 if let Some((ref destination, _)) = *destination {
1490                     write!(fmt, "{:?} = ", destination)?;
1491                 }
1492                 write!(fmt, "{:?}(", func)?;
1493                 for (index, arg) in args.iter().enumerate() {
1494                     if index > 0 {
1495                         write!(fmt, ", ")?;
1496                     }
1497                     write!(fmt, "{:?}", arg)?;
1498                 }
1499                 write!(fmt, ")")
1500             }
1501             Assert { ref cond, expected, ref msg, .. } => {
1502                 write!(fmt, "assert(")?;
1503                 if !expected {
1504                     write!(fmt, "!")?;
1505                 }
1506                 write!(fmt, "{:?}, \"{:?}\")", cond, msg)
1507             }
1508             FalseEdges { .. } => write!(fmt, "falseEdges"),
1509             FalseUnwind { .. } => write!(fmt, "falseUnwind"),
1510         }
1511     }
1512
1513     /// Returns the list of labels for the edges to the successor basic blocks.
1514     pub fn fmt_successor_labels(&self) -> Vec<Cow<'static, str>> {
1515         use self::TerminatorKind::*;
1516         match *self {
1517             Return | Resume | Abort | Unreachable | GeneratorDrop => vec![],
1518             Goto { .. } => vec!["".into()],
1519             SwitchInt { ref values, switch_ty, .. } => ty::tls::with(|tcx| {
1520                 let param_env = ty::ParamEnv::empty();
1521                 let switch_ty = tcx.lift(&switch_ty).unwrap();
1522                 let size = tcx.layout_of(param_env.and(switch_ty)).unwrap().size;
1523                 values
1524                     .iter()
1525                     .map(|&u| {
1526                         ty::Const::from_scalar(
1527                             tcx,
1528                             Scalar::from_uint(u, size).into(),
1529                             switch_ty,
1530                         )
1531                         .to_string()
1532                         .into()
1533                     })
1534                     .chain(iter::once("otherwise".into()))
1535                     .collect()
1536             }),
1537             Call { destination: Some(_), cleanup: Some(_), .. } => {
1538                 vec!["return".into(), "unwind".into()]
1539             }
1540             Call { destination: Some(_), cleanup: None, .. } => vec!["return".into()],
1541             Call { destination: None, cleanup: Some(_), .. } => vec!["unwind".into()],
1542             Call { destination: None, cleanup: None, .. } => vec![],
1543             Yield { drop: Some(_), .. } => vec!["resume".into(), "drop".into()],
1544             Yield { drop: None, .. } => vec!["resume".into()],
1545             DropAndReplace { unwind: None, .. } | Drop { unwind: None, .. } => {
1546                 vec!["return".into()]
1547             }
1548             DropAndReplace { unwind: Some(_), .. } | Drop { unwind: Some(_), .. } => {
1549                 vec!["return".into(), "unwind".into()]
1550             }
1551             Assert { cleanup: None, .. } => vec!["".into()],
1552             Assert { .. } => vec!["success".into(), "unwind".into()],
1553             FalseEdges { .. } => vec!["real".into(), "imaginary".into()],
1554             FalseUnwind { unwind: Some(_), .. } => vec!["real".into(), "cleanup".into()],
1555             FalseUnwind { unwind: None, .. } => vec!["real".into()],
1556         }
1557     }
1558 }
1559
1560 ///////////////////////////////////////////////////////////////////////////
1561 // Statements
1562
1563 #[derive(Clone, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
1564 pub struct Statement<'tcx> {
1565     pub source_info: SourceInfo,
1566     pub kind: StatementKind<'tcx>,
1567 }
1568
1569 // `Statement` is used a lot. Make sure it doesn't unintentionally get bigger.
1570 #[cfg(target_arch = "x86_64")]
1571 static_assert_size!(Statement<'_>, 32);
1572
1573 impl Statement<'_> {
1574     /// Changes a statement to a nop. This is both faster than deleting instructions and avoids
1575     /// invalidating statement indices in `Location`s.
1576     pub fn make_nop(&mut self) {
1577         self.kind = StatementKind::Nop
1578     }
1579
1580     /// Changes a statement to a nop and returns the original statement.
1581     pub fn replace_nop(&mut self) -> Self {
1582         Statement {
1583             source_info: self.source_info,
1584             kind: mem::replace(&mut self.kind, StatementKind::Nop),
1585         }
1586     }
1587 }
1588
1589 #[derive(Clone, Debug, PartialEq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
1590 pub enum StatementKind<'tcx> {
1591     /// Write the RHS Rvalue to the LHS Place.
1592     Assign(Box<(Place<'tcx>, Rvalue<'tcx>)>),
1593
1594     /// This represents all the reading that a pattern match may do
1595     /// (e.g., inspecting constants and discriminant values), and the
1596     /// kind of pattern it comes from. This is in order to adapt potential
1597     /// error messages to these specific patterns.
1598     ///
1599     /// Note that this also is emitted for regular `let` bindings to ensure that locals that are
1600     /// never accessed still get some sanity checks for, e.g., `let x: ! = ..;`
1601     FakeRead(FakeReadCause, Box<Place<'tcx>>),
1602
1603     /// Write the discriminant for a variant to the enum Place.
1604     SetDiscriminant { place: Box<Place<'tcx>>, variant_index: VariantIdx },
1605
1606     /// Start a live range for the storage of the local.
1607     StorageLive(Local),
1608
1609     /// End the current live range for the storage of the local.
1610     StorageDead(Local),
1611
1612     /// Executes a piece of inline Assembly. Stored in a Box to keep the size
1613     /// of `StatementKind` low.
1614     InlineAsm(Box<InlineAsm<'tcx>>),
1615
1616     /// Retag references in the given place, ensuring they got fresh tags. This is
1617     /// part of the Stacked Borrows model. These statements are currently only interpreted
1618     /// by miri and only generated when "-Z mir-emit-retag" is passed.
1619     /// See <https://internals.rust-lang.org/t/stacked-borrows-an-aliasing-model-for-rust/8153/>
1620     /// for more details.
1621     Retag(RetagKind, Box<Place<'tcx>>),
1622
1623     /// Encodes a user's type ascription. These need to be preserved
1624     /// intact so that NLL can respect them. For example:
1625     ///
1626     ///     let a: T = y;
1627     ///
1628     /// The effect of this annotation is to relate the type `T_y` of the place `y`
1629     /// to the user-given type `T`. The effect depends on the specified variance:
1630     ///
1631     /// - `Covariant` -- requires that `T_y <: T`
1632     /// - `Contravariant` -- requires that `T_y :> T`
1633     /// - `Invariant` -- requires that `T_y == T`
1634     /// - `Bivariant` -- no effect
1635     AscribeUserType(Box<(Place<'tcx>, UserTypeProjection)>, ty::Variance),
1636
1637     /// No-op. Useful for deleting instructions without affecting statement indices.
1638     Nop,
1639 }
1640
1641 /// Describes what kind of retag is to be performed.
1642 #[derive(Copy, Clone, RustcEncodable, RustcDecodable, Debug, PartialEq, Eq, HashStable)]
1643 pub enum RetagKind {
1644     /// The initial retag when entering a function.
1645     FnEntry,
1646     /// Retag preparing for a two-phase borrow.
1647     TwoPhase,
1648     /// Retagging raw pointers.
1649     Raw,
1650     /// A "normal" retag.
1651     Default,
1652 }
1653
1654 /// The `FakeReadCause` describes the type of pattern why a FakeRead statement exists.
1655 #[derive(Copy, Clone, RustcEncodable, RustcDecodable, Debug, HashStable, PartialEq)]
1656 pub enum FakeReadCause {
1657     /// Inject a fake read of the borrowed input at the end of each guards
1658     /// code.
1659     ///
1660     /// This should ensure that you cannot change the variant for an enum while
1661     /// you are in the midst of matching on it.
1662     ForMatchGuard,
1663
1664     /// `let x: !; match x {}` doesn't generate any read of x so we need to
1665     /// generate a read of x to check that it is initialized and safe.
1666     ForMatchedPlace,
1667
1668     /// A fake read of the RefWithinGuard version of a bind-by-value variable
1669     /// in a match guard to ensure that it's value hasn't change by the time
1670     /// we create the OutsideGuard version.
1671     ForGuardBinding,
1672
1673     /// Officially, the semantics of
1674     ///
1675     /// `let pattern = <expr>;`
1676     ///
1677     /// is that `<expr>` is evaluated into a temporary and then this temporary is
1678     /// into the pattern.
1679     ///
1680     /// However, if we see the simple pattern `let var = <expr>`, we optimize this to
1681     /// evaluate `<expr>` directly into the variable `var`. This is mostly unobservable,
1682     /// but in some cases it can affect the borrow checker, as in #53695.
1683     /// Therefore, we insert a "fake read" here to ensure that we get
1684     /// appropriate errors.
1685     ForLet,
1686
1687     /// If we have an index expression like
1688     ///
1689     /// (*x)[1][{ x = y; 4}]
1690     ///
1691     /// then the first bounds check is invalidated when we evaluate the second
1692     /// index expression. Thus we create a fake borrow of `x` across the second
1693     /// indexer, which will cause a borrow check error.
1694     ForIndex,
1695 }
1696
1697 #[derive(Clone, Debug, PartialEq, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
1698 pub struct InlineAsm<'tcx> {
1699     pub asm: hir::InlineAsmInner,
1700     pub outputs: Box<[Place<'tcx>]>,
1701     pub inputs: Box<[(Span, Operand<'tcx>)]>,
1702 }
1703
1704 impl Debug for Statement<'_> {
1705     fn fmt(&self, fmt: &mut Formatter<'_>) -> fmt::Result {
1706         use self::StatementKind::*;
1707         match self.kind {
1708             Assign(box(ref place, ref rv)) => write!(fmt, "{:?} = {:?}", place, rv),
1709             FakeRead(ref cause, ref place) => write!(fmt, "FakeRead({:?}, {:?})", cause, place),
1710             Retag(ref kind, ref place) => write!(
1711                 fmt,
1712                 "Retag({}{:?})",
1713                 match kind {
1714                     RetagKind::FnEntry => "[fn entry] ",
1715                     RetagKind::TwoPhase => "[2phase] ",
1716                     RetagKind::Raw => "[raw] ",
1717                     RetagKind::Default => "",
1718                 },
1719                 place,
1720             ),
1721             StorageLive(ref place) => write!(fmt, "StorageLive({:?})", place),
1722             StorageDead(ref place) => write!(fmt, "StorageDead({:?})", place),
1723             SetDiscriminant { ref place, variant_index } => {
1724                 write!(fmt, "discriminant({:?}) = {:?}", place, variant_index)
1725             }
1726             InlineAsm(ref asm) => {
1727                 write!(fmt, "asm!({:?} : {:?} : {:?})", asm.asm, asm.outputs, asm.inputs)
1728             }
1729             AscribeUserType(box(ref place, ref c_ty), ref variance) => {
1730                 write!(fmt, "AscribeUserType({:?}, {:?}, {:?})", place, variance, c_ty)
1731             }
1732             Nop => write!(fmt, "nop"),
1733         }
1734     }
1735 }
1736
1737 ///////////////////////////////////////////////////////////////////////////
1738 // Places
1739
1740 /// A path to a value; something that can be evaluated without
1741 /// changing or disturbing program state.
1742 #[derive(
1743     Clone, PartialEq, Eq, PartialOrd, Ord, Hash, RustcEncodable, HashStable,
1744 )]
1745 pub struct Place<'tcx> {
1746     pub base: PlaceBase<'tcx>,
1747
1748     /// projection out of a place (access a field, deref a pointer, etc)
1749     pub projection: &'tcx List<PlaceElem<'tcx>>,
1750 }
1751
1752 impl<'tcx> rustc_serialize::UseSpecializedDecodable for Place<'tcx> {}
1753
1754 #[derive(
1755     Clone, PartialEq, Eq, PartialOrd, Ord, Hash, RustcEncodable, RustcDecodable, HashStable,
1756 )]
1757 pub enum PlaceBase<'tcx> {
1758     /// local variable
1759     Local(Local),
1760
1761     /// static or static mut variable
1762     Static(Box<Static<'tcx>>),
1763 }
1764
1765 /// We store the normalized type to avoid requiring normalization when reading MIR
1766 #[derive(Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash,
1767          RustcEncodable, RustcDecodable, HashStable)]
1768 pub struct Static<'tcx> {
1769     pub ty: Ty<'tcx>,
1770     pub kind: StaticKind<'tcx>,
1771     /// The `DefId` of the item this static was declared in. For promoted values, usually, this is
1772     /// the same as the `DefId` of the `mir::Body` containing the `Place` this promoted appears in.
1773     /// However, after inlining, that might no longer be the case as inlined `Place`s are copied
1774     /// into the calling frame.
1775     pub def_id: DefId,
1776 }
1777
1778 #[derive(
1779     Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash, HashStable, RustcEncodable, RustcDecodable,
1780 )]
1781 pub enum StaticKind<'tcx> {
1782     /// Promoted references consist of an id (`Promoted`) and the substs necessary to monomorphize
1783     /// it. Usually, these substs are just the identity substs for the item. However, the inliner
1784     /// will adjust these substs when it inlines a function based on the substs at the callsite.
1785     Promoted(Promoted, SubstsRef<'tcx>),
1786     Static,
1787 }
1788
1789 #[derive(Copy, Clone, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
1790 #[derive(RustcEncodable, RustcDecodable, HashStable)]
1791 pub enum ProjectionElem<V, T> {
1792     Deref,
1793     Field(Field, T),
1794     Index(V),
1795
1796     /// These indices are generated by slice patterns. Easiest to explain
1797     /// by example:
1798     ///
1799     /// ```
1800     /// [X, _, .._, _, _] => { offset: 0, min_length: 4, from_end: false },
1801     /// [_, X, .._, _, _] => { offset: 1, min_length: 4, from_end: false },
1802     /// [_, _, .._, X, _] => { offset: 2, min_length: 4, from_end: true },
1803     /// [_, _, .._, _, X] => { offset: 1, min_length: 4, from_end: true },
1804     /// ```
1805     ConstantIndex {
1806         /// index or -index (in Python terms), depending on from_end
1807         offset: u32,
1808         /// thing being indexed must be at least this long
1809         min_length: u32,
1810         /// counting backwards from end?
1811         from_end: bool,
1812     },
1813
1814     /// These indices are generated by slice patterns.
1815     ///
1816     /// slice[from:-to] in Python terms.
1817     Subslice {
1818         from: u32,
1819         to: u32,
1820     },
1821
1822     /// "Downcast" to a variant of an ADT. Currently, we only introduce
1823     /// this for ADTs with more than one variant. It may be better to
1824     /// just introduce it always, or always for enums.
1825     ///
1826     /// The included Symbol is the name of the variant, used for printing MIR.
1827     Downcast(Option<Symbol>, VariantIdx),
1828 }
1829
1830 impl<V, T> ProjectionElem<V, T> {
1831     /// Returns `true` if the target of this projection may refer to a different region of memory
1832     /// than the base.
1833     fn is_indirect(&self) -> bool {
1834         match self {
1835             Self::Deref => true,
1836
1837             | Self::Field(_, _)
1838             | Self::Index(_)
1839             | Self::ConstantIndex { .. }
1840             | Self::Subslice { .. }
1841             | Self::Downcast(_, _)
1842             => false
1843         }
1844     }
1845 }
1846
1847 /// Alias for projections as they appear in places, where the base is a place
1848 /// and the index is a local.
1849 pub type PlaceElem<'tcx> = ProjectionElem<Local, Ty<'tcx>>;
1850
1851 impl<'tcx> Copy for PlaceElem<'tcx> { }
1852
1853 // At least on 64 bit systems, `PlaceElem` should not be larger than two pointers.
1854 #[cfg(target_arch = "x86_64")]
1855 static_assert_size!(PlaceElem<'_>, 16);
1856
1857 /// Alias for projections as they appear in `UserTypeProjection`, where we
1858 /// need neither the `V` parameter for `Index` nor the `T` for `Field`.
1859 pub type ProjectionKind = ProjectionElem<(), ()>;
1860
1861 rustc_index::newtype_index! {
1862     pub struct Field {
1863         derive [HashStable]
1864         DEBUG_FORMAT = "field[{}]"
1865     }
1866 }
1867
1868 #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
1869 pub struct PlaceRef<'a, 'tcx> {
1870     pub base: &'a PlaceBase<'tcx>,
1871     pub projection: &'a [PlaceElem<'tcx>],
1872 }
1873
1874 impl<'tcx> Place<'tcx> {
1875     // FIXME change this to a const fn by also making List::empty a const fn.
1876     pub fn return_place() -> Place<'tcx> {
1877         Place {
1878             base: PlaceBase::Local(RETURN_PLACE),
1879             projection: List::empty(),
1880         }
1881     }
1882
1883     /// Returns `true` if this `Place` contains a `Deref` projection.
1884     ///
1885     /// If `Place::is_indirect` returns false, the caller knows that the `Place` refers to the
1886     /// same region of memory as its base.
1887     pub fn is_indirect(&self) -> bool {
1888         self.projection.iter().any(|elem| elem.is_indirect())
1889     }
1890
1891     /// Finds the innermost `Local` from this `Place`, *if* it is either a local itself or
1892     /// a single deref of a local.
1893     //
1894     // FIXME: can we safely swap the semantics of `fn base_local` below in here instead?
1895     pub fn local_or_deref_local(&self) -> Option<Local> {
1896         match self.as_ref() {
1897             PlaceRef {
1898                 base: &PlaceBase::Local(local),
1899                 projection: &[],
1900             } |
1901             PlaceRef {
1902                 base: &PlaceBase::Local(local),
1903                 projection: &[ProjectionElem::Deref],
1904             } => Some(local),
1905             _ => None,
1906         }
1907     }
1908
1909     /// If this place represents a local variable like `_X` with no
1910     /// projections, return `Some(_X)`.
1911     pub fn as_local(&self) -> Option<Local> {
1912         self.as_ref().as_local()
1913     }
1914
1915     pub fn as_ref(&self) -> PlaceRef<'_, 'tcx> {
1916         PlaceRef {
1917             base: &self.base,
1918             projection: &self.projection,
1919         }
1920     }
1921 }
1922
1923 impl From<Local> for Place<'_> {
1924     fn from(local: Local) -> Self {
1925         Place {
1926             base: local.into(),
1927             projection: List::empty(),
1928         }
1929     }
1930 }
1931
1932 impl From<Local> for PlaceBase<'_> {
1933     fn from(local: Local) -> Self {
1934         PlaceBase::Local(local)
1935     }
1936 }
1937
1938 impl<'a, 'tcx> PlaceRef<'a, 'tcx> {
1939     /// Finds the innermost `Local` from this `Place`, *if* it is either a local itself or
1940     /// a single deref of a local.
1941     //
1942     // FIXME: can we safely swap the semantics of `fn base_local` below in here instead?
1943     pub fn local_or_deref_local(&self) -> Option<Local> {
1944         match self {
1945             PlaceRef {
1946                 base: PlaceBase::Local(local),
1947                 projection: [],
1948             } |
1949             PlaceRef {
1950                 base: PlaceBase::Local(local),
1951                 projection: [ProjectionElem::Deref],
1952             } => Some(*local),
1953             _ => None,
1954         }
1955     }
1956
1957     /// If this place represents a local variable like `_X` with no
1958     /// projections, return `Some(_X)`.
1959     pub fn as_local(&self) -> Option<Local> {
1960         match self {
1961             PlaceRef { base: PlaceBase::Local(l), projection: [] } => Some(*l),
1962             _ => None,
1963         }
1964     }
1965 }
1966
1967 impl Debug for Place<'_> {
1968     fn fmt(&self, fmt: &mut Formatter<'_>) -> fmt::Result {
1969         for elem in self.projection.iter().rev() {
1970             match elem {
1971                 ProjectionElem::Downcast(_, _) | ProjectionElem::Field(_, _) => {
1972                     write!(fmt, "(").unwrap();
1973                 }
1974                 ProjectionElem::Deref => {
1975                     write!(fmt, "(*").unwrap();
1976                 }
1977                 ProjectionElem::Index(_)
1978                 | ProjectionElem::ConstantIndex { .. }
1979                 | ProjectionElem::Subslice { .. } => {}
1980             }
1981         }
1982
1983         write!(fmt, "{:?}", self.base)?;
1984
1985         for elem in self.projection.iter() {
1986             match elem {
1987                 ProjectionElem::Downcast(Some(name), _index) => {
1988                     write!(fmt, " as {})", name)?;
1989                 }
1990                 ProjectionElem::Downcast(None, index) => {
1991                     write!(fmt, " as variant#{:?})", index)?;
1992                 }
1993                 ProjectionElem::Deref => {
1994                     write!(fmt, ")")?;
1995                 }
1996                 ProjectionElem::Field(field, ty) => {
1997                     write!(fmt, ".{:?}: {:?})", field.index(), ty)?;
1998                 }
1999                 ProjectionElem::Index(ref index) => {
2000                     write!(fmt, "[{:?}]", index)?;
2001                 }
2002                 ProjectionElem::ConstantIndex { offset, min_length, from_end: false } => {
2003                     write!(fmt, "[{:?} of {:?}]", offset, min_length)?;
2004                 }
2005                 ProjectionElem::ConstantIndex { offset, min_length, from_end: true } => {
2006                     write!(fmt, "[-{:?} of {:?}]", offset, min_length)?;
2007                 }
2008                 ProjectionElem::Subslice { from, to } if *to == 0 => {
2009                     write!(fmt, "[{:?}:]", from)?;
2010                 }
2011                 ProjectionElem::Subslice { from, to } if *from == 0 => {
2012                     write!(fmt, "[:-{:?}]", to)?;
2013                 }
2014                 ProjectionElem::Subslice { from, to } => {
2015                     write!(fmt, "[{:?}:-{:?}]", from, to)?;
2016                 }
2017             }
2018         }
2019
2020         Ok(())
2021     }
2022 }
2023
2024 impl Debug for PlaceBase<'_> {
2025     fn fmt(&self, fmt: &mut Formatter<'_>) -> fmt::Result {
2026         match *self {
2027             PlaceBase::Local(id) => write!(fmt, "{:?}", id),
2028             PlaceBase::Static(box self::Static { ty, kind: StaticKind::Static, def_id }) => {
2029                 write!(fmt, "({}: {:?})", ty::tls::with(|tcx| tcx.def_path_str(def_id)), ty)
2030             }
2031             PlaceBase::Static(box self::Static {
2032                 ty, kind: StaticKind::Promoted(promoted, _), def_id: _
2033             }) => {
2034                 write!(fmt, "({:?}: {:?})", promoted, ty)
2035             }
2036         }
2037     }
2038 }
2039
2040 ///////////////////////////////////////////////////////////////////////////
2041 // Scopes
2042
2043 rustc_index::newtype_index! {
2044     pub struct SourceScope {
2045         derive [HashStable]
2046         DEBUG_FORMAT = "scope[{}]",
2047         const OUTERMOST_SOURCE_SCOPE = 0,
2048     }
2049 }
2050
2051 #[derive(Clone, Debug, RustcEncodable, RustcDecodable, HashStable)]
2052 pub struct SourceScopeData {
2053     pub span: Span,
2054     pub parent_scope: Option<SourceScope>,
2055
2056     /// Crate-local information for this source scope, that can't (and
2057     /// needn't) be tracked across crates.
2058     pub local_data: ClearCrossCrate<SourceScopeLocalData>,
2059 }
2060
2061 #[derive(Clone, Debug, RustcEncodable, RustcDecodable, HashStable)]
2062 pub struct SourceScopeLocalData {
2063     /// An `HirId` with lint levels equivalent to this scope's lint levels.
2064     pub lint_root: hir::HirId,
2065     /// The unsafe block that contains this node.
2066     pub safety: Safety,
2067 }
2068
2069 ///////////////////////////////////////////////////////////////////////////
2070 // Operands
2071
2072 /// These are values that can appear inside an rvalue. They are intentionally
2073 /// limited to prevent rvalues from being nested in one another.
2074 #[derive(Clone, PartialEq, RustcEncodable, RustcDecodable, HashStable)]
2075 pub enum Operand<'tcx> {
2076     /// Copy: The value must be available for use afterwards.
2077     ///
2078     /// This implies that the type of the place must be `Copy`; this is true
2079     /// by construction during build, but also checked by the MIR type checker.
2080     Copy(Place<'tcx>),
2081
2082     /// Move: The value (including old borrows of it) will not be used again.
2083     ///
2084     /// Safe for values of all types (modulo future developments towards `?Move`).
2085     /// Correct usage patterns are enforced by the borrow checker for safe code.
2086     /// `Copy` may be converted to `Move` to enable "last-use" optimizations.
2087     Move(Place<'tcx>),
2088
2089     /// Synthesizes a constant value.
2090     Constant(Box<Constant<'tcx>>),
2091 }
2092
2093 impl<'tcx> Debug for Operand<'tcx> {
2094     fn fmt(&self, fmt: &mut Formatter<'_>) -> fmt::Result {
2095         use self::Operand::*;
2096         match *self {
2097             Constant(ref a) => write!(fmt, "{:?}", a),
2098             Copy(ref place) => write!(fmt, "{:?}", place),
2099             Move(ref place) => write!(fmt, "move {:?}", place),
2100         }
2101     }
2102 }
2103
2104 impl<'tcx> Operand<'tcx> {
2105     /// Convenience helper to make a constant that refers to the fn
2106     /// with given `DefId` and substs. Since this is used to synthesize
2107     /// MIR, assumes `user_ty` is None.
2108     pub fn function_handle(
2109         tcx: TyCtxt<'tcx>,
2110         def_id: DefId,
2111         substs: SubstsRef<'tcx>,
2112         span: Span,
2113     ) -> Self {
2114         let ty = tcx.type_of(def_id).subst(tcx, substs);
2115         Operand::Constant(box Constant {
2116             span,
2117             user_ty: None,
2118             literal: ty::Const::zero_sized(tcx, ty),
2119         })
2120     }
2121
2122     pub fn to_copy(&self) -> Self {
2123         match *self {
2124             Operand::Copy(_) | Operand::Constant(_) => self.clone(),
2125             Operand::Move(ref place) => Operand::Copy(place.clone()),
2126         }
2127     }
2128 }
2129
2130 ///////////////////////////////////////////////////////////////////////////
2131 /// Rvalues
2132
2133 #[derive(Clone, RustcEncodable, RustcDecodable, HashStable, PartialEq)]
2134 pub enum Rvalue<'tcx> {
2135     /// x (either a move or copy, depending on type of x)
2136     Use(Operand<'tcx>),
2137
2138     /// [x; 32]
2139     Repeat(Operand<'tcx>, u64),
2140
2141     /// &x or &mut x
2142     Ref(Region<'tcx>, BorrowKind, Place<'tcx>),
2143
2144     /// length of a [X] or [X;n] value
2145     Len(Place<'tcx>),
2146
2147     Cast(CastKind, Operand<'tcx>, Ty<'tcx>),
2148
2149     BinaryOp(BinOp, Operand<'tcx>, Operand<'tcx>),
2150     CheckedBinaryOp(BinOp, Operand<'tcx>, Operand<'tcx>),
2151
2152     NullaryOp(NullOp, Ty<'tcx>),
2153     UnaryOp(UnOp, Operand<'tcx>),
2154
2155     /// Read the discriminant of an ADT.
2156     ///
2157     /// Undefined (i.e., no effort is made to make it defined, but there’s no reason why it cannot
2158     /// be defined to return, say, a 0) if ADT is not an enum.
2159     Discriminant(Place<'tcx>),
2160
2161     /// Creates an aggregate value, like a tuple or struct. This is
2162     /// only needed because we want to distinguish `dest = Foo { x:
2163     /// ..., y: ... }` from `dest.x = ...; dest.y = ...;` in the case
2164     /// that `Foo` has a destructor. These rvalues can be optimized
2165     /// away after type-checking and before lowering.
2166     Aggregate(Box<AggregateKind<'tcx>>, Vec<Operand<'tcx>>),
2167 }
2168
2169 #[derive(Clone, Copy, Debug, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable)]
2170 pub enum CastKind {
2171     Misc,
2172     Pointer(PointerCast),
2173 }
2174
2175 #[derive(Clone, Debug, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable)]
2176 pub enum AggregateKind<'tcx> {
2177     /// The type is of the element
2178     Array(Ty<'tcx>),
2179     Tuple,
2180
2181     /// The second field is the variant index. It's equal to 0 for struct
2182     /// and union expressions. The fourth field is
2183     /// active field number and is present only for union expressions
2184     /// -- e.g., for a union expression `SomeUnion { c: .. }`, the
2185     /// active field index would identity the field `c`
2186     Adt(&'tcx AdtDef, VariantIdx, SubstsRef<'tcx>, Option<UserTypeAnnotationIndex>, Option<usize>),
2187
2188     Closure(DefId, SubstsRef<'tcx>),
2189     Generator(DefId, SubstsRef<'tcx>, hir::Movability),
2190 }
2191
2192 #[derive(Copy, Clone, Debug, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable)]
2193 pub enum BinOp {
2194     /// The `+` operator (addition)
2195     Add,
2196     /// The `-` operator (subtraction)
2197     Sub,
2198     /// The `*` operator (multiplication)
2199     Mul,
2200     /// The `/` operator (division)
2201     Div,
2202     /// The `%` operator (modulus)
2203     Rem,
2204     /// The `^` operator (bitwise xor)
2205     BitXor,
2206     /// The `&` operator (bitwise and)
2207     BitAnd,
2208     /// The `|` operator (bitwise or)
2209     BitOr,
2210     /// The `<<` operator (shift left)
2211     Shl,
2212     /// The `>>` operator (shift right)
2213     Shr,
2214     /// The `==` operator (equality)
2215     Eq,
2216     /// The `<` operator (less than)
2217     Lt,
2218     /// The `<=` operator (less than or equal to)
2219     Le,
2220     /// The `!=` operator (not equal to)
2221     Ne,
2222     /// The `>=` operator (greater than or equal to)
2223     Ge,
2224     /// The `>` operator (greater than)
2225     Gt,
2226     /// The `ptr.offset` operator
2227     Offset,
2228 }
2229
2230 impl BinOp {
2231     pub fn is_checkable(self) -> bool {
2232         use self::BinOp::*;
2233         match self {
2234             Add | Sub | Mul | Shl | Shr => true,
2235             _ => false,
2236         }
2237     }
2238 }
2239
2240 #[derive(Copy, Clone, Debug, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable)]
2241 pub enum NullOp {
2242     /// Returns the size of a value of that type
2243     SizeOf,
2244     /// Creates a new uninitialized box for a value of that type
2245     Box,
2246 }
2247
2248 #[derive(Copy, Clone, Debug, PartialEq, Eq, RustcEncodable, RustcDecodable, HashStable)]
2249 pub enum UnOp {
2250     /// The `!` operator for logical inversion
2251     Not,
2252     /// The `-` operator for negation
2253     Neg,
2254 }
2255
2256 impl<'tcx> Debug for Rvalue<'tcx> {
2257     fn fmt(&self, fmt: &mut Formatter<'_>) -> fmt::Result {
2258         use self::Rvalue::*;
2259
2260         match *self {
2261             Use(ref place) => write!(fmt, "{:?}", place),
2262             Repeat(ref a, ref b) => write!(fmt, "[{:?}; {:?}]", a, b),
2263             Len(ref a) => write!(fmt, "Len({:?})", a),
2264             Cast(ref kind, ref place, ref ty) => {
2265                 write!(fmt, "{:?} as {:?} ({:?})", place, ty, kind)
2266             }
2267             BinaryOp(ref op, ref a, ref b) => write!(fmt, "{:?}({:?}, {:?})", op, a, b),
2268             CheckedBinaryOp(ref op, ref a, ref b) => {
2269                 write!(fmt, "Checked{:?}({:?}, {:?})", op, a, b)
2270             }
2271             UnaryOp(ref op, ref a) => write!(fmt, "{:?}({:?})", op, a),
2272             Discriminant(ref place) => write!(fmt, "discriminant({:?})", place),
2273             NullaryOp(ref op, ref t) => write!(fmt, "{:?}({:?})", op, t),
2274             Ref(region, borrow_kind, ref place) => {
2275                 let kind_str = match borrow_kind {
2276                     BorrowKind::Shared => "",
2277                     BorrowKind::Shallow => "shallow ",
2278                     BorrowKind::Mut { .. } | BorrowKind::Unique => "mut ",
2279                 };
2280
2281                 // When printing regions, add trailing space if necessary.
2282                 let print_region = ty::tls::with(|tcx| {
2283                     tcx.sess.verbose() || tcx.sess.opts.debugging_opts.identify_regions
2284                 });
2285                 let region = if print_region {
2286                     let mut region = region.to_string();
2287                     if region.len() > 0 {
2288                         region.push(' ');
2289                     }
2290                     region
2291                 } else {
2292                     // Do not even print 'static
2293                     String::new()
2294                 };
2295                 write!(fmt, "&{}{}{:?}", region, kind_str, place)
2296             }
2297
2298             Aggregate(ref kind, ref places) => {
2299                 fn fmt_tuple(fmt: &mut Formatter<'_>, places: &[Operand<'_>]) -> fmt::Result {
2300                     let mut tuple_fmt = fmt.debug_tuple("");
2301                     for place in places {
2302                         tuple_fmt.field(place);
2303                     }
2304                     tuple_fmt.finish()
2305                 }
2306
2307                 match **kind {
2308                     AggregateKind::Array(_) => write!(fmt, "{:?}", places),
2309
2310                     AggregateKind::Tuple => match places.len() {
2311                         0 => write!(fmt, "()"),
2312                         1 => write!(fmt, "({:?},)", places[0]),
2313                         _ => fmt_tuple(fmt, places),
2314                     },
2315
2316                     AggregateKind::Adt(adt_def, variant, substs, _user_ty, _) => {
2317                         let variant_def = &adt_def.variants[variant];
2318
2319                         let f = &mut *fmt;
2320                         ty::tls::with(|tcx| {
2321                             let substs = tcx.lift(&substs).expect("could not lift for printing");
2322                             FmtPrinter::new(tcx, f, Namespace::ValueNS)
2323                                 .print_def_path(variant_def.def_id, substs)?;
2324                             Ok(())
2325                         })?;
2326
2327                         match variant_def.ctor_kind {
2328                             CtorKind::Const => Ok(()),
2329                             CtorKind::Fn => fmt_tuple(fmt, places),
2330                             CtorKind::Fictive => {
2331                                 let mut struct_fmt = fmt.debug_struct("");
2332                                 for (field, place) in variant_def.fields.iter().zip(places) {
2333                                     struct_fmt.field(&field.ident.as_str(), place);
2334                                 }
2335                                 struct_fmt.finish()
2336                             }
2337                         }
2338                     }
2339
2340                     AggregateKind::Closure(def_id, substs) => ty::tls::with(|tcx| {
2341                         if let Some(hir_id) = tcx.hir().as_local_hir_id(def_id) {
2342                             let name = if tcx.sess.opts.debugging_opts.span_free_formats {
2343                                 let substs = tcx.lift(&substs).unwrap();
2344                                 format!(
2345                                     "[closure@{}]",
2346                                     tcx.def_path_str_with_substs(def_id, substs),
2347                                 )
2348                             } else {
2349                                 format!("[closure@{:?}]", tcx.hir().span(hir_id))
2350                             };
2351                             let mut struct_fmt = fmt.debug_struct(&name);
2352
2353                             if let Some(upvars) = tcx.upvars(def_id) {
2354                                 for (&var_id, place) in upvars.keys().zip(places) {
2355                                     let var_name = tcx.hir().name(var_id);
2356                                     struct_fmt.field(&var_name.as_str(), place);
2357                                 }
2358                             }
2359
2360                             struct_fmt.finish()
2361                         } else {
2362                             write!(fmt, "[closure]")
2363                         }
2364                     }),
2365
2366                     AggregateKind::Generator(def_id, _, _) => ty::tls::with(|tcx| {
2367                         if let Some(hir_id) = tcx.hir().as_local_hir_id(def_id) {
2368                             let name = format!("[generator@{:?}]", tcx.hir().span(hir_id));
2369                             let mut struct_fmt = fmt.debug_struct(&name);
2370
2371                             if let Some(upvars) = tcx.upvars(def_id) {
2372                                 for (&var_id, place) in upvars.keys().zip(places) {
2373                                     let var_name = tcx.hir().name(var_id);
2374                                     struct_fmt.field(&var_name.as_str(), place);
2375                                 }
2376                             }
2377
2378                             struct_fmt.finish()
2379                         } else {
2380                             write!(fmt, "[generator]")
2381                         }
2382                     }),
2383                 }
2384             }
2385         }
2386     }
2387 }
2388
2389 ///////////////////////////////////////////////////////////////////////////
2390 /// Constants
2391 ///
2392 /// Two constants are equal if they are the same constant. Note that
2393 /// this does not necessarily mean that they are "==" in Rust -- in
2394 /// particular one must be wary of `NaN`!
2395
2396 #[derive(Clone, PartialEq, RustcEncodable, RustcDecodable, HashStable)]
2397 pub struct Constant<'tcx> {
2398     pub span: Span,
2399
2400     /// Optional user-given type: for something like
2401     /// `collect::<Vec<_>>`, this would be present and would
2402     /// indicate that `Vec<_>` was explicitly specified.
2403     ///
2404     /// Needed for NLL to impose user-given type constraints.
2405     pub user_ty: Option<UserTypeAnnotationIndex>,
2406
2407     pub literal: &'tcx ty::Const<'tcx>,
2408 }
2409
2410 impl Constant<'tcx> {
2411     pub fn check_static_ptr(&self, tcx: TyCtxt<'_>) -> Option<DefId> {
2412         match self.literal.val.try_to_scalar() {
2413             Some(Scalar::Ptr(ptr)) => match tcx.alloc_map.lock().get(ptr.alloc_id) {
2414                 Some(GlobalAlloc::Static(def_id)) => Some(def_id),
2415                 Some(_) => None,
2416                 None => {
2417                     tcx.sess.delay_span_bug(
2418                         DUMMY_SP, "MIR cannot contain dangling const pointers",
2419                     );
2420                     None
2421                 },
2422             },
2423             _ => None,
2424         }
2425     }
2426 }
2427
2428 /// A collection of projections into user types.
2429 ///
2430 /// They are projections because a binding can occur a part of a
2431 /// parent pattern that has been ascribed a type.
2432 ///
2433 /// Its a collection because there can be multiple type ascriptions on
2434 /// the path from the root of the pattern down to the binding itself.
2435 ///
2436 /// An example:
2437 ///
2438 /// ```rust
2439 /// struct S<'a>((i32, &'a str), String);
2440 /// let S((_, w): (i32, &'static str), _): S = ...;
2441 /// //    ------  ^^^^^^^^^^^^^^^^^^^ (1)
2442 /// //  ---------------------------------  ^ (2)
2443 /// ```
2444 ///
2445 /// The highlights labelled `(1)` show the subpattern `(_, w)` being
2446 /// ascribed the type `(i32, &'static str)`.
2447 ///
2448 /// The highlights labelled `(2)` show the whole pattern being
2449 /// ascribed the type `S`.
2450 ///
2451 /// In this example, when we descend to `w`, we will have built up the
2452 /// following two projected types:
2453 ///
2454 ///   * base: `S`,                   projection: `(base.0).1`
2455 ///   * base: `(i32, &'static str)`, projection: `base.1`
2456 ///
2457 /// The first will lead to the constraint `w: &'1 str` (for some
2458 /// inferred region `'1`). The second will lead to the constraint `w:
2459 /// &'static str`.
2460 #[derive(Clone, Debug, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
2461 pub struct UserTypeProjections {
2462     pub(crate) contents: Vec<(UserTypeProjection, Span)>,
2463 }
2464
2465 impl<'tcx> UserTypeProjections {
2466     pub fn none() -> Self {
2467         UserTypeProjections { contents: vec![] }
2468     }
2469
2470     pub fn from_projections(projs: impl Iterator<Item = (UserTypeProjection, Span)>) -> Self {
2471         UserTypeProjections { contents: projs.collect() }
2472     }
2473
2474     pub fn projections_and_spans(&self) -> impl Iterator<Item = &(UserTypeProjection, Span)> {
2475         self.contents.iter()
2476     }
2477
2478     pub fn projections(&self) -> impl Iterator<Item = &UserTypeProjection> {
2479         self.contents.iter().map(|&(ref user_type, _span)| user_type)
2480     }
2481
2482     pub fn push_projection(mut self, user_ty: &UserTypeProjection, span: Span) -> Self {
2483         self.contents.push((user_ty.clone(), span));
2484         self
2485     }
2486
2487     fn map_projections(
2488         mut self,
2489         mut f: impl FnMut(UserTypeProjection) -> UserTypeProjection,
2490     ) -> Self {
2491         self.contents = self.contents.drain(..).map(|(proj, span)| (f(proj), span)).collect();
2492         self
2493     }
2494
2495     pub fn index(self) -> Self {
2496         self.map_projections(|pat_ty_proj| pat_ty_proj.index())
2497     }
2498
2499     pub fn subslice(self, from: u32, to: u32) -> Self {
2500         self.map_projections(|pat_ty_proj| pat_ty_proj.subslice(from, to))
2501     }
2502
2503     pub fn deref(self) -> Self {
2504         self.map_projections(|pat_ty_proj| pat_ty_proj.deref())
2505     }
2506
2507     pub fn leaf(self, field: Field) -> Self {
2508         self.map_projections(|pat_ty_proj| pat_ty_proj.leaf(field))
2509     }
2510
2511     pub fn variant(self, adt_def: &'tcx AdtDef, variant_index: VariantIdx, field: Field) -> Self {
2512         self.map_projections(|pat_ty_proj| pat_ty_proj.variant(adt_def, variant_index, field))
2513     }
2514 }
2515
2516 /// Encodes the effect of a user-supplied type annotation on the
2517 /// subcomponents of a pattern. The effect is determined by applying the
2518 /// given list of proejctions to some underlying base type. Often,
2519 /// the projection element list `projs` is empty, in which case this
2520 /// directly encodes a type in `base`. But in the case of complex patterns with
2521 /// subpatterns and bindings, we want to apply only a *part* of the type to a variable,
2522 /// in which case the `projs` vector is used.
2523 ///
2524 /// Examples:
2525 ///
2526 /// * `let x: T = ...` -- here, the `projs` vector is empty.
2527 ///
2528 /// * `let (x, _): T = ...` -- here, the `projs` vector would contain
2529 ///   `field[0]` (aka `.0`), indicating that the type of `s` is
2530 ///   determined by finding the type of the `.0` field from `T`.
2531 #[derive(Clone, Debug, RustcEncodable, RustcDecodable, HashStable, PartialEq)]
2532 pub struct UserTypeProjection {
2533     pub base: UserTypeAnnotationIndex,
2534     pub projs: Vec<ProjectionKind>,
2535 }
2536
2537 impl Copy for ProjectionKind {}
2538
2539 impl UserTypeProjection {
2540     pub(crate) fn index(mut self) -> Self {
2541         self.projs.push(ProjectionElem::Index(()));
2542         self
2543     }
2544
2545     pub(crate) fn subslice(mut self, from: u32, to: u32) -> Self {
2546         self.projs.push(ProjectionElem::Subslice { from, to });
2547         self
2548     }
2549
2550     pub(crate) fn deref(mut self) -> Self {
2551         self.projs.push(ProjectionElem::Deref);
2552         self
2553     }
2554
2555     pub(crate) fn leaf(mut self, field: Field) -> Self {
2556         self.projs.push(ProjectionElem::Field(field, ()));
2557         self
2558     }
2559
2560     pub(crate) fn variant(
2561         mut self,
2562         adt_def: &'tcx AdtDef,
2563         variant_index: VariantIdx,
2564         field: Field,
2565     ) -> Self {
2566         self.projs.push(ProjectionElem::Downcast(
2567             Some(adt_def.variants[variant_index].ident.name),
2568             variant_index,
2569         ));
2570         self.projs.push(ProjectionElem::Field(field, ()));
2571         self
2572     }
2573 }
2574
2575 CloneTypeFoldableAndLiftImpls! { ProjectionKind, }
2576
2577 impl<'tcx> TypeFoldable<'tcx> for UserTypeProjection {
2578     fn super_fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Self {
2579         use crate::mir::ProjectionElem::*;
2580
2581         let base = self.base.fold_with(folder);
2582         let projs: Vec<_> = self
2583             .projs
2584             .iter()
2585             .map(|elem| match elem {
2586                 Deref => Deref,
2587                 Field(f, ()) => Field(f.clone(), ()),
2588                 Index(()) => Index(()),
2589                 elem => elem.clone(),
2590             })
2591             .collect();
2592
2593         UserTypeProjection { base, projs }
2594     }
2595
2596     fn super_visit_with<Vs: TypeVisitor<'tcx>>(&self, visitor: &mut Vs) -> bool {
2597         self.base.visit_with(visitor)
2598         // Note: there's nothing in `self.proj` to visit.
2599     }
2600 }
2601
2602 rustc_index::newtype_index! {
2603     pub struct Promoted {
2604         derive [HashStable]
2605         DEBUG_FORMAT = "promoted[{}]"
2606     }
2607 }
2608
2609 impl<'tcx> Debug for Constant<'tcx> {
2610     fn fmt(&self, fmt: &mut Formatter<'_>) -> fmt::Result {
2611         write!(fmt, "{}", self)
2612     }
2613 }
2614
2615 impl<'tcx> Display for Constant<'tcx> {
2616     fn fmt(&self, fmt: &mut Formatter<'_>) -> fmt::Result {
2617         write!(fmt, "const ")?;
2618         // FIXME make the default pretty printing of raw pointers more detailed. Here we output the
2619         // debug representation of raw pointers, so that the raw pointers in the mir dump output are
2620         // detailed and just not '{pointer}'.
2621         if let ty::RawPtr(_) = self.literal.ty.kind {
2622             write!(fmt, "{:?} : {}", self.literal.val, self.literal.ty)
2623         } else {
2624             write!(fmt, "{}", self.literal)
2625         }
2626     }
2627 }
2628
2629 impl<'tcx> graph::DirectedGraph for Body<'tcx> {
2630     type Node = BasicBlock;
2631 }
2632
2633 impl<'tcx> graph::WithNumNodes for Body<'tcx> {
2634     fn num_nodes(&self) -> usize {
2635         self.basic_blocks.len()
2636     }
2637 }
2638
2639 impl<'tcx> graph::WithStartNode for Body<'tcx> {
2640     fn start_node(&self) -> Self::Node {
2641         START_BLOCK
2642     }
2643 }
2644
2645 impl<'tcx> graph::WithPredecessors for Body<'tcx> {
2646     fn predecessors(
2647         &self,
2648         node: Self::Node,
2649     ) -> <Self as GraphPredecessors<'_>>::Iter {
2650         self.predecessors_for(node).to_vec().into_iter()
2651     }
2652 }
2653
2654 impl<'tcx> graph::WithSuccessors for Body<'tcx> {
2655     fn successors(
2656         &self,
2657         node: Self::Node,
2658     ) -> <Self as GraphSuccessors<'_>>::Iter {
2659         self.basic_blocks[node].terminator().successors().cloned()
2660     }
2661 }
2662
2663 impl<'a, 'b> graph::GraphPredecessors<'b> for Body<'a> {
2664     type Item = BasicBlock;
2665     type Iter = IntoIter<BasicBlock>;
2666 }
2667
2668 impl<'a, 'b> graph::GraphSuccessors<'b> for Body<'a> {
2669     type Item = BasicBlock;
2670     type Iter = iter::Cloned<Successors<'b>>;
2671 }
2672
2673 #[derive(Copy, Clone, PartialEq, Eq, Hash, Ord, PartialOrd, HashStable)]
2674 pub struct Location {
2675     /// The block that the location is within.
2676     pub block: BasicBlock,
2677
2678     /// The location is the position of the start of the statement; or, if
2679     /// `statement_index` equals the number of statements, then the start of the
2680     /// terminator.
2681     pub statement_index: usize,
2682 }
2683
2684 impl fmt::Debug for Location {
2685     fn fmt(&self, fmt: &mut fmt::Formatter<'_>) -> fmt::Result {
2686         write!(fmt, "{:?}[{}]", self.block, self.statement_index)
2687     }
2688 }
2689
2690 impl Location {
2691     pub const START: Location = Location { block: START_BLOCK, statement_index: 0 };
2692
2693     /// Returns the location immediately after this one within the enclosing block.
2694     ///
2695     /// Note that if this location represents a terminator, then the
2696     /// resulting location would be out of bounds and invalid.
2697     pub fn successor_within_block(&self) -> Location {
2698         Location { block: self.block, statement_index: self.statement_index + 1 }
2699     }
2700
2701     /// Returns `true` if `other` is earlier in the control flow graph than `self`.
2702     pub fn is_predecessor_of<'tcx>(&self, other: Location, body: &Body<'tcx>) -> bool {
2703         // If we are in the same block as the other location and are an earlier statement
2704         // then we are a predecessor of `other`.
2705         if self.block == other.block && self.statement_index < other.statement_index {
2706             return true;
2707         }
2708
2709         // If we're in another block, then we want to check that block is a predecessor of `other`.
2710         let mut queue: Vec<BasicBlock> = body.predecessors_for(other.block).to_vec();
2711         let mut visited = FxHashSet::default();
2712
2713         while let Some(block) = queue.pop() {
2714             // If we haven't visited this block before, then make sure we visit it's predecessors.
2715             if visited.insert(block) {
2716                 queue.extend(body.predecessors_for(block).iter().cloned());
2717             } else {
2718                 continue;
2719             }
2720
2721             // If we found the block that `self` is in, then we are a predecessor of `other` (since
2722             // we found that block by looking at the predecessors of `other`).
2723             if self.block == block {
2724                 return true;
2725             }
2726         }
2727
2728         false
2729     }
2730
2731     pub fn dominates(&self, other: Location, dominators: &Dominators<BasicBlock>) -> bool {
2732         if self.block == other.block {
2733             self.statement_index <= other.statement_index
2734         } else {
2735             dominators.is_dominated_by(other.block, self.block)
2736         }
2737     }
2738 }
2739
2740 #[derive(Copy, Clone, PartialEq, RustcEncodable, RustcDecodable, HashStable)]
2741 pub enum UnsafetyViolationKind {
2742     General,
2743     /// Permitted both in `const fn`s and regular `fn`s.
2744     GeneralAndConstFn,
2745     BorrowPacked(hir::HirId),
2746 }
2747
2748 #[derive(Copy, Clone, PartialEq, RustcEncodable, RustcDecodable, HashStable)]
2749 pub struct UnsafetyViolation {
2750     pub source_info: SourceInfo,
2751     pub description: Symbol,
2752     pub details: Symbol,
2753     pub kind: UnsafetyViolationKind,
2754 }
2755
2756 #[derive(Clone, RustcEncodable, RustcDecodable, HashStable)]
2757 pub struct UnsafetyCheckResult {
2758     /// Violations that are propagated *upwards* from this function.
2759     pub violations: Lrc<[UnsafetyViolation]>,
2760     /// `unsafe` blocks in this function, along with whether they are used. This is
2761     /// used for the "unused_unsafe" lint.
2762     pub unsafe_blocks: Lrc<[(hir::HirId, bool)]>,
2763 }
2764
2765 rustc_index::newtype_index! {
2766     pub struct GeneratorSavedLocal {
2767         derive [HashStable]
2768         DEBUG_FORMAT = "_{}",
2769     }
2770 }
2771
2772 /// The layout of generator state.
2773 #[derive(Clone, Debug, RustcEncodable, RustcDecodable, HashStable, TypeFoldable)]
2774 pub struct GeneratorLayout<'tcx> {
2775     /// The type of every local stored inside the generator.
2776     pub field_tys: IndexVec<GeneratorSavedLocal, Ty<'tcx>>,
2777
2778     /// Which of the above fields are in each variant. Note that one field may
2779     /// be stored in multiple variants.
2780     pub variant_fields: IndexVec<VariantIdx, IndexVec<Field, GeneratorSavedLocal>>,
2781
2782     /// Which saved locals are storage-live at the same time. Locals that do not
2783     /// have conflicts with each other are allowed to overlap in the computed
2784     /// layout.
2785     pub storage_conflicts: BitMatrix<GeneratorSavedLocal, GeneratorSavedLocal>,
2786 }
2787
2788 #[derive(Clone, Debug, RustcEncodable, RustcDecodable, HashStable)]
2789 pub struct BorrowCheckResult<'tcx> {
2790     pub closure_requirements: Option<ClosureRegionRequirements<'tcx>>,
2791     pub used_mut_upvars: SmallVec<[Field; 8]>,
2792 }
2793
2794 /// The result of the `mir_const_qualif` query.
2795 ///
2796 /// Each field corresponds to an implementer of the `Qualif` trait in
2797 /// `librustc_mir/transform/check_consts/qualifs.rs`. See that file for more information on each
2798 /// `Qualif`.
2799 #[derive(Clone, Copy, Debug, Default, RustcEncodable, RustcDecodable, HashStable)]
2800 pub struct ConstQualifs {
2801     pub has_mut_interior: bool,
2802     pub needs_drop: bool,
2803 }
2804
2805 /// After we borrow check a closure, we are left with various
2806 /// requirements that we have inferred between the free regions that
2807 /// appear in the closure's signature or on its field types. These
2808 /// requirements are then verified and proved by the closure's
2809 /// creating function. This struct encodes those requirements.
2810 ///
2811 /// The requirements are listed as being between various
2812 /// `RegionVid`. The 0th region refers to `'static`; subsequent region
2813 /// vids refer to the free regions that appear in the closure (or
2814 /// generator's) type, in order of appearance. (This numbering is
2815 /// actually defined by the `UniversalRegions` struct in the NLL
2816 /// region checker. See for example
2817 /// `UniversalRegions::closure_mapping`.) Note that we treat the free
2818 /// regions in the closure's type "as if" they were erased, so their
2819 /// precise identity is not important, only their position.
2820 ///
2821 /// Example: If type check produces a closure with the closure substs:
2822 ///
2823 /// ```text
2824 /// ClosureSubsts = [
2825 ///     i8,                                  // the "closure kind"
2826 ///     for<'x> fn(&'a &'x u32) -> &'x u32,  // the "closure signature"
2827 ///     &'a String,                          // some upvar
2828 /// ]
2829 /// ```
2830 ///
2831 /// here, there is one unique free region (`'a`) but it appears
2832 /// twice. We would "renumber" each occurrence to a unique vid, as follows:
2833 ///
2834 /// ```text
2835 /// ClosureSubsts = [
2836 ///     i8,                                  // the "closure kind"
2837 ///     for<'x> fn(&'1 &'x u32) -> &'x u32,  // the "closure signature"
2838 ///     &'2 String,                          // some upvar
2839 /// ]
2840 /// ```
2841 ///
2842 /// Now the code might impose a requirement like `'1: '2`. When an
2843 /// instance of the closure is created, the corresponding free regions
2844 /// can be extracted from its type and constrained to have the given
2845 /// outlives relationship.
2846 ///
2847 /// In some cases, we have to record outlives requirements between
2848 /// types and regions as well. In that case, if those types include
2849 /// any regions, those regions are recorded as `ReClosureBound`
2850 /// instances assigned one of these same indices. Those regions will
2851 /// be substituted away by the creator. We use `ReClosureBound` in
2852 /// that case because the regions must be allocated in the global
2853 /// `TyCtxt`, and hence we cannot use `ReVar` (which is what we use
2854 /// internally within the rest of the NLL code).
2855 #[derive(Clone, Debug, RustcEncodable, RustcDecodable, HashStable)]
2856 pub struct ClosureRegionRequirements<'tcx> {
2857     /// The number of external regions defined on the closure. In our
2858     /// example above, it would be 3 -- one for `'static`, then `'1`
2859     /// and `'2`. This is just used for a sanity check later on, to
2860     /// make sure that the number of regions we see at the callsite
2861     /// matches.
2862     pub num_external_vids: usize,
2863
2864     /// Requirements between the various free regions defined in
2865     /// indices.
2866     pub outlives_requirements: Vec<ClosureOutlivesRequirement<'tcx>>,
2867 }
2868
2869 /// Indicates an outlives-constraint between a type or between two
2870 /// free regions declared on the closure.
2871 #[derive(Copy, Clone, Debug, RustcEncodable, RustcDecodable, HashStable)]
2872 pub struct ClosureOutlivesRequirement<'tcx> {
2873     // This region or type ...
2874     pub subject: ClosureOutlivesSubject<'tcx>,
2875
2876     // ... must outlive this one.
2877     pub outlived_free_region: ty::RegionVid,
2878
2879     // If not, report an error here ...
2880     pub blame_span: Span,
2881
2882     // ... due to this reason.
2883     pub category: ConstraintCategory,
2884 }
2885
2886 /// Outlives-constraints can be categorized to determine whether and why they
2887 /// are interesting (for error reporting). Order of variants indicates sort
2888 /// order of the category, thereby influencing diagnostic output.
2889 ///
2890 /// See also [rustc_mir::borrow_check::nll::constraints].
2891 #[derive(
2892     Copy,
2893     Clone,
2894     Debug,
2895     Eq,
2896     PartialEq,
2897     PartialOrd,
2898     Ord,
2899     Hash,
2900     RustcEncodable,
2901     RustcDecodable,
2902     HashStable,
2903 )]
2904 pub enum ConstraintCategory {
2905     Return,
2906     Yield,
2907     UseAsConst,
2908     UseAsStatic,
2909     TypeAnnotation,
2910     Cast,
2911
2912     /// A constraint that came from checking the body of a closure.
2913     ///
2914     /// We try to get the category that the closure used when reporting this.
2915     ClosureBounds,
2916     CallArgument,
2917     CopyBound,
2918     SizedBound,
2919     Assignment,
2920     OpaqueType,
2921
2922     /// A "boring" constraint (caused by the given location) is one that
2923     /// the user probably doesn't want to see described in diagnostics,
2924     /// because it is kind of an artifact of the type system setup.
2925     /// Example: `x = Foo { field: y }` technically creates
2926     /// intermediate regions representing the "type of `Foo { field: y
2927     /// }`", and data flows from `y` into those variables, but they
2928     /// are not very interesting. The assignment into `x` on the other
2929     /// hand might be.
2930     Boring,
2931     // Boring and applicable everywhere.
2932     BoringNoLocation,
2933
2934     /// A constraint that doesn't correspond to anything the user sees.
2935     Internal,
2936 }
2937
2938 /// The subject of a `ClosureOutlivesRequirement` -- that is, the thing
2939 /// that must outlive some region.
2940 #[derive(Copy, Clone, Debug, RustcEncodable, RustcDecodable, HashStable)]
2941 pub enum ClosureOutlivesSubject<'tcx> {
2942     /// Subject is a type, typically a type parameter, but could also
2943     /// be a projection. Indicates a requirement like `T: 'a` being
2944     /// passed to the caller, where the type here is `T`.
2945     ///
2946     /// The type here is guaranteed not to contain any free regions at
2947     /// present.
2948     Ty(Ty<'tcx>),
2949
2950     /// Subject is a free region from the closure. Indicates a requirement
2951     /// like `'a: 'b` being passed to the caller; the region here is `'a`.
2952     Region(ty::RegionVid),
2953 }
2954
2955 /*
2956  * `TypeFoldable` implementations for MIR types
2957 */
2958
2959 CloneTypeFoldableAndLiftImpls! {
2960     BlockTailInfo,
2961     MirPhase,
2962     Mutability,
2963     SourceInfo,
2964     FakeReadCause,
2965     RetagKind,
2966     SourceScope,
2967     SourceScopeData,
2968     SourceScopeLocalData,
2969     UserTypeAnnotationIndex,
2970 }
2971
2972 impl<'tcx> TypeFoldable<'tcx> for Terminator<'tcx> {
2973     fn super_fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Self {
2974         use crate::mir::TerminatorKind::*;
2975
2976         let kind = match self.kind {
2977             Goto { target } => Goto { target },
2978             SwitchInt { ref discr, switch_ty, ref values, ref targets } => SwitchInt {
2979                 discr: discr.fold_with(folder),
2980                 switch_ty: switch_ty.fold_with(folder),
2981                 values: values.clone(),
2982                 targets: targets.clone(),
2983             },
2984             Drop { ref location, target, unwind } => {
2985                 Drop { location: location.fold_with(folder), target, unwind }
2986             }
2987             DropAndReplace { ref location, ref value, target, unwind } => DropAndReplace {
2988                 location: location.fold_with(folder),
2989                 value: value.fold_with(folder),
2990                 target,
2991                 unwind,
2992             },
2993             Yield { ref value, resume, drop } => {
2994                 Yield { value: value.fold_with(folder), resume: resume, drop: drop }
2995             }
2996             Call { ref func, ref args, ref destination, cleanup, from_hir_call } => {
2997                 let dest =
2998                     destination.as_ref().map(|&(ref loc, dest)| (loc.fold_with(folder), dest));
2999
3000                 Call {
3001                     func: func.fold_with(folder),
3002                     args: args.fold_with(folder),
3003                     destination: dest,
3004                     cleanup,
3005                     from_hir_call,
3006                 }
3007             }
3008             Assert { ref cond, expected, ref msg, target, cleanup } => {
3009                 use PanicInfo::*;
3010                 let msg = match msg {
3011                     BoundsCheck { ref len, ref index } =>
3012                         BoundsCheck {
3013                             len: len.fold_with(folder),
3014                             index: index.fold_with(folder),
3015                         },
3016                     Panic { .. } | Overflow(_) | OverflowNeg | DivisionByZero | RemainderByZero |
3017                     ResumedAfterReturn(_) | ResumedAfterPanic(_)  =>
3018                         msg.clone(),
3019                 };
3020                 Assert { cond: cond.fold_with(folder), expected, msg, target, cleanup }
3021             }
3022             GeneratorDrop => GeneratorDrop,
3023             Resume => Resume,
3024             Abort => Abort,
3025             Return => Return,
3026             Unreachable => Unreachable,
3027             FalseEdges { real_target, imaginary_target } => {
3028                 FalseEdges { real_target, imaginary_target }
3029             }
3030             FalseUnwind { real_target, unwind } => FalseUnwind { real_target, unwind },
3031         };
3032         Terminator { source_info: self.source_info, kind }
3033     }
3034
3035     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
3036         use crate::mir::TerminatorKind::*;
3037
3038         match self.kind {
3039             SwitchInt { ref discr, switch_ty, .. } => {
3040                 discr.visit_with(visitor) || switch_ty.visit_with(visitor)
3041             }
3042             Drop { ref location, .. } => location.visit_with(visitor),
3043             DropAndReplace { ref location, ref value, .. } => {
3044                 location.visit_with(visitor) || value.visit_with(visitor)
3045             }
3046             Yield { ref value, .. } => value.visit_with(visitor),
3047             Call { ref func, ref args, ref destination, .. } => {
3048                 let dest = if let Some((ref loc, _)) = *destination {
3049                     loc.visit_with(visitor)
3050                 } else {
3051                     false
3052                 };
3053                 dest || func.visit_with(visitor) || args.visit_with(visitor)
3054             }
3055             Assert { ref cond, ref msg, .. } => {
3056                 if cond.visit_with(visitor) {
3057                     use PanicInfo::*;
3058                     match msg {
3059                         BoundsCheck { ref len, ref index } =>
3060                             len.visit_with(visitor) || index.visit_with(visitor),
3061                         Panic { .. } | Overflow(_) | OverflowNeg |
3062                         DivisionByZero | RemainderByZero |
3063                         ResumedAfterReturn(_) | ResumedAfterPanic(_) =>
3064                             false
3065                     }
3066                 } else {
3067                     false
3068                 }
3069             }
3070             Goto { .. }
3071             | Resume
3072             | Abort
3073             | Return
3074             | GeneratorDrop
3075             | Unreachable
3076             | FalseEdges { .. }
3077             | FalseUnwind { .. } => false,
3078         }
3079     }
3080 }
3081
3082 impl<'tcx> TypeFoldable<'tcx> for GeneratorKind {
3083     fn super_fold_with<F: TypeFolder<'tcx>>(&self, _: &mut F) -> Self {
3084         *self
3085     }
3086
3087     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, _: &mut V) -> bool {
3088         false
3089     }
3090 }
3091
3092 impl<'tcx> TypeFoldable<'tcx> for Place<'tcx> {
3093     fn super_fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Self {
3094         Place {
3095             base: self.base.fold_with(folder),
3096             projection: self.projection.fold_with(folder),
3097         }
3098     }
3099
3100     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
3101         self.base.visit_with(visitor) || self.projection.visit_with(visitor)
3102     }
3103 }
3104
3105 impl<'tcx> TypeFoldable<'tcx> for PlaceBase<'tcx> {
3106     fn super_fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Self {
3107         match self {
3108             PlaceBase::Local(local) => PlaceBase::Local(local.fold_with(folder)),
3109             PlaceBase::Static(static_) => PlaceBase::Static(static_.fold_with(folder)),
3110         }
3111     }
3112
3113     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
3114         match self {
3115             PlaceBase::Local(local) => local.visit_with(visitor),
3116             PlaceBase::Static(static_) => (**static_).visit_with(visitor),
3117         }
3118     }
3119 }
3120
3121 impl<'tcx> TypeFoldable<'tcx> for &'tcx ty::List<PlaceElem<'tcx>> {
3122     fn super_fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Self {
3123         let v = self.iter().map(|t| t.fold_with(folder)).collect::<Vec<_>>();
3124         folder.tcx().intern_place_elems(&v)
3125     }
3126
3127     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
3128         self.iter().any(|t| t.visit_with(visitor))
3129     }
3130 }
3131
3132 impl<'tcx> TypeFoldable<'tcx> for Static<'tcx> {
3133     fn super_fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Self {
3134         Static {
3135             ty: self.ty.fold_with(folder),
3136             kind: self.kind.fold_with(folder),
3137             def_id: self.def_id,
3138         }
3139     }
3140
3141     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
3142         let Static { ty, kind, def_id: _ } = self;
3143
3144         ty.visit_with(visitor) || kind.visit_with(visitor)
3145     }
3146 }
3147
3148 impl<'tcx> TypeFoldable<'tcx> for StaticKind<'tcx> {
3149     fn super_fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Self {
3150         match self {
3151             StaticKind::Promoted(promoted, substs) =>
3152                 StaticKind::Promoted(promoted.fold_with(folder), substs.fold_with(folder)),
3153             StaticKind::Static => StaticKind::Static
3154         }
3155     }
3156
3157     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
3158         match self {
3159             StaticKind::Promoted(promoted, substs) =>
3160                 promoted.visit_with(visitor) || substs.visit_with(visitor),
3161             StaticKind::Static => { false }
3162         }
3163     }
3164 }
3165
3166 impl<'tcx> TypeFoldable<'tcx> for Rvalue<'tcx> {
3167     fn super_fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Self {
3168         use crate::mir::Rvalue::*;
3169         match *self {
3170             Use(ref op) => Use(op.fold_with(folder)),
3171             Repeat(ref op, len) => Repeat(op.fold_with(folder), len),
3172             Ref(region, bk, ref place) => {
3173                 Ref(region.fold_with(folder), bk, place.fold_with(folder))
3174             }
3175             Len(ref place) => Len(place.fold_with(folder)),
3176             Cast(kind, ref op, ty) => Cast(kind, op.fold_with(folder), ty.fold_with(folder)),
3177             BinaryOp(op, ref rhs, ref lhs) => {
3178                 BinaryOp(op, rhs.fold_with(folder), lhs.fold_with(folder))
3179             }
3180             CheckedBinaryOp(op, ref rhs, ref lhs) => {
3181                 CheckedBinaryOp(op, rhs.fold_with(folder), lhs.fold_with(folder))
3182             }
3183             UnaryOp(op, ref val) => UnaryOp(op, val.fold_with(folder)),
3184             Discriminant(ref place) => Discriminant(place.fold_with(folder)),
3185             NullaryOp(op, ty) => NullaryOp(op, ty.fold_with(folder)),
3186             Aggregate(ref kind, ref fields) => {
3187                 let kind = box match **kind {
3188                     AggregateKind::Array(ty) => AggregateKind::Array(ty.fold_with(folder)),
3189                     AggregateKind::Tuple => AggregateKind::Tuple,
3190                     AggregateKind::Adt(def, v, substs, user_ty, n) => AggregateKind::Adt(
3191                         def,
3192                         v,
3193                         substs.fold_with(folder),
3194                         user_ty.fold_with(folder),
3195                         n,
3196                     ),
3197                     AggregateKind::Closure(id, substs) => {
3198                         AggregateKind::Closure(id, substs.fold_with(folder))
3199                     }
3200                     AggregateKind::Generator(id, substs, movablity) => {
3201                         AggregateKind::Generator(id, substs.fold_with(folder), movablity)
3202                     }
3203                 };
3204                 Aggregate(kind, fields.fold_with(folder))
3205             }
3206         }
3207     }
3208
3209     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
3210         use crate::mir::Rvalue::*;
3211         match *self {
3212             Use(ref op) => op.visit_with(visitor),
3213             Repeat(ref op, _) => op.visit_with(visitor),
3214             Ref(region, _, ref place) => region.visit_with(visitor) || place.visit_with(visitor),
3215             Len(ref place) => place.visit_with(visitor),
3216             Cast(_, ref op, ty) => op.visit_with(visitor) || ty.visit_with(visitor),
3217             BinaryOp(_, ref rhs, ref lhs) | CheckedBinaryOp(_, ref rhs, ref lhs) => {
3218                 rhs.visit_with(visitor) || lhs.visit_with(visitor)
3219             }
3220             UnaryOp(_, ref val) => val.visit_with(visitor),
3221             Discriminant(ref place) => place.visit_with(visitor),
3222             NullaryOp(_, ty) => ty.visit_with(visitor),
3223             Aggregate(ref kind, ref fields) => {
3224                 (match **kind {
3225                     AggregateKind::Array(ty) => ty.visit_with(visitor),
3226                     AggregateKind::Tuple => false,
3227                     AggregateKind::Adt(_, _, substs, user_ty, _) => {
3228                         substs.visit_with(visitor) || user_ty.visit_with(visitor)
3229                     }
3230                     AggregateKind::Closure(_, substs) => substs.visit_with(visitor),
3231                     AggregateKind::Generator(_, substs, _) => substs.visit_with(visitor),
3232                 }) || fields.visit_with(visitor)
3233             }
3234         }
3235     }
3236 }
3237
3238 impl<'tcx> TypeFoldable<'tcx> for Operand<'tcx> {
3239     fn super_fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Self {
3240         match *self {
3241             Operand::Copy(ref place) => Operand::Copy(place.fold_with(folder)),
3242             Operand::Move(ref place) => Operand::Move(place.fold_with(folder)),
3243             Operand::Constant(ref c) => Operand::Constant(c.fold_with(folder)),
3244         }
3245     }
3246
3247     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
3248         match *self {
3249             Operand::Copy(ref place) | Operand::Move(ref place) => place.visit_with(visitor),
3250             Operand::Constant(ref c) => c.visit_with(visitor),
3251         }
3252     }
3253 }
3254
3255 impl<'tcx> TypeFoldable<'tcx> for PlaceElem<'tcx> {
3256     fn super_fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Self {
3257         use crate::mir::ProjectionElem::*;
3258
3259         match self {
3260             Deref => Deref,
3261             Field(f, ty) => Field(*f, ty.fold_with(folder)),
3262             Index(v) => Index(v.fold_with(folder)),
3263             elem => elem.clone(),
3264         }
3265     }
3266
3267     fn super_visit_with<Vs: TypeVisitor<'tcx>>(&self, visitor: &mut Vs) -> bool {
3268         use crate::mir::ProjectionElem::*;
3269
3270         match self {
3271             Field(_, ty) => ty.visit_with(visitor),
3272             Index(v) => v.visit_with(visitor),
3273             _ => false,
3274         }
3275     }
3276 }
3277
3278 impl<'tcx> TypeFoldable<'tcx> for Field {
3279     fn super_fold_with<F: TypeFolder<'tcx>>(&self, _: &mut F) -> Self {
3280         *self
3281     }
3282     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, _: &mut V) -> bool {
3283         false
3284     }
3285 }
3286
3287 impl<'tcx> TypeFoldable<'tcx> for GeneratorSavedLocal {
3288     fn super_fold_with<F: TypeFolder<'tcx>>(&self, _: &mut F) -> Self {
3289         *self
3290     }
3291     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, _: &mut V) -> bool {
3292         false
3293     }
3294 }
3295
3296 impl<'tcx, R: Idx, C: Idx> TypeFoldable<'tcx> for BitMatrix<R, C> {
3297     fn super_fold_with<F: TypeFolder<'tcx>>(&self, _: &mut F) -> Self {
3298         self.clone()
3299     }
3300     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, _: &mut V) -> bool {
3301         false
3302     }
3303 }
3304
3305 impl<'tcx> TypeFoldable<'tcx> for Constant<'tcx> {
3306     fn super_fold_with<F: TypeFolder<'tcx>>(&self, folder: &mut F) -> Self {
3307         Constant {
3308             span: self.span.clone(),
3309             user_ty: self.user_ty.fold_with(folder),
3310             literal: self.literal.fold_with(folder),
3311         }
3312     }
3313     fn super_visit_with<V: TypeVisitor<'tcx>>(&self, visitor: &mut V) -> bool {
3314         self.literal.visit_with(visitor)
3315     }
3316 }