Merge #7513

7513: NFA parser for mbe matcher r=matklad a=edwin0cheng

Almost straight porting from rustc one, but a little bit slow :(

```
rust-analyzer analysis-stats -q . 
```

From:
```log
Database loaded:     636.11ms, 277minstr
  crates: 36, mods: 594, decls: 11527, fns: 9017
Item Collection:     10.99s, 60ginstr
  exprs: 249618, ??ty: 2699 (1%), ?ty: 2101 (0%), !ty: 932
Inference:           28.94s, 123ginstr
Total:               39.93s, 184ginstr
```

To:
```log
Database loaded:     630.90ms, 277minstr
  crates: 36, mods: 594, decls: 11528, fns: 9018
Item Collection:     13.70s, 77ginstr
  exprs: 249482, ??ty: 2699 (1%), ?ty: 2101 (0%), !ty: 932
Inference:           30.27s, 133ginstr
Total:               43.97s, 211ginstr
```

Fixes #4777

Co-authored-by: Edwin Cheng <[email protected]>

1 files changed, 8 insertions, 8 deletions

diff --git a/crates/mbe/src/expander.rs b/crates/mbe/src/expander.rs
index e7e14b3cc..2efff8f52 100644
--- a/crates/mbe/src/expander.rs
+++ b/crates/mbe/src/expander.rs
@@ -5,7 +5,7 @@
 mod matcher;
 mod transcriber;
 
-use rustc_hash::FxHashMap;
+use smallvec::SmallVec;
 use syntax::SmolStr;
 
 use crate::{ExpandError, ExpandResult};
@@ -28,10 +28,10 @@ pub(crate) fn expand_rules(
                 return ExpandResult::ok(value);
             }
         }
-        // Use the rule if we matched more tokens, or had fewer errors
+        // Use the rule if we matched more tokens, or bound variables count
         if let Some((prev_match, _)) = &match_ {
-            if (new_match.unmatched_tts, new_match.err_count)
-                < (prev_match.unmatched_tts, prev_match.err_count)
+            if (new_match.unmatched_tts, -(new_match.bound_count as i32))
+                < (prev_match.unmatched_tts, -(prev_match.bound_count as i32))
             {
                 match_ = Some((new_match, rule));
             }
@@ -94,19 +94,19 @@ pub(crate) fn expand_rules(
 /// In other words, `Bindings` is a *multi* mapping from `SmolStr` to
 /// `tt::TokenTree`, where the index to select a particular `TokenTree` among
 /// many is not a plain `usize`, but an `&[usize]`.
-#[derive(Debug, Default)]
+#[derive(Debug, Default, Clone, PartialEq, Eq)]
 struct Bindings {
-    inner: FxHashMap<SmolStr, Binding>,
+    inner: SmallVec<[(SmolStr, Binding); 4]>,
 }
 
-#[derive(Debug)]
+#[derive(Debug, Clone, PartialEq, Eq)]
 enum Binding {
     Fragment(Fragment),
     Nested(Vec<Binding>),
     Empty,
 }
 
-#[derive(Debug, Clone)]
+#[derive(Debug, Clone, PartialEq, Eq)]
 enum Fragment {
     /// token fragments are just copy-pasted into the output
     Tokens(tt::TokenTree),