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