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