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_eval::ConstVal;
  13 use rustc_const_eval::{ConstUsize, ConstInt};
  14 use middle::def_id::DefId;
  15 use middle::subst::Substs;
  16 use middle::ty::{self, AdtDef, ClosureSubsts, FnOutput, Region, Ty};
  17 use util::ppaux;
  18 use rustc_back::slice;
  19 use rustc_front::hir::InlineAsm;
  20 use std::ascii;
  21 use std::borrow::{Cow};
  22 use std::fmt::{self, Debug, Formatter, Write};
  23 use std::{iter, u32};
  24 use std::ops::{Index, IndexMut};
  25 use syntax::ast::{self, Name};
  26 use syntax::codemap::Span;
  27
  28 /// Lowered representation of a single function.
  29 #[derive(Clone, RustcEncodable, RustcDecodable)]
  30 pub struct Mir<'tcx> {
  31     /// List of basic blocks. References to basic block use a newtyped index type `BasicBlock`
  32     /// that indexes into this vector.
  33     pub basic_blocks: Vec<BasicBlockData<'tcx>>,
  34
  35     /// List of lexical scopes; these are referenced by statements and
  36     /// used (eventually) for debuginfo. Indexed by a `ScopeId`.
  37     pub scopes: ScopeDataVec,
  38
  39     /// Return type of the function.
  40     pub return_ty: FnOutput<'tcx>,
  41
  42     /// Variables: these are stack slots corresponding to user variables. They may be
  43     /// assigned many times.
  44     pub var_decls: Vec<VarDecl<'tcx>>,
  45
  46     /// Args: these are stack slots corresponding to the input arguments.
  47     pub arg_decls: Vec<ArgDecl<'tcx>>,
  48
  49     /// Temp declarations: stack slots that for temporaries created by
  50     /// the compiler. These are assigned once, but they are not SSA
  51     /// values in that it is possible to borrow them and mutate them
  52     /// through the resulting reference.
  53     pub temp_decls: Vec<TempDecl<'tcx>>,
  54
  55     /// A span representing this MIR, for error reporting
  56     pub span: Span,
  57 }
  58
  59 /// where execution begins
  60 pub const START_BLOCK: BasicBlock = BasicBlock(0);
  61
  62 /// where execution ends, on normal return
  63 pub const END_BLOCK: BasicBlock = BasicBlock(1);
  64
  65 impl<'tcx> Mir<'tcx> {
  66     pub fn all_basic_blocks(&self) -> Vec<BasicBlock> {
  67         (0..self.basic_blocks.len())
  68             .map(|i| BasicBlock::new(i))
  69             .collect()
  70     }
  71
  72     pub fn basic_block_data(&self, bb: BasicBlock) -> &BasicBlockData<'tcx> {
  73         &self.basic_blocks[bb.index()]
  74     }
  75
  76     pub fn basic_block_data_mut(&mut self, bb: BasicBlock) -> &mut BasicBlockData<'tcx> {
  77         &mut self.basic_blocks[bb.index()]
  78     }
  79 }
  80
  81 impl<'tcx> Index<BasicBlock> for Mir<'tcx> {
  82     type Output = BasicBlockData<'tcx>;
  83
  84     #[inline]
  85     fn index(&self, index: BasicBlock) -> &BasicBlockData<'tcx> {
  86         self.basic_block_data(index)
  87     }
  88 }
  89
  90 impl<'tcx> IndexMut<BasicBlock> for Mir<'tcx> {
  91     #[inline]
  92     fn index_mut(&mut self, index: BasicBlock) -> &mut BasicBlockData<'tcx> {
  93         self.basic_block_data_mut(index)
  94     }
  95 }
  96
  97 ///////////////////////////////////////////////////////////////////////////
  98 // Mutability and borrow kinds
  99
 100 #[derive(Copy, Clone, Debug, PartialEq, Eq, RustcEncodable, RustcDecodable)]
 101 pub enum Mutability {
 102     Mut,
 103     Not,
 104 }
 105
 106 #[derive(Copy, Clone, Debug, PartialEq, Eq, RustcEncodable, RustcDecodable)]
 107 pub enum BorrowKind {
 108     /// Data must be immutable and is aliasable.
 109     Shared,
 110
 111     /// Data must be immutable but not aliasable.  This kind of borrow
 112     /// cannot currently be expressed by the user and is used only in
 113     /// implicit closure bindings. It is needed when you the closure
 114     /// is borrowing or mutating a mutable referent, e.g.:
 115     ///
 116     ///    let x: &mut isize = ...;
 117     ///    let y = || *x += 5;
 118     ///
 119     /// If we were to try to translate this closure into a more explicit
 120     /// form, we'd encounter an error with the code as written:
 121     ///
 122     ///    struct Env { x: & &mut isize }
 123     ///    let x: &mut isize = ...;
 124     ///    let y = (&mut Env { &x }, fn_ptr);  // Closure is pair of env and fn
 125     ///    fn fn_ptr(env: &mut Env) { **env.x += 5; }
 126     ///
 127     /// This is then illegal because you cannot mutate a `&mut` found
 128     /// in an aliasable location. To solve, you'd have to translate with
 129     /// an `&mut` borrow:
 130     ///
 131     ///    struct Env { x: & &mut isize }
 132     ///    let x: &mut isize = ...;
 133     ///    let y = (&mut Env { &mut x }, fn_ptr); // changed from &x to &mut x
 134     ///    fn fn_ptr(env: &mut Env) { **env.x += 5; }
 135     ///
 136     /// Now the assignment to `**env.x` is legal, but creating a
 137     /// mutable pointer to `x` is not because `x` is not mutable. We
 138     /// could fix this by declaring `x` as `let mut x`. This is ok in
 139     /// user code, if awkward, but extra weird for closures, since the
 140     /// borrow is hidden.
 141     ///
 142     /// So we introduce a "unique imm" borrow -- the referent is
 143     /// immutable, but not aliasable. This solves the problem. For
 144     /// simplicity, we don't give users the way to express this
 145     /// borrow, it's just used when translating closures.
 146     Unique,
 147
 148     /// Data is mutable and not aliasable.
 149     Mut,
 150 }
 151
 152 ///////////////////////////////////////////////////////////////////////////
 153 // Variables and temps
 154
 155 /// A "variable" is a binding declared by the user as part of the fn
 156 /// decl, a let, etc.
 157 #[derive(Clone, Debug, RustcEncodable, RustcDecodable)]
 158 pub struct VarDecl<'tcx> {
 159     pub mutability: Mutability,
 160     pub name: Name,
 161     pub ty: Ty<'tcx>,
 162     pub scope: ScopeId, // scope in which variable was declared
 163     pub span: Span, // span where variable was declared
 164 }
 165
 166 /// A "temp" is a temporary that we place on the stack. They are
 167 /// anonymous, always mutable, and have only a type.
 168 #[derive(Clone, Debug, RustcEncodable, RustcDecodable)]
 169 pub struct TempDecl<'tcx> {
 170     pub ty: Ty<'tcx>,
 171 }
 172
 173 /// A "arg" is one of the function's formal arguments. These are
 174 /// anonymous and distinct from the bindings that the user declares.
 175 ///
 176 /// For example, in this function:
 177 ///
 178 /// ```
 179 /// fn foo((x, y): (i32, u32)) { ... }
 180 /// ```
 181 ///
 182 /// there is only one argument, of type `(i32, u32)`, but two bindings
 183 /// (`x` and `y`).
 184 #[derive(Clone, Debug, RustcEncodable, RustcDecodable)]
 185 pub struct ArgDecl<'tcx> {
 186     pub ty: Ty<'tcx>,
 187
 188     /// If true, this argument is a tuple after monomorphization,
 189     /// and has to be collected from multiple actual arguments.
 190     pub spread: bool
 191 }
 192
 193 ///////////////////////////////////////////////////////////////////////////
 194 // BasicBlock
 195
 196 /// The index of a particular basic block. The index is into the `basic_blocks`
 197 /// list of the `Mir`.
 198 ///
 199 /// (We use a `u32` internally just to save memory.)
 200 #[derive(Copy, Clone, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
 201 pub struct BasicBlock(u32);
 202
 203 impl BasicBlock {
 204     pub fn new(index: usize) -> BasicBlock {
 205         assert!(index < (u32::MAX as usize));
 206         BasicBlock(index as u32)
 207     }
 208
 209     /// Extract the index.
 210     pub fn index(self) -> usize {
 211         self.0 as usize
 212     }
 213 }
 214
 215 impl Debug for BasicBlock {
 216     fn fmt(&self, fmt: &mut Formatter) -> fmt::Result {
 217         write!(fmt, "bb{}", self.0)
 218     }
 219 }
 220
 221 ///////////////////////////////////////////////////////////////////////////
 222 // BasicBlockData and Terminator
 223
 224 #[derive(Clone, Debug, RustcEncodable, RustcDecodable)]
 225 pub struct BasicBlockData<'tcx> {
 226     pub statements: Vec<Statement<'tcx>>,
 227     pub terminator: Option<Terminator<'tcx>>,
 228     pub is_cleanup: bool,
 229 }
 230
 231 #[derive(Clone, Debug, RustcEncodable, RustcDecodable)]
 232 pub struct Terminator<'tcx> {
 233     pub span: Span,
 234     pub scope: ScopeId,
 235     pub kind: TerminatorKind<'tcx>
 236 }
 237
 238 #[derive(Clone, RustcEncodable, RustcDecodable)]
 239 pub enum TerminatorKind<'tcx> {
 240     /// block should have one successor in the graph; we jump there
 241     Goto {
 242         target: BasicBlock,
 243     },
 244
 245     /// jump to branch 0 if this lvalue evaluates to true
 246     If {
 247         cond: Operand<'tcx>,
 248         targets: (BasicBlock, BasicBlock),
 249     },
 250
 251     /// lvalue evaluates to some enum; jump depending on the branch
 252     Switch {
 253         discr: Lvalue<'tcx>,
 254         adt_def: AdtDef<'tcx>,
 255         targets: Vec<BasicBlock>,
 256     },
 257
 258     /// operand evaluates to an integer; jump depending on its value
 259     /// to one of the targets, and otherwise fallback to `otherwise`
 260     SwitchInt {
 261         /// discriminant value being tested
 262         discr: Lvalue<'tcx>,
 263
 264         /// type of value being tested
 265         switch_ty: Ty<'tcx>,
 266
 267         /// Possible values. The locations to branch to in each case
 268         /// are found in the corresponding indices from the `targets` vector.
 269         values: Vec<ConstVal>,
 270
 271         /// Possible branch sites. The length of this vector should be
 272         /// equal to the length of the `values` vector plus 1 -- the
 273         /// extra item is the block to branch to if none of the values
 274         /// fit.
 275         targets: Vec<BasicBlock>,
 276     },
 277
 278     /// Indicates that the landing pad is finished and unwinding should
 279     /// continue. Emitted by build::scope::diverge_cleanup.
 280     Resume,
 281
 282     /// Indicates a normal return. The ReturnPointer lvalue should
 283     /// have been filled in by now. This should only occur in the
 284     /// `END_BLOCK`.
 285     Return,
 286
 287     /// Drop the Lvalue
 288     Drop {
 289         value: Lvalue<'tcx>,
 290         target: BasicBlock,
 291         unwind: Option<BasicBlock>
 292     },
 293
 294     /// Block ends with a call of a converging function
 295     Call {
 296         /// The function that’s being called
 297         func: Operand<'tcx>,
 298         /// Arguments the function is called with
 299         args: Vec<Operand<'tcx>>,
 300         /// Destination for the return value. If some, the call is converging.
 301         destination: Option<(Lvalue<'tcx>, BasicBlock)>,
 302         /// Cleanups to be done if the call unwinds.
 303         cleanup: Option<BasicBlock>
 304     },
 305 }
 306
 307 impl<'tcx> Terminator<'tcx> {
 308     pub fn successors(&self) -> Cow<[BasicBlock]> {
 309         self.kind.successors()
 310     }
 311
 312     pub fn successors_mut(&mut self) -> Vec<&mut BasicBlock> {
 313         self.kind.successors_mut()
 314     }
 315 }
 316
 317 impl<'tcx> TerminatorKind<'tcx> {
 318     pub fn successors(&self) -> Cow<[BasicBlock]> {
 319         use self::TerminatorKind::*;
 320         match *self {
 321             Goto { target: ref b } => slice::ref_slice(b).into_cow(),
 322             If { targets: (b1, b2), .. } => vec![b1, b2].into_cow(),
 323             Switch { targets: ref b, .. } => b[..].into_cow(),
 324             SwitchInt { targets: ref b, .. } => b[..].into_cow(),
 325             Resume => (&[]).into_cow(),
 326             Return => (&[]).into_cow(),
 327             Call { destination: Some((_, t)), cleanup: Some(c), .. } => vec![t, c].into_cow(),
 328             Call { destination: Some((_, ref t)), cleanup: None, .. } =>
 329                 slice::ref_slice(t).into_cow(),
 330             Call { destination: None, cleanup: Some(ref c), .. } => slice::ref_slice(c).into_cow(),
 331             Call { destination: None, cleanup: None, .. } => (&[]).into_cow(),
 332             Drop { target, unwind: Some(unwind), .. } => vec![target, unwind].into_cow(),
 333             Drop { ref target, .. } => slice::ref_slice(target).into_cow(),
 334         }
 335     }
 336
 337     // FIXME: no mootable cow. I’m honestly not sure what a “cow” between `&mut [BasicBlock]` and
 338     // `Vec<&mut BasicBlock>` would look like in the first place.
 339     pub fn successors_mut(&mut self) -> Vec<&mut BasicBlock> {
 340         use self::TerminatorKind::*;
 341         match *self {
 342             Goto { target: ref mut b } => vec![b],
 343             If { targets: (ref mut b1, ref mut b2), .. } => vec![b1, b2],
 344             Switch { targets: ref mut b, .. } => b.iter_mut().collect(),
 345             SwitchInt { targets: ref mut b, .. } => b.iter_mut().collect(),
 346             Resume => Vec::new(),
 347             Return => Vec::new(),
 348             Call { destination: Some((_, ref mut t)), cleanup: Some(ref mut c), .. } => vec![t, c],
 349             Call { destination: Some((_, ref mut t)), cleanup: None, .. } => vec![t],
 350             Call { destination: None, cleanup: Some(ref mut c), .. } => vec![c],
 351             Call { destination: None, cleanup: None, .. } => vec![],
 352             Drop { ref mut target, unwind: Some(ref mut unwind), .. } => vec![target, unwind],
 353             Drop { ref mut target, .. } => vec![target]
 354         }
 355     }
 356 }
 357
 358 impl<'tcx> BasicBlockData<'tcx> {
 359     pub fn new(terminator: Option<Terminator<'tcx>>) -> BasicBlockData<'tcx> {
 360         BasicBlockData {
 361             statements: vec![],
 362             terminator: terminator,
 363             is_cleanup: false,
 364         }
 365     }
 366
 367     /// Accessor for terminator.
 368     ///
 369     /// Terminator may not be None after construction of the basic block is complete. This accessor
 370     /// provides a convenience way to reach the terminator.
 371     pub fn terminator(&self) -> &Terminator<'tcx> {
 372         self.terminator.as_ref().expect("invalid terminator state")
 373     }
 374
 375     pub fn terminator_mut(&mut self) -> &mut Terminator<'tcx> {
 376         self.terminator.as_mut().expect("invalid terminator state")
 377     }
 378 }
 379
 380 impl<'tcx> Debug for TerminatorKind<'tcx> {
 381     fn fmt(&self, fmt: &mut Formatter) -> fmt::Result {
 382         self.fmt_head(fmt)?;
 383         let successors = self.successors();
 384         let labels = self.fmt_successor_labels();
 385         assert_eq!(successors.len(), labels.len());
 386
 387         match successors.len() {
 388             0 => Ok(()),
 389
 390             1 => write!(fmt, " -> {:?}", successors[0]),
 391
 392             _ => {
 393                 write!(fmt, " -> [")?;
 394                 for (i, target) in successors.iter().enumerate() {
 395                     if i > 0 {
 396                         write!(fmt, ", ")?;
 397                     }
 398                     write!(fmt, "{}: {:?}", labels[i], target)?;
 399                 }
 400                 write!(fmt, "]")
 401             }
 402
 403         }
 404     }
 405 }
 406
 407 impl<'tcx> TerminatorKind<'tcx> {
 408     /// Write the "head" part of the terminator; that is, its name and the data it uses to pick the
 409     /// successor basic block, if any. The only information not inlcuded is the list of possible
 410     /// successors, which may be rendered differently between the text and the graphviz format.
 411     pub fn fmt_head<W: Write>(&self, fmt: &mut W) -> fmt::Result {
 412         use self::TerminatorKind::*;
 413         match *self {
 414             Goto { .. } => write!(fmt, "goto"),
 415             If { cond: ref lv, .. } => write!(fmt, "if({:?})", lv),
 416             Switch { discr: ref lv, .. } => write!(fmt, "switch({:?})", lv),
 417             SwitchInt { discr: ref lv, .. } => write!(fmt, "switchInt({:?})", lv),
 418             Return => write!(fmt, "return"),
 419             Resume => write!(fmt, "resume"),
 420             Drop { ref value, .. } => write!(fmt, "drop({:?})", value),
 421             Call { ref func, ref args, ref destination, .. } => {
 422                 if let Some((ref destination, _)) = *destination {
 423                     write!(fmt, "{:?} = ", destination)?;
 424                 }
 425                 write!(fmt, "{:?}(", func)?;
 426                 for (index, arg) in args.iter().enumerate() {
 427                     if index > 0 {
 428                         write!(fmt, ", ")?;
 429                     }
 430                     write!(fmt, "{:?}", arg)?;
 431                 }
 432                 write!(fmt, ")")
 433             }
 434         }
 435     }
 436
 437     /// Return the list of labels for the edges to the successor basic blocks.
 438     pub fn fmt_successor_labels(&self) -> Vec<Cow<'static, str>> {
 439         use self::TerminatorKind::*;
 440         match *self {
 441             Return | Resume => vec![],
 442             Goto { .. } => vec!["".into()],
 443             If { .. } => vec!["true".into(), "false".into()],
 444             Switch { ref adt_def, .. } => {
 445                 adt_def.variants
 446                        .iter()
 447                        .map(|variant| variant.name.to_string().into())
 448                        .collect()
 449             }
 450             SwitchInt { ref values, .. } => {
 451                 values.iter()
 452                       .map(|const_val| {
 453                           let mut buf = String::new();
 454                           fmt_const_val(&mut buf, const_val).unwrap();
 455                           buf.into()
 456                       })
 457                       .chain(iter::once(String::from("otherwise").into()))
 458                       .collect()
 459             }
 460             Call { destination: Some(_), cleanup: Some(_), .. } =>
 461                 vec!["return".into_cow(), "unwind".into_cow()],
 462             Call { destination: Some(_), cleanup: None, .. } => vec!["return".into_cow()],
 463             Call { destination: None, cleanup: Some(_), .. } => vec!["unwind".into_cow()],
 464             Call { destination: None, cleanup: None, .. } => vec![],
 465             Drop { unwind: None, .. } => vec!["return".into_cow()],
 466             Drop { .. } => vec!["return".into_cow(), "unwind".into_cow()],
 467         }
 468     }
 469 }
 470
 471
 472 ///////////////////////////////////////////////////////////////////////////
 473 // Statements
 474
 475 #[derive(Clone, RustcEncodable, RustcDecodable)]
 476 pub struct Statement<'tcx> {
 477     pub span: Span,
 478     pub scope: ScopeId,
 479     pub kind: StatementKind<'tcx>,
 480 }
 481
 482 #[derive(Clone, Debug, RustcEncodable, RustcDecodable)]
 483 pub enum StatementKind<'tcx> {
 484     Assign(Lvalue<'tcx>, Rvalue<'tcx>),
 485 }
 486
 487 impl<'tcx> Debug for Statement<'tcx> {
 488     fn fmt(&self, fmt: &mut Formatter) -> fmt::Result {
 489         use self::StatementKind::*;
 490         match self.kind {
 491             Assign(ref lv, ref rv) => write!(fmt, "{:?} = {:?}", lv, rv)
 492         }
 493     }
 494 }
 495
 496 ///////////////////////////////////////////////////////////////////////////
 497 // Lvalues
 498
 499 /// A path to a value; something that can be evaluated without
 500 /// changing or disturbing program state.
 501 #[derive(Clone, PartialEq, RustcEncodable, RustcDecodable)]
 502 pub enum Lvalue<'tcx> {
 503     /// local variable declared by the user
 504     Var(u32),
 505
 506     /// temporary introduced during lowering into MIR
 507     Temp(u32),
 508
 509     /// formal parameter of the function; note that these are NOT the
 510     /// bindings that the user declares, which are vars
 511     Arg(u32),
 512
 513     /// static or static mut variable
 514     Static(DefId),
 515
 516     /// the return pointer of the fn
 517     ReturnPointer,
 518
 519     /// projection out of an lvalue (access a field, deref a pointer, etc)
 520     Projection(Box<LvalueProjection<'tcx>>),
 521 }
 522
 523 /// The `Projection` data structure defines things of the form `B.x`
 524 /// or `*B` or `B[index]`. Note that it is parameterized because it is
 525 /// shared between `Constant` and `Lvalue`. See the aliases
 526 /// `LvalueProjection` etc below.
 527 #[derive(Clone, Debug, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
 528 pub struct Projection<'tcx, B, V> {
 529     pub base: B,
 530     pub elem: ProjectionElem<'tcx, V>,
 531 }
 532
 533 #[derive(Clone, Debug, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
 534 pub enum ProjectionElem<'tcx, V> {
 535     Deref,
 536     Field(Field, Ty<'tcx>),
 537     Index(V),
 538
 539     /// These indices are generated by slice patterns. Easiest to explain
 540     /// by example:
 541     ///
 542     /// ```
 543     /// [X, _, .._, _, _] => { offset: 0, min_length: 4, from_end: false },
 544     /// [_, X, .._, _, _] => { offset: 1, min_length: 4, from_end: false },
 545     /// [_, _, .._, X, _] => { offset: 2, min_length: 4, from_end: true },
 546     /// [_, _, .._, _, X] => { offset: 1, min_length: 4, from_end: true },
 547     /// ```
 548     ConstantIndex {
 549         /// index or -index (in Python terms), depending on from_end
 550         offset: u32,
 551         /// thing being indexed must be at least this long
 552         min_length: u32,
 553         /// counting backwards from end?
 554         from_end: bool,
 555     },
 556
 557     /// "Downcast" to a variant of an ADT. Currently, we only introduce
 558     /// this for ADTs with more than one variant. It may be better to
 559     /// just introduce it always, or always for enums.
 560     Downcast(AdtDef<'tcx>, usize),
 561 }
 562
 563 /// Alias for projections as they appear in lvalues, where the base is an lvalue
 564 /// and the index is an operand.
 565 pub type LvalueProjection<'tcx> = Projection<'tcx, Lvalue<'tcx>, Operand<'tcx>>;
 566
 567 /// Alias for projections as they appear in lvalues, where the base is an lvalue
 568 /// and the index is an operand.
 569 pub type LvalueElem<'tcx> = ProjectionElem<'tcx, Operand<'tcx>>;
 570
 571 /// Index into the list of fields found in a `VariantDef`
 572 #[derive(Copy, Clone, Debug, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
 573 pub struct Field(u32);
 574
 575 impl Field {
 576     pub fn new(value: usize) -> Field {
 577         assert!(value < (u32::MAX) as usize);
 578         Field(value as u32)
 579     }
 580
 581     pub fn index(self) -> usize {
 582         self.0 as usize
 583     }
 584 }
 585
 586 impl<'tcx> Lvalue<'tcx> {
 587     pub fn field(self, f: Field, ty: Ty<'tcx>) -> Lvalue<'tcx> {
 588         self.elem(ProjectionElem::Field(f, ty))
 589     }
 590
 591     pub fn deref(self) -> Lvalue<'tcx> {
 592         self.elem(ProjectionElem::Deref)
 593     }
 594
 595     pub fn index(self, index: Operand<'tcx>) -> Lvalue<'tcx> {
 596         self.elem(ProjectionElem::Index(index))
 597     }
 598
 599     pub fn elem(self, elem: LvalueElem<'tcx>) -> Lvalue<'tcx> {
 600         Lvalue::Projection(Box::new(LvalueProjection {
 601             base: self,
 602             elem: elem,
 603         }))
 604     }
 605 }
 606
 607 impl<'tcx> Debug for Lvalue<'tcx> {
 608     fn fmt(&self, fmt: &mut Formatter) -> fmt::Result {
 609         use self::Lvalue::*;
 610
 611         match *self {
 612             Var(id) =>
 613                 write!(fmt, "var{:?}", id),
 614             Arg(id) =>
 615                 write!(fmt, "arg{:?}", id),
 616             Temp(id) =>
 617                 write!(fmt, "tmp{:?}", id),
 618             Static(def_id) =>
 619                 write!(fmt, "{}", ty::tls::with(|tcx| tcx.item_path_str(def_id))),
 620             ReturnPointer =>
 621                 write!(fmt, "return"),
 622             Projection(ref data) =>
 623                 match data.elem {
 624                     ProjectionElem::Downcast(ref adt_def, index) =>
 625                         write!(fmt, "({:?} as {})", data.base, adt_def.variants[index].name),
 626                     ProjectionElem::Deref =>
 627                         write!(fmt, "(*{:?})", data.base),
 628                     ProjectionElem::Field(field, ty) =>
 629                         write!(fmt, "({:?}.{:?}: {:?})", data.base, field.index(), ty),
 630                     ProjectionElem::Index(ref index) =>
 631                         write!(fmt, "{:?}[{:?}]", data.base, index),
 632                     ProjectionElem::ConstantIndex { offset, min_length, from_end: false } =>
 633                         write!(fmt, "{:?}[{:?} of {:?}]", data.base, offset, min_length),
 634                     ProjectionElem::ConstantIndex { offset, min_length, from_end: true } =>
 635                         write!(fmt, "{:?}[-{:?} of {:?}]", data.base, offset, min_length),
 636                 },
 637         }
 638     }
 639 }
 640
 641 ///////////////////////////////////////////////////////////////////////////
 642 // Scopes
 643
 644 #[derive(Clone, Debug, RustcEncodable, RustcDecodable)]
 645 pub struct ScopeDataVec {
 646     pub vec: Vec<ScopeData>
 647 }
 648
 649 impl ScopeDataVec {
 650     pub fn new() -> Self {
 651         ScopeDataVec { vec: Vec::new() }
 652     }
 653 }
 654
 655 impl Index<ScopeId> for ScopeDataVec {
 656     type Output = ScopeData;
 657
 658     #[inline]
 659     fn index(&self, index: ScopeId) -> &ScopeData {
 660         &self.vec[index.index()]
 661     }
 662 }
 663
 664 impl IndexMut<ScopeId> for ScopeDataVec {
 665     #[inline]
 666     fn index_mut(&mut self, index: ScopeId) -> &mut ScopeData {
 667         &mut self.vec[index.index()]
 668     }
 669 }
 670
 671 #[derive(Copy, Clone, Debug, Hash, PartialEq, Eq, RustcEncodable, RustcDecodable)]
 672 pub struct ScopeId(u32);
 673
 674 impl ScopeId {
 675     pub fn new(index: usize) -> ScopeId {
 676         assert!(index < (u32::MAX as usize));
 677         ScopeId(index as u32)
 678     }
 679
 680     pub fn index(self) -> usize {
 681         self.0 as usize
 682     }
 683 }
 684
 685 #[derive(Clone, Debug, RustcEncodable, RustcDecodable)]
 686 pub struct ScopeData {
 687     pub parent_scope: Option<ScopeId>,
 688 }
 689
 690 ///////////////////////////////////////////////////////////////////////////
 691 // Operands
 692
 693 /// These are values that can appear inside an rvalue (or an index
 694 /// lvalue). They are intentionally limited to prevent rvalues from
 695 /// being nested in one another.
 696 #[derive(Clone, PartialEq, RustcEncodable, RustcDecodable)]
 697 pub enum Operand<'tcx> {
 698     Consume(Lvalue<'tcx>),
 699     Constant(Constant<'tcx>),
 700 }
 701
 702 impl<'tcx> Debug for Operand<'tcx> {
 703     fn fmt(&self, fmt: &mut Formatter) -> fmt::Result {
 704         use self::Operand::*;
 705         match *self {
 706             Constant(ref a) => write!(fmt, "{:?}", a),
 707             Consume(ref lv) => write!(fmt, "{:?}", lv),
 708         }
 709     }
 710 }
 711
 712 ///////////////////////////////////////////////////////////////////////////
 713 /// Rvalues
 714
 715 #[derive(Clone, RustcEncodable, RustcDecodable)]
 716 pub enum Rvalue<'tcx> {
 717     /// x (either a move or copy, depending on type of x)
 718     Use(Operand<'tcx>),
 719
 720     /// [x; 32]
 721     Repeat(Operand<'tcx>, TypedConstVal<'tcx>),
 722
 723     /// &x or &mut x
 724     Ref(Region, BorrowKind, Lvalue<'tcx>),
 725
 726     /// length of a [X] or [X;n] value
 727     Len(Lvalue<'tcx>),
 728
 729     Cast(CastKind, Operand<'tcx>, Ty<'tcx>),
 730
 731     BinaryOp(BinOp, Operand<'tcx>, Operand<'tcx>),
 732
 733     UnaryOp(UnOp, Operand<'tcx>),
 734
 735     /// Creates an *uninitialized* Box
 736     Box(Ty<'tcx>),
 737
 738     /// Create an aggregate value, like a tuple or struct.  This is
 739     /// only needed because we want to distinguish `dest = Foo { x:
 740     /// ..., y: ... }` from `dest.x = ...; dest.y = ...;` in the case
 741     /// that `Foo` has a destructor. These rvalues can be optimized
 742     /// away after type-checking and before lowering.
 743     Aggregate(AggregateKind<'tcx>, Vec<Operand<'tcx>>),
 744
 745     /// Generates a slice of the form `&input[from_start..L-from_end]`
 746     /// where `L` is the length of the slice. This is only created by
 747     /// slice pattern matching, so e.g. a pattern of the form `[x, y,
 748     /// .., z]` might create a slice with `from_start=2` and
 749     /// `from_end=1`.
 750     Slice {
 751         input: Lvalue<'tcx>,
 752         from_start: usize,
 753         from_end: usize,
 754     },
 755
 756     InlineAsm {
 757         asm: InlineAsm,
 758         outputs: Vec<Lvalue<'tcx>>,
 759         inputs: Vec<Operand<'tcx>>
 760     }
 761 }
 762
 763 #[derive(Clone, Copy, Debug, PartialEq, Eq, RustcEncodable, RustcDecodable)]
 764 pub enum CastKind {
 765     Misc,
 766
 767     /// Convert unique, zero-sized type for a fn to fn()
 768     ReifyFnPointer,
 769
 770     /// Convert safe fn() to unsafe fn()
 771     UnsafeFnPointer,
 772
 773     /// "Unsize" -- convert a thin-or-fat pointer to a fat pointer.
 774     /// trans must figure out the details once full monomorphization
 775     /// is known. For example, this could be used to cast from a
 776     /// `&[i32;N]` to a `&[i32]`, or a `Box<T>` to a `Box<Trait>`
 777     /// (presuming `T: Trait`).
 778     Unsize,
 779 }
 780
 781 #[derive(Clone, Debug, PartialEq, Eq, RustcEncodable, RustcDecodable)]
 782 pub enum AggregateKind<'tcx> {
 783     Vec,
 784     Tuple,
 785     Adt(AdtDef<'tcx>, usize, &'tcx Substs<'tcx>),
 786     Closure(DefId, &'tcx ClosureSubsts<'tcx>),
 787 }
 788
 789 #[derive(Copy, Clone, Debug, PartialEq, Eq, RustcEncodable, RustcDecodable)]
 790 pub enum BinOp {
 791     /// The `+` operator (addition)
 792     Add,
 793     /// The `-` operator (subtraction)
 794     Sub,
 795     /// The `*` operator (multiplication)
 796     Mul,
 797     /// The `/` operator (division)
 798     Div,
 799     /// The `%` operator (modulus)
 800     Rem,
 801     /// The `^` operator (bitwise xor)
 802     BitXor,
 803     /// The `&` operator (bitwise and)
 804     BitAnd,
 805     /// The `|` operator (bitwise or)
 806     BitOr,
 807     /// The `<<` operator (shift left)
 808     Shl,
 809     /// The `>>` operator (shift right)
 810     Shr,
 811     /// The `==` operator (equality)
 812     Eq,
 813     /// The `<` operator (less than)
 814     Lt,
 815     /// The `<=` operator (less than or equal to)
 816     Le,
 817     /// The `!=` operator (not equal to)
 818     Ne,
 819     /// The `>=` operator (greater than or equal to)
 820     Ge,
 821     /// The `>` operator (greater than)
 822     Gt,
 823 }
 824
 825 #[derive(Copy, Clone, Debug, PartialEq, Eq, RustcEncodable, RustcDecodable)]
 826 pub enum UnOp {
 827     /// The `!` operator for logical inversion
 828     Not,
 829     /// The `-` operator for negation
 830     Neg,
 831 }
 832
 833 impl<'tcx> Debug for Rvalue<'tcx> {
 834     fn fmt(&self, fmt: &mut Formatter) -> fmt::Result {
 835         use self::Rvalue::*;
 836
 837         match *self {
 838             Use(ref lvalue) => write!(fmt, "{:?}", lvalue),
 839             Repeat(ref a, ref b) => write!(fmt, "[{:?}; {:?}]", a, b),
 840             Len(ref a) => write!(fmt, "Len({:?})", a),
 841             Cast(ref kind, ref lv, ref ty) => write!(fmt, "{:?} as {:?} ({:?})", lv, ty, kind),
 842             BinaryOp(ref op, ref a, ref b) => write!(fmt, "{:?}({:?}, {:?})", op, a, b),
 843             UnaryOp(ref op, ref a) => write!(fmt, "{:?}({:?})", op, a),
 844             Box(ref t) => write!(fmt, "Box({:?})", t),
 845             InlineAsm { ref asm, ref outputs, ref inputs } => {
 846                 write!(fmt, "asm!({:?} : {:?} : {:?})", asm, outputs, inputs)
 847             }
 848             Slice { ref input, from_start, from_end } =>
 849                 write!(fmt, "{:?}[{:?}..-{:?}]", input, from_start, from_end),
 850
 851             Ref(_, borrow_kind, ref lv) => {
 852                 let kind_str = match borrow_kind {
 853                     BorrowKind::Shared => "",
 854                     BorrowKind::Mut | BorrowKind::Unique => "mut ",
 855                 };
 856                 write!(fmt, "&{}{:?}", kind_str, lv)
 857             }
 858
 859             Aggregate(ref kind, ref lvs) => {
 860                 use self::AggregateKind::*;
 861
 862                 fn fmt_tuple(fmt: &mut Formatter, lvs: &[Operand]) -> fmt::Result {
 863                     let mut tuple_fmt = fmt.debug_tuple("");
 864                     for lv in lvs {
 865                         tuple_fmt.field(lv);
 866                     }
 867                     tuple_fmt.finish()
 868                 }
 869
 870                 match *kind {
 871                     Vec => write!(fmt, "{:?}", lvs),
 872
 873                     Tuple => {
 874                         match lvs.len() {
 875                             0 => write!(fmt, "()"),
 876                             1 => write!(fmt, "({:?},)", lvs[0]),
 877                             _ => fmt_tuple(fmt, lvs),
 878                         }
 879                     }
 880
 881                     Adt(adt_def, variant, substs) => {
 882                         let variant_def = &adt_def.variants[variant];
 883
 884                         ppaux::parameterized(fmt, substs, variant_def.did,
 885                                              ppaux::Ns::Value, &[],
 886                                              |tcx| {
 887                             tcx.lookup_item_type(variant_def.did).generics
 888                         })?;
 889
 890                         match variant_def.kind() {
 891                             ty::VariantKind::Unit => Ok(()),
 892                             ty::VariantKind::Tuple => fmt_tuple(fmt, lvs),
 893                             ty::VariantKind::Struct => {
 894                                 let mut struct_fmt = fmt.debug_struct("");
 895                                 for (field, lv) in variant_def.fields.iter().zip(lvs) {
 896                                     struct_fmt.field(&field.name.as_str(), lv);
 897                                 }
 898                                 struct_fmt.finish()
 899                             }
 900                         }
 901                     }
 902
 903                     Closure(def_id, _) => ty::tls::with(|tcx| {
 904                         if let Some(node_id) = tcx.map.as_local_node_id(def_id) {
 905                             let name = format!("[closure@{:?}]", tcx.map.span(node_id));
 906                             let mut struct_fmt = fmt.debug_struct(&name);
 907
 908                             tcx.with_freevars(node_id, |freevars| {
 909                                 for (freevar, lv) in freevars.iter().zip(lvs) {
 910                                     let var_name = tcx.local_var_name_str(freevar.def.var_id());
 911                                     struct_fmt.field(&var_name, lv);
 912                                 }
 913                             });
 914
 915                             struct_fmt.finish()
 916                         } else {
 917                             write!(fmt, "[closure]")
 918                         }
 919                     }),
 920                 }
 921             }
 922         }
 923     }
 924 }
 925
 926 ///////////////////////////////////////////////////////////////////////////
 927 /// Constants
 928 ///
 929 /// Two constants are equal if they are the same constant. Note that
 930 /// this does not necessarily mean that they are "==" in Rust -- in
 931 /// particular one must be wary of `NaN`!
 932
 933 #[derive(Clone, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
 934 pub struct Constant<'tcx> {
 935     pub span: Span,
 936     pub ty: Ty<'tcx>,
 937     pub literal: Literal<'tcx>,
 938 }
 939
 940 #[derive(Clone, RustcEncodable, RustcDecodable)]
 941 pub struct TypedConstVal<'tcx> {
 942     pub ty: Ty<'tcx>,
 943     pub span: Span,
 944     pub value: ConstUsize,
 945 }
 946
 947 impl<'tcx> Debug for TypedConstVal<'tcx> {
 948     fn fmt(&self, fmt: &mut Formatter) -> fmt::Result {
 949         write!(fmt, "const {}", ConstInt::Usize(self.value))
 950     }
 951 }
 952
 953 #[derive(Clone, PartialEq, Eq, Hash, RustcEncodable, RustcDecodable)]
 954 pub enum Literal<'tcx> {
 955     Item {
 956         def_id: DefId,
 957         substs: &'tcx Substs<'tcx>,
 958     },
 959     Value {
 960         value: ConstVal,
 961     },
 962 }
 963
 964 impl<'tcx> Debug for Constant<'tcx> {
 965     fn fmt(&self, fmt: &mut Formatter) -> fmt::Result {
 966         write!(fmt, "{:?}", self.literal)
 967     }
 968 }
 969
 970 impl<'tcx> Debug for Literal<'tcx> {
 971     fn fmt(&self, fmt: &mut Formatter) -> fmt::Result {
 972         use self::Literal::*;
 973         match *self {
 974             Item { def_id, substs } => {
 975                 ppaux::parameterized(fmt, substs, def_id, ppaux::Ns::Value, &[],
 976                                      |tcx| tcx.lookup_item_type(def_id).generics)
 977             }
 978             Value { ref value } => {
 979                 write!(fmt, "const ")?;
 980                 fmt_const_val(fmt, value)
 981             }
 982         }
 983     }
 984 }
 985
 986 /// Write a `ConstVal` in a way closer to the original source code than the `Debug` output.
 987 fn fmt_const_val<W: Write>(fmt: &mut W, const_val: &ConstVal) -> fmt::Result {
 988     use middle::const_eval::ConstVal::*;
 989     match *const_val {
 990         Float(f) => write!(fmt, "{:?}", f),
 991         Integral(n) => write!(fmt, "{}", n),
 992         Str(ref s) => write!(fmt, "{:?}", s),
 993         ByteStr(ref bytes) => {
 994             let escaped: String = bytes
 995                 .iter()
 996                 .flat_map(|&ch| ascii::escape_default(ch).map(|c| c as char))
 997                 .collect();
 998             write!(fmt, "b\"{}\"", escaped)
 999         }
1000         Bool(b) => write!(fmt, "{:?}", b),
1001         Function(def_id) => write!(fmt, "{}", item_path_str(def_id)),
1002         Struct(node_id) | Tuple(node_id) | Array(node_id, _) | Repeat(node_id, _) =>
1003             write!(fmt, "{}", node_to_string(node_id)),
1004         Char(c) => write!(fmt, "{:?}", c),
1005         Dummy => unreachable!(),
1006     }
1007 }
1008
1009 fn node_to_string(node_id: ast::NodeId) -> String {
1010     ty::tls::with(|tcx| tcx.map.node_to_user_string(node_id))
1011 }
1012
1013 fn item_path_str(def_id: DefId) -> String {
1014     ty::tls::with(|tcx| tcx.item_path_str(def_id))
1015 }