Reduce the memory footprint of expression classifiers

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/hashmap.h"
@@ skipping 367 matching lines @@
       DCHECK(is_resumable());
       generator_object_variable_ = variable;
     }
     typename Traits::Type::GeneratorVariable* generator_object_variable()
         const {
       return generator_object_variable_;
     }
 
     typename Traits::Type::Factory* factory() { return factory_; }
 
-    const List<DestructuringAssignment>& destructuring_assignments_to_rewrite()
-        const {
+    const ZoneList<DestructuringAssignment>&
+        destructuring_assignments_to_rewrite() const {
       return destructuring_assignments_to_rewrite_;
     }
 
     TailCallExpressionList& tail_call_expressions() {
       return tail_call_expressions_;
     }
     void AddImplicitTailCallExpression(ExpressionT expression) {
       if (return_expr_context() ==
           ReturnExprContext::kInsideValidReturnStatement) {
         tail_call_expressions_.AddImplicitTailCall(expression);
       }
     }
     void AddExplicitTailCallExpression(ExpressionT expression,
                                        const Scanner::Location& loc) {
       DCHECK(expression->IsCall());
       if (return_expr_context() ==
           ReturnExprContext::kInsideValidReturnStatement) {
         tail_call_expressions_.AddExplicitTailCall(expression, loc);
       }
     }
 
+    ZoneList<typename ExpressionClassifier::Error>* GetReportedErrorList() {
+      return &reported_errors_;
+    }
+
     ReturnExprContext return_expr_context() const {
       return return_expr_context_;
     }
     void set_return_expr_context(ReturnExprContext context) {
       return_expr_context_ = context;
     }
 
     ZoneList<ExpressionT>* non_patterns_to_rewrite() {
       return &non_patterns_to_rewrite_;
     }
 
     void next_function_is_parenthesized(bool parenthesized) {
       next_function_is_parenthesized_ = parenthesized;
     }
 
     bool this_function_is_parenthesized() const {
       return this_function_is_parenthesized_;
     }
 
    private:
     void AddDestructuringAssignment(DestructuringAssignment pair) {
-      destructuring_assignments_to_rewrite_.Add(pair);
+      destructuring_assignments_to_rewrite_.Add(pair, (*scope_stack_)->zone());
     }
 
     V8_INLINE Scope* scope() { return *scope_stack_; }
 
     void AddNonPatternForRewriting(ExpressionT expr) {
       non_patterns_to_rewrite_.Add(expr, (*scope_stack_)->zone());
     }
 
     // Used to assign an index to each literal that needs materialization in
     // the function.  Includes regexp literals, and boilerplate for object and
@@ skipping 16 matching lines @@
     // For generators, this variable may hold the generator object. It variable
     // is used by yield expressions and return statements. It is not necessary
     // for generator functions to have this variable set.
     Variable* generator_object_variable_;
 
     FunctionState** function_state_stack_;
     FunctionState* outer_function_state_;
     Scope** scope_stack_;
     Scope* outer_scope_;
 
-    List<DestructuringAssignment> destructuring_assignments_to_rewrite_;
+    ZoneList<DestructuringAssignment> destructuring_assignments_to_rewrite_;

[adamk, 2016/06/06 20:51:02]

Yikes, was this a memory leak before? Maybe pull this into a separate patch?

[nickie, 2016/06/08 11:38:46]

As far as I understand, it was not a memory leak.  It was just using the heap,
instead of the zone, for storing the list of DestructuringAssignments.  The list
destructor clears the space.

[adamk, 2016/06/09 08:25:36]

Ah, I forgot this was in FunctionState, not some ZoneObject.

     TailCallExpressionList tail_call_expressions_;
     ReturnExprContext return_expr_context_;
     ZoneList<ExpressionT> non_patterns_to_rewrite_;
 
+    ZoneList<typename ExpressionClassifier::Error> reported_errors_;
+
     typename Traits::Type::Factory* factory_;
 
     // If true, the next (and immediately following) function literal is
     // preceded by a parenthesis.
     bool next_function_is_parenthesized_;
 
     // The value of the parents' next_function_is_parenthesized_, as it applies
     // to this function. Filled in by constructor.
     bool this_function_is_parenthesized_;
 
@@ skipping 702 matching lines @@
       expected_property_count_(0),
       this_location_(Scanner::Location::invalid()),
       return_location_(Scanner::Location::invalid()),
       super_location_(Scanner::Location::invalid()),
       kind_(kind),
       generator_object_variable_(NULL),
       function_state_stack_(function_state_stack),
       outer_function_state_(*function_state_stack),
       scope_stack_(scope_stack),
       outer_scope_(*scope_stack),
+      destructuring_assignments_to_rewrite_(16, scope->zone()),
       tail_call_expressions_(scope->zone()),
       return_expr_context_(ReturnExprContext::kInsideValidBlock),
       non_patterns_to_rewrite_(0, scope->zone()),
+      reported_errors_(16, scope->zone()),
       factory_(factory),
       next_function_is_parenthesized_(false),
       this_function_is_parenthesized_(false) {
   *scope_stack_ = scope;
   *function_state_stack = this;
   if (outer_function_state_) {
     this_function_is_parenthesized_ =
         outer_function_state_->next_function_is_parenthesized_;
     outer_function_state_->next_function_is_parenthesized_ = false;
   }
@@ skipping 336 matching lines @@
 
     case Token::LBRACE:
       return this->ParseObjectLiteral(classifier, ok);
 
     case Token::LPAREN: {
       // Arrow function formal parameters are either a single identifier or a
       // list of BindingPattern productions enclosed in parentheses.
       // Parentheses are not valid on the LHS of a BindingPattern, so we use the
       // is_valid_binding_pattern() check to detect multiple levels of
       // parenthesization.
-      if (!classifier->is_valid_binding_pattern()) {
-        ArrowFormalParametersUnexpectedToken(classifier);
-      }
+      bool pattern_error = !classifier->is_valid_binding_pattern();
       classifier->RecordPatternError(scanner()->peek_location(),
                                      MessageTemplate::kUnexpectedToken,
                                      Token::String(Token::LPAREN));
+      if (pattern_error) ArrowFormalParametersUnexpectedToken(classifier);

[adamk, 2016/06/06 20:51:02]

Why was this reordering necessary? I think I'm missing exactly what you mean by
using the classifier in a "stack-based fashion".

[nickie, 2016/06/08 11:38:46]

This one is not related to the "stack-based fashion", it's just an optimization.
 If you put the AFP before the BP in the list, when accumulating the AFP will
not be copied and will force you to shift the BP one place to the left.  This
will save the trouble.  It actually occurs several hundred thousand times.  :-)

       Consume(Token::LPAREN);
       if (Check(Token::RPAREN)) {
         // ()=>x.  The continuation that looks for the => is in
         // ParseAssignmentExpression.
         classifier->RecordExpressionError(scanner()->location(),
                                           MessageTemplate::kUnexpectedToken,
                                           Token::String(Token::RPAREN));
         return factory()->NewEmptyParentheses(beg_pos);
       } else if (Check(Token::ELLIPSIS)) {
         // (...x)=>x.  The continuation that looks for the => is in
@@ skipping 85 matching lines @@
   return result;
 }
 
 template <class Traits>
 typename ParserBase<Traits>::ExpressionT ParserBase<Traits>::ParseExpression(
     bool accept_IN, ExpressionClassifier* classifier, bool* ok) {
   // Expression ::
   //   AssignmentExpression
   //   Expression ',' AssignmentExpression
 
   ExpressionClassifier binding_classifier(this);

[adamk, 2016/06/06 20:51:02]

Can we wrap this and the next two lines in a block, now that the classifier used
inside the loop is a different one? That'd avoid shadowing.

[nickie, 2016/06/08 11:38:46]

What you're suggesting is a common pattern in parser.cc but not in parser-base.h
 It can be done but not so easily because, as you say in the next comment,
result will have to be declared before the block, e.g.

  ExpressionT result;
  {
    ExpressionClassifier binding_classifier(this);
    result = this->ParseAssignmentExpression(...);
    classifier->Accumulate(&binding_classifier, ...);
  }

Now, for the parser where ExpressionT is a pointer, this is equivalent.
For the preparser, where ExpressionT is PreParserExpression, there is no default
constructor, so we would have to replace the first line with something like:

  ExpressionT elem = this->EmptyExpression();

Again, in the case of the parser this would be almost equivalent, as
EmptyExpression returns NULL and the compiler will probably figure out that
initialization is not necessary.  For the preparser, however, I think that this
would first initialize a PreParserExpression object and then use the copy
constructor to copy a new value there.

In any case, this pattern with the extraneous initialization occurs in several
places in parser-base.h and it would not harm much to add one more here, if you
insist.

[adamk, 2016/06/09 08:25:36]

If you think it's unlikely to be a significant perf regression, I do think that
this block would make the code more understandable. At the moment it's a bit
surprising to a casual reader that the Accumulate() call is to the outer
|classifier|, not this binding_classifier, even though the latter is the closest
one on the stack.

   ExpressionT result =

[adamk, 2016/06/06 20:51:02]

If you can do the above, this'll have to be declared outside the block
obviously.

       this->ParseAssignmentExpression(accept_IN, &binding_classifier, CHECK_OK);
   classifier->Accumulate(&binding_classifier,
                          ExpressionClassifier::AllProductions);
   bool is_simple_parameter_list = this->IsIdentifier(result);
   bool seen_rest = false;
   while (peek() == Token::COMMA) {
     CheckNoTailCallExpressions(classifier, CHECK_OK);
     if (seen_rest) {
       // At this point the production can't possibly be valid, but we don't know
       // which error to signal.
       classifier->RecordArrowFormalParametersError(
           scanner()->peek_location(), MessageTemplate::kParamAfterRest);
     }
     Consume(Token::COMMA);
     bool is_rest = false;
     if (peek() == Token::ELLIPSIS) {
       // 'x, y, ...z' in CoverParenthesizedExpressionAndArrowParameterList only
       // as the formal parameters of'(x, y, ...z) => foo', and is not itself a
       // valid expression or binding pattern.
       ExpressionUnexpectedToken(classifier);
       BindingPatternUnexpectedToken(classifier);
       Consume(Token::ELLIPSIS);
       seen_rest = is_rest = true;
     }
     int pos = position(), expr_pos = peek_position();
+    ExpressionClassifier binding_classifier(this);

[nickie, 2016/06/08 11:38:46]

Same thing; a block could be introduced here.

     ExpressionT right = this->ParseAssignmentExpression(
         accept_IN, &binding_classifier, CHECK_OK);
     classifier->Accumulate(&binding_classifier,
                            ExpressionClassifier::AllProductions);
     if (is_rest) {
       if (!this->IsIdentifier(right) && !IsValidPattern(right)) {
         classifier->RecordArrowFormalParametersError(
             Scanner::Location(pos, scanner()->location().end_pos),
             MessageTemplate::kInvalidRestParameter);
       }
@@ skipping 514 matching lines @@
 
   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());
   }
 
   if (peek() == Token::ARROW) {
-    classifier->RecordPatternError(scanner()->peek_location(),
-                                   MessageTemplate::kUnexpectedToken,
-                                   Token::String(Token::ARROW));
+    typename ExpressionClassifier::Error e1 =
+        ExpressionClassifier::BindingPatternError(
+            scanner()->peek_location(), MessageTemplate::kUnexpectedToken,

[adamk, 2016/06/06 20:51:02]

Can you just store the location here, and move the call to RecordPatternError
below? That'd save a good amount of boilerplate.

[nickie, 2016/06/08 11:38:46]

Done.

+            Token::String(Token::ARROW));
+    typename ExpressionClassifier::Error e2 =
+        ExpressionClassifier::AssignmentPatternError(
+            scanner()->peek_location(), MessageTemplate::kUnexpectedToken,
+            Token::String(Token::ARROW));
     ValidateArrowFormalParameters(&arrow_formals_classifier, expression,
                                   parenthesized_formals, is_async, CHECK_OK);
     // This reads strangely, but is correct: it checks whether any
     // sub-expression of the parameter list failed to be a valid formal
     // parameter initializer. Since YieldExpressions are banned anywhere
     // in an arrow parameter list, this is correct.
     // TODO(adamk): Rename "FormalParameterInitializerError" to refer to
     // "YieldExpression", which is its only use.
     ValidateFormalParameterInitializer(&arrow_formals_classifier, ok);
 
@@ skipping 16 matching lines @@
     scope->set_start_position(lhs_beg_pos);
     Scanner::Location duplicate_loc = Scanner::Location::invalid();
     this->ParseArrowFunctionFormalParameterList(&parameters, expression, loc,
                                                 &duplicate_loc, CHECK_OK);
     if (duplicate_loc.IsValid()) {
       arrow_formals_classifier.RecordDuplicateFormalParameterError(
           duplicate_loc);
     }
     expression = this->ParseArrowFunctionLiteral(
         accept_IN, parameters, is_async, arrow_formals_classifier, CHECK_OK);
+    arrow_formals_classifier.Discard();
+    classifier->RecordBindingPatternError(e1);
+    classifier->RecordAssignmentPatternError(e2);
 
     if (fni_ != nullptr) fni_->Infer();
 
     return expression;
   }
 
   if (this->IsValidReferenceExpression(expression)) {
     arrow_formals_classifier.ForgiveAssignmentPatternError();
   }
 
@@ skipping 219 matching lines @@
   //   LogicalOrExpression
   //   LogicalOrExpression '?' AssignmentExpression ':' AssignmentExpression
 
   int pos = peek_position();
   // We start using the binary expression parser for prec >= 4 only!
   ExpressionT expression =
       this->ParseBinaryExpression(4, accept_IN, classifier, CHECK_OK);
   if (peek() != Token::CONDITIONAL) return expression;
   CheckNoTailCallExpressions(classifier, CHECK_OK);
   Traits::RewriteNonPattern(classifier, CHECK_OK);
+  BindingPatternUnexpectedToken(classifier);
   ArrowFormalParametersUnexpectedToken(classifier);
-  BindingPatternUnexpectedToken(classifier);
   Consume(Token::CONDITIONAL);
   // In parsing the first assignment expression in conditional
   // expressions we always accept the 'in' keyword; see ECMA-262,
   // section 11.12, page 58.
   ExpressionT left = ParseAssignmentExpression(true, classifier, CHECK_OK);
   Traits::RewriteNonPattern(classifier, CHECK_OK);
   Expect(Token::COLON, CHECK_OK);
   ExpressionT right =
       ParseAssignmentExpression(accept_IN, classifier, CHECK_OK);
   Traits::RewriteNonPattern(classifier, CHECK_OK);
@@ skipping 1076 matching lines @@
     has_seen_constructor_ = true;
     return;
   }
 }
 
 
 }  // namespace internal
 }  // namespace v8
 
 #endif  // V8_PARSING_PARSER_BASE_H