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