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