2010-05-13 Maciej Stachowiak <mjs@apple.com>
[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
275         if (length) {
276             if (!array->canGetIndex(k)) 
277                 goto skipFirstLoop;
278             JSValue element = array->getIndex(k);
279             if (!element.isUndefinedOrNull())
280                 strBuffer.append(element.toString(exec));
281             k++;
282         }
283
284         if (separator.isNull()) {
285             for (; k < length; k++) {
286                 if (!array->canGetIndex(k))
287                     break;
288                 strBuffer.append(',');
289                 JSValue element = array->getIndex(k);
290                 if (!element.isUndefinedOrNull())
291                     strBuffer.append(element.toString(exec));
292             }
293         } else {
294             for (; k < length; k++) {
295                 if (!array->canGetIndex(k))
296                     break;
297                 strBuffer.append(separator);
298                 JSValue element = array->getIndex(k);
299                 if (!element.isUndefinedOrNull())
300                     strBuffer.append(element.toString(exec));
301             }
302         }
303     }
304  skipFirstLoop:
305     for (; k < length; k++) {
306         if (k >= 1) {
307             if (separator.isNull())
308                 strBuffer.append(',');
309             else
310                 strBuffer.append(separator);
311         }
312
313         JSValue element = thisObj->get(exec, k);
314         if (!element.isUndefinedOrNull())
315             strBuffer.append(element.toString(exec));
316     }
317     arrayVisitedElements.remove(thisObj);
318     return strBuffer.build(exec);
319 }
320
321 JSValue JSC_HOST_CALL arrayProtoFuncConcat(ExecState* exec, JSObject*, JSValue thisValue, const ArgList& args)
322 {
323     JSArray* arr = constructEmptyArray(exec);
324     int n = 0;
325     JSValue curArg = thisValue.toThisObject(exec);
326     ArgList::const_iterator it = args.begin();
327     ArgList::const_iterator end = args.end();
328     while (1) {
329         if (curArg.inherits(&JSArray::info)) {
330             unsigned length = curArg.get(exec, exec->propertyNames().length).toUInt32(exec);
331             JSObject* curObject = curArg.toObject(exec);
332             for (unsigned k = 0; k < length; ++k) {
333                 if (JSValue v = getProperty(exec, curObject, k))
334                     arr->put(exec, n, v);
335                 n++;
336             }
337         } else {
338             arr->put(exec, n, curArg);
339             n++;
340         }
341         if (it == end)
342             break;
343         curArg = (*it);
344         ++it;
345     }
346     arr->setLength(n);
347     return arr;
348 }
349
350 JSValue JSC_HOST_CALL arrayProtoFuncPop(ExecState* exec, JSObject*, JSValue thisValue, const ArgList&)
351 {
352     if (isJSArray(&exec->globalData(), thisValue))
353         return asArray(thisValue)->pop();
354
355     JSObject* thisObj = thisValue.toThisObject(exec);
356     JSValue result;
357     unsigned length = thisObj->get(exec, exec->propertyNames().length).toUInt32(exec);
358     if (length == 0) {
359         putProperty(exec, thisObj, exec->propertyNames().length, jsNumber(exec, length));
360         result = jsUndefined();
361     } else {
362         result = thisObj->get(exec, length - 1);
363         thisObj->deleteProperty(exec, length - 1);
364         putProperty(exec, thisObj, exec->propertyNames().length, jsNumber(exec, length - 1));
365     }
366     return result;
367 }
368
369 JSValue JSC_HOST_CALL arrayProtoFuncPush(ExecState* exec, JSObject*, JSValue thisValue, const ArgList& args)
370 {
371     if (isJSArray(&exec->globalData(), thisValue) && args.size() == 1) {
372         JSArray* array = asArray(thisValue);
373         array->push(exec, *args.begin());
374         return jsNumber(exec, array->length());
375     }
376
377     JSObject* thisObj = thisValue.toThisObject(exec);
378     unsigned length = thisObj->get(exec, exec->propertyNames().length).toUInt32(exec);
379     for (unsigned n = 0; n < args.size(); n++)
380         thisObj->put(exec, length + n, args.at(n));
381     length += args.size();
382     putProperty(exec, thisObj, exec->propertyNames().length, jsNumber(exec, length));
383     return jsNumber(exec, length);
384 }
385
386 JSValue JSC_HOST_CALL arrayProtoFuncReverse(ExecState* exec, JSObject*, JSValue thisValue, const ArgList&)
387 {
388     JSObject* thisObj = thisValue.toThisObject(exec);
389     unsigned length = thisObj->get(exec, exec->propertyNames().length).toUInt32(exec);
390     unsigned middle = length / 2;
391
392     for (unsigned k = 0; k < middle; k++) {
393         unsigned lk1 = length - k - 1;
394         JSValue obj2 = getProperty(exec, thisObj, lk1);
395         JSValue obj = getProperty(exec, thisObj, k);
396
397         if (obj2)
398             thisObj->put(exec, k, obj2);
399         else
400             thisObj->deleteProperty(exec, k);
401
402         if (obj)
403             thisObj->put(exec, lk1, obj);
404         else
405             thisObj->deleteProperty(exec, lk1);
406     }
407     return thisObj;
408 }
409
410 JSValue JSC_HOST_CALL arrayProtoFuncShift(ExecState* exec, JSObject*, JSValue thisValue, const ArgList&)
411 {
412     JSObject* thisObj = thisValue.toThisObject(exec);
413     JSValue result;
414
415     unsigned length = thisObj->get(exec, exec->propertyNames().length).toUInt32(exec);
416     if (length == 0) {
417         putProperty(exec, thisObj, exec->propertyNames().length, jsNumber(exec, length));
418         result = jsUndefined();
419     } else {
420         result = thisObj->get(exec, 0);
421         for (unsigned k = 1; k < length; k++) {
422             if (JSValue obj = getProperty(exec, thisObj, k))
423                 thisObj->put(exec, k - 1, obj);
424             else
425                 thisObj->deleteProperty(exec, k - 1);
426         }
427         thisObj->deleteProperty(exec, length - 1);
428         putProperty(exec, thisObj, exec->propertyNames().length, jsNumber(exec, length - 1));
429     }
430     return result;
431 }
432
433 JSValue JSC_HOST_CALL arrayProtoFuncSlice(ExecState* exec, JSObject*, JSValue thisValue, const ArgList& args)
434 {
435     // http://developer.netscape.com/docs/manuals/js/client/jsref/array.htm#1193713 or 15.4.4.10
436
437     JSObject* thisObj = thisValue.toThisObject(exec);
438
439     // We return a new array
440     JSArray* resObj = constructEmptyArray(exec);
441     JSValue result = resObj;
442     double begin = args.at(0).toInteger(exec);
443     unsigned length = thisObj->get(exec, exec->propertyNames().length).toUInt32(exec);
444     if (begin >= 0) {
445         if (begin > length)
446             begin = length;
447     } else {
448         begin += length;
449         if (begin < 0)
450             begin = 0;
451     }
452     double end;
453     if (args.at(1).isUndefined())
454         end = length;
455     else {
456         end = args.at(1).toInteger(exec);
457         if (end < 0) {
458             end += length;
459             if (end < 0)
460                 end = 0;
461         } else {
462             if (end > length)
463                 end = length;
464         }
465     }
466
467     int n = 0;
468     int b = static_cast<int>(begin);
469     int e = static_cast<int>(end);
470     for (int k = b; k < e; k++, n++) {
471         if (JSValue v = getProperty(exec, thisObj, k))
472             resObj->put(exec, n, v);
473     }
474     resObj->setLength(n);
475     return result;
476 }
477
478 JSValue JSC_HOST_CALL arrayProtoFuncSort(ExecState* exec, JSObject*, JSValue thisValue, const ArgList& args)
479 {
480     JSObject* thisObj = thisValue.toThisObject(exec);
481
482     JSValue function = args.at(0);
483     CallData callData;
484     CallType callType = function.getCallData(callData);
485
486     if (thisObj->classInfo() == &JSArray::info) {
487         if (isNumericCompareFunction(exec, callType, callData))
488             asArray(thisObj)->sortNumeric(exec, function, callType, callData);
489         else if (callType != CallTypeNone)
490             asArray(thisObj)->sort(exec, function, callType, callData);
491         else
492             asArray(thisObj)->sort(exec);
493         return thisObj;
494     }
495
496     unsigned length = thisObj->get(exec, exec->propertyNames().length).toUInt32(exec);
497
498     if (!length)
499         return thisObj;
500
501     // "Min" sort. Not the fastest, but definitely less code than heapsort
502     // or quicksort, and much less swapping than bubblesort/insertionsort.
503     for (unsigned i = 0; i < length - 1; ++i) {
504         JSValue iObj = thisObj->get(exec, i);
505         unsigned themin = i;
506         JSValue minObj = iObj;
507         for (unsigned j = i + 1; j < length; ++j) {
508             JSValue jObj = thisObj->get(exec, j);
509             double compareResult;
510             if (jObj.isUndefined())
511                 compareResult = 1; // don't check minObj because there's no need to differentiate == (0) from > (1)
512             else if (minObj.isUndefined())
513                 compareResult = -1;
514             else if (callType != CallTypeNone) {
515                 MarkedArgumentBuffer l;
516                 l.append(jObj);
517                 l.append(minObj);
518                 compareResult = call(exec, function, callType, callData, exec->globalThisValue(), l).toNumber(exec);
519             } else
520                 compareResult = (jObj.toString(exec) < minObj.toString(exec)) ? -1 : 1;
521
522             if (compareResult < 0) {
523                 themin = j;
524                 minObj = jObj;
525             }
526         }
527         // Swap themin and i
528         if (themin > i) {
529             thisObj->put(exec, i, minObj);
530             thisObj->put(exec, themin, iObj);
531         }
532     }
533     return thisObj;
534 }
535
536 JSValue JSC_HOST_CALL arrayProtoFuncSplice(ExecState* exec, JSObject*, JSValue thisValue, const ArgList& args)
537 {
538     JSObject* thisObj = thisValue.toThisObject(exec);
539
540     // 15.4.4.12
541     JSArray* resObj = constructEmptyArray(exec);
542     JSValue result = resObj;
543
544     // FIXME: Firefox returns an empty array.
545     if (!args.size())
546         return jsUndefined();
547
548     unsigned length = thisObj->get(exec, exec->propertyNames().length).toUInt32(exec);
549     double relativeBegin = args.at(0).toInteger(exec);
550     unsigned begin;
551     if (relativeBegin < 0) {
552         relativeBegin += length;
553         begin = (relativeBegin < 0) ? 0 : static_cast<unsigned>(relativeBegin);
554     } else
555         begin = std::min<unsigned>(static_cast<unsigned>(relativeBegin), length);
556
557     unsigned deleteCount;
558     if (args.size() > 1)
559         deleteCount = std::min<int>(std::max<int>(args.at(1).toUInt32(exec), 0), length - begin);
560     else
561         deleteCount = length - begin;
562
563     for (unsigned k = 0; k < deleteCount; k++) {
564         if (JSValue v = getProperty(exec, thisObj, k + begin))
565             resObj->put(exec, k, v);
566     }
567     resObj->setLength(deleteCount);
568
569     unsigned additionalArgs = std::max<int>(args.size() - 2, 0);
570     if (additionalArgs != deleteCount) {
571         if (additionalArgs < deleteCount) {
572             for (unsigned k = begin; k < length - deleteCount; ++k) {
573                 if (JSValue v = getProperty(exec, thisObj, k + deleteCount))
574                     thisObj->put(exec, k + additionalArgs, v);
575                 else
576                     thisObj->deleteProperty(exec, k + additionalArgs);
577             }
578             for (unsigned k = length; k > length - deleteCount + additionalArgs; --k)
579                 thisObj->deleteProperty(exec, k - 1);
580         } else {
581             for (unsigned k = length - deleteCount; k > begin; --k) {
582                 if (JSValue obj = getProperty(exec, thisObj, k + deleteCount - 1))
583                     thisObj->put(exec, k + additionalArgs - 1, obj);
584                 else
585                     thisObj->deleteProperty(exec, k + additionalArgs - 1);
586             }
587         }
588     }
589     for (unsigned k = 0; k < additionalArgs; ++k)
590         thisObj->put(exec, k + begin, args.at(k + 2));
591
592     putProperty(exec, thisObj, exec->propertyNames().length, jsNumber(exec, length - deleteCount + additionalArgs));
593     return result;
594 }
595
596 JSValue JSC_HOST_CALL arrayProtoFuncUnShift(ExecState* exec, JSObject*, JSValue thisValue, const ArgList& args)
597 {
598     JSObject* thisObj = thisValue.toThisObject(exec);
599
600     // 15.4.4.13
601     unsigned length = thisObj->get(exec, exec->propertyNames().length).toUInt32(exec);
602     unsigned nrArgs = args.size();
603     if (nrArgs) {
604         for (unsigned k = length; k > 0; --k) {
605             if (JSValue v = getProperty(exec, thisObj, k - 1))
606                 thisObj->put(exec, k + nrArgs - 1, v);
607             else
608                 thisObj->deleteProperty(exec, k + nrArgs - 1);
609         }
610     }
611     for (unsigned k = 0; k < nrArgs; ++k)
612         thisObj->put(exec, k, args.at(k));
613     JSValue result = jsNumber(exec, length + nrArgs);
614     putProperty(exec, thisObj, exec->propertyNames().length, result);
615     return result;
616 }
617
618 JSValue JSC_HOST_CALL arrayProtoFuncFilter(ExecState* exec, JSObject*, JSValue thisValue, const ArgList& args)
619 {
620     JSObject* thisObj = thisValue.toThisObject(exec);
621
622     JSValue function = args.at(0);
623     CallData callData;
624     CallType callType = function.getCallData(callData);
625     if (callType == CallTypeNone)
626         return throwError(exec, TypeError);
627
628     JSObject* applyThis = args.at(1).isUndefinedOrNull() ? exec->globalThisValue() : args.at(1).toObject(exec);
629     JSArray* resultArray = constructEmptyArray(exec);
630
631     unsigned filterIndex = 0;
632     unsigned length = thisObj->get(exec, exec->propertyNames().length).toUInt32(exec);
633     unsigned k = 0;
634     if (callType == CallTypeJS && isJSArray(&exec->globalData(), thisObj)) {
635         JSFunction* f = asFunction(function);
636         JSArray* array = asArray(thisObj);
637         CachedCall cachedCall(exec, f, 3, exec->exceptionSlot());
638         for (; k < length && !exec->hadException(); ++k) {
639             if (!array->canGetIndex(k))
640                 break;
641             JSValue v = array->getIndex(k);
642             cachedCall.setThis(applyThis);
643             cachedCall.setArgument(0, v);
644             cachedCall.setArgument(1, jsNumber(exec, k));
645             cachedCall.setArgument(2, thisObj);
646             
647             JSValue result = cachedCall.call();
648             if (result.toBoolean(exec))
649                 resultArray->put(exec, filterIndex++, v);
650         }
651         if (k == length)
652             return resultArray;
653     }
654     for (; k < length && !exec->hadException(); ++k) {
655         PropertySlot slot(thisObj);
656
657         if (!thisObj->getPropertySlot(exec, k, slot))
658             continue;
659
660         JSValue v = slot.getValue(exec, k);
661
662         MarkedArgumentBuffer eachArguments;
663
664         eachArguments.append(v);
665         eachArguments.append(jsNumber(exec, k));
666         eachArguments.append(thisObj);
667
668         JSValue result = call(exec, function, callType, callData, applyThis, eachArguments);
669
670         if (result.toBoolean(exec))
671             resultArray->put(exec, filterIndex++, v);
672     }
673     return resultArray;
674 }
675
676 JSValue JSC_HOST_CALL arrayProtoFuncMap(ExecState* exec, JSObject*, JSValue thisValue, const ArgList& args)
677 {
678     JSObject* thisObj = thisValue.toThisObject(exec);
679
680     JSValue function = args.at(0);
681     CallData callData;
682     CallType callType = function.getCallData(callData);
683     if (callType == CallTypeNone)
684         return throwError(exec, TypeError);
685
686     JSObject* applyThis = args.at(1).isUndefinedOrNull() ? exec->globalThisValue() : args.at(1).toObject(exec);
687
688     unsigned length = thisObj->get(exec, exec->propertyNames().length).toUInt32(exec);
689
690     JSArray* resultArray = constructEmptyArray(exec, length);
691     unsigned k = 0;
692     if (callType == CallTypeJS && isJSArray(&exec->globalData(), thisObj)) {
693         JSFunction* f = asFunction(function);
694         JSArray* array = asArray(thisObj);
695         CachedCall cachedCall(exec, f, 3, exec->exceptionSlot());
696         for (; k < length && !exec->hadException(); ++k) {
697             if (UNLIKELY(!array->canGetIndex(k)))
698                 break;
699
700             cachedCall.setThis(applyThis);
701             cachedCall.setArgument(0, array->getIndex(k));
702             cachedCall.setArgument(1, jsNumber(exec, k));
703             cachedCall.setArgument(2, thisObj);
704
705             resultArray->JSArray::put(exec, k, cachedCall.call());
706         }
707     }
708     for (; k < length && !exec->hadException(); ++k) {
709         PropertySlot slot(thisObj);
710         if (!thisObj->getPropertySlot(exec, k, slot))
711             continue;
712
713         JSValue v = slot.getValue(exec, k);
714
715         MarkedArgumentBuffer eachArguments;
716
717         eachArguments.append(v);
718         eachArguments.append(jsNumber(exec, k));
719         eachArguments.append(thisObj);
720
721         JSValue result = call(exec, function, callType, callData, applyThis, eachArguments);
722         resultArray->put(exec, k, result);
723     }
724
725     return resultArray;
726 }
727
728 // Documentation for these three is available at:
729 // http://developer-test.mozilla.org/en/docs/Core_JavaScript_1.5_Reference:Objects:Array:every
730 // http://developer-test.mozilla.org/en/docs/Core_JavaScript_1.5_Reference:Objects:Array:forEach
731 // http://developer-test.mozilla.org/en/docs/Core_JavaScript_1.5_Reference:Objects:Array:some
732
733 JSValue JSC_HOST_CALL arrayProtoFuncEvery(ExecState* exec, JSObject*, JSValue thisValue, const ArgList& args)
734 {
735     JSObject* thisObj = thisValue.toThisObject(exec);
736
737     JSValue function = args.at(0);
738     CallData callData;
739     CallType callType = function.getCallData(callData);
740     if (callType == CallTypeNone)
741         return throwError(exec, TypeError);
742
743     JSObject* applyThis = args.at(1).isUndefinedOrNull() ? exec->globalThisValue() : args.at(1).toObject(exec);
744
745     JSValue result = jsBoolean(true);
746
747     unsigned length = thisObj->get(exec, exec->propertyNames().length).toUInt32(exec);
748     unsigned k = 0;
749     if (callType == CallTypeJS && isJSArray(&exec->globalData(), thisObj)) {
750         JSFunction* f = asFunction(function);
751         JSArray* array = asArray(thisObj);
752         CachedCall cachedCall(exec, f, 3, exec->exceptionSlot());
753         for (; k < length && !exec->hadException(); ++k) {
754             if (UNLIKELY(!array->canGetIndex(k)))
755                 break;
756             
757             cachedCall.setThis(applyThis);
758             cachedCall.setArgument(0, array->getIndex(k));
759             cachedCall.setArgument(1, jsNumber(exec, k));
760             cachedCall.setArgument(2, thisObj);
761             JSValue result = cachedCall.call();
762             if (!result.toBoolean(cachedCall.newCallFrame(exec)))
763                 return jsBoolean(false);
764         }
765     }
766     for (; k < length && !exec->hadException(); ++k) {
767         PropertySlot slot(thisObj);
768
769         if (!thisObj->getPropertySlot(exec, k, slot))
770             continue;
771
772         MarkedArgumentBuffer eachArguments;
773
774         eachArguments.append(slot.getValue(exec, k));
775         eachArguments.append(jsNumber(exec, k));
776         eachArguments.append(thisObj);
777
778         bool predicateResult = call(exec, function, callType, callData, applyThis, eachArguments).toBoolean(exec);
779
780         if (!predicateResult) {
781             result = jsBoolean(false);
782             break;
783         }
784     }
785
786     return result;
787 }
788
789 JSValue JSC_HOST_CALL arrayProtoFuncForEach(ExecState* exec, JSObject*, JSValue thisValue, const ArgList& args)
790 {
791     JSObject* thisObj = thisValue.toThisObject(exec);
792
793     JSValue function = args.at(0);
794     CallData callData;
795     CallType callType = function.getCallData(callData);
796     if (callType == CallTypeNone)
797         return throwError(exec, TypeError);
798
799     JSObject* applyThis = args.at(1).isUndefinedOrNull() ? exec->globalThisValue() : args.at(1).toObject(exec);
800
801     unsigned length = thisObj->get(exec, exec->propertyNames().length).toUInt32(exec);
802     unsigned k = 0;
803     if (callType == CallTypeJS && isJSArray(&exec->globalData(), thisObj)) {
804         JSFunction* f = asFunction(function);
805         JSArray* array = asArray(thisObj);
806         CachedCall cachedCall(exec, f, 3, exec->exceptionSlot());
807         for (; k < length && !exec->hadException(); ++k) {
808             if (UNLIKELY(!array->canGetIndex(k)))
809                 break;
810
811             cachedCall.setThis(applyThis);
812             cachedCall.setArgument(0, array->getIndex(k));
813             cachedCall.setArgument(1, jsNumber(exec, k));
814             cachedCall.setArgument(2, thisObj);
815
816             cachedCall.call();
817         }
818     }
819     for (; k < length && !exec->hadException(); ++k) {
820         PropertySlot slot(thisObj);
821         if (!thisObj->getPropertySlot(exec, k, slot))
822             continue;
823
824         MarkedArgumentBuffer eachArguments;
825         eachArguments.append(slot.getValue(exec, k));
826         eachArguments.append(jsNumber(exec, k));
827         eachArguments.append(thisObj);
828
829         call(exec, function, callType, callData, applyThis, eachArguments);
830     }
831     return jsUndefined();
832 }
833
834 JSValue JSC_HOST_CALL arrayProtoFuncSome(ExecState* exec, JSObject*, JSValue thisValue, const ArgList& args)
835 {
836     JSObject* thisObj = thisValue.toThisObject(exec);
837
838     JSValue function = args.at(0);
839     CallData callData;
840     CallType callType = function.getCallData(callData);
841     if (callType == CallTypeNone)
842         return throwError(exec, TypeError);
843
844     JSObject* applyThis = args.at(1).isUndefinedOrNull() ? exec->globalThisValue() : args.at(1).toObject(exec);
845
846     JSValue result = jsBoolean(false);
847
848     unsigned length = thisObj->get(exec, exec->propertyNames().length).toUInt32(exec);
849     unsigned k = 0;
850     if (callType == CallTypeJS && isJSArray(&exec->globalData(), thisObj)) {
851         JSFunction* f = asFunction(function);
852         JSArray* array = asArray(thisObj);
853         CachedCall cachedCall(exec, f, 3, exec->exceptionSlot());
854         for (; k < length && !exec->hadException(); ++k) {
855             if (UNLIKELY(!array->canGetIndex(k)))
856                 break;
857             
858             cachedCall.setThis(applyThis);
859             cachedCall.setArgument(0, array->getIndex(k));
860             cachedCall.setArgument(1, jsNumber(exec, k));
861             cachedCall.setArgument(2, thisObj);
862             JSValue result = cachedCall.call();
863             if (result.toBoolean(cachedCall.newCallFrame(exec)))
864                 return jsBoolean(true);
865         }
866     }
867     for (; k < length && !exec->hadException(); ++k) {
868         PropertySlot slot(thisObj);
869         if (!thisObj->getPropertySlot(exec, k, slot))
870             continue;
871
872         MarkedArgumentBuffer eachArguments;
873         eachArguments.append(slot.getValue(exec, k));
874         eachArguments.append(jsNumber(exec, k));
875         eachArguments.append(thisObj);
876
877         bool predicateResult = call(exec, function, callType, callData, applyThis, eachArguments).toBoolean(exec);
878
879         if (predicateResult) {
880             result = jsBoolean(true);
881             break;
882         }
883     }
884     return result;
885 }
886
887 JSValue JSC_HOST_CALL arrayProtoFuncReduce(ExecState* exec, JSObject*, JSValue thisValue, const ArgList& args)
888 {
889     JSObject* thisObj = thisValue.toThisObject(exec);
890     
891     JSValue function = args.at(0);
892     CallData callData;
893     CallType callType = function.getCallData(callData);
894     if (callType == CallTypeNone)
895         return throwError(exec, TypeError);
896
897     unsigned i = 0;
898     JSValue rv;
899     unsigned length = thisObj->get(exec, exec->propertyNames().length).toUInt32(exec);
900     if (!length && args.size() == 1)
901         return throwError(exec, TypeError);
902     JSArray* array = 0;
903     if (isJSArray(&exec->globalData(), thisObj))
904         array = asArray(thisObj);
905
906     if (args.size() >= 2)
907         rv = args.at(1);
908     else if (array && array->canGetIndex(0)){
909         rv = array->getIndex(0);
910         i = 1;
911     } else {
912         for (i = 0; i < length; i++) {
913             rv = getProperty(exec, thisObj, i);
914             if (rv)
915                 break;
916         }
917         if (!rv)
918             return throwError(exec, TypeError);
919         i++;
920     }
921
922     if (callType == CallTypeJS && array) {
923         CachedCall cachedCall(exec, asFunction(function), 4, exec->exceptionSlot());
924         for (; i < length && !exec->hadException(); ++i) {
925             cachedCall.setThis(jsNull());
926             cachedCall.setArgument(0, rv);
927             JSValue v;
928             if (LIKELY(array->canGetIndex(i)))
929                 v = array->getIndex(i);
930             else
931                 break; // length has been made unsafe while we enumerate fallback to slow path
932             cachedCall.setArgument(1, v);
933             cachedCall.setArgument(2, jsNumber(exec, i));
934             cachedCall.setArgument(3, array);
935             rv = cachedCall.call();
936         }
937         if (i == length) // only return if we reached the end of the array
938             return rv;
939     }
940
941     for (; i < length && !exec->hadException(); ++i) {
942         JSValue prop = getProperty(exec, thisObj, i);
943         if (!prop)
944             continue;
945         
946         MarkedArgumentBuffer eachArguments;
947         eachArguments.append(rv);
948         eachArguments.append(prop);
949         eachArguments.append(jsNumber(exec, i));
950         eachArguments.append(thisObj);
951         
952         rv = call(exec, function, callType, callData, jsNull(), eachArguments);
953     }
954     return rv;
955 }
956
957 JSValue JSC_HOST_CALL arrayProtoFuncReduceRight(ExecState* exec, JSObject*, JSValue thisValue, const ArgList& args)
958 {
959     JSObject* thisObj = thisValue.toThisObject(exec);
960     
961     JSValue function = args.at(0);
962     CallData callData;
963     CallType callType = function.getCallData(callData);
964     if (callType == CallTypeNone)
965         return throwError(exec, TypeError);
966     
967     unsigned i = 0;
968     JSValue rv;
969     unsigned length = thisObj->get(exec, exec->propertyNames().length).toUInt32(exec);
970     if (!length && args.size() == 1)
971         return throwError(exec, TypeError);
972     JSArray* array = 0;
973     if (isJSArray(&exec->globalData(), thisObj))
974         array = asArray(thisObj);
975     
976     if (args.size() >= 2)
977         rv = args.at(1);
978     else if (array && array->canGetIndex(length - 1)){
979         rv = array->getIndex(length - 1);
980         i = 1;
981     } else {
982         for (i = 0; i < length; i++) {
983             rv = getProperty(exec, thisObj, length - i - 1);
984             if (rv)
985                 break;
986         }
987         if (!rv)
988             return throwError(exec, TypeError);
989         i++;
990     }
991     
992     if (callType == CallTypeJS && array) {
993         CachedCall cachedCall(exec, asFunction(function), 4, exec->exceptionSlot());
994         for (; i < length && !exec->hadException(); ++i) {
995             unsigned idx = length - i - 1;
996             cachedCall.setThis(jsNull());
997             cachedCall.setArgument(0, rv);
998             if (UNLIKELY(!array->canGetIndex(idx)))
999                 break; // length has been made unsafe while we enumerate fallback to slow path
1000             cachedCall.setArgument(1, array->getIndex(idx));
1001             cachedCall.setArgument(2, jsNumber(exec, idx));
1002             cachedCall.setArgument(3, array);
1003             rv = cachedCall.call();
1004         }
1005         if (i == length) // only return if we reached the end of the array
1006             return rv;
1007     }
1008     
1009     for (; i < length && !exec->hadException(); ++i) {
1010         unsigned idx = length - i - 1;
1011         JSValue prop = getProperty(exec, thisObj, idx);
1012         if (!prop)
1013             continue;
1014         
1015         MarkedArgumentBuffer eachArguments;
1016         eachArguments.append(rv);
1017         eachArguments.append(prop);
1018         eachArguments.append(jsNumber(exec, idx));
1019         eachArguments.append(thisObj);
1020         
1021         rv = call(exec, function, callType, callData, jsNull(), eachArguments);
1022     }
1023     return rv;        
1024 }
1025
1026 JSValue JSC_HOST_CALL arrayProtoFuncIndexOf(ExecState* exec, JSObject*, JSValue thisValue, const ArgList& args)
1027 {
1028     // JavaScript 1.5 Extension by Mozilla
1029     // Documentation: http://developer.mozilla.org/en/docs/Core_JavaScript_1.5_Reference:Global_Objects:Array:indexOf
1030
1031     JSObject* thisObj = thisValue.toThisObject(exec);
1032
1033     unsigned index = 0;
1034     double d = args.at(1).toInteger(exec);
1035     unsigned length = thisObj->get(exec, exec->propertyNames().length).toUInt32(exec);
1036     if (d < 0)
1037         d += length;
1038     if (d > 0) {
1039         if (d > length)
1040             index = length;
1041         else
1042             index = static_cast<unsigned>(d);
1043     }
1044
1045     JSValue searchElement = args.at(0);
1046     for (; index < length; ++index) {
1047         JSValue e = getProperty(exec, thisObj, index);
1048         if (!e)
1049             continue;
1050         if (JSValue::strictEqual(exec, searchElement, e))
1051             return jsNumber(exec, index);
1052     }
1053
1054     return jsNumber(exec, -1);
1055 }
1056
1057 JSValue JSC_HOST_CALL arrayProtoFuncLastIndexOf(ExecState* exec, JSObject*, JSValue thisValue, const ArgList& args)
1058 {
1059     // JavaScript 1.6 Extension by Mozilla
1060     // Documentation: http://developer.mozilla.org/en/docs/Core_JavaScript_1.5_Reference:Global_Objects:Array:lastIndexOf
1061
1062     JSObject* thisObj = thisValue.toThisObject(exec);
1063
1064     unsigned length = thisObj->get(exec, exec->propertyNames().length).toUInt32(exec);
1065     int index = length - 1;
1066     double d = args.at(1).toIntegerPreserveNaN(exec);
1067
1068     if (d < 0) {
1069         d += length;
1070         if (d < 0)
1071             return jsNumber(exec, -1);
1072     }
1073     if (d < length)
1074         index = static_cast<int>(d);
1075
1076     JSValue searchElement = args.at(0);
1077     for (; index >= 0; --index) {
1078         JSValue e = getProperty(exec, thisObj, index);
1079         if (!e)
1080             continue;
1081         if (JSValue::strictEqual(exec, searchElement, e))
1082             return jsNumber(exec, index);
1083     }
1084
1085     return jsNumber(exec, -1);
1086 }
1087
1088 } // namespace JSC