536161 - Provide, or make possible, some method (necessarily non-JSON) to serialize cyclic data structures

Status: RESOLVED INVALID

(Core :: JavaScript Engine, enhancement)

Description

[Jan Honza Odvarko [:Honza] (always need-info? me)]

In Firebug, we would like to support a "Copy object as JSON" feature or DOM object. The problem is that Firefox native JSON implementation doesn't support recursive cycle detection and this doesn't work for DOM objects (e.g. window)

Couple students contributing to Firebug modified json2.js (from www.json.org) and implemented simple detection. See following test case:

http://www.janodvarko.cz/firebug/tests/2560/issue2560.html

Is it possible to enhance the native Fx JSON so, it can be used and we don't have to duplicate the stringify code?

Honza

Comment 1

[Jeff Walden [:Waldo]]

"enhance", no.  ES5 spec is very precise about what it requires (and, incidentally, when it comes to recursive data structures, we don't actually follow it precisely last I checked).  "supplement", as in a separate API that might do the trick, might be possible (although I'd discourage a mechanism based around sharp variables or their syntax).

Comment 2

[Brendan Eich [:brendan]]

(In reply to comment #0)
> http://www.janodvarko.cz/firebug/tests/2560/issue2560.html

This implementation (and any pure-JS one lacking a general value->value Map data structure) uses linear search in an array to detect cycles and join points (it misdiagnoses the latter as the former). This has O(n^2) growth rate, so no good for large/variable-sized data sets.

(In reply to comment #1)
> (although I'd discourage a mechanism based around sharp variables or their
> syntax).

JSON syntax is what it is, it will not be extended. Underlying mechanism, on the other hand, would be the same for sharp variables as for any general cyclic or multiply-connected object graph detection scheme, and should not be reinvented.

/be

Comment 3

[John J. Barton]

Just FYI, our current plan is to base remote (multiprocess) Firebug on JSON traffic so we need either a plan for this bug or we need to look into an alternative.

Comment 4

[Jeff Walden [:Waldo]]

You might consider this alternative:

http://benjamin.smedbergs.us/blog/2008-08-21/json-serialization-of-interconnected-object-graphs/

Comment 5

[Brendan Eich [:brendan]]

(In reply to comment #4)
> You might consider this alternative:
> 
> http://benjamin.smedbergs.us/blog/2008-08-21/json-serialization-of-interconnected-object-graphs/

Where is Map defined? If it's written in JS it must use array search, so O(n^2).

/be

Comment 6

[Jeff Walden [:Waldo]]

I assume they're less concerned about algorithmic optimality than about having something that works, at a first cut, since plain old JSON doesn't.  Map isn't necessary to have something that works "well enough".

Comment 7

[Brendan Eich [:brendan]]

"algorithmic optimality" is not what big-O measures. Growth rate is tyrannical. For small data sets, you don't care; as you scale up, it starts to suck. In the big leagues your team gets shut out and goes home early.

Are the data sets always small enough it doesn't matter? Could be, but if not, or if you don't know, it's an issue.

Lack of Map in JS is definitely an issue; see the proposal at

http://wiki.ecmascript.org/doku.php?id=strawman:weak_references

and comment to es-discuss.

/be

Comment 8

[Benjamin Smedberg]

Map is http://hg.mozilla.org/rewriting-and-analysis/dehydra/file/54c8f525cde9/libs/map.js which uses a primitive hashcode() function that dehydra provides.

Comment 9

[Steven Parkes]

So this bug at this point is open waiting for correct implementation of cycle checking as spec'd in ES5?

Right now, eventually we get a too much recursion error in the 1.9.2 shell.

Comment 10

[consiliens]

I tried exporting DOM objects as JSON and am blocked by this bug.  Potential ways forward include:

1. Pure JS
Too slow

2. C++ XPCOM
Would only benefit extensions that include the XPCOM

3. Add to Firefox platform
Ideal solution if there's someone to implement it soon

A super slow JS approach is better than nothing at this point.  What is the best way forward?

Comment 11

[Brendan Eich [:brendan]]

Isn't this covered by another es5-blocker bug?

/be

Comment 12

[Steven Parkes]

I wasn't sure when I posted on 2010-03-12.

Just looked through the open and closed deps of https://bugzilla.mozilla.org/show_bug.cgi?id=445494 and don't see any dups. I see one other open for JSON, https://bugzilla.mozilla.org/show_bug.cgi?id=509184, but I don't believe it's related.

Comment 13

[Robert Sayre]

(In reply to comment #11)
> Isn't this covered by another es5-blocker bug?

No. See comment 1. Our JSON codes needs to detect cycles as soon as they occur, and then throw an exception, per the spec. So, custom JS code will always be needed to serialize DOM objects.

Comment 14

[Steven Parkes]

That's what raised this to my attention: someone asking why the env.js port was segv'ing while the same code worked in FF 3.6. We weren't setting the stack limit, which is why we were getting the segv.

But it is the case that it appears right now FF 3.6 actually succeeds in serializing DOM objects. Chrome, on the other hand, throws a type error.

My response to the person that asked was that while it appears you can serialize DOM objects within FF, you can't rely on that ... (but it should throw a type error if it fails).

Comment 15

[John J. Barton]

I ran into this again in trying to use native JSON to serial Firebug breakpoint descriptions. 
 var jsonString = JSON.stringify(obj);
fails, with "too much recursion". That's so discouraging: there is no practical way to work around the problem short of binary search through the properties of "obj" until you find the one that breaks. I think I'd rather do something else today, like switch to the js implementation of JSON.

Comment 16

[Jeff Walden [:Waldo]]

Resummarizing, unmarking as an ES5 blocker since this functionality exceeds that mandated by ES5...

Comment 17

[Steven Parkes]

Was there an issue/fix for throwing a type error, which I think ES5 requires? Could be added to a see-also for this issue.

Comment 18

[Jeff Walden [:Waldo]]

Not aware of one, busy tracking down other bugs and patchwork today and didn't get to filing one until just now: bug 578273.

Comment 19

[André Bargull [:anba]]

Firebug related bugs are no longer valid and anything else should go through the TC39 standards process.