1/*
2 * Copyright (C) 1999-2000 Harri Porten ([email protected])
3 * Copyright (C) 2003-2019 Apple Inc. All rights reserved.
4 * Copyright (C) 2003 Peter Kelly ([email protected])
5 * Copyright (C) 2006 Alexey Proskuryakov ([email protected])
6 *
7 * This library is free software; you can redistribute it and/or
8 * modify it under the terms of the GNU Lesser General Public
9 * License as published by the Free Software Foundation; either
10 * version 2 of the License, or (at your option) any later version.
11 *
12 * This library is distributed in the hope that it will be useful,
13 * but WITHOUT ANY WARRANTY; without even the implied warranty of
14 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 * Lesser General Public License for more details.
16 *
17 * You should have received a copy of the GNU Lesser General Public
18 * License along with this library; if not, write to the Free Software
19 * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
20 *
21 */
22
23#include "config.h"
24#include "JSArray.h"
25
26#include "ArrayPrototype.h"
27#include "ButterflyInlines.h"
28#include "CodeBlock.h"
29#include "Error.h"
30#include "GetterSetter.h"
31#include "IndexingHeaderInlines.h"
32#include "JSArrayInlines.h"
33#include "JSCInlines.h"
34#include "PropertyNameArray.h"
35#include "TypeError.h"
36#include <wtf/Assertions.h>
37
38namespace JSC {
39
40const ASCIILiteral LengthExceededTheMaximumArrayLengthError { "Length exceeded the maximum array length"_s };
41
42STATIC_ASSERT_IS_TRIVIALLY_DESTRUCTIBLE(JSArray);
43
44const ClassInfo JSArray::s_info = {"Array", &JSNonFinalObject::s_info, nullptr, nullptr, CREATE_METHOD_TABLE(JSArray)};
45
46JSArray* JSArray::tryCreateUninitializedRestricted(ObjectInitializationScope& scope, GCDeferralContext* deferralContext, Structure* structure, unsigned initialLength)
47{
48 VM& vm = scope.vm();
49
50 if (UNLIKELY(initialLength > MAX_STORAGE_VECTOR_LENGTH))
51 return nullptr;
52
53 unsigned outOfLineStorage = structure->outOfLineCapacity();
54 Butterfly* butterfly;
55 IndexingType indexingType = structure->indexingType();
56 if (LIKELY(!hasAnyArrayStorage(indexingType))) {
57 ASSERT(
58 hasUndecided(indexingType)
59 || hasInt32(indexingType)
60 || hasDouble(indexingType)
61 || hasContiguous(indexingType));
62
63 unsigned vectorLength = Butterfly::optimalContiguousVectorLength(structure, initialLength);
64 void* temp = vm.jsValueGigacageAuxiliarySpace.allocateNonVirtual(
65 vm,
66 Butterfly::totalSize(0, outOfLineStorage, true, vectorLength * sizeof(EncodedJSValue)),
67 deferralContext, AllocationFailureMode::ReturnNull);
68 if (UNLIKELY(!temp))
69 return nullptr;
70 butterfly = Butterfly::fromBase(temp, 0, outOfLineStorage);
71 butterfly->setVectorLength(vectorLength);
72 butterfly->setPublicLength(initialLength);
73 if (hasDouble(indexingType)) {
74 for (unsigned i = initialLength; i < vectorLength; ++i)
75 butterfly->contiguousDouble().atUnsafe(i) = PNaN;
76 } else {
77 for (unsigned i = initialLength; i < vectorLength; ++i)
78 butterfly->contiguous().atUnsafe(i).clear();
79 }
80 } else {
81 ASSERT(
82 indexingType == ArrayWithSlowPutArrayStorage
83 || indexingType == ArrayWithArrayStorage);
84 static constexpr unsigned indexBias = 0;
85 unsigned vectorLength = ArrayStorage::optimalVectorLength(indexBias, structure, initialLength);
86 void* temp = vm.jsValueGigacageAuxiliarySpace.allocateNonVirtual(
87 vm,
88 Butterfly::totalSize(indexBias, outOfLineStorage, true, ArrayStorage::sizeFor(vectorLength)),
89 deferralContext, AllocationFailureMode::ReturnNull);
90 if (UNLIKELY(!temp))
91 return nullptr;
92 butterfly = Butterfly::fromBase(temp, indexBias, outOfLineStorage);
93 *butterfly->indexingHeader() = indexingHeaderForArrayStorage(initialLength, vectorLength);
94 ArrayStorage* storage = butterfly->arrayStorage();
95 storage->m_indexBias = indexBias;
96 storage->m_sparseMap.clear();
97 storage->m_numValuesInVector = initialLength;
98 for (unsigned i = initialLength; i < vectorLength; ++i)
99 storage->m_vector[i].clear();
100 }
101
102 JSArray* result = createWithButterfly(vm, deferralContext, structure, butterfly);
103
104 const bool createUninitialized = true;
105 scope.notifyAllocated(result, createUninitialized);
106 return result;
107}
108
109void JSArray::eagerlyInitializeButterfly(ObjectInitializationScope& scope, JSArray* array, unsigned initialLength)
110{
111 Structure* structure = array->structure(scope.vm());
112 IndexingType indexingType = structure->indexingType();
113 Butterfly* butterfly = array->butterfly();
114
115 // This function only serves as a companion to tryCreateUninitializedRestricted()
116 // in the event that we really can't defer initialization of the butterfly after all.
117 // tryCreateUninitializedRestricted() already initialized the elements between
118 // initialLength and vector length. We just need to do 0 - initialLength.
119 // ObjectInitializationScope::notifyInitialized() will verify that all elements are
120 // initialized.
121 if (LIKELY(!hasAnyArrayStorage(indexingType))) {
122 if (hasDouble(indexingType)) {
123 for (unsigned i = 0; i < initialLength; ++i)
124 butterfly->contiguousDouble().atUnsafe(i) = PNaN;
125 } else {
126 for (unsigned i = 0; i < initialLength; ++i)
127 butterfly->contiguous().atUnsafe(i).clear();
128 }
129 } else {
130 ArrayStorage* storage = butterfly->arrayStorage();
131 for (unsigned i = 0; i < initialLength; ++i)
132 storage->m_vector[i].clear();
133 }
134 scope.notifyInitialized(array);
135}
136
137void JSArray::setLengthWritable(JSGlobalObject* globalObject, bool writable)
138{
139 ASSERT(isLengthWritable() || !writable);
140 if (!isLengthWritable() || writable)
141 return;
142
143 enterDictionaryIndexingMode(globalObject->vm());
144
145 SparseArrayValueMap* map = arrayStorage()->m_sparseMap.get();
146 ASSERT(map);
147 map->setLengthIsReadOnly();
148}
149
150// Defined in ES5.1 15.4.5.1
151bool JSArray::defineOwnProperty(JSObject* object, JSGlobalObject* globalObject, PropertyName propertyName, const PropertyDescriptor& descriptor, bool throwException)
152{
153 VM& vm = globalObject->vm();
154 auto scope = DECLARE_THROW_SCOPE(vm);
155
156 JSArray* array = jsCast<JSArray*>(object);
157
158 // 3. If P is "length", then
159 if (propertyName == vm.propertyNames->length) {
160 // All paths through length definition call the default [[DefineOwnProperty]], hence:
161 // from ES5.1 8.12.9 7.a.
162 if (descriptor.configurablePresent() && descriptor.configurable())
163 return typeError(globalObject, scope, throwException, UnconfigurablePropertyChangeConfigurabilityError);
164 // from ES5.1 8.12.9 7.b.
165 if (descriptor.enumerablePresent() && descriptor.enumerable())
166 return typeError(globalObject, scope, throwException, UnconfigurablePropertyChangeEnumerabilityError);
167
168 // a. If the [[Value]] field of Desc is absent, then
169 // a.i. Return the result of calling the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length", Desc, and Throw as arguments.
170 if (descriptor.isAccessorDescriptor())
171 return typeError(globalObject, scope, throwException, UnconfigurablePropertyChangeAccessMechanismError);
172 // from ES5.1 8.12.9 10.a.
173 if (!array->isLengthWritable() && descriptor.writablePresent() && descriptor.writable())
174 return typeError(globalObject, scope, throwException, UnconfigurablePropertyChangeWritabilityError);
175 // This descriptor is either just making length read-only, or changing nothing!
176 if (!descriptor.value()) {
177 if (descriptor.writablePresent())
178 array->setLengthWritable(globalObject, descriptor.writable());
179 return true;
180 }
181
182 // b. Let newLenDesc be a copy of Desc.
183 // c. Let newLen be ToUint32(Desc.[[Value]]).
184 unsigned newLen = descriptor.value().toUInt32(globalObject);
185 RETURN_IF_EXCEPTION(scope, false);
186 // d. If newLen is not equal to ToNumber( Desc.[[Value]]), throw a RangeError exception.
187 double valueAsNumber = descriptor.value().toNumber(globalObject);
188 RETURN_IF_EXCEPTION(scope, false);
189 if (newLen != valueAsNumber) {
190 JSC::throwException(globalObject, scope, createRangeError(globalObject, "Invalid array length"_s));
191 return false;
192 }
193
194 // Based on SameValue check in 8.12.9, this is always okay.
195 // FIXME: Nothing prevents this from being called on a RuntimeArray, and the length function will always return 0 in that case.
196 if (newLen == array->length()) {
197 if (descriptor.writablePresent())
198 array->setLengthWritable(globalObject, descriptor.writable());
199 return true;
200 }
201
202 // e. Set newLenDesc.[[Value] to newLen.
203 // f. If newLen >= oldLen, then
204 // f.i. Return the result of calling the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length", newLenDesc, and Throw as arguments.
205 // g. Reject if oldLenDesc.[[Writable]] is false.
206 if (!array->isLengthWritable())
207 return typeError(globalObject, scope, throwException, ReadonlyPropertyChangeError);
208
209 // h. If newLenDesc.[[Writable]] is absent or has the value true, let newWritable be true.
210 // i. Else,
211 // i.i. Need to defer setting the [[Writable]] attribute to false in case any elements cannot be deleted.
212 // i.ii. Let newWritable be false.
213 // i.iii. Set newLenDesc.[[Writable] to true.
214 // j. Let succeeded be the result of calling the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length", newLenDesc, and Throw as arguments.
215 // k. If succeeded is false, return false.
216 // l. While newLen < oldLen repeat,
217 // l.i. Set oldLen to oldLen – 1.
218 // l.ii. Let deleteSucceeded be the result of calling the [[Delete]] internal method of A passing ToString(oldLen) and false as arguments.
219 // l.iii. If deleteSucceeded is false, then
220 bool success = array->setLength(globalObject, newLen, throwException);
221 EXCEPTION_ASSERT(!scope.exception() || !success);
222 if (!success) {
223 // 1. Set newLenDesc.[[Value] to oldLen+1.
224 // 2. If newWritable is false, set newLenDesc.[[Writable] to false.
225 // 3. Call the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length", newLenDesc, and false as arguments.
226 // 4. Reject.
227 if (descriptor.writablePresent())
228 array->setLengthWritable(globalObject, descriptor.writable());
229 return false;
230 }
231
232 // m. If newWritable is false, then
233 // i. Call the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length",
234 // Property Descriptor{[[Writable]]: false}, and false as arguments. This call will always
235 // return true.
236 if (descriptor.writablePresent())
237 array->setLengthWritable(globalObject, descriptor.writable());
238 // n. Return true.
239 return true;
240 }
241
242 // 4. Else if P is an array index (15.4), then
243 // a. Let index be ToUint32(P).
244 if (Optional<uint32_t> optionalIndex = parseIndex(propertyName)) {
245 // b. Reject if index >= oldLen and oldLenDesc.[[Writable]] is false.
246 uint32_t index = optionalIndex.value();
247 // FIXME: Nothing prevents this from being called on a RuntimeArray, and the length function will always return 0 in that case.
248 if (index >= array->length() && !array->isLengthWritable())
249 return typeError(globalObject, scope, throwException, "Attempting to define numeric property on array with non-writable length property."_s);
250 // c. Let succeeded be the result of calling the default [[DefineOwnProperty]] internal method (8.12.9) on A passing P, Desc, and false as arguments.
251 // d. Reject if succeeded is false.
252 // e. If index >= oldLen
253 // e.i. Set oldLenDesc.[[Value]] to index + 1.
254 // e.ii. Call the default [[DefineOwnProperty]] internal method (8.12.9) on A passing "length", oldLenDesc, and false as arguments. This call will always return true.
255 // f. Return true.
256 RELEASE_AND_RETURN(scope, array->defineOwnIndexedProperty(globalObject, index, descriptor, throwException));
257 }
258
259 RELEASE_AND_RETURN(scope, array->JSObject::defineOwnNonIndexProperty(globalObject, propertyName, descriptor, throwException));
260}
261
262bool JSArray::getOwnPropertySlot(JSObject* object, JSGlobalObject* globalObject, PropertyName propertyName, PropertySlot& slot)
263{
264 VM& vm = globalObject->vm();
265 JSArray* thisObject = jsCast<JSArray*>(object);
266 if (propertyName == vm.propertyNames->length) {
267 unsigned attributes = thisObject->isLengthWritable() ? PropertyAttribute::DontDelete | PropertyAttribute::DontEnum : PropertyAttribute::DontDelete | PropertyAttribute::DontEnum | PropertyAttribute::ReadOnly;
268 slot.setValue(thisObject, attributes, jsNumber(thisObject->length()));
269 return true;
270 }
271
272 return JSObject::getOwnPropertySlot(thisObject, globalObject, propertyName, slot);
273}
274
275// ECMA 15.4.5.1
276bool JSArray::put(JSCell* cell, JSGlobalObject* globalObject, PropertyName propertyName, JSValue value, PutPropertySlot& slot)
277{
278 VM& vm = globalObject->vm();
279 auto scope = DECLARE_THROW_SCOPE(vm);
280
281 JSArray* thisObject = jsCast<JSArray*>(cell);
282
283 if (UNLIKELY(isThisValueAltered(slot, thisObject)))
284 RELEASE_AND_RETURN(scope, ordinarySetSlow(globalObject, thisObject, propertyName, value, slot.thisValue(), slot.isStrictMode()));
285
286 thisObject->ensureWritable(vm);
287
288 if (propertyName == vm.propertyNames->length) {
289 if (!thisObject->isLengthWritable()) {
290 if (slot.isStrictMode())
291 throwTypeError(globalObject, scope, "Array length is not writable"_s);
292 return false;
293 }
294
295 unsigned newLength = value.toUInt32(globalObject);
296 RETURN_IF_EXCEPTION(scope, false);
297 double valueAsNumber = value.toNumber(globalObject);
298 RETURN_IF_EXCEPTION(scope, false);
299 if (valueAsNumber != static_cast<double>(newLength)) {
300 throwException(globalObject, scope, createRangeError(globalObject, "Invalid array length"_s));
301 return false;
302 }
303 RELEASE_AND_RETURN(scope, thisObject->setLength(globalObject, newLength, slot.isStrictMode()));
304 }
305
306 RELEASE_AND_RETURN(scope, JSObject::put(thisObject, globalObject, propertyName, value, slot));
307}
308
309bool JSArray::deleteProperty(JSCell* cell, JSGlobalObject* globalObject, PropertyName propertyName)
310{
311 VM& vm = globalObject->vm();
312 JSArray* thisObject = jsCast<JSArray*>(cell);
313
314 if (propertyName == vm.propertyNames->length)
315 return false;
316
317 return JSObject::deleteProperty(thisObject, globalObject, propertyName);
318}
319
320static int compareKeysForQSort(const void* a, const void* b)
321{
322 unsigned da = *static_cast<const unsigned*>(a);
323 unsigned db = *static_cast<const unsigned*>(b);
324 return (da > db) - (da < db);
325}
326
327void JSArray::getOwnNonIndexPropertyNames(JSObject* object, JSGlobalObject* globalObject, PropertyNameArray& propertyNames, EnumerationMode mode)
328{
329 VM& vm = globalObject->vm();
330 JSArray* thisObject = jsCast<JSArray*>(object);
331
332 if (mode.includeDontEnumProperties())
333 propertyNames.add(vm.propertyNames->length);
334
335 JSObject::getOwnNonIndexPropertyNames(thisObject, globalObject, propertyNames, mode);
336}
337
338// This method makes room in the vector, but leaves the new space for count slots uncleared.
339bool JSArray::unshiftCountSlowCase(const AbstractLocker&, VM& vm, DeferGC&, bool addToFront, unsigned count)
340{
341 ASSERT(cellLock().isLocked());
342
343 ArrayStorage* storage = ensureArrayStorage(vm);
344 Butterfly* butterfly = storage->butterfly();
345 Structure* structure = this->structure(vm);
346 unsigned propertyCapacity = structure->outOfLineCapacity();
347 unsigned propertySize = structure->outOfLineSize();
348
349 // If not, we should have handled this on the fast path.
350 ASSERT(!addToFront || count > storage->m_indexBias);
351
352 // Step 1:
353 // Gather 4 key metrics:
354 // * usedVectorLength - how many entries are currently in the vector (conservative estimate - fewer may be in use in sparse vectors).
355 // * requiredVectorLength - how many entries are will there be in the vector, after allocating space for 'count' more.
356 // * currentCapacity - what is the current size of the vector, including any pre-capacity.
357 // * desiredCapacity - how large should we like to grow the vector to - based on 2x requiredVectorLength.
358
359 unsigned length = storage->length();
360 unsigned oldVectorLength = storage->vectorLength();
361 unsigned usedVectorLength = std::min(oldVectorLength, length);
362 ASSERT(usedVectorLength <= MAX_STORAGE_VECTOR_LENGTH);
363 // Check that required vector length is possible, in an overflow-safe fashion.
364 if (count > MAX_STORAGE_VECTOR_LENGTH - usedVectorLength)
365 return false;
366 unsigned requiredVectorLength = usedVectorLength + count;
367 ASSERT(requiredVectorLength <= MAX_STORAGE_VECTOR_LENGTH);
368 // The sum of m_vectorLength and m_indexBias will never exceed MAX_STORAGE_VECTOR_LENGTH.
369 ASSERT(storage->vectorLength() <= MAX_STORAGE_VECTOR_LENGTH && (MAX_STORAGE_VECTOR_LENGTH - storage->vectorLength()) >= storage->m_indexBias);
370 unsigned currentCapacity = storage->vectorLength() + storage->m_indexBias;
371 // The calculation of desiredCapacity won't overflow, due to the range of MAX_STORAGE_VECTOR_LENGTH.
372 // FIXME: This code should be fixed to avoid internal fragmentation. It's not super high
373 // priority since increaseVectorLength() will "fix" any mistakes we make, but it would be cool
374 // to get this right eventually.
375 unsigned desiredCapacity = std::min(MAX_STORAGE_VECTOR_LENGTH, std::max(BASE_ARRAY_STORAGE_VECTOR_LEN, requiredVectorLength) << 1);
376
377 // Step 2:
378 // We're either going to choose to allocate a new ArrayStorage, or we're going to reuse the existing one.
379
380 void* newAllocBase = nullptr;
381 unsigned newStorageCapacity;
382 bool allocatedNewStorage;
383 // If the current storage array is sufficiently large (but not too large!) then just keep using it.
384 if (currentCapacity > desiredCapacity && isDenseEnoughForVector(currentCapacity, requiredVectorLength)) {
385 newAllocBase = butterfly->base(structure);
386 newStorageCapacity = currentCapacity;
387 allocatedNewStorage = false;
388 } else {
389 const unsigned preCapacity = 0;
390 Butterfly* newButterfly = Butterfly::tryCreateUninitialized(vm, this, preCapacity, propertyCapacity, true, ArrayStorage::sizeFor(desiredCapacity));
391 if (!newButterfly)
392 return false;
393 newAllocBase = newButterfly->base(preCapacity, propertyCapacity);
394 newStorageCapacity = desiredCapacity;
395 allocatedNewStorage = true;
396 }
397
398 // Step 3:
399 // Work out where we're going to move things to.
400
401 // Determine how much of the vector to use as pre-capacity, and how much as post-capacity.
402 // If we're adding to the end, we'll add all the new space to the end.
403 // If the vector had no free post-capacity (length >= m_vectorLength), don't give it any.
404 // If it did, we calculate the amount that will remain based on an atomic decay - leave the
405 // vector with half the post-capacity it had previously.
406 unsigned postCapacity = 0;
407 if (!addToFront)
408 postCapacity = newStorageCapacity - requiredVectorLength;
409 else if (length < storage->vectorLength()) {
410 // Atomic decay, + the post-capacity cannot be greater than what is available.
411 postCapacity = std::min((storage->vectorLength() - length) >> 1, newStorageCapacity - requiredVectorLength);
412 // If we're moving contents within the same allocation, the post-capacity is being reduced.
413 ASSERT(newAllocBase != butterfly->base(structure) || postCapacity < storage->vectorLength() - length);
414 }
415
416 unsigned newVectorLength = requiredVectorLength + postCapacity;
417 RELEASE_ASSERT(newVectorLength <= MAX_STORAGE_VECTOR_LENGTH);
418 unsigned preCapacity = newStorageCapacity - newVectorLength;
419
420 Butterfly* newButterfly = Butterfly::fromBase(newAllocBase, preCapacity, propertyCapacity);
421
422 if (addToFront) {
423 ASSERT(count + usedVectorLength <= newVectorLength);
424 gcSafeMemmove(newButterfly->arrayStorage()->m_vector + count, storage->m_vector, sizeof(JSValue) * usedVectorLength);
425 gcSafeMemmove(newButterfly->propertyStorage() - propertySize, butterfly->propertyStorage() - propertySize, sizeof(JSValue) * propertySize + sizeof(IndexingHeader) + ArrayStorage::sizeFor(0));
426
427 // We don't need to zero the pre-capacity for the concurrent GC because it is not available to use as property storage.
428 gcSafeZeroMemory(static_cast<JSValue*>(newButterfly->base(0, propertyCapacity)), (propertyCapacity - propertySize) * sizeof(JSValue));
429
430 if (allocatedNewStorage) {
431 // We will set the vectorLength to newVectorLength. We populated requiredVectorLength
432 // (usedVectorLength + count), which is less. Clear the difference.
433 for (unsigned i = requiredVectorLength; i < newVectorLength; ++i)
434 newButterfly->arrayStorage()->m_vector[i].clear();
435 }
436 } else if ((newAllocBase != butterfly->base(structure)) || (preCapacity != storage->m_indexBias)) {
437 gcSafeMemmove(newButterfly->propertyStorage() - propertyCapacity, butterfly->propertyStorage() - propertyCapacity, sizeof(JSValue) * propertyCapacity + sizeof(IndexingHeader) + ArrayStorage::sizeFor(0));
438 gcSafeMemmove(newButterfly->arrayStorage()->m_vector, storage->m_vector, sizeof(JSValue) * usedVectorLength);
439
440 for (unsigned i = requiredVectorLength; i < newVectorLength; i++)
441 newButterfly->arrayStorage()->m_vector[i].clear();
442 }
443
444 newButterfly->arrayStorage()->setVectorLength(newVectorLength);
445 newButterfly->arrayStorage()->m_indexBias = preCapacity;
446
447 setButterfly(vm, newButterfly);
448
449 return true;
450}
451
452bool JSArray::setLengthWithArrayStorage(JSGlobalObject* globalObject, unsigned newLength, bool throwException, ArrayStorage* storage)
453{
454 VM& vm = globalObject->vm();
455 auto scope = DECLARE_THROW_SCOPE(vm);
456
457 unsigned length = storage->length();
458
459 // If the length is read only then we enter sparse mode, so should enter the following 'if'.
460 ASSERT(isLengthWritable() || storage->m_sparseMap);
461
462 if (SparseArrayValueMap* map = storage->m_sparseMap.get()) {
463 // Fail if the length is not writable.
464 if (map->lengthIsReadOnly())
465 return typeError(globalObject, scope, throwException, ReadonlyPropertyWriteError);
466
467 if (newLength < length) {
468 // Copy any keys we might be interested in into a vector.
469 Vector<unsigned, 0, UnsafeVectorOverflow> keys;
470 keys.reserveInitialCapacity(std::min(map->size(), static_cast<size_t>(length - newLength)));
471 SparseArrayValueMap::const_iterator end = map->end();
472 for (SparseArrayValueMap::const_iterator it = map->begin(); it != end; ++it) {
473 unsigned index = static_cast<unsigned>(it->key);
474 if (index < length && index >= newLength)
475 keys.append(index);
476 }
477
478 // Check if the array is in sparse mode. If so there may be non-configurable
479 // properties, so we have to perform deletion with caution, if not we can
480 // delete values in any order.
481 if (map->sparseMode()) {
482 qsort(keys.begin(), keys.size(), sizeof(unsigned), compareKeysForQSort);
483 unsigned i = keys.size();
484 while (i) {
485 unsigned index = keys[--i];
486 SparseArrayValueMap::iterator it = map->find(index);
487 ASSERT(it != map->notFound());
488 if (it->value.attributes() & PropertyAttribute::DontDelete) {
489 storage->setLength(index + 1);
490 return typeError(globalObject, scope, throwException, UnableToDeletePropertyError);
491 }
492 map->remove(it);
493 }
494 } else {
495 for (unsigned i = 0; i < keys.size(); ++i)
496 map->remove(keys[i]);
497 if (map->isEmpty())
498 deallocateSparseIndexMap();
499 }
500 }
501 }
502
503 if (newLength < length) {
504 // Delete properties from the vector.
505 unsigned usedVectorLength = std::min(length, storage->vectorLength());
506 for (unsigned i = newLength; i < usedVectorLength; ++i) {
507 WriteBarrier<Unknown>& valueSlot = storage->m_vector[i];
508 bool hadValue = !!valueSlot;
509 valueSlot.clear();
510 storage->m_numValuesInVector -= hadValue;
511 }
512 }
513
514 storage->setLength(newLength);
515
516 return true;
517}
518
519bool JSArray::appendMemcpy(JSGlobalObject* globalObject, VM& vm, unsigned startIndex, JSC::JSArray* otherArray)
520{
521 auto scope = DECLARE_THROW_SCOPE(vm);
522
523 if (!canFastCopy(vm, otherArray))
524 return false;
525
526 IndexingType type = indexingType();
527 IndexingType otherType = otherArray->indexingType();
528 IndexingType copyType = mergeIndexingTypeForCopying(otherType);
529 if (type == ArrayWithUndecided && copyType != NonArray) {
530 if (copyType == ArrayWithInt32)
531 convertUndecidedToInt32(vm);
532 else if (copyType == ArrayWithDouble)
533 convertUndecidedToDouble(vm);
534 else if (copyType == ArrayWithContiguous)
535 convertUndecidedToContiguous(vm);
536 else {
537 ASSERT(copyType == ArrayWithUndecided);
538 return true;
539 }
540 } else if (type != copyType)
541 return false;
542
543 unsigned otherLength = otherArray->length();
544 Checked<unsigned, RecordOverflow> checkedNewLength = startIndex;
545 checkedNewLength += otherLength;
546
547 unsigned newLength;
548 if (checkedNewLength.safeGet(newLength) == CheckedState::DidOverflow) {
549 throwException(globalObject, scope, createRangeError(globalObject, LengthExceededTheMaximumArrayLengthError));
550 return false;
551 }
552
553 if (newLength >= MIN_SPARSE_ARRAY_INDEX)
554 return false;
555
556 if (!ensureLength(vm, newLength)) {
557 throwOutOfMemoryError(globalObject, scope);
558 return false;
559 }
560 ASSERT(copyType == indexingType());
561
562 if (UNLIKELY(otherType == ArrayWithUndecided)) {
563 auto* butterfly = this->butterfly();
564 if (type == ArrayWithDouble) {
565 for (unsigned i = startIndex; i < newLength; ++i)
566 butterfly->contiguousDouble().at(this, i) = PNaN;
567 } else {
568 for (unsigned i = startIndex; i < newLength; ++i)
569 butterfly->contiguousInt32().at(this, i).setWithoutWriteBarrier(JSValue());
570 }
571 } else if (type == ArrayWithDouble)
572 gcSafeMemcpy(butterfly()->contiguousDouble().data() + startIndex, otherArray->butterfly()->contiguousDouble().data(), sizeof(JSValue) * otherLength);
573 else {
574 gcSafeMemcpy(butterfly()->contiguous().data() + startIndex, otherArray->butterfly()->contiguous().data(), sizeof(JSValue) * otherLength);
575 vm.heap.writeBarrier(this);
576 }
577
578 return true;
579}
580
581bool JSArray::setLength(JSGlobalObject* globalObject, unsigned newLength, bool throwException)
582{
583 VM& vm = globalObject->vm();
584 auto scope = DECLARE_THROW_SCOPE(vm);
585
586 Butterfly* butterfly = this->butterfly();
587 switch (indexingMode()) {
588 case ArrayClass:
589 if (!newLength)
590 return true;
591 if (newLength >= MIN_SPARSE_ARRAY_INDEX) {
592 RELEASE_AND_RETURN(scope, setLengthWithArrayStorage(
593 globalObject, newLength, throwException,
594 ensureArrayStorage(vm)));
595 }
596 createInitialUndecided(vm, newLength);
597 return true;
598
599 case CopyOnWriteArrayWithInt32:
600 case CopyOnWriteArrayWithDouble:
601 case CopyOnWriteArrayWithContiguous:
602 if (newLength == butterfly->publicLength())
603 return true;
604 convertFromCopyOnWrite(vm);
605 butterfly = this->butterfly();
606 FALLTHROUGH;
607
608 case ArrayWithUndecided:
609 case ArrayWithInt32:
610 case ArrayWithDouble:
611 case ArrayWithContiguous: {
612 if (newLength == butterfly->publicLength())
613 return true;
614 if (newLength > MAX_STORAGE_VECTOR_LENGTH // This check ensures that we can do fast push.
615 || (newLength >= MIN_SPARSE_ARRAY_INDEX
616 && !isDenseEnoughForVector(newLength, countElements()))) {
617 RELEASE_AND_RETURN(scope, setLengthWithArrayStorage(
618 globalObject, newLength, throwException,
619 ensureArrayStorage(vm)));
620 }
621 if (newLength > butterfly->publicLength()) {
622 if (!ensureLength(vm, newLength)) {
623 throwOutOfMemoryError(globalObject, scope);
624 return false;
625 }
626 return true;
627 }
628
629 unsigned lengthToClear = butterfly->publicLength() - newLength;
630 unsigned costToAllocateNewButterfly = 64; // a heuristic.
631 if (lengthToClear > newLength && lengthToClear > costToAllocateNewButterfly) {
632 reallocateAndShrinkButterfly(vm, newLength);
633 return true;
634 }
635
636 if (indexingType() == ArrayWithDouble) {
637 for (unsigned i = butterfly->publicLength(); i-- > newLength;)
638 butterfly->contiguousDouble().at(this, i) = PNaN;
639 } else {
640 for (unsigned i = butterfly->publicLength(); i-- > newLength;)
641 butterfly->contiguous().at(this, i).clear();
642 }
643 butterfly->setPublicLength(newLength);
644 return true;
645 }
646
647 case ArrayWithArrayStorage:
648 case ArrayWithSlowPutArrayStorage:
649 RELEASE_AND_RETURN(scope, setLengthWithArrayStorage(globalObject, newLength, throwException, arrayStorage()));
650
651 default:
652 CRASH();
653 return false;
654 }
655}
656
657JSValue JSArray::pop(JSGlobalObject* globalObject)
658{
659 VM& vm = globalObject->vm();
660 auto scope = DECLARE_THROW_SCOPE(vm);
661
662 ensureWritable(vm);
663
664 Butterfly* butterfly = this->butterfly();
665
666 switch (indexingType()) {
667 case ArrayClass:
668 return jsUndefined();
669
670 case ArrayWithUndecided:
671 if (!butterfly->publicLength())
672 return jsUndefined();
673 // We have nothing but holes. So, drop down to the slow version.
674 break;
675
676 case ArrayWithInt32:
677 case ArrayWithContiguous: {
678 unsigned length = butterfly->publicLength();
679
680 if (!length--)
681 return jsUndefined();
682
683 RELEASE_ASSERT(length < butterfly->vectorLength());
684 JSValue value = butterfly->contiguous().at(this, length).get();
685 if (value) {
686 butterfly->contiguous().at(this, length).clear();
687 butterfly->setPublicLength(length);
688 return value;
689 }
690 break;
691 }
692
693 case ArrayWithDouble: {
694 unsigned length = butterfly->publicLength();
695
696 if (!length--)
697 return jsUndefined();
698
699 RELEASE_ASSERT(length < butterfly->vectorLength());
700 double value = butterfly->contiguousDouble().at(this, length);
701 if (value == value) {
702 butterfly->contiguousDouble().at(this, length) = PNaN;
703 butterfly->setPublicLength(length);
704 return JSValue(JSValue::EncodeAsDouble, value);
705 }
706 break;
707 }
708
709 case ARRAY_WITH_ARRAY_STORAGE_INDEXING_TYPES: {
710 ArrayStorage* storage = butterfly->arrayStorage();
711
712 unsigned length = storage->length();
713 if (!length) {
714 if (!isLengthWritable())
715 throwTypeError(globalObject, scope, ReadonlyPropertyWriteError);
716 return jsUndefined();
717 }
718
719 unsigned index = length - 1;
720 if (index < storage->vectorLength()) {
721 WriteBarrier<Unknown>& valueSlot = storage->m_vector[index];
722 if (valueSlot) {
723 --storage->m_numValuesInVector;
724 JSValue element = valueSlot.get();
725 valueSlot.clear();
726
727 RELEASE_ASSERT(isLengthWritable());
728 storage->setLength(index);
729 return element;
730 }
731 }
732 break;
733 }
734
735 default:
736 CRASH();
737 return JSValue();
738 }
739
740 unsigned index = getArrayLength() - 1;
741 // Let element be the result of calling the [[Get]] internal method of O with argument indx.
742 JSValue element = get(globalObject, index);
743 RETURN_IF_EXCEPTION(scope, JSValue());
744 // Call the [[Delete]] internal method of O with arguments indx and true.
745 bool success = deletePropertyByIndex(this, globalObject, index);
746 RETURN_IF_EXCEPTION(scope, JSValue());
747 if (!success) {
748 throwTypeError(globalObject, scope, UnableToDeletePropertyError);
749 return jsUndefined();
750 }
751 // Call the [[Put]] internal method of O with arguments "length", indx, and true.
752 scope.release();
753 setLength(globalObject, index, true);
754 // Return element.
755 return element;
756}
757
758// Push & putIndex are almost identical, with two small differences.
759// - we always are writing beyond the current array bounds, so it is always necessary to update m_length & m_numValuesInVector.
760// - pushing to an array of length 2^32-1 stores the property, but throws a range error.
761NEVER_INLINE void JSArray::push(JSGlobalObject* globalObject, JSValue value)
762{
763 pushInline(globalObject, value);
764}
765
766JSArray* JSArray::fastSlice(JSGlobalObject* globalObject, unsigned startIndex, unsigned count)
767{
768 VM& vm = globalObject->vm();
769
770 ensureWritable(vm);
771
772 auto arrayType = indexingMode();
773 switch (arrayType) {
774 case ArrayWithDouble:
775 case ArrayWithInt32:
776 case ArrayWithContiguous: {
777 if (count >= MIN_SPARSE_ARRAY_INDEX || structure(vm)->holesMustForwardToPrototype(vm, this))
778 return nullptr;
779
780 Structure* resultStructure = globalObject->arrayStructureForIndexingTypeDuringAllocation(arrayType);
781 if (UNLIKELY(hasAnyArrayStorage(resultStructure->indexingType())))
782 return nullptr;
783
784 ASSERT(!globalObject->isHavingABadTime());
785 ObjectInitializationScope scope(vm);
786 JSArray* resultArray = JSArray::tryCreateUninitializedRestricted(scope, resultStructure, count);
787 if (UNLIKELY(!resultArray))
788 return nullptr;
789
790 auto& resultButterfly = *resultArray->butterfly();
791 if (arrayType == ArrayWithDouble)
792 gcSafeMemcpy(resultButterfly.contiguousDouble().data(), butterfly()->contiguousDouble().data() + startIndex, sizeof(JSValue) * count);
793 else
794 gcSafeMemcpy(resultButterfly.contiguous().data(), butterfly()->contiguous().data() + startIndex, sizeof(JSValue) * count);
795
796 ASSERT(resultButterfly.publicLength() == count);
797 return resultArray;
798 }
799 default:
800 return nullptr;
801 }
802}
803
804bool JSArray::shiftCountWithArrayStorage(VM& vm, unsigned startIndex, unsigned count, ArrayStorage* storage)
805{
806 unsigned oldLength = storage->length();
807 RELEASE_ASSERT(count <= oldLength);
808
809 // If the array contains holes or is otherwise in an abnormal state,
810 // use the generic algorithm in ArrayPrototype.
811 if (storage->hasHoles()
812 || hasSparseMap()
813 || shouldUseSlowPut(indexingType())) {
814 return false;
815 }
816
817 if (!oldLength)
818 return true;
819
820 unsigned length = oldLength - count;
821
822 storage->m_numValuesInVector -= count;
823 storage->setLength(length);
824
825 unsigned vectorLength = storage->vectorLength();
826 if (!vectorLength)
827 return true;
828
829 if (startIndex >= vectorLength)
830 return true;
831
832 DisallowGC disallowGC;
833 auto locker = holdLock(cellLock());
834
835 if (startIndex + count > vectorLength)
836 count = vectorLength - startIndex;
837
838 unsigned usedVectorLength = std::min(vectorLength, oldLength);
839
840 unsigned numElementsBeforeShiftRegion = startIndex;
841 unsigned firstIndexAfterShiftRegion = startIndex + count;
842 unsigned numElementsAfterShiftRegion = usedVectorLength - firstIndexAfterShiftRegion;
843 ASSERT(numElementsBeforeShiftRegion + count + numElementsAfterShiftRegion == usedVectorLength);
844
845 // The point of this comparison seems to be to minimize the amount of elements that have to
846 // be moved during a shift operation.
847 if (numElementsBeforeShiftRegion < numElementsAfterShiftRegion) {
848 // The number of elements before the shift region is less than the number of elements
849 // after the shift region, so we move the elements before to the right.
850 if (numElementsBeforeShiftRegion) {
851 RELEASE_ASSERT(count + startIndex <= vectorLength);
852 gcSafeMemmove(storage->m_vector + count,
853 storage->m_vector,
854 sizeof(JSValue) * startIndex);
855 }
856 // Adjust the Butterfly and the index bias. We only need to do this here because we're changing
857 // the start of the Butterfly, which needs to point at the first indexed property in the used
858 // portion of the vector.
859 Butterfly* butterfly = this->butterfly()->shift(structure(vm), count);
860 storage = butterfly->arrayStorage();
861 storage->m_indexBias += count;
862
863 // Since we're consuming part of the vector by moving its beginning to the left,
864 // we need to modify the vector length appropriately.
865 storage->setVectorLength(vectorLength - count);
866 setButterfly(vm, butterfly);
867 } else {
868 // The number of elements before the shift region is greater than or equal to the number
869 // of elements after the shift region, so we move the elements after the shift region to the left.
870 gcSafeMemmove(storage->m_vector + startIndex,
871 storage->m_vector + firstIndexAfterShiftRegion,
872 sizeof(JSValue) * numElementsAfterShiftRegion);
873
874 // Clear the slots of the elements we just moved.
875 unsigned startOfEmptyVectorTail = usedVectorLength - count;
876 for (unsigned i = startOfEmptyVectorTail; i < usedVectorLength; ++i)
877 storage->m_vector[i].clear();
878 // We don't modify the index bias or the Butterfly pointer in this case because we're not changing
879 // the start of the Butterfly, which needs to point at the first indexed property in the used
880 // portion of the vector. We also don't modify the vector length because we're not actually changing
881 // its length; we're just using less of it.
882 }
883
884 return true;
885}
886
887bool JSArray::shiftCountWithAnyIndexingType(JSGlobalObject* globalObject, unsigned& startIndex, unsigned count)
888{
889 VM& vm = globalObject->vm();
890 RELEASE_ASSERT(count > 0);
891
892 ensureWritable(vm);
893
894 Butterfly* butterfly = this->butterfly();
895
896 auto indexingType = this->indexingType();
897 switch (indexingType) {
898 case ArrayClass:
899 return true;
900
901 case ArrayWithUndecided:
902 // Don't handle this because it's confusing and it shouldn't come up.
903 return false;
904
905 case ArrayWithInt32:
906 case ArrayWithContiguous: {
907 unsigned oldLength = butterfly->publicLength();
908 RELEASE_ASSERT(count <= oldLength);
909
910 // We may have to walk the entire array to do the shift. We're willing to do
911 // so only if it's not horribly slow.
912 if (oldLength - (startIndex + count) >= MIN_SPARSE_ARRAY_INDEX)
913 return shiftCountWithArrayStorage(vm, startIndex, count, ensureArrayStorage(vm));
914
915 // Storing to a hole is fine since we're still having a good time. But reading from a hole
916 // is totally not fine, since we might have to read from the proto chain.
917 // We have to check for holes before we start moving things around so that we don't get halfway
918 // through shifting and then realize we should have been in ArrayStorage mode.
919 unsigned end = oldLength - count;
920 if (this->structure(vm)->holesMustForwardToPrototype(vm, this)) {
921 for (unsigned i = startIndex; i < end; ++i) {
922 JSValue v = butterfly->contiguous().at(this, i + count).get();
923 if (UNLIKELY(!v)) {
924 startIndex = i;
925 return shiftCountWithArrayStorage(vm, startIndex, count, ensureArrayStorage(vm));
926 }
927 butterfly->contiguous().at(this, i).setWithoutWriteBarrier(v);
928 }
929 } else {
930 gcSafeMemmove(butterfly->contiguous().data() + startIndex,
931 butterfly->contiguous().data() + startIndex + count,
932 sizeof(JSValue) * (end - startIndex));
933 }
934
935 for (unsigned i = end; i < oldLength; ++i)
936 butterfly->contiguous().at(this, i).clear();
937
938 butterfly->setPublicLength(oldLength - count);
939
940 // Our memmoving of values around in the array could have concealed some of them from
941 // the collector. Let's make sure that the collector scans this object again.
942 if (indexingType == ArrayWithContiguous)
943 vm.heap.writeBarrier(this);
944
945 return true;
946 }
947
948 case ArrayWithDouble: {
949 unsigned oldLength = butterfly->publicLength();
950 RELEASE_ASSERT(count <= oldLength);
951
952 // We may have to walk the entire array to do the shift. We're willing to do
953 // so only if it's not horribly slow.
954 if (oldLength - (startIndex + count) >= MIN_SPARSE_ARRAY_INDEX)
955 return shiftCountWithArrayStorage(vm, startIndex, count, ensureArrayStorage(vm));
956
957 // Storing to a hole is fine since we're still having a good time. But reading from a hole
958 // is totally not fine, since we might have to read from the proto chain.
959 // We have to check for holes before we start moving things around so that we don't get halfway
960 // through shifting and then realize we should have been in ArrayStorage mode.
961 unsigned end = oldLength - count;
962 if (this->structure(vm)->holesMustForwardToPrototype(vm, this)) {
963 for (unsigned i = startIndex; i < end; ++i) {
964 double v = butterfly->contiguousDouble().at(this, i + count);
965 if (UNLIKELY(v != v)) {
966 startIndex = i;
967 return shiftCountWithArrayStorage(vm, startIndex, count, ensureArrayStorage(vm));
968 }
969 butterfly->contiguousDouble().at(this, i) = v;
970 }
971 } else {
972 gcSafeMemmove(butterfly->contiguousDouble().data() + startIndex,
973 butterfly->contiguousDouble().data() + startIndex + count,
974 sizeof(JSValue) * (end - startIndex));
975 }
976 for (unsigned i = end; i < oldLength; ++i)
977 butterfly->contiguousDouble().at(this, i) = PNaN;
978
979 butterfly->setPublicLength(oldLength - count);
980 return true;
981 }
982
983 case ArrayWithArrayStorage:
984 case ArrayWithSlowPutArrayStorage:
985 return shiftCountWithArrayStorage(vm, startIndex, count, arrayStorage());
986
987 default:
988 CRASH();
989 return false;
990 }
991}
992
993// Returns true if the unshift can be handled, false to fallback.
994bool JSArray::unshiftCountWithArrayStorage(JSGlobalObject* globalObject, unsigned startIndex, unsigned count, ArrayStorage* storage)
995{
996 VM& vm = globalObject->vm();
997 auto scope = DECLARE_THROW_SCOPE(vm);
998
999 unsigned length = storage->length();
1000
1001 RELEASE_ASSERT(startIndex <= length);
1002
1003 // If the array contains holes or is otherwise in an abnormal state,
1004 // use the generic algorithm in ArrayPrototype.
1005 if (storage->hasHoles() || storage->inSparseMode() || shouldUseSlowPut(indexingType()))
1006 return false;
1007
1008 bool moveFront = !startIndex || startIndex < length / 2;
1009
1010 unsigned vectorLength = storage->vectorLength();
1011
1012 // Need to have GC deferred around the unshiftCountSlowCase(), since that leaves the butterfly in
1013 // a weird state: some parts of it will be left uninitialized, which we will fill in here.
1014 DeferGC deferGC(vm.heap);
1015 auto locker = holdLock(cellLock());
1016
1017 if (moveFront && storage->m_indexBias >= count) {
1018 Butterfly* newButterfly = storage->butterfly()->unshift(structure(vm), count);
1019 storage = newButterfly->arrayStorage();
1020 storage->m_indexBias -= count;
1021 storage->setVectorLength(vectorLength + count);
1022 setButterfly(vm, newButterfly);
1023 } else if (!moveFront && vectorLength - length >= count)
1024 storage = storage->butterfly()->arrayStorage();
1025 else if (unshiftCountSlowCase(locker, vm, deferGC, moveFront, count))
1026 storage = arrayStorage();
1027 else {
1028 throwOutOfMemoryError(globalObject, scope);
1029 return true;
1030 }
1031
1032 WriteBarrier<Unknown>* vector = storage->m_vector;
1033
1034 if (startIndex) {
1035 if (moveFront)
1036 gcSafeMemmove(vector, vector + count, startIndex * sizeof(JSValue));
1037 else if (length - startIndex)
1038 gcSafeMemmove(vector + startIndex + count, vector + startIndex, (length - startIndex) * sizeof(JSValue));
1039 }
1040
1041 for (unsigned i = 0; i < count; i++)
1042 vector[i + startIndex].clear();
1043
1044 return true;
1045}
1046
1047bool JSArray::unshiftCountWithAnyIndexingType(JSGlobalObject* globalObject, unsigned startIndex, unsigned count)
1048{
1049 VM& vm = globalObject->vm();
1050 auto scope = DECLARE_THROW_SCOPE(vm);
1051
1052 ensureWritable(vm);
1053
1054 Butterfly* butterfly = this->butterfly();
1055
1056 switch (indexingType()) {
1057 case ArrayClass:
1058 case ArrayWithUndecided:
1059 // We could handle this. But it shouldn't ever come up, so we won't.
1060 return false;
1061
1062 case ArrayWithInt32:
1063 case ArrayWithContiguous: {
1064 unsigned oldLength = butterfly->publicLength();
1065
1066 // We may have to walk the entire array to do the unshift. We're willing to do so
1067 // only if it's not horribly slow.
1068 if (oldLength - startIndex >= MIN_SPARSE_ARRAY_INDEX)
1069 RELEASE_AND_RETURN(scope, unshiftCountWithArrayStorage(globalObject, startIndex, count, ensureArrayStorage(vm)));
1070
1071 Checked<unsigned, RecordOverflow> checkedLength(oldLength);
1072 checkedLength += count;
1073 unsigned newLength;
1074 if (CheckedState::DidOverflow == checkedLength.safeGet(newLength)) {
1075 throwOutOfMemoryError(globalObject, scope);
1076 return true;
1077 }
1078 if (newLength > MAX_STORAGE_VECTOR_LENGTH)
1079 return false;
1080 if (!ensureLength(vm, newLength)) {
1081 throwOutOfMemoryError(globalObject, scope);
1082 return true;
1083 }
1084 butterfly = this->butterfly();
1085
1086 // We have to check for holes before we start moving things around so that we don't get halfway
1087 // through shifting and then realize we should have been in ArrayStorage mode.
1088 for (unsigned i = oldLength; i-- > startIndex;) {
1089 JSValue v = butterfly->contiguous().at(this, i).get();
1090 if (UNLIKELY(!v))
1091 RELEASE_AND_RETURN(scope, unshiftCountWithArrayStorage(globalObject, startIndex, count, ensureArrayStorage(vm)));
1092 }
1093
1094 for (unsigned i = oldLength; i-- > startIndex;) {
1095 JSValue v = butterfly->contiguous().at(this, i).get();
1096 ASSERT(v);
1097 butterfly->contiguous().at(this, i + count).setWithoutWriteBarrier(v);
1098 }
1099
1100 // Our memmoving of values around in the array could have concealed some of them from
1101 // the collector. Let's make sure that the collector scans this object again.
1102 vm.heap.writeBarrier(this);
1103
1104 // NOTE: we're leaving being garbage in the part of the array that we shifted out
1105 // of. This is fine because the caller is required to store over that area, and
1106 // in contiguous mode storing into a hole is guaranteed to behave exactly the same
1107 // as storing over an existing element.
1108
1109 return true;
1110 }
1111
1112 case ArrayWithDouble: {
1113 unsigned oldLength = butterfly->publicLength();
1114
1115 // We may have to walk the entire array to do the unshift. We're willing to do so
1116 // only if it's not horribly slow.
1117 if (oldLength - startIndex >= MIN_SPARSE_ARRAY_INDEX)
1118 RELEASE_AND_RETURN(scope, unshiftCountWithArrayStorage(globalObject, startIndex, count, ensureArrayStorage(vm)));
1119
1120 Checked<unsigned, RecordOverflow> checkedLength(oldLength);
1121 checkedLength += count;
1122 unsigned newLength;
1123 if (CheckedState::DidOverflow == checkedLength.safeGet(newLength)) {
1124 throwOutOfMemoryError(globalObject, scope);
1125 return true;
1126 }
1127 if (newLength > MAX_STORAGE_VECTOR_LENGTH)
1128 return false;
1129 if (!ensureLength(vm, newLength)) {
1130 throwOutOfMemoryError(globalObject, scope);
1131 return true;
1132 }
1133 butterfly = this->butterfly();
1134
1135 // We have to check for holes before we start moving things around so that we don't get halfway
1136 // through shifting and then realize we should have been in ArrayStorage mode.
1137 for (unsigned i = oldLength; i-- > startIndex;) {
1138 double v = butterfly->contiguousDouble().at(this, i);
1139 if (UNLIKELY(v != v))
1140 RELEASE_AND_RETURN(scope, unshiftCountWithArrayStorage(globalObject, startIndex, count, ensureArrayStorage(vm)));
1141 }
1142
1143 for (unsigned i = oldLength; i-- > startIndex;) {
1144 double v = butterfly->contiguousDouble().at(this, i);
1145 ASSERT(v == v);
1146 butterfly->contiguousDouble().at(this, i + count) = v;
1147 }
1148
1149 // NOTE: we're leaving being garbage in the part of the array that we shifted out
1150 // of. This is fine because the caller is required to store over that area, and
1151 // in contiguous mode storing into a hole is guaranteed to behave exactly the same
1152 // as storing over an existing element.
1153
1154 return true;
1155 }
1156
1157 case ArrayWithArrayStorage:
1158 case ArrayWithSlowPutArrayStorage:
1159 RELEASE_AND_RETURN(scope, unshiftCountWithArrayStorage(globalObject, startIndex, count, arrayStorage()));
1160
1161 default:
1162 CRASH();
1163 return false;
1164 }
1165}
1166
1167void JSArray::fillArgList(JSGlobalObject* globalObject, MarkedArgumentBuffer& args)
1168{
1169 unsigned i = 0;
1170 unsigned vectorEnd;
1171 WriteBarrier<Unknown>* vector;
1172
1173 Butterfly* butterfly = this->butterfly();
1174
1175 switch (indexingType()) {
1176 case ArrayClass:
1177 return;
1178
1179 case ArrayWithUndecided: {
1180 vector = 0;
1181 vectorEnd = 0;
1182 break;
1183 }
1184
1185 case ArrayWithInt32:
1186 case ArrayWithContiguous: {
1187 vectorEnd = butterfly->publicLength();
1188 vector = butterfly->contiguous().data();
1189 break;
1190 }
1191
1192 case ArrayWithDouble: {
1193 vector = 0;
1194 vectorEnd = 0;
1195 for (; i < butterfly->publicLength(); ++i) {
1196 double v = butterfly->contiguousDouble().at(this, i);
1197 if (v != v)
1198 break;
1199 args.append(JSValue(JSValue::EncodeAsDouble, v));
1200 }
1201 break;
1202 }
1203
1204 case ARRAY_WITH_ARRAY_STORAGE_INDEXING_TYPES: {
1205 ArrayStorage* storage = butterfly->arrayStorage();
1206
1207 vector = storage->m_vector;
1208 vectorEnd = std::min(storage->length(), storage->vectorLength());
1209 break;
1210 }
1211
1212 default:
1213 CRASH();
1214#if COMPILER_QUIRK(CONSIDERS_UNREACHABLE_CODE)
1215 vector = 0;
1216 vectorEnd = 0;
1217 break;
1218#endif
1219 }
1220
1221 for (; i < vectorEnd; ++i) {
1222 WriteBarrier<Unknown>& v = vector[i];
1223 if (!v)
1224 break;
1225 args.append(v.get());
1226 }
1227
1228 // FIXME: What prevents this from being called with a RuntimeArray? The length function will always return 0 in that case.
1229 for (; i < length(); ++i)
1230 args.append(get(globalObject, i));
1231}
1232
1233void JSArray::copyToArguments(JSGlobalObject* globalObject, CallFrame* callFrame, VirtualRegister firstElementDest, unsigned offset, unsigned length)
1234{
1235 VM& vm = globalObject->vm();
1236 auto scope = DECLARE_THROW_SCOPE(vm);
1237
1238 unsigned i = offset;
1239 WriteBarrier<Unknown>* vector;
1240 unsigned vectorEnd;
1241 length += offset; // We like to think of the length as being our length, rather than the output length.
1242
1243 // FIXME: What prevents this from being called with a RuntimeArray? The length function will always return 0 in that case.
1244 ASSERT(length == this->length());
1245
1246 Butterfly* butterfly = this->butterfly();
1247 switch (indexingType()) {
1248 case ArrayClass:
1249 return;
1250
1251 case ArrayWithUndecided: {
1252 vector = 0;
1253 vectorEnd = 0;
1254 break;
1255 }
1256
1257 case ArrayWithInt32:
1258 case ArrayWithContiguous: {
1259 vector = butterfly->contiguous().data();
1260 vectorEnd = butterfly->publicLength();
1261 break;
1262 }
1263
1264 case ArrayWithDouble: {
1265 vector = 0;
1266 vectorEnd = 0;
1267 for (; i < butterfly->publicLength(); ++i) {
1268 ASSERT(i < butterfly->vectorLength());
1269 double v = butterfly->contiguousDouble().at(this, i);
1270 if (v != v)
1271 break;
1272 callFrame->r(firstElementDest + i - offset) = JSValue(JSValue::EncodeAsDouble, v);
1273 }
1274 break;
1275 }
1276
1277 case ARRAY_WITH_ARRAY_STORAGE_INDEXING_TYPES: {
1278 ArrayStorage* storage = butterfly->arrayStorage();
1279 vector = storage->m_vector;
1280 vectorEnd = std::min(length, storage->vectorLength());
1281 break;
1282 }
1283
1284 default:
1285 CRASH();
1286#if COMPILER_QUIRK(CONSIDERS_UNREACHABLE_CODE)
1287 vector = 0;
1288 vectorEnd = 0;
1289 break;
1290#endif
1291 }
1292
1293 for (; i < vectorEnd; ++i) {
1294 WriteBarrier<Unknown>& v = vector[i];
1295 if (!v)
1296 break;
1297 callFrame->r(firstElementDest + i - offset) = v.get();
1298 }
1299
1300 for (; i < length; ++i) {
1301 callFrame->r(firstElementDest + i - offset) = get(globalObject, i);
1302 RETURN_IF_EXCEPTION(scope, void());
1303 }
1304}
1305
1306bool JSArray::isIteratorProtocolFastAndNonObservable()
1307{
1308 JSGlobalObject* globalObject = this->globalObject();
1309 if (!globalObject->isArrayPrototypeIteratorProtocolFastAndNonObservable())
1310 return false;
1311
1312 VM& vm = globalObject->vm();
1313 Structure* structure = this->structure(vm);
1314 // This is the fast case. Many arrays will be an original array.
1315 if (globalObject->isOriginalArrayStructure(structure))
1316 return true;
1317
1318 if (structure->mayInterceptIndexedAccesses())
1319 return false;
1320
1321 if (getPrototypeDirect(vm) != globalObject->arrayPrototype())
1322 return false;
1323
1324 if (getDirectOffset(vm, vm.propertyNames->iteratorSymbol) != invalidOffset)
1325 return false;
1326
1327 return true;
1328}
1329
1330inline JSArray* constructArray(ObjectInitializationScope& scope, Structure* arrayStructure, unsigned length)
1331{
1332 JSArray* array = JSArray::tryCreateUninitializedRestricted(scope, arrayStructure, length);
1333
1334 // FIXME: we should probably throw an out of memory error here, but
1335 // when making this change we should check that all clients of this
1336 // function will correctly handle an exception being thrown from here.
1337 // https://bugs.webkit.org/show_bug.cgi?id=169786
1338 RELEASE_ASSERT(array);
1339
1340 // FIXME: We only need this for subclasses of Array because we might need to allocate a new structure to change
1341 // indexing types while initializing. If this triggered a GC then we might scan our currently uninitialized
1342 // array and crash. https://bugs.webkit.org/show_bug.cgi?id=186811
1343 if (!arrayStructure->globalObject()->isOriginalArrayStructure(arrayStructure))
1344 JSArray::eagerlyInitializeButterfly(scope, array, length);
1345
1346 return array;
1347}
1348
1349JSArray* constructArray(JSGlobalObject* globalObject, Structure* arrayStructure, const ArgList& values)
1350{
1351 VM& vm = globalObject->vm();
1352 unsigned length = values.size();
1353 ObjectInitializationScope scope(vm);
1354
1355 JSArray* array = constructArray(scope, arrayStructure, length);
1356 for (unsigned i = 0; i < length; ++i)
1357 array->initializeIndex(scope, i, values.at(i));
1358 return array;
1359}
1360
1361JSArray* constructArray(JSGlobalObject* globalObject, Structure* arrayStructure, const JSValue* values, unsigned length)
1362{
1363 VM& vm = globalObject->vm();
1364 ObjectInitializationScope scope(vm);
1365
1366 JSArray* array = constructArray(scope, arrayStructure, length);
1367 for (unsigned i = 0; i < length; ++i)
1368 array->initializeIndex(scope, i, values[i]);
1369 return array;
1370}
1371
1372JSArray* constructArrayNegativeIndexed(JSGlobalObject* globalObject, Structure* arrayStructure, const JSValue* values, unsigned length)
1373{
1374 VM& vm = globalObject->vm();
1375 ObjectInitializationScope scope(vm);
1376
1377 JSArray* array = constructArray(scope, arrayStructure, length);
1378 for (int i = 0; i < static_cast<int>(length); ++i)
1379 array->initializeIndex(scope, i, values[-i]);
1380 return array;
1381}
1382
1383} // namespace JSC
1384