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 use codemap::{Span, Spanned, DUMMY_SP};
  14 use abi::Abi;
  15 use ast_util;
  16 use owned_slice::OwnedSlice;
  17 use parse::token::{InternedString, special_idents, str_to_ident};
  18 use parse::token;
  19
  20 use std::fmt;
  21 use std::fmt::Show;
  22 use std::option::Option;
  23 use std::rc::Rc;
  24 use std::gc::{Gc, GC};
  25 use serialize::{Encodable, Decodable, Encoder, Decoder};
  26
  27 /// A pointer abstraction. FIXME(eddyb) #10676 use Rc<T> in the future.
  28 pub type P<T> = Gc<T>;
  29
  30 #[allow(non_snake_case_functions)]
  31 /// Construct a P<T> from a T value.
  32 pub fn P<T: 'static>(value: T) -> P<T> {
  33     box(GC) value
  34 }
  35
  36 // FIXME #6993: in librustc, uses of "ident" should be replaced
  37 // by just "Name".
  38
  39 // an identifier contains a Name (index into the interner
  40 // table) and a SyntaxContext to track renaming and
  41 // macro expansion per Flatt et al., "Macros
  42 // That Work Together"
  43 #[deriving(Clone, Hash, PartialOrd, Eq, Ord, Show)]
  44 pub struct Ident {
  45     pub name: Name,
  46     pub ctxt: SyntaxContext
  47 }
  48
  49 impl Ident {
  50     /// Construct an identifier with the given name and an empty context:
  51     pub fn new(name: Name) -> Ident { Ident {name: name, ctxt: EMPTY_CTXT}}
  52 }
  53
  54 impl PartialEq for Ident {
  55     fn eq(&self, other: &Ident) -> bool {
  56         if self.ctxt == other.ctxt {
  57             self.name == other.name
  58         } else {
  59             // IF YOU SEE ONE OF THESE FAILS: it means that you're comparing
  60             // idents that have different contexts. You can't fix this without
  61             // knowing whether the comparison should be hygienic or non-hygienic.
  62             // if it should be non-hygienic (most things are), just compare the
  63             // 'name' fields of the idents. Or, even better, replace the idents
  64             // with Name's.
  65             //
  66             // On the other hand, if the comparison does need to be hygienic,
  67             // one example and its non-hygienic counterpart would be:
  68             //      syntax::parse::token::mtwt_token_eq
  69             //      syntax::ext::tt::macro_parser::token_name_eq
  70             fail!("not allowed to compare these idents: {:?}, {:?}. \
  71                    Probably related to issue \\#6993", self, other);
  72         }
  73     }
  74     fn ne(&self, other: &Ident) -> bool {
  75         ! self.eq(other)
  76     }
  77 }
  78
  79 /// A SyntaxContext represents a chain of macro-expandings
  80 /// and renamings. Each macro expansion corresponds to
  81 /// a fresh uint
  82
  83 // I'm representing this syntax context as an index into
  84 // a table, in order to work around a compiler bug
  85 // that's causing unreleased memory to cause core dumps
  86 // and also perhaps to save some work in destructor checks.
  87 // the special uint '0' will be used to indicate an empty
  88 // syntax context.
  89
  90 // this uint is a reference to a table stored in thread-local
  91 // storage.
  92 pub type SyntaxContext = u32;
  93 pub static EMPTY_CTXT : SyntaxContext = 0;
  94 pub static ILLEGAL_CTXT : SyntaxContext = 1;
  95
  96 /// A name is a part of an identifier, representing a string or gensym. It's
  97 /// the result of interning.
  98 pub type Name = u32;
  99
 100 /// A mark represents a unique id associated with a macro expansion
 101 pub type Mrk = u32;
 102
 103 impl<S: Encoder<E>, E> Encodable<S, E> for Ident {
 104     fn encode(&self, s: &mut S) -> Result<(), E> {
 105         s.emit_str(token::get_ident(*self).get())
 106     }
 107 }
 108
 109 impl<D:Decoder<E>, E> Decodable<D, E> for Ident {
 110     fn decode(d: &mut D) -> Result<Ident, E> {
 111         Ok(str_to_ident(try!(d.read_str()).as_slice()))
 112     }
 113 }
 114
 115 /// Function name (not all functions have names)
 116 pub type FnIdent = Option<Ident>;
 117
 118 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 119 pub struct Lifetime {
 120     pub id: NodeId,
 121     pub span: Span,
 122     pub name: Name
 123 }
 124
 125 // a "Path" is essentially Rust's notion of a name;
 126 // for instance: std::cmp::PartialEq  .  It's represented
 127 // as a sequence of identifiers, along with a bunch
 128 // of supporting information.
 129 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 130 pub struct Path {
 131     pub span: Span,
 132     /// A `::foo` path, is relative to the crate root rather than current
 133     /// module (like paths in an import).
 134     pub global: bool,
 135     /// The segments in the path: the things separated by `::`.
 136     pub segments: Vec<PathSegment> ,
 137 }
 138
 139 /// A segment of a path: an identifier, an optional lifetime, and a set of
 140 /// types.
 141 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 142 pub struct PathSegment {
 143     /// The identifier portion of this path segment.
 144     pub identifier: Ident,
 145     /// The lifetime parameters for this path segment.
 146     pub lifetimes: Vec<Lifetime>,
 147     /// The type parameters for this path segment, if present.
 148     pub types: OwnedSlice<P<Ty>>,
 149 }
 150
 151 pub type CrateNum = u32;
 152
 153 pub type NodeId = u32;
 154
 155 #[deriving(Clone, Eq, Ord, PartialOrd, PartialEq, Encodable, Decodable, Hash, Show)]
 156 pub struct DefId {
 157     pub krate: CrateNum,
 158     pub node: NodeId,
 159 }
 160
 161 /// Item definitions in the currently-compiled crate would have the CrateNum
 162 /// LOCAL_CRATE in their DefId.
 163 pub static LOCAL_CRATE: CrateNum = 0;
 164 pub static CRATE_NODE_ID: NodeId = 0;
 165
 166 // When parsing and doing expansions, we initially give all AST nodes this AST
 167 // node value. Then later, in the renumber pass, we renumber them to have
 168 // small, positive ids.
 169 pub static DUMMY_NODE_ID: NodeId = -1;
 170
 171 // The AST represents all type param bounds as types.
 172 // typeck::collect::compute_bounds matches these against
 173 // the "special" built-in traits (see middle::lang_items) and
 174 // detects Copy, Send and Share.
 175 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 176 pub enum TyParamBound {
 177     TraitTyParamBound(TraitRef),
 178     StaticRegionTyParamBound,
 179     UnboxedFnTyParamBound(UnboxedFnTy),
 180     OtherRegionTyParamBound(Span) // FIXME -- just here until work for #5723 lands
 181 }
 182
 183 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 184 pub struct TyParam {
 185     pub ident: Ident,
 186     pub id: NodeId,
 187     pub bounds: OwnedSlice<TyParamBound>,
 188     pub unbound: Option<TyParamBound>,
 189     pub default: Option<P<Ty>>,
 190     pub span: Span
 191 }
 192
 193 /// Represents lifetimes and type parameters attached to a declaration
 194 /// of a function, enum, trait, etc.
 195 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 196 pub struct Generics {
 197     pub lifetimes: Vec<Lifetime>,
 198     pub ty_params: OwnedSlice<TyParam>,
 199 }
 200
 201 impl Generics {
 202     pub fn is_parameterized(&self) -> bool {
 203         self.lifetimes.len() + self.ty_params.len() > 0
 204     }
 205     pub fn is_lt_parameterized(&self) -> bool {
 206         self.lifetimes.len() > 0
 207     }
 208     pub fn is_type_parameterized(&self) -> bool {
 209         self.ty_params.len() > 0
 210     }
 211 }
 212
 213 // The set of MetaItems that define the compilation environment of the crate,
 214 // used to drive conditional compilation
 215 pub type CrateConfig = Vec<Gc<MetaItem>>;
 216
 217 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 218 pub struct Crate {
 219     pub module: Mod,
 220     pub attrs: Vec<Attribute>,
 221     pub config: CrateConfig,
 222     pub span: Span,
 223 }
 224
 225 pub type MetaItem = Spanned<MetaItem_>;
 226
 227 #[deriving(Clone, Encodable, Decodable, Eq, Hash)]
 228 pub enum MetaItem_ {
 229     MetaWord(InternedString),
 230     MetaList(InternedString, Vec<Gc<MetaItem>>),
 231     MetaNameValue(InternedString, Lit),
 232 }
 233
 234 // can't be derived because the MetaList requires an unordered comparison
 235 impl PartialEq for MetaItem_ {
 236     fn eq(&self, other: &MetaItem_) -> bool {
 237         match *self {
 238             MetaWord(ref ns) => match *other {
 239                 MetaWord(ref no) => (*ns) == (*no),
 240                 _ => false
 241             },
 242             MetaNameValue(ref ns, ref vs) => match *other {
 243                 MetaNameValue(ref no, ref vo) => {
 244                     (*ns) == (*no) && vs.node == vo.node
 245                 }
 246                 _ => false
 247             },
 248             MetaList(ref ns, ref miss) => match *other {
 249                 MetaList(ref no, ref miso) => {
 250                     ns == no &&
 251                         miss.iter().all(|mi| miso.iter().any(|x| x.node == mi.node))
 252                 }
 253                 _ => false
 254             }
 255         }
 256     }
 257 }
 258
 259 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 260 pub struct Block {
 261     pub view_items: Vec<ViewItem>,
 262     pub stmts: Vec<Gc<Stmt>>,
 263     pub expr: Option<Gc<Expr>>,
 264     pub id: NodeId,
 265     pub rules: BlockCheckMode,
 266     pub span: Span,
 267 }
 268
 269 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 270 pub struct Pat {
 271     pub id: NodeId,
 272     pub node: Pat_,
 273     pub span: Span,
 274 }
 275
 276 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 277 pub struct FieldPat {
 278     pub ident: Ident,
 279     pub pat: Gc<Pat>,
 280 }
 281
 282 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 283 pub enum BindingMode {
 284     BindByRef(Mutability),
 285     BindByValue(Mutability),
 286 }
 287
 288 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 289 pub enum Pat_ {
 290     PatWild,
 291     PatWildMulti,
 292     // A PatIdent may either be a new bound variable,
 293     // or a nullary enum (in which case the third field
 294     // is None).
 295     // In the nullary enum case, the parser can't determine
 296     // which it is. The resolver determines this, and
 297     // records this pattern's NodeId in an auxiliary
 298     // set (of "PatIdents that refer to nullary enums")
 299     PatIdent(BindingMode, SpannedIdent, Option<Gc<Pat>>),
 300     PatEnum(Path, Option<Vec<Gc<Pat>>>), /* "none" means a * pattern where
 301                                      * we don't bind the fields to names */
 302     PatStruct(Path, Vec<FieldPat>, bool),
 303     PatTup(Vec<Gc<Pat>>),
 304     PatBox(Gc<Pat>),
 305     PatRegion(Gc<Pat>), // reference pattern
 306     PatLit(Gc<Expr>),
 307     PatRange(Gc<Expr>, Gc<Expr>),
 308     // [a, b, ..i, y, z] is represented as
 309     // PatVec(~[a, b], Some(i), ~[y, z])
 310     PatVec(Vec<Gc<Pat>>, Option<Gc<Pat>>, Vec<Gc<Pat>>),
 311     PatMac(Mac),
 312 }
 313
 314 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash, Show)]
 315 pub enum Mutability {
 316     MutMutable,
 317     MutImmutable,
 318 }
 319
 320 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 321 pub enum ExprVstore {
 322     ExprVstoreUniq,                 // ~[1,2,3,4]
 323     ExprVstoreSlice,                // &[1,2,3,4]
 324     ExprVstoreMutSlice,             // &mut [1,2,3,4]
 325 }
 326
 327 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 328 pub enum BinOp {
 329     BiAdd,
 330     BiSub,
 331     BiMul,
 332     BiDiv,
 333     BiRem,
 334     BiAnd,
 335     BiOr,
 336     BiBitXor,
 337     BiBitAnd,
 338     BiBitOr,
 339     BiShl,
 340     BiShr,
 341     BiEq,
 342     BiLt,
 343     BiLe,
 344     BiNe,
 345     BiGe,
 346     BiGt,
 347 }
 348
 349 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 350 pub enum UnOp {
 351     UnBox,
 352     UnUniq,
 353     UnDeref,
 354     UnNot,
 355     UnNeg
 356 }
 357
 358 pub type Stmt = Spanned<Stmt_>;
 359
 360 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 361 pub enum Stmt_ {
 362     // could be an item or a local (let) binding:
 363     StmtDecl(Gc<Decl>, NodeId),
 364
 365     // expr without trailing semi-colon (must have unit type):
 366     StmtExpr(Gc<Expr>, NodeId),
 367
 368     // expr with trailing semi-colon (may have any type):
 369     StmtSemi(Gc<Expr>, NodeId),
 370
 371     // bool: is there a trailing sem-colon?
 372     StmtMac(Mac, bool),
 373 }
 374
 375 /// Where a local declaration came from: either a true `let ... =
 376 /// ...;`, or one desugared from the pattern of a for loop.
 377 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 378 pub enum LocalSource {
 379     LocalLet,
 380     LocalFor,
 381 }
 382
 383 // FIXME (pending discussion of #1697, #2178...): local should really be
 384 // a refinement on pat.
 385 /// Local represents a `let` statement, e.g., `let <pat>:<ty> = <expr>;`
 386 #[deriving(PartialEq, Eq, Encodable, Decodable, Hash)]
 387 pub struct Local {
 388     pub ty: P<Ty>,
 389     pub pat: Gc<Pat>,
 390     pub init: Option<Gc<Expr>>,
 391     pub id: NodeId,
 392     pub span: Span,
 393     pub source: LocalSource,
 394 }
 395
 396 pub type Decl = Spanned<Decl_>;
 397
 398 #[deriving(PartialEq, Eq, Encodable, Decodable, Hash)]
 399 pub enum Decl_ {
 400     // a local (let) binding:
 401     DeclLocal(Gc<Local>),
 402     // an item binding:
 403     DeclItem(Gc<Item>),
 404 }
 405
 406 /// represents one arm of a 'match'
 407 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 408 pub struct Arm {
 409     pub attrs: Vec<Attribute>,
 410     pub pats: Vec<Gc<Pat>>,
 411     pub guard: Option<Gc<Expr>>,
 412     pub body: Gc<Expr>,
 413 }
 414
 415 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 416 pub struct Field {
 417     pub ident: SpannedIdent,
 418     pub expr: Gc<Expr>,
 419     pub span: Span,
 420 }
 421
 422 pub type SpannedIdent = Spanned<Ident>;
 423
 424 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 425 pub enum BlockCheckMode {
 426     DefaultBlock,
 427     UnsafeBlock(UnsafeSource),
 428 }
 429
 430 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 431 pub enum UnsafeSource {
 432     CompilerGenerated,
 433     UserProvided,
 434 }
 435
 436 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 437 pub struct Expr {
 438     pub id: NodeId,
 439     pub node: Expr_,
 440     pub span: Span,
 441 }
 442
 443 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 444 pub enum Expr_ {
 445     ExprVstore(Gc<Expr>, ExprVstore),
 446     // First expr is the place; second expr is the value.
 447     ExprBox(Gc<Expr>, Gc<Expr>),
 448     ExprVec(Vec<Gc<Expr>>),
 449     ExprCall(Gc<Expr>, Vec<Gc<Expr>>),
 450     ExprMethodCall(SpannedIdent, Vec<P<Ty>>, Vec<Gc<Expr>>),
 451     ExprTup(Vec<Gc<Expr>>),
 452     ExprBinary(BinOp, Gc<Expr>, Gc<Expr>),
 453     ExprUnary(UnOp, Gc<Expr>),
 454     ExprLit(Gc<Lit>),
 455     ExprCast(Gc<Expr>, P<Ty>),
 456     ExprIf(Gc<Expr>, P<Block>, Option<Gc<Expr>>),
 457     ExprWhile(Gc<Expr>, P<Block>),
 458     // FIXME #6993: change to Option<Name> ... or not, if these are hygienic.
 459     ExprForLoop(Gc<Pat>, Gc<Expr>, P<Block>, Option<Ident>),
 460     // Conditionless loop (can be exited with break, cont, or ret)
 461     // FIXME #6993: change to Option<Name> ... or not, if these are hygienic.
 462     ExprLoop(P<Block>, Option<Ident>),
 463     ExprMatch(Gc<Expr>, Vec<Arm>),
 464     ExprFnBlock(P<FnDecl>, P<Block>),
 465     ExprProc(P<FnDecl>, P<Block>),
 466     ExprBlock(P<Block>),
 467
 468     ExprAssign(Gc<Expr>, Gc<Expr>),
 469     ExprAssignOp(BinOp, Gc<Expr>, Gc<Expr>),
 470     ExprField(Gc<Expr>, SpannedIdent, Vec<P<Ty>>),
 471     ExprIndex(Gc<Expr>, Gc<Expr>),
 472
 473     /// Variable reference, possibly containing `::` and/or
 474     /// type parameters, e.g. foo::bar::<baz>
 475     ExprPath(Path),
 476
 477     ExprAddrOf(Mutability, Gc<Expr>),
 478     ExprBreak(Option<Ident>),
 479     ExprAgain(Option<Ident>),
 480     ExprRet(Option<Gc<Expr>>),
 481
 482     ExprInlineAsm(InlineAsm),
 483
 484     ExprMac(Mac),
 485
 486     // A struct literal expression.
 487     ExprStruct(Path, Vec<Field> , Option<Gc<Expr>> /* base */),
 488
 489     // A vector literal constructed from one repeated element.
 490     ExprRepeat(Gc<Expr> /* element */, Gc<Expr> /* count */),
 491
 492     // No-op: used solely so we can pretty-print faithfully
 493     ExprParen(Gc<Expr>)
 494 }
 495
 496 // When the main rust parser encounters a syntax-extension invocation, it
 497 // parses the arguments to the invocation as a token-tree. This is a very
 498 // loose structure, such that all sorts of different AST-fragments can
 499 // be passed to syntax extensions using a uniform type.
 500 //
 501 // If the syntax extension is an MBE macro, it will attempt to match its
 502 // LHS "matchers" against the provided token tree, and if it finds a
 503 // match, will transcribe the RHS token tree, splicing in any captured
 504 // macro_parser::matched_nonterminals into the TTNonterminals it finds.
 505 //
 506 // The RHS of an MBE macro is the only place a TTNonterminal or TTSeq
 507 // makes any real sense. You could write them elsewhere but nothing
 508 // else knows what to do with them, so you'll probably get a syntax
 509 // error.
 510 //
 511 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 512 #[doc="For macro invocations; parsing is delegated to the macro"]
 513 pub enum TokenTree {
 514     // a single token
 515     TTTok(Span, ::parse::token::Token),
 516     // a delimited sequence (the delimiters appear as the first
 517     // and last elements of the vector)
 518     // FIXME(eddyb) #6308 Use Rc<[TokenTree]> after DST.
 519     TTDelim(Rc<Vec<TokenTree>>),
 520
 521     // These only make sense for right-hand-sides of MBE macros:
 522
 523     // a kleene-style repetition sequence with a span, a TTForest,
 524     // an optional separator, and a boolean where true indicates
 525     // zero or more (..), and false indicates one or more (+).
 526     // FIXME(eddyb) #6308 Use Rc<[TokenTree]> after DST.
 527     TTSeq(Span, Rc<Vec<TokenTree>>, Option<::parse::token::Token>, bool),
 528
 529     // a syntactic variable that will be filled in by macro expansion.
 530     TTNonterminal(Span, Ident)
 531 }
 532
 533 //
 534 // Matchers are nodes defined-by and recognized-by the main rust parser and
 535 // language, but they're only ever found inside syntax-extension invocations;
 536 // indeed, the only thing that ever _activates_ the rules in the rust parser
 537 // for parsing a matcher is a matcher looking for the 'matchers' nonterminal
 538 // itself. Matchers represent a small sub-language for pattern-matching
 539 // token-trees, and are thus primarily used by the macro-defining extension
 540 // itself.
 541 //
 542 // MatchTok
 543 // --------
 544 //
 545 //     A matcher that matches a single token, denoted by the token itself. So
 546 //     long as there's no $ involved.
 547 //
 548 //
 549 // MatchSeq
 550 // --------
 551 //
 552 //     A matcher that matches a sequence of sub-matchers, denoted various
 553 //     possible ways:
 554 //
 555 //             $(M)*       zero or more Ms
 556 //             $(M)+       one or more Ms
 557 //             $(M),+      one or more comma-separated Ms
 558 //             $(A B C);*  zero or more semi-separated 'A B C' seqs
 559 //
 560 //
 561 // MatchNonterminal
 562 // -----------------
 563 //
 564 //     A matcher that matches one of a few interesting named rust
 565 //     nonterminals, such as types, expressions, items, or raw token-trees. A
 566 //     black-box matcher on expr, for example, binds an expr to a given ident,
 567 //     and that ident can re-occur as an interpolation in the RHS of a
 568 //     macro-by-example rule. For example:
 569 //
 570 //        $foo:expr   =>     1 + $foo    // interpolate an expr
 571 //        $foo:tt     =>     $foo        // interpolate a token-tree
 572 //        $foo:tt     =>     bar! $foo   // only other valid interpolation
 573 //                                       // is in arg position for another
 574 //                                       // macro
 575 //
 576 // As a final, horrifying aside, note that macro-by-example's input is
 577 // also matched by one of these matchers. Holy self-referential! It is matched
 578 // by a MatchSeq, specifically this one:
 579 //
 580 //                   $( $lhs:matchers => $rhs:tt );+
 581 //
 582 // If you understand that, you have closed to loop and understand the whole
 583 // macro system. Congratulations.
 584 //
 585 pub type Matcher = Spanned<Matcher_>;
 586
 587 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 588 pub enum Matcher_ {
 589     // match one token
 590     MatchTok(::parse::token::Token),
 591     // match repetitions of a sequence: body, separator, zero ok?,
 592     // lo, hi position-in-match-array used:
 593     MatchSeq(Vec<Matcher> , Option<::parse::token::Token>, bool, uint, uint),
 594     // parse a Rust NT: name to bind, name of NT, position in match array:
 595     MatchNonterminal(Ident, Ident, uint)
 596 }
 597
 598 pub type Mac = Spanned<Mac_>;
 599
 600 // represents a macro invocation. The Path indicates which macro
 601 // is being invoked, and the vector of token-trees contains the source
 602 // of the macro invocation.
 603 // There's only one flavor, now, so this could presumably be simplified.
 604 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 605 pub enum Mac_ {
 606     MacInvocTT(Path, Vec<TokenTree> , SyntaxContext),   // new macro-invocation
 607 }
 608
 609 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 610 pub enum StrStyle {
 611     CookedStr,
 612     RawStr(uint)
 613 }
 614
 615 pub type Lit = Spanned<Lit_>;
 616
 617 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 618 pub enum Lit_ {
 619     LitStr(InternedString, StrStyle),
 620     LitBinary(Rc<Vec<u8> >),
 621     LitByte(u8),
 622     LitChar(char),
 623     LitInt(i64, IntTy),
 624     LitUint(u64, UintTy),
 625     LitIntUnsuffixed(i64),
 626     LitFloat(InternedString, FloatTy),
 627     LitFloatUnsuffixed(InternedString),
 628     LitNil,
 629     LitBool(bool),
 630 }
 631
 632 // NB: If you change this, you'll probably want to change the corresponding
 633 // type structure in middle/ty.rs as well.
 634 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 635 pub struct MutTy {
 636     pub ty: P<Ty>,
 637     pub mutbl: Mutability,
 638 }
 639
 640 #[deriving(PartialEq, Eq, Encodable, Decodable, Hash)]
 641 pub struct TypeField {
 642     pub ident: Ident,
 643     pub mt: MutTy,
 644     pub span: Span,
 645 }
 646
 647 /// Represents a required method in a trait declaration,
 648 /// one without a default implementation
 649 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 650 pub struct TypeMethod {
 651     pub ident: Ident,
 652     pub attrs: Vec<Attribute>,
 653     pub fn_style: FnStyle,
 654     pub decl: P<FnDecl>,
 655     pub generics: Generics,
 656     pub explicit_self: ExplicitSelf,
 657     pub id: NodeId,
 658     pub span: Span,
 659     pub vis: Visibility,
 660 }
 661
 662 /// Represents a method declaration in a trait declaration, possibly
 663 /// including a default implementation
 664 // A trait method is either required (meaning it doesn't have an
 665 // implementation, just a signature) or provided (meaning it has a default
 666 // implementation).
 667 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 668 pub enum TraitMethod {
 669     Required(TypeMethod),
 670     Provided(Gc<Method>),
 671 }
 672
 673 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 674 pub enum IntTy {
 675     TyI,
 676     TyI8,
 677     TyI16,
 678     TyI32,
 679     TyI64,
 680 }
 681
 682 impl fmt::Show for IntTy {
 683     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 684         write!(f, "{}", ast_util::int_ty_to_string(*self, None))
 685     }
 686 }
 687
 688 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 689 pub enum UintTy {
 690     TyU,
 691     TyU8,
 692     TyU16,
 693     TyU32,
 694     TyU64,
 695 }
 696
 697 impl fmt::Show for UintTy {
 698     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 699         write!(f, "{}", ast_util::uint_ty_to_string(*self, None))
 700     }
 701 }
 702
 703 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 704 pub enum FloatTy {
 705     TyF32,
 706     TyF64,
 707 }
 708
 709 impl fmt::Show for FloatTy {
 710     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 711         write!(f, "{}", ast_util::float_ty_to_string(*self))
 712     }
 713 }
 714
 715 // NB PartialEq method appears below.
 716 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 717 pub struct Ty {
 718     pub id: NodeId,
 719     pub node: Ty_,
 720     pub span: Span,
 721 }
 722
 723 // Not represented directly in the AST, referred to by name through a ty_path.
 724 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 725 pub enum PrimTy {
 726     TyInt(IntTy),
 727     TyUint(UintTy),
 728     TyFloat(FloatTy),
 729     TyStr,
 730     TyBool,
 731     TyChar
 732 }
 733
 734 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 735 pub enum Onceness {
 736     Once,
 737     Many
 738 }
 739
 740 impl fmt::Show for Onceness {
 741     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 742         match *self {
 743             Once => "once".fmt(f),
 744             Many => "many".fmt(f),
 745         }
 746     }
 747 }
 748
 749 /// Represents the type of a closure
 750 #[deriving(PartialEq, Eq, Encodable, Decodable, Hash)]
 751 pub struct ClosureTy {
 752     pub lifetimes: Vec<Lifetime>,
 753     pub fn_style: FnStyle,
 754     pub onceness: Onceness,
 755     pub decl: P<FnDecl>,
 756     // Optional optvec distinguishes between "fn()" and "fn:()" so we can
 757     // implement issue #7264. None means "fn()", which means infer a default
 758     // bound based on pointer sigil during typeck. Some(Empty) means "fn:()",
 759     // which means use no bounds (e.g., not even Owned on a ~fn()).
 760     pub bounds: Option<OwnedSlice<TyParamBound>>,
 761 }
 762
 763 #[deriving(PartialEq, Eq, Encodable, Decodable, Hash)]
 764 pub struct BareFnTy {
 765     pub fn_style: FnStyle,
 766     pub abi: Abi,
 767     pub lifetimes: Vec<Lifetime>,
 768     pub decl: P<FnDecl>
 769 }
 770
 771 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 772 pub struct UnboxedFnTy {
 773     pub decl: P<FnDecl>,
 774 }
 775
 776 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 777 pub enum Ty_ {
 778     TyNil,
 779     TyBot, /* bottom type */
 780     TyBox(P<Ty>),
 781     TyUniq(P<Ty>),
 782     TyVec(P<Ty>),
 783     TyFixedLengthVec(P<Ty>, Gc<Expr>),
 784     TyPtr(MutTy),
 785     TyRptr(Option<Lifetime>, MutTy),
 786     TyClosure(Gc<ClosureTy>, Option<Lifetime>),
 787     TyProc(Gc<ClosureTy>),
 788     TyBareFn(Gc<BareFnTy>),
 789     TyUnboxedFn(Gc<UnboxedFnTy>),
 790     TyTup(Vec<P<Ty>> ),
 791     TyPath(Path, Option<OwnedSlice<TyParamBound>>, NodeId), // for #7264; see above
 792     // No-op; kept solely so that we can pretty-print faithfully
 793     TyParen(P<Ty>),
 794     TyTypeof(Gc<Expr>),
 795     // TyInfer means the type should be inferred instead of it having been
 796     // specified. This can appear anywhere in a type.
 797     TyInfer,
 798 }
 799
 800 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 801 pub enum AsmDialect {
 802     AsmAtt,
 803     AsmIntel
 804 }
 805
 806 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 807 pub struct InlineAsm {
 808     pub asm: InternedString,
 809     pub asm_str_style: StrStyle,
 810     pub clobbers: InternedString,
 811     pub inputs: Vec<(InternedString, Gc<Expr>)>,
 812     pub outputs: Vec<(InternedString, Gc<Expr>)>,
 813     pub volatile: bool,
 814     pub alignstack: bool,
 815     pub dialect: AsmDialect
 816 }
 817
 818 /// represents an argument in a function header
 819 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 820 pub struct Arg {
 821     pub ty: P<Ty>,
 822     pub pat: Gc<Pat>,
 823     pub id: NodeId,
 824 }
 825
 826 impl Arg {
 827     pub fn new_self(span: Span, mutability: Mutability) -> Arg {
 828         let path = Spanned{span:span,node:special_idents::self_};
 829         Arg {
 830             // HACK(eddyb) fake type for the self argument.
 831             ty: P(Ty {
 832                 id: DUMMY_NODE_ID,
 833                 node: TyInfer,
 834                 span: DUMMY_SP,
 835             }),
 836             pat: box(GC) Pat {
 837                 id: DUMMY_NODE_ID,
 838                 node: PatIdent(BindByValue(mutability), path, None),
 839                 span: span
 840             },
 841             id: DUMMY_NODE_ID
 842         }
 843     }
 844 }
 845
 846 /// represents the header (not the body) of a function declaration
 847 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 848 pub struct FnDecl {
 849     pub inputs: Vec<Arg>,
 850     pub output: P<Ty>,
 851     pub cf: RetStyle,
 852     pub variadic: bool
 853 }
 854
 855 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 856 pub enum FnStyle {
 857     UnsafeFn, // declared with "unsafe fn"
 858     NormalFn, // declared with "fn"
 859 }
 860
 861 impl fmt::Show for FnStyle {
 862     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 863         match *self {
 864             NormalFn => "normal".fmt(f),
 865             UnsafeFn => "unsafe".fmt(f),
 866         }
 867     }
 868 }
 869
 870 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 871 pub enum RetStyle {
 872     NoReturn, // functions with return type _|_ that always
 873               // raise an error or exit (i.e. never return to the caller)
 874     Return, // everything else
 875 }
 876
 877 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 878 pub enum ExplicitSelf_ {
 879     SelfStatic,                                // no self
 880     SelfValue,                                 // `self`
 881     SelfRegion(Option<Lifetime>, Mutability),  // `&'lt self`, `&'lt mut self`
 882     SelfUniq                                   // `~self`
 883 }
 884
 885 pub type ExplicitSelf = Spanned<ExplicitSelf_>;
 886
 887 #[deriving(PartialEq, Eq, Encodable, Decodable, Hash)]
 888 pub struct Method {
 889     pub ident: Ident,
 890     pub attrs: Vec<Attribute>,
 891     pub generics: Generics,
 892     pub explicit_self: ExplicitSelf,
 893     pub fn_style: FnStyle,
 894     pub decl: P<FnDecl>,
 895     pub body: P<Block>,
 896     pub id: NodeId,
 897     pub span: Span,
 898     pub vis: Visibility,
 899 }
 900
 901 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 902 pub struct Mod {
 903     /// A span from the first token past `{` to the last token until `}`.
 904     /// For `mod foo;`, the inner span ranges from the first token
 905     /// to the last token in the external file.
 906     pub inner: Span,
 907     pub view_items: Vec<ViewItem>,
 908     pub items: Vec<Gc<Item>>,
 909 }
 910
 911 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 912 pub struct ForeignMod {
 913     pub abi: Abi,
 914     pub view_items: Vec<ViewItem>,
 915     pub items: Vec<Gc<ForeignItem>>,
 916 }
 917
 918 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 919 pub struct VariantArg {
 920     pub ty: P<Ty>,
 921     pub id: NodeId,
 922 }
 923
 924 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 925 pub enum VariantKind {
 926     TupleVariantKind(Vec<VariantArg>),
 927     StructVariantKind(Gc<StructDef>),
 928 }
 929
 930 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 931 pub struct EnumDef {
 932     pub variants: Vec<P<Variant>>,
 933 }
 934
 935 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 936 pub struct Variant_ {
 937     pub name: Ident,
 938     pub attrs: Vec<Attribute>,
 939     pub kind: VariantKind,
 940     pub id: NodeId,
 941     pub disr_expr: Option<Gc<Expr>>,
 942     pub vis: Visibility,
 943 }
 944
 945 pub type Variant = Spanned<Variant_>;
 946
 947 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 948 pub struct PathListIdent_ {
 949     pub name: Ident,
 950     pub id: NodeId,
 951 }
 952
 953 pub type PathListIdent = Spanned<PathListIdent_>;
 954
 955 pub type ViewPath = Spanned<ViewPath_>;
 956
 957 #[deriving(PartialEq, Eq, Encodable, Decodable, Hash)]
 958 pub enum ViewPath_ {
 959
 960     // quux = foo::bar::baz
 961     //
 962     // or just
 963     //
 964     // foo::bar::baz  (with 'baz =' implicitly on the left)
 965     ViewPathSimple(Ident, Path, NodeId),
 966
 967     // foo::bar::*
 968     ViewPathGlob(Path, NodeId),
 969
 970     // foo::bar::{a,b,c}
 971     ViewPathList(Path, Vec<PathListIdent> , NodeId)
 972 }
 973
 974 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 975 pub struct ViewItem {
 976     pub node: ViewItem_,
 977     pub attrs: Vec<Attribute>,
 978     pub vis: Visibility,
 979     pub span: Span,
 980 }
 981
 982 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 983 pub enum ViewItem_ {
 984     // ident: name used to refer to this crate in the code
 985     // optional (InternedString,StrStyle): if present, this is a location
 986     // (containing arbitrary characters) from which to fetch the crate sources
 987     // For example, extern crate whatever = "github.com/rust-lang/rust"
 988     ViewItemExternCrate(Ident, Option<(InternedString,StrStyle)>, NodeId),
 989     ViewItemUse(Gc<ViewPath>),
 990 }
 991
 992 // Meta-data associated with an item
 993 pub type Attribute = Spanned<Attribute_>;
 994
 995 // Distinguishes between Attributes that decorate items and Attributes that
 996 // are contained as statements within items. These two cases need to be
 997 // distinguished for pretty-printing.
 998 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
 999 pub enum AttrStyle {
1000     AttrOuter,
1001     AttrInner,
1002 }
1003
1004 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
1005 pub struct AttrId(pub uint);
1006
1007 // doc-comments are promoted to attributes that have is_sugared_doc = true
1008 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
1009 pub struct Attribute_ {
1010     pub id: AttrId,
1011     pub style: AttrStyle,
1012     pub value: Gc<MetaItem>,
1013     pub is_sugared_doc: bool,
1014 }
1015
1016 /*
1017   TraitRef's appear in impls.
1018   resolve maps each TraitRef's ref_id to its defining trait; that's all
1019   that the ref_id is for. The impl_id maps to the "self type" of this impl.
1020   If this impl is an ItemImpl, the impl_id is redundant (it could be the
1021   same as the impl's node id).
1022  */
1023 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
1024 pub struct TraitRef {
1025     pub path: Path,
1026     pub ref_id: NodeId,
1027 }
1028
1029 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
1030 pub enum Visibility {
1031     Public,
1032     Inherited,
1033 }
1034
1035 impl Visibility {
1036     pub fn inherit_from(&self, parent_visibility: Visibility) -> Visibility {
1037         match self {
1038             &Inherited => parent_visibility,
1039             &Public => *self
1040         }
1041     }
1042 }
1043
1044 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
1045 pub struct StructField_ {
1046     pub kind: StructFieldKind,
1047     pub id: NodeId,
1048     pub ty: P<Ty>,
1049     pub attrs: Vec<Attribute>,
1050 }
1051
1052 impl StructField_ {
1053     pub fn ident(&self) -> Option<Ident> {
1054         match self.kind {
1055             NamedField(ref ident, _) => Some(ident.clone()),
1056             UnnamedField(_) => None
1057         }
1058     }
1059 }
1060
1061 pub type StructField = Spanned<StructField_>;
1062
1063 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
1064 pub enum StructFieldKind {
1065     NamedField(Ident, Visibility),
1066     UnnamedField(Visibility), // element of a tuple-like struct
1067 }
1068
1069 impl StructFieldKind {
1070     pub fn is_unnamed(&self) -> bool {
1071         match *self {
1072             UnnamedField(..) => true,
1073             NamedField(..) => false,
1074         }
1075     }
1076 }
1077
1078 #[deriving(PartialEq, Eq, Encodable, Decodable, Hash)]
1079 pub struct StructDef {
1080     pub fields: Vec<StructField>, /* fields, not including ctor */
1081     /* ID of the constructor. This is only used for tuple- or enum-like
1082      * structs. */
1083     pub ctor_id: Option<NodeId>,
1084     pub super_struct: Option<P<Ty>>, // Super struct, if specified.
1085     pub is_virtual: bool,            // True iff the struct may be inherited from.
1086 }
1087
1088 /*
1089   FIXME (#3300): Should allow items to be anonymous. Right now
1090   we just use dummy names for anon items.
1091  */
1092 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
1093 pub struct Item {
1094     pub ident: Ident,
1095     pub attrs: Vec<Attribute>,
1096     pub id: NodeId,
1097     pub node: Item_,
1098     pub vis: Visibility,
1099     pub span: Span,
1100 }
1101
1102 #[deriving(Clone, PartialEq, Eq, Encodable, Decodable, Hash)]
1103 pub enum Item_ {
1104     ItemStatic(P<Ty>, Mutability, Gc<Expr>),
1105     ItemFn(P<FnDecl>, FnStyle, Abi, Generics, P<Block>),
1106     ItemMod(Mod),
1107     ItemForeignMod(ForeignMod),
1108     ItemTy(P<Ty>, Generics),
1109     ItemEnum(EnumDef, Generics),
1110     ItemStruct(Gc<StructDef>, Generics),
1111     /// Represents a Trait Declaration
1112     ItemTrait(Generics,
1113               Option<TyParamBound>, // (optional) default bound not required for Self.
1114                                     // Currently, only Sized makes sense here.
1115               Vec<TraitRef> ,
1116               Vec<TraitMethod>),
1117     ItemImpl(Generics,
1118              Option<TraitRef>, // (optional) trait this impl implements
1119              P<Ty>, // self
1120              Vec<Gc<Method>>),
1121     // a macro invocation (which includes macro definition)
1122     ItemMac(Mac),
1123 }
1124
1125 #[deriving(PartialEq, Eq, Encodable, Decodable, Hash)]
1126 pub struct ForeignItem {
1127     pub ident: Ident,
1128     pub attrs: Vec<Attribute>,
1129     pub node: ForeignItem_,
1130     pub id: NodeId,
1131     pub span: Span,
1132     pub vis: Visibility,
1133 }
1134
1135 #[deriving(PartialEq, Eq, Encodable, Decodable, Hash)]
1136 pub enum ForeignItem_ {
1137     ForeignItemFn(P<FnDecl>, Generics),
1138     ForeignItemStatic(P<Ty>, /* is_mutbl */ bool),
1139 }
1140
1141 // The data we save and restore about an inlined item or method.  This is not
1142 // part of the AST that we parse from a file, but it becomes part of the tree
1143 // that we trans.
1144 #[deriving(PartialEq, Eq, Encodable, Decodable, Hash)]
1145 pub enum InlinedItem {
1146     IIItem(Gc<Item>),
1147     IIMethod(DefId /* impl id */, bool /* is provided */, Gc<Method>),
1148     IIForeign(Gc<ForeignItem>),
1149 }
1150
1151 #[cfg(test)]
1152 mod test {
1153     use serialize::json;
1154     use serialize;
1155     use codemap::*;
1156     use super::*;
1157
1158     // are ASTs encodable?
1159     #[test]
1160     fn check_asts_encodable() {
1161         use std::io;
1162         let e = Crate {
1163             module: Mod {
1164                 inner: Span {
1165                     lo: BytePos(11),
1166                     hi: BytePos(19),
1167                     expn_info: None,
1168                 },
1169                 view_items: Vec::new(),
1170                 items: Vec::new(),
1171             },
1172             attrs: Vec::new(),
1173             config: Vec::new(),
1174             span: Span {
1175                 lo: BytePos(10),
1176                 hi: BytePos(20),
1177                 expn_info: None,
1178             },
1179         };
1180         // doesn't matter which encoder we use....
1181         let _f = &e as &serialize::Encodable<json::Encoder, io::IoError>;
1182     }
1183 }