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