JSON.stringify crashes on circular references

[haysmark]

From util/doh, run the dojo tests in Rhino:

java -classpath ../shrinksafe/js.jar org.mozilla.javascript.tools.shell.Main ../../dojo/dojo.js baseUrl=../../dojo load=doh test=dojo/tests/module

Our Rhino 1.7 gets stuck on dojo/tests/json.js, line 49, before giving an OutOfMemoryError?.

[haysmark]

(In #7523) There are still issues with Rhino.

[Tom Trenka]

According to haysmark, the version of Rhino is 1.7.

[haysmark]

This is actually a bug in the old dojo.toJson that got cut/pasted into the new dojo/json. It affects all browsers that do not provide a native JSON object.

[bill]

Mark, why don't you tell us the exact cut/pasted code where the bug is?

IIRC from the meeting Mark said that the failing test was in dojo/tests/json.js:

function serializeCircular(t){
	try{
		var a = {};
		a.a = a;
		console.log("circular: " + JSON.stringify(a));
	}catch(e){
		return;
	}
	throw new Error("stringify must throw for circular references");

},

[haysmark]

Yes, that is indeed the test that fails. I can't pinpoint any particular line in dojo/json because the absence of circular reference testing is causing the problem.

[Kris Zyp]

I don't see any test failures on browsers (with or without native JSON support). I would bet Rhino would properly abort the circular reference stack depth in compiled mode (optimization level of 0 or higher) since Java should provide a catchable StackOverflow? exception, IIRC. Or we could disable that test for Rhino. However, shouldn't the newest versions of Rhino have native JSON support?

[haysmark]

Perhaps I misworded... in all other browsers, the test does not "fail" so much as it misconstrues the exception in non-native mode. For instance on IE7 the test passes but if you debug the catch block you see a stack overflow. Similarly if you throw out the native impl on Chrome you see the same thing.

I tried running it with -opt 9 and while the Rhino call stack changed to include the optimizer, the result was the same.

[Kris Zyp]

The test is testing that an exception be thrown. An exception is the correct behavior. I don't believe that dojo/json makes any claims as to what type of exception is thrown. We are intentionally relying on stack overflow errors to fulfill this expectation. The only problem is if the test isn't successfully catching the error (StackOverflow? or otherwise), in which case we should just omit the test.

[haysmark]

Potential fix.

[haysmark]

I've attached a patch implementing a linear time algorithm for cycle detection of JSON. It is a little rough around the edges (wasn't sure whether to use the replacer function) but it demonstrates my idea.

[Kris Zyp]

Sorry, I don't think we can add 2.4KB to dojo/json just for the sake of cycle detection.

[Eugene Lazutkin]

Replying to kzyp:

Sorry, I don't think we can add 2.4KB to dojo/json just for the sake of cycle detection.

I concur. That's why it is not there in the first place --- this feature was discussed before and left out.

[haysmark]

By that logic, why embed the fallback in dojo/json at all? Just make the has check and if it fails, load a dojo/_json that has the fallback+the circular reference checking.

[Eugene Lazutkin]

Let me explain my opposition in more details:

1. I use JSON extensively on server and on client with different languages, and never in my practice I had to deal with self-referential structures I wanted to serialize intentionally or by mistake. I never heard any complaints from my colleagues, nor clients about Dojo not processing self-referential structures in some special way. So I think that the problem is overblown right there.

2. Obviously it would be bad if Dojo silently ignored errors and produced wrong output even/especially in obscured corner cases. My understanding is that it is not the case --- wrong structures would produce a noticeable error, and can be easily debugged.

3. The patch doesn't contain a test demonstrating that it finds cycles reliably. Having worked with graphs and cycles in them professionally I would assume that the test would include a bunch of use cases. In general a cycle detection in graphs, and how to do it efficiently, is a major branch of the graph theory. Different algorithms have varying time/space complexity in different cases --- I am not sure that we can do this trade-off for a programmer implicitly without any knowledge of what kind of cycles can be found in data (if any at all).

4. On IE6 loop for-in skips properties with certain names (see gory details in the implementation of dojo._mixin()), so if cycles are in those names, they will be undetected by the proposed patch.

5. If I am not mistaken the patch implements the Floyd's algorithm, which has its own problems, and doesn't come for free. For example, in a simple case with 61 objects arranged in a linear graph:

var a = {}, // 1 object
    b = [[[[[[[[[[[[[[[[[[[[a]]]]]]]]]]]]]]]]]]]], // 20 objects
    c = [[[[[[[[[[[[[[[[[[[[b]]]]]]]]]]]]]]]]]]]], // 20 objects
    d = [[[[[[[[[[[[[[[[[[[[c]]]]]]]]]]]]]]]]]]]]; // 20 objects
a.x = d;
hasCycle(a);

objStack had 120 newly created items in it by the time when a loop was found, while objList had 60 items. I'd say that this is a big object churn, which will slow down the GC especially on slow browsers (IE and mobile), and when processing large data structures --- both cases when we need a performance the most.

In general, I think that the problem is a valid one, but I feel that we cannot force a solution, which comes with a time/space tax, on our users indiscriminately. It is a good candidate for a separate module, which implements this specific functionality. I would like to see it submitted to CPM, so it can be used when truly needed.

Just to frame this problem in a perspective: native implementations of JSON.stringify() are quite frugal, because they don't use graph algorithms to detect cycles at all. See ECMA-262 5th edition 15.12.3, which describes its algorithm in details. The "secret sauce" is hidden in this phrase: "If stack contains value...". AFAIK, fast implementations use Set() --- an associative container, which can use objects as keys. How? Simple: object's memory address is used as an integer key for any given object. Unfortunately, while memory addresses are all the rage in C/C++, this functionality is unavailable in JavaScript. Fortunately it will come to us in the upcoming ES6, which is planned to be finalized by 2013. OTOH, when Set() is available, so will be JSON.stringify() making the whole problem a moot point.

PS: Why hasCycle() has two parameters, and the second one is unused?

[haysmark]

Right hasCycle has two parameters because I originally intended to check the "replaced" version of the JSON but got caught up in the cycle detection itself.

It seems like we already had a Rhino loader plugin for various bits of Dojo, would it make sense to put cycle detection there seeing as it is the only adversely affected browser?

[bill]

OK, so Kris and Eugene both said they don't they don't want to add this code, thus this should be closed as wontfix. I'm not sure how to run the tests on rhino but if it's really failing there you can just disable the test for rhino.

[bill]

#16254 is a duplicate of this ticket.

[andybalaam]

[patch][ccla] disable-circular-ref-test-on-rhino.patch Andy Balaam (IBM, CCLA)

[andybalaam]

Added a patch to disable this test on Rhino. (I can't re-open the ticket - I hope someone's watching...)

[bill]

In [29894]:

Disable circular test on Rhino, refs #15497, patch from Andy Balaam (IBM, CCLA).