Here is an example of a data structure with cyclic references:
function makeToolshed(){
var nut = {name: 'nut'}, bolt = {name: 'bolt'};
nut.needs = bolt; bolt.needs = nut;
return { nut: nut, bolt: bolt };
}
When you wish to KEEP the cyclic references (restore them when you deserialize, instead of "nuking" them), you have 2 choices, which I'll compare here. First is Douglas Crockford's cycle.js, second is my siberia package. Both work by first "decycling" the object, i.e., constructing another object (without any cyclic references) "containing the same information."
Mr. Crockford goes first:
JSON.decycle(makeToolshed())
As you see, the nested structure of JSON is retained, but there is a new thing, which is objects with the special $ref
property. Let's see how that works.
root = makeToolshed();
[root.bolt === root.nut.needs, root.nut.needs.needs === root.nut]; // retutrns [true,true]
The dollar sign stands for the root. .bolt
having $ref
tells us that .bolt
is an "already seen" object, and the value of that special property (here, the string $["nut"]["needs"]) tells us where, see first ===
above. Likewise for second $ref
and the second ===
above.
Let's use a suitable deep equality test (namely Anders Kaseorg's deepGraphEqual
function from accepted answer to this question) to see if cloning works.
root = makeToolshed();
clone = JSON.retrocycle(JSON.decycle(root));
deepGraphEqual(root, clone) // true
serialized = JSON.stringify(JSON.decycle(root));
clone2 = JSON.retrocycle(JSON.parse(serialized));
deepGraphEqual(root, clone2); // true
Now, siberia:
JSON.Siberia.forestify(makeToolshed())
Siberia does not try to mimic "classic" JSON, no nested structure. The object graph is described in a "flat" manner.
Each node of the object graph is turned into a flat tree (plain key value pair list with integer-only values), which is an entry in .forest.
At index zero, we find the root object, at higher indices, we find the other nodes of the object graph, and negative values (of some key of some tree of the forest) point to the atoms
array, (which is typed via the types array, but we'll skip the typing details here). All terminal nodes are in the atoms table, all non-terminal nodes are in the forest table, and you can see right away how many nodes the object graph has, namely forest.length
. Let's test if it works:
root = makeToolshed();
clone = JSON.Siberia.unforestify(JSON.Siberia.forestify(root));
deepGraphEqual(root, clone); // true
serialized = JSON.Siberia.stringify(JSON.Siberia.forestify(root));
clone2 = JSON.Siberia.unforestify(JSON.Siberia.unstringify(serialized));
deepGraphEqual(root, clone2); // true
comparison
will add section later.
note
I'm currently refactoring the package. Central ideas and algorithms are staying the same, but the new version will be easier to use, the top level API will be different. I will very soon archive siberia and present the refactored version, which I'll call objectgraph. Stay tuned, it will happen this month (August 2020)
ah, and ultra short version for the comparison. For a "pointer", I need as much space as an integer takes, since my "pointers to already seen nodes" (as a matter of fact, to all nodes, already seen or not) are just integers. In Mr. Crockford's version, amount needed to store a "pointer" is bounded only by the size of the object graph. That makes the worst case complexity of Mr. Crockford's version extremely horrible. Mr. Crockford gave us "another Bubblesort". I'm not kidding you. It's that bad. If you don't believe it, there are tests, you can find them starting from the readme of the package (will transform them to be benchmark.js compliant also this month, Aug 2020)
cycle.js
as an answer here, since it's the most appropriate solution for a lot of cases. It seems appropriate for you to post that answer, since you're the first one to reference it (in your comment below). If you don't feel like posting it as an answer yourself, I will eventually do so. – Armagh