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.usize(),
  99                 self.ctxt)
 100     }
 101 }
 102
 103 impl fmt::Debug 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::Display for Ident {
 110     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 111         fmt::Display::fmt(&self.name, f)
 112     }
 113 }
 114
 115 impl fmt::Debug 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::Display for Name {
 123     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 124         fmt::Display::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 usize
 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 usize(&self) -> usize {
 185         let Name(nm) = *self;
 186         nm as usize
 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<usize>),
 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: usize,
 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) -> usize {
 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: usize) -> 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(usize)
 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) -> usize {
 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::Debug for IntTy {
1104     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1105         fmt::Display::fmt(self, f)
1106     }
1107 }
1108
1109 impl fmt::Display 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) -> usize {
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) -> usize {
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::Debug for UintTy {
1159     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1160         fmt::Display::fmt(self, f)
1161     }
1162 }
1163
1164 impl fmt::Display 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::Debug for FloatTy {
1177     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1178         fmt::Display::fmt(self, f)
1179     }
1180 }
1181
1182 impl fmt::Display 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) -> usize {
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, Show)]
1226 pub enum Onceness {
1227     Once,
1228     Many
1229 }
1230
1231 impl fmt::Display for Onceness {
1232     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1233         fmt::Display::fmt(match *self {
1234             Once => "once",
1235             Many => "many",
1236         }, f)
1237     }
1238 }
1239
1240 /// Represents the type of a closure
1241 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1242 pub struct ClosureTy {
1243     pub lifetimes: Vec<LifetimeDef>,
1244     pub unsafety: Unsafety,
1245     pub onceness: Onceness,
1246     pub decl: P<FnDecl>,
1247     pub bounds: TyParamBounds,
1248 }
1249
1250 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1251 pub struct BareFnTy {
1252     pub unsafety: Unsafety,
1253     pub abi: Abi,
1254     pub lifetimes: Vec<LifetimeDef>,
1255     pub decl: P<FnDecl>
1256 }
1257
1258 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1259 /// The different kinds of types recognized by the compiler
1260 pub enum Ty_ {
1261     TyVec(P<Ty>),
1262     /// A fixed length array (`[T, ..n]`)
1263     TyFixedLengthVec(P<Ty>, P<Expr>),
1264     /// A raw pointer (`*const T` or `*mut T`)
1265     TyPtr(MutTy),
1266     /// A reference (`&'a T` or `&'a mut T`)
1267     TyRptr(Option<Lifetime>, MutTy),
1268     /// A bare function (e.g. `fn(usize) -> bool`)
1269     TyBareFn(P<BareFnTy>),
1270     /// A tuple (`(A, B, C, D,...)`)
1271     TyTup(Vec<P<Ty>> ),
1272     /// A path (`module::module::...::Type`) or primitive
1273     ///
1274     /// Type parameters are stored in the Path itself
1275     TyPath(Path, NodeId),
1276     /// Something like `A+B`. Note that `B` must always be a path.
1277     TyObjectSum(P<Ty>, TyParamBounds),
1278     /// A type like `for<'a> Foo<&'a Bar>`
1279     TyPolyTraitRef(TyParamBounds),
1280     /// A "qualified path", e.g. `<Vec<T> as SomeTrait>::SomeType`
1281     TyQPath(P<QPath>),
1282     /// No-op; kept solely so that we can pretty-print faithfully
1283     TyParen(P<Ty>),
1284     /// Unused for now
1285     TyTypeof(P<Expr>),
1286     /// TyInfer means the type should be inferred instead of it having been
1287     /// specified. This can appear anywhere in a type.
1288     TyInfer,
1289 }
1290
1291 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show, Copy)]
1292 pub enum AsmDialect {
1293     AsmAtt,
1294     AsmIntel
1295 }
1296
1297 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1298 pub struct InlineAsm {
1299     pub asm: InternedString,
1300     pub asm_str_style: StrStyle,
1301     pub outputs: Vec<(InternedString, P<Expr>, bool)>,
1302     pub inputs: Vec<(InternedString, P<Expr>)>,
1303     pub clobbers: Vec<InternedString>,
1304     pub volatile: bool,
1305     pub alignstack: bool,
1306     pub dialect: AsmDialect,
1307     pub expn_id: ExpnId,
1308 }
1309
1310 /// represents an argument in a function header
1311 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1312 pub struct Arg {
1313     pub ty: P<Ty>,
1314     pub pat: P<Pat>,
1315     pub id: NodeId,
1316 }
1317
1318 impl Arg {
1319     pub fn new_self(span: Span, mutability: Mutability, self_ident: Ident) -> Arg {
1320         let path = Spanned{span:span,node:self_ident};
1321         Arg {
1322             // HACK(eddyb) fake type for the self argument.
1323             ty: P(Ty {
1324                 id: DUMMY_NODE_ID,
1325                 node: TyInfer,
1326                 span: DUMMY_SP,
1327             }),
1328             pat: P(Pat {
1329                 id: DUMMY_NODE_ID,
1330                 node: PatIdent(BindByValue(mutability), path, None),
1331                 span: span
1332             }),
1333             id: DUMMY_NODE_ID
1334         }
1335     }
1336 }
1337
1338 /// represents the header (not the body) of a function declaration
1339 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1340 pub struct FnDecl {
1341     pub inputs: Vec<Arg>,
1342     pub output: FunctionRetTy,
1343     pub variadic: bool
1344 }
1345
1346 #[derive(Copy, Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1347 pub enum Unsafety {
1348     Unsafe,
1349     Normal,
1350 }
1351
1352 impl fmt::Display for Unsafety {
1353     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1354         fmt::Display::fmt(match *self {
1355             Unsafety::Normal => "normal",
1356             Unsafety::Unsafe => "unsafe",
1357         }, f)
1358     }
1359 }
1360
1361 #[derive(Copy, Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash)]
1362 pub enum ImplPolarity {
1363     /// impl Trait for Type
1364     Positive,
1365     /// impl !Trait for Type
1366     Negative,
1367 }
1368
1369 impl fmt::Debug for ImplPolarity {
1370     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
1371         match *self {
1372             ImplPolarity::Positive => "positive".fmt(f),
1373             ImplPolarity::Negative => "negative".fmt(f),
1374         }
1375     }
1376 }
1377
1378
1379 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1380 pub enum FunctionRetTy {
1381     /// Functions with return type ! that always
1382     /// raise an error or exit (i.e. never return to the caller)
1383     NoReturn(Span),
1384     /// Return type is not specified. Functions default to () and
1385     /// closures default to inference. Span points to where return
1386     /// type would be inserted.
1387     DefaultReturn(Span),
1388     /// Everything else
1389     Return(P<Ty>),
1390 }
1391
1392 impl FunctionRetTy {
1393     pub fn span(&self) -> Span {
1394         match *self {
1395             NoReturn(span) => span,
1396             DefaultReturn(span) => span,
1397             Return(ref ty) => ty.span
1398         }
1399     }
1400 }
1401
1402 /// Represents the kind of 'self' associated with a method
1403 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1404 pub enum ExplicitSelf_ {
1405     /// No self
1406     SelfStatic,
1407     /// `self`
1408     SelfValue(Ident),
1409     /// `&'lt self`, `&'lt mut self`
1410     SelfRegion(Option<Lifetime>, Mutability, Ident),
1411     /// `self: TYPE`
1412     SelfExplicit(P<Ty>, Ident),
1413 }
1414
1415 pub type ExplicitSelf = Spanned<ExplicitSelf_>;
1416
1417 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1418 pub struct Method {
1419     pub attrs: Vec<Attribute>,
1420     pub id: NodeId,
1421     pub span: Span,
1422     pub node: Method_,
1423 }
1424
1425 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1426 pub enum Method_ {
1427     /// Represents a method declaration
1428     MethDecl(Ident,
1429              Generics,
1430              Abi,
1431              ExplicitSelf,
1432              Unsafety,
1433              P<FnDecl>,
1434              P<Block>,
1435              Visibility),
1436     /// Represents a macro in method position
1437     MethMac(Mac),
1438 }
1439
1440 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1441 pub struct Mod {
1442     /// A span from the first token past `{` to the last token until `}`.
1443     /// For `mod foo;`, the inner span ranges from the first token
1444     /// to the last token in the external file.
1445     pub inner: Span,
1446     pub view_items: Vec<ViewItem>,
1447     pub items: Vec<P<Item>>,
1448 }
1449
1450 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1451 pub struct ForeignMod {
1452     pub abi: Abi,
1453     pub view_items: Vec<ViewItem>,
1454     pub items: Vec<P<ForeignItem>>,
1455 }
1456
1457 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1458 pub struct VariantArg {
1459     pub ty: P<Ty>,
1460     pub id: NodeId,
1461 }
1462
1463 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1464 pub enum VariantKind {
1465     TupleVariantKind(Vec<VariantArg>),
1466     StructVariantKind(P<StructDef>),
1467 }
1468
1469 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1470 pub struct EnumDef {
1471     pub variants: Vec<P<Variant>>,
1472 }
1473
1474 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1475 pub struct Variant_ {
1476     pub name: Ident,
1477     pub attrs: Vec<Attribute>,
1478     pub kind: VariantKind,
1479     pub id: NodeId,
1480     pub disr_expr: Option<P<Expr>>,
1481     pub vis: Visibility,
1482 }
1483
1484 pub type Variant = Spanned<Variant_>;
1485
1486 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show, Copy)]
1487 pub enum PathListItem_ {
1488     PathListIdent { name: Ident, id: NodeId },
1489     PathListMod { id: NodeId }
1490 }
1491
1492 impl PathListItem_ {
1493     pub fn id(&self) -> NodeId {
1494         match *self {
1495             PathListIdent { id, .. } | PathListMod { id } => id
1496         }
1497     }
1498 }
1499
1500 pub type PathListItem = Spanned<PathListItem_>;
1501
1502 pub type ViewPath = Spanned<ViewPath_>;
1503
1504 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1505 pub enum ViewPath_ {
1506
1507     /// `foo::bar::baz as quux`
1508     ///
1509     /// or just
1510     ///
1511     /// `foo::bar::baz` (with `as baz` implicitly on the right)
1512     ViewPathSimple(Ident, Path, NodeId),
1513
1514     /// `foo::bar::*`
1515     ViewPathGlob(Path, NodeId),
1516
1517     /// `foo::bar::{a,b,c}`
1518     ViewPathList(Path, Vec<PathListItem> , NodeId)
1519 }
1520
1521 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1522 pub struct ViewItem {
1523     pub node: ViewItem_,
1524     pub attrs: Vec<Attribute>,
1525     pub vis: Visibility,
1526     pub span: Span,
1527 }
1528
1529 impl ViewItem {
1530     pub fn id(&self) -> NodeId {
1531         match self.node {
1532             ViewItemExternCrate(_, _, id) => id,
1533             ViewItemUse(ref vp) => match vp.node {
1534                 ViewPathSimple(_, _, id) => id,
1535                 ViewPathGlob(_, id) => id,
1536                 ViewPathList(_, _, id) => id,
1537             }
1538         }
1539     }
1540 }
1541
1542 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1543 pub enum ViewItem_ {
1544     /// Ident: name used to refer to this crate in the code
1545     /// optional (InternedString,StrStyle): if present, this is a location
1546     /// (containing arbitrary characters) from which to fetch the crate sources
1547     /// For example, extern crate whatever = "github.com/rust-lang/rust"
1548     ViewItemExternCrate(Ident, Option<(InternedString,StrStyle)>, NodeId),
1549     ViewItemUse(P<ViewPath>),
1550 }
1551
1552 /// Meta-data associated with an item
1553 pub type Attribute = Spanned<Attribute_>;
1554
1555 /// Distinguishes between Attributes that decorate items and Attributes that
1556 /// are contained as statements within items. These two cases need to be
1557 /// distinguished for pretty-printing.
1558 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show, Copy)]
1559 pub enum AttrStyle {
1560     AttrOuter,
1561     AttrInner,
1562 }
1563
1564 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show, Copy)]
1565 pub struct AttrId(pub usize);
1566
1567 /// Doc-comments are promoted to attributes that have is_sugared_doc = true
1568 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1569 pub struct Attribute_ {
1570     pub id: AttrId,
1571     pub style: AttrStyle,
1572     pub value: P<MetaItem>,
1573     pub is_sugared_doc: bool,
1574 }
1575
1576 /// TraitRef's appear in impls.
1577 /// resolve maps each TraitRef's ref_id to its defining trait; that's all
1578 /// that the ref_id is for. The impl_id maps to the "self type" of this impl.
1579 /// If this impl is an ItemImpl, the impl_id is redundant (it could be the
1580 /// same as the impl's node id).
1581 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1582 pub struct TraitRef {
1583     pub path: Path,
1584     pub ref_id: NodeId,
1585 }
1586
1587 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1588 pub struct PolyTraitRef {
1589     /// The `'a` in `<'a> Foo<&'a T>`
1590     pub bound_lifetimes: Vec<LifetimeDef>,
1591
1592     /// The `Foo<&'a T>` in `<'a> Foo<&'a T>`
1593     pub trait_ref: TraitRef,
1594 }
1595
1596 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show, Copy)]
1597 pub enum Visibility {
1598     Public,
1599     Inherited,
1600 }
1601
1602 impl Visibility {
1603     pub fn inherit_from(&self, parent_visibility: Visibility) -> Visibility {
1604         match self {
1605             &Inherited => parent_visibility,
1606             &Public => *self
1607         }
1608     }
1609 }
1610
1611 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1612 pub struct StructField_ {
1613     pub kind: StructFieldKind,
1614     pub id: NodeId,
1615     pub ty: P<Ty>,
1616     pub attrs: Vec<Attribute>,
1617 }
1618
1619 impl StructField_ {
1620     pub fn ident(&self) -> Option<Ident> {
1621         match self.kind {
1622             NamedField(ref ident, _) => Some(ident.clone()),
1623             UnnamedField(_) => None
1624         }
1625     }
1626 }
1627
1628 pub type StructField = Spanned<StructField_>;
1629
1630 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show, Copy)]
1631 pub enum StructFieldKind {
1632     NamedField(Ident, Visibility),
1633     /// Element of a tuple-like struct
1634     UnnamedField(Visibility),
1635 }
1636
1637 impl StructFieldKind {
1638     pub fn is_unnamed(&self) -> bool {
1639         match *self {
1640             UnnamedField(..) => true,
1641             NamedField(..) => false,
1642         }
1643     }
1644 }
1645
1646 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1647 pub struct StructDef {
1648     /// Fields, not including ctor
1649     pub fields: Vec<StructField>,
1650     /// ID of the constructor. This is only used for tuple- or enum-like
1651     /// structs.
1652     pub ctor_id: Option<NodeId>,
1653 }
1654
1655 /*
1656   FIXME (#3300): Should allow items to be anonymous. Right now
1657   we just use dummy names for anon items.
1658  */
1659 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1660 pub struct Item {
1661     pub ident: Ident,
1662     pub attrs: Vec<Attribute>,
1663     pub id: NodeId,
1664     pub node: Item_,
1665     pub vis: Visibility,
1666     pub span: Span,
1667 }
1668
1669 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1670 pub enum Item_ {
1671     ItemStatic(P<Ty>, Mutability, P<Expr>),
1672     ItemConst(P<Ty>, P<Expr>),
1673     ItemFn(P<FnDecl>, Unsafety, Abi, Generics, P<Block>),
1674     ItemMod(Mod),
1675     ItemForeignMod(ForeignMod),
1676     ItemTy(P<Ty>, Generics),
1677     ItemEnum(EnumDef, Generics),
1678     ItemStruct(P<StructDef>, Generics),
1679     /// Represents a Trait Declaration
1680     ItemTrait(Unsafety,
1681               Generics,
1682               TyParamBounds,
1683               Vec<TraitItem>),
1684     ItemImpl(Unsafety,
1685              ImplPolarity,
1686              Generics,
1687              Option<TraitRef>, // (optional) trait this impl implements
1688              P<Ty>, // self
1689              Vec<ImplItem>),
1690     /// A macro invocation (which includes macro definition)
1691     ItemMac(Mac),
1692 }
1693
1694 impl Item_ {
1695     pub fn descriptive_variant(&self) -> &str {
1696         match *self {
1697             ItemStatic(..) => "static item",
1698             ItemConst(..) => "constant item",
1699             ItemFn(..) => "function",
1700             ItemMod(..) => "module",
1701             ItemForeignMod(..) => "foreign module",
1702             ItemTy(..) => "type alias",
1703             ItemEnum(..) => "enum",
1704             ItemStruct(..) => "struct",
1705             ItemTrait(..) => "trait",
1706             ItemMac(..) |
1707             ItemImpl(..) => "item"
1708         }
1709     }
1710 }
1711
1712 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1713 pub struct ForeignItem {
1714     pub ident: Ident,
1715     pub attrs: Vec<Attribute>,
1716     pub node: ForeignItem_,
1717     pub id: NodeId,
1718     pub span: Span,
1719     pub vis: Visibility,
1720 }
1721
1722 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1723 pub enum ForeignItem_ {
1724     ForeignItemFn(P<FnDecl>, Generics),
1725     ForeignItemStatic(P<Ty>, /* is_mutbl */ bool),
1726 }
1727
1728 impl ForeignItem_ {
1729     pub fn descriptive_variant(&self) -> &str {
1730         match *self {
1731             ForeignItemFn(..) => "foreign function",
1732             ForeignItemStatic(..) => "foreign static item"
1733         }
1734     }
1735 }
1736
1737 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show, Copy)]
1738 pub enum UnboxedClosureKind {
1739     FnUnboxedClosureKind,
1740     FnMutUnboxedClosureKind,
1741     FnOnceUnboxedClosureKind,
1742 }
1743
1744 /// The data we save and restore about an inlined item or method.  This is not
1745 /// part of the AST that we parse from a file, but it becomes part of the tree
1746 /// that we trans.
1747 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1748 pub enum InlinedItem {
1749     IIItem(P<Item>),
1750     IITraitItem(DefId /* impl id */, TraitItem),
1751     IIImplItem(DefId /* impl id */, ImplItem),
1752     IIForeign(P<ForeignItem>),
1753 }
1754
1755 /// A macro definition, in this crate or imported from another.
1756 ///
1757 /// Not parsed directly, but created on macro import or `macro_rules!` expansion.
1758 #[derive(Clone, PartialEq, Eq, RustcEncodable, RustcDecodable, Hash, Show)]
1759 pub struct MacroDef {
1760     pub ident: Ident,
1761     pub attrs: Vec<Attribute>,
1762     pub id: NodeId,
1763     pub span: Span,
1764     pub imported_from: Option<Ident>,
1765     pub export: bool,
1766     pub use_locally: bool,
1767     pub body: Vec<TokenTree>,
1768 }
1769
1770 #[cfg(test)]
1771 mod test {
1772     use serialize;
1773     use super::*;
1774
1775     // are ASTs encodable?
1776     #[test]
1777     fn check_asts_encodable() {
1778         fn assert_encodable<T: serialize::Encodable>() {}
1779         assert_encodable::<Crate>();
1780     }
1781 }