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