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