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