JSC::Symbol should be hash-consed
[WebKit-https.git] / Source / JavaScriptCore / runtime / MapDataInlines.h
1 /*
2  * Copyright (C) 2013, 2016 Apple Inc. All rights reserved.
3  * Copyright (C) 2015 Yusuke Suzuki <utatane.tea@gmail.com>.
4  *
5  * Redistribution and use in source and binary forms, with or without
6  * modification, are permitted provided that the following conditions
7  * are met:
8  * 1. Redistributions of source code must retain the above copyright
9  *    notice, this list of conditions and the following disclaimer.
10  * 2. Redistributions in binary form must reproduce the above copyright
11  *    notice, this list of conditions and the following disclaimer in the
12  *    documentation and/or other materials provided with the distribution.
13  *
14  * THIS SOFTWARE IS PROVIDED BY APPLE INC. AND ITS CONTRIBUTORS ``AS IS''
15  * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO,
16  * THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
17  * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE INC. OR ITS CONTRIBUTORS
18  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
19  * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
20  * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
21  * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
22  * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
23  * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF
24  * THE POSSIBILITY OF SUCH DAMAGE.
25  */
26
27 #include "CopiedAllocator.h"
28 #include "CopyVisitorInlines.h"
29 #include "ExceptionHelpers.h"
30 #include "JSCJSValueInlines.h"
31 #include "MapData.h"
32 #include "SlotVisitorInlines.h"
33
34 #include <wtf/CryptographicallyRandomNumber.h>
35 #include <wtf/MathExtras.h>
36
37
38 namespace JSC {
39
40 template<typename Entry, typename JSIterator>
41 inline void MapDataImpl<Entry, JSIterator>::clear()
42 {
43     m_cellKeyedTable.clear();
44     m_valueKeyedTable.clear();
45     m_stringKeyedTable.clear();
46     m_capacity = 0;
47     m_size = 0;
48     m_deletedCount = 0;
49     m_entries.clear();
50     m_iterators.forEach([](JSIterator* iterator, JSIterator*) {
51         iterator->iteratorData()->didRemoveAllEntries();
52     });
53 }
54
55 template<typename Entry, typename JSIterator>
56 inline Entry* MapDataImpl<Entry, JSIterator>::find(ExecState* exec, KeyType key)
57 {
58     if (key.value.isString()) {
59         auto iter = m_stringKeyedTable.find(asString(key.value)->value(exec).impl());
60         if (iter == m_stringKeyedTable.end())
61             return 0;
62         return &m_entries.get()[iter->value];
63     }
64     if (key.value.isCell()) {
65         auto iter = m_cellKeyedTable.find(key.value.asCell());
66         if (iter == m_cellKeyedTable.end())
67             return 0;
68         return &m_entries.get()[iter->value];
69     }
70
71     auto iter = m_valueKeyedTable.find(JSValue::encode(key.value));
72     if (iter == m_valueKeyedTable.end())
73         return 0;
74     return &m_entries.get()[iter->value];
75 }
76
77 template<typename Entry, typename JSIterator>
78 inline bool MapDataImpl<Entry, JSIterator>::contains(ExecState* exec, KeyType key)
79 {
80     return find(exec, key);
81 }
82
83 template<typename Entry, typename JSIterator>
84 template <typename Map, typename Key>
85 inline Entry* MapDataImpl<Entry, JSIterator>::add(ExecState* exec, JSCell* owner, Map& map, Key key, KeyType keyValue)
86 {
87     typename Map::iterator location = map.find(key);
88     if (location != map.end())
89         return &m_entries.get()[location->value];
90
91     if (!ensureSpaceForAppend(exec, owner))
92         return 0;
93
94     auto result = map.add(key, m_size);
95     RELEASE_ASSERT(result.isNewEntry);
96     Entry* entry = &m_entries.get()[m_size++];
97     new (entry) Entry();
98     entry->setKey(exec->vm(), owner, keyValue.value);
99     return entry;
100 }
101
102 template<typename Entry, typename JSIterator>
103 inline void MapDataImpl<Entry, JSIterator>::set(ExecState* exec, JSCell* owner, KeyType key, JSValue value)
104 {
105     Entry* location = add(exec, owner, key);
106     if (!location)
107         return;
108     location->setValue(exec->vm(), owner, value);
109 }
110
111 template<typename Entry, typename JSIterator>
112 inline Entry* MapDataImpl<Entry, JSIterator>::add(ExecState* exec, JSCell* owner, KeyType key)
113 {
114     if (key.value.isString())
115         return add(exec, owner, m_stringKeyedTable, asString(key.value)->value(exec).impl(), key);
116     if (key.value.isCell())
117         return add(exec, owner, m_cellKeyedTable, key.value.asCell(), key);
118     return add(exec, owner, m_valueKeyedTable, JSValue::encode(key.value), key);
119 }
120
121 template<typename Entry, typename JSIterator>
122 inline JSValue MapDataImpl<Entry, JSIterator>::get(ExecState* exec, KeyType key)
123 {
124     if (Entry* entry = find(exec, key))
125         return entry->value().get();
126     return JSValue();
127 }
128
129 template<typename Entry, typename JSIterator>
130 inline bool MapDataImpl<Entry, JSIterator>::remove(ExecState* exec, KeyType key)
131 {
132     int32_t location;
133     if (key.value.isString()) {
134         auto iter = m_stringKeyedTable.find(asString(key.value)->value(exec).impl());
135         if (iter == m_stringKeyedTable.end())
136             return false;
137         location = iter->value;
138         m_stringKeyedTable.remove(iter);
139     } else if (key.value.isCell()) {
140         auto iter = m_cellKeyedTable.find(key.value.asCell());
141         if (iter == m_cellKeyedTable.end())
142             return false;
143         location = iter->value;
144         m_cellKeyedTable.remove(iter);
145     } else {
146         auto iter = m_valueKeyedTable.find(JSValue::encode(key.value));
147         if (iter == m_valueKeyedTable.end())
148             return false;
149         location = iter->value;
150         m_valueKeyedTable.remove(iter);
151     }
152     m_entries.get()[location].clear();
153     m_deletedCount++;
154     return true;
155 }
156
157 template<typename Entry, typename JSIterator>
158 inline void MapDataImpl<Entry, JSIterator>::replaceAndPackBackingStore(Entry* destination, int32_t newCapacity)
159 {
160     ASSERT(shouldPack());
161     int32_t newEnd = 0;
162     RELEASE_ASSERT(newCapacity > 0);
163     for (int32_t i = 0; i < m_size; i++) {
164         Entry& entry = m_entries.get()[i];
165         if (!entry.key()) {
166             m_iterators.forEach([newEnd](JSIterator* iterator, JSIterator*) {
167                 iterator->iteratorData()->didRemoveEntry(newEnd);
168             });
169             continue;
170         }
171         ASSERT(newEnd < newCapacity);
172         destination[newEnd] = entry;
173
174         // We overwrite the old entry with a forwarding index for the new entry,
175         // so that we can fix up our hash tables below without doing additional
176         // hash lookups
177         entry.setKeyWithoutWriteBarrier(jsNumber(newEnd));
178         newEnd++;
179     }
180
181     // Fixup for the hashmaps
182     for (auto ptr = m_valueKeyedTable.begin(); ptr != m_valueKeyedTable.end(); ++ptr)
183         ptr->value = m_entries.get()[ptr->value].key().get().asInt32();
184     for (auto ptr = m_cellKeyedTable.begin(); ptr != m_cellKeyedTable.end(); ++ptr)
185         ptr->value = m_entries.get()[ptr->value].key().get().asInt32();
186     for (auto ptr = m_stringKeyedTable.begin(); ptr != m_stringKeyedTable.end(); ++ptr)
187         ptr->value = m_entries.get()[ptr->value].key().get().asInt32();
188
189     ASSERT((m_size - newEnd) == m_deletedCount);
190     m_deletedCount = 0;
191
192     m_capacity = newCapacity;
193     m_size = newEnd;
194     m_entries.setWithoutBarrier(destination);
195 }
196
197 template<typename Entry, typename JSIterator>
198 inline void MapDataImpl<Entry, JSIterator>::replaceBackingStore(Entry* destination, int32_t newCapacity)
199 {
200     ASSERT(!shouldPack());
201     RELEASE_ASSERT(newCapacity > 0);
202     ASSERT(newCapacity >= m_capacity);
203     memcpy(destination, m_entries.get(), sizeof(Entry) * m_size);
204     m_capacity = newCapacity;
205     m_entries.setWithoutBarrier(destination);
206 }
207
208 template<typename Entry, typename JSIterator>
209 inline CheckedBoolean MapDataImpl<Entry, JSIterator>::ensureSpaceForAppend(ExecState* exec, JSCell* owner)
210 {
211     if (m_capacity > m_size)
212         return true;
213
214     size_t requiredSize = std::max(m_capacity + (m_capacity / 2) + 1, static_cast<int32_t>(minimumMapSize));
215     void* newStorage = nullptr;
216     DeferGC defer(*exec->heap());
217     if (!exec->heap()->tryAllocateStorage(owner, requiredSize * sizeof(Entry), &newStorage)) {
218         throwOutOfMemoryError(exec);
219         return false;
220     }
221     Entry* newEntries = static_cast<Entry*>(newStorage);
222     if (shouldPack())
223         replaceAndPackBackingStore(newEntries, requiredSize);
224     else
225         replaceBackingStore(newEntries, requiredSize);
226     exec->heap()->writeBarrier(owner);
227     return true;
228 }
229
230 template<typename Entry, typename JSIterator>
231 inline void MapDataImpl<Entry, JSIterator>::visitChildren(JSCell* owner, SlotVisitor& visitor)
232 {
233     Entry* entries = m_entries.get();
234     if (!entries)
235         return;
236     if (m_deletedCount) {
237         for (int32_t i = 0; i < m_size; i++) {
238             if (!entries[i].key())
239                 continue;
240             entries[i].visitChildren(visitor);
241         }
242     } else {
243         // Guaranteed that all fields of Entry type is WriteBarrier<Unknown>.
244         visitor.appendValues(reinterpret_cast<WriteBarrier<Unknown>*>(&entries[0]), m_size * (sizeof(Entry) / sizeof(WriteBarrier<Unknown>)));
245     }
246
247     visitor.copyLater(owner, MapBackingStoreCopyToken, m_entries.get(), capacityInBytes());
248 }
249
250 template<typename Entry, typename JSIterator>
251 inline void MapDataImpl<Entry, JSIterator>::copyBackingStore(CopyVisitor& visitor, CopyToken token)
252 {
253     if (token == MapBackingStoreCopyToken && visitor.checkIfShouldCopy(m_entries.get())) {
254         Entry* oldEntries = m_entries.get();
255         Entry* newEntries = static_cast<Entry*>(visitor.allocateNewSpace(capacityInBytes()));
256         if (shouldPack())
257             replaceAndPackBackingStore(newEntries, m_capacity);
258         else
259             replaceBackingStore(newEntries, m_capacity);
260         visitor.didCopy(oldEntries, capacityInBytes());
261     }
262 }
263
264 template<typename Entry, typename JSIterator>
265 inline auto MapDataImpl<Entry, JSIterator>::createIteratorData(JSIterator* iterator) -> IteratorData
266 {
267     m_iterators.set(iterator, iterator);
268     return IteratorData(this);
269 }
270
271 }