Reduced malloc/free operations in the parser.

src/parser.cc

 // Copyright 2006-2008 the V8 project authors. All rights reserved.
 // Redistribution and use in source and binary forms, with or without
 // modification, are permitted provided that the following conditions are
 // met:
 //
 //     * Redistributions of source code must retain the above copyright
 //       notice, this list of conditions and the following disclaimer.
 //     * Redistributions in binary form must reproduce the above
 //       copyright notice, this list of conditions and the following
 //       disclaimer in the documentation and/or other materials provided
@@ skipping 24 matching lines @@
 #include "runtime.h"
 #include "parser.h"
 #include "scopes.h"
 #include "string-stream.h"
 
 namespace v8 { namespace internal {
 
 class ParserFactory;
 class ParserLog;
 class TemporaryScope;
+class Target;
+
 template <typename T> class ZoneListWrapper;
 
 
+// PositionStack is used for on-stack allocation of token positions for
+// new expressions. Please look at ParseNewExpression.
+
+class PositionStack  {
+ public:
+  PositionStack() : top_(NULL) {}
+  ~PositionStack() { }
+
+  class Element  {

[Kasper Lund, 2009/05/15 13:37:11]

Couldn't the entire Element class be private?

+   public:
+    Element(PositionStack* stack, int value) {
+      previous_ = stack->top();
+      value_ = value;
+      stack->set_top(this);
+    }
+   protected:

[Kasper Lund, 2009/05/15 13:37:11]

How about a newline before protected: and private: (repeated)?

[Kasper Lund, 2009/05/15 13:37:11]

Why do you have both private and protected? Do you ever inherit from
PositionStack?

+    Element* previous() { return previous_; }
+    int value() { return value_; }
+    friend class PositionStack;
+   private:
+    Element* previous_;
+    int value_;
+  };
+
+  bool is_empty() { return top_ == NULL; }
+  int pop() {
+    ASSERT(!is_empty());
+    int result = top_->value();
+    top_ = top_->previous();
+    return result;
+  }
+ protected:
+  Element* top() { return top_; }
+  void set_top(Element* value) { top_ = value; }
+ private:
+  Element* top_;
+};
+
+
 class Parser {
  public:
   Parser(Handle<Script> script, bool allow_natives_syntax,
          v8::Extension* extension, bool is_pre_parsing,
          ParserFactory* factory, ParserLog* log, ScriptDataImpl* pre_data);
   virtual ~Parser() { }
 
   // Pre-parse the program from the character stream; returns true on
   // success, false if a stack-overflow happened during parsing.
   bool PreParseProgram(unibrow::CharacterStream* stream);
@@ skipping 28 matching lines @@
   void ReportUnexpectedToken(Token::Value token);
 
   Handle<Script> script_;
   Scanner scanner_;
 
   Scope* top_scope_;
   int with_nesting_level_;
 
   TemporaryScope* temp_scope_;
   Mode mode_;
-  List<Node*>* target_stack_;  // for break, continue statements
+
+  Target* target_stack_;  // for break, continue statements
   bool allow_natives_syntax_;
   v8::Extension* extension_;
   ParserFactory* factory_;
   ParserLog* log_;
   bool is_pre_parsing_;
   ScriptDataImpl* pre_data_;
 
   bool inside_with() const  { return with_nesting_level_ > 0; }
   ParserFactory* factory() const  { return factory_; }
   ParserLog* log() const { return log_; }
@@ skipping 36 matching lines @@
 
   Expression* ParseExpression(bool accept_IN, bool* ok);
   Expression* ParseAssignmentExpression(bool accept_IN, bool* ok);
   Expression* ParseConditionalExpression(bool accept_IN, bool* ok);
   Expression* ParseBinaryExpression(int prec, bool accept_IN, bool* ok);
   Expression* ParseUnaryExpression(bool* ok);
   Expression* ParsePostfixExpression(bool* ok);
   Expression* ParseLeftHandSideExpression(bool* ok);
   Expression* ParseNewExpression(bool* ok);
   Expression* ParseMemberExpression(bool* ok);
-  Expression* ParseMemberWithNewPrefixesExpression(List<int>* new_prefixes,
+  Expression* ParseNewPrefix(PositionStack* stack, bool* ok);
+  Expression* ParseMemberWithNewPrefixesExpression(PositionStack* stack,
                                                    bool* ok);
   Expression* ParsePrimaryExpression(bool* ok);
   Expression* ParseArrayLiteral(bool* ok);
   Expression* ParseObjectLiteral(bool* ok);
   Expression* ParseRegExpLiteral(bool seen_equal, bool* ok);
 
   // Decide if a property should be the object boilerplate.
   bool IsBoilerplateProperty(ObjectLiteral::Property* property);
   // If the expression is a literal, return the literal value;
   // if the expression is a materialized literal and is simple return a
@@ skipping 37 matching lines @@
   // Parser support
   virtual VariableProxy* Declare(Handle<String> name, Variable::Mode mode,
                                  FunctionLiteral* fun,
                                  bool resolve,
                                  bool* ok) = 0;
 
   bool TargetStackContainsLabel(Handle<String> label);
   BreakableStatement* LookupBreakTarget(Handle<String> label, bool* ok);
   IterationStatement* LookupContinueTarget(Handle<String> label, bool* ok);
 
-  void RegisterTargetUse(BreakTarget* target, int index);
+  void RegisterTargetUse(BreakTarget* target, Target* stop);
 
   // Create a number literal.
   Literal* NewNumberLiteral(double value);
 
   // Generate AST node that throw a ReferenceError with the given type.
   Expression* NewThrowReferenceError(Handle<String> type);
 
   // Generate AST node that throw a SyntaxError with the given
   // type. The first argument may be null (in the handle sense) in
   // which case no arguments are passed to the constructor.
@@ skipping 742 matching lines @@
 
 
 // ----------------------------------------------------------------------------
 // Target is a support class to facilitate manipulation of the
 // Parser's target_stack_ (the stack of potential 'break' and
 // 'continue' statement targets). Upon construction, a new target is
 // added; it is removed upon destruction.
 
 class Target BASE_EMBEDDED {
  public:
-  Target(Parser* parser, Node* node) : parser_(parser) {
-    parser_->target_stack_->Add(node);
+  Target(Parser* parser, Node* node)
+      : parser_(parser), node_(node), previous_(parser_->target_stack_) {
+    parser_->target_stack_ = this;
   }
 
   ~Target() {
-    parser_->target_stack_->RemoveLast();
+    parser_->target_stack_ = previous_;
   }
 
+  Target* previous() { return previous_; }
+  Node* node() { return node_; }
+
  private:
   Parser* parser_;
+  Node* node_;
+  Target* previous_;
 };
 
 
 class TargetScope BASE_EMBEDDED {
  public:
   explicit TargetScope(Parser* parser)
-      : parser_(parser), previous_(parser->target_stack_), stack_(0) {
-    parser_->target_stack_ = &stack_;
+      : parser_(parser), previous_(parser->target_stack_) {
+    parser->target_stack_ = NULL;
   }
 
   ~TargetScope() {
-    ASSERT(stack_.is_empty());
     parser_->target_stack_ = previous_;
   }
 
  private:
   Parser* parser_;
-  List<Node*>* previous_;
-  List<Node*> stack_;
+  Target* previous_;
 };
 
 
 // ----------------------------------------------------------------------------
 // LexicalScope is a support class to facilitate manipulation of the
 // Parser's scope stack. The constructor sets the parser's top scope
 // to the incoming scope, and the destructor resets it.
 
 class LexicalScope BASE_EMBEDDED {
  public:
@@ skipping 1772 matching lines @@
         break;
       }
 
       default:
         return result;
     }
   }
 }
 
 
-Expression* Parser::ParseNewExpression(bool* ok) {
+
+Expression* Parser::ParseNewPrefix(PositionStack* stack, bool* ok) {
   // NewExpression ::
   //   ('new')+ MemberExpression
 
   // The grammar for new expressions is pretty warped. The keyword
   // 'new' can either be a part of the new expression (where it isn't
   // followed by an argument list) or a part of the member expression,
   // where it must be followed by an argument list. To accommodate
   // this, we parse the 'new' keywords greedily and keep track of how
   // many we have parsed. This information is then passed on to the
   // member expression parser, which is only allowed to match argument
   // lists as long as it has 'new' prefixes left
-  List<int> new_positions(4);
-  while (peek() == Token::NEW) {
-    Consume(Token::NEW);
-    new_positions.Add(scanner().location().beg_pos);
+  Expect(Token::NEW, CHECK_OK);
+  PositionStack::Element pos(stack, scanner().location().beg_pos);
+
+  Expression* result;
+  if (peek() == Token::NEW) {
+    result = ParseNewPrefix(stack, CHECK_OK);
+  } else {
+    result = ParseMemberWithNewPrefixesExpression(stack, CHECK_OK);
   }
-  ASSERT(new_positions.length() > 0);
 
-  Expression* result =
-      ParseMemberWithNewPrefixesExpression(&new_positions, CHECK_OK);
-  while (!new_positions.is_empty()) {
-    int last = new_positions.RemoveLast();
-    result = NEW(CallNew(result, new ZoneList<Expression*>(0), last));
+  if (!stack->is_empty()) {
+    result = NEW(CallNew(result, new ZoneList<Expression*>(0), stack->pop()));
   }
   return result;
 }
 
 
-Expression* Parser::ParseMemberExpression(bool* ok) {
-  static List<int> new_positions(0);
-  return ParseMemberWithNewPrefixesExpression(&new_positions, ok);
+Expression* Parser::ParseNewExpression(bool* ok) {
+  PositionStack stack;
+  return ParseNewPrefix(&stack, ok);
 }
 
 
-Expression* Parser::ParseMemberWithNewPrefixesExpression(
-    List<int>* new_positions,
-    bool* ok) {
+Expression* Parser::ParseMemberExpression(bool* ok) {
+  return ParseMemberWithNewPrefixesExpression(NULL, ok);
+}
+
+
+Expression* Parser::ParseMemberWithNewPrefixesExpression(PositionStack* stack,
+                                                         bool* ok) {
   // MemberExpression ::
   //   (PrimaryExpression | FunctionLiteral)
   //     ('[' Expression ']' | '.' Identifier | Arguments)*
 
   // Parse the initial primary or function expression.
   Expression* result = NULL;
   if (peek() == Token::FUNCTION) {
     Expect(Token::FUNCTION, CHECK_OK);
     int function_token_position = scanner().location().beg_pos;
     Handle<String> name;
@@ skipping 15 matching lines @@
         break;
       }
       case Token::PERIOD: {
         Consume(Token::PERIOD);
         int pos = scanner().location().beg_pos;
         Handle<String> name = ParseIdentifier(CHECK_OK);
         result = factory()->NewProperty(result, NEW(Literal(name)), pos);
         break;
       }
       case Token::LPAREN: {
-        if (new_positions->is_empty()) return result;
+        if ((stack == NULL) || stack->is_empty()) return result;
         // Consume one of the new prefixes (already parsed).
         ZoneList<Expression*>* args = ParseArguments(CHECK_OK);
-        int last = new_positions->RemoveLast();
-        result = NEW(CallNew(result, args, last));
+        result = NEW(CallNew(result, args, stack->pop()));
         break;
       }
       default:
         return result;
     }
   }
 }
 
 
 DebuggerStatement* Parser::ParseDebuggerStatement(bool* ok) {
@@ skipping 658 matching lines @@
   return factory()->LookupSymbol(scanner_.literal_string(),
                                  scanner_.literal_length());
 }
 
 
 // ----------------------------------------------------------------------------
 // Parser support
 
 
 bool Parser::TargetStackContainsLabel(Handle<String> label) {
-  for (int i = target_stack_->length(); i-- > 0;) {
-    BreakableStatement* stat = target_stack_->at(i)->AsBreakableStatement();
+  for (Target* t = target_stack_; t != NULL; t = t->previous()) {
+    BreakableStatement* stat = t->node()->AsBreakableStatement();
     if (stat != NULL && ContainsLabel(stat->labels(), label))
       return true;
   }
   return false;
 }
 
 
 BreakableStatement* Parser::LookupBreakTarget(Handle<String> label, bool* ok) {
   bool anonymous = label.is_null();
-  for (int i = target_stack_->length(); i-- > 0;) {
-    BreakableStatement* stat = target_stack_->at(i)->AsBreakableStatement();
+  for (Target* t = target_stack_; t != NULL; t = t->previous()) {
+    BreakableStatement* stat = t->node()->AsBreakableStatement();
     if (stat == NULL) continue;
-
     if ((anonymous && stat->is_target_for_anonymous()) ||
         (!anonymous && ContainsLabel(stat->labels(), label))) {
-      RegisterTargetUse(stat->break_target(), i);
+      RegisterTargetUse(stat->break_target(), t->previous());
       return stat;
     }
   }
   return NULL;
 }
 
 
 IterationStatement* Parser::LookupContinueTarget(Handle<String> label,
                                                  bool* ok) {
   bool anonymous = label.is_null();
-  for (int i = target_stack_->length(); i-- > 0;) {
-    IterationStatement* stat = target_stack_->at(i)->AsIterationStatement();
+  for (Target* t = target_stack_; t != NULL; t = t->previous()) {
+    IterationStatement* stat = t->node()->AsIterationStatement();
     if (stat == NULL) continue;
 
     ASSERT(stat->is_target_for_anonymous());
     if (anonymous || ContainsLabel(stat->labels(), label)) {
-      RegisterTargetUse(stat->continue_target(), i);
+      RegisterTargetUse(stat->continue_target(), t->previous());
       return stat;
     }
   }
   return NULL;
 }
 
 
-void Parser::RegisterTargetUse(BreakTarget* target, int index) {
-  // Register that a break target found at the given index in the
+void Parser::RegisterTargetUse(BreakTarget* target, Target* stop) {
+  // Register that a break target found at the given stop in the
   // target stack has been used from the top of the target stack. Add
   // the break target to any TargetCollectors passed on the stack.
-  for (int i = target_stack_->length(); i-- > index;) {
-    TargetCollector* collector = target_stack_->at(i)->AsTargetCollector();
+  for (Target* t = target_stack_; t != stop; t = t->previous()) {
+    TargetCollector* collector = t->node()->AsTargetCollector();
     if (collector != NULL) collector->AddTarget(target);
   }
 }
 
 
 Literal* Parser::NewNumberLiteral(double number) {
   return NEW(Literal(Factory::NewNumber(number, TENURED)));
 }
 
 
@@ skipping 962 matching lines @@
                        start_position,
                        is_expression);
   return result;
 }
 
 
 #undef NEW
 
 
 } }  // namespace v8::internal