aboutsummaryrefslogtreecommitdiff
path: root/crates/mbe/src/mbe_expander.rs
diff options
context:
space:
mode:
Diffstat (limited to 'crates/mbe/src/mbe_expander.rs')
-rw-r--r--crates/mbe/src/mbe_expander.rs180
1 files changed, 180 insertions, 0 deletions
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 @@
1//! This module takes a (parsed) definition of `macro_rules` invocation, a
2//! `tt::TokenTree` representing an argument of macro invocation, and produces a
3//! `tt::TokenTree` for the result of the expansion.
4
5mod matcher;
6mod transcriber;
7
8use rustc_hash::FxHashMap;
9use syntax::SmolStr;
10
11use crate::{ExpandError, ExpandResult};
12
13pub(crate) fn expand(rules: &crate::MacroRules, input: &tt::Subtree) -> ExpandResult<tt::Subtree> {
14 expand_rules(&rules.rules, input)
15}
16
17fn expand_rules(rules: &[crate::Rule], input: &tt::Subtree) -> ExpandResult<tt::Subtree> {
18 let mut match_: Option<(matcher::Match, &crate::Rule)> = None;
19 for rule in rules {
20 let new_match = match matcher::match_(&rule.lhs, input) {
21 Ok(m) => m,
22 Err(_e) => {
23 // error in pattern parsing
24 continue;
25 }
26 };
27 if new_match.err.is_none() {
28 // If we find a rule that applies without errors, we're done.
29 // Unconditionally returning the transcription here makes the
30 // `test_repeat_bad_var` test fail.
31 let ExpandResult(res, transcribe_err) =
32 transcriber::transcribe(&rule.rhs, &new_match.bindings);
33 if transcribe_err.is_none() {
34 return ExpandResult::ok(res);
35 }
36 }
37 // Use the rule if we matched more tokens, or had fewer errors
38 if let Some((prev_match, _)) = &match_ {
39 if (new_match.unmatched_tts, new_match.err_count)
40 < (prev_match.unmatched_tts, prev_match.err_count)
41 {
42 match_ = Some((new_match, rule));
43 }
44 } else {
45 match_ = Some((new_match, rule));
46 }
47 }
48 if let Some((match_, rule)) = match_ {
49 // if we got here, there was no match without errors
50 let ExpandResult(result, transcribe_err) =
51 transcriber::transcribe(&rule.rhs, &match_.bindings);
52 ExpandResult(result, match_.err.or(transcribe_err))
53 } else {
54 ExpandResult(tt::Subtree::default(), Some(ExpandError::NoMatchingRule))
55 }
56}
57
58/// The actual algorithm for expansion is not too hard, but is pretty tricky.
59/// `Bindings` structure is the key to understanding what we are doing here.
60///
61/// On the high level, it stores mapping from meta variables to the bits of
62/// syntax it should be substituted with. For example, if `$e:expr` is matched
63/// with `1 + 1` by macro_rules, the `Binding` will store `$e -> 1 + 1`.
64///
65/// The tricky bit is dealing with repetitions (`$()*`). Consider this example:
66///
67/// ```not_rust
68/// macro_rules! foo {
69/// ($($ i:ident $($ e:expr),*);*) => {
70/// $(fn $ i() { $($ e);*; })*
71/// }
72/// }
73/// foo! { foo 1,2,3; bar 4,5,6 }
74/// ```
75///
76/// Here, the `$i` meta variable is matched first with `foo` and then with
77/// `bar`, and `$e` is matched in turn with `1`, `2`, `3`, `4`, `5`, `6`.
78///
79/// To represent such "multi-mappings", we use a recursive structures: we map
80/// variables not to values, but to *lists* of values or other lists (that is,
81/// to the trees).
82///
83/// For the above example, the bindings would store
84///
85/// ```not_rust
86/// i -> [foo, bar]
87/// e -> [[1, 2, 3], [4, 5, 6]]
88/// ```
89///
90/// We construct `Bindings` in the `match_lhs`. The interesting case is
91/// `TokenTree::Repeat`, where we use `push_nested` to create the desired
92/// nesting structure.
93///
94/// The other side of the puzzle is `expand_subtree`, where we use the bindings
95/// to substitute meta variables in the output template. When expanding, we
96/// maintain a `nesting` stack of indices which tells us which occurrence from
97/// the `Bindings` we should take. We push to the stack when we enter a
98/// repetition.
99///
100/// In other words, `Bindings` is a *multi* mapping from `SmolStr` to
101/// `tt::TokenTree`, where the index to select a particular `TokenTree` among
102/// many is not a plain `usize`, but an `&[usize]`.
103#[derive(Debug, Default)]
104struct Bindings {
105 inner: FxHashMap<SmolStr, Binding>,
106}
107
108#[derive(Debug)]
109enum Binding {
110 Fragment(Fragment),
111 Nested(Vec<Binding>),
112 Empty,
113}
114
115#[derive(Debug, Clone)]
116enum Fragment {
117 /// token fragments are just copy-pasted into the output
118 Tokens(tt::TokenTree),
119 /// Ast fragments are inserted with fake delimiters, so as to make things
120 /// like `$i * 2` where `$i = 1 + 1` work as expectd.
121 Ast(tt::TokenTree),
122}
123
124#[cfg(test)]
125mod tests {
126 use syntax::{ast, AstNode};
127
128 use super::*;
129 use crate::ast_to_token_tree;
130
131 #[test]
132 fn test_expand_rule() {
133 assert_err(
134 "($($i:ident);*) => ($i)",
135 "foo!{a}",
136 ExpandError::BindingError(String::from(
137 "expected simple binding, found nested binding `i`",
138 )),
139 );
140
141 // FIXME:
142 // Add an err test case for ($($i:ident)) => ($())
143 }
144
145 fn assert_err(macro_body: &str, invocation: &str, err: ExpandError) {
146 assert_eq!(expand_first(&create_rules(&format_macro(macro_body)), invocation).1, Some(err));
147 }
148
149 fn format_macro(macro_body: &str) -> String {
150 format!(
151 "
152 macro_rules! foo {{
153 {}
154 }}
155",
156 macro_body
157 )
158 }
159
160 fn create_rules(macro_definition: &str) -> crate::MacroRules {
161 let source_file = ast::SourceFile::parse(macro_definition).ok().unwrap();
162 let macro_definition =
163 source_file.syntax().descendants().find_map(ast::MacroCall::cast).unwrap();
164
165 let (definition_tt, _) =
166 ast_to_token_tree(&macro_definition.token_tree().unwrap()).unwrap();
167 crate::MacroRules::parse(&definition_tt).unwrap()
168 }
169
170 fn expand_first(rules: &crate::MacroRules, invocation: &str) -> ExpandResult<tt::Subtree> {
171 let source_file = ast::SourceFile::parse(invocation).ok().unwrap();
172 let macro_invocation =
173 source_file.syntax().descendants().find_map(ast::MacroCall::cast).unwrap();
174
175 let (invocation_tt, _) =
176 ast_to_token_tree(&macro_invocation.token_tree().unwrap()).unwrap();
177
178 expand_rules(&rules.rules, &invocation_tt)
179 }
180}