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