Array.concat should be fast for integer or double arrays
[WebKit-https.git] / Source / JavaScriptCore / runtime / ArrayPrototype.cpp
1 /*
2  *  Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
3  *  Copyright (C) 2003, 2007, 2008, 2009, 2011, 2013, 2015 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 "ButterflyInlines.h"
28 #include "CachedCall.h"
29 #include "CodeBlock.h"
30 #include "CopiedSpaceInlines.h"
31 #include "Error.h"
32 #include "Interpreter.h"
33 #include "JIT.h"
34 #include "JSArrayIterator.h"
35 #include "JSCBuiltins.h"
36 #include "JSCInlines.h"
37 #include "JSStringBuilder.h"
38 #include "JSStringJoiner.h"
39 #include "Lookup.h"
40 #include "ObjectConstructor.h"
41 #include "ObjectPrototype.h"
42 #include "StringRecursionChecker.h"
43 #include <algorithm>
44 #include <wtf/Assertions.h>
45 #include <wtf/HashSet.h>
46
47 namespace JSC {
48
49 EncodedJSValue JSC_HOST_CALL arrayProtoFuncToString(ExecState*);
50 EncodedJSValue JSC_HOST_CALL arrayProtoFuncToLocaleString(ExecState*);
51 EncodedJSValue JSC_HOST_CALL arrayProtoFuncConcat(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 arrayProtoFuncReduce(ExecState*);
62 EncodedJSValue JSC_HOST_CALL arrayProtoFuncReduceRight(ExecState*);
63 EncodedJSValue JSC_HOST_CALL arrayProtoFuncLastIndexOf(ExecState*);
64 EncodedJSValue JSC_HOST_CALL arrayProtoFuncKeys(ExecState*);
65 EncodedJSValue JSC_HOST_CALL arrayProtoFuncEntries(ExecState*);
66
67 // ------------------------------ ArrayPrototype ----------------------------
68
69 const ClassInfo ArrayPrototype::s_info = {"Array", &JSArray::s_info, nullptr, CREATE_METHOD_TABLE(ArrayPrototype)};
70
71 ArrayPrototype* ArrayPrototype::create(VM& vm, JSGlobalObject* globalObject, Structure* structure)
72 {
73     ArrayPrototype* prototype = new (NotNull, allocateCell<ArrayPrototype>(vm.heap)) ArrayPrototype(vm, structure);
74     prototype->finishCreation(vm, globalObject);
75     return prototype;
76 }
77
78 // ECMA 15.4.4
79 ArrayPrototype::ArrayPrototype(VM& vm, Structure* structure)
80     : JSArray(vm, structure, 0)
81 {
82 }
83
84 void ArrayPrototype::finishCreation(VM& vm, JSGlobalObject* globalObject)
85 {
86     Base::finishCreation(vm);
87     ASSERT(inherits(info()));
88     vm.prototypeMap.addPrototype(this);
89
90     putDirectWithoutTransition(vm, vm.propertyNames->values, globalObject->arrayProtoValuesFunction(), DontEnum);
91     putDirectWithoutTransition(vm, vm.propertyNames->iteratorSymbol, globalObject->arrayProtoValuesFunction(), DontEnum);
92     
93     JSC_NATIVE_FUNCTION(vm.propertyNames->toString, arrayProtoFuncToString, DontEnum, 0);
94     JSC_NATIVE_FUNCTION(vm.propertyNames->toLocaleString, arrayProtoFuncToLocaleString, DontEnum, 0);
95     JSC_NATIVE_FUNCTION("concat", arrayProtoFuncConcat, DontEnum, 1);
96     JSC_BUILTIN_FUNCTION("fill", arrayPrototypeFillCodeGenerator, DontEnum);
97     JSC_NATIVE_FUNCTION(vm.propertyNames->join, arrayProtoFuncJoin, DontEnum, 1);
98     JSC_NATIVE_INTRINSIC_FUNCTION("pop", arrayProtoFuncPop, DontEnum, 0, ArrayPopIntrinsic);
99     JSC_NATIVE_INTRINSIC_FUNCTION("push", arrayProtoFuncPush, DontEnum, 1, ArrayPushIntrinsic);
100     JSC_NATIVE_FUNCTION("reverse", arrayProtoFuncReverse, DontEnum, 0);
101     JSC_NATIVE_FUNCTION("shift", arrayProtoFuncShift, DontEnum, 0);
102     JSC_NATIVE_FUNCTION(vm.propertyNames->slice, arrayProtoFuncSlice, DontEnum, 2);
103     JSC_BUILTIN_FUNCTION("sort", arrayPrototypeSortCodeGenerator, DontEnum);
104     JSC_NATIVE_FUNCTION("splice", arrayProtoFuncSplice, DontEnum, 2);
105     JSC_NATIVE_FUNCTION("unshift", arrayProtoFuncUnShift, DontEnum, 1);
106     JSC_BUILTIN_FUNCTION("every", arrayPrototypeEveryCodeGenerator, DontEnum);
107     JSC_BUILTIN_FUNCTION("forEach", arrayPrototypeForEachCodeGenerator, DontEnum);
108     JSC_BUILTIN_FUNCTION("some", arrayPrototypeSomeCodeGenerator, DontEnum);
109     JSC_NATIVE_FUNCTION("indexOf", arrayProtoFuncIndexOf, DontEnum, 1);
110     JSC_NATIVE_FUNCTION("lastIndexOf", arrayProtoFuncLastIndexOf, DontEnum, 1);
111     JSC_BUILTIN_FUNCTION("filter", arrayPrototypeFilterCodeGenerator, DontEnum);
112     JSC_BUILTIN_FUNCTION("reduce", arrayPrototypeReduceCodeGenerator, DontEnum);
113     JSC_BUILTIN_FUNCTION("reduceRight", arrayPrototypeReduceRightCodeGenerator, DontEnum);
114     JSC_BUILTIN_FUNCTION("map", arrayPrototypeMapCodeGenerator, DontEnum);
115     JSC_NATIVE_FUNCTION(vm.propertyNames->entries, arrayProtoFuncEntries, DontEnum, 0);
116     JSC_NATIVE_FUNCTION(vm.propertyNames->keys, arrayProtoFuncKeys, DontEnum, 0);
117     JSC_BUILTIN_FUNCTION("find", arrayPrototypeFindCodeGenerator, DontEnum);
118     JSC_BUILTIN_FUNCTION("findIndex", arrayPrototypeFindIndexCodeGenerator, DontEnum);
119     JSC_BUILTIN_FUNCTION("includes", arrayPrototypeIncludesCodeGenerator, DontEnum);
120     JSC_BUILTIN_FUNCTION("copyWithin", arrayPrototypeCopyWithinCodeGenerator, DontEnum);
121     
122     if (!globalObject->runtimeFlags().isSymbolDisabled()) {
123         JSObject* unscopables = constructEmptyObject(globalObject->globalExec(), globalObject->nullPrototypeObjectStructure());
124         const char* unscopableNames[] = {
125             "copyWithin",
126             "entries",
127             "fill",
128             "find",
129             "findIndex",
130             "keys",
131             "values"
132         };
133         for (const char* unscopableName : unscopableNames)
134             unscopables->putDirect(vm, Identifier::fromString(&vm, unscopableName), jsBoolean(true));
135         putDirectWithoutTransition(vm, vm.propertyNames->unscopablesSymbol, unscopables, DontEnum | ReadOnly);
136     }
137 }
138
139 // ------------------------------ Array Functions ----------------------------
140
141 static ALWAYS_INLINE JSValue getProperty(ExecState* exec, JSObject* object, unsigned index)
142 {
143     if (JSValue result = object->tryGetIndexQuickly(index))
144         return result;
145     PropertySlot slot(object);
146     if (!object->getPropertySlot(exec, index, slot))
147         return JSValue();
148     return slot.getValue(exec, index);
149 }
150
151 static ALWAYS_INLINE unsigned getLength(ExecState* exec, JSObject* obj)
152 {
153     if (isJSArray(obj))
154         return jsCast<JSArray*>(obj)->length();
155     return obj->get(exec, exec->propertyNames().length).toUInt32(exec);
156 }
157
158 static void putLength(ExecState* exec, JSObject* obj, JSValue value)
159 {
160     PutPropertySlot slot(obj);
161     obj->methodTable()->put(obj, exec, exec->propertyNames().length, value, slot);
162 }
163
164 static inline unsigned argumentClampedIndexFromStartOrEnd(ExecState* exec, int argument, unsigned length, unsigned undefinedValue = 0)
165 {
166     JSValue value = exec->argument(argument);
167     if (value.isUndefined())
168         return undefinedValue;
169
170     double indexDouble = value.toInteger(exec);
171     if (indexDouble < 0) {
172         indexDouble += length;
173         return indexDouble < 0 ? 0 : static_cast<unsigned>(indexDouble);
174     }
175     return indexDouble > length ? length : static_cast<unsigned>(indexDouble);
176 }
177
178 // The shift/unshift function implement the shift/unshift behaviour required
179 // by the corresponding array prototype methods, and by splice. In both cases,
180 // the methods are operating an an array or array like object.
181 //
182 //  header  currentCount  (remainder)
183 // [------][------------][-----------]
184 //  header  resultCount  (remainder)
185 // [------][-----------][-----------]
186 //
187 // The set of properties in the range 'header' must be unchanged. The set of
188 // properties in the range 'remainder' (where remainder = length - header -
189 // currentCount) will be shifted to the left or right as appropriate; in the
190 // case of shift this must be removing values, in the case of unshift this
191 // must be introducing new values.
192
193 template<JSArray::ShiftCountMode shiftCountMode>
194 void shift(ExecState* exec, JSObject* thisObj, unsigned header, unsigned currentCount, unsigned resultCount, unsigned length)
195 {
196     RELEASE_ASSERT(currentCount > resultCount);
197     unsigned count = currentCount - resultCount;
198
199     RELEASE_ASSERT(header <= length);
200     RELEASE_ASSERT(currentCount <= (length - header));
201
202     if (isJSArray(thisObj)) {
203         JSArray* array = asArray(thisObj);
204         if (array->length() == length && array->shiftCount<shiftCountMode>(exec, header, count))
205             return;
206     }
207
208     for (unsigned k = header; k < length - currentCount; ++k) {
209         unsigned from = k + currentCount;
210         unsigned to = k + resultCount;
211         if (JSValue value = getProperty(exec, thisObj, from)) {
212             if (exec->hadException())
213                 return;
214             thisObj->putByIndexInline(exec, to, value, true);
215             if (exec->hadException())
216                 return;
217         } else if (!thisObj->methodTable(exec->vm())->deletePropertyByIndex(thisObj, exec, to)) {
218             throwTypeError(exec, ASCIILiteral("Unable to delete property."));
219             return;
220         }
221     }
222     for (unsigned k = length; k > length - count; --k) {
223         if (!thisObj->methodTable(exec->vm())->deletePropertyByIndex(thisObj, exec, k - 1)) {
224             throwTypeError(exec, ASCIILiteral("Unable to delete property."));
225             return;
226         }
227     }
228 }
229
230 template<JSArray::ShiftCountMode shiftCountMode>
231 void unshift(ExecState* exec, JSObject* thisObj, unsigned header, unsigned currentCount, unsigned resultCount, unsigned length)
232 {
233     RELEASE_ASSERT(resultCount > currentCount);
234     unsigned count = resultCount - currentCount;
235
236     RELEASE_ASSERT(header <= length);
237     RELEASE_ASSERT(currentCount <= (length - header));
238
239     // Guard against overflow.
240     if (count > (UINT_MAX - length)) {
241         throwOutOfMemoryError(exec);
242         return;
243     }
244
245     if (isJSArray(thisObj)) {
246         JSArray* array = asArray(thisObj);
247         if (array->length() == length && array->unshiftCount<shiftCountMode>(exec, header, count))
248             return;
249     }
250
251     for (unsigned k = length - currentCount; k > header; --k) {
252         unsigned from = k + currentCount - 1;
253         unsigned to = k + resultCount - 1;
254         if (JSValue value = getProperty(exec, thisObj, from)) {
255             if (exec->hadException())
256                 return;
257             thisObj->putByIndexInline(exec, to, value, true);
258         } else if (!thisObj->methodTable(exec->vm())->deletePropertyByIndex(thisObj, exec, to)) {
259             throwTypeError(exec, ASCIILiteral("Unable to delete property."));
260             return;
261         }
262         if (exec->hadException())
263             return;
264     }
265 }
266
267 EncodedJSValue JSC_HOST_CALL arrayProtoFuncToString(ExecState* exec)
268 {
269     JSValue thisValue = exec->thisValue().toThis(exec, StrictMode);
270
271     // 1. Let array be the result of calling ToObject on the this value.
272     JSObject* thisObject = thisValue.toObject(exec);
273     if (exec->hadException())
274         return JSValue::encode(jsUndefined());
275     
276     // 2. Let func be the result of calling the [[Get]] internal method of array with argument "join".
277     JSValue function = JSValue(thisObject).get(exec, exec->propertyNames().join);
278
279     // 3. If IsCallable(func) is false, then let func be the standard built-in method Object.prototype.toString (15.2.4.2).
280     if (!function.isCell())
281         return JSValue::encode(jsMakeNontrivialString(exec, "[object ", thisObject->methodTable(exec->vm())->className(thisObject), "]"));
282     CallData callData;
283     CallType callType = getCallData(function, callData);
284     if (callType == CallTypeNone)
285         return JSValue::encode(jsMakeNontrivialString(exec, "[object ", thisObject->methodTable(exec->vm())->className(thisObject), "]"));
286
287     // 4. Return the result of calling the [[Call]] internal method of func providing array as the this value and an empty arguments list.
288     if (!isJSArray(thisObject) || callType != CallTypeHost || callData.native.function != arrayProtoFuncJoin)
289         return JSValue::encode(call(exec, function, callType, callData, thisObject, exec->emptyList()));
290
291     ASSERT(isJSArray(thisValue));
292     JSArray* thisArray = asArray(thisValue);
293
294     unsigned length = thisArray->length();
295
296     StringRecursionChecker checker(exec, thisArray);
297     if (JSValue earlyReturnValue = checker.earlyReturnValue())
298         return JSValue::encode(earlyReturnValue);
299
300     JSStringJoiner joiner(*exec, ',', length);
301     if (exec->hadException())
302         return JSValue::encode(jsUndefined());
303
304     for (unsigned i = 0; i < length; ++i) {
305         JSValue element = thisArray->tryGetIndexQuickly(i);
306         if (!element) {
307             element = thisArray->get(exec, i);
308             if (exec->hadException())
309                 return JSValue::encode(jsUndefined());
310         }
311         joiner.append(*exec, element);
312         if (exec->hadException())
313             return JSValue::encode(jsUndefined());
314     }
315
316     return JSValue::encode(joiner.join(*exec));
317 }
318
319 EncodedJSValue JSC_HOST_CALL arrayProtoFuncToLocaleString(ExecState* exec)
320 {
321     JSValue thisValue = exec->thisValue().toThis(exec, StrictMode);
322
323     JSObject* thisObject = thisValue.toObject(exec);
324     if (exec->hadException())
325         return JSValue::encode(jsUndefined());
326
327     unsigned length = getLength(exec, thisObject);
328     if (exec->hadException())
329         return JSValue::encode(jsUndefined());
330
331     StringRecursionChecker checker(exec, thisObject);
332     if (JSValue earlyReturnValue = checker.earlyReturnValue())
333         return JSValue::encode(earlyReturnValue);
334
335     JSStringJoiner stringJoiner(*exec, ',', length);
336     if (exec->hadException())
337         return JSValue::encode(jsUndefined());
338
339     for (unsigned i = 0; i < length; ++i) {
340         JSValue element = thisObject->getIndex(exec, i);
341         if (exec->hadException())
342             return JSValue::encode(jsUndefined());
343         if (element.isUndefinedOrNull())
344             continue;
345         JSValue conversionFunction = element.get(exec, exec->propertyNames().toLocaleString);
346         if (exec->hadException())
347             return JSValue::encode(jsUndefined());
348         CallData callData;
349         CallType callType = getCallData(conversionFunction, callData);
350         if (callType != CallTypeNone) {
351             element = call(exec, conversionFunction, callType, callData, element, exec->emptyList());
352             if (exec->hadException())
353                 return JSValue::encode(jsUndefined());
354         }
355         stringJoiner.append(*exec, element);
356         if (exec->hadException())
357             return JSValue::encode(jsUndefined());
358     }
359
360     return JSValue::encode(stringJoiner.join(*exec));
361 }
362
363 static inline bool isHole(double value)
364 {
365     return std::isnan(value);
366 }
367
368 static inline bool isHole(const WriteBarrier<Unknown>& value)
369 {
370     return !value;
371 }
372
373 template<typename T> static inline bool containsHole(T* data, unsigned length)
374 {
375     for (unsigned i = 0; i < length; ++i) {
376         if (isHole(data[i]))
377             return true;
378     }
379     return false;
380 }
381
382 static inline bool holesMustForwardToPrototype(ExecState& state, JSObject* object)
383 {
384     auto& vm = state.vm();
385     return object->structure(vm)->holesMustForwardToPrototype(vm);
386 }
387
388 static inline JSValue join(ExecState& state, JSObject* thisObject, StringView separator)
389 {
390     unsigned length = getLength(&state, thisObject);
391     if (state.hadException())
392         return jsUndefined();
393
394     switch (thisObject->indexingType()) {
395     case ALL_CONTIGUOUS_INDEXING_TYPES:
396     case ALL_INT32_INDEXING_TYPES: {
397         auto& butterfly = *thisObject->butterfly();
398         if (length > butterfly.publicLength())
399             break;
400         JSStringJoiner joiner(state, separator, length);
401         if (state.hadException())
402             return jsUndefined();
403         auto data = butterfly.contiguous().data();
404         bool holesKnownToBeOK = false;
405         for (unsigned i = 0; i < length; ++i) {
406             if (JSValue value = data[i].get()) {
407                 joiner.append(state, value);
408                 if (state.hadException())
409                     return jsUndefined();
410             } else {
411                 if (!holesKnownToBeOK) {
412                     if (holesMustForwardToPrototype(state, thisObject))
413                         goto generalCase;
414                     holesKnownToBeOK = true;
415                 }
416                 joiner.appendEmptyString();
417             }
418         }
419         return joiner.join(state);
420     }
421     case ALL_DOUBLE_INDEXING_TYPES: {
422         auto& butterfly = *thisObject->butterfly();
423         if (length > butterfly.publicLength())
424             break;
425         JSStringJoiner joiner(state, separator, length);
426         if (state.hadException())
427             return jsUndefined();
428         auto data = butterfly.contiguousDouble().data();
429         bool holesKnownToBeOK = false;
430         for (unsigned i = 0; i < length; ++i) {
431             double value = data[i];
432             if (!isHole(value))
433                 joiner.append(state, jsDoubleNumber(value));
434             else {
435                 if (!holesKnownToBeOK) {
436                     if (thisObject->structure(state.vm())->holesMustForwardToPrototype(state.vm()))
437                         goto generalCase;
438                     holesKnownToBeOK = true;
439                 }
440                 joiner.appendEmptyString();
441             }
442         }
443         return joiner.join(state);
444     }
445     case ALL_ARRAY_STORAGE_INDEXING_TYPES: {
446         auto& storage = *thisObject->butterfly()->arrayStorage();
447         if (length > storage.vectorLength())
448             break;
449         if (storage.hasHoles() && thisObject->structure(state.vm())->holesMustForwardToPrototype(state.vm()))
450             break;
451         JSStringJoiner joiner(state, separator, length);
452         if (state.hadException())
453             return jsUndefined();
454         auto data = storage.vector().data();
455         for (unsigned i = 0; i < length; ++i) {
456             if (JSValue value = data[i].get()) {
457                 joiner.append(state, value);
458                 if (state.hadException())
459                     return jsUndefined();
460             } else
461                 joiner.appendEmptyString();
462         }
463         return joiner.join(state);
464     }
465     }
466
467 generalCase:
468     JSStringJoiner joiner(state, separator, length);
469     if (state.hadException())
470         return jsUndefined();
471     for (unsigned i = 0; i < length; ++i) {
472         JSValue element = thisObject->getIndex(&state, i);
473         if (state.hadException())
474             return jsUndefined();
475         joiner.append(state, element);
476         if (state.hadException())
477             return jsUndefined();
478     }
479     return joiner.join(state);
480 }
481
482 EncodedJSValue JSC_HOST_CALL arrayProtoFuncJoin(ExecState* exec)
483 {
484     JSObject* thisObject = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
485
486     StringRecursionChecker checker(exec, thisObject);
487     if (JSValue earlyReturnValue = checker.earlyReturnValue())
488         return JSValue::encode(earlyReturnValue);
489
490     JSValue separatorValue = exec->argument(0);
491     if (separatorValue.isUndefined()) {
492         const LChar comma = ',';
493         return JSValue::encode(join(*exec, thisObject, { &comma, 1 }));
494     }
495
496     JSString* separator = separatorValue.toString(exec);
497     if (exec->hadException())
498         return JSValue::encode(jsUndefined());
499     return JSValue::encode(join(*exec, thisObject, separator->view(exec)));
500 }
501
502 EncodedJSValue JSC_HOST_CALL arrayProtoFuncConcat(ExecState* exec)
503 {
504     JSValue thisValue = exec->thisValue().toThis(exec, StrictMode);
505     unsigned argCount = exec->argumentCount();
506     JSValue curArg = thisValue.toObject(exec);
507     Checked<unsigned, RecordOverflow> finalArraySize = 0;
508
509     JSArray* currentArray = nullptr;
510     JSArray* previousArray = nullptr;
511     for (unsigned i = 0; ; ++i) {
512         previousArray = currentArray;
513         currentArray = jsDynamicCast<JSArray*>(curArg);
514         if (currentArray) {
515             // Can't use JSArray::length here because this might be a RuntimeArray!
516             finalArraySize += getLength(exec, currentArray);
517             if (exec->hadException())
518                 return JSValue::encode(jsUndefined());
519         } else
520             ++finalArraySize;
521         if (i == argCount)
522             break;
523         curArg = exec->uncheckedArgument(i);
524     }
525
526     if (finalArraySize.hasOverflowed())
527         return JSValue::encode(throwOutOfMemoryError(exec));
528
529     if (argCount == 1 && previousArray && currentArray && finalArraySize.unsafeGet() < MIN_SPARSE_ARRAY_INDEX) {
530         IndexingType type = JSArray::fastConcatType(exec->vm(), *previousArray, *currentArray);
531         if (type != NonArray)
532             return previousArray->fastConcatWith(*exec, *currentArray);
533     }
534
535     JSArray* arr = constructEmptyArray(exec, nullptr, finalArraySize.unsafeGet());
536     if (exec->hadException())
537         return JSValue::encode(jsUndefined());
538
539     curArg = thisValue.toObject(exec);
540     unsigned n = 0;
541     for (unsigned i = 0; ; ++i) {
542         if (JSArray* currentArray = jsDynamicCast<JSArray*>(curArg)) {
543             // Can't use JSArray::length here because this might be a RuntimeArray!
544             unsigned length = getLength(exec, currentArray);
545             if (exec->hadException())
546                 return JSValue::encode(jsUndefined());
547             for (unsigned k = 0; k < length; ++k) {
548                 JSValue v = getProperty(exec, currentArray, k);
549                 if (exec->hadException())
550                     return JSValue::encode(jsUndefined());
551                 if (v)
552                     arr->putDirectIndex(exec, n, v);
553                 n++;
554             }
555         } else {
556             arr->putDirectIndex(exec, n, curArg);
557             n++;
558         }
559         if (i == argCount)
560             break;
561         curArg = exec->uncheckedArgument(i);
562     }
563     arr->setLength(exec, n);
564     return JSValue::encode(arr);
565 }
566
567 EncodedJSValue JSC_HOST_CALL arrayProtoFuncPop(ExecState* exec)
568 {
569     JSValue thisValue = exec->thisValue().toThis(exec, StrictMode);
570
571     if (isJSArray(thisValue))
572         return JSValue::encode(asArray(thisValue)->pop(exec));
573
574     JSObject* thisObj = thisValue.toObject(exec);
575     unsigned length = getLength(exec, thisObj);
576     if (exec->hadException())
577         return JSValue::encode(jsUndefined());
578
579     JSValue result;
580     if (length == 0) {
581         putLength(exec, thisObj, jsNumber(length));
582         result = jsUndefined();
583     } else {
584         result = thisObj->get(exec, length - 1);
585         if (exec->hadException())
586             return JSValue::encode(jsUndefined());
587         if (!thisObj->methodTable(exec->vm())->deletePropertyByIndex(thisObj, exec, length - 1)) {
588             throwTypeError(exec, ASCIILiteral("Unable to delete property."));
589             return JSValue::encode(jsUndefined());
590         }
591         putLength(exec, thisObj, jsNumber(length - 1));
592     }
593     return JSValue::encode(result);
594 }
595
596 EncodedJSValue JSC_HOST_CALL arrayProtoFuncPush(ExecState* exec)
597 {
598     JSValue thisValue = exec->thisValue().toThis(exec, StrictMode);
599
600     if (isJSArray(thisValue) && exec->argumentCount() == 1) {
601         JSArray* array = asArray(thisValue);
602         array->push(exec, exec->uncheckedArgument(0));
603         return JSValue::encode(jsNumber(array->length()));
604     }
605     
606     JSObject* thisObj = thisValue.toObject(exec);
607     unsigned length = getLength(exec, thisObj);
608     if (exec->hadException())
609         return JSValue::encode(jsUndefined());
610
611     for (unsigned n = 0; n < exec->argumentCount(); n++) {
612         // Check for integer overflow; where safe we can do a fast put by index.
613         if (length + n >= length)
614             thisObj->methodTable()->putByIndex(thisObj, exec, length + n, exec->uncheckedArgument(n), true);
615         else {
616             PutPropertySlot slot(thisObj);
617             Identifier propertyName = Identifier::fromString(exec, JSValue(static_cast<int64_t>(length) + static_cast<int64_t>(n)).toWTFString(exec));
618             thisObj->methodTable()->put(thisObj, exec, propertyName, exec->uncheckedArgument(n), slot);
619         }
620         if (exec->hadException())
621             return JSValue::encode(jsUndefined());
622     }
623     
624     JSValue newLength(static_cast<int64_t>(length) + static_cast<int64_t>(exec->argumentCount()));
625     putLength(exec, thisObj, newLength);
626     return JSValue::encode(newLength);
627 }
628
629 EncodedJSValue JSC_HOST_CALL arrayProtoFuncReverse(ExecState* exec)
630 {
631     JSObject* thisObject = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
632
633     unsigned length = getLength(exec, thisObject);
634     if (exec->hadException())
635         return JSValue::encode(jsUndefined());
636
637     switch (thisObject->indexingType()) {
638     case ALL_CONTIGUOUS_INDEXING_TYPES:
639     case ALL_INT32_INDEXING_TYPES: {
640         auto& butterfly = *thisObject->butterfly();
641         if (length > butterfly.publicLength())
642             break;
643         auto data = butterfly.contiguous().data();
644         if (containsHole(data, length) && holesMustForwardToPrototype(*exec, thisObject))
645             break;
646         std::reverse(data, data + length);
647         return JSValue::encode(thisObject);
648     }
649     case ALL_DOUBLE_INDEXING_TYPES: {
650         auto& butterfly = *thisObject->butterfly();
651         if (length > butterfly.publicLength())
652             break;
653         auto data = butterfly.contiguousDouble().data();
654         if (containsHole(data, length) && holesMustForwardToPrototype(*exec, thisObject))
655             break;
656         std::reverse(data, data + length);
657         return JSValue::encode(thisObject);
658     }
659     case ALL_ARRAY_STORAGE_INDEXING_TYPES: {
660         auto& storage = *thisObject->butterfly()->arrayStorage();
661         if (length > storage.vectorLength())
662             break;
663         if (storage.hasHoles() && holesMustForwardToPrototype(*exec, thisObject))
664             break;
665         auto data = storage.vector().data();
666         std::reverse(data, data + length);
667         return JSValue::encode(thisObject);
668     }
669     }
670
671     unsigned middle = length / 2;
672     for (unsigned k = 0; k < middle; k++) {
673         unsigned lk1 = length - k - 1;
674         JSValue obj2 = getProperty(exec, thisObject, lk1);
675         if (exec->hadException())
676             return JSValue::encode(jsUndefined());
677         JSValue obj = getProperty(exec, thisObject, k);
678         if (exec->hadException())
679             return JSValue::encode(jsUndefined());
680
681         if (obj2) {
682             thisObject->putByIndexInline(exec, k, obj2, true);
683             if (exec->hadException())
684                 return JSValue::encode(jsUndefined());
685         } else if (!thisObject->methodTable(exec->vm())->deletePropertyByIndex(thisObject, exec, k)) {
686             throwTypeError(exec, ASCIILiteral("Unable to delete property."));
687             return JSValue::encode(jsUndefined());
688         }
689
690         if (obj) {
691             thisObject->putByIndexInline(exec, lk1, obj, true);
692             if (exec->hadException())
693                 return JSValue::encode(jsUndefined());
694         } else if (!thisObject->methodTable(exec->vm())->deletePropertyByIndex(thisObject, exec, lk1)) {
695             throwTypeError(exec, ASCIILiteral("Unable to delete property."));
696             return JSValue::encode(jsUndefined());
697         }
698     }
699     return JSValue::encode(thisObject);
700 }
701
702 EncodedJSValue JSC_HOST_CALL arrayProtoFuncShift(ExecState* exec)
703 {
704     JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
705     unsigned length = getLength(exec, thisObj);
706     if (exec->hadException())
707         return JSValue::encode(jsUndefined());
708
709     JSValue result;
710     if (length == 0) {
711         putLength(exec, thisObj, jsNumber(length));
712         result = jsUndefined();
713     } else {
714         result = thisObj->getIndex(exec, 0);
715         shift<JSArray::ShiftCountForShift>(exec, thisObj, 0, 1, 0, length);
716         if (exec->hadException())
717             return JSValue::encode(jsUndefined());
718         putLength(exec, thisObj, jsNumber(length - 1));
719     }
720     return JSValue::encode(result);
721 }
722
723 EncodedJSValue JSC_HOST_CALL arrayProtoFuncSlice(ExecState* exec)
724 {
725     // http://developer.netscape.com/docs/manuals/js/client/jsref/array.htm#1193713 or 15.4.4.10
726     JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
727     unsigned length = getLength(exec, thisObj);
728     if (exec->hadException())
729         return JSValue::encode(jsUndefined());
730
731     unsigned begin = argumentClampedIndexFromStartOrEnd(exec, 0, length);
732     unsigned end = argumentClampedIndexFromStartOrEnd(exec, 1, length, length);
733
734     if (isJSArray(thisObj)) {
735         if (JSArray* result = asArray(thisObj)->fastSlice(*exec, begin, end - begin))
736             return JSValue::encode(result);
737     }
738
739     JSArray* result = constructEmptyArray(exec, nullptr, end - begin);
740
741     unsigned n = 0;
742     for (unsigned k = begin; k < end; k++, n++) {
743         JSValue v = getProperty(exec, thisObj, k);
744         if (exec->hadException())
745             return JSValue::encode(jsUndefined());
746         if (v)
747             result->putDirectIndex(exec, n, v);
748     }
749     result->setLength(exec, n);
750     return JSValue::encode(result);
751 }
752
753 EncodedJSValue JSC_HOST_CALL arrayProtoFuncSplice(ExecState* exec)
754 {
755     // 15.4.4.12
756
757     VM& vm = exec->vm();
758
759     JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
760     unsigned length = getLength(exec, thisObj);
761     if (exec->hadException())
762         return JSValue::encode(jsUndefined());
763     
764     if (!exec->argumentCount())
765         return JSValue::encode(constructEmptyArray(exec, nullptr));
766
767     unsigned begin = argumentClampedIndexFromStartOrEnd(exec, 0, length);
768
769     unsigned deleteCount = length - begin;
770     if (exec->argumentCount() > 1) {
771         double deleteDouble = exec->uncheckedArgument(1).toInteger(exec);
772         if (deleteDouble < 0)
773             deleteCount = 0;
774         else if (deleteDouble > length - begin)
775             deleteCount = length - begin;
776         else
777             deleteCount = static_cast<unsigned>(deleteDouble);
778     }
779
780     JSArray* result = nullptr;
781
782     if (isJSArray(thisObj))
783         result = asArray(thisObj)->fastSlice(*exec, begin, deleteCount);
784
785     if (!result) {
786         result = JSArray::tryCreateUninitialized(vm, exec->lexicalGlobalObject()->arrayStructureForIndexingTypeDuringAllocation(ArrayWithUndecided), deleteCount);
787         if (!result)
788             return JSValue::encode(throwOutOfMemoryError(exec));
789
790         for (unsigned k = 0; k < deleteCount; ++k) {
791             JSValue v = getProperty(exec, thisObj, k + begin);
792             if (exec->hadException())
793                 return JSValue::encode(jsUndefined());
794             result->initializeIndex(vm, k, v);
795         }
796     }
797
798     unsigned additionalArgs = std::max<int>(exec->argumentCount() - 2, 0);
799     if (additionalArgs < deleteCount) {
800         shift<JSArray::ShiftCountForSplice>(exec, thisObj, begin, deleteCount, additionalArgs, length);
801         if (exec->hadException())
802             return JSValue::encode(jsUndefined());
803     } else if (additionalArgs > deleteCount) {
804         unshift<JSArray::ShiftCountForSplice>(exec, thisObj, begin, deleteCount, additionalArgs, length);
805         if (exec->hadException())
806             return JSValue::encode(jsUndefined());
807     }
808     for (unsigned k = 0; k < additionalArgs; ++k) {
809         thisObj->putByIndexInline(exec, k + begin, exec->uncheckedArgument(k + 2), true);
810         if (exec->hadException())
811             return JSValue::encode(jsUndefined());
812     }
813
814     putLength(exec, thisObj, jsNumber(length - deleteCount + additionalArgs));
815     return JSValue::encode(result);
816 }
817
818 EncodedJSValue JSC_HOST_CALL arrayProtoFuncUnShift(ExecState* exec)
819 {
820     // 15.4.4.13
821
822     JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
823     unsigned length = getLength(exec, thisObj);
824     if (exec->hadException())
825         return JSValue::encode(jsUndefined());
826
827     unsigned nrArgs = exec->argumentCount();
828     if (nrArgs) {
829         unshift<JSArray::ShiftCountForShift>(exec, thisObj, 0, 0, nrArgs, length);
830         if (exec->hadException())
831             return JSValue::encode(jsUndefined());
832     }
833     for (unsigned k = 0; k < nrArgs; ++k) {
834         thisObj->putByIndexInline(exec, k, exec->uncheckedArgument(k), true);
835         if (exec->hadException())
836             return JSValue::encode(jsUndefined());
837     }
838     JSValue result = jsNumber(length + nrArgs);
839     putLength(exec, thisObj, result);
840     return JSValue::encode(result);
841 }
842
843 EncodedJSValue JSC_HOST_CALL arrayProtoFuncIndexOf(ExecState* exec)
844 {
845     // 15.4.4.14
846     JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
847     unsigned length = getLength(exec, thisObj);
848     if (exec->hadException())
849         return JSValue::encode(jsUndefined());
850
851     unsigned index = argumentClampedIndexFromStartOrEnd(exec, 1, length);
852     JSValue searchElement = exec->argument(0);
853     for (; index < length; ++index) {
854         JSValue e = getProperty(exec, thisObj, index);
855         if (exec->hadException())
856             return JSValue::encode(jsUndefined());
857         if (!e)
858             continue;
859         if (JSValue::strictEqual(exec, searchElement, e))
860             return JSValue::encode(jsNumber(index));
861     }
862
863     return JSValue::encode(jsNumber(-1));
864 }
865
866 EncodedJSValue JSC_HOST_CALL arrayProtoFuncLastIndexOf(ExecState* exec)
867 {
868     // 15.4.4.15
869     JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
870     unsigned length = getLength(exec, thisObj);
871     if (!length)
872         return JSValue::encode(jsNumber(-1));
873
874     unsigned index = length - 1;
875     if (exec->argumentCount() >= 2) {
876         JSValue fromValue = exec->uncheckedArgument(1);
877         double fromDouble = fromValue.toInteger(exec);
878         if (fromDouble < 0) {
879             fromDouble += length;
880             if (fromDouble < 0)
881                 return JSValue::encode(jsNumber(-1));
882         }
883         if (fromDouble < length)
884             index = static_cast<unsigned>(fromDouble);
885     }
886
887     JSValue searchElement = exec->argument(0);
888     do {
889         RELEASE_ASSERT(index < length);
890         JSValue e = getProperty(exec, thisObj, index);
891         if (exec->hadException())
892             return JSValue::encode(jsUndefined());
893         if (!e)
894             continue;
895         if (JSValue::strictEqual(exec, searchElement, e))
896             return JSValue::encode(jsNumber(index));
897     } while (index--);
898
899     return JSValue::encode(jsNumber(-1));
900 }
901
902 EncodedJSValue JSC_HOST_CALL arrayProtoFuncValues(ExecState* exec)
903 {
904     JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
905     return JSValue::encode(JSArrayIterator::create(exec, exec->callee()->globalObject()->arrayIteratorStructure(), ArrayIterateValue, thisObj));
906 }
907
908 EncodedJSValue JSC_HOST_CALL arrayProtoFuncEntries(ExecState* exec)
909 {
910     JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
911     return JSValue::encode(JSArrayIterator::create(exec, exec->callee()->globalObject()->arrayIteratorStructure(), ArrayIterateKeyValue, thisObj));
912 }
913     
914 EncodedJSValue JSC_HOST_CALL arrayProtoFuncKeys(ExecState* exec)
915 {
916     JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
917     return JSValue::encode(JSArrayIterator::create(exec, exec->callee()->globalObject()->arrayIteratorStructure(), ArrayIterateKey, thisObj));
918 }
919
920 } // namespace JSC