f480051e0b8688149618b371af57ce18b716a4c8
[WebKit-https.git] / Source / JavaScriptCore / 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 StringImpl* 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.impl(), attributes, specificValue);
114         }
115         bool transitionedFor(const JSCell* specificValue)
116         {
117             return m_specificValueInPrevious == specificValue;
118         }
119         bool hasTransition(StringImpl*, unsigned attributes);
120         bool hasTransition(const Identifier& propertyName, unsigned attributes)
121         {
122             return hasTransition(propertyName.impl(), 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<StringImpl> 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         StringImpl* rep = propertyName.impl();
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