src/librustc/hir/mod.rs

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