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