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