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
47namespace 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

source code of qtscript/src/3rdparty/javascriptcore/JavaScriptCore/runtime/Structure.h