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