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