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