Bug 595963: notify iterators about property deletion in array_splice, r=gal
☠☠ backed out by d2d4a7115949 ☠ ☠
authorDavid Mandelin <dmandelin@mozilla.com>
Fri, 01 Oct 2010 11:12:01 -0700
changeset 55465 97d2c33271e8c7a36144a3aae366922ceb32fcda
parent 55464 1283831c28bf74b8770b0ba9adb18518c39318db
child 55466 9f36af4e3a8a29aebfa093214996cf37ebd5fea4
child 55475 d2d4a7115949ad8793fc8c97e87d0b00d3da9080
push id16269
push userjst@mozilla.com
push dateThu, 14 Oct 2010 01:40:35 +0000
treeherdermozilla-central@29c228a4d7eb [default view] [failures only]
perfherder[talos] [build metrics] [platform microbench] (compared to previous push)
reviewersgal
bugs595963
milestone2.0b7pre
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 595963: notify iterators about property deletion in array_splice, r=gal
js/src/jsarray.cpp
js/src/jsiter.cpp
js/src/jsiter.h
js/src/trace-test/tests/basic/bug595963-1.js
js/src/trace-test/tests/basic/bug595963-2.js
--- a/js/src/jsarray.cpp
+++ b/js/src/jsarray.cpp
@@ -2333,16 +2333,17 @@ array_splice(JSContext *cx, uintN argc, 
 
     /* Nothing to do if no args.  Otherwise get length. */
     if (argc == 0)
         return JS_TRUE;
     Value *argv = JS_ARGV(cx, vp);
     JSObject *obj = ComputeThisFromVp(cx, vp);
     if (!obj || !js_GetLengthProperty(cx, obj, &length))
         return JS_FALSE;
+    jsuint origlength = length;
 
     /* Convert the first argument into a starting index. */
     jsdouble d;
     if (!ValueToNumber(cx, *argv, &d))
         return JS_FALSE;
     d = js_DoubleToInteger(d);
     if (d < 0) {
         d += length;
@@ -2447,16 +2448,19 @@ array_splice(JSContext *cx, uintN argc, 
                     !SetOrDeleteArrayElement(cx, obj, last - delta, hole, tvr.value())) {
                     return JS_FALSE;
                 }
             }
         }
         length -= delta;
     }
 
+    if (length < origlength && !js_SuppressDeletedIndexProperties(cx, obj, length, origlength))
+        return JS_FALSE;
+
     /*
      * Copy from argv into the hole to complete the splice, and update length in
      * case we deleted elements from the end.
      */
     return InitArrayElements(cx, obj, begin, argc, argv) &&
            js_SetLengthProperty(cx, obj, length);
 }
 
--- a/js/src/jsiter.cpp
+++ b/js/src/jsiter.cpp
@@ -866,89 +866,130 @@ js_CloseIterator(JSContext *cx, JSObject
     else if (clasp == &js_GeneratorClass) {
         return CloseGenerator(cx, obj);
     }
 #endif
     return JS_TRUE;
 }
 
 /*
- * Suppress enumeration of deleted properties. We maintain a list of all active
- * non-escaping for-in enumerators. Whenever a property is deleted, we check
- * whether any active enumerator contains the (obj, id) pair and has not
- * enumerated id yet. If so, we delete the id from the list (or advance the
- * cursor if it is the next id to be enumerated).
+ * Suppress enumeration of deleted properties. This function must be called
+ * when a property is deleted and there might be active enumerators. 
+ *
+ * We maintain a list of active non-escaping for-in enumerators. To suppress
+ * a property, we check whether each active enumerator contains the (obj, id)
+ * pair and has not yet enumerated |id|. If so, and |id| is the next property,
+ * we simply advance the cursor. Otherwise, we delete |id| from the list.
  *
  * We do not suppress enumeration of a property deleted along an object's
  * prototype chain. Only direct deletions on the object are handled.
+ *
+ * This function can suppress multiple properties at once. The |predicate|
+ * argument is an object which can be called on an id and returns true or
+ * false. It also must have a method |matchesAtMostOne| which allows us to
+ * stop searching after the first deletion if true.
  */
-bool
-js_SuppressDeletedProperty(JSContext *cx, JSObject *obj, jsid id)
+template<typename IdPredicate>
+static bool
+SuppressDeletedPropertyHelper(JSContext *cx, JSObject *obj, IdPredicate predicate)
 {
     JSObject *iterobj = cx->enumerators;
     while (iterobj) {
       again:
         NativeIterator *ni = iterobj->getNativeIterator();
         /* This only works for identified surpressed keys, not values. */
         if (ni->isKeyIter() && ni->obj == obj && ni->props_cursor < ni->props_end) {
             /* Check whether id is still to come. */
             jsid *props_cursor = ni->currentKey();
             jsid *props_end = ni->endKey();
             for (jsid *idp = props_cursor; idp < props_end; ++idp) {
-                if (*idp == id) {
+                if (predicate(*idp)) {
                     /*
                      * Check whether another property along the prototype chain
                      * became visible as a result of this deletion.
                      */
                     if (obj->getProto()) {
                         AutoObjectRooter proto(cx, obj->getProto());
                         AutoObjectRooter obj2(cx);
                         JSProperty *prop;
-                        if (!proto.object()->lookupProperty(cx, id, obj2.addr(), &prop))
+                        if (!proto.object()->lookupProperty(cx, *idp, obj2.addr(), &prop))
                             return false;
                         if (prop) {
                             uintN attrs;
                             if (obj2.object()->isNative()) {
                                 attrs = ((Shape *) prop)->attributes();
                                 JS_UNLOCK_OBJ(cx, obj2.object());
-                            } else if (!obj2.object()->getAttributes(cx, id, &attrs)) {
+                            } else if (!obj2.object()->getAttributes(cx, *idp, &attrs)) {
                                 return false;
                             }
                             if (attrs & JSPROP_ENUMERATE)
                                 continue;
                         }
                     }
 
                     /*
                      * If lookupProperty or getAttributes above removed a property from
                      * ni, start over.
                      */
                     if (props_end != ni->props_end || props_cursor != ni->props_cursor)
                         goto again;
 
                     /*
-                     * No property along the prototype chain steppeded in to take the
+                     * No property along the prototype chain stepped in to take the
                      * property's place, so go ahead and delete id from the list.
                      * If it is the next property to be enumerated, just skip it.
                      */
                     if (idp == props_cursor) {
                         ni->incKeyCursor();
                     } else {
                         memmove(idp, idp + 1, (props_end - (idp + 1)) * sizeof(jsid));
                         ni->props_end = ni->endKey() - 1;
                     }
-                    break;
+                    if (predicate.matchesAtMostOne())
+                        break;
                 }
             }
         }
         iterobj = ni->next;
     }
     return true;
 }
 
+class SingleIdPredicate {
+    jsid id;
+public:
+    SingleIdPredicate(jsid id) : id(id) {}
+
+    bool operator()(jsid id) { return id == this->id; }
+    bool matchesAtMostOne() { return true; }
+};
+
+bool
+js_SuppressDeletedProperty(JSContext *cx, JSObject *obj, jsid id)
+{
+    return SuppressDeletedPropertyHelper(cx, obj, SingleIdPredicate(id));
+}
+
+class IndexRangePredicate {
+    jsint begin, end;
+public:
+    IndexRangePredicate(jsint begin, jsint end) : begin(begin), end(end) {}
+
+    bool operator()(jsid id) { 
+        return JSID_IS_INT(id) && begin <= JSID_TO_INT(id) && JSID_TO_INT(id) < end;
+    }
+    bool matchesAtMostOne() { return false; }
+};
+
+bool
+js_SuppressDeletedIndexProperties(JSContext *cx, JSObject *obj, jsint begin, jsint end)
+{
+    return SuppressDeletedPropertyHelper(cx, obj, IndexRangePredicate(begin, end));
+}
+
 JSBool
 js_IteratorMore(JSContext *cx, JSObject *iterobj, Value *rval)
 {
     /* Fast path for native iterators */
     if (iterobj->getClass() == &js_IteratorClass) {
         /*
          * Implement next directly as all the methods of native iterator are
          * read-only and permanent.
--- a/js/src/jsiter.h
+++ b/js/src/jsiter.h
@@ -166,16 +166,19 @@ extern JS_FRIEND_API(JSBool)
 js_ValueToIterator(JSContext *cx, uintN flags, js::Value *vp);
 
 extern JS_FRIEND_API(JSBool)
 js_CloseIterator(JSContext *cx, JSObject *iterObj);
 
 bool
 js_SuppressDeletedProperty(JSContext *cx, JSObject *obj, jsid id);
 
+bool
+js_SuppressDeletedIndexProperties(JSContext *cx, JSObject *obj, jsint begin, jsint end);
+
 /*
  * IteratorMore() indicates whether another value is available. It might
  * internally call iterobj.next() and then cache the value until its
  * picked up by IteratorNext(). The value is cached in the current context.
  */
 extern JSBool
 js_IteratorMore(JSContext *cx, JSObject *iterobj, js::Value *rval);
 
new file mode 100644
--- /dev/null
+++ b/js/src/trace-test/tests/basic/bug595963-1.js
@@ -0,0 +1,19 @@
+function remove(k, L) {
+  for (var i in k) {
+    if (i == L)
+      k.splice(L, 1);
+  }
+}
+function f(k) {
+  var L = 0;
+  for (var i in k) {
+    if (L == 1)
+      remove(k, L);
+    L++;
+    assertEq(k[i], 3);
+  }
+  assertEq(L, 6);
+}
+
+var a = [3, 3, 3, 3, 3, 3, 3];
+f(a);
new file mode 100644
--- /dev/null
+++ b/js/src/trace-test/tests/basic/bug595963-2.js
@@ -0,0 +1,19 @@
+function remove(k, L) {
+  for (var i in k) {
+    if (i == L)
+      k.splice(L, 3);
+  }
+}
+function f(k) {
+  var L = 0;
+  for (var i in k) {
+    if (L == 1)
+      remove(k, L);
+    L++;
+    assertEq(k[i], 3);
+  }
+  assertEq(L, 4);
+}
+
+var a = [3, 3, 3, 3, 3, 3, 3];
+f(a);