Quelle  Array.cpp   Sprache: C

/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
 * vim: set ts=8 sts=2 et sw=2 tw=80:
 * This Source Code Form is subject to the terms of the Mozilla Public
 * License, v. 2.0. If a copy of the MPL was not distributed with this
 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#include "builtin/Array-inl.h"

#include "mozilla/CheckedInt.h"
#include "mozilla/DebugOnly.h"
#include "mozilla/MathAlgorithms.h"
#include "mozilla/Maybe.h"
#include "mozilla/ScopeExit.h"
#include "mozilla/SIMD.h"
#include "mozilla/TextUtils.h"

#include <algorithm>
#include <cmath>
#include <iterator>

#include "jsfriendapi.h"
#include "jsnum.h"
#include "jstypes.h"

#include "builtin/SelfHostingDefines.h"
#include "ds/Sort.h"
#include "jit/InlinableNatives.h"
#include "jit/TrampolineNatives.h"
#include "js/Class.h"
#include "js/Conversions.h"
#include "js/experimental/JitInfo.h"  // JSJitGetterOp, JSJitInfo
#include "js/friend/ErrorMessages.h"  // js::GetErrorMessage, JSMSG_*
#include "js/PropertySpec.h"
#include "util/Poison.h"
#include "util/StringBuilder.h"
#include "util/Text.h"
#include "vm/ArgumentsObject.h"
#include "vm/EqualityOperations.h"
#include "vm/Interpreter.h"
#include "vm/Iteration.h"
#include "vm/JSContext.h"
#include "vm/JSFunction.h"
#include "vm/JSObject.h"
#include "vm/PlainObject.h"  // js::PlainObject
#include "vm/SelfHosting.h"
#include "vm/Shape.h"
#include "vm/StringType.h"
#include "vm/ToSource.h"  // js::ValueToSource
#include "vm/TypedArrayObject.h"
#include "vm/WrapperObject.h"
#ifdef ENABLE_RECORD_TUPLE
#  include "vm/TupleType.h"
#endif

#include "builtin/Sorting-inl.h"
#include "vm/ArgumentsObject-inl.h"
#include "vm/ArrayObject-inl.h"
#include "vm/GeckoProfiler-inl.h"
#include "vm/IsGivenTypeObject-inl.h"
#include "vm/JSAtomUtils-inl.h"  // PrimitiveValueToId, IndexToId
#include "vm/NativeObject-inl.h"

using namespace js;

using mozilla::Abs;
using mozilla::CeilingLog2;
using mozilla::CheckedInt;
using mozilla::DebugOnly;
using mozilla::Maybe;
using mozilla::SIMD;

using JS::AutoCheckCannotGC;
using JS::IsArrayAnswer;
using JS::ToUint32;

bool js::ObjectMayHaveExtraIndexedOwnProperties(JSObject* obj) {
  if (!obj->is<NativeObject>()) {
    return true;
  }

  if (obj->as<NativeObject>().isIndexed()) {
    return true;
  }

  if (obj->is<TypedArrayObject>()) {
    return true;
  }

  return ClassMayResolveId(*obj->runtimeFromAnyThread()->commonNames,
                           obj->getClass(), PropertyKey::Int(0), obj);
}

bool js::PrototypeMayHaveIndexedProperties(NativeObject* obj) {
  do {
    MOZ_ASSERT(obj->hasStaticPrototype(),
               "dynamic-prototype objects must be non-native");

    JSObject* proto = obj->staticPrototype();
    if (!proto) {
      return false;  // no extra indexed properties found
    }

    if (ObjectMayHaveExtraIndexedOwnProperties(proto)) {
      return true;
    }
    obj = &proto->as<NativeObject>();
    if (obj->getDenseInitializedLength() != 0) {
      return true;
    }
  } while (true);
}

/*
 * Whether obj may have indexed properties anywhere besides its dense
 * elements. This includes other indexed properties in its shape hierarchy, and
 * indexed properties or elements along its prototype chain.
 */
bool js::ObjectMayHaveExtraIndexedProperties(JSObject* obj) {
  MOZ_ASSERT_IF(obj->hasDynamicPrototype(), !obj->is<NativeObject>());

  if (ObjectMayHaveExtraIndexedOwnProperties(obj)) {
    return true;
  }

  return PrototypeMayHaveIndexedProperties(&obj->as<NativeObject>());
}

bool JS::IsArray(JSContext* cx, HandleObject obj, IsArrayAnswer* answer) {
  if (obj->is<ArrayObject>()) {
    *answer = IsArrayAnswer::Array;
    return true;
  }

  if (obj->is<ProxyObject>()) {
    return Proxy::isArray(cx, obj, answer);
  }

  *answer = IsArrayAnswer::NotArray;
  return true;
}

bool JS::IsArray(JSContext* cx, HandleObject obj, bool* isArray) {
  IsArrayAnswer answer;
  if (!IsArray(cx, obj, &answer)) {
    return false;
  }

  if (answer == IsArrayAnswer::RevokedProxy) {
    JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
                              JSMSG_PROXY_REVOKED);
    return false;
  }

  *isArray = answer == IsArrayAnswer::Array;
  return true;
}

bool js::IsArrayFromJit(JSContext* cx, HandleObject obj, bool* isArray) {
  return JS::IsArray(cx, obj, isArray);
}

// ES2017 7.1.15 ToLength.
bool js::ToLength(JSContext* cx, HandleValue v, uint64_t* out) {
  if (v.isInt32()) {
    int32_t i = v.toInt32();
    *out = i < 0 ? 0 : i;
    return true;
  }

  double d;
  if (v.isDouble()) {
    d = v.toDouble();
  } else {
    if (!ToNumber(cx, v, &d)) {
      return false;
    }
  }

  d = JS::ToInteger(d);
  if (d <= 0.0) {
    *out = 0;
  } else {
    *out = uint64_t(std::min(d, DOUBLE_INTEGRAL_PRECISION_LIMIT - 1));
  }
  return true;
}

bool js::GetLengthProperty(JSContext* cx, HandleObject obj, uint64_t* lengthp) {
  if (obj->is<ArrayObject>()) {
    *lengthp = obj->as<ArrayObject>().length();
    return true;
  }

  if (obj->is<ArgumentsObject>()) {
    ArgumentsObject& argsobj = obj->as<ArgumentsObject>();
    if (!argsobj.hasOverriddenLength()) {
      *lengthp = argsobj.initialLength();
      return true;
    }
  }

  RootedValue value(cx);
  if (!GetProperty(cx, obj, obj, cx->names().length, &value)) {
    return false;
  }

  return ToLength(cx, value, lengthp);
}

// Fast path for array functions where the object is expected to be an array.
static MOZ_ALWAYS_INLINE bool GetLengthPropertyInlined(JSContext* cx,
                                                       HandleObject obj,
                                                       uint64_t* lengthp) {
  if (obj->is<ArrayObject>()) {
    *lengthp = obj->as<ArrayObject>().length();
    return true;
  }

  return GetLengthProperty(cx, obj, lengthp);
}

/*
 * Determine if the id represents an array index.
 *
 * An id is an array index according to ECMA by (15.4):
 *
 * "Array objects give special treatment to a certain class of property names.
 * A property name P (in the form of a string value) is an array index if and
 * only if ToString(ToUint32(P)) is equal to P and ToUint32(P) is not equal
 * to 2^32-1."
 *
 * This means the largest allowed index is actually 2^32-2 (4294967294).
 *
 * In our implementation, it would be sufficient to check for id.isInt32()
 * except that by using signed 31-bit integers we miss the top half of the
 * valid range. This function checks the string representation itself; note
 * that calling a standard conversion routine might allow strings such as
 * "08" or "4.0" as array indices, which they are not.
 *
 */
JS_PUBLIC_API bool js::StringIsArrayIndex(const JSLinearString* str,
                                          uint32_t* indexp) {
  if (!str->isIndex(indexp)) {
    return false;
  }
  MOZ_ASSERT(*indexp <= MAX_ARRAY_INDEX);
  return true;
}

JS_PUBLIC_API bool js::StringIsArrayIndex(const char16_t* str, uint32_t length,
                                          uint32_t* indexp) {
  if (length == 0 || length > UINT32_CHAR_BUFFER_LENGTH) {
    return false;
  }
  if (!mozilla::IsAsciiDigit(str[0])) {
    return false;
  }
  if (!CheckStringIsIndex(str, length, indexp)) {
    return false;
  }
  MOZ_ASSERT(*indexp <= MAX_ARRAY_INDEX);
  return true;
}

template <typename T>
static bool ToId(JSContext* cx, T index, MutableHandleId id);

template <>
bool ToId(JSContext* cx, uint32_t index, MutableHandleId id) {
  return IndexToId(cx, index, id);
}

template <>
bool ToId(JSContext* cx, uint64_t index, MutableHandleId id) {
  MOZ_ASSERT(index < uint64_t(DOUBLE_INTEGRAL_PRECISION_LIMIT));

  if (index == uint32_t(index)) {
    return IndexToId(cx, uint32_t(index), id);
  }

  Value tmp = DoubleValue(index);
  return PrimitiveValueToId<CanGC>(cx, HandleValue::fromMarkedLocation(&tmp),
                                   id);
}

/*
 * If the property at the given index exists, get its value into |vp| and set
 * |*hole| to false. Otherwise set |*hole| to true and |vp| to Undefined.
 */
template <typename T>
static bool HasAndGetElement(JSContext* cx, HandleObject obj,
                             HandleObject receiver, T index, bool* hole,
                             MutableHandleValue vp) {
  if (obj->is<NativeObject>()) {
    NativeObject* nobj = &obj->as<NativeObject>();
    if (index < nobj->getDenseInitializedLength()) {
      vp.set(nobj->getDenseElement(size_t(index)));
      if (!vp.isMagic(JS_ELEMENTS_HOLE)) {
        *hole = false;
        return true;
      }
    }
    if (nobj->is<ArgumentsObject>() && index <= UINT32_MAX) {
      if (nobj->as<ArgumentsObject>().maybeGetElement(uint32_t(index), vp)) {
        *hole = false;
        return true;
      }
    }
  }

  RootedId id(cx);
  if (!ToId(cx, index, &id)) {
    return false;
  }

  bool found;
  if (!HasProperty(cx, obj, id, &found)) {
    return false;
  }

  if (found) {
    if (!GetProperty(cx, obj, receiver, id, vp)) {
      return false;
    }
  } else {
    vp.setUndefined();
  }
  *hole = !found;
  return true;
}

template <typename T>
static inline bool HasAndGetElement(JSContext* cx, HandleObject obj, T index,
                                    bool* hole, MutableHandleValue vp) {
  return HasAndGetElement(cx, obj, obj, index, hole, vp);
}

bool ElementAdder::append(JSContext* cx, HandleValue v) {
  MOZ_ASSERT(index_ < length_);
  if (resObj_) {
    NativeObject* resObj = &resObj_->as<NativeObject>();
    DenseElementResult result =
        resObj->setOrExtendDenseElements(cx, index_, v.address(), 1);
    if (result == DenseElementResult::Failure) {
      return false;
    }
    if (result == DenseElementResult::Incomplete) {
      if (!DefineDataElement(cx, resObj_, index_, v)) {
        return false;
      }
    }
  } else {
    vp_[index_] = v;
  }
  index_++;
  return true;
}

void ElementAdder::appendHole() {
  MOZ_ASSERT(getBehavior_ == ElementAdder::CheckHasElemPreserveHoles);
  MOZ_ASSERT(index_ < length_);
  if (!resObj_) {
    vp_[index_].setMagic(JS_ELEMENTS_HOLE);
  }
  index_++;
}

bool js::GetElementsWithAdder(JSContext* cx, HandleObject obj,
                              HandleObject receiver, uint32_t begin,
                              uint32_t end, ElementAdder* adder) {
  MOZ_ASSERT(begin <= end);

  RootedValue val(cx);
  for (uint32_t i = begin; i < end; i++) {
    if (adder->getBehavior() == ElementAdder::CheckHasElemPreserveHoles) {
      bool hole;
      if (!HasAndGetElement(cx, obj, receiver, i, &hole, &val)) {
        return false;
      }
      if (hole) {
        adder->appendHole();
        continue;
      }
    } else {
      MOZ_ASSERT(adder->getBehavior() == ElementAdder::GetElement);
      if (!GetElement(cx, obj, receiver, i, &val)) {
        return false;
      }
    }
    if (!adder->append(cx, val)) {
      return false;
    }
  }

  return true;
}

static inline bool IsPackedArrayOrNoExtraIndexedProperties(JSObject* obj,
                                                           uint64_t length) {
  return (IsPackedArray(obj) && obj->as<ArrayObject>().length() == length) ||
         !ObjectMayHaveExtraIndexedProperties(obj);
}

static bool GetDenseElements(NativeObject* aobj, uint32_t length, Value* vp) {
  MOZ_ASSERT(IsPackedArrayOrNoExtraIndexedProperties(aobj, length));

  if (length > aobj->getDenseInitializedLength()) {
    return false;
  }

  for (size_t i = 0; i < length; i++) {
    vp[i] = aobj->getDenseElement(i);

    // No other indexed properties so hole => undefined.
    if (vp[i].isMagic(JS_ELEMENTS_HOLE)) {
      vp[i] = UndefinedValue();
    }
  }

  return true;
}

bool js::GetElements(JSContext* cx, HandleObject aobj, uint32_t length,
                     Value* vp) {
  if (IsPackedArrayOrNoExtraIndexedProperties(aobj, length)) {
    if (GetDenseElements(&aobj->as<NativeObject>(), length, vp)) {
      return true;
    }
  }

  if (aobj->is<ArgumentsObject>()) {
    ArgumentsObject& argsobj = aobj->as<ArgumentsObject>();
    if (!argsobj.hasOverriddenLength()) {
      if (argsobj.maybeGetElements(0, length, vp)) {
        return true;
      }
    }
  }

  if (aobj->is<TypedArrayObject>()) {
    Handle<TypedArrayObject*> typedArray = aobj.as<TypedArrayObject>();
    if (typedArray->length().valueOr(0) == length) {
      return TypedArrayObject::getElements(cx, typedArray, length, vp);
    }
  }

  if (js::GetElementsOp op = aobj->getOpsGetElements()) {
    ElementAdder adder(cx, vp, length, ElementAdder::GetElement);
    return op(cx, aobj, 0, length, &adder);
  }

  for (uint32_t i = 0; i < length; i++) {
    if (!GetElement(cx, aobj, aobj, i,
                    MutableHandleValue::fromMarkedLocation(&vp[i]))) {
      return false;
    }
  }

  return true;
}

static inline bool GetArrayElement(JSContext* cx, HandleObject obj,
                                   uint64_t index, MutableHandleValue vp) {
  if (obj->is<NativeObject>()) {
    NativeObject* nobj = &obj->as<NativeObject>();
    if (index < nobj->getDenseInitializedLength()) {
      vp.set(nobj->getDenseElement(size_t(index)));
      if (!vp.isMagic(JS_ELEMENTS_HOLE)) {
        return true;
      }
    }

    if (nobj->is<ArgumentsObject>() && index <= UINT32_MAX) {
      if (nobj->as<ArgumentsObject>().maybeGetElement(uint32_t(index), vp)) {
        return true;
      }
    }
  }

  RootedId id(cx);
  if (!ToId(cx, index, &id)) {
    return false;
  }
  return GetProperty(cx, obj, obj, id, vp);
}

static inline bool DefineArrayElement(JSContext* cx, HandleObject obj,
                                      uint64_t index, HandleValue value) {
  RootedId id(cx);
  if (!ToId(cx, index, &id)) {
    return false;
  }
  return DefineDataProperty(cx, obj, id, value);
}

// Set the value of the property at the given index to v.
static inline bool SetArrayElement(JSContext* cx, HandleObject obj,
                                   uint64_t index, HandleValue v) {
  RootedId id(cx);
  if (!ToId(cx, index, &id)) {
    return false;
  }

  return SetProperty(cx, obj, id, v);
}

/*
 * Attempt to delete the element |index| from |obj| as if by
 * |obj.[[Delete]](index)|.
 *
 * If an error occurs while attempting to delete the element (that is, the call
 * to [[Delete]] threw), return false.
 *
 * Otherwise call result.succeed() or result.fail() to indicate whether the
 * deletion attempt succeeded (that is, whether the call to [[Delete]] returned
 * true or false).  (Deletes generally fail only when the property is
 * non-configurable, but proxies may implement different semantics.)
 */
static bool DeleteArrayElement(JSContext* cx, HandleObject obj, uint64_t index,
                               ObjectOpResult& result) {
  if (obj->is<ArrayObject>() && !obj->as<NativeObject>().isIndexed() &&
      !obj->as<NativeObject>().denseElementsAreSealed()) {
    ArrayObject* aobj = &obj->as<ArrayObject>();
    if (index <= UINT32_MAX) {
      uint32_t idx = uint32_t(index);
      if (idx < aobj->getDenseInitializedLength()) {
        if (idx + 1 == aobj->getDenseInitializedLength()) {
          aobj->setDenseInitializedLengthMaybeNonExtensible(cx, idx);
        } else {
          aobj->setDenseElementHole(idx);
        }
        if (!SuppressDeletedElement(cx, obj, idx)) {
          return false;
        }
      }
    }

    return result.succeed();
  }

  RootedId id(cx);
  if (!ToId(cx, index, &id)) {
    return false;
  }
  return DeleteProperty(cx, obj, id, result);
}

/* ES6 draft rev 32 (2 Febr 2015) 7.3.7 */
static bool DeletePropertyOrThrow(JSContext* cx, HandleObject obj,
                                  uint64_t index) {
  ObjectOpResult success;
  if (!DeleteArrayElement(cx, obj, index, success)) {
    return false;
  }
  if (!success) {
    RootedId id(cx);
    if (!ToId(cx, index, &id)) {
      return false;
    }
    return success.reportError(cx, obj, id);
  }
  return true;
}

static bool DeletePropertiesOrThrow(JSContext* cx, HandleObject obj,
                                    uint64_t len, uint64_t finalLength) {
  if (obj->is<ArrayObject>() && !obj->as<NativeObject>().isIndexed() &&
      !obj->as<NativeObject>().denseElementsAreSealed()) {
    if (len <= UINT32_MAX) {
      // Skip forward to the initialized elements of this array.
      len = std::min(uint32_t(len),
                     obj->as<ArrayObject>().getDenseInitializedLength());
    }
  }

  for (uint64_t k = len; k > finalLength; k--) {
    if (!CheckForInterrupt(cx)) {
      return false;
    }

    if (!DeletePropertyOrThrow(cx, obj, k - 1)) {
      return false;
    }
  }
  return true;
}

static bool SetArrayLengthProperty(JSContext* cx, Handle<ArrayObject*> obj,
                                   HandleValue value) {
  RootedId id(cx, NameToId(cx->names().length));
  ObjectOpResult result;
  if (obj->lengthIsWritable()) {
    Rooted<PropertyDescriptor> desc(
        cx, PropertyDescriptor::Data(value, JS::PropertyAttribute::Writable));
    if (!ArraySetLength(cx, obj, id, desc, result)) {
      return false;
    }
  } else {
    MOZ_ALWAYS_TRUE(result.fail(JSMSG_READ_ONLY));
  }
  return result.checkStrict(cx, obj, id);
}

static bool SetLengthProperty(JSContext* cx, HandleObject obj,
                              uint64_t length) {
  MOZ_ASSERT(length < uint64_t(DOUBLE_INTEGRAL_PRECISION_LIMIT));

  RootedValue v(cx, NumberValue(length));
  if (obj->is<ArrayObject>()) {
    return SetArrayLengthProperty(cx, obj.as<ArrayObject>(), v);
  }
  return SetProperty(cx, obj, cx->names().length, v);
}

bool js::SetLengthProperty(JSContext* cx, HandleObject obj, uint32_t length) {
  RootedValue v(cx, NumberValue(length));
  if (obj->is<ArrayObject>()) {
    return SetArrayLengthProperty(cx, obj.as<ArrayObject>(), v);
  }
  return SetProperty(cx, obj, cx->names().length, v);
}

bool js::ArrayLengthGetter(JSContext* cx, HandleObject obj, HandleId id,
                           MutableHandleValue vp) {
  MOZ_ASSERT(id == NameToId(cx->names().length));

  vp.setNumber(obj->as<ArrayObject>().length());
  return true;
}

bool js::ArrayLengthSetter(JSContext* cx, HandleObject obj, HandleId id,
                           HandleValue v, ObjectOpResult& result) {
  MOZ_ASSERT(id == NameToId(cx->names().length));

  Handle<ArrayObject*> arr = obj.as<ArrayObject>();
  MOZ_ASSERT(arr->lengthIsWritable(),
             "setter shouldn't be called if property is non-writable");

  Rooted<PropertyDescriptor> desc(
      cx, PropertyDescriptor::Data(v, JS::PropertyAttribute::Writable));
  return ArraySetLength(cx, arr, id, desc, result);
}

struct ReverseIndexComparator {
  bool operator()(const uint32_t& a, const uint32_t& b, bool* lessOrEqualp) {
    MOZ_ASSERT(a != b, "how'd we get duplicate indexes?");
    *lessOrEqualp = b <= a;
    return true;
  }
};

// Fast path to remove all elements with index >= newLen when setting the
// .length property of an array to a smaller value.
static bool TryFastDeleteElementsForNewLength(JSContext* cx,
                                              Handle<ArrayObject*> arr,
                                              uint32_t newLen, bool* success) {
  MOZ_ASSERT(newLen < arr->length());

  // If there might be an active for-in iterator for this array we have to use
  // the generic code path because it supports suppressing deleted properties.
  // Keys deleted before being reached during the iteration must not be visited.
  if (arr->denseElementsMaybeInIteration()) {
    *success = false;
    return true;
  }

  // Sealed elements are non-configurable and shouldn't be removed.
  if (arr->denseElementsAreSealed()) {
    *success = false;
    return true;
  }

  if (arr->isIndexed()) {
    // This fast path doesn't suppress deleted properties from active iterators.
    if (arr->compartment()->objectMaybeInIteration(arr)) {
      *success = false;
      return true;
    }

    // First add all sparse indexes we want to remove to a vector and check for
    // non-configurable elements.
    JS::RootedVector<PropertyKey> keys(cx);
    for (ShapePropertyIter<NoGC> iter(arr->shape()); !iter.done(); iter++) {
      uint32_t index;
      if (!IdIsIndex(iter->key(), &index)) {
        continue;
      }
      if (index < newLen) {
        continue;
      }
      // Non-configurable elements shouldn't be removed.
      if (!iter->configurable()) {
        *success = false;
        return true;
      }
      if (!keys.append(iter->key())) {
        return false;
      }
    }

    // Remove the sparse elements. Note that this starts at the most recently
    // added property because this is most efficient when removing many
    // elements.
    //
    // The rest of this function must be infallible (other than OOM).
    for (size_t i = 0, len = keys.length(); i < len; i++) {
      MOZ_ASSERT(arr->containsPure(keys[i]), "must still be a sparse element");
      if (!NativeObject::removeProperty(cx, arr, keys[i])) {
        MOZ_ASSERT(cx->isThrowingOutOfMemory());
        return false;
      }
    }
  }

  // Remove dense elements.
  uint32_t oldCapacity = arr->getDenseCapacity();
  uint32_t oldInitializedLength = arr->getDenseInitializedLength();
  MOZ_ASSERT(oldCapacity >= oldInitializedLength);
  if (oldInitializedLength > newLen) {
    arr->setDenseInitializedLengthMaybeNonExtensible(cx, newLen);
  }
  if (oldCapacity > newLen) {
    if (arr->isExtensible()) {
      arr->shrinkElements(cx, newLen);
    } else {
      MOZ_ASSERT(arr->getDenseInitializedLength() == arr->getDenseCapacity());
    }
  }

  *success = true;
  return true;
}

/* ES6 draft rev 34 (2015 Feb 20) 9.4.2.4 ArraySetLength */
bool js::ArraySetLength(JSContext* cx, Handle<ArrayObject*> arr, HandleId id,
                        Handle<PropertyDescriptor> desc,
                        ObjectOpResult& result) {
  MOZ_ASSERT(id == NameToId(cx->names().length));
  MOZ_ASSERT(desc.isDataDescriptor() || desc.isGenericDescriptor());

  // Step 1.
  uint32_t newLen;
  if (!desc.hasValue()) {
    // The spec has us calling OrdinaryDefineOwnProperty if
    // Desc.[[Value]] is absent, but our implementation is so different that
    // this is impossible. Instead, set newLen to the current length and
    // proceed to step 9.
    newLen = arr->length();
  } else {
    // Step 2 is irrelevant in our implementation.

    // Step 3.
    if (!ToUint32(cx, desc.value(), &newLen)) {
      return false;
    }

    // Step 4.
    double d;
    if (!ToNumber(cx, desc.value(), &d)) {
      return false;
    }

    // Step 5.
    if (d != newLen) {
      JS_ReportErrorNumberASCII(cx, GetErrorMessage, nullptr,
                                JSMSG_BAD_ARRAY_LENGTH);
      return false;
    }

    // Steps 6-8 are irrelevant in our implementation.
  }

  // Steps 9-11.
  bool lengthIsWritable = arr->lengthIsWritable();
#ifdef DEBUG
  {
    mozilla::Maybe<PropertyInfo> lengthProp = arr->lookupPure(id);
    MOZ_ASSERT(lengthProp.isSome());
    MOZ_ASSERT(lengthProp->writable() == lengthIsWritable);
  }
#endif
  uint32_t oldLen = arr->length();

  // Part of steps 1.a, 12.a, and 16: Fail if we're being asked to change
  // enumerability or configurability, or otherwise break the object
  // invariants. (ES6 checks these by calling OrdinaryDefineOwnProperty, but
  // in SM, the array length property is hardly ordinary.)
  if ((desc.hasConfigurable() && desc.configurable()) ||
      (desc.hasEnumerable() && desc.enumerable()) ||
      (!lengthIsWritable && desc.hasWritable() && desc.writable())) {
    return result.fail(JSMSG_CANT_REDEFINE_PROP);
  }

  // Steps 12-13 for arrays with non-writable length.
  if (!lengthIsWritable) {
    if (newLen == oldLen) {
      return result.succeed();
    }

    return result.fail(JSMSG_CANT_REDEFINE_ARRAY_LENGTH);
  }

  // Step 19.
  bool succeeded = true;
  do {
    // The initialized length and capacity of an array only need updating
    // when non-hole elements are added or removed, which doesn't happen
    // when array length stays the same or increases.
    if (newLen >= oldLen) {
      break;
    }

    bool success;
    if (!TryFastDeleteElementsForNewLength(cx, arr, newLen, &success)) {
      return false;
    }

    if (success) {
      // We've done the work of deleting any elements needing deletion.
      // Thus we can skip straight to defining the length.
      break;
    }

    // Step 15.
    //
    // Attempt to delete all elements above the new length, from greatest
    // to least.  If any of these deletions fails, we're supposed to define
    // the length to one greater than the index that couldn't be deleted,
    // *with the property attributes specified*.  This might convert the
    // length to be not the value specified, yet non-writable.  (You may be
    // forgiven for thinking these are interesting semantics.)  Example:
    //
    //   var arr =
    //     Object.defineProperty([0, 1, 2, 3], 1, { writable: false });
    //   Object.defineProperty(arr, "length",
    //                         { value: 0, writable: false });
    //
    // will convert |arr| to an array of non-writable length two, then
    // throw a TypeError.
    //
    // We implement this behavior, in the relevant lops below, by setting
    // |succeeded| to false.  Then we exit the loop, define the length
    // appropriately, and only then throw a TypeError, if necessary.
    uint32_t gap = oldLen - newLen;
    const uint32_t RemoveElementsFastLimit = 1 << 24;
    if (gap < RemoveElementsFastLimit) {
      // If we're removing a relatively small number of elements, just do
      // it exactly by the spec.
      while (newLen < oldLen) {
        // Step 15a.
        oldLen--;

        // Steps 15b-d.
        ObjectOpResult deleteSucceeded;
        if (!DeleteElement(cx, arr, oldLen, deleteSucceeded)) {
          return false;
        }
        if (!deleteSucceeded) {
          newLen = oldLen + 1;
          succeeded = false;
          break;
        }
      }
    } else {
      // If we're removing a large number of elements from an array
      // that's probably sparse, try a different tack.  Get all the own
      // property names, sift out the indexes in the deletion range into
      // a vector, sort the vector greatest to least, then delete the
      // indexes greatest to least using that vector.  See bug 322135.
      //
      // This heuristic's kind of a huge guess -- "large number of
      // elements" and "probably sparse" are completely unprincipled
      // predictions.  In the long run, bug 586842 will support the right
      // fix: store sparse elements in a sorted data structure that
      // permits fast in-reverse-order traversal and concurrent removals.

      Vector<uint32_t> indexes(cx);
      {
        RootedIdVector props(cx);
        if (!GetPropertyKeys(cx, arr, JSITER_OWNONLY | JSITER_HIDDEN, &props)) {
          return false;
        }

        for (size_t i = 0; i < props.length(); i++) {
          if (!CheckForInterrupt(cx)) {
            return false;
          }

          uint32_t index;
          if (!IdIsIndex(props[i], &index)) {
            continue;
          }

          if (index >= newLen && index < oldLen) {
            if (!indexes.append(index)) {
              return false;
            }
          }
        }
      }

      uint32_t count = indexes.length();
      {
        // We should use radix sort to be O(n), but this is uncommon
        // enough that we'll punt til someone complains.
        Vector<uint32_t> scratch(cx);
        if (!scratch.resize(count)) {
          return false;
        }
        MOZ_ALWAYS_TRUE(MergeSort(indexes.begin(), count, scratch.begin(),
                                  ReverseIndexComparator()));
      }

      uint32_t index = UINT32_MAX;
      for (uint32_t i = 0; i < count; i++) {
        MOZ_ASSERT(indexes[i] < index, "indexes should never repeat");
        index = indexes[i];

        // Steps 15b-d.
        ObjectOpResult deleteSucceeded;
        if (!DeleteElement(cx, arr, index, deleteSucceeded)) {
          return false;
        }
        if (!deleteSucceeded) {
          newLen = index + 1;
          succeeded = false;
          break;
        }
      }
    }
  } while (false);

  // Update array length. Technically we should have been doing this
  // throughout the loop, in step 19.d.iii.
  arr->setLength(newLen);

  // Step 20.
  if (desc.hasWritable() && !desc.writable()) {
    Maybe<PropertyInfo> lengthProp = arr->lookup(cx, id);
    MOZ_ASSERT(lengthProp.isSome());
    MOZ_ASSERT(lengthProp->isCustomDataProperty());
    PropertyFlags flags = lengthProp->flags();
    flags.clearFlag(PropertyFlag::Writable);
    if (!NativeObject::changeCustomDataPropAttributes(cx, arr, id, flags)) {
      return false;
    }
  }

  // All operations past here until the |!succeeded| code must be infallible,
  // so that all element fields remain properly synchronized.

  // Trim the initialized length, if needed, to preserve the <= length
  // invariant.  (Capacity was already reduced during element deletion, if
  // necessary.)
  ObjectElements* header = arr->getElementsHeader();
  header->initializedLength = std::min(header->initializedLength, newLen);

  if (!arr->isExtensible()) {
    arr->shrinkCapacityToInitializedLength(cx);
  }

  if (desc.hasWritable() && !desc.writable()) {
    arr->setNonWritableLength(cx);
  }

  if (!succeeded) {
    return result.fail(JSMSG_CANT_TRUNCATE_ARRAY);
  }

  return result.succeed();
}

static bool array_addProperty(JSContext* cx, HandleObject obj, HandleId id,
                              HandleValue v) {
  ArrayObject* arr = &obj->as<ArrayObject>();

  uint32_t index;
  if (!IdIsIndex(id, &index)) {
    return true;
  }

  uint32_t length = arr->length();
  if (index >= length) {
    MOZ_ASSERT(arr->lengthIsWritable(),
               "how'd this element get added if length is non-writable?");
    arr->setLength(index + 1);
  }
  return true;
}

static SharedShape* AddLengthProperty(JSContext* cx,
                                      Handle<SharedShape*> shape) {
  // Add the 'length' property for a newly created array shape.

  MOZ_ASSERT(shape->propMapLength() == 0);
  MOZ_ASSERT(shape->getObjectClass() == &ArrayObject::class_);

  RootedId lengthId(cx, NameToId(cx->names().length));
  constexpr PropertyFlags flags = {PropertyFlag::CustomDataProperty,
                                   PropertyFlag::Writable};

  Rooted<SharedPropMap*> map(cx, shape->propMap());
  uint32_t mapLength = shape->propMapLength();
  ObjectFlags objectFlags = shape->objectFlags();

  if (!SharedPropMap::addCustomDataProperty(cx, &ArrayObject::class_, &map,
                                            &mapLength, lengthId, flags,
                                            &objectFlags)) {
    return nullptr;
  }

  return SharedShape::getPropMapShape(cx, shape->base(), shape->numFixedSlots(),
                                      map, mapLength, objectFlags);
}

bool js::IsArrayConstructor(const JSObject* obj) {
  // Note: this also returns true for cross-realm Array constructors in the
  // same compartment.
  return IsNativeFunction(obj, ArrayConstructor);
}

static bool IsArrayConstructor(const Value& v) {
  return v.isObject() && IsArrayConstructor(&v.toObject());
}

bool js::IsCrossRealmArrayConstructor(JSContext* cx, JSObject* obj,
                                      bool* result) {
  if (obj->is<WrapperObject>()) {
    obj = CheckedUnwrapDynamic(obj, cx);
    if (!obj) {
      ReportAccessDenied(cx);
      return false;
    }
  }

  *result =
      IsArrayConstructor(obj) && obj->as<JSFunction>().realm() != cx->realm();
  return true;
}

// Returns true iff we know for -sure- that it is definitely safe to use the
// realm's array constructor.
//
// This function is conservative as it may return false for cases which
// ultimately do use the array constructor.
static MOZ_ALWAYS_INLINE bool IsArraySpecies(JSContext* cx,
                                             HandleObject origArray) {
  if (MOZ_UNLIKELY(origArray->is<ProxyObject>())) {
    if (origArray->getClass()->isDOMClass()) {
#ifdef DEBUG
      // We assume DOM proxies never return true for IsArray.
      IsArrayAnswer answer;
      MOZ_ASSERT(Proxy::isArray(cx, origArray, &answer));
      MOZ_ASSERT(answer == IsArrayAnswer::NotArray);
#endif
      return true;
    }
    return false;
  }

  // 9.4.2.3 Step 4. Non-array objects always use the default constructor.
  if (!origArray->is<ArrayObject>()) {
    return true;
  }

  if (cx->realm()->arraySpeciesLookup.tryOptimizeArray(
          cx, &origArray->as<ArrayObject>())) {
    return true;
  }

  Value ctor;
  if (!GetPropertyPure(cx, origArray, NameToId(cx->names().constructor),
                       &ctor)) {
    return false;
  }

  if (!IsArrayConstructor(ctor)) {
    return ctor.isUndefined();
  }

  // 9.4.2.3 Step 6.c. Use the current realm's constructor if |ctor| is a
  // cross-realm Array constructor.
  if (cx->realm() != ctor.toObject().as<JSFunction>().realm()) {
    return true;
  }

  jsid speciesId = PropertyKey::Symbol(cx->wellKnownSymbols().species);
  JSFunction* getter;
  if (!GetGetterPure(cx, &ctor.toObject(), speciesId, &getter)) {
    return false;
  }

  if (!getter) {
    return false;
  }

  return IsSelfHostedFunctionWithName(getter, cx->names().dollar_ArraySpecies_);
}

static bool ArraySpeciesCreate(JSContext* cx, HandleObject origArray,
                               uint64_t length, MutableHandleObject arr) {
  MOZ_ASSERT(length < DOUBLE_INTEGRAL_PRECISION_LIMIT);

  FixedInvokeArgs<2> args(cx);

  args[0].setObject(*origArray);
  args[1].set(NumberValue(length));

  RootedValue rval(cx);
  if (!CallSelfHostedFunction(cx, cx->names().ArraySpeciesCreate,
                              UndefinedHandleValue, args, &rval)) {
    return false;
  }

  MOZ_ASSERT(rval.isObject());
  arr.set(&rval.toObject());
  return true;
}

JSString* js::ArrayToSource(JSContext* cx, HandleObject obj) {
  AutoCycleDetector detector(cx, obj);
  if (!detector.init()) {
    return nullptr;
  }

  JSStringBuilder sb(cx);

  if (detector.foundCycle()) {
    if (!sb.append("[]")) {
      return nullptr;
    }
    return sb.finishString();
  }

  if (!sb.append('[')) {
    return nullptr;
  }

  uint64_t length;
  if (!GetLengthPropertyInlined(cx, obj, &length)) {
    return nullptr;
  }

  RootedValue elt(cx);
  for (uint64_t index = 0; index < length; index++) {
    bool hole;
    if (!CheckForInterrupt(cx) ||
        !HasAndGetElement(cx, obj, index, &hole, &elt)) {
      return nullptr;
    }

    /* Get element's character string. */
    JSString* str;
    if (hole) {
      str = cx->runtime()->emptyString;
    } else {
      str = ValueToSource(cx, elt);
      if (!str) {
        return nullptr;
      }
    }

    /* Append element to buffer. */
    if (!sb.append(str)) {
      return nullptr;
    }
    if (index + 1 != length) {
      if (!sb.append(", ")) {
        return nullptr;
      }
    } else if (hole) {
      if (!sb.append(',')) {
        return nullptr;
      }
    }
  }

  /* Finalize the buffer. */
  if (!sb.append(']')) {
    return nullptr;
  }

  return sb.finishString();
}

static bool array_toSource(JSContext* cx, unsigned argc, Value* vp) {
  AutoJSMethodProfilerEntry pseudoFrame(cx, "Array.prototype", "toSource");
  CallArgs args = CallArgsFromVp(argc, vp);

  if (!args.thisv().isObject()) {
    ReportIncompatible(cx, args);
    return false;
  }

  Rooted<JSObject*> obj(cx, &args.thisv().toObject());

  JSString* str = ArrayToSource(cx, obj);
  if (!str) {
    return false;
  }

  args.rval().setString(str);
  return true;
}

template <typename SeparatorOp>
static bool ArrayJoinDenseKernel(JSContext* cx, SeparatorOp sepOp,
                                 Handle<NativeObject*> obj, uint64_t length,
                                 StringBuilder& sb, uint32_t* numProcessed) {
  // This loop handles all elements up to initializedLength. If
  // length > initLength we rely on the second loop to add the
  // other elements.
  MOZ_ASSERT(*numProcessed == 0);
  uint64_t initLength =
      std::min<uint64_t>(obj->getDenseInitializedLength(), length);
  MOZ_ASSERT(initLength <= UINT32_MAX,
             "initialized length shouldn't exceed UINT32_MAX");
  uint32_t initLengthClamped = uint32_t(initLength);
  while (*numProcessed < initLengthClamped) {
    if (!CheckForInterrupt(cx)) {
      return false;
    }

    // Step 7.b.
    Value elem = obj->getDenseElement(*numProcessed);

    // Steps 7.c-d.
    if (elem.isString()) {
      if (!sb.append(elem.toString())) {
        return false;
      }
    } else if (elem.isNumber()) {
      if (!NumberValueToStringBuilder(elem, sb)) {
        return false;
      }
    } else if (elem.isBoolean()) {
      if (!BooleanToStringBuilder(elem.toBoolean(), sb)) {
        return false;
      }
    } else if (elem.isObject() || elem.isSymbol()) {
      /*
       * Object stringifying could modify the initialized length or make
       * the array sparse. Delegate it to a separate loop to keep this
       * one tight.
       *
       * Symbol stringifying is a TypeError, so into the slow path
       * with those as well.
       */
      break;
    } else if (elem.isBigInt()) {
      // ToString(bigint) doesn't access bigint.toString or
      // anything like that, so it can't mutate the array we're
      // walking through, so it *could* be handled here. We don't
      // do so yet for reasons of initial-implementation economy.
      break;
    } else {
      MOZ_ASSERT(elem.isMagic(JS_ELEMENTS_HOLE) || elem.isNullOrUndefined());
    }

    // Steps 7.a, 7.e.
    if (++(*numProcessed) != length && !sepOp(sb)) {
      return false;
    }
  }

  return true;
}

template <typename SeparatorOp>
static bool ArrayJoinKernel(JSContext* cx, SeparatorOp sepOp, HandleObject obj,
                            uint64_t length, StringBuilder& sb) {
  // Step 6.
  uint32_t numProcessed = 0;

  if (IsPackedArrayOrNoExtraIndexedProperties(obj, length)) {
    if (!ArrayJoinDenseKernel<SeparatorOp>(cx, sepOp, obj.as<NativeObject>(),
                                           length, sb, &numProcessed)) {
      return false;
    }
  }

  // Step 7.
  if (numProcessed != length) {
    RootedValue v(cx);
    for (uint64_t i = numProcessed; i < length;) {
      if (!CheckForInterrupt(cx)) {
        return false;
      }

      // Step 7.b.
      if (!GetArrayElement(cx, obj, i, &v)) {
        return false;
      }

      // Steps 7.c-d.
      if (!v.isNullOrUndefined()) {
        if (!ValueToStringBuilder(cx, v, sb)) {
          return false;
        }
      }

      // Steps 7.a, 7.e.
      if (++i != length && !sepOp(sb)) {
        return false;
      }
    }
  }

  return true;
}

// ES2017 draft rev 1b0184bc17fc09a8ddcf4aeec9b6d9fcac4eafce
// 22.1.3.13 Array.prototype.join ( separator )
bool js::array_join(JSContext* cx, unsigned argc, Value* vp) {
  AutoJSMethodProfilerEntry pseudoFrame(cx, "Array.prototype", "join");
  CallArgs args = CallArgsFromVp(argc, vp);

  // Step 1.
  RootedObject obj(cx, ToObject(cx, args.thisv()));
  if (!obj) {
    return false;
  }

  AutoCycleDetector detector(cx, obj);
  if (!detector.init()) {
    return false;
  }

  if (detector.foundCycle()) {
    args.rval().setString(cx->names().empty_);
    return true;
  }

  // Step 2.
  uint64_t length;
  if (!GetLengthPropertyInlined(cx, obj, &length)) {
    return false;
  }

  // Steps 3-4.
  Rooted<JSLinearString*> sepstr(cx);
  if (args.hasDefined(0)) {
    JSString* s = ToString<CanGC>(cx, args[0]);
    if (!s) {
      return false;
    }
    sepstr = s->ensureLinear(cx);
    if (!sepstr) {
      return false;
    }
  } else {
    sepstr = cx->names().comma_;
  }

  // Steps 5-8 (When the length is zero, directly return the empty string).
  if (length == 0) {
    args.rval().setString(cx->emptyString());
    return true;
  }

  // An optimized version of a special case of steps 5-8: when length==1 and
  // the 0th element is a string, ToString() of that element is a no-op and
  // so it can be immediately returned as the result.
  if (length == 1 && obj->is<NativeObject>()) {
    NativeObject* nobj = &obj->as<NativeObject>();
    if (nobj->getDenseInitializedLength() == 1) {
      Value elem0 = nobj->getDenseElement(0);
      if (elem0.isString()) {
        args.rval().set(elem0);
        return true;
      }
    }
  }

  // Step 5.
  JSStringBuilder sb(cx);
  if (sepstr->hasTwoByteChars() && !sb.ensureTwoByteChars()) {
    return false;
  }

  // The separator will be added |length - 1| times, reserve space for that
  // so that we don't have to unnecessarily grow the buffer.
  size_t seplen = sepstr->length();
  if (seplen > 0) {
    if (length > UINT32_MAX) {
      ReportAllocationOverflow(cx);
      return false;
    }
    CheckedInt<uint32_t> res =
        CheckedInt<uint32_t>(seplen) * (uint32_t(length) - 1);
    if (!res.isValid()) {
      ReportAllocationOverflow(cx);
      return false;
    }

    if (!sb.reserve(res.value())) {
      return false;
    }
  }

  // Various optimized versions of steps 6-7.
  if (seplen == 0) {
    auto sepOp = [](StringBuilder&) { return true; };
    if (!ArrayJoinKernel(cx, sepOp, obj, length, sb)) {
      return false;
    }
  } else if (seplen == 1) {
    char16_t c = sepstr->latin1OrTwoByteChar(0);
    if (c <= JSString::MAX_LATIN1_CHAR) {
      Latin1Char l1char = Latin1Char(c);
      auto sepOp = [l1char](StringBuilder& sb) { return sb.append(l1char); };
      if (!ArrayJoinKernel(cx, sepOp, obj, length, sb)) {
        return false;
      }
    } else {
      auto sepOp = [c](StringBuilder& sb) { return sb.append(c); };
      if (!ArrayJoinKernel(cx, sepOp, obj, length, sb)) {
        return false;
      }
    }
  } else {
    Handle<JSLinearString*> sepHandle = sepstr;
    auto sepOp = [sepHandle](StringBuilder& sb) {
      return sb.append(sepHandle);
    };
    if (!ArrayJoinKernel(cx, sepOp, obj, length, sb)) {
      return false;
    }
  }

  // Step 8.
  JSString* str = sb.finishString();
  if (!str) {
    return false;
  }

  args.rval().setString(str);
  return true;
}

// ES2017 draft rev f8a9be8ea4bd97237d176907a1e3080dce20c68f
// 22.1.3.27 Array.prototype.toLocaleString ([ reserved1 [ , reserved2 ] ])
// ES2017 Intl draft rev 78bbe7d1095f5ff3760ac4017ed366026e4cb276
// 13.4.1 Array.prototype.toLocaleString ([ locales [ , options ]])
static bool array_toLocaleString(JSContext* cx, unsigned argc, Value* vp) {
  AutoJSMethodProfilerEntry pseudoFrame(cx, "Array.prototype",
                                        "toLocaleString");

  CallArgs args = CallArgsFromVp(argc, vp);

  // Step 1
  RootedObject obj(cx, ToObject(cx, args.thisv()));
  if (!obj) {
    return false;
  }

  // Avoid calling into self-hosted code if the array is empty.
  if (obj->is<ArrayObject>() && obj->as<ArrayObject>().length() == 0) {
    args.rval().setString(cx->names().empty_);
    return true;
  }

  AutoCycleDetector detector(cx, obj);
  if (!detector.init()) {
    return false;
  }

  if (detector.foundCycle()) {
    args.rval().setString(cx->names().empty_);
    return true;
  }

  FixedInvokeArgs<2> args2(cx);

  args2[0].set(args.get(0));
  args2[1].set(args.get(1));

  // Steps 2-10.
  RootedValue thisv(cx, ObjectValue(*obj));
  return CallSelfHostedFunction(cx, cx->names().ArrayToLocaleString, thisv,
                                args2, args.rval());
}

/* vector must point to rooted memory. */
static bool SetArrayElements(JSContext* cx, HandleObject obj, uint64_t start,
                             uint32_t count, const Value* vector) {
  MOZ_ASSERT(count <= MAX_ARRAY_INDEX);
  MOZ_ASSERT(start + count < uint64_t(DOUBLE_INTEGRAL_PRECISION_LIMIT));

  if (count == 0) {
    return true;
  }

  if (!ObjectMayHaveExtraIndexedProperties(obj) && start <= UINT32_MAX) {
    NativeObject* nobj = &obj->as<NativeObject>();
    DenseElementResult result =
        nobj->setOrExtendDenseElements(cx, uint32_t(start), vector, count);
    if (result != DenseElementResult::Incomplete) {
      return result == DenseElementResult::Success;
    }
  }

  RootedId id(cx);
  const Value* end = vector + count;
  while (vector < end) {
    if (!CheckForInterrupt(cx)) {
      return false;
    }

    if (!ToId(cx, start++, &id)) {
      return false;
    }

    if (!SetProperty(cx, obj, id, HandleValue::fromMarkedLocation(vector++))) {
      return false;
    }
  }

  return true;
}

static DenseElementResult ArrayReverseDenseKernel(JSContext* cx,
                                                  Handle<NativeObject*> obj,
                                                  uint32_t length) {
  MOZ_ASSERT(length > 1);

  // If there are no elements, we're done.
  if (obj->getDenseInitializedLength() == 0) {
    return DenseElementResult::Success;
  }

  if (!obj->isExtensible()) {
    return DenseElementResult::Incomplete;
  }

  if (!IsPackedArray(obj)) {
    /*
     * It's actually surprisingly complicated to reverse an array due
     * to the orthogonality of array length and array capacity while
     * handling leading and trailing holes correctly.  Reversing seems
     * less likely to be a common operation than other array
     * mass-mutation methods, so for now just take a probably-small
     * memory hit (in the absence of too many holes in the array at
     * its start) and ensure that the capacity is sufficient to hold
     * all the elements in the array if it were full.
     */
    DenseElementResult result = obj->ensureDenseElements(cx, length, 0);
    if (result != DenseElementResult::Success) {
      return result;
    }

    /* Fill out the array's initialized length to its proper length. */
    obj->ensureDenseInitializedLength(length, 0);
  }

  if (!obj->denseElementsMaybeInIteration() &&
      !cx->zone()->needsIncrementalBarrier()) {
    obj->reverseDenseElementsNoPreBarrier(length);
    return DenseElementResult::Success;
  }

  auto setElementMaybeHole = [](JSContext* cx, Handle<NativeObject*> obj,
                                uint32_t index, const Value& val) {
    if (MOZ_LIKELY(!val.isMagic(JS_ELEMENTS_HOLE))) {
      obj->setDenseElement(index, val);
      return true;
    }

    obj->setDenseElementHole(index);
    return SuppressDeletedProperty(cx, obj, PropertyKey::Int(index));
  };

  RootedValue origlo(cx), orighi(cx);

  uint32_t lo = 0, hi = length - 1;
  for (; lo < hi; lo++, hi--) {
    origlo = obj->getDenseElement(lo);
    orighi = obj->getDenseElement(hi);
    if (!setElementMaybeHole(cx, obj, lo, orighi)) {
      return DenseElementResult::Failure;
    }
    if (!setElementMaybeHole(cx, obj, hi, origlo)) {
      return DenseElementResult::Failure;
    }
  }

  return DenseElementResult::Success;
}

// ES2017 draft rev 1b0184bc17fc09a8ddcf4aeec9b6d9fcac4eafce
// 22.1.3.21 Array.prototype.reverse ( )
static bool array_reverse(JSContext* cx, unsigned argc, Value* vp) {
  AutoJSMethodProfilerEntry pseudoFrame(cx, "Array.prototype", "reverse");
  CallArgs args = CallArgsFromVp(argc, vp);

  // Step 1.
  RootedObject obj(cx, ToObject(cx, args.thisv()));
  if (!obj) {
    return false;
  }

  // Step 2.
  uint64_t len;
  if (!GetLengthPropertyInlined(cx, obj, &len)) {
    return false;
  }

  // An empty array or an array with length 1 is already reversed.
  if (len <= 1) {
    args.rval().setObject(*obj);
    return true;
  }

  if (IsPackedArrayOrNoExtraIndexedProperties(obj, len) && len <= UINT32_MAX) {
    DenseElementResult result =
        ArrayReverseDenseKernel(cx, obj.as<NativeObject>(), uint32_t(len));
    if (result != DenseElementResult::Incomplete) {
      /*
       * Per ECMA-262, don't update the length of the array, even if the new
       * array has trailing holes (and thus the original array began with
       * holes).
       */
      args.rval().setObject(*obj);
      return result == DenseElementResult::Success;
    }
  }

  // Steps 3-5.
  RootedValue lowval(cx), hival(cx);
  for (uint64_t i = 0, half = len / 2; i < half; i++) {
    bool hole, hole2;
    if (!CheckForInterrupt(cx) ||
        !HasAndGetElement(cx, obj, i, &hole, &lowval) ||
        !HasAndGetElement(cx, obj, len - i - 1, &hole2, &hival)) {
      return false;
    }

    if (!hole && !hole2) {
      if (!SetArrayElement(cx, obj, i, hival)) {
        return false;
      }
      if (!SetArrayElement(cx, obj, len - i - 1, lowval)) {
        return false;
      }
    } else if (hole && !hole2) {
      if (!SetArrayElement(cx, obj, i, hival)) {
        return false;
      }
      if (!DeletePropertyOrThrow(cx, obj, len - i - 1)) {
        return false;
      }
    } else if (!hole && hole2) {
      if (!DeletePropertyOrThrow(cx, obj, i)) {
        return false;
      }
      if (!SetArrayElement(cx, obj, len - i - 1, lowval)) {
        return false;
      }
    } else {
      // No action required.
    }
  }

  // Step 6.
  args.rval().setObject(*obj);
  return true;
}

static inline bool CompareStringValues(JSContext* cx, const Value& a,
                                       const Value& b, bool* lessOrEqualp) {
  if (!CheckForInterrupt(cx)) {
    return false;
  }

  JSString* astr = a.toString();
  JSString* bstr = b.toString();
  int32_t result;
  if (!CompareStrings(cx, astr, bstr, &result)) {
    return false;
  }

  *lessOrEqualp = (result <= 0);
  return true;
}

static const uint64_t powersOf10[] = {
    1,       10,       100,       1000,       10000,           100000,
    1000000, 10000000, 100000000, 1000000000, 1000000000000ULL};

static inline unsigned NumDigitsBase10(uint32_t n) {
  /*
   * This is just floor_log10(n) + 1
   * Algorithm taken from
   * http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog10
   */
  uint32_t log2 = CeilingLog2(n);
  uint32_t t = log2 * 1233 >> 12;
  return t - (n < powersOf10[t]) + 1;
}

static inline bool CompareLexicographicInt32(const Value& a, const Value& b,
                                             bool* lessOrEqualp) {
  int32_t aint = a.toInt32();
  int32_t bint = b.toInt32();

  /*
   * If both numbers are equal ... trivial
   * If only one of both is negative --> arithmetic comparison as char code
   * of '-' is always less than any other digit
   * If both numbers are negative convert them to positive and continue
   * handling ...
   */
  if (aint == bint) {
    *lessOrEqualp = true;
  } else if ((aint < 0) && (bint >= 0)) {
    *lessOrEqualp = true;
  } else if ((aint >= 0) && (bint < 0)) {
    *lessOrEqualp = false;
  } else {
    uint32_t auint = Abs(aint);
    uint32_t buint = Abs(bint);

    /*
     *  ... get number of digits of both integers.
     * If they have the same number of digits --> arithmetic comparison.
     * If digits_a > digits_b: a < b*10e(digits_a - digits_b).
     * If digits_b > digits_a: a*10e(digits_b - digits_a) <= b.
     */
    unsigned digitsa = NumDigitsBase10(auint);
    unsigned digitsb = NumDigitsBase10(buint);
    if (digitsa == digitsb) {
      *lessOrEqualp = (auint <= buint);
    } else if (digitsa > digitsb) {
      MOZ_ASSERT((digitsa - digitsb) < std::size(powersOf10));
      *lessOrEqualp =
          (uint64_t(auint) < uint64_t(buint) * powersOf10[digitsa - digitsb]);
    } else { /* if (digitsb > digitsa) */
      MOZ_ASSERT((digitsb - digitsa) < std::size(powersOf10));
      *lessOrEqualp =
          (uint64_t(auint) * powersOf10[digitsb - digitsa] <= uint64_t(buint));
    }
  }

  return true;
}

template <typename Char1, typename Char2>
static inline bool CompareSubStringValues(JSContext* cx, const Char1* s1,
                                          size_t len1, const Char2* s2,
                                          size_t len2, bool* lessOrEqualp) {
  if (!CheckForInterrupt(cx)) {
    return false;
  }

  if (!s1 || !s2) {
    return false;
  }

  int32_t result = CompareChars(s1, len1, s2, len2);
  *lessOrEqualp = (result <= 0);
  return true;
}

namespace {

struct SortComparatorStrings {
  JSContext* const cx;

  explicit SortComparatorStrings(JSContext* cx) : cx(cx) {}

  bool operator()(const Value& a, const Value& b, bool* lessOrEqualp) {
    return CompareStringValues(cx, a, b, lessOrEqualp);
  }
};

struct SortComparatorLexicographicInt32 {
  bool operator()(const Value& a, const Value& b, bool* lessOrEqualp) {
    return CompareLexicographicInt32(a, b, lessOrEqualp);
  }
};

struct StringifiedElement {
  size_t charsBegin;
  size_t charsEnd;
  size_t elementIndex;
};

struct SortComparatorStringifiedElements {
  JSContext* const cx;
  const StringBuilder& sb;

  SortComparatorStringifiedElements(JSContext* cx, const StringBuilder& sb)
      : cx(cx), sb(sb) {}

  bool operator()(const StringifiedElement& a, const StringifiedElement& b,
                  bool* lessOrEqualp) {
    size_t lenA = a.charsEnd - a.charsBegin;
    size_t lenB = b.charsEnd - b.charsBegin;

    if (sb.isUnderlyingBufferLatin1()) {
      return CompareSubStringValues(cx, sb.rawLatin1Begin() + a.charsBegin,
                                    lenA, sb.rawLatin1Begin() + b.charsBegin,
                                    lenB, lessOrEqualp);
    }

    return CompareSubStringValues(cx, sb.rawTwoByteBegin() + a.charsBegin, lenA,
                                  sb.rawTwoByteBegin() + b.charsBegin, lenB,
                                  lessOrEqualp);
  }
};

struct NumericElement {
  double dv;
  size_t elementIndex;
};

static bool ComparatorNumericLeftMinusRight(const NumericElement& a,
                                            const NumericElement& b,
                                            bool* lessOrEqualp) {
  *lessOrEqualp = std::isunordered(a.dv, b.dv) || (a.dv <= b.dv);
  return true;
}

static bool ComparatorNumericRightMinusLeft(const NumericElement& a,
                                            const NumericElement& b,
                                            bool* lessOrEqualp) {
  *lessOrEqualp = std::isunordered(a.dv, b.dv) || (b.dv <= a.dv);
  return true;
}

using ComparatorNumeric = bool (*)(const NumericElement&, const NumericElement&,
                                   bool*);

static const ComparatorNumeric SortComparatorNumerics[] = {
    nullptr, nullptr, ComparatorNumericLeftMinusRight,
    ComparatorNumericRightMinusLeft};

static bool ComparatorInt32LeftMinusRight(const Value& a, const Value& b,
                                          bool* lessOrEqualp) {
  *lessOrEqualp = (a.toInt32() <= b.toInt32());
  return true;
}

static bool ComparatorInt32RightMinusLeft(const Value& a, const Value& b,
                                          bool* lessOrEqualp) {
  *lessOrEqualp = (b.toInt32() <= a.toInt32());
  return true;
}

using ComparatorInt32 = bool (*)(const Value&, const Value&, bool*);

static const ComparatorInt32 SortComparatorInt32s[] = {
    nullptr, nullptr, ComparatorInt32LeftMinusRight,
    ComparatorInt32RightMinusLeft};

// Note: Values for this enum must match up with SortComparatorNumerics
// and SortComparatorInt32s.
enum ComparatorMatchResult {
  Match_Failure = 0,
  Match_None,
  Match_LeftMinusRight,
  Match_RightMinusLeft
};

}  // namespace

/*
 * Specialize behavior for comparator functions with particular common bytecode
 * patterns: namely, |return x - y| and |return y - x|.
 */
static ComparatorMatchResult MatchNumericComparator(JSContext* cx,
                                                    JSObject* obj) {
  if (!obj->is<JSFunction>()) {
    return Match_None;
  }

  RootedFunction fun(cx, &obj->as<JSFunction>());
  if (!fun->isInterpreted() || fun->isClassConstructor()) {
    return Match_None;
  }

  JSScript* script = JSFunction::getOrCreateScript(cx, fun);
  if (!script) {
    return Match_Failure;
  }

  jsbytecode* pc = script->code();

  uint16_t arg0, arg1;
  if (JSOp(*pc) != JSOp::GetArg) {
    return Match_None;
  }
  arg0 = GET_ARGNO(pc);
  pc += JSOpLength_GetArg;

  if (JSOp(*pc) != JSOp::GetArg) {
    return Match_None;
  }
  arg1 = GET_ARGNO(pc);
  pc += JSOpLength_GetArg;

  if (JSOp(*pc) != JSOp::Sub) {
    return Match_None;
  }
  pc += JSOpLength_Sub;

  if (JSOp(*pc) != JSOp::Return) {
    return Match_None;
  }

  if (arg0 == 0 && arg1 == 1) {
    return Match_LeftMinusRight;
  }

  if (arg0 == 1 && arg1 == 0) {
    return Match_RightMinusLeft;
  }

  return Match_None;
}

template <typename K, typename C>
static inline bool MergeSortByKey(K keys, size_t len, K scratch, C comparator,
                                  MutableHandle<GCVector<Value>> vec) {
  MOZ_ASSERT(vec.length() >= len);

  /* Sort keys. */
  if (!MergeSort(keys, len, scratch, comparator)) {
    return false;
  }

  /*
   * Reorder vec by keys in-place, going element by element.  When an out-of-
   * place element is encountered, move that element to its proper position,
   * displacing whatever element was at *that* point to its proper position,
   * and so on until an element must be moved to the current position.
   *
   * At each outer iteration all elements up to |i| are sorted.  If
   * necessary each inner iteration moves some number of unsorted elements
   * (including |i|) directly to sorted position.  Thus on completion |*vec|
   * is sorted, and out-of-position elements have moved once.  Complexity is
   * Θ(len) + O(len) == O(2*len), with each element visited at most twice.
   */
  for (size_t i = 0; i < len; i++) {
    size_t j = keys[i].elementIndex;
    if (i == j) {
      continue;  // fixed point
    }

    MOZ_ASSERT(j > i, "Everything less than |i| should be in the right place!");
    Value tv = vec[j];
    do {
      size_t k = keys[j].elementIndex;
      keys[j].elementIndex = j;
      vec[j].set(vec[k]);
      j = k;
    } while (j != i);

    // We could assert the loop invariant that |i == keys[i].elementIndex|
    // here if we synced |keys[i].elementIndex|.  But doing so would render
    // the assertion vacuous, so don't bother, even in debug builds.
    vec[i].set(tv);
  }

  return true;
}

/*
 * Sort Values as strings.
 *
 * To minimize #conversions, SortLexicographically() first converts all Values
 * to strings at once, then sorts the elements by these cached strings.
 */
static bool SortLexicographically(JSContext* cx,
                                  MutableHandle<GCVector<Value>> vec,
                                  size_t len) {
  MOZ_ASSERT(vec.length() >= len);

  StringBuilder sb(cx);
  Vector<StringifiedElement, 0, TempAllocPolicy> strElements(cx);

  /* MergeSort uses the upper half as scratch space. */
  if (!strElements.resize(2 * len)) {
    return false;
  }

  /* Convert Values to strings. */
  size_t cursor = 0;
  for (size_t i = 0; i < len; i++) {
    if (!CheckForInterrupt(cx)) {
      return false;
    }

    if (!ValueToStringBuilder(cx, vec[i], sb)) {
      return false;
    }

    strElements[i] = {cursor, sb.length(), i};
    cursor = sb.length();
  }

  /* Sort Values in vec alphabetically. */
  return MergeSortByKey(strElements.begin(), len, strElements.begin() + len,
                        SortComparatorStringifiedElements(cx, sb), vec);
}

/*
 * Sort Values as numbers.
 *
 * To minimize #conversions, SortNumerically first converts all Values to
 * numerics at once, then sorts the elements by these cached numerics.
 */
static bool SortNumerically(JSContext* cx, MutableHandle<GCVector<Value>> vec,
                            size_t len, ComparatorMatchResult comp) {
  MOZ_ASSERT(vec.length() >= len);

  Vector<NumericElement, 0, TempAllocPolicy> numElements(cx);

  /* MergeSort uses the upper half as scratch space. */
  if (!numElements.resize(2 * len)) {
    return false;
  }

  /* Convert Values to numerics. */
  for (size_t i = 0; i < len; i++) {
    if (!CheckForInterrupt(cx)) {
      return false;
    }

    double dv;
    if (!ToNumber(cx, vec[i], &dv)) {
      return false;
    }

    numElements[i] = {dv, i};
  }

  /* Sort Values in vec numerically. */
  return MergeSortByKey(numElements.begin(), len, numElements.begin() + len,
                        SortComparatorNumerics[comp], vec);
}

static bool FillWithUndefined(JSContext* cx, HandleObject obj, uint32_t start,
                              uint32_t count) {
  MOZ_ASSERT(start < start + count,
             "count > 0 and start + count doesn't overflow");

  do {
    if (ObjectMayHaveExtraIndexedProperties(obj)) {
      break;
    }

    NativeObject* nobj = &obj->as<NativeObject>();
    if (!nobj->isExtensible()) {
      break;
    }

    if (obj->is<ArrayObject>() && !obj->as<ArrayObject>().lengthIsWritable() &&
        start + count >= obj->as<ArrayObject>().length()) {
      break;
    }

    DenseElementResult result = nobj->ensureDenseElements(cx, start, count);
    if (result != DenseElementResult::Success) {
      if (result == DenseElementResult::Failure) {
        return false;
      }
      MOZ_ASSERT(result == DenseElementResult::Incomplete);
      break;
    }

    if (obj->is<ArrayObject>() &&
        start + count >= obj->as<ArrayObject>().length()) {
      obj->as<ArrayObject>().setLength(start + count);
    }

    for (uint32_t i = 0; i < count; i++) {
      nobj->setDenseElement(start + i, UndefinedHandleValue);
    }

    return true;
  } while (false);

  for (uint32_t i = 0; i < count; i++) {
    if (!CheckForInterrupt(cx) ||
        !SetArrayElement(cx, obj, start + i, UndefinedHandleValue)) {
      return false;
    }
  }

  return true;
}

static bool ArraySortWithoutComparator(JSContext* cx, Handle<JSObject*> obj,
                                       uint64_t length,
                                       ComparatorMatchResult comp) {
  MOZ_ASSERT(length > 1);

  if (length > UINT32_MAX) {
    ReportAllocationOverflow(cx);
    return false;
  }
  uint32_t len = uint32_t(length);

  /*
   * We need a temporary array of 2 * len Value to hold the array elements
   * and the scratch space for merge sort. Check that its size does not
   * overflow size_t, which would allow for indexing beyond the end of the
   * malloc'd vector.
   */
#if JS_BITS_PER_WORD == 32
  if (size_t(len) > size_t(-1) / (2 * sizeof(Value))) {
    ReportAllocationOverflow(cx);
    return false;
  }
#endif

  size_t n, undefs;
  {
    Rooted<GCVector<Value>> vec(cx, GCVector<Value>(cx));
    if (!vec.reserve(2 * size_t(len))) {
      return false;
    }

    /*
     * By ECMA 262, 15.4.4.11, a property that does not exist (which we
     * call a "hole") is always greater than an existing property with
     * value undefined and that is always greater than any other property.
     * Thus to sort holes and undefs we simply count them, sort the rest
     * of elements, append undefs after them and then make holes after
     * undefs.
     */
    undefs = 0;
    bool allStrings = true;
    bool allInts = true;
    RootedValue v(cx);
    if (IsPackedArray(obj)) {
      Handle<ArrayObject*> array = obj.as<ArrayObject>();

      for (uint32_t i = 0; i < len; i++) {
        if (!CheckForInterrupt(cx)) {
          return false;
        }

        v.set(array->getDenseElement(i));
        MOZ_ASSERT(!v.isMagic(JS_ELEMENTS_HOLE));
        if (v.isUndefined()) {
          ++undefs;
          continue;
        }
        vec.infallibleAppend(v);
        allStrings = allStrings && v.isString();
        allInts = allInts && v.isInt32();
      }
    } else {
      for (uint32_t i = 0; i < len; i++) {
        if (!CheckForInterrupt(cx)) {
          return false;
        }

        bool hole;
        if (!HasAndGetElement(cx, obj, i, &hole, &v)) {
          return false;
        }
        if (hole) {
          continue;
        }
        if (v.isUndefined()) {
          ++undefs;
          continue;
        }
        vec.infallibleAppend(v);
        allStrings = allStrings && v.isString();
        allInts = allInts && v.isInt32();
      }
    }

    /*
     * If the array only contains holes, we're done.  But if it contains
     * undefs, those must be sorted to the front of the array.
     */
    n = vec.length();
    if (n == 0 && undefs == 0) {
      return true;
    }

    /* Here len == n + undefs + number_of_holes. */
    if (comp == Match_None) {
      /*
       * Sort using the default comparator converting all elements to
       * strings.
       */
      if (allStrings) {
        MOZ_ALWAYS_TRUE(vec.resize(n * 2));
        if (!MergeSort(vec.begin(), n, vec.begin() + n,
                       SortComparatorStrings(cx))) {
          return false;
        }
      } else if (allInts) {
        MOZ_ALWAYS_TRUE(vec.resize(n * 2));
        if (!MergeSort(vec.begin(), n, vec.begin() + n,
                       SortComparatorLexicographicInt32())) {
          return false;
        }
      } else {
        if (!SortLexicographically(cx, &vec, n)) {
          return false;
        }
      }
    } else {
      if (allInts) {
        MOZ_ALWAYS_TRUE(vec.resize(n * 2));
        if (!MergeSort(vec.begin(), n, vec.begin() + n,
                       SortComparatorInt32s[comp])) {
          return false;
        }
      } else {
        if (!SortNumerically(cx, &vec, n, comp)) {
          return false;
        }
      }
    }

    if (!SetArrayElements(cx, obj, 0, uint32_t(n), vec.begin())) {
      return false;
    }
  }

  /* Set undefs that sorted after the rest of elements. */
  if (undefs > 0) {
    if (!FillWithUndefined(cx, obj, n, undefs)) {
      return false;
    }
    n += undefs;
  }

  /* Re-create any holes that sorted to the end of the array. */
  for (uint32_t i = n; i < len; i++) {
    if (!CheckForInterrupt(cx) || !DeletePropertyOrThrow(cx, obj, i)) {
      return false;
    }
  }
  return true;
--> --------------------

--> maximum size reached

--> --------------------