[parser] Refactor AstTraversalVisitor

src/ast/ast-traversal-visitor.h

+// Copyright 2016 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_AST_AST_TRAVERSAL_VISITOR_H_
+#define V8_AST_AST_TRAVERSAL_VISITOR_H_
+
+#include "src/ast/ast.h"
+#include "src/ast/scopes.h"
+
+namespace v8 {
+namespace internal {
+
+// ----------------------------------------------------------------------------
+// Traversal visitor
+// - fully traverses the entire AST.
+//
+// Sub-class should parametrize AstTraversalVisitor with itself, e.g.:
+//   class SpecificVisitor : public AstTraversalVisitor<SpecificVisitor> { ... }
+//
+// It invokes VisitNode on each AST node, before proceeding with its subtrees.
+// It invokes VisitExpression (after VisitNode) on each AST node that is an
+// expression, before proceeding with its subtrees.
+// It proceeds with the subtrees only if these two methods return true.
+// Sub-classes may override VisitNode and VisitExpressions, whose implementation
+// is dummy here.  Or they may override the specific Visit* methods.
+
+template <class Subclass>
+class AstTraversalVisitor : public AstVisitor<Subclass> {
+ public:
+  explicit AstTraversalVisitor(Isolate* isolate, AstNode* root = nullptr);
+  explicit AstTraversalVisitor(uintptr_t stack_limit, AstNode* root = nullptr);
+
+  void Run() {
+    DCHECK_NOT_NULL(root_);
+    Visit(root_);
+  }
+
+  bool VisitNode(AstNode* node) { return true; }
+  bool VisitExpression(Expression* node) { return true; }

[adamk, 2016/07/21 18:11:57]

I don't see either of these methods overridden anywhere (VisitNode didn't exist
before, and this CL removes the only override of VisitExpression). Do we still
need this part of the design? 

[nickie, 2016/07/22 08:40:18]

They're not yet.  The idea is to have them there, so that several visitors
(existing, or future) can be refactored using them, e.g. AstNumberingVisitor,
which pretty much does one thing all over the tree.  If the functionality is not
needed and these methods have dummy implementations, they are static and the
optimizer will make them disappear.

All that said, there are three ways to make specialized visitors:

1. Redefine (some or all) specific Visit* methods, to do something specialized
to some types of nodes (after dispatch).
2. Redefine VisitNode and/or VisitExpression, to do something regardless of the
type of node (before dispatch).
3. Redefine the Visit() method, to do something that requires absolute freedom.

Bottom line, if you don't want them, they're not needed.  But I suggest that we
keep them.

[adamk, 2016/07/22 18:02:31]

Makes sense, I wanted to be clear that they're not used yet. I'd recommend using
them soon so they get covered by tests, otherwise they might well rot away.

+
+  // Iteration left-to-right.
+  void VisitDeclarations(ZoneList<Declaration*>* declarations);
+  void VisitStatements(ZoneList<Statement*>* statements);
+
+// Individual nodes
+#define DECLARE_VISIT(type) void Visit##type(type* node);
+  AST_NODE_LIST(DECLARE_VISIT)
+#undef DECLARE_VISIT
+
+ protected:
+  int depth() { return depth_; }

[adamk, 2016/07/21 18:11:57]

Nit: make this a const method

[nickie, 2016/07/22 08:40:18]

Done.

+
+ private:
+  DEFINE_AST_VISITOR_SUBCLASS_MEMBERS();
+
+  AstNode* root_;
+  int depth_;
+
+  DISALLOW_COPY_AND_ASSIGN(AstTraversalVisitor);
+};
+
+// ----------------------------------------------------------------------------
+// Implementation of AstTraversalVisitor
+
+#define PROCESS_NODE(node) do {                         \
+    if (!(this->impl()->VisitNode(node))) return;       \
+  } while (false)
+
+#define PROCESS_EXPRESSION(node) do {                           \
+    PROCESS_NODE(node);                                         \
+    if (!(this->impl()->VisitExpression(node))) return;         \
+  } while (false)
+
+#define RECURSE(call)               \
+  do {                              \
+    DCHECK(!HasStackOverflow());    \
+    this->impl()->call;             \
+    if (HasStackOverflow()) return; \
+  } while (false)
+
+#define RECURSE_EXPRESSION(call)    \
+  do {                              \
+    DCHECK(!HasStackOverflow());    \
+    ++depth_;                       \
+    this->impl()->call;             \
+    --depth_;                       \
+    if (HasStackOverflow()) return; \
+  } while (false)
+
+template <class Subclass>
+AstTraversalVisitor<Subclass>::AstTraversalVisitor(Isolate* isolate,
+                                                   AstNode* root)
+    : root_(root), depth_(0) {
+  InitializeAstVisitor(isolate);
+}
+
+template <class Subclass>
+AstTraversalVisitor<Subclass>::AstTraversalVisitor(uintptr_t stack_limit,
+                                                   AstNode* root)
+    : root_(root), depth_(0) {
+  InitializeAstVisitor(stack_limit);
+}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitDeclarations(
+    ZoneList<Declaration*>* decls) {
+  for (int i = 0; i < decls->length(); ++i) {
+    Declaration* decl = decls->at(i);
+    RECURSE(Visit(decl));
+  }
+}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitStatements(
+    ZoneList<Statement*>* stmts) {
+  for (int i = 0; i < stmts->length(); ++i) {
+    Statement* stmt = stmts->at(i);
+    RECURSE(Visit(stmt));
+    if (stmt->IsJump()) break;
+  }
+}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitVariableDeclaration(
+    VariableDeclaration* decl) {
+  PROCESS_NODE(decl);
+}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitFunctionDeclaration(
+    FunctionDeclaration* decl) {
+  PROCESS_NODE(decl);
+  RECURSE(Visit(decl->fun()));
+}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitBlock(Block* stmt) {
+  PROCESS_NODE(stmt);
+  RECURSE(VisitStatements(stmt->statements()));
+}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitExpressionStatement(
+    ExpressionStatement* stmt) {
+  PROCESS_NODE(stmt);
+  RECURSE(Visit(stmt->expression()));
+}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitEmptyStatement(EmptyStatement* stmt) {}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitSloppyBlockFunctionStatement(
+    SloppyBlockFunctionStatement* stmt) {
+  PROCESS_NODE(stmt);
+  RECURSE(Visit(stmt->statement()));
+}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitIfStatement(IfStatement* stmt) {
+  PROCESS_NODE(stmt);
+  RECURSE(Visit(stmt->condition()));
+  RECURSE(Visit(stmt->then_statement()));
+  RECURSE(Visit(stmt->else_statement()));
+}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitContinueStatement(
+    ContinueStatement* stmt) {
+  PROCESS_NODE(stmt);
+}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitBreakStatement(BreakStatement* stmt) {
+  PROCESS_NODE(stmt);
+}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitReturnStatement(
+    ReturnStatement* stmt) {
+  PROCESS_NODE(stmt);
+  RECURSE(Visit(stmt->expression()));
+}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitWithStatement(WithStatement* stmt) {
+  PROCESS_NODE(stmt);
+  RECURSE(Visit(stmt->expression()));
+  RECURSE(Visit(stmt->statement()));
+}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitSwitchStatement(
+    SwitchStatement* stmt) {
+  PROCESS_NODE(stmt);
+  RECURSE(Visit(stmt->tag()));
+
+  ZoneList<CaseClause*>* clauses = stmt->cases();
+  for (int i = 0; i < clauses->length(); ++i) {
+    CaseClause* clause = clauses->at(i);
+    if (!clause->is_default()) {
+      Expression* label = clause->label();
+      RECURSE(Visit(label));
+    }
+    ZoneList<Statement*>* stmts = clause->statements();
+    RECURSE(VisitStatements(stmts));
+  }
+}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitCaseClause(CaseClause* clause) {
+  UNREACHABLE();
+}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitDoWhileStatement(
+    DoWhileStatement* stmt) {
+  PROCESS_NODE(stmt);
+  RECURSE(Visit(stmt->body()));
+  RECURSE(Visit(stmt->cond()));
+}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitWhileStatement(WhileStatement* stmt) {
+  PROCESS_NODE(stmt);
+  RECURSE(Visit(stmt->cond()));
+  RECURSE(Visit(stmt->body()));
+}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitForStatement(ForStatement* stmt) {
+  PROCESS_NODE(stmt);
+  if (stmt->init() != NULL) {
+    RECURSE(Visit(stmt->init()));
+  }
+  if (stmt->cond() != NULL) {
+    RECURSE(Visit(stmt->cond()));
+  }
+  if (stmt->next() != NULL) {
+    RECURSE(Visit(stmt->next()));
+  }
+  RECURSE(Visit(stmt->body()));
+}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitForInStatement(ForInStatement* stmt) {
+  PROCESS_NODE(stmt);
+  RECURSE(Visit(stmt->enumerable()));
+  RECURSE(Visit(stmt->body()));
+}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitForOfStatement(ForOfStatement* stmt) {
+  PROCESS_NODE(stmt);
+  RECURSE(Visit(stmt->assign_iterator()));
+  RECURSE(Visit(stmt->next_result()));
+  RECURSE(Visit(stmt->result_done()));
+  RECURSE(Visit(stmt->assign_each()));
+  RECURSE(Visit(stmt->body()));
+}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitTryCatchStatement(
+    TryCatchStatement* stmt) {
+  PROCESS_NODE(stmt);
+  RECURSE(Visit(stmt->try_block()));
+  RECURSE(Visit(stmt->catch_block()));
+}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitTryFinallyStatement(
+    TryFinallyStatement* stmt) {
+  PROCESS_NODE(stmt);
+  RECURSE(Visit(stmt->try_block()));
+  RECURSE(Visit(stmt->finally_block()));
+}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitDebuggerStatement(
+    DebuggerStatement* stmt) {
+  PROCESS_NODE(stmt);
+}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitFunctionLiteral(
+    FunctionLiteral* expr) {
+  PROCESS_EXPRESSION(expr);
+  Scope* scope = expr->scope();
+  RECURSE_EXPRESSION(VisitDeclarations(scope->declarations()));
+  RECURSE_EXPRESSION(VisitStatements(expr->body()));
+}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitNativeFunctionLiteral(
+    NativeFunctionLiteral* expr) {
+  PROCESS_EXPRESSION(expr);
+}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitDoExpression(DoExpression* expr) {
+  PROCESS_EXPRESSION(expr);
+  RECURSE(VisitBlock(expr->block()));
+  RECURSE(VisitVariableProxy(expr->result()));
+}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitConditional(Conditional* expr) {
+  PROCESS_EXPRESSION(expr);
+  RECURSE_EXPRESSION(Visit(expr->condition()));
+  RECURSE_EXPRESSION(Visit(expr->then_expression()));
+  RECURSE_EXPRESSION(Visit(expr->else_expression()));
+}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitVariableProxy(VariableProxy* expr) {
+  PROCESS_EXPRESSION(expr);
+}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitLiteral(Literal* expr) {
+  PROCESS_EXPRESSION(expr);
+}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitRegExpLiteral(RegExpLiteral* expr) {
+  PROCESS_EXPRESSION(expr);
+}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitObjectLiteral(ObjectLiteral* expr) {
+  PROCESS_EXPRESSION(expr);
+  ZoneList<ObjectLiteralProperty*>* props = expr->properties();
+  for (int i = 0; i < props->length(); ++i) {
+    ObjectLiteralProperty* prop = props->at(i);
+    RECURSE_EXPRESSION(Visit(prop->key()));
+    RECURSE_EXPRESSION(Visit(prop->value()));
+  }
+}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitArrayLiteral(ArrayLiteral* expr) {
+  PROCESS_EXPRESSION(expr);
+  ZoneList<Expression*>* values = expr->values();
+  for (int i = 0; i < values->length(); ++i) {
+    Expression* value = values->at(i);
+    RECURSE_EXPRESSION(Visit(value));
+  }
+}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitAssignment(Assignment* expr) {
+  PROCESS_EXPRESSION(expr);
+  RECURSE_EXPRESSION(Visit(expr->target()));
+  RECURSE_EXPRESSION(Visit(expr->value()));
+}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitYield(Yield* expr) {
+  PROCESS_EXPRESSION(expr);
+  RECURSE_EXPRESSION(Visit(expr->generator_object()));
+  RECURSE_EXPRESSION(Visit(expr->expression()));
+}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitThrow(Throw* expr) {
+  PROCESS_EXPRESSION(expr);
+  RECURSE_EXPRESSION(Visit(expr->exception()));
+}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitProperty(Property* expr) {
+  PROCESS_EXPRESSION(expr);
+  RECURSE_EXPRESSION(Visit(expr->obj()));
+  RECURSE_EXPRESSION(Visit(expr->key()));
+}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitCall(Call* expr) {
+  PROCESS_EXPRESSION(expr);
+  RECURSE_EXPRESSION(Visit(expr->expression()));
+  ZoneList<Expression*>* args = expr->arguments();
+  for (int i = 0; i < args->length(); ++i) {
+    Expression* arg = args->at(i);
+    RECURSE_EXPRESSION(Visit(arg));
+  }
+}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitCallNew(CallNew* expr) {
+  PROCESS_EXPRESSION(expr);
+  RECURSE_EXPRESSION(Visit(expr->expression()));
+  ZoneList<Expression*>* args = expr->arguments();
+  for (int i = 0; i < args->length(); ++i) {
+    Expression* arg = args->at(i);
+    RECURSE_EXPRESSION(Visit(arg));
+  }
+}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitCallRuntime(CallRuntime* expr) {
+  PROCESS_EXPRESSION(expr);
+  ZoneList<Expression*>* args = expr->arguments();
+  for (int i = 0; i < args->length(); ++i) {
+    Expression* arg = args->at(i);
+    RECURSE_EXPRESSION(Visit(arg));
+  }
+}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitUnaryOperation(UnaryOperation* expr) {
+  PROCESS_EXPRESSION(expr);
+  RECURSE_EXPRESSION(Visit(expr->expression()));
+}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitCountOperation(CountOperation* expr) {
+  PROCESS_EXPRESSION(expr);
+  RECURSE_EXPRESSION(Visit(expr->expression()));
+}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitBinaryOperation(
+    BinaryOperation* expr) {
+  PROCESS_EXPRESSION(expr);
+  RECURSE_EXPRESSION(Visit(expr->left()));
+  RECURSE_EXPRESSION(Visit(expr->right()));
+}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitCompareOperation(
+    CompareOperation* expr) {
+  PROCESS_EXPRESSION(expr);
+  RECURSE_EXPRESSION(Visit(expr->left()));
+  RECURSE_EXPRESSION(Visit(expr->right()));
+}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitThisFunction(ThisFunction* expr) {
+  PROCESS_EXPRESSION(expr);
+}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitClassLiteral(ClassLiteral* expr) {
+  PROCESS_EXPRESSION(expr);
+  if (expr->extends() != nullptr) {
+    RECURSE_EXPRESSION(Visit(expr->extends()));
+  }
+  RECURSE_EXPRESSION(Visit(expr->constructor()));
+  ZoneList<ObjectLiteralProperty*>* props = expr->properties();
+  for (int i = 0; i < props->length(); ++i) {
+    ObjectLiteralProperty* prop = props->at(i);
+    if (!prop->key()->IsLiteral()) {
+      RECURSE_EXPRESSION(Visit(prop->key()));
+    }
+    RECURSE_EXPRESSION(Visit(prop->value()));
+  }
+}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitSpread(Spread* expr) {
+  PROCESS_EXPRESSION(expr);
+  RECURSE_EXPRESSION(Visit(expr->expression()));
+}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitEmptyParentheses(
+    EmptyParentheses* expr) {
+  PROCESS_EXPRESSION(expr);
+}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitSuperPropertyReference(
+    SuperPropertyReference* expr) {
+  PROCESS_EXPRESSION(expr);
+  RECURSE_EXPRESSION(VisitVariableProxy(expr->this_var()));
+  RECURSE_EXPRESSION(Visit(expr->home_object()));
+}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitSuperCallReference(
+    SuperCallReference* expr) {
+  PROCESS_EXPRESSION(expr);
+  RECURSE_EXPRESSION(VisitVariableProxy(expr->this_var()));
+  RECURSE_EXPRESSION(VisitVariableProxy(expr->new_target_var()));
+  RECURSE_EXPRESSION(VisitVariableProxy(expr->this_function_var()));
+}
+
+template <class Subclass>
+void AstTraversalVisitor<Subclass>::VisitRewritableExpression(
+    RewritableExpression* expr) {
+  PROCESS_EXPRESSION(expr);
+  RECURSE(Visit(expr->expression()));
+}
+
+#undef PROCESS_NODE
+#undef PROCESS_EXPRESSION
+#undef RECURSE_EXPRESSION
+#undef RECURSE
+
+}  // namespace internal
+}  // namespace v8
+
+#endif  // V8_AST_AST_TRAVERSAL_VISITOR_H_