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