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