8 files changed, 215 insertions, 40 deletions

diff --git a/Cargo.lock b/Cargo.lock
index b48721622..a9bc80c40 100644
--- a/Cargo.lock
+++ b/Cargo.lock
@@ -1022,6 +1022,7 @@ dependencies = [
 name = "ra_macros"
 version = "0.1.0"
 dependencies = [
+ "join_to_string 0.1.3 (registry+https://github.com/rust-lang/crates.io-index)",
  "rustc-hash 1.0.1 (registry+https://github.com/rust-lang/crates.io-index)",
  "smol_str 0.1.9 (registry+https://github.com/rust-lang/crates.io-index)",
 ]
diff --git a/crates/ra_hir/src/macros.rs b/crates/ra_hir/src/macros.rs
index 7e9aba3f2..059543bf2 100644
--- a/crates/ra_hir/src/macros.rs
+++ b/crates/ra_hir/src/macros.rs
@@ -254,7 +254,7 @@ fn convert_tt(tt: &SyntaxNode) -> Option<tt::Subtree> {
 
 #[test]
 fn test_convert_tt() {
-    let text = r#"
+    let macro_defenition = r#"
 macro_rules! impl_froms {
     ($e:ident: $($v:ident),*) => {
         $(
@@ -267,13 +267,32 @@ macro_rules! impl_froms {
     }
 }
 "#;
-    let source_file = ast::SourceFile::parse(text);
-    let maco_call = source_file
+
+    let macro_invocation = r#"
+impl_froms!(TokenTree: Leaf, Subtree);
+"#;
+
+    let source_file = ast::SourceFile::parse(macro_defenition);
+    let macro_defenition = source_file
         .syntax()
         .descendants()
         .find_map(ast::MacroCall::cast)
         .unwrap();
-    let tt = macro_call_to_tt(maco_call).unwrap();
-    let tt = mbe::parse(&tt);
-    assert!(tt.is_some());
+
+    let source_file = ast::SourceFile::parse(macro_invocation);
+    let macro_invocation = source_file
+        .syntax()
+        .descendants()
+        .find_map(ast::MacroCall::cast)
+        .unwrap();
+
+    let defenition_tt = macro_call_to_tt(macro_defenition).unwrap();
+    let invocation_tt = macro_call_to_tt(macro_invocation).unwrap();
+    let mbe = mbe::parse(&defenition_tt).unwrap();
+    let expansion = mbe::exapnd(&mbe, &invocation_tt).unwrap();
+    assert_eq!(
+        expansion.to_string(),
+        "{(impl From < Leaf > for TokenTree {fn from (it : Leaf) - > TokenTree {TokenTree : : Leaf (it)}}) \
+          (impl From < Subtree > for TokenTree {fn from (it : Subtree) - > TokenTree {TokenTree : : Subtree (it)}})}"
+    )
 }
diff --git a/crates/ra_macros/Cargo.toml b/crates/ra_macros/Cargo.toml
index 7d3cb055c..1c9cc9e92 100644
--- a/crates/ra_macros/Cargo.toml
+++ b/crates/ra_macros/Cargo.toml
@@ -7,3 +7,4 @@ authors = ["Aleksey Kladov <[email protected]>"]
 [dependencies]
 rustc-hash = "1.0.0"
 smol_str = "0.1.9"
+join_to_string = "0.1.3"
diff --git a/crates/ra_macros/src/mbe.rs b/crates/ra_macros/src/mbe.rs
index 6a168a1b5..ac76d64e4 100644
--- a/crates/ra_macros/src/mbe.rs
+++ b/crates/ra_macros/src/mbe.rs
@@ -1,6 +1,6 @@
 use smol_str::SmolStr;
 
-use crate::tt::Delimiter;
+pub(crate) use crate::tt::{Delimiter, Punct};
 
 pub use crate::{
     mbe_parser::parse,
@@ -61,11 +61,6 @@ pub(crate) struct Literal {
 }
 
 #[derive(Debug)]
-pub(crate) struct Punct {
-    pub(crate) char: char,
-}
-
-#[derive(Debug)]
 pub(crate) struct Ident {
     pub(crate) text: SmolStr,
 }
diff --git a/crates/ra_macros/src/mbe_expander.rs b/crates/ra_macros/src/mbe_expander.rs
index f55c337da..5d5363261 100644
--- a/crates/ra_macros/src/mbe_expander.rs
+++ b/crates/ra_macros/src/mbe_expander.rs
@@ -1,15 +1,16 @@
 use rustc_hash::FxHashMap;
 use smol_str::SmolStr;
 
-use crate::{mbe, tt};
+use crate::{mbe, tt, 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 bindings = match_lhs(&rule.lhs, input)?;
-    expand_rhs(&rule.rhs, &bindings)
+    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)]
@@ -23,25 +24,35 @@ enum Binding {
     Nested(Vec<Binding>),
 }
 
-/*
-
-macro_rules! impl_froms {
-    ($e:ident: $($v:ident),*) => {
-        $(
-            impl From<$v> for $e {
-                fn from(it: $v) -> $e {
-                    $e::$v(it)
-                }
+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(())
     }
 }
 
-impl_froms! (Foo: Bar, Baz)
-
-*/
-
-fn match_lhs(pattern: &mbe::Subtree, input: &tt::Subtree) -> Option<Bindings> {
+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 {
@@ -49,18 +60,110 @@ fn match_lhs(pattern: &mbe::Subtree, input: &tt::Subtree) -> Option<Bindings> {
                 mbe::Leaf::Var(mbe::Var { text, kind }) => {
                     let kind = kind.clone()?;
                     match kind.as_str() {
-                        "ident" => (),
+                        "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)
 }
 
-fn expand_rhs(template: &mbe::Subtree, bindings: &Bindings) -> Option<tt::Subtree> {
-    None
+/*
+
+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_macros/src/mbe_parser.rs b/crates/ra_macros/src/mbe_parser.rs
index 024d3a040..279ab2f25 100644
--- a/crates/ra_macros/src/mbe_parser.rs
+++ b/crates/ra_macros/src/mbe_parser.rs
@@ -84,7 +84,7 @@ fn parse_repeat(p: &mut TtCursor) -> Option<mbe::Repeat> {
     let kind = match rep {
         '*' => mbe::RepeatKind::ZeroOrMore,
         '+' => mbe::RepeatKind::OneOrMore,
-        '?' => mbe::RepeatKind::ZeroOrMore,
+        '?' => mbe::RepeatKind::ZeroOrOne,
         _ => return None,
     };
     p.bump();
diff --git a/crates/ra_macros/src/tt.rs b/crates/ra_macros/src/tt.rs
index 364eed9e6..56e930f00 100644
--- a/crates/ra_macros/src/tt.rs
+++ b/crates/ra_macros/src/tt.rs
@@ -1,13 +1,16 @@
+use std::fmt;
+
 use smol_str::SmolStr;
+use join_to_string::join;
 
-#[derive(Debug)]
+#[derive(Debug, Clone)]
 pub enum TokenTree {
     Leaf(Leaf),
     Subtree(Subtree),
 }
 impl_froms!(TokenTree: Leaf, Subtree);
 
-#[derive(Debug)]
+#[derive(Debug, Clone)]
 pub enum Leaf {
     Literal(Literal),
     Punct(Punct),
@@ -15,7 +18,7 @@ pub enum Leaf {
 }
 impl_froms!(Leaf: Literal, Punct, Ident);
 
-#[derive(Debug)]
+#[derive(Debug, Clone)]
 pub struct Subtree {
     pub delimiter: Delimiter,
     pub token_trees: Vec<TokenTree>,
@@ -29,17 +32,69 @@ pub enum Delimiter {
     None,
 }
 
-#[derive(Debug)]
+#[derive(Debug, Clone)]
 pub struct Literal {
     pub text: SmolStr,
 }
 
-#[derive(Debug)]
+#[derive(Debug, Clone, PartialEq, Eq)]
 pub struct Punct {
     pub char: char,
 }
 
-#[derive(Debug)]
+#[derive(Debug, Clone)]
 pub struct Ident {
     pub text: SmolStr,
 }
+
+impl fmt::Display for TokenTree {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        match self {
+            TokenTree::Leaf(it) => fmt::Display::fmt(it, f),
+            TokenTree::Subtree(it) => fmt::Display::fmt(it, f),
+        }
+    }
+}
+
+impl fmt::Display for Subtree {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        let (l, r) = match self.delimiter {
+            Delimiter::Parenthesis => ("(", ")"),
+            Delimiter::Brace => ("{", "}"),
+            Delimiter::Bracket => ("[", "]"),
+            Delimiter::None => ("", ""),
+        };
+        join(self.token_trees.iter())
+            .separator(" ")
+            .surround_with(l, r)
+            .to_fmt(f)
+    }
+}
+
+impl fmt::Display for Leaf {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        match self {
+            Leaf::Ident(it) => fmt::Display::fmt(it, f),
+            Leaf::Literal(it) => fmt::Display::fmt(it, f),
+            Leaf::Punct(it) => fmt::Display::fmt(it, f),
+        }
+    }
+}
+
+impl fmt::Display for Ident {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        fmt::Display::fmt(&self.text, f)
+    }
+}
+
+impl fmt::Display for Literal {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        fmt::Display::fmt(&self.text, f)
+    }
+}
+
+impl fmt::Display for Punct {
+    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
+        fmt::Display::fmt(&self.char, f)
+    }
+}
diff --git a/crates/ra_macros/src/tt_cursor.rs b/crates/ra_macros/src/tt_cursor.rs
index 380c60b40..6dc9f400d 100644
--- a/crates/ra_macros/src/tt_cursor.rs
+++ b/crates/ra_macros/src/tt_cursor.rs
@@ -1,5 +1,6 @@
 use crate::tt;
 
+#[derive(Clone)]
 pub(crate) struct TtCursor<'a> {
     subtree: &'a tt::Subtree,
     pos: usize,