src/libsyntax/ast.rs

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