Auto merge of #42533 - Mark-Simulacrum:macro-parse-speed-small, r=jseyfried

Speed up expansion

This reduces duplication, thereby increasing expansion speed. Based on tests with rust-uinput, this produces a 29x performance win (440 seconds to 15 seconds). I want to land this first, since it's a minimal patch, but with more changes to the macro parsing I can get down to 12 seconds locally.

There is one FIXME added to the code that I'll keep for now since changing it will spread outward and increase the patch size, I think.

Fixes #37074.

r? @jseyfried
cc @oberien

3 files changed, 34 insertions, 27 deletions

diff --git a/src/libsyntax/ext/tt/macro_parser.rs b/src/libsyntax/ext/tt/macro_parser.rs
index 0b6a2eb536a..61d8fc2941a 100644
--- a/src/libsyntax/ext/tt/macro_parser.rs
+++ b/src/libsyntax/ext/tt/macro_parser.rs
@@ -139,13 +139,20 @@ struct MatcherPos {
     sep: Option<Token>,
     idx: usize,
     up: Option<Box<MatcherPos>>,
-    matches: Vec<Vec<Rc<NamedMatch>>>,
+    matches: Vec<Rc<Vec<NamedMatch>>>,
     match_lo: usize,
     match_cur: usize,
     match_hi: usize,
     sp_lo: BytePos,
 }
 
+impl MatcherPos {
+    fn push_match(&mut self, idx: usize, m: NamedMatch) {
+        let matches = Rc::make_mut(&mut self.matches[idx]);
+        matches.push(m);
+    }
+}
+
 pub type NamedParseResult = ParseResult<HashMap<Ident, Rc<NamedMatch>>>;
 
 pub fn count_names(ms: &[TokenTree]) -> usize {
@@ -199,14 +206,15 @@ fn initial_matcher_pos(ms: Vec<TokenTree>, lo: BytePos) -> Box<MatcherPos> {
 /// only on the nesting depth of `ast::TTSeq`s in the originating
 /// token tree it was derived from.
 
+#[derive(Debug, Clone)]
 pub enum NamedMatch {
-    MatchedSeq(Vec<Rc<NamedMatch>>, syntax_pos::Span),
+    MatchedSeq(Rc<Vec<NamedMatch>>, syntax_pos::Span),
     MatchedNonterminal(Rc<Nonterminal>)
 }
 
-fn nameize<I: Iterator<Item=Rc<NamedMatch>>>(sess: &ParseSess, ms: &[TokenTree], mut res: I)
+fn nameize<I: Iterator<Item=NamedMatch>>(sess: &ParseSess, ms: &[TokenTree], mut res: I)
                                              -> NamedParseResult {
-    fn n_rec<I: Iterator<Item=Rc<NamedMatch>>>(sess: &ParseSess, m: &TokenTree, mut res: &mut I,
+    fn n_rec<I: Iterator<Item=NamedMatch>>(sess: &ParseSess, m: &TokenTree, mut res: &mut I,
              ret_val: &mut HashMap<Ident, Rc<NamedMatch>>)
              -> Result<(), (syntax_pos::Span, String)> {
         match *m {
@@ -228,7 +236,8 @@ fn nameize<I: Iterator<Item=Rc<NamedMatch>>>(sess: &ParseSess, ms: &[TokenTree],
             TokenTree::MetaVarDecl(sp, bind_name, _) => {
                 match ret_val.entry(bind_name) {
                     Vacant(spot) => {
-                        spot.insert(res.next().unwrap());
+                        // FIXME(simulacrum): Don't construct Rc here
+                        spot.insert(Rc::new(res.next().unwrap()));
                     }
                     Occupied(..) => {
                         return Err((sp, format!("duplicated bind name: {}", bind_name)))
@@ -280,8 +289,8 @@ fn token_name_eq(t1 : &Token, t2 : &Token) -> bool {
     }
 }
 
-fn create_matches(len: usize) -> Vec<Vec<Rc<NamedMatch>>> {
-    (0..len).into_iter().map(|_| Vec::new()).collect()
+fn create_matches(len: usize) -> Vec<Rc<Vec<NamedMatch>>> {
+    (0..len).into_iter().map(|_| Rc::new(Vec::new())).collect()
 }
 
 fn inner_parse_loop(sess: &ParseSess,
@@ -320,15 +329,10 @@ fn inner_parse_loop(sess: &ParseSess,
                     // update matches (the MBE "parse tree") by appending
                     // each tree as a subtree.
 
-                    // I bet this is a perf problem: we're preemptively
-                    // doing a lot of array work that will get thrown away
-                    // most of the time.
-
                     // Only touch the binders we have actually bound
                     for idx in ei.match_lo..ei.match_hi {
                         let sub = ei.matches[idx].clone();
-                        new_pos.matches[idx]
-                            .push(Rc::new(MatchedSeq(sub, Span { lo: ei.sp_lo, ..span })));
+                        new_pos.push_match(idx, MatchedSeq(sub, Span { lo: ei.sp_lo, ..span }));
                     }
 
                     new_pos.match_cur = ei.match_hi;
@@ -362,7 +366,7 @@ fn inner_parse_loop(sess: &ParseSess,
                         new_ei.match_cur += seq.num_captures;
                         new_ei.idx += 1;
                         for idx in ei.match_cur..ei.match_cur + seq.num_captures {
-                            new_ei.matches[idx].push(Rc::new(MatchedSeq(vec![], sp)));
+                            new_ei.push_match(idx, MatchedSeq(Rc::new(vec![]), sp));
                         }
                         cur_eis.push(new_ei);
                     }
@@ -446,7 +450,9 @@ pub fn parse(sess: &ParseSess,
         /* error messages here could be improved with links to orig. rules */
         if token_name_eq(&parser.token, &token::Eof) {
             if eof_eis.len() == 1 {
-                let matches = eof_eis[0].matches.iter_mut().map(|mut dv| dv.pop().unwrap());
+                let matches = eof_eis[0].matches.iter_mut().map(|mut dv| {
+                    Rc::make_mut(dv).pop().unwrap()
+                });
                 return nameize(sess, ms, matches);
             } else if eof_eis.len() > 1 {
                 return Error(parser.span, "ambiguity: multiple successful parses".to_string());
@@ -479,8 +485,8 @@ pub fn parse(sess: &ParseSess,
             let mut ei = bb_eis.pop().unwrap();
             if let TokenTree::MetaVarDecl(span, _, ident) = ei.top_elts.get_tt(ei.idx) {
                 let match_cur = ei.match_cur;
-                ei.matches[match_cur].push(Rc::new(MatchedNonterminal(
-                            Rc::new(parse_nt(&mut parser, span, &ident.name.as_str())))));
+                ei.push_match(match_cur,
+                    MatchedNonterminal(Rc::new(parse_nt(&mut parser, span, &ident.name.as_str()))));
                 ei.idx += 1;
                 ei.match_cur += 1;
             } else {
diff --git a/src/libsyntax/ext/tt/macro_rules.rs b/src/libsyntax/ext/tt/macro_rules.rs
index 0472a94e0ce..9c728c9f2eb 100644
--- a/src/libsyntax/ext/tt/macro_rules.rs
+++ b/src/libsyntax/ext/tt/macro_rules.rs
@@ -219,7 +219,7 @@ pub fn compile(sess: &ParseSess, features: &RefCell<Features>, def: &ast::Item)
     let lhses = match *argument_map[&lhs_nm] {
         MatchedSeq(ref s, _) => {
             s.iter().map(|m| {
-                if let MatchedNonterminal(ref nt) = **m {
+                if let MatchedNonterminal(ref nt) = *m {
                     if let NtTT(ref tt) = **nt {
                         let tt = quoted::parse(tt.clone().into(), true, sess).pop().unwrap();
                         valid &= check_lhs_nt_follows(sess, features, &tt);
@@ -235,7 +235,7 @@ pub fn compile(sess: &ParseSess, features: &RefCell<Features>, def: &ast::Item)
     let rhses = match *argument_map[&rhs_nm] {
         MatchedSeq(ref s, _) => {
             s.iter().map(|m| {
-                if let MatchedNonterminal(ref nt) = **m {
+                if let MatchedNonterminal(ref nt) = *m {
                     if let NtTT(ref tt) = **nt {
                         return quoted::parse(tt.clone().into(), false, sess).pop().unwrap();
                     }
diff --git a/src/libsyntax/ext/tt/transcribe.rs b/src/libsyntax/ext/tt/transcribe.rs
index 2a435bdea10..78e755e73fa 100644
--- a/src/libsyntax/ext/tt/transcribe.rs
+++ b/src/libsyntax/ext/tt/transcribe.rs
@@ -182,15 +182,16 @@ fn lookup_cur_matched(ident: Ident,
                       repeats: &[(usize, usize)])
                       -> Option<Rc<NamedMatch>> {
     interpolations.get(&ident).map(|matched| {
-        repeats.iter().fold(matched.clone(), |ad, &(idx, _)| {
-            match *ad {
-                MatchedNonterminal(_) => {
-                    // end of the line; duplicate henceforth
-                    ad.clone()
-                }
-                MatchedSeq(ref ads, _) => ads[idx].clone()
+        let mut matched = matched.clone();
+        for &(idx, _) in repeats {
+            let m = matched.clone();
+            match *m {
+                MatchedNonterminal(_) => break,
+                MatchedSeq(ref ads, _) => matched = Rc::new(ads[idx].clone()),
             }
-        })
+        }
+
+        matched
     })
 }