Open Bug 536161 Opened 11 years ago Updated 4 years ago

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

Categories

(Core :: JavaScript Engine, enhancement)

enhancement
Not set
normal

Tracking

()

People

(Reporter: Honza, Unassigned)

References

Details

(Whiteboard: [firebug-p3])

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
Whiteboard: [firebug-p3]
"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).
Severity: normal → enhancement
OS: Windows Vista → All
Hardware: x86 → All
(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
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.
(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
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".
"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
Map is http://hg.mozilla.org/rewriting-and-analysis/dehydra/file/54c8f525cde9/libs/map.js which uses a primitive hashcode() function that dehydra provides.
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.
Blocks: es5
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?
Isn't this covered by another es5-blocker bug?

/be
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.
(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.
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).
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.
Resummarizing, unmarking as an ES5 blocker since this functionality exceeds that mandated by ES5...
No longer blocks: es5
Summary: Effective detection of cyclic data structures in native JSON → Provide, or make possible, some method (necessarily non-JSON) to serialize cyclic data structures
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.
Not aware of one, busy tracking down other bugs and patchwork today and didn't get to filing one until just now: bug 578273.
See Also: → 578273
Assignee: general → nobody
You need to log in before you can comment on or make changes to this bug.