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