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     return this;
 653 }
 654
 655 PropertyOffset Structure::addPropertyWithoutTransition(VM& vm, PropertyName propertyName, unsigned attributes, JSCell* specificValue)
 656 {
 657     ASSERT(!enumerationCache());
 658
 659     if (m_specificFunctionThrashCount == maxSpecificFunctionThrashCount)
 660         specificValue = 0;
 661
 662     materializePropertyMapIfNecessaryForPinning(vm);
 663
 664     pin();
 665
 666     return putSpecificValue(vm, propertyName, attributes, specificValue);
 667 }
 668
 669 PropertyOffset Structure::removePropertyWithoutTransition(VM& vm, PropertyName propertyName)
 670 {
 671     ASSERT(isUncacheableDictionary());
 672     ASSERT(!enumerationCache());
 673
 674     materializePropertyMapIfNecessaryForPinning(vm);
 675
 676     pin();
 677     return remove(propertyName);
 678 }
 679
 680 void Structure::pin()
 681 {
 682     ASSERT(propertyTable());
 683     m_isPinnedPropertyTable = true;
 684     clearPreviousID();
 685     m_nameInPrevious.clear();
 686 }
 687
 688 void Structure::allocateRareData(VM& vm)
 689 {
 690     ASSERT(!typeInfo().structureHasRareData());
 691     StructureRareData* rareData = StructureRareData::create(vm, previous());
 692     m_typeInfo = TypeInfo(typeInfo().type(), typeInfo().flags() | StructureHasRareData);
 693     m_previousOrRareData.set(vm, this, rareData);
 694 }
 695
 696 void Structure::cloneRareDataFrom(VM& vm, const Structure* other)
 697 {
 698     ASSERT(other->typeInfo().structureHasRareData());
 699     StructureRareData* newRareData = StructureRareData::clone(vm, other->rareData());
 700     m_typeInfo = TypeInfo(typeInfo().type(), typeInfo().flags() | StructureHasRareData);
 701     m_previousOrRareData.set(vm, this, newRareData);
 702 }
 703
 704 #if DUMP_PROPERTYMAP_STATS
 705
 706 struct PropertyMapStatisticsExitLogger {
 707     ~PropertyMapStatisticsExitLogger();
 708 };
 709
 710 static PropertyMapStatisticsExitLogger logger;
 711
 712 PropertyMapStatisticsExitLogger::~PropertyMapStatisticsExitLogger()
 713 {
 714     dataLogF("\nJSC::PropertyMap statistics\n\n");
 715     dataLogF("%d probes\n", numProbes);
 716     dataLogF("%d collisions (%.1f%%)\n", numCollisions, 100.0 * numCollisions / numProbes);
 717     dataLogF("%d rehashes\n", numRehashes);
 718     dataLogF("%d removes\n", numRemoves);
 719 }
 720
 721 #endif
 722
 723 #if !DO_PROPERTYMAP_CONSTENCY_CHECK
 724
 725 inline void Structure::checkConsistency()
 726 {
 727     checkOffsetConsistency();
 728 }
 729
 730 #endif
 731
 732 PropertyTable* Structure::copyPropertyTable(VM& vm, Structure* owner)
 733 {
 734     if (!propertyTable())
 735         return 0;
 736     return PropertyTable::clone(vm, owner, *propertyTable().get());
 737 }
 738
 739 PropertyTable* Structure::copyPropertyTableForPinning(VM& vm, Structure* owner)
 740 {
 741     if (propertyTable())
 742         return PropertyTable::clone(vm, owner, *propertyTable().get());
 743     return PropertyTable::create(vm, numberOfSlotsForLastOffset(m_offset, m_inlineCapacity));
 744 }
 745
 746 PropertyOffset Structure::get(VM& vm, PropertyName propertyName, unsigned& attributes, JSCell*& specificValue)
 747 {
 748     ASSERT(structure()->classInfo() == &s_info);
 749
 750     materializePropertyMapIfNecessary(vm);
 751     if (!propertyTable())
 752         return invalidOffset;
 753
 754     PropertyMapEntry* entry = propertyTable()->find(propertyName.uid()).first;
 755     if (!entry)
 756         return invalidOffset;
 757
 758     attributes = entry->attributes;
 759     specificValue = entry->specificValue.get();
 760     return entry->offset;
 761 }
 762
 763 bool Structure::despecifyFunction(VM& vm, PropertyName propertyName)
 764 {
 765     materializePropertyMapIfNecessary(vm);
 766     if (!propertyTable())
 767         return false;
 768
 769     PropertyMapEntry* entry = propertyTable()->find(propertyName.uid()).first;
 770     if (!entry)
 771         return false;
 772
 773     ASSERT(entry->specificValue);
 774     entry->specificValue.clear();
 775     return true;
 776 }
 777
 778 void Structure::despecifyAllFunctions(VM& vm)
 779 {
 780     materializePropertyMapIfNecessary(vm);
 781     if (!propertyTable())
 782         return;
 783
 784     PropertyTable::iterator end = propertyTable()->end();
 785     for (PropertyTable::iterator iter = propertyTable()->begin(); iter != end; ++iter)
 786         iter->specificValue.clear();
 787 }
 788
 789 PropertyOffset Structure::putSpecificValue(VM& vm, PropertyName propertyName, unsigned attributes, JSCell* specificValue)
 790 {
 791     ASSERT(!JSC::isValidOffset(get(vm, propertyName)));
 792
 793     checkConsistency();
 794     if (attributes & DontEnum)
 795         m_hasNonEnumerableProperties = true;
 796
 797     StringImpl* rep = propertyName.uid();
 798
 799     if (!propertyTable())
 800         createPropertyMap(vm);
 801
 802     PropertyOffset newOffset = propertyTable()->nextOffset(m_inlineCapacity);
 803
 804     propertyTable()->add(PropertyMapEntry(vm, this, rep, newOffset, attributes, specificValue), m_offset, PropertyTable::PropertyOffsetMayChange);
 805
 806     checkConsistency();
 807     return newOffset;
 808 }
 809
 810 PropertyOffset Structure::remove(PropertyName propertyName)
 811 {
 812     checkConsistency();
 813
 814     StringImpl* rep = propertyName.uid();
 815
 816     if (!propertyTable())
 817         return invalidOffset;
 818
 819     PropertyTable::find_iterator position = propertyTable()->find(rep);
 820     if (!position.first)
 821         return invalidOffset;
 822
 823     PropertyOffset offset = position.first->offset;
 824
 825     propertyTable()->remove(position);
 826     propertyTable()->addDeletedOffset(offset);
 827
 828     checkConsistency();
 829     return offset;
 830 }
 831
 832 void Structure::createPropertyMap(VM& vm, unsigned capacity)
 833 {
 834     ASSERT(!propertyTable());
 835
 836     checkConsistency();
 837     propertyTable().set(vm, this, PropertyTable::create(vm, capacity));
 838 }
 839
 840 void Structure::getPropertyNamesFromStructure(VM& vm, PropertyNameArray& propertyNames, EnumerationMode mode)
 841 {
 842     materializePropertyMapIfNecessary(vm);
 843     if (!propertyTable())
 844         return;
 845
 846     bool knownUnique = !propertyNames.size();
 847
 848     PropertyTable::iterator end = propertyTable()->end();
 849     for (PropertyTable::iterator iter = propertyTable()->begin(); iter != end; ++iter) {
 850         ASSERT(m_hasNonEnumerableProperties || !(iter->attributes & DontEnum));
 851         if (iter->key->isIdentifier() && (!(iter->attributes & DontEnum) || mode == IncludeDontEnumProperties)) {
 852             if (knownUnique)
 853                 propertyNames.addKnownUnique(iter->key);
 854             else
 855                 propertyNames.add(iter->key);
 856         }
 857     }
 858 }
 859
 860 JSValue Structure::prototypeForLookup(CodeBlock* codeBlock) const
 861 {
 862     return prototypeForLookup(codeBlock->globalObject());
 863 }
 864
 865 void Structure::visitChildren(JSCell* cell, SlotVisitor& visitor)
 866 {
 867     Structure* thisObject = jsCast<Structure*>(cell);
 868     ASSERT_GC_OBJECT_INHERITS(thisObject, &s_info);
 869     ASSERT(thisObject->structure()->typeInfo().overridesVisitChildren());
 870
 871     JSCell::visitChildren(thisObject, visitor);
 872     visitor.append(&thisObject->m_globalObject);
 873     if (!thisObject->isObject())
 874         thisObject->m_cachedPrototypeChain.clear();
 875     else {
 876         visitor.append(&thisObject->m_prototype);
 877         visitor.append(&thisObject->m_cachedPrototypeChain);
 878     }
 879     visitor.append(&thisObject->m_previousOrRareData);
 880     visitor.append(&thisObject->m_specificValueInPrevious);
 881
 882     if (thisObject->m_isPinnedPropertyTable) {
 883         ASSERT(thisObject->m_propertyTableUnsafe);
 884         visitor.append(&thisObject->m_propertyTableUnsafe);
 885     } else if (thisObject->m_propertyTableUnsafe)
 886         thisObject->m_propertyTableUnsafe.clear();
 887 }
 888
 889 bool Structure::prototypeChainMayInterceptStoreTo(VM& vm, PropertyName propertyName)
 890 {
 891     unsigned i = propertyName.asIndex();
 892     if (i != PropertyName::NotAnIndex)
 893         return anyObjectInChainMayInterceptIndexedAccesses();
 894
 895     for (Structure* current = this; ;) {
 896         JSValue prototype = current->storedPrototype();
 897         if (prototype.isNull())
 898             return false;
 899
 900         current = prototype.asCell()->structure();
 901
 902         unsigned attributes;
 903         JSCell* specificValue;
 904         PropertyOffset offset = current->get(vm, propertyName, attributes, specificValue);
 905         if (!JSC::isValidOffset(offset))
 906             continue;
 907
 908         if (attributes & (ReadOnly | Accessor))
 909             return true;
 910
 911         return false;
 912     }
 913 }
 914
 915 #if DO_PROPERTYMAP_CONSTENCY_CHECK
 916
 917 void PropertyTable::checkConsistency()
 918 {
 919     checkOffsetConsistency();
 920     ASSERT(m_indexSize >= PropertyTable::MinimumTableSize);
 921     ASSERT(m_indexMask);
 922     ASSERT(m_indexSize == m_indexMask + 1);
 923     ASSERT(!(m_indexSize & m_indexMask));
 924
 925     ASSERT(m_keyCount <= m_indexSize / 2);
 926     ASSERT(m_keyCount + m_deletedCount <= m_indexSize / 2);
 927     ASSERT(m_deletedCount <= m_indexSize / 4);
 928
 929     unsigned indexCount = 0;
 930     unsigned deletedIndexCount = 0;
 931     for (unsigned a = 0; a != m_indexSize; ++a) {
 932         unsigned entryIndex = m_index[a];
 933         if (entryIndex == PropertyTable::EmptyEntryIndex)
 934             continue;
 935         if (entryIndex == deletedEntryIndex()) {
 936             ++deletedIndexCount;
 937             continue;
 938         }
 939         ASSERT(entryIndex < deletedEntryIndex());
 940         ASSERT(entryIndex - 1 <= usedCount());
 941         ++indexCount;
 942
 943         for (unsigned b = a + 1; b != m_indexSize; ++b)
 944             ASSERT(m_index[b] != entryIndex);
 945     }
 946     ASSERT(indexCount == m_keyCount);
 947     ASSERT(deletedIndexCount == m_deletedCount);
 948
 949     ASSERT(!table()[deletedEntryIndex() - 1].key);
 950
 951     unsigned nonEmptyEntryCount = 0;
 952     for (unsigned c = 0; c < usedCount(); ++c) {
 953         StringImpl* rep = table()[c].key;
 954         if (rep == PROPERTY_MAP_DELETED_ENTRY_KEY)
 955             continue;
 956         ++nonEmptyEntryCount;
 957         unsigned i = rep->existingHash();
 958         unsigned k = 0;
 959         unsigned entryIndex;
 960         while (1) {
 961             entryIndex = m_index[i & m_indexMask];
 962             ASSERT(entryIndex != PropertyTable::EmptyEntryIndex);
 963             if (rep == table()[entryIndex - 1].key)
 964                 break;
 965             if (k == 0)
 966                 k = 1 | doubleHash(rep->existingHash());
 967             i += k;
 968         }
 969         ASSERT(entryIndex == c + 1);
 970     }
 971
 972     ASSERT(nonEmptyEntryCount == m_keyCount);
 973 }
 974
 975 void Structure::checkConsistency()
 976 {
 977     if (!propertyTable())
 978         return;
 979
 980     if (!m_hasNonEnumerableProperties) {
 981         PropertyTable::iterator end = propertyTable()->end();
 982         for (PropertyTable::iterator iter = propertyTable()->begin(); iter != end; ++iter) {
 983             ASSERT(!(iter->attributes & DontEnum));
 984         }
 985     }
 986
 987     propertyTable()->checkConsistency();
 988 }
 989
 990 #endif // DO_PROPERTYMAP_CONSTENCY_CHECK
 991
 992 } // namespace JSC