aboutsummaryrefslogtreecommitdiff
path: root/crates/mbe
diff options
context:
space:
mode:
authorEdwin Cheng <[email protected]>2021-03-13 12:17:54 +0000
committerEdwin Cheng <[email protected]>2021-03-13 12:52:36 +0000
commit9117148f42371108f49de84ff765da987dcb5917 (patch)
treea45a4b895303104bdedfde27e27efb9bac4fb442 /crates/mbe
parentf1350dd93c92fa5e71b6c5d7f703fe19c2511e06 (diff)
Add bindings builder for speed up matching
Diffstat (limited to 'crates/mbe')
-rw-r--r--crates/mbe/src/expander.rs4
-rw-r--r--crates/mbe/src/expander/matcher.rs272
-rw-r--r--crates/mbe/src/expander/transcriber.rs12
3 files changed, 221 insertions, 67 deletions
diff --git a/crates/mbe/src/expander.rs b/crates/mbe/src/expander.rs
index 2efff8f52..3197c834c 100644
--- a/crates/mbe/src/expander.rs
+++ b/crates/mbe/src/expander.rs
@@ -5,7 +5,7 @@
5mod matcher; 5mod matcher;
6mod transcriber; 6mod transcriber;
7 7
8use smallvec::SmallVec; 8use rustc_hash::FxHashMap;
9use syntax::SmolStr; 9use syntax::SmolStr;
10 10
11use crate::{ExpandError, ExpandResult}; 11use crate::{ExpandError, ExpandResult};
@@ -96,7 +96,7 @@ pub(crate) fn expand_rules(
96/// many is not a plain `usize`, but an `&[usize]`. 96/// many is not a plain `usize`, but an `&[usize]`.
97#[derive(Debug, Default, Clone, PartialEq, Eq)] 97#[derive(Debug, Default, Clone, PartialEq, Eq)]
98struct Bindings { 98struct Bindings {
99 inner: SmallVec<[(SmolStr, Binding); 4]>, 99 inner: FxHashMap<SmolStr, Binding>,
100} 100}
101 101
102#[derive(Debug, Clone, PartialEq, Eq)] 102#[derive(Debug, Clone, PartialEq, Eq)]
diff --git a/crates/mbe/src/expander/matcher.rs b/crates/mbe/src/expander/matcher.rs
index 9d3d28055..54db76d5d 100644
--- a/crates/mbe/src/expander/matcher.rs
+++ b/crates/mbe/src/expander/matcher.rs
@@ -59,6 +59,8 @@
59//! eof: [a $( a )* a b ·] 59//! eof: [a $( a )* a b ·]
60//! ``` 60//! ```
61 61
62use std::rc::Rc;
63
62use crate::{ 64use crate::{
63 expander::{Binding, Bindings, Fragment}, 65 expander::{Binding, Bindings, Fragment},
64 parser::{Op, OpDelimited, OpDelimitedIter, RepeatKind, Separator}, 66 parser::{Op, OpDelimited, OpDelimitedIter, RepeatKind, Separator},
@@ -76,43 +78,15 @@ impl Bindings {
76 // FIXME: Do we have a better way to represent an empty token ? 78 // FIXME: Do we have a better way to represent an empty token ?
77 // Insert an empty subtree for empty token 79 // Insert an empty subtree for empty token
78 let tt = tt::Subtree::default().into(); 80 let tt = tt::Subtree::default().into();
79 self.inner.push((name.clone(), Binding::Fragment(Fragment::Tokens(tt)))); 81 self.inner.insert(name.clone(), Binding::Fragment(Fragment::Tokens(tt)));
80 } 82 }
81 83
82 fn push_empty(&mut self, name: &SmolStr) { 84 fn push_empty(&mut self, name: &SmolStr) {
83 self.inner.push((name.clone(), Binding::Empty)); 85 self.inner.insert(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 } 86 }
113 87
114 fn bindings(&self) -> impl Iterator<Item = &Binding> { 88 fn bindings(&self) -> impl Iterator<Item = &Binding> {
115 self.inner.iter().map(|(_, b)| b) 89 self.inner.values()
116 } 90 }
117} 91}
118 92
@@ -163,6 +137,187 @@ pub(super) fn match_(pattern: &MetaTemplate, input: &tt::Subtree) -> Match {
163} 137}
164 138
165#[derive(Debug, Clone)] 139#[derive(Debug, Clone)]
140enum BindingKind {
141 Empty(SmolStr),
142 Optional(SmolStr),
143 Fragment(SmolStr, Fragment),
144 Nested(usize, usize),
145}
146
147#[derive(Debug, Clone)]
148struct BindingsIdx(usize, usize);
149
150#[derive(Debug, Clone)]
151enum LinkNode<T> {
152 Node(T),
153 Parent { idx: usize, len: usize },
154}
155
156#[derive(Default)]
157struct BindingsBuilder {
158 nodes: Vec<Vec<LinkNode<Rc<BindingKind>>>>,
159 nested: Vec<Vec<LinkNode<usize>>>,
160}
161
162impl BindingsBuilder {
163 fn alloc(&mut self) -> BindingsIdx {
164 let idx = self.nodes.len();
165 self.nodes.push(Vec::with_capacity(8));
166 let nidx = self.nested.len();
167 self.nested.push(Vec::with_capacity(8));
168 BindingsIdx(idx, nidx)
169 }
170
171 fn copy(&mut self, bindings: &BindingsIdx) -> BindingsIdx {
172 let idx = copy_parent(bindings.0, &mut self.nodes);
173 let nidx = copy_parent(bindings.1, &mut self.nested);
174 return BindingsIdx(idx, nidx);
175
176 fn copy_parent<T>(idx: usize, target: &mut Vec<Vec<LinkNode<T>>>) -> usize
177 where
178 T: Clone,
179 {
180 let new_idx = target.len();
181 let len = target[idx].len();
182 if len < 4 {
183 target.push(target[idx].clone())
184 } else {
185 let mut item = Vec::with_capacity(8);
186 item.push(LinkNode::Parent { idx, len });
187 target.push(item);
188 }
189
190 new_idx
191 }
192 }
193
194 fn push_empty(&mut self, idx: &mut BindingsIdx, var: &SmolStr) {
195 self.nodes[idx.0].push(LinkNode::Node(Rc::new(BindingKind::Empty(var.clone()))));
196 }
197
198 fn push_optional(&mut self, idx: &mut BindingsIdx, var: &SmolStr) {
199 self.nodes[idx.0].push(LinkNode::Node(Rc::new(BindingKind::Optional(var.clone()))));
200 }
201
202 fn push_fragment(&mut self, idx: &mut BindingsIdx, var: &SmolStr, fragment: Fragment) {
203 self.nodes[idx.0]
204 .push(LinkNode::Node(Rc::new(BindingKind::Fragment(var.clone(), fragment))));
205 }
206
207 fn push_nested(&mut self, parent: &mut BindingsIdx, child: &BindingsIdx) {
208 let BindingsIdx(idx, nidx) = self.copy(&child);
209 self.nodes[parent.0].push(LinkNode::Node(Rc::new(BindingKind::Nested(idx, nidx))));
210 }
211
212 fn push_default(&mut self, idx: &mut BindingsIdx) {
213 self.nested[idx.1].push(LinkNode::Node(idx.0));
214 let new_idx = self.nodes.len();
215 self.nodes.push(Vec::with_capacity(8));
216 idx.0 = new_idx;
217 }
218
219 fn build(self, idx: &BindingsIdx) -> Bindings {
220 let mut bindings = Bindings::default();
221 self.build_recur(&mut bindings, self.nodes[idx.0].clone());
222 bindings
223 }
224
225 fn build_recur(&self, bindings: &mut Bindings, nodes: Vec<LinkNode<Rc<BindingKind>>>) {
226 for cmd in self.flatten_nodes(nodes) {
227 match &*cmd {
228 BindingKind::Empty(name) => {
229 bindings.push_empty(name);
230 }
231 BindingKind::Optional(name) => {
232 bindings.push_optional(name);
233 }
234 BindingKind::Fragment(name, fragment) => {
235 bindings.inner.insert(name.clone(), Binding::Fragment(fragment.clone()));
236 }
237 BindingKind::Nested(idx, list) => {
238 let list = self.flatten_nested(*idx, *list);
239
240 for (idx, iter) in list.enumerate() {
241 for (key, value) in &iter.inner {
242 let bindings = bindings
243 .inner
244 .entry(key.clone())
245 .or_insert_with(|| Binding::Nested(Vec::new()));
246
247 if let Binding::Nested(it) = bindings {
248 // insert empty nested bindings before this one
249 while it.len() < idx {
250 it.push(Binding::Nested(Vec::new()));
251 }
252 it.push(value.clone());
253 }
254 }
255 }
256 }
257 }
258 }
259 }
260
261 fn flatten_nested_ref(&self, id: usize, len: usize) -> Vec<Vec<LinkNode<Rc<BindingKind>>>> {
262 self.nested[id]
263 .iter()
264 .take(len)
265 .map(|it| match it {
266 LinkNode::Node(id) => vec![self.nodes[*id].clone()],
267 LinkNode::Parent { idx, len } => self.flatten_nested_ref(*idx, *len),
268 })
269 .flatten()
270 .collect()
271 }
272
273 fn flatten_nested<'a>(
274 &'a self,
275 idx: usize,
276 list: usize,
277 ) -> impl Iterator<Item = Bindings> + 'a {
278 let last = self.nodes[idx].clone();
279 self.nested[list]
280 .iter()
281 .map(move |it| match *it {
282 LinkNode::Node(idx) => vec![self.nodes[idx].clone()],
283 LinkNode::Parent { idx, len } => self.flatten_nested_ref(idx, len),
284 })
285 .flatten()
286 .chain(std::iter::once(last))
287 .map(move |iter| {
288 let mut child_bindings = Bindings::default();
289 self.build_recur(&mut child_bindings, iter);
290 child_bindings
291 })
292 }
293
294 fn flatten_nodes_ref(&self, id: usize, len: usize) -> Vec<Rc<BindingKind>> {
295 self.nodes[id]
296 .iter()
297 .take(len)
298 .map(|it| match it {
299 LinkNode::Node(it) => vec![it.clone()],
300 LinkNode::Parent { idx, len } => self.flatten_nodes_ref(*idx, *len),
301 })
302 .flatten()
303 .collect()
304 }
305
306 fn flatten_nodes<'a>(
307 &'a self,
308 nodes: Vec<LinkNode<Rc<BindingKind>>>,
309 ) -> impl Iterator<Item = Rc<BindingKind>> + 'a {
310 nodes
311 .into_iter()
312 .map(move |it| match it {
313 LinkNode::Node(it) => vec![it],
314 LinkNode::Parent { idx, len } => self.flatten_nodes_ref(idx, len),
315 })
316 .flatten()
317 }
318}
319
320#[derive(Debug, Clone)]
166struct MatchState<'t> { 321struct MatchState<'t> {
167 /// The position of the "dot" in this matcher 322 /// The position of the "dot" in this matcher
168 dot: OpDelimitedIter<'t>, 323 dot: OpDelimitedIter<'t>,
@@ -187,7 +342,7 @@ struct MatchState<'t> {
187 sep_parsed: Option<usize>, 342 sep_parsed: Option<usize>,
188 343
189 /// Matched meta variables bindings 344 /// Matched meta variables bindings
190 bindings: SmallVec<[Bindings; 4]>, 345 bindings: BindingsIdx,
191 346
192 /// Cached result of meta variable parsing 347 /// Cached result of meta variable parsing
193 meta_result: Option<(TtIter<'t>, ExpandResult<Option<Fragment>>)>, 348 meta_result: Option<(TtIter<'t>, ExpandResult<Option<Fragment>>)>,
@@ -218,6 +373,7 @@ fn match_loop_inner<'t>(
218 src: TtIter<'t>, 373 src: TtIter<'t>,
219 stack: &[TtIter<'t>], 374 stack: &[TtIter<'t>],
220 res: &mut Match, 375 res: &mut Match,
376 bindings_builder: &mut BindingsBuilder,
221 cur_items: &mut SmallVec<[MatchState<'t>; 1]>, 377 cur_items: &mut SmallVec<[MatchState<'t>; 1]>,
222 bb_items: &mut SmallVec<[MatchState<'t>; 1]>, 378 bb_items: &mut SmallVec<[MatchState<'t>; 1]>,
223 next_items: &mut Vec<MatchState<'t>>, 379 next_items: &mut Vec<MatchState<'t>>,
@@ -251,12 +407,10 @@ fn match_loop_inner<'t>(
251 if item.sep_parsed.is_none() { 407 if item.sep_parsed.is_none() {
252 // Get the `up` matcher 408 // Get the `up` matcher
253 let mut new_pos = *item.up.clone().unwrap(); 409 let mut new_pos = *item.up.clone().unwrap();
410 new_pos.bindings = bindings_builder.copy(&new_pos.bindings);
254 // Add matches from this repetition to the `matches` of `up` 411 // Add matches from this repetition to the `matches` of `up`
255 if let Some(bindings) = new_pos.bindings.last_mut() { 412 bindings_builder.push_nested(&mut new_pos.bindings, &item.bindings);
256 for (i, b) in item.bindings.iter_mut().enumerate() { 413
257 bindings.push_nested(i, b.clone()).unwrap();
258 }
259 }
260 // Move the "dot" past the repetition in `up` 414 // Move the "dot" past the repetition in `up`
261 new_pos.dot.next(); 415 new_pos.dot.next();
262 new_pos.is_error = new_pos.is_error || item.is_error; 416 new_pos.is_error = new_pos.is_error || item.is_error;
@@ -280,7 +434,7 @@ fn match_loop_inner<'t>(
280 else if item.sep_kind != Some(RepeatKind::ZeroOrOne) { 434 else if item.sep_kind != Some(RepeatKind::ZeroOrOne) {
281 item.dot = item.dot.reset(); 435 item.dot = item.dot.reset();
282 item.sep_parsed = None; 436 item.sep_parsed = None;
283 item.bindings.push(Bindings::default()); 437 bindings_builder.push_default(&mut item.bindings);
284 cur_items.push(item); 438 cur_items.push(item);
285 } 439 }
286 } else { 440 } else {
@@ -298,12 +452,12 @@ fn match_loop_inner<'t>(
298 OpDelimited::Op(Op::Repeat { tokens, kind, separator }) => { 452 OpDelimited::Op(Op::Repeat { tokens, kind, separator }) => {
299 if matches!(kind, RepeatKind::ZeroOrMore | RepeatKind::ZeroOrOne) { 453 if matches!(kind, RepeatKind::ZeroOrMore | RepeatKind::ZeroOrOne) {
300 let mut new_item = item.clone(); 454 let mut new_item = item.clone();
455 new_item.bindings = bindings_builder.copy(&new_item.bindings);
301 new_item.dot.next(); 456 new_item.dot.next();
302 let mut vars = Vec::new(); 457 let mut vars = Vec::new();
303 let bindings = new_item.bindings.last_mut().unwrap();
304 collect_vars(&mut vars, tokens); 458 collect_vars(&mut vars, tokens);
305 for var in vars { 459 for var in vars {
306 bindings.push_empty(&var); 460 bindings_builder.push_empty(&mut new_item.bindings, &var);
307 } 461 }
308 cur_items.push(new_item); 462 cur_items.push(new_item);
309 } 463 }
@@ -314,7 +468,7 @@ fn match_loop_inner<'t>(
314 sep: separator.clone(), 468 sep: separator.clone(),
315 sep_kind: Some(*kind), 469 sep_kind: Some(*kind),
316 sep_parsed: None, 470 sep_parsed: None,
317 bindings: smallvec![Bindings::default()], 471 bindings: bindings_builder.alloc(),
318 meta_result: None, 472 meta_result: None,
319 is_error: false, 473 is_error: false,
320 }) 474 })
@@ -339,7 +493,7 @@ fn match_loop_inner<'t>(
339 item.meta_result = Some((fork, match_res)); 493 item.meta_result = Some((fork, match_res));
340 try_push!(bb_items, item); 494 try_push!(bb_items, item);
341 } else { 495 } else {
342 item.bindings.last_mut().unwrap().push_optional(name); 496 bindings_builder.push_optional(&mut item.bindings, &name);
343 item.dot.next(); 497 item.dot.next();
344 cur_items.push(item); 498 cur_items.push(item);
345 } 499 }
@@ -348,11 +502,11 @@ fn match_loop_inner<'t>(
348 res.add_err(err); 502 res.add_err(err);
349 match match_res.value { 503 match match_res.value {
350 Some(fragment) => { 504 Some(fragment) => {
351 item.bindings 505 bindings_builder.push_fragment(
352 .last_mut() 506 &mut item.bindings,
353 .unwrap() 507 &name,
354 .inner 508 fragment,
355 .push((name.clone(), Binding::Fragment(fragment))); 509 );
356 } 510 }
357 _ => {} 511 _ => {}
358 } 512 }
@@ -394,6 +548,8 @@ fn match_loop(pattern: &MetaTemplate, src: &tt::Subtree) -> Match {
394 let mut res = Match::default(); 548 let mut res = Match::default();
395 let mut error_reover_item = None; 549 let mut error_reover_item = None;
396 550
551 let mut bindings_builder = BindingsBuilder::default();
552
397 let mut cur_items = smallvec![MatchState { 553 let mut cur_items = smallvec![MatchState {
398 dot: pattern.iter_delimited(None), 554 dot: pattern.iter_delimited(None),
399 stack: Default::default(), 555 stack: Default::default(),
@@ -401,7 +557,7 @@ fn match_loop(pattern: &MetaTemplate, src: &tt::Subtree) -> Match {
401 sep: None, 557 sep: None,
402 sep_kind: None, 558 sep_kind: None,
403 sep_parsed: None, 559 sep_parsed: None,
404 bindings: smallvec![Bindings::default()], 560 bindings: bindings_builder.alloc(),
405 is_error: false, 561 is_error: false,
406 meta_result: None, 562 meta_result: None,
407 }]; 563 }];
@@ -419,6 +575,7 @@ fn match_loop(pattern: &MetaTemplate, src: &tt::Subtree) -> Match {
419 src.clone(), 575 src.clone(),
420 &stack, 576 &stack,
421 &mut res, 577 &mut res,
578 &mut bindings_builder,
422 &mut cur_items, 579 &mut cur_items,
423 &mut bb_items, 580 &mut bb_items,
424 &mut next_items, 581 &mut next_items,
@@ -428,9 +585,9 @@ fn match_loop(pattern: &MetaTemplate, src: &tt::Subtree) -> Match {
428 stdx::always!(cur_items.is_empty()); 585 stdx::always!(cur_items.is_empty());
429 586
430 if error_items.len() > 0 { 587 if error_items.len() > 0 {
431 error_reover_item = error_items.pop(); 588 error_reover_item = error_items.pop().map(|it| it.bindings);
432 } else if eof_items.len() > 0 { 589 } else if eof_items.len() > 0 {
433 error_reover_item = Some(eof_items[0].clone()); 590 error_reover_item = Some(eof_items[0].bindings.clone());
434 } 591 }
435 592
436 // We need to do some post processing after the `match_loop_inner`. 593 // We need to do some post processing after the `match_loop_inner`.
@@ -440,11 +597,11 @@ fn match_loop(pattern: &MetaTemplate, src: &tt::Subtree) -> Match {
440 if eof_items.len() == 1 { 597 if eof_items.len() == 1 {
441 // remove all errors, because it is the correct answer ! 598 // remove all errors, because it is the correct answer !
442 res = Match::default(); 599 res = Match::default();
443 res.bindings = eof_items[0].bindings[0].clone(); 600 res.bindings = bindings_builder.build(&eof_items[0].bindings);
444 } else { 601 } else {
445 // Error recovery 602 // Error recovery
446 if error_reover_item.is_some() { 603 if error_reover_item.is_some() {
447 res.bindings = error_reover_item.unwrap().bindings[0].clone(); 604 res.bindings = bindings_builder.build(&error_reover_item.unwrap());
448 } 605 }
449 res.add_err(ExpandError::UnexpectedToken); 606 res.add_err(ExpandError::UnexpectedToken);
450 } 607 }
@@ -467,8 +624,8 @@ fn match_loop(pattern: &MetaTemplate, src: &tt::Subtree) -> Match {
467 } 624 }
468 res.add_err(err!("leftover tokens")); 625 res.add_err(err!("leftover tokens"));
469 626
470 if let Some(mut error_reover_item) = error_reover_item { 627 if let Some(error_reover_item) = error_reover_item {
471 res.bindings = error_reover_item.bindings.remove(0); 628 res.bindings = bindings_builder.build(&error_reover_item);
472 } 629 }
473 return res; 630 return res;
474 } 631 }
@@ -494,12 +651,13 @@ fn match_loop(pattern: &MetaTemplate, src: &tt::Subtree) -> Match {
494 651
495 if let Some(OpDelimited::Op(Op::Var { name, .. })) = item.dot.peek() { 652 if let Some(OpDelimited::Op(Op::Var { name, .. })) = item.dot.peek() {
496 let (iter, match_res) = item.meta_result.take().unwrap(); 653 let (iter, match_res) = item.meta_result.take().unwrap();
497 let bindings = item.bindings.last_mut().unwrap();
498 match match_res.value { 654 match match_res.value {
499 Some(fragment) => { 655 Some(fragment) => {
500 bindings.inner.push((name.clone(), Binding::Fragment(fragment))); 656 bindings_builder.push_fragment(&mut item.bindings, &name, fragment);
657 }
658 None if match_res.err.is_none() => {
659 bindings_builder.push_optional(&mut item.bindings, &name);
501 } 660 }
502 None if match_res.err.is_none() => bindings.push_optional(name),
503 _ => {} 661 _ => {}
504 } 662 }
505 if let Some(err) = match_res.err { 663 if let Some(err) = match_res.err {
diff --git a/crates/mbe/src/expander/transcriber.rs b/crates/mbe/src/expander/transcriber.rs
index ad9953a7d..c679e5e5d 100644
--- a/crates/mbe/src/expander/transcriber.rs
+++ b/crates/mbe/src/expander/transcriber.rs
@@ -13,17 +13,13 @@ use crate::{
13 13
14impl Bindings { 14impl Bindings {
15 fn contains(&self, name: &str) -> bool { 15 fn contains(&self, name: &str) -> bool {
16 self.inner.iter().any(|(n, _)| n == name) 16 self.inner.contains_key(name)
17 } 17 }
18 18
19 fn get(&self, name: &str, nesting: &mut [NestingState]) -> Result<&Fragment, ExpandError> { 19 fn get(&self, name: &str, nesting: &mut [NestingState]) -> Result<&Fragment, ExpandError> {
20 let mut b: &Binding = self 20 let mut b: &Binding = self.inner.get(name).ok_or_else(|| {
21 .inner 21 ExpandError::BindingError(format!("could not find binding `{}`", name))
22 .iter() 22 })?;
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 })?;
27 for nesting_state in nesting.iter_mut() { 23 for nesting_state in nesting.iter_mut() {
28 nesting_state.hit = true; 24 nesting_state.hit = true;
29 b = match b { 25 b = match b {