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