13 files changed, 325 insertions, 157 deletions

diff --git a/crates/hir_def/src/item_tree.rs b/crates/hir_def/src/item_tree.rs
index 6bb334573..09bcb10dc 100644
--- a/crates/hir_def/src/item_tree.rs
+++ b/crates/hir_def/src/item_tree.rs
@@ -209,18 +209,6 @@ impl ItemTree {
         }
     }
 
-    pub fn source<S: ItemTreeNode>(&self, db: &dyn DefDatabase, of: ItemTreeId<S>) -> S::Source {
-        // This unwrap cannot fail, since it has either succeeded above, or resulted in an empty
-        // ItemTree (in which case there is no valid `FileItemTreeId` to call this method with).
-        let root =
-            db.parse_or_expand(of.file_id).expect("parse_or_expand failed on constructed ItemTree");
-
-        let id = self[of.value].ast_id();
-        let map = db.ast_id_map(of.file_id);
-        let ptr = map.get(id);
-        ptr.to_node(&root)
-    }
-
     fn data(&self) -> &ItemTreeData {
         self.data.as_ref().expect("attempted to access data of empty ItemTree")
     }
diff --git a/crates/hir_def/src/test_db.rs b/crates/hir_def/src/test_db.rs
index eda982c85..10977761c 100644
--- a/crates/hir_def/src/test_db.rs
+++ b/crates/hir_def/src/test_db.rs
@@ -15,7 +15,7 @@ use rustc_hash::FxHashSet;
 use syntax::{algo, ast, AstNode, TextRange, TextSize};
 use test_utils::extract_annotations;
 
-use crate::{db::DefDatabase, nameres::DefMap, Lookup, ModuleDefId, ModuleId};
+use crate::{db::DefDatabase, nameres::DefMap, src::HasSource, Lookup, ModuleDefId, ModuleId};
 
 #[salsa::database(
     base_db::SourceDatabaseExtStorage,
@@ -115,14 +115,9 @@ impl TestDB {
             if file_id != position.file_id.into() {
                 continue;
             }
-            let root = self.parse_or_expand(file_id).unwrap();
-            let ast_map = self.ast_id_map(file_id);
-            let item_tree = self.item_tree(file_id);
             for decl in module.scope.declarations() {
                 if let ModuleDefId::FunctionId(it) = decl {
-                    let ast =
-                        ast_map.get(item_tree[it.lookup(self).id.value].ast_id).to_node(&root);
-                    let range = ast.syntax().text_range();
+                    let range = it.lookup(self).source(self).value.syntax().text_range();
 
                     if !range.contains(position.offset) {
                         continue;
diff --git a/crates/hir_expand/src/db.rs b/crates/hir_expand/src/db.rs
index cb6e23320..9086e6c17 100644
--- a/crates/hir_expand/src/db.rs
+++ b/crates/hir_expand/src/db.rs
@@ -340,6 +340,8 @@ fn parse_macro_with_arg(
         None => return ExpandResult { value: None, err: result.err },
     };
 
+    log::debug!("expanded = {}", tt.as_debug_string());
+
     let fragment_kind = to_fragment_kind(db, macro_call_id);
 
     let (parse, rev_token_map) = match mbe::token_tree_to_syntax_node(&tt, fragment_kind) {
diff --git a/crates/hir_ty/src/lower.rs b/crates/hir_ty/src/lower.rs
index 5fa83567b..d84ec9b7a 100644
--- a/crates/hir_ty/src/lower.rs
+++ b/crates/hir_ty/src/lower.rs
@@ -8,7 +8,7 @@
 use std::{iter, sync::Arc};
 
 use base_db::CrateId;
-use chalk_ir::Mutability;
+use chalk_ir::{cast::Cast, Mutability};
 use hir_def::{
     adt::StructKind,
     builtin_type::BuiltinType,
@@ -27,6 +27,7 @@ use stdx::impl_from;
 
 use crate::{
     db::HirDatabase,
+    traits::chalk::{Interner, ToChalk},
     utils::{
         all_super_trait_refs, associated_type_by_name_including_super_traits, generics,
         make_mut_slice, variant_data,
@@ -914,10 +915,21 @@ impl TraitEnvironment {
     pub fn lower(db: &dyn HirDatabase, resolver: &Resolver) -> Arc<TraitEnvironment> {
         let ctx = TyLoweringContext::new(db, &resolver)
             .with_type_param_mode(TypeParamLoweringMode::Placeholder);
-        let mut predicates = resolver
-            .where_predicates_in_scope()
-            .flat_map(|pred| GenericPredicate::from_where_predicate(&ctx, pred))
-            .collect::<Vec<_>>();
+        let mut traits_in_scope = Vec::new();
+        let mut clauses = Vec::new();
+        for pred in resolver.where_predicates_in_scope() {
+            for pred in GenericPredicate::from_where_predicate(&ctx, pred) {
+                if pred.is_error() {
+                    continue;
+                }
+                if let GenericPredicate::Implemented(tr) = &pred {
+                    traits_in_scope.push((tr.self_ty().clone(), tr.trait_));
+                }
+                let program_clause: chalk_ir::ProgramClause<Interner> =
+                    pred.clone().to_chalk(db).cast(&Interner);
+                clauses.push(program_clause.into_from_env_clause(&Interner));
+            }
+        }
 
         if let Some(def) = resolver.generic_def() {
             let container: Option<AssocContainerId> = match def {
@@ -938,12 +950,15 @@ impl TraitEnvironment {
                 let substs = Substs::type_params(db, trait_id);
                 let trait_ref = TraitRef { trait_: trait_id, substs };
                 let pred = GenericPredicate::Implemented(trait_ref);
-
-                predicates.push(pred);
+                let program_clause: chalk_ir::ProgramClause<Interner> =
+                    pred.clone().to_chalk(db).cast(&Interner);
+                clauses.push(program_clause.into_from_env_clause(&Interner));
             }
         }
 
-        Arc::new(TraitEnvironment { predicates })
+        let env = chalk_ir::Environment::new(&Interner).add_clauses(&Interner, clauses);
+
+        Arc::new(TraitEnvironment { traits_from_clauses: traits_in_scope, env })
     }
 }
 
diff --git a/crates/hir_ty/src/method_resolution.rs b/crates/hir_ty/src/method_resolution.rs
index ccc12c075..d57c6de70 100644
--- a/crates/hir_ty/src/method_resolution.rs
+++ b/crates/hir_ty/src/method_resolution.rs
@@ -528,8 +528,7 @@ fn iterate_trait_method_candidates(
         self_ty.value.dyn_trait().into_iter().flat_map(|t| all_super_traits(db.upcast(), t));
     let env_traits = if let Ty::Placeholder(_) = self_ty.value {
         // if we have `T: Trait` in the param env, the trait doesn't need to be in scope
-        env.trait_predicates_for_self_ty(&self_ty.value)
-            .map(|tr| tr.trait_)
+        env.traits_in_scope_from_clauses(&self_ty.value)
             .flat_map(|t| all_super_traits(db.upcast(), t))
             .collect()
     } else {
diff --git a/crates/hir_ty/src/tests.rs b/crates/hir_ty/src/tests.rs
index fc770ea60..0a4141e69 100644
--- a/crates/hir_ty/src/tests.rs
+++ b/crates/hir_ty/src/tests.rs
@@ -19,6 +19,7 @@ use hir_def::{
     item_scope::ItemScope,
     keys,
     nameres::DefMap,
+    src::HasSource,
     AssocItemId, DefWithBodyId, LocalModuleId, Lookup, ModuleDefId,
 };
 use hir_expand::{db::AstDatabase, InFile};
@@ -195,18 +196,15 @@ fn infer_with_mismatches(content: &str, include_mismatches: bool) -> String {
     defs.sort_by_key(|def| match def {
         DefWithBodyId::FunctionId(it) => {
             let loc = it.lookup(&db);
-            let tree = db.item_tree(loc.id.file_id);
-            tree.source(&db, loc.id).syntax().text_range().start()
+            loc.source(&db).value.syntax().text_range().start()
         }
         DefWithBodyId::ConstId(it) => {
             let loc = it.lookup(&db);
-            let tree = db.item_tree(loc.id.file_id);
-            tree.source(&db, loc.id).syntax().text_range().start()
+            loc.source(&db).value.syntax().text_range().start()
         }
         DefWithBodyId::StaticId(it) => {
             let loc = it.lookup(&db);
-            let tree = db.item_tree(loc.id.file_id);
-            tree.source(&db, loc.id).syntax().text_range().start()
+            loc.source(&db).value.syntax().text_range().start()
         }
     });
     for def in defs {
diff --git a/crates/hir_ty/src/traits.rs b/crates/hir_ty/src/traits.rs
index e4cdb6d53..27f350f70 100644
--- a/crates/hir_ty/src/traits.rs
+++ b/crates/hir_ty/src/traits.rs
@@ -38,22 +38,25 @@ fn create_chalk_solver() -> chalk_recursive::RecursiveSolver<Interner> {
 /// fn foo<T: Default>(t: T) {}
 /// ```
 /// we assume that `T: Default`.
-#[derive(Clone, Debug, PartialEq, Eq, Hash)]
+#[derive(Debug, Clone, PartialEq, Eq, Hash)]
 pub struct TraitEnvironment {
-    pub predicates: Vec<GenericPredicate>,
+    // When we're using Chalk's Ty we can make this a BTreeMap since it's Ord,
+    // but for now it's too annoying...
+    pub(crate) traits_from_clauses: Vec<(Ty, TraitId)>,
+    pub(crate) env: chalk_ir::Environment<Interner>,
 }
 
 impl TraitEnvironment {
-    /// Returns trait refs with the given self type which are supposed to hold
-    /// in this trait env. E.g. if we are in `foo<T: SomeTrait>()`, this will
-    /// find that `T: SomeTrait` if we call it for `T`.
-    pub(crate) fn trait_predicates_for_self_ty<'a>(
+    pub(crate) fn traits_in_scope_from_clauses<'a>(
         &'a self,
         ty: &'a Ty,
-    ) -> impl Iterator<Item = &'a TraitRef> + 'a {
-        self.predicates.iter().filter_map(move |pred| match pred {
-            GenericPredicate::Implemented(tr) if tr.self_ty() == ty => Some(tr),
-            _ => None,
+    ) -> impl Iterator<Item = TraitId> + 'a {
+        self.traits_from_clauses.iter().filter_map(move |(self_ty, trait_id)| {
+            if self_ty == ty {
+                Some(*trait_id)
+            } else {
+                None
+            }
         })
     }
 }
diff --git a/crates/hir_ty/src/traits/chalk.rs b/crates/hir_ty/src/traits/chalk.rs
index 565672b6b..1a2a3a8c7 100644
--- a/crates/hir_ty/src/traits/chalk.rs
+++ b/crates/hir_ty/src/traits/chalk.rs
@@ -33,13 +33,13 @@ pub(super) mod tls;
 mod interner;
 mod mapping;
 
-pub(super) trait ToChalk {
+pub(crate) trait ToChalk {
     type Chalk;
     fn to_chalk(self, db: &dyn HirDatabase) -> Self::Chalk;
     fn from_chalk(db: &dyn HirDatabase, chalk: Self::Chalk) -> Self;
 }
 
-pub(super) fn from_chalk<T, ChalkT>(db: &dyn HirDatabase, chalk: ChalkT) -> T
+pub(crate) fn from_chalk<T, ChalkT>(db: &dyn HirDatabase, chalk: ChalkT) -> T
 where
     T: ToChalk<Chalk = ChalkT>,
 {
@@ -487,19 +487,14 @@ pub(crate) fn struct_datum_query(
     struct_id: AdtId,
 ) -> Arc<StructDatum> {
     debug!("struct_datum {:?}", struct_id);
-    let type_ctor = Ty::Adt(struct_id, Substs::empty());
     let chalk_ir::AdtId(adt_id) = struct_id;
-    debug!("struct {:?} = {:?}", struct_id, type_ctor);
     let num_params = generics(db.upcast(), adt_id.into()).len();
     let upstream = adt_id.module(db.upcast()).krate() != krate;
-    let where_clauses = type_ctor
-        .as_generic_def()
-        .map(|generic_def| {
-            let generic_params = generics(db.upcast(), generic_def);
-            let bound_vars = Substs::bound_vars(&generic_params, DebruijnIndex::INNERMOST);
-            convert_where_clauses(db, generic_def, &bound_vars)
-        })
-        .unwrap_or_else(Vec::new);
+    let where_clauses = {
+        let generic_params = generics(db.upcast(), adt_id.into());
+        let bound_vars = Substs::bound_vars(&generic_params, DebruijnIndex::INNERMOST);
+        convert_where_clauses(db, adt_id.into(), &bound_vars)
+    };
     let flags = rust_ir::AdtFlags {
         upstream,
         // FIXME set fundamental and phantom_data flags correctly
diff --git a/crates/hir_ty/src/traits/chalk/mapping.rs b/crates/hir_ty/src/traits/chalk/mapping.rs
index 3a08b67e9..b0415e8b0 100644
--- a/crates/hir_ty/src/traits/chalk/mapping.rs
+++ b/crates/hir_ty/src/traits/chalk/mapping.rs
@@ -17,7 +17,7 @@ use crate::{
     primitive::UintTy,
     traits::{Canonical, Obligation},
     AliasTy, CallableDefId, FnPointer, FnSig, GenericPredicate, InEnvironment, OpaqueTy,
-    OpaqueTyId, ProjectionPredicate, ProjectionTy, Scalar, Substs, TraitEnvironment, TraitRef, Ty,
+    OpaqueTyId, ProjectionPredicate, ProjectionTy, Scalar, Substs, TraitRef, Ty,
 };
 
 use super::interner::*;
@@ -536,31 +536,6 @@ where
     }
 }
 
-impl ToChalk for Arc<TraitEnvironment> {
-    type Chalk = chalk_ir::Environment<Interner>;
-
-    fn to_chalk(self, db: &dyn HirDatabase) -> chalk_ir::Environment<Interner> {
-        let mut clauses = Vec::new();
-        for pred in &self.predicates {
-            if pred.is_error() {
-                // for env, we just ignore errors
-                continue;
-            }
-            let program_clause: chalk_ir::ProgramClause<Interner> =
-                pred.clone().to_chalk(db).cast(&Interner);
-            clauses.push(program_clause.into_from_env_clause(&Interner));
-        }
-        chalk_ir::Environment::new(&Interner).add_clauses(&Interner, clauses)
-    }
-
-    fn from_chalk(
-        _db: &dyn HirDatabase,
-        _env: chalk_ir::Environment<Interner>,
-    ) -> Arc<TraitEnvironment> {
-        unimplemented!()
-    }
-}
-
 impl<T: ToChalk> ToChalk for InEnvironment<T>
 where
     T::Chalk: chalk_ir::interner::HasInterner<Interner = Interner>,
@@ -569,19 +544,16 @@ where
 
     fn to_chalk(self, db: &dyn HirDatabase) -> chalk_ir::InEnvironment<T::Chalk> {
         chalk_ir::InEnvironment {
-            environment: self.environment.to_chalk(db),
+            environment: self.environment.env.clone(),
             goal: self.value.to_chalk(db),
         }
     }
 
     fn from_chalk(
-        db: &dyn HirDatabase,
-        in_env: chalk_ir::InEnvironment<T::Chalk>,
+        _db: &dyn HirDatabase,
+        _in_env: chalk_ir::InEnvironment<T::Chalk>,
     ) -> InEnvironment<T> {
-        InEnvironment {
-            environment: from_chalk(db, in_env.environment),
-            value: from_chalk(db, in_env.goal),
-        }
+        unimplemented!()
     }
 }
 
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..54db76d5d 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,187 @@ 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::with_capacity(8));
+        let nidx = self.nested.len();
+        self.nested.push(Vec::with_capacity(8));
+        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 {
+                let mut item = Vec::with_capacity(8);
+                item.push(LinkNode::Parent { idx, len });
+                target.push(item);
+            }
+
+            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::with_capacity(8));
+        idx.0 = new_idx;
+    }
+
+    fn build(self, idx: &BindingsIdx) -> Bindings {
+        let mut bindings = Bindings::default();
+        self.build_recur(&mut bindings, self.nodes[idx.0].clone());
+        bindings
+    }
+
+    fn build_recur(&self, bindings: &mut Bindings, nodes: Vec<LinkNode<Rc<BindingKind>>>) {
+        for cmd in self.flatten_nodes(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, list) => {
+                    let list = self.flatten_nested(*idx, *list);
+
+                    for (idx, iter) in list.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 flatten_nested_ref(&self, id: usize, len: usize) -> Vec<Vec<LinkNode<Rc<BindingKind>>>> {
+        self.nested[id]
+            .iter()
+            .take(len)
+            .map(|it| match it {
+                LinkNode::Node(id) => vec![self.nodes[*id].clone()],
+                LinkNode::Parent { idx, len } => self.flatten_nested_ref(*idx, *len),
+            })
+            .flatten()
+            .collect()
+    }
+
+    fn flatten_nested<'a>(
+        &'a self,
+        idx: usize,
+        list: usize,
+    ) -> impl Iterator<Item = Bindings> + 'a {
+        let last = self.nodes[idx].clone();
+        self.nested[list]
+            .iter()
+            .map(move |it| match *it {
+                LinkNode::Node(idx) => vec![self.nodes[idx].clone()],
+                LinkNode::Parent { idx, len } => self.flatten_nested_ref(idx, len),
+            })
+            .flatten()
+            .chain(std::iter::once(last))
+            .map(move |iter| {
+                let mut child_bindings = Bindings::default();
+                self.build_recur(&mut child_bindings, iter);
+                child_bindings
+            })
+    }
+
+    fn flatten_nodes_ref(&self, id: usize, len: usize) -> Vec<Rc<BindingKind>> {
+        self.nodes[id]
+            .iter()
+            .take(len)
+            .map(|it| match it {
+                LinkNode::Node(it) => vec![it.clone()],
+                LinkNode::Parent { idx, len } => self.flatten_nodes_ref(*idx, *len),
+            })
+            .flatten()
+            .collect()
+    }
+
+    fn flatten_nodes<'a>(
+        &'a self,
+        nodes: Vec<LinkNode<Rc<BindingKind>>>,
+    ) -> impl Iterator<Item = Rc<BindingKind>> + 'a {
+        nodes
+            .into_iter()
+            .map(move |it| match it {
+                LinkNode::Node(it) => vec![it],
+                LinkNode::Parent { idx, len } => self.flatten_nodes_ref(idx, len),
+            })
+            .flatten()
+    }
+}
+
+#[derive(Debug, Clone)]
 struct MatchState<'t> {
     /// The position of the "dot" in this matcher
     dot: OpDelimitedIter<'t>,
@@ -187,7 +342,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 +373,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 +407,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 +434,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 +452,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 +468,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 +493,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 +502,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 +548,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 +557,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 +575,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 +585,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 +597,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 +624,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 +651,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..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 {
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)]