47c2ed10a0b7e30c894f6645bcd899aecb580749
[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(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, unsigned 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     ASSERT(inlineCapacity <= JSFinalObject::maxInlineCapacity());
175     ASSERT(inlineCapacity < firstOutOfLineOffset);
176 }
177
178 const ClassInfo Structure::s_info = { "Structure", 0, 0, 0, CREATE_METHOD_TABLE(Structure) };
179
180 Structure::Structure(JSGlobalData& globalData)
181     : JSCell(CreatingEarlyCell)
182     , m_typeInfo(CompoundType, OverridesVisitChildren)
183     , m_indexingType(0)
184     , m_prototype(globalData, this, jsNull())
185     , m_classInfo(&s_info)
186     , m_transitionWatchpointSet(InitializedWatching)
187     , m_outOfLineCapacity(0)
188     , m_inlineCapacity(0)
189     , m_offset(invalidOffset)
190     , m_dictionaryKind(NoneDictionaryKind)
191     , m_isPinnedPropertyTable(false)
192     , m_hasGetterSetterProperties(false)
193     , m_hasReadOnlyOrGetterSetterPropertiesExcludingProto(false)
194     , m_hasNonEnumerableProperties(false)
195     , m_attributesInPrevious(0)
196     , m_specificFunctionThrashCount(0)
197     , m_preventExtensions(false)
198     , m_didTransition(false)
199     , m_staticFunctionReified(false)
200 {
201 }
202
203 Structure::Structure(JSGlobalData& globalData, const Structure* previous)
204     : JSCell(globalData, globalData.structureStructure.get())
205     , m_typeInfo(previous->typeInfo())
206     , m_indexingType(previous->indexingTypeIncludingHistory())
207     , m_prototype(globalData, this, previous->storedPrototype())
208     , m_classInfo(previous->m_classInfo)
209     , m_transitionWatchpointSet(InitializedWatching)
210     , m_outOfLineCapacity(previous->m_outOfLineCapacity)
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->m_previous);
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() - 2; 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);
266     }
267 }
268
269 inline size_t nextOutOfLineStorageCapacity(size_t currentCapacity)
270 {
271     if (!currentCapacity)
272         return initialOutOfLineCapacity;
273     return currentCapacity * outOfLineGrowthFactor;
274 }
275
276 void Structure::growOutOfLineCapacity()
277 {
278     m_outOfLineCapacity = nextOutOfLineStorageCapacity(m_outOfLineCapacity);
279 }
280
281 size_t Structure::suggestedNewOutOfLineStorageCapacity()
282 {
283     return nextOutOfLineStorageCapacity(m_outOfLineCapacity);
284 }
285  
286 void Structure::despecifyDictionaryFunction(JSGlobalData& globalData, PropertyName propertyName)
287 {
288     StringImpl* rep = propertyName.uid();
289
290     materializePropertyMapIfNecessary(globalData);
291
292     ASSERT(isDictionary());
293     ASSERT(m_propertyTable);
294
295     PropertyMapEntry* entry = m_propertyTable->find(rep).first;
296     ASSERT(entry);
297     entry->specificValue.clear();
298 }
299
300 Structure* Structure::addPropertyTransitionToExistingStructure(Structure* structure, PropertyName propertyName, unsigned attributes, JSCell* specificValue, PropertyOffset& offset)
301 {
302     ASSERT(!structure->isDictionary());
303     ASSERT(structure->isObject());
304
305     if (Structure* existingTransition = structure->m_transitionTable.get(propertyName.uid(), attributes)) {
306         JSCell* specificValueInPrevious = existingTransition->m_specificValueInPrevious.get();
307         if (specificValueInPrevious && specificValueInPrevious != specificValue)
308             return 0;
309         validateOffset(existingTransition->m_offset, existingTransition->inlineCapacity());
310         offset = existingTransition->m_offset;
311         return existingTransition;
312     }
313
314     return 0;
315 }
316
317 bool Structure::anyObjectInChainMayInterceptIndexedAccesses() const
318 {
319     for (const Structure* current = this; ;) {
320         if (current->mayInterceptIndexedAccesses())
321             return true;
322         
323         JSValue prototype = current->storedPrototype();
324         if (prototype.isNull())
325             return false;
326         
327         current = asObject(prototype)->structure();
328     }
329 }
330
331 bool Structure::needsSlowPutIndexing() const
332 {
333     return anyObjectInChainMayInterceptIndexedAccesses()
334         || globalObject()->isHavingABadTime();
335 }
336
337 NonPropertyTransition Structure::suggestedArrayStorageTransition() const
338 {
339     if (needsSlowPutIndexing())
340         return AllocateSlowPutArrayStorage;
341     
342     return AllocateArrayStorage;
343 }
344
345 Structure* Structure::addPropertyTransition(JSGlobalData& globalData, Structure* structure, PropertyName propertyName, unsigned attributes, JSCell* specificValue, PropertyOffset& offset)
346 {
347     // If we have a specific function, we may have got to this point if there is
348     // already a transition with the correct property name and attributes, but
349     // specialized to a different function.  In this case we just want to give up
350     // and despecialize the transition.
351     // In this case we clear the value of specificFunction which will result
352     // in us adding a non-specific transition, and any subsequent lookup in
353     // Structure::addPropertyTransitionToExistingStructure will just use that.
354     if (specificValue && structure->m_transitionTable.contains(propertyName.uid(), attributes))
355         specificValue = 0;
356
357     ASSERT(!structure->isDictionary());
358     ASSERT(structure->isObject());
359     ASSERT(!Structure::addPropertyTransitionToExistingStructure(structure, propertyName, attributes, specificValue, offset));
360     
361     if (structure->m_specificFunctionThrashCount == maxSpecificFunctionThrashCount)
362         specificValue = 0;
363
364     if (structure->transitionCount() > s_maxTransitionLength) {
365         Structure* transition = toCacheableDictionaryTransition(globalData, structure);
366         ASSERT(structure != transition);
367         offset = transition->putSpecificValue(globalData, propertyName, attributes, specificValue);
368         if (transition->outOfLineSize() > transition->outOfLineCapacity())
369             transition->growOutOfLineCapacity();
370         return transition;
371     }
372     
373     Structure* transition = create(globalData, structure);
374
375     transition->m_cachedPrototypeChain.setMayBeNull(globalData, transition, structure->m_cachedPrototypeChain.get());
376     transition->m_previous.set(globalData, transition, structure);
377     transition->m_nameInPrevious = propertyName.uid();
378     transition->m_attributesInPrevious = attributes;
379     transition->m_specificValueInPrevious.setMayBeNull(globalData, transition, specificValue);
380
381     if (structure->m_propertyTable) {
382         if (structure->m_isPinnedPropertyTable)
383             transition->m_propertyTable = structure->m_propertyTable->copy(globalData, transition, structure->m_propertyTable->size() + 1);
384         else
385             transition->m_propertyTable = structure->m_propertyTable.release();
386     } else {
387         if (structure->m_previous)
388             transition->materializePropertyMap(globalData);
389         else
390             transition->createPropertyMap();
391     }
392
393     offset = transition->putSpecificValue(globalData, propertyName, attributes, specificValue);
394     if (transition->outOfLineSize() > transition->outOfLineCapacity())
395         transition->growOutOfLineCapacity();
396
397     transition->m_offset = offset;
398     checkOffset(transition->m_offset, transition->inlineCapacity());
399     structure->m_transitionTable.add(globalData, transition);
400     return transition;
401 }
402
403 Structure* Structure::removePropertyTransition(JSGlobalData& globalData, Structure* structure, PropertyName propertyName, PropertyOffset& offset)
404 {
405     ASSERT(!structure->isUncacheableDictionary());
406
407     Structure* transition = toUncacheableDictionaryTransition(globalData, structure);
408
409     offset = transition->remove(propertyName);
410
411     return transition;
412 }
413
414 Structure* Structure::changePrototypeTransition(JSGlobalData& globalData, Structure* structure, JSValue prototype)
415 {
416     Structure* transition = create(globalData, structure);
417
418     transition->m_prototype.set(globalData, transition, prototype);
419
420     // Don't set m_offset, as one can not transition to this.
421
422     structure->materializePropertyMapIfNecessary(globalData);
423     transition->m_propertyTable = structure->copyPropertyTableForPinning(globalData, transition);
424     transition->pin();
425
426     return transition;
427 }
428
429 Structure* Structure::despecifyFunctionTransition(JSGlobalData& globalData, Structure* structure, PropertyName replaceFunction)
430 {
431     ASSERT(structure->m_specificFunctionThrashCount < maxSpecificFunctionThrashCount);
432     Structure* transition = create(globalData, structure);
433
434     ++transition->m_specificFunctionThrashCount;
435
436     // Don't set m_offset, as one can not transition to this.
437
438     structure->materializePropertyMapIfNecessary(globalData);
439     transition->m_propertyTable = structure->copyPropertyTableForPinning(globalData, transition);
440     transition->pin();
441
442     if (transition->m_specificFunctionThrashCount == maxSpecificFunctionThrashCount)
443         transition->despecifyAllFunctions(globalData);
444     else {
445         bool removed = transition->despecifyFunction(globalData, replaceFunction);
446         ASSERT_UNUSED(removed, removed);
447     }
448
449     return transition;
450 }
451
452 Structure* Structure::attributeChangeTransition(JSGlobalData& globalData, Structure* structure, PropertyName propertyName, unsigned attributes)
453 {
454     if (!structure->isUncacheableDictionary()) {
455         Structure* transition = create(globalData, structure);
456
457         // Don't set m_offset, as one can not transition to this.
458
459         structure->materializePropertyMapIfNecessary(globalData);
460         transition->m_propertyTable = structure->copyPropertyTableForPinning(globalData, transition);
461         transition->pin();
462         
463         structure = transition;
464     }
465
466     ASSERT(structure->m_propertyTable);
467     PropertyMapEntry* entry = structure->m_propertyTable->find(propertyName.uid()).first;
468     ASSERT(entry);
469     entry->attributes = attributes;
470
471     return structure;
472 }
473
474 Structure* Structure::toDictionaryTransition(JSGlobalData& globalData, Structure* structure, DictionaryKind kind)
475 {
476     ASSERT(!structure->isUncacheableDictionary());
477     
478     Structure* transition = create(globalData, structure);
479
480     structure->materializePropertyMapIfNecessary(globalData);
481     transition->m_propertyTable = structure->copyPropertyTableForPinning(globalData, transition);
482     transition->m_dictionaryKind = kind;
483     transition->pin();
484
485     return transition;
486 }
487
488 Structure* Structure::toCacheableDictionaryTransition(JSGlobalData& globalData, Structure* structure)
489 {
490     return toDictionaryTransition(globalData, structure, CachedDictionaryKind);
491 }
492
493 Structure* Structure::toUncacheableDictionaryTransition(JSGlobalData& globalData, Structure* structure)
494 {
495     return toDictionaryTransition(globalData, structure, UncachedDictionaryKind);
496 }
497
498 // In future we may want to cache this transition.
499 Structure* Structure::sealTransition(JSGlobalData& globalData, Structure* structure)
500 {
501     Structure* transition = preventExtensionsTransition(globalData, structure);
502
503     if (transition->m_propertyTable) {
504         PropertyTable::iterator end = transition->m_propertyTable->end();
505         for (PropertyTable::iterator iter = transition->m_propertyTable->begin(); iter != end; ++iter)
506             iter->attributes |= DontDelete;
507     }
508
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     return transition;
527 }
528
529 // In future we may want to cache this transition.
530 Structure* Structure::preventExtensionsTransition(JSGlobalData& globalData, Structure* structure)
531 {
532     Structure* transition = create(globalData, structure);
533
534     // Don't set m_offset, as one can not transition to this.
535
536     structure->materializePropertyMapIfNecessary(globalData);
537     transition->m_propertyTable = structure->copyPropertyTableForPinning(globalData, transition);
538     transition->m_preventExtensions = true;
539     transition->pin();
540
541     return transition;
542 }
543
544 Structure* Structure::nonPropertyTransition(JSGlobalData& globalData, Structure* structure, NonPropertyTransition transitionKind)
545 {
546     unsigned attributes = toAttributes(transitionKind);
547     IndexingType indexingType = newIndexingType(structure->indexingTypeIncludingHistory(), transitionKind);
548     
549     if (JSGlobalObject* globalObject = structure->m_globalObject.get()) {
550         if (globalObject->isOriginalArrayStructure(structure)) {
551             Structure* result = globalObject->originalArrayStructureForIndexingType(indexingType);
552             if (result->indexingTypeIncludingHistory() == indexingType) {
553                 structure->notifyTransitionFromThisStructure();
554                 return result;
555             }
556         }
557     }
558     
559     if (Structure* existingTransition = structure->m_transitionTable.get(0, attributes)) {
560         ASSERT(existingTransition->m_attributesInPrevious == attributes);
561         ASSERT(existingTransition->indexingTypeIncludingHistory() == indexingType);
562         return existingTransition;
563     }
564     
565     Structure* transition = create(globalData, structure);
566     transition->m_previous.set(globalData, transition, structure);
567     transition->m_attributesInPrevious = attributes;
568     transition->m_indexingType = indexingType;
569     transition->m_offset = structure->m_offset;
570     checkOffset(transition->m_offset, transition->inlineCapacity());
571     
572     if (structure->m_propertyTable) {
573         if (structure->m_isPinnedPropertyTable)
574             transition->m_propertyTable = structure->m_propertyTable->copy(globalData, transition, structure->m_propertyTable->size() + 1);
575         else
576             transition->m_propertyTable = structure->m_propertyTable.release();
577     } else {
578         if (structure->m_previous)
579             transition->materializePropertyMap(globalData);
580         else
581             transition->createPropertyMap();
582     }
583     
584     structure->m_transitionTable.add(globalData, transition);
585     return transition;
586 }
587
588 // In future we may want to cache this property.
589 bool Structure::isSealed(JSGlobalData& globalData)
590 {
591     if (isExtensible())
592         return false;
593
594     materializePropertyMapIfNecessary(globalData);
595     if (!m_propertyTable)
596         return true;
597
598     PropertyTable::iterator end = m_propertyTable->end();
599     for (PropertyTable::iterator iter = m_propertyTable->begin(); iter != end; ++iter) {
600         if ((iter->attributes & DontDelete) != DontDelete)
601             return false;
602     }
603     return true;
604 }
605
606 // In future we may want to cache this property.
607 bool Structure::isFrozen(JSGlobalData& globalData)
608 {
609     if (isExtensible())
610         return false;
611
612     materializePropertyMapIfNecessary(globalData);
613     if (!m_propertyTable)
614         return true;
615
616     PropertyTable::iterator end = m_propertyTable->end();
617     for (PropertyTable::iterator iter = m_propertyTable->begin(); iter != end; ++iter) {
618         if (!(iter->attributes & DontDelete))
619             return false;
620         if (!(iter->attributes & (ReadOnly | Accessor)))
621             return false;
622     }
623     return true;
624 }
625
626 Structure* Structure::flattenDictionaryStructure(JSGlobalData& globalData, JSObject* object)
627 {
628     ASSERT(isDictionary());
629     if (isUncacheableDictionary()) {
630         ASSERT(m_propertyTable);
631
632         size_t propertyCount = m_propertyTable->size();
633
634         // Holds our values compacted by insertion order.
635         Vector<JSValue> values(propertyCount);
636
637         // Copies out our values from their hashed locations, compacting property table offsets as we go.
638         unsigned i = 0;
639         PropertyTable::iterator end = m_propertyTable->end();
640         for (PropertyTable::iterator iter = m_propertyTable->begin(); iter != end; ++iter, ++i) {
641             values[i] = object->getDirect(iter->offset);
642             iter->offset = offsetForPropertyNumber(i, m_inlineCapacity);
643         }
644         
645         // Copies in our values to their compacted locations.
646         for (unsigned i = 0; i < propertyCount; i++)
647             object->putDirect(globalData, offsetForPropertyNumber(i, m_inlineCapacity), values[i]);
648
649         m_propertyTable->clearDeletedOffsets();
650     }
651
652     m_dictionaryKind = NoneDictionaryKind;
653     return this;
654 }
655
656 PropertyOffset Structure::addPropertyWithoutTransition(JSGlobalData& globalData, PropertyName propertyName, unsigned attributes, JSCell* specificValue)
657 {
658     ASSERT(!m_enumerationCache);
659
660     if (m_specificFunctionThrashCount == maxSpecificFunctionThrashCount)
661         specificValue = 0;
662
663     materializePropertyMapIfNecessaryForPinning(globalData);
664     
665     pin();
666
667     PropertyOffset offset = putSpecificValue(globalData, propertyName, attributes, specificValue);
668     if (outOfLineSize() > outOfLineCapacity())
669         growOutOfLineCapacity();
670     return offset;
671 }
672
673 PropertyOffset Structure::removePropertyWithoutTransition(JSGlobalData& globalData, PropertyName propertyName)
674 {
675     ASSERT(isUncacheableDictionary());
676     ASSERT(!m_enumerationCache);
677
678     materializePropertyMapIfNecessaryForPinning(globalData);
679
680     pin();
681     return remove(propertyName);
682 }
683
684 void Structure::pin()
685 {
686     ASSERT(m_propertyTable);
687     m_isPinnedPropertyTable = true;
688     m_previous.clear();
689     m_nameInPrevious.clear();
690 }
691
692 #if DUMP_PROPERTYMAP_STATS
693
694 struct PropertyMapStatisticsExitLogger {
695     ~PropertyMapStatisticsExitLogger();
696 };
697
698 static PropertyMapStatisticsExitLogger logger;
699
700 PropertyMapStatisticsExitLogger::~PropertyMapStatisticsExitLogger()
701 {
702     dataLogF("\nJSC::PropertyMap statistics\n\n");
703     dataLogF("%d probes\n", numProbes);
704     dataLogF("%d collisions (%.1f%%)\n", numCollisions, 100.0 * numCollisions / numProbes);
705     dataLogF("%d rehashes\n", numRehashes);
706     dataLogF("%d removes\n", numRemoves);
707 }
708
709 #endif
710
711 #if !DO_PROPERTYMAP_CONSTENCY_CHECK
712
713 inline void Structure::checkConsistency()
714 {
715 }
716
717 #endif
718
719 PassOwnPtr<PropertyTable> Structure::copyPropertyTable(JSGlobalData& globalData, Structure* owner)
720 {
721     return adoptPtr(m_propertyTable ? new PropertyTable(globalData, owner, *m_propertyTable) : 0);
722 }
723
724 PassOwnPtr<PropertyTable> Structure::copyPropertyTableForPinning(JSGlobalData& globalData, Structure* owner)
725 {
726     return adoptPtr(m_propertyTable ? new PropertyTable(globalData, owner, *m_propertyTable) : new PropertyTable(numberOfSlotsForLastOffset(m_offset, m_inlineCapacity)));
727 }
728
729 PropertyOffset Structure::get(JSGlobalData& globalData, PropertyName propertyName, unsigned& attributes, JSCell*& specificValue)
730 {
731     ASSERT(structure()->classInfo() == &s_info);
732
733     materializePropertyMapIfNecessary(globalData);
734     if (!m_propertyTable)
735         return invalidOffset;
736
737     PropertyMapEntry* entry = m_propertyTable->find(propertyName.uid()).first;
738     if (!entry)
739         return invalidOffset;
740
741     attributes = entry->attributes;
742     specificValue = entry->specificValue.get();
743     return entry->offset;
744 }
745
746 bool Structure::despecifyFunction(JSGlobalData& globalData, PropertyName propertyName)
747 {
748     materializePropertyMapIfNecessary(globalData);
749     if (!m_propertyTable)
750         return false;
751
752     PropertyMapEntry* entry = m_propertyTable->find(propertyName.uid()).first;
753     if (!entry)
754         return false;
755
756     ASSERT(entry->specificValue);
757     entry->specificValue.clear();
758     return true;
759 }
760
761 void Structure::despecifyAllFunctions(JSGlobalData& globalData)
762 {
763     materializePropertyMapIfNecessary(globalData);
764     if (!m_propertyTable)
765         return;
766
767     PropertyTable::iterator end = m_propertyTable->end();
768     for (PropertyTable::iterator iter = m_propertyTable->begin(); iter != end; ++iter)
769         iter->specificValue.clear();
770 }
771
772 PropertyOffset Structure::putSpecificValue(JSGlobalData& globalData, PropertyName propertyName, unsigned attributes, JSCell* specificValue)
773 {
774     ASSERT(!JSC::isValidOffset(get(globalData, propertyName)));
775
776     checkConsistency();
777     if (attributes & DontEnum)
778         m_hasNonEnumerableProperties = true;
779
780     StringImpl* rep = propertyName.uid();
781
782     if (!m_propertyTable)
783         createPropertyMap();
784
785     PropertyOffset newOffset = m_propertyTable->nextOffset(m_inlineCapacity);
786
787     m_propertyTable->add(PropertyMapEntry(globalData, this, rep, newOffset, attributes, specificValue));
788
789     checkConsistency();
790     return newOffset;
791 }
792
793 PropertyOffset Structure::remove(PropertyName propertyName)
794 {
795     checkConsistency();
796
797     StringImpl* rep = propertyName.uid();
798
799     if (!m_propertyTable)
800         return invalidOffset;
801
802     PropertyTable::find_iterator position = m_propertyTable->find(rep);
803     if (!position.first)
804         return invalidOffset;
805
806     PropertyOffset offset = position.first->offset;
807
808     m_propertyTable->remove(position);
809     m_propertyTable->addDeletedOffset(offset);
810
811     checkConsistency();
812     return offset;
813 }
814
815 void Structure::createPropertyMap(unsigned capacity)
816 {
817     ASSERT(!m_propertyTable);
818
819     checkConsistency();
820     m_propertyTable = adoptPtr(new PropertyTable(capacity));
821     checkConsistency();
822 }
823
824 void Structure::getPropertyNamesFromStructure(JSGlobalData& globalData, PropertyNameArray& propertyNames, EnumerationMode mode)
825 {
826     materializePropertyMapIfNecessary(globalData);
827     if (!m_propertyTable)
828         return;
829
830     bool knownUnique = !propertyNames.size();
831
832     PropertyTable::iterator end = m_propertyTable->end();
833     for (PropertyTable::iterator iter = m_propertyTable->begin(); iter != end; ++iter) {
834         ASSERT(m_hasNonEnumerableProperties || !(iter->attributes & DontEnum));
835         if (iter->key->isIdentifier() && (!(iter->attributes & DontEnum) || mode == IncludeDontEnumProperties)) {
836             if (knownUnique)
837                 propertyNames.addKnownUnique(iter->key);
838             else
839                 propertyNames.add(iter->key);
840         }
841     }
842 }
843
844 void Structure::visitChildren(JSCell* cell, SlotVisitor& visitor)
845 {
846     Structure* thisObject = jsCast<Structure*>(cell);
847     ASSERT_GC_OBJECT_INHERITS(thisObject, &s_info);
848     ASSERT(thisObject->structure()->typeInfo().overridesVisitChildren());
849
850     JSCell::visitChildren(thisObject, visitor);
851     visitor.append(&thisObject->m_globalObject);
852     if (!thisObject->isObject())
853         thisObject->m_cachedPrototypeChain.clear();
854     else {
855         visitor.append(&thisObject->m_prototype);
856         visitor.append(&thisObject->m_cachedPrototypeChain);
857     }
858     visitor.append(&thisObject->m_previous);
859     visitor.append(&thisObject->m_specificValueInPrevious);
860     visitor.append(&thisObject->m_enumerationCache);
861     if (thisObject->m_propertyTable) {
862         PropertyTable::iterator end = thisObject->m_propertyTable->end();
863         for (PropertyTable::iterator ptr = thisObject->m_propertyTable->begin(); ptr != end; ++ptr)
864             visitor.append(&ptr->specificValue);
865     }
866     visitor.append(&thisObject->m_objectToStringValue);
867 }
868
869 bool Structure::prototypeChainMayInterceptStoreTo(JSGlobalData& globalData, PropertyName propertyName)
870 {
871     unsigned i = propertyName.asIndex();
872     if (i != PropertyName::NotAnIndex)
873         return anyObjectInChainMayInterceptIndexedAccesses();
874     
875     for (Structure* current = this; ;) {
876         JSValue prototype = current->storedPrototype();
877         if (prototype.isNull())
878             return false;
879         
880         current = prototype.asCell()->structure();
881         
882         unsigned attributes;
883         JSCell* specificValue;
884         PropertyOffset offset = current->get(globalData, propertyName, attributes, specificValue);
885         if (!JSC::isValidOffset(offset))
886             continue;
887         
888         if (attributes & (ReadOnly | Accessor))
889             return true;
890         
891         return false;
892     }
893 }
894
895 #if DO_PROPERTYMAP_CONSTENCY_CHECK
896
897 void PropertyTable::checkConsistency()
898 {
899     ASSERT(m_indexSize >= PropertyTable::MinimumTableSize);
900     ASSERT(m_indexMask);
901     ASSERT(m_indexSize == m_indexMask + 1);
902     ASSERT(!(m_indexSize & m_indexMask));
903
904     ASSERT(m_keyCount <= m_indexSize / 2);
905     ASSERT(m_keyCount + m_deletedCount <= m_indexSize / 2);
906     ASSERT(m_deletedCount <= m_indexSize / 4);
907
908     unsigned indexCount = 0;
909     unsigned deletedIndexCount = 0;
910     for (unsigned a = 0; a != m_indexSize; ++a) {
911         unsigned entryIndex = m_index[a];
912         if (entryIndex == PropertyTable::EmptyEntryIndex)
913             continue;
914         if (entryIndex == deletedEntryIndex()) {
915             ++deletedIndexCount;
916             continue;
917         }
918         ASSERT(entryIndex < deletedEntryIndex());
919         ASSERT(entryIndex - 1 <= usedCount());
920         ++indexCount;
921
922         for (unsigned b = a + 1; b != m_indexSize; ++b)
923             ASSERT(m_index[b] != entryIndex);
924     }
925     ASSERT(indexCount == m_keyCount);
926     ASSERT(deletedIndexCount == m_deletedCount);
927
928     ASSERT(!table()[deletedEntryIndex() - 1].key);
929
930     unsigned nonEmptyEntryCount = 0;
931     for (unsigned c = 0; c < usedCount(); ++c) {
932         StringImpl* rep = table()[c].key;
933         if (rep == PROPERTY_MAP_DELETED_ENTRY_KEY)
934             continue;
935         ++nonEmptyEntryCount;
936         unsigned i = rep->existingHash();
937         unsigned k = 0;
938         unsigned entryIndex;
939         while (1) {
940             entryIndex = m_index[i & m_indexMask];
941             ASSERT(entryIndex != PropertyTable::EmptyEntryIndex);
942             if (rep == table()[entryIndex - 1].key)
943                 break;
944             if (k == 0)
945                 k = 1 | doubleHash(rep->existingHash());
946             i += k;
947         }
948         ASSERT(entryIndex == c + 1);
949     }
950
951     ASSERT(nonEmptyEntryCount == m_keyCount);
952 }
953
954 void Structure::checkConsistency()
955 {
956     if (!m_propertyTable)
957         return;
958
959     if (!m_hasNonEnumerableProperties) {
960         PropertyTable::iterator end = m_propertyTable->end();
961         for (PropertyTable::iterator iter = m_propertyTable->begin(); iter != end; ++iter) {
962             ASSERT(!(iter->attributes & DontEnum));
963         }
964     }
965
966     m_propertyTable->checkConsistency();
967 }
968
969 #endif // DO_PROPERTYMAP_CONSTENCY_CHECK
970
971 } // namespace JSC