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