d02879fe4ced53d031d09389b90249a10854776b
[WebKit.git] / Source / JavaScriptCore / runtime / Structure.h
1 /*
2  * Copyright (C) 2008-2019 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 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 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 #pragma once
27
28 #include "ClassInfo.h"
29 #include "ConcurrentJSLock.h"
30 #include "DeletePropertySlot.h"
31 #include "IndexingType.h"
32 #include "JSCJSValue.h"
33 #include "JSCast.h"
34 #include "JSType.h"
35 #include "JSTypeInfo.h"
36 #include "PropertyName.h"
37 #include "PropertyNameArray.h"
38 #include "PropertyOffset.h"
39 #include "PutPropertySlot.h"
40 #include "StructureIDBlob.h"
41 #include "StructureRareData.h"
42 #include "StructureTransitionTable.h"
43 #include "TinyBloomFilter.h"
44 #include "Watchpoint.h"
45 #include "WriteBarrierInlines.h"
46 #include <wtf/CompactRefPtrTuple.h>
47 #include <wtf/PrintStream.h>
48
49 namespace WTF {
50
51 class UniquedStringImpl;
52
53 } // namespace WTF
54
55 namespace JSC {
56
57 class DeferGC;
58 class LLIntOffsetsExtractor;
59 class PropertyNameArray;
60 class PropertyNameArrayData;
61 class PropertyTable;
62 class StructureChain;
63 class StructureShape;
64 class SlotVisitor;
65 class JSString;
66 struct DumpContext;
67 struct HashTable;
68 struct HashTableValue;
69
70 // The out-of-line property storage capacity to use when first allocating out-of-line
71 // storage. Note that all objects start out without having any out-of-line storage;
72 // this comes into play only on the first property store that exhausts inline storage.
73 static constexpr unsigned initialOutOfLineCapacity = 4;
74
75 // The factor by which to grow out-of-line storage when it is exhausted, after the
76 // initial allocation.
77 static constexpr unsigned outOfLineGrowthFactor = 2;
78
79 struct PropertyMapEntry {
80     UniquedStringImpl* key;
81     PropertyOffset offset;
82     uint8_t attributes;
83
84     PropertyMapEntry()
85         : key(nullptr)
86         , offset(invalidOffset)
87         , attributes(0)
88     {
89     }
90     
91     PropertyMapEntry(UniquedStringImpl* key, PropertyOffset offset, unsigned attributes)
92         : key(key)
93         , offset(offset)
94         , attributes(attributes)
95     {
96         ASSERT(this->attributes == attributes);
97     }
98 };
99
100 class StructureFireDetail : public FireDetail {
101 public:
102     StructureFireDetail(const Structure* structure)
103         : m_structure(structure)
104     {
105     }
106     
107     void dump(PrintStream& out) const override;
108
109 private:
110     const Structure* m_structure;
111 };
112
113 class DeferredStructureTransitionWatchpointFire : public DeferredWatchpointFire {
114     WTF_MAKE_NONCOPYABLE(DeferredStructureTransitionWatchpointFire);
115 public:
116     JS_EXPORT_PRIVATE DeferredStructureTransitionWatchpointFire(VM&, Structure*);
117     JS_EXPORT_PRIVATE ~DeferredStructureTransitionWatchpointFire();
118     
119     void dump(PrintStream& out) const override;
120
121     const Structure* structure() const { return m_structure; }
122
123 private:
124     const Structure* m_structure;
125 };
126
127 class Structure final : public JSCell {
128     static constexpr uint16_t shortInvalidOffset = std::numeric_limits<uint16_t>::max() - 1;
129     static constexpr uint16_t useRareDataFlag = std::numeric_limits<uint16_t>::max();
130 public:
131     friend class StructureTransitionTable;
132
133     typedef JSCell Base;
134     static constexpr unsigned StructureFlags = Base::StructureFlags | StructureIsImmortal;
135     
136     enum PolyProtoTag { PolyProto };
137     static Structure* create(VM&, JSGlobalObject*, JSValue prototype, const TypeInfo&, const ClassInfo*, IndexingType = NonArray, unsigned inlineCapacity = 0);
138     static Structure* create(PolyProtoTag, VM&, JSGlobalObject*, JSObject* prototype, const TypeInfo&, const ClassInfo*, IndexingType = NonArray, unsigned inlineCapacity = 0);
139
140     ~Structure();
141     
142     template<typename CellType, SubspaceAccess>
143     static IsoSubspace* subspaceFor(VM& vm)
144     {
145         return &vm.structureSpace;
146     }
147
148     JS_EXPORT_PRIVATE static bool isValidPrototype(JSValue);
149
150 protected:
151     void finishCreation(VM& vm)
152     {
153         Base::finishCreation(vm);
154         ASSERT(m_prototype.get().isEmpty() || isValidPrototype(m_prototype.get()));
155     }
156
157     void finishCreation(VM& vm, const Structure* previous)
158     {
159         this->finishCreation(vm);
160         if (previous->hasRareData()) {
161             const StructureRareData* previousRareData = previous->rareData();
162             if (previousRareData->hasSharedPolyProtoWatchpoint()) {
163                 ensureRareData(vm);
164                 rareData()->setSharedPolyProtoWatchpoint(previousRareData->copySharedPolyProtoWatchpoint());
165             }
166         }
167     }
168
169     void finishCreation(VM& vm, CreatingEarlyCellTag)
170     {
171         Base::finishCreation(vm, this, CreatingEarlyCell);
172         ASSERT(m_prototype);
173         ASSERT(m_prototype.isNull());
174         ASSERT(!vm.structureStructure);
175     }
176
177 public:
178     StructureID id() const { return m_blob.structureID(); }
179     int32_t objectInitializationBlob() const { return m_blob.blobExcludingStructureID(); }
180     int64_t idBlob() const { return m_blob.blob(); }
181
182     bool isProxy() const
183     {
184         JSType type = m_blob.type();
185         return type == ImpureProxyType || type == PureForwardingProxyType || type == ProxyObjectType;
186     }
187
188     static void dumpStatistics();
189
190     JS_EXPORT_PRIVATE static Structure* addPropertyTransition(VM&, Structure*, PropertyName, unsigned attributes, PropertyOffset&);
191     JS_EXPORT_PRIVATE static Structure* addNewPropertyTransition(VM&, Structure*, PropertyName, unsigned attributes, PropertyOffset&, PutPropertySlot::Context = PutPropertySlot::UnknownContext, DeferredStructureTransitionWatchpointFire* = nullptr);
192     static Structure* addPropertyTransitionToExistingStructureConcurrently(Structure*, UniquedStringImpl* uid, unsigned attributes, PropertyOffset&);
193     JS_EXPORT_PRIVATE static Structure* addPropertyTransitionToExistingStructure(Structure*, PropertyName, unsigned attributes, PropertyOffset&);
194     static Structure* removeNewPropertyTransition(VM&, Structure*, PropertyName, PropertyOffset&, DeferredStructureTransitionWatchpointFire* = nullptr);
195     static Structure* removePropertyTransition(VM&, Structure*, PropertyName, PropertyOffset&, DeferredStructureTransitionWatchpointFire* = nullptr);
196     static Structure* removePropertyTransitionFromExistingStructure(Structure*, PropertyName, PropertyOffset&);
197     static Structure* removePropertyTransitionFromExistingStructureConcurrently(Structure*, PropertyName, PropertyOffset&);
198     static Structure* changePrototypeTransition(VM&, Structure*, JSValue prototype, DeferredStructureTransitionWatchpointFire&);
199     JS_EXPORT_PRIVATE static Structure* attributeChangeTransition(VM&, Structure*, PropertyName, unsigned attributes);
200     JS_EXPORT_PRIVATE static Structure* toCacheableDictionaryTransition(VM&, Structure*, DeferredStructureTransitionWatchpointFire* = nullptr);
201     static Structure* toUncacheableDictionaryTransition(VM&, Structure*, DeferredStructureTransitionWatchpointFire* = nullptr);
202     JS_EXPORT_PRIVATE static Structure* sealTransition(VM&, Structure*);
203     JS_EXPORT_PRIVATE static Structure* freezeTransition(VM&, Structure*);
204     static Structure* preventExtensionsTransition(VM&, Structure*);
205     static Structure* nonPropertyTransition(VM&, Structure*, NonPropertyTransition);
206     JS_EXPORT_PRIVATE static Structure* nonPropertyTransitionSlow(VM&, Structure*, NonPropertyTransition);
207
208     JS_EXPORT_PRIVATE bool isSealed(VM&);
209     JS_EXPORT_PRIVATE bool isFrozen(VM&);
210     bool isStructureExtensible() const { return !didPreventExtensions(); }
211
212     JS_EXPORT_PRIVATE Structure* flattenDictionaryStructure(VM&, JSObject*);
213
214     static constexpr bool needsDestruction = true;
215     static void destroy(JSCell*);
216
217     // Versions that take a func will call it after making the change but while still holding
218     // the lock. The callback is not called if there is no change being made, like if you call
219     // removePropertyWithoutTransition() and the property is not found.
220     template<typename Func>
221     PropertyOffset addPropertyWithoutTransition(VM&, PropertyName, unsigned attributes, const Func&);
222     template<typename Func>
223     PropertyOffset removePropertyWithoutTransition(VM&, PropertyName, const Func&);
224     void setPrototypeWithoutTransition(VM&, JSValue prototype);
225         
226     bool isDictionary() const { return dictionaryKind() != NoneDictionaryKind; }
227     bool isUncacheableDictionary() const { return dictionaryKind() == UncachedDictionaryKind; }
228   
229     bool prototypeQueriesAreCacheable()
230     {
231         return !typeInfo().prohibitsPropertyCaching();
232     }
233     
234     bool propertyAccessesAreCacheable()
235     {
236         return dictionaryKind() != UncachedDictionaryKind
237             && prototypeQueriesAreCacheable()
238             && !(typeInfo().getOwnPropertySlotIsImpure() && !typeInfo().newImpurePropertyFiresWatchpoints());
239     }
240
241     bool propertyAccessesAreCacheableForAbsence()
242     {
243         return !typeInfo().getOwnPropertySlotIsImpureForPropertyAbsence();
244     }
245
246     bool needImpurePropertyWatchpoint()
247     {
248         return propertyAccessesAreCacheable()
249             && typeInfo().getOwnPropertySlotIsImpure()
250             && typeInfo().newImpurePropertyFiresWatchpoints();
251     }
252
253     bool isImmutablePrototypeExoticObject()
254     {
255         return typeInfo().isImmutablePrototypeExoticObject();
256     }
257
258     // We use SlowPath in GetByStatus for structures that may get new impure properties later to prevent
259     // DFG from inlining property accesses since structures don't transition when a new impure property appears.
260     bool takesSlowPathInDFGForImpureProperty()
261     {
262         return typeInfo().getOwnPropertySlotIsImpure();
263     }
264
265     TypeInfo::OutOfLineTypeFlags outOfLineTypeFlags() const
266     {
267 #if CPU(ADDRESS64)
268         return m_outOfLineTypeFlagsAndPropertyTableUnsafe.type();
269 #else
270         return m_outOfLineTypeFlags;
271 #endif
272     }
273     
274     // Type accessors.
275     TypeInfo typeInfo() const { return m_blob.typeInfo(outOfLineTypeFlags()); }
276     bool isObject() const { return typeInfo().isObject(); }
277
278     IndexingType indexingType() const { return m_blob.indexingModeIncludingHistory() & AllWritableArrayTypes; }
279     IndexingType indexingMode() const  { return m_blob.indexingModeIncludingHistory() & AllArrayTypes; }
280     IndexingType indexingModeIncludingHistory() const { return m_blob.indexingModeIncludingHistory(); }
281         
282     inline bool mayInterceptIndexedAccesses() const;
283     
284     bool holesMustForwardToPrototype(VM&, JSObject*) const;
285         
286     JSGlobalObject* globalObject() const { return m_globalObject.get(); }
287
288     // NOTE: This method should only be called during the creation of structures, since the global
289     // object of a structure is presumed to be immutable in a bunch of places.
290     void setGlobalObject(VM&, JSGlobalObject*);
291
292     ALWAYS_INLINE bool hasMonoProto() const
293     {
294         return !m_prototype.get().isEmpty();
295     }
296     ALWAYS_INLINE bool hasPolyProto() const
297     {
298         return !hasMonoProto();
299     }
300     ALWAYS_INLINE JSValue storedPrototype() const
301     {
302         ASSERT(hasMonoProto());
303         return m_prototype.get();
304     }
305     JSValue storedPrototype(const JSObject*) const;
306     JSObject* storedPrototypeObject(const JSObject*) const;
307     Structure* storedPrototypeStructure(const JSObject*) const;
308
309     JSObject* storedPrototypeObject() const;
310     Structure* storedPrototypeStructure() const;
311     JSValue prototypeForLookup(JSGlobalObject*) const;
312     JSValue prototypeForLookup(JSGlobalObject*, JSCell* base) const;
313     StructureChain* prototypeChain(VM&, JSGlobalObject*, JSObject* base) const;
314     StructureChain* prototypeChain(JSGlobalObject*, JSObject* base) const;
315     static void visitChildren(JSCell*, SlotVisitor&);
316     
317     // A Structure is cheap to mark during GC if doing so would only add a small and bounded amount
318     // to our heap footprint. For example, if the structure refers to a global object that is not
319     // yet marked, then as far as we know, the decision to mark this Structure would lead to a large
320     // increase in footprint because no other object refers to that global object. This method
321     // returns true if all user-controlled (and hence unbounded in size) objects referenced from the
322     // Structure are already marked.
323     bool isCheapDuringGC(VM&);
324     
325     // Returns true if this structure is now marked.
326     bool markIfCheap(SlotVisitor&);
327     
328     bool hasRareData() const
329     {
330         return isRareData(cachedPrototypeChainOrRareData());
331     }
332
333     StructureRareData* rareData()
334     {
335         ASSERT(hasRareData());
336         return static_cast<StructureRareData*>(cachedPrototypeChainOrRareData());
337     }
338
339     const StructureRareData* rareData() const
340     {
341         ASSERT(hasRareData());
342         return static_cast<const StructureRareData*>(cachedPrototypeChainOrRareData());
343     }
344
345     const StructureRareData* rareDataConcurrently() const
346     {
347         JSCell* cell = cachedPrototypeChainOrRareData();
348         if (isRareData(cell))
349             return static_cast<StructureRareData*>(cell);
350         return nullptr;
351     }
352
353     StructureRareData* ensureRareData(VM& vm)
354     {
355         if (!hasRareData())
356             allocateRareData(vm);
357         return rareData();
358     }
359     
360     Structure* previousID(VM& vm) const
361     {
362         if (!m_previousID)
363             return nullptr;
364         return vm.getStructure(m_previousID);
365     }
366     bool transitivelyTransitionedFrom(Structure* structureToFind);
367
368     PropertyOffset maxOffset() const
369     {
370 #if CPU(ADDRESS64)
371         uint16_t maxOffset = m_maxOffsetAndTransitionPropertyName.type();
372 #else
373         uint16_t maxOffset = m_maxOffset;
374 #endif
375         if (maxOffset == shortInvalidOffset)
376             return invalidOffset;
377         if (maxOffset == useRareDataFlag)
378             return rareData()->m_maxOffset;
379         return maxOffset;
380     }
381
382     void setMaxOffset(VM& vm, PropertyOffset offset)
383     {
384         ASSERT(!isCompilationThread() && !Thread::mayBeGCThread());
385         auto commit = [&](uint16_t value) {
386 #if CPU(ADDRESS64)
387             m_maxOffsetAndTransitionPropertyName.setType(value);
388 #else
389             m_maxOffset = value;
390 #endif
391         };
392
393         if (offset == invalidOffset) {
394             commit(shortInvalidOffset);
395             return;
396         }
397         if (offset < useRareDataFlag && offset < shortInvalidOffset) {
398             commit(offset);
399             return;
400         }
401 #if CPU(ADDRESS64)
402         uint16_t maxOffset = m_maxOffsetAndTransitionPropertyName.type();
403 #else
404         uint16_t maxOffset = m_maxOffset;
405 #endif
406         if (maxOffset == useRareDataFlag) {
407             rareData()->m_maxOffset = offset;
408             return;
409         }
410
411         ensureRareData(vm)->m_maxOffset = offset;
412         WTF::storeStoreFence();
413         commit(useRareDataFlag);
414     }
415
416     PropertyOffset transitionOffset() const
417     {
418 #if CPU(ADDRESS64)
419         uint16_t transitionOffset = m_transitionOffsetAndClassInfo.type();
420 #else
421         uint16_t transitionOffset = m_transitionOffset;
422 #endif
423         if (transitionOffset == shortInvalidOffset)
424             return invalidOffset;
425         if (transitionOffset == useRareDataFlag)
426             return rareData()->m_transitionOffset;
427         return transitionOffset;
428     }
429
430     void setTransitionOffset(VM& vm, PropertyOffset offset)
431     {
432         ASSERT(!isCompilationThread() && !Thread::mayBeGCThread());
433         auto commit = [&](uint16_t value) {
434 #if CPU(ADDRESS64)
435             m_transitionOffsetAndClassInfo.setType(value);
436 #else
437             m_transitionOffset = value;
438 #endif
439         };
440
441         if (offset == invalidOffset) {
442             commit(shortInvalidOffset);
443             return;
444         }
445         if (offset < useRareDataFlag && offset < shortInvalidOffset) {
446             commit(offset);
447             return;
448         }
449 #if CPU(ADDRESS64)
450         uint16_t transitionOffset = m_transitionOffsetAndClassInfo.type();
451 #else
452         uint16_t transitionOffset = m_transitionOffset;
453 #endif
454         if (transitionOffset == useRareDataFlag) {
455             rareData()->m_transitionOffset = offset;
456             return;
457         }
458
459         ensureRareData(vm)->m_transitionOffset = offset;
460         WTF::storeStoreFence();
461         commit(useRareDataFlag);
462     }
463
464     static unsigned outOfLineCapacity(PropertyOffset maxOffset)
465     {
466         unsigned outOfLineSize = Structure::outOfLineSize(maxOffset);
467
468         // This algorithm completely determines the out-of-line property storage growth algorithm.
469         // The JSObject code will only trigger a resize if the value returned by this algorithm
470         // changed between the new and old structure. So, it's important to keep this simple because
471         // it's on a fast path.
472         
473         if (!outOfLineSize)
474             return 0;
475
476         if (outOfLineSize <= initialOutOfLineCapacity)
477             return initialOutOfLineCapacity;
478
479         ASSERT(outOfLineSize > initialOutOfLineCapacity);
480         COMPILE_ASSERT(outOfLineGrowthFactor == 2, outOfLineGrowthFactor_is_two);
481         return WTF::roundUpToPowerOfTwo(outOfLineSize);
482     }
483     
484     static unsigned outOfLineSize(PropertyOffset maxOffset)
485     {
486         return numberOfOutOfLineSlotsForMaxOffset(maxOffset);
487     }
488
489     unsigned outOfLineCapacity() const
490     {
491         return outOfLineCapacity(maxOffset());
492     }
493     unsigned outOfLineSize() const
494     {
495         return outOfLineSize(maxOffset());
496     }
497     bool hasInlineStorage() const { return !!inlineCapacity(); }
498     unsigned inlineCapacity() const
499     {
500 #if CPU(ADDRESS64)
501         return static_cast<uint8_t>(m_inlineCapacityAndCachedPrototypeChainOrRareData.type());
502 #else
503         return m_inlineCapacity;
504 #endif
505     }
506     unsigned inlineSize() const
507     {
508         return std::min<unsigned>(maxOffset() + 1, inlineCapacity());
509     }
510     unsigned totalStorageCapacity() const
511     {
512         ASSERT(structure()->classInfo() == info());
513         return outOfLineCapacity() + inlineCapacity();
514     }
515
516     bool isValidOffset(PropertyOffset offset) const
517     {
518         return JSC::isValidOffset(offset)
519             && offset <= maxOffset()
520             && (offset < static_cast<int>(inlineCapacity()) || offset >= firstOutOfLineOffset);
521     }
522
523     bool hijacksIndexingHeader() const
524     {
525         return isTypedView(classInfo()->typedArrayStorageType);
526     }
527     
528     bool couldHaveIndexingHeader() const
529     {
530         return hasIndexedProperties(indexingType())
531             || hijacksIndexingHeader();
532     }
533     
534     bool hasIndexingHeader(const JSCell*) const;
535     bool mayHaveIndexingHeader() const;
536     bool canCacheDeleteIC() const;
537     
538     bool masqueradesAsUndefined(JSGlobalObject* lexicalGlobalObject);
539
540     PropertyOffset get(VM&, PropertyName);
541     PropertyOffset get(VM&, PropertyName, unsigned& attributes);
542
543     // This is a somewhat internalish method. It will call your functor while possibly holding the
544     // Structure's lock. There is no guarantee whether the lock is held or not in any particular
545     // call. So, you have to assume the worst. Also, the functor returns true if it wishes for you
546     // to continue or false if it's done.
547     template<typename Functor>
548     void forEachPropertyConcurrently(const Functor&);
549
550     template<typename Functor>
551     void forEachProperty(VM&, const Functor&);
552     
553     PropertyOffset getConcurrently(UniquedStringImpl* uid);
554     PropertyOffset getConcurrently(UniquedStringImpl* uid, unsigned& attributes);
555     
556     Vector<PropertyMapEntry> getPropertiesConcurrently();
557     
558     void setHasGetterSetterPropertiesWithProtoCheck(bool is__proto__)
559     {
560         setHasGetterSetterProperties(true);
561         if (!is__proto__)
562             setHasReadOnlyOrGetterSetterPropertiesExcludingProto(true);
563     }
564     
565     void setContainsReadOnlyProperties() { setHasReadOnlyOrGetterSetterPropertiesExcludingProto(true); }
566     
567     void setHasCustomGetterSetterPropertiesWithProtoCheck(bool is__proto__)
568     {
569         setHasCustomGetterSetterProperties(true);
570         if (!is__proto__)
571             setHasReadOnlyOrGetterSetterPropertiesExcludingProto(true);
572     }
573
574     void setCachedPropertyNameEnumerator(VM&, JSPropertyNameEnumerator*);
575     JSPropertyNameEnumerator* cachedPropertyNameEnumerator() const;
576     bool canCachePropertyNameEnumerator(VM&) const;
577     bool canAccessPropertiesQuicklyForEnumeration() const;
578
579     void setCachedOwnKeys(VM&, JSImmutableButterfly*);
580     JSImmutableButterfly* cachedOwnKeys() const;
581     JSImmutableButterfly* cachedOwnKeysIgnoringSentinel() const;
582     bool canCacheOwnKeys() const;
583
584     void getPropertyNamesFromStructure(VM&, PropertyNameArray&, EnumerationMode);
585
586     JSString* objectToStringValue()
587     {
588         if (!hasRareData())
589             return 0;
590         return rareData()->objectToStringValue();
591     }
592
593     void setObjectToStringValue(JSGlobalObject*, VM&, JSString* value, PropertySlot toStringTagSymbolSlot);
594
595     const ClassInfo* classInfo() const
596     {
597 #if CPU(ADDRESS64)
598         return m_transitionOffsetAndClassInfo.pointer();
599 #else
600         return m_classInfo;
601 #endif
602     }
603
604     static ptrdiff_t structureIDOffset()
605     {
606         return OBJECT_OFFSETOF(Structure, m_blob) + StructureIDBlob::structureIDOffset();
607     }
608
609     static ptrdiff_t prototypeOffset()
610     {
611         return OBJECT_OFFSETOF(Structure, m_prototype);
612     }
613
614     static ptrdiff_t globalObjectOffset()
615     {
616         return OBJECT_OFFSETOF(Structure, m_globalObject);
617     }
618
619     static ptrdiff_t offsetOfClassInfo()
620     {
621 #if CPU(ADDRESS64)
622         return OBJECT_OFFSETOF(Structure, m_transitionOffsetAndClassInfo);
623 #else
624         return OBJECT_OFFSETOF(Structure, m_classInfo);
625 #endif
626     }
627
628     static ptrdiff_t indexingModeIncludingHistoryOffset()
629     {
630         return OBJECT_OFFSETOF(Structure, m_blob) + StructureIDBlob::indexingModeIncludingHistoryOffset();
631     }
632
633 #if CPU(LITTLE_ENDIAN)
634     static ptrdiff_t offsetOfInlineCapacity()
635     {
636 #if CPU(ADDRESS64)
637         return OBJECT_OFFSETOF(Structure, m_inlineCapacityAndCachedPrototypeChainOrRareData) + CompactPointerTuple<JSCell*, uint16_t>::offsetOfType();
638 #else
639         return OBJECT_OFFSETOF(Structure, m_inlineCapacity);
640 #endif
641
642     }
643 #endif
644
645     static ptrdiff_t offsetOfCachedPrototypeChainOrRareData()
646     {
647 #if CPU(ADDRESS64)
648         return OBJECT_OFFSETOF(Structure, m_inlineCapacityAndCachedPrototypeChainOrRareData);
649 #else
650         return OBJECT_OFFSETOF(Structure, m_cachedPrototypeChainOrRareData);
651 #endif
652     }
653
654     static Structure* createStructure(VM&);
655         
656     bool transitionWatchpointSetHasBeenInvalidated() const
657     {
658         return m_transitionWatchpointSet.hasBeenInvalidated();
659     }
660         
661     bool transitionWatchpointSetIsStillValid() const
662     {
663         return m_transitionWatchpointSet.isStillValid();
664     }
665     
666     bool dfgShouldWatchIfPossible() const
667     {
668         // FIXME: We would like to not watch things that are unprofitable to watch, like
669         // dictionaries. Unfortunately, we can't do such things: a dictionary could get flattened,
670         // in which case it will start to appear watchable and so the DFG will think that it is
671         // watching it. We should come up with a comprehensive story for not watching things that
672         // aren't profitable to watch.
673         // https://bugs.webkit.org/show_bug.cgi?id=133625
674         
675         // - We don't watch Structures that either decided not to be watched, or whose predecessors
676         //   decided not to be watched. This happens when a transition is fired while being watched.
677         if (transitionWatchpointIsLikelyToBeFired())
678             return false;
679
680         // - Don't watch Structures that had been dictionaries.
681         if (hasBeenDictionary())
682             return false;
683         
684         return true;
685     }
686     
687     bool dfgShouldWatch() const
688     {
689         return dfgShouldWatchIfPossible() && transitionWatchpointSetIsStillValid();
690     }
691         
692     void addTransitionWatchpoint(Watchpoint* watchpoint) const
693     {
694         ASSERT(transitionWatchpointSetIsStillValid());
695         m_transitionWatchpointSet.add(watchpoint);
696     }
697     
698     void didTransitionFromThisStructure(DeferredStructureTransitionWatchpointFire* = nullptr) const;
699     
700     InlineWatchpointSet& transitionWatchpointSet() const
701     {
702         return m_transitionWatchpointSet;
703     }
704     
705     WatchpointSet* ensurePropertyReplacementWatchpointSet(VM&, PropertyOffset);
706     void startWatchingPropertyForReplacements(VM& vm, PropertyOffset offset)
707     {
708         ensurePropertyReplacementWatchpointSet(vm, offset);
709     }
710     void startWatchingPropertyForReplacements(VM&, PropertyName);
711     WatchpointSet* propertyReplacementWatchpointSet(PropertyOffset);
712     void didReplaceProperty(PropertyOffset);
713     void didCachePropertyReplacement(VM&, PropertyOffset);
714     
715     void startWatchingInternalPropertiesIfNecessary(VM& vm)
716     {
717         if (LIKELY(didWatchInternalProperties()))
718             return;
719         startWatchingInternalProperties(vm);
720     }
721     
722     Ref<StructureShape> toStructureShape(JSValue, bool& sawPolyProtoStructure);
723     
724     void dump(PrintStream&) const;
725     void dumpInContext(PrintStream&, DumpContext*) const;
726     void dumpBrief(PrintStream&, const CString&) const;
727     
728     static void dumpContextHeader(PrintStream&);
729     
730     static bool shouldConvertToPolyProto(const Structure* a, const Structure* b);
731
732     UniquedStringImpl* transitionPropertyName() const
733     {
734 #if CPU(ADDRESS64)
735         return m_maxOffsetAndTransitionPropertyName.pointer();
736 #else
737         return m_transitionPropertyName.get();
738 #endif
739     }
740
741     struct PropertyHashEntry {
742         const HashTable* table;
743         const HashTableValue* value;
744     };
745     Optional<PropertyHashEntry> findPropertyHashEntry(PropertyName) const;
746     
747     DECLARE_EXPORT_INFO;
748
749 private:
750     bool ruleOutUnseenProperty(UniquedStringImpl*) const;
751 #if CPU(ADDRESS64)
752     // As a propertyHash, 64bit environment uses 16bit property-hash + seenProperties set.
753     uintptr_t propertyHash() const { return m_propertyHashAndSeenProperties.data(); }
754 #else
755     uint32_t propertyHash() const { return m_propertyHash; }
756 #endif
757     TinyBloomFilter seenProperties() const;
758     void addPropertyHashAndSeenProperty(unsigned, UniquedStringImpl*);
759
760     void setTransitionPropertyName(const AbstractLocker&, UniquedStringImpl* transitionPropertyName)
761     {
762 #if CPU(ADDRESS64)
763         m_maxOffsetAndTransitionPropertyName.setPointer(transitionPropertyName);
764 #else
765         m_transitionPropertyName = transitionPropertyName;
766 #endif
767     }
768
769     typedef enum { 
770         NoneDictionaryKind = 0,
771         CachedDictionaryKind = 1,
772         UncachedDictionaryKind = 2
773     } DictionaryKind;
774
775 public:
776 #define DEFINE_BITFIELD(type, lowerName, upperName, width, offset) \
777     static constexpr uint32_t s_##lowerName##Shift = offset;\
778     static constexpr uint32_t s_##lowerName##Mask = ((1 << (width - 1)) | ((1 << (width - 1)) - 1));\
779     static constexpr uint32_t s_bitWidthOf##upperName = width;\
780     type lowerName() const { return static_cast<type>((m_bitField >> offset) & s_##lowerName##Mask); }\
781     void set##upperName(type newValue) \
782     {\
783         m_bitField &= ~(s_##lowerName##Mask << offset);\
784         m_bitField |= (newValue & s_##lowerName##Mask) << offset;\
785         ASSERT(newValue == lowerName());\
786     }
787
788     DEFINE_BITFIELD(DictionaryKind, dictionaryKind, DictionaryKind, 2, 0);
789     DEFINE_BITFIELD(bool, isPinnedPropertyTable, IsPinnedPropertyTable, 1, 2);
790     DEFINE_BITFIELD(bool, hasGetterSetterProperties, HasGetterSetterProperties, 1, 3);
791     DEFINE_BITFIELD(bool, hasReadOnlyOrGetterSetterPropertiesExcludingProto, HasReadOnlyOrGetterSetterPropertiesExcludingProto, 1, 4);
792     DEFINE_BITFIELD(bool, isQuickPropertyAccessAllowedForEnumeration, IsQuickPropertyAccessAllowedForEnumeration, 1, 5);
793     DEFINE_BITFIELD(unsigned, transitionPropertyAttributes, TransitionPropertyAttributes, 8, 6);
794     DEFINE_BITFIELD(bool, didPreventExtensions, DidPreventExtensions, 1, 14);
795     DEFINE_BITFIELD(bool, didTransition, DidTransition, 1, 15);
796     DEFINE_BITFIELD(bool, staticPropertiesReified, StaticPropertiesReified, 1, 16);
797     DEFINE_BITFIELD(bool, hasBeenFlattenedBefore, HasBeenFlattenedBefore, 1, 17);
798     DEFINE_BITFIELD(bool, hasCustomGetterSetterProperties, HasCustomGetterSetterProperties, 1, 18);
799     DEFINE_BITFIELD(bool, didWatchInternalProperties, DidWatchInternalProperties, 1, 19);
800     DEFINE_BITFIELD(bool, transitionWatchpointIsLikelyToBeFired, TransitionWatchpointIsLikelyToBeFired, 1, 20);
801     DEFINE_BITFIELD(bool, hasBeenDictionary, HasBeenDictionary, 1, 21);
802     DEFINE_BITFIELD(bool, protectPropertyTableWhileTransitioning, ProtectPropertyTableWhileTransitioning, 1, 22);
803     DEFINE_BITFIELD(bool, hasUnderscoreProtoPropertyExcludingOriginalProto, HasUnderscoreProtoPropertyExcludingOriginalProto, 1, 23);
804     DEFINE_BITFIELD(bool, isPropertyDeletionTransition, IsPropertyDeletionTransition, 1, 24);
805
806     static_assert(s_bitWidthOfTransitionPropertyAttributes <= sizeof(TransitionPropertyAttributes) * 8);
807
808 private:
809     friend class LLIntOffsetsExtractor;
810
811     JS_EXPORT_PRIVATE Structure(VM&, JSGlobalObject*, JSValue prototype, const TypeInfo&, const ClassInfo*, IndexingType, unsigned inlineCapacity);
812     Structure(VM&);
813     Structure(VM&, Structure*, DeferredStructureTransitionWatchpointFire*);
814
815     static Structure* create(VM&, Structure*, DeferredStructureTransitionWatchpointFire* = nullptr);
816     
817     static Structure* addPropertyTransitionToExistingStructureImpl(Structure*, UniquedStringImpl* uid, unsigned attributes, PropertyOffset&);
818     static Structure* removePropertyTransitionFromExistingStructureImpl(Structure*, PropertyName, unsigned attributes, PropertyOffset&);
819
820     // This will return the structure that has a usable property table, that property table,
821     // and the list of structures that we visited before we got to it. If it returns a
822     // non-null structure, it will also lock the structure that it returns; it is your job
823     // to unlock it.
824     void findStructuresAndMapForMaterialization(VM&, Vector<Structure*, 8>& structures, Structure*&, PropertyTable*&);
825     
826     static Structure* toDictionaryTransition(VM&, Structure*, DictionaryKind, DeferredStructureTransitionWatchpointFire* = nullptr);
827
828     enum class ShouldPin { No, Yes };
829     template<ShouldPin, typename Func>
830     PropertyOffset add(VM&, PropertyName, unsigned attributes, const Func&);
831     PropertyOffset add(VM&, PropertyName, unsigned attributes);
832     template<ShouldPin, typename Func>
833     PropertyOffset remove(VM&, PropertyName, const Func&);
834     PropertyOffset remove(VM&, PropertyName);
835
836     void checkConsistency();
837
838     // This may grab the lock, or not. Do not call when holding the Structure's lock.
839     PropertyTable* ensurePropertyTableIfNotEmpty(VM& vm)
840     {
841         if (PropertyTable* result = propertyTableUnsafeOrNull())
842             return result;
843         if (!previousID(vm))
844             return nullptr;
845         return materializePropertyTable(vm);
846     }
847     
848     // This may grab the lock, or not. Do not call when holding the Structure's lock.
849     PropertyTable* ensurePropertyTable(VM& vm)
850     {
851         if (PropertyTable* result = propertyTableUnsafeOrNull())
852             return result;
853         return materializePropertyTable(vm);
854     }
855     
856     PropertyTable* propertyTableUnsafeOrNull() const
857     {
858 #if CPU(ADDRESS64)
859         return m_outOfLineTypeFlagsAndPropertyTableUnsafe.pointer();
860 #else
861         return m_propertyTableUnsafe.get();
862 #endif
863     }
864     
865     // This will grab the lock. Do not call when holding the Structure's lock.
866     JS_EXPORT_PRIVATE PropertyTable* materializePropertyTable(VM&, bool setPropertyTable = true);
867     
868     void setPropertyTable(VM& vm, PropertyTable* table);
869     void clearPropertyTable();
870     
871     PropertyTable* takePropertyTableOrCloneIfPinned(VM&);
872     PropertyTable* copyPropertyTableForPinning(VM&);
873
874     void setPreviousID(VM&, Structure*);
875     void clearPreviousID();
876
877     int transitionCountEstimate() const
878     {
879         // Since the number of transitions is often the same as the last offset (except if there are deletes)
880         // we keep the size of Structure down by not storing both.
881         return numberOfSlotsForMaxOffset(maxOffset(), inlineCapacity());
882     }
883
884     bool isValid(JSGlobalObject*, StructureChain* cachedPrototypeChain, JSObject* base) const;
885
886     // You have to hold the structure lock to do these.
887     JS_EXPORT_PRIVATE void pin(const AbstractLocker&, VM&, PropertyTable*);
888     void pinForCaching(const AbstractLocker&, VM&, PropertyTable*);
889     
890     bool isRareData(JSCell* cell) const
891     {
892         return cell && cell->type() == StructureRareDataType;
893     }
894
895     template<typename DetailsFunc>
896     bool checkOffsetConsistency(PropertyTable*, const DetailsFunc&) const;
897     bool checkOffsetConsistency() const;
898
899     JS_EXPORT_PRIVATE void allocateRareData(VM&);
900     
901     void startWatchingInternalProperties(VM&);
902
903     StructureChain* cachedPrototypeChain() const;
904     void setCachedPrototypeChain(VM&, StructureChain*);
905
906     void setOutOfLineTypeFlags(TypeInfo::OutOfLineTypeFlags);
907     void setClassInfo(const ClassInfo*);
908     void setInlineCapacity(uint8_t);
909
910     JSCell* cachedPrototypeChainOrRareData() const
911     {
912 #if CPU(ADDRESS64)
913         return m_inlineCapacityAndCachedPrototypeChainOrRareData.pointer();
914 #else
915         return m_cachedPrototypeChainOrRareData.get();
916 #endif
917     }
918
919     static constexpr int s_maxTransitionLength = 64;
920     static constexpr int s_maxTransitionLengthForNonEvalPutById = 512;
921
922     // These need to be properly aligned at the beginning of the 'Structure'
923     // part of the object.
924     StructureIDBlob m_blob;
925
926     // The property table pointer should be accessed through ensurePropertyTable(). During GC, m_propertyTableUnsafe field part may be set to 0 by another thread.
927     // During a Heap Snapshot GC we avoid clearing the table so it is safe to use.
928 #if CPU(ADDRESS64)
929 public:
930     static constexpr uintptr_t classInfoMask = CompactPointerTuple<const ClassInfo*, uint16_t>::pointerMask;
931     static constexpr uintptr_t cachedPrototypeChainOrRareDataMask = CompactPointerTuple<JSCell*, uint16_t>::pointerMask;
932 private:
933     // Structure is one of the most frequently allocated data structure. Moreover, Structure tends to be alive a long time!
934     // This motivates extra complicated hack which optimizes sizeof(Structure).
935     //
936     // We combine 16bit data and 64bit pointer into one pointer-size field to (1) save memory while (2) not losing atomic load/store.
937     // The key here is analyzing data access patterns carefully. They are categoriezed into three types.
938     //     1. ImmutableAfterConstruction
939     //     2. MutableFromAnyThread
940     //     3. MutableFromMainThread
941     //  We assume that loading happens from any threads. Under this assumption, MutableFromAnyThread + (MutableFromMainThread / MutableFromAnyThread) is the pair which is racy.
942     //  Other pairs works well. We carefully put assertions to setters, analyze access patterns and pick appropriate pairs in Structure fields.
943     CompactPointerTuple<PropertyTable*, TypeInfo::OutOfLineTypeFlags> m_outOfLineTypeFlagsAndPropertyTableUnsafe; // ImmutableAfterConstruction(m_outOfLineTypeFlags) and MutableFromAnyThread(m_propertyTableUnsafe).
944     CompactRefPtrTuple<UniquedStringImpl, uint16_t> m_maxOffsetAndTransitionPropertyName; // MutableFromMainThread(m_maxOffset) and MutableFromMainThread(m_transitionPropertyName).
945     CompactPointerTuple<const ClassInfo*, uint16_t> m_transitionOffsetAndClassInfo; // MutableFromMainThread(m_transitionOffset) and ImmutableAfterConstruction(m_classInfo).
946     CompactPointerTuple<JSCell*, uint16_t> m_inlineCapacityAndCachedPrototypeChainOrRareData; // ImmutableAfterConstruction(m_inlineCapacity) and MutableFromMainThread(m_cachedPrototypeChainOrRareData).
947     CompactPointerTuple<UniquedStringImpl*, uint16_t> m_propertyHashAndSeenProperties; // MutableFromMainThread(m_propertyHash) and MutableFromMainThread(m_seenProperties).
948 #else
949     TypeInfo::OutOfLineTypeFlags m_outOfLineTypeFlags { 0 };
950     uint8_t m_inlineCapacity { 0 };
951     uint32_t m_propertyHash { 0 };
952     uint16_t m_transitionOffset { 0 };
953     uint16_t m_maxOffset { 0 };
954     WriteBarrier<PropertyTable> m_propertyTableUnsafe;
955     const ClassInfo* m_classInfo { nullptr };
956     WriteBarrier<JSCell> m_cachedPrototypeChainOrRareData;
957     uintptr_t m_seenProperties { 0 };
958     RefPtr<UniquedStringImpl> m_transitionPropertyName;
959 #endif
960     StructureID m_previousID { 0 };
961     uint32_t m_bitField { 0 };
962
963     StructureTransitionTable m_transitionTable;
964     WriteBarrier<JSGlobalObject> m_globalObject;
965     WriteBarrier<Unknown> m_prototype;
966
967     mutable InlineWatchpointSet m_transitionWatchpointSet;
968
969     COMPILE_ASSERT(firstOutOfLineOffset < 256, firstOutOfLineOffset_fits);
970
971     friend class VMInspector;
972     friend class JSDollarVMHelper;
973 };
974 #if CPU(ADDRESS64)
975 static_assert(sizeof(Structure) <= 96, "Do not increase sizeof(Structure), it immediately causes memory regression");
976 #endif
977
978 } // namespace JSC