compiler/rustc_middle/src/mir/mod.rs

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