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         typedef std::pair<Structure*, Structure*> Transition;

   184         typedef HashMap<StructureTransitionTableHash::Key, Transition, StructureTransitionTableHash, StructureTransitionTableHashTraits> TransitionTable;

   185 

   186         inline bool transitionTableContains(const StructureTransitionTableHash::Key& key, JSCell* specificValue);

   187         inline void transitionTableRemove(const StructureTransitionTableHash::Key& key, JSCell* specificValue);

   188         inline void transitionTableAdd(const StructureTransitionTableHash::Key& key, Structure* structure, JSCell* specificValue);

   189         inline bool transitionTableHasTransition(const StructureTransitionTableHash::Key& key) const;

   190         inline Structure* transitionTableGet(const StructureTransitionTableHash::Key& key, JSCell* specificValue) const;

   191 

   192         TransitionTable* transitionTable() const { ASSERT(!m_isUsingSingleSlot); return m_transitions.m_table; }

   193         inline void setTransitionTable(TransitionTable* table);

   194         Structure* singleTransition() const { ASSERT(m_isUsingSingleSlot); return m_transitions.m_singleTransition; }

   195         void setSingleTransition(Structure* structure) { ASSERT(m_isUsingSingleSlot); m_transitions.m_singleTransition = structure; }

   196         

   197         bool isValid(ExecState*, StructureChain* cachedPrototypeChain) const;

   198 

   199         static const unsigned emptyEntryIndex = 0;

   200     

   201         static const signed char s_maxTransitionLength = 64;

   202 

   203         static const signed char noOffset = -1;

   204 

   205         static const unsigned maxSpecificFunctionThrashCount = 3;

   206 

   207         TypeInfo m_typeInfo;

   208 

   209         JSValue m_prototype;

   210         mutable RefPtr<StructureChain> m_cachedPrototypeChain;

   211 

   212         RefPtr<Structure> m_previous;

   213         RefPtr<UString::Rep> m_nameInPrevious;

   214         JSCell* m_specificValueInPrevious;

   215 

   216         // 'm_isUsingSingleSlot' indicates whether we are using the single transition optimisation.

   217         union {

   218             TransitionTable* m_table;

   219             Structure* m_singleTransition;

   220         } m_transitions;

   221 

   222         WeakGCPtr<JSPropertyNameIterator> m_enumerationCache;

   223 

   224         PropertyMapHashTable* m_propertyTable;

   225 

   226         uint32_t m_propertyStorageCapacity;

   227 

   228         // m_offset does not account for anonymous slots

   229         signed char m_offset;

   230 

   231         unsigned m_dictionaryKind : 2;

   232         bool m_isPinnedPropertyTable : 1;

   233         bool m_hasGetterSetterProperties : 1;

   234         bool m_hasNonEnumerableProperties : 1;

   235 #if COMPILER(WINSCW)

   236         // Workaround for Symbian WINSCW compiler that cannot resolve unsigned type of the declared 

   237         // bitfield, when used as argument in make_pair() function calls in structure.ccp.

   238         // This bitfield optimization is insignificant for the Symbian emulator target.

   239         unsigned m_attributesInPrevious;

   240 #else

   241         unsigned m_attributesInPrevious : 7;

   242 #endif

   243         unsigned m_specificFunctionThrashCount : 2;

   244         unsigned m_anonymousSlotCount : 5;

   245         unsigned m_isUsingSingleSlot : 1;

   246         // 4 free bits

   247     };

   248 

   249     inline size_t Structure::get(const Identifier& propertyName)

   250     {

   251         ASSERT(!propertyName.isNull());

   252 

   253         materializePropertyMapIfNecessary();

   254         if (!m_propertyTable)

   255             return WTF::notFound;

   256 

   257         UString::Rep* rep = propertyName._ustring.rep();

   258 

   259         unsigned i = rep->existingHash();

   260 

   261 #if DUMP_PROPERTYMAP_STATS

   262         ++numProbes;

   263 #endif

   264 

   265         unsigned entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];

   266         if (entryIndex == emptyEntryIndex)

   267             return WTF::notFound;

   268 

   269         if (rep == m_propertyTable->entries()[entryIndex - 1].key)

   270             return m_propertyTable->entries()[entryIndex - 1].offset;

   271 

   272 #if DUMP_PROPERTYMAP_STATS

   273         ++numCollisions;

   274 #endif

   275 

   276         unsigned k = 1 | WTF::doubleHash(rep->existingHash());

   277 

   278         while (1) {

   279             i += k;

   280 

   281 #if DUMP_PROPERTYMAP_STATS

   282             ++numRehashes;

   283 #endif

   284 

   285             entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];

   286             if (entryIndex == emptyEntryIndex)

   287                 return WTF::notFound;

   288 

   289             if (rep == m_propertyTable->entries()[entryIndex - 1].key)

   290                 return m_propertyTable->entries()[entryIndex - 1].offset;

   291         }

   292     }

   293 

   294 } // namespace JSC

   295 

   296 #endif // Structure_h