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