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