ac4a77ae12d9f3776f2fae72ebfb566840daad1b
[WebKit-https.git] / Source / JavaScriptCore / runtime / Structure.h
1 /*
2  * Copyright (C) 2008, 2009, 2012, 2013 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 "ClassInfo.h"
30 #include "ConcurrentJITLock.h"
31 #include "IndexingType.h"
32 #include "JSCJSValue.h"
33 #include "JSCell.h"
34 #include "JSType.h"
35 #include "PropertyName.h"
36 #include "PropertyNameArray.h"
37 #include "PropertyOffset.h"
38 #include "Protect.h"
39 #include "PutPropertySlot.h"
40 #include "StructureRareData.h"
41 #include "StructureTransitionTable.h"
42 #include "JSTypeInfo.h"
43 #include "Watchpoint.h"
44 #include "Weak.h"
45 #include <wtf/CompilationThread.h>
46 #include <wtf/PassRefPtr.h>
47 #include <wtf/PrintStream.h>
48 #include <wtf/RefCounted.h>
49 #include <wtf/text/StringImpl.h>
50
51
52 namespace JSC {
53
54 class DeferGC;
55 class LLIntOffsetsExtractor;
56 class PropertyNameArray;
57 class PropertyNameArrayData;
58 class PropertyTable;
59 class StructureChain;
60 class SlotVisitor;
61 class JSString;
62 struct DumpContext;
63
64 // The out-of-line property storage capacity to use when first allocating out-of-line
65 // storage. Note that all objects start out without having any out-of-line storage;
66 // this comes into play only on the first property store that exhausts inline storage.
67 static const unsigned initialOutOfLineCapacity = 4;
68
69 // The factor by which to grow out-of-line storage when it is exhausted, after the
70 // initial allocation.
71 static const unsigned outOfLineGrowthFactor = 2;
72
73 class Structure : public JSCell {
74 public:
75     friend class StructureTransitionTable;
76
77     typedef JSCell Base;
78     
79     static Structure* create(VM&, JSGlobalObject*, JSValue prototype, const TypeInfo&, const ClassInfo*, IndexingType = NonArray, unsigned inlineCapacity = 0);
80
81 protected:
82     void finishCreation(VM& vm)
83     {
84         Base::finishCreation(vm);
85         ASSERT(m_prototype);
86         ASSERT(m_prototype.isObject() || m_prototype.isNull());
87     }
88
89     void finishCreation(VM& vm, CreatingEarlyCellTag)
90     {
91         Base::finishCreation(vm, this, CreatingEarlyCell);
92         ASSERT(m_prototype);
93         ASSERT(m_prototype.isNull());
94         ASSERT(!vm.structureStructure);
95     }
96
97 public:
98     static void dumpStatistics();
99
100     JS_EXPORT_PRIVATE static Structure* addPropertyTransition(VM&, Structure*, PropertyName, unsigned attributes, JSCell* specificValue, PropertyOffset&, PutPropertySlot::Context = PutPropertySlot::UnknownContext);
101     static Structure* addPropertyTransitionToExistingStructureConcurrently(Structure*, StringImpl* uid, unsigned attributes, JSCell* specificValue, PropertyOffset&);
102     JS_EXPORT_PRIVATE static Structure* addPropertyTransitionToExistingStructure(Structure*, PropertyName, unsigned attributes, JSCell* specificValue, PropertyOffset&);
103     static Structure* removePropertyTransition(VM&, Structure*, PropertyName, PropertyOffset&);
104     JS_EXPORT_PRIVATE static Structure* changePrototypeTransition(VM&, Structure*, JSValue prototype);
105     JS_EXPORT_PRIVATE static Structure* despecifyFunctionTransition(VM&, Structure*, PropertyName);
106     static Structure* attributeChangeTransition(VM&, Structure*, PropertyName, unsigned attributes);
107     static Structure* toCacheableDictionaryTransition(VM&, Structure*);
108     static Structure* toUncacheableDictionaryTransition(VM&, Structure*);
109     static Structure* sealTransition(VM&, Structure*);
110     static Structure* freezeTransition(VM&, Structure*);
111     static Structure* preventExtensionsTransition(VM&, Structure*);
112     static Structure* nonPropertyTransition(VM&, Structure*, NonPropertyTransition);
113
114     bool isSealed(VM&);
115     bool isFrozen(VM&);
116     bool isExtensible() const { return !m_preventExtensions; }
117     bool didTransition() const { return m_didTransition; }
118     bool putWillGrowOutOfLineStorage();
119     JS_EXPORT_PRIVATE size_t suggestedNewOutOfLineStorageCapacity(); 
120
121     Structure* flattenDictionaryStructure(VM&, JSObject*);
122
123     static const bool needsDestruction = true;
124     static const bool hasImmortalStructure = true;
125     static void destroy(JSCell*);
126
127     // These should be used with caution.  
128     JS_EXPORT_PRIVATE PropertyOffset addPropertyWithoutTransition(VM&, PropertyName, unsigned attributes, JSCell* specificValue);
129     PropertyOffset removePropertyWithoutTransition(VM&, PropertyName);
130     void setPrototypeWithoutTransition(VM& vm, JSValue prototype) { m_prototype.set(vm, this, prototype); }
131         
132     bool isDictionary() const { return m_dictionaryKind != NoneDictionaryKind; }
133     bool isUncacheableDictionary() const { return m_dictionaryKind == UncachedDictionaryKind; }
134
135     bool propertyAccessesAreCacheable() { return m_dictionaryKind != UncachedDictionaryKind && !typeInfo().prohibitsPropertyCaching(); }
136
137     // Type accessors.
138     const TypeInfo& typeInfo() const { ASSERT(structure()->classInfo() == info()); return m_typeInfo; }
139     bool isObject() const { return typeInfo().isObject(); }
140
141     IndexingType indexingType() const { return m_indexingType & AllArrayTypes; }
142     IndexingType indexingTypeIncludingHistory() const { return m_indexingType; }
143         
144     bool mayInterceptIndexedAccesses() const
145     {
146         return !!(indexingTypeIncludingHistory() & MayHaveIndexedAccessors);
147     }
148         
149     bool anyObjectInChainMayInterceptIndexedAccesses() const;
150         
151     bool needsSlowPutIndexing() const;
152     NonPropertyTransition suggestedArrayStorageTransition() const;
153         
154     JSGlobalObject* globalObject() const { return m_globalObject.get(); }
155     void setGlobalObject(VM& vm, JSGlobalObject* globalObject) { m_globalObject.set(vm, this, globalObject); }
156         
157     JSValue storedPrototype() const { return m_prototype.get(); }
158     JSObject* storedPrototypeObject() const;
159     Structure* storedPrototypeStructure() const;
160     JSValue prototypeForLookup(ExecState*) const;
161     JSValue prototypeForLookup(JSGlobalObject*) const;
162     JSValue prototypeForLookup(CodeBlock*) const;
163     StructureChain* prototypeChain(VM&, JSGlobalObject*) const;
164     StructureChain* prototypeChain(ExecState*) const;
165     static void visitChildren(JSCell*, SlotVisitor&);
166         
167     // Will just the prototype chain intercept this property access?
168     bool prototypeChainMayInterceptStoreTo(VM&, PropertyName);
169         
170     bool transitionDidInvolveSpecificValue() const { return !!m_specificValueInPrevious; }
171         
172     Structure* previousID() const
173     {
174         ASSERT(structure()->classInfo() == info());
175         if (typeInfo().structureHasRareData())
176             return rareData()->previousID();
177         return previous();
178     }
179     bool transitivelyTransitionedFrom(Structure* structureToFind);
180
181     unsigned outOfLineCapacity() const
182     {
183         ASSERT(checkOffsetConsistency());
184             
185         unsigned outOfLineSize = this->outOfLineSize();
186
187         if (!outOfLineSize)
188             return 0;
189
190         if (outOfLineSize <= initialOutOfLineCapacity)
191             return initialOutOfLineCapacity;
192
193         ASSERT(outOfLineSize > initialOutOfLineCapacity);
194         COMPILE_ASSERT(outOfLineGrowthFactor == 2, outOfLineGrowthFactor_is_two);
195         return WTF::roundUpToPowerOfTwo(outOfLineSize);
196     }
197     unsigned outOfLineSize() const
198     {
199         ASSERT(checkOffsetConsistency());
200         ASSERT(structure()->classInfo() == info());
201             
202         return numberOfOutOfLineSlotsForLastOffset(m_offset);
203     }
204     bool hasInlineStorage() const
205     {
206         return !!m_inlineCapacity;
207     }
208     unsigned inlineCapacity() const
209     {
210         return m_inlineCapacity;
211     }
212     unsigned inlineSize() const
213     {
214         return std::min<unsigned>(m_offset + 1, m_inlineCapacity);
215     }
216     unsigned totalStorageSize() const
217     {
218         return numberOfSlotsForLastOffset(m_offset, m_inlineCapacity);
219     }
220     unsigned totalStorageCapacity() const
221     {
222         ASSERT(structure()->classInfo() == info());
223         return outOfLineCapacity() + inlineCapacity();
224     }
225
226     bool isValidOffset(PropertyOffset offset) const
227     {
228         return JSC::isValidOffset(offset)
229             && offset <= m_offset
230             && (offset < m_inlineCapacity || offset >= firstOutOfLineOffset);
231     }
232     
233     bool couldHaveIndexingHeader() const
234     {
235         return hasIndexedProperties(indexingType())
236             || isTypedView(m_classInfo->typedArrayStorageType);
237     }
238     
239     bool hasIndexingHeader(const JSCell*) const;
240     
241     bool masqueradesAsUndefined(JSGlobalObject* lexicalGlobalObject);
242
243     PropertyOffset get(VM&, PropertyName);
244     PropertyOffset get(VM&, const WTF::String& name);
245     JS_EXPORT_PRIVATE PropertyOffset get(VM&, PropertyName, unsigned& attributes, JSCell*& specificValue);
246
247     PropertyOffset getConcurrently(VM&, StringImpl* uid);
248     PropertyOffset getConcurrently(VM&, StringImpl* uid, unsigned& attributes, JSCell*& specificValue);
249
250     bool hasGetterSetterProperties() const { return m_hasGetterSetterProperties; }
251     bool hasReadOnlyOrGetterSetterPropertiesExcludingProto() const { return m_hasReadOnlyOrGetterSetterPropertiesExcludingProto; }
252     void setHasGetterSetterProperties(bool is__proto__)
253     {
254         m_hasGetterSetterProperties = true;
255         if (!is__proto__)
256             m_hasReadOnlyOrGetterSetterPropertiesExcludingProto = true;
257     }
258     void setContainsReadOnlyProperties()
259     {
260         m_hasReadOnlyOrGetterSetterPropertiesExcludingProto = true;
261     }
262
263     bool hasNonEnumerableProperties() const { return m_hasNonEnumerableProperties; }
264         
265     bool isEmpty() const
266     {
267         ASSERT(checkOffsetConsistency());
268         return !JSC::isValidOffset(m_offset);
269     }
270
271     JS_EXPORT_PRIVATE void despecifyDictionaryFunction(VM&, PropertyName);
272     void disableSpecificFunctionTracking() { m_specificFunctionThrashCount = maxSpecificFunctionThrashCount; }
273
274     void setEnumerationCache(VM&, JSPropertyNameIterator* enumerationCache); // Defined in JSPropertyNameIterator.h.
275     JSPropertyNameIterator* enumerationCache(); // Defined in JSPropertyNameIterator.h.
276     void getPropertyNamesFromStructure(VM&, PropertyNameArray&, EnumerationMode);
277
278     JSString* objectToStringValue()
279     {
280         if (!typeInfo().structureHasRareData())
281             return 0;
282         return rareData()->objectToStringValue();
283     }
284
285     void setObjectToStringValue(VM& vm, const JSCell* owner, JSString* value)
286     {
287         if (!typeInfo().structureHasRareData())
288             allocateRareData(vm);
289         rareData()->setObjectToStringValue(vm, owner, value);
290     }
291
292     bool staticFunctionsReified()
293     {
294         return m_staticFunctionReified;
295     }
296
297     void setStaticFunctionsReified()
298     {
299         m_staticFunctionReified = true;
300     }
301
302     const ClassInfo* classInfo() const { return m_classInfo; }
303
304     static ptrdiff_t prototypeOffset()
305     {
306         return OBJECT_OFFSETOF(Structure, m_prototype);
307     }
308
309     static ptrdiff_t globalObjectOffset()
310     {
311         return OBJECT_OFFSETOF(Structure, m_globalObject);
312     }
313
314     static ptrdiff_t typeInfoFlagsOffset()
315     {
316         return OBJECT_OFFSETOF(Structure, m_typeInfo) + TypeInfo::flagsOffset();
317     }
318
319     static ptrdiff_t typeInfoTypeOffset()
320     {
321         return OBJECT_OFFSETOF(Structure, m_typeInfo) + TypeInfo::typeOffset();
322     }
323         
324     static ptrdiff_t classInfoOffset()
325     {
326         return OBJECT_OFFSETOF(Structure, m_classInfo);
327     }
328         
329     static ptrdiff_t indexingTypeOffset()
330     {
331         return OBJECT_OFFSETOF(Structure, m_indexingType);
332     }
333
334     static Structure* createStructure(VM&);
335         
336     bool transitionWatchpointSetHasBeenInvalidated() const
337     {
338         return m_transitionWatchpointSet.hasBeenInvalidated();
339     }
340         
341     bool transitionWatchpointSetIsStillValid() const
342     {
343         return m_transitionWatchpointSet.isStillValid();
344     }
345         
346     void addTransitionWatchpoint(Watchpoint* watchpoint) const
347     {
348         ASSERT(transitionWatchpointSetIsStillValid());
349         m_transitionWatchpointSet.add(watchpoint);
350     }
351         
352     void notifyTransitionFromThisStructure() const
353     {
354         m_transitionWatchpointSet.fireAll();
355     }
356     
357     InlineWatchpointSet& transitionWatchpointSet() const
358     {
359         return m_transitionWatchpointSet;
360     }
361     
362     void dump(PrintStream&) const;
363     void dumpInContext(PrintStream&, DumpContext*) const;
364     void dumpBrief(PrintStream&, const CString&) const;
365     
366     static void dumpContextHeader(PrintStream&);
367     
368     DECLARE_EXPORT_INFO;
369
370 private:
371     friend class LLIntOffsetsExtractor;
372
373     JS_EXPORT_PRIVATE Structure(VM&, JSGlobalObject*, JSValue prototype, const TypeInfo&, const ClassInfo*, IndexingType, unsigned inlineCapacity);
374     Structure(VM&);
375     Structure(VM&, const Structure*);
376
377     static Structure* create(VM&, const Structure*);
378     
379     static Structure* addPropertyTransitionToExistingStructureImpl(Structure*, StringImpl* uid, unsigned attributes, JSCell* specificValue, PropertyOffset&);
380
381     // This will return the structure that has a usable property table, that property table,
382     // and the list of structures that we visited before we got to it. If it returns a
383     // non-null structure, it will also lock the structure that it returns; it is your job
384     // to unlock it.
385     void findStructuresAndMapForMaterialization(Vector<Structure*, 8>& structures, Structure*&, PropertyTable*&);
386     
387     typedef enum { 
388         NoneDictionaryKind = 0,
389         CachedDictionaryKind = 1,
390         UncachedDictionaryKind = 2
391     } DictionaryKind;
392     static Structure* toDictionaryTransition(VM&, Structure*, DictionaryKind);
393
394     PropertyOffset putSpecificValue(VM&, PropertyName, unsigned attributes, JSCell* specificValue);
395     PropertyOffset remove(PropertyName);
396
397     void createPropertyMap(const GCSafeConcurrentJITLocker&, VM&, unsigned keyCount = 0);
398     void checkConsistency();
399
400     bool despecifyFunction(VM&, PropertyName);
401     void despecifyAllFunctions(VM&);
402
403     WriteBarrier<PropertyTable>& propertyTable();
404     PropertyTable* takePropertyTableOrCloneIfPinned(VM&, Structure* owner);
405     PropertyTable* copyPropertyTable(VM&, Structure* owner);
406     PropertyTable* copyPropertyTableForPinning(VM&, Structure* owner);
407     JS_EXPORT_PRIVATE void materializePropertyMap(VM&);
408     void materializePropertyMapIfNecessary(VM& vm, DeferGC&)
409     {
410         ASSERT(!isCompilationThread());
411         ASSERT(structure()->classInfo() == info());
412         ASSERT(checkOffsetConsistency());
413         if (!propertyTable() && previousID())
414             materializePropertyMap(vm);
415     }
416     void materializePropertyMapIfNecessaryForPinning(VM& vm, DeferGC&)
417     {
418         ASSERT(structure()->classInfo() == info());
419         checkOffsetConsistency();
420         if (!propertyTable())
421             materializePropertyMap(vm);
422     }
423
424     void setPreviousID(VM& vm, Structure* transition, Structure* structure)
425     {
426         if (typeInfo().structureHasRareData())
427             rareData()->setPreviousID(vm, transition, structure);
428         else
429             m_previousOrRareData.set(vm, transition, structure);
430     }
431
432     void clearPreviousID()
433     {
434         if (typeInfo().structureHasRareData())
435             rareData()->clearPreviousID();
436         else
437             m_previousOrRareData.clear();
438     }
439
440     int transitionCount() const
441     {
442         // Since the number of transitions is always the same as m_offset, we keep the size of Structure down by not storing both.
443         return numberOfSlotsForLastOffset(m_offset, m_inlineCapacity);
444     }
445
446     bool isValid(JSGlobalObject*, StructureChain* cachedPrototypeChain) const;
447     bool isValid(ExecState*, StructureChain* cachedPrototypeChain) const;
448         
449     void pin();
450
451     Structure* previous() const
452     {
453         ASSERT(!typeInfo().structureHasRareData());
454         return static_cast<Structure*>(m_previousOrRareData.get());
455     }
456
457     StructureRareData* rareData() const
458     {
459         ASSERT(typeInfo().structureHasRareData());
460         return static_cast<StructureRareData*>(m_previousOrRareData.get());
461     }
462         
463     bool checkOffsetConsistency() const;
464
465     void allocateRareData(VM&);
466     void cloneRareDataFrom(VM&, const Structure*);
467
468     static const int s_maxTransitionLength = 64;
469     static const int s_maxTransitionLengthForNonEvalPutById = 512;
470
471     static const unsigned maxSpecificFunctionThrashCount = 3;
472         
473     WriteBarrier<JSGlobalObject> m_globalObject;
474     WriteBarrier<Unknown> m_prototype;
475     mutable WriteBarrier<StructureChain> m_cachedPrototypeChain;
476
477     WriteBarrier<JSCell> m_previousOrRareData;
478
479     RefPtr<StringImpl> m_nameInPrevious;
480     WriteBarrier<JSCell> m_specificValueInPrevious;
481
482     const ClassInfo* m_classInfo;
483
484     StructureTransitionTable m_transitionTable;
485
486     // Should be accessed through propertyTable(). During GC, it may be set to 0 by another thread.
487     WriteBarrier<PropertyTable> m_propertyTableUnsafe;
488
489     mutable InlineWatchpointSet m_transitionWatchpointSet;
490
491     COMPILE_ASSERT(firstOutOfLineOffset < 256, firstOutOfLineOffset_fits);
492
493     // m_offset does not account for anonymous slots
494     PropertyOffset m_offset;
495
496     TypeInfo m_typeInfo;
497     IndexingType m_indexingType;
498     uint8_t m_inlineCapacity;
499     
500     ConcurrentJITLock m_lock;
501     
502     unsigned m_dictionaryKind : 2;
503     bool m_isPinnedPropertyTable : 1;
504     bool m_hasGetterSetterProperties : 1;
505     bool m_hasReadOnlyOrGetterSetterPropertiesExcludingProto : 1;
506     bool m_hasNonEnumerableProperties : 1;
507     unsigned m_attributesInPrevious : 14;
508     unsigned m_specificFunctionThrashCount : 2;
509     unsigned m_preventExtensions : 1;
510     unsigned m_didTransition : 1;
511     unsigned m_staticFunctionReified : 1;
512 };
513
514 } // namespace JSC
515
516 #endif // Structure_h