runtime/Structure.cpp

   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
  48 using namespace std;
  49 using namespace WTF;
  50
  51 #if DUMP_PROPERTYMAP_STATS
  52
  53 int numProbes;
  54 int numCollisions;
  55 int numRehashes;
  56 int numRemoves;
  57
  58 #endif
  59
  60 namespace JSC {
  61
  62 #if DUMP_STRUCTURE_ID_STATISTICS
  63 static HashSet<Structure*>& liveStructureSet = *(new HashSet<Structure*>);
  64 #endif
  65
  66 bool 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
  75 inline 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
  84 inline 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
 109 void 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
 154 Structure::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
 180 const ClassInfo Structure::s_info = { "Structure", 0, 0, 0, CREATE_METHOD_TABLE(Structure) };
 181
 182 Structure::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
 204 Structure::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
 234 void Structure::destroy(JSCell* cell)
 235 {
 236     static_cast<Structure*>(cell)->Structure::~Structure();
 237 }
 238
 239 void 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
 276 inline size_t nextOutOfLineStorageCapacity(size_t currentCapacity)
 277 {
 278     if (!currentCapacity)
 279         return initialOutOfLineCapacity;
 280     return currentCapacity * outOfLineGrowthFactor;
 281 }
 282
 283 size_t Structure::suggestedNewOutOfLineStorageCapacity()
 284 {
 285     return nextOutOfLineStorageCapacity(outOfLineCapacity());
 286 }
 287
 288 void 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
 302 Structure* 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
 319 bool 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
 333 bool Structure::needsSlowPutIndexing() const
 334 {
 335     return anyObjectInChainMayInterceptIndexedAccesses()
 336         || globalObject()->isHavingABadTime();
 337 }
 338
 339 NonPropertyTransition Structure::suggestedArrayStorageTransition() const
 340 {
 341     if (needsSlowPutIndexing())
 342         return AllocateSlowPutArrayStorage;
 343
 344     return AllocateArrayStorage;
 345 }
 346
 347 Structure* 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
 392 Structure* 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
 404 Structure* 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
 419 Structure* 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
 442 Structure* 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
 464 Structure* 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
 480 Structure* Structure::toCacheableDictionaryTransition(VM& vm, Structure* structure)
 481 {
 482     return toDictionaryTransition(vm, structure, CachedDictionaryKind);
 483 }
 484
 485 Structure* 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.
 491 Structure* 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.
 506 Structure* 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.
 524 Structure* 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
 540 PropertyTable* 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
 550 Structure* 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.
 585 bool 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.
 603 bool 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
 622 Structure* 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
 661 PropertyOffset 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
 675 PropertyOffset 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
 686 void Structure::pin()
 687 {
 688     ASSERT(propertyTable());
 689     m_isPinnedPropertyTable = true;
 690     clearPreviousID();
 691     m_nameInPrevious.clear();
 692 }
 693
 694 void 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
 702 void 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
 712 struct PropertyMapStatisticsExitLogger {
 713     ~PropertyMapStatisticsExitLogger();
 714 };
 715
 716 static PropertyMapStatisticsExitLogger logger;
 717
 718 PropertyMapStatisticsExitLogger::~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
 731 inline void Structure::checkConsistency()
 732 {
 733     checkOffsetConsistency();
 734 }
 735
 736 #endif
 737
 738 PropertyTable* Structure::copyPropertyTable(VM& vm, Structure* owner)
 739 {
 740     if (!propertyTable())
 741         return 0;
 742     return PropertyTable::clone(vm, owner, *propertyTable().get());
 743 }
 744
 745 PropertyTable* 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
 752 PropertyOffset 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
 769 bool 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
 784 void 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
 795 PropertyOffset 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
 816 PropertyOffset 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
 838 void Structure::createPropertyMap(VM& vm, unsigned capacity)
 839 {
 840     ASSERT(!propertyTable());
 841
 842     checkConsistency();
 843     propertyTable().set(vm, this, PropertyTable::create(vm, capacity));
 844 }
 845
 846 void 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
 866 JSValue Structure::prototypeForLookup(CodeBlock* codeBlock) const
 867 {
 868     return prototypeForLookup(codeBlock->globalObject());
 869 }
 870
 871 void 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
 895 bool 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
 923 void 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
 981 void 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