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