src/libsyntax/ast.rs

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