put_by_val_direct need to check the property is index or not for using putDirect...
[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 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
45 namespace JSC {
46
47 EncodedJSValue JSC_HOST_CALL arrayProtoFuncToString(ExecState*);
48 EncodedJSValue JSC_HOST_CALL arrayProtoFuncToLocaleString(ExecState*);
49 EncodedJSValue JSC_HOST_CALL arrayProtoFuncConcat(ExecState*);
50 EncodedJSValue JSC_HOST_CALL arrayProtoFuncJoin(ExecState*);
51 EncodedJSValue JSC_HOST_CALL arrayProtoFuncPop(ExecState*);
52 EncodedJSValue JSC_HOST_CALL arrayProtoFuncPush(ExecState*);
53 EncodedJSValue JSC_HOST_CALL arrayProtoFuncReverse(ExecState*);
54 EncodedJSValue JSC_HOST_CALL arrayProtoFuncShift(ExecState*);
55 EncodedJSValue JSC_HOST_CALL arrayProtoFuncSlice(ExecState*);
56 EncodedJSValue JSC_HOST_CALL arrayProtoFuncSort(ExecState*);
57 EncodedJSValue JSC_HOST_CALL arrayProtoFuncSplice(ExecState*);
58 EncodedJSValue JSC_HOST_CALL arrayProtoFuncUnShift(ExecState*);
59 EncodedJSValue JSC_HOST_CALL arrayProtoFuncIndexOf(ExecState*);
60 EncodedJSValue JSC_HOST_CALL arrayProtoFuncReduce(ExecState*);
61 EncodedJSValue JSC_HOST_CALL arrayProtoFuncReduceRight(ExecState*);
62 EncodedJSValue JSC_HOST_CALL arrayProtoFuncLastIndexOf(ExecState*);
63 EncodedJSValue JSC_HOST_CALL arrayProtoFuncValues(ExecState*);
64 EncodedJSValue JSC_HOST_CALL arrayProtoFuncKeys(ExecState*);
65 EncodedJSValue JSC_HOST_CALL arrayProtoFuncEntries(ExecState*);
66
67 }
68
69 #include "ArrayPrototype.lut.h"
70
71 namespace JSC {
72
73 static 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
90 const ClassInfo ArrayPrototype::s_info = {"Array", &JSArray::s_info, &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
123 ArrayPrototype* 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
131 ArrayPrototype::ArrayPrototype(VM& vm, Structure* structure)
132     : JSArray(vm, structure, 0)
133 {
134 }
135
136 void 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
144 bool ArrayPrototype::getOwnPropertySlot(JSObject* object, ExecState* exec, PropertyName propertyName, PropertySlot& slot)
145 {
146     return getStaticFunctionSlot<JSArray>(exec, arrayPrototypeTable, jsCast<ArrayPrototype*>(object), propertyName, slot);
147 }
148
149 // ------------------------------ Array Functions ----------------------------
150
151 // Helper function
152 static 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
160 static 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
167 static 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
173 static 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.
202 template<JSArray::ShiftCountMode shiftCountMode>
203 void 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 }
240 template<JSArray::ShiftCountMode shiftCountMode>
241 void 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
279 EncodedJSValue 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
337 EncodedJSValue 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
380 EncodedJSValue 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
428 EncodedJSValue 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
483 EncodedJSValue 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
512 EncodedJSValue 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
545 EncodedJSValue 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
583 EncodedJSValue 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
604 EncodedJSValue 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
629 inline 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
638 static 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
654 static 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, ASCIILiteral("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, ASCIILiteral("Unable to delete property."));
706                 return false;
707             }
708         }
709     }
710     return true;
711 }
712
713 EncodedJSValue 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         Optional<uint32_t> optionalIndex = name.asIndex();
746         if (!optionalIndex)
747             continue;
748
749         uint32_t index = optionalIndex.value();
750         JSValue value = getOrHole(thisObj, exec, index);
751         if (exec->hadException())
752             return JSValue::encode(jsUndefined());
753         if (!value)
754             continue;
755         keys.append(index);
756         flatArray->push(exec, value);
757         if (exec->hadException())
758             return JSValue::encode(jsUndefined());
759     }
760     
761     if (!attemptFastSort(exec, flatArray, function, callData, callType)
762         && !performSlowSort(exec, flatArray, flatArray->length(), function, callData, callType))
763         return JSValue::encode(jsUndefined());
764     
765     for (size_t i = 0; i < keys.size(); ++i) {
766         size_t index = keys[i];
767         if (index < flatArray->length())
768             continue;
769         
770         if (!thisObj->methodTable(exec->vm())->deletePropertyByIndex(thisObj, exec, index)) {
771             throwTypeError(exec, ASCIILiteral("Unable to delete property."));
772             return JSValue::encode(jsUndefined());
773         }
774     }
775     
776     for (size_t i = flatArray->length(); i--;) {
777         JSValue value = getOrHole(flatArray, exec, i);
778         RELEASE_ASSERT(value);
779         thisObj->methodTable(exec->vm())->putByIndex(thisObj, exec, i, value, true);
780         if (exec->hadException())
781             return JSValue::encode(jsUndefined());
782     }
783     
784     return JSValue::encode(thisObj);
785 }
786
787 EncodedJSValue JSC_HOST_CALL arrayProtoFuncSplice(ExecState* exec)
788 {
789     // 15.4.4.12
790
791     JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
792     unsigned length = getLength(exec, thisObj);
793     if (exec->hadException())
794         return JSValue::encode(jsUndefined());
795     
796     if (!exec->argumentCount())
797         return JSValue::encode(constructEmptyArray(exec, nullptr));
798
799     unsigned begin = argumentClampedIndexFromStartOrEnd(exec, 0, length);
800
801     unsigned deleteCount = length - begin;
802     if (exec->argumentCount() > 1) {
803         double deleteDouble = exec->uncheckedArgument(1).toInteger(exec);
804         if (deleteDouble < 0)
805             deleteCount = 0;
806         else if (deleteDouble > length - begin)
807             deleteCount = length - begin;
808         else
809             deleteCount = static_cast<unsigned>(deleteDouble);
810     }
811
812     JSArray* resObj = JSArray::tryCreateUninitialized(exec->vm(), exec->lexicalGlobalObject()->arrayStructureForIndexingTypeDuringAllocation(ArrayWithUndecided), deleteCount);
813     if (!resObj)
814         return JSValue::encode(throwOutOfMemoryError(exec));
815
816     JSValue result = resObj;
817     VM& vm = exec->vm();
818     for (unsigned k = 0; k < deleteCount; k++) {
819         JSValue v = getProperty(exec, thisObj, k + begin);
820         if (exec->hadException())
821             return JSValue::encode(jsUndefined());
822         resObj->initializeIndex(vm, k, v);
823     }
824
825     unsigned additionalArgs = std::max<int>(exec->argumentCount() - 2, 0);
826     if (additionalArgs < deleteCount) {
827         shift<JSArray::ShiftCountForSplice>(exec, thisObj, begin, deleteCount, additionalArgs, length);
828         if (exec->hadException())
829             return JSValue::encode(jsUndefined());
830     } else if (additionalArgs > deleteCount) {
831         unshift<JSArray::ShiftCountForSplice>(exec, thisObj, begin, deleteCount, additionalArgs, length);
832         if (exec->hadException())
833             return JSValue::encode(jsUndefined());
834     }
835     for (unsigned k = 0; k < additionalArgs; ++k) {
836         thisObj->methodTable(exec->vm())->putByIndex(thisObj, exec, k + begin, exec->uncheckedArgument(k + 2), true);
837         if (exec->hadException())
838             return JSValue::encode(jsUndefined());
839     }
840
841     putLength(exec, thisObj, jsNumber(length - deleteCount + additionalArgs));
842     return JSValue::encode(result);
843 }
844
845 EncodedJSValue JSC_HOST_CALL arrayProtoFuncUnShift(ExecState* exec)
846 {
847     // 15.4.4.13
848
849     JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
850     unsigned length = getLength(exec, thisObj);
851     if (exec->hadException())
852         return JSValue::encode(jsUndefined());
853
854     unsigned nrArgs = exec->argumentCount();
855     if (nrArgs) {
856         unshift<JSArray::ShiftCountForShift>(exec, thisObj, 0, 0, nrArgs, length);
857         if (exec->hadException())
858             return JSValue::encode(jsUndefined());
859     }
860     for (unsigned k = 0; k < nrArgs; ++k) {
861         thisObj->methodTable(exec->vm())->putByIndex(thisObj, exec, k, exec->uncheckedArgument(k), true);
862         if (exec->hadException())
863             return JSValue::encode(jsUndefined());
864     }
865     JSValue result = jsNumber(length + nrArgs);
866     putLength(exec, thisObj, result);
867     return JSValue::encode(result);
868 }
869
870 EncodedJSValue JSC_HOST_CALL arrayProtoFuncReduce(ExecState* exec)
871 {
872     JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
873     unsigned length = getLength(exec, thisObj);
874     if (exec->hadException())
875         return JSValue::encode(jsUndefined());
876
877     JSValue function = exec->argument(0);
878     CallData callData;
879     CallType callType = getCallData(function, callData);
880     if (callType == CallTypeNone)
881         return throwVMTypeError(exec);
882
883     unsigned i = 0;
884     JSValue rv;
885     if (!length && exec->argumentCount() == 1)
886         return throwVMTypeError(exec);
887
888     JSArray* array = 0;
889     if (isJSArray(thisObj))
890         array = asArray(thisObj);
891
892     if (exec->argumentCount() >= 2)
893         rv = exec->uncheckedArgument(1);
894     else if (array && array->canGetIndexQuickly(0)) {
895         rv = array->getIndexQuickly(0);
896         i = 1;
897     } else {
898         for (i = 0; i < length; i++) {
899             rv = getProperty(exec, thisObj, i);
900             if (exec->hadException())
901                 return JSValue::encode(jsUndefined());
902             if (rv)
903                 break;
904         }
905         if (!rv)
906             return throwVMTypeError(exec);
907         i++;
908     }
909
910     if (callType == CallTypeJS && array) {
911         CachedCall cachedCall(exec, jsCast<JSFunction*>(function), 4);
912         for (; i < length && !exec->hadException(); ++i) {
913             cachedCall.setThis(jsUndefined());
914             cachedCall.setArgument(0, rv);
915             JSValue v;
916             if (LIKELY(array->canGetIndexQuickly(i)))
917                 v = array->getIndexQuickly(i);
918             else
919                 break; // length has been made unsafe while we enumerate fallback to slow path
920             cachedCall.setArgument(1, v);
921             cachedCall.setArgument(2, jsNumber(i));
922             cachedCall.setArgument(3, array);
923             rv = cachedCall.call();
924         }
925         if (i == length) // only return if we reached the end of the array
926             return JSValue::encode(rv);
927     }
928
929     for (; i < length && !exec->hadException(); ++i) {
930         JSValue prop = getProperty(exec, thisObj, i);
931         if (exec->hadException())
932             return JSValue::encode(jsUndefined());
933         if (!prop)
934             continue;
935         
936         MarkedArgumentBuffer eachArguments;
937         eachArguments.append(rv);
938         eachArguments.append(prop);
939         eachArguments.append(jsNumber(i));
940         eachArguments.append(thisObj);
941         
942         rv = call(exec, function, callType, callData, jsUndefined(), eachArguments);
943     }
944     return JSValue::encode(rv);
945 }
946
947 EncodedJSValue JSC_HOST_CALL arrayProtoFuncReduceRight(ExecState* exec)
948 {
949     JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
950     unsigned length = getLength(exec, thisObj);
951     if (exec->hadException())
952         return JSValue::encode(jsUndefined());
953
954     JSValue function = exec->argument(0);
955     CallData callData;
956     CallType callType = getCallData(function, callData);
957     if (callType == CallTypeNone)
958         return throwVMTypeError(exec);
959     
960     unsigned i = 0;
961     JSValue rv;
962     if (!length && exec->argumentCount() == 1)
963         return throwVMTypeError(exec);
964
965     JSArray* array = 0;
966     if (isJSArray(thisObj))
967         array = asArray(thisObj);
968     
969     if (exec->argumentCount() >= 2)
970         rv = exec->uncheckedArgument(1);
971     else if (array && array->canGetIndexQuickly(length - 1)) {
972         rv = array->getIndexQuickly(length - 1);
973         i = 1;
974     } else {
975         for (i = 0; i < length; i++) {
976             rv = getProperty(exec, thisObj, length - i - 1);
977             if (exec->hadException())
978                 return JSValue::encode(jsUndefined());
979             if (rv)
980                 break;
981         }
982         if (!rv)
983             return throwVMTypeError(exec);
984         i++;
985     }
986     
987     if (callType == CallTypeJS && array) {
988         CachedCall cachedCall(exec, jsCast<JSFunction*>(function), 4);
989         for (; i < length && !exec->hadException(); ++i) {
990             unsigned idx = length - i - 1;
991             cachedCall.setThis(jsUndefined());
992             cachedCall.setArgument(0, rv);
993             if (UNLIKELY(!array->canGetIndexQuickly(idx)))
994                 break; // length has been made unsafe while we enumerate fallback to slow path
995             cachedCall.setArgument(1, array->getIndexQuickly(idx));
996             cachedCall.setArgument(2, jsNumber(idx));
997             cachedCall.setArgument(3, array);
998             rv = cachedCall.call();
999         }
1000         if (i == length) // only return if we reached the end of the array
1001             return JSValue::encode(rv);
1002     }
1003     
1004     for (; i < length && !exec->hadException(); ++i) {
1005         unsigned idx = length - i - 1;
1006         JSValue prop = getProperty(exec, thisObj, idx);
1007         if (exec->hadException())
1008             return JSValue::encode(jsUndefined());
1009         if (!prop)
1010             continue;
1011         
1012         MarkedArgumentBuffer eachArguments;
1013         eachArguments.append(rv);
1014         eachArguments.append(prop);
1015         eachArguments.append(jsNumber(idx));
1016         eachArguments.append(thisObj);
1017         
1018         rv = call(exec, function, callType, callData, jsUndefined(), eachArguments);
1019     }
1020     return JSValue::encode(rv);        
1021 }
1022
1023 EncodedJSValue JSC_HOST_CALL arrayProtoFuncIndexOf(ExecState* exec)
1024 {
1025     // 15.4.4.14
1026     JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
1027     unsigned length = getLength(exec, thisObj);
1028     if (exec->hadException())
1029         return JSValue::encode(jsUndefined());
1030
1031     unsigned index = argumentClampedIndexFromStartOrEnd(exec, 1, length);
1032     JSValue searchElement = exec->argument(0);
1033     for (; index < length; ++index) {
1034         JSValue e = getProperty(exec, thisObj, index);
1035         if (exec->hadException())
1036             return JSValue::encode(jsUndefined());
1037         if (!e)
1038             continue;
1039         if (JSValue::strictEqual(exec, searchElement, e))
1040             return JSValue::encode(jsNumber(index));
1041     }
1042
1043     return JSValue::encode(jsNumber(-1));
1044 }
1045
1046 EncodedJSValue JSC_HOST_CALL arrayProtoFuncLastIndexOf(ExecState* exec)
1047 {
1048     // 15.4.4.15
1049     JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
1050     unsigned length = getLength(exec, thisObj);
1051     if (!length)
1052         return JSValue::encode(jsNumber(-1));
1053
1054     unsigned index = length - 1;
1055     if (exec->argumentCount() >= 2) {
1056         JSValue fromValue = exec->uncheckedArgument(1);
1057         double fromDouble = fromValue.toInteger(exec);
1058         if (fromDouble < 0) {
1059             fromDouble += length;
1060             if (fromDouble < 0)
1061                 return JSValue::encode(jsNumber(-1));
1062         }
1063         if (fromDouble < length)
1064             index = static_cast<unsigned>(fromDouble);
1065     }
1066
1067     JSValue searchElement = exec->argument(0);
1068     do {
1069         RELEASE_ASSERT(index < length);
1070         JSValue e = getProperty(exec, thisObj, index);
1071         if (exec->hadException())
1072             return JSValue::encode(jsUndefined());
1073         if (!e)
1074             continue;
1075         if (JSValue::strictEqual(exec, searchElement, e))
1076             return JSValue::encode(jsNumber(index));
1077     } while (index--);
1078
1079     return JSValue::encode(jsNumber(-1));
1080 }
1081
1082 EncodedJSValue JSC_HOST_CALL arrayProtoFuncValues(ExecState* exec)
1083 {
1084     JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
1085     return JSValue::encode(JSArrayIterator::create(exec, exec->callee()->globalObject()->arrayIteratorStructure(), ArrayIterateValue, thisObj));
1086 }
1087
1088 EncodedJSValue JSC_HOST_CALL arrayProtoFuncEntries(ExecState* exec)
1089 {
1090     JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
1091     return JSValue::encode(JSArrayIterator::create(exec, exec->callee()->globalObject()->arrayIteratorStructure(), ArrayIterateKeyValue, thisObj));
1092 }
1093     
1094 EncodedJSValue JSC_HOST_CALL arrayProtoFuncKeys(ExecState* exec)
1095 {
1096     JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
1097     return JSValue::encode(JSArrayIterator::create(exec, exec->callee()->globalObject()->arrayIteratorStructure(), ArrayIterateKey, thisObj));
1098 }
1099
1100 } // namespace JSC