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