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