1/*
2 *  Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
3 *  Copyright (C) 2003, 2007, 2008, 2009, 2011, 2013 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 "JSStringBuilder.h"
36#include "JSStringJoiner.h"
37#include "Lookup.h"
38#include "ObjectPrototype.h"
39#include "JSCInlines.h"
40#include "StringRecursionChecker.h"
41#include <algorithm>
42#include <wtf/Assertions.h>
43#include <wtf/HashSet.h>
44
45namespace JSC {
46
47static EncodedJSValue JSC_HOST_CALL arrayProtoFuncToString(ExecState*);
48static EncodedJSValue JSC_HOST_CALL arrayProtoFuncToLocaleString(ExecState*);
49static EncodedJSValue JSC_HOST_CALL arrayProtoFuncConcat(ExecState*);
50static EncodedJSValue JSC_HOST_CALL arrayProtoFuncJoin(ExecState*);
51static EncodedJSValue JSC_HOST_CALL arrayProtoFuncPop(ExecState*);
52static EncodedJSValue JSC_HOST_CALL arrayProtoFuncPush(ExecState*);
53static EncodedJSValue JSC_HOST_CALL arrayProtoFuncReverse(ExecState*);
54static EncodedJSValue JSC_HOST_CALL arrayProtoFuncShift(ExecState*);
55static EncodedJSValue JSC_HOST_CALL arrayProtoFuncSlice(ExecState*);
56static EncodedJSValue JSC_HOST_CALL arrayProtoFuncSort(ExecState*);
57static EncodedJSValue JSC_HOST_CALL arrayProtoFuncSplice(ExecState*);
58static EncodedJSValue JSC_HOST_CALL arrayProtoFuncUnShift(ExecState*);
59static EncodedJSValue JSC_HOST_CALL arrayProtoFuncIndexOf(ExecState*);
60static EncodedJSValue JSC_HOST_CALL arrayProtoFuncReduce(ExecState*);
61static EncodedJSValue JSC_HOST_CALL arrayProtoFuncReduceRight(ExecState*);
62static EncodedJSValue JSC_HOST_CALL arrayProtoFuncLastIndexOf(ExecState*);
63static EncodedJSValue JSC_HOST_CALL arrayProtoFuncValues(ExecState*);
64static EncodedJSValue JSC_HOST_CALL arrayProtoFuncKeys(ExecState*);
65static EncodedJSValue JSC_HOST_CALL arrayProtoFuncEntries(ExecState*);
66
67}
68
69#include "ArrayPrototype.lut.h"
70
71namespace JSC {
72
73static inline bool isNumericCompareFunction(ExecState* exec, JSValue function, CallType callType, const CallData& callData)
74{
75    if (callType != CallTypeJS)
76        return false;
77
78    FunctionExecutable* executable = callData.js.functionExecutable;
79    JSScope* scope = callData.js.scope;
80
81    JSObject* error = executable->prepareForExecution(exec, jsCast<JSFunction*>(function), &scope, CodeForCall);
82    if (error)
83        return false;
84
85    return executable->codeBlockForCall()->isNumericCompareFunction();
86}
87
88// ------------------------------ ArrayPrototype ----------------------------
89
90const ClassInfo ArrayPrototype::s_info = {"Array", &JSArray::s_info, 0, ExecState::arrayPrototypeTable, CREATE_METHOD_TABLE(ArrayPrototype)};
91
92/* Source for ArrayPrototype.lut.h
93@begin arrayPrototypeTable 16
94  toString       arrayProtoFuncToString       DontEnum|Function 0
95  toLocaleString arrayProtoFuncToLocaleString DontEnum|Function 0
96  concat         arrayProtoFuncConcat         DontEnum|Function 1
97  fill           arrayProtoFuncFill           DontEnum|Function 1
98  join           arrayProtoFuncJoin           DontEnum|Function 1
99  pop            arrayProtoFuncPop            DontEnum|Function 0
100  push           arrayProtoFuncPush           DontEnum|Function 1
101  reverse        arrayProtoFuncReverse        DontEnum|Function 0
102  shift          arrayProtoFuncShift          DontEnum|Function 0
103  slice          arrayProtoFuncSlice          DontEnum|Function 2
104  sort           arrayProtoFuncSort           DontEnum|Function 1
105  splice         arrayProtoFuncSplice         DontEnum|Function 2
106  unshift        arrayProtoFuncUnShift        DontEnum|Function 1
107  every          arrayProtoFuncEvery          DontEnum|Function 1
108  forEach        arrayProtoFuncForEach        DontEnum|Function 1
109  some           arrayProtoFuncSome           DontEnum|Function 1
110  indexOf        arrayProtoFuncIndexOf        DontEnum|Function 1
111  lastIndexOf    arrayProtoFuncLastIndexOf    DontEnum|Function 1
112  filter         arrayProtoFuncFilter         DontEnum|Function 1
113  reduce         arrayProtoFuncReduce         DontEnum|Function 1
114  reduceRight    arrayProtoFuncReduceRight    DontEnum|Function 1
115  map            arrayProtoFuncMap            DontEnum|Function 1
116  entries        arrayProtoFuncEntries        DontEnum|Function 0
117  keys           arrayProtoFuncKeys           DontEnum|Function 0
118  find           arrayProtoFuncFind           DontEnum|Function 1
119  findIndex      arrayProtoFuncFindIndex      DontEnum|Function 1
120@end
121*/
122
123ArrayPrototype* ArrayPrototype::create(VM& vm, JSGlobalObject* globalObject, Structure* structure)
124{
125    ArrayPrototype* prototype = new (NotNull, allocateCell<ArrayPrototype>(vm.heap)) ArrayPrototype(vm, structure);
126    prototype->finishCreation(vm, globalObject);
127    return prototype;
128}
129
130// ECMA 15.4.4
131ArrayPrototype::ArrayPrototype(VM& vm, Structure* structure)
132    : JSArray(vm, structure, 0)
133{
134}
135
136void ArrayPrototype::finishCreation(VM& vm, JSGlobalObject* globalObject)
137{
138    Base::finishCreation(vm);
139    ASSERT(inherits(info()));
140    vm.prototypeMap.addPrototype(this);
141    JSC_NATIVE_FUNCTION(vm.propertyNames->iteratorPrivateName, arrayProtoFuncValues, DontEnum, 0);
142}
143
144bool ArrayPrototype::getOwnPropertySlot(JSObject* object, ExecState* exec, PropertyName propertyName, PropertySlot& slot)
145{
146    return getStaticFunctionSlot<JSArray>(exec, ExecState::arrayPrototypeTable(exec->vm()), jsCast<ArrayPrototype*>(object), propertyName, slot);
147}
148
149// ------------------------------ Array Functions ----------------------------
150
151// Helper function
152static ALWAYS_INLINE JSValue getProperty(ExecState* exec, JSObject* obj, unsigned index)
153{
154    PropertySlot slot(obj);
155    if (!obj->getPropertySlot(exec, index, slot))
156        return JSValue();
157    return slot.getValue(exec, index);
158}
159
160static ALWAYS_INLINE unsigned getLength(ExecState* exec, JSObject* obj)
161{
162    if (isJSArray(obj))
163        return jsCast<JSArray*>(obj)->length();
164    return obj->get(exec, exec->propertyNames().length).toUInt32(exec);
165}
166
167static void putLength(ExecState* exec, JSObject* obj, JSValue value)
168{
169    PutPropertySlot slot(obj);
170    obj->methodTable()->put(obj, exec, exec->propertyNames().length, value, slot);
171}
172
173static unsigned argumentClampedIndexFromStartOrEnd(ExecState* exec, int argument, unsigned length, unsigned undefinedValue = 0)
174{
175    JSValue value = exec->argument(argument);
176    if (value.isUndefined())
177        return undefinedValue;
178
179    double indexDouble = value.toInteger(exec);
180    if (indexDouble < 0) {
181        indexDouble += length;
182        return indexDouble < 0 ? 0 : static_cast<unsigned>(indexDouble);
183    }
184    return indexDouble > length ? length : static_cast<unsigned>(indexDouble);
185}
186
187
188// The shift/unshift function implement the shift/unshift behaviour required
189// by the corresponding array prototype methods, and by splice. In both cases,
190// the methods are operating an an array or array like object.
191//
192//  header  currentCount  (remainder)
193// [------][------------][-----------]
194//  header  resultCount  (remainder)
195// [------][-----------][-----------]
196//
197// The set of properties in the range 'header' must be unchanged. The set of
198// properties in the range 'remainder' (where remainder = length - header -
199// currentCount) will be shifted to the left or right as appropriate; in the
200// case of shift this must be removing values, in the case of unshift this
201// must be introducing new values.
202template<JSArray::ShiftCountMode shiftCountMode>
203void shift(ExecState* exec, JSObject* thisObj, unsigned header, unsigned currentCount, unsigned resultCount, unsigned length)
204{
205    RELEASE_ASSERT(currentCount > resultCount);
206    unsigned count = currentCount - resultCount;
207
208    RELEASE_ASSERT(header <= length);
209    RELEASE_ASSERT(currentCount <= (length - header));
210
211    if (isJSArray(thisObj)) {
212        JSArray* array = asArray(thisObj);
213        if (array->length() == length && asArray(thisObj)->shiftCount<shiftCountMode>(exec, header, count))
214            return;
215    }
216
217    for (unsigned k = header; k < length - currentCount; ++k) {
218        unsigned from = k + currentCount;
219        unsigned to = k + resultCount;
220        PropertySlot slot(thisObj);
221        if (thisObj->getPropertySlot(exec, from, slot)) {
222            JSValue value = slot.getValue(exec, from);
223            if (exec->hadException())
224                return;
225            thisObj->methodTable(exec->vm())->putByIndex(thisObj, exec, to, value, true);
226            if (exec->hadException())
227                return;
228        } else if (!thisObj->methodTable(exec->vm())->deletePropertyByIndex(thisObj, exec, to)) {
229            throwTypeError(exec, ASCIILiteral("Unable to delete property."));
230            return;
231        }
232    }
233    for (unsigned k = length; k > length - count; --k) {
234        if (!thisObj->methodTable(exec->vm())->deletePropertyByIndex(thisObj, exec, k - 1)) {
235            throwTypeError(exec, ASCIILiteral("Unable to delete property."));
236            return;
237        }
238    }
239}
240template<JSArray::ShiftCountMode shiftCountMode>
241void unshift(ExecState* exec, JSObject* thisObj, unsigned header, unsigned currentCount, unsigned resultCount, unsigned length)
242{
243    RELEASE_ASSERT(resultCount > currentCount);
244    unsigned count = resultCount - currentCount;
245
246    RELEASE_ASSERT(header <= length);
247    RELEASE_ASSERT(currentCount <= (length - header));
248
249    // Guard against overflow.
250    if (count > (UINT_MAX - length)) {
251        throwOutOfMemoryError(exec);
252        return;
253    }
254
255    if (isJSArray(thisObj)) {
256        JSArray* array = asArray(thisObj);
257        if (array->length() == length && array->unshiftCount<shiftCountMode>(exec, header, count))
258            return;
259    }
260
261    for (unsigned k = length - currentCount; k > header; --k) {
262        unsigned from = k + currentCount - 1;
263        unsigned to = k + resultCount - 1;
264        PropertySlot slot(thisObj);
265        if (thisObj->getPropertySlot(exec, from, slot)) {
266            JSValue value = slot.getValue(exec, from);
267            if (exec->hadException())
268                return;
269            thisObj->methodTable(exec->vm())->putByIndex(thisObj, exec, to, value, true);
270        } else if (!thisObj->methodTable(exec->vm())->deletePropertyByIndex(thisObj, exec, to)) {
271            throwTypeError(exec, ASCIILiteral("Unable to delete property."));
272            return;
273        }
274        if (exec->hadException())
275            return;
276    }
277}
278
279EncodedJSValue JSC_HOST_CALL arrayProtoFuncToString(ExecState* exec)
280{
281    JSValue thisValue = exec->thisValue().toThis(exec, StrictMode);
282
283    // 1. Let array be the result of calling ToObject on the this value.
284    JSObject* thisObject = thisValue.toObject(exec);
285    if (exec->hadException())
286        return JSValue::encode(jsUndefined());
287
288    // 2. Let func be the result of calling the [[Get]] internal method of array with argument "join".
289    JSValue function = JSValue(thisObject).get(exec, exec->propertyNames().join);
290
291    // 3. If IsCallable(func) is false, then let func be the standard built-in method Object.prototype.toString (15.2.4.2).
292    if (!function.isCell())
293        return JSValue::encode(jsMakeNontrivialString(exec, "[object ", thisObject->methodTable(exec->vm())->className(thisObject), "]"));
294    CallData callData;
295    CallType callType = getCallData(function, callData);
296    if (callType == CallTypeNone)
297        return JSValue::encode(jsMakeNontrivialString(exec, "[object ", thisObject->methodTable(exec->vm())->className(thisObject), "]"));
298
299    // 4. Return the result of calling the [[Call]] internal method of func providing array as the this value and an empty arguments list.
300    if (!isJSArray(thisObject) || callType != CallTypeHost || callData.native.function != arrayProtoFuncJoin)
301        return JSValue::encode(call(exec, function, callType, callData, thisObject, exec->emptyList()));
302
303    ASSERT(isJSArray(thisValue));
304    JSArray* thisObj = asArray(thisValue);
305
306    unsigned length = getLength(exec, thisObj);
307    if (exec->hadException())
308        return JSValue::encode(jsUndefined());
309
310    StringRecursionChecker checker(exec, thisObj);
311    if (JSValue earlyReturnValue = checker.earlyReturnValue())
312        return JSValue::encode(earlyReturnValue);
313
314    String separator(",", String::ConstructFromLiteral);
315    JSStringJoiner stringJoiner(separator, length);
316    for (unsigned k = 0; k < length; k++) {
317        JSValue element;
318        if (thisObj->canGetIndexQuickly(k))
319            element = thisObj->getIndexQuickly(k);
320        else {
321            element = thisObj->get(exec, k);
322            if (exec->hadException())
323                return JSValue::encode(jsUndefined());
324        }
325
326        if (element.isUndefinedOrNull())
327            stringJoiner.append(String());
328        else
329            stringJoiner.append(element.toWTFString(exec));
330
331        if (exec->hadException())
332            return JSValue::encode(jsUndefined());
333    }
334    return JSValue::encode(stringJoiner.join(exec));
335}
336
337EncodedJSValue JSC_HOST_CALL arrayProtoFuncToLocaleString(ExecState* exec)
338{
339    JSValue thisValue = exec->thisValue().toThis(exec, StrictMode);
340
341    JSObject* thisObj = thisValue.toObject(exec);
342    if (exec->hadException())
343        return JSValue::encode(jsUndefined());
344
345    unsigned length = getLength(exec, thisObj);
346    if (exec->hadException())
347        return JSValue::encode(jsUndefined());
348
349    StringRecursionChecker checker(exec, thisObj);
350    if (JSValue earlyReturnValue = checker.earlyReturnValue())
351        return JSValue::encode(earlyReturnValue);
352
353    String separator(",", String::ConstructFromLiteral);
354    JSStringJoiner stringJoiner(separator, length);
355    for (unsigned k = 0; k < length; k++) {
356        JSValue element = thisObj->get(exec, k);
357        if (exec->hadException())
358            return JSValue::encode(jsUndefined());
359        if (!element.isUndefinedOrNull()) {
360            JSObject* o = element.toObject(exec);
361            JSValue conversionFunction = o->get(exec, exec->propertyNames().toLocaleString);
362            if (exec->hadException())
363                return JSValue::encode(jsUndefined());
364            String str;
365            CallData callData;
366            CallType callType = getCallData(conversionFunction, callData);
367            if (callType != CallTypeNone)
368                str = call(exec, conversionFunction, callType, callData, element, exec->emptyList()).toWTFString(exec);
369            else
370                str = element.toWTFString(exec);
371            if (exec->hadException())
372                return JSValue::encode(jsUndefined());
373            stringJoiner.append(str);
374        }
375    }
376
377    return JSValue::encode(stringJoiner.join(exec));
378}
379
380EncodedJSValue JSC_HOST_CALL arrayProtoFuncJoin(ExecState* exec)
381{
382    JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
383    unsigned length = getLength(exec, thisObj);
384    if (exec->hadException())
385        return JSValue::encode(jsUndefined());
386
387    StringRecursionChecker checker(exec, thisObj);
388    if (JSValue earlyReturnValue = checker.earlyReturnValue())
389        return JSValue::encode(earlyReturnValue);
390
391    String separator;
392    if (!exec->argument(0).isUndefined())
393        separator = exec->argument(0).toWTFString(exec);
394    if (separator.isNull())
395        separator = String(",", String::ConstructFromLiteral);
396
397    JSStringJoiner stringJoiner(separator, length);
398
399    unsigned k = 0;
400    if (isJSArray(thisObj)) {
401        JSArray* array = asArray(thisObj);
402
403        for (; k < length; k++) {
404            if (!array->canGetIndexQuickly(k))
405                break;
406
407            JSValue element = array->getIndexQuickly(k);
408            if (!element.isUndefinedOrNull())
409                stringJoiner.append(element.toWTFStringInline(exec));
410            else
411                stringJoiner.append(String());
412        }
413    }
414
415    for (; k < length; k++) {
416        JSValue element = thisObj->get(exec, k);
417        if (exec->hadException())
418            return JSValue::encode(jsUndefined());
419        if (!element.isUndefinedOrNull())
420            stringJoiner.append(element.toWTFStringInline(exec));
421        else
422            stringJoiner.append(String());
423    }
424
425    return JSValue::encode(stringJoiner.join(exec));
426}
427
428EncodedJSValue JSC_HOST_CALL arrayProtoFuncConcat(ExecState* exec)
429{
430    JSValue thisValue = exec->thisValue().toThis(exec, StrictMode);
431    size_t argCount = exec->argumentCount();
432    JSValue curArg = thisValue.toObject(exec);
433    Checked<unsigned, RecordOverflow> finalArraySize = 0;
434
435    for (size_t i = 0;;) {
436        if (JSArray* currentArray = jsDynamicCast<JSArray*>(curArg)) {
437            finalArraySize += getLength(exec, currentArray);
438            if (exec->hadException())
439                return JSValue::encode(jsUndefined());
440        } else
441            finalArraySize++;
442        if (i == argCount)
443            break;
444        curArg = exec->uncheckedArgument(i);
445        ++i;
446    }
447
448    if (finalArraySize.hasOverflowed())
449        return JSValue::encode(throwOutOfMemoryError(exec));
450
451    JSArray* arr = constructEmptyArray(exec, nullptr, finalArraySize.unsafeGet());
452    if (exec->hadException())
453        return JSValue::encode(jsUndefined());
454
455    curArg = thisValue.toObject(exec);
456    unsigned n = 0;
457    for (size_t i = 0;;) {
458        if (JSArray* currentArray = jsDynamicCast<JSArray*>(curArg)) {
459            unsigned length = getLength(exec, currentArray);
460            if (exec->hadException())
461                return JSValue::encode(jsUndefined());
462            for (unsigned k = 0; k < length; ++k) {
463                JSValue v = getProperty(exec, currentArray, k);
464                if (exec->hadException())
465                    return JSValue::encode(jsUndefined());
466                if (v)
467                    arr->putDirectIndex(exec, n, v);
468                n++;
469            }
470        } else {
471            arr->putDirectIndex(exec, n, curArg);
472            n++;
473        }
474        if (i == argCount)
475            break;
476        curArg = exec->uncheckedArgument(i);
477        ++i;
478    }
479    arr->setLength(exec, n);
480    return JSValue::encode(arr);
481}
482
483EncodedJSValue JSC_HOST_CALL arrayProtoFuncPop(ExecState* exec)
484{
485    JSValue thisValue = exec->thisValue().toThis(exec, StrictMode);
486
487    if (isJSArray(thisValue))
488        return JSValue::encode(asArray(thisValue)->pop(exec));
489
490    JSObject* thisObj = thisValue.toObject(exec);
491    unsigned length = getLength(exec, thisObj);
492    if (exec->hadException())
493        return JSValue::encode(jsUndefined());
494
495    JSValue result;
496    if (length == 0) {
497        putLength(exec, thisObj, jsNumber(length));
498        result = jsUndefined();
499    } else {
500        result = thisObj->get(exec, length - 1);
501        if (exec->hadException())
502            return JSValue::encode(jsUndefined());
503        if (!thisObj->methodTable(exec->vm())->deletePropertyByIndex(thisObj, exec, length - 1)) {
504            throwTypeError(exec, ASCIILiteral("Unable to delete property."));
505            return JSValue::encode(jsUndefined());
506        }
507        putLength(exec, thisObj, jsNumber(length - 1));
508    }
509    return JSValue::encode(result);
510}
511
512EncodedJSValue JSC_HOST_CALL arrayProtoFuncPush(ExecState* exec)
513{
514    JSValue thisValue = exec->thisValue().toThis(exec, StrictMode);
515
516    if (isJSArray(thisValue) && exec->argumentCount() == 1) {
517        JSArray* array = asArray(thisValue);
518        array->push(exec, exec->uncheckedArgument(0));
519        return JSValue::encode(jsNumber(array->length()));
520    }
521
522    JSObject* thisObj = thisValue.toObject(exec);
523    unsigned length = getLength(exec, thisObj);
524    if (exec->hadException())
525        return JSValue::encode(jsUndefined());
526
527    for (unsigned n = 0; n < exec->argumentCount(); n++) {
528        // Check for integer overflow; where safe we can do a fast put by index.
529        if (length + n >= length)
530            thisObj->methodTable()->putByIndex(thisObj, exec, length + n, exec->uncheckedArgument(n), true);
531        else {
532            PutPropertySlot slot(thisObj);
533            Identifier propertyName(exec, JSValue(static_cast<int64_t>(length) + static_cast<int64_t>(n)).toWTFString(exec));
534            thisObj->methodTable()->put(thisObj, exec, propertyName, exec->uncheckedArgument(n), slot);
535        }
536        if (exec->hadException())
537            return JSValue::encode(jsUndefined());
538    }
539
540    JSValue newLength(static_cast<int64_t>(length) + static_cast<int64_t>(exec->argumentCount()));
541    putLength(exec, thisObj, newLength);
542    return JSValue::encode(newLength);
543}
544
545EncodedJSValue JSC_HOST_CALL arrayProtoFuncReverse(ExecState* exec)
546{
547    JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
548    unsigned length = getLength(exec, thisObj);
549    if (exec->hadException())
550        return JSValue::encode(jsUndefined());
551
552    unsigned middle = length / 2;
553    for (unsigned k = 0; k < middle; k++) {
554        unsigned lk1 = length - k - 1;
555        JSValue obj2 = getProperty(exec, thisObj, lk1);
556        if (exec->hadException())
557            return JSValue::encode(jsUndefined());
558        JSValue obj = getProperty(exec, thisObj, k);
559        if (exec->hadException())
560            return JSValue::encode(jsUndefined());
561
562        if (obj2) {
563            thisObj->methodTable(exec->vm())->putByIndex(thisObj, exec, k, obj2, true);
564            if (exec->hadException())
565                return JSValue::encode(jsUndefined());
566        } else if (!thisObj->methodTable(exec->vm())->deletePropertyByIndex(thisObj, exec, k)) {
567            throwTypeError(exec, ASCIILiteral("Unable to delete property."));
568            return JSValue::encode(jsUndefined());
569        }
570
571        if (obj) {
572            thisObj->methodTable(exec->vm())->putByIndex(thisObj, exec, lk1, obj, true);
573            if (exec->hadException())
574                return JSValue::encode(jsUndefined());
575        } else if (!thisObj->methodTable(exec->vm())->deletePropertyByIndex(thisObj, exec, lk1)) {
576            throwTypeError(exec, ASCIILiteral("Unable to delete property."));
577            return JSValue::encode(jsUndefined());
578        }
579    }
580    return JSValue::encode(thisObj);
581}
582
583EncodedJSValue JSC_HOST_CALL arrayProtoFuncShift(ExecState* exec)
584{
585    JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
586    unsigned length = getLength(exec, thisObj);
587    if (exec->hadException())
588        return JSValue::encode(jsUndefined());
589
590    JSValue result;
591    if (length == 0) {
592        putLength(exec, thisObj, jsNumber(length));
593        result = jsUndefined();
594    } else {
595        result = thisObj->get(exec, 0);
596        shift<JSArray::ShiftCountForShift>(exec, thisObj, 0, 1, 0, length);
597        if (exec->hadException())
598            return JSValue::encode(jsUndefined());
599        putLength(exec, thisObj, jsNumber(length - 1));
600    }
601    return JSValue::encode(result);
602}
603
604EncodedJSValue JSC_HOST_CALL arrayProtoFuncSlice(ExecState* exec)
605{
606    // http://developer.netscape.com/docs/manuals/js/client/jsref/array.htm#1193713 or 15.4.4.10
607    JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
608    unsigned length = getLength(exec, thisObj);
609    if (exec->hadException())
610        return JSValue::encode(jsUndefined());
611
612    unsigned begin = argumentClampedIndexFromStartOrEnd(exec, 0, length);
613    unsigned end = argumentClampedIndexFromStartOrEnd(exec, 1, length, length);
614
615    JSArray* result = constructEmptyArray(exec, nullptr, end - begin);
616
617    unsigned n = 0;
618    for (unsigned k = begin; k < end; k++, n++) {
619        JSValue v = getProperty(exec, thisObj, k);
620        if (exec->hadException())
621            return JSValue::encode(jsUndefined());
622        if (v)
623            result->putDirectIndex(exec, n, v);
624    }
625    result->setLength(exec, n);
626    return JSValue::encode(result);
627}
628
629inline JSValue getOrHole(JSObject* obj, ExecState* exec, unsigned propertyName)
630{
631    PropertySlot slot(obj);
632    if (obj->getPropertySlot(exec, propertyName, slot))
633        return slot.getValue(exec, propertyName);
634
635    return JSValue();
636}
637
638static bool attemptFastSort(ExecState* exec, JSObject* thisObj, JSValue function, CallData& callData, CallType& callType)
639{
640    if (thisObj->classInfo() != JSArray::info()
641        || asArray(thisObj)->hasSparseMap()
642        || shouldUseSlowPut(thisObj->indexingType()))
643        return false;
644
645    if (isNumericCompareFunction(exec, function, callType, callData))
646        asArray(thisObj)->sortNumeric(exec, function, callType, callData);
647    else if (callType != CallTypeNone)
648        asArray(thisObj)->sort(exec, function, callType, callData);
649    else
650        asArray(thisObj)->sort(exec);
651    return true;
652}
653
654static bool performSlowSort(ExecState* exec, JSObject* thisObj, unsigned length, JSValue function, CallData& callData, CallType& callType)
655{
656    // "Min" sort. Not the fastest, but definitely less code than heapsort
657    // or quicksort, and much less swapping than bubblesort/insertionsort.
658    for (unsigned i = 0; i < length - 1; ++i) {
659        JSValue iObj = getOrHole(thisObj, exec, i);
660        if (exec->hadException())
661            return false;
662        unsigned themin = i;
663        JSValue minObj = iObj;
664        for (unsigned j = i + 1; j < length; ++j) {
665            JSValue jObj = getOrHole(thisObj, exec, j);
666            if (exec->hadException())
667                return false;
668            double compareResult;
669            if (!jObj)
670                compareResult = 1;
671            else if (!minObj)
672                compareResult = -1;
673            else if (jObj.isUndefined())
674                compareResult = 1; // don't check minObj because there's no need to differentiate == (0) from > (1)
675            else if (minObj.isUndefined())
676                compareResult = -1;
677            else if (callType != CallTypeNone) {
678                MarkedArgumentBuffer l;
679                l.append(jObj);
680                l.append(minObj);
681                compareResult = call(exec, function, callType, callData, jsUndefined(), l).toNumber(exec);
682            } else
683                compareResult = codePointCompareLessThan(jObj.toWTFStringInline(exec), minObj.toWTFStringInline(exec)) ? -1 : 1;
684
685            if (compareResult < 0) {
686                themin = j;
687                minObj = jObj;
688            }
689        }
690        // Swap themin and i
691        if (themin > i) {
692            if (minObj) {
693                thisObj->methodTable(exec->vm())->putByIndex(thisObj, exec, i, minObj, true);
694                if (exec->hadException())
695                    return false;
696            } else if (!thisObj->methodTable(exec->vm())->deletePropertyByIndex(thisObj, exec, i)) {
697                throwTypeError(exec, "Unable to delete property.");
698                return false;
699            }
700            if (iObj) {
701                thisObj->methodTable(exec->vm())->putByIndex(thisObj, exec, themin, iObj, true);
702                if (exec->hadException())
703                    return false;
704            } else if (!thisObj->methodTable(exec->vm())->deletePropertyByIndex(thisObj, exec, themin)) {
705                throwTypeError(exec, "Unable to delete property.");
706                return false;
707            }
708        }
709    }
710    return true;
711}
712
713EncodedJSValue JSC_HOST_CALL arrayProtoFuncSort(ExecState* exec)
714{
715    JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
716    unsigned length = getLength(exec, thisObj);
717    if (!length || exec->hadException())
718        return JSValue::encode(thisObj);
719
720    JSValue function = exec->argument(0);
721    CallData callData;
722    CallType callType = getCallData(function, callData);
723
724    if (attemptFastSort(exec, thisObj, function, callData, callType))
725        return JSValue::encode(thisObj);
726
727    // Assume that for small-ish arrays, doing the slow sort directly is better.
728    if (length < 1000)
729        return performSlowSort(exec, thisObj, length, function, callData, callType) ? JSValue::encode(thisObj) : JSValue::encode(jsUndefined());
730
731    JSGlobalObject* globalObject = JSGlobalObject::create(
732        exec->vm(), JSGlobalObject::createStructure(exec->vm(), jsNull()));
733    JSArray* flatArray = constructEmptyArray(globalObject->globalExec(), nullptr);
734    if (exec->hadException())
735        return JSValue::encode(jsUndefined());
736
737    PropertyNameArray nameArray(exec);
738    thisObj->methodTable(exec->vm())->getPropertyNames(thisObj, exec, nameArray, IncludeDontEnumProperties);
739    if (exec->hadException())
740        return JSValue::encode(jsUndefined());
741
742    Vector<uint32_t, 0, UnsafeVectorOverflow> keys;
743    for (size_t i = 0; i < nameArray.size(); ++i) {
744        PropertyName name = nameArray[i];
745        uint32_t index = name.asIndex();
746        if (index == PropertyName::NotAnIndex)
747            continue;
748
749        JSValue value = getOrHole(thisObj, exec, index);
750        if (exec->hadException())
751            return JSValue::encode(jsUndefined());
752        if (!value)
753            continue;
754        keys.append(index);
755        flatArray->push(exec, value);
756        if (exec->hadException())
757            return JSValue::encode(jsUndefined());
758    }
759
760    if (!attemptFastSort(exec, flatArray, function, callData, callType)
761        && !performSlowSort(exec, flatArray, flatArray->length(), function, callData, callType))
762        return JSValue::encode(jsUndefined());
763
764    for (size_t i = 0; i < keys.size(); ++i) {
765        size_t index = keys[i];
766        if (index < flatArray->length())
767            continue;
768
769        if (!thisObj->methodTable(exec->vm())->deletePropertyByIndex(thisObj, exec, index)) {
770            throwTypeError(exec, "Unable to delete property.");
771            return JSValue::encode(jsUndefined());
772        }
773    }
774
775    for (size_t i = flatArray->length(); i--;) {
776        JSValue value = getOrHole(flatArray, exec, i);
777        RELEASE_ASSERT(value);
778        thisObj->methodTable(exec->vm())->putByIndex(thisObj, exec, i, value, true);
779        if (exec->hadException())
780            return JSValue::encode(jsUndefined());
781    }
782
783    return JSValue::encode(thisObj);
784}
785
786EncodedJSValue JSC_HOST_CALL arrayProtoFuncSplice(ExecState* exec)
787{
788    // 15.4.4.12
789
790    JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
791    unsigned length = getLength(exec, thisObj);
792    if (exec->hadException())
793        return JSValue::encode(jsUndefined());
794
795    if (!exec->argumentCount())
796        return JSValue::encode(constructEmptyArray(exec, nullptr));
797
798    unsigned begin = argumentClampedIndexFromStartOrEnd(exec, 0, length);
799
800    unsigned deleteCount = length - begin;
801    if (exec->argumentCount() > 1) {
802        double deleteDouble = exec->uncheckedArgument(1).toInteger(exec);
803        if (deleteDouble < 0)
804            deleteCount = 0;
805        else if (deleteDouble > length - begin)
806            deleteCount = length - begin;
807        else
808            deleteCount = static_cast<unsigned>(deleteDouble);
809    }
810
811    JSArray* resObj = JSArray::tryCreateUninitialized(exec->vm(), exec->lexicalGlobalObject()->arrayStructureForIndexingTypeDuringAllocation(ArrayWithUndecided), deleteCount);
812    if (!resObj)
813        return JSValue::encode(throwOutOfMemoryError(exec));
814
815    JSValue result = resObj;
816    VM& vm = exec->vm();
817    for (unsigned k = 0; k < deleteCount; k++) {
818        JSValue v = getProperty(exec, thisObj, k + begin);
819        if (exec->hadException())
820            return JSValue::encode(jsUndefined());
821        resObj->initializeIndex(vm, k, v);
822    }
823
824    unsigned additionalArgs = std::max<int>(exec->argumentCount() - 2, 0);
825    if (additionalArgs < deleteCount) {
826        shift<JSArray::ShiftCountForSplice>(exec, thisObj, begin, deleteCount, additionalArgs, length);
827        if (exec->hadException())
828            return JSValue::encode(jsUndefined());
829    } else if (additionalArgs > deleteCount) {
830        unshift<JSArray::ShiftCountForSplice>(exec, thisObj, begin, deleteCount, additionalArgs, length);
831        if (exec->hadException())
832            return JSValue::encode(jsUndefined());
833    }
834    for (unsigned k = 0; k < additionalArgs; ++k) {
835        thisObj->methodTable(exec->vm())->putByIndex(thisObj, exec, k + begin, exec->uncheckedArgument(k + 2), true);
836        if (exec->hadException())
837            return JSValue::encode(jsUndefined());
838    }
839
840    putLength(exec, thisObj, jsNumber(length - deleteCount + additionalArgs));
841    return JSValue::encode(result);
842}
843
844EncodedJSValue JSC_HOST_CALL arrayProtoFuncUnShift(ExecState* exec)
845{
846    // 15.4.4.13
847
848    JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
849    unsigned length = getLength(exec, thisObj);
850    if (exec->hadException())
851        return JSValue::encode(jsUndefined());
852
853    unsigned nrArgs = exec->argumentCount();
854    if (nrArgs) {
855        unshift<JSArray::ShiftCountForShift>(exec, thisObj, 0, 0, nrArgs, length);
856        if (exec->hadException())
857            return JSValue::encode(jsUndefined());
858    }
859    for (unsigned k = 0; k < nrArgs; ++k) {
860        thisObj->methodTable(exec->vm())->putByIndex(thisObj, exec, k, exec->uncheckedArgument(k), true);
861        if (exec->hadException())
862            return JSValue::encode(jsUndefined());
863    }
864    JSValue result = jsNumber(length + nrArgs);
865    putLength(exec, thisObj, result);
866    return JSValue::encode(result);
867}
868
869EncodedJSValue JSC_HOST_CALL arrayProtoFuncReduce(ExecState* exec)
870{
871    JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
872    unsigned length = getLength(exec, thisObj);
873    if (exec->hadException())
874        return JSValue::encode(jsUndefined());
875
876    JSValue function = exec->argument(0);
877    CallData callData;
878    CallType callType = getCallData(function, callData);
879    if (callType == CallTypeNone)
880        return throwVMTypeError(exec);
881
882    unsigned i = 0;
883    JSValue rv;
884    if (!length && exec->argumentCount() == 1)
885        return throwVMTypeError(exec);
886
887    JSArray* array = 0;
888    if (isJSArray(thisObj))
889        array = asArray(thisObj);
890
891    if (exec->argumentCount() >= 2)
892        rv = exec->uncheckedArgument(1);
893    else if (array && array->canGetIndexQuickly(0)) {
894        rv = array->getIndexQuickly(0);
895        i = 1;
896    } else {
897        for (i = 0; i < length; i++) {
898            rv = getProperty(exec, thisObj, i);
899            if (exec->hadException())
900                return JSValue::encode(jsUndefined());
901            if (rv)
902                break;
903        }
904        if (!rv)
905            return throwVMTypeError(exec);
906        i++;
907    }
908
909    if (callType == CallTypeJS && array) {
910        CachedCall cachedCall(exec, jsCast<JSFunction*>(function), 4);
911        for (; i < length && !exec->hadException(); ++i) {
912            cachedCall.setThis(jsUndefined());
913            cachedCall.setArgument(0, rv);
914            JSValue v;
915            if (LIKELY(array->canGetIndexQuickly(i)))
916                v = array->getIndexQuickly(i);
917            else
918                break; // length has been made unsafe while we enumerate fallback to slow path
919            cachedCall.setArgument(1, v);
920            cachedCall.setArgument(2, jsNumber(i));
921            cachedCall.setArgument(3, array);
922            rv = cachedCall.call();
923        }
924        if (i == length) // only return if we reached the end of the array
925            return JSValue::encode(rv);
926    }
927
928    for (; i < length && !exec->hadException(); ++i) {
929        JSValue prop = getProperty(exec, thisObj, i);
930        if (exec->hadException())
931            return JSValue::encode(jsUndefined());
932        if (!prop)
933            continue;
934
935        MarkedArgumentBuffer eachArguments;
936        eachArguments.append(rv);
937        eachArguments.append(prop);
938        eachArguments.append(jsNumber(i));
939        eachArguments.append(thisObj);
940
941        rv = call(exec, function, callType, callData, jsUndefined(), eachArguments);
942    }
943    return JSValue::encode(rv);
944}
945
946EncodedJSValue JSC_HOST_CALL arrayProtoFuncReduceRight(ExecState* exec)
947{
948    JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
949    unsigned length = getLength(exec, thisObj);
950    if (exec->hadException())
951        return JSValue::encode(jsUndefined());
952
953    JSValue function = exec->argument(0);
954    CallData callData;
955    CallType callType = getCallData(function, callData);
956    if (callType == CallTypeNone)
957        return throwVMTypeError(exec);
958
959    unsigned i = 0;
960    JSValue rv;
961    if (!length && exec->argumentCount() == 1)
962        return throwVMTypeError(exec);
963
964    JSArray* array = 0;
965    if (isJSArray(thisObj))
966        array = asArray(thisObj);
967
968    if (exec->argumentCount() >= 2)
969        rv = exec->uncheckedArgument(1);
970    else if (array && array->canGetIndexQuickly(length - 1)) {
971        rv = array->getIndexQuickly(length - 1);
972        i = 1;
973    } else {
974        for (i = 0; i < length; i++) {
975            rv = getProperty(exec, thisObj, length - i - 1);
976            if (exec->hadException())
977                return JSValue::encode(jsUndefined());
978            if (rv)
979                break;
980        }
981        if (!rv)
982            return throwVMTypeError(exec);
983        i++;
984    }
985
986    if (callType == CallTypeJS && array) {
987        CachedCall cachedCall(exec, jsCast<JSFunction*>(function), 4);
988        for (; i < length && !exec->hadException(); ++i) {
989            unsigned idx = length - i - 1;
990            cachedCall.setThis(jsUndefined());
991            cachedCall.setArgument(0, rv);
992            if (UNLIKELY(!array->canGetIndexQuickly(idx)))
993                break; // length has been made unsafe while we enumerate fallback to slow path
994            cachedCall.setArgument(1, array->getIndexQuickly(idx));
995            cachedCall.setArgument(2, jsNumber(idx));
996            cachedCall.setArgument(3, array);
997            rv = cachedCall.call();
998        }
999        if (i == length) // only return if we reached the end of the array
1000            return JSValue::encode(rv);
1001    }
1002
1003    for (; i < length && !exec->hadException(); ++i) {
1004        unsigned idx = length - i - 1;
1005        JSValue prop = getProperty(exec, thisObj, idx);
1006        if (exec->hadException())
1007            return JSValue::encode(jsUndefined());
1008        if (!prop)
1009            continue;
1010
1011        MarkedArgumentBuffer eachArguments;
1012        eachArguments.append(rv);
1013        eachArguments.append(prop);
1014        eachArguments.append(jsNumber(idx));
1015        eachArguments.append(thisObj);
1016
1017        rv = call(exec, function, callType, callData, jsUndefined(), eachArguments);
1018    }
1019    return JSValue::encode(rv);
1020}
1021
1022EncodedJSValue JSC_HOST_CALL arrayProtoFuncIndexOf(ExecState* exec)
1023{
1024    // 15.4.4.14
1025    JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
1026    unsigned length = getLength(exec, thisObj);
1027    if (exec->hadException())
1028        return JSValue::encode(jsUndefined());
1029
1030    unsigned index = argumentClampedIndexFromStartOrEnd(exec, 1, length);
1031    JSValue searchElement = exec->argument(0);
1032    for (; index < length; ++index) {
1033        JSValue e = getProperty(exec, thisObj, index);
1034        if (exec->hadException())
1035            return JSValue::encode(jsUndefined());
1036        if (!e)
1037            continue;
1038        if (JSValue::strictEqual(exec, searchElement, e))
1039            return JSValue::encode(jsNumber(index));
1040    }
1041
1042    return JSValue::encode(jsNumber(-1));
1043}
1044
1045EncodedJSValue JSC_HOST_CALL arrayProtoFuncLastIndexOf(ExecState* exec)
1046{
1047    // 15.4.4.15
1048    JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
1049    unsigned length = getLength(exec, thisObj);
1050    if (!length)
1051        return JSValue::encode(jsNumber(-1));
1052
1053    unsigned index = length - 1;
1054    if (exec->argumentCount() >= 2) {
1055        JSValue fromValue = exec->uncheckedArgument(1);
1056        double fromDouble = fromValue.toInteger(exec);
1057        if (fromDouble < 0) {
1058            fromDouble += length;
1059            if (fromDouble < 0)
1060                return JSValue::encode(jsNumber(-1));
1061        }
1062        if (fromDouble < length)
1063            index = static_cast<unsigned>(fromDouble);
1064    }
1065
1066    JSValue searchElement = exec->argument(0);
1067    do {
1068        RELEASE_ASSERT(index < length);
1069        JSValue e = getProperty(exec, thisObj, index);
1070        if (exec->hadException())
1071            return JSValue::encode(jsUndefined());
1072        if (!e)
1073            continue;
1074        if (JSValue::strictEqual(exec, searchElement, e))
1075            return JSValue::encode(jsNumber(index));
1076    } while (index--);
1077
1078    return JSValue::encode(jsNumber(-1));
1079}
1080
1081EncodedJSValue JSC_HOST_CALL arrayProtoFuncValues(ExecState* exec)
1082{
1083    JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
1084    return JSValue::encode(JSArrayIterator::create(exec, exec->callee()->globalObject()->arrayIteratorStructure(), ArrayIterateValue, thisObj));
1085}
1086
1087EncodedJSValue JSC_HOST_CALL arrayProtoFuncEntries(ExecState* exec)
1088{
1089    JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
1090    return JSValue::encode(JSArrayIterator::create(exec, exec->callee()->globalObject()->arrayIteratorStructure(), ArrayIterateKeyValue, thisObj));
1091}
1092
1093EncodedJSValue JSC_HOST_CALL arrayProtoFuncKeys(ExecState* exec)
1094{
1095    JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
1096    return JSValue::encode(JSArrayIterator::create(exec, exec->callee()->globalObject()->arrayIteratorStructure(), ArrayIterateKey, thisObj));
1097}
1098
1099} // namespace JSC
1100