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