ec6542d209853d3f8d16b4e443508f1f8878e36d
[WebKit-https.git] / Source / JavaScriptCore / runtime / ArrayPrototype.cpp
1 /*
2  *  Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
3  *  Copyright (C) 2003, 2007-2009, 2011, 2013, 2015-2016 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(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_FUNCTION_WITHOUT_TRANSITION(vm.propertyNames->slice, arrayProtoFuncSlice, DontEnum, 2);
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     if (JSValue result = object->tryGetIndexQuickly(index))
153         return result;
154     // We want to perform get and has in the same operation.
155     // We can only do so when this behavior is not observable. The
156     // only time it is observable is when we encounter an opaque objects (ProxyObject and JSModuleNamespaceObject)
157     // somewhere in the prototype chain.
158     PropertySlot slot(object, PropertySlot::InternalMethodType::HasProperty);
159     if (!object->getPropertySlot(exec, index, slot))
160         return JSValue();
161     if (UNLIKELY(slot.isTaintedByOpaqueObject()))
162         return object->get(exec, index);
163     return slot.getValue(exec, index);
164 }
165
166 static ALWAYS_INLINE void putLength(ExecState* exec, JSObject* obj, JSValue value)
167 {
168     PutPropertySlot slot(obj);
169     obj->methodTable()->put(obj, exec, exec->propertyNames().length, value, slot);
170 }
171
172 static ALWAYS_INLINE void setLength(ExecState* exec, JSObject* obj, unsigned value)
173 {
174     if (isJSArray(obj))
175         jsCast<JSArray*>(obj)->setLength(exec, value);
176     putLength(exec, obj, jsNumber(value));
177 }
178
179 inline bool speciesWatchpointsValid(ExecState* exec, JSObject* thisObject)
180 {
181     ArrayPrototype* arrayPrototype = thisObject->globalObject()->arrayPrototype();
182     ArrayPrototype::SpeciesWatchpointStatus status = arrayPrototype->speciesWatchpointStatus();
183     if (UNLIKELY(status == ArrayPrototype::SpeciesWatchpointStatus::Uninitialized))
184         status = arrayPrototype->attemptToInitializeSpeciesWatchpoint(exec);
185     ASSERT(status != ArrayPrototype::SpeciesWatchpointStatus::Uninitialized);
186     return !thisObject->hasCustomProperties()
187         && arrayPrototype == thisObject->getPrototypeDirect()
188         && status == ArrayPrototype::SpeciesWatchpointStatus::Initialized;
189 }
190
191 enum class SpeciesConstructResult {
192     FastPath,
193     Exception,
194     CreatedObject
195 };
196
197 static ALWAYS_INLINE std::pair<SpeciesConstructResult, JSObject*> speciesConstructArray(ExecState* exec, JSObject* thisObject, unsigned length)
198 {
199     VM& vm = exec->vm();
200     auto scope = DECLARE_THROW_SCOPE(vm);
201
202     auto exceptionResult = [] () {
203         return std::make_pair(SpeciesConstructResult::Exception, nullptr);
204     };
205
206     // ECMA 9.4.2.3: https://tc39.github.io/ecma262/#sec-arrayspeciescreate
207     JSValue constructor = jsUndefined();
208     if (LIKELY(isArray(exec, thisObject))) {
209         // Fast path in the normal case where the user has not set an own constructor and the Array.prototype.constructor is normal.
210         // We need prototype check for subclasses of Array, which are Array objects but have a different prototype by default.
211         if (LIKELY(speciesWatchpointsValid(exec, thisObject)))
212             return std::make_pair(SpeciesConstructResult::FastPath, nullptr);
213
214         constructor = thisObject->get(exec, exec->propertyNames().constructor);
215         RETURN_IF_EXCEPTION(scope, exceptionResult());
216         if (constructor.isConstructor()) {
217             JSObject* constructorObject = jsCast<JSObject*>(constructor);
218             if (exec->lexicalGlobalObject() != constructorObject->globalObject())
219                 return std::make_pair(SpeciesConstructResult::FastPath, nullptr);;
220         }
221         if (constructor.isObject()) {
222             constructor = constructor.get(exec, exec->propertyNames().speciesSymbol);
223             RETURN_IF_EXCEPTION(scope, exceptionResult());
224             if (constructor.isNull())
225                 return std::make_pair(SpeciesConstructResult::FastPath, nullptr);;
226         }
227     } else
228         RETURN_IF_EXCEPTION(scope, exceptionResult());
229
230     if (constructor.isUndefined())
231         return std::make_pair(SpeciesConstructResult::FastPath, nullptr);
232
233     MarkedArgumentBuffer args;
234     args.append(jsNumber(length));
235     JSObject* newObject = construct(exec, constructor, args, "Species construction did not get a valid constructor");
236     RETURN_IF_EXCEPTION(scope, exceptionResult());
237     return std::make_pair(SpeciesConstructResult::CreatedObject, newObject);
238 }
239
240 static inline unsigned argumentClampedIndexFromStartOrEnd(ExecState* exec, int argument, unsigned length, unsigned undefinedValue = 0)
241 {
242     JSValue value = exec->argument(argument);
243     if (value.isUndefined())
244         return undefinedValue;
245
246     double indexDouble = value.toInteger(exec);
247     if (indexDouble < 0) {
248         indexDouble += length;
249         return indexDouble < 0 ? 0 : static_cast<unsigned>(indexDouble);
250     }
251     return indexDouble > length ? length : static_cast<unsigned>(indexDouble);
252 }
253
254 // The shift/unshift function implement the shift/unshift behaviour required
255 // by the corresponding array prototype methods, and by splice. In both cases,
256 // the methods are operating an an array or array like object.
257 //
258 //  header  currentCount  (remainder)
259 // [------][------------][-----------]
260 //  header  resultCount  (remainder)
261 // [------][-----------][-----------]
262 //
263 // The set of properties in the range 'header' must be unchanged. The set of
264 // properties in the range 'remainder' (where remainder = length - header -
265 // currentCount) will be shifted to the left or right as appropriate; in the
266 // case of shift this must be removing values, in the case of unshift this
267 // must be introducing new values.
268
269 template<JSArray::ShiftCountMode shiftCountMode>
270 void shift(ExecState* exec, JSObject* thisObj, unsigned header, unsigned currentCount, unsigned resultCount, unsigned length)
271 {
272     VM& vm = exec->vm();
273     auto scope = DECLARE_THROW_SCOPE(vm);
274
275     RELEASE_ASSERT(currentCount > resultCount);
276     unsigned count = currentCount - resultCount;
277
278     RELEASE_ASSERT(header <= length);
279     RELEASE_ASSERT(currentCount <= (length - header));
280
281     if (isJSArray(thisObj)) {
282         JSArray* array = asArray(thisObj);
283         if (array->length() == length && array->shiftCount<shiftCountMode>(exec, header, count))
284             return;
285     }
286
287     for (unsigned k = header; k < length - currentCount; ++k) {
288         unsigned from = k + currentCount;
289         unsigned to = k + resultCount;
290         if (JSValue value = getProperty(exec, thisObj, from)) {
291             RETURN_IF_EXCEPTION(scope, void());
292             thisObj->putByIndexInline(exec, to, value, true);
293             RETURN_IF_EXCEPTION(scope, void());
294         } else if (!thisObj->methodTable(vm)->deletePropertyByIndex(thisObj, exec, to)) {
295             throwTypeError(exec, scope, ASCIILiteral("Unable to delete property."));
296             return;
297         }
298     }
299     for (unsigned k = length; k > length - count; --k) {
300         if (!thisObj->methodTable(vm)->deletePropertyByIndex(thisObj, exec, k - 1)) {
301             throwTypeError(exec, scope, ASCIILiteral("Unable to delete property."));
302             return;
303         }
304     }
305 }
306
307 template<JSArray::ShiftCountMode shiftCountMode>
308 void unshift(ExecState* exec, JSObject* thisObj, unsigned header, unsigned currentCount, unsigned resultCount, unsigned length)
309 {
310     VM& vm = exec->vm();
311     auto scope = DECLARE_THROW_SCOPE(vm);
312
313     RELEASE_ASSERT(resultCount > currentCount);
314     unsigned count = resultCount - currentCount;
315
316     RELEASE_ASSERT(header <= length);
317     RELEASE_ASSERT(currentCount <= (length - header));
318
319     // Guard against overflow.
320     if (count > (UINT_MAX - length)) {
321         throwOutOfMemoryError(exec, scope);
322         return;
323     }
324
325     if (isJSArray(thisObj)) {
326         JSArray* array = asArray(thisObj);
327         if (array->length() == length && array->unshiftCount<shiftCountMode>(exec, header, count))
328             return;
329     }
330
331     for (unsigned k = length - currentCount; k > header; --k) {
332         unsigned from = k + currentCount - 1;
333         unsigned to = k + resultCount - 1;
334         if (JSValue value = getProperty(exec, thisObj, from)) {
335             RETURN_IF_EXCEPTION(scope, void());
336             thisObj->putByIndexInline(exec, to, value, true);
337         } else if (!thisObj->methodTable(vm)->deletePropertyByIndex(thisObj, exec, to)) {
338             throwTypeError(exec, scope, ASCIILiteral("Unable to delete property."));
339             return;
340         }
341         RETURN_IF_EXCEPTION(scope, void());
342     }
343 }
344
345 EncodedJSValue JSC_HOST_CALL arrayProtoFuncToString(ExecState* exec)
346 {
347     VM& vm = exec->vm();
348     auto scope = DECLARE_THROW_SCOPE(vm);
349     JSValue thisValue = exec->thisValue().toThis(exec, StrictMode);
350
351     // 1. Let array be the result of calling ToObject on the this value.
352     JSObject* thisObject = thisValue.toObject(exec);
353     RETURN_IF_EXCEPTION(scope, encodedJSValue());
354     
355     // 2. Let func be the result of calling the [[Get]] internal method of array with argument "join".
356     JSValue function = JSValue(thisObject).get(exec, exec->propertyNames().join);
357     RETURN_IF_EXCEPTION(scope, encodedJSValue());
358
359     // 3. If IsCallable(func) is false, then let func be the standard built-in method Object.prototype.toString (15.2.4.2).
360     bool customJoinCase = false;
361     if (!function.isCell())
362         customJoinCase = true;
363     CallData callData;
364     CallType callType = getCallData(function, callData);
365     if (callType == CallType::None)
366         customJoinCase = true;
367
368     if (UNLIKELY(customJoinCase))
369         return JSValue::encode(jsMakeNontrivialString(exec, "[object ", thisObject->methodTable(vm)->className(thisObject), "]"));
370
371     // 4. Return the result of calling the [[Call]] internal method of func providing array as the this value and an empty arguments list.
372     if (!isJSArray(thisObject) || callType != CallType::Host || callData.native.function != arrayProtoFuncJoin)
373         return JSValue::encode(call(exec, function, callType, callData, thisObject, exec->emptyList()));
374
375     ASSERT(isJSArray(thisValue));
376     JSArray* thisArray = asArray(thisValue);
377
378     unsigned length = thisArray->length();
379
380     StringRecursionChecker checker(exec, thisArray);
381     if (JSValue earlyReturnValue = checker.earlyReturnValue())
382         return JSValue::encode(earlyReturnValue);
383
384     JSStringJoiner joiner(*exec, ',', length);
385     RETURN_IF_EXCEPTION(scope, encodedJSValue());
386
387     for (unsigned i = 0; i < length; ++i) {
388         JSValue element = thisArray->tryGetIndexQuickly(i);
389         if (!element) {
390             element = thisArray->get(exec, i);
391             RETURN_IF_EXCEPTION(scope, encodedJSValue());
392         }
393         joiner.append(*exec, element);
394         RETURN_IF_EXCEPTION(scope, encodedJSValue());
395     }
396
397     return JSValue::encode(joiner.join(*exec));
398 }
399
400 EncodedJSValue JSC_HOST_CALL arrayProtoFuncToLocaleString(ExecState* exec)
401 {
402     VM& vm = exec->vm();
403     auto scope = DECLARE_THROW_SCOPE(vm);
404     JSValue thisValue = exec->thisValue().toThis(exec, StrictMode);
405
406     JSObject* thisObject = thisValue.toObject(exec);
407     RETURN_IF_EXCEPTION(scope, encodedJSValue());
408
409     unsigned length = getLength(exec, thisObject);
410     RETURN_IF_EXCEPTION(scope, encodedJSValue());
411
412     StringRecursionChecker checker(exec, thisObject);
413     if (JSValue earlyReturnValue = checker.earlyReturnValue())
414         return JSValue::encode(earlyReturnValue);
415
416     JSStringJoiner stringJoiner(*exec, ',', length);
417     RETURN_IF_EXCEPTION(scope, encodedJSValue());
418
419 #if ENABLE(INTL)
420     ArgList arguments(exec);
421     for (unsigned i = 0; i < length; ++i) {
422         JSValue element = thisObject->getIndex(exec, i);
423         RETURN_IF_EXCEPTION(scope, encodedJSValue());
424         if (element.isUndefinedOrNull())
425             element = jsEmptyString(exec);
426         else {
427             JSValue conversionFunction = element.get(exec, exec->propertyNames().toLocaleString);
428             RETURN_IF_EXCEPTION(scope, encodedJSValue());
429             CallData callData;
430             CallType callType = getCallData(conversionFunction, callData);
431             if (callType != CallType::None) {
432                 element = call(exec, conversionFunction, callType, callData, element, arguments);
433                 RETURN_IF_EXCEPTION(scope, encodedJSValue());
434             }
435         }
436         stringJoiner.append(*exec, element);
437         RETURN_IF_EXCEPTION(scope, encodedJSValue());
438     }
439 #else // !ENABLE(INTL)
440     for (unsigned i = 0; i < length; ++i) {
441         JSValue element = thisObject->getIndex(exec, i);
442         RETURN_IF_EXCEPTION(scope, encodedJSValue());
443         if (element.isUndefinedOrNull())
444             continue;
445         JSValue conversionFunction = element.get(exec, exec->propertyNames().toLocaleString);
446         RETURN_IF_EXCEPTION(scope, encodedJSValue());
447         CallData callData;
448         CallType callType = getCallData(conversionFunction, callData);
449         if (callType != CallType::None) {
450             element = call(exec, conversionFunction, callType, callData, element, exec->emptyList());
451             RETURN_IF_EXCEPTION(scope, encodedJSValue());
452         }
453         stringJoiner.append(*exec, element);
454         RETURN_IF_EXCEPTION(scope, encodedJSValue());
455     }
456 #endif // !ENABLE(INTL)
457
458     return JSValue::encode(stringJoiner.join(*exec));
459 }
460
461 static inline bool isHole(double value)
462 {
463     return std::isnan(value);
464 }
465
466 static inline bool isHole(const WriteBarrier<Unknown>& value)
467 {
468     return !value;
469 }
470
471 template<typename T> static inline bool containsHole(T* data, unsigned length)
472 {
473     for (unsigned i = 0; i < length; ++i) {
474         if (isHole(data[i]))
475             return true;
476     }
477     return false;
478 }
479
480 static inline bool holesMustForwardToPrototype(ExecState& state, JSObject* object)
481 {
482     auto& vm = state.vm();
483     return object->structure(vm)->holesMustForwardToPrototype(vm);
484 }
485
486 static JSValue slowJoin(ExecState& exec, JSObject* thisObject, JSString* separator, uint64_t length)
487 {
488     VM& vm = exec.vm();
489     auto scope = DECLARE_THROW_SCOPE(vm);
490
491     // 5. If len is zero, return the empty String.
492     if (!length)
493         return jsEmptyString(&exec);
494
495     // 6. Let element0 be Get(O, "0").
496     JSValue element0 = thisObject->getIndex(&exec, 0);
497     RETURN_IF_EXCEPTION(scope, JSValue());
498
499     // 7. If element0 is undefined or null, let R be the empty String; otherwise, let R be ? ToString(element0).
500     JSString* r = nullptr;
501     if (element0.isUndefinedOrNull())
502         r = jsEmptyString(&exec);
503     else
504         r = element0.toString(&exec);
505     RETURN_IF_EXCEPTION(scope, JSValue());
506
507     // 8. Let k be 1.
508     // 9. Repeat, while k < len
509     // 9.e Increase k by 1..
510     for (uint64_t k = 1; k < length; ++k) {
511         // b. Let element be ? Get(O, ! ToString(k)).
512         JSValue element = thisObject->get(&exec, Identifier::fromString(&exec, AtomicString::number(k)));
513         RETURN_IF_EXCEPTION(scope, JSValue());
514
515         // c. If element is undefined or null, let next be the empty String; otherwise, let next be ? ToString(element).
516         JSString* next = nullptr;
517         if (element.isUndefinedOrNull()) {
518             if (!separator->length())
519                 continue;
520             next = jsEmptyString(&exec);
521         } else
522             next = element.toString(&exec);
523         RETURN_IF_EXCEPTION(scope, JSValue());
524
525         // a. Let S be the String value produced by concatenating R and sep.
526         // d. Let R be a String value produced by concatenating S and next.
527         r = jsString(&exec, r, separator, next);
528         RETURN_IF_EXCEPTION(scope, JSValue());
529     }
530     // 10. Return R.
531     return r;
532 }
533
534 static inline bool canUseFastJoin(const JSObject* thisObject)
535 {
536     switch (thisObject->indexingType()) {
537     case ALL_CONTIGUOUS_INDEXING_TYPES:
538     case ALL_INT32_INDEXING_TYPES:
539     case ALL_DOUBLE_INDEXING_TYPES:
540         return true;
541     default:
542         break;
543     }
544     return false;
545 }
546
547 static inline JSValue fastJoin(ExecState& state, JSObject* thisObject, StringView separator, unsigned length)
548 {
549     VM& vm = state.vm();
550     auto scope = DECLARE_THROW_SCOPE(vm);
551
552     switch (thisObject->indexingType()) {
553     case ALL_CONTIGUOUS_INDEXING_TYPES:
554     case ALL_INT32_INDEXING_TYPES: {
555         auto& butterfly = *thisObject->butterfly();
556         if (length > butterfly.publicLength())
557             break;
558         JSStringJoiner joiner(state, separator, length);
559         RETURN_IF_EXCEPTION(scope, JSValue());
560         auto data = butterfly.contiguous().data();
561         bool holesKnownToBeOK = false;
562         for (unsigned i = 0; i < length; ++i) {
563             if (JSValue value = data[i].get()) {
564                 if (!joiner.appendWithoutSideEffects(state, value))
565                     goto generalCase;
566             } else {
567                 if (!holesKnownToBeOK) {
568                     if (holesMustForwardToPrototype(state, thisObject))
569                         goto generalCase;
570                     holesKnownToBeOK = true;
571                 }
572                 joiner.appendEmptyString();
573             }
574         }
575         return joiner.join(state);
576     }
577     case ALL_DOUBLE_INDEXING_TYPES: {
578         auto& butterfly = *thisObject->butterfly();
579         if (length > butterfly.publicLength())
580             break;
581         JSStringJoiner joiner(state, separator, length);
582         RETURN_IF_EXCEPTION(scope, JSValue());
583         auto data = butterfly.contiguousDouble().data();
584         bool holesKnownToBeOK = false;
585         for (unsigned i = 0; i < length; ++i) {
586             double value = data[i];
587             if (!isHole(value))
588                 joiner.append(state, jsDoubleNumber(value));
589             else {
590                 if (!holesKnownToBeOK) {
591                     if (thisObject->structure(vm)->holesMustForwardToPrototype(vm))
592                         goto generalCase;
593                     holesKnownToBeOK = true;
594                 }
595                 joiner.appendEmptyString();
596             }
597         }
598         return joiner.join(state);
599     }
600     }
601
602 generalCase:
603     JSStringJoiner joiner(state, separator, length);
604     RETURN_IF_EXCEPTION(scope, JSValue());
605     for (unsigned i = 0; i < length; ++i) {
606         JSValue element = thisObject->getIndex(&state, i);
607         RETURN_IF_EXCEPTION(scope, JSValue());
608         joiner.append(state, element);
609         RETURN_IF_EXCEPTION(scope, JSValue());
610     }
611     return joiner.join(state);
612 }
613
614 EncodedJSValue JSC_HOST_CALL arrayProtoFuncJoin(ExecState* exec)
615 {
616     VM& vm = exec->vm();
617     auto scope = DECLARE_THROW_SCOPE(vm);
618
619     // 1. Let O be ? ToObject(this value).
620     JSObject* thisObject = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
621     if (!thisObject)
622         return JSValue::encode(JSValue());
623
624     StringRecursionChecker checker(exec, thisObject);
625     if (JSValue earlyReturnValue = checker.earlyReturnValue())
626         return JSValue::encode(earlyReturnValue);
627
628     // 2. Let len be ? ToLength(? Get(O, "length")).
629     double length = toLength(exec, thisObject);
630     RETURN_IF_EXCEPTION(scope, encodedJSValue());
631
632     // 3. If separator is undefined, let separator be the single-element String ",".
633     JSValue separatorValue = exec->argument(0);
634     if (separatorValue.isUndefined()) {
635         const LChar comma = ',';
636
637         if (UNLIKELY(length > std::numeric_limits<unsigned>::max() || !canUseFastJoin(thisObject))) {
638             uint64_t length64 = static_cast<uint64_t>(length);
639             ASSERT(static_cast<double>(length64) == length);
640             JSString* jsSeparator = jsSingleCharacterString(exec, comma);
641             RETURN_IF_EXCEPTION(scope, encodedJSValue());
642
643             return JSValue::encode(slowJoin(*exec, thisObject, jsSeparator, length64));
644         }
645
646         unsigned unsignedLength = static_cast<unsigned>(length);
647         ASSERT(static_cast<double>(unsignedLength) == length);
648         return JSValue::encode(fastJoin(*exec, thisObject, { &comma, 1 }, unsignedLength));
649     }
650
651     // 4. Let sep be ? ToString(separator).
652     JSString* jsSeparator = separatorValue.toString(exec);
653     RETURN_IF_EXCEPTION(scope, encodedJSValue());
654
655     if (UNLIKELY(length > std::numeric_limits<unsigned>::max() || !canUseFastJoin(thisObject))) {
656         uint64_t length64 = static_cast<uint64_t>(length);
657         ASSERT(static_cast<double>(length64) == length);
658         return JSValue::encode(slowJoin(*exec, thisObject, jsSeparator, length64));
659     }
660
661     return JSValue::encode(fastJoin(*exec, thisObject, jsSeparator->view(exec).get(), length));
662 }
663
664 EncodedJSValue JSC_HOST_CALL arrayProtoFuncPop(ExecState* exec)
665 {
666     VM& vm = exec->vm();
667     auto scope = DECLARE_THROW_SCOPE(vm);
668
669     JSValue thisValue = exec->thisValue().toThis(exec, StrictMode);
670
671     if (isJSArray(thisValue))
672         return JSValue::encode(asArray(thisValue)->pop(exec));
673
674     JSObject* thisObj = thisValue.toObject(exec);
675     if (!thisObj)
676         return JSValue::encode(JSValue());
677     unsigned length = getLength(exec, thisObj);
678     RETURN_IF_EXCEPTION(scope, encodedJSValue());
679
680     JSValue result;
681     if (length == 0) {
682         putLength(exec, thisObj, jsNumber(length));
683         result = jsUndefined();
684     } else {
685         result = thisObj->get(exec, length - 1);
686         RETURN_IF_EXCEPTION(scope, encodedJSValue());
687         if (!thisObj->methodTable(vm)->deletePropertyByIndex(thisObj, exec, length - 1)) {
688             throwTypeError(exec, scope, ASCIILiteral("Unable to delete property."));
689             return JSValue::encode(jsUndefined());
690         }
691         putLength(exec, thisObj, jsNumber(length - 1));
692     }
693     return JSValue::encode(result);
694 }
695
696 EncodedJSValue JSC_HOST_CALL arrayProtoFuncPush(ExecState* exec)
697 {
698     VM& vm = exec->vm();
699     auto scope = DECLARE_THROW_SCOPE(vm);
700     JSValue thisValue = exec->thisValue().toThis(exec, StrictMode);
701
702     if (isJSArray(thisValue) && exec->argumentCount() == 1) {
703         JSArray* array = asArray(thisValue);
704         array->push(exec, exec->uncheckedArgument(0));
705         return JSValue::encode(jsNumber(array->length()));
706     }
707     
708     JSObject* thisObj = thisValue.toObject(exec);
709     if (!thisObj)
710         return JSValue::encode(JSValue());
711     unsigned length = getLength(exec, thisObj);
712     RETURN_IF_EXCEPTION(scope, encodedJSValue());
713
714     for (unsigned n = 0; n < exec->argumentCount(); n++) {
715         // Check for integer overflow; where safe we can do a fast put by index.
716         if (length + n >= length)
717             thisObj->methodTable()->putByIndex(thisObj, exec, length + n, exec->uncheckedArgument(n), true);
718         else {
719             PutPropertySlot slot(thisObj);
720             Identifier propertyName = Identifier::fromString(exec, JSValue(static_cast<int64_t>(length) + static_cast<int64_t>(n)).toWTFString(exec));
721             thisObj->methodTable()->put(thisObj, exec, propertyName, exec->uncheckedArgument(n), slot);
722         }
723         RETURN_IF_EXCEPTION(scope, encodedJSValue());
724     }
725     
726     JSValue newLength(static_cast<int64_t>(length) + static_cast<int64_t>(exec->argumentCount()));
727     putLength(exec, thisObj, newLength);
728     return JSValue::encode(newLength);
729 }
730
731 EncodedJSValue JSC_HOST_CALL arrayProtoFuncReverse(ExecState* exec)
732 {
733     VM& vm = exec->vm();
734     auto scope = DECLARE_THROW_SCOPE(vm);
735
736     JSObject* thisObject = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
737     if (!thisObject)
738         return JSValue::encode(JSValue());
739
740     unsigned length = getLength(exec, thisObject);
741     RETURN_IF_EXCEPTION(scope, encodedJSValue());
742
743     switch (thisObject->indexingType()) {
744     case ALL_CONTIGUOUS_INDEXING_TYPES:
745     case ALL_INT32_INDEXING_TYPES: {
746         auto& butterfly = *thisObject->butterfly();
747         if (length > butterfly.publicLength())
748             break;
749         auto data = butterfly.contiguous().data();
750         if (containsHole(data, length) && holesMustForwardToPrototype(*exec, thisObject))
751             break;
752         std::reverse(data, data + length);
753         return JSValue::encode(thisObject);
754     }
755     case ALL_DOUBLE_INDEXING_TYPES: {
756         auto& butterfly = *thisObject->butterfly();
757         if (length > butterfly.publicLength())
758             break;
759         auto data = butterfly.contiguousDouble().data();
760         if (containsHole(data, length) && holesMustForwardToPrototype(*exec, thisObject))
761             break;
762         std::reverse(data, data + length);
763         return JSValue::encode(thisObject);
764     }
765     case ALL_ARRAY_STORAGE_INDEXING_TYPES: {
766         auto& storage = *thisObject->butterfly()->arrayStorage();
767         if (length > storage.vectorLength())
768             break;
769         if (storage.hasHoles() && holesMustForwardToPrototype(*exec, thisObject))
770             break;
771         auto data = storage.vector().data();
772         std::reverse(data, data + length);
773         return JSValue::encode(thisObject);
774     }
775     }
776
777     unsigned middle = length / 2;
778     for (unsigned lower = 0; lower < middle; lower++) {
779         unsigned upper = length - lower - 1;
780         bool lowerExists = thisObject->hasProperty(exec, lower);
781         RETURN_IF_EXCEPTION(scope, encodedJSValue());
782         JSValue lowerValue;
783         if (lowerExists) {
784             lowerValue = thisObject->get(exec, lower);
785             RETURN_IF_EXCEPTION(scope, encodedJSValue());
786         }
787
788         bool upperExists = thisObject->hasProperty(exec, upper);
789         RETURN_IF_EXCEPTION(scope, encodedJSValue());
790         JSValue upperValue;
791         if (upperExists) {
792             upperValue = thisObject->get(exec, upper);
793             RETURN_IF_EXCEPTION(scope, encodedJSValue());
794         }
795
796         if (upperExists) {
797             thisObject->putByIndexInline(exec, lower, upperValue, true);
798             RETURN_IF_EXCEPTION(scope, encodedJSValue());
799         } else if (!thisObject->methodTable(vm)->deletePropertyByIndex(thisObject, exec, lower)) {
800             if (!scope.exception())
801                 throwTypeError(exec, scope, ASCIILiteral("Unable to delete property."));
802             return JSValue::encode(JSValue());
803         }
804
805         if (lowerExists) {
806             thisObject->putByIndexInline(exec, upper, lowerValue, true);
807             RETURN_IF_EXCEPTION(scope, encodedJSValue());
808         } else if (!thisObject->methodTable(vm)->deletePropertyByIndex(thisObject, exec, upper)) {
809             if (!scope.exception())
810                 throwTypeError(exec, scope, ASCIILiteral("Unable to delete property."));
811             return JSValue::encode(JSValue());
812         }
813     }
814     return JSValue::encode(thisObject);
815 }
816
817 EncodedJSValue JSC_HOST_CALL arrayProtoFuncShift(ExecState* exec)
818 {
819     VM& vm = exec->vm();
820     auto scope = DECLARE_THROW_SCOPE(vm);
821     JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
822     if (!thisObj)
823         return JSValue::encode(JSValue());
824     unsigned length = getLength(exec, thisObj);
825     RETURN_IF_EXCEPTION(scope, encodedJSValue());
826
827     JSValue result;
828     if (length == 0) {
829         putLength(exec, thisObj, jsNumber(length));
830         result = jsUndefined();
831     } else {
832         result = thisObj->getIndex(exec, 0);
833         shift<JSArray::ShiftCountForShift>(exec, thisObj, 0, 1, 0, length);
834         RETURN_IF_EXCEPTION(scope, encodedJSValue());
835         putLength(exec, thisObj, jsNumber(length - 1));
836     }
837     return JSValue::encode(result);
838 }
839
840 EncodedJSValue JSC_HOST_CALL arrayProtoFuncSlice(ExecState* exec)
841 {
842     // http://developer.netscape.com/docs/manuals/js/client/jsref/array.htm#1193713 or 15.4.4.10
843     VM& vm = exec->vm();
844     auto scope = DECLARE_THROW_SCOPE(vm);
845     JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
846     if (!thisObj)
847         return JSValue::encode(JSValue());
848     unsigned length = getLength(exec, thisObj);
849     RETURN_IF_EXCEPTION(scope, encodedJSValue());
850
851     unsigned begin = argumentClampedIndexFromStartOrEnd(exec, 0, length);
852     unsigned end = argumentClampedIndexFromStartOrEnd(exec, 1, length, length);
853
854     std::pair<SpeciesConstructResult, JSObject*> speciesResult = speciesConstructArray(exec, thisObj, end - begin);
855     // We can only get an exception if we call some user function.
856     if (UNLIKELY(speciesResult.first == SpeciesConstructResult::Exception))
857         return JSValue::encode(jsUndefined());
858
859     if (LIKELY(speciesResult.first == SpeciesConstructResult::FastPath && isJSArray(thisObj) && length == getLength(exec, thisObj))) {
860         if (JSArray* result = asArray(thisObj)->fastSlice(*exec, begin, end - begin))
861             return JSValue::encode(result);
862     }
863
864     JSObject* result;
865     if (speciesResult.first == SpeciesConstructResult::CreatedObject)
866         result = speciesResult.second;
867     else {
868         result = constructEmptyArray(exec, nullptr, end - begin);
869         RETURN_IF_EXCEPTION(scope, encodedJSValue());
870     }
871
872     unsigned n = 0;
873     for (unsigned k = begin; k < end; k++, n++) {
874         JSValue v = getProperty(exec, thisObj, k);
875         RETURN_IF_EXCEPTION(scope, encodedJSValue());
876         if (v)
877             result->putDirectIndex(exec, n, v);
878     }
879     setLength(exec, result, n);
880     return JSValue::encode(result);
881 }
882
883 EncodedJSValue JSC_HOST_CALL arrayProtoFuncSplice(ExecState* exec)
884 {
885     // 15.4.4.12
886
887     VM& vm = exec->vm();
888     auto scope = DECLARE_THROW_SCOPE(vm);
889
890     JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
891     if (!thisObj)
892         return JSValue::encode(JSValue());
893     unsigned length = getLength(exec, thisObj);
894     RETURN_IF_EXCEPTION(scope, encodedJSValue());
895
896     if (!exec->argumentCount()) {
897         std::pair<SpeciesConstructResult, JSObject*> speciesResult = speciesConstructArray(exec, thisObj, 0);
898         if (speciesResult.first == SpeciesConstructResult::Exception)
899             return JSValue::encode(jsUndefined());
900
901         JSObject* result;
902         if (speciesResult.first == SpeciesConstructResult::CreatedObject)
903             result = speciesResult.second;
904         else {
905             result = constructEmptyArray(exec, nullptr);
906             RETURN_IF_EXCEPTION(scope, encodedJSValue());
907         }
908
909         setLength(exec, result, 0);
910         setLength(exec, thisObj, length);
911         return JSValue::encode(result);
912     }
913
914     unsigned begin = argumentClampedIndexFromStartOrEnd(exec, 0, length);
915
916     unsigned deleteCount = length - begin;
917     if (exec->argumentCount() > 1) {
918         double deleteDouble = exec->uncheckedArgument(1).toInteger(exec);
919         if (deleteDouble < 0)
920             deleteCount = 0;
921         else if (deleteDouble > length - begin)
922             deleteCount = length - begin;
923         else
924             deleteCount = static_cast<unsigned>(deleteDouble);
925     }
926
927     std::pair<SpeciesConstructResult, JSObject*> speciesResult = speciesConstructArray(exec, thisObj, deleteCount);
928     if (speciesResult.first == SpeciesConstructResult::Exception)
929         return JSValue::encode(jsUndefined());
930
931     JSObject* result = nullptr;
932     if (speciesResult.first == SpeciesConstructResult::FastPath && isJSArray(thisObj) && length == getLength(exec, thisObj))
933         result = asArray(thisObj)->fastSlice(*exec, begin, deleteCount);
934
935     if (!result) {
936         if (speciesResult.first == SpeciesConstructResult::CreatedObject) {
937             result = speciesResult.second;
938             
939             for (unsigned k = 0; k < deleteCount; ++k) {
940                 JSValue v = getProperty(exec, thisObj, k + begin);
941                 RETURN_IF_EXCEPTION(scope, encodedJSValue());
942                 if (UNLIKELY(!v))
943                     continue;
944                 result->putByIndexInline(exec, k, v, true);
945                 RETURN_IF_EXCEPTION(scope, encodedJSValue());
946             }
947         } else {
948             result = JSArray::tryCreateUninitialized(vm, exec->lexicalGlobalObject()->arrayStructureForIndexingTypeDuringAllocation(ArrayWithUndecided), deleteCount);
949             if (!result)
950                 return JSValue::encode(throwOutOfMemoryError(exec, scope));
951             
952             for (unsigned k = 0; k < deleteCount; ++k) {
953                 JSValue v = getProperty(exec, thisObj, k + begin);
954                 RETURN_IF_EXCEPTION(scope, encodedJSValue());
955                 if (UNLIKELY(!v))
956                     continue;
957                 result->initializeIndex(vm, k, v);
958             }
959         }
960     }
961
962     unsigned additionalArgs = std::max<int>(exec->argumentCount() - 2, 0);
963     if (additionalArgs < deleteCount) {
964         shift<JSArray::ShiftCountForSplice>(exec, thisObj, begin, deleteCount, additionalArgs, length);
965         RETURN_IF_EXCEPTION(scope, encodedJSValue());
966     } else if (additionalArgs > deleteCount) {
967         unshift<JSArray::ShiftCountForSplice>(exec, thisObj, begin, deleteCount, additionalArgs, length);
968         RETURN_IF_EXCEPTION(scope, encodedJSValue());
969     }
970     for (unsigned k = 0; k < additionalArgs; ++k) {
971         thisObj->putByIndexInline(exec, k + begin, exec->uncheckedArgument(k + 2), true);
972         RETURN_IF_EXCEPTION(scope, encodedJSValue());
973     }
974     
975     setLength(exec, thisObj, length - deleteCount + additionalArgs);
976     return JSValue::encode(result);
977 }
978
979 EncodedJSValue JSC_HOST_CALL arrayProtoFuncUnShift(ExecState* exec)
980 {
981     VM& vm = exec->vm();
982     auto scope = DECLARE_THROW_SCOPE(vm);
983     // 15.4.4.13
984
985     JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
986     if (!thisObj)
987         return JSValue::encode(JSValue());
988     unsigned length = getLength(exec, thisObj);
989     RETURN_IF_EXCEPTION(scope, encodedJSValue());
990
991     unsigned nrArgs = exec->argumentCount();
992     if (nrArgs) {
993         unshift<JSArray::ShiftCountForShift>(exec, thisObj, 0, 0, nrArgs, length);
994         RETURN_IF_EXCEPTION(scope, encodedJSValue());
995     }
996     for (unsigned k = 0; k < nrArgs; ++k) {
997         thisObj->putByIndexInline(exec, k, exec->uncheckedArgument(k), true);
998         RETURN_IF_EXCEPTION(scope, encodedJSValue());
999     }
1000     JSValue result = jsNumber(length + nrArgs);
1001     putLength(exec, thisObj, result);
1002     return JSValue::encode(result);
1003 }
1004
1005 EncodedJSValue JSC_HOST_CALL arrayProtoFuncIndexOf(ExecState* exec)
1006 {
1007     VM& vm = exec->vm();
1008     auto scope = DECLARE_THROW_SCOPE(vm);
1009
1010     // 15.4.4.14
1011     JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
1012     if (!thisObj)
1013         return JSValue::encode(JSValue());
1014     unsigned length = getLength(exec, thisObj);
1015     RETURN_IF_EXCEPTION(scope, encodedJSValue());
1016
1017     unsigned index = argumentClampedIndexFromStartOrEnd(exec, 1, length);
1018     JSValue searchElement = exec->argument(0);
1019     for (; index < length; ++index) {
1020         JSValue e = getProperty(exec, thisObj, index);
1021         RETURN_IF_EXCEPTION(scope, encodedJSValue());
1022         if (!e)
1023             continue;
1024         if (JSValue::strictEqual(exec, searchElement, e))
1025             return JSValue::encode(jsNumber(index));
1026         RETURN_IF_EXCEPTION(scope, encodedJSValue());
1027     }
1028
1029     return JSValue::encode(jsNumber(-1));
1030 }
1031
1032 EncodedJSValue JSC_HOST_CALL arrayProtoFuncLastIndexOf(ExecState* exec)
1033 {
1034     VM& vm = exec->vm();
1035     auto scope = DECLARE_THROW_SCOPE(vm);
1036
1037     // 15.4.4.15
1038     JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
1039     if (!thisObj)
1040         return JSValue::encode(JSValue());
1041     unsigned length = getLength(exec, thisObj);
1042     if (!length)
1043         return JSValue::encode(jsNumber(-1));
1044
1045     unsigned index = length - 1;
1046     if (exec->argumentCount() >= 2) {
1047         JSValue fromValue = exec->uncheckedArgument(1);
1048         double fromDouble = fromValue.toInteger(exec);
1049         if (fromDouble < 0) {
1050             fromDouble += length;
1051             if (fromDouble < 0)
1052                 return JSValue::encode(jsNumber(-1));
1053         }
1054         if (fromDouble < length)
1055             index = static_cast<unsigned>(fromDouble);
1056     }
1057
1058     JSValue searchElement = exec->argument(0);
1059     do {
1060         RELEASE_ASSERT(index < length);
1061         JSValue e = getProperty(exec, thisObj, index);
1062         RETURN_IF_EXCEPTION(scope, encodedJSValue());
1063         if (!e)
1064             continue;
1065         if (JSValue::strictEqual(exec, searchElement, e))
1066             return JSValue::encode(jsNumber(index));
1067         RETURN_IF_EXCEPTION(scope, encodedJSValue());
1068     } while (index--);
1069
1070     return JSValue::encode(jsNumber(-1));
1071 }
1072
1073 static bool moveElements(ExecState* exec, VM& vm, JSArray* target, unsigned targetOffset, JSArray* source, unsigned sourceLength)
1074 {
1075     auto scope = DECLARE_THROW_SCOPE(vm);
1076
1077     if (LIKELY(!hasAnyArrayStorage(source->indexingType()) && !source->structure()->holesMustForwardToPrototype(vm))) {
1078         for (unsigned i = 0; i < sourceLength; ++i) {
1079             JSValue value = source->tryGetIndexQuickly(i);
1080             if (value) {
1081                 target->putDirectIndex(exec, targetOffset + i, value);
1082                 RETURN_IF_EXCEPTION(scope, false);
1083             }
1084         }
1085     } else {
1086         for (unsigned i = 0; i < sourceLength; ++i) {
1087             JSValue value = getProperty(exec, source, i);
1088             RETURN_IF_EXCEPTION(scope, false);
1089             if (value) {
1090                 target->putDirectIndex(exec, targetOffset + i, value);
1091                 RETURN_IF_EXCEPTION(scope, false);
1092             }
1093         }
1094     }
1095     return true;
1096 }
1097
1098 static EncodedJSValue concatAppendOne(ExecState* exec, VM& vm, JSArray* first, JSValue second)
1099 {
1100     auto scope = DECLARE_THROW_SCOPE(vm);
1101
1102     ASSERT(!isJSArray(second));
1103     ASSERT(!shouldUseSlowPut(first->indexingType()));
1104     Butterfly* firstButterfly = first->butterfly();
1105     unsigned firstArraySize = firstButterfly->publicLength();
1106
1107     IndexingType type = first->mergeIndexingTypeForCopying(indexingTypeForValue(second) | IsArray);
1108     
1109     if (type == NonArray)
1110         type = first->indexingType();
1111
1112     Structure* resultStructure = exec->lexicalGlobalObject()->arrayStructureForIndexingTypeDuringAllocation(type);
1113     JSArray* result = JSArray::create(vm, resultStructure, firstArraySize + 1);
1114     if (!result)
1115         return JSValue::encode(throwOutOfMemoryError(exec, scope));
1116
1117     if (!result->appendMemcpy(exec, vm, 0, first)) {
1118         if (!moveElements(exec, vm, result, 0, first, firstArraySize)) {
1119             ASSERT(scope.exception());
1120             return JSValue::encode(JSValue());
1121         }
1122     }
1123
1124     result->putDirectIndex(exec, firstArraySize, second);
1125     return JSValue::encode(result);
1126
1127 }
1128
1129
1130 EncodedJSValue JSC_HOST_CALL arrayProtoPrivateFuncConcatMemcpy(ExecState* exec)
1131 {
1132     ASSERT(exec->argumentCount() == 2);
1133     VM& vm = exec->vm();
1134     auto scope = DECLARE_THROW_SCOPE(vm);
1135
1136     JSArray* firstArray = jsCast<JSArray*>(exec->uncheckedArgument(0));
1137     
1138     // This code assumes that neither array has set Symbol.isConcatSpreadable. If the first array
1139     // has indexed accessors then one of those accessors might change the value of Symbol.isConcatSpreadable
1140     // on the second argument.
1141     if (UNLIKELY(shouldUseSlowPut(firstArray->indexingType())))
1142         return JSValue::encode(jsNull());
1143
1144     // We need to check the species constructor here since checking it in the JS wrapper is too expensive for the non-optimizing tiers.
1145     if (UNLIKELY(!speciesWatchpointsValid(exec, firstArray)))
1146         return JSValue::encode(jsNull());
1147
1148     JSValue second = exec->uncheckedArgument(1);
1149     if (!isJSArray(second))
1150         return concatAppendOne(exec, vm, firstArray, second);
1151
1152     JSArray* secondArray = jsCast<JSArray*>(second);
1153     
1154     Butterfly* firstButterfly = firstArray->butterfly();
1155     Butterfly* secondButterfly = secondArray->butterfly();
1156
1157     unsigned firstArraySize = firstButterfly->publicLength();
1158     unsigned secondArraySize = secondButterfly->publicLength();
1159
1160     IndexingType secondType = secondArray->indexingType();
1161     IndexingType type = firstArray->mergeIndexingTypeForCopying(secondType);
1162     if (type == NonArray || !firstArray->canFastCopy(vm, secondArray) || firstArraySize + secondArraySize >= MIN_SPARSE_ARRAY_INDEX) {
1163         JSArray* result = constructEmptyArray(exec, nullptr, firstArraySize + secondArraySize);
1164         RETURN_IF_EXCEPTION(scope, encodedJSValue());
1165
1166         if (!moveElements(exec, vm, result, 0, firstArray, firstArraySize)
1167             || !moveElements(exec, vm, result, firstArraySize, secondArray, secondArraySize)) {
1168             ASSERT(scope.exception());
1169             return JSValue::encode(JSValue());
1170         }
1171
1172         return JSValue::encode(result);
1173     }
1174
1175     Structure* resultStructure = exec->lexicalGlobalObject()->arrayStructureForIndexingTypeDuringAllocation(type);
1176     JSArray* result = JSArray::tryCreateUninitialized(vm, resultStructure, firstArraySize + secondArraySize);
1177     if (!result)
1178         return JSValue::encode(throwOutOfMemoryError(exec, scope));
1179     
1180     if (type == ArrayWithDouble) {
1181         double* buffer = result->butterfly()->contiguousDouble().data();
1182         memcpy(buffer, firstButterfly->contiguousDouble().data(), sizeof(JSValue) * firstArraySize);
1183         memcpy(buffer + firstArraySize, secondButterfly->contiguousDouble().data(), sizeof(JSValue) * secondArraySize);
1184     } else if (type != ArrayWithUndecided) {
1185         WriteBarrier<Unknown>* buffer = result->butterfly()->contiguous().data();
1186         memcpy(buffer, firstButterfly->contiguous().data(), sizeof(JSValue) * firstArraySize);
1187         if (secondType != ArrayWithUndecided)
1188             memcpy(buffer + firstArraySize, secondButterfly->contiguous().data(), sizeof(JSValue) * secondArraySize);
1189         else {
1190             for (unsigned i = secondArraySize; i--;)
1191                 buffer[i + firstArraySize].clear();
1192         }
1193     }
1194
1195     result->butterfly()->setPublicLength(firstArraySize + secondArraySize);
1196     return JSValue::encode(result);
1197 }
1198
1199 EncodedJSValue JSC_HOST_CALL arrayProtoPrivateFuncAppendMemcpy(ExecState* exec)
1200 {
1201     ASSERT(exec->argumentCount() == 3);
1202
1203     VM& vm = exec->vm();
1204     JSArray* resultArray = jsCast<JSArray*>(exec->uncheckedArgument(0));
1205     JSArray* otherArray = jsCast<JSArray*>(exec->uncheckedArgument(1));
1206     JSValue startValue = exec->uncheckedArgument(2);
1207     ASSERT(startValue.isAnyInt() && startValue.asAnyInt() >= 0 && startValue.asAnyInt() <= std::numeric_limits<unsigned>::max());
1208     unsigned startIndex = static_cast<unsigned>(startValue.asAnyInt());
1209     if (!resultArray->appendMemcpy(exec, vm, startIndex, otherArray))
1210         moveElements(exec, vm, resultArray, startIndex, otherArray, otherArray->length());
1211
1212     return JSValue::encode(jsUndefined());
1213 }
1214
1215
1216 // -------------------- ArrayPrototype.constructor Watchpoint ------------------
1217
1218 static bool verbose = false;
1219
1220 class ArrayPrototypeAdaptiveInferredPropertyWatchpoint : public AdaptiveInferredPropertyValueWatchpointBase {
1221 public:
1222     typedef AdaptiveInferredPropertyValueWatchpointBase Base;
1223     ArrayPrototypeAdaptiveInferredPropertyWatchpoint(const ObjectPropertyCondition&, ArrayPrototype*);
1224
1225 private:
1226     void handleFire(const FireDetail&) override;
1227
1228     ArrayPrototype* m_arrayPrototype;
1229 };
1230
1231 ArrayPrototype::SpeciesWatchpointStatus ArrayPrototype::attemptToInitializeSpeciesWatchpoint(ExecState* exec)
1232 {
1233     ASSERT(m_speciesWatchpointStatus == SpeciesWatchpointStatus::Uninitialized);
1234
1235     VM& vm = exec->vm();
1236
1237     if (verbose)
1238         dataLog("Attempting to initialize 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");
1239     // First we need to make sure that the Array.prototype.constructor property points to Array
1240     // and that Array[Symbol.species] is the primordial GetterSetter.
1241
1242     // We only initialize once so flattening the structures does not have any real cost.
1243     Structure* prototypeStructure = this->structure(vm);
1244     if (prototypeStructure->isDictionary())
1245         prototypeStructure = prototypeStructure->flattenDictionaryStructure(vm, this);
1246     RELEASE_ASSERT(!prototypeStructure->isDictionary());
1247
1248     JSGlobalObject* globalObject = this->globalObject();
1249     ArrayConstructor* arrayConstructor = globalObject->arrayConstructor();
1250
1251     PropertySlot constructorSlot(this, PropertySlot::InternalMethodType::VMInquiry);
1252     JSValue(this).get(exec, vm.propertyNames->constructor, constructorSlot);
1253     if (constructorSlot.slotBase() != this
1254         || !constructorSlot.isCacheableValue()
1255         || constructorSlot.getValue(exec, vm.propertyNames->constructor) != arrayConstructor)
1256         return m_speciesWatchpointStatus = SpeciesWatchpointStatus::Fired;
1257
1258     Structure* constructorStructure = arrayConstructor->structure(vm);
1259     if (constructorStructure->isDictionary())
1260         constructorStructure = constructorStructure->flattenDictionaryStructure(vm, arrayConstructor);
1261
1262     PropertySlot speciesSlot(arrayConstructor, PropertySlot::InternalMethodType::VMInquiry);
1263     JSValue(arrayConstructor).get(exec, vm.propertyNames->speciesSymbol, speciesSlot);
1264     if (speciesSlot.slotBase() != arrayConstructor
1265         || !speciesSlot.isCacheableGetter()
1266         || speciesSlot.getterSetter() != globalObject->speciesGetterSetter())
1267         return m_speciesWatchpointStatus = SpeciesWatchpointStatus::Fired;
1268
1269     // Now we need to setup the watchpoints to make sure these conditions remain valid.
1270     prototypeStructure->startWatchingPropertyForReplacements(vm, constructorSlot.cachedOffset());
1271     constructorStructure->startWatchingPropertyForReplacements(vm, speciesSlot.cachedOffset());
1272
1273     ObjectPropertyCondition constructorCondition = ObjectPropertyCondition::equivalence(vm, this, this, vm.propertyNames->constructor.impl(), arrayConstructor);
1274     ObjectPropertyCondition speciesCondition = ObjectPropertyCondition::equivalence(vm, this, arrayConstructor, vm.propertyNames->speciesSymbol.impl(), globalObject->speciesGetterSetter());
1275
1276     if (!constructorCondition.isWatchable() || !speciesCondition.isWatchable())
1277         return m_speciesWatchpointStatus = SpeciesWatchpointStatus::Fired;
1278
1279     m_constructorWatchpoint = std::make_unique<ArrayPrototypeAdaptiveInferredPropertyWatchpoint>(constructorCondition, this);
1280     m_constructorWatchpoint->install();
1281
1282     m_constructorSpeciesWatchpoint = std::make_unique<ArrayPrototypeAdaptiveInferredPropertyWatchpoint>(speciesCondition, this);
1283     m_constructorSpeciesWatchpoint->install();
1284
1285     return m_speciesWatchpointStatus = SpeciesWatchpointStatus::Initialized;
1286 }
1287
1288 ArrayPrototypeAdaptiveInferredPropertyWatchpoint::ArrayPrototypeAdaptiveInferredPropertyWatchpoint(const ObjectPropertyCondition& key, ArrayPrototype* prototype)
1289     : Base(key)
1290     , m_arrayPrototype(prototype)
1291 {
1292 }
1293
1294 void ArrayPrototypeAdaptiveInferredPropertyWatchpoint::handleFire(const FireDetail& detail)
1295 {
1296     StringPrintStream out;
1297     out.print("ArrayPrototype adaption of ", key(), " failed: ", detail);
1298
1299     StringFireDetail stringDetail(out.toCString().data());
1300
1301     if (verbose)
1302         WTF::dataLog(stringDetail, "\n");
1303
1304     m_arrayPrototype->m_speciesWatchpointStatus = ArrayPrototype::SpeciesWatchpointStatus::Fired;
1305 }
1306
1307 } // namespace JSC