src/libsyntax/parse/token.rs

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