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, 47 insertions, 0 deletions

diff --git a/crates/tt/src/lib.rs b/crates/tt/src/lib.rs
index 8301dc28a..9d9a01e30 100644
--- a/crates/tt/src/lib.rs
+++ b/crates/tt/src/lib.rs
@@ -227,6 +227,53 @@ impl Subtree {
     }
 }
 
+impl Subtree {
+    /// A simple line string used for debugging
+    pub fn as_debug_string(&self) -> String {
+        let delim = match self.delimiter_kind() {
+            Some(DelimiterKind::Brace) => ("{", "}"),
+            Some(DelimiterKind::Bracket) => ("[", "]"),
+            Some(DelimiterKind::Parenthesis) => ("(", ")"),
+            None => (" ", " "),
+        };
+
+        let mut res = String::new();
+        res.push_str(delim.0);
+        let mut iter = self.token_trees.iter();
+        let mut last = None;
+        while let Some(child) = iter.next() {
+            let s = match child {
+                TokenTree::Leaf(it) => {
+                    let s = match it {
+                        Leaf::Literal(it) => it.text.to_string(),
+                        Leaf::Punct(it) => it.char.to_string(),
+                        Leaf::Ident(it) => it.text.to_string(),
+                    };
+                    match (it, last) {
+                        (Leaf::Ident(_), Some(&TokenTree::Leaf(Leaf::Ident(_)))) => {
+                            " ".to_string() + &s
+                        }
+                        (Leaf::Punct(_), Some(&TokenTree::Leaf(Leaf::Punct(punct)))) => {
+                            if punct.spacing == Spacing::Alone {
+                                " ".to_string() + &s
+                            } else {
+                                s
+                            }
+                        }
+                        _ => s,
+                    }
+                }
+                TokenTree::Subtree(it) => it.as_debug_string(),
+            };
+            res.push_str(&s);
+            last = Some(child);
+        }
+
+        res.push_str(delim.1);
+        res
+    }
+}
+
 pub mod buffer;
 
 #[derive(Debug, PartialEq, Eq, Clone)]