1// Copyright 2012 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_SCOPES_H_ 6#define V8_SCOPES_H_ 7 8#include "src/ast.h" 9#include "src/zone.h" 10 11namespace v8 { 12namespace internal { 13 14class CompilationInfo; 15 16 17// A hash map to support fast variable declaration and lookup. 18class VariableMap: public ZoneHashMap { 19 public: 20 explicit VariableMap(Zone* zone); 21 22 virtual ~VariableMap(); 23 24 Variable* Declare(Scope* scope, 25 Handle<String> name, 26 VariableMode mode, 27 bool is_valid_lhs, 28 Variable::Kind kind, 29 InitializationFlag initialization_flag, 30 Interface* interface = Interface::NewValue()); 31 32 Variable* Lookup(Handle<String> name); 33 34 Zone* zone() const { return zone_; } 35 36 private: 37 Zone* zone_; 38}; 39 40 41// The dynamic scope part holds hash maps for the variables that will 42// be looked up dynamically from within eval and with scopes. The objects 43// are allocated on-demand from Scope::NonLocal to avoid wasting memory 44// and setup time for scopes that don't need them. 45class DynamicScopePart : public ZoneObject { 46 public: 47 explicit DynamicScopePart(Zone* zone) { 48 for (int i = 0; i < 3; i++) 49 maps_[i] = new(zone->New(sizeof(VariableMap))) VariableMap(zone); 50 } 51 52 VariableMap* GetMap(VariableMode mode) { 53 int index = mode - DYNAMIC; 54 ASSERT(index >= 0 && index < 3); 55 return maps_[index]; 56 } 57 58 private: 59 VariableMap *maps_[3]; 60}; 61 62 63// Global invariants after AST construction: Each reference (i.e. identifier) 64// to a JavaScript variable (including global properties) is represented by a 65// VariableProxy node. Immediately after AST construction and before variable 66// allocation, most VariableProxy nodes are "unresolved", i.e. not bound to a 67// corresponding variable (though some are bound during parse time). Variable 68// allocation binds each unresolved VariableProxy to one Variable and assigns 69// a location. Note that many VariableProxy nodes may refer to the same Java- 70// Script variable. 71 72class Scope: public ZoneObject { 73 public: 74 // --------------------------------------------------------------------------- 75 // Construction 76 77 Scope(Scope* outer_scope, ScopeType scope_type, Zone* zone); 78 79 // Compute top scope and allocate variables. For lazy compilation the top 80 // scope only contains the single lazily compiled function, so this 81 // doesn't re-allocate variables repeatedly. 82 static bool Analyze(CompilationInfo* info); 83 84 static Scope* DeserializeScopeChain(Context* context, Scope* global_scope, 85 Zone* zone); 86 87 // The scope name is only used for printing/debugging. 88 void SetScopeName(Handle<String> scope_name) { scope_name_ = scope_name; } 89 90 void Initialize(); 91 92 // Checks if the block scope is redundant, i.e. it does not contain any 93 // block scoped declarations. In that case it is removed from the scope 94 // tree and its children are reparented. 95 Scope* FinalizeBlockScope(); 96 97 Zone* zone() const { return zone_; } 98 99 // --------------------------------------------------------------------------- 100 // Declarations 101 102 // Lookup a variable in this scope. Returns the variable or NULL if not found. 103 Variable* LookupLocal(Handle<String> name); 104 105 // This lookup corresponds to a lookup in the "intermediate" scope sitting 106 // between this scope and the outer scope. (ECMA-262, 3rd., requires that 107 // the name of named function literal is kept in an intermediate scope 108 // in between this scope and the next outer scope.) 109 Variable* LookupFunctionVar(Handle<String> name, 110 AstNodeFactory<AstNullVisitor>* factory); 111 112 // Lookup a variable in this scope or outer scopes. 113 // Returns the variable or NULL if not found. 114 Variable* Lookup(Handle<String> name); 115 116 // Declare the function variable for a function literal. This variable 117 // is in an intermediate scope between this function scope and the the 118 // outer scope. Only possible for function scopes; at most one variable. 119 void DeclareFunctionVar(VariableDeclaration* declaration) { 120 ASSERT(is_function_scope()); 121 function_ = declaration; 122 } 123 124 // Declare a parameter in this scope. When there are duplicated 125 // parameters the rightmost one 'wins'. However, the implementation 126 // expects all parameters to be declared and from left to right. 127 void DeclareParameter(Handle<String> name, VariableMode mode); 128 129 // Declare a local variable in this scope. If the variable has been 130 // declared before, the previously declared variable is returned. 131 Variable* DeclareLocal(Handle<String> name, 132 VariableMode mode, 133 InitializationFlag init_flag, 134 Interface* interface = Interface::NewValue()); 135 136 // Declare an implicit global variable in this scope which must be a 137 // global scope. The variable was introduced (possibly from an inner 138 // scope) by a reference to an unresolved variable with no intervening 139 // with statements or eval calls. 140 Variable* DeclareDynamicGlobal(Handle<String> name); 141 142 // Create a new unresolved variable. 143 template<class Visitor> 144 VariableProxy* NewUnresolved(AstNodeFactory<Visitor>* factory, 145 Handle<String> name, 146 Interface* interface = Interface::NewValue(), 147 int position = RelocInfo::kNoPosition) { 148 // Note that we must not share the unresolved variables with 149 // the same name because they may be removed selectively via 150 // RemoveUnresolved(). 151 ASSERT(!already_resolved()); 152 VariableProxy* proxy = 153 factory->NewVariableProxy(name, false, interface, position); 154 unresolved_.Add(proxy, zone_); 155 return proxy; 156 } 157 158 // Remove a unresolved variable. During parsing, an unresolved variable 159 // may have been added optimistically, but then only the variable name 160 // was used (typically for labels). If the variable was not declared, the 161 // addition introduced a new unresolved variable which may end up being 162 // allocated globally as a "ghost" variable. RemoveUnresolved removes 163 // such a variable again if it was added; otherwise this is a no-op. 164 void RemoveUnresolved(VariableProxy* var); 165 166 // Creates a new internal variable in this scope. The name is only used 167 // for printing and cannot be used to find the variable. In particular, 168 // the only way to get hold of the temporary is by keeping the Variable* 169 // around. 170 Variable* NewInternal(Handle<String> name); 171 172 // Creates a new temporary variable in this scope. The name is only used 173 // for printing and cannot be used to find the variable. In particular, 174 // the only way to get hold of the temporary is by keeping the Variable* 175 // around. The name should not clash with a legitimate variable names. 176 Variable* NewTemporary(Handle<String> name); 177 178 // Adds the specific declaration node to the list of declarations in 179 // this scope. The declarations are processed as part of entering 180 // the scope; see codegen.cc:ProcessDeclarations. 181 void AddDeclaration(Declaration* declaration); 182 183 // --------------------------------------------------------------------------- 184 // Illegal redeclaration support. 185 186 // Set an expression node that will be executed when the scope is 187 // entered. We only keep track of one illegal redeclaration node per 188 // scope - the first one - so if you try to set it multiple times 189 // the additional requests will be silently ignored. 190 void SetIllegalRedeclaration(Expression* expression); 191 192 // Visit the illegal redeclaration expression. Do not call if the 193 // scope doesn't have an illegal redeclaration node. 194 void VisitIllegalRedeclaration(AstVisitor* visitor); 195 196 // Check if the scope has (at least) one illegal redeclaration. 197 bool HasIllegalRedeclaration() const { return illegal_redecl_ != NULL; } 198 199 // For harmony block scoping mode: Check if the scope has conflicting var 200 // declarations, i.e. a var declaration that has been hoisted from a nested 201 // scope over a let binding of the same name. 202 Declaration* CheckConflictingVarDeclarations(); 203 204 // --------------------------------------------------------------------------- 205 // Scope-specific info. 206 207 // Inform the scope that the corresponding code contains a with statement. 208 void RecordWithStatement() { scope_contains_with_ = true; } 209 210 // Inform the scope that the corresponding code contains an eval call. 211 void RecordEvalCall() { if (!is_global_scope()) scope_calls_eval_ = true; } 212 213 // Set the strict mode flag (unless disabled by a global flag). 214 void SetStrictMode(StrictMode strict_mode) { strict_mode_ = strict_mode; } 215 216 // Position in the source where this scope begins and ends. 217 // 218 // * For the scope of a with statement 219 // with (obj) stmt 220 // start position: start position of first token of 'stmt' 221 // end position: end position of last token of 'stmt' 222 // * For the scope of a block 223 // { stmts } 224 // start position: start position of '{' 225 // end position: end position of '}' 226 // * For the scope of a function literal or decalaration 227 // function fun(a,b) { stmts } 228 // start position: start position of '(' 229 // end position: end position of '}' 230 // * For the scope of a catch block 231 // try { stms } catch(e) { stmts } 232 // start position: start position of '(' 233 // end position: end position of ')' 234 // * For the scope of a for-statement 235 // for (let x ...) stmt 236 // start position: start position of '(' 237 // end position: end position of last token of 'stmt' 238 int start_position() const { return start_position_; } 239 void set_start_position(int statement_pos) { 240 start_position_ = statement_pos; 241 } 242 int end_position() const { return end_position_; } 243 void set_end_position(int statement_pos) { 244 end_position_ = statement_pos; 245 } 246 247 // In some cases we want to force context allocation for a whole scope. 248 void ForceContextAllocation() { 249 ASSERT(!already_resolved()); 250 force_context_allocation_ = true; 251 } 252 bool has_forced_context_allocation() const { 253 return force_context_allocation_; 254 } 255 256 // --------------------------------------------------------------------------- 257 // Predicates. 258 259 // Specific scope types. 260 bool is_eval_scope() const { return scope_type_ == EVAL_SCOPE; } 261 bool is_function_scope() const { return scope_type_ == FUNCTION_SCOPE; } 262 bool is_module_scope() const { return scope_type_ == MODULE_SCOPE; } 263 bool is_global_scope() const { return scope_type_ == GLOBAL_SCOPE; } 264 bool is_catch_scope() const { return scope_type_ == CATCH_SCOPE; } 265 bool is_block_scope() const { return scope_type_ == BLOCK_SCOPE; } 266 bool is_with_scope() const { return scope_type_ == WITH_SCOPE; } 267 bool is_declaration_scope() const { 268 return is_eval_scope() || is_function_scope() || 269 is_module_scope() || is_global_scope(); 270 } 271 bool is_strict_eval_scope() const { 272 return is_eval_scope() && strict_mode_ == STRICT; 273 } 274 275 // Information about which scopes calls eval. 276 bool calls_eval() const { return scope_calls_eval_; } 277 bool calls_sloppy_eval() { 278 return scope_calls_eval_ && strict_mode_ == SLOPPY; 279 } 280 bool outer_scope_calls_sloppy_eval() const { 281 return outer_scope_calls_sloppy_eval_; 282 } 283 284 // Is this scope inside a with statement. 285 bool inside_with() const { return scope_inside_with_; } 286 // Does this scope contain a with statement. 287 bool contains_with() const { return scope_contains_with_; } 288 289 // --------------------------------------------------------------------------- 290 // Accessors. 291 292 // The type of this scope. 293 ScopeType scope_type() const { return scope_type_; } 294 295 // The language mode of this scope. 296 StrictMode strict_mode() const { return strict_mode_; } 297 298 // The variable corresponding the 'this' value. 299 Variable* receiver() { return receiver_; } 300 301 // The variable holding the function literal for named function 302 // literals, or NULL. Only valid for function scopes. 303 VariableDeclaration* function() const { 304 ASSERT(is_function_scope()); 305 return function_; 306 } 307 308 // Parameters. The left-most parameter has index 0. 309 // Only valid for function scopes. 310 Variable* parameter(int index) const { 311 ASSERT(is_function_scope()); 312 return params_[index]; 313 } 314 315 int num_parameters() const { return params_.length(); } 316 317 // The local variable 'arguments' if we need to allocate it; NULL otherwise. 318 Variable* arguments() const { return arguments_; } 319 320 // Declarations list. 321 ZoneList<Declaration*>* declarations() { return &decls_; } 322 323 // Inner scope list. 324 ZoneList<Scope*>* inner_scopes() { return &inner_scopes_; } 325 326 // The scope immediately surrounding this scope, or NULL. 327 Scope* outer_scope() const { return outer_scope_; } 328 329 // The interface as inferred so far; only for module scopes. 330 Interface* interface() const { return interface_; } 331 332 // --------------------------------------------------------------------------- 333 // Variable allocation. 334 335 // Collect stack and context allocated local variables in this scope. Note 336 // that the function variable - if present - is not collected and should be 337 // handled separately. 338 void CollectStackAndContextLocals(ZoneList<Variable*>* stack_locals, 339 ZoneList<Variable*>* context_locals); 340 341 // Current number of var or const locals. 342 int num_var_or_const() { return num_var_or_const_; } 343 344 // Result of variable allocation. 345 int num_stack_slots() const { return num_stack_slots_; } 346 int num_heap_slots() const { return num_heap_slots_; } 347 348 int StackLocalCount() const; 349 int ContextLocalCount() const; 350 351 // For global scopes, the number of module literals (including nested ones). 352 int num_modules() const { return num_modules_; } 353 354 // For module scopes, the host scope's internal variable binding this module. 355 Variable* module_var() const { return module_var_; } 356 357 // Make sure this scope and all outer scopes are eagerly compiled. 358 void ForceEagerCompilation() { force_eager_compilation_ = true; } 359 360 // Determine if we can use lazy compilation for this scope. 361 bool AllowsLazyCompilation() const; 362 363 // Determine if we can use lazy compilation for this scope without a context. 364 bool AllowsLazyCompilationWithoutContext() const; 365 366 // True if the outer context of this scope is always the native context. 367 bool HasTrivialOuterContext() const; 368 369 // True if the outer context allows lazy compilation of this scope. 370 bool HasLazyCompilableOuterContext() const; 371 372 // The number of contexts between this and scope; zero if this == scope. 373 int ContextChainLength(Scope* scope); 374 375 // Find the innermost global scope. 376 Scope* GlobalScope(); 377 378 // Find the first function, global, or eval scope. This is the scope 379 // where var declarations will be hoisted to in the implementation. 380 Scope* DeclarationScope(); 381 382 Handle<ScopeInfo> GetScopeInfo(); 383 384 // Get the chain of nested scopes within this scope for the source statement 385 // position. The scopes will be added to the list from the outermost scope to 386 // the innermost scope. Only nested block, catch or with scopes are tracked 387 // and will be returned, but no inner function scopes. 388 void GetNestedScopeChain(List<Handle<ScopeInfo> >* chain, 389 int statement_position); 390 391 // --------------------------------------------------------------------------- 392 // Strict mode support. 393 bool IsDeclared(Handle<String> name) { 394 // During formal parameter list parsing the scope only contains 395 // two variables inserted at initialization: "this" and "arguments". 396 // "this" is an invalid parameter name and "arguments" is invalid parameter 397 // name in strict mode. Therefore looking up with the map which includes 398 // "this" and "arguments" in addition to all formal parameters is safe. 399 return variables_.Lookup(name) != NULL; 400 } 401 402 // --------------------------------------------------------------------------- 403 // Debugging. 404 405#ifdef DEBUG 406 void Print(int n = 0); // n = indentation; n < 0 => don't print recursively 407#endif 408 409 // --------------------------------------------------------------------------- 410 // Implementation. 411 protected: 412 friend class ParserFactory; 413 414 Isolate* const isolate_; 415 416 // Scope tree. 417 Scope* outer_scope_; // the immediately enclosing outer scope, or NULL 418 ZoneList<Scope*> inner_scopes_; // the immediately enclosed inner scopes 419 420 // The scope type. 421 ScopeType scope_type_; 422 423 // Debugging support. 424 Handle<String> scope_name_; 425 426 // The variables declared in this scope: 427 // 428 // All user-declared variables (incl. parameters). For global scopes 429 // variables may be implicitly 'declared' by being used (possibly in 430 // an inner scope) with no intervening with statements or eval calls. 431 VariableMap variables_; 432 // Compiler-allocated (user-invisible) internals. 433 ZoneList<Variable*> internals_; 434 // Compiler-allocated (user-invisible) temporaries. 435 ZoneList<Variable*> temps_; 436 // Parameter list in source order. 437 ZoneList<Variable*> params_; 438 // Variables that must be looked up dynamically. 439 DynamicScopePart* dynamics_; 440 // Unresolved variables referred to from this scope. 441 ZoneList<VariableProxy*> unresolved_; 442 // Declarations. 443 ZoneList<Declaration*> decls_; 444 // Convenience variable. 445 Variable* receiver_; 446 // Function variable, if any; function scopes only. 447 VariableDeclaration* function_; 448 // Convenience variable; function scopes only. 449 Variable* arguments_; 450 // Interface; module scopes only. 451 Interface* interface_; 452 453 // Illegal redeclaration. 454 Expression* illegal_redecl_; 455 456 // Scope-specific information computed during parsing. 457 // 458 // This scope is inside a 'with' of some outer scope. 459 bool scope_inside_with_; 460 // This scope contains a 'with' statement. 461 bool scope_contains_with_; 462 // This scope or a nested catch scope or with scope contain an 'eval' call. At 463 // the 'eval' call site this scope is the declaration scope. 464 bool scope_calls_eval_; 465 // The strict mode of this scope. 466 StrictMode strict_mode_; 467 // Source positions. 468 int start_position_; 469 int end_position_; 470 471 // Computed via PropagateScopeInfo. 472 bool outer_scope_calls_sloppy_eval_; 473 bool inner_scope_calls_eval_; 474 bool force_eager_compilation_; 475 bool force_context_allocation_; 476 477 // True if it doesn't need scope resolution (e.g., if the scope was 478 // constructed based on a serialized scope info or a catch context). 479 bool already_resolved_; 480 481 // Computed as variables are declared. 482 int num_var_or_const_; 483 484 // Computed via AllocateVariables; function, block and catch scopes only. 485 int num_stack_slots_; 486 int num_heap_slots_; 487 488 // The number of modules (including nested ones). 489 int num_modules_; 490 491 // For module scopes, the host scope's internal variable binding this module. 492 Variable* module_var_; 493 494 // Serialized scope info support. 495 Handle<ScopeInfo> scope_info_; 496 bool already_resolved() { return already_resolved_; } 497 498 // Create a non-local variable with a given name. 499 // These variables are looked up dynamically at runtime. 500 Variable* NonLocal(Handle<String> name, VariableMode mode); 501 502 // Variable resolution. 503 // Possible results of a recursive variable lookup telling if and how a 504 // variable is bound. These are returned in the output parameter *binding_kind 505 // of the LookupRecursive function. 506 enum BindingKind { 507 // The variable reference could be statically resolved to a variable binding 508 // which is returned. There is no 'with' statement between the reference and 509 // the binding and no scope between the reference scope (inclusive) and 510 // binding scope (exclusive) makes a sloppy 'eval' call. 511 BOUND, 512 513 // The variable reference could be statically resolved to a variable binding 514 // which is returned. There is no 'with' statement between the reference and 515 // the binding, but some scope between the reference scope (inclusive) and 516 // binding scope (exclusive) makes a sloppy 'eval' call, that might 517 // possibly introduce variable bindings shadowing the found one. Thus the 518 // found variable binding is just a guess. 519 BOUND_EVAL_SHADOWED, 520 521 // The variable reference could not be statically resolved to any binding 522 // and thus should be considered referencing a global variable. NULL is 523 // returned. The variable reference is not inside any 'with' statement and 524 // no scope between the reference scope (inclusive) and global scope 525 // (exclusive) makes a sloppy 'eval' call. 526 UNBOUND, 527 528 // The variable reference could not be statically resolved to any binding 529 // NULL is returned. The variable reference is not inside any 'with' 530 // statement, but some scope between the reference scope (inclusive) and 531 // global scope (exclusive) makes a sloppy 'eval' call, that might 532 // possibly introduce a variable binding. Thus the reference should be 533 // considered referencing a global variable unless it is shadowed by an 534 // 'eval' introduced binding. 535 UNBOUND_EVAL_SHADOWED, 536 537 // The variable could not be statically resolved and needs to be looked up 538 // dynamically. NULL is returned. There are two possible reasons: 539 // * A 'with' statement has been encountered and there is no variable 540 // binding for the name between the variable reference and the 'with'. 541 // The variable potentially references a property of the 'with' object. 542 // * The code is being executed as part of a call to 'eval' and the calling 543 // context chain contains either a variable binding for the name or it 544 // contains a 'with' context. 545 DYNAMIC_LOOKUP 546 }; 547 548 // Lookup a variable reference given by name recursively starting with this 549 // scope. If the code is executed because of a call to 'eval', the context 550 // parameter should be set to the calling context of 'eval'. 551 Variable* LookupRecursive(Handle<String> name, 552 BindingKind* binding_kind, 553 AstNodeFactory<AstNullVisitor>* factory); 554 MUST_USE_RESULT 555 bool ResolveVariable(CompilationInfo* info, 556 VariableProxy* proxy, 557 AstNodeFactory<AstNullVisitor>* factory); 558 MUST_USE_RESULT 559 bool ResolveVariablesRecursively(CompilationInfo* info, 560 AstNodeFactory<AstNullVisitor>* factory); 561 562 // Scope analysis. 563 bool PropagateScopeInfo(bool outer_scope_calls_sloppy_eval); 564 bool HasTrivialContext() const; 565 566 // Predicates. 567 bool MustAllocate(Variable* var); 568 bool MustAllocateInContext(Variable* var); 569 bool HasArgumentsParameter(); 570 571 // Variable allocation. 572 void AllocateStackSlot(Variable* var); 573 void AllocateHeapSlot(Variable* var); 574 void AllocateParameterLocals(); 575 void AllocateNonParameterLocal(Variable* var); 576 void AllocateNonParameterLocals(); 577 void AllocateVariablesRecursively(); 578 void AllocateModulesRecursively(Scope* host_scope); 579 580 // Resolve and fill in the allocation information for all variables 581 // in this scopes. Must be called *after* all scopes have been 582 // processed (parsed) to ensure that unresolved variables can be 583 // resolved properly. 584 // 585 // In the case of code compiled and run using 'eval', the context 586 // parameter is the context in which eval was called. In all other 587 // cases the context parameter is an empty handle. 588 MUST_USE_RESULT 589 bool AllocateVariables(CompilationInfo* info, 590 AstNodeFactory<AstNullVisitor>* factory); 591 592 private: 593 // Construct a scope based on the scope info. 594 Scope(Scope* inner_scope, ScopeType type, Handle<ScopeInfo> scope_info, 595 Zone* zone); 596 597 // Construct a catch scope with a binding for the name. 598 Scope(Scope* inner_scope, Handle<String> catch_variable_name, Zone* zone); 599 600 void AddInnerScope(Scope* inner_scope) { 601 if (inner_scope != NULL) { 602 inner_scopes_.Add(inner_scope, zone_); 603 inner_scope->outer_scope_ = this; 604 } 605 } 606 607 void SetDefaults(ScopeType type, 608 Scope* outer_scope, 609 Handle<ScopeInfo> scope_info); 610 611 Zone* zone_; 612}; 613 614} } // namespace v8::internal 615 616#endif // V8_SCOPES_H_ 617