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