Speed up parsing w/ grammar shortcut.

src/parsing/parser-base.h

 // Copyright 2012 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #ifndef V8_PARSING_PARSER_BASE_H
 #define V8_PARSING_PARSER_BASE_H
 
 #include "src/ast/scopes.h"
 #include "src/bailout-reason.h"
 #include "src/base/hashmap.h"
@@ skipping 1059 matching lines @@
       ExpressionClassifier* classifier, bool* ok);
   typename Traits::Type::ExpressionList ParseArguments(
       Scanner::Location* first_spread_pos, ExpressionClassifier* classifier,
       bool* ok) {
     return ParseArguments(first_spread_pos, false, classifier, ok);
   }
 
   ExpressionT ParseAssignmentExpression(bool accept_IN,
                                         ExpressionClassifier* classifier,
                                         bool* ok);
+  ExpressionT ParseTrivialAssignmentExpression(ExpressionClassifier* classifier,
+                                               bool* ok);
   ExpressionT ParseYieldExpression(bool accept_IN,
                                    ExpressionClassifier* classifier, bool* ok);
   ExpressionT ParseTailCallExpression(ExpressionClassifier* classifier,
                                       bool* ok);
   ExpressionT ParseConditionalExpression(bool accept_IN,
                                          ExpressionClassifier* classifier,
                                          bool* ok);
   ExpressionT ParseBinaryExpression(int prec, bool accept_IN,
                                     ExpressionClassifier* classifier, bool* ok);
   ExpressionT ParseUnaryExpression(ExpressionClassifier* classifier, bool* ok);
@@ skipping 453 matching lines @@
   switch (peek()) {
     case Token::THIS: {
       BindingPatternUnexpectedToken(classifier);
       Consume(Token::THIS);
       return this->ThisExpression(scope(), factory(), beg_pos);
     }
 
     case Token::NULL_LITERAL:
     case Token::TRUE_LITERAL:
     case Token::FALSE_LITERAL:
-      BindingPatternUnexpectedToken(classifier);
-      return this->ExpressionFromLiteral(Next(), beg_pos, scanner(), factory());
     case Token::SMI:
     case Token::NUMBER:
       BindingPatternUnexpectedToken(classifier);
       return this->ExpressionFromLiteral(Next(), beg_pos, scanner(), factory());
 
     case Token::ASYNC:
       if (allow_harmony_async_await() &&
           !scanner()->HasAnyLineTerminatorAfterNext() &&
           PeekAhead() == Token::FUNCTION) {
         Consume(Token::ASYNC);
@@ skipping 705 matching lines @@
 
   return result;
 }
 
 // Precedence = 2
 template <class Traits>
 typename ParserBase<Traits>::ExpressionT
 ParserBase<Traits>::ParseAssignmentExpression(bool accept_IN,
                                               ExpressionClassifier* classifier,
                                               bool* ok) {
+  // Try to parse a simple sub-grammar and early-out if successful.
+  typename ParserBase<Traits>::ExpressionT trivial_result =
+      this->ParseTrivialAssignmentExpression(classifier, ok);
+  if (!Traits::IsEmptyExpression(trivial_result)) return trivial_result;

[marja, 2016/07/29 07:56:04]

Ah right, since we have 2 expression types, this check is more complicated.

How about passing the "is trivial" return value explicitly:

bool is_trivial = false;
... trivial_result = ParseTrivialAssignmentExpression(..., &is_trivial);
if (is_trivial) return trivial_result;

Or the other way around:

ExpressionT trivial_result;
if (ParseTrivialAssignmentExpression(... , &trivial_result)) return
trivial_result;

Would one of these be clearer than the somewhat artificial emptiness check? I
like the second version...

In reality, we'd like to pass both the expression and the success bool as return
values, and it's just a limitation of C++ that we can't.

[vogelheim, 2016/08/09 11:26:08]

Done. (2nd version)

+
   // AssignmentExpression ::
   //   ConditionalExpression
   //   ArrowFunction
   //   YieldExpression
   //   LeftHandSideExpression AssignmentOperator AssignmentExpression
   bool is_destructuring_assignment = false;
   int lhs_beg_pos = peek_position();
 
   if (peek() == Token::YIELD && is_generator()) {
     return this->ParseYieldExpression(accept_IN, classifier, ok);
   }
 
   FuncNameInferrer::State fni_state(fni_);
   ParserBase<Traits>::Checkpoint checkpoint(this);
   ExpressionClassifier arrow_formals_classifier(this,
                                                 classifier->duplicate_finder());
 
   bool is_async = allow_harmony_async_await() && peek() == Token::ASYNC &&
                   !scanner()->HasAnyLineTerminatorAfterNext() &&
                   IsValidArrowFormalParametersStart(PeekAhead());
 
   bool parenthesized_formals = peek() == Token::LPAREN;
   if (!is_async && !parenthesized_formals) {
     ArrowFormalParametersUnexpectedToken(&arrow_formals_classifier);
   }
   ExpressionT expression = this->ParseConditionalExpression(

[adamk, 2016/07/28 17:51:55]

What if, rather than putting ParseTrivialAssignmentExpression() up at the top,
you put it here instead, after checking for the case that'll be trivially
parseable? That would let you eliminate a lot of the worst duplication (the
FuncNameInferrer, the ExpressionClassifier) since those are already set up
correctly at this point.

[vogelheim, 2016/08/09 11:26:08]

Well... it would also do a lot of work that I'm now skipping. E.g., notice that
most branches (all except the Identifier one) don't instantiate a separate
classifier and instead record the proper effect directly with the one that's
passed in.

[adamk, 2016/08/09 16:39:16]

But we'd still be skipping the function calls, right (my understanding was that
the function calls were what was expensive here)?

I don't see anything horribly expensive above. And it's the ExpressionClassifier
that I especially would like to not see duplicated, since the logic is quite
subtle. The FuncNameInferrer would also be nice not to duplicate.

The only other expensive work I see is the call to PeekAhead(), but you already
do that in ParseTrivial.

This seems like something we could measure. Would you mind giving it a shot?

       accept_IN, &arrow_formals_classifier, CHECK_OK);
 
   if (is_async && peek_any_identifier() && PeekAhead() == Token::ARROW) {
     // async Identifier => AsyncConciseBody
     IdentifierT name =
         ParseAndClassifyIdentifier(&arrow_formals_classifier, CHECK_OK);
     expression = this->ExpressionFromIdentifier(
         name, position(), scanner()->location().end_pos, scope(), factory());
   }
 
@@ skipping 142 matching lines @@
   if (is_destructuring_assignment) {
     result = factory()->NewRewritableExpression(result);
     Traits::QueueDestructuringAssignmentForRewriting(result);
   }
 
   return result;
 }
 
 template <class Traits>
 typename ParserBase<Traits>::ExpressionT
+ParserBase<Traits>::ParseTrivialAssignmentExpression(
+    ExpressionClassifier* classifier, bool* ok) {
+  // Parser shortcut: The following scope is a micro-optimization to reduce

[adamk, 2016/07/28 17:51:55]

This can be rewritten now that it's in its own function:

s/Parser shortcut: The following scope/This parser shortcut/

[vogelheim, 2016/08/09 11:26:08]

Done.

+  // parsing time. It should be functionally neutral and deliver either nullptr
+  // or the same result as the canonical ParseAssignmentExpression.
+  // When we encounter
+  //   [SMI|NUMBER|{NULL,TRUE,FALSE}_LITERAL|THIS|STRING|IDENTIFIER]
+  // followed by
+  //    [COMMA|RPAREN|RBRACK|SEMICOLON]
+  // then this will result in a single AST node. Instead of parsing this
+  // 'properly' (a call chain 11-levels deep), we will just generate the
+  // appropriate AST nodes right here.
+  Token::Value peek_token = peek();
+  bool is_number = peek_token == Token::SMI || peek_token == Token::NUMBER;
+  bool is_literal = peek_token == Token::NULL_LITERAL ||
+                    peek_token == Token::TRUE_LITERAL ||
+                    peek_token == Token::FALSE_LITERAL;
+  bool is_string = peek_token == Token::STRING;
+  bool is_identifier = peek_token == Token::IDENTIFIER;
+  bool is_this = peek_token == Token::THIS;
+  if (is_number || is_literal || is_string || is_identifier || is_this) {
+    // PeekAhead() is expensive & may not always be called, so we only call it
+    // after checking peek().
+    Token::Value peek_ahead = PeekAhead();
+    if (peek_ahead == Token::COMMA || peek_ahead == Token::RPAREN ||
+        peek_ahead == Token::SEMICOLON || peek_ahead == Token::RBRACK) {
+      Scanner::Location pos = scanner()->peek_location();
+      if (is_string) {
+        FuncNameInferrer::State fni_state(fni_);
+        classifier->RecordBindingPatternError(
+            pos, MessageTemplate::kUnexpectedTokenString);
+        Consume(Token::STRING);
+        return this->ExpressionFromString(pos.beg_pos, scanner(), factory());
+      } else if (is_this) {
+        classifier->RecordBindingPatternError(
+            pos, MessageTemplate::kUnexpectedToken, Token::Name(Token::THIS));
+        Consume(Token::THIS);
+        return this->ThisExpression(scope(), factory(), pos.beg_pos);
+      } else if (is_number) {
+        classifier->RecordBindingPatternError(
+            pos, MessageTemplate::kUnexpectedTokenNumber);
+        Consume(peek_token);
+        return this->ExpressionFromLiteral(peek_token, pos.beg_pos, scanner(),
+                                           factory());
+      } else if (is_literal) {
+        classifier->RecordBindingPatternError(
+            pos, MessageTemplate::kUnexpectedToken, Token::Name(peek_token));
+        Consume(peek_token);
+        return this->ExpressionFromLiteral(peek_token, pos.beg_pos, scanner(),
+                                           factory());
+      } else if (is_identifier) {
+        FuncNameInferrer::State fni_state(fni_);
+        ExpressionClassifier arrow_formals_classifier(
+            this, classifier->duplicate_finder());
+        IdentifierT name =
+            ParseAndClassifyIdentifier(&arrow_formals_classifier, CHECK_OK);
+        typename ParserBase<Traits>::ExpressionT shortcut_result =
+            this->ExpressionFromIdentifier(name, pos.beg_pos, pos.end_pos,
+                                           scope(), factory());
+        if (this->IsAssignableIdentifier(shortcut_result)) {
+          arrow_formals_classifier.ForgiveAssignmentPatternError();
+        }
+        classifier->Accumulate(
+            &arrow_formals_classifier,
+            ExpressionClassifier::StandardProductions |
+                ExpressionClassifier::FormalParametersProductions |
+                ExpressionClassifier::CoverInitializedNameProduction |
+                ExpressionClassifier::AsyncArrowFormalParametersProduction |
+                ExpressionClassifier::AsyncBindingPatternProduction,
+            false);
+        DCHECK(!Token::IsAssignmentOp(peek_ahead));
+        classifier->MergeNonPatterns(&arrow_formals_classifier);
+        return shortcut_result;
+      } else {
+        UNREACHABLE();
+      }
+    }
+  }
+  // No applicable shortcut found: Proceed w/ regular parsing.
+  return this->EmptyExpression();
+}
+
+template <class Traits>
+typename ParserBase<Traits>::ExpressionT
 ParserBase<Traits>::ParseYieldExpression(bool accept_IN,
                                          ExpressionClassifier* classifier,
                                          bool* ok) {
   // YieldExpression ::
   //   'yield' ([no line terminator] '*'? AssignmentExpression)?
   int pos = peek_position();
   classifier->RecordPatternError(scanner()->peek_location(),
                                  MessageTemplate::kInvalidDestructuringTarget);
   classifier->RecordFormalParameterInitializerError(
       scanner()->peek_location(), MessageTemplate::kYieldInParameter);
@@ skipping 1219 matching lines @@
     has_seen_constructor_ = true;
     return;
   }
 }
 
 
 }  // namespace internal
 }  // namespace v8
 
 #endif  // V8_PARSING_PARSER_BASE_H