1// Copyright 2016 the V8 project authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#ifndef V8_AST_AST_TRAVERSAL_VISITOR_H_
6#define V8_AST_AST_TRAVERSAL_VISITOR_H_
7
8#include "src/ast/ast.h"
9#include "src/ast/scopes.h"
10
11namespace v8 {
12namespace internal {
13
14// ----------------------------------------------------------------------------
15// Traversal visitor
16// - fully traverses the entire AST.
17//
18// Sub-class should parametrize AstTraversalVisitor with itself, e.g.:
19//   class SpecificVisitor : public AstTraversalVisitor<SpecificVisitor> { ... }
20//
21// It invokes VisitNode on each AST node, before proceeding with its subtrees.
22// It invokes VisitExpression (after VisitNode) on each AST node that is an
23// expression, before proceeding with its subtrees.
24// It proceeds with the subtrees only if these two methods return true.
25// Sub-classes may override VisitNode and VisitExpressions, whose implementation
26// is dummy here.  Or they may override the specific Visit* methods.
27
28template <class Subclass>
29class AstTraversalVisitor : public AstVisitor<Subclass> {
30 public:
31  explicit AstTraversalVisitor(Isolate* isolate, AstNode* root = nullptr);
32  explicit AstTraversalVisitor(uintptr_t stack_limit, AstNode* root = nullptr);
33
34  void Run() {
35    DCHECK_NOT_NULL(root_);
36    Visit(root_);
37  }
38
39  bool VisitNode(AstNode* node) { return true; }
40  bool VisitExpression(Expression* node) { return true; }
41
42  // Iteration left-to-right.
43  void VisitDeclarations(Declaration::List* declarations);
44  void VisitStatements(ZoneList<Statement*>* statements);
45
46// Individual nodes
47#define DECLARE_VISIT(type) void Visit##type(type* node);
48  AST_NODE_LIST(DECLARE_VISIT)
49#undef DECLARE_VISIT
50
51 protected:
52  int depth() const { return depth_; }
53
54 private:
55  DEFINE_AST_VISITOR_SUBCLASS_MEMBERS();
56
57  AstNode* root_;
58  int depth_;
59
60  DISALLOW_COPY_AND_ASSIGN(AstTraversalVisitor);
61};
62
63// ----------------------------------------------------------------------------
64// Implementation of AstTraversalVisitor
65
66#define PROCESS_NODE(node) do {                         \
67    if (!(this->impl()->VisitNode(node))) return;       \
68  } while (false)
69
70#define PROCESS_EXPRESSION(node) do {                           \
71    PROCESS_NODE(node);                                         \
72    if (!(this->impl()->VisitExpression(node))) return;         \
73  } while (false)
74
75#define RECURSE(call)               \
76  do {                              \
77    DCHECK(!HasStackOverflow());    \
78    this->impl()->call;             \
79    if (HasStackOverflow()) return; \
80  } while (false)
81
82#define RECURSE_EXPRESSION(call)    \
83  do {                              \
84    DCHECK(!HasStackOverflow());    \
85    ++depth_;                       \
86    this->impl()->call;             \
87    --depth_;                       \
88    if (HasStackOverflow()) return; \
89  } while (false)
90
91template <class Subclass>
92AstTraversalVisitor<Subclass>::AstTraversalVisitor(Isolate* isolate,
93                                                   AstNode* root)
94    : root_(root), depth_(0) {
95  InitializeAstVisitor(isolate);
96}
97
98template <class Subclass>
99AstTraversalVisitor<Subclass>::AstTraversalVisitor(uintptr_t stack_limit,
100                                                   AstNode* root)
101    : root_(root), depth_(0) {
102  InitializeAstVisitor(stack_limit);
103}
104
105template <class Subclass>
106void AstTraversalVisitor<Subclass>::VisitDeclarations(
107    Declaration::List* decls) {
108  for (Declaration* decl : *decls) {
109    RECURSE(Visit(decl));
110  }
111}
112
113template <class Subclass>
114void AstTraversalVisitor<Subclass>::VisitStatements(
115    ZoneList<Statement*>* stmts) {
116  for (int i = 0; i < stmts->length(); ++i) {
117    Statement* stmt = stmts->at(i);
118    RECURSE(Visit(stmt));
119    if (stmt->IsJump()) break;
120  }
121}
122
123template <class Subclass>
124void AstTraversalVisitor<Subclass>::VisitVariableDeclaration(
125    VariableDeclaration* decl) {
126  PROCESS_NODE(decl);
127}
128
129template <class Subclass>
130void AstTraversalVisitor<Subclass>::VisitFunctionDeclaration(
131    FunctionDeclaration* decl) {
132  PROCESS_NODE(decl);
133  RECURSE(Visit(decl->fun()));
134}
135
136template <class Subclass>
137void AstTraversalVisitor<Subclass>::VisitBlock(Block* stmt) {
138  PROCESS_NODE(stmt);
139  RECURSE(VisitStatements(stmt->statements()));
140}
141
142template <class Subclass>
143void AstTraversalVisitor<Subclass>::VisitExpressionStatement(
144    ExpressionStatement* stmt) {
145  PROCESS_NODE(stmt);
146  RECURSE(Visit(stmt->expression()));
147}
148
149template <class Subclass>
150void AstTraversalVisitor<Subclass>::VisitEmptyStatement(EmptyStatement* stmt) {}
151
152template <class Subclass>
153void AstTraversalVisitor<Subclass>::VisitSloppyBlockFunctionStatement(
154    SloppyBlockFunctionStatement* stmt) {
155  PROCESS_NODE(stmt);
156  RECURSE(Visit(stmt->statement()));
157}
158
159template <class Subclass>
160void AstTraversalVisitor<Subclass>::VisitIfStatement(IfStatement* stmt) {
161  PROCESS_NODE(stmt);
162  RECURSE(Visit(stmt->condition()));
163  RECURSE(Visit(stmt->then_statement()));
164  RECURSE(Visit(stmt->else_statement()));
165}
166
167template <class Subclass>
168void AstTraversalVisitor<Subclass>::VisitContinueStatement(
169    ContinueStatement* stmt) {
170  PROCESS_NODE(stmt);
171}
172
173template <class Subclass>
174void AstTraversalVisitor<Subclass>::VisitBreakStatement(BreakStatement* stmt) {
175  PROCESS_NODE(stmt);
176}
177
178template <class Subclass>
179void AstTraversalVisitor<Subclass>::VisitReturnStatement(
180    ReturnStatement* stmt) {
181  PROCESS_NODE(stmt);
182  RECURSE(Visit(stmt->expression()));
183}
184
185template <class Subclass>
186void AstTraversalVisitor<Subclass>::VisitWithStatement(WithStatement* stmt) {
187  PROCESS_NODE(stmt);
188  RECURSE(Visit(stmt->expression()));
189  RECURSE(Visit(stmt->statement()));
190}
191
192template <class Subclass>
193void AstTraversalVisitor<Subclass>::VisitSwitchStatement(
194    SwitchStatement* stmt) {
195  PROCESS_NODE(stmt);
196  RECURSE(Visit(stmt->tag()));
197
198  ZoneList<CaseClause*>* clauses = stmt->cases();
199  for (int i = 0; i < clauses->length(); ++i) {
200    CaseClause* clause = clauses->at(i);
201    if (!clause->is_default()) {
202      Expression* label = clause->label();
203      RECURSE(Visit(label));
204    }
205    ZoneList<Statement*>* stmts = clause->statements();
206    RECURSE(VisitStatements(stmts));
207  }
208}
209
210template <class Subclass>
211void AstTraversalVisitor<Subclass>::VisitCaseClause(CaseClause* clause) {
212  UNREACHABLE();
213}
214
215template <class Subclass>
216void AstTraversalVisitor<Subclass>::VisitDoWhileStatement(
217    DoWhileStatement* stmt) {
218  PROCESS_NODE(stmt);
219  RECURSE(Visit(stmt->body()));
220  RECURSE(Visit(stmt->cond()));
221}
222
223template <class Subclass>
224void AstTraversalVisitor<Subclass>::VisitWhileStatement(WhileStatement* stmt) {
225  PROCESS_NODE(stmt);
226  RECURSE(Visit(stmt->cond()));
227  RECURSE(Visit(stmt->body()));
228}
229
230template <class Subclass>
231void AstTraversalVisitor<Subclass>::VisitForStatement(ForStatement* stmt) {
232  PROCESS_NODE(stmt);
233  if (stmt->init() != NULL) {
234    RECURSE(Visit(stmt->init()));
235  }
236  if (stmt->cond() != NULL) {
237    RECURSE(Visit(stmt->cond()));
238  }
239  if (stmt->next() != NULL) {
240    RECURSE(Visit(stmt->next()));
241  }
242  RECURSE(Visit(stmt->body()));
243}
244
245template <class Subclass>
246void AstTraversalVisitor<Subclass>::VisitForInStatement(ForInStatement* stmt) {
247  PROCESS_NODE(stmt);
248  RECURSE(Visit(stmt->enumerable()));
249  RECURSE(Visit(stmt->body()));
250}
251
252template <class Subclass>
253void AstTraversalVisitor<Subclass>::VisitForOfStatement(ForOfStatement* stmt) {
254  PROCESS_NODE(stmt);
255  RECURSE(Visit(stmt->assign_iterator()));
256  RECURSE(Visit(stmt->next_result()));
257  RECURSE(Visit(stmt->result_done()));
258  RECURSE(Visit(stmt->assign_each()));
259  RECURSE(Visit(stmt->body()));
260}
261
262template <class Subclass>
263void AstTraversalVisitor<Subclass>::VisitTryCatchStatement(
264    TryCatchStatement* stmt) {
265  PROCESS_NODE(stmt);
266  RECURSE(Visit(stmt->try_block()));
267  RECURSE(Visit(stmt->catch_block()));
268}
269
270template <class Subclass>
271void AstTraversalVisitor<Subclass>::VisitTryFinallyStatement(
272    TryFinallyStatement* stmt) {
273  PROCESS_NODE(stmt);
274  RECURSE(Visit(stmt->try_block()));
275  RECURSE(Visit(stmt->finally_block()));
276}
277
278template <class Subclass>
279void AstTraversalVisitor<Subclass>::VisitDebuggerStatement(
280    DebuggerStatement* stmt) {
281  PROCESS_NODE(stmt);
282}
283
284template <class Subclass>
285void AstTraversalVisitor<Subclass>::VisitFunctionLiteral(
286    FunctionLiteral* expr) {
287  PROCESS_EXPRESSION(expr);
288  DeclarationScope* scope = expr->scope();
289  RECURSE_EXPRESSION(VisitDeclarations(scope->declarations()));
290  // A lazily parsed function literal won't have a body.
291  if (expr->scope()->is_lazily_parsed()) return;
292  RECURSE_EXPRESSION(VisitStatements(expr->body()));
293}
294
295template <class Subclass>
296void AstTraversalVisitor<Subclass>::VisitNativeFunctionLiteral(
297    NativeFunctionLiteral* expr) {
298  PROCESS_EXPRESSION(expr);
299}
300
301template <class Subclass>
302void AstTraversalVisitor<Subclass>::VisitDoExpression(DoExpression* expr) {
303  PROCESS_EXPRESSION(expr);
304  RECURSE(VisitBlock(expr->block()));
305  RECURSE(VisitVariableProxy(expr->result()));
306}
307
308template <class Subclass>
309void AstTraversalVisitor<Subclass>::VisitConditional(Conditional* expr) {
310  PROCESS_EXPRESSION(expr);
311  RECURSE_EXPRESSION(Visit(expr->condition()));
312  RECURSE_EXPRESSION(Visit(expr->then_expression()));
313  RECURSE_EXPRESSION(Visit(expr->else_expression()));
314}
315
316template <class Subclass>
317void AstTraversalVisitor<Subclass>::VisitVariableProxy(VariableProxy* expr) {
318  PROCESS_EXPRESSION(expr);
319}
320
321template <class Subclass>
322void AstTraversalVisitor<Subclass>::VisitLiteral(Literal* expr) {
323  PROCESS_EXPRESSION(expr);
324}
325
326template <class Subclass>
327void AstTraversalVisitor<Subclass>::VisitRegExpLiteral(RegExpLiteral* expr) {
328  PROCESS_EXPRESSION(expr);
329}
330
331template <class Subclass>
332void AstTraversalVisitor<Subclass>::VisitObjectLiteral(ObjectLiteral* expr) {
333  PROCESS_EXPRESSION(expr);
334  ZoneList<ObjectLiteralProperty*>* props = expr->properties();
335  for (int i = 0; i < props->length(); ++i) {
336    ObjectLiteralProperty* prop = props->at(i);
337    RECURSE_EXPRESSION(Visit(prop->key()));
338    RECURSE_EXPRESSION(Visit(prop->value()));
339  }
340}
341
342template <class Subclass>
343void AstTraversalVisitor<Subclass>::VisitArrayLiteral(ArrayLiteral* expr) {
344  PROCESS_EXPRESSION(expr);
345  ZoneList<Expression*>* values = expr->values();
346  for (int i = 0; i < values->length(); ++i) {
347    Expression* value = values->at(i);
348    RECURSE_EXPRESSION(Visit(value));
349  }
350}
351
352template <class Subclass>
353void AstTraversalVisitor<Subclass>::VisitAssignment(Assignment* expr) {
354  PROCESS_EXPRESSION(expr);
355  RECURSE_EXPRESSION(Visit(expr->target()));
356  RECURSE_EXPRESSION(Visit(expr->value()));
357}
358
359template <class Subclass>
360void AstTraversalVisitor<Subclass>::VisitYield(Yield* expr) {
361  PROCESS_EXPRESSION(expr);
362  RECURSE_EXPRESSION(Visit(expr->generator_object()));
363  RECURSE_EXPRESSION(Visit(expr->expression()));
364}
365
366template <class Subclass>
367void AstTraversalVisitor<Subclass>::VisitThrow(Throw* expr) {
368  PROCESS_EXPRESSION(expr);
369  RECURSE_EXPRESSION(Visit(expr->exception()));
370}
371
372template <class Subclass>
373void AstTraversalVisitor<Subclass>::VisitProperty(Property* expr) {
374  PROCESS_EXPRESSION(expr);
375  RECURSE_EXPRESSION(Visit(expr->obj()));
376  RECURSE_EXPRESSION(Visit(expr->key()));
377}
378
379template <class Subclass>
380void AstTraversalVisitor<Subclass>::VisitCall(Call* expr) {
381  PROCESS_EXPRESSION(expr);
382  RECURSE_EXPRESSION(Visit(expr->expression()));
383  ZoneList<Expression*>* args = expr->arguments();
384  for (int i = 0; i < args->length(); ++i) {
385    Expression* arg = args->at(i);
386    RECURSE_EXPRESSION(Visit(arg));
387  }
388}
389
390template <class Subclass>
391void AstTraversalVisitor<Subclass>::VisitCallNew(CallNew* expr) {
392  PROCESS_EXPRESSION(expr);
393  RECURSE_EXPRESSION(Visit(expr->expression()));
394  ZoneList<Expression*>* args = expr->arguments();
395  for (int i = 0; i < args->length(); ++i) {
396    Expression* arg = args->at(i);
397    RECURSE_EXPRESSION(Visit(arg));
398  }
399}
400
401template <class Subclass>
402void AstTraversalVisitor<Subclass>::VisitCallRuntime(CallRuntime* expr) {
403  PROCESS_EXPRESSION(expr);
404  ZoneList<Expression*>* args = expr->arguments();
405  for (int i = 0; i < args->length(); ++i) {
406    Expression* arg = args->at(i);
407    RECURSE_EXPRESSION(Visit(arg));
408  }
409}
410
411template <class Subclass>
412void AstTraversalVisitor<Subclass>::VisitUnaryOperation(UnaryOperation* expr) {
413  PROCESS_EXPRESSION(expr);
414  RECURSE_EXPRESSION(Visit(expr->expression()));
415}
416
417template <class Subclass>
418void AstTraversalVisitor<Subclass>::VisitCountOperation(CountOperation* expr) {
419  PROCESS_EXPRESSION(expr);
420  RECURSE_EXPRESSION(Visit(expr->expression()));
421}
422
423template <class Subclass>
424void AstTraversalVisitor<Subclass>::VisitBinaryOperation(
425    BinaryOperation* expr) {
426  PROCESS_EXPRESSION(expr);
427  RECURSE_EXPRESSION(Visit(expr->left()));
428  RECURSE_EXPRESSION(Visit(expr->right()));
429}
430
431template <class Subclass>
432void AstTraversalVisitor<Subclass>::VisitCompareOperation(
433    CompareOperation* expr) {
434  PROCESS_EXPRESSION(expr);
435  RECURSE_EXPRESSION(Visit(expr->left()));
436  RECURSE_EXPRESSION(Visit(expr->right()));
437}
438
439template <class Subclass>
440void AstTraversalVisitor<Subclass>::VisitThisFunction(ThisFunction* expr) {
441  PROCESS_EXPRESSION(expr);
442}
443
444template <class Subclass>
445void AstTraversalVisitor<Subclass>::VisitClassLiteral(ClassLiteral* expr) {
446  PROCESS_EXPRESSION(expr);
447  if (expr->extends() != nullptr) {
448    RECURSE_EXPRESSION(Visit(expr->extends()));
449  }
450  RECURSE_EXPRESSION(Visit(expr->constructor()));
451  ZoneList<ClassLiteralProperty*>* props = expr->properties();
452  for (int i = 0; i < props->length(); ++i) {
453    ClassLiteralProperty* prop = props->at(i);
454    if (!prop->key()->IsLiteral()) {
455      RECURSE_EXPRESSION(Visit(prop->key()));
456    }
457    RECURSE_EXPRESSION(Visit(prop->value()));
458  }
459}
460
461template <class Subclass>
462void AstTraversalVisitor<Subclass>::VisitSpread(Spread* expr) {
463  PROCESS_EXPRESSION(expr);
464  RECURSE_EXPRESSION(Visit(expr->expression()));
465}
466
467template <class Subclass>
468void AstTraversalVisitor<Subclass>::VisitEmptyParentheses(
469    EmptyParentheses* expr) {
470  PROCESS_EXPRESSION(expr);
471}
472
473template <class Subclass>
474void AstTraversalVisitor<Subclass>::VisitSuperPropertyReference(
475    SuperPropertyReference* expr) {
476  PROCESS_EXPRESSION(expr);
477  RECURSE_EXPRESSION(VisitVariableProxy(expr->this_var()));
478  RECURSE_EXPRESSION(Visit(expr->home_object()));
479}
480
481template <class Subclass>
482void AstTraversalVisitor<Subclass>::VisitSuperCallReference(
483    SuperCallReference* expr) {
484  PROCESS_EXPRESSION(expr);
485  RECURSE_EXPRESSION(VisitVariableProxy(expr->this_var()));
486  RECURSE_EXPRESSION(VisitVariableProxy(expr->new_target_var()));
487  RECURSE_EXPRESSION(VisitVariableProxy(expr->this_function_var()));
488}
489
490template <class Subclass>
491void AstTraversalVisitor<Subclass>::VisitRewritableExpression(
492    RewritableExpression* expr) {
493  PROCESS_EXPRESSION(expr);
494  RECURSE(Visit(expr->expression()));
495}
496
497#undef PROCESS_NODE
498#undef PROCESS_EXPRESSION
499#undef RECURSE_EXPRESSION
500#undef RECURSE
501
502}  // namespace internal
503}  // namespace v8
504
505#endif  // V8_AST_AST_TRAVERSAL_VISITOR_H_
506