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