From 2f45cfc415626cfae5cba89c88a25fb3225486f7 Mon Sep 17 00:00:00 2001 From: Aleksey Kladov Date: Thu, 13 Aug 2020 10:08:11 +0200 Subject: Rename ra_mbe -> mbe --- crates/mbe/src/mbe_expander.rs | 180 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 180 insertions(+) create mode 100644 crates/mbe/src/mbe_expander.rs (limited to 'crates/mbe/src/mbe_expander.rs') diff --git a/crates/mbe/src/mbe_expander.rs b/crates/mbe/src/mbe_expander.rs new file mode 100644 index 000000000..1ad8b9f8a --- /dev/null +++ b/crates/mbe/src/mbe_expander.rs @@ -0,0 +1,180 @@ +//! This module takes a (parsed) definition of `macro_rules` invocation, a +//! `tt::TokenTree` representing an argument of macro invocation, and produces a +//! `tt::TokenTree` for the result of the expansion. + +mod matcher; +mod transcriber; + +use rustc_hash::FxHashMap; +use syntax::SmolStr; + +use crate::{ExpandError, ExpandResult}; + +pub(crate) fn expand(rules: &crate::MacroRules, input: &tt::Subtree) -> ExpandResult { + expand_rules(&rules.rules, input) +} + +fn expand_rules(rules: &[crate::Rule], input: &tt::Subtree) -> ExpandResult { + let mut match_: Option<(matcher::Match, &crate::Rule)> = None; + for rule in rules { + let new_match = match matcher::match_(&rule.lhs, input) { + Ok(m) => m, + Err(_e) => { + // error in pattern parsing + continue; + } + }; + if new_match.err.is_none() { + // If we find a rule that applies without errors, we're done. + // Unconditionally returning the transcription here makes the + // `test_repeat_bad_var` test fail. + let ExpandResult(res, transcribe_err) = + transcriber::transcribe(&rule.rhs, &new_match.bindings); + if transcribe_err.is_none() { + return ExpandResult::ok(res); + } + } + // Use the rule if we matched more tokens, or had fewer errors + if let Some((prev_match, _)) = &match_ { + if (new_match.unmatched_tts, new_match.err_count) + < (prev_match.unmatched_tts, prev_match.err_count) + { + match_ = Some((new_match, rule)); + } + } else { + match_ = Some((new_match, rule)); + } + } + if let Some((match_, rule)) = match_ { + // if we got here, there was no match without errors + let ExpandResult(result, transcribe_err) = + transcriber::transcribe(&rule.rhs, &match_.bindings); + ExpandResult(result, match_.err.or(transcribe_err)) + } else { + ExpandResult(tt::Subtree::default(), Some(ExpandError::NoMatchingRule)) + } +} + +/// The actual algorithm for expansion is not too hard, but is pretty tricky. +/// `Bindings` structure is the key to understanding what we are doing here. +/// +/// On the high level, it stores mapping from meta variables to the bits of +/// syntax it should be substituted with. For example, if `$e:expr` is matched +/// with `1 + 1` by macro_rules, the `Binding` will store `$e -> 1 + 1`. +/// +/// The tricky bit is dealing with repetitions (`$()*`). Consider this example: +/// +/// ```not_rust +/// macro_rules! foo { +/// ($($ i:ident $($ e:expr),*);*) => { +/// $(fn $ i() { $($ e);*; })* +/// } +/// } +/// foo! { foo 1,2,3; bar 4,5,6 } +/// ``` +/// +/// Here, the `$i` meta variable is matched first with `foo` and then with +/// `bar`, and `$e` is matched in turn with `1`, `2`, `3`, `4`, `5`, `6`. +/// +/// To represent such "multi-mappings", we use a recursive structures: we map +/// variables not to values, but to *lists* of values or other lists (that is, +/// to the trees). +/// +/// For the above example, the bindings would store +/// +/// ```not_rust +/// i -> [foo, bar] +/// e -> [[1, 2, 3], [4, 5, 6]] +/// ``` +/// +/// We construct `Bindings` in the `match_lhs`. The interesting case is +/// `TokenTree::Repeat`, where we use `push_nested` to create the desired +/// nesting structure. +/// +/// The other side of the puzzle is `expand_subtree`, where we use the bindings +/// to substitute meta variables in the output template. When expanding, we +/// maintain a `nesting` stack of indices which tells us which occurrence from +/// the `Bindings` we should take. We push to the stack when we enter a +/// repetition. +/// +/// In other words, `Bindings` is a *multi* mapping from `SmolStr` to +/// `tt::TokenTree`, where the index to select a particular `TokenTree` among +/// many is not a plain `usize`, but an `&[usize]`. +#[derive(Debug, Default)] +struct Bindings { + inner: FxHashMap, +} + +#[derive(Debug)] +enum Binding { + Fragment(Fragment), + Nested(Vec), + Empty, +} + +#[derive(Debug, Clone)] +enum Fragment { + /// token fragments are just copy-pasted into the output + Tokens(tt::TokenTree), + /// Ast fragments are inserted with fake delimiters, so as to make things + /// like `$i * 2` where `$i = 1 + 1` work as expectd. + Ast(tt::TokenTree), +} + +#[cfg(test)] +mod tests { + use syntax::{ast, AstNode}; + + use super::*; + use crate::ast_to_token_tree; + + #[test] + fn test_expand_rule() { + assert_err( + "($($i:ident);*) => ($i)", + "foo!{a}", + ExpandError::BindingError(String::from( + "expected simple binding, found nested binding `i`", + )), + ); + + // FIXME: + // Add an err test case for ($($i:ident)) => ($()) + } + + fn assert_err(macro_body: &str, invocation: &str, err: ExpandError) { + assert_eq!(expand_first(&create_rules(&format_macro(macro_body)), invocation).1, Some(err)); + } + + fn format_macro(macro_body: &str) -> String { + format!( + " + macro_rules! foo {{ + {} + }} +", + macro_body + ) + } + + fn create_rules(macro_definition: &str) -> crate::MacroRules { + let source_file = ast::SourceFile::parse(macro_definition).ok().unwrap(); + let macro_definition = + source_file.syntax().descendants().find_map(ast::MacroCall::cast).unwrap(); + + let (definition_tt, _) = + ast_to_token_tree(¯o_definition.token_tree().unwrap()).unwrap(); + crate::MacroRules::parse(&definition_tt).unwrap() + } + + fn expand_first(rules: &crate::MacroRules, invocation: &str) -> ExpandResult { + let source_file = ast::SourceFile::parse(invocation).ok().unwrap(); + let macro_invocation = + source_file.syntax().descendants().find_map(ast::MacroCall::cast).unwrap(); + + let (invocation_tt, _) = + ast_to_token_tree(¯o_invocation.token_tree().unwrap()).unwrap(); + + expand_rules(&rules.rules, &invocation_tt) + } +} -- cgit v1.2.3