Array concat operation should check for length overflows.
[WebKit-https.git] / Source / JavaScriptCore / runtime / ArrayPrototype.cpp
1 /*
2  *  Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
3  *  Copyright (C) 2003-2017 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
20  *  USA
21  *
22  */
23
24 #include "config.h"
25 #include "ArrayPrototype.h"
26
27 #include "AdaptiveInferredPropertyValueWatchpointBase.h"
28 #include "ArrayConstructor.h"
29 #include "BuiltinNames.h"
30 #include "ButterflyInlines.h"
31 #include "CodeBlock.h"
32 #include "Error.h"
33 #include "GetterSetter.h"
34 #include "Interpreter.h"
35 #include "JIT.h"
36 #include "JSArrayInlines.h"
37 #include "JSCBuiltins.h"
38 #include "JSCInlines.h"
39 #include "JSStringBuilder.h"
40 #include "JSStringJoiner.h"
41 #include "Lookup.h"
42 #include "ObjectConstructor.h"
43 #include "ObjectPrototype.h"
44 #include "Operations.h"
45 #include "StringRecursionChecker.h"
46 #include <algorithm>
47 #include <wtf/Assertions.h>
48
49 namespace JSC {
50
51 EncodedJSValue JSC_HOST_CALL arrayProtoFuncToLocaleString(ExecState*);
52 EncodedJSValue JSC_HOST_CALL arrayProtoFuncJoin(ExecState*);
53 EncodedJSValue JSC_HOST_CALL arrayProtoFuncPop(ExecState*);
54 EncodedJSValue JSC_HOST_CALL arrayProtoFuncPush(ExecState*);
55 EncodedJSValue JSC_HOST_CALL arrayProtoFuncReverse(ExecState*);
56 EncodedJSValue JSC_HOST_CALL arrayProtoFuncShift(ExecState*);
57 EncodedJSValue JSC_HOST_CALL arrayProtoFuncSlice(ExecState*);
58 EncodedJSValue JSC_HOST_CALL arrayProtoFuncSplice(ExecState*);
59 EncodedJSValue JSC_HOST_CALL arrayProtoFuncUnShift(ExecState*);
60 EncodedJSValue JSC_HOST_CALL arrayProtoFuncIndexOf(ExecState*);
61 EncodedJSValue JSC_HOST_CALL arrayProtoFuncLastIndexOf(ExecState*);
62
63 // ------------------------------ ArrayPrototype ----------------------------
64
65 const ClassInfo ArrayPrototype::s_info = {"Array", &JSArray::s_info, nullptr, CREATE_METHOD_TABLE(ArrayPrototype)};
66
67 ArrayPrototype* ArrayPrototype::create(VM& vm, JSGlobalObject* globalObject, Structure* structure)
68 {
69     ArrayPrototype* prototype = new (NotNull, allocateCell<ArrayPrototype>(vm.heap)) ArrayPrototype(vm, structure);
70     prototype->finishCreation(vm, globalObject);
71     vm.heap.addFinalizer(prototype, destroy);
72     return prototype;
73 }
74
75 // ECMA 15.4.4
76 ArrayPrototype::ArrayPrototype(VM& vm, Structure* structure)
77     : JSArray(vm, structure, 0)
78 {
79 }
80
81 void ArrayPrototype::finishCreation(VM& vm, JSGlobalObject* globalObject)
82 {
83     Base::finishCreation(vm);
84     ASSERT(inherits(vm, info()));
85     vm.prototypeMap.addPrototype(this);
86
87     putDirectWithoutTransition(vm, vm.propertyNames->toString, globalObject->arrayProtoToStringFunction(), DontEnum);
88     putDirectWithoutTransition(vm, vm.propertyNames->builtinNames().valuesPublicName(), globalObject->arrayProtoValuesFunction(), DontEnum);
89     putDirectWithoutTransition(vm, vm.propertyNames->iteratorSymbol, globalObject->arrayProtoValuesFunction(), DontEnum);
90
91     JSC_NATIVE_FUNCTION_WITHOUT_TRANSITION(vm.propertyNames->toLocaleString, arrayProtoFuncToLocaleString, DontEnum, 0);
92     JSC_BUILTIN_FUNCTION_WITHOUT_TRANSITION("concat", arrayPrototypeConcatCodeGenerator, DontEnum);
93     JSC_BUILTIN_FUNCTION_WITHOUT_TRANSITION("fill", arrayPrototypeFillCodeGenerator, DontEnum);
94     JSC_NATIVE_FUNCTION_WITHOUT_TRANSITION(vm.propertyNames->join, arrayProtoFuncJoin, DontEnum, 1);
95     JSC_NATIVE_INTRINSIC_FUNCTION_WITHOUT_TRANSITION("pop", arrayProtoFuncPop, DontEnum, 0, ArrayPopIntrinsic);
96     JSC_NATIVE_INTRINSIC_FUNCTION_WITHOUT_TRANSITION(vm.propertyNames->builtinNames().pushPublicName(), arrayProtoFuncPush, DontEnum, 1, ArrayPushIntrinsic);
97     JSC_NATIVE_INTRINSIC_FUNCTION_WITHOUT_TRANSITION(vm.propertyNames->builtinNames().pushPrivateName(), arrayProtoFuncPush, DontEnum | DontDelete | ReadOnly, 1, ArrayPushIntrinsic);
98     JSC_NATIVE_FUNCTION_WITHOUT_TRANSITION("reverse", arrayProtoFuncReverse, DontEnum, 0);
99     JSC_NATIVE_FUNCTION_WITHOUT_TRANSITION(vm.propertyNames->builtinNames().shiftPublicName(), arrayProtoFuncShift, DontEnum, 0);
100     JSC_NATIVE_FUNCTION_WITHOUT_TRANSITION(vm.propertyNames->builtinNames().shiftPrivateName(), arrayProtoFuncShift, DontEnum | DontDelete | ReadOnly, 0);
101     JSC_NATIVE_INTRINSIC_FUNCTION_WITHOUT_TRANSITION(vm.propertyNames->slice, arrayProtoFuncSlice, DontEnum, 2, ArraySliceIntrinsic);
102     JSC_BUILTIN_FUNCTION_WITHOUT_TRANSITION("sort", arrayPrototypeSortCodeGenerator, DontEnum);
103     JSC_NATIVE_FUNCTION_WITHOUT_TRANSITION("splice", arrayProtoFuncSplice, DontEnum, 2);
104     JSC_NATIVE_FUNCTION_WITHOUT_TRANSITION("unshift", arrayProtoFuncUnShift, DontEnum, 1);
105     JSC_BUILTIN_FUNCTION_WITHOUT_TRANSITION("every", arrayPrototypeEveryCodeGenerator, DontEnum);
106     JSC_BUILTIN_FUNCTION_WITHOUT_TRANSITION("forEach", arrayPrototypeForEachCodeGenerator, DontEnum);
107     JSC_BUILTIN_FUNCTION_WITHOUT_TRANSITION("some", arrayPrototypeSomeCodeGenerator, DontEnum);
108     JSC_NATIVE_FUNCTION_WITHOUT_TRANSITION("indexOf", arrayProtoFuncIndexOf, DontEnum, 1);
109     JSC_NATIVE_FUNCTION_WITHOUT_TRANSITION("lastIndexOf", arrayProtoFuncLastIndexOf, DontEnum, 1);
110     JSC_BUILTIN_FUNCTION_WITHOUT_TRANSITION("filter", arrayPrototypeFilterCodeGenerator, DontEnum);
111     JSC_BUILTIN_FUNCTION_WITHOUT_TRANSITION("reduce", arrayPrototypeReduceCodeGenerator, DontEnum);
112     JSC_BUILTIN_FUNCTION_WITHOUT_TRANSITION("reduceRight", arrayPrototypeReduceRightCodeGenerator, DontEnum);
113     JSC_BUILTIN_FUNCTION_WITHOUT_TRANSITION("map", arrayPrototypeMapCodeGenerator, DontEnum);
114     JSC_BUILTIN_FUNCTION_WITHOUT_TRANSITION(vm.propertyNames->builtinNames().entriesPublicName(), arrayPrototypeEntriesCodeGenerator, DontEnum);
115     JSC_BUILTIN_FUNCTION_WITHOUT_TRANSITION(vm.propertyNames->builtinNames().keysPublicName(), arrayPrototypeKeysCodeGenerator, DontEnum);
116     JSC_BUILTIN_FUNCTION_WITHOUT_TRANSITION("find", arrayPrototypeFindCodeGenerator, DontEnum);
117     JSC_BUILTIN_FUNCTION_WITHOUT_TRANSITION("findIndex", arrayPrototypeFindIndexCodeGenerator, DontEnum);
118     JSC_BUILTIN_FUNCTION_WITHOUT_TRANSITION("includes", arrayPrototypeIncludesCodeGenerator, DontEnum);
119     JSC_BUILTIN_FUNCTION_WITHOUT_TRANSITION("copyWithin", arrayPrototypeCopyWithinCodeGenerator, DontEnum);
120
121     putDirectWithoutTransition(vm, vm.propertyNames->builtinNames().entriesPrivateName(), getDirect(vm, vm.propertyNames->builtinNames().entriesPublicName()), ReadOnly);
122     putDirectWithoutTransition(vm, vm.propertyNames->builtinNames().forEachPrivateName(), getDirect(vm, vm.propertyNames->builtinNames().forEachPublicName()), ReadOnly);
123     putDirectWithoutTransition(vm, vm.propertyNames->builtinNames().keysPrivateName(), getDirect(vm, vm.propertyNames->builtinNames().keysPublicName()), ReadOnly);
124     putDirectWithoutTransition(vm, vm.propertyNames->builtinNames().valuesPrivateName(), globalObject->arrayProtoValuesFunction(), ReadOnly);
125
126     JSObject* unscopables = constructEmptyObject(globalObject->globalExec(), globalObject->nullPrototypeObjectStructure());
127     const char* unscopableNames[] = {
128         "copyWithin",
129         "entries",
130         "fill",
131         "find",
132         "findIndex",
133         "includes",
134         "keys",
135         "values"
136     };
137     for (const char* unscopableName : unscopableNames)
138         unscopables->putDirect(vm, Identifier::fromString(&vm, unscopableName), jsBoolean(true));
139     putDirectWithoutTransition(vm, vm.propertyNames->unscopablesSymbol, unscopables, DontEnum | ReadOnly);
140 }
141
142 void ArrayPrototype::destroy(JSC::JSCell* cell)
143 {
144     ArrayPrototype* thisObject = static_cast<ArrayPrototype*>(cell);
145     thisObject->ArrayPrototype::~ArrayPrototype();
146 }
147
148 // ------------------------------ Array Functions ----------------------------
149
150 static ALWAYS_INLINE JSValue getProperty(ExecState* exec, JSObject* object, unsigned index)
151 {
152     VM& vm = exec->vm();
153     auto scope = DECLARE_THROW_SCOPE(vm);
154     
155     if (JSValue result = object->tryGetIndexQuickly(index))
156         return result;
157     // We want to perform get and has in the same operation.
158     // We can only do so when this behavior is not observable. The
159     // only time it is observable is when we encounter an opaque objects (ProxyObject and JSModuleNamespaceObject)
160     // somewhere in the prototype chain.
161     PropertySlot slot(object, PropertySlot::InternalMethodType::HasProperty);
162     bool hasProperty = object->getPropertySlot(exec, index, slot);
163     ASSERT(!scope.exception() || !hasProperty);
164     if (!hasProperty)
165         return { };
166     if (UNLIKELY(slot.isTaintedByOpaqueObject())) {
167         scope.release();
168         return object->get(exec, index);
169     }
170     scope.release();
171     return slot.getValue(exec, index);
172 }
173
174 static ALWAYS_INLINE bool putLength(ExecState* exec, VM& vm, JSObject* obj, JSValue value)
175 {
176     PutPropertySlot slot(obj);
177     return obj->methodTable(vm)->put(obj, exec, vm.propertyNames->length, value, slot);
178 }
179
180 static ALWAYS_INLINE void setLength(ExecState* exec, VM& vm, JSObject* obj, unsigned value)
181 {
182     auto scope = DECLARE_THROW_SCOPE(vm);
183     static const bool throwException = true;
184     if (isJSArray(obj)) {
185         jsCast<JSArray*>(obj)->setLength(exec, value, throwException);
186         RETURN_IF_EXCEPTION(scope, void());
187     }
188     bool success = putLength(exec, vm, obj, jsNumber(value));
189     RETURN_IF_EXCEPTION(scope, void());
190     if (UNLIKELY(!success))
191         throwTypeError(exec, scope, ASCIILiteral(ReadonlyPropertyWriteError));
192 }
193
194 ALWAYS_INLINE bool speciesWatchpointIsValid(ExecState* exec, JSObject* thisObject)
195 {
196     JSGlobalObject* globalObject = thisObject->globalObject();
197     ArrayPrototype* arrayPrototype = globalObject->arrayPrototype();
198
199     if (globalObject->arraySpeciesWatchpoint().stateOnJSThread() == ClearWatchpoint) {
200         arrayPrototype->tryInitializeSpeciesWatchpoint(exec);
201         ASSERT(globalObject->arraySpeciesWatchpoint().stateOnJSThread() != ClearWatchpoint);
202     }
203
204     return !thisObject->hasCustomProperties()
205         && arrayPrototype == thisObject->getPrototypeDirect()
206         && globalObject->arraySpeciesWatchpoint().stateOnJSThread() == IsWatched;
207 }
208
209 enum class SpeciesConstructResult {
210     FastPath,
211     Exception,
212     CreatedObject
213 };
214
215 static ALWAYS_INLINE std::pair<SpeciesConstructResult, JSObject*> speciesConstructArray(ExecState* exec, JSObject* thisObject, unsigned length)
216 {
217     VM& vm = exec->vm();
218     auto scope = DECLARE_THROW_SCOPE(vm);
219
220     auto exceptionResult = [] () {
221         return std::make_pair(SpeciesConstructResult::Exception, nullptr);
222     };
223
224     // ECMA 9.4.2.3: https://tc39.github.io/ecma262/#sec-arrayspeciescreate
225     JSValue constructor = jsUndefined();
226     bool thisIsArray = isArray(exec, thisObject);
227     RETURN_IF_EXCEPTION(scope, exceptionResult());
228     if (LIKELY(thisIsArray)) {
229         // Fast path in the normal case where the user has not set an own constructor and the Array.prototype.constructor is normal.
230         // We need prototype check for subclasses of Array, which are Array objects but have a different prototype by default.
231         bool isValid = speciesWatchpointIsValid(exec, thisObject);
232         if (LIKELY(isValid))
233             return std::make_pair(SpeciesConstructResult::FastPath, nullptr);
234
235         constructor = thisObject->get(exec, vm.propertyNames->constructor);
236         RETURN_IF_EXCEPTION(scope, exceptionResult());
237         if (constructor.isConstructor()) {
238             JSObject* constructorObject = jsCast<JSObject*>(constructor);
239             if (exec->lexicalGlobalObject() != constructorObject->globalObject())
240                 return std::make_pair(SpeciesConstructResult::FastPath, nullptr);;
241         }
242         if (constructor.isObject()) {
243             constructor = constructor.get(exec, vm.propertyNames->speciesSymbol);
244             RETURN_IF_EXCEPTION(scope, exceptionResult());
245             if (constructor.isNull())
246                 return std::make_pair(SpeciesConstructResult::FastPath, nullptr);;
247         }
248     } else
249         RETURN_IF_EXCEPTION(scope, exceptionResult());
250
251     if (constructor.isUndefined())
252         return std::make_pair(SpeciesConstructResult::FastPath, nullptr);
253
254     MarkedArgumentBuffer args;
255     args.append(jsNumber(length));
256     JSObject* newObject = construct(exec, constructor, args, "Species construction did not get a valid constructor");
257     RETURN_IF_EXCEPTION(scope, exceptionResult());
258     return std::make_pair(SpeciesConstructResult::CreatedObject, newObject);
259 }
260
261 static inline unsigned argumentClampedIndexFromStartOrEnd(ExecState* exec, int argument, unsigned length, unsigned undefinedValue = 0)
262 {
263     JSValue value = exec->argument(argument);
264     if (value.isUndefined())
265         return undefinedValue;
266
267     double indexDouble = value.toInteger(exec);
268     if (indexDouble < 0) {
269         indexDouble += length;
270         return indexDouble < 0 ? 0 : static_cast<unsigned>(indexDouble);
271     }
272     return indexDouble > length ? length : static_cast<unsigned>(indexDouble);
273 }
274
275 // The shift/unshift function implement the shift/unshift behaviour required
276 // by the corresponding array prototype methods, and by splice. In both cases,
277 // the methods are operating an an array or array like object.
278 //
279 //  header  currentCount  (remainder)
280 // [------][------------][-----------]
281 //  header  resultCount  (remainder)
282 // [------][-----------][-----------]
283 //
284 // The set of properties in the range 'header' must be unchanged. The set of
285 // properties in the range 'remainder' (where remainder = length - header -
286 // currentCount) will be shifted to the left or right as appropriate; in the
287 // case of shift this must be removing values, in the case of unshift this
288 // must be introducing new values.
289
290 template<JSArray::ShiftCountMode shiftCountMode>
291 void shift(ExecState* exec, JSObject* thisObj, unsigned header, unsigned currentCount, unsigned resultCount, unsigned length)
292 {
293     VM& vm = exec->vm();
294     auto scope = DECLARE_THROW_SCOPE(vm);
295
296     RELEASE_ASSERT(currentCount > resultCount);
297     unsigned count = currentCount - resultCount;
298
299     RELEASE_ASSERT(header <= length);
300     RELEASE_ASSERT(currentCount <= (length - header));
301
302     if (isJSArray(thisObj)) {
303         JSArray* array = asArray(thisObj);
304         if (array->length() == length && array->shiftCount<shiftCountMode>(exec, header, count))
305             return;
306     }
307
308     for (unsigned k = header; k < length - currentCount; ++k) {
309         unsigned from = k + currentCount;
310         unsigned to = k + resultCount;
311         JSValue value = getProperty(exec, thisObj, from);
312         RETURN_IF_EXCEPTION(scope, void());
313         if (value) {
314             thisObj->putByIndexInline(exec, to, value, true);
315             RETURN_IF_EXCEPTION(scope, void());
316         } else {
317             bool success = thisObj->methodTable(vm)->deletePropertyByIndex(thisObj, exec, to);
318             RETURN_IF_EXCEPTION(scope, void());
319             if (!success) {
320                 throwTypeError(exec, scope, ASCIILiteral(UnableToDeletePropertyError));
321                 return;
322             }
323         }
324     }
325     for (unsigned k = length; k > length - count; --k) {
326         bool success = thisObj->methodTable(vm)->deletePropertyByIndex(thisObj, exec, k - 1);
327         RETURN_IF_EXCEPTION(scope, void());
328         if (!success) {
329             throwTypeError(exec, scope, ASCIILiteral(UnableToDeletePropertyError));
330             return;
331         }
332     }
333 }
334
335 template<JSArray::ShiftCountMode shiftCountMode>
336 void unshift(ExecState* exec, JSObject* thisObj, unsigned header, unsigned currentCount, unsigned resultCount, unsigned length)
337 {
338     VM& vm = exec->vm();
339     auto scope = DECLARE_THROW_SCOPE(vm);
340
341     RELEASE_ASSERT(resultCount > currentCount);
342     unsigned count = resultCount - currentCount;
343
344     RELEASE_ASSERT(header <= length);
345     RELEASE_ASSERT(currentCount <= (length - header));
346
347     // Guard against overflow.
348     if (count > (UINT_MAX - length)) {
349         throwOutOfMemoryError(exec, scope);
350         return;
351     }
352
353     if (isJSArray(thisObj)) {
354         JSArray* array = asArray(thisObj);
355         if (array->length() == length) {
356             bool handled = array->unshiftCount<shiftCountMode>(exec, header, count);
357             ASSERT(!scope.exception() || handled);
358             if (handled)
359                 return;
360         }
361     }
362
363     for (unsigned k = length - currentCount; k > header; --k) {
364         unsigned from = k + currentCount - 1;
365         unsigned to = k + resultCount - 1;
366         JSValue value = getProperty(exec, thisObj, from);
367         RETURN_IF_EXCEPTION(scope, void());
368         if (value) {
369             thisObj->putByIndexInline(exec, to, value, true);
370             RETURN_IF_EXCEPTION(scope, void());
371         } else {
372             bool success = thisObj->methodTable(vm)->deletePropertyByIndex(thisObj, exec, to);
373             RETURN_IF_EXCEPTION(scope, void());
374             if (UNLIKELY(!success)) {
375                 throwTypeError(exec, scope, ASCIILiteral(UnableToDeletePropertyError));
376                 return;
377             }
378         }
379     }
380 }
381
382 EncodedJSValue JSC_HOST_CALL arrayProtoFuncToString(ExecState* exec)
383 {
384     VM& vm = exec->vm();
385     auto scope = DECLARE_THROW_SCOPE(vm);
386     JSValue thisValue = exec->thisValue().toThis(exec, StrictMode);
387
388     // 1. Let array be the result of calling ToObject on the this value.
389     JSObject* thisObject = thisValue.toObject(exec);
390     RETURN_IF_EXCEPTION(scope, encodedJSValue());
391     
392     // 2. Let func be the result of calling the [[Get]] internal method of array with argument "join".
393     JSValue function = JSValue(thisObject).get(exec, vm.propertyNames->join);
394     RETURN_IF_EXCEPTION(scope, encodedJSValue());
395
396     // 3. If IsCallable(func) is false, then let func be the standard built-in method Object.prototype.toString (15.2.4.2).
397     bool customJoinCase = false;
398     if (!function.isCell())
399         customJoinCase = true;
400     CallData callData;
401     CallType callType = getCallData(function, callData);
402     if (callType == CallType::None)
403         customJoinCase = true;
404
405     if (UNLIKELY(customJoinCase)) {
406         scope.release();
407         return JSValue::encode(jsMakeNontrivialString(exec, "[object ", thisObject->methodTable(vm)->className(thisObject), "]"));
408     }
409
410     // 4. Return the result of calling the [[Call]] internal method of func providing array as the this value and an empty arguments list.
411     if (!isJSArray(thisObject) || callType != CallType::Host || callData.native.function != arrayProtoFuncJoin) {
412         scope.release();
413         return JSValue::encode(call(exec, function, callType, callData, thisObject, exec->emptyList()));
414     }
415
416     ASSERT(isJSArray(thisValue));
417     JSArray* thisArray = asArray(thisValue);
418
419     unsigned length = thisArray->length();
420
421     StringRecursionChecker checker(exec, thisArray);
422     ASSERT(!scope.exception() || checker.earlyReturnValue());
423     if (JSValue earlyReturnValue = checker.earlyReturnValue())
424         return JSValue::encode(earlyReturnValue);
425
426     JSStringJoiner joiner(*exec, ',', length);
427     RETURN_IF_EXCEPTION(scope, encodedJSValue());
428
429     for (unsigned i = 0; i < length; ++i) {
430         JSValue element = thisArray->tryGetIndexQuickly(i);
431         if (!element) {
432             element = thisArray->get(exec, i);
433             RETURN_IF_EXCEPTION(scope, encodedJSValue());
434         }
435         joiner.append(*exec, element);
436         RETURN_IF_EXCEPTION(scope, encodedJSValue());
437     }
438
439     scope.release();
440     return JSValue::encode(joiner.join(*exec));
441 }
442
443 EncodedJSValue JSC_HOST_CALL arrayProtoFuncToLocaleString(ExecState* exec)
444 {
445     VM& vm = exec->vm();
446     auto scope = DECLARE_THROW_SCOPE(vm);
447     JSValue thisValue = exec->thisValue().toThis(exec, StrictMode);
448
449     JSObject* thisObject = thisValue.toObject(exec);
450     RETURN_IF_EXCEPTION(scope, encodedJSValue());
451
452     unsigned length = getLength(exec, thisObject);
453     RETURN_IF_EXCEPTION(scope, encodedJSValue());
454
455     StringRecursionChecker checker(exec, thisObject);
456     ASSERT(!scope.exception() || checker.earlyReturnValue());
457     if (JSValue earlyReturnValue = checker.earlyReturnValue())
458         return JSValue::encode(earlyReturnValue);
459
460     JSStringJoiner stringJoiner(*exec, ',', length);
461     RETURN_IF_EXCEPTION(scope, encodedJSValue());
462
463 #if ENABLE(INTL)
464     ArgList arguments(exec);
465     for (unsigned i = 0; i < length; ++i) {
466         JSValue element = thisObject->getIndex(exec, i);
467         RETURN_IF_EXCEPTION(scope, encodedJSValue());
468         if (element.isUndefinedOrNull())
469             element = jsEmptyString(exec);
470         else {
471             JSValue conversionFunction = element.get(exec, vm.propertyNames->toLocaleString);
472             RETURN_IF_EXCEPTION(scope, encodedJSValue());
473             CallData callData;
474             CallType callType = getCallData(conversionFunction, callData);
475             if (callType != CallType::None) {
476                 element = call(exec, conversionFunction, callType, callData, element, arguments);
477                 RETURN_IF_EXCEPTION(scope, encodedJSValue());
478             }
479         }
480         stringJoiner.append(*exec, element);
481         RETURN_IF_EXCEPTION(scope, encodedJSValue());
482     }
483 #else // !ENABLE(INTL)
484     for (unsigned i = 0; i < length; ++i) {
485         JSValue element = thisObject->getIndex(exec, i);
486         RETURN_IF_EXCEPTION(scope, encodedJSValue());
487         if (element.isUndefinedOrNull())
488             continue;
489         JSValue conversionFunction = element.get(exec, vm.propertyNames->toLocaleString);
490         RETURN_IF_EXCEPTION(scope, encodedJSValue());
491         CallData callData;
492         CallType callType = getCallData(conversionFunction, callData);
493         if (callType != CallType::None) {
494             element = call(exec, conversionFunction, callType, callData, element, exec->emptyList());
495             RETURN_IF_EXCEPTION(scope, encodedJSValue());
496         }
497         stringJoiner.append(*exec, element);
498         RETURN_IF_EXCEPTION(scope, encodedJSValue());
499     }
500 #endif // !ENABLE(INTL)
501
502     scope.release();
503     return JSValue::encode(stringJoiner.join(*exec));
504 }
505
506 static inline bool isHole(double value)
507 {
508     return std::isnan(value);
509 }
510
511 static inline bool isHole(const WriteBarrier<Unknown>& value)
512 {
513     return !value;
514 }
515
516 template<typename T> static inline bool containsHole(T* data, unsigned length)
517 {
518     for (unsigned i = 0; i < length; ++i) {
519         if (isHole(data[i]))
520             return true;
521     }
522     return false;
523 }
524
525 static inline bool holesMustForwardToPrototype(ExecState& state, JSObject* object)
526 {
527     auto& vm = state.vm();
528     return object->structure(vm)->holesMustForwardToPrototype(vm);
529 }
530
531 static JSValue slowJoin(ExecState& exec, JSObject* thisObject, JSString* separator, uint64_t length)
532 {
533     VM& vm = exec.vm();
534     auto scope = DECLARE_THROW_SCOPE(vm);
535
536     // 5. If len is zero, return the empty String.
537     if (!length)
538         return jsEmptyString(&exec);
539
540     // 6. Let element0 be Get(O, "0").
541     JSValue element0 = thisObject->getIndex(&exec, 0);
542     RETURN_IF_EXCEPTION(scope, { });
543
544     // 7. If element0 is undefined or null, let R be the empty String; otherwise, let R be ? ToString(element0).
545     JSString* r = nullptr;
546     if (element0.isUndefinedOrNull())
547         r = jsEmptyString(&exec);
548     else
549         r = element0.toString(&exec);
550     RETURN_IF_EXCEPTION(scope, { });
551
552     // 8. Let k be 1.
553     // 9. Repeat, while k < len
554     // 9.e Increase k by 1..
555     for (uint64_t k = 1; k < length; ++k) {
556         // b. Let element be ? Get(O, ! ToString(k)).
557         JSValue element = thisObject->get(&exec, Identifier::fromString(&exec, AtomicString::number(k)));
558         RETURN_IF_EXCEPTION(scope, { });
559
560         // c. If element is undefined or null, let next be the empty String; otherwise, let next be ? ToString(element).
561         JSString* next = nullptr;
562         if (element.isUndefinedOrNull()) {
563             if (!separator->length())
564                 continue;
565             next = jsEmptyString(&exec);
566         } else
567             next = element.toString(&exec);
568         RETURN_IF_EXCEPTION(scope, { });
569
570         // a. Let S be the String value produced by concatenating R and sep.
571         // d. Let R be a String value produced by concatenating S and next.
572         r = jsString(&exec, r, separator, next);
573         RETURN_IF_EXCEPTION(scope, { });
574     }
575     // 10. Return R.
576     return r;
577 }
578
579 static inline bool canUseFastJoin(const JSObject* thisObject)
580 {
581     switch (thisObject->indexingType()) {
582     case ALL_CONTIGUOUS_INDEXING_TYPES:
583     case ALL_INT32_INDEXING_TYPES:
584     case ALL_DOUBLE_INDEXING_TYPES:
585         return true;
586     default:
587         break;
588     }
589     return false;
590 }
591
592 static inline JSValue fastJoin(ExecState& state, JSObject* thisObject, StringView separator, unsigned length)
593 {
594     VM& vm = state.vm();
595     auto scope = DECLARE_THROW_SCOPE(vm);
596
597     switch (thisObject->indexingType()) {
598     case ALL_CONTIGUOUS_INDEXING_TYPES:
599     case ALL_INT32_INDEXING_TYPES: {
600         auto& butterfly = *thisObject->butterfly();
601         if (length > butterfly.publicLength())
602             break;
603         JSStringJoiner joiner(state, separator, length);
604         RETURN_IF_EXCEPTION(scope, { });
605         auto data = butterfly.contiguous().data();
606         bool holesKnownToBeOK = false;
607         for (unsigned i = 0; i < length; ++i) {
608             if (JSValue value = data[i].get()) {
609                 if (!joiner.appendWithoutSideEffects(state, value))
610                     goto generalCase;
611             } else {
612                 if (!holesKnownToBeOK) {
613                     if (holesMustForwardToPrototype(state, thisObject))
614                         goto generalCase;
615                     holesKnownToBeOK = true;
616                 }
617                 joiner.appendEmptyString();
618             }
619         }
620         scope.release();
621         return joiner.join(state);
622     }
623     case ALL_DOUBLE_INDEXING_TYPES: {
624         auto& butterfly = *thisObject->butterfly();
625         if (length > butterfly.publicLength())
626             break;
627         JSStringJoiner joiner(state, separator, length);
628         RETURN_IF_EXCEPTION(scope, { });
629         auto data = butterfly.contiguousDouble().data();
630         bool holesKnownToBeOK = false;
631         for (unsigned i = 0; i < length; ++i) {
632             double value = data[i];
633             if (!isHole(value))
634                 joiner.append(state, jsDoubleNumber(value));
635             else {
636                 if (!holesKnownToBeOK) {
637                     if (thisObject->structure(vm)->holesMustForwardToPrototype(vm))
638                         goto generalCase;
639                     holesKnownToBeOK = true;
640                 }
641                 joiner.appendEmptyString();
642             }
643         }
644         scope.release();
645         return joiner.join(state);
646     }
647     }
648
649 generalCase:
650     JSStringJoiner joiner(state, separator, length);
651     RETURN_IF_EXCEPTION(scope, { });
652     for (unsigned i = 0; i < length; ++i) {
653         JSValue element = thisObject->getIndex(&state, i);
654         RETURN_IF_EXCEPTION(scope, { });
655         joiner.append(state, element);
656         RETURN_IF_EXCEPTION(scope, { });
657     }
658     scope.release();
659     return joiner.join(state);
660 }
661
662 EncodedJSValue JSC_HOST_CALL arrayProtoFuncJoin(ExecState* exec)
663 {
664     VM& vm = exec->vm();
665     auto scope = DECLARE_THROW_SCOPE(vm);
666
667     // 1. Let O be ? ToObject(this value).
668     JSObject* thisObject = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
669     ASSERT(!!scope.exception() == !thisObject);
670     if (UNLIKELY(!thisObject))
671         return encodedJSValue();
672
673     StringRecursionChecker checker(exec, thisObject);
674     ASSERT(!scope.exception() || checker.earlyReturnValue());
675     if (JSValue earlyReturnValue = checker.earlyReturnValue())
676         return JSValue::encode(earlyReturnValue);
677
678     // 2. Let len be ? ToLength(? Get(O, "length")).
679     double length = toLength(exec, thisObject);
680     RETURN_IF_EXCEPTION(scope, encodedJSValue());
681
682     // 3. If separator is undefined, let separator be the single-element String ",".
683     JSValue separatorValue = exec->argument(0);
684     if (separatorValue.isUndefined()) {
685         const LChar comma = ',';
686
687         if (UNLIKELY(length > std::numeric_limits<unsigned>::max() || !canUseFastJoin(thisObject))) {
688             uint64_t length64 = static_cast<uint64_t>(length);
689             ASSERT(static_cast<double>(length64) == length);
690             JSString* jsSeparator = jsSingleCharacterString(exec, comma);
691             RETURN_IF_EXCEPTION(scope, encodedJSValue());
692
693             scope.release();
694             return JSValue::encode(slowJoin(*exec, thisObject, jsSeparator, length64));
695         }
696
697         unsigned unsignedLength = static_cast<unsigned>(length);
698         ASSERT(static_cast<double>(unsignedLength) == length);
699
700         scope.release();
701         return JSValue::encode(fastJoin(*exec, thisObject, { &comma, 1 }, unsignedLength));
702     }
703
704     // 4. Let sep be ? ToString(separator).
705     JSString* jsSeparator = separatorValue.toString(exec);
706     RETURN_IF_EXCEPTION(scope, encodedJSValue());
707
708     if (UNLIKELY(length > std::numeric_limits<unsigned>::max() || !canUseFastJoin(thisObject))) {
709         uint64_t length64 = static_cast<uint64_t>(length);
710         ASSERT(static_cast<double>(length64) == length);
711
712         scope.release();
713         return JSValue::encode(slowJoin(*exec, thisObject, jsSeparator, length64));
714     }
715
716     auto viewWithString = jsSeparator->viewWithUnderlyingString(*exec);
717     RETURN_IF_EXCEPTION(scope, encodedJSValue());
718
719     scope.release();
720     return JSValue::encode(fastJoin(*exec, thisObject, viewWithString.view, length));
721 }
722
723 EncodedJSValue JSC_HOST_CALL arrayProtoFuncPop(ExecState* exec)
724 {
725     VM& vm = exec->vm();
726     auto scope = DECLARE_THROW_SCOPE(vm);
727
728     JSValue thisValue = exec->thisValue().toThis(exec, StrictMode);
729
730     if (isJSArray(thisValue)) {
731         scope.release();
732         return JSValue::encode(asArray(thisValue)->pop(exec));
733     }
734
735     JSObject* thisObj = thisValue.toObject(exec);
736     ASSERT(!!scope.exception() == !thisObj);
737     if (UNLIKELY(!thisObj))
738         return encodedJSValue();
739     unsigned length = getLength(exec, thisObj);
740     RETURN_IF_EXCEPTION(scope, encodedJSValue());
741
742     if (length == 0) {
743         scope.release();
744         putLength(exec, vm, thisObj, jsNumber(length));
745         return JSValue::encode(jsUndefined());
746     }
747
748     JSValue result = thisObj->get(exec, length - 1);
749     RETURN_IF_EXCEPTION(scope, encodedJSValue());
750     bool success = thisObj->methodTable(vm)->deletePropertyByIndex(thisObj, exec, length - 1);
751     RETURN_IF_EXCEPTION(scope, encodedJSValue());
752     if (UNLIKELY(!success)) {
753         throwTypeError(exec, scope, ASCIILiteral(UnableToDeletePropertyError));
754         return encodedJSValue();
755     }
756     scope.release();
757     putLength(exec, vm, thisObj, jsNumber(length - 1));
758     return JSValue::encode(result);
759 }
760
761 EncodedJSValue JSC_HOST_CALL arrayProtoFuncPush(ExecState* exec)
762 {
763     VM& vm = exec->vm();
764     auto scope = DECLARE_THROW_SCOPE(vm);
765     JSValue thisValue = exec->thisValue().toThis(exec, StrictMode);
766
767     if (isJSArray(thisValue) && exec->argumentCount() == 1) {
768         JSArray* array = asArray(thisValue);
769         scope.release();
770         array->push(exec, exec->uncheckedArgument(0));
771         return JSValue::encode(jsNumber(array->length()));
772     }
773     
774     JSObject* thisObj = thisValue.toObject(exec);
775     ASSERT(!!scope.exception() == !thisObj);
776     if (UNLIKELY(!thisObj))
777         return encodedJSValue();
778     unsigned length = getLength(exec, thisObj);
779     RETURN_IF_EXCEPTION(scope, encodedJSValue());
780
781     for (unsigned n = 0; n < exec->argumentCount(); n++) {
782         // Check for integer overflow; where safe we can do a fast put by index.
783         if (length + n >= length)
784             thisObj->methodTable(vm)->putByIndex(thisObj, exec, length + n, exec->uncheckedArgument(n), true);
785         else {
786             PutPropertySlot slot(thisObj);
787             Identifier propertyName = Identifier::fromString(exec, JSValue(static_cast<int64_t>(length) + static_cast<int64_t>(n)).toWTFString(exec));
788             thisObj->methodTable(vm)->put(thisObj, exec, propertyName, exec->uncheckedArgument(n), slot);
789         }
790         RETURN_IF_EXCEPTION(scope, encodedJSValue());
791     }
792     
793     JSValue newLength(static_cast<int64_t>(length) + static_cast<int64_t>(exec->argumentCount()));
794     scope.release();
795     putLength(exec, vm, thisObj, newLength);
796     return JSValue::encode(newLength);
797 }
798
799 EncodedJSValue JSC_HOST_CALL arrayProtoFuncReverse(ExecState* exec)
800 {
801     VM& vm = exec->vm();
802     auto scope = DECLARE_THROW_SCOPE(vm);
803
804     JSObject* thisObject = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
805     ASSERT(!!scope.exception() == !thisObject);
806     if (UNLIKELY(!thisObject))
807         return encodedJSValue();
808
809     unsigned length = getLength(exec, thisObject);
810     RETURN_IF_EXCEPTION(scope, encodedJSValue());
811
812     switch (thisObject->indexingType()) {
813     case ALL_CONTIGUOUS_INDEXING_TYPES:
814     case ALL_INT32_INDEXING_TYPES: {
815         auto& butterfly = *thisObject->butterfly();
816         if (length > butterfly.publicLength())
817             break;
818         auto data = butterfly.contiguous().data();
819         if (containsHole(data, length) && holesMustForwardToPrototype(*exec, thisObject))
820             break;
821         std::reverse(data, data + length);
822         return JSValue::encode(thisObject);
823     }
824     case ALL_DOUBLE_INDEXING_TYPES: {
825         auto& butterfly = *thisObject->butterfly();
826         if (length > butterfly.publicLength())
827             break;
828         auto data = butterfly.contiguousDouble().data();
829         if (containsHole(data, length) && holesMustForwardToPrototype(*exec, thisObject))
830             break;
831         std::reverse(data, data + length);
832         return JSValue::encode(thisObject);
833     }
834     case ALL_ARRAY_STORAGE_INDEXING_TYPES: {
835         auto& storage = *thisObject->butterfly()->arrayStorage();
836         if (length > storage.vectorLength())
837             break;
838         if (storage.hasHoles() && holesMustForwardToPrototype(*exec, thisObject))
839             break;
840         auto data = storage.vector().data();
841         std::reverse(data, data + length);
842         return JSValue::encode(thisObject);
843     }
844     }
845
846     unsigned middle = length / 2;
847     for (unsigned lower = 0; lower < middle; lower++) {
848         unsigned upper = length - lower - 1;
849         bool lowerExists = thisObject->hasProperty(exec, lower);
850         RETURN_IF_EXCEPTION(scope, encodedJSValue());
851         JSValue lowerValue;
852         if (lowerExists) {
853             lowerValue = thisObject->get(exec, lower);
854             RETURN_IF_EXCEPTION(scope, encodedJSValue());
855         }
856
857         bool upperExists = thisObject->hasProperty(exec, upper);
858         RETURN_IF_EXCEPTION(scope, encodedJSValue());
859         JSValue upperValue;
860         if (upperExists) {
861             upperValue = thisObject->get(exec, upper);
862             RETURN_IF_EXCEPTION(scope, encodedJSValue());
863         }
864
865         if (upperExists) {
866             thisObject->putByIndexInline(exec, lower, upperValue, true);
867             RETURN_IF_EXCEPTION(scope, encodedJSValue());
868         } else {
869             bool success = thisObject->methodTable(vm)->deletePropertyByIndex(thisObject, exec, lower);
870             RETURN_IF_EXCEPTION(scope, encodedJSValue());
871             if (UNLIKELY(!success)) {
872                 throwTypeError(exec, scope, ASCIILiteral(UnableToDeletePropertyError));
873                 return encodedJSValue();
874             }
875         }
876
877         if (lowerExists) {
878             thisObject->putByIndexInline(exec, upper, lowerValue, true);
879             RETURN_IF_EXCEPTION(scope, encodedJSValue());
880         } else {
881             bool success = thisObject->methodTable(vm)->deletePropertyByIndex(thisObject, exec, upper);
882             RETURN_IF_EXCEPTION(scope, encodedJSValue());
883             if (UNLIKELY(!success)) {
884                 throwTypeError(exec, scope, ASCIILiteral(UnableToDeletePropertyError));
885                 return encodedJSValue();
886             }
887         }
888     }
889     return JSValue::encode(thisObject);
890 }
891
892 EncodedJSValue JSC_HOST_CALL arrayProtoFuncShift(ExecState* exec)
893 {
894     VM& vm = exec->vm();
895     auto scope = DECLARE_THROW_SCOPE(vm);
896     JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
897     ASSERT(!!scope.exception() == !thisObj);
898     if (UNLIKELY(!thisObj))
899         return encodedJSValue();
900     unsigned length = getLength(exec, thisObj);
901     RETURN_IF_EXCEPTION(scope, encodedJSValue());
902
903     if (length == 0) {
904         scope.release();
905         putLength(exec, vm, thisObj, jsNumber(length));
906         return JSValue::encode(jsUndefined());
907     }
908
909     JSValue result = thisObj->getIndex(exec, 0);
910     RETURN_IF_EXCEPTION(scope, encodedJSValue());
911     shift<JSArray::ShiftCountForShift>(exec, thisObj, 0, 1, 0, length);
912     RETURN_IF_EXCEPTION(scope, encodedJSValue());
913     scope.release();
914     putLength(exec, vm, thisObj, jsNumber(length - 1));
915     return JSValue::encode(result);
916 }
917
918 EncodedJSValue JSC_HOST_CALL arrayProtoFuncSlice(ExecState* exec)
919 {
920     // https://tc39.github.io/ecma262/#sec-array.prototype.slice
921     VM& vm = exec->vm();
922     auto scope = DECLARE_THROW_SCOPE(vm);
923     JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
924     ASSERT(!!scope.exception() == !thisObj);
925     if (UNLIKELY(!thisObj))
926         return { };
927     unsigned length = getLength(exec, thisObj);
928     RETURN_IF_EXCEPTION(scope, { });
929
930     unsigned begin = argumentClampedIndexFromStartOrEnd(exec, 0, length);
931     RETURN_IF_EXCEPTION(scope, { });
932     unsigned end = argumentClampedIndexFromStartOrEnd(exec, 1, length, length);
933     RETURN_IF_EXCEPTION(scope, { });
934
935     std::pair<SpeciesConstructResult, JSObject*> speciesResult = speciesConstructArray(exec, thisObj, end - begin);
936     // We can only get an exception if we call some user function.
937     ASSERT(!!scope.exception() == (speciesResult.first == SpeciesConstructResult::Exception));
938     if (UNLIKELY(speciesResult.first == SpeciesConstructResult::Exception))
939         return { };
940
941     bool okToDoFastPath = speciesResult.first == SpeciesConstructResult::FastPath && isJSArray(thisObj) && length == getLength(exec, thisObj);
942     RETURN_IF_EXCEPTION(scope, { });
943     if (LIKELY(okToDoFastPath)) {
944         if (JSArray* result = asArray(thisObj)->fastSlice(*exec, begin, end - begin))
945             return JSValue::encode(result);
946     }
947
948     JSObject* result;
949     if (speciesResult.first == SpeciesConstructResult::CreatedObject)
950         result = speciesResult.second;
951     else {
952         result = constructEmptyArray(exec, nullptr, end - begin);
953         RETURN_IF_EXCEPTION(scope, { });
954     }
955
956     unsigned n = 0;
957     for (unsigned k = begin; k < end; k++, n++) {
958         JSValue v = getProperty(exec, thisObj, k);
959         RETURN_IF_EXCEPTION(scope, { });
960         if (v) {
961             result->putDirectIndex(exec, n, v, 0, PutDirectIndexShouldThrow);
962             RETURN_IF_EXCEPTION(scope, { });
963         }
964     }
965     scope.release();
966     setLength(exec, vm, result, n);
967     return JSValue::encode(result);
968 }
969
970 EncodedJSValue JSC_HOST_CALL arrayProtoFuncSplice(ExecState* exec)
971 {
972     // 15.4.4.12
973
974     VM& vm = exec->vm();
975     auto scope = DECLARE_THROW_SCOPE(vm);
976
977     JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
978     ASSERT(!!scope.exception() == !thisObj);
979     if (UNLIKELY(!thisObj))
980         return encodedJSValue();
981     unsigned length = getLength(exec, thisObj);
982     RETURN_IF_EXCEPTION(scope, encodedJSValue());
983
984     if (!exec->argumentCount()) {
985         std::pair<SpeciesConstructResult, JSObject*> speciesResult = speciesConstructArray(exec, thisObj, 0);
986         ASSERT(!!scope.exception() == (speciesResult.first == SpeciesConstructResult::Exception));
987         if (UNLIKELY(speciesResult.first == SpeciesConstructResult::Exception))
988             return encodedJSValue();
989
990         JSObject* result;
991         if (speciesResult.first == SpeciesConstructResult::CreatedObject)
992             result = speciesResult.second;
993         else {
994             result = constructEmptyArray(exec, nullptr);
995             RETURN_IF_EXCEPTION(scope, encodedJSValue());
996         }
997
998         setLength(exec, vm, result, 0);
999         RETURN_IF_EXCEPTION(scope, encodedJSValue());
1000         scope.release();
1001         setLength(exec, vm, thisObj, length);
1002         return JSValue::encode(result);
1003     }
1004
1005     unsigned actualStart = argumentClampedIndexFromStartOrEnd(exec, 0, length);
1006     RETURN_IF_EXCEPTION(scope, encodedJSValue());
1007
1008     unsigned actualDeleteCount = length - actualStart;
1009     if (exec->argumentCount() > 1) {
1010         double deleteCount = exec->uncheckedArgument(1).toInteger(exec);
1011         RETURN_IF_EXCEPTION(scope, encodedJSValue());
1012         if (deleteCount < 0)
1013             actualDeleteCount = 0;
1014         else if (deleteCount > length - actualStart)
1015             actualDeleteCount = length - actualStart;
1016         else
1017             actualDeleteCount = static_cast<unsigned>(deleteCount);
1018     }
1019
1020     std::pair<SpeciesConstructResult, JSObject*> speciesResult = speciesConstructArray(exec, thisObj, actualDeleteCount);
1021     ASSERT(!!scope.exception() == (speciesResult.first == SpeciesConstructResult::Exception));
1022     if (speciesResult.first == SpeciesConstructResult::Exception)
1023         return JSValue::encode(jsUndefined());
1024
1025     JSObject* result = nullptr;
1026     bool okToDoFastPath = speciesResult.first == SpeciesConstructResult::FastPath && isJSArray(thisObj) && length == getLength(exec, thisObj);
1027     RETURN_IF_EXCEPTION(scope, encodedJSValue());
1028     if (LIKELY(okToDoFastPath))
1029         result = asArray(thisObj)->fastSlice(*exec, actualStart, actualDeleteCount);
1030
1031     if (!result) {
1032         if (speciesResult.first == SpeciesConstructResult::CreatedObject) {
1033             result = speciesResult.second;
1034             
1035             for (unsigned k = 0; k < actualDeleteCount; ++k) {
1036                 JSValue v = getProperty(exec, thisObj, k + actualStart);
1037                 RETURN_IF_EXCEPTION(scope, encodedJSValue());
1038                 if (UNLIKELY(!v))
1039                     continue;
1040                 result->putByIndexInline(exec, k, v, true);
1041                 RETURN_IF_EXCEPTION(scope, encodedJSValue());
1042             }
1043         } else {
1044             result = JSArray::tryCreateForInitializationPrivate(vm, exec->lexicalGlobalObject()->arrayStructureForIndexingTypeDuringAllocation(ArrayWithUndecided), actualDeleteCount);
1045             if (!result)
1046                 return JSValue::encode(throwOutOfMemoryError(exec, scope));
1047             
1048             for (unsigned k = 0; k < actualDeleteCount; ++k) {
1049                 JSValue v = getProperty(exec, thisObj, k + actualStart);
1050                 RETURN_IF_EXCEPTION(scope, encodedJSValue());
1051                 if (UNLIKELY(!v))
1052                     continue;
1053                 result->initializeIndex(vm, k, v);
1054             }
1055         }
1056     }
1057
1058     unsigned itemCount = std::max<int>(exec->argumentCount() - 2, 0);
1059     if (itemCount < actualDeleteCount) {
1060         shift<JSArray::ShiftCountForSplice>(exec, thisObj, actualStart, actualDeleteCount, itemCount, length);
1061         RETURN_IF_EXCEPTION(scope, encodedJSValue());
1062     } else if (itemCount > actualDeleteCount) {
1063         unshift<JSArray::ShiftCountForSplice>(exec, thisObj, actualStart, actualDeleteCount, itemCount, length);
1064         RETURN_IF_EXCEPTION(scope, encodedJSValue());
1065     }
1066     for (unsigned k = 0; k < itemCount; ++k) {
1067         thisObj->putByIndexInline(exec, k + actualStart, exec->uncheckedArgument(k + 2), true);
1068         RETURN_IF_EXCEPTION(scope, encodedJSValue());
1069     }
1070     
1071     scope.release();
1072     setLength(exec, vm, thisObj, length - actualDeleteCount + itemCount);
1073     return JSValue::encode(result);
1074 }
1075
1076 EncodedJSValue JSC_HOST_CALL arrayProtoFuncUnShift(ExecState* exec)
1077 {
1078     VM& vm = exec->vm();
1079     auto scope = DECLARE_THROW_SCOPE(vm);
1080     // 15.4.4.13
1081
1082     JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
1083     ASSERT(!!scope.exception() == !thisObj);
1084     if (UNLIKELY(!thisObj))
1085         return encodedJSValue();
1086     unsigned length = getLength(exec, thisObj);
1087     RETURN_IF_EXCEPTION(scope, encodedJSValue());
1088
1089     unsigned nrArgs = exec->argumentCount();
1090     if (nrArgs) {
1091         unshift<JSArray::ShiftCountForShift>(exec, thisObj, 0, 0, nrArgs, length);
1092         RETURN_IF_EXCEPTION(scope, encodedJSValue());
1093     }
1094     for (unsigned k = 0; k < nrArgs; ++k) {
1095         thisObj->putByIndexInline(exec, k, exec->uncheckedArgument(k), true);
1096         RETURN_IF_EXCEPTION(scope, encodedJSValue());
1097     }
1098     JSValue result = jsNumber(length + nrArgs);
1099     scope.release();
1100     putLength(exec, vm, thisObj, result);
1101     return JSValue::encode(result);
1102 }
1103
1104 EncodedJSValue JSC_HOST_CALL arrayProtoFuncIndexOf(ExecState* exec)
1105 {
1106     VM& vm = exec->vm();
1107     auto scope = DECLARE_THROW_SCOPE(vm);
1108
1109     // 15.4.4.14
1110     JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
1111     ASSERT(!!scope.exception() == !thisObj);
1112     if (UNLIKELY(!thisObj))
1113         return encodedJSValue();
1114     unsigned length = getLength(exec, thisObj);
1115     RETURN_IF_EXCEPTION(scope, encodedJSValue());
1116
1117     unsigned index = argumentClampedIndexFromStartOrEnd(exec, 1, length);
1118     JSValue searchElement = exec->argument(0);
1119     for (; index < length; ++index) {
1120         JSValue e = getProperty(exec, thisObj, index);
1121         RETURN_IF_EXCEPTION(scope, encodedJSValue());
1122         if (!e)
1123             continue;
1124         if (JSValue::strictEqual(exec, searchElement, e))
1125             return JSValue::encode(jsNumber(index));
1126         RETURN_IF_EXCEPTION(scope, encodedJSValue());
1127     }
1128
1129     return JSValue::encode(jsNumber(-1));
1130 }
1131
1132 EncodedJSValue JSC_HOST_CALL arrayProtoFuncLastIndexOf(ExecState* exec)
1133 {
1134     VM& vm = exec->vm();
1135     auto scope = DECLARE_THROW_SCOPE(vm);
1136
1137     // 15.4.4.15
1138     JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
1139     ASSERT(!!scope.exception() == !thisObj);
1140     if (UNLIKELY(!thisObj))
1141         return encodedJSValue();
1142     unsigned length = getLength(exec, thisObj);
1143     if (UNLIKELY(scope.exception()) || !length)
1144         return JSValue::encode(jsNumber(-1));
1145
1146     unsigned index = length - 1;
1147     if (exec->argumentCount() >= 2) {
1148         JSValue fromValue = exec->uncheckedArgument(1);
1149         double fromDouble = fromValue.toInteger(exec);
1150         if (fromDouble < 0) {
1151             fromDouble += length;
1152             if (fromDouble < 0)
1153                 return JSValue::encode(jsNumber(-1));
1154         }
1155         if (fromDouble < length)
1156             index = static_cast<unsigned>(fromDouble);
1157     }
1158
1159     JSValue searchElement = exec->argument(0);
1160     do {
1161         RELEASE_ASSERT(index < length);
1162         JSValue e = getProperty(exec, thisObj, index);
1163         RETURN_IF_EXCEPTION(scope, encodedJSValue());
1164         if (!e)
1165             continue;
1166         if (JSValue::strictEqual(exec, searchElement, e))
1167             return JSValue::encode(jsNumber(index));
1168         RETURN_IF_EXCEPTION(scope, encodedJSValue());
1169     } while (index--);
1170
1171     return JSValue::encode(jsNumber(-1));
1172 }
1173
1174 static bool moveElements(ExecState* exec, VM& vm, JSArray* target, unsigned targetOffset, JSArray* source, unsigned sourceLength)
1175 {
1176     auto scope = DECLARE_THROW_SCOPE(vm);
1177
1178     if (LIKELY(!hasAnyArrayStorage(source->indexingType()) && !source->structure()->holesMustForwardToPrototype(vm))) {
1179         for (unsigned i = 0; i < sourceLength; ++i) {
1180             JSValue value = source->tryGetIndexQuickly(i);
1181             if (value) {
1182                 target->putDirectIndex(exec, targetOffset + i, value, 0, PutDirectIndexShouldThrow);
1183                 RETURN_IF_EXCEPTION(scope, false);
1184             }
1185         }
1186     } else {
1187         for (unsigned i = 0; i < sourceLength; ++i) {
1188             JSValue value = getProperty(exec, source, i);
1189             RETURN_IF_EXCEPTION(scope, false);
1190             if (value) {
1191                 target->putDirectIndex(exec, targetOffset + i, value, 0, PutDirectIndexShouldThrow);
1192                 RETURN_IF_EXCEPTION(scope, false);
1193             }
1194         }
1195     }
1196     return true;
1197 }
1198
1199 static EncodedJSValue concatAppendOne(ExecState* exec, VM& vm, JSArray* first, JSValue second)
1200 {
1201     auto scope = DECLARE_THROW_SCOPE(vm);
1202
1203     ASSERT(!isJSArray(second));
1204     ASSERT(!shouldUseSlowPut(first->indexingType()));
1205     Butterfly* firstButterfly = first->butterfly();
1206     unsigned firstArraySize = firstButterfly->publicLength();
1207
1208     Checked<unsigned, RecordOverflow> checkedResultSize = firstArraySize;
1209     checkedResultSize += 1;
1210     if (UNLIKELY(checkedResultSize.hasOverflowed())) {
1211         throwOutOfMemoryError(exec, scope);
1212         return encodedJSValue();
1213     }
1214
1215     unsigned resultSize = checkedResultSize.unsafeGet();
1216     IndexingType type = first->mergeIndexingTypeForCopying(indexingTypeForValue(second) | IsArray);
1217     
1218     if (type == NonArray)
1219         type = first->indexingType();
1220
1221     Structure* resultStructure = exec->lexicalGlobalObject()->arrayStructureForIndexingTypeDuringAllocation(type);
1222     JSArray* result = JSArray::create(vm, resultStructure, resultSize);
1223     if (UNLIKELY(!result)) {
1224         throwOutOfMemoryError(exec, scope);
1225         return encodedJSValue();
1226     }
1227
1228     bool success = result->appendMemcpy(exec, vm, 0, first);
1229     ASSERT(!success || !scope.exception());
1230     if (!success) {
1231         RETURN_IF_EXCEPTION(scope, encodedJSValue());
1232
1233         bool success = moveElements(exec, vm, result, 0, first, firstArraySize);
1234         ASSERT(!scope.exception() == success);
1235         if (UNLIKELY(!success))
1236             return encodedJSValue();
1237     }
1238
1239     scope.release();
1240     result->putDirectIndex(exec, firstArraySize, second);
1241     return JSValue::encode(result);
1242
1243 }
1244
1245
1246 EncodedJSValue JSC_HOST_CALL arrayProtoPrivateFuncConcatMemcpy(ExecState* exec)
1247 {
1248     ASSERT(exec->argumentCount() == 2);
1249     VM& vm = exec->vm();
1250     auto scope = DECLARE_THROW_SCOPE(vm);
1251
1252     JSArray* firstArray = jsCast<JSArray*>(exec->uncheckedArgument(0));
1253     
1254     // This code assumes that neither array has set Symbol.isConcatSpreadable. If the first array
1255     // has indexed accessors then one of those accessors might change the value of Symbol.isConcatSpreadable
1256     // on the second argument.
1257     if (UNLIKELY(shouldUseSlowPut(firstArray->indexingType())))
1258         return JSValue::encode(jsNull());
1259
1260     // We need to check the species constructor here since checking it in the JS wrapper is too expensive for the non-optimizing tiers.
1261     bool isValid = speciesWatchpointIsValid(exec, firstArray);
1262     if (UNLIKELY(!isValid))
1263         return JSValue::encode(jsNull());
1264
1265     JSValue second = exec->uncheckedArgument(1);
1266     if (!isJSArray(second)) {
1267         scope.release();
1268         return concatAppendOne(exec, vm, firstArray, second);
1269     }
1270
1271     JSArray* secondArray = jsCast<JSArray*>(second);
1272     
1273     Butterfly* firstButterfly = firstArray->butterfly();
1274     Butterfly* secondButterfly = secondArray->butterfly();
1275
1276     unsigned firstArraySize = firstButterfly->publicLength();
1277     unsigned secondArraySize = secondButterfly->publicLength();
1278
1279     Checked<unsigned, RecordOverflow> checkedResultSize = firstArraySize;
1280     checkedResultSize += secondArraySize;
1281
1282     if (UNLIKELY(checkedResultSize.hasOverflowed())) {
1283         throwOutOfMemoryError(exec, scope);
1284         return encodedJSValue();
1285     }
1286
1287     unsigned resultSize = checkedResultSize.unsafeGet();
1288     IndexingType secondType = secondArray->indexingType();
1289     IndexingType type = firstArray->mergeIndexingTypeForCopying(secondType);
1290     if (type == NonArray || !firstArray->canFastCopy(vm, secondArray) || resultSize >= MIN_SPARSE_ARRAY_INDEX) {
1291         JSArray* result = constructEmptyArray(exec, nullptr, resultSize);
1292         RETURN_IF_EXCEPTION(scope, encodedJSValue());
1293
1294         bool success = moveElements(exec, vm, result, 0, firstArray, firstArraySize);
1295         ASSERT(!scope.exception() == success);
1296         if (UNLIKELY(!success))
1297             return encodedJSValue();
1298         success = moveElements(exec, vm, result, firstArraySize, secondArray, secondArraySize);
1299         ASSERT(!scope.exception() == success);
1300         if (UNLIKELY(!success))
1301             return encodedJSValue();
1302
1303         return JSValue::encode(result);
1304     }
1305
1306     Structure* resultStructure = exec->lexicalGlobalObject()->arrayStructureForIndexingTypeDuringAllocation(type);
1307     JSArray* result = JSArray::tryCreateForInitializationPrivate(vm, resultStructure, resultSize);
1308     if (UNLIKELY(!result)) {
1309         throwOutOfMemoryError(exec, scope);
1310         return encodedJSValue();
1311     }
1312     
1313     if (type == ArrayWithDouble) {
1314         double* buffer = result->butterfly()->contiguousDouble().data();
1315         memcpy(buffer, firstButterfly->contiguousDouble().data(), sizeof(JSValue) * firstArraySize);
1316         memcpy(buffer + firstArraySize, secondButterfly->contiguousDouble().data(), sizeof(JSValue) * secondArraySize);
1317     } else if (type != ArrayWithUndecided) {
1318         WriteBarrier<Unknown>* buffer = result->butterfly()->contiguous().data();
1319         memcpy(buffer, firstButterfly->contiguous().data(), sizeof(JSValue) * firstArraySize);
1320         if (secondType != ArrayWithUndecided)
1321             memcpy(buffer + firstArraySize, secondButterfly->contiguous().data(), sizeof(JSValue) * secondArraySize);
1322         else {
1323             for (unsigned i = secondArraySize; i--;)
1324                 buffer[i + firstArraySize].clear();
1325         }
1326     }
1327
1328     result->butterfly()->setPublicLength(resultSize);
1329     return JSValue::encode(result);
1330 }
1331
1332 EncodedJSValue JSC_HOST_CALL arrayProtoPrivateFuncAppendMemcpy(ExecState* exec)
1333 {
1334     ASSERT(exec->argumentCount() == 3);
1335
1336     VM& vm = exec->vm();
1337     auto scope = DECLARE_THROW_SCOPE(vm);
1338     JSArray* resultArray = jsCast<JSArray*>(exec->uncheckedArgument(0));
1339     JSArray* otherArray = jsCast<JSArray*>(exec->uncheckedArgument(1));
1340     JSValue startValue = exec->uncheckedArgument(2);
1341     ASSERT(startValue.isAnyInt() && startValue.asAnyInt() >= 0 && startValue.asAnyInt() <= std::numeric_limits<unsigned>::max());
1342     unsigned startIndex = static_cast<unsigned>(startValue.asAnyInt());
1343     bool success = resultArray->appendMemcpy(exec, vm, startIndex, otherArray);
1344     ASSERT(!success || !scope.exception());
1345     if (!success) {
1346         RETURN_IF_EXCEPTION(scope, encodedJSValue());
1347         moveElements(exec, vm, resultArray, startIndex, otherArray, otherArray->length());
1348     }
1349     return JSValue::encode(jsUndefined());
1350 }
1351
1352
1353 // -------------------- ArrayPrototype.constructor Watchpoint ------------------
1354
1355 static bool verbose = false;
1356
1357 class ArrayPrototypeAdaptiveInferredPropertyWatchpoint : public AdaptiveInferredPropertyValueWatchpointBase {
1358 public:
1359     typedef AdaptiveInferredPropertyValueWatchpointBase Base;
1360     ArrayPrototypeAdaptiveInferredPropertyWatchpoint(const ObjectPropertyCondition&, ArrayPrototype*);
1361
1362 private:
1363     void handleFire(const FireDetail&) override;
1364
1365     ArrayPrototype* m_arrayPrototype;
1366 };
1367
1368 void ArrayPrototype::tryInitializeSpeciesWatchpoint(ExecState* exec)
1369 {
1370     VM& vm = exec->vm();
1371
1372     RELEASE_ASSERT(!m_constructorWatchpoint);
1373     RELEASE_ASSERT(!m_constructorSpeciesWatchpoint);
1374
1375     auto scope = DECLARE_THROW_SCOPE(vm);
1376
1377     if (verbose)
1378         dataLog("Initializing Array species watchpoints for Array.prototype: ", pointerDump(this), " with structure: ", pointerDump(this->structure()), "\nand Array: ", pointerDump(this->globalObject()->arrayConstructor()), " with structure: ", pointerDump(this->globalObject()->arrayConstructor()->structure()), "\n");
1379     // First we need to make sure that the Array.prototype.constructor property points to Array
1380     // and that Array[Symbol.species] is the primordial GetterSetter.
1381
1382     // We only initialize once so flattening the structures does not have any real cost.
1383     Structure* prototypeStructure = this->structure(vm);
1384     if (prototypeStructure->isDictionary())
1385         prototypeStructure = prototypeStructure->flattenDictionaryStructure(vm, this);
1386     RELEASE_ASSERT(!prototypeStructure->isDictionary());
1387
1388     JSGlobalObject* globalObject = this->globalObject();
1389     ArrayConstructor* arrayConstructor = globalObject->arrayConstructor();
1390
1391     auto invalidateWatchpoint = [&] {
1392         globalObject->arraySpeciesWatchpoint().invalidate(vm, StringFireDetail("Was not able to set up array species watchpoint."));
1393     };
1394
1395     PropertySlot constructorSlot(this, PropertySlot::InternalMethodType::VMInquiry);
1396     this->getOwnPropertySlot(this, exec, vm.propertyNames->constructor, constructorSlot);
1397     ASSERT_UNUSED(scope, !scope.exception());
1398     if (constructorSlot.slotBase() != this
1399         || !constructorSlot.isCacheableValue()
1400         || constructorSlot.getValue(exec, vm.propertyNames->constructor) != arrayConstructor) {
1401         invalidateWatchpoint();
1402         return;
1403     }
1404
1405     Structure* constructorStructure = arrayConstructor->structure(vm);
1406     if (constructorStructure->isDictionary())
1407         constructorStructure = constructorStructure->flattenDictionaryStructure(vm, arrayConstructor);
1408
1409     PropertySlot speciesSlot(arrayConstructor, PropertySlot::InternalMethodType::VMInquiry);
1410     arrayConstructor->getOwnPropertySlot(arrayConstructor, exec, vm.propertyNames->speciesSymbol, speciesSlot);
1411     ASSERT_UNUSED(scope, !scope.exception());
1412     if (speciesSlot.slotBase() != arrayConstructor
1413         || !speciesSlot.isCacheableGetter()
1414         || speciesSlot.getterSetter() != globalObject->speciesGetterSetter()) {
1415         invalidateWatchpoint();
1416         return;
1417     }
1418
1419     // Now we need to setup the watchpoints to make sure these conditions remain valid.
1420     prototypeStructure->startWatchingPropertyForReplacements(vm, constructorSlot.cachedOffset());
1421     constructorStructure->startWatchingPropertyForReplacements(vm, speciesSlot.cachedOffset());
1422
1423     ObjectPropertyCondition constructorCondition = ObjectPropertyCondition::equivalence(vm, this, this, vm.propertyNames->constructor.impl(), arrayConstructor);
1424     ObjectPropertyCondition speciesCondition = ObjectPropertyCondition::equivalence(vm, this, arrayConstructor, vm.propertyNames->speciesSymbol.impl(), globalObject->speciesGetterSetter());
1425
1426     if (!constructorCondition.isWatchable() || !speciesCondition.isWatchable()) {
1427         invalidateWatchpoint();
1428         return;
1429     }
1430
1431     m_constructorWatchpoint = std::make_unique<ArrayPrototypeAdaptiveInferredPropertyWatchpoint>(constructorCondition, this);
1432     m_constructorWatchpoint->install();
1433
1434     m_constructorSpeciesWatchpoint = std::make_unique<ArrayPrototypeAdaptiveInferredPropertyWatchpoint>(speciesCondition, this);
1435     m_constructorSpeciesWatchpoint->install();
1436
1437     // We only watch this from the DFG, and the DFG makes sure to only start watching if the watchpoint is in the IsWatched state.
1438     RELEASE_ASSERT(!globalObject->arraySpeciesWatchpoint().isBeingWatched()); 
1439     globalObject->arraySpeciesWatchpoint().touch(vm, "Set up array species watchpoint.");
1440 }
1441
1442 ArrayPrototypeAdaptiveInferredPropertyWatchpoint::ArrayPrototypeAdaptiveInferredPropertyWatchpoint(const ObjectPropertyCondition& key, ArrayPrototype* prototype)
1443     : Base(key)
1444     , m_arrayPrototype(prototype)
1445 {
1446 }
1447
1448 void ArrayPrototypeAdaptiveInferredPropertyWatchpoint::handleFire(const FireDetail& detail)
1449 {
1450     StringPrintStream out;
1451     out.print("ArrayPrototype adaption of ", key(), " failed: ", detail);
1452
1453     StringFireDetail stringDetail(out.toCString().data());
1454
1455     if (verbose)
1456         WTF::dataLog(stringDetail, "\n");
1457
1458     JSGlobalObject* globalObject = m_arrayPrototype->globalObject();
1459     globalObject->arraySpeciesWatchpoint().fireAll(globalObject->vm(), stringDetail);
1460 }
1461
1462 } // namespace JSC