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