rustc_expand/mbe/
macro_parser.rs

1//! This is an NFA-based parser, which calls out to the main Rust parser for named non-terminals
2//! (which it commits to fully when it hits one in a grammar). There's a set of current NFA threads
3//! and a set of next ones. Instead of NTs, we have a special case for Kleene star. The big-O, in
4//! pathological cases, is worse than traditional use of NFA or Earley parsing, but it's an easier
5//! fit for Macro-by-Example-style rules.
6//!
7//! (In order to prevent the pathological case, we'd need to lazily construct the resulting
8//! `NamedMatch`es at the very end. It'd be a pain, and require more memory to keep around old
9//! matcher positions, but it would also save overhead)
10//!
11//! We don't say this parser uses the Earley algorithm, because it's unnecessarily inaccurate.
12//! The macro parser restricts itself to the features of finite state automata. Earley parsers
13//! can be described as an extension of NFAs with completion rules, prediction rules, and recursion.
14//!
15//! Quick intro to how the parser works:
16//!
17//! A "matcher position" (a.k.a. "position" or "mp") is a dot in the middle of a matcher, usually
18//! written as a `·`. For example `· a $( a )* a b` is one, as is `a $( · a )* a b`.
19//!
20//! The parser walks through the input a token at a time, maintaining a list
21//! of threads consistent with the current position in the input string: `cur_mps`.
22//!
23//! As it processes them, it fills up `eof_mps` with threads that would be valid if
24//! the macro invocation is now over, `bb_mps` with threads that are waiting on
25//! a Rust non-terminal like `$e:expr`, and `next_mps` with threads that are waiting
26//! on a particular token. Most of the logic concerns moving the · through the
27//! repetitions indicated by Kleene stars. The rules for moving the · without
28//! consuming any input are called epsilon transitions. It only advances or calls
29//! out to the real Rust parser when no `cur_mps` threads remain.
30//!
31//! Example:
32//!
33//! ```text, ignore
34//! Start parsing a a a a b against [· a $( a )* a b].
35//!
36//! Remaining input: a a a a b
37//! next: [· a $( a )* a b]
38//!
39//! - - - Advance over an a. - - -
40//!
41//! Remaining input: a a a b
42//! cur: [a · $( a )* a b]
43//! Descend/Skip (first position).
44//! next: [a $( · a )* a b]  [a $( a )* · a b].
45//!
46//! - - - Advance over an a. - - -
47//!
48//! Remaining input: a a b
49//! cur: [a $( a · )* a b]  [a $( a )* a · b]
50//! Follow epsilon transition: Finish/Repeat (first position)
51//! next: [a $( a )* · a b]  [a $( · a )* a b]  [a $( a )* a · b]
52//!
53//! - - - Advance over an a. - - - (this looks exactly like the last step)
54//!
55//! Remaining input: a b
56//! cur: [a $( a · )* a b]  [a $( a )* a · b]
57//! Follow epsilon transition: Finish/Repeat (first position)
58//! next: [a $( a )* · a b]  [a $( · a )* a b]  [a $( a )* a · b]
59//!
60//! - - - Advance over an a. - - - (this looks exactly like the last step)
61//!
62//! Remaining input: b
63//! cur: [a $( a · )* a b]  [a $( a )* a · b]
64//! Follow epsilon transition: Finish/Repeat (first position)
65//! next: [a $( a )* · a b]  [a $( · a )* a b]  [a $( a )* a · b]
66//!
67//! - - - Advance over a b. - - -
68//!
69//! Remaining input: ''
70//! eof: [a $( a )* a b ·]
71//! ```
72
73use std::borrow::Cow;
74use std::collections::hash_map::Entry::{Occupied, Vacant};
75use std::fmt::Display;
76use std::rc::Rc;
77
78pub(crate) use NamedMatch::*;
79pub(crate) use ParseResult::*;
80use rustc_ast::token::{self, DocComment, NonterminalKind, Token};
81use rustc_data_structures::fx::FxHashMap;
82use rustc_errors::ErrorGuaranteed;
83use rustc_lint_defs::pluralize;
84use rustc_parse::parser::{ParseNtResult, Parser, token_descr};
85use rustc_span::{Ident, MacroRulesNormalizedIdent, Span};
86
87use crate::mbe::macro_rules::Tracker;
88use crate::mbe::{KleeneOp, TokenTree};
89
90/// A unit within a matcher that a `MatcherPos` can refer to. Similar to (and derived from)
91/// `mbe::TokenTree`, but designed specifically for fast and easy traversal during matching.
92/// Notable differences to `mbe::TokenTree`:
93/// - It is non-recursive, i.e. there is no nesting.
94/// - The end pieces of each sequence (the separator, if present, and the Kleene op) are
95///   represented explicitly, as is the very end of the matcher.
96///
97/// This means a matcher can be represented by `&[MatcherLoc]`, and traversal mostly involves
98/// simply incrementing the current matcher position index by one.
99#[derive(Debug, PartialEq, Clone)]
100pub(crate) enum MatcherLoc {
101    Token {
102        token: Token,
103    },
104    Delimited,
105    Sequence {
106        op: KleeneOp,
107        num_metavar_decls: usize,
108        idx_first_after: usize,
109        next_metavar: usize,
110        seq_depth: usize,
111    },
112    SequenceKleeneOpNoSep {
113        op: KleeneOp,
114        idx_first: usize,
115    },
116    SequenceSep {
117        separator: Token,
118    },
119    SequenceKleeneOpAfterSep {
120        idx_first: usize,
121    },
122    MetaVarDecl {
123        span: Span,
124        bind: Ident,
125        kind: NonterminalKind,
126        next_metavar: usize,
127        seq_depth: usize,
128    },
129    Eof,
130}
131
132impl MatcherLoc {
133    pub(super) fn span(&self) -> Option<Span> {
134        match self {
135            MatcherLoc::Token { token } => Some(token.span),
136            MatcherLoc::Delimited => None,
137            MatcherLoc::Sequence { .. } => None,
138            MatcherLoc::SequenceKleeneOpNoSep { .. } => None,
139            MatcherLoc::SequenceSep { .. } => None,
140            MatcherLoc::SequenceKleeneOpAfterSep { .. } => None,
141            MatcherLoc::MetaVarDecl { span, .. } => Some(*span),
142            MatcherLoc::Eof => None,
143        }
144    }
145}
146
147impl Display for MatcherLoc {
148    fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
149        match self {
150            MatcherLoc::Token { token } | MatcherLoc::SequenceSep { separator: token } => {
151                write!(f, "{}", token_descr(token))
152            }
153            MatcherLoc::MetaVarDecl { bind, kind, .. } => {
154                write!(f, "meta-variable `${bind}:{kind}`")
155            }
156            MatcherLoc::Eof => f.write_str("end of macro"),
157
158            // These are not printed in the diagnostic
159            MatcherLoc::Delimited => f.write_str("delimiter"),
160            MatcherLoc::Sequence { .. } => f.write_str("sequence start"),
161            MatcherLoc::SequenceKleeneOpNoSep { .. } => f.write_str("sequence end"),
162            MatcherLoc::SequenceKleeneOpAfterSep { .. } => f.write_str("sequence end"),
163        }
164    }
165}
166
167pub(super) fn compute_locs(matcher: &[TokenTree]) -> Vec<MatcherLoc> {
168    fn inner(
169        tts: &[TokenTree],
170        locs: &mut Vec<MatcherLoc>,
171        next_metavar: &mut usize,
172        seq_depth: usize,
173    ) {
174        for tt in tts {
175            match tt {
176                TokenTree::Token(token) => {
177                    locs.push(MatcherLoc::Token { token: *token });
178                }
179                TokenTree::Delimited(span, _, delimited) => {
180                    let open_token = Token::new(delimited.delim.as_open_token_kind(), span.open);
181                    let close_token = Token::new(delimited.delim.as_close_token_kind(), span.close);
182
183                    locs.push(MatcherLoc::Delimited);
184                    locs.push(MatcherLoc::Token { token: open_token });
185                    inner(&delimited.tts, locs, next_metavar, seq_depth);
186                    locs.push(MatcherLoc::Token { token: close_token });
187                }
188                TokenTree::Sequence(_, seq) => {
189                    // We can't determine `idx_first_after` and construct the final
190                    // `MatcherLoc::Sequence` until after `inner()` is called and the sequence end
191                    // pieces are processed. So we push a dummy value (`Eof` is cheapest to
192                    // construct) now, and overwrite it with the proper value below.
193                    let dummy = MatcherLoc::Eof;
194                    locs.push(dummy);
195
196                    let next_metavar_orig = *next_metavar;
197                    let op = seq.kleene.op;
198                    let idx_first = locs.len();
199                    let idx_seq = idx_first - 1;
200                    inner(&seq.tts, locs, next_metavar, seq_depth + 1);
201
202                    if let Some(separator) = &seq.separator {
203                        locs.push(MatcherLoc::SequenceSep { separator: separator.clone() });
204                        locs.push(MatcherLoc::SequenceKleeneOpAfterSep { idx_first });
205                    } else {
206                        locs.push(MatcherLoc::SequenceKleeneOpNoSep { op, idx_first });
207                    }
208
209                    // Overwrite the dummy value pushed above with the proper value.
210                    locs[idx_seq] = MatcherLoc::Sequence {
211                        op,
212                        num_metavar_decls: seq.num_captures,
213                        idx_first_after: locs.len(),
214                        next_metavar: next_metavar_orig,
215                        seq_depth,
216                    };
217                }
218                &TokenTree::MetaVarDecl { span, name: bind, kind } => {
219                    locs.push(MatcherLoc::MetaVarDecl {
220                        span,
221                        bind,
222                        kind,
223                        next_metavar: *next_metavar,
224                        seq_depth,
225                    });
226                    *next_metavar += 1;
227                }
228                TokenTree::MetaVar(..) | TokenTree::MetaVarExpr(..) => unreachable!(),
229            }
230        }
231    }
232
233    let mut locs = vec![];
234    let mut next_metavar = 0;
235    inner(matcher, &mut locs, &mut next_metavar, /* seq_depth */ 0);
236
237    // A final entry is needed for eof.
238    locs.push(MatcherLoc::Eof);
239
240    locs
241}
242
243/// A single matcher position, representing the state of matching.
244#[derive(Debug)]
245struct MatcherPos {
246    /// The index into `TtParser::locs`, which represents the "dot".
247    idx: usize,
248
249    /// The matches made against metavar decls so far. On a successful match, this vector ends up
250    /// with one element per metavar decl in the matcher. Each element records token trees matched
251    /// against the relevant metavar by the black box parser. An element will be a `MatchedSeq` if
252    /// the corresponding metavar decl is within a sequence.
253    ///
254    /// It is critical to performance that this is an `Rc`, because it gets cloned frequently when
255    /// processing sequences. Mostly for sequence-ending possibilities that must be tried but end
256    /// up failing.
257    matches: Rc<Vec<NamedMatch>>,
258}
259
260// This type is used a lot. Make sure it doesn't unintentionally get bigger.
261#[cfg(target_pointer_width = "64")]
262rustc_data_structures::static_assert_size!(MatcherPos, 16);
263
264impl MatcherPos {
265    /// Adds `m` as a named match for the `metavar_idx`-th metavar. There are only two call sites,
266    /// and both are hot enough to be always worth inlining.
267    #[inline(always)]
268    fn push_match(&mut self, metavar_idx: usize, seq_depth: usize, m: NamedMatch) {
269        let matches = Rc::make_mut(&mut self.matches);
270        match seq_depth {
271            0 => {
272                // We are not within a sequence. Just append `m`.
273                assert_eq!(metavar_idx, matches.len());
274                matches.push(m);
275            }
276            _ => {
277                // We are within a sequence. Find the final `MatchedSeq` at the appropriate depth
278                // and append `m` to its vector.
279                let mut curr = &mut matches[metavar_idx];
280                for _ in 0..seq_depth - 1 {
281                    match curr {
282                        MatchedSeq(seq) => curr = seq.last_mut().unwrap(),
283                        _ => unreachable!(),
284                    }
285                }
286                match curr {
287                    MatchedSeq(seq) => seq.push(m),
288                    _ => unreachable!(),
289                }
290            }
291        }
292    }
293}
294
295enum EofMatcherPositions {
296    None,
297    One(MatcherPos),
298    Multiple,
299}
300
301/// Represents the possible results of an attempted parse.
302pub(crate) enum ParseResult<T, F> {
303    /// Parsed successfully.
304    Success(T),
305    /// Arm failed to match. If the second parameter is `token::Eof`, it indicates an unexpected
306    /// end of macro invocation. Otherwise, it indicates that no rules expected the given token.
307    /// The usize is the approximate position of the token in the input token stream.
308    Failure(F),
309    /// Fatal error (malformed macro?). Abort compilation.
310    Error(rustc_span::Span, String),
311    ErrorReported(ErrorGuaranteed),
312}
313
314/// A `ParseResult` where the `Success` variant contains a mapping of
315/// `MacroRulesNormalizedIdent`s to `NamedMatch`es. This represents the mapping
316/// of metavars to the token trees they bind to.
317pub(crate) type NamedParseResult<F> = ParseResult<NamedMatches, F>;
318
319/// Contains a mapping of `MacroRulesNormalizedIdent`s to `NamedMatch`es.
320/// This represents the mapping of metavars to the token trees they bind to.
321pub(crate) type NamedMatches = FxHashMap<MacroRulesNormalizedIdent, NamedMatch>;
322
323/// Count how many metavars declarations are in `matcher`.
324pub(super) fn count_metavar_decls(matcher: &[TokenTree]) -> usize {
325    matcher
326        .iter()
327        .map(|tt| match tt {
328            TokenTree::MetaVarDecl { .. } => 1,
329            TokenTree::Sequence(_, seq) => seq.num_captures,
330            TokenTree::Delimited(.., delim) => count_metavar_decls(&delim.tts),
331            TokenTree::Token(..) => 0,
332            TokenTree::MetaVar(..) | TokenTree::MetaVarExpr(..) => unreachable!(),
333        })
334        .sum()
335}
336
337/// `NamedMatch` is a pattern-match result for a single metavar. All
338/// `MatchedNonterminal`s in the `NamedMatch` have the same non-terminal type
339/// (expr, item, etc).
340///
341/// The in-memory structure of a particular `NamedMatch` represents the match
342/// that occurred when a particular subset of a matcher was applied to a
343/// particular token tree.
344///
345/// The width of each `MatchedSeq` in the `NamedMatch`, and the identity of
346/// the `MatchedNtNonTts`s, will depend on the token tree it was applied
347/// to: each `MatchedSeq` corresponds to a single repetition in the originating
348/// token tree. The depth of the `NamedMatch` structure will therefore depend
349/// only on the nesting depth of repetitions in the originating token tree it
350/// was derived from.
351///
352/// In layperson's terms: `NamedMatch` will form a tree representing nested matches of a particular
353/// meta variable. For example, if we are matching the following macro against the following
354/// invocation...
355///
356/// ```rust
357/// macro_rules! foo {
358///   ($($($x:ident),+);+) => {}
359/// }
360///
361/// foo!(a, b, c, d; a, b, c, d, e);
362/// ```
363///
364/// Then, the tree will have the following shape:
365///
366/// ```ignore (private-internal)
367/// # use NamedMatch::*;
368/// MatchedSeq([
369///   MatchedSeq([
370///     MatchedNonterminal(a),
371///     MatchedNonterminal(b),
372///     MatchedNonterminal(c),
373///     MatchedNonterminal(d),
374///   ]),
375///   MatchedSeq([
376///     MatchedNonterminal(a),
377///     MatchedNonterminal(b),
378///     MatchedNonterminal(c),
379///     MatchedNonterminal(d),
380///     MatchedNonterminal(e),
381///   ])
382/// ])
383/// ```
384#[derive(Debug, Clone)]
385pub(crate) enum NamedMatch {
386    MatchedSeq(Vec<NamedMatch>),
387    MatchedSingle(ParseNtResult),
388}
389
390/// Performs a token equality check, ignoring syntax context (that is, an unhygienic comparison)
391fn token_name_eq(t1: &Token, t2: &Token) -> bool {
392    if let (Some((ident1, is_raw1)), Some((ident2, is_raw2))) = (t1.ident(), t2.ident()) {
393        ident1.name == ident2.name && is_raw1 == is_raw2
394    } else if let (Some((ident1, is_raw1)), Some((ident2, is_raw2))) =
395        (t1.lifetime(), t2.lifetime())
396    {
397        ident1.name == ident2.name && is_raw1 == is_raw2
398    } else {
399        t1.kind == t2.kind
400    }
401}
402
403// Note: the vectors could be created and dropped within `parse_tt`, but to avoid excess
404// allocations we have a single vector for each kind that is cleared and reused repeatedly.
405pub(crate) struct TtParser {
406    macro_name: Ident,
407
408    /// The set of current mps to be processed. This should be empty by the end of a successful
409    /// execution of `parse_tt_inner`.
410    cur_mps: Vec<MatcherPos>,
411
412    /// The set of newly generated mps. These are used to replenish `cur_mps` in the function
413    /// `parse_tt`.
414    next_mps: Vec<MatcherPos>,
415
416    /// The set of mps that are waiting for the black-box parser.
417    bb_mps: Vec<MatcherPos>,
418
419    /// Pre-allocate an empty match array, so it can be cloned cheaply for macros with many rules
420    /// that have no metavars.
421    empty_matches: Rc<Vec<NamedMatch>>,
422}
423
424impl TtParser {
425    pub(super) fn new(macro_name: Ident) -> TtParser {
426        TtParser {
427            macro_name,
428            cur_mps: vec![],
429            next_mps: vec![],
430            bb_mps: vec![],
431            empty_matches: Rc::new(vec![]),
432        }
433    }
434
435    pub(super) fn has_no_remaining_items_for_step(&self) -> bool {
436        self.cur_mps.is_empty()
437    }
438
439    /// Process the matcher positions of `cur_mps` until it is empty. In the process, this will
440    /// produce more mps in `next_mps` and `bb_mps`.
441    ///
442    /// # Returns
443    ///
444    /// `Some(result)` if everything is finished, `None` otherwise. Note that matches are kept
445    /// track of through the mps generated.
446    fn parse_tt_inner<'matcher, T: Tracker<'matcher>>(
447        &mut self,
448        matcher: &'matcher [MatcherLoc],
449        token: &Token,
450        approx_position: u32,
451        track: &mut T,
452    ) -> Option<NamedParseResult<T::Failure>> {
453        // Matcher positions that would be valid if the macro invocation was over now. Only
454        // modified if `token == Eof`.
455        let mut eof_mps = EofMatcherPositions::None;
456
457        while let Some(mut mp) = self.cur_mps.pop() {
458            let matcher_loc = &matcher[mp.idx];
459            track.before_match_loc(self, matcher_loc);
460
461            match matcher_loc {
462                MatcherLoc::Token { token: t } => {
463                    // If it's a doc comment, we just ignore it and move on to the next tt in the
464                    // matcher. This is a bug, but #95267 showed that existing programs rely on
465                    // this behaviour, and changing it would require some care and a transition
466                    // period.
467                    //
468                    // If the token matches, we can just advance the parser.
469                    //
470                    // Otherwise, this match has failed, there is nothing to do, and hopefully
471                    // another mp in `cur_mps` will match.
472                    if matches!(t, Token { kind: DocComment(..), .. }) {
473                        mp.idx += 1;
474                        self.cur_mps.push(mp);
475                    } else if token_name_eq(t, token) {
476                        mp.idx += 1;
477                        self.next_mps.push(mp);
478                    }
479                }
480                MatcherLoc::Delimited => {
481                    // Entering the delimiter is trivial.
482                    mp.idx += 1;
483                    self.cur_mps.push(mp);
484                }
485                &MatcherLoc::Sequence {
486                    op,
487                    num_metavar_decls,
488                    idx_first_after,
489                    next_metavar,
490                    seq_depth,
491                } => {
492                    // Install an empty vec for each metavar within the sequence.
493                    for metavar_idx in next_metavar..next_metavar + num_metavar_decls {
494                        mp.push_match(metavar_idx, seq_depth, MatchedSeq(vec![]));
495                    }
496
497                    if matches!(op, KleeneOp::ZeroOrMore | KleeneOp::ZeroOrOne) {
498                        // Try zero matches of this sequence, by skipping over it.
499                        self.cur_mps.push(MatcherPos {
500                            idx: idx_first_after,
501                            matches: Rc::clone(&mp.matches),
502                        });
503                    }
504
505                    // Try one or more matches of this sequence, by entering it.
506                    mp.idx += 1;
507                    self.cur_mps.push(mp);
508                }
509                &MatcherLoc::SequenceKleeneOpNoSep { op, idx_first } => {
510                    // We are past the end of a sequence with no separator. Try ending the
511                    // sequence. If that's not possible, `ending_mp` will fail quietly when it is
512                    // processed next time around the loop.
513                    let ending_mp = MatcherPos {
514                        idx: mp.idx + 1, // +1 skips the Kleene op
515                        matches: Rc::clone(&mp.matches),
516                    };
517                    self.cur_mps.push(ending_mp);
518
519                    if op != KleeneOp::ZeroOrOne {
520                        // Try another repetition.
521                        mp.idx = idx_first;
522                        self.cur_mps.push(mp);
523                    }
524                }
525                MatcherLoc::SequenceSep { separator } => {
526                    // We are past the end of a sequence with a separator but we haven't seen the
527                    // separator yet. Try ending the sequence. If that's not possible, `ending_mp`
528                    // will fail quietly when it is processed next time around the loop.
529                    let ending_mp = MatcherPos {
530                        idx: mp.idx + 2, // +2 skips the separator and the Kleene op
531                        matches: Rc::clone(&mp.matches),
532                    };
533                    self.cur_mps.push(ending_mp);
534
535                    if token_name_eq(token, separator) {
536                        // The separator matches the current token. Advance past it.
537                        mp.idx += 1;
538                        self.next_mps.push(mp);
539                    } else {
540                        track.set_expected_token(separator);
541                    }
542                }
543                &MatcherLoc::SequenceKleeneOpAfterSep { idx_first } => {
544                    // We are past the sequence separator. This can't be a `?` Kleene op, because
545                    // they don't permit separators. Try another repetition.
546                    mp.idx = idx_first;
547                    self.cur_mps.push(mp);
548                }
549                &MatcherLoc::MetaVarDecl { kind, .. } => {
550                    // Built-in nonterminals never start with these tokens, so we can eliminate
551                    // them from consideration. We use the span of the metavariable declaration
552                    // to determine any edition-specific matching behavior for non-terminals.
553                    if Parser::nonterminal_may_begin_with(kind, token) {
554                        self.bb_mps.push(mp);
555                    }
556                }
557                MatcherLoc::Eof => {
558                    // We are past the matcher's end, and not in a sequence. Try to end things.
559                    debug_assert_eq!(mp.idx, matcher.len() - 1);
560                    if *token == token::Eof {
561                        eof_mps = match eof_mps {
562                            EofMatcherPositions::None => EofMatcherPositions::One(mp),
563                            EofMatcherPositions::One(_) | EofMatcherPositions::Multiple => {
564                                EofMatcherPositions::Multiple
565                            }
566                        }
567                    }
568                }
569            }
570        }
571
572        // If we reached the end of input, check that there is EXACTLY ONE possible matcher.
573        // Otherwise, either the parse is ambiguous (which is an error) or there is a syntax error.
574        if *token == token::Eof {
575            Some(match eof_mps {
576                EofMatcherPositions::One(mut eof_mp) => {
577                    // Need to take ownership of the matches from within the `Rc`.
578                    Rc::make_mut(&mut eof_mp.matches);
579                    let matches = Rc::try_unwrap(eof_mp.matches).unwrap().into_iter();
580                    self.nameize(matcher, matches)
581                }
582                EofMatcherPositions::Multiple => {
583                    Error(token.span, "ambiguity: multiple successful parses".to_string())
584                }
585                EofMatcherPositions::None => Failure(T::build_failure(
586                    Token::new(
587                        token::Eof,
588                        if token.span.is_dummy() { token.span } else { token.span.shrink_to_hi() },
589                    ),
590                    approx_position,
591                    "missing tokens in macro arguments",
592                )),
593            })
594        } else {
595            None
596        }
597    }
598
599    /// Match the token stream from `parser` against `matcher`.
600    pub(super) fn parse_tt<'matcher, T: Tracker<'matcher>>(
601        &mut self,
602        parser: &mut Cow<'_, Parser<'_>>,
603        matcher: &'matcher [MatcherLoc],
604        track: &mut T,
605    ) -> NamedParseResult<T::Failure> {
606        // A queue of possible matcher positions. We initialize it with the matcher position in
607        // which the "dot" is before the first token of the first token tree in `matcher`.
608        // `parse_tt_inner` then processes all of these possible matcher positions and produces
609        // possible next positions into `next_mps`. After some post-processing, the contents of
610        // `next_mps` replenish `cur_mps` and we start over again.
611        self.cur_mps.clear();
612        self.cur_mps.push(MatcherPos { idx: 0, matches: Rc::clone(&self.empty_matches) });
613
614        loop {
615            self.next_mps.clear();
616            self.bb_mps.clear();
617
618            // Process `cur_mps` until either we have finished the input or we need to get some
619            // parsing from the black-box parser done.
620            let res = self.parse_tt_inner(
621                matcher,
622                &parser.token,
623                parser.approx_token_stream_pos(),
624                track,
625            );
626
627            if let Some(res) = res {
628                return res;
629            }
630
631            // `parse_tt_inner` handled all of `cur_mps`, so it's empty.
632            assert!(self.cur_mps.is_empty());
633
634            // Error messages here could be improved with links to original rules.
635            match (self.next_mps.len(), self.bb_mps.len()) {
636                (0, 0) => {
637                    // There are no possible next positions AND we aren't waiting for the black-box
638                    // parser: syntax error.
639                    return Failure(T::build_failure(
640                        parser.token,
641                        parser.approx_token_stream_pos(),
642                        "no rules expected this token in macro call",
643                    ));
644                }
645
646                (_, 0) => {
647                    // Dump all possible `next_mps` into `cur_mps` for the next iteration. Then
648                    // process the next token.
649                    self.cur_mps.append(&mut self.next_mps);
650                    parser.to_mut().bump();
651                }
652
653                (0, 1) => {
654                    // We need to call the black-box parser to get some nonterminal.
655                    let mut mp = self.bb_mps.pop().unwrap();
656                    let loc = &matcher[mp.idx];
657                    if let &MatcherLoc::MetaVarDecl {
658                        span, kind, next_metavar, seq_depth, ..
659                    } = loc
660                    {
661                        // We use the span of the metavariable declaration to determine any
662                        // edition-specific matching behavior for non-terminals.
663                        let nt = match parser.to_mut().parse_nonterminal(kind) {
664                            Err(err) => {
665                                let guarantee = err.with_span_label(
666                                    span,
667                                    format!(
668                                        "while parsing argument for this `{kind}` macro fragment"
669                                    ),
670                                )
671                                .emit();
672                                return ErrorReported(guarantee);
673                            }
674                            Ok(nt) => nt,
675                        };
676                        mp.push_match(next_metavar, seq_depth, MatchedSingle(nt));
677                        mp.idx += 1;
678                    } else {
679                        unreachable!()
680                    }
681                    self.cur_mps.push(mp);
682                }
683
684                (_, _) => {
685                    // Too many possibilities!
686                    return self.ambiguity_error(matcher, parser.token.span);
687                }
688            }
689
690            assert!(!self.cur_mps.is_empty());
691        }
692    }
693
694    fn ambiguity_error<F>(
695        &self,
696        matcher: &[MatcherLoc],
697        token_span: rustc_span::Span,
698    ) -> NamedParseResult<F> {
699        let nts = self
700            .bb_mps
701            .iter()
702            .map(|mp| match &matcher[mp.idx] {
703                MatcherLoc::MetaVarDecl { bind, kind, .. } => {
704                    format!("{kind} ('{bind}')")
705                }
706                _ => unreachable!(),
707            })
708            .collect::<Vec<String>>()
709            .join(" or ");
710
711        Error(
712            token_span,
713            format!(
714                "local ambiguity when calling macro `{}`: multiple parsing options: {}",
715                self.macro_name,
716                match self.next_mps.len() {
717                    0 => format!("built-in NTs {nts}."),
718                    n => format!("built-in NTs {nts} or {n} other option{s}.", s = pluralize!(n)),
719                }
720            ),
721        )
722    }
723
724    fn nameize<I: Iterator<Item = NamedMatch>, F>(
725        &self,
726        matcher: &[MatcherLoc],
727        mut res: I,
728    ) -> NamedParseResult<F> {
729        // Make that each metavar has _exactly one_ binding. If so, insert the binding into the
730        // `NamedParseResult`. Otherwise, it's an error.
731        let mut ret_val = FxHashMap::default();
732        for loc in matcher {
733            if let &MatcherLoc::MetaVarDecl { span, bind, .. } = loc {
734                match ret_val.entry(MacroRulesNormalizedIdent::new(bind)) {
735                    Vacant(spot) => spot.insert(res.next().unwrap()),
736                    Occupied(..) => {
737                        return Error(span, format!("duplicated bind name: {bind}"));
738                    }
739                };
740            }
741        }
742        Success(ret_val)
743    }
744}