aboutsummaryrefslogtreecommitdiff
path: root/crates/mbe
diff options
context:
space:
mode:
Diffstat (limited to 'crates/mbe')
-rw-r--r--crates/mbe/Cargo.toml4
-rw-r--r--crates/mbe/src/benchmark.rs225
-rw-r--r--crates/mbe/src/expander.rs (renamed from crates/mbe/src/mbe_expander.rs)34
-rw-r--r--crates/mbe/src/expander/matcher.rs737
-rw-r--r--crates/mbe/src/expander/transcriber.rs (renamed from crates/mbe/src/mbe_expander/transcriber.rs)37
-rw-r--r--crates/mbe/src/lib.rs130
-rw-r--r--crates/mbe/src/mbe_expander/matcher.rs502
-rw-r--r--crates/mbe/src/parser.rs130
-rw-r--r--crates/mbe/src/syntax_bridge.rs73
-rw-r--r--crates/mbe/src/tests.rs296
-rw-r--r--crates/mbe/src/tt_iter.rs77
11 files changed, 1530 insertions, 715 deletions
diff --git a/crates/mbe/Cargo.toml b/crates/mbe/Cargo.toml
index af80e2be3..bb2656a80 100644
--- a/crates/mbe/Cargo.toml
+++ b/crates/mbe/Cargo.toml
@@ -17,6 +17,8 @@ log = "0.4.8"
17syntax = { path = "../syntax", version = "0.0.0" } 17syntax = { path = "../syntax", version = "0.0.0" }
18parser = { path = "../parser", version = "0.0.0" } 18parser = { path = "../parser", version = "0.0.0" }
19tt = { path = "../tt", version = "0.0.0" } 19tt = { path = "../tt", version = "0.0.0" }
20test_utils = { path = "../test_utils", version = "0.0.0" }
21stdx = { path = "../stdx", version = "0.0.0" }
20 22
21[dev-dependencies] 23[dev-dependencies]
22test_utils = { path = "../test_utils" } 24profile = { path = "../profile" }
diff --git a/crates/mbe/src/benchmark.rs b/crates/mbe/src/benchmark.rs
new file mode 100644
index 000000000..503ad1355
--- /dev/null
+++ b/crates/mbe/src/benchmark.rs
@@ -0,0 +1,225 @@
1//! This module add real world mbe example for benchmark tests
2
3use rustc_hash::FxHashMap;
4use syntax::{
5 ast::{self, NameOwner},
6 AstNode, SmolStr,
7};
8use test_utils::{bench, bench_fixture, skip_slow_tests};
9
10use crate::{
11 ast_to_token_tree,
12 parser::{Op, RepeatKind, Separator},
13 MacroRules,
14};
15
16#[test]
17fn benchmark_parse_macro_rules() {
18 if skip_slow_tests() {
19 return;
20 }
21 let rules = macro_rules_fixtures_tt();
22 let hash: usize = {
23 let _pt = bench("mbe parse macro rules");
24 rules.values().map(|it| MacroRules::parse(it).unwrap().rules.len()).sum()
25 };
26 assert_eq!(hash, 1144);
27}
28
29#[test]
30fn benchmark_expand_macro_rules() {
31 if skip_slow_tests() {
32 return;
33 }
34 let rules = macro_rules_fixtures();
35 let invocations = invocation_fixtures(&rules);
36
37 let hash: usize = {
38 let _pt = bench("mbe expand macro rules");
39 invocations
40 .into_iter()
41 .map(|(id, tt)| {
42 let res = rules[&id].expand(&tt);
43 assert!(res.err.is_none());
44 res.value.token_trees.len()
45 })
46 .sum()
47 };
48 assert_eq!(hash, 69413);
49}
50
51fn macro_rules_fixtures() -> FxHashMap<String, MacroRules> {
52 macro_rules_fixtures_tt()
53 .into_iter()
54 .map(|(id, tt)| (id, MacroRules::parse(&tt).unwrap()))
55 .collect()
56}
57
58fn macro_rules_fixtures_tt() -> FxHashMap<String, tt::Subtree> {
59 let fixture = bench_fixture::numerous_macro_rules();
60 let source_file = ast::SourceFile::parse(&fixture).ok().unwrap();
61
62 source_file
63 .syntax()
64 .descendants()
65 .filter_map(ast::MacroRules::cast)
66 .map(|rule| {
67 let id = rule.name().unwrap().to_string();
68 let (def_tt, _) = ast_to_token_tree(&rule.token_tree().unwrap()).unwrap();
69 (id, def_tt)
70 })
71 .collect()
72}
73
74/// Generate random invocation fixtures from rules
75fn invocation_fixtures(rules: &FxHashMap<String, MacroRules>) -> Vec<(String, tt::Subtree)> {
76 let mut seed = 123456789;
77 let mut res = Vec::new();
78
79 for (name, it) in rules {
80 for rule in &it.rules {
81 // Generate twice
82 for _ in 0..2 {
83 // The input are generated by filling the `Op` randomly.
84 // However, there are some cases generated are ambiguous for expanding, for example:
85 // ```rust
86 // macro_rules! m {
87 // ($($t:ident),* as $ty:ident) => {}
88 // }
89 // m!(as u32); // error: local ambiguity: multiple parsing options: built-in NTs ident ('t') or 1 other option.
90 // ```
91 //
92 // So we just skip any error cases and try again
93 let mut try_cnt = 0;
94 loop {
95 let mut subtree = tt::Subtree::default();
96 for op in rule.lhs.iter() {
97 collect_from_op(op, &mut subtree, &mut seed);
98 }
99 if it.expand(&subtree).err.is_none() {
100 res.push((name.clone(), subtree));
101 break;
102 }
103 try_cnt += 1;
104 if try_cnt > 100 {
105 panic!("invocaton fixture {} cannot be generated.\n", name);
106 }
107 }
108 }
109 }
110 }
111 return res;
112
113 fn collect_from_op(op: &Op, parent: &mut tt::Subtree, seed: &mut usize) {
114 return match op {
115 Op::Var { kind, .. } => match kind.as_ref().map(|it| it.as_str()) {
116 Some("ident") => parent.token_trees.push(make_ident("foo")),
117 Some("ty") => parent.token_trees.push(make_ident("Foo")),
118 Some("tt") => parent.token_trees.push(make_ident("foo")),
119 Some("vis") => parent.token_trees.push(make_ident("pub")),
120 Some("pat") => parent.token_trees.push(make_ident("foo")),
121 Some("path") => parent.token_trees.push(make_ident("foo")),
122 Some("literal") => parent.token_trees.push(make_literal("1")),
123 Some("expr") => parent.token_trees.push(make_ident("foo").into()),
124 Some("lifetime") => {
125 parent.token_trees.push(make_punct('\''));
126 parent.token_trees.push(make_ident("a"));
127 }
128 Some("block") => {
129 parent.token_trees.push(make_subtree(tt::DelimiterKind::Brace, None))
130 }
131 Some("item") => {
132 parent.token_trees.push(make_ident("fn"));
133 parent.token_trees.push(make_ident("foo"));
134 parent.token_trees.push(make_subtree(tt::DelimiterKind::Parenthesis, None));
135 parent.token_trees.push(make_subtree(tt::DelimiterKind::Brace, None));
136 }
137 Some("meta") => {
138 parent.token_trees.push(make_ident("foo"));
139 parent.token_trees.push(make_subtree(tt::DelimiterKind::Parenthesis, None));
140 }
141
142 None => (),
143 Some(kind) => panic!("Unhandled kind {}", kind),
144 },
145 Op::Leaf(leaf) => parent.token_trees.push(leaf.clone().into()),
146 Op::Repeat { tokens, kind, separator } => {
147 let max = 10;
148 let cnt = match kind {
149 RepeatKind::ZeroOrMore => rand(seed) % max,
150 RepeatKind::OneOrMore => 1 + rand(seed) % max,
151 RepeatKind::ZeroOrOne => rand(seed) % 2,
152 };
153 for i in 0..cnt {
154 for it in tokens.iter() {
155 collect_from_op(it, parent, seed);
156 }
157 if i + 1 != cnt {
158 if let Some(sep) = separator {
159 match sep {
160 Separator::Literal(it) => parent
161 .token_trees
162 .push(tt::Leaf::Literal(it.clone().into()).into()),
163 Separator::Ident(it) => parent
164 .token_trees
165 .push(tt::Leaf::Ident(it.clone().into()).into()),
166 Separator::Puncts(puncts) => {
167 for it in puncts {
168 parent
169 .token_trees
170 .push(tt::Leaf::Punct(it.clone().into()).into())
171 }
172 }
173 };
174 }
175 }
176 }
177 }
178 Op::Subtree { tokens, delimiter } => {
179 let mut subtree =
180 tt::Subtree { delimiter: delimiter.clone(), token_trees: Vec::new() };
181 tokens.iter().for_each(|it| {
182 collect_from_op(it, &mut subtree, seed);
183 });
184 parent.token_trees.push(subtree.into());
185 }
186 };
187
188 // Simple linear congruential generator for determistic result
189 fn rand(seed: &mut usize) -> usize {
190 let a = 1664525;
191 let c = 1013904223;
192 *seed = usize::wrapping_add(usize::wrapping_mul(*seed, a), c);
193 return *seed;
194 }
195 fn make_ident(ident: &str) -> tt::TokenTree {
196 tt::Leaf::Ident(tt::Ident { id: tt::TokenId::unspecified(), text: SmolStr::new(ident) })
197 .into()
198 }
199 fn make_punct(char: char) -> tt::TokenTree {
200 tt::Leaf::Punct(tt::Punct {
201 id: tt::TokenId::unspecified(),
202 char,
203 spacing: tt::Spacing::Alone,
204 })
205 .into()
206 }
207 fn make_literal(lit: &str) -> tt::TokenTree {
208 tt::Leaf::Literal(tt::Literal {
209 id: tt::TokenId::unspecified(),
210 text: SmolStr::new(lit),
211 })
212 .into()
213 }
214 fn make_subtree(
215 kind: tt::DelimiterKind,
216 token_trees: Option<Vec<tt::TokenTree>>,
217 ) -> tt::TokenTree {
218 tt::Subtree {
219 delimiter: Some(tt::Delimiter { id: tt::TokenId::unspecified(), kind }),
220 token_trees: token_trees.unwrap_or_default(),
221 }
222 .into()
223 }
224 }
225}
diff --git a/crates/mbe/src/mbe_expander.rs b/crates/mbe/src/expander.rs
index a80b73db4..2efff8f52 100644
--- a/crates/mbe/src/mbe_expander.rs
+++ b/crates/mbe/src/expander.rs
@@ -5,25 +5,19 @@
5mod matcher; 5mod matcher;
6mod transcriber; 6mod transcriber;
7 7
8use rustc_hash::FxHashMap; 8use smallvec::SmallVec;
9use syntax::SmolStr; 9use syntax::SmolStr;
10 10
11use crate::{ExpandError, ExpandResult}; 11use crate::{ExpandError, ExpandResult};
12 12
13pub(crate) fn expand(rules: &crate::MacroRules, input: &tt::Subtree) -> ExpandResult<tt::Subtree> { 13pub(crate) fn expand_rules(
14 expand_rules(&rules.rules, input) 14 rules: &[crate::Rule],
15} 15 input: &tt::Subtree,
16 16) -> ExpandResult<tt::Subtree> {
17fn expand_rules(rules: &[crate::Rule], input: &tt::Subtree) -> ExpandResult<tt::Subtree> {
18 let mut match_: Option<(matcher::Match, &crate::Rule)> = None; 17 let mut match_: Option<(matcher::Match, &crate::Rule)> = None;
19 for rule in rules { 18 for rule in rules {
20 let new_match = match matcher::match_(&rule.lhs, input) { 19 let new_match = matcher::match_(&rule.lhs, input);
21 Ok(m) => m, 20
22 Err(_e) => {
23 // error in pattern parsing
24 continue;
25 }
26 };
27 if new_match.err.is_none() { 21 if new_match.err.is_none() {
28 // If we find a rule that applies without errors, we're done. 22 // If we find a rule that applies without errors, we're done.
29 // Unconditionally returning the transcription here makes the 23 // Unconditionally returning the transcription here makes the
@@ -34,10 +28,10 @@ fn expand_rules(rules: &[crate::Rule], input: &tt::Subtree) -> ExpandResult<tt::
34 return ExpandResult::ok(value); 28 return ExpandResult::ok(value);
35 } 29 }
36 } 30 }
37 // Use the rule if we matched more tokens, or had fewer errors 31 // Use the rule if we matched more tokens, or bound variables count
38 if let Some((prev_match, _)) = &match_ { 32 if let Some((prev_match, _)) = &match_ {
39 if (new_match.unmatched_tts, new_match.err_count) 33 if (new_match.unmatched_tts, -(new_match.bound_count as i32))
40 < (prev_match.unmatched_tts, prev_match.err_count) 34 < (prev_match.unmatched_tts, -(prev_match.bound_count as i32))
41 { 35 {
42 match_ = Some((new_match, rule)); 36 match_ = Some((new_match, rule));
43 } 37 }
@@ -100,19 +94,19 @@ fn expand_rules(rules: &[crate::Rule], input: &tt::Subtree) -> ExpandResult<tt::
100/// In other words, `Bindings` is a *multi* mapping from `SmolStr` to 94/// In other words, `Bindings` is a *multi* mapping from `SmolStr` to
101/// `tt::TokenTree`, where the index to select a particular `TokenTree` among 95/// `tt::TokenTree`, where the index to select a particular `TokenTree` among
102/// many is not a plain `usize`, but an `&[usize]`. 96/// many is not a plain `usize`, but an `&[usize]`.
103#[derive(Debug, Default)] 97#[derive(Debug, Default, Clone, PartialEq, Eq)]
104struct Bindings { 98struct Bindings {
105 inner: FxHashMap<SmolStr, Binding>, 99 inner: SmallVec<[(SmolStr, Binding); 4]>,
106} 100}
107 101
108#[derive(Debug)] 102#[derive(Debug, Clone, PartialEq, Eq)]
109enum Binding { 103enum Binding {
110 Fragment(Fragment), 104 Fragment(Fragment),
111 Nested(Vec<Binding>), 105 Nested(Vec<Binding>),
112 Empty, 106 Empty,
113} 107}
114 108
115#[derive(Debug, Clone)] 109#[derive(Debug, Clone, PartialEq, Eq)]
116enum Fragment { 110enum Fragment {
117 /// token fragments are just copy-pasted into the output 111 /// token fragments are just copy-pasted into the output
118 Tokens(tt::TokenTree), 112 Tokens(tt::TokenTree),
diff --git a/crates/mbe/src/expander/matcher.rs b/crates/mbe/src/expander/matcher.rs
new file mode 100644
index 000000000..9d3d28055
--- /dev/null
+++ b/crates/mbe/src/expander/matcher.rs
@@ -0,0 +1,737 @@
1//! An NFA-based parser, which is porting from rustc mbe parsing code
2//!
3//! See https://github.com/rust-lang/rust/blob/70b18bc2cbac4712020019f5bf57c00905373205/compiler/rustc_expand/src/mbe/macro_parser.rs
4//! Here is a quick intro to how the parser works, copied from rustc:
5//!
6//! A 'position' is a dot in the middle of a matcher, usually represented as a
7//! dot. For example `· a $( a )* a b` is a position, as is `a $( · a )* a b`.
8//!
9//! The parser walks through the input a character at a time, maintaining a list
10//! of threads consistent with the current position in the input string: `cur_items`.
11//!
12//! As it processes them, it fills up `eof_items` with threads that would be valid if
13//! the macro invocation is now over, `bb_items` with threads that are waiting on
14//! a Rust non-terminal like `$e:expr`, and `next_items` with threads that are waiting
15//! on a particular token. Most of the logic concerns moving the · through the
16//! repetitions indicated by Kleene stars. The rules for moving the · without
17//! consuming any input are called epsilon transitions. It only advances or calls
18//! out to the real Rust parser when no `cur_items` threads remain.
19//!
20//! Example:
21//!
22//! ```text, ignore
23//! Start parsing a a a a b against [· a $( a )* a b].
24//!
25//! Remaining input: a a a a b
26//! next: [· a $( a )* a b]
27//!
28//! - - - Advance over an a. - - -
29//!
30//! Remaining input: a a a b
31//! cur: [a · $( a )* a b]
32//! Descend/Skip (first item).
33//! next: [a $( · a )* a b] [a $( a )* · a b].
34//!
35//! - - - Advance over an a. - - -
36//!
37//! Remaining input: a a b
38//! cur: [a $( a · )* a b] [a $( a )* a · b]
39//! Follow epsilon transition: Finish/Repeat (first item)
40//! next: [a $( a )* · a b] [a $( · a )* a b] [a $( a )* a · b]
41//!
42//! - - - Advance over an a. - - - (this looks exactly like the last step)
43//!
44//! Remaining input: a b
45//! cur: [a $( a · )* a b] [a $( a )* a · b]
46//! Follow epsilon transition: Finish/Repeat (first item)
47//! next: [a $( a )* · a b] [a $( · a )* a b] [a $( a )* a · b]
48//!
49//! - - - Advance over an a. - - - (this looks exactly like the last step)
50//!
51//! Remaining input: b
52//! cur: [a $( a · )* a b] [a $( a )* a · b]
53//! Follow epsilon transition: Finish/Repeat (first item)
54//! next: [a $( a )* · a b] [a $( · a )* a b] [a $( a )* a · b]
55//!
56//! - - - Advance over a b. - - -
57//!
58//! Remaining input: ''
59//! eof: [a $( a )* a b ·]
60//! ```
61
62use crate::{
63 expander::{Binding, Bindings, Fragment},
64 parser::{Op, OpDelimited, OpDelimitedIter, RepeatKind, Separator},
65 tt_iter::TtIter,
66 ExpandError, MetaTemplate,
67};
68
69use super::ExpandResult;
70use parser::FragmentKind::*;
71use smallvec::{smallvec, SmallVec};
72use syntax::SmolStr;
73
74impl Bindings {
75 fn push_optional(&mut self, name: &SmolStr) {
76 // FIXME: Do we have a better way to represent an empty token ?
77 // Insert an empty subtree for empty token
78 let tt = tt::Subtree::default().into();
79 self.inner.push((name.clone(), Binding::Fragment(Fragment::Tokens(tt))));
80 }
81
82 fn push_empty(&mut self, name: &SmolStr) {
83 self.inner.push((name.clone(), Binding::Empty));
84 }
85
86 fn push_nested(&mut self, idx: usize, nested: Bindings) -> Result<(), ExpandError> {
87 for (key, value) in nested.inner {
88 if self.get_mut(&key).is_none() {
89 self.inner.push((key.clone(), Binding::Nested(Vec::new())));
90 }
91 match self.get_mut(&key) {
92 Some(Binding::Nested(it)) => {
93 // insert empty nested bindings before this one
94 while it.len() < idx {
95 it.push(Binding::Nested(vec![]));
96 }
97 it.push(value);
98 }
99 _ => {
100 return Err(ExpandError::BindingError(format!(
101 "could not find binding `{}`",
102 key
103 )));
104 }
105 }
106 }
107 Ok(())
108 }
109
110 fn get_mut(&mut self, name: &str) -> Option<&mut Binding> {
111 self.inner.iter_mut().find_map(|(n, b)| if n == name { Some(b) } else { None })
112 }
113
114 fn bindings(&self) -> impl Iterator<Item = &Binding> {
115 self.inner.iter().map(|(_, b)| b)
116 }
117}
118
119macro_rules! err {
120 () => {
121 ExpandError::BindingError(format!(""))
122 };
123 ($($tt:tt)*) => {
124 ExpandError::BindingError(format!($($tt)*))
125 };
126}
127
128#[derive(Clone, Debug, Default, PartialEq, Eq)]
129pub(super) struct Match {
130 pub(super) bindings: Bindings,
131 /// We currently just keep the first error and count the rest to compare matches.
132 pub(super) err: Option<ExpandError>,
133 pub(super) err_count: usize,
134 /// How many top-level token trees were left to match.
135 pub(super) unmatched_tts: usize,
136 /// The number of bound variables
137 pub(super) bound_count: usize,
138}
139
140impl Match {
141 fn add_err(&mut self, err: ExpandError) {
142 let prev_err = self.err.take();
143 self.err = prev_err.or(Some(err));
144 self.err_count += 1;
145 }
146}
147
148/// Matching errors are added to the `Match`.
149pub(super) fn match_(pattern: &MetaTemplate, input: &tt::Subtree) -> Match {
150 let mut res = match_loop(pattern, &input);
151 res.bound_count = count(res.bindings.bindings());
152 return res;
153
154 fn count<'a>(bindings: impl Iterator<Item = &'a Binding>) -> usize {
155 bindings
156 .map(|it| match it {
157 Binding::Fragment(_) => 1,
158 Binding::Empty => 1,
159 Binding::Nested(it) => count(it.iter()),
160 })
161 .sum()
162 }
163}
164
165#[derive(Debug, Clone)]
166struct MatchState<'t> {
167 /// The position of the "dot" in this matcher
168 dot: OpDelimitedIter<'t>,
169
170 /// Token subtree stack
171 /// When matching against matchers with nested delimited submatchers (e.g., `pat ( pat ( .. )
172 /// pat ) pat`), we need to keep track of the matchers we are descending into. This stack does
173 /// that where the bottom of the stack is the outermost matcher.
174 stack: SmallVec<[OpDelimitedIter<'t>; 4]>,
175
176 /// The "parent" matcher position if we are in a repetition. That is, the matcher position just
177 /// before we enter the repetition.
178 up: Option<Box<MatchState<'t>>>,
179
180 /// The separator if we are in a repetition.
181 sep: Option<Separator>,
182
183 /// The KleeneOp of this sequence if we are in a repetition.
184 sep_kind: Option<RepeatKind>,
185
186 /// Number of tokens of seperator parsed
187 sep_parsed: Option<usize>,
188
189 /// Matched meta variables bindings
190 bindings: SmallVec<[Bindings; 4]>,
191
192 /// Cached result of meta variable parsing
193 meta_result: Option<(TtIter<'t>, ExpandResult<Option<Fragment>>)>,
194
195 /// Is error occuried in this state, will `poised` to "parent"
196 is_error: bool,
197}
198
199/// Process the matcher positions of `cur_items` until it is empty. In the process, this will
200/// produce more items in `next_items`, `eof_items`, and `bb_items`.
201///
202/// For more info about the how this happens, see the module-level doc comments and the inline
203/// comments of this function.
204///
205/// # Parameters
206///
207/// - `src`: the current token of the parser.
208/// - `stack`: the "parent" frames of the token tree
209/// - `res`: the match result to store errors
210/// - `cur_items`: the set of current items to be processed. This should be empty by the end of a
211/// successful execution of this function.
212/// - `next_items`: the set of newly generated items. These are used to replenish `cur_items` in
213/// the function `parse`.
214/// - `eof_items`: the set of items that would be valid if this was the EOF.
215/// - `bb_items`: the set of items that are waiting for the black-box parser.
216/// - `error_items`: the set of items in errors, used for error-resilient parsing
217fn match_loop_inner<'t>(
218 src: TtIter<'t>,
219 stack: &[TtIter<'t>],
220 res: &mut Match,
221 cur_items: &mut SmallVec<[MatchState<'t>; 1]>,
222 bb_items: &mut SmallVec<[MatchState<'t>; 1]>,
223 next_items: &mut Vec<MatchState<'t>>,
224 eof_items: &mut SmallVec<[MatchState<'t>; 1]>,
225 error_items: &mut SmallVec<[MatchState<'t>; 1]>,
226) {
227 macro_rules! try_push {
228 ($items: expr, $it:expr) => {
229 if $it.is_error {
230 error_items.push($it);
231 } else {
232 $items.push($it);
233 }
234 };
235 }
236
237 while let Some(mut item) = cur_items.pop() {
238 while item.dot.is_eof() {
239 match item.stack.pop() {
240 Some(frame) => {
241 item.dot = frame;
242 item.dot.next();
243 }
244 None => break,
245 }
246 }
247 let op = match item.dot.peek() {
248 None => {
249 // We are at or past the end of the matcher of `item`.
250 if item.up.is_some() {
251 if item.sep_parsed.is_none() {
252 // Get the `up` matcher
253 let mut new_pos = *item.up.clone().unwrap();
254 // Add matches from this repetition to the `matches` of `up`
255 if let Some(bindings) = new_pos.bindings.last_mut() {
256 for (i, b) in item.bindings.iter_mut().enumerate() {
257 bindings.push_nested(i, b.clone()).unwrap();
258 }
259 }
260 // Move the "dot" past the repetition in `up`
261 new_pos.dot.next();
262 new_pos.is_error = new_pos.is_error || item.is_error;
263 cur_items.push(new_pos);
264 }
265
266 // Check if we need a separator.
267 // We check the separator one by one
268 let sep_idx = *item.sep_parsed.as_ref().unwrap_or(&0);
269 let sep_len = item.sep.as_ref().map_or(0, Separator::tt_count);
270 if item.sep.is_some() && sep_idx != sep_len {
271 let sep = item.sep.as_ref().unwrap();
272 if src.clone().expect_separator(&sep, sep_idx) {
273 item.dot.next();
274 item.sep_parsed = Some(sep_idx + 1);
275 try_push!(next_items, item);
276 }
277 }
278 // We don't need a separator. Move the "dot" back to the beginning of the matcher
279 // and try to match again UNLESS we are only allowed to have _one_ repetition.
280 else if item.sep_kind != Some(RepeatKind::ZeroOrOne) {
281 item.dot = item.dot.reset();
282 item.sep_parsed = None;
283 item.bindings.push(Bindings::default());
284 cur_items.push(item);
285 }
286 } else {
287 // If we are not in a repetition, then being at the end of a matcher means that we have
288 // reached the potential end of the input.
289 try_push!(eof_items, item);
290 }
291 continue;
292 }
293 Some(it) => it,
294 };
295
296 // We are in the middle of a matcher.
297 match op {
298 OpDelimited::Op(Op::Repeat { tokens, kind, separator }) => {
299 if matches!(kind, RepeatKind::ZeroOrMore | RepeatKind::ZeroOrOne) {
300 let mut new_item = item.clone();
301 new_item.dot.next();
302 let mut vars = Vec::new();
303 let bindings = new_item.bindings.last_mut().unwrap();
304 collect_vars(&mut vars, tokens);
305 for var in vars {
306 bindings.push_empty(&var);
307 }
308 cur_items.push(new_item);
309 }
310 cur_items.push(MatchState {
311 dot: tokens.iter_delimited(None),
312 stack: Default::default(),
313 up: Some(Box::new(item)),
314 sep: separator.clone(),
315 sep_kind: Some(*kind),
316 sep_parsed: None,
317 bindings: smallvec![Bindings::default()],
318 meta_result: None,
319 is_error: false,
320 })
321 }
322 OpDelimited::Op(Op::Subtree { tokens, delimiter }) => {
323 if let Ok(subtree) = src.clone().expect_subtree() {
324 if subtree.delimiter_kind() == delimiter.map(|it| it.kind) {
325 item.stack.push(item.dot);
326 item.dot = tokens.iter_delimited(delimiter.as_ref());
327 cur_items.push(item);
328 }
329 }
330 }
331 OpDelimited::Op(Op::Var { kind, name, .. }) => {
332 if let Some(kind) = kind {
333 let mut fork = src.clone();
334 let match_res = match_meta_var(kind.as_str(), &mut fork);
335 match match_res.err {
336 None => {
337 // Some meta variables are optional (e.g. vis)
338 if match_res.value.is_some() {
339 item.meta_result = Some((fork, match_res));
340 try_push!(bb_items, item);
341 } else {
342 item.bindings.last_mut().unwrap().push_optional(name);
343 item.dot.next();
344 cur_items.push(item);
345 }
346 }
347 Some(err) => {
348 res.add_err(err);
349 match match_res.value {
350 Some(fragment) => {
351 item.bindings
352 .last_mut()
353 .unwrap()
354 .inner
355 .push((name.clone(), Binding::Fragment(fragment)));
356 }
357 _ => {}
358 }
359 item.is_error = true;
360 error_items.push(item);
361 }
362 }
363 }
364 }
365 OpDelimited::Op(Op::Leaf(leaf)) => {
366 if let Err(err) = match_leaf(&leaf, &mut src.clone()) {
367 res.add_err(err);
368 item.is_error = true;
369 } else {
370 item.dot.next();
371 }
372 try_push!(next_items, item);
373 }
374 OpDelimited::Open => {
375 if matches!(src.clone().next(), Some(tt::TokenTree::Subtree(..))) {
376 item.dot.next();
377 try_push!(next_items, item);
378 }
379 }
380 OpDelimited::Close => {
381 let is_delim_closed = src.peek_n(0).is_none() && !stack.is_empty();
382 if is_delim_closed {
383 item.dot.next();
384 try_push!(next_items, item);
385 }
386 }
387 }
388 }
389}
390
391fn match_loop(pattern: &MetaTemplate, src: &tt::Subtree) -> Match {
392 let mut src = TtIter::new(src);
393 let mut stack: SmallVec<[TtIter; 1]> = SmallVec::new();
394 let mut res = Match::default();
395 let mut error_reover_item = None;
396
397 let mut cur_items = smallvec![MatchState {
398 dot: pattern.iter_delimited(None),
399 stack: Default::default(),
400 up: None,
401 sep: None,
402 sep_kind: None,
403 sep_parsed: None,
404 bindings: smallvec![Bindings::default()],
405 is_error: false,
406 meta_result: None,
407 }];
408
409 let mut next_items = vec![];
410
411 loop {
412 let mut bb_items = SmallVec::new();
413 let mut eof_items = SmallVec::new();
414 let mut error_items = SmallVec::new();
415
416 stdx::always!(next_items.is_empty());
417
418 match_loop_inner(
419 src.clone(),
420 &stack,
421 &mut res,
422 &mut cur_items,
423 &mut bb_items,
424 &mut next_items,
425 &mut eof_items,
426 &mut error_items,
427 );
428 stdx::always!(cur_items.is_empty());
429
430 if error_items.len() > 0 {
431 error_reover_item = error_items.pop();
432 } else if eof_items.len() > 0 {
433 error_reover_item = Some(eof_items[0].clone());
434 }
435
436 // We need to do some post processing after the `match_loop_inner`.
437 // If we reached the EOF, check that there is EXACTLY ONE possible matcher. Otherwise,
438 // either the parse is ambiguous (which should never happen) or there is a syntax error.
439 if src.peek_n(0).is_none() && stack.is_empty() {
440 if eof_items.len() == 1 {
441 // remove all errors, because it is the correct answer !
442 res = Match::default();
443 res.bindings = eof_items[0].bindings[0].clone();
444 } else {
445 // Error recovery
446 if error_reover_item.is_some() {
447 res.bindings = error_reover_item.unwrap().bindings[0].clone();
448 }
449 res.add_err(ExpandError::UnexpectedToken);
450 }
451 return res;
452 }
453
454 // If there are no possible next positions AND we aren't waiting for the black-box parser,
455 // then there is a syntax error.
456 //
457 // Another possibility is that we need to call out to parse some rust nonterminal
458 // (black-box) parser. However, if there is not EXACTLY ONE of these, something is wrong.
459 if (bb_items.is_empty() && next_items.is_empty())
460 || (!bb_items.is_empty() && !next_items.is_empty())
461 || bb_items.len() > 1
462 {
463 res.unmatched_tts += src.len();
464 while let Some(it) = stack.pop() {
465 src = it;
466 res.unmatched_tts += src.len();
467 }
468 res.add_err(err!("leftover tokens"));
469
470 if let Some(mut error_reover_item) = error_reover_item {
471 res.bindings = error_reover_item.bindings.remove(0);
472 }
473 return res;
474 }
475 // Dump all possible `next_items` into `cur_items` for the next iteration.
476 else if !next_items.is_empty() {
477 // Now process the next token
478 cur_items.extend(next_items.drain(..));
479
480 match src.next() {
481 Some(tt::TokenTree::Subtree(subtree)) => {
482 stack.push(src.clone());
483 src = TtIter::new(subtree);
484 }
485 None if !stack.is_empty() => src = stack.pop().unwrap(),
486 _ => (),
487 }
488 }
489 // Finally, we have the case where we need to call the black-box parser to get some
490 // nonterminal.
491 else {
492 stdx::always!(bb_items.len() == 1);
493 let mut item = bb_items.pop().unwrap();
494
495 if let Some(OpDelimited::Op(Op::Var { name, .. })) = item.dot.peek() {
496 let (iter, match_res) = item.meta_result.take().unwrap();
497 let bindings = item.bindings.last_mut().unwrap();
498 match match_res.value {
499 Some(fragment) => {
500 bindings.inner.push((name.clone(), Binding::Fragment(fragment)));
501 }
502 None if match_res.err.is_none() => bindings.push_optional(name),
503 _ => {}
504 }
505 if let Some(err) = match_res.err {
506 res.add_err(err);
507 }
508 src = iter.clone();
509 item.dot.next();
510 } else {
511 unreachable!()
512 }
513 cur_items.push(item);
514 }
515 stdx::always!(!cur_items.is_empty());
516 }
517}
518
519fn match_leaf(lhs: &tt::Leaf, src: &mut TtIter) -> Result<(), ExpandError> {
520 let rhs = match src.expect_leaf() {
521 Ok(l) => l,
522 Err(()) => {
523 return Err(err!("expected leaf: `{}`", lhs));
524 }
525 };
526 match (lhs, rhs) {
527 (
528 tt::Leaf::Punct(tt::Punct { char: lhs, .. }),
529 tt::Leaf::Punct(tt::Punct { char: rhs, .. }),
530 ) if lhs == rhs => (),
531 (
532 tt::Leaf::Ident(tt::Ident { text: lhs, .. }),
533 tt::Leaf::Ident(tt::Ident { text: rhs, .. }),
534 ) if lhs == rhs => (),
535 (
536 tt::Leaf::Literal(tt::Literal { text: lhs, .. }),
537 tt::Leaf::Literal(tt::Literal { text: rhs, .. }),
538 ) if lhs == rhs => (),
539 _ => {
540 return Err(ExpandError::UnexpectedToken);
541 }
542 }
543
544 Ok(())
545}
546
547fn match_meta_var(kind: &str, input: &mut TtIter) -> ExpandResult<Option<Fragment>> {
548 let fragment = match kind {
549 "path" => Path,
550 "expr" => Expr,
551 "ty" => Type,
552 "pat" => Pattern,
553 "stmt" => Statement,
554 "block" => Block,
555 "meta" => MetaItem,
556 "item" => Item,
557 _ => {
558 let tt_result = match kind {
559 "ident" => input
560 .expect_ident()
561 .map(|ident| Some(tt::Leaf::from(ident.clone()).into()))
562 .map_err(|()| err!("expected ident")),
563 "tt" => input.expect_tt().map(Some).map_err(|()| err!()),
564 "lifetime" => input
565 .expect_lifetime()
566 .map(|tt| Some(tt))
567 .map_err(|()| err!("expected lifetime")),
568 "literal" => {
569 let neg = input.eat_char('-');
570 input
571 .expect_literal()
572 .map(|literal| {
573 let lit = tt::Leaf::from(literal.clone());
574 match neg {
575 None => Some(lit.into()),
576 Some(neg) => Some(tt::TokenTree::Subtree(tt::Subtree {
577 delimiter: None,
578 token_trees: vec![neg, lit.into()],
579 })),
580 }
581 })
582 .map_err(|()| err!())
583 }
584 // `vis` is optional
585 "vis" => match input.eat_vis() {
586 Some(vis) => Ok(Some(vis)),
587 None => Ok(None),
588 },
589 _ => Err(ExpandError::UnexpectedToken),
590 };
591 return tt_result.map(|it| it.map(Fragment::Tokens)).into();
592 }
593 };
594 let result = input.expect_fragment(fragment);
595 result.map(|tt| if kind == "expr" { tt.map(Fragment::Ast) } else { tt.map(Fragment::Tokens) })
596}
597
598fn collect_vars(buf: &mut Vec<SmolStr>, pattern: &MetaTemplate) {
599 for op in pattern.iter() {
600 match op {
601 Op::Var { name, .. } => buf.push(name.clone()),
602 Op::Leaf(_) => (),
603 Op::Subtree { tokens, .. } => collect_vars(buf, tokens),
604 Op::Repeat { tokens, .. } => collect_vars(buf, tokens),
605 }
606 }
607}
608
609impl<'a> TtIter<'a> {
610 fn expect_separator(&mut self, separator: &Separator, idx: usize) -> bool {
611 let mut fork = self.clone();
612 let ok = match separator {
613 Separator::Ident(lhs) if idx == 0 => match fork.expect_ident() {
614 Ok(rhs) => rhs.text == lhs.text,
615 _ => false,
616 },
617 Separator::Literal(lhs) if idx == 0 => match fork.expect_literal() {
618 Ok(rhs) => match rhs {
619 tt::Leaf::Literal(rhs) => rhs.text == lhs.text,
620 tt::Leaf::Ident(rhs) => rhs.text == lhs.text,
621 tt::Leaf::Punct(_) => false,
622 },
623 _ => false,
624 },
625 Separator::Puncts(lhss) if idx < lhss.len() => match fork.expect_punct() {
626 Ok(rhs) => rhs.char == lhss[idx].char,
627 _ => false,
628 },
629 _ => false,
630 };
631 if ok {
632 *self = fork;
633 }
634 ok
635 }
636
637 fn expect_tt(&mut self) -> Result<tt::TokenTree, ()> {
638 match self.peek_n(0) {
639 Some(tt::TokenTree::Leaf(tt::Leaf::Punct(punct))) if punct.char == '\'' => {
640 return self.expect_lifetime();
641 }
642 _ => (),
643 }
644
645 let tt = self.next().ok_or_else(|| ())?.clone();
646 let punct = match tt {
647 tt::TokenTree::Leaf(tt::Leaf::Punct(punct)) if punct.spacing == tt::Spacing::Joint => {
648 punct
649 }
650 _ => return Ok(tt),
651 };
652
653 let (second, third) = match (self.peek_n(0), self.peek_n(1)) {
654 (
655 Some(tt::TokenTree::Leaf(tt::Leaf::Punct(p2))),
656 Some(tt::TokenTree::Leaf(tt::Leaf::Punct(p3))),
657 ) if p2.spacing == tt::Spacing::Joint => (p2.char, Some(p3.char)),
658 (Some(tt::TokenTree::Leaf(tt::Leaf::Punct(p2))), _) => (p2.char, None),
659 _ => return Ok(tt),
660 };
661
662 match (punct.char, second, third) {
663 ('.', '.', Some('.'))
664 | ('.', '.', Some('='))
665 | ('<', '<', Some('='))
666 | ('>', '>', Some('=')) => {
667 let tt2 = self.next().unwrap().clone();
668 let tt3 = self.next().unwrap().clone();
669 Ok(tt::Subtree { delimiter: None, token_trees: vec![tt, tt2, tt3] }.into())
670 }
671 ('-', '=', _)
672 | ('-', '>', _)
673 | (':', ':', _)
674 | ('!', '=', _)
675 | ('.', '.', _)
676 | ('*', '=', _)
677 | ('/', '=', _)
678 | ('&', '&', _)
679 | ('&', '=', _)
680 | ('%', '=', _)
681 | ('^', '=', _)
682 | ('+', '=', _)
683 | ('<', '<', _)
684 | ('<', '=', _)
685 | ('=', '=', _)
686 | ('=', '>', _)
687 | ('>', '=', _)
688 | ('>', '>', _)
689 | ('|', '=', _)
690 | ('|', '|', _) => {
691 let tt2 = self.next().unwrap().clone();
692 Ok(tt::Subtree { delimiter: None, token_trees: vec![tt, tt2] }.into())
693 }
694 _ => Ok(tt),
695 }
696 }
697
698 fn expect_lifetime(&mut self) -> Result<tt::TokenTree, ()> {
699 let punct = self.expect_punct()?;
700 if punct.char != '\'' {
701 return Err(());
702 }
703 let ident = self.expect_ident()?;
704
705 Ok(tt::Subtree {
706 delimiter: None,
707 token_trees: vec![
708 tt::Leaf::Punct(*punct).into(),
709 tt::Leaf::Ident(ident.clone()).into(),
710 ],
711 }
712 .into())
713 }
714
715 fn eat_vis(&mut self) -> Option<tt::TokenTree> {
716 let mut fork = self.clone();
717 match fork.expect_fragment(Visibility) {
718 ExpandResult { value: tt, err: None } => {
719 *self = fork;
720 tt
721 }
722 ExpandResult { value: _, err: Some(_) } => None,
723 }
724 }
725
726 fn eat_char(&mut self, c: char) -> Option<tt::TokenTree> {
727 let mut fork = self.clone();
728 match fork.expect_char(c) {
729 Ok(_) => {
730 let tt = self.next().cloned();
731 *self = fork;
732 tt
733 }
734 Err(_) => None,
735 }
736 }
737}
diff --git a/crates/mbe/src/mbe_expander/transcriber.rs b/crates/mbe/src/expander/transcriber.rs
index 59a3c80a8..ad9953a7d 100644
--- a/crates/mbe/src/mbe_expander/transcriber.rs
+++ b/crates/mbe/src/expander/transcriber.rs
@@ -2,23 +2,28 @@
2//! `$ident => foo`, interpolates variables in the template, to get `fn foo() {}` 2//! `$ident => foo`, interpolates variables in the template, to get `fn foo() {}`
3 3
4use syntax::SmolStr; 4use syntax::SmolStr;
5use tt::Delimiter;
5 6
6use super::ExpandResult; 7use super::ExpandResult;
7use crate::{ 8use crate::{
8 mbe_expander::{Binding, Bindings, Fragment}, 9 expander::{Binding, Bindings, Fragment},
9 parser::{Op, RepeatKind, Separator}, 10 parser::{Op, RepeatKind, Separator},
10 ExpandError, MetaTemplate, 11 ExpandError, MetaTemplate,
11}; 12};
12 13
13impl Bindings { 14impl Bindings {
14 fn contains(&self, name: &str) -> bool { 15 fn contains(&self, name: &str) -> bool {
15 self.inner.contains_key(name) 16 self.inner.iter().any(|(n, _)| n == name)
16 } 17 }
17 18
18 fn get(&self, name: &str, nesting: &mut [NestingState]) -> Result<&Fragment, ExpandError> { 19 fn get(&self, name: &str, nesting: &mut [NestingState]) -> Result<&Fragment, ExpandError> {
19 let mut b = self.inner.get(name).ok_or_else(|| { 20 let mut b: &Binding = self
20 ExpandError::BindingError(format!("could not find binding `{}`", name)) 21 .inner
21 })?; 22 .iter()
23 .find_map(|(n, b)| if n == name { Some(b) } else { None })
24 .ok_or_else(|| {
25 ExpandError::BindingError(format!("could not find binding `{}`", name))
26 })?;
22 for nesting_state in nesting.iter_mut() { 27 for nesting_state in nesting.iter_mut() {
23 nesting_state.hit = true; 28 nesting_state.hit = true;
24 b = match b { 29 b = match b {
@@ -54,10 +59,9 @@ pub(super) fn transcribe(
54 template: &MetaTemplate, 59 template: &MetaTemplate,
55 bindings: &Bindings, 60 bindings: &Bindings,
56) -> ExpandResult<tt::Subtree> { 61) -> ExpandResult<tt::Subtree> {
57 assert!(template.delimiter == None);
58 let mut ctx = ExpandCtx { bindings: &bindings, nesting: Vec::new() }; 62 let mut ctx = ExpandCtx { bindings: &bindings, nesting: Vec::new() };
59 let mut arena: Vec<tt::TokenTree> = Vec::new(); 63 let mut arena: Vec<tt::TokenTree> = Vec::new();
60 expand_subtree(&mut ctx, template, &mut arena) 64 expand_subtree(&mut ctx, template, None, &mut arena)
61} 65}
62 66
63#[derive(Debug)] 67#[derive(Debug)]
@@ -80,23 +84,18 @@ struct ExpandCtx<'a> {
80fn expand_subtree( 84fn expand_subtree(
81 ctx: &mut ExpandCtx, 85 ctx: &mut ExpandCtx,
82 template: &MetaTemplate, 86 template: &MetaTemplate,
87 delimiter: Option<Delimiter>,
83 arena: &mut Vec<tt::TokenTree>, 88 arena: &mut Vec<tt::TokenTree>,
84) -> ExpandResult<tt::Subtree> { 89) -> ExpandResult<tt::Subtree> {
85 // remember how many elements are in the arena now - when returning, we want to drain exactly how many elements we added. This way, the recursive uses of the arena get their own "view" of the arena, but will reuse the allocation 90 // remember how many elements are in the arena now - when returning, we want to drain exactly how many elements we added. This way, the recursive uses of the arena get their own "view" of the arena, but will reuse the allocation
86 let start_elements = arena.len(); 91 let start_elements = arena.len();
87 let mut err = None; 92 let mut err = None;
88 for op in template.iter() { 93 for op in template.iter() {
89 let op = match op {
90 Ok(op) => op,
91 Err(e) => {
92 err = Some(e.clone());
93 break;
94 }
95 };
96 match op { 94 match op {
97 Op::Leaf(tt) => arena.push(tt.clone().into()), 95 Op::Leaf(tt) => arena.push(tt.clone().into()),
98 Op::Subtree(tt) => { 96 Op::Subtree { tokens, delimiter } => {
99 let ExpandResult { value: tt, err: e } = expand_subtree(ctx, &tt, arena); 97 let ExpandResult { value: tt, err: e } =
98 expand_subtree(ctx, &tokens, *delimiter, arena);
100 err = err.or(e); 99 err = err.or(e);
101 arena.push(tt.into()); 100 arena.push(tt.into());
102 } 101 }
@@ -105,7 +104,7 @@ fn expand_subtree(
105 err = err.or(e); 104 err = err.or(e);
106 push_fragment(arena, fragment); 105 push_fragment(arena, fragment);
107 } 106 }
108 Op::Repeat { subtree, kind, separator } => { 107 Op::Repeat { tokens: subtree, kind, separator } => {
109 let ExpandResult { value: fragment, err: e } = 108 let ExpandResult { value: fragment, err: e } =
110 expand_repeat(ctx, subtree, *kind, separator, arena); 109 expand_repeat(ctx, subtree, *kind, separator, arena);
111 err = err.or(e); 110 err = err.or(e);
@@ -115,7 +114,7 @@ fn expand_subtree(
115 } 114 }
116 // drain the elements added in this instance of expand_subtree 115 // drain the elements added in this instance of expand_subtree
117 let tts = arena.drain(start_elements..arena.len()).collect(); 116 let tts = arena.drain(start_elements..arena.len()).collect();
118 ExpandResult { value: tt::Subtree { delimiter: template.delimiter, token_trees: tts }, err } 117 ExpandResult { value: tt::Subtree { delimiter, token_trees: tts }, err }
119} 118}
120 119
121fn expand_var(ctx: &mut ExpandCtx, v: &SmolStr, id: tt::TokenId) -> ExpandResult<Fragment> { 120fn expand_var(ctx: &mut ExpandCtx, v: &SmolStr, id: tt::TokenId) -> ExpandResult<Fragment> {
@@ -169,7 +168,7 @@ fn expand_repeat(
169 let mut counter = 0; 168 let mut counter = 0;
170 169
171 loop { 170 loop {
172 let ExpandResult { value: mut t, err: e } = expand_subtree(ctx, template, arena); 171 let ExpandResult { value: mut t, err: e } = expand_subtree(ctx, template, None, arena);
173 let nesting_state = ctx.nesting.last_mut().unwrap(); 172 let nesting_state = ctx.nesting.last_mut().unwrap();
174 if nesting_state.at_end || !nesting_state.hit { 173 if nesting_state.at_end || !nesting_state.hit {
175 break; 174 break;
diff --git a/crates/mbe/src/lib.rs b/crates/mbe/src/lib.rs
index 19543d777..f3d2da55a 100644
--- a/crates/mbe/src/lib.rs
+++ b/crates/mbe/src/lib.rs
@@ -4,7 +4,7 @@
4//! `TokenTree`s as well! 4//! `TokenTree`s as well!
5 5
6mod parser; 6mod parser;
7mod mbe_expander; 7mod expander;
8mod syntax_bridge; 8mod syntax_bridge;
9mod tt_iter; 9mod tt_iter;
10mod subtree_source; 10mod subtree_source;
@@ -12,18 +12,24 @@ mod subtree_source;
12#[cfg(test)] 12#[cfg(test)]
13mod tests; 13mod tests;
14 14
15#[cfg(test)]
16mod benchmark;
17
15use std::fmt; 18use std::fmt;
16 19
20use test_utils::mark;
17pub use tt::{Delimiter, DelimiterKind, Punct}; 21pub use tt::{Delimiter, DelimiterKind, Punct};
18 22
19use crate::{ 23use crate::{
20 parser::{parse_pattern, parse_template, Op}, 24 parser::{parse_pattern, parse_template, MetaTemplate, Op},
21 tt_iter::TtIter, 25 tt_iter::TtIter,
22}; 26};
23 27
24#[derive(Debug, PartialEq, Eq)] 28#[derive(Debug, PartialEq, Eq)]
25pub enum ParseError { 29pub enum ParseError {
30 UnexpectedToken(String),
26 Expected(String), 31 Expected(String),
32 InvalidRepeat,
27 RepetitionEmptyTokenTree, 33 RepetitionEmptyTokenTree,
28} 34}
29 35
@@ -33,7 +39,6 @@ pub enum ExpandError {
33 UnexpectedToken, 39 UnexpectedToken,
34 BindingError(String), 40 BindingError(String),
35 ConversionError, 41 ConversionError,
36 InvalidRepeat,
37 ProcMacroError(tt::ExpansionError), 42 ProcMacroError(tt::ExpansionError),
38 UnresolvedProcMacro, 43 UnresolvedProcMacro,
39 Other(String), 44 Other(String),
@@ -52,7 +57,6 @@ impl fmt::Display for ExpandError {
52 ExpandError::UnexpectedToken => f.write_str("unexpected token in input"), 57 ExpandError::UnexpectedToken => f.write_str("unexpected token in input"),
53 ExpandError::BindingError(e) => f.write_str(e), 58 ExpandError::BindingError(e) => f.write_str(e),
54 ExpandError::ConversionError => f.write_str("could not convert tokens"), 59 ExpandError::ConversionError => f.write_str("could not convert tokens"),
55 ExpandError::InvalidRepeat => f.write_str("invalid repeat expression"),
56 ExpandError::ProcMacroError(e) => e.fmt(f), 60 ExpandError::ProcMacroError(e) => e.fmt(f),
57 ExpandError::UnresolvedProcMacro => f.write_str("unresolved proc macro"), 61 ExpandError::UnresolvedProcMacro => f.write_str("unresolved proc macro"),
58 ExpandError::Other(e) => f.write_str(e), 62 ExpandError::Other(e) => f.write_str(e),
@@ -61,8 +65,8 @@ impl fmt::Display for ExpandError {
61} 65}
62 66
63pub use crate::syntax_bridge::{ 67pub use crate::syntax_bridge::{
64 ast_to_token_tree, parse_to_token_tree, syntax_node_to_token_tree, token_tree_to_syntax_node, 68 ast_to_token_tree, parse_exprs_with_sep, parse_to_token_tree, syntax_node_to_token_tree,
65 TokenMap, 69 token_tree_to_syntax_node, TokenMap,
66}; 70};
67 71
68/// This struct contains AST for a single `macro_rules` definition. What might 72/// This struct contains AST for a single `macro_rules` definition. What might
@@ -76,26 +80,18 @@ pub struct MacroRules {
76 shift: Shift, 80 shift: Shift,
77} 81}
78 82
83/// For Macro 2.0
79#[derive(Clone, Debug, PartialEq, Eq)] 84#[derive(Clone, Debug, PartialEq, Eq)]
80struct Rule { 85pub struct MacroDef {
81 lhs: MetaTemplate, 86 rules: Vec<Rule>,
82 rhs: MetaTemplate, 87 /// Highest id of the token we have in TokenMap
88 shift: Shift,
83} 89}
84 90
85#[derive(Clone, Debug, PartialEq, Eq)] 91#[derive(Clone, Debug, PartialEq, Eq)]
86struct MetaTemplate { 92struct Rule {
87 delimiter: Option<Delimiter>, 93 lhs: MetaTemplate,
88 tokens: Vec<Result<Op, ExpandError>>, 94 rhs: MetaTemplate,
89}
90
91impl<'a> MetaTemplate {
92 fn iter(&self) -> impl Iterator<Item = &Result<Op, ExpandError>> {
93 self.tokens.iter()
94 }
95
96 fn delimiter_kind(&self) -> Option<DelimiterKind> {
97 self.delimiter.map(|it| it.kind)
98 }
99} 95}
100 96
101#[derive(Clone, Copy, Debug, PartialEq, Eq)] 97#[derive(Clone, Copy, Debug, PartialEq, Eq)]
@@ -179,7 +175,7 @@ impl MacroRules {
179 let mut src = TtIter::new(tt); 175 let mut src = TtIter::new(tt);
180 let mut rules = Vec::new(); 176 let mut rules = Vec::new();
181 while src.len() > 0 { 177 while src.len() > 0 {
182 let rule = Rule::parse(&mut src)?; 178 let rule = Rule::parse(&mut src, true)?;
183 rules.push(rule); 179 rules.push(rule);
184 if let Err(()) = src.expect_char(';') { 180 if let Err(()) = src.expect_char(';') {
185 if src.len() > 0 { 181 if src.len() > 0 {
@@ -200,7 +196,58 @@ impl MacroRules {
200 // apply shift 196 // apply shift
201 let mut tt = tt.clone(); 197 let mut tt = tt.clone();
202 self.shift.shift_all(&mut tt); 198 self.shift.shift_all(&mut tt);
203 mbe_expander::expand(self, &tt) 199 expander::expand_rules(&self.rules, &tt)
200 }
201
202 pub fn map_id_down(&self, id: tt::TokenId) -> tt::TokenId {
203 self.shift.shift(id)
204 }
205
206 pub fn map_id_up(&self, id: tt::TokenId) -> (tt::TokenId, Origin) {
207 match self.shift.unshift(id) {
208 Some(id) => (id, Origin::Call),
209 None => (id, Origin::Def),
210 }
211 }
212}
213
214impl MacroDef {
215 pub fn parse(tt: &tt::Subtree) -> Result<MacroDef, ParseError> {
216 let mut src = TtIter::new(tt);
217 let mut rules = Vec::new();
218
219 if Some(tt::DelimiterKind::Brace) == tt.delimiter_kind() {
220 mark::hit!(parse_macro_def_rules);
221 while src.len() > 0 {
222 let rule = Rule::parse(&mut src, true)?;
223 rules.push(rule);
224 if let Err(()) = src.expect_char(';') {
225 if src.len() > 0 {
226 return Err(ParseError::Expected("expected `;`".to_string()));
227 }
228 break;
229 }
230 }
231 } else {
232 mark::hit!(parse_macro_def_simple);
233 let rule = Rule::parse(&mut src, false)?;
234 if src.len() != 0 {
235 return Err(ParseError::Expected("remain tokens in macro def".to_string()));
236 }
237 rules.push(rule);
238 }
239 for rule in rules.iter() {
240 validate(&rule.lhs)?;
241 }
242
243 Ok(MacroDef { rules, shift: Shift::new(tt) })
244 }
245
246 pub fn expand(&self, tt: &tt::Subtree) -> ExpandResult<tt::Subtree> {
247 // apply shift
248 let mut tt = tt.clone();
249 self.shift.shift_all(&mut tt);
250 expander::expand_rules(&self.rules, &tt)
204 } 251 }
205 252
206 pub fn map_id_down(&self, id: tt::TokenId) -> tt::TokenId { 253 pub fn map_id_down(&self, id: tt::TokenId) -> tt::TokenId {
@@ -216,57 +263,50 @@ impl MacroRules {
216} 263}
217 264
218impl Rule { 265impl Rule {
219 fn parse(src: &mut TtIter) -> Result<Rule, ParseError> { 266 fn parse(src: &mut TtIter, expect_arrow: bool) -> Result<Rule, ParseError> {
220 let lhs = src 267 let lhs = src
221 .expect_subtree() 268 .expect_subtree()
222 .map_err(|()| ParseError::Expected("expected subtree".to_string()))?; 269 .map_err(|()| ParseError::Expected("expected subtree".to_string()))?;
223 src.expect_char('=').map_err(|()| ParseError::Expected("expected `=`".to_string()))?; 270 if expect_arrow {
224 src.expect_char('>').map_err(|()| ParseError::Expected("expected `>`".to_string()))?; 271 src.expect_char('=').map_err(|()| ParseError::Expected("expected `=`".to_string()))?;
272 src.expect_char('>').map_err(|()| ParseError::Expected("expected `>`".to_string()))?;
273 }
225 let rhs = src 274 let rhs = src
226 .expect_subtree() 275 .expect_subtree()
227 .map_err(|()| ParseError::Expected("expected subtree".to_string()))?; 276 .map_err(|()| ParseError::Expected("expected subtree".to_string()))?;
228 277
229 let lhs = MetaTemplate { tokens: parse_pattern(&lhs), delimiter: None }; 278 let lhs = MetaTemplate(parse_pattern(&lhs)?);
230 let rhs = MetaTemplate { tokens: parse_template(&rhs), delimiter: None }; 279 let rhs = MetaTemplate(parse_template(&rhs)?);
231 280
232 Ok(crate::Rule { lhs, rhs }) 281 Ok(crate::Rule { lhs, rhs })
233 } 282 }
234} 283}
235 284
236fn to_parse_error(e: &ExpandError) -> ParseError {
237 let msg = match e {
238 ExpandError::InvalidRepeat => "invalid repeat".to_string(),
239 _ => "invalid macro definition".to_string(),
240 };
241 ParseError::Expected(msg)
242}
243
244fn validate(pattern: &MetaTemplate) -> Result<(), ParseError> { 285fn validate(pattern: &MetaTemplate) -> Result<(), ParseError> {
245 for op in pattern.iter() { 286 for op in pattern.iter() {
246 let op = op.as_ref().map_err(|e| to_parse_error(&e))?;
247
248 match op { 287 match op {
249 Op::Subtree(subtree) => validate(&subtree)?, 288 Op::Subtree { tokens, .. } => validate(&tokens)?,
250 Op::Repeat { subtree, separator, .. } => { 289 Op::Repeat { tokens: subtree, separator, .. } => {
251 // Checks that no repetition which could match an empty token 290 // Checks that no repetition which could match an empty token
252 // https://github.com/rust-lang/rust/blob/a58b1ed44f5e06976de2bdc4d7dc81c36a96934f/src/librustc_expand/mbe/macro_rules.rs#L558 291 // https://github.com/rust-lang/rust/blob/a58b1ed44f5e06976de2bdc4d7dc81c36a96934f/src/librustc_expand/mbe/macro_rules.rs#L558
253 292
254 if separator.is_none() { 293 if separator.is_none() {
255 if subtree.iter().all(|child_op| { 294 if subtree.iter().all(|child_op| {
256 match child_op.as_ref().map_err(to_parse_error) { 295 match child_op {
257 Ok(Op::Var { kind, .. }) => { 296 Op::Var { kind, .. } => {
258 // vis is optional 297 // vis is optional
259 if kind.as_ref().map_or(false, |it| it == "vis") { 298 if kind.as_ref().map_or(false, |it| it == "vis") {
260 return true; 299 return true;
261 } 300 }
262 } 301 }
263 Ok(Op::Repeat { kind, .. }) => { 302 Op::Repeat { kind, .. } => {
264 return matches!( 303 return matches!(
265 kind, 304 kind,
266 parser::RepeatKind::ZeroOrMore | parser::RepeatKind::ZeroOrOne 305 parser::RepeatKind::ZeroOrMore | parser::RepeatKind::ZeroOrOne
267 ) 306 )
268 } 307 }
269 _ => {} 308 Op::Leaf(_) => {}
309 Op::Subtree { .. } => {}
270 } 310 }
271 false 311 false
272 }) { 312 }) {
diff --git a/crates/mbe/src/mbe_expander/matcher.rs b/crates/mbe/src/mbe_expander/matcher.rs
deleted file mode 100644
index d32e60521..000000000
--- a/crates/mbe/src/mbe_expander/matcher.rs
+++ /dev/null
@@ -1,502 +0,0 @@
1//! FIXME: write short doc here
2
3use crate::{
4 mbe_expander::{Binding, Bindings, Fragment},
5 parser::{Op, RepeatKind, Separator},
6 subtree_source::SubtreeTokenSource,
7 tt_iter::TtIter,
8 ExpandError, MetaTemplate,
9};
10
11use super::ExpandResult;
12use parser::{FragmentKind::*, TreeSink};
13use syntax::{SmolStr, SyntaxKind};
14use tt::buffer::{Cursor, TokenBuffer};
15
16impl Bindings {
17 fn push_optional(&mut self, name: &SmolStr) {
18 // FIXME: Do we have a better way to represent an empty token ?
19 // Insert an empty subtree for empty token
20 let tt = tt::Subtree::default().into();
21 self.inner.insert(name.clone(), Binding::Fragment(Fragment::Tokens(tt)));
22 }
23
24 fn push_empty(&mut self, name: &SmolStr) {
25 self.inner.insert(name.clone(), Binding::Empty);
26 }
27
28 fn push_nested(&mut self, idx: usize, nested: Bindings) -> Result<(), ExpandError> {
29 for (key, value) in nested.inner {
30 if !self.inner.contains_key(&key) {
31 self.inner.insert(key.clone(), Binding::Nested(Vec::new()));
32 }
33 match self.inner.get_mut(&key) {
34 Some(Binding::Nested(it)) => {
35 // insert empty nested bindings before this one
36 while it.len() < idx {
37 it.push(Binding::Nested(vec![]));
38 }
39 it.push(value);
40 }
41 _ => {
42 return Err(ExpandError::BindingError(format!(
43 "could not find binding `{}`",
44 key
45 )));
46 }
47 }
48 }
49 Ok(())
50 }
51}
52
53macro_rules! err {
54 () => {
55 ExpandError::BindingError(format!(""))
56 };
57 ($($tt:tt)*) => {
58 ExpandError::BindingError(format!($($tt)*))
59 };
60}
61
62#[derive(Debug, Default)]
63pub(super) struct Match {
64 pub(super) bindings: Bindings,
65 /// We currently just keep the first error and count the rest to compare matches.
66 pub(super) err: Option<ExpandError>,
67 pub(super) err_count: usize,
68 /// How many top-level token trees were left to match.
69 pub(super) unmatched_tts: usize,
70}
71
72impl Match {
73 pub(super) fn add_err(&mut self, err: ExpandError) {
74 let prev_err = self.err.take();
75 self.err = prev_err.or(Some(err));
76 self.err_count += 1;
77 }
78}
79
80// General note: These functions have two channels to return errors, a `Result`
81// return value and the `&mut Match`. The returned Result is for pattern parsing
82// errors; if a branch of the macro definition doesn't parse, it doesn't make
83// sense to try using it. Matching errors are added to the `Match`. It might
84// make sense to make pattern parsing a separate step?
85
86pub(super) fn match_(pattern: &MetaTemplate, src: &tt::Subtree) -> Result<Match, ExpandError> {
87 assert!(pattern.delimiter == None);
88
89 let mut res = Match::default();
90 let mut src = TtIter::new(src);
91
92 match_subtree(&mut res, pattern, &mut src)?;
93
94 if src.len() > 0 {
95 res.unmatched_tts += src.len();
96 res.add_err(err!("leftover tokens"));
97 }
98
99 Ok(res)
100}
101
102fn match_subtree(
103 res: &mut Match,
104 pattern: &MetaTemplate,
105 src: &mut TtIter,
106) -> Result<(), ExpandError> {
107 for op in pattern.iter() {
108 match op.as_ref().map_err(|err| err.clone())? {
109 Op::Leaf(lhs) => {
110 let rhs = match src.expect_leaf() {
111 Ok(l) => l,
112 Err(()) => {
113 res.add_err(err!("expected leaf: `{}`", lhs));
114 continue;
115 }
116 };
117 match (lhs, rhs) {
118 (
119 tt::Leaf::Punct(tt::Punct { char: lhs, .. }),
120 tt::Leaf::Punct(tt::Punct { char: rhs, .. }),
121 ) if lhs == rhs => (),
122 (
123 tt::Leaf::Ident(tt::Ident { text: lhs, .. }),
124 tt::Leaf::Ident(tt::Ident { text: rhs, .. }),
125 ) if lhs == rhs => (),
126 (
127 tt::Leaf::Literal(tt::Literal { text: lhs, .. }),
128 tt::Leaf::Literal(tt::Literal { text: rhs, .. }),
129 ) if lhs == rhs => (),
130 _ => {
131 res.add_err(ExpandError::UnexpectedToken);
132 }
133 }
134 }
135 Op::Subtree(lhs) => {
136 let rhs = match src.expect_subtree() {
137 Ok(s) => s,
138 Err(()) => {
139 res.add_err(err!("expected subtree"));
140 continue;
141 }
142 };
143 if lhs.delimiter_kind() != rhs.delimiter_kind() {
144 res.add_err(err!("mismatched delimiter"));
145 continue;
146 }
147 let mut src = TtIter::new(rhs);
148 match_subtree(res, lhs, &mut src)?;
149 if src.len() > 0 {
150 res.add_err(err!("leftover tokens"));
151 }
152 }
153 Op::Var { name, kind, .. } => {
154 let kind = match kind {
155 Some(k) => k,
156 None => {
157 res.add_err(ExpandError::UnexpectedToken);
158 continue;
159 }
160 };
161 let ExpandResult { value: matched, err: match_err } =
162 match_meta_var(kind.as_str(), src);
163 match matched {
164 Some(fragment) => {
165 res.bindings.inner.insert(name.clone(), Binding::Fragment(fragment));
166 }
167 None if match_err.is_none() => res.bindings.push_optional(name),
168 _ => {}
169 }
170 if let Some(err) = match_err {
171 res.add_err(err);
172 }
173 }
174 Op::Repeat { subtree, kind, separator } => {
175 match_repeat(res, subtree, *kind, separator, src)?;
176 }
177 }
178 }
179 Ok(())
180}
181
182impl<'a> TtIter<'a> {
183 fn eat_separator(&mut self, separator: &Separator) -> bool {
184 let mut fork = self.clone();
185 let ok = match separator {
186 Separator::Ident(lhs) => match fork.expect_ident() {
187 Ok(rhs) => rhs.text == lhs.text,
188 _ => false,
189 },
190 Separator::Literal(lhs) => match fork.expect_literal() {
191 Ok(rhs) => match rhs {
192 tt::Leaf::Literal(rhs) => rhs.text == lhs.text,
193 tt::Leaf::Ident(rhs) => rhs.text == lhs.text,
194 tt::Leaf::Punct(_) => false,
195 },
196 _ => false,
197 },
198 Separator::Puncts(lhss) => lhss.iter().all(|lhs| match fork.expect_punct() {
199 Ok(rhs) => rhs.char == lhs.char,
200 _ => false,
201 }),
202 };
203 if ok {
204 *self = fork;
205 }
206 ok
207 }
208
209 pub(crate) fn expect_tt(&mut self) -> Result<tt::TokenTree, ()> {
210 match self.peek_n(0) {
211 Some(tt::TokenTree::Leaf(tt::Leaf::Punct(punct))) if punct.char == '\'' => {
212 return self.expect_lifetime();
213 }
214 _ => (),
215 }
216
217 let tt = self.next().ok_or_else(|| ())?.clone();
218 let punct = match tt {
219 tt::TokenTree::Leaf(tt::Leaf::Punct(punct)) if punct.spacing == tt::Spacing::Joint => {
220 punct
221 }
222 _ => return Ok(tt),
223 };
224
225 let (second, third) = match (self.peek_n(0), self.peek_n(1)) {
226 (
227 Some(tt::TokenTree::Leaf(tt::Leaf::Punct(p2))),
228 Some(tt::TokenTree::Leaf(tt::Leaf::Punct(p3))),
229 ) if p2.spacing == tt::Spacing::Joint => (p2.char, Some(p3.char)),
230 (Some(tt::TokenTree::Leaf(tt::Leaf::Punct(p2))), _) => (p2.char, None),
231 _ => return Ok(tt),
232 };
233
234 match (punct.char, second, third) {
235 ('.', '.', Some('.'))
236 | ('.', '.', Some('='))
237 | ('<', '<', Some('='))
238 | ('>', '>', Some('=')) => {
239 let tt2 = self.next().unwrap().clone();
240 let tt3 = self.next().unwrap().clone();
241 Ok(tt::Subtree { delimiter: None, token_trees: vec![tt, tt2, tt3] }.into())
242 }
243 ('-', '=', _)
244 | ('-', '>', _)
245 | (':', ':', _)
246 | ('!', '=', _)
247 | ('.', '.', _)
248 | ('*', '=', _)
249 | ('/', '=', _)
250 | ('&', '&', _)
251 | ('&', '=', _)
252 | ('%', '=', _)
253 | ('^', '=', _)
254 | ('+', '=', _)
255 | ('<', '<', _)
256 | ('<', '=', _)
257 | ('=', '=', _)
258 | ('=', '>', _)
259 | ('>', '=', _)
260 | ('>', '>', _)
261 | ('|', '=', _)
262 | ('|', '|', _) => {
263 let tt2 = self.next().unwrap().clone();
264 Ok(tt::Subtree { delimiter: None, token_trees: vec![tt, tt2] }.into())
265 }
266 _ => Ok(tt),
267 }
268 }
269
270 pub(crate) fn expect_lifetime(&mut self) -> Result<tt::TokenTree, ()> {
271 let punct = self.expect_punct()?;
272 if punct.char != '\'' {
273 return Err(());
274 }
275 let ident = self.expect_ident()?;
276
277 Ok(tt::Subtree {
278 delimiter: None,
279 token_trees: vec![
280 tt::Leaf::Punct(*punct).into(),
281 tt::Leaf::Ident(ident.clone()).into(),
282 ],
283 }
284 .into())
285 }
286
287 pub(crate) fn expect_fragment(
288 &mut self,
289 fragment_kind: parser::FragmentKind,
290 ) -> ExpandResult<Option<tt::TokenTree>> {
291 pub(crate) struct OffsetTokenSink<'a> {
292 pub(crate) cursor: Cursor<'a>,
293 pub(crate) error: bool,
294 }
295
296 impl<'a> TreeSink for OffsetTokenSink<'a> {
297 fn token(&mut self, kind: SyntaxKind, mut n_tokens: u8) {
298 if kind == SyntaxKind::LIFETIME_IDENT {
299 n_tokens = 2;
300 }
301 for _ in 0..n_tokens {
302 self.cursor = self.cursor.bump_subtree();
303 }
304 }
305 fn start_node(&mut self, _kind: SyntaxKind) {}
306 fn finish_node(&mut self) {}
307 fn error(&mut self, _error: parser::ParseError) {
308 self.error = true;
309 }
310 }
311
312 let buffer = TokenBuffer::from_tokens(&self.inner.as_slice());
313 let mut src = SubtreeTokenSource::new(&buffer);
314 let mut sink = OffsetTokenSink { cursor: buffer.begin(), error: false };
315
316 parser::parse_fragment(&mut src, &mut sink, fragment_kind);
317
318 let mut err = None;
319 if !sink.cursor.is_root() || sink.error {
320 err = Some(err!("expected {:?}", fragment_kind));
321 }
322
323 let mut curr = buffer.begin();
324 let mut res = vec![];
325
326 if sink.cursor.is_root() {
327 while curr != sink.cursor {
328 if let Some(token) = curr.token_tree() {
329 res.push(token);
330 }
331 curr = curr.bump();
332 }
333 }
334 self.inner = self.inner.as_slice()[res.len()..].iter();
335 if res.len() == 0 && err.is_none() {
336 err = Some(err!("no tokens consumed"));
337 }
338 let res = match res.len() {
339 1 => Some(res[0].cloned()),
340 0 => None,
341 _ => Some(tt::TokenTree::Subtree(tt::Subtree {
342 delimiter: None,
343 token_trees: res.into_iter().map(|it| it.cloned()).collect(),
344 })),
345 };
346 ExpandResult { value: res, err }
347 }
348
349 pub(crate) fn eat_vis(&mut self) -> Option<tt::TokenTree> {
350 let mut fork = self.clone();
351 match fork.expect_fragment(Visibility) {
352 ExpandResult { value: tt, err: None } => {
353 *self = fork;
354 tt
355 }
356 ExpandResult { value: _, err: Some(_) } => None,
357 }
358 }
359
360 pub(crate) fn eat_char(&mut self, c: char) -> Option<tt::TokenTree> {
361 let mut fork = self.clone();
362 match fork.expect_char(c) {
363 Ok(_) => {
364 let tt = self.next().cloned();
365 *self = fork;
366 tt
367 }
368 Err(_) => None,
369 }
370 }
371}
372
373pub(super) fn match_repeat(
374 res: &mut Match,
375 pattern: &MetaTemplate,
376 kind: RepeatKind,
377 separator: &Option<Separator>,
378 src: &mut TtIter,
379) -> Result<(), ExpandError> {
380 // Dirty hack to make macro-expansion terminate.
381 // This should be replaced by a proper macro-by-example implementation
382 let mut limit = 65536;
383 let mut counter = 0;
384
385 for i in 0.. {
386 let mut fork = src.clone();
387
388 if let Some(separator) = &separator {
389 if i != 0 && !fork.eat_separator(separator) {
390 break;
391 }
392 }
393
394 let mut nested = Match::default();
395 match_subtree(&mut nested, pattern, &mut fork)?;
396 if nested.err.is_none() {
397 limit -= 1;
398 if limit == 0 {
399 log::warn!(
400 "match_lhs exceeded repeat pattern limit => {:#?}\n{:#?}\n{:#?}\n{:#?}",
401 pattern,
402 src,
403 kind,
404 separator
405 );
406 break;
407 }
408 *src = fork;
409
410 if let Err(err) = res.bindings.push_nested(counter, nested.bindings) {
411 res.add_err(err);
412 }
413 counter += 1;
414 if counter == 1 {
415 if let RepeatKind::ZeroOrOne = kind {
416 break;
417 }
418 }
419 } else {
420 break;
421 }
422 }
423
424 match (kind, counter) {
425 (RepeatKind::OneOrMore, 0) => {
426 res.add_err(ExpandError::UnexpectedToken);
427 }
428 (_, 0) => {
429 // Collect all empty variables in subtrees
430 let mut vars = Vec::new();
431 collect_vars(&mut vars, pattern)?;
432 for var in vars {
433 res.bindings.push_empty(&var)
434 }
435 }
436 _ => (),
437 }
438 Ok(())
439}
440
441fn match_meta_var(kind: &str, input: &mut TtIter) -> ExpandResult<Option<Fragment>> {
442 let fragment = match kind {
443 "path" => Path,
444 "expr" => Expr,
445 "ty" => Type,
446 "pat" => Pattern,
447 "stmt" => Statement,
448 "block" => Block,
449 "meta" => MetaItem,
450 "item" => Item,
451 _ => {
452 let tt_result = match kind {
453 "ident" => input
454 .expect_ident()
455 .map(|ident| Some(tt::Leaf::from(ident.clone()).into()))
456 .map_err(|()| err!("expected ident")),
457 "tt" => input.expect_tt().map(Some).map_err(|()| err!()),
458 "lifetime" => input
459 .expect_lifetime()
460 .map(|tt| Some(tt))
461 .map_err(|()| err!("expected lifetime")),
462 "literal" => {
463 let neg = input.eat_char('-');
464 input
465 .expect_literal()
466 .map(|literal| {
467 let lit = tt::Leaf::from(literal.clone());
468 match neg {
469 None => Some(lit.into()),
470 Some(neg) => Some(tt::TokenTree::Subtree(tt::Subtree {
471 delimiter: None,
472 token_trees: vec![neg, lit.into()],
473 })),
474 }
475 })
476 .map_err(|()| err!())
477 }
478 // `vis` is optional
479 "vis" => match input.eat_vis() {
480 Some(vis) => Ok(Some(vis)),
481 None => Ok(None),
482 },
483 _ => Err(ExpandError::UnexpectedToken),
484 };
485 return tt_result.map(|it| it.map(Fragment::Tokens)).into();
486 }
487 };
488 let result = input.expect_fragment(fragment);
489 result.map(|tt| if kind == "expr" { tt.map(Fragment::Ast) } else { tt.map(Fragment::Tokens) })
490}
491
492fn collect_vars(buf: &mut Vec<SmolStr>, pattern: &MetaTemplate) -> Result<(), ExpandError> {
493 for op in pattern.iter() {
494 match op.as_ref().map_err(|e| e.clone())? {
495 Op::Var { name, .. } => buf.push(name.clone()),
496 Op::Leaf(_) => (),
497 Op::Subtree(subtree) => collect_vars(buf, subtree)?,
498 Op::Repeat { subtree, .. } => collect_vars(buf, subtree)?,
499 }
500 }
501 Ok(())
502}
diff --git a/crates/mbe/src/parser.rs b/crates/mbe/src/parser.rs
index f3047972d..8671322e1 100644
--- a/crates/mbe/src/parser.rs
+++ b/crates/mbe/src/parser.rs
@@ -3,15 +3,84 @@
3 3
4use smallvec::SmallVec; 4use smallvec::SmallVec;
5use syntax::SmolStr; 5use syntax::SmolStr;
6use tt::Delimiter;
6 7
7use crate::{tt_iter::TtIter, ExpandError, MetaTemplate}; 8use crate::{tt_iter::TtIter, ParseError};
9
10#[derive(Clone, Debug, PartialEq, Eq)]
11pub(crate) struct MetaTemplate(pub(crate) Vec<Op>);
12
13#[derive(Debug, Clone, Copy)]
14pub(crate) enum OpDelimited<'a> {
15 Op(&'a Op),
16 Open,
17 Close,
18}
19
20#[derive(Debug, Clone, Copy)]
21pub(crate) struct OpDelimitedIter<'a> {
22 inner: &'a Vec<Op>,
23 delimited: Option<&'a Delimiter>,
24 idx: usize,
25}
26
27impl<'a> OpDelimitedIter<'a> {
28 pub(crate) fn is_eof(&self) -> bool {
29 let len = self.inner.len() + if self.delimited.is_some() { 2 } else { 0 };
30 self.idx >= len
31 }
32
33 pub(crate) fn peek(&self) -> Option<OpDelimited<'a>> {
34 match self.delimited {
35 None => self.inner.get(self.idx).map(OpDelimited::Op),
36 Some(_) => match self.idx {
37 0 => Some(OpDelimited::Open),
38 i if i == self.inner.len() + 1 => Some(OpDelimited::Close),
39 i => self.inner.get(i - 1).map(OpDelimited::Op),
40 },
41 }
42 }
43
44 pub(crate) fn reset(&self) -> Self {
45 Self { inner: &self.inner, idx: 0, delimited: self.delimited }
46 }
47}
48
49impl<'a> Iterator for OpDelimitedIter<'a> {
50 type Item = OpDelimited<'a>;
51
52 fn next(&mut self) -> Option<Self::Item> {
53 let res = self.peek();
54 self.idx += 1;
55 res
56 }
57
58 fn size_hint(&self) -> (usize, Option<usize>) {
59 let len = self.inner.len() + if self.delimited.is_some() { 2 } else { 0 };
60 let remain = len.checked_sub(self.idx).unwrap_or(0);
61 (remain, Some(remain))
62 }
63}
64
65impl<'a> MetaTemplate {
66 pub(crate) fn iter(&self) -> impl Iterator<Item = &Op> {
67 self.0.iter()
68 }
69
70 pub(crate) fn iter_delimited(
71 &'a self,
72 delimited: Option<&'a Delimiter>,
73 ) -> OpDelimitedIter<'a> {
74 OpDelimitedIter { inner: &self.0, idx: 0, delimited }
75 }
76}
8 77
9#[derive(Clone, Debug, PartialEq, Eq)] 78#[derive(Clone, Debug, PartialEq, Eq)]
10pub(crate) enum Op { 79pub(crate) enum Op {
11 Var { name: SmolStr, kind: Option<SmolStr>, id: tt::TokenId }, 80 Var { name: SmolStr, kind: Option<SmolStr>, id: tt::TokenId },
12 Repeat { subtree: MetaTemplate, kind: RepeatKind, separator: Option<Separator> }, 81 Repeat { tokens: MetaTemplate, kind: RepeatKind, separator: Option<Separator> },
13 Leaf(tt::Leaf), 82 Leaf(tt::Leaf),
14 Subtree(MetaTemplate), 83 Subtree { tokens: MetaTemplate, delimiter: Option<Delimiter> },
15} 84}
16 85
17#[derive(Copy, Clone, Debug, PartialEq, Eq)] 86#[derive(Copy, Clone, Debug, PartialEq, Eq)]
@@ -46,12 +115,22 @@ impl PartialEq for Separator {
46 } 115 }
47} 116}
48 117
49pub(crate) fn parse_template(template: &tt::Subtree) -> Vec<Result<Op, ExpandError>> { 118impl Separator {
50 parse_inner(&template, Mode::Template) 119 pub(crate) fn tt_count(&self) -> usize {
120 match self {
121 Separator::Literal(_) => 1,
122 Separator::Ident(_) => 1,
123 Separator::Puncts(it) => it.len(),
124 }
125 }
126}
127
128pub(crate) fn parse_template(template: &tt::Subtree) -> Result<Vec<Op>, ParseError> {
129 parse_inner(&template, Mode::Template).into_iter().collect()
51} 130}
52 131
53pub(crate) fn parse_pattern(pattern: &tt::Subtree) -> Vec<Result<Op, ExpandError>> { 132pub(crate) fn parse_pattern(pattern: &tt::Subtree) -> Result<Vec<Op>, ParseError> {
54 parse_inner(&pattern, Mode::Pattern) 133 parse_inner(&pattern, Mode::Pattern).into_iter().collect()
55} 134}
56 135
57#[derive(Clone, Copy)] 136#[derive(Clone, Copy)]
@@ -60,7 +139,7 @@ enum Mode {
60 Template, 139 Template,
61} 140}
62 141
63fn parse_inner(tt: &tt::Subtree, mode: Mode) -> Vec<Result<Op, ExpandError>> { 142fn parse_inner(tt: &tt::Subtree, mode: Mode) -> Vec<Result<Op, ParseError>> {
64 let mut src = TtIter::new(&tt); 143 let mut src = TtIter::new(&tt);
65 std::iter::from_fn(move || { 144 std::iter::from_fn(move || {
66 let first = src.next()?; 145 let first = src.next()?;
@@ -71,7 +150,7 @@ fn parse_inner(tt: &tt::Subtree, mode: Mode) -> Vec<Result<Op, ExpandError>> {
71 150
72macro_rules! err { 151macro_rules! err {
73 ($($tt:tt)*) => { 152 ($($tt:tt)*) => {
74 ExpandError::UnexpectedToken 153 ParseError::UnexpectedToken(($($tt)*).to_string())
75 }; 154 };
76} 155}
77 156
@@ -81,7 +160,7 @@ macro_rules! bail {
81 }; 160 };
82} 161}
83 162
84fn next_op<'a>(first: &tt::TokenTree, src: &mut TtIter<'a>, mode: Mode) -> Result<Op, ExpandError> { 163fn next_op<'a>(first: &tt::TokenTree, src: &mut TtIter<'a>, mode: Mode) -> Result<Op, ParseError> {
85 let res = match first { 164 let res = match first {
86 tt::TokenTree::Leaf(leaf @ tt::Leaf::Punct(tt::Punct { char: '$', .. })) => { 165 tt::TokenTree::Leaf(leaf @ tt::Leaf::Punct(tt::Punct { char: '$', .. })) => {
87 // Note that the '$' itself is a valid token inside macro_rules. 166 // Note that the '$' itself is a valid token inside macro_rules.
@@ -92,17 +171,17 @@ fn next_op<'a>(first: &tt::TokenTree, src: &mut TtIter<'a>, mode: Mode) -> Resul
92 match second { 171 match second {
93 tt::TokenTree::Subtree(subtree) => { 172 tt::TokenTree::Subtree(subtree) => {
94 let (separator, kind) = parse_repeat(src)?; 173 let (separator, kind) = parse_repeat(src)?;
95 let delimiter = subtree.delimiter; 174 let tokens = parse_inner(&subtree, mode)
96 let tokens = parse_inner(&subtree, mode); 175 .into_iter()
97 let subtree = MetaTemplate { tokens, delimiter }; 176 .collect::<Result<Vec<Op>, ParseError>>()?;
98 Op::Repeat { subtree, separator, kind } 177 Op::Repeat { tokens: MetaTemplate(tokens), separator, kind }
99 } 178 }
100 tt::TokenTree::Leaf(leaf) => match leaf { 179 tt::TokenTree::Leaf(leaf) => match leaf {
101 tt::Leaf::Punct(punct) => { 180 tt::Leaf::Punct(punct) => {
102 static UNDERSCORE: SmolStr = SmolStr::new_inline("_"); 181 static UNDERSCORE: SmolStr = SmolStr::new_inline("_");
103 182
104 if punct.char != '_' { 183 if punct.char != '_' {
105 return Err(ExpandError::UnexpectedToken); 184 return Err(ParseError::Expected("_".to_string()));
106 } 185 }
107 let name = UNDERSCORE.clone(); 186 let name = UNDERSCORE.clone();
108 let kind = eat_fragment_kind(src, mode)?; 187 let kind = eat_fragment_kind(src, mode)?;
@@ -134,16 +213,15 @@ fn next_op<'a>(first: &tt::TokenTree, src: &mut TtIter<'a>, mode: Mode) -> Resul
134 } 213 }
135 tt::TokenTree::Leaf(tt) => Op::Leaf(tt.clone()), 214 tt::TokenTree::Leaf(tt) => Op::Leaf(tt.clone()),
136 tt::TokenTree::Subtree(subtree) => { 215 tt::TokenTree::Subtree(subtree) => {
137 let delimiter = subtree.delimiter; 216 let tokens =
138 let tokens = parse_inner(&subtree, mode); 217 parse_inner(&subtree, mode).into_iter().collect::<Result<Vec<Op>, ParseError>>()?;
139 let subtree = MetaTemplate { tokens, delimiter }; 218 Op::Subtree { tokens: MetaTemplate(tokens), delimiter: subtree.delimiter }
140 Op::Subtree(subtree)
141 } 219 }
142 }; 220 };
143 Ok(res) 221 Ok(res)
144} 222}
145 223
146fn eat_fragment_kind<'a>(src: &mut TtIter<'a>, mode: Mode) -> Result<Option<SmolStr>, ExpandError> { 224fn eat_fragment_kind<'a>(src: &mut TtIter<'a>, mode: Mode) -> Result<Option<SmolStr>, ParseError> {
147 if let Mode::Pattern = mode { 225 if let Mode::Pattern = mode {
148 src.expect_char(':').map_err(|()| err!("bad fragment specifier 1"))?; 226 src.expect_char(':').map_err(|()| err!("bad fragment specifier 1"))?;
149 let ident = src.expect_ident().map_err(|()| err!("bad fragment specifier 1"))?; 227 let ident = src.expect_ident().map_err(|()| err!("bad fragment specifier 1"))?;
@@ -156,12 +234,12 @@ fn is_boolean_literal(lit: &tt::Literal) -> bool {
156 matches!(lit.text.as_str(), "true" | "false") 234 matches!(lit.text.as_str(), "true" | "false")
157} 235}
158 236
159fn parse_repeat(src: &mut TtIter) -> Result<(Option<Separator>, RepeatKind), ExpandError> { 237fn parse_repeat(src: &mut TtIter) -> Result<(Option<Separator>, RepeatKind), ParseError> {
160 let mut separator = Separator::Puncts(SmallVec::new()); 238 let mut separator = Separator::Puncts(SmallVec::new());
161 for tt in src { 239 for tt in src {
162 let tt = match tt { 240 let tt = match tt {
163 tt::TokenTree::Leaf(leaf) => leaf, 241 tt::TokenTree::Leaf(leaf) => leaf,
164 tt::TokenTree::Subtree(_) => return Err(ExpandError::InvalidRepeat), 242 tt::TokenTree::Subtree(_) => return Err(ParseError::InvalidRepeat),
165 }; 243 };
166 let has_sep = match &separator { 244 let has_sep = match &separator {
167 Separator::Puncts(puncts) => !puncts.is_empty(), 245 Separator::Puncts(puncts) => !puncts.is_empty(),
@@ -169,7 +247,7 @@ fn parse_repeat(src: &mut TtIter) -> Result<(Option<Separator>, RepeatKind), Exp
169 }; 247 };
170 match tt { 248 match tt {
171 tt::Leaf::Ident(_) | tt::Leaf::Literal(_) if has_sep => { 249 tt::Leaf::Ident(_) | tt::Leaf::Literal(_) if has_sep => {
172 return Err(ExpandError::InvalidRepeat) 250 return Err(ParseError::InvalidRepeat)
173 } 251 }
174 tt::Leaf::Ident(ident) => separator = Separator::Ident(ident.clone()), 252 tt::Leaf::Ident(ident) => separator = Separator::Ident(ident.clone()),
175 tt::Leaf::Literal(lit) => separator = Separator::Literal(lit.clone()), 253 tt::Leaf::Literal(lit) => separator = Separator::Literal(lit.clone()),
@@ -182,11 +260,11 @@ fn parse_repeat(src: &mut TtIter) -> Result<(Option<Separator>, RepeatKind), Exp
182 match &mut separator { 260 match &mut separator {
183 Separator::Puncts(puncts) => { 261 Separator::Puncts(puncts) => {
184 if puncts.len() == 3 { 262 if puncts.len() == 3 {
185 return Err(ExpandError::InvalidRepeat); 263 return Err(ParseError::InvalidRepeat);
186 } 264 }
187 puncts.push(punct.clone()) 265 puncts.push(punct.clone())
188 } 266 }
189 _ => return Err(ExpandError::InvalidRepeat), 267 _ => return Err(ParseError::InvalidRepeat),
190 } 268 }
191 continue; 269 continue;
192 } 270 }
@@ -196,5 +274,5 @@ fn parse_repeat(src: &mut TtIter) -> Result<(Option<Separator>, RepeatKind), Exp
196 } 274 }
197 } 275 }
198 } 276 }
199 Err(ExpandError::InvalidRepeat) 277 Err(ParseError::InvalidRepeat)
200} 278}
diff --git a/crates/mbe/src/syntax_bridge.rs b/crates/mbe/src/syntax_bridge.rs
index 2a41d8167..aacae1026 100644
--- a/crates/mbe/src/syntax_bridge.rs
+++ b/crates/mbe/src/syntax_bridge.rs
@@ -10,22 +10,24 @@ use syntax::{
10}; 10};
11use tt::buffer::{Cursor, TokenBuffer}; 11use tt::buffer::{Cursor, TokenBuffer};
12 12
13use crate::subtree_source::SubtreeTokenSource;
14use crate::ExpandError; 13use crate::ExpandError;
14use crate::{subtree_source::SubtreeTokenSource, tt_iter::TtIter};
15 15
16#[derive(Debug, PartialEq, Eq, Clone, Copy)] 16#[derive(Debug, PartialEq, Eq, Clone, Copy)]
17pub enum TokenTextRange { 17pub enum TokenTextRange {
18 Token(TextRange), 18 Token(TextRange),
19 Delimiter(TextRange, TextRange), 19 Delimiter(TextRange),
20} 20}
21 21
22impl TokenTextRange { 22impl TokenTextRange {
23 pub fn by_kind(self, kind: SyntaxKind) -> Option<TextRange> { 23 pub fn by_kind(self, kind: SyntaxKind) -> Option<TextRange> {
24 match self { 24 match self {
25 TokenTextRange::Token(it) => Some(it), 25 TokenTextRange::Token(it) => Some(it),
26 TokenTextRange::Delimiter(open, close) => match kind { 26 TokenTextRange::Delimiter(it) => match kind {
27 T!['{'] | T!['('] | T!['['] => Some(open), 27 T!['{'] | T!['('] | T!['['] => Some(TextRange::at(it.start(), 1.into())),
28 T!['}'] | T![')'] | T![']'] => Some(close), 28 T!['}'] | T![')'] | T![']'] => {
29 Some(TextRange::at(it.end() - TextSize::of('}'), 1.into()))
30 }
29 _ => None, 31 _ => None,
30 }, 32 },
31 } 33 }
@@ -110,12 +112,51 @@ pub fn parse_to_token_tree(text: &str) -> Option<(tt::Subtree, TokenMap)> {
110 Some((subtree, conv.id_alloc.map)) 112 Some((subtree, conv.id_alloc.map))
111} 113}
112 114
115/// Split token tree with seperate expr: $($e:expr)SEP*
116pub fn parse_exprs_with_sep(tt: &tt::Subtree, sep: char) -> Vec<tt::Subtree> {
117 if tt.token_trees.is_empty() {
118 return Vec::new();
119 }
120
121 let mut iter = TtIter::new(tt);
122 let mut res = Vec::new();
123
124 while iter.peek_n(0).is_some() {
125 let expanded = iter.expect_fragment(FragmentKind::Expr);
126 if expanded.err.is_some() {
127 break;
128 }
129
130 res.push(match expanded.value {
131 None => break,
132 Some(tt @ tt::TokenTree::Leaf(_)) => {
133 tt::Subtree { delimiter: None, token_trees: vec![tt.into()] }
134 }
135 Some(tt::TokenTree::Subtree(tt)) => tt,
136 });
137
138 let mut fork = iter.clone();
139 if fork.expect_char(sep).is_err() {
140 break;
141 }
142 iter = fork;
143 }
144
145 if iter.peek_n(0).is_some() {
146 res.push(tt::Subtree { delimiter: None, token_trees: iter.into_iter().cloned().collect() });
147 }
148
149 res
150}
151
113impl TokenMap { 152impl TokenMap {
114 pub fn token_by_range(&self, relative_range: TextRange) -> Option<tt::TokenId> { 153 pub fn token_by_range(&self, relative_range: TextRange) -> Option<tt::TokenId> {
115 let &(token_id, _) = self.entries.iter().find(|(_, range)| match range { 154 let &(token_id, _) = self.entries.iter().find(|(_, range)| match range {
116 TokenTextRange::Token(it) => *it == relative_range, 155 TokenTextRange::Token(it) => *it == relative_range,
117 TokenTextRange::Delimiter(open, close) => { 156 TokenTextRange::Delimiter(it) => {
118 *open == relative_range || *close == relative_range 157 let open = TextRange::at(it.start(), 1.into());
158 let close = TextRange::at(it.end() - TextSize::of('}'), 1.into());
159 open == relative_range || close == relative_range
119 } 160 }
120 })?; 161 })?;
121 Some(token_id) 162 Some(token_id)
@@ -137,15 +178,17 @@ impl TokenMap {
137 close_relative_range: TextRange, 178 close_relative_range: TextRange,
138 ) -> usize { 179 ) -> usize {
139 let res = self.entries.len(); 180 let res = self.entries.len();
140 self.entries 181 let cover = open_relative_range.cover(close_relative_range);
141 .push((token_id, TokenTextRange::Delimiter(open_relative_range, close_relative_range))); 182
183 self.entries.push((token_id, TokenTextRange::Delimiter(cover)));
142 res 184 res
143 } 185 }
144 186
145 fn update_close_delim(&mut self, idx: usize, close_relative_range: TextRange) { 187 fn update_close_delim(&mut self, idx: usize, close_relative_range: TextRange) {
146 let (_, token_text_range) = &mut self.entries[idx]; 188 let (_, token_text_range) = &mut self.entries[idx];
147 if let TokenTextRange::Delimiter(dim, _) = token_text_range { 189 if let TokenTextRange::Delimiter(dim) = token_text_range {
148 *token_text_range = TokenTextRange::Delimiter(*dim, close_relative_range); 190 let cover = dim.cover(close_relative_range);
191 *token_text_range = TokenTextRange::Delimiter(cover);
149 } 192 }
150 } 193 }
151 194
@@ -170,7 +213,7 @@ fn doc_comment_text(comment: &ast::Comment) -> SmolStr {
170 213
171 // Quote the string 214 // Quote the string
172 // Note that `tt::Literal` expect an escaped string 215 // Note that `tt::Literal` expect an escaped string
173 let text = format!("{:?}", text.escape_default().to_string()); 216 let text = format!("{:?}", text.escape_debug().to_string());
174 text.into() 217 text.into()
175} 218}
176 219
@@ -501,7 +544,7 @@ impl SrcToken for SynToken {
501 } 544 }
502 } 545 }
503 fn to_text(&self) -> SmolStr { 546 fn to_text(&self) -> SmolStr {
504 self.token().text().clone() 547 self.token().text().into()
505 } 548 }
506} 549}
507 550
@@ -676,10 +719,8 @@ impl<'a> TreeSink for TtTreeSink<'a> {
676 self.text_pos += TextSize::of(text); 719 self.text_pos += TextSize::of(text);
677 } 720 }
678 721
679 let text = SmolStr::new(self.buf.as_str()); 722 self.inner.token(kind, self.buf.as_str());
680 self.buf.clear(); 723 self.buf.clear();
681 self.inner.token(kind, text);
682
683 // Add whitespace between adjoint puncts 724 // Add whitespace between adjoint puncts
684 let next = last.bump(); 725 let next = last.bump();
685 if let ( 726 if let (
diff --git a/crates/mbe/src/tests.rs b/crates/mbe/src/tests.rs
index bd2977ebd..5c641ebf2 100644
--- a/crates/mbe/src/tests.rs
+++ b/crates/mbe/src/tests.rs
@@ -6,7 +6,7 @@ use syntax::{
6 SyntaxKind::{ERROR, IDENT}, 6 SyntaxKind::{ERROR, IDENT},
7 SyntaxNode, WalkEvent, T, 7 SyntaxNode, WalkEvent, T,
8}; 8};
9use test_utils::assert_eq_text; 9use test_utils::{assert_eq_text, mark};
10 10
11use super::*; 11use super::*;
12 12
@@ -33,19 +33,18 @@ mod rule_parsing {
33 33
34 #[test] 34 #[test]
35 fn test_invalid_arms() { 35 fn test_invalid_arms() {
36 fn check(macro_body: &str, err: &str) { 36 fn check(macro_body: &str, err: ParseError) {
37 let m = parse_macro_arm(macro_body); 37 let m = parse_macro_arm(macro_body);
38 assert_eq!(m, Err(ParseError::Expected(String::from(err)))); 38 assert_eq!(m, Err(err.into()));
39 } 39 }
40 check("invalid", ParseError::Expected("expected subtree".into()));
40 41
41 check("invalid", "expected subtree"); 42 check("$i:ident => ()", ParseError::Expected("expected subtree".into()));
43 check("($i:ident) ()", ParseError::Expected("expected `=`".into()));
44 check("($($i:ident)_) => ()", ParseError::InvalidRepeat);
42 45
43 check("$i:ident => ()", "expected subtree"); 46 check("($i) => ($i)", ParseError::UnexpectedToken("bad fragment specifier 1".into()));
44 check("($i:ident) ()", "expected `=`"); 47 check("($i:) => ($i)", ParseError::UnexpectedToken("bad fragment specifier 1".into()));
45 check("($($i:ident)_) => ()", "invalid repeat");
46
47 check("($i) => ($i)", "invalid macro definition");
48 check("($i:) => ($i)", "invalid macro definition");
49 } 48 }
50 49
51 fn parse_macro_arm(arm_definition: &str) -> Result<crate::MacroRules, ParseError> { 50 fn parse_macro_arm(arm_definition: &str) -> Result<crate::MacroRules, ParseError> {
@@ -458,6 +457,17 @@ fn test_match_group_with_multichar_sep() {
458} 457}
459 458
460#[test] 459#[test]
460fn test_match_group_with_multichar_sep2() {
461 parse_macro(
462 r#"
463 macro_rules! foo {
464 (fn $name:ident {$($i:literal)&&*} ) => ( fn $name() -> bool { $($i)&&*} );
465 }"#,
466 )
467 .assert_expand_items("foo! (fn baz {true && true} );", "fn baz () -> bool {true &&true}");
468}
469
470#[test]
461fn test_match_group_zero_match() { 471fn test_match_group_zero_match() {
462 parse_macro( 472 parse_macro(
463 r#" 473 r#"
@@ -675,6 +685,36 @@ fn test_match_literal() {
675 .assert_expand_items("foo! ['('];", "fn foo () {}"); 685 .assert_expand_items("foo! ['('];", "fn foo () {}");
676} 686}
677 687
688#[test]
689fn test_parse_macro_def_simple() {
690 mark::check!(parse_macro_def_simple);
691
692 parse_macro2(
693 r#"
694macro foo($id:ident) {
695 fn $id() {}
696}
697"#,
698 )
699 .assert_expand_items("foo!(bar);", "fn bar () {}");
700}
701
702#[test]
703fn test_parse_macro_def_rules() {
704 mark::check!(parse_macro_def_rules);
705
706 parse_macro2(
707 r#"
708macro foo {
709 ($id:ident) => {
710 fn $id() {}
711 }
712}
713"#,
714 )
715 .assert_expand_items("foo!(bar);", "fn bar () {}");
716}
717
678// The following tests are port from intellij-rust directly 718// The following tests are port from intellij-rust directly
679// https://github.com/intellij-rust/intellij-rust/blob/c4e9feee4ad46e7953b1948c112533360b6087bb/src/test/kotlin/org/rust/lang/core/macros/RsMacroExpansionTest.kt 719// https://github.com/intellij-rust/intellij-rust/blob/c4e9feee4ad46e7953b1948c112533360b6087bb/src/test/kotlin/org/rust/lang/core/macros/RsMacroExpansionTest.kt
680 720
@@ -941,6 +981,29 @@ fn test_meta_doc_comments() {
941} 981}
942 982
943#[test] 983#[test]
984fn test_meta_doc_comments_non_latin() {
985 parse_macro(
986 r#"
987 macro_rules! foo {
988 ($(#[$ i:meta])+) => (
989 $(#[$ i])+
990 fn bar() {}
991 )
992 }
993"#,
994 ).
995 assert_expand_items(
996 r#"foo! {
997 /// 錦瑟無端五十弦,一弦一柱思華年。
998 /**
999 莊生曉夢迷蝴蝶,望帝春心託杜鵑。
1000 */
1001 }"#,
1002 "# [doc = \" 錦瑟無端五十弦,一弦一柱思華年。\"] # [doc = \"\\\\n 莊生曉夢迷蝴蝶,望帝春心託杜鵑。\\\\n \"] fn bar () {}",
1003 );
1004}
1005
1006#[test]
944fn test_tt_block() { 1007fn test_tt_block() {
945 parse_macro( 1008 parse_macro(
946 r#" 1009 r#"
@@ -1215,6 +1278,18 @@ macro_rules! m {
1215 .is_some()); 1278 .is_some());
1216} 1279}
1217 1280
1281#[test]
1282fn test_match_is_not_greedy() {
1283 parse_macro(
1284 r#"
1285macro_rules! foo {
1286 ($($i:ident $(,)*),*) => {};
1287}
1288"#,
1289 )
1290 .assert_expand_items(r#"foo!(a,b);"#, r#""#);
1291}
1292
1218// The following tests are based on real world situations 1293// The following tests are based on real world situations
1219#[test] 1294#[test]
1220fn test_vec() { 1295fn test_vec() {
@@ -1699,95 +1774,122 @@ pub(crate) struct MacroFixture {
1699 rules: MacroRules, 1774 rules: MacroRules,
1700} 1775}
1701 1776
1702impl MacroFixture { 1777pub(crate) struct MacroFixture2 {
1703 pub(crate) fn expand_tt(&self, invocation: &str) -> tt::Subtree { 1778 rules: MacroDef,
1704 self.try_expand_tt(invocation).unwrap() 1779}
1705 }
1706
1707 fn try_expand_tt(&self, invocation: &str) -> Result<tt::Subtree, ExpandError> {
1708 let source_file = ast::SourceFile::parse(invocation).tree();
1709 let macro_invocation =
1710 source_file.syntax().descendants().find_map(ast::MacroCall::cast).unwrap();
1711
1712 let (invocation_tt, _) = ast_to_token_tree(&macro_invocation.token_tree().unwrap())
1713 .ok_or_else(|| ExpandError::ConversionError)?;
1714 1780
1715 self.rules.expand(&invocation_tt).result() 1781macro_rules! impl_fixture {
1716 } 1782 ($name:ident) => {
1783 impl $name {
1784 pub(crate) fn expand_tt(&self, invocation: &str) -> tt::Subtree {
1785 self.try_expand_tt(invocation).unwrap()
1786 }
1717 1787
1718 fn assert_expand_err(&self, invocation: &str, err: &ExpandError) { 1788 fn try_expand_tt(&self, invocation: &str) -> Result<tt::Subtree, ExpandError> {
1719 assert_eq!(self.try_expand_tt(invocation).as_ref(), Err(err)); 1789 let source_file = ast::SourceFile::parse(invocation).tree();
1720 } 1790 let macro_invocation =
1791 source_file.syntax().descendants().find_map(ast::MacroCall::cast).unwrap();
1721 1792
1722 fn expand_items(&self, invocation: &str) -> SyntaxNode { 1793 let (invocation_tt, _) = ast_to_token_tree(&macro_invocation.token_tree().unwrap())
1723 let expanded = self.expand_tt(invocation); 1794 .ok_or_else(|| ExpandError::ConversionError)?;
1724 token_tree_to_syntax_node(&expanded, FragmentKind::Items).unwrap().0.syntax_node()
1725 }
1726 1795
1727 fn expand_statements(&self, invocation: &str) -> SyntaxNode { 1796 self.rules.expand(&invocation_tt).result()
1728 let expanded = self.expand_tt(invocation); 1797 }
1729 token_tree_to_syntax_node(&expanded, FragmentKind::Statements).unwrap().0.syntax_node()
1730 }
1731 1798
1732 fn expand_expr(&self, invocation: &str) -> SyntaxNode { 1799 #[allow(unused)]
1733 let expanded = self.expand_tt(invocation); 1800 fn assert_expand_err(&self, invocation: &str, err: &ExpandError) {
1734 token_tree_to_syntax_node(&expanded, FragmentKind::Expr).unwrap().0.syntax_node() 1801 assert_eq!(self.try_expand_tt(invocation).as_ref(), Err(err));
1735 } 1802 }
1736 1803
1737 fn assert_expand_tt(&self, invocation: &str, expected: &str) { 1804 #[allow(unused)]
1738 let expansion = self.expand_tt(invocation); 1805 fn expand_items(&self, invocation: &str) -> SyntaxNode {
1739 assert_eq!(expansion.to_string(), expected); 1806 let expanded = self.expand_tt(invocation);
1740 } 1807 token_tree_to_syntax_node(&expanded, FragmentKind::Items).unwrap().0.syntax_node()
1808 }
1741 1809
1742 fn assert_expand(&self, invocation: &str, expected: &str) { 1810 #[allow(unused)]
1743 let expansion = self.expand_tt(invocation); 1811 fn expand_statements(&self, invocation: &str) -> SyntaxNode {
1744 let actual = format!("{:?}", expansion); 1812 let expanded = self.expand_tt(invocation);
1745 test_utils::assert_eq_text!(&expected.trim(), &actual.trim()); 1813 token_tree_to_syntax_node(&expanded, FragmentKind::Statements)
1746 } 1814 .unwrap()
1815 .0
1816 .syntax_node()
1817 }
1747 1818
1748 fn assert_expand_items(&self, invocation: &str, expected: &str) -> &MacroFixture { 1819 #[allow(unused)]
1749 self.assert_expansion(FragmentKind::Items, invocation, expected); 1820 fn expand_expr(&self, invocation: &str) -> SyntaxNode {
1750 self 1821 let expanded = self.expand_tt(invocation);
1751 } 1822 token_tree_to_syntax_node(&expanded, FragmentKind::Expr).unwrap().0.syntax_node()
1823 }
1752 1824
1753 fn assert_expand_statements(&self, invocation: &str, expected: &str) -> &MacroFixture { 1825 #[allow(unused)]
1754 self.assert_expansion(FragmentKind::Statements, invocation, expected); 1826 fn assert_expand_tt(&self, invocation: &str, expected: &str) {
1755 self 1827 let expansion = self.expand_tt(invocation);
1756 } 1828 assert_eq!(expansion.to_string(), expected);
1829 }
1757 1830
1758 fn assert_expansion(&self, kind: FragmentKind, invocation: &str, expected: &str) { 1831 #[allow(unused)]
1759 let expanded = self.expand_tt(invocation); 1832 fn assert_expand(&self, invocation: &str, expected: &str) {
1760 assert_eq!(expanded.to_string(), expected); 1833 let expansion = self.expand_tt(invocation);
1761 1834 let actual = format!("{:?}", expansion);
1762 let expected = expected.replace("$crate", "C_C__C"); 1835 test_utils::assert_eq_text!(&expected.trim(), &actual.trim());
1763 1836 }
1764 // wrap the given text to a macro call
1765 let expected = {
1766 let wrapped = format!("wrap_macro!( {} )", expected);
1767 let wrapped = ast::SourceFile::parse(&wrapped);
1768 let wrapped =
1769 wrapped.tree().syntax().descendants().find_map(ast::TokenTree::cast).unwrap();
1770 let mut wrapped = ast_to_token_tree(&wrapped).unwrap().0;
1771 wrapped.delimiter = None;
1772 wrapped
1773 };
1774 1837
1775 let expanded_tree = token_tree_to_syntax_node(&expanded, kind).unwrap().0.syntax_node(); 1838 fn assert_expand_items(&self, invocation: &str, expected: &str) -> &$name {
1776 let expanded_tree = debug_dump_ignore_spaces(&expanded_tree).trim().to_string(); 1839 self.assert_expansion(FragmentKind::Items, invocation, expected);
1840 self
1841 }
1777 1842
1778 let expected_tree = token_tree_to_syntax_node(&expected, kind).unwrap().0.syntax_node(); 1843 #[allow(unused)]
1779 let expected_tree = debug_dump_ignore_spaces(&expected_tree).trim().to_string(); 1844 fn assert_expand_statements(&self, invocation: &str, expected: &str) -> &$name {
1845 self.assert_expansion(FragmentKind::Statements, invocation, expected);
1846 self
1847 }
1780 1848
1781 let expected_tree = expected_tree.replace("C_C__C", "$crate"); 1849 fn assert_expansion(&self, kind: FragmentKind, invocation: &str, expected: &str) {
1782 assert_eq!( 1850 let expanded = self.expand_tt(invocation);
1783 expanded_tree, expected_tree, 1851 assert_eq!(expanded.to_string(), expected);
1784 "\nleft:\n{}\nright:\n{}", 1852
1785 expanded_tree, expected_tree, 1853 let expected = expected.replace("$crate", "C_C__C");
1786 ); 1854
1787 } 1855 // wrap the given text to a macro call
1856 let expected = {
1857 let wrapped = format!("wrap_macro!( {} )", expected);
1858 let wrapped = ast::SourceFile::parse(&wrapped);
1859 let wrapped = wrapped
1860 .tree()
1861 .syntax()
1862 .descendants()
1863 .find_map(ast::TokenTree::cast)
1864 .unwrap();
1865 let mut wrapped = ast_to_token_tree(&wrapped).unwrap().0;
1866 wrapped.delimiter = None;
1867 wrapped
1868 };
1869
1870 let expanded_tree =
1871 token_tree_to_syntax_node(&expanded, kind).unwrap().0.syntax_node();
1872 let expanded_tree = debug_dump_ignore_spaces(&expanded_tree).trim().to_string();
1873
1874 let expected_tree =
1875 token_tree_to_syntax_node(&expected, kind).unwrap().0.syntax_node();
1876 let expected_tree = debug_dump_ignore_spaces(&expected_tree).trim().to_string();
1877
1878 let expected_tree = expected_tree.replace("C_C__C", "$crate");
1879 assert_eq!(
1880 expanded_tree, expected_tree,
1881 "\nleft:\n{}\nright:\n{}",
1882 expanded_tree, expected_tree,
1883 );
1884 }
1885 }
1886 };
1788} 1887}
1789 1888
1790fn parse_macro_to_tt(ra_fixture: &str) -> tt::Subtree { 1889impl_fixture!(MacroFixture);
1890impl_fixture!(MacroFixture2);
1891
1892fn parse_macro_rules_to_tt(ra_fixture: &str) -> tt::Subtree {
1791 let source_file = ast::SourceFile::parse(ra_fixture).ok().unwrap(); 1893 let source_file = ast::SourceFile::parse(ra_fixture).ok().unwrap();
1792 let macro_definition = 1894 let macro_definition =
1793 source_file.syntax().descendants().find_map(ast::MacroRules::cast).unwrap(); 1895 source_file.syntax().descendants().find_map(ast::MacroRules::cast).unwrap();
@@ -1804,14 +1906,36 @@ fn parse_macro_to_tt(ra_fixture: &str) -> tt::Subtree {
1804 definition_tt 1906 definition_tt
1805} 1907}
1806 1908
1909fn parse_macro_def_to_tt(ra_fixture: &str) -> tt::Subtree {
1910 let source_file = ast::SourceFile::parse(ra_fixture).ok().unwrap();
1911 let macro_definition =
1912 source_file.syntax().descendants().find_map(ast::MacroDef::cast).unwrap();
1913
1914 let (definition_tt, _) = ast_to_token_tree(&macro_definition.body().unwrap()).unwrap();
1915
1916 let parsed =
1917 parse_to_token_tree(&ra_fixture[macro_definition.body().unwrap().syntax().text_range()])
1918 .unwrap()
1919 .0;
1920 assert_eq!(definition_tt, parsed);
1921
1922 definition_tt
1923}
1924
1807pub(crate) fn parse_macro(ra_fixture: &str) -> MacroFixture { 1925pub(crate) fn parse_macro(ra_fixture: &str) -> MacroFixture {
1808 let definition_tt = parse_macro_to_tt(ra_fixture); 1926 let definition_tt = parse_macro_rules_to_tt(ra_fixture);
1809 let rules = MacroRules::parse(&definition_tt).unwrap(); 1927 let rules = MacroRules::parse(&definition_tt).unwrap();
1810 MacroFixture { rules } 1928 MacroFixture { rules }
1811} 1929}
1812 1930
1931pub(crate) fn parse_macro2(ra_fixture: &str) -> MacroFixture2 {
1932 let definition_tt = parse_macro_def_to_tt(ra_fixture);
1933 let rules = MacroDef::parse(&definition_tt).unwrap();
1934 MacroFixture2 { rules }
1935}
1936
1813pub(crate) fn parse_macro_error(ra_fixture: &str) -> ParseError { 1937pub(crate) fn parse_macro_error(ra_fixture: &str) -> ParseError {
1814 let definition_tt = parse_macro_to_tt(ra_fixture); 1938 let definition_tt = parse_macro_rules_to_tt(ra_fixture);
1815 1939
1816 match MacroRules::parse(&definition_tt) { 1940 match MacroRules::parse(&definition_tt) {
1817 Ok(_) => panic!("Expect error"), 1941 Ok(_) => panic!("Expect error"),
diff --git a/crates/mbe/src/tt_iter.rs b/crates/mbe/src/tt_iter.rs
index 46c420718..a362d31fc 100644
--- a/crates/mbe/src/tt_iter.rs
+++ b/crates/mbe/src/tt_iter.rs
@@ -1,5 +1,20 @@
1//! FIXME: write short doc here 1//! FIXME: write short doc here
2 2
3use crate::{subtree_source::SubtreeTokenSource, ExpandError, ExpandResult};
4
5use parser::TreeSink;
6use syntax::SyntaxKind;
7use tt::buffer::{Cursor, TokenBuffer};
8
9macro_rules! err {
10 () => {
11 ExpandError::BindingError(format!(""))
12 };
13 ($($tt:tt)*) => {
14 ExpandError::BindingError(format!($($tt)*))
15 };
16}
17
3#[derive(Debug, Clone)] 18#[derive(Debug, Clone)]
4pub(crate) struct TtIter<'a> { 19pub(crate) struct TtIter<'a> {
5 pub(crate) inner: std::slice::Iter<'a, tt::TokenTree>, 20 pub(crate) inner: std::slice::Iter<'a, tt::TokenTree>,
@@ -56,6 +71,68 @@ impl<'a> TtIter<'a> {
56 } 71 }
57 } 72 }
58 73
74 pub(crate) fn expect_fragment(
75 &mut self,
76 fragment_kind: parser::FragmentKind,
77 ) -> ExpandResult<Option<tt::TokenTree>> {
78 struct OffsetTokenSink<'a> {
79 cursor: Cursor<'a>,
80 error: bool,
81 }
82
83 impl<'a> TreeSink for OffsetTokenSink<'a> {
84 fn token(&mut self, kind: SyntaxKind, mut n_tokens: u8) {
85 if kind == SyntaxKind::LIFETIME_IDENT {
86 n_tokens = 2;
87 }
88 for _ in 0..n_tokens {
89 self.cursor = self.cursor.bump_subtree();
90 }
91 }
92 fn start_node(&mut self, _kind: SyntaxKind) {}
93 fn finish_node(&mut self) {}
94 fn error(&mut self, _error: parser::ParseError) {
95 self.error = true;
96 }
97 }
98
99 let buffer = TokenBuffer::from_tokens(&self.inner.as_slice());
100 let mut src = SubtreeTokenSource::new(&buffer);
101 let mut sink = OffsetTokenSink { cursor: buffer.begin(), error: false };
102
103 parser::parse_fragment(&mut src, &mut sink, fragment_kind);
104
105 let mut err = None;
106 if !sink.cursor.is_root() || sink.error {
107 err = Some(err!("expected {:?}", fragment_kind));
108 }
109
110 let mut curr = buffer.begin();
111 let mut res = vec![];
112
113 if sink.cursor.is_root() {
114 while curr != sink.cursor {
115 if let Some(token) = curr.token_tree() {
116 res.push(token);
117 }
118 curr = curr.bump();
119 }
120 }
121 self.inner = self.inner.as_slice()[res.len()..].iter();
122 if res.len() == 0 && err.is_none() {
123 err = Some(err!("no tokens consumed"));
124 }
125 let res = match res.len() {
126 1 => Some(res[0].cloned()),
127 0 => None,
128 _ => Some(tt::TokenTree::Subtree(tt::Subtree {
129 delimiter: None,
130 token_trees: res.into_iter().map(|it| it.cloned()).collect(),
131 })),
132 };
133 ExpandResult { value: res, err }
134 }
135
59 pub(crate) fn peek_n(&self, n: usize) -> Option<&tt::TokenTree> { 136 pub(crate) fn peek_n(&self, n: usize) -> Option<&tt::TokenTree> {
60 self.inner.as_slice().get(n) 137 self.inner.as_slice().get(n)
61 } 138 }