src/librustc_mir/hair.rs

   1 // Copyright 2015 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 //! The MIR is translated from some high-level abstract IR
  12 //! (HAIR). This section defines the HAIR along with a trait for
  13 //! accessing it. The intention is to allow MIR construction to be
  14 //! unit-tested and separated from the Rust source and compiler data
  15 //! structures.
  16
  17 use repr::{BinOp, BorrowKind, Field, Literal, Mutability, UnOp};
  18 use std::fmt::Debug;
  19 use std::hash::Hash;
  20
  21 pub trait Hair: Sized+Debug+Clone+Eq+Hash { // (*)
  22
  23     // (*) the `Sized` and Debug` bounds are the only ones that really
  24     // make sense.  The rest are just there so that we can
  25     // `#[derive(Clone)]` on things that are parameterized over
  26     // `H:HAIR`. It's kind of lame.
  27
  28     type VarId: Copy+Debug+Eq+Hash;                              // e.g., NodeId for a variable
  29     type DefId: Copy+Debug+Eq+Hash;                              // e.g., DefId
  30     type AdtDef: Copy+Debug+Eq+Hash;                             // e.g., AdtDef<'tcx>
  31     type Name: Copy+Debug+Eq+Hash;                               // e.g., ast::Name
  32     type Ident: Copy+Debug+Eq+Hash;                              // e.g., ast::Ident
  33     type InternedString: Clone+Debug+Eq+Hash;                    // e.g., InternedString
  34     type Bytes: Clone+Debug+Eq+Hash;                             // e.g., Rc<Vec<u8>>
  35     type Span: Copy+Debug+Eq;                                    // e.g., syntax::codemap::Span
  36     type Projection: Clone+Debug+Eq;                             // e.g., ty::ProjectionTy<'tcx>
  37     type Substs: Clone+Debug+Eq;                                 // e.g., substs::Substs<'tcx>
  38     type ClosureSubsts: Clone+Debug+Eq;                          // e.g., ty::ClosureSubsts<'tcx>
  39     type Ty: Clone+Debug+Eq;                                     // e.g., ty::Ty<'tcx>
  40     type Region: Copy+Debug;                                     // e.g., ty::Region
  41     type CodeExtent: Copy+Debug+Hash+Eq;                         // e.g., region::CodeExtent
  42     type Pattern: Clone+Debug+Mirror<Self,Output=Pattern<Self>>; // e.g., &P<ast::Pat>
  43     type Expr: Clone+Debug+Mirror<Self,Output=Expr<Self>>;       // e.g., &P<ast::Expr>
  44     type Stmt: Clone+Debug+Mirror<Self,Output=Stmt<Self>>;       // e.g., &P<ast::Stmt>
  45     type Block: Clone+Debug+Mirror<Self,Output=Block<Self>>;     // e.g., &P<ast::Block>
  46     type InlineAsm: Clone+Debug+Eq+Hash;                         // e.g., ast::InlineAsm
  47
  48     /// Normalizes `ast` into the appropriate `mirror` type.
  49     fn mirror<M:Mirror<Self>>(&mut self, ast: M) -> M::Output {
  50         ast.make_mirror(self)
  51     }
  52
  53     /// Returns the unit type `()`
  54     fn unit_ty(&mut self) -> Self::Ty;
  55
  56     /// Returns the type `usize`.
  57     fn usize_ty(&mut self) -> Self::Ty;
  58
  59     /// Returns the type `bool`.
  60     fn bool_ty(&mut self) -> Self::Ty;
  61
  62     /// Returns a reference to `PartialEq::<T,T>::eq`
  63     fn partial_eq(&mut self, ty: Self::Ty) -> ItemRef<Self>;
  64
  65     /// Returns a reference to `PartialOrd::<T,T>::le`
  66     fn partial_le(&mut self, ty: Self::Ty) -> ItemRef<Self>;
  67
  68     /// Returns the number of variants for the given enum
  69     fn num_variants(&mut self, adt: Self::AdtDef) -> usize;
  70
  71     fn fields(&mut self, adt: Self::AdtDef, variant_index: usize) -> Vec<Field<Self>>;
  72
  73     /// true if a value of type `ty` (may) need to be dropped; this
  74     /// may return false even for non-Copy types if there is no
  75     /// destructor to execute. If correct result is not known, may be
  76     /// approximated by returning `true`; this will result in more
  77     /// drops but not incorrect code.
  78     fn needs_drop(&mut self, ty: Self::Ty, span: Self::Span) -> bool;
  79
  80     /// Report an internal inconsistency.
  81     fn span_bug(&mut self, span: Self::Span, message: &str) -> !;
  82 }
  83
  84 #[derive(Clone, Debug)]
  85 pub struct ItemRef<H:Hair> {
  86     pub ty: H::Ty,
  87     pub def_id: H::DefId,
  88     pub substs: H::Substs,
  89 }
  90
  91 #[derive(Clone, Debug)]
  92 pub struct Block<H:Hair> {
  93     pub extent: H::CodeExtent,
  94     pub span: H::Span,
  95     pub stmts: Vec<StmtRef<H>>,
  96     pub expr: Option<ExprRef<H>>,
  97 }
  98
  99 #[derive(Clone, Debug)]
 100 pub enum StmtRef<H:Hair> {
 101     Hair(H::Stmt),
 102     Mirror(Box<Stmt<H>>),
 103 }
 104
 105 #[derive(Clone, Debug)]
 106 pub struct Stmt<H:Hair> {
 107     pub span: H::Span,
 108     pub kind: StmtKind<H>,
 109 }
 110
 111 #[derive(Clone, Debug)]
 112 pub enum StmtKind<H:Hair> {
 113     Expr {
 114         /// scope for this statement; may be used as lifetime of temporaries
 115         scope: H::CodeExtent,
 116
 117         /// expression being evaluated in this statement
 118         expr: ExprRef<H>
 119     },
 120
 121     Let {
 122         /// scope for variables bound in this let; covers this and
 123         /// remaining statements in block
 124         remainder_scope: H::CodeExtent,
 125
 126         /// scope for the initialization itself; might be used as
 127         /// lifetime of temporaries
 128         init_scope: H::CodeExtent,
 129
 130         /// let <PAT> = ...
 131         pattern: PatternRef<H>,
 132
 133         /// let pat = <INIT> ...
 134         initializer: Option<ExprRef<H>>,
 135
 136         /// let pat = init; <STMTS>
 137         stmts: Vec<StmtRef<H>>
 138     },
 139 }
 140
 141 // The Hair trait implementor translates their expressions (`H::Expr`)
 142 // into instances of this `Expr` enum. This translation can be done
 143 // basically as lazilly or as eagerly as desired: every recursive
 144 // reference to an expression in this enum is an `ExprRef<H>`, which
 145 // may in turn be another instance of this enum (boxed), or else an
 146 // untranslated `H::Expr`. Note that instances of `Expr` are very
 147 // shortlived. They are created by `Hair::to_expr`, analyzed and
 148 // converted into MIR, and then discarded.
 149 //
 150 // If you compare `Expr` to the full compiler AST, you will see it is
 151 // a good bit simpler. In fact, a number of the more straight-forward
 152 // MIR simplifications are already done in the impl of `Hair`. For
 153 // example, method calls and overloaded operators are absent: they are
 154 // expected to be converted into `Expr::Call` instances.
 155 #[derive(Clone, Debug)]
 156 pub struct Expr<H:Hair> {
 157     // type of this expression
 158     pub ty: H::Ty,
 159
 160     // lifetime of this expression if it should be spilled into a
 161     // temporary; should be None only if in a constant context
 162     pub temp_lifetime: Option<H::CodeExtent>,
 163
 164     // span of the expression in the source
 165     pub span: H::Span,
 166
 167     // kind of expression
 168     pub kind: ExprKind<H>,
 169 }
 170
 171 #[derive(Clone, Debug)]
 172 pub enum ExprKind<H:Hair> {
 173     Scope { extent: H::CodeExtent, value: ExprRef<H> },
 174     Box { place: Option<ExprRef<H>>, value: ExprRef<H> },
 175     Call { fun: ExprRef<H>, args: Vec<ExprRef<H>> },
 176     Deref { arg: ExprRef<H> }, // NOT overloaded!
 177     Binary { op: BinOp, lhs: ExprRef<H>, rhs: ExprRef<H> }, // NOT overloaded!
 178     LogicalOp { op: LogicalOp, lhs: ExprRef<H>, rhs: ExprRef<H> },
 179     Unary { op: UnOp, arg: ExprRef<H> }, // NOT overloaded!
 180     Cast { source: ExprRef<H> },
 181     ReifyFnPointer { source: ExprRef<H> },
 182     UnsafeFnPointer { source: ExprRef<H> },
 183     Unsize { source: ExprRef<H> },
 184     If { condition: ExprRef<H>, then: ExprRef<H>, otherwise: Option<ExprRef<H>> },
 185     Loop { condition: Option<ExprRef<H>>, body: ExprRef<H>, },
 186     Match { discriminant: ExprRef<H>, arms: Vec<Arm<H>> },
 187     Block { body: H::Block },
 188     Assign { lhs: ExprRef<H>, rhs: ExprRef<H> },
 189     AssignOp { op: BinOp, lhs: ExprRef<H>, rhs: ExprRef<H> },
 190     Field { lhs: ExprRef<H>, name: Field<H> },
 191     Index { lhs: ExprRef<H>, index: ExprRef<H> },
 192     VarRef { id: H::VarId },
 193     SelfRef, // first argument, used for self in a closure
 194     StaticRef { id: H::DefId },
 195     Borrow { region: H::Region, borrow_kind: BorrowKind, arg: ExprRef<H> },
 196     Break { label: Option<H::CodeExtent> },
 197     Continue { label: Option<H::CodeExtent> },
 198     Return { value: Option<ExprRef<H>> },
 199     Repeat { value: ExprRef<H>, count: ExprRef<H> },
 200     Vec { fields: Vec<ExprRef<H>> },
 201     Tuple { fields: Vec<ExprRef<H>> },
 202     Adt { adt_def: H::AdtDef,
 203           variant_index: usize,
 204           substs: H::Substs,
 205           fields: Vec<FieldExprRef<H>>,
 206           base: Option<ExprRef<H>> },
 207     Closure { closure_id: H::DefId, substs: H::ClosureSubsts,
 208               upvars: Vec<ExprRef<H>> },
 209     Literal { literal: Literal<H> },
 210     InlineAsm { asm: H::InlineAsm },
 211 }
 212
 213 #[derive(Clone, Debug)]
 214 pub enum ExprRef<H:Hair> {
 215     Hair(H::Expr),
 216     Mirror(Box<Expr<H>>),
 217 }
 218
 219 #[derive(Clone, Debug)]
 220 pub struct FieldExprRef<H:Hair> {
 221     pub name: Field<H>,
 222     pub expr: ExprRef<H>,
 223 }
 224
 225 #[derive(Clone, Debug)]
 226 pub struct Arm<H:Hair> {
 227     pub patterns: Vec<PatternRef<H>>,
 228     pub guard: Option<ExprRef<H>>,
 229     pub body: ExprRef<H>,
 230 }
 231
 232 #[derive(Clone, Debug)]
 233 pub struct Pattern<H:Hair> {
 234     pub ty: H::Ty,
 235     pub span: H::Span,
 236     pub kind: PatternKind<H>,
 237 }
 238
 239 #[derive(Copy, Clone, Debug)]
 240 pub enum LogicalOp {
 241     And,
 242     Or
 243 }
 244
 245 #[derive(Clone, Debug)]
 246 pub enum PatternKind<H:Hair> {
 247     Wild,
 248
 249     // x, ref x, x @ P, etc
 250     Binding { mutability: Mutability,
 251               name: H::Ident,
 252               mode: BindingMode<H>,
 253               var: H::VarId,
 254               ty: H::Ty,
 255               subpattern: Option<PatternRef<H>> },
 256
 257     // Foo(...) or Foo{...} or Foo, where `Foo` is a variant name from an adt with >1 variants
 258     Variant { adt_def: H::AdtDef, variant_index: usize, subpatterns: Vec<FieldPatternRef<H>> },
 259
 260     // (...), Foo(...), Foo{...}, or Foo, where `Foo` is a variant name from an adt with 1 variant
 261     Leaf { subpatterns: Vec<FieldPatternRef<H>> },
 262
 263     Deref { subpattern: PatternRef<H> }, // box P, &P, &mut P, etc
 264
 265     Constant { expr: ExprRef<H> },
 266
 267     Range { lo: ExprRef<H>, hi: ExprRef<H> },
 268
 269     // matches against a slice, checking the length and extracting elements
 270     Slice { prefix: Vec<PatternRef<H>>,
 271             slice: Option<PatternRef<H>>,
 272             suffix: Vec<PatternRef<H>> },
 273
 274     // fixed match against an array, irrefutable
 275     Array { prefix: Vec<PatternRef<H>>,
 276             slice: Option<PatternRef<H>>,
 277             suffix: Vec<PatternRef<H>> },
 278 }
 279
 280 #[derive(Copy, Clone, Debug)]
 281 pub enum BindingMode<H:Hair> {
 282     ByValue,
 283     ByRef(H::Region, BorrowKind),
 284 }
 285
 286 #[derive(Clone, Debug)]
 287 pub enum PatternRef<H:Hair> {
 288     Hair(H::Pattern),
 289     Mirror(Box<Pattern<H>>),
 290 }
 291
 292 #[derive(Clone, Debug)]
 293 pub struct FieldPatternRef<H:Hair> {
 294     pub field: Field<H>,
 295     pub pattern: PatternRef<H>,
 296 }
 297
 298 ///////////////////////////////////////////////////////////////////////////
 299 // The Mirror trait
 300
 301 /// "Mirroring" is the process of converting from a Hair type into one
 302 /// of the types in this file. For example, the mirror of a `H::Expr`
 303 /// is an `Expr<H>`. Mirroring is the point at which the actual IR is
 304 /// converting into the more idealized representation described in
 305 /// this file. Mirroring is gradual: when you mirror an outer
 306 /// expression like `e1 + e2`, the references to the inner expressions
 307 /// `e1` and `e2` are `ExprRef<H>` instances, and they may or may not
 308 /// be eagerly mirrored.  This allows a single AST node from the
 309 /// compiler to expand into one or more Hair nodes, which lets the Hair
 310 /// nodes be simpler.
 311 pub trait Mirror<H:Hair> {
 312     type Output;
 313
 314     fn make_mirror(self, hir: &mut H) -> Self::Output;
 315 }
 316
 317 impl<H:Hair> Mirror<H> for Expr<H> {
 318     type Output = Expr<H>;
 319
 320     fn make_mirror(self, _: &mut H) -> Expr<H> {
 321         self
 322     }
 323 }
 324
 325 impl<H:Hair> Mirror<H> for ExprRef<H> {
 326     type Output = Expr<H>;
 327
 328     fn make_mirror(self, hir: &mut H) -> Expr<H> {
 329         match self {
 330             ExprRef::Hair(h) => h.make_mirror(hir),
 331             ExprRef::Mirror(m) => *m,
 332         }
 333     }
 334 }
 335
 336 impl<H:Hair> Mirror<H> for Stmt<H> {
 337     type Output = Stmt<H>;
 338
 339     fn make_mirror(self, _: &mut H) -> Stmt<H> {
 340         self
 341     }
 342 }
 343
 344 impl<H:Hair> Mirror<H> for StmtRef<H> {
 345     type Output = Stmt<H>;
 346
 347     fn make_mirror(self, hir: &mut H) -> Stmt<H> {
 348         match self {
 349             StmtRef::Hair(h) => h.make_mirror(hir),
 350             StmtRef::Mirror(m) => *m,
 351         }
 352     }
 353 }
 354
 355 impl<H:Hair> Mirror<H> for Pattern<H> {
 356     type Output = Pattern<H>;
 357
 358     fn make_mirror(self, _: &mut H) -> Pattern<H> {
 359         self
 360     }
 361 }
 362
 363 impl<H:Hair> Mirror<H> for PatternRef<H> {
 364     type Output = Pattern<H>;
 365
 366     fn make_mirror(self, hir: &mut H) -> Pattern<H> {
 367         match self {
 368             PatternRef::Hair(h) => h.make_mirror(hir),
 369             PatternRef::Mirror(m) => *m,
 370         }
 371     }
 372 }
 373
 374 impl<H:Hair> Mirror<H> for Block<H> {
 375     type Output = Block<H>;
 376
 377     fn make_mirror(self, _: &mut H) -> Block<H> {
 378         self
 379     }
 380 }
 381