//! This is an NFA-based parser, which calls out to the main Rust parser for named non-terminals //! (which it commits to fully when it hits one in a grammar). There's a set of current NFA threads //! and a set of next ones. Instead of NTs, we have a special case for Kleene star. The big-O, in //! pathological cases, is worse than traditional use of NFA or Earley parsing, but it's an easier //! fit for Macro-by-Example-style rules. //! //! (In order to prevent the pathological case, we'd need to lazily construct the resulting //! `NamedMatch`es at the very end. It'd be a pain, and require more memory to keep around old //! items, but it would also save overhead) //! //! We don't say this parser uses the Earley algorithm, because it's unnecessarily inaccurate. //! The macro parser restricts itself to the features of finite state automata. Earley parsers //! can be described as an extension of NFAs with completion rules, prediction rules, and recursion. //! //! Quick intro to how the parser works: //! //! A 'position' is a dot in the middle of a matcher, usually represented as a //! dot. For example `· a $( a )* a b` is a position, as is `a $( · a )* a b`. //! //! The parser walks through the input a character at a time, maintaining a list //! of threads consistent with the current position in the input string: `cur_items`. //! //! As it processes them, it fills up `eof_items` with threads that would be valid if //! the macro invocation is now over, `bb_items` with threads that are waiting on //! a Rust non-terminal like `$e:expr`, and `next_items` with threads that are waiting //! on a particular token. Most of the logic concerns moving the · through the //! repetitions indicated by Kleene stars. The rules for moving the · without //! consuming any input are called epsilon transitions. It only advances or calls //! out to the real Rust parser when no `cur_items` threads remain. //! //! Example: //! //! ```text, ignore //! Start parsing a a a a b against [· a $( a )* a b]. //! //! Remaining input: a a a a b //! next: [· a $( a )* a b] //! //! - - - Advance over an a. - - - //! //! Remaining input: a a a b //! cur: [a · $( a )* a b] //! Descend/Skip (first item). //! next: [a $( · a )* a b] [a $( a )* · a b]. //! //! - - - Advance over an a. - - - //! //! Remaining input: a a b //! cur: [a $( a · )* a b] [a $( a )* a · b] //! Follow epsilon transition: Finish/Repeat (first item) //! next: [a $( a )* · a b] [a $( · a )* a b] [a $( a )* a · b] //! //! - - - Advance over an a. - - - (this looks exactly like the last step) //! //! Remaining input: a b //! cur: [a $( a · )* a b] [a $( a )* a · b] //! Follow epsilon transition: Finish/Repeat (first item) //! next: [a $( a )* · a b] [a $( · a )* a b] [a $( a )* a · b] //! //! - - - Advance over an a. - - - (this looks exactly like the last step) //! //! Remaining input: b //! cur: [a $( a · )* a b] [a $( a )* a · b] //! Follow epsilon transition: Finish/Repeat (first item) //! next: [a $( a )* · a b] [a $( · a )* a b] [a $( a )* a · b] //! //! - - - Advance over a b. - - - //! //! Remaining input: '' //! eof: [a $( a )* a b ·] //! ``` crate use NamedMatch::*; crate use ParseResult::*; use crate::mbe::{self, SequenceRepetition, TokenTree}; use rustc_ast::token::{self, DocComment, Nonterminal, Token}; use rustc_parse::parser::Parser; use rustc_session::parse::ParseSess; use rustc_span::symbol::MacroRulesNormalizedIdent; use smallvec::{smallvec, SmallVec}; use rustc_data_structures::fx::FxHashMap; use rustc_data_structures::sync::Lrc; use rustc_span::symbol::Ident; use std::borrow::Cow; use std::collections::hash_map::Entry::{Occupied, Vacant}; use std::mem; /// An unzipping of `TokenTree`s... see the `stack` field of `MatcherPos`. /// /// This is used by `parse_tt_inner` to keep track of delimited submatchers that we have /// descended into. #[derive(Clone)] struct MatcherTtFrame<'tt> { /// The "parent" matcher that we are descending into. elts: &'tt [TokenTree], /// The position of the "dot" in `elts` at the time we descended. idx: usize, } // One element is enough to cover 95-99% of vectors for most benchmarks. Also, // vectors longer than one frequently have many elements, not just two or // three. type NamedMatchVec = SmallVec<[NamedMatch; 1]>; // This type is used a lot. Make sure it doesn't unintentionally get bigger. #[cfg(all(target_arch = "x86_64", target_pointer_width = "64"))] rustc_data_structures::static_assert_size!(NamedMatchVec, 48); /// Represents a single "position" (aka "matcher position", aka "item"), as /// described in the module documentation. #[derive(Clone)] struct MatcherPos<'tt> { /// The token or slice of tokens that make up the matcher. `elts` is short for "elements". top_elts: &'tt [TokenTree], /// The position of the "dot" in this matcher idx: usize, /// For each named metavar in the matcher, we keep track of token trees matched against the /// metavar by the black box parser. In particular, there may be more than one match per /// metavar if we are in a repetition (each repetition matches each of the variables). /// Moreover, matchers and repetitions can be nested; the `matches` field is shared (hence the /// `Rc`) among all "nested" matchers. `match_lo`, `match_cur`, and `match_hi` keep track of /// the current position of the `self` matcher position in the shared `matches` list. /// /// Also, note that while we are descending into a sequence, matchers are given their own /// `matches` vector. Only once we reach the end of a full repetition of the sequence do we add /// all bound matches from the submatcher into the shared top-level `matches` vector. If `sep` /// and `up` are `Some`, then `matches` is _not_ the shared top-level list. Instead, if one /// wants the shared `matches`, one should use `up.matches`. matches: Box<[Lrc]>, /// The position in `matches` corresponding to the first metavar in this matcher's sequence of /// token trees. In other words, the first metavar in the first token of `top_elts` corresponds /// to `matches[match_lo]`. match_lo: usize, /// The position in `matches` corresponding to the metavar we are currently trying to match /// against the source token stream. `match_lo <= match_cur <= match_hi`. match_cur: usize, /// Similar to `match_lo` except `match_hi` is the position in `matches` of the _last_ metavar /// in this matcher. match_hi: usize, /// This field is only used if we are matching a repetition. repetition: Option>, /// Specifically used to "unzip" token trees. By "unzip", we mean to unwrap the delimiters from /// a delimited token tree (e.g., something wrapped in `(` `)`) or to get the contents of a doc /// comment... /// /// When matching against matchers with nested delimited submatchers (e.g., `pat ( pat ( .. ) /// pat ) pat`), we need to keep track of the matchers we are descending into. This stack does /// that where the bottom of the stack is the outermost matcher. /// Also, throughout the comments, this "descent" is often referred to as "unzipping"... stack: SmallVec<[MatcherTtFrame<'tt>; 1]>, } // This type is used a lot. Make sure it doesn't unintentionally get bigger. #[cfg(all(target_arch = "x86_64", target_pointer_width = "64"))] rustc_data_structures::static_assert_size!(MatcherPos<'_>, 112); impl<'tt> MatcherPos<'tt> { /// `len` `Vec`s (initially shared and empty) that will store matches of metavars. fn create_matches(len: usize) -> Box<[Lrc]> { if len == 0 { vec![] } else { let empty_matches = Lrc::new(SmallVec::new()); vec![empty_matches; len] } .into_boxed_slice() } /// Generates the top-level matcher position in which the "dot" is before the first token of /// the matcher `ms`. fn new(ms: &'tt [TokenTree]) -> Self { let match_idx_hi = count_names(ms); MatcherPos { // Start with the top level matcher given to us. top_elts: ms, // The "dot" is before the first token of the matcher. idx: 0, // Initialize `matches` to a bunch of empty `Vec`s -- one for each metavar in // `top_elts`. `match_lo` for `top_elts` is 0 and `match_hi` is `match_idx_hi`. // `match_cur` is 0 since we haven't actually matched anything yet. matches: Self::create_matches(match_idx_hi), match_lo: 0, match_cur: 0, match_hi: match_idx_hi, // Haven't descended into any delimiters, so this is empty. stack: smallvec![], // Haven't descended into any sequences, so this is `None`. repetition: None, } } fn repetition(up: Box>, seq: &'tt SequenceRepetition) -> Self { MatcherPos { top_elts: &seq.tts, idx: 0, matches: Self::create_matches(up.matches.len()), match_lo: up.match_cur, match_cur: up.match_cur, match_hi: up.match_cur + seq.num_captures, repetition: Some(MatcherPosRepetition { up, seq }), stack: smallvec![], } } /// Adds `m` as a named match for the `idx`-th metavar. fn push_match(&mut self, idx: usize, m: NamedMatch) { let matches = Lrc::make_mut(&mut self.matches[idx]); matches.push(m); } } #[derive(Clone)] struct MatcherPosRepetition<'tt> { /// The "parent" matcher position. That is, the matcher position just before we enter the /// sequence. up: Box>, /// The sequence itself. seq: &'tt SequenceRepetition, } enum EofItems<'tt> { None, One(Box>), Multiple, } /// Represents the possible results of an attempted parse. crate enum ParseResult { /// Parsed successfully. Success(T), /// Arm failed to match. If the second parameter is `token::Eof`, it indicates an unexpected /// end of macro invocation. Otherwise, it indicates that no rules expected the given token. Failure(Token, &'static str), /// Fatal error (malformed macro?). Abort compilation. Error(rustc_span::Span, String), ErrorReported, } /// A `ParseResult` where the `Success` variant contains a mapping of /// `MacroRulesNormalizedIdent`s to `NamedMatch`es. This represents the mapping /// of metavars to the token trees they bind to. crate type NamedParseResult = ParseResult>; /// Count how many metavars are named in the given matcher `ms`. pub(super) fn count_names(ms: &[TokenTree]) -> usize { ms.iter().fold(0, |count, elt| { count + match elt { TokenTree::Delimited(_, delim) => count_names(delim.inner_tts()), TokenTree::MetaVar(..) => 0, TokenTree::MetaVarDecl(..) => 1, // Panicking here would abort execution because `parse_tree` makes use of this // function. In other words, RHS meta-variable expressions eventually end-up here. // // `0` is still returned to inform that no meta-variable was found. `Meta-variables // != Meta-variable expressions` TokenTree::MetaVarExpr(..) => 0, TokenTree::Sequence(_, seq) => seq.num_captures, TokenTree::Token(..) => 0, } }) } /// `NamedMatch` is a pattern-match result for a single metavar. All /// `MatchedNtNonTt`s in the `NamedMatch` have the same non-terminal type /// (expr, item, etc). /// /// The in-memory structure of a particular `NamedMatch` represents the match /// that occurred when a particular subset of a matcher was applied to a /// particular token tree. /// /// The width of each `MatchedSeq` in the `NamedMatch`, and the identity of /// the `MatchedNtNonTts`s, will depend on the token tree it was applied /// to: each `MatchedSeq` corresponds to a single repetition in the originating /// token tree. The depth of the `NamedMatch` structure will therefore depend /// only on the nesting depth of repetitions in the originating token tree it /// was derived from. /// /// In layman's terms: `NamedMatch` will form a tree representing nested matches of a particular /// meta variable. For example, if we are matching the following macro against the following /// invocation... /// /// ```rust /// macro_rules! foo { /// ($($($x:ident),+);+) => {} /// } /// /// foo!(a, b, c, d; a, b, c, d, e); /// ``` /// /// Then, the tree will have the following shape: /// /// ```rust /// MatchedSeq([ /// MatchedSeq([ /// MatchedNtNonTt(a), /// MatchedNtNonTt(b), /// MatchedNtNonTt(c), /// MatchedNtNonTt(d), /// ]), /// MatchedSeq([ /// MatchedNtNonTt(a), /// MatchedNtNonTt(b), /// MatchedNtNonTt(c), /// MatchedNtNonTt(d), /// MatchedNtNonTt(e), /// ]) /// ]) /// ``` #[derive(Debug, Clone)] crate enum NamedMatch { MatchedSeq(Lrc), // This variant should never hold an `NtTT`. `MatchedNtTt` should be used // for that case. MatchedNtNonTt(Lrc), // `NtTT` is handled without any cloning when transcribing, unlike other // nonterminals. Therefore, an `Lrc` isn't helpful and causes unnecessary // allocations. Hence this separate variant. MatchedNtTt(rustc_ast::tokenstream::TokenTree), } /// Takes a slice of token trees `ms` representing a matcher which successfully matched input /// and an iterator of items that matched input and produces a `NamedParseResult`. fn nameize>( sess: &ParseSess, ms: &[TokenTree], mut res: I, ) -> NamedParseResult { // Recursively descend into each type of matcher (e.g., sequences, delimited, metavars) and make // sure that each metavar has _exactly one_ binding. If a metavar does not have exactly one // binding, then there is an error. If it does, then we insert the binding into the // `NamedParseResult`. fn n_rec>( sess: &ParseSess, m: &TokenTree, res: &mut I, ret_val: &mut FxHashMap, ) -> Result<(), (rustc_span::Span, String)> { match *m { TokenTree::Sequence(_, ref seq) => { for next_m in &seq.tts { n_rec(sess, next_m, res.by_ref(), ret_val)? } } TokenTree::Delimited(_, ref delim) => { for next_m in delim.inner_tts() { n_rec(sess, next_m, res.by_ref(), ret_val)?; } } TokenTree::MetaVarDecl(span, _, None) => { if sess.missing_fragment_specifiers.borrow_mut().remove(&span).is_some() { return Err((span, "missing fragment specifier".to_string())); } } TokenTree::MetaVarDecl(sp, bind_name, _) => match ret_val .entry(MacroRulesNormalizedIdent::new(bind_name)) { Vacant(spot) => { spot.insert(res.next().unwrap()); } Occupied(..) => return Err((sp, format!("duplicated bind name: {}", bind_name))), }, TokenTree::Token(..) => (), TokenTree::MetaVar(..) | TokenTree::MetaVarExpr(..) => unreachable!(), } Ok(()) } let mut ret_val = FxHashMap::default(); for m in ms { match n_rec(sess, m, res.by_ref(), &mut ret_val) { Ok(_) => {} Err((sp, msg)) => return Error(sp, msg), } } Success(ret_val) } /// Performs a token equality check, ignoring syntax context (that is, an unhygienic comparison) fn token_name_eq(t1: &Token, t2: &Token) -> bool { if let (Some((ident1, is_raw1)), Some((ident2, is_raw2))) = (t1.ident(), t2.ident()) { ident1.name == ident2.name && is_raw1 == is_raw2 } else if let (Some(ident1), Some(ident2)) = (t1.lifetime(), t2.lifetime()) { ident1.name == ident2.name } else { t1.kind == t2.kind } } // Note: the item vectors could be created and dropped within `parse_tt`, but to avoid excess // allocations we have a single vector fo each kind that is cleared and reused repeatedly. pub struct TtParser<'tt> { macro_name: Ident, /// The set of current items to be processed. This should be empty by the end of a successful /// execution of `parse_tt_inner`. cur_items: Vec>>, /// The set of newly generated items. These are used to replenish `cur_items` in the function /// `parse_tt`. next_items: Vec>>, /// The set of items that are waiting for the black-box parser. bb_items: Vec>>, } impl<'tt> TtParser<'tt> { pub(super) fn new(macro_name: Ident) -> TtParser<'tt> { TtParser { macro_name, cur_items: vec![], next_items: vec![], bb_items: vec![] } } /// Process the matcher positions of `cur_items` until it is empty. In the process, this will /// produce more items in `next_items` and `bb_items`. /// /// For more info about the how this happens, see the module-level doc comments and the inline /// comments of this function. /// /// # Returns /// /// `Some(result)` if everything is finished, `None` otherwise. Note that matches are kept /// track of through the items generated. fn parse_tt_inner( &mut self, sess: &ParseSess, ms: &[TokenTree], token: &Token, ) -> Option { // Matcher positions that would be valid if the macro invocation was over now. Only // modified if `token == Eof`. let mut eof_items = EofItems::None; while let Some(mut item) = self.cur_items.pop() { // When unzipped trees end, remove them. This corresponds to backtracking out of a // delimited submatcher into which we already descended. When backtracking out again, we // need to advance the "dot" past the delimiters in the outer matcher. while item.idx >= item.top_elts.len() { match item.stack.pop() { Some(MatcherTtFrame { elts, idx }) => { item.top_elts = elts; item.idx = idx + 1; } None => break, } } // Get the current position of the "dot" (`idx`) in `item` and the number of token // trees in the matcher (`len`). let idx = item.idx; let len = item.top_elts.len(); if idx < len { // We are in the middle of a matcher. Compare the matcher's current tt against // `token`. match &item.top_elts[idx] { TokenTree::Sequence(_sp, seq) => { let op = seq.kleene.op; if op == mbe::KleeneOp::ZeroOrMore || op == mbe::KleeneOp::ZeroOrOne { // Allow for the possibility of zero matches of this sequence. let mut new_item = item.clone(); new_item.match_cur += seq.num_captures; new_item.idx += 1; for idx in item.match_cur..item.match_cur + seq.num_captures { new_item.push_match(idx, MatchedSeq(Lrc::new(smallvec![]))); } self.cur_items.push(new_item); } // Allow for the possibility of one or more matches of this sequence. self.cur_items.push(box MatcherPos::repetition(item, &seq)); } &TokenTree::MetaVarDecl(span, _, None) => { // E.g. `$e` instead of `$e:expr`. if sess.missing_fragment_specifiers.borrow_mut().remove(&span).is_some() { return Some(Error(span, "missing fragment specifier".to_string())); } } &TokenTree::MetaVarDecl(_, _, Some(kind)) => { // Built-in nonterminals never start with these tokens, so we can eliminate // them from consideration. // // We use the span of the metavariable declaration to determine any // edition-specific matching behavior for non-terminals. if Parser::nonterminal_may_begin_with(kind, token) { self.bb_items.push(item); } } TokenTree::Delimited(_, delimited) => { // To descend into a delimited submatcher, we push the current matcher onto // a stack and push a new item containing the submatcher onto `cur_items`. // // At the beginning of the loop, if we reach the end of the delimited // submatcher, we pop the stack to backtrack out of the descent. Note that // we use `all_tts` to include the open and close delimiter tokens. let lower_elts = mem::replace(&mut item.top_elts, &delimited.all_tts); let idx = item.idx; item.stack.push(MatcherTtFrame { elts: lower_elts, idx }); item.idx = 0; self.cur_items.push(item); } TokenTree::Token(t) => { // Doc comments cannot appear in a matcher. debug_assert!(!matches!(t, Token { kind: DocComment(..), .. })); // If the token matches, we can just advance the parser. Otherwise, this // match hash failed, there is nothing to do, and hopefully another item in // `cur_items` will match. if token_name_eq(&t, token) { item.idx += 1; self.next_items.push(item); } } // These cannot appear in a matcher. TokenTree::MetaVar(..) | TokenTree::MetaVarExpr(..) => unreachable!(), } } else if let Some(repetition) = &item.repetition { // We are past the end of a repetition. debug_assert!(idx <= len + 1); if idx == len { // Add all matches from the sequence to `up`, and move the "dot" past the // repetition in `up`. This allows for the case where the sequence matching is // finished. let mut new_pos = repetition.up.clone(); for idx in item.match_lo..item.match_hi { let sub = item.matches[idx].clone(); new_pos.push_match(idx, MatchedSeq(sub)); } new_pos.match_cur = item.match_hi; new_pos.idx += 1; self.cur_items.push(new_pos); } if idx == len && repetition.seq.separator.is_some() { if repetition .seq .separator .as_ref() .map_or(false, |sep| token_name_eq(token, sep)) { // The matcher has a separator, and it matches the current token. We can // advance past the separator token. item.idx += 1; self.next_items.push(item); } } else if repetition.seq.kleene.op != mbe::KleeneOp::ZeroOrOne { // We don't need a separator. Move the "dot" back to the beginning of the // matcher and try to match again UNLESS we are only allowed to have _one_ // repetition. item.match_cur = item.match_lo; item.idx = 0; self.cur_items.push(item); } } else { // We are past the end of the matcher, and not in a repetition. Look for end of // input. debug_assert_eq!(idx, len); if *token == token::Eof { eof_items = match eof_items { EofItems::None => EofItems::One(item), EofItems::One(_) | EofItems::Multiple => EofItems::Multiple, } } } } // If we reached the end of input, check that there is EXACTLY ONE possible matcher. // Otherwise, either the parse is ambiguous (which is an error) or there is a syntax error. if *token == token::Eof { Some(match eof_items { EofItems::One(mut eof_item) => { let matches = eof_item.matches.iter_mut().map(|dv| Lrc::make_mut(dv).pop().unwrap()); nameize(sess, ms, matches) } EofItems::Multiple => { Error(token.span, "ambiguity: multiple successful parses".to_string()) } EofItems::None => Failure( Token::new( token::Eof, if token.span.is_dummy() { token.span } else { token.span.shrink_to_hi() }, ), "missing tokens in macro arguments", ), }) } else { None } } /// Use the given slice of token trees (`ms`) as a matcher. Match the token stream from the /// given `parser` against it and return the match. pub(super) fn parse_tt( &mut self, parser: &mut Cow<'_, Parser<'_>>, ms: &'tt [TokenTree], ) -> NamedParseResult { // A queue of possible matcher positions. We initialize it with the matcher position in // which the "dot" is before the first token of the first token tree in `ms`. // `parse_tt_inner` then processes all of these possible matcher positions and produces // possible next positions into `next_items`. After some post-processing, the contents of // `next_items` replenish `cur_items` and we start over again. self.cur_items.clear(); self.cur_items.push(box MatcherPos::new(ms)); loop { self.next_items.clear(); self.bb_items.clear(); // Process `cur_items` until either we have finished the input or we need to get some // parsing from the black-box parser done. if let Some(result) = self.parse_tt_inner(parser.sess, ms, &parser.token) { return result; } // `parse_tt_inner` handled all cur_items, so it's empty. assert!(self.cur_items.is_empty()); // Error messages here could be improved with links to original rules. match (self.next_items.len(), self.bb_items.len()) { (0, 0) => { // There are no possible next positions AND we aren't waiting for the black-box // parser: syntax error. return Failure( parser.token.clone(), "no rules expected this token in macro call", ); } (_, 0) => { // Dump all possible `next_items` into `cur_items` for the next iteration. Then // process the next token. self.cur_items.extend(self.next_items.drain(..)); parser.to_mut().bump(); } (0, 1) => { // We need to call the black-box parser to get some nonterminal. let mut item = self.bb_items.pop().unwrap(); if let TokenTree::MetaVarDecl(span, _, Some(kind)) = item.top_elts[item.idx] { let match_cur = item.match_cur; // We use the span of the metavariable declaration to determine any // edition-specific matching behavior for non-terminals. let nt = match parser.to_mut().parse_nonterminal(kind) { Err(mut err) => { err.span_label( span, format!( "while parsing argument for this `{kind}` macro fragment" ), ) .emit(); return ErrorReported; } Ok(nt) => nt, }; let m = match nt { Nonterminal::NtTT(tt) => MatchedNtTt(tt), _ => MatchedNtNonTt(Lrc::new(nt)), }; item.push_match(match_cur, m); item.idx += 1; item.match_cur += 1; } else { unreachable!() } self.cur_items.push(item); } (_, _) => { // Too many possibilities! return self.ambiguity_error(parser.token.span); } } assert!(!self.cur_items.is_empty()); } } fn ambiguity_error(&self, token_span: rustc_span::Span) -> NamedParseResult { let nts = self .bb_items .iter() .map(|item| match item.top_elts[item.idx] { TokenTree::MetaVarDecl(_, bind, Some(kind)) => { format!("{} ('{}')", kind, bind) } _ => panic!(), }) .collect::>() .join(" or "); Error( token_span, format!( "local ambiguity when calling macro `{}`: multiple parsing options: {}", self.macro_name, match self.next_items.len() { 0 => format!("built-in NTs {}.", nts), 1 => format!("built-in NTs {} or 1 other option.", nts), n => format!("built-in NTs {} or {} other options.", nts, n), } ), ) } }