Bug 688852 - Rewrite Array.prototype.concat to use spec steps; r=Waldo
☠☠ backed out by 38e88a332eeb ☠ ☠
authorTerrence Cole <terrence@mozilla.com>
Thu, 03 Jan 2013 17:34:34 -0800
changeset 164371 e807ddf2965f621d2948a44b7631ebd6ee5d5135
parent 164370 8854b9662405a3ba43d731273b3800c24e6906aa
child 164372 368ed1ff1ae665b4d9b9357df8658064a45073ad
push id3066
push userakeybl@mozilla.com
push dateMon, 09 Dec 2013 19:58:46 +0000
treeherdermozilla-beta@a31a0dce83aa [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersWaldo
bugs688852
milestone27.0a1
first release with
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
last release without
nightly linux32
nightly linux64
nightly mac
nightly win32
nightly win64
Bug 688852 - Rewrite Array.prototype.concat to use spec steps; r=Waldo
js/public/CallArgs.h
js/src/jit-test/tests/arrays/concat-define-element.js
js/src/jit-test/tests/arrays/concat-dense-prototype-shadowing.js
js/src/jit-test/tests/arrays/concat-overflow.js
js/src/jit-test/tests/arrays/concat-use-correct-this.js
js/src/jsarray.cpp
--- a/js/public/CallArgs.h
+++ b/js/public/CallArgs.h
@@ -26,16 +26,17 @@
  * methods' implementations, potentially under time pressure.
  */
 
 #ifndef js_CallArgs_h
 #define js_CallArgs_h
 
 #include "mozilla/Assertions.h"
 #include "mozilla/Attributes.h"
+#include "mozilla/RangedPtr.h"
 #include "mozilla/TypeTraits.h"
 
 #include "jstypes.h"
 
 #include "js/RootingAPI.h"
 #include "js/Value.h"
 
 /* Typedef for native functions called by the JS VM. */
@@ -332,16 +333,24 @@ class MOZ_STACK_CLASS CallArgsBase :
     /*
      * Returns true if the i-th zero-indexed argument is present and is not
      * |undefined|.
      */
     bool hasDefined(unsigned i) const {
         return i < argc_ && !this->argv_[i].isUndefined();
     }
 
+    /*
+     * Returns thisv and args in a single array. (That is, a pointer to |this|
+     * followed by any provided arguments.)
+     */
+    mozilla::RangedPtr<const Value> thisAndArgs() const {
+        return mozilla::RangedPtr<const Value>(this->argv_ - 1, argc_ + 1);
+    }
+
   public:
     // These methods are publicly exposed, but we're less sure of the interface
     // here than we'd like (because they're hackish and drop assertions).  Try
     // to avoid using these if you can.
 
     Value *array() const { return this->argv_; }
     Value *end() const { return this->argv_ + argc_; }
 };
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/arrays/concat-define-element.js
@@ -0,0 +1,4 @@
+var bigarr = [];
+bigarr[5000] = 17;
+Object.defineProperty(Object.prototype, 5000, { set: function() { throw 42; } });
+assertEq([].concat(bigarr).length, 5001);
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/arrays/concat-dense-prototype-shadowing.js
@@ -0,0 +1,2 @@
+Object.prototype[0] = "foo";
+assertEq([/* hole */, 5].concat().hasOwnProperty("0"), true);
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/arrays/concat-overflow.js
@@ -0,0 +1,104 @@
+function testOverflowOneSplat() {
+    var threw = false;
+    var c;
+    try {
+        c = (new Array(4294967295)).concat(['a']);
+    } catch(e) {
+        threw = true;
+    }
+    assertEq(threw, false);
+    assertEq(c[4294967295], 'a');
+    assertEq(c.length, 0);
+}
+testOverflowOneSplat();
+
+function testOverflowOneArg() {
+    var threw = false;
+    var c;
+    try {
+        c = (new Array(4294967295)).concat('a');
+    } catch(e) {
+        threw = true;
+    }
+    assertEq(threw, false);
+    assertEq(c[4294967295], 'a');
+    assertEq(c.length, 0);
+}
+testOverflowOneArg();
+
+function testOverflowManySplat() {
+    var threw = false;
+    var c;
+    try {
+        c = (new Array(4294967294)).concat(['a', 'b', 'c']);
+    } catch(e) {
+        threw = true;
+    }
+    assertEq(threw, false);
+    assertEq(c[4294967294], 'a');
+    assertEq(c[4294967295], 'b');
+    assertEq(c[4294967296], 'c');
+    assertEq(c.length, 4294967295);
+}
+testOverflowManySplat();
+
+function testOverflowManyArg() {
+    var threw = false;
+    var c;
+    try {
+        c = (new Array(4294967294)).concat('a', 'b', 'c');
+    } catch(e) {
+        threw = true;
+    }
+    assertEq(threw, false);
+    assertEq(c[4294967294], 'a');
+    assertEq(c[4294967295], 'b');
+    assertEq(c[4294967296], 'c');
+    assertEq(c.length, 4294967295);
+}
+testOverflowManyArg();
+
+/*
+ * Ensure we run for side-effects, even when overflowing.
+ */
+var count;
+function MakeFunky() {
+    var o = new Array();
+    Object.defineProperty(o, "0", { get: function() { count++; return 'a'; } });
+    o.length = 1;
+    return o;
+}
+
+function testReadWhenOverflowing() {
+    count = 0;
+    var threw = false;
+    var c;
+    try {
+        c = (new Array(4294967294)).concat(MakeFunky(), MakeFunky(), MakeFunky());
+    } catch(e) {
+        threw = true;
+    }
+    assertEq(threw, false);
+    assertEq(c[4294967294], 'a');
+    assertEq(c[4294967295], 'a');
+    assertEq(c[4294967296], 'a');
+    assertEq(c.length, 4294967295);
+    assertEq(count, 3);
+}
+testReadWhenOverflowing();
+
+function testDenseFastpathCallsGetters() {
+    count = 0;
+    var threw = false;
+    var c;
+    try {
+        c = MakeFunky().concat([]);
+    } catch(e) {
+        threw = true;
+    }
+    assertEq(threw, false);
+    assertEq(c[0], 'a');
+    assertEq(c.length, 1);
+    assertEq(count, 1);
+}
+testDenseFastpathCallsGetters();
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/arrays/concat-use-correct-this.js
@@ -0,0 +1,2 @@
+assertEq(typeof (Array.prototype.concat).call("foo")[0], "object")
+assertEq(Array.prototype.concat.call("foo")[0] instanceof String, true);
--- a/js/src/jsarray.cpp
+++ b/js/src/jsarray.cpp
@@ -4,16 +4,17 @@
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #include "jsarray.h"
 
 #include "mozilla/DebugOnly.h"
 #include "mozilla/FloatingPoint.h"
 #include "mozilla/MathAlgorithms.h"
+#include "mozilla/RangedPtr.h"
 #include "mozilla/Util.h"
 
 #include "jsapi.h"
 #include "jsatom.h"
 #include "jsautooplen.h"
 #include "jscntxt.h"
 #include "jsfriendapi.h"
 #include "jsfun.h"
@@ -43,16 +44,17 @@ using namespace js::gc;
 using namespace js::types;
 
 using mozilla::Abs;
 using mozilla::ArrayLength;
 using mozilla::CeilingLog2;
 using mozilla::DebugOnly;
 using mozilla::IsNaN;
 using mozilla::PointerRangeSize;
+using mozilla::RangedPtr;
 
 bool
 js::GetLengthProperty(JSContext *cx, HandleObject obj, uint32_t *lengthp)
 {
     if (obj->is<ArrayObject>()) {
         *lengthp = obj->as<ArrayObject>().length();
         return true;
     }
@@ -298,16 +300,60 @@ SetArrayElement(JSContext *cx, HandleObj
     RootedId id(cx);
     if (!DoubleIndexToId(cx, index, &id))
         return false;
 
     RootedValue tmp(cx, v);
     return JSObject::setGeneric(cx, obj, obj, id, &tmp, true);
 }
 
+/**
+ * Calls [[DefineOwnProperty]] on the given object to create a writable,
+ * enumerable, configurable data property with the given value.  The property
+ * must not already exist on the object.
+ */
+static bool
+DefineElementNoConflict(JSContext *cx, HandleObject obj, double index, HandleValue v)
+{
+    JS_ASSERT(index >= 0);
+
+    if (obj->is<ArrayObject>() && !obj->isIndexed()) {
+        Rooted<ArrayObject*> arr(cx, &obj->as<ArrayObject>());
+        /* Predicted/prefetched code should favor the remains-dense case. */
+        JSObject::EnsureDenseResult result = JSObject::ED_SPARSE;
+        do {
+            if (index > uint32_t(-1))
+                break;
+            uint32_t idx = uint32_t(index);
+            if (idx >= arr->length() && !arr->lengthIsWritable()) {
+                JS_ReportErrorFlagsAndNumber(cx, JSREPORT_ERROR, js_GetErrorMessage, NULL,
+                                             JSMSG_CANT_REDEFINE_ARRAY_LENGTH);
+                return false;
+            }
+            result = arr->ensureDenseElements(cx, idx, 1);
+            if (result != JSObject::ED_OK)
+                break;
+            if (idx >= arr->length())
+                arr->setLengthInt32(idx + 1);
+            JSObject::setDenseElementWithType(cx, arr, idx, v);
+            return true;
+        } while (false);
+
+        if (result == JSObject::ED_FAILED)
+            return false;
+        JS_ASSERT(result == JSObject::ED_SPARSE);
+    }
+
+    RootedId id(cx);
+    if (!DoubleIndexToId(cx, index, &id))
+        return false;
+
+    return JSObject::defineGeneric(cx, obj, id, v);
+}
+
 /*
  * Attempt to delete the element |index| from |obj| as if by
  * |obj.[[Delete]](index)|.
  *
  * If an error occurs while attempting to delete the element (that is, the call
  * to [[Delete]] threw), return false.
  *
  * Otherwise set *succeeded to indicate whether the deletion attempt succeeded
@@ -2588,90 +2634,99 @@ js::array_concat_dense(JSContext *cx, Ha
 
     result->initDenseElements(0, arr1->getDenseElements(), initlen1);
     result->initDenseElements(initlen1, arr2->getDenseElements(), initlen2);
     result->setLengthInt32(len);
     return true;
 }
 #endif /* JS_ION */
 
-/*
- * Python-esque sequence operations.
- */
+/* ES5 15.4.4.4. */
 bool
 js::array_concat(JSContext *cx, unsigned argc, Value *vp)
 {
     CallArgs args = CallArgsFromVp(argc, vp);
 
-    /* Treat our |this| object as the first argument; see ECMA 15.4.4.4. */
-    Value *p = args.array() - 1;
-
-    /* Create a new Array object and root it using *vp. */
-    RootedObject aobj(cx, ToObject(cx, args.thisv()));
-    if (!aobj)
+    /* Step 1. */
+    RootedObject obj(cx, ToObject(cx, args.thisv()));
+    if (!obj)
         return false;
 
-    Rooted<ArrayObject*> narr(cx);
-    uint32_t length;
-    if (aobj->is<ArrayObject>() && !aobj->isIndexed()) {
-        length = aobj->as<ArrayObject>().length();
-        uint32_t initlen = aobj->getDenseInitializedLength();
-        narr = NewDenseCopiedArray(cx, initlen, aobj, 0);
-        if (!narr)
+    /* Step 3-4. */
+    double n = 0;
+    size_t nitems = args.length() + 1;
+    RangedPtr<const Value> items = args.thisAndArgs();
+
+    /* Iterate the modified |this| and not the original. */
+    args.setThis(ObjectValue(*obj));
+
+    /*
+     * Step 2. This may alse inline the first iteration of Step 5 if it is
+     * possible to perform a fast, dense copy.
+     */
+    Rooted<ArrayObject*> arr(cx);
+    if (obj->is<ArrayObject>() && !ObjectMayHaveExtraIndexedProperties(obj)) {
+        uint32_t initlen = obj->getDenseInitializedLength();
+        arr = NewDenseCopiedArray(cx, initlen, obj, 0);
+        if (!arr)
             return false;
-        TryReuseArrayType(aobj, narr);
-        ArrayObject::setLength(cx, narr, length);
-        args.rval().setObject(*narr);
-        if (argc == 0)
-            return true;
-        argc--;
-        p++;
+        TryReuseArrayType(obj, arr);
+        n = obj->as<ArrayObject>().length();
+        items++;
+        nitems--;
     } else {
-        narr = NewDenseEmptyArray(cx);
-        if (!narr)
+        arr = NewDenseEmptyArray(cx);
+        if (!arr)
             return false;
-        args.rval().setObject(*narr);
-        length = 0;
     }
 
-    /* Loop over [0, argc] to concat args into narr, expanding all Arrays. */
-    for (unsigned i = 0; i <= argc; i++) {
+    /* Step 5. */
+    RootedObject elemObj(cx);
+    RootedValue subElement(cx);
+    for (; nitems > 0; --nitems, ++items) {
+        HandleValue elem = HandleValue::fromMarkedLocation(&*items);
+
         if (!JS_CHECK_OPERATION_LIMIT(cx))
             return false;
-        HandleValue v = HandleValue::fromMarkedLocation(&p[i]);
-        if (v.isObject()) {
-            RootedObject obj(cx, &v.toObject());
-            if (ObjectClassIs(obj, ESClass_Array, cx)) {
-                uint32_t alength;
-                if (!GetLengthProperty(cx, obj, &alength))
+
+        /* Step 5b. */
+        if (IsObjectWithClass(elem, ESClass_Array, cx)) {
+            elemObj = &elem.toObject();
+
+            /* Step 5b(ii). */
+            uint32_t len;
+            if (!GetLengthProperty(cx, elemObj, &len))
+                return false;
+
+            /* Step 5b(i), 5b(iii). */
+            for (uint32_t k = 0; k < len; ++k) {
+                if (!JS_CHECK_OPERATION_LIMIT(cx))
+                    return false;
+
+                bool exists;
+                if (!JSObject::getElementIfPresent(cx, elemObj, elemObj, k, &subElement, &exists))
                     return false;
-                RootedValue tmp(cx);
-                for (uint32_t slot = 0; slot < alength; slot++) {
-                    bool hole;
-                    if (!JS_CHECK_OPERATION_LIMIT(cx) || !GetElement(cx, obj, slot, &hole, &tmp))
-                        return false;
-
-                    /*
-                     * Per ECMA 262, 15.4.4.4, step 9, ignore nonexistent
-                     * properties.
-                     */
-                    if (!hole && !SetArrayElement(cx, narr, length + slot, tmp))
-                        return false;
-                }
-                length += alength;
-                continue;
+
+                if (exists && !DefineElementNoConflict(cx, arr, n + k, subElement))
+                    return false;
             }
+            n += len;
+        } else {
+            /* Step 5c(i). */
+            if (!DefineElementNoConflict(cx, arr, n, elem))
+                return false;
+
+            /* Step 5c(ii). */
+            n++;
         }
-
-        if (!SetArrayElement(cx, narr, length, v))
-            return false;
-        length++;
     }
 
-    return SetLengthProperty(cx, narr, length);
+    /* Step 6. */
+    args.rval().setObject(*arr);
+    return true;
 }
 
 static bool
 array_slice(JSContext *cx, unsigned argc, Value *vp)
 {
     uint32_t length, begin, end, slot;
     bool hole;