rustc_expand/mbe/
macro_rules.rs

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