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
 751     ExprAddrOf(Mutability, P<Expr>),
 752     ExprBreak(Option<Ident>),
 753     ExprAgain(Option<Ident>),
 754     ExprRet(Option<P<Expr>>),
 755
 756     ExprInlineAsm(InlineAsm),
 757
 758     ExprMac(Mac),
 759
 760     /// A struct literal expression.
 761     ExprStruct(Path, Vec<Field>, Option<P<Expr>> /* base */),
 762
 763     /// A vector literal constructed from one repeated element.
 764     ExprRepeat(P<Expr> /* element */, P<Expr> /* count */),
 765
 766     /// No-op: used solely so we can pretty-print faithfully
 767     ExprParen(P<Expr>)
 768 }
 769
 770 /// A "qualified path":
 771 ///
 772 ///     <Vec<T> as SomeTrait>::SomeAssociatedItem
 773 ///      ^~~~~     ^~~~~~~~~   ^~~~~~~~~~~~~~~~~~
 774 ///      self_type  trait_name  item_name
 775 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
 776 pub struct QPath {
 777     pub self_type: P<Ty>,
 778     pub trait_ref: P<TraitRef>,
 779     pub item_name: Ident, // FIXME(#20301) -- should use Name
 780 }
 781
 782 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show, Copy)]
 783 pub enum MatchSource {
 784     Normal,
 785     IfLetDesugar { contains_else_clause: bool },
 786     WhileLetDesugar,
 787 }
 788
 789 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show, Copy)]
 790 pub enum CaptureClause {
 791     CaptureByValue,
 792     CaptureByRef,
 793 }
 794
 795 /// A delimited sequence of token trees
 796 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
 797 pub struct Delimited {
 798     /// The type of delimiter
 799     pub delim: token::DelimToken,
 800     /// The span covering the opening delimiter
 801     pub open_span: Span,
 802     /// The delimited sequence of token trees
 803     pub tts: Vec<TokenTree>,
 804     /// The span covering the closing delimiter
 805     pub close_span: Span,
 806 }
 807
 808 impl Delimited {
 809     /// Returns the opening delimiter as a token.
 810     pub fn open_token(&self) -> token::Token {
 811         token::OpenDelim(self.delim)
 812     }
 813
 814     /// Returns the closing delimiter as a token.
 815     pub fn close_token(&self) -> token::Token {
 816         token::CloseDelim(self.delim)
 817     }
 818
 819     /// Returns the opening delimiter as a token tree.
 820     pub fn open_tt(&self) -> TokenTree {
 821         TtToken(self.open_span, self.open_token())
 822     }
 823
 824     /// Returns the closing delimiter as a token tree.
 825     pub fn close_tt(&self) -> TokenTree {
 826         TtToken(self.close_span, self.close_token())
 827     }
 828 }
 829
 830 /// A sequence of token treesee
 831 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
 832 pub struct SequenceRepetition {
 833     /// The sequence of token trees
 834     pub tts: Vec<TokenTree>,
 835     /// The optional separator
 836     pub separator: Option<token::Token>,
 837     /// Whether the sequence can be repeated zero (*), or one or more times (+)
 838     pub op: KleeneOp,
 839     /// The number of `MatchNt`s that appear in the sequence (and subsequences)
 840     pub num_captures: uint,
 841 }
 842
 843 /// A Kleene-style [repetition operator](http://en.wikipedia.org/wiki/Kleene_star)
 844 /// for token sequences.
 845 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show, Copy)]
 846 pub enum KleeneOp {
 847     ZeroOrMore,
 848     OneOrMore,
 849 }
 850
 851 /// When the main rust parser encounters a syntax-extension invocation, it
 852 /// parses the arguments to the invocation as a token-tree. This is a very
 853 /// loose structure, such that all sorts of different AST-fragments can
 854 /// be passed to syntax extensions using a uniform type.
 855 ///
 856 /// If the syntax extension is an MBE macro, it will attempt to match its
 857 /// LHS token tree against the provided token tree, and if it finds a
 858 /// match, will transcribe the RHS token tree, splicing in any captured
 859 /// macro_parser::matched_nonterminals into the `SubstNt`s it finds.
 860 ///
 861 /// The RHS of an MBE macro is the only place `SubstNt`s are substituted.
 862 /// Nothing special happens to misnamed or misplaced `SubstNt`s.
 863 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
 864 #[doc="For macro invocations; parsing is delegated to the macro"]
 865 pub enum TokenTree {
 866     /// A single token
 867     TtToken(Span, token::Token),
 868     /// A delimited sequence of token trees
 869     TtDelimited(Span, Rc<Delimited>),
 870
 871     // This only makes sense in MBE macros.
 872
 873     /// A kleene-style repetition sequence with a span
 874     // FIXME(eddyb) #12938 Use DST.
 875     TtSequence(Span, Rc<SequenceRepetition>),
 876 }
 877
 878 impl TokenTree {
 879     pub fn len(&self) -> uint {
 880         match *self {
 881             TtToken(_, token::DocComment(_)) => 2,
 882             TtToken(_, token::SpecialVarNt(..)) => 2,
 883             TtToken(_, token::MatchNt(..)) => 3,
 884             TtDelimited(_, ref delimed) => {
 885                 delimed.tts.len() + 2
 886             }
 887             TtSequence(_, ref seq) => {
 888                 seq.tts.len()
 889             }
 890             TtToken(..) => 0
 891         }
 892     }
 893
 894     pub fn get_tt(&self, index: uint) -> TokenTree {
 895         match (self, index) {
 896             (&TtToken(sp, token::DocComment(_)), 0) => {
 897                 TtToken(sp, token::Pound)
 898             }
 899             (&TtToken(sp, token::DocComment(name)), 1) => {
 900                 TtDelimited(sp, Rc::new(Delimited {
 901                     delim: token::Bracket,
 902                     open_span: sp,
 903                     tts: vec![TtToken(sp, token::Ident(token::str_to_ident("doc"),
 904                                                        token::Plain)),
 905                               TtToken(sp, token::Eq),
 906                               TtToken(sp, token::Literal(token::Str_(name), None))],
 907                     close_span: sp,
 908                 }))
 909             }
 910             (&TtDelimited(_, ref delimed), _) => {
 911                 if index == 0 {
 912                     return delimed.open_tt();
 913                 }
 914                 if index == delimed.tts.len() + 1 {
 915                     return delimed.close_tt();
 916                 }
 917                 delimed.tts[index - 1].clone()
 918             }
 919             (&TtToken(sp, token::SpecialVarNt(var)), _) => {
 920                 let v = [TtToken(sp, token::Dollar),
 921                          TtToken(sp, token::Ident(token::str_to_ident(var.as_str()),
 922                                                   token::Plain))];
 923                 v[index]
 924             }
 925             (&TtToken(sp, token::MatchNt(name, kind, name_st, kind_st)), _) => {
 926                 let v = [TtToken(sp, token::SubstNt(name, name_st)),
 927                          TtToken(sp, token::Colon),
 928                          TtToken(sp, token::Ident(kind, kind_st))];
 929                 v[index]
 930             }
 931             (&TtSequence(_, ref seq), _) => {
 932                 seq.tts[index].clone()
 933             }
 934             _ => panic!("Cannot expand a token tree")
 935         }
 936     }
 937
 938     /// Returns the `Span` corresponding to this token tree.
 939     pub fn get_span(&self) -> Span {
 940         match *self {
 941             TtToken(span, _)     => span,
 942             TtDelimited(span, _) => span,
 943             TtSequence(span, _)  => span,
 944         }
 945     }
 946 }
 947
 948 pub type Mac = Spanned<Mac_>;
 949
 950 /// Represents a macro invocation. The Path indicates which macro
 951 /// is being invoked, and the vector of token-trees contains the source
 952 /// of the macro invocation.
 953 /// There's only one flavor, now, so this could presumably be simplified.
 954 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
 955 pub enum Mac_ {
 956     // NB: the additional ident for a macro_rules-style macro is actually
 957     // stored in the enclosing item. Oog.
 958     MacInvocTT(Path, Vec<TokenTree> , SyntaxContext),   // new macro-invocation
 959 }
 960
 961 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show, Copy)]
 962 pub enum StrStyle {
 963     CookedStr,
 964     RawStr(uint)
 965 }
 966
 967 pub type Lit = Spanned<Lit_>;
 968
 969 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show, Copy)]
 970 pub enum Sign {
 971     Minus,
 972     Plus
 973 }
 974
 975 impl Sign {
 976     pub fn new<T:Int>(n: T) -> Sign {
 977         if n < Int::zero() {
 978             Minus
 979         } else {
 980             Plus
 981         }
 982     }
 983 }
 984
 985 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show, Copy)]
 986 pub enum LitIntType {
 987     SignedIntLit(IntTy, Sign),
 988     UnsignedIntLit(UintTy),
 989     UnsuffixedIntLit(Sign)
 990 }
 991
 992 impl LitIntType {
 993     pub fn suffix_len(&self) -> uint {
 994         match *self {
 995             UnsuffixedIntLit(_) => 0,
 996             SignedIntLit(s, _) => s.suffix_len(),
 997             UnsignedIntLit(u) => u.suffix_len()
 998         }
 999     }
1000 }
1001
1002 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1003 pub enum Lit_ {
1004     LitStr(InternedString, StrStyle),
1005     LitBinary(Rc<Vec<u8>>),
1006     LitByte(u8),
1007     LitChar(char),
1008     LitInt(u64, LitIntType),
1009     LitFloat(InternedString, FloatTy),
1010     LitFloatUnsuffixed(InternedString),
1011     LitBool(bool),
1012 }
1013
1014 // NB: If you change this, you'll probably want to change the corresponding
1015 // type structure in middle/ty.rs as well.
1016 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1017 pub struct MutTy {
1018     pub ty: P<Ty>,
1019     pub mutbl: Mutability,
1020 }
1021
1022 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1023 pub struct TypeField {
1024     pub ident: Ident,
1025     pub mt: MutTy,
1026     pub span: Span,
1027 }
1028
1029 /// Represents a required method in a trait declaration,
1030 /// one without a default implementation
1031 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1032 pub struct TypeMethod {
1033     pub ident: Ident,
1034     pub attrs: Vec<Attribute>,
1035     pub unsafety: Unsafety,
1036     pub abi: Abi,
1037     pub decl: P<FnDecl>,
1038     pub generics: Generics,
1039     pub explicit_self: ExplicitSelf,
1040     pub id: NodeId,
1041     pub span: Span,
1042     pub vis: Visibility,
1043 }
1044
1045 /// Represents a method declaration in a trait declaration, possibly including
1046 /// a default implementation A trait method is either required (meaning it
1047 /// doesn't have an implementation, just a signature) or provided (meaning it
1048 /// has a default implementation).
1049 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1050 pub enum TraitItem {
1051     RequiredMethod(TypeMethod),
1052     ProvidedMethod(P<Method>),
1053     TypeTraitItem(P<AssociatedType>),
1054 }
1055
1056 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1057 pub enum ImplItem {
1058     MethodImplItem(P<Method>),
1059     TypeImplItem(P<Typedef>),
1060 }
1061
1062 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1063 pub struct AssociatedType {
1064     pub attrs: Vec<Attribute>,
1065     pub ty_param: TyParam,
1066 }
1067
1068 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1069 pub struct Typedef {
1070     pub id: NodeId,
1071     pub span: Span,
1072     pub ident: Ident,
1073     pub vis: Visibility,
1074     pub attrs: Vec<Attribute>,
1075     pub typ: P<Ty>,
1076 }
1077
1078 #[derive(Clone, Eq, RustcEncodable, RustcDecodable, Hash, Copy)]
1079 pub enum IntTy {
1080     TyIs(bool /* is this deprecated `int`? */),
1081     TyI8,
1082     TyI16,
1083     TyI32,
1084     TyI64,
1085 }
1086
1087 impl PartialEq for IntTy {
1088     fn eq(&self, other: &IntTy) -> bool {
1089         match (*self, *other) {
1090             // true/false need to compare the same, so this can't be derived
1091             (TyIs(_), TyIs(_)) |
1092             (TyI8, TyI8) |
1093             (TyI16, TyI16) |
1094             (TyI32, TyI32) |
1095             (TyI64, TyI64) => true,
1096             _ => false
1097         }
1098     }
1099 }
1100
1101 impl fmt::Show for IntTy {
1102     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1103         fmt::String::fmt(self, f)
1104     }
1105 }
1106
1107 impl fmt::String for IntTy {
1108     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1109         write!(f, "{}", ast_util::int_ty_to_string(*self, None))
1110     }
1111 }
1112
1113 impl IntTy {
1114     pub fn suffix_len(&self) -> uint {
1115         match *self {
1116             TyIs(true) /* i */ => 1,
1117             TyIs(false) /* is */ | TyI8 => 2,
1118             TyI16 | TyI32 | TyI64  => 3,
1119         }
1120     }
1121 }
1122
1123 #[derive(Clone, Eq, RustcEncodable, RustcDecodable, Hash, Copy)]
1124 pub enum UintTy {
1125     TyUs(bool /* is this deprecated uint? */),
1126     TyU8,
1127     TyU16,
1128     TyU32,
1129     TyU64,
1130 }
1131
1132 impl PartialEq for UintTy {
1133     fn eq(&self, other: &UintTy) -> bool {
1134         match (*self, *other) {
1135             // true/false need to compare the same, so this can't be derived
1136             (TyUs(_), TyUs(_)) |
1137             (TyU8, TyU8) |
1138             (TyU16, TyU16) |
1139             (TyU32, TyU32) |
1140             (TyU64, TyU64) => true,
1141             _ => false
1142         }
1143     }
1144 }
1145
1146 impl UintTy {
1147     pub fn suffix_len(&self) -> uint {
1148         match *self {
1149             TyUs(true) /* u */ => 1,
1150             TyUs(false) /* us */ | TyU8 => 2,
1151             TyU16 | TyU32 | TyU64  => 3,
1152         }
1153     }
1154 }
1155
1156 impl fmt::Show for UintTy {
1157     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1158         fmt::String::fmt(self, f)
1159     }
1160 }
1161
1162 impl fmt::String for UintTy {
1163     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1164         write!(f, "{}", ast_util::uint_ty_to_string(*self, None))
1165     }
1166 }
1167
1168 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Copy)]
1169 pub enum FloatTy {
1170     TyF32,
1171     TyF64,
1172 }
1173
1174 impl fmt::Show for FloatTy {
1175     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1176         fmt::String::fmt(self, f)
1177     }
1178 }
1179
1180 impl fmt::String for FloatTy {
1181     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1182         write!(f, "{}", ast_util::float_ty_to_string(*self))
1183     }
1184 }
1185
1186 impl FloatTy {
1187     pub fn suffix_len(&self) -> uint {
1188         match *self {
1189             TyF32 | TyF64 => 3, // add F128 handling here
1190         }
1191     }
1192 }
1193
1194 // Bind a type to an associated type: `A=Foo`.
1195 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1196 pub struct TypeBinding {
1197     pub id: NodeId,
1198     pub ident: Ident,
1199     pub ty: P<Ty>,
1200     pub span: Span,
1201 }
1202
1203
1204 // NB PartialEq method appears below.
1205 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1206 pub struct Ty {
1207     pub id: NodeId,
1208     pub node: Ty_,
1209     pub span: Span,
1210 }
1211
1212 /// Not represented directly in the AST, referred to by name through a ty_path.
1213 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show, Copy)]
1214 pub enum PrimTy {
1215     TyInt(IntTy),
1216     TyUint(UintTy),
1217     TyFloat(FloatTy),
1218     TyStr,
1219     TyBool,
1220     TyChar
1221 }
1222
1223 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Copy)]
1224 pub enum Onceness {
1225     Once,
1226     Many
1227 }
1228
1229 impl fmt::Show for Onceness {
1230     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1231         fmt::String::fmt(match *self {
1232             Once => "once",
1233             Many => "many",
1234         }, f)
1235     }
1236 }
1237
1238 impl fmt::String for Onceness {
1239     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1240         fmt::String::fmt(match *self {
1241             Once => "once",
1242             Many => "many",
1243         }, f)
1244     }
1245 }
1246
1247 /// Represents the type of a closure
1248 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1249 pub struct ClosureTy {
1250     pub lifetimes: Vec<LifetimeDef>,
1251     pub unsafety: Unsafety,
1252     pub onceness: Onceness,
1253     pub decl: P<FnDecl>,
1254     pub bounds: TyParamBounds,
1255 }
1256
1257 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1258 pub struct BareFnTy {
1259     pub unsafety: Unsafety,
1260     pub abi: Abi,
1261     pub lifetimes: Vec<LifetimeDef>,
1262     pub decl: P<FnDecl>
1263 }
1264
1265 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1266 /// The different kinds of types recognized by the compiler
1267 pub enum Ty_ {
1268     TyVec(P<Ty>),
1269     /// A fixed length array (`[T, ..n]`)
1270     TyFixedLengthVec(P<Ty>, P<Expr>),
1271     /// A raw pointer (`*const T` or `*mut T`)
1272     TyPtr(MutTy),
1273     /// A reference (`&'a T` or `&'a mut T`)
1274     TyRptr(Option<Lifetime>, MutTy),
1275     /// A bare function (e.g. `fn(uint) -> bool`)
1276     TyBareFn(P<BareFnTy>),
1277     /// A tuple (`(A, B, C, D,...)`)
1278     TyTup(Vec<P<Ty>> ),
1279     /// A path (`module::module::...::Type`) or primitive
1280     ///
1281     /// Type parameters are stored in the Path itself
1282     TyPath(Path, NodeId),
1283     /// Something like `A+B`. Note that `B` must always be a path.
1284     TyObjectSum(P<Ty>, TyParamBounds),
1285     /// A type like `for<'a> Foo<&'a Bar>`
1286     TyPolyTraitRef(TyParamBounds),
1287     /// A "qualified path", e.g. `<Vec<T> as SomeTrait>::SomeType`
1288     TyQPath(P<QPath>),
1289     /// No-op; kept solely so that we can pretty-print faithfully
1290     TyParen(P<Ty>),
1291     /// Unused for now
1292     TyTypeof(P<Expr>),
1293     /// TyInfer means the type should be inferred instead of it having been
1294     /// specified. This can appear anywhere in a type.
1295     TyInfer,
1296 }
1297
1298 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show, Copy)]
1299 pub enum AsmDialect {
1300     AsmAtt,
1301     AsmIntel
1302 }
1303
1304 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1305 pub struct InlineAsm {
1306     pub asm: InternedString,
1307     pub asm_str_style: StrStyle,
1308     pub outputs: Vec<(InternedString, P<Expr>, bool)>,
1309     pub inputs: Vec<(InternedString, P<Expr>)>,
1310     pub clobbers: Vec<InternedString>,
1311     pub volatile: bool,
1312     pub alignstack: bool,
1313     pub dialect: AsmDialect,
1314     pub expn_id: ExpnId,
1315 }
1316
1317 /// represents an argument in a function header
1318 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1319 pub struct Arg {
1320     pub ty: P<Ty>,
1321     pub pat: P<Pat>,
1322     pub id: NodeId,
1323 }
1324
1325 impl Arg {
1326     pub fn new_self(span: Span, mutability: Mutability, self_ident: Ident) -> Arg {
1327         let path = Spanned{span:span,node:self_ident};
1328         Arg {
1329             // HACK(eddyb) fake type for the self argument.
1330             ty: P(Ty {
1331                 id: DUMMY_NODE_ID,
1332                 node: TyInfer,
1333                 span: DUMMY_SP,
1334             }),
1335             pat: P(Pat {
1336                 id: DUMMY_NODE_ID,
1337                 node: PatIdent(BindByValue(mutability), path, None),
1338                 span: span
1339             }),
1340             id: DUMMY_NODE_ID
1341         }
1342     }
1343 }
1344
1345 /// represents the header (not the body) of a function declaration
1346 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1347 pub struct FnDecl {
1348     pub inputs: Vec<Arg>,
1349     pub output: FunctionRetTy,
1350     pub variadic: bool
1351 }
1352
1353 #[derive(Copy, Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1354 pub enum Unsafety {
1355     Unsafe,
1356     Normal,
1357 }
1358
1359 impl fmt::String for Unsafety {
1360     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1361         fmt::String::fmt(match *self {
1362             Unsafety::Normal => "normal",
1363             Unsafety::Unsafe => "unsafe",
1364         }, f)
1365     }
1366 }
1367
1368 #[derive(Copy, Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash)]
1369 pub enum ImplPolarity {
1370     /// impl Trait for Type
1371     Positive,
1372     /// impl !Trait for Type
1373     Negative,
1374 }
1375
1376 impl fmt::Show for ImplPolarity {
1377     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1378         match *self {
1379             ImplPolarity::Positive => "positive".fmt(f),
1380             ImplPolarity::Negative => "negative".fmt(f),
1381         }
1382     }
1383 }
1384
1385
1386 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1387 pub enum FunctionRetTy {
1388     /// Functions with return type ! that always
1389     /// raise an error or exit (i.e. never return to the caller)
1390     NoReturn(Span),
1391     /// Everything else
1392     Return(P<Ty>),
1393 }
1394
1395 impl FunctionRetTy {
1396     pub fn span(&self) -> Span {
1397         match *self {
1398             NoReturn(span) => span,
1399             Return(ref ty) => ty.span
1400         }
1401     }
1402 }
1403
1404 /// Represents the kind of 'self' associated with a method
1405 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1406 pub enum ExplicitSelf_ {
1407     /// No self
1408     SelfStatic,
1409     /// `self`
1410     SelfValue(Ident),
1411     /// `&'lt self`, `&'lt mut self`
1412     SelfRegion(Option<Lifetime>, Mutability, Ident),
1413     /// `self: TYPE`
1414     SelfExplicit(P<Ty>, Ident),
1415 }
1416
1417 pub type ExplicitSelf = Spanned<ExplicitSelf_>;
1418
1419 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1420 pub struct Method {
1421     pub attrs: Vec<Attribute>,
1422     pub id: NodeId,
1423     pub span: Span,
1424     pub node: Method_,
1425 }
1426
1427 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1428 pub enum Method_ {
1429     /// Represents a method declaration
1430     MethDecl(Ident,
1431              Generics,
1432              Abi,
1433              ExplicitSelf,
1434              Unsafety,
1435              P<FnDecl>,
1436              P<Block>,
1437              Visibility),
1438     /// Represents a macro in method position
1439     MethMac(Mac),
1440 }
1441
1442 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1443 pub struct Mod {
1444     /// A span from the first token past `{` to the last token until `}`.
1445     /// For `mod foo;`, the inner span ranges from the first token
1446     /// to the last token in the external file.
1447     pub inner: Span,
1448     pub view_items: Vec<ViewItem>,
1449     pub items: Vec<P<Item>>,
1450 }
1451
1452 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1453 pub struct ForeignMod {
1454     pub abi: Abi,
1455     pub view_items: Vec<ViewItem>,
1456     pub items: Vec<P<ForeignItem>>,
1457 }
1458
1459 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1460 pub struct VariantArg {
1461     pub ty: P<Ty>,
1462     pub id: NodeId,
1463 }
1464
1465 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1466 pub enum VariantKind {
1467     TupleVariantKind(Vec<VariantArg>),
1468     StructVariantKind(P<StructDef>),
1469 }
1470
1471 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1472 pub struct EnumDef {
1473     pub variants: Vec<P<Variant>>,
1474 }
1475
1476 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1477 pub struct Variant_ {
1478     pub name: Ident,
1479     pub attrs: Vec<Attribute>,
1480     pub kind: VariantKind,
1481     pub id: NodeId,
1482     pub disr_expr: Option<P<Expr>>,
1483     pub vis: Visibility,
1484 }
1485
1486 pub type Variant = Spanned<Variant_>;
1487
1488 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show, Copy)]
1489 pub enum PathListItem_ {
1490     PathListIdent { name: Ident, id: NodeId },
1491     PathListMod { id: NodeId }
1492 }
1493
1494 impl PathListItem_ {
1495     pub fn id(&self) -> NodeId {
1496         match *self {
1497             PathListIdent { id, .. } | PathListMod { id } => id
1498         }
1499     }
1500 }
1501
1502 pub type PathListItem = Spanned<PathListItem_>;
1503
1504 pub type ViewPath = Spanned<ViewPath_>;
1505
1506 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1507 pub enum ViewPath_ {
1508
1509     /// `foo::bar::baz as quux`
1510     ///
1511     /// or just
1512     ///
1513     /// `foo::bar::baz` (with `as baz` implicitly on the right)
1514     ViewPathSimple(Ident, Path, NodeId),
1515
1516     /// `foo::bar::*`
1517     ViewPathGlob(Path, NodeId),
1518
1519     /// `foo::bar::{a,b,c}`
1520     ViewPathList(Path, Vec<PathListItem> , NodeId)
1521 }
1522
1523 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1524 pub struct ViewItem {
1525     pub node: ViewItem_,
1526     pub attrs: Vec<Attribute>,
1527     pub vis: Visibility,
1528     pub span: Span,
1529 }
1530
1531 impl ViewItem {
1532     pub fn id(&self) -> NodeId {
1533         match self.node {
1534             ViewItemExternCrate(_, _, id) => id,
1535             ViewItemUse(ref vp) => match vp.node {
1536                 ViewPathSimple(_, _, id) => id,
1537                 ViewPathGlob(_, id) => id,
1538                 ViewPathList(_, _, id) => id,
1539             }
1540         }
1541     }
1542 }
1543
1544 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1545 pub enum ViewItem_ {
1546     /// Ident: name used to refer to this crate in the code
1547     /// optional (InternedString,StrStyle): if present, this is a location
1548     /// (containing arbitrary characters) from which to fetch the crate sources
1549     /// For example, extern crate whatever = "github.com/rust-lang/rust"
1550     ViewItemExternCrate(Ident, Option<(InternedString,StrStyle)>, NodeId),
1551     ViewItemUse(P<ViewPath>),
1552 }
1553
1554 /// Meta-data associated with an item
1555 pub type Attribute = Spanned<Attribute_>;
1556
1557 /// Distinguishes between Attributes that decorate items and Attributes that
1558 /// are contained as statements within items. These two cases need to be
1559 /// distinguished for pretty-printing.
1560 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show, Copy)]
1561 pub enum AttrStyle {
1562     AttrOuter,
1563     AttrInner,
1564 }
1565
1566 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show, Copy)]
1567 pub struct AttrId(pub uint);
1568
1569 /// Doc-comments are promoted to attributes that have is_sugared_doc = true
1570 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1571 pub struct Attribute_ {
1572     pub id: AttrId,
1573     pub style: AttrStyle,
1574     pub value: P<MetaItem>,
1575     pub is_sugared_doc: bool,
1576 }
1577
1578 /// TraitRef's appear in impls.
1579 /// resolve maps each TraitRef's ref_id to its defining trait; that's all
1580 /// that the ref_id is for. The impl_id maps to the "self type" of this impl.
1581 /// If this impl is an ItemImpl, the impl_id is redundant (it could be the
1582 /// same as the impl's node id).
1583 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1584 pub struct TraitRef {
1585     pub path: Path,
1586     pub ref_id: NodeId,
1587 }
1588
1589 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1590 pub struct PolyTraitRef {
1591     /// The `'a` in `<'a> Foo<&'a T>`
1592     pub bound_lifetimes: Vec<LifetimeDef>,
1593
1594     /// The `Foo<&'a T>` in `<'a> Foo<&'a T>`
1595     pub trait_ref: TraitRef,
1596 }
1597
1598 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show, Copy)]
1599 pub enum Visibility {
1600     Public,
1601     Inherited,
1602 }
1603
1604 impl Visibility {
1605     pub fn inherit_from(&self, parent_visibility: Visibility) -> Visibility {
1606         match self {
1607             &Inherited => parent_visibility,
1608             &Public => *self
1609         }
1610     }
1611 }
1612
1613 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1614 pub struct StructField_ {
1615     pub kind: StructFieldKind,
1616     pub id: NodeId,
1617     pub ty: P<Ty>,
1618     pub attrs: Vec<Attribute>,
1619 }
1620
1621 impl StructField_ {
1622     pub fn ident(&self) -> Option<Ident> {
1623         match self.kind {
1624             NamedField(ref ident, _) => Some(ident.clone()),
1625             UnnamedField(_) => None
1626         }
1627     }
1628 }
1629
1630 pub type StructField = Spanned<StructField_>;
1631
1632 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show, Copy)]
1633 pub enum StructFieldKind {
1634     NamedField(Ident, Visibility),
1635     /// Element of a tuple-like struct
1636     UnnamedField(Visibility),
1637 }
1638
1639 impl StructFieldKind {
1640     pub fn is_unnamed(&self) -> bool {
1641         match *self {
1642             UnnamedField(..) => true,
1643             NamedField(..) => false,
1644         }
1645     }
1646 }
1647
1648 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1649 pub struct StructDef {
1650     /// Fields, not including ctor
1651     pub fields: Vec<StructField>,
1652     /// ID of the constructor. This is only used for tuple- or enum-like
1653     /// structs.
1654     pub ctor_id: Option<NodeId>,
1655 }
1656
1657 /*
1658   FIXME (#3300): Should allow items to be anonymous. Right now
1659   we just use dummy names for anon items.
1660  */
1661 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1662 pub struct Item {
1663     pub ident: Ident,
1664     pub attrs: Vec<Attribute>,
1665     pub id: NodeId,
1666     pub node: Item_,
1667     pub vis: Visibility,
1668     pub span: Span,
1669 }
1670
1671 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1672 pub enum Item_ {
1673     ItemStatic(P<Ty>, Mutability, P<Expr>),
1674     ItemConst(P<Ty>, P<Expr>),
1675     ItemFn(P<FnDecl>, Unsafety, Abi, Generics, P<Block>),
1676     ItemMod(Mod),
1677     ItemForeignMod(ForeignMod),
1678     ItemTy(P<Ty>, Generics),
1679     ItemEnum(EnumDef, Generics),
1680     ItemStruct(P<StructDef>, Generics),
1681     /// Represents a Trait Declaration
1682     ItemTrait(Unsafety,
1683               Generics,
1684               TyParamBounds,
1685               Vec<TraitItem>),
1686     ItemImpl(Unsafety,
1687              ImplPolarity,
1688              Generics,
1689              Option<TraitRef>, // (optional) trait this impl implements
1690              P<Ty>, // self
1691              Vec<ImplItem>),
1692     /// A macro invocation (which includes macro definition)
1693     ItemMac(Mac),
1694 }
1695
1696 impl Item_ {
1697     pub fn descriptive_variant(&self) -> &str {
1698         match *self {
1699             ItemStatic(..) => "static item",
1700             ItemConst(..) => "constant item",
1701             ItemFn(..) => "function",
1702             ItemMod(..) => "module",
1703             ItemForeignMod(..) => "foreign module",
1704             ItemTy(..) => "type alias",
1705             ItemEnum(..) => "enum",
1706             ItemStruct(..) => "struct",
1707             ItemTrait(..) => "trait",
1708             ItemMac(..) |
1709             ItemImpl(..) => "item"
1710         }
1711     }
1712 }
1713
1714 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1715 pub struct ForeignItem {
1716     pub ident: Ident,
1717     pub attrs: Vec<Attribute>,
1718     pub node: ForeignItem_,
1719     pub id: NodeId,
1720     pub span: Span,
1721     pub vis: Visibility,
1722 }
1723
1724 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1725 pub enum ForeignItem_ {
1726     ForeignItemFn(P<FnDecl>, Generics),
1727     ForeignItemStatic(P<Ty>, /* is_mutbl */ bool),
1728 }
1729
1730 impl ForeignItem_ {
1731     pub fn descriptive_variant(&self) -> &str {
1732         match *self {
1733             ForeignItemFn(..) => "foreign function",
1734             ForeignItemStatic(..) => "foreign static item"
1735         }
1736     }
1737 }
1738
1739 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show, Copy)]
1740 pub enum UnboxedClosureKind {
1741     FnUnboxedClosureKind,
1742     FnMutUnboxedClosureKind,
1743     FnOnceUnboxedClosureKind,
1744 }
1745
1746 /// The data we save and restore about an inlined item or method.  This is not
1747 /// part of the AST that we parse from a file, but it becomes part of the tree
1748 /// that we trans.
1749 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1750 pub enum InlinedItem {
1751     IIItem(P<Item>),
1752     IITraitItem(DefId /* impl id */, TraitItem),
1753     IIImplItem(DefId /* impl id */, ImplItem),
1754     IIForeign(P<ForeignItem>),
1755 }
1756
1757 /// A macro definition, in this crate or imported from another.
1758 ///
1759 /// Not parsed directly, but created on macro import or `macro_rules!` expansion.
1760 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1761 pub struct MacroDef {
1762     pub ident: Ident,
1763     pub attrs: Vec<Attribute>,
1764     pub id: NodeId,
1765     pub span: Span,
1766     pub imported_from: Option<Ident>,
1767     pub export: bool,
1768     pub use_locally: bool,
1769     pub body: Vec<TokenTree>,
1770 }
1771
1772 #[cfg(test)]
1773 mod test {
1774     use serialize;
1775     use super::*;
1776
1777     // are ASTs encodable?
1778     #[test]
1779     fn check_asts_encodable() {
1780         fn assert_encodable<T: serialize::Encodable>() {}
1781         assert_encodable::<Crate>();
1782     }
1783 }