src/libsyntax/parse/token.rs

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