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