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