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