Closed Bug 578273 Opened 12 years ago Closed 12 years ago

ES5: Properly detect cycles in JSON.stringify (throw TypeError, check for cycles rather than imprecisely rely on recursion limits)


(Core :: JavaScript Engine, defect)

Not set





(Reporter: Waldo, Assigned: Waldo)




(Whiteboard: fixed-in-tracemonkey)


(1 file)

var count = 0;
var desc =
    get: function() { count++; return obj; },
    enumerable: true,
    configurable: true
var obj = Object.defineProperty({ p1: 0 }, "p2", desc);

  assertEq(false, true, "should have thrown");
catch (e)
  assertEq(e instanceof TypeError, true,
           "wrong error type: " +;
  assertEq(count, 1,
           "cyclic data structures not detected immediately");
Attached patch Patch and testSplinter Review
The changed XML test is because the relevant verbiage says to throw an Error exception, and with the type tweak it's now a TypeError exception -- but it delegates to Error prototypally, of course, so I think we technically still comply with the spec (I couldn't find more explicit language on the semantics of the phrasing).  I don't think we care about E4X nitpicks here anyway, and using one central error message makes sense.

This new recursion detection is necessarily slower in the normal case, and faster in the rare recursive case, but we don't have a choice in the matter, spec requires it, other implementations enforce it correctly.

A further note on those implementations: even for ridiculously huge amounts of object-stack-checking, I couldn't observe any noticeable performance degradation to cycle-detecting beyond that inherent in stringifying a heavily nested object.  It seems that cycle detection, while potentially asymptotically quadratic, accesses memory so efficiently that the extra time is *still* negligible.  In short: there's no reason to worry about performance here.
Attachment #457257 - Flags: review?(sayrer)
Comment on attachment 457257 [details] [diff] [review]
Patch and test

>+    bool init(JSContext *cx, jsval space) {
>+        return stack.init(16);
>+    }

nit: this method is ok, but keep a separate InitializeGap method instead of mixing them together. It's self-documenting that way.

>+    typedef HashSet<JSObject *> ObjectStack;
>+    ObjectStack stack;

nit: no need for a typedef, I'd think.

HashSet<JSObject *> objectStack;

might work better, and be more transparent than "stack".
Attachment #457257 - Flags: review?(sayrer) → review+
Whiteboard: fixed-in-tracemonkey
Closed: 12 years ago
Resolution: --- → FIXED
Target Milestone: mozilla2.0b2 → mozilla2.0b3
Duplicate of this bug: 538301
You need to log in before you can comment on or make changes to this bug.