jcs.org
Serenity Operating System
1/*
2 * Copyright (c) 2020, Matthew Olsson <mattco@serenityos.org>
3 *
4 * SPDX-License-Identifier: BSD-2-Clause
5 */
6
7#include <AK/QuickSort.h>
8#include <LibJS/Runtime/Accessor.h>
9#include <LibJS/Runtime/IndexedProperties.h>
10
11namespace JS {
12
13constexpr const size_t SPARSE_ARRAY_HOLE_THRESHOLD = 200;
14constexpr const size_t LENGTH_SETTER_GENERIC_STORAGE_THRESHOLD = 4 * MiB;
15
16SimpleIndexedPropertyStorage::SimpleIndexedPropertyStorage(Vector<Value>&& initial_values)
17 : m_array_size(initial_values.size())
18 , m_packed_elements(move(initial_values))
19{
20}
21
22bool SimpleIndexedPropertyStorage::has_index(u32 index) const
23{
24 return index < m_array_size && !m_packed_elements[index].is_empty();
25}
26
27Optional<ValueAndAttributes> SimpleIndexedPropertyStorage::get(u32 index) const
28{
29 if (!has_index(index))
30 return {};
31 return ValueAndAttributes { m_packed_elements[index], default_attributes };
32}
33
34void SimpleIndexedPropertyStorage::grow_storage_if_needed()
35{
36 if (m_array_size <= m_packed_elements.size())
37 return;
38
39 if (m_array_size <= m_packed_elements.capacity()) {
40 m_packed_elements.resize_and_keep_capacity(m_array_size);
41 } else {
42 // When the array is actually full grow storage by 25% at a time.
43 m_packed_elements.resize_and_keep_capacity(m_array_size + (m_array_size / 4));
44 }
45}
46
47void SimpleIndexedPropertyStorage::put(u32 index, Value value, PropertyAttributes attributes)
48{
49 VERIFY(attributes == default_attributes);
50
51 if (index >= m_array_size) {
52 m_array_size = index + 1;
53 grow_storage_if_needed();
54 }
55 m_packed_elements[index] = value;
56}
57
58void SimpleIndexedPropertyStorage::remove(u32 index)
59{
60 VERIFY(index < m_array_size);
61 m_packed_elements[index] = {};
62}
63
64ValueAndAttributes SimpleIndexedPropertyStorage::take_first()
65{
66 m_array_size--;
67 return { m_packed_elements.take_first(), default_attributes };
68}
69
70ValueAndAttributes SimpleIndexedPropertyStorage::take_last()
71{
72 m_array_size--;
73 auto last_element = m_packed_elements[m_array_size];
74 m_packed_elements[m_array_size] = {};
75 return { last_element, default_attributes };
76}
77
78bool SimpleIndexedPropertyStorage::set_array_like_size(size_t new_size)
79{
80 m_array_size = new_size;
81 m_packed_elements.resize_and_keep_capacity(new_size);
82 return true;
83}
84
85GenericIndexedPropertyStorage::GenericIndexedPropertyStorage(SimpleIndexedPropertyStorage&& storage)
86{
87 m_array_size = storage.array_like_size();
88 for (size_t i = 0; i < storage.m_packed_elements.size(); ++i) {
89 auto value = storage.m_packed_elements[i];
90 if (!value.is_empty())
91 m_sparse_elements.set(i, { value, default_attributes });
92 }
93}
94
95bool GenericIndexedPropertyStorage::has_index(u32 index) const
96{
97 return m_sparse_elements.contains(index);
98}
99
100Optional<ValueAndAttributes> GenericIndexedPropertyStorage::get(u32 index) const
101{
102 if (index >= m_array_size)
103 return {};
104 return m_sparse_elements.get(index);
105}
106
107void GenericIndexedPropertyStorage::put(u32 index, Value value, PropertyAttributes attributes)
108{
109 if (index >= m_array_size)
110 m_array_size = index + 1;
111 m_sparse_elements.set(index, { value, attributes });
112}
113
114void GenericIndexedPropertyStorage::remove(u32 index)
115{
116 VERIFY(index < m_array_size);
117 m_sparse_elements.remove(index);
118}
119
120ValueAndAttributes GenericIndexedPropertyStorage::take_first()
121{
122 VERIFY(m_array_size > 0);
123 m_array_size--;
124
125 auto indices = m_sparse_elements.keys();
126 quick_sort(indices);
127
128 auto it = m_sparse_elements.find(indices.first());
129 auto first_element = it->value;
130 m_sparse_elements.remove(it);
131 return first_element;
132}
133
134ValueAndAttributes GenericIndexedPropertyStorage::take_last()
135{
136 VERIFY(m_array_size > 0);
137 m_array_size--;
138
139 auto result = m_sparse_elements.get(m_array_size);
140 if (!result.has_value())
141 return {};
142 m_sparse_elements.remove(m_array_size);
143 return result.value();
144}
145
146bool GenericIndexedPropertyStorage::set_array_like_size(size_t new_size)
147{
148 if (new_size == m_array_size)
149 return true;
150
151 if (new_size >= m_array_size) {
152 m_array_size = new_size;
153 return true;
154 }
155
156 bool any_failed = false;
157 size_t highest_index = 0;
158
159 HashMap<u32, ValueAndAttributes> new_sparse_elements;
160 for (auto& entry : m_sparse_elements) {
161 if (entry.key >= new_size) {
162 if (entry.value.attributes.is_configurable())
163 continue;
164 else
165 any_failed = true;
166 }
167 new_sparse_elements.set(entry.key, entry.value);
168 highest_index = max(highest_index, entry.key);
169 }
170
171 if (any_failed)
172 m_array_size = highest_index + 1;
173 else
174 m_array_size = new_size;
175
176 m_sparse_elements = move(new_sparse_elements);
177 return !any_failed;
178}
179
180IndexedPropertyIterator::IndexedPropertyIterator(IndexedProperties const& indexed_properties, u32 staring_index, bool skip_empty)
181 : m_indexed_properties(indexed_properties)
182 , m_index(staring_index)
183 , m_skip_empty(skip_empty)
184{
185 if (m_skip_empty) {
186 m_cached_indices = m_indexed_properties.indices();
187 skip_empty_indices();
188 }
189}
190
191IndexedPropertyIterator& IndexedPropertyIterator::operator++()
192{
193 m_index++;
194
195 if (m_skip_empty)
196 skip_empty_indices();
197
198 return *this;
199}
200
201IndexedPropertyIterator& IndexedPropertyIterator::operator*()
202{
203 return *this;
204}
205
206bool IndexedPropertyIterator::operator!=(IndexedPropertyIterator const& other) const
207{
208 return m_index != other.m_index;
209}
210
211void IndexedPropertyIterator::skip_empty_indices()
212{
213 for (auto i : m_cached_indices) {
214 if (i < m_index)
215 continue;
216 m_index = i;
217 return;
218 }
219 m_index = m_indexed_properties.array_like_size();
220}
221
222Optional<ValueAndAttributes> IndexedProperties::get(u32 index) const
223{
224 if (!m_storage)
225 return {};
226 return m_storage->get(index);
227}
228
229void IndexedProperties::put(u32 index, Value value, PropertyAttributes attributes)
230{
231 ensure_storage();
232 if (m_storage->is_simple_storage() && (attributes != default_attributes || index > (array_like_size() + SPARSE_ARRAY_HOLE_THRESHOLD))) {
233 switch_to_generic_storage();
234 }
235
236 m_storage->put(index, value, attributes);
237}
238
239void IndexedProperties::remove(u32 index)
240{
241 VERIFY(m_storage);
242 VERIFY(m_storage->has_index(index));
243 m_storage->remove(index);
244}
245
246bool IndexedProperties::set_array_like_size(size_t new_size)
247{
248 ensure_storage();
249 auto current_array_like_size = array_like_size();
250
251 // We can't use simple storage for lengths that don't fit in an i32.
252 // Also, to avoid gigantic unused storage allocations, let's put an (arbitrary) 4M cap on simple storage here.
253 // This prevents something like "a = []; a.length = 0x80000000;" from allocating 2G entries.
254 if (m_storage->is_simple_storage()
255 && (new_size > NumericLimits<i32>::max()
256 || (current_array_like_size < LENGTH_SETTER_GENERIC_STORAGE_THRESHOLD && new_size > LENGTH_SETTER_GENERIC_STORAGE_THRESHOLD))) {
257 switch_to_generic_storage();
258 }
259
260 return m_storage->set_array_like_size(new_size);
261}
262
263size_t IndexedProperties::real_size() const
264{
265 if (!m_storage)
266 return 0;
267 if (m_storage->is_simple_storage()) {
268 auto& packed_elements = static_cast<SimpleIndexedPropertyStorage const&>(*m_storage).elements();
269 size_t size = 0;
270 for (auto& element : packed_elements) {
271 if (!element.is_empty())
272 ++size;
273 }
274 return size;
275 }
276 return static_cast<GenericIndexedPropertyStorage const&>(*m_storage).size();
277}
278
279Vector<u32> IndexedProperties::indices() const
280{
281 if (!m_storage)
282 return {};
283 if (m_storage->is_simple_storage()) {
284 auto const& storage = static_cast<SimpleIndexedPropertyStorage const&>(*m_storage);
285 auto const& elements = storage.elements();
286 Vector<u32> indices;
287 indices.ensure_capacity(storage.array_like_size());
288 for (size_t i = 0; i < elements.size(); ++i) {
289 if (!elements.at(i).is_empty())
290 indices.unchecked_append(i);
291 }
292 return indices;
293 }
294 auto const& storage = static_cast<GenericIndexedPropertyStorage const&>(*m_storage);
295 auto indices = storage.sparse_elements().keys();
296 quick_sort(indices);
297 return indices;
298}
299
300void IndexedProperties::switch_to_generic_storage()
301{
302 if (!m_storage) {
303 m_storage = make<GenericIndexedPropertyStorage>();
304 return;
305 }
306 auto& storage = static_cast<SimpleIndexedPropertyStorage&>(*m_storage);
307 m_storage = make<GenericIndexedPropertyStorage>(move(storage));
308}
309
310void IndexedProperties::ensure_storage()
311{
312 if (!m_storage)
313 m_storage = make<SimpleIndexedPropertyStorage>();
314}
315
316}