[JSC] Weak should only accept cell pointees.
[WebKit-https.git] / Source / JavaScriptCore / runtime / Structure.cpp
1 /*
2  * Copyright (C) 2008, 2009, 2013-2015 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(JSCell*&, 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->cell());
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     setHasNonEnumerableProperties(false);
205     setAttributesInPrevious(0);
206     setPreventExtensions(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     setHasNonEnumerableProperties(false);
237     setAttributesInPrevious(0);
238     setPreventExtensions(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     setHasNonEnumerableProperties(previous->hasNonEnumerableProperties());
268     setAttributesInPrevious(0);
269     setPreventExtensions(previous->preventExtensions());
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     for (size_t i = structures.size(); i--;) {
354         structure = structures[i];
355         if (!structure->m_nameInPrevious)
356             continue;
357         PropertyMapEntry entry(structure->m_nameInPrevious.get(), structure->m_offset, structure->attributesInPrevious());
358         propertyTable()->add(entry, m_offset, PropertyTable::PropertyOffsetMustNotChange);
359     }
360     
361     checkOffsetConsistency();
362 }
363
364 Structure* Structure::addPropertyTransitionToExistingStructureImpl(Structure* structure, UniquedStringImpl* uid, unsigned attributes, PropertyOffset& offset)
365 {
366     ASSERT(!structure->isDictionary());
367     ASSERT(structure->isObject());
368
369     if (Structure* existingTransition = structure->m_transitionTable.get(uid, attributes)) {
370         validateOffset(existingTransition->m_offset, existingTransition->inlineCapacity());
371         offset = existingTransition->m_offset;
372         return existingTransition;
373     }
374
375     return 0;
376 }
377
378 Structure* Structure::addPropertyTransitionToExistingStructure(Structure* structure, PropertyName propertyName, unsigned attributes, PropertyOffset& offset)
379 {
380     ASSERT(!isCompilationThread());
381     return addPropertyTransitionToExistingStructureImpl(structure, propertyName.uid(), attributes, offset);
382 }
383
384 Structure* Structure::addPropertyTransitionToExistingStructureConcurrently(Structure* structure, UniquedStringImpl* uid, unsigned attributes, PropertyOffset& offset)
385 {
386     ConcurrentJITLocker locker(structure->m_lock);
387     return addPropertyTransitionToExistingStructureImpl(structure, uid, attributes, offset);
388 }
389
390 bool Structure::anyObjectInChainMayInterceptIndexedAccesses() const
391 {
392     for (const Structure* current = this; ;) {
393         if (current->mayInterceptIndexedAccesses())
394             return true;
395         
396         JSValue prototype = current->storedPrototype();
397         if (prototype.isNull())
398             return false;
399         
400         current = asObject(prototype)->structure();
401     }
402 }
403
404 bool Structure::holesMustForwardToPrototype(VM& vm) const
405 {
406     if (this->mayInterceptIndexedAccesses())
407         return true;
408
409     JSValue prototype = this->storedPrototype();
410     if (!prototype.isObject())
411         return false;
412     JSObject* object = asObject(prototype);
413
414     while (true) {
415         Structure& structure = *object->structure(vm);
416         if (hasIndexedProperties(object->indexingType()) || structure.mayInterceptIndexedAccesses())
417             return true;
418         prototype = structure.storedPrototype();
419         if (!prototype.isObject())
420             return false;
421         object = asObject(prototype);
422     }
423
424     RELEASE_ASSERT_NOT_REACHED();
425     return false;
426 }
427
428 bool Structure::needsSlowPutIndexing() const
429 {
430     return anyObjectInChainMayInterceptIndexedAccesses()
431         || globalObject()->isHavingABadTime();
432 }
433
434 NonPropertyTransition Structure::suggestedArrayStorageTransition() const
435 {
436     if (needsSlowPutIndexing())
437         return AllocateSlowPutArrayStorage;
438     
439     return AllocateArrayStorage;
440 }
441
442 Structure* Structure::addPropertyTransition(VM& vm, Structure* structure, PropertyName propertyName, unsigned attributes, PropertyOffset& offset, PutPropertySlot::Context context, DeferredStructureTransitionWatchpointFire* deferred)
443 {
444     ASSERT(!structure->isDictionary());
445     ASSERT(structure->isObject());
446     ASSERT(!Structure::addPropertyTransitionToExistingStructure(structure, propertyName, attributes, offset));
447     
448     int maxTransitionLength;
449     if (context == PutPropertySlot::PutById)
450         maxTransitionLength = s_maxTransitionLengthForNonEvalPutById;
451     else
452         maxTransitionLength = s_maxTransitionLength;
453     if (structure->transitionCount() > maxTransitionLength) {
454         Structure* transition = toCacheableDictionaryTransition(vm, structure, deferred);
455         ASSERT(structure != transition);
456         offset = transition->add(vm, propertyName, attributes);
457         return transition;
458     }
459     
460     Structure* transition = create(vm, structure, deferred);
461
462     transition->m_cachedPrototypeChain.setMayBeNull(vm, transition, structure->m_cachedPrototypeChain.get());
463     transition->m_nameInPrevious = propertyName.uid();
464     transition->setAttributesInPrevious(attributes);
465     transition->propertyTable().set(vm, transition, structure->takePropertyTableOrCloneIfPinned(vm));
466     transition->m_offset = structure->m_offset;
467
468     offset = transition->add(vm, propertyName, attributes);
469
470     checkOffset(transition->m_offset, transition->inlineCapacity());
471     {
472         ConcurrentJITLocker locker(structure->m_lock);
473         structure->m_transitionTable.add(vm, transition);
474     }
475     transition->checkOffsetConsistency();
476     structure->checkOffsetConsistency();
477     return transition;
478 }
479
480 Structure* Structure::removePropertyTransition(VM& vm, Structure* structure, PropertyName propertyName, PropertyOffset& offset)
481 {
482     ASSERT(!structure->isUncacheableDictionary());
483
484     Structure* transition = toUncacheableDictionaryTransition(vm, structure);
485
486     offset = transition->remove(propertyName);
487
488     transition->checkOffsetConsistency();
489     return transition;
490 }
491
492 Structure* Structure::changePrototypeTransition(VM& vm, Structure* structure, JSValue prototype)
493 {
494     Structure* transition = create(vm, structure);
495
496     transition->m_prototype.set(vm, transition, prototype);
497
498     DeferGC deferGC(vm.heap);
499     structure->materializePropertyMapIfNecessary(vm, deferGC);
500     transition->propertyTable().set(vm, transition, structure->copyPropertyTableForPinning(vm));
501     transition->m_offset = structure->m_offset;
502     transition->pin();
503
504     transition->checkOffsetConsistency();
505     return transition;
506 }
507
508 Structure* Structure::attributeChangeTransition(VM& vm, Structure* structure, PropertyName propertyName, unsigned attributes)
509 {
510     DeferGC deferGC(vm.heap);
511     if (!structure->isUncacheableDictionary()) {
512         Structure* transition = create(vm, structure);
513
514         structure->materializePropertyMapIfNecessary(vm, deferGC);
515         transition->propertyTable().set(vm, transition, structure->copyPropertyTableForPinning(vm));
516         transition->m_offset = structure->m_offset;
517         transition->pin();
518         
519         structure = transition;
520     }
521
522     ASSERT(structure->propertyTable());
523     PropertyMapEntry* entry = structure->propertyTable()->get(propertyName.uid());
524     ASSERT(entry);
525     entry->attributes = attributes;
526
527     structure->checkOffsetConsistency();
528     return structure;
529 }
530
531 Structure* Structure::toDictionaryTransition(VM& vm, Structure* structure, DictionaryKind kind, DeferredStructureTransitionWatchpointFire* deferred)
532 {
533     ASSERT(!structure->isUncacheableDictionary());
534     
535     Structure* transition = create(vm, structure, deferred);
536
537     DeferGC deferGC(vm.heap);
538     structure->materializePropertyMapIfNecessary(vm, deferGC);
539     transition->propertyTable().set(vm, transition, structure->copyPropertyTableForPinning(vm));
540     transition->m_offset = structure->m_offset;
541     transition->setDictionaryKind(kind);
542     transition->pin();
543     transition->setHasBeenDictionary(true);
544
545     transition->checkOffsetConsistency();
546     return transition;
547 }
548
549 Structure* Structure::toCacheableDictionaryTransition(VM& vm, Structure* structure, DeferredStructureTransitionWatchpointFire* deferred)
550 {
551     return toDictionaryTransition(vm, structure, CachedDictionaryKind, deferred);
552 }
553
554 Structure* Structure::toUncacheableDictionaryTransition(VM& vm, Structure* structure)
555 {
556     return toDictionaryTransition(vm, structure, UncachedDictionaryKind);
557 }
558
559 // In future we may want to cache this transition.
560 Structure* Structure::sealTransition(VM& vm, Structure* structure)
561 {
562     Structure* transition = preventExtensionsTransition(vm, structure);
563
564     if (transition->propertyTable()) {
565         PropertyTable::iterator end = transition->propertyTable()->end();
566         for (PropertyTable::iterator iter = transition->propertyTable()->begin(); iter != end; ++iter)
567             iter->attributes |= DontDelete;
568     }
569
570     transition->checkOffsetConsistency();
571     return transition;
572 }
573
574 // In future we may want to cache this transition.
575 Structure* Structure::freezeTransition(VM& vm, Structure* structure)
576 {
577     Structure* transition = preventExtensionsTransition(vm, structure);
578
579     if (transition->propertyTable()) {
580         PropertyTable::iterator iter = transition->propertyTable()->begin();
581         PropertyTable::iterator end = transition->propertyTable()->end();
582         if (iter != end)
583             transition->setHasReadOnlyOrGetterSetterPropertiesExcludingProto(true);
584         for (; iter != end; ++iter)
585             iter->attributes |= iter->attributes & Accessor ? DontDelete : (DontDelete | ReadOnly);
586     }
587
588     ASSERT(transition->hasReadOnlyOrGetterSetterPropertiesExcludingProto() || !transition->classInfo()->hasStaticSetterOrReadonlyProperties());
589     ASSERT(transition->hasGetterSetterProperties() || !transition->classInfo()->hasStaticSetterOrReadonlyProperties());
590     transition->checkOffsetConsistency();
591     return transition;
592 }
593
594 // In future we may want to cache this transition.
595 Structure* Structure::preventExtensionsTransition(VM& vm, Structure* structure)
596 {
597     Structure* transition = create(vm, structure);
598
599     // Don't set m_offset, as one can not transition to this.
600
601     DeferGC deferGC(vm.heap);
602     structure->materializePropertyMapIfNecessary(vm, deferGC);
603     transition->propertyTable().set(vm, transition, structure->copyPropertyTableForPinning(vm));
604     transition->m_offset = structure->m_offset;
605     transition->setPreventExtensions(true);
606     transition->pin();
607
608     transition->checkOffsetConsistency();
609     return transition;
610 }
611
612 PropertyTable* Structure::takePropertyTableOrCloneIfPinned(VM& vm)
613 {
614     DeferGC deferGC(vm.heap);
615     materializePropertyMapIfNecessaryForPinning(vm, deferGC);
616     
617     if (isPinnedPropertyTable())
618         return propertyTable()->copy(vm, propertyTable()->size() + 1);
619     
620     // Hold the lock while stealing the table - so that getConcurrently() on another thread
621     // will either have to bypass this structure, or will get to use the property table
622     // before it is stolen.
623     ConcurrentJITLocker locker(m_lock);
624     PropertyTable* takenPropertyTable = propertyTable().get();
625     propertyTable().clear();
626     return takenPropertyTable;
627 }
628
629 Structure* Structure::nonPropertyTransition(VM& vm, Structure* structure, NonPropertyTransition transitionKind)
630 {
631     unsigned attributes = toAttributes(transitionKind);
632     IndexingType indexingType = newIndexingType(structure->indexingTypeIncludingHistory(), transitionKind);
633     
634     if (JSGlobalObject* globalObject = structure->m_globalObject.get()) {
635         if (globalObject->isOriginalArrayStructure(structure)) {
636             Structure* result = globalObject->originalArrayStructureForIndexingType(indexingType);
637             if (result->indexingTypeIncludingHistory() == indexingType) {
638                 structure->didTransitionFromThisStructure();
639                 return result;
640             }
641         }
642     }
643     
644     Structure* existingTransition;
645     if (!structure->isDictionary() && (existingTransition = structure->m_transitionTable.get(0, attributes))) {
646         ASSERT(existingTransition->attributesInPrevious() == attributes);
647         ASSERT(existingTransition->indexingTypeIncludingHistory() == indexingType);
648         return existingTransition;
649     }
650     
651     Structure* transition = create(vm, structure);
652     transition->setAttributesInPrevious(attributes);
653     transition->m_blob.setIndexingType(indexingType);
654     transition->propertyTable().set(vm, transition, structure->takePropertyTableOrCloneIfPinned(vm));
655     transition->m_offset = structure->m_offset;
656     checkOffset(transition->m_offset, transition->inlineCapacity());
657     
658     if (structure->isDictionary())
659         transition->pin();
660     else {
661         ConcurrentJITLocker locker(structure->m_lock);
662         structure->m_transitionTable.add(vm, transition);
663     }
664     transition->checkOffsetConsistency();
665     return transition;
666 }
667
668 // In future we may want to cache this property.
669 bool Structure::isSealed(VM& vm)
670 {
671     if (isExtensible())
672         return false;
673
674     DeferGC deferGC(vm.heap);
675     materializePropertyMapIfNecessary(vm, deferGC);
676     if (!propertyTable())
677         return true;
678
679     PropertyTable::iterator end = propertyTable()->end();
680     for (PropertyTable::iterator iter = propertyTable()->begin(); iter != end; ++iter) {
681         if ((iter->attributes & DontDelete) != DontDelete)
682             return false;
683     }
684     return true;
685 }
686
687 // In future we may want to cache this property.
688 bool Structure::isFrozen(VM& vm)
689 {
690     if (isExtensible())
691         return false;
692
693     DeferGC deferGC(vm.heap);
694     materializePropertyMapIfNecessary(vm, deferGC);
695     if (!propertyTable())
696         return true;
697
698     PropertyTable::iterator end = propertyTable()->end();
699     for (PropertyTable::iterator iter = propertyTable()->begin(); iter != end; ++iter) {
700         if (!(iter->attributes & DontDelete))
701             return false;
702         if (!(iter->attributes & (ReadOnly | Accessor)))
703             return false;
704     }
705     return true;
706 }
707
708 Structure* Structure::flattenDictionaryStructure(VM& vm, JSObject* object)
709 {
710     checkOffsetConsistency();
711     ASSERT(isDictionary());
712
713     size_t beforeOutOfLineCapacity = this->outOfLineCapacity();
714     if (isUncacheableDictionary()) {
715         ASSERT(propertyTable());
716
717         size_t propertyCount = propertyTable()->size();
718
719         // Holds our values compacted by insertion order.
720         Vector<JSValue> values(propertyCount);
721
722         // Copies out our values from their hashed locations, compacting property table offsets as we go.
723         unsigned i = 0;
724         PropertyTable::iterator end = propertyTable()->end();
725         m_offset = invalidOffset;
726         for (PropertyTable::iterator iter = propertyTable()->begin(); iter != end; ++iter, ++i) {
727             values[i] = object->getDirect(iter->offset);
728             m_offset = iter->offset = offsetForPropertyNumber(i, m_inlineCapacity);
729         }
730         
731         // Copies in our values to their compacted locations.
732         for (unsigned i = 0; i < propertyCount; i++)
733             object->putDirect(vm, offsetForPropertyNumber(i, m_inlineCapacity), values[i]);
734
735         propertyTable()->clearDeletedOffsets();
736         checkOffsetConsistency();
737     }
738
739     setDictionaryKind(NoneDictionaryKind);
740     setHasBeenFlattenedBefore(true);
741
742     size_t afterOutOfLineCapacity = this->outOfLineCapacity();
743
744     if (beforeOutOfLineCapacity != afterOutOfLineCapacity) {
745         ASSERT(beforeOutOfLineCapacity > afterOutOfLineCapacity);
746         // If the object had a Butterfly but after flattening/compacting we no longer have need of it,
747         // we need to zero it out because the collector depends on the Structure to know the size for copying.
748         if (object->butterfly() && !afterOutOfLineCapacity && !this->hasIndexingHeader(object))
749             object->setStructureAndButterfly(vm, this, 0);
750         // If the object was down-sized to the point where the base of the Butterfly is no longer within the 
751         // first CopiedBlock::blockSize bytes, we'll get the wrong answer if we try to mask the base back to 
752         // the CopiedBlock header. To prevent this case we need to memmove the Butterfly down.
753         else if (object->butterfly())
754             object->shiftButterflyAfterFlattening(vm, beforeOutOfLineCapacity, afterOutOfLineCapacity);
755     }
756
757     return this;
758 }
759
760 PropertyOffset Structure::addPropertyWithoutTransition(VM& vm, PropertyName propertyName, unsigned attributes)
761 {
762     DeferGC deferGC(vm.heap);
763     materializePropertyMapIfNecessaryForPinning(vm, deferGC);
764     
765     pin();
766
767     return add(vm, propertyName, attributes);
768 }
769
770 PropertyOffset Structure::removePropertyWithoutTransition(VM& vm, PropertyName propertyName)
771 {
772     ASSERT(isUncacheableDictionary());
773
774     DeferGC deferGC(vm.heap);
775     materializePropertyMapIfNecessaryForPinning(vm, deferGC);
776
777     pin();
778     return remove(propertyName);
779 }
780
781 void Structure::pin()
782 {
783     ASSERT(propertyTable());
784     setIsPinnedPropertyTable(true);
785     clearPreviousID();
786     m_nameInPrevious = nullptr;
787 }
788
789 void Structure::allocateRareData(VM& vm)
790 {
791     ASSERT(!hasRareData());
792     StructureRareData* rareData = StructureRareData::create(vm, previous());
793     WTF::storeStoreFence();
794     m_previousOrRareData.set(vm, this, rareData);
795     WTF::storeStoreFence();
796     setHasRareData(true);
797     ASSERT(hasRareData());
798 }
799
800 WatchpointSet* Structure::ensurePropertyReplacementWatchpointSet(VM& vm, PropertyOffset offset)
801 {
802     ASSERT(!isUncacheableDictionary());
803
804     // In some places it's convenient to call this with an invalid offset. So, we do the check here.
805     if (!isValidOffset(offset))
806         return nullptr;
807     
808     if (!hasRareData())
809         allocateRareData(vm);
810     ConcurrentJITLocker locker(m_lock);
811     StructureRareData* rareData = this->rareData();
812     if (!rareData->m_replacementWatchpointSets) {
813         rareData->m_replacementWatchpointSets =
814             std::make_unique<StructureRareData::PropertyWatchpointMap>();
815         WTF::storeStoreFence();
816     }
817     auto result = rareData->m_replacementWatchpointSets->add(offset, nullptr);
818     if (result.isNewEntry)
819         result.iterator->value = adoptRef(new WatchpointSet(IsWatched));
820     return result.iterator->value.get();
821 }
822
823 void Structure::startWatchingPropertyForReplacements(VM& vm, PropertyName propertyName)
824 {
825     ASSERT(!isUncacheableDictionary());
826     
827     startWatchingPropertyForReplacements(vm, get(vm, propertyName));
828 }
829
830 void Structure::didCachePropertyReplacement(VM& vm, PropertyOffset offset)
831 {
832     ensurePropertyReplacementWatchpointSet(vm, offset)->fireAll("Did cache property replacement");
833 }
834
835 void Structure::startWatchingInternalProperties(VM& vm)
836 {
837     if (!isUncacheableDictionary()) {
838         startWatchingPropertyForReplacements(vm, vm.propertyNames->toString);
839         startWatchingPropertyForReplacements(vm, vm.propertyNames->valueOf);
840     }
841     setDidWatchInternalProperties(true);
842 }
843
844 #if DUMP_PROPERTYMAP_STATS
845
846 PropertyMapHashTableStats* propertyMapHashTableStats = 0;
847
848 struct PropertyMapStatisticsExitLogger {
849     PropertyMapStatisticsExitLogger();
850     ~PropertyMapStatisticsExitLogger();
851 };
852
853 DEFINE_GLOBAL_FOR_LOGGING(PropertyMapStatisticsExitLogger, logger, );
854
855 PropertyMapStatisticsExitLogger::PropertyMapStatisticsExitLogger()
856 {
857     propertyMapHashTableStats = adoptPtr(new PropertyMapHashTableStats()).leakPtr();
858 }
859
860 PropertyMapStatisticsExitLogger::~PropertyMapStatisticsExitLogger()
861 {
862     unsigned finds = propertyMapHashTableStats->numFinds;
863     unsigned collisions = propertyMapHashTableStats->numCollisions;
864     dataLogF("\nJSC::PropertyMap statistics for process %d\n\n", getCurrentProcessID());
865     dataLogF("%d finds\n", finds);
866     dataLogF("%d collisions (%.1f%%)\n", collisions, 100.0 * collisions / finds);
867     dataLogF("%d lookups\n", propertyMapHashTableStats->numLookups.load());
868     dataLogF("%d lookup probings\n", propertyMapHashTableStats->numLookupProbing.load());
869     dataLogF("%d adds\n", propertyMapHashTableStats->numAdds.load());
870     dataLogF("%d removes\n", propertyMapHashTableStats->numRemoves.load());
871     dataLogF("%d rehashes\n", propertyMapHashTableStats->numRehashes.load());
872     dataLogF("%d reinserts\n", propertyMapHashTableStats->numReinserts.load());
873 }
874
875 #endif
876
877 PropertyTable* Structure::copyPropertyTable(VM& vm)
878 {
879     if (!propertyTable())
880         return 0;
881     return PropertyTable::clone(vm, *propertyTable().get());
882 }
883
884 PropertyTable* Structure::copyPropertyTableForPinning(VM& vm)
885 {
886     if (propertyTable())
887         return PropertyTable::clone(vm, *propertyTable().get());
888     return PropertyTable::create(vm, numberOfSlotsForLastOffset(m_offset, m_inlineCapacity));
889 }
890
891 PropertyOffset Structure::getConcurrently(UniquedStringImpl* uid, unsigned& attributes)
892 {
893     PropertyOffset result = invalidOffset;
894     
895     forEachPropertyConcurrently(
896         [&] (const PropertyMapEntry& candidate) -> bool {
897             if (candidate.key != uid)
898                 return true;
899             
900             result = candidate.offset;
901             attributes = candidate.attributes;
902             return false;
903         });
904     
905     return result;
906 }
907
908 Vector<PropertyMapEntry> Structure::getPropertiesConcurrently()
909 {
910     Vector<PropertyMapEntry> result;
911
912     forEachPropertyConcurrently(
913         [&] (const PropertyMapEntry& entry) -> bool {
914             result.append(entry);
915             return true;
916         });
917     
918     return result;
919 }
920
921 PropertyOffset Structure::add(VM& vm, PropertyName propertyName, unsigned attributes)
922 {
923     GCSafeConcurrentJITLocker locker(m_lock, vm.heap);
924     
925     ASSERT(!JSC::isValidOffset(get(vm, propertyName)));
926
927     checkConsistency();
928     if (attributes & DontEnum)
929         setHasNonEnumerableProperties(true);
930
931     auto rep = propertyName.uid();
932
933     if (!propertyTable())
934         createPropertyMap(locker, vm);
935
936     PropertyOffset newOffset = propertyTable()->nextOffset(m_inlineCapacity);
937
938     propertyTable()->add(PropertyMapEntry(rep, newOffset, attributes), m_offset, PropertyTable::PropertyOffsetMayChange);
939     
940     checkConsistency();
941     return newOffset;
942 }
943
944 PropertyOffset Structure::remove(PropertyName propertyName)
945 {
946     ConcurrentJITLocker locker(m_lock);
947     
948     checkConsistency();
949
950     auto rep = propertyName.uid();
951
952     if (!propertyTable())
953         return invalidOffset;
954
955     PropertyTable::find_iterator position = propertyTable()->find(rep);
956     if (!position.first)
957         return invalidOffset;
958
959     PropertyOffset offset = position.first->offset;
960
961     propertyTable()->remove(position);
962     propertyTable()->addDeletedOffset(offset);
963
964     checkConsistency();
965     return offset;
966 }
967
968 void Structure::createPropertyMap(const GCSafeConcurrentJITLocker&, VM& vm, unsigned capacity)
969 {
970     ASSERT(!propertyTable());
971
972     checkConsistency();
973     propertyTable().set(vm, this, PropertyTable::create(vm, capacity));
974 }
975
976 void Structure::getPropertyNamesFromStructure(VM& vm, PropertyNameArray& propertyNames, EnumerationMode mode)
977 {
978     DeferGC deferGC(vm.heap);
979     materializePropertyMapIfNecessary(vm, deferGC);
980     if (!propertyTable())
981         return;
982
983     bool knownUnique = propertyNames.canAddKnownUniqueForStructure();
984
985     PropertyTable::iterator end = propertyTable()->end();
986     for (PropertyTable::iterator iter = propertyTable()->begin(); iter != end; ++iter) {
987         ASSERT(hasNonEnumerableProperties() || !(iter->attributes & DontEnum));
988         if (!(iter->attributes & DontEnum) || mode.includeDontEnumProperties()) {
989             if (iter->key->isSymbol() && !propertyNames.includeSymbolProperties())
990                 continue;
991             if (knownUnique)
992                 propertyNames.addKnownUnique(iter->key);
993             else
994                 propertyNames.add(iter->key);
995         }
996     }
997 }
998
999 void StructureFireDetail::dump(PrintStream& out) const
1000 {
1001     out.print("Structure transition from ", *m_structure);
1002 }
1003
1004 DeferredStructureTransitionWatchpointFire::DeferredStructureTransitionWatchpointFire()
1005     : m_structure(nullptr)
1006 {
1007 }
1008
1009 DeferredStructureTransitionWatchpointFire::~DeferredStructureTransitionWatchpointFire()
1010 {
1011     if (m_structure)
1012         m_structure->transitionWatchpointSet().fireAll(StructureFireDetail(m_structure));
1013 }
1014
1015 void DeferredStructureTransitionWatchpointFire::add(const Structure* structure)
1016 {
1017     RELEASE_ASSERT(!m_structure);
1018     RELEASE_ASSERT(structure);
1019     m_structure = structure;
1020 }
1021
1022 void Structure::didTransitionFromThisStructure(DeferredStructureTransitionWatchpointFire* deferred) const
1023 {
1024     // If the structure is being watched, and this is the kind of structure that the DFG would
1025     // like to watch, then make sure to note for all future versions of this structure that it's
1026     // unwise to watch it.
1027     if (m_transitionWatchpointSet.isBeingWatched())
1028         const_cast<Structure*>(this)->setTransitionWatchpointIsLikelyToBeFired(true);
1029     
1030     if (deferred)
1031         deferred->add(this);
1032     else
1033         m_transitionWatchpointSet.fireAll(StructureFireDetail(this));
1034 }
1035
1036 JSValue Structure::prototypeForLookup(CodeBlock* codeBlock) const
1037 {
1038     return prototypeForLookup(codeBlock->globalObject());
1039 }
1040
1041 void Structure::visitChildren(JSCell* cell, SlotVisitor& visitor)
1042 {
1043     Structure* thisObject = jsCast<Structure*>(cell);
1044     ASSERT_GC_OBJECT_INHERITS(thisObject, info());
1045
1046     JSCell::visitChildren(thisObject, visitor);
1047     visitor.append(&thisObject->m_globalObject);
1048     if (!thisObject->isObject())
1049         thisObject->m_cachedPrototypeChain.clear();
1050     else {
1051         visitor.append(&thisObject->m_prototype);
1052         visitor.append(&thisObject->m_cachedPrototypeChain);
1053     }
1054     visitor.append(&thisObject->m_previousOrRareData);
1055
1056     if (thisObject->isPinnedPropertyTable()) {
1057         ASSERT(thisObject->m_propertyTableUnsafe);
1058         visitor.append(&thisObject->m_propertyTableUnsafe);
1059     } else if (thisObject->m_propertyTableUnsafe)
1060         thisObject->m_propertyTableUnsafe.clear();
1061 }
1062
1063 bool Structure::prototypeChainMayInterceptStoreTo(VM& vm, PropertyName propertyName)
1064 {
1065     if (parseIndex(propertyName))
1066         return anyObjectInChainMayInterceptIndexedAccesses();
1067     
1068     for (Structure* current = this; ;) {
1069         JSValue prototype = current->storedPrototype();
1070         if (prototype.isNull())
1071             return false;
1072         
1073         current = prototype.asCell()->structure(vm);
1074         
1075         unsigned attributes;
1076         PropertyOffset offset = current->get(vm, propertyName, attributes);
1077         if (!JSC::isValidOffset(offset))
1078             continue;
1079         
1080         if (attributes & (ReadOnly | Accessor))
1081             return true;
1082         
1083         return false;
1084     }
1085 }
1086
1087 PassRefPtr<StructureShape> Structure::toStructureShape(JSValue value)
1088 {
1089     RefPtr<StructureShape> baseShape = StructureShape::create();
1090     RefPtr<StructureShape> curShape = baseShape;
1091     Structure* curStructure = this;
1092     JSValue curValue = value;
1093     while (curStructure) {
1094         Vector<Structure*, 8> structures;
1095         Structure* structure;
1096         PropertyTable* table;
1097
1098         curStructure->findStructuresAndMapForMaterialization(structures, structure, table);
1099         if (table) {
1100             PropertyTable::iterator iter = table->begin();
1101             PropertyTable::iterator end = table->end();
1102             for (; iter != end; ++iter)
1103                 curShape->addProperty(*iter->key);
1104             
1105             structure->m_lock.unlock();
1106         }
1107         for (unsigned i = structures.size(); i--;) {
1108             Structure* structure = structures[i];
1109             if (structure->m_nameInPrevious)
1110                 curShape->addProperty(*structure->m_nameInPrevious);
1111         }
1112
1113         if (JSObject* curObject = curValue.getObject())
1114             curShape->setConstructorName(JSObject::calculatedClassName(curObject));
1115         else
1116             curShape->setConstructorName(curStructure->classInfo()->className);
1117
1118         if (curStructure->isDictionary())
1119             curShape->enterDictionaryMode();
1120
1121         curShape->markAsFinal();
1122
1123         if (curStructure->storedPrototypeStructure()) {
1124             RefPtr<StructureShape> newShape = StructureShape::create();
1125             curShape->setProto(newShape);
1126             curShape = newShape.release();
1127             curValue = curStructure->storedPrototype();
1128         }
1129
1130         curStructure = curStructure->storedPrototypeStructure();
1131     }
1132     
1133     return baseShape.release();
1134 }
1135
1136 bool Structure::canUseForAllocationsOf(Structure* other)
1137 {
1138     return inlineCapacity() == other->inlineCapacity()
1139         && storedPrototype() == other->storedPrototype()
1140         && objectInitializationBlob() == other->objectInitializationBlob();
1141 }
1142
1143 void Structure::dump(PrintStream& out) const
1144 {
1145     out.print(RawPointer(this), ":[", classInfo()->className, ", {");
1146     
1147     CommaPrinter comma;
1148     
1149     const_cast<Structure*>(this)->forEachPropertyConcurrently(
1150         [&] (const PropertyMapEntry& entry) -> bool {
1151             out.print(comma, entry.key, ":", static_cast<int>(entry.offset));
1152             return true;
1153         });
1154     
1155     out.print("}, ", IndexingTypeDump(indexingType()));
1156     
1157     if (m_prototype.get().isCell())
1158         out.print(", Proto:", RawPointer(m_prototype.get().asCell()));
1159
1160     switch (dictionaryKind()) {
1161     case NoneDictionaryKind:
1162         if (hasBeenDictionary())
1163             out.print(", Has been dictionary");
1164         break;
1165     case CachedDictionaryKind:
1166         out.print(", Dictionary");
1167         break;
1168     case UncachedDictionaryKind:
1169         out.print(", UncacheableDictionary");
1170         break;
1171     }
1172
1173     if (transitionWatchpointSetIsStillValid())
1174         out.print(", Leaf");
1175     else if (transitionWatchpointIsLikelyToBeFired())
1176         out.print(", Shady leaf");
1177     
1178     out.print("]");
1179 }
1180
1181 void Structure::dumpInContext(PrintStream& out, DumpContext* context) const
1182 {
1183     if (context)
1184         context->structures.dumpBrief(this, out);
1185     else
1186         dump(out);
1187 }
1188
1189 void Structure::dumpBrief(PrintStream& out, const CString& string) const
1190 {
1191     out.print("%", string, ":", classInfo()->className);
1192 }
1193
1194 void Structure::dumpContextHeader(PrintStream& out)
1195 {
1196     out.print("Structures:");
1197 }
1198
1199 #if DO_PROPERTYMAP_CONSTENCY_CHECK
1200
1201 void PropertyTable::checkConsistency()
1202 {
1203     ASSERT(m_indexSize >= PropertyTable::MinimumTableSize);
1204     ASSERT(m_indexMask);
1205     ASSERT(m_indexSize == m_indexMask + 1);
1206     ASSERT(!(m_indexSize & m_indexMask));
1207
1208     ASSERT(m_keyCount <= m_indexSize / 2);
1209     ASSERT(m_keyCount + m_deletedCount <= m_indexSize / 2);
1210     ASSERT(m_deletedCount <= m_indexSize / 4);
1211
1212     unsigned indexCount = 0;
1213     unsigned deletedIndexCount = 0;
1214     for (unsigned a = 0; a != m_indexSize; ++a) {
1215         unsigned entryIndex = m_index[a];
1216         if (entryIndex == PropertyTable::EmptyEntryIndex)
1217             continue;
1218         if (entryIndex == deletedEntryIndex()) {
1219             ++deletedIndexCount;
1220             continue;
1221         }
1222         ASSERT(entryIndex < deletedEntryIndex());
1223         ASSERT(entryIndex - 1 <= usedCount());
1224         ++indexCount;
1225
1226         for (unsigned b = a + 1; b != m_indexSize; ++b)
1227             ASSERT(m_index[b] != entryIndex);
1228     }
1229     ASSERT(indexCount == m_keyCount);
1230     ASSERT(deletedIndexCount == m_deletedCount);
1231
1232     ASSERT(!table()[deletedEntryIndex() - 1].key);
1233
1234     unsigned nonEmptyEntryCount = 0;
1235     for (unsigned c = 0; c < usedCount(); ++c) {
1236         StringImpl* rep = table()[c].key;
1237         if (rep == PROPERTY_MAP_DELETED_ENTRY_KEY)
1238             continue;
1239         ++nonEmptyEntryCount;
1240         unsigned i = IdentifierRepHash::hash(rep);
1241         unsigned k = 0;
1242         unsigned entryIndex;
1243         while (1) {
1244             entryIndex = m_index[i & m_indexMask];
1245             ASSERT(entryIndex != PropertyTable::EmptyEntryIndex);
1246             if (rep == table()[entryIndex - 1].key)
1247                 break;
1248             if (k == 0)
1249                 k = 1 | doubleHash(IdentifierRepHash::hash(rep));
1250             i += k;
1251         }
1252         ASSERT(entryIndex == c + 1);
1253     }
1254
1255     ASSERT(nonEmptyEntryCount == m_keyCount);
1256 }
1257
1258 void Structure::checkConsistency()
1259 {
1260     checkOffsetConsistency();
1261
1262     if (!propertyTable())
1263         return;
1264
1265     if (!hasNonEnumerableProperties()) {
1266         PropertyTable::iterator end = propertyTable()->end();
1267         for (PropertyTable::iterator iter = propertyTable()->begin(); iter != end; ++iter) {
1268             ASSERT(!(iter->attributes & DontEnum));
1269         }
1270     }
1271
1272     propertyTable()->checkConsistency();
1273 }
1274
1275 #else
1276
1277 inline void Structure::checkConsistency()
1278 {
1279     checkOffsetConsistency();
1280 }
1281
1282 #endif // DO_PROPERTYMAP_CONSTENCY_CHECK
1283
1284 bool ClassInfo::hasStaticSetterOrReadonlyProperties() const
1285 {
1286     for (const ClassInfo* ci = this; ci; ci = ci->parentClass) {
1287         if (const HashTable* table = ci->staticPropHashTable) {
1288             if (table->hasSetterOrReadonlyProperties)
1289                 return true;
1290         }
1291     }
1292     return false;
1293 }
1294
1295 void Structure::setCachedPropertyNameEnumerator(VM& vm, JSPropertyNameEnumerator* enumerator)
1296 {
1297     ASSERT(!isDictionary());
1298     if (!hasRareData())
1299         allocateRareData(vm);
1300     rareData()->setCachedPropertyNameEnumerator(vm, enumerator);
1301 }
1302
1303 JSPropertyNameEnumerator* Structure::cachedPropertyNameEnumerator() const
1304 {
1305     if (!hasRareData())
1306         return nullptr;
1307     return rareData()->cachedPropertyNameEnumerator();
1308 }
1309
1310 bool Structure::canCachePropertyNameEnumerator() const
1311 {
1312     if (isDictionary())
1313         return false;
1314
1315     if (hasIndexedProperties(indexingType()))
1316         return false;
1317
1318     if (typeInfo().overridesGetPropertyNames())
1319         return false;
1320
1321     StructureChain* structureChain = m_cachedPrototypeChain.get();
1322     ASSERT(structureChain);
1323     WriteBarrier<Structure>* structure = structureChain->head();
1324     while (true) {
1325         if (!structure->get())
1326             break;
1327         if (structure->get()->typeInfo().overridesGetPropertyNames())
1328             return false;
1329         structure++;
1330     }
1331     
1332     return true;
1333 }
1334     
1335 bool Structure::canAccessPropertiesQuickly() const
1336 {
1337     if (hasNonEnumerableProperties())
1338         return false;
1339     if (hasGetterSetterProperties())
1340         return false;
1341     if (isUncacheableDictionary())
1342         return false;
1343     return true;
1344 }
1345
1346 } // namespace JSC