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