compiler/rustc_expand/src/mbe/macro_rules.rs

   1 use crate::base::{DummyResult, ExtCtxt, MacResult, TTMacroExpander};
   2 use crate::base::{SyntaxExtension, SyntaxExtensionKind};
   3 use crate::expand::{ensure_complete_parse, parse_ast_fragment, AstFragment, AstFragmentKind};
   4 use crate::mbe;
   5 use crate::mbe::diagnostics::{annotate_doc_comment, parse_failure_msg};
   6 use crate::mbe::macro_check;
   7 use crate::mbe::macro_parser::{Error, ErrorReported, Failure, Success, TtParser};
   8 use crate::mbe::macro_parser::{MatchedSeq, MatchedTokenTree, MatcherLoc};
   9 use crate::mbe::transcribe::transcribe;
  10
  11 use rustc_ast as ast;
  12 use rustc_ast::token::{self, Delimiter, NonterminalKind, Token, TokenKind, TokenKind::*};
  13 use rustc_ast::tokenstream::{DelimSpan, TokenStream};
  14 use rustc_ast::{NodeId, DUMMY_NODE_ID};
  15 use rustc_ast_pretty::pprust;
  16 use rustc_attr::{self as attr, TransparencyError};
  17 use rustc_data_structures::fx::{FxHashMap, FxIndexMap};
  18 use rustc_errors::{Applicability, ErrorGuaranteed};
  19 use rustc_feature::Features;
  20 use rustc_lint_defs::builtin::{
  21     RUST_2021_INCOMPATIBLE_OR_PATTERNS, SEMICOLON_IN_EXPRESSIONS_FROM_MACROS,
  22 };
  23 use rustc_lint_defs::BuiltinLintDiagnostics;
  24 use rustc_parse::parser::{Parser, Recovery};
  25 use rustc_session::parse::ParseSess;
  26 use rustc_session::Session;
  27 use rustc_span::edition::Edition;
  28 use rustc_span::hygiene::Transparency;
  29 use rustc_span::symbol::{kw, sym, Ident, MacroRulesNormalizedIdent};
  30 use rustc_span::Span;
  31
  32 use std::borrow::Cow;
  33 use std::collections::hash_map::Entry;
  34 use std::{mem, slice};
  35
  36 use super::diagnostics;
  37 use super::macro_parser::{NamedMatches, NamedParseResult};
  38
  39 pub(crate) struct ParserAnyMacro<'a> {
  40     parser: Parser<'a>,
  41
  42     /// Span of the expansion site of the macro this parser is for
  43     site_span: Span,
  44     /// The ident of the macro we're parsing
  45     macro_ident: Ident,
  46     lint_node_id: NodeId,
  47     is_trailing_mac: bool,
  48     arm_span: Span,
  49     /// Whether or not this macro is defined in the current crate
  50     is_local: bool,
  51 }
  52
  53 impl<'a> ParserAnyMacro<'a> {
  54     pub(crate) fn make(mut self: Box<ParserAnyMacro<'a>>, kind: AstFragmentKind) -> AstFragment {
  55         let ParserAnyMacro {
  56             site_span,
  57             macro_ident,
  58             ref mut parser,
  59             lint_node_id,
  60             arm_span,
  61             is_trailing_mac,
  62             is_local,
  63         } = *self;
  64         let snapshot = &mut parser.create_snapshot_for_diagnostic();
  65         let fragment = match parse_ast_fragment(parser, kind) {
  66             Ok(f) => f,
  67             Err(err) => {
  68                 diagnostics::emit_frag_parse_err(err, parser, snapshot, site_span, arm_span, kind);
  69                 return kind.dummy(site_span);
  70             }
  71         };
  72
  73         // We allow semicolons at the end of expressions -- e.g., the semicolon in
  74         // `macro_rules! m { () => { panic!(); } }` isn't parsed by `.parse_expr()`,
  75         // but `m!()` is allowed in expression positions (cf. issue #34706).
  76         if kind == AstFragmentKind::Expr && parser.token == token::Semi {
  77             if is_local {
  78                 parser.sess.buffer_lint_with_diagnostic(
  79                     SEMICOLON_IN_EXPRESSIONS_FROM_MACROS,
  80                     parser.token.span,
  81                     lint_node_id,
  82                     "trailing semicolon in macro used in expression position",
  83                     BuiltinLintDiagnostics::TrailingMacro(is_trailing_mac, macro_ident),
  84                 );
  85             }
  86             parser.bump();
  87         }
  88
  89         // Make sure we don't have any tokens left to parse so we don't silently drop anything.
  90         let path = ast::Path::from_ident(macro_ident.with_span_pos(site_span));
  91         ensure_complete_parse(parser, &path, kind.name(), site_span);
  92         fragment
  93     }
  94 }
  95
  96 struct MacroRulesMacroExpander {
  97     node_id: NodeId,
  98     name: Ident,
  99     span: Span,
 100     transparency: Transparency,
 101     lhses: Vec<Vec<MatcherLoc>>,
 102     rhses: Vec<mbe::TokenTree>,
 103     valid: bool,
 104 }
 105
 106 impl TTMacroExpander for MacroRulesMacroExpander {
 107     fn expand<'cx>(
 108         &self,
 109         cx: &'cx mut ExtCtxt<'_>,
 110         sp: Span,
 111         input: TokenStream,
 112     ) -> Box<dyn MacResult + 'cx> {
 113         if !self.valid {
 114             return DummyResult::any(sp);
 115         }
 116         expand_macro(
 117             cx,
 118             sp,
 119             self.span,
 120             self.node_id,
 121             self.name,
 122             self.transparency,
 123             input,
 124             &self.lhses,
 125             &self.rhses,
 126         )
 127     }
 128 }
 129
 130 fn macro_rules_dummy_expander<'cx>(
 131     _: &'cx mut ExtCtxt<'_>,
 132     span: Span,
 133     _: TokenStream,
 134 ) -> Box<dyn MacResult + 'cx> {
 135     DummyResult::any(span)
 136 }
 137
 138 fn trace_macros_note(cx_expansions: &mut FxIndexMap<Span, Vec<String>>, sp: Span, message: String) {
 139     let sp = sp.macro_backtrace().last().map_or(sp, |trace| trace.call_site);
 140     cx_expansions.entry(sp).or_default().push(message);
 141 }
 142
 143 pub(super) trait Tracker<'matcher> {
 144     /// This is called before trying to match next MatcherLoc on the current token.
 145     fn before_match_loc(&mut self, parser: &TtParser, matcher: &'matcher MatcherLoc);
 146
 147     /// This is called after an arm has been parsed, either successfully or unsuccessfully. When this is called,
 148     /// `before_match_loc` was called at least once (with a `MatcherLoc::Eof`).
 149     fn after_arm(&mut self, result: &NamedParseResult);
 150
 151     /// For tracing.
 152     fn description() -> &'static str;
 153
 154     fn recovery() -> Recovery;
 155 }
 156
 157 /// A noop tracker that is used in the hot path of the expansion, has zero overhead thanks to monomorphization.
 158 pub(super) struct NoopTracker;
 159
 160 impl<'matcher> Tracker<'matcher> for NoopTracker {
 161     fn before_match_loc(&mut self, _: &TtParser, _: &'matcher MatcherLoc) {}
 162     fn after_arm(&mut self, _: &NamedParseResult) {}
 163     fn description() -> &'static str {
 164         "none"
 165     }
 166     fn recovery() -> Recovery {
 167         Recovery::Forbidden
 168     }
 169 }
 170
 171 /// Expands the rules based macro defined by `lhses` and `rhses` for a given
 172 /// input `arg`.
 173 #[instrument(skip(cx, transparency, arg, lhses, rhses))]
 174 fn expand_macro<'cx>(
 175     cx: &'cx mut ExtCtxt<'_>,
 176     sp: Span,
 177     def_span: Span,
 178     node_id: NodeId,
 179     name: Ident,
 180     transparency: Transparency,
 181     arg: TokenStream,
 182     lhses: &[Vec<MatcherLoc>],
 183     rhses: &[mbe::TokenTree],
 184 ) -> Box<dyn MacResult + 'cx> {
 185     let sess = &cx.sess.parse_sess;
 186     // Macros defined in the current crate have a real node id,
 187     // whereas macros from an external crate have a dummy id.
 188     let is_local = node_id != DUMMY_NODE_ID;
 189
 190     if cx.trace_macros() {
 191         let msg = format!("expanding `{}! {{ {} }}`", name, pprust::tts_to_string(&arg));
 192         trace_macros_note(&mut cx.expansions, sp, msg);
 193     }
 194
 195     // Track nothing for the best performance.
 196     let try_success_result = try_match_macro(sess, name, &arg, lhses, &mut NoopTracker);
 197
 198     match try_success_result {
 199         Ok((i, named_matches)) => {
 200             let (rhs, rhs_span): (&mbe::Delimited, DelimSpan) = match &rhses[i] {
 201                 mbe::TokenTree::Delimited(span, delimited) => (&delimited, *span),
 202                 _ => cx.span_bug(sp, "malformed macro rhs"),
 203             };
 204             let arm_span = rhses[i].span();
 205
 206             let rhs_spans = rhs.tts.iter().map(|t| t.span()).collect::<Vec<_>>();
 207             // rhs has holes ( `$id` and `$(...)` that need filled)
 208             let mut tts = match transcribe(cx, &named_matches, &rhs, rhs_span, transparency) {
 209                 Ok(tts) => tts,
 210                 Err(mut err) => {
 211                     err.emit();
 212                     return DummyResult::any(arm_span);
 213                 }
 214             };
 215
 216             // Replace all the tokens for the corresponding positions in the macro, to maintain
 217             // proper positions in error reporting, while maintaining the macro_backtrace.
 218             if rhs_spans.len() == tts.len() {
 219                 tts = tts.map_enumerated(|i, tt| {
 220                     let mut tt = tt.clone();
 221                     let mut sp = rhs_spans[i];
 222                     sp = sp.with_ctxt(tt.span().ctxt());
 223                     tt.set_span(sp);
 224                     tt
 225                 });
 226             }
 227
 228             if cx.trace_macros() {
 229                 let msg = format!("to `{}`", pprust::tts_to_string(&tts));
 230                 trace_macros_note(&mut cx.expansions, sp, msg);
 231             }
 232
 233             let mut p = Parser::new(sess, tts, false, None);
 234             p.last_type_ascription = cx.current_expansion.prior_type_ascription;
 235
 236             if is_local {
 237                 cx.resolver.record_macro_rule_usage(node_id, i);
 238             }
 239
 240             // Let the context choose how to interpret the result.
 241             // Weird, but useful for X-macros.
 242             return Box::new(ParserAnyMacro {
 243                 parser: p,
 244
 245                 // Pass along the original expansion site and the name of the macro
 246                 // so we can print a useful error message if the parse of the expanded
 247                 // macro leaves unparsed tokens.
 248                 site_span: sp,
 249                 macro_ident: name,
 250                 lint_node_id: cx.current_expansion.lint_node_id,
 251                 is_trailing_mac: cx.current_expansion.is_trailing_mac,
 252                 arm_span,
 253                 is_local,
 254             });
 255         }
 256         Err(CanRetry::No(_)) => {
 257             debug!("Will not retry matching as an error was emitted already");
 258             return DummyResult::any(sp);
 259         }
 260         Err(CanRetry::Yes) => {
 261             // Retry and emit a better error below.
 262         }
 263     }
 264
 265     diagnostics::failed_to_match_macro(cx, sp, def_span, name, arg, lhses)
 266 }
 267
 268 pub(super) enum CanRetry {
 269     Yes,
 270     /// We are not allowed to retry macro expansion as a fatal error has been emitted already.
 271     No(ErrorGuaranteed),
 272 }
 273
 274 /// Try expanding the macro. Returns the index of the successful arm and its named_matches if it was successful,
 275 /// and nothing if it failed. On failure, it's the callers job to use `track` accordingly to record all errors
 276 /// correctly.
 277 #[instrument(level = "debug", skip(sess, arg, lhses, track), fields(tracking = %T::description()))]
 278 pub(super) fn try_match_macro<'matcher, T: Tracker<'matcher>>(
 279     sess: &ParseSess,
 280     name: Ident,
 281     arg: &TokenStream,
 282     lhses: &'matcher [Vec<MatcherLoc>],
 283     track: &mut T,
 284 ) -> Result<(usize, NamedMatches), CanRetry> {
 285     // We create a base parser that can be used for the "black box" parts.
 286     // Every iteration needs a fresh copy of that parser. However, the parser
 287     // is not mutated on many of the iterations, particularly when dealing with
 288     // macros like this:
 289     //
 290     // macro_rules! foo {
 291     //     ("a") => (A);
 292     //     ("b") => (B);
 293     //     ("c") => (C);
 294     //     // ... etc. (maybe hundreds more)
 295     // }
 296     //
 297     // as seen in the `html5ever` benchmark. We use a `Cow` so that the base
 298     // parser is only cloned when necessary (upon mutation). Furthermore, we
 299     // reinitialize the `Cow` with the base parser at the start of every
 300     // iteration, so that any mutated parsers are not reused. This is all quite
 301     // hacky, but speeds up the `html5ever` benchmark significantly. (Issue
 302     // 68836 suggests a more comprehensive but more complex change to deal with
 303     // this situation.)
 304     let parser = parser_from_cx(sess, arg.clone(), T::recovery());
 305     // Try each arm's matchers.
 306     let mut tt_parser = TtParser::new(name);
 307     for (i, lhs) in lhses.iter().enumerate() {
 308         let _tracing_span = trace_span!("Matching arm", %i);
 309
 310         // Take a snapshot of the state of pre-expansion gating at this point.
 311         // This is used so that if a matcher is not `Success(..)`ful,
 312         // then the spans which became gated when parsing the unsuccessful matcher
 313         // are not recorded. On the first `Success(..)`ful matcher, the spans are merged.
 314         let mut gated_spans_snapshot = mem::take(&mut *sess.gated_spans.spans.borrow_mut());
 315
 316         let result = tt_parser.parse_tt(&mut Cow::Borrowed(&parser), lhs, track);
 317
 318         track.after_arm(&result);
 319
 320         match result {
 321             Success(named_matches) => {
 322                 debug!("Parsed arm successfully");
 323                 // The matcher was `Success(..)`ful.
 324                 // Merge the gated spans from parsing the matcher with the pre-existing ones.
 325                 sess.gated_spans.merge(gated_spans_snapshot);
 326
 327                 return Ok((i, named_matches));
 328             }
 329             Failure(_, reached_position, _) => {
 330                 trace!(%reached_position, "Failed to match arm, trying the next one");
 331                 // Try the next arm.
 332             }
 333             Error(_, _) => {
 334                 debug!("Fatal error occurred during matching");
 335                 // We haven't emitted an error yet, so we can retry.
 336                 return Err(CanRetry::Yes);
 337             }
 338             ErrorReported(guarantee) => {
 339                 debug!("Fatal error occurred and was reported during matching");
 340                 // An error has been reported already, we cannot retry as that would cause duplicate errors.
 341                 return Err(CanRetry::No(guarantee));
 342             }
 343         }
 344
 345         // The matcher was not `Success(..)`ful.
 346         // Restore to the state before snapshotting and maybe try again.
 347         mem::swap(&mut gated_spans_snapshot, &mut sess.gated_spans.spans.borrow_mut());
 348     }
 349
 350     Err(CanRetry::Yes)
 351 }
 352
 353 // Note that macro-by-example's input is also matched against a token tree:
 354 //                   $( $lhs:tt => $rhs:tt );+
 355 //
 356 // Holy self-referential!
 357
 358 /// Converts a macro item into a syntax extension.
 359 pub fn compile_declarative_macro(
 360     sess: &Session,
 361     features: &Features,
 362     def: &ast::Item,
 363     edition: Edition,
 364 ) -> (SyntaxExtension, Vec<(usize, Span)>) {
 365     debug!("compile_declarative_macro: {:?}", def);
 366     let mk_syn_ext = |expander| {
 367         SyntaxExtension::new(
 368             sess,
 369             SyntaxExtensionKind::LegacyBang(expander),
 370             def.span,
 371             Vec::new(),
 372             edition,
 373             def.ident.name,
 374             &def.attrs,
 375         )
 376     };
 377     let dummy_syn_ext = || (mk_syn_ext(Box::new(macro_rules_dummy_expander)), Vec::new());
 378
 379     let diag = &sess.parse_sess.span_diagnostic;
 380     let lhs_nm = Ident::new(sym::lhs, def.span);
 381     let rhs_nm = Ident::new(sym::rhs, def.span);
 382     let tt_spec = Some(NonterminalKind::TT);
 383
 384     // Parse the macro_rules! invocation
 385     let (macro_rules, body) = match &def.kind {
 386         ast::ItemKind::MacroDef(def) => (def.macro_rules, def.body.tokens.clone()),
 387         _ => unreachable!(),
 388     };
 389
 390     // The pattern that macro_rules matches.
 391     // The grammar for macro_rules! is:
 392     // $( $lhs:tt => $rhs:tt );+
 393     // ...quasiquoting this would be nice.
 394     // These spans won't matter, anyways
 395     let argument_gram = vec![
 396         mbe::TokenTree::Sequence(
 397             DelimSpan::dummy(),
 398             mbe::SequenceRepetition {
 399                 tts: vec![
 400                     mbe::TokenTree::MetaVarDecl(def.span, lhs_nm, tt_spec),
 401                     mbe::TokenTree::token(token::FatArrow, def.span),
 402                     mbe::TokenTree::MetaVarDecl(def.span, rhs_nm, tt_spec),
 403                 ],
 404                 separator: Some(Token::new(
 405                     if macro_rules { token::Semi } else { token::Comma },
 406                     def.span,
 407                 )),
 408                 kleene: mbe::KleeneToken::new(mbe::KleeneOp::OneOrMore, def.span),
 409                 num_captures: 2,
 410             },
 411         ),
 412         // to phase into semicolon-termination instead of semicolon-separation
 413         mbe::TokenTree::Sequence(
 414             DelimSpan::dummy(),
 415             mbe::SequenceRepetition {
 416                 tts: vec![mbe::TokenTree::token(
 417                     if macro_rules { token::Semi } else { token::Comma },
 418                     def.span,
 419                 )],
 420                 separator: None,
 421                 kleene: mbe::KleeneToken::new(mbe::KleeneOp::ZeroOrMore, def.span),
 422                 num_captures: 0,
 423             },
 424         ),
 425     ];
 426     // Convert it into `MatcherLoc` form.
 427     let argument_gram = mbe::macro_parser::compute_locs(&argument_gram);
 428
 429     let parser = Parser::new(&sess.parse_sess, body, true, rustc_parse::MACRO_ARGUMENTS);
 430     let mut tt_parser =
 431         TtParser::new(Ident::with_dummy_span(if macro_rules { kw::MacroRules } else { kw::Macro }));
 432     let argument_map =
 433         match tt_parser.parse_tt(&mut Cow::Owned(parser), &argument_gram, &mut NoopTracker) {
 434             Success(m) => m,
 435             Failure(token, _, msg) => {
 436                 let s = parse_failure_msg(&token);
 437                 let sp = token.span.substitute_dummy(def.span);
 438                 let mut err = sess.parse_sess.span_diagnostic.struct_span_err(sp, &s);
 439                 err.span_label(sp, msg);
 440                 annotate_doc_comment(&mut err, sess.source_map(), sp);
 441                 err.emit();
 442                 return dummy_syn_ext();
 443             }
 444             Error(sp, msg) => {
 445                 sess.parse_sess
 446                     .span_diagnostic
 447                     .struct_span_err(sp.substitute_dummy(def.span), &msg)
 448                     .emit();
 449                 return dummy_syn_ext();
 450             }
 451             ErrorReported(_) => {
 452                 return dummy_syn_ext();
 453             }
 454         };
 455
 456     let mut valid = true;
 457
 458     // Extract the arguments:
 459     let lhses = match argument_map[&MacroRulesNormalizedIdent::new(lhs_nm)] {
 460         MatchedSeq(ref s) => s
 461             .iter()
 462             .map(|m| {
 463                 if let MatchedTokenTree(ref tt) = *m {
 464                     let tt = mbe::quoted::parse(
 465                         TokenStream::new(vec![tt.clone()]),
 466                         true,
 467                         &sess.parse_sess,
 468                         def.id,
 469                         features,
 470                         edition,
 471                     )
 472                     .pop()
 473                     .unwrap();
 474                     valid &= check_lhs_nt_follows(&sess.parse_sess, &def, &tt);
 475                     return tt;
 476                 }
 477                 sess.parse_sess.span_diagnostic.span_bug(def.span, "wrong-structured lhs")
 478             })
 479             .collect::<Vec<mbe::TokenTree>>(),
 480         _ => sess.parse_sess.span_diagnostic.span_bug(def.span, "wrong-structured lhs"),
 481     };
 482
 483     let rhses = match argument_map[&MacroRulesNormalizedIdent::new(rhs_nm)] {
 484         MatchedSeq(ref s) => s
 485             .iter()
 486             .map(|m| {
 487                 if let MatchedTokenTree(ref tt) = *m {
 488                     return mbe::quoted::parse(
 489                         TokenStream::new(vec![tt.clone()]),
 490                         false,
 491                         &sess.parse_sess,
 492                         def.id,
 493                         features,
 494                         edition,
 495                     )
 496                     .pop()
 497                     .unwrap();
 498                 }
 499                 sess.parse_sess.span_diagnostic.span_bug(def.span, "wrong-structured lhs")
 500             })
 501             .collect::<Vec<mbe::TokenTree>>(),
 502         _ => sess.parse_sess.span_diagnostic.span_bug(def.span, "wrong-structured rhs"),
 503     };
 504
 505     for rhs in &rhses {
 506         valid &= check_rhs(&sess.parse_sess, rhs);
 507     }
 508
 509     // don't abort iteration early, so that errors for multiple lhses can be reported
 510     for lhs in &lhses {
 511         valid &= check_lhs_no_empty_seq(&sess.parse_sess, slice::from_ref(lhs));
 512     }
 513
 514     valid &= macro_check::check_meta_variables(&sess.parse_sess, def.id, def.span, &lhses, &rhses);
 515
 516     let (transparency, transparency_error) = attr::find_transparency(&def.attrs, macro_rules);
 517     match transparency_error {
 518         Some(TransparencyError::UnknownTransparency(value, span)) => {
 519             diag.span_err(span, &format!("unknown macro transparency: `{}`", value));
 520         }
 521         Some(TransparencyError::MultipleTransparencyAttrs(old_span, new_span)) => {
 522             diag.span_err(vec![old_span, new_span], "multiple macro transparency attributes");
 523         }
 524         None => {}
 525     }
 526
 527     // Compute the spans of the macro rules for unused rule linting.
 528     // To avoid warning noise, only consider the rules of this
 529     // macro for the lint, if all rules are valid.
 530     // Also, we are only interested in non-foreign macros.
 531     let rule_spans = if valid && def.id != DUMMY_NODE_ID {
 532         lhses
 533             .iter()
 534             .zip(rhses.iter())
 535             .enumerate()
 536             // If the rhs contains an invocation like compile_error!,
 537             // don't consider the rule for the unused rule lint.
 538             .filter(|(_idx, (_lhs, rhs))| !has_compile_error_macro(rhs))
 539             // We only take the span of the lhs here,
 540             // so that the spans of created warnings are smaller.
 541             .map(|(idx, (lhs, _rhs))| (idx, lhs.span()))
 542             .collect::<Vec<_>>()
 543     } else {
 544         Vec::new()
 545     };
 546
 547     // Convert the lhses into `MatcherLoc` form, which is better for doing the
 548     // actual matching. Unless the matcher is invalid.
 549     let lhses = if valid {
 550         lhses
 551             .iter()
 552             .map(|lhs| {
 553                 // Ignore the delimiters around the matcher.
 554                 match lhs {
 555                     mbe::TokenTree::Delimited(_, delimited) => {
 556                         mbe::macro_parser::compute_locs(&delimited.tts)
 557                     }
 558                     _ => sess.parse_sess.span_diagnostic.span_bug(def.span, "malformed macro lhs"),
 559                 }
 560             })
 561             .collect()
 562     } else {
 563         vec![]
 564     };
 565
 566     let expander = Box::new(MacroRulesMacroExpander {
 567         name: def.ident,
 568         span: def.span,
 569         node_id: def.id,
 570         transparency,
 571         lhses,
 572         rhses,
 573         valid,
 574     });
 575     (mk_syn_ext(expander), rule_spans)
 576 }
 577
 578 fn check_lhs_nt_follows(sess: &ParseSess, def: &ast::Item, lhs: &mbe::TokenTree) -> bool {
 579     // lhs is going to be like TokenTree::Delimited(...), where the
 580     // entire lhs is those tts. Or, it can be a "bare sequence", not wrapped in parens.
 581     if let mbe::TokenTree::Delimited(_, delimited) = lhs {
 582         check_matcher(sess, def, &delimited.tts)
 583     } else {
 584         let msg = "invalid macro matcher; matchers must be contained in balanced delimiters";
 585         sess.span_diagnostic.span_err(lhs.span(), msg);
 586         false
 587     }
 588     // we don't abort on errors on rejection, the driver will do that for us
 589     // after parsing/expansion. we can report every error in every macro this way.
 590 }
 591
 592 /// Checks that the lhs contains no repetition which could match an empty token
 593 /// tree, because then the matcher would hang indefinitely.
 594 fn check_lhs_no_empty_seq(sess: &ParseSess, tts: &[mbe::TokenTree]) -> bool {
 595     use mbe::TokenTree;
 596     for tt in tts {
 597         match *tt {
 598             TokenTree::Token(..)
 599             | TokenTree::MetaVar(..)
 600             | TokenTree::MetaVarDecl(..)
 601             | TokenTree::MetaVarExpr(..) => (),
 602             TokenTree::Delimited(_, ref del) => {
 603                 if !check_lhs_no_empty_seq(sess, &del.tts) {
 604                     return false;
 605                 }
 606             }
 607             TokenTree::Sequence(span, ref seq) => {
 608                 if seq.separator.is_none()
 609                     && seq.tts.iter().all(|seq_tt| match *seq_tt {
 610                         TokenTree::MetaVarDecl(_, _, Some(NonterminalKind::Vis)) => true,
 611                         TokenTree::Sequence(_, ref sub_seq) => {
 612                             sub_seq.kleene.op == mbe::KleeneOp::ZeroOrMore
 613                                 || sub_seq.kleene.op == mbe::KleeneOp::ZeroOrOne
 614                         }
 615                         _ => false,
 616                     })
 617                 {
 618                     let sp = span.entire();
 619                     sess.span_diagnostic.span_err(sp, "repetition matches empty token tree");
 620                     return false;
 621                 }
 622                 if !check_lhs_no_empty_seq(sess, &seq.tts) {
 623                     return false;
 624                 }
 625             }
 626         }
 627     }
 628
 629     true
 630 }
 631
 632 fn check_rhs(sess: &ParseSess, rhs: &mbe::TokenTree) -> bool {
 633     match *rhs {
 634         mbe::TokenTree::Delimited(..) => return true,
 635         _ => {
 636             sess.span_diagnostic.span_err(rhs.span(), "macro rhs must be delimited");
 637         }
 638     }
 639     false
 640 }
 641
 642 fn check_matcher(sess: &ParseSess, def: &ast::Item, matcher: &[mbe::TokenTree]) -> bool {
 643     let first_sets = FirstSets::new(matcher);
 644     let empty_suffix = TokenSet::empty();
 645     let err = sess.span_diagnostic.err_count();
 646     check_matcher_core(sess, def, &first_sets, matcher, &empty_suffix);
 647     err == sess.span_diagnostic.err_count()
 648 }
 649
 650 fn has_compile_error_macro(rhs: &mbe::TokenTree) -> bool {
 651     match rhs {
 652         mbe::TokenTree::Delimited(_sp, d) => {
 653             let has_compile_error = d.tts.array_windows::<3>().any(|[ident, bang, args]| {
 654                 if let mbe::TokenTree::Token(ident) = ident &&
 655                         let TokenKind::Ident(ident, _) = ident.kind &&
 656                         ident == sym::compile_error &&
 657                         let mbe::TokenTree::Token(bang) = bang &&
 658                         let TokenKind::Not = bang.kind &&
 659                         let mbe::TokenTree::Delimited(_, del) = args &&
 660                         del.delim != Delimiter::Invisible
 661                     {
 662                         true
 663                     } else {
 664                         false
 665                     }
 666             });
 667             if has_compile_error { true } else { d.tts.iter().any(has_compile_error_macro) }
 668         }
 669         _ => false,
 670     }
 671 }
 672
 673 // `The FirstSets` for a matcher is a mapping from subsequences in the
 674 // matcher to the FIRST set for that subsequence.
 675 //
 676 // This mapping is partially precomputed via a backwards scan over the
 677 // token trees of the matcher, which provides a mapping from each
 678 // repetition sequence to its *first* set.
 679 //
 680 // (Hypothetically, sequences should be uniquely identifiable via their
 681 // spans, though perhaps that is false, e.g., for macro-generated macros
 682 // that do not try to inject artificial span information. My plan is
 683 // to try to catch such cases ahead of time and not include them in
 684 // the precomputed mapping.)
 685 struct FirstSets<'tt> {
 686     // this maps each TokenTree::Sequence `$(tt ...) SEP OP` that is uniquely identified by its
 687     // span in the original matcher to the First set for the inner sequence `tt ...`.
 688     //
 689     // If two sequences have the same span in a matcher, then map that
 690     // span to None (invalidating the mapping here and forcing the code to
 691     // use a slow path).
 692     first: FxHashMap<Span, Option<TokenSet<'tt>>>,
 693 }
 694
 695 impl<'tt> FirstSets<'tt> {
 696     fn new(tts: &'tt [mbe::TokenTree]) -> FirstSets<'tt> {
 697         use mbe::TokenTree;
 698
 699         let mut sets = FirstSets { first: FxHashMap::default() };
 700         build_recur(&mut sets, tts);
 701         return sets;
 702
 703         // walks backward over `tts`, returning the FIRST for `tts`
 704         // and updating `sets` at the same time for all sequence
 705         // substructure we find within `tts`.
 706         fn build_recur<'tt>(sets: &mut FirstSets<'tt>, tts: &'tt [TokenTree]) -> TokenSet<'tt> {
 707             let mut first = TokenSet::empty();
 708             for tt in tts.iter().rev() {
 709                 match *tt {
 710                     TokenTree::Token(..)
 711                     | TokenTree::MetaVar(..)
 712                     | TokenTree::MetaVarDecl(..)
 713                     | TokenTree::MetaVarExpr(..) => {
 714                         first.replace_with(TtHandle::TtRef(tt));
 715                     }
 716                     TokenTree::Delimited(span, ref delimited) => {
 717                         build_recur(sets, &delimited.tts);
 718                         first.replace_with(TtHandle::from_token_kind(
 719                             token::OpenDelim(delimited.delim),
 720                             span.open,
 721                         ));
 722                     }
 723                     TokenTree::Sequence(sp, ref seq_rep) => {
 724                         let subfirst = build_recur(sets, &seq_rep.tts);
 725
 726                         match sets.first.entry(sp.entire()) {
 727                             Entry::Vacant(vac) => {
 728                                 vac.insert(Some(subfirst.clone()));
 729                             }
 730                             Entry::Occupied(mut occ) => {
 731                                 // if there is already an entry, then a span must have collided.
 732                                 // This should not happen with typical macro_rules macros,
 733                                 // but syntax extensions need not maintain distinct spans,
 734                                 // so distinct syntax trees can be assigned the same span.
 735                                 // In such a case, the map cannot be trusted; so mark this
 736                                 // entry as unusable.
 737                                 occ.insert(None);
 738                             }
 739                         }
 740
 741                         // If the sequence contents can be empty, then the first
 742                         // token could be the separator token itself.
 743
 744                         if let (Some(sep), true) = (&seq_rep.separator, subfirst.maybe_empty) {
 745                             first.add_one_maybe(TtHandle::from_token(sep.clone()));
 746                         }
 747
 748                         // Reverse scan: Sequence comes before `first`.
 749                         if subfirst.maybe_empty
 750                             || seq_rep.kleene.op == mbe::KleeneOp::ZeroOrMore
 751                             || seq_rep.kleene.op == mbe::KleeneOp::ZeroOrOne
 752                         {
 753                             // If sequence is potentially empty, then
 754                             // union them (preserving first emptiness).
 755                             first.add_all(&TokenSet { maybe_empty: true, ..subfirst });
 756                         } else {
 757                             // Otherwise, sequence guaranteed
 758                             // non-empty; replace first.
 759                             first = subfirst;
 760                         }
 761                     }
 762                 }
 763             }
 764
 765             first
 766         }
 767     }
 768
 769     // walks forward over `tts` until all potential FIRST tokens are
 770     // identified.
 771     fn first(&self, tts: &'tt [mbe::TokenTree]) -> TokenSet<'tt> {
 772         use mbe::TokenTree;
 773
 774         let mut first = TokenSet::empty();
 775         for tt in tts.iter() {
 776             assert!(first.maybe_empty);
 777             match *tt {
 778                 TokenTree::Token(..)
 779                 | TokenTree::MetaVar(..)
 780                 | TokenTree::MetaVarDecl(..)
 781                 | TokenTree::MetaVarExpr(..) => {
 782                     first.add_one(TtHandle::TtRef(tt));
 783                     return first;
 784                 }
 785                 TokenTree::Delimited(span, ref delimited) => {
 786                     first.add_one(TtHandle::from_token_kind(
 787                         token::OpenDelim(delimited.delim),
 788                         span.open,
 789                     ));
 790                     return first;
 791                 }
 792                 TokenTree::Sequence(sp, ref seq_rep) => {
 793                     let subfirst_owned;
 794                     let subfirst = match self.first.get(&sp.entire()) {
 795                         Some(Some(subfirst)) => subfirst,
 796                         Some(&None) => {
 797                             subfirst_owned = self.first(&seq_rep.tts);
 798                             &subfirst_owned
 799                         }
 800                         None => {
 801                             panic!("We missed a sequence during FirstSets construction");
 802                         }
 803                     };
 804
 805                     // If the sequence contents can be empty, then the first
 806                     // token could be the separator token itself.
 807                     if let (Some(sep), true) = (&seq_rep.separator, subfirst.maybe_empty) {
 808                         first.add_one_maybe(TtHandle::from_token(sep.clone()));
 809                     }
 810
 811                     assert!(first.maybe_empty);
 812                     first.add_all(subfirst);
 813                     if subfirst.maybe_empty
 814                         || seq_rep.kleene.op == mbe::KleeneOp::ZeroOrMore
 815                         || seq_rep.kleene.op == mbe::KleeneOp::ZeroOrOne
 816                     {
 817                         // Continue scanning for more first
 818                         // tokens, but also make sure we
 819                         // restore empty-tracking state.
 820                         first.maybe_empty = true;
 821                         continue;
 822                     } else {
 823                         return first;
 824                     }
 825                 }
 826             }
 827         }
 828
 829         // we only exit the loop if `tts` was empty or if every
 830         // element of `tts` matches the empty sequence.
 831         assert!(first.maybe_empty);
 832         first
 833     }
 834 }
 835
 836 // Most `mbe::TokenTree`s are pre-existing in the matcher, but some are defined
 837 // implicitly, such as opening/closing delimiters and sequence repetition ops.
 838 // This type encapsulates both kinds. It implements `Clone` while avoiding the
 839 // need for `mbe::TokenTree` to implement `Clone`.
 840 #[derive(Debug)]
 841 enum TtHandle<'tt> {
 842     /// This is used in most cases.
 843     TtRef(&'tt mbe::TokenTree),
 844
 845     /// This is only used for implicit token trees. The `mbe::TokenTree` *must*
 846     /// be `mbe::TokenTree::Token`. No other variants are allowed. We store an
 847     /// `mbe::TokenTree` rather than a `Token` so that `get()` can return a
 848     /// `&mbe::TokenTree`.
 849     Token(mbe::TokenTree),
 850 }
 851
 852 impl<'tt> TtHandle<'tt> {
 853     fn from_token(tok: Token) -> Self {
 854         TtHandle::Token(mbe::TokenTree::Token(tok))
 855     }
 856
 857     fn from_token_kind(kind: TokenKind, span: Span) -> Self {
 858         TtHandle::from_token(Token::new(kind, span))
 859     }
 860
 861     // Get a reference to a token tree.
 862     fn get(&'tt self) -> &'tt mbe::TokenTree {
 863         match self {
 864             TtHandle::TtRef(tt) => tt,
 865             TtHandle::Token(token_tt) => &token_tt,
 866         }
 867     }
 868 }
 869
 870 impl<'tt> PartialEq for TtHandle<'tt> {
 871     fn eq(&self, other: &TtHandle<'tt>) -> bool {
 872         self.get() == other.get()
 873     }
 874 }
 875
 876 impl<'tt> Clone for TtHandle<'tt> {
 877     fn clone(&self) -> Self {
 878         match self {
 879             TtHandle::TtRef(tt) => TtHandle::TtRef(tt),
 880
 881             // This variant *must* contain a `mbe::TokenTree::Token`, and not
 882             // any other variant of `mbe::TokenTree`.
 883             TtHandle::Token(mbe::TokenTree::Token(tok)) => {
 884                 TtHandle::Token(mbe::TokenTree::Token(tok.clone()))
 885             }
 886
 887             _ => unreachable!(),
 888         }
 889     }
 890 }
 891
 892 // A set of `mbe::TokenTree`s, which may include `TokenTree::Match`s
 893 // (for macro-by-example syntactic variables). It also carries the
 894 // `maybe_empty` flag; that is true if and only if the matcher can
 895 // match an empty token sequence.
 896 //
 897 // The First set is computed on submatchers like `$($a:expr b),* $(c)* d`,
 898 // which has corresponding FIRST = {$a:expr, c, d}.
 899 // Likewise, `$($a:expr b),* $(c)+ d` has FIRST = {$a:expr, c}.
 900 //
 901 // (Notably, we must allow for *-op to occur zero times.)
 902 #[derive(Clone, Debug)]
 903 struct TokenSet<'tt> {
 904     tokens: Vec<TtHandle<'tt>>,
 905     maybe_empty: bool,
 906 }
 907
 908 impl<'tt> TokenSet<'tt> {
 909     // Returns a set for the empty sequence.
 910     fn empty() -> Self {
 911         TokenSet { tokens: Vec::new(), maybe_empty: true }
 912     }
 913
 914     // Returns the set `{ tok }` for the single-token (and thus
 915     // non-empty) sequence [tok].
 916     fn singleton(tt: TtHandle<'tt>) -> Self {
 917         TokenSet { tokens: vec![tt], maybe_empty: false }
 918     }
 919
 920     // Changes self to be the set `{ tok }`.
 921     // Since `tok` is always present, marks self as non-empty.
 922     fn replace_with(&mut self, tt: TtHandle<'tt>) {
 923         self.tokens.clear();
 924         self.tokens.push(tt);
 925         self.maybe_empty = false;
 926     }
 927
 928     // Changes self to be the empty set `{}`; meant for use when
 929     // the particular token does not matter, but we want to
 930     // record that it occurs.
 931     fn replace_with_irrelevant(&mut self) {
 932         self.tokens.clear();
 933         self.maybe_empty = false;
 934     }
 935
 936     // Adds `tok` to the set for `self`, marking sequence as non-empty.
 937     fn add_one(&mut self, tt: TtHandle<'tt>) {
 938         if !self.tokens.contains(&tt) {
 939             self.tokens.push(tt);
 940         }
 941         self.maybe_empty = false;
 942     }
 943
 944     // Adds `tok` to the set for `self`. (Leaves `maybe_empty` flag alone.)
 945     fn add_one_maybe(&mut self, tt: TtHandle<'tt>) {
 946         if !self.tokens.contains(&tt) {
 947             self.tokens.push(tt);
 948         }
 949     }
 950
 951     // Adds all elements of `other` to this.
 952     //
 953     // (Since this is a set, we filter out duplicates.)
 954     //
 955     // If `other` is potentially empty, then preserves the previous
 956     // setting of the empty flag of `self`. If `other` is guaranteed
 957     // non-empty, then `self` is marked non-empty.
 958     fn add_all(&mut self, other: &Self) {
 959         for tt in &other.tokens {
 960             if !self.tokens.contains(tt) {
 961                 self.tokens.push(tt.clone());
 962             }
 963         }
 964         if !other.maybe_empty {
 965             self.maybe_empty = false;
 966         }
 967     }
 968 }
 969
 970 // Checks that `matcher` is internally consistent and that it
 971 // can legally be followed by a token `N`, for all `N` in `follow`.
 972 // (If `follow` is empty, then it imposes no constraint on
 973 // the `matcher`.)
 974 //
 975 // Returns the set of NT tokens that could possibly come last in
 976 // `matcher`. (If `matcher` matches the empty sequence, then
 977 // `maybe_empty` will be set to true.)
 978 //
 979 // Requires that `first_sets` is pre-computed for `matcher`;
 980 // see `FirstSets::new`.
 981 fn check_matcher_core<'tt>(
 982     sess: &ParseSess,
 983     def: &ast::Item,
 984     first_sets: &FirstSets<'tt>,
 985     matcher: &'tt [mbe::TokenTree],
 986     follow: &TokenSet<'tt>,
 987 ) -> TokenSet<'tt> {
 988     use mbe::TokenTree;
 989
 990     let mut last = TokenSet::empty();
 991
 992     // 2. For each token and suffix  [T, SUFFIX] in M:
 993     // ensure that T can be followed by SUFFIX, and if SUFFIX may be empty,
 994     // then ensure T can also be followed by any element of FOLLOW.
 995     'each_token: for i in 0..matcher.len() {
 996         let token = &matcher[i];
 997         let suffix = &matcher[i + 1..];
 998
 999         let build_suffix_first = || {
1000             let mut s = first_sets.first(suffix);
1001             if s.maybe_empty {
1002                 s.add_all(follow);
1003             }
1004             s
1005         };
1006
1007         // (we build `suffix_first` on demand below; you can tell
1008         // which cases are supposed to fall through by looking for the
1009         // initialization of this variable.)
1010         let suffix_first;
1011
1012         // First, update `last` so that it corresponds to the set
1013         // of NT tokens that might end the sequence `... token`.
1014         match *token {
1015             TokenTree::Token(..)
1016             | TokenTree::MetaVar(..)
1017             | TokenTree::MetaVarDecl(..)
1018             | TokenTree::MetaVarExpr(..) => {
1019                 if token_can_be_followed_by_any(token) {
1020                     // don't need to track tokens that work with any,
1021                     last.replace_with_irrelevant();
1022                     // ... and don't need to check tokens that can be
1023                     // followed by anything against SUFFIX.
1024                     continue 'each_token;
1025                 } else {
1026                     last.replace_with(TtHandle::TtRef(token));
1027                     suffix_first = build_suffix_first();
1028                 }
1029             }
1030             TokenTree::Delimited(span, ref d) => {
1031                 let my_suffix = TokenSet::singleton(TtHandle::from_token_kind(
1032                     token::CloseDelim(d.delim),
1033                     span.close,
1034                 ));
1035                 check_matcher_core(sess, def, first_sets, &d.tts, &my_suffix);
1036                 // don't track non NT tokens
1037                 last.replace_with_irrelevant();
1038
1039                 // also, we don't need to check delimited sequences
1040                 // against SUFFIX
1041                 continue 'each_token;
1042             }
1043             TokenTree::Sequence(_, ref seq_rep) => {
1044                 suffix_first = build_suffix_first();
1045                 // The trick here: when we check the interior, we want
1046                 // to include the separator (if any) as a potential
1047                 // (but not guaranteed) element of FOLLOW. So in that
1048                 // case, we make a temp copy of suffix and stuff
1049                 // delimiter in there.
1050                 //
1051                 // FIXME: Should I first scan suffix_first to see if
1052                 // delimiter is already in it before I go through the
1053                 // work of cloning it? But then again, this way I may
1054                 // get a "tighter" span?
1055                 let mut new;
1056                 let my_suffix = if let Some(sep) = &seq_rep.separator {
1057                     new = suffix_first.clone();
1058                     new.add_one_maybe(TtHandle::from_token(sep.clone()));
1059                     &new
1060                 } else {
1061                     &suffix_first
1062                 };
1063
1064                 // At this point, `suffix_first` is built, and
1065                 // `my_suffix` is some TokenSet that we can use
1066                 // for checking the interior of `seq_rep`.
1067                 let next = check_matcher_core(sess, def, first_sets, &seq_rep.tts, my_suffix);
1068                 if next.maybe_empty {
1069                     last.add_all(&next);
1070                 } else {
1071                     last = next;
1072                 }
1073
1074                 // the recursive call to check_matcher_core already ran the 'each_last
1075                 // check below, so we can just keep going forward here.
1076                 continue 'each_token;
1077             }
1078         }
1079
1080         // (`suffix_first` guaranteed initialized once reaching here.)
1081
1082         // Now `last` holds the complete set of NT tokens that could
1083         // end the sequence before SUFFIX. Check that every one works with `suffix`.
1084         for tt in &last.tokens {
1085             if let &TokenTree::MetaVarDecl(span, name, Some(kind)) = tt.get() {
1086                 for next_token in &suffix_first.tokens {
1087                     let next_token = next_token.get();
1088
1089                     // Check if the old pat is used and the next token is `|`
1090                     // to warn about incompatibility with Rust 2021.
1091                     // We only emit this lint if we're parsing the original
1092                     // definition of this macro_rules, not while (re)parsing
1093                     // the macro when compiling another crate that is using the
1094                     // macro. (See #86567.)
1095                     // Macros defined in the current crate have a real node id,
1096                     // whereas macros from an external crate have a dummy id.
1097                     if def.id != DUMMY_NODE_ID
1098                         && matches!(kind, NonterminalKind::PatParam { inferred: true })
1099                         && matches!(next_token, TokenTree::Token(token) if token.kind == BinOp(token::BinOpToken::Or))
1100                     {
1101                         // It is suggestion to use pat_param, for example: $x:pat -> $x:pat_param.
1102                         let suggestion = quoted_tt_to_string(&TokenTree::MetaVarDecl(
1103                             span,
1104                             name,
1105                             Some(NonterminalKind::PatParam { inferred: false }),
1106                         ));
1107                         sess.buffer_lint_with_diagnostic(
1108                             &RUST_2021_INCOMPATIBLE_OR_PATTERNS,
1109                             span,
1110                             ast::CRATE_NODE_ID,
1111                             "the meaning of the `pat` fragment specifier is changing in Rust 2021, which may affect this macro",
1112                             BuiltinLintDiagnostics::OrPatternsBackCompat(span, suggestion),
1113                         );
1114                     }
1115                     match is_in_follow(next_token, kind) {
1116                         IsInFollow::Yes => {}
1117                         IsInFollow::No(possible) => {
1118                             let may_be = if last.tokens.len() == 1 && suffix_first.tokens.len() == 1
1119                             {
1120                                 "is"
1121                             } else {
1122                                 "may be"
1123                             };
1124
1125                             let sp = next_token.span();
1126                             let mut err = sess.span_diagnostic.struct_span_err(
1127                                 sp,
1128                                 &format!(
1129                                     "`${name}:{frag}` {may_be} followed by `{next}`, which \
1130                                      is not allowed for `{frag}` fragments",
1131                                     name = name,
1132                                     frag = kind,
1133                                     next = quoted_tt_to_string(next_token),
1134                                     may_be = may_be
1135                                 ),
1136                             );
1137                             err.span_label(sp, format!("not allowed after `{}` fragments", kind));
1138
1139                             if kind == NonterminalKind::PatWithOr
1140                                 && sess.edition.rust_2021()
1141                                 && next_token.is_token(&BinOp(token::BinOpToken::Or))
1142                             {
1143                                 let suggestion = quoted_tt_to_string(&TokenTree::MetaVarDecl(
1144                                     span,
1145                                     name,
1146                                     Some(NonterminalKind::PatParam { inferred: false }),
1147                                 ));
1148                                 err.span_suggestion(
1149                                     span,
1150                                     "try a `pat_param` fragment specifier instead",
1151                                     suggestion,
1152                                     Applicability::MaybeIncorrect,
1153                                 );
1154                             }
1155
1156                             let msg = "allowed there are: ";
1157                             match possible {
1158                                 &[] => {}
1159                                 &[t] => {
1160                                     err.note(&format!(
1161                                         "only {} is allowed after `{}` fragments",
1162                                         t, kind,
1163                                     ));
1164                                 }
1165                                 ts => {
1166                                     err.note(&format!(
1167                                         "{}{} or {}",
1168                                         msg,
1169                                         ts[..ts.len() - 1].to_vec().join(", "),
1170                                         ts[ts.len() - 1],
1171                                     ));
1172                                 }
1173                             }
1174                             err.emit();
1175                         }
1176                     }
1177                 }
1178             }
1179         }
1180     }
1181     last
1182 }
1183
1184 fn token_can_be_followed_by_any(tok: &mbe::TokenTree) -> bool {
1185     if let mbe::TokenTree::MetaVarDecl(_, _, Some(kind)) = *tok {
1186         frag_can_be_followed_by_any(kind)
1187     } else {
1188         // (Non NT's can always be followed by anything in matchers.)
1189         true
1190     }
1191 }
1192
1193 /// Returns `true` if a fragment of type `frag` can be followed by any sort of
1194 /// token. We use this (among other things) as a useful approximation
1195 /// for when `frag` can be followed by a repetition like `$(...)*` or
1196 /// `$(...)+`. In general, these can be a bit tricky to reason about,
1197 /// so we adopt a conservative position that says that any fragment
1198 /// specifier which consumes at most one token tree can be followed by
1199 /// a fragment specifier (indeed, these fragments can be followed by
1200 /// ANYTHING without fear of future compatibility hazards).
1201 fn frag_can_be_followed_by_any(kind: NonterminalKind) -> bool {
1202     matches!(
1203         kind,
1204         NonterminalKind::Item           // always terminated by `}` or `;`
1205         | NonterminalKind::Block        // exactly one token tree
1206         | NonterminalKind::Ident        // exactly one token tree
1207         | NonterminalKind::Literal      // exactly one token tree
1208         | NonterminalKind::Meta         // exactly one token tree
1209         | NonterminalKind::Lifetime     // exactly one token tree
1210         | NonterminalKind::TT // exactly one token tree
1211     )
1212 }
1213
1214 enum IsInFollow {
1215     Yes,
1216     No(&'static [&'static str]),
1217 }
1218
1219 /// Returns `true` if `frag` can legally be followed by the token `tok`. For
1220 /// fragments that can consume an unbounded number of tokens, `tok`
1221 /// must be within a well-defined follow set. This is intended to
1222 /// guarantee future compatibility: for example, without this rule, if
1223 /// we expanded `expr` to include a new binary operator, we might
1224 /// break macros that were relying on that binary operator as a
1225 /// separator.
1226 // when changing this do not forget to update doc/book/macros.md!
1227 fn is_in_follow(tok: &mbe::TokenTree, kind: NonterminalKind) -> IsInFollow {
1228     use mbe::TokenTree;
1229
1230     if let TokenTree::Token(Token { kind: token::CloseDelim(_), .. }) = *tok {
1231         // closing a token tree can never be matched by any fragment;
1232         // iow, we always require that `(` and `)` match, etc.
1233         IsInFollow::Yes
1234     } else {
1235         match kind {
1236             NonterminalKind::Item => {
1237                 // since items *must* be followed by either a `;` or a `}`, we can
1238                 // accept anything after them
1239                 IsInFollow::Yes
1240             }
1241             NonterminalKind::Block => {
1242                 // anything can follow block, the braces provide an easy boundary to
1243                 // maintain
1244                 IsInFollow::Yes
1245             }
1246             NonterminalKind::Stmt | NonterminalKind::Expr => {
1247                 const TOKENS: &[&str] = &["`=>`", "`,`", "`;`"];
1248                 match tok {
1249                     TokenTree::Token(token) => match token.kind {
1250                         FatArrow | Comma | Semi => IsInFollow::Yes,
1251                         _ => IsInFollow::No(TOKENS),
1252                     },
1253                     _ => IsInFollow::No(TOKENS),
1254                 }
1255             }
1256             NonterminalKind::PatParam { .. } => {
1257                 const TOKENS: &[&str] = &["`=>`", "`,`", "`=`", "`|`", "`if`", "`in`"];
1258                 match tok {
1259                     TokenTree::Token(token) => match token.kind {
1260                         FatArrow | Comma | Eq | BinOp(token::Or) => IsInFollow::Yes,
1261                         Ident(name, false) if name == kw::If || name == kw::In => IsInFollow::Yes,
1262                         _ => IsInFollow::No(TOKENS),
1263                     },
1264                     _ => IsInFollow::No(TOKENS),
1265                 }
1266             }
1267             NonterminalKind::PatWithOr { .. } => {
1268                 const TOKENS: &[&str] = &["`=>`", "`,`", "`=`", "`if`", "`in`"];
1269                 match tok {
1270                     TokenTree::Token(token) => match token.kind {
1271                         FatArrow | Comma | Eq => IsInFollow::Yes,
1272                         Ident(name, false) if name == kw::If || name == kw::In => IsInFollow::Yes,
1273                         _ => IsInFollow::No(TOKENS),
1274                     },
1275                     _ => IsInFollow::No(TOKENS),
1276                 }
1277             }
1278             NonterminalKind::Path | NonterminalKind::Ty => {
1279                 const TOKENS: &[&str] = &[
1280                     "`{`", "`[`", "`=>`", "`,`", "`>`", "`=`", "`:`", "`;`", "`|`", "`as`",
1281                     "`where`",
1282                 ];
1283                 match tok {
1284                     TokenTree::Token(token) => match token.kind {
1285                         OpenDelim(Delimiter::Brace)
1286                         | OpenDelim(Delimiter::Bracket)
1287                         | Comma
1288                         | FatArrow
1289                         | Colon
1290                         | Eq
1291                         | Gt
1292                         | BinOp(token::Shr)
1293                         | Semi
1294                         | BinOp(token::Or) => IsInFollow::Yes,
1295                         Ident(name, false) if name == kw::As || name == kw::Where => {
1296                             IsInFollow::Yes
1297                         }
1298                         _ => IsInFollow::No(TOKENS),
1299                     },
1300                     TokenTree::MetaVarDecl(_, _, Some(NonterminalKind::Block)) => IsInFollow::Yes,
1301                     _ => IsInFollow::No(TOKENS),
1302                 }
1303             }
1304             NonterminalKind::Ident | NonterminalKind::Lifetime => {
1305                 // being a single token, idents and lifetimes are harmless
1306                 IsInFollow::Yes
1307             }
1308             NonterminalKind::Literal => {
1309                 // literals may be of a single token, or two tokens (negative numbers)
1310                 IsInFollow::Yes
1311             }
1312             NonterminalKind::Meta | NonterminalKind::TT => {
1313                 // being either a single token or a delimited sequence, tt is
1314                 // harmless
1315                 IsInFollow::Yes
1316             }
1317             NonterminalKind::Vis => {
1318                 // Explicitly disallow `priv`, on the off chance it comes back.
1319                 const TOKENS: &[&str] = &["`,`", "an ident", "a type"];
1320                 match tok {
1321                     TokenTree::Token(token) => match token.kind {
1322                         Comma => IsInFollow::Yes,
1323                         Ident(name, is_raw) if is_raw || name != kw::Priv => IsInFollow::Yes,
1324                         _ => {
1325                             if token.can_begin_type() {
1326                                 IsInFollow::Yes
1327                             } else {
1328                                 IsInFollow::No(TOKENS)
1329                             }
1330                         }
1331                     },
1332                     TokenTree::MetaVarDecl(
1333                         _,
1334                         _,
1335                         Some(NonterminalKind::Ident | NonterminalKind::Ty | NonterminalKind::Path),
1336                     ) => IsInFollow::Yes,
1337                     _ => IsInFollow::No(TOKENS),
1338                 }
1339             }
1340         }
1341     }
1342 }
1343
1344 fn quoted_tt_to_string(tt: &mbe::TokenTree) -> String {
1345     match *tt {
1346         mbe::TokenTree::Token(ref token) => pprust::token_to_string(&token).into(),
1347         mbe::TokenTree::MetaVar(_, name) => format!("${}", name),
1348         mbe::TokenTree::MetaVarDecl(_, name, Some(kind)) => format!("${}:{}", name, kind),
1349         mbe::TokenTree::MetaVarDecl(_, name, None) => format!("${}:", name),
1350         _ => panic!(
1351             "{}",
1352             "unexpected mbe::TokenTree::{Sequence or Delimited} \
1353              in follow set checker"
1354         ),
1355     }
1356 }
1357
1358 pub(super) fn parser_from_cx(sess: &ParseSess, tts: TokenStream, recovery: Recovery) -> Parser<'_> {
1359     Parser::new(sess, tts, true, rustc_parse::MACRO_ARGUMENTS).recovery(recovery)
1360 }