Adding upstream version 1.64.0+dfsg1.upstream/1.64.0+dfsg1

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

11 files changed, 3382 insertions, 0 deletions

diff --git a/src/tools/rust-analyzer/crates/mbe/Cargo.toml b/src/tools/rust-analyzer/crates/mbe/Cargo.toml
new file mode 100644
index 000000000..5ff3448a1
--- /dev/null
+++ b/src/tools/rust-analyzer/crates/mbe/Cargo.toml
@@ -0,0 +1,24 @@
+[package]
+name = "mbe"
+version = "0.0.0"
+description = "TBD"
+license = "MIT OR Apache-2.0"
+edition = "2021"
+rust-version = "1.57"
+
+[lib]
+doctest = false
+
+[dependencies]
+cov-mark = "2.0.0-pre.1"
+rustc-hash = "1.1.0"
+smallvec = "1.9.0"
+tracing = "0.1.35"
+
+syntax = { path = "../syntax", version = "0.0.0" }
+parser = { path = "../parser", version = "0.0.0" }
+tt = { path = "../tt", version = "0.0.0" }
+stdx = { path = "../stdx", version = "0.0.0" }
+
+[dev-dependencies]
+test-utils = { path = "../test-utils" }
diff --git a/src/tools/rust-analyzer/crates/mbe/src/benchmark.rs b/src/tools/rust-analyzer/crates/mbe/src/benchmark.rs
new file mode 100644
index 000000000..ac691578d
--- /dev/null
+++ b/src/tools/rust-analyzer/crates/mbe/src/benchmark.rs
@@ -0,0 +1,222 @@
+//! This module add real world mbe example for benchmark tests
+
+use rustc_hash::FxHashMap;
+use syntax::{
+    ast::{self, HasName},
+    AstNode, SmolStr,
+};
+use test_utils::{bench, bench_fixture, skip_slow_tests};
+
+use crate::{
+    parser::{Op, RepeatKind, Separator},
+    syntax_node_to_token_tree, DeclarativeMacro,
+};
+
+#[test]
+fn benchmark_parse_macro_rules() {
+    if skip_slow_tests() {
+        return;
+    }
+    let rules = macro_rules_fixtures_tt();
+    let hash: usize = {
+        let _pt = bench("mbe parse macro rules");
+        rules.values().map(|it| DeclarativeMacro::parse_macro_rules(it).unwrap().rules.len()).sum()
+    };
+    assert_eq!(hash, 1144);
+}
+
+#[test]
+fn benchmark_expand_macro_rules() {
+    if skip_slow_tests() {
+        return;
+    }
+    let rules = macro_rules_fixtures();
+    let invocations = invocation_fixtures(&rules);
+
+    let hash: usize = {
+        let _pt = bench("mbe expand macro rules");
+        invocations
+            .into_iter()
+            .map(|(id, tt)| {
+                let res = rules[&id].expand(&tt);
+                assert!(res.err.is_none());
+                res.value.token_trees.len()
+            })
+            .sum()
+    };
+    assert_eq!(hash, 69413);
+}
+
+fn macro_rules_fixtures() -> FxHashMap<String, DeclarativeMacro> {
+    macro_rules_fixtures_tt()
+        .into_iter()
+        .map(|(id, tt)| (id, DeclarativeMacro::parse_macro_rules(&tt).unwrap()))
+        .collect()
+}
+
+fn macro_rules_fixtures_tt() -> FxHashMap<String, tt::Subtree> {
+    let fixture = bench_fixture::numerous_macro_rules();
+    let source_file = ast::SourceFile::parse(&fixture).ok().unwrap();
+
+    source_file
+        .syntax()
+        .descendants()
+        .filter_map(ast::MacroRules::cast)
+        .map(|rule| {
+            let id = rule.name().unwrap().to_string();
+            let (def_tt, _) = syntax_node_to_token_tree(rule.token_tree().unwrap().syntax());
+            (id, def_tt)
+        })
+        .collect()
+}
+
+/// Generate random invocation fixtures from rules
+fn invocation_fixtures(rules: &FxHashMap<String, DeclarativeMacro>) -> Vec<(String, tt::Subtree)> {
+    let mut seed = 123456789;
+    let mut res = Vec::new();
+
+    for (name, it) in rules {
+        for rule in &it.rules {
+            // Generate twice
+            for _ in 0..2 {
+                // The input are generated by filling the `Op` randomly.
+                // However, there are some cases generated are ambiguous for expanding, for example:
+                // ```rust
+                // macro_rules! m {
+                //    ($($t:ident),* as $ty:ident) => {}
+                // }
+                // m!(as u32);  // error: local ambiguity: multiple parsing options: built-in NTs ident ('t') or 1 other option.
+                // ```
+                //
+                // So we just skip any error cases and try again
+                let mut try_cnt = 0;
+                loop {
+                    let mut subtree = tt::Subtree::default();
+                    for op in rule.lhs.iter() {
+                        collect_from_op(op, &mut subtree, &mut seed);
+                    }
+                    if it.expand(&subtree).err.is_none() {
+                        res.push((name.clone(), subtree));
+                        break;
+                    }
+                    try_cnt += 1;
+                    if try_cnt > 100 {
+                        panic!("invocaton fixture {} cannot be generated.\n", name);
+                    }
+                }
+            }
+        }
+    }
+    return res;
+
+    fn collect_from_op(op: &Op, parent: &mut tt::Subtree, seed: &mut usize) {
+        return match op {
+            Op::Var { kind, .. } => match kind.as_ref().map(|it| it.as_str()) {
+                Some("ident") => parent.token_trees.push(make_ident("foo")),
+                Some("ty") => parent.token_trees.push(make_ident("Foo")),
+                Some("tt") => parent.token_trees.push(make_ident("foo")),
+                Some("vis") => parent.token_trees.push(make_ident("pub")),
+                Some("pat") => parent.token_trees.push(make_ident("foo")),
+                Some("path") => parent.token_trees.push(make_ident("foo")),
+                Some("literal") => parent.token_trees.push(make_literal("1")),
+                Some("expr") => parent.token_trees.push(make_ident("foo")),
+                Some("lifetime") => {
+                    parent.token_trees.push(make_punct('\''));
+                    parent.token_trees.push(make_ident("a"));
+                }
+                Some("block") => {
+                    parent.token_trees.push(make_subtree(tt::DelimiterKind::Brace, None))
+                }
+                Some("item") => {
+                    parent.token_trees.push(make_ident("fn"));
+                    parent.token_trees.push(make_ident("foo"));
+                    parent.token_trees.push(make_subtree(tt::DelimiterKind::Parenthesis, None));
+                    parent.token_trees.push(make_subtree(tt::DelimiterKind::Brace, None));
+                }
+                Some("meta") => {
+                    parent.token_trees.push(make_ident("foo"));
+                    parent.token_trees.push(make_subtree(tt::DelimiterKind::Parenthesis, None));
+                }
+
+                None => (),
+                Some(kind) => panic!("Unhandled kind {}", kind),
+            },
+            Op::Leaf(leaf) => parent.token_trees.push(leaf.clone().into()),
+            Op::Repeat { tokens, kind, separator } => {
+                let max = 10;
+                let cnt = match kind {
+                    RepeatKind::ZeroOrMore => rand(seed) % max,
+                    RepeatKind::OneOrMore => 1 + rand(seed) % max,
+                    RepeatKind::ZeroOrOne => rand(seed) % 2,
+                };
+                for i in 0..cnt {
+                    for it in tokens.iter() {
+                        collect_from_op(it, parent, seed);
+                    }
+                    if i + 1 != cnt {
+                        if let Some(sep) = separator {
+                            match sep {
+                                Separator::Literal(it) => {
+                                    parent.token_trees.push(tt::Leaf::Literal(it.clone()).into())
+                                }
+                                Separator::Ident(it) => {
+                                    parent.token_trees.push(tt::Leaf::Ident(it.clone()).into())
+                                }
+                                Separator::Puncts(puncts) => {
+                                    for it in puncts {
+                                        parent.token_trees.push(tt::Leaf::Punct(*it).into())
+                                    }
+                                }
+                            };
+                        }
+                    }
+                }
+            }
+            Op::Subtree { tokens, delimiter } => {
+                let mut subtree = tt::Subtree { delimiter: *delimiter, token_trees: Vec::new() };
+                tokens.iter().for_each(|it| {
+                    collect_from_op(it, &mut subtree, seed);
+                });
+                parent.token_trees.push(subtree.into());
+            }
+            Op::Ignore { .. } | Op::Index { .. } => {}
+        };
+
+        // Simple linear congruential generator for determistic result
+        fn rand(seed: &mut usize) -> usize {
+            let a = 1664525;
+            let c = 1013904223;
+            *seed = usize::wrapping_add(usize::wrapping_mul(*seed, a), c);
+            *seed
+        }
+        fn make_ident(ident: &str) -> tt::TokenTree {
+            tt::Leaf::Ident(tt::Ident { id: tt::TokenId::unspecified(), text: SmolStr::new(ident) })
+                .into()
+        }
+        fn make_punct(char: char) -> tt::TokenTree {
+            tt::Leaf::Punct(tt::Punct {
+                id: tt::TokenId::unspecified(),
+                char,
+                spacing: tt::Spacing::Alone,
+            })
+            .into()
+        }
+        fn make_literal(lit: &str) -> tt::TokenTree {
+            tt::Leaf::Literal(tt::Literal {
+                id: tt::TokenId::unspecified(),
+                text: SmolStr::new(lit),
+            })
+            .into()
+        }
+        fn make_subtree(
+            kind: tt::DelimiterKind,
+            token_trees: Option<Vec<tt::TokenTree>>,
+        ) -> tt::TokenTree {
+            tt::Subtree {
+                delimiter: Some(tt::Delimiter { id: tt::TokenId::unspecified(), kind }),
+                token_trees: token_trees.unwrap_or_default(),
+            }
+            .into()
+        }
+    }
+}
diff --git a/src/tools/rust-analyzer/crates/mbe/src/expander.rs b/src/tools/rust-analyzer/crates/mbe/src/expander.rs
new file mode 100644
index 000000000..1e1bfa550
--- /dev/null
+++ b/src/tools/rust-analyzer/crates/mbe/src/expander.rs
@@ -0,0 +1,121 @@
+//! This module takes a (parsed) definition of `macro_rules` invocation, a
+//! `tt::TokenTree` representing an argument of macro invocation, and produces a
+//! `tt::TokenTree` for the result of the expansion.
+
+mod matcher;
+mod transcriber;
+
+use rustc_hash::FxHashMap;
+use syntax::SmolStr;
+
+use crate::{ExpandError, ExpandResult};
+
+pub(crate) fn expand_rules(
+    rules: &[crate::Rule],
+    input: &tt::Subtree,
+) -> ExpandResult<tt::Subtree> {
+    let mut match_: Option<(matcher::Match, &crate::Rule)> = None;
+    for rule in rules {
+        let new_match = matcher::match_(&rule.lhs, input);
+
+        if new_match.err.is_none() {
+            // If we find a rule that applies without errors, we're done.
+            // Unconditionally returning the transcription here makes the
+            // `test_repeat_bad_var` test fail.
+            let ExpandResult { value, err: transcribe_err } =
+                transcriber::transcribe(&rule.rhs, &new_match.bindings);
+            if transcribe_err.is_none() {
+                return ExpandResult::ok(value);
+            }
+        }
+        // Use the rule if we matched more tokens, or bound variables count
+        if let Some((prev_match, _)) = &match_ {
+            if (new_match.unmatched_tts, -(new_match.bound_count as i32))
+                < (prev_match.unmatched_tts, -(prev_match.bound_count as i32))
+            {
+                match_ = Some((new_match, rule));
+            }
+        } else {
+            match_ = Some((new_match, rule));
+        }
+    }
+    if let Some((match_, rule)) = match_ {
+        // if we got here, there was no match without errors
+        let ExpandResult { value, err: transcribe_err } =
+            transcriber::transcribe(&rule.rhs, &match_.bindings);
+        ExpandResult { value, err: match_.err.or(transcribe_err) }
+    } else {
+        ExpandResult::only_err(ExpandError::NoMatchingRule)
+    }
+}
+
+/// The actual algorithm for expansion is not too hard, but is pretty tricky.
+/// `Bindings` structure is the key to understanding what we are doing here.
+///
+/// On the high level, it stores mapping from meta variables to the bits of
+/// syntax it should be substituted with. For example, if `$e:expr` is matched
+/// with `1 + 1` by macro_rules, the `Binding` will store `$e -> 1 + 1`.
+///
+/// The tricky bit is dealing with repetitions (`$()*`). Consider this example:
+///
+/// ```not_rust
+/// macro_rules! foo {
+///     ($($ i:ident $($ e:expr),*);*) => {
+///         $(fn $ i() { $($ e);*; })*
+///     }
+/// }
+/// foo! { foo 1,2,3; bar 4,5,6 }
+/// ```
+///
+/// Here, the `$i` meta variable is matched first with `foo` and then with
+/// `bar`, and `$e` is matched in turn with `1`, `2`, `3`, `4`, `5`, `6`.
+///
+/// To represent such "multi-mappings", we use a recursive structures: we map
+/// variables not to values, but to *lists* of values or other lists (that is,
+/// to the trees).
+///
+/// For the above example, the bindings would store
+///
+/// ```not_rust
+/// i -> [foo, bar]
+/// e -> [[1, 2, 3], [4, 5, 6]]
+/// ```
+///
+/// We construct `Bindings` in the `match_lhs`. The interesting case is
+/// `TokenTree::Repeat`, where we use `push_nested` to create the desired
+/// nesting structure.
+///
+/// The other side of the puzzle is `expand_subtree`, where we use the bindings
+/// to substitute meta variables in the output template. When expanding, we
+/// maintain a `nesting` stack of indices which tells us which occurrence from
+/// the `Bindings` we should take. We push to the stack when we enter a
+/// repetition.
+///
+/// In other words, `Bindings` is a *multi* mapping from `SmolStr` to
+/// `tt::TokenTree`, where the index to select a particular `TokenTree` among
+/// many is not a plain `usize`, but a `&[usize]`.
+#[derive(Debug, Default, Clone, PartialEq, Eq)]
+struct Bindings {
+    inner: FxHashMap<SmolStr, Binding>,
+}
+
+#[derive(Debug, Clone, PartialEq, Eq)]
+enum Binding {
+    Fragment(Fragment),
+    Nested(Vec<Binding>),
+    Empty,
+}
+
+#[derive(Debug, Clone, PartialEq, Eq)]
+enum Fragment {
+    /// token fragments are just copy-pasted into the output
+    Tokens(tt::TokenTree),
+    /// Expr ast fragments are surrounded with `()` on insertion to preserve
+    /// precedence. Note that this impl is different from the one currently in
+    /// `rustc` -- `rustc` doesn't translate fragments into token trees at all.
+    ///
+    /// At one point in time, we tried to to use "fake" delimiters here a-la
+    /// proc-macro delimiter=none. As we later discovered, "none" delimiters are
+    /// tricky to handle in the parser, and rustc doesn't handle those either.
+    Expr(tt::TokenTree),
+}
diff --git a/src/tools/rust-analyzer/crates/mbe/src/expander/matcher.rs b/src/tools/rust-analyzer/crates/mbe/src/expander/matcher.rs
new file mode 100644
index 000000000..5020e9aba
--- /dev/null
+++ b/src/tools/rust-analyzer/crates/mbe/src/expander/matcher.rs
@@ -0,0 +1,914 @@
+//! An NFA-based parser, which is porting from rustc mbe parsing code
+//!
+//! See <https://github.com/rust-lang/rust/blob/70b18bc2cbac4712020019f5bf57c00905373205/compiler/rustc_expand/src/mbe/macro_parser.rs>
+//! Here is a quick intro to how the parser works, copied from rustc:
+//!
+//! A 'position' is a dot in the middle of a matcher, usually represented as a
+//! dot. For example `· a $( a )* a b` is a position, as is `a $( · a )* a b`.
+//!
+//! The parser walks through the input a character at a time, maintaining a list
+//! of threads consistent with the current position in the input string: `cur_items`.
+//!
+//! As it processes them, it fills up `eof_items` with threads that would be valid if
+//! the macro invocation is now over, `bb_items` with threads that are waiting on
+//! a Rust non-terminal like `$e:expr`, and `next_items` with threads that are waiting
+//! on a particular token. Most of the logic concerns moving the · through the
+//! repetitions indicated by Kleene stars. The rules for moving the · without
+//! consuming any input are called epsilon transitions. It only advances or calls
+//! out to the real Rust parser when no `cur_items` threads remain.
+//!
+//! Example:
+//!
+//! ```text, ignore
+//! Start parsing a a a a b against [· a $( a )* a b].
+//!
+//! Remaining input: a a a a b
+//! next: [· a $( a )* a b]
+//!
+//! - - - Advance over an a. - - -
+//!
+//! Remaining input: a a a b
+//! cur: [a · $( a )* a b]
+//! Descend/Skip (first item).
+//! next: [a $( · a )* a b]  [a $( a )* · a b].
+//!
+//! - - - Advance over an a. - - -
+//!
+//! Remaining input: a a b
+//! cur: [a $( a · )* a b]  [a $( a )* a · b]
+//! Follow epsilon transition: Finish/Repeat (first item)
+//! next: [a $( a )* · a b]  [a $( · a )* a b]  [a $( a )* a · b]
+//!
+//! - - - Advance over an a. - - - (this looks exactly like the last step)
+//!
+//! Remaining input: a b
+//! cur: [a $( a · )* a b]  [a $( a )* a · b]
+//! Follow epsilon transition: Finish/Repeat (first item)
+//! next: [a $( a )* · a b]  [a $( · a )* a b]  [a $( a )* a · b]
+//!
+//! - - - Advance over an a. - - - (this looks exactly like the last step)
+//!
+//! Remaining input: b
+//! cur: [a $( a · )* a b]  [a $( a )* a · b]
+//! Follow epsilon transition: Finish/Repeat (first item)
+//! next: [a $( a )* · a b]  [a $( · a )* a b]  [a $( a )* a · b]
+//!
+//! - - - Advance over a b. - - -
+//!
+//! Remaining input: ''
+//! eof: [a $( a )* a b ·]
+//! ```
+
+use std::rc::Rc;
+
+use smallvec::{smallvec, SmallVec};
+use syntax::SmolStr;
+
+use crate::{
+    expander::{Binding, Bindings, ExpandResult, Fragment},
+    parser::{Op, RepeatKind, Separator},
+    tt_iter::TtIter,
+    ExpandError, MetaTemplate,
+};
+
+impl Bindings {
+    fn push_optional(&mut self, name: &SmolStr) {
+        // 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.insert(name.clone(), Binding::Fragment(Fragment::Tokens(tt)));
+    }
+
+    fn push_empty(&mut self, name: &SmolStr) {
+        self.inner.insert(name.clone(), Binding::Empty);
+    }
+
+    fn bindings(&self) -> impl Iterator<Item = &Binding> {
+        self.inner.values()
+    }
+}
+
+#[derive(Clone, Debug, Default, PartialEq, Eq)]
+pub(super) struct Match {
+    pub(super) bindings: Bindings,
+    /// We currently just keep the first error and count the rest to compare matches.
+    pub(super) err: Option<ExpandError>,
+    pub(super) err_count: usize,
+    /// How many top-level token trees were left to match.
+    pub(super) unmatched_tts: usize,
+    /// The number of bound variables
+    pub(super) bound_count: usize,
+}
+
+impl Match {
+    fn add_err(&mut self, err: ExpandError) {
+        let prev_err = self.err.take();
+        self.err = prev_err.or(Some(err));
+        self.err_count += 1;
+    }
+}
+
+/// Matching errors are added to the `Match`.
+pub(super) fn match_(pattern: &MetaTemplate, input: &tt::Subtree) -> Match {
+    let mut res = match_loop(pattern, input);
+    res.bound_count = count(res.bindings.bindings());
+    return res;
+
+    fn count<'a>(bindings: impl Iterator<Item = &'a Binding>) -> usize {
+        bindings
+            .map(|it| match it {
+                Binding::Fragment(_) => 1,
+                Binding::Empty => 1,
+                Binding::Nested(it) => count(it.iter()),
+            })
+            .sum()
+    }
+}
+
+#[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: &[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 [LinkNode<Rc<BindingKind>>],
+        nodes: &mut Vec<&'a Rc<BindingKind>>,
+    ) {
+        link_nodes.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>,
+
+    /// Token subtree stack
+    /// When matching against matchers with nested delimited submatchers (e.g., `pat ( pat ( .. )
+    /// pat ) pat`), we need to keep track of the matchers we are descending into. This stack does
+    /// that where the bottom of the stack is the outermost matcher.
+    stack: SmallVec<[OpDelimitedIter<'t>; 4]>,
+
+    /// The "parent" matcher position if we are in a repetition. That is, the matcher position just
+    /// before we enter the repetition.
+    up: Option<Box<MatchState<'t>>>,
+
+    /// The separator if we are in a repetition.
+    sep: Option<Separator>,
+
+    /// The KleeneOp of this sequence if we are in a repetition.
+    sep_kind: Option<RepeatKind>,
+
+    /// Number of tokens of seperator parsed
+    sep_parsed: Option<usize>,
+
+    /// Matched meta variables bindings
+    bindings: BindingsIdx,
+
+    /// Cached result of meta variable parsing
+    meta_result: Option<(TtIter<'t>, ExpandResult<Option<Fragment>>)>,
+
+    /// Is error occuried in this state, will `poised` to "parent"
+    is_error: bool,
+}
+
+/// Process the matcher positions of `cur_items` until it is empty. In the process, this will
+/// produce more items in `next_items`, `eof_items`, and `bb_items`.
+///
+/// For more info about the how this happens, see the module-level doc comments and the inline
+/// comments of this function.
+///
+/// # Parameters
+///
+/// - `src`: the current token of the parser.
+/// - `stack`: the "parent" frames of the token tree
+/// - `res`: the match result to store errors
+/// - `cur_items`: the set of current items to be processed. This should be empty by the end of a
+///   successful execution of this function.
+/// - `next_items`: the set of newly generated items. These are used to replenish `cur_items` in
+///   the function `parse`.
+/// - `eof_items`: the set of items that would be valid if this was the EOF.
+/// - `bb_items`: the set of items that are waiting for the black-box parser.
+/// - `error_items`: the set of items in errors, used for error-resilient parsing
+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>>,
+    eof_items: &mut SmallVec<[MatchState<'t>; 1]>,
+    error_items: &mut SmallVec<[MatchState<'t>; 1]>,
+) {
+    macro_rules! try_push {
+        ($items: expr, $it:expr) => {
+            if $it.is_error {
+                error_items.push($it);
+            } else {
+                $items.push($it);
+            }
+        };
+    }
+
+    while let Some(mut item) = cur_items.pop() {
+        while item.dot.is_eof() {
+            match item.stack.pop() {
+                Some(frame) => {
+                    item.dot = frame;
+                    item.dot.next();
+                }
+                None => break,
+            }
+        }
+        let op = match item.dot.peek() {
+            None => {
+                // We are at or past the end of the matcher of `item`.
+                if item.up.is_some() {
+                    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`
+                        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;
+                        cur_items.push(new_pos);
+                    }
+
+                    // Check if we need a separator.
+                    // We check the separator one by one
+                    let sep_idx = *item.sep_parsed.as_ref().unwrap_or(&0);
+                    let sep_len = item.sep.as_ref().map_or(0, Separator::tt_count);
+                    if item.sep.is_some() && sep_idx != sep_len {
+                        let sep = item.sep.as_ref().unwrap();
+                        if src.clone().expect_separator(sep, sep_idx) {
+                            item.dot.next();
+                            item.sep_parsed = Some(sep_idx + 1);
+                            try_push!(next_items, item);
+                        }
+                    }
+                    // We don't need a separator. Move the "dot" back to the beginning of the matcher
+                    // and try to match again UNLESS we are only allowed to have _one_ repetition.
+                    else if item.sep_kind != Some(RepeatKind::ZeroOrOne) {
+                        item.dot = item.dot.reset();
+                        item.sep_parsed = None;
+                        bindings_builder.push_default(&mut item.bindings);
+                        cur_items.push(item);
+                    }
+                } else {
+                    // If we are not in a repetition, then being at the end of a matcher means that we have
+                    // reached the potential end of the input.
+                    try_push!(eof_items, item);
+                }
+                continue;
+            }
+            Some(it) => it,
+        };
+
+        // We are in the middle of a matcher.
+        match op {
+            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();
+                    collect_vars(
+                        &mut |s| {
+                            bindings_builder.push_empty(&mut new_item.bindings, &s);
+                        },
+                        tokens,
+                    );
+                    cur_items.push(new_item);
+                }
+                cur_items.push(MatchState {
+                    dot: tokens.iter_delimited(None),
+                    stack: Default::default(),
+                    up: Some(Box::new(item)),
+                    sep: separator.clone(),
+                    sep_kind: Some(*kind),
+                    sep_parsed: None,
+                    bindings: bindings_builder.alloc(),
+                    meta_result: None,
+                    is_error: false,
+                })
+            }
+            OpDelimited::Op(Op::Subtree { tokens, delimiter }) => {
+                if let Ok(subtree) = src.clone().expect_subtree() {
+                    if subtree.delimiter_kind() == delimiter.map(|it| it.kind) {
+                        item.stack.push(item.dot);
+                        item.dot = tokens.iter_delimited(delimiter.as_ref());
+                        cur_items.push(item);
+                    }
+                }
+            }
+            OpDelimited::Op(Op::Var { kind, name, .. }) => {
+                if let Some(kind) = kind {
+                    let mut fork = src.clone();
+                    let match_res = match_meta_var(kind.as_str(), &mut fork);
+                    match match_res.err {
+                        None => {
+                            // Some meta variables are optional (e.g. vis)
+                            if match_res.value.is_some() {
+                                item.meta_result = Some((fork, match_res));
+                                try_push!(bb_items, item);
+                            } else {
+                                bindings_builder.push_optional(&mut item.bindings, name);
+                                item.dot.next();
+                                cur_items.push(item);
+                            }
+                        }
+                        Some(err) => {
+                            res.add_err(err);
+                            if let Some(fragment) = match_res.value {
+                                bindings_builder.push_fragment(&mut item.bindings, name, fragment);
+                            }
+                            item.is_error = true;
+                            error_items.push(item);
+                        }
+                    }
+                }
+            }
+            OpDelimited::Op(Op::Leaf(leaf)) => {
+                if let Err(err) = match_leaf(leaf, &mut src.clone()) {
+                    res.add_err(err);
+                    item.is_error = true;
+                } else {
+                    item.dot.next();
+                }
+                try_push!(next_items, item);
+            }
+            OpDelimited::Op(Op::Ignore { .. } | Op::Index { .. }) => {}
+            OpDelimited::Open => {
+                if matches!(src.clone().next(), Some(tt::TokenTree::Subtree(..))) {
+                    item.dot.next();
+                    try_push!(next_items, item);
+                }
+            }
+            OpDelimited::Close => {
+                let is_delim_closed = src.peek_n(0).is_none() && !stack.is_empty();
+                if is_delim_closed {
+                    item.dot.next();
+                    try_push!(next_items, item);
+                }
+            }
+        }
+    }
+}
+
+fn match_loop(pattern: &MetaTemplate, src: &tt::Subtree) -> Match {
+    let mut src = TtIter::new(src);
+    let mut stack: SmallVec<[TtIter<'_>; 1]> = SmallVec::new();
+    let mut res = Match::default();
+    let mut error_recover_item = None;
+
+    let mut bindings_builder = BindingsBuilder::default();
+
+    let mut cur_items = smallvec![MatchState {
+        dot: pattern.iter_delimited(None),
+        stack: Default::default(),
+        up: None,
+        sep: None,
+        sep_kind: None,
+        sep_parsed: None,
+        bindings: bindings_builder.alloc(),
+        is_error: false,
+        meta_result: None,
+    }];
+
+    let mut next_items = vec![];
+
+    loop {
+        let mut bb_items = SmallVec::new();
+        let mut eof_items = SmallVec::new();
+        let mut error_items = SmallVec::new();
+
+        stdx::always!(next_items.is_empty());
+
+        match_loop_inner(
+            src.clone(),
+            &stack,
+            &mut res,
+            &mut bindings_builder,
+            &mut cur_items,
+            &mut bb_items,
+            &mut next_items,
+            &mut eof_items,
+            &mut error_items,
+        );
+        stdx::always!(cur_items.is_empty());
+
+        if !error_items.is_empty() {
+            error_recover_item = error_items.pop().map(|it| it.bindings);
+        } else if let [state, ..] = &*eof_items {
+            error_recover_item = Some(state.bindings.clone());
+        }
+
+        // We need to do some post processing after the `match_loop_inner`.
+        // If we reached the EOF, check that there is EXACTLY ONE possible matcher. Otherwise,
+        // either the parse is ambiguous (which should never happen) or there is a syntax error.
+        if src.peek_n(0).is_none() && stack.is_empty() {
+            if let [state] = &*eof_items {
+                // remove all errors, because it is the correct answer !
+                res = Match::default();
+                res.bindings = bindings_builder.build(&state.bindings);
+            } else {
+                // Error recovery
+                if let Some(item) = error_recover_item {
+                    res.bindings = bindings_builder.build(&item);
+                }
+                res.add_err(ExpandError::UnexpectedToken);
+            }
+            return res;
+        }
+
+        // If there are no possible next positions AND we aren't waiting for the black-box parser,
+        // then there is a syntax error.
+        //
+        // Another possibility is that we need to call out to parse some rust nonterminal
+        // (black-box) parser. However, if there is not EXACTLY ONE of these, something is wrong.
+        let has_leftover_tokens = (bb_items.is_empty() && next_items.is_empty())
+            || !(bb_items.is_empty() || next_items.is_empty())
+            || bb_items.len() > 1;
+        if has_leftover_tokens {
+            res.unmatched_tts += src.len();
+            while let Some(it) = stack.pop() {
+                src = it;
+                res.unmatched_tts += src.len();
+            }
+            res.add_err(ExpandError::LeftoverTokens);
+
+            if let Some(error_reover_item) = error_recover_item {
+                res.bindings = bindings_builder.build(&error_reover_item);
+            }
+            return res;
+        }
+        // Dump all possible `next_items` into `cur_items` for the next iteration.
+        else if !next_items.is_empty() {
+            // Now process the next token
+            cur_items.extend(next_items.drain(..));
+
+            match src.next() {
+                Some(tt::TokenTree::Subtree(subtree)) => {
+                    stack.push(src.clone());
+                    src = TtIter::new(subtree);
+                }
+                None => {
+                    if let Some(iter) = stack.pop() {
+                        src = iter;
+                    }
+                }
+                _ => (),
+            }
+        }
+        // Finally, we have the case where we need to call the black-box parser to get some
+        // nonterminal.
+        else {
+            stdx::always!(bb_items.len() == 1);
+            let mut item = bb_items.pop().unwrap();
+
+            if let Some(OpDelimited::Op(Op::Var { name, .. })) = item.dot.peek() {
+                let (iter, match_res) = item.meta_result.take().unwrap();
+                match match_res.value {
+                    Some(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 let Some(err) = match_res.err {
+                    res.add_err(err);
+                }
+                src = iter.clone();
+                item.dot.next();
+            } else {
+                unreachable!()
+            }
+            cur_items.push(item);
+        }
+        stdx::always!(!cur_items.is_empty());
+    }
+}
+
+fn match_leaf(lhs: &tt::Leaf, src: &mut TtIter<'_>) -> Result<(), ExpandError> {
+    let rhs = src
+        .expect_leaf()
+        .map_err(|()| ExpandError::binding_error(format!("expected leaf: `{lhs}`")))?;
+    match (lhs, rhs) {
+        (
+            tt::Leaf::Punct(tt::Punct { char: lhs, .. }),
+            tt::Leaf::Punct(tt::Punct { char: rhs, .. }),
+        ) if lhs == rhs => Ok(()),
+        (
+            tt::Leaf::Ident(tt::Ident { text: lhs, .. }),
+            tt::Leaf::Ident(tt::Ident { text: rhs, .. }),
+        ) if lhs == rhs => Ok(()),
+        (
+            tt::Leaf::Literal(tt::Literal { text: lhs, .. }),
+            tt::Leaf::Literal(tt::Literal { text: rhs, .. }),
+        ) if lhs == rhs => Ok(()),
+        _ => Err(ExpandError::UnexpectedToken),
+    }
+}
+
+fn match_meta_var(kind: &str, input: &mut TtIter<'_>) -> ExpandResult<Option<Fragment>> {
+    let fragment = match kind {
+        "path" => parser::PrefixEntryPoint::Path,
+        "ty" => parser::PrefixEntryPoint::Ty,
+        // FIXME: These two should actually behave differently depending on the edition.
+        //
+        // https://doc.rust-lang.org/edition-guide/rust-2021/or-patterns-macro-rules.html
+        "pat" | "pat_param" => parser::PrefixEntryPoint::Pat,
+        "stmt" => parser::PrefixEntryPoint::Stmt,
+        "block" => parser::PrefixEntryPoint::Block,
+        "meta" => parser::PrefixEntryPoint::MetaItem,
+        "item" => parser::PrefixEntryPoint::Item,
+        "vis" => parser::PrefixEntryPoint::Vis,
+        "expr" => {
+            // `expr` should not match underscores.
+            // HACK: Macro expansion should not be done using "rollback and try another alternative".
+            // rustc [explicitly checks the next token][0].
+            // [0]: https://github.com/rust-lang/rust/blob/f0c4da499/compiler/rustc_expand/src/mbe/macro_parser.rs#L576
+            match input.peek_n(0) {
+                Some(tt::TokenTree::Leaf(tt::Leaf::Ident(it))) if it.text == "_" => {
+                    return ExpandResult::only_err(ExpandError::NoMatchingRule)
+                }
+                _ => {}
+            };
+            return input
+                .expect_fragment(parser::PrefixEntryPoint::Expr)
+                .map(|tt| tt.map(Fragment::Expr));
+        }
+        _ => {
+            let tt_result = match kind {
+                "ident" => input
+                    .expect_ident()
+                    .map(|ident| tt::Leaf::from(ident.clone()).into())
+                    .map_err(|()| ExpandError::binding_error("expected ident")),
+                "tt" => input
+                    .expect_tt()
+                    .map_err(|()| ExpandError::binding_error("expected token tree")),
+                "lifetime" => input
+                    .expect_lifetime()
+                    .map_err(|()| ExpandError::binding_error("expected lifetime")),
+                "literal" => {
+                    let neg = input.eat_char('-');
+                    input
+                        .expect_literal()
+                        .map(|literal| {
+                            let lit = literal.clone();
+                            match neg {
+                                None => lit.into(),
+                                Some(neg) => tt::TokenTree::Subtree(tt::Subtree {
+                                    delimiter: None,
+                                    token_trees: vec![neg, lit.into()],
+                                }),
+                            }
+                        })
+                        .map_err(|()| ExpandError::binding_error("expected literal"))
+                }
+                _ => Err(ExpandError::UnexpectedToken),
+            };
+            return tt_result.map(|it| Some(Fragment::Tokens(it))).into();
+        }
+    };
+    input.expect_fragment(fragment).map(|it| it.map(Fragment::Tokens))
+}
+
+fn collect_vars(collector_fun: &mut impl FnMut(SmolStr), pattern: &MetaTemplate) {
+    for op in pattern.iter() {
+        match op {
+            Op::Var { name, .. } => collector_fun(name.clone()),
+            Op::Leaf(_) => (),
+            Op::Subtree { tokens, .. } => collect_vars(collector_fun, tokens),
+            Op::Repeat { tokens, .. } => collect_vars(collector_fun, tokens),
+            Op::Ignore { .. } | Op::Index { .. } => {}
+        }
+    }
+}
+impl MetaTemplate {
+    fn iter_delimited<'a>(&'a self, delimited: Option<&'a tt::Delimiter>) -> OpDelimitedIter<'a> {
+        OpDelimitedIter { inner: &self.0, idx: 0, delimited }
+    }
+}
+
+#[derive(Debug, Clone, Copy)]
+enum OpDelimited<'a> {
+    Op(&'a Op),
+    Open,
+    Close,
+}
+
+#[derive(Debug, Clone, Copy)]
+struct OpDelimitedIter<'a> {
+    inner: &'a [Op],
+    delimited: Option<&'a tt::Delimiter>,
+    idx: usize,
+}
+
+impl<'a> OpDelimitedIter<'a> {
+    fn is_eof(&self) -> bool {
+        let len = self.inner.len() + if self.delimited.is_some() { 2 } else { 0 };
+        self.idx >= len
+    }
+
+    fn peek(&self) -> Option<OpDelimited<'a>> {
+        match self.delimited {
+            None => self.inner.get(self.idx).map(OpDelimited::Op),
+            Some(_) => match self.idx {
+                0 => Some(OpDelimited::Open),
+                i if i == self.inner.len() + 1 => Some(OpDelimited::Close),
+                i => self.inner.get(i - 1).map(OpDelimited::Op),
+            },
+        }
+    }
+
+    fn reset(&self) -> Self {
+        Self { inner: self.inner, idx: 0, delimited: self.delimited }
+    }
+}
+
+impl<'a> Iterator for OpDelimitedIter<'a> {
+    type Item = OpDelimited<'a>;
+
+    fn next(&mut self) -> Option<Self::Item> {
+        let res = self.peek();
+        self.idx += 1;
+        res
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        let len = self.inner.len() + if self.delimited.is_some() { 2 } else { 0 };
+        let remain = len.saturating_sub(self.idx);
+        (remain, Some(remain))
+    }
+}
+
+impl<'a> TtIter<'a> {
+    fn expect_separator(&mut self, separator: &Separator, idx: usize) -> bool {
+        let mut fork = self.clone();
+        let ok = match separator {
+            Separator::Ident(lhs) if idx == 0 => match fork.expect_ident_or_underscore() {
+                Ok(rhs) => rhs.text == lhs.text,
+                Err(_) => false,
+            },
+            Separator::Literal(lhs) if idx == 0 => match fork.expect_literal() {
+                Ok(rhs) => match rhs {
+                    tt::Leaf::Literal(rhs) => rhs.text == lhs.text,
+                    tt::Leaf::Ident(rhs) => rhs.text == lhs.text,
+                    tt::Leaf::Punct(_) => false,
+                },
+                Err(_) => false,
+            },
+            Separator::Puncts(lhss) if idx < lhss.len() => match fork.expect_punct() {
+                Ok(rhs) => rhs.char == lhss[idx].char,
+                Err(_) => false,
+            },
+            _ => false,
+        };
+        if ok {
+            *self = fork;
+        }
+        ok
+    }
+
+    fn expect_tt(&mut self) -> Result<tt::TokenTree, ()> {
+        match self.peek_n(0) {
+            Some(tt::TokenTree::Leaf(tt::Leaf::Punct(punct))) if punct.char == '\'' => {
+                return self.expect_lifetime();
+            }
+            _ => (),
+        }
+
+        let tt = self.next().ok_or(())?.clone();
+        let punct = match tt {
+            tt::TokenTree::Leaf(tt::Leaf::Punct(punct)) if punct.spacing == tt::Spacing::Joint => {
+                punct
+            }
+            _ => return Ok(tt),
+        };
+
+        let (second, third) = match (self.peek_n(0), self.peek_n(1)) {
+            (
+                Some(tt::TokenTree::Leaf(tt::Leaf::Punct(p2))),
+                Some(tt::TokenTree::Leaf(tt::Leaf::Punct(p3))),
+            ) if p2.spacing == tt::Spacing::Joint => (p2.char, Some(p3.char)),
+            (Some(tt::TokenTree::Leaf(tt::Leaf::Punct(p2))), _) => (p2.char, None),
+            _ => return Ok(tt),
+        };
+
+        match (punct.char, second, third) {
+            ('.', '.', Some('.' | '=')) | ('<', '<', Some('=')) | ('>', '>', Some('=')) => {
+                let tt2 = self.next().unwrap().clone();
+                let tt3 = self.next().unwrap().clone();
+                Ok(tt::Subtree { delimiter: None, token_trees: vec![tt, tt2, tt3] }.into())
+            }
+            ('-' | '!' | '*' | '/' | '&' | '%' | '^' | '+' | '<' | '=' | '>' | '|', '=', _)
+            | ('-' | '=' | '>', '>', _)
+            | (':', ':', _)
+            | ('.', '.', _)
+            | ('&', '&', _)
+            | ('<', '<', _)
+            | ('|', '|', _) => {
+                let tt2 = self.next().unwrap().clone();
+                Ok(tt::Subtree { delimiter: None, token_trees: vec![tt, tt2] }.into())
+            }
+            _ => Ok(tt),
+        }
+    }
+
+    fn expect_lifetime(&mut self) -> Result<tt::TokenTree, ()> {
+        let punct = self.expect_punct()?;
+        if punct.char != '\'' {
+            return Err(());
+        }
+        let ident = self.expect_ident_or_underscore()?;
+
+        Ok(tt::Subtree {
+            delimiter: None,
+            token_trees: vec![
+                tt::Leaf::Punct(*punct).into(),
+                tt::Leaf::Ident(ident.clone()).into(),
+            ],
+        }
+        .into())
+    }
+
+    fn eat_char(&mut self, c: char) -> Option<tt::TokenTree> {
+        let mut fork = self.clone();
+        match fork.expect_char(c) {
+            Ok(_) => {
+                let tt = self.next().cloned();
+                *self = fork;
+                tt
+            }
+            Err(_) => None,
+        }
+    }
+}
diff --git a/src/tools/rust-analyzer/crates/mbe/src/expander/transcriber.rs b/src/tools/rust-analyzer/crates/mbe/src/expander/transcriber.rs
new file mode 100644
index 000000000..7bcc84740
--- /dev/null
+++ b/src/tools/rust-analyzer/crates/mbe/src/expander/transcriber.rs
@@ -0,0 +1,272 @@
+//! Transcriber takes a template, like `fn $ident() {}`, a set of bindings like
+//! `$ident => foo`, interpolates variables in the template, to get `fn foo() {}`
+
+use syntax::SmolStr;
+use tt::{Delimiter, Subtree};
+
+use crate::{
+    expander::{Binding, Bindings, Fragment},
+    parser::{Op, RepeatKind, Separator},
+    ExpandError, ExpandResult, MetaTemplate,
+};
+
+impl Bindings {
+    fn contains(&self, name: &str) -> bool {
+        self.inner.contains_key(name)
+    }
+
+    fn get(&self, name: &str, nesting: &mut [NestingState]) -> Result<&Fragment, ExpandError> {
+        macro_rules! binding_err {
+            ($($arg:tt)*) => { ExpandError::binding_error(format!($($arg)*)) };
+        }
+
+        let mut b: &Binding =
+            self.inner.get(name).ok_or_else(|| binding_err!("could not find binding `{name}`"))?;
+        for nesting_state in nesting.iter_mut() {
+            nesting_state.hit = true;
+            b = match b {
+                Binding::Fragment(_) => break,
+                Binding::Nested(bs) => bs.get(nesting_state.idx).ok_or_else(|| {
+                    nesting_state.at_end = true;
+                    binding_err!("could not find nested binding `{name}`")
+                })?,
+                Binding::Empty => {
+                    nesting_state.at_end = true;
+                    return Err(binding_err!("could not find empty binding `{name}`"));
+                }
+            };
+        }
+        match b {
+            Binding::Fragment(it) => Ok(it),
+            Binding::Nested(_) => {
+                Err(binding_err!("expected simple binding, found nested binding `{name}`"))
+            }
+            Binding::Empty => {
+                Err(binding_err!("expected simple binding, found empty binding `{name}`"))
+            }
+        }
+    }
+}
+
+pub(super) fn transcribe(
+    template: &MetaTemplate,
+    bindings: &Bindings,
+) -> ExpandResult<tt::Subtree> {
+    let mut ctx = ExpandCtx { bindings, nesting: Vec::new() };
+    let mut arena: Vec<tt::TokenTree> = Vec::new();
+    expand_subtree(&mut ctx, template, None, &mut arena)
+}
+
+#[derive(Debug)]
+struct NestingState {
+    idx: usize,
+    /// `hit` is currently necessary to tell `expand_repeat` if it should stop
+    /// because there is no variable in use by the current repetition
+    hit: bool,
+    /// `at_end` is currently necessary to tell `expand_repeat` if it should stop
+    /// because there is no more value available for the current repetition
+    at_end: bool,
+}
+
+#[derive(Debug)]
+struct ExpandCtx<'a> {
+    bindings: &'a Bindings,
+    nesting: Vec<NestingState>,
+}
+
+fn expand_subtree(
+    ctx: &mut ExpandCtx<'_>,
+    template: &MetaTemplate,
+    delimiter: Option<Delimiter>,
+    arena: &mut Vec<tt::TokenTree>,
+) -> ExpandResult<tt::Subtree> {
+    // remember how many elements are in the arena now - when returning, we want to drain exactly how many elements we added. This way, the recursive uses of the arena get their own "view" of the arena, but will reuse the allocation
+    let start_elements = arena.len();
+    let mut err = None;
+    for op in template.iter() {
+        match op {
+            Op::Leaf(tt) => arena.push(tt.clone().into()),
+            Op::Subtree { tokens, delimiter } => {
+                let ExpandResult { value: tt, err: e } =
+                    expand_subtree(ctx, tokens, *delimiter, arena);
+                err = err.or(e);
+                arena.push(tt.into());
+            }
+            Op::Var { name, id, .. } => {
+                let ExpandResult { value: fragment, err: e } = expand_var(ctx, name, *id);
+                err = err.or(e);
+                push_fragment(arena, fragment);
+            }
+            Op::Repeat { tokens: subtree, kind, separator } => {
+                let ExpandResult { value: fragment, err: e } =
+                    expand_repeat(ctx, subtree, *kind, separator, arena);
+                err = err.or(e);
+                push_fragment(arena, fragment)
+            }
+            Op::Ignore { name, id } => {
+                // Expand the variable, but ignore the result. This registers the repetition count.
+                expand_var(ctx, name, *id);
+            }
+            Op::Index { depth } => {
+                let index = ctx
+                    .nesting
+                    .get(ctx.nesting.len() - 1 - (*depth as usize))
+                    .map_or(0, |nest| nest.idx);
+                arena.push(
+                    tt::Leaf::Literal(tt::Literal {
+                        text: index.to_string().into(),
+                        id: tt::TokenId::unspecified(),
+                    })
+                    .into(),
+                );
+            }
+        }
+    }
+    // drain the elements added in this instance of expand_subtree
+    let tts = arena.drain(start_elements..).collect();
+    ExpandResult { value: tt::Subtree { delimiter, token_trees: tts }, err }
+}
+
+fn expand_var(ctx: &mut ExpandCtx<'_>, v: &SmolStr, id: tt::TokenId) -> ExpandResult<Fragment> {
+    // We already handle $crate case in mbe parser
+    debug_assert!(v != "crate");
+
+    if !ctx.bindings.contains(v) {
+        // Note that it is possible to have a `$var` inside a macro which is not bound.
+        // For example:
+        // ```
+        // macro_rules! foo {
+        //     ($a:ident, $b:ident, $c:tt) => {
+        //         macro_rules! bar {
+        //             ($bi:ident) => {
+        //                 fn $bi() -> u8 {$c}
+        //             }
+        //         }
+        //     }
+        // ```
+        // We just treat it a normal tokens
+        let tt = tt::Subtree {
+            delimiter: None,
+            token_trees: vec![
+                tt::Leaf::from(tt::Punct { char: '$', spacing: tt::Spacing::Alone, id }).into(),
+                tt::Leaf::from(tt::Ident { text: v.clone(), id }).into(),
+            ],
+        }
+        .into();
+        ExpandResult::ok(Fragment::Tokens(tt))
+    } else {
+        ctx.bindings.get(v, &mut ctx.nesting).map_or_else(
+            |e| ExpandResult { value: Fragment::Tokens(tt::TokenTree::empty()), err: Some(e) },
+            |b| ExpandResult::ok(b.clone()),
+        )
+    }
+}
+
+fn expand_repeat(
+    ctx: &mut ExpandCtx<'_>,
+    template: &MetaTemplate,
+    kind: RepeatKind,
+    separator: &Option<Separator>,
+    arena: &mut Vec<tt::TokenTree>,
+) -> ExpandResult<Fragment> {
+    let mut buf: Vec<tt::TokenTree> = Vec::new();
+    ctx.nesting.push(NestingState { idx: 0, at_end: false, hit: false });
+    // Dirty hack to make macro-expansion terminate.
+    // This should be replaced by a proper macro-by-example implementation
+    let limit = 65536;
+    let mut has_seps = 0;
+    let mut counter = 0;
+
+    loop {
+        let ExpandResult { value: mut t, err: e } = expand_subtree(ctx, template, None, arena);
+        let nesting_state = ctx.nesting.last_mut().unwrap();
+        if nesting_state.at_end || !nesting_state.hit {
+            break;
+        }
+        nesting_state.idx += 1;
+        nesting_state.hit = false;
+
+        counter += 1;
+        if counter == limit {
+            tracing::warn!(
+                "expand_tt in repeat pattern exceed limit => {:#?}\n{:#?}",
+                template,
+                ctx
+            );
+            return ExpandResult {
+                value: Fragment::Tokens(Subtree::default().into()),
+                err: Some(ExpandError::LimitExceeded),
+            };
+        }
+
+        if e.is_some() {
+            continue;
+        }
+
+        t.delimiter = None;
+        push_subtree(&mut buf, t);
+
+        if let Some(sep) = separator {
+            has_seps = match sep {
+                Separator::Ident(ident) => {
+                    buf.push(tt::Leaf::from(ident.clone()).into());
+                    1
+                }
+                Separator::Literal(lit) => {
+                    buf.push(tt::Leaf::from(lit.clone()).into());
+                    1
+                }
+                Separator::Puncts(puncts) => {
+                    for &punct in puncts {
+                        buf.push(tt::Leaf::from(punct).into());
+                    }
+                    puncts.len()
+                }
+            };
+        }
+
+        if RepeatKind::ZeroOrOne == kind {
+            break;
+        }
+    }
+
+    ctx.nesting.pop().unwrap();
+    for _ in 0..has_seps {
+        buf.pop();
+    }
+
+    // Check if it is a single token subtree without any delimiter
+    // e.g {Delimiter:None> ['>'] /Delimiter:None>}
+    let tt = tt::Subtree { delimiter: None, token_trees: buf }.into();
+
+    if RepeatKind::OneOrMore == kind && counter == 0 {
+        return ExpandResult {
+            value: Fragment::Tokens(tt),
+            err: Some(ExpandError::UnexpectedToken),
+        };
+    }
+    ExpandResult::ok(Fragment::Tokens(tt))
+}
+
+fn push_fragment(buf: &mut Vec<tt::TokenTree>, fragment: Fragment) {
+    match fragment {
+        Fragment::Tokens(tt::TokenTree::Subtree(tt)) => push_subtree(buf, tt),
+        Fragment::Expr(tt::TokenTree::Subtree(mut tt)) => {
+            if tt.delimiter.is_none() {
+                tt.delimiter = Some(tt::Delimiter {
+                    id: tt::TokenId::unspecified(),
+                    kind: tt::DelimiterKind::Parenthesis,
+                })
+            }
+            buf.push(tt.into())
+        }
+        Fragment::Tokens(tt) | Fragment::Expr(tt) => buf.push(tt),
+    }
+}
+
+fn push_subtree(buf: &mut Vec<tt::TokenTree>, tt: tt::Subtree) {
+    match tt.delimiter {
+        None => buf.extend(tt.token_trees),
+        Some(_) => buf.push(tt.into()),
+    }
+}
diff --git a/src/tools/rust-analyzer/crates/mbe/src/lib.rs b/src/tools/rust-analyzer/crates/mbe/src/lib.rs
new file mode 100644
index 000000000..79da84f4a
--- /dev/null
+++ b/src/tools/rust-analyzer/crates/mbe/src/lib.rs
@@ -0,0 +1,352 @@
+//! `mbe` (short for Macro By Example) crate contains code for handling
+//! `macro_rules` macros. It uses `TokenTree` (from `tt` package) as the
+//! interface, although it contains some code to bridge `SyntaxNode`s and
+//! `TokenTree`s as well!
+//!
+//! The tes for this functionality live in another crate:
+//! `hir_def::macro_expansion_tests::mbe`.
+
+#![warn(rust_2018_idioms, unused_lifetimes, semicolon_in_expressions_from_macros)]
+
+mod parser;
+mod expander;
+mod syntax_bridge;
+mod tt_iter;
+mod to_parser_input;
+
+#[cfg(test)]
+mod benchmark;
+mod token_map;
+
+use std::fmt;
+
+use crate::{
+    parser::{MetaTemplate, Op},
+    tt_iter::TtIter,
+};
+
+// FIXME: we probably should re-think  `token_tree_to_syntax_node` interfaces
+pub use ::parser::TopEntryPoint;
+pub use tt::{Delimiter, DelimiterKind, Punct};
+
+pub use crate::{
+    syntax_bridge::{
+        parse_exprs_with_sep, parse_to_token_tree, syntax_node_to_token_tree,
+        syntax_node_to_token_tree_with_modifications, token_tree_to_syntax_node, SyntheticToken,
+        SyntheticTokenId,
+    },
+    token_map::TokenMap,
+};
+
+#[derive(Debug, PartialEq, Eq, Clone)]
+pub enum ParseError {
+    UnexpectedToken(Box<str>),
+    Expected(Box<str>),
+    InvalidRepeat,
+    RepetitionEmptyTokenTree,
+}
+
+impl ParseError {
+    fn expected(e: &str) -> ParseError {
+        ParseError::Expected(e.into())
+    }
+
+    fn unexpected(e: &str) -> ParseError {
+        ParseError::UnexpectedToken(e.into())
+    }
+}
+
+impl fmt::Display for ParseError {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        match self {
+            ParseError::UnexpectedToken(it) => f.write_str(it),
+            ParseError::Expected(it) => f.write_str(it),
+            ParseError::InvalidRepeat => f.write_str("invalid repeat"),
+            ParseError::RepetitionEmptyTokenTree => f.write_str("empty token tree in repetition"),
+        }
+    }
+}
+
+#[derive(Debug, PartialEq, Eq, Clone)]
+pub enum ExpandError {
+    BindingError(Box<Box<str>>),
+    LeftoverTokens,
+    ConversionError,
+    LimitExceeded,
+    NoMatchingRule,
+    UnexpectedToken,
+}
+
+impl ExpandError {
+    fn binding_error(e: impl Into<Box<str>>) -> ExpandError {
+        ExpandError::BindingError(Box::new(e.into()))
+    }
+}
+
+impl fmt::Display for ExpandError {
+    fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result {
+        match self {
+            ExpandError::NoMatchingRule => f.write_str("no rule matches input tokens"),
+            ExpandError::UnexpectedToken => f.write_str("unexpected token in input"),
+            ExpandError::BindingError(e) => f.write_str(e),
+            ExpandError::ConversionError => f.write_str("could not convert tokens"),
+            ExpandError::LimitExceeded => f.write_str("Expand exceed limit"),
+            ExpandError::LeftoverTokens => f.write_str("leftover tokens"),
+        }
+    }
+}
+
+/// This struct contains AST for a single `macro_rules` definition. What might
+/// be very confusing is that AST has almost exactly the same shape as
+/// `tt::TokenTree`, but there's a crucial difference: in macro rules, `$ident`
+/// and `$()*` have special meaning (see `Var` and `Repeat` data structures)
+#[derive(Clone, Debug, PartialEq, Eq)]
+pub struct DeclarativeMacro {
+    rules: Vec<Rule>,
+    /// Highest id of the token we have in TokenMap
+    shift: Shift,
+}
+
+#[derive(Clone, Debug, PartialEq, Eq)]
+struct Rule {
+    lhs: MetaTemplate,
+    rhs: MetaTemplate,
+}
+
+#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
+pub struct Shift(u32);
+
+impl Shift {
+    pub fn new(tt: &tt::Subtree) -> Shift {
+        // Note that TokenId is started from zero,
+        // We have to add 1 to prevent duplication.
+        let value = max_id(tt).map_or(0, |it| it + 1);
+        return Shift(value);
+
+        // Find the max token id inside a subtree
+        fn max_id(subtree: &tt::Subtree) -> Option<u32> {
+            let filter = |tt: &_| match tt {
+                tt::TokenTree::Subtree(subtree) => {
+                    let tree_id = max_id(subtree);
+                    match subtree.delimiter {
+                        Some(it) if it.id != tt::TokenId::unspecified() => {
+                            Some(tree_id.map_or(it.id.0, |t| t.max(it.id.0)))
+                        }
+                        _ => tree_id,
+                    }
+                }
+                tt::TokenTree::Leaf(leaf) => {
+                    let &(tt::Leaf::Ident(tt::Ident { id, .. })
+                    | tt::Leaf::Punct(tt::Punct { id, .. })
+                    | tt::Leaf::Literal(tt::Literal { id, .. })) = leaf;
+
+                    (id != tt::TokenId::unspecified()).then(|| id.0)
+                }
+            };
+            subtree.token_trees.iter().filter_map(filter).max()
+        }
+    }
+
+    /// Shift given TokenTree token id
+    pub fn shift_all(self, tt: &mut tt::Subtree) {
+        for t in &mut tt.token_trees {
+            match t {
+                tt::TokenTree::Leaf(
+                    tt::Leaf::Ident(tt::Ident { id, .. })
+                    | tt::Leaf::Punct(tt::Punct { id, .. })
+                    | tt::Leaf::Literal(tt::Literal { id, .. }),
+                ) => *id = self.shift(*id),
+                tt::TokenTree::Subtree(tt) => {
+                    if let Some(it) = tt.delimiter.as_mut() {
+                        it.id = self.shift(it.id);
+                    }
+                    self.shift_all(tt)
+                }
+            }
+        }
+    }
+
+    pub fn shift(self, id: tt::TokenId) -> tt::TokenId {
+        if id == tt::TokenId::unspecified() {
+            id
+        } else {
+            tt::TokenId(id.0 + self.0)
+        }
+    }
+
+    pub fn unshift(self, id: tt::TokenId) -> Option<tt::TokenId> {
+        id.0.checked_sub(self.0).map(tt::TokenId)
+    }
+}
+
+#[derive(Debug, Eq, PartialEq)]
+pub enum Origin {
+    Def,
+    Call,
+}
+
+impl DeclarativeMacro {
+    /// The old, `macro_rules! m {}` flavor.
+    pub fn parse_macro_rules(tt: &tt::Subtree) -> Result<DeclarativeMacro, ParseError> {
+        // Note: this parsing can be implemented using mbe machinery itself, by
+        // matching against `$($lhs:tt => $rhs:tt);*` pattern, but implementing
+        // manually seems easier.
+        let mut src = TtIter::new(tt);
+        let mut rules = Vec::new();
+        while src.len() > 0 {
+            let rule = Rule::parse(&mut src, true)?;
+            rules.push(rule);
+            if let Err(()) = src.expect_char(';') {
+                if src.len() > 0 {
+                    return Err(ParseError::expected("expected `;`"));
+                }
+                break;
+            }
+        }
+
+        for Rule { lhs, .. } in &rules {
+            validate(lhs)?;
+        }
+
+        Ok(DeclarativeMacro { rules, shift: Shift::new(tt) })
+    }
+
+    /// The new, unstable `macro m {}` flavor.
+    pub fn parse_macro2(tt: &tt::Subtree) -> Result<DeclarativeMacro, ParseError> {
+        let mut src = TtIter::new(tt);
+        let mut rules = Vec::new();
+
+        if Some(tt::DelimiterKind::Brace) == tt.delimiter_kind() {
+            cov_mark::hit!(parse_macro_def_rules);
+            while src.len() > 0 {
+                let rule = Rule::parse(&mut src, true)?;
+                rules.push(rule);
+                if let Err(()) = src.expect_any_char(&[';', ',']) {
+                    if src.len() > 0 {
+                        return Err(ParseError::expected("expected `;` or `,` to delimit rules"));
+                    }
+                    break;
+                }
+            }
+        } else {
+            cov_mark::hit!(parse_macro_def_simple);
+            let rule = Rule::parse(&mut src, false)?;
+            if src.len() != 0 {
+                return Err(ParseError::expected("remaining tokens in macro def"));
+            }
+            rules.push(rule);
+        }
+
+        for Rule { lhs, .. } in &rules {
+            validate(lhs)?;
+        }
+
+        Ok(DeclarativeMacro { rules, shift: Shift::new(tt) })
+    }
+
+    pub fn expand(&self, tt: &tt::Subtree) -> ExpandResult<tt::Subtree> {
+        // apply shift
+        let mut tt = tt.clone();
+        self.shift.shift_all(&mut tt);
+        expander::expand_rules(&self.rules, &tt)
+    }
+
+    pub fn map_id_down(&self, id: tt::TokenId) -> tt::TokenId {
+        self.shift.shift(id)
+    }
+
+    pub fn map_id_up(&self, id: tt::TokenId) -> (tt::TokenId, Origin) {
+        match self.shift.unshift(id) {
+            Some(id) => (id, Origin::Call),
+            None => (id, Origin::Def),
+        }
+    }
+
+    pub fn shift(&self) -> Shift {
+        self.shift
+    }
+}
+
+impl Rule {
+    fn parse(src: &mut TtIter<'_>, expect_arrow: bool) -> Result<Self, ParseError> {
+        let lhs = src.expect_subtree().map_err(|()| ParseError::expected("expected subtree"))?;
+        if expect_arrow {
+            src.expect_char('=').map_err(|()| ParseError::expected("expected `=`"))?;
+            src.expect_char('>').map_err(|()| ParseError::expected("expected `>`"))?;
+        }
+        let rhs = src.expect_subtree().map_err(|()| ParseError::expected("expected subtree"))?;
+
+        let lhs = MetaTemplate::parse_pattern(lhs)?;
+        let rhs = MetaTemplate::parse_template(rhs)?;
+
+        Ok(crate::Rule { lhs, rhs })
+    }
+}
+
+fn validate(pattern: &MetaTemplate) -> Result<(), ParseError> {
+    for op in pattern.iter() {
+        match op {
+            Op::Subtree { tokens, .. } => validate(tokens)?,
+            Op::Repeat { tokens: subtree, separator, .. } => {
+                // Checks that no repetition which could match an empty token
+                // https://github.com/rust-lang/rust/blob/a58b1ed44f5e06976de2bdc4d7dc81c36a96934f/src/librustc_expand/mbe/macro_rules.rs#L558
+                let lsh_is_empty_seq = separator.is_none() && subtree.iter().all(|child_op| {
+                    match child_op {
+                        // vis is optional
+                        Op::Var { kind: Some(kind), .. } => kind == "vis",
+                        Op::Repeat {
+                            kind: parser::RepeatKind::ZeroOrMore | parser::RepeatKind::ZeroOrOne,
+                            ..
+                        } => true,
+                        _ => false,
+                    }
+                });
+                if lsh_is_empty_seq {
+                    return Err(ParseError::RepetitionEmptyTokenTree);
+                }
+                validate(subtree)?
+            }
+            _ => (),
+        }
+    }
+    Ok(())
+}
+
+pub type ExpandResult<T> = ValueResult<T, ExpandError>;
+
+#[derive(Debug, Clone, Eq, PartialEq)]
+pub struct ValueResult<T, E> {
+    pub value: T,
+    pub err: Option<E>,
+}
+
+impl<T, E> ValueResult<T, E> {
+    pub fn ok(value: T) -> Self {
+        Self { value, err: None }
+    }
+
+    pub fn only_err(err: E) -> Self
+    where
+        T: Default,
+    {
+        Self { value: Default::default(), err: Some(err) }
+    }
+
+    pub fn map<U>(self, f: impl FnOnce(T) -> U) -> ValueResult<U, E> {
+        ValueResult { value: f(self.value), err: self.err }
+    }
+
+    pub fn map_err<E2>(self, f: impl FnOnce(E) -> E2) -> ValueResult<T, E2> {
+        ValueResult { value: self.value, err: self.err.map(f) }
+    }
+
+    pub fn result(self) -> Result<T, E> {
+        self.err.map_or(Ok(self.value), Err)
+    }
+}
+
+impl<T: Default, E> From<Result<T, E>> for ValueResult<T, E> {
+    fn from(result: Result<T, E>) -> Self {
+        result.map_or_else(Self::only_err, Self::ok)
+    }
+}
diff --git a/src/tools/rust-analyzer/crates/mbe/src/parser.rs b/src/tools/rust-analyzer/crates/mbe/src/parser.rs
new file mode 100644
index 000000000..acb4be584
--- /dev/null
+++ b/src/tools/rust-analyzer/crates/mbe/src/parser.rs
@@ -0,0 +1,261 @@
+//! Parser recognizes special macro syntax, `$var` and `$(repeat)*`, in token
+//! trees.
+
+use smallvec::SmallVec;
+use syntax::SmolStr;
+
+use crate::{tt_iter::TtIter, ParseError};
+
+/// Consider
+///
+/// ```
+/// macro_rules! an_macro {
+///     ($x:expr + $y:expr) => ($y * $x)
+/// }
+/// ```
+///
+/// Stuff to the left of `=>` is a [`MetaTemplate`] pattern (which is matched
+/// with input).
+///
+/// Stuff to the right is a [`MetaTemplate`] template which is used to produce
+/// output.
+#[derive(Clone, Debug, PartialEq, Eq)]
+pub(crate) struct MetaTemplate(pub(crate) Vec<Op>);
+
+impl MetaTemplate {
+    pub(crate) fn parse_pattern(pattern: &tt::Subtree) -> Result<MetaTemplate, ParseError> {
+        MetaTemplate::parse(pattern, Mode::Pattern)
+    }
+
+    pub(crate) fn parse_template(template: &tt::Subtree) -> Result<MetaTemplate, ParseError> {
+        MetaTemplate::parse(template, Mode::Template)
+    }
+
+    pub(crate) fn iter(&self) -> impl Iterator<Item = &Op> {
+        self.0.iter()
+    }
+
+    fn parse(tt: &tt::Subtree, mode: Mode) -> Result<MetaTemplate, ParseError> {
+        let mut src = TtIter::new(tt);
+
+        let mut res = Vec::new();
+        while let Some(first) = src.next() {
+            let op = next_op(first, &mut src, mode)?;
+            res.push(op);
+        }
+
+        Ok(MetaTemplate(res))
+    }
+}
+
+#[derive(Clone, Debug, PartialEq, Eq)]
+pub(crate) enum Op {
+    Var { name: SmolStr, kind: Option<SmolStr>, id: tt::TokenId },
+    Ignore { name: SmolStr, id: tt::TokenId },
+    Index { depth: u32 },
+    Repeat { tokens: MetaTemplate, kind: RepeatKind, separator: Option<Separator> },
+    Leaf(tt::Leaf),
+    Subtree { tokens: MetaTemplate, delimiter: Option<tt::Delimiter> },
+}
+
+#[derive(Copy, Clone, Debug, PartialEq, Eq)]
+pub(crate) enum RepeatKind {
+    ZeroOrMore,
+    OneOrMore,
+    ZeroOrOne,
+}
+
+#[derive(Clone, Debug, Eq)]
+pub(crate) enum Separator {
+    Literal(tt::Literal),
+    Ident(tt::Ident),
+    Puncts(SmallVec<[tt::Punct; 3]>),
+}
+
+// Note that when we compare a Separator, we just care about its textual value.
+impl PartialEq for Separator {
+    fn eq(&self, other: &Separator) -> bool {
+        use Separator::*;
+
+        match (self, other) {
+            (Ident(a), Ident(b)) => a.text == b.text,
+            (Literal(a), Literal(b)) => a.text == b.text,
+            (Puncts(a), Puncts(b)) if a.len() == b.len() => {
+                let a_iter = a.iter().map(|a| a.char);
+                let b_iter = b.iter().map(|b| b.char);
+                a_iter.eq(b_iter)
+            }
+            _ => false,
+        }
+    }
+}
+
+impl Separator {
+    pub(crate) fn tt_count(&self) -> usize {
+        match self {
+            Separator::Literal(_) => 1,
+            Separator::Ident(_) => 1,
+            Separator::Puncts(it) => it.len(),
+        }
+    }
+}
+
+#[derive(Clone, Copy)]
+enum Mode {
+    Pattern,
+    Template,
+}
+
+fn next_op<'a>(first: &tt::TokenTree, src: &mut TtIter<'a>, mode: Mode) -> Result<Op, ParseError> {
+    let res = match first {
+        tt::TokenTree::Leaf(leaf @ tt::Leaf::Punct(tt::Punct { char: '$', .. })) => {
+            // Note that the '$' itself is a valid token inside macro_rules.
+            let second = match src.next() {
+                None => return Ok(Op::Leaf(leaf.clone())),
+                Some(it) => it,
+            };
+            match second {
+                tt::TokenTree::Subtree(subtree) => match subtree.delimiter_kind() {
+                    Some(tt::DelimiterKind::Parenthesis) => {
+                        let (separator, kind) = parse_repeat(src)?;
+                        let tokens = MetaTemplate::parse(subtree, mode)?;
+                        Op::Repeat { tokens, separator, kind }
+                    }
+                    Some(tt::DelimiterKind::Brace) => match mode {
+                        Mode::Template => {
+                            parse_metavar_expr(&mut TtIter::new(subtree)).map_err(|()| {
+                                ParseError::unexpected("invalid metavariable expression")
+                            })?
+                        }
+                        Mode::Pattern => {
+                            return Err(ParseError::unexpected(
+                                "`${}` metavariable expressions are not allowed in matchers",
+                            ))
+                        }
+                    },
+                    _ => {
+                        return Err(ParseError::expected(
+                            "expected `$()` repetition or `${}` expression",
+                        ))
+                    }
+                },
+                tt::TokenTree::Leaf(leaf) => match leaf {
+                    tt::Leaf::Ident(ident) if ident.text == "crate" => {
+                        // We simply produce identifier `$crate` here. And it will be resolved when lowering ast to Path.
+                        Op::Leaf(tt::Leaf::from(tt::Ident { text: "$crate".into(), id: ident.id }))
+                    }
+                    tt::Leaf::Ident(ident) => {
+                        let kind = eat_fragment_kind(src, mode)?;
+                        let name = ident.text.clone();
+                        let id = ident.id;
+                        Op::Var { name, kind, id }
+                    }
+                    tt::Leaf::Literal(lit) if is_boolean_literal(lit) => {
+                        let kind = eat_fragment_kind(src, mode)?;
+                        let name = lit.text.clone();
+                        let id = lit.id;
+                        Op::Var { name, kind, id }
+                    }
+                    tt::Leaf::Punct(punct @ tt::Punct { char: '$', .. }) => match mode {
+                        Mode::Pattern => {
+                            return Err(ParseError::unexpected(
+                                "`$$` is not allowed on the pattern side",
+                            ))
+                        }
+                        Mode::Template => Op::Leaf(tt::Leaf::Punct(*punct)),
+                    },
+                    tt::Leaf::Punct(_) | tt::Leaf::Literal(_) => {
+                        return Err(ParseError::expected("expected ident"))
+                    }
+                },
+            }
+        }
+        tt::TokenTree::Leaf(tt) => Op::Leaf(tt.clone()),
+        tt::TokenTree::Subtree(subtree) => {
+            let tokens = MetaTemplate::parse(subtree, mode)?;
+            Op::Subtree { tokens, delimiter: subtree.delimiter }
+        }
+    };
+    Ok(res)
+}
+
+fn eat_fragment_kind(src: &mut TtIter<'_>, mode: Mode) -> Result<Option<SmolStr>, ParseError> {
+    if let Mode::Pattern = mode {
+        src.expect_char(':').map_err(|()| ParseError::unexpected("missing fragment specifier"))?;
+        let ident = src
+            .expect_ident()
+            .map_err(|()| ParseError::unexpected("missing fragment specifier"))?;
+        return Ok(Some(ident.text.clone()));
+    };
+    Ok(None)
+}
+
+fn is_boolean_literal(lit: &tt::Literal) -> bool {
+    matches!(lit.text.as_str(), "true" | "false")
+}
+
+fn parse_repeat(src: &mut TtIter<'_>) -> Result<(Option<Separator>, RepeatKind), ParseError> {
+    let mut separator = Separator::Puncts(SmallVec::new());
+    for tt in src {
+        let tt = match tt {
+            tt::TokenTree::Leaf(leaf) => leaf,
+            tt::TokenTree::Subtree(_) => return Err(ParseError::InvalidRepeat),
+        };
+        let has_sep = match &separator {
+            Separator::Puncts(puncts) => !puncts.is_empty(),
+            _ => true,
+        };
+        match tt {
+            tt::Leaf::Ident(_) | tt::Leaf::Literal(_) if has_sep => {
+                return Err(ParseError::InvalidRepeat)
+            }
+            tt::Leaf::Ident(ident) => separator = Separator::Ident(ident.clone()),
+            tt::Leaf::Literal(lit) => separator = Separator::Literal(lit.clone()),
+            tt::Leaf::Punct(punct) => {
+                let repeat_kind = match punct.char {
+                    '*' => RepeatKind::ZeroOrMore,
+                    '+' => RepeatKind::OneOrMore,
+                    '?' => RepeatKind::ZeroOrOne,
+                    _ => match &mut separator {
+                        Separator::Puncts(puncts) if puncts.len() != 3 => {
+                            puncts.push(*punct);
+                            continue;
+                        }
+                        _ => return Err(ParseError::InvalidRepeat),
+                    },
+                };
+                return Ok((has_sep.then(|| separator), repeat_kind));
+            }
+        }
+    }
+    Err(ParseError::InvalidRepeat)
+}
+
+fn parse_metavar_expr(src: &mut TtIter<'_>) -> Result<Op, ()> {
+    let func = src.expect_ident()?;
+    let args = src.expect_subtree()?;
+
+    if args.delimiter_kind() != Some(tt::DelimiterKind::Parenthesis) {
+        return Err(());
+    }
+
+    let mut args = TtIter::new(args);
+
+    let op = match &*func.text {
+        "ignore" => {
+            let ident = args.expect_ident()?;
+            Op::Ignore { name: ident.text.clone(), id: ident.id }
+        }
+        "index" => {
+            let depth = if args.len() == 0 { 0 } else { args.expect_u32_literal()? };
+            Op::Index { depth }
+        }
+        _ => return Err(()),
+    };
+
+    if args.next().is_some() {
+        return Err(());
+    }
+
+    Ok(op)
+}
diff --git a/src/tools/rust-analyzer/crates/mbe/src/syntax_bridge.rs b/src/tools/rust-analyzer/crates/mbe/src/syntax_bridge.rs
new file mode 100644
index 000000000..aca6ecd42
--- /dev/null
+++ b/src/tools/rust-analyzer/crates/mbe/src/syntax_bridge.rs
@@ -0,0 +1,844 @@
+//! Conversions between [`SyntaxNode`] and [`tt::TokenTree`].
+
+use rustc_hash::FxHashMap;
+use stdx::{always, non_empty_vec::NonEmptyVec};
+use syntax::{
+    ast::{self, make::tokens::doc_comment},
+    AstToken, Parse, PreorderWithTokens, SmolStr, SyntaxElement, SyntaxKind,
+    SyntaxKind::*,
+    SyntaxNode, SyntaxToken, SyntaxTreeBuilder, TextRange, TextSize, WalkEvent, T,
+};
+use tt::buffer::{Cursor, TokenBuffer};
+
+use crate::{to_parser_input::to_parser_input, tt_iter::TtIter, TokenMap};
+
+/// Convert the syntax node to a `TokenTree` (what macro
+/// will consume).
+pub fn syntax_node_to_token_tree(node: &SyntaxNode) -> (tt::Subtree, TokenMap) {
+    let (subtree, token_map, _) = syntax_node_to_token_tree_with_modifications(
+        node,
+        Default::default(),
+        0,
+        Default::default(),
+        Default::default(),
+    );
+    (subtree, token_map)
+}
+
+/// Convert the syntax node to a `TokenTree` (what macro will consume)
+/// with the censored range excluded.
+pub fn syntax_node_to_token_tree_with_modifications(
+    node: &SyntaxNode,
+    existing_token_map: TokenMap,
+    next_id: u32,
+    replace: FxHashMap<SyntaxElement, Vec<SyntheticToken>>,
+    append: FxHashMap<SyntaxElement, Vec<SyntheticToken>>,
+) -> (tt::Subtree, TokenMap, u32) {
+    let global_offset = node.text_range().start();
+    let mut c = Convertor::new(node, global_offset, existing_token_map, next_id, replace, append);
+    let subtree = convert_tokens(&mut c);
+    c.id_alloc.map.shrink_to_fit();
+    always!(c.replace.is_empty(), "replace: {:?}", c.replace);
+    always!(c.append.is_empty(), "append: {:?}", c.append);
+    (subtree, c.id_alloc.map, c.id_alloc.next_id)
+}
+
+#[derive(Clone, Copy, Debug, PartialEq, Eq, Hash)]
+pub struct SyntheticTokenId(pub u32);
+
+#[derive(Debug, Clone)]
+pub struct SyntheticToken {
+    pub kind: SyntaxKind,
+    pub text: SmolStr,
+    pub range: TextRange,
+    pub id: SyntheticTokenId,
+}
+
+// The following items are what `rustc` macro can be parsed into :
+// link: https://github.com/rust-lang/rust/blob/9ebf47851a357faa4cd97f4b1dc7835f6376e639/src/libsyntax/ext/expand.rs#L141
+// * Expr(P<ast::Expr>)                     -> token_tree_to_expr
+// * Pat(P<ast::Pat>)                       -> token_tree_to_pat
+// * Ty(P<ast::Ty>)                         -> token_tree_to_ty
+// * Stmts(SmallVec<[ast::Stmt; 1]>)        -> token_tree_to_stmts
+// * Items(SmallVec<[P<ast::Item>; 1]>)     -> token_tree_to_items
+//
+// * TraitItems(SmallVec<[ast::TraitItem; 1]>)
+// * AssocItems(SmallVec<[ast::AssocItem; 1]>)
+// * ForeignItems(SmallVec<[ast::ForeignItem; 1]>
+
+pub fn token_tree_to_syntax_node(
+    tt: &tt::Subtree,
+    entry_point: parser::TopEntryPoint,
+) -> (Parse<SyntaxNode>, TokenMap) {
+    let buffer = match tt {
+        tt::Subtree { delimiter: None, token_trees } => {
+            TokenBuffer::from_tokens(token_trees.as_slice())
+        }
+        _ => TokenBuffer::from_subtree(tt),
+    };
+    let parser_input = to_parser_input(&buffer);
+    let parser_output = entry_point.parse(&parser_input);
+    let mut tree_sink = TtTreeSink::new(buffer.begin());
+    for event in parser_output.iter() {
+        match event {
+            parser::Step::Token { kind, n_input_tokens: n_raw_tokens } => {
+                tree_sink.token(kind, n_raw_tokens)
+            }
+            parser::Step::Enter { kind } => tree_sink.start_node(kind),
+            parser::Step::Exit => tree_sink.finish_node(),
+            parser::Step::Error { msg } => tree_sink.error(msg.to_string()),
+        }
+    }
+    let (parse, range_map) = tree_sink.finish();
+    (parse, range_map)
+}
+
+/// Convert a string to a `TokenTree`
+pub fn parse_to_token_tree(text: &str) -> Option<(tt::Subtree, TokenMap)> {
+    let lexed = parser::LexedStr::new(text);
+    if lexed.errors().next().is_some() {
+        return None;
+    }
+
+    let mut conv = RawConvertor {
+        lexed,
+        pos: 0,
+        id_alloc: TokenIdAlloc {
+            map: Default::default(),
+            global_offset: TextSize::default(),
+            next_id: 0,
+        },
+    };
+
+    let subtree = convert_tokens(&mut conv);
+    Some((subtree, conv.id_alloc.map))
+}
+
+/// Split token tree with separate expr: $($e:expr)SEP*
+pub fn parse_exprs_with_sep(tt: &tt::Subtree, sep: char) -> Vec<tt::Subtree> {
+    if tt.token_trees.is_empty() {
+        return Vec::new();
+    }
+
+    let mut iter = TtIter::new(tt);
+    let mut res = Vec::new();
+
+    while iter.peek_n(0).is_some() {
+        let expanded = iter.expect_fragment(parser::PrefixEntryPoint::Expr);
+
+        res.push(match expanded.value {
+            None => break,
+            Some(tt @ tt::TokenTree::Leaf(_)) => {
+                tt::Subtree { delimiter: None, token_trees: vec![tt] }
+            }
+            Some(tt::TokenTree::Subtree(tt)) => tt,
+        });
+
+        let mut fork = iter.clone();
+        if fork.expect_char(sep).is_err() {
+            break;
+        }
+        iter = fork;
+    }
+
+    if iter.peek_n(0).is_some() {
+        res.push(tt::Subtree { delimiter: None, token_trees: iter.into_iter().cloned().collect() });
+    }
+
+    res
+}
+
+fn convert_tokens<C: TokenConvertor>(conv: &mut C) -> tt::Subtree {
+    struct StackEntry {
+        subtree: tt::Subtree,
+        idx: usize,
+        open_range: TextRange,
+    }
+
+    let entry = StackEntry {
+        subtree: tt::Subtree { delimiter: None, ..Default::default() },
+        // never used (delimiter is `None`)
+        idx: !0,
+        open_range: TextRange::empty(TextSize::of('.')),
+    };
+    let mut stack = NonEmptyVec::new(entry);
+
+    loop {
+        let StackEntry { subtree, .. } = stack.last_mut();
+        let result = &mut subtree.token_trees;
+        let (token, range) = match conv.bump() {
+            Some(it) => it,
+            None => break,
+        };
+        let synth_id = token.synthetic_id(conv);
+
+        let kind = token.kind(conv);
+        if kind == COMMENT {
+            if let Some(tokens) = conv.convert_doc_comment(&token) {
+                // FIXME: There has to be a better way to do this
+                // Add the comments token id to the converted doc string
+                let id = conv.id_alloc().alloc(range, synth_id);
+                result.extend(tokens.into_iter().map(|mut tt| {
+                    if let tt::TokenTree::Subtree(sub) = &mut tt {
+                        if let Some(tt::TokenTree::Leaf(tt::Leaf::Literal(lit))) =
+                            sub.token_trees.get_mut(2)
+                        {
+                            lit.id = id
+                        }
+                    }
+                    tt
+                }));
+            }
+            continue;
+        }
+        let tt = if kind.is_punct() && kind != UNDERSCORE {
+            if synth_id.is_none() {
+                assert_eq!(range.len(), TextSize::of('.'));
+            }
+
+            if let Some(delim) = subtree.delimiter {
+                let expected = match delim.kind {
+                    tt::DelimiterKind::Parenthesis => T![')'],
+                    tt::DelimiterKind::Brace => T!['}'],
+                    tt::DelimiterKind::Bracket => T![']'],
+                };
+
+                if kind == expected {
+                    if let Some(entry) = stack.pop() {
+                        conv.id_alloc().close_delim(entry.idx, Some(range));
+                        stack.last_mut().subtree.token_trees.push(entry.subtree.into());
+                    }
+                    continue;
+                }
+            }
+
+            let delim = match kind {
+                T!['('] => Some(tt::DelimiterKind::Parenthesis),
+                T!['{'] => Some(tt::DelimiterKind::Brace),
+                T!['['] => Some(tt::DelimiterKind::Bracket),
+                _ => None,
+            };
+
+            if let Some(kind) = delim {
+                let mut subtree = tt::Subtree::default();
+                let (id, idx) = conv.id_alloc().open_delim(range, synth_id);
+                subtree.delimiter = Some(tt::Delimiter { id, kind });
+                stack.push(StackEntry { subtree, idx, open_range: range });
+                continue;
+            }
+
+            let spacing = match conv.peek().map(|next| next.kind(conv)) {
+                Some(kind)
+                    if !kind.is_trivia()
+                        && kind.is_punct()
+                        && kind != T!['[']
+                        && kind != T!['{']
+                        && kind != T!['(']
+                        && kind != UNDERSCORE =>
+                {
+                    tt::Spacing::Joint
+                }
+                _ => tt::Spacing::Alone,
+            };
+            let char = match token.to_char(conv) {
+                Some(c) => c,
+                None => {
+                    panic!("Token from lexer must be single char: token = {:#?}", token);
+                }
+            };
+            tt::Leaf::from(tt::Punct { char, spacing, id: conv.id_alloc().alloc(range, synth_id) })
+                .into()
+        } else {
+            macro_rules! make_leaf {
+                ($i:ident) => {
+                    tt::$i { id: conv.id_alloc().alloc(range, synth_id), text: token.to_text(conv) }
+                        .into()
+                };
+            }
+            let leaf: tt::Leaf = match kind {
+                T![true] | T![false] => make_leaf!(Ident),
+                IDENT => make_leaf!(Ident),
+                UNDERSCORE => make_leaf!(Ident),
+                k if k.is_keyword() => make_leaf!(Ident),
+                k if k.is_literal() => make_leaf!(Literal),
+                LIFETIME_IDENT => {
+                    let char_unit = TextSize::of('\'');
+                    let r = TextRange::at(range.start(), char_unit);
+                    let apostrophe = tt::Leaf::from(tt::Punct {
+                        char: '\'',
+                        spacing: tt::Spacing::Joint,
+                        id: conv.id_alloc().alloc(r, synth_id),
+                    });
+                    result.push(apostrophe.into());
+
+                    let r = TextRange::at(range.start() + char_unit, range.len() - char_unit);
+                    let ident = tt::Leaf::from(tt::Ident {
+                        text: SmolStr::new(&token.to_text(conv)[1..]),
+                        id: conv.id_alloc().alloc(r, synth_id),
+                    });
+                    result.push(ident.into());
+                    continue;
+                }
+                _ => continue,
+            };
+
+            leaf.into()
+        };
+        result.push(tt);
+    }
+
+    // If we get here, we've consumed all input tokens.
+    // We might have more than one subtree in the stack, if the delimiters are improperly balanced.
+    // Merge them so we're left with one.
+    while let Some(entry) = stack.pop() {
+        let parent = stack.last_mut();
+
+        conv.id_alloc().close_delim(entry.idx, None);
+        let leaf: tt::Leaf = tt::Punct {
+            id: conv.id_alloc().alloc(entry.open_range, None),
+            char: match entry.subtree.delimiter.unwrap().kind {
+                tt::DelimiterKind::Parenthesis => '(',
+                tt::DelimiterKind::Brace => '{',
+                tt::DelimiterKind::Bracket => '[',
+            },
+            spacing: tt::Spacing::Alone,
+        }
+        .into();
+        parent.subtree.token_trees.push(leaf.into());
+        parent.subtree.token_trees.extend(entry.subtree.token_trees);
+    }
+
+    let subtree = stack.into_last().subtree;
+    if let [tt::TokenTree::Subtree(first)] = &*subtree.token_trees {
+        first.clone()
+    } else {
+        subtree
+    }
+}
+
+/// Returns the textual content of a doc comment block as a quoted string
+/// That is, strips leading `///` (or `/**`, etc)
+/// and strips the ending `*/`
+/// And then quote the string, which is needed to convert to `tt::Literal`
+fn doc_comment_text(comment: &ast::Comment) -> SmolStr {
+    let prefix_len = comment.prefix().len();
+    let mut text = &comment.text()[prefix_len..];
+
+    // Remove ending "*/"
+    if comment.kind().shape == ast::CommentShape::Block {
+        text = &text[0..text.len() - 2];
+    }
+
+    // Quote the string
+    // Note that `tt::Literal` expect an escaped string
+    let text = format!("\"{}\"", text.escape_debug());
+    text.into()
+}
+
+fn convert_doc_comment(token: &syntax::SyntaxToken) -> Option<Vec<tt::TokenTree>> {
+    cov_mark::hit!(test_meta_doc_comments);
+    let comment = ast::Comment::cast(token.clone())?;
+    let doc = comment.kind().doc?;
+
+    // Make `doc="\" Comments\""
+    let meta_tkns = vec![mk_ident("doc"), mk_punct('='), mk_doc_literal(&comment)];
+
+    // Make `#![]`
+    let mut token_trees = Vec::with_capacity(3);
+    token_trees.push(mk_punct('#'));
+    if let ast::CommentPlacement::Inner = doc {
+        token_trees.push(mk_punct('!'));
+    }
+    token_trees.push(tt::TokenTree::from(tt::Subtree {
+        delimiter: Some(tt::Delimiter {
+            kind: tt::DelimiterKind::Bracket,
+            id: tt::TokenId::unspecified(),
+        }),
+        token_trees: meta_tkns,
+    }));
+
+    return Some(token_trees);
+
+    // Helper functions
+    fn mk_ident(s: &str) -> tt::TokenTree {
+        tt::TokenTree::from(tt::Leaf::from(tt::Ident {
+            text: s.into(),
+            id: tt::TokenId::unspecified(),
+        }))
+    }
+
+    fn mk_punct(c: char) -> tt::TokenTree {
+        tt::TokenTree::from(tt::Leaf::from(tt::Punct {
+            char: c,
+            spacing: tt::Spacing::Alone,
+            id: tt::TokenId::unspecified(),
+        }))
+    }
+
+    fn mk_doc_literal(comment: &ast::Comment) -> tt::TokenTree {
+        let lit = tt::Literal { text: doc_comment_text(comment), id: tt::TokenId::unspecified() };
+
+        tt::TokenTree::from(tt::Leaf::from(lit))
+    }
+}
+
+struct TokenIdAlloc {
+    map: TokenMap,
+    global_offset: TextSize,
+    next_id: u32,
+}
+
+impl TokenIdAlloc {
+    fn alloc(
+        &mut self,
+        absolute_range: TextRange,
+        synthetic_id: Option<SyntheticTokenId>,
+    ) -> tt::TokenId {
+        let relative_range = absolute_range - self.global_offset;
+        let token_id = tt::TokenId(self.next_id);
+        self.next_id += 1;
+        self.map.insert(token_id, relative_range);
+        if let Some(id) = synthetic_id {
+            self.map.insert_synthetic(token_id, id);
+        }
+        token_id
+    }
+
+    fn open_delim(
+        &mut self,
+        open_abs_range: TextRange,
+        synthetic_id: Option<SyntheticTokenId>,
+    ) -> (tt::TokenId, usize) {
+        let token_id = tt::TokenId(self.next_id);
+        self.next_id += 1;
+        let idx = self.map.insert_delim(
+            token_id,
+            open_abs_range - self.global_offset,
+            open_abs_range - self.global_offset,
+        );
+        if let Some(id) = synthetic_id {
+            self.map.insert_synthetic(token_id, id);
+        }
+        (token_id, idx)
+    }
+
+    fn close_delim(&mut self, idx: usize, close_abs_range: Option<TextRange>) {
+        match close_abs_range {
+            None => {
+                self.map.remove_delim(idx);
+            }
+            Some(close) => {
+                self.map.update_close_delim(idx, close - self.global_offset);
+            }
+        }
+    }
+}
+
+/// A raw token (straight from lexer) convertor
+struct RawConvertor<'a> {
+    lexed: parser::LexedStr<'a>,
+    pos: usize,
+    id_alloc: TokenIdAlloc,
+}
+
+trait SrcToken<Ctx>: std::fmt::Debug {
+    fn kind(&self, ctx: &Ctx) -> SyntaxKind;
+
+    fn to_char(&self, ctx: &Ctx) -> Option<char>;
+
+    fn to_text(&self, ctx: &Ctx) -> SmolStr;
+
+    fn synthetic_id(&self, ctx: &Ctx) -> Option<SyntheticTokenId>;
+}
+
+trait TokenConvertor: Sized {
+    type Token: SrcToken<Self>;
+
+    fn convert_doc_comment(&self, token: &Self::Token) -> Option<Vec<tt::TokenTree>>;
+
+    fn bump(&mut self) -> Option<(Self::Token, TextRange)>;
+
+    fn peek(&self) -> Option<Self::Token>;
+
+    fn id_alloc(&mut self) -> &mut TokenIdAlloc;
+}
+
+impl<'a> SrcToken<RawConvertor<'a>> for usize {
+    fn kind(&self, ctx: &RawConvertor<'a>) -> SyntaxKind {
+        ctx.lexed.kind(*self)
+    }
+
+    fn to_char(&self, ctx: &RawConvertor<'a>) -> Option<char> {
+        ctx.lexed.text(*self).chars().next()
+    }
+
+    fn to_text(&self, ctx: &RawConvertor<'_>) -> SmolStr {
+        ctx.lexed.text(*self).into()
+    }
+
+    fn synthetic_id(&self, _ctx: &RawConvertor<'a>) -> Option<SyntheticTokenId> {
+        None
+    }
+}
+
+impl<'a> TokenConvertor for RawConvertor<'a> {
+    type Token = usize;
+
+    fn convert_doc_comment(&self, &token: &usize) -> Option<Vec<tt::TokenTree>> {
+        let text = self.lexed.text(token);
+        convert_doc_comment(&doc_comment(text))
+    }
+
+    fn bump(&mut self) -> Option<(Self::Token, TextRange)> {
+        if self.pos == self.lexed.len() {
+            return None;
+        }
+        let token = self.pos;
+        self.pos += 1;
+        let range = self.lexed.text_range(token);
+        let range = TextRange::new(range.start.try_into().unwrap(), range.end.try_into().unwrap());
+
+        Some((token, range))
+    }
+
+    fn peek(&self) -> Option<Self::Token> {
+        if self.pos == self.lexed.len() {
+            return None;
+        }
+        Some(self.pos)
+    }
+
+    fn id_alloc(&mut self) -> &mut TokenIdAlloc {
+        &mut self.id_alloc
+    }
+}
+
+struct Convertor {
+    id_alloc: TokenIdAlloc,
+    current: Option<SyntaxToken>,
+    current_synthetic: Vec<SyntheticToken>,
+    preorder: PreorderWithTokens,
+    replace: FxHashMap<SyntaxElement, Vec<SyntheticToken>>,
+    append: FxHashMap<SyntaxElement, Vec<SyntheticToken>>,
+    range: TextRange,
+    punct_offset: Option<(SyntaxToken, TextSize)>,
+}
+
+impl Convertor {
+    fn new(
+        node: &SyntaxNode,
+        global_offset: TextSize,
+        existing_token_map: TokenMap,
+        next_id: u32,
+        mut replace: FxHashMap<SyntaxElement, Vec<SyntheticToken>>,
+        mut append: FxHashMap<SyntaxElement, Vec<SyntheticToken>>,
+    ) -> Convertor {
+        let range = node.text_range();
+        let mut preorder = node.preorder_with_tokens();
+        let (first, synthetic) = Self::next_token(&mut preorder, &mut replace, &mut append);
+        Convertor {
+            id_alloc: { TokenIdAlloc { map: existing_token_map, global_offset, next_id } },
+            current: first,
+            current_synthetic: synthetic,
+            preorder,
+            range,
+            replace,
+            append,
+            punct_offset: None,
+        }
+    }
+
+    fn next_token(
+        preorder: &mut PreorderWithTokens,
+        replace: &mut FxHashMap<SyntaxElement, Vec<SyntheticToken>>,
+        append: &mut FxHashMap<SyntaxElement, Vec<SyntheticToken>>,
+    ) -> (Option<SyntaxToken>, Vec<SyntheticToken>) {
+        while let Some(ev) = preorder.next() {
+            let ele = match ev {
+                WalkEvent::Enter(ele) => ele,
+                WalkEvent::Leave(ele) => {
+                    if let Some(mut v) = append.remove(&ele) {
+                        if !v.is_empty() {
+                            v.reverse();
+                            return (None, v);
+                        }
+                    }
+                    continue;
+                }
+            };
+            if let Some(mut v) = replace.remove(&ele) {
+                preorder.skip_subtree();
+                if !v.is_empty() {
+                    v.reverse();
+                    return (None, v);
+                }
+            }
+            match ele {
+                SyntaxElement::Token(t) => return (Some(t), Vec::new()),
+                _ => {}
+            }
+        }
+        (None, Vec::new())
+    }
+}
+
+#[derive(Debug)]
+enum SynToken {
+    Ordinary(SyntaxToken),
+    // FIXME is this supposed to be `Punct`?
+    Punch(SyntaxToken, TextSize),
+    Synthetic(SyntheticToken),
+}
+
+impl SynToken {
+    fn token(&self) -> Option<&SyntaxToken> {
+        match self {
+            SynToken::Ordinary(it) | SynToken::Punch(it, _) => Some(it),
+            SynToken::Synthetic(_) => None,
+        }
+    }
+}
+
+impl SrcToken<Convertor> for SynToken {
+    fn kind(&self, _ctx: &Convertor) -> SyntaxKind {
+        match self {
+            SynToken::Ordinary(token) => token.kind(),
+            SynToken::Punch(token, _) => token.kind(),
+            SynToken::Synthetic(token) => token.kind,
+        }
+    }
+    fn to_char(&self, _ctx: &Convertor) -> Option<char> {
+        match self {
+            SynToken::Ordinary(_) => None,
+            SynToken::Punch(it, i) => it.text().chars().nth((*i).into()),
+            SynToken::Synthetic(token) if token.text.len() == 1 => token.text.chars().next(),
+            SynToken::Synthetic(_) => None,
+        }
+    }
+    fn to_text(&self, _ctx: &Convertor) -> SmolStr {
+        match self {
+            SynToken::Ordinary(token) => token.text().into(),
+            SynToken::Punch(token, _) => token.text().into(),
+            SynToken::Synthetic(token) => token.text.clone(),
+        }
+    }
+
+    fn synthetic_id(&self, _ctx: &Convertor) -> Option<SyntheticTokenId> {
+        match self {
+            SynToken::Synthetic(token) => Some(token.id),
+            _ => None,
+        }
+    }
+}
+
+impl TokenConvertor for Convertor {
+    type Token = SynToken;
+    fn convert_doc_comment(&self, token: &Self::Token) -> Option<Vec<tt::TokenTree>> {
+        convert_doc_comment(token.token()?)
+    }
+
+    fn bump(&mut self) -> Option<(Self::Token, TextRange)> {
+        if let Some((punct, offset)) = self.punct_offset.clone() {
+            if usize::from(offset) + 1 < punct.text().len() {
+                let offset = offset + TextSize::of('.');
+                let range = punct.text_range();
+                self.punct_offset = Some((punct.clone(), offset));
+                let range = TextRange::at(range.start() + offset, TextSize::of('.'));
+                return Some((SynToken::Punch(punct, offset), range));
+            }
+        }
+
+        if let Some(synth_token) = self.current_synthetic.pop() {
+            if self.current_synthetic.is_empty() {
+                let (new_current, new_synth) =
+                    Self::next_token(&mut self.preorder, &mut self.replace, &mut self.append);
+                self.current = new_current;
+                self.current_synthetic = new_synth;
+            }
+            let range = synth_token.range;
+            return Some((SynToken::Synthetic(synth_token), range));
+        }
+
+        let curr = self.current.clone()?;
+        if !&self.range.contains_range(curr.text_range()) {
+            return None;
+        }
+        let (new_current, new_synth) =
+            Self::next_token(&mut self.preorder, &mut self.replace, &mut self.append);
+        self.current = new_current;
+        self.current_synthetic = new_synth;
+        let token = if curr.kind().is_punct() {
+            self.punct_offset = Some((curr.clone(), 0.into()));
+            let range = curr.text_range();
+            let range = TextRange::at(range.start(), TextSize::of('.'));
+            (SynToken::Punch(curr, 0.into()), range)
+        } else {
+            self.punct_offset = None;
+            let range = curr.text_range();
+            (SynToken::Ordinary(curr), range)
+        };
+
+        Some(token)
+    }
+
+    fn peek(&self) -> Option<Self::Token> {
+        if let Some((punct, mut offset)) = self.punct_offset.clone() {
+            offset += TextSize::of('.');
+            if usize::from(offset) < punct.text().len() {
+                return Some(SynToken::Punch(punct, offset));
+            }
+        }
+
+        if let Some(synth_token) = self.current_synthetic.last() {
+            return Some(SynToken::Synthetic(synth_token.clone()));
+        }
+
+        let curr = self.current.clone()?;
+        if !self.range.contains_range(curr.text_range()) {
+            return None;
+        }
+
+        let token = if curr.kind().is_punct() {
+            SynToken::Punch(curr, 0.into())
+        } else {
+            SynToken::Ordinary(curr)
+        };
+        Some(token)
+    }
+
+    fn id_alloc(&mut self) -> &mut TokenIdAlloc {
+        &mut self.id_alloc
+    }
+}
+
+struct TtTreeSink<'a> {
+    buf: String,
+    cursor: Cursor<'a>,
+    open_delims: FxHashMap<tt::TokenId, TextSize>,
+    text_pos: TextSize,
+    inner: SyntaxTreeBuilder,
+    token_map: TokenMap,
+}
+
+impl<'a> TtTreeSink<'a> {
+    fn new(cursor: Cursor<'a>) -> Self {
+        TtTreeSink {
+            buf: String::new(),
+            cursor,
+            open_delims: FxHashMap::default(),
+            text_pos: 0.into(),
+            inner: SyntaxTreeBuilder::default(),
+            token_map: TokenMap::default(),
+        }
+    }
+
+    fn finish(mut self) -> (Parse<SyntaxNode>, TokenMap) {
+        self.token_map.shrink_to_fit();
+        (self.inner.finish(), self.token_map)
+    }
+}
+
+fn delim_to_str(d: tt::DelimiterKind, closing: bool) -> &'static str {
+    let texts = match d {
+        tt::DelimiterKind::Parenthesis => "()",
+        tt::DelimiterKind::Brace => "{}",
+        tt::DelimiterKind::Bracket => "[]",
+    };
+
+    let idx = closing as usize;
+    &texts[idx..texts.len() - (1 - idx)]
+}
+
+impl<'a> TtTreeSink<'a> {
+    fn token(&mut self, kind: SyntaxKind, mut n_tokens: u8) {
+        if kind == LIFETIME_IDENT {
+            n_tokens = 2;
+        }
+
+        let mut last = self.cursor;
+        for _ in 0..n_tokens {
+            let tmp: u8;
+            if self.cursor.eof() {
+                break;
+            }
+            last = self.cursor;
+            let text: &str = loop {
+                break match self.cursor.token_tree() {
+                    Some(tt::buffer::TokenTreeRef::Leaf(leaf, _)) => {
+                        // Mark the range if needed
+                        let (text, id) = match leaf {
+                            tt::Leaf::Ident(ident) => (ident.text.as_str(), ident.id),
+                            tt::Leaf::Punct(punct) => {
+                                assert!(punct.char.is_ascii());
+                                tmp = punct.char as u8;
+                                (std::str::from_utf8(std::slice::from_ref(&tmp)).unwrap(), punct.id)
+                            }
+                            tt::Leaf::Literal(lit) => (lit.text.as_str(), lit.id),
+                        };
+                        let range = TextRange::at(self.text_pos, TextSize::of(text));
+                        self.token_map.insert(id, range);
+                        self.cursor = self.cursor.bump();
+                        text
+                    }
+                    Some(tt::buffer::TokenTreeRef::Subtree(subtree, _)) => {
+                        self.cursor = self.cursor.subtree().unwrap();
+                        match subtree.delimiter {
+                            Some(d) => {
+                                self.open_delims.insert(d.id, self.text_pos);
+                                delim_to_str(d.kind, false)
+                            }
+                            None => continue,
+                        }
+                    }
+                    None => {
+                        let parent = self.cursor.end().unwrap();
+                        self.cursor = self.cursor.bump();
+                        match parent.delimiter {
+                            Some(d) => {
+                                if let Some(open_delim) = self.open_delims.get(&d.id) {
+                                    let open_range = TextRange::at(*open_delim, TextSize::of('('));
+                                    let close_range =
+                                        TextRange::at(self.text_pos, TextSize::of('('));
+                                    self.token_map.insert_delim(d.id, open_range, close_range);
+                                }
+                                delim_to_str(d.kind, true)
+                            }
+                            None => continue,
+                        }
+                    }
+                };
+            };
+            self.buf += text;
+            self.text_pos += TextSize::of(text);
+        }
+
+        self.inner.token(kind, self.buf.as_str());
+        self.buf.clear();
+        // Add whitespace between adjoint puncts
+        let next = last.bump();
+        if let (
+            Some(tt::buffer::TokenTreeRef::Leaf(tt::Leaf::Punct(curr), _)),
+            Some(tt::buffer::TokenTreeRef::Leaf(tt::Leaf::Punct(_), _)),
+        ) = (last.token_tree(), next.token_tree())
+        {
+            // Note: We always assume the semi-colon would be the last token in
+            // other parts of RA such that we don't add whitespace here.
+            if curr.spacing == tt::Spacing::Alone && curr.char != ';' {
+                self.inner.token(WHITESPACE, " ");
+                self.text_pos += TextSize::of(' ');
+            }
+        }
+    }
+
+    fn start_node(&mut self, kind: SyntaxKind) {
+        self.inner.start_node(kind);
+    }
+
+    fn finish_node(&mut self) {
+        self.inner.finish_node();
+    }
+
+    fn error(&mut self, error: String) {
+        self.inner.error(error, self.text_pos)
+    }
+}
diff --git a/src/tools/rust-analyzer/crates/mbe/src/to_parser_input.rs b/src/tools/rust-analyzer/crates/mbe/src/to_parser_input.rs
new file mode 100644
index 000000000..783c3ca4a
--- /dev/null
+++ b/src/tools/rust-analyzer/crates/mbe/src/to_parser_input.rs
@@ -0,0 +1,99 @@
+//! Convert macro-by-example tokens which are specific to macro expansion into a
+//! format that works for our parser.
+
+use syntax::{SyntaxKind, SyntaxKind::*, T};
+use tt::buffer::TokenBuffer;
+
+pub(crate) fn to_parser_input(buffer: &TokenBuffer<'_>) -> parser::Input {
+    let mut res = parser::Input::default();
+
+    let mut current = buffer.begin();
+
+    while !current.eof() {
+        let cursor = current;
+        let tt = cursor.token_tree();
+
+        // Check if it is lifetime
+        if let Some(tt::buffer::TokenTreeRef::Leaf(tt::Leaf::Punct(punct), _)) = tt {
+            if punct.char == '\'' {
+                let next = cursor.bump();
+                match next.token_tree() {
+                    Some(tt::buffer::TokenTreeRef::Leaf(tt::Leaf::Ident(_ident), _)) => {
+                        res.push(LIFETIME_IDENT);
+                        current = next.bump();
+                        continue;
+                    }
+                    _ => panic!("Next token must be ident : {:#?}", next.token_tree()),
+                }
+            }
+        }
+
+        current = match tt {
+            Some(tt::buffer::TokenTreeRef::Leaf(leaf, _)) => {
+                match leaf {
+                    tt::Leaf::Literal(lit) => {
+                        let is_negated = lit.text.starts_with('-');
+                        let inner_text = &lit.text[if is_negated { 1 } else { 0 }..];
+
+                        let kind = parser::LexedStr::single_token(inner_text)
+                            .map(|(kind, _error)| kind)
+                            .filter(|kind| {
+                                kind.is_literal()
+                                    && (!is_negated || matches!(kind, FLOAT_NUMBER | INT_NUMBER))
+                            })
+                            .unwrap_or_else(|| panic!("Fail to convert given literal {:#?}", &lit));
+
+                        res.push(kind);
+                    }
+                    tt::Leaf::Ident(ident) => match ident.text.as_ref() {
+                        "_" => res.push(T![_]),
+                        i if i.starts_with('\'') => res.push(LIFETIME_IDENT),
+                        _ => match SyntaxKind::from_keyword(&ident.text) {
+                            Some(kind) => res.push(kind),
+                            None => {
+                                let contextual_keyword =
+                                    SyntaxKind::from_contextual_keyword(&ident.text)
+                                        .unwrap_or(SyntaxKind::IDENT);
+                                res.push_ident(contextual_keyword);
+                            }
+                        },
+                    },
+                    tt::Leaf::Punct(punct) => {
+                        let kind = SyntaxKind::from_char(punct.char)
+                            .unwrap_or_else(|| panic!("{:#?} is not a valid punct", punct));
+                        res.push(kind);
+                        if punct.spacing == tt::Spacing::Joint {
+                            res.was_joint();
+                        }
+                    }
+                }
+                cursor.bump()
+            }
+            Some(tt::buffer::TokenTreeRef::Subtree(subtree, _)) => {
+                if let Some(d) = subtree.delimiter_kind() {
+                    res.push(match d {
+                        tt::DelimiterKind::Parenthesis => T!['('],
+                        tt::DelimiterKind::Brace => T!['{'],
+                        tt::DelimiterKind::Bracket => T!['['],
+                    });
+                }
+                cursor.subtree().unwrap()
+            }
+            None => match cursor.end() {
+                Some(subtree) => {
+                    if let Some(d) = subtree.delimiter_kind() {
+                        res.push(match d {
+                            tt::DelimiterKind::Parenthesis => T![')'],
+                            tt::DelimiterKind::Brace => T!['}'],
+                            tt::DelimiterKind::Bracket => T![']'],
+                        })
+                    }
+                    cursor.bump()
+                }
+                None => continue,
+            },
+        };
+    }
+
+    res
+}
diff --git a/src/tools/rust-analyzer/crates/mbe/src/token_map.rs b/src/tools/rust-analyzer/crates/mbe/src/token_map.rs
new file mode 100644
index 000000000..c923e7a69
--- /dev/null
+++ b/src/tools/rust-analyzer/crates/mbe/src/token_map.rs
@@ -0,0 +1,113 @@
+//! Mapping between `TokenId`s and the token's position in macro definitions or inputs.
+
+use std::hash::Hash;
+
+use parser::{SyntaxKind, T};
+use syntax::{TextRange, TextSize};
+
+use crate::syntax_bridge::SyntheticTokenId;
+
+#[derive(Debug, PartialEq, Eq, Clone, Copy, Hash)]
+enum TokenTextRange {
+    Token(TextRange),
+    Delimiter(TextRange),
+}
+
+impl TokenTextRange {
+    fn by_kind(self, kind: SyntaxKind) -> Option<TextRange> {
+        match self {
+            TokenTextRange::Token(it) => Some(it),
+            TokenTextRange::Delimiter(it) => match kind {
+                T!['{'] | T!['('] | T!['['] => Some(TextRange::at(it.start(), 1.into())),
+                T!['}'] | T![')'] | T![']'] => {
+                    Some(TextRange::at(it.end() - TextSize::of('}'), 1.into()))
+                }
+                _ => None,
+            },
+        }
+    }
+}
+
+/// Maps `tt::TokenId` to the relative range of the original token.
+#[derive(Debug, PartialEq, Eq, Clone, Default, Hash)]
+pub struct TokenMap {
+    /// Maps `tt::TokenId` to the *relative* source range.
+    entries: Vec<(tt::TokenId, TokenTextRange)>,
+    pub synthetic_entries: Vec<(tt::TokenId, SyntheticTokenId)>,
+}
+
+impl TokenMap {
+    pub fn token_by_range(&self, relative_range: TextRange) -> Option<tt::TokenId> {
+        let &(token_id, _) = self.entries.iter().find(|(_, range)| match range {
+            TokenTextRange::Token(it) => *it == relative_range,
+            TokenTextRange::Delimiter(it) => {
+                let open = TextRange::at(it.start(), 1.into());
+                let close = TextRange::at(it.end() - TextSize::of('}'), 1.into());
+                open == relative_range || close == relative_range
+            }
+        })?;
+        Some(token_id)
+    }
+
+    pub fn ranges_by_token(
+        &self,
+        token_id: tt::TokenId,
+        kind: SyntaxKind,
+    ) -> impl Iterator<Item = TextRange> + '_ {
+        self.entries
+            .iter()
+            .filter(move |&&(tid, _)| tid == token_id)
+            .filter_map(move |(_, range)| range.by_kind(kind))
+    }
+
+    pub fn synthetic_token_id(&self, token_id: tt::TokenId) -> Option<SyntheticTokenId> {
+        self.synthetic_entries.iter().find(|(tid, _)| *tid == token_id).map(|(_, id)| *id)
+    }
+
+    pub fn first_range_by_token(
+        &self,
+        token_id: tt::TokenId,
+        kind: SyntaxKind,
+    ) -> Option<TextRange> {
+        self.ranges_by_token(token_id, kind).next()
+    }
+
+    pub(crate) fn shrink_to_fit(&mut self) {
+        self.entries.shrink_to_fit();
+        self.synthetic_entries.shrink_to_fit();
+    }
+
+    pub(crate) fn insert(&mut self, token_id: tt::TokenId, relative_range: TextRange) {
+        self.entries.push((token_id, TokenTextRange::Token(relative_range)));
+    }
+
+    pub(crate) fn insert_synthetic(&mut self, token_id: tt::TokenId, id: SyntheticTokenId) {
+        self.synthetic_entries.push((token_id, id));
+    }
+
+    pub(crate) fn insert_delim(
+        &mut self,
+        token_id: tt::TokenId,
+        open_relative_range: TextRange,
+        close_relative_range: TextRange,
+    ) -> usize {
+        let res = self.entries.len();
+        let cover = open_relative_range.cover(close_relative_range);
+
+        self.entries.push((token_id, TokenTextRange::Delimiter(cover)));
+        res
+    }
+
+    pub(crate) fn update_close_delim(&mut self, idx: usize, close_relative_range: TextRange) {
+        let (_, token_text_range) = &mut self.entries[idx];
+        if let TokenTextRange::Delimiter(dim) = token_text_range {
+            let cover = dim.cover(close_relative_range);
+            *token_text_range = TokenTextRange::Delimiter(cover);
+        }
+    }
+
+    pub(crate) fn remove_delim(&mut self, idx: usize) {
+        // FIXME: This could be accidentally quadratic
+        self.entries.remove(idx);
+    }
+}
diff --git a/src/tools/rust-analyzer/crates/mbe/src/tt_iter.rs b/src/tools/rust-analyzer/crates/mbe/src/tt_iter.rs
new file mode 100644
index 000000000..7aceb676c
--- /dev/null
+++ b/src/tools/rust-analyzer/crates/mbe/src/tt_iter.rs
@@ -0,0 +1,160 @@
+//! A "Parser" structure for token trees. We use this when parsing a declarative
+//! macro definition into a list of patterns and templates.
+
+use syntax::SyntaxKind;
+use tt::buffer::TokenBuffer;
+
+use crate::{to_parser_input::to_parser_input, ExpandError, ExpandResult};
+
+#[derive(Debug, Clone)]
+pub(crate) struct TtIter<'a> {
+    pub(crate) inner: std::slice::Iter<'a, tt::TokenTree>,
+}
+
+impl<'a> TtIter<'a> {
+    pub(crate) fn new(subtree: &'a tt::Subtree) -> TtIter<'a> {
+        TtIter { inner: subtree.token_trees.iter() }
+    }
+
+    pub(crate) fn expect_char(&mut self, char: char) -> Result<(), ()> {
+        match self.next() {
+            Some(&tt::TokenTree::Leaf(tt::Leaf::Punct(tt::Punct { char: c, .. }))) if c == char => {
+                Ok(())
+            }
+            _ => Err(()),
+        }
+    }
+
+    pub(crate) fn expect_any_char(&mut self, chars: &[char]) -> Result<(), ()> {
+        match self.next() {
+            Some(tt::TokenTree::Leaf(tt::Leaf::Punct(tt::Punct { char: c, .. })))
+                if chars.contains(c) =>
+            {
+                Ok(())
+            }
+            _ => Err(()),
+        }
+    }
+
+    pub(crate) fn expect_subtree(&mut self) -> Result<&'a tt::Subtree, ()> {
+        match self.next() {
+            Some(tt::TokenTree::Subtree(it)) => Ok(it),
+            _ => Err(()),
+        }
+    }
+
+    pub(crate) fn expect_leaf(&mut self) -> Result<&'a tt::Leaf, ()> {
+        match self.next() {
+            Some(tt::TokenTree::Leaf(it)) => Ok(it),
+            _ => Err(()),
+        }
+    }
+
+    pub(crate) fn expect_ident(&mut self) -> Result<&'a tt::Ident, ()> {
+        match self.expect_leaf()? {
+            tt::Leaf::Ident(it) if it.text != "_" => Ok(it),
+            _ => Err(()),
+        }
+    }
+
+    pub(crate) fn expect_ident_or_underscore(&mut self) -> Result<&'a tt::Ident, ()> {
+        match self.expect_leaf()? {
+            tt::Leaf::Ident(it) => Ok(it),
+            _ => Err(()),
+        }
+    }
+
+    pub(crate) fn expect_literal(&mut self) -> Result<&'a tt::Leaf, ()> {
+        let it = self.expect_leaf()?;
+        match it {
+            tt::Leaf::Literal(_) => Ok(it),
+            tt::Leaf::Ident(ident) if ident.text == "true" || ident.text == "false" => Ok(it),
+            _ => Err(()),
+        }
+    }
+
+    pub(crate) fn expect_u32_literal(&mut self) -> Result<u32, ()> {
+        match self.expect_literal()? {
+            tt::Leaf::Literal(lit) => lit.text.parse().map_err(drop),
+            _ => Err(()),
+        }
+    }
+
+    pub(crate) fn expect_punct(&mut self) -> Result<&'a tt::Punct, ()> {
+        match self.expect_leaf()? {
+            tt::Leaf::Punct(it) => Ok(it),
+            _ => Err(()),
+        }
+    }
+
+    pub(crate) fn expect_fragment(
+        &mut self,
+        entry_point: parser::PrefixEntryPoint,
+    ) -> ExpandResult<Option<tt::TokenTree>> {
+        let buffer = TokenBuffer::from_tokens(self.inner.as_slice());
+        let parser_input = to_parser_input(&buffer);
+        let tree_traversal = entry_point.parse(&parser_input);
+
+        let mut cursor = buffer.begin();
+        let mut error = false;
+        for step in tree_traversal.iter() {
+            match step {
+                parser::Step::Token { kind, mut n_input_tokens } => {
+                    if kind == SyntaxKind::LIFETIME_IDENT {
+                        n_input_tokens = 2;
+                    }
+                    for _ in 0..n_input_tokens {
+                        cursor = cursor.bump_subtree();
+                    }
+                }
+                parser::Step::Enter { .. } | parser::Step::Exit => (),
+                parser::Step::Error { .. } => error = true,
+            }
+        }
+
+        let err = if error || !cursor.is_root() {
+            Some(ExpandError::binding_error(format!("expected {entry_point:?}")))
+        } else {
+            None
+        };
+
+        let mut curr = buffer.begin();
+        let mut res = vec![];
+
+        if cursor.is_root() {
+            while curr != cursor {
+                if let Some(token) = curr.token_tree() {
+                    res.push(token);
+                }
+                curr = curr.bump();
+            }
+        }
+        self.inner = self.inner.as_slice()[res.len()..].iter();
+        let res = match res.len() {
+            1 => Some(res[0].cloned()),
+            0 => None,
+            _ => Some(tt::TokenTree::Subtree(tt::Subtree {
+                delimiter: None,
+                token_trees: res.into_iter().map(|it| it.cloned()).collect(),
+            })),
+        };
+        ExpandResult { value: res, err }
+    }
+
+    pub(crate) fn peek_n(&self, n: usize) -> Option<&tt::TokenTree> {
+        self.inner.as_slice().get(n)
+    }
+}
+
+impl<'a> Iterator for TtIter<'a> {
+    type Item = &'a tt::TokenTree;
+    fn next(&mut self) -> Option<Self::Item> {
+        self.inner.next()
+    }
+
+    fn size_hint(&self) -> (usize, Option<usize>) {
+        self.inner.size_hint()
+    }
+}
+
+impl<'a> std::iter::ExactSizeIterator for TtIter<'a> {}