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