Move all Structure out-of-line inline methods to StructureInlines.h
[WebKit-https.git] / Source / JavaScriptCore / runtime / Structure.cpp
1 /*
2  * Copyright (C) 2008, 2009, 2013 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 COMPUTER, 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 COMPUTER, 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 "JSObject.h"
31 #include "JSPropertyNameIterator.h"
32 #include "Lookup.h"
33 #include "PropertyNameArray.h"
34 #include "StructureChain.h"
35 #include "StructureRareDataInlines.h"
36 #include <wtf/RefCountedLeakCounter.h>
37 #include <wtf/RefPtr.h>
38 #include <wtf/Threading.h>
39
40 #define DUMP_STRUCTURE_ID_STATISTICS 0
41
42 #ifndef NDEBUG
43 #define DO_PROPERTYMAP_CONSTENCY_CHECK 0
44 #else
45 #define DO_PROPERTYMAP_CONSTENCY_CHECK 0
46 #endif
47
48 using namespace std;
49 using namespace WTF;
50
51 #if DUMP_PROPERTYMAP_STATS
52
53 int numProbes;
54 int numCollisions;
55 int numRehashes;
56 int numRemoves;
57
58 #endif
59
60 namespace JSC {
61
62 #if DUMP_STRUCTURE_ID_STATISTICS
63 static HashSet<Structure*>& liveStructureSet = *(new HashSet<Structure*>);
64 #endif
65
66 bool StructureTransitionTable::contains(StringImpl* rep, unsigned attributes) const
67 {
68     if (isUsingSingleSlot()) {
69         Structure* transition = singleTransition();
70         return transition && transition->m_nameInPrevious == rep && transition->m_attributesInPrevious == attributes;
71     }
72     return map()->get(make_pair(rep, attributes));
73 }
74
75 inline Structure* StructureTransitionTable::get(StringImpl* rep, unsigned attributes) const
76 {
77     if (isUsingSingleSlot()) {
78         Structure* transition = singleTransition();
79         return (transition && transition->m_nameInPrevious == rep && transition->m_attributesInPrevious == attributes) ? transition : 0;
80     }
81     return map()->get(make_pair(rep, attributes));
82 }
83
84 inline void StructureTransitionTable::add(JSGlobalData& globalData, Structure* structure)
85 {
86     if (isUsingSingleSlot()) {
87         Structure* existingTransition = singleTransition();
88
89         // This handles the first transition being added.
90         if (!existingTransition) {
91             setSingleTransition(globalData, structure);
92             return;
93         }
94
95         // This handles the second transition being added
96         // (or the first transition being despecified!)
97         setMap(new TransitionMap());
98         add(globalData, existingTransition);
99     }
100
101     // Add the structure to the map.
102
103     // Newer versions of the STL have an std::make_pair function that takes rvalue references.
104     // 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.
105     // See https://bugs.webkit.org/show_bug.cgi?id=59261 for more details
106     map()->set(make_pair(structure->m_nameInPrevious, +structure->m_attributesInPrevious), structure);
107 }
108
109 void Structure::dumpStatistics()
110 {
111 #if DUMP_STRUCTURE_ID_STATISTICS
112     unsigned numberLeaf = 0;
113     unsigned numberUsingSingleSlot = 0;
114     unsigned numberSingletons = 0;
115     unsigned numberWithPropertyMaps = 0;
116     unsigned totalPropertyMapsSize = 0;
117
118     HashSet<Structure*>::const_iterator end = liveStructureSet.end();
119     for (HashSet<Structure*>::const_iterator it = liveStructureSet.begin(); it != end; ++it) {
120         Structure* structure = *it;
121
122         switch (structure->m_transitionTable.size()) {
123             case 0:
124                 ++numberLeaf;
125                 if (!structure->previousID())
126                     ++numberSingletons;
127                 break;
128
129             case 1:
130                 ++numberUsingSingleSlot;
131                 break;
132         }
133
134         if (structure->m_propertyTable) {
135             ++numberWithPropertyMaps;
136             totalPropertyMapsSize += structure->m_propertyTable->sizeInMemory();
137         }
138     }
139
140     dataLogF("Number of live Structures: %d\n", liveStructureSet.size());
141     dataLogF("Number of Structures using the single item optimization for transition map: %d\n", numberUsingSingleSlot);
142     dataLogF("Number of Structures that are leaf nodes: %d\n", numberLeaf);
143     dataLogF("Number of Structures that singletons: %d\n", numberSingletons);
144     dataLogF("Number of Structures with PropertyMaps: %d\n", numberWithPropertyMaps);
145
146     dataLogF("Size of a single Structures: %d\n", static_cast<unsigned>(sizeof(Structure)));
147     dataLogF("Size of sum of all property maps: %d\n", totalPropertyMapsSize);
148     dataLogF("Size of average of all property maps: %f\n", static_cast<double>(totalPropertyMapsSize) / static_cast<double>(liveStructureSet.size()));
149 #else
150     dataLogF("Dumping Structure statistics is not enabled.\n");
151 #endif
152 }
153
154 Structure::Structure(JSGlobalData& globalData, JSGlobalObject* globalObject, JSValue prototype, const TypeInfo& typeInfo, const ClassInfo* classInfo, IndexingType indexingType, unsigned inlineCapacity)
155     : JSCell(globalData, globalData.structureStructure.get())
156     , m_typeInfo(typeInfo)
157     , m_indexingType(indexingType)
158     , m_globalObject(globalData, this, globalObject, WriteBarrier<JSGlobalObject>::MayBeNull)
159     , m_prototype(globalData, this, prototype)
160     , m_classInfo(classInfo)
161     , m_transitionWatchpointSet(InitializedWatching)
162     , m_inlineCapacity(inlineCapacity)
163     , m_offset(invalidOffset)
164     , m_dictionaryKind(NoneDictionaryKind)
165     , m_isPinnedPropertyTable(false)
166     , m_hasGetterSetterProperties(false)
167     , m_hasReadOnlyOrGetterSetterPropertiesExcludingProto(false)
168     , m_hasNonEnumerableProperties(false)
169     , m_attributesInPrevious(0)
170     , m_specificFunctionThrashCount(0)
171     , m_preventExtensions(false)
172     , m_didTransition(false)
173     , m_staticFunctionReified(false)
174 {
175     ASSERT(inlineCapacity <= JSFinalObject::maxInlineCapacity());
176     ASSERT(static_cast<PropertyOffset>(inlineCapacity) < firstOutOfLineOffset);
177     ASSERT(!typeInfo.structureHasRareData());
178 }
179
180 const ClassInfo Structure::s_info = { "Structure", 0, 0, 0, CREATE_METHOD_TABLE(Structure) };
181
182 Structure::Structure(JSGlobalData& globalData)
183     : JSCell(CreatingEarlyCell)
184     , m_typeInfo(CompoundType, OverridesVisitChildren)
185     , m_indexingType(0)
186     , m_prototype(globalData, this, jsNull())
187     , m_classInfo(&s_info)
188     , m_transitionWatchpointSet(InitializedWatching)
189     , m_inlineCapacity(0)
190     , m_offset(invalidOffset)
191     , m_dictionaryKind(NoneDictionaryKind)
192     , m_isPinnedPropertyTable(false)
193     , m_hasGetterSetterProperties(false)
194     , m_hasReadOnlyOrGetterSetterPropertiesExcludingProto(false)
195     , m_hasNonEnumerableProperties(false)
196     , m_attributesInPrevious(0)
197     , m_specificFunctionThrashCount(0)
198     , m_preventExtensions(false)
199     , m_didTransition(false)
200     , m_staticFunctionReified(false)
201 {
202 }
203
204 Structure::Structure(JSGlobalData& globalData, const Structure* previous)
205     : JSCell(globalData, globalData.structureStructure.get())
206     , m_typeInfo(previous->typeInfo())
207     , m_indexingType(previous->indexingTypeIncludingHistory())
208     , m_prototype(globalData, this, previous->storedPrototype())
209     , m_classInfo(previous->m_classInfo)
210     , m_transitionWatchpointSet(InitializedWatching)
211     , m_inlineCapacity(previous->m_inlineCapacity)
212     , m_offset(invalidOffset)
213     , m_dictionaryKind(previous->m_dictionaryKind)
214     , m_isPinnedPropertyTable(false)
215     , m_hasGetterSetterProperties(previous->m_hasGetterSetterProperties)
216     , m_hasReadOnlyOrGetterSetterPropertiesExcludingProto(previous->m_hasReadOnlyOrGetterSetterPropertiesExcludingProto)
217     , m_hasNonEnumerableProperties(previous->m_hasNonEnumerableProperties)
218     , m_attributesInPrevious(0)
219     , m_specificFunctionThrashCount(previous->m_specificFunctionThrashCount)
220     , m_preventExtensions(previous->m_preventExtensions)
221     , m_didTransition(true)
222     , m_staticFunctionReified(previous->m_staticFunctionReified)
223 {
224     previous->notifyTransitionFromThisStructure();
225     if (previous->m_globalObject)
226         m_globalObject.set(globalData, this, previous->m_globalObject.get());
227 }
228
229 void Structure::destroy(JSCell* cell)
230 {
231     static_cast<Structure*>(cell)->Structure::~Structure();
232 }
233
234 void Structure::materializePropertyMap(JSGlobalData& globalData)
235 {
236     ASSERT(structure()->classInfo() == &s_info);
237     ASSERT(!m_propertyTable);
238
239     Vector<Structure*, 8> structures;
240     structures.append(this);
241
242     Structure* structure = this;
243
244     // Search for the last Structure with a property table.
245     while ((structure = structure->previousID())) {
246         if (structure->m_isPinnedPropertyTable) {
247             ASSERT(structure->m_propertyTable);
248             ASSERT(!structure->previousID());
249
250             m_propertyTable = structure->m_propertyTable->copy(globalData, 0, numberOfSlotsForLastOffset(m_offset, m_inlineCapacity));
251             break;
252         }
253
254         structures.append(structure);
255     }
256
257     if (!m_propertyTable)
258         createPropertyMap(numberOfSlotsForLastOffset(m_offset, m_inlineCapacity));
259
260     for (ptrdiff_t i = structures.size() - 1; i >= 0; --i) {
261         structure = structures[i];
262         if (!structure->m_nameInPrevious)
263             continue;
264         PropertyMapEntry entry(globalData, this, structure->m_nameInPrevious.get(), structure->m_offset, structure->m_attributesInPrevious, structure->m_specificValueInPrevious.get());
265         m_propertyTable->add(entry, m_offset, PropertyTable::PropertyOffsetMustNotChange);
266     }
267     
268     checkOffsetConsistency();
269 }
270
271 inline size_t nextOutOfLineStorageCapacity(size_t currentCapacity)
272 {
273     if (!currentCapacity)
274         return initialOutOfLineCapacity;
275     return currentCapacity * outOfLineGrowthFactor;
276 }
277
278 size_t Structure::suggestedNewOutOfLineStorageCapacity()
279 {
280     return nextOutOfLineStorageCapacity(outOfLineCapacity());
281 }
282  
283 void Structure::despecifyDictionaryFunction(JSGlobalData& globalData, PropertyName propertyName)
284 {
285     StringImpl* rep = propertyName.uid();
286
287     materializePropertyMapIfNecessary(globalData);
288
289     ASSERT(isDictionary());
290     ASSERT(m_propertyTable);
291
292     PropertyMapEntry* entry = m_propertyTable->find(rep).first;
293     ASSERT(entry);
294     entry->specificValue.clear();
295 }
296
297 Structure* Structure::addPropertyTransitionToExistingStructure(Structure* structure, PropertyName propertyName, unsigned attributes, JSCell* specificValue, PropertyOffset& offset)
298 {
299     ASSERT(!structure->isDictionary());
300     ASSERT(structure->isObject());
301
302     if (Structure* existingTransition = structure->m_transitionTable.get(propertyName.uid(), attributes)) {
303         JSCell* specificValueInPrevious = existingTransition->m_specificValueInPrevious.get();
304         if (specificValueInPrevious && specificValueInPrevious != specificValue)
305             return 0;
306         validateOffset(existingTransition->m_offset, existingTransition->inlineCapacity());
307         offset = existingTransition->m_offset;
308         return existingTransition;
309     }
310
311     return 0;
312 }
313
314 bool Structure::anyObjectInChainMayInterceptIndexedAccesses() const
315 {
316     for (const Structure* current = this; ;) {
317         if (current->mayInterceptIndexedAccesses())
318             return true;
319         
320         JSValue prototype = current->storedPrototype();
321         if (prototype.isNull())
322             return false;
323         
324         current = asObject(prototype)->structure();
325     }
326 }
327
328 bool Structure::needsSlowPutIndexing() const
329 {
330     return anyObjectInChainMayInterceptIndexedAccesses()
331         || globalObject()->isHavingABadTime();
332 }
333
334 NonPropertyTransition Structure::suggestedArrayStorageTransition() const
335 {
336     if (needsSlowPutIndexing())
337         return AllocateSlowPutArrayStorage;
338     
339     return AllocateArrayStorage;
340 }
341
342 Structure* Structure::addPropertyTransition(JSGlobalData& globalData, Structure* structure, PropertyName propertyName, unsigned attributes, JSCell* specificValue, PropertyOffset& offset)
343 {
344     // If we have a specific function, we may have got to this point if there is
345     // already a transition with the correct property name and attributes, but
346     // specialized to a different function.  In this case we just want to give up
347     // and despecialize the transition.
348     // In this case we clear the value of specificFunction which will result
349     // in us adding a non-specific transition, and any subsequent lookup in
350     // Structure::addPropertyTransitionToExistingStructure will just use that.
351     if (specificValue && structure->m_transitionTable.contains(propertyName.uid(), attributes))
352         specificValue = 0;
353
354     ASSERT(!structure->isDictionary());
355     ASSERT(structure->isObject());
356     ASSERT(!Structure::addPropertyTransitionToExistingStructure(structure, propertyName, attributes, specificValue, offset));
357     
358     if (structure->m_specificFunctionThrashCount == maxSpecificFunctionThrashCount)
359         specificValue = 0;
360
361     if (structure->transitionCount() > s_maxTransitionLength) {
362         Structure* transition = toCacheableDictionaryTransition(globalData, structure);
363         ASSERT(structure != transition);
364         offset = transition->putSpecificValue(globalData, propertyName, attributes, specificValue);
365         return transition;
366     }
367     
368     Structure* transition = create(globalData, structure);
369
370     transition->m_cachedPrototypeChain.setMayBeNull(globalData, transition, structure->m_cachedPrototypeChain.get());
371     transition->setPreviousID(globalData, transition, structure);
372     transition->m_nameInPrevious = propertyName.uid();
373     transition->m_attributesInPrevious = attributes;
374     transition->m_specificValueInPrevious.setMayBeNull(globalData, transition, specificValue);
375
376     if (structure->m_propertyTable) {
377         structure->checkOffsetConsistency();
378         if (structure->m_isPinnedPropertyTable)
379             transition->m_propertyTable = structure->m_propertyTable->copy(globalData, transition, structure->m_propertyTable->size() + 1);
380         else
381             transition->m_propertyTable = structure->m_propertyTable.release();
382     } else {
383         if (structure->previousID())
384             transition->materializePropertyMap(globalData);
385         else
386             transition->createPropertyMap();
387     }
388     transition->m_offset = structure->m_offset;
389
390     offset = transition->putSpecificValue(globalData, propertyName, attributes, specificValue);
391
392     checkOffset(transition->m_offset, transition->inlineCapacity());
393     structure->m_transitionTable.add(globalData, transition);
394     transition->checkOffsetConsistency();
395     structure->checkOffsetConsistency();
396     return transition;
397 }
398
399 Structure* Structure::removePropertyTransition(JSGlobalData& globalData, Structure* structure, PropertyName propertyName, PropertyOffset& offset)
400 {
401     ASSERT(!structure->isUncacheableDictionary());
402
403     Structure* transition = toUncacheableDictionaryTransition(globalData, structure);
404
405     offset = transition->remove(propertyName);
406
407     transition->checkOffsetConsistency();
408     return transition;
409 }
410
411 Structure* Structure::changePrototypeTransition(JSGlobalData& globalData, Structure* structure, JSValue prototype)
412 {
413     Structure* transition = create(globalData, structure);
414
415     transition->m_prototype.set(globalData, transition, prototype);
416
417     structure->materializePropertyMapIfNecessary(globalData);
418     transition->m_propertyTable = structure->copyPropertyTableForPinning(globalData, transition);
419     transition->m_offset = structure->m_offset;
420     transition->pin();
421
422     transition->checkOffsetConsistency();
423     return transition;
424 }
425
426 Structure* Structure::despecifyFunctionTransition(JSGlobalData& globalData, Structure* structure, PropertyName replaceFunction)
427 {
428     ASSERT(structure->m_specificFunctionThrashCount < maxSpecificFunctionThrashCount);
429     Structure* transition = create(globalData, structure);
430
431     ++transition->m_specificFunctionThrashCount;
432
433     structure->materializePropertyMapIfNecessary(globalData);
434     transition->m_propertyTable = structure->copyPropertyTableForPinning(globalData, transition);
435     transition->m_offset = structure->m_offset;
436     transition->pin();
437
438     if (transition->m_specificFunctionThrashCount == maxSpecificFunctionThrashCount)
439         transition->despecifyAllFunctions(globalData);
440     else {
441         bool removed = transition->despecifyFunction(globalData, replaceFunction);
442         ASSERT_UNUSED(removed, removed);
443     }
444
445     transition->checkOffsetConsistency();
446     return transition;
447 }
448
449 Structure* Structure::attributeChangeTransition(JSGlobalData& globalData, Structure* structure, PropertyName propertyName, unsigned attributes)
450 {
451     if (!structure->isUncacheableDictionary()) {
452         Structure* transition = create(globalData, structure);
453
454         structure->materializePropertyMapIfNecessary(globalData);
455         transition->m_propertyTable = structure->copyPropertyTableForPinning(globalData, transition);
456         transition->m_offset = structure->m_offset;
457         transition->pin();
458         
459         structure = transition;
460     }
461
462     ASSERT(structure->m_propertyTable);
463     PropertyMapEntry* entry = structure->m_propertyTable->find(propertyName.uid()).first;
464     ASSERT(entry);
465     entry->attributes = attributes;
466
467     structure->checkOffsetConsistency();
468     return structure;
469 }
470
471 Structure* Structure::toDictionaryTransition(JSGlobalData& globalData, Structure* structure, DictionaryKind kind)
472 {
473     ASSERT(!structure->isUncacheableDictionary());
474     
475     Structure* transition = create(globalData, structure);
476
477     structure->materializePropertyMapIfNecessary(globalData);
478     transition->m_propertyTable = structure->copyPropertyTableForPinning(globalData, transition);
479     transition->m_offset = structure->m_offset;
480     transition->m_dictionaryKind = kind;
481     transition->pin();
482
483     transition->checkOffsetConsistency();
484     return transition;
485 }
486
487 Structure* Structure::toCacheableDictionaryTransition(JSGlobalData& globalData, Structure* structure)
488 {
489     return toDictionaryTransition(globalData, structure, CachedDictionaryKind);
490 }
491
492 Structure* Structure::toUncacheableDictionaryTransition(JSGlobalData& globalData, Structure* structure)
493 {
494     return toDictionaryTransition(globalData, structure, UncachedDictionaryKind);
495 }
496
497 // In future we may want to cache this transition.
498 Structure* Structure::sealTransition(JSGlobalData& globalData, Structure* structure)
499 {
500     Structure* transition = preventExtensionsTransition(globalData, structure);
501
502     if (transition->m_propertyTable) {
503         PropertyTable::iterator end = transition->m_propertyTable->end();
504         for (PropertyTable::iterator iter = transition->m_propertyTable->begin(); iter != end; ++iter)
505             iter->attributes |= DontDelete;
506     }
507
508     transition->checkOffsetConsistency();
509     return transition;
510 }
511
512 // In future we may want to cache this transition.
513 Structure* Structure::freezeTransition(JSGlobalData& globalData, Structure* structure)
514 {
515     Structure* transition = preventExtensionsTransition(globalData, structure);
516
517     if (transition->m_propertyTable) {
518         PropertyTable::iterator iter = transition->m_propertyTable->begin();
519         PropertyTable::iterator end = transition->m_propertyTable->end();
520         if (iter != end)
521             transition->m_hasReadOnlyOrGetterSetterPropertiesExcludingProto = true;
522         for (; iter != end; ++iter)
523             iter->attributes |= iter->attributes & Accessor ? DontDelete : (DontDelete | ReadOnly);
524     }
525
526     transition->checkOffsetConsistency();
527     return transition;
528 }
529
530 // In future we may want to cache this transition.
531 Structure* Structure::preventExtensionsTransition(JSGlobalData& globalData, Structure* structure)
532 {
533     Structure* transition = create(globalData, structure);
534
535     // Don't set m_offset, as one can not transition to this.
536
537     structure->materializePropertyMapIfNecessary(globalData);
538     transition->m_propertyTable = structure->copyPropertyTableForPinning(globalData, transition);
539     transition->m_offset = structure->m_offset;
540     transition->m_preventExtensions = true;
541     transition->pin();
542
543     transition->checkOffsetConsistency();
544     return transition;
545 }
546
547 Structure* Structure::nonPropertyTransition(JSGlobalData& globalData, Structure* structure, NonPropertyTransition transitionKind)
548 {
549     unsigned attributes = toAttributes(transitionKind);
550     IndexingType indexingType = newIndexingType(structure->indexingTypeIncludingHistory(), transitionKind);
551     
552     if (JSGlobalObject* globalObject = structure->m_globalObject.get()) {
553         if (globalObject->isOriginalArrayStructure(structure)) {
554             Structure* result = globalObject->originalArrayStructureForIndexingType(indexingType);
555             if (result->indexingTypeIncludingHistory() == indexingType) {
556                 structure->notifyTransitionFromThisStructure();
557                 return result;
558             }
559         }
560     }
561     
562     if (Structure* existingTransition = structure->m_transitionTable.get(0, attributes)) {
563         ASSERT(existingTransition->m_attributesInPrevious == attributes);
564         ASSERT(existingTransition->indexingTypeIncludingHistory() == indexingType);
565         return existingTransition;
566     }
567     
568     Structure* transition = create(globalData, structure);
569     transition->setPreviousID(globalData, transition, structure);
570     transition->m_attributesInPrevious = attributes;
571     transition->m_indexingType = indexingType;
572     transition->m_offset = structure->m_offset;
573     checkOffset(transition->m_offset, transition->inlineCapacity());
574     
575     if (structure->m_propertyTable) {
576         structure->checkOffsetConsistency();
577         if (structure->m_isPinnedPropertyTable)
578             transition->m_propertyTable = structure->m_propertyTable->copy(globalData, transition, structure->m_propertyTable->size() + 1);
579         else
580             transition->m_propertyTable = structure->m_propertyTable.release();
581     } else {
582         if (structure->previousID())
583             transition->materializePropertyMap(globalData);
584         else
585             transition->createPropertyMap();
586     }
587     
588     structure->m_transitionTable.add(globalData, transition);
589     transition->checkOffsetConsistency();
590     return transition;
591 }
592
593 // In future we may want to cache this property.
594 bool Structure::isSealed(JSGlobalData& globalData)
595 {
596     if (isExtensible())
597         return false;
598
599     materializePropertyMapIfNecessary(globalData);
600     if (!m_propertyTable)
601         return true;
602
603     PropertyTable::iterator end = m_propertyTable->end();
604     for (PropertyTable::iterator iter = m_propertyTable->begin(); iter != end; ++iter) {
605         if ((iter->attributes & DontDelete) != DontDelete)
606             return false;
607     }
608     return true;
609 }
610
611 // In future we may want to cache this property.
612 bool Structure::isFrozen(JSGlobalData& globalData)
613 {
614     if (isExtensible())
615         return false;
616
617     materializePropertyMapIfNecessary(globalData);
618     if (!m_propertyTable)
619         return true;
620
621     PropertyTable::iterator end = m_propertyTable->end();
622     for (PropertyTable::iterator iter = m_propertyTable->begin(); iter != end; ++iter) {
623         if (!(iter->attributes & DontDelete))
624             return false;
625         if (!(iter->attributes & (ReadOnly | Accessor)))
626             return false;
627     }
628     return true;
629 }
630
631 Structure* Structure::flattenDictionaryStructure(JSGlobalData& globalData, JSObject* object)
632 {
633     checkOffsetConsistency();
634     ASSERT(isDictionary());
635     if (isUncacheableDictionary()) {
636         ASSERT(m_propertyTable);
637
638         size_t propertyCount = m_propertyTable->size();
639
640         // Holds our values compacted by insertion order.
641         Vector<JSValue> values(propertyCount);
642
643         // Copies out our values from their hashed locations, compacting property table offsets as we go.
644         unsigned i = 0;
645         PropertyTable::iterator end = m_propertyTable->end();
646         for (PropertyTable::iterator iter = m_propertyTable->begin(); iter != end; ++iter, ++i) {
647             values[i] = object->getDirect(iter->offset);
648             m_offset = iter->offset = offsetForPropertyNumber(i, m_inlineCapacity);
649         }
650         
651         // Copies in our values to their compacted locations.
652         for (unsigned i = 0; i < propertyCount; i++)
653             object->putDirect(globalData, offsetForPropertyNumber(i, m_inlineCapacity), values[i]);
654
655         m_propertyTable->clearDeletedOffsets();
656         checkOffsetConsistency();
657     }
658
659     m_dictionaryKind = NoneDictionaryKind;
660     return this;
661 }
662
663 PropertyOffset Structure::addPropertyWithoutTransition(JSGlobalData& globalData, PropertyName propertyName, unsigned attributes, JSCell* specificValue)
664 {
665     ASSERT(!enumerationCache());
666
667     if (m_specificFunctionThrashCount == maxSpecificFunctionThrashCount)
668         specificValue = 0;
669
670     materializePropertyMapIfNecessaryForPinning(globalData);
671     
672     pin();
673
674     return putSpecificValue(globalData, propertyName, attributes, specificValue);
675 }
676
677 PropertyOffset Structure::removePropertyWithoutTransition(JSGlobalData& globalData, PropertyName propertyName)
678 {
679     ASSERT(isUncacheableDictionary());
680     ASSERT(!enumerationCache());
681
682     materializePropertyMapIfNecessaryForPinning(globalData);
683
684     pin();
685     return remove(propertyName);
686 }
687
688 void Structure::pin()
689 {
690     ASSERT(m_propertyTable);
691     m_isPinnedPropertyTable = true;
692     clearPreviousID();
693     m_nameInPrevious.clear();
694 }
695
696 void Structure::allocateRareData(JSGlobalData& globalData)
697 {
698     ASSERT(!typeInfo().structureHasRareData());
699     StructureRareData* rareData = StructureRareData::create(globalData, previous());
700     m_typeInfo = TypeInfo(typeInfo().type(), typeInfo().flags() | StructureHasRareData);
701     m_previousOrRareData.set(globalData, this, rareData);
702 }
703
704 void Structure::cloneRareDataFrom(JSGlobalData& globalData, const Structure* other)
705 {
706     ASSERT(other->typeInfo().structureHasRareData());
707     StructureRareData* newRareData = StructureRareData::clone(globalData, other->rareData());
708     m_previousOrRareData.set(globalData, this, newRareData);
709 }
710
711 #if DUMP_PROPERTYMAP_STATS
712
713 struct PropertyMapStatisticsExitLogger {
714     ~PropertyMapStatisticsExitLogger();
715 };
716
717 static PropertyMapStatisticsExitLogger logger;
718
719 PropertyMapStatisticsExitLogger::~PropertyMapStatisticsExitLogger()
720 {
721     dataLogF("\nJSC::PropertyMap statistics\n\n");
722     dataLogF("%d probes\n", numProbes);
723     dataLogF("%d collisions (%.1f%%)\n", numCollisions, 100.0 * numCollisions / numProbes);
724     dataLogF("%d rehashes\n", numRehashes);
725     dataLogF("%d removes\n", numRemoves);
726 }
727
728 #endif
729
730 #if !DO_PROPERTYMAP_CONSTENCY_CHECK
731
732 inline void Structure::checkConsistency()
733 {
734     checkOffsetConsistency();
735 }
736
737 #endif
738
739 PassOwnPtr<PropertyTable> Structure::copyPropertyTable(JSGlobalData& globalData, Structure* owner)
740 {
741     return adoptPtr(m_propertyTable ? new PropertyTable(globalData, owner, *m_propertyTable) : 0);
742 }
743
744 PassOwnPtr<PropertyTable> Structure::copyPropertyTableForPinning(JSGlobalData& globalData, Structure* owner)
745 {
746     return adoptPtr(m_propertyTable ? new PropertyTable(globalData, owner, *m_propertyTable) : new PropertyTable(numberOfSlotsForLastOffset(m_offset, m_inlineCapacity)));
747 }
748
749 PropertyOffset Structure::get(JSGlobalData& globalData, PropertyName propertyName, unsigned& attributes, JSCell*& specificValue)
750 {
751     ASSERT(structure()->classInfo() == &s_info);
752
753     materializePropertyMapIfNecessary(globalData);
754     if (!m_propertyTable)
755         return invalidOffset;
756
757     PropertyMapEntry* entry = m_propertyTable->find(propertyName.uid()).first;
758     if (!entry)
759         return invalidOffset;
760
761     attributes = entry->attributes;
762     specificValue = entry->specificValue.get();
763     return entry->offset;
764 }
765
766 bool Structure::despecifyFunction(JSGlobalData& globalData, PropertyName propertyName)
767 {
768     materializePropertyMapIfNecessary(globalData);
769     if (!m_propertyTable)
770         return false;
771
772     PropertyMapEntry* entry = m_propertyTable->find(propertyName.uid()).first;
773     if (!entry)
774         return false;
775
776     ASSERT(entry->specificValue);
777     entry->specificValue.clear();
778     return true;
779 }
780
781 void Structure::despecifyAllFunctions(JSGlobalData& globalData)
782 {
783     materializePropertyMapIfNecessary(globalData);
784     if (!m_propertyTable)
785         return;
786
787     PropertyTable::iterator end = m_propertyTable->end();
788     for (PropertyTable::iterator iter = m_propertyTable->begin(); iter != end; ++iter)
789         iter->specificValue.clear();
790 }
791
792 PropertyOffset Structure::putSpecificValue(JSGlobalData& globalData, PropertyName propertyName, unsigned attributes, JSCell* specificValue)
793 {
794     ASSERT(!JSC::isValidOffset(get(globalData, propertyName)));
795
796     checkConsistency();
797     if (attributes & DontEnum)
798         m_hasNonEnumerableProperties = true;
799
800     StringImpl* rep = propertyName.uid();
801
802     if (!m_propertyTable)
803         createPropertyMap();
804
805     PropertyOffset newOffset = m_propertyTable->nextOffset(m_inlineCapacity);
806
807     m_propertyTable->add(PropertyMapEntry(globalData, this, rep, newOffset, attributes, specificValue), m_offset, PropertyTable::PropertyOffsetMayChange);
808     
809     checkConsistency();
810     return newOffset;
811 }
812
813 PropertyOffset Structure::remove(PropertyName propertyName)
814 {
815     checkConsistency();
816
817     StringImpl* rep = propertyName.uid();
818
819     if (!m_propertyTable)
820         return invalidOffset;
821
822     PropertyTable::find_iterator position = m_propertyTable->find(rep);
823     if (!position.first)
824         return invalidOffset;
825
826     PropertyOffset offset = position.first->offset;
827
828     m_propertyTable->remove(position);
829     m_propertyTable->addDeletedOffset(offset);
830
831     checkConsistency();
832     return offset;
833 }
834
835 void Structure::createPropertyMap(unsigned capacity)
836 {
837     ASSERT(!m_propertyTable);
838
839     checkConsistency();
840     m_propertyTable = adoptPtr(new PropertyTable(capacity));
841 }
842
843 void Structure::getPropertyNamesFromStructure(JSGlobalData& globalData, PropertyNameArray& propertyNames, EnumerationMode mode)
844 {
845     materializePropertyMapIfNecessary(globalData);
846     if (!m_propertyTable)
847         return;
848
849     bool knownUnique = !propertyNames.size();
850
851     PropertyTable::iterator end = m_propertyTable->end();
852     for (PropertyTable::iterator iter = m_propertyTable->begin(); iter != end; ++iter) {
853         ASSERT(m_hasNonEnumerableProperties || !(iter->attributes & DontEnum));
854         if (iter->key->isIdentifier() && (!(iter->attributes & DontEnum) || mode == IncludeDontEnumProperties)) {
855             if (knownUnique)
856                 propertyNames.addKnownUnique(iter->key);
857             else
858                 propertyNames.add(iter->key);
859         }
860     }
861 }
862
863 JSValue Structure::prototypeForLookup(CodeBlock* codeBlock) const
864 {
865     return prototypeForLookup(codeBlock->globalObject());
866 }
867
868 void Structure::visitChildren(JSCell* cell, SlotVisitor& visitor)
869 {
870     Structure* thisObject = jsCast<Structure*>(cell);
871     ASSERT_GC_OBJECT_INHERITS(thisObject, &s_info);
872     ASSERT(thisObject->structure()->typeInfo().overridesVisitChildren());
873
874     JSCell::visitChildren(thisObject, visitor);
875     visitor.append(&thisObject->m_globalObject);
876     if (!thisObject->isObject())
877         thisObject->m_cachedPrototypeChain.clear();
878     else {
879         visitor.append(&thisObject->m_prototype);
880         visitor.append(&thisObject->m_cachedPrototypeChain);
881     }
882     visitor.append(&thisObject->m_previousOrRareData);
883     visitor.append(&thisObject->m_specificValueInPrevious);
884     if (thisObject->m_propertyTable) {
885         PropertyTable::iterator end = thisObject->m_propertyTable->end();
886         for (PropertyTable::iterator ptr = thisObject->m_propertyTable->begin(); ptr != end; ++ptr)
887             visitor.append(&ptr->specificValue);
888     }
889 }
890
891 bool Structure::prototypeChainMayInterceptStoreTo(JSGlobalData& globalData, PropertyName propertyName)
892 {
893     unsigned i = propertyName.asIndex();
894     if (i != PropertyName::NotAnIndex)
895         return anyObjectInChainMayInterceptIndexedAccesses();
896     
897     for (Structure* current = this; ;) {
898         JSValue prototype = current->storedPrototype();
899         if (prototype.isNull())
900             return false;
901         
902         current = prototype.asCell()->structure();
903         
904         unsigned attributes;
905         JSCell* specificValue;
906         PropertyOffset offset = current->get(globalData, propertyName, attributes, specificValue);
907         if (!JSC::isValidOffset(offset))
908             continue;
909         
910         if (attributes & (ReadOnly | Accessor))
911             return true;
912         
913         return false;
914     }
915 }
916
917 #if DO_PROPERTYMAP_CONSTENCY_CHECK
918
919 void PropertyTable::checkConsistency()
920 {
921     checkOffsetConsistency();
922     ASSERT(m_indexSize >= PropertyTable::MinimumTableSize);
923     ASSERT(m_indexMask);
924     ASSERT(m_indexSize == m_indexMask + 1);
925     ASSERT(!(m_indexSize & m_indexMask));
926
927     ASSERT(m_keyCount <= m_indexSize / 2);
928     ASSERT(m_keyCount + m_deletedCount <= m_indexSize / 2);
929     ASSERT(m_deletedCount <= m_indexSize / 4);
930
931     unsigned indexCount = 0;
932     unsigned deletedIndexCount = 0;
933     for (unsigned a = 0; a != m_indexSize; ++a) {
934         unsigned entryIndex = m_index[a];
935         if (entryIndex == PropertyTable::EmptyEntryIndex)
936             continue;
937         if (entryIndex == deletedEntryIndex()) {
938             ++deletedIndexCount;
939             continue;
940         }
941         ASSERT(entryIndex < deletedEntryIndex());
942         ASSERT(entryIndex - 1 <= usedCount());
943         ++indexCount;
944
945         for (unsigned b = a + 1; b != m_indexSize; ++b)
946             ASSERT(m_index[b] != entryIndex);
947     }
948     ASSERT(indexCount == m_keyCount);
949     ASSERT(deletedIndexCount == m_deletedCount);
950
951     ASSERT(!table()[deletedEntryIndex() - 1].key);
952
953     unsigned nonEmptyEntryCount = 0;
954     for (unsigned c = 0; c < usedCount(); ++c) {
955         StringImpl* rep = table()[c].key;
956         if (rep == PROPERTY_MAP_DELETED_ENTRY_KEY)
957             continue;
958         ++nonEmptyEntryCount;
959         unsigned i = rep->existingHash();
960         unsigned k = 0;
961         unsigned entryIndex;
962         while (1) {
963             entryIndex = m_index[i & m_indexMask];
964             ASSERT(entryIndex != PropertyTable::EmptyEntryIndex);
965             if (rep == table()[entryIndex - 1].key)
966                 break;
967             if (k == 0)
968                 k = 1 | doubleHash(rep->existingHash());
969             i += k;
970         }
971         ASSERT(entryIndex == c + 1);
972     }
973
974     ASSERT(nonEmptyEntryCount == m_keyCount);
975 }
976
977 void Structure::checkConsistency()
978 {
979     if (!m_propertyTable)
980         return;
981
982     if (!m_hasNonEnumerableProperties) {
983         PropertyTable::iterator end = m_propertyTable->end();
984         for (PropertyTable::iterator iter = m_propertyTable->begin(); iter != end; ++iter) {
985             ASSERT(!(iter->attributes & DontEnum));
986         }
987     }
988
989     m_propertyTable->checkConsistency();
990 }
991
992 #endif // DO_PROPERTYMAP_CONSTENCY_CHECK
993
994 } // namespace JSC