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