src/libsyntax/parse/token.rs

   1 // Copyright 2012-2013 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 pub use self::BinOpToken::*;
  12 pub use self::Nonterminal::*;
  13 pub use self::DelimToken::*;
  14 pub use self::Lit::*;
  15 pub use self::Token::*;
  16
  17 use ast::{self};
  18 use parse::ParseSess;
  19 use print::pprust;
  20 use ptr::P;
  21 use serialize::{Decodable, Decoder, Encodable, Encoder};
  22 use symbol::keywords;
  23 use syntax::parse::parse_stream_from_source_str;
  24 use syntax_pos::{self, Span, FileName};
  25 use syntax_pos::symbol::{self, Symbol};
  26 use tokenstream::{self, DelimSpan, TokenStream, TokenTree};
  27
  28 use std::{cmp, fmt};
  29 use std::mem;
  30 use rustc_data_structures::sync::{Lrc, Lock};
  31
  32 #[derive(Clone, PartialEq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
  33 pub enum BinOpToken {
  34     Plus,
  35     Minus,
  36     Star,
  37     Slash,
  38     Percent,
  39     Caret,
  40     And,
  41     Or,
  42     Shl,
  43     Shr,
  44 }
  45
  46 /// A delimiter token
  47 #[derive(Clone, PartialEq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
  48 pub enum DelimToken {
  49     /// A round parenthesis: `(` or `)`
  50     Paren,
  51     /// A square bracket: `[` or `]`
  52     Bracket,
  53     /// A curly brace: `{` or `}`
  54     Brace,
  55     /// An empty delimiter
  56     NoDelim,
  57 }
  58
  59 impl DelimToken {
  60     pub fn len(self) -> usize {
  61         if self == NoDelim { 0 } else { 1 }
  62     }
  63
  64     pub fn is_empty(self) -> bool {
  65         self == NoDelim
  66     }
  67 }
  68
  69 #[derive(Clone, PartialEq, RustcEncodable, RustcDecodable, Hash, Debug, Copy)]
  70 pub enum Lit {
  71     Byte(ast::Name),
  72     Char(ast::Name),
  73     Integer(ast::Name),
  74     Float(ast::Name),
  75     Str_(ast::Name),
  76     StrRaw(ast::Name, u16), /* raw str delimited by n hash symbols */
  77     ByteStr(ast::Name),
  78     ByteStrRaw(ast::Name, u16), /* raw byte str delimited by n hash symbols */
  79 }
  80
  81 impl Lit {
  82     crate fn literal_name(&self) -> &'static str {
  83         match *self {
  84             Byte(_) => "byte literal",
  85             Char(_) => "char literal",
  86             Integer(_) => "integer literal",
  87             Float(_) => "float literal",
  88             Str_(_) | StrRaw(..) => "string literal",
  89             ByteStr(_) | ByteStrRaw(..) => "byte string literal"
  90         }
  91     }
  92
  93     // See comments in `interpolated_to_tokenstream` for why we care about
  94     // *probably* equal here rather than actual equality
  95     fn probably_equal_for_proc_macro(&self, other: &Lit) -> bool {
  96         mem::discriminant(self) == mem::discriminant(other)
  97     }
  98 }
  99
 100 pub(crate) fn ident_can_begin_expr(ident: ast::Ident, is_raw: bool) -> bool {
 101     let ident_token: Token = Ident(ident, is_raw);
 102
 103     !ident_token.is_reserved_ident() ||
 104     ident_token.is_path_segment_keyword() ||
 105     [
 106         keywords::Async.name(),
 107         keywords::Do.name(),
 108         keywords::Box.name(),
 109         keywords::Break.name(),
 110         keywords::Continue.name(),
 111         keywords::False.name(),
 112         keywords::For.name(),
 113         keywords::If.name(),
 114         keywords::Loop.name(),
 115         keywords::Match.name(),
 116         keywords::Move.name(),
 117         keywords::Return.name(),
 118         keywords::True.name(),
 119         keywords::Unsafe.name(),
 120         keywords::While.name(),
 121         keywords::Yield.name(),
 122         keywords::Static.name(),
 123     ].contains(&ident.name)
 124 }
 125
 126 fn ident_can_begin_type(ident: ast::Ident, is_raw: bool) -> bool {
 127     let ident_token: Token = Ident(ident, is_raw);
 128
 129     !ident_token.is_reserved_ident() ||
 130     ident_token.is_path_segment_keyword() ||
 131     [
 132         keywords::Underscore.name(),
 133         keywords::For.name(),
 134         keywords::Impl.name(),
 135         keywords::Fn.name(),
 136         keywords::Unsafe.name(),
 137         keywords::Extern.name(),
 138         keywords::Typeof.name(),
 139         keywords::Dyn.name(),
 140     ].contains(&ident.name)
 141 }
 142
 143 #[derive(Clone, RustcEncodable, RustcDecodable, PartialEq, Debug)]
 144 pub enum Token {
 145     /* Expression-operator symbols. */
 146     Eq,
 147     Lt,
 148     Le,
 149     EqEq,
 150     Ne,
 151     Ge,
 152     Gt,
 153     AndAnd,
 154     OrOr,
 155     Not,
 156     Tilde,
 157     BinOp(BinOpToken),
 158     BinOpEq(BinOpToken),
 159
 160     /* Structural symbols */
 161     At,
 162     Dot,
 163     DotDot,
 164     DotDotDot,
 165     DotDotEq,
 166     Comma,
 167     Semi,
 168     Colon,
 169     ModSep,
 170     RArrow,
 171     LArrow,
 172     FatArrow,
 173     Pound,
 174     Dollar,
 175     Question,
 176     /// Used by proc macros for representing lifetimes, not generated by lexer right now.
 177     SingleQuote,
 178     /// An opening delimiter, eg. `{`
 179     OpenDelim(DelimToken),
 180     /// A closing delimiter, eg. `}`
 181     CloseDelim(DelimToken),
 182
 183     /* Literals */
 184     Literal(Lit, Option<ast::Name>),
 185
 186     /* Name components */
 187     Ident(ast::Ident, /* is_raw */ bool),
 188     Lifetime(ast::Ident),
 189
 190     // The `LazyTokenStream` is a pure function of the `Nonterminal`,
 191     // and so the `LazyTokenStream` can be ignored by Eq, Hash, etc.
 192     Interpolated(Lrc<(Nonterminal, LazyTokenStream)>),
 193     // Can be expanded into several tokens.
 194     /// Doc comment
 195     DocComment(ast::Name),
 196
 197     // Junk. These carry no data because we don't really care about the data
 198     // they *would* carry, and don't really want to allocate a new ident for
 199     // them. Instead, users could extract that from the associated span.
 200
 201     /// Whitespace
 202     Whitespace,
 203     /// Comment
 204     Comment,
 205     Shebang(ast::Name),
 206
 207     Eof,
 208 }
 209
 210 impl Token {
 211     pub fn interpolated(nt: Nonterminal) -> Token {
 212         Token::Interpolated(Lrc::new((nt, LazyTokenStream::new())))
 213     }
 214
 215     /// Recovers a `Token` from an `ast::Ident`. This creates a raw identifier if necessary.
 216     pub fn from_ast_ident(ident: ast::Ident) -> Token {
 217         Ident(ident, ident.is_raw_guess())
 218     }
 219
 220     crate fn is_like_plus(&self) -> bool {
 221         match *self {
 222             BinOp(Plus) | BinOpEq(Plus) => true,
 223             _ => false,
 224         }
 225     }
 226
 227     /// Returns `true` if the token can appear at the start of an expression.
 228     crate fn can_begin_expr(&self) -> bool {
 229         match *self {
 230             Ident(ident, is_raw)              =>
 231                 ident_can_begin_expr(ident, is_raw), // value name or keyword
 232             OpenDelim(..)                     | // tuple, array or block
 233             Literal(..)                       | // literal
 234             Not                               | // operator not
 235             BinOp(Minus)                      | // unary minus
 236             BinOp(Star)                       | // dereference
 237             BinOp(Or) | OrOr                  | // closure
 238             BinOp(And)                        | // reference
 239             AndAnd                            | // double reference
 240             // DotDotDot is no longer supported, but we need some way to display the error
 241             DotDot | DotDotDot | DotDotEq     | // range notation
 242             Lt | BinOp(Shl)                   | // associated path
 243             ModSep                            | // global path
 244             Lifetime(..)                      | // labeled loop
 245             Pound                             => true, // expression attributes
 246             Interpolated(ref nt) => match nt.0 {
 247                 NtLiteral(..) |
 248                 NtIdent(..)   |
 249                 NtExpr(..)    |
 250                 NtBlock(..)   |
 251                 NtPath(..)    |
 252                 NtLifetime(..) => true,
 253                 _ => false,
 254             },
 255             _ => false,
 256         }
 257     }
 258
 259     /// Returns `true` if the token can appear at the start of a type.
 260     crate fn can_begin_type(&self) -> bool {
 261         match *self {
 262             Ident(ident, is_raw)        =>
 263                 ident_can_begin_type(ident, is_raw), // type name or keyword
 264             OpenDelim(Paren)            | // tuple
 265             OpenDelim(Bracket)          | // array
 266             Not                         | // never
 267             BinOp(Star)                 | // raw pointer
 268             BinOp(And)                  | // reference
 269             AndAnd                      | // double reference
 270             Question                    | // maybe bound in trait object
 271             Lifetime(..)                | // lifetime bound in trait object
 272             Lt | BinOp(Shl)             | // associated path
 273             ModSep                      => true, // global path
 274             Interpolated(ref nt) => match nt.0 {
 275                 NtIdent(..) | NtTy(..) | NtPath(..) | NtLifetime(..) => true,
 276                 _ => false,
 277             },
 278             _ => false,
 279         }
 280     }
 281
 282     /// Returns `true` if the token can appear at the start of a generic bound.
 283     crate fn can_begin_bound(&self) -> bool {
 284         self.is_path_start() || self.is_lifetime() || self.is_keyword(keywords::For) ||
 285         self == &Question || self == &OpenDelim(Paren)
 286     }
 287
 288     /// Returns `true` if the token is any literal
 289     crate fn is_lit(&self) -> bool {
 290         match *self {
 291             Literal(..) => true,
 292             _           => false,
 293         }
 294     }
 295
 296     /// Returns `true` if the token is any literal, a minus (which can follow a literal,
 297     /// for example a '-42', or one of the boolean idents).
 298     crate fn can_begin_literal_or_bool(&self) -> bool {
 299         match *self {
 300             Literal(..)  => true,
 301             BinOp(Minus) => true,
 302             Ident(ident, false) if ident.name == keywords::True.name() => true,
 303             Ident(ident, false) if ident.name == keywords::False.name() => true,
 304             Interpolated(ref nt) => match nt.0 {
 305                 NtLiteral(..) => true,
 306                 _             => false,
 307             },
 308             _            => false,
 309         }
 310     }
 311
 312     /// Returns an identifier if this token is an identifier.
 313     pub fn ident(&self) -> Option<(ast::Ident, /* is_raw */ bool)> {
 314         match *self {
 315             Ident(ident, is_raw) => Some((ident, is_raw)),
 316             Interpolated(ref nt) => match nt.0 {
 317                 NtIdent(ident, is_raw) => Some((ident, is_raw)),
 318                 _ => None,
 319             },
 320             _ => None,
 321         }
 322     }
 323     /// Returns a lifetime identifier if this token is a lifetime.
 324     pub fn lifetime(&self) -> Option<ast::Ident> {
 325         match *self {
 326             Lifetime(ident) => Some(ident),
 327             Interpolated(ref nt) => match nt.0 {
 328                 NtLifetime(ident) => Some(ident),
 329                 _ => None,
 330             },
 331             _ => None,
 332         }
 333     }
 334     /// Returns `true` if the token is an identifier.
 335     pub fn is_ident(&self) -> bool {
 336         self.ident().is_some()
 337     }
 338     /// Returns `true` if the token is a lifetime.
 339     crate fn is_lifetime(&self) -> bool {
 340         self.lifetime().is_some()
 341     }
 342
 343     /// Returns `true` if the token is a identifier whose name is the given
 344     /// string slice.
 345     crate fn is_ident_named(&self, name: &str) -> bool {
 346         match self.ident() {
 347             Some((ident, _)) => ident.as_str() == name,
 348             None => false
 349         }
 350     }
 351
 352     /// Returns `true` if the token is an interpolated path.
 353     fn is_path(&self) -> bool {
 354         if let Interpolated(ref nt) = *self {
 355             if let NtPath(..) = nt.0 {
 356                 return true;
 357             }
 358         }
 359         false
 360     }
 361
 362     /// Returns `true` if the token is either the `mut` or `const` keyword.
 363     crate fn is_mutability(&self) -> bool {
 364         self.is_keyword(keywords::Mut) ||
 365         self.is_keyword(keywords::Const)
 366     }
 367
 368     crate fn is_qpath_start(&self) -> bool {
 369         self == &Lt || self == &BinOp(Shl)
 370     }
 371
 372     crate fn is_path_start(&self) -> bool {
 373         self == &ModSep || self.is_qpath_start() || self.is_path() ||
 374         self.is_path_segment_keyword() || self.is_ident() && !self.is_reserved_ident()
 375     }
 376
 377     /// Returns `true` if the token is a given keyword, `kw`.
 378     pub fn is_keyword(&self, kw: keywords::Keyword) -> bool {
 379         self.ident().map(|(ident, is_raw)| ident.name == kw.name() && !is_raw).unwrap_or(false)
 380     }
 381
 382     pub fn is_path_segment_keyword(&self) -> bool {
 383         match self.ident() {
 384             Some((id, false)) => id.is_path_segment_keyword(),
 385             _ => false,
 386         }
 387     }
 388
 389     // Returns true for reserved identifiers used internally for elided lifetimes,
 390     // unnamed method parameters, crate root module, error recovery etc.
 391     pub fn is_special_ident(&self) -> bool {
 392         match self.ident() {
 393             Some((id, false)) => id.is_special(),
 394             _ => false,
 395         }
 396     }
 397
 398     /// Returns `true` if the token is a keyword used in the language.
 399     crate fn is_used_keyword(&self) -> bool {
 400         match self.ident() {
 401             Some((id, false)) => id.is_used_keyword(),
 402             _ => false,
 403         }
 404     }
 405
 406     /// Returns `true` if the token is a keyword reserved for possible future use.
 407     crate fn is_unused_keyword(&self) -> bool {
 408         match self.ident() {
 409             Some((id, false)) => id.is_unused_keyword(),
 410             _ => false,
 411         }
 412     }
 413
 414     /// Returns `true` if the token is either a special identifier or a keyword.
 415     pub fn is_reserved_ident(&self) -> bool {
 416         match self.ident() {
 417             Some((id, false)) => id.is_reserved(),
 418             _ => false,
 419         }
 420     }
 421
 422     crate fn glue(self, joint: Token) -> Option<Token> {
 423         Some(match self {
 424             Eq => match joint {
 425                 Eq => EqEq,
 426                 Gt => FatArrow,
 427                 _ => return None,
 428             },
 429             Lt => match joint {
 430                 Eq => Le,
 431                 Lt => BinOp(Shl),
 432                 Le => BinOpEq(Shl),
 433                 BinOp(Minus) => LArrow,
 434                 _ => return None,
 435             },
 436             Gt => match joint {
 437                 Eq => Ge,
 438                 Gt => BinOp(Shr),
 439                 Ge => BinOpEq(Shr),
 440                 _ => return None,
 441             },
 442             Not => match joint {
 443                 Eq => Ne,
 444                 _ => return None,
 445             },
 446             BinOp(op) => match joint {
 447                 Eq => BinOpEq(op),
 448                 BinOp(And) if op == And => AndAnd,
 449                 BinOp(Or) if op == Or => OrOr,
 450                 Gt if op == Minus => RArrow,
 451                 _ => return None,
 452             },
 453             Dot => match joint {
 454                 Dot => DotDot,
 455                 DotDot => DotDotDot,
 456                 _ => return None,
 457             },
 458             DotDot => match joint {
 459                 Dot => DotDotDot,
 460                 Eq => DotDotEq,
 461                 _ => return None,
 462             },
 463             Colon => match joint {
 464                 Colon => ModSep,
 465                 _ => return None,
 466             },
 467             SingleQuote => match joint {
 468                 Ident(ident, false) => {
 469                     let name = Symbol::intern(&format!("'{}", ident));
 470                     Lifetime(symbol::Ident {
 471                         name,
 472                         span: ident.span,
 473                     })
 474                 }
 475                 _ => return None,
 476             },
 477
 478             Le | EqEq | Ne | Ge | AndAnd | OrOr | Tilde | BinOpEq(..) | At | DotDotDot |
 479             DotDotEq | Comma | Semi | ModSep | RArrow | LArrow | FatArrow | Pound | Dollar |
 480             Question | OpenDelim(..) | CloseDelim(..) => return None,
 481
 482             Literal(..) | Ident(..) | Lifetime(..) | Interpolated(..) | DocComment(..) |
 483             Whitespace | Comment | Shebang(..) | Eof => return None,
 484         })
 485     }
 486
 487     /// Returns tokens that are likely to be typed accidentally instead of the current token.
 488     /// Enables better error recovery when the wrong token is found.
 489     crate fn similar_tokens(&self) -> Option<Vec<Token>> {
 490         match *self {
 491             Comma => Some(vec![Dot, Lt]),
 492             Semi => Some(vec![Colon]),
 493             _ => None
 494         }
 495     }
 496
 497     pub fn interpolated_to_tokenstream(&self, sess: &ParseSess, span: Span)
 498         -> TokenStream
 499     {
 500         let nt = match *self {
 501             Token::Interpolated(ref nt) => nt,
 502             _ => panic!("only works on interpolated tokens"),
 503         };
 504
 505         // An `Interpolated` token means that we have a `Nonterminal`
 506         // which is often a parsed AST item. At this point we now need
 507         // to convert the parsed AST to an actual token stream, e.g.
 508         // un-parse it basically.
 509         //
 510         // Unfortunately there's not really a great way to do that in a
 511         // guaranteed lossless fashion right now. The fallback here is
 512         // to just stringify the AST node and reparse it, but this loses
 513         // all span information.
 514         //
 515         // As a result, some AST nodes are annotated with the token
 516         // stream they came from. Here we attempt to extract these
 517         // lossless token streams before we fall back to the
 518         // stringification.
 519         let mut tokens = None;
 520
 521         match nt.0 {
 522             Nonterminal::NtItem(ref item) => {
 523                 tokens = prepend_attrs(sess, &item.attrs, item.tokens.as_ref(), span);
 524             }
 525             Nonterminal::NtTraitItem(ref item) => {
 526                 tokens = prepend_attrs(sess, &item.attrs, item.tokens.as_ref(), span);
 527             }
 528             Nonterminal::NtImplItem(ref item) => {
 529                 tokens = prepend_attrs(sess, &item.attrs, item.tokens.as_ref(), span);
 530             }
 531             Nonterminal::NtIdent(ident, is_raw) => {
 532                 let token = Token::Ident(ident, is_raw);
 533                 tokens = Some(TokenTree::Token(ident.span, token).into());
 534             }
 535             Nonterminal::NtLifetime(ident) => {
 536                 let token = Token::Lifetime(ident);
 537                 tokens = Some(TokenTree::Token(ident.span, token).into());
 538             }
 539             Nonterminal::NtTT(ref tt) => {
 540                 tokens = Some(tt.clone().into());
 541             }
 542             _ => {}
 543         }
 544
 545         let tokens_for_real = nt.1.force(|| {
 546             // FIXME(#43081): Avoid this pretty-print + reparse hack
 547             let source = pprust::token_to_string(self);
 548             let filename = FileName::macro_expansion_source_code(&source);
 549             parse_stream_from_source_str(filename, source, sess, Some(span))
 550         });
 551
 552         // During early phases of the compiler the AST could get modified
 553         // directly (e.g. attributes added or removed) and the internal cache
 554         // of tokens my not be invalidated or updated. Consequently if the
 555         // "lossless" token stream disagrees with our actual stringification
 556         // (which has historically been much more battle-tested) then we go
 557         // with the lossy stream anyway (losing span information).
 558         //
 559         // Note that the comparison isn't `==` here to avoid comparing spans,
 560         // but it *also* is a "probable" equality which is a pretty weird
 561         // definition. We mostly want to catch actual changes to the AST
 562         // like a `#[cfg]` being processed or some weird `macro_rules!`
 563         // expansion.
 564         //
 565         // What we *don't* want to catch is the fact that a user-defined
 566         // literal like `0xf` is stringified as `15`, causing the cached token
 567         // stream to not be literal `==` token-wise (ignoring spans) to the
 568         // token stream we got from stringification.
 569         //
 570         // Instead the "probably equal" check here is "does each token
 571         // recursively have the same discriminant?" We basically don't look at
 572         // the token values here and assume that such fine grained token stream
 573         // modifications, including adding/removing typically non-semantic
 574         // tokens such as extra braces and commas, don't happen.
 575         if let Some(tokens) = tokens {
 576             if tokens.probably_equal_for_proc_macro(&tokens_for_real) {
 577                 return tokens
 578             }
 579             info!("cached tokens found, but they're not \"probably equal\", \
 580                    going with stringified version");
 581         }
 582         return tokens_for_real
 583     }
 584
 585     // See comments in `interpolated_to_tokenstream` for why we care about
 586     // *probably* equal here rather than actual equality
 587     crate fn probably_equal_for_proc_macro(&self, other: &Token) -> bool {
 588         if mem::discriminant(self) != mem::discriminant(other) {
 589             return false
 590         }
 591         match (self, other) {
 592             (&Eq, &Eq) |
 593             (&Lt, &Lt) |
 594             (&Le, &Le) |
 595             (&EqEq, &EqEq) |
 596             (&Ne, &Ne) |
 597             (&Ge, &Ge) |
 598             (&Gt, &Gt) |
 599             (&AndAnd, &AndAnd) |
 600             (&OrOr, &OrOr) |
 601             (&Not, &Not) |
 602             (&Tilde, &Tilde) |
 603             (&At, &At) |
 604             (&Dot, &Dot) |
 605             (&DotDot, &DotDot) |
 606             (&DotDotDot, &DotDotDot) |
 607             (&DotDotEq, &DotDotEq) |
 608             (&Comma, &Comma) |
 609             (&Semi, &Semi) |
 610             (&Colon, &Colon) |
 611             (&ModSep, &ModSep) |
 612             (&RArrow, &RArrow) |
 613             (&LArrow, &LArrow) |
 614             (&FatArrow, &FatArrow) |
 615             (&Pound, &Pound) |
 616             (&Dollar, &Dollar) |
 617             (&Question, &Question) |
 618             (&Whitespace, &Whitespace) |
 619             (&Comment, &Comment) |
 620             (&Eof, &Eof) => true,
 621
 622             (&BinOp(a), &BinOp(b)) |
 623             (&BinOpEq(a), &BinOpEq(b)) => a == b,
 624
 625             (&OpenDelim(a), &OpenDelim(b)) |
 626             (&CloseDelim(a), &CloseDelim(b)) => a == b,
 627
 628             (&DocComment(a), &DocComment(b)) |
 629             (&Shebang(a), &Shebang(b)) => a == b,
 630
 631             (&Lifetime(a), &Lifetime(b)) => a.name == b.name,
 632             (&Ident(a, b), &Ident(c, d)) => a.name == c.name && b == d,
 633
 634             (&Literal(ref a, b), &Literal(ref c, d)) => {
 635                 b == d && a.probably_equal_for_proc_macro(c)
 636             }
 637
 638             (&Interpolated(_), &Interpolated(_)) => false,
 639
 640             _ => panic!("forgot to add a token?"),
 641         }
 642     }
 643 }
 644
 645 #[derive(Clone, RustcEncodable, RustcDecodable)]
 646 /// For interpolation during macro expansion.
 647 pub enum Nonterminal {
 648     NtItem(P<ast::Item>),
 649     NtBlock(P<ast::Block>),
 650     NtStmt(ast::Stmt),
 651     NtPat(P<ast::Pat>),
 652     NtExpr(P<ast::Expr>),
 653     NtTy(P<ast::Ty>),
 654     NtIdent(ast::Ident, /* is_raw */ bool),
 655     NtLifetime(ast::Ident),
 656     NtLiteral(P<ast::Expr>),
 657     /// Stuff inside brackets for attributes
 658     NtMeta(ast::MetaItem),
 659     NtPath(ast::Path),
 660     NtVis(ast::Visibility),
 661     NtTT(TokenTree),
 662     // These are not exposed to macros, but are used by quasiquote.
 663     NtArm(ast::Arm),
 664     NtImplItem(ast::ImplItem),
 665     NtTraitItem(ast::TraitItem),
 666     NtForeignItem(ast::ForeignItem),
 667     NtGenerics(ast::Generics),
 668     NtWhereClause(ast::WhereClause),
 669     NtArg(ast::Arg),
 670 }
 671
 672 impl PartialEq for Nonterminal {
 673     fn eq(&self, rhs: &Self) -> bool {
 674         match (self, rhs) {
 675             (NtIdent(ident_lhs, is_raw_lhs), NtIdent(ident_rhs, is_raw_rhs)) =>
 676                 ident_lhs == ident_rhs && is_raw_lhs == is_raw_rhs,
 677             (NtLifetime(ident_lhs), NtLifetime(ident_rhs)) => ident_lhs == ident_rhs,
 678             (NtTT(tt_lhs), NtTT(tt_rhs)) => tt_lhs == tt_rhs,
 679             // FIXME: Assume that all "complex" nonterminal are not equal, we can't compare them
 680             // correctly based on data from AST. This will prevent them from matching each other
 681             // in macros. The comparison will become possible only when each nonterminal has an
 682             // attached token stream from which it was parsed.
 683             _ => false,
 684         }
 685     }
 686 }
 687
 688 impl fmt::Debug for Nonterminal {
 689     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 690         match *self {
 691             NtItem(..) => f.pad("NtItem(..)"),
 692             NtBlock(..) => f.pad("NtBlock(..)"),
 693             NtStmt(..) => f.pad("NtStmt(..)"),
 694             NtPat(..) => f.pad("NtPat(..)"),
 695             NtExpr(..) => f.pad("NtExpr(..)"),
 696             NtTy(..) => f.pad("NtTy(..)"),
 697             NtIdent(..) => f.pad("NtIdent(..)"),
 698             NtLiteral(..) => f.pad("NtLiteral(..)"),
 699             NtMeta(..) => f.pad("NtMeta(..)"),
 700             NtPath(..) => f.pad("NtPath(..)"),
 701             NtTT(..) => f.pad("NtTT(..)"),
 702             NtArm(..) => f.pad("NtArm(..)"),
 703             NtImplItem(..) => f.pad("NtImplItem(..)"),
 704             NtTraitItem(..) => f.pad("NtTraitItem(..)"),
 705             NtForeignItem(..) => f.pad("NtForeignItem(..)"),
 706             NtGenerics(..) => f.pad("NtGenerics(..)"),
 707             NtWhereClause(..) => f.pad("NtWhereClause(..)"),
 708             NtArg(..) => f.pad("NtArg(..)"),
 709             NtVis(..) => f.pad("NtVis(..)"),
 710             NtLifetime(..) => f.pad("NtLifetime(..)"),
 711         }
 712     }
 713 }
 714
 715 crate fn is_op(tok: &Token) -> bool {
 716     match *tok {
 717         OpenDelim(..) | CloseDelim(..) | Literal(..) | DocComment(..) |
 718         Ident(..) | Lifetime(..) | Interpolated(..) |
 719         Whitespace | Comment | Shebang(..) | Eof => false,
 720         _ => true,
 721     }
 722 }
 723
 724 #[derive(Clone)]
 725 pub struct LazyTokenStream(Lock<Option<TokenStream>>);
 726
 727 impl cmp::Eq for LazyTokenStream {}
 728 impl PartialEq for LazyTokenStream {
 729     fn eq(&self, _other: &LazyTokenStream) -> bool {
 730         true
 731     }
 732 }
 733
 734 impl fmt::Debug for LazyTokenStream {
 735     fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
 736         fmt::Debug::fmt(&self.clone().0.into_inner(), f)
 737     }
 738 }
 739
 740 impl LazyTokenStream {
 741     fn new() -> Self {
 742         LazyTokenStream(Lock::new(None))
 743     }
 744
 745     fn force<F: FnOnce() -> TokenStream>(&self, f: F) -> TokenStream {
 746         let mut opt_stream = self.0.lock();
 747         if opt_stream.is_none() {
 748             *opt_stream = Some(f());
 749         }
 750         opt_stream.clone().unwrap()
 751     }
 752 }
 753
 754 impl Encodable for LazyTokenStream {
 755     fn encode<S: Encoder>(&self, _: &mut S) -> Result<(), S::Error> {
 756         Ok(())
 757     }
 758 }
 759
 760 impl Decodable for LazyTokenStream {
 761     fn decode<D: Decoder>(_: &mut D) -> Result<LazyTokenStream, D::Error> {
 762         Ok(LazyTokenStream::new())
 763     }
 764 }
 765
 766 impl ::std::hash::Hash for LazyTokenStream {
 767     fn hash<H: ::std::hash::Hasher>(&self, _hasher: &mut H) {}
 768 }
 769
 770 fn prepend_attrs(sess: &ParseSess,
 771                  attrs: &[ast::Attribute],
 772                  tokens: Option<&tokenstream::TokenStream>,
 773                  span: syntax_pos::Span)
 774     -> Option<tokenstream::TokenStream>
 775 {
 776     let tokens = tokens?;
 777     if attrs.len() == 0 {
 778         return Some(tokens.clone())
 779     }
 780     let mut builder = tokenstream::TokenStreamBuilder::new();
 781     for attr in attrs {
 782         assert_eq!(attr.style, ast::AttrStyle::Outer,
 783                    "inner attributes should prevent cached tokens from existing");
 784
 785         let source = pprust::attr_to_string(attr);
 786         let macro_filename = FileName::macro_expansion_source_code(&source);
 787         if attr.is_sugared_doc {
 788             let stream = parse_stream_from_source_str(
 789                 macro_filename,
 790                 source,
 791                 sess,
 792                 Some(span),
 793             );
 794             builder.push(stream);
 795             continue
 796         }
 797
 798         // synthesize # [ $path $tokens ] manually here
 799         let mut brackets = tokenstream::TokenStreamBuilder::new();
 800
 801         // For simple paths, push the identifier directly
 802         if attr.path.segments.len() == 1 && attr.path.segments[0].args.is_none() {
 803             let ident = attr.path.segments[0].ident;
 804             let token = Ident(ident, ident.as_str().starts_with("r#"));
 805             brackets.push(tokenstream::TokenTree::Token(ident.span, token));
 806
 807         // ... and for more complicated paths, fall back to a reparse hack that
 808         // should eventually be removed.
 809         } else {
 810             let stream = parse_stream_from_source_str(
 811                 macro_filename,
 812                 source,
 813                 sess,
 814                 Some(span),
 815             );
 816             brackets.push(stream);
 817         }
 818
 819         brackets.push(attr.tokens.clone());
 820
 821         let tokens = tokenstream::Delimited {
 822             delim: DelimToken::Bracket,
 823             tts: brackets.build().into(),
 824         };
 825         // The span we list here for `#` and for `[ ... ]` are both wrong in
 826         // that it encompasses more than each token, but it hopefully is "good
 827         // enough" for now at least.
 828         builder.push(tokenstream::TokenTree::Token(attr.span, Pound));
 829         let delim_span = DelimSpan::from_single(attr.span);
 830         builder.push(tokenstream::TokenTree::Delimited(delim_span, tokens));
 831     }
 832     builder.push(tokens.clone());
 833     Some(builder.build())
 834 }