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