runtime/StructureTransitionTable.h

   1 /*
   2  * Copyright (C) 2008, 2009, 2013 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 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 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 StructureTransitionTable_h
  27 #define StructureTransitionTable_h
  28
  29 #include "IndexingType.h"
  30 #include "WeakGCMap.h"
  31 #include <wtf/HashFunctions.h>
  32 #include <wtf/text/UniquedStringImpl.h>
  33
  34 namespace JSC {
  35
  36 class JSCell;
  37 class Structure;
  38
  39 static const unsigned FirstInternalAttribute = 1 << 6; // Use for transitions that don't have to do with property additions.
  40
  41 // Support for attributes used to indicate transitions not related to properties.
  42 // If any of these are used, the string portion of the key should be 0.
  43 enum NonPropertyTransition {
  44     AllocateUndecided,
  45     AllocateInt32,
  46     AllocateDouble,
  47     AllocateContiguous,
  48     AllocateArrayStorage,
  49     AllocateSlowPutArrayStorage,
  50     SwitchToSlowPutArrayStorage,
  51     AddIndexedAccessors
  52 };
  53
  54 inline unsigned toAttributes(NonPropertyTransition transition)
  55 {
  56     return transition + FirstInternalAttribute;
  57 }
  58
  59 inline IndexingType newIndexingType(IndexingType oldType, NonPropertyTransition transition)
  60 {
  61     switch (transition) {
  62     case AllocateUndecided:
  63         ASSERT(!hasIndexedProperties(oldType));
  64         return oldType | UndecidedShape;
  65     case AllocateInt32:
  66         ASSERT(!hasIndexedProperties(oldType) || hasUndecided(oldType));
  67         return (oldType & ~IndexingShapeMask) | Int32Shape;
  68     case AllocateDouble:
  69         ASSERT(!hasIndexedProperties(oldType) || hasUndecided(oldType) || hasInt32(oldType));
  70         return (oldType & ~IndexingShapeMask) | DoubleShape;
  71     case AllocateContiguous:
  72         ASSERT(!hasIndexedProperties(oldType) || hasUndecided(oldType) || hasInt32(oldType) || hasDouble(oldType));
  73         return (oldType & ~IndexingShapeMask) | ContiguousShape;
  74     case AllocateArrayStorage:
  75         ASSERT(!hasIndexedProperties(oldType) || hasUndecided(oldType) || hasInt32(oldType) || hasDouble(oldType) || hasContiguous(oldType));
  76         return (oldType & ~IndexingShapeMask) | ArrayStorageShape;
  77     case AllocateSlowPutArrayStorage:
  78         ASSERT(!hasIndexedProperties(oldType) || hasUndecided(oldType) || hasInt32(oldType) || hasDouble(oldType) || hasContiguous(oldType) || hasContiguous(oldType));
  79         return (oldType & ~IndexingShapeMask) | SlowPutArrayStorageShape;
  80     case SwitchToSlowPutArrayStorage:
  81         ASSERT(hasArrayStorage(oldType));
  82         return (oldType & ~IndexingShapeMask) | SlowPutArrayStorageShape;
  83     case AddIndexedAccessors:
  84         return oldType | MayHaveIndexedAccessors;
  85     default:
  86         RELEASE_ASSERT_NOT_REACHED();
  87         return oldType;
  88     }
  89 }
  90
  91 class StructureTransitionTable {
  92     static const intptr_t UsingSingleSlotFlag = 1;
  93
  94
  95     struct Hash {
  96         typedef std::pair<UniquedStringImpl*, unsigned> Key;
  97
  98         static unsigned hash(const Key& p)
  99         {
 100             return PtrHash<UniquedStringImpl*>::hash(p.first) + p.second;
 101         }
 102
 103         static bool equal(const Key& a, const Key& b)
 104         {
 105             return a == b;
 106         }
 107
 108         static const bool safeToCompareToEmptyOrDeleted = true;
 109     };
 110
 111     typedef WeakGCMap<Hash::Key, Structure, Hash> TransitionMap;
 112
 113 public:
 114     StructureTransitionTable()
 115         : m_data(UsingSingleSlotFlag)
 116     {
 117     }
 118
 119     ~StructureTransitionTable()
 120     {
 121         if (!isUsingSingleSlot()) {
 122             delete map();
 123             return;
 124         }
 125
 126         WeakImpl* impl = this->weakImpl();
 127         if (!impl)
 128             return;
 129         WeakSet::deallocate(impl);
 130     }
 131
 132     void add(VM&, Structure*);
 133     bool contains(UniquedStringImpl*, unsigned attributes) const;
 134     Structure* get(UniquedStringImpl*, unsigned attributes) const;
 135
 136 private:
 137     bool isUsingSingleSlot() const
 138     {
 139         return m_data & UsingSingleSlotFlag;
 140     }
 141
 142     TransitionMap* map() const
 143     {
 144         ASSERT(!isUsingSingleSlot());
 145         return reinterpret_cast<TransitionMap*>(m_data);
 146     }
 147
 148     WeakImpl* weakImpl() const
 149     {
 150         ASSERT(isUsingSingleSlot());
 151         return reinterpret_cast<WeakImpl*>(m_data & ~UsingSingleSlotFlag);
 152     }
 153
 154     void setMap(TransitionMap* map)
 155     {
 156         ASSERT(isUsingSingleSlot());
 157
 158         if (WeakImpl* impl = this->weakImpl())
 159             WeakSet::deallocate(impl);
 160
 161         // This implicitly clears the flag that indicates we're using a single transition
 162         m_data = reinterpret_cast<intptr_t>(map);
 163
 164         ASSERT(!isUsingSingleSlot());
 165     }
 166
 167     Structure* singleTransition() const
 168     {
 169         ASSERT(isUsingSingleSlot());
 170         if (WeakImpl* impl = this->weakImpl()) {
 171             if (impl->state() == WeakImpl::Live)
 172                 return reinterpret_cast<Structure*>(impl->jsValue().asCell());
 173         }
 174         return 0;
 175     }
 176
 177     void setSingleTransition(VM&, Structure* structure)
 178     {
 179         ASSERT(isUsingSingleSlot());
 180         if (WeakImpl* impl = this->weakImpl())
 181             WeakSet::deallocate(impl);
 182         WeakImpl* impl = WeakSet::allocate(reinterpret_cast<JSCell*>(structure));
 183         m_data = reinterpret_cast<intptr_t>(impl) | UsingSingleSlotFlag;
 184     }
 185
 186     intptr_t m_data;
 187 };
 188
 189 } // namespace JSC
 190
 191 #endif // StructureTransitionTable_h