1/* 2 * Copyright (C) 1999-2000 Harri Porten (porten@kde.org) 3 * Copyright (C) 2003, 2007, 2008, 2009, 2011, 2013 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 "ButterflyInlines.h" 28#include "CachedCall.h" 29#include "CodeBlock.h" 30#include "CopiedSpaceInlines.h" 31#include "Error.h" 32#include "Interpreter.h" 33#include "JIT.h" 34#include "JSArrayIterator.h" 35#include "JSStringBuilder.h" 36#include "JSStringJoiner.h" 37#include "Lookup.h" 38#include "ObjectPrototype.h" 39#include "JSCInlines.h" 40#include "StringRecursionChecker.h" 41#include <algorithm> 42#include <wtf/Assertions.h> 43#include <wtf/HashSet.h> 44 45namespace JSC { 46 47static EncodedJSValue JSC_HOST_CALL arrayProtoFuncToString(ExecState*); 48static EncodedJSValue JSC_HOST_CALL arrayProtoFuncToLocaleString(ExecState*); 49static EncodedJSValue JSC_HOST_CALL arrayProtoFuncConcat(ExecState*); 50static EncodedJSValue JSC_HOST_CALL arrayProtoFuncJoin(ExecState*); 51static EncodedJSValue JSC_HOST_CALL arrayProtoFuncPop(ExecState*); 52static EncodedJSValue JSC_HOST_CALL arrayProtoFuncPush(ExecState*); 53static EncodedJSValue JSC_HOST_CALL arrayProtoFuncReverse(ExecState*); 54static EncodedJSValue JSC_HOST_CALL arrayProtoFuncShift(ExecState*); 55static EncodedJSValue JSC_HOST_CALL arrayProtoFuncSlice(ExecState*); 56static EncodedJSValue JSC_HOST_CALL arrayProtoFuncSort(ExecState*); 57static EncodedJSValue JSC_HOST_CALL arrayProtoFuncSplice(ExecState*); 58static EncodedJSValue JSC_HOST_CALL arrayProtoFuncUnShift(ExecState*); 59static EncodedJSValue JSC_HOST_CALL arrayProtoFuncIndexOf(ExecState*); 60static EncodedJSValue JSC_HOST_CALL arrayProtoFuncReduce(ExecState*); 61static EncodedJSValue JSC_HOST_CALL arrayProtoFuncReduceRight(ExecState*); 62static EncodedJSValue JSC_HOST_CALL arrayProtoFuncLastIndexOf(ExecState*); 63static EncodedJSValue JSC_HOST_CALL arrayProtoFuncValues(ExecState*); 64static EncodedJSValue JSC_HOST_CALL arrayProtoFuncKeys(ExecState*); 65static EncodedJSValue JSC_HOST_CALL arrayProtoFuncEntries(ExecState*); 66 67} 68 69#include "ArrayPrototype.lut.h" 70 71namespace JSC { 72 73static inline bool isNumericCompareFunction(ExecState* exec, JSValue function, CallType callType, const CallData& callData) 74{ 75 if (callType != CallTypeJS) 76 return false; 77 78 FunctionExecutable* executable = callData.js.functionExecutable; 79 JSScope* scope = callData.js.scope; 80 81 JSObject* error = executable->prepareForExecution(exec, jsCast<JSFunction*>(function), &scope, CodeForCall); 82 if (error) 83 return false; 84 85 return executable->codeBlockForCall()->isNumericCompareFunction(); 86} 87 88// ------------------------------ ArrayPrototype ---------------------------- 89 90const ClassInfo ArrayPrototype::s_info = {"Array", &JSArray::s_info, 0, ExecState::arrayPrototypeTable, CREATE_METHOD_TABLE(ArrayPrototype)}; 91 92/* Source for ArrayPrototype.lut.h 93@begin arrayPrototypeTable 16 94 toString arrayProtoFuncToString DontEnum|Function 0 95 toLocaleString arrayProtoFuncToLocaleString DontEnum|Function 0 96 concat arrayProtoFuncConcat DontEnum|Function 1 97 fill arrayProtoFuncFill DontEnum|Function 1 98 join arrayProtoFuncJoin DontEnum|Function 1 99 pop arrayProtoFuncPop DontEnum|Function 0 100 push arrayProtoFuncPush DontEnum|Function 1 101 reverse arrayProtoFuncReverse DontEnum|Function 0 102 shift arrayProtoFuncShift DontEnum|Function 0 103 slice arrayProtoFuncSlice DontEnum|Function 2 104 sort arrayProtoFuncSort DontEnum|Function 1 105 splice arrayProtoFuncSplice DontEnum|Function 2 106 unshift arrayProtoFuncUnShift DontEnum|Function 1 107 every arrayProtoFuncEvery DontEnum|Function 1 108 forEach arrayProtoFuncForEach DontEnum|Function 1 109 some arrayProtoFuncSome DontEnum|Function 1 110 indexOf arrayProtoFuncIndexOf DontEnum|Function 1 111 lastIndexOf arrayProtoFuncLastIndexOf DontEnum|Function 1 112 filter arrayProtoFuncFilter DontEnum|Function 1 113 reduce arrayProtoFuncReduce DontEnum|Function 1 114 reduceRight arrayProtoFuncReduceRight DontEnum|Function 1 115 map arrayProtoFuncMap DontEnum|Function 1 116 entries arrayProtoFuncEntries DontEnum|Function 0 117 keys arrayProtoFuncKeys DontEnum|Function 0 118 find arrayProtoFuncFind DontEnum|Function 1 119 findIndex arrayProtoFuncFindIndex DontEnum|Function 1 120@end 121*/ 122 123ArrayPrototype* ArrayPrototype::create(VM& vm, JSGlobalObject* globalObject, Structure* structure) 124{ 125 ArrayPrototype* prototype = new (NotNull, allocateCell<ArrayPrototype>(vm.heap)) ArrayPrototype(vm, structure); 126 prototype->finishCreation(vm, globalObject); 127 return prototype; 128} 129 130// ECMA 15.4.4 131ArrayPrototype::ArrayPrototype(VM& vm, Structure* structure) 132 : JSArray(vm, structure, 0) 133{ 134} 135 136void ArrayPrototype::finishCreation(VM& vm, JSGlobalObject* globalObject) 137{ 138 Base::finishCreation(vm); 139 ASSERT(inherits(info())); 140 vm.prototypeMap.addPrototype(this); 141 JSC_NATIVE_FUNCTION(vm.propertyNames->iteratorPrivateName, arrayProtoFuncValues, DontEnum, 0); 142} 143 144bool ArrayPrototype::getOwnPropertySlot(JSObject* object, ExecState* exec, PropertyName propertyName, PropertySlot& slot) 145{ 146 return getStaticFunctionSlot<JSArray>(exec, ExecState::arrayPrototypeTable(exec->vm()), jsCast<ArrayPrototype*>(object), propertyName, slot); 147} 148 149// ------------------------------ Array Functions ---------------------------- 150 151// Helper function 152static ALWAYS_INLINE JSValue getProperty(ExecState* exec, JSObject* obj, unsigned index) 153{ 154 PropertySlot slot(obj); 155 if (!obj->getPropertySlot(exec, index, slot)) 156 return JSValue(); 157 return slot.getValue(exec, index); 158} 159 160static ALWAYS_INLINE unsigned getLength(ExecState* exec, JSObject* obj) 161{ 162 if (isJSArray(obj)) 163 return jsCast<JSArray*>(obj)->length(); 164 return obj->get(exec, exec->propertyNames().length).toUInt32(exec); 165} 166 167static void putLength(ExecState* exec, JSObject* obj, JSValue value) 168{ 169 PutPropertySlot slot(obj); 170 obj->methodTable()->put(obj, exec, exec->propertyNames().length, value, slot); 171} 172 173static unsigned argumentClampedIndexFromStartOrEnd(ExecState* exec, int argument, unsigned length, unsigned undefinedValue = 0) 174{ 175 JSValue value = exec->argument(argument); 176 if (value.isUndefined()) 177 return undefinedValue; 178 179 double indexDouble = value.toInteger(exec); 180 if (indexDouble < 0) { 181 indexDouble += length; 182 return indexDouble < 0 ? 0 : static_cast<unsigned>(indexDouble); 183 } 184 return indexDouble > length ? length : static_cast<unsigned>(indexDouble); 185} 186 187 188// The shift/unshift function implement the shift/unshift behaviour required 189// by the corresponding array prototype methods, and by splice. In both cases, 190// the methods are operating an an array or array like object. 191// 192// header currentCount (remainder) 193// [------][------------][-----------] 194// header resultCount (remainder) 195// [------][-----------][-----------] 196// 197// The set of properties in the range 'header' must be unchanged. The set of 198// properties in the range 'remainder' (where remainder = length - header - 199// currentCount) will be shifted to the left or right as appropriate; in the 200// case of shift this must be removing values, in the case of unshift this 201// must be introducing new values. 202template<JSArray::ShiftCountMode shiftCountMode> 203void shift(ExecState* exec, JSObject* thisObj, unsigned header, unsigned currentCount, unsigned resultCount, unsigned length) 204{ 205 RELEASE_ASSERT(currentCount > resultCount); 206 unsigned count = currentCount - resultCount; 207 208 RELEASE_ASSERT(header <= length); 209 RELEASE_ASSERT(currentCount <= (length - header)); 210 211 if (isJSArray(thisObj)) { 212 JSArray* array = asArray(thisObj); 213 if (array->length() == length && asArray(thisObj)->shiftCount<shiftCountMode>(exec, header, count)) 214 return; 215 } 216 217 for (unsigned k = header; k < length - currentCount; ++k) { 218 unsigned from = k + currentCount; 219 unsigned to = k + resultCount; 220 PropertySlot slot(thisObj); 221 if (thisObj->getPropertySlot(exec, from, slot)) { 222 JSValue value = slot.getValue(exec, from); 223 if (exec->hadException()) 224 return; 225 thisObj->methodTable(exec->vm())->putByIndex(thisObj, exec, to, value, true); 226 if (exec->hadException()) 227 return; 228 } else if (!thisObj->methodTable(exec->vm())->deletePropertyByIndex(thisObj, exec, to)) { 229 throwTypeError(exec, ASCIILiteral("Unable to delete property.")); 230 return; 231 } 232 } 233 for (unsigned k = length; k > length - count; --k) { 234 if (!thisObj->methodTable(exec->vm())->deletePropertyByIndex(thisObj, exec, k - 1)) { 235 throwTypeError(exec, ASCIILiteral("Unable to delete property.")); 236 return; 237 } 238 } 239} 240template<JSArray::ShiftCountMode shiftCountMode> 241void unshift(ExecState* exec, JSObject* thisObj, unsigned header, unsigned currentCount, unsigned resultCount, unsigned length) 242{ 243 RELEASE_ASSERT(resultCount > currentCount); 244 unsigned count = resultCount - currentCount; 245 246 RELEASE_ASSERT(header <= length); 247 RELEASE_ASSERT(currentCount <= (length - header)); 248 249 // Guard against overflow. 250 if (count > (UINT_MAX - length)) { 251 throwOutOfMemoryError(exec); 252 return; 253 } 254 255 if (isJSArray(thisObj)) { 256 JSArray* array = asArray(thisObj); 257 if (array->length() == length && array->unshiftCount<shiftCountMode>(exec, header, count)) 258 return; 259 } 260 261 for (unsigned k = length - currentCount; k > header; --k) { 262 unsigned from = k + currentCount - 1; 263 unsigned to = k + resultCount - 1; 264 PropertySlot slot(thisObj); 265 if (thisObj->getPropertySlot(exec, from, slot)) { 266 JSValue value = slot.getValue(exec, from); 267 if (exec->hadException()) 268 return; 269 thisObj->methodTable(exec->vm())->putByIndex(thisObj, exec, to, value, true); 270 } else if (!thisObj->methodTable(exec->vm())->deletePropertyByIndex(thisObj, exec, to)) { 271 throwTypeError(exec, ASCIILiteral("Unable to delete property.")); 272 return; 273 } 274 if (exec->hadException()) 275 return; 276 } 277} 278 279EncodedJSValue JSC_HOST_CALL arrayProtoFuncToString(ExecState* exec) 280{ 281 JSValue thisValue = exec->thisValue().toThis(exec, StrictMode); 282 283 // 1. Let array be the result of calling ToObject on the this value. 284 JSObject* thisObject = thisValue.toObject(exec); 285 if (exec->hadException()) 286 return JSValue::encode(jsUndefined()); 287 288 // 2. Let func be the result of calling the [[Get]] internal method of array with argument "join". 289 JSValue function = JSValue(thisObject).get(exec, exec->propertyNames().join); 290 291 // 3. If IsCallable(func) is false, then let func be the standard built-in method Object.prototype.toString (15.2.4.2). 292 if (!function.isCell()) 293 return JSValue::encode(jsMakeNontrivialString(exec, "[object ", thisObject->methodTable(exec->vm())->className(thisObject), "]")); 294 CallData callData; 295 CallType callType = getCallData(function, callData); 296 if (callType == CallTypeNone) 297 return JSValue::encode(jsMakeNontrivialString(exec, "[object ", thisObject->methodTable(exec->vm())->className(thisObject), "]")); 298 299 // 4. Return the result of calling the [[Call]] internal method of func providing array as the this value and an empty arguments list. 300 if (!isJSArray(thisObject) || callType != CallTypeHost || callData.native.function != arrayProtoFuncJoin) 301 return JSValue::encode(call(exec, function, callType, callData, thisObject, exec->emptyList())); 302 303 ASSERT(isJSArray(thisValue)); 304 JSArray* thisObj = asArray(thisValue); 305 306 unsigned length = getLength(exec, thisObj); 307 if (exec->hadException()) 308 return JSValue::encode(jsUndefined()); 309 310 StringRecursionChecker checker(exec, thisObj); 311 if (JSValue earlyReturnValue = checker.earlyReturnValue()) 312 return JSValue::encode(earlyReturnValue); 313 314 String separator(",", String::ConstructFromLiteral); 315 JSStringJoiner stringJoiner(separator, length); 316 for (unsigned k = 0; k < length; k++) { 317 JSValue element; 318 if (thisObj->canGetIndexQuickly(k)) 319 element = thisObj->getIndexQuickly(k); 320 else { 321 element = thisObj->get(exec, k); 322 if (exec->hadException()) 323 return JSValue::encode(jsUndefined()); 324 } 325 326 if (element.isUndefinedOrNull()) 327 stringJoiner.append(String()); 328 else 329 stringJoiner.append(element.toWTFString(exec)); 330 331 if (exec->hadException()) 332 return JSValue::encode(jsUndefined()); 333 } 334 return JSValue::encode(stringJoiner.join(exec)); 335} 336 337EncodedJSValue JSC_HOST_CALL arrayProtoFuncToLocaleString(ExecState* exec) 338{ 339 JSValue thisValue = exec->thisValue().toThis(exec, StrictMode); 340 341 JSObject* thisObj = thisValue.toObject(exec); 342 if (exec->hadException()) 343 return JSValue::encode(jsUndefined()); 344 345 unsigned length = getLength(exec, thisObj); 346 if (exec->hadException()) 347 return JSValue::encode(jsUndefined()); 348 349 StringRecursionChecker checker(exec, thisObj); 350 if (JSValue earlyReturnValue = checker.earlyReturnValue()) 351 return JSValue::encode(earlyReturnValue); 352 353 String separator(",", String::ConstructFromLiteral); 354 JSStringJoiner stringJoiner(separator, length); 355 for (unsigned k = 0; k < length; k++) { 356 JSValue element = thisObj->get(exec, k); 357 if (exec->hadException()) 358 return JSValue::encode(jsUndefined()); 359 if (!element.isUndefinedOrNull()) { 360 JSObject* o = element.toObject(exec); 361 JSValue conversionFunction = o->get(exec, exec->propertyNames().toLocaleString); 362 if (exec->hadException()) 363 return JSValue::encode(jsUndefined()); 364 String str; 365 CallData callData; 366 CallType callType = getCallData(conversionFunction, callData); 367 if (callType != CallTypeNone) 368 str = call(exec, conversionFunction, callType, callData, element, exec->emptyList()).toWTFString(exec); 369 else 370 str = element.toWTFString(exec); 371 if (exec->hadException()) 372 return JSValue::encode(jsUndefined()); 373 stringJoiner.append(str); 374 } 375 } 376 377 return JSValue::encode(stringJoiner.join(exec)); 378} 379 380EncodedJSValue JSC_HOST_CALL arrayProtoFuncJoin(ExecState* exec) 381{ 382 JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec); 383 unsigned length = getLength(exec, thisObj); 384 if (exec->hadException()) 385 return JSValue::encode(jsUndefined()); 386 387 StringRecursionChecker checker(exec, thisObj); 388 if (JSValue earlyReturnValue = checker.earlyReturnValue()) 389 return JSValue::encode(earlyReturnValue); 390 391 String separator; 392 if (!exec->argument(0).isUndefined()) 393 separator = exec->argument(0).toWTFString(exec); 394 if (separator.isNull()) 395 separator = String(",", String::ConstructFromLiteral); 396 397 JSStringJoiner stringJoiner(separator, length); 398 399 unsigned k = 0; 400 if (isJSArray(thisObj)) { 401 JSArray* array = asArray(thisObj); 402 403 for (; k < length; k++) { 404 if (!array->canGetIndexQuickly(k)) 405 break; 406 407 JSValue element = array->getIndexQuickly(k); 408 if (!element.isUndefinedOrNull()) 409 stringJoiner.append(element.toWTFStringInline(exec)); 410 else 411 stringJoiner.append(String()); 412 } 413 } 414 415 for (; k < length; k++) { 416 JSValue element = thisObj->get(exec, k); 417 if (exec->hadException()) 418 return JSValue::encode(jsUndefined()); 419 if (!element.isUndefinedOrNull()) 420 stringJoiner.append(element.toWTFStringInline(exec)); 421 else 422 stringJoiner.append(String()); 423 } 424 425 return JSValue::encode(stringJoiner.join(exec)); 426} 427 428EncodedJSValue JSC_HOST_CALL arrayProtoFuncConcat(ExecState* exec) 429{ 430 JSValue thisValue = exec->thisValue().toThis(exec, StrictMode); 431 size_t argCount = exec->argumentCount(); 432 JSValue curArg = thisValue.toObject(exec); 433 Checked<unsigned, RecordOverflow> finalArraySize = 0; 434 435 for (size_t i = 0;;) { 436 if (JSArray* currentArray = jsDynamicCast<JSArray*>(curArg)) { 437 finalArraySize += getLength(exec, currentArray); 438 if (exec->hadException()) 439 return JSValue::encode(jsUndefined()); 440 } else 441 finalArraySize++; 442 if (i == argCount) 443 break; 444 curArg = exec->uncheckedArgument(i); 445 ++i; 446 } 447 448 if (finalArraySize.hasOverflowed()) 449 return JSValue::encode(throwOutOfMemoryError(exec)); 450 451 JSArray* arr = constructEmptyArray(exec, nullptr, finalArraySize.unsafeGet()); 452 if (exec->hadException()) 453 return JSValue::encode(jsUndefined()); 454 455 curArg = thisValue.toObject(exec); 456 unsigned n = 0; 457 for (size_t i = 0;;) { 458 if (JSArray* currentArray = jsDynamicCast<JSArray*>(curArg)) { 459 unsigned length = getLength(exec, currentArray); 460 if (exec->hadException()) 461 return JSValue::encode(jsUndefined()); 462 for (unsigned k = 0; k < length; ++k) { 463 JSValue v = getProperty(exec, currentArray, k); 464 if (exec->hadException()) 465 return JSValue::encode(jsUndefined()); 466 if (v) 467 arr->putDirectIndex(exec, n, v); 468 n++; 469 } 470 } else { 471 arr->putDirectIndex(exec, n, curArg); 472 n++; 473 } 474 if (i == argCount) 475 break; 476 curArg = exec->uncheckedArgument(i); 477 ++i; 478 } 479 arr->setLength(exec, n); 480 return JSValue::encode(arr); 481} 482 483EncodedJSValue JSC_HOST_CALL arrayProtoFuncPop(ExecState* exec) 484{ 485 JSValue thisValue = exec->thisValue().toThis(exec, StrictMode); 486 487 if (isJSArray(thisValue)) 488 return JSValue::encode(asArray(thisValue)->pop(exec)); 489 490 JSObject* thisObj = thisValue.toObject(exec); 491 unsigned length = getLength(exec, thisObj); 492 if (exec->hadException()) 493 return JSValue::encode(jsUndefined()); 494 495 JSValue result; 496 if (length == 0) { 497 putLength(exec, thisObj, jsNumber(length)); 498 result = jsUndefined(); 499 } else { 500 result = thisObj->get(exec, length - 1); 501 if (exec->hadException()) 502 return JSValue::encode(jsUndefined()); 503 if (!thisObj->methodTable(exec->vm())->deletePropertyByIndex(thisObj, exec, length - 1)) { 504 throwTypeError(exec, ASCIILiteral("Unable to delete property.")); 505 return JSValue::encode(jsUndefined()); 506 } 507 putLength(exec, thisObj, jsNumber(length - 1)); 508 } 509 return JSValue::encode(result); 510} 511 512EncodedJSValue JSC_HOST_CALL arrayProtoFuncPush(ExecState* exec) 513{ 514 JSValue thisValue = exec->thisValue().toThis(exec, StrictMode); 515 516 if (isJSArray(thisValue) && exec->argumentCount() == 1) { 517 JSArray* array = asArray(thisValue); 518 array->push(exec, exec->uncheckedArgument(0)); 519 return JSValue::encode(jsNumber(array->length())); 520 } 521 522 JSObject* thisObj = thisValue.toObject(exec); 523 unsigned length = getLength(exec, thisObj); 524 if (exec->hadException()) 525 return JSValue::encode(jsUndefined()); 526 527 for (unsigned n = 0; n < exec->argumentCount(); n++) { 528 // Check for integer overflow; where safe we can do a fast put by index. 529 if (length + n >= length) 530 thisObj->methodTable()->putByIndex(thisObj, exec, length + n, exec->uncheckedArgument(n), true); 531 else { 532 PutPropertySlot slot(thisObj); 533 Identifier propertyName(exec, JSValue(static_cast<int64_t>(length) + static_cast<int64_t>(n)).toWTFString(exec)); 534 thisObj->methodTable()->put(thisObj, exec, propertyName, exec->uncheckedArgument(n), slot); 535 } 536 if (exec->hadException()) 537 return JSValue::encode(jsUndefined()); 538 } 539 540 JSValue newLength(static_cast<int64_t>(length) + static_cast<int64_t>(exec->argumentCount())); 541 putLength(exec, thisObj, newLength); 542 return JSValue::encode(newLength); 543} 544 545EncodedJSValue JSC_HOST_CALL arrayProtoFuncReverse(ExecState* exec) 546{ 547 JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec); 548 unsigned length = getLength(exec, thisObj); 549 if (exec->hadException()) 550 return JSValue::encode(jsUndefined()); 551 552 unsigned middle = length / 2; 553 for (unsigned k = 0; k < middle; k++) { 554 unsigned lk1 = length - k - 1; 555 JSValue obj2 = getProperty(exec, thisObj, lk1); 556 if (exec->hadException()) 557 return JSValue::encode(jsUndefined()); 558 JSValue obj = getProperty(exec, thisObj, k); 559 if (exec->hadException()) 560 return JSValue::encode(jsUndefined()); 561 562 if (obj2) { 563 thisObj->methodTable(exec->vm())->putByIndex(thisObj, exec, k, obj2, true); 564 if (exec->hadException()) 565 return JSValue::encode(jsUndefined()); 566 } else if (!thisObj->methodTable(exec->vm())->deletePropertyByIndex(thisObj, exec, k)) { 567 throwTypeError(exec, ASCIILiteral("Unable to delete property.")); 568 return JSValue::encode(jsUndefined()); 569 } 570 571 if (obj) { 572 thisObj->methodTable(exec->vm())->putByIndex(thisObj, exec, lk1, obj, true); 573 if (exec->hadException()) 574 return JSValue::encode(jsUndefined()); 575 } else if (!thisObj->methodTable(exec->vm())->deletePropertyByIndex(thisObj, exec, lk1)) { 576 throwTypeError(exec, ASCIILiteral("Unable to delete property.")); 577 return JSValue::encode(jsUndefined()); 578 } 579 } 580 return JSValue::encode(thisObj); 581} 582 583EncodedJSValue JSC_HOST_CALL arrayProtoFuncShift(ExecState* exec) 584{ 585 JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec); 586 unsigned length = getLength(exec, thisObj); 587 if (exec->hadException()) 588 return JSValue::encode(jsUndefined()); 589 590 JSValue result; 591 if (length == 0) { 592 putLength(exec, thisObj, jsNumber(length)); 593 result = jsUndefined(); 594 } else { 595 result = thisObj->get(exec, 0); 596 shift<JSArray::ShiftCountForShift>(exec, thisObj, 0, 1, 0, length); 597 if (exec->hadException()) 598 return JSValue::encode(jsUndefined()); 599 putLength(exec, thisObj, jsNumber(length - 1)); 600 } 601 return JSValue::encode(result); 602} 603 604EncodedJSValue JSC_HOST_CALL arrayProtoFuncSlice(ExecState* exec) 605{ 606 // http://developer.netscape.com/docs/manuals/js/client/jsref/array.htm#1193713 or 15.4.4.10 607 JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec); 608 unsigned length = getLength(exec, thisObj); 609 if (exec->hadException()) 610 return JSValue::encode(jsUndefined()); 611 612 unsigned begin = argumentClampedIndexFromStartOrEnd(exec, 0, length); 613 unsigned end = argumentClampedIndexFromStartOrEnd(exec, 1, length, length); 614 615 JSArray* result = constructEmptyArray(exec, nullptr, end - begin); 616 617 unsigned n = 0; 618 for (unsigned k = begin; k < end; k++, n++) { 619 JSValue v = getProperty(exec, thisObj, k); 620 if (exec->hadException()) 621 return JSValue::encode(jsUndefined()); 622 if (v) 623 result->putDirectIndex(exec, n, v); 624 } 625 result->setLength(exec, n); 626 return JSValue::encode(result); 627} 628 629inline JSValue getOrHole(JSObject* obj, ExecState* exec, unsigned propertyName) 630{ 631 PropertySlot slot(obj); 632 if (obj->getPropertySlot(exec, propertyName, slot)) 633 return slot.getValue(exec, propertyName); 634 635 return JSValue(); 636} 637 638static bool attemptFastSort(ExecState* exec, JSObject* thisObj, JSValue function, CallData& callData, CallType& callType) 639{ 640 if (thisObj->classInfo() != JSArray::info() 641 || asArray(thisObj)->hasSparseMap() 642 || shouldUseSlowPut(thisObj->indexingType())) 643 return false; 644 645 if (isNumericCompareFunction(exec, function, callType, callData)) 646 asArray(thisObj)->sortNumeric(exec, function, callType, callData); 647 else if (callType != CallTypeNone) 648 asArray(thisObj)->sort(exec, function, callType, callData); 649 else 650 asArray(thisObj)->sort(exec); 651 return true; 652} 653 654static bool performSlowSort(ExecState* exec, JSObject* thisObj, unsigned length, JSValue function, CallData& callData, CallType& callType) 655{ 656 // "Min" sort. Not the fastest, but definitely less code than heapsort 657 // or quicksort, and much less swapping than bubblesort/insertionsort. 658 for (unsigned i = 0; i < length - 1; ++i) { 659 JSValue iObj = getOrHole(thisObj, exec, i); 660 if (exec->hadException()) 661 return false; 662 unsigned themin = i; 663 JSValue minObj = iObj; 664 for (unsigned j = i + 1; j < length; ++j) { 665 JSValue jObj = getOrHole(thisObj, exec, j); 666 if (exec->hadException()) 667 return false; 668 double compareResult; 669 if (!jObj) 670 compareResult = 1; 671 else if (!minObj) 672 compareResult = -1; 673 else if (jObj.isUndefined()) 674 compareResult = 1; // don't check minObj because there's no need to differentiate == (0) from > (1) 675 else if (minObj.isUndefined()) 676 compareResult = -1; 677 else if (callType != CallTypeNone) { 678 MarkedArgumentBuffer l; 679 l.append(jObj); 680 l.append(minObj); 681 compareResult = call(exec, function, callType, callData, jsUndefined(), l).toNumber(exec); 682 } else 683 compareResult = codePointCompareLessThan(jObj.toWTFStringInline(exec), minObj.toWTFStringInline(exec)) ? -1 : 1; 684 685 if (compareResult < 0) { 686 themin = j; 687 minObj = jObj; 688 } 689 } 690 // Swap themin and i 691 if (themin > i) { 692 if (minObj) { 693 thisObj->methodTable(exec->vm())->putByIndex(thisObj, exec, i, minObj, true); 694 if (exec->hadException()) 695 return false; 696 } else if (!thisObj->methodTable(exec->vm())->deletePropertyByIndex(thisObj, exec, i)) { 697 throwTypeError(exec, "Unable to delete property."); 698 return false; 699 } 700 if (iObj) { 701 thisObj->methodTable(exec->vm())->putByIndex(thisObj, exec, themin, iObj, true); 702 if (exec->hadException()) 703 return false; 704 } else if (!thisObj->methodTable(exec->vm())->deletePropertyByIndex(thisObj, exec, themin)) { 705 throwTypeError(exec, "Unable to delete property."); 706 return false; 707 } 708 } 709 } 710 return true; 711} 712 713EncodedJSValue JSC_HOST_CALL arrayProtoFuncSort(ExecState* exec) 714{ 715 JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec); 716 unsigned length = getLength(exec, thisObj); 717 if (!length || exec->hadException()) 718 return JSValue::encode(thisObj); 719 720 JSValue function = exec->argument(0); 721 CallData callData; 722 CallType callType = getCallData(function, callData); 723 724 if (attemptFastSort(exec, thisObj, function, callData, callType)) 725 return JSValue::encode(thisObj); 726 727 // Assume that for small-ish arrays, doing the slow sort directly is better. 728 if (length < 1000) 729 return performSlowSort(exec, thisObj, length, function, callData, callType) ? JSValue::encode(thisObj) : JSValue::encode(jsUndefined()); 730 731 JSGlobalObject* globalObject = JSGlobalObject::create( 732 exec->vm(), JSGlobalObject::createStructure(exec->vm(), jsNull())); 733 JSArray* flatArray = constructEmptyArray(globalObject->globalExec(), nullptr); 734 if (exec->hadException()) 735 return JSValue::encode(jsUndefined()); 736 737 PropertyNameArray nameArray(exec); 738 thisObj->methodTable(exec->vm())->getPropertyNames(thisObj, exec, nameArray, IncludeDontEnumProperties); 739 if (exec->hadException()) 740 return JSValue::encode(jsUndefined()); 741 742 Vector<uint32_t, 0, UnsafeVectorOverflow> keys; 743 for (size_t i = 0; i < nameArray.size(); ++i) { 744 PropertyName name = nameArray[i]; 745 uint32_t index = name.asIndex(); 746 if (index == PropertyName::NotAnIndex) 747 continue; 748 749 JSValue value = getOrHole(thisObj, exec, index); 750 if (exec->hadException()) 751 return JSValue::encode(jsUndefined()); 752 if (!value) 753 continue; 754 keys.append(index); 755 flatArray->push(exec, value); 756 if (exec->hadException()) 757 return JSValue::encode(jsUndefined()); 758 } 759 760 if (!attemptFastSort(exec, flatArray, function, callData, callType) 761 && !performSlowSort(exec, flatArray, flatArray->length(), function, callData, callType)) 762 return JSValue::encode(jsUndefined()); 763 764 for (size_t i = 0; i < keys.size(); ++i) { 765 size_t index = keys[i]; 766 if (index < flatArray->length()) 767 continue; 768 769 if (!thisObj->methodTable(exec->vm())->deletePropertyByIndex(thisObj, exec, index)) { 770 throwTypeError(exec, "Unable to delete property."); 771 return JSValue::encode(jsUndefined()); 772 } 773 } 774 775 for (size_t i = flatArray->length(); i--;) { 776 JSValue value = getOrHole(flatArray, exec, i); 777 RELEASE_ASSERT(value); 778 thisObj->methodTable(exec->vm())->putByIndex(thisObj, exec, i, value, true); 779 if (exec->hadException()) 780 return JSValue::encode(jsUndefined()); 781 } 782 783 return JSValue::encode(thisObj); 784} 785 786EncodedJSValue JSC_HOST_CALL arrayProtoFuncSplice(ExecState* exec) 787{ 788 // 15.4.4.12 789 790 JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec); 791 unsigned length = getLength(exec, thisObj); 792 if (exec->hadException()) 793 return JSValue::encode(jsUndefined()); 794 795 if (!exec->argumentCount()) 796 return JSValue::encode(constructEmptyArray(exec, nullptr)); 797 798 unsigned begin = argumentClampedIndexFromStartOrEnd(exec, 0, length); 799 800 unsigned deleteCount = length - begin; 801 if (exec->argumentCount() > 1) { 802 double deleteDouble = exec->uncheckedArgument(1).toInteger(exec); 803 if (deleteDouble < 0) 804 deleteCount = 0; 805 else if (deleteDouble > length - begin) 806 deleteCount = length - begin; 807 else 808 deleteCount = static_cast<unsigned>(deleteDouble); 809 } 810 811 JSArray* resObj = JSArray::tryCreateUninitialized(exec->vm(), exec->lexicalGlobalObject()->arrayStructureForIndexingTypeDuringAllocation(ArrayWithUndecided), deleteCount); 812 if (!resObj) 813 return JSValue::encode(throwOutOfMemoryError(exec)); 814 815 JSValue result = resObj; 816 VM& vm = exec->vm(); 817 for (unsigned k = 0; k < deleteCount; k++) { 818 JSValue v = getProperty(exec, thisObj, k + begin); 819 if (exec->hadException()) 820 return JSValue::encode(jsUndefined()); 821 resObj->initializeIndex(vm, k, v); 822 } 823 824 unsigned additionalArgs = std::max<int>(exec->argumentCount() - 2, 0); 825 if (additionalArgs < deleteCount) { 826 shift<JSArray::ShiftCountForSplice>(exec, thisObj, begin, deleteCount, additionalArgs, length); 827 if (exec->hadException()) 828 return JSValue::encode(jsUndefined()); 829 } else if (additionalArgs > deleteCount) { 830 unshift<JSArray::ShiftCountForSplice>(exec, thisObj, begin, deleteCount, additionalArgs, length); 831 if (exec->hadException()) 832 return JSValue::encode(jsUndefined()); 833 } 834 for (unsigned k = 0; k < additionalArgs; ++k) { 835 thisObj->methodTable(exec->vm())->putByIndex(thisObj, exec, k + begin, exec->uncheckedArgument(k + 2), true); 836 if (exec->hadException()) 837 return JSValue::encode(jsUndefined()); 838 } 839 840 putLength(exec, thisObj, jsNumber(length - deleteCount + additionalArgs)); 841 return JSValue::encode(result); 842} 843 844EncodedJSValue JSC_HOST_CALL arrayProtoFuncUnShift(ExecState* exec) 845{ 846 // 15.4.4.13 847 848 JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec); 849 unsigned length = getLength(exec, thisObj); 850 if (exec->hadException()) 851 return JSValue::encode(jsUndefined()); 852 853 unsigned nrArgs = exec->argumentCount(); 854 if (nrArgs) { 855 unshift<JSArray::ShiftCountForShift>(exec, thisObj, 0, 0, nrArgs, length); 856 if (exec->hadException()) 857 return JSValue::encode(jsUndefined()); 858 } 859 for (unsigned k = 0; k < nrArgs; ++k) { 860 thisObj->methodTable(exec->vm())->putByIndex(thisObj, exec, k, exec->uncheckedArgument(k), true); 861 if (exec->hadException()) 862 return JSValue::encode(jsUndefined()); 863 } 864 JSValue result = jsNumber(length + nrArgs); 865 putLength(exec, thisObj, result); 866 return JSValue::encode(result); 867} 868 869EncodedJSValue JSC_HOST_CALL arrayProtoFuncReduce(ExecState* exec) 870{ 871 JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec); 872 unsigned length = getLength(exec, thisObj); 873 if (exec->hadException()) 874 return JSValue::encode(jsUndefined()); 875 876 JSValue function = exec->argument(0); 877 CallData callData; 878 CallType callType = getCallData(function, callData); 879 if (callType == CallTypeNone) 880 return throwVMTypeError(exec); 881 882 unsigned i = 0; 883 JSValue rv; 884 if (!length && exec->argumentCount() == 1) 885 return throwVMTypeError(exec); 886 887 JSArray* array = 0; 888 if (isJSArray(thisObj)) 889 array = asArray(thisObj); 890 891 if (exec->argumentCount() >= 2) 892 rv = exec->uncheckedArgument(1); 893 else if (array && array->canGetIndexQuickly(0)) { 894 rv = array->getIndexQuickly(0); 895 i = 1; 896 } else { 897 for (i = 0; i < length; i++) { 898 rv = getProperty(exec, thisObj, i); 899 if (exec->hadException()) 900 return JSValue::encode(jsUndefined()); 901 if (rv) 902 break; 903 } 904 if (!rv) 905 return throwVMTypeError(exec); 906 i++; 907 } 908 909 if (callType == CallTypeJS && array) { 910 CachedCall cachedCall(exec, jsCast<JSFunction*>(function), 4); 911 for (; i < length && !exec->hadException(); ++i) { 912 cachedCall.setThis(jsUndefined()); 913 cachedCall.setArgument(0, rv); 914 JSValue v; 915 if (LIKELY(array->canGetIndexQuickly(i))) 916 v = array->getIndexQuickly(i); 917 else 918 break; // length has been made unsafe while we enumerate fallback to slow path 919 cachedCall.setArgument(1, v); 920 cachedCall.setArgument(2, jsNumber(i)); 921 cachedCall.setArgument(3, array); 922 rv = cachedCall.call(); 923 } 924 if (i == length) // only return if we reached the end of the array 925 return JSValue::encode(rv); 926 } 927 928 for (; i < length && !exec->hadException(); ++i) { 929 JSValue prop = getProperty(exec, thisObj, i); 930 if (exec->hadException()) 931 return JSValue::encode(jsUndefined()); 932 if (!prop) 933 continue; 934 935 MarkedArgumentBuffer eachArguments; 936 eachArguments.append(rv); 937 eachArguments.append(prop); 938 eachArguments.append(jsNumber(i)); 939 eachArguments.append(thisObj); 940 941 rv = call(exec, function, callType, callData, jsUndefined(), eachArguments); 942 } 943 return JSValue::encode(rv); 944} 945 946EncodedJSValue JSC_HOST_CALL arrayProtoFuncReduceRight(ExecState* exec) 947{ 948 JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec); 949 unsigned length = getLength(exec, thisObj); 950 if (exec->hadException()) 951 return JSValue::encode(jsUndefined()); 952 953 JSValue function = exec->argument(0); 954 CallData callData; 955 CallType callType = getCallData(function, callData); 956 if (callType == CallTypeNone) 957 return throwVMTypeError(exec); 958 959 unsigned i = 0; 960 JSValue rv; 961 if (!length && exec->argumentCount() == 1) 962 return throwVMTypeError(exec); 963 964 JSArray* array = 0; 965 if (isJSArray(thisObj)) 966 array = asArray(thisObj); 967 968 if (exec->argumentCount() >= 2) 969 rv = exec->uncheckedArgument(1); 970 else if (array && array->canGetIndexQuickly(length - 1)) { 971 rv = array->getIndexQuickly(length - 1); 972 i = 1; 973 } else { 974 for (i = 0; i < length; i++) { 975 rv = getProperty(exec, thisObj, length - i - 1); 976 if (exec->hadException()) 977 return JSValue::encode(jsUndefined()); 978 if (rv) 979 break; 980 } 981 if (!rv) 982 return throwVMTypeError(exec); 983 i++; 984 } 985 986 if (callType == CallTypeJS && array) { 987 CachedCall cachedCall(exec, jsCast<JSFunction*>(function), 4); 988 for (; i < length && !exec->hadException(); ++i) { 989 unsigned idx = length - i - 1; 990 cachedCall.setThis(jsUndefined()); 991 cachedCall.setArgument(0, rv); 992 if (UNLIKELY(!array->canGetIndexQuickly(idx))) 993 break; // length has been made unsafe while we enumerate fallback to slow path 994 cachedCall.setArgument(1, array->getIndexQuickly(idx)); 995 cachedCall.setArgument(2, jsNumber(idx)); 996 cachedCall.setArgument(3, array); 997 rv = cachedCall.call(); 998 } 999 if (i == length) // only return if we reached the end of the array 1000 return JSValue::encode(rv); 1001 } 1002 1003 for (; i < length && !exec->hadException(); ++i) { 1004 unsigned idx = length - i - 1; 1005 JSValue prop = getProperty(exec, thisObj, idx); 1006 if (exec->hadException()) 1007 return JSValue::encode(jsUndefined()); 1008 if (!prop) 1009 continue; 1010 1011 MarkedArgumentBuffer eachArguments; 1012 eachArguments.append(rv); 1013 eachArguments.append(prop); 1014 eachArguments.append(jsNumber(idx)); 1015 eachArguments.append(thisObj); 1016 1017 rv = call(exec, function, callType, callData, jsUndefined(), eachArguments); 1018 } 1019 return JSValue::encode(rv); 1020} 1021 1022EncodedJSValue JSC_HOST_CALL arrayProtoFuncIndexOf(ExecState* exec) 1023{ 1024 // 15.4.4.14 1025 JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec); 1026 unsigned length = getLength(exec, thisObj); 1027 if (exec->hadException()) 1028 return JSValue::encode(jsUndefined()); 1029 1030 unsigned index = argumentClampedIndexFromStartOrEnd(exec, 1, length); 1031 JSValue searchElement = exec->argument(0); 1032 for (; index < length; ++index) { 1033 JSValue e = getProperty(exec, thisObj, index); 1034 if (exec->hadException()) 1035 return JSValue::encode(jsUndefined()); 1036 if (!e) 1037 continue; 1038 if (JSValue::strictEqual(exec, searchElement, e)) 1039 return JSValue::encode(jsNumber(index)); 1040 } 1041 1042 return JSValue::encode(jsNumber(-1)); 1043} 1044 1045EncodedJSValue JSC_HOST_CALL arrayProtoFuncLastIndexOf(ExecState* exec) 1046{ 1047 // 15.4.4.15 1048 JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec); 1049 unsigned length = getLength(exec, thisObj); 1050 if (!length) 1051 return JSValue::encode(jsNumber(-1)); 1052 1053 unsigned index = length - 1; 1054 if (exec->argumentCount() >= 2) { 1055 JSValue fromValue = exec->uncheckedArgument(1); 1056 double fromDouble = fromValue.toInteger(exec); 1057 if (fromDouble < 0) { 1058 fromDouble += length; 1059 if (fromDouble < 0) 1060 return JSValue::encode(jsNumber(-1)); 1061 } 1062 if (fromDouble < length) 1063 index = static_cast<unsigned>(fromDouble); 1064 } 1065 1066 JSValue searchElement = exec->argument(0); 1067 do { 1068 RELEASE_ASSERT(index < length); 1069 JSValue e = getProperty(exec, thisObj, index); 1070 if (exec->hadException()) 1071 return JSValue::encode(jsUndefined()); 1072 if (!e) 1073 continue; 1074 if (JSValue::strictEqual(exec, searchElement, e)) 1075 return JSValue::encode(jsNumber(index)); 1076 } while (index--); 1077 1078 return JSValue::encode(jsNumber(-1)); 1079} 1080 1081EncodedJSValue JSC_HOST_CALL arrayProtoFuncValues(ExecState* exec) 1082{ 1083 JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec); 1084 return JSValue::encode(JSArrayIterator::create(exec, exec->callee()->globalObject()->arrayIteratorStructure(), ArrayIterateValue, thisObj)); 1085} 1086 1087EncodedJSValue JSC_HOST_CALL arrayProtoFuncEntries(ExecState* exec) 1088{ 1089 JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec); 1090 return JSValue::encode(JSArrayIterator::create(exec, exec->callee()->globalObject()->arrayIteratorStructure(), ArrayIterateKeyValue, thisObj)); 1091} 1092 1093EncodedJSValue JSC_HOST_CALL arrayProtoFuncKeys(ExecState* exec) 1094{ 1095 JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec); 1096 return JSValue::encode(JSArrayIterator::create(exec, exec->callee()->globalObject()->arrayIteratorStructure(), ArrayIterateKey, thisObj)); 1097} 1098 1099} // namespace JSC 1100