Home | History | Annotate | Download | only in src 
      1 // Copyright 2011 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 <stdlib.h>
     29 
     30 #include "v8.h"
     31 
     32 #include "scopeinfo.h"
     33 #include "scopes.h"
     34 
     35 #include "allocation-inl.h"
     36 
     37 namespace v8 {
     38 namespace internal {
     39 
     40 
     41 Handle<ScopeInfo> ScopeInfo::Create(Scope* scope) {
     42   // Collect stack and context locals.
     43   ZoneList<Variable*> stack_locals(scope->StackLocalCount());
     44   ZoneList<Variable*> context_locals(scope->ContextLocalCount());
     45   scope->CollectStackAndContextLocals(&stack_locals, &context_locals);
     46   const int stack_local_count = stack_locals.length();
     47   const int context_local_count = context_locals.length();
     48   // Make sure we allocate the correct amount.
     49   ASSERT(scope->StackLocalCount() == stack_local_count);
     50   ASSERT(scope->ContextLocalCount() == context_local_count);
     51 
     52   // Determine use and location of the function variable if it is present.
     53   FunctionVariableInfo function_name_info;
     54   VariableMode function_variable_mode;
     55   if (scope->is_function_scope() && scope->function() != NULL) {
     56     Variable* var = scope->function()->var();
     57     if (!var->is_used()) {
     58       function_name_info = UNUSED;
     59     } else if (var->IsContextSlot()) {
     60       function_name_info = CONTEXT;
     61     } else {
     62       ASSERT(var->IsStackLocal());
     63       function_name_info = STACK;
     64     }
     65     function_variable_mode = var->mode();
     66   } else {
     67     function_name_info = NONE;
     68     function_variable_mode = VAR;
     69   }
     70 
     71   const bool has_function_name = function_name_info != NONE;
     72   const int parameter_count = scope->num_parameters();
     73   const int length = kVariablePartIndex
     74       + parameter_count + stack_local_count + 2 * context_local_count
     75       + (has_function_name ? 2 : 0);
     76 
     77   Handle<ScopeInfo> scope_info = FACTORY->NewScopeInfo(length);
     78 
     79   // Encode the flags.
     80   int flags = TypeField::encode(scope->type()) |
     81       CallsEvalField::encode(scope->calls_eval()) |
     82       LanguageModeField::encode(scope->language_mode()) |
     83       FunctionVariableField::encode(function_name_info) |
     84       FunctionVariableMode::encode(function_variable_mode);
     85   scope_info->SetFlags(flags);
     86   scope_info->SetParameterCount(parameter_count);
     87   scope_info->SetStackLocalCount(stack_local_count);
     88   scope_info->SetContextLocalCount(context_local_count);
     89 
     90   int index = kVariablePartIndex;
     91   // Add parameters.
     92   ASSERT(index == scope_info->ParameterEntriesIndex());
     93   for (int i = 0; i < parameter_count; ++i) {
     94     scope_info->set(index++, *scope->parameter(i)->name());
     95   }
     96 
     97   // Add stack locals' names. We are assuming that the stack locals'
     98   // slots are allocated in increasing order, so we can simply add
     99   // them to the ScopeInfo object.
    100   ASSERT(index == scope_info->StackLocalEntriesIndex());
    101   for (int i = 0; i < stack_local_count; ++i) {
    102     ASSERT(stack_locals[i]->index() == i);
    103     scope_info->set(index++, *stack_locals[i]->name());
    104   }
    105 
    106   // Due to usage analysis, context-allocated locals are not necessarily in
    107   // increasing order: Some of them may be parameters which are allocated before
    108   // the non-parameter locals. When the non-parameter locals are sorted
    109   // according to usage, the allocated slot indices may not be in increasing
    110   // order with the variable list anymore. Thus, we first need to sort them by
    111   // context slot index before adding them to the ScopeInfo object.
    112   context_locals.Sort(&Variable::CompareIndex);
    113 
    114   // Add context locals' names.
    115   ASSERT(index == scope_info->ContextLocalNameEntriesIndex());
    116   for (int i = 0; i < context_local_count; ++i) {
    117     scope_info->set(index++, *context_locals[i]->name());
    118   }
    119 
    120   // Add context locals' info.
    121   ASSERT(index == scope_info->ContextLocalInfoEntriesIndex());
    122   for (int i = 0; i < context_local_count; ++i) {
    123     Variable* var = context_locals[i];
    124     uint32_t value = ContextLocalMode::encode(var->mode()) |
    125         ContextLocalInitFlag::encode(var->initialization_flag());
    126     scope_info->set(index++, Smi::FromInt(value));
    127   }
    128 
    129   // If present, add the function variable name and its index.
    130   ASSERT(index == scope_info->FunctionNameEntryIndex());
    131   if (has_function_name) {
    132     int var_index = scope->function()->var()->index();
    133     scope_info->set(index++, *scope->function()->name());
    134     scope_info->set(index++, Smi::FromInt(var_index));
    135     ASSERT(function_name_info != STACK ||
    136            (var_index == scope_info->StackLocalCount() &&
    137             var_index == scope_info->StackSlotCount() - 1));
    138     ASSERT(function_name_info != CONTEXT ||
    139            var_index == scope_info->ContextLength() - 1);
    140   }
    141 
    142   ASSERT(index == scope_info->length());
    143   ASSERT(scope->num_parameters() == scope_info->ParameterCount());
    144   ASSERT(scope->num_stack_slots() == scope_info->StackSlotCount());
    145   ASSERT(scope->num_heap_slots() == scope_info->ContextLength());
    146   return scope_info;
    147 }
    148 
    149 
    150 ScopeInfo* ScopeInfo::Empty() {
    151   return reinterpret_cast<ScopeInfo*>(HEAP->empty_fixed_array());
    152 }
    153 
    154 
    155 ScopeType ScopeInfo::Type() {
    156   ASSERT(length() > 0);
    157   return TypeField::decode(Flags());
    158 }
    159 
    160 
    161 bool ScopeInfo::CallsEval() {
    162   return length() > 0 && CallsEvalField::decode(Flags());
    163 }
    164 
    165 
    166 LanguageMode ScopeInfo::language_mode() {
    167   return length() > 0 ? LanguageModeField::decode(Flags()) : CLASSIC_MODE;
    168 }
    169 
    170 
    171 int ScopeInfo::LocalCount() {
    172   return StackLocalCount() + ContextLocalCount();
    173 }
    174 
    175 
    176 int ScopeInfo::StackSlotCount() {
    177   if (length() > 0) {
    178     bool function_name_stack_slot =
    179         FunctionVariableField::decode(Flags()) == STACK;
    180     return StackLocalCount() + (function_name_stack_slot ? 1 : 0);
    181   }
    182   return 0;
    183 }
    184 
    185 
    186 int ScopeInfo::ContextLength() {
    187   if (length() > 0) {
    188     int context_locals = ContextLocalCount();
    189     bool function_name_context_slot =
    190         FunctionVariableField::decode(Flags()) == CONTEXT;
    191     bool has_context = context_locals > 0 ||
    192         function_name_context_slot ||
    193         Type() == WITH_SCOPE ||
    194         (Type() == FUNCTION_SCOPE && CallsEval());
    195     if (has_context) {
    196       return Context::MIN_CONTEXT_SLOTS + context_locals +
    197           (function_name_context_slot ? 1 : 0);
    198     }
    199   }
    200   return 0;
    201 }
    202 
    203 
    204 bool ScopeInfo::HasFunctionName() {
    205   if (length() > 0) {
    206     return NONE != FunctionVariableField::decode(Flags());
    207   } else {
    208     return false;
    209   }
    210 }
    211 
    212 
    213 bool ScopeInfo::HasHeapAllocatedLocals() {
    214   if (length() > 0) {
    215     return ContextLocalCount() > 0;
    216   } else {
    217     return false;
    218   }
    219 }
    220 
    221 
    222 bool ScopeInfo::HasContext() {
    223   if (length() > 0) {
    224     return ContextLength() > 0;
    225   } else {
    226     return false;
    227   }
    228 }
    229 
    230 
    231 String* ScopeInfo::FunctionName() {
    232   ASSERT(HasFunctionName());
    233   return String::cast(get(FunctionNameEntryIndex()));
    234 }
    235 
    236 
    237 String* ScopeInfo::ParameterName(int var) {
    238   ASSERT(0 <= var && var < ParameterCount());
    239   int info_index = ParameterEntriesIndex() + var;
    240   return String::cast(get(info_index));
    241 }
    242 
    243 
    244 String* ScopeInfo::LocalName(int var) {
    245   ASSERT(0 <= var && var < LocalCount());
    246   ASSERT(StackLocalEntriesIndex() + StackLocalCount() ==
    247          ContextLocalNameEntriesIndex());
    248   int info_index = StackLocalEntriesIndex() + var;
    249   return String::cast(get(info_index));
    250 }
    251 
    252 
    253 String* ScopeInfo::StackLocalName(int var) {
    254   ASSERT(0 <= var && var < StackLocalCount());
    255   int info_index = StackLocalEntriesIndex() + var;
    256   return String::cast(get(info_index));
    257 }
    258 
    259 
    260 String* ScopeInfo::ContextLocalName(int var) {
    261   ASSERT(0 <= var && var < ContextLocalCount());
    262   int info_index = ContextLocalNameEntriesIndex() + var;
    263   return String::cast(get(info_index));
    264 }
    265 
    266 
    267 VariableMode ScopeInfo::ContextLocalMode(int var) {
    268   ASSERT(0 <= var && var < ContextLocalCount());
    269   int info_index = ContextLocalInfoEntriesIndex() + var;
    270   int value = Smi::cast(get(info_index))->value();
    271   return ContextLocalMode::decode(value);
    272 }
    273 
    274 
    275 InitializationFlag ScopeInfo::ContextLocalInitFlag(int var) {
    276   ASSERT(0 <= var && var < ContextLocalCount());
    277   int info_index = ContextLocalInfoEntriesIndex() + var;
    278   int value = Smi::cast(get(info_index))->value();
    279   return ContextLocalInitFlag::decode(value);
    280 }
    281 
    282 
    283 int ScopeInfo::StackSlotIndex(String* name) {
    284   ASSERT(name->IsSymbol());
    285   if (length() > 0) {
    286     int start = StackLocalEntriesIndex();
    287     int end = StackLocalEntriesIndex() + StackLocalCount();
    288     for (int i = start; i < end; ++i) {
    289       if (name == get(i)) {
    290         return i - start;
    291       }
    292     }
    293   }
    294   return -1;
    295 }
    296 
    297 
    298 int ScopeInfo::ContextSlotIndex(String* name,
    299                                 VariableMode* mode,
    300                                 InitializationFlag* init_flag) {
    301   ASSERT(name->IsSymbol());
    302   ASSERT(mode != NULL);
    303   ASSERT(init_flag != NULL);
    304   if (length() > 0) {
    305     ContextSlotCache* context_slot_cache = GetIsolate()->context_slot_cache();
    306     int result = context_slot_cache->Lookup(this, name, mode, init_flag);
    307     if (result != ContextSlotCache::kNotFound) {
    308       ASSERT(result < ContextLength());
    309       return result;
    310     }
    311 
    312     int start = ContextLocalNameEntriesIndex();
    313     int end = ContextLocalNameEntriesIndex() + ContextLocalCount();
    314     for (int i = start; i < end; ++i) {
    315       if (name == get(i)) {
    316         int var = i - start;
    317         *mode = ContextLocalMode(var);
    318         *init_flag = ContextLocalInitFlag(var);
    319         result = Context::MIN_CONTEXT_SLOTS + var;
    320         context_slot_cache->Update(this, name, *mode, *init_flag, result);
    321         ASSERT(result < ContextLength());
    322         return result;
    323       }
    324     }
    325     context_slot_cache->Update(this, name, INTERNAL, kNeedsInitialization, -1);
    326   }
    327   return -1;
    328 }
    329 
    330 
    331 int ScopeInfo::ParameterIndex(String* name) {
    332   ASSERT(name->IsSymbol());
    333   if (length() > 0) {
    334     // We must read parameters from the end since for
    335     // multiply declared parameters the value of the
    336     // last declaration of that parameter is used
    337     // inside a function (and thus we need to look
    338     // at the last index). Was bug# 1110337.
    339     int start = ParameterEntriesIndex();
    340     int end = ParameterEntriesIndex() + ParameterCount();
    341     for (int i = end - 1; i >= start; --i) {
    342       if (name == get(i)) {
    343         return i - start;
    344       }
    345     }
    346   }
    347   return -1;
    348 }
    349 
    350 
    351 int ScopeInfo::FunctionContextSlotIndex(String* name, VariableMode* mode) {
    352   ASSERT(name->IsSymbol());
    353   ASSERT(mode != NULL);
    354   if (length() > 0) {
    355     if (FunctionVariableField::decode(Flags()) == CONTEXT &&
    356         FunctionName() == name) {
    357       *mode = FunctionVariableMode::decode(Flags());
    358       return Smi::cast(get(FunctionNameEntryIndex() + 1))->value();
    359     }
    360   }
    361   return -1;
    362 }
    363 
    364 
    365 int ScopeInfo::ParameterEntriesIndex() {
    366   ASSERT(length() > 0);
    367   return kVariablePartIndex;
    368 }
    369 
    370 
    371 int ScopeInfo::StackLocalEntriesIndex() {
    372   return ParameterEntriesIndex() + ParameterCount();
    373 }
    374 
    375 
    376 int ScopeInfo::ContextLocalNameEntriesIndex() {
    377   return StackLocalEntriesIndex() + StackLocalCount();
    378 }
    379 
    380 
    381 int ScopeInfo::ContextLocalInfoEntriesIndex() {
    382   return ContextLocalNameEntriesIndex() + ContextLocalCount();
    383 }
    384 
    385 
    386 int ScopeInfo::FunctionNameEntryIndex() {
    387   return ContextLocalInfoEntriesIndex() + ContextLocalCount();
    388 }
    389 
    390 
    391 int ContextSlotCache::Hash(Object* data, String* name) {
    392   // Uses only lower 32 bits if pointers are larger.
    393   uintptr_t addr_hash =
    394       static_cast<uint32_t>(reinterpret_cast<uintptr_t>(data)) >> 2;
    395   return static_cast<int>((addr_hash ^ name->Hash()) % kLength);
    396 }
    397 
    398 
    399 int ContextSlotCache::Lookup(Object* data,
    400                              String* name,
    401                              VariableMode* mode,
    402                              InitializationFlag* init_flag) {
    403   int index = Hash(data, name);
    404   Key& key = keys_[index];
    405   if ((key.data == data) && key.name->Equals(name)) {
    406     Value result(values_[index]);
    407     if (mode != NULL) *mode = result.mode();
    408     if (init_flag != NULL) *init_flag = result.initialization_flag();
    409     return result.index() + kNotFound;
    410   }
    411   return kNotFound;
    412 }
    413 
    414 
    415 void ContextSlotCache::Update(Object* data,
    416                               String* name,
    417                               VariableMode mode,
    418                               InitializationFlag init_flag,
    419                               int slot_index) {
    420   String* symbol;
    421   ASSERT(slot_index > kNotFound);
    422   if (HEAP->LookupSymbolIfExists(name, &symbol)) {
    423     int index = Hash(data, symbol);
    424     Key& key = keys_[index];
    425     key.data = data;
    426     key.name = symbol;
    427     // Please note value only takes a uint as index.
    428     values_[index] = Value(mode, init_flag, slot_index - kNotFound).raw();
    429 #ifdef DEBUG
    430     ValidateEntry(data, name, mode, init_flag, slot_index);
    431 #endif
    432   }
    433 }
    434 
    435 
    436 void ContextSlotCache::Clear() {
    437   for (int index = 0; index < kLength; index++) keys_[index].data = NULL;
    438 }
    439 
    440 
    441 #ifdef DEBUG
    442 
    443 void ContextSlotCache::ValidateEntry(Object* data,
    444                                      String* name,
    445                                      VariableMode mode,
    446                                      InitializationFlag init_flag,
    447                                      int slot_index) {
    448   String* symbol;
    449   if (HEAP->LookupSymbolIfExists(name, &symbol)) {
    450     int index = Hash(data, name);
    451     Key& key = keys_[index];
    452     ASSERT(key.data == data);
    453     ASSERT(key.name->Equals(name));
    454     Value result(values_[index]);
    455     ASSERT(result.mode() == mode);
    456     ASSERT(result.initialization_flag() == init_flag);
    457     ASSERT(result.index() + kNotFound == slot_index);
    458   }
    459 }
    460 
    461 
    462 static void PrintList(const char* list_name,
    463                       int nof_internal_slots,
    464                       int start,
    465                       int end,
    466                       ScopeInfo* scope_info) {
    467   if (start < end) {
    468     PrintF("\n  // %s\n", list_name);
    469     if (nof_internal_slots > 0) {
    470       PrintF("  %2d - %2d [internal slots]\n", 0 , nof_internal_slots - 1);
    471     }
    472     for (int i = nof_internal_slots; start < end; ++i, ++start) {
    473       PrintF("  %2d ", i);
    474       String::cast(scope_info->get(start))->ShortPrint();
    475       PrintF("\n");
    476     }
    477   }
    478 }
    479 
    480 
    481 void ScopeInfo::Print() {
    482   PrintF("ScopeInfo ");
    483   if (HasFunctionName()) {
    484     FunctionName()->ShortPrint();
    485   } else {
    486     PrintF("/* no function name */");
    487   }
    488   PrintF("{");
    489 
    490   PrintList("parameters", 0,
    491             ParameterEntriesIndex(),
    492             ParameterEntriesIndex() + ParameterCount(),
    493             this);
    494   PrintList("stack slots", 0,
    495             StackLocalEntriesIndex(),
    496             StackLocalEntriesIndex() + StackLocalCount(),
    497             this);
    498   PrintList("context slots",
    499             Context::MIN_CONTEXT_SLOTS,
    500             ContextLocalNameEntriesIndex(),
    501             ContextLocalNameEntriesIndex() + ContextLocalCount(),
    502             this);
    503 
    504   PrintF("}\n");
    505 }
    506 #endif  // DEBUG
    507 
    508 } }  // namespace v8::internal
    509