Introduce UniquedStringImpl and SymbolImpl to separate symbolic strings from AtomicSt...
[WebKit-https.git] / Source / JavaScriptCore / 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