Suppress deleted properties during iteration (569735, r=brendan).
☠☠ backed out by 2fe89784cf66 ☠ ☠
authorAndreas Gal <gal@mozilla.com>
Wed, 02 Jun 2010 20:11:56 -0700
changeset 43257 96dbe8a784f15719031a8716921ad50a86650a15
parent 43256 331702c6884fcdd54bb3d95d50f132545a6200bb
child 43258 0a5778b1355b182451493c52a73b1de34de54577
push idunknown
push userunknown
push dateunknown
reviewersbrendan
bugs569735
milestone1.9.3a5pre
Suppress deleted properties during iteration (569735, r=brendan).
js/src/jsarray.cpp
js/src/jscntxt.h
js/src/jsiter.cpp
js/src/jsiter.h
js/src/jsobj.cpp
js/src/jsproxy.cpp
--- a/js/src/jsarray.cpp
+++ b/js/src/jsarray.cpp
@@ -97,16 +97,17 @@
 #include "jsbuiltins.h"
 #include "jscntxt.h"
 #include "jsversion.h"
 #include "jsdbgapi.h" /* for js_TraceWatchPoints */
 #include "jsdtoa.h"
 #include "jsfun.h"
 #include "jsgc.h"
 #include "jsinterp.h"
+#include "jsiter.h"
 #include "jslock.h"
 #include "jsnum.h"
 #include "jsobj.h"
 #include "jsscope.h"
 #include "jsstr.h"
 #include "jsstaticcheck.h"
 #include "jsvector.h"
 
@@ -1046,16 +1047,19 @@ array_deleteProperty(JSContext *cx, JSOb
     }
 
     if (js_IdIsIndex(id, &i) && i < obj->getDenseArrayCapacity() &&
         obj->getDenseArrayElement(i) != JSVAL_HOLE) {
         obj->decDenseArrayCountBy(1);
         obj->setDenseArrayElement(i, JSVAL_HOLE);
     }
 
+    if (!js_SuppressDeletedProperty(cx, obj, id))
+        return false;
+
     *rval = JSVAL_TRUE;
     return JS_TRUE;
 }
 
 static void
 array_finalize(JSContext *cx, JSObject *obj)
 {
     obj->freeDenseArrayElements(cx);
--- a/js/src/jscntxt.h
+++ b/js/src/jscntxt.h
@@ -1028,16 +1028,19 @@ struct JSThreadData {
     } dtoaCache;
 
     /* Cached native iterators. */
     JSObject            *cachedNativeIterators[NATIVE_ITER_CACHE_SIZE];
 
     /* Base address of the native stack for the current thread. */
     jsuword             *nativeStackBase;
 
+    /* List of currently active non-escaping enumerators (for-in). */
+    JSObject            *enumerators;
+
     bool init();
     void finish();
     void mark(JSTracer *trc);
     void purge(JSContext *cx);
     void purgeGCFreeLists();
 };
 
 #ifdef JS_THREADSAFE
--- a/js/src/jsiter.cpp
+++ b/js/src/jsiter.cpp
@@ -102,16 +102,17 @@ JSExtendedClass js_IteratorClass = {
 
 void
 NativeIterator::mark(JSTracer *trc)
 {
     for (jsval *vp = props_array; vp < props_end; ++vp) {
         JS_SET_TRACING_INDEX(trc, "props", (vp - props_array));
         js_CallValueTracerIfGCThing(trc, *vp);
     }
+    JS_CALL_OBJECT_TRACER(trc, obj, "obj");
 }
 
 /*
  * Shared code to close iterator's state either through an explicit call or
  * when GC detects that the iterator is no longer reachable.
  */
 static void
 iterator_finalize(JSContext *cx, JSObject *obj)
@@ -225,23 +226,24 @@ EnumerateDenseArrayProperties(JSContext 
                     return false;
             }
         }
     }
     return true;
 }
 
 NativeIterator *
-NativeIterator::allocate(JSContext *cx, uintN flags, uint32 *sarray, uint32 slength, uint32 key,
-                         jsval *parray, uint32 plength)
+NativeIterator::allocate(JSContext *cx, JSObject *obj, uintN flags, uint32 *sarray, uint32 slength,
+                         uint32 key, jsval *parray, uint32 plength)
 {
     NativeIterator *ni = (NativeIterator *)
         cx->malloc(sizeof(NativeIterator) + plength * sizeof(jsval) + slength * sizeof(uint32));
     if (!ni)
         return NULL;
+    ni->obj = obj;
     ni->props_array = ni->props_cursor = (jsval *) (ni + 1);
     ni->props_end = ni->props_array + plength;
     if (plength)
         memcpy(ni->props_array, parray, plength * sizeof(jsval));
     ni->shapes_array = (uint32 *) ni->props_end;
     ni->shapes_length = slength;
     ni->shapes_key = key;
     ni->flags = flags;
@@ -310,17 +312,17 @@ Snapshot(JSContext *cx, JSObject *obj, u
         }
 
         if (JS_UNLIKELY(pobj->isXML() || (flags & JSITER_OWNONLY)))
             break;
 
         pobj = pobj->getProto();
     }
 
-    return NativeIterator::allocate(cx, flags, sarray, slength, key, props.begin(), props.length());
+    return NativeIterator::allocate(cx, obj, flags, sarray, slength, key, props.begin(), props.length());
 }
 
 bool
 NativeIteratorToJSIdArray(JSContext *cx, NativeIterator *ni, JSIdArray **idap)
 {
     /* Morph the NativeIterator into a JSIdArray. The caller will deallocate it. */
     JS_ASSERT(sizeof(NativeIterator) > sizeof(JSIdArray));
     JS_ASSERT(ni->props_array == (jsid *) (ni + 1));
@@ -394,31 +396,44 @@ Compare(T *a, T *b, size_t c)
 static JSObject *
 NewIteratorObject(JSContext *cx, uintN flags)
 {
     return !(flags & JSITER_ENUMERATE)
            ? NewObject(cx, &js_IteratorClass.base, NULL, NULL)
            : NewObjectWithGivenProto(cx, &js_IteratorClass.base, NULL, NULL);
 }
 
+static inline void
+RegisterEnumerator(JSContext *cx, JSObject *iterobj, NativeIterator *ni)
+{
+    /* Register non-escaping native enumerators (for-in) with the current thread. */
+    if (ni->flags & JSITER_ENUMERATE) {
+        JSThreadData *data = JS_THREAD_DATA(cx);
+        ni->next = data->enumerators;
+        data->enumerators = iterobj;
+    }
+}
+
 bool
-JSIdArrayToIterator(JSContext *cx, uintN flags, JSIdArray *ida, jsval *vp)
+JSIdArrayToIterator(JSContext *cx, JSObject *obj, uintN flags, JSIdArray *ida, jsval *vp)
 {
     JSObject *iterobj = NewIteratorObject(cx, flags);
     if (!iterobj)
         return false;
 
     *vp = OBJECT_TO_JSVAL(iterobj);
 
-    NativeIterator *ni = NativeIterator::allocate(cx, flags, NULL, 0, 0,
+    NativeIterator *ni = NativeIterator::allocate(cx, obj, flags, NULL, 0, 0,
                                                   ida->vector, ida->length);
     if (!ni)
         return false;
 
     iterobj->setNativeIterator(ni);
+
+    RegisterEnumerator(cx, iterobj, ni);
     return true;
 }
 
 bool
 GetIterator(JSContext *cx, JSObject *obj, uintN flags, jsval *vp)
 {
     uint32 hash;
     JSObject **hp;
@@ -455,16 +470,18 @@ GetIterator(JSContext *cx, JSObject *obj
             JSObject *iterobj = *hp;
             if (iterobj) {
                 NativeIterator *ni = iterobj->getNativeIterator();
                 if (ni->shapes_key == key &&
                     ni->shapes_length == shapes.length() &&
                     Compare(ni->shapes_array, shapes.begin(), ni->shapes_length)) {
                     *vp = OBJECT_TO_JSVAL(iterobj);
                     *hp = ni->next;
+
+                    RegisterEnumerator(cx, iterobj, ni);
                     return true;
                 }
             }
         }
 
       miss:
         if (obj->isProxy())
             return JSProxy::iterate(cx, obj, flags, vp);
@@ -481,16 +498,18 @@ GetIterator(JSContext *cx, JSObject *obj
     /* Store in *vp to protect it from GC (callers must root vp). */
     *vp = OBJECT_TO_JSVAL(iterobj);
 
     NativeIterator *ni = Snapshot(cx, obj, flags, shapes.begin(), shapes.length(), key);
     if (!ni)
         return false;
 
     iterobj->setNativeIterator(ni);
+
+    RegisterEnumerator(cx, iterobj, ni);
     return true;
 }
 
 static JSObject *
 iterator_iterator(JSContext *cx, JSObject *obj, JSBool keysonly)
 {
     return obj;
 }
@@ -622,18 +641,25 @@ js_CloseIterator(JSContext *cx, jsval v)
 
     cx->iterValue = JSVAL_HOLE;
 
     JS_ASSERT(!JSVAL_IS_PRIMITIVE(v));
     obj = JSVAL_TO_OBJECT(v);
     clasp = obj->getClass();
 
     if (clasp == &js_IteratorClass.base) {
+        /* Remove enumerators from the active list, which is a stack. */
+        NativeIterator *ni = obj->getNativeIterator();
+        if (ni->flags & JSITER_ENUMERATE) {
+            JSThreadData *data = JS_THREAD_DATA(cx);
+            JS_ASSERT(data->enumerators == obj);
+            data->enumerators = ni->next;
+        }
+
         /* Cache the iterator object if possible. */
-        NativeIterator *ni = obj->getNativeIterator();
         if (ni->shapes_length) {
             uint32 hash = ni->shapes_key % NATIVE_ITER_CACHE_SIZE;
             JSObject **hp = &JS_THREAD_DATA(cx)->cachedNativeIterators[hash];
             ni->props_cursor = ni->props_array;
             ni->next = *hp;
             *hp = obj;
         } else {
             iterator_finalize(cx, obj);
@@ -642,16 +668,77 @@ js_CloseIterator(JSContext *cx, jsval v)
 #if JS_HAS_GENERATORS
     else if (clasp == &js_GeneratorClass.base) {
         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).
+ *
+ * We do not suppress enumeration of a property deleted along an object's
+ * prototype chain. Only direct deletions on the object are handled.
+ */
+bool
+js_SuppressDeletedProperty(JSContext *cx, JSObject *obj, jsid id)
+{
+    JSObject *iterobj = JS_THREAD_DATA(cx)->enumerators;
+    while (iterobj) {
+        NativeIterator *ni = iterobj->getNativeIterator();
+        if (ni->obj == obj && ni->props_cursor < ni->props_end) {
+            /* Check whether id is still to come. */
+            for (jsid *idp = ni->props_cursor; idp < ni->props_end; ++idp) {
+                if (*idp == id) {
+                    /*
+                     * 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))
+                            return false;
+                        if (obj2.object()) {
+                            uintN attrs;
+                            JSBool ok = obj2.object()->getAttributes(cx, id, prop, &attrs);
+                            obj2.object()->dropProperty(cx, prop);
+                            if (!ok)
+                                return false;
+                            if (attrs & JSPROP_ENUMERATE)
+                                continue;
+                        }
+                    }
+
+                    /*
+                     * No property along the prototype chain steppeded 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 == ni->props_cursor) {
+                        ni->props_cursor++;
+                    } else {
+                        memmove(idp, idp + 1, (ni->props_end - (idp + 1)) * sizeof(jsid));
+                        ni->props_end--;
+                    }
+                    break;
+                }
+            }
+        }
+        iterobj = ni->next;
+    }
+    return true;
+}
+
 JSBool
 js_IteratorMore(JSContext *cx, JSObject *iterobj, jsval *rval)
 {
     /* Fast path for native iterators */
     if (iterobj->getClass() == &js_IteratorClass.base) {
         /*
          * 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
@@ -56,26 +56,27 @@ JS_BEGIN_EXTERN_C
  */
 #define JSITER_ENUMERATE  0x1   /* for-in compatible hidden default iterator */
 #define JSITER_FOREACH    0x2   /* return [key, value] pair rather than key */
 #define JSITER_KEYVALUE   0x4   /* destructuring for-in wants [key, value] */
 #define JSITER_OWNONLY    0x8   /* iterate over obj's own properties only */
 #define JSITER_HIDDEN     0x10  /* also enumerate non-enumerable properties */
 
 struct NativeIterator {
+    JSObject  *obj;
     jsval     *props_array;
     jsval     *props_cursor;
     jsval     *props_end;
     uint32    *shapes_array;
     uint32    shapes_length;
     uint32    shapes_key;
     uintN     flags;
     JSObject  *next;
 
-    static NativeIterator *allocate(JSContext *cx, uintN flags,
+    static NativeIterator *allocate(JSContext *cx, JSObject *obj, uintN flags,
                                     uint32 *sarray, uint32 slength, uint32 key,
                                     jsval *parray, uint32 plength);
 
     void mark(JSTracer *trc);
 };
 
 /*
  * Magic jsval that indicates that a custom enumerate hook forwarded
@@ -86,30 +87,33 @@ static const jsval JSVAL_NATIVE_ENUMERAT
 
 bool
 GetPropertyNames(JSContext *cx, JSObject *obj, uintN flags, JSIdArray **idap);
 
 bool
 GetIterator(JSContext *cx, JSObject *obj, uintN flags, jsval *vp);
 
 bool
-JSIdArrayToIterator(JSContext *cx, uintN flags, JSIdArray *ida, jsval *vp);
+JSIdArrayToIterator(JSContext *cx, JSObject *obj, uintN flags, JSIdArray *ida, jsval *vp);
 
 /*
  * Convert the value stored in *vp to its iteration object. The flags should
  * contain JSITER_ENUMERATE if js_ValueToIterator is called when enumerating
  * for-in semantics are required, and when the caller can guarantee that the
  * iterator will never be exposed to scripts.
  */
 extern JS_FRIEND_API(JSBool)
 js_ValueToIterator(JSContext *cx, uintN flags, jsval *vp);
 
 extern JS_FRIEND_API(JSBool)
 js_CloseIterator(JSContext *cx, jsval v);
 
+bool
+js_SuppressDeletedProperty(JSContext *cx, JSObject *obj, jsid id);
+
 /*
  * 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, jsval *rval);
 
--- a/js/src/jsobj.cpp
+++ b/js/src/jsobj.cpp
@@ -59,16 +59,17 @@
 #include "jsbool.h"
 #include "jsbuiltins.h"
 #include "jscntxt.h"
 #include "jsversion.h"
 #include "jsemit.h"
 #include "jsfun.h"
 #include "jsgc.h"
 #include "jsinterp.h"
+#include "jsiter.h"
 #include "jslock.h"
 #include "jsnum.h"
 #include "jsobj.h"
 #include "jsopcode.h"
 #include "jsparse.h"
 #include "jsproxy.h"
 #include "jsscope.h"
 #include "jsscript.h"
@@ -5320,17 +5321,18 @@ js_DeleteProperty(JSContext *cx, JSObjec
     }
 
     scope = obj->scope();
     if (SPROP_HAS_VALID_SLOT(sprop, scope))
         GC_POKE(cx, obj->lockedGetSlot(sprop->slot));
 
     ok = scope->removeProperty(cx, id);
     obj->dropProperty(cx, prop);
-    return ok;
+
+    return ok && js_SuppressDeletedProperty(cx, obj, id);
 }
 
 JSBool
 js_DefaultValue(JSContext *cx, JSObject *obj, JSType hint, jsval *vp)
 {
     jsval v, save;
     JSString *str;
 
--- a/js/src/jsproxy.cpp
+++ b/js/src/jsproxy.cpp
@@ -172,17 +172,17 @@ JSProxyHandler::enumerateOwn(JSContext *
 
 bool
 JSProxyHandler::iterate(JSContext *cx, JSObject *proxy, uintN flags, jsval *vp)
 {
     JSIdArray *ida;
     if (!enumerate(cx, proxy, &ida))
         return false;
     AutoIdArray idar(cx, ida);
-    return JSIdArrayToIterator(cx, flags, ida, vp);
+    return JSIdArrayToIterator(cx, proxy, flags, ida, vp);
 }
 
 void
 JSProxyHandler::finalize(JSContext *cx, JSObject *proxy)
 {
 }
 
 void