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.

4 files changed, 317 insertions, 6 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());
diff --git a/src/test/compile-fail/fail-simple.rs b/src/test/compile-fail/fail-simple.rs
index e889d354770..a20ff864705 100644
--- a/src/test/compile-fail/fail-simple.rs
+++ b/src/test/compile-fail/fail-simple.rs
@@ -9,5 +9,5 @@
 // except according to those terms.
 
 fn main() {
-    panic!(@); //~ ERROR expected expression, found `@`
+    panic!(@); //~ ERROR no rules expected the token `@`
 }
diff --git a/src/test/compile-fail/vec-macro-with-comma-only.rs b/src/test/compile-fail/vec-macro-with-comma-only.rs
index 96f58666fdf..c79e67a3768 100644
--- a/src/test/compile-fail/vec-macro-with-comma-only.rs
+++ b/src/test/compile-fail/vec-macro-with-comma-only.rs
@@ -9,5 +9,5 @@
 // except according to those terms.
 
 pub fn main() {
-    vec![,]; //~ ERROR expected expression, found `,`
+    vec![,]; //~ ERROR no rules expected the token `,`
 }
diff --git a/src/test/run-pass/macro-first-set.rs b/src/test/run-pass/macro-first-set.rs
new file mode 100644
index 00000000000..99e5d22fb47
--- /dev/null
+++ b/src/test/run-pass/macro-first-set.rs
@@ -0,0 +1,245 @@
+// Copyright 2017 The Rust Project Developers. See the COPYRIGHT
+// file at the top-level directory of this distribution and at
+// http://rust-lang.org/COPYRIGHT.
+//
+// Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or
+// http://www.apache.org/licenses/LICENSE-2.0> or the MIT license
+// <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your
+// option. This file may not be copied, modified, or distributed
+// except according to those terms.
+
+#![feature(macro_vis_matcher)]
+
+//{{{ issue 40569 ==============================================================
+
+macro_rules! my_struct {
+    ($(#[$meta:meta])* $ident:ident) => {
+        $(#[$meta])* struct $ident;
+    }
+}
+
+my_struct!(#[derive(Debug, PartialEq)] Foo40569);
+
+fn test_40569() {
+    assert_eq!(Foo40569, Foo40569);
+}
+
+//}}}
+
+//{{{ issue 26444 ==============================================================
+
+macro_rules! foo_26444 {
+    ($($beginning:ident),*; $middle:ident; $($end:ident),*) => {
+        stringify!($($beginning,)* $middle $(,$end)*)
+    }
+}
+
+fn test_26444() {
+    assert_eq!("a , b , c , d , e", foo_26444!(a, b; c; d, e));
+    assert_eq!("f", foo_26444!(; f ;));
+}
+
+macro_rules! pat_26444 {
+    ($fname:ident $($arg:pat)* =) => {}
+}
+
+pat_26444!(foo 1 2 5...7 =);
+pat_26444!(bar Some(ref x) Ok(ref mut y) &(w, z) =);
+
+//}}}
+
+//{{{ issue 40984 ==============================================================
+
+macro_rules! thread_local_40984 {
+    () => {};
+    ($(#[$attr:meta])* $vis:vis static $name:ident: $t:ty = $init:expr; $($rest:tt)*) => {
+        thread_local_40984!($($rest)*);
+    };
+    ($(#[$attr:meta])* $vis:vis static $name:ident: $t:ty = $init:expr) => {};
+}
+
+thread_local_40984! {
+    // no docs
+    #[allow(unused)]
+    static FOO: i32 = 42;
+    /// docs
+    pub static BAR: String = String::from("bar");
+
+    // look at these restrictions!!
+    pub(crate) static BAZ: usize = 0;
+    pub(in foo) static QUUX: usize = 0;
+}
+
+//}}}
+
+//{{{ issue 35650 ==============================================================
+
+macro_rules! size {
+    ($ty:ty) => {
+        std::mem::size_of::<$ty>()
+    };
+    ($size:tt) => {
+        $size
+    };
+}
+
+fn test_35650() {
+    assert_eq!(size!(u64), 8);
+    assert_eq!(size!(5), 5);
+}
+
+//}}}
+
+//{{{ issue 27832 ==============================================================
+
+macro_rules! m {
+    ( $i:ident ) => ();
+    ( $t:tt $j:tt ) => ();
+}
+
+m!(c);
+m!(t 9);
+m!(0 9);
+m!(struct);
+m!(struct Foo);
+
+macro_rules! m2 {
+    ( $b:expr ) => ();
+    ( $t:tt $u:tt ) => ();
+}
+
+m2!(3);
+m2!(1 2);
+m2!(_ 1);
+m2!(enum Foo);
+
+//}}}
+
+//{{{ issue 39964 ==============================================================
+
+macro_rules! foo_39964 {
+    ($a:ident) => {};
+    (_) => {};
+}
+
+foo_39964!(_);
+
+//}}}
+
+//{{{ issue 34030 ==============================================================
+
+macro_rules! foo_34030 {
+    ($($t:ident),* /) => {};
+}
+
+foo_34030!(a, b/);
+foo_34030!(a/);
+foo_34030!(/);
+
+//}}}
+
+//{{{ issue 24189 ==============================================================
+
+macro_rules! foo_24189 {
+    (
+        pub enum $name:ident {
+            $( #[$attr:meta] )* $var:ident
+        }
+    ) => {
+        pub enum $name {
+            $( #[$attr] )* $var
+        }
+    };
+}
+
+foo_24189! {
+    pub enum Foo24189 {
+        #[doc = "Bar"] Baz
+    }
+}
+
+macro_rules! serializable {
+    (
+        $(#[$struct_meta:meta])*
+        pub struct $name:ident {
+            $(
+                $(#[$field_meta:meta])*
+                $field:ident: $type_:ty
+            ),* ,
+        }
+    ) => {
+        $(#[$struct_meta])*
+        pub struct $name {
+            $(
+                $(#[$field_meta])*
+                $field: $type_
+            ),* ,
+        }
+    }
+}
+
+serializable! {
+    #[allow(dead_code)]
+    /// This is a test
+    pub struct Tester {
+        #[allow(dead_code)]
+        name: String,
+    }
+}
+
+macro_rules! foo_24189_c {
+    ( $( > )* $x:ident ) => { };
+}
+foo_24189_c!( > a );
+
+fn test_24189() {
+    let _ = Foo24189::Baz;
+    let _ = Tester { name: "".to_owned() };
+}
+
+//}}}
+
+//{{{ some more tests ==========================================================
+
+macro_rules! test_block {
+    (< $($b:block)* >) => {}
+}
+
+test_block!(<>);
+test_block!(<{}>);
+test_block!(<{1}{2}>);
+
+macro_rules! test_ty {
+    ($($t:ty),* $(,)*) => {}
+}
+
+test_ty!();
+test_ty!(,);
+test_ty!(u8);
+test_ty!(u8,);
+
+macro_rules! test_path {
+    ($($t:path),* $(,)*) => {}
+}
+
+test_path!();
+test_path!(,);
+test_path!(::std);
+test_path!(std::u8,);
+test_path!(any, super, super::super::self::path, X<Y>::Z<'a, T=U>);
+
+macro_rules! test_meta_block {
+    ($($m:meta)* $b:block) => {};
+}
+
+test_meta_block!(windows {});
+
+//}}}
+
+fn main() {
+    test_26444();
+    test_40569();
+    test_35650();
+    test_24189();
+}
+