6 files changed, 196 insertions, 107 deletions

diff --git a/crates/mbe/src/lib.rs b/crates/mbe/src/lib.rs
index 3ad609a00..b3472879d 100644
--- a/crates/mbe/src/lib.rs
+++ b/crates/mbe/src/lib.rs
@@ -14,10 +14,10 @@ mod tests;
 
 use std::fmt;
 
-pub use tt::{Delimiter, Punct};
+pub use tt::{Delimiter, DelimiterKind, Punct};
 
 use crate::{
-    parser::{parse_pattern, Op},
+    parser::{parse_pattern, parse_template, Op},
     tt_iter::TtIter,
 };
 
@@ -78,8 +78,24 @@ pub struct MacroRules {
 
 #[derive(Clone, Debug, PartialEq, Eq)]
 struct Rule {
-    lhs: tt::Subtree,
-    rhs: tt::Subtree,
+    lhs: MetaTemplate,
+    rhs: MetaTemplate,
+}
+
+#[derive(Clone, Debug, PartialEq, Eq)]
+struct MetaTemplate {
+    delimiter: Option<Delimiter>,
+    tokens: Vec<Result<Op, ExpandError>>,
+}
+
+impl<'a> MetaTemplate {
+    fn iter(&self) -> impl Iterator<Item = &Result<Op, ExpandError>> {
+        self.tokens.iter()
+    }
+
+    fn delimiter_kind(&self) -> Option<DelimiterKind> {
+        self.delimiter.map(|it| it.kind)
+    }
 }
 
 #[derive(Clone, Copy, Debug, PartialEq, Eq)]
@@ -167,7 +183,7 @@ impl MacroRules {
             rules.push(rule);
             if let Err(()) = src.expect_char(';') {
                 if src.len() > 0 {
-                    return Err(ParseError::Expected("expected `:`".to_string()));
+                    return Err(ParseError::Expected("expected `;`".to_string()));
                 }
                 break;
             }
@@ -201,23 +217,23 @@ impl MacroRules {
 
 impl Rule {
     fn parse(src: &mut TtIter) -> Result<Rule, ParseError> {
-        let mut lhs = src
+        let lhs = src
             .expect_subtree()
-            .map_err(|()| ParseError::Expected("expected subtree".to_string()))?
-            .clone();
-        lhs.delimiter = None;
+            .map_err(|()| ParseError::Expected("expected subtree".to_string()))?;
         src.expect_char('=').map_err(|()| ParseError::Expected("expected `=`".to_string()))?;
         src.expect_char('>').map_err(|()| ParseError::Expected("expected `>`".to_string()))?;
-        let mut rhs = src
+        let rhs = src
             .expect_subtree()
-            .map_err(|()| ParseError::Expected("expected subtree".to_string()))?
-            .clone();
-        rhs.delimiter = None;
+            .map_err(|()| ParseError::Expected("expected subtree".to_string()))?;
+
+        let lhs = MetaTemplate { tokens: parse_pattern(&lhs), delimiter: None };
+        let rhs = MetaTemplate { tokens: parse_template(&rhs), delimiter: None };
+
         Ok(crate::Rule { lhs, rhs })
     }
 }
 
-fn to_parse_error(e: ExpandError) -> ParseError {
+fn to_parse_error(e: &ExpandError) -> ParseError {
     let msg = match e {
         ExpandError::InvalidRepeat => "invalid repeat".to_string(),
         _ => "invalid macro definition".to_string(),
@@ -225,22 +241,22 @@ fn to_parse_error(e: ExpandError) -> ParseError {
     ParseError::Expected(msg)
 }
 
-fn validate(pattern: &tt::Subtree) -> Result<(), ParseError> {
-    for op in parse_pattern(pattern) {
-        let op = op.map_err(to_parse_error)?;
+fn validate(pattern: &MetaTemplate) -> Result<(), ParseError> {
+    for op in pattern.iter() {
+        let op = op.as_ref().map_err(|e| to_parse_error(&e))?;
 
         match op {
-            Op::TokenTree(tt::TokenTree::Subtree(subtree)) => validate(subtree)?,
+            Op::Subtree(subtree) => validate(&subtree)?,
             Op::Repeat { 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
 
                 if separator.is_none() {
-                    if parse_pattern(subtree).all(|child_op| {
-                        match child_op.map_err(to_parse_error) {
+                    if subtree.iter().all(|child_op| {
+                        match child_op.as_ref().map_err(to_parse_error) {
                             Ok(Op::Var { kind, .. }) => {
                                 // vis is optional
-                                if kind.map_or(false, |it| it == "vis") {
+                                if kind.as_ref().map_or(false, |it| it == "vis") {
                                     return true;
                                 }
                             }
diff --git a/crates/mbe/src/mbe_expander/matcher.rs b/crates/mbe/src/mbe_expander/matcher.rs
index 7aeef7be5..ab5f87c48 100644
--- a/crates/mbe/src/mbe_expander/matcher.rs
+++ b/crates/mbe/src/mbe_expander/matcher.rs
@@ -2,10 +2,10 @@
 
 use crate::{
     mbe_expander::{Binding, Bindings, Fragment},
-    parser::{parse_pattern, Op, RepeatKind, Separator},
+    parser::{Op, RepeatKind, Separator},
     subtree_source::SubtreeTokenSource,
     tt_iter::TtIter,
-    ExpandError,
+    ExpandError, MetaTemplate,
 };
 
 use super::ExpandResult;
@@ -83,7 +83,7 @@ impl Match {
 // sense to try using it. Matching errors are added to the `Match`. It might
 // make sense to make pattern parsing a separate step?
 
-pub(super) fn match_(pattern: &tt::Subtree, src: &tt::Subtree) -> Result<Match, ExpandError> {
+pub(super) fn match_(pattern: &MetaTemplate, src: &tt::Subtree) -> Result<Match, ExpandError> {
     assert!(pattern.delimiter == None);
 
     let mut res = Match::default();
@@ -101,12 +101,12 @@ pub(super) fn match_(pattern: &tt::Subtree, src: &tt::Subtree) -> Result<Match,
 
 fn match_subtree(
     res: &mut Match,
-    pattern: &tt::Subtree,
+    pattern: &MetaTemplate,
     src: &mut TtIter,
 ) -> Result<(), ExpandError> {
-    for op in parse_pattern(pattern) {
-        match op? {
-            Op::TokenTree(tt::TokenTree::Leaf(lhs)) => {
+    for op in pattern.iter() {
+        match op.as_ref().map_err(|err| err.clone())? {
+            Op::Leaf(lhs) => {
                 let rhs = match src.expect_leaf() {
                     Ok(l) => l,
                     Err(()) => {
@@ -132,7 +132,7 @@ fn match_subtree(
                     }
                 }
             }
-            Op::TokenTree(tt::TokenTree::Subtree(lhs)) => {
+            Op::Subtree(lhs) => {
                 let rhs = match src.expect_subtree() {
                     Ok(s) => s,
                     Err(()) => {
@@ -172,7 +172,7 @@ fn match_subtree(
                 }
             }
             Op::Repeat { subtree, kind, separator } => {
-                match_repeat(res, subtree, kind, separator, src)?;
+                match_repeat(res, subtree, *kind, separator, src)?;
             }
         }
     }
@@ -240,26 +240,26 @@ impl<'a> TtIter<'a> {
                 let tt3 = self.next().unwrap().clone();
                 Ok(tt::Subtree { delimiter: None, token_trees: vec![tt, tt2, tt3] }.into())
             }
-            ('-', '=', None)
-            | ('-', '>', None)
-            | (':', ':', None)
-            | ('!', '=', None)
-            | ('.', '.', None)
-            | ('*', '=', None)
-            | ('/', '=', None)
-            | ('&', '&', None)
-            | ('&', '=', None)
-            | ('%', '=', None)
-            | ('^', '=', None)
-            | ('+', '=', None)
-            | ('<', '<', None)
-            | ('<', '=', None)
-            | ('=', '=', None)
-            | ('=', '>', None)
-            | ('>', '=', None)
-            | ('>', '>', None)
-            | ('|', '=', None)
-            | ('|', '|', None) => {
+            ('-', '=', _)
+            | ('-', '>', _)
+            | (':', ':', _)
+            | ('!', '=', _)
+            | ('.', '.', _)
+            | ('*', '=', _)
+            | ('/', '=', _)
+            | ('&', '&', _)
+            | ('&', '=', _)
+            | ('%', '=', _)
+            | ('^', '=', _)
+            | ('+', '=', _)
+            | ('<', '<', _)
+            | ('<', '=', _)
+            | ('=', '=', _)
+            | ('=', '>', _)
+            | ('>', '=', _)
+            | ('>', '>', _)
+            | ('|', '=', _)
+            | ('|', '|', _) => {
                 let tt2 = self.next().unwrap().clone();
                 Ok(tt::Subtree { delimiter: None, token_trees: vec![tt, tt2] }.into())
             }
@@ -372,9 +372,9 @@ impl<'a> TtIter<'a> {
 
 pub(super) fn match_repeat(
     res: &mut Match,
-    pattern: &tt::Subtree,
+    pattern: &MetaTemplate,
     kind: RepeatKind,
-    separator: Option<Separator>,
+    separator: &Option<Separator>,
     src: &mut TtIter,
 ) -> Result<(), ExpandError> {
     // Dirty hack to make macro-expansion terminate.
@@ -489,12 +489,12 @@ fn match_meta_var(kind: &str, input: &mut TtIter) -> ExpandResult<Option<Fragmen
     result.map(|tt| if kind == "expr" { tt.map(Fragment::Ast) } else { tt.map(Fragment::Tokens) })
 }
 
-fn collect_vars(buf: &mut Vec<SmolStr>, pattern: &tt::Subtree) -> Result<(), ExpandError> {
-    for op in parse_pattern(pattern) {
-        match op? {
+fn collect_vars(buf: &mut Vec<SmolStr>, pattern: &MetaTemplate) -> Result<(), ExpandError> {
+    for op in pattern.iter() {
+        match op.as_ref().map_err(|e| e.clone())? {
             Op::Var { name, .. } => buf.push(name.clone()),
-            Op::TokenTree(tt::TokenTree::Leaf(_)) => (),
-            Op::TokenTree(tt::TokenTree::Subtree(subtree)) => collect_vars(buf, subtree)?,
+            Op::Leaf(_) => (),
+            Op::Subtree(subtree) => collect_vars(buf, subtree)?,
             Op::Repeat { subtree, .. } => collect_vars(buf, subtree)?,
         }
     }
diff --git a/crates/mbe/src/mbe_expander/transcriber.rs b/crates/mbe/src/mbe_expander/transcriber.rs
index 57592dc92..720531237 100644
--- a/crates/mbe/src/mbe_expander/transcriber.rs
+++ b/crates/mbe/src/mbe_expander/transcriber.rs
@@ -6,8 +6,8 @@ use syntax::SmolStr;
 use super::ExpandResult;
 use crate::{
     mbe_expander::{Binding, Bindings, Fragment},
-    parser::{parse_template, Op, RepeatKind, Separator},
-    ExpandError,
+    parser::{Op, RepeatKind, Separator},
+    ExpandError, MetaTemplate,
 };
 
 impl Bindings {
@@ -50,7 +50,10 @@ impl Bindings {
     }
 }
 
-pub(super) fn transcribe(template: &tt::Subtree, bindings: &Bindings) -> ExpandResult<tt::Subtree> {
+pub(super) fn transcribe(
+    template: &MetaTemplate,
+    bindings: &Bindings,
+) -> ExpandResult<tt::Subtree> {
     assert!(template.delimiter == None);
     let mut ctx = ExpandCtx { bindings: &bindings, nesting: Vec::new() };
     let mut arena: Vec<tt::TokenTree> = Vec::new();
@@ -76,35 +79,35 @@ struct ExpandCtx<'a> {
 
 fn expand_subtree(
     ctx: &mut ExpandCtx,
-    template: &tt::Subtree,
+    template: &MetaTemplate,
     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 parse_template(template) {
+    for op in template.iter() {
         let op = match op {
             Ok(op) => op,
             Err(e) => {
-                err = Some(e);
+                err = Some(e.clone());
                 break;
             }
         };
         match op {
-            Op::TokenTree(tt @ tt::TokenTree::Leaf(..)) => arena.push(tt.clone()),
-            Op::TokenTree(tt::TokenTree::Subtree(tt)) => {
-                let ExpandResult { value: tt, err: e } = expand_subtree(ctx, tt, arena);
+            Op::Leaf(tt) => arena.push(tt.clone().into()),
+            Op::Subtree(tt) => {
+                let ExpandResult { value: tt, err: e } = expand_subtree(ctx, &tt, arena);
                 err = err.or(e);
                 arena.push(tt.into());
             }
             Op::Var { name, .. } => {
-                let ExpandResult { value: fragment, err: e } = expand_var(ctx, name);
+                let ExpandResult { value: fragment, err: e } = expand_var(ctx, &name);
                 err = err.or(e);
                 push_fragment(arena, fragment);
             }
             Op::Repeat { subtree, kind, separator } => {
                 let ExpandResult { value: fragment, err: e } =
-                    expand_repeat(ctx, subtree, kind, separator, arena);
+                    expand_repeat(ctx, subtree, *kind, separator, arena);
                 err = err.or(e);
                 push_fragment(arena, fragment)
             }
@@ -161,9 +164,9 @@ fn expand_var(ctx: &mut ExpandCtx, v: &SmolStr) -> ExpandResult<Fragment> {
 
 fn expand_repeat(
     ctx: &mut ExpandCtx,
-    template: &tt::Subtree,
+    template: &MetaTemplate,
     kind: RepeatKind,
-    separator: Option<Separator>,
+    separator: &Option<Separator>,
     arena: &mut Vec<tt::TokenTree>,
 ) -> ExpandResult<Fragment> {
     let mut buf: Vec<tt::TokenTree> = Vec::new();
diff --git a/crates/mbe/src/parser.rs b/crates/mbe/src/parser.rs
index c3fdd4040..2f3ebc831 100644
--- a/crates/mbe/src/parser.rs
+++ b/crates/mbe/src/parser.rs
@@ -4,16 +4,17 @@
 use smallvec::SmallVec;
 use syntax::SmolStr;
 
-use crate::{tt_iter::TtIter, ExpandError};
+use crate::{tt_iter::TtIter, ExpandError, MetaTemplate};
 
-#[derive(Debug)]
-pub(crate) enum Op<'a> {
-    Var { name: &'a SmolStr, kind: Option<&'a SmolStr> },
-    Repeat { subtree: &'a tt::Subtree, kind: RepeatKind, separator: Option<Separator> },
-    TokenTree(&'a tt::TokenTree),
+#[derive(Clone, Debug, PartialEq, Eq)]
+pub(crate) enum Op {
+    Var { name: SmolStr, kind: Option<SmolStr> },
+    Repeat { subtree: MetaTemplate, kind: RepeatKind, separator: Option<Separator> },
+    Leaf(tt::Leaf),
+    Subtree(MetaTemplate),
 }
 
-#[derive(Clone, Debug, PartialEq, Eq)]
+#[derive(Copy, Clone, Debug, PartialEq, Eq)]
 pub(crate) enum RepeatKind {
     ZeroOrMore,
     OneOrMore,
@@ -45,16 +46,12 @@ impl PartialEq for Separator {
     }
 }
 
-pub(crate) fn parse_template(
-    template: &tt::Subtree,
-) -> impl Iterator<Item = Result<Op<'_>, ExpandError>> {
-    parse_inner(template, Mode::Template)
+pub(crate) fn parse_template(template: &tt::Subtree) -> Vec<Result<Op, ExpandError>> {
+    parse_inner(&template, Mode::Template)
 }
 
-pub(crate) fn parse_pattern(
-    pattern: &tt::Subtree,
-) -> impl Iterator<Item = Result<Op<'_>, ExpandError>> {
-    parse_inner(pattern, Mode::Pattern)
+pub(crate) fn parse_pattern(pattern: &tt::Subtree) -> Vec<Result<Op, ExpandError>> {
+    parse_inner(&pattern, Mode::Pattern)
 }
 
 #[derive(Clone, Copy)]
@@ -63,12 +60,13 @@ enum Mode {
     Template,
 }
 
-fn parse_inner(src: &tt::Subtree, mode: Mode) -> impl Iterator<Item = Result<Op<'_>, ExpandError>> {
-    let mut src = TtIter::new(src);
+fn parse_inner(tt: &tt::Subtree, mode: Mode) -> Vec<Result<Op, ExpandError>> {
+    let mut src = TtIter::new(&tt);
     std::iter::from_fn(move || {
         let first = src.next()?;
         Some(next_op(first, &mut src, mode))
     })
+    .collect()
 }
 
 macro_rules! err {
@@ -83,35 +81,41 @@ macro_rules! bail {
     };
 }
 
-fn next_op<'a>(
-    first: &'a tt::TokenTree,
-    src: &mut TtIter<'a>,
-    mode: Mode,
-) -> Result<Op<'a>, ExpandError> {
+fn next_op<'a>(first: &tt::TokenTree, src: &mut TtIter<'a>, mode: Mode) -> Result<Op, ExpandError> {
     let res = match first {
-        tt::TokenTree::Leaf(tt::Leaf::Punct(tt::Punct { char: '$', .. })) => {
+        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::TokenTree(first)),
+                None => return Ok(Op::Leaf(leaf.clone())),
                 Some(it) => it,
             };
             match second {
                 tt::TokenTree::Subtree(subtree) => {
                     let (separator, kind) = parse_repeat(src)?;
+                    let delimiter = subtree.delimiter;
+                    let tokens = parse_inner(&subtree, mode);
+                    let subtree = MetaTemplate { tokens, delimiter };
                     Op::Repeat { subtree, separator, kind }
                 }
                 tt::TokenTree::Leaf(leaf) => match leaf {
-                    tt::Leaf::Punct(_) => {
-                        return Err(ExpandError::UnexpectedToken);
+                    tt::Leaf::Punct(punct) => {
+                        static UNDERSCORE: SmolStr = SmolStr::new_inline("_");
+
+                        if punct.char != '_' {
+                            return Err(ExpandError::UnexpectedToken);
+                        }
+                        let name = UNDERSCORE.clone();
+                        let kind = eat_fragment_kind(src, mode)?;
+                        Op::Var { name, kind }
                     }
                     tt::Leaf::Ident(ident) => {
-                        let name = &ident.text;
+                        let name = ident.text.clone();
                         let kind = eat_fragment_kind(src, mode)?;
                         Op::Var { name, kind }
                     }
                     tt::Leaf::Literal(lit) => {
-                        if is_boolean_literal(lit) {
-                            let name = &lit.text;
+                        if is_boolean_literal(&lit) {
+                            let name = lit.text.clone();
                             let kind = eat_fragment_kind(src, mode)?;
                             Op::Var { name, kind }
                         } else {
@@ -121,19 +125,22 @@ fn next_op<'a>(
                 },
             }
         }
-        tt => Op::TokenTree(tt),
+        tt::TokenTree::Leaf(tt) => Op::Leaf(tt.clone()),
+        tt::TokenTree::Subtree(subtree) => {
+            let delimiter = subtree.delimiter;
+            let tokens = parse_inner(&subtree, mode);
+            let subtree = MetaTemplate { tokens, delimiter };
+            Op::Subtree(subtree)
+        }
     };
     Ok(res)
 }
 
-fn eat_fragment_kind<'a>(
-    src: &mut TtIter<'a>,
-    mode: Mode,
-) -> Result<Option<&'a SmolStr>, ExpandError> {
+fn eat_fragment_kind<'a>(src: &mut TtIter<'a>, mode: Mode) -> Result<Option<SmolStr>, ExpandError> {
     if let Mode::Pattern = mode {
         src.expect_char(':').map_err(|()| err!("bad fragment specifier 1"))?;
         let ident = src.expect_ident().map_err(|()| err!("bad fragment specifier 1"))?;
-        return Ok(Some(&ident.text));
+        return Ok(Some(ident.text.clone()));
     };
     Ok(None)
 }
diff --git a/crates/mbe/src/syntax_bridge.rs b/crates/mbe/src/syntax_bridge.rs
index 2bec7fd49..265c0d63d 100644
--- a/crates/mbe/src/syntax_bridge.rs
+++ b/crates/mbe/src/syntax_bridge.rs
@@ -313,7 +313,7 @@ trait TokenConvertor {
             return;
         }
 
-        result.push(if k.is_punct() && k != UNDERSCORE {
+        result.push(if k.is_punct() {
             assert_eq!(range.len(), TextSize::of('.'));
             let delim = match k {
                 T!['('] => Some((tt::DelimiterKind::Parenthesis, T![')'])),
@@ -378,7 +378,6 @@ trait TokenConvertor {
             let leaf: tt::Leaf = match k {
                 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 => {
diff --git a/crates/mbe/src/tests.rs b/crates/mbe/src/tests.rs
index 451fa1456..1d9afb4fb 100644
--- a/crates/mbe/src/tests.rs
+++ b/crates/mbe/src/tests.rs
@@ -761,6 +761,18 @@ fn test_last_expr() {
 }
 
 #[test]
+fn test_expr_with_attr() {
+    parse_macro(
+        r#"
+macro_rules! m {
+    ($a:expr) => {0}
+}
+"#,
+    )
+    .assert_expand_items("m!(#[allow(a)]())", "0");
+}
+
+#[test]
 fn test_ty() {
     parse_macro(
         r#"
@@ -992,6 +1004,22 @@ fn test_tt_composite2() {
 }
 
 #[test]
+fn test_tt_with_composite_without_space() {
+    parse_macro(
+        r#"
+        macro_rules! foo {
+            ($ op:tt, $j:path) => (
+                0
+            )
+        }
+"#,
+    )
+    // Test macro input without any spaces
+    // See https://github.com/rust-analyzer/rust-analyzer/issues/6692
+    .assert_expand_items("foo!(==,Foo::Bool)", "0");
+}
+
+#[test]
 fn test_underscore() {
     parse_macro(
         r#"
@@ -1004,6 +1032,42 @@ fn test_underscore() {
 }
 
 #[test]
+fn test_underscore_not_greedily() {
+    parse_macro(
+        r#"
+macro_rules! q {
+    ($($a:ident)* _) => {0};
+}
+"#,
+    )
+    // `_` overlaps with `$a:ident` but rustc matches it under the `_` token
+    .assert_expand_items(r#"q![a b c d _]"#, r#"0"#);
+
+    parse_macro(
+        r#"
+macro_rules! q {
+    ($($a:expr => $b:ident)* _ => $c:expr) => {0};
+}
+"#,
+    )
+    // `_ => ou` overlaps with `$a:expr => $b:ident` but rustc matches it under `_ => $c:expr`
+    .assert_expand_items(r#"q![a => b c => d _ => ou]"#, r#"0"#);
+}
+
+#[test]
+fn test_underscore_as_type() {
+    parse_macro(
+        r#"
+macro_rules! q {
+    ($a:ty) => {0};
+}
+"#,
+    )
+    // Underscore is a type
+    .assert_expand_items(r#"q![_]"#, r#"0"#);
+}
+
+#[test]
 fn test_vertical_bar_with_pat() {
     parse_macro(
         r#"