320a47a7b83459a2b8d97b21d4457a181aa28eef
[WebKit-https.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(bool& mustCheckCell) const;
536     
537     bool masqueradesAsUndefined(JSGlobalObject* lexicalGlobalObject);
538
539     PropertyOffset get(VM&, PropertyName);
540     PropertyOffset get(VM&, PropertyName, unsigned& attributes);
541
542     // This is a somewhat internalish method. It will call your functor while possibly holding the
543     // Structure's lock. There is no guarantee whether the lock is held or not in any particular
544     // call. So, you have to assume the worst. Also, the functor returns true if it wishes for you
545     // to continue or false if it's done.
546     template<typename Functor>
547     void forEachPropertyConcurrently(const Functor&);
548
549     template<typename Functor>
550     void forEachProperty(VM&, const Functor&);
551     
552     PropertyOffset getConcurrently(UniquedStringImpl* uid);
553     PropertyOffset getConcurrently(UniquedStringImpl* uid, unsigned& attributes);
554     
555     Vector<PropertyMapEntry> getPropertiesConcurrently();
556     
557     void setHasGetterSetterPropertiesWithProtoCheck(bool is__proto__)
558     {
559         setHasGetterSetterProperties(true);
560         if (!is__proto__)
561             setHasReadOnlyOrGetterSetterPropertiesExcludingProto(true);
562     }
563     
564     void setContainsReadOnlyProperties() { setHasReadOnlyOrGetterSetterPropertiesExcludingProto(true); }
565     
566     void setHasCustomGetterSetterPropertiesWithProtoCheck(bool is__proto__)
567     {
568         setHasCustomGetterSetterProperties(true);
569         if (!is__proto__)
570             setHasReadOnlyOrGetterSetterPropertiesExcludingProto(true);
571     }
572
573     void setCachedPropertyNameEnumerator(VM&, JSPropertyNameEnumerator*);
574     JSPropertyNameEnumerator* cachedPropertyNameEnumerator() const;
575     bool canCachePropertyNameEnumerator(VM&) const;
576     bool canAccessPropertiesQuicklyForEnumeration() const;
577
578     void setCachedOwnKeys(VM&, JSImmutableButterfly*);
579     JSImmutableButterfly* cachedOwnKeys() const;
580     JSImmutableButterfly* cachedOwnKeysIgnoringSentinel() const;
581     bool canCacheOwnKeys() const;
582
583     void getPropertyNamesFromStructure(VM&, PropertyNameArray&, EnumerationMode);
584
585     JSString* objectToStringValue()
586     {
587         if (!hasRareData())
588             return 0;
589         return rareData()->objectToStringValue();
590     }
591
592     void setObjectToStringValue(JSGlobalObject*, VM&, JSString* value, PropertySlot toStringTagSymbolSlot);
593
594     const ClassInfo* classInfo() const
595     {
596 #if CPU(ADDRESS64)
597         return m_transitionOffsetAndClassInfo.pointer();
598 #else
599         return m_classInfo;
600 #endif
601     }
602
603     static ptrdiff_t structureIDOffset()
604     {
605         return OBJECT_OFFSETOF(Structure, m_blob) + StructureIDBlob::structureIDOffset();
606     }
607
608     static ptrdiff_t prototypeOffset()
609     {
610         return OBJECT_OFFSETOF(Structure, m_prototype);
611     }
612
613     static ptrdiff_t globalObjectOffset()
614     {
615         return OBJECT_OFFSETOF(Structure, m_globalObject);
616     }
617
618     static ptrdiff_t offsetOfClassInfo()
619     {
620 #if CPU(ADDRESS64)
621         return OBJECT_OFFSETOF(Structure, m_transitionOffsetAndClassInfo);
622 #else
623         return OBJECT_OFFSETOF(Structure, m_classInfo);
624 #endif
625     }
626
627     static ptrdiff_t indexingModeIncludingHistoryOffset()
628     {
629         return OBJECT_OFFSETOF(Structure, m_blob) + StructureIDBlob::indexingModeIncludingHistoryOffset();
630     }
631
632 #if CPU(LITTLE_ENDIAN)
633     static ptrdiff_t offsetOfInlineCapacity()
634     {
635 #if CPU(ADDRESS64)
636         return OBJECT_OFFSETOF(Structure, m_inlineCapacityAndCachedPrototypeChainOrRareData) + CompactPointerTuple<JSCell*, uint16_t>::offsetOfType();
637 #else
638         return OBJECT_OFFSETOF(Structure, m_inlineCapacity);
639 #endif
640
641     }
642 #endif
643
644     static ptrdiff_t offsetOfCachedPrototypeChainOrRareData()
645     {
646 #if CPU(ADDRESS64)
647         return OBJECT_OFFSETOF(Structure, m_inlineCapacityAndCachedPrototypeChainOrRareData);
648 #else
649         return OBJECT_OFFSETOF(Structure, m_cachedPrototypeChainOrRareData);
650 #endif
651     }
652
653     static Structure* createStructure(VM&);
654         
655     bool transitionWatchpointSetHasBeenInvalidated() const
656     {
657         return m_transitionWatchpointSet.hasBeenInvalidated();
658     }
659         
660     bool transitionWatchpointSetIsStillValid() const
661     {
662         return m_transitionWatchpointSet.isStillValid();
663     }
664     
665     bool dfgShouldWatchIfPossible() const
666     {
667         // FIXME: We would like to not watch things that are unprofitable to watch, like
668         // dictionaries. Unfortunately, we can't do such things: a dictionary could get flattened,
669         // in which case it will start to appear watchable and so the DFG will think that it is
670         // watching it. We should come up with a comprehensive story for not watching things that
671         // aren't profitable to watch.
672         // https://bugs.webkit.org/show_bug.cgi?id=133625
673         
674         // - We don't watch Structures that either decided not to be watched, or whose predecessors
675         //   decided not to be watched. This happens when a transition is fired while being watched.
676         if (transitionWatchpointIsLikelyToBeFired())
677             return false;
678
679         // - Don't watch Structures that had been dictionaries.
680         if (hasBeenDictionary())
681             return false;
682         
683         return true;
684     }
685     
686     bool dfgShouldWatch() const
687     {
688         return dfgShouldWatchIfPossible() && transitionWatchpointSetIsStillValid();
689     }
690         
691     void addTransitionWatchpoint(Watchpoint* watchpoint) const
692     {
693         ASSERT(transitionWatchpointSetIsStillValid());
694         m_transitionWatchpointSet.add(watchpoint);
695     }
696     
697     void didTransitionFromThisStructure(DeferredStructureTransitionWatchpointFire* = nullptr) const;
698     
699     InlineWatchpointSet& transitionWatchpointSet() const
700     {
701         return m_transitionWatchpointSet;
702     }
703     
704     WatchpointSet* ensurePropertyReplacementWatchpointSet(VM&, PropertyOffset);
705     void startWatchingPropertyForReplacements(VM& vm, PropertyOffset offset)
706     {
707         ensurePropertyReplacementWatchpointSet(vm, offset);
708     }
709     void startWatchingPropertyForReplacements(VM&, PropertyName);
710     WatchpointSet* propertyReplacementWatchpointSet(PropertyOffset);
711     void didReplaceProperty(PropertyOffset);
712     void didCachePropertyReplacement(VM&, PropertyOffset);
713     
714     void startWatchingInternalPropertiesIfNecessary(VM& vm)
715     {
716         if (LIKELY(didWatchInternalProperties()))
717             return;
718         startWatchingInternalProperties(vm);
719     }
720     
721     Ref<StructureShape> toStructureShape(JSValue, bool& sawPolyProtoStructure);
722     
723     void dump(PrintStream&) const;
724     void dumpInContext(PrintStream&, DumpContext*) const;
725     void dumpBrief(PrintStream&, const CString&) const;
726     
727     static void dumpContextHeader(PrintStream&);
728     
729     static bool shouldConvertToPolyProto(const Structure* a, const Structure* b);
730
731     UniquedStringImpl* transitionPropertyName() const
732     {
733 #if CPU(ADDRESS64)
734         return m_maxOffsetAndTransitionPropertyName.pointer();
735 #else
736         return m_transitionPropertyName.get();
737 #endif
738     }
739
740     struct PropertyHashEntry {
741         const HashTable* table;
742         const HashTableValue* value;
743     };
744     Optional<PropertyHashEntry> findPropertyHashEntry(PropertyName) const;
745     
746     DECLARE_EXPORT_INFO;
747
748 private:
749     bool ruleOutUnseenProperty(UniquedStringImpl*) const;
750 #if CPU(ADDRESS64)
751     // As a propertyHash, 64bit environment uses 16bit property-hash + seenProperties set.
752     uintptr_t propertyHash() const { return m_propertyHashAndSeenProperties.data(); }
753 #else
754     uint32_t propertyHash() const { return m_propertyHash; }
755 #endif
756     TinyBloomFilter seenProperties() const;
757     void addPropertyHashAndSeenProperty(unsigned, UniquedStringImpl*);
758
759     void setTransitionPropertyName(const AbstractLocker&, UniquedStringImpl* transitionPropertyName)
760     {
761 #if CPU(ADDRESS64)
762         m_maxOffsetAndTransitionPropertyName.setPointer(transitionPropertyName);
763 #else
764         m_transitionPropertyName = transitionPropertyName;
765 #endif
766     }
767
768     typedef enum { 
769         NoneDictionaryKind = 0,
770         CachedDictionaryKind = 1,
771         UncachedDictionaryKind = 2
772     } DictionaryKind;
773
774 public:
775 #define DEFINE_BITFIELD(type, lowerName, upperName, width, offset) \
776     static constexpr uint32_t s_##lowerName##Shift = offset;\
777     static constexpr uint32_t s_##lowerName##Mask = ((1 << (width - 1)) | ((1 << (width - 1)) - 1));\
778     static constexpr uint32_t s_bitWidthOf##upperName = width;\
779     type lowerName() const { return static_cast<type>((m_bitField >> offset) & s_##lowerName##Mask); }\
780     void set##upperName(type newValue) \
781     {\
782         m_bitField &= ~(s_##lowerName##Mask << offset);\
783         m_bitField |= (newValue & s_##lowerName##Mask) << offset;\
784         ASSERT(newValue == lowerName());\
785     }
786
787     DEFINE_BITFIELD(DictionaryKind, dictionaryKind, DictionaryKind, 2, 0);
788     DEFINE_BITFIELD(bool, isPinnedPropertyTable, IsPinnedPropertyTable, 1, 2);
789     DEFINE_BITFIELD(bool, hasGetterSetterProperties, HasGetterSetterProperties, 1, 3);
790     DEFINE_BITFIELD(bool, hasReadOnlyOrGetterSetterPropertiesExcludingProto, HasReadOnlyOrGetterSetterPropertiesExcludingProto, 1, 4);
791     DEFINE_BITFIELD(bool, isQuickPropertyAccessAllowedForEnumeration, IsQuickPropertyAccessAllowedForEnumeration, 1, 5);
792     DEFINE_BITFIELD(unsigned, transitionPropertyAttributes, TransitionPropertyAttributes, 8, 6);
793     DEFINE_BITFIELD(bool, didPreventExtensions, DidPreventExtensions, 1, 14);
794     DEFINE_BITFIELD(bool, didTransition, DidTransition, 1, 15);
795     DEFINE_BITFIELD(bool, staticPropertiesReified, StaticPropertiesReified, 1, 16);
796     DEFINE_BITFIELD(bool, hasBeenFlattenedBefore, HasBeenFlattenedBefore, 1, 17);
797     DEFINE_BITFIELD(bool, hasCustomGetterSetterProperties, HasCustomGetterSetterProperties, 1, 18);
798     DEFINE_BITFIELD(bool, didWatchInternalProperties, DidWatchInternalProperties, 1, 19);
799     DEFINE_BITFIELD(bool, transitionWatchpointIsLikelyToBeFired, TransitionWatchpointIsLikelyToBeFired, 1, 20);
800     DEFINE_BITFIELD(bool, hasBeenDictionary, HasBeenDictionary, 1, 21);
801     DEFINE_BITFIELD(bool, protectPropertyTableWhileTransitioning, ProtectPropertyTableWhileTransitioning, 1, 22);
802     DEFINE_BITFIELD(bool, hasUnderscoreProtoPropertyExcludingOriginalProto, HasUnderscoreProtoPropertyExcludingOriginalProto, 1, 23);
803     DEFINE_BITFIELD(bool, isPropertyDeletionTransition, IsPropertyDeletionTransition, 1, 24);
804
805     static_assert(s_bitWidthOfTransitionPropertyAttributes <= sizeof(TransitionPropertyAttributes) * 8);
806
807 private:
808     friend class LLIntOffsetsExtractor;
809
810     JS_EXPORT_PRIVATE Structure(VM&, JSGlobalObject*, JSValue prototype, const TypeInfo&, const ClassInfo*, IndexingType, unsigned inlineCapacity);
811     Structure(VM&);
812     Structure(VM&, Structure*, DeferredStructureTransitionWatchpointFire*);
813
814     static Structure* create(VM&, Structure*, DeferredStructureTransitionWatchpointFire* = nullptr);
815     
816     static Structure* addPropertyTransitionToExistingStructureImpl(Structure*, UniquedStringImpl* uid, unsigned attributes, PropertyOffset&);
817     static Structure* removePropertyTransitionFromExistingStructureImpl(Structure*, PropertyName, unsigned attributes, PropertyOffset&);
818
819     // This will return the structure that has a usable property table, that property table,
820     // and the list of structures that we visited before we got to it. If it returns a
821     // non-null structure, it will also lock the structure that it returns; it is your job
822     // to unlock it.
823     void findStructuresAndMapForMaterialization(VM&, Vector<Structure*, 8>& structures, Structure*&, PropertyTable*&);
824     
825     static Structure* toDictionaryTransition(VM&, Structure*, DictionaryKind, DeferredStructureTransitionWatchpointFire* = nullptr);
826
827     enum class ShouldPin { No, Yes };
828     template<ShouldPin, typename Func>
829     PropertyOffset add(VM&, PropertyName, unsigned attributes, const Func&);
830     PropertyOffset add(VM&, PropertyName, unsigned attributes);
831     template<ShouldPin, typename Func>
832     PropertyOffset remove(VM&, PropertyName, const Func&);
833     PropertyOffset remove(VM&, PropertyName);
834
835     void checkConsistency();
836
837     // This may grab the lock, or not. Do not call when holding the Structure's lock.
838     PropertyTable* ensurePropertyTableIfNotEmpty(VM& vm)
839     {
840         if (PropertyTable* result = propertyTableUnsafeOrNull())
841             return result;
842         if (!previousID(vm))
843             return nullptr;
844         return materializePropertyTable(vm);
845     }
846     
847     // This may grab the lock, or not. Do not call when holding the Structure's lock.
848     PropertyTable* ensurePropertyTable(VM& vm)
849     {
850         if (PropertyTable* result = propertyTableUnsafeOrNull())
851             return result;
852         return materializePropertyTable(vm);
853     }
854     
855     PropertyTable* propertyTableUnsafeOrNull() const
856     {
857 #if CPU(ADDRESS64)
858         return m_outOfLineTypeFlagsAndPropertyTableUnsafe.pointer();
859 #else
860         return m_propertyTableUnsafe.get();
861 #endif
862     }
863     
864     // This will grab the lock. Do not call when holding the Structure's lock.
865     JS_EXPORT_PRIVATE PropertyTable* materializePropertyTable(VM&, bool setPropertyTable = true);
866     
867     void setPropertyTable(VM& vm, PropertyTable* table);
868     void clearPropertyTable();
869     
870     PropertyTable* takePropertyTableOrCloneIfPinned(VM&);
871     PropertyTable* copyPropertyTableForPinning(VM&);
872
873     void setPreviousID(VM&, Structure*);
874     void clearPreviousID();
875
876     int transitionCountEstimate() const
877     {
878         // Since the number of transitions is often the same as the last offset (except if there are deletes)
879         // we keep the size of Structure down by not storing both.
880         return numberOfSlotsForMaxOffset(maxOffset(), inlineCapacity());
881     }
882
883     bool isValid(JSGlobalObject*, StructureChain* cachedPrototypeChain, JSObject* base) const;
884
885     // You have to hold the structure lock to do these.
886     JS_EXPORT_PRIVATE void pin(const AbstractLocker&, VM&, PropertyTable*);
887     void pinForCaching(const AbstractLocker&, VM&, PropertyTable*);
888     
889     bool isRareData(JSCell* cell) const
890     {
891         return cell && cell->type() == StructureRareDataType;
892     }
893
894     template<typename DetailsFunc>
895     bool checkOffsetConsistency(PropertyTable*, const DetailsFunc&) const;
896     bool checkOffsetConsistency() const;
897
898     JS_EXPORT_PRIVATE void allocateRareData(VM&);
899     
900     void startWatchingInternalProperties(VM&);
901
902     StructureChain* cachedPrototypeChain() const;
903     void setCachedPrototypeChain(VM&, StructureChain*);
904
905     void setOutOfLineTypeFlags(TypeInfo::OutOfLineTypeFlags);
906     void setClassInfo(const ClassInfo*);
907     void setInlineCapacity(uint8_t);
908
909     JSCell* cachedPrototypeChainOrRareData() const
910     {
911 #if CPU(ADDRESS64)
912         return m_inlineCapacityAndCachedPrototypeChainOrRareData.pointer();
913 #else
914         return m_cachedPrototypeChainOrRareData.get();
915 #endif
916     }
917
918     static constexpr int s_maxTransitionLength = 64;
919     static constexpr int s_maxTransitionLengthForNonEvalPutById = 512;
920
921     // These need to be properly aligned at the beginning of the 'Structure'
922     // part of the object.
923     StructureIDBlob m_blob;
924
925     // The property table pointer should be accessed through ensurePropertyTable(). During GC, m_propertyTableUnsafe field part may be set to 0 by another thread.
926     // During a Heap Snapshot GC we avoid clearing the table so it is safe to use.
927 #if CPU(ADDRESS64)
928 public:
929     static constexpr uintptr_t classInfoMask = CompactPointerTuple<const ClassInfo*, uint16_t>::pointerMask;
930     static constexpr uintptr_t cachedPrototypeChainOrRareDataMask = CompactPointerTuple<JSCell*, uint16_t>::pointerMask;
931 private:
932     // Structure is one of the most frequently allocated data structure. Moreover, Structure tends to be alive a long time!
933     // This motivates extra complicated hack which optimizes sizeof(Structure).
934     //
935     // We combine 16bit data and 64bit pointer into one pointer-size field to (1) save memory while (2) not losing atomic load/store.
936     // The key here is analyzing data access patterns carefully. They are categoriezed into three types.
937     //     1. ImmutableAfterConstruction
938     //     2. MutableFromAnyThread
939     //     3. MutableFromMainThread
940     //  We assume that loading happens from any threads. Under this assumption, MutableFromAnyThread + (MutableFromMainThread / MutableFromAnyThread) is the pair which is racy.
941     //  Other pairs works well. We carefully put assertions to setters, analyze access patterns and pick appropriate pairs in Structure fields.
942     CompactPointerTuple<PropertyTable*, TypeInfo::OutOfLineTypeFlags> m_outOfLineTypeFlagsAndPropertyTableUnsafe; // ImmutableAfterConstruction(m_outOfLineTypeFlags) and MutableFromAnyThread(m_propertyTableUnsafe).
943     CompactRefPtrTuple<UniquedStringImpl, uint16_t> m_maxOffsetAndTransitionPropertyName; // MutableFromMainThread(m_maxOffset) and MutableFromMainThread(m_transitionPropertyName).
944     CompactPointerTuple<const ClassInfo*, uint16_t> m_transitionOffsetAndClassInfo; // MutableFromMainThread(m_transitionOffset) and ImmutableAfterConstruction(m_classInfo).
945     CompactPointerTuple<JSCell*, uint16_t> m_inlineCapacityAndCachedPrototypeChainOrRareData; // ImmutableAfterConstruction(m_inlineCapacity) and MutableFromMainThread(m_cachedPrototypeChainOrRareData).
946     CompactPointerTuple<UniquedStringImpl*, uint16_t> m_propertyHashAndSeenProperties; // MutableFromMainThread(m_propertyHash) and MutableFromMainThread(m_seenProperties).
947 #else
948     TypeInfo::OutOfLineTypeFlags m_outOfLineTypeFlags { 0 };
949     uint8_t m_inlineCapacity { 0 };
950     uint32_t m_propertyHash { 0 };
951     uint16_t m_transitionOffset { 0 };
952     uint16_t m_maxOffset { 0 };
953     WriteBarrier<PropertyTable> m_propertyTableUnsafe;
954     const ClassInfo* m_classInfo { nullptr };
955     WriteBarrier<JSCell> m_cachedPrototypeChainOrRareData;
956     uintptr_t m_seenProperties { 0 };
957     RefPtr<UniquedStringImpl> m_transitionPropertyName;
958 #endif
959     StructureID m_previousID { 0 };
960     uint32_t m_bitField { 0 };
961
962     StructureTransitionTable m_transitionTable;
963     WriteBarrier<JSGlobalObject> m_globalObject;
964     WriteBarrier<Unknown> m_prototype;
965
966     mutable InlineWatchpointSet m_transitionWatchpointSet;
967
968     COMPILE_ASSERT(firstOutOfLineOffset < 256, firstOutOfLineOffset_fits);
969
970     friend class VMInspector;
971     friend class JSDollarVMHelper;
972 };
973 #if CPU(ADDRESS64)
974 static_assert(sizeof(Structure) <= 96, "Do not increase sizeof(Structure), it immediately causes memory regression");
975 #endif
976
977 } // namespace JSC