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 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 91 template <class Subclass> 92 AstTraversalVisitor<Subclass>::AstTraversalVisitor(Isolate* isolate, 93 AstNode* root) 94 : 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 : root_(root), depth_(0) { 102 InitializeAstVisitor(stack_limit); 103 } 104 105 template <class Subclass> 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> 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> 124 void AstTraversalVisitor<Subclass>::VisitVariableDeclaration( 125 VariableDeclaration* decl) { 126 PROCESS_NODE(decl); 127 } 128 129 template <class Subclass> 130 void AstTraversalVisitor<Subclass>::VisitFunctionDeclaration( 131 FunctionDeclaration* decl) { 132 PROCESS_NODE(decl); 133 RECURSE(Visit(decl->fun())); 134 } 135 136 template <class Subclass> 137 void AstTraversalVisitor<Subclass>::VisitBlock(Block* stmt) { 138 PROCESS_NODE(stmt); 139 RECURSE(VisitStatements(stmt->statements())); 140 } 141 142 template <class Subclass> 143 void AstTraversalVisitor<Subclass>::VisitExpressionStatement( 144 ExpressionStatement* stmt) { 145 PROCESS_NODE(stmt); 146 RECURSE(Visit(stmt->expression())); 147 } 148 149 template <class Subclass> 150 void AstTraversalVisitor<Subclass>::VisitEmptyStatement(EmptyStatement* stmt) {} 151 152 template <class Subclass> 153 void AstTraversalVisitor<Subclass>::VisitSloppyBlockFunctionStatement( 154 SloppyBlockFunctionStatement* stmt) { 155 PROCESS_NODE(stmt); 156 RECURSE(Visit(stmt->statement())); 157 } 158 159 template <class Subclass> 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> 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 void AstTraversalVisitor<Subclass>::VisitReturnStatement( 180 ReturnStatement* stmt) { 181 PROCESS_NODE(stmt); 182 RECURSE(Visit(stmt->expression())); 183 } 184 185 template <class Subclass> 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> 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> 211 void AstTraversalVisitor<Subclass>::VisitCaseClause(CaseClause* clause) { 212 UNREACHABLE(); 213 } 214 215 template <class Subclass> 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> 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> 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> 246 void AstTraversalVisitor<Subclass>::VisitForInStatement(ForInStatement* stmt) { 247 PROCESS_NODE(stmt); 248 RECURSE(Visit(stmt->enumerable())); 249 RECURSE(Visit(stmt->body())); 250 } 251 252 template <class Subclass> 253 void 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 262 template <class Subclass> 263 void AstTraversalVisitor<Subclass>::VisitTryCatchStatement( 264 TryCatchStatement* stmt) { 265 PROCESS_NODE(stmt); 266 RECURSE(Visit(stmt->try_block())); 267 RECURSE(Visit(stmt->catch_block())); 268 } 269 270 template <class Subclass> 271 void AstTraversalVisitor<Subclass>::VisitTryFinallyStatement( 272 TryFinallyStatement* stmt) { 273 PROCESS_NODE(stmt); 274 RECURSE(Visit(stmt->try_block())); 275 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 void 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()->was_lazily_parsed()) return; 292 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 void AstTraversalVisitor<Subclass>::VisitDoExpression(DoExpression* expr) { 303 PROCESS_EXPRESSION(expr); 304 RECURSE(VisitBlock(expr->block())); 305 RECURSE(VisitVariableProxy(expr->result())); 306 } 307 308 template <class Subclass> 309 void 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 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 void 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 342 template <class Subclass> 343 void 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 352 template <class Subclass> 353 void AstTraversalVisitor<Subclass>::VisitAssignment(Assignment* expr) { 354 PROCESS_EXPRESSION(expr); 355 RECURSE_EXPRESSION(Visit(expr->target())); 356 RECURSE_EXPRESSION(Visit(expr->value())); 357 } 358 359 template <class Subclass> 360 void AstTraversalVisitor<Subclass>::VisitYield(Yield* expr) { 361 PROCESS_EXPRESSION(expr); 362 RECURSE_EXPRESSION(Visit(expr->generator_object())); 363 RECURSE_EXPRESSION(Visit(expr->expression())); 364 } 365 366 template <class Subclass> 367 void AstTraversalVisitor<Subclass>::VisitThrow(Throw* expr) { 368 PROCESS_EXPRESSION(expr); 369 RECURSE_EXPRESSION(Visit(expr->exception())); 370 } 371 372 template <class Subclass> 373 void AstTraversalVisitor<Subclass>::VisitProperty(Property* expr) { 374 PROCESS_EXPRESSION(expr); 375 RECURSE_EXPRESSION(Visit(expr->obj())); 376 RECURSE_EXPRESSION(Visit(expr->key())); 377 } 378 379 template <class Subclass> 380 void 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 390 template <class Subclass> 391 void 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 401 template <class Subclass> 402 void 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 411 template <class Subclass> 412 void AstTraversalVisitor<Subclass>::VisitUnaryOperation(UnaryOperation* expr) { 413 PROCESS_EXPRESSION(expr); 414 RECURSE_EXPRESSION(Visit(expr->expression())); 415 } 416 417 template <class Subclass> 418 void AstTraversalVisitor<Subclass>::VisitCountOperation(CountOperation* expr) { 419 PROCESS_EXPRESSION(expr); 420 RECURSE_EXPRESSION(Visit(expr->expression())); 421 } 422 423 template <class Subclass> 424 void AstTraversalVisitor<Subclass>::VisitBinaryOperation( 425 BinaryOperation* expr) { 426 PROCESS_EXPRESSION(expr); 427 RECURSE_EXPRESSION(Visit(expr->left())); 428 RECURSE_EXPRESSION(Visit(expr->right())); 429 } 430 431 template <class Subclass> 432 void AstTraversalVisitor<Subclass>::VisitCompareOperation( 433 CompareOperation* expr) { 434 PROCESS_EXPRESSION(expr); 435 RECURSE_EXPRESSION(Visit(expr->left())); 436 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 void 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 461 template <class Subclass> 462 void AstTraversalVisitor<Subclass>::VisitSpread(Spread* expr) { 463 PROCESS_EXPRESSION(expr); 464 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 void AstTraversalVisitor<Subclass>::VisitGetIterator(GetIterator* expr) { 475 PROCESS_EXPRESSION(expr); 476 RECURSE_EXPRESSION(Visit(expr->iterable())); 477 } 478 479 template <class Subclass> 480 void AstTraversalVisitor<Subclass>::VisitSuperPropertyReference( 481 SuperPropertyReference* expr) { 482 PROCESS_EXPRESSION(expr); 483 RECURSE_EXPRESSION(VisitVariableProxy(expr->this_var())); 484 RECURSE_EXPRESSION(Visit(expr->home_object())); 485 } 486 487 template <class Subclass> 488 void AstTraversalVisitor<Subclass>::VisitSuperCallReference( 489 SuperCallReference* expr) { 490 PROCESS_EXPRESSION(expr); 491 RECURSE_EXPRESSION(VisitVariableProxy(expr->this_var())); 492 RECURSE_EXPRESSION(VisitVariableProxy(expr->new_target_var())); 493 RECURSE_EXPRESSION(VisitVariableProxy(expr->this_function_var())); 494 } 495 496 template <class Subclass> 497 void AstTraversalVisitor<Subclass>::VisitRewritableExpression( 498 RewritableExpression* expr) { 499 PROCESS_EXPRESSION(expr); 500 RECURSE(Visit(expr->expression())); 501 } 502 503 #undef PROCESS_NODE 504 #undef PROCESS_EXPRESSION 505 #undef RECURSE_EXPRESSION 506 #undef RECURSE 507 508 } // namespace internal 509 } // namespace v8 510 511 #endif // V8_AST_AST_TRAVERSAL_VISITOR_H_ 512
