runtime/Structure.h

   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 #ifndef Structure_h
  27 #define Structure_h
  28
  29 #include "Identifier.h"
  30 #include "JSType.h"
  31 #include "JSValue.h"
  32 #include "PropertyMapHashTable.h"
  33 #include "PropertyNameArray.h"
  34 #include "Protect.h"
  35 #include "StructureChain.h"
  36 #include "StructureTransitionTable.h"
  37 #include "JSTypeInfo.h"
  38 #include "UString.h"
  39 #include "WeakGCPtr.h"
  40 #include <wtf/PassRefPtr.h>
  41 #include <wtf/RefCounted.h>
  42
  43 #ifndef NDEBUG
  44 #define DUMP_PROPERTYMAP_STATS 0
  45 #else
  46 #define DUMP_PROPERTYMAP_STATS 0
  47 #endif
  48
  49 namespace JSC {
  50
  51     class MarkStack;
  52     class PropertyNameArray;
  53     class PropertyNameArrayData;
  54
  55     enum EnumerationMode {
  56         ExcludeDontEnumProperties,
  57         IncludeDontEnumProperties
  58     };
  59
  60     class Structure : public RefCounted<Structure> {
  61     public:
  62         friend class JIT;
  63         friend class StructureTransitionTable;
  64         static PassRefPtr<Structure> create(JSValue prototype, const TypeInfo& typeInfo, unsigned anonymousSlotCount)
  65         {
  66             return adoptRef(new Structure(prototype, typeInfo, anonymousSlotCount));
  67         }
  68
  69         static void startIgnoringLeaks();
  70         static void stopIgnoringLeaks();
  71
  72         static void dumpStatistics();
  73
  74         static PassRefPtr<Structure> addPropertyTransition(Structure*, const Identifier& propertyName, unsigned attributes, JSCell* specificValue, size_t& offset);
  75         static PassRefPtr<Structure> addPropertyTransitionToExistingStructure(Structure*, const Identifier& propertyName, unsigned attributes, JSCell* specificValue, size_t& offset);
  76         static PassRefPtr<Structure> removePropertyTransition(Structure*, const Identifier& propertyName, size_t& offset);
  77         static PassRefPtr<Structure> changePrototypeTransition(Structure*, JSValue prototype);
  78         static PassRefPtr<Structure> despecifyFunctionTransition(Structure*, const Identifier&);
  79         static PassRefPtr<Structure> getterSetterTransition(Structure*);
  80         static PassRefPtr<Structure> toCacheableDictionaryTransition(Structure*);
  81         static PassRefPtr<Structure> toUncacheableDictionaryTransition(Structure*);
  82
  83         PassRefPtr<Structure> flattenDictionaryStructure(JSObject*);
  84
  85         ~Structure();
  86
  87         // These should be used with caution.
  88         size_t addPropertyWithoutTransition(const Identifier& propertyName, unsigned attributes, JSCell* specificValue);
  89         size_t removePropertyWithoutTransition(const Identifier& propertyName);
  90         void setPrototypeWithoutTransition(JSValue prototype) { m_prototype = prototype; }
  91
  92         bool isDictionary() const { return m_dictionaryKind != NoneDictionaryKind; }
  93         bool isUncacheableDictionary() const { return m_dictionaryKind == UncachedDictionaryKind; }
  94
  95         const TypeInfo& typeInfo() const { return m_typeInfo; }
  96
  97         JSValue storedPrototype() const { return m_prototype; }
  98         JSValue prototypeForLookup(ExecState*) const;
  99         StructureChain* prototypeChain(ExecState*) const;
 100
 101         Structure* previousID() const { return m_previous.get(); }
 102
 103         void growPropertyStorageCapacity();
 104         unsigned propertyStorageCapacity() const { return m_propertyStorageCapacity; }
 105         unsigned propertyStorageSize() const { return m_anonymousSlotCount + (m_propertyTable ? m_propertyTable->keyCount + (m_propertyTable->deletedOffsets ? m_propertyTable->deletedOffsets->size() : 0) : m_offset + 1); }
 106         bool isUsingInlineStorage() const;
 107
 108         size_t get(const Identifier& propertyName);
 109         size_t get(const UString::Rep* rep, unsigned& attributes, JSCell*& specificValue);
 110         size_t get(const Identifier& propertyName, unsigned& attributes, JSCell*& specificValue)
 111         {
 112             ASSERT(!propertyName.isNull());
 113             return get(propertyName.ustring().rep(), attributes, specificValue);
 114         }
 115         bool transitionedFor(const JSCell* specificValue)
 116         {
 117             return m_specificValueInPrevious == specificValue;
 118         }
 119         bool hasTransition(UString::Rep*, unsigned attributes);
 120         bool hasTransition(const Identifier& propertyName, unsigned attributes)
 121         {
 122             return hasTransition(propertyName._ustring.rep(), attributes);
 123         }
 124
 125         bool hasGetterSetterProperties() const { return m_hasGetterSetterProperties; }
 126         void setHasGetterSetterProperties(bool hasGetterSetterProperties) { m_hasGetterSetterProperties = hasGetterSetterProperties; }
 127
 128         bool hasNonEnumerableProperties() const { return m_hasNonEnumerableProperties; }
 129
 130         bool hasAnonymousSlots() const { return !!m_anonymousSlotCount; }
 131         unsigned anonymousSlotCount() const { return m_anonymousSlotCount; }
 132
 133         bool isEmpty() const { return m_propertyTable ? !m_propertyTable->keyCount : m_offset == noOffset; }
 134
 135         void despecifyDictionaryFunction(const Identifier& propertyName);
 136         void disableSpecificFunctionTracking() { m_specificFunctionThrashCount = maxSpecificFunctionThrashCount; }
 137
 138         void setEnumerationCache(JSPropertyNameIterator* enumerationCache); // Defined in JSPropertyNameIterator.h.
 139         void clearEnumerationCache(JSPropertyNameIterator* enumerationCache); // Defined in JSPropertyNameIterator.h.
 140         JSPropertyNameIterator* enumerationCache(); // Defined in JSPropertyNameIterator.h.
 141         void getPropertyNames(PropertyNameArray&, EnumerationMode mode);
 142
 143     private:
 144
 145         Structure(JSValue prototype, const TypeInfo&, unsigned anonymousSlotCount);
 146
 147         typedef enum {
 148             NoneDictionaryKind = 0,
 149             CachedDictionaryKind = 1,
 150             UncachedDictionaryKind = 2
 151         } DictionaryKind;
 152         static PassRefPtr<Structure> toDictionaryTransition(Structure*, DictionaryKind);
 153
 154         size_t put(const Identifier& propertyName, unsigned attributes, JSCell* specificValue);
 155         size_t remove(const Identifier& propertyName);
 156
 157         void expandPropertyMapHashTable();
 158         void rehashPropertyMapHashTable();
 159         void rehashPropertyMapHashTable(unsigned newTableSize);
 160         void createPropertyMapHashTable();
 161         void createPropertyMapHashTable(unsigned newTableSize);
 162         void insertIntoPropertyMapHashTable(const PropertyMapEntry&);
 163         void checkConsistency();
 164
 165         bool despecifyFunction(const Identifier&);
 166         void despecifyAllFunctions();
 167
 168         PropertyMapHashTable* copyPropertyTable();
 169         void materializePropertyMap();
 170         void materializePropertyMapIfNecessary()
 171         {
 172             if (m_propertyTable || !m_previous)
 173                 return;
 174             materializePropertyMap();
 175         }
 176
 177         signed char transitionCount() const
 178         {
 179             // Since the number of transitions is always the same as m_offset, we keep the size of Structure down by not storing both.
 180             return m_offset == noOffset ? 0 : m_offset + 1;
 181         }
 182
 183         bool isValid(ExecState*, StructureChain* cachedPrototypeChain) const;
 184
 185         static const unsigned emptyEntryIndex = 0;
 186
 187         static const signed char s_maxTransitionLength = 64;
 188
 189         static const signed char noOffset = -1;
 190
 191         static const unsigned maxSpecificFunctionThrashCount = 3;
 192
 193         TypeInfo m_typeInfo;
 194
 195         JSValue m_prototype;
 196         mutable RefPtr<StructureChain> m_cachedPrototypeChain;
 197
 198         RefPtr<Structure> m_previous;
 199         RefPtr<UString::Rep> m_nameInPrevious;
 200         JSCell* m_specificValueInPrevious;
 201
 202         StructureTransitionTable table;
 203
 204         WeakGCPtr<JSPropertyNameIterator> m_enumerationCache;
 205
 206         PropertyMapHashTable* m_propertyTable;
 207
 208         uint32_t m_propertyStorageCapacity;
 209
 210         // m_offset does not account for anonymous slots
 211         signed char m_offset;
 212
 213         unsigned m_dictionaryKind : 2;
 214         bool m_isPinnedPropertyTable : 1;
 215         bool m_hasGetterSetterProperties : 1;
 216         bool m_hasNonEnumerableProperties : 1;
 217 #if COMPILER(WINSCW)
 218         // Workaround for Symbian WINSCW compiler that cannot resolve unsigned type of the declared
 219         // bitfield, when used as argument in make_pair() function calls in structure.ccp.
 220         // This bitfield optimization is insignificant for the Symbian emulator target.
 221         unsigned m_attributesInPrevious;
 222 #else
 223         unsigned m_attributesInPrevious : 7;
 224 #endif
 225         unsigned m_specificFunctionThrashCount : 2;
 226         unsigned m_anonymousSlotCount : 5;
 227         // 5 free bits
 228     };
 229
 230     inline size_t Structure::get(const Identifier& propertyName)
 231     {
 232         ASSERT(!propertyName.isNull());
 233
 234         materializePropertyMapIfNecessary();
 235         if (!m_propertyTable)
 236             return WTF::notFound;
 237
 238         UString::Rep* rep = propertyName._ustring.rep();
 239
 240         unsigned i = rep->existingHash();
 241
 242 #if DUMP_PROPERTYMAP_STATS
 243         ++numProbes;
 244 #endif
 245
 246         unsigned entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
 247         if (entryIndex == emptyEntryIndex)
 248             return WTF::notFound;
 249
 250         if (rep == m_propertyTable->entries()[entryIndex - 1].key)
 251             return m_propertyTable->entries()[entryIndex - 1].offset;
 252
 253 #if DUMP_PROPERTYMAP_STATS
 254         ++numCollisions;
 255 #endif
 256
 257         unsigned k = 1 | WTF::doubleHash(rep->existingHash());
 258
 259         while (1) {
 260             i += k;
 261
 262 #if DUMP_PROPERTYMAP_STATS
 263             ++numRehashes;
 264 #endif
 265
 266             entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
 267             if (entryIndex == emptyEntryIndex)
 268                 return WTF::notFound;
 269
 270             if (rep == m_propertyTable->entries()[entryIndex - 1].key)
 271                 return m_propertyTable->entries()[entryIndex - 1].offset;
 272         }
 273     }
 274
 275     bool StructureTransitionTable::contains(const StructureTransitionTableHash::Key& key, JSCell* specificValue)
 276     {
 277         if (usingSingleTransitionSlot()) {
 278             Structure* existingTransition = singleTransition();
 279             return existingTransition && existingTransition->m_nameInPrevious.get() == key.first
 280                    && existingTransition->m_attributesInPrevious == key.second
 281                    && (existingTransition->m_specificValueInPrevious == specificValue || existingTransition->m_specificValueInPrevious == 0);
 282         }
 283         TransitionTable::iterator find = table()->find(key);
 284         if (find == table()->end())
 285             return false;
 286
 287         return find->second.first || find->second.second->transitionedFor(specificValue);
 288     }
 289
 290     Structure* StructureTransitionTable::get(const StructureTransitionTableHash::Key& key, JSCell* specificValue) const
 291     {
 292         if (usingSingleTransitionSlot()) {
 293             Structure* existingTransition = singleTransition();
 294             if (existingTransition && existingTransition->m_nameInPrevious.get() == key.first
 295                 && existingTransition->m_attributesInPrevious == key.second
 296                 && (existingTransition->m_specificValueInPrevious == specificValue || existingTransition->m_specificValueInPrevious == 0))
 297                 return existingTransition;
 298             return 0;
 299         }
 300
 301         Transition transition = table()->get(key);
 302         if (transition.second && transition.second->transitionedFor(specificValue))
 303             return transition.second;
 304         return transition.first;
 305     }
 306
 307     bool StructureTransitionTable::hasTransition(const StructureTransitionTableHash::Key& key) const
 308     {
 309         if (usingSingleTransitionSlot()) {
 310             Structure* transition = singleTransition();
 311             return transition && transition->m_nameInPrevious == key.first
 312             && transition->m_attributesInPrevious == key.second;
 313         }
 314         return table()->contains(key);
 315     }
 316
 317     void StructureTransitionTable::reifySingleTransition()
 318     {
 319         ASSERT(usingSingleTransitionSlot());
 320         Structure* existingTransition = singleTransition();
 321         TransitionTable* transitionTable = new TransitionTable;
 322         setTransitionTable(transitionTable);
 323         if (existingTransition)
 324             add(std::make_pair(existingTransition->m_nameInPrevious.get(), existingTransition->m_attributesInPrevious), existingTransition, existingTransition->m_specificValueInPrevious);
 325     }
 326 } // namespace JSC
 327
 328 #endif // Structure_h