1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/js/src/jsarray.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,3357 @@
1.4 +/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
1.5 + * vim: set ts=8 sts=4 et sw=4 tw=99:
1.6 + * This Source Code Form is subject to the terms of the Mozilla Public
1.7 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.8 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.9 +
1.10 +#include "jsarray.h"
1.11 +
1.12 +#include "mozilla/ArrayUtils.h"
1.13 +#include "mozilla/DebugOnly.h"
1.14 +#include "mozilla/FloatingPoint.h"
1.15 +#include "mozilla/MathAlgorithms.h"
1.16 +
1.17 +#include "jsapi.h"
1.18 +#include "jsatom.h"
1.19 +#include "jscntxt.h"
1.20 +#include "jsfriendapi.h"
1.21 +#include "jsfun.h"
1.22 +#include "jsiter.h"
1.23 +#include "jsnum.h"
1.24 +#include "jsobj.h"
1.25 +#include "jstypes.h"
1.26 +#include "jsutil.h"
1.27 +
1.28 +#include "ds/Sort.h"
1.29 +#include "gc/Heap.h"
1.30 +#include "vm/ArgumentsObject.h"
1.31 +#include "vm/ForkJoin.h"
1.32 +#include "vm/Interpreter.h"
1.33 +#include "vm/NumericConversions.h"
1.34 +#include "vm/Shape.h"
1.35 +#include "vm/StringBuffer.h"
1.36 +
1.37 +#include "jsatominlines.h"
1.38 +
1.39 +#include "vm/ArgumentsObject-inl.h"
1.40 +#include "vm/ArrayObject-inl.h"
1.41 +#include "vm/Interpreter-inl.h"
1.42 +#include "vm/Runtime-inl.h"
1.43 +
1.44 +using namespace js;
1.45 +using namespace js::gc;
1.46 +using namespace js::types;
1.47 +
1.48 +using mozilla::Abs;
1.49 +using mozilla::ArrayLength;
1.50 +using mozilla::CeilingLog2;
1.51 +using mozilla::DebugOnly;
1.52 +using mozilla::IsNaN;
1.53 +using mozilla::PointerRangeSize;
1.54 +
1.55 +bool
1.56 +js::GetLengthProperty(JSContext *cx, HandleObject obj, uint32_t *lengthp)
1.57 +{
1.58 + if (obj->is<ArrayObject>()) {
1.59 + *lengthp = obj->as<ArrayObject>().length();
1.60 + return true;
1.61 + }
1.62 +
1.63 + if (obj->is<ArgumentsObject>()) {
1.64 + ArgumentsObject &argsobj = obj->as<ArgumentsObject>();
1.65 + if (!argsobj.hasOverriddenLength()) {
1.66 + *lengthp = argsobj.initialLength();
1.67 + return true;
1.68 + }
1.69 + }
1.70 +
1.71 + RootedValue value(cx);
1.72 + if (!JSObject::getProperty(cx, obj, obj, cx->names().length, &value))
1.73 + return false;
1.74 +
1.75 + if (value.isInt32()) {
1.76 + *lengthp = uint32_t(value.toInt32()); // uint32_t cast does ToUint32
1.77 + return true;
1.78 + }
1.79 +
1.80 + return ToUint32(cx, value, lengthp);
1.81 +}
1.82 +
1.83 +/*
1.84 + * Determine if the id represents an array index.
1.85 + *
1.86 + * An id is an array index according to ECMA by (15.4):
1.87 + *
1.88 + * "Array objects give special treatment to a certain class of property names.
1.89 + * A property name P (in the form of a string value) is an array index if and
1.90 + * only if ToString(ToUint32(P)) is equal to P and ToUint32(P) is not equal
1.91 + * to 2^32-1."
1.92 + *
1.93 + * This means the largest allowed index is actually 2^32-2 (4294967294).
1.94 + *
1.95 + * In our implementation, it would be sufficient to check for JSVAL_IS_INT(id)
1.96 + * except that by using signed 31-bit integers we miss the top half of the
1.97 + * valid range. This function checks the string representation itself; note
1.98 + * that calling a standard conversion routine might allow strings such as
1.99 + * "08" or "4.0" as array indices, which they are not.
1.100 + *
1.101 + */
1.102 +JS_FRIEND_API(bool)
1.103 +js::StringIsArrayIndex(JSLinearString *str, uint32_t *indexp)
1.104 +{
1.105 + const jschar *s = str->chars();
1.106 + uint32_t length = str->length();
1.107 + const jschar *end = s + length;
1.108 +
1.109 + if (length == 0 || length > (sizeof("4294967294") - 1) || !JS7_ISDEC(*s))
1.110 + return false;
1.111 +
1.112 + uint32_t c = 0, previous = 0;
1.113 + uint32_t index = JS7_UNDEC(*s++);
1.114 +
1.115 + /* Don't allow leading zeros. */
1.116 + if (index == 0 && s != end)
1.117 + return false;
1.118 +
1.119 + for (; s < end; s++) {
1.120 + if (!JS7_ISDEC(*s))
1.121 + return false;
1.122 +
1.123 + previous = index;
1.124 + c = JS7_UNDEC(*s);
1.125 + index = 10 * index + c;
1.126 + }
1.127 +
1.128 + /* Make sure we didn't overflow. */
1.129 + if (previous < (MAX_ARRAY_INDEX / 10) || (previous == (MAX_ARRAY_INDEX / 10) &&
1.130 + c <= (MAX_ARRAY_INDEX % 10))) {
1.131 + JS_ASSERT(index <= MAX_ARRAY_INDEX);
1.132 + *indexp = index;
1.133 + return true;
1.134 + }
1.135 +
1.136 + return false;
1.137 +}
1.138 +
1.139 +static bool
1.140 +ToId(JSContext *cx, double index, MutableHandleId id)
1.141 +{
1.142 + if (index == uint32_t(index))
1.143 + return IndexToId(cx, uint32_t(index), id);
1.144 +
1.145 + Value tmp = DoubleValue(index);
1.146 + return ValueToId<CanGC>(cx, HandleValue::fromMarkedLocation(&tmp), id);
1.147 +}
1.148 +
1.149 +static bool
1.150 +ToId(JSContext *cx, uint32_t index, MutableHandleId id)
1.151 +{
1.152 + return IndexToId(cx, index, id);
1.153 +}
1.154 +
1.155 +/*
1.156 + * If the property at the given index exists, get its value into location
1.157 + * pointed by vp and set *hole to false. Otherwise set *hole to true and *vp
1.158 + * to JSVAL_VOID. This function assumes that the location pointed by vp is
1.159 + * properly rooted and can be used as GC-protected storage for temporaries.
1.160 + */
1.161 +template<typename IndexType>
1.162 +static inline bool
1.163 +DoGetElement(JSContext *cx, HandleObject obj, HandleObject receiver,
1.164 + IndexType index, bool *hole, MutableHandleValue vp)
1.165 +{
1.166 + RootedId id(cx);
1.167 + if (!ToId(cx, index, &id))
1.168 + return false;
1.169 +
1.170 + RootedObject obj2(cx);
1.171 + RootedShape prop(cx);
1.172 + if (!JSObject::lookupGeneric(cx, obj, id, &obj2, &prop))
1.173 + return false;
1.174 +
1.175 + if (!prop) {
1.176 + vp.setUndefined();
1.177 + *hole = true;
1.178 + } else {
1.179 + if (!JSObject::getGeneric(cx, obj, receiver, id, vp))
1.180 + return false;
1.181 + *hole = false;
1.182 + }
1.183 + return true;
1.184 +}
1.185 +
1.186 +template<typename IndexType>
1.187 +static void
1.188 +AssertGreaterThanZero(IndexType index)
1.189 +{
1.190 + JS_ASSERT(index >= 0);
1.191 + JS_ASSERT(index == floor(index));
1.192 +}
1.193 +
1.194 +template<>
1.195 +void
1.196 +AssertGreaterThanZero(uint32_t index)
1.197 +{
1.198 +}
1.199 +
1.200 +template<typename IndexType>
1.201 +static bool
1.202 +GetElement(JSContext *cx, HandleObject obj, HandleObject receiver,
1.203 + IndexType index, bool *hole, MutableHandleValue vp)
1.204 +{
1.205 + AssertGreaterThanZero(index);
1.206 + if (obj->isNative() && index < obj->getDenseInitializedLength()) {
1.207 + vp.set(obj->getDenseElement(uint32_t(index)));
1.208 + if (!vp.isMagic(JS_ELEMENTS_HOLE)) {
1.209 + *hole = false;
1.210 + return true;
1.211 + }
1.212 + }
1.213 + if (obj->is<ArgumentsObject>()) {
1.214 + if (obj->as<ArgumentsObject>().maybeGetElement(uint32_t(index), vp)) {
1.215 + *hole = false;
1.216 + return true;
1.217 + }
1.218 + }
1.219 +
1.220 + return DoGetElement(cx, obj, receiver, index, hole, vp);
1.221 +}
1.222 +
1.223 +template<typename IndexType>
1.224 +static inline bool
1.225 +GetElement(JSContext *cx, HandleObject obj, IndexType index, bool *hole, MutableHandleValue vp)
1.226 +{
1.227 + return GetElement(cx, obj, obj, index, hole, vp);
1.228 +}
1.229 +
1.230 +static bool
1.231 +GetElementsSlow(JSContext *cx, HandleObject aobj, uint32_t length, Value *vp)
1.232 +{
1.233 + for (uint32_t i = 0; i < length; i++) {
1.234 + if (!JSObject::getElement(cx, aobj, aobj, i, MutableHandleValue::fromMarkedLocation(&vp[i])))
1.235 + return false;
1.236 + }
1.237 +
1.238 + return true;
1.239 +}
1.240 +
1.241 +bool
1.242 +js::GetElements(JSContext *cx, HandleObject aobj, uint32_t length, Value *vp)
1.243 +{
1.244 + if (aobj->is<ArrayObject>() && length <= aobj->getDenseInitializedLength() &&
1.245 + !ObjectMayHaveExtraIndexedProperties(aobj))
1.246 + {
1.247 + /* No other indexed properties so hole = undefined */
1.248 + const Value *srcbeg = aobj->getDenseElements();
1.249 + const Value *srcend = srcbeg + length;
1.250 + const Value *src = srcbeg;
1.251 + for (Value *dst = vp; src < srcend; ++dst, ++src)
1.252 + *dst = src->isMagic(JS_ELEMENTS_HOLE) ? UndefinedValue() : *src;
1.253 + return true;
1.254 + }
1.255 +
1.256 + if (aobj->is<ArgumentsObject>()) {
1.257 + ArgumentsObject &argsobj = aobj->as<ArgumentsObject>();
1.258 + if (!argsobj.hasOverriddenLength()) {
1.259 + if (argsobj.maybeGetElements(0, length, vp))
1.260 + return true;
1.261 + }
1.262 + }
1.263 +
1.264 + return GetElementsSlow(cx, aobj, length, vp);
1.265 +}
1.266 +
1.267 +/*
1.268 + * Set the value of the property at the given index to v assuming v is rooted.
1.269 + */
1.270 +static bool
1.271 +SetArrayElement(JSContext *cx, HandleObject obj, double index, HandleValue v)
1.272 +{
1.273 + JS_ASSERT(index >= 0);
1.274 +
1.275 + if (obj->is<ArrayObject>() && !obj->isIndexed()) {
1.276 + Rooted<ArrayObject*> arr(cx, &obj->as<ArrayObject>());
1.277 + /* Predicted/prefetched code should favor the remains-dense case. */
1.278 + JSObject::EnsureDenseResult result = JSObject::ED_SPARSE;
1.279 + do {
1.280 + if (index > uint32_t(-1))
1.281 + break;
1.282 + uint32_t idx = uint32_t(index);
1.283 + if (idx >= arr->length() && !arr->lengthIsWritable()) {
1.284 + JS_ReportErrorFlagsAndNumber(cx, JSREPORT_ERROR, js_GetErrorMessage, nullptr,
1.285 + JSMSG_CANT_REDEFINE_ARRAY_LENGTH);
1.286 + return false;
1.287 + }
1.288 + result = arr->ensureDenseElements(cx, idx, 1);
1.289 + if (result != JSObject::ED_OK)
1.290 + break;
1.291 + if (idx >= arr->length())
1.292 + arr->setLengthInt32(idx + 1);
1.293 + arr->setDenseElementWithType(cx, idx, v);
1.294 + return true;
1.295 + } while (false);
1.296 +
1.297 + if (result == JSObject::ED_FAILED)
1.298 + return false;
1.299 + JS_ASSERT(result == JSObject::ED_SPARSE);
1.300 + }
1.301 +
1.302 + RootedId id(cx);
1.303 + if (!ToId(cx, index, &id))
1.304 + return false;
1.305 +
1.306 + RootedValue tmp(cx, v);
1.307 + return JSObject::setGeneric(cx, obj, obj, id, &tmp, true);
1.308 +}
1.309 +
1.310 +/*
1.311 + * Attempt to delete the element |index| from |obj| as if by
1.312 + * |obj.[[Delete]](index)|.
1.313 + *
1.314 + * If an error occurs while attempting to delete the element (that is, the call
1.315 + * to [[Delete]] threw), return false.
1.316 + *
1.317 + * Otherwise set *succeeded to indicate whether the deletion attempt succeeded
1.318 + * (that is, whether the call to [[Delete]] returned true or false). (Deletes
1.319 + * generally fail only when the property is non-configurable, but proxies may
1.320 + * implement different semantics.)
1.321 + */
1.322 +static bool
1.323 +DeleteArrayElement(JSContext *cx, HandleObject obj, double index, bool *succeeded)
1.324 +{
1.325 + JS_ASSERT(index >= 0);
1.326 + JS_ASSERT(floor(index) == index);
1.327 +
1.328 + if (obj->is<ArrayObject>() && !obj->isIndexed()) {
1.329 + if (index <= UINT32_MAX) {
1.330 + uint32_t idx = uint32_t(index);
1.331 + if (idx < obj->getDenseInitializedLength()) {
1.332 + obj->markDenseElementsNotPacked(cx);
1.333 + obj->setDenseElement(idx, MagicValue(JS_ELEMENTS_HOLE));
1.334 + if (!js_SuppressDeletedElement(cx, obj, idx))
1.335 + return false;
1.336 + }
1.337 + }
1.338 +
1.339 + *succeeded = true;
1.340 + return true;
1.341 + }
1.342 +
1.343 + if (index <= UINT32_MAX)
1.344 + return JSObject::deleteElement(cx, obj, uint32_t(index), succeeded);
1.345 +
1.346 + return JSObject::deleteByValue(cx, obj, DoubleValue(index), succeeded);
1.347 +}
1.348 +
1.349 +/* ES6 20130308 draft 9.3.5 */
1.350 +static bool
1.351 +DeletePropertyOrThrow(JSContext *cx, HandleObject obj, double index)
1.352 +{
1.353 + bool succeeded;
1.354 + if (!DeleteArrayElement(cx, obj, index, &succeeded))
1.355 + return false;
1.356 + if (succeeded)
1.357 + return true;
1.358 +
1.359 + RootedId id(cx);
1.360 + RootedValue indexv(cx, NumberValue(index));
1.361 + if (!ValueToId<CanGC>(cx, indexv, &id))
1.362 + return false;
1.363 + return obj->reportNotConfigurable(cx, id, JSREPORT_ERROR);
1.364 +}
1.365 +
1.366 +bool
1.367 +js::SetLengthProperty(JSContext *cx, HandleObject obj, double length)
1.368 +{
1.369 + RootedValue v(cx, NumberValue(length));
1.370 + return JSObject::setProperty(cx, obj, obj, cx->names().length, &v, true);
1.371 +}
1.372 +
1.373 +/*
1.374 + * Since SpiderMonkey supports cross-class prototype-based delegation, we have
1.375 + * to be careful about the length getter and setter being called on an object
1.376 + * not of Array class. For the getter, we search obj's prototype chain for the
1.377 + * array that caused this getter to be invoked. In the setter case to overcome
1.378 + * the JSPROP_SHARED attribute, we must define a shadowing length property.
1.379 + */
1.380 +static bool
1.381 +array_length_getter(JSContext *cx, HandleObject obj_, HandleId id, MutableHandleValue vp)
1.382 +{
1.383 + RootedObject obj(cx, obj_);
1.384 + do {
1.385 + if (obj->is<ArrayObject>()) {
1.386 + vp.setNumber(obj->as<ArrayObject>().length());
1.387 + return true;
1.388 + }
1.389 + if (!JSObject::getProto(cx, obj, &obj))
1.390 + return false;
1.391 + } while (obj);
1.392 + return true;
1.393 +}
1.394 +
1.395 +static bool
1.396 +array_length_setter(JSContext *cx, HandleObject obj, HandleId id, bool strict, MutableHandleValue vp)
1.397 +{
1.398 + if (!obj->is<ArrayObject>()) {
1.399 + return JSObject::defineProperty(cx, obj, cx->names().length, vp,
1.400 + nullptr, nullptr, JSPROP_ENUMERATE);
1.401 + }
1.402 +
1.403 + Rooted<ArrayObject*> arr(cx, &obj->as<ArrayObject>());
1.404 + MOZ_ASSERT(arr->lengthIsWritable(),
1.405 + "setter shouldn't be called if property is non-writable");
1.406 + return ArraySetLength<SequentialExecution>(cx, arr, id, JSPROP_PERMANENT, vp, strict);
1.407 +}
1.408 +
1.409 +struct ReverseIndexComparator
1.410 +{
1.411 + bool operator()(const uint32_t& a, const uint32_t& b, bool *lessOrEqualp) {
1.412 + MOZ_ASSERT(a != b, "how'd we get duplicate indexes?");
1.413 + *lessOrEqualp = b <= a;
1.414 + return true;
1.415 + }
1.416 +};
1.417 +
1.418 +template <ExecutionMode mode>
1.419 +bool
1.420 +js::CanonicalizeArrayLengthValue(typename ExecutionModeTraits<mode>::ContextType cx,
1.421 + HandleValue v, uint32_t *newLen)
1.422 +{
1.423 + double d;
1.424 +
1.425 + if (mode == ParallelExecution) {
1.426 + if (v.isObject())
1.427 + return false;
1.428 +
1.429 + if (!NonObjectToUint32(cx, v, newLen))
1.430 + return false;
1.431 +
1.432 + if (!NonObjectToNumber(cx, v, &d))
1.433 + return false;
1.434 + } else {
1.435 + if (!ToUint32(cx->asJSContext(), v, newLen))
1.436 + return false;
1.437 +
1.438 + if (!ToNumber(cx->asJSContext(), v, &d))
1.439 + return false;
1.440 + }
1.441 +
1.442 + if (d == *newLen)
1.443 + return true;
1.444 +
1.445 + if (cx->isJSContext())
1.446 + JS_ReportErrorNumber(cx->asJSContext(), js_GetErrorMessage, nullptr,
1.447 + JSMSG_BAD_ARRAY_LENGTH);
1.448 + return false;
1.449 +}
1.450 +
1.451 +template bool
1.452 +js::CanonicalizeArrayLengthValue<SequentialExecution>(JSContext *cx,
1.453 + HandleValue v, uint32_t *newLen);
1.454 +template bool
1.455 +js::CanonicalizeArrayLengthValue<ParallelExecution>(ForkJoinContext *cx,
1.456 + HandleValue v, uint32_t *newLen);
1.457 +
1.458 +/* ES6 20130308 draft 8.4.2.4 ArraySetLength */
1.459 +template <ExecutionMode mode>
1.460 +bool
1.461 +js::ArraySetLength(typename ExecutionModeTraits<mode>::ContextType cxArg,
1.462 + Handle<ArrayObject*> arr, HandleId id,
1.463 + unsigned attrs, HandleValue value, bool setterIsStrict)
1.464 +{
1.465 + MOZ_ASSERT(cxArg->isThreadLocal(arr));
1.466 + MOZ_ASSERT(id == NameToId(cxArg->names().length));
1.467 +
1.468 + /* Steps 1-2 are irrelevant in our implementation. */
1.469 +
1.470 + /* Steps 3-5. */
1.471 + uint32_t newLen;
1.472 + if (!CanonicalizeArrayLengthValue<mode>(cxArg, value, &newLen))
1.473 + return false;
1.474 +
1.475 + // Abort if we're being asked to change enumerability or configurability.
1.476 + // (The length property of arrays is non-configurable, so such attempts
1.477 + // must fail.) This behavior is spread throughout the ArraySetLength spec
1.478 + // algorithm, but we only need check it once as our array implementation
1.479 + // is internally so different from the spec algorithm. (ES5 and ES6 define
1.480 + // behavior by delegating to the default define-own-property algorithm --
1.481 + // OrdinaryDefineOwnProperty in ES6, the default [[DefineOwnProperty]] in
1.482 + // ES5 -- but we reimplement all the conflict-detection bits ourselves here
1.483 + // so that we can use a customized length representation.)
1.484 + if (!(attrs & JSPROP_PERMANENT) || (attrs & JSPROP_ENUMERATE)) {
1.485 + if (!setterIsStrict)
1.486 + return true;
1.487 + // Bail for strict mode in parallel execution, as we need to go back
1.488 + // to sequential mode to throw the error.
1.489 + if (mode == ParallelExecution)
1.490 + return false;
1.491 + return Throw(cxArg->asJSContext(), id, JSMSG_CANT_REDEFINE_PROP);
1.492 + }
1.493 +
1.494 + /* Steps 6-7. */
1.495 + bool lengthIsWritable = arr->lengthIsWritable();
1.496 +#ifdef DEBUG
1.497 + {
1.498 + RootedShape lengthShape(cxArg, arr->nativeLookupPure(id));
1.499 + MOZ_ASSERT(lengthShape);
1.500 + MOZ_ASSERT(lengthShape->writable() == lengthIsWritable);
1.501 + }
1.502 +#endif
1.503 +
1.504 + uint32_t oldLen = arr->length();
1.505 +
1.506 + /* Steps 8-9 for arrays with non-writable length. */
1.507 + if (!lengthIsWritable) {
1.508 + if (newLen == oldLen)
1.509 + return true;
1.510 +
1.511 + if (!cxArg->isJSContext())
1.512 + return false;
1.513 +
1.514 + if (setterIsStrict) {
1.515 + return JS_ReportErrorFlagsAndNumber(cxArg->asJSContext(),
1.516 + JSREPORT_ERROR, js_GetErrorMessage, nullptr,
1.517 + JSMSG_CANT_REDEFINE_ARRAY_LENGTH);
1.518 + }
1.519 +
1.520 + return JSObject::reportReadOnly(cxArg->asJSContext(), id,
1.521 + JSREPORT_STRICT | JSREPORT_WARNING);
1.522 + }
1.523 +
1.524 + /* Step 8. */
1.525 + bool succeeded = true;
1.526 + do {
1.527 + // The initialized length and capacity of an array only need updating
1.528 + // when non-hole elements are added or removed, which doesn't happen
1.529 + // when array length stays the same or increases.
1.530 + if (newLen >= oldLen)
1.531 + break;
1.532 +
1.533 + // Attempt to propagate dense-element optimization tricks, if possible,
1.534 + // and avoid the generic (and accordingly slow) deletion code below.
1.535 + // We can only do this if there are only densely-indexed elements.
1.536 + // Once there's a sparse indexed element, there's no good way to know,
1.537 + // save by enumerating all the properties to find it. But we *have* to
1.538 + // know in case that sparse indexed element is non-configurable, as
1.539 + // that element must prevent any deletions below it. Bug 586842 should
1.540 + // fix this inefficiency by moving indexed storage to be entirely
1.541 + // separate from non-indexed storage.
1.542 + if (!arr->isIndexed()) {
1.543 + uint32_t oldCapacity = arr->getDenseCapacity();
1.544 + uint32_t oldInitializedLength = arr->getDenseInitializedLength();
1.545 + MOZ_ASSERT(oldCapacity >= oldInitializedLength);
1.546 + if (oldInitializedLength > newLen)
1.547 + arr->setDenseInitializedLength(newLen);
1.548 + if (oldCapacity > newLen)
1.549 + arr->shrinkElements(cxArg, newLen);
1.550 +
1.551 + // We've done the work of deleting any dense elements needing
1.552 + // deletion, and there are no sparse elements. Thus we can skip
1.553 + // straight to defining the length.
1.554 + break;
1.555 + }
1.556 +
1.557 + // Bail from parallel execution if need to perform step 15, which is
1.558 + // unsafe and isn't a common case.
1.559 + if (mode == ParallelExecution)
1.560 + return false;
1.561 +
1.562 + JSContext *cx = cxArg->asJSContext();
1.563 +
1.564 + // Step 15.
1.565 + //
1.566 + // Attempt to delete all elements above the new length, from greatest
1.567 + // to least. If any of these deletions fails, we're supposed to define
1.568 + // the length to one greater than the index that couldn't be deleted,
1.569 + // *with the property attributes specified*. This might convert the
1.570 + // length to be not the value specified, yet non-writable. (You may be
1.571 + // forgiven for thinking these are interesting semantics.) Example:
1.572 + //
1.573 + // var arr =
1.574 + // Object.defineProperty([0, 1, 2, 3], 1, { writable: false });
1.575 + // Object.defineProperty(arr, "length",
1.576 + // { value: 0, writable: false });
1.577 + //
1.578 + // will convert |arr| to an array of non-writable length two, then
1.579 + // throw a TypeError.
1.580 + //
1.581 + // We implement this behavior, in the relevant lops below, by setting
1.582 + // |succeeded| to false. Then we exit the loop, define the length
1.583 + // appropriately, and only then throw a TypeError, if necessary.
1.584 + uint32_t gap = oldLen - newLen;
1.585 + const uint32_t RemoveElementsFastLimit = 1 << 24;
1.586 + if (gap < RemoveElementsFastLimit) {
1.587 + // If we're removing a relatively small number of elements, just do
1.588 + // it exactly by the spec.
1.589 + while (newLen < oldLen) {
1.590 + /* Step 15a. */
1.591 + oldLen--;
1.592 +
1.593 + /* Steps 15b-d. */
1.594 + bool deleteSucceeded;
1.595 + if (!JSObject::deleteElement(cx, arr, oldLen, &deleteSucceeded))
1.596 + return false;
1.597 + if (!deleteSucceeded) {
1.598 + newLen = oldLen + 1;
1.599 + succeeded = false;
1.600 + break;
1.601 + }
1.602 + }
1.603 + } else {
1.604 + // If we're removing a large number of elements from an array
1.605 + // that's probably sparse, try a different tack. Get all the own
1.606 + // property names, sift out the indexes in the deletion range into
1.607 + // a vector, sort the vector greatest to least, then delete the
1.608 + // indexes greatest to least using that vector. See bug 322135.
1.609 + //
1.610 + // This heuristic's kind of a huge guess -- "large number of
1.611 + // elements" and "probably sparse" are completely unprincipled
1.612 + // predictions. In the long run, bug 586842 will support the right
1.613 + // fix: store sparse elements in a sorted data structure that
1.614 + // permits fast in-reverse-order traversal and concurrent removals.
1.615 +
1.616 + Vector<uint32_t> indexes(cx);
1.617 + {
1.618 + AutoIdVector props(cx);
1.619 + if (!GetPropertyNames(cx, arr, JSITER_OWNONLY | JSITER_HIDDEN, &props))
1.620 + return false;
1.621 +
1.622 + for (size_t i = 0; i < props.length(); i++) {
1.623 + if (!CheckForInterrupt(cx))
1.624 + return false;
1.625 +
1.626 + uint32_t index;
1.627 + if (!js_IdIsIndex(props[i], &index))
1.628 + continue;
1.629 +
1.630 + if (index >= newLen && index < oldLen) {
1.631 + if (!indexes.append(index))
1.632 + return false;
1.633 + }
1.634 + }
1.635 + }
1.636 +
1.637 + uint32_t count = indexes.length();
1.638 + {
1.639 + // We should use radix sort to be O(n), but this is uncommon
1.640 + // enough that we'll punt til someone complains.
1.641 + Vector<uint32_t> scratch(cx);
1.642 + if (!scratch.resize(count))
1.643 + return false;
1.644 + MOZ_ALWAYS_TRUE(MergeSort(indexes.begin(), count, scratch.begin(),
1.645 + ReverseIndexComparator()));
1.646 + }
1.647 +
1.648 + uint32_t index = UINT32_MAX;
1.649 + for (uint32_t i = 0; i < count; i++) {
1.650 + MOZ_ASSERT(indexes[i] < index, "indexes should never repeat");
1.651 + index = indexes[i];
1.652 +
1.653 + /* Steps 15b-d. */
1.654 + bool deleteSucceeded;
1.655 + if (!JSObject::deleteElement(cx, arr, index, &deleteSucceeded))
1.656 + return false;
1.657 + if (!deleteSucceeded) {
1.658 + newLen = index + 1;
1.659 + succeeded = false;
1.660 + break;
1.661 + }
1.662 + }
1.663 + }
1.664 + } while (false);
1.665 +
1.666 + /* Steps 12, 16. */
1.667 +
1.668 + // Yes, we totally drop a non-stub getter/setter from a defineProperty
1.669 + // API call on the floor here. Given that getter/setter will go away in
1.670 + // the long run, with accessors replacing them both internally and at the
1.671 + // API level, just run with this.
1.672 + RootedShape lengthShape(cxArg, mode == ParallelExecution
1.673 + ? arr->nativeLookupPure(id)
1.674 + : arr->nativeLookup(cxArg->asJSContext(), id));
1.675 + if (!JSObject::changeProperty<mode>(cxArg, arr, lengthShape, attrs,
1.676 + JSPROP_PERMANENT | JSPROP_READONLY | JSPROP_SHARED,
1.677 + array_length_getter, array_length_setter))
1.678 + {
1.679 + return false;
1.680 + }
1.681 +
1.682 + if (mode == ParallelExecution) {
1.683 + // Overflowing int32 requires changing TI state.
1.684 + if (newLen > INT32_MAX)
1.685 + return false;
1.686 + arr->setLengthInt32(newLen);
1.687 + } else {
1.688 + JSContext *cx = cxArg->asJSContext();
1.689 + arr->setLength(cx, newLen);
1.690 + }
1.691 +
1.692 +
1.693 + // All operations past here until the |!succeeded| code must be infallible,
1.694 + // so that all element fields remain properly synchronized.
1.695 +
1.696 + // Trim the initialized length, if needed, to preserve the <= length
1.697 + // invariant. (Capacity was already reduced during element deletion, if
1.698 + // necessary.)
1.699 + ObjectElements *header = arr->getElementsHeader();
1.700 + header->initializedLength = Min(header->initializedLength, newLen);
1.701 +
1.702 + if (attrs & JSPROP_READONLY) {
1.703 + header->setNonwritableArrayLength();
1.704 +
1.705 + // When an array's length becomes non-writable, writes to indexes
1.706 + // greater than or equal to the length don't change the array. We
1.707 + // handle this with a check for non-writable length in most places.
1.708 + // But in JIT code every check counts -- so we piggyback the check on
1.709 + // the already-required range check for |index < capacity| by making
1.710 + // capacity of arrays with non-writable length never exceed the length.
1.711 + if (arr->getDenseCapacity() > newLen) {
1.712 + arr->shrinkElements(cxArg, newLen);
1.713 + arr->getElementsHeader()->capacity = newLen;
1.714 + }
1.715 + }
1.716 +
1.717 + if (setterIsStrict && !succeeded) {
1.718 + // We can't have arrived here under ParallelExecution, as we have
1.719 + // returned from the function before step 15 above.
1.720 + JSContext *cx = cxArg->asJSContext();
1.721 + RootedId elementId(cx);
1.722 + if (!IndexToId(cx, newLen - 1, &elementId))
1.723 + return false;
1.724 + return arr->reportNotConfigurable(cx, elementId);
1.725 + }
1.726 +
1.727 + return true;
1.728 +}
1.729 +
1.730 +template bool
1.731 +js::ArraySetLength<SequentialExecution>(JSContext *cx, Handle<ArrayObject*> arr,
1.732 + HandleId id, unsigned attrs, HandleValue value,
1.733 + bool setterIsStrict);
1.734 +template bool
1.735 +js::ArraySetLength<ParallelExecution>(ForkJoinContext *cx, Handle<ArrayObject*> arr,
1.736 + HandleId id, unsigned attrs, HandleValue value,
1.737 + bool setterIsStrict);
1.738 +
1.739 +bool
1.740 +js::WouldDefinePastNonwritableLength(ThreadSafeContext *cx,
1.741 + HandleObject obj, uint32_t index, bool strict,
1.742 + bool *definesPast)
1.743 +{
1.744 + if (!obj->is<ArrayObject>()) {
1.745 + *definesPast = false;
1.746 + return true;
1.747 + }
1.748 +
1.749 + Rooted<ArrayObject*> arr(cx, &obj->as<ArrayObject>());
1.750 + uint32_t length = arr->length();
1.751 + if (index < length) {
1.752 + *definesPast = false;
1.753 + return true;
1.754 + }
1.755 +
1.756 + if (arr->lengthIsWritable()) {
1.757 + *definesPast = false;
1.758 + return true;
1.759 + }
1.760 +
1.761 + *definesPast = true;
1.762 +
1.763 + // Error in strict mode code or warn with strict option.
1.764 + unsigned flags = strict ? JSREPORT_ERROR : (JSREPORT_STRICT | JSREPORT_WARNING);
1.765 + if (cx->isForkJoinContext())
1.766 + return cx->asForkJoinContext()->reportError(ParallelBailoutUnsupportedVM, flags);
1.767 +
1.768 + if (!cx->isJSContext())
1.769 + return true;
1.770 +
1.771 + JSContext *ncx = cx->asJSContext();
1.772 +
1.773 + if (!strict && !ncx->options().extraWarnings())
1.774 + return true;
1.775 +
1.776 + // XXX include the index and maybe array length in the error message
1.777 + return JS_ReportErrorFlagsAndNumber(ncx, flags, js_GetErrorMessage, nullptr,
1.778 + JSMSG_CANT_DEFINE_PAST_ARRAY_LENGTH);
1.779 +}
1.780 +
1.781 +static bool
1.782 +array_addProperty(JSContext *cx, HandleObject obj, HandleId id, MutableHandleValue vp)
1.783 +{
1.784 + Rooted<ArrayObject*> arr(cx, &obj->as<ArrayObject>());
1.785 +
1.786 + uint32_t index;
1.787 + if (!js_IdIsIndex(id, &index))
1.788 + return true;
1.789 +
1.790 + uint32_t length = arr->length();
1.791 + if (index >= length) {
1.792 + MOZ_ASSERT(arr->lengthIsWritable(),
1.793 + "how'd this element get added if length is non-writable?");
1.794 + arr->setLength(cx, index + 1);
1.795 + }
1.796 + return true;
1.797 +}
1.798 +
1.799 +bool
1.800 +js::ObjectMayHaveExtraIndexedProperties(JSObject *obj)
1.801 +{
1.802 + /*
1.803 + * Whether obj may have indexed properties anywhere besides its dense
1.804 + * elements. This includes other indexed properties in its shape hierarchy,
1.805 + * and indexed properties or elements along its prototype chain.
1.806 + */
1.807 +
1.808 + JS_ASSERT(obj->isNative());
1.809 +
1.810 + if (obj->isIndexed())
1.811 + return true;
1.812 +
1.813 + /*
1.814 + * Walk up the prototype chain and see if this indexed element already
1.815 + * exists. If we hit the end of the prototype chain, it's safe to set the
1.816 + * element on the original object.
1.817 + */
1.818 + while ((obj = obj->getProto()) != nullptr) {
1.819 + /*
1.820 + * If the prototype is a non-native object (possibly a dense array), or
1.821 + * a native object (possibly a slow array) that has indexed properties,
1.822 + * return true.
1.823 + */
1.824 + if (!obj->isNative())
1.825 + return true;
1.826 + if (obj->isIndexed())
1.827 + return true;
1.828 + if (obj->getDenseInitializedLength() > 0)
1.829 + return true;
1.830 + if (obj->is<TypedArrayObject>())
1.831 + return true;
1.832 + }
1.833 +
1.834 + return false;
1.835 +}
1.836 +
1.837 +const Class ArrayObject::class_ = {
1.838 + "Array",
1.839 + JSCLASS_HAS_CACHED_PROTO(JSProto_Array),
1.840 + array_addProperty,
1.841 + JS_DeletePropertyStub, /* delProperty */
1.842 + JS_PropertyStub, /* getProperty */
1.843 + JS_StrictPropertyStub, /* setProperty */
1.844 + JS_EnumerateStub,
1.845 + JS_ResolveStub,
1.846 + JS_ConvertStub,
1.847 + nullptr,
1.848 + nullptr, /* call */
1.849 + nullptr, /* hasInstance */
1.850 + nullptr, /* construct */
1.851 + nullptr /* trace */
1.852 +};
1.853 +
1.854 +static bool
1.855 +AddLengthProperty(ExclusiveContext *cx, HandleObject obj)
1.856 +{
1.857 + /*
1.858 + * Add the 'length' property for a newly created array,
1.859 + * and update the elements to be an empty array owned by the object.
1.860 + * The shared emptyObjectElements singleton cannot be used for slow arrays,
1.861 + * as accesses to 'length' will use the elements header.
1.862 + */
1.863 +
1.864 + RootedId lengthId(cx, NameToId(cx->names().length));
1.865 + JS_ASSERT(!obj->nativeLookup(cx, lengthId));
1.866 +
1.867 + return JSObject::addProperty(cx, obj, lengthId, array_length_getter, array_length_setter,
1.868 + SHAPE_INVALID_SLOT, JSPROP_PERMANENT | JSPROP_SHARED, 0,
1.869 + /* allowDictionary = */ false);
1.870 +}
1.871 +
1.872 +#if JS_HAS_TOSOURCE
1.873 +MOZ_ALWAYS_INLINE bool
1.874 +IsArray(HandleValue v)
1.875 +{
1.876 + return v.isObject() && v.toObject().is<ArrayObject>();
1.877 +}
1.878 +
1.879 +MOZ_ALWAYS_INLINE bool
1.880 +array_toSource_impl(JSContext *cx, CallArgs args)
1.881 +{
1.882 + JS_ASSERT(IsArray(args.thisv()));
1.883 +
1.884 + Rooted<JSObject*> obj(cx, &args.thisv().toObject());
1.885 + RootedValue elt(cx);
1.886 +
1.887 + AutoCycleDetector detector(cx, obj);
1.888 + if (!detector.init())
1.889 + return false;
1.890 +
1.891 + StringBuffer sb(cx);
1.892 +
1.893 + if (detector.foundCycle()) {
1.894 + if (!sb.append("[]"))
1.895 + return false;
1.896 + goto make_string;
1.897 + }
1.898 +
1.899 + if (!sb.append('['))
1.900 + return false;
1.901 +
1.902 + uint32_t length;
1.903 + if (!GetLengthProperty(cx, obj, &length))
1.904 + return false;
1.905 +
1.906 + for (uint32_t index = 0; index < length; index++) {
1.907 + bool hole;
1.908 + if (!CheckForInterrupt(cx) ||
1.909 + !GetElement(cx, obj, index, &hole, &elt)) {
1.910 + return false;
1.911 + }
1.912 +
1.913 + /* Get element's character string. */
1.914 + JSString *str;
1.915 + if (hole) {
1.916 + str = cx->runtime()->emptyString;
1.917 + } else {
1.918 + str = ValueToSource(cx, elt);
1.919 + if (!str)
1.920 + return false;
1.921 + }
1.922 +
1.923 + /* Append element to buffer. */
1.924 + if (!sb.append(str))
1.925 + return false;
1.926 + if (index + 1 != length) {
1.927 + if (!sb.append(", "))
1.928 + return false;
1.929 + } else if (hole) {
1.930 + if (!sb.append(','))
1.931 + return false;
1.932 + }
1.933 + }
1.934 +
1.935 + /* Finalize the buffer. */
1.936 + if (!sb.append(']'))
1.937 + return false;
1.938 +
1.939 + make_string:
1.940 + JSString *str = sb.finishString();
1.941 + if (!str)
1.942 + return false;
1.943 +
1.944 + args.rval().setString(str);
1.945 + return true;
1.946 +}
1.947 +
1.948 +static bool
1.949 +array_toSource(JSContext *cx, unsigned argc, Value *vp)
1.950 +{
1.951 + JS_CHECK_RECURSION(cx, return false);
1.952 + CallArgs args = CallArgsFromVp(argc, vp);
1.953 + return CallNonGenericMethod<IsArray, array_toSource_impl>(cx, args);
1.954 +}
1.955 +#endif
1.956 +
1.957 +struct EmptySeparatorOp
1.958 +{
1.959 + bool operator()(JSContext *, StringBuffer &sb) { return true; }
1.960 +};
1.961 +
1.962 +struct CharSeparatorOp
1.963 +{
1.964 + jschar sep;
1.965 + CharSeparatorOp(jschar sep) : sep(sep) {};
1.966 + bool operator()(JSContext *, StringBuffer &sb) { return sb.append(sep); }
1.967 +};
1.968 +
1.969 +struct StringSeparatorOp
1.970 +{
1.971 + const jschar *sepchars;
1.972 + size_t seplen;
1.973 +
1.974 + StringSeparatorOp(const jschar *sepchars, size_t seplen)
1.975 + : sepchars(sepchars), seplen(seplen) {};
1.976 +
1.977 + bool operator()(JSContext *cx, StringBuffer &sb) {
1.978 + return sb.append(sepchars, seplen);
1.979 + }
1.980 +};
1.981 +
1.982 +template <bool Locale, typename SeparatorOp>
1.983 +static bool
1.984 +ArrayJoinKernel(JSContext *cx, SeparatorOp sepOp, HandleObject obj, uint32_t length,
1.985 + StringBuffer &sb)
1.986 +{
1.987 + uint32_t i = 0;
1.988 +
1.989 + if (!Locale && obj->is<ArrayObject>() && !ObjectMayHaveExtraIndexedProperties(obj)) {
1.990 + // This loop handles all elements up to initializedLength. If
1.991 + // length > initLength we rely on the second loop to add the
1.992 + // other elements.
1.993 + uint32_t initLength = obj->getDenseInitializedLength();
1.994 + while (i < initLength) {
1.995 + if (!CheckForInterrupt(cx))
1.996 + return false;
1.997 +
1.998 + const Value &elem = obj->getDenseElement(i);
1.999 +
1.1000 + if (elem.isString()) {
1.1001 + if (!sb.append(elem.toString()))
1.1002 + return false;
1.1003 + } else if (elem.isNumber()) {
1.1004 + if (!NumberValueToStringBuffer(cx, elem, sb))
1.1005 + return false;
1.1006 + } else if (elem.isBoolean()) {
1.1007 + if (!BooleanToStringBuffer(elem.toBoolean(), sb))
1.1008 + return false;
1.1009 + } else if (elem.isObject()) {
1.1010 + /*
1.1011 + * Object stringifying could modify the initialized length or make
1.1012 + * the array sparse. Delegate it to a separate loop to keep this
1.1013 + * one tight.
1.1014 + */
1.1015 + break;
1.1016 + } else {
1.1017 + JS_ASSERT(elem.isMagic(JS_ELEMENTS_HOLE) || elem.isNullOrUndefined());
1.1018 + }
1.1019 +
1.1020 + if (++i != length && !sepOp(cx, sb))
1.1021 + return false;
1.1022 + }
1.1023 + }
1.1024 +
1.1025 + if (i != length) {
1.1026 + RootedValue v(cx);
1.1027 + while (i < length) {
1.1028 + if (!CheckForInterrupt(cx))
1.1029 + return false;
1.1030 +
1.1031 + bool hole;
1.1032 + if (!GetElement(cx, obj, i, &hole, &v))
1.1033 + return false;
1.1034 + if (!hole && !v.isNullOrUndefined()) {
1.1035 + if (Locale) {
1.1036 + JSObject *robj = ToObject(cx, v);
1.1037 + if (!robj)
1.1038 + return false;
1.1039 + RootedId id(cx, NameToId(cx->names().toLocaleString));
1.1040 + if (!robj->callMethod(cx, id, 0, nullptr, &v))
1.1041 + return false;
1.1042 + }
1.1043 + if (!ValueToStringBuffer(cx, v, sb))
1.1044 + return false;
1.1045 + }
1.1046 +
1.1047 + if (++i != length && !sepOp(cx, sb))
1.1048 + return false;
1.1049 + }
1.1050 + }
1.1051 +
1.1052 + return true;
1.1053 +}
1.1054 +
1.1055 +template <bool Locale>
1.1056 +static bool
1.1057 +ArrayJoin(JSContext *cx, CallArgs &args)
1.1058 +{
1.1059 + // This method is shared by Array.prototype.join and
1.1060 + // Array.prototype.toLocaleString. The steps in ES5 are nearly the same, so
1.1061 + // the annotations in this function apply to both toLocaleString and join.
1.1062 +
1.1063 + // Step 1
1.1064 + RootedObject obj(cx, ToObject(cx, args.thisv()));
1.1065 + if (!obj)
1.1066 + return false;
1.1067 +
1.1068 + AutoCycleDetector detector(cx, obj);
1.1069 + if (!detector.init())
1.1070 + return false;
1.1071 +
1.1072 + if (detector.foundCycle()) {
1.1073 + args.rval().setString(cx->names().empty);
1.1074 + return true;
1.1075 + }
1.1076 +
1.1077 + // Steps 2 and 3
1.1078 + uint32_t length;
1.1079 + if (!GetLengthProperty(cx, obj, &length))
1.1080 + return false;
1.1081 +
1.1082 + // Steps 4 and 5
1.1083 + RootedString sepstr(cx, nullptr);
1.1084 + const jschar *sepchars;
1.1085 + size_t seplen;
1.1086 + if (!Locale && args.hasDefined(0)) {
1.1087 + sepstr = ToString<CanGC>(cx, args[0]);
1.1088 + if (!sepstr)
1.1089 + return false;
1.1090 + sepchars = sepstr->getChars(cx);
1.1091 + if (!sepchars)
1.1092 + return false;
1.1093 + seplen = sepstr->length();
1.1094 + } else {
1.1095 + HandlePropertyName comma = cx->names().comma;
1.1096 + sepstr = comma;
1.1097 + sepchars = comma->chars();
1.1098 + seplen = comma->length();
1.1099 + }
1.1100 +
1.1101 + JS::Anchor<JSString*> anchor(sepstr);
1.1102 +
1.1103 + // Step 6 is implicit in the loops below.
1.1104 +
1.1105 + // An optimized version of a special case of steps 7-11: when length==1 and
1.1106 + // the 0th element is a string, ToString() of that element is a no-op and
1.1107 + // so it can be immediately returned as the result.
1.1108 + if (length == 1 && !Locale && obj->is<ArrayObject>() &&
1.1109 + obj->getDenseInitializedLength() == 1)
1.1110 + {
1.1111 + const Value &elem0 = obj->getDenseElement(0);
1.1112 + if (elem0.isString()) {
1.1113 + args.rval().setString(elem0.toString());
1.1114 + return true;
1.1115 + }
1.1116 + }
1.1117 +
1.1118 + StringBuffer sb(cx);
1.1119 +
1.1120 + // The separator will be added |length - 1| times, reserve space for that
1.1121 + // so that we don't have to unnecessarily grow the buffer.
1.1122 + if (length > 0 && !sb.reserve(seplen * (length - 1)))
1.1123 + return false;
1.1124 +
1.1125 + // Various optimized versions of steps 7-10.
1.1126 + if (seplen == 0) {
1.1127 + EmptySeparatorOp op;
1.1128 + if (!ArrayJoinKernel<Locale>(cx, op, obj, length, sb))
1.1129 + return false;
1.1130 + } else if (seplen == 1) {
1.1131 + CharSeparatorOp op(sepchars[0]);
1.1132 + if (!ArrayJoinKernel<Locale>(cx, op, obj, length, sb))
1.1133 + return false;
1.1134 + } else {
1.1135 + StringSeparatorOp op(sepchars, seplen);
1.1136 + if (!ArrayJoinKernel<Locale>(cx, op, obj, length, sb))
1.1137 + return false;
1.1138 + }
1.1139 +
1.1140 + // Step 11
1.1141 + JSString *str = sb.finishString();
1.1142 + if (!str)
1.1143 + return false;
1.1144 + args.rval().setString(str);
1.1145 + return true;
1.1146 +}
1.1147 +
1.1148 +/* ES5 15.4.4.2. NB: The algorithm here differs from the one in ES3. */
1.1149 +static bool
1.1150 +array_toString(JSContext *cx, unsigned argc, Value *vp)
1.1151 +{
1.1152 + JS_CHECK_RECURSION(cx, return false);
1.1153 +
1.1154 + CallArgs args = CallArgsFromVp(argc, vp);
1.1155 + RootedObject obj(cx, ToObject(cx, args.thisv()));
1.1156 + if (!obj)
1.1157 + return false;
1.1158 +
1.1159 + RootedValue join(cx, args.calleev());
1.1160 + if (!JSObject::getProperty(cx, obj, obj, cx->names().join, &join))
1.1161 + return false;
1.1162 +
1.1163 + if (!js_IsCallable(join)) {
1.1164 + JSString *str = JS_BasicObjectToString(cx, obj);
1.1165 + if (!str)
1.1166 + return false;
1.1167 + args.rval().setString(str);
1.1168 + return true;
1.1169 + }
1.1170 +
1.1171 + InvokeArgs args2(cx);
1.1172 + if (!args2.init(0))
1.1173 + return false;
1.1174 +
1.1175 + args2.setCallee(join);
1.1176 + args2.setThis(ObjectValue(*obj));
1.1177 +
1.1178 + /* Do the call. */
1.1179 + if (!Invoke(cx, args2))
1.1180 + return false;
1.1181 + args.rval().set(args2.rval());
1.1182 + return true;
1.1183 +}
1.1184 +
1.1185 +/* ES5 15.4.4.3 */
1.1186 +static bool
1.1187 +array_toLocaleString(JSContext *cx, unsigned argc, Value *vp)
1.1188 +{
1.1189 + JS_CHECK_RECURSION(cx, return false);
1.1190 +
1.1191 + CallArgs args = CallArgsFromVp(argc, vp);
1.1192 + return ArrayJoin<true>(cx, args);
1.1193 +}
1.1194 +
1.1195 +/* ES5 15.4.4.5 */
1.1196 +static bool
1.1197 +array_join(JSContext *cx, unsigned argc, Value *vp)
1.1198 +{
1.1199 + JS_CHECK_RECURSION(cx, return false);
1.1200 +
1.1201 + CallArgs args = CallArgsFromVp(argc, vp);
1.1202 + return ArrayJoin<false>(cx, args);
1.1203 +}
1.1204 +
1.1205 +static inline bool
1.1206 +InitArrayTypes(JSContext *cx, TypeObject *type, const Value *vector, unsigned count)
1.1207 +{
1.1208 + if (!type->unknownProperties()) {
1.1209 + AutoEnterAnalysis enter(cx);
1.1210 +
1.1211 + HeapTypeSet *types = type->getProperty(cx, JSID_VOID);
1.1212 + if (!types)
1.1213 + return false;
1.1214 +
1.1215 + for (unsigned i = 0; i < count; i++) {
1.1216 + if (vector[i].isMagic(JS_ELEMENTS_HOLE))
1.1217 + continue;
1.1218 + Type valtype = GetValueType(vector[i]);
1.1219 + types->addType(cx, valtype);
1.1220 + }
1.1221 + }
1.1222 + return true;
1.1223 +}
1.1224 +
1.1225 +enum ShouldUpdateTypes
1.1226 +{
1.1227 + UpdateTypes = true,
1.1228 + DontUpdateTypes = false
1.1229 +};
1.1230 +
1.1231 +/* vector must point to rooted memory. */
1.1232 +static bool
1.1233 +InitArrayElements(JSContext *cx, HandleObject obj, uint32_t start, uint32_t count, const Value *vector, ShouldUpdateTypes updateTypes)
1.1234 +{
1.1235 + JS_ASSERT(count <= MAX_ARRAY_INDEX);
1.1236 +
1.1237 + if (count == 0)
1.1238 + return true;
1.1239 +
1.1240 + types::TypeObject *type = obj->getType(cx);
1.1241 + if (!type)
1.1242 + return false;
1.1243 + if (updateTypes && !InitArrayTypes(cx, type, vector, count))
1.1244 + return false;
1.1245 +
1.1246 + /*
1.1247 + * Optimize for dense arrays so long as adding the given set of elements
1.1248 + * wouldn't otherwise make the array slow or exceed a non-writable array
1.1249 + * length.
1.1250 + */
1.1251 + do {
1.1252 + if (!obj->is<ArrayObject>())
1.1253 + break;
1.1254 + if (ObjectMayHaveExtraIndexedProperties(obj))
1.1255 + break;
1.1256 +
1.1257 + if (obj->shouldConvertDoubleElements())
1.1258 + break;
1.1259 +
1.1260 + Rooted<ArrayObject*> arr(cx, &obj->as<ArrayObject>());
1.1261 +
1.1262 + if (!arr->lengthIsWritable() && start + count > arr->length())
1.1263 + break;
1.1264 +
1.1265 + JSObject::EnsureDenseResult result = arr->ensureDenseElements(cx, start, count);
1.1266 + if (result != JSObject::ED_OK) {
1.1267 + if (result == JSObject::ED_FAILED)
1.1268 + return false;
1.1269 + JS_ASSERT(result == JSObject::ED_SPARSE);
1.1270 + break;
1.1271 + }
1.1272 +
1.1273 + uint32_t newlen = start + count;
1.1274 + if (newlen > arr->length())
1.1275 + arr->setLengthInt32(newlen);
1.1276 +
1.1277 + JS_ASSERT(count < UINT32_MAX / sizeof(Value));
1.1278 + arr->copyDenseElements(start, vector, count);
1.1279 + JS_ASSERT_IF(count != 0, !arr->getDenseElement(newlen - 1).isMagic(JS_ELEMENTS_HOLE));
1.1280 + return true;
1.1281 + } while (false);
1.1282 +
1.1283 + const Value* end = vector + count;
1.1284 + while (vector < end && start <= MAX_ARRAY_INDEX) {
1.1285 + if (!CheckForInterrupt(cx) ||
1.1286 + !SetArrayElement(cx, obj, start++, HandleValue::fromMarkedLocation(vector++))) {
1.1287 + return false;
1.1288 + }
1.1289 + }
1.1290 +
1.1291 + if (vector == end)
1.1292 + return true;
1.1293 +
1.1294 + JS_ASSERT(start == MAX_ARRAY_INDEX + 1);
1.1295 + RootedValue value(cx);
1.1296 + RootedId id(cx);
1.1297 + RootedValue indexv(cx);
1.1298 + double index = MAX_ARRAY_INDEX + 1;
1.1299 + do {
1.1300 + value = *vector++;
1.1301 + indexv = DoubleValue(index);
1.1302 + if (!ValueToId<CanGC>(cx, indexv, &id) ||
1.1303 + !JSObject::setGeneric(cx, obj, obj, id, &value, true))
1.1304 + {
1.1305 + return false;
1.1306 + }
1.1307 + index += 1;
1.1308 + } while (vector != end);
1.1309 +
1.1310 + return true;
1.1311 +}
1.1312 +
1.1313 +static bool
1.1314 +array_reverse(JSContext *cx, unsigned argc, Value *vp)
1.1315 +{
1.1316 + CallArgs args = CallArgsFromVp(argc, vp);
1.1317 + RootedObject obj(cx, ToObject(cx, args.thisv()));
1.1318 + if (!obj)
1.1319 + return false;
1.1320 +
1.1321 + uint32_t len;
1.1322 + if (!GetLengthProperty(cx, obj, &len))
1.1323 + return false;
1.1324 +
1.1325 + do {
1.1326 + if (!obj->is<ArrayObject>())
1.1327 + break;
1.1328 + if (ObjectMayHaveExtraIndexedProperties(obj))
1.1329 + break;
1.1330 +
1.1331 + /* An empty array or an array with no elements is already reversed. */
1.1332 + if (len == 0 || obj->getDenseCapacity() == 0) {
1.1333 + args.rval().setObject(*obj);
1.1334 + return true;
1.1335 + }
1.1336 +
1.1337 + /*
1.1338 + * It's actually surprisingly complicated to reverse an array due to the
1.1339 + * orthogonality of array length and array capacity while handling
1.1340 + * leading and trailing holes correctly. Reversing seems less likely to
1.1341 + * be a common operation than other array mass-mutation methods, so for
1.1342 + * now just take a probably-small memory hit (in the absence of too many
1.1343 + * holes in the array at its start) and ensure that the capacity is
1.1344 + * sufficient to hold all the elements in the array if it were full.
1.1345 + */
1.1346 + JSObject::EnsureDenseResult result = obj->ensureDenseElements(cx, len, 0);
1.1347 + if (result != JSObject::ED_OK) {
1.1348 + if (result == JSObject::ED_FAILED)
1.1349 + return false;
1.1350 + JS_ASSERT(result == JSObject::ED_SPARSE);
1.1351 + break;
1.1352 + }
1.1353 +
1.1354 + /* Fill out the array's initialized length to its proper length. */
1.1355 + obj->ensureDenseInitializedLength(cx, len, 0);
1.1356 +
1.1357 + RootedValue origlo(cx), orighi(cx);
1.1358 +
1.1359 + uint32_t lo = 0, hi = len - 1;
1.1360 + for (; lo < hi; lo++, hi--) {
1.1361 + origlo = obj->getDenseElement(lo);
1.1362 + orighi = obj->getDenseElement(hi);
1.1363 + obj->setDenseElement(lo, orighi);
1.1364 + if (orighi.isMagic(JS_ELEMENTS_HOLE) &&
1.1365 + !js_SuppressDeletedProperty(cx, obj, INT_TO_JSID(lo))) {
1.1366 + return false;
1.1367 + }
1.1368 + obj->setDenseElement(hi, origlo);
1.1369 + if (origlo.isMagic(JS_ELEMENTS_HOLE) &&
1.1370 + !js_SuppressDeletedProperty(cx, obj, INT_TO_JSID(hi))) {
1.1371 + return false;
1.1372 + }
1.1373 + }
1.1374 +
1.1375 + /*
1.1376 + * Per ECMA-262, don't update the length of the array, even if the new
1.1377 + * array has trailing holes (and thus the original array began with
1.1378 + * holes).
1.1379 + */
1.1380 + args.rval().setObject(*obj);
1.1381 + return true;
1.1382 + } while (false);
1.1383 +
1.1384 + RootedValue lowval(cx), hival(cx);
1.1385 + for (uint32_t i = 0, half = len / 2; i < half; i++) {
1.1386 + bool hole, hole2;
1.1387 + if (!CheckForInterrupt(cx) ||
1.1388 + !GetElement(cx, obj, i, &hole, &lowval) ||
1.1389 + !GetElement(cx, obj, len - i - 1, &hole2, &hival))
1.1390 + {
1.1391 + return false;
1.1392 + }
1.1393 +
1.1394 + if (!hole && !hole2) {
1.1395 + if (!SetArrayElement(cx, obj, i, hival))
1.1396 + return false;
1.1397 + if (!SetArrayElement(cx, obj, len - i - 1, lowval))
1.1398 + return false;
1.1399 + } else if (hole && !hole2) {
1.1400 + if (!SetArrayElement(cx, obj, i, hival))
1.1401 + return false;
1.1402 + if (!DeletePropertyOrThrow(cx, obj, len - i - 1))
1.1403 + return false;
1.1404 + } else if (!hole && hole2) {
1.1405 + if (!DeletePropertyOrThrow(cx, obj, i))
1.1406 + return false;
1.1407 + if (!SetArrayElement(cx, obj, len - i - 1, lowval))
1.1408 + return false;
1.1409 + } else {
1.1410 + // No action required.
1.1411 + }
1.1412 + }
1.1413 + args.rval().setObject(*obj);
1.1414 + return true;
1.1415 +}
1.1416 +
1.1417 +namespace {
1.1418 +
1.1419 +inline bool
1.1420 +CompareStringValues(JSContext *cx, const Value &a, const Value &b, bool *lessOrEqualp)
1.1421 +{
1.1422 + if (!CheckForInterrupt(cx))
1.1423 + return false;
1.1424 +
1.1425 + JSString *astr = a.toString();
1.1426 + JSString *bstr = b.toString();
1.1427 + int32_t result;
1.1428 + if (!CompareStrings(cx, astr, bstr, &result))
1.1429 + return false;
1.1430 +
1.1431 + *lessOrEqualp = (result <= 0);
1.1432 + return true;
1.1433 +}
1.1434 +
1.1435 +static const uint64_t powersOf10[] = {
1.1436 + 1, 10, 100, 1000, 10000, 100000, 1000000, 10000000, 100000000, 1000000000, 1000000000000ULL
1.1437 +};
1.1438 +
1.1439 +static inline unsigned
1.1440 +NumDigitsBase10(uint32_t n)
1.1441 +{
1.1442 + /*
1.1443 + * This is just floor_log10(n) + 1
1.1444 + * Algorithm taken from
1.1445 + * http://graphics.stanford.edu/~seander/bithacks.html#IntegerLog10
1.1446 + */
1.1447 + uint32_t log2 = CeilingLog2(n);
1.1448 + uint32_t t = log2 * 1233 >> 12;
1.1449 + return t - (n < powersOf10[t]) + 1;
1.1450 +}
1.1451 +
1.1452 +static inline bool
1.1453 +CompareLexicographicInt32(const Value &a, const Value &b, bool *lessOrEqualp)
1.1454 +{
1.1455 + int32_t aint = a.toInt32();
1.1456 + int32_t bint = b.toInt32();
1.1457 +
1.1458 + /*
1.1459 + * If both numbers are equal ... trivial
1.1460 + * If only one of both is negative --> arithmetic comparison as char code
1.1461 + * of '-' is always less than any other digit
1.1462 + * If both numbers are negative convert them to positive and continue
1.1463 + * handling ...
1.1464 + */
1.1465 + if (aint == bint) {
1.1466 + *lessOrEqualp = true;
1.1467 + } else if ((aint < 0) && (bint >= 0)) {
1.1468 + *lessOrEqualp = true;
1.1469 + } else if ((aint >= 0) && (bint < 0)) {
1.1470 + *lessOrEqualp = false;
1.1471 + } else {
1.1472 + uint32_t auint = Abs(aint);
1.1473 + uint32_t buint = Abs(bint);
1.1474 +
1.1475 + /*
1.1476 + * ... get number of digits of both integers.
1.1477 + * If they have the same number of digits --> arithmetic comparison.
1.1478 + * If digits_a > digits_b: a < b*10e(digits_a - digits_b).
1.1479 + * If digits_b > digits_a: a*10e(digits_b - digits_a) <= b.
1.1480 + */
1.1481 + unsigned digitsa = NumDigitsBase10(auint);
1.1482 + unsigned digitsb = NumDigitsBase10(buint);
1.1483 + if (digitsa == digitsb) {
1.1484 + *lessOrEqualp = (auint <= buint);
1.1485 + } else if (digitsa > digitsb) {
1.1486 + JS_ASSERT((digitsa - digitsb) < ArrayLength(powersOf10));
1.1487 + *lessOrEqualp = (uint64_t(auint) < uint64_t(buint) * powersOf10[digitsa - digitsb]);
1.1488 + } else { /* if (digitsb > digitsa) */
1.1489 + JS_ASSERT((digitsb - digitsa) < ArrayLength(powersOf10));
1.1490 + *lessOrEqualp = (uint64_t(auint) * powersOf10[digitsb - digitsa] <= uint64_t(buint));
1.1491 + }
1.1492 + }
1.1493 +
1.1494 + return true;
1.1495 +}
1.1496 +
1.1497 +static inline bool
1.1498 +CompareSubStringValues(JSContext *cx, const jschar *s1, size_t l1,
1.1499 + const jschar *s2, size_t l2, bool *lessOrEqualp)
1.1500 +{
1.1501 + if (!CheckForInterrupt(cx))
1.1502 + return false;
1.1503 +
1.1504 + if (!s1 || !s2)
1.1505 + return false;
1.1506 +
1.1507 + int32_t result = CompareChars(s1, l1, s2, l2);
1.1508 + *lessOrEqualp = (result <= 0);
1.1509 + return true;
1.1510 +}
1.1511 +
1.1512 +struct SortComparatorStrings
1.1513 +{
1.1514 + JSContext *const cx;
1.1515 +
1.1516 + SortComparatorStrings(JSContext *cx)
1.1517 + : cx(cx) {}
1.1518 +
1.1519 + bool operator()(const Value &a, const Value &b, bool *lessOrEqualp) {
1.1520 + return CompareStringValues(cx, a, b, lessOrEqualp);
1.1521 + }
1.1522 +};
1.1523 +
1.1524 +struct SortComparatorLexicographicInt32
1.1525 +{
1.1526 + bool operator()(const Value &a, const Value &b, bool *lessOrEqualp) {
1.1527 + return CompareLexicographicInt32(a, b, lessOrEqualp);
1.1528 + }
1.1529 +};
1.1530 +
1.1531 +struct StringifiedElement
1.1532 +{
1.1533 + size_t charsBegin;
1.1534 + size_t charsEnd;
1.1535 + size_t elementIndex;
1.1536 +};
1.1537 +
1.1538 +struct SortComparatorStringifiedElements
1.1539 +{
1.1540 + JSContext *const cx;
1.1541 + const StringBuffer &sb;
1.1542 +
1.1543 + SortComparatorStringifiedElements(JSContext *cx, const StringBuffer &sb)
1.1544 + : cx(cx), sb(sb) {}
1.1545 +
1.1546 + bool operator()(const StringifiedElement &a, const StringifiedElement &b, bool *lessOrEqualp) {
1.1547 + return CompareSubStringValues(cx, sb.begin() + a.charsBegin, a.charsEnd - a.charsBegin,
1.1548 + sb.begin() + b.charsBegin, b.charsEnd - b.charsBegin,
1.1549 + lessOrEqualp);
1.1550 + }
1.1551 +};
1.1552 +
1.1553 +struct SortComparatorFunction
1.1554 +{
1.1555 + JSContext *const cx;
1.1556 + const Value &fval;
1.1557 + FastInvokeGuard &fig;
1.1558 +
1.1559 + SortComparatorFunction(JSContext *cx, const Value &fval, FastInvokeGuard &fig)
1.1560 + : cx(cx), fval(fval), fig(fig) { }
1.1561 +
1.1562 + bool operator()(const Value &a, const Value &b, bool *lessOrEqualp);
1.1563 +};
1.1564 +
1.1565 +bool
1.1566 +SortComparatorFunction::operator()(const Value &a, const Value &b, bool *lessOrEqualp)
1.1567 +{
1.1568 + /*
1.1569 + * array_sort deals with holes and undefs on its own and they should not
1.1570 + * come here.
1.1571 + */
1.1572 + JS_ASSERT(!a.isMagic() && !a.isUndefined());
1.1573 + JS_ASSERT(!a.isMagic() && !b.isUndefined());
1.1574 +
1.1575 + if (!CheckForInterrupt(cx))
1.1576 + return false;
1.1577 +
1.1578 + InvokeArgs &args = fig.args();
1.1579 + if (!args.init(2))
1.1580 + return false;
1.1581 +
1.1582 + args.setCallee(fval);
1.1583 + args.setThis(UndefinedValue());
1.1584 + args[0].set(a);
1.1585 + args[1].set(b);
1.1586 +
1.1587 + if (!fig.invoke(cx))
1.1588 + return false;
1.1589 +
1.1590 + double cmp;
1.1591 + if (!ToNumber(cx, args.rval(), &cmp))
1.1592 + return false;
1.1593 +
1.1594 + /*
1.1595 + * XXX eport some kind of error here if cmp is NaN? ECMA talks about
1.1596 + * 'consistent compare functions' that don't return NaN, but is silent
1.1597 + * about what the result should be. So we currently ignore it.
1.1598 + */
1.1599 + *lessOrEqualp = (IsNaN(cmp) || cmp <= 0);
1.1600 + return true;
1.1601 +}
1.1602 +
1.1603 +struct NumericElement
1.1604 +{
1.1605 + double dv;
1.1606 + size_t elementIndex;
1.1607 +};
1.1608 +
1.1609 +bool
1.1610 +ComparatorNumericLeftMinusRight(const NumericElement &a, const NumericElement &b,
1.1611 + bool *lessOrEqualp)
1.1612 +{
1.1613 + *lessOrEqualp = (a.dv <= b.dv);
1.1614 + return true;
1.1615 +}
1.1616 +
1.1617 +bool
1.1618 +ComparatorNumericRightMinusLeft(const NumericElement &a, const NumericElement &b,
1.1619 + bool *lessOrEqualp)
1.1620 +{
1.1621 + *lessOrEqualp = (b.dv <= a.dv);
1.1622 + return true;
1.1623 +}
1.1624 +
1.1625 +typedef bool (*ComparatorNumeric)(const NumericElement &a, const NumericElement &b,
1.1626 + bool *lessOrEqualp);
1.1627 +
1.1628 +ComparatorNumeric SortComparatorNumerics[] = {
1.1629 + nullptr,
1.1630 + nullptr,
1.1631 + ComparatorNumericLeftMinusRight,
1.1632 + ComparatorNumericRightMinusLeft
1.1633 +};
1.1634 +
1.1635 +bool
1.1636 +ComparatorInt32LeftMinusRight(const Value &a, const Value &b, bool *lessOrEqualp)
1.1637 +{
1.1638 + *lessOrEqualp = (a.toInt32() <= b.toInt32());
1.1639 + return true;
1.1640 +}
1.1641 +
1.1642 +bool
1.1643 +ComparatorInt32RightMinusLeft(const Value &a, const Value &b, bool *lessOrEqualp)
1.1644 +{
1.1645 + *lessOrEqualp = (b.toInt32() <= a.toInt32());
1.1646 + return true;
1.1647 +}
1.1648 +
1.1649 +typedef bool (*ComparatorInt32)(const Value &a, const Value &b, bool *lessOrEqualp);
1.1650 +
1.1651 +ComparatorInt32 SortComparatorInt32s[] = {
1.1652 + nullptr,
1.1653 + nullptr,
1.1654 + ComparatorInt32LeftMinusRight,
1.1655 + ComparatorInt32RightMinusLeft
1.1656 +};
1.1657 +
1.1658 +// Note: Values for this enum must match up with SortComparatorNumerics
1.1659 +// and SortComparatorInt32s.
1.1660 +enum ComparatorMatchResult {
1.1661 + Match_Failure = 0,
1.1662 + Match_None,
1.1663 + Match_LeftMinusRight,
1.1664 + Match_RightMinusLeft
1.1665 +};
1.1666 +
1.1667 +/*
1.1668 + * Specialize behavior for comparator functions with particular common bytecode
1.1669 + * patterns: namely, |return x - y| and |return y - x|.
1.1670 + */
1.1671 +ComparatorMatchResult
1.1672 +MatchNumericComparator(JSContext *cx, const Value &v)
1.1673 +{
1.1674 + if (!v.isObject())
1.1675 + return Match_None;
1.1676 +
1.1677 + JSObject &obj = v.toObject();
1.1678 + if (!obj.is<JSFunction>())
1.1679 + return Match_None;
1.1680 +
1.1681 + JSFunction *fun = &obj.as<JSFunction>();
1.1682 + if (!fun->isInterpreted())
1.1683 + return Match_None;
1.1684 +
1.1685 + JSScript *script = fun->getOrCreateScript(cx);
1.1686 + if (!script)
1.1687 + return Match_Failure;
1.1688 +
1.1689 + jsbytecode *pc = script->code();
1.1690 +
1.1691 + uint16_t arg0, arg1;
1.1692 + if (JSOp(*pc) != JSOP_GETARG)
1.1693 + return Match_None;
1.1694 + arg0 = GET_ARGNO(pc);
1.1695 + pc += JSOP_GETARG_LENGTH;
1.1696 +
1.1697 + if (JSOp(*pc) != JSOP_GETARG)
1.1698 + return Match_None;
1.1699 + arg1 = GET_ARGNO(pc);
1.1700 + pc += JSOP_GETARG_LENGTH;
1.1701 +
1.1702 + if (JSOp(*pc) != JSOP_SUB)
1.1703 + return Match_None;
1.1704 + pc += JSOP_SUB_LENGTH;
1.1705 +
1.1706 + if (JSOp(*pc) != JSOP_RETURN)
1.1707 + return Match_None;
1.1708 +
1.1709 + if (arg0 == 0 && arg1 == 1)
1.1710 + return Match_LeftMinusRight;
1.1711 +
1.1712 + if (arg0 == 1 && arg1 == 0)
1.1713 + return Match_RightMinusLeft;
1.1714 +
1.1715 + return Match_None;
1.1716 +}
1.1717 +
1.1718 +template<typename K, typename C>
1.1719 +static inline bool
1.1720 +MergeSortByKey(K keys, size_t len, K scratch, C comparator, AutoValueVector *vec)
1.1721 +{
1.1722 + MOZ_ASSERT(vec->length() >= len);
1.1723 +
1.1724 + /* Sort keys. */
1.1725 + if (!MergeSort(keys, len, scratch, comparator))
1.1726 + return false;
1.1727 +
1.1728 + /*
1.1729 + * Reorder vec by keys in-place, going element by element. When an out-of-
1.1730 + * place element is encountered, move that element to its proper position,
1.1731 + * displacing whatever element was at *that* point to its proper position,
1.1732 + * and so on until an element must be moved to the current position.
1.1733 + *
1.1734 + * At each outer iteration all elements up to |i| are sorted. If
1.1735 + * necessary each inner iteration moves some number of unsorted elements
1.1736 + * (including |i|) directly to sorted position. Thus on completion |*vec|
1.1737 + * is sorted, and out-of-position elements have moved once. Complexity is
1.1738 + * Θ(len) + O(len) == O(2*len), with each element visited at most twice.
1.1739 + */
1.1740 + for (size_t i = 0; i < len; i++) {
1.1741 + size_t j = keys[i].elementIndex;
1.1742 + if (i == j)
1.1743 + continue; // fixed point
1.1744 +
1.1745 + MOZ_ASSERT(j > i, "Everything less than |i| should be in the right place!");
1.1746 + Value tv = (*vec)[j];
1.1747 + do {
1.1748 + size_t k = keys[j].elementIndex;
1.1749 + keys[j].elementIndex = j;
1.1750 + (*vec)[j] = (*vec)[k];
1.1751 + j = k;
1.1752 + } while (j != i);
1.1753 +
1.1754 + // We could assert the loop invariant that |i == keys[i].elementIndex|
1.1755 + // here if we synced |keys[i].elementIndex|. But doing so would render
1.1756 + // the assertion vacuous, so don't bother, even in debug builds.
1.1757 + (*vec)[i] = tv;
1.1758 + }
1.1759 +
1.1760 + return true;
1.1761 +}
1.1762 +
1.1763 +/*
1.1764 + * Sort Values as strings.
1.1765 + *
1.1766 + * To minimize #conversions, SortLexicographically() first converts all Values
1.1767 + * to strings at once, then sorts the elements by these cached strings.
1.1768 + */
1.1769 +bool
1.1770 +SortLexicographically(JSContext *cx, AutoValueVector *vec, size_t len)
1.1771 +{
1.1772 + JS_ASSERT(vec->length() >= len);
1.1773 +
1.1774 + StringBuffer sb(cx);
1.1775 + Vector<StringifiedElement, 0, TempAllocPolicy> strElements(cx);
1.1776 +
1.1777 + /* MergeSort uses the upper half as scratch space. */
1.1778 + if (!strElements.reserve(2 * len))
1.1779 + return false;
1.1780 +
1.1781 + /* Convert Values to strings. */
1.1782 + size_t cursor = 0;
1.1783 + for (size_t i = 0; i < len; i++) {
1.1784 + if (!CheckForInterrupt(cx))
1.1785 + return false;
1.1786 +
1.1787 + if (!ValueToStringBuffer(cx, (*vec)[i], sb))
1.1788 + return false;
1.1789 +
1.1790 + StringifiedElement el = { cursor, sb.length(), i };
1.1791 + strElements.infallibleAppend(el);
1.1792 + cursor = sb.length();
1.1793 + }
1.1794 +
1.1795 + /* Resize strElements so we can perform MergeSort. */
1.1796 + JS_ALWAYS_TRUE(strElements.resize(2 * len));
1.1797 +
1.1798 + /* Sort Values in vec alphabetically. */
1.1799 + return MergeSortByKey(strElements.begin(), len, strElements.begin() + len,
1.1800 + SortComparatorStringifiedElements(cx, sb), vec);
1.1801 +}
1.1802 +
1.1803 +/*
1.1804 + * Sort Values as numbers.
1.1805 + *
1.1806 + * To minimize #conversions, SortNumerically first converts all Values to
1.1807 + * numerics at once, then sorts the elements by these cached numerics.
1.1808 + */
1.1809 +bool
1.1810 +SortNumerically(JSContext *cx, AutoValueVector *vec, size_t len, ComparatorMatchResult comp)
1.1811 +{
1.1812 + JS_ASSERT(vec->length() >= len);
1.1813 +
1.1814 + Vector<NumericElement, 0, TempAllocPolicy> numElements(cx);
1.1815 +
1.1816 + /* MergeSort uses the upper half as scratch space. */
1.1817 + if (!numElements.reserve(2 * len))
1.1818 + return false;
1.1819 +
1.1820 + /* Convert Values to numerics. */
1.1821 + for (size_t i = 0; i < len; i++) {
1.1822 + if (!CheckForInterrupt(cx))
1.1823 + return false;
1.1824 +
1.1825 + double dv;
1.1826 + if (!ToNumber(cx, vec->handleAt(i), &dv))
1.1827 + return false;
1.1828 +
1.1829 + NumericElement el = { dv, i };
1.1830 + numElements.infallibleAppend(el);
1.1831 + }
1.1832 +
1.1833 + /* Resize strElements so we can perform MergeSort. */
1.1834 + JS_ALWAYS_TRUE(numElements.resize(2 * len));
1.1835 +
1.1836 + /* Sort Values in vec numerically. */
1.1837 + return MergeSortByKey(numElements.begin(), len, numElements.begin() + len,
1.1838 + SortComparatorNumerics[comp], vec);
1.1839 +}
1.1840 +
1.1841 +} /* namespace anonymous */
1.1842 +
1.1843 +bool
1.1844 +js::array_sort(JSContext *cx, unsigned argc, Value *vp)
1.1845 +{
1.1846 + CallArgs args = CallArgsFromVp(argc, vp);
1.1847 +
1.1848 + RootedValue fvalRoot(cx);
1.1849 + Value &fval = fvalRoot.get();
1.1850 +
1.1851 + if (args.hasDefined(0)) {
1.1852 + if (args[0].isPrimitive()) {
1.1853 + JS_ReportErrorNumber(cx, js_GetErrorMessage, nullptr, JSMSG_BAD_SORT_ARG);
1.1854 + return false;
1.1855 + }
1.1856 + fval = args[0]; /* non-default compare function */
1.1857 + } else {
1.1858 + fval.setNull();
1.1859 + }
1.1860 +
1.1861 + RootedObject obj(cx, ToObject(cx, args.thisv()));
1.1862 + if (!obj)
1.1863 + return false;
1.1864 +
1.1865 + uint32_t len;
1.1866 + if (!GetLengthProperty(cx, obj, &len))
1.1867 + return false;
1.1868 + if (len < 2) {
1.1869 + /* [] and [a] remain unchanged when sorted. */
1.1870 + args.rval().setObject(*obj);
1.1871 + return true;
1.1872 + }
1.1873 +
1.1874 + /*
1.1875 + * We need a temporary array of 2 * len Value to hold the array elements
1.1876 + * and the scratch space for merge sort. Check that its size does not
1.1877 + * overflow size_t, which would allow for indexing beyond the end of the
1.1878 + * malloc'd vector.
1.1879 + */
1.1880 +#if JS_BITS_PER_WORD == 32
1.1881 + if (size_t(len) > size_t(-1) / (2 * sizeof(Value))) {
1.1882 + js_ReportAllocationOverflow(cx);
1.1883 + return false;
1.1884 + }
1.1885 +#endif
1.1886 +
1.1887 + /*
1.1888 + * Initialize vec as a root. We will clear elements of vec one by
1.1889 + * one while increasing the rooted amount of vec when we know that the
1.1890 + * property at the corresponding index exists and its value must be rooted.
1.1891 + *
1.1892 + * In this way when sorting a huge mostly sparse array we will not
1.1893 + * access the tail of vec corresponding to properties that do not
1.1894 + * exist, allowing OS to avoiding committing RAM. See bug 330812.
1.1895 + */
1.1896 + size_t n, undefs;
1.1897 + {
1.1898 + AutoValueVector vec(cx);
1.1899 + if (!vec.reserve(2 * size_t(len)))
1.1900 + return false;
1.1901 +
1.1902 + /*
1.1903 + * By ECMA 262, 15.4.4.11, a property that does not exist (which we
1.1904 + * call a "hole") is always greater than an existing property with
1.1905 + * value undefined and that is always greater than any other property.
1.1906 + * Thus to sort holes and undefs we simply count them, sort the rest
1.1907 + * of elements, append undefs after them and then make holes after
1.1908 + * undefs.
1.1909 + */
1.1910 + undefs = 0;
1.1911 + bool allStrings = true;
1.1912 + bool allInts = true;
1.1913 + RootedValue v(cx);
1.1914 + for (uint32_t i = 0; i < len; i++) {
1.1915 + if (!CheckForInterrupt(cx))
1.1916 + return false;
1.1917 +
1.1918 + /* Clear vec[newlen] before including it in the rooted set. */
1.1919 + bool hole;
1.1920 + if (!GetElement(cx, obj, i, &hole, &v))
1.1921 + return false;
1.1922 + if (hole)
1.1923 + continue;
1.1924 + if (v.isUndefined()) {
1.1925 + ++undefs;
1.1926 + continue;
1.1927 + }
1.1928 + vec.infallibleAppend(v);
1.1929 + allStrings = allStrings && v.isString();
1.1930 + allInts = allInts && v.isInt32();
1.1931 + }
1.1932 +
1.1933 +
1.1934 + /*
1.1935 + * If the array only contains holes, we're done. But if it contains
1.1936 + * undefs, those must be sorted to the front of the array.
1.1937 + */
1.1938 + n = vec.length();
1.1939 + if (n == 0 && undefs == 0) {
1.1940 + args.rval().setObject(*obj);
1.1941 + return true;
1.1942 + }
1.1943 +
1.1944 + /* Here len == n + undefs + number_of_holes. */
1.1945 + if (fval.isNull()) {
1.1946 + /*
1.1947 + * Sort using the default comparator converting all elements to
1.1948 + * strings.
1.1949 + */
1.1950 + if (allStrings) {
1.1951 + JS_ALWAYS_TRUE(vec.resize(n * 2));
1.1952 + if (!MergeSort(vec.begin(), n, vec.begin() + n, SortComparatorStrings(cx)))
1.1953 + return false;
1.1954 + } else if (allInts) {
1.1955 + JS_ALWAYS_TRUE(vec.resize(n * 2));
1.1956 + if (!MergeSort(vec.begin(), n, vec.begin() + n,
1.1957 + SortComparatorLexicographicInt32())) {
1.1958 + return false;
1.1959 + }
1.1960 + } else {
1.1961 + if (!SortLexicographically(cx, &vec, n))
1.1962 + return false;
1.1963 + }
1.1964 + } else {
1.1965 + ComparatorMatchResult comp = MatchNumericComparator(cx, fval);
1.1966 + if (comp == Match_Failure)
1.1967 + return false;
1.1968 +
1.1969 + if (comp != Match_None) {
1.1970 + if (allInts) {
1.1971 + JS_ALWAYS_TRUE(vec.resize(n * 2));
1.1972 + if (!MergeSort(vec.begin(), n, vec.begin() + n, SortComparatorInt32s[comp]))
1.1973 + return false;
1.1974 + } else {
1.1975 + if (!SortNumerically(cx, &vec, n, comp))
1.1976 + return false;
1.1977 + }
1.1978 + } else {
1.1979 + FastInvokeGuard fig(cx, fval);
1.1980 + MOZ_ASSERT(!InParallelSection(),
1.1981 + "Array.sort() can't currently be used from parallel code");
1.1982 + JS_ALWAYS_TRUE(vec.resize(n * 2));
1.1983 + if (!MergeSort(vec.begin(), n, vec.begin() + n,
1.1984 + SortComparatorFunction(cx, fval, fig)))
1.1985 + {
1.1986 + return false;
1.1987 + }
1.1988 + }
1.1989 + }
1.1990 +
1.1991 + if (!InitArrayElements(cx, obj, 0, uint32_t(n), vec.begin(), DontUpdateTypes))
1.1992 + return false;
1.1993 + }
1.1994 +
1.1995 + /* Set undefs that sorted after the rest of elements. */
1.1996 + while (undefs != 0) {
1.1997 + --undefs;
1.1998 + if (!CheckForInterrupt(cx) || !SetArrayElement(cx, obj, n++, UndefinedHandleValue))
1.1999 + return false;
1.2000 + }
1.2001 +
1.2002 + /* Re-create any holes that sorted to the end of the array. */
1.2003 + while (len > n) {
1.2004 + if (!CheckForInterrupt(cx) || !DeletePropertyOrThrow(cx, obj, --len))
1.2005 + return false;
1.2006 + }
1.2007 + args.rval().setObject(*obj);
1.2008 + return true;
1.2009 +}
1.2010 +
1.2011 +bool
1.2012 +js::NewbornArrayPush(JSContext *cx, HandleObject obj, const Value &v)
1.2013 +{
1.2014 + Rooted<ArrayObject*> arr(cx, &obj->as<ArrayObject>());
1.2015 +
1.2016 + JS_ASSERT(!v.isMagic());
1.2017 + JS_ASSERT(arr->lengthIsWritable());
1.2018 +
1.2019 + uint32_t length = arr->length();
1.2020 + JS_ASSERT(length <= arr->getDenseCapacity());
1.2021 +
1.2022 + if (!arr->ensureElements(cx, length + 1))
1.2023 + return false;
1.2024 +
1.2025 + arr->setDenseInitializedLength(length + 1);
1.2026 + arr->setLengthInt32(length + 1);
1.2027 + arr->initDenseElementWithType(cx, length, v);
1.2028 + return true;
1.2029 +}
1.2030 +
1.2031 +/* ES5 15.4.4.7 */
1.2032 +bool
1.2033 +js::array_push(JSContext *cx, unsigned argc, Value *vp)
1.2034 +{
1.2035 + CallArgs args = CallArgsFromVp(argc, vp);
1.2036 +
1.2037 + /* Step 1. */
1.2038 + RootedObject obj(cx, ToObject(cx, args.thisv()));
1.2039 + if (!obj)
1.2040 + return false;
1.2041 +
1.2042 + /* Steps 2-3. */
1.2043 + uint32_t length;
1.2044 + if (!GetLengthProperty(cx, obj, &length))
1.2045 + return false;
1.2046 +
1.2047 + /* Fast path for native objects with dense elements. */
1.2048 + do {
1.2049 + if (!obj->isNative() || obj->is<TypedArrayObject>())
1.2050 + break;
1.2051 +
1.2052 + if (obj->is<ArrayObject>() && !obj->as<ArrayObject>().lengthIsWritable())
1.2053 + break;
1.2054 +
1.2055 + if (ObjectMayHaveExtraIndexedProperties(obj))
1.2056 + break;
1.2057 +
1.2058 + uint32_t argCount = args.length();
1.2059 + JSObject::EnsureDenseResult result = obj->ensureDenseElements(cx, length, argCount);
1.2060 + if (result == JSObject::ED_FAILED)
1.2061 + return false;
1.2062 +
1.2063 + if (result == JSObject::ED_OK) {
1.2064 + for (uint32_t i = 0, index = length; i < argCount; index++, i++)
1.2065 + obj->setDenseElementWithType(cx, index, args[i]);
1.2066 + uint32_t newlength = length + argCount;
1.2067 + args.rval().setNumber(newlength);
1.2068 + if (obj->is<ArrayObject>()) {
1.2069 + obj->as<ArrayObject>().setLengthInt32(newlength);
1.2070 + return true;
1.2071 + }
1.2072 + return SetLengthProperty(cx, obj, newlength);
1.2073 + }
1.2074 +
1.2075 + MOZ_ASSERT(result == JSObject::ED_SPARSE);
1.2076 + } while (false);
1.2077 +
1.2078 + /* Steps 4-5. */
1.2079 + if (!InitArrayElements(cx, obj, length, args.length(), args.array(), UpdateTypes))
1.2080 + return false;
1.2081 +
1.2082 + /* Steps 6-7. */
1.2083 + double newlength = length + double(args.length());
1.2084 + args.rval().setNumber(newlength);
1.2085 + return SetLengthProperty(cx, obj, newlength);
1.2086 +}
1.2087 +
1.2088 +/* ES6 20130308 draft 15.4.4.6. */
1.2089 +bool
1.2090 +js::array_pop(JSContext *cx, unsigned argc, Value *vp)
1.2091 +{
1.2092 + CallArgs args = CallArgsFromVp(argc, vp);
1.2093 +
1.2094 + /* Step 1. */
1.2095 + RootedObject obj(cx, ToObject(cx, args.thisv()));
1.2096 + if (!obj)
1.2097 + return false;
1.2098 +
1.2099 + /* Steps 2-3. */
1.2100 + uint32_t index;
1.2101 + if (!GetLengthProperty(cx, obj, &index))
1.2102 + return false;
1.2103 +
1.2104 + /* Steps 4-5. */
1.2105 + if (index == 0) {
1.2106 + /* Step 4b. */
1.2107 + args.rval().setUndefined();
1.2108 + } else {
1.2109 + /* Step 5a. */
1.2110 + index--;
1.2111 +
1.2112 + /* Step 5b, 5e. */
1.2113 + bool hole;
1.2114 + if (!GetElement(cx, obj, index, &hole, args.rval()))
1.2115 + return false;
1.2116 +
1.2117 + /* Step 5c. */
1.2118 + if (!hole && !DeletePropertyOrThrow(cx, obj, index))
1.2119 + return false;
1.2120 + }
1.2121 +
1.2122 + // If this was an array, then there are no elements above the one we just
1.2123 + // deleted (if we deleted an element). Thus we can shrink the dense
1.2124 + // initialized length accordingly. (This is fine even if the array length
1.2125 + // is non-writable: length-changing occurs after element-deletion effects.)
1.2126 + // Don't do anything if this isn't an array, as any deletion above has no
1.2127 + // effect on any elements after the "last" one indicated by the "length"
1.2128 + // property.
1.2129 + if (obj->is<ArrayObject>() && obj->getDenseInitializedLength() > index)
1.2130 + obj->setDenseInitializedLength(index);
1.2131 +
1.2132 + /* Steps 4a, 5d. */
1.2133 + return SetLengthProperty(cx, obj, index);
1.2134 +}
1.2135 +
1.2136 +void
1.2137 +js::ArrayShiftMoveElements(JSObject *obj)
1.2138 +{
1.2139 + JS_ASSERT(obj->is<ArrayObject>());
1.2140 + JS_ASSERT(obj->as<ArrayObject>().lengthIsWritable());
1.2141 +
1.2142 + /*
1.2143 + * At this point the length and initialized length have already been
1.2144 + * decremented and the result fetched, so just shift the array elements
1.2145 + * themselves.
1.2146 + */
1.2147 + uint32_t initlen = obj->getDenseInitializedLength();
1.2148 + obj->moveDenseElementsNoPreBarrier(0, 1, initlen);
1.2149 +}
1.2150 +
1.2151 +/* ES5 15.4.4.9 */
1.2152 +bool
1.2153 +js::array_shift(JSContext *cx, unsigned argc, Value *vp)
1.2154 +{
1.2155 + CallArgs args = CallArgsFromVp(argc, vp);
1.2156 +
1.2157 + /* Step 1. */
1.2158 + RootedObject obj(cx, ToObject(cx, args.thisv()));
1.2159 + if (!obj)
1.2160 + return false;
1.2161 +
1.2162 + /* Steps 2-3. */
1.2163 + uint32_t len;
1.2164 + if (!GetLengthProperty(cx, obj, &len))
1.2165 + return false;
1.2166 +
1.2167 + /* Step 4. */
1.2168 + if (len == 0) {
1.2169 + /* Step 4a. */
1.2170 + if (!SetLengthProperty(cx, obj, 0))
1.2171 + return false;
1.2172 +
1.2173 + /* Step 4b. */
1.2174 + args.rval().setUndefined();
1.2175 + return true;
1.2176 + }
1.2177 +
1.2178 + uint32_t newlen = len - 1;
1.2179 +
1.2180 + /* Fast paths. */
1.2181 + if (obj->is<ArrayObject>() &&
1.2182 + obj->getDenseInitializedLength() > 0 &&
1.2183 + newlen < obj->getDenseCapacity() &&
1.2184 + !ObjectMayHaveExtraIndexedProperties(obj))
1.2185 + {
1.2186 + args.rval().set(obj->getDenseElement(0));
1.2187 + if (args.rval().isMagic(JS_ELEMENTS_HOLE))
1.2188 + args.rval().setUndefined();
1.2189 +
1.2190 + obj->moveDenseElements(0, 1, obj->getDenseInitializedLength() - 1);
1.2191 + obj->setDenseInitializedLength(obj->getDenseInitializedLength() - 1);
1.2192 +
1.2193 + if (!SetLengthProperty(cx, obj, newlen))
1.2194 + return false;
1.2195 +
1.2196 + return js_SuppressDeletedProperty(cx, obj, INT_TO_JSID(newlen));
1.2197 + }
1.2198 +
1.2199 + /* Steps 5, 10. */
1.2200 + bool hole;
1.2201 + if (!GetElement(cx, obj, uint32_t(0), &hole, args.rval()))
1.2202 + return false;
1.2203 +
1.2204 + /* Steps 6-7. */
1.2205 + RootedValue value(cx);
1.2206 + for (uint32_t i = 0; i < newlen; i++) {
1.2207 + if (!CheckForInterrupt(cx))
1.2208 + return false;
1.2209 + if (!GetElement(cx, obj, i + 1, &hole, &value))
1.2210 + return false;
1.2211 + if (hole) {
1.2212 + if (!DeletePropertyOrThrow(cx, obj, i))
1.2213 + return false;
1.2214 + } else {
1.2215 + if (!SetArrayElement(cx, obj, i, value))
1.2216 + return false;
1.2217 + }
1.2218 + }
1.2219 +
1.2220 + /* Step 8. */
1.2221 + if (!DeletePropertyOrThrow(cx, obj, newlen))
1.2222 + return false;
1.2223 +
1.2224 + /* Step 9. */
1.2225 + return SetLengthProperty(cx, obj, newlen);
1.2226 +}
1.2227 +
1.2228 +static bool
1.2229 +array_unshift(JSContext *cx, unsigned argc, Value *vp)
1.2230 +{
1.2231 + CallArgs args = CallArgsFromVp(argc, vp);
1.2232 + RootedObject obj(cx, ToObject(cx, args.thisv()));
1.2233 + if (!obj)
1.2234 + return false;
1.2235 +
1.2236 + uint32_t length;
1.2237 + if (!GetLengthProperty(cx, obj, &length))
1.2238 + return false;
1.2239 +
1.2240 + double newlen = length;
1.2241 + if (args.length() > 0) {
1.2242 + /* Slide up the array to make room for all args at the bottom. */
1.2243 + if (length > 0) {
1.2244 + bool optimized = false;
1.2245 + do {
1.2246 + if (!obj->is<ArrayObject>())
1.2247 + break;
1.2248 + if (ObjectMayHaveExtraIndexedProperties(obj))
1.2249 + break;
1.2250 + if (!obj->as<ArrayObject>().lengthIsWritable())
1.2251 + break;
1.2252 + JSObject::EnsureDenseResult result = obj->ensureDenseElements(cx, length, args.length());
1.2253 + if (result != JSObject::ED_OK) {
1.2254 + if (result == JSObject::ED_FAILED)
1.2255 + return false;
1.2256 + JS_ASSERT(result == JSObject::ED_SPARSE);
1.2257 + break;
1.2258 + }
1.2259 + obj->moveDenseElements(args.length(), 0, length);
1.2260 + for (uint32_t i = 0; i < args.length(); i++)
1.2261 + obj->setDenseElement(i, MagicValue(JS_ELEMENTS_HOLE));
1.2262 + optimized = true;
1.2263 + } while (false);
1.2264 +
1.2265 + if (!optimized) {
1.2266 + double last = length;
1.2267 + double upperIndex = last + args.length();
1.2268 + RootedValue value(cx);
1.2269 + do {
1.2270 + --last, --upperIndex;
1.2271 + bool hole;
1.2272 + if (!CheckForInterrupt(cx))
1.2273 + return false;
1.2274 + if (!GetElement(cx, obj, last, &hole, &value))
1.2275 + return false;
1.2276 + if (hole) {
1.2277 + if (!DeletePropertyOrThrow(cx, obj, upperIndex))
1.2278 + return false;
1.2279 + } else {
1.2280 + if (!SetArrayElement(cx, obj, upperIndex, value))
1.2281 + return false;
1.2282 + }
1.2283 + } while (last != 0);
1.2284 + }
1.2285 + }
1.2286 +
1.2287 + /* Copy from args to the bottom of the array. */
1.2288 + if (!InitArrayElements(cx, obj, 0, args.length(), args.array(), UpdateTypes))
1.2289 + return false;
1.2290 +
1.2291 + newlen += args.length();
1.2292 + }
1.2293 + if (!SetLengthProperty(cx, obj, newlen))
1.2294 + return false;
1.2295 +
1.2296 + /* Follow Perl by returning the new array length. */
1.2297 + args.rval().setNumber(newlen);
1.2298 + return true;
1.2299 +}
1.2300 +
1.2301 +static inline void
1.2302 +TryReuseArrayType(JSObject *obj, ArrayObject *narr)
1.2303 +{
1.2304 + /*
1.2305 + * Try to change the type of a newly created array narr to the same type
1.2306 + * as obj. This can only be performed if the original object is an array
1.2307 + * and has the same prototype.
1.2308 + */
1.2309 + JS_ASSERT(narr->getProto()->hasNewType(&ArrayObject::class_, narr->type()));
1.2310 +
1.2311 + if (obj->is<ArrayObject>() && !obj->hasSingletonType() && obj->getProto() == narr->getProto())
1.2312 + narr->setType(obj->type());
1.2313 +}
1.2314 +
1.2315 +/*
1.2316 + * Returns true if this is a dense array whose |count| properties starting from
1.2317 + * |startingIndex| may be accessed (get, set, delete) directly through its
1.2318 + * contiguous vector of elements without fear of getters, setters, etc. along
1.2319 + * the prototype chain, or of enumerators requiring notification of
1.2320 + * modifications.
1.2321 + */
1.2322 +static inline bool
1.2323 +CanOptimizeForDenseStorage(HandleObject arr, uint32_t startingIndex, uint32_t count, JSContext *cx)
1.2324 +{
1.2325 + /* If the desired properties overflow dense storage, we can't optimize. */
1.2326 + if (UINT32_MAX - startingIndex < count)
1.2327 + return false;
1.2328 +
1.2329 + /* There's no optimizing possible if it's not an array. */
1.2330 + if (!arr->is<ArrayObject>())
1.2331 + return false;
1.2332 +
1.2333 + /*
1.2334 + * Don't optimize if the array might be in the midst of iteration. We
1.2335 + * rely on this to be able to safely move dense array elements around with
1.2336 + * just a memmove (see JSObject::moveDenseArrayElements), without worrying
1.2337 + * about updating any in-progress enumerators for properties implicitly
1.2338 + * deleted if a hole is moved from one location to another location not yet
1.2339 + * visited. See bug 690622.
1.2340 + *
1.2341 + * Another potential wrinkle: what if the enumeration is happening on an
1.2342 + * object which merely has |arr| on its prototype chain? It turns out this
1.2343 + * case can't happen, because any dense array used as the prototype of
1.2344 + * another object is first slowified, for type inference's sake.
1.2345 + */
1.2346 + types::TypeObject *arrType = arr->getType(cx);
1.2347 + if (MOZ_UNLIKELY(!arrType || arrType->hasAllFlags(OBJECT_FLAG_ITERATED)))
1.2348 + return false;
1.2349 +
1.2350 + /*
1.2351 + * Now watch out for getters and setters along the prototype chain or in
1.2352 + * other indexed properties on the object. (Note that non-writable length
1.2353 + * is subsumed by the initializedLength comparison.)
1.2354 + */
1.2355 + return !ObjectMayHaveExtraIndexedProperties(arr) &&
1.2356 + startingIndex + count <= arr->getDenseInitializedLength();
1.2357 +}
1.2358 +
1.2359 +/* ES5 15.4.4.12. */
1.2360 +bool
1.2361 +js::array_splice(JSContext *cx, unsigned argc, Value *vp)
1.2362 +{
1.2363 + return array_splice_impl(cx, argc, vp, true);
1.2364 +}
1.2365 +
1.2366 +bool
1.2367 +js::array_splice_impl(JSContext *cx, unsigned argc, Value *vp, bool returnValueIsUsed)
1.2368 +{
1.2369 + CallArgs args = CallArgsFromVp(argc, vp);
1.2370 +
1.2371 + /* Step 1. */
1.2372 + RootedObject obj(cx, ToObject(cx, args.thisv()));
1.2373 + if (!obj)
1.2374 + return false;
1.2375 +
1.2376 + /* Steps 3-4. */
1.2377 + uint32_t len;
1.2378 + if (!GetLengthProperty(cx, obj, &len))
1.2379 + return false;
1.2380 +
1.2381 + /* Step 5. */
1.2382 + double relativeStart;
1.2383 + if (!ToInteger(cx, args.get(0), &relativeStart))
1.2384 + return false;
1.2385 +
1.2386 + /* Step 6. */
1.2387 + uint32_t actualStart;
1.2388 + if (relativeStart < 0)
1.2389 + actualStart = Max(len + relativeStart, 0.0);
1.2390 + else
1.2391 + actualStart = Min(relativeStart, double(len));
1.2392 +
1.2393 + /* Step 7. */
1.2394 + uint32_t actualDeleteCount;
1.2395 + if (args.length() != 1) {
1.2396 + double deleteCountDouble;
1.2397 + RootedValue cnt(cx, args.length() >= 2 ? args[1] : Int32Value(0));
1.2398 + if (!ToInteger(cx, cnt, &deleteCountDouble))
1.2399 + return false;
1.2400 + actualDeleteCount = Min(Max(deleteCountDouble, 0.0), double(len - actualStart));
1.2401 + } else {
1.2402 + /*
1.2403 + * Non-standard: if start was specified but deleteCount was omitted,
1.2404 + * delete to the end of the array. See bug 668024 for discussion.
1.2405 + */
1.2406 + actualDeleteCount = len - actualStart;
1.2407 + }
1.2408 +
1.2409 + JS_ASSERT(len - actualStart >= actualDeleteCount);
1.2410 +
1.2411 + /* Steps 2, 8-9. */
1.2412 + Rooted<ArrayObject*> arr(cx);
1.2413 + if (CanOptimizeForDenseStorage(obj, actualStart, actualDeleteCount, cx)) {
1.2414 + if (returnValueIsUsed) {
1.2415 + arr = NewDenseCopiedArray(cx, actualDeleteCount, obj, actualStart);
1.2416 + if (!arr)
1.2417 + return false;
1.2418 + TryReuseArrayType(obj, arr);
1.2419 + }
1.2420 + } else {
1.2421 + arr = NewDenseAllocatedArray(cx, actualDeleteCount);
1.2422 + if (!arr)
1.2423 + return false;
1.2424 + TryReuseArrayType(obj, arr);
1.2425 +
1.2426 + RootedValue fromValue(cx);
1.2427 + for (uint32_t k = 0; k < actualDeleteCount; k++) {
1.2428 + bool hole;
1.2429 + if (!CheckForInterrupt(cx) ||
1.2430 + !GetElement(cx, obj, actualStart + k, &hole, &fromValue) ||
1.2431 + (!hole && !JSObject::defineElement(cx, arr, k, fromValue)))
1.2432 + {
1.2433 + return false;
1.2434 + }
1.2435 + }
1.2436 + }
1.2437 +
1.2438 + /* Step 11. */
1.2439 + uint32_t itemCount = (args.length() >= 2) ? (args.length() - 2) : 0;
1.2440 +
1.2441 + if (itemCount < actualDeleteCount) {
1.2442 + /* Step 12: the array is being shrunk. */
1.2443 + uint32_t sourceIndex = actualStart + actualDeleteCount;
1.2444 + uint32_t targetIndex = actualStart + itemCount;
1.2445 + uint32_t finalLength = len - actualDeleteCount + itemCount;
1.2446 +
1.2447 + if (CanOptimizeForDenseStorage(obj, 0, len, cx)) {
1.2448 + /* Steps 12(a)-(b). */
1.2449 + obj->moveDenseElements(targetIndex, sourceIndex, len - sourceIndex);
1.2450 +
1.2451 + /*
1.2452 + * Update the initialized length. Do so before shrinking so that we
1.2453 + * can apply the write barrier to the old slots.
1.2454 + */
1.2455 + obj->setDenseInitializedLength(finalLength);
1.2456 +
1.2457 + /* Steps 12(c)-(d). */
1.2458 + obj->shrinkElements(cx, finalLength);
1.2459 + } else {
1.2460 + /*
1.2461 + * This is all very slow if the length is very large. We don't yet
1.2462 + * have the ability to iterate in sorted order, so we just do the
1.2463 + * pessimistic thing and let CheckForInterrupt handle the
1.2464 + * fallout.
1.2465 + */
1.2466 +
1.2467 + /* Steps 12(a)-(b). */
1.2468 + RootedValue fromValue(cx);
1.2469 + for (uint32_t from = sourceIndex, to = targetIndex; from < len; from++, to++) {
1.2470 + if (!CheckForInterrupt(cx))
1.2471 + return false;
1.2472 +
1.2473 + bool hole;
1.2474 + if (!GetElement(cx, obj, from, &hole, &fromValue))
1.2475 + return false;
1.2476 + if (hole) {
1.2477 + if (!DeletePropertyOrThrow(cx, obj, to))
1.2478 + return false;
1.2479 + } else {
1.2480 + if (!SetArrayElement(cx, obj, to, fromValue))
1.2481 + return false;
1.2482 + }
1.2483 + }
1.2484 +
1.2485 + /* Steps 12(c)-(d). */
1.2486 + for (uint32_t k = len; k > finalLength; k--) {
1.2487 + if (!DeletePropertyOrThrow(cx, obj, k - 1))
1.2488 + return false;
1.2489 + }
1.2490 + }
1.2491 + } else if (itemCount > actualDeleteCount) {
1.2492 + /* Step 13. */
1.2493 +
1.2494 + /*
1.2495 + * Optimize only if the array is already dense and we can extend it to
1.2496 + * its new length. It would be wrong to extend the elements here for a
1.2497 + * number of reasons.
1.2498 + *
1.2499 + * First, this could cause us to fall into the fast-path below. This
1.2500 + * would cause elements to be moved into places past the non-writable
1.2501 + * length. And when the dense initialized length is updated, that'll
1.2502 + * cause the |in| operator to think that those elements actually exist,
1.2503 + * even though, properly, setting them must fail.
1.2504 + *
1.2505 + * Second, extending the elements here will trigger assertions inside
1.2506 + * ensureDenseElements that the elements aren't being extended past the
1.2507 + * length of a non-writable array. This is because extending elements
1.2508 + * will extend capacity -- which might extend them past a non-writable
1.2509 + * length, violating the |capacity <= length| invariant for such
1.2510 + * arrays. And that would make the various JITted fast-path method
1.2511 + * implementations of [].push, [].unshift, and so on wrong.
1.2512 + *
1.2513 + * If the array length is non-writable, this method *will* throw. For
1.2514 + * simplicity, have the slow-path code do it. (Also note that the slow
1.2515 + * path may validly *not* throw -- if all the elements being moved are
1.2516 + * holes.)
1.2517 + */
1.2518 + if (obj->is<ArrayObject>()) {
1.2519 + Rooted<ArrayObject*> arr(cx, &obj->as<ArrayObject>());
1.2520 + if (arr->lengthIsWritable()) {
1.2521 + JSObject::EnsureDenseResult res =
1.2522 + arr->ensureDenseElements(cx, arr->length(), itemCount - actualDeleteCount);
1.2523 + if (res == JSObject::ED_FAILED)
1.2524 + return false;
1.2525 + }
1.2526 + }
1.2527 +
1.2528 + if (CanOptimizeForDenseStorage(obj, len, itemCount - actualDeleteCount, cx)) {
1.2529 + obj->moveDenseElements(actualStart + itemCount,
1.2530 + actualStart + actualDeleteCount,
1.2531 + len - (actualStart + actualDeleteCount));
1.2532 + obj->setDenseInitializedLength(len + itemCount - actualDeleteCount);
1.2533 + } else {
1.2534 + RootedValue fromValue(cx);
1.2535 + for (double k = len - actualDeleteCount; k > actualStart; k--) {
1.2536 + if (!CheckForInterrupt(cx))
1.2537 + return false;
1.2538 +
1.2539 + double from = k + actualDeleteCount - 1;
1.2540 + double to = k + itemCount - 1;
1.2541 +
1.2542 + bool hole;
1.2543 + if (!GetElement(cx, obj, from, &hole, &fromValue))
1.2544 + return false;
1.2545 +
1.2546 + if (hole) {
1.2547 + if (!DeletePropertyOrThrow(cx, obj, to))
1.2548 + return false;
1.2549 + } else {
1.2550 + if (!SetArrayElement(cx, obj, to, fromValue))
1.2551 + return false;
1.2552 + }
1.2553 + }
1.2554 + }
1.2555 + }
1.2556 +
1.2557 + /* Step 10. */
1.2558 + Value *items = args.array() + 2;
1.2559 +
1.2560 + /* Steps 14-15. */
1.2561 + for (uint32_t k = actualStart, i = 0; i < itemCount; i++, k++) {
1.2562 + if (!SetArrayElement(cx, obj, k, HandleValue::fromMarkedLocation(&items[i])))
1.2563 + return false;
1.2564 + }
1.2565 +
1.2566 + /* Step 16. */
1.2567 + double finalLength = double(len) - actualDeleteCount + itemCount;
1.2568 + if (!SetLengthProperty(cx, obj, finalLength))
1.2569 + return false;
1.2570 +
1.2571 + /* Step 17. */
1.2572 + if (returnValueIsUsed)
1.2573 + args.rval().setObject(*arr);
1.2574 +
1.2575 + return true;
1.2576 +}
1.2577 +
1.2578 +#ifdef JS_ION
1.2579 +bool
1.2580 +js::array_concat_dense(JSContext *cx, Handle<ArrayObject*> arr1, Handle<ArrayObject*> arr2,
1.2581 + Handle<ArrayObject*> result)
1.2582 +{
1.2583 + uint32_t initlen1 = arr1->getDenseInitializedLength();
1.2584 + JS_ASSERT(initlen1 == arr1->length());
1.2585 +
1.2586 + uint32_t initlen2 = arr2->getDenseInitializedLength();
1.2587 + JS_ASSERT(initlen2 == arr2->length());
1.2588 +
1.2589 + /* No overflow here due to nelements limit. */
1.2590 + uint32_t len = initlen1 + initlen2;
1.2591 +
1.2592 + if (!result->ensureElements(cx, len))
1.2593 + return false;
1.2594 +
1.2595 + JS_ASSERT(!result->getDenseInitializedLength());
1.2596 + result->setDenseInitializedLength(len);
1.2597 +
1.2598 + result->initDenseElements(0, arr1->getDenseElements(), initlen1);
1.2599 + result->initDenseElements(initlen1, arr2->getDenseElements(), initlen2);
1.2600 + result->setLengthInt32(len);
1.2601 + return true;
1.2602 +}
1.2603 +#endif /* JS_ION */
1.2604 +
1.2605 +/*
1.2606 + * Python-esque sequence operations.
1.2607 + */
1.2608 +bool
1.2609 +js::array_concat(JSContext *cx, unsigned argc, Value *vp)
1.2610 +{
1.2611 + CallArgs args = CallArgsFromVp(argc, vp);
1.2612 +
1.2613 + /* Treat our |this| object as the first argument; see ECMA 15.4.4.4. */
1.2614 + Value *p = args.array() - 1;
1.2615 +
1.2616 + /* Create a new Array object and root it using *vp. */
1.2617 + RootedObject aobj(cx, ToObject(cx, args.thisv()));
1.2618 + if (!aobj)
1.2619 + return false;
1.2620 +
1.2621 + Rooted<ArrayObject*> narr(cx);
1.2622 + uint32_t length;
1.2623 + if (aobj->is<ArrayObject>() && !aobj->isIndexed()) {
1.2624 + length = aobj->as<ArrayObject>().length();
1.2625 + uint32_t initlen = aobj->getDenseInitializedLength();
1.2626 + narr = NewDenseCopiedArray(cx, initlen, aobj, 0);
1.2627 + if (!narr)
1.2628 + return false;
1.2629 + TryReuseArrayType(aobj, narr);
1.2630 + narr->setLength(cx, length);
1.2631 + args.rval().setObject(*narr);
1.2632 + if (argc == 0)
1.2633 + return true;
1.2634 + argc--;
1.2635 + p++;
1.2636 + } else {
1.2637 + narr = NewDenseEmptyArray(cx);
1.2638 + if (!narr)
1.2639 + return false;
1.2640 + args.rval().setObject(*narr);
1.2641 + length = 0;
1.2642 + }
1.2643 +
1.2644 + /* Loop over [0, argc] to concat args into narr, expanding all Arrays. */
1.2645 + for (unsigned i = 0; i <= argc; i++) {
1.2646 + if (!CheckForInterrupt(cx))
1.2647 + return false;
1.2648 + HandleValue v = HandleValue::fromMarkedLocation(&p[i]);
1.2649 + if (v.isObject()) {
1.2650 + RootedObject obj(cx, &v.toObject());
1.2651 + if (ObjectClassIs(obj, ESClass_Array, cx)) {
1.2652 + uint32_t alength;
1.2653 + if (!GetLengthProperty(cx, obj, &alength))
1.2654 + return false;
1.2655 + RootedValue tmp(cx);
1.2656 + for (uint32_t slot = 0; slot < alength; slot++) {
1.2657 + bool hole;
1.2658 + if (!CheckForInterrupt(cx) || !GetElement(cx, obj, slot, &hole, &tmp))
1.2659 + return false;
1.2660 +
1.2661 + /*
1.2662 + * Per ECMA 262, 15.4.4.4, step 9, ignore nonexistent
1.2663 + * properties.
1.2664 + */
1.2665 + if (!hole && !SetArrayElement(cx, narr, length + slot, tmp))
1.2666 + return false;
1.2667 + }
1.2668 + length += alength;
1.2669 + continue;
1.2670 + }
1.2671 + }
1.2672 +
1.2673 + if (!SetArrayElement(cx, narr, length, v))
1.2674 + return false;
1.2675 + length++;
1.2676 + }
1.2677 +
1.2678 + return SetLengthProperty(cx, narr, length);
1.2679 +}
1.2680 +
1.2681 +static bool
1.2682 +array_slice(JSContext *cx, unsigned argc, Value *vp)
1.2683 +{
1.2684 + CallArgs args = CallArgsFromVp(argc, vp);
1.2685 +
1.2686 + RootedObject obj(cx, ToObject(cx, args.thisv()));
1.2687 + if (!obj)
1.2688 + return false;
1.2689 +
1.2690 + uint32_t length;
1.2691 + if (!GetLengthProperty(cx, obj, &length))
1.2692 + return false;
1.2693 +
1.2694 + uint32_t begin = 0;
1.2695 + uint32_t end = length;
1.2696 + if (args.length() > 0) {
1.2697 + double d;
1.2698 + if (!ToInteger(cx, args[0], &d))
1.2699 + return false;
1.2700 + if (d < 0) {
1.2701 + d += length;
1.2702 + if (d < 0)
1.2703 + d = 0;
1.2704 + } else if (d > length) {
1.2705 + d = length;
1.2706 + }
1.2707 + begin = (uint32_t)d;
1.2708 +
1.2709 + if (args.hasDefined(1)) {
1.2710 + if (!ToInteger(cx, args[1], &d))
1.2711 + return false;
1.2712 + if (d < 0) {
1.2713 + d += length;
1.2714 + if (d < 0)
1.2715 + d = 0;
1.2716 + } else if (d > length) {
1.2717 + d = length;
1.2718 + }
1.2719 + end = (uint32_t)d;
1.2720 + }
1.2721 + }
1.2722 +
1.2723 + if (begin > end)
1.2724 + begin = end;
1.2725 +
1.2726 + Rooted<ArrayObject*> narr(cx);
1.2727 + narr = NewDenseAllocatedArray(cx, end - begin);
1.2728 + if (!narr)
1.2729 + return false;
1.2730 + TryReuseArrayType(obj, narr);
1.2731 +
1.2732 + if (obj->is<ArrayObject>() && !ObjectMayHaveExtraIndexedProperties(obj)) {
1.2733 + if (obj->getDenseInitializedLength() > begin) {
1.2734 + uint32_t numSourceElements = obj->getDenseInitializedLength() - begin;
1.2735 + uint32_t initLength = Min(numSourceElements, end - begin);
1.2736 + narr->setDenseInitializedLength(initLength);
1.2737 + narr->initDenseElements(0, &obj->getDenseElement(begin), initLength);
1.2738 + }
1.2739 + args.rval().setObject(*narr);
1.2740 + return true;
1.2741 + }
1.2742 +
1.2743 + if (js::SliceOp op = obj->getOps()->slice) {
1.2744 + // Ensure that we have dense elements, so that DOM can use js::UnsafeDefineElement.
1.2745 + JSObject::EnsureDenseResult result = narr->ensureDenseElements(cx, 0, end - begin);
1.2746 + if (result == JSObject::ED_FAILED)
1.2747 + return false;
1.2748 +
1.2749 + if (result == JSObject::ED_OK) {
1.2750 + if (!op(cx, obj, begin, end, narr))
1.2751 + return false;
1.2752 +
1.2753 + args.rval().setObject(*narr);
1.2754 + return true;
1.2755 + }
1.2756 +
1.2757 + // Fallthrough
1.2758 + JS_ASSERT(result == JSObject::ED_SPARSE);
1.2759 + }
1.2760 +
1.2761 +
1.2762 + if (!SliceSlowly(cx, obj, obj, begin, end, narr))
1.2763 + return false;
1.2764 +
1.2765 + args.rval().setObject(*narr);
1.2766 + return true;
1.2767 +}
1.2768 +
1.2769 +JS_FRIEND_API(bool)
1.2770 +js::SliceSlowly(JSContext* cx, HandleObject obj, HandleObject receiver,
1.2771 + uint32_t begin, uint32_t end, HandleObject result)
1.2772 +{
1.2773 + RootedValue value(cx);
1.2774 + for (uint32_t slot = begin; slot < end; slot++) {
1.2775 + bool hole;
1.2776 + if (!CheckForInterrupt(cx) ||
1.2777 + !GetElement(cx, obj, receiver, slot, &hole, &value))
1.2778 + {
1.2779 + return false;
1.2780 + }
1.2781 + if (!hole && !JSObject::defineElement(cx, result, slot - begin, value))
1.2782 + return false;
1.2783 + }
1.2784 + return true;
1.2785 +}
1.2786 +
1.2787 +/* ES5 15.4.4.20. */
1.2788 +static bool
1.2789 +array_filter(JSContext *cx, unsigned argc, Value *vp)
1.2790 +{
1.2791 + CallArgs args = CallArgsFromVp(argc, vp);
1.2792 +
1.2793 + /* Step 1. */
1.2794 + RootedObject obj(cx, ToObject(cx, args.thisv()));
1.2795 + if (!obj)
1.2796 + return false;
1.2797 +
1.2798 + /* Step 2-3. */
1.2799 + uint32_t len;
1.2800 + if (!GetLengthProperty(cx, obj, &len))
1.2801 + return false;
1.2802 +
1.2803 + /* Step 4. */
1.2804 + if (args.length() == 0) {
1.2805 + js_ReportMissingArg(cx, args.calleev(), 0);
1.2806 + return false;
1.2807 + }
1.2808 + RootedObject callable(cx, ValueToCallable(cx, args[0], args.length() - 1));
1.2809 + if (!callable)
1.2810 + return false;
1.2811 +
1.2812 + /* Step 5. */
1.2813 + RootedValue thisv(cx, args.length() >= 2 ? args[1] : UndefinedValue());
1.2814 +
1.2815 + /* Step 6. */
1.2816 + RootedObject arr(cx, NewDenseAllocatedArray(cx, 0));
1.2817 + if (!arr)
1.2818 + return false;
1.2819 + TypeObject *newtype = GetTypeCallerInitObject(cx, JSProto_Array);
1.2820 + if (!newtype)
1.2821 + return false;
1.2822 + arr->setType(newtype);
1.2823 +
1.2824 + /* Step 7. */
1.2825 + uint32_t k = 0;
1.2826 +
1.2827 + /* Step 8. */
1.2828 + uint32_t to = 0;
1.2829 +
1.2830 + /* Step 9. */
1.2831 + JS_ASSERT(!InParallelSection());
1.2832 + FastInvokeGuard fig(cx, ObjectValue(*callable));
1.2833 + InvokeArgs &args2 = fig.args();
1.2834 + RootedValue kValue(cx);
1.2835 + while (k < len) {
1.2836 + if (!CheckForInterrupt(cx))
1.2837 + return false;
1.2838 +
1.2839 + /* Step a, b, and c.i. */
1.2840 + bool kNotPresent;
1.2841 + if (!GetElement(cx, obj, k, &kNotPresent, &kValue))
1.2842 + return false;
1.2843 +
1.2844 + /* Step c.ii-iii. */
1.2845 + if (!kNotPresent) {
1.2846 + if (!args2.init(3))
1.2847 + return false;
1.2848 + args2.setCallee(ObjectValue(*callable));
1.2849 + args2.setThis(thisv);
1.2850 + args2[0].set(kValue);
1.2851 + args2[1].setNumber(k);
1.2852 + args2[2].setObject(*obj);
1.2853 + if (!fig.invoke(cx))
1.2854 + return false;
1.2855 +
1.2856 + if (ToBoolean(args2.rval())) {
1.2857 + if (!SetArrayElement(cx, arr, to, kValue))
1.2858 + return false;
1.2859 + to++;
1.2860 + }
1.2861 + }
1.2862 +
1.2863 + /* Step d. */
1.2864 + k++;
1.2865 + }
1.2866 +
1.2867 + /* Step 10. */
1.2868 + args.rval().setObject(*arr);
1.2869 + return true;
1.2870 +}
1.2871 +
1.2872 +static bool
1.2873 +array_isArray(JSContext *cx, unsigned argc, Value *vp)
1.2874 +{
1.2875 + CallArgs args = CallArgsFromVp(argc, vp);
1.2876 + bool isArray = args.length() > 0 && IsObjectWithClass(args[0], ESClass_Array, cx);
1.2877 + args.rval().setBoolean(isArray);
1.2878 + return true;
1.2879 +}
1.2880 +
1.2881 +static bool
1.2882 +IsArrayConstructor(const Value &v)
1.2883 +{
1.2884 + // This must only return true if v is *the* Array constructor for the
1.2885 + // current compartment; we rely on the fact that any other Array
1.2886 + // constructor would be represented as a wrapper.
1.2887 + return v.isObject() &&
1.2888 + v.toObject().is<JSFunction>() &&
1.2889 + v.toObject().as<JSFunction>().isNative() &&
1.2890 + v.toObject().as<JSFunction>().native() == js_Array;
1.2891 +}
1.2892 +
1.2893 +static bool
1.2894 +ArrayFromCallArgs(JSContext *cx, RootedTypeObject &type, CallArgs &args)
1.2895 +{
1.2896 + if (!InitArrayTypes(cx, type, args.array(), args.length()))
1.2897 + return false;
1.2898 + JSObject *obj = (args.length() == 0)
1.2899 + ? NewDenseEmptyArray(cx)
1.2900 + : NewDenseCopiedArray(cx, args.length(), args.array());
1.2901 + if (!obj)
1.2902 + return false;
1.2903 + obj->setType(type);
1.2904 + args.rval().setObject(*obj);
1.2905 + return true;
1.2906 +}
1.2907 +
1.2908 +static bool
1.2909 +array_of(JSContext *cx, unsigned argc, Value *vp)
1.2910 +{
1.2911 + CallArgs args = CallArgsFromVp(argc, vp);
1.2912 +
1.2913 + if (IsArrayConstructor(args.thisv()) || !IsConstructor(args.thisv())) {
1.2914 + // IsArrayConstructor(this) will usually be true in practice. This is
1.2915 + // the most common path.
1.2916 + RootedTypeObject type(cx, GetTypeCallerInitObject(cx, JSProto_Array));
1.2917 + if (!type)
1.2918 + return false;
1.2919 + return ArrayFromCallArgs(cx, type, args);
1.2920 + }
1.2921 +
1.2922 + // Step 4.
1.2923 + RootedObject obj(cx);
1.2924 + {
1.2925 + RootedValue v(cx);
1.2926 + Value argv[1] = {NumberValue(args.length())};
1.2927 + if (!InvokeConstructor(cx, args.thisv(), 1, argv, v.address()))
1.2928 + return false;
1.2929 + obj = ToObject(cx, v);
1.2930 + if (!obj)
1.2931 + return false;
1.2932 + }
1.2933 +
1.2934 + // Step 8.
1.2935 + for (unsigned k = 0; k < args.length(); k++) {
1.2936 + if (!JSObject::defineElement(cx, obj, k, args[k]))
1.2937 + return false;
1.2938 + }
1.2939 +
1.2940 + // Steps 9-10.
1.2941 + RootedValue v(cx, NumberValue(args.length()));
1.2942 + if (!JSObject::setProperty(cx, obj, obj, cx->names().length, &v, true))
1.2943 + return false;
1.2944 +
1.2945 + // Step 11.
1.2946 + args.rval().setObject(*obj);
1.2947 + return true;
1.2948 +}
1.2949 +
1.2950 +#define GENERIC JSFUN_GENERIC_NATIVE
1.2951 +
1.2952 +static const JSFunctionSpec array_methods[] = {
1.2953 +#if JS_HAS_TOSOURCE
1.2954 + JS_FN(js_toSource_str, array_toSource, 0,0),
1.2955 +#endif
1.2956 + JS_FN(js_toString_str, array_toString, 0,0),
1.2957 + JS_FN(js_toLocaleString_str,array_toLocaleString,0,0),
1.2958 +
1.2959 + /* Perl-ish methods. */
1.2960 + JS_FN("join", array_join, 1,JSFUN_GENERIC_NATIVE),
1.2961 + JS_FN("reverse", array_reverse, 0,JSFUN_GENERIC_NATIVE),
1.2962 + JS_FN("sort", array_sort, 1,JSFUN_GENERIC_NATIVE),
1.2963 + JS_FN("push", array_push, 1,JSFUN_GENERIC_NATIVE),
1.2964 + JS_FN("pop", array_pop, 0,JSFUN_GENERIC_NATIVE),
1.2965 + JS_FN("shift", array_shift, 0,JSFUN_GENERIC_NATIVE),
1.2966 + JS_FN("unshift", array_unshift, 1,JSFUN_GENERIC_NATIVE),
1.2967 + JS_FN("splice", array_splice, 2,JSFUN_GENERIC_NATIVE),
1.2968 +
1.2969 + /* Pythonic sequence methods. */
1.2970 + JS_FN("concat", array_concat, 1,JSFUN_GENERIC_NATIVE),
1.2971 + JS_FN("slice", array_slice, 2,JSFUN_GENERIC_NATIVE),
1.2972 +
1.2973 + JS_SELF_HOSTED_FN("lastIndexOf", "ArrayLastIndexOf", 1,0),
1.2974 + JS_SELF_HOSTED_FN("indexOf", "ArrayIndexOf", 1,0),
1.2975 + JS_SELF_HOSTED_FN("forEach", "ArrayForEach", 1,0),
1.2976 + JS_SELF_HOSTED_FN("map", "ArrayMap", 1,0),
1.2977 + JS_SELF_HOSTED_FN("reduce", "ArrayReduce", 1,0),
1.2978 + JS_SELF_HOSTED_FN("reduceRight", "ArrayReduceRight", 1,0),
1.2979 + JS_FN("filter", array_filter, 1,JSFUN_GENERIC_NATIVE),
1.2980 + JS_SELF_HOSTED_FN("some", "ArraySome", 1,0),
1.2981 + JS_SELF_HOSTED_FN("every", "ArrayEvery", 1,0),
1.2982 +
1.2983 +#ifdef ENABLE_PARALLEL_JS
1.2984 + /* Parallelizable and pure methods. */
1.2985 + JS_SELF_HOSTED_FN("mapPar", "ArrayMapPar", 2,0),
1.2986 + JS_SELF_HOSTED_FN("reducePar", "ArrayReducePar", 2,0),
1.2987 + JS_SELF_HOSTED_FN("scanPar", "ArrayScanPar", 2,0),
1.2988 + JS_SELF_HOSTED_FN("scatterPar", "ArrayScatterPar", 5,0),
1.2989 + JS_SELF_HOSTED_FN("filterPar", "ArrayFilterPar", 2,0),
1.2990 +#endif
1.2991 +
1.2992 + /* ES6 additions */
1.2993 + JS_SELF_HOSTED_FN("find", "ArrayFind", 1,0),
1.2994 + JS_SELF_HOSTED_FN("findIndex", "ArrayFindIndex", 1,0),
1.2995 +
1.2996 + JS_SELF_HOSTED_FN("fill", "ArrayFill", 3,0),
1.2997 +
1.2998 + JS_SELF_HOSTED_FN("@@iterator", "ArrayValues", 0,0),
1.2999 + JS_SELF_HOSTED_FN("entries", "ArrayEntries", 0,0),
1.3000 + JS_SELF_HOSTED_FN("keys", "ArrayKeys", 0,0),
1.3001 + JS_FS_END
1.3002 +};
1.3003 +
1.3004 +static const JSFunctionSpec array_static_methods[] = {
1.3005 + JS_FN("isArray", array_isArray, 1,0),
1.3006 + JS_SELF_HOSTED_FN("lastIndexOf", "ArrayStaticLastIndexOf", 2,0),
1.3007 + JS_SELF_HOSTED_FN("indexOf", "ArrayStaticIndexOf", 2,0),
1.3008 + JS_SELF_HOSTED_FN("forEach", "ArrayStaticForEach", 2,0),
1.3009 + JS_SELF_HOSTED_FN("map", "ArrayStaticMap", 2,0),
1.3010 + JS_SELF_HOSTED_FN("every", "ArrayStaticEvery", 2,0),
1.3011 + JS_SELF_HOSTED_FN("some", "ArrayStaticSome", 2,0),
1.3012 + JS_SELF_HOSTED_FN("reduce", "ArrayStaticReduce", 2,0),
1.3013 + JS_SELF_HOSTED_FN("reduceRight", "ArrayStaticReduceRight", 2,0),
1.3014 + JS_FN("of", array_of, 0,0),
1.3015 +
1.3016 +#ifdef ENABLE_PARALLEL_JS
1.3017 + JS_SELF_HOSTED_FN("build", "ArrayStaticBuild", 2,0),
1.3018 + /* Parallelizable and pure static methods. */
1.3019 + JS_SELF_HOSTED_FN("buildPar", "ArrayStaticBuildPar", 3,0),
1.3020 +#endif
1.3021 +
1.3022 + JS_FS_END
1.3023 +};
1.3024 +
1.3025 +/* ES5 15.4.2 */
1.3026 +bool
1.3027 +js_Array(JSContext *cx, unsigned argc, Value *vp)
1.3028 +{
1.3029 + CallArgs args = CallArgsFromVp(argc, vp);
1.3030 + RootedTypeObject type(cx, GetTypeCallerInitObject(cx, JSProto_Array));
1.3031 + if (!type)
1.3032 + return false;
1.3033 +
1.3034 + if (args.length() != 1 || !args[0].isNumber())
1.3035 + return ArrayFromCallArgs(cx, type, args);
1.3036 +
1.3037 + uint32_t length;
1.3038 + if (args[0].isInt32()) {
1.3039 + int32_t i = args[0].toInt32();
1.3040 + if (i < 0) {
1.3041 + JS_ReportErrorNumber(cx, js_GetErrorMessage, nullptr, JSMSG_BAD_ARRAY_LENGTH);
1.3042 + return false;
1.3043 + }
1.3044 + length = uint32_t(i);
1.3045 + } else {
1.3046 + double d = args[0].toDouble();
1.3047 + length = ToUint32(d);
1.3048 + if (d != double(length)) {
1.3049 + JS_ReportErrorNumber(cx, js_GetErrorMessage, nullptr, JSMSG_BAD_ARRAY_LENGTH);
1.3050 + return false;
1.3051 + }
1.3052 + }
1.3053 +
1.3054 + /*
1.3055 + * Allocate dense elements eagerly for small arrays, to avoid reallocating
1.3056 + * elements when filling the array.
1.3057 + */
1.3058 + RootedObject obj(cx);
1.3059 + obj = (length <= ArrayObject::EagerAllocationMaxLength)
1.3060 + ? NewDenseAllocatedArray(cx, length)
1.3061 + : NewDenseUnallocatedArray(cx, length);
1.3062 + if (!obj)
1.3063 + return false;
1.3064 + Rooted<ArrayObject*> arr(cx, &obj->as<ArrayObject>());
1.3065 +
1.3066 + arr->setType(type);
1.3067 +
1.3068 + /* If the length calculation overflowed, make sure that is marked for the new type. */
1.3069 + if (arr->length() > INT32_MAX)
1.3070 + arr->setLength(cx, arr->length());
1.3071 +
1.3072 + args.rval().setObject(*arr);
1.3073 + return true;
1.3074 +}
1.3075 +
1.3076 +JSObject *
1.3077 +js_InitArrayClass(JSContext *cx, HandleObject obj)
1.3078 +{
1.3079 + JS_ASSERT(obj->isNative());
1.3080 +
1.3081 + Rooted<GlobalObject*> global(cx, &obj->as<GlobalObject>());
1.3082 +
1.3083 + RootedObject proto(cx, global->getOrCreateObjectPrototype(cx));
1.3084 + if (!proto)
1.3085 + return nullptr;
1.3086 +
1.3087 + RootedTypeObject type(cx, cx->getNewType(&ArrayObject::class_, proto.get()));
1.3088 + if (!type)
1.3089 + return nullptr;
1.3090 +
1.3091 + JSObject *metadata = nullptr;
1.3092 + if (!NewObjectMetadata(cx, &metadata))
1.3093 + return nullptr;
1.3094 +
1.3095 + RootedShape shape(cx, EmptyShape::getInitialShape(cx, &ArrayObject::class_, TaggedProto(proto),
1.3096 + proto->getParent(), metadata,
1.3097 + gc::FINALIZE_OBJECT0));
1.3098 + if (!shape)
1.3099 + return nullptr;
1.3100 +
1.3101 + RootedObject arrayProto(cx, JSObject::createArray(cx, gc::FINALIZE_OBJECT4, gc::TenuredHeap, shape, type, 0));
1.3102 + if (!arrayProto || !JSObject::setSingletonType(cx, arrayProto) || !AddLengthProperty(cx, arrayProto))
1.3103 + return nullptr;
1.3104 +
1.3105 + RootedFunction ctor(cx);
1.3106 + ctor = global->createConstructor(cx, js_Array, cx->names().Array, 1);
1.3107 + if (!ctor)
1.3108 + return nullptr;
1.3109 +
1.3110 + /*
1.3111 + * The default 'new' type of Array.prototype is required by type inference
1.3112 + * to have unknown properties, to simplify handling of e.g. heterogenous
1.3113 + * arrays in JSON and script literals and allows setDenseArrayElement to
1.3114 + * be used without updating the indexed type set for such default arrays.
1.3115 + */
1.3116 + if (!JSObject::setNewTypeUnknown(cx, &ArrayObject::class_, arrayProto))
1.3117 + return nullptr;
1.3118 +
1.3119 + if (!LinkConstructorAndPrototype(cx, ctor, arrayProto))
1.3120 + return nullptr;
1.3121 +
1.3122 + if (!DefinePropertiesAndBrand(cx, arrayProto, nullptr, array_methods) ||
1.3123 + !DefinePropertiesAndBrand(cx, ctor, nullptr, array_static_methods))
1.3124 + {
1.3125 + return nullptr;
1.3126 + }
1.3127 +
1.3128 + if (!GlobalObject::initBuiltinConstructor(cx, global, JSProto_Array, ctor, arrayProto))
1.3129 + return nullptr;
1.3130 +
1.3131 + return arrayProto;
1.3132 +}
1.3133 +
1.3134 +/*
1.3135 + * Array allocation functions.
1.3136 + */
1.3137 +
1.3138 +static inline bool
1.3139 +EnsureNewArrayElements(ExclusiveContext *cx, JSObject *obj, uint32_t length)
1.3140 +{
1.3141 + /*
1.3142 + * If ensureElements creates dynamically allocated slots, then having
1.3143 + * fixedSlots is a waste.
1.3144 + */
1.3145 + DebugOnly<uint32_t> cap = obj->getDenseCapacity();
1.3146 +
1.3147 + if (!obj->ensureElements(cx, length))
1.3148 + return false;
1.3149 +
1.3150 + JS_ASSERT_IF(cap, !obj->hasDynamicElements());
1.3151 +
1.3152 + return true;
1.3153 +}
1.3154 +
1.3155 +template<bool allocateCapacity>
1.3156 +static MOZ_ALWAYS_INLINE ArrayObject *
1.3157 +NewArray(ExclusiveContext *cxArg, uint32_t length,
1.3158 + JSObject *protoArg, NewObjectKind newKind = GenericObject)
1.3159 +{
1.3160 + gc::AllocKind allocKind = GuessArrayGCKind(length);
1.3161 + JS_ASSERT(CanBeFinalizedInBackground(allocKind, &ArrayObject::class_));
1.3162 + allocKind = GetBackgroundAllocKind(allocKind);
1.3163 +
1.3164 + NewObjectCache::EntryIndex entry = -1;
1.3165 + if (JSContext *cx = cxArg->maybeJSContext()) {
1.3166 + NewObjectCache &cache = cx->runtime()->newObjectCache;
1.3167 + if (newKind == GenericObject &&
1.3168 + !cx->compartment()->hasObjectMetadataCallback() &&
1.3169 + cache.lookupGlobal(&ArrayObject::class_, cx->global(), allocKind, &entry))
1.3170 + {
1.3171 + gc::InitialHeap heap = GetInitialHeap(newKind, &ArrayObject::class_);
1.3172 + JSObject *obj = cache.newObjectFromHit<NoGC>(cx, entry, heap);
1.3173 + if (obj) {
1.3174 + /* Fixup the elements pointer and length, which may be incorrect. */
1.3175 + ArrayObject *arr = &obj->as<ArrayObject>();
1.3176 + arr->setFixedElements();
1.3177 + arr->setLength(cx, length);
1.3178 + if (allocateCapacity && !EnsureNewArrayElements(cx, arr, length))
1.3179 + return nullptr;
1.3180 + return arr;
1.3181 + } else {
1.3182 + RootedObject proto(cxArg, protoArg);
1.3183 + obj = cache.newObjectFromHit<CanGC>(cx, entry, heap);
1.3184 + JS_ASSERT(!obj);
1.3185 + protoArg = proto;
1.3186 + }
1.3187 + }
1.3188 + }
1.3189 +
1.3190 + RootedObject proto(cxArg, protoArg);
1.3191 + if (protoArg)
1.3192 + JS::PoisonPtr(&protoArg);
1.3193 +
1.3194 + if (!proto && !GetBuiltinPrototype(cxArg, JSProto_Array, &proto))
1.3195 + return nullptr;
1.3196 +
1.3197 + RootedTypeObject type(cxArg, cxArg->getNewType(&ArrayObject::class_, proto.get()));
1.3198 + if (!type)
1.3199 + return nullptr;
1.3200 +
1.3201 + JSObject *metadata = nullptr;
1.3202 + if (!NewObjectMetadata(cxArg, &metadata))
1.3203 + return nullptr;
1.3204 +
1.3205 + /*
1.3206 + * Get a shape with zero fixed slots, regardless of the size class.
1.3207 + * See JSObject::createArray.
1.3208 + */
1.3209 + RootedShape shape(cxArg, EmptyShape::getInitialShape(cxArg, &ArrayObject::class_,
1.3210 + TaggedProto(proto), cxArg->global(),
1.3211 + metadata, gc::FINALIZE_OBJECT0));
1.3212 + if (!shape)
1.3213 + return nullptr;
1.3214 +
1.3215 + Rooted<ArrayObject*> arr(cxArg, JSObject::createArray(cxArg, allocKind,
1.3216 + GetInitialHeap(newKind, &ArrayObject::class_),
1.3217 + shape, type, length));
1.3218 + if (!arr)
1.3219 + return nullptr;
1.3220 +
1.3221 + if (shape->isEmptyShape()) {
1.3222 + if (!AddLengthProperty(cxArg, arr))
1.3223 + return nullptr;
1.3224 + shape = arr->lastProperty();
1.3225 + EmptyShape::insertInitialShape(cxArg, shape, proto);
1.3226 + }
1.3227 +
1.3228 + if (newKind == SingletonObject && !JSObject::setSingletonType(cxArg, arr))
1.3229 + return nullptr;
1.3230 +
1.3231 + if (entry != -1) {
1.3232 + cxArg->asJSContext()->runtime()->newObjectCache.fillGlobal(entry, &ArrayObject::class_,
1.3233 + cxArg->global(), allocKind, arr);
1.3234 + }
1.3235 +
1.3236 + if (allocateCapacity && !EnsureNewArrayElements(cxArg, arr, length))
1.3237 + return nullptr;
1.3238 +
1.3239 + probes::CreateObject(cxArg, arr);
1.3240 + return arr;
1.3241 +}
1.3242 +
1.3243 +ArrayObject * JS_FASTCALL
1.3244 +js::NewDenseEmptyArray(JSContext *cx, JSObject *proto /* = nullptr */,
1.3245 + NewObjectKind newKind /* = GenericObject */)
1.3246 +{
1.3247 + return NewArray<false>(cx, 0, proto, newKind);
1.3248 +}
1.3249 +
1.3250 +ArrayObject * JS_FASTCALL
1.3251 +js::NewDenseAllocatedArray(ExclusiveContext *cx, uint32_t length, JSObject *proto /* = nullptr */,
1.3252 + NewObjectKind newKind /* = GenericObject */)
1.3253 +{
1.3254 + return NewArray<true>(cx, length, proto, newKind);
1.3255 +}
1.3256 +
1.3257 +ArrayObject * JS_FASTCALL
1.3258 +js::NewDenseUnallocatedArray(ExclusiveContext *cx, uint32_t length, JSObject *proto /* = nullptr */,
1.3259 + NewObjectKind newKind /* = GenericObject */)
1.3260 +{
1.3261 + return NewArray<false>(cx, length, proto, newKind);
1.3262 +}
1.3263 +
1.3264 +ArrayObject *
1.3265 +js::NewDenseCopiedArray(JSContext *cx, uint32_t length, HandleObject src, uint32_t elementOffset,
1.3266 + JSObject *proto /* = nullptr */)
1.3267 +{
1.3268 + JS_ASSERT(!src->isIndexed());
1.3269 +
1.3270 + ArrayObject* arr = NewArray<true>(cx, length, proto);
1.3271 + if (!arr)
1.3272 + return nullptr;
1.3273 +
1.3274 + JS_ASSERT(arr->getDenseCapacity() >= length);
1.3275 +
1.3276 + const Value* vp = src->getDenseElements() + elementOffset;
1.3277 + arr->setDenseInitializedLength(vp ? length : 0);
1.3278 +
1.3279 + if (vp)
1.3280 + arr->initDenseElements(0, vp, length);
1.3281 +
1.3282 + return arr;
1.3283 +}
1.3284 +
1.3285 +// values must point at already-rooted Value objects
1.3286 +ArrayObject *
1.3287 +js::NewDenseCopiedArray(JSContext *cx, uint32_t length, const Value *values,
1.3288 + JSObject *proto /* = nullptr */, NewObjectKind newKind /* = GenericObject */)
1.3289 +{
1.3290 + ArrayObject* arr = NewArray<true>(cx, length, proto);
1.3291 + if (!arr)
1.3292 + return nullptr;
1.3293 +
1.3294 + JS_ASSERT(arr->getDenseCapacity() >= length);
1.3295 +
1.3296 + arr->setDenseInitializedLength(values ? length : 0);
1.3297 +
1.3298 + if (values)
1.3299 + arr->initDenseElements(0, values, length);
1.3300 +
1.3301 + return arr;
1.3302 +}
1.3303 +
1.3304 +ArrayObject *
1.3305 +js::NewDenseAllocatedArrayWithTemplate(JSContext *cx, uint32_t length, JSObject *templateObject)
1.3306 +{
1.3307 + gc::AllocKind allocKind = GuessArrayGCKind(length);
1.3308 + JS_ASSERT(CanBeFinalizedInBackground(allocKind, &ArrayObject::class_));
1.3309 + allocKind = GetBackgroundAllocKind(allocKind);
1.3310 +
1.3311 + RootedTypeObject type(cx, templateObject->type());
1.3312 + if (!type)
1.3313 + return nullptr;
1.3314 +
1.3315 + RootedShape shape(cx, templateObject->lastProperty());
1.3316 + if (!shape)
1.3317 + return nullptr;
1.3318 +
1.3319 + gc::InitialHeap heap = GetInitialHeap(GenericObject, &ArrayObject::class_);
1.3320 + Rooted<ArrayObject *> arr(cx, JSObject::createArray(cx, allocKind, heap, shape, type, length));
1.3321 + if (!arr)
1.3322 + return nullptr;
1.3323 +
1.3324 + if (!EnsureNewArrayElements(cx, arr, length))
1.3325 + return nullptr;
1.3326 +
1.3327 + probes::CreateObject(cx, arr);
1.3328 +
1.3329 + return arr;
1.3330 +}
1.3331 +
1.3332 +#ifdef DEBUG
1.3333 +bool
1.3334 +js_ArrayInfo(JSContext *cx, unsigned argc, Value *vp)
1.3335 +{
1.3336 + CallArgs args = CallArgsFromVp(argc, vp);
1.3337 + JSObject *obj;
1.3338 +
1.3339 + for (unsigned i = 0; i < args.length(); i++) {
1.3340 + RootedValue arg(cx, args[i]);
1.3341 +
1.3342 + char *bytes = DecompileValueGenerator(cx, JSDVG_SEARCH_STACK, arg, NullPtr());
1.3343 + if (!bytes)
1.3344 + return false;
1.3345 + if (arg.isPrimitive() ||
1.3346 + !(obj = arg.toObjectOrNull())->is<ArrayObject>()) {
1.3347 + fprintf(stderr, "%s: not array\n", bytes);
1.3348 + js_free(bytes);
1.3349 + continue;
1.3350 + }
1.3351 + fprintf(stderr, "%s: (len %u", bytes, obj->as<ArrayObject>().length());
1.3352 + fprintf(stderr, ", capacity %u", obj->getDenseCapacity());
1.3353 + fputs(")\n", stderr);
1.3354 + js_free(bytes);
1.3355 + }
1.3356 +
1.3357 + args.rval().setUndefined();
1.3358 + return true;
1.3359 +}
1.3360 +#endif
