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.
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)
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.
15 //! Quick intro to how the parser works:
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`.
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`.
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.
34 //! Start parsing a a a a b against [· a $( a )* a b].
36 //! Remaining input: a a a a b
37 //! next: [· a $( a )* a b]
39 //! - - - Advance over an a. - - -
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].
46 //! - - - Advance over an a. - - -
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]
53 //! - - - Advance over an a. - - - (this looks exactly like the last step)
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]
60 //! - - - Advance over an a. - - - (this looks exactly like the last step)
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]
67 //! - - - Advance over a b. - - -
69 //! Remaining input: ''
70 //! eof: [a $( a )* a b ·]
73 use rustc_errors::ErrorGuaranteed;
74 pub(crate) use NamedMatch::*;
75 pub(crate) use ParseResult::*;
77 use crate::mbe::{macro_rules::Tracker, KleeneOp, TokenTree};
79 use rustc_ast::token::{self, DocComment, Nonterminal, NonterminalKind, Token};
80 use rustc_data_structures::fx::FxHashMap;
81 use rustc_data_structures::sync::Lrc;
82 use rustc_lint_defs::pluralize;
83 use rustc_parse::parser::{NtOrTt, Parser};
84 use rustc_span::symbol::Ident;
85 use rustc_span::symbol::MacroRulesNormalizedIdent;
88 use std::collections::hash_map::Entry::{Occupied, Vacant};
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.
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, Clone, PartialEq)]
100 pub(crate) enum MatcherLoc {
107 num_metavar_decls: usize,
108 idx_first_after: usize,
112 SequenceKleeneOpNoSep {
119 SequenceKleeneOpAfterSep {
125 kind: Option<NonterminalKind>,
132 pub(super) fn compute_locs(matcher: &[TokenTree]) -> Vec<MatcherLoc> {
135 locs: &mut Vec<MatcherLoc>,
136 next_metavar: &mut usize,
141 TokenTree::Token(token) => {
142 locs.push(MatcherLoc::Token { token: token.clone() });
144 TokenTree::Delimited(span, delimited) => {
145 let open_token = Token::new(token::OpenDelim(delimited.delim), span.open);
146 let close_token = Token::new(token::CloseDelim(delimited.delim), span.close);
148 locs.push(MatcherLoc::Delimited);
149 locs.push(MatcherLoc::Token { token: open_token });
150 inner(&delimited.tts, locs, next_metavar, seq_depth);
151 locs.push(MatcherLoc::Token { token: close_token });
153 TokenTree::Sequence(_, seq) => {
154 // We can't determine `idx_first_after` and construct the final
155 // `MatcherLoc::Sequence` until after `inner()` is called and the sequence end
156 // pieces are processed. So we push a dummy value (`Eof` is cheapest to
157 // construct) now, and overwrite it with the proper value below.
158 let dummy = MatcherLoc::Eof;
161 let next_metavar_orig = *next_metavar;
162 let op = seq.kleene.op;
163 let idx_first = locs.len();
164 let idx_seq = idx_first - 1;
165 inner(&seq.tts, locs, next_metavar, seq_depth + 1);
167 if let Some(separator) = &seq.separator {
168 locs.push(MatcherLoc::SequenceSep { separator: separator.clone() });
169 locs.push(MatcherLoc::SequenceKleeneOpAfterSep { idx_first });
171 locs.push(MatcherLoc::SequenceKleeneOpNoSep { op, idx_first });
174 // Overwrite the dummy value pushed above with the proper value.
175 locs[idx_seq] = MatcherLoc::Sequence {
177 num_metavar_decls: seq.num_captures,
178 idx_first_after: locs.len(),
179 next_metavar: next_metavar_orig,
183 &TokenTree::MetaVarDecl(span, bind, kind) => {
184 locs.push(MatcherLoc::MetaVarDecl {
188 next_metavar: *next_metavar,
193 TokenTree::MetaVar(..) | TokenTree::MetaVarExpr(..) => unreachable!(),
198 let mut locs = vec![];
199 let mut next_metavar = 0;
200 inner(matcher, &mut locs, &mut next_metavar, /* seq_depth */ 0);
202 // A final entry is needed for eof.
203 locs.push(MatcherLoc::Eof);
208 /// A single matcher position, representing the state of matching.
210 /// The index into `TtParser::locs`, which represents the "dot".
213 /// The matches made against metavar decls so far. On a successful match, this vector ends up
214 /// with one element per metavar decl in the matcher. Each element records token trees matched
215 /// against the relevant metavar by the black box parser. An element will be a `MatchedSeq` if
216 /// the corresponding metavar decl is within a sequence.
218 /// It is critical to performance that this is an `Lrc`, because it gets cloned frequently when
219 /// processing sequences. Mostly for sequence-ending possibilities that must be tried but end
221 matches: Lrc<Vec<NamedMatch>>,
224 // This type is used a lot. Make sure it doesn't unintentionally get bigger.
225 #[cfg(all(target_arch = "x86_64", target_pointer_width = "64"))]
226 rustc_data_structures::static_assert_size!(MatcherPos, 16);
229 /// Adds `m` as a named match for the `metavar_idx`-th metavar. There are only two call sites,
230 /// and both are hot enough to be always worth inlining.
232 fn push_match(&mut self, metavar_idx: usize, seq_depth: usize, m: NamedMatch) {
233 let matches = Lrc::make_mut(&mut self.matches);
236 // We are not within a sequence. Just append `m`.
237 assert_eq!(metavar_idx, matches.len());
241 // We are within a sequence. Find the final `MatchedSeq` at the appropriate depth
242 // and append `m` to its vector.
243 let mut curr = &mut matches[metavar_idx];
244 for _ in 0..seq_depth - 1 {
246 MatchedSeq(seq) => curr = seq.last_mut().unwrap(),
251 MatchedSeq(seq) => seq.push(m),
259 enum EofMatcherPositions {
265 /// Represents the possible results of an attempted parse.
266 pub(crate) enum ParseResult<T> {
267 /// Parsed successfully.
269 /// Arm failed to match. If the second parameter is `token::Eof`, it indicates an unexpected
270 /// end of macro invocation. Otherwise, it indicates that no rules expected the given token.
271 Failure(Token, &'static str),
272 /// Fatal error (malformed macro?). Abort compilation.
273 Error(rustc_span::Span, String),
274 ErrorReported(ErrorGuaranteed),
277 /// A `ParseResult` where the `Success` variant contains a mapping of
278 /// `MacroRulesNormalizedIdent`s to `NamedMatch`es. This represents the mapping
279 /// of metavars to the token trees they bind to.
280 pub(crate) type NamedParseResult = ParseResult<NamedMatches>;
282 /// Contains a mapping of `MacroRulesNormalizedIdent`s to `NamedMatch`es.
283 /// This represents the mapping of metavars to the token trees they bind to.
284 pub(crate) type NamedMatches = FxHashMap<MacroRulesNormalizedIdent, NamedMatch>;
286 /// Count how many metavars declarations are in `matcher`.
287 pub(super) fn count_metavar_decls(matcher: &[TokenTree]) -> usize {
291 TokenTree::MetaVarDecl(..) => 1,
292 TokenTree::Sequence(_, seq) => seq.num_captures,
293 TokenTree::Delimited(_, delim) => count_metavar_decls(&delim.tts),
294 TokenTree::Token(..) => 0,
295 TokenTree::MetaVar(..) | TokenTree::MetaVarExpr(..) => unreachable!(),
300 /// `NamedMatch` is a pattern-match result for a single metavar. All
301 /// `MatchedNonterminal`s in the `NamedMatch` have the same non-terminal type
302 /// (expr, item, etc).
304 /// The in-memory structure of a particular `NamedMatch` represents the match
305 /// that occurred when a particular subset of a matcher was applied to a
306 /// particular token tree.
308 /// The width of each `MatchedSeq` in the `NamedMatch`, and the identity of
309 /// the `MatchedNtNonTts`s, will depend on the token tree it was applied
310 /// to: each `MatchedSeq` corresponds to a single repetition in the originating
311 /// token tree. The depth of the `NamedMatch` structure will therefore depend
312 /// only on the nesting depth of repetitions in the originating token tree it
313 /// was derived from.
315 /// In layperson's terms: `NamedMatch` will form a tree representing nested matches of a particular
316 /// meta variable. For example, if we are matching the following macro against the following
320 /// macro_rules! foo {
321 /// ($($($x:ident),+);+) => {}
324 /// foo!(a, b, c, d; a, b, c, d, e);
327 /// Then, the tree will have the following shape:
329 /// ```ignore (private-internal)
330 /// # use NamedMatch::*;
333 /// MatchedNonterminal(a),
334 /// MatchedNonterminal(b),
335 /// MatchedNonterminal(c),
336 /// MatchedNonterminal(d),
339 /// MatchedNonterminal(a),
340 /// MatchedNonterminal(b),
341 /// MatchedNonterminal(c),
342 /// MatchedNonterminal(d),
343 /// MatchedNonterminal(e),
347 #[derive(Debug, Clone)]
348 pub(crate) enum NamedMatch {
349 MatchedSeq(Vec<NamedMatch>),
351 // A metavar match of type `tt`.
352 MatchedTokenTree(rustc_ast::tokenstream::TokenTree),
354 // A metavar match of any type other than `tt`.
355 MatchedNonterminal(Lrc<Nonterminal>),
358 /// Performs a token equality check, ignoring syntax context (that is, an unhygienic comparison)
359 fn token_name_eq(t1: &Token, t2: &Token) -> bool {
360 if let (Some((ident1, is_raw1)), Some((ident2, is_raw2))) = (t1.ident(), t2.ident()) {
361 ident1.name == ident2.name && is_raw1 == is_raw2
362 } else if let (Some(ident1), Some(ident2)) = (t1.lifetime(), t2.lifetime()) {
363 ident1.name == ident2.name
369 // Note: the vectors could be created and dropped within `parse_tt`, but to avoid excess
370 // allocations we have a single vector for each kind that is cleared and reused repeatedly.
371 pub struct TtParser {
374 /// The set of current mps to be processed. This should be empty by the end of a successful
375 /// execution of `parse_tt_inner`.
376 cur_mps: Vec<MatcherPos>,
378 /// The set of newly generated mps. These are used to replenish `cur_mps` in the function
380 next_mps: Vec<MatcherPos>,
382 /// The set of mps that are waiting for the black-box parser.
383 bb_mps: Vec<MatcherPos>,
385 /// Pre-allocate an empty match array, so it can be cloned cheaply for macros with many rules
386 /// that have no metavars.
387 empty_matches: Lrc<Vec<NamedMatch>>,
391 pub(super) fn new(macro_name: Ident) -> TtParser {
397 empty_matches: Lrc::new(vec![]),
401 /// Process the matcher positions of `cur_mps` until it is empty. In the process, this will
402 /// produce more mps in `next_mps` and `bb_mps`.
406 /// `Some(result)` if everything is finished, `None` otherwise. Note that matches are kept
407 /// track of through the mps generated.
408 fn parse_tt_inner<'matcher, T: Tracker<'matcher>>(
410 matcher: &'matcher [MatcherLoc],
413 ) -> Option<NamedParseResult> {
414 // Matcher positions that would be valid if the macro invocation was over now. Only
415 // modified if `token == Eof`.
416 let mut eof_mps = EofMatcherPositions::None;
418 while let Some(mut mp) = self.cur_mps.pop() {
419 let matcher_loc = &matcher[mp.idx];
420 track.before_match_loc(self, matcher_loc);
423 MatcherLoc::Token { token: t } => {
424 // If it's a doc comment, we just ignore it and move on to the next tt in the
425 // matcher. This is a bug, but #95267 showed that existing programs rely on
426 // this behaviour, and changing it would require some care and a transition
429 // If the token matches, we can just advance the parser.
431 // Otherwise, this match has failed, there is nothing to do, and hopefully
432 // another mp in `cur_mps` will match.
433 if matches!(t, Token { kind: DocComment(..), .. }) {
435 self.cur_mps.push(mp);
436 } else if token_name_eq(&t, token) {
438 self.next_mps.push(mp);
441 MatcherLoc::Delimited => {
442 // Entering the delimiter is trivial.
444 self.cur_mps.push(mp);
446 &MatcherLoc::Sequence {
453 // Install an empty vec for each metavar within the sequence.
454 for metavar_idx in next_metavar..next_metavar + num_metavar_decls {
455 mp.push_match(metavar_idx, seq_depth, MatchedSeq(vec![]));
458 if op == KleeneOp::ZeroOrMore || op == KleeneOp::ZeroOrOne {
459 // Try zero matches of this sequence, by skipping over it.
460 self.cur_mps.push(MatcherPos {
461 idx: idx_first_after,
462 matches: Lrc::clone(&mp.matches),
466 // Try one or more matches of this sequence, by entering it.
468 self.cur_mps.push(mp);
470 &MatcherLoc::SequenceKleeneOpNoSep { op, idx_first } => {
471 // We are past the end of a sequence with no separator. Try ending the
472 // sequence. If that's not possible, `ending_mp` will fail quietly when it is
473 // processed next time around the loop.
474 let ending_mp = MatcherPos {
475 idx: mp.idx + 1, // +1 skips the Kleene op
476 matches: Lrc::clone(&mp.matches),
478 self.cur_mps.push(ending_mp);
480 if op != KleeneOp::ZeroOrOne {
481 // Try another repetition.
483 self.cur_mps.push(mp);
486 MatcherLoc::SequenceSep { separator } => {
487 // We are past the end of a sequence with a separator but we haven't seen the
488 // separator yet. Try ending the sequence. If that's not possible, `ending_mp`
489 // will fail quietly when it is processed next time around the loop.
490 let ending_mp = MatcherPos {
491 idx: mp.idx + 2, // +2 skips the separator and the Kleene op
492 matches: Lrc::clone(&mp.matches),
494 self.cur_mps.push(ending_mp);
496 if token_name_eq(token, separator) {
497 // The separator matches the current token. Advance past it.
499 self.next_mps.push(mp);
502 &MatcherLoc::SequenceKleeneOpAfterSep { idx_first } => {
503 // We are past the sequence separator. This can't be a `?` Kleene op, because
504 // they don't permit separators. Try another repetition.
506 self.cur_mps.push(mp);
508 &MatcherLoc::MetaVarDecl { span, kind, .. } => {
509 // Built-in nonterminals never start with these tokens, so we can eliminate
510 // them from consideration. We use the span of the metavariable declaration
511 // to determine any edition-specific matching behavior for non-terminals.
512 if let Some(kind) = kind {
513 if Parser::nonterminal_may_begin_with(kind, token) {
514 self.bb_mps.push(mp);
517 // E.g. `$e` instead of `$e:expr`, reported as a hard error if actually used.
518 // Both this check and the one in `nameize` are necessary, surprisingly.
519 return Some(Error(span, "missing fragment specifier".to_string()));
523 // We are past the matcher's end, and not in a sequence. Try to end things.
524 debug_assert_eq!(mp.idx, matcher.len() - 1);
525 if *token == token::Eof {
526 eof_mps = match eof_mps {
527 EofMatcherPositions::None => EofMatcherPositions::One(mp),
528 EofMatcherPositions::One(_) | EofMatcherPositions::Multiple => {
529 EofMatcherPositions::Multiple
537 // If we reached the end of input, check that there is EXACTLY ONE possible matcher.
538 // Otherwise, either the parse is ambiguous (which is an error) or there is a syntax error.
539 if *token == token::Eof {
541 EofMatcherPositions::One(mut eof_mp) => {
542 // Need to take ownership of the matches from within the `Lrc`.
543 Lrc::make_mut(&mut eof_mp.matches);
544 let matches = Lrc::try_unwrap(eof_mp.matches).unwrap().into_iter();
545 self.nameize(matcher, matches)
547 EofMatcherPositions::Multiple => {
548 Error(token.span, "ambiguity: multiple successful parses".to_string())
550 EofMatcherPositions::None => Failure(
553 if token.span.is_dummy() { token.span } else { token.span.shrink_to_hi() },
555 "missing tokens in macro arguments",
563 /// Match the token stream from `parser` against `matcher`.
564 pub(super) fn parse_tt<'matcher, T: Tracker<'matcher>>(
566 parser: &mut Cow<'_, Parser<'_>>,
567 matcher: &'matcher [MatcherLoc],
569 ) -> NamedParseResult {
570 // A queue of possible matcher positions. We initialize it with the matcher position in
571 // which the "dot" is before the first token of the first token tree in `matcher`.
572 // `parse_tt_inner` then processes all of these possible matcher positions and produces
573 // possible next positions into `next_mps`. After some post-processing, the contents of
574 // `next_mps` replenish `cur_mps` and we start over again.
575 self.cur_mps.clear();
576 self.cur_mps.push(MatcherPos { idx: 0, matches: self.empty_matches.clone() });
579 self.next_mps.clear();
582 // Process `cur_mps` until either we have finished the input or we need to get some
583 // parsing from the black-box parser done.
584 let res = self.parse_tt_inner(matcher, &parser.token, track);
585 if let Some(res) = res {
589 // `parse_tt_inner` handled all of `cur_mps`, so it's empty.
590 assert!(self.cur_mps.is_empty());
592 // Error messages here could be improved with links to original rules.
593 match (self.next_mps.len(), self.bb_mps.len()) {
595 // There are no possible next positions AND we aren't waiting for the black-box
596 // parser: syntax error.
598 parser.token.clone(),
599 "no rules expected this token in macro call",
604 // Dump all possible `next_mps` into `cur_mps` for the next iteration. Then
605 // process the next token.
606 self.cur_mps.append(&mut self.next_mps);
607 parser.to_mut().bump();
611 // We need to call the black-box parser to get some nonterminal.
612 let mut mp = self.bb_mps.pop().unwrap();
613 let loc = &matcher[mp.idx];
614 if let &MatcherLoc::MetaVarDecl {
622 // We use the span of the metavariable declaration to determine any
623 // edition-specific matching behavior for non-terminals.
624 let nt = match parser.to_mut().parse_nonterminal(kind) {
626 let guarantee = err.span_label(
629 "while parsing argument for this `{kind}` macro fragment"
633 return ErrorReported(guarantee);
638 NtOrTt::Nt(nt) => MatchedNonterminal(Lrc::new(nt)),
639 NtOrTt::Tt(tt) => MatchedTokenTree(tt),
641 mp.push_match(next_metavar, seq_depth, m);
646 self.cur_mps.push(mp);
650 // Too many possibilities!
651 return self.ambiguity_error(matcher, parser.token.span);
655 assert!(!self.cur_mps.is_empty());
661 matcher: &[MatcherLoc],
662 token_span: rustc_span::Span,
663 ) -> NamedParseResult {
667 .map(|mp| match &matcher[mp.idx] {
668 MatcherLoc::MetaVarDecl { bind, kind: Some(kind), .. } => {
669 format!("{} ('{}')", kind, bind)
673 .collect::<Vec<String>>()
679 "local ambiguity when calling macro `{}`: multiple parsing options: {}",
681 match self.next_mps.len() {
682 0 => format!("built-in NTs {}.", nts),
683 n => format!("built-in NTs {} or {n} other option{s}.", nts, s = pluralize!(n)),
689 fn nameize<I: Iterator<Item = NamedMatch>>(
691 matcher: &[MatcherLoc],
693 ) -> NamedParseResult {
694 // Make that each metavar has _exactly one_ binding. If so, insert the binding into the
695 // `NamedParseResult`. Otherwise, it's an error.
696 let mut ret_val = FxHashMap::default();
698 if let &MatcherLoc::MetaVarDecl { span, bind, kind, .. } = loc {
700 match ret_val.entry(MacroRulesNormalizedIdent::new(bind)) {
701 Vacant(spot) => spot.insert(res.next().unwrap()),
703 return Error(span, format!("duplicated bind name: {}", bind));
707 // E.g. `$e` instead of `$e:expr`, reported as a hard error if actually used.
708 // Both this check and the one in `parse_tt_inner` are necessary, surprisingly.
709 return Error(span, "missing fragment specifier".to_string());