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