Bug 613066: Update structured clone algorithm to the latest spec. r=jorendorff
authorKyle Huey <khuey@kylehuey.com>
Thu, 16 Jun 2011 11:22:37 -0700
changeset 71888 16b6d006a3fe44a58ced44f4e9ed7882a80fc517
parent 71887 0c1bdce6b0d2382ef4d9db730b62b0a352c3501a
child 71889 8b3dc129aed843be1da384c659c098db80cb42e5
push idunknown
push userunknown
push dateunknown
reviewersjorendorff
bugs613066
milestone7.0a1
Bug 613066: Update structured clone algorithm to the latest spec. r=jorendorff
dom/src/threads/test/json_worker.js
dom/tests/mochitest/whatwg/postMessage_structured_clone_helper.html
dom/tests/mochitest/whatwg/postMessage_structured_clone_helper.js
js/src/jsclone.cpp
js/src/jsclone.h
js/src/jscntxt.h
js/src/tests/js1_8_5/extensions/clone-complex-object.js
js/src/tests/js1_8_5/extensions/clone-errors.js
js/src/tests/js1_8_5/extensions/clone-object.js
js/src/tests/js1_8_5/extensions/jstests.list
--- a/dom/src/threads/test/json_worker.js
+++ b/dom/src/threads/test/json_worker.js
@@ -73,42 +73,37 @@ var messages = [
   {
     type: "object",
     value: {foo: "bar", foo2: [1,2,3]},
     jsonValue: '{"foo":"bar","foo2":[1,2,3]}'
   },
   {
     type: "object",
     value: cyclicalObject,
-    exception: true
   },
   {
     type: "object",
     value: [null, 2, false, cyclicalObject],
-    exception: true
   },
   {
     type: "object",
     value: cyclicalArray,
-    exception: true
   },
   {
     type: "object",
     value: {foo: 1, bar: cyclicalArray},
-    exception: true
   },
   {
     type: "object",
     value: crazyNestedObject,
     jsonValue: JSON.stringify(crazyNestedObject)
   },
   {
     type: "object",
     value: crazyCyclicalObject,
-    exception: true
   },
   {
     type: "object",
     value: objectWithSaneGetter,
     jsonValue: '{"foo":5}'
   },
   {
     type: "object",
--- a/dom/tests/mochitest/whatwg/postMessage_structured_clone_helper.html
+++ b/dom/tests/mochitest/whatwg/postMessage_structured_clone_helper.html
@@ -1,43 +1,104 @@
 <!DOCTYPE html>
 <html>
 <head>
   <title>postMessage structured clone page</title>
   <script type="application/javascript;version=1.7"
           src="postMessage_structured_clone_helper.js"></script>
-  <script type="application/javascript">
+  <script type="application/javascript;version=1.7">
     var generator = new getTestContent()
 
-    function eq(lhs, rhs)
-    {
-      for(p in lhs)
-      {
-        switch(typeof(lhs[p]))
-        {
-          case 'object':
-            if (!eq(lhs[p], rhs[p])) { return false }; break;
-          case 'function':
-            if (typeof(rhs[p])=='undefined' || (p != 'equals' && lhs[p].toString() != rhs[p].toString())) { return false; }; break;
-          default:
-            if (lhs[p] != rhs[p]) { return false; }
+    function isClone(a, b) {
+        window.dump("Object a: " + a + "\n");
+        window.dump("Object b: " + b + "\n");
+        var stack = [[a, b]];
+        var memory = new WeakMap();
+        var rmemory = new WeakMap();
+
+        while (stack.length > 0) {
+            var pair = stack.pop();
+            var x = pair[0], y = pair[1];
+            if (typeof x !== "object" || x === null) {
+                // x is primitive.
+                if (x !== y) {
+                    window.dump("Primitives not equal!\n");
+                    return false;
+                }
+            } else if (x instanceof Date) {
+                if (x.getTime() == y.getTime())
+                    return true;
+                window.dump("Dates not equal!\n");
+                return false;
+            } else if (memory.has(x)) {
+                // x is an object we have seen before in a.
+                if (y !== memory.get(x)) {
+                    window.dump("Already seen!?\n");
+                    return false;
+                }
+                if (!(rmemory.get(y) == x)) {
+                    window.dump("Not equal??\n");
+                    return false;
+                }
+            } else {
+                // x is an object we have not seen before.
+                // Check that we have not seen y before either.
+                if (rmemory.has(y)) {
+                    // If we have seen y before, the only possible outcome
+                    // is that x and y are literally the same object.
+                    if (y == x)
+                        continue;
+                    window.dump("Already seen y!?\n");
+                    window.dump(y.toString() + "\n");
+                    return false;
+                }
+
+                // x and y must be of the same [[Class]].
+                var xcls = Object.prototype.toString.call(x);
+                var ycls = Object.prototype.toString.call(y);
+                if (xcls !== ycls) {
+                    window.dump("Failing on proto\n");
+                    return false;
+                }
+
+                // This function is only designed to check Objects and Arrays.
+                if (!(xcls === "[object Object]" || xcls === "[object Array]")) {
+                    window.dump("Not an object!\n");
+                    window.dump(xcls + "\n");
+                    return false;
+                }
+
+                // Compare objects.
+                var xk = Object.keys(x), yk = Object.keys(y);
+                if (xk.length !== yk.length) {
+                    window.dump("Length mismatch!\n");
+                    return false;
+                }
+                for (var i = 0; i < xk.length; i++) {
+                    // We must see the same property names in the same order.
+                    if (xk[i] !== yk[i]) {
+                        window.dump("wrong order\n");
+                        return false;
+                    }
+
+                    // Put the property values on the stack to compare later.
+                    stack.push([x[xk[i]], y[yk[i]]]);
+                }
+
+                // Record that we have seen this pair of objects.
+                memory.set(x, y);
+                rmemory.set(y, x);
+            }
         }
-      }
-
-      for(p in rhs)
-      {
-        if(typeof(lhs[p])=='undefined') {return false;}
-      }
-
-      return true;
+        return true;
     }
 
     function receiveMessage(evt)
     {
-      if (eq(evt.data,generator.next()))
+      if (isClone(evt.data, generator.next()))
         window.parent.postMessage("TEST-PASS", "*");
       else
         window.parent.postMessage("TEST-FAIL", "*");
     }
     window.addEventListener("message", receiveMessage, false);
   </script>
 </head>
 <body>
--- a/dom/tests/mochitest/whatwg/postMessage_structured_clone_helper.js
+++ b/dom/tests/mochitest/whatwg/postMessage_structured_clone_helper.js
@@ -7,10 +7,57 @@ function getTestContent()
   yield "complex" + "string";
   yield new Object();
   yield new Date(1306113544);
   yield [1, 2, 3, 4, 5];
   let obj = new Object();
   obj.foo = 3;
   obj.bar = "hi";
   obj.baz = new Date(1306113544);
+  obj.boo = obj;
   yield obj;
+
+  let recursiveobj = new Object();
+  recursiveobj.a = recursiveobj;
+  recursiveobj.foo = new Object();
+  recursiveobj.foo.bar = "bar";
+  recursiveobj.foo.backref = recursiveobj;
+  recursiveobj.foo.baz = 84;
+  recursiveobj.foo.backref2 = recursiveobj;
+  recursiveobj.bar = new Object();
+  recursiveobj.bar.foo = "foo";
+  recursiveobj.bar.backref = recursiveobj;
+  recursiveobj.bar.baz = new Date(1306113544);
+  recursiveobj.bar.backref2 = recursiveobj;
+  recursiveobj.expando = recursiveobj;
+  yield recursiveobj;
+
+  let obj = new Object();
+  obj.expando1 = 1;
+  obj.foo = new Object();
+  obj.foo.bar = 2;
+  obj.bar = new Object();
+  obj.bar.foo = obj.foo;
+  obj.expando = new Object();
+  obj.expando.expando = new Object();
+  obj.expando.expando.obj = obj;
+  obj.expando2 = 4;
+  obj.baz = obj.expando.expando;
+  obj.blah = obj.bar;
+  obj.foo.baz = obj.blah;
+  obj.foo.blah = obj.blah;
+  yield obj;
+
+  let diamond = new Object();
+  let obj = new Object();
+  obj.foo = "foo";
+  obj.bar = 92;
+  obj.backref = diamond;
+  diamond.ref1 = obj;
+  diamond.ref2 = obj;
+  yield diamond;
+
+  let doubleref = new Object();
+  let obj = new Object();
+  doubleref.ref1 = obj;
+  doubleref.ref2 = obj;
+  yield doubleref;
 }
--- a/js/src/jsclone.cpp
+++ b/js/src/jsclone.cpp
@@ -79,16 +79,17 @@ enum StructuredDataType {
     SCTAG_DATE_OBJECT,
     SCTAG_REGEXP_OBJECT,
     SCTAG_ARRAY_OBJECT,
     SCTAG_OBJECT_OBJECT,
     SCTAG_ARRAY_BUFFER_OBJECT,
     SCTAG_BOOLEAN_OBJECT,
     SCTAG_STRING_OBJECT,
     SCTAG_NUMBER_OBJECT,
+    SCTAG_BACK_REFERENCE_OBJECT,
     SCTAG_TYPED_ARRAY_MIN = 0xFFFF0100,
     SCTAG_TYPED_ARRAY_MAX = SCTAG_TYPED_ARRAY_MIN + TypedArray::TYPE_MAX - 1,
     SCTAG_END_OF_BUILTIN_TYPES
 };
 
 JS_STATIC_ASSERT(SCTAG_END_OF_BUILTIN_TYPES <= JS_SCTAG_USER_MIN);
 JS_STATIC_ASSERT(JS_SCTAG_USER_MIN <= JS_SCTAG_USER_MAX);
 
@@ -385,17 +386,16 @@ JSStructuredCloneWriter::checkStack()
         JS_ASSERT(total + counts[i] >= total);
         total += counts[i];
     }
     if (counts.length() <= MAX)
         JS_ASSERT(total == ids.length());
     else
         JS_ASSERT(total <= ids.length());
 
-    JS_ASSERT(memory.count() == objs.length());
     size_t j = objs.length();
     for (size_t i = 0; i < limit; i++)
         JS_ASSERT(memory.has(&objs[--j].toObject()));
 #endif
 }
 
 static inline uint32_t
 ArrayTypeToTag(uint32_t type)
@@ -462,28 +462,28 @@ JSStructuredCloneWriter::writeArrayBuffe
            out.writeBytes(ArrayBuffer::getDataOffset(obj), ArrayBuffer::getByteLength(obj));
 }
 
 bool
 JSStructuredCloneWriter::startObject(JSObject *obj)
 {
     JS_ASSERT(obj->isArray() || obj->isObject());
 
-    /* Fail if obj is already on the stack. */
-    MemorySet::AddPtr p = memory.lookupForAdd(obj);
-    if (p) {
-        JSContext *cx = context();
-        if (callbacks && callbacks->reportError)
-            callbacks->reportError(cx, JS_SCERR_RECURSION);
-        else
-            JS_ReportErrorNumber(cx, js_GetErrorMessage, NULL, JSMSG_SC_RECURSION);
+    /* Handle cycles in the object graph. */
+    CloneMemory::AddPtr p = memory.lookupForAdd(obj);
+    if (p)
+        return out.writePair(SCTAG_BACK_REFERENCE_OBJECT, p->value);
+    if (!memory.add(p, obj, memory.count()))
+        return false;
+
+    if (memory.count() == UINT32_MAX) {
+        JS_ReportErrorNumber(context(), js_GetErrorMessage, NULL,
+                             JSMSG_NEED_DIET, "object graph to serialize");
         return false;
     }
-    if (!memory.add(p, obj))
-        return false;
 
     /*
      * Get enumerable property ids and put them in reverse order so that they
      * will come off the stack in forward order.
      */
     size_t initialLength = ids.length();
     if (!GetPropertyNames(context(), obj, JSITER_OWNONLY, &ids))
         return false;
@@ -569,27 +569,31 @@ JSStructuredCloneWriter::write(const Val
                 JSProperty *prop;
                 if (!js_HasOwnProperty(context(), obj->getOps()->lookupProperty, obj, id,
                                        &obj2, &prop)) {
                     return false;
                 }
 
                 if (prop) {
                     Value val;
-                    if (!writeId(id) || !obj->getProperty(context(), id, &val) || !startWrite(val))
+                    if (!writeId(id) ||
+                        !obj->getProperty(context(), id, &val) ||
+                        !startWrite(val))
                         return false;
                 }
             }
         } else {
             out.writePair(SCTAG_NULL, 0);
-            memory.remove(obj);
             objs.popBack();
             counts.popBack();
         }
     }
+
+    memory.clear();
+
     return true;
 }
 
 bool
 JSStructuredCloneReader::checkDouble(jsdouble d)
 {
     jsval_layout l;
     l.asDouble = d;
@@ -766,22 +770,33 @@ JSStructuredCloneReader::startRead(Value
         break;
       }
 
       case SCTAG_ARRAY_OBJECT:
       case SCTAG_OBJECT_OBJECT: {
         JSObject *obj = (tag == SCTAG_ARRAY_OBJECT)
                         ? NewDenseEmptyArray(context())
                         : NewBuiltinClassInstance(context(), &js_ObjectClass);
-        if (!obj || !objs.append(ObjectValue(*obj)))
+        if (!obj || !objs.append(ObjectValue(*obj)) ||
+            !allObjs.append(ObjectValue(*obj)))
             return false;
         vp->setObject(*obj);
         break;
       }
 
+      case SCTAG_BACK_REFERENCE_OBJECT: {
+        if (data >= allObjs.length()) {
+            JS_ReportErrorNumber(context(), js_GetErrorMessage, NULL,
+                                 JSMSG_SC_BAD_SERIALIZED_DATA,
+                                 "invalid input");
+        }
+        *vp = allObjs[data];
+        break;
+      }
+
       case SCTAG_ARRAY_BUFFER_OBJECT:
         return readArrayBuffer(data, vp);
 
       default: {
         if (tag <= SCTAG_FLOAT_MAX) {
             jsdouble d = ReinterpretPairAsDouble(tag, data);
             if (!checkDouble(d))
                 return false;
@@ -851,10 +866,13 @@ JSStructuredCloneReader::read(Value *vp)
         if (JSID_IS_VOID(id)) {
             objs.popBack();
         } else {
             Value v;
             if (!startRead(&v) || !obj->defineProperty(context(), id, v))
                 return false;
         }
     }
+
+    allObjs.clear();
+
     return true;
 }
--- a/js/src/jsclone.h
+++ b/js/src/jsclone.h
@@ -108,17 +108,18 @@ struct SCInput {
 };
 
 }
 
 struct JSStructuredCloneReader {
   public:
     explicit JSStructuredCloneReader(js::SCInput &in, const JSStructuredCloneCallbacks *cb,
                                      void *cbClosure)
-        : in(in), objs(in.context()), callbacks(cb), closure(cbClosure) { }
+        : in(in), objs(in.context()), allObjs(in.context()),
+          callbacks(cb), closure(cbClosure) { }
 
     js::SCInput &input() { return in; }
     bool read(js::Value *vp);
 
   private:
     JSContext *context() { return in.context(); }
 
     bool checkDouble(jsdouble d);
@@ -128,16 +129,19 @@ struct JSStructuredCloneReader {
     bool readId(jsid *idp);
     bool startRead(js::Value *vp);
 
     js::SCInput &in;
 
     // Stack of objects with properties remaining to be read.
     js::AutoValueVector objs;
 
+    // Stack of all objects read during this deserialization
+    js::AutoValueVector allObjs;
+
     // The user defined callbacks that will be used for cloning.
     const JSStructuredCloneCallbacks *callbacks;
 
     // Any value passed to JS_ReadStructuredClone.
     void *closure;
 };
 
 struct JSStructuredCloneWriter {
@@ -162,30 +166,31 @@ struct JSStructuredCloneWriter {
     bool writeTypedArray(JSObject *obj);
     bool startObject(JSObject *obj);
     bool startWrite(const js::Value &v);
 
     inline void checkStack();
 
     js::SCOutput &out;
 
-    // Stack of objects with properties remaining to be written.
+    // Vector of objects with properties remaining to be written.
     js::AutoValueVector objs;
 
     // counts[i] is the number of properties of objs[i] remaining to be written.
     // counts.length() == objs.length() and sum(counts) == ids.length().
     js::Vector<size_t> counts;
 
     // Ids of properties remaining to be written.
     js::AutoIdVector ids;
 
     // The "memory" list described in the HTML5 internal structured cloning algorithm.
-    // memory has the same elements as objs.
-    typedef js::HashSet<JSObject *> MemorySet;
-    MemorySet memory;
+    // memory is a superset of objs; items are never removed from Memory
+    // until a serialization operation is finished
+    typedef js::HashMap<JSObject *, uint32> CloneMemory;
+    CloneMemory memory;
 
     // The user defined callbacks that will be used for cloning.
     const JSStructuredCloneCallbacks *callbacks;
 
     // Any value passed to JS_WriteStructuredClone.
     void *closure;
 };
 
--- a/js/src/jscntxt.h
+++ b/js/src/jscntxt.h
@@ -2552,16 +2552,18 @@ class AutoVectorRooter : protected AutoG
             return true;
         }
         if (!vector.growByUninitialized(newLength - oldLength))
             return false;
         MakeRangeGCSafe(vector.begin() + oldLength, vector.end());
         return true;
     }
 
+    void clear() { vector.clear(); }
+
     bool reserve(size_t newLength) {
         return vector.reserve(newLength);
     }
 
     T &operator[](size_t i) { return vector[i]; }
     const T &operator[](size_t i) const { return vector[i]; }
 
     const T *begin() const { return vector.begin(); }
new file mode 100644
--- /dev/null
+++ b/js/src/tests/js1_8_5/extensions/clone-complex-object.js
@@ -0,0 +1,105 @@
+// -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
+// Any copyright is dedicated to the Public Domain.
+// http://creativecommons.org/licenses/publicdomain/
+
+function isClone(a, b) {
+    var stack = [[a, b]];
+    var memory = new WeakMap();
+    var rmemory = new WeakMap();
+
+    while (stack.length > 0) {
+        var pair = stack.pop();
+        var x = pair[0], y = pair[1];
+        if (typeof x !== "object" || x === null) {
+            // x is primitive.
+            if (x !== y)
+                return false;
+        } else if (x instanceof Date) {
+            if (x.getTime() !== y.getTime())
+                return false;
+        } else if (memory.has(x)) {
+            // x is an object we have seen before in a.
+            if (y !== memory.get(x))
+                return false;
+            assertEq(rmemory.get(y), x);
+        } else {
+            // x is an object we have not seen before.
+	          // Check that we have not seen y before either.
+            if (rmemory.has(y))
+                return false;
+
+            // x and y must be of the same [[Class]].
+            var xcls = Object.prototype.toString.call(x);
+            var ycls = Object.prototype.toString.call(y);
+            if (xcls !== ycls)
+                return false;
+
+            // This function is only designed to check Objects and Arrays.
+            assertEq(xcls === "[object Object]" || xcls === "[object Array]",
+                     true);
+
+            // Compare objects.
+            var xk = Object.keys(x), yk = Object.keys(y);
+            if (xk.length !== yk.length)
+                return false;
+            for (var i = 0; i < xk.length; i++) {
+                // We must see the same property names in the same order.
+                if (xk[i] !== yk[i])
+                    return false;
+
+                // Put the property values on the stack to compare later.
+                stack.push([x[xk[i]], y[yk[i]]]);
+            }
+
+            // Record that we have seen this pair of objects.
+            memory.set(x, y);
+            rmemory.set(y, x);
+        }
+    }
+    return true;
+}
+
+function check(a) {
+    assertEq(isClone(a, deserialize(serialize(a))), true);
+}
+
+// Various recursive objects, i.e. those which the structured cloning
+// algorithm wants us to reject due to "memory".
+//
+// Recursive array.
+var a = [];
+a[0] = a;
+check(a);
+
+// Recursive Object.
+var b = {};
+b.next = b;
+check(b);
+
+// Mutually recursive objects.
+var a = [];
+var b = {};
+var c = {};
+a[0] = b;
+a[1] = b;
+a[2] = b;
+b.next = a;
+check(a);
+check(b);
+
+// A date
+check(new Date);
+
+// A recursive object that is very large.
+a = [];
+b = a;
+for (var i = 0; i < 10000; i++) {
+    b[0] = {};
+    b[1] = [];
+    b = b[1];
+}
+b[0] = {owner: a};
+b[1] = [];
+check(a);
+
+reportCompare(0, 0, 'ok');
--- a/js/src/tests/js1_8_5/extensions/clone-errors.js
+++ b/js/src/tests/js1_8_5/extensions/clone-errors.js
@@ -19,40 +19,9 @@ check(function () {});
 check(Proxy.create({enumerate: function () { return []; }}));
 check(<element/>);
 check(new Namespace("x"));
 check(new QName("x", "y"));
 
 // A failing getter.
 check({get x() { throw new Error("fail"); }});
 
-// Various recursive objects, i.e. those which the structured cloning
-// algorithm wants us to reject due to "memory".
-//
-// Recursive array.
-var a = [];
-a[0] = a;
-check(a);
-
-// Recursive Object.
-var b = {};
-b.next = b;
-check(b);
-
-// Mutually recursive objects.
-a[0] = b;
-b.next = a;
-check(a);
-check(b);
-
-// A recursive object that doesn't fail until 'memory' contains lots of objects.
-a = [];
-b = a;
-for (var i = 0; i < 10000; i++) {
-    b[0] = {};
-    b[1] = [];
-    b = b[1];
-}
-b[0] = {owner: a};
-b[1] = [];
-check(a);
-
 reportCompare(0, 0, "ok");
--- a/js/src/tests/js1_8_5/extensions/clone-object.js
+++ b/js/src/tests/js1_8_5/extensions/clone-object.js
@@ -159,25 +159,25 @@ function test() {
     assertEq(a.length, 2);
 
     // Check that prototypes are not cloned, per spec.
     b = Object.create({x:1});
     b.y = 2;
     b.z = 3;
     check(b);
 
-    // Check that cloning separates merge points in the tree, per spec.
+    // Check that cloning does not separate merge points in the tree.
     var same = {};
     b = {one: same, two: same};
     a = check(b);
-    assertEq(a.one === a.two, false);
+    assertEq(a.one === a.two, true);
 
     b = [same, same];
     a = check(b);
-    assertEq(a[0] === a[1], false);
+    assertEq(a[0] === a[1], true);
 
     // Try cloning a deep object. Don't fail with "too much recursion".
     b = {};
     var current = b;
     for (var i = 0; i < 10000; i++) {
         var next = {};
         current['x' + i] = next;
         current = next;
--- a/js/src/tests/js1_8_5/extensions/jstests.list
+++ b/js/src/tests/js1_8_5/extensions/jstests.list
@@ -21,16 +21,17 @@ script destructure-accessor.js
 script censor-strict-caller.js
 skip-if(!xulRuntime.shell) script clone-simple.js
 skip-if(!xulRuntime.shell) script clone-regexp.js
 skip-if(!xulRuntime.shell) script clone-leaf-object.js
 skip-if(!xulRuntime.shell) script clone-object.js
 skip-if(!xulRuntime.shell) script clone-typed-array.js
 skip-if(!xulRuntime.shell) script clone-errors.js
 skip-if(!xulRuntime.shell) script clone-forge.js
+skip-if(!xulRuntime.shell) script clone-complex-object.js
 script set-property-non-extensible.js
 script recursion.js
 script regress-627984-1.js
 script regress-627984-2.js
 script regress-627984-3.js
 script regress-627984-4.js
 script regress-627984-5.js
 script regress-627984-6.js