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
  17 use core::cast;
  18 use core::option::{None, Option, Some};
  19 use core::task;
  20 use core::to_bytes;
  21 use core::to_str::ToStr;
  22 use std::serialize::{Encodable, Decodable, Encoder, Decoder};
  23
  24
  25 // an identifier contains an index into the interner
  26 // table and a SyntaxContext to track renaming and
  27 // macro expansion per Flatt et al., "Macros
  28 // That Work Together"
  29 #[deriving(Eq)]
  30 pub struct ident { repr: Name, ctxt: SyntaxContext }
  31
  32 // a SyntaxContext represents a chain of macro-expandings
  33 // and renamings. Each macro expansion corresponds to
  34 // a fresh uint
  35
  36 // I'm representing this syntax context as an index into
  37 // a table, in order to work around a compiler bug
  38 // that's causing unreleased memory to cause core dumps
  39 // and also perhaps to save some work in destructor checks.
  40 // the special uint '0' will be used to indicate an empty
  41 // syntax context
  42
  43 // this uint is a reference to a table stored in thread-local
  44 // storage.
  45 pub type SyntaxContext = uint;
  46
  47 pub type SCTable = ~[SyntaxContext_];
  48 pub static empty_ctxt : uint = 0;
  49
  50 #[deriving(Eq)]
  51 #[auto_encode]
  52 #[auto_decode]
  53 pub enum SyntaxContext_ {
  54     EmptyCtxt,
  55     Mark (Mrk,SyntaxContext),
  56     // flattening the name and syntaxcontext into the rename...
  57     // HIDDEN INVARIANTS:
  58     // 1) the first name in a Rename node
  59     // can only be a programmer-supplied name.
  60     // 2) Every Rename node with a given Name in the
  61     // "to" slot must have the same name and context
  62     // in the "from" slot. In essence, they're all
  63     // pointers to a single "rename" event node.
  64     Rename (ident,Name,SyntaxContext)
  65 }
  66
  67 // a name represents an identifier
  68 pub type Name = uint;
  69 // a mark represents a unique id associated
  70 // with a macro expansion
  71 pub type Mrk = uint;
  72
  73 #[cfg(stage0)]
  74 impl<S:Encoder> Encodable<S> for ident {
  75     fn encode(&self, s: &S) {
  76         unsafe {
  77             let intr =
  78                 match task::local_data::local_data_get(interner_key!()) {
  79                     None => fail!(~"encode: TLS interner not set up"),
  80                     Some(intr) => intr
  81                 };
  82
  83             s.emit_str(*(*intr).get(*self));
  84         }
  85     }
  86 }
  87
  88 #[cfg(not(stage0))]
  89 impl<S:Encoder> Encodable<S> for ident {
  90     fn encode(&self, s: &mut S) {
  91         unsafe {
  92             let intr =
  93                 match task::local_data::local_data_get(interner_key!()) {
  94                     None => fail!(~"encode: TLS interner not set up"),
  95                     Some(intr) => intr
  96                 };
  97
  98             s.emit_str(*(*intr).get(*self));
  99         }
 100     }
 101 }
 102
 103 #[cfg(stage0)]
 104 impl<D:Decoder> Decodable<D> for ident {
 105     fn decode(d: &D) -> ident {
 106         let intr = match unsafe {
 107             task::local_data::local_data_get(interner_key!())
 108         } {
 109             None => fail!(~"decode: TLS interner not set up"),
 110             Some(intr) => intr
 111         };
 112
 113         (*intr).intern(@d.read_str())
 114     }
 115 }
 116
 117 #[cfg(not(stage0))]
 118 impl<D:Decoder> Decodable<D> for ident {
 119     fn decode(d: &mut D) -> ident {
 120         let intr = match unsafe {
 121             task::local_data::local_data_get(interner_key!())
 122         } {
 123             None => fail!(~"decode: TLS interner not set up"),
 124             Some(intr) => intr
 125         };
 126
 127         (*intr).intern(@d.read_str())
 128     }
 129 }
 130
 131 impl to_bytes::IterBytes for ident {
 132     fn iter_bytes(&self, lsb0: bool, f: to_bytes::Cb) {
 133         self.repr.iter_bytes(lsb0, f)
 134     }
 135 }
 136
 137 // Functions may or may not have names.
 138 pub type fn_ident = Option<ident>;
 139
 140 #[auto_encode]
 141 #[auto_decode]
 142 #[deriving(Eq)]
 143 pub struct Lifetime {
 144     id: node_id,
 145     span: span,
 146     ident: ident
 147 }
 148
 149 // a "Path" is essentially Rust's notion of a name;
 150 // for instance: core::cmp::Eq  .  It's represented
 151 // as a sequence of identifiers, along with a bunch
 152 // of supporting information.
 153 #[auto_encode]
 154 #[auto_decode]
 155 #[deriving(Eq)]
 156 pub struct Path {
 157     span: span,
 158     global: bool,
 159     idents: ~[ident],
 160     rp: Option<@Lifetime>,
 161     types: ~[@Ty],
 162 }
 163
 164 pub type crate_num = int;
 165
 166 pub type node_id = int;
 167
 168 #[auto_encode]
 169 #[auto_decode]
 170 #[deriving(Eq)]
 171 pub struct def_id {
 172     crate: crate_num,
 173     node: node_id,
 174 }
 175
 176 pub static local_crate: crate_num = 0;
 177 pub static crate_node_id: node_id = 0;
 178
 179 #[auto_encode]
 180 #[auto_decode]
 181 #[deriving(Eq)]
 182 // The AST represents all type param bounds as types.
 183 // typeck::collect::compute_bounds matches these against
 184 // the "special" built-in traits (see middle::lang_items) and
 185 // detects Copy, Send, Owned, and Const.
 186 pub enum TyParamBound {
 187     TraitTyParamBound(@trait_ref),
 188     RegionTyParamBound
 189 }
 190
 191 #[auto_encode]
 192 #[auto_decode]
 193 #[deriving(Eq)]
 194 pub struct TyParam {
 195     ident: ident,
 196     id: node_id,
 197     bounds: @OptVec<TyParamBound>
 198 }
 199
 200 #[auto_encode]
 201 #[auto_decode]
 202 #[deriving(Eq)]
 203 pub struct Generics {
 204     lifetimes: OptVec<Lifetime>,
 205     ty_params: OptVec<TyParam>
 206 }
 207
 208 pub impl Generics {
 209     fn is_parameterized(&self) -> bool {
 210         self.lifetimes.len() + self.ty_params.len() > 0
 211     }
 212     fn is_lt_parameterized(&self) -> bool {
 213         self.lifetimes.len() > 0
 214     }
 215     fn is_type_parameterized(&self) -> bool {
 216         self.ty_params.len() > 0
 217     }
 218 }
 219
 220 #[auto_encode]
 221 #[auto_decode]
 222 #[deriving(Eq)]
 223 pub enum def {
 224     def_fn(def_id, purity),
 225     def_static_method(/* method */ def_id,
 226                       /* trait */  Option<def_id>,
 227                       purity),
 228     def_self(node_id, bool /* is_implicit */),
 229     def_self_ty(/* trait id */ node_id),
 230     def_mod(def_id),
 231     def_foreign_mod(def_id),
 232     def_const(def_id),
 233     def_arg(node_id, bool /* is_mutbl */),
 234     def_local(node_id, bool /* is_mutbl */),
 235     def_variant(def_id /* enum */, def_id /* variant */),
 236     def_ty(def_id),
 237     def_trait(def_id),
 238     def_prim_ty(prim_ty),
 239     def_ty_param(def_id, uint),
 240     def_binding(node_id, binding_mode),
 241     def_use(def_id),
 242     def_upvar(node_id,  // id of closed over var
 243               @def,     // closed over def
 244               node_id,  // expr node that creates the closure
 245               node_id), // id for the block/body of the closure expr
 246     def_struct(def_id),
 247     def_typaram_binder(node_id), /* struct, impl or trait with ty params */
 248     def_region(node_id),
 249     def_label(node_id)
 250 }
 251
 252
 253 // The set of meta_items that define the compilation environment of the crate,
 254 // used to drive conditional compilation
 255 pub type crate_cfg = ~[@meta_item];
 256
 257 pub type crate = spanned<crate_>;
 258
 259 #[auto_encode]
 260 #[auto_decode]
 261 #[deriving(Eq)]
 262 pub struct crate_ {
 263     module: _mod,
 264     attrs: ~[attribute],
 265     config: crate_cfg,
 266 }
 267
 268 pub type meta_item = spanned<meta_item_>;
 269
 270 #[auto_encode]
 271 #[auto_decode]
 272 #[deriving(Eq)]
 273 pub enum meta_item_ {
 274     meta_word(@~str),
 275     meta_list(@~str, ~[@meta_item]),
 276     meta_name_value(@~str, lit),
 277 }
 278
 279 pub type blk = spanned<blk_>;
 280
 281 #[auto_encode]
 282 #[auto_decode]
 283 #[deriving(Eq)]
 284 pub struct blk_ {
 285     view_items: ~[@view_item],
 286     stmts: ~[@stmt],
 287     expr: Option<@expr>,
 288     id: node_id,
 289     rules: blk_check_mode,
 290 }
 291
 292 #[auto_encode]
 293 #[auto_decode]
 294 #[deriving(Eq)]
 295 pub struct pat {
 296     id: node_id,
 297     node: pat_,
 298     span: span,
 299 }
 300
 301 #[auto_encode]
 302 #[auto_decode]
 303 #[deriving(Eq)]
 304 pub struct field_pat {
 305     ident: ident,
 306     pat: @pat,
 307 }
 308
 309 #[auto_encode]
 310 #[auto_decode]
 311 #[deriving(Eq)]
 312 pub enum binding_mode {
 313     bind_by_copy,
 314     bind_by_ref(mutability),
 315     bind_infer
 316 }
 317
 318 impl to_bytes::IterBytes for binding_mode {
 319     fn iter_bytes(&self, lsb0: bool, f: to_bytes::Cb) {
 320         match *self {
 321           bind_by_copy => 0u8.iter_bytes(lsb0, f),
 322
 323           bind_by_ref(ref m) =>
 324           to_bytes::iter_bytes_2(&1u8, m, lsb0, f),
 325
 326           bind_infer =>
 327           2u8.iter_bytes(lsb0, f),
 328         }
 329     }
 330 }
 331
 332 #[auto_encode]
 333 #[auto_decode]
 334 #[deriving(Eq)]
 335 pub enum pat_ {
 336     pat_wild,
 337     // A pat_ident may either be a new bound variable,
 338     // or a nullary enum (in which case the second field
 339     // is None).
 340     // In the nullary enum case, the parser can't determine
 341     // which it is. The resolver determines this, and
 342     // records this pattern's node_id in an auxiliary
 343     // set (of "pat_idents that refer to nullary enums")
 344     pat_ident(binding_mode, @Path, Option<@pat>),
 345     pat_enum(@Path, Option<~[@pat]>), /* "none" means a * pattern where
 346                                        * we don't bind the fields to names */
 347     pat_struct(@Path, ~[field_pat], bool),
 348     pat_tup(~[@pat]),
 349     pat_box(@pat),
 350     pat_uniq(@pat),
 351     pat_region(@pat), // borrowed pointer pattern
 352     pat_lit(@expr),
 353     pat_range(@expr, @expr),
 354     // [a, b, ..i, y, z] is represented as
 355     // pat_vec(~[a, b], Some(i), ~[y, z])
 356     pat_vec(~[@pat], Option<@pat>, ~[@pat])
 357 }
 358
 359 #[auto_encode]
 360 #[auto_decode]
 361 #[deriving(Eq)]
 362 pub enum mutability { m_mutbl, m_imm, m_const, }
 363
 364 impl to_bytes::IterBytes for mutability {
 365     fn iter_bytes(&self, lsb0: bool, f: to_bytes::Cb) {
 366         (*self as u8).iter_bytes(lsb0, f)
 367     }
 368 }
 369
 370 #[auto_encode]
 371 #[auto_decode]
 372 #[deriving(Eq)]
 373 pub enum Sigil {
 374     BorrowedSigil,
 375     OwnedSigil,
 376     ManagedSigil
 377 }
 378
 379 impl to_bytes::IterBytes for Sigil {
 380     fn iter_bytes(&self, lsb0: bool, f: to_bytes::Cb) {
 381         (*self as uint).iter_bytes(lsb0, f)
 382     }
 383 }
 384
 385 impl ToStr for Sigil {
 386     fn to_str(&self) -> ~str {
 387         match *self {
 388             BorrowedSigil => ~"&",
 389             OwnedSigil => ~"~",
 390             ManagedSigil => ~"@"
 391          }
 392     }
 393 }
 394
 395 #[auto_encode]
 396 #[auto_decode]
 397 #[deriving(Eq)]
 398 pub enum vstore {
 399     // FIXME (#3469): Change uint to @expr (actually only constant exprs)
 400     vstore_fixed(Option<uint>),     // [1,2,3,4]
 401     vstore_uniq,                    // ~[1,2,3,4]
 402     vstore_box,                     // @[1,2,3,4]
 403     vstore_slice(Option<@Lifetime>) // &'foo? [1,2,3,4]
 404 }
 405
 406 #[auto_encode]
 407 #[auto_decode]
 408 #[deriving(Eq)]
 409 pub enum expr_vstore {
 410     expr_vstore_uniq,                  // ~[1,2,3,4]
 411     expr_vstore_box,                   // @[1,2,3,4]
 412     expr_vstore_mut_box,               // @mut [1,2,3,4]
 413     expr_vstore_slice,                 // &[1,2,3,4]
 414     expr_vstore_mut_slice,             // &mut [1,2,3,4]
 415 }
 416
 417 #[auto_encode]
 418 #[auto_decode]
 419 #[deriving(Eq)]
 420 pub enum binop {
 421     add,
 422     subtract,
 423     mul,
 424     div,
 425     rem,
 426     and,
 427     or,
 428     bitxor,
 429     bitand,
 430     bitor,
 431     shl,
 432     shr,
 433     eq,
 434     lt,
 435     le,
 436     ne,
 437     ge,
 438     gt,
 439 }
 440
 441 #[auto_encode]
 442 #[auto_decode]
 443 #[deriving(Eq)]
 444 pub enum unop {
 445     box(mutability),
 446     uniq(mutability),
 447     deref,
 448     not,
 449     neg
 450 }
 451
 452 pub type stmt = spanned<stmt_>;
 453
 454 #[auto_encode]
 455 #[auto_decode]
 456 #[deriving(Eq)]
 457 pub enum stmt_ {
 458     stmt_decl(@decl, node_id),
 459
 460     // expr without trailing semi-colon (must have unit type):
 461     stmt_expr(@expr, node_id),
 462
 463     // expr with trailing semi-colon (may have any type):
 464     stmt_semi(@expr, node_id),
 465
 466     // bool: is there a trailing sem-colon?
 467     stmt_mac(mac, bool),
 468 }
 469
 470 // FIXME (pending discussion of #1697, #2178...): local should really be
 471 // a refinement on pat.
 472 #[auto_encode]
 473 #[auto_decode]
 474 #[deriving(Eq)]
 475 pub struct local_ {
 476     is_mutbl: bool,
 477     ty: @Ty,
 478     pat: @pat,
 479     init: Option<@expr>,
 480     id: node_id,
 481 }
 482
 483 pub type local = spanned<local_>;
 484
 485 pub type decl = spanned<decl_>;
 486
 487 #[auto_encode]
 488 #[auto_decode]
 489 #[deriving(Eq)]
 490 pub enum decl_ { decl_local(~[@local]), decl_item(@item), }
 491
 492 #[auto_encode]
 493 #[auto_decode]
 494 #[deriving(Eq)]
 495 pub struct arm {
 496     pats: ~[@pat],
 497     guard: Option<@expr>,
 498     body: blk,
 499 }
 500
 501 #[auto_encode]
 502 #[auto_decode]
 503 #[deriving(Eq)]
 504 pub struct field_ {
 505     mutbl: mutability,
 506     ident: ident,
 507     expr: @expr,
 508 }
 509
 510 pub type field = spanned<field_>;
 511
 512 #[auto_encode]
 513 #[auto_decode]
 514 #[deriving(Eq)]
 515 pub enum blk_check_mode { default_blk, unsafe_blk, }
 516
 517 #[auto_encode]
 518 #[auto_decode]
 519 #[deriving(Eq)]
 520 pub struct expr {
 521     id: node_id,
 522     // Extra node ID is only used for index, assign_op, unary, binary, method
 523     // call
 524     callee_id: node_id,
 525     node: expr_,
 526     span: span,
 527 }
 528
 529 #[auto_encode]
 530 #[auto_decode]
 531 #[deriving(Eq)]
 532 pub enum CallSugar {
 533     NoSugar,
 534     DoSugar,
 535     ForSugar
 536 }
 537
 538 #[auto_encode]
 539 #[auto_decode]
 540 #[deriving(Eq)]
 541 pub enum expr_ {
 542     expr_vstore(@expr, expr_vstore),
 543     expr_vec(~[@expr], mutability),
 544     expr_call(@expr, ~[@expr], CallSugar),
 545     expr_method_call(@expr, ident, ~[@Ty], ~[@expr], CallSugar),
 546     expr_tup(~[@expr]),
 547     expr_binary(binop, @expr, @expr),
 548     expr_unary(unop, @expr),
 549     expr_lit(@lit),
 550     expr_cast(@expr, @Ty),
 551     expr_if(@expr, blk, Option<@expr>),
 552     expr_while(@expr, blk),
 553     /* Conditionless loop (can be exited with break, cont, or ret)
 554        Same semantics as while(true) { body }, but typestate knows that the
 555        (implicit) condition is always true. */
 556     expr_loop(blk, Option<ident>),
 557     expr_match(@expr, ~[arm]),
 558     expr_fn_block(fn_decl, blk),
 559     // Inner expr is always an expr_fn_block. We need the wrapping node to
 560     // easily type this (a function returning nil on the inside but bool on
 561     // the outside).
 562     expr_loop_body(@expr),
 563     // Like expr_loop_body but for 'do' blocks
 564     expr_do_body(@expr),
 565     expr_block(blk),
 566
 567     expr_copy(@expr),
 568     expr_assign(@expr, @expr),
 569     expr_swap(@expr, @expr),
 570     expr_assign_op(binop, @expr, @expr),
 571     expr_field(@expr, ident, ~[@Ty]),
 572     expr_index(@expr, @expr),
 573     expr_path(@Path),
 574     expr_addr_of(mutability, @expr),
 575     expr_break(Option<ident>),
 576     expr_again(Option<ident>),
 577     expr_ret(Option<@expr>),
 578     expr_log(@expr, @expr),
 579
 580     expr_inline_asm(inline_asm),
 581
 582     expr_mac(mac),
 583
 584     // A struct literal expression.
 585     expr_struct(@Path, ~[field], Option<@expr>),
 586
 587     // A vector literal constructed from one repeated element.
 588     expr_repeat(@expr /* element */, @expr /* count */, mutability),
 589
 590     // No-op: used solely so we can pretty-print faithfully
 591     expr_paren(@expr)
 592 }
 593
 594 // When the main rust parser encounters a syntax-extension invocation, it
 595 // parses the arguments to the invocation as a token-tree. This is a very
 596 // loose structure, such that all sorts of different AST-fragments can
 597 // be passed to syntax extensions using a uniform type.
 598 //
 599 // If the syntax extension is an MBE macro, it will attempt to match its
 600 // LHS "matchers" against the provided token tree, and if it finds a
 601 // match, will transcribe the RHS token tree, splicing in any captured
 602 // macro_parser::matched_nonterminals into the tt_nonterminals it finds.
 603 //
 604 // The RHS of an MBE macro is the only place a tt_nonterminal or tt_seq
 605 // makes any real sense. You could write them elsewhere but nothing
 606 // else knows what to do with them, so you'll probably get a syntax
 607 // error.
 608 //
 609 #[auto_encode]
 610 #[auto_decode]
 611 #[deriving(Eq)]
 612 #[doc="For macro invocations; parsing is delegated to the macro"]
 613 pub enum token_tree {
 614     // a single token
 615     tt_tok(span, ::parse::token::Token),
 616     // a delimited sequence (the delimiters appear as the first
 617     // and last elements of the vector)
 618     tt_delim(~[token_tree]),
 619     // These only make sense for right-hand-sides of MBE macros:
 620
 621     // a kleene-style repetition sequence with a span, a tt_forest,
 622     // an optional separator (?), and a boolean where true indicates
 623     // zero or more (*), and false indicates one or more (+).
 624     tt_seq(span, ~[token_tree], Option<::parse::token::Token>, bool),
 625
 626     // a syntactic variable that will be filled in by macro expansion.
 627     tt_nonterminal(span, ident)
 628 }
 629
 630 //
 631 // Matchers are nodes defined-by and recognized-by the main rust parser and
 632 // language, but they're only ever found inside syntax-extension invocations;
 633 // indeed, the only thing that ever _activates_ the rules in the rust parser
 634 // for parsing a matcher is a matcher looking for the 'matchers' nonterminal
 635 // itself. Matchers represent a small sub-language for pattern-matching
 636 // token-trees, and are thus primarily used by the macro-defining extension
 637 // itself.
 638 //
 639 // match_tok
 640 // ---------
 641 //
 642 //     A matcher that matches a single token, denoted by the token itself. So
 643 //     long as there's no $ involved.
 644 //
 645 //
 646 // match_seq
 647 // ---------
 648 //
 649 //     A matcher that matches a sequence of sub-matchers, denoted various
 650 //     possible ways:
 651 //
 652 //             $(M)*       zero or more Ms
 653 //             $(M)+       one or more Ms
 654 //             $(M),+      one or more comma-separated Ms
 655 //             $(A B C);*  zero or more semi-separated 'A B C' seqs
 656 //
 657 //
 658 // match_nonterminal
 659 // -----------------
 660 //
 661 //     A matcher that matches one of a few interesting named rust
 662 //     nonterminals, such as types, expressions, items, or raw token-trees. A
 663 //     black-box matcher on expr, for example, binds an expr to a given ident,
 664 //     and that ident can re-occur as an interpolation in the RHS of a
 665 //     macro-by-example rule. For example:
 666 //
 667 //        $foo:expr   =>     1 + $foo    // interpolate an expr
 668 //        $foo:tt     =>     $foo        // interpolate a token-tree
 669 //        $foo:tt     =>     bar! $foo   // only other valid interpolation
 670 //                                       // is in arg position for another
 671 //                                       // macro
 672 //
 673 // As a final, horrifying aside, note that macro-by-example's input is
 674 // also matched by one of these matchers. Holy self-referential! It is matched
 675 // by an match_seq, specifically this one:
 676 //
 677 //                   $( $lhs:matchers => $rhs:tt );+
 678 //
 679 // If you understand that, you have closed to loop and understand the whole
 680 // macro system. Congratulations.
 681 //
 682 pub type matcher = spanned<matcher_>;
 683
 684 #[auto_encode]
 685 #[auto_decode]
 686 #[deriving(Eq)]
 687 pub enum matcher_ {
 688     // match one token
 689     match_tok(::parse::token::Token),
 690     // match repetitions of a sequence: body, separator, zero ok?,
 691     // lo, hi position-in-match-array used:
 692     match_seq(~[matcher], Option<::parse::token::Token>, bool, uint, uint),
 693     // parse a Rust NT: name to bind, name of NT, position in match array:
 694     match_nonterminal(ident, ident, uint)
 695 }
 696
 697 pub type mac = spanned<mac_>;
 698
 699 #[auto_encode]
 700 #[auto_decode]
 701 #[deriving(Eq)]
 702 pub enum mac_ {
 703     mac_invoc_tt(@Path,~[token_tree]),   // new macro-invocation
 704 }
 705
 706 pub type lit = spanned<lit_>;
 707
 708 #[auto_encode]
 709 #[auto_decode]
 710 #[deriving(Eq)]
 711 pub enum lit_ {
 712     lit_str(@~str),
 713     lit_int(i64, int_ty),
 714     lit_uint(u64, uint_ty),
 715     lit_int_unsuffixed(i64),
 716     lit_float(@~str, float_ty),
 717     lit_float_unsuffixed(@~str),
 718     lit_nil,
 719     lit_bool(bool),
 720 }
 721
 722 // NB: If you change this, you'll probably want to change the corresponding
 723 // type structure in middle/ty.rs as well.
 724 #[auto_encode]
 725 #[auto_decode]
 726 #[deriving(Eq)]
 727 pub struct mt {
 728     ty: @Ty,
 729     mutbl: mutability,
 730 }
 731
 732 #[auto_encode]
 733 #[auto_decode]
 734 #[deriving(Eq)]
 735 pub struct ty_field_ {
 736     ident: ident,
 737     mt: mt,
 738 }
 739
 740 pub type ty_field = spanned<ty_field_>;
 741
 742 #[auto_encode]
 743 #[auto_decode]
 744 #[deriving(Eq)]
 745 pub struct ty_method {
 746     ident: ident,
 747     attrs: ~[attribute],
 748     purity: purity,
 749     decl: fn_decl,
 750     generics: Generics,
 751     self_ty: self_ty,
 752     id: node_id,
 753     span: span,
 754 }
 755
 756 #[auto_encode]
 757 #[auto_decode]
 758 #[deriving(Eq)]
 759 // A trait method is either required (meaning it doesn't have an
 760 // implementation, just a signature) or provided (meaning it has a default
 761 // implementation).
 762 pub enum trait_method {
 763     required(ty_method),
 764     provided(@method),
 765 }
 766
 767 #[auto_encode]
 768 #[auto_decode]
 769 #[deriving(Eq)]
 770 pub enum int_ty { ty_i, ty_char, ty_i8, ty_i16, ty_i32, ty_i64, }
 771
 772 impl ToStr for int_ty {
 773     fn to_str(&self) -> ~str {
 774         ::ast_util::int_ty_to_str(*self)
 775     }
 776 }
 777
 778 impl to_bytes::IterBytes for int_ty {
 779     fn iter_bytes(&self, lsb0: bool, f: to_bytes::Cb) {
 780         (*self as u8).iter_bytes(lsb0, f)
 781     }
 782 }
 783
 784 #[auto_encode]
 785 #[auto_decode]
 786 #[deriving(Eq)]
 787 pub enum uint_ty { ty_u, ty_u8, ty_u16, ty_u32, ty_u64, }
 788
 789 impl ToStr for uint_ty {
 790     fn to_str(&self) -> ~str {
 791         ::ast_util::uint_ty_to_str(*self)
 792     }
 793 }
 794
 795 impl to_bytes::IterBytes for uint_ty {
 796     fn iter_bytes(&self, lsb0: bool, f: to_bytes::Cb) {
 797         (*self as u8).iter_bytes(lsb0, f)
 798     }
 799 }
 800
 801 #[auto_encode]
 802 #[auto_decode]
 803 #[deriving(Eq)]
 804 pub enum float_ty { ty_f, ty_f32, ty_f64, }
 805
 806 impl ToStr for float_ty {
 807     fn to_str(&self) -> ~str {
 808         ::ast_util::float_ty_to_str(*self)
 809     }
 810 }
 811
 812 impl to_bytes::IterBytes for float_ty {
 813     fn iter_bytes(&self, lsb0: bool, f: to_bytes::Cb) {
 814         (*self as u8).iter_bytes(lsb0, f)
 815     }
 816 }
 817
 818 // NB Eq method appears below.
 819 #[auto_encode]
 820 #[auto_decode]
 821 #[deriving(Eq)]
 822 pub struct Ty {
 823     id: node_id,
 824     node: ty_,
 825     span: span,
 826 }
 827
 828 // Not represented directly in the AST, referred to by name through a ty_path.
 829 #[auto_encode]
 830 #[auto_decode]
 831 #[deriving(Eq)]
 832 pub enum prim_ty {
 833     ty_int(int_ty),
 834     ty_uint(uint_ty),
 835     ty_float(float_ty),
 836     ty_str,
 837     ty_bool,
 838 }
 839
 840 #[auto_encode]
 841 #[auto_decode]
 842 #[deriving(Eq)]
 843 pub enum Onceness {
 844     Once,
 845     Many
 846 }
 847
 848 impl ToStr for Onceness {
 849     fn to_str(&self) -> ~str {
 850         match *self {
 851             Once => ~"once",
 852             Many => ~"many"
 853         }
 854     }
 855 }
 856
 857 impl to_bytes::IterBytes for Onceness {
 858     fn iter_bytes(&self, lsb0: bool, f: to_bytes::Cb) {
 859         (*self as uint).iter_bytes(lsb0, f);
 860     }
 861 }
 862
 863 #[auto_encode]
 864 #[auto_decode]
 865 #[deriving(Eq)]
 866 pub struct TyClosure {
 867     sigil: Sigil,
 868     region: Option<@Lifetime>,
 869     lifetimes: OptVec<Lifetime>,
 870     purity: purity,
 871     onceness: Onceness,
 872     decl: fn_decl
 873 }
 874
 875 #[auto_encode]
 876 #[auto_decode]
 877 #[deriving(Eq)]
 878 pub struct TyBareFn {
 879     purity: purity,
 880     abis: AbiSet,
 881     lifetimes: OptVec<Lifetime>,
 882     decl: fn_decl
 883 }
 884
 885 #[auto_encode]
 886 #[auto_decode]
 887 #[deriving(Eq)]
 888 pub enum ty_ {
 889     ty_nil,
 890     ty_bot, /* bottom type */
 891     ty_box(mt),
 892     ty_uniq(mt),
 893     ty_vec(mt),
 894     ty_fixed_length_vec(mt, @expr),
 895     ty_ptr(mt),
 896     ty_rptr(Option<@Lifetime>, mt),
 897     ty_closure(@TyClosure),
 898     ty_bare_fn(@TyBareFn),
 899     ty_tup(~[@Ty]),
 900     ty_path(@Path, node_id),
 901     ty_mac(mac),
 902     // ty_infer means the type should be inferred instead of it having been
 903     // specified. This should only appear at the "top level" of a type and not
 904     // nested in one.
 905     ty_infer,
 906 }
 907
 908 impl to_bytes::IterBytes for Ty {
 909     fn iter_bytes(&self, lsb0: bool, f: to_bytes::Cb) {
 910         to_bytes::iter_bytes_2(&self.span.lo, &self.span.hi, lsb0, f);
 911     }
 912 }
 913
 914 #[auto_encode]
 915 #[auto_decode]
 916 #[deriving(Eq)]
 917 pub enum asm_dialect {
 918     asm_att,
 919     asm_intel
 920 }
 921
 922 #[auto_encode]
 923 #[auto_decode]
 924 #[deriving(Eq)]
 925 pub struct inline_asm {
 926     asm: @~str,
 927     clobbers: @~str,
 928     inputs: ~[(@~str, @expr)],
 929     outputs: ~[(@~str, @expr)],
 930     volatile: bool,
 931     alignstack: bool,
 932     dialect: asm_dialect
 933 }
 934
 935 #[auto_encode]
 936 #[auto_decode]
 937 #[deriving(Eq)]
 938 pub struct arg {
 939     is_mutbl: bool,
 940     ty: @Ty,
 941     pat: @pat,
 942     id: node_id,
 943 }
 944
 945 #[auto_encode]
 946 #[auto_decode]
 947 #[deriving(Eq)]
 948 pub struct fn_decl {
 949     inputs: ~[arg],
 950     output: @Ty,
 951     cf: ret_style,
 952 }
 953
 954 #[auto_encode]
 955 #[auto_decode]
 956 #[deriving(Eq)]
 957 pub enum purity {
 958     pure_fn, // declared with "pure fn"
 959     unsafe_fn, // declared with "unsafe fn"
 960     impure_fn, // declared with "fn"
 961     extern_fn, // declared with "extern fn"
 962 }
 963
 964 impl ToStr for purity {
 965     fn to_str(&self) -> ~str {
 966         match *self {
 967             impure_fn => ~"impure",
 968             unsafe_fn => ~"unsafe",
 969             pure_fn => ~"pure",
 970             extern_fn => ~"extern"
 971         }
 972     }
 973 }
 974
 975 impl to_bytes::IterBytes for purity {
 976     fn iter_bytes(&self, lsb0: bool, f: to_bytes::Cb) {
 977         (*self as u8).iter_bytes(lsb0, f)
 978     }
 979 }
 980
 981 #[auto_encode]
 982 #[auto_decode]
 983 #[deriving(Eq)]
 984 pub enum ret_style {
 985     noreturn, // functions with return type _|_ that always
 986               // raise an error or exit (i.e. never return to the caller)
 987     return_val, // everything else
 988 }
 989
 990 impl to_bytes::IterBytes for ret_style {
 991     fn iter_bytes(&self, lsb0: bool, f: to_bytes::Cb) {
 992         (*self as u8).iter_bytes(lsb0, f)
 993     }
 994 }
 995
 996 #[auto_encode]
 997 #[auto_decode]
 998 #[deriving(Eq)]
 999 pub enum self_ty_ {
1000     sty_static,                                // no self
1001     sty_value,                                 // `self`
1002     sty_region(Option<@Lifetime>, mutability), // `&'lt self`
1003     sty_box(mutability),                       // `@self`
1004     sty_uniq(mutability)                       // `~self`
1005 }
1006
1007 pub type self_ty = spanned<self_ty_>;
1008
1009 #[auto_encode]
1010 #[auto_decode]
1011 #[deriving(Eq)]
1012 pub struct method {
1013     ident: ident,
1014     attrs: ~[attribute],
1015     generics: Generics,
1016     self_ty: self_ty,
1017     purity: purity,
1018     decl: fn_decl,
1019     body: blk,
1020     id: node_id,
1021     span: span,
1022     self_id: node_id,
1023     vis: visibility,
1024 }
1025
1026 #[auto_encode]
1027 #[auto_decode]
1028 #[deriving(Eq)]
1029 pub struct _mod {
1030     view_items: ~[@view_item],
1031     items: ~[@item],
1032 }
1033
1034 // Foreign mods can be named or anonymous
1035 #[auto_encode]
1036 #[auto_decode]
1037 #[deriving(Eq)]
1038 pub enum foreign_mod_sort { named, anonymous }
1039
1040 #[auto_encode]
1041 #[auto_decode]
1042 #[deriving(Eq)]
1043 pub struct foreign_mod {
1044     sort: foreign_mod_sort,
1045     abis: AbiSet,
1046     view_items: ~[@view_item],
1047     items: ~[@foreign_item],
1048 }
1049
1050 #[auto_encode]
1051 #[auto_decode]
1052 #[deriving(Eq)]
1053 pub struct variant_arg {
1054     ty: @Ty,
1055     id: node_id,
1056 }
1057
1058 #[auto_encode]
1059 #[auto_decode]
1060 #[deriving(Eq)]
1061 pub enum variant_kind {
1062     tuple_variant_kind(~[variant_arg]),
1063     struct_variant_kind(@struct_def),
1064 }
1065
1066 #[auto_encode]
1067 #[auto_decode]
1068 #[deriving(Eq)]
1069 pub struct enum_def {
1070     variants: ~[variant],
1071 }
1072
1073 #[auto_encode]
1074 #[auto_decode]
1075 #[deriving(Eq)]
1076 pub struct variant_ {
1077     name: ident,
1078     attrs: ~[attribute],
1079     kind: variant_kind,
1080     id: node_id,
1081     disr_expr: Option<@expr>,
1082     vis: visibility,
1083 }
1084
1085 pub type variant = spanned<variant_>;
1086
1087 #[auto_encode]
1088 #[auto_decode]
1089 #[deriving(Eq)]
1090 pub struct path_list_ident_ {
1091     name: ident,
1092     id: node_id,
1093 }
1094
1095 pub type path_list_ident = spanned<path_list_ident_>;
1096
1097 pub type view_path = spanned<view_path_>;
1098
1099 #[auto_encode]
1100 #[auto_decode]
1101 #[deriving(Eq)]
1102 pub enum view_path_ {
1103
1104     // quux = foo::bar::baz
1105     //
1106     // or just
1107     //
1108     // foo::bar::baz  (with 'baz =' implicitly on the left)
1109     view_path_simple(ident, @Path, node_id),
1110
1111     // foo::bar::*
1112     view_path_glob(@Path, node_id),
1113
1114     // foo::bar::{a,b,c}
1115     view_path_list(@Path, ~[path_list_ident], node_id)
1116 }
1117
1118 #[auto_encode]
1119 #[auto_decode]
1120 #[deriving(Eq)]
1121 pub struct view_item {
1122     node: view_item_,
1123     attrs: ~[attribute],
1124     vis: visibility,
1125     span: span,
1126 }
1127
1128 #[auto_encode]
1129 #[auto_decode]
1130 #[deriving(Eq)]
1131 pub enum view_item_ {
1132     view_item_extern_mod(ident, ~[@meta_item], node_id),
1133     view_item_use(~[@view_path]),
1134 }
1135
1136 // Meta-data associated with an item
1137 pub type attribute = spanned<attribute_>;
1138
1139 // Distinguishes between attributes that decorate items and attributes that
1140 // are contained as statements within items. These two cases need to be
1141 // distinguished for pretty-printing.
1142 #[auto_encode]
1143 #[auto_decode]
1144 #[deriving(Eq)]
1145 pub enum attr_style { attr_outer, attr_inner, }
1146
1147 // doc-comments are promoted to attributes that have is_sugared_doc = true
1148 #[auto_encode]
1149 #[auto_decode]
1150 #[deriving(Eq)]
1151 pub struct attribute_ {
1152     style: attr_style,
1153     value: @meta_item,
1154     is_sugared_doc: bool,
1155 }
1156
1157 /*
1158   trait_refs appear in impls.
1159   resolve maps each trait_ref's ref_id to its defining trait; that's all
1160   that the ref_id is for. The impl_id maps to the "self type" of this impl.
1161   If this impl is an item_impl, the impl_id is redundant (it could be the
1162   same as the impl's node id).
1163  */
1164 #[auto_encode]
1165 #[auto_decode]
1166 #[deriving(Eq)]
1167 pub struct trait_ref {
1168     path: @Path,
1169     ref_id: node_id,
1170 }
1171
1172 #[auto_encode]
1173 #[auto_decode]
1174 #[deriving(Eq)]
1175 pub enum visibility { public, private, inherited }
1176
1177 impl visibility {
1178     fn inherit_from(&self, parent_visibility: visibility) -> visibility {
1179         match self {
1180             &inherited => parent_visibility,
1181             &public | &private => *self
1182         }
1183     }
1184 }
1185
1186 #[auto_encode]
1187 #[auto_decode]
1188 #[deriving(Eq)]
1189 pub struct struct_field_ {
1190     kind: struct_field_kind,
1191     id: node_id,
1192     ty: @Ty,
1193     attrs: ~[attribute],
1194 }
1195
1196 pub type struct_field = spanned<struct_field_>;
1197
1198 #[auto_encode]
1199 #[auto_decode]
1200 #[deriving(Eq)]
1201 pub enum struct_field_kind {
1202     named_field(ident, struct_mutability, visibility),
1203     unnamed_field   // element of a tuple-like struct
1204 }
1205
1206 #[auto_encode]
1207 #[auto_decode]
1208 #[deriving(Eq)]
1209 pub struct struct_def {
1210     fields: ~[@struct_field], /* fields, not including ctor */
1211     /* ID of the constructor. This is only used for tuple- or enum-like
1212      * structs. */
1213     ctor_id: Option<node_id>
1214 }
1215
1216 /*
1217   FIXME (#3300): Should allow items to be anonymous. Right now
1218   we just use dummy names for anon items.
1219  */
1220 #[auto_encode]
1221 #[auto_decode]
1222 #[deriving(Eq)]
1223 pub struct item {
1224     ident: ident,
1225     attrs: ~[attribute],
1226     id: node_id,
1227     node: item_,
1228     vis: visibility,
1229     span: span,
1230 }
1231
1232 #[auto_encode]
1233 #[auto_decode]
1234 #[deriving(Eq)]
1235 pub enum item_ {
1236     item_const(@Ty, @expr),
1237     item_fn(fn_decl, purity, AbiSet, Generics, blk),
1238     item_mod(_mod),
1239     item_foreign_mod(foreign_mod),
1240     item_ty(@Ty, Generics),
1241     item_enum(enum_def, Generics),
1242     item_struct(@struct_def, Generics),
1243     item_trait(Generics, ~[@trait_ref], ~[trait_method]),
1244     item_impl(Generics,
1245               Option<@trait_ref>, // (optional) trait this impl implements
1246               @Ty, // self
1247               ~[@method]),
1248     // a macro invocation (which includes macro definition)
1249     item_mac(mac),
1250 }
1251
1252 #[auto_encode]
1253 #[auto_decode]
1254 #[deriving(Eq)]
1255 pub enum struct_mutability { struct_mutable, struct_immutable }
1256
1257 impl to_bytes::IterBytes for struct_mutability {
1258     fn iter_bytes(&self, lsb0: bool, f: to_bytes::Cb) {
1259         (*self as u8).iter_bytes(lsb0, f)
1260     }
1261 }
1262
1263 #[auto_encode]
1264 #[auto_decode]
1265 #[deriving(Eq)]
1266 pub struct foreign_item {
1267     ident: ident,
1268     attrs: ~[attribute],
1269     node: foreign_item_,
1270     id: node_id,
1271     span: span,
1272     vis: visibility,
1273 }
1274
1275 #[auto_encode]
1276 #[auto_decode]
1277 #[deriving(Eq)]
1278 pub enum foreign_item_ {
1279     foreign_item_fn(fn_decl, purity, Generics),
1280     foreign_item_const(@Ty)
1281 }
1282
1283 // The data we save and restore about an inlined item or method.  This is not
1284 // part of the AST that we parse from a file, but it becomes part of the tree
1285 // that we trans.
1286 #[auto_encode]
1287 #[auto_decode]
1288 #[deriving(Eq)]
1289 pub enum inlined_item {
1290     ii_item(@item),
1291     ii_method(def_id /* impl id */, @method),
1292     ii_foreign(@foreign_item),
1293 }
1294
1295 /* hold off on tests ... they appear in a later merge.
1296 #[cfg(test)]
1297 mod test {
1298     use core::option::{None, Option, Some};
1299     use core::uint;
1300     use std;
1301     use codemap::*;
1302     use super::*;
1303
1304
1305     #[test] fn xorpush_test () {
1306         let mut s = ~[];
1307         xorPush(&mut s,14);
1308         assert_eq!(s,~[14]);
1309         xorPush(&mut s,14);
1310         assert_eq!(s,~[]);
1311         xorPush(&mut s,14);
1312         assert_eq!(s,~[14]);
1313         xorPush(&mut s,15);
1314         assert_eq!(s,~[14,15]);
1315         xorPush (&mut s,16);
1316         assert_eq! (s,~[14,15,16]);
1317         xorPush (&mut s,16);
1318         assert_eq! (s,~[14,15]);
1319         xorPush (&mut s,15);
1320         assert_eq! (s,~[14]);
1321     }
1322
1323     #[test] fn test_marksof () {
1324         let stopname = uints_to_name(&~[12,14,78]);
1325         let name1 = uints_to_name(&~[4,9,7]);
1326         assert_eq!(marksof (MT,stopname),~[]);
1327         assert_eq! (marksof (Mark (4,@Mark(98,@MT)),stopname),~[4,98]);
1328         // does xoring work?
1329         assert_eq! (marksof (Mark (5, @Mark (5, @Mark (16,@MT))),stopname),
1330                      ~[16]);
1331         // does nested xoring work?
1332         assert_eq! (marksof (Mark (5,
1333                                     @Mark (10,
1334                                            @Mark (10,
1335                                                   @Mark (5,
1336                                                          @Mark (16,@MT))))),
1337                               stopname),
1338                      ~[16]);
1339         // stop has no effect on marks
1340         assert_eq! (marksof (Mark (9, @Mark (14, @Mark (12, @MT))),stopname),
1341                      ~[9,14,12]);
1342         // rename where stop doesn't match:
1343         assert_eq! (marksof (Mark (9, @Rename
1344                                     (name1,
1345                                      @Mark (4, @MT),
1346                                      uints_to_name(&~[100,101,102]),
1347                                      @Mark (14, @MT))),
1348                               stopname),
1349                      ~[9,14]);
1350         // rename where stop does match
1351         ;
1352         assert_eq! (marksof (Mark(9, @Rename (name1,
1353                                                @Mark (4, @MT),
1354                                                stopname,
1355                                                @Mark (14, @MT))),
1356                               stopname),
1357                      ~[9]);
1358     }
1359
1360     // are ASTs encodable?
1361     #[test] fn check_asts_encodable() {
1362         let bogus_span = span {lo:BytePos(10),
1363                                hi:BytePos(20),
1364                                expn_info:None};
1365         let e : crate =
1366             spanned{
1367             node: crate_{
1368                 module: _mod {view_items: ~[], items: ~[]},
1369                 attrs: ~[],
1370                 config: ~[]
1371             },
1372             span: bogus_span};
1373         // doesn't matter which encoder we use....
1374         let _f = (@e as @std::serialize::Encodable<std::json::Encoder>);
1375     }
1376
1377
1378 }
1379
1380 */