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