Bug 1175111 - Fix enumeration order for indexed properties. r=jorendorff
authorJan de Mooij <jdemooij@mozilla.com>
Sat, 24 Oct 2015 20:59:50 +0200
changeset 304571 45dd451ce4ed9ccf912f57ee019b237becfc28b8
parent 304570 430fb98d29000430e6566c8187413ecca0ff1c0d
child 304572 778c44efbafacfae5fd2bcb84ef593e9d8b6ebb6
push id1001
push userraliiev@mozilla.com
push dateMon, 18 Jan 2016 19:06:03 +0000
treeherdermozilla-release@8b89261f3ac4 [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersjorendorff
bugs1175111
milestone44.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 1175111 - Fix enumeration order for indexed properties. r=jorendorff
js/src/jit-test/tests/basic/property-enumeration-order.js
js/src/jit-test/tests/ion/bug1060387.js
js/src/jsiter.cpp
new file mode 100644
--- /dev/null
+++ b/js/src/jit-test/tests/basic/property-enumeration-order.js
@@ -0,0 +1,37 @@
+function check(obj, expected, expectedAll = expected) {
+    assertEq(Reflect.ownKeys(obj).join(""), expectedAll);
+    assertEq(Object.getOwnPropertyNames(obj).join(""), expectedAll);
+    assertEq(Object.keys(obj).join(""), expected);
+    var s = "";
+    for (var x in obj)
+	s += x;
+    assertEq(s, expected);
+}
+
+var obj = {2: 0, 0: 0, "foo": "bar", 4: 0, "-5": 1};
+check(obj, "024foo-5");
+obj.x = 1;
+check(obj, "024foo-5x");
+obj[1] = 1;
+check(obj, "0124foo-5x");
+obj[1.2] = 1;
+check(obj, "0124foo-5x1.2");
+Object.defineProperty(obj, '3', {value:1,enumerable:false,configurable:false,writable:false});
+check(obj, "0124foo-5x1.2", "01234foo-5x1.2");
+delete obj[2];
+check(obj, "014foo-5x1.2", "0134foo-5x1.2");
+obj[2] = 1;
+check(obj, "0124foo-5x1.2", "01234foo-5x1.2");
+
+assertEq(JSON.stringify(obj), '{"0":0,"1":1,"2":1,"4":0,"foo":"bar","-5":1,"x":1,"1.2":1}');
+
+var arr = [1, 2, 3];
+Object.defineProperty(arr, '3', {value:1,enumerable:true,configurable:true,writable:true});
+check(arr, "0123", "0123length");
+Object.defineProperty(arr, '1000', {value:1,enumerable:true,configurable:true,writable:false});
+check(arr, "01231000", "01231000length");
+
+arr = [1, 2, , , 5];
+check(arr, "014", "014length");
+arr[0xfffffff] = 4;
+check(arr, "014268435455", "014268435455length");
--- a/js/src/jit-test/tests/ion/bug1060387.js
+++ b/js/src/jit-test/tests/ion/bug1060387.js
@@ -2,11 +2,11 @@ function foo() {
     var obj = new Object();
     var index = [-0, 2147483648, 1073741825];
     for (var j in index) {
         testProperty(index[j]);
     }
     function testProperty(i) {
         obj[i] = '' + i;
     }
-    assertEq(JSON.stringify(obj), '{"0":"0","2147483648":"2147483648","1073741825":"1073741825"}');
+    assertEq(JSON.stringify(obj), '{"0":"0","1073741825":"1073741825","2147483648":"2147483648"}');
 }
 foo();
--- a/js/src/jsiter.cpp
+++ b/js/src/jsiter.cpp
@@ -40,19 +40,17 @@
 #include "vm/String-inl.h"
 
 using namespace js;
 using namespace js::gc;
 using JS::ForOfIterator;
 
 using mozilla::ArrayLength;
 using mozilla::Maybe;
-#ifdef JS_MORE_DETERMINISTIC
 using mozilla::PodCopy;
-#endif
 using mozilla::PodZero;
 
 typedef Rooted<PropertyIteratorObject*> RootedPropertyIteratorObject;
 
 static const gc::AllocKind ITERATOR_FINALIZE_KIND = gc::AllocKind::OBJECT2_BACKGROUND;
 
 void
 NativeIterator::mark(JSTracer* trc)
@@ -133,57 +131,105 @@ Enumerate(JSContext* cx, HandleObject po
         return true;
     if (!enumerable && !(flags & JSITER_HIDDEN))
         return true;
 
     return props->append(id);
 }
 
 static bool
+SortComparatorIntegerIds(jsid a, jsid b, bool* lessOrEqualp)
+{
+    uint32_t indexA, indexB;
+    MOZ_ALWAYS_TRUE(IdIsIndex(a, &indexA));
+    MOZ_ALWAYS_TRUE(IdIsIndex(b, &indexB));
+    *lessOrEqualp = (indexA <= indexB);
+    return true;
+}
+
+static bool
 EnumerateNativeProperties(JSContext* cx, HandleNativeObject pobj, unsigned flags, Maybe<IdSet>& ht,
                           AutoIdVector* props)
 {
     bool enumerateSymbols;
     if (flags & JSITER_SYMBOLSONLY) {
         enumerateSymbols = true;
     } else {
         /* Collect any dense elements from this object. */
         size_t initlen = pobj->getDenseInitializedLength();
         const Value* vp = pobj->getDenseElements();
+        bool hasHoles = false;
         for (size_t i = 0; i < initlen; ++i, ++vp) {
-            if (!vp->isMagic(JS_ELEMENTS_HOLE)) {
+            if (vp->isMagic(JS_ELEMENTS_HOLE)) {
+                hasHoles = true;
+            } else {
                 /* Dense arrays never get so large that i would not fit into an integer id. */
                 if (!Enumerate(cx, pobj, INT_TO_JSID(i), /* enumerable = */ true, flags, ht, props))
                     return false;
             }
         }
 
         /* Collect any typed array or shared typed array elements from this object. */
         if (IsAnyTypedArray(pobj)) {
             size_t len = AnyTypedArrayLength(pobj);
             for (size_t i = 0; i < len; i++) {
                 if (!Enumerate(cx, pobj, INT_TO_JSID(i), /* enumerable = */ true, flags, ht, props))
                     return false;
             }
         }
 
+        // Collect any sparse elements from this object.
+        bool isIndexed = pobj->isIndexed();
+        if (isIndexed) {
+            size_t numElements = props->length();
+
+            for (Shape::Range<NoGC> r(pobj->lastProperty()); !r.empty(); r.popFront()) {
+                Shape& shape = r.front();
+                jsid id = shape.propid();
+                uint32_t dummy;
+                if (IdIsIndex(id, &dummy)) {
+                    if (!Enumerate(cx, pobj, id, shape.enumerable(), flags, ht, props))
+                        return false;
+                }
+            }
+
+            // If the dense elements didn't have holes, we don't need to include
+            // them in the sort.
+            size_t startIndex = hasHoles ? 0 : numElements;
+
+            jsid* ids = props->begin() + startIndex;
+            size_t n = props->length() - startIndex;
+
+            AutoIdVector tmp(cx);
+            if (!tmp.resize(n))
+                return false;
+            PodCopy(tmp.begin(), ids, n);
+
+            if (!MergeSort(ids, n, tmp.begin(), SortComparatorIntegerIds))
+                return false;
+        }
+
         size_t initialLength = props->length();
 
         /* Collect all unique property names from this object's shape. */
         bool symbolsFound = false;
         Shape::Range<NoGC> r(pobj->lastProperty());
         for (; !r.empty(); r.popFront()) {
             Shape& shape = r.front();
             jsid id = shape.propid();
 
             if (JSID_IS_SYMBOL(id)) {
                 symbolsFound = true;
                 continue;
             }
 
+            uint32_t dummy;
+            if (isIndexed && IdIsIndex(id, &dummy))
+                continue;
+
             if (!Enumerate(cx, pobj, id, shape.enumerable(), flags, ht, props))
                 return false;
         }
         ::Reverse(props->begin() + initialLength, props->end());
 
         enumerateSymbols = symbolsFound && (flags & JSITER_SYMBOLS);
     }