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, Zone* zone) { 42 // Collect stack and context locals. 43 ZoneList<Variable*> stack_locals(scope->StackLocalCount(), zone); 44 ZoneList<Variable*> context_locals(scope->ContextLocalCount(), zone); 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 Factory* factory = Isolate::Current()->factory(); 78 Handle<ScopeInfo> scope_info = factory->NewScopeInfo(length); 79 80 // Encode the flags. 81 int flags = ScopeTypeField::encode(scope->scope_type()) | 82 CallsEvalField::encode(scope->calls_eval()) | 83 LanguageModeField::encode(scope->language_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(Isolate* isolate) { 154 return reinterpret_cast<ScopeInfo*>(isolate->heap()->empty_fixed_array()); 155 } 156 157 158 ScopeType ScopeInfo::scope_type() { 159 ASSERT(length() > 0); 160 return ScopeTypeField::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 int ScopeInfo::LocalCount() { 175 return StackLocalCount() + ContextLocalCount(); 176 } 177 178 179 int ScopeInfo::StackSlotCount() { 180 if (length() > 0) { 181 bool function_name_stack_slot = 182 FunctionVariableField::decode(Flags()) == STACK; 183 return StackLocalCount() + (function_name_stack_slot ? 1 : 0); 184 } 185 return 0; 186 } 187 188 189 int ScopeInfo::ContextLength() { 190 if (length() > 0) { 191 int context_locals = ContextLocalCount(); 192 bool function_name_context_slot = 193 FunctionVariableField::decode(Flags()) == CONTEXT; 194 bool has_context = context_locals > 0 || 195 function_name_context_slot || 196 scope_type() == WITH_SCOPE || 197 (scope_type() == FUNCTION_SCOPE && CallsEval()) || 198 scope_type() == MODULE_SCOPE; 199 if (has_context) { 200 return Context::MIN_CONTEXT_SLOTS + context_locals + 201 (function_name_context_slot ? 1 : 0); 202 } 203 } 204 return 0; 205 } 206 207 208 bool ScopeInfo::HasFunctionName() { 209 if (length() > 0) { 210 return NONE != FunctionVariableField::decode(Flags()); 211 } else { 212 return false; 213 } 214 } 215 216 217 bool ScopeInfo::HasHeapAllocatedLocals() { 218 if (length() > 0) { 219 return ContextLocalCount() > 0; 220 } else { 221 return false; 222 } 223 } 224 225 226 bool ScopeInfo::HasContext() { 227 return ContextLength() > 0; 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->IsInternalizedString()); 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->IsInternalizedString()); 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 // Cache as not found. Mode and init flag don't matter. 326 context_slot_cache->Update(this, name, INTERNAL, kNeedsInitialization, -1); 327 } 328 return -1; 329 } 330 331 332 int ScopeInfo::ParameterIndex(String* name) { 333 ASSERT(name->IsInternalizedString()); 334 if (length() > 0) { 335 // We must read parameters from the end since for 336 // multiply declared parameters the value of the 337 // last declaration of that parameter is used 338 // inside a function (and thus we need to look 339 // at the last index). Was bug# 1110337. 340 int start = ParameterEntriesIndex(); 341 int end = ParameterEntriesIndex() + ParameterCount(); 342 for (int i = end - 1; i >= start; --i) { 343 if (name == get(i)) { 344 return i - start; 345 } 346 } 347 } 348 return -1; 349 } 350 351 352 int ScopeInfo::FunctionContextSlotIndex(String* name, VariableMode* mode) { 353 ASSERT(name->IsInternalizedString()); 354 ASSERT(mode != NULL); 355 if (length() > 0) { 356 if (FunctionVariableField::decode(Flags()) == CONTEXT && 357 FunctionName() == name) { 358 *mode = FunctionVariableMode::decode(Flags()); 359 return Smi::cast(get(FunctionNameEntryIndex() + 1))->value(); 360 } 361 } 362 return -1; 363 } 364 365 366 bool ScopeInfo::CopyContextLocalsToScopeObject( 367 Isolate* isolate, 368 Handle<Context> context, 369 Handle<JSObject> scope_object) { 370 int local_count = ContextLocalCount(); 371 if (local_count == 0) return true; 372 // Fill all context locals to the context extension. 373 int start = ContextLocalNameEntriesIndex(); 374 int end = start + local_count; 375 for (int i = start; i < end; ++i) { 376 int context_index = Context::MIN_CONTEXT_SLOTS + i - start; 377 RETURN_IF_EMPTY_HANDLE_VALUE( 378 isolate, 379 SetProperty(isolate, 380 scope_object, 381 Handle<String>(String::cast(get(i))), 382 Handle<Object>(context->get(context_index), isolate), 383 ::NONE, 384 kNonStrictMode), 385 false); 386 } 387 return true; 388 } 389 390 391 int ScopeInfo::ParameterEntriesIndex() { 392 ASSERT(length() > 0); 393 return kVariablePartIndex; 394 } 395 396 397 int ScopeInfo::StackLocalEntriesIndex() { 398 return ParameterEntriesIndex() + ParameterCount(); 399 } 400 401 402 int ScopeInfo::ContextLocalNameEntriesIndex() { 403 return StackLocalEntriesIndex() + StackLocalCount(); 404 } 405 406 407 int ScopeInfo::ContextLocalInfoEntriesIndex() { 408 return ContextLocalNameEntriesIndex() + ContextLocalCount(); 409 } 410 411 412 int ScopeInfo::FunctionNameEntryIndex() { 413 return ContextLocalInfoEntriesIndex() + ContextLocalCount(); 414 } 415 416 417 int ContextSlotCache::Hash(Object* data, String* name) { 418 // Uses only lower 32 bits if pointers are larger. 419 uintptr_t addr_hash = 420 static_cast<uint32_t>(reinterpret_cast<uintptr_t>(data)) >> 2; 421 return static_cast<int>((addr_hash ^ name->Hash()) % kLength); 422 } 423 424 425 int ContextSlotCache::Lookup(Object* data, 426 String* name, 427 VariableMode* mode, 428 InitializationFlag* init_flag) { 429 int index = Hash(data, name); 430 Key& key = keys_[index]; 431 if ((key.data == data) && key.name->Equals(name)) { 432 Value result(values_[index]); 433 if (mode != NULL) *mode = result.mode(); 434 if (init_flag != NULL) *init_flag = result.initialization_flag(); 435 return result.index() + kNotFound; 436 } 437 return kNotFound; 438 } 439 440 441 void ContextSlotCache::Update(Object* data, 442 String* name, 443 VariableMode mode, 444 InitializationFlag init_flag, 445 int slot_index) { 446 String* internalized_name; 447 ASSERT(slot_index > kNotFound); 448 if (HEAP->InternalizeStringIfExists(name, &internalized_name)) { 449 int index = Hash(data, internalized_name); 450 Key& key = keys_[index]; 451 key.data = data; 452 key.name = internalized_name; 453 // Please note value only takes a uint as index. 454 values_[index] = Value(mode, init_flag, slot_index - kNotFound).raw(); 455 #ifdef DEBUG 456 ValidateEntry(data, name, mode, init_flag, slot_index); 457 #endif 458 } 459 } 460 461 462 void ContextSlotCache::Clear() { 463 for (int index = 0; index < kLength; index++) keys_[index].data = NULL; 464 } 465 466 467 #ifdef DEBUG 468 469 void ContextSlotCache::ValidateEntry(Object* data, 470 String* name, 471 VariableMode mode, 472 InitializationFlag init_flag, 473 int slot_index) { 474 String* internalized_name; 475 if (HEAP->InternalizeStringIfExists(name, &internalized_name)) { 476 int index = Hash(data, name); 477 Key& key = keys_[index]; 478 ASSERT(key.data == data); 479 ASSERT(key.name->Equals(name)); 480 Value result(values_[index]); 481 ASSERT(result.mode() == mode); 482 ASSERT(result.initialization_flag() == init_flag); 483 ASSERT(result.index() + kNotFound == slot_index); 484 } 485 } 486 487 488 static void PrintList(const char* list_name, 489 int nof_internal_slots, 490 int start, 491 int end, 492 ScopeInfo* scope_info) { 493 if (start < end) { 494 PrintF("\n // %s\n", list_name); 495 if (nof_internal_slots > 0) { 496 PrintF(" %2d - %2d [internal slots]\n", 0 , nof_internal_slots - 1); 497 } 498 for (int i = nof_internal_slots; start < end; ++i, ++start) { 499 PrintF(" %2d ", i); 500 String::cast(scope_info->get(start))->ShortPrint(); 501 PrintF("\n"); 502 } 503 } 504 } 505 506 507 void ScopeInfo::Print() { 508 PrintF("ScopeInfo "); 509 if (HasFunctionName()) { 510 FunctionName()->ShortPrint(); 511 } else { 512 PrintF("/* no function name */"); 513 } 514 PrintF("{"); 515 516 PrintList("parameters", 0, 517 ParameterEntriesIndex(), 518 ParameterEntriesIndex() + ParameterCount(), 519 this); 520 PrintList("stack slots", 0, 521 StackLocalEntriesIndex(), 522 StackLocalEntriesIndex() + StackLocalCount(), 523 this); 524 PrintList("context slots", 525 Context::MIN_CONTEXT_SLOTS, 526 ContextLocalNameEntriesIndex(), 527 ContextLocalNameEntriesIndex() + ContextLocalCount(), 528 this); 529 530 PrintF("}\n"); 531 } 532 #endif // DEBUG 533 534 535 //--------------------------------------------------------------------------- 536 // ModuleInfo. 537 538 Handle<ModuleInfo> ModuleInfo::Create( 539 Isolate* isolate, Interface* interface, Scope* scope) { 540 Handle<ModuleInfo> info = Allocate(isolate, interface->Length()); 541 info->set_host_index(interface->Index()); 542 int i = 0; 543 for (Interface::Iterator it = interface->iterator(); 544 !it.done(); it.Advance(), ++i) { 545 Variable* var = scope->LocalLookup(it.name()); 546 info->set_name(i, *it.name()); 547 info->set_mode(i, var->mode()); 548 ASSERT((var->mode() == MODULE) == (it.interface()->IsModule())); 549 if (var->mode() == MODULE) { 550 ASSERT(it.interface()->IsFrozen()); 551 ASSERT(it.interface()->Index() >= 0); 552 info->set_index(i, it.interface()->Index()); 553 } else { 554 ASSERT(var->index() >= 0); 555 info->set_index(i, var->index()); 556 } 557 } 558 ASSERT(i == info->length()); 559 return info; 560 } 561 562 } } // namespace v8::internal 563