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, 4 deletions

diff --git a/crates/mbe/src/expander/transcriber.rs b/crates/mbe/src/expander/transcriber.rs
index 78368a33e..ad9953a7d 100644
--- a/crates/mbe/src/expander/transcriber.rs
+++ b/crates/mbe/src/expander/transcriber.rs
@@ -13,13 +13,17 @@ use crate::{
 
 impl Bindings {
     fn contains(&self, name: &str) -> bool {
-        self.inner.contains_key(name)
+        self.inner.iter().any(|(n, _)| n == name)
     }
 
     fn get(&self, name: &str, nesting: &mut [NestingState]) -> Result<&Fragment, ExpandError> {
-        let mut b = self.inner.get(name).ok_or_else(|| {
-            ExpandError::BindingError(format!("could not find binding `{}`", name))
-        })?;
+        let mut b: &Binding = self
+            .inner
+            .iter()
+            .find_map(|(n, b)| if n == name { Some(b) } else { None })
+            .ok_or_else(|| {
+                ExpandError::BindingError(format!("could not find binding `{}`", name))
+            })?;
         for nesting_state in nesting.iter_mut() {
             nesting_state.hit = true;
             b = match b {