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