1/* 2 * Copyright (C) 2008, 2009, 2013 Apple Inc. All rights reserved. 3 * 4 * Redistribution and use in source and binary forms, with or without 5 * modification, are permitted provided that the following conditions 6 * are met: 7 * 1. Redistributions of source code must retain the above copyright 8 * notice, this list of conditions and the following disclaimer. 9 * 2. Redistributions in binary form must reproduce the above copyright 10 * notice, this list of conditions and the following disclaimer in the 11 * documentation and/or other materials provided with the distribution. 12 * 13 * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY 14 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 15 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 16 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE COMPUTER, INC. OR 17 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 18 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 19 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 20 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY 21 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 22 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 23 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 24 */ 25 26#include "config.h" 27#include "Structure.h" 28 29#include "CodeBlock.h" 30#include "JSObject.h" 31#include "JSPropertyNameIterator.h" 32#include "Lookup.h" 33#include "PropertyNameArray.h" 34#include "StructureChain.h" 35#include "StructureRareDataInlines.h" 36#include <wtf/RefCountedLeakCounter.h> 37#include <wtf/RefPtr.h> 38#include <wtf/Threading.h> 39 40#define DUMP_STRUCTURE_ID_STATISTICS 0 41 42#ifndef NDEBUG 43#define DO_PROPERTYMAP_CONSTENCY_CHECK 0 44#else 45#define DO_PROPERTYMAP_CONSTENCY_CHECK 0 46#endif 47 48using namespace std; 49using namespace WTF; 50 51#if DUMP_PROPERTYMAP_STATS 52 53int numProbes; 54int numCollisions; 55int numRehashes; 56int numRemoves; 57 58#endif 59 60namespace JSC { 61 62#if DUMP_STRUCTURE_ID_STATISTICS 63static HashSet<Structure*>& liveStructureSet = *(new HashSet<Structure*>); 64#endif 65 66bool StructureTransitionTable::contains(StringImpl* rep, unsigned attributes) const 67{ 68 if (isUsingSingleSlot()) { 69 Structure* transition = singleTransition(); 70 return transition && transition->m_nameInPrevious == rep && transition->m_attributesInPrevious == attributes; 71 } 72 return map()->get(make_pair(rep, attributes)); 73} 74 75inline Structure* StructureTransitionTable::get(StringImpl* rep, unsigned attributes) const 76{ 77 if (isUsingSingleSlot()) { 78 Structure* transition = singleTransition(); 79 return (transition && transition->m_nameInPrevious == rep && transition->m_attributesInPrevious == attributes) ? transition : 0; 80 } 81 return map()->get(make_pair(rep, attributes)); 82} 83 84inline void StructureTransitionTable::add(VM& vm, Structure* structure) 85{ 86 if (isUsingSingleSlot()) { 87 Structure* existingTransition = singleTransition(); 88 89 // This handles the first transition being added. 90 if (!existingTransition) { 91 setSingleTransition(vm, structure); 92 return; 93 } 94 95 // This handles the second transition being added 96 // (or the first transition being despecified!) 97 setMap(new TransitionMap()); 98 add(vm, existingTransition); 99 } 100 101 // Add the structure to the map. 102 103 // Newer versions of the STL have an std::make_pair function that takes rvalue references. 104 // When either of the parameters are bitfields, the C++ compiler will try to bind them as lvalues, which is invalid. To work around this, use unary "+" to make the parameter an rvalue. 105 // See https://bugs.webkit.org/show_bug.cgi?id=59261 for more details 106 map()->set(make_pair(structure->m_nameInPrevious, +structure->m_attributesInPrevious), structure); 107} 108 109void Structure::dumpStatistics() 110{ 111#if DUMP_STRUCTURE_ID_STATISTICS 112 unsigned numberLeaf = 0; 113 unsigned numberUsingSingleSlot = 0; 114 unsigned numberSingletons = 0; 115 unsigned numberWithPropertyMaps = 0; 116 unsigned totalPropertyMapsSize = 0; 117 118 HashSet<Structure*>::const_iterator end = liveStructureSet.end(); 119 for (HashSet<Structure*>::const_iterator it = liveStructureSet.begin(); it != end; ++it) { 120 Structure* structure = *it; 121 122 switch (structure->m_transitionTable.size()) { 123 case 0: 124 ++numberLeaf; 125 if (!structure->previousID()) 126 ++numberSingletons; 127 break; 128 129 case 1: 130 ++numberUsingSingleSlot; 131 break; 132 } 133 134 if (structure->propertyTable()) { 135 ++numberWithPropertyMaps; 136 totalPropertyMapsSize += structure->propertyTable()->sizeInMemory(); 137 } 138 } 139 140 dataLogF("Number of live Structures: %d\n", liveStructureSet.size()); 141 dataLogF("Number of Structures using the single item optimization for transition map: %d\n", numberUsingSingleSlot); 142 dataLogF("Number of Structures that are leaf nodes: %d\n", numberLeaf); 143 dataLogF("Number of Structures that singletons: %d\n", numberSingletons); 144 dataLogF("Number of Structures with PropertyMaps: %d\n", numberWithPropertyMaps); 145 146 dataLogF("Size of a single Structures: %d\n", static_cast<unsigned>(sizeof(Structure))); 147 dataLogF("Size of sum of all property maps: %d\n", totalPropertyMapsSize); 148 dataLogF("Size of average of all property maps: %f\n", static_cast<double>(totalPropertyMapsSize) / static_cast<double>(liveStructureSet.size())); 149#else 150 dataLogF("Dumping Structure statistics is not enabled.\n"); 151#endif 152} 153 154Structure::Structure(VM& vm, JSGlobalObject* globalObject, JSValue prototype, const TypeInfo& typeInfo, const ClassInfo* classInfo, IndexingType indexingType, unsigned inlineCapacity) 155 : JSCell(vm, vm.structureStructure.get()) 156 , m_globalObject(vm, this, globalObject, WriteBarrier<JSGlobalObject>::MayBeNull) 157 , m_prototype(vm, this, prototype) 158 , m_classInfo(classInfo) 159 , m_transitionWatchpointSet(InitializedWatching) 160 , m_offset(invalidOffset) 161 , m_typeInfo(typeInfo) 162 , m_indexingType(indexingType) 163 , m_inlineCapacity(inlineCapacity) 164 , m_dictionaryKind(NoneDictionaryKind) 165 , m_isPinnedPropertyTable(false) 166 , m_hasGetterSetterProperties(false) 167 , m_hasReadOnlyOrGetterSetterPropertiesExcludingProto(false) 168 , m_hasNonEnumerableProperties(false) 169 , m_attributesInPrevious(0) 170 , m_specificFunctionThrashCount(0) 171 , m_preventExtensions(false) 172 , m_didTransition(false) 173 , m_staticFunctionReified(false) 174{ 175 ASSERT(inlineCapacity <= JSFinalObject::maxInlineCapacity()); 176 ASSERT(static_cast<PropertyOffset>(inlineCapacity) < firstOutOfLineOffset); 177 ASSERT(!typeInfo.structureHasRareData()); 178} 179 180const ClassInfo Structure::s_info = { "Structure", 0, 0, 0, CREATE_METHOD_TABLE(Structure) }; 181 182Structure::Structure(VM& vm) 183 : JSCell(CreatingEarlyCell) 184 , m_prototype(vm, this, jsNull()) 185 , m_classInfo(&s_info) 186 , m_transitionWatchpointSet(InitializedWatching) 187 , m_offset(invalidOffset) 188 , m_typeInfo(CompoundType, OverridesVisitChildren) 189 , m_indexingType(0) 190 , m_inlineCapacity(0) 191 , m_dictionaryKind(NoneDictionaryKind) 192 , m_isPinnedPropertyTable(false) 193 , m_hasGetterSetterProperties(false) 194 , m_hasReadOnlyOrGetterSetterPropertiesExcludingProto(false) 195 , m_hasNonEnumerableProperties(false) 196 , m_attributesInPrevious(0) 197 , m_specificFunctionThrashCount(0) 198 , m_preventExtensions(false) 199 , m_didTransition(false) 200 , m_staticFunctionReified(false) 201{ 202} 203 204Structure::Structure(VM& vm, const Structure* previous) 205 : JSCell(vm, vm.structureStructure.get()) 206 , m_prototype(vm, this, previous->storedPrototype()) 207 , m_classInfo(previous->m_classInfo) 208 , m_transitionWatchpointSet(InitializedWatching) 209 , m_offset(invalidOffset) 210 , m_typeInfo(previous->typeInfo().type(), previous->typeInfo().flags() & ~StructureHasRareData) 211 , m_indexingType(previous->indexingTypeIncludingHistory()) 212 , m_inlineCapacity(previous->m_inlineCapacity) 213 , m_dictionaryKind(previous->m_dictionaryKind) 214 , m_isPinnedPropertyTable(false) 215 , m_hasGetterSetterProperties(previous->m_hasGetterSetterProperties) 216 , m_hasReadOnlyOrGetterSetterPropertiesExcludingProto(previous->m_hasReadOnlyOrGetterSetterPropertiesExcludingProto) 217 , m_hasNonEnumerableProperties(previous->m_hasNonEnumerableProperties) 218 , m_attributesInPrevious(0) 219 , m_specificFunctionThrashCount(previous->m_specificFunctionThrashCount) 220 , m_preventExtensions(previous->m_preventExtensions) 221 , m_didTransition(true) 222 , m_staticFunctionReified(previous->m_staticFunctionReified) 223{ 224 if (previous->typeInfo().structureHasRareData() && previous->rareData()->needsCloning()) 225 cloneRareDataFrom(vm, previous); 226 else if (previous->previousID()) 227 m_previousOrRareData.set(vm, this, previous->previousID()); 228 229 previous->notifyTransitionFromThisStructure(); 230 if (previous->m_globalObject) 231 m_globalObject.set(vm, this, previous->m_globalObject.get()); 232} 233 234void Structure::destroy(JSCell* cell) 235{ 236 static_cast<Structure*>(cell)->Structure::~Structure(); 237} 238 239void Structure::materializePropertyMap(VM& vm) 240{ 241 ASSERT(structure()->classInfo() == &s_info); 242 ASSERT(!propertyTable()); 243 244 Vector<Structure*, 8> structures; 245 structures.append(this); 246 247 Structure* structure = this; 248 249 // Search for the last Structure with a property table. 250 while ((structure = structure->previousID())) { 251 if (structure->m_isPinnedPropertyTable) { 252 ASSERT(structure->propertyTable()); 253 ASSERT(!structure->previousID()); 254 255 propertyTable().set(vm, this, structure->propertyTable()->copy(vm, 0, numberOfSlotsForLastOffset(m_offset, m_inlineCapacity))); 256 break; 257 } 258 259 structures.append(structure); 260 } 261 262 if (!propertyTable()) 263 createPropertyMap(vm, numberOfSlotsForLastOffset(m_offset, m_inlineCapacity)); 264 265 for (ptrdiff_t i = structures.size() - 1; i >= 0; --i) { 266 structure = structures[i]; 267 if (!structure->m_nameInPrevious) 268 continue; 269 PropertyMapEntry entry(vm, this, structure->m_nameInPrevious.get(), structure->m_offset, structure->m_attributesInPrevious, structure->m_specificValueInPrevious.get()); 270 propertyTable()->add(entry, m_offset, PropertyTable::PropertyOffsetMustNotChange); 271 } 272 273 checkOffsetConsistency(); 274} 275 276inline size_t nextOutOfLineStorageCapacity(size_t currentCapacity) 277{ 278 if (!currentCapacity) 279 return initialOutOfLineCapacity; 280 return currentCapacity * outOfLineGrowthFactor; 281} 282 283size_t Structure::suggestedNewOutOfLineStorageCapacity() 284{ 285 return nextOutOfLineStorageCapacity(outOfLineCapacity()); 286} 287 288void Structure::despecifyDictionaryFunction(VM& vm, PropertyName propertyName) 289{ 290 StringImpl* rep = propertyName.uid(); 291 292 materializePropertyMapIfNecessary(vm); 293 294 ASSERT(isDictionary()); 295 ASSERT(propertyTable()); 296 297 PropertyMapEntry* entry = propertyTable()->find(rep).first; 298 ASSERT(entry); 299 entry->specificValue.clear(); 300} 301 302Structure* Structure::addPropertyTransitionToExistingStructure(Structure* structure, PropertyName propertyName, unsigned attributes, JSCell* specificValue, PropertyOffset& offset) 303{ 304 ASSERT(!structure->isDictionary()); 305 ASSERT(structure->isObject()); 306 307 if (Structure* existingTransition = structure->m_transitionTable.get(propertyName.uid(), attributes)) { 308 JSCell* specificValueInPrevious = existingTransition->m_specificValueInPrevious.get(); 309 if (specificValueInPrevious && specificValueInPrevious != specificValue) 310 return 0; 311 validateOffset(existingTransition->m_offset, existingTransition->inlineCapacity()); 312 offset = existingTransition->m_offset; 313 return existingTransition; 314 } 315 316 return 0; 317} 318 319bool Structure::anyObjectInChainMayInterceptIndexedAccesses() const 320{ 321 for (const Structure* current = this; ;) { 322 if (current->mayInterceptIndexedAccesses()) 323 return true; 324 325 JSValue prototype = current->storedPrototype(); 326 if (prototype.isNull()) 327 return false; 328 329 current = asObject(prototype)->structure(); 330 } 331} 332 333bool Structure::needsSlowPutIndexing() const 334{ 335 return anyObjectInChainMayInterceptIndexedAccesses() 336 || globalObject()->isHavingABadTime(); 337} 338 339NonPropertyTransition Structure::suggestedArrayStorageTransition() const 340{ 341 if (needsSlowPutIndexing()) 342 return AllocateSlowPutArrayStorage; 343 344 return AllocateArrayStorage; 345} 346 347Structure* Structure::addPropertyTransition(VM& vm, Structure* structure, PropertyName propertyName, unsigned attributes, JSCell* specificValue, PropertyOffset& offset) 348{ 349 // If we have a specific function, we may have got to this point if there is 350 // already a transition with the correct property name and attributes, but 351 // specialized to a different function. In this case we just want to give up 352 // and despecialize the transition. 353 // In this case we clear the value of specificFunction which will result 354 // in us adding a non-specific transition, and any subsequent lookup in 355 // Structure::addPropertyTransitionToExistingStructure will just use that. 356 if (specificValue && structure->m_transitionTable.contains(propertyName.uid(), attributes)) 357 specificValue = 0; 358 359 ASSERT(!structure->isDictionary()); 360 ASSERT(structure->isObject()); 361 ASSERT(!Structure::addPropertyTransitionToExistingStructure(structure, propertyName, attributes, specificValue, offset)); 362 363 if (structure->m_specificFunctionThrashCount == maxSpecificFunctionThrashCount) 364 specificValue = 0; 365 366 if (structure->transitionCount() > s_maxTransitionLength) { 367 Structure* transition = toCacheableDictionaryTransition(vm, structure); 368 ASSERT(structure != transition); 369 offset = transition->putSpecificValue(vm, propertyName, attributes, specificValue); 370 return transition; 371 } 372 373 Structure* transition = create(vm, structure); 374 375 transition->m_cachedPrototypeChain.setMayBeNull(vm, transition, structure->m_cachedPrototypeChain.get()); 376 transition->setPreviousID(vm, transition, structure); 377 transition->m_nameInPrevious = propertyName.uid(); 378 transition->m_attributesInPrevious = attributes; 379 transition->m_specificValueInPrevious.setMayBeNull(vm, transition, specificValue); 380 transition->propertyTable().set(vm, transition, structure->takePropertyTableOrCloneIfPinned(vm, transition)); 381 transition->m_offset = structure->m_offset; 382 383 offset = transition->putSpecificValue(vm, propertyName, attributes, specificValue); 384 385 checkOffset(transition->m_offset, transition->inlineCapacity()); 386 structure->m_transitionTable.add(vm, transition); 387 transition->checkOffsetConsistency(); 388 structure->checkOffsetConsistency(); 389 return transition; 390} 391 392Structure* Structure::removePropertyTransition(VM& vm, Structure* structure, PropertyName propertyName, PropertyOffset& offset) 393{ 394 ASSERT(!structure->isUncacheableDictionary()); 395 396 Structure* transition = toUncacheableDictionaryTransition(vm, structure); 397 398 offset = transition->remove(propertyName); 399 400 transition->checkOffsetConsistency(); 401 return transition; 402} 403 404Structure* Structure::changePrototypeTransition(VM& vm, Structure* structure, JSValue prototype) 405{ 406 Structure* transition = create(vm, structure); 407 408 transition->m_prototype.set(vm, transition, prototype); 409 410 structure->materializePropertyMapIfNecessary(vm); 411 transition->propertyTable().set(vm, transition, structure->copyPropertyTableForPinning(vm, transition)); 412 transition->m_offset = structure->m_offset; 413 transition->pin(); 414 415 transition->checkOffsetConsistency(); 416 return transition; 417} 418 419Structure* Structure::despecifyFunctionTransition(VM& vm, Structure* structure, PropertyName replaceFunction) 420{ 421 ASSERT(structure->m_specificFunctionThrashCount < maxSpecificFunctionThrashCount); 422 Structure* transition = create(vm, structure); 423 424 ++transition->m_specificFunctionThrashCount; 425 426 structure->materializePropertyMapIfNecessary(vm); 427 transition->propertyTable().set(vm, transition, structure->copyPropertyTableForPinning(vm, transition)); 428 transition->m_offset = structure->m_offset; 429 transition->pin(); 430 431 if (transition->m_specificFunctionThrashCount == maxSpecificFunctionThrashCount) 432 transition->despecifyAllFunctions(vm); 433 else { 434 bool removed = transition->despecifyFunction(vm, replaceFunction); 435 ASSERT_UNUSED(removed, removed); 436 } 437 438 transition->checkOffsetConsistency(); 439 return transition; 440} 441 442Structure* Structure::attributeChangeTransition(VM& vm, Structure* structure, PropertyName propertyName, unsigned attributes) 443{ 444 if (!structure->isUncacheableDictionary()) { 445 Structure* transition = create(vm, structure); 446 447 structure->materializePropertyMapIfNecessary(vm); 448 transition->propertyTable().set(vm, transition, structure->copyPropertyTableForPinning(vm, transition)); 449 transition->m_offset = structure->m_offset; 450 transition->pin(); 451 452 structure = transition; 453 } 454 455 ASSERT(structure->propertyTable()); 456 PropertyMapEntry* entry = structure->propertyTable()->find(propertyName.uid()).first; 457 ASSERT(entry); 458 entry->attributes = attributes; 459 460 structure->checkOffsetConsistency(); 461 return structure; 462} 463 464Structure* Structure::toDictionaryTransition(VM& vm, Structure* structure, DictionaryKind kind) 465{ 466 ASSERT(!structure->isUncacheableDictionary()); 467 468 Structure* transition = create(vm, structure); 469 470 structure->materializePropertyMapIfNecessary(vm); 471 transition->propertyTable().set(vm, transition, structure->copyPropertyTableForPinning(vm, transition)); 472 transition->m_offset = structure->m_offset; 473 transition->m_dictionaryKind = kind; 474 transition->pin(); 475 476 transition->checkOffsetConsistency(); 477 return transition; 478} 479 480Structure* Structure::toCacheableDictionaryTransition(VM& vm, Structure* structure) 481{ 482 return toDictionaryTransition(vm, structure, CachedDictionaryKind); 483} 484 485Structure* Structure::toUncacheableDictionaryTransition(VM& vm, Structure* structure) 486{ 487 return toDictionaryTransition(vm, structure, UncachedDictionaryKind); 488} 489 490// In future we may want to cache this transition. 491Structure* Structure::sealTransition(VM& vm, Structure* structure) 492{ 493 Structure* transition = preventExtensionsTransition(vm, structure); 494 495 if (transition->propertyTable()) { 496 PropertyTable::iterator end = transition->propertyTable()->end(); 497 for (PropertyTable::iterator iter = transition->propertyTable()->begin(); iter != end; ++iter) 498 iter->attributes |= DontDelete; 499 } 500 501 transition->checkOffsetConsistency(); 502 return transition; 503} 504 505// In future we may want to cache this transition. 506Structure* Structure::freezeTransition(VM& vm, Structure* structure) 507{ 508 Structure* transition = preventExtensionsTransition(vm, structure); 509 510 if (transition->propertyTable()) { 511 PropertyTable::iterator iter = transition->propertyTable()->begin(); 512 PropertyTable::iterator end = transition->propertyTable()->end(); 513 if (iter != end) 514 transition->m_hasReadOnlyOrGetterSetterPropertiesExcludingProto = true; 515 for (; iter != end; ++iter) 516 iter->attributes |= iter->attributes & Accessor ? DontDelete : (DontDelete | ReadOnly); 517 } 518 519 transition->checkOffsetConsistency(); 520 return transition; 521} 522 523// In future we may want to cache this transition. 524Structure* Structure::preventExtensionsTransition(VM& vm, Structure* structure) 525{ 526 Structure* transition = create(vm, structure); 527 528 // Don't set m_offset, as one can not transition to this. 529 530 structure->materializePropertyMapIfNecessary(vm); 531 transition->propertyTable().set(vm, transition, structure->copyPropertyTableForPinning(vm, transition)); 532 transition->m_offset = structure->m_offset; 533 transition->m_preventExtensions = true; 534 transition->pin(); 535 536 transition->checkOffsetConsistency(); 537 return transition; 538} 539 540PropertyTable* Structure::takePropertyTableOrCloneIfPinned(VM& vm, Structure* owner) 541{ 542 materializePropertyMapIfNecessaryForPinning(vm); 543 if (m_isPinnedPropertyTable) 544 return propertyTable()->copy(vm, owner, propertyTable()->size() + 1); 545 PropertyTable* takenPropertyTable = propertyTable().get(); 546 propertyTable().clear(); 547 return takenPropertyTable; 548} 549 550Structure* Structure::nonPropertyTransition(VM& vm, Structure* structure, NonPropertyTransition transitionKind) 551{ 552 unsigned attributes = toAttributes(transitionKind); 553 IndexingType indexingType = newIndexingType(structure->indexingTypeIncludingHistory(), transitionKind); 554 555 if (JSGlobalObject* globalObject = structure->m_globalObject.get()) { 556 if (globalObject->isOriginalArrayStructure(structure)) { 557 Structure* result = globalObject->originalArrayStructureForIndexingType(indexingType); 558 if (result->indexingTypeIncludingHistory() == indexingType) { 559 structure->notifyTransitionFromThisStructure(); 560 return result; 561 } 562 } 563 } 564 565 if (Structure* existingTransition = structure->m_transitionTable.get(0, attributes)) { 566 ASSERT(existingTransition->m_attributesInPrevious == attributes); 567 ASSERT(existingTransition->indexingTypeIncludingHistory() == indexingType); 568 return existingTransition; 569 } 570 571 Structure* transition = create(vm, structure); 572 transition->setPreviousID(vm, transition, structure); 573 transition->m_attributesInPrevious = attributes; 574 transition->m_indexingType = indexingType; 575 transition->propertyTable().set(vm, transition, structure->takePropertyTableOrCloneIfPinned(vm, transition)); 576 transition->m_offset = structure->m_offset; 577 checkOffset(transition->m_offset, transition->inlineCapacity()); 578 579 structure->m_transitionTable.add(vm, transition); 580 transition->checkOffsetConsistency(); 581 return transition; 582} 583 584// In future we may want to cache this property. 585bool Structure::isSealed(VM& vm) 586{ 587 if (isExtensible()) 588 return false; 589 590 materializePropertyMapIfNecessary(vm); 591 if (!propertyTable()) 592 return true; 593 594 PropertyTable::iterator end = propertyTable()->end(); 595 for (PropertyTable::iterator iter = propertyTable()->begin(); iter != end; ++iter) { 596 if ((iter->attributes & DontDelete) != DontDelete) 597 return false; 598 } 599 return true; 600} 601 602// In future we may want to cache this property. 603bool Structure::isFrozen(VM& vm) 604{ 605 if (isExtensible()) 606 return false; 607 608 materializePropertyMapIfNecessary(vm); 609 if (!propertyTable()) 610 return true; 611 612 PropertyTable::iterator end = propertyTable()->end(); 613 for (PropertyTable::iterator iter = propertyTable()->begin(); iter != end; ++iter) { 614 if (!(iter->attributes & DontDelete)) 615 return false; 616 if (!(iter->attributes & (ReadOnly | Accessor))) 617 return false; 618 } 619 return true; 620} 621 622Structure* Structure::flattenDictionaryStructure(VM& vm, JSObject* object) 623{ 624 checkOffsetConsistency(); 625 ASSERT(isDictionary()); 626 if (isUncacheableDictionary()) { 627 ASSERT(propertyTable()); 628 629 size_t propertyCount = propertyTable()->size(); 630 631 // Holds our values compacted by insertion order. 632 Vector<JSValue> values(propertyCount); 633 634 // Copies out our values from their hashed locations, compacting property table offsets as we go. 635 unsigned i = 0; 636 PropertyTable::iterator end = propertyTable()->end(); 637 m_offset = invalidOffset; 638 for (PropertyTable::iterator iter = propertyTable()->begin(); iter != end; ++iter, ++i) { 639 values[i] = object->getDirect(iter->offset); 640 m_offset = iter->offset = offsetForPropertyNumber(i, m_inlineCapacity); 641 } 642 643 // Copies in our values to their compacted locations. 644 for (unsigned i = 0; i < propertyCount; i++) 645 object->putDirect(vm, offsetForPropertyNumber(i, m_inlineCapacity), values[i]); 646 647 propertyTable()->clearDeletedOffsets(); 648 checkOffsetConsistency(); 649 } 650 651 m_dictionaryKind = NoneDictionaryKind; 652 653 // If the object had a Butterfly but after flattening/compacting we no longer have need of it, 654 // we need to zero it out because the collector depends on the Structure to know the size for copying. 655 if (object->butterfly() && !this->outOfLineCapacity() && !hasIndexingHeader(this->indexingType())) 656 object->setButterfly(vm, 0, this); 657 658 return this; 659} 660 661PropertyOffset Structure::addPropertyWithoutTransition(VM& vm, PropertyName propertyName, unsigned attributes, JSCell* specificValue) 662{ 663 ASSERT(!enumerationCache()); 664 665 if (m_specificFunctionThrashCount == maxSpecificFunctionThrashCount) 666 specificValue = 0; 667 668 materializePropertyMapIfNecessaryForPinning(vm); 669 670 pin(); 671 672 return putSpecificValue(vm, propertyName, attributes, specificValue); 673} 674 675PropertyOffset Structure::removePropertyWithoutTransition(VM& vm, PropertyName propertyName) 676{ 677 ASSERT(isUncacheableDictionary()); 678 ASSERT(!enumerationCache()); 679 680 materializePropertyMapIfNecessaryForPinning(vm); 681 682 pin(); 683 return remove(propertyName); 684} 685 686void Structure::pin() 687{ 688 ASSERT(propertyTable()); 689 m_isPinnedPropertyTable = true; 690 clearPreviousID(); 691 m_nameInPrevious.clear(); 692} 693 694void Structure::allocateRareData(VM& vm) 695{ 696 ASSERT(!typeInfo().structureHasRareData()); 697 StructureRareData* rareData = StructureRareData::create(vm, previous()); 698 m_typeInfo = TypeInfo(typeInfo().type(), typeInfo().flags() | StructureHasRareData); 699 m_previousOrRareData.set(vm, this, rareData); 700} 701 702void Structure::cloneRareDataFrom(VM& vm, const Structure* other) 703{ 704 ASSERT(other->typeInfo().structureHasRareData()); 705 StructureRareData* newRareData = StructureRareData::clone(vm, other->rareData()); 706 m_typeInfo = TypeInfo(typeInfo().type(), typeInfo().flags() | StructureHasRareData); 707 m_previousOrRareData.set(vm, this, newRareData); 708} 709 710#if DUMP_PROPERTYMAP_STATS 711 712struct PropertyMapStatisticsExitLogger { 713 ~PropertyMapStatisticsExitLogger(); 714}; 715 716static PropertyMapStatisticsExitLogger logger; 717 718PropertyMapStatisticsExitLogger::~PropertyMapStatisticsExitLogger() 719{ 720 dataLogF("\nJSC::PropertyMap statistics\n\n"); 721 dataLogF("%d probes\n", numProbes); 722 dataLogF("%d collisions (%.1f%%)\n", numCollisions, 100.0 * numCollisions / numProbes); 723 dataLogF("%d rehashes\n", numRehashes); 724 dataLogF("%d removes\n", numRemoves); 725} 726 727#endif 728 729#if !DO_PROPERTYMAP_CONSTENCY_CHECK 730 731inline void Structure::checkConsistency() 732{ 733 checkOffsetConsistency(); 734} 735 736#endif 737 738PropertyTable* Structure::copyPropertyTable(VM& vm, Structure* owner) 739{ 740 if (!propertyTable()) 741 return 0; 742 return PropertyTable::clone(vm, owner, *propertyTable().get()); 743} 744 745PropertyTable* Structure::copyPropertyTableForPinning(VM& vm, Structure* owner) 746{ 747 if (propertyTable()) 748 return PropertyTable::clone(vm, owner, *propertyTable().get()); 749 return PropertyTable::create(vm, numberOfSlotsForLastOffset(m_offset, m_inlineCapacity)); 750} 751 752PropertyOffset Structure::get(VM& vm, PropertyName propertyName, unsigned& attributes, JSCell*& specificValue) 753{ 754 ASSERT(structure()->classInfo() == &s_info); 755 756 materializePropertyMapIfNecessary(vm); 757 if (!propertyTable()) 758 return invalidOffset; 759 760 PropertyMapEntry* entry = propertyTable()->find(propertyName.uid()).first; 761 if (!entry) 762 return invalidOffset; 763 764 attributes = entry->attributes; 765 specificValue = entry->specificValue.get(); 766 return entry->offset; 767} 768 769bool Structure::despecifyFunction(VM& vm, PropertyName propertyName) 770{ 771 materializePropertyMapIfNecessary(vm); 772 if (!propertyTable()) 773 return false; 774 775 PropertyMapEntry* entry = propertyTable()->find(propertyName.uid()).first; 776 if (!entry) 777 return false; 778 779 ASSERT(entry->specificValue); 780 entry->specificValue.clear(); 781 return true; 782} 783 784void Structure::despecifyAllFunctions(VM& vm) 785{ 786 materializePropertyMapIfNecessary(vm); 787 if (!propertyTable()) 788 return; 789 790 PropertyTable::iterator end = propertyTable()->end(); 791 for (PropertyTable::iterator iter = propertyTable()->begin(); iter != end; ++iter) 792 iter->specificValue.clear(); 793} 794 795PropertyOffset Structure::putSpecificValue(VM& vm, PropertyName propertyName, unsigned attributes, JSCell* specificValue) 796{ 797 ASSERT(!JSC::isValidOffset(get(vm, propertyName))); 798 799 checkConsistency(); 800 if (attributes & DontEnum) 801 m_hasNonEnumerableProperties = true; 802 803 StringImpl* rep = propertyName.uid(); 804 805 if (!propertyTable()) 806 createPropertyMap(vm); 807 808 PropertyOffset newOffset = propertyTable()->nextOffset(m_inlineCapacity); 809 810 propertyTable()->add(PropertyMapEntry(vm, this, rep, newOffset, attributes, specificValue), m_offset, PropertyTable::PropertyOffsetMayChange); 811 812 checkConsistency(); 813 return newOffset; 814} 815 816PropertyOffset Structure::remove(PropertyName propertyName) 817{ 818 checkConsistency(); 819 820 StringImpl* rep = propertyName.uid(); 821 822 if (!propertyTable()) 823 return invalidOffset; 824 825 PropertyTable::find_iterator position = propertyTable()->find(rep); 826 if (!position.first) 827 return invalidOffset; 828 829 PropertyOffset offset = position.first->offset; 830 831 propertyTable()->remove(position); 832 propertyTable()->addDeletedOffset(offset); 833 834 checkConsistency(); 835 return offset; 836} 837 838void Structure::createPropertyMap(VM& vm, unsigned capacity) 839{ 840 ASSERT(!propertyTable()); 841 842 checkConsistency(); 843 propertyTable().set(vm, this, PropertyTable::create(vm, capacity)); 844} 845 846void Structure::getPropertyNamesFromStructure(VM& vm, PropertyNameArray& propertyNames, EnumerationMode mode) 847{ 848 materializePropertyMapIfNecessary(vm); 849 if (!propertyTable()) 850 return; 851 852 bool knownUnique = !propertyNames.size(); 853 854 PropertyTable::iterator end = propertyTable()->end(); 855 for (PropertyTable::iterator iter = propertyTable()->begin(); iter != end; ++iter) { 856 ASSERT(m_hasNonEnumerableProperties || !(iter->attributes & DontEnum)); 857 if (iter->key->isIdentifier() && (!(iter->attributes & DontEnum) || mode == IncludeDontEnumProperties)) { 858 if (knownUnique) 859 propertyNames.addKnownUnique(iter->key); 860 else 861 propertyNames.add(iter->key); 862 } 863 } 864} 865 866JSValue Structure::prototypeForLookup(CodeBlock* codeBlock) const 867{ 868 return prototypeForLookup(codeBlock->globalObject()); 869} 870 871void Structure::visitChildren(JSCell* cell, SlotVisitor& visitor) 872{ 873 Structure* thisObject = jsCast<Structure*>(cell); 874 ASSERT_GC_OBJECT_INHERITS(thisObject, &s_info); 875 ASSERT(thisObject->structure()->typeInfo().overridesVisitChildren()); 876 877 JSCell::visitChildren(thisObject, visitor); 878 visitor.append(&thisObject->m_globalObject); 879 if (!thisObject->isObject()) 880 thisObject->m_cachedPrototypeChain.clear(); 881 else { 882 visitor.append(&thisObject->m_prototype); 883 visitor.append(&thisObject->m_cachedPrototypeChain); 884 } 885 visitor.append(&thisObject->m_previousOrRareData); 886 visitor.append(&thisObject->m_specificValueInPrevious); 887 888 if (thisObject->m_isPinnedPropertyTable) { 889 ASSERT(thisObject->m_propertyTableUnsafe); 890 visitor.append(&thisObject->m_propertyTableUnsafe); 891 } else if (thisObject->m_propertyTableUnsafe) 892 thisObject->m_propertyTableUnsafe.clear(); 893} 894 895bool Structure::prototypeChainMayInterceptStoreTo(VM& vm, PropertyName propertyName) 896{ 897 unsigned i = propertyName.asIndex(); 898 if (i != PropertyName::NotAnIndex) 899 return anyObjectInChainMayInterceptIndexedAccesses(); 900 901 for (Structure* current = this; ;) { 902 JSValue prototype = current->storedPrototype(); 903 if (prototype.isNull()) 904 return false; 905 906 current = prototype.asCell()->structure(); 907 908 unsigned attributes; 909 JSCell* specificValue; 910 PropertyOffset offset = current->get(vm, propertyName, attributes, specificValue); 911 if (!JSC::isValidOffset(offset)) 912 continue; 913 914 if (attributes & (ReadOnly | Accessor)) 915 return true; 916 917 return false; 918 } 919} 920 921#if DO_PROPERTYMAP_CONSTENCY_CHECK 922 923void PropertyTable::checkConsistency() 924{ 925 checkOffsetConsistency(); 926 ASSERT(m_indexSize >= PropertyTable::MinimumTableSize); 927 ASSERT(m_indexMask); 928 ASSERT(m_indexSize == m_indexMask + 1); 929 ASSERT(!(m_indexSize & m_indexMask)); 930 931 ASSERT(m_keyCount <= m_indexSize / 2); 932 ASSERT(m_keyCount + m_deletedCount <= m_indexSize / 2); 933 ASSERT(m_deletedCount <= m_indexSize / 4); 934 935 unsigned indexCount = 0; 936 unsigned deletedIndexCount = 0; 937 for (unsigned a = 0; a != m_indexSize; ++a) { 938 unsigned entryIndex = m_index[a]; 939 if (entryIndex == PropertyTable::EmptyEntryIndex) 940 continue; 941 if (entryIndex == deletedEntryIndex()) { 942 ++deletedIndexCount; 943 continue; 944 } 945 ASSERT(entryIndex < deletedEntryIndex()); 946 ASSERT(entryIndex - 1 <= usedCount()); 947 ++indexCount; 948 949 for (unsigned b = a + 1; b != m_indexSize; ++b) 950 ASSERT(m_index[b] != entryIndex); 951 } 952 ASSERT(indexCount == m_keyCount); 953 ASSERT(deletedIndexCount == m_deletedCount); 954 955 ASSERT(!table()[deletedEntryIndex() - 1].key); 956 957 unsigned nonEmptyEntryCount = 0; 958 for (unsigned c = 0; c < usedCount(); ++c) { 959 StringImpl* rep = table()[c].key; 960 if (rep == PROPERTY_MAP_DELETED_ENTRY_KEY) 961 continue; 962 ++nonEmptyEntryCount; 963 unsigned i = rep->existingHash(); 964 unsigned k = 0; 965 unsigned entryIndex; 966 while (1) { 967 entryIndex = m_index[i & m_indexMask]; 968 ASSERT(entryIndex != PropertyTable::EmptyEntryIndex); 969 if (rep == table()[entryIndex - 1].key) 970 break; 971 if (k == 0) 972 k = 1 | doubleHash(rep->existingHash()); 973 i += k; 974 } 975 ASSERT(entryIndex == c + 1); 976 } 977 978 ASSERT(nonEmptyEntryCount == m_keyCount); 979} 980 981void Structure::checkConsistency() 982{ 983 if (!propertyTable()) 984 return; 985 986 if (!m_hasNonEnumerableProperties) { 987 PropertyTable::iterator end = propertyTable()->end(); 988 for (PropertyTable::iterator iter = propertyTable()->begin(); iter != end; ++iter) { 989 ASSERT(!(iter->attributes & DontEnum)); 990 } 991 } 992 993 propertyTable()->checkConsistency(); 994} 995 996#endif // DO_PROPERTYMAP_CONSTENCY_CHECK 997 998} // namespace JSC 999