Line data Source code
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 :
34 : void Run() {
35 : DCHECK_NOT_NULL(root_);
36 32010 : 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 669191 : 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>
92 : AstTraversalVisitor<Subclass>::AstTraversalVisitor(Isolate* isolate,
93 : AstNode* root)
94 1618 : : root_(root), depth_(0) {
95 : InitializeAstVisitor(isolate);
96 : }
97 :
98 : template <class Subclass>
99 : AstTraversalVisitor<Subclass>::AstTraversalVisitor(uintptr_t stack_limit,
100 : AstNode* root)
101 32309 : : root_(root), depth_(0) {
102 : InitializeAstVisitor(stack_limit);
103 : }
104 :
105 : template <class Subclass>
106 5179 : void AstTraversalVisitor<Subclass>::VisitDeclarations(
107 4964 : Declaration::List* decls) {
108 15322 : for (Declaration* decl : *decls) {
109 15107 : RECURSE(Visit(decl));
110 : }
111 : }
112 :
113 : template <class Subclass>
114 12248 : void AstTraversalVisitor<Subclass>::VisitStatements(
115 23568 : ZoneList<Statement*>* stmts) {
116 62774 : for (int i = 0; i < stmts->length(); ++i) {
117 54955 : Statement* stmt = stmts->at(i);
118 59384 : RECURSE(Visit(stmt));
119 23568 : if (stmt->IsJump()) break;
120 : }
121 : }
122 :
123 : template <class Subclass>
124 : void AstTraversalVisitor<Subclass>::VisitVariableDeclaration(
125 : VariableDeclaration* decl) {
126 : PROCESS_NODE(decl);
127 : }
128 :
129 : template <class Subclass>
130 2198 : void AstTraversalVisitor<Subclass>::VisitFunctionDeclaration(
131 2198 : FunctionDeclaration* decl) {
132 : PROCESS_NODE(decl);
133 2198 : RECURSE(Visit(decl->fun()));
134 : }
135 :
136 : template <class Subclass>
137 6185 : void AstTraversalVisitor<Subclass>::VisitBlock(Block* stmt) {
138 : PROCESS_NODE(stmt);
139 6621 : RECURSE(VisitStatements(stmt->statements()));
140 : }
141 :
142 : template <class Subclass>
143 13611 : void AstTraversalVisitor<Subclass>::VisitExpressionStatement(
144 13611 : ExpressionStatement* stmt) {
145 : PROCESS_NODE(stmt);
146 13611 : RECURSE(Visit(stmt->expression()));
147 : }
148 :
149 : template <class Subclass>
150 : void AstTraversalVisitor<Subclass>::VisitEmptyStatement(EmptyStatement* stmt) {}
151 :
152 : template <class Subclass>
153 0 : void AstTraversalVisitor<Subclass>::VisitSloppyBlockFunctionStatement(
154 0 : SloppyBlockFunctionStatement* stmt) {
155 : PROCESS_NODE(stmt);
156 0 : RECURSE(Visit(stmt->statement()));
157 : }
158 :
159 : template <class Subclass>
160 5560 : void AstTraversalVisitor<Subclass>::VisitIfStatement(IfStatement* stmt) {
161 : PROCESS_NODE(stmt);
162 2224 : RECURSE(Visit(stmt->condition()));
163 2224 : RECURSE(Visit(stmt->then_statement()));
164 1112 : RECURSE(Visit(stmt->else_statement()));
165 : }
166 :
167 : template <class Subclass>
168 : void AstTraversalVisitor<Subclass>::VisitContinueStatement(
169 : ContinueStatement* stmt) {
170 : PROCESS_NODE(stmt);
171 : }
172 :
173 : template <class Subclass>
174 : void AstTraversalVisitor<Subclass>::VisitBreakStatement(BreakStatement* stmt) {
175 : PROCESS_NODE(stmt);
176 : }
177 :
178 : template <class Subclass>
179 4535 : void AstTraversalVisitor<Subclass>::VisitReturnStatement(
180 4535 : ReturnStatement* stmt) {
181 : PROCESS_NODE(stmt);
182 4535 : RECURSE(Visit(stmt->expression()));
183 : }
184 :
185 : template <class Subclass>
186 0 : void AstTraversalVisitor<Subclass>::VisitWithStatement(WithStatement* stmt) {
187 : PROCESS_NODE(stmt);
188 0 : RECURSE(Visit(stmt->expression()));
189 0 : RECURSE(Visit(stmt->statement()));
190 : }
191 :
192 : template <class Subclass>
193 112 : void AstTraversalVisitor<Subclass>::VisitSwitchStatement(
194 1120 : SwitchStatement* stmt) {
195 : PROCESS_NODE(stmt);
196 224 : RECURSE(Visit(stmt->tag()));
197 :
198 : ZoneList<CaseClause*>* clauses = stmt->cases();
199 1120 : for (int i = 0; i < clauses->length(); ++i) {
200 1456 : CaseClause* clause = clauses->at(i);
201 448 : if (!clause->is_default()) {
202 336 : Expression* label = clause->label();
203 672 : RECURSE(Visit(label));
204 : }
205 : ZoneList<Statement*>* stmts = clause->statements();
206 896 : RECURSE(VisitStatements(stmts));
207 : }
208 : }
209 :
210 : template <class Subclass>
211 0 : void AstTraversalVisitor<Subclass>::VisitCaseClause(CaseClause* clause) {
212 0 : UNREACHABLE();
213 : }
214 :
215 : template <class Subclass>
216 0 : void AstTraversalVisitor<Subclass>::VisitDoWhileStatement(
217 0 : DoWhileStatement* stmt) {
218 : PROCESS_NODE(stmt);
219 0 : RECURSE(Visit(stmt->body()));
220 0 : RECURSE(Visit(stmt->cond()));
221 : }
222 :
223 : template <class Subclass>
224 0 : void AstTraversalVisitor<Subclass>::VisitWhileStatement(WhileStatement* stmt) {
225 : PROCESS_NODE(stmt);
226 0 : RECURSE(Visit(stmt->cond()));
227 0 : RECURSE(Visit(stmt->body()));
228 : }
229 :
230 : template <class Subclass>
231 2184 : void AstTraversalVisitor<Subclass>::VisitForStatement(ForStatement* stmt) {
232 : PROCESS_NODE(stmt);
233 364 : if (stmt->init() != NULL) {
234 728 : RECURSE(Visit(stmt->init()));
235 : }
236 364 : if (stmt->cond() != NULL) {
237 728 : RECURSE(Visit(stmt->cond()));
238 : }
239 364 : if (stmt->next() != NULL) {
240 728 : RECURSE(Visit(stmt->next()));
241 : }
242 364 : RECURSE(Visit(stmt->body()));
243 : }
244 :
245 : template <class Subclass>
246 0 : void AstTraversalVisitor<Subclass>::VisitForInStatement(ForInStatement* stmt) {
247 : PROCESS_NODE(stmt);
248 0 : RECURSE(Visit(stmt->enumerable()));
249 0 : RECURSE(Visit(stmt->body()));
250 : }
251 :
252 : template <class Subclass>
253 256 : void AstTraversalVisitor<Subclass>::VisitForOfStatement(ForOfStatement* stmt) {
254 : PROCESS_NODE(stmt);
255 64 : RECURSE(Visit(stmt->assign_iterator()));
256 64 : RECURSE(Visit(stmt->next_result()));
257 64 : RECURSE(Visit(stmt->result_done()));
258 64 : RECURSE(Visit(stmt->assign_each()));
259 32 : RECURSE(Visit(stmt->body()));
260 : }
261 :
262 : template <class Subclass>
263 537 : void AstTraversalVisitor<Subclass>::VisitTryCatchStatement(
264 1074 : TryCatchStatement* stmt) {
265 : PROCESS_NODE(stmt);
266 1074 : RECURSE(Visit(stmt->try_block()));
267 537 : RECURSE(Visit(stmt->catch_block()));
268 : }
269 :
270 : template <class Subclass>
271 218 : void AstTraversalVisitor<Subclass>::VisitTryFinallyStatement(
272 436 : TryFinallyStatement* stmt) {
273 : PROCESS_NODE(stmt);
274 436 : RECURSE(Visit(stmt->try_block()));
275 218 : RECURSE(Visit(stmt->finally_block()));
276 : }
277 :
278 : template <class Subclass>
279 : void AstTraversalVisitor<Subclass>::VisitDebuggerStatement(
280 : DebuggerStatement* stmt) {
281 : PROCESS_NODE(stmt);
282 : }
283 :
284 : template <class Subclass>
285 5179 : void AstTraversalVisitor<Subclass>::VisitFunctionLiteral(
286 20716 : FunctionLiteral* expr) {
287 : PROCESS_EXPRESSION(expr);
288 : DeclarationScope* scope = expr->scope();
289 10358 : RECURSE_EXPRESSION(VisitDeclarations(scope->declarations()));
290 : // A lazily parsed function literal won't have a body.
291 5179 : if (expr->scope()->was_lazily_parsed()) return;
292 10358 : RECURSE_EXPRESSION(VisitStatements(expr->body()));
293 : }
294 :
295 : template <class Subclass>
296 : void AstTraversalVisitor<Subclass>::VisitNativeFunctionLiteral(
297 : NativeFunctionLiteral* expr) {
298 : PROCESS_EXPRESSION(expr);
299 : }
300 :
301 : template <class Subclass>
302 436 : void AstTraversalVisitor<Subclass>::VisitDoExpression(DoExpression* expr) {
303 : PROCESS_EXPRESSION(expr);
304 0 : RECURSE(VisitBlock(expr->block()));
305 0 : RECURSE(VisitVariableProxy(expr->result()));
306 : }
307 :
308 : template <class Subclass>
309 6660 : void AstTraversalVisitor<Subclass>::VisitConditional(Conditional* expr) {
310 : PROCESS_EXPRESSION(expr);
311 3330 : RECURSE_EXPRESSION(Visit(expr->condition()));
312 3330 : RECURSE_EXPRESSION(Visit(expr->then_expression()));
313 2220 : RECURSE_EXPRESSION(Visit(expr->else_expression()));
314 : }
315 :
316 : template <class Subclass>
317 : void AstTraversalVisitor<Subclass>::VisitVariableProxy(VariableProxy* expr) {
318 : PROCESS_EXPRESSION(expr);
319 : }
320 :
321 : template <class Subclass>
322 : void AstTraversalVisitor<Subclass>::VisitLiteral(Literal* expr) {
323 : PROCESS_EXPRESSION(expr);
324 : }
325 :
326 : template <class Subclass>
327 : void AstTraversalVisitor<Subclass>::VisitRegExpLiteral(RegExpLiteral* expr) {
328 : PROCESS_EXPRESSION(expr);
329 : }
330 :
331 : template <class Subclass>
332 4164 : void AstTraversalVisitor<Subclass>::VisitObjectLiteral(ObjectLiteral* expr) {
333 : PROCESS_EXPRESSION(expr);
334 : ZoneList<ObjectLiteralProperty*>* props = expr->properties();
335 5628 : for (int i = 0; i < props->length(); ++i) {
336 4164 : ObjectLiteralProperty* prop = props->at(i);
337 4050 : RECURSE_EXPRESSION(Visit(prop->key()));
338 4050 : RECURSE_EXPRESSION(Visit(prop->value()));
339 : }
340 : }
341 :
342 : template <class Subclass>
343 3859 : void AstTraversalVisitor<Subclass>::VisitArrayLiteral(ArrayLiteral* expr) {
344 : PROCESS_EXPRESSION(expr);
345 : ZoneList<Expression*>* values = expr->values();
346 7718 : for (int i = 0; i < values->length(); ++i) {
347 6066 : Expression* value = values->at(i);
348 4414 : RECURSE_EXPRESSION(Visit(value));
349 : }
350 : }
351 :
352 : template <class Subclass>
353 32816 : void AstTraversalVisitor<Subclass>::VisitAssignment(Assignment* expr) {
354 : PROCESS_EXPRESSION(expr);
355 24612 : RECURSE_EXPRESSION(Visit(expr->target()));
356 16408 : RECURSE_EXPRESSION(Visit(expr->value()));
357 : }
358 :
359 : template <class Subclass>
360 1008 : void AstTraversalVisitor<Subclass>::VisitSuspend(Suspend* expr) {
361 : PROCESS_EXPRESSION(expr);
362 756 : RECURSE_EXPRESSION(Visit(expr->generator_object()));
363 504 : RECURSE_EXPRESSION(Visit(expr->expression()));
364 : }
365 :
366 : template <class Subclass>
367 570 : void AstTraversalVisitor<Subclass>::VisitThrow(Throw* expr) {
368 : PROCESS_EXPRESSION(expr);
369 570 : RECURSE_EXPRESSION(Visit(expr->exception()));
370 : }
371 :
372 : template <class Subclass>
373 23808 : void AstTraversalVisitor<Subclass>::VisitProperty(Property* expr) {
374 : PROCESS_EXPRESSION(expr);
375 17856 : RECURSE_EXPRESSION(Visit(expr->obj()));
376 11904 : RECURSE_EXPRESSION(Visit(expr->key()));
377 : }
378 :
379 : template <class Subclass>
380 48054 : void AstTraversalVisitor<Subclass>::VisitCall(Call* expr) {
381 : PROCESS_EXPRESSION(expr);
382 29346 : RECURSE_EXPRESSION(Visit(expr->expression()));
383 : ZoneList<Expression*>* args = expr->arguments();
384 37416 : for (int i = 0; i < args->length(); ++i) {
385 27634 : Expression* arg = args->at(i);
386 17852 : RECURSE_EXPRESSION(Visit(arg));
387 : }
388 : }
389 :
390 : template <class Subclass>
391 728 : void AstTraversalVisitor<Subclass>::VisitCallNew(CallNew* expr) {
392 : PROCESS_EXPRESSION(expr);
393 483 : RECURSE_EXPRESSION(Visit(expr->expression()));
394 : ZoneList<Expression*>* args = expr->arguments();
395 490 : for (int i = 0; i < args->length(); ++i) {
396 329 : Expression* arg = args->at(i);
397 168 : RECURSE_EXPRESSION(Visit(arg));
398 : }
399 : }
400 :
401 : template <class Subclass>
402 6104 : void AstTraversalVisitor<Subclass>::VisitCallRuntime(CallRuntime* expr) {
403 : PROCESS_EXPRESSION(expr);
404 : ZoneList<Expression*>* args = expr->arguments();
405 12208 : for (int i = 0; i < args->length(); ++i) {
406 10233 : Expression* arg = args->at(i);
407 8258 : RECURSE_EXPRESSION(Visit(arg));
408 : }
409 : }
410 :
411 : template <class Subclass>
412 924 : void AstTraversalVisitor<Subclass>::VisitUnaryOperation(UnaryOperation* expr) {
413 : PROCESS_EXPRESSION(expr);
414 924 : RECURSE_EXPRESSION(Visit(expr->expression()));
415 : }
416 :
417 : template <class Subclass>
418 1834 : void AstTraversalVisitor<Subclass>::VisitCountOperation(CountOperation* expr) {
419 : PROCESS_EXPRESSION(expr);
420 1834 : RECURSE_EXPRESSION(Visit(expr->expression()));
421 : }
422 :
423 : template <class Subclass>
424 1578 : void AstTraversalVisitor<Subclass>::VisitBinaryOperation(
425 4734 : BinaryOperation* expr) {
426 : PROCESS_EXPRESSION(expr);
427 4734 : RECURSE_EXPRESSION(Visit(expr->left()));
428 3156 : RECURSE_EXPRESSION(Visit(expr->right()));
429 : }
430 :
431 : template <class Subclass>
432 2560 : void AstTraversalVisitor<Subclass>::VisitCompareOperation(
433 7680 : CompareOperation* expr) {
434 : PROCESS_EXPRESSION(expr);
435 7680 : RECURSE_EXPRESSION(Visit(expr->left()));
436 5120 : RECURSE_EXPRESSION(Visit(expr->right()));
437 : }
438 :
439 : template <class Subclass>
440 : void AstTraversalVisitor<Subclass>::VisitThisFunction(ThisFunction* expr) {
441 : PROCESS_EXPRESSION(expr);
442 : }
443 :
444 : template <class Subclass>
445 308 : void AstTraversalVisitor<Subclass>::VisitClassLiteral(ClassLiteral* expr) {
446 : PROCESS_EXPRESSION(expr);
447 63 : if (expr->extends() != nullptr) {
448 14 : RECURSE_EXPRESSION(Visit(expr->extends()));
449 : }
450 189 : RECURSE_EXPRESSION(Visit(expr->constructor()));
451 : ZoneList<ClassLiteralProperty*>* props = expr->properties();
452 196 : for (int i = 0; i < props->length(); ++i) {
453 133 : ClassLiteralProperty* prop = props->at(i);
454 119 : if (!prop->key()->IsLiteral()) {
455 42 : RECURSE_EXPRESSION(Visit(prop->key()));
456 : }
457 105 : RECURSE_EXPRESSION(Visit(prop->value()));
458 : }
459 : }
460 :
461 : template <class Subclass>
462 0 : void AstTraversalVisitor<Subclass>::VisitSpread(Spread* expr) {
463 : PROCESS_EXPRESSION(expr);
464 0 : RECURSE_EXPRESSION(Visit(expr->expression()));
465 : }
466 :
467 : template <class Subclass>
468 : void AstTraversalVisitor<Subclass>::VisitEmptyParentheses(
469 : EmptyParentheses* expr) {
470 : PROCESS_EXPRESSION(expr);
471 : }
472 :
473 : template <class Subclass>
474 100 : void AstTraversalVisitor<Subclass>::VisitGetIterator(GetIterator* expr) {
475 : PROCESS_EXPRESSION(expr);
476 100 : RECURSE_EXPRESSION(Visit(expr->iterable()));
477 : }
478 :
479 : template <class Subclass>
480 0 : void AstTraversalVisitor<Subclass>::VisitImportCallExpression(
481 0 : ImportCallExpression* expr) {
482 : PROCESS_EXPRESSION(expr);
483 0 : RECURSE_EXPRESSION(Visit(expr->argument()));
484 : }
485 :
486 : template <class Subclass>
487 13 : void AstTraversalVisitor<Subclass>::VisitSuperPropertyReference(
488 26 : SuperPropertyReference* expr) {
489 : PROCESS_EXPRESSION(expr);
490 26 : RECURSE_EXPRESSION(VisitVariableProxy(expr->this_var()));
491 26 : RECURSE_EXPRESSION(Visit(expr->home_object()));
492 : }
493 :
494 : template <class Subclass>
495 0 : void AstTraversalVisitor<Subclass>::VisitSuperCallReference(
496 13 : SuperCallReference* expr) {
497 : PROCESS_EXPRESSION(expr);
498 26 : RECURSE_EXPRESSION(VisitVariableProxy(expr->this_var()));
499 13 : RECURSE_EXPRESSION(VisitVariableProxy(expr->new_target_var()));
500 13 : RECURSE_EXPRESSION(VisitVariableProxy(expr->this_function_var()));
501 : }
502 :
503 : template <class Subclass>
504 0 : void AstTraversalVisitor<Subclass>::VisitRewritableExpression(
505 114 : RewritableExpression* expr) {
506 : PROCESS_EXPRESSION(expr);
507 114 : RECURSE(Visit(expr->expression()));
508 : }
509 :
510 : #undef PROCESS_NODE
511 : #undef PROCESS_EXPRESSION
512 : #undef RECURSE_EXPRESSION
513 : #undef RECURSE
514 :
515 : } // namespace internal
516 : } // namespace v8
517 :
518 : #endif // V8_AST_AST_TRAVERSAL_VISITOR_H_
|
