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) : static_cast<unsigned>(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         typedef std::pair<Structure*, Structure*> Transition;
 184         typedef HashMap<StructureTransitionTableHash::Key, Transition, StructureTransitionTableHash, StructureTransitionTableHashTraits> TransitionTable;
 185
 186         inline bool transitionTableContains(const StructureTransitionTableHash::Key& key, JSCell* specificValue);
 187         inline void transitionTableRemove(const StructureTransitionTableHash::Key& key, JSCell* specificValue);
 188         inline void transitionTableAdd(const StructureTransitionTableHash::Key& key, Structure* structure, JSCell* specificValue);
 189         inline bool transitionTableHasTransition(const StructureTransitionTableHash::Key& key) const;
 190         inline Structure* transitionTableGet(const StructureTransitionTableHash::Key& key, JSCell* specificValue) const;
 191
 192         TransitionTable* transitionTable() const { ASSERT(!m_isUsingSingleSlot); return m_transitions.m_table; }
 193         inline void setTransitionTable(TransitionTable* table);
 194         Structure* singleTransition() const { ASSERT(m_isUsingSingleSlot); return m_transitions.m_singleTransition; }
 195         void setSingleTransition(Structure* structure) { ASSERT(m_isUsingSingleSlot); m_transitions.m_singleTransition = structure; }
 196
 197         bool isValid(ExecState*, StructureChain* cachedPrototypeChain) const;
 198
 199         static const unsigned emptyEntryIndex = 0;
 200
 201         static const signed char s_maxTransitionLength = 64;
 202
 203         static const signed char noOffset = -1;
 204
 205         static const unsigned maxSpecificFunctionThrashCount = 3;
 206
 207         TypeInfo m_typeInfo;
 208
 209         JSValue m_prototype;
 210         mutable RefPtr<StructureChain> m_cachedPrototypeChain;
 211
 212         RefPtr<Structure> m_previous;
 213         RefPtr<UString::Rep> m_nameInPrevious;
 214         JSCell* m_specificValueInPrevious;
 215
 216         // 'm_isUsingSingleSlot' indicates whether we are using the single transition optimisation.
 217         union {
 218             TransitionTable* m_table;
 219             Structure* m_singleTransition;
 220         } m_transitions;
 221
 222         WeakGCPtr<JSPropertyNameIterator> m_enumerationCache;
 223
 224         PropertyMapHashTable* m_propertyTable;
 225
 226         uint32_t m_propertyStorageCapacity;
 227
 228         // m_offset does not account for anonymous slots
 229         signed char m_offset;
 230
 231         unsigned m_dictionaryKind : 2;
 232         bool m_isPinnedPropertyTable : 1;
 233         bool m_hasGetterSetterProperties : 1;
 234         bool m_hasNonEnumerableProperties : 1;
 235 #if COMPILER(WINSCW)
 236         // Workaround for Symbian WINSCW compiler that cannot resolve unsigned type of the declared
 237         // bitfield, when used as argument in make_pair() function calls in structure.ccp.
 238         // This bitfield optimization is insignificant for the Symbian emulator target.
 239         unsigned m_attributesInPrevious;
 240 #else
 241         unsigned m_attributesInPrevious : 7;
 242 #endif
 243         unsigned m_specificFunctionThrashCount : 2;
 244         unsigned m_anonymousSlotCount : 5;
 245         unsigned m_isUsingSingleSlot : 1;
 246         // 4 free bits
 247     };
 248
 249     inline size_t Structure::get(const Identifier& propertyName)
 250     {
 251         ASSERT(!propertyName.isNull());
 252
 253         materializePropertyMapIfNecessary();
 254         if (!m_propertyTable)
 255             return WTF::notFound;
 256
 257         UString::Rep* rep = propertyName._ustring.rep();
 258
 259         unsigned i = rep->existingHash();
 260
 261 #if DUMP_PROPERTYMAP_STATS
 262         ++numProbes;
 263 #endif
 264
 265         unsigned entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
 266         if (entryIndex == emptyEntryIndex)
 267             return WTF::notFound;
 268
 269         if (rep == m_propertyTable->entries()[entryIndex - 1].key)
 270             return m_propertyTable->entries()[entryIndex - 1].offset;
 271
 272 #if DUMP_PROPERTYMAP_STATS
 273         ++numCollisions;
 274 #endif
 275
 276         unsigned k = 1 | WTF::doubleHash(rep->existingHash());
 277
 278         while (1) {
 279             i += k;
 280
 281 #if DUMP_PROPERTYMAP_STATS
 282             ++numRehashes;
 283 #endif
 284
 285             entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
 286             if (entryIndex == emptyEntryIndex)
 287                 return WTF::notFound;
 288
 289             if (rep == m_propertyTable->entries()[entryIndex - 1].key)
 290                 return m_propertyTable->entries()[entryIndex - 1].offset;
 291         }
 292     }
 293
 294 } // namespace JSC
 295
 296 #endif // Structure_h