diff options
author | bors[bot] <26634292+bors[bot]@users.noreply.github.com> | 2021-01-29 12:24:38 +0000 |
---|---|---|
committer | GitHub <[email protected]> | 2021-01-29 12:24:38 +0000 |
commit | 3ecd5112bbc2cc1a45f423e0256230507f159162 (patch) | |
tree | 012ff5ebc1cedb761dac87f5d05744603b1cc663 /crates/mbe/src/expander/matcher.rs | |
parent | 0ac4a8f35497718a5d17f74e0dd3ef36227222cc (diff) | |
parent | 4c7d8cbfbfd2d93008c1266eb45c2671bd49b60e (diff) |
Merge #7488
7488: Rename mbe_expander for consistency r=edwin0cheng a=edwin0cheng
bors r+
Co-authored-by: Edwin Cheng <[email protected]>
Diffstat (limited to 'crates/mbe/src/expander/matcher.rs')
-rw-r--r-- | crates/mbe/src/expander/matcher.rs | 502 |
1 files changed, 502 insertions, 0 deletions
diff --git a/crates/mbe/src/expander/matcher.rs b/crates/mbe/src/expander/matcher.rs new file mode 100644 index 000000000..5b5845850 --- /dev/null +++ b/crates/mbe/src/expander/matcher.rs | |||
@@ -0,0 +1,502 @@ | |||
1 | //! FIXME: write short doc here | ||
2 | |||
3 | use crate::{ | ||
4 | expander::{Binding, Bindings, Fragment}, | ||
5 | parser::{Op, RepeatKind, Separator}, | ||
6 | subtree_source::SubtreeTokenSource, | ||
7 | tt_iter::TtIter, | ||
8 | ExpandError, MetaTemplate, | ||
9 | }; | ||
10 | |||
11 | use super::ExpandResult; | ||
12 | use parser::{FragmentKind::*, TreeSink}; | ||
13 | use syntax::{SmolStr, SyntaxKind}; | ||
14 | use tt::buffer::{Cursor, TokenBuffer}; | ||
15 | |||
16 | impl 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 | |||
53 | macro_rules! err { | ||
54 | () => { | ||
55 | ExpandError::BindingError(format!("")) | ||
56 | }; | ||
57 | ($($tt:tt)*) => { | ||
58 | ExpandError::BindingError(format!($($tt)*)) | ||
59 | }; | ||
60 | } | ||
61 | |||
62 | #[derive(Debug, Default)] | ||
63 | pub(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 | |||
72 | impl 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 | |||
86 | pub(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 | |||
102 | fn 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 | |||
182 | impl<'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 | |||
373 | pub(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 | |||
441 | fn 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 | |||
492 | fn 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 | } | ||