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