• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 // Copyright 2006-2008 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 
34 namespace v8 {
35 namespace internal {
36 
37 
38 // A hash map to support fast variable declaration and lookup.
39 class VariableMap: public HashMap {
40  public:
41   VariableMap();
42 
43   // Dummy constructor.  This constructor doesn't set up the map
44   // properly so don't use it unless you have a good reason.
45   explicit VariableMap(bool gotta_love_static_overloading);
46 
47   virtual ~VariableMap();
48 
49   Variable* Declare(Scope* scope,
50                     Handle<String> name,
51                     Variable::Mode mode,
52                     bool is_valid_lhs,
53                     Variable::Kind kind);
54 
55   Variable* Lookup(Handle<String> name);
56 };
57 
58 
59 // The dynamic scope part holds hash maps for the variables that will
60 // be looked up dynamically from within eval and with scopes. The objects
61 // are allocated on-demand from Scope::NonLocal to avoid wasting memory
62 // and setup time for scopes that don't need them.
63 class DynamicScopePart : public ZoneObject {
64  public:
GetMap(Variable::Mode mode)65   VariableMap* GetMap(Variable::Mode mode) {
66     int index = mode - Variable::DYNAMIC;
67     ASSERT(index >= 0 && index < 3);
68     return &maps_[index];
69   }
70 
71  private:
72   VariableMap maps_[3];
73 };
74 
75 
76 // Global invariants after AST construction: Each reference (i.e. identifier)
77 // to a JavaScript variable (including global properties) is represented by a
78 // VariableProxy node. Immediately after AST construction and before variable
79 // allocation, most VariableProxy nodes are "unresolved", i.e. not bound to a
80 // corresponding variable (though some are bound during parse time). Variable
81 // allocation binds each unresolved VariableProxy to one Variable and assigns
82 // a location. Note that many VariableProxy nodes may refer to the same Java-
83 // Script variable.
84 
85 class Scope: public ZoneObject {
86  public:
87   // ---------------------------------------------------------------------------
88   // Construction
89 
90   enum Type {
91     EVAL_SCOPE,     // the top-level scope for an 'eval' source
92     FUNCTION_SCOPE,  // the top-level scope for a function
93     GLOBAL_SCOPE    // the top-level scope for a program or a top-level eval
94   };
95 
96   Scope(Scope* outer_scope, Type type);
97 
~Scope()98   virtual ~Scope() { }
99 
100   // The scope name is only used for printing/debugging.
SetScopeName(Handle<String> scope_name)101   void SetScopeName(Handle<String> scope_name)  { scope_name_ = scope_name; }
102 
103   void Initialize(bool inside_with);
104 
105 
106   // ---------------------------------------------------------------------------
107   // Declarations
108 
109   // Lookup a variable in this scope. Returns the variable or NULL if not found.
110   virtual Variable* LocalLookup(Handle<String> name);
111 
112   // Lookup a variable in this scope or outer scopes.
113   // Returns the variable or NULL if not found.
114   virtual 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   Variable* DeclareFunctionVar(Handle<String> name);
120 
121   // Declare a local variable in this scope. If the variable has been
122   // declared before, the previously declared variable is returned.
123   virtual Variable* DeclareLocal(Handle<String> name, Variable::Mode mode);
124 
125   // Declare an implicit global variable in this scope which must be a
126   // global scope.  The variable was introduced (possibly from an inner
127   // scope) by a reference to an unresolved variable with no intervening
128   // with statements or eval calls.
129   Variable* DeclareGlobal(Handle<String> name);
130 
131   // Add a parameter to the parameter list. The parameter must have been
132   // declared via Declare. The same parameter may occur more than once in
133   // the parameter list; they must be added in source order, from left to
134   // right.
135   void AddParameter(Variable* var);
136 
137   // Create a new unresolved variable.
138   virtual VariableProxy* NewUnresolved(Handle<String> name, bool inside_with);
139 
140   // Remove a unresolved variable. During parsing, an unresolved variable
141   // may have been added optimistically, but then only the variable name
142   // was used (typically for labels). If the variable was not declared, the
143   // addition introduced a new unresolved variable which may end up being
144   // allocated globally as a "ghost" variable. RemoveUnresolved removes
145   // such a variable again if it was added; otherwise this is a no-op.
146   void RemoveUnresolved(VariableProxy* var);
147 
148   // Creates a new temporary variable in this scope and binds a proxy to it.
149   // The name is only used for printing and cannot be used to find the variable.
150   // In particular, the only way to get hold of the temporary is by keeping the
151   // VariableProxy* around.
152   virtual VariableProxy* NewTemporary(Handle<String> name);
153 
154   // Adds the specific declaration node to the list of declarations in
155   // this scope. The declarations are processed as part of entering
156   // the scope; see codegen.cc:ProcessDeclarations.
157   void AddDeclaration(Declaration* declaration);
158 
159   // ---------------------------------------------------------------------------
160   // Illegal redeclaration support.
161 
162   // Set an expression node that will be executed when the scope is
163   // entered. We only keep track of one illegal redeclaration node per
164   // scope - the first one - so if you try to set it multiple times
165   // the additional requests will be silently ignored.
166   void SetIllegalRedeclaration(Expression* expression);
167 
168   // Visit the illegal redeclaration expression. Do not call if the
169   // scope doesn't have an illegal redeclaration node.
170   void VisitIllegalRedeclaration(AstVisitor* visitor);
171 
172   // Check if the scope has (at least) one illegal redeclaration.
HasIllegalRedeclaration()173   bool HasIllegalRedeclaration() const { return illegal_redecl_ != NULL; }
174 
175 
176   // ---------------------------------------------------------------------------
177   // Scope-specific info.
178 
179   // Inform the scope that the corresponding code contains a with statement.
RecordWithStatement()180   void RecordWithStatement()  { scope_contains_with_ = true; }
181 
182   // Inform the scope that the corresponding code contains an eval call.
RecordEvalCall()183   void RecordEvalCall()  { scope_calls_eval_ = true; }
184 
185 
186   // ---------------------------------------------------------------------------
187   // Predicates.
188 
189   // Specific scope types.
is_eval_scope()190   bool is_eval_scope() const  { return type_ == EVAL_SCOPE; }
is_function_scope()191   bool is_function_scope() const  { return type_ == FUNCTION_SCOPE; }
is_global_scope()192   bool is_global_scope() const  { return type_ == GLOBAL_SCOPE; }
193 
194   // Information about which scopes calls eval.
calls_eval()195   bool calls_eval() const  { return scope_calls_eval_; }
outer_scope_calls_eval()196   bool outer_scope_calls_eval() const  { return outer_scope_calls_eval_; }
197 
198   // Is this scope inside a with statement.
inside_with()199   bool inside_with() const  { return scope_inside_with_; }
200   // Does this scope contain a with statement.
contains_with()201   bool contains_with() const  { return scope_contains_with_; }
202 
203   // The scope immediately surrounding this scope, or NULL.
outer_scope()204   Scope* outer_scope() const  { return outer_scope_; }
205 
206   // ---------------------------------------------------------------------------
207   // Accessors.
208 
209   // The variable corresponding to the (function) receiver.
receiver()210   VariableProxy* receiver() const  { return receiver_; }
211 
212   // The variable holding the function literal for named function
213   // literals, or NULL.
214   // Only valid for function scopes.
function()215   Variable* function() const  {
216     ASSERT(is_function_scope());
217     return function_;
218   }
219 
220   // Parameters. The left-most parameter has index 0.
221   // Only valid for function scopes.
parameter(int index)222   Variable* parameter(int index) const  {
223     ASSERT(is_function_scope());
224     return params_[index];
225   }
226 
num_parameters()227   int num_parameters() const  { return params_.length(); }
228 
229   // The local variable 'arguments' if we need to allocate it; NULL otherwise.
230   // If arguments() exist, arguments_shadow() exists, too.
arguments()231   VariableProxy* arguments()  const  { return arguments_; }
232 
233   // The '.arguments' shadow variable if we need to allocate it; NULL otherwise.
234   // If arguments_shadow() exist, arguments() exists, too.
arguments_shadow()235   VariableProxy* arguments_shadow()  const  { return arguments_shadow_; }
236 
237   // Declarations list.
declarations()238   ZoneList<Declaration*>* declarations() { return &decls_; }
239 
240 
241 
242   // ---------------------------------------------------------------------------
243   // Variable allocation.
244 
245   // Collect all used locals in this scope.
246   template<class Allocator>
247   void CollectUsedVariables(List<Variable*, Allocator>* locals);
248 
249   // Resolve and fill in the allocation information for all variables
250   // in this scopes. Must be called *after* all scopes have been
251   // processed (parsed) to ensure that unresolved variables can be
252   // resolved properly.
253   //
254   // In the case of code compiled and run using 'eval', the context
255   // parameter is the context in which eval was called.  In all other
256   // cases the context parameter is an empty handle.
257   void AllocateVariables(Handle<Context> context);
258 
259   // Result of variable allocation.
num_stack_slots()260   int num_stack_slots() const  { return num_stack_slots_; }
num_heap_slots()261   int num_heap_slots() const  { return num_heap_slots_; }
262 
263   // Make sure this scope and all outer scopes are eagerly compiled.
ForceEagerCompilation()264   void ForceEagerCompilation()  { force_eager_compilation_ = true; }
265 
266   // Determine if we can use lazy compilation for this scope.
267   bool AllowsLazyCompilation() const;
268 
269   // True if the outer context of this scope is always the global context.
270   bool HasTrivialOuterContext() const;
271 
272   // The number of contexts between this and scope; zero if this == scope.
273   int ContextChainLength(Scope* scope);
274 
275 
276   // ---------------------------------------------------------------------------
277   // Debugging.
278 
279 #ifdef DEBUG
280   void Print(int n = 0);  // n = indentation; n < 0 => don't print recursively
281 #endif
282 
283   // ---------------------------------------------------------------------------
284   // Implementation.
285  protected:
286   friend class ParserFactory;
287 
288   explicit Scope(Type type);
289 
290   // Scope tree.
291   Scope* outer_scope_;  // the immediately enclosing outer scope, or NULL
292   ZoneList<Scope*> inner_scopes_;  // the immediately enclosed inner scopes
293 
294   // The scope type.
295   Type type_;
296 
297   // Debugging support.
298   Handle<String> scope_name_;
299 
300   // The variables declared in this scope:
301   //
302   // All user-declared variables (incl. parameters).  For global scopes
303   // variables may be implicitly 'declared' by being used (possibly in
304   // an inner scope) with no intervening with statements or eval calls.
305   VariableMap variables_;
306   // Compiler-allocated (user-invisible) temporaries.
307   ZoneList<Variable*> temps_;
308   // Parameter list in source order.
309   ZoneList<Variable*> params_;
310   // Variables that must be looked up dynamically.
311   DynamicScopePart* dynamics_;
312   // Unresolved variables referred to from this scope.
313   ZoneList<VariableProxy*> unresolved_;
314   // Declarations.
315   ZoneList<Declaration*> decls_;
316   // Convenience variable.
317   VariableProxy* receiver_;
318   // Function variable, if any; function scopes only.
319   Variable* function_;
320   // Convenience variable; function scopes only.
321   VariableProxy* arguments_;
322   // Convenience variable; function scopes only.
323   VariableProxy* arguments_shadow_;
324 
325   // Illegal redeclaration.
326   Expression* illegal_redecl_;
327 
328   // Scope-specific information.
329   bool scope_inside_with_;  // this scope is inside a 'with' of some outer scope
330   bool scope_contains_with_;  // this scope contains a 'with' statement
331   bool scope_calls_eval_;  // this scope contains an 'eval' call
332 
333   // Computed via PropagateScopeInfo.
334   bool outer_scope_calls_eval_;
335   bool inner_scope_calls_eval_;
336   bool outer_scope_is_eval_scope_;
337   bool force_eager_compilation_;
338 
339   // Computed via AllocateVariables; function scopes only.
340   int num_stack_slots_;
341   int num_heap_slots_;
342 
343   // Create a non-local variable with a given name.
344   // These variables are looked up dynamically at runtime.
345   Variable* NonLocal(Handle<String> name, Variable::Mode mode);
346 
347   // Variable resolution.
348   Variable* LookupRecursive(Handle<String> name,
349                             bool inner_lookup,
350                             Variable** invalidated_local);
351   void ResolveVariable(Scope* global_scope,
352                        Handle<Context> context,
353                        VariableProxy* proxy);
354   void ResolveVariablesRecursively(Scope* global_scope,
355                                    Handle<Context> context);
356 
357   // Scope analysis.
358   bool PropagateScopeInfo(bool outer_scope_calls_eval,
359                           bool outer_scope_is_eval_scope);
360   bool HasTrivialContext() const;
361 
362   // Predicates.
363   bool MustAllocate(Variable* var);
364   bool MustAllocateInContext(Variable* var);
365   bool HasArgumentsParameter();
366 
367   // Variable allocation.
368   void AllocateStackSlot(Variable* var);
369   void AllocateHeapSlot(Variable* var);
370   void AllocateParameterLocals();
371   void AllocateNonParameterLocal(Variable* var);
372   void AllocateNonParameterLocals();
373   void AllocateVariablesRecursively();
374 };
375 
376 
377 class DummyScope : public Scope {
378  public:
DummyScope()379   DummyScope() : Scope(GLOBAL_SCOPE) {
380     outer_scope_ = this;
381   }
382 
Lookup(Handle<String> name)383   virtual Variable* Lookup(Handle<String> name)  { return NULL; }
Declare(Handle<String> name,Variable::Mode mode)384   virtual Variable* Declare(Handle<String> name, Variable::Mode mode) {
385     return NULL;
386   }
NewUnresolved(Handle<String> name,bool inside_with)387   virtual VariableProxy* NewUnresolved(Handle<String> name, bool inside_with) {
388     return NULL;
389   }
NewTemporary(Handle<String> name)390   virtual VariableProxy* NewTemporary(Handle<String> name)  { return NULL; }
391 };
392 
393 
394 } }  // namespace v8::internal
395 
396 #endif  // V8_SCOPES_H_
397