runtime/Structure.h

   1 /*
   2  * Copyright (C) 2008 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 "StructureChain.h"
  34 #include "StructureTransitionTable.h"
  35 #include "TypeInfo.h"
  36 #include "UString.h"
  37 #include <wtf/PassRefPtr.h>
  38 #include <wtf/RefCounted.h>
  39
  40 #ifndef NDEBUG
  41 #define DUMP_PROPERTYMAP_STATS 0
  42 #else
  43 #define DUMP_PROPERTYMAP_STATS 0
  44 #endif
  45
  46 namespace JSC {
  47
  48     class PropertyNameArray;
  49     class PropertyNameArrayData;
  50
  51     class Structure : public RefCounted<Structure> {
  52     public:
  53         friend class JIT;
  54         static PassRefPtr<Structure> create(JSValuePtr prototype, const TypeInfo& typeInfo)
  55         {
  56             return adoptRef(new Structure(prototype, typeInfo));
  57         }
  58
  59         static void startIgnoringLeaks();
  60         static void stopIgnoringLeaks();
  61
  62         static void dumpStatistics();
  63
  64         static PassRefPtr<Structure> addPropertyTransition(Structure*, const Identifier& propertyName, unsigned attributes, size_t& offset);
  65         static PassRefPtr<Structure> addPropertyTransitionToExistingStructure(Structure*, const Identifier& propertyName, unsigned attributes, size_t& offset);
  66         static PassRefPtr<Structure> removePropertyTransition(Structure*, const Identifier& propertyName, size_t& offset);
  67         static PassRefPtr<Structure> changePrototypeTransition(Structure*, JSValuePtr prototype);
  68         static PassRefPtr<Structure> getterSetterTransition(Structure*);
  69         static PassRefPtr<Structure> toDictionaryTransition(Structure*);
  70         static PassRefPtr<Structure> fromDictionaryTransition(Structure*);
  71
  72         ~Structure();
  73
  74         void mark()
  75         {
  76             if (!m_prototype.marked())
  77                 m_prototype.mark();
  78         }
  79
  80         // These should be used with caution.
  81         size_t addPropertyWithoutTransition(const Identifier& propertyName, unsigned attributes);
  82         size_t removePropertyWithoutTransition(const Identifier& propertyName);
  83         void setPrototypeWithoutTransition(JSValuePtr prototype) { m_prototype = prototype; }
  84
  85         bool isDictionary() const { return m_isDictionary; }
  86
  87         const TypeInfo& typeInfo() const { return m_typeInfo; }
  88
  89         JSValuePtr storedPrototype() const { return m_prototype; }
  90         JSValuePtr prototypeForLookup(ExecState*) const;
  91         StructureChain* prototypeChain(ExecState*) const;
  92
  93         Structure* previousID() const { return m_previous.get(); }
  94
  95         void growPropertyStorageCapacity();
  96         size_t propertyStorageCapacity() const { return m_propertyStorageCapacity; }
  97         size_t propertyStorageSize() const { return m_propertyTable ? m_propertyTable->keyCount + (m_propertyTable->deletedOffsets ? m_propertyTable->deletedOffsets->size() : 0) : m_offset + 1; }
  98
  99         size_t get(const Identifier& propertyName);
 100         size_t get(const Identifier& propertyName, unsigned& attributes);
 101         void getEnumerablePropertyNames(ExecState*, PropertyNameArray&, JSObject*);
 102
 103         bool hasGetterSetterProperties() const { return m_hasGetterSetterProperties; }
 104         void setHasGetterSetterProperties(bool hasGetterSetterProperties) { m_hasGetterSetterProperties = hasGetterSetterProperties; }
 105
 106         bool isEmpty() const { return m_propertyTable ? !m_propertyTable->keyCount : m_offset == noOffset; }
 107
 108     private:
 109         Structure(JSValuePtr prototype, const TypeInfo&);
 110
 111         size_t put(const Identifier& propertyName, unsigned attributes);
 112         size_t remove(const Identifier& propertyName);
 113         void getEnumerableNamesFromPropertyTable(PropertyNameArray&);
 114         void getEnumerableNamesFromClassInfoTable(ExecState*, const ClassInfo*, PropertyNameArray&);
 115
 116         void expandPropertyMapHashTable();
 117         void rehashPropertyMapHashTable();
 118         void rehashPropertyMapHashTable(unsigned newTableSize);
 119         void createPropertyMapHashTable();
 120         void createPropertyMapHashTable(unsigned newTableSize);
 121         void insertIntoPropertyMapHashTable(const PropertyMapEntry&);
 122         void checkConsistency();
 123
 124         PropertyMapHashTable* copyPropertyTable();
 125         void materializePropertyMap();
 126         void materializePropertyMapIfNecessary()
 127         {
 128             if (m_propertyTable || !m_previous)
 129                 return;
 130             materializePropertyMap();
 131         }
 132
 133         void clearEnumerationCache();
 134
 135         void* addressOfCount()
 136         {
 137             return &m_refCount;
 138         }
 139
 140         signed char transitionCount() const
 141         {
 142             // Since the number of transitions is always the same as m_offset, we keep the size of Structure down by not storing both.
 143             return m_offset == noOffset ? 0 : m_offset + 1;
 144         }
 145
 146         bool isValid(ExecState*, StructureChain* cachedPrototypeChain) const;
 147
 148         static const unsigned emptyEntryIndex = 0;
 149
 150         static const signed char s_maxTransitionLength = 64;
 151
 152         static const signed char noOffset = -1;
 153
 154         TypeInfo m_typeInfo;
 155
 156         JSValuePtr m_prototype;
 157         mutable RefPtr<StructureChain> m_cachedPrototypeChain;
 158
 159         RefPtr<Structure> m_previous;
 160         RefPtr<UString::Rep> m_nameInPrevious;
 161
 162         union {
 163             Structure* singleTransition;
 164             StructureTransitionTable* table;
 165         } m_transitions;
 166
 167         RefPtr<PropertyNameArrayData> m_cachedPropertyNameArrayData;
 168
 169         PropertyMapHashTable* m_propertyTable;
 170
 171         size_t m_propertyStorageCapacity;
 172         signed char m_offset;
 173
 174         bool m_isDictionary : 1;
 175         bool m_isPinnedPropertyTable : 1;
 176         bool m_hasGetterSetterProperties : 1;
 177         bool m_usingSingleTransitionSlot : 1;
 178         unsigned m_attributesInPrevious : 5;
 179     };
 180
 181     inline size_t Structure::get(const Identifier& propertyName)
 182     {
 183         ASSERT(!propertyName.isNull());
 184
 185         materializePropertyMapIfNecessary();
 186         if (!m_propertyTable)
 187             return WTF::notFound;
 188
 189         UString::Rep* rep = propertyName._ustring.rep();
 190
 191         unsigned i = rep->computedHash();
 192
 193 #if DUMP_PROPERTYMAP_STATS
 194         ++numProbes;
 195 #endif
 196
 197         unsigned entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
 198         if (entryIndex == emptyEntryIndex)
 199             return WTF::notFound;
 200
 201         if (rep == m_propertyTable->entries()[entryIndex - 1].key)
 202             return m_propertyTable->entries()[entryIndex - 1].offset;
 203
 204 #if DUMP_PROPERTYMAP_STATS
 205         ++numCollisions;
 206 #endif
 207
 208         unsigned k = 1 | WTF::doubleHash(rep->computedHash());
 209
 210         while (1) {
 211             i += k;
 212
 213 #if DUMP_PROPERTYMAP_STATS
 214             ++numRehashes;
 215 #endif
 216
 217             entryIndex = m_propertyTable->entryIndices[i & m_propertyTable->sizeMask];
 218             if (entryIndex == emptyEntryIndex)
 219                 return WTF::notFound;
 220
 221             if (rep == m_propertyTable->entries()[entryIndex - 1].key)
 222                 return m_propertyTable->entries()[entryIndex - 1].offset;
 223         }
 224     }
 225
 226 } // namespace JSC
 227
 228 #endif // Structure_h