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