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