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