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