Rollup merge of #39118 - jseyfried:token_tree_based_parser, r=nrc

Refactor the parser to consume token trees

This is groundwork for efficiently parsing attribute proc macro invocations, bang macro invocations, and `TokenStream`-based attributes and fragment matchers.

This improves parsing performance by 8-15% and expansion performance by 0-5% on a sampling of the compiler's crates.

r? @nrc

5 files changed, 49 insertions, 100 deletions

diff --git a/src/libsyntax/ext/base.rs b/src/libsyntax/ext/base.rs
index 68d261c64f8..edf74e1fe19 100644
--- a/src/libsyntax/ext/base.rs
+++ b/src/libsyntax/ext/base.rs
@@ -615,9 +615,7 @@ impl<'a> ExtCtxt<'a> {
 
     pub fn new_parser_from_tts(&self, tts: &[tokenstream::TokenTree])
         -> parser::Parser<'a> {
-        let mut parser = parse::tts_to_parser(self.parse_sess, tts.to_vec());
-        parser.allow_interpolated_tts = false; // FIXME(jseyfried) `quote!` can't handle these yet
-        parser
+        parse::tts_to_parser(self.parse_sess, tts.to_vec())
     }
     pub fn codemap(&self) -> &'a CodeMap { self.parse_sess.codemap() }
     pub fn parse_sess(&self) -> &'a parse::ParseSess { self.parse_sess }
diff --git a/src/libsyntax/ext/expand.rs b/src/libsyntax/ext/expand.rs
index bc3c11b36c2..d748eec73e8 100644
--- a/src/libsyntax/ext/expand.rs
+++ b/src/libsyntax/ext/expand.rs
@@ -21,7 +21,7 @@ use ext::base::*;
 use feature_gate::{self, Features};
 use fold;
 use fold::*;
-use parse::{ParseSess, DirectoryOwnership, PResult, lexer};
+use parse::{ParseSess, DirectoryOwnership, PResult, filemap_to_tts};
 use parse::parser::Parser;
 use parse::token;
 use print::pprust;
@@ -669,12 +669,8 @@ fn tts_for_attr_args(attr: &ast::Attribute, parse_sess: &ParseSess) -> Vec<Token
 }
 
 fn string_to_tts(text: String, parse_sess: &ParseSess) -> Vec<TokenTree> {
-    let filemap = parse_sess.codemap()
-                            .new_filemap(String::from("<macro expansion>"), None, text);
-
-    let lexer = lexer::StringReader::new(&parse_sess.span_diagnostic, filemap);
-    let mut parser = Parser::new(parse_sess, Box::new(lexer), None, false);
-    panictry!(parser.parse_all_token_trees())
+    let filename = String::from("<macro expansion>");
+    filemap_to_tts(parse_sess, parse_sess.codemap().new_filemap(filename, None, text))
 }
 
 impl<'a, 'b> Folder for InvocationCollector<'a, 'b> {
diff --git a/src/libsyntax/ext/tt/macro_parser.rs b/src/libsyntax/ext/tt/macro_parser.rs
index 87c8f3efb63..089c35c694a 100644
--- a/src/libsyntax/ext/tt/macro_parser.rs
+++ b/src/libsyntax/ext/tt/macro_parser.rs
@@ -82,7 +82,6 @@ use ast::Ident;
 use syntax_pos::{self, BytePos, mk_sp, Span};
 use codemap::Spanned;
 use errors::FatalError;
-use parse::lexer::*; //resolve bug?
 use parse::{Directory, ParseSess};
 use parse::parser::{PathStyle, Parser};
 use parse::token::{DocComment, MatchNt, SubstNt};
@@ -407,9 +406,9 @@ fn inner_parse_loop(cur_eis: &mut SmallVector<Box<MatcherPos>>,
     Success(())
 }
 
-pub fn parse(sess: &ParseSess, rdr: TtReader, ms: &[TokenTree], directory: Option<Directory>)
+pub fn parse(sess: &ParseSess, tts: Vec<TokenTree>, ms: &[TokenTree], directory: Option<Directory>)
              -> NamedParseResult {
-    let mut parser = Parser::new(sess, Box::new(rdr), directory, true);
+    let mut parser = Parser::new(sess, tts, directory, true);
     let mut cur_eis = SmallVector::one(initial_matcher_pos(ms.to_owned(), parser.span.lo));
     let mut next_eis = Vec::new(); // or proceed normally
 
@@ -481,23 +480,8 @@ fn parse_nt<'a>(p: &mut Parser<'a>, sp: Span, name: &str) -> Nonterminal {
     match name {
         "tt" => {
             p.quote_depth += 1; //but in theory, non-quoted tts might be useful
-            let mut tt = panictry!(p.parse_token_tree());
+            let tt = panictry!(p.parse_token_tree());
             p.quote_depth -= 1;
-            while let TokenTree::Token(sp, token::Interpolated(nt)) = tt {
-                if let token::NtTT(..) = *nt {
-                    match Rc::try_unwrap(nt) {
-                        Ok(token::NtTT(sub_tt)) => tt = sub_tt,
-                        Ok(_) => unreachable!(),
-                        Err(nt_rc) => match *nt_rc {
-                            token::NtTT(ref sub_tt) => tt = sub_tt.clone(),
-                            _ => unreachable!(),
-                        },
-                    }
-                } else {
-                    tt = TokenTree::Token(sp, token::Interpolated(nt.clone()));
-                    break
-                }
-            }
             return token::NtTT(tt);
         }
         _ => {}
@@ -527,7 +511,7 @@ fn parse_nt<'a>(p: &mut Parser<'a>, sp: Span, name: &str) -> Nonterminal {
         "ident" => match p.token {
             token::Ident(sn) => {
                 p.bump();
-                token::NtIdent(Spanned::<Ident>{node: sn, span: p.span})
+                token::NtIdent(Spanned::<Ident>{node: sn, span: p.prev_span})
             }
             _ => {
                 let token_str = pprust::token_to_string(&p.token);
diff --git a/src/libsyntax/ext/tt/macro_rules.rs b/src/libsyntax/ext/tt/macro_rules.rs
index 3abd24b50ba..f6a25d4acee 100644
--- a/src/libsyntax/ext/tt/macro_rules.rs
+++ b/src/libsyntax/ext/tt/macro_rules.rs
@@ -16,8 +16,8 @@ use ext::expand::{Expansion, ExpansionKind};
 use ext::tt::macro_parser::{Success, Error, Failure};
 use ext::tt::macro_parser::{MatchedSeq, MatchedNonterminal};
 use ext::tt::macro_parser::{parse, parse_failure_msg};
+use ext::tt::transcribe::transcribe;
 use parse::{Directory, ParseSess};
-use parse::lexer::new_tt_reader;
 use parse::parser::Parser;
 use parse::token::{self, NtTT, Token};
 use parse::token::Token::*;
@@ -113,13 +113,12 @@ fn generic_extension<'cx>(cx: &'cx ExtCtxt,
                     _ => cx.span_bug(sp, "malformed macro rhs"),
                 };
                 // rhs has holes ( `$id` and `$(...)` that need filled)
-                let trncbr =
-                    new_tt_reader(&cx.parse_sess.span_diagnostic, Some(named_matches), rhs);
+                let tts = transcribe(&cx.parse_sess.span_diagnostic, Some(named_matches), rhs);
                 let directory = Directory {
                     path: cx.current_expansion.module.directory.clone(),
                     ownership: cx.current_expansion.directory_ownership,
                 };
-                let mut p = Parser::new(cx.parse_sess(), Box::new(trncbr), Some(directory), false);
+                let mut p = Parser::new(cx.parse_sess(), tts, Some(directory), false);
                 p.root_module_name = cx.current_expansion.module.mod_path.last()
                     .map(|id| (*id.name.as_str()).to_owned());
 
@@ -187,10 +186,8 @@ pub fn compile(sess: &ParseSess, def: &ast::MacroDef) -> SyntaxExtension {
         })),
     ];
 
-    // Parse the macro_rules! invocation (`none` is for no interpolations):
-    let arg_reader = new_tt_reader(&sess.span_diagnostic, None, def.body.clone());
-
-    let argument_map = match parse(sess, arg_reader, &argument_gram, None) {
+    // Parse the macro_rules! invocation
+    let argument_map = match parse(sess, def.body.clone(), &argument_gram, None) {
         Success(m) => m,
         Failure(sp, tok) => {
             let s = parse_failure_msg(tok);
diff --git a/src/libsyntax/ext/tt/transcribe.rs b/src/libsyntax/ext/tt/transcribe.rs
index 37e329e5d3b..38becbe7b1d 100644
--- a/src/libsyntax/ext/tt/transcribe.rs
+++ b/src/libsyntax/ext/tt/transcribe.rs
@@ -10,10 +10,9 @@
 use self::LockstepIterSize::*;
 
 use ast::Ident;
-use errors::{Handler, DiagnosticBuilder};
+use errors::Handler;
 use ext::tt::macro_parser::{NamedMatch, MatchedSeq, MatchedNonterminal};
-use parse::token::{self, MatchNt, SubstNt, Token, NtIdent};
-use parse::lexer::TokenAndSpan;
+use parse::token::{self, MatchNt, SubstNt, Token, NtIdent, NtTT};
 use syntax_pos::{Span, DUMMY_SP};
 use tokenstream::{self, TokenTree};
 use util::small_vector::SmallVector;
@@ -32,8 +31,8 @@ struct TtFrame {
 }
 
 #[derive(Clone)]
-pub struct TtReader<'a> {
-    pub sp_diag: &'a Handler,
+struct TtReader<'a> {
+    sp_diag: &'a Handler,
     /// the unzipped tree:
     stack: SmallVector<TtFrame>,
     /* for MBE-style macro transcription */
@@ -41,20 +40,15 @@ pub struct TtReader<'a> {
 
     repeat_idx: Vec<usize>,
     repeat_len: Vec<usize>,
-    /* cached: */
-    pub cur_tok: Token,
-    pub cur_span: Span,
-    /// Transform doc comments. Only useful in macro invocations
-    pub fatal_errs: Vec<DiagnosticBuilder<'a>>,
 }
 
 /// This can do Macro-By-Example transcription. On the other hand, if
 /// `src` contains no `TokenTree::Sequence`s, `MatchNt`s or `SubstNt`s, `interp` can
 /// (and should) be None.
-pub fn new_tt_reader(sp_diag: &Handler,
-                     interp: Option<HashMap<Ident, Rc<NamedMatch>>>,
-                     src: Vec<tokenstream::TokenTree>)
-                     -> TtReader {
+pub fn transcribe(sp_diag: &Handler,
+                  interp: Option<HashMap<Ident, Rc<NamedMatch>>>,
+                  src: Vec<tokenstream::TokenTree>)
+                  -> Vec<TokenTree> {
     let mut r = TtReader {
         sp_diag: sp_diag,
         stack: SmallVector::one(TtFrame {
@@ -73,13 +67,15 @@ pub fn new_tt_reader(sp_diag: &Handler,
         },
         repeat_idx: Vec::new(),
         repeat_len: Vec::new(),
-        /* dummy values, never read: */
-        cur_tok: token::Eof,
-        cur_span: DUMMY_SP,
-        fatal_errs: Vec::new(),
     };
-    tt_next_token(&mut r); /* get cur_tok and cur_span set up */
-    r
+
+    let mut tts = Vec::new();
+    let mut prev_span = DUMMY_SP;
+    while let Some(tt) = tt_next_token(&mut r, prev_span) {
+        prev_span = tt.span();
+        tts.push(tt);
+    }
+    tts
 }
 
 fn lookup_cur_matched_by_matched(r: &TtReader, start: Rc<NamedMatch>) -> Rc<NamedMatch> {
@@ -153,38 +149,24 @@ fn lockstep_iter_size(t: &TokenTree, r: &TtReader) -> LockstepIterSize {
 
 /// Return the next token from the TtReader.
 /// EFFECT: advances the reader's token field
-pub fn tt_next_token(r: &mut TtReader) -> TokenAndSpan {
-    // FIXME(pcwalton): Bad copy?
-    let ret_val = TokenAndSpan {
-        tok: r.cur_tok.clone(),
-        sp: r.cur_span.clone(),
-    };
+fn tt_next_token(r: &mut TtReader, prev_span: Span) -> Option<TokenTree> {
     loop {
-        let should_pop = match r.stack.last() {
-            None => {
-                assert_eq!(ret_val.tok, token::Eof);
-                return ret_val;
-            }
-            Some(frame) => {
-                if frame.idx < frame.forest.len() {
-                    break;
-                }
-                !frame.dotdotdoted ||
-                    *r.repeat_idx.last().unwrap() == *r.repeat_len.last().unwrap() - 1
+        let should_pop = if let Some(frame) = r.stack.last() {
+            if frame.idx < frame.forest.len() {
+                break;
             }
+            !frame.dotdotdoted || *r.repeat_idx.last().unwrap() == *r.repeat_len.last().unwrap() - 1
+        } else {
+            return None;
         };
 
         /* done with this set; pop or repeat? */
         if should_pop {
             let prev = r.stack.pop().unwrap();
-            match r.stack.last_mut() {
-                None => {
-                    r.cur_tok = token::Eof;
-                    return ret_val;
-                }
-                Some(frame) => {
-                    frame.idx += 1;
-                }
+            if let Some(frame) = r.stack.last_mut() {
+                frame.idx += 1;
+            } else {
+                return None;
             }
             if prev.dotdotdoted {
                 r.repeat_idx.pop();
@@ -194,8 +176,7 @@ pub fn tt_next_token(r: &mut TtReader) -> TokenAndSpan {
             *r.repeat_idx.last_mut().unwrap() += 1;
             r.stack.last_mut().unwrap().idx = 0;
             if let Some(tk) = r.stack.last().unwrap().sep.clone() {
-                r.cur_tok = tk; // repeat same span, I guess
-                return ret_val;
+                return Some(TokenTree::Token(prev_span, tk)); // repeat same span, I guess
             }
         }
     }
@@ -231,7 +212,7 @@ pub fn tt_next_token(r: &mut TtReader) -> TokenAndSpan {
                             }
 
                             r.stack.last_mut().unwrap().idx += 1;
-                            return tt_next_token(r);
+                            return tt_next_token(r, prev_span);
                         }
                         r.repeat_len.push(len);
                         r.repeat_idx.push(0);
@@ -249,9 +230,7 @@ pub fn tt_next_token(r: &mut TtReader) -> TokenAndSpan {
                 r.stack.last_mut().unwrap().idx += 1;
                 match lookup_cur_matched(r, ident) {
                     None => {
-                        r.cur_span = sp;
-                        r.cur_tok = SubstNt(ident);
-                        return ret_val;
+                        return Some(TokenTree::Token(sp, SubstNt(ident)));
                         // this can't be 0 length, just like TokenTree::Delimited
                     }
                     Some(cur_matched) => if let MatchedNonterminal(ref nt) = *cur_matched {
@@ -260,15 +239,12 @@ pub fn tt_next_token(r: &mut TtReader) -> TokenAndSpan {
                             // (a) idents can be in lots of places, so it'd be a pain
                             // (b) we actually can, since it's a token.
                             NtIdent(ref sn) => {
-                                r.cur_span = sn.span;
-                                r.cur_tok = token::Ident(sn.node);
-                                return ret_val;
+                                return Some(TokenTree::Token(sn.span, token::Ident(sn.node)));
                             }
+                            NtTT(ref tt) => return Some(tt.clone()),
                             _ => {
-                                // FIXME(pcwalton): Bad copy.
-                                r.cur_span = sp;
-                                r.cur_tok = token::Interpolated(nt.clone());
-                                return ret_val;
+                                // FIXME(pcwalton): Bad copy
+                                return Some(TokenTree::Token(sp, token::Interpolated(nt.clone())));
                             }
                         }
                     } else {
@@ -289,11 +265,9 @@ pub fn tt_next_token(r: &mut TtReader) -> TokenAndSpan {
                 });
                 // if this could be 0-length, we'd need to potentially recur here
             }
-            TokenTree::Token(sp, tok) => {
-                r.cur_span = sp;
-                r.cur_tok = tok;
+            tt @ TokenTree::Token(..) => {
                 r.stack.last_mut().unwrap().idx += 1;
-                return ret_val;
+                return Some(tt);
             }
         }
     }