src/librustc/hir/mod.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 Rust HIR.
  12
  13 pub use self::BindingMode::*;
  14 pub use self::BinOp_::*;
  15 pub use self::BlockCheckMode::*;
  16 pub use self::CaptureClause::*;
  17 pub use self::Decl_::*;
  18 pub use self::Expr_::*;
  19 pub use self::FunctionRetTy::*;
  20 pub use self::ForeignItem_::*;
  21 pub use self::Item_::*;
  22 pub use self::Mutability::*;
  23 pub use self::PrimTy::*;
  24 pub use self::Stmt_::*;
  25 pub use self::TraitItem_::*;
  26 pub use self::Ty_::*;
  27 pub use self::TyParamBound::*;
  28 pub use self::UnOp::*;
  29 pub use self::UnsafeSource::*;
  30 pub use self::ViewPath_::*;
  31 pub use self::Visibility::{Public, Inherited};
  32 pub use self::PathParameters::*;
  33
  34 use hir::def::Def;
  35 use hir::def_id::DefId;
  36 use util::nodemap::{NodeMap, FxHashSet};
  37
  38 use syntax_pos::{mk_sp, Span, ExpnId, DUMMY_SP};
  39 use syntax::codemap::{self, respan, Spanned};
  40 use syntax::abi::Abi;
  41 use syntax::ast::{Name, NodeId, DUMMY_NODE_ID, AsmDialect};
  42 use syntax::ast::{Attribute, Lit, StrStyle, FloatTy, IntTy, UintTy, MetaItem};
  43 use syntax::ptr::P;
  44 use syntax::symbol::{Symbol, keywords};
  45 use syntax::tokenstream::TokenTree;
  46 use syntax::util::ThinVec;
  47
  48 use std::collections::BTreeMap;
  49 use std::fmt;
  50
  51 /// HIR doesn't commit to a concrete storage type and have its own alias for a vector.
  52 /// It can be `Vec`, `P<[T]>` or potentially `Box<[T]>`, or some other container with similar
  53 /// behavior. Unlike AST, HIR is mostly a static structure, so we can use an owned slice instead
  54 /// of `Vec` to avoid keeping extra capacity.
  55 pub type HirVec<T> = P<[T]>;
  56
  57 macro_rules! hir_vec {
  58     ($elem:expr; $n:expr) => (
  59         $crate::hir::HirVec::from(vec![$elem; $n])
  60     );
  61     ($($x:expr),*) => (
  62         $crate::hir::HirVec::from(vec![$($x),*])
  63     );
  64     ($($x:expr,)*) => (hir_vec![$($x),*])
  65 }
  66
  67 pub mod check_attr;
  68 pub mod def;
  69 pub mod def_id;
  70 pub mod intravisit;
  71 pub mod itemlikevisit;
  72 pub mod lowering;
  73 pub mod map;
  74 pub mod pat_util;
  75 pub mod print;
  76 pub mod svh;
  77
  78 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Copy)]
  79 pub struct Lifetime {
  80     pub id: NodeId,
  81     pub span: Span,
  82     pub name: Name,
  83 }
  84
  85 impl fmt::Debug for Lifetime {
  86     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
  87         write!(f,
  88                "lifetime({}: {})",
  89                self.id,
  90                print::lifetime_to_string(self))
  91     }
  92 }
  93
  94 /// A lifetime definition, eg `'a: 'b+'c+'d`
  95 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
  96 pub struct LifetimeDef {
  97     pub lifetime: Lifetime,
  98     pub bounds: HirVec<Lifetime>,
  99     pub pure_wrt_drop: bool,
 100 }
 101
 102 /// A "Path" is essentially Rust's notion of a name; for instance:
 103 /// std::cmp::PartialEq  .  It's represented as a sequence of identifiers,
 104 /// along with a bunch of supporting information.
 105 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash)]
 106 pub struct Path {
 107     pub span: Span,
 108     /// A `::foo` path, is relative to the crate root rather than current
 109     /// module (like paths in an import).
 110     pub global: bool,
 111     /// The segments in the path: the things separated by `::`.
 112     pub segments: HirVec<PathSegment>,
 113 }
 114
 115 impl fmt::Debug for Path {
 116     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 117         write!(f, "path({})", print::path_to_string(self))
 118     }
 119 }
 120
 121 impl fmt::Display for Path {
 122     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 123         write!(f, "{}", print::path_to_string(self))
 124     }
 125 }
 126
 127 impl Path {
 128     /// Convert a span and an identifier to the corresponding
 129     /// 1-segment path.
 130     pub fn from_name(s: Span, name: Name) -> Path {
 131         Path {
 132             span: s,
 133             global: false,
 134             segments: hir_vec![PathSegment {
 135                 name: name,
 136                 parameters: PathParameters::none()
 137             }],
 138         }
 139     }
 140 }
 141
 142 /// A segment of a path: an identifier, an optional lifetime, and a set of
 143 /// types.
 144 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 145 pub struct PathSegment {
 146     /// The identifier portion of this path segment.
 147     pub name: Name,
 148
 149     /// Type/lifetime parameters attached to this path. They come in
 150     /// two flavors: `Path<A,B,C>` and `Path(A,B) -> C`. Note that
 151     /// this is more than just simple syntactic sugar; the use of
 152     /// parens affects the region binding rules, so we preserve the
 153     /// distinction.
 154     pub parameters: PathParameters,
 155 }
 156
 157 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 158 pub enum PathParameters {
 159     /// The `<'a, A,B,C>` in `foo::bar::baz::<'a, A,B,C>`
 160     AngleBracketedParameters(AngleBracketedParameterData),
 161     /// The `(A,B)` and `C` in `Foo(A,B) -> C`
 162     ParenthesizedParameters(ParenthesizedParameterData),
 163 }
 164
 165 impl PathParameters {
 166     pub fn none() -> PathParameters {
 167         AngleBracketedParameters(AngleBracketedParameterData {
 168             lifetimes: HirVec::new(),
 169             types: HirVec::new(),
 170             infer_types: true,
 171             bindings: HirVec::new(),
 172         })
 173     }
 174
 175     pub fn is_empty(&self) -> bool {
 176         match *self {
 177             AngleBracketedParameters(ref data) => data.is_empty(),
 178
 179             // Even if the user supplied no types, something like
 180             // `X()` is equivalent to `X<(),()>`.
 181             ParenthesizedParameters(..) => false,
 182         }
 183     }
 184
 185     pub fn has_lifetimes(&self) -> bool {
 186         match *self {
 187             AngleBracketedParameters(ref data) => !data.lifetimes.is_empty(),
 188             ParenthesizedParameters(_) => false,
 189         }
 190     }
 191
 192     pub fn has_types(&self) -> bool {
 193         match *self {
 194             AngleBracketedParameters(ref data) => !data.types.is_empty(),
 195             ParenthesizedParameters(..) => true,
 196         }
 197     }
 198
 199     /// Returns the types that the user wrote. Note that these do not necessarily map to the type
 200     /// parameters in the parenthesized case.
 201     pub fn types(&self) -> HirVec<&P<Ty>> {
 202         match *self {
 203             AngleBracketedParameters(ref data) => {
 204                 data.types.iter().collect()
 205             }
 206             ParenthesizedParameters(ref data) => {
 207                 data.inputs
 208                     .iter()
 209                     .chain(data.output.iter())
 210                     .collect()
 211             }
 212         }
 213     }
 214
 215     pub fn lifetimes(&self) -> HirVec<&Lifetime> {
 216         match *self {
 217             AngleBracketedParameters(ref data) => {
 218                 data.lifetimes.iter().collect()
 219             }
 220             ParenthesizedParameters(_) => {
 221                 HirVec::new()
 222             }
 223         }
 224     }
 225
 226     pub fn bindings(&self) -> HirVec<&TypeBinding> {
 227         match *self {
 228             AngleBracketedParameters(ref data) => {
 229                 data.bindings.iter().collect()
 230             }
 231             ParenthesizedParameters(_) => {
 232                 HirVec::new()
 233             }
 234         }
 235     }
 236 }
 237
 238 /// A path like `Foo<'a, T>`
 239 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 240 pub struct AngleBracketedParameterData {
 241     /// The lifetime parameters for this path segment.
 242     pub lifetimes: HirVec<Lifetime>,
 243     /// The type parameters for this path segment, if present.
 244     pub types: HirVec<P<Ty>>,
 245     /// Whether to infer remaining type parameters, if any.
 246     /// This only applies to expression and pattern paths, and
 247     /// out of those only the segments with no type parameters
 248     /// to begin with, e.g. `Vec::new` is `<Vec<..>>::new::<..>`.
 249     pub infer_types: bool,
 250     /// Bindings (equality constraints) on associated types, if present.
 251     /// E.g., `Foo<A=Bar>`.
 252     pub bindings: HirVec<TypeBinding>,
 253 }
 254
 255 impl AngleBracketedParameterData {
 256     fn is_empty(&self) -> bool {
 257         self.lifetimes.is_empty() && self.types.is_empty() && self.bindings.is_empty()
 258     }
 259 }
 260
 261 /// A path like `Foo(A,B) -> C`
 262 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 263 pub struct ParenthesizedParameterData {
 264     /// Overall span
 265     pub span: Span,
 266
 267     /// `(A,B)`
 268     pub inputs: HirVec<P<Ty>>,
 269
 270     /// `C`
 271     pub output: Option<P<Ty>>,
 272 }
 273
 274 /// The AST represents all type param bounds as types.
 275 /// typeck::collect::compute_bounds matches these against
 276 /// the "special" built-in traits (see middle::lang_items) and
 277 /// detects Copy, Send and Sync.
 278 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 279 pub enum TyParamBound {
 280     TraitTyParamBound(PolyTraitRef, TraitBoundModifier),
 281     RegionTyParamBound(Lifetime),
 282 }
 283
 284 /// A modifier on a bound, currently this is only used for `?Sized`, where the
 285 /// modifier is `Maybe`. Negative bounds should also be handled here.
 286 #[derive(Copy, Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 287 pub enum TraitBoundModifier {
 288     None,
 289     Maybe,
 290 }
 291
 292 pub type TyParamBounds = HirVec<TyParamBound>;
 293
 294 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 295 pub struct TyParam {
 296     pub name: Name,
 297     pub id: NodeId,
 298     pub bounds: TyParamBounds,
 299     pub default: Option<P<Ty>>,
 300     pub span: Span,
 301     pub pure_wrt_drop: bool,
 302 }
 303
 304 /// Represents lifetimes and type parameters attached to a declaration
 305 /// of a function, enum, trait, etc.
 306 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 307 pub struct Generics {
 308     pub lifetimes: HirVec<LifetimeDef>,
 309     pub ty_params: HirVec<TyParam>,
 310     pub where_clause: WhereClause,
 311     pub span: Span,
 312 }
 313
 314 impl Generics {
 315     pub fn empty() -> Generics {
 316         Generics {
 317             lifetimes: HirVec::new(),
 318             ty_params: HirVec::new(),
 319             where_clause: WhereClause {
 320                 id: DUMMY_NODE_ID,
 321                 predicates: HirVec::new(),
 322             },
 323             span: DUMMY_SP,
 324         }
 325     }
 326
 327     pub fn is_lt_parameterized(&self) -> bool {
 328         !self.lifetimes.is_empty()
 329     }
 330
 331     pub fn is_type_parameterized(&self) -> bool {
 332         !self.ty_params.is_empty()
 333     }
 334
 335     pub fn is_parameterized(&self) -> bool {
 336         self.is_lt_parameterized() || self.is_type_parameterized()
 337     }
 338 }
 339
 340 pub enum UnsafeGeneric {
 341     Region(LifetimeDef, &'static str),
 342     Type(TyParam, &'static str),
 343 }
 344
 345 impl UnsafeGeneric {
 346     pub fn attr_name(&self) -> &'static str {
 347         match *self {
 348             UnsafeGeneric::Region(_, s) => s,
 349             UnsafeGeneric::Type(_, s) => s,
 350         }
 351     }
 352 }
 353
 354 impl Generics {
 355     pub fn carries_unsafe_attr(&self) -> Option<UnsafeGeneric> {
 356         for r in &self.lifetimes {
 357             if r.pure_wrt_drop {
 358                 return Some(UnsafeGeneric::Region(r.clone(), "may_dangle"));
 359             }
 360         }
 361         for t in &self.ty_params {
 362             if t.pure_wrt_drop {
 363                 return Some(UnsafeGeneric::Type(t.clone(), "may_dangle"));
 364             }
 365         }
 366         return None;
 367     }
 368 }
 369
 370 /// A `where` clause in a definition
 371 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 372 pub struct WhereClause {
 373     pub id: NodeId,
 374     pub predicates: HirVec<WherePredicate>,
 375 }
 376
 377 /// A single predicate in a `where` clause
 378 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 379 pub enum WherePredicate {
 380     /// A type binding, eg `for<'c> Foo: Send+Clone+'c`
 381     BoundPredicate(WhereBoundPredicate),
 382     /// A lifetime predicate, e.g. `'a: 'b+'c`
 383     RegionPredicate(WhereRegionPredicate),
 384     /// An equality predicate (unsupported)
 385     EqPredicate(WhereEqPredicate),
 386 }
 387
 388 /// A type bound, eg `for<'c> Foo: Send+Clone+'c`
 389 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 390 pub struct WhereBoundPredicate {
 391     pub span: Span,
 392     /// Any lifetimes from a `for` binding
 393     pub bound_lifetimes: HirVec<LifetimeDef>,
 394     /// The type being bounded
 395     pub bounded_ty: P<Ty>,
 396     /// Trait and lifetime bounds (`Clone+Send+'static`)
 397     pub bounds: TyParamBounds,
 398 }
 399
 400 /// A lifetime predicate, e.g. `'a: 'b+'c`
 401 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 402 pub struct WhereRegionPredicate {
 403     pub span: Span,
 404     pub lifetime: Lifetime,
 405     pub bounds: HirVec<Lifetime>,
 406 }
 407
 408 /// An equality predicate (unsupported), e.g. `T=int`
 409 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 410 pub struct WhereEqPredicate {
 411     pub id: NodeId,
 412     pub span: Span,
 413     pub path: Path,
 414     pub ty: P<Ty>,
 415 }
 416
 417 pub type CrateConfig = HirVec<P<MetaItem>>;
 418
 419 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Debug)]
 420 pub struct Crate {
 421     pub module: Mod,
 422     pub attrs: HirVec<Attribute>,
 423     pub span: Span,
 424     pub exported_macros: HirVec<MacroDef>,
 425
 426     // NB: We use a BTreeMap here so that `visit_all_items` iterates
 427     // over the ids in increasing order. In principle it should not
 428     // matter what order we visit things in, but in *practice* it
 429     // does, because it can affect the order in which errors are
 430     // detected, which in turn can make compile-fail tests yield
 431     // slightly different results.
 432     pub items: BTreeMap<NodeId, Item>,
 433
 434     pub impl_items: BTreeMap<ImplItemId, ImplItem>,
 435 }
 436
 437 impl Crate {
 438     pub fn item(&self, id: NodeId) -> &Item {
 439         &self.items[&id]
 440     }
 441
 442     pub fn impl_item(&self, id: ImplItemId) -> &ImplItem {
 443         &self.impl_items[&id]
 444     }
 445
 446     /// Visits all items in the crate in some determinstic (but
 447     /// unspecified) order. If you just need to process every item,
 448     /// but don't care about nesting, this method is the best choice.
 449     ///
 450     /// If you do care about nesting -- usually because your algorithm
 451     /// follows lexical scoping rules -- then you want a different
 452     /// approach. You should override `visit_nested_item` in your
 453     /// visitor and then call `intravisit::walk_crate` instead.
 454     pub fn visit_all_item_likes<'hir, V>(&'hir self, visitor: &mut V)
 455         where V: itemlikevisit::ItemLikeVisitor<'hir>
 456     {
 457         for (_, item) in &self.items {
 458             visitor.visit_item(item);
 459         }
 460
 461         for (_, impl_item) in &self.impl_items {
 462             visitor.visit_impl_item(impl_item);
 463         }
 464     }
 465 }
 466
 467 /// A macro definition, in this crate or imported from another.
 468 ///
 469 /// Not parsed directly, but created on macro import or `macro_rules!` expansion.
 470 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 471 pub struct MacroDef {
 472     pub name: Name,
 473     pub attrs: HirVec<Attribute>,
 474     pub id: NodeId,
 475     pub span: Span,
 476     pub imported_from: Option<Name>,
 477     pub allow_internal_unstable: bool,
 478     pub body: HirVec<TokenTree>,
 479 }
 480
 481 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 482 pub struct Block {
 483     /// Statements in a block
 484     pub stmts: HirVec<Stmt>,
 485     /// An expression at the end of the block
 486     /// without a semicolon, if any
 487     pub expr: Option<P<Expr>>,
 488     pub id: NodeId,
 489     /// Distinguishes between `unsafe { ... }` and `{ ... }`
 490     pub rules: BlockCheckMode,
 491     pub span: Span,
 492 }
 493
 494 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash)]
 495 pub struct Pat {
 496     pub id: NodeId,
 497     pub node: PatKind,
 498     pub span: Span,
 499 }
 500
 501 impl fmt::Debug for Pat {
 502     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 503         write!(f, "pat({}: {})", self.id, print::pat_to_string(self))
 504     }
 505 }
 506
 507 impl Pat {
 508     // FIXME(#19596) this is a workaround, but there should be a better way
 509     fn walk_<G>(&self, it: &mut G) -> bool
 510         where G: FnMut(&Pat) -> bool
 511     {
 512         if !it(self) {
 513             return false;
 514         }
 515
 516         match self.node {
 517             PatKind::Binding(.., Some(ref p)) => p.walk_(it),
 518             PatKind::Struct(_, ref fields, _) => {
 519                 fields.iter().all(|field| field.node.pat.walk_(it))
 520             }
 521             PatKind::TupleStruct(_, ref s, _) | PatKind::Tuple(ref s, _) => {
 522                 s.iter().all(|p| p.walk_(it))
 523             }
 524             PatKind::Box(ref s) | PatKind::Ref(ref s, _) => {
 525                 s.walk_(it)
 526             }
 527             PatKind::Slice(ref before, ref slice, ref after) => {
 528                 before.iter().all(|p| p.walk_(it)) &&
 529                 slice.iter().all(|p| p.walk_(it)) &&
 530                 after.iter().all(|p| p.walk_(it))
 531             }
 532             PatKind::Wild |
 533             PatKind::Lit(_) |
 534             PatKind::Range(..) |
 535             PatKind::Binding(..) |
 536             PatKind::Path(_) => {
 537                 true
 538             }
 539         }
 540     }
 541
 542     pub fn walk<F>(&self, mut it: F) -> bool
 543         where F: FnMut(&Pat) -> bool
 544     {
 545         self.walk_(&mut it)
 546     }
 547 }
 548
 549 /// A single field in a struct pattern
 550 ///
 551 /// Patterns like the fields of Foo `{ x, ref y, ref mut z }`
 552 /// are treated the same as` x: x, y: ref y, z: ref mut z`,
 553 /// except is_shorthand is true
 554 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 555 pub struct FieldPat {
 556     /// The identifier for the field
 557     pub name: Name,
 558     /// The pattern the field is destructured to
 559     pub pat: P<Pat>,
 560     pub is_shorthand: bool,
 561 }
 562
 563 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
 564 pub enum BindingMode {
 565     BindByRef(Mutability),
 566     BindByValue(Mutability),
 567 }
 568
 569 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 570 pub enum PatKind {
 571     /// Represents a wildcard pattern (`_`)
 572     Wild,
 573
 574     /// A fresh binding `ref mut binding @ OPT_SUBPATTERN`.
 575     Binding(BindingMode, Spanned<Name>, Option<P<Pat>>),
 576
 577     /// A struct or struct variant pattern, e.g. `Variant {x, y, ..}`.
 578     /// The `bool` is `true` in the presence of a `..`.
 579     Struct(QPath, HirVec<Spanned<FieldPat>>, bool),
 580
 581     /// A tuple struct/variant pattern `Variant(x, y, .., z)`.
 582     /// If the `..` pattern fragment is present, then `Option<usize>` denotes its position.
 583     /// 0 <= position <= subpats.len()
 584     TupleStruct(QPath, HirVec<P<Pat>>, Option<usize>),
 585
 586     /// A path pattern for an unit struct/variant or a (maybe-associated) constant.
 587     Path(QPath),
 588
 589     /// A tuple pattern `(a, b)`.
 590     /// If the `..` pattern fragment is present, then `Option<usize>` denotes its position.
 591     /// 0 <= position <= subpats.len()
 592     Tuple(HirVec<P<Pat>>, Option<usize>),
 593     /// A `box` pattern
 594     Box(P<Pat>),
 595     /// A reference pattern, e.g. `&mut (a, b)`
 596     Ref(P<Pat>, Mutability),
 597     /// A literal
 598     Lit(P<Expr>),
 599     /// A range pattern, e.g. `1...2`
 600     Range(P<Expr>, P<Expr>),
 601     /// `[a, b, ..i, y, z]` is represented as:
 602     ///     `PatKind::Slice(box [a, b], Some(i), box [y, z])`
 603     Slice(HirVec<P<Pat>>, Option<P<Pat>>, HirVec<P<Pat>>),
 604 }
 605
 606 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
 607 pub enum Mutability {
 608     MutMutable,
 609     MutImmutable,
 610 }
 611
 612 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
 613 pub enum BinOp_ {
 614     /// The `+` operator (addition)
 615     BiAdd,
 616     /// The `-` operator (subtraction)
 617     BiSub,
 618     /// The `*` operator (multiplication)
 619     BiMul,
 620     /// The `/` operator (division)
 621     BiDiv,
 622     /// The `%` operator (modulus)
 623     BiRem,
 624     /// The `&&` operator (logical and)
 625     BiAnd,
 626     /// The `||` operator (logical or)
 627     BiOr,
 628     /// The `^` operator (bitwise xor)
 629     BiBitXor,
 630     /// The `&` operator (bitwise and)
 631     BiBitAnd,
 632     /// The `|` operator (bitwise or)
 633     BiBitOr,
 634     /// The `<<` operator (shift left)
 635     BiShl,
 636     /// The `>>` operator (shift right)
 637     BiShr,
 638     /// The `==` operator (equality)
 639     BiEq,
 640     /// The `<` operator (less than)
 641     BiLt,
 642     /// The `<=` operator (less than or equal to)
 643     BiLe,
 644     /// The `!=` operator (not equal to)
 645     BiNe,
 646     /// The `>=` operator (greater than or equal to)
 647     BiGe,
 648     /// The `>` operator (greater than)
 649     BiGt,
 650 }
 651
 652 impl BinOp_ {
 653     pub fn as_str(self) -> &'static str {
 654         match self {
 655             BiAdd => "+",
 656             BiSub => "-",
 657             BiMul => "*",
 658             BiDiv => "/",
 659             BiRem => "%",
 660             BiAnd => "&&",
 661             BiOr => "||",
 662             BiBitXor => "^",
 663             BiBitAnd => "&",
 664             BiBitOr => "|",
 665             BiShl => "<<",
 666             BiShr => ">>",
 667             BiEq => "==",
 668             BiLt => "<",
 669             BiLe => "<=",
 670             BiNe => "!=",
 671             BiGe => ">=",
 672             BiGt => ">",
 673         }
 674     }
 675
 676     pub fn is_lazy(self) -> bool {
 677         match self {
 678             BiAnd | BiOr => true,
 679             _ => false,
 680         }
 681     }
 682
 683     pub fn is_shift(self) -> bool {
 684         match self {
 685             BiShl | BiShr => true,
 686             _ => false,
 687         }
 688     }
 689
 690     pub fn is_comparison(self) -> bool {
 691         match self {
 692             BiEq | BiLt | BiLe | BiNe | BiGt | BiGe => true,
 693             BiAnd |
 694             BiOr |
 695             BiAdd |
 696             BiSub |
 697             BiMul |
 698             BiDiv |
 699             BiRem |
 700             BiBitXor |
 701             BiBitAnd |
 702             BiBitOr |
 703             BiShl |
 704             BiShr => false,
 705         }
 706     }
 707
 708     /// Returns `true` if the binary operator takes its arguments by value
 709     pub fn is_by_value(self) -> bool {
 710         !self.is_comparison()
 711     }
 712 }
 713
 714 pub type BinOp = Spanned<BinOp_>;
 715
 716 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
 717 pub enum UnOp {
 718     /// The `*` operator for dereferencing
 719     UnDeref,
 720     /// The `!` operator for logical inversion
 721     UnNot,
 722     /// The `-` operator for negation
 723     UnNeg,
 724 }
 725
 726 impl UnOp {
 727     pub fn as_str(self) -> &'static str {
 728         match self {
 729             UnDeref => "*",
 730             UnNot => "!",
 731             UnNeg => "-",
 732         }
 733     }
 734
 735     /// Returns `true` if the unary operator takes its argument by value
 736     pub fn is_by_value(self) -> bool {
 737         match self {
 738             UnNeg | UnNot => true,
 739             _ => false,
 740         }
 741     }
 742 }
 743
 744 /// A statement
 745 pub type Stmt = Spanned<Stmt_>;
 746
 747 impl fmt::Debug for Stmt_ {
 748     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 749         // Sadness.
 750         let spanned = codemap::dummy_spanned(self.clone());
 751         write!(f,
 752                "stmt({}: {})",
 753                spanned.node.id(),
 754                print::stmt_to_string(&spanned))
 755     }
 756 }
 757
 758 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash)]
 759 pub enum Stmt_ {
 760     /// Could be an item or a local (let) binding:
 761     StmtDecl(P<Decl>, NodeId),
 762
 763     /// Expr without trailing semi-colon (must have unit type):
 764     StmtExpr(P<Expr>, NodeId),
 765
 766     /// Expr with trailing semi-colon (may have any type):
 767     StmtSemi(P<Expr>, NodeId),
 768 }
 769
 770 impl Stmt_ {
 771     pub fn attrs(&self) -> &[Attribute] {
 772         match *self {
 773             StmtDecl(ref d, _) => d.node.attrs(),
 774             StmtExpr(ref e, _) |
 775             StmtSemi(ref e, _) => &e.attrs,
 776         }
 777     }
 778
 779     pub fn id(&self) -> NodeId {
 780         match *self {
 781             StmtDecl(_, id) => id,
 782             StmtExpr(_, id) => id,
 783             StmtSemi(_, id) => id,
 784         }
 785     }
 786 }
 787
 788 // FIXME (pending discussion of #1697, #2178...): local should really be
 789 // a refinement on pat.
 790 /// Local represents a `let` statement, e.g., `let <pat>:<ty> = <expr>;`
 791 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 792 pub struct Local {
 793     pub pat: P<Pat>,
 794     pub ty: Option<P<Ty>>,
 795     /// Initializer expression to set the value, if any
 796     pub init: Option<P<Expr>>,
 797     pub id: NodeId,
 798     pub span: Span,
 799     pub attrs: ThinVec<Attribute>,
 800 }
 801
 802 pub type Decl = Spanned<Decl_>;
 803
 804 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 805 pub enum Decl_ {
 806     /// A local (let) binding:
 807     DeclLocal(P<Local>),
 808     /// An item binding:
 809     DeclItem(ItemId),
 810 }
 811
 812 impl Decl_ {
 813     pub fn attrs(&self) -> &[Attribute] {
 814         match *self {
 815             DeclLocal(ref l) => &l.attrs,
 816             DeclItem(_) => &[]
 817         }
 818     }
 819 }
 820
 821 /// represents one arm of a 'match'
 822 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 823 pub struct Arm {
 824     pub attrs: HirVec<Attribute>,
 825     pub pats: HirVec<P<Pat>>,
 826     pub guard: Option<P<Expr>>,
 827     pub body: P<Expr>,
 828 }
 829
 830 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 831 pub struct Field {
 832     pub name: Spanned<Name>,
 833     pub expr: P<Expr>,
 834     pub span: Span,
 835     pub is_shorthand: bool,
 836 }
 837
 838 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
 839 pub enum BlockCheckMode {
 840     DefaultBlock,
 841     UnsafeBlock(UnsafeSource),
 842     PushUnsafeBlock(UnsafeSource),
 843     PopUnsafeBlock(UnsafeSource),
 844     // Within this block (but outside a PopUnstableBlock), we suspend checking of stability.
 845     PushUnstableBlock,
 846     PopUnstableBlock,
 847 }
 848
 849 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
 850 pub enum UnsafeSource {
 851     CompilerGenerated,
 852     UserProvided,
 853 }
 854
 855 /// An expression
 856 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash)]
 857 pub struct Expr {
 858     pub id: NodeId,
 859     pub span: Span,
 860     pub node: Expr_,
 861     pub attrs: ThinVec<Attribute>,
 862 }
 863
 864 impl fmt::Debug for Expr {
 865     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 866         write!(f, "expr({}: {})", self.id, print::expr_to_string(self))
 867     }
 868 }
 869
 870 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 871 pub enum Expr_ {
 872     /// A `box x` expression.
 873     ExprBox(P<Expr>),
 874     /// An array (`[a, b, c, d]`)
 875     ExprArray(HirVec<Expr>),
 876     /// A function call
 877     ///
 878     /// The first field resolves to the function itself (usually an `ExprPath`),
 879     /// and the second field is the list of arguments
 880     ExprCall(P<Expr>, HirVec<Expr>),
 881     /// A method call (`x.foo::<Bar, Baz>(a, b, c, d)`)
 882     ///
 883     /// The `Spanned<Name>` is the identifier for the method name.
 884     /// The vector of `Ty`s are the ascripted type parameters for the method
 885     /// (within the angle brackets).
 886     ///
 887     /// The first element of the vector of `Expr`s is the expression that
 888     /// evaluates to the object on which the method is being called on (the
 889     /// receiver), and the remaining elements are the rest of the arguments.
 890     ///
 891     /// Thus, `x.foo::<Bar, Baz>(a, b, c, d)` is represented as
 892     /// `ExprMethodCall(foo, [Bar, Baz], [x, a, b, c, d])`.
 893     ExprMethodCall(Spanned<Name>, HirVec<P<Ty>>, HirVec<Expr>),
 894     /// A tuple (`(a, b, c ,d)`)
 895     ExprTup(HirVec<Expr>),
 896     /// A binary operation (For example: `a + b`, `a * b`)
 897     ExprBinary(BinOp, P<Expr>, P<Expr>),
 898     /// A unary operation (For example: `!x`, `*x`)
 899     ExprUnary(UnOp, P<Expr>),
 900     /// A literal (For example: `1`, `"foo"`)
 901     ExprLit(P<Lit>),
 902     /// A cast (`foo as f64`)
 903     ExprCast(P<Expr>, P<Ty>),
 904     ExprType(P<Expr>, P<Ty>),
 905     /// An `if` block, with an optional else block
 906     ///
 907     /// `if expr { block } else { expr }`
 908     ExprIf(P<Expr>, P<Block>, Option<P<Expr>>),
 909     /// A while loop, with an optional label
 910     ///
 911     /// `'label: while expr { block }`
 912     ExprWhile(P<Expr>, P<Block>, Option<Spanned<Name>>),
 913     /// Conditionless loop (can be exited with break, continue, or return)
 914     ///
 915     /// `'label: loop { block }`
 916     ExprLoop(P<Block>, Option<Spanned<Name>>, LoopSource),
 917     /// A `match` block, with a source that indicates whether or not it is
 918     /// the result of a desugaring, and if so, which kind.
 919     ExprMatch(P<Expr>, HirVec<Arm>, MatchSource),
 920     /// A closure (for example, `move |a, b, c| {a + b + c}`).
 921     ///
 922     /// The final span is the span of the argument block `|...|`
 923     ExprClosure(CaptureClause, P<FnDecl>, P<Expr>, Span),
 924     /// A block (`{ ... }`)
 925     ExprBlock(P<Block>),
 926
 927     /// An assignment (`a = foo()`)
 928     ExprAssign(P<Expr>, P<Expr>),
 929     /// An assignment with an operator
 930     ///
 931     /// For example, `a += 1`.
 932     ExprAssignOp(BinOp, P<Expr>, P<Expr>),
 933     /// Access of a named struct field (`obj.foo`)
 934     ExprField(P<Expr>, Spanned<Name>),
 935     /// Access of an unnamed field of a struct or tuple-struct
 936     ///
 937     /// For example, `foo.0`.
 938     ExprTupField(P<Expr>, Spanned<usize>),
 939     /// An indexing operation (`foo[2]`)
 940     ExprIndex(P<Expr>, P<Expr>),
 941
 942     /// Path to a definition, possibly containing lifetime or type parameters.
 943     ExprPath(QPath),
 944
 945     /// A referencing operation (`&a` or `&mut a`)
 946     ExprAddrOf(Mutability, P<Expr>),
 947     /// A `break`, with an optional label to break
 948     ExprBreak(Option<Spanned<Name>>, Option<P<Expr>>),
 949     /// A `continue`, with an optional label
 950     ExprAgain(Option<Spanned<Name>>),
 951     /// A `return`, with an optional value to be returned
 952     ExprRet(Option<P<Expr>>),
 953
 954     /// Inline assembly (from `asm!`), with its outputs and inputs.
 955     ExprInlineAsm(P<InlineAsm>, HirVec<Expr>, HirVec<Expr>),
 956
 957     /// A struct or struct-like variant literal expression.
 958     ///
 959     /// For example, `Foo {x: 1, y: 2}`, or
 960     /// `Foo {x: 1, .. base}`, where `base` is the `Option<Expr>`.
 961     ExprStruct(QPath, HirVec<Field>, Option<P<Expr>>),
 962
 963     /// An array literal constructed from one repeated element.
 964     ///
 965     /// For example, `[1; 5]`. The first expression is the element
 966     /// to be repeated; the second is the number of times to repeat it.
 967     ExprRepeat(P<Expr>, P<Expr>),
 968 }
 969
 970 /// Optionally `Self`-qualified value/type path or associated extension.
 971 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 972 pub enum QPath {
 973     /// Path to a definition, optionally "fully-qualified" with a `Self`
 974     /// type, if the path points to an associated item in a trait.
 975     ///
 976     /// E.g. an unqualified path like `Clone::clone` has `None` for `Self`,
 977     /// while `<Vec<T> as Clone>::clone` has `Some(Vec<T>)` for `Self`,
 978     /// even though they both have the same two-segment `Clone::clone` `Path`.
 979     Resolved(Option<P<Ty>>, P<Path>),
 980
 981     /// Type-related paths, e.g. `<T>::default` or `<T>::Output`.
 982     /// Will be resolved by type-checking to an associated item.
 983     ///
 984     /// UFCS source paths can desugar into this, with `Vec::new` turning into
 985     /// `<Vec>::new`, and `T::X::Y::method` into `<<<T>::X>::Y>::method`,
 986     /// the `X` and `Y` nodes being each a `TyPath(QPath::TypeRelative(..))`.
 987     TypeRelative(P<Ty>, P<PathSegment>)
 988 }
 989
 990 impl fmt::Display for QPath {
 991     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 992         write!(f, "{}", print::qpath_to_string(self))
 993     }
 994 }
 995
 996 /// Hints at the original code for a `match _ { .. }`
 997 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
 998 pub enum MatchSource {
 999     /// A `match _ { .. }`
1000     Normal,
1001     /// An `if let _ = _ { .. }` (optionally with `else { .. }`)
1002     IfLetDesugar {
1003         contains_else_clause: bool,
1004     },
1005     /// A `while let _ = _ { .. }` (which was desugared to a
1006     /// `loop { match _ { .. } }`)
1007     WhileLetDesugar,
1008     /// A desugared `for _ in _ { .. }` loop
1009     ForLoopDesugar,
1010     /// A desugared `?` operator
1011     TryDesugar,
1012 }
1013
1014 /// The loop type that yielded an ExprLoop
1015 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
1016 pub enum LoopSource {
1017     /// A `loop { .. }` loop
1018     Loop,
1019     /// A `while let _ = _ { .. }` loop
1020     WhileLet,
1021     /// A `for _ in _ { .. }` loop
1022     ForLoop,
1023 }
1024
1025
1026 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
1027 pub enum CaptureClause {
1028     CaptureByValue,
1029     CaptureByRef,
1030 }
1031
1032 // NB: If you change this, you'll probably want to change the corresponding
1033 // type structure in middle/ty.rs as well.
1034 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1035 pub struct MutTy {
1036     pub ty: P<Ty>,
1037     pub mutbl: Mutability,
1038 }
1039
1040 /// Represents a method's signature in a trait declaration or implementation.
1041 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1042 pub struct MethodSig {
1043     pub unsafety: Unsafety,
1044     pub constness: Constness,
1045     pub abi: Abi,
1046     pub decl: P<FnDecl>,
1047     pub generics: Generics,
1048 }
1049
1050 /// Represents an item declaration within a trait declaration,
1051 /// possibly including a default implementation. A trait item is
1052 /// either required (meaning it doesn't have an implementation, just a
1053 /// signature) or provided (meaning it has a default implementation).
1054 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1055 pub struct TraitItem {
1056     pub id: NodeId,
1057     pub name: Name,
1058     pub attrs: HirVec<Attribute>,
1059     pub node: TraitItem_,
1060     pub span: Span,
1061 }
1062
1063 /// Represents a trait method or associated constant or type
1064 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1065 pub enum TraitItem_ {
1066     /// An associated constant with an optional value (otherwise `impl`s
1067     /// must contain a value)
1068     ConstTraitItem(P<Ty>, Option<P<Expr>>),
1069     /// A method with an optional body
1070     MethodTraitItem(MethodSig, Option<P<Expr>>),
1071     /// An associated type with (possibly empty) bounds and optional concrete
1072     /// type
1073     TypeTraitItem(TyParamBounds, Option<P<Ty>>),
1074 }
1075
1076 // The bodies for items are stored "out of line", in a separate
1077 // hashmap in the `Crate`. Here we just record the node-id of the item
1078 // so it can fetched later.
1079 #[derive(Copy, Clone, PartialEq, Eq, PartialOrd, Ord, RustcEncodable, RustcDecodable, Hash, Debug)]
1080 pub struct ImplItemId {
1081     pub node_id: NodeId,
1082 }
1083
1084 /// Represents anything within an `impl` block
1085 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1086 pub struct ImplItem {
1087     pub id: NodeId,
1088     pub name: Name,
1089     pub vis: Visibility,
1090     pub defaultness: Defaultness,
1091     pub attrs: HirVec<Attribute>,
1092     pub node: ImplItemKind,
1093     pub span: Span,
1094 }
1095
1096 /// Represents different contents within `impl`s
1097 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1098 pub enum ImplItemKind {
1099     /// An associated constant of the given type, set to the constant result
1100     /// of the expression
1101     Const(P<Ty>, P<Expr>),
1102     /// A method implementation with the given signature and body
1103     Method(MethodSig, P<Expr>),
1104     /// An associated type
1105     Type(P<Ty>),
1106 }
1107
1108 // Bind a type to an associated type: `A=Foo`.
1109 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1110 pub struct TypeBinding {
1111     pub id: NodeId,
1112     pub name: Name,
1113     pub ty: P<Ty>,
1114     pub span: Span,
1115 }
1116
1117
1118 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash)]
1119 pub struct Ty {
1120     pub id: NodeId,
1121     pub node: Ty_,
1122     pub span: Span,
1123 }
1124
1125 impl fmt::Debug for Ty {
1126     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1127         write!(f, "type({})", print::ty_to_string(self))
1128     }
1129 }
1130
1131 /// Not represented directly in the AST, referred to by name through a ty_path.
1132 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
1133 pub enum PrimTy {
1134     TyInt(IntTy),
1135     TyUint(UintTy),
1136     TyFloat(FloatTy),
1137     TyStr,
1138     TyBool,
1139     TyChar,
1140 }
1141
1142 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1143 pub struct BareFnTy {
1144     pub unsafety: Unsafety,
1145     pub abi: Abi,
1146     pub lifetimes: HirVec<LifetimeDef>,
1147     pub decl: P<FnDecl>,
1148 }
1149
1150 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1151 /// The different kinds of types recognized by the compiler
1152 pub enum Ty_ {
1153     /// A variable length slice (`[T]`)
1154     TySlice(P<Ty>),
1155     /// A fixed length array (`[T; n]`)
1156     TyArray(P<Ty>, P<Expr>),
1157     /// A raw pointer (`*const T` or `*mut T`)
1158     TyPtr(MutTy),
1159     /// A reference (`&'a T` or `&'a mut T`)
1160     TyRptr(Option<Lifetime>, MutTy),
1161     /// A bare function (e.g. `fn(usize) -> bool`)
1162     TyBareFn(P<BareFnTy>),
1163     /// The never type (`!`)
1164     TyNever,
1165     /// A tuple (`(A, B, C, D,...)`)
1166     TyTup(HirVec<P<Ty>>),
1167     /// A path to a type definition (`module::module::...::Type`), or an
1168     /// associated type, e.g. `<Vec<T> as Trait>::Type` or `<T>::Target`.
1169     ///
1170     /// Type parameters may be stored in each `PathSegment`.
1171     TyPath(QPath),
1172
1173     /// Something like `A+B`. Note that `B` must always be a path.
1174     TyObjectSum(P<Ty>, TyParamBounds),
1175     /// A type like `for<'a> Foo<&'a Bar>`
1176     TyPolyTraitRef(TyParamBounds),
1177     /// An `impl TraitA+TraitB` type.
1178     TyImplTrait(TyParamBounds),
1179     /// Unused for now
1180     TyTypeof(P<Expr>),
1181     /// TyInfer means the type should be inferred instead of it having been
1182     /// specified. This can appear anywhere in a type.
1183     TyInfer,
1184 }
1185
1186 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1187 pub struct InlineAsmOutput {
1188     pub constraint: Symbol,
1189     pub is_rw: bool,
1190     pub is_indirect: bool,
1191 }
1192
1193 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1194 pub struct InlineAsm {
1195     pub asm: Symbol,
1196     pub asm_str_style: StrStyle,
1197     pub outputs: HirVec<InlineAsmOutput>,
1198     pub inputs: HirVec<Symbol>,
1199     pub clobbers: HirVec<Symbol>,
1200     pub volatile: bool,
1201     pub alignstack: bool,
1202     pub dialect: AsmDialect,
1203     pub expn_id: ExpnId,
1204 }
1205
1206 /// represents an argument in a function header
1207 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1208 pub struct Arg {
1209     pub ty: P<Ty>,
1210     pub pat: P<Pat>,
1211     pub id: NodeId,
1212 }
1213
1214 /// Alternative representation for `Arg`s describing `self` parameter of methods.
1215 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1216 pub enum SelfKind {
1217     /// `self`, `mut self`
1218     Value(Mutability),
1219     /// `&'lt self`, `&'lt mut self`
1220     Region(Option<Lifetime>, Mutability),
1221     /// `self: TYPE`, `mut self: TYPE`
1222     Explicit(P<Ty>, Mutability),
1223 }
1224
1225 pub type ExplicitSelf = Spanned<SelfKind>;
1226
1227 impl Arg {
1228     pub fn to_self(&self) -> Option<ExplicitSelf> {
1229         if let PatKind::Binding(BindByValue(mutbl), name, _) = self.pat.node {
1230             if name.node == keywords::SelfValue.name() {
1231                 return match self.ty.node {
1232                     TyInfer => Some(respan(self.pat.span, SelfKind::Value(mutbl))),
1233                     TyRptr(lt, MutTy{ref ty, mutbl}) if ty.node == TyInfer => {
1234                         Some(respan(self.pat.span, SelfKind::Region(lt, mutbl)))
1235                     }
1236                     _ => Some(respan(mk_sp(self.pat.span.lo, self.ty.span.hi),
1237                                      SelfKind::Explicit(self.ty.clone(), mutbl)))
1238                 }
1239             }
1240         }
1241         None
1242     }
1243
1244     pub fn is_self(&self) -> bool {
1245         if let PatKind::Binding(_, name, _) = self.pat.node {
1246             name.node == keywords::SelfValue.name()
1247         } else {
1248             false
1249         }
1250     }
1251 }
1252
1253 /// Represents the header (not the body) of a function declaration
1254 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1255 pub struct FnDecl {
1256     pub inputs: HirVec<Arg>,
1257     pub output: FunctionRetTy,
1258     pub variadic: bool,
1259 }
1260
1261 impl FnDecl {
1262     pub fn get_self(&self) -> Option<ExplicitSelf> {
1263         self.inputs.get(0).and_then(Arg::to_self)
1264     }
1265     pub fn has_self(&self) -> bool {
1266         self.inputs.get(0).map(Arg::is_self).unwrap_or(false)
1267     }
1268 }
1269
1270 #[derive(Copy, Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1271 pub enum Unsafety {
1272     Unsafe,
1273     Normal,
1274 }
1275
1276 #[derive(Copy, Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1277 pub enum Constness {
1278     Const,
1279     NotConst,
1280 }
1281
1282 #[derive(Copy, Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1283 pub enum Defaultness {
1284     Default { has_value: bool },
1285     Final,
1286 }
1287
1288 impl Defaultness {
1289     pub fn has_value(&self) -> bool {
1290         match *self {
1291             Defaultness::Default { has_value, .. } => has_value,
1292             Defaultness::Final => true,
1293         }
1294     }
1295
1296     pub fn is_final(&self) -> bool {
1297         *self == Defaultness::Final
1298     }
1299
1300     pub fn is_default(&self) -> bool {
1301         match *self {
1302             Defaultness::Default { .. } => true,
1303             _ => false,
1304         }
1305     }
1306 }
1307
1308 impl fmt::Display for Unsafety {
1309     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1310         fmt::Display::fmt(match *self {
1311                               Unsafety::Normal => "normal",
1312                               Unsafety::Unsafe => "unsafe",
1313                           },
1314                           f)
1315     }
1316 }
1317
1318 #[derive(Copy, Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash)]
1319 pub enum ImplPolarity {
1320     /// `impl Trait for Type`
1321     Positive,
1322     /// `impl !Trait for Type`
1323     Negative,
1324 }
1325
1326 impl fmt::Debug for ImplPolarity {
1327     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1328         match *self {
1329             ImplPolarity::Positive => "positive".fmt(f),
1330             ImplPolarity::Negative => "negative".fmt(f),
1331         }
1332     }
1333 }
1334
1335
1336 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1337 pub enum FunctionRetTy {
1338     /// Return type is not specified.
1339     ///
1340     /// Functions default to `()` and
1341     /// closures default to inference. Span points to where return
1342     /// type would be inserted.
1343     DefaultReturn(Span),
1344     /// Everything else
1345     Return(P<Ty>),
1346 }
1347
1348 impl FunctionRetTy {
1349     pub fn span(&self) -> Span {
1350         match *self {
1351             DefaultReturn(span) => span,
1352             Return(ref ty) => ty.span,
1353         }
1354     }
1355 }
1356
1357 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1358 pub struct Mod {
1359     /// A span from the first token past `{` to the last token until `}`.
1360     /// For `mod foo;`, the inner span ranges from the first token
1361     /// to the last token in the external file.
1362     pub inner: Span,
1363     pub item_ids: HirVec<ItemId>,
1364 }
1365
1366 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1367 pub struct ForeignMod {
1368     pub abi: Abi,
1369     pub items: HirVec<ForeignItem>,
1370 }
1371
1372 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1373 pub struct EnumDef {
1374     pub variants: HirVec<Variant>,
1375 }
1376
1377 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1378 pub struct Variant_ {
1379     pub name: Name,
1380     pub attrs: HirVec<Attribute>,
1381     pub data: VariantData,
1382     /// Explicit discriminant, eg `Foo = 1`
1383     pub disr_expr: Option<P<Expr>>,
1384 }
1385
1386 pub type Variant = Spanned<Variant_>;
1387
1388 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
1389 pub struct PathListItem_ {
1390     pub name: Name,
1391     /// renamed in list, eg `use foo::{bar as baz};`
1392     pub rename: Option<Name>,
1393     pub id: NodeId,
1394 }
1395
1396 pub type PathListItem = Spanned<PathListItem_>;
1397
1398 pub type ViewPath = Spanned<ViewPath_>;
1399
1400 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1401 pub enum ViewPath_ {
1402     /// `foo::bar::baz as quux`
1403     ///
1404     /// or just
1405     ///
1406     /// `foo::bar::baz` (with `as baz` implicitly on the right)
1407     ViewPathSimple(Name, Path),
1408
1409     /// `foo::bar::*`
1410     ViewPathGlob(Path),
1411
1412     /// `foo::bar::{a,b,c}`
1413     ViewPathList(Path, HirVec<PathListItem>),
1414 }
1415
1416 /// TraitRef's appear in impls.
1417 ///
1418 /// resolve maps each TraitRef's ref_id to its defining trait; that's all
1419 /// that the ref_id is for. Note that ref_id's value is not the NodeId of the
1420 /// trait being referred to but just a unique NodeId that serves as a key
1421 /// within the DefMap.
1422 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1423 pub struct TraitRef {
1424     pub path: Path,
1425     pub ref_id: NodeId,
1426 }
1427
1428 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1429 pub struct PolyTraitRef {
1430     /// The `'a` in `<'a> Foo<&'a T>`
1431     pub bound_lifetimes: HirVec<LifetimeDef>,
1432
1433     /// The `Foo<&'a T>` in `<'a> Foo<&'a T>`
1434     pub trait_ref: TraitRef,
1435
1436     pub span: Span,
1437 }
1438
1439 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1440 pub enum Visibility {
1441     Public,
1442     Crate,
1443     Restricted { path: P<Path>, id: NodeId },
1444     Inherited,
1445 }
1446
1447 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1448 pub struct StructField {
1449     pub span: Span,
1450     pub name: Name,
1451     pub vis: Visibility,
1452     pub id: NodeId,
1453     pub ty: P<Ty>,
1454     pub attrs: HirVec<Attribute>,
1455 }
1456
1457 impl StructField {
1458     // Still necessary in couple of places
1459     pub fn is_positional(&self) -> bool {
1460         let first = self.name.as_str().as_bytes()[0];
1461         first >= b'0' && first <= b'9'
1462     }
1463 }
1464
1465 /// Fields and Ids of enum variants and structs
1466 ///
1467 /// For enum variants: `NodeId` represents both an Id of the variant itself (relevant for all
1468 /// variant kinds) and an Id of the variant's constructor (not relevant for `Struct`-variants).
1469 /// One shared Id can be successfully used for these two purposes.
1470 /// Id of the whole enum lives in `Item`.
1471 ///
1472 /// For structs: `NodeId` represents an Id of the structure's constructor, so it is not actually
1473 /// used for `Struct`-structs (but still presents). Structures don't have an analogue of "Id of
1474 /// the variant itself" from enum variants.
1475 /// Id of the whole struct lives in `Item`.
1476 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1477 pub enum VariantData {
1478     Struct(HirVec<StructField>, NodeId),
1479     Tuple(HirVec<StructField>, NodeId),
1480     Unit(NodeId),
1481 }
1482
1483 impl VariantData {
1484     pub fn fields(&self) -> &[StructField] {
1485         match *self {
1486             VariantData::Struct(ref fields, _) | VariantData::Tuple(ref fields, _) => fields,
1487             _ => &[],
1488         }
1489     }
1490     pub fn id(&self) -> NodeId {
1491         match *self {
1492             VariantData::Struct(_, id) | VariantData::Tuple(_, id) | VariantData::Unit(id) => id,
1493         }
1494     }
1495     pub fn is_struct(&self) -> bool {
1496         if let VariantData::Struct(..) = *self {
1497             true
1498         } else {
1499             false
1500         }
1501     }
1502     pub fn is_tuple(&self) -> bool {
1503         if let VariantData::Tuple(..) = *self {
1504             true
1505         } else {
1506             false
1507         }
1508     }
1509     pub fn is_unit(&self) -> bool {
1510         if let VariantData::Unit(..) = *self {
1511             true
1512         } else {
1513             false
1514         }
1515     }
1516 }
1517
1518 // The bodies for items are stored "out of line", in a separate
1519 // hashmap in the `Crate`. Here we just record the node-id of the item
1520 // so it can fetched later.
1521 #[derive(Copy, Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1522 pub struct ItemId {
1523     pub id: NodeId,
1524 }
1525
1526 //  FIXME (#3300): Should allow items to be anonymous. Right now
1527 //  we just use dummy names for anon items.
1528 /// An item
1529 ///
1530 /// The name might be a dummy name in case of anonymous items
1531 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1532 pub struct Item {
1533     pub name: Name,
1534     pub attrs: HirVec<Attribute>,
1535     pub id: NodeId,
1536     pub node: Item_,
1537     pub vis: Visibility,
1538     pub span: Span,
1539 }
1540
1541 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1542 pub enum Item_ {
1543     /// An`extern crate` item, with optional original crate name,
1544     ///
1545     /// e.g. `extern crate foo` or `extern crate foo_bar as foo`
1546     ItemExternCrate(Option<Name>),
1547     /// A `use` or `pub use` item
1548     ItemUse(P<ViewPath>),
1549
1550     /// A `static` item
1551     ItemStatic(P<Ty>, Mutability, P<Expr>),
1552     /// A `const` item
1553     ItemConst(P<Ty>, P<Expr>),
1554     /// A function declaration
1555     ItemFn(P<FnDecl>, Unsafety, Constness, Abi, Generics, P<Expr>),
1556     /// A module
1557     ItemMod(Mod),
1558     /// An external module
1559     ItemForeignMod(ForeignMod),
1560     /// A type alias, e.g. `type Foo = Bar<u8>`
1561     ItemTy(P<Ty>, Generics),
1562     /// An enum definition, e.g. `enum Foo<A, B> {C<A>, D<B>}`
1563     ItemEnum(EnumDef, Generics),
1564     /// A struct definition, e.g. `struct Foo<A> {x: A}`
1565     ItemStruct(VariantData, Generics),
1566     /// A union definition, e.g. `union Foo<A, B> {x: A, y: B}`
1567     ItemUnion(VariantData, Generics),
1568     /// Represents a Trait Declaration
1569     ItemTrait(Unsafety, Generics, TyParamBounds, HirVec<TraitItem>),
1570
1571     // Default trait implementations
1572     ///
1573     /// `impl Trait for .. {}`
1574     ItemDefaultImpl(Unsafety, TraitRef),
1575     /// An implementation, eg `impl<A> Trait for Foo { .. }`
1576     ItemImpl(Unsafety,
1577              ImplPolarity,
1578              Generics,
1579              Option<TraitRef>, // (optional) trait this impl implements
1580              P<Ty>, // self
1581              HirVec<ImplItemRef>),
1582 }
1583
1584 impl Item_ {
1585     pub fn descriptive_variant(&self) -> &str {
1586         match *self {
1587             ItemExternCrate(..) => "extern crate",
1588             ItemUse(..) => "use",
1589             ItemStatic(..) => "static item",
1590             ItemConst(..) => "constant item",
1591             ItemFn(..) => "function",
1592             ItemMod(..) => "module",
1593             ItemForeignMod(..) => "foreign module",
1594             ItemTy(..) => "type alias",
1595             ItemEnum(..) => "enum",
1596             ItemStruct(..) => "struct",
1597             ItemUnion(..) => "union",
1598             ItemTrait(..) => "trait",
1599             ItemImpl(..) |
1600             ItemDefaultImpl(..) => "item",
1601         }
1602     }
1603 }
1604
1605 /// A reference from an impl to one of its associated items. This
1606 /// contains the item's id, naturally, but also the item's name and
1607 /// some other high-level details (like whether it is an associated
1608 /// type or method, and whether it is public). This allows other
1609 /// passes to find the impl they want without loading the id (which
1610 /// means fewer edges in the incremental compilation graph).
1611 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1612 pub struct ImplItemRef {
1613     pub id: ImplItemId,
1614     pub name: Name,
1615     pub kind: AssociatedItemKind,
1616     pub span: Span,
1617     pub vis: Visibility,
1618     pub defaultness: Defaultness,
1619 }
1620
1621 #[derive(Copy, Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1622 pub enum AssociatedItemKind {
1623     Const,
1624     Method { has_self: bool },
1625     Type,
1626 }
1627
1628 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1629 pub struct ForeignItem {
1630     pub name: Name,
1631     pub attrs: HirVec<Attribute>,
1632     pub node: ForeignItem_,
1633     pub id: NodeId,
1634     pub span: Span,
1635     pub vis: Visibility,
1636 }
1637
1638 /// An item within an `extern` block
1639 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1640 pub enum ForeignItem_ {
1641     /// A foreign function
1642     ForeignItemFn(P<FnDecl>, Generics),
1643     /// A foreign static item (`static ext: u8`), with optional mutability
1644     /// (the boolean is true when mutable)
1645     ForeignItemStatic(P<Ty>, bool),
1646 }
1647
1648 impl ForeignItem_ {
1649     pub fn descriptive_variant(&self) -> &str {
1650         match *self {
1651             ForeignItemFn(..) => "foreign function",
1652             ForeignItemStatic(..) => "foreign static item",
1653         }
1654     }
1655 }
1656
1657 /// A free variable referred to in a function.
1658 #[derive(Copy, Clone, RustcEncodable, RustcDecodable)]
1659 pub struct Freevar {
1660     /// The variable being accessed free.
1661     pub def: Def,
1662
1663     // First span where it is accessed (there can be multiple).
1664     pub span: Span
1665 }
1666
1667 pub type FreevarMap = NodeMap<Vec<Freevar>>;
1668
1669 pub type CaptureModeMap = NodeMap<CaptureClause>;
1670
1671 #[derive(Clone, Debug)]
1672 pub struct TraitCandidate {
1673     pub def_id: DefId,
1674     pub import_id: Option<NodeId>,
1675 }
1676
1677 // Trait method resolution
1678 pub type TraitMap = NodeMap<Vec<TraitCandidate>>;
1679
1680 // Map from the NodeId of a glob import to a list of items which are actually
1681 // imported.
1682 pub type GlobMap = NodeMap<FxHashSet<Name>>;