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; |
63 | static PassRefPtr<Structure> create(JSValue prototype, const TypeInfo& typeInfo) |
64 | { |
65 | return adoptRef(p: 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); |
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_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); |
110 | size_t get(const Identifier& propertyName, unsigned& attributes, JSCell*& specificValue) |
111 | { |
112 | ASSERT(!propertyName.isNull()); |
113 | return get(rep: propertyName.ustring().rep(), attributes, specificValue); |
114 | } |
115 | bool transitionedFor(const JSCell* specificValue) |
116 | { |
117 | return m_specificValueInPrevious == specificValue; |
118 | } |
119 | bool hasTransition(UString::Rep*, unsigned attributes); |
120 | bool hasTransition(const Identifier& propertyName, unsigned attributes) |
121 | { |
122 | return hasTransition(propertyName._ustring.rep(), 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_propertyTable && m_propertyTable->anonymousSlotCount; } |
131 | |
132 | bool isEmpty() const { return m_propertyTable ? !m_propertyTable->keyCount : m_offset == noOffset; } |
133 | |
134 | void despecifyDictionaryFunction(const Identifier& propertyName); |
135 | void disableSpecificFunctionTracking() { m_specificFunctionThrashCount = maxSpecificFunctionThrashCount; } |
136 | |
137 | void setEnumerationCache(JSPropertyNameIterator* enumerationCache); // Defined in JSPropertyNameIterator.h. |
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(); |
168 | void materializePropertyMapIfNecessary() |
169 | { |
170 | if (m_propertyTable || !m_previous) |
171 | return; |
172 | materializePropertyMap(); |
173 | } |
174 | |
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 | |
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(key: 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 | |
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 | |
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 | |
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 | |
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(key: StructureTransitionTableHash::Key(RefPtr<UString::Rep>(existingTransition->m_nameInPrevious.get()), attrsInPrev), structure: existingTransition, specificValue: existingTransition->m_specificValueInPrevious); |
322 | } |
323 | } |
324 | } // namespace JSC |
325 | |
326 | #endif // Structure_h |
327 | |