Home | History | Annotate | Download | only in src
      1 // Copyright 2012 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 #include "v8.h"
     29 
     30 #include "scopes.h"
     31 
     32 #include "bootstrapper.h"
     33 #include "compiler.h"
     34 #include "messages.h"
     35 #include "scopeinfo.h"
     36 
     37 #include "allocation-inl.h"
     38 
     39 namespace v8 {
     40 namespace internal {
     41 
     42 // ----------------------------------------------------------------------------
     43 // Implementation of LocalsMap
     44 //
     45 // Note: We are storing the handle locations as key values in the hash map.
     46 //       When inserting a new variable via Declare(), we rely on the fact that
     47 //       the handle location remains alive for the duration of that variable
     48 //       use. Because a Variable holding a handle with the same location exists
     49 //       this is ensured.
     50 
     51 static bool Match(void* key1, void* key2) {
     52   String* name1 = *reinterpret_cast<String**>(key1);
     53   String* name2 = *reinterpret_cast<String**>(key2);
     54   ASSERT(name1->IsSymbol());
     55   ASSERT(name2->IsSymbol());
     56   return name1 == name2;
     57 }
     58 
     59 
     60 VariableMap::VariableMap() : ZoneHashMap(Match, 8) {}
     61 VariableMap::~VariableMap() {}
     62 
     63 
     64 Variable* VariableMap::Declare(
     65     Scope* scope,
     66     Handle<String> name,
     67     VariableMode mode,
     68     bool is_valid_lhs,
     69     Variable::Kind kind,
     70     InitializationFlag initialization_flag,
     71     Interface* interface) {
     72   Entry* p = ZoneHashMap::Lookup(name.location(), name->Hash(), true);
     73   if (p->value == NULL) {
     74     // The variable has not been declared yet -> insert it.
     75     ASSERT(p->key == name.location());
     76     p->value = new Variable(scope,
     77                             name,
     78                             mode,
     79                             is_valid_lhs,
     80                             kind,
     81                             initialization_flag,
     82                             interface);
     83   }
     84   return reinterpret_cast<Variable*>(p->value);
     85 }
     86 
     87 
     88 Variable* VariableMap::Lookup(Handle<String> name) {
     89   Entry* p = ZoneHashMap::Lookup(name.location(), name->Hash(), false);
     90   if (p != NULL) {
     91     ASSERT(*reinterpret_cast<String**>(p->key) == *name);
     92     ASSERT(p->value != NULL);
     93     return reinterpret_cast<Variable*>(p->value);
     94   }
     95   return NULL;
     96 }
     97 
     98 
     99 // ----------------------------------------------------------------------------
    100 // Implementation of Scope
    101 
    102 Scope::Scope(Scope* outer_scope, ScopeType type)
    103     : isolate_(Isolate::Current()),
    104       inner_scopes_(4),
    105       variables_(),
    106       temps_(4),
    107       params_(4),
    108       unresolved_(16),
    109       decls_(4),
    110       interface_(FLAG_harmony_modules &&
    111                  (type == MODULE_SCOPE || type == GLOBAL_SCOPE)
    112                      ? Interface::NewModule() : NULL),
    113       already_resolved_(false) {
    114   SetDefaults(type, outer_scope, Handle<ScopeInfo>::null());
    115   // At some point we might want to provide outer scopes to
    116   // eval scopes (by walking the stack and reading the scope info).
    117   // In that case, the ASSERT below needs to be adjusted.
    118   ASSERT_EQ(type == GLOBAL_SCOPE, outer_scope == NULL);
    119   ASSERT(!HasIllegalRedeclaration());
    120 }
    121 
    122 
    123 Scope::Scope(Scope* inner_scope,
    124              ScopeType type,
    125              Handle<ScopeInfo> scope_info)
    126     : isolate_(Isolate::Current()),
    127       inner_scopes_(4),
    128       variables_(),
    129       temps_(4),
    130       params_(4),
    131       unresolved_(16),
    132       decls_(4),
    133       interface_(NULL),
    134       already_resolved_(true) {
    135   SetDefaults(type, NULL, scope_info);
    136   if (!scope_info.is_null()) {
    137     num_heap_slots_ = scope_info_->ContextLength();
    138   }
    139   // Ensure at least MIN_CONTEXT_SLOTS to indicate a materialized context.
    140   num_heap_slots_ = Max(num_heap_slots_,
    141                         static_cast<int>(Context::MIN_CONTEXT_SLOTS));
    142   AddInnerScope(inner_scope);
    143 }
    144 
    145 
    146 Scope::Scope(Scope* inner_scope, Handle<String> catch_variable_name)
    147     : isolate_(Isolate::Current()),
    148       inner_scopes_(1),
    149       variables_(),
    150       temps_(0),
    151       params_(0),
    152       unresolved_(0),
    153       decls_(0),
    154       interface_(NULL),
    155       already_resolved_(true) {
    156   SetDefaults(CATCH_SCOPE, NULL, Handle<ScopeInfo>::null());
    157   AddInnerScope(inner_scope);
    158   ++num_var_or_const_;
    159   num_heap_slots_ = Context::MIN_CONTEXT_SLOTS;
    160   Variable* variable = variables_.Declare(this,
    161                                           catch_variable_name,
    162                                           VAR,
    163                                           true,  // Valid left-hand side.
    164                                           Variable::NORMAL,
    165                                           kCreatedInitialized);
    166   AllocateHeapSlot(variable);
    167 }
    168 
    169 
    170 void Scope::SetDefaults(ScopeType type,
    171                         Scope* outer_scope,
    172                         Handle<ScopeInfo> scope_info) {
    173   outer_scope_ = outer_scope;
    174   type_ = type;
    175   scope_name_ = isolate_->factory()->empty_symbol();
    176   dynamics_ = NULL;
    177   receiver_ = NULL;
    178   function_ = NULL;
    179   arguments_ = NULL;
    180   illegal_redecl_ = NULL;
    181   scope_inside_with_ = false;
    182   scope_contains_with_ = false;
    183   scope_calls_eval_ = false;
    184   // Inherit the strict mode from the parent scope.
    185   language_mode_ = (outer_scope != NULL)
    186       ? outer_scope->language_mode_ : CLASSIC_MODE;
    187   outer_scope_calls_non_strict_eval_ = false;
    188   inner_scope_calls_eval_ = false;
    189   force_eager_compilation_ = false;
    190   num_var_or_const_ = 0;
    191   num_stack_slots_ = 0;
    192   num_heap_slots_ = 0;
    193   scope_info_ = scope_info;
    194   start_position_ = RelocInfo::kNoPosition;
    195   end_position_ = RelocInfo::kNoPosition;
    196   if (!scope_info.is_null()) {
    197     scope_calls_eval_ = scope_info->CallsEval();
    198     language_mode_ = scope_info->language_mode();
    199   }
    200 }
    201 
    202 
    203 Scope* Scope::DeserializeScopeChain(Context* context, Scope* global_scope) {
    204   // Reconstruct the outer scope chain from a closure's context chain.
    205   Scope* current_scope = NULL;
    206   Scope* innermost_scope = NULL;
    207   bool contains_with = false;
    208   while (!context->IsGlobalContext()) {
    209     if (context->IsWithContext()) {
    210       Scope* with_scope = new Scope(current_scope,
    211                                     WITH_SCOPE,
    212                                     Handle<ScopeInfo>::null());
    213       current_scope = with_scope;
    214       // All the inner scopes are inside a with.
    215       contains_with = true;
    216       for (Scope* s = innermost_scope; s != NULL; s = s->outer_scope()) {
    217         s->scope_inside_with_ = true;
    218       }
    219     } else if (context->IsFunctionContext()) {
    220       ScopeInfo* scope_info = context->closure()->shared()->scope_info();
    221       current_scope = new Scope(current_scope,
    222                                 FUNCTION_SCOPE,
    223                                 Handle<ScopeInfo>(scope_info));
    224     } else if (context->IsBlockContext()) {
    225       ScopeInfo* scope_info = ScopeInfo::cast(context->extension());
    226       current_scope = new Scope(current_scope,
    227                                 BLOCK_SCOPE,
    228                                 Handle<ScopeInfo>(scope_info));
    229     } else {
    230       ASSERT(context->IsCatchContext());
    231       String* name = String::cast(context->extension());
    232       current_scope = new Scope(current_scope, Handle<String>(name));
    233     }
    234     if (contains_with) current_scope->RecordWithStatement();
    235     if (innermost_scope == NULL) innermost_scope = current_scope;
    236 
    237     // Forget about a with when we move to a context for a different function.
    238     if (context->previous()->closure() != context->closure()) {
    239       contains_with = false;
    240     }
    241     context = context->previous();
    242   }
    243 
    244   global_scope->AddInnerScope(current_scope);
    245   global_scope->PropagateScopeInfo(false);
    246   return (innermost_scope == NULL) ? global_scope : innermost_scope;
    247 }
    248 
    249 
    250 bool Scope::Analyze(CompilationInfo* info) {
    251   ASSERT(info->function() != NULL);
    252   Scope* scope = info->function()->scope();
    253   Scope* top = scope;
    254 
    255   // Traverse the scope tree up to the first unresolved scope or the global
    256   // scope and start scope resolution and variable allocation from that scope.
    257   while (!top->is_global_scope() &&
    258          !top->outer_scope()->already_resolved()) {
    259     top = top->outer_scope();
    260   }
    261 
    262   // Allocate the variables.
    263   {
    264     AstNodeFactory<AstNullVisitor> ast_node_factory(info->isolate());
    265     if (!top->AllocateVariables(info, &ast_node_factory)) return false;
    266   }
    267 
    268 #ifdef DEBUG
    269   if (info->isolate()->bootstrapper()->IsActive()
    270           ? FLAG_print_builtin_scopes
    271           : FLAG_print_scopes) {
    272     scope->Print();
    273   }
    274 
    275   if (FLAG_harmony_modules && FLAG_print_interfaces && top->is_global_scope()) {
    276     PrintF("global : ");
    277     top->interface()->Print();
    278   }
    279 #endif
    280 
    281   if (FLAG_harmony_scoping) {
    282     VariableProxy* proxy = scope->CheckAssignmentToConst();
    283     if (proxy != NULL) {
    284       // Found an assignment to const. Throw a syntax error.
    285       MessageLocation location(info->script(),
    286                                proxy->position(),
    287                                proxy->position());
    288       Isolate* isolate = info->isolate();
    289       Factory* factory = isolate->factory();
    290       Handle<JSArray> array = factory->NewJSArray(0);
    291       Handle<Object> result =
    292           factory->NewSyntaxError("harmony_const_assign", array);
    293       isolate->Throw(*result, &location);
    294       return false;
    295     }
    296   }
    297 
    298   info->SetScope(scope);
    299   return true;
    300 }
    301 
    302 
    303 void Scope::Initialize() {
    304   ASSERT(!already_resolved());
    305 
    306   // Add this scope as a new inner scope of the outer scope.
    307   if (outer_scope_ != NULL) {
    308     outer_scope_->inner_scopes_.Add(this);
    309     scope_inside_with_ = outer_scope_->scope_inside_with_ || is_with_scope();
    310   } else {
    311     scope_inside_with_ = is_with_scope();
    312   }
    313 
    314   // Declare convenience variables.
    315   // Declare and allocate receiver (even for the global scope, and even
    316   // if naccesses_ == 0).
    317   // NOTE: When loading parameters in the global scope, we must take
    318   // care not to access them as properties of the global object, but
    319   // instead load them directly from the stack. Currently, the only
    320   // such parameter is 'this' which is passed on the stack when
    321   // invoking scripts
    322   if (is_declaration_scope()) {
    323     Variable* var =
    324         variables_.Declare(this,
    325                            isolate_->factory()->this_symbol(),
    326                            VAR,
    327                            false,
    328                            Variable::THIS,
    329                            kCreatedInitialized);
    330     var->AllocateTo(Variable::PARAMETER, -1);
    331     receiver_ = var;
    332   } else {
    333     ASSERT(outer_scope() != NULL);
    334     receiver_ = outer_scope()->receiver();
    335   }
    336 
    337   if (is_function_scope()) {
    338     // Declare 'arguments' variable which exists in all functions.
    339     // Note that it might never be accessed, in which case it won't be
    340     // allocated during variable allocation.
    341     variables_.Declare(this,
    342                        isolate_->factory()->arguments_symbol(),
    343                        VAR,
    344                        true,
    345                        Variable::ARGUMENTS,
    346                        kCreatedInitialized);
    347   }
    348 }
    349 
    350 
    351 Scope* Scope::FinalizeBlockScope() {
    352   ASSERT(is_block_scope());
    353   ASSERT(temps_.is_empty());
    354   ASSERT(params_.is_empty());
    355 
    356   if (num_var_or_const() > 0) return this;
    357 
    358   // Remove this scope from outer scope.
    359   for (int i = 0; i < outer_scope_->inner_scopes_.length(); i++) {
    360     if (outer_scope_->inner_scopes_[i] == this) {
    361       outer_scope_->inner_scopes_.Remove(i);
    362       break;
    363     }
    364   }
    365 
    366   // Reparent inner scopes.
    367   for (int i = 0; i < inner_scopes_.length(); i++) {
    368     outer_scope()->AddInnerScope(inner_scopes_[i]);
    369   }
    370 
    371   // Move unresolved variables
    372   for (int i = 0; i < unresolved_.length(); i++) {
    373     outer_scope()->unresolved_.Add(unresolved_[i]);
    374   }
    375 
    376   return NULL;
    377 }
    378 
    379 
    380 Variable* Scope::LocalLookup(Handle<String> name) {
    381   Variable* result = variables_.Lookup(name);
    382   if (result != NULL || scope_info_.is_null()) {
    383     return result;
    384   }
    385   // If we have a serialized scope info, we might find the variable there.
    386   // There should be no local slot with the given name.
    387   ASSERT(scope_info_->StackSlotIndex(*name) < 0);
    388 
    389   // Check context slot lookup.
    390   VariableMode mode;
    391   InitializationFlag init_flag;
    392   int index = scope_info_->ContextSlotIndex(*name, &mode, &init_flag);
    393   if (index < 0) {
    394     // Check parameters.
    395     mode = VAR;
    396     init_flag = kCreatedInitialized;
    397     index = scope_info_->ParameterIndex(*name);
    398     if (index < 0) return NULL;
    399   }
    400 
    401   Variable* var =
    402       variables_.Declare(this,
    403                          name,
    404                          mode,
    405                          true,
    406                          Variable::NORMAL,
    407                          init_flag);
    408   var->AllocateTo(Variable::CONTEXT, index);
    409   return var;
    410 }
    411 
    412 
    413 Variable* Scope::LookupFunctionVar(Handle<String> name,
    414                                    AstNodeFactory<AstNullVisitor>* factory) {
    415   if (function_ != NULL && function_->name().is_identical_to(name)) {
    416     return function_->var();
    417   } else if (!scope_info_.is_null()) {
    418     // If we are backed by a scope info, try to lookup the variable there.
    419     VariableMode mode;
    420     int index = scope_info_->FunctionContextSlotIndex(*name, &mode);
    421     if (index < 0) return NULL;
    422     Variable* var = DeclareFunctionVar(name, mode, factory);
    423     var->AllocateTo(Variable::CONTEXT, index);
    424     return var;
    425   } else {
    426     return NULL;
    427   }
    428 }
    429 
    430 
    431 Variable* Scope::Lookup(Handle<String> name) {
    432   for (Scope* scope = this;
    433        scope != NULL;
    434        scope = scope->outer_scope()) {
    435     Variable* var = scope->LocalLookup(name);
    436     if (var != NULL) return var;
    437   }
    438   return NULL;
    439 }
    440 
    441 
    442 void Scope::DeclareParameter(Handle<String> name, VariableMode mode) {
    443   ASSERT(!already_resolved());
    444   ASSERT(is_function_scope());
    445   Variable* var = variables_.Declare(
    446       this, name, mode, true, Variable::NORMAL, kCreatedInitialized);
    447   params_.Add(var);
    448 }
    449 
    450 
    451 Variable* Scope::DeclareLocal(Handle<String> name,
    452                               VariableMode mode,
    453                               InitializationFlag init_flag,
    454                               Interface* interface) {
    455   ASSERT(!already_resolved());
    456   // This function handles VAR and CONST modes.  DYNAMIC variables are
    457   // introduces during variable allocation, INTERNAL variables are allocated
    458   // explicitly, and TEMPORARY variables are allocated via NewTemporary().
    459   ASSERT(mode == VAR ||
    460          mode == CONST ||
    461          mode == CONST_HARMONY ||
    462          mode == LET);
    463   ++num_var_or_const_;
    464   return variables_.Declare(
    465       this, name, mode, true, Variable::NORMAL, init_flag, interface);
    466 }
    467 
    468 
    469 Variable* Scope::DeclareGlobal(Handle<String> name) {
    470   ASSERT(is_global_scope());
    471   return variables_.Declare(this,
    472                             name,
    473                             DYNAMIC_GLOBAL,
    474                             true,
    475                             Variable::NORMAL,
    476                             kCreatedInitialized);
    477 }
    478 
    479 
    480 void Scope::RemoveUnresolved(VariableProxy* var) {
    481   // Most likely (always?) any variable we want to remove
    482   // was just added before, so we search backwards.
    483   for (int i = unresolved_.length(); i-- > 0;) {
    484     if (unresolved_[i] == var) {
    485       unresolved_.Remove(i);
    486       return;
    487     }
    488   }
    489 }
    490 
    491 
    492 Variable* Scope::NewTemporary(Handle<String> name) {
    493   ASSERT(!already_resolved());
    494   Variable* var = new Variable(this,
    495                                name,
    496                                TEMPORARY,
    497                                true,
    498                                Variable::NORMAL,
    499                                kCreatedInitialized);
    500   temps_.Add(var);
    501   return var;
    502 }
    503 
    504 
    505 void Scope::AddDeclaration(Declaration* declaration) {
    506   decls_.Add(declaration);
    507 }
    508 
    509 
    510 void Scope::SetIllegalRedeclaration(Expression* expression) {
    511   // Record only the first illegal redeclaration.
    512   if (!HasIllegalRedeclaration()) {
    513     illegal_redecl_ = expression;
    514   }
    515   ASSERT(HasIllegalRedeclaration());
    516 }
    517 
    518 
    519 void Scope::VisitIllegalRedeclaration(AstVisitor* visitor) {
    520   ASSERT(HasIllegalRedeclaration());
    521   illegal_redecl_->Accept(visitor);
    522 }
    523 
    524 
    525 Declaration* Scope::CheckConflictingVarDeclarations() {
    526   int length = decls_.length();
    527   for (int i = 0; i < length; i++) {
    528     Declaration* decl = decls_[i];
    529     if (decl->mode() != VAR) continue;
    530     Handle<String> name = decl->proxy()->name();
    531 
    532     // Iterate through all scopes until and including the declaration scope.
    533     Scope* previous = NULL;
    534     Scope* current = decl->scope();
    535     do {
    536       // There is a conflict if there exists a non-VAR binding.
    537       Variable* other_var = current->variables_.Lookup(name);
    538       if (other_var != NULL && other_var->mode() != VAR) {
    539         return decl;
    540       }
    541       previous = current;
    542       current = current->outer_scope_;
    543     } while (!previous->is_declaration_scope());
    544   }
    545   return NULL;
    546 }
    547 
    548 
    549 VariableProxy* Scope::CheckAssignmentToConst() {
    550   // Check this scope.
    551   if (is_extended_mode()) {
    552     for (int i = 0; i < unresolved_.length(); i++) {
    553       ASSERT(unresolved_[i]->var() != NULL);
    554       if (unresolved_[i]->var()->is_const_mode() &&
    555           unresolved_[i]->IsLValue()) {
    556         return unresolved_[i];
    557       }
    558     }
    559   }
    560 
    561   // Check inner scopes.
    562   for (int i = 0; i < inner_scopes_.length(); i++) {
    563     VariableProxy* proxy = inner_scopes_[i]->CheckAssignmentToConst();
    564     if (proxy != NULL) return proxy;
    565   }
    566 
    567   // No assignments to const found.
    568   return NULL;
    569 }
    570 
    571 
    572 void Scope::CollectStackAndContextLocals(ZoneList<Variable*>* stack_locals,
    573                                          ZoneList<Variable*>* context_locals) {
    574   ASSERT(stack_locals != NULL);
    575   ASSERT(context_locals != NULL);
    576 
    577   // Collect temporaries which are always allocated on the stack.
    578   for (int i = 0; i < temps_.length(); i++) {
    579     Variable* var = temps_[i];
    580     if (var->is_used()) {
    581       ASSERT(var->IsStackLocal());
    582       stack_locals->Add(var);
    583     }
    584   }
    585 
    586   // Collect declared local variables.
    587   for (VariableMap::Entry* p = variables_.Start();
    588        p != NULL;
    589        p = variables_.Next(p)) {
    590     Variable* var = reinterpret_cast<Variable*>(p->value);
    591     if (var->is_used()) {
    592       if (var->IsStackLocal()) {
    593         stack_locals->Add(var);
    594       } else if (var->IsContextSlot()) {
    595         context_locals->Add(var);
    596       }
    597     }
    598   }
    599 }
    600 
    601 
    602 bool Scope::AllocateVariables(CompilationInfo* info,
    603                               AstNodeFactory<AstNullVisitor>* factory) {
    604   // 1) Propagate scope information.
    605   bool outer_scope_calls_non_strict_eval = false;
    606   if (outer_scope_ != NULL) {
    607     outer_scope_calls_non_strict_eval =
    608         outer_scope_->outer_scope_calls_non_strict_eval() |
    609         outer_scope_->calls_non_strict_eval();
    610   }
    611   PropagateScopeInfo(outer_scope_calls_non_strict_eval);
    612 
    613   // 2) Resolve variables.
    614   if (!ResolveVariablesRecursively(info, factory)) return false;
    615 
    616   // 3) Allocate variables.
    617   AllocateVariablesRecursively();
    618 
    619   return true;
    620 }
    621 
    622 
    623 bool Scope::AllowsLazyCompilation() const {
    624   return !force_eager_compilation_ && HasTrivialOuterContext();
    625 }
    626 
    627 
    628 bool Scope::HasTrivialContext() const {
    629   // A function scope has a trivial context if it always is the global
    630   // context. We iteratively scan out the context chain to see if
    631   // there is anything that makes this scope non-trivial; otherwise we
    632   // return true.
    633   for (const Scope* scope = this; scope != NULL; scope = scope->outer_scope_) {
    634     if (scope->is_eval_scope()) return false;
    635     if (scope->scope_inside_with_) return false;
    636     if (scope->num_heap_slots_ > 0) return false;
    637   }
    638   return true;
    639 }
    640 
    641 
    642 bool Scope::HasTrivialOuterContext() const {
    643   Scope* outer = outer_scope_;
    644   if (outer == NULL) return true;
    645   // Note that the outer context may be trivial in general, but the current
    646   // scope may be inside a 'with' statement in which case the outer context
    647   // for this scope is not trivial.
    648   return !scope_inside_with_ && outer->HasTrivialContext();
    649 }
    650 
    651 
    652 bool Scope::AllowsLazyRecompilation() const {
    653   return !force_eager_compilation_ &&
    654          !TrivialDeclarationScopesBeforeWithScope();
    655 }
    656 
    657 
    658 bool Scope::TrivialDeclarationScopesBeforeWithScope() const {
    659   Scope* outer = outer_scope_;
    660   if (outer == NULL) return false;
    661   outer = outer->DeclarationScope();
    662   while (outer != NULL) {
    663     if (outer->is_with_scope()) return true;
    664     if (outer->is_declaration_scope() && outer->num_heap_slots() > 0)
    665       return false;
    666     outer = outer->outer_scope_;
    667   }
    668   return false;
    669 }
    670 
    671 
    672 int Scope::ContextChainLength(Scope* scope) {
    673   int n = 0;
    674   for (Scope* s = this; s != scope; s = s->outer_scope_) {
    675     ASSERT(s != NULL);  // scope must be in the scope chain
    676     if (s->num_heap_slots() > 0) n++;
    677   }
    678   return n;
    679 }
    680 
    681 
    682 Scope* Scope::DeclarationScope() {
    683   Scope* scope = this;
    684   while (!scope->is_declaration_scope()) {
    685     scope = scope->outer_scope();
    686   }
    687   return scope;
    688 }
    689 
    690 
    691 Handle<ScopeInfo> Scope::GetScopeInfo() {
    692   if (scope_info_.is_null()) {
    693     scope_info_ = ScopeInfo::Create(this);
    694   }
    695   return scope_info_;
    696 }
    697 
    698 
    699 void Scope::GetNestedScopeChain(
    700     List<Handle<ScopeInfo> >* chain,
    701     int position) {
    702   if (!is_eval_scope()) chain->Add(Handle<ScopeInfo>(GetScopeInfo()));
    703 
    704   for (int i = 0; i < inner_scopes_.length(); i++) {
    705     Scope* scope = inner_scopes_[i];
    706     int beg_pos = scope->start_position();
    707     int end_pos = scope->end_position();
    708     ASSERT(beg_pos >= 0 && end_pos >= 0);
    709     if (beg_pos <= position && position < end_pos) {
    710       scope->GetNestedScopeChain(chain, position);
    711       return;
    712     }
    713   }
    714 }
    715 
    716 
    717 #ifdef DEBUG
    718 static const char* Header(ScopeType type) {
    719   switch (type) {
    720     case EVAL_SCOPE: return "eval";
    721     case FUNCTION_SCOPE: return "function";
    722     case MODULE_SCOPE: return "module";
    723     case GLOBAL_SCOPE: return "global";
    724     case CATCH_SCOPE: return "catch";
    725     case BLOCK_SCOPE: return "block";
    726     case WITH_SCOPE: return "with";
    727   }
    728   UNREACHABLE();
    729   return NULL;
    730 }
    731 
    732 
    733 static void Indent(int n, const char* str) {
    734   PrintF("%*s%s", n, "", str);
    735 }
    736 
    737 
    738 static void PrintName(Handle<String> name) {
    739   SmartArrayPointer<char> s = name->ToCString(DISALLOW_NULLS);
    740   PrintF("%s", *s);
    741 }
    742 
    743 
    744 static void PrintLocation(Variable* var) {
    745   switch (var->location()) {
    746     case Variable::UNALLOCATED:
    747       break;
    748     case Variable::PARAMETER:
    749       PrintF("parameter[%d]", var->index());
    750       break;
    751     case Variable::LOCAL:
    752       PrintF("local[%d]", var->index());
    753       break;
    754     case Variable::CONTEXT:
    755       PrintF("context[%d]", var->index());
    756       break;
    757     case Variable::LOOKUP:
    758       PrintF("lookup");
    759       break;
    760   }
    761 }
    762 
    763 
    764 static void PrintVar(int indent, Variable* var) {
    765   if (var->is_used() || !var->IsUnallocated()) {
    766     Indent(indent, Variable::Mode2String(var->mode()));
    767     PrintF(" ");
    768     PrintName(var->name());
    769     PrintF(";  // ");
    770     PrintLocation(var);
    771     if (var->has_forced_context_allocation()) {
    772       if (!var->IsUnallocated()) PrintF(", ");
    773       PrintF("forced context allocation");
    774     }
    775     PrintF("\n");
    776   }
    777 }
    778 
    779 
    780 static void PrintMap(int indent, VariableMap* map) {
    781   for (VariableMap::Entry* p = map->Start(); p != NULL; p = map->Next(p)) {
    782     Variable* var = reinterpret_cast<Variable*>(p->value);
    783     PrintVar(indent, var);
    784   }
    785 }
    786 
    787 
    788 void Scope::Print(int n) {
    789   int n0 = (n > 0 ? n : 0);
    790   int n1 = n0 + 2;  // indentation
    791 
    792   // Print header.
    793   Indent(n0, Header(type_));
    794   if (scope_name_->length() > 0) {
    795     PrintF(" ");
    796     PrintName(scope_name_);
    797   }
    798 
    799   // Print parameters, if any.
    800   if (is_function_scope()) {
    801     PrintF(" (");
    802     for (int i = 0; i < params_.length(); i++) {
    803       if (i > 0) PrintF(", ");
    804       PrintName(params_[i]->name());
    805     }
    806     PrintF(")");
    807   }
    808 
    809   PrintF(" { // (%d, %d)\n", start_position(), end_position());
    810 
    811   // Function name, if any (named function literals, only).
    812   if (function_ != NULL) {
    813     Indent(n1, "// (local) function name: ");
    814     PrintName(function_->name());
    815     PrintF("\n");
    816   }
    817 
    818   // Scope info.
    819   if (HasTrivialOuterContext()) {
    820     Indent(n1, "// scope has trivial outer context\n");
    821   }
    822   switch (language_mode()) {
    823     case CLASSIC_MODE:
    824       break;
    825     case STRICT_MODE:
    826       Indent(n1, "// strict mode scope\n");
    827       break;
    828     case EXTENDED_MODE:
    829       Indent(n1, "// extended mode scope\n");
    830       break;
    831   }
    832   if (scope_inside_with_) Indent(n1, "// scope inside 'with'\n");
    833   if (scope_contains_with_) Indent(n1, "// scope contains 'with'\n");
    834   if (scope_calls_eval_) Indent(n1, "// scope calls 'eval'\n");
    835   if (outer_scope_calls_non_strict_eval_) {
    836     Indent(n1, "// outer scope calls 'eval' in non-strict context\n");
    837   }
    838   if (inner_scope_calls_eval_) Indent(n1, "// inner scope calls 'eval'\n");
    839   if (num_stack_slots_ > 0) { Indent(n1, "// ");
    840   PrintF("%d stack slots\n", num_stack_slots_); }
    841   if (num_heap_slots_ > 0) { Indent(n1, "// ");
    842   PrintF("%d heap slots\n", num_heap_slots_); }
    843 
    844   // Print locals.
    845   Indent(n1, "// function var\n");
    846   if (function_ != NULL) {
    847     PrintVar(n1, function_->var());
    848   }
    849 
    850   Indent(n1, "// temporary vars\n");
    851   for (int i = 0; i < temps_.length(); i++) {
    852     PrintVar(n1, temps_[i]);
    853   }
    854 
    855   Indent(n1, "// local vars\n");
    856   PrintMap(n1, &variables_);
    857 
    858   Indent(n1, "// dynamic vars\n");
    859   if (dynamics_ != NULL) {
    860     PrintMap(n1, dynamics_->GetMap(DYNAMIC));
    861     PrintMap(n1, dynamics_->GetMap(DYNAMIC_LOCAL));
    862     PrintMap(n1, dynamics_->GetMap(DYNAMIC_GLOBAL));
    863   }
    864 
    865   // Print inner scopes (disable by providing negative n).
    866   if (n >= 0) {
    867     for (int i = 0; i < inner_scopes_.length(); i++) {
    868       PrintF("\n");
    869       inner_scopes_[i]->Print(n1);
    870     }
    871   }
    872 
    873   Indent(n0, "}\n");
    874 }
    875 #endif  // DEBUG
    876 
    877 
    878 Variable* Scope::NonLocal(Handle<String> name, VariableMode mode) {
    879   if (dynamics_ == NULL) dynamics_ = new DynamicScopePart();
    880   VariableMap* map = dynamics_->GetMap(mode);
    881   Variable* var = map->Lookup(name);
    882   if (var == NULL) {
    883     // Declare a new non-local.
    884     InitializationFlag init_flag = (mode == VAR)
    885         ? kCreatedInitialized : kNeedsInitialization;
    886     var = map->Declare(NULL,
    887                        name,
    888                        mode,
    889                        true,
    890                        Variable::NORMAL,
    891                        init_flag);
    892     // Allocate it by giving it a dynamic lookup.
    893     var->AllocateTo(Variable::LOOKUP, -1);
    894   }
    895   return var;
    896 }
    897 
    898 
    899 Variable* Scope::LookupRecursive(Handle<String> name,
    900                                  BindingKind* binding_kind,
    901                                  AstNodeFactory<AstNullVisitor>* factory) {
    902   ASSERT(binding_kind != NULL);
    903   // Try to find the variable in this scope.
    904   Variable* var = LocalLookup(name);
    905 
    906   // We found a variable and we are done. (Even if there is an 'eval' in
    907   // this scope which introduces the same variable again, the resulting
    908   // variable remains the same.)
    909   if (var != NULL) {
    910     *binding_kind = BOUND;
    911     return var;
    912   }
    913 
    914   // We did not find a variable locally. Check against the function variable,
    915   // if any. We can do this for all scopes, since the function variable is
    916   // only present - if at all - for function scopes.
    917   *binding_kind = UNBOUND;
    918   var = LookupFunctionVar(name, factory);
    919   if (var != NULL) {
    920     *binding_kind = BOUND;
    921   } else if (outer_scope_ != NULL) {
    922     var = outer_scope_->LookupRecursive(name, binding_kind, factory);
    923     if (*binding_kind == BOUND && (is_function_scope() || is_with_scope())) {
    924       var->ForceContextAllocation();
    925     }
    926   } else {
    927     ASSERT(is_global_scope());
    928   }
    929 
    930   if (is_with_scope()) {
    931     // The current scope is a with scope, so the variable binding can not be
    932     // statically resolved. However, note that it was necessary to do a lookup
    933     // in the outer scope anyway, because if a binding exists in an outer scope,
    934     // the associated variable has to be marked as potentially being accessed
    935     // from inside of an inner with scope (the property may not be in the 'with'
    936     // object).
    937     *binding_kind = DYNAMIC_LOOKUP;
    938     return NULL;
    939   } else if (calls_non_strict_eval()) {
    940     // A variable binding may have been found in an outer scope, but the current
    941     // scope makes a non-strict 'eval' call, so the found variable may not be
    942     // the correct one (the 'eval' may introduce a binding with the same name).
    943     // In that case, change the lookup result to reflect this situation.
    944     if (*binding_kind == BOUND) {
    945       *binding_kind = BOUND_EVAL_SHADOWED;
    946     } else if (*binding_kind == UNBOUND) {
    947       *binding_kind = UNBOUND_EVAL_SHADOWED;
    948     }
    949   }
    950   return var;
    951 }
    952 
    953 
    954 bool Scope::ResolveVariable(CompilationInfo* info,
    955                             VariableProxy* proxy,
    956                             AstNodeFactory<AstNullVisitor>* factory) {
    957   ASSERT(info->global_scope()->is_global_scope());
    958 
    959   // If the proxy is already resolved there's nothing to do
    960   // (functions and consts may be resolved by the parser).
    961   if (proxy->var() != NULL) return true;
    962 
    963   // Otherwise, try to resolve the variable.
    964   BindingKind binding_kind;
    965   Variable* var = LookupRecursive(proxy->name(), &binding_kind, factory);
    966   switch (binding_kind) {
    967     case BOUND:
    968       // We found a variable binding.
    969       break;
    970 
    971     case BOUND_EVAL_SHADOWED:
    972       // We found a variable variable binding that might be shadowed
    973       // by 'eval' introduced variable bindings.
    974       if (var->is_global()) {
    975         var = NonLocal(proxy->name(), DYNAMIC_GLOBAL);
    976       } else {
    977         Variable* invalidated = var;
    978         var = NonLocal(proxy->name(), DYNAMIC_LOCAL);
    979         var->set_local_if_not_shadowed(invalidated);
    980       }
    981       break;
    982 
    983     case UNBOUND:
    984       // No binding has been found. Declare a variable in global scope.
    985       var = info->global_scope()->DeclareGlobal(proxy->name());
    986       break;
    987 
    988     case UNBOUND_EVAL_SHADOWED:
    989       // No binding has been found. But some scope makes a
    990       // non-strict 'eval' call.
    991       var = NonLocal(proxy->name(), DYNAMIC_GLOBAL);
    992       break;
    993 
    994     case DYNAMIC_LOOKUP:
    995       // The variable could not be resolved statically.
    996       var = NonLocal(proxy->name(), DYNAMIC);
    997       break;
    998   }
    999 
   1000   ASSERT(var != NULL);
   1001   proxy->BindTo(var);
   1002 
   1003   if (FLAG_harmony_modules) {
   1004     bool ok;
   1005 #ifdef DEBUG
   1006     if (FLAG_print_interface_details)
   1007       PrintF("# Resolve %s:\n", var->name()->ToAsciiArray());
   1008 #endif
   1009     proxy->interface()->Unify(var->interface(), &ok);
   1010     if (!ok) {
   1011 #ifdef DEBUG
   1012       if (FLAG_print_interfaces) {
   1013         PrintF("SCOPES TYPE ERROR\n");
   1014         PrintF("proxy: ");
   1015         proxy->interface()->Print();
   1016         PrintF("var: ");
   1017         var->interface()->Print();
   1018       }
   1019 #endif
   1020 
   1021       // Inconsistent use of module. Throw a syntax error.
   1022       // TODO(rossberg): generate more helpful error message.
   1023       MessageLocation location(info->script(),
   1024                                proxy->position(),
   1025                                proxy->position());
   1026       Isolate* isolate = Isolate::Current();
   1027       Factory* factory = isolate->factory();
   1028       Handle<JSArray> array = factory->NewJSArray(1);
   1029       USE(JSObject::SetElement(array, 0, var->name(), NONE, kStrictMode));
   1030       Handle<Object> result =
   1031           factory->NewSyntaxError("module_type_error", array);
   1032       isolate->Throw(*result, &location);
   1033       return false;
   1034     }
   1035   }
   1036 
   1037   return true;
   1038 }
   1039 
   1040 
   1041 bool Scope::ResolveVariablesRecursively(
   1042     CompilationInfo* info,
   1043     AstNodeFactory<AstNullVisitor>* factory) {
   1044   ASSERT(info->global_scope()->is_global_scope());
   1045 
   1046   // Resolve unresolved variables for this scope.
   1047   for (int i = 0; i < unresolved_.length(); i++) {
   1048     if (!ResolveVariable(info, unresolved_[i], factory)) return false;
   1049   }
   1050 
   1051   // Resolve unresolved variables for inner scopes.
   1052   for (int i = 0; i < inner_scopes_.length(); i++) {
   1053     if (!inner_scopes_[i]->ResolveVariablesRecursively(info, factory))
   1054       return false;
   1055   }
   1056 
   1057   return true;
   1058 }
   1059 
   1060 
   1061 bool Scope::PropagateScopeInfo(bool outer_scope_calls_non_strict_eval ) {
   1062   if (outer_scope_calls_non_strict_eval) {
   1063     outer_scope_calls_non_strict_eval_ = true;
   1064   }
   1065 
   1066   bool calls_non_strict_eval =
   1067       this->calls_non_strict_eval() || outer_scope_calls_non_strict_eval_;
   1068   for (int i = 0; i < inner_scopes_.length(); i++) {
   1069     Scope* inner_scope = inner_scopes_[i];
   1070     if (inner_scope->PropagateScopeInfo(calls_non_strict_eval)) {
   1071       inner_scope_calls_eval_ = true;
   1072     }
   1073     if (inner_scope->force_eager_compilation_) {
   1074       force_eager_compilation_ = true;
   1075     }
   1076   }
   1077 
   1078   return scope_calls_eval_ || inner_scope_calls_eval_;
   1079 }
   1080 
   1081 
   1082 bool Scope::MustAllocate(Variable* var) {
   1083   // Give var a read/write use if there is a chance it might be accessed
   1084   // via an eval() call.  This is only possible if the variable has a
   1085   // visible name.
   1086   if ((var->is_this() || var->name()->length() > 0) &&
   1087       (var->has_forced_context_allocation() ||
   1088        scope_calls_eval_ ||
   1089        inner_scope_calls_eval_ ||
   1090        scope_contains_with_ ||
   1091        is_catch_scope() ||
   1092        is_block_scope())) {
   1093     var->set_is_used(true);
   1094   }
   1095   // Global variables do not need to be allocated.
   1096   return !var->is_global() && var->is_used();
   1097 }
   1098 
   1099 
   1100 bool Scope::MustAllocateInContext(Variable* var) {
   1101   // If var is accessed from an inner scope, or if there is a possibility
   1102   // that it might be accessed from the current or an inner scope (through
   1103   // an eval() call or a runtime with lookup), it must be allocated in the
   1104   // context.
   1105   //
   1106   // Exceptions: temporary variables are never allocated in a context;
   1107   // catch-bound variables are always allocated in a context.
   1108   if (var->mode() == TEMPORARY) return false;
   1109   if (is_catch_scope() || is_block_scope()) return true;
   1110   return var->has_forced_context_allocation() ||
   1111       scope_calls_eval_ ||
   1112       inner_scope_calls_eval_ ||
   1113       scope_contains_with_ ||
   1114       var->is_global();
   1115 }
   1116 
   1117 
   1118 bool Scope::HasArgumentsParameter() {
   1119   for (int i = 0; i < params_.length(); i++) {
   1120     if (params_[i]->name().is_identical_to(
   1121             isolate_->factory()->arguments_symbol())) {
   1122       return true;
   1123     }
   1124   }
   1125   return false;
   1126 }
   1127 
   1128 
   1129 void Scope::AllocateStackSlot(Variable* var) {
   1130   var->AllocateTo(Variable::LOCAL, num_stack_slots_++);
   1131 }
   1132 
   1133 
   1134 void Scope::AllocateHeapSlot(Variable* var) {
   1135   var->AllocateTo(Variable::CONTEXT, num_heap_slots_++);
   1136 }
   1137 
   1138 
   1139 void Scope::AllocateParameterLocals() {
   1140   ASSERT(is_function_scope());
   1141   Variable* arguments = LocalLookup(isolate_->factory()->arguments_symbol());
   1142   ASSERT(arguments != NULL);  // functions have 'arguments' declared implicitly
   1143 
   1144   bool uses_nonstrict_arguments = false;
   1145 
   1146   if (MustAllocate(arguments) && !HasArgumentsParameter()) {
   1147     // 'arguments' is used. Unless there is also a parameter called
   1148     // 'arguments', we must be conservative and allocate all parameters to
   1149     // the context assuming they will be captured by the arguments object.
   1150     // If we have a parameter named 'arguments', a (new) value is always
   1151     // assigned to it via the function invocation. Then 'arguments' denotes
   1152     // that specific parameter value and cannot be used to access the
   1153     // parameters, which is why we don't need to allocate an arguments
   1154     // object in that case.
   1155 
   1156     // We are using 'arguments'. Tell the code generator that is needs to
   1157     // allocate the arguments object by setting 'arguments_'.
   1158     arguments_ = arguments;
   1159 
   1160     // In strict mode 'arguments' does not alias formal parameters.
   1161     // Therefore in strict mode we allocate parameters as if 'arguments'
   1162     // were not used.
   1163     uses_nonstrict_arguments = is_classic_mode();
   1164   }
   1165 
   1166   // The same parameter may occur multiple times in the parameters_ list.
   1167   // If it does, and if it is not copied into the context object, it must
   1168   // receive the highest parameter index for that parameter; thus iteration
   1169   // order is relevant!
   1170   for (int i = params_.length() - 1; i >= 0; --i) {
   1171     Variable* var = params_[i];
   1172     ASSERT(var->scope() == this);
   1173     if (uses_nonstrict_arguments) {
   1174       // Force context allocation of the parameter.
   1175       var->ForceContextAllocation();
   1176     }
   1177 
   1178     if (MustAllocate(var)) {
   1179       if (MustAllocateInContext(var)) {
   1180         ASSERT(var->IsUnallocated() || var->IsContextSlot());
   1181         if (var->IsUnallocated()) {
   1182           AllocateHeapSlot(var);
   1183         }
   1184       } else {
   1185         ASSERT(var->IsUnallocated() || var->IsParameter());
   1186         if (var->IsUnallocated()) {
   1187           var->AllocateTo(Variable::PARAMETER, i);
   1188         }
   1189       }
   1190     }
   1191   }
   1192 }
   1193 
   1194 
   1195 void Scope::AllocateNonParameterLocal(Variable* var) {
   1196   ASSERT(var->scope() == this);
   1197   ASSERT(!var->IsVariable(isolate_->factory()->result_symbol()) ||
   1198          !var->IsStackLocal());
   1199   if (var->IsUnallocated() && MustAllocate(var)) {
   1200     if (MustAllocateInContext(var)) {
   1201       AllocateHeapSlot(var);
   1202     } else {
   1203       AllocateStackSlot(var);
   1204     }
   1205   }
   1206 }
   1207 
   1208 
   1209 void Scope::AllocateNonParameterLocals() {
   1210   // All variables that have no rewrite yet are non-parameter locals.
   1211   for (int i = 0; i < temps_.length(); i++) {
   1212     AllocateNonParameterLocal(temps_[i]);
   1213   }
   1214 
   1215   for (VariableMap::Entry* p = variables_.Start();
   1216        p != NULL;
   1217        p = variables_.Next(p)) {
   1218     Variable* var = reinterpret_cast<Variable*>(p->value);
   1219     AllocateNonParameterLocal(var);
   1220   }
   1221 
   1222   // For now, function_ must be allocated at the very end.  If it gets
   1223   // allocated in the context, it must be the last slot in the context,
   1224   // because of the current ScopeInfo implementation (see
   1225   // ScopeInfo::ScopeInfo(FunctionScope* scope) constructor).
   1226   if (function_ != NULL) {
   1227     AllocateNonParameterLocal(function_->var());
   1228   }
   1229 }
   1230 
   1231 
   1232 void Scope::AllocateVariablesRecursively() {
   1233   // Allocate variables for inner scopes.
   1234   for (int i = 0; i < inner_scopes_.length(); i++) {
   1235     inner_scopes_[i]->AllocateVariablesRecursively();
   1236   }
   1237 
   1238   // If scope is already resolved, we still need to allocate
   1239   // variables in inner scopes which might not had been resolved yet.
   1240   if (already_resolved()) return;
   1241   // The number of slots required for variables.
   1242   num_stack_slots_ = 0;
   1243   num_heap_slots_ = Context::MIN_CONTEXT_SLOTS;
   1244 
   1245   // Allocate variables for this scope.
   1246   // Parameters must be allocated first, if any.
   1247   if (is_function_scope()) AllocateParameterLocals();
   1248   AllocateNonParameterLocals();
   1249 
   1250   // Force allocation of a context for this scope if necessary. For a 'with'
   1251   // scope and for a function scope that makes an 'eval' call we need a context,
   1252   // even if no local variables were statically allocated in the scope.
   1253   bool must_have_context = is_with_scope() ||
   1254       (is_function_scope() && calls_eval());
   1255 
   1256   // If we didn't allocate any locals in the local context, then we only
   1257   // need the minimal number of slots if we must have a context.
   1258   if (num_heap_slots_ == Context::MIN_CONTEXT_SLOTS && !must_have_context) {
   1259     num_heap_slots_ = 0;
   1260   }
   1261 
   1262   // Allocation done.
   1263   ASSERT(num_heap_slots_ == 0 || num_heap_slots_ >= Context::MIN_CONTEXT_SLOTS);
   1264 }
   1265 
   1266 
   1267 int Scope::StackLocalCount() const {
   1268   return num_stack_slots() -
   1269       (function_ != NULL && function_->var()->IsStackLocal() ? 1 : 0);
   1270 }
   1271 
   1272 
   1273 int Scope::ContextLocalCount() const {
   1274   if (num_heap_slots() == 0) return 0;
   1275   return num_heap_slots() - Context::MIN_CONTEXT_SLOTS -
   1276       (function_ != NULL && function_->var()->IsContextSlot() ? 1 : 0);
   1277 }
   1278 
   1279 } }  // namespace v8::internal
   1280