src/libsyntax/ast.rs

   1 // Copyright 2012-2014 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 abstract syntax tree.
  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::ExplicitSelf_::*;
  19 pub use self::Expr_::*;
  20 pub use self::FloatTy::*;
  21 pub use self::FunctionRetTy::*;
  22 pub use self::ForeignItem_::*;
  23 pub use self::ImplItem_::*;
  24 pub use self::IntTy::*;
  25 pub use self::Item_::*;
  26 pub use self::KleeneOp::*;
  27 pub use self::Lit_::*;
  28 pub use self::LitIntType::*;
  29 pub use self::MacStmtStyle::*;
  30 pub use self::MetaItem_::*;
  31 pub use self::Mutability::*;
  32 pub use self::Pat_::*;
  33 pub use self::PathListItem_::*;
  34 pub use self::PrimTy::*;
  35 pub use self::Sign::*;
  36 pub use self::Stmt_::*;
  37 pub use self::StrStyle::*;
  38 pub use self::StructFieldKind::*;
  39 pub use self::TraitItem_::*;
  40 pub use self::Ty_::*;
  41 pub use self::TyParamBound::*;
  42 pub use self::UintTy::*;
  43 pub use self::UnOp::*;
  44 pub use self::UnsafeSource::*;
  45 pub use self::ViewPath_::*;
  46 pub use self::Visibility::*;
  47 pub use self::PathParameters::*;
  48
  49 use codemap::{Span, Spanned, DUMMY_SP, ExpnId};
  50 use abi::Abi;
  51 use ast_util;
  52 use ext::base;
  53 use ext::tt::macro_parser;
  54 use owned_slice::OwnedSlice;
  55 use parse::token::{InternedString, str_to_ident};
  56 use parse::token;
  57 use parse::lexer;
  58 use parse::lexer::comments::{doc_comment_style, strip_doc_comment_decoration};
  59 use print::pprust;
  60 use ptr::P;
  61
  62 use std::fmt;
  63 use std::rc::Rc;
  64 use std::borrow::Cow;
  65 use std::hash::{Hash, Hasher};
  66 use serialize::{Encodable, Decodable, Encoder, Decoder};
  67
  68 /// A name is a part of an identifier, representing a string or gensym. It's
  69 /// the result of interning.
  70 #[derive(Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
  71 pub struct Name(pub u32);
  72
  73 /// A SyntaxContext represents a chain of macro-expandings
  74 /// and renamings. Each macro expansion corresponds to
  75 /// a fresh u32. This u32 is a reference to a table stored
  76 // in thread-local storage.
  77 // The special value EMPTY_CTXT is used to indicate an empty
  78 // syntax context.
  79 #[derive(Clone, Copy, PartialEq, Eq, Hash, Debug, RustcEncodable, RustcDecodable)]
  80 pub struct SyntaxContext(pub u32);
  81
  82 /// An identifier contains a Name (index into the interner
  83 /// table) and a SyntaxContext to track renaming and
  84 /// macro expansion per Flatt et al., "Macros That Work Together"
  85 #[derive(Clone, Copy, Eq)]
  86 pub struct Ident {
  87     pub name: Name,
  88     pub ctxt: SyntaxContext
  89 }
  90
  91 impl Name {
  92     pub fn as_str(self) -> token::InternedString {
  93         token::InternedString::new_from_name(self)
  94     }
  95 }
  96
  97 impl fmt::Debug for Name {
  98     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
  99         write!(f, "{}({})", self, self.0)
 100     }
 101 }
 102
 103 impl fmt::Display for Name {
 104     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 105         fmt::Display::fmt(&self.as_str(), f)
 106     }
 107 }
 108
 109 impl Encodable for Name {
 110     fn encode<S: Encoder>(&self, s: &mut S) -> Result<(), S::Error> {
 111         s.emit_str(&self.as_str())
 112     }
 113 }
 114
 115 impl Decodable for Name {
 116     fn decode<D: Decoder>(d: &mut D) -> Result<Name, D::Error> {
 117         Ok(token::intern(&try!(d.read_str())[..]))
 118     }
 119 }
 120
 121 pub const EMPTY_CTXT : SyntaxContext = SyntaxContext(0);
 122
 123 impl Ident {
 124     pub fn new(name: Name, ctxt: SyntaxContext) -> Ident {
 125         Ident {name: name, ctxt: ctxt}
 126     }
 127     pub fn with_empty_ctxt(name: Name) -> Ident {
 128         Ident {name: name, ctxt: EMPTY_CTXT}
 129     }
 130 }
 131
 132 impl PartialEq for Ident {
 133     fn eq(&self, other: &Ident) -> bool {
 134         if self.ctxt != other.ctxt {
 135             // There's no one true way to compare Idents. They can be compared
 136             // non-hygienically `id1.name == id2.name`, hygienically
 137             // `mtwt::resolve(id1) == mtwt::resolve(id2)`, or even member-wise
 138             // `(id1.name, id1.ctxt) == (id2.name, id2.ctxt)` depending on the situation.
 139             // Ideally, PartialEq should not be implemented for Ident at all, but that
 140             // would be too impractical, because many larger structures (Token, in particular)
 141             // including Idents as their parts derive PartialEq and use it for non-hygienic
 142             // comparisons. That's why PartialEq is implemented and defaults to non-hygienic
 143             // comparison. Hash is implemented too and is consistent with PartialEq, i.e. only
 144             // the name of Ident is hashed. Still try to avoid comparing idents in your code
 145             // (especially as keys in hash maps), use one of the three methods listed above
 146             // explicitly.
 147             //
 148             // If you see this panic, then some idents from different contexts were compared
 149             // non-hygienically. It's likely a bug. Use one of the three comparison methods
 150             // listed above explicitly.
 151
 152             panic!("idents with different contexts are compared with operator `==`: \
 153                 {:?}, {:?}.", self, other);
 154         }
 155
 156         self.name == other.name
 157     }
 158 }
 159
 160 impl Hash for Ident {
 161     fn hash<H: Hasher>(&self, state: &mut H) {
 162         self.name.hash(state)
 163     }
 164 }
 165
 166 impl fmt::Debug for Ident {
 167     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 168         write!(f, "{}#{}", self.name, self.ctxt.0)
 169     }
 170 }
 171
 172 impl fmt::Display for Ident {
 173     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 174         fmt::Display::fmt(&self.name, f)
 175     }
 176 }
 177
 178 impl Encodable for Ident {
 179     fn encode<S: Encoder>(&self, s: &mut S) -> Result<(), S::Error> {
 180         self.name.encode(s)
 181     }
 182 }
 183
 184 impl Decodable for Ident {
 185     fn decode<D: Decoder>(d: &mut D) -> Result<Ident, D::Error> {
 186         Ok(Ident::with_empty_ctxt(try!(Name::decode(d))))
 187     }
 188 }
 189
 190 /// A mark represents a unique id associated with a macro expansion
 191 pub type Mrk = u32;
 192
 193 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Copy)]
 194 pub struct Lifetime {
 195     pub id: NodeId,
 196     pub span: Span,
 197     pub name: Name
 198 }
 199
 200 impl fmt::Debug for Lifetime {
 201     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 202         write!(f, "lifetime({}: {})", self.id, pprust::lifetime_to_string(self))
 203     }
 204 }
 205
 206 /// A lifetime definition, eg `'a: 'b+'c+'d`
 207 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 208 pub struct LifetimeDef {
 209     pub lifetime: Lifetime,
 210     pub bounds: Vec<Lifetime>
 211 }
 212
 213 /// A "Path" is essentially Rust's notion of a name; for instance:
 214 /// std::cmp::PartialEq  .  It's represented as a sequence of identifiers,
 215 /// along with a bunch of supporting information.
 216 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash)]
 217 pub struct Path {
 218     pub span: Span,
 219     /// A `::foo` path, is relative to the crate root rather than current
 220     /// module (like paths in an import).
 221     pub global: bool,
 222     /// The segments in the path: the things separated by `::`.
 223     pub segments: Vec<PathSegment>,
 224 }
 225
 226 impl fmt::Debug for Path {
 227     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 228         write!(f, "path({})", pprust::path_to_string(self))
 229     }
 230 }
 231
 232 impl fmt::Display for Path {
 233     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 234         write!(f, "{}", pprust::path_to_string(self))
 235     }
 236 }
 237
 238 /// A segment of a path: an identifier, an optional lifetime, and a set of
 239 /// types.
 240 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 241 pub struct PathSegment {
 242     /// The identifier portion of this path segment.
 243     pub identifier: Ident,
 244
 245     /// Type/lifetime parameters attached to this path. They come in
 246     /// two flavors: `Path<A,B,C>` and `Path(A,B) -> C`. Note that
 247     /// this is more than just simple syntactic sugar; the use of
 248     /// parens affects the region binding rules, so we preserve the
 249     /// distinction.
 250     pub parameters: PathParameters,
 251 }
 252
 253 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 254 pub enum PathParameters {
 255     /// The `<'a, A,B,C>` in `foo::bar::baz::<'a, A,B,C>`
 256     AngleBracketedParameters(AngleBracketedParameterData),
 257     /// The `(A,B)` and `C` in `Foo(A,B) -> C`
 258     ParenthesizedParameters(ParenthesizedParameterData),
 259 }
 260
 261 impl PathParameters {
 262     pub fn none() -> PathParameters {
 263         AngleBracketedParameters(AngleBracketedParameterData {
 264             lifetimes: Vec::new(),
 265             types: OwnedSlice::empty(),
 266             bindings: OwnedSlice::empty(),
 267         })
 268     }
 269
 270     pub fn is_empty(&self) -> bool {
 271         match *self {
 272             AngleBracketedParameters(ref data) => data.is_empty(),
 273
 274             // Even if the user supplied no types, something like
 275             // `X()` is equivalent to `X<(),()>`.
 276             ParenthesizedParameters(..) => false,
 277         }
 278     }
 279
 280     pub fn has_lifetimes(&self) -> bool {
 281         match *self {
 282             AngleBracketedParameters(ref data) => !data.lifetimes.is_empty(),
 283             ParenthesizedParameters(_) => false,
 284         }
 285     }
 286
 287     pub fn has_types(&self) -> bool {
 288         match *self {
 289             AngleBracketedParameters(ref data) => !data.types.is_empty(),
 290             ParenthesizedParameters(..) => true,
 291         }
 292     }
 293
 294     /// Returns the types that the user wrote. Note that these do not necessarily map to the type
 295     /// parameters in the parenthesized case.
 296     pub fn types(&self) -> Vec<&P<Ty>> {
 297         match *self {
 298             AngleBracketedParameters(ref data) => {
 299                 data.types.iter().collect()
 300             }
 301             ParenthesizedParameters(ref data) => {
 302                 data.inputs.iter()
 303                     .chain(data.output.iter())
 304                     .collect()
 305             }
 306         }
 307     }
 308
 309     pub fn lifetimes(&self) -> Vec<&Lifetime> {
 310         match *self {
 311             AngleBracketedParameters(ref data) => {
 312                 data.lifetimes.iter().collect()
 313             }
 314             ParenthesizedParameters(_) => {
 315                 Vec::new()
 316             }
 317         }
 318     }
 319
 320     pub fn bindings(&self) -> Vec<&P<TypeBinding>> {
 321         match *self {
 322             AngleBracketedParameters(ref data) => {
 323                 data.bindings.iter().collect()
 324             }
 325             ParenthesizedParameters(_) => {
 326                 Vec::new()
 327             }
 328         }
 329     }
 330 }
 331
 332 /// A path like `Foo<'a, T>`
 333 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 334 pub struct AngleBracketedParameterData {
 335     /// The lifetime parameters for this path segment.
 336     pub lifetimes: Vec<Lifetime>,
 337     /// The type parameters for this path segment, if present.
 338     pub types: OwnedSlice<P<Ty>>,
 339     /// Bindings (equality constraints) on associated types, if present.
 340     /// E.g., `Foo<A=Bar>`.
 341     pub bindings: OwnedSlice<P<TypeBinding>>,
 342 }
 343
 344 impl AngleBracketedParameterData {
 345     fn is_empty(&self) -> bool {
 346         self.lifetimes.is_empty() && self.types.is_empty() && self.bindings.is_empty()
 347     }
 348 }
 349
 350 /// A path like `Foo(A,B) -> C`
 351 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 352 pub struct ParenthesizedParameterData {
 353     /// Overall span
 354     pub span: Span,
 355
 356     /// `(A,B)`
 357     pub inputs: Vec<P<Ty>>,
 358
 359     /// `C`
 360     pub output: Option<P<Ty>>,
 361 }
 362
 363 pub type CrateNum = u32;
 364
 365 pub type NodeId = u32;
 366
 367 /// Node id used to represent the root of the crate.
 368 pub const CRATE_NODE_ID: NodeId = 0;
 369
 370 /// When parsing and doing expansions, we initially give all AST nodes this AST
 371 /// node value. Then later, in the renumber pass, we renumber them to have
 372 /// small, positive ids.
 373 pub const DUMMY_NODE_ID: NodeId = !0;
 374
 375 pub trait NodeIdAssigner {
 376     fn next_node_id(&self) -> NodeId;
 377     fn peek_node_id(&self) -> NodeId;
 378 }
 379
 380 /// The AST represents all type param bounds as types.
 381 /// typeck::collect::compute_bounds matches these against
 382 /// the "special" built-in traits (see middle::lang_items) and
 383 /// detects Copy, Send and Sync.
 384 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 385 pub enum TyParamBound {
 386     TraitTyParamBound(PolyTraitRef, TraitBoundModifier),
 387     RegionTyParamBound(Lifetime)
 388 }
 389
 390 /// A modifier on a bound, currently this is only used for `?Sized`, where the
 391 /// modifier is `Maybe`. Negative bounds should also be handled here.
 392 #[derive(Copy, Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 393 pub enum TraitBoundModifier {
 394     None,
 395     Maybe,
 396 }
 397
 398 pub type TyParamBounds = OwnedSlice<TyParamBound>;
 399
 400 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 401 pub struct TyParam {
 402     pub ident: Ident,
 403     pub id: NodeId,
 404     pub bounds: TyParamBounds,
 405     pub default: Option<P<Ty>>,
 406     pub span: Span
 407 }
 408
 409 /// Represents lifetimes and type parameters attached to a declaration
 410 /// of a function, enum, trait, etc.
 411 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 412 pub struct Generics {
 413     pub lifetimes: Vec<LifetimeDef>,
 414     pub ty_params: OwnedSlice<TyParam>,
 415     pub where_clause: WhereClause,
 416 }
 417
 418 impl Generics {
 419     pub fn is_lt_parameterized(&self) -> bool {
 420         !self.lifetimes.is_empty()
 421     }
 422     pub fn is_type_parameterized(&self) -> bool {
 423         !self.ty_params.is_empty()
 424     }
 425     pub fn is_parameterized(&self) -> bool {
 426         self.is_lt_parameterized() || self.is_type_parameterized()
 427     }
 428 }
 429
 430 /// A `where` clause in a definition
 431 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 432 pub struct WhereClause {
 433     pub id: NodeId,
 434     pub predicates: Vec<WherePredicate>,
 435 }
 436
 437 /// A single predicate in a `where` clause
 438 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 439 pub enum WherePredicate {
 440     /// A type binding, eg `for<'c> Foo: Send+Clone+'c`
 441     BoundPredicate(WhereBoundPredicate),
 442     /// A lifetime predicate, e.g. `'a: 'b+'c`
 443     RegionPredicate(WhereRegionPredicate),
 444     /// An equality predicate (unsupported)
 445     EqPredicate(WhereEqPredicate),
 446 }
 447
 448 /// A type bound, eg `for<'c> Foo: Send+Clone+'c`
 449 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 450 pub struct WhereBoundPredicate {
 451     pub span: Span,
 452     /// Any lifetimes from a `for` binding
 453     pub bound_lifetimes: Vec<LifetimeDef>,
 454     /// The type being bounded
 455     pub bounded_ty: P<Ty>,
 456     /// Trait and lifetime bounds (`Clone+Send+'static`)
 457     pub bounds: OwnedSlice<TyParamBound>,
 458 }
 459
 460 /// A lifetime predicate, e.g. `'a: 'b+'c`
 461 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 462 pub struct WhereRegionPredicate {
 463     pub span: Span,
 464     pub lifetime: Lifetime,
 465     pub bounds: Vec<Lifetime>,
 466 }
 467
 468 /// An equality predicate (unsupported), e.g. `T=int`
 469 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 470 pub struct WhereEqPredicate {
 471     pub id: NodeId,
 472     pub span: Span,
 473     pub path: Path,
 474     pub ty: P<Ty>,
 475 }
 476
 477 /// The set of MetaItems that define the compilation environment of the crate,
 478 /// used to drive conditional compilation
 479 pub type CrateConfig = Vec<P<MetaItem>> ;
 480
 481 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 482 pub struct Crate {
 483     pub module: Mod,
 484     pub attrs: Vec<Attribute>,
 485     pub config: CrateConfig,
 486     pub span: Span,
 487     pub exported_macros: Vec<MacroDef>,
 488 }
 489
 490 pub type MetaItem = Spanned<MetaItem_>;
 491
 492 #[derive(Clone, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 493 pub enum MetaItem_ {
 494     MetaWord(InternedString),
 495     MetaList(InternedString, Vec<P<MetaItem>>),
 496     MetaNameValue(InternedString, Lit),
 497 }
 498
 499 // can't be derived because the MetaList requires an unordered comparison
 500 impl PartialEq for MetaItem_ {
 501     fn eq(&self, other: &MetaItem_) -> bool {
 502         match *self {
 503             MetaWord(ref ns) => match *other {
 504                 MetaWord(ref no) => (*ns) == (*no),
 505                 _ => false
 506             },
 507             MetaNameValue(ref ns, ref vs) => match *other {
 508                 MetaNameValue(ref no, ref vo) => {
 509                     (*ns) == (*no) && vs.node == vo.node
 510                 }
 511                 _ => false
 512             },
 513             MetaList(ref ns, ref miss) => match *other {
 514                 MetaList(ref no, ref miso) => {
 515                     ns == no &&
 516                         miss.iter().all(|mi| miso.iter().any(|x| x.node == mi.node))
 517                 }
 518                 _ => false
 519             }
 520         }
 521     }
 522 }
 523
 524 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 525 pub struct Block {
 526     /// Statements in a block
 527     pub stmts: Vec<P<Stmt>>,
 528     /// An expression at the end of the block
 529     /// without a semicolon, if any
 530     pub expr: Option<P<Expr>>,
 531     pub id: NodeId,
 532     /// Distinguishes between `unsafe { ... }` and `{ ... }`
 533     pub rules: BlockCheckMode,
 534     pub span: Span,
 535 }
 536
 537 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash)]
 538 pub struct Pat {
 539     pub id: NodeId,
 540     pub node: Pat_,
 541     pub span: Span,
 542 }
 543
 544 impl fmt::Debug for Pat {
 545     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 546         write!(f, "pat({}: {})", self.id, pprust::pat_to_string(self))
 547     }
 548 }
 549
 550 /// A single field in a struct pattern
 551 ///
 552 /// Patterns like the fields of Foo `{ x, ref y, ref mut z }`
 553 /// are treated the same as` x: x, y: ref y, z: ref mut z`,
 554 /// except is_shorthand is true
 555 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 556 pub struct FieldPat {
 557     /// The identifier for the field
 558     pub ident: Ident,
 559     /// The pattern the field is destructured to
 560     pub pat: P<Pat>,
 561     pub is_shorthand: bool,
 562 }
 563
 564 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
 565 pub enum BindingMode {
 566     BindByRef(Mutability),
 567     BindByValue(Mutability),
 568 }
 569
 570 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 571 pub enum Pat_ {
 572     /// Represents a wildcard pattern (`_`)
 573     PatWild,
 574
 575     /// A PatIdent may either be a new bound variable,
 576     /// or a nullary enum (in which case the third field
 577     /// is None).
 578     ///
 579     /// In the nullary enum case, the parser can't determine
 580     /// which it is. The resolver determines this, and
 581     /// records this pattern's NodeId in an auxiliary
 582     /// set (of "PatIdents that refer to nullary enums")
 583     PatIdent(BindingMode, SpannedIdent, Option<P<Pat>>),
 584
 585     /// "None" means a `Variant(..)` pattern where we don't bind the fields to names.
 586     PatEnum(Path, Option<Vec<P<Pat>>>),
 587
 588     /// An associated const named using the qualified path `<T>::CONST` or
 589     /// `<T as Trait>::CONST`. Associated consts from inherent impls can be
 590     /// referred to as simply `T::CONST`, in which case they will end up as
 591     /// PatEnum, and the resolver will have to sort that out.
 592     PatQPath(QSelf, Path),
 593
 594     /// Destructuring of a struct, e.g. `Foo {x, y, ..}`
 595     /// The `bool` is `true` in the presence of a `..`
 596     PatStruct(Path, Vec<Spanned<FieldPat>>, bool),
 597     /// A tuple pattern `(a, b)`
 598     PatTup(Vec<P<Pat>>),
 599     /// A `box` pattern
 600     PatBox(P<Pat>),
 601     /// A reference pattern, e.g. `&mut (a, b)`
 602     PatRegion(P<Pat>, Mutability),
 603     /// A literal
 604     PatLit(P<Expr>),
 605     /// A range pattern, e.g. `1...2`
 606     PatRange(P<Expr>, P<Expr>),
 607     /// `[a, b, ..i, y, z]` is represented as:
 608     ///     `PatVec(box [a, b], Some(i), box [y, z])`
 609     PatVec(Vec<P<Pat>>, Option<P<Pat>>, Vec<P<Pat>>),
 610     /// A macro pattern; pre-expansion
 611     PatMac(Mac),
 612 }
 613
 614 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
 615 pub enum Mutability {
 616     MutMutable,
 617     MutImmutable,
 618 }
 619
 620 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
 621 pub enum BinOp_ {
 622     /// The `+` operator (addition)
 623     BiAdd,
 624     /// The `-` operator (subtraction)
 625     BiSub,
 626     /// The `*` operator (multiplication)
 627     BiMul,
 628     /// The `/` operator (division)
 629     BiDiv,
 630     /// The `%` operator (modulus)
 631     BiRem,
 632     /// The `&&` operator (logical and)
 633     BiAnd,
 634     /// The `||` operator (logical or)
 635     BiOr,
 636     /// The `^` operator (bitwise xor)
 637     BiBitXor,
 638     /// The `&` operator (bitwise and)
 639     BiBitAnd,
 640     /// The `|` operator (bitwise or)
 641     BiBitOr,
 642     /// The `<<` operator (shift left)
 643     BiShl,
 644     /// The `>>` operator (shift right)
 645     BiShr,
 646     /// The `==` operator (equality)
 647     BiEq,
 648     /// The `<` operator (less than)
 649     BiLt,
 650     /// The `<=` operator (less than or equal to)
 651     BiLe,
 652     /// The `!=` operator (not equal to)
 653     BiNe,
 654     /// The `>=` operator (greater than or equal to)
 655     BiGe,
 656     /// The `>` operator (greater than)
 657     BiGt,
 658 }
 659
 660 pub type BinOp = Spanned<BinOp_>;
 661
 662 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
 663 pub enum UnOp {
 664     /// The `*` operator for dereferencing
 665     UnDeref,
 666     /// The `!` operator for logical inversion
 667     UnNot,
 668     /// The `-` operator for negation
 669     UnNeg
 670 }
 671
 672 /// A statement
 673 pub type Stmt = Spanned<Stmt_>;
 674
 675 impl fmt::Debug for Stmt {
 676     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 677         write!(f, "stmt({}: {})",
 678                ast_util::stmt_id(self)
 679                    .map_or(Cow::Borrowed("<macro>"),|id|Cow::Owned(id.to_string())),
 680                pprust::stmt_to_string(self))
 681     }
 682 }
 683
 684
 685 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash)]
 686 pub enum Stmt_ {
 687     /// Could be an item or a local (let) binding:
 688     StmtDecl(P<Decl>, NodeId),
 689
 690     /// Expr without trailing semi-colon (must have unit type):
 691     StmtExpr(P<Expr>, NodeId),
 692
 693     /// Expr with trailing semi-colon (may have any type):
 694     StmtSemi(P<Expr>, NodeId),
 695
 696     StmtMac(P<Mac>, MacStmtStyle),
 697 }
 698 #[derive(Clone, Copy, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 699 pub enum MacStmtStyle {
 700     /// The macro statement had a trailing semicolon, e.g. `foo! { ... };`
 701     /// `foo!(...);`, `foo![...];`
 702     MacStmtWithSemicolon,
 703     /// The macro statement had braces; e.g. foo! { ... }
 704     MacStmtWithBraces,
 705     /// The macro statement had parentheses or brackets and no semicolon; e.g.
 706     /// `foo!(...)`. All of these will end up being converted into macro
 707     /// expressions.
 708     MacStmtWithoutBraces,
 709 }
 710
 711 // FIXME (pending discussion of #1697, #2178...): local should really be
 712 // a refinement on pat.
 713 /// Local represents a `let` statement, e.g., `let <pat>:<ty> = <expr>;`
 714 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 715 pub struct Local {
 716     pub pat: P<Pat>,
 717     pub ty: Option<P<Ty>>,
 718     /// Initializer expression to set the value, if any
 719     pub init: Option<P<Expr>>,
 720     pub id: NodeId,
 721     pub span: Span,
 722 }
 723
 724 pub type Decl = Spanned<Decl_>;
 725
 726 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 727 pub enum Decl_ {
 728     /// A local (let) binding:
 729     DeclLocal(P<Local>),
 730     /// An item binding:
 731     DeclItem(P<Item>),
 732 }
 733
 734 /// represents one arm of a 'match'
 735 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 736 pub struct Arm {
 737     pub attrs: Vec<Attribute>,
 738     pub pats: Vec<P<Pat>>,
 739     pub guard: Option<P<Expr>>,
 740     pub body: P<Expr>,
 741 }
 742
 743 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 744 pub struct Field {
 745     pub ident: SpannedIdent,
 746     pub expr: P<Expr>,
 747     pub span: Span,
 748 }
 749
 750 pub type SpannedIdent = Spanned<Ident>;
 751
 752 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
 753 pub enum BlockCheckMode {
 754     DefaultBlock,
 755     UnsafeBlock(UnsafeSource),
 756 }
 757
 758 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
 759 pub enum UnsafeSource {
 760     CompilerGenerated,
 761     UserProvided,
 762 }
 763
 764 /// An expression
 765 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash,)]
 766 pub struct Expr {
 767     pub id: NodeId,
 768     pub node: Expr_,
 769     pub span: Span,
 770 }
 771
 772 impl fmt::Debug for Expr {
 773     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 774         write!(f, "expr({}: {})", self.id, pprust::expr_to_string(self))
 775     }
 776 }
 777
 778 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 779 pub enum Expr_ {
 780     /// A `box x` expression.
 781     ExprBox(P<Expr>),
 782     /// First expr is the place; second expr is the value.
 783     ExprInPlace(P<Expr>, P<Expr>),
 784     /// An array (`[a, b, c, d]`)
 785     ExprVec(Vec<P<Expr>>),
 786     /// A function call
 787     ///
 788     /// The first field resolves to the function itself,
 789     /// and the second field is the list of arguments
 790     ExprCall(P<Expr>, Vec<P<Expr>>),
 791     /// A method call (`x.foo::<Bar, Baz>(a, b, c, d)`)
 792     ///
 793     /// The `SpannedIdent` is the identifier for the method name.
 794     /// The vector of `Ty`s are the ascripted type parameters for the method
 795     /// (within the angle brackets).
 796     ///
 797     /// The first element of the vector of `Expr`s is the expression that evaluates
 798     /// to the object on which the method is being called on (the receiver),
 799     /// and the remaining elements are the rest of the arguments.
 800     ///
 801     /// Thus, `x.foo::<Bar, Baz>(a, b, c, d)` is represented as
 802     /// `ExprMethodCall(foo, [Bar, Baz], [x, a, b, c, d])`.
 803     ExprMethodCall(SpannedIdent, Vec<P<Ty>>, Vec<P<Expr>>),
 804     /// A tuple (`(a, b, c ,d)`)
 805     ExprTup(Vec<P<Expr>>),
 806     /// A binary operation (For example: `a + b`, `a * b`)
 807     ExprBinary(BinOp, P<Expr>, P<Expr>),
 808     /// A unary operation (For example: `!x`, `*x`)
 809     ExprUnary(UnOp, P<Expr>),
 810     /// A literal (For example: `1u8`, `"foo"`)
 811     ExprLit(P<Lit>),
 812     /// A cast (`foo as f64`)
 813     ExprCast(P<Expr>, P<Ty>),
 814     /// An `if` block, with an optional else block
 815     ///
 816     /// `if expr { block } else { expr }`
 817     ExprIf(P<Expr>, P<Block>, Option<P<Expr>>),
 818     /// An `if let` expression with an optional else block
 819     ///
 820     /// `if let pat = expr { block } else { expr }`
 821     ///
 822     /// This is desugared to a `match` expression.
 823     ExprIfLet(P<Pat>, P<Expr>, P<Block>, Option<P<Expr>>),
 824     /// A while loop, with an optional label
 825     ///
 826     /// `'label: while expr { block }`
 827     ExprWhile(P<Expr>, P<Block>, Option<Ident>),
 828     /// A while-let loop, with an optional label
 829     ///
 830     /// `'label: while let pat = expr { block }`
 831     ///
 832     /// This is desugared to a combination of `loop` and `match` expressions.
 833     ExprWhileLet(P<Pat>, P<Expr>, P<Block>, Option<Ident>),
 834     /// A for loop, with an optional label
 835     ///
 836     /// `'label: for pat in expr { block }`
 837     ///
 838     /// This is desugared to a combination of `loop` and `match` expressions.
 839     ExprForLoop(P<Pat>, P<Expr>, P<Block>, Option<Ident>),
 840     /// Conditionless loop (can be exited with break, continue, or return)
 841     ///
 842     /// `'label: loop { block }`
 843     ExprLoop(P<Block>, Option<Ident>),
 844     /// A `match` block.
 845     ExprMatch(P<Expr>, Vec<Arm>),
 846     /// A closure (for example, `move |a, b, c| {a + b + c}`)
 847     ExprClosure(CaptureClause, P<FnDecl>, P<Block>),
 848     /// A block (`{ ... }`)
 849     ExprBlock(P<Block>),
 850
 851     /// An assignment (`a = foo()`)
 852     ExprAssign(P<Expr>, P<Expr>),
 853     /// An assignment with an operator
 854     ///
 855     /// For example, `a += 1`.
 856     ExprAssignOp(BinOp, P<Expr>, P<Expr>),
 857     /// Access of a named struct field (`obj.foo`)
 858     ExprField(P<Expr>, SpannedIdent),
 859     /// Access of an unnamed field of a struct or tuple-struct
 860     ///
 861     /// For example, `foo.0`.
 862     ExprTupField(P<Expr>, Spanned<usize>),
 863     /// An indexing operation (`foo[2]`)
 864     ExprIndex(P<Expr>, P<Expr>),
 865     /// A range (`1..2`, `1..`, or `..2`)
 866     ExprRange(Option<P<Expr>>, Option<P<Expr>>),
 867
 868     /// Variable reference, possibly containing `::` and/or type
 869     /// parameters, e.g. foo::bar::<baz>.
 870     ///
 871     /// Optionally "qualified",
 872     /// e.g. `<Vec<T> as SomeTrait>::SomeType`.
 873     ExprPath(Option<QSelf>, Path),
 874
 875     /// A referencing operation (`&a` or `&mut a`)
 876     ExprAddrOf(Mutability, P<Expr>),
 877     /// A `break`, with an optional label to break
 878     ExprBreak(Option<SpannedIdent>),
 879     /// A `continue`, with an optional label
 880     ExprAgain(Option<SpannedIdent>),
 881     /// A `return`, with an optional value to be returned
 882     ExprRet(Option<P<Expr>>),
 883
 884     /// Output of the `asm!()` macro
 885     ExprInlineAsm(InlineAsm),
 886
 887     /// A macro invocation; pre-expansion
 888     ExprMac(Mac),
 889
 890     /// A struct literal expression.
 891     ///
 892     /// For example, `Foo {x: 1, y: 2}`, or
 893     /// `Foo {x: 1, .. base}`, where `base` is the `Option<Expr>`.
 894     ExprStruct(Path, Vec<Field>, Option<P<Expr>>),
 895
 896     /// An array literal constructed from one repeated element.
 897     ///
 898     /// For example, `[1u8; 5]`. The first expression is the element
 899     /// to be repeated; the second is the number of times to repeat it.
 900     ExprRepeat(P<Expr>, P<Expr>),
 901
 902     /// No-op: used solely so we can pretty-print faithfully
 903     ExprParen(P<Expr>)
 904 }
 905
 906 /// The explicit Self type in a "qualified path". The actual
 907 /// path, including the trait and the associated item, is stored
 908 /// separately. `position` represents the index of the associated
 909 /// item qualified with this Self type.
 910 ///
 911 /// ```ignore
 912 /// <Vec<T> as a::b::Trait>::AssociatedItem
 913 ///  ^~~~~     ~~~~~~~~~~~~~~^
 914 ///  ty        position = 3
 915 ///
 916 /// <Vec<T>>::AssociatedItem
 917 ///  ^~~~~    ^
 918 ///  ty       position = 0
 919 /// ```
 920 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 921 pub struct QSelf {
 922     pub ty: P<Ty>,
 923     pub position: usize
 924 }
 925
 926 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
 927 pub enum CaptureClause {
 928     CaptureByValue,
 929     CaptureByRef,
 930 }
 931
 932 /// A delimited sequence of token trees
 933 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 934 pub struct Delimited {
 935     /// The type of delimiter
 936     pub delim: token::DelimToken,
 937     /// The span covering the opening delimiter
 938     pub open_span: Span,
 939     /// The delimited sequence of token trees
 940     pub tts: Vec<TokenTree>,
 941     /// The span covering the closing delimiter
 942     pub close_span: Span,
 943 }
 944
 945 impl Delimited {
 946     /// Returns the opening delimiter as a token.
 947     pub fn open_token(&self) -> token::Token {
 948         token::OpenDelim(self.delim)
 949     }
 950
 951     /// Returns the closing delimiter as a token.
 952     pub fn close_token(&self) -> token::Token {
 953         token::CloseDelim(self.delim)
 954     }
 955
 956     /// Returns the opening delimiter as a token tree.
 957     pub fn open_tt(&self) -> TokenTree {
 958         TokenTree::Token(self.open_span, self.open_token())
 959     }
 960
 961     /// Returns the closing delimiter as a token tree.
 962     pub fn close_tt(&self) -> TokenTree {
 963         TokenTree::Token(self.close_span, self.close_token())
 964     }
 965 }
 966
 967 /// A sequence of token treesee
 968 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
 969 pub struct SequenceRepetition {
 970     /// The sequence of token trees
 971     pub tts: Vec<TokenTree>,
 972     /// The optional separator
 973     pub separator: Option<token::Token>,
 974     /// Whether the sequence can be repeated zero (*), or one or more times (+)
 975     pub op: KleeneOp,
 976     /// The number of `MatchNt`s that appear in the sequence (and subsequences)
 977     pub num_captures: usize,
 978 }
 979
 980 /// A Kleene-style [repetition operator](http://en.wikipedia.org/wiki/Kleene_star)
 981 /// for token sequences.
 982 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
 983 pub enum KleeneOp {
 984     ZeroOrMore,
 985     OneOrMore,
 986 }
 987
 988 /// When the main rust parser encounters a syntax-extension invocation, it
 989 /// parses the arguments to the invocation as a token-tree. This is a very
 990 /// loose structure, such that all sorts of different AST-fragments can
 991 /// be passed to syntax extensions using a uniform type.
 992 ///
 993 /// If the syntax extension is an MBE macro, it will attempt to match its
 994 /// LHS token tree against the provided token tree, and if it finds a
 995 /// match, will transcribe the RHS token tree, splicing in any captured
 996 /// macro_parser::matched_nonterminals into the `SubstNt`s it finds.
 997 ///
 998 /// The RHS of an MBE macro is the only place `SubstNt`s are substituted.
 999 /// Nothing special happens to misnamed or misplaced `SubstNt`s.
1000 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1001 pub enum TokenTree {
1002     /// A single token
1003     Token(Span, token::Token),
1004     /// A delimited sequence of token trees
1005     Delimited(Span, Rc<Delimited>),
1006
1007     // This only makes sense in MBE macros.
1008
1009     /// A kleene-style repetition sequence with a span
1010     // FIXME(eddyb) #12938 Use DST.
1011     Sequence(Span, Rc<SequenceRepetition>),
1012 }
1013
1014 impl TokenTree {
1015     pub fn len(&self) -> usize {
1016         match *self {
1017             TokenTree::Token(_, token::DocComment(name)) => {
1018                 match doc_comment_style(&name.as_str()) {
1019                     AttrStyle::Outer => 2,
1020                     AttrStyle::Inner => 3
1021                 }
1022             }
1023             TokenTree::Token(_, token::SpecialVarNt(..)) => 2,
1024             TokenTree::Token(_, token::MatchNt(..)) => 3,
1025             TokenTree::Delimited(_, ref delimed) => {
1026                 delimed.tts.len() + 2
1027             }
1028             TokenTree::Sequence(_, ref seq) => {
1029                 seq.tts.len()
1030             }
1031             TokenTree::Token(..) => 0
1032         }
1033     }
1034
1035     pub fn get_tt(&self, index: usize) -> TokenTree {
1036         match (self, index) {
1037             (&TokenTree::Token(sp, token::DocComment(_)), 0) => {
1038                 TokenTree::Token(sp, token::Pound)
1039             }
1040             (&TokenTree::Token(sp, token::DocComment(name)), 1)
1041             if doc_comment_style(&name.as_str()) == AttrStyle::Inner => {
1042                 TokenTree::Token(sp, token::Not)
1043             }
1044             (&TokenTree::Token(sp, token::DocComment(name)), _) => {
1045                 let stripped = strip_doc_comment_decoration(&name.as_str());
1046                 TokenTree::Delimited(sp, Rc::new(Delimited {
1047                     delim: token::Bracket,
1048                     open_span: sp,
1049                     tts: vec![TokenTree::Token(sp, token::Ident(token::str_to_ident("doc"),
1050                                                                 token::Plain)),
1051                               TokenTree::Token(sp, token::Eq),
1052                               TokenTree::Token(sp, token::Literal(
1053                                   token::StrRaw(token::intern(&stripped), 0), None))],
1054                     close_span: sp,
1055                 }))
1056             }
1057             (&TokenTree::Delimited(_, ref delimed), _) => {
1058                 if index == 0 {
1059                     return delimed.open_tt();
1060                 }
1061                 if index == delimed.tts.len() + 1 {
1062                     return delimed.close_tt();
1063                 }
1064                 delimed.tts[index - 1].clone()
1065             }
1066             (&TokenTree::Token(sp, token::SpecialVarNt(var)), _) => {
1067                 let v = [TokenTree::Token(sp, token::Dollar),
1068                          TokenTree::Token(sp, token::Ident(token::str_to_ident(var.as_str()),
1069                                                   token::Plain))];
1070                 v[index].clone()
1071             }
1072             (&TokenTree::Token(sp, token::MatchNt(name, kind, name_st, kind_st)), _) => {
1073                 let v = [TokenTree::Token(sp, token::SubstNt(name, name_st)),
1074                          TokenTree::Token(sp, token::Colon),
1075                          TokenTree::Token(sp, token::Ident(kind, kind_st))];
1076                 v[index].clone()
1077             }
1078             (&TokenTree::Sequence(_, ref seq), _) => {
1079                 seq.tts[index].clone()
1080             }
1081             _ => panic!("Cannot expand a token tree")
1082         }
1083     }
1084
1085     /// Returns the `Span` corresponding to this token tree.
1086     pub fn get_span(&self) -> Span {
1087         match *self {
1088             TokenTree::Token(span, _)     => span,
1089             TokenTree::Delimited(span, _) => span,
1090             TokenTree::Sequence(span, _)  => span,
1091         }
1092     }
1093
1094     /// Use this token tree as a matcher to parse given tts.
1095     pub fn parse(cx: &base::ExtCtxt, mtch: &[TokenTree], tts: &[TokenTree])
1096                  -> macro_parser::NamedParseResult {
1097         // `None` is because we're not interpolating
1098         let arg_rdr = lexer::new_tt_reader_with_doc_flag(&cx.parse_sess().span_diagnostic,
1099                                                          None,
1100                                                          None,
1101                                                          tts.iter().cloned().collect(),
1102                                                          true);
1103         macro_parser::parse(cx.parse_sess(), cx.cfg(), arg_rdr, mtch)
1104     }
1105 }
1106
1107 pub type Mac = Spanned<Mac_>;
1108
1109 /// Represents a macro invocation. The Path indicates which macro
1110 /// is being invoked, and the vector of token-trees contains the source
1111 /// of the macro invocation.
1112 ///
1113 /// NB: the additional ident for a macro_rules-style macro is actually
1114 /// stored in the enclosing item. Oog.
1115 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1116 pub struct Mac_ {
1117     pub path: Path,
1118     pub tts: Vec<TokenTree>,
1119     pub ctxt: SyntaxContext,
1120 }
1121
1122 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
1123 pub enum StrStyle {
1124     /// A regular string, like `"foo"`
1125     CookedStr,
1126     /// A raw string, like `r##"foo"##`
1127     ///
1128     /// The uint is the number of `#` symbols used
1129     RawStr(usize)
1130 }
1131
1132 /// A literal
1133 pub type Lit = Spanned<Lit_>;
1134
1135 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
1136 pub enum Sign {
1137     Minus,
1138     Plus
1139 }
1140
1141 impl Sign {
1142     pub fn new<T: IntSign>(n: T) -> Sign {
1143         n.sign()
1144     }
1145 }
1146
1147 pub trait IntSign {
1148     fn sign(&self) -> Sign;
1149 }
1150 macro_rules! doit {
1151     ($($t:ident)*) => ($(impl IntSign for $t {
1152         #[allow(unused_comparisons)]
1153         fn sign(&self) -> Sign {
1154             if *self < 0 {Minus} else {Plus}
1155         }
1156     })*)
1157 }
1158 doit! { i8 i16 i32 i64 isize u8 u16 u32 u64 usize }
1159
1160 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
1161 pub enum LitIntType {
1162     SignedIntLit(IntTy, Sign),
1163     UnsignedIntLit(UintTy),
1164     UnsuffixedIntLit(Sign)
1165 }
1166
1167 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1168 pub enum Lit_ {
1169     /// A string literal (`"foo"`)
1170     LitStr(InternedString, StrStyle),
1171     /// A byte string (`b"foo"`)
1172     LitByteStr(Rc<Vec<u8>>),
1173     /// A byte char (`b'f'`)
1174     LitByte(u8),
1175     /// A character literal (`'a'`)
1176     LitChar(char),
1177     /// An integer literal (`1u8`)
1178     LitInt(u64, LitIntType),
1179     /// A float literal (`1f64` or `1E10f64`)
1180     LitFloat(InternedString, FloatTy),
1181     /// A float literal without a suffix (`1.0 or 1.0E10`)
1182     LitFloatUnsuffixed(InternedString),
1183     /// A boolean literal
1184     LitBool(bool),
1185 }
1186
1187 // NB: If you change this, you'll probably want to change the corresponding
1188 // type structure in middle/ty.rs as well.
1189 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1190 pub struct MutTy {
1191     pub ty: P<Ty>,
1192     pub mutbl: Mutability,
1193 }
1194
1195 /// Represents a method's signature in a trait declaration,
1196 /// or in an implementation.
1197 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1198 pub struct MethodSig {
1199     pub unsafety: Unsafety,
1200     pub constness: Constness,
1201     pub abi: Abi,
1202     pub decl: P<FnDecl>,
1203     pub generics: Generics,
1204     pub explicit_self: ExplicitSelf,
1205 }
1206
1207 /// Represents a method declaration in a trait declaration, possibly including
1208 /// a default implementation A trait method is either required (meaning it
1209 /// doesn't have an implementation, just a signature) or provided (meaning it
1210 /// has a default implementation).
1211 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1212 pub struct TraitItem {
1213     pub id: NodeId,
1214     pub ident: Ident,
1215     pub attrs: Vec<Attribute>,
1216     pub node: TraitItem_,
1217     pub span: Span,
1218 }
1219
1220 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1221 pub enum TraitItem_ {
1222     ConstTraitItem(P<Ty>, Option<P<Expr>>),
1223     MethodTraitItem(MethodSig, Option<P<Block>>),
1224     TypeTraitItem(TyParamBounds, Option<P<Ty>>),
1225 }
1226
1227 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1228 pub struct ImplItem {
1229     pub id: NodeId,
1230     pub ident: Ident,
1231     pub vis: Visibility,
1232     pub attrs: Vec<Attribute>,
1233     pub node: ImplItem_,
1234     pub span: Span,
1235 }
1236
1237 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1238 pub enum ImplItem_ {
1239     ConstImplItem(P<Ty>, P<Expr>),
1240     MethodImplItem(MethodSig, P<Block>),
1241     TypeImplItem(P<Ty>),
1242     MacImplItem(Mac),
1243 }
1244
1245 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Copy)]
1246 pub enum IntTy {
1247     TyIs,
1248     TyI8,
1249     TyI16,
1250     TyI32,
1251     TyI64,
1252 }
1253
1254 impl fmt::Debug for IntTy {
1255     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1256         fmt::Display::fmt(self, f)
1257     }
1258 }
1259
1260 impl fmt::Display for IntTy {
1261     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1262         write!(f, "{}", ast_util::int_ty_to_string(*self, None))
1263     }
1264 }
1265
1266 impl IntTy {
1267     pub fn bit_width(&self) -> Option<usize> {
1268         Some(match *self {
1269             TyIs => return None,
1270             TyI8 => 8,
1271             TyI16 => 16,
1272             TyI32 => 32,
1273             TyI64 => 64,
1274         })
1275     }
1276 }
1277
1278 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Copy)]
1279 pub enum UintTy {
1280     TyUs,
1281     TyU8,
1282     TyU16,
1283     TyU32,
1284     TyU64,
1285 }
1286
1287 impl UintTy {
1288     pub fn bit_width(&self) -> Option<usize> {
1289         Some(match *self {
1290             TyUs => return None,
1291             TyU8 => 8,
1292             TyU16 => 16,
1293             TyU32 => 32,
1294             TyU64 => 64,
1295         })
1296     }
1297 }
1298
1299 impl fmt::Debug for UintTy {
1300     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1301         fmt::Display::fmt(self, f)
1302     }
1303 }
1304
1305 impl fmt::Display for UintTy {
1306     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1307         write!(f, "{}", ast_util::uint_ty_to_string(*self, None))
1308     }
1309 }
1310
1311 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Copy)]
1312 pub enum FloatTy {
1313     TyF32,
1314     TyF64,
1315 }
1316
1317 impl fmt::Debug for FloatTy {
1318     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1319         fmt::Display::fmt(self, f)
1320     }
1321 }
1322
1323 impl fmt::Display for FloatTy {
1324     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1325         write!(f, "{}", ast_util::float_ty_to_string(*self))
1326     }
1327 }
1328
1329 impl FloatTy {
1330     pub fn bit_width(&self) -> usize {
1331         match *self {
1332             TyF32 => 32,
1333             TyF64 => 64,
1334         }
1335     }
1336 }
1337
1338 // Bind a type to an associated type: `A=Foo`.
1339 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1340 pub struct TypeBinding {
1341     pub id: NodeId,
1342     pub ident: Ident,
1343     pub ty: P<Ty>,
1344     pub span: Span,
1345 }
1346
1347 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash)]
1348 pub struct Ty {
1349     pub id: NodeId,
1350     pub node: Ty_,
1351     pub span: Span,
1352 }
1353
1354 impl fmt::Debug for Ty {
1355     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1356         write!(f, "type({})", pprust::ty_to_string(self))
1357     }
1358 }
1359
1360 /// Not represented directly in the AST, referred to by name through a ty_path.
1361 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
1362 pub enum PrimTy {
1363     TyInt(IntTy),
1364     TyUint(UintTy),
1365     TyFloat(FloatTy),
1366     TyStr,
1367     TyBool,
1368     TyChar
1369 }
1370
1371 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1372 pub struct BareFnTy {
1373     pub unsafety: Unsafety,
1374     pub abi: Abi,
1375     pub lifetimes: Vec<LifetimeDef>,
1376     pub decl: P<FnDecl>
1377 }
1378
1379 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1380 /// The different kinds of types recognized by the compiler
1381 pub enum Ty_ {
1382     TyVec(P<Ty>),
1383     /// A fixed length array (`[T; n]`)
1384     TyFixedLengthVec(P<Ty>, P<Expr>),
1385     /// A raw pointer (`*const T` or `*mut T`)
1386     TyPtr(MutTy),
1387     /// A reference (`&'a T` or `&'a mut T`)
1388     TyRptr(Option<Lifetime>, MutTy),
1389     /// A bare function (e.g. `fn(usize) -> bool`)
1390     TyBareFn(P<BareFnTy>),
1391     /// A tuple (`(A, B, C, D,...)`)
1392     TyTup(Vec<P<Ty>> ),
1393     /// A path (`module::module::...::Type`), optionally
1394     /// "qualified", e.g. `<Vec<T> as SomeTrait>::SomeType`.
1395     ///
1396     /// Type parameters are stored in the Path itself
1397     TyPath(Option<QSelf>, Path),
1398     /// Something like `A+B`. Note that `B` must always be a path.
1399     TyObjectSum(P<Ty>, TyParamBounds),
1400     /// A type like `for<'a> Foo<&'a Bar>`
1401     TyPolyTraitRef(TyParamBounds),
1402     /// No-op; kept solely so that we can pretty-print faithfully
1403     TyParen(P<Ty>),
1404     /// Unused for now
1405     TyTypeof(P<Expr>),
1406     /// TyInfer means the type should be inferred instead of it having been
1407     /// specified. This can appear anywhere in a type.
1408     TyInfer,
1409     // A macro in the type position.
1410     TyMac(Mac)
1411 }
1412
1413 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
1414 pub enum AsmDialect {
1415     Att,
1416     Intel,
1417 }
1418
1419 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1420 pub struct InlineAsm {
1421     pub asm: InternedString,
1422     pub asm_str_style: StrStyle,
1423     pub outputs: Vec<(InternedString, P<Expr>, bool)>,
1424     pub inputs: Vec<(InternedString, P<Expr>)>,
1425     pub clobbers: Vec<InternedString>,
1426     pub volatile: bool,
1427     pub alignstack: bool,
1428     pub dialect: AsmDialect,
1429     pub expn_id: ExpnId,
1430 }
1431
1432 /// represents an argument in a function header
1433 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1434 pub struct Arg {
1435     pub ty: P<Ty>,
1436     pub pat: P<Pat>,
1437     pub id: NodeId,
1438 }
1439
1440 impl Arg {
1441     pub fn new_self(span: Span, mutability: Mutability, self_ident: Ident) -> Arg {
1442         let path = Spanned{span:span,node:self_ident};
1443         Arg {
1444             // HACK(eddyb) fake type for the self argument.
1445             ty: P(Ty {
1446                 id: DUMMY_NODE_ID,
1447                 node: TyInfer,
1448                 span: DUMMY_SP,
1449             }),
1450             pat: P(Pat {
1451                 id: DUMMY_NODE_ID,
1452                 node: PatIdent(BindByValue(mutability), path, None),
1453                 span: span
1454             }),
1455             id: DUMMY_NODE_ID
1456         }
1457     }
1458 }
1459
1460 /// Represents the header (not the body) of a function declaration
1461 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1462 pub struct FnDecl {
1463     pub inputs: Vec<Arg>,
1464     pub output: FunctionRetTy,
1465     pub variadic: bool
1466 }
1467
1468 #[derive(Copy, Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1469 pub enum Unsafety {
1470     Unsafe,
1471     Normal,
1472 }
1473
1474 #[derive(Copy, Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1475 pub enum Constness {
1476     Const,
1477     NotConst,
1478 }
1479
1480 impl fmt::Display for Unsafety {
1481     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1482         fmt::Display::fmt(match *self {
1483             Unsafety::Normal => "normal",
1484             Unsafety::Unsafe => "unsafe",
1485         }, f)
1486     }
1487 }
1488
1489 #[derive(Copy, Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash)]
1490 pub enum ImplPolarity {
1491     /// `impl Trait for Type`
1492     Positive,
1493     /// `impl !Trait for Type`
1494     Negative,
1495 }
1496
1497 impl fmt::Debug for ImplPolarity {
1498     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1499         match *self {
1500             ImplPolarity::Positive => "positive".fmt(f),
1501             ImplPolarity::Negative => "negative".fmt(f),
1502         }
1503     }
1504 }
1505
1506
1507 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1508 pub enum FunctionRetTy {
1509     /// Functions with return type `!`that always
1510     /// raise an error or exit (i.e. never return to the caller)
1511     NoReturn(Span),
1512     /// Return type is not specified.
1513     ///
1514     /// Functions default to `()` and
1515     /// closures default to inference. Span points to where return
1516     /// type would be inserted.
1517     DefaultReturn(Span),
1518     /// Everything else
1519     Return(P<Ty>),
1520 }
1521
1522 impl FunctionRetTy {
1523     pub fn span(&self) -> Span {
1524         match *self {
1525             NoReturn(span) => span,
1526             DefaultReturn(span) => span,
1527             Return(ref ty) => ty.span
1528         }
1529     }
1530 }
1531
1532 /// Represents the kind of 'self' associated with a method
1533 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1534 pub enum ExplicitSelf_ {
1535     /// No self
1536     SelfStatic,
1537     /// `self`
1538     SelfValue(Ident),
1539     /// `&'lt self`, `&'lt mut self`
1540     SelfRegion(Option<Lifetime>, Mutability, Ident),
1541     /// `self: TYPE`
1542     SelfExplicit(P<Ty>, Ident),
1543 }
1544
1545 pub type ExplicitSelf = Spanned<ExplicitSelf_>;
1546
1547 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1548 pub struct Mod {
1549     /// A span from the first token past `{` to the last token until `}`.
1550     /// For `mod foo;`, the inner span ranges from the first token
1551     /// to the last token in the external file.
1552     pub inner: Span,
1553     pub items: Vec<P<Item>>,
1554 }
1555
1556 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1557 pub struct ForeignMod {
1558     pub abi: Abi,
1559     pub items: Vec<P<ForeignItem>>,
1560 }
1561
1562 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1563 pub struct EnumDef {
1564     pub variants: Vec<P<Variant>>,
1565 }
1566
1567 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1568 pub struct Variant_ {
1569     pub name: Ident,
1570     pub attrs: Vec<Attribute>,
1571     pub data: VariantData,
1572     /// Explicit discriminant, eg `Foo = 1`
1573     pub disr_expr: Option<P<Expr>>,
1574 }
1575
1576 pub type Variant = Spanned<Variant_>;
1577
1578 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
1579 pub enum PathListItem_ {
1580     PathListIdent {
1581         name: Ident,
1582         /// renamed in list, eg `use foo::{bar as baz};`
1583         rename: Option<Ident>,
1584         id: NodeId
1585     },
1586     PathListMod {
1587         /// renamed in list, eg `use foo::{self as baz};`
1588         rename: Option<Ident>,
1589         id: NodeId
1590     }
1591 }
1592
1593 impl PathListItem_ {
1594     pub fn id(&self) -> NodeId {
1595         match *self {
1596             PathListIdent { id, .. } | PathListMod { id, .. } => id
1597         }
1598     }
1599
1600     pub fn name(&self) -> Option<Ident> {
1601         match *self {
1602             PathListIdent { name, .. } => Some(name),
1603             PathListMod { .. } => None,
1604         }
1605     }
1606
1607     pub fn rename(&self) -> Option<Ident> {
1608         match *self {
1609             PathListIdent { rename, .. } | PathListMod { rename, .. } => rename
1610         }
1611     }
1612 }
1613
1614 pub type PathListItem = Spanned<PathListItem_>;
1615
1616 pub type ViewPath = Spanned<ViewPath_>;
1617
1618 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1619 pub enum ViewPath_ {
1620
1621     /// `foo::bar::baz as quux`
1622     ///
1623     /// or just
1624     ///
1625     /// `foo::bar::baz` (with `as baz` implicitly on the right)
1626     ViewPathSimple(Ident, Path),
1627
1628     /// `foo::bar::*`
1629     ViewPathGlob(Path),
1630
1631     /// `foo::bar::{a,b,c}`
1632     ViewPathList(Path, Vec<PathListItem>)
1633 }
1634
1635 /// Meta-data associated with an item
1636 pub type Attribute = Spanned<Attribute_>;
1637
1638 /// Distinguishes between Attributes that decorate items and Attributes that
1639 /// are contained as statements within items. These two cases need to be
1640 /// distinguished for pretty-printing.
1641 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
1642 pub enum AttrStyle {
1643     Outer,
1644     Inner,
1645 }
1646
1647 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
1648 pub struct AttrId(pub usize);
1649
1650 /// Doc-comments are promoted to attributes that have is_sugared_doc = true
1651 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1652 pub struct Attribute_ {
1653     pub id: AttrId,
1654     pub style: AttrStyle,
1655     pub value: P<MetaItem>,
1656     pub is_sugared_doc: bool,
1657 }
1658
1659 /// TraitRef's appear in impls.
1660 ///
1661 /// resolve maps each TraitRef's ref_id to its defining trait; that's all
1662 /// that the ref_id is for. The impl_id maps to the "self type" of this impl.
1663 /// If this impl is an ItemImpl, the impl_id is redundant (it could be the
1664 /// same as the impl's node id).
1665 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1666 pub struct TraitRef {
1667     pub path: Path,
1668     pub ref_id: NodeId,
1669 }
1670
1671 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1672 pub struct PolyTraitRef {
1673     /// The `'a` in `<'a> Foo<&'a T>`
1674     pub bound_lifetimes: Vec<LifetimeDef>,
1675
1676     /// The `Foo<&'a T>` in `<'a> Foo<&'a T>`
1677     pub trait_ref: TraitRef,
1678
1679     pub span: Span,
1680 }
1681
1682 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
1683 pub enum Visibility {
1684     Public,
1685     Inherited,
1686 }
1687
1688 impl Visibility {
1689     pub fn inherit_from(&self, parent_visibility: Visibility) -> Visibility {
1690         match self {
1691             &Inherited => parent_visibility,
1692             &Public => *self
1693         }
1694     }
1695 }
1696
1697 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1698 pub struct StructField_ {
1699     pub kind: StructFieldKind,
1700     pub id: NodeId,
1701     pub ty: P<Ty>,
1702     pub attrs: Vec<Attribute>,
1703 }
1704
1705 impl StructField_ {
1706     pub fn ident(&self) -> Option<Ident> {
1707         match self.kind {
1708             NamedField(ref ident, _) => Some(ident.clone()),
1709             UnnamedField(_) => None
1710         }
1711     }
1712 }
1713
1714 pub type StructField = Spanned<StructField_>;
1715
1716 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
1717 pub enum StructFieldKind {
1718     NamedField(Ident, Visibility),
1719     /// Element of a tuple-like struct
1720     UnnamedField(Visibility),
1721 }
1722
1723 impl StructFieldKind {
1724     pub fn is_unnamed(&self) -> bool {
1725         match *self {
1726             UnnamedField(..) => true,
1727             NamedField(..) => false,
1728         }
1729     }
1730
1731     pub fn visibility(&self) -> Visibility {
1732         match *self {
1733             NamedField(_, vis) | UnnamedField(vis) => vis
1734         }
1735     }
1736 }
1737
1738 /// Fields and Ids of enum variants and structs
1739 ///
1740 /// For enum variants: `NodeId` represents both an Id of the variant itself (relevant for all
1741 /// variant kinds) and an Id of the variant's constructor (not relevant for `Struct`-variants).
1742 /// One shared Id can be successfully used for these two purposes.
1743 /// Id of the whole enum lives in `Item`.
1744 ///
1745 /// For structs: `NodeId` represents an Id of the structure's constructor, so it is not actually
1746 /// used for `Struct`-structs (but still presents). Structures don't have an analogue of "Id of
1747 /// the variant itself" from enum variants.
1748 /// Id of the whole struct lives in `Item`.
1749 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1750 pub enum VariantData {
1751     Struct(Vec<StructField>, NodeId),
1752     Tuple(Vec<StructField>, NodeId),
1753     Unit(NodeId),
1754 }
1755
1756 impl VariantData {
1757     pub fn fields(&self) -> &[StructField] {
1758         match *self {
1759             VariantData::Struct(ref fields, _) | VariantData::Tuple(ref fields, _) => fields,
1760             _ => &[],
1761         }
1762     }
1763     pub fn id(&self) -> NodeId {
1764         match *self {
1765             VariantData::Struct(_, id) | VariantData::Tuple(_, id) | VariantData::Unit(id) => id
1766         }
1767     }
1768     pub fn is_struct(&self) -> bool {
1769         if let VariantData::Struct(..) = *self { true } else { false }
1770     }
1771     pub fn is_tuple(&self) -> bool {
1772         if let VariantData::Tuple(..) = *self { true } else { false }
1773     }
1774     pub fn is_unit(&self) -> bool {
1775         if let VariantData::Unit(..) = *self { true } else { false }
1776     }
1777 }
1778
1779 /*
1780   FIXME (#3300): Should allow items to be anonymous. Right now
1781   we just use dummy names for anon items.
1782  */
1783 /// An item
1784 ///
1785 /// The name might be a dummy name in case of anonymous items
1786 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1787 pub struct Item {
1788     pub ident: Ident,
1789     pub attrs: Vec<Attribute>,
1790     pub id: NodeId,
1791     pub node: Item_,
1792     pub vis: Visibility,
1793     pub span: Span,
1794 }
1795
1796 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1797 pub enum Item_ {
1798     /// An`extern crate` item, with optional original crate name,
1799     ///
1800     /// e.g. `extern crate foo` or `extern crate foo_bar as foo`
1801     ItemExternCrate(Option<Name>),
1802     /// A `use` or `pub use` item
1803     ItemUse(P<ViewPath>),
1804
1805     /// A `static` item
1806     ItemStatic(P<Ty>, Mutability, P<Expr>),
1807     /// A `const` item
1808     ItemConst(P<Ty>, P<Expr>),
1809     /// A function declaration
1810     ItemFn(P<FnDecl>, Unsafety, Constness, Abi, Generics, P<Block>),
1811     /// A module
1812     ItemMod(Mod),
1813     /// An external module
1814     ItemForeignMod(ForeignMod),
1815     /// A type alias, e.g. `type Foo = Bar<u8>`
1816     ItemTy(P<Ty>, Generics),
1817     /// An enum definition, e.g. `enum Foo<A, B> {C<A>, D<B>}`
1818     ItemEnum(EnumDef, Generics),
1819     /// A struct definition, e.g. `struct Foo<A> {x: A}`
1820     ItemStruct(VariantData, Generics),
1821     /// Represents a Trait Declaration
1822     ItemTrait(Unsafety,
1823               Generics,
1824               TyParamBounds,
1825               Vec<P<TraitItem>>),
1826
1827     // Default trait implementations
1828     ///
1829     // `impl Trait for .. {}`
1830     ItemDefaultImpl(Unsafety, TraitRef),
1831     /// An implementation, eg `impl<A> Trait for Foo { .. }`
1832     ItemImpl(Unsafety,
1833              ImplPolarity,
1834              Generics,
1835              Option<TraitRef>, // (optional) trait this impl implements
1836              P<Ty>, // self
1837              Vec<P<ImplItem>>),
1838     /// A macro invocation (which includes macro definition)
1839     ItemMac(Mac),
1840 }
1841
1842 impl Item_ {
1843     pub fn descriptive_variant(&self) -> &str {
1844         match *self {
1845             ItemExternCrate(..) => "extern crate",
1846             ItemUse(..) => "use",
1847             ItemStatic(..) => "static item",
1848             ItemConst(..) => "constant item",
1849             ItemFn(..) => "function",
1850             ItemMod(..) => "module",
1851             ItemForeignMod(..) => "foreign module",
1852             ItemTy(..) => "type alias",
1853             ItemEnum(..) => "enum",
1854             ItemStruct(..) => "struct",
1855             ItemTrait(..) => "trait",
1856             ItemMac(..) |
1857             ItemImpl(..) |
1858             ItemDefaultImpl(..) => "item"
1859         }
1860     }
1861 }
1862
1863 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1864 pub struct ForeignItem {
1865     pub ident: Ident,
1866     pub attrs: Vec<Attribute>,
1867     pub node: ForeignItem_,
1868     pub id: NodeId,
1869     pub span: Span,
1870     pub vis: Visibility,
1871 }
1872
1873 /// An item within an `extern` block
1874 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1875 pub enum ForeignItem_ {
1876     /// A foreign function
1877     ForeignItemFn(P<FnDecl>, Generics),
1878     /// A foreign static item (`static ext: u8`), with optional mutability
1879     /// (the boolean is true when mutable)
1880     ForeignItemStatic(P<Ty>, bool),
1881 }
1882
1883 impl ForeignItem_ {
1884     pub fn descriptive_variant(&self) -> &str {
1885         match *self {
1886             ForeignItemFn(..) => "foreign function",
1887             ForeignItemStatic(..) => "foreign static item"
1888         }
1889     }
1890 }
1891
1892 /// A macro definition, in this crate or imported from another.
1893 ///
1894 /// Not parsed directly, but created on macro import or `macro_rules!` expansion.
1895 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Debug)]
1896 pub struct MacroDef {
1897     pub ident: Ident,
1898     pub attrs: Vec<Attribute>,
1899     pub id: NodeId,
1900     pub span: Span,
1901     pub imported_from: Option<Ident>,
1902     pub export: bool,
1903     pub use_locally: bool,
1904     pub allow_internal_unstable: bool,
1905     pub body: Vec<TokenTree>,
1906 }
1907
1908 #[cfg(test)]
1909 mod tests {
1910     use serialize;
1911     use super::*;
1912
1913     // are ASTs encodable?
1914     #[test]
1915     fn check_asts_encodable() {
1916         fn assert_encodable<T: serialize::Encodable>() {}
1917         assert_encodable::<Crate>();
1918     }
1919 }