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

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

Re-land SNES fix, with correct assertion

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