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