832ce44abe4caaa6b742ff9ab0ec600c74764909
[WebKit.git] / Source / JavaScriptCore / runtime / Structure.cpp
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 #include "config.h"
27 #include "Structure.h"
28
29 #include "BuiltinNames.h"
30 #include "CodeBlock.h"
31 #include "DumpContext.h"
32 #include "JSCInlines.h"
33 #include "JSObject.h"
34 #include "JSPropertyNameEnumerator.h"
35 #include "Lookup.h"
36 #include "PropertyMapHashTable.h"
37 #include "PropertyNameArray.h"
38 #include "StructureChain.h"
39 #include "StructureRareDataInlines.h"
40 #include "WeakGCMapInlines.h"
41 #include <wtf/CommaPrinter.h>
42 #include <wtf/NeverDestroyed.h>
43 #include <wtf/ProcessID.h>
44 #include <wtf/RefPtr.h>
45 #include <wtf/Threading.h>
46
47 #define DUMP_STRUCTURE_ID_STATISTICS 0
48
49 namespace JSC {
50
51 #if DUMP_STRUCTURE_ID_STATISTICS
52 static HashSet<Structure*>& liveStructureSet = *(new HashSet<Structure*>);
53 #endif
54
55 class SingleSlotTransitionWeakOwner final : public WeakHandleOwner {
56     void finalize(Handle<Unknown>, void* context) override
57     {
58         StructureTransitionTable* table = reinterpret_cast<StructureTransitionTable*>(context);
59         ASSERT(table->isUsingSingleSlot());
60         WeakSet::deallocate(table->weakImpl());
61         table->m_data = StructureTransitionTable::UsingSingleSlotFlag;
62     }
63 };
64
65 static SingleSlotTransitionWeakOwner& singleSlotTransitionWeakOwner()
66 {
67     static NeverDestroyed<SingleSlotTransitionWeakOwner> owner;
68     return owner;
69 }
70
71 inline Structure* StructureTransitionTable::singleTransition() const
72 {
73     ASSERT(isUsingSingleSlot());
74     if (WeakImpl* impl = this->weakImpl()) {
75         if (impl->state() == WeakImpl::Live)
76             return jsCast<Structure*>(impl->jsValue().asCell());
77     }
78     return nullptr;
79 }
80
81 inline void StructureTransitionTable::setSingleTransition(Structure* structure)
82 {
83     ASSERT(isUsingSingleSlot());
84     if (WeakImpl* impl = this->weakImpl())
85         WeakSet::deallocate(impl);
86     WeakImpl* impl = WeakSet::allocate(structure, &singleSlotTransitionWeakOwner(), this);
87     m_data = bitwise_cast<intptr_t>(impl) | UsingSingleSlotFlag;
88 }
89
90 bool StructureTransitionTable::contains(UniquedStringImpl* rep, unsigned attributes, bool isAddition) const
91 {
92     if (isUsingSingleSlot()) {
93         Structure* transition = singleTransition();
94         return transition && transition->transitionPropertyName() == rep && transition->transitionPropertyAttributes() == attributes && transition->isPropertyDeletionTransition() == !isAddition;
95     }
96     return map()->get(StructureTransitionTable::Hash::Key(rep, attributes, isAddition));
97 }
98
99 inline Structure* StructureTransitionTable::get(UniquedStringImpl* rep, unsigned attributes, bool isAddition) const
100 {
101     if (isUsingSingleSlot()) {
102         Structure* transition = singleTransition();
103         return (transition && transition->transitionPropertyName() == rep && transition->transitionPropertyAttributes() == attributes && transition->isPropertyDeletionTransition() == !isAddition) ? transition : nullptr;
104     }
105     return map()->get(StructureTransitionTable::Hash::Key(rep, attributes, isAddition));
106 }
107
108 void StructureTransitionTable::add(VM& vm, Structure* structure)
109 {
110     if (isUsingSingleSlot()) {
111         Structure* existingTransition = singleTransition();
112
113         // This handles the first transition being added.
114         if (!existingTransition) {
115             setSingleTransition(structure);
116             return;
117         }
118
119         // This handles the second transition being added
120         // (or the first transition being despecified!)
121         setMap(new TransitionMap(vm));
122         add(vm, existingTransition);
123     }
124
125     // Add the structure to the map.
126     map()->set(StructureTransitionTable::Hash::Key(structure->transitionPropertyName(), structure->transitionPropertyAttributes(), !structure->isPropertyDeletionTransition()), structure);
127 }
128
129 void Structure::dumpStatistics()
130 {
131 #if DUMP_STRUCTURE_ID_STATISTICS
132     unsigned numberLeaf = 0;
133     unsigned numberUsingSingleSlot = 0;
134     unsigned numberSingletons = 0;
135     unsigned numberWithPropertyMaps = 0;
136     unsigned totalPropertyMapsSize = 0;
137
138     HashSet<Structure*>::const_iterator end = liveStructureSet.end();
139     for (HashSet<Structure*>::const_iterator it = liveStructureSet.begin(); it != end; ++it) {
140         Structure* structure = *it;
141
142         switch (structure->m_transitionTable.size()) {
143             case 0:
144                 ++numberLeaf;
145                 if (!structure->previousID(structure->vm()))
146                     ++numberSingletons;
147                 break;
148
149             case 1:
150                 ++numberUsingSingleSlot;
151                 break;
152         }
153
154         if (PropertyTable* table = structure->propertyTableUnsafeOrNull()) {
155             ++numberWithPropertyMaps;
156             totalPropertyMapsSize += table->sizeInMemory();
157         }
158     }
159
160     dataLogF("Number of live Structures: %d\n", liveStructureSet.size());
161     dataLogF("Number of Structures using the single item optimization for transition map: %d\n", numberUsingSingleSlot);
162     dataLogF("Number of Structures that are leaf nodes: %d\n", numberLeaf);
163     dataLogF("Number of Structures that singletons: %d\n", numberSingletons);
164     dataLogF("Number of Structures with PropertyMaps: %d\n", numberWithPropertyMaps);
165
166     dataLogF("Size of a single Structures: %d\n", static_cast<unsigned>(sizeof(Structure)));
167     dataLogF("Size of sum of all property maps: %d\n", totalPropertyMapsSize);
168     dataLogF("Size of average of all property maps: %f\n", static_cast<double>(totalPropertyMapsSize) / static_cast<double>(liveStructureSet.size()));
169 #else
170     dataLogF("Dumping Structure statistics is not enabled.\n");
171 #endif
172 }
173
174 Structure::Structure(VM& vm, JSGlobalObject* globalObject, JSValue prototype, const TypeInfo& typeInfo, const ClassInfo* classInfo, IndexingType indexingType, unsigned inlineCapacity)
175     : JSCell(vm, vm.structureStructure.get())
176     , m_blob(vm.heap.structureIDTable().allocateID(this), indexingType, typeInfo)
177     , m_globalObject(vm, this, globalObject, WriteBarrier<JSGlobalObject>::MayBeNull)
178     , m_prototype(vm, this, prototype)
179     , m_transitionWatchpointSet(IsWatched)
180 {
181     setInlineCapacity(inlineCapacity);
182     setClassInfo(classInfo);
183     setDictionaryKind(NoneDictionaryKind);
184     setIsPinnedPropertyTable(false);
185     setHasGetterSetterProperties(classInfo->hasStaticSetterOrReadonlyProperties());
186     setHasCustomGetterSetterProperties(false);
187     setHasReadOnlyOrGetterSetterPropertiesExcludingProto(classInfo->hasStaticSetterOrReadonlyProperties());
188     setHasUnderscoreProtoPropertyExcludingOriginalProto(false);
189     setIsQuickPropertyAccessAllowedForEnumeration(true);
190     setTransitionPropertyAttributes(0);
191     setDidPreventExtensions(false);
192     setDidTransition(false);
193     setStaticPropertiesReified(false);
194     setTransitionWatchpointIsLikelyToBeFired(false);
195     setHasBeenDictionary(false);
196     setProtectPropertyTableWhileTransitioning(false);
197     setIsPropertyDeletionTransition(false);
198     setTransitionOffset(vm, invalidOffset);
199     setMaxOffset(vm, invalidOffset);
200     setOutOfLineTypeFlags(typeInfo.outOfLineTypeFlags());
201
202     ASSERT(inlineCapacity <= JSFinalObject::maxInlineCapacity());
203     ASSERT(static_cast<PropertyOffset>(inlineCapacity) < firstOutOfLineOffset);
204     ASSERT(!hasRareData());
205     ASSERT(hasReadOnlyOrGetterSetterPropertiesExcludingProto() || !this->classInfo()->hasStaticSetterOrReadonlyProperties());
206     ASSERT(hasGetterSetterProperties() || !this->classInfo()->hasStaticSetterOrReadonlyProperties());
207     ASSERT(!this->typeInfo().overridesGetCallData() || this->classInfo()->methodTable.getCallData != &JSCell::getCallData);
208 }
209
210 const ClassInfo Structure::s_info = { "Structure", nullptr, nullptr, nullptr, CREATE_METHOD_TABLE(Structure) };
211
212 Structure::Structure(VM& vm)
213     : JSCell(CreatingEarlyCell)
214     , m_prototype(vm, this, jsNull())
215     , m_transitionWatchpointSet(IsWatched)
216 {
217     setInlineCapacity(0);
218     setClassInfo(info());
219     setDictionaryKind(NoneDictionaryKind);
220     setIsPinnedPropertyTable(false);
221     setHasGetterSetterProperties(classInfo()->hasStaticSetterOrReadonlyProperties());
222     setHasCustomGetterSetterProperties(false);
223     setHasReadOnlyOrGetterSetterPropertiesExcludingProto(classInfo()->hasStaticSetterOrReadonlyProperties());
224     setHasUnderscoreProtoPropertyExcludingOriginalProto(false);
225     setIsQuickPropertyAccessAllowedForEnumeration(true);
226     setTransitionPropertyAttributes(0);
227     setDidPreventExtensions(false);
228     setDidTransition(false);
229     setStaticPropertiesReified(false);
230     setTransitionWatchpointIsLikelyToBeFired(false);
231     setHasBeenDictionary(false);
232     setProtectPropertyTableWhileTransitioning(false);
233     setIsPropertyDeletionTransition(false);
234     setTransitionOffset(vm, invalidOffset);
235     setMaxOffset(vm, invalidOffset);
236  
237     TypeInfo typeInfo = TypeInfo(CellType, StructureFlags);
238     m_blob = StructureIDBlob(vm.heap.structureIDTable().allocateID(this), 0, typeInfo);
239     setOutOfLineTypeFlags(typeInfo.outOfLineTypeFlags());
240
241     ASSERT(hasReadOnlyOrGetterSetterPropertiesExcludingProto() || !classInfo()->hasStaticSetterOrReadonlyProperties());
242     ASSERT(hasGetterSetterProperties() || !classInfo()->hasStaticSetterOrReadonlyProperties());
243     ASSERT(!this->typeInfo().overridesGetCallData() || classInfo()->methodTable.getCallData != &JSCell::getCallData);
244 }
245
246 Structure::Structure(VM& vm, Structure* previous, DeferredStructureTransitionWatchpointFire* deferred)
247     : JSCell(vm, vm.structureStructure.get())
248 #if CPU(ADDRESS64)
249     , m_propertyHashAndSeenProperties(previous->m_propertyHashAndSeenProperties)
250 #else
251     , m_propertyHash(previous->m_propertyHash)
252     , m_seenProperties(previous->m_seenProperties)
253 #endif
254     , m_prototype(vm, this, previous->m_prototype.get())
255     , m_transitionWatchpointSet(IsWatched)
256 {
257     setInlineCapacity(previous->inlineCapacity());
258     setClassInfo(previous->classInfo());
259     setDictionaryKind(previous->dictionaryKind());
260     setIsPinnedPropertyTable(false);
261     setHasBeenFlattenedBefore(previous->hasBeenFlattenedBefore());
262     setHasGetterSetterProperties(previous->hasGetterSetterProperties());
263     setHasCustomGetterSetterProperties(previous->hasCustomGetterSetterProperties());
264     setHasReadOnlyOrGetterSetterPropertiesExcludingProto(previous->hasReadOnlyOrGetterSetterPropertiesExcludingProto());
265     setHasUnderscoreProtoPropertyExcludingOriginalProto(previous->hasUnderscoreProtoPropertyExcludingOriginalProto());
266     setIsQuickPropertyAccessAllowedForEnumeration(previous->isQuickPropertyAccessAllowedForEnumeration());
267     setTransitionPropertyAttributes(0);
268     setDidPreventExtensions(previous->didPreventExtensions());
269     setDidTransition(true);
270     setStaticPropertiesReified(previous->staticPropertiesReified());
271     setHasBeenDictionary(previous->hasBeenDictionary());
272     setProtectPropertyTableWhileTransitioning(false);
273     setIsPropertyDeletionTransition(false);
274     setTransitionOffset(vm, invalidOffset);
275     setMaxOffset(vm, invalidOffset);
276  
277     TypeInfo typeInfo = previous->typeInfo();
278     m_blob = StructureIDBlob(vm.heap.structureIDTable().allocateID(this), previous->indexingModeIncludingHistory(), typeInfo);
279     setOutOfLineTypeFlags(typeInfo.outOfLineTypeFlags());
280
281     ASSERT(!previous->typeInfo().structureIsImmortal());
282     setPreviousID(vm, previous);
283
284     previous->didTransitionFromThisStructure(deferred);
285     
286     // Copy this bit now, in case previous was being watched.
287     setTransitionWatchpointIsLikelyToBeFired(previous->transitionWatchpointIsLikelyToBeFired());
288
289     if (previous->m_globalObject)
290         m_globalObject.set(vm, this, previous->m_globalObject.get());
291     ASSERT(hasReadOnlyOrGetterSetterPropertiesExcludingProto() || !classInfo()->hasStaticSetterOrReadonlyProperties());
292     ASSERT(hasGetterSetterProperties() || !classInfo()->hasStaticSetterOrReadonlyProperties());
293     ASSERT(!this->typeInfo().overridesGetCallData() || classInfo()->methodTable.getCallData != &JSCell::getCallData);
294 }
295
296 Structure::~Structure()
297 {
298     if (typeInfo().structureIsImmortal())
299         return;
300     Heap::heap(this)->structureIDTable().deallocateID(this, m_blob.structureID());
301 }
302
303 void Structure::destroy(JSCell* cell)
304 {
305     static_cast<Structure*>(cell)->Structure::~Structure();
306 }
307
308 Structure* Structure::create(PolyProtoTag, VM& vm, JSGlobalObject* globalObject, JSObject* prototype, const TypeInfo& typeInfo, const ClassInfo* classInfo, IndexingType indexingType, unsigned inlineCapacity)
309 {
310     Structure* result = create(vm, globalObject, prototype, typeInfo, classInfo, indexingType, inlineCapacity);
311
312     unsigned oldOutOfLineCapacity = result->outOfLineCapacity();
313     result->addPropertyWithoutTransition(
314         vm, vm.propertyNames->builtinNames().polyProtoName(), static_cast<unsigned>(PropertyAttribute::DontEnum),
315         [&](const GCSafeConcurrentJSCellLocker&, PropertyOffset offset, PropertyOffset newMaxOffset) {
316             RELEASE_ASSERT(Structure::outOfLineCapacity(newMaxOffset) == oldOutOfLineCapacity);
317             RELEASE_ASSERT(offset == knownPolyProtoOffset);
318             RELEASE_ASSERT(isInlineOffset(knownPolyProtoOffset));
319             result->m_prototype.setWithoutWriteBarrier(JSValue());
320             result->setMaxOffset(vm, newMaxOffset);
321         });
322
323     return result;
324 }
325
326 bool Structure::isValidPrototype(JSValue prototype)
327 {
328     return prototype.isNull() || (prototype.isObject() && prototype.getObject()->mayBePrototype());
329 }
330
331 void Structure::findStructuresAndMapForMaterialization(VM& vm, Vector<Structure*, 8>& structures, Structure*& structure, PropertyTable*& table)
332 {
333     ASSERT(structures.isEmpty());
334     table = nullptr;
335
336     for (structure = this; structure; structure = structure->previousID(vm)) {
337         structure->cellLock().lock();
338         
339         table = structure->propertyTableUnsafeOrNull();
340         if (table) {
341             // Leave the structure locked, so that the caller can do things to it atomically
342             // before it loses its property table.
343             return;
344         }
345         
346         structures.append(structure);
347         structure->cellLock().unlock();
348     }
349     
350     ASSERT(!structure);
351     ASSERT(!table);
352 }
353
354 PropertyTable* Structure::materializePropertyTable(VM& vm, bool setPropertyTable)
355 {
356     ASSERT(structure(vm)->classInfo() == info());
357     ASSERT(!protectPropertyTableWhileTransitioning());
358     
359     DeferGC deferGC(vm.heap);
360     
361     Vector<Structure*, 8> structures;
362     Structure* structure;
363     PropertyTable* table;
364     
365     findStructuresAndMapForMaterialization(vm, structures, structure, table);
366     
367     unsigned capacity = numberOfSlotsForMaxOffset(maxOffset(), inlineCapacity());
368     if (table) {
369         table = table->copy(vm, capacity);
370         structure->cellLock().unlock();
371     } else
372         table = PropertyTable::create(vm, capacity);
373     
374     // Must hold the lock on this structure, since we will be modifying this structure's
375     // property map. We don't want getConcurrently() to see the property map in a half-baked
376     // state.
377     GCSafeConcurrentJSCellLocker locker(cellLock(), vm.heap);
378     if (setPropertyTable)
379         this->setPropertyTable(vm, table);
380
381     for (size_t i = structures.size(); i--;) {
382         structure = structures[i];
383         UniquedStringImpl* transitionPropertyName = structure->transitionPropertyName();
384         if (!transitionPropertyName)
385             continue;
386         if (structure->isPropertyDeletionTransition()) {
387             auto item = table->find(transitionPropertyName);
388             ASSERT(item.first);
389             table->remove(item);
390             table->addDeletedOffset(structure->transitionOffset());
391             continue;
392         }
393         PropertyMapEntry entry(transitionPropertyName, structure->transitionOffset(), structure->transitionPropertyAttributes());
394         auto nextOffset = table->nextOffset(structure->inlineCapacity());
395         ASSERT_UNUSED(nextOffset, nextOffset == structure->transitionOffset());
396         auto result = table->add(entry);
397         ASSERT_UNUSED(result, result.second);
398         ASSERT_UNUSED(result, result.first.first->offset == nextOffset);
399     }
400     
401     checkOffsetConsistency(
402         table,
403         [&] () {
404             dataLog("Detected in materializePropertyTable.\n");
405             dataLog("Found structure = ", RawPointer(structure), "\n");
406             dataLog("structures = ");
407             CommaPrinter comma;
408             for (Structure* structure : structures)
409                 dataLog(comma, RawPointer(structure));
410             dataLog("\n");
411         });
412     
413     return table;
414 }
415
416 Structure* Structure::addPropertyTransitionToExistingStructureImpl(Structure* structure, UniquedStringImpl* uid, unsigned attributes, PropertyOffset& offset)
417 {
418     ASSERT(!structure->isDictionary());
419     ASSERT(structure->isObject());
420
421     constexpr bool isAddition = true;
422     if (Structure* existingTransition = structure->m_transitionTable.get(uid, attributes, isAddition)) {
423         validateOffset(existingTransition->transitionOffset(), existingTransition->inlineCapacity());
424         offset = existingTransition->transitionOffset();
425         return existingTransition;
426     }
427
428     return nullptr;
429 }
430
431 Structure* Structure::addPropertyTransitionToExistingStructure(Structure* structure, PropertyName propertyName, unsigned attributes, PropertyOffset& offset)
432 {
433     ASSERT(!isCompilationThread());
434     return addPropertyTransitionToExistingStructureImpl(structure, propertyName.uid(), attributes, offset);
435 }
436
437 Structure* Structure::addPropertyTransitionToExistingStructureConcurrently(Structure* structure, UniquedStringImpl* uid, unsigned attributes, PropertyOffset& offset)
438 {
439     ConcurrentJSCellLocker locker(structure->cellLock());
440     return addPropertyTransitionToExistingStructureImpl(structure, uid, attributes, offset);
441 }
442
443 bool Structure::holesMustForwardToPrototype(VM& vm, JSObject* base) const
444 {
445     ASSERT(base->structure(vm) == this);
446
447     if (this->mayInterceptIndexedAccesses())
448         return true;
449
450     JSValue prototype = this->storedPrototype(base);
451     if (!prototype.isObject())
452         return false;
453     JSObject* object = asObject(prototype);
454
455     while (true) {
456         Structure& structure = *object->structure(vm);
457         if (hasIndexedProperties(object->indexingType()) || structure.mayInterceptIndexedAccesses())
458             return true;
459         prototype = structure.storedPrototype(object);
460         if (!prototype.isObject())
461             return false;
462         object = asObject(prototype);
463     }
464
465     RELEASE_ASSERT_NOT_REACHED();
466     return false;
467 }
468
469 Structure* Structure::addPropertyTransition(VM& vm, Structure* structure, PropertyName propertyName, unsigned attributes, PropertyOffset& offset)
470 {
471     Structure* newStructure = addPropertyTransitionToExistingStructure(
472         structure, propertyName, attributes, offset);
473     if (newStructure)
474         return newStructure;
475
476     return addNewPropertyTransition(
477         vm, structure, propertyName, attributes, offset, PutPropertySlot::UnknownContext);
478 }
479
480 Structure* Structure::addNewPropertyTransition(VM& vm, Structure* structure, PropertyName propertyName, unsigned attributes, PropertyOffset& offset, PutPropertySlot::Context context, DeferredStructureTransitionWatchpointFire* deferred)
481 {
482     ASSERT(!structure->isDictionary());
483     ASSERT(structure->isObject());
484     ASSERT(!Structure::addPropertyTransitionToExistingStructure(structure, propertyName, attributes, offset));
485     
486     int maxTransitionLength;
487     if (context == PutPropertySlot::PutById)
488         maxTransitionLength = s_maxTransitionLengthForNonEvalPutById;
489     else
490         maxTransitionLength = s_maxTransitionLength;
491     if (structure->transitionCountEstimate() > maxTransitionLength) {
492         ASSERT(!isCopyOnWrite(structure->indexingMode()));
493         Structure* transition = toCacheableDictionaryTransition(vm, structure, deferred);
494         ASSERT(structure != transition);
495         offset = transition->add(vm, propertyName, attributes);
496         return transition;
497     }
498     
499     Structure* transition = create(vm, structure, deferred);
500     transition->setCachedPrototypeChain(vm, structure->cachedPrototypeChain());
501     
502     // While we are adding the property, rematerializing the property table is super weird: we already
503     // have a m_transitionPropertyName and transitionPropertyAttributes but the m_transitionOffset is still wrong. If the
504     // materialization algorithm runs, it'll build a property table that already has the property but
505     // at a bogus offset. Rather than try to teach the materialization code how to create a table under
506     // those conditions, we just tell the GC not to blow the table away during this period of time.
507     // Holding the lock ensures that we either do this before the GC starts scanning the structure, in
508     // which case the GC will not blow the table away, or we do it after the GC already ran in which
509     // case all is well.  If it wasn't for the lock, the GC would have TOCTOU: if could read
510     // protectPropertyTableWhileTransitioning before we set it to true, and then blow the table away after.
511     {
512         ConcurrentJSCellLocker locker(transition->cellLock());
513         transition->setProtectPropertyTableWhileTransitioning(true);
514         transition->setTransitionPropertyName(locker, propertyName.uid());
515     }
516
517     transition->m_blob.setIndexingModeIncludingHistory(structure->indexingModeIncludingHistory() & ~CopyOnWrite);
518     transition->setTransitionPropertyAttributes(attributes);
519     transition->setPropertyTable(vm, structure->takePropertyTableOrCloneIfPinned(vm));
520     transition->setMaxOffset(vm, structure->maxOffset());
521
522     offset = transition->add(vm, propertyName, attributes);
523     transition->setTransitionOffset(vm, offset);
524
525     // Now that everything is fine with the new structure's bookkeeping, the GC is free to blow the
526     // table away if it wants. We can now rebuild it fine.
527     WTF::storeStoreFence();
528     transition->setProtectPropertyTableWhileTransitioning(false);
529
530     checkOffset(transition->transitionOffset(), transition->inlineCapacity());
531     {
532         GCSafeConcurrentJSCellLocker locker(structure->cellLock(), vm.heap);
533         structure->m_transitionTable.add(vm, transition);
534     }
535     transition->checkOffsetConsistency();
536     structure->checkOffsetConsistency();
537     return transition;
538 }
539
540 Structure* Structure::removePropertyTransition(VM& vm, Structure* structure, PropertyName propertyName, PropertyOffset& offset, DeferredStructureTransitionWatchpointFire* deferred)
541 {
542     Structure* newStructure = removePropertyTransitionFromExistingStructure(structure, propertyName, offset);
543     if (newStructure)
544         return newStructure;
545
546     return removeNewPropertyTransition(
547         vm, structure, propertyName, offset, deferred);
548 }
549
550 Structure* Structure::removePropertyTransitionFromExistingStructureImpl(Structure* structure, PropertyName propertyName, unsigned attributes, PropertyOffset& offset)
551 {
552     ASSERT(!structure->isUncacheableDictionary());
553     ASSERT(structure->isObject());
554
555     constexpr bool isAddition = false;
556     offset = invalidOffset;
557     if (Structure* existingTransition = structure->m_transitionTable.get(propertyName.uid(), attributes, isAddition)) {
558         validateOffset(existingTransition->transitionOffset(), existingTransition->inlineCapacity());
559         offset = existingTransition->transitionOffset();
560         return existingTransition;
561     }
562
563     return nullptr;
564 }
565
566 Structure* Structure::removePropertyTransitionFromExistingStructure(Structure* structure, PropertyName propertyName, PropertyOffset& offset)
567 {
568     ASSERT(!isCompilationThread());
569     unsigned attributes = 0;
570     if (structure->getConcurrently(propertyName.uid(), attributes) == invalidOffset)
571         return nullptr;
572     return removePropertyTransitionFromExistingStructureImpl(structure, propertyName, attributes, offset);
573 }
574
575 Structure* Structure::removePropertyTransitionFromExistingStructureConcurrently(Structure* structure, PropertyName propertyName, PropertyOffset& offset)
576 {
577     unsigned attributes = 0;
578     if (structure->getConcurrently(propertyName.uid(), attributes) == invalidOffset)
579         return nullptr;
580     ConcurrentJSCellLocker locker(structure->cellLock());
581     return removePropertyTransitionFromExistingStructureImpl(structure, propertyName, attributes, offset);
582 }
583
584 Structure* Structure::removeNewPropertyTransition(VM& vm, Structure* structure, PropertyName propertyName, PropertyOffset& offset, DeferredStructureTransitionWatchpointFire* deferred)
585 {
586     ASSERT(!isCompilationThread());
587     ASSERT(!structure->isUncacheableDictionary());
588     ASSERT(structure->isObject());
589     ASSERT(!Structure::removePropertyTransitionFromExistingStructure(structure, propertyName, offset));
590     ASSERT(structure->getConcurrently(propertyName.uid()) != invalidOffset);
591
592     int transitionCount = 0;
593     for (auto* s = structure; s && transitionCount <= s_maxTransitionLength; s = s->previousID(vm))
594         ++transitionCount;
595
596     if (transitionCount > s_maxTransitionLength) {
597         ASSERT(!isCopyOnWrite(structure->indexingMode()));
598         Structure* transition = toUncacheableDictionaryTransition(vm, structure, deferred);
599         ASSERT(structure != transition);
600         offset = transition->remove(vm, propertyName);
601         return transition;
602     }
603
604     Structure* transition = create(vm, structure, deferred);
605     transition->setCachedPrototypeChain(vm, structure->cachedPrototypeChain());
606
607     // While we are deleting the property, we need to make sure the table is not cleared.
608     {
609         ConcurrentJSCellLocker locker(transition->cellLock());
610         transition->setProtectPropertyTableWhileTransitioning(true);
611         transition->setTransitionPropertyName(locker, propertyName.uid());
612     }
613
614     transition->m_blob.setIndexingModeIncludingHistory(structure->indexingModeIncludingHistory() & ~CopyOnWrite);
615     transition->setPropertyTable(vm, structure->takePropertyTableOrCloneIfPinned(vm));
616     transition->setMaxOffset(vm, structure->maxOffset());
617     transition->setIsPropertyDeletionTransition(true);
618
619     offset = transition->remove(vm, propertyName);
620     ASSERT(offset != invalidOffset);
621     transition->setTransitionOffset(vm, offset);
622
623     // Now that everything is fine with the new structure's bookkeeping, the GC is free to blow the
624     // table away if it wants. We can now rebuild it fine.
625     WTF::storeStoreFence();
626     transition->setProtectPropertyTableWhileTransitioning(false);
627
628     checkOffset(transition->transitionOffset(), transition->inlineCapacity());
629     {
630         GCSafeConcurrentJSCellLocker locker(structure->cellLock(), vm.heap);
631         structure->m_transitionTable.add(vm, transition);
632     }
633     transition->checkOffsetConsistency();
634     structure->checkOffsetConsistency();
635     return transition;
636 }
637
638 Structure* Structure::changePrototypeTransition(VM& vm, Structure* structure, JSValue prototype, DeferredStructureTransitionWatchpointFire& deferred)
639 {
640     ASSERT(isValidPrototype(prototype));
641
642     DeferGC deferGC(vm.heap);
643     Structure* transition = create(vm, structure, &deferred);
644
645     transition->m_prototype.set(vm, transition, prototype);
646
647     PropertyTable* table = structure->copyPropertyTableForPinning(vm);
648     transition->pin(holdLock(transition->cellLock()), vm, table);
649     transition->setMaxOffset(vm, structure->maxOffset());
650     
651     transition->checkOffsetConsistency();
652     return transition;
653 }
654
655 Structure* Structure::attributeChangeTransition(VM& vm, Structure* structure, PropertyName propertyName, unsigned attributes)
656 {
657     if (!structure->isUncacheableDictionary()) {
658         Structure* transition = create(vm, structure);
659
660         PropertyTable* table = structure->copyPropertyTableForPinning(vm);
661         transition->pin(holdLock(transition->cellLock()), vm, table);
662         transition->setMaxOffset(vm, structure->maxOffset());
663         
664         structure = transition;
665     }
666
667     PropertyMapEntry* entry = structure->ensurePropertyTable(vm)->get(propertyName.uid());
668     ASSERT(entry);
669     entry->attributes = attributes;
670
671     structure->checkOffsetConsistency();
672     return structure;
673 }
674
675 Structure* Structure::toDictionaryTransition(VM& vm, Structure* structure, DictionaryKind kind, DeferredStructureTransitionWatchpointFire* deferred)
676 {
677     ASSERT(!structure->isUncacheableDictionary());
678     DeferGC deferGC(vm.heap);
679     
680     Structure* transition = create(vm, structure, deferred);
681
682     PropertyTable* table = structure->copyPropertyTableForPinning(vm);
683     transition->pin(holdLock(transition->cellLock()), vm, table);
684     transition->setMaxOffset(vm, structure->maxOffset());
685     transition->setDictionaryKind(kind);
686     transition->setHasBeenDictionary(true);
687     
688     transition->checkOffsetConsistency();
689     return transition;
690 }
691
692 Structure* Structure::toCacheableDictionaryTransition(VM& vm, Structure* structure, DeferredStructureTransitionWatchpointFire* deferred)
693 {
694     return toDictionaryTransition(vm, structure, CachedDictionaryKind, deferred);
695 }
696
697 Structure* Structure::toUncacheableDictionaryTransition(VM& vm, Structure* structure, DeferredStructureTransitionWatchpointFire* deferred)
698 {
699     return toDictionaryTransition(vm, structure, UncachedDictionaryKind, deferred);
700 }
701
702 Structure* Structure::sealTransition(VM& vm, Structure* structure)
703 {
704     return nonPropertyTransition(vm, structure, NonPropertyTransition::Seal);
705 }
706
707 Structure* Structure::freezeTransition(VM& vm, Structure* structure)
708 {
709     return nonPropertyTransition(vm, structure, NonPropertyTransition::Freeze);
710 }
711
712 Structure* Structure::preventExtensionsTransition(VM& vm, Structure* structure)
713 {
714     return nonPropertyTransition(vm, structure, NonPropertyTransition::PreventExtensions);
715 }
716
717 PropertyTable* Structure::takePropertyTableOrCloneIfPinned(VM& vm)
718 {
719     // This function must always return a property table. It can't return null.
720     PropertyTable* result = propertyTableUnsafeOrNull();
721     if (result) {
722         if (isPinnedPropertyTable())
723             return result->copy(vm, result->size() + 1);
724         ConcurrentJSCellLocker locker(cellLock());
725         setPropertyTable(vm, nullptr);
726         return result;
727     }
728     bool setPropertyTable = false;
729     return materializePropertyTable(vm, setPropertyTable);
730 }
731
732 Structure* Structure::nonPropertyTransitionSlow(VM& vm, Structure* structure, NonPropertyTransition transitionKind)
733 {
734     unsigned attributes = toAttributes(transitionKind);
735     IndexingType indexingModeIncludingHistory = newIndexingType(structure->indexingModeIncludingHistory(), transitionKind);
736     
737     Structure* existingTransition;
738     constexpr bool isAddition = true;
739     if (!structure->isDictionary() && (existingTransition = structure->m_transitionTable.get(0, attributes, isAddition))) {
740         ASSERT(existingTransition->transitionPropertyAttributes() == attributes);
741         ASSERT(existingTransition->indexingModeIncludingHistory() == indexingModeIncludingHistory);
742         return existingTransition;
743     }
744     
745     DeferGC deferGC(vm.heap);
746     
747     Structure* transition = create(vm, structure);
748     transition->setTransitionPropertyAttributes(attributes);
749     transition->m_blob.setIndexingModeIncludingHistory(indexingModeIncludingHistory);
750     
751     if (preventsExtensions(transitionKind))
752         transition->setDidPreventExtensions(true);
753     
754     if (setsDontDeleteOnAllProperties(transitionKind)
755         || setsReadOnlyOnNonAccessorProperties(transitionKind)) {
756         // We pin the property table on transitions that do wholesale editing of the property
757         // table, since our logic for walking the property transition chain to rematerialize the
758         // table doesn't know how to take into account such wholesale edits.
759
760         PropertyTable* table = structure->copyPropertyTableForPinning(vm);
761         transition->pinForCaching(holdLock(transition->cellLock()), vm, table);
762         transition->setMaxOffset(vm, structure->maxOffset());
763         
764         table = transition->propertyTableUnsafeOrNull();
765         RELEASE_ASSERT(table);
766         for (auto& entry : *table) {
767             if (setsDontDeleteOnAllProperties(transitionKind))
768                 entry.attributes |= static_cast<unsigned>(PropertyAttribute::DontDelete);
769             if (setsReadOnlyOnNonAccessorProperties(transitionKind) && !(entry.attributes & PropertyAttribute::Accessor))
770                 entry.attributes |= static_cast<unsigned>(PropertyAttribute::ReadOnly);
771         }
772     } else {
773         transition->setPropertyTable(vm, structure->takePropertyTableOrCloneIfPinned(vm));
774         transition->setMaxOffset(vm, structure->maxOffset());
775         checkOffset(transition->maxOffset(), transition->inlineCapacity());
776     }
777     
778     if (setsReadOnlyOnNonAccessorProperties(transitionKind)
779         && !transition->propertyTableUnsafeOrNull()->isEmpty())
780         transition->setHasReadOnlyOrGetterSetterPropertiesExcludingProto(true);
781     
782     if (structure->isDictionary()) {
783         PropertyTable* table = transition->ensurePropertyTable(vm);
784         transition->pin(holdLock(transition->cellLock()), vm, table);
785     } else {
786         auto locker = holdLock(structure->cellLock());
787         structure->m_transitionTable.add(vm, transition);
788     }
789
790     transition->checkOffsetConsistency();
791     return transition;
792 }
793
794 // In future we may want to cache this property.
795 bool Structure::isSealed(VM& vm)
796 {
797     if (isStructureExtensible())
798         return false;
799
800     PropertyTable* table = ensurePropertyTableIfNotEmpty(vm);
801     if (!table)
802         return true;
803     
804     PropertyTable::iterator end = table->end();
805     for (PropertyTable::iterator iter = table->begin(); iter != end; ++iter) {
806         if ((iter->attributes & PropertyAttribute::DontDelete) != static_cast<unsigned>(PropertyAttribute::DontDelete))
807             return false;
808     }
809     return true;
810 }
811
812 // In future we may want to cache this property.
813 bool Structure::isFrozen(VM& vm)
814 {
815     if (isStructureExtensible())
816         return false;
817
818     PropertyTable* table = ensurePropertyTableIfNotEmpty(vm);
819     if (!table)
820         return true;
821     
822     PropertyTable::iterator end = table->end();
823     for (PropertyTable::iterator iter = table->begin(); iter != end; ++iter) {
824         if (!(iter->attributes & PropertyAttribute::DontDelete))
825             return false;
826         if (!(iter->attributes & (PropertyAttribute::ReadOnly | PropertyAttribute::Accessor)))
827             return false;
828     }
829     return true;
830 }
831
832 Structure* Structure::flattenDictionaryStructure(VM& vm, JSObject* object)
833 {
834     checkOffsetConsistency();
835     ASSERT(isDictionary());
836     ASSERT(object->structure(vm) == this);
837     
838     GCSafeConcurrentJSCellLocker locker(cellLock(), vm.heap);
839     
840     object->setStructureIDDirectly(nuke(id()));
841     WTF::storeStoreFence();
842
843     size_t beforeOutOfLineCapacity = this->outOfLineCapacity();
844     if (isUncacheableDictionary()) {
845         PropertyTable* table = propertyTableUnsafeOrNull();
846         ASSERT(table);
847
848         size_t propertyCount = table->size();
849
850         // Holds our values compacted by insertion order.
851         Vector<JSValue> values(propertyCount);
852
853         // Copies out our values from their hashed locations, compacting property table offsets as we go.
854         unsigned i = 0;
855         PropertyTable::iterator end = table->end();
856         auto offset = invalidOffset;
857         for (PropertyTable::iterator iter = table->begin(); iter != end; ++iter, ++i) {
858             values[i] = object->getDirect(iter->offset);
859             offset = iter->offset = offsetForPropertyNumber(i, inlineCapacity());
860         }
861         setMaxOffset(vm, offset);
862         ASSERT(transitionOffset() == invalidOffset);
863         
864         // Copies in our values to their compacted locations.
865         for (unsigned i = 0; i < propertyCount; i++)
866             object->putDirect(vm, offsetForPropertyNumber(i, inlineCapacity()), values[i]);
867
868         table->clearDeletedOffsets();
869
870         // We need to zero our unused property space; otherwise the GC might see a
871         // stale pointer when we add properties in the future.
872         gcSafeZeroMemory(
873             object->inlineStorageUnsafe() + inlineSize(),
874             (inlineCapacity() - inlineSize()) * sizeof(EncodedJSValue));
875
876         Butterfly* butterfly = object->butterfly();
877         size_t preCapacity = butterfly->indexingHeader()->preCapacity(this);
878         void* base = butterfly->base(preCapacity, beforeOutOfLineCapacity);
879         void* startOfPropertyStorageSlots = reinterpret_cast<EncodedJSValue*>(base) + preCapacity;
880         gcSafeZeroMemory(static_cast<JSValue*>(startOfPropertyStorageSlots), (beforeOutOfLineCapacity - outOfLineSize()) * sizeof(EncodedJSValue));
881         checkOffsetConsistency();
882     }
883
884     setDictionaryKind(NoneDictionaryKind);
885     setHasBeenFlattenedBefore(true);
886
887     size_t afterOutOfLineCapacity = this->outOfLineCapacity();
888
889     if (object->butterfly() && beforeOutOfLineCapacity != afterOutOfLineCapacity) {
890         ASSERT(beforeOutOfLineCapacity > afterOutOfLineCapacity);
891         // If the object had a Butterfly but after flattening/compacting we no longer have need of it,
892         // we need to zero it out because the collector depends on the Structure to know the size for copying.
893         if (!afterOutOfLineCapacity && !this->hasIndexingHeader(object))
894             object->setButterfly(vm, nullptr);
895         // If the object was down-sized to the point where the base of the Butterfly is no longer within the 
896         // first CopiedBlock::blockSize bytes, we'll get the wrong answer if we try to mask the base back to 
897         // the CopiedBlock header. To prevent this case we need to memmove the Butterfly down.
898         else
899             object->shiftButterflyAfterFlattening(locker, vm, this, afterOutOfLineCapacity);
900     }
901     
902     WTF::storeStoreFence();
903     object->setStructureIDDirectly(id());
904
905     // We need to do a writebarrier here because the GC thread might be scanning the butterfly while
906     // we are shuffling properties around. See: https://bugs.webkit.org/show_bug.cgi?id=166989
907     vm.heap.writeBarrier(object);
908
909     return this;
910 }
911
912 void Structure::pin(const AbstractLocker& locker, VM& vm, PropertyTable* table)
913 {
914     setIsPinnedPropertyTable(true);
915     setPropertyTable(vm, table);
916     clearPreviousID();
917     setTransitionPropertyName(locker, nullptr);
918 }
919
920 void Structure::pinForCaching(const AbstractLocker& locker, VM& vm, PropertyTable* table)
921 {
922     setIsPinnedPropertyTable(true);
923     setPropertyTable(vm, table);
924     setTransitionPropertyName(locker, nullptr);
925 }
926
927 void Structure::allocateRareData(VM& vm)
928 {
929     ASSERT(!hasRareData());
930     StructureRareData* rareData = StructureRareData::create(vm, cachedPrototypeChain());
931     WTF::storeStoreFence();
932 #if CPU(ADDRESS64)
933     m_inlineCapacityAndCachedPrototypeChainOrRareData.setPointer(rareData);
934     vm.heap.writeBarrier(this, rareData);
935 #else
936     m_cachedPrototypeChainOrRareData.set(vm, this, rareData);
937 #endif
938     ASSERT(hasRareData());
939 }
940
941 WatchpointSet* Structure::ensurePropertyReplacementWatchpointSet(VM& vm, PropertyOffset offset)
942 {
943     ASSERT(!isUncacheableDictionary());
944
945     // In some places it's convenient to call this with an invalid offset. So, we do the check here.
946     if (!isValidOffset(offset))
947         return nullptr;
948     
949     if (!hasRareData())
950         allocateRareData(vm);
951     ConcurrentJSCellLocker locker(cellLock());
952     StructureRareData* rareData = this->rareData();
953     if (!rareData->m_replacementWatchpointSets) {
954         rareData->m_replacementWatchpointSets =
955             makeUnique<StructureRareData::PropertyWatchpointMap>();
956         WTF::storeStoreFence();
957     }
958     auto result = rareData->m_replacementWatchpointSets->add(offset, nullptr);
959     if (result.isNewEntry)
960         result.iterator->value = adoptRef(new WatchpointSet(IsWatched));
961     return result.iterator->value.get();
962 }
963
964 void Structure::startWatchingPropertyForReplacements(VM& vm, PropertyName propertyName)
965 {
966     ASSERT(!isUncacheableDictionary());
967     
968     startWatchingPropertyForReplacements(vm, get(vm, propertyName));
969 }
970
971 void Structure::didCachePropertyReplacement(VM& vm, PropertyOffset offset)
972 {
973     RELEASE_ASSERT(isValidOffset(offset));
974     ensurePropertyReplacementWatchpointSet(vm, offset)->fireAll(vm, "Did cache property replacement");
975 }
976
977 void Structure::startWatchingInternalProperties(VM& vm)
978 {
979     if (!isUncacheableDictionary()) {
980         startWatchingPropertyForReplacements(vm, vm.propertyNames->toString);
981         startWatchingPropertyForReplacements(vm, vm.propertyNames->valueOf);
982     }
983     setDidWatchInternalProperties(true);
984 }
985
986 #if DUMP_PROPERTYMAP_STATS
987
988 PropertyMapHashTableStats* propertyMapHashTableStats = 0;
989
990 struct PropertyMapStatisticsExitLogger {
991     PropertyMapStatisticsExitLogger();
992     ~PropertyMapStatisticsExitLogger();
993 };
994
995 DEFINE_GLOBAL_FOR_LOGGING(PropertyMapStatisticsExitLogger, logger, );
996
997 PropertyMapStatisticsExitLogger::PropertyMapStatisticsExitLogger()
998 {
999     propertyMapHashTableStats = adoptPtr(new PropertyMapHashTableStats()).leakPtr();
1000 }
1001
1002 PropertyMapStatisticsExitLogger::~PropertyMapStatisticsExitLogger()
1003 {
1004     unsigned finds = propertyMapHashTableStats->numFinds;
1005     unsigned collisions = propertyMapHashTableStats->numCollisions;
1006     dataLogF("\nJSC::PropertyMap statistics for process %d\n\n", getCurrentProcessID());
1007     dataLogF("%d finds\n", finds);
1008     dataLogF("%d collisions (%.1f%%)\n", collisions, 100.0 * collisions / finds);
1009     dataLogF("%d lookups\n", propertyMapHashTableStats->numLookups.load());
1010     dataLogF("%d lookup probings\n", propertyMapHashTableStats->numLookupProbing.load());
1011     dataLogF("%d adds\n", propertyMapHashTableStats->numAdds.load());
1012     dataLogF("%d removes\n", propertyMapHashTableStats->numRemoves.load());
1013     dataLogF("%d rehashes\n", propertyMapHashTableStats->numRehashes.load());
1014     dataLogF("%d reinserts\n", propertyMapHashTableStats->numReinserts.load());
1015 }
1016
1017 #endif
1018
1019 PropertyTable* Structure::copyPropertyTableForPinning(VM& vm)
1020 {
1021     if (PropertyTable* table = propertyTableUnsafeOrNull())
1022         return PropertyTable::clone(vm, *table);
1023     bool setPropertyTable = false;
1024     return materializePropertyTable(vm, setPropertyTable);
1025 }
1026
1027 PropertyOffset Structure::getConcurrently(UniquedStringImpl* uid, unsigned& attributes)
1028 {
1029     PropertyOffset result = invalidOffset;
1030     
1031     forEachPropertyConcurrently(
1032         [&] (const PropertyMapEntry& candidate) -> bool {
1033             if (candidate.key != uid)
1034                 return true;
1035             
1036             result = candidate.offset;
1037             attributes = candidate.attributes;
1038             return false;
1039         });
1040     
1041     return result;
1042 }
1043
1044 Vector<PropertyMapEntry> Structure::getPropertiesConcurrently()
1045 {
1046     Vector<PropertyMapEntry> result;
1047
1048     forEachPropertyConcurrently(
1049         [&] (const PropertyMapEntry& entry) -> bool {
1050             result.append(entry);
1051             return true;
1052         });
1053     
1054     return result;
1055 }
1056
1057 PropertyOffset Structure::add(VM& vm, PropertyName propertyName, unsigned attributes)
1058 {
1059     return add<ShouldPin::No>(
1060         vm, propertyName, attributes,
1061         [this, &vm](const GCSafeConcurrentJSCellLocker&, PropertyOffset, PropertyOffset newMaxOffset) {
1062             setMaxOffset(vm, newMaxOffset);
1063         });
1064 }
1065
1066 PropertyOffset Structure::remove(VM& vm, PropertyName propertyName)
1067 {
1068     return remove<ShouldPin::No>(vm, propertyName, [this, &vm](const GCSafeConcurrentJSCellLocker&, PropertyOffset, PropertyOffset newMaxOffset) {
1069         setMaxOffset(vm, newMaxOffset);
1070     });
1071 }
1072
1073 void Structure::getPropertyNamesFromStructure(VM& vm, PropertyNameArray& propertyNames, EnumerationMode mode)
1074 {
1075     PropertyTable* table = ensurePropertyTableIfNotEmpty(vm);
1076     if (!table)
1077         return;
1078     
1079     bool knownUnique = propertyNames.canAddKnownUniqueForStructure();
1080     
1081     PropertyTable::iterator end = table->end();
1082     for (PropertyTable::iterator iter = table->begin(); iter != end; ++iter) {
1083         ASSERT(!isQuickPropertyAccessAllowedForEnumeration() || !(iter->attributes & PropertyAttribute::DontEnum));
1084         ASSERT(!isQuickPropertyAccessAllowedForEnumeration() || !iter->key->isSymbol());
1085         if (!(iter->attributes & PropertyAttribute::DontEnum) || mode.includeDontEnumProperties()) {
1086             if (iter->key->isSymbol() && !propertyNames.includeSymbolProperties())
1087                 continue;
1088             if (knownUnique)
1089                 propertyNames.addUnchecked(iter->key);
1090             else
1091                 propertyNames.add(iter->key);
1092         }
1093     }
1094 }
1095
1096 void StructureFireDetail::dump(PrintStream& out) const
1097 {
1098     out.print("Structure transition from ", *m_structure);
1099 }
1100
1101 DeferredStructureTransitionWatchpointFire::DeferredStructureTransitionWatchpointFire(VM& vm, Structure* structure)
1102     : DeferredWatchpointFire(vm)
1103     , m_structure(structure)
1104 {
1105 }
1106
1107 DeferredStructureTransitionWatchpointFire::~DeferredStructureTransitionWatchpointFire()
1108 {
1109     fireAll();
1110 }
1111
1112 void DeferredStructureTransitionWatchpointFire::dump(PrintStream& out) const
1113 {
1114     out.print("Structure transition from ", *m_structure);
1115 }
1116
1117 void Structure::didTransitionFromThisStructure(DeferredStructureTransitionWatchpointFire* deferred) const
1118 {
1119     // If the structure is being watched, and this is the kind of structure that the DFG would
1120     // like to watch, then make sure to note for all future versions of this structure that it's
1121     // unwise to watch it.
1122     if (m_transitionWatchpointSet.isBeingWatched())
1123         const_cast<Structure*>(this)->setTransitionWatchpointIsLikelyToBeFired(true);
1124
1125     if (deferred) {
1126         ASSERT(deferred->structure() == this);
1127         m_transitionWatchpointSet.fireAll(vm(), deferred);
1128     } else
1129         m_transitionWatchpointSet.fireAll(vm(), StructureFireDetail(this));
1130 }
1131
1132 void Structure::visitChildren(JSCell* cell, SlotVisitor& visitor)
1133 {
1134     Structure* thisObject = jsCast<Structure*>(cell);
1135     ASSERT_GC_OBJECT_INHERITS(thisObject, info());
1136
1137     Base::visitChildren(thisObject, visitor);
1138     
1139     ConcurrentJSCellLocker locker(thisObject->cellLock());
1140     
1141     visitor.append(thisObject->m_globalObject);
1142     visitor.append(thisObject->m_prototype);
1143     visitor.appendUnbarriered(thisObject->previousID(visitor.vm()));
1144     visitor.appendUnbarriered(thisObject->cachedPrototypeChainOrRareData());
1145
1146     if (thisObject->isPinnedPropertyTable() || thisObject->protectPropertyTableWhileTransitioning()) {
1147         // NOTE: This can interleave in pin(), in which case it may see a null property table.
1148         // That's fine, because then the barrier will fire and we will scan this again.
1149         visitor.appendUnbarriered(thisObject->propertyTableUnsafeOrNull());
1150     } else if (visitor.isAnalyzingHeap())
1151         visitor.appendUnbarriered(thisObject->propertyTableUnsafeOrNull());
1152     else if (thisObject->propertyTableUnsafeOrNull())
1153         thisObject->clearPropertyTable();
1154 }
1155
1156 bool Structure::isCheapDuringGC(VM& vm)
1157 {
1158     // FIXME: We could make this even safer by returning false if this structure's property table
1159     // has any large property names.
1160     // https://bugs.webkit.org/show_bug.cgi?id=157334
1161     
1162     return (!m_globalObject || vm.heap.isMarked(m_globalObject.get()))
1163         && (hasPolyProto() || !storedPrototypeObject() || vm.heap.isMarked(storedPrototypeObject()));
1164 }
1165
1166 bool Structure::markIfCheap(SlotVisitor& visitor)
1167 {
1168     VM& vm = visitor.vm();
1169     if (!isCheapDuringGC(vm))
1170         return vm.heap.isMarked(this);
1171     
1172     visitor.appendUnbarriered(this);
1173     return true;
1174 }
1175
1176 Ref<StructureShape> Structure::toStructureShape(JSValue value, bool& sawPolyProtoStructure)
1177 {
1178     Ref<StructureShape> baseShape = StructureShape::create();
1179     RefPtr<StructureShape> curShape = baseShape.ptr();
1180     Structure* curStructure = this;
1181     JSValue curValue = value;
1182     sawPolyProtoStructure = false;
1183     while (curStructure) {
1184         sawPolyProtoStructure |= curStructure->hasPolyProto();
1185         curStructure->forEachPropertyConcurrently(
1186             [&] (const PropertyMapEntry& entry) -> bool {
1187                 if (!PropertyName(entry.key).isPrivateName())
1188                     curShape->addProperty(*entry.key);
1189                 return true;
1190             });
1191
1192         if (JSObject* curObject = curValue.getObject())
1193             curShape->setConstructorName(JSObject::calculatedClassName(curObject));
1194         else
1195             curShape->setConstructorName(curStructure->classInfo()->className);
1196
1197         if (curStructure->isDictionary())
1198             curShape->enterDictionaryMode();
1199
1200         curShape->markAsFinal();
1201
1202         if (!curValue.isObject())
1203             break;
1204
1205         JSObject* object = asObject(curValue);
1206         JSObject* prototypeObject = object->structure()->storedPrototypeObject(object);
1207         if (!prototypeObject)
1208             break;
1209
1210         auto newShape = StructureShape::create();
1211         curShape->setProto(newShape.copyRef());
1212         curShape = WTFMove(newShape);
1213         curValue = prototypeObject;
1214         curStructure = prototypeObject->structure();
1215     }
1216     
1217     return baseShape;
1218 }
1219
1220 void Structure::dump(PrintStream& out) const
1221 {
1222     out.print(RawPointer(this), ":[", RawPointer(reinterpret_cast<void*>(id())), ", ", classInfo()->className, ", {");
1223     
1224     CommaPrinter comma;
1225     
1226     const_cast<Structure*>(this)->forEachPropertyConcurrently(
1227         [&] (const PropertyMapEntry& entry) -> bool {
1228             out.print(comma, entry.key, ":", static_cast<int>(entry.offset));
1229             return true;
1230         });
1231     
1232     out.print("}, ", IndexingTypeDump(indexingMode()));
1233     
1234     if (hasPolyProto())
1235         out.print(", PolyProto offset:", knownPolyProtoOffset);
1236     else if (m_prototype.get().isCell())
1237         out.print(", Proto:", RawPointer(m_prototype.get().asCell()));
1238
1239     switch (dictionaryKind()) {
1240     case NoneDictionaryKind:
1241         if (hasBeenDictionary())
1242             out.print(", Has been dictionary");
1243         break;
1244     case CachedDictionaryKind:
1245         out.print(", Dictionary");
1246         break;
1247     case UncachedDictionaryKind:
1248         out.print(", UncacheableDictionary");
1249         break;
1250     }
1251
1252     if (transitionWatchpointSetIsStillValid())
1253         out.print(", Leaf");
1254     else if (transitionWatchpointIsLikelyToBeFired())
1255         out.print(", Shady leaf");
1256     
1257     out.print("]");
1258 }
1259
1260 void Structure::dumpInContext(PrintStream& out, DumpContext* context) const
1261 {
1262     if (context)
1263         context->structures.dumpBrief(this, out);
1264     else
1265         dump(out);
1266 }
1267
1268 void Structure::dumpBrief(PrintStream& out, const CString& string) const
1269 {
1270     out.print("%", string, ":", classInfo()->className);
1271 }
1272
1273 void Structure::dumpContextHeader(PrintStream& out)
1274 {
1275     out.print("Structures:");
1276 }
1277
1278 bool ClassInfo::hasStaticSetterOrReadonlyProperties() const
1279 {
1280     for (const ClassInfo* ci = this; ci; ci = ci->parentClass) {
1281         if (const HashTable* table = ci->staticPropHashTable) {
1282             if (table->hasSetterOrReadonlyProperties)
1283                 return true;
1284         }
1285     }
1286     return false;
1287 }
1288
1289 void Structure::setCachedPropertyNameEnumerator(VM& vm, JSPropertyNameEnumerator* enumerator)
1290 {
1291     ASSERT(!isDictionary());
1292     if (!hasRareData())
1293         allocateRareData(vm);
1294     rareData()->setCachedPropertyNameEnumerator(vm, enumerator);
1295 }
1296
1297 JSPropertyNameEnumerator* Structure::cachedPropertyNameEnumerator() const
1298 {
1299     if (!hasRareData())
1300         return nullptr;
1301     return rareData()->cachedPropertyNameEnumerator();
1302 }
1303
1304 bool Structure::canCachePropertyNameEnumerator(VM& vm) const
1305 {
1306     if (!this->canCacheOwnKeys())
1307         return false;
1308
1309     StructureChain* structureChain = cachedPrototypeChain();
1310     ASSERT(structureChain);
1311     StructureID* currentStructureID = structureChain->head();
1312     while (true) {
1313         StructureID structureID = *currentStructureID;
1314         if (!structureID)
1315             return true;
1316         Structure* structure = vm.getStructure(structureID);
1317         if (!structure->canCacheOwnKeys())
1318             return false;
1319         currentStructureID++;
1320     }
1321
1322     ASSERT_NOT_REACHED();
1323     return true;
1324 }
1325     
1326 bool Structure::canAccessPropertiesQuicklyForEnumeration() const
1327 {
1328     if (!isQuickPropertyAccessAllowedForEnumeration())
1329         return false;
1330     if (hasGetterSetterProperties())
1331         return false;
1332     if (isUncacheableDictionary())
1333         return false;
1334     return true;
1335 }
1336
1337 auto Structure::findPropertyHashEntry(PropertyName propertyName) const -> Optional<PropertyHashEntry>
1338 {
1339     for (const ClassInfo* info = classInfo(); info; info = info->parentClass) {
1340         if (const HashTable* propHashTable = info->staticPropHashTable) {
1341             if (const HashTableValue* entry = propHashTable->entry(propertyName))
1342                 return PropertyHashEntry { propHashTable, entry };
1343         }
1344     }
1345     return WTF::nullopt;
1346 }
1347
1348 } // namespace JSC