scopes.h revision b0fe1620dcb4135ac3ab2d66ff93072373911299
1// Copyright 2010 the V8 project authors. All rights reserved. 2// Redistribution and use in source and binary forms, with or without 3// modification, are permitted provided that the following conditions are 4// met: 5// 6// * Redistributions of source code must retain the above copyright 7// notice, this list of conditions and the following disclaimer. 8// * Redistributions in binary form must reproduce the above 9// copyright notice, this list of conditions and the following 10// disclaimer in the documentation and/or other materials provided 11// with the distribution. 12// * Neither the name of Google Inc. nor the names of its 13// contributors may be used to endorse or promote products derived 14// from this software without specific prior written permission. 15// 16// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 17// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 18// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 19// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 20// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 21// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 22// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 23// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 24// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 25// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 26// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 27 28#ifndef V8_SCOPES_H_ 29#define V8_SCOPES_H_ 30 31#include "ast.h" 32#include "hashmap.h" 33 34namespace v8 { 35namespace internal { 36 37class CompilationInfo; 38 39 40// A hash map to support fast variable declaration and lookup. 41class VariableMap: public HashMap { 42 public: 43 VariableMap(); 44 45 // Dummy constructor. This constructor doesn't set up the map 46 // properly so don't use it unless you have a good reason. 47 explicit VariableMap(bool gotta_love_static_overloading); 48 49 virtual ~VariableMap(); 50 51 Variable* Declare(Scope* scope, 52 Handle<String> name, 53 Variable::Mode mode, 54 bool is_valid_lhs, 55 Variable::Kind kind); 56 57 Variable* Lookup(Handle<String> name); 58}; 59 60 61// The dynamic scope part holds hash maps for the variables that will 62// be looked up dynamically from within eval and with scopes. The objects 63// are allocated on-demand from Scope::NonLocal to avoid wasting memory 64// and setup time for scopes that don't need them. 65class DynamicScopePart : public ZoneObject { 66 public: 67 VariableMap* GetMap(Variable::Mode mode) { 68 int index = mode - Variable::DYNAMIC; 69 ASSERT(index >= 0 && index < 3); 70 return &maps_[index]; 71 } 72 73 private: 74 VariableMap maps_[3]; 75}; 76 77 78// Global invariants after AST construction: Each reference (i.e. identifier) 79// to a JavaScript variable (including global properties) is represented by a 80// VariableProxy node. Immediately after AST construction and before variable 81// allocation, most VariableProxy nodes are "unresolved", i.e. not bound to a 82// corresponding variable (though some are bound during parse time). Variable 83// allocation binds each unresolved VariableProxy to one Variable and assigns 84// a location. Note that many VariableProxy nodes may refer to the same Java- 85// Script variable. 86 87class Scope: public ZoneObject { 88 public: 89 // --------------------------------------------------------------------------- 90 // Construction 91 92 enum Type { 93 EVAL_SCOPE, // the top-level scope for an 'eval' source 94 FUNCTION_SCOPE, // the top-level scope for a function 95 GLOBAL_SCOPE // the top-level scope for a program or a top-level eval 96 }; 97 98 Scope(Scope* outer_scope, Type type); 99 100 virtual ~Scope() { } 101 102 // Compute top scope and allocate variables. For lazy compilation the top 103 // scope only contains the single lazily compiled function, so this 104 // doesn't re-allocate variables repeatedly. 105 static bool Analyze(CompilationInfo* info); 106 107 // The scope name is only used for printing/debugging. 108 void SetScopeName(Handle<String> scope_name) { scope_name_ = scope_name; } 109 110 virtual void Initialize(bool inside_with); 111 112 // Called just before leaving a scope. 113 virtual void Leave() { 114 // No cleanup or fixup necessary. 115 } 116 117 // --------------------------------------------------------------------------- 118 // Declarations 119 120 // Lookup a variable in this scope. Returns the variable or NULL if not found. 121 virtual Variable* LocalLookup(Handle<String> name); 122 123 // Lookup a variable in this scope or outer scopes. 124 // Returns the variable or NULL if not found. 125 virtual Variable* Lookup(Handle<String> name); 126 127 // Declare the function variable for a function literal. This variable 128 // is in an intermediate scope between this function scope and the the 129 // outer scope. Only possible for function scopes; at most one variable. 130 Variable* DeclareFunctionVar(Handle<String> name); 131 132 // Declare a local variable in this scope. If the variable has been 133 // declared before, the previously declared variable is returned. 134 virtual Variable* DeclareLocal(Handle<String> name, Variable::Mode mode); 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* DeclareGlobal(Handle<String> name); 141 142 // Add a parameter to the parameter list. The parameter must have been 143 // declared via Declare. The same parameter may occur more than once in 144 // the parameter list; they must be added in source order, from left to 145 // right. 146 void AddParameter(Variable* var); 147 148 // Create a new unresolved variable. 149 virtual VariableProxy* NewUnresolved(Handle<String> name, bool inside_with); 150 151 // Remove a unresolved variable. During parsing, an unresolved variable 152 // may have been added optimistically, but then only the variable name 153 // was used (typically for labels). If the variable was not declared, the 154 // addition introduced a new unresolved variable which may end up being 155 // allocated globally as a "ghost" variable. RemoveUnresolved removes 156 // such a variable again if it was added; otherwise this is a no-op. 157 void RemoveUnresolved(VariableProxy* var); 158 159 // Creates a new temporary variable in this scope. The name is only used 160 // for printing and cannot be used to find the variable. In particular, 161 // the only way to get hold of the temporary is by keeping the Variable* 162 // around. 163 virtual Variable* NewTemporary(Handle<String> name); 164 165 // Adds the specific declaration node to the list of declarations in 166 // this scope. The declarations are processed as part of entering 167 // the scope; see codegen.cc:ProcessDeclarations. 168 void AddDeclaration(Declaration* declaration); 169 170 // --------------------------------------------------------------------------- 171 // Illegal redeclaration support. 172 173 // Set an expression node that will be executed when the scope is 174 // entered. We only keep track of one illegal redeclaration node per 175 // scope - the first one - so if you try to set it multiple times 176 // the additional requests will be silently ignored. 177 void SetIllegalRedeclaration(Expression* expression); 178 179 // Visit the illegal redeclaration expression. Do not call if the 180 // scope doesn't have an illegal redeclaration node. 181 void VisitIllegalRedeclaration(AstVisitor* visitor); 182 183 // Check if the scope has (at least) one illegal redeclaration. 184 bool HasIllegalRedeclaration() const { return illegal_redecl_ != NULL; } 185 186 187 // --------------------------------------------------------------------------- 188 // Scope-specific info. 189 190 // Inform the scope that the corresponding code contains a with statement. 191 void RecordWithStatement() { scope_contains_with_ = true; } 192 193 // Inform the scope that the corresponding code contains an eval call. 194 void RecordEvalCall() { scope_calls_eval_ = true; } 195 196 197 // --------------------------------------------------------------------------- 198 // Predicates. 199 200 // Specific scope types. 201 bool is_eval_scope() const { return type_ == EVAL_SCOPE; } 202 bool is_function_scope() const { return type_ == FUNCTION_SCOPE; } 203 bool is_global_scope() const { return type_ == GLOBAL_SCOPE; } 204 205 // Information about which scopes calls eval. 206 bool calls_eval() const { return scope_calls_eval_; } 207 bool outer_scope_calls_eval() const { return outer_scope_calls_eval_; } 208 209 // Is this scope inside a with statement. 210 bool inside_with() const { return scope_inside_with_; } 211 // Does this scope contain a with statement. 212 bool contains_with() const { return scope_contains_with_; } 213 214 // The scope immediately surrounding this scope, or NULL. 215 Scope* outer_scope() const { return outer_scope_; } 216 217 // --------------------------------------------------------------------------- 218 // Accessors. 219 220 // A new variable proxy corresponding to the (function) receiver. 221 VariableProxy* receiver() const { 222 VariableProxy* proxy = 223 new VariableProxy(Factory::this_symbol(), true, false); 224 proxy->BindTo(receiver_); 225 return proxy; 226 } 227 228 // The variable holding the function literal for named function 229 // literals, or NULL. 230 // Only valid for function scopes. 231 Variable* function() const { 232 ASSERT(is_function_scope()); 233 return function_; 234 } 235 236 // Parameters. The left-most parameter has index 0. 237 // Only valid for function scopes. 238 Variable* parameter(int index) const { 239 ASSERT(is_function_scope()); 240 return params_[index]; 241 } 242 243 int num_parameters() const { return params_.length(); } 244 245 // The local variable 'arguments' if we need to allocate it; NULL otherwise. 246 // If arguments() exist, arguments_shadow() exists, too. 247 Variable* arguments() const { return arguments_; } 248 249 // The '.arguments' shadow variable if we need to allocate it; NULL otherwise. 250 // If arguments_shadow() exist, arguments() exists, too. 251 Variable* arguments_shadow() const { return arguments_shadow_; } 252 253 // Declarations list. 254 ZoneList<Declaration*>* declarations() { return &decls_; } 255 256 257 258 // --------------------------------------------------------------------------- 259 // Variable allocation. 260 261 // Collect all used locals in this scope. 262 template<class Allocator> 263 void CollectUsedVariables(List<Variable*, Allocator>* locals); 264 265 // Resolve and fill in the allocation information for all variables 266 // in this scopes. Must be called *after* all scopes have been 267 // processed (parsed) to ensure that unresolved variables can be 268 // resolved properly. 269 // 270 // In the case of code compiled and run using 'eval', the context 271 // parameter is the context in which eval was called. In all other 272 // cases the context parameter is an empty handle. 273 void AllocateVariables(Handle<Context> context); 274 275 // Result of variable allocation. 276 int num_stack_slots() const { return num_stack_slots_; } 277 int num_heap_slots() const { return num_heap_slots_; } 278 279 // Make sure this scope and all outer scopes are eagerly compiled. 280 void ForceEagerCompilation() { force_eager_compilation_ = true; } 281 282 // Determine if we can use lazy compilation for this scope. 283 bool AllowsLazyCompilation() const; 284 285 // True if the outer context of this scope is always the global context. 286 virtual bool HasTrivialOuterContext() const; 287 288 // The number of contexts between this and scope; zero if this == scope. 289 int ContextChainLength(Scope* scope); 290 291 // --------------------------------------------------------------------------- 292 // Debugging. 293 294#ifdef DEBUG 295 void Print(int n = 0); // n = indentation; n < 0 => don't print recursively 296#endif 297 298 // --------------------------------------------------------------------------- 299 // Implementation. 300 protected: 301 friend class ParserFactory; 302 303 explicit Scope(Type type); 304 305 // Scope tree. 306 Scope* outer_scope_; // the immediately enclosing outer scope, or NULL 307 ZoneList<Scope*> inner_scopes_; // the immediately enclosed inner scopes 308 309 // The scope type. 310 Type type_; 311 312 // Debugging support. 313 Handle<String> scope_name_; 314 315 // The variables declared in this scope: 316 // 317 // All user-declared variables (incl. parameters). For global scopes 318 // variables may be implicitly 'declared' by being used (possibly in 319 // an inner scope) with no intervening with statements or eval calls. 320 VariableMap variables_; 321 // Compiler-allocated (user-invisible) temporaries. 322 ZoneList<Variable*> temps_; 323 // Parameter list in source order. 324 ZoneList<Variable*> params_; 325 // Variables that must be looked up dynamically. 326 DynamicScopePart* dynamics_; 327 // Unresolved variables referred to from this scope. 328 ZoneList<VariableProxy*> unresolved_; 329 // Declarations. 330 ZoneList<Declaration*> decls_; 331 // Convenience variable. 332 Variable* receiver_; 333 // Function variable, if any; function scopes only. 334 Variable* function_; 335 // Convenience variable; function scopes only. 336 Variable* arguments_; 337 // Convenience variable; function scopes only. 338 Variable* arguments_shadow_; 339 340 // Illegal redeclaration. 341 Expression* illegal_redecl_; 342 343 // Scope-specific information. 344 bool scope_inside_with_; // this scope is inside a 'with' of some outer scope 345 bool scope_contains_with_; // this scope contains a 'with' statement 346 bool scope_calls_eval_; // this scope contains an 'eval' call 347 348 // Computed via PropagateScopeInfo. 349 bool outer_scope_calls_eval_; 350 bool inner_scope_calls_eval_; 351 bool outer_scope_is_eval_scope_; 352 bool force_eager_compilation_; 353 354 // Computed via AllocateVariables; function scopes only. 355 int num_stack_slots_; 356 int num_heap_slots_; 357 358 // Create a non-local variable with a given name. 359 // These variables are looked up dynamically at runtime. 360 Variable* NonLocal(Handle<String> name, Variable::Mode mode); 361 362 // Variable resolution. 363 Variable* LookupRecursive(Handle<String> name, 364 bool inner_lookup, 365 Variable** invalidated_local); 366 void ResolveVariable(Scope* global_scope, 367 Handle<Context> context, 368 VariableProxy* proxy); 369 void ResolveVariablesRecursively(Scope* global_scope, 370 Handle<Context> context); 371 372 // Scope analysis. 373 bool PropagateScopeInfo(bool outer_scope_calls_eval, 374 bool outer_scope_is_eval_scope); 375 bool HasTrivialContext() const; 376 377 // Predicates. 378 bool MustAllocate(Variable* var); 379 bool MustAllocateInContext(Variable* var); 380 bool HasArgumentsParameter(); 381 382 // Variable allocation. 383 void AllocateStackSlot(Variable* var); 384 void AllocateHeapSlot(Variable* var); 385 void AllocateParameterLocals(); 386 void AllocateNonParameterLocal(Variable* var); 387 void AllocateNonParameterLocals(); 388 void AllocateVariablesRecursively(); 389}; 390 391 392// Scope used during pre-parsing. 393class DummyScope : public Scope { 394 public: 395 DummyScope() 396 : Scope(GLOBAL_SCOPE), 397 nesting_level_(1), // Allows us to Leave the initial scope. 398 inside_with_level_(kNotInsideWith) { 399 outer_scope_ = this; 400 scope_inside_with_ = false; 401 } 402 403 virtual void Initialize(bool inside_with) { 404 nesting_level_++; 405 if (inside_with && inside_with_level_ == kNotInsideWith) { 406 inside_with_level_ = nesting_level_; 407 } 408 ASSERT(inside_with_level_ <= nesting_level_); 409 } 410 411 virtual void Leave() { 412 nesting_level_--; 413 ASSERT(nesting_level_ >= 0); 414 if (nesting_level_ < inside_with_level_) { 415 inside_with_level_ = kNotInsideWith; 416 } 417 ASSERT(inside_with_level_ <= nesting_level_); 418 } 419 420 virtual Variable* Lookup(Handle<String> name) { return NULL; } 421 422 virtual VariableProxy* NewUnresolved(Handle<String> name, bool inside_with) { 423 return NULL; 424 } 425 426 virtual Variable* NewTemporary(Handle<String> name) { return NULL; } 427 428 virtual bool HasTrivialOuterContext() const { 429 return (nesting_level_ == 0 || inside_with_level_ <= 0); 430 } 431 432 private: 433 static const int kNotInsideWith = -1; 434 // Number of surrounding scopes of the current scope. 435 int nesting_level_; 436 // Nesting level of outermost scope that is contained in a with statement, 437 // or kNotInsideWith if there are no with's around the current scope. 438 int inside_with_level_; 439}; 440 441 442} } // namespace v8::internal 443 444#endif // V8_SCOPES_H_ 445