Home | History | Annotate | Download | only in runtime 
      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 #ifndef Structure_h
     27 #define Structure_h
     28 
     29 #include "Identifier.h"
     30 #include "JSType.h"
     31 #include "JSValue.h"
     32 #include "PropertyMapHashTable.h"
     33 #include "PropertyNameArray.h"
     34 #include "Protect.h"
     35 #include "StructureChain.h"
     36 #include "StructureTransitionTable.h"
     37 #include "JSTypeInfo.h"
     38 #include "UString.h"
     39 #include "WeakGCPtr.h"
     40 #include <wtf/PassRefPtr.h>
     41 #include <wtf/RefCounted.h>
     42 
     43 #ifndef NDEBUG
     44 #define DUMP_PROPERTYMAP_STATS 0
     45 #else
     46 #define DUMP_PROPERTYMAP_STATS 0
     47 #endif
     48 
     49 namespace JSC {
     50 
     51     class MarkStack;
     52     class PropertyNameArray;
     53     class PropertyNameArrayData;
     54 
     55     enum EnumerationMode {
     56         ExcludeDontEnumProperties,
     57         IncludeDontEnumProperties
     58     };
     59 
     60     class Structure : public RefCounted<Structure> {
     61     public:
     62         friend class JIT;
     63         friend class StructureTransitionTable;
     64         static PassRefPtr<Structure> create(JSValue prototype, const TypeInfo& typeInfo, unsigned anonymousSlotCount)
     65         {
     66             return adoptRef(new Structure(prototype, typeInfo, anonymousSlotCount));
     67         }
     68 
     69         static void startIgnoringLeaks();
     70         static void stopIgnoringLeaks();
     71 
     72         static void dumpStatistics();
     73 
     74         static PassRefPtr<Structure> addPropertyTransition(Structure*, const Identifier& propertyName, unsigned attributes, JSCell* specificValue, size_t& offset);
     75         static PassRefPtr<Structure> addPropertyTransitionToExistingStructure(Structure*, const Identifier& propertyName, unsigned attributes, JSCell* specificValue, size_t& offset);
     76         static PassRefPtr<Structure> removePropertyTransition(Structure*, const Identifier& propertyName, size_t& offset);
     77         static PassRefPtr<Structure> changePrototypeTransition(Structure*, JSValue prototype);
     78         static PassRefPtr<Structure> despecifyFunctionTransition(Structure*, const Identifier&);
     79         static PassRefPtr<Structure> getterSetterTransition(Structure*);
     80         static PassRefPtr<Structure> toCacheableDictionaryTransition(Structure*);
     81         static PassRefPtr<Structure> toUncacheableDictionaryTransition(Structure*);
     82 
     83         PassRefPtr<Structure> flattenDictionaryStructure(JSObject*);
     84 
     85         ~Structure();
     86 
     87         // These should be used with caution.
     88         size_t addPropertyWithoutTransition(const Identifier& propertyName, unsigned attributes, JSCell* specificValue);
     89         size_t removePropertyWithoutTransition(const Identifier& propertyName);
     90         void setPrototypeWithoutTransition(JSValue prototype) { m_prototype = prototype; }
     91 
     92         bool isDictionary() const { return m_dictionaryKind != NoneDictionaryKind; }
     93         bool isUncacheableDictionary() const { return m_dictionaryKind == UncachedDictionaryKind; }
     94 
     95         const TypeInfo& typeInfo() const { return m_typeInfo; }
     96 
     97         JSValue storedPrototype() const { return m_prototype; }
     98         JSValue prototypeForLookup(ExecState*) const;
     99         StructureChain* prototypeChain(ExecState*) const;
    100 
    101         Structure* previousID() const { return m_previous.get(); }
    102 
    103         void growPropertyStorageCapacity();
    104         unsigned propertyStorageCapacity() const { return m_propertyStorageCapacity; }
    105         unsigned propertyStorageSize() const { return m_anonymousSlotCount + (m_propertyTable ? m_propertyTable->keyCount + (m_propertyTable->deletedOffsets ? m_propertyTable->deletedOffsets->size() : 0) : static_cast<unsigned>(m_offset + 1)); }
    106         bool isUsingInlineStorage() const;
    107 
    108         size_t get(const Identifier& propertyName);
    109         size_t get(const UString::Rep* rep, unsigned& attributes, JSCell*& specificValue);
    110         size_t get(const Identifier& propertyName, unsigned& attributes, JSCell*& specificValue)
    111         {
    112             ASSERT(!propertyName.isNull());
    113             return get(propertyName.ustring().rep(), attributes, specificValue);
    114         }
    115         bool transitionedFor(const JSCell* specificValue)
    116         {
    117             return m_specificValueInPrevious == specificValue;
    118         }
    119         bool hasTransition(UString::Rep*, unsigned attributes);
    120         bool hasTransition(const Identifier& propertyName, unsigned attributes)
    121         {
    122             return hasTransition(propertyName._ustring.rep(), attributes);
    123         }
    124 
    125         bool hasGetterSetterProperties() const { return m_hasGetterSetterProperties; }
    126         void setHasGetterSetterProperties(bool hasGetterSetterProperties) { m_hasGetterSetterProperties = hasGetterSetterProperties; }
    127 
    128         bool hasNonEnumerableProperties() const { return m_hasNonEnumerableProperties; }
    129 
    130         bool hasAnonymousSlots() const { return !!m_anonymousSlotCount; }
    131         unsigned anonymousSlotCount() const { return m_anonymousSlotCount; }
    132 
    133         bool isEmpty() const { return m_propertyTable ? !m_propertyTable->keyCount : m_offset == noOffset; }
    134 
    135         void despecifyDictionaryFunction(const Identifier& propertyName);
    136         void disableSpecificFunctionTracking() { m_specificFunctionThrashCount = maxSpecificFunctionThrashCount; }
    137 
    138         void setEnumerationCache(JSPropertyNameIterator* enumerationCache); // Defined in JSPropertyNameIterator.h.
    139         void clearEnumerationCache(JSPropertyNameIterator* enumerationCache); // Defined in JSPropertyNameIterator.h.
    140         JSPropertyNameIterator* enumerationCache(); // Defined in JSPropertyNameIterator.h.
    141         void getPropertyNames(PropertyNameArray&, EnumerationMode mode);
    142 
    143     private:
    144 
    145         Structure(JSValue prototype, const TypeInfo&, unsigned anonymousSlotCount);
    146 
    147         typedef enum {
    148             NoneDictionaryKind = 0,
    149             CachedDictionaryKind = 1,
    150             UncachedDictionaryKind = 2
    151         } DictionaryKind;
    152         static PassRefPtr<Structure> toDictionaryTransition(Structure*, DictionaryKind);
    153 
    154         size_t put(const Identifier& propertyName, unsigned attributes, JSCell* specificValue);
    155         size_t remove(const Identifier& propertyName);
    156 
    157         void expandPropertyMapHashTable();
    158         void rehashPropertyMapHashTable();
    159         void rehashPropertyMapHashTable(unsigned newTableSize);
    160         void createPropertyMapHashTable();
    161         void createPropertyMapHashTable(unsigned newTableSize);
    162         void insertIntoPropertyMapHashTable(const PropertyMapEntry&);
    163         void checkConsistency();
    164 
    165         bool despecifyFunction(const Identifier&);
    166         void despecifyAllFunctions();
    167 
    168         PropertyMapHashTable* copyPropertyTable();
    169         void materializePropertyMap();
    170         void materializePropertyMapIfNecessary()
    171         {
    172             if (m_propertyTable || !m_previous)
    173                 return;
    174             materializePropertyMap();
    175         }
    176 
    177         signed char transitionCount() const
    178         {
    179             // Since the number of transitions is always the same as m_offset, we keep the size of Structure down by not storing both.
    180             return m_offset == noOffset ? 0 : m_offset + 1;
    181         }
    182 
    183         bool isValid(ExecState*, StructureChain* cachedPrototypeChain) const;
    184 
    185         static const unsigned emptyEntryIndex = 0;
    186 
    187         static const signed char s_maxTransitionLength = 64;
    188 
    189         static const signed char noOffset = -1;
    190 
    191         static const unsigned maxSpecificFunctionThrashCount = 3;
    192 
    193         TypeInfo m_typeInfo;
    194 
    195         JSValue m_prototype;
    196         mutable RefPtr<StructureChain> m_cachedPrototypeChain;
    197 
    198         RefPtr<Structure> m_previous;
    199         RefPtr<UString::Rep> m_nameInPrevious;
    200         JSCell* m_specificValueInPrevious;
    201 
    202         StructureTransitionTable table;
    203 
    204         WeakGCPtr<JSPropertyNameIterator> m_enumerationCache;
    205 
    206         PropertyMapHashTable* m_propertyTable;
    207 
    208         uint32_t m_propertyStorageCapacity;
    209 
    210         // m_offset does not account for anonymous slots
    211         signed char m_offset;
    212 
    213         unsigned m_dictionaryKind : 2;
    214         bool m_isPinnedPropertyTable : 1;
    215         bool m_hasGetterSetterProperties : 1;
    216         bool m_hasNonEnumerableProperties : 1;
    217 #if COMPILER(WINSCW)
    218         // Workaround for Symbian WINSCW compiler that cannot resolve unsigned type of the declared
    219         // bitfield, when used as argument in make_pair() function calls in structure.ccp.
    220         // This bitfield optimization is insignificant for the Symbian emulator target.
    221         unsigned m_attributesInPrevious;
    222 #else
    223         unsigned m_attributesInPrevious : 7;
    224 #endif
    225         unsigned m_specificFunctionThrashCount : 2;
    226         unsigned m_anonymousSlotCount : 5;
    227         // 5 free bits
    228     };
    229 
    230     inline size_t Structure::get(const Identifier& propertyName)
    231     {
    232         ASSERT(!propertyName.isNull());
    233 
    234         materializePropertyMapIfNecessary();
    235         if (!m_propertyTable)
    236             return WTF::notFound;
    237 
    238         UString::Rep* rep = propertyName._ustring.rep();
    239 
    240         unsigned i = rep->existingHash();
    241 
    242 #if DUMP_PROPERTYMAP_STATS
    243         ++numProbes;
    244 #endif
    245 
    246         unsigned entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
    247         if (entryIndex == emptyEntryIndex)
    248             return WTF::notFound;
    249 
    250         if (rep == m_propertyTable->entries()[entryIndex - 1].key)
    251             return m_propertyTable->entries()[entryIndex - 1].offset;
    252 
    253 #if DUMP_PROPERTYMAP_STATS
    254         ++numCollisions;
    255 #endif
    256 
    257         unsigned k = 1 | WTF::doubleHash(rep->existingHash());
    258 
    259         while (1) {
    260             i += k;
    261 
    262 #if DUMP_PROPERTYMAP_STATS
    263             ++numRehashes;
    264 #endif
    265 
    266             entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
    267             if (entryIndex == emptyEntryIndex)
    268                 return WTF::notFound;
    269 
    270             if (rep == m_propertyTable->entries()[entryIndex - 1].key)
    271                 return m_propertyTable->entries()[entryIndex - 1].offset;
    272         }
    273     }
    274 
    275     bool StructureTransitionTable::contains(const StructureTransitionTableHash::Key& key, JSCell* specificValue)
    276     {
    277         if (usingSingleTransitionSlot()) {
    278             Structure* existingTransition = singleTransition();
    279             return existingTransition && existingTransition->m_nameInPrevious.get() == key.first
    280                    && existingTransition->m_attributesInPrevious == key.second
    281                    && (existingTransition->m_specificValueInPrevious == specificValue || existingTransition->m_specificValueInPrevious == 0);
    282         }
    283         TransitionTable::iterator find = table()->find(key);
    284         if (find == table()->end())
    285             return false;
    286 
    287         return find->second.first || find->second.second->transitionedFor(specificValue);
    288     }
    289 
    290     Structure* StructureTransitionTable::get(const StructureTransitionTableHash::Key& key, JSCell* specificValue) const
    291     {
    292         if (usingSingleTransitionSlot()) {
    293             Structure* existingTransition = singleTransition();
    294             if (existingTransition && existingTransition->m_nameInPrevious.get() == key.first
    295                 && existingTransition->m_attributesInPrevious == key.second
    296                 && (existingTransition->m_specificValueInPrevious == specificValue || existingTransition->m_specificValueInPrevious == 0))
    297                 return existingTransition;
    298             return 0;
    299         }
    300 
    301         Transition transition = table()->get(key);
    302         if (transition.second && transition.second->transitionedFor(specificValue))
    303             return transition.second;
    304         return transition.first;
    305     }
    306 
    307     bool StructureTransitionTable::hasTransition(const StructureTransitionTableHash::Key& key) const
    308     {
    309         if (usingSingleTransitionSlot()) {
    310             Structure* transition = singleTransition();
    311             return transition && transition->m_nameInPrevious == key.first
    312             && transition->m_attributesInPrevious == key.second;
    313         }
    314         return table()->contains(key);
    315     }
    316 
    317     void StructureTransitionTable::reifySingleTransition()
    318     {
    319         ASSERT(usingSingleTransitionSlot());
    320         Structure* existingTransition = singleTransition();
    321         TransitionTable* transitionTable = new TransitionTable;
    322         setTransitionTable(transitionTable);
    323         if (existingTransition)
    324             add(std::make_pair(existingTransition->m_nameInPrevious.get(), existingTransition->m_attributesInPrevious), existingTransition, existingTransition->m_specificValueInPrevious);
    325     }
    326 } // namespace JSC
    327 
    328 #endif // Structure_h
    329