JavaScriptCore/kjs/StructureID.cpp

   1 /*
   2  * Copyright (C) 2008 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 "StructureID.h"
  28
  29 #include "JSObject.h"
  30 #include "PropertyNameArray.h"
  31 #include "identifier.h"
  32 #include "lookup.h"
  33 #include <wtf/RefCountedLeakCounter.h>
  34 #include <wtf/RefPtr.h>
  35
  36 #if ENABLE(JSC_MULTIPLE_THREADS)
  37 #include <wtf/Threading.h>
  38 #endif
  39
  40 using namespace std;
  41
  42 namespace JSC {
  43
  44 #ifndef NDEBUG
  45 static WTF::RefCountedLeakCounter structureIDCounter("StructureID");
  46
  47 #if ENABLE(JSC_MULTIPLE_THREADS)
  48 static Mutex ignoreSetMutex;
  49 #endif
  50
  51 static bool shouldIgnoreLeaks;
  52 static HashSet<StructureID*> ignoreSet;
  53 #endif
  54
  55 #if DUMP_STRUCTURE_ID_STATISTICS
  56 static HashSet<StructureID*> liveStructureIDSet;
  57
  58 void StructureID::dumpStatistics()
  59 {
  60     unsigned numberUsingSingleSlot = 0;
  61
  62     HashSet<StructureID*>::const_iterator end = liveStructureIDSet.end();
  63     for (HashSet<StructureID*>::const_iterator it = liveStructureIDSet.begin(); it != end; ++it) {
  64         StructureID* structureID = *it;
  65         if (structureID->m_usingSingleTransitionSlot)
  66             ++numberUsingSingleSlot;
  67     }
  68
  69     printf("Number of live StructureIDs: %d\n", liveStructureIDSet.size());
  70     printf("Number of StructureIDs using the single item optimization for transition map: %d\n", numberUsingSingleSlot);
  71 }
  72 #endif
  73
  74 StructureID::StructureID(JSValue* prototype, const TypeInfo& typeInfo)
  75     : m_typeInfo(typeInfo)
  76     , m_isDictionary(false)
  77     , m_hasGetterSetterProperties(false)
  78     , m_prototype(prototype)
  79     , m_cachedPrototypeChain(0)
  80     , m_previous(0)
  81     , m_nameInPrevious(0)
  82     , m_transitionCount(0)
  83     , m_usingSingleTransitionSlot(true)
  84     , m_propertyStorageCapacity(JSObject::inlineStorageCapacity)
  85     , m_cachedTransistionOffset(WTF::notFound)
  86 {
  87     ASSERT(m_prototype);
  88     ASSERT(m_prototype->isObject() || m_prototype->isNull());
  89
  90     m_transitions.singleTransition = 0;
  91
  92 #ifndef NDEBUG
  93 #if ENABLE(JSC_MULTIPLE_THREADS)
  94     MutexLocker protect(ignoreSetMutex);
  95 #endif
  96     if (shouldIgnoreLeaks)
  97         ignoreSet.add(this);
  98     else
  99         structureIDCounter.increment();
 100 #endif
 101
 102 #if DUMP_STRUCTURE_ID_STATISTICS
 103     liveStructureIDSet.add(this);
 104 #endif
 105 }
 106
 107 StructureID::~StructureID()
 108 {
 109     if (m_previous) {
 110         if (m_previous->m_usingSingleTransitionSlot) {
 111             m_previous->m_transitions.singleTransition->deref();
 112             m_previous->m_transitions.singleTransition = 0;
 113         } else {
 114             ASSERT(m_previous->m_transitions.table->contains(make_pair(m_nameInPrevious, m_attributesInPrevious)));
 115             m_previous->m_transitions.table->remove(make_pair(m_nameInPrevious, m_attributesInPrevious));
 116         }
 117     }
 118
 119     if (m_cachedPropertyNameArrayData)
 120         m_cachedPropertyNameArrayData->setCachedStructureID(0);
 121
 122     if (m_usingSingleTransitionSlot) {
 123         if (m_transitions.singleTransition)
 124             m_transitions.singleTransition->deref();
 125     } else
 126         delete m_transitions.table;
 127
 128 #ifndef NDEBUG
 129 #if ENABLE(JSC_MULTIPLE_THREADS)
 130     MutexLocker protect(ignoreSetMutex);
 131 #endif
 132     HashSet<StructureID*>::iterator it = ignoreSet.find(this);
 133     if (it != ignoreSet.end())
 134         ignoreSet.remove(it);
 135     else
 136         structureIDCounter.decrement();
 137 #endif
 138
 139 #if DUMP_STRUCTURE_ID_STATISTICS
 140     liveStructureIDSet.remove(this);
 141 #endif
 142 }
 143
 144 void StructureID::startIgnoringLeaks()
 145 {
 146 #ifndef NDEBUG
 147     shouldIgnoreLeaks = true;
 148 #endif
 149 }
 150
 151 void StructureID::stopIgnoringLeaks()
 152 {
 153 #ifndef NDEBUG
 154     shouldIgnoreLeaks = false;
 155 #endif
 156 }
 157
 158 void StructureID::getEnumerablePropertyNames(ExecState* exec, PropertyNameArray& propertyNames, JSObject* baseObject)
 159 {
 160     bool shouldCache = propertyNames.cacheable() && !(propertyNames.size() || m_isDictionary);
 161
 162     if (shouldCache) {
 163         if (m_cachedPropertyNameArrayData) {
 164             if (structureIDChainsAreEqual(m_cachedPropertyNameArrayData->cachedPrototypeChain(), cachedPrototypeChain())) {
 165                 propertyNames.setData(m_cachedPropertyNameArrayData);
 166                 return;
 167             }
 168         }
 169         propertyNames.setCacheable(false);
 170     }
 171
 172     m_propertyMap.getEnumerablePropertyNames(propertyNames);
 173
 174     // Add properties from the static hashtables of properties
 175     for (const ClassInfo* info = baseObject->classInfo(); info; info = info->parentClass) {
 176         const HashTable* table = info->propHashTable(exec);
 177         if (!table)
 178             continue;
 179         table->initializeIfNeeded(exec);
 180         ASSERT(table->table);
 181         int hashSizeMask = table->hashSizeMask;
 182         const HashEntry* entry = table->table;
 183         for (int i = 0; i <= hashSizeMask; ++i, ++entry) {
 184             if (entry->key() && !(entry->attributes() & DontEnum))
 185                 propertyNames.add(entry->key());
 186         }
 187     }
 188
 189     if (m_prototype->isObject())
 190         static_cast<JSObject*>(m_prototype)->getPropertyNames(exec, propertyNames);
 191
 192     if (shouldCache) {
 193         if (m_cachedPropertyNameArrayData)
 194             m_cachedPropertyNameArrayData->setCachedStructureID(0);
 195
 196         m_cachedPropertyNameArrayData = propertyNames.data();
 197
 198         StructureIDChain* chain = cachedPrototypeChain();
 199         if (!chain)
 200             chain = createCachedPrototypeChain();
 201         m_cachedPropertyNameArrayData->setCachedPrototypeChain(chain);
 202         m_cachedPropertyNameArrayData->setCachedStructureID(this);
 203     }
 204 }
 205
 206 void StructureID::clearEnumerationCache()
 207 {
 208     if (m_cachedPropertyNameArrayData)
 209         m_cachedPropertyNameArrayData->setCachedStructureID(0);
 210     m_cachedPropertyNameArrayData.clear();
 211 }
 212
 213 void StructureID::growPropertyStorageCapacity()
 214 {
 215     if (m_propertyStorageCapacity == JSObject::inlineStorageCapacity)
 216         m_propertyStorageCapacity = JSObject::nonInlineBaseStorageCapacity;
 217     else
 218         m_propertyStorageCapacity *= 2;
 219 }
 220
 221 PassRefPtr<StructureID> StructureID::addPropertyTransition(StructureID* structureID, const Identifier& propertyName, unsigned attributes, size_t& offset)
 222 {
 223     ASSERT(!structureID->m_isDictionary);
 224     ASSERT(structureID->typeInfo().type() == ObjectType);
 225
 226     if (structureID->m_usingSingleTransitionSlot) {
 227         StructureID* existingTransition = structureID->m_transitions.singleTransition;
 228         if (existingTransition && existingTransition->m_nameInPrevious == propertyName.ustring().rep() && existingTransition->m_attributesInPrevious == attributes) {
 229             offset = structureID->m_transitions.singleTransition->cachedTransistionOffset();
 230             ASSERT(offset != WTF::notFound);
 231             return existingTransition;
 232         }
 233     } else {
 234         if (StructureID* existingTransition = structureID->m_transitions.table->get(make_pair(propertyName.ustring().rep(), attributes))) {
 235             offset = existingTransition->cachedTransistionOffset();
 236             ASSERT(offset != WTF::notFound);
 237             return existingTransition;
 238         }
 239     }
 240
 241     if (structureID->m_transitionCount > s_maxTransitionLength) {
 242         RefPtr<StructureID> transition = toDictionaryTransition(structureID);
 243         offset = transition->m_propertyMap.put(propertyName, attributes);
 244         if (transition->m_propertyMap.storageSize() > transition->propertyStorageCapacity())
 245             transition->growPropertyStorageCapacity();
 246         return transition.release();
 247     }
 248
 249     RefPtr<StructureID> transition = create(structureID->m_prototype, structureID->typeInfo());
 250     transition->m_cachedPrototypeChain = structureID->m_cachedPrototypeChain;
 251     transition->m_previous = structureID;
 252     transition->m_nameInPrevious = propertyName.ustring().rep();
 253     transition->m_attributesInPrevious = attributes;
 254     transition->m_transitionCount = structureID->m_transitionCount + 1;
 255     transition->m_propertyMap = structureID->m_propertyMap;
 256     transition->m_propertyStorageCapacity = structureID->m_propertyStorageCapacity;
 257     transition->m_hasGetterSetterProperties = structureID->m_hasGetterSetterProperties;
 258
 259     offset = transition->m_propertyMap.put(propertyName, attributes);
 260     if (transition->m_propertyMap.storageSize() > transition->propertyStorageCapacity())
 261         transition->growPropertyStorageCapacity();
 262
 263     transition->setCachedTransistionOffset(offset);
 264
 265     if (structureID->m_usingSingleTransitionSlot) {
 266         if (!structureID->m_transitions.singleTransition) {
 267             structureID->m_transitions.singleTransition = transition.get();
 268             transition->ref();
 269             return transition.release();
 270         }
 271
 272         StructureID* existingTransition = structureID->m_transitions.singleTransition;
 273         structureID->m_usingSingleTransitionSlot = false;
 274         TransitionTable* transitionTable = new TransitionTable;
 275         structureID->m_transitions.table = transitionTable;
 276         transitionTable->add(make_pair(existingTransition->m_nameInPrevious, existingTransition->m_attributesInPrevious), existingTransition);
 277         existingTransition->deref();
 278     }
 279     structureID->m_transitions.table->add(make_pair(propertyName.ustring().rep(), attributes), transition.get());
 280     return transition.release();
 281 }
 282
 283 PassRefPtr<StructureID> StructureID::toDictionaryTransition(StructureID* structureID)
 284 {
 285     ASSERT(!structureID->m_isDictionary);
 286
 287     RefPtr<StructureID> transition = create(structureID->m_prototype, structureID->typeInfo());
 288     transition->m_isDictionary = true;
 289     transition->m_propertyMap = structureID->m_propertyMap;
 290     transition->m_propertyStorageCapacity = structureID->m_propertyStorageCapacity;
 291     transition->m_hasGetterSetterProperties = structureID->m_hasGetterSetterProperties;
 292     return transition.release();
 293 }
 294
 295 PassRefPtr<StructureID> StructureID::fromDictionaryTransition(StructureID* structureID)
 296 {
 297     ASSERT(structureID->m_isDictionary);
 298
 299     // Since dictionary StructureIDs are not shared, and no opcodes specialize
 300     // for them, we don't need to allocate a new StructureID when transitioning
 301     // to non-dictionary status.
 302     structureID->m_isDictionary = false;
 303     return structureID;
 304 }
 305
 306 PassRefPtr<StructureID> StructureID::changePrototypeTransition(StructureID* structureID, JSValue* prototype)
 307 {
 308     RefPtr<StructureID> transition = create(prototype, structureID->typeInfo());
 309     transition->m_transitionCount = structureID->m_transitionCount + 1;
 310     transition->m_propertyMap = structureID->m_propertyMap;
 311     transition->m_propertyStorageCapacity = structureID->m_propertyStorageCapacity;
 312     transition->m_hasGetterSetterProperties = structureID->m_hasGetterSetterProperties;
 313     return transition.release();
 314 }
 315
 316 PassRefPtr<StructureID> StructureID::getterSetterTransition(StructureID* structureID)
 317 {
 318     RefPtr<StructureID> transition = create(structureID->storedPrototype(), structureID->typeInfo());
 319     transition->m_transitionCount = structureID->m_transitionCount + 1;
 320     transition->m_propertyMap = structureID->m_propertyMap;
 321     transition->m_propertyStorageCapacity = structureID->m_propertyStorageCapacity;
 322     transition->m_hasGetterSetterProperties = transition->m_hasGetterSetterProperties;
 323     return transition.release();
 324 }
 325
 326 StructureIDChain* StructureID::createCachedPrototypeChain()
 327 {
 328     ASSERT(typeInfo().type() == ObjectType);
 329     ASSERT(!m_cachedPrototypeChain);
 330
 331     JSValue* prototype = storedPrototype();
 332     if (JSImmediate::isImmediate(prototype))
 333         return 0;
 334
 335     RefPtr<StructureIDChain> chain = StructureIDChain::create(static_cast<JSObject*>(prototype)->structureID());
 336     setCachedPrototypeChain(chain.release());
 337     return cachedPrototypeChain();
 338 }
 339
 340 StructureIDChain::StructureIDChain(StructureID* structureID)
 341 {
 342     size_t size = 1;
 343
 344     StructureID* tmp = structureID;
 345     while (!tmp->storedPrototype()->isNull()) {
 346         ++size;
 347         tmp = static_cast<JSCell*>(tmp->storedPrototype())->structureID();
 348     }
 349
 350     m_vector.set(new RefPtr<StructureID>[size + 1]);
 351
 352     size_t i;
 353     for (i = 0; i < size - 1; ++i) {
 354         m_vector[i] = structureID;
 355         structureID = static_cast<JSObject*>(structureID->storedPrototype())->structureID();
 356     }
 357     m_vector[i] = structureID;
 358     m_vector[i + 1] = 0;
 359 }
 360
 361 bool structureIDChainsAreEqual(StructureIDChain* chainA, StructureIDChain* chainB)
 362 {
 363     if (!chainA || !chainB)
 364         return false;
 365
 366     RefPtr<StructureID>* a = chainA->head();
 367     RefPtr<StructureID>* b = chainB->head();
 368     while (1) {
 369         if (*a != *b)
 370             return false;
 371         if (!*a)
 372             return true;
 373         a++;
 374         b++;
 375     }
 376 }
 377
 378 } // namespace JSC