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