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