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