Source/JavaScriptCore/runtime/ArrayPrototype.cpp

   1 /*
   2  *  Copyright (C) 1999-2000 Harri Porten (porten@kde.org)
   3  *  Copyright (C) 2003, 2007-2009, 2011, 2013, 2015-2016 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 "AdaptiveInferredPropertyValueWatchpointBase.h"
  28 #include "ArrayConstructor.h"
  29 #include "BuiltinNames.h"
  30 #include "ButterflyInlines.h"
  31 #include "CodeBlock.h"
  32 #include "Error.h"
  33 #include "GetterSetter.h"
  34 #include "Interpreter.h"
  35 #include "JIT.h"
  36 #include "JSArrayInlines.h"
  37 #include "JSCBuiltins.h"
  38 #include "JSCInlines.h"
  39 #include "JSStringBuilder.h"
  40 #include "JSStringJoiner.h"
  41 #include "Lookup.h"
  42 #include "ObjectConstructor.h"
  43 #include "ObjectPrototype.h"
  44 #include "Operations.h"
  45 #include "StringRecursionChecker.h"
  46 #include <algorithm>
  47 #include <wtf/Assertions.h>
  48
  49 namespace JSC {
  50
  51 EncodedJSValue JSC_HOST_CALL arrayProtoFuncToLocaleString(ExecState*);
  52 EncodedJSValue JSC_HOST_CALL arrayProtoFuncJoin(ExecState*);
  53 EncodedJSValue JSC_HOST_CALL arrayProtoFuncPop(ExecState*);
  54 EncodedJSValue JSC_HOST_CALL arrayProtoFuncPush(ExecState*);
  55 EncodedJSValue JSC_HOST_CALL arrayProtoFuncReverse(ExecState*);
  56 EncodedJSValue JSC_HOST_CALL arrayProtoFuncShift(ExecState*);
  57 EncodedJSValue JSC_HOST_CALL arrayProtoFuncSlice(ExecState*);
  58 EncodedJSValue JSC_HOST_CALL arrayProtoFuncSplice(ExecState*);
  59 EncodedJSValue JSC_HOST_CALL arrayProtoFuncUnShift(ExecState*);
  60 EncodedJSValue JSC_HOST_CALL arrayProtoFuncIndexOf(ExecState*);
  61 EncodedJSValue JSC_HOST_CALL arrayProtoFuncLastIndexOf(ExecState*);
  62
  63 // ------------------------------ ArrayPrototype ----------------------------
  64
  65 const ClassInfo ArrayPrototype::s_info = {"Array", &JSArray::s_info, nullptr, CREATE_METHOD_TABLE(ArrayPrototype)};
  66
  67 ArrayPrototype* ArrayPrototype::create(VM& vm, JSGlobalObject* globalObject, Structure* structure)
  68 {
  69     ArrayPrototype* prototype = new (NotNull, allocateCell<ArrayPrototype>(vm.heap)) ArrayPrototype(vm, structure);
  70     prototype->finishCreation(vm, globalObject);
  71     vm.heap.addFinalizer(prototype, destroy);
  72     return prototype;
  73 }
  74
  75 // ECMA 15.4.4
  76 ArrayPrototype::ArrayPrototype(VM& vm, Structure* structure)
  77     : JSArray(vm, structure, 0)
  78 {
  79 }
  80
  81 void ArrayPrototype::finishCreation(VM& vm, JSGlobalObject* globalObject)
  82 {
  83     Base::finishCreation(vm);
  84     ASSERT(inherits(info()));
  85     vm.prototypeMap.addPrototype(this);
  86
  87     putDirectWithoutTransition(vm, vm.propertyNames->toString, globalObject->arrayProtoToStringFunction(), DontEnum);
  88     putDirectWithoutTransition(vm, vm.propertyNames->builtinNames().valuesPublicName(), globalObject->arrayProtoValuesFunction(), DontEnum);
  89     putDirectWithoutTransition(vm, vm.propertyNames->iteratorSymbol, globalObject->arrayProtoValuesFunction(), DontEnum);
  90
  91     JSC_NATIVE_FUNCTION_WITHOUT_TRANSITION(vm.propertyNames->toLocaleString, arrayProtoFuncToLocaleString, DontEnum, 0);
  92     JSC_BUILTIN_FUNCTION_WITHOUT_TRANSITION("concat", arrayPrototypeConcatCodeGenerator, DontEnum);
  93     JSC_BUILTIN_FUNCTION_WITHOUT_TRANSITION("fill", arrayPrototypeFillCodeGenerator, DontEnum);
  94     JSC_NATIVE_FUNCTION_WITHOUT_TRANSITION(vm.propertyNames->join, arrayProtoFuncJoin, DontEnum, 1);
  95     JSC_NATIVE_INTRINSIC_FUNCTION_WITHOUT_TRANSITION("pop", arrayProtoFuncPop, DontEnum, 0, ArrayPopIntrinsic);
  96     JSC_NATIVE_INTRINSIC_FUNCTION_WITHOUT_TRANSITION(vm.propertyNames->builtinNames().pushPublicName(), arrayProtoFuncPush, DontEnum, 1, ArrayPushIntrinsic);
  97     JSC_NATIVE_INTRINSIC_FUNCTION_WITHOUT_TRANSITION(vm.propertyNames->builtinNames().pushPrivateName(), arrayProtoFuncPush, DontEnum | DontDelete | ReadOnly, 1, ArrayPushIntrinsic);
  98     JSC_NATIVE_FUNCTION_WITHOUT_TRANSITION("reverse", arrayProtoFuncReverse, DontEnum, 0);
  99     JSC_NATIVE_FUNCTION_WITHOUT_TRANSITION(vm.propertyNames->builtinNames().shiftPublicName(), arrayProtoFuncShift, DontEnum, 0);
 100     JSC_NATIVE_FUNCTION_WITHOUT_TRANSITION(vm.propertyNames->builtinNames().shiftPrivateName(), arrayProtoFuncShift, DontEnum | DontDelete | ReadOnly, 0);
 101     JSC_NATIVE_FUNCTION_WITHOUT_TRANSITION(vm.propertyNames->slice, arrayProtoFuncSlice, DontEnum, 2);
 102     JSC_BUILTIN_FUNCTION_WITHOUT_TRANSITION("sort", arrayPrototypeSortCodeGenerator, DontEnum);
 103     JSC_NATIVE_FUNCTION_WITHOUT_TRANSITION("splice", arrayProtoFuncSplice, DontEnum, 2);
 104     JSC_NATIVE_FUNCTION_WITHOUT_TRANSITION("unshift", arrayProtoFuncUnShift, DontEnum, 1);
 105     JSC_BUILTIN_FUNCTION_WITHOUT_TRANSITION("every", arrayPrototypeEveryCodeGenerator, DontEnum);
 106     JSC_BUILTIN_FUNCTION_WITHOUT_TRANSITION("forEach", arrayPrototypeForEachCodeGenerator, DontEnum);
 107     JSC_BUILTIN_FUNCTION_WITHOUT_TRANSITION("some", arrayPrototypeSomeCodeGenerator, DontEnum);
 108     JSC_NATIVE_FUNCTION_WITHOUT_TRANSITION("indexOf", arrayProtoFuncIndexOf, DontEnum, 1);
 109     JSC_NATIVE_FUNCTION_WITHOUT_TRANSITION("lastIndexOf", arrayProtoFuncLastIndexOf, DontEnum, 1);
 110     JSC_BUILTIN_FUNCTION_WITHOUT_TRANSITION("filter", arrayPrototypeFilterCodeGenerator, DontEnum);
 111     JSC_BUILTIN_FUNCTION_WITHOUT_TRANSITION("reduce", arrayPrototypeReduceCodeGenerator, DontEnum);
 112     JSC_BUILTIN_FUNCTION_WITHOUT_TRANSITION("reduceRight", arrayPrototypeReduceRightCodeGenerator, DontEnum);
 113     JSC_BUILTIN_FUNCTION_WITHOUT_TRANSITION("map", arrayPrototypeMapCodeGenerator, DontEnum);
 114     JSC_BUILTIN_FUNCTION_WITHOUT_TRANSITION(vm.propertyNames->builtinNames().entriesPublicName(), arrayPrototypeEntriesCodeGenerator, DontEnum);
 115     JSC_BUILTIN_FUNCTION_WITHOUT_TRANSITION(vm.propertyNames->builtinNames().keysPublicName(), arrayPrototypeKeysCodeGenerator, DontEnum);
 116     JSC_BUILTIN_FUNCTION_WITHOUT_TRANSITION("find", arrayPrototypeFindCodeGenerator, DontEnum);
 117     JSC_BUILTIN_FUNCTION_WITHOUT_TRANSITION("findIndex", arrayPrototypeFindIndexCodeGenerator, DontEnum);
 118     JSC_BUILTIN_FUNCTION_WITHOUT_TRANSITION("includes", arrayPrototypeIncludesCodeGenerator, DontEnum);
 119     JSC_BUILTIN_FUNCTION_WITHOUT_TRANSITION("copyWithin", arrayPrototypeCopyWithinCodeGenerator, DontEnum);
 120
 121     putDirectWithoutTransition(vm, vm.propertyNames->builtinNames().entriesPrivateName(), getDirect(vm, vm.propertyNames->builtinNames().entriesPublicName()), ReadOnly);
 122     putDirectWithoutTransition(vm, vm.propertyNames->builtinNames().forEachPrivateName(), getDirect(vm, vm.propertyNames->builtinNames().forEachPublicName()), ReadOnly);
 123     putDirectWithoutTransition(vm, vm.propertyNames->builtinNames().keysPrivateName(), getDirect(vm, vm.propertyNames->builtinNames().keysPublicName()), ReadOnly);
 124     putDirectWithoutTransition(vm, vm.propertyNames->builtinNames().valuesPrivateName(), globalObject->arrayProtoValuesFunction(), ReadOnly);
 125
 126     JSObject* unscopables = constructEmptyObject(globalObject->globalExec(), globalObject->nullPrototypeObjectStructure());
 127     const char* unscopableNames[] = {
 128         "copyWithin",
 129         "entries",
 130         "fill",
 131         "find",
 132         "findIndex",
 133         "includes",
 134         "keys",
 135         "values"
 136     };
 137     for (const char* unscopableName : unscopableNames)
 138         unscopables->putDirect(vm, Identifier::fromString(&vm, unscopableName), jsBoolean(true));
 139     putDirectWithoutTransition(vm, vm.propertyNames->unscopablesSymbol, unscopables, DontEnum | ReadOnly);
 140 }
 141
 142 void ArrayPrototype::destroy(JSC::JSCell* cell)
 143 {
 144     ArrayPrototype* thisObject = static_cast<ArrayPrototype*>(cell);
 145     thisObject->ArrayPrototype::~ArrayPrototype();
 146 }
 147
 148 // ------------------------------ Array Functions ----------------------------
 149
 150 static ALWAYS_INLINE JSValue getProperty(ExecState* exec, JSObject* object, unsigned index)
 151 {
 152     if (JSValue result = object->tryGetIndexQuickly(index))
 153         return result;
 154     // We want to perform get and has in the same operation.
 155     // We can only do so when this behavior is not observable. The
 156     // only time it is observable is when we encounter an opaque objects (ProxyObject and JSModuleNamespaceObject)
 157     // somewhere in the prototype chain.
 158     PropertySlot slot(object, PropertySlot::InternalMethodType::HasProperty);
 159     if (!object->getPropertySlot(exec, index, slot))
 160         return JSValue();
 161     if (UNLIKELY(slot.isTaintedByOpaqueObject()))
 162         return object->get(exec, index);
 163     return slot.getValue(exec, index);
 164 }
 165
 166 static ALWAYS_INLINE bool putLength(ExecState* exec, VM& vm, JSObject* obj, JSValue value)
 167 {
 168     PutPropertySlot slot(obj);
 169     return obj->methodTable()->put(obj, exec, vm.propertyNames->length, value, slot);
 170 }
 171
 172 static ALWAYS_INLINE void setLength(ExecState* exec, VM& vm, JSObject* obj, unsigned value)
 173 {
 174     auto scope = DECLARE_THROW_SCOPE(vm);
 175     static const bool throwException = true;
 176     if (isJSArray(obj)) {
 177         jsCast<JSArray*>(obj)->setLength(exec, value, throwException);
 178         RETURN_IF_EXCEPTION(scope, void());
 179     }
 180     bool success = putLength(exec, vm, obj, jsNumber(value));
 181     RETURN_IF_EXCEPTION(scope, void());
 182     if (UNLIKELY(!success))
 183         throwTypeError(exec, scope, ASCIILiteral(ReadonlyPropertyWriteError));
 184 }
 185
 186 inline bool speciesWatchpointsValid(ExecState* exec, JSObject* thisObject)
 187 {
 188     ArrayPrototype* arrayPrototype = thisObject->globalObject()->arrayPrototype();
 189     ArrayPrototype::SpeciesWatchpointStatus status = arrayPrototype->speciesWatchpointStatus();
 190     if (UNLIKELY(status == ArrayPrototype::SpeciesWatchpointStatus::Uninitialized))
 191         status = arrayPrototype->attemptToInitializeSpeciesWatchpoint(exec);
 192     ASSERT(status != ArrayPrototype::SpeciesWatchpointStatus::Uninitialized);
 193     return !thisObject->hasCustomProperties()
 194         && arrayPrototype == thisObject->getPrototypeDirect()
 195         && status == ArrayPrototype::SpeciesWatchpointStatus::Initialized;
 196 }
 197
 198 enum class SpeciesConstructResult {
 199     FastPath,
 200     Exception,
 201     CreatedObject
 202 };
 203
 204 static ALWAYS_INLINE std::pair<SpeciesConstructResult, JSObject*> speciesConstructArray(ExecState* exec, JSObject* thisObject, unsigned length)
 205 {
 206     VM& vm = exec->vm();
 207     auto scope = DECLARE_THROW_SCOPE(vm);
 208
 209     auto exceptionResult = [] () {
 210         return std::make_pair(SpeciesConstructResult::Exception, nullptr);
 211     };
 212
 213     // ECMA 9.4.2.3: https://tc39.github.io/ecma262/#sec-arrayspeciescreate
 214     JSValue constructor = jsUndefined();
 215     if (LIKELY(isArray(exec, thisObject))) {
 216         // Fast path in the normal case where the user has not set an own constructor and the Array.prototype.constructor is normal.
 217         // We need prototype check for subclasses of Array, which are Array objects but have a different prototype by default.
 218         if (LIKELY(speciesWatchpointsValid(exec, thisObject)))
 219             return std::make_pair(SpeciesConstructResult::FastPath, nullptr);
 220
 221         constructor = thisObject->get(exec, exec->propertyNames().constructor);
 222         RETURN_IF_EXCEPTION(scope, exceptionResult());
 223         if (constructor.isConstructor()) {
 224             JSObject* constructorObject = jsCast<JSObject*>(constructor);
 225             if (exec->lexicalGlobalObject() != constructorObject->globalObject())
 226                 return std::make_pair(SpeciesConstructResult::FastPath, nullptr);;
 227         }
 228         if (constructor.isObject()) {
 229             constructor = constructor.get(exec, exec->propertyNames().speciesSymbol);
 230             RETURN_IF_EXCEPTION(scope, exceptionResult());
 231             if (constructor.isNull())
 232                 return std::make_pair(SpeciesConstructResult::FastPath, nullptr);;
 233         }
 234     } else
 235         RETURN_IF_EXCEPTION(scope, exceptionResult());
 236
 237     if (constructor.isUndefined())
 238         return std::make_pair(SpeciesConstructResult::FastPath, nullptr);
 239
 240     MarkedArgumentBuffer args;
 241     args.append(jsNumber(length));
 242     JSObject* newObject = construct(exec, constructor, args, "Species construction did not get a valid constructor");
 243     RETURN_IF_EXCEPTION(scope, exceptionResult());
 244     return std::make_pair(SpeciesConstructResult::CreatedObject, newObject);
 245 }
 246
 247 static inline unsigned argumentClampedIndexFromStartOrEnd(ExecState* exec, int argument, unsigned length, unsigned undefinedValue = 0)
 248 {
 249     JSValue value = exec->argument(argument);
 250     if (value.isUndefined())
 251         return undefinedValue;
 252
 253     double indexDouble = value.toInteger(exec);
 254     if (indexDouble < 0) {
 255         indexDouble += length;
 256         return indexDouble < 0 ? 0 : static_cast<unsigned>(indexDouble);
 257     }
 258     return indexDouble > length ? length : static_cast<unsigned>(indexDouble);
 259 }
 260
 261 // The shift/unshift function implement the shift/unshift behaviour required
 262 // by the corresponding array prototype methods, and by splice. In both cases,
 263 // the methods are operating an an array or array like object.
 264 //
 265 //  header  currentCount  (remainder)
 266 // [------][------------][-----------]
 267 //  header  resultCount  (remainder)
 268 // [------][-----------][-----------]
 269 //
 270 // The set of properties in the range 'header' must be unchanged. The set of
 271 // properties in the range 'remainder' (where remainder = length - header -
 272 // currentCount) will be shifted to the left or right as appropriate; in the
 273 // case of shift this must be removing values, in the case of unshift this
 274 // must be introducing new values.
 275
 276 template<JSArray::ShiftCountMode shiftCountMode>
 277 void shift(ExecState* exec, JSObject* thisObj, unsigned header, unsigned currentCount, unsigned resultCount, unsigned length)
 278 {
 279     VM& vm = exec->vm();
 280     auto scope = DECLARE_THROW_SCOPE(vm);
 281
 282     RELEASE_ASSERT(currentCount > resultCount);
 283     unsigned count = currentCount - resultCount;
 284
 285     RELEASE_ASSERT(header <= length);
 286     RELEASE_ASSERT(currentCount <= (length - header));
 287
 288     if (isJSArray(thisObj)) {
 289         JSArray* array = asArray(thisObj);
 290         if (array->length() == length && array->shiftCount<shiftCountMode>(exec, header, count))
 291             return;
 292     }
 293
 294     for (unsigned k = header; k < length - currentCount; ++k) {
 295         unsigned from = k + currentCount;
 296         unsigned to = k + resultCount;
 297         if (JSValue value = getProperty(exec, thisObj, from)) {
 298             RETURN_IF_EXCEPTION(scope, void());
 299             thisObj->putByIndexInline(exec, to, value, true);
 300             RETURN_IF_EXCEPTION(scope, void());
 301         } else if (!thisObj->methodTable(vm)->deletePropertyByIndex(thisObj, exec, to)) {
 302             throwTypeError(exec, scope, ASCIILiteral("Unable to delete property."));
 303             return;
 304         }
 305     }
 306     for (unsigned k = length; k > length - count; --k) {
 307         if (!thisObj->methodTable(vm)->deletePropertyByIndex(thisObj, exec, k - 1)) {
 308             throwTypeError(exec, scope, ASCIILiteral("Unable to delete property."));
 309             return;
 310         }
 311     }
 312 }
 313
 314 template<JSArray::ShiftCountMode shiftCountMode>
 315 void unshift(ExecState* exec, JSObject* thisObj, unsigned header, unsigned currentCount, unsigned resultCount, unsigned length)
 316 {
 317     VM& vm = exec->vm();
 318     auto scope = DECLARE_THROW_SCOPE(vm);
 319
 320     RELEASE_ASSERT(resultCount > currentCount);
 321     unsigned count = resultCount - currentCount;
 322
 323     RELEASE_ASSERT(header <= length);
 324     RELEASE_ASSERT(currentCount <= (length - header));
 325
 326     // Guard against overflow.
 327     if (count > (UINT_MAX - length)) {
 328         throwOutOfMemoryError(exec, scope);
 329         return;
 330     }
 331
 332     if (isJSArray(thisObj)) {
 333         JSArray* array = asArray(thisObj);
 334         if (array->length() == length && array->unshiftCount<shiftCountMode>(exec, header, count))
 335             return;
 336     }
 337
 338     for (unsigned k = length - currentCount; k > header; --k) {
 339         unsigned from = k + currentCount - 1;
 340         unsigned to = k + resultCount - 1;
 341         if (JSValue value = getProperty(exec, thisObj, from)) {
 342             RETURN_IF_EXCEPTION(scope, void());
 343             thisObj->putByIndexInline(exec, to, value, true);
 344         } else if (!thisObj->methodTable(vm)->deletePropertyByIndex(thisObj, exec, to)) {
 345             throwTypeError(exec, scope, ASCIILiteral("Unable to delete property."));
 346             return;
 347         }
 348         RETURN_IF_EXCEPTION(scope, void());
 349     }
 350 }
 351
 352 EncodedJSValue JSC_HOST_CALL arrayProtoFuncToString(ExecState* exec)
 353 {
 354     VM& vm = exec->vm();
 355     auto scope = DECLARE_THROW_SCOPE(vm);
 356     JSValue thisValue = exec->thisValue().toThis(exec, StrictMode);
 357
 358     // 1. Let array be the result of calling ToObject on the this value.
 359     JSObject* thisObject = thisValue.toObject(exec);
 360     RETURN_IF_EXCEPTION(scope, encodedJSValue());
 361
 362     // 2. Let func be the result of calling the [[Get]] internal method of array with argument "join".
 363     JSValue function = JSValue(thisObject).get(exec, exec->propertyNames().join);
 364     RETURN_IF_EXCEPTION(scope, encodedJSValue());
 365
 366     // 3. If IsCallable(func) is false, then let func be the standard built-in method Object.prototype.toString (15.2.4.2).
 367     bool customJoinCase = false;
 368     if (!function.isCell())
 369         customJoinCase = true;
 370     CallData callData;
 371     CallType callType = getCallData(function, callData);
 372     if (callType == CallType::None)
 373         customJoinCase = true;
 374
 375     if (UNLIKELY(customJoinCase))
 376         return JSValue::encode(jsMakeNontrivialString(exec, "[object ", thisObject->methodTable(vm)->className(thisObject), "]"));
 377
 378     // 4. Return the result of calling the [[Call]] internal method of func providing array as the this value and an empty arguments list.
 379     if (!isJSArray(thisObject) || callType != CallType::Host || callData.native.function != arrayProtoFuncJoin)
 380         return JSValue::encode(call(exec, function, callType, callData, thisObject, exec->emptyList()));
 381
 382     ASSERT(isJSArray(thisValue));
 383     JSArray* thisArray = asArray(thisValue);
 384
 385     unsigned length = thisArray->length();
 386
 387     StringRecursionChecker checker(exec, thisArray);
 388     if (JSValue earlyReturnValue = checker.earlyReturnValue())
 389         return JSValue::encode(earlyReturnValue);
 390
 391     JSStringJoiner joiner(*exec, ',', length);
 392     RETURN_IF_EXCEPTION(scope, encodedJSValue());
 393
 394     for (unsigned i = 0; i < length; ++i) {
 395         JSValue element = thisArray->tryGetIndexQuickly(i);
 396         if (!element) {
 397             element = thisArray->get(exec, i);
 398             RETURN_IF_EXCEPTION(scope, encodedJSValue());
 399         }
 400         joiner.append(*exec, element);
 401         RETURN_IF_EXCEPTION(scope, encodedJSValue());
 402     }
 403
 404     return JSValue::encode(joiner.join(*exec));
 405 }
 406
 407 EncodedJSValue JSC_HOST_CALL arrayProtoFuncToLocaleString(ExecState* exec)
 408 {
 409     VM& vm = exec->vm();
 410     auto scope = DECLARE_THROW_SCOPE(vm);
 411     JSValue thisValue = exec->thisValue().toThis(exec, StrictMode);
 412
 413     JSObject* thisObject = thisValue.toObject(exec);
 414     RETURN_IF_EXCEPTION(scope, encodedJSValue());
 415
 416     unsigned length = getLength(exec, thisObject);
 417     RETURN_IF_EXCEPTION(scope, encodedJSValue());
 418
 419     StringRecursionChecker checker(exec, thisObject);
 420     if (JSValue earlyReturnValue = checker.earlyReturnValue())
 421         return JSValue::encode(earlyReturnValue);
 422
 423     JSStringJoiner stringJoiner(*exec, ',', length);
 424     RETURN_IF_EXCEPTION(scope, encodedJSValue());
 425
 426 #if ENABLE(INTL)
 427     ArgList arguments(exec);
 428     for (unsigned i = 0; i < length; ++i) {
 429         JSValue element = thisObject->getIndex(exec, i);
 430         RETURN_IF_EXCEPTION(scope, encodedJSValue());
 431         if (element.isUndefinedOrNull())
 432             element = jsEmptyString(exec);
 433         else {
 434             JSValue conversionFunction = element.get(exec, exec->propertyNames().toLocaleString);
 435             RETURN_IF_EXCEPTION(scope, encodedJSValue());
 436             CallData callData;
 437             CallType callType = getCallData(conversionFunction, callData);
 438             if (callType != CallType::None) {
 439                 element = call(exec, conversionFunction, callType, callData, element, arguments);
 440                 RETURN_IF_EXCEPTION(scope, encodedJSValue());
 441             }
 442         }
 443         stringJoiner.append(*exec, element);
 444         RETURN_IF_EXCEPTION(scope, encodedJSValue());
 445     }
 446 #else // !ENABLE(INTL)
 447     for (unsigned i = 0; i < length; ++i) {
 448         JSValue element = thisObject->getIndex(exec, i);
 449         RETURN_IF_EXCEPTION(scope, encodedJSValue());
 450         if (element.isUndefinedOrNull())
 451             continue;
 452         JSValue conversionFunction = element.get(exec, exec->propertyNames().toLocaleString);
 453         RETURN_IF_EXCEPTION(scope, encodedJSValue());
 454         CallData callData;
 455         CallType callType = getCallData(conversionFunction, callData);
 456         if (callType != CallType::None) {
 457             element = call(exec, conversionFunction, callType, callData, element, exec->emptyList());
 458             RETURN_IF_EXCEPTION(scope, encodedJSValue());
 459         }
 460         stringJoiner.append(*exec, element);
 461         RETURN_IF_EXCEPTION(scope, encodedJSValue());
 462     }
 463 #endif // !ENABLE(INTL)
 464
 465     return JSValue::encode(stringJoiner.join(*exec));
 466 }
 467
 468 static inline bool isHole(double value)
 469 {
 470     return std::isnan(value);
 471 }
 472
 473 static inline bool isHole(const WriteBarrier<Unknown>& value)
 474 {
 475     return !value;
 476 }
 477
 478 template<typename T> static inline bool containsHole(T* data, unsigned length)
 479 {
 480     for (unsigned i = 0; i < length; ++i) {
 481         if (isHole(data[i]))
 482             return true;
 483     }
 484     return false;
 485 }
 486
 487 static inline bool holesMustForwardToPrototype(ExecState& state, JSObject* object)
 488 {
 489     auto& vm = state.vm();
 490     return object->structure(vm)->holesMustForwardToPrototype(vm);
 491 }
 492
 493 static JSValue slowJoin(ExecState& exec, JSObject* thisObject, JSString* separator, uint64_t length)
 494 {
 495     VM& vm = exec.vm();
 496     auto scope = DECLARE_THROW_SCOPE(vm);
 497
 498     // 5. If len is zero, return the empty String.
 499     if (!length)
 500         return jsEmptyString(&exec);
 501
 502     // 6. Let element0 be Get(O, "0").
 503     JSValue element0 = thisObject->getIndex(&exec, 0);
 504     RETURN_IF_EXCEPTION(scope, JSValue());
 505
 506     // 7. If element0 is undefined or null, let R be the empty String; otherwise, let R be ? ToString(element0).
 507     JSString* r = nullptr;
 508     if (element0.isUndefinedOrNull())
 509         r = jsEmptyString(&exec);
 510     else
 511         r = element0.toString(&exec);
 512     RETURN_IF_EXCEPTION(scope, JSValue());
 513
 514     // 8. Let k be 1.
 515     // 9. Repeat, while k < len
 516     // 9.e Increase k by 1..
 517     for (uint64_t k = 1; k < length; ++k) {
 518         // b. Let element be ? Get(O, ! ToString(k)).
 519         JSValue element = thisObject->get(&exec, Identifier::fromString(&exec, AtomicString::number(k)));
 520         RETURN_IF_EXCEPTION(scope, JSValue());
 521
 522         // c. If element is undefined or null, let next be the empty String; otherwise, let next be ? ToString(element).
 523         JSString* next = nullptr;
 524         if (element.isUndefinedOrNull()) {
 525             if (!separator->length())
 526                 continue;
 527             next = jsEmptyString(&exec);
 528         } else
 529             next = element.toString(&exec);
 530         RETURN_IF_EXCEPTION(scope, JSValue());
 531
 532         // a. Let S be the String value produced by concatenating R and sep.
 533         // d. Let R be a String value produced by concatenating S and next.
 534         r = jsString(&exec, r, separator, next);
 535         RETURN_IF_EXCEPTION(scope, JSValue());
 536     }
 537     // 10. Return R.
 538     return r;
 539 }
 540
 541 static inline bool canUseFastJoin(const JSObject* thisObject)
 542 {
 543     switch (thisObject->indexingType()) {
 544     case ALL_CONTIGUOUS_INDEXING_TYPES:
 545     case ALL_INT32_INDEXING_TYPES:
 546     case ALL_DOUBLE_INDEXING_TYPES:
 547         return true;
 548     default:
 549         break;
 550     }
 551     return false;
 552 }
 553
 554 static inline JSValue fastJoin(ExecState& state, JSObject* thisObject, StringView separator, unsigned length)
 555 {
 556     VM& vm = state.vm();
 557     auto scope = DECLARE_THROW_SCOPE(vm);
 558
 559     switch (thisObject->indexingType()) {
 560     case ALL_CONTIGUOUS_INDEXING_TYPES:
 561     case ALL_INT32_INDEXING_TYPES: {
 562         auto& butterfly = *thisObject->butterfly();
 563         if (length > butterfly.publicLength())
 564             break;
 565         JSStringJoiner joiner(state, separator, length);
 566         RETURN_IF_EXCEPTION(scope, JSValue());
 567         auto data = butterfly.contiguous().data();
 568         bool holesKnownToBeOK = false;
 569         for (unsigned i = 0; i < length; ++i) {
 570             if (JSValue value = data[i].get()) {
 571                 if (!joiner.appendWithoutSideEffects(state, value))
 572                     goto generalCase;
 573             } else {
 574                 if (!holesKnownToBeOK) {
 575                     if (holesMustForwardToPrototype(state, thisObject))
 576                         goto generalCase;
 577                     holesKnownToBeOK = true;
 578                 }
 579                 joiner.appendEmptyString();
 580             }
 581         }
 582         return joiner.join(state);
 583     }
 584     case ALL_DOUBLE_INDEXING_TYPES: {
 585         auto& butterfly = *thisObject->butterfly();
 586         if (length > butterfly.publicLength())
 587             break;
 588         JSStringJoiner joiner(state, separator, length);
 589         RETURN_IF_EXCEPTION(scope, JSValue());
 590         auto data = butterfly.contiguousDouble().data();
 591         bool holesKnownToBeOK = false;
 592         for (unsigned i = 0; i < length; ++i) {
 593             double value = data[i];
 594             if (!isHole(value))
 595                 joiner.append(state, jsDoubleNumber(value));
 596             else {
 597                 if (!holesKnownToBeOK) {
 598                     if (thisObject->structure(vm)->holesMustForwardToPrototype(vm))
 599                         goto generalCase;
 600                     holesKnownToBeOK = true;
 601                 }
 602                 joiner.appendEmptyString();
 603             }
 604         }
 605         return joiner.join(state);
 606     }
 607     }
 608
 609 generalCase:
 610     JSStringJoiner joiner(state, separator, length);
 611     RETURN_IF_EXCEPTION(scope, JSValue());
 612     for (unsigned i = 0; i < length; ++i) {
 613         JSValue element = thisObject->getIndex(&state, i);
 614         RETURN_IF_EXCEPTION(scope, JSValue());
 615         joiner.append(state, element);
 616         RETURN_IF_EXCEPTION(scope, JSValue());
 617     }
 618     return joiner.join(state);
 619 }
 620
 621 EncodedJSValue JSC_HOST_CALL arrayProtoFuncJoin(ExecState* exec)
 622 {
 623     VM& vm = exec->vm();
 624     auto scope = DECLARE_THROW_SCOPE(vm);
 625
 626     // 1. Let O be ? ToObject(this value).
 627     JSObject* thisObject = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
 628     if (!thisObject)
 629         return JSValue::encode(JSValue());
 630
 631     StringRecursionChecker checker(exec, thisObject);
 632     if (JSValue earlyReturnValue = checker.earlyReturnValue())
 633         return JSValue::encode(earlyReturnValue);
 634
 635     // 2. Let len be ? ToLength(? Get(O, "length")).
 636     double length = toLength(exec, thisObject);
 637     RETURN_IF_EXCEPTION(scope, encodedJSValue());
 638
 639     // 3. If separator is undefined, let separator be the single-element String ",".
 640     JSValue separatorValue = exec->argument(0);
 641     if (separatorValue.isUndefined()) {
 642         const LChar comma = ',';
 643
 644         if (UNLIKELY(length > std::numeric_limits<unsigned>::max() || !canUseFastJoin(thisObject))) {
 645             uint64_t length64 = static_cast<uint64_t>(length);
 646             ASSERT(static_cast<double>(length64) == length);
 647             JSString* jsSeparator = jsSingleCharacterString(exec, comma);
 648             RETURN_IF_EXCEPTION(scope, encodedJSValue());
 649
 650             return JSValue::encode(slowJoin(*exec, thisObject, jsSeparator, length64));
 651         }
 652
 653         unsigned unsignedLength = static_cast<unsigned>(length);
 654         ASSERT(static_cast<double>(unsignedLength) == length);
 655         return JSValue::encode(fastJoin(*exec, thisObject, { &comma, 1 }, unsignedLength));
 656     }
 657
 658     // 4. Let sep be ? ToString(separator).
 659     JSString* jsSeparator = separatorValue.toString(exec);
 660     RETURN_IF_EXCEPTION(scope, encodedJSValue());
 661
 662     if (UNLIKELY(length > std::numeric_limits<unsigned>::max() || !canUseFastJoin(thisObject))) {
 663         uint64_t length64 = static_cast<uint64_t>(length);
 664         ASSERT(static_cast<double>(length64) == length);
 665         return JSValue::encode(slowJoin(*exec, thisObject, jsSeparator, length64));
 666     }
 667
 668     return JSValue::encode(fastJoin(*exec, thisObject, jsSeparator->view(exec).get(), length));
 669 }
 670
 671 EncodedJSValue JSC_HOST_CALL arrayProtoFuncPop(ExecState* exec)
 672 {
 673     VM& vm = exec->vm();
 674     auto scope = DECLARE_THROW_SCOPE(vm);
 675
 676     JSValue thisValue = exec->thisValue().toThis(exec, StrictMode);
 677
 678     if (isJSArray(thisValue))
 679         return JSValue::encode(asArray(thisValue)->pop(exec));
 680
 681     JSObject* thisObj = thisValue.toObject(exec);
 682     if (!thisObj)
 683         return JSValue::encode(JSValue());
 684     unsigned length = getLength(exec, thisObj);
 685     RETURN_IF_EXCEPTION(scope, encodedJSValue());
 686
 687     JSValue result;
 688     if (length == 0) {
 689         putLength(exec, vm, thisObj, jsNumber(length));
 690         result = jsUndefined();
 691     } else {
 692         result = thisObj->get(exec, length - 1);
 693         RETURN_IF_EXCEPTION(scope, encodedJSValue());
 694         if (!thisObj->methodTable(vm)->deletePropertyByIndex(thisObj, exec, length - 1)) {
 695             throwTypeError(exec, scope, ASCIILiteral("Unable to delete property."));
 696             return JSValue::encode(jsUndefined());
 697         }
 698         putLength(exec, vm, thisObj, jsNumber(length - 1));
 699     }
 700     return JSValue::encode(result);
 701 }
 702
 703 EncodedJSValue JSC_HOST_CALL arrayProtoFuncPush(ExecState* exec)
 704 {
 705     VM& vm = exec->vm();
 706     auto scope = DECLARE_THROW_SCOPE(vm);
 707     JSValue thisValue = exec->thisValue().toThis(exec, StrictMode);
 708
 709     if (isJSArray(thisValue) && exec->argumentCount() == 1) {
 710         JSArray* array = asArray(thisValue);
 711         array->push(exec, exec->uncheckedArgument(0));
 712         return JSValue::encode(jsNumber(array->length()));
 713     }
 714
 715     JSObject* thisObj = thisValue.toObject(exec);
 716     if (!thisObj)
 717         return JSValue::encode(JSValue());
 718     unsigned length = getLength(exec, thisObj);
 719     RETURN_IF_EXCEPTION(scope, encodedJSValue());
 720
 721     for (unsigned n = 0; n < exec->argumentCount(); n++) {
 722         // Check for integer overflow; where safe we can do a fast put by index.
 723         if (length + n >= length)
 724             thisObj->methodTable()->putByIndex(thisObj, exec, length + n, exec->uncheckedArgument(n), true);
 725         else {
 726             PutPropertySlot slot(thisObj);
 727             Identifier propertyName = Identifier::fromString(exec, JSValue(static_cast<int64_t>(length) + static_cast<int64_t>(n)).toWTFString(exec));
 728             thisObj->methodTable()->put(thisObj, exec, propertyName, exec->uncheckedArgument(n), slot);
 729         }
 730         RETURN_IF_EXCEPTION(scope, encodedJSValue());
 731     }
 732
 733     JSValue newLength(static_cast<int64_t>(length) + static_cast<int64_t>(exec->argumentCount()));
 734     putLength(exec, vm, thisObj, newLength);
 735     return JSValue::encode(newLength);
 736 }
 737
 738 EncodedJSValue JSC_HOST_CALL arrayProtoFuncReverse(ExecState* exec)
 739 {
 740     VM& vm = exec->vm();
 741     auto scope = DECLARE_THROW_SCOPE(vm);
 742
 743     JSObject* thisObject = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
 744     if (!thisObject)
 745         return JSValue::encode(JSValue());
 746
 747     unsigned length = getLength(exec, thisObject);
 748     RETURN_IF_EXCEPTION(scope, encodedJSValue());
 749
 750     switch (thisObject->indexingType()) {
 751     case ALL_CONTIGUOUS_INDEXING_TYPES:
 752     case ALL_INT32_INDEXING_TYPES: {
 753         auto& butterfly = *thisObject->butterfly();
 754         if (length > butterfly.publicLength())
 755             break;
 756         auto data = butterfly.contiguous().data();
 757         if (containsHole(data, length) && holesMustForwardToPrototype(*exec, thisObject))
 758             break;
 759         std::reverse(data, data + length);
 760         return JSValue::encode(thisObject);
 761     }
 762     case ALL_DOUBLE_INDEXING_TYPES: {
 763         auto& butterfly = *thisObject->butterfly();
 764         if (length > butterfly.publicLength())
 765             break;
 766         auto data = butterfly.contiguousDouble().data();
 767         if (containsHole(data, length) && holesMustForwardToPrototype(*exec, thisObject))
 768             break;
 769         std::reverse(data, data + length);
 770         return JSValue::encode(thisObject);
 771     }
 772     case ALL_ARRAY_STORAGE_INDEXING_TYPES: {
 773         auto& storage = *thisObject->butterfly()->arrayStorage();
 774         if (length > storage.vectorLength())
 775             break;
 776         if (storage.hasHoles() && holesMustForwardToPrototype(*exec, thisObject))
 777             break;
 778         auto data = storage.vector().data();
 779         std::reverse(data, data + length);
 780         return JSValue::encode(thisObject);
 781     }
 782     }
 783
 784     unsigned middle = length / 2;
 785     for (unsigned lower = 0; lower < middle; lower++) {
 786         unsigned upper = length - lower - 1;
 787         bool lowerExists = thisObject->hasProperty(exec, lower);
 788         RETURN_IF_EXCEPTION(scope, encodedJSValue());
 789         JSValue lowerValue;
 790         if (lowerExists) {
 791             lowerValue = thisObject->get(exec, lower);
 792             RETURN_IF_EXCEPTION(scope, encodedJSValue());
 793         }
 794
 795         bool upperExists = thisObject->hasProperty(exec, upper);
 796         RETURN_IF_EXCEPTION(scope, encodedJSValue());
 797         JSValue upperValue;
 798         if (upperExists) {
 799             upperValue = thisObject->get(exec, upper);
 800             RETURN_IF_EXCEPTION(scope, encodedJSValue());
 801         }
 802
 803         if (upperExists) {
 804             thisObject->putByIndexInline(exec, lower, upperValue, true);
 805             RETURN_IF_EXCEPTION(scope, encodedJSValue());
 806         } else if (!thisObject->methodTable(vm)->deletePropertyByIndex(thisObject, exec, lower)) {
 807             if (!scope.exception())
 808                 throwTypeError(exec, scope, ASCIILiteral("Unable to delete property."));
 809             return JSValue::encode(JSValue());
 810         }
 811
 812         if (lowerExists) {
 813             thisObject->putByIndexInline(exec, upper, lowerValue, true);
 814             RETURN_IF_EXCEPTION(scope, encodedJSValue());
 815         } else if (!thisObject->methodTable(vm)->deletePropertyByIndex(thisObject, exec, upper)) {
 816             if (!scope.exception())
 817                 throwTypeError(exec, scope, ASCIILiteral("Unable to delete property."));
 818             return JSValue::encode(JSValue());
 819         }
 820     }
 821     return JSValue::encode(thisObject);
 822 }
 823
 824 EncodedJSValue JSC_HOST_CALL arrayProtoFuncShift(ExecState* exec)
 825 {
 826     VM& vm = exec->vm();
 827     auto scope = DECLARE_THROW_SCOPE(vm);
 828     JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
 829     if (!thisObj)
 830         return JSValue::encode(JSValue());
 831     unsigned length = getLength(exec, thisObj);
 832     RETURN_IF_EXCEPTION(scope, encodedJSValue());
 833
 834     JSValue result;
 835     if (length == 0) {
 836         putLength(exec, vm, thisObj, jsNumber(length));
 837         result = jsUndefined();
 838     } else {
 839         result = thisObj->getIndex(exec, 0);
 840         shift<JSArray::ShiftCountForShift>(exec, thisObj, 0, 1, 0, length);
 841         RETURN_IF_EXCEPTION(scope, encodedJSValue());
 842         putLength(exec, vm, thisObj, jsNumber(length - 1));
 843     }
 844     return JSValue::encode(result);
 845 }
 846
 847 EncodedJSValue JSC_HOST_CALL arrayProtoFuncSlice(ExecState* exec)
 848 {
 849     // http://developer.netscape.com/docs/manuals/js/client/jsref/array.htm#1193713 or 15.4.4.10
 850     VM& vm = exec->vm();
 851     auto scope = DECLARE_THROW_SCOPE(vm);
 852     JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
 853     if (!thisObj)
 854         return JSValue::encode(JSValue());
 855     unsigned length = getLength(exec, thisObj);
 856     RETURN_IF_EXCEPTION(scope, encodedJSValue());
 857
 858     unsigned begin = argumentClampedIndexFromStartOrEnd(exec, 0, length);
 859     unsigned end = argumentClampedIndexFromStartOrEnd(exec, 1, length, length);
 860
 861     std::pair<SpeciesConstructResult, JSObject*> speciesResult = speciesConstructArray(exec, thisObj, end - begin);
 862     // We can only get an exception if we call some user function.
 863     if (UNLIKELY(speciesResult.first == SpeciesConstructResult::Exception))
 864         return JSValue::encode(jsUndefined());
 865
 866     if (LIKELY(speciesResult.first == SpeciesConstructResult::FastPath && isJSArray(thisObj) && length == getLength(exec, thisObj))) {
 867         if (JSArray* result = asArray(thisObj)->fastSlice(*exec, begin, end - begin))
 868             return JSValue::encode(result);
 869     }
 870
 871     JSObject* result;
 872     if (speciesResult.first == SpeciesConstructResult::CreatedObject)
 873         result = speciesResult.second;
 874     else {
 875         result = constructEmptyArray(exec, nullptr, end - begin);
 876         RETURN_IF_EXCEPTION(scope, encodedJSValue());
 877     }
 878
 879     unsigned n = 0;
 880     for (unsigned k = begin; k < end; k++, n++) {
 881         JSValue v = getProperty(exec, thisObj, k);
 882         RETURN_IF_EXCEPTION(scope, encodedJSValue());
 883         if (v)
 884             result->putDirectIndex(exec, n, v, 0, PutDirectIndexShouldThrow);
 885     }
 886     scope.release();
 887     setLength(exec, vm, result, n);
 888     return JSValue::encode(result);
 889 }
 890
 891 EncodedJSValue JSC_HOST_CALL arrayProtoFuncSplice(ExecState* exec)
 892 {
 893     // 15.4.4.12
 894
 895     VM& vm = exec->vm();
 896     auto scope = DECLARE_THROW_SCOPE(vm);
 897
 898     JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
 899     if (!thisObj)
 900         return JSValue::encode(JSValue());
 901     unsigned length = getLength(exec, thisObj);
 902     RETURN_IF_EXCEPTION(scope, encodedJSValue());
 903
 904     if (!exec->argumentCount()) {
 905         std::pair<SpeciesConstructResult, JSObject*> speciesResult = speciesConstructArray(exec, thisObj, 0);
 906         if (speciesResult.first == SpeciesConstructResult::Exception)
 907             return JSValue::encode(jsUndefined());
 908
 909         JSObject* result;
 910         if (speciesResult.first == SpeciesConstructResult::CreatedObject)
 911             result = speciesResult.second;
 912         else {
 913             result = constructEmptyArray(exec, nullptr);
 914             RETURN_IF_EXCEPTION(scope, encodedJSValue());
 915         }
 916
 917         setLength(exec, vm, result, 0);
 918         RETURN_IF_EXCEPTION(scope, encodedJSValue());
 919         scope.release();
 920         setLength(exec, vm, thisObj, length);
 921         return JSValue::encode(result);
 922     }
 923
 924     unsigned actualStart = argumentClampedIndexFromStartOrEnd(exec, 0, length);
 925
 926     unsigned actualDeleteCount = length - actualStart;
 927     if (exec->argumentCount() > 1) {
 928         double deleteCount = exec->uncheckedArgument(1).toInteger(exec);
 929         if (deleteCount < 0)
 930             actualDeleteCount = 0;
 931         else if (deleteCount > length - actualStart)
 932             actualDeleteCount = length - actualStart;
 933         else
 934             actualDeleteCount = static_cast<unsigned>(deleteCount);
 935     }
 936
 937     std::pair<SpeciesConstructResult, JSObject*> speciesResult = speciesConstructArray(exec, thisObj, actualDeleteCount);
 938     if (speciesResult.first == SpeciesConstructResult::Exception)
 939         return JSValue::encode(jsUndefined());
 940
 941     JSObject* result = nullptr;
 942     if (speciesResult.first == SpeciesConstructResult::FastPath && isJSArray(thisObj) && length == getLength(exec, thisObj))
 943         result = asArray(thisObj)->fastSlice(*exec, actualStart, actualDeleteCount);
 944
 945     if (!result) {
 946         if (speciesResult.first == SpeciesConstructResult::CreatedObject) {
 947             result = speciesResult.second;
 948
 949             for (unsigned k = 0; k < actualDeleteCount; ++k) {
 950                 JSValue v = getProperty(exec, thisObj, k + actualStart);
 951                 RETURN_IF_EXCEPTION(scope, encodedJSValue());
 952                 if (UNLIKELY(!v))
 953                     continue;
 954                 result->putByIndexInline(exec, k, v, true);
 955                 RETURN_IF_EXCEPTION(scope, encodedJSValue());
 956             }
 957         } else {
 958             result = JSArray::tryCreateUninitialized(vm, exec->lexicalGlobalObject()->arrayStructureForIndexingTypeDuringAllocation(ArrayWithUndecided), actualDeleteCount);
 959             if (!result)
 960                 return JSValue::encode(throwOutOfMemoryError(exec, scope));
 961
 962             for (unsigned k = 0; k < actualDeleteCount; ++k) {
 963                 JSValue v = getProperty(exec, thisObj, k + actualStart);
 964                 RETURN_IF_EXCEPTION(scope, encodedJSValue());
 965                 if (UNLIKELY(!v))
 966                     continue;
 967                 result->initializeIndex(vm, k, v);
 968             }
 969         }
 970     }
 971
 972     unsigned itemCount = std::max<int>(exec->argumentCount() - 2, 0);
 973     if (itemCount < actualDeleteCount) {
 974         shift<JSArray::ShiftCountForSplice>(exec, thisObj, actualStart, actualDeleteCount, itemCount, length);
 975         RETURN_IF_EXCEPTION(scope, encodedJSValue());
 976     } else if (itemCount > actualDeleteCount) {
 977         unshift<JSArray::ShiftCountForSplice>(exec, thisObj, actualStart, actualDeleteCount, itemCount, length);
 978         RETURN_IF_EXCEPTION(scope, encodedJSValue());
 979     }
 980     for (unsigned k = 0; k < itemCount; ++k) {
 981         thisObj->putByIndexInline(exec, k + actualStart, exec->uncheckedArgument(k + 2), true);
 982         RETURN_IF_EXCEPTION(scope, encodedJSValue());
 983     }
 984
 985     scope.release();
 986     setLength(exec, vm, thisObj, length - actualDeleteCount + itemCount);
 987     return JSValue::encode(result);
 988 }
 989
 990 EncodedJSValue JSC_HOST_CALL arrayProtoFuncUnShift(ExecState* exec)
 991 {
 992     VM& vm = exec->vm();
 993     auto scope = DECLARE_THROW_SCOPE(vm);
 994     // 15.4.4.13
 995
 996     JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
 997     if (!thisObj)
 998         return JSValue::encode(JSValue());
 999     unsigned length = getLength(exec, thisObj);
1000     RETURN_IF_EXCEPTION(scope, encodedJSValue());
1001
1002     unsigned nrArgs = exec->argumentCount();
1003     if (nrArgs) {
1004         unshift<JSArray::ShiftCountForShift>(exec, thisObj, 0, 0, nrArgs, length);
1005         RETURN_IF_EXCEPTION(scope, encodedJSValue());
1006     }
1007     for (unsigned k = 0; k < nrArgs; ++k) {
1008         thisObj->putByIndexInline(exec, k, exec->uncheckedArgument(k), true);
1009         RETURN_IF_EXCEPTION(scope, encodedJSValue());
1010     }
1011     JSValue result = jsNumber(length + nrArgs);
1012     putLength(exec, vm, thisObj, result);
1013     return JSValue::encode(result);
1014 }
1015
1016 EncodedJSValue JSC_HOST_CALL arrayProtoFuncIndexOf(ExecState* exec)
1017 {
1018     VM& vm = exec->vm();
1019     auto scope = DECLARE_THROW_SCOPE(vm);
1020
1021     // 15.4.4.14
1022     JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
1023     if (!thisObj)
1024         return JSValue::encode(JSValue());
1025     unsigned length = getLength(exec, thisObj);
1026     RETURN_IF_EXCEPTION(scope, encodedJSValue());
1027
1028     unsigned index = argumentClampedIndexFromStartOrEnd(exec, 1, length);
1029     JSValue searchElement = exec->argument(0);
1030     for (; index < length; ++index) {
1031         JSValue e = getProperty(exec, thisObj, index);
1032         RETURN_IF_EXCEPTION(scope, encodedJSValue());
1033         if (!e)
1034             continue;
1035         if (JSValue::strictEqual(exec, searchElement, e))
1036             return JSValue::encode(jsNumber(index));
1037         RETURN_IF_EXCEPTION(scope, encodedJSValue());
1038     }
1039
1040     return JSValue::encode(jsNumber(-1));
1041 }
1042
1043 EncodedJSValue JSC_HOST_CALL arrayProtoFuncLastIndexOf(ExecState* exec)
1044 {
1045     VM& vm = exec->vm();
1046     auto scope = DECLARE_THROW_SCOPE(vm);
1047
1048     // 15.4.4.15
1049     JSObject* thisObj = exec->thisValue().toThis(exec, StrictMode).toObject(exec);
1050     if (!thisObj)
1051         return JSValue::encode(JSValue());
1052     unsigned length = getLength(exec, thisObj);
1053     if (!length)
1054         return JSValue::encode(jsNumber(-1));
1055
1056     unsigned index = length - 1;
1057     if (exec->argumentCount() >= 2) {
1058         JSValue fromValue = exec->uncheckedArgument(1);
1059         double fromDouble = fromValue.toInteger(exec);
1060         if (fromDouble < 0) {
1061             fromDouble += length;
1062             if (fromDouble < 0)
1063                 return JSValue::encode(jsNumber(-1));
1064         }
1065         if (fromDouble < length)
1066             index = static_cast<unsigned>(fromDouble);
1067     }
1068
1069     JSValue searchElement = exec->argument(0);
1070     do {
1071         RELEASE_ASSERT(index < length);
1072         JSValue e = getProperty(exec, thisObj, index);
1073         RETURN_IF_EXCEPTION(scope, encodedJSValue());
1074         if (!e)
1075             continue;
1076         if (JSValue::strictEqual(exec, searchElement, e))
1077             return JSValue::encode(jsNumber(index));
1078         RETURN_IF_EXCEPTION(scope, encodedJSValue());
1079     } while (index--);
1080
1081     return JSValue::encode(jsNumber(-1));
1082 }
1083
1084 static bool moveElements(ExecState* exec, VM& vm, JSArray* target, unsigned targetOffset, JSArray* source, unsigned sourceLength)
1085 {
1086     auto scope = DECLARE_THROW_SCOPE(vm);
1087
1088     if (LIKELY(!hasAnyArrayStorage(source->indexingType()) && !source->structure()->holesMustForwardToPrototype(vm))) {
1089         for (unsigned i = 0; i < sourceLength; ++i) {
1090             JSValue value = source->tryGetIndexQuickly(i);
1091             if (value) {
1092                 target->putDirectIndex(exec, targetOffset + i, value, 0, PutDirectIndexShouldThrow);
1093                 RETURN_IF_EXCEPTION(scope, false);
1094             }
1095         }
1096     } else {
1097         for (unsigned i = 0; i < sourceLength; ++i) {
1098             JSValue value = getProperty(exec, source, i);
1099             RETURN_IF_EXCEPTION(scope, false);
1100             if (value) {
1101                 target->putDirectIndex(exec, targetOffset + i, value, 0, PutDirectIndexShouldThrow);
1102                 RETURN_IF_EXCEPTION(scope, false);
1103             }
1104         }
1105     }
1106     return true;
1107 }
1108
1109 static EncodedJSValue concatAppendOne(ExecState* exec, VM& vm, JSArray* first, JSValue second)
1110 {
1111     auto scope = DECLARE_THROW_SCOPE(vm);
1112
1113     ASSERT(!isJSArray(second));
1114     ASSERT(!shouldUseSlowPut(first->indexingType()));
1115     Butterfly* firstButterfly = first->butterfly();
1116     unsigned firstArraySize = firstButterfly->publicLength();
1117
1118     IndexingType type = first->mergeIndexingTypeForCopying(indexingTypeForValue(second) | IsArray);
1119
1120     if (type == NonArray)
1121         type = first->indexingType();
1122
1123     Structure* resultStructure = exec->lexicalGlobalObject()->arrayStructureForIndexingTypeDuringAllocation(type);
1124     JSArray* result = JSArray::create(vm, resultStructure, firstArraySize + 1);
1125     if (!result)
1126         return JSValue::encode(throwOutOfMemoryError(exec, scope));
1127
1128     if (!result->appendMemcpy(exec, vm, 0, first)) {
1129         if (!moveElements(exec, vm, result, 0, first, firstArraySize)) {
1130             ASSERT(scope.exception());
1131             return JSValue::encode(JSValue());
1132         }
1133     }
1134
1135     result->putDirectIndex(exec, firstArraySize, second);
1136     return JSValue::encode(result);
1137
1138 }
1139
1140
1141 EncodedJSValue JSC_HOST_CALL arrayProtoPrivateFuncConcatMemcpy(ExecState* exec)
1142 {
1143     ASSERT(exec->argumentCount() == 2);
1144     VM& vm = exec->vm();
1145     auto scope = DECLARE_THROW_SCOPE(vm);
1146
1147     JSArray* firstArray = jsCast<JSArray*>(exec->uncheckedArgument(0));
1148
1149     // This code assumes that neither array has set Symbol.isConcatSpreadable. If the first array
1150     // has indexed accessors then one of those accessors might change the value of Symbol.isConcatSpreadable
1151     // on the second argument.
1152     if (UNLIKELY(shouldUseSlowPut(firstArray->indexingType())))
1153         return JSValue::encode(jsNull());
1154
1155     // We need to check the species constructor here since checking it in the JS wrapper is too expensive for the non-optimizing tiers.
1156     if (UNLIKELY(!speciesWatchpointsValid(exec, firstArray)))
1157         return JSValue::encode(jsNull());
1158
1159     JSValue second = exec->uncheckedArgument(1);
1160     if (!isJSArray(second))
1161         return concatAppendOne(exec, vm, firstArray, second);
1162
1163     JSArray* secondArray = jsCast<JSArray*>(second);
1164
1165     Butterfly* firstButterfly = firstArray->butterfly();
1166     Butterfly* secondButterfly = secondArray->butterfly();
1167
1168     unsigned firstArraySize = firstButterfly->publicLength();
1169     unsigned secondArraySize = secondButterfly->publicLength();
1170
1171     IndexingType secondType = secondArray->indexingType();
1172     IndexingType type = firstArray->mergeIndexingTypeForCopying(secondType);
1173     if (type == NonArray || !firstArray->canFastCopy(vm, secondArray) || firstArraySize + secondArraySize >= MIN_SPARSE_ARRAY_INDEX) {
1174         JSArray* result = constructEmptyArray(exec, nullptr, firstArraySize + secondArraySize);
1175         RETURN_IF_EXCEPTION(scope, encodedJSValue());
1176
1177         if (!moveElements(exec, vm, result, 0, firstArray, firstArraySize)
1178             || !moveElements(exec, vm, result, firstArraySize, secondArray, secondArraySize)) {
1179             ASSERT(scope.exception());
1180             return JSValue::encode(JSValue());
1181         }
1182
1183         return JSValue::encode(result);
1184     }
1185
1186     Structure* resultStructure = exec->lexicalGlobalObject()->arrayStructureForIndexingTypeDuringAllocation(type);
1187     JSArray* result = JSArray::tryCreateUninitialized(vm, resultStructure, firstArraySize + secondArraySize);
1188     if (!result)
1189         return JSValue::encode(throwOutOfMemoryError(exec, scope));
1190
1191     if (type == ArrayWithDouble) {
1192         double* buffer = result->butterfly()->contiguousDouble().data();
1193         memcpy(buffer, firstButterfly->contiguousDouble().data(), sizeof(JSValue) * firstArraySize);
1194         memcpy(buffer + firstArraySize, secondButterfly->contiguousDouble().data(), sizeof(JSValue) * secondArraySize);
1195     } else if (type != ArrayWithUndecided) {
1196         WriteBarrier<Unknown>* buffer = result->butterfly()->contiguous().data();
1197         memcpy(buffer, firstButterfly->contiguous().data(), sizeof(JSValue) * firstArraySize);
1198         if (secondType != ArrayWithUndecided)
1199             memcpy(buffer + firstArraySize, secondButterfly->contiguous().data(), sizeof(JSValue) * secondArraySize);
1200         else {
1201             for (unsigned i = secondArraySize; i--;)
1202                 buffer[i + firstArraySize].clear();
1203         }
1204     }
1205
1206     result->butterfly()->setPublicLength(firstArraySize + secondArraySize);
1207     return JSValue::encode(result);
1208 }
1209
1210 EncodedJSValue JSC_HOST_CALL arrayProtoPrivateFuncAppendMemcpy(ExecState* exec)
1211 {
1212     ASSERT(exec->argumentCount() == 3);
1213
1214     VM& vm = exec->vm();
1215     JSArray* resultArray = jsCast<JSArray*>(exec->uncheckedArgument(0));
1216     JSArray* otherArray = jsCast<JSArray*>(exec->uncheckedArgument(1));
1217     JSValue startValue = exec->uncheckedArgument(2);
1218     ASSERT(startValue.isAnyInt() && startValue.asAnyInt() >= 0 && startValue.asAnyInt() <= std::numeric_limits<unsigned>::max());
1219     unsigned startIndex = static_cast<unsigned>(startValue.asAnyInt());
1220     if (!resultArray->appendMemcpy(exec, vm, startIndex, otherArray))
1221         moveElements(exec, vm, resultArray, startIndex, otherArray, otherArray->length());
1222
1223     return JSValue::encode(jsUndefined());
1224 }
1225
1226
1227 // -------------------- ArrayPrototype.constructor Watchpoint ------------------
1228
1229 static bool verbose = false;
1230
1231 class ArrayPrototypeAdaptiveInferredPropertyWatchpoint : public AdaptiveInferredPropertyValueWatchpointBase {
1232 public:
1233     typedef AdaptiveInferredPropertyValueWatchpointBase Base;
1234     ArrayPrototypeAdaptiveInferredPropertyWatchpoint(const ObjectPropertyCondition&, ArrayPrototype*);
1235
1236 private:
1237     void handleFire(const FireDetail&) override;
1238
1239     ArrayPrototype* m_arrayPrototype;
1240 };
1241
1242 ArrayPrototype::SpeciesWatchpointStatus ArrayPrototype::attemptToInitializeSpeciesWatchpoint(ExecState* exec)
1243 {
1244     ASSERT(m_speciesWatchpointStatus == SpeciesWatchpointStatus::Uninitialized);
1245
1246     VM& vm = exec->vm();
1247
1248     if (verbose)
1249         dataLog("Attempting to initialize Array species watchpoints for Array.prototype: ", pointerDump(this), " with structure: ", pointerDump(this->structure()), "\nand Array: ", pointerDump(this->globalObject()->arrayConstructor()), " with structure: ", pointerDump(this->globalObject()->arrayConstructor()->structure()), "\n");
1250     // First we need to make sure that the Array.prototype.constructor property points to Array
1251     // and that Array[Symbol.species] is the primordial GetterSetter.
1252
1253     // We only initialize once so flattening the structures does not have any real cost.
1254     Structure* prototypeStructure = this->structure(vm);
1255     if (prototypeStructure->isDictionary())
1256         prototypeStructure = prototypeStructure->flattenDictionaryStructure(vm, this);
1257     RELEASE_ASSERT(!prototypeStructure->isDictionary());
1258
1259     JSGlobalObject* globalObject = this->globalObject();
1260     ArrayConstructor* arrayConstructor = globalObject->arrayConstructor();
1261
1262     PropertySlot constructorSlot(this, PropertySlot::InternalMethodType::VMInquiry);
1263     JSValue(this).get(exec, vm.propertyNames->constructor, constructorSlot);
1264     if (constructorSlot.slotBase() != this
1265         || !constructorSlot.isCacheableValue()
1266         || constructorSlot.getValue(exec, vm.propertyNames->constructor) != arrayConstructor)
1267         return m_speciesWatchpointStatus = SpeciesWatchpointStatus::Fired;
1268
1269     Structure* constructorStructure = arrayConstructor->structure(vm);
1270     if (constructorStructure->isDictionary())
1271         constructorStructure = constructorStructure->flattenDictionaryStructure(vm, arrayConstructor);
1272
1273     PropertySlot speciesSlot(arrayConstructor, PropertySlot::InternalMethodType::VMInquiry);
1274     JSValue(arrayConstructor).get(exec, vm.propertyNames->speciesSymbol, speciesSlot);
1275     if (speciesSlot.slotBase() != arrayConstructor
1276         || !speciesSlot.isCacheableGetter()
1277         || speciesSlot.getterSetter() != globalObject->speciesGetterSetter())
1278         return m_speciesWatchpointStatus = SpeciesWatchpointStatus::Fired;
1279
1280     // Now we need to setup the watchpoints to make sure these conditions remain valid.
1281     prototypeStructure->startWatchingPropertyForReplacements(vm, constructorSlot.cachedOffset());
1282     constructorStructure->startWatchingPropertyForReplacements(vm, speciesSlot.cachedOffset());
1283
1284     ObjectPropertyCondition constructorCondition = ObjectPropertyCondition::equivalence(vm, this, this, vm.propertyNames->constructor.impl(), arrayConstructor);
1285     ObjectPropertyCondition speciesCondition = ObjectPropertyCondition::equivalence(vm, this, arrayConstructor, vm.propertyNames->speciesSymbol.impl(), globalObject->speciesGetterSetter());
1286
1287     if (!constructorCondition.isWatchable() || !speciesCondition.isWatchable())
1288         return m_speciesWatchpointStatus = SpeciesWatchpointStatus::Fired;
1289
1290     m_constructorWatchpoint = std::make_unique<ArrayPrototypeAdaptiveInferredPropertyWatchpoint>(constructorCondition, this);
1291     m_constructorWatchpoint->install();
1292
1293     m_constructorSpeciesWatchpoint = std::make_unique<ArrayPrototypeAdaptiveInferredPropertyWatchpoint>(speciesCondition, this);
1294     m_constructorSpeciesWatchpoint->install();
1295
1296     return m_speciesWatchpointStatus = SpeciesWatchpointStatus::Initialized;
1297 }
1298
1299 ArrayPrototypeAdaptiveInferredPropertyWatchpoint::ArrayPrototypeAdaptiveInferredPropertyWatchpoint(const ObjectPropertyCondition& key, ArrayPrototype* prototype)
1300     : Base(key)
1301     , m_arrayPrototype(prototype)
1302 {
1303 }
1304
1305 void ArrayPrototypeAdaptiveInferredPropertyWatchpoint::handleFire(const FireDetail& detail)
1306 {
1307     StringPrintStream out;
1308     out.print("ArrayPrototype adaption of ", key(), " failed: ", detail);
1309
1310     StringFireDetail stringDetail(out.toCString().data());
1311
1312     if (verbose)
1313         WTF::dataLog(stringDetail, "\n");
1314
1315     m_arrayPrototype->m_speciesWatchpointStatus = ArrayPrototype::SpeciesWatchpointStatus::Fired;
1316 }
1317
1318 } // namespace JSC