Auto merge of #42913 - kennytm:fix-40569-ident-without-backtrack, r=jseyfried

Only match a fragment specifier the if it starts with certain tokens.

When trying to match a fragment specifier, we first predict whether the current token can be matched at all. If it cannot be matched, don't bother to push the Earley item to `bb_eis`. This can fix a lot of issues which otherwise requires full backtracking (#42838).

In this PR the prediction treatment is not done for `:item`, `:stmt` and `:tt`, but it could be expanded in the future.

Fixes #24189.
Fixes #26444.
Fixes #27832.
Fixes #34030.
Fixes #35650.
Fixes #39964.
Fixes the 4th comment in #40569.
Fixes the issue blocking #40984.

1 files changed, 70 insertions, 4 deletions

diff --git a/src/libsyntax/ext/tt/macro_parser.rs b/src/libsyntax/ext/tt/macro_parser.rs
index e877f1fedd4..d18961b75c8 100644
--- a/src/libsyntax/ext/tt/macro_parser.rs
+++ b/src/libsyntax/ext/tt/macro_parser.rs
@@ -386,12 +386,11 @@ fn inner_parse_loop(sess: &ParseSess,
                         return Error(span, "missing fragment specifier".to_string());
                     }
                 }
-                TokenTree::MetaVarDecl(..) => {
+                TokenTree::MetaVarDecl(_, _, id) => {
                     // Built-in nonterminals never start with these tokens,
                     // so we can eliminate them from consideration.
-                    match *token {
-                        token::CloseDelim(_) => {},
-                        _ => bb_eis.push(ei),
+                    if may_begin_with(&*id.name.as_str(), token) {
+                        bb_eis.push(ei);
                     }
                 }
                 seq @ TokenTree::Delimited(..) | seq @ TokenTree::Token(_, DocComment(..)) => {
@@ -493,6 +492,73 @@ pub fn parse(sess: &ParseSess,
     }
 }
 
+/// Checks whether a non-terminal may begin with a particular token.
+///
+/// Returning `false` is a *stability guarantee* that such a matcher will *never* begin with that
+/// token. Be conservative (return true) if not sure.
+fn may_begin_with(name: &str, token: &Token) -> bool {
+    /// Checks whether the non-terminal may contain a single (non-keyword) identifier.
+    fn may_be_ident(nt: &token::Nonterminal) -> bool {
+        match *nt {
+            token::NtItem(_) | token::NtBlock(_) | token::NtVis(_) => false,
+            _ => true,
+        }
+    }
+
+    match name {
+        "expr" => token.can_begin_expr(),
+        "ty" => token.can_begin_type(),
+        "ident" => token.is_ident(),
+        "vis" => match *token { // The follow-set of :vis + "priv" keyword + interpolated
+            Token::Comma | Token::Ident(_) | Token::Interpolated(_) => true,
+            _ => token.can_begin_type(),
+        },
+        "block" => match *token {
+            Token::OpenDelim(token::Brace) => true,
+            Token::Interpolated(ref nt) => match nt.0 {
+                token::NtItem(_) |
+                token::NtPat(_) |
+                token::NtTy(_) |
+                token::NtIdent(_) |
+                token::NtMeta(_) |
+                token::NtPath(_) |
+                token::NtVis(_) => false, // none of these may start with '{'.
+                _ => true,
+            },
+            _ => false,
+        },
+        "path" | "meta" => match *token {
+            Token::ModSep | Token::Ident(_) => true,
+            Token::Interpolated(ref nt) => match nt.0 {
+                token::NtPath(_) | token::NtMeta(_) => true,
+                _ => may_be_ident(&nt.0),
+            },
+            _ => false,
+        },
+        "pat" => match *token {
+            Token::Ident(_) |               // box, ref, mut, and other identifiers (can stricten)
+            Token::OpenDelim(token::Paren) |    // tuple pattern
+            Token::OpenDelim(token::Bracket) |  // slice pattern
+            Token::BinOp(token::And) |          // reference
+            Token::BinOp(token::Minus) |        // negative literal
+            Token::AndAnd |                     // double reference
+            Token::Literal(..) |                // literal
+            Token::DotDot |                     // range pattern (future compat)
+            Token::DotDotDot |                  // range pattern (future compat)
+            Token::ModSep |                     // path
+            Token::Lt |                         // path (UFCS constant)
+            Token::BinOp(token::Shl) |          // path (double UFCS)
+            Token::Underscore => true,          // placeholder
+            Token::Interpolated(ref nt) => may_be_ident(&nt.0),
+            _ => false,
+        },
+        _ => match *token {
+            token::CloseDelim(_) => false,
+            _ => true,
+        },
+    }
+}
+
 fn parse_nt<'a>(p: &mut Parser<'a>, sp: Span, name: &str) -> Nonterminal {
     if name == "tt" {
         return token::NtTT(p.parse_token_tree());