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