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 #include <wtf/Threading.h>
  38
  39 #define DUMP_STRUCTURE_ID_STATISTICS 0
  40
  41 #ifndef NDEBUG
  42 #define DO_PROPERTYMAP_CONSTENCY_CHECK 0
  43 #else
  44 #define DO_PROPERTYMAP_CONSTENCY_CHECK 0
  45 #endif
  46
  47 using namespace std;
  48 using namespace WTF;
  49
  50 #if DUMP_PROPERTYMAP_STATS
  51
  52 int numProbes;
  53 int numCollisions;
  54 int numRehashes;
  55 int numRemoves;
  56
  57 #endif
  58
  59 namespace JSC {
  60
  61 #if DUMP_STRUCTURE_ID_STATISTICS
  62 static HashSet<Structure*>& liveStructureSet = *(new HashSet<Structure*>);
  63 #endif
  64
  65 bool StructureTransitionTable::contains(StringImpl* rep, unsigned attributes) const
  66 {
  67     if (isUsingSingleSlot()) {
  68         Structure* transition = singleTransition();
  69         return transition && transition->m_nameInPrevious == rep && transition->m_attributesInPrevious == attributes;
  70     }
  71     return map()->contains(make_pair(rep, attributes));
  72 }
  73
  74 inline Structure* StructureTransitionTable::get(StringImpl* rep, unsigned attributes) const
  75 {
  76     if (isUsingSingleSlot()) {
  77         Structure* transition = singleTransition();
  78         return (transition && transition->m_nameInPrevious == rep && transition->m_attributesInPrevious == attributes) ? transition : 0;
  79     }
  80     return map()->get(make_pair(rep, attributes));
  81 }
  82
  83 inline void StructureTransitionTable::add(JSGlobalData& globalData, Structure* structure)
  84 {
  85     if (isUsingSingleSlot()) {
  86         Structure* existingTransition = singleTransition();
  87
  88         // This handles the first transition being added.
  89         if (!existingTransition) {
  90             setSingleTransition(globalData, structure);
  91             return;
  92         }
  93
  94         // This handles the second transition being added
  95         // (or the first transition being despecified!)
  96         setMap(new TransitionMap());
  97         add(globalData, existingTransition);
  98     }
  99
 100     // Add the structure to the map.
 101
 102     // Newer versions of the STL have an std::make_pair function that takes rvalue references.
 103     // 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.
 104     // See https://bugs.webkit.org/show_bug.cgi?id=59261 for more details
 105     TransitionMap::AddResult result = map()->add(globalData, make_pair(structure->m_nameInPrevious, +structure->m_attributesInPrevious), structure);
 106     if (!result.isNewEntry) {
 107         // There already is an entry! - we should only hit this when despecifying.
 108         ASSERT(result.iterator.get().second->m_specificValueInPrevious);
 109         ASSERT(!structure->m_specificValueInPrevious);
 110         map()->set(globalData, result.iterator.get().first, structure);
 111     }
 112 }
 113
 114 void Structure::dumpStatistics()
 115 {
 116 #if DUMP_STRUCTURE_ID_STATISTICS
 117     unsigned numberLeaf = 0;
 118     unsigned numberUsingSingleSlot = 0;
 119     unsigned numberSingletons = 0;
 120     unsigned numberWithPropertyMaps = 0;
 121     unsigned totalPropertyMapsSize = 0;
 122
 123     HashSet<Structure*>::const_iterator end = liveStructureSet.end();
 124     for (HashSet<Structure*>::const_iterator it = liveStructureSet.begin(); it != end; ++it) {
 125         Structure* structure = *it;
 126
 127         switch (structure->m_transitionTable.size()) {
 128             case 0:
 129                 ++numberLeaf;
 130                if (!structure->m_previous)
 131                     ++numberSingletons;
 132                 break;
 133
 134             case 1:
 135                 ++numberUsingSingleSlot;
 136                 break;
 137         }
 138
 139         if (structure->m_propertyTable) {
 140             ++numberWithPropertyMaps;
 141             totalPropertyMapsSize += structure->m_propertyTable->sizeInMemory();
 142         }
 143     }
 144
 145     dataLog("Number of live Structures: %d\n", liveStructureSet.size());
 146     dataLog("Number of Structures using the single item optimization for transition map: %d\n", numberUsingSingleSlot);
 147     dataLog("Number of Structures that are leaf nodes: %d\n", numberLeaf);
 148     dataLog("Number of Structures that singletons: %d\n", numberSingletons);
 149     dataLog("Number of Structures with PropertyMaps: %d\n", numberWithPropertyMaps);
 150
 151     dataLog("Size of a single Structures: %d\n", static_cast<unsigned>(sizeof(Structure)));
 152     dataLog("Size of sum of all property maps: %d\n", totalPropertyMapsSize);
 153     dataLog("Size of average of all property maps: %f\n", static_cast<double>(totalPropertyMapsSize) / static_cast<double>(liveStructureSet.size()));
 154 #else
 155     dataLog("Dumping Structure statistics is not enabled.\n");
 156 #endif
 157 }
 158
 159 Structure::Structure(JSGlobalData& globalData, JSGlobalObject* globalObject, JSValue prototype, const TypeInfo& typeInfo, const ClassInfo* classInfo)
 160     : JSCell(globalData, globalData.structureStructure.get())
 161     , m_typeInfo(typeInfo)
 162     , m_globalObject(globalData, this, globalObject, WriteBarrier<JSGlobalObject>::MayBeNull)
 163     , m_prototype(globalData, this, prototype)
 164     , m_classInfo(classInfo)
 165     , m_propertyStorageCapacity(typeInfo.isFinalObject() ? JSFinalObject_inlineStorageCapacity : JSNonFinalObject_inlineStorageCapacity)
 166     , m_offset(noOffset)
 167     , m_dictionaryKind(NoneDictionaryKind)
 168     , m_isPinnedPropertyTable(false)
 169     , m_hasGetterSetterProperties(false)
 170     , m_hasReadOnlyOrGetterSetterPropertiesExcludingProto(false)
 171     , m_hasNonEnumerableProperties(false)
 172     , m_attributesInPrevious(0)
 173     , m_specificFunctionThrashCount(0)
 174     , m_preventExtensions(false)
 175     , m_didTransition(false)
 176     , m_staticFunctionReified(false)
 177 {
 178 }
 179
 180 const ClassInfo Structure::s_info = { "Structure", 0, 0, 0, CREATE_METHOD_TABLE(Structure) };
 181
 182 Structure::Structure(JSGlobalData& globalData)
 183     : JSCell(CreatingEarlyCell)
 184     , m_typeInfo(CompoundType, OverridesVisitChildren)
 185     , m_prototype(globalData, this, jsNull())
 186     , m_classInfo(&s_info)
 187     , m_propertyStorageCapacity(0)
 188     , m_offset(noOffset)
 189     , m_dictionaryKind(NoneDictionaryKind)
 190     , m_isPinnedPropertyTable(false)
 191     , m_hasGetterSetterProperties(false)
 192     , m_hasReadOnlyOrGetterSetterPropertiesExcludingProto(false)
 193     , m_hasNonEnumerableProperties(false)
 194     , m_attributesInPrevious(0)
 195     , m_specificFunctionThrashCount(0)
 196     , m_preventExtensions(false)
 197     , m_didTransition(false)
 198     , m_staticFunctionReified(false)
 199 {
 200 }
 201
 202 Structure::Structure(JSGlobalData& globalData, const Structure* previous)
 203     : JSCell(globalData, globalData.structureStructure.get())
 204     , m_typeInfo(previous->typeInfo())
 205     , m_prototype(globalData, this, previous->storedPrototype())
 206     , m_classInfo(previous->m_classInfo)
 207     , m_propertyStorageCapacity(previous->m_propertyStorageCapacity)
 208     , m_offset(noOffset)
 209     , m_dictionaryKind(previous->m_dictionaryKind)
 210     , m_isPinnedPropertyTable(false)
 211     , m_hasGetterSetterProperties(previous->m_hasGetterSetterProperties)
 212     , m_hasReadOnlyOrGetterSetterPropertiesExcludingProto(previous->m_hasReadOnlyOrGetterSetterPropertiesExcludingProto)
 213     , m_hasNonEnumerableProperties(previous->m_hasNonEnumerableProperties)
 214     , m_attributesInPrevious(0)
 215     , m_specificFunctionThrashCount(previous->m_specificFunctionThrashCount)
 216     , m_preventExtensions(previous->m_preventExtensions)
 217     , m_didTransition(true)
 218     , m_staticFunctionReified(previous->m_staticFunctionReified)
 219 {
 220     if (previous->m_globalObject)
 221         m_globalObject.set(globalData, this, previous->m_globalObject.get());
 222 }
 223
 224 void Structure::destroy(JSCell* cell)
 225 {
 226     jsCast<Structure*>(cell)->Structure::~Structure();
 227 }
 228
 229 void Structure::materializePropertyMap(JSGlobalData& globalData)
 230 {
 231     ASSERT(structure()->classInfo() == &s_info);
 232     ASSERT(!m_propertyTable);
 233
 234     Vector<Structure*, 8> structures;
 235     structures.append(this);
 236
 237     Structure* structure = this;
 238
 239     // Search for the last Structure with a property table.
 240     while ((structure = structure->previousID())) {
 241         if (structure->m_isPinnedPropertyTable) {
 242             ASSERT(structure->m_propertyTable);
 243             ASSERT(!structure->m_previous);
 244
 245             m_propertyTable = structure->m_propertyTable->copy(globalData, 0, m_offset + 1);
 246             break;
 247         }
 248
 249         structures.append(structure);
 250     }
 251
 252     if (!m_propertyTable)
 253         createPropertyMap(m_offset + 1);
 254
 255     for (ptrdiff_t i = structures.size() - 2; i >= 0; --i) {
 256         structure = structures[i];
 257         PropertyMapEntry entry(globalData, this, structure->m_nameInPrevious.get(), structure->m_offset, structure->m_attributesInPrevious, structure->m_specificValueInPrevious.get());
 258         m_propertyTable->add(entry);
 259     }
 260 }
 261
 262 void Structure::growPropertyStorageCapacity()
 263 {
 264     if (isUsingInlineStorage())
 265         m_propertyStorageCapacity = JSObject::baseExternalStorageCapacity;
 266     else
 267         m_propertyStorageCapacity *= 2;
 268 }
 269
 270 size_t Structure::suggestedNewPropertyStorageSize()
 271 {
 272     if (isUsingInlineStorage())
 273         return JSObject::baseExternalStorageCapacity;
 274     return m_propertyStorageCapacity * 2;
 275 }
 276
 277 void Structure::despecifyDictionaryFunction(JSGlobalData& globalData, const Identifier& propertyName)
 278 {
 279     StringImpl* rep = propertyName.impl();
 280
 281     materializePropertyMapIfNecessary(globalData);
 282
 283     ASSERT(isDictionary());
 284     ASSERT(m_propertyTable);
 285
 286     PropertyMapEntry* entry = m_propertyTable->find(rep).first;
 287     ASSERT(entry);
 288     entry->specificValue.clear();
 289 }
 290
 291 Structure* Structure::addPropertyTransitionToExistingStructure(Structure* structure, const Identifier& propertyName, unsigned attributes, JSCell* specificValue, size_t& offset)
 292 {
 293     ASSERT(!structure->isDictionary());
 294     ASSERT(structure->isObject());
 295
 296     if (Structure* existingTransition = structure->m_transitionTable.get(propertyName.impl(), attributes)) {
 297         JSCell* specificValueInPrevious = existingTransition->m_specificValueInPrevious.get();
 298         if (specificValueInPrevious && specificValueInPrevious != specificValue)
 299             return 0;
 300         ASSERT(existingTransition->m_offset != noOffset);
 301         offset = existingTransition->m_offset;
 302         return existingTransition;
 303     }
 304
 305     return 0;
 306 }
 307
 308 Structure* Structure::addPropertyTransition(JSGlobalData& globalData, Structure* structure, const Identifier& propertyName, unsigned attributes, JSCell* specificValue, size_t& offset)
 309 {
 310     // If we have a specific function, we may have got to this point if there is
 311     // already a transition with the correct property name and attributes, but
 312     // specialized to a different function.  In this case we just want to give up
 313     // and despecialize the transition.
 314     // In this case we clear the value of specificFunction which will result
 315     // in us adding a non-specific transition, and any subsequent lookup in
 316     // Structure::addPropertyTransitionToExistingStructure will just use that.
 317     if (specificValue && structure->m_transitionTable.contains(propertyName.impl(), attributes))
 318         specificValue = 0;
 319
 320     ASSERT(!structure->isDictionary());
 321     ASSERT(structure->isObject());
 322     ASSERT(!Structure::addPropertyTransitionToExistingStructure(structure, propertyName, attributes, specificValue, offset));
 323
 324     if (structure->m_specificFunctionThrashCount == maxSpecificFunctionThrashCount)
 325         specificValue = 0;
 326
 327     if (structure->transitionCount() > s_maxTransitionLength) {
 328         Structure* transition = toCacheableDictionaryTransition(globalData, structure);
 329         ASSERT(structure != transition);
 330         offset = transition->putSpecificValue(globalData, propertyName, attributes, specificValue);
 331         if (transition->propertyStorageSize() > transition->propertyStorageCapacity())
 332             transition->growPropertyStorageCapacity();
 333         return transition;
 334     }
 335
 336     Structure* transition = create(globalData, structure);
 337
 338     transition->m_cachedPrototypeChain.setMayBeNull(globalData, transition, structure->m_cachedPrototypeChain.get());
 339     transition->m_previous.set(globalData, transition, structure);
 340     transition->m_nameInPrevious = propertyName.impl();
 341     transition->m_attributesInPrevious = attributes;
 342     transition->m_specificValueInPrevious.setMayBeNull(globalData, transition, specificValue);
 343
 344     if (structure->m_propertyTable) {
 345         if (structure->m_isPinnedPropertyTable)
 346             transition->m_propertyTable = structure->m_propertyTable->copy(globalData, transition, structure->m_propertyTable->size() + 1);
 347         else
 348             transition->m_propertyTable = structure->m_propertyTable.release();
 349     } else {
 350         if (structure->m_previous)
 351             transition->materializePropertyMap(globalData);
 352         else
 353             transition->createPropertyMap();
 354     }
 355
 356     offset = transition->putSpecificValue(globalData, propertyName, attributes, specificValue);
 357     if (transition->propertyStorageSize() > transition->propertyStorageCapacity())
 358         transition->growPropertyStorageCapacity();
 359
 360     transition->m_offset = offset;
 361     structure->m_transitionTable.add(globalData, transition);
 362     return transition;
 363 }
 364
 365 Structure* Structure::removePropertyTransition(JSGlobalData& globalData, Structure* structure, const Identifier& propertyName, size_t& offset)
 366 {
 367     ASSERT(!structure->isUncacheableDictionary());
 368
 369     Structure* transition = toUncacheableDictionaryTransition(globalData, structure);
 370
 371     offset = transition->remove(propertyName);
 372
 373     return transition;
 374 }
 375
 376 Structure* Structure::changePrototypeTransition(JSGlobalData& globalData, Structure* structure, JSValue prototype)
 377 {
 378     Structure* transition = create(globalData, structure);
 379
 380     transition->m_prototype.set(globalData, transition, prototype);
 381
 382     // Don't set m_offset, as one can not transition to this.
 383
 384     structure->materializePropertyMapIfNecessary(globalData);
 385     transition->m_propertyTable = structure->copyPropertyTableForPinning(globalData, transition);
 386     transition->pin();
 387
 388     return transition;
 389 }
 390
 391 Structure* Structure::despecifyFunctionTransition(JSGlobalData& globalData, Structure* structure, const Identifier& replaceFunction)
 392 {
 393     ASSERT(structure->m_specificFunctionThrashCount < maxSpecificFunctionThrashCount);
 394     Structure* transition = create(globalData, structure);
 395
 396     ++transition->m_specificFunctionThrashCount;
 397
 398     // Don't set m_offset, as one can not transition to this.
 399
 400     structure->materializePropertyMapIfNecessary(globalData);
 401     transition->m_propertyTable = structure->copyPropertyTableForPinning(globalData, transition);
 402     transition->pin();
 403
 404     if (transition->m_specificFunctionThrashCount == maxSpecificFunctionThrashCount)
 405         transition->despecifyAllFunctions(globalData);
 406     else {
 407         bool removed = transition->despecifyFunction(globalData, replaceFunction);
 408         ASSERT_UNUSED(removed, removed);
 409     }
 410
 411     return transition;
 412 }
 413
 414 Structure* Structure::attributeChangeTransition(JSGlobalData& globalData, Structure* structure, const Identifier& propertyName, unsigned attributes)
 415 {
 416     if (!structure->isUncacheableDictionary()) {
 417         Structure* transition = create(globalData, structure);
 418
 419         // Don't set m_offset, as one can not transition to this.
 420
 421         structure->materializePropertyMapIfNecessary(globalData);
 422         transition->m_propertyTable = structure->copyPropertyTableForPinning(globalData, transition);
 423         transition->pin();
 424
 425         structure = transition;
 426     }
 427
 428     ASSERT(structure->m_propertyTable);
 429     PropertyMapEntry* entry = structure->m_propertyTable->find(propertyName.impl()).first;
 430     ASSERT(entry);
 431     entry->attributes = attributes;
 432
 433     return structure;
 434 }
 435
 436 Structure* Structure::toDictionaryTransition(JSGlobalData& globalData, Structure* structure, DictionaryKind kind)
 437 {
 438     ASSERT(!structure->isUncacheableDictionary());
 439
 440     Structure* transition = create(globalData, structure);
 441
 442     structure->materializePropertyMapIfNecessary(globalData);
 443     transition->m_propertyTable = structure->copyPropertyTableForPinning(globalData, transition);
 444     transition->m_dictionaryKind = kind;
 445     transition->pin();
 446
 447     return transition;
 448 }
 449
 450 Structure* Structure::toCacheableDictionaryTransition(JSGlobalData& globalData, Structure* structure)
 451 {
 452     return toDictionaryTransition(globalData, structure, CachedDictionaryKind);
 453 }
 454
 455 Structure* Structure::toUncacheableDictionaryTransition(JSGlobalData& globalData, Structure* structure)
 456 {
 457     return toDictionaryTransition(globalData, structure, UncachedDictionaryKind);
 458 }
 459
 460 // In future we may want to cache this transition.
 461 Structure* Structure::sealTransition(JSGlobalData& globalData, Structure* structure)
 462 {
 463     Structure* transition = preventExtensionsTransition(globalData, structure);
 464
 465     if (transition->m_propertyTable) {
 466         PropertyTable::iterator end = transition->m_propertyTable->end();
 467         for (PropertyTable::iterator iter = transition->m_propertyTable->begin(); iter != end; ++iter)
 468             iter->attributes |= DontDelete;
 469     }
 470
 471     return transition;
 472 }
 473
 474 // In future we may want to cache this transition.
 475 Structure* Structure::freezeTransition(JSGlobalData& globalData, Structure* structure)
 476 {
 477     Structure* transition = preventExtensionsTransition(globalData, structure);
 478
 479     if (transition->m_propertyTable) {
 480         PropertyTable::iterator iter = transition->m_propertyTable->begin();
 481         PropertyTable::iterator end = transition->m_propertyTable->end();
 482         if (iter != end)
 483             transition->m_hasReadOnlyOrGetterSetterPropertiesExcludingProto = true;
 484         for (; iter != end; ++iter)
 485             iter->attributes |= iter->attributes & Accessor ? DontDelete : (DontDelete | ReadOnly);
 486     }
 487
 488     return transition;
 489 }
 490
 491 // In future we may want to cache this transition.
 492 Structure* Structure::preventExtensionsTransition(JSGlobalData& globalData, Structure* structure)
 493 {
 494     Structure* transition = create(globalData, structure);
 495
 496     // Don't set m_offset, as one can not transition to this.
 497
 498     structure->materializePropertyMapIfNecessary(globalData);
 499     transition->m_propertyTable = structure->copyPropertyTableForPinning(globalData, transition);
 500     transition->m_preventExtensions = true;
 501     transition->pin();
 502
 503     return transition;
 504 }
 505
 506 // In future we may want to cache this property.
 507 bool Structure::isSealed(JSGlobalData& globalData)
 508 {
 509     if (isExtensible())
 510         return false;
 511
 512     materializePropertyMapIfNecessary(globalData);
 513     if (!m_propertyTable)
 514         return true;
 515
 516     PropertyTable::iterator end = m_propertyTable->end();
 517     for (PropertyTable::iterator iter = m_propertyTable->begin(); iter != end; ++iter) {
 518         if ((iter->attributes & DontDelete) != DontDelete)
 519             return false;
 520     }
 521     return true;
 522 }
 523
 524 // In future we may want to cache this property.
 525 bool Structure::isFrozen(JSGlobalData& globalData)
 526 {
 527     if (isExtensible())
 528         return false;
 529
 530     materializePropertyMapIfNecessary(globalData);
 531     if (!m_propertyTable)
 532         return true;
 533
 534     PropertyTable::iterator end = m_propertyTable->end();
 535     for (PropertyTable::iterator iter = m_propertyTable->begin(); iter != end; ++iter) {
 536         if (!(iter->attributes & DontDelete))
 537             return false;
 538         if (!(iter->attributes & (ReadOnly | Accessor)))
 539             return false;
 540     }
 541     return true;
 542 }
 543
 544 Structure* Structure::flattenDictionaryStructure(JSGlobalData& globalData, JSObject* object)
 545 {
 546     ASSERT(isDictionary());
 547     if (isUncacheableDictionary()) {
 548         ASSERT(m_propertyTable);
 549
 550         size_t propertyCount = m_propertyTable->size();
 551         Vector<JSValue> values(propertyCount);
 552
 553         unsigned i = 0;
 554         PropertyTable::iterator end = m_propertyTable->end();
 555         for (PropertyTable::iterator iter = m_propertyTable->begin(); iter != end; ++iter, ++i) {
 556             values[i] = object->getDirectOffset(iter->offset);
 557             // Update property table to have the new property offsets
 558             iter->offset = i;
 559         }
 560
 561         // Copy the original property values into their final locations
 562         for (unsigned i = 0; i < propertyCount; i++)
 563             object->putDirectOffset(globalData, i, values[i]);
 564
 565         m_propertyTable->clearDeletedOffsets();
 566     }
 567
 568     m_dictionaryKind = NoneDictionaryKind;
 569     return this;
 570 }
 571
 572 size_t Structure::addPropertyWithoutTransition(JSGlobalData& globalData, const Identifier& propertyName, unsigned attributes, JSCell* specificValue)
 573 {
 574     ASSERT(!m_enumerationCache);
 575
 576     if (m_specificFunctionThrashCount == maxSpecificFunctionThrashCount)
 577         specificValue = 0;
 578
 579     materializePropertyMapIfNecessaryForPinning(globalData);
 580
 581     pin();
 582
 583     size_t offset = putSpecificValue(globalData, propertyName, attributes, specificValue);
 584     if (propertyStorageSize() > propertyStorageCapacity())
 585         growPropertyStorageCapacity();
 586     return offset;
 587 }
 588
 589 size_t Structure::removePropertyWithoutTransition(JSGlobalData& globalData, const Identifier& propertyName)
 590 {
 591     ASSERT(isUncacheableDictionary());
 592     ASSERT(!m_enumerationCache);
 593
 594     materializePropertyMapIfNecessaryForPinning(globalData);
 595
 596     pin();
 597     size_t offset = remove(propertyName);
 598     return offset;
 599 }
 600
 601 void Structure::pin()
 602 {
 603     ASSERT(m_propertyTable);
 604     m_isPinnedPropertyTable = true;
 605     m_previous.clear();
 606     m_nameInPrevious.clear();
 607 }
 608
 609 #if DUMP_PROPERTYMAP_STATS
 610
 611 struct PropertyMapStatisticsExitLogger {
 612     ~PropertyMapStatisticsExitLogger();
 613 };
 614
 615 static PropertyMapStatisticsExitLogger logger;
 616
 617 PropertyMapStatisticsExitLogger::~PropertyMapStatisticsExitLogger()
 618 {
 619     dataLog("\nJSC::PropertyMap statistics\n\n");
 620     dataLog("%d probes\n", numProbes);
 621     dataLog("%d collisions (%.1f%%)\n", numCollisions, 100.0 * numCollisions / numProbes);
 622     dataLog("%d rehashes\n", numRehashes);
 623     dataLog("%d removes\n", numRemoves);
 624 }
 625
 626 #endif
 627
 628 #if !DO_PROPERTYMAP_CONSTENCY_CHECK
 629
 630 inline void Structure::checkConsistency()
 631 {
 632 }
 633
 634 #endif
 635
 636 PassOwnPtr<PropertyTable> Structure::copyPropertyTable(JSGlobalData& globalData, Structure* owner)
 637 {
 638     return adoptPtr(m_propertyTable ? new PropertyTable(globalData, owner, *m_propertyTable) : 0);
 639 }
 640
 641 PassOwnPtr<PropertyTable> Structure::copyPropertyTableForPinning(JSGlobalData& globalData, Structure* owner)
 642 {
 643     return adoptPtr(m_propertyTable ? new PropertyTable(globalData, owner, *m_propertyTable) : new PropertyTable(m_offset == noOffset ? 0 : m_offset));
 644 }
 645
 646 size_t Structure::get(JSGlobalData& globalData, StringImpl* propertyName, unsigned& attributes, JSCell*& specificValue)
 647 {
 648     materializePropertyMapIfNecessary(globalData);
 649     if (!m_propertyTable)
 650         return WTF::notFound;
 651
 652     PropertyMapEntry* entry = m_propertyTable->find(propertyName).first;
 653     if (!entry)
 654         return WTF::notFound;
 655
 656     attributes = entry->attributes;
 657     specificValue = entry->specificValue.get();
 658     return entry->offset;
 659 }
 660
 661 bool Structure::despecifyFunction(JSGlobalData& globalData, const Identifier& propertyName)
 662 {
 663     materializePropertyMapIfNecessary(globalData);
 664     if (!m_propertyTable)
 665         return false;
 666
 667     ASSERT(!propertyName.isNull());
 668     PropertyMapEntry* entry = m_propertyTable->find(propertyName.impl()).first;
 669     if (!entry)
 670         return false;
 671
 672     ASSERT(entry->specificValue);
 673     entry->specificValue.clear();
 674     return true;
 675 }
 676
 677 void Structure::despecifyAllFunctions(JSGlobalData& globalData)
 678 {
 679     materializePropertyMapIfNecessary(globalData);
 680     if (!m_propertyTable)
 681         return;
 682
 683     PropertyTable::iterator end = m_propertyTable->end();
 684     for (PropertyTable::iterator iter = m_propertyTable->begin(); iter != end; ++iter)
 685         iter->specificValue.clear();
 686 }
 687
 688 size_t Structure::putSpecificValue(JSGlobalData& globalData, const Identifier& propertyName, unsigned attributes, JSCell* specificValue)
 689 {
 690     ASSERT(!propertyName.isNull());
 691     ASSERT(get(globalData, propertyName) == notFound);
 692
 693     checkConsistency();
 694     if (attributes & DontEnum)
 695         m_hasNonEnumerableProperties = true;
 696
 697     StringImpl* rep = propertyName.impl();
 698
 699     if (!m_propertyTable)
 700         createPropertyMap();
 701
 702     unsigned newOffset;
 703
 704     if (m_propertyTable->hasDeletedOffset())
 705         newOffset = m_propertyTable->getDeletedOffset();
 706     else
 707         newOffset = m_propertyTable->size();
 708
 709     m_propertyTable->add(PropertyMapEntry(globalData, this, rep, newOffset, attributes, specificValue));
 710
 711     checkConsistency();
 712     return newOffset;
 713 }
 714
 715 size_t Structure::remove(const Identifier& propertyName)
 716 {
 717     ASSERT(!propertyName.isNull());
 718
 719     checkConsistency();
 720
 721     StringImpl* rep = propertyName.impl();
 722
 723     if (!m_propertyTable)
 724         return notFound;
 725
 726     PropertyTable::find_iterator position = m_propertyTable->find(rep);
 727     if (!position.first)
 728         return notFound;
 729
 730     size_t offset = position.first->offset;
 731
 732     m_propertyTable->remove(position);
 733     m_propertyTable->addDeletedOffset(offset);
 734
 735     checkConsistency();
 736     return offset;
 737 }
 738
 739 void Structure::createPropertyMap(unsigned capacity)
 740 {
 741     ASSERT(!m_propertyTable);
 742
 743     checkConsistency();
 744     m_propertyTable = adoptPtr(new PropertyTable(capacity));
 745     checkConsistency();
 746 }
 747
 748 void Structure::getPropertyNamesFromStructure(JSGlobalData& globalData, PropertyNameArray& propertyNames, EnumerationMode mode)
 749 {
 750     materializePropertyMapIfNecessary(globalData);
 751     if (!m_propertyTable)
 752         return;
 753
 754     bool knownUnique = !propertyNames.size();
 755
 756     PropertyTable::iterator end = m_propertyTable->end();
 757     for (PropertyTable::iterator iter = m_propertyTable->begin(); iter != end; ++iter) {
 758         ASSERT(m_hasNonEnumerableProperties || !(iter->attributes & DontEnum));
 759         if (!(iter->attributes & DontEnum) || (mode == IncludeDontEnumProperties)) {
 760             if (knownUnique)
 761                 propertyNames.addKnownUnique(iter->key);
 762             else
 763                 propertyNames.add(iter->key);
 764         }
 765     }
 766 }
 767
 768 void Structure::visitChildren(JSCell* cell, SlotVisitor& visitor)
 769 {
 770     Structure* thisObject = jsCast<Structure*>(cell);
 771     ASSERT_GC_OBJECT_INHERITS(thisObject, &s_info);
 772     ASSERT(thisObject->structure()->typeInfo().overridesVisitChildren());
 773     JSCell::visitChildren(thisObject, visitor);
 774     if (thisObject->m_globalObject)
 775         visitor.append(&thisObject->m_globalObject);
 776     if (!thisObject->isObject())
 777         thisObject->m_cachedPrototypeChain.clear();
 778     else {
 779         if (thisObject->m_prototype)
 780             visitor.append(&thisObject->m_prototype);
 781         if (thisObject->m_cachedPrototypeChain)
 782             visitor.append(&thisObject->m_cachedPrototypeChain);
 783     }
 784     if (thisObject->m_previous)
 785         visitor.append(&thisObject->m_previous);
 786     if (thisObject->m_specificValueInPrevious)
 787         visitor.append(&thisObject->m_specificValueInPrevious);
 788     if (thisObject->m_enumerationCache)
 789         visitor.append(&thisObject->m_enumerationCache);
 790     if (thisObject->m_propertyTable) {
 791         PropertyTable::iterator end = thisObject->m_propertyTable->end();
 792         for (PropertyTable::iterator ptr = thisObject->m_propertyTable->begin(); ptr != end; ++ptr) {
 793             if (ptr->specificValue)
 794                 visitor.append(&ptr->specificValue);
 795         }
 796     }
 797     if (thisObject->m_objectToStringValue)
 798         visitor.append(&thisObject->m_objectToStringValue);
 799 }
 800
 801 #if DO_PROPERTYMAP_CONSTENCY_CHECK
 802
 803 void PropertyTable::checkConsistency()
 804 {
 805     ASSERT(m_indexSize >= PropertyTable::MinimumTableSize);
 806     ASSERT(m_indexMask);
 807     ASSERT(m_indexSize == m_indexMask + 1);
 808     ASSERT(!(m_indexSize & m_indexMask));
 809
 810     ASSERT(m_keyCount <= m_indexSize / 2);
 811     ASSERT(m_keyCount + m_deletedCount <= m_indexSize / 2);
 812     ASSERT(m_deletedCount <= m_indexSize / 4);
 813
 814     unsigned indexCount = 0;
 815     unsigned deletedIndexCount = 0;
 816     for (unsigned a = 0; a != m_indexSize; ++a) {
 817         unsigned entryIndex = m_index[a];
 818         if (entryIndex == PropertyTable::EmptyEntryIndex)
 819             continue;
 820         if (entryIndex == deletedEntryIndex()) {
 821             ++deletedIndexCount;
 822             continue;
 823         }
 824         ASSERT(entryIndex < deletedEntryIndex());
 825         ASSERT(entryIndex - 1 <= usedCount());
 826         ++indexCount;
 827
 828         for (unsigned b = a + 1; b != m_indexSize; ++b)
 829             ASSERT(m_index[b] != entryIndex);
 830     }
 831     ASSERT(indexCount == m_keyCount);
 832     ASSERT(deletedIndexCount == m_deletedCount);
 833
 834     ASSERT(!table()[deletedEntryIndex() - 1].key);
 835
 836     unsigned nonEmptyEntryCount = 0;
 837     for (unsigned c = 0; c < usedCount(); ++c) {
 838         StringImpl* rep = table()[c].key;
 839         if (rep == PROPERTY_MAP_DELETED_ENTRY_KEY)
 840             continue;
 841         ++nonEmptyEntryCount;
 842         unsigned i = rep->existingHash();
 843         unsigned k = 0;
 844         unsigned entryIndex;
 845         while (1) {
 846             entryIndex = m_index[i & m_indexMask];
 847             ASSERT(entryIndex != PropertyTable::EmptyEntryIndex);
 848             if (rep == table()[entryIndex - 1].key)
 849                 break;
 850             if (k == 0)
 851                 k = 1 | doubleHash(rep->existingHash());
 852             i += k;
 853         }
 854         ASSERT(entryIndex == c + 1);
 855     }
 856
 857     ASSERT(nonEmptyEntryCount == m_keyCount);
 858 }
 859
 860 void Structure::checkConsistency()
 861 {
 862     if (!m_propertyTable)
 863         return;
 864
 865     if (!m_hasNonEnumerableProperties) {
 866         PropertyTable::iterator end = m_propertyTable->end();
 867         for (PropertyTable::iterator iter = m_propertyTable->begin(); iter != end; ++iter) {
 868             ASSERT(!(iter->attributes & DontEnum));
 869         }
 870     }
 871
 872     m_propertyTable->checkConsistency();
 873 }
 874
 875 #endif // DO_PROPERTYMAP_CONSTENCY_CHECK
 876
 877 } // namespace JSC