src/librustc/mir/mod.rs

   1 // Copyright 2014 The Rust Project Developers. See the COPYRIGHT
   2 // file at the top-level directory of this distribution and at
   3 // http://rust-lang.org/COPYRIGHT.
   4 //
   5 // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
   6 // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
   7 // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
   8 // option. This file may not be copied, modified, or distributed
   9 // except according to those terms.
  10
  11 use graphviz::IntoCow;
  12 use middle::const_val::ConstVal;
  13 use rustc_const_math::{ConstUsize, ConstInt, ConstMathErr};
  14 use rustc_data_structures::indexed_vec::{IndexVec, Idx};
  15 use rustc_data_structures::control_flow_graph::dominators::{Dominators, dominators};
  16 use rustc_data_structures::control_flow_graph::{GraphPredecessors, GraphSuccessors};
  17 use rustc_data_structures::control_flow_graph::ControlFlowGraph;
  18 use hir::def::CtorKind;
  19 use hir::def_id::DefId;
  20 use ty::subst::Substs;
  21 use ty::{self, AdtDef, ClosureSubsts, Region, Ty};
  22 use util::ppaux;
  23 use rustc_back::slice;
  24 use hir::InlineAsm;
  25 use std::ascii;
  26 use std::borrow::{Cow};
  27 use std::cell::Ref;
  28 use std::fmt::{self, Debug, Formatter, Write};
  29 use std::{iter, u32};
  30 use std::ops::{Index, IndexMut};
  31 use std::vec::IntoIter;
  32 use syntax::ast::Name;
  33 use syntax_pos::Span;
  34
  35 mod cache;
  36 pub mod tcx;
  37 pub mod visit;
  38 pub mod transform;
  39 pub mod traversal;
  40
  41 macro_rules! newtype_index {
  42     ($name:ident, $debug_name:expr) => (
  43         #[derive(Copy, Clone, PartialEq, Eq, Hash, PartialOrd, Ord,
  44          RustcEncodable, RustcDecodable)]
  45         pub struct $name(u32);
  46
  47         impl Idx for $name {
  48             fn new(value: usize) -> Self {
  49                 assert!(value < (u32::MAX) as usize);
  50                 $name(value as u32)
  51             }
  52             fn index(self) -> usize {
  53                 self.0 as usize
  54             }
  55         }
  56
  57         impl Debug for $name {
  58             fn fmt(&self, fmt: &mut Formatter) -> fmt::Result {
  59                 write!(fmt, "{}{}", $debug_name, self.0)
  60             }
  61         }
  62     )
  63 }
  64
  65 /// Lowered representation of a single function.
  66 // Do not implement clone for Mir, its easy to do so accidently and its kind of expensive.
  67 #[derive(RustcEncodable, RustcDecodable, Debug)]
  68 pub struct Mir<'tcx> {
  69     /// List of basic blocks. References to basic block use a newtyped index type `BasicBlock`
  70     /// that indexes into this vector.
  71     basic_blocks: IndexVec<BasicBlock, BasicBlockData<'tcx>>,
  72
  73     /// List of visibility (lexical) scopes; these are referenced by statements
  74     /// and used (eventually) for debuginfo. Indexed by a `VisibilityScope`.
  75     pub visibility_scopes: IndexVec<VisibilityScope, VisibilityScopeData>,
  76
  77     /// Rvalues promoted from this function, such as borrows of constants.
  78     /// Each of them is the Mir of a constant with the fn's type parameters
  79     /// in scope, but a separate set of locals.
  80     pub promoted: IndexVec<Promoted, Mir<'tcx>>,
  81
  82     /// Return type of the function.
  83     pub return_ty: Ty<'tcx>,
  84
  85     /// Declarations of locals.
  86     ///
  87     /// The first local is the return value pointer, followed by `arg_count`
  88     /// locals for the function arguments, followed by any user-declared
  89     /// variables and temporaries.
  90     pub local_decls: IndexVec<Local, LocalDecl<'tcx>>,
  91
  92     /// Number of arguments this function takes.
  93     ///
  94     /// Starting at local 1, `arg_count` locals will be provided by the caller
  95     /// and can be assumed to be initialized.
  96     ///
  97     /// If this MIR was built for a constant, this will be 0.
  98     pub arg_count: usize,
  99
 100     /// Names and capture modes of all the closure upvars, assuming
 101     /// the first argument is either the closure or a reference to it.
 102     pub upvar_decls: Vec<UpvarDecl>,
 103
 104     /// Mark an argument local (which must be a tuple) as getting passed as
 105     /// its individual components at the LLVM level.
 106     ///
 107     /// This is used for the "rust-call" ABI.
 108     pub spread_arg: Option<Local>,
 109
 110     /// A span representing this MIR, for error reporting
 111     pub span: Span,
 112
 113     /// A cache for various calculations
 114     cache: cache::Cache
 115 }
 116
 117 /// where execution begins
 118 pub const START_BLOCK: BasicBlock = BasicBlock(0);
 119
 120 impl<'tcx> Mir<'tcx> {
 121     pub fn new(basic_blocks: IndexVec<BasicBlock, BasicBlockData<'tcx>>,
 122                visibility_scopes: IndexVec<VisibilityScope, VisibilityScopeData>,
 123                promoted: IndexVec<Promoted, Mir<'tcx>>,
 124                return_ty: Ty<'tcx>,
 125                local_decls: IndexVec<Local, LocalDecl<'tcx>>,
 126                arg_count: usize,
 127                upvar_decls: Vec<UpvarDecl>,
 128                span: Span) -> Self
 129     {
 130         // We need `arg_count` locals, and one for the return pointer
 131         assert!(local_decls.len() >= arg_count + 1,
 132             "expected at least {} locals, got {}", arg_count + 1, local_decls.len());
 133         assert_eq!(local_decls[RETURN_POINTER].ty, return_ty);
 134
 135         Mir {
 136             basic_blocks: basic_blocks,
 137             visibility_scopes: visibility_scopes,
 138             promoted: promoted,
 139             return_ty: return_ty,
 140             local_decls: local_decls,
 141             arg_count: arg_count,
 142             upvar_decls: upvar_decls,
 143             spread_arg: None,
 144             span: span,
 145             cache: cache::Cache::new()
 146         }
 147     }
 148
 149     #[inline]
 150     pub fn basic_blocks(&self) -> &IndexVec<BasicBlock, BasicBlockData<'tcx>> {
 151         &self.basic_blocks
 152     }
 153
 154     #[inline]
 155     pub fn basic_blocks_mut(&mut self) -> &mut IndexVec<BasicBlock, BasicBlockData<'tcx>> {
 156         self.cache.invalidate();
 157         &mut self.basic_blocks
 158     }
 159
 160     #[inline]
 161     pub fn predecessors(&self) -> Ref<IndexVec<BasicBlock, Vec<BasicBlock>>> {
 162         self.cache.predecessors(self)
 163     }
 164
 165     #[inline]
 166     pub fn predecessors_for(&self, bb: BasicBlock) -> Ref<Vec<BasicBlock>> {
 167         Ref::map(self.predecessors(), |p| &p[bb])
 168     }
 169
 170     #[inline]
 171     pub fn dominators(&self) -> Dominators<BasicBlock> {
 172         dominators(self)
 173     }
 174
 175     #[inline]
 176     pub fn local_kind(&self, local: Local) -> LocalKind {
 177         let index = local.0 as usize;
 178         if index == 0 {
 179             debug_assert!(self.local_decls[local].mutability == Mutability::Mut,
 180                           "return pointer should be mutable");
 181
 182             LocalKind::ReturnPointer
 183         } else if index < self.arg_count + 1 {
 184             LocalKind::Arg
 185         } else if self.local_decls[local].name.is_some() {
 186             LocalKind::Var
 187         } else {
 188             debug_assert!(self.local_decls[local].mutability == Mutability::Mut,
 189                           "temp should be mutable");
 190
 191             LocalKind::Temp
 192         }
 193     }
 194
 195     /// Returns an iterator over all temporaries.
 196     #[inline]
 197     pub fn temps_iter<'a>(&'a self) -> impl Iterator<Item=Local> + 'a {
 198         (self.arg_count+1..self.local_decls.len()).filter_map(move |index| {
 199             let local = Local::new(index);
 200             if self.local_decls[local].source_info.is_none() {
 201                 Some(local)
 202             } else {
 203                 None
 204             }
 205         })
 206     }
 207
 208     /// Returns an iterator over all user-declared locals.
 209     #[inline]
 210     pub fn vars_iter<'a>(&'a self) -> impl Iterator<Item=Local> + 'a {
 211         (self.arg_count+1..self.local_decls.len()).filter_map(move |index| {
 212             let local = Local::new(index);
 213             if self.local_decls[local].source_info.is_none() {
 214                 None
 215             } else {
 216                 Some(local)
 217             }
 218         })
 219     }
 220
 221     /// Returns an iterator over all function arguments.
 222     #[inline]
 223     pub fn args_iter(&self) -> impl Iterator<Item=Local> {
 224         let arg_count = self.arg_count;
 225         (1..arg_count+1).map(Local::new)
 226     }
 227
 228     /// Returns an iterator over all user-defined variables and compiler-generated temporaries (all
 229     /// locals that are neither arguments nor the return pointer).
 230     #[inline]
 231     pub fn vars_and_temps_iter(&self) -> impl Iterator<Item=Local> {
 232         let arg_count = self.arg_count;
 233         let local_count = self.local_decls.len();
 234         (arg_count+1..local_count).map(Local::new)
 235     }
 236
 237     /// Changes a statement to a nop. This is both faster than deleting instructions and avoids
 238     /// invalidating statement indices in `Location`s.
 239     pub fn make_statement_nop(&mut self, location: Location) {
 240         let block = &mut self[location.block];
 241         debug_assert!(location.statement_index < block.statements.len());
 242         block.statements[location.statement_index].make_nop()
 243     }
 244 }
 245
 246 impl<'tcx> Index<BasicBlock> for Mir<'tcx> {
 247     type Output = BasicBlockData<'tcx>;
 248
 249     #[inline]
 250     fn index(&self, index: BasicBlock) -> &BasicBlockData<'tcx> {
 251         &self.basic_blocks()[index]
 252     }
 253 }
 254
 255 impl<'tcx> IndexMut<BasicBlock> for Mir<'tcx> {
 256     #[inline]
 257     fn index_mut(&mut self, index: BasicBlock) -> &mut BasicBlockData<'tcx> {
 258         &mut self.basic_blocks_mut()[index]
 259     }
 260 }
 261
 262 /// Grouped information about the source code origin of a MIR entity.
 263 /// Intended to be inspected by diagnostics and debuginfo.
 264 /// Most passes can work with it as a whole, within a single function.
 265 #[derive(Copy, Clone, Debug, PartialEq, Eq, RustcEncodable, RustcDecodable)]
 266 pub struct SourceInfo {
 267     /// Source span for the AST pertaining to this MIR entity.
 268     pub span: Span,
 269
 270     /// The lexical visibility scope, i.e. which bindings can be seen.
 271     pub scope: VisibilityScope
 272 }
 273
 274 ///////////////////////////////////////////////////////////////////////////
 275 // Mutability and borrow kinds
 276
 277 #[derive(Copy, Clone, Debug, PartialEq, Eq, RustcEncodable, RustcDecodable)]
 278 pub enum Mutability {
 279     Mut,
 280     Not,
 281 }
 282
 283 #[derive(Copy, Clone, Debug, PartialEq, Eq, RustcEncodable, RustcDecodable)]
 284 pub enum BorrowKind {
 285     /// Data must be immutable and is aliasable.
 286     Shared,
 287
 288     /// Data must be immutable but not aliasable.  This kind of borrow
 289     /// cannot currently be expressed by the user and is used only in
 290     /// implicit closure bindings. It is needed when you the closure
 291     /// is borrowing or mutating a mutable referent, e.g.:
 292     ///
 293     ///    let x: &mut isize = ...;
 294     ///    let y = || *x += 5;
 295     ///
 296     /// If we were to try to translate this closure into a more explicit
 297     /// form, we'd encounter an error with the code as written:
 298     ///
 299     ///    struct Env { x: & &mut isize }
 300     ///    let x: &mut isize = ...;
 301     ///    let y = (&mut Env { &x }, fn_ptr);  // Closure is pair of env and fn
 302     ///    fn fn_ptr(env: &mut Env) { **env.x += 5; }
 303     ///
 304     /// This is then illegal because you cannot mutate a `&mut` found
 305     /// in an aliasable location. To solve, you'd have to translate with
 306     /// an `&mut` borrow:
 307     ///
 308     ///    struct Env { x: & &mut isize }
 309     ///    let x: &mut isize = ...;
 310     ///    let y = (&mut Env { &mut x }, fn_ptr); // changed from &x to &mut x
 311     ///    fn fn_ptr(env: &mut Env) { **env.x += 5; }
 312     ///
 313     /// Now the assignment to `**env.x` is legal, but creating a
 314     /// mutable pointer to `x` is not because `x` is not mutable. We
 315     /// could fix this by declaring `x` as `let mut x`. This is ok in
 316     /// user code, if awkward, but extra weird for closures, since the
 317     /// borrow is hidden.
 318     ///
 319     /// So we introduce a "unique imm" borrow -- the referent is
 320     /// immutable, but not aliasable. This solves the problem. For
 321     /// simplicity, we don't give users the way to express this
 322     /// borrow, it's just used when translating closures.
 323     Unique,
 324
 325     /// Data is mutable and not aliasable.
 326     Mut,
 327 }
 328
 329 ///////////////////////////////////////////////////////////////////////////
 330 // Variables and temps
 331
 332 newtype_index!(Local, "_");
 333
 334 pub const RETURN_POINTER: Local = Local(0);
 335
 336 /// Classifies locals into categories. See `Mir::local_kind`.
 337 #[derive(PartialEq, Eq, Debug)]
 338 pub enum LocalKind {
 339     /// User-declared variable binding
 340     Var,
 341     /// Compiler-introduced temporary
 342     Temp,
 343     /// Function argument
 344     Arg,
 345     /// Location of function's return value
 346     ReturnPointer,
 347 }
 348
 349 /// A MIR local.
 350 ///
 351 /// This can be a binding declared by the user, a temporary inserted by the compiler, a function
 352 /// argument, or the return pointer.
 353 #[derive(Clone, Debug, RustcEncodable, RustcDecodable)]
 354 pub struct LocalDecl<'tcx> {
 355     /// `let mut x` vs `let x`.
 356     ///
 357     /// Temporaries and the return pointer are always mutable.
 358     pub mutability: Mutability,
 359
 360     /// Type of this local.
 361     pub ty: Ty<'tcx>,
 362
 363     /// Name of the local, used in debuginfo and pretty-printing.
 364     ///
 365     /// Note that function arguments can also have this set to `Some(_)`
 366     /// to generate better debuginfo.
 367     pub name: Option<Name>,
 368
 369     /// For user-declared variables, stores their source information.
 370     ///
 371     /// For temporaries, this is `None`.
 372     ///
 373     /// This is the primary way to differentiate between user-declared
 374     /// variables and compiler-generated temporaries.
 375     pub source_info: Option<SourceInfo>,
 376 }
 377
 378 impl<'tcx> LocalDecl<'tcx> {
 379     /// Create a new `LocalDecl` for a temporary.
 380     #[inline]
 381     pub fn new_temp(ty: Ty<'tcx>) -> Self {
 382         LocalDecl {
 383             mutability: Mutability::Mut,
 384             ty: ty,
 385             name: None,
 386             source_info: None,
 387         }
 388     }
 389
 390     /// Builds a `LocalDecl` for the return pointer.
 391     ///
 392     /// This must be inserted into the `local_decls` list as the first local.
 393     #[inline]
 394     pub fn new_return_pointer(return_ty: Ty) -> LocalDecl {
 395         LocalDecl {
 396             mutability: Mutability::Mut,
 397             ty: return_ty,
 398             source_info: None,
 399             name: None,     // FIXME maybe we do want some name here?
 400         }
 401     }
 402 }
 403
 404 /// A closure capture, with its name and mode.
 405 #[derive(Clone, Debug, RustcEncodable, RustcDecodable)]
 406 pub struct UpvarDecl {
 407     pub debug_name: Name,
 408
 409     /// If true, the capture is behind a reference.
 410     pub by_ref: bool
 411 }
 412
 413 ///////////////////////////////////////////////////////////////////////////
 414 // BasicBlock
 415
 416 newtype_index!(BasicBlock, "bb");
 417
 418 ///////////////////////////////////////////////////////////////////////////
 419 // BasicBlockData and Terminator
 420
 421 #[derive(Clone, Debug, RustcEncodable, RustcDecodable)]
 422 pub struct BasicBlockData<'tcx> {
 423     /// List of statements in this block.
 424     pub statements: Vec<Statement<'tcx>>,
 425
 426     /// Terminator for this block.
 427     ///
 428     /// NB. This should generally ONLY be `None` during construction.
 429     /// Therefore, you should generally access it via the
 430     /// `terminator()` or `terminator_mut()` methods. The only
 431     /// exception is that certain passes, such as `simplify_cfg`, swap
 432     /// out the terminator temporarily with `None` while they continue
 433     /// to recurse over the set of basic blocks.
 434     pub terminator: Option<Terminator<'tcx>>,
 435
 436     /// If true, this block lies on an unwind path. This is used
 437     /// during trans where distinct kinds of basic blocks may be
 438     /// generated (particularly for MSVC cleanup). Unwind blocks must
 439     /// only branch to other unwind blocks.
 440     pub is_cleanup: bool,
 441 }
 442
 443 #[derive(Clone, Debug, RustcEncodable, RustcDecodable)]
 444 pub struct Terminator<'tcx> {
 445     pub source_info: SourceInfo,
 446     pub kind: TerminatorKind<'tcx>
 447 }
 448
 449 #[derive(Clone, RustcEncodable, RustcDecodable)]
 450 pub enum TerminatorKind<'tcx> {
 451     /// block should have one successor in the graph; we jump there
 452     Goto {
 453         target: BasicBlock,
 454     },
 455
 456     /// jump to branch 0 if this lvalue evaluates to true
 457     If {
 458         cond: Operand<'tcx>,
 459         targets: (BasicBlock, BasicBlock),
 460     },
 461
 462     /// lvalue evaluates to some enum; jump depending on the branch
 463     Switch {
 464         discr: Lvalue<'tcx>,
 465         adt_def: &'tcx AdtDef,
 466         targets: Vec<BasicBlock>,
 467     },
 468
 469     /// operand evaluates to an integer; jump depending on its value
 470     /// to one of the targets, and otherwise fallback to `otherwise`
 471     SwitchInt {
 472         /// discriminant value being tested
 473         discr: Lvalue<'tcx>,
 474
 475         /// type of value being tested
 476         switch_ty: Ty<'tcx>,
 477
 478         /// Possible values. The locations to branch to in each case
 479         /// are found in the corresponding indices from the `targets` vector.
 480         values: Vec<ConstVal>,
 481
 482         /// Possible branch sites. The length of this vector should be
 483         /// equal to the length of the `values` vector plus 1 -- the
 484         /// extra item is the block to branch to if none of the values
 485         /// fit.
 486         targets: Vec<BasicBlock>,
 487     },
 488
 489     /// Indicates that the landing pad is finished and unwinding should
 490     /// continue. Emitted by build::scope::diverge_cleanup.
 491     Resume,
 492
 493     /// Indicates a normal return. The return pointer lvalue should
 494     /// have been filled in by now. This should occur at most once.
 495     Return,
 496
 497     /// Indicates a terminator that can never be reached.
 498     Unreachable,
 499
 500     /// Drop the Lvalue
 501     Drop {
 502         location: Lvalue<'tcx>,
 503         target: BasicBlock,
 504         unwind: Option<BasicBlock>
 505     },
 506
 507     /// Drop the Lvalue and assign the new value over it
 508     DropAndReplace {
 509         location: Lvalue<'tcx>,
 510         value: Operand<'tcx>,
 511         target: BasicBlock,
 512         unwind: Option<BasicBlock>,
 513     },
 514
 515     /// Block ends with a call of a converging function
 516     Call {
 517         /// The function that’s being called
 518         func: Operand<'tcx>,
 519         /// Arguments the function is called with
 520         args: Vec<Operand<'tcx>>,
 521         /// Destination for the return value. If some, the call is converging.
 522         destination: Option<(Lvalue<'tcx>, BasicBlock)>,
 523         /// Cleanups to be done if the call unwinds.
 524         cleanup: Option<BasicBlock>
 525     },
 526
 527     /// Jump to the target if the condition has the expected value,
 528     /// otherwise panic with a message and a cleanup target.
 529     Assert {
 530         cond: Operand<'tcx>,
 531         expected: bool,
 532         msg: AssertMessage<'tcx>,
 533         target: BasicBlock,
 534         cleanup: Option<BasicBlock>
 535     }
 536 }
 537
 538 impl<'tcx> Terminator<'tcx> {
 539     pub fn successors(&self) -> Cow<[BasicBlock]> {
 540         self.kind.successors()
 541     }
 542
 543     pub fn successors_mut(&mut self) -> Vec<&mut BasicBlock> {
 544         self.kind.successors_mut()
 545     }
 546 }
 547
 548 impl<'tcx> TerminatorKind<'tcx> {
 549     pub fn successors(&self) -> Cow<[BasicBlock]> {
 550         use self::TerminatorKind::*;
 551         match *self {
 552             Goto { target: ref b } => slice::ref_slice(b).into_cow(),
 553             If { targets: (b1, b2), .. } => vec![b1, b2].into_cow(),
 554             Switch { targets: ref b, .. } => b[..].into_cow(),
 555             SwitchInt { targets: ref b, .. } => b[..].into_cow(),
 556             Resume => (&[]).into_cow(),
 557             Return => (&[]).into_cow(),
 558             Unreachable => (&[]).into_cow(),
 559             Call { destination: Some((_, t)), cleanup: Some(c), .. } => vec![t, c].into_cow(),
 560             Call { destination: Some((_, ref t)), cleanup: None, .. } =>
 561                 slice::ref_slice(t).into_cow(),
 562             Call { destination: None, cleanup: Some(ref c), .. } => slice::ref_slice(c).into_cow(),
 563             Call { destination: None, cleanup: None, .. } => (&[]).into_cow(),
 564             DropAndReplace { target, unwind: Some(unwind), .. } |
 565             Drop { target, unwind: Some(unwind), .. } => {
 566                 vec![target, unwind].into_cow()
 567             }
 568             DropAndReplace { ref target, unwind: None, .. } |
 569             Drop { ref target, unwind: None, .. } => {
 570                 slice::ref_slice(target).into_cow()
 571             }
 572             Assert { target, cleanup: Some(unwind), .. } => vec![target, unwind].into_cow(),
 573             Assert { ref target, .. } => slice::ref_slice(target).into_cow(),
 574         }
 575     }
 576
 577     // FIXME: no mootable cow. I’m honestly not sure what a “cow” between `&mut [BasicBlock]` and
 578     // `Vec<&mut BasicBlock>` would look like in the first place.
 579     pub fn successors_mut(&mut self) -> Vec<&mut BasicBlock> {
 580         use self::TerminatorKind::*;
 581         match *self {
 582             Goto { target: ref mut b } => vec![b],
 583             If { targets: (ref mut b1, ref mut b2), .. } => vec![b1, b2],
 584             Switch { targets: ref mut b, .. } => b.iter_mut().collect(),
 585             SwitchInt { targets: ref mut b, .. } => b.iter_mut().collect(),
 586             Resume => Vec::new(),
 587             Return => Vec::new(),
 588             Unreachable => Vec::new(),
 589             Call { destination: Some((_, ref mut t)), cleanup: Some(ref mut c), .. } => vec![t, c],
 590             Call { destination: Some((_, ref mut t)), cleanup: None, .. } => vec![t],
 591             Call { destination: None, cleanup: Some(ref mut c), .. } => vec![c],
 592             Call { destination: None, cleanup: None, .. } => vec![],
 593             DropAndReplace { ref mut target, unwind: Some(ref mut unwind), .. } |
 594             Drop { ref mut target, unwind: Some(ref mut unwind), .. } => vec![target, unwind],
 595             DropAndReplace { ref mut target, unwind: None, .. } |
 596             Drop { ref mut target, unwind: None, .. } => {
 597                 vec![target]
 598             }
 599             Assert { ref mut target, cleanup: Some(ref mut unwind), .. } => vec![target, unwind],
 600             Assert { ref mut target, .. } => vec![target]
 601         }
 602     }
 603 }
 604
 605 impl<'tcx> BasicBlockData<'tcx> {
 606     pub fn new(terminator: Option<Terminator<'tcx>>) -> BasicBlockData<'tcx> {
 607         BasicBlockData {
 608             statements: vec![],
 609             terminator: terminator,
 610             is_cleanup: false,
 611         }
 612     }
 613
 614     /// Accessor for terminator.
 615     ///
 616     /// Terminator may not be None after construction of the basic block is complete. This accessor
 617     /// provides a convenience way to reach the terminator.
 618     pub fn terminator(&self) -> &Terminator<'tcx> {
 619         self.terminator.as_ref().expect("invalid terminator state")
 620     }
 621
 622     pub fn terminator_mut(&mut self) -> &mut Terminator<'tcx> {
 623         self.terminator.as_mut().expect("invalid terminator state")
 624     }
 625 }
 626
 627 impl<'tcx> Debug for TerminatorKind<'tcx> {
 628     fn fmt(&self, fmt: &mut Formatter) -> fmt::Result {
 629         self.fmt_head(fmt)?;
 630         let successors = self.successors();
 631         let labels = self.fmt_successor_labels();
 632         assert_eq!(successors.len(), labels.len());
 633
 634         match successors.len() {
 635             0 => Ok(()),
 636
 637             1 => write!(fmt, " -> {:?}", successors[0]),
 638
 639             _ => {
 640                 write!(fmt, " -> [")?;
 641                 for (i, target) in successors.iter().enumerate() {
 642                     if i > 0 {
 643                         write!(fmt, ", ")?;
 644                     }
 645                     write!(fmt, "{}: {:?}", labels[i], target)?;
 646                 }
 647                 write!(fmt, "]")
 648             }
 649
 650         }
 651     }
 652 }
 653
 654 impl<'tcx> TerminatorKind<'tcx> {
 655     /// Write the "head" part of the terminator; that is, its name and the data it uses to pick the
 656     /// successor basic block, if any. The only information not inlcuded is the list of possible
 657     /// successors, which may be rendered differently between the text and the graphviz format.
 658     pub fn fmt_head<W: Write>(&self, fmt: &mut W) -> fmt::Result {
 659         use self::TerminatorKind::*;
 660         match *self {
 661             Goto { .. } => write!(fmt, "goto"),
 662             If { cond: ref lv, .. } => write!(fmt, "if({:?})", lv),
 663             Switch { discr: ref lv, .. } => write!(fmt, "switch({:?})", lv),
 664             SwitchInt { discr: ref lv, .. } => write!(fmt, "switchInt({:?})", lv),
 665             Return => write!(fmt, "return"),
 666             Resume => write!(fmt, "resume"),
 667             Unreachable => write!(fmt, "unreachable"),
 668             Drop { ref location, .. } => write!(fmt, "drop({:?})", location),
 669             DropAndReplace { ref location, ref value, .. } =>
 670                 write!(fmt, "replace({:?} <- {:?})", location, value),
 671             Call { ref func, ref args, ref destination, .. } => {
 672                 if let Some((ref destination, _)) = *destination {
 673                     write!(fmt, "{:?} = ", destination)?;
 674                 }
 675                 write!(fmt, "{:?}(", func)?;
 676                 for (index, arg) in args.iter().enumerate() {
 677                     if index > 0 {
 678                         write!(fmt, ", ")?;
 679                     }
 680                     write!(fmt, "{:?}", arg)?;
 681                 }
 682                 write!(fmt, ")")
 683             }
 684             Assert { ref cond, expected, ref msg, .. } => {
 685                 write!(fmt, "assert(")?;
 686                 if !expected {
 687                     write!(fmt, "!")?;
 688                 }
 689                 write!(fmt, "{:?}, ", cond)?;
 690
 691                 match *msg {
 692                     AssertMessage::BoundsCheck { ref len, ref index } => {
 693                         write!(fmt, "{:?}, {:?}, {:?}",
 694                                "index out of bounds: the len is {} but the index is {}",
 695                                len, index)?;
 696                     }
 697                     AssertMessage::Math(ref err) => {
 698                         write!(fmt, "{:?}", err.description())?;
 699                     }
 700                 }
 701
 702                 write!(fmt, ")")
 703             }
 704         }
 705     }
 706
 707     /// Return the list of labels for the edges to the successor basic blocks.
 708     pub fn fmt_successor_labels(&self) -> Vec<Cow<'static, str>> {
 709         use self::TerminatorKind::*;
 710         match *self {
 711             Return | Resume | Unreachable => vec![],
 712             Goto { .. } => vec!["".into()],
 713             If { .. } => vec!["true".into(), "false".into()],
 714             Switch { ref adt_def, .. } => {
 715                 adt_def.variants
 716                        .iter()
 717                        .map(|variant| variant.name.to_string().into())
 718                        .collect()
 719             }
 720             SwitchInt { ref values, .. } => {
 721                 values.iter()
 722                       .map(|const_val| {
 723                           let mut buf = String::new();
 724                           fmt_const_val(&mut buf, const_val).unwrap();
 725                           buf.into()
 726                       })
 727                       .chain(iter::once(String::from("otherwise").into()))
 728                       .collect()
 729             }
 730             Call { destination: Some(_), cleanup: Some(_), .. } =>
 731                 vec!["return".into_cow(), "unwind".into_cow()],
 732             Call { destination: Some(_), cleanup: None, .. } => vec!["return".into_cow()],
 733             Call { destination: None, cleanup: Some(_), .. } => vec!["unwind".into_cow()],
 734             Call { destination: None, cleanup: None, .. } => vec![],
 735             DropAndReplace { unwind: None, .. } |
 736             Drop { unwind: None, .. } => vec!["return".into_cow()],
 737             DropAndReplace { unwind: Some(_), .. } |
 738             Drop { unwind: Some(_), .. } => {
 739                 vec!["return".into_cow(), "unwind".into_cow()]
 740             }
 741             Assert { cleanup: None, .. } => vec!["".into()],
 742             Assert { .. } =>
 743                 vec!["success".into_cow(), "unwind".into_cow()]
 744         }
 745     }
 746 }
 747
 748 #[derive(Clone, Debug, RustcEncodable, RustcDecodable)]
 749 pub enum AssertMessage<'tcx> {
 750     BoundsCheck {
 751         len: Operand<'tcx>,
 752         index: Operand<'tcx>
 753     },
 754     Math(ConstMathErr)
 755 }
 756
 757 ///////////////////////////////////////////////////////////////////////////
 758 // Statements
 759
 760 #[derive(Clone, RustcEncodable, RustcDecodable)]
 761 pub struct Statement<'tcx> {
 762     pub source_info: SourceInfo,
 763     pub kind: StatementKind<'tcx>,
 764 }
 765
 766 impl<'tcx> Statement<'tcx> {
 767     /// Changes a statement to a nop. This is both faster than deleting instructions and avoids
 768     /// invalidating statement indices in `Location`s.
 769     pub fn make_nop(&mut self) {
 770         self.kind = StatementKind::Nop
 771     }
 772 }
 773
 774 #[derive(Clone, Debug, RustcEncodable, RustcDecodable)]
 775 pub enum StatementKind<'tcx> {
 776     /// Write the RHS Rvalue to the LHS Lvalue.
 777     Assign(Lvalue<'tcx>, Rvalue<'tcx>),
 778
 779     /// Write the discriminant for a variant to the enum Lvalue.
 780     SetDiscriminant { lvalue: Lvalue<'tcx>, variant_index: usize },
 781
 782     /// Start a live range for the storage of the local.
 783     StorageLive(Lvalue<'tcx>),
 784
 785     /// End the current live range for the storage of the local.
 786     StorageDead(Lvalue<'tcx>),
 787
 788     /// No-op. Useful for deleting instructions without affecting statement indices.
 789     Nop,
 790 }
 791
 792 impl<'tcx> Debug for Statement<'tcx> {
 793     fn fmt(&self, fmt: &mut Formatter) -> fmt::Result {
 794         use self::StatementKind::*;
 795         match self.kind {
 796             Assign(ref lv, ref rv) => write!(fmt, "{:?} = {:?}", lv, rv),
 797             StorageLive(ref lv) => write!(fmt, "StorageLive({:?})", lv),
 798             StorageDead(ref lv) => write!(fmt, "StorageDead({:?})", lv),
 799             SetDiscriminant{lvalue: ref lv, variant_index: index} => {
 800                 write!(fmt, "discriminant({:?}) = {:?}", lv, index)
 801             }
 802             Nop => write!(fmt, "nop"),
 803         }
 804     }
 805 }
 806
 807 ///////////////////////////////////////////////////////////////////////////
 808 // Lvalues
 809
 810 /// A path to a value; something that can be evaluated without
 811 /// changing or disturbing program state.
 812 #[derive(Clone, PartialEq, RustcEncodable, RustcDecodable)]
 813 pub enum Lvalue<'tcx> {
 814     /// local variable
 815     Local(Local),
 816
 817     /// static or static mut variable
 818     Static(DefId),
 819
 820     /// projection out of an lvalue (access a field, deref a pointer, etc)
 821     Projection(Box<LvalueProjection<'tcx>>),
 822 }
 823
 824 /// The `Projection` data structure defines things of the form `B.x`
 825 /// or `*B` or `B[index]`. Note that it is parameterized because it is
 826 /// shared between `Constant` and `Lvalue`. See the aliases
 827 /// `LvalueProjection` etc below.
 828 #[derive(Clone, Debug, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
 829 pub struct Projection<'tcx, B, V> {
 830     pub base: B,
 831     pub elem: ProjectionElem<'tcx, V>,
 832 }
 833
 834 #[derive(Clone, Debug, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
 835 pub enum ProjectionElem<'tcx, V> {
 836     Deref,
 837     Field(Field, Ty<'tcx>),
 838     Index(V),
 839
 840     /// These indices are generated by slice patterns. Easiest to explain
 841     /// by example:
 842     ///
 843     /// ```
 844     /// [X, _, .._, _, _] => { offset: 0, min_length: 4, from_end: false },
 845     /// [_, X, .._, _, _] => { offset: 1, min_length: 4, from_end: false },
 846     /// [_, _, .._, X, _] => { offset: 2, min_length: 4, from_end: true },
 847     /// [_, _, .._, _, X] => { offset: 1, min_length: 4, from_end: true },
 848     /// ```
 849     ConstantIndex {
 850         /// index or -index (in Python terms), depending on from_end
 851         offset: u32,
 852         /// thing being indexed must be at least this long
 853         min_length: u32,
 854         /// counting backwards from end?
 855         from_end: bool,
 856     },
 857
 858     /// These indices are generated by slice patterns.
 859     ///
 860     /// slice[from:-to] in Python terms.
 861     Subslice {
 862         from: u32,
 863         to: u32,
 864     },
 865
 866     /// "Downcast" to a variant of an ADT. Currently, we only introduce
 867     /// this for ADTs with more than one variant. It may be better to
 868     /// just introduce it always, or always for enums.
 869     Downcast(&'tcx AdtDef, usize),
 870 }
 871
 872 /// Alias for projections as they appear in lvalues, where the base is an lvalue
 873 /// and the index is an operand.
 874 pub type LvalueProjection<'tcx> = Projection<'tcx, Lvalue<'tcx>, Operand<'tcx>>;
 875
 876 /// Alias for projections as they appear in lvalues, where the base is an lvalue
 877 /// and the index is an operand.
 878 pub type LvalueElem<'tcx> = ProjectionElem<'tcx, Operand<'tcx>>;
 879
 880 newtype_index!(Field, "field");
 881
 882 impl<'tcx> Lvalue<'tcx> {
 883     pub fn field(self, f: Field, ty: Ty<'tcx>) -> Lvalue<'tcx> {
 884         self.elem(ProjectionElem::Field(f, ty))
 885     }
 886
 887     pub fn deref(self) -> Lvalue<'tcx> {
 888         self.elem(ProjectionElem::Deref)
 889     }
 890
 891     pub fn downcast(self, adt_def: &'tcx AdtDef, variant_index: usize) -> Lvalue<'tcx> {
 892         self.elem(ProjectionElem::Downcast(adt_def, variant_index))
 893     }
 894
 895     pub fn index(self, index: Operand<'tcx>) -> Lvalue<'tcx> {
 896         self.elem(ProjectionElem::Index(index))
 897     }
 898
 899     pub fn elem(self, elem: LvalueElem<'tcx>) -> Lvalue<'tcx> {
 900         Lvalue::Projection(Box::new(LvalueProjection {
 901             base: self,
 902             elem: elem,
 903         }))
 904     }
 905 }
 906
 907 impl<'tcx> Debug for Lvalue<'tcx> {
 908     fn fmt(&self, fmt: &mut Formatter) -> fmt::Result {
 909         use self::Lvalue::*;
 910
 911         match *self {
 912             Local(id) => write!(fmt, "{:?}", id),
 913             Static(def_id) =>
 914                 write!(fmt, "{}", ty::tls::with(|tcx| tcx.item_path_str(def_id))),
 915             Projection(ref data) =>
 916                 match data.elem {
 917                     ProjectionElem::Downcast(ref adt_def, index) =>
 918                         write!(fmt, "({:?} as {})", data.base, adt_def.variants[index].name),
 919                     ProjectionElem::Deref =>
 920                         write!(fmt, "(*{:?})", data.base),
 921                     ProjectionElem::Field(field, ty) =>
 922                         write!(fmt, "({:?}.{:?}: {:?})", data.base, field.index(), ty),
 923                     ProjectionElem::Index(ref index) =>
 924                         write!(fmt, "{:?}[{:?}]", data.base, index),
 925                     ProjectionElem::ConstantIndex { offset, min_length, from_end: false } =>
 926                         write!(fmt, "{:?}[{:?} of {:?}]", data.base, offset, min_length),
 927                     ProjectionElem::ConstantIndex { offset, min_length, from_end: true } =>
 928                         write!(fmt, "{:?}[-{:?} of {:?}]", data.base, offset, min_length),
 929                     ProjectionElem::Subslice { from, to } if to == 0 =>
 930                         write!(fmt, "{:?}[{:?}:]", data.base, from),
 931                     ProjectionElem::Subslice { from, to } if from == 0 =>
 932                         write!(fmt, "{:?}[:-{:?}]", data.base, to),
 933                     ProjectionElem::Subslice { from, to } =>
 934                         write!(fmt, "{:?}[{:?}:-{:?}]", data.base,
 935                                from, to),
 936
 937                 },
 938         }
 939     }
 940 }
 941
 942 ///////////////////////////////////////////////////////////////////////////
 943 // Scopes
 944
 945 newtype_index!(VisibilityScope, "scope");
 946 pub const ARGUMENT_VISIBILITY_SCOPE : VisibilityScope = VisibilityScope(0);
 947
 948 #[derive(Clone, Debug, RustcEncodable, RustcDecodable)]
 949 pub struct VisibilityScopeData {
 950     pub span: Span,
 951     pub parent_scope: Option<VisibilityScope>,
 952 }
 953
 954 ///////////////////////////////////////////////////////////////////////////
 955 // Operands
 956
 957 /// These are values that can appear inside an rvalue (or an index
 958 /// lvalue). They are intentionally limited to prevent rvalues from
 959 /// being nested in one another.
 960 #[derive(Clone, PartialEq, RustcEncodable, RustcDecodable)]
 961 pub enum Operand<'tcx> {
 962     Consume(Lvalue<'tcx>),
 963     Constant(Constant<'tcx>),
 964 }
 965
 966 impl<'tcx> Debug for Operand<'tcx> {
 967     fn fmt(&self, fmt: &mut Formatter) -> fmt::Result {
 968         use self::Operand::*;
 969         match *self {
 970             Constant(ref a) => write!(fmt, "{:?}", a),
 971             Consume(ref lv) => write!(fmt, "{:?}", lv),
 972         }
 973     }
 974 }
 975
 976 ///////////////////////////////////////////////////////////////////////////
 977 /// Rvalues
 978
 979 #[derive(Clone, RustcEncodable, RustcDecodable)]
 980 pub enum Rvalue<'tcx> {
 981     /// x (either a move or copy, depending on type of x)
 982     Use(Operand<'tcx>),
 983
 984     /// [x; 32]
 985     Repeat(Operand<'tcx>, TypedConstVal<'tcx>),
 986
 987     /// &x or &mut x
 988     Ref(&'tcx Region, BorrowKind, Lvalue<'tcx>),
 989
 990     /// length of a [X] or [X;n] value
 991     Len(Lvalue<'tcx>),
 992
 993     Cast(CastKind, Operand<'tcx>, Ty<'tcx>),
 994
 995     BinaryOp(BinOp, Operand<'tcx>, Operand<'tcx>),
 996     CheckedBinaryOp(BinOp, Operand<'tcx>, Operand<'tcx>),
 997
 998     UnaryOp(UnOp, Operand<'tcx>),
 999
1000     /// Creates an *uninitialized* Box
1001     Box(Ty<'tcx>),
1002
1003     /// Create an aggregate value, like a tuple or struct.  This is
1004     /// only needed because we want to distinguish `dest = Foo { x:
1005     /// ..., y: ... }` from `dest.x = ...; dest.y = ...;` in the case
1006     /// that `Foo` has a destructor. These rvalues can be optimized
1007     /// away after type-checking and before lowering.
1008     Aggregate(AggregateKind<'tcx>, Vec<Operand<'tcx>>),
1009
1010     InlineAsm {
1011         asm: InlineAsm,
1012         outputs: Vec<Lvalue<'tcx>>,
1013         inputs: Vec<Operand<'tcx>>
1014     }
1015 }
1016
1017 #[derive(Clone, Copy, Debug, PartialEq, Eq, RustcEncodable, RustcDecodable)]
1018 pub enum CastKind {
1019     Misc,
1020
1021     /// Convert unique, zero-sized type for a fn to fn()
1022     ReifyFnPointer,
1023
1024     /// Convert safe fn() to unsafe fn()
1025     UnsafeFnPointer,
1026
1027     /// "Unsize" -- convert a thin-or-fat pointer to a fat pointer.
1028     /// trans must figure out the details once full monomorphization
1029     /// is known. For example, this could be used to cast from a
1030     /// `&[i32;N]` to a `&[i32]`, or a `Box<T>` to a `Box<Trait>`
1031     /// (presuming `T: Trait`).
1032     Unsize,
1033 }
1034
1035 #[derive(Clone, Debug, PartialEq, Eq, RustcEncodable, RustcDecodable)]
1036 pub enum AggregateKind<'tcx> {
1037     Array,
1038     Tuple,
1039     /// The second field is variant number (discriminant), it's equal to 0
1040     /// for struct and union expressions. The fourth field is active field
1041     /// number and is present only for union expressions.
1042     Adt(&'tcx AdtDef, usize, &'tcx Substs<'tcx>, Option<usize>),
1043     Closure(DefId, ClosureSubsts<'tcx>),
1044 }
1045
1046 #[derive(Copy, Clone, Debug, PartialEq, Eq, RustcEncodable, RustcDecodable)]
1047 pub enum BinOp {
1048     /// The `+` operator (addition)
1049     Add,
1050     /// The `-` operator (subtraction)
1051     Sub,
1052     /// The `*` operator (multiplication)
1053     Mul,
1054     /// The `/` operator (division)
1055     Div,
1056     /// The `%` operator (modulus)
1057     Rem,
1058     /// The `^` operator (bitwise xor)
1059     BitXor,
1060     /// The `&` operator (bitwise and)
1061     BitAnd,
1062     /// The `|` operator (bitwise or)
1063     BitOr,
1064     /// The `<<` operator (shift left)
1065     Shl,
1066     /// The `>>` operator (shift right)
1067     Shr,
1068     /// The `==` operator (equality)
1069     Eq,
1070     /// The `<` operator (less than)
1071     Lt,
1072     /// The `<=` operator (less than or equal to)
1073     Le,
1074     /// The `!=` operator (not equal to)
1075     Ne,
1076     /// The `>=` operator (greater than or equal to)
1077     Ge,
1078     /// The `>` operator (greater than)
1079     Gt,
1080 }
1081
1082 impl BinOp {
1083     pub fn is_checkable(self) -> bool {
1084         use self::BinOp::*;
1085         match self {
1086             Add | Sub | Mul | Shl | Shr => true,
1087             _ => false
1088         }
1089     }
1090 }
1091
1092 #[derive(Copy, Clone, Debug, PartialEq, Eq, RustcEncodable, RustcDecodable)]
1093 pub enum UnOp {
1094     /// The `!` operator for logical inversion
1095     Not,
1096     /// The `-` operator for negation
1097     Neg,
1098 }
1099
1100 impl<'tcx> Debug for Rvalue<'tcx> {
1101     fn fmt(&self, fmt: &mut Formatter) -> fmt::Result {
1102         use self::Rvalue::*;
1103
1104         match *self {
1105             Use(ref lvalue) => write!(fmt, "{:?}", lvalue),
1106             Repeat(ref a, ref b) => write!(fmt, "[{:?}; {:?}]", a, b),
1107             Len(ref a) => write!(fmt, "Len({:?})", a),
1108             Cast(ref kind, ref lv, ref ty) => write!(fmt, "{:?} as {:?} ({:?})", lv, ty, kind),
1109             BinaryOp(ref op, ref a, ref b) => write!(fmt, "{:?}({:?}, {:?})", op, a, b),
1110             CheckedBinaryOp(ref op, ref a, ref b) => {
1111                 write!(fmt, "Checked{:?}({:?}, {:?})", op, a, b)
1112             }
1113             UnaryOp(ref op, ref a) => write!(fmt, "{:?}({:?})", op, a),
1114             Box(ref t) => write!(fmt, "Box({:?})", t),
1115             InlineAsm { ref asm, ref outputs, ref inputs } => {
1116                 write!(fmt, "asm!({:?} : {:?} : {:?})", asm, outputs, inputs)
1117             }
1118
1119             Ref(_, borrow_kind, ref lv) => {
1120                 let kind_str = match borrow_kind {
1121                     BorrowKind::Shared => "",
1122                     BorrowKind::Mut | BorrowKind::Unique => "mut ",
1123                 };
1124                 write!(fmt, "&{}{:?}", kind_str, lv)
1125             }
1126
1127             Aggregate(ref kind, ref lvs) => {
1128                 fn fmt_tuple(fmt: &mut Formatter, lvs: &[Operand]) -> fmt::Result {
1129                     let mut tuple_fmt = fmt.debug_tuple("");
1130                     for lv in lvs {
1131                         tuple_fmt.field(lv);
1132                     }
1133                     tuple_fmt.finish()
1134                 }
1135
1136                 match *kind {
1137                     AggregateKind::Array => write!(fmt, "{:?}", lvs),
1138
1139                     AggregateKind::Tuple => {
1140                         match lvs.len() {
1141                             0 => write!(fmt, "()"),
1142                             1 => write!(fmt, "({:?},)", lvs[0]),
1143                             _ => fmt_tuple(fmt, lvs),
1144                         }
1145                     }
1146
1147                     AggregateKind::Adt(adt_def, variant, substs, _) => {
1148                         let variant_def = &adt_def.variants[variant];
1149
1150                         ppaux::parameterized(fmt, substs, variant_def.did, &[])?;
1151
1152                         match variant_def.ctor_kind {
1153                             CtorKind::Const => Ok(()),
1154                             CtorKind::Fn => fmt_tuple(fmt, lvs),
1155                             CtorKind::Fictive => {
1156                                 let mut struct_fmt = fmt.debug_struct("");
1157                                 for (field, lv) in variant_def.fields.iter().zip(lvs) {
1158                                     struct_fmt.field(&field.name.as_str(), lv);
1159                                 }
1160                                 struct_fmt.finish()
1161                             }
1162                         }
1163                     }
1164
1165                     AggregateKind::Closure(def_id, _) => ty::tls::with(|tcx| {
1166                         if let Some(node_id) = tcx.hir.as_local_node_id(def_id) {
1167                             let name = format!("[closure@{:?}]", tcx.hir.span(node_id));
1168                             let mut struct_fmt = fmt.debug_struct(&name);
1169
1170                             tcx.with_freevars(node_id, |freevars| {
1171                                 for (freevar, lv) in freevars.iter().zip(lvs) {
1172                                     let def_id = freevar.def.def_id();
1173                                     let var_id = tcx.hir.as_local_node_id(def_id).unwrap();
1174                                     let var_name = tcx.local_var_name_str(var_id);
1175                                     struct_fmt.field(&var_name, lv);
1176                                 }
1177                             });
1178
1179                             struct_fmt.finish()
1180                         } else {
1181                             write!(fmt, "[closure]")
1182                         }
1183                     }),
1184                 }
1185             }
1186         }
1187     }
1188 }
1189
1190 ///////////////////////////////////////////////////////////////////////////
1191 /// Constants
1192 ///
1193 /// Two constants are equal if they are the same constant. Note that
1194 /// this does not necessarily mean that they are "==" in Rust -- in
1195 /// particular one must be wary of `NaN`!
1196
1197 #[derive(Clone, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
1198 pub struct Constant<'tcx> {
1199     pub span: Span,
1200     pub ty: Ty<'tcx>,
1201     pub literal: Literal<'tcx>,
1202 }
1203
1204 #[derive(Clone, RustcEncodable, RustcDecodable)]
1205 pub struct TypedConstVal<'tcx> {
1206     pub ty: Ty<'tcx>,
1207     pub span: Span,
1208     pub value: ConstUsize,
1209 }
1210
1211 impl<'tcx> Debug for TypedConstVal<'tcx> {
1212     fn fmt(&self, fmt: &mut Formatter) -> fmt::Result {
1213         write!(fmt, "const {}", ConstInt::Usize(self.value))
1214     }
1215 }
1216
1217 newtype_index!(Promoted, "promoted");
1218
1219 #[derive(Clone, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
1220 pub enum Literal<'tcx> {
1221     Item {
1222         def_id: DefId,
1223         substs: &'tcx Substs<'tcx>,
1224     },
1225     Value {
1226         value: ConstVal,
1227     },
1228     Promoted {
1229         // Index into the `promoted` vector of `Mir`.
1230         index: Promoted
1231     },
1232 }
1233
1234 impl<'tcx> Debug for Constant<'tcx> {
1235     fn fmt(&self, fmt: &mut Formatter) -> fmt::Result {
1236         write!(fmt, "{:?}", self.literal)
1237     }
1238 }
1239
1240 impl<'tcx> Debug for Literal<'tcx> {
1241     fn fmt(&self, fmt: &mut Formatter) -> fmt::Result {
1242         use self::Literal::*;
1243         match *self {
1244             Item { def_id, substs } => {
1245                 ppaux::parameterized(fmt, substs, def_id, &[])
1246             }
1247             Value { ref value } => {
1248                 write!(fmt, "const ")?;
1249                 fmt_const_val(fmt, value)
1250             }
1251             Promoted { index } => {
1252                 write!(fmt, "{:?}", index)
1253             }
1254         }
1255     }
1256 }
1257
1258 /// Write a `ConstVal` in a way closer to the original source code than the `Debug` output.
1259 fn fmt_const_val<W: Write>(fmt: &mut W, const_val: &ConstVal) -> fmt::Result {
1260     use middle::const_val::ConstVal::*;
1261     match *const_val {
1262         Float(f) => write!(fmt, "{:?}", f),
1263         Integral(n) => write!(fmt, "{}", n),
1264         Str(ref s) => write!(fmt, "{:?}", s),
1265         ByteStr(ref bytes) => {
1266             let escaped: String = bytes
1267                 .iter()
1268                 .flat_map(|&ch| ascii::escape_default(ch).map(|c| c as char))
1269                 .collect();
1270             write!(fmt, "b\"{}\"", escaped)
1271         }
1272         Bool(b) => write!(fmt, "{:?}", b),
1273         Function(def_id) => write!(fmt, "{}", item_path_str(def_id)),
1274         Struct(_) | Tuple(_) | Array(_) | Repeat(..) =>
1275             bug!("ConstVal `{:?}` should not be in MIR", const_val),
1276         Char(c) => write!(fmt, "{:?}", c),
1277     }
1278 }
1279
1280 fn item_path_str(def_id: DefId) -> String {
1281     ty::tls::with(|tcx| tcx.item_path_str(def_id))
1282 }
1283
1284 impl<'tcx> ControlFlowGraph for Mir<'tcx> {
1285
1286     type Node = BasicBlock;
1287
1288     fn num_nodes(&self) -> usize { self.basic_blocks.len() }
1289
1290     fn start_node(&self) -> Self::Node { START_BLOCK }
1291
1292     fn predecessors<'graph>(&'graph self, node: Self::Node)
1293                             -> <Self as GraphPredecessors<'graph>>::Iter
1294     {
1295         self.predecessors_for(node).clone().into_iter()
1296     }
1297     fn successors<'graph>(&'graph self, node: Self::Node)
1298                           -> <Self as GraphSuccessors<'graph>>::Iter
1299     {
1300         self.basic_blocks[node].terminator().successors().into_owned().into_iter()
1301     }
1302 }
1303
1304 impl<'a, 'b> GraphPredecessors<'b> for Mir<'a> {
1305     type Item = BasicBlock;
1306     type Iter = IntoIter<BasicBlock>;
1307 }
1308
1309 impl<'a, 'b>  GraphSuccessors<'b> for Mir<'a> {
1310     type Item = BasicBlock;
1311     type Iter = IntoIter<BasicBlock>;
1312 }
1313
1314 #[derive(Copy, Clone, PartialEq, Eq, Hash, Ord, PartialOrd)]
1315 pub struct Location {
1316     /// the location is within this block
1317     pub block: BasicBlock,
1318
1319     /// the location is the start of the this statement; or, if `statement_index`
1320     /// == num-statements, then the start of the terminator.
1321     pub statement_index: usize,
1322 }
1323
1324 impl fmt::Debug for Location {
1325     fn fmt(&self, fmt: &mut fmt::Formatter) -> fmt::Result {
1326         write!(fmt, "{:?}[{}]", self.block, self.statement_index)
1327     }
1328 }
1329
1330 impl Location {
1331     pub fn dominates(&self, other: &Location, dominators: &Dominators<BasicBlock>) -> bool {
1332         if self.block == other.block {
1333             self.statement_index <= other.statement_index
1334         } else {
1335             dominators.is_dominated_by(other.block, self.block)
1336         }
1337     }
1338 }