runtime/Structure.cpp

   1 /*
   2  * Copyright (C) 2008, 2009 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 "Identifier.h"
  30 #include "JSObject.h"
  31 #include "JSPropertyNameIterator.h"
  32 #include "Lookup.h"
  33 #include "PropertyNameArray.h"
  34 #include "StructureChain.h"
  35 #include <wtf/RefCountedLeakCounter.h>
  36 #include <wtf/RefPtr.h>
  37
  38 #if ENABLE(JSC_MULTIPLE_THREADS)
  39 #include <wtf/Threading.h>
  40 #endif
  41
  42 #define DUMP_STRUCTURE_ID_STATISTICS 0
  43
  44 #ifndef NDEBUG
  45 #define DO_PROPERTYMAP_CONSTENCY_CHECK 0
  46 #else
  47 #define DO_PROPERTYMAP_CONSTENCY_CHECK 0
  48 #endif
  49
  50 using namespace std;
  51 using namespace WTF;
  52
  53 namespace JSC {
  54
  55 // Choose a number for the following so that most property maps are smaller,
  56 // but it's not going to blow out the stack to allocate this number of pointers.
  57 static const int smallMapThreshold = 1024;
  58
  59 // The point at which the function call overhead of the qsort implementation
  60 // becomes small compared to the inefficiency of insertion sort.
  61 static const unsigned tinyMapThreshold = 20;
  62
  63 static const unsigned newTableSize = 16;
  64
  65 #ifndef NDEBUG
  66 static WTF::RefCountedLeakCounter structureCounter("Structure");
  67
  68 #if ENABLE(JSC_MULTIPLE_THREADS)
  69 static Mutex& ignoreSetMutex = *(new Mutex);
  70 #endif
  71
  72 static bool shouldIgnoreLeaks;
  73 static HashSet<Structure*>& ignoreSet = *(new HashSet<Structure*>);
  74 #endif
  75
  76 #if DUMP_STRUCTURE_ID_STATISTICS
  77 static HashSet<Structure*>& liveStructureSet = *(new HashSet<Structure*>);
  78 #endif
  79
  80 static int comparePropertyMapEntryIndices(const void* a, const void* b);
  81
  82 void Structure::dumpStatistics()
  83 {
  84 #if DUMP_STRUCTURE_ID_STATISTICS
  85     unsigned numberLeaf = 0;
  86     unsigned numberUsingSingleSlot = 0;
  87     unsigned numberSingletons = 0;
  88     unsigned numberWithPropertyMaps = 0;
  89     unsigned totalPropertyMapsSize = 0;
  90
  91     HashSet<Structure*>::const_iterator end = liveStructureSet.end();
  92     for (HashSet<Structure*>::const_iterator it = liveStructureSet.begin(); it != end; ++it) {
  93         Structure* structure = *it;
  94         if (structure->m_usingSingleTransitionSlot) {
  95             if (!structure->m_transitions.singleTransition)
  96                 ++numberLeaf;
  97             else
  98                 ++numberUsingSingleSlot;
  99
 100            if (!structure->m_previous && !structure->m_transitions.singleTransition)
 101                 ++numberSingletons;
 102         }
 103
 104         if (structure->m_propertyTable) {
 105             ++numberWithPropertyMaps;
 106             totalPropertyMapsSize += PropertyMapHashTable::allocationSize(structure->m_propertyTable->size);
 107             if (structure->m_propertyTable->deletedOffsets)
 108                 totalPropertyMapsSize += (structure->m_propertyTable->deletedOffsets->capacity() * sizeof(unsigned));
 109         }
 110     }
 111
 112     printf("Number of live Structures: %d\n", liveStructureSet.size());
 113     printf("Number of Structures using the single item optimization for transition map: %d\n", numberUsingSingleSlot);
 114     printf("Number of Structures that are leaf nodes: %d\n", numberLeaf);
 115     printf("Number of Structures that singletons: %d\n", numberSingletons);
 116     printf("Number of Structures with PropertyMaps: %d\n", numberWithPropertyMaps);
 117
 118     printf("Size of a single Structures: %d\n", static_cast<unsigned>(sizeof(Structure)));
 119     printf("Size of sum of all property maps: %d\n", totalPropertyMapsSize);
 120     printf("Size of average of all property maps: %f\n", static_cast<double>(totalPropertyMapsSize) / static_cast<double>(liveStructureSet.size()));
 121 #else
 122     printf("Dumping Structure statistics is not enabled.\n");
 123 #endif
 124 }
 125
 126 Structure::Structure(JSValue prototype, const TypeInfo& typeInfo, unsigned anonymousSlotCount)
 127     : m_typeInfo(typeInfo)
 128     , m_prototype(prototype)
 129     , m_specificValueInPrevious(0)
 130     , m_propertyTable(0)
 131     , m_propertyStorageCapacity(JSObject::inlineStorageCapacity)
 132     , m_offset(noOffset)
 133     , m_dictionaryKind(NoneDictionaryKind)
 134     , m_isPinnedPropertyTable(false)
 135     , m_hasGetterSetterProperties(false)
 136     , m_attributesInPrevious(0)
 137     , m_specificFunctionThrashCount(0)
 138     , m_anonymousSlotCount(anonymousSlotCount)
 139 {
 140     ASSERT(m_prototype);
 141     ASSERT(m_prototype.isObject() || m_prototype.isNull());
 142
 143 #ifndef NDEBUG
 144 #if ENABLE(JSC_MULTIPLE_THREADS)
 145     MutexLocker protect(ignoreSetMutex);
 146 #endif
 147     if (shouldIgnoreLeaks)
 148         ignoreSet.add(this);
 149     else
 150         structureCounter.increment();
 151 #endif
 152
 153 #if DUMP_STRUCTURE_ID_STATISTICS
 154     liveStructureSet.add(this);
 155 #endif
 156 }
 157
 158 Structure::~Structure()
 159 {
 160     if (m_previous) {
 161         ASSERT(m_nameInPrevious);
 162         m_previous->table.remove(make_pair(m_nameInPrevious.get(), m_attributesInPrevious), m_specificValueInPrevious);
 163
 164     }
 165
 166     if (m_enumerationCache)
 167         m_enumerationCache->setCachedStructure(0);
 168
 169     if (m_propertyTable) {
 170         unsigned entryCount = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount;
 171         for (unsigned i = 1; i <= entryCount; i++) {
 172             if (UString::Rep* key = m_propertyTable->entries()[i].key)
 173                 key->deref();
 174         }
 175
 176         delete m_propertyTable->deletedOffsets;
 177         fastFree(m_propertyTable);
 178     }
 179
 180 #ifndef NDEBUG
 181 #if ENABLE(JSC_MULTIPLE_THREADS)
 182     MutexLocker protect(ignoreSetMutex);
 183 #endif
 184     HashSet<Structure*>::iterator it = ignoreSet.find(this);
 185     if (it != ignoreSet.end())
 186         ignoreSet.remove(it);
 187     else
 188         structureCounter.decrement();
 189 #endif
 190
 191 #if DUMP_STRUCTURE_ID_STATISTICS
 192     liveStructureSet.remove(this);
 193 #endif
 194 }
 195
 196 void Structure::startIgnoringLeaks()
 197 {
 198 #ifndef NDEBUG
 199     shouldIgnoreLeaks = true;
 200 #endif
 201 }
 202
 203 void Structure::stopIgnoringLeaks()
 204 {
 205 #ifndef NDEBUG
 206     shouldIgnoreLeaks = false;
 207 #endif
 208 }
 209
 210 static bool isPowerOf2(unsigned v)
 211 {
 212     // Taken from http://www.cs.utk.edu/~vose/c-stuff/bithacks.html
 213
 214     return !(v & (v - 1)) && v;
 215 }
 216
 217 static unsigned nextPowerOf2(unsigned v)
 218 {
 219     // Taken from http://www.cs.utk.edu/~vose/c-stuff/bithacks.html
 220     // Devised by Sean Anderson, Sepember 14, 2001
 221
 222     v--;
 223     v |= v >> 1;
 224     v |= v >> 2;
 225     v |= v >> 4;
 226     v |= v >> 8;
 227     v |= v >> 16;
 228     v++;
 229
 230     return v;
 231 }
 232
 233 static unsigned sizeForKeyCount(size_t keyCount)
 234 {
 235     if (keyCount == notFound)
 236         return newTableSize;
 237
 238     if (keyCount < 8)
 239         return newTableSize;
 240
 241     if (isPowerOf2(keyCount))
 242         return keyCount * 4;
 243
 244     return nextPowerOf2(keyCount) * 2;
 245 }
 246
 247 void Structure::materializePropertyMap()
 248 {
 249     ASSERT(!m_propertyTable);
 250
 251     Vector<Structure*, 8> structures;
 252     structures.append(this);
 253
 254     Structure* structure = this;
 255
 256     // Search for the last Structure with a property table.
 257     while ((structure = structure->previousID())) {
 258         if (structure->m_isPinnedPropertyTable) {
 259             ASSERT(structure->m_propertyTable);
 260             ASSERT(!structure->m_previous);
 261
 262             m_propertyTable = structure->copyPropertyTable();
 263             break;
 264         }
 265
 266         structures.append(structure);
 267     }
 268
 269     if (!m_propertyTable)
 270         createPropertyMapHashTable(sizeForKeyCount(m_offset + 1));
 271     else {
 272         if (sizeForKeyCount(m_offset + 1) > m_propertyTable->size)
 273             rehashPropertyMapHashTable(sizeForKeyCount(m_offset + 1)); // This could be made more efficient by combining with the copy above.
 274     }
 275
 276     for (ptrdiff_t i = structures.size() - 2; i >= 0; --i) {
 277         structure = structures[i];
 278         structure->m_nameInPrevious->ref();
 279         PropertyMapEntry entry(structure->m_nameInPrevious.get(), m_anonymousSlotCount + structure->m_offset, structure->m_attributesInPrevious, structure->m_specificValueInPrevious, ++m_propertyTable->lastIndexUsed);
 280         insertIntoPropertyMapHashTable(entry);
 281     }
 282 }
 283
 284 void Structure::growPropertyStorageCapacity()
 285 {
 286     if (m_propertyStorageCapacity == JSObject::inlineStorageCapacity)
 287         m_propertyStorageCapacity = JSObject::nonInlineBaseStorageCapacity;
 288     else
 289         m_propertyStorageCapacity *= 2;
 290 }
 291
 292 void Structure::despecifyDictionaryFunction(const Identifier& propertyName)
 293 {
 294     const UString::Rep* rep = propertyName._ustring.rep();
 295
 296     materializePropertyMapIfNecessary();
 297
 298     ASSERT(isDictionary());
 299     ASSERT(m_propertyTable);
 300
 301     unsigned i = rep->existingHash();
 302
 303 #if DUMP_PROPERTYMAP_STATS
 304     ++numProbes;
 305 #endif
 306
 307     unsigned entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
 308     ASSERT(entryIndex != emptyEntryIndex);
 309
 310     if (rep == m_propertyTable->entries()[entryIndex - 1].key) {
 311         m_propertyTable->entries()[entryIndex - 1].specificValue = 0;
 312         return;
 313     }
 314
 315 #if DUMP_PROPERTYMAP_STATS
 316     ++numCollisions;
 317 #endif
 318
 319     unsigned k = 1 | doubleHash(rep->existingHash());
 320
 321     while (1) {
 322         i += k;
 323
 324 #if DUMP_PROPERTYMAP_STATS
 325         ++numRehashes;
 326 #endif
 327
 328         entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
 329         ASSERT(entryIndex != emptyEntryIndex);
 330
 331         if (rep == m_propertyTable->entries()[entryIndex - 1].key) {
 332             m_propertyTable->entries()[entryIndex - 1].specificValue = 0;
 333             return;
 334         }
 335     }
 336 }
 337
 338 PassRefPtr<Structure> Structure::addPropertyTransitionToExistingStructure(Structure* structure, const Identifier& propertyName, unsigned attributes, JSCell* specificValue, size_t& offset)
 339 {
 340     ASSERT(!structure->isDictionary());
 341     ASSERT(structure->typeInfo().type() == ObjectType);
 342
 343     if (Structure* existingTransition = structure->table.get(make_pair(propertyName.ustring().rep(), attributes), specificValue)) {
 344         ASSERT(existingTransition->m_offset != noOffset);
 345         offset = existingTransition->m_offset + existingTransition->m_anonymousSlotCount;
 346         ASSERT(offset >= structure->m_anonymousSlotCount);
 347         ASSERT(structure->m_anonymousSlotCount == existingTransition->m_anonymousSlotCount);
 348         return existingTransition;
 349     }
 350
 351     return 0;
 352 }
 353
 354 PassRefPtr<Structure> Structure::addPropertyTransition(Structure* structure, const Identifier& propertyName, unsigned attributes, JSCell* specificValue, size_t& offset)
 355 {
 356     ASSERT(!structure->isDictionary());
 357     ASSERT(structure->typeInfo().type() == ObjectType);
 358     ASSERT(!Structure::addPropertyTransitionToExistingStructure(structure, propertyName, attributes, specificValue, offset));
 359
 360     if (structure->m_specificFunctionThrashCount == maxSpecificFunctionThrashCount)
 361         specificValue = 0;
 362
 363     if (structure->transitionCount() > s_maxTransitionLength) {
 364         RefPtr<Structure> transition = toCacheableDictionaryTransition(structure);
 365         ASSERT(structure != transition);
 366         offset = transition->put(propertyName, attributes, specificValue);
 367         ASSERT(offset >= structure->m_anonymousSlotCount);
 368         ASSERT(structure->m_anonymousSlotCount == transition->m_anonymousSlotCount);
 369         if (transition->propertyStorageSize() > transition->propertyStorageCapacity())
 370             transition->growPropertyStorageCapacity();
 371         return transition.release();
 372     }
 373
 374     RefPtr<Structure> transition = create(structure->m_prototype, structure->typeInfo(), structure->anonymousSlotCount());
 375
 376     transition->m_cachedPrototypeChain = structure->m_cachedPrototypeChain;
 377     transition->m_previous = structure;
 378     transition->m_nameInPrevious = propertyName.ustring().rep();
 379     transition->m_attributesInPrevious = attributes;
 380     transition->m_specificValueInPrevious = specificValue;
 381     transition->m_propertyStorageCapacity = structure->m_propertyStorageCapacity;
 382     transition->m_hasGetterSetterProperties = structure->m_hasGetterSetterProperties;
 383     transition->m_hasNonEnumerableProperties = structure->m_hasNonEnumerableProperties;
 384     transition->m_specificFunctionThrashCount = structure->m_specificFunctionThrashCount;
 385
 386     if (structure->m_propertyTable) {
 387         if (structure->m_isPinnedPropertyTable)
 388             transition->m_propertyTable = structure->copyPropertyTable();
 389         else {
 390             transition->m_propertyTable = structure->m_propertyTable;
 391             structure->m_propertyTable = 0;
 392         }
 393     } else {
 394         if (structure->m_previous)
 395             transition->materializePropertyMap();
 396         else
 397             transition->createPropertyMapHashTable();
 398     }
 399
 400     offset = transition->put(propertyName, attributes, specificValue);
 401     ASSERT(offset >= structure->m_anonymousSlotCount);
 402     ASSERT(structure->m_anonymousSlotCount == transition->m_anonymousSlotCount);
 403     if (transition->propertyStorageSize() > transition->propertyStorageCapacity())
 404         transition->growPropertyStorageCapacity();
 405
 406     transition->m_offset = offset - structure->m_anonymousSlotCount;
 407     ASSERT(structure->anonymousSlotCount() == transition->anonymousSlotCount());
 408     structure->table.add(make_pair(propertyName.ustring().rep(), attributes), transition.get(), specificValue);
 409     return transition.release();
 410 }
 411
 412 PassRefPtr<Structure> Structure::removePropertyTransition(Structure* structure, const Identifier& propertyName, size_t& offset)
 413 {
 414     ASSERT(!structure->isUncacheableDictionary());
 415
 416     RefPtr<Structure> transition = toUncacheableDictionaryTransition(structure);
 417
 418     offset = transition->remove(propertyName);
 419     ASSERT(offset >= structure->m_anonymousSlotCount);
 420     ASSERT(structure->m_anonymousSlotCount == transition->m_anonymousSlotCount);
 421
 422     return transition.release();
 423 }
 424
 425 PassRefPtr<Structure> Structure::changePrototypeTransition(Structure* structure, JSValue prototype)
 426 {
 427     RefPtr<Structure> transition = create(prototype, structure->typeInfo(), structure->anonymousSlotCount());
 428
 429     transition->m_propertyStorageCapacity = structure->m_propertyStorageCapacity;
 430     transition->m_hasGetterSetterProperties = structure->m_hasGetterSetterProperties;
 431     transition->m_hasNonEnumerableProperties = structure->m_hasNonEnumerableProperties;
 432     transition->m_specificFunctionThrashCount = structure->m_specificFunctionThrashCount;
 433
 434     // Don't set m_offset, as one can not transition to this.
 435
 436     structure->materializePropertyMapIfNecessary();
 437     transition->m_propertyTable = structure->copyPropertyTable();
 438     transition->m_isPinnedPropertyTable = true;
 439
 440     ASSERT(structure->anonymousSlotCount() == transition->anonymousSlotCount());
 441     return transition.release();
 442 }
 443
 444 PassRefPtr<Structure> Structure::despecifyFunctionTransition(Structure* structure, const Identifier& replaceFunction)
 445 {
 446     ASSERT(structure->m_specificFunctionThrashCount < maxSpecificFunctionThrashCount);
 447     RefPtr<Structure> transition = create(structure->storedPrototype(), structure->typeInfo(), structure->anonymousSlotCount());
 448
 449     transition->m_propertyStorageCapacity = structure->m_propertyStorageCapacity;
 450     transition->m_hasGetterSetterProperties = structure->m_hasGetterSetterProperties;
 451     transition->m_hasNonEnumerableProperties = structure->m_hasNonEnumerableProperties;
 452     transition->m_specificFunctionThrashCount = structure->m_specificFunctionThrashCount + 1;
 453
 454     // Don't set m_offset, as one can not transition to this.
 455
 456     structure->materializePropertyMapIfNecessary();
 457     transition->m_propertyTable = structure->copyPropertyTable();
 458     transition->m_isPinnedPropertyTable = true;
 459
 460     if (transition->m_specificFunctionThrashCount == maxSpecificFunctionThrashCount)
 461         transition->despecifyAllFunctions();
 462     else {
 463         bool removed = transition->despecifyFunction(replaceFunction);
 464         ASSERT_UNUSED(removed, removed);
 465     }
 466
 467     ASSERT(structure->anonymousSlotCount() == transition->anonymousSlotCount());
 468     return transition.release();
 469 }
 470
 471 PassRefPtr<Structure> Structure::getterSetterTransition(Structure* structure)
 472 {
 473     RefPtr<Structure> transition = create(structure->storedPrototype(), structure->typeInfo(), structure->anonymousSlotCount());
 474     transition->m_propertyStorageCapacity = structure->m_propertyStorageCapacity;
 475     transition->m_hasGetterSetterProperties = transition->m_hasGetterSetterProperties;
 476     transition->m_hasNonEnumerableProperties = structure->m_hasNonEnumerableProperties;
 477     transition->m_specificFunctionThrashCount = structure->m_specificFunctionThrashCount;
 478
 479     // Don't set m_offset, as one can not transition to this.
 480
 481     structure->materializePropertyMapIfNecessary();
 482     transition->m_propertyTable = structure->copyPropertyTable();
 483     transition->m_isPinnedPropertyTable = true;
 484
 485     ASSERT(structure->anonymousSlotCount() == transition->anonymousSlotCount());
 486     return transition.release();
 487 }
 488
 489 PassRefPtr<Structure> Structure::toDictionaryTransition(Structure* structure, DictionaryKind kind)
 490 {
 491     ASSERT(!structure->isUncacheableDictionary());
 492
 493     RefPtr<Structure> transition = create(structure->m_prototype, structure->typeInfo(), structure->anonymousSlotCount());
 494     transition->m_dictionaryKind = kind;
 495     transition->m_propertyStorageCapacity = structure->m_propertyStorageCapacity;
 496     transition->m_hasGetterSetterProperties = structure->m_hasGetterSetterProperties;
 497     transition->m_hasNonEnumerableProperties = structure->m_hasNonEnumerableProperties;
 498     transition->m_specificFunctionThrashCount = structure->m_specificFunctionThrashCount;
 499
 500     structure->materializePropertyMapIfNecessary();
 501     transition->m_propertyTable = structure->copyPropertyTable();
 502     transition->m_isPinnedPropertyTable = true;
 503
 504     ASSERT(structure->anonymousSlotCount() == transition->anonymousSlotCount());
 505     return transition.release();
 506 }
 507
 508 PassRefPtr<Structure> Structure::toCacheableDictionaryTransition(Structure* structure)
 509 {
 510     return toDictionaryTransition(structure, CachedDictionaryKind);
 511 }
 512
 513 PassRefPtr<Structure> Structure::toUncacheableDictionaryTransition(Structure* structure)
 514 {
 515     return toDictionaryTransition(structure, UncachedDictionaryKind);
 516 }
 517
 518 PassRefPtr<Structure> Structure::flattenDictionaryStructure(JSObject* object)
 519 {
 520     ASSERT(isDictionary());
 521     if (isUncacheableDictionary()) {
 522         ASSERT(m_propertyTable);
 523         Vector<PropertyMapEntry*> sortedPropertyEntries(m_propertyTable->keyCount);
 524         PropertyMapEntry** p = sortedPropertyEntries.data();
 525         unsigned entryCount = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount;
 526         for (unsigned i = 1; i <= entryCount; i++) {
 527             if (m_propertyTable->entries()[i].key)
 528                 *p++ = &m_propertyTable->entries()[i];
 529         }
 530         size_t propertyCount = p - sortedPropertyEntries.data();
 531         qsort(sortedPropertyEntries.data(), propertyCount, sizeof(PropertyMapEntry*), comparePropertyMapEntryIndices);
 532         sortedPropertyEntries.resize(propertyCount);
 533
 534         // We now have the properties currently defined on this object
 535         // in the order that they are expected to be in, but we need to
 536         // reorder the storage, so we have to copy the current values out
 537         Vector<JSValue> values(propertyCount);
 538         unsigned anonymousSlotCount = m_anonymousSlotCount;
 539         for (unsigned i = 0; i < propertyCount; i++) {
 540             PropertyMapEntry* entry = sortedPropertyEntries[i];
 541             values[i] = object->getDirectOffset(entry->offset);
 542             // Update property table to have the new property offsets
 543             entry->offset = anonymousSlotCount + i;
 544             entry->index = i;
 545         }
 546
 547         // Copy the original property values into their final locations
 548         for (unsigned i = 0; i < propertyCount; i++)
 549             object->putDirectOffset(anonymousSlotCount + i, values[i]);
 550
 551         if (m_propertyTable->deletedOffsets) {
 552             delete m_propertyTable->deletedOffsets;
 553             m_propertyTable->deletedOffsets = 0;
 554         }
 555     }
 556
 557     m_dictionaryKind = NoneDictionaryKind;
 558     return this;
 559 }
 560
 561 size_t Structure::addPropertyWithoutTransition(const Identifier& propertyName, unsigned attributes, JSCell* specificValue)
 562 {
 563     ASSERT(!m_enumerationCache);
 564
 565     if (m_specificFunctionThrashCount == maxSpecificFunctionThrashCount)
 566         specificValue = 0;
 567
 568     materializePropertyMapIfNecessary();
 569
 570     m_isPinnedPropertyTable = true;
 571
 572     size_t offset = put(propertyName, attributes, specificValue);
 573     ASSERT(offset >= m_anonymousSlotCount);
 574     if (propertyStorageSize() > propertyStorageCapacity())
 575         growPropertyStorageCapacity();
 576     return offset;
 577 }
 578
 579 size_t Structure::removePropertyWithoutTransition(const Identifier& propertyName)
 580 {
 581     ASSERT(isUncacheableDictionary());
 582     ASSERT(!m_enumerationCache);
 583
 584     materializePropertyMapIfNecessary();
 585
 586     m_isPinnedPropertyTable = true;
 587     size_t offset = remove(propertyName);
 588     ASSERT(offset >= m_anonymousSlotCount);
 589     return offset;
 590 }
 591
 592 #if DUMP_PROPERTYMAP_STATS
 593
 594 static int numProbes;
 595 static int numCollisions;
 596 static int numRehashes;
 597 static int numRemoves;
 598
 599 struct PropertyMapStatisticsExitLogger {
 600     ~PropertyMapStatisticsExitLogger();
 601 };
 602
 603 static PropertyMapStatisticsExitLogger logger;
 604
 605 PropertyMapStatisticsExitLogger::~PropertyMapStatisticsExitLogger()
 606 {
 607     printf("\nJSC::PropertyMap statistics\n\n");
 608     printf("%d probes\n", numProbes);
 609     printf("%d collisions (%.1f%%)\n", numCollisions, 100.0 * numCollisions / numProbes);
 610     printf("%d rehashes\n", numRehashes);
 611     printf("%d removes\n", numRemoves);
 612 }
 613
 614 #endif
 615
 616 static const unsigned deletedSentinelIndex = 1;
 617
 618 #if !DO_PROPERTYMAP_CONSTENCY_CHECK
 619
 620 inline void Structure::checkConsistency()
 621 {
 622 }
 623
 624 #endif
 625
 626 PropertyMapHashTable* Structure::copyPropertyTable()
 627 {
 628     if (!m_propertyTable)
 629         return 0;
 630
 631     size_t tableSize = PropertyMapHashTable::allocationSize(m_propertyTable->size);
 632     PropertyMapHashTable* newTable = static_cast<PropertyMapHashTable*>(fastMalloc(tableSize));
 633     memcpy(newTable, m_propertyTable, tableSize);
 634
 635     unsigned entryCount = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount;
 636     for (unsigned i = 1; i <= entryCount; ++i) {
 637         if (UString::Rep* key = newTable->entries()[i].key)
 638             key->ref();
 639     }
 640
 641     // Copy the deletedOffsets vector.
 642     if (m_propertyTable->deletedOffsets)
 643         newTable->deletedOffsets = new Vector<unsigned>(*m_propertyTable->deletedOffsets);
 644
 645     return newTable;
 646 }
 647
 648 size_t Structure::get(const UString::Rep* rep, unsigned& attributes, JSCell*& specificValue)
 649 {
 650     materializePropertyMapIfNecessary();
 651     if (!m_propertyTable)
 652         return notFound;
 653
 654     unsigned i = rep->existingHash();
 655
 656 #if DUMP_PROPERTYMAP_STATS
 657     ++numProbes;
 658 #endif
 659
 660     unsigned entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
 661     if (entryIndex == emptyEntryIndex)
 662         return notFound;
 663
 664     if (rep == m_propertyTable->entries()[entryIndex - 1].key) {
 665         attributes = m_propertyTable->entries()[entryIndex - 1].attributes;
 666         specificValue = m_propertyTable->entries()[entryIndex - 1].specificValue;
 667         ASSERT(m_propertyTable->entries()[entryIndex - 1].offset >= m_anonymousSlotCount);
 668         return m_propertyTable->entries()[entryIndex - 1].offset;
 669     }
 670
 671 #if DUMP_PROPERTYMAP_STATS
 672     ++numCollisions;
 673 #endif
 674
 675     unsigned k = 1 | doubleHash(rep->existingHash());
 676
 677     while (1) {
 678         i += k;
 679
 680 #if DUMP_PROPERTYMAP_STATS
 681         ++numRehashes;
 682 #endif
 683
 684         entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
 685         if (entryIndex == emptyEntryIndex)
 686             return notFound;
 687
 688         if (rep == m_propertyTable->entries()[entryIndex - 1].key) {
 689             attributes = m_propertyTable->entries()[entryIndex - 1].attributes;
 690             specificValue = m_propertyTable->entries()[entryIndex - 1].specificValue;
 691             ASSERT(m_propertyTable->entries()[entryIndex - 1].offset >= m_anonymousSlotCount);
 692             return m_propertyTable->entries()[entryIndex - 1].offset;
 693         }
 694     }
 695 }
 696
 697 bool Structure::despecifyFunction(const Identifier& propertyName)
 698 {
 699     ASSERT(!propertyName.isNull());
 700
 701     materializePropertyMapIfNecessary();
 702     if (!m_propertyTable)
 703         return false;
 704
 705     UString::Rep* rep = propertyName._ustring.rep();
 706
 707     unsigned i = rep->existingHash();
 708
 709 #if DUMP_PROPERTYMAP_STATS
 710     ++numProbes;
 711 #endif
 712
 713     unsigned entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
 714     if (entryIndex == emptyEntryIndex)
 715         return false;
 716
 717     if (rep == m_propertyTable->entries()[entryIndex - 1].key) {
 718         ASSERT(m_propertyTable->entries()[entryIndex - 1].specificValue);
 719         m_propertyTable->entries()[entryIndex - 1].specificValue = 0;
 720         return true;
 721     }
 722
 723 #if DUMP_PROPERTYMAP_STATS
 724     ++numCollisions;
 725 #endif
 726
 727     unsigned k = 1 | doubleHash(rep->existingHash());
 728
 729     while (1) {
 730         i += k;
 731
 732 #if DUMP_PROPERTYMAP_STATS
 733         ++numRehashes;
 734 #endif
 735
 736         entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
 737         if (entryIndex == emptyEntryIndex)
 738             return false;
 739
 740         if (rep == m_propertyTable->entries()[entryIndex - 1].key) {
 741             ASSERT(m_propertyTable->entries()[entryIndex - 1].specificValue);
 742             m_propertyTable->entries()[entryIndex - 1].specificValue = 0;
 743             return true;
 744         }
 745     }
 746 }
 747
 748 void Structure::despecifyAllFunctions()
 749 {
 750     materializePropertyMapIfNecessary();
 751     if (!m_propertyTable)
 752         return;
 753
 754     unsigned entryCount = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount;
 755     for (unsigned i = 1; i <= entryCount; ++i)
 756         m_propertyTable->entries()[i].specificValue = 0;
 757 }
 758
 759 size_t Structure::put(const Identifier& propertyName, unsigned attributes, JSCell* specificValue)
 760 {
 761     ASSERT(!propertyName.isNull());
 762     ASSERT(get(propertyName) == notFound);
 763
 764     checkConsistency();
 765
 766     if (attributes & DontEnum)
 767         m_hasNonEnumerableProperties = true;
 768
 769     UString::Rep* rep = propertyName._ustring.rep();
 770
 771     if (!m_propertyTable)
 772         createPropertyMapHashTable();
 773
 774     // FIXME: Consider a fast case for tables with no deleted sentinels.
 775
 776     unsigned i = rep->existingHash();
 777     unsigned k = 0;
 778     bool foundDeletedElement = false;
 779     unsigned deletedElementIndex = 0; // initialize to make the compiler happy
 780
 781 #if DUMP_PROPERTYMAP_STATS
 782     ++numProbes;
 783 #endif
 784
 785     while (1) {
 786         unsigned entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
 787         if (entryIndex == emptyEntryIndex)
 788             break;
 789
 790         if (entryIndex == deletedSentinelIndex) {
 791             // If we find a deleted-element sentinel, remember it for use later.
 792             if (!foundDeletedElement) {
 793                 foundDeletedElement = true;
 794                 deletedElementIndex = i;
 795             }
 796         }
 797
 798         if (k == 0) {
 799             k = 1 | doubleHash(rep->existingHash());
 800 #if DUMP_PROPERTYMAP_STATS
 801             ++numCollisions;
 802 #endif
 803         }
 804
 805         i += k;
 806
 807 #if DUMP_PROPERTYMAP_STATS
 808         ++numRehashes;
 809 #endif
 810     }
 811
 812     // Figure out which entry to use.
 813     unsigned entryIndex = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount + 2;
 814     if (foundDeletedElement) {
 815         i = deletedElementIndex;
 816         --m_propertyTable->deletedSentinelCount;
 817
 818         // Since we're not making the table bigger, we can't use the entry one past
 819         // the end that we were planning on using, so search backwards for the empty
 820         // slot that we can use. We know it will be there because we did at least one
 821         // deletion in the past that left an entry empty.
 822         while (m_propertyTable->entries()[--entryIndex - 1].key) { }
 823     }
 824
 825     // Create a new hash table entry.
 826     m_propertyTable->entryIndices[i & m_propertyTable->sizeMask] = entryIndex;
 827
 828     // Create a new hash table entry.
 829     rep->ref();
 830     m_propertyTable->entries()[entryIndex - 1].key = rep;
 831     m_propertyTable->entries()[entryIndex - 1].attributes = attributes;
 832     m_propertyTable->entries()[entryIndex - 1].specificValue = specificValue;
 833     m_propertyTable->entries()[entryIndex - 1].index = ++m_propertyTable->lastIndexUsed;
 834
 835     unsigned newOffset;
 836     if (m_propertyTable->deletedOffsets && !m_propertyTable->deletedOffsets->isEmpty()) {
 837         newOffset = m_propertyTable->deletedOffsets->last();
 838         m_propertyTable->deletedOffsets->removeLast();
 839     } else
 840         newOffset = m_propertyTable->keyCount + m_anonymousSlotCount;
 841     m_propertyTable->entries()[entryIndex - 1].offset = newOffset;
 842
 843     ASSERT(newOffset >= m_anonymousSlotCount);
 844     ++m_propertyTable->keyCount;
 845
 846     if ((m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount) * 2 >= m_propertyTable->size)
 847         expandPropertyMapHashTable();
 848
 849     checkConsistency();
 850     return newOffset;
 851 }
 852
 853 bool Structure::hasTransition(UString::Rep* rep, unsigned attributes)
 854 {
 855     return table.hasTransition(make_pair(rep, attributes));
 856 }
 857
 858 size_t Structure::remove(const Identifier& propertyName)
 859 {
 860     ASSERT(!propertyName.isNull());
 861
 862     checkConsistency();
 863
 864     UString::Rep* rep = propertyName._ustring.rep();
 865
 866     if (!m_propertyTable)
 867         return notFound;
 868
 869 #if DUMP_PROPERTYMAP_STATS
 870     ++numProbes;
 871     ++numRemoves;
 872 #endif
 873
 874     // Find the thing to remove.
 875     unsigned i = rep->existingHash();
 876     unsigned k = 0;
 877     unsigned entryIndex;
 878     UString::Rep* key = 0;
 879     while (1) {
 880         entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
 881         if (entryIndex == emptyEntryIndex)
 882             return notFound;
 883
 884         key = m_propertyTable->entries()[entryIndex - 1].key;
 885         if (rep == key)
 886             break;
 887
 888         if (k == 0) {
 889             k = 1 | doubleHash(rep->existingHash());
 890 #if DUMP_PROPERTYMAP_STATS
 891             ++numCollisions;
 892 #endif
 893         }
 894
 895         i += k;
 896
 897 #if DUMP_PROPERTYMAP_STATS
 898         ++numRehashes;
 899 #endif
 900     }
 901
 902     // Replace this one element with the deleted sentinel. Also clear out
 903     // the entry so we can iterate all the entries as needed.
 904     m_propertyTable->entryIndices[i & m_propertyTable->sizeMask] = deletedSentinelIndex;
 905
 906     size_t offset = m_propertyTable->entries()[entryIndex - 1].offset;
 907     ASSERT(offset >= m_anonymousSlotCount);
 908
 909     key->deref();
 910     m_propertyTable->entries()[entryIndex - 1].key = 0;
 911     m_propertyTable->entries()[entryIndex - 1].attributes = 0;
 912     m_propertyTable->entries()[entryIndex - 1].specificValue = 0;
 913     m_propertyTable->entries()[entryIndex - 1].offset = 0;
 914
 915     if (!m_propertyTable->deletedOffsets)
 916         m_propertyTable->deletedOffsets = new Vector<unsigned>;
 917     m_propertyTable->deletedOffsets->append(offset);
 918
 919     ASSERT(m_propertyTable->keyCount >= 1);
 920     --m_propertyTable->keyCount;
 921     ++m_propertyTable->deletedSentinelCount;
 922
 923     if (m_propertyTable->deletedSentinelCount * 4 >= m_propertyTable->size)
 924         rehashPropertyMapHashTable();
 925
 926     checkConsistency();
 927     return offset;
 928 }
 929
 930 void Structure::insertIntoPropertyMapHashTable(const PropertyMapEntry& entry)
 931 {
 932     ASSERT(m_propertyTable);
 933     ASSERT(entry.offset >= m_anonymousSlotCount);
 934     unsigned i = entry.key->existingHash();
 935     unsigned k = 0;
 936
 937 #if DUMP_PROPERTYMAP_STATS
 938     ++numProbes;
 939 #endif
 940
 941     while (1) {
 942         unsigned entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
 943         if (entryIndex == emptyEntryIndex)
 944             break;
 945
 946         if (k == 0) {
 947             k = 1 | doubleHash(entry.key->existingHash());
 948 #if DUMP_PROPERTYMAP_STATS
 949             ++numCollisions;
 950 #endif
 951         }
 952
 953         i += k;
 954
 955 #if DUMP_PROPERTYMAP_STATS
 956         ++numRehashes;
 957 #endif
 958     }
 959
 960     unsigned entryIndex = m_propertyTable->keyCount + 2;
 961     m_propertyTable->entryIndices[i & m_propertyTable->sizeMask] = entryIndex;
 962     m_propertyTable->entries()[entryIndex - 1] = entry;
 963
 964     ++m_propertyTable->keyCount;
 965 }
 966
 967 void Structure::createPropertyMapHashTable()
 968 {
 969     ASSERT(sizeForKeyCount(7) == newTableSize);
 970     createPropertyMapHashTable(newTableSize);
 971 }
 972
 973 void Structure::createPropertyMapHashTable(unsigned newTableSize)
 974 {
 975     ASSERT(!m_propertyTable);
 976     ASSERT(isPowerOf2(newTableSize));
 977
 978     checkConsistency();
 979
 980     m_propertyTable = static_cast<PropertyMapHashTable*>(fastZeroedMalloc(PropertyMapHashTable::allocationSize(newTableSize)));
 981     m_propertyTable->size = newTableSize;
 982     m_propertyTable->sizeMask = newTableSize - 1;
 983
 984     checkConsistency();
 985 }
 986
 987 void Structure::expandPropertyMapHashTable()
 988 {
 989     ASSERT(m_propertyTable);
 990     rehashPropertyMapHashTable(m_propertyTable->size * 2);
 991 }
 992
 993 void Structure::rehashPropertyMapHashTable()
 994 {
 995     ASSERT(m_propertyTable);
 996     ASSERT(m_propertyTable->size);
 997     rehashPropertyMapHashTable(m_propertyTable->size);
 998 }
 999
1000 void Structure::rehashPropertyMapHashTable(unsigned newTableSize)
1001 {
1002     ASSERT(m_propertyTable);
1003     ASSERT(isPowerOf2(newTableSize));
1004
1005     checkConsistency();
1006
1007     PropertyMapHashTable* oldTable = m_propertyTable;
1008
1009     m_propertyTable = static_cast<PropertyMapHashTable*>(fastZeroedMalloc(PropertyMapHashTable::allocationSize(newTableSize)));
1010     m_propertyTable->size = newTableSize;
1011     m_propertyTable->sizeMask = newTableSize - 1;
1012
1013     unsigned lastIndexUsed = 0;
1014     unsigned entryCount = oldTable->keyCount + oldTable->deletedSentinelCount;
1015     for (unsigned i = 1; i <= entryCount; ++i) {
1016         if (oldTable->entries()[i].key) {
1017             lastIndexUsed = max(oldTable->entries()[i].index, lastIndexUsed);
1018             insertIntoPropertyMapHashTable(oldTable->entries()[i]);
1019         }
1020     }
1021     m_propertyTable->lastIndexUsed = lastIndexUsed;
1022     m_propertyTable->deletedOffsets = oldTable->deletedOffsets;
1023
1024     fastFree(oldTable);
1025
1026     checkConsistency();
1027 }
1028
1029 int comparePropertyMapEntryIndices(const void* a, const void* b)
1030 {
1031     unsigned ia = static_cast<PropertyMapEntry* const*>(a)[0]->index;
1032     unsigned ib = static_cast<PropertyMapEntry* const*>(b)[0]->index;
1033     if (ia < ib)
1034         return -1;
1035     if (ia > ib)
1036         return +1;
1037     return 0;
1038 }
1039
1040 void Structure::getPropertyNames(PropertyNameArray& propertyNames, EnumerationMode mode)
1041 {
1042     materializePropertyMapIfNecessary();
1043     if (!m_propertyTable)
1044         return;
1045
1046     if (m_propertyTable->keyCount < tinyMapThreshold) {
1047         PropertyMapEntry* a[tinyMapThreshold];
1048         int i = 0;
1049         unsigned entryCount = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount;
1050         for (unsigned k = 1; k <= entryCount; k++) {
1051             ASSERT(m_hasNonEnumerableProperties || !(m_propertyTable->entries()[k].attributes & DontEnum));
1052             if (m_propertyTable->entries()[k].key && (!(m_propertyTable->entries()[k].attributes & DontEnum) || (mode == IncludeDontEnumProperties))) {
1053                 PropertyMapEntry* value = &m_propertyTable->entries()[k];
1054                 int j;
1055                 for (j = i - 1; j >= 0 && a[j]->index > value->index; --j)
1056                     a[j + 1] = a[j];
1057                 a[j + 1] = value;
1058                 ++i;
1059             }
1060         }
1061         if (!propertyNames.size()) {
1062             for (int k = 0; k < i; ++k)
1063                 propertyNames.addKnownUnique(a[k]->key);
1064         } else {
1065             for (int k = 0; k < i; ++k)
1066                 propertyNames.add(a[k]->key);
1067         }
1068
1069         return;
1070     }
1071
1072     // Allocate a buffer to use to sort the keys.
1073     Vector<PropertyMapEntry*, smallMapThreshold> sortedEnumerables(m_propertyTable->keyCount);
1074
1075     // Get pointers to the enumerable entries in the buffer.
1076     PropertyMapEntry** p = sortedEnumerables.data();
1077     unsigned entryCount = m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount;
1078     for (unsigned i = 1; i <= entryCount; i++) {
1079         if (m_propertyTable->entries()[i].key && (!(m_propertyTable->entries()[i].attributes & DontEnum) || (mode == IncludeDontEnumProperties)))
1080             *p++ = &m_propertyTable->entries()[i];
1081     }
1082
1083     size_t enumerableCount = p - sortedEnumerables.data();
1084     // Sort the entries by index.
1085     qsort(sortedEnumerables.data(), enumerableCount, sizeof(PropertyMapEntry*), comparePropertyMapEntryIndices);
1086     sortedEnumerables.resize(enumerableCount);
1087
1088     // Put the keys of the sorted entries into the list.
1089     if (!propertyNames.size()) {
1090         for (size_t i = 0; i < sortedEnumerables.size(); ++i)
1091             propertyNames.addKnownUnique(sortedEnumerables[i]->key);
1092     } else {
1093         for (size_t i = 0; i < sortedEnumerables.size(); ++i)
1094             propertyNames.add(sortedEnumerables[i]->key);
1095     }
1096 }
1097
1098 #if DO_PROPERTYMAP_CONSTENCY_CHECK
1099
1100 void Structure::checkConsistency()
1101 {
1102     if (!m_propertyTable)
1103         return;
1104
1105     ASSERT(m_propertyTable->size >= newTableSize);
1106     ASSERT(m_propertyTable->sizeMask);
1107     ASSERT(m_propertyTable->size == m_propertyTable->sizeMask + 1);
1108     ASSERT(!(m_propertyTable->size & m_propertyTable->sizeMask));
1109
1110     ASSERT(m_propertyTable->keyCount <= m_propertyTable->size / 2);
1111     ASSERT(m_propertyTable->deletedSentinelCount <= m_propertyTable->size / 4);
1112
1113     ASSERT(m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount <= m_propertyTable->size / 2);
1114
1115     unsigned indexCount = 0;
1116     unsigned deletedIndexCount = 0;
1117     for (unsigned a = 0; a != m_propertyTable->size; ++a) {
1118         unsigned entryIndex = m_propertyTable->entryIndices[a];
1119         if (entryIndex == emptyEntryIndex)
1120             continue;
1121         if (entryIndex == deletedSentinelIndex) {
1122             ++deletedIndexCount;
1123             continue;
1124         }
1125         ASSERT(entryIndex > deletedSentinelIndex);
1126         ASSERT(entryIndex - 1 <= m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount);
1127         ++indexCount;
1128
1129         for (unsigned b = a + 1; b != m_propertyTable->size; ++b)
1130             ASSERT(m_propertyTable->entryIndices[b] != entryIndex);
1131     }
1132     ASSERT(indexCount == m_propertyTable->keyCount);
1133     ASSERT(deletedIndexCount == m_propertyTable->deletedSentinelCount);
1134
1135     ASSERT(m_propertyTable->entries()[0].key == 0);
1136
1137     unsigned nonEmptyEntryCount = 0;
1138     for (unsigned c = 1; c <= m_propertyTable->keyCount + m_propertyTable->deletedSentinelCount; ++c) {
1139         ASSERT(m_hasNonEnumerableProperties || !(m_propertyTable->entries()[c].attributes & DontEnum));
1140         UString::Rep* rep = m_propertyTable->entries()[c].key;
1141         ASSERT(m_propertyTable->entries()[c].offset >= m_anonymousSlotCount);
1142         if (!rep)
1143             continue;
1144         ++nonEmptyEntryCount;
1145         unsigned i = rep->existingHash();
1146         unsigned k = 0;
1147         unsigned entryIndex;
1148         while (1) {
1149             entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
1150             ASSERT(entryIndex != emptyEntryIndex);
1151             if (rep == m_propertyTable->entries()[entryIndex - 1].key)
1152                 break;
1153             if (k == 0)
1154                 k = 1 | doubleHash(rep->existingHash());
1155             i += k;
1156         }
1157         ASSERT(entryIndex == c + 1);
1158     }
1159
1160     ASSERT(nonEmptyEntryCount == m_propertyTable->keyCount);
1161 }
1162
1163 #endif // DO_PROPERTYMAP_CONSTENCY_CHECK
1164
1165 } // namespace JSC