src/librustc/mir/mod.rs

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