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