source: webkit/trunk/JavaScriptCore/runtime/Structure.h@ 51875

Last change on this file since 51875 was 50704, checked in by [email protected], 16 years ago

Can cache prototype lookups on uncacheable dictionaries.
​https://bugs.webkit.org/show_bug.cgi?id=31198

Reviewed by Gavin Barraclough.

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