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