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