2011-01-27 Oliver Hunt <oliver@apple.com>
[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(JSGlobalData&, 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.get(); }
98         DeprecatedPtr<Unknown>* storedPrototypeSlot() { return &m_prototype; }
99         JSValue prototypeForLookup(ExecState*) const;
100         StructureChain* prototypeChain(ExecState*) const;
101
102         Structure* previousID() const { return m_previous.get(); }
103
104         void growPropertyStorageCapacity();
105         unsigned propertyStorageCapacity() const { return m_propertyStorageCapacity; }
106         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)); }
107         bool isUsingInlineStorage() const;
108
109         size_t get(const Identifier& propertyName);
110         size_t get(const StringImpl* rep, unsigned& attributes, JSCell*& specificValue);
111         size_t get(const Identifier& propertyName, unsigned& attributes, JSCell*& specificValue)
112         {
113             ASSERT(!propertyName.isNull());
114             return get(propertyName.impl(), attributes, specificValue);
115         }
116         bool transitionedFor(const JSCell* specificValue)
117         {
118             return m_specificValueInPrevious == specificValue;
119         }
120         bool hasTransition(StringImpl*, unsigned attributes);
121         bool hasTransition(const Identifier& propertyName, unsigned attributes)
122         {
123             return hasTransition(propertyName.impl(), attributes);
124         }
125
126         bool hasGetterSetterProperties() const { return m_hasGetterSetterProperties; }
127         void setHasGetterSetterProperties(bool hasGetterSetterProperties) { m_hasGetterSetterProperties = hasGetterSetterProperties; }
128
129         bool hasNonEnumerableProperties() const { return m_hasNonEnumerableProperties; }
130
131         bool hasAnonymousSlots() const { return !!m_anonymousSlotCount; }
132         unsigned anonymousSlotCount() const { return m_anonymousSlotCount; }
133         
134         bool isEmpty() const { return m_propertyTable ? !m_propertyTable->keyCount : m_offset == noOffset; }
135
136         void despecifyDictionaryFunction(const Identifier& propertyName);
137         void disableSpecificFunctionTracking() { m_specificFunctionThrashCount = maxSpecificFunctionThrashCount; }
138
139         void setEnumerationCache(JSPropertyNameIterator* enumerationCache); // Defined in JSPropertyNameIterator.h.
140         void clearEnumerationCache(JSPropertyNameIterator* enumerationCache); // Defined in JSPropertyNameIterator.h.
141         JSPropertyNameIterator* enumerationCache(); // Defined in JSPropertyNameIterator.h.
142         void getPropertyNames(PropertyNameArray&, EnumerationMode mode);
143         
144     private:
145
146         Structure(JSValue prototype, const TypeInfo&, unsigned anonymousSlotCount);
147         
148         typedef enum { 
149             NoneDictionaryKind = 0,
150             CachedDictionaryKind = 1,
151             UncachedDictionaryKind = 2
152         } DictionaryKind;
153         static PassRefPtr<Structure> toDictionaryTransition(Structure*, DictionaryKind);
154
155         size_t put(const Identifier& propertyName, unsigned attributes, JSCell* specificValue);
156         size_t remove(const Identifier& propertyName);
157
158         void expandPropertyMapHashTable();
159         void rehashPropertyMapHashTable();
160         void rehashPropertyMapHashTable(unsigned newTableSize);
161         void createPropertyMapHashTable();
162         void createPropertyMapHashTable(unsigned newTableSize);
163         void insertIntoPropertyMapHashTable(const PropertyMapEntry&);
164         void checkConsistency();
165
166         bool despecifyFunction(const Identifier&);
167         void despecifyAllFunctions();
168
169         PropertyMapHashTable* copyPropertyTable();
170         void materializePropertyMap();
171         void materializePropertyMapIfNecessary()
172         {
173             if (m_propertyTable || !m_previous)             
174                 return;
175             materializePropertyMap();
176         }
177
178         signed char transitionCount() const
179         {
180             // Since the number of transitions is always the same as m_offset, we keep the size of Structure down by not storing both.
181             return m_offset == noOffset ? 0 : m_offset + 1;
182         }
183
184         typedef std::pair<Structure*, Structure*> Transition;
185         typedef HashMap<StructureTransitionTableHash::Key, Transition, StructureTransitionTableHash, StructureTransitionTableHashTraits> TransitionTable;
186
187         inline bool transitionTableContains(const StructureTransitionTableHash::Key& key, JSCell* specificValue);
188         inline void transitionTableRemove(const StructureTransitionTableHash::Key& key, JSCell* specificValue);
189         inline void transitionTableAdd(const StructureTransitionTableHash::Key& key, Structure* structure, JSCell* specificValue);
190         inline bool transitionTableHasTransition(const StructureTransitionTableHash::Key& key) const;
191         inline Structure* transitionTableGet(const StructureTransitionTableHash::Key& key, JSCell* specificValue) const;
192
193         TransitionTable* transitionTable() const { ASSERT(!m_isUsingSingleSlot); return m_transitions.m_table; }
194         inline void setTransitionTable(TransitionTable* table);
195         Structure* singleTransition() const { ASSERT(m_isUsingSingleSlot); return m_transitions.m_singleTransition; }
196         void setSingleTransition(Structure* structure) { ASSERT(m_isUsingSingleSlot); m_transitions.m_singleTransition = structure; }
197         
198         bool isValid(ExecState*, StructureChain* cachedPrototypeChain) const;
199
200         static const unsigned emptyEntryIndex = 0;
201     
202         static const signed char s_maxTransitionLength = 64;
203
204         static const signed char noOffset = -1;
205
206         static const unsigned maxSpecificFunctionThrashCount = 3;
207
208         TypeInfo m_typeInfo;
209
210         DeprecatedPtr<Unknown> m_prototype;
211         mutable RefPtr<StructureChain> m_cachedPrototypeChain;
212
213         RefPtr<Structure> m_previous;
214         RefPtr<StringImpl> m_nameInPrevious;
215         JSCell* m_specificValueInPrevious;
216
217         // 'm_isUsingSingleSlot' indicates whether we are using the single transition optimisation.
218         union {
219             TransitionTable* m_table;
220             Structure* m_singleTransition;
221         } m_transitions;
222
223         WeakGCPtr<JSPropertyNameIterator> m_enumerationCache;
224
225         PropertyMapHashTable* m_propertyTable;
226
227         uint32_t m_propertyStorageCapacity;
228
229         // m_offset does not account for anonymous slots
230         signed char m_offset;
231
232         unsigned m_dictionaryKind : 2;
233         bool m_isPinnedPropertyTable : 1;
234         bool m_hasGetterSetterProperties : 1;
235         bool m_hasNonEnumerableProperties : 1;
236 #if COMPILER(WINSCW)
237         // Workaround for Symbian WINSCW compiler that cannot resolve unsigned type of the declared 
238         // bitfield, when used as argument in make_pair() function calls in structure.ccp.
239         // This bitfield optimization is insignificant for the Symbian emulator target.
240         unsigned m_attributesInPrevious;
241 #else
242         unsigned m_attributesInPrevious : 7;
243 #endif
244         unsigned m_specificFunctionThrashCount : 2;
245         unsigned m_anonymousSlotCount : 5;
246         unsigned m_isUsingSingleSlot : 1;
247         // 4 free bits
248     };
249
250     inline size_t Structure::get(const Identifier& propertyName)
251     {
252         ASSERT(!propertyName.isNull());
253
254         materializePropertyMapIfNecessary();
255         if (!m_propertyTable)
256             return WTF::notFound;
257
258         StringImpl* rep = propertyName.impl();
259
260         unsigned i = rep->existingHash();
261
262 #if DUMP_PROPERTYMAP_STATS
263         ++numProbes;
264 #endif
265
266         unsigned entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
267         if (entryIndex == emptyEntryIndex)
268             return WTF::notFound;
269
270         if (rep == m_propertyTable->entries()[entryIndex - 1].key)
271             return m_propertyTable->entries()[entryIndex - 1].offset;
272
273 #if DUMP_PROPERTYMAP_STATS
274         ++numCollisions;
275 #endif
276
277         unsigned k = 1 | WTF::doubleHash(rep->existingHash());
278
279         while (1) {
280             i += k;
281
282 #if DUMP_PROPERTYMAP_STATS
283             ++numRehashes;
284 #endif
285
286             entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
287             if (entryIndex == emptyEntryIndex)
288                 return WTF::notFound;
289
290             if (rep == m_propertyTable->entries()[entryIndex - 1].key)
291                 return m_propertyTable->entries()[entryIndex - 1].offset;
292         }
293     }
294
295 } // namespace JSC
296
297 #endif // Structure_h