[JSC] Implement optimized WeakMap and WeakSet
[WebKit-https.git] / Source / JavaScriptCore / runtime / WeakMapImpl.cpp
1 /*
2  * Copyright (C) 2017 Apple Inc. All rights reserved.
3  * Copyright (C) 2017 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. ``AS IS'' AND ANY
15  * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
16  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR
17  * PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL APPLE INC. OR
18  * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
19  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
20  * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
21  * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY
22  * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
23  * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
24  * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
25  */
26
27 #include "config.h"
28 #include "WeakMapImpl.h"
29
30 #include "JSCInlines.h"
31
32 namespace JSC {
33
34 template <typename WeakMapBucket>
35 void WeakMapImpl<WeakMapBucket>::destroy(JSCell* cell)
36 {
37     static_cast<WeakMapImpl*>(cell)->~WeakMapImpl();
38 }
39
40 template <typename WeakMapBucket>
41 void WeakMapImpl<WeakMapBucket>::visitChildren(JSCell* cell, SlotVisitor& visitor)
42 {
43     WeakMapImpl* thisObject = jsCast<WeakMapImpl*>(cell);
44     ASSERT_GC_OBJECT_INHERITS(thisObject, info());
45     Base::visitChildren(thisObject, visitor);
46
47     visitor.addUnconditionalFinalizer(&thisObject->m_deadKeyCleaner);
48     if (std::is_same<WeakMapBucket, JSC::WeakMapBucket<WeakMapBucketDataKeyValue>>::value)
49         visitor.addWeakReferenceHarvester(&thisObject->m_deadKeyCleaner);
50
51     visitor.reportExtraMemoryVisited(thisObject->m_capacity * sizeof(WeakMapBucket));
52 }
53
54 template <typename WeakMapBucket>
55 size_t WeakMapImpl<WeakMapBucket>::estimatedSize(JSCell* cell)
56 {
57     auto* thisObject = static_cast<WeakMapImpl*>(cell);
58     return Base::estimatedSize(thisObject) + (sizeof(WeakMapImpl) - sizeof(Base)) + thisObject->m_capacity * sizeof(WeakMapBucket);
59 }
60
61 template <>
62 void WeakMapImpl<WeakMapBucket<WeakMapBucketDataKey>>::visitWeakReferences(SlotVisitor&)
63 {
64     // Only JSWeakMap needs to harvest value references
65 }
66
67 template <>
68 void WeakMapImpl<WeakMapBucket<WeakMapBucketDataKeyValue>>::visitWeakReferences(SlotVisitor& visitor)
69 {
70     auto* buffer = this->buffer();
71     for (uint32_t index = 0; index < m_capacity; ++index) {
72         auto* bucket = buffer + index;
73         if (bucket->isEmpty() || bucket->isDeleted())
74             continue;
75         if (!Heap::isMarked(bucket->key()))
76             continue;
77         bucket->visitAggregate(visitor);
78     }
79 }
80
81 template <typename WeakMapBucket>
82 void WeakMapImpl<WeakMapBucket>::finalizeUnconditionally()
83 {
84     auto* buffer = this->buffer();
85     for (uint32_t index = 0; index < m_capacity; ++index) {
86         auto* bucket = buffer + index;
87         if (bucket->isEmpty() || bucket->isDeleted())
88             continue;
89
90         if (Heap::isMarked(bucket->key()))
91             continue;
92
93         bucket->makeDeleted();
94         ++m_deleteCount;
95         RELEASE_ASSERT(m_keyCount > 0);
96         --m_keyCount;
97     }
98
99     if (shouldShrink())
100         rehash(RehashMode::RemoveBatching);
101 }
102
103 template <typename WeakMapBucket>
104 template<typename Appender>
105 void WeakMapImpl<WeakMapBucket>::takeSnapshotInternal(unsigned limit, Appender appender)
106 {
107     DisallowGC disallowGC;
108     unsigned fetched = 0;
109     forEach([&] (JSObject* key, JSValue value) {
110         appender(key, value);
111         ++fetched;
112         if (limit && fetched >= limit)
113             return IterationState::Stop;
114         return IterationState::Continue;
115     });
116 }
117
118 // takeSnapshot must not invoke garbage collection since iterating WeakMap may be modified.
119 template <>
120 void WeakMapImpl<WeakMapBucket<WeakMapBucketDataKey>>::takeSnapshot(MarkedArgumentBuffer& buffer, unsigned limit)
121 {
122     takeSnapshotInternal(limit, [&] (JSObject* key, JSValue) {
123         buffer.append(key);
124     });
125 }
126
127 template <>
128 void WeakMapImpl<WeakMapBucket<WeakMapBucketDataKeyValue>>::takeSnapshot(MarkedArgumentBuffer& buffer, unsigned limit)
129 {
130     takeSnapshotInternal(limit, [&] (JSObject* key, JSValue value) {
131         buffer.append(key);
132         buffer.append(value);
133     });
134 }
135
136 template class WeakMapImpl<WeakMapBucket<WeakMapBucketDataKeyValue>>;
137 template class WeakMapImpl<WeakMapBucket<WeakMapBucketDataKey>>;
138
139 } // namespace JSC