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