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

RESOLVED FIXED in mozilla2.0b3

Status

()

defect
--
minor
RESOLVED FIXED
9 years ago
9 years ago

People

(Reporter: Waldo, Assigned: Waldo)

Tracking

Trunk
mozilla2.0b3
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(Not tracked)

Details

(Whiteboard: fixed-in-tracemonkey, )

Attachments

(1 attachment)

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

try
{
  JSON.stringify(obj);
  assertEq(false, true, "should have thrown");
}
catch (e)
{
  assertEq(e instanceof TypeError, true,
           "wrong error type: " + e.constructor.name);
  assertEq(count, 1,
           "cyclic data structures not detected immediately");
}
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+
http://hg.mozilla.org/tracemonkey/rev/0e4fda0e2519
Whiteboard: fixed-in-tracemonkey
http://hg.mozilla.org/mozilla-central/rev/0e4fda0e2519
Status: ASSIGNED → RESOLVED
Closed: 9 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.