e682429792077a05c22aec384dbcd8449fe24856
[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     for (unsigned i = 0; ; ++i) {
510         if (JSArray* currentArray = jsDynamicCast<JSArray*>(curArg)) {
511             // Can't use JSArray::length here because this might be a RuntimeArray!
512             finalArraySize += getLength(exec, currentArray);
513             if (exec->hadException())
514                 return JSValue::encode(jsUndefined());
515         } else
516             ++finalArraySize;
517         if (i == argCount)
518             break;
519         curArg = exec->uncheckedArgument(i);
520     }
521
522     if (finalArraySize.hasOverflowed())
523         return JSValue::encode(throwOutOfMemoryError(exec));
524
525     JSArray* arr = constructEmptyArray(exec, nullptr, finalArraySize.unsafeGet());
526     if (exec->hadException())
527         return JSValue::encode(jsUndefined());
528
529     curArg = thisValue.toObject(exec);
530     unsigned n = 0;
531     for (unsigned i = 0; ; ++i) {
532         if (JSArray* currentArray = jsDynamicCast<JSArray*>(curArg)) {
533             // Can't use JSArray::length here because this might be a RuntimeArray!
534             unsigned length = getLength(exec, currentArray);
535             if (exec->hadException())
536                 return JSValue::encode(jsUndefined());
537             for (unsigned k = 0; k < length; ++k) {
538                 JSValue v = getProperty(exec, currentArray, k);
539                 if (exec->hadException())
540                     return JSValue::encode(jsUndefined());
541                 if (v)
542                     arr->putDirectIndex(exec, n, v);
543                 n++;
544             }
545         } else {
546             arr->putDirectIndex(exec, n, curArg);
547             n++;
548         }
549         if (i == argCount)
550             break;
551         curArg = exec->uncheckedArgument(i);
552     }
553     arr->setLength(exec, n);
554     return JSValue::encode(arr);
555 }
556
557 EncodedJSValue JSC_HOST_CALL arrayProtoFuncPop(ExecState* exec)
558 {
559     JSValue thisValue = exec->thisValue().toThis(exec, StrictMode);
560
561     if (isJSArray(thisValue))
562         return JSValue::encode(asArray(thisValue)->pop(exec));
563
564     JSObject* thisObj = thisValue.toObject(exec);
565     unsigned length = getLength(exec, thisObj);
566     if (exec->hadException())
567         return JSValue::encode(jsUndefined());
568
569     JSValue result;
570     if (length == 0) {
571         putLength(exec, thisObj, jsNumber(length));
572         result = jsUndefined();
573     } else {
574         result = thisObj->get(exec, length - 1);
575         if (exec->hadException())
576             return JSValue::encode(jsUndefined());
577         if (!thisObj->methodTable(exec->vm())->deletePropertyByIndex(thisObj, exec, length - 1)) {
578             throwTypeError(exec, ASCIILiteral("Unable to delete property."));
579             return JSValue::encode(jsUndefined());
580         }
581         putLength(exec, thisObj, jsNumber(length - 1));
582     }
583     return JSValue::encode(result);
584 }
585
586 EncodedJSValue JSC_HOST_CALL arrayProtoFuncPush(ExecState* exec)
587 {
588     JSValue thisValue = exec->thisValue().toThis(exec, StrictMode);
589
590     if (isJSArray(thisValue) && exec->argumentCount() == 1) {
591         JSArray* array = asArray(thisValue);
592         array->push(exec, exec->uncheckedArgument(0));
593         return JSValue::encode(jsNumber(array->length()));
594     }
595     
596     JSObject* thisObj = thisValue.toObject(exec);
597     unsigned length = getLength(exec, thisObj);
598     if (exec->hadException())
599         return JSValue::encode(jsUndefined());
600
601     for (unsigned n = 0; n < exec->argumentCount(); n++) {
602         // Check for integer overflow; where safe we can do a fast put by index.
603         if (length + n >= length)
604             thisObj->methodTable()->putByIndex(thisObj, exec, length + n, exec->uncheckedArgument(n), true);
605         else {
606             PutPropertySlot slot(thisObj);
607             Identifier propertyName = Identifier::fromString(exec, JSValue(static_cast<int64_t>(length) + static_cast<int64_t>(n)).toWTFString(exec));
608             thisObj->methodTable()->put(thisObj, exec, propertyName, exec->uncheckedArgument(n), slot);
609         }
610         if (exec->hadException())
611             return JSValue::encode(jsUndefined());
612     }
613     
614     JSValue newLength(static_cast<int64_t>(length) + static_cast<int64_t>(exec->argumentCount()));
615     putLength(exec, thisObj, newLength);
616     return JSValue::encode(newLength);
617 }
618
619 EncodedJSValue JSC_HOST_CALL arrayProtoFuncReverse(ExecState* exec)
620 {
621     JSObject* thisObject = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
622
623     unsigned length = getLength(exec, thisObject);
624     if (exec->hadException())
625         return JSValue::encode(jsUndefined());
626
627     switch (thisObject->indexingType()) {
628     case ALL_CONTIGUOUS_INDEXING_TYPES:
629     case ALL_INT32_INDEXING_TYPES: {
630         auto& butterfly = *thisObject->butterfly();
631         if (length > butterfly.publicLength())
632             break;
633         auto data = butterfly.contiguous().data();
634         if (containsHole(data, length) && holesMustForwardToPrototype(*exec, thisObject))
635             break;
636         std::reverse(data, data + length);
637         return JSValue::encode(thisObject);
638     }
639     case ALL_DOUBLE_INDEXING_TYPES: {
640         auto& butterfly = *thisObject->butterfly();
641         if (length > butterfly.publicLength())
642             break;
643         auto data = butterfly.contiguousDouble().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_ARRAY_STORAGE_INDEXING_TYPES: {
650         auto& storage = *thisObject->butterfly()->arrayStorage();
651         if (length > storage.vectorLength())
652             break;
653         if (storage.hasHoles() && holesMustForwardToPrototype(*exec, thisObject))
654             break;
655         auto data = storage.vector().data();
656         std::reverse(data, data + length);
657         return JSValue::encode(thisObject);
658     }
659     }
660
661     unsigned middle = length / 2;
662     for (unsigned k = 0; k < middle; k++) {
663         unsigned lk1 = length - k - 1;
664         JSValue obj2 = getProperty(exec, thisObject, lk1);
665         if (exec->hadException())
666             return JSValue::encode(jsUndefined());
667         JSValue obj = getProperty(exec, thisObject, k);
668         if (exec->hadException())
669             return JSValue::encode(jsUndefined());
670
671         if (obj2) {
672             thisObject->putByIndexInline(exec, k, obj2, true);
673             if (exec->hadException())
674                 return JSValue::encode(jsUndefined());
675         } else if (!thisObject->methodTable(exec->vm())->deletePropertyByIndex(thisObject, exec, k)) {
676             throwTypeError(exec, ASCIILiteral("Unable to delete property."));
677             return JSValue::encode(jsUndefined());
678         }
679
680         if (obj) {
681             thisObject->putByIndexInline(exec, lk1, obj, true);
682             if (exec->hadException())
683                 return JSValue::encode(jsUndefined());
684         } else if (!thisObject->methodTable(exec->vm())->deletePropertyByIndex(thisObject, exec, lk1)) {
685             throwTypeError(exec, ASCIILiteral("Unable to delete property."));
686             return JSValue::encode(jsUndefined());
687         }
688     }
689     return JSValue::encode(thisObject);
690 }
691
692 EncodedJSValue JSC_HOST_CALL arrayProtoFuncShift(ExecState* exec)
693 {
694     JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
695     unsigned length = getLength(exec, thisObj);
696     if (exec->hadException())
697         return JSValue::encode(jsUndefined());
698
699     JSValue result;
700     if (length == 0) {
701         putLength(exec, thisObj, jsNumber(length));
702         result = jsUndefined();
703     } else {
704         result = thisObj->getIndex(exec, 0);
705         shift<JSArray::ShiftCountForShift>(exec, thisObj, 0, 1, 0, length);
706         if (exec->hadException())
707             return JSValue::encode(jsUndefined());
708         putLength(exec, thisObj, jsNumber(length - 1));
709     }
710     return JSValue::encode(result);
711 }
712
713 EncodedJSValue JSC_HOST_CALL arrayProtoFuncSlice(ExecState* exec)
714 {
715     // http://developer.netscape.com/docs/manuals/js/client/jsref/array.htm#1193713 or 15.4.4.10
716     JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
717     unsigned length = getLength(exec, thisObj);
718     if (exec->hadException())
719         return JSValue::encode(jsUndefined());
720
721     unsigned begin = argumentClampedIndexFromStartOrEnd(exec, 0, length);
722     unsigned end = argumentClampedIndexFromStartOrEnd(exec, 1, length, length);
723
724     if (isJSArray(thisObj)) {
725         if (JSArray* result = asArray(thisObj)->fastSlice(*exec, begin, end - begin))
726             return JSValue::encode(result);
727     }
728
729     JSArray* result = constructEmptyArray(exec, nullptr, end - begin);
730
731     unsigned n = 0;
732     for (unsigned k = begin; k < end; k++, n++) {
733         JSValue v = getProperty(exec, thisObj, k);
734         if (exec->hadException())
735             return JSValue::encode(jsUndefined());
736         if (v)
737             result->putDirectIndex(exec, n, v);
738     }
739     result->setLength(exec, n);
740     return JSValue::encode(result);
741 }
742
743 EncodedJSValue JSC_HOST_CALL arrayProtoFuncSplice(ExecState* exec)
744 {
745     // 15.4.4.12
746
747     VM& vm = exec->vm();
748
749     JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
750     unsigned length = getLength(exec, thisObj);
751     if (exec->hadException())
752         return JSValue::encode(jsUndefined());
753     
754     if (!exec->argumentCount())
755         return JSValue::encode(constructEmptyArray(exec, nullptr));
756
757     unsigned begin = argumentClampedIndexFromStartOrEnd(exec, 0, length);
758
759     unsigned deleteCount = length - begin;
760     if (exec->argumentCount() > 1) {
761         double deleteDouble = exec->uncheckedArgument(1).toInteger(exec);
762         if (deleteDouble < 0)
763             deleteCount = 0;
764         else if (deleteDouble > length - begin)
765             deleteCount = length - begin;
766         else
767             deleteCount = static_cast<unsigned>(deleteDouble);
768     }
769
770     JSArray* result = nullptr;
771
772     if (isJSArray(thisObj))
773         result = asArray(thisObj)->fastSlice(*exec, begin, deleteCount);
774
775     if (!result) {
776         result = JSArray::tryCreateUninitialized(vm, exec->lexicalGlobalObject()->arrayStructureForIndexingTypeDuringAllocation(ArrayWithUndecided), deleteCount);
777         if (!result)
778             return JSValue::encode(throwOutOfMemoryError(exec));
779
780         for (unsigned k = 0; k < deleteCount; ++k) {
781             JSValue v = getProperty(exec, thisObj, k + begin);
782             if (exec->hadException())
783                 return JSValue::encode(jsUndefined());
784             result->initializeIndex(vm, k, v);
785         }
786     }
787
788     unsigned additionalArgs = std::max<int>(exec->argumentCount() - 2, 0);
789     if (additionalArgs < deleteCount) {
790         shift<JSArray::ShiftCountForSplice>(exec, thisObj, begin, deleteCount, additionalArgs, length);
791         if (exec->hadException())
792             return JSValue::encode(jsUndefined());
793     } else if (additionalArgs > deleteCount) {
794         unshift<JSArray::ShiftCountForSplice>(exec, thisObj, begin, deleteCount, additionalArgs, length);
795         if (exec->hadException())
796             return JSValue::encode(jsUndefined());
797     }
798     for (unsigned k = 0; k < additionalArgs; ++k) {
799         thisObj->putByIndexInline(exec, k + begin, exec->uncheckedArgument(k + 2), true);
800         if (exec->hadException())
801             return JSValue::encode(jsUndefined());
802     }
803
804     putLength(exec, thisObj, jsNumber(length - deleteCount + additionalArgs));
805     return JSValue::encode(result);
806 }
807
808 EncodedJSValue JSC_HOST_CALL arrayProtoFuncUnShift(ExecState* exec)
809 {
810     // 15.4.4.13
811
812     JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
813     unsigned length = getLength(exec, thisObj);
814     if (exec->hadException())
815         return JSValue::encode(jsUndefined());
816
817     unsigned nrArgs = exec->argumentCount();
818     if (nrArgs) {
819         unshift<JSArray::ShiftCountForShift>(exec, thisObj, 0, 0, nrArgs, length);
820         if (exec->hadException())
821             return JSValue::encode(jsUndefined());
822     }
823     for (unsigned k = 0; k < nrArgs; ++k) {
824         thisObj->putByIndexInline(exec, k, exec->uncheckedArgument(k), true);
825         if (exec->hadException())
826             return JSValue::encode(jsUndefined());
827     }
828     JSValue result = jsNumber(length + nrArgs);
829     putLength(exec, thisObj, result);
830     return JSValue::encode(result);
831 }
832
833 EncodedJSValue JSC_HOST_CALL arrayProtoFuncIndexOf(ExecState* exec)
834 {
835     // 15.4.4.14
836     JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
837     unsigned length = getLength(exec, thisObj);
838     if (exec->hadException())
839         return JSValue::encode(jsUndefined());
840
841     unsigned index = argumentClampedIndexFromStartOrEnd(exec, 1, length);
842     JSValue searchElement = exec->argument(0);
843     for (; index < length; ++index) {
844         JSValue e = getProperty(exec, thisObj, index);
845         if (exec->hadException())
846             return JSValue::encode(jsUndefined());
847         if (!e)
848             continue;
849         if (JSValue::strictEqual(exec, searchElement, e))
850             return JSValue::encode(jsNumber(index));
851     }
852
853     return JSValue::encode(jsNumber(-1));
854 }
855
856 EncodedJSValue JSC_HOST_CALL arrayProtoFuncLastIndexOf(ExecState* exec)
857 {
858     // 15.4.4.15
859     JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
860     unsigned length = getLength(exec, thisObj);
861     if (!length)
862         return JSValue::encode(jsNumber(-1));
863
864     unsigned index = length - 1;
865     if (exec->argumentCount() >= 2) {
866         JSValue fromValue = exec->uncheckedArgument(1);
867         double fromDouble = fromValue.toInteger(exec);
868         if (fromDouble < 0) {
869             fromDouble += length;
870             if (fromDouble < 0)
871                 return JSValue::encode(jsNumber(-1));
872         }
873         if (fromDouble < length)
874             index = static_cast<unsigned>(fromDouble);
875     }
876
877     JSValue searchElement = exec->argument(0);
878     do {
879         RELEASE_ASSERT(index < length);
880         JSValue e = getProperty(exec, thisObj, index);
881         if (exec->hadException())
882             return JSValue::encode(jsUndefined());
883         if (!e)
884             continue;
885         if (JSValue::strictEqual(exec, searchElement, e))
886             return JSValue::encode(jsNumber(index));
887     } while (index--);
888
889     return JSValue::encode(jsNumber(-1));
890 }
891
892 EncodedJSValue JSC_HOST_CALL arrayProtoFuncValues(ExecState* exec)
893 {
894     JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
895     return JSValue::encode(JSArrayIterator::create(exec, exec->callee()->globalObject()->arrayIteratorStructure(), ArrayIterateValue, thisObj));
896 }
897
898 EncodedJSValue JSC_HOST_CALL arrayProtoFuncEntries(ExecState* exec)
899 {
900     JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
901     return JSValue::encode(JSArrayIterator::create(exec, exec->callee()->globalObject()->arrayIteratorStructure(), ArrayIterateKeyValue, thisObj));
902 }
903     
904 EncodedJSValue JSC_HOST_CALL arrayProtoFuncKeys(ExecState* exec)
905 {
906     JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
907     return JSValue::encode(JSArrayIterator::create(exec, exec->callee()->globalObject()->arrayIteratorStructure(), ArrayIterateKey, thisObj));
908 }
909
910 } // namespace JSC