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