3 files changed, 220 insertions, 69 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 @@
 mod matcher;
 mod transcriber;
 
-use smallvec::SmallVec;
+use rustc_hash::FxHashMap;
 use syntax::SmolStr;
 
 use crate::{ExpandError, ExpandResult};
@@ -96,7 +96,7 @@ pub(crate) fn expand_rules(
 /// many is not a plain `usize`, but an `&[usize]`.
 #[derive(Debug, Default, Clone, PartialEq, Eq)]
 struct Bindings {
-    inner: SmallVec<[(SmolStr, Binding); 4]>,
+    inner: FxHashMap<SmolStr, Binding>,
 }
 
 #[derive(Debug, Clone, PartialEq, Eq)]
diff --git a/crates/mbe/src/expander/matcher.rs b/crates/mbe/src/expander/matcher.rs
index 9d3d28055..2c69e8968 100644
--- a/crates/mbe/src/expander/matcher.rs
+++ b/crates/mbe/src/expander/matcher.rs
@@ -59,6 +59,8 @@
 //! eof: [a $( a )* a b ·]
 //! ```
 
+use std::rc::Rc;
+
 use crate::{
     expander::{Binding, Bindings, Fragment},
     parser::{Op, OpDelimited, OpDelimitedIter, RepeatKind, Separator},
@@ -76,43 +78,15 @@ impl Bindings {
         // FIXME: Do we have a better way to represent an empty token ?
         // Insert an empty subtree for empty token
         let tt = tt::Subtree::default().into();
-        self.inner.push((name.clone(), Binding::Fragment(Fragment::Tokens(tt))));
+        self.inner.insert(name.clone(), Binding::Fragment(Fragment::Tokens(tt)));
     }
 
     fn push_empty(&mut self, name: &SmolStr) {
-        self.inner.push((name.clone(), Binding::Empty));
-    }
-
-    fn push_nested(&mut self, idx: usize, nested: Bindings) -> Result<(), ExpandError> {
-        for (key, value) in nested.inner {
-            if self.get_mut(&key).is_none() {
-                self.inner.push((key.clone(), Binding::Nested(Vec::new())));
-            }
-            match self.get_mut(&key) {
-                Some(Binding::Nested(it)) => {
-                    // insert empty nested bindings before this one
-                    while it.len() < idx {
-                        it.push(Binding::Nested(vec![]));
-                    }
-                    it.push(value);
-                }
-                _ => {
-                    return Err(ExpandError::BindingError(format!(
-                        "could not find binding `{}`",
-                        key
-                    )));
-                }
-            }
-        }
-        Ok(())
-    }
-
-    fn get_mut(&mut self, name: &str) -> Option<&mut Binding> {
-        self.inner.iter_mut().find_map(|(n, b)| if n == name { Some(b) } else { None })
+        self.inner.insert(name.clone(), Binding::Empty);
     }
 
     fn bindings(&self) -> impl Iterator<Item = &Binding> {
-        self.inner.iter().map(|(_, b)| b)
+        self.inner.values()
     }
 }
 
@@ -163,6 +137,181 @@ pub(super) fn match_(pattern: &MetaTemplate, input: &tt::Subtree) -> Match {
 }
 
 #[derive(Debug, Clone)]
+enum BindingKind {
+    Empty(SmolStr),
+    Optional(SmolStr),
+    Fragment(SmolStr, Fragment),
+    Nested(usize, usize),
+}
+
+#[derive(Debug, Clone)]
+struct BindingsIdx(usize, usize);
+
+#[derive(Debug, Clone)]
+enum LinkNode<T> {
+    Node(T),
+    Parent { idx: usize, len: usize },
+}
+
+#[derive(Default)]
+struct BindingsBuilder {
+    nodes: Vec<Vec<LinkNode<Rc<BindingKind>>>>,
+    nested: Vec<Vec<LinkNode<usize>>>,
+}
+
+impl BindingsBuilder {
+    fn alloc(&mut self) -> BindingsIdx {
+        let idx = self.nodes.len();
+        self.nodes.push(Vec::new());
+        let nidx = self.nested.len();
+        self.nested.push(Vec::new());
+        BindingsIdx(idx, nidx)
+    }
+
+    fn copy(&mut self, bindings: &BindingsIdx) -> BindingsIdx {
+        let idx = copy_parent(bindings.0, &mut self.nodes);
+        let nidx = copy_parent(bindings.1, &mut self.nested);
+        return BindingsIdx(idx, nidx);
+
+        fn copy_parent<T>(idx: usize, target: &mut Vec<Vec<LinkNode<T>>>) -> usize
+        where
+            T: Clone,
+        {
+            let new_idx = target.len();
+            let len = target[idx].len();
+            if len < 4 {
+                target.push(target[idx].clone())
+            } else {
+                target.push(vec![LinkNode::Parent { idx, len }]);
+            }
+            new_idx
+        }
+    }
+
+    fn push_empty(&mut self, idx: &mut BindingsIdx, var: &SmolStr) {
+        self.nodes[idx.0].push(LinkNode::Node(Rc::new(BindingKind::Empty(var.clone()))));
+    }
+
+    fn push_optional(&mut self, idx: &mut BindingsIdx, var: &SmolStr) {
+        self.nodes[idx.0].push(LinkNode::Node(Rc::new(BindingKind::Optional(var.clone()))));
+    }
+
+    fn push_fragment(&mut self, idx: &mut BindingsIdx, var: &SmolStr, fragment: Fragment) {
+        self.nodes[idx.0]
+            .push(LinkNode::Node(Rc::new(BindingKind::Fragment(var.clone(), fragment))));
+    }
+
+    fn push_nested(&mut self, parent: &mut BindingsIdx, child: &BindingsIdx) {
+        let BindingsIdx(idx, nidx) = self.copy(&child);
+        self.nodes[parent.0].push(LinkNode::Node(Rc::new(BindingKind::Nested(idx, nidx))));
+    }
+
+    fn push_default(&mut self, idx: &mut BindingsIdx) {
+        self.nested[idx.1].push(LinkNode::Node(idx.0));
+        let new_idx = self.nodes.len();
+        self.nodes.push(Vec::new());
+        idx.0 = new_idx;
+    }
+
+    fn build(self, idx: &BindingsIdx) -> Bindings {
+        let mut bindings = Bindings::default();
+        self.build_inner(&mut bindings, &self.nodes[idx.0]);
+        bindings
+    }
+
+    fn build_inner(&self, bindings: &mut Bindings, link_nodes: &Vec<LinkNode<Rc<BindingKind>>>) {
+        let mut nodes = Vec::new();
+        self.collect_nodes(&link_nodes, &mut nodes);
+
+        for cmd in nodes {
+            match &**cmd {
+                BindingKind::Empty(name) => {
+                    bindings.push_empty(name);
+                }
+                BindingKind::Optional(name) => {
+                    bindings.push_optional(name);
+                }
+                BindingKind::Fragment(name, fragment) => {
+                    bindings.inner.insert(name.clone(), Binding::Fragment(fragment.clone()));
+                }
+                BindingKind::Nested(idx, nested_idx) => {
+                    let mut nested_nodes = Vec::new();
+                    self.collect_nested(*idx, *nested_idx, &mut nested_nodes);
+
+                    for (idx, iter) in nested_nodes.into_iter().enumerate() {
+                        for (key, value) in &iter.inner {
+                            let bindings = bindings
+                                .inner
+                                .entry(key.clone())
+                                .or_insert_with(|| Binding::Nested(Vec::new()));
+
+                            if let Binding::Nested(it) = bindings {
+                                // insert empty nested bindings before this one
+                                while it.len() < idx {
+                                    it.push(Binding::Nested(Vec::new()));
+                                }
+                                it.push(value.clone());
+                            }
+                        }
+                    }
+                }
+            }
+        }
+    }
+
+    fn collect_nested_ref<'a>(
+        &'a self,
+        id: usize,
+        len: usize,
+        nested_refs: &mut Vec<&'a Vec<LinkNode<Rc<BindingKind>>>>,
+    ) {
+        self.nested[id].iter().take(len).for_each(|it| match it {
+            LinkNode::Node(id) => nested_refs.push(&self.nodes[*id]),
+            LinkNode::Parent { idx, len } => self.collect_nested_ref(*idx, *len, nested_refs),
+        });
+    }
+
+    fn collect_nested(&self, idx: usize, nested_idx: usize, nested: &mut Vec<Bindings>) {
+        let last = &self.nodes[idx];
+        let mut nested_refs = Vec::new();
+        self.nested[nested_idx].iter().for_each(|it| match *it {
+            LinkNode::Node(idx) => nested_refs.push(&self.nodes[idx]),
+            LinkNode::Parent { idx, len } => self.collect_nested_ref(idx, len, &mut nested_refs),
+        });
+        nested_refs.push(last);
+
+        nested_refs.into_iter().for_each(|iter| {
+            let mut child_bindings = Bindings::default();
+            self.build_inner(&mut child_bindings, &iter);
+            nested.push(child_bindings)
+        })
+    }
+
+    fn collect_nodes_ref<'a>(
+        &'a self,
+        id: usize,
+        len: usize,
+        nodes: &mut Vec<&'a Rc<BindingKind>>,
+    ) {
+        self.nodes[id].iter().take(len).for_each(|it| match it {
+            LinkNode::Node(it) => nodes.push(it),
+            LinkNode::Parent { idx, len } => self.collect_nodes_ref(*idx, *len, nodes),
+        });
+    }
+
+    fn collect_nodes<'a>(
+        &'a self,
+        link_nodes: &'a Vec<LinkNode<Rc<BindingKind>>>,
+        nodes: &mut Vec<&'a Rc<BindingKind>>,
+    ) {
+        link_nodes.into_iter().for_each(|it| match it {
+            LinkNode::Node(it) => nodes.push(it),
+            LinkNode::Parent { idx, len } => self.collect_nodes_ref(*idx, *len, nodes),
+        });
+    }
+}
+
+#[derive(Debug, Clone)]
 struct MatchState<'t> {
     /// The position of the "dot" in this matcher
     dot: OpDelimitedIter<'t>,
@@ -187,7 +336,7 @@ struct MatchState<'t> {
     sep_parsed: Option<usize>,
 
     /// Matched meta variables bindings
-    bindings: SmallVec<[Bindings; 4]>,
+    bindings: BindingsIdx,
 
     /// Cached result of meta variable parsing
     meta_result: Option<(TtIter<'t>, ExpandResult<Option<Fragment>>)>,
@@ -218,6 +367,7 @@ fn match_loop_inner<'t>(
     src: TtIter<'t>,
     stack: &[TtIter<'t>],
     res: &mut Match,
+    bindings_builder: &mut BindingsBuilder,
     cur_items: &mut SmallVec<[MatchState<'t>; 1]>,
     bb_items: &mut SmallVec<[MatchState<'t>; 1]>,
     next_items: &mut Vec<MatchState<'t>>,
@@ -251,12 +401,10 @@ fn match_loop_inner<'t>(
                     if item.sep_parsed.is_none() {
                         // Get the `up` matcher
                         let mut new_pos = *item.up.clone().unwrap();
+                        new_pos.bindings = bindings_builder.copy(&new_pos.bindings);
                         // Add matches from this repetition to the `matches` of `up`
-                        if let Some(bindings) = new_pos.bindings.last_mut() {
-                            for (i, b) in item.bindings.iter_mut().enumerate() {
-                                bindings.push_nested(i, b.clone()).unwrap();
-                            }
-                        }
+                        bindings_builder.push_nested(&mut new_pos.bindings, &item.bindings);
+
                         // Move the "dot" past the repetition in `up`
                         new_pos.dot.next();
                         new_pos.is_error = new_pos.is_error || item.is_error;
@@ -280,7 +428,7 @@ fn match_loop_inner<'t>(
                     else if item.sep_kind != Some(RepeatKind::ZeroOrOne) {
                         item.dot = item.dot.reset();
                         item.sep_parsed = None;
-                        item.bindings.push(Bindings::default());
+                        bindings_builder.push_default(&mut item.bindings);
                         cur_items.push(item);
                     }
                 } else {
@@ -298,12 +446,12 @@ fn match_loop_inner<'t>(
             OpDelimited::Op(Op::Repeat { tokens, kind, separator }) => {
                 if matches!(kind, RepeatKind::ZeroOrMore | RepeatKind::ZeroOrOne) {
                     let mut new_item = item.clone();
+                    new_item.bindings = bindings_builder.copy(&new_item.bindings);
                     new_item.dot.next();
                     let mut vars = Vec::new();
-                    let bindings = new_item.bindings.last_mut().unwrap();
                     collect_vars(&mut vars, tokens);
                     for var in vars {
-                        bindings.push_empty(&var);
+                        bindings_builder.push_empty(&mut new_item.bindings, &var);
                     }
                     cur_items.push(new_item);
                 }
@@ -314,7 +462,7 @@ fn match_loop_inner<'t>(
                     sep: separator.clone(),
                     sep_kind: Some(*kind),
                     sep_parsed: None,
-                    bindings: smallvec![Bindings::default()],
+                    bindings: bindings_builder.alloc(),
                     meta_result: None,
                     is_error: false,
                 })
@@ -339,7 +487,7 @@ fn match_loop_inner<'t>(
                                 item.meta_result = Some((fork, match_res));
                                 try_push!(bb_items, item);
                             } else {
-                                item.bindings.last_mut().unwrap().push_optional(name);
+                                bindings_builder.push_optional(&mut item.bindings, &name);
                                 item.dot.next();
                                 cur_items.push(item);
                             }
@@ -348,11 +496,11 @@ fn match_loop_inner<'t>(
                             res.add_err(err);
                             match match_res.value {
                                 Some(fragment) => {
-                                    item.bindings
-                                        .last_mut()
-                                        .unwrap()
-                                        .inner
-                                        .push((name.clone(), Binding::Fragment(fragment)));
+                                    bindings_builder.push_fragment(
+                                        &mut item.bindings,
+                                        &name,
+                                        fragment,
+                                    );
                                 }
                                 _ => {}
                             }
@@ -394,6 +542,8 @@ fn match_loop(pattern: &MetaTemplate, src: &tt::Subtree) -> Match {
     let mut res = Match::default();
     let mut error_reover_item = None;
 
+    let mut bindings_builder = BindingsBuilder::default();
+
     let mut cur_items = smallvec![MatchState {
         dot: pattern.iter_delimited(None),
         stack: Default::default(),
@@ -401,7 +551,7 @@ fn match_loop(pattern: &MetaTemplate, src: &tt::Subtree) -> Match {
         sep: None,
         sep_kind: None,
         sep_parsed: None,
-        bindings: smallvec![Bindings::default()],
+        bindings: bindings_builder.alloc(),
         is_error: false,
         meta_result: None,
     }];
@@ -419,6 +569,7 @@ fn match_loop(pattern: &MetaTemplate, src: &tt::Subtree) -> Match {
             src.clone(),
             &stack,
             &mut res,
+            &mut bindings_builder,
             &mut cur_items,
             &mut bb_items,
             &mut next_items,
@@ -428,9 +579,9 @@ fn match_loop(pattern: &MetaTemplate, src: &tt::Subtree) -> Match {
         stdx::always!(cur_items.is_empty());
 
         if error_items.len() > 0 {
-            error_reover_item = error_items.pop();
+            error_reover_item = error_items.pop().map(|it| it.bindings);
         } else if eof_items.len() > 0 {
-            error_reover_item = Some(eof_items[0].clone());
+            error_reover_item = Some(eof_items[0].bindings.clone());
         }
 
         // We need to do some post processing after the `match_loop_inner`.
@@ -440,11 +591,11 @@ fn match_loop(pattern: &MetaTemplate, src: &tt::Subtree) -> Match {
             if eof_items.len() == 1 {
                 // remove all errors, because it is the correct answer !
                 res = Match::default();
-                res.bindings = eof_items[0].bindings[0].clone();
+                res.bindings = bindings_builder.build(&eof_items[0].bindings);
             } else {
                 // Error recovery
                 if error_reover_item.is_some() {
-                    res.bindings = error_reover_item.unwrap().bindings[0].clone();
+                    res.bindings = bindings_builder.build(&error_reover_item.unwrap());
                 }
                 res.add_err(ExpandError::UnexpectedToken);
             }
@@ -467,8 +618,8 @@ fn match_loop(pattern: &MetaTemplate, src: &tt::Subtree) -> Match {
             }
             res.add_err(err!("leftover tokens"));
 
-            if let Some(mut error_reover_item) = error_reover_item {
-                res.bindings = error_reover_item.bindings.remove(0);
+            if let Some(error_reover_item) = error_reover_item {
+                res.bindings = bindings_builder.build(&error_reover_item);
             }
             return res;
         }
@@ -494,12 +645,13 @@ fn match_loop(pattern: &MetaTemplate, src: &tt::Subtree) -> Match {
 
             if let Some(OpDelimited::Op(Op::Var { name, .. })) = item.dot.peek() {
                 let (iter, match_res) = item.meta_result.take().unwrap();
-                let bindings = item.bindings.last_mut().unwrap();
                 match match_res.value {
                     Some(fragment) => {
-                        bindings.inner.push((name.clone(), Binding::Fragment(fragment)));
+                        bindings_builder.push_fragment(&mut item.bindings, &name, fragment);
+                    }
+                    None if match_res.err.is_none() => {
+                        bindings_builder.push_optional(&mut item.bindings, &name);
                     }
-                    None if match_res.err.is_none() => bindings.push_optional(name),
                     _ => {}
                 }
                 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..dd7fa97d7 100644
--- a/crates/mbe/src/expander/transcriber.rs
+++ b/crates/mbe/src/expander/transcriber.rs
@@ -2,7 +2,7 @@
 //! `$ident => foo`, interpolates variables in the template, to get `fn foo() {}`
 
 use syntax::SmolStr;
-use tt::Delimiter;
+use tt::{Delimiter, Subtree};
 
 use super::ExpandResult;
 use crate::{
@@ -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 {
@@ -179,7 +175,10 @@ fn expand_repeat(
         counter += 1;
         if counter == limit {
             log::warn!("expand_tt in repeat pattern exceed limit => {:#?}\n{:#?}", template, ctx);
-            break;
+            return ExpandResult {
+                value: Fragment::Tokens(Subtree::default().into()),
+                err: Some(ExpandError::Other("Expand exceed limit".to_string())),
+            };
         }
 
         if e.is_some() {