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

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Jeff Walden [:Waldo]]

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");
}

Comment 1

[Jeff Walden [:Waldo]]

Attachment: Patch and test

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.

Comment 2

[Robert Sayre]

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".

Comment 3

[Jeff Walden [:Waldo]]

http://hg.mozilla.org/tracemonkey/rev/0e4fda0e2519

Comment 4

[Jeff Walden [:Waldo]]

http://hg.mozilla.org/mozilla-central/rev/0e4fda0e2519