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