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