Merge #7994

7994: Speed up mbe matching in heavy recursive cases r=edwin0cheng a=edwin0cheng

In some cases (e.g.  #4186), mbe matching is very slow due to a lot of copy and allocation for bindings, this PR try to solve this problem by introduce a semi "link-list" approach for bindings building.

I used this [test case](https://github.com/weiznich/minimal_example_for_rust_81262) (for `features(32-column-tables)`) to run following command to benchmark:
```
time rust-analyzer analysis-stats  --load-output-dirs ./ 
```

Before this PR : 2 mins
After this PR: 3 seconds.

However, for 64-column-tables cases, we still need 4 mins to complete. 

I will try to investigate in the following weeks.

bors r+




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

1 files changed, 4 insertions, 8 deletions

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::{
 
 impl Bindings {
     fn contains(&self, name: &str) -> bool {
-        self.inner.iter().any(|(n, _)| n == name)
+        self.inner.contains_key(name)
     }
 
     fn get(&self, name: &str, nesting: &mut [NestingState]) -> Result<&Fragment, ExpandError> {
-        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))
-            })?;
+        let mut b: &Binding = self.inner.get(name).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 {