src/3rdparty/v8/src/scopeinfo.cc

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