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