[WTF] Import std::optional reference implementation as WTF::Optional
[WebKit-https.git] / Source / JavaScriptCore / runtime / HashMapImpl.h
1 /*
2  * Copyright (C) 2016 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 "ExceptionHelpers.h"
29 #include "JSObject.h"
30
31 namespace JSC {
32
33 JS_EXPORT_PRIVATE const ClassInfo* getHashMapBucketKeyClassInfo();
34 JS_EXPORT_PRIVATE const ClassInfo* getHashMapBucketKeyValueClassInfo();
35 JS_EXPORT_PRIVATE const ClassInfo* getHashMapImplKeyClassInfo();
36 JS_EXPORT_PRIVATE const ClassInfo* getHashMapImplKeyValueClassInfo();
37
38 enum class HashTableType {
39     Key,
40     KeyValue
41 };
42
43 struct HashMapBucketDataKey {
44     static const HashTableType Type = HashTableType::Key;
45     WriteBarrier<Unknown> key;
46 };
47
48 struct HashMapBucketDataKeyValue {
49     static const HashTableType Type = HashTableType::KeyValue;
50     WriteBarrier<Unknown> key;
51     WriteBarrier<Unknown> value;
52 };
53
54 template <typename Data>
55 class HashMapBucket : public JSCell {
56     typedef JSCell Base;
57
58     template <typename T = Data>
59     static typename std::enable_if<std::is_same<T, HashMapBucketDataKey>::value, Structure*>::type selectStructure(VM& vm)
60     {
61         return vm.hashMapBucketSetStructure.get();
62     }
63
64     template <typename T = Data>
65     static typename std::enable_if<std::is_same<T, HashMapBucketDataKeyValue>::value, Structure*>::type selectStructure(VM& vm)
66     {
67         return vm.hashMapBucketMapStructure.get();
68     }
69
70 public:
71     static const HashTableType Type = Data::Type;
72     static const ClassInfo s_info; // This is never accessed directly, since that would break linkage on some compilers.
73
74     static const ClassInfo* info()
75     {
76         switch (Type) {
77         case HashTableType::Key:
78             return getHashMapBucketKeyClassInfo();
79         case HashTableType::KeyValue:
80             return getHashMapBucketKeyValueClassInfo();
81         }
82         RELEASE_ASSERT_NOT_REACHED();
83     }
84
85     static Structure* createStructure(VM& vm, JSGlobalObject* globalObject, JSValue prototype)
86     {
87         return Structure::create(vm, globalObject, prototype, TypeInfo(CellType, StructureFlags), info());
88     }
89
90     static HashMapBucket* create(VM& vm)
91     {
92         HashMapBucket* bucket = new (NotNull, allocateCell<HashMapBucket<Data>>(vm.heap)) HashMapBucket(vm, selectStructure(vm));
93         bucket->finishCreation(vm);
94         ASSERT(!bucket->next());
95         ASSERT(!bucket->prev());
96         return bucket;
97     }
98
99     HashMapBucket(VM& vm, Structure* structure)
100         : Base(vm, structure)
101     { }
102
103     ALWAYS_INLINE void setNext(VM& vm, HashMapBucket* bucket)
104     {
105         m_next.set(vm, this, bucket);
106     }
107     ALWAYS_INLINE void setPrev(VM& vm, HashMapBucket* bucket)
108     {
109         m_prev.set(vm, this, bucket);
110     }
111
112     ALWAYS_INLINE void setKey(VM& vm, JSValue key)
113     {
114         m_data.key.set(vm, this, key);
115     }
116
117     template <typename T = Data>
118     ALWAYS_INLINE typename std::enable_if<std::is_same<T, HashMapBucketDataKeyValue>::value>::type setValue(VM& vm, JSValue value)
119     {
120         m_data.value.set(vm, this, value);
121     }
122     template <typename T = Data>
123     ALWAYS_INLINE typename std::enable_if<std::is_same<T, HashMapBucketDataKey>::value>::type setValue(VM&, JSValue) { }
124
125     ALWAYS_INLINE JSValue key() const { return m_data.key.get(); }
126
127     template <typename T = Data>
128     ALWAYS_INLINE typename std::enable_if<std::is_same<T, HashMapBucketDataKeyValue>::value, JSValue>::type value() const
129     {
130         return m_data.value.get();
131     }
132
133     static void visitChildren(JSCell*, SlotVisitor&);
134
135     ALWAYS_INLINE HashMapBucket* next() const { return m_next.get(); }
136     ALWAYS_INLINE HashMapBucket* prev() const { return m_prev.get(); }
137
138     ALWAYS_INLINE bool deleted() const { return m_deleted; }
139     ALWAYS_INLINE void setDeleted(bool deleted) { m_deleted = deleted; }
140
141     static ptrdiff_t offsetOfKey()
142     {
143         return OBJECT_OFFSETOF(HashMapBucket, m_data) + OBJECT_OFFSETOF(Data, key);
144     }
145
146     template <typename T = Data>
147     static typename std::enable_if<std::is_same<T, HashMapBucketDataKeyValue>::value, ptrdiff_t>::type offsetOfValue()
148     {
149         return OBJECT_OFFSETOF(HashMapBucket, m_data) + OBJECT_OFFSETOF(Data, value);
150     }
151
152 private:
153     Data m_data;
154     WriteBarrier<HashMapBucket> m_next;
155     WriteBarrier<HashMapBucket> m_prev;
156     bool m_deleted { false };
157 };
158
159 template <typename BucketType>
160 class HashMapBuffer {
161 public:
162     HashMapBuffer() = delete;
163
164     static size_t allocationSize(uint32_t capacity)
165     {
166         return capacity * sizeof(BucketType*);
167     }
168
169     ALWAYS_INLINE BucketType** buffer() const
170     {
171         return bitwise_cast<BucketType**>(this);
172     }
173
174     static HashMapBuffer* create(ExecState* exec, VM& vm, JSCell* owner, uint32_t capacity)
175     {
176         auto scope = DECLARE_THROW_SCOPE(vm);
177         size_t allocationSize = HashMapBuffer::allocationSize(capacity);
178         void* data = vm.heap.tryAllocateAuxiliary(owner, allocationSize);
179         if (!data) {
180             throwOutOfMemoryError(exec, scope);
181             return nullptr;
182         }
183
184         HashMapBuffer* buffer = static_cast<HashMapBuffer*>(data);
185         buffer->reset(capacity);
186         return buffer;
187     }
188
189     ALWAYS_INLINE void reset(uint32_t capacity)
190     {
191         memset(this, -1, allocationSize(capacity));
192     }
193 };
194
195 ALWAYS_INLINE static bool areKeysEqual(ExecState* exec, JSValue a, JSValue b)
196 {
197     // We want +0 and -0 to be compared to true here. sameValue() itself doesn't
198     // guarantee that, however, we normalize all keys before comparing and storing
199     // them in the map. The normalization will convert -0.0 and 0.0 to the integer
200     // representation for 0.
201     return sameValue(exec, a, b);
202 }
203
204 ALWAYS_INLINE JSValue normalizeMapKey(JSValue key)
205 {
206     if (!key.isNumber())
207         return key;
208
209     if (key.isInt32())
210         return key;
211
212     double d = key.asDouble();
213     if (std::isnan(d))
214         return key;
215
216     int i = static_cast<int>(d);
217     if (i == d) {
218         // When a key is -0, we convert it to positive zero.
219         // When a key is the double representation for an integer, we convert it to an integer.
220         return jsNumber(i);
221     }
222     // This means key is definitely not negative zero, and it's definitely not a double representation of an integer. 
223     return key;
224 }
225
226 static ALWAYS_INLINE uint32_t wangsInt64Hash(uint64_t key)
227 {
228     key += ~(key << 32);
229     key ^= (key >> 22);
230     key += ~(key << 13);
231     key ^= (key >> 8);
232     key += (key << 3);
233     key ^= (key >> 15);
234     key += ~(key << 27);
235     key ^= (key >> 31);
236     return static_cast<unsigned>(key);
237 }
238
239 ALWAYS_INLINE uint32_t jsMapHash(ExecState* exec, VM& vm, JSValue value)
240 {
241     ASSERT_WITH_MESSAGE(normalizeMapKey(value) == value, "We expect normalized values flowing into this function.");
242
243     auto scope = DECLARE_THROW_SCOPE(vm);
244
245     if (value.isString()) {
246         JSString* string = asString(value);
247         const String& wtfString = string->value(exec);
248         RETURN_IF_EXCEPTION(scope, UINT_MAX);
249         return wtfString.impl()->hash();
250     }
251
252     uint64_t rawValue = JSValue::encode(value);
253     return wangsInt64Hash(rawValue);
254 }
255
256 ALWAYS_INLINE std::optional<uint32_t> concurrentJSMapHash(JSValue key)
257 {
258     key = normalizeMapKey(key);
259     if (key.isString()) {
260         JSString* string = asString(key);
261         if (string->length() > 10 * 1024)
262             return std::nullopt;
263         const StringImpl* impl = string->tryGetValueImpl();
264         if (!impl)
265             return std::nullopt;
266         return impl->concurrentHash();
267     }
268
269     uint64_t rawValue = JSValue::encode(key);
270     return wangsInt64Hash(rawValue);
271 }
272
273 template <typename HashMapBucketType>
274 class HashMapImpl : public JSCell {
275     typedef JSCell Base;
276     typedef HashMapBuffer<HashMapBucketType> HashMapBufferType;
277
278     template <typename T = HashMapBucketType>
279     static typename std::enable_if<std::is_same<T, HashMapBucket<HashMapBucketDataKey>>::value, Structure*>::type selectStructure(VM& vm)
280     {
281         return vm.hashMapImplSetStructure.get();
282     }
283
284     template <typename T = HashMapBucketType>
285     static typename std::enable_if<std::is_same<T, HashMapBucket<HashMapBucketDataKeyValue>>::value, Structure*>::type selectStructure(VM& vm)
286     {
287         return vm.hashMapImplMapStructure.get();
288     }
289
290 public:
291     static const ClassInfo s_info; // This is never accessed directly, since that would break linkage on some compilers.
292
293     static const ClassInfo* info()
294     {
295         switch (HashMapBucketType::Type) {
296         case HashTableType::Key:
297             return getHashMapImplKeyClassInfo();
298         case HashTableType::KeyValue:
299             return getHashMapImplKeyValueClassInfo();
300         }
301         RELEASE_ASSERT_NOT_REACHED();
302     }
303
304     static Structure* createStructure(VM& vm, JSGlobalObject* globalObject, JSValue prototype)
305     {
306         return Structure::create(vm, globalObject, prototype, TypeInfo(CellType, StructureFlags), info());
307     }
308
309     static HashMapImpl* create(ExecState* exec, VM& vm)
310     {
311         ASSERT_WITH_MESSAGE(HashMapBucket<HashMapBucketDataKey>::offsetOfKey() == HashMapBucket<HashMapBucketDataKeyValue>::offsetOfKey(), "We assume this to be true in the DFG and FTL JIT.");
312
313         HashMapImpl* impl = new (NotNull, allocateCell<HashMapImpl>(vm.heap)) HashMapImpl(vm, selectStructure(vm));
314         impl->finishCreation(exec, vm);
315         return impl;
316     }
317
318     static void visitChildren(JSCell*, SlotVisitor&);
319
320     HashMapImpl(VM& vm, Structure* structure)
321         : Base(vm, structure)
322         , m_keyCount(0)
323         , m_deleteCount(0)
324         , m_capacity(4)
325     {
326     }
327
328     ALWAYS_INLINE HashMapBucketType** buffer() const
329     {
330         return m_buffer.get()->buffer();
331     }
332
333     void finishCreation(ExecState* exec, VM& vm)
334     {
335         auto scope = DECLARE_THROW_SCOPE(vm);
336         Base::finishCreation(vm);
337
338         makeAndSetNewBuffer(exec, vm);
339         RETURN_IF_EXCEPTION(scope, void());
340
341         m_head.set(vm, this, HashMapBucketType::create(vm));
342         m_tail.set(vm, this, HashMapBucketType::create(vm));
343
344         m_head->setNext(vm, m_tail.get());
345         m_tail->setPrev(vm, m_head.get());
346         m_head->setDeleted(true);
347         m_tail->setDeleted(true);
348
349     }
350
351     static HashMapBucketType* emptyValue()
352     {
353         return bitwise_cast<HashMapBucketType*>(static_cast<uintptr_t>(-1));
354     }
355
356     static ALWAYS_INLINE bool isEmpty(HashMapBucketType* bucket)
357     {
358         return bucket == emptyValue();
359     }
360
361     static HashMapBucketType* deletedValue()
362     {
363         return bitwise_cast<HashMapBucketType*>(static_cast<uintptr_t>(-3));
364     }
365
366     static ALWAYS_INLINE bool isDeleted(HashMapBucketType* bucket)
367     {
368         return bucket == deletedValue();
369     }
370
371     ALWAYS_INLINE HashMapBucketType** findBucket(ExecState* exec, JSValue key)
372     {
373         VM& vm = exec->vm();
374         auto scope = DECLARE_THROW_SCOPE(vm);
375         key = normalizeMapKey(key);
376         uint32_t hash = jsMapHash(exec, vm, key);
377         RETURN_IF_EXCEPTION(scope, nullptr);
378         return findBucket(exec, key, hash);
379     }
380
381     ALWAYS_INLINE HashMapBucketType** findBucket(ExecState* exec, JSValue key, uint32_t hash)
382     {
383         ASSERT_WITH_MESSAGE(normalizeMapKey(key) == key, "We expect normalized values flowing into this function.");
384         return findBucketAlreadyHashedAndNormalized(exec, key, hash);
385     }
386
387     ALWAYS_INLINE JSValue get(ExecState* exec, JSValue key)
388     {
389         if (HashMapBucketType** bucket = findBucket(exec, key))
390             return (*bucket)->value();
391         return jsUndefined();
392     }
393
394     ALWAYS_INLINE bool has(ExecState* exec, JSValue key)
395     {
396         return !!findBucket(exec, key);
397     }
398
399     ALWAYS_INLINE void add(ExecState* exec, JSValue key, JSValue value = JSValue())
400     {
401         key = normalizeMapKey(key);
402
403         VM& vm = exec->vm();
404         auto scope = DECLARE_THROW_SCOPE(vm);
405
406         const uint32_t mask = m_capacity - 1;
407         uint32_t index = jsMapHash(exec, vm, key) & mask;
408         RETURN_IF_EXCEPTION(scope, void());
409         HashMapBucketType** buffer = this->buffer();
410         HashMapBucketType* bucket = buffer[index];
411         while (!isEmpty(bucket)) {
412             if (!isDeleted(bucket) && areKeysEqual(exec, key, bucket->key())) {
413                 bucket->setValue(vm, value);
414                 return;
415             }
416             index = (index + 1) & mask;
417             bucket = buffer[index];
418         }
419
420         HashMapBucketType* newEntry = m_tail.get();
421         buffer[index] = newEntry;
422         newEntry->setKey(vm, key);
423         newEntry->setValue(vm, value);
424         newEntry->setDeleted(false);
425         HashMapBucketType* newTail = HashMapBucketType::create(vm);
426         m_tail.set(vm, this, newTail);
427         newTail->setPrev(vm, newEntry);
428         newTail->setDeleted(true);
429         newEntry->setNext(vm, newTail);
430
431         ++m_keyCount;
432
433         if (shouldRehashAfterAdd())
434             rehash(exec);
435     }
436
437     ALWAYS_INLINE bool remove(ExecState* exec, JSValue key)
438     {
439         HashMapBucketType** bucket = findBucket(exec, key);
440         if (!bucket)
441             return false;
442
443         VM& vm = exec->vm();
444         HashMapBucketType* impl = *bucket;
445         impl->next()->setPrev(vm, impl->prev());
446         impl->prev()->setNext(vm, impl->next());
447         impl->setDeleted(true);
448
449         *bucket = deletedValue();
450
451         ++m_deleteCount;
452         ASSERT(m_keyCount > 0);
453         --m_keyCount;
454
455         if (shouldShrink())
456             rehash(exec);
457
458         return true;
459     }
460
461     ALWAYS_INLINE uint32_t size() const
462     {
463         return m_keyCount;
464     }
465
466     ALWAYS_INLINE void clear(ExecState* exec)
467     {
468         VM& vm = exec->vm();
469         m_keyCount = 0;
470         m_deleteCount = 0;
471         HashMapBucketType* head = m_head.get();
472         HashMapBucketType* bucket = m_head->next();
473         HashMapBucketType* tail = m_tail.get();
474         while (bucket != tail) {
475             HashMapBucketType* next = bucket->next();
476             // We restart each iterator by pointing it to the head of the list.
477             bucket->setNext(vm, head);
478             bucket->setDeleted(true);
479             bucket = next;
480         }
481         m_head->setNext(vm, m_tail.get());
482         m_tail->setPrev(vm, m_head.get());
483         m_capacity = 4;
484         makeAndSetNewBuffer(exec, vm);
485         checkConsistency();
486     }
487
488     ALWAYS_INLINE size_t bufferSizeInBytes() const
489     {
490         return m_capacity * sizeof(HashMapBucketType*);
491     }
492
493     static ptrdiff_t offsetOfBuffer()
494     {
495         return OBJECT_OFFSETOF(HashMapImpl<HashMapBucketType>, m_buffer);
496     }
497
498     static ptrdiff_t offsetOfCapacity()
499     {
500         return OBJECT_OFFSETOF(HashMapImpl<HashMapBucketType>, m_capacity);
501     }
502
503     HashMapBucketType* head() { return m_head.get(); }
504     HashMapBucketType* tail() { return m_tail.get(); }
505
506     size_t approximateSize() const
507     {
508         size_t size = sizeof(HashMapImpl);
509         size += bufferSizeInBytes();
510         size += 2 * sizeof(HashMapBucketType); // Head and tail members.
511         size += m_keyCount * sizeof(HashMapBucketType); // Number of members that are on the list.
512         return size;
513     }
514
515 private:
516     ALWAYS_INLINE uint32_t shouldRehashAfterAdd() const
517     {
518         return 2 * (m_keyCount + m_deleteCount) >= m_capacity;
519     }
520
521     ALWAYS_INLINE uint32_t shouldShrink() const
522     {
523         return 8 * m_keyCount <= m_capacity && m_capacity > 4;
524     }
525
526     ALWAYS_INLINE HashMapBucketType** findBucketAlreadyHashedAndNormalized(ExecState* exec, JSValue key, uint32_t hash)
527     {
528         const uint32_t mask = m_capacity - 1;
529         uint32_t index = hash & mask;
530         HashMapBucketType** buffer = this->buffer();
531         HashMapBucketType* bucket = buffer[index];
532
533         while (!isEmpty(bucket)) {
534             if (!isDeleted(bucket) && areKeysEqual(exec, key, bucket->key()))
535                 return buffer + index;
536             index = (index + 1) & mask;
537             bucket = buffer[index];
538         }
539         return nullptr;
540     }
541
542     void rehash(ExecState* exec)
543     {
544         VM& vm = exec->vm();
545         auto scope = DECLARE_THROW_SCOPE(vm);
546
547         uint32_t oldCapacity = m_capacity;
548         if (shouldShrink()) {
549             m_capacity = m_capacity / 2;
550             ASSERT(m_capacity >= 4);
551         } else if (3 * m_keyCount <= m_capacity && m_capacity > 64) {
552             // We stay at the same size if rehashing would cause us to be no more than
553             // 1/3rd full. This comes up for programs like this:
554             // Say the hash table grew to a key count of 64, causing it to grow to a capacity of 256.
555             // Then, the table added 63 items. The load is now 127. Then, 63 items are deleted.
556             // The load is still 127. Then, another item is added. The load is now 128, and we
557             // decide that we need to rehash. The key count is 65, almost exactly what it was
558             // when we grew to a capacity of 256. We don't really need to grow to a capacity
559             // of 512 in this situation. Instead, we choose to rehash at the same size. This
560             // will bring the load down to 65. We rehash into the same size when we determine
561             // that the new load ratio will be under 1/3rd. (We also pick a minumum capacity
562             // at which this rule kicks in because otherwise we will be too sensitive to rehashing
563             // at the same capacity).
564         } else
565             m_capacity = (Checked<uint32_t>(m_capacity) * 2).unsafeGet();
566
567         if (m_capacity != oldCapacity) {
568             makeAndSetNewBuffer(exec, vm);
569             RETURN_IF_EXCEPTION(scope, void());
570         } else {
571             m_buffer.get()->reset(m_capacity);
572             assertBufferIsEmpty();
573         }
574
575         HashMapBucketType* iter = m_head->next();
576         HashMapBucketType* end = m_tail.get();
577         const uint32_t mask = m_capacity - 1;
578         RELEASE_ASSERT(!(m_capacity & (m_capacity - 1)));
579         HashMapBucketType** buffer = this->buffer();
580         while (iter != end) {
581             uint32_t index = jsMapHash(exec, vm, iter->key()) & mask;
582             ASSERT_WITH_MESSAGE(!scope.exception(), "All keys should already be hashed before, so this should not throw because it won't resolve ropes.");
583             {
584                 HashMapBucketType* bucket = buffer[index];
585                 while (!isEmpty(bucket)) {
586                     index = (index + 1) & mask;
587                     bucket = buffer[index];
588                 }
589             }
590             buffer[index] = iter;
591             iter = iter->next();
592         }
593
594         m_deleteCount = 0;
595
596         checkConsistency();
597     }
598
599     ALWAYS_INLINE void checkConsistency() const
600     {
601         if (!ASSERT_DISABLED) {
602             HashMapBucketType* iter = m_head->next();
603             HashMapBucketType* end = m_tail.get();
604             uint32_t size = 0;
605             while (iter != end) {
606                 ++size;
607                 iter = iter->next();
608             }
609             ASSERT(size == m_keyCount);
610         }
611     }
612
613     void makeAndSetNewBuffer(ExecState* exec, VM& vm)
614     {
615         ASSERT(!(m_capacity & (m_capacity - 1)));
616
617         HashMapBufferType* buffer = HashMapBufferType::create(exec, vm, this, m_capacity);
618         if (UNLIKELY(!buffer))
619             return;
620
621         m_buffer.set(vm, this, buffer);
622         assertBufferIsEmpty();
623     }
624
625     ALWAYS_INLINE void assertBufferIsEmpty() const
626     {
627         if (!ASSERT_DISABLED) {
628             for (unsigned i = 0; i < m_capacity; i++)
629                 ASSERT(isEmpty(buffer()[i]));
630         }
631     }
632
633     WriteBarrier<HashMapBucketType> m_head;
634     WriteBarrier<HashMapBucketType> m_tail;
635     AuxiliaryBarrier<HashMapBufferType*> m_buffer;
636     uint32_t m_keyCount;
637     uint32_t m_deleteCount;
638     uint32_t m_capacity;
639 };
640
641 } // namespace JSC