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