5 files changed, 451 insertions, 0 deletions

diff --git a/crates/ra_mbe/Cargo.toml b/crates/ra_mbe/Cargo.toml
new file mode 100644
index 000000000..b7f03cd38
--- /dev/null
+++ b/crates/ra_mbe/Cargo.toml
@@ -0,0 +1,10 @@
+[package]
+edition = "2018"
+name = "ra_mbe"
+version = "0.1.0"
+authors = ["Aleksey Kladov <[email protected]>"]
+
+[dependencies]
+tt = { path = "../ra_tt", package = "ra_tt" }
+rustc-hash = "1.0.0"
+smol_str = "0.1.9"
diff --git a/crates/ra_mbe/src/lib.rs b/crates/ra_mbe/src/lib.rs
new file mode 100644
index 000000000..38bf3431a
--- /dev/null
+++ b/crates/ra_mbe/src/lib.rs
@@ -0,0 +1,88 @@
+macro_rules! impl_froms {
+    ($e:ident: $($v:ident), *) => {
+        $(
+            impl From<$v> for $e {
+                fn from(it: $v) -> $e {
+                    $e::$v(it)
+                }
+            }
+        )*
+    }
+}
+
+mod tt_cursor;
+mod mbe_parser;
+mod mbe_expander;
+
+use smol_str::SmolStr;
+
+pub use tt::{Delimiter, Punct};
+
+pub use crate::{
+    mbe_parser::parse,
+    mbe_expander::exapnd,
+};
+
+#[derive(Debug)]
+pub struct MacroRules {
+    pub(crate) rules: Vec<Rule>,
+}
+
+#[derive(Debug)]
+pub(crate) struct Rule {
+    pub(crate) lhs: Subtree,
+    pub(crate) rhs: Subtree,
+}
+
+#[derive(Debug)]
+pub(crate) enum TokenTree {
+    Leaf(Leaf),
+    Subtree(Subtree),
+    Repeat(Repeat),
+}
+impl_froms!(TokenTree: Leaf, Subtree, Repeat);
+
+#[derive(Debug)]
+pub(crate) enum Leaf {
+    Literal(Literal),
+    Punct(Punct),
+    Ident(Ident),
+    Var(Var),
+}
+impl_froms!(Leaf: Literal, Punct, Ident, Var);
+
+#[derive(Debug)]
+pub(crate) struct Subtree {
+    pub(crate) delimiter: Delimiter,
+    pub(crate) token_trees: Vec<TokenTree>,
+}
+
+#[derive(Debug)]
+pub(crate) struct Repeat {
+    pub(crate) subtree: Subtree,
+    pub(crate) kind: RepeatKind,
+    pub(crate) separator: Option<char>,
+}
+
+#[derive(Debug)]
+pub(crate) enum RepeatKind {
+    ZeroOrMore,
+    OneOrMore,
+    ZeroOrOne,
+}
+
+#[derive(Debug)]
+pub(crate) struct Literal {
+    pub(crate) text: SmolStr,
+}
+
+#[derive(Debug)]
+pub(crate) struct Ident {
+    pub(crate) text: SmolStr,
+}
+
+#[derive(Debug)]
+pub(crate) struct Var {
+    pub(crate) text: SmolStr,
+    pub(crate) kind: Option<SmolStr>,
+}
diff --git a/crates/ra_mbe/src/mbe_expander.rs b/crates/ra_mbe/src/mbe_expander.rs
new file mode 100644
index 000000000..92ad26889
--- /dev/null
+++ b/crates/ra_mbe/src/mbe_expander.rs
@@ -0,0 +1,169 @@
+use rustc_hash::FxHashMap;
+use smol_str::SmolStr;
+
+use crate::{self as mbe, tt_cursor::TtCursor};
+
+pub fn exapnd(rules: &mbe::MacroRules, input: &tt::Subtree) -> Option<tt::Subtree> {
+    rules.rules.iter().find_map(|it| expand_rule(it, input))
+}
+
+fn expand_rule(rule: &mbe::Rule, input: &tt::Subtree) -> Option<tt::Subtree> {
+    let mut input = TtCursor::new(input);
+    let bindings = match_lhs(&rule.lhs, &mut input)?;
+    expand_subtree(&rule.rhs, &bindings, &mut Vec::new())
+}
+
+#[derive(Debug, Default)]
+struct Bindings {
+    inner: FxHashMap<SmolStr, Binding>,
+}
+
+#[derive(Debug)]
+enum Binding {
+    Simple(tt::TokenTree),
+    Nested(Vec<Binding>),
+}
+
+impl Bindings {
+    fn get(&self, name: &SmolStr, nesting: &[usize]) -> Option<&tt::TokenTree> {
+        let mut b = self.inner.get(name)?;
+        for &idx in nesting.iter() {
+            b = match b {
+                Binding::Simple(_) => break,
+                Binding::Nested(bs) => bs.get(idx)?,
+            };
+        }
+        match b {
+            Binding::Simple(it) => Some(it),
+            Binding::Nested(_) => None,
+        }
+    }
+    fn push_nested(&mut self, nested: Bindings) -> Option<()> {
+        for (key, value) in nested.inner {
+            if !self.inner.contains_key(&key) {
+                self.inner.insert(key.clone(), Binding::Nested(Vec::new()));
+            }
+            match self.inner.get_mut(&key) {
+                Some(Binding::Nested(it)) => it.push(value),
+                _ => return None,
+            }
+        }
+        Some(())
+    }
+}
+
+fn match_lhs(pattern: &mbe::Subtree, input: &mut TtCursor) -> Option<Bindings> {
+    let mut res = Bindings::default();
+    for pat in pattern.token_trees.iter() {
+        match pat {
+            mbe::TokenTree::Leaf(leaf) => match leaf {
+                mbe::Leaf::Var(mbe::Var { text, kind }) => {
+                    let kind = kind.clone()?;
+                    match kind.as_str() {
+                        "ident" => {
+                            let ident = input.eat_ident()?.clone();
+                            res.inner.insert(
+                                text.clone(),
+                                Binding::Simple(tt::Leaf::from(ident).into()),
+                            );
+                        }
+                        _ => return None,
+                    }
+                }
+                mbe::Leaf::Punct(punct) => {
+                    if input.eat_punct()? != punct {
+                        return None;
+                    }
+                }
+                _ => return None,
+            },
+            mbe::TokenTree::Repeat(mbe::Repeat {
+                subtree,
+                kind: _,
+                separator,
+            }) => {
+                while let Some(nested) = match_lhs(subtree, input) {
+                    res.push_nested(nested)?;
+                    if separator.is_some() && !input.is_eof() {
+                        input.eat_punct()?;
+                    }
+                }
+            }
+            _ => {}
+        }
+    }
+    Some(res)
+}
+
+/*
+
+macro_rules! impl_froms {
+    ($e:ident: $($v:ident),*) => {
+        $(
+            impl From<$v> for $e {
+                fn from(it: $v) -> $e {
+                    $e::$v(it)
+                }
+            }
+        )*
+    }
+}
+
+impl_froms! (Foo: Bar, Baz)
+
+*/
+
+fn expand_subtree(
+    template: &mbe::Subtree,
+    bindings: &Bindings,
+    nesting: &mut Vec<usize>,
+) -> Option<tt::Subtree> {
+    let token_trees = template
+        .token_trees
+        .iter()
+        .map(|it| expand_tt(it, bindings, nesting))
+        .collect::<Option<Vec<_>>>()?;
+
+    Some(tt::Subtree {
+        token_trees,
+        delimiter: template.delimiter,
+    })
+}
+
+fn expand_tt(
+    template: &mbe::TokenTree,
+    bindings: &Bindings,
+    nesting: &mut Vec<usize>,
+) -> Option<tt::TokenTree> {
+    let res: tt::TokenTree = match template {
+        mbe::TokenTree::Subtree(subtree) => expand_subtree(subtree, bindings, nesting)?.into(),
+        mbe::TokenTree::Repeat(repeat) => {
+            let mut token_trees = Vec::new();
+            nesting.push(0);
+            while let Some(t) = expand_subtree(&repeat.subtree, bindings, nesting) {
+                let idx = nesting.pop().unwrap();
+                nesting.push(idx + 1);
+                token_trees.push(t.into())
+            }
+            nesting.pop().unwrap();
+            tt::Subtree {
+                token_trees,
+                delimiter: tt::Delimiter::None,
+            }
+            .into()
+        }
+        mbe::TokenTree::Leaf(leaf) => match leaf {
+            mbe::Leaf::Ident(ident) => tt::Leaf::from(tt::Ident {
+                text: ident.text.clone(),
+            })
+            .into(),
+            mbe::Leaf::Punct(punct) => tt::Leaf::from(punct.clone()).into(),
+            mbe::Leaf::Var(v) => bindings.get(&v.text, nesting)?.clone(),
+            mbe::Leaf::Literal(l) => tt::Leaf::from(tt::Literal {
+                text: l.text.clone(),
+            })
+            .into(),
+        },
+    };
+    Some(res)
+}
diff --git a/crates/ra_mbe/src/mbe_parser.rs b/crates/ra_mbe/src/mbe_parser.rs
new file mode 100644
index 000000000..a70ed1d52
--- /dev/null
+++ b/crates/ra_mbe/src/mbe_parser.rs
@@ -0,0 +1,93 @@
+use crate::{self as mbe, tt_cursor::TtCursor};
+
+/// This module parses a raw `tt::TokenStream` into macro-by-example token
+/// stream. This is a *mostly* identify function, expect for handling of
+/// `$var:tt_kind` and `$(repeat),*` constructs.
+
+pub fn parse(tt: &tt::Subtree) -> Option<mbe::MacroRules> {
+    let mut parser = TtCursor::new(tt);
+    let mut rules = Vec::new();
+    while !parser.is_eof() {
+        rules.push(parse_rule(&mut parser)?)
+    }
+    Some(mbe::MacroRules { rules })
+}
+
+fn parse_rule(p: &mut TtCursor) -> Option<mbe::Rule> {
+    let lhs = parse_subtree(p.eat_subtree()?)?;
+    p.expect_char('=')?;
+    p.expect_char('>')?;
+    let rhs = parse_subtree(p.eat_subtree()?)?;
+    Some(mbe::Rule { lhs, rhs })
+}
+
+fn parse_subtree(tt: &tt::Subtree) -> Option<mbe::Subtree> {
+    let mut token_trees = Vec::new();
+    let mut p = TtCursor::new(tt);
+    while let Some(tt) = p.eat() {
+        let child: mbe::TokenTree = match tt {
+            tt::TokenTree::Leaf(leaf) => match leaf {
+                tt::Leaf::Punct(tt::Punct { char: '$', .. }) => {
+                    if p.at_ident().is_some() {
+                        mbe::Leaf::from(parse_var(&mut p)?).into()
+                    } else {
+                        parse_repeat(&mut p)?.into()
+                    }
+                }
+                tt::Leaf::Punct(punct) => mbe::Leaf::from(*punct).into(),
+                tt::Leaf::Ident(tt::Ident { text }) => {
+                    mbe::Leaf::from(mbe::Ident { text: text.clone() }).into()
+                }
+                tt::Leaf::Literal(tt::Literal { text }) => {
+                    mbe::Leaf::from(mbe::Literal { text: text.clone() }).into()
+                }
+            },
+            tt::TokenTree::Subtree(subtree) => parse_subtree(&subtree)?.into(),
+        };
+        token_trees.push(child);
+    }
+    Some(mbe::Subtree {
+        token_trees,
+        delimiter: tt.delimiter,
+    })
+}
+
+fn parse_var(p: &mut TtCursor) -> Option<mbe::Var> {
+    let ident = p.eat_ident().unwrap();
+    let text = ident.text.clone();
+    let kind = if p.at_char(':') {
+        p.bump();
+        if let Some(ident) = p.eat_ident() {
+            Some(ident.text.clone())
+        } else {
+            p.rev_bump();
+            None
+        }
+    } else {
+        None
+    };
+    Some(mbe::Var { text, kind })
+}
+
+fn parse_repeat(p: &mut TtCursor) -> Option<mbe::Repeat> {
+    let subtree = p.eat_subtree().unwrap();
+    let subtree = parse_subtree(subtree)?;
+    let sep = p.eat_punct()?;
+    let (separator, rep) = match sep.char {
+        '*' | '+' | '?' => (None, sep.char),
+        char => (Some(char), p.eat_punct()?.char),
+    };
+
+    let kind = match rep {
+        '*' => mbe::RepeatKind::ZeroOrMore,
+        '+' => mbe::RepeatKind::OneOrMore,
+        '?' => mbe::RepeatKind::ZeroOrOne,
+        _ => return None,
+    };
+    p.bump();
+    Some(mbe::Repeat {
+        subtree,
+        kind,
+        separator,
+    })
+}
diff --git a/crates/ra_mbe/src/tt_cursor.rs b/crates/ra_mbe/src/tt_cursor.rs
new file mode 100644
index 000000000..30c8eda67
--- /dev/null
+++ b/crates/ra_mbe/src/tt_cursor.rs
@@ -0,0 +1,91 @@
+#[derive(Clone)]
+pub(crate) struct TtCursor<'a> {
+    subtree: &'a tt::Subtree,
+    pos: usize,
+}
+
+impl<'a> TtCursor<'a> {
+    pub(crate) fn new(subtree: &'a tt::Subtree) -> TtCursor<'a> {
+        TtCursor { subtree, pos: 0 }
+    }
+
+    pub(crate) fn is_eof(&self) -> bool {
+        self.pos == self.subtree.token_trees.len()
+    }
+
+    pub(crate) fn current(&self) -> Option<&'a tt::TokenTree> {
+        self.subtree.token_trees.get(self.pos)
+    }
+
+    pub(crate) fn at_punct(&self) -> Option<&'a tt::Punct> {
+        match self.current() {
+            Some(tt::TokenTree::Leaf(tt::Leaf::Punct(it))) => Some(it),
+            _ => None,
+        }
+    }
+
+    pub(crate) fn at_char(&self, char: char) -> bool {
+        match self.at_punct() {
+            Some(tt::Punct { char: c, .. }) if *c == char => true,
+            _ => false,
+        }
+    }
+
+    pub(crate) fn at_ident(&mut self) -> Option<&'a tt::Ident> {
+        match self.current() {
+            Some(tt::TokenTree::Leaf(tt::Leaf::Ident(i))) => Some(i),
+            _ => None,
+        }
+    }
+
+    pub(crate) fn bump(&mut self) {
+        self.pos += 1;
+    }
+    pub(crate) fn rev_bump(&mut self) {
+        self.pos -= 1;
+    }
+
+    pub(crate) fn eat(&mut self) -> Option<&'a tt::TokenTree> {
+        match self.current() {
+            Some(it) => {
+                self.bump();
+                Some(it)
+            }
+            None => None,
+        }
+    }
+
+    pub(crate) fn eat_subtree(&mut self) -> Option<&'a tt::Subtree> {
+        match self.current()? {
+            tt::TokenTree::Subtree(sub) => {
+                self.bump();
+                Some(sub)
+            }
+            _ => return None,
+        }
+    }
+
+    pub(crate) fn eat_punct(&mut self) -> Option<&'a tt::Punct> {
+        if let Some(it) = self.at_punct() {
+            self.bump();
+            return Some(it);
+        }
+        None
+    }
+
+    pub(crate) fn eat_ident(&mut self) -> Option<&'a tt::Ident> {
+        if let Some(i) = self.at_ident() {
+            self.bump();
+            return Some(i);
+        }
+        None
+    }
+
+    pub(crate) fn expect_char(&mut self, char: char) -> Option<()> {
+        if self.at_char(char) {
+            self.bump();
+            return Some(());
+        }
+        None
+    }
+}