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