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