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
11 namespace v8 {
12 namespace 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
28 template <class Subclass>
29 class 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
Run()34 void Run() {
35 DCHECK_NOT_NULL(root_);
36 Visit(root_);
37 }
38
VisitNode(AstNode * node)39 bool VisitNode(AstNode* node) { return true; }
VisitExpression(Expression * node)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);
AST_NODE_LIST(DECLARE_VISIT)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
91 template <class Subclass>
AstTraversalVisitor(Isolate * isolate,AstNode * root)92 AstTraversalVisitor<Subclass>::AstTraversalVisitor(Isolate* isolate,
93 AstNode* root)
94 : root_(root), depth_(0) {
95 InitializeAstVisitor(isolate);
96 }
97
98 template <class Subclass>
AstTraversalVisitor(uintptr_t stack_limit,AstNode * root)99 AstTraversalVisitor<Subclass>::AstTraversalVisitor(uintptr_t stack_limit,
100 AstNode* root)
101 : root_(root), depth_(0) {
102 InitializeAstVisitor(stack_limit);
103 }
104
105 template <class Subclass>
VisitDeclarations(Declaration::List * decls)106 void AstTraversalVisitor<Subclass>::VisitDeclarations(
107 Declaration::List* decls) {
108 for (Declaration* decl : *decls) {
109 RECURSE(Visit(decl));
110 }
111 }
112
113 template <class Subclass>
VisitStatements(ZoneList<Statement * > * stmts)114 void 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
123 template <class Subclass>
VisitVariableDeclaration(VariableDeclaration * decl)124 void AstTraversalVisitor<Subclass>::VisitVariableDeclaration(
125 VariableDeclaration* decl) {
126 PROCESS_NODE(decl);
127 }
128
129 template <class Subclass>
VisitFunctionDeclaration(FunctionDeclaration * decl)130 void AstTraversalVisitor<Subclass>::VisitFunctionDeclaration(
131 FunctionDeclaration* decl) {
132 PROCESS_NODE(decl);
133 RECURSE(Visit(decl->fun()));
134 }
135
136 template <class Subclass>
VisitBlock(Block * stmt)137 void AstTraversalVisitor<Subclass>::VisitBlock(Block* stmt) {
138 PROCESS_NODE(stmt);
139 RECURSE(VisitStatements(stmt->statements()));
140 }
141
142 template <class Subclass>
VisitExpressionStatement(ExpressionStatement * stmt)143 void AstTraversalVisitor<Subclass>::VisitExpressionStatement(
144 ExpressionStatement* stmt) {
145 PROCESS_NODE(stmt);
146 RECURSE(Visit(stmt->expression()));
147 }
148
149 template <class Subclass>
VisitEmptyStatement(EmptyStatement * stmt)150 void AstTraversalVisitor<Subclass>::VisitEmptyStatement(EmptyStatement* stmt) {}
151
152 template <class Subclass>
VisitSloppyBlockFunctionStatement(SloppyBlockFunctionStatement * stmt)153 void AstTraversalVisitor<Subclass>::VisitSloppyBlockFunctionStatement(
154 SloppyBlockFunctionStatement* stmt) {
155 PROCESS_NODE(stmt);
156 RECURSE(Visit(stmt->statement()));
157 }
158
159 template <class Subclass>
VisitIfStatement(IfStatement * stmt)160 void 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
167 template <class Subclass>
VisitContinueStatement(ContinueStatement * stmt)168 void AstTraversalVisitor<Subclass>::VisitContinueStatement(
169 ContinueStatement* stmt) {
170 PROCESS_NODE(stmt);
171 }
172
173 template <class Subclass>
VisitBreakStatement(BreakStatement * stmt)174 void AstTraversalVisitor<Subclass>::VisitBreakStatement(BreakStatement* stmt) {
175 PROCESS_NODE(stmt);
176 }
177
178 template <class Subclass>
VisitReturnStatement(ReturnStatement * stmt)179 void AstTraversalVisitor<Subclass>::VisitReturnStatement(
180 ReturnStatement* stmt) {
181 PROCESS_NODE(stmt);
182 RECURSE(Visit(stmt->expression()));
183 }
184
185 template <class Subclass>
VisitWithStatement(WithStatement * stmt)186 void AstTraversalVisitor<Subclass>::VisitWithStatement(WithStatement* stmt) {
187 PROCESS_NODE(stmt);
188 RECURSE(Visit(stmt->expression()));
189 RECURSE(Visit(stmt->statement()));
190 }
191
192 template <class Subclass>
VisitSwitchStatement(SwitchStatement * stmt)193 void 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
210 template <class Subclass>
VisitCaseClause(CaseClause * clause)211 void AstTraversalVisitor<Subclass>::VisitCaseClause(CaseClause* clause) {
212 UNREACHABLE();
213 }
214
215 template <class Subclass>
VisitDoWhileStatement(DoWhileStatement * stmt)216 void AstTraversalVisitor<Subclass>::VisitDoWhileStatement(
217 DoWhileStatement* stmt) {
218 PROCESS_NODE(stmt);
219 RECURSE(Visit(stmt->body()));
220 RECURSE(Visit(stmt->cond()));
221 }
222
223 template <class Subclass>
VisitWhileStatement(WhileStatement * stmt)224 void AstTraversalVisitor<Subclass>::VisitWhileStatement(WhileStatement* stmt) {
225 PROCESS_NODE(stmt);
226 RECURSE(Visit(stmt->cond()));
227 RECURSE(Visit(stmt->body()));
228 }
229
230 template <class Subclass>
VisitForStatement(ForStatement * stmt)231 void 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
245 template <class Subclass>
VisitForInStatement(ForInStatement * stmt)246 void AstTraversalVisitor<Subclass>::VisitForInStatement(ForInStatement* stmt) {
247 PROCESS_NODE(stmt);
248 RECURSE(Visit(stmt->each()));
249 RECURSE(Visit(stmt->enumerable()));
250 RECURSE(Visit(stmt->body()));
251 }
252
253 template <class Subclass>
VisitForOfStatement(ForOfStatement * stmt)254 void AstTraversalVisitor<Subclass>::VisitForOfStatement(ForOfStatement* stmt) {
255 PROCESS_NODE(stmt);
256 RECURSE(Visit(stmt->assign_iterator()));
257 RECURSE(Visit(stmt->next_result()));
258 RECURSE(Visit(stmt->result_done()));
259 RECURSE(Visit(stmt->assign_each()));
260 RECURSE(Visit(stmt->body()));
261 }
262
263 template <class Subclass>
VisitTryCatchStatement(TryCatchStatement * stmt)264 void AstTraversalVisitor<Subclass>::VisitTryCatchStatement(
265 TryCatchStatement* stmt) {
266 PROCESS_NODE(stmt);
267 RECURSE(Visit(stmt->try_block()));
268 RECURSE(Visit(stmt->catch_block()));
269 }
270
271 template <class Subclass>
VisitTryFinallyStatement(TryFinallyStatement * stmt)272 void AstTraversalVisitor<Subclass>::VisitTryFinallyStatement(
273 TryFinallyStatement* stmt) {
274 PROCESS_NODE(stmt);
275 RECURSE(Visit(stmt->try_block()));
276 RECURSE(Visit(stmt->finally_block()));
277 }
278
279 template <class Subclass>
VisitDebuggerStatement(DebuggerStatement * stmt)280 void AstTraversalVisitor<Subclass>::VisitDebuggerStatement(
281 DebuggerStatement* stmt) {
282 PROCESS_NODE(stmt);
283 }
284
285 template <class Subclass>
VisitFunctionLiteral(FunctionLiteral * expr)286 void AstTraversalVisitor<Subclass>::VisitFunctionLiteral(
287 FunctionLiteral* expr) {
288 PROCESS_EXPRESSION(expr);
289 DeclarationScope* scope = expr->scope();
290 RECURSE_EXPRESSION(VisitDeclarations(scope->declarations()));
291 // A lazily parsed function literal won't have a body.
292 if (expr->scope()->was_lazily_parsed()) return;
293 RECURSE_EXPRESSION(VisitStatements(expr->body()));
294 }
295
296 template <class Subclass>
VisitNativeFunctionLiteral(NativeFunctionLiteral * expr)297 void AstTraversalVisitor<Subclass>::VisitNativeFunctionLiteral(
298 NativeFunctionLiteral* expr) {
299 PROCESS_EXPRESSION(expr);
300 }
301
302 template <class Subclass>
VisitDoExpression(DoExpression * expr)303 void AstTraversalVisitor<Subclass>::VisitDoExpression(DoExpression* expr) {
304 PROCESS_EXPRESSION(expr);
305 RECURSE(VisitBlock(expr->block()));
306 RECURSE(VisitVariableProxy(expr->result()));
307 }
308
309 template <class Subclass>
VisitConditional(Conditional * expr)310 void AstTraversalVisitor<Subclass>::VisitConditional(Conditional* expr) {
311 PROCESS_EXPRESSION(expr);
312 RECURSE_EXPRESSION(Visit(expr->condition()));
313 RECURSE_EXPRESSION(Visit(expr->then_expression()));
314 RECURSE_EXPRESSION(Visit(expr->else_expression()));
315 }
316
317 template <class Subclass>
VisitVariableProxy(VariableProxy * expr)318 void AstTraversalVisitor<Subclass>::VisitVariableProxy(VariableProxy* expr) {
319 PROCESS_EXPRESSION(expr);
320 }
321
322 template <class Subclass>
VisitLiteral(Literal * expr)323 void AstTraversalVisitor<Subclass>::VisitLiteral(Literal* expr) {
324 PROCESS_EXPRESSION(expr);
325 }
326
327 template <class Subclass>
VisitRegExpLiteral(RegExpLiteral * expr)328 void AstTraversalVisitor<Subclass>::VisitRegExpLiteral(RegExpLiteral* expr) {
329 PROCESS_EXPRESSION(expr);
330 }
331
332 template <class Subclass>
VisitObjectLiteral(ObjectLiteral * expr)333 void AstTraversalVisitor<Subclass>::VisitObjectLiteral(ObjectLiteral* expr) {
334 PROCESS_EXPRESSION(expr);
335 ZoneList<ObjectLiteralProperty*>* props = expr->properties();
336 for (int i = 0; i < props->length(); ++i) {
337 ObjectLiteralProperty* prop = props->at(i);
338 RECURSE_EXPRESSION(Visit(prop->key()));
339 RECURSE_EXPRESSION(Visit(prop->value()));
340 }
341 }
342
343 template <class Subclass>
VisitArrayLiteral(ArrayLiteral * expr)344 void AstTraversalVisitor<Subclass>::VisitArrayLiteral(ArrayLiteral* expr) {
345 PROCESS_EXPRESSION(expr);
346 ZoneList<Expression*>* values = expr->values();
347 for (int i = 0; i < values->length(); ++i) {
348 Expression* value = values->at(i);
349 RECURSE_EXPRESSION(Visit(value));
350 }
351 }
352
353 template <class Subclass>
VisitAssignment(Assignment * expr)354 void AstTraversalVisitor<Subclass>::VisitAssignment(Assignment* expr) {
355 PROCESS_EXPRESSION(expr);
356 RECURSE_EXPRESSION(Visit(expr->target()));
357 RECURSE_EXPRESSION(Visit(expr->value()));
358 }
359
360 template <class Subclass>
VisitYield(Yield * expr)361 void AstTraversalVisitor<Subclass>::VisitYield(Yield* expr) {
362 PROCESS_EXPRESSION(expr);
363 RECURSE_EXPRESSION(Visit(expr->generator_object()));
364 RECURSE_EXPRESSION(Visit(expr->expression()));
365 }
366
367 template <class Subclass>
VisitThrow(Throw * expr)368 void AstTraversalVisitor<Subclass>::VisitThrow(Throw* expr) {
369 PROCESS_EXPRESSION(expr);
370 RECURSE_EXPRESSION(Visit(expr->exception()));
371 }
372
373 template <class Subclass>
VisitProperty(Property * expr)374 void AstTraversalVisitor<Subclass>::VisitProperty(Property* expr) {
375 PROCESS_EXPRESSION(expr);
376 RECURSE_EXPRESSION(Visit(expr->obj()));
377 RECURSE_EXPRESSION(Visit(expr->key()));
378 }
379
380 template <class Subclass>
VisitCall(Call * expr)381 void AstTraversalVisitor<Subclass>::VisitCall(Call* expr) {
382 PROCESS_EXPRESSION(expr);
383 RECURSE_EXPRESSION(Visit(expr->expression()));
384 ZoneList<Expression*>* args = expr->arguments();
385 for (int i = 0; i < args->length(); ++i) {
386 Expression* arg = args->at(i);
387 RECURSE_EXPRESSION(Visit(arg));
388 }
389 }
390
391 template <class Subclass>
VisitCallNew(CallNew * expr)392 void AstTraversalVisitor<Subclass>::VisitCallNew(CallNew* expr) {
393 PROCESS_EXPRESSION(expr);
394 RECURSE_EXPRESSION(Visit(expr->expression()));
395 ZoneList<Expression*>* args = expr->arguments();
396 for (int i = 0; i < args->length(); ++i) {
397 Expression* arg = args->at(i);
398 RECURSE_EXPRESSION(Visit(arg));
399 }
400 }
401
402 template <class Subclass>
VisitCallRuntime(CallRuntime * expr)403 void AstTraversalVisitor<Subclass>::VisitCallRuntime(CallRuntime* expr) {
404 PROCESS_EXPRESSION(expr);
405 ZoneList<Expression*>* args = expr->arguments();
406 for (int i = 0; i < args->length(); ++i) {
407 Expression* arg = args->at(i);
408 RECURSE_EXPRESSION(Visit(arg));
409 }
410 }
411
412 template <class Subclass>
VisitUnaryOperation(UnaryOperation * expr)413 void AstTraversalVisitor<Subclass>::VisitUnaryOperation(UnaryOperation* expr) {
414 PROCESS_EXPRESSION(expr);
415 RECURSE_EXPRESSION(Visit(expr->expression()));
416 }
417
418 template <class Subclass>
VisitCountOperation(CountOperation * expr)419 void AstTraversalVisitor<Subclass>::VisitCountOperation(CountOperation* expr) {
420 PROCESS_EXPRESSION(expr);
421 RECURSE_EXPRESSION(Visit(expr->expression()));
422 }
423
424 template <class Subclass>
VisitBinaryOperation(BinaryOperation * expr)425 void AstTraversalVisitor<Subclass>::VisitBinaryOperation(
426 BinaryOperation* expr) {
427 PROCESS_EXPRESSION(expr);
428 RECURSE_EXPRESSION(Visit(expr->left()));
429 RECURSE_EXPRESSION(Visit(expr->right()));
430 }
431
432 template <class Subclass>
VisitCompareOperation(CompareOperation * expr)433 void AstTraversalVisitor<Subclass>::VisitCompareOperation(
434 CompareOperation* expr) {
435 PROCESS_EXPRESSION(expr);
436 RECURSE_EXPRESSION(Visit(expr->left()));
437 RECURSE_EXPRESSION(Visit(expr->right()));
438 }
439
440 template <class Subclass>
VisitThisFunction(ThisFunction * expr)441 void AstTraversalVisitor<Subclass>::VisitThisFunction(ThisFunction* expr) {
442 PROCESS_EXPRESSION(expr);
443 }
444
445 template <class Subclass>
VisitClassLiteral(ClassLiteral * expr)446 void AstTraversalVisitor<Subclass>::VisitClassLiteral(ClassLiteral* expr) {
447 PROCESS_EXPRESSION(expr);
448 if (expr->extends() != nullptr) {
449 RECURSE_EXPRESSION(Visit(expr->extends()));
450 }
451 RECURSE_EXPRESSION(Visit(expr->constructor()));
452 ZoneList<ClassLiteralProperty*>* props = expr->properties();
453 for (int i = 0; i < props->length(); ++i) {
454 ClassLiteralProperty* prop = props->at(i);
455 if (!prop->key()->IsLiteral()) {
456 RECURSE_EXPRESSION(Visit(prop->key()));
457 }
458 RECURSE_EXPRESSION(Visit(prop->value()));
459 }
460 }
461
462 template <class Subclass>
VisitSpread(Spread * expr)463 void AstTraversalVisitor<Subclass>::VisitSpread(Spread* expr) {
464 PROCESS_EXPRESSION(expr);
465 RECURSE_EXPRESSION(Visit(expr->expression()));
466 }
467
468 template <class Subclass>
VisitEmptyParentheses(EmptyParentheses * expr)469 void AstTraversalVisitor<Subclass>::VisitEmptyParentheses(
470 EmptyParentheses* expr) {
471 PROCESS_EXPRESSION(expr);
472 }
473
474 template <class Subclass>
VisitGetIterator(GetIterator * expr)475 void AstTraversalVisitor<Subclass>::VisitGetIterator(GetIterator* expr) {
476 PROCESS_EXPRESSION(expr);
477 RECURSE_EXPRESSION(Visit(expr->iterable()));
478 }
479
480 template <class Subclass>
VisitSuperPropertyReference(SuperPropertyReference * expr)481 void AstTraversalVisitor<Subclass>::VisitSuperPropertyReference(
482 SuperPropertyReference* expr) {
483 PROCESS_EXPRESSION(expr);
484 RECURSE_EXPRESSION(VisitVariableProxy(expr->this_var()));
485 RECURSE_EXPRESSION(Visit(expr->home_object()));
486 }
487
488 template <class Subclass>
VisitSuperCallReference(SuperCallReference * expr)489 void AstTraversalVisitor<Subclass>::VisitSuperCallReference(
490 SuperCallReference* expr) {
491 PROCESS_EXPRESSION(expr);
492 RECURSE_EXPRESSION(VisitVariableProxy(expr->this_var()));
493 RECURSE_EXPRESSION(VisitVariableProxy(expr->new_target_var()));
494 RECURSE_EXPRESSION(VisitVariableProxy(expr->this_function_var()));
495 }
496
497 template <class Subclass>
VisitRewritableExpression(RewritableExpression * expr)498 void AstTraversalVisitor<Subclass>::VisitRewritableExpression(
499 RewritableExpression* expr) {
500 PROCESS_EXPRESSION(expr);
501 RECURSE(Visit(expr->expression()));
502 }
503
504 #undef PROCESS_NODE
505 #undef PROCESS_EXPRESSION
506 #undef RECURSE_EXPRESSION
507 #undef RECURSE
508
509 } // namespace internal
510 } // namespace v8
511
512 #endif // V8_AST_AST_TRAVERSAL_VISITOR_H_
513