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