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

NEW
Unassigned

Status

()

Core
JavaScript Engine
--
enhancement
8 years ago
3 years ago

People

(Reporter: Honza, Unassigned)

Tracking

Trunk
Points:
---

Firefox Tracking Flags

(Not tracked)

Details

(Whiteboard: [firebug-p3])

(Reporter)

Description

8 years ago
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
(Reporter)

Updated

8 years ago
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

Comment 3

8 years ago
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.
You might consider this alternative:

http://benjamin.smedbergs.us/blog/2008-08-21/json-serialization-of-interconnected-object-graphs/
(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.

Comment 9

7 years ago
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.

Updated

7 years ago
Blocks: 445494

Comment 10

7 years ago
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

Comment 12

7 years ago
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

7 years ago
(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

7 years ago
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

7 years ago
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: 445494
Summary: Effective detection of cyclic data structures in native JSON → Provide, or make possible, some method (necessarily non-JSON) to serialize cyclic data structures

Comment 17

7 years ago
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: → bug 578273
(Assignee)

Updated

3 years ago
Assignee: general → nobody
You need to log in before you can comment on or make changes to this bug.