runtime/Structure.h

   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 #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 "StructureChain.h"
  34 #include "StructureTransitionTable.h"
  35 #include "TypeInfo.h"
  36 #include "UString.h"
  37 #include <wtf/PassRefPtr.h>
  38 #include <wtf/RefCounted.h>
  39
  40 #ifndef NDEBUG
  41 #define DUMP_PROPERTYMAP_STATS 0
  42 #else
  43 #define DUMP_PROPERTYMAP_STATS 0
  44 #endif
  45
  46 namespace JSC {
  47
  48     class PropertyNameArray;
  49     class PropertyNameArrayData;
  50
  51     class Structure : public RefCounted<Structure> {
  52     public:
  53         friend class JIT;
  54         static PassRefPtr<Structure> create(JSValue prototype, const TypeInfo& typeInfo)
  55         {
  56             return adoptRef(new Structure(prototype, typeInfo));
  57         }
  58
  59         static void startIgnoringLeaks();
  60         static void stopIgnoringLeaks();
  61
  62         static void dumpStatistics();
  63
  64         static PassRefPtr<Structure> addPropertyTransition(Structure*, const Identifier& propertyName, unsigned attributes, JSCell* specificValue, size_t& offset);
  65         static PassRefPtr<Structure> addPropertyTransitionToExistingStructure(Structure*, const Identifier& propertyName, unsigned attributes, JSCell* specificValue, size_t& offset);
  66         static PassRefPtr<Structure> removePropertyTransition(Structure*, const Identifier& propertyName, size_t& offset);
  67         static PassRefPtr<Structure> changePrototypeTransition(Structure*, JSValue prototype);
  68         static PassRefPtr<Structure> despecifyFunctionTransition(Structure*, const Identifier&);
  69         static PassRefPtr<Structure> getterSetterTransition(Structure*);
  70         static PassRefPtr<Structure> toCacheableDictionaryTransition(Structure*);
  71         static PassRefPtr<Structure> toUncacheableDictionaryTransition(Structure*);
  72
  73         PassRefPtr<Structure> flattenDictionaryStructure(JSObject*);
  74
  75         ~Structure();
  76
  77         void mark()
  78         {
  79             if (!m_prototype.marked())
  80                 m_prototype.mark();
  81         }
  82
  83         // These should be used with caution.
  84         size_t addPropertyWithoutTransition(const Identifier& propertyName, unsigned attributes, JSCell* specificValue);
  85         size_t removePropertyWithoutTransition(const Identifier& propertyName);
  86         void setPrototypeWithoutTransition(JSValue prototype) { m_prototype = prototype; }
  87
  88         bool isDictionary() const { return m_dictionaryKind != NoneDictionaryKind; }
  89         bool isUncacheableDictionary() const { return m_dictionaryKind == UncachedDictionaryKind; }
  90
  91         const TypeInfo& typeInfo() const { return m_typeInfo; }
  92
  93         JSValue storedPrototype() const { return m_prototype; }
  94         JSValue prototypeForLookup(ExecState*) const;
  95         StructureChain* prototypeChain(ExecState*) const;
  96
  97         Structure* previousID() const { return m_previous.get(); }
  98
  99         void growPropertyStorageCapacity();
 100         size_t propertyStorageCapacity() const { return m_propertyStorageCapacity; }
 101         size_t propertyStorageSize() const { return m_propertyTable ? m_propertyTable->keyCount + (m_propertyTable->deletedOffsets ? m_propertyTable->deletedOffsets->size() : 0) : m_offset + 1; }
 102         bool isUsingInlineStorage() const;
 103
 104         size_t get(const Identifier& propertyName);
 105         size_t get(const UString::Rep* rep, unsigned& attributes, JSCell*& specificValue);
 106         size_t get(const Identifier& propertyName, unsigned& attributes, JSCell*& specificValue)
 107         {
 108             ASSERT(!propertyName.isNull());
 109             return get(propertyName.ustring().rep(), attributes, specificValue);
 110         }
 111         bool transitionedFor(const JSCell* specificValue)
 112         {
 113             return m_specificValueInPrevious == specificValue;
 114         }
 115         bool hasTransition(UString::Rep*, unsigned attributes);
 116         bool hasTransition(const Identifier& propertyName, unsigned attributes)
 117         {
 118             return hasTransition(propertyName._ustring.rep(), attributes);
 119         }
 120
 121         void getEnumerablePropertyNames(ExecState*, PropertyNameArray&, JSObject*);
 122
 123         bool hasGetterSetterProperties() const { return m_hasGetterSetterProperties; }
 124         void setHasGetterSetterProperties(bool hasGetterSetterProperties) { m_hasGetterSetterProperties = hasGetterSetterProperties; }
 125
 126         bool isEmpty() const { return m_propertyTable ? !m_propertyTable->keyCount : m_offset == noOffset; }
 127
 128         JSCell* specificValue() { return m_specificValueInPrevious; }
 129         void despecifyDictionaryFunction(const Identifier& propertyName);
 130
 131     private:
 132         Structure(JSValue prototype, const TypeInfo&);
 133
 134         typedef enum {
 135             NoneDictionaryKind = 0,
 136             CachedDictionaryKind = 1,
 137             UncachedDictionaryKind = 2
 138         } DictionaryKind;
 139         static PassRefPtr<Structure> toDictionaryTransition(Structure*, DictionaryKind);
 140
 141         size_t put(const Identifier& propertyName, unsigned attributes, JSCell* specificValue);
 142         size_t remove(const Identifier& propertyName);
 143         void getEnumerableNamesFromPropertyTable(PropertyNameArray&);
 144         void getEnumerableNamesFromClassInfoTable(ExecState*, const ClassInfo*, PropertyNameArray&);
 145
 146         void expandPropertyMapHashTable();
 147         void rehashPropertyMapHashTable();
 148         void rehashPropertyMapHashTable(unsigned newTableSize);
 149         void createPropertyMapHashTable();
 150         void createPropertyMapHashTable(unsigned newTableSize);
 151         void insertIntoPropertyMapHashTable(const PropertyMapEntry&);
 152         void checkConsistency();
 153
 154         bool despecifyFunction(const Identifier&);
 155
 156         PropertyMapHashTable* copyPropertyTable();
 157         void materializePropertyMap();
 158         void materializePropertyMapIfNecessary()
 159         {
 160             if (m_propertyTable || !m_previous)
 161                 return;
 162             materializePropertyMap();
 163         }
 164
 165         void clearEnumerationCache();
 166
 167         signed char transitionCount() const
 168         {
 169             // Since the number of transitions is always the same as m_offset, we keep the size of Structure down by not storing both.
 170             return m_offset == noOffset ? 0 : m_offset + 1;
 171         }
 172
 173         bool isValid(ExecState*, StructureChain* cachedPrototypeChain) const;
 174
 175         static const unsigned emptyEntryIndex = 0;
 176
 177         static const signed char s_maxTransitionLength = 64;
 178
 179         static const signed char noOffset = -1;
 180
 181         TypeInfo m_typeInfo;
 182
 183         JSValue m_prototype;
 184         mutable RefPtr<StructureChain> m_cachedPrototypeChain;
 185
 186         RefPtr<Structure> m_previous;
 187         RefPtr<UString::Rep> m_nameInPrevious;
 188         JSCell* m_specificValueInPrevious;
 189
 190         union {
 191             Structure* singleTransition;
 192             StructureTransitionTable* table;
 193         } m_transitions;
 194
 195         RefPtr<PropertyNameArrayData> m_cachedPropertyNameArrayData;
 196
 197         PropertyMapHashTable* m_propertyTable;
 198
 199         size_t m_propertyStorageCapacity;
 200         signed char m_offset;
 201
 202         unsigned m_dictionaryKind : 2;
 203         bool m_isPinnedPropertyTable : 1;
 204         bool m_hasGetterSetterProperties : 1;
 205         bool m_usingSingleTransitionSlot : 1;
 206         unsigned m_attributesInPrevious : 7;
 207     };
 208
 209     inline size_t Structure::get(const Identifier& propertyName)
 210     {
 211         ASSERT(!propertyName.isNull());
 212
 213         materializePropertyMapIfNecessary();
 214         if (!m_propertyTable)
 215             return WTF::notFound;
 216
 217         UString::Rep* rep = propertyName._ustring.rep();
 218
 219         unsigned i = rep->computedHash();
 220
 221 #if DUMP_PROPERTYMAP_STATS
 222         ++numProbes;
 223 #endif
 224
 225         unsigned entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
 226         if (entryIndex == emptyEntryIndex)
 227             return WTF::notFound;
 228
 229         if (rep == m_propertyTable->entries()[entryIndex - 1].key)
 230             return m_propertyTable->entries()[entryIndex - 1].offset;
 231
 232 #if DUMP_PROPERTYMAP_STATS
 233         ++numCollisions;
 234 #endif
 235
 236         unsigned k = 1 | WTF::doubleHash(rep->computedHash());
 237
 238         while (1) {
 239             i += k;
 240
 241 #if DUMP_PROPERTYMAP_STATS
 242             ++numRehashes;
 243 #endif
 244
 245             entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
 246             if (entryIndex == emptyEntryIndex)
 247                 return WTF::notFound;
 248
 249             if (rep == m_propertyTable->entries()[entryIndex - 1].key)
 250                 return m_propertyTable->entries()[entryIndex - 1].offset;
 251         }
 252     }
 253
 254     bool StructureTransitionTable::contains(const StructureTransitionTableHash::Key& key, JSCell* specificValue)
 255     {
 256         TransitionTable::iterator find = m_table.find(key);
 257         if (find == m_table.end())
 258             return false;
 259
 260         return find->second.first || find->second.second->transitionedFor(specificValue);
 261     }
 262
 263     Structure* StructureTransitionTable::get(const StructureTransitionTableHash::Key& key, JSCell* specificValue) const
 264     {
 265         Transition transition = m_table.get(key);
 266         if (transition.second && transition.second->transitionedFor(specificValue))
 267             return transition.second;
 268         return transition.first;
 269     }
 270 } // namespace JSC
 271
 272 #endif // Structure_h