Passing an object with circular references from server to client-side Javascript while retaining circularity

I'm trying to pass an object with circular references from node.js server to client-side javascript.

Server (node.js):

var object = { circular: object }
//....
app.get('/', function(req, res){    
    res.render('index.jade', {object: object});
});

Client-side Jade/Javascript

script var object = !{JSON.stringify(object)};

Here I get the error that object contains circular references.

Any way to get the object in client-side javascript, with or without circular references?

Answers:

Answer

Douglas Crockford has a solution for this that I have successfully used to solve this problem before: Cycle.js

instead of just using stringify and parse you would first call decycle and restore with retrocycle

var jsonString = JSON.stringify(JSON.decycle(parent));
var restoredObject = JSON.retrocycle(JSON.parse(jsonString));

JSFiddle

Answer

CHECK THIS OUT! HUGE PERFORMANCE IMPROVEMENTS COMPARED TO ACCEPTED ANSWER

The trick is to first construct a new object, which contains all the information of the original object, but does so without any cyclic references. Mr Crockford calls this step decyle, and calls the reverse step retrocyle (I guess 're-cyle' would have been confusing). For clarity while discussing both Mr Crockford's and my method, I'll use 2 different names for my (similar) method, namely decycleIntoForest, and deForestIntoCycle.

In both cases, the construction of the 'pre-frozen' (cycle-free) object makes use of WeakMaps. In case you haven't used WeakMaps before, just like (mathematically speaking) JavaScript objects are mappings from strings (the object's keys) to anything, in a WeakMap, the keys are all objects (also mapped to anything); no other difference mathematically (syntactically of course more differences, see above MDN article).

So you traverse the object tree (or graph), and when an object is encountered which 'has been seen before' (now you see what the WeakMap is good for), we can't just put that object as it is into our "pre-frozen mod-clone-object", but we'll put some sort of encoding of how to find "that thing we've encountered before".

Mr. Crockford's encoding is, essentially, to explain it by example, storing the string '$.lorem.ipsum.dolor.sit.amet' (under a special reserved key called $ref) when the object $.lorem.ipsum.dolor.sit.amet ($ being the root object in question) occurs somewhere else later (and putting that string into the WeakMap when that object is encountered for the first time.)

My approach uses WeakMap similarly - as the tool to 'lookup' objects. In contrast to Mr. Crockford's method, my 'pre-frozen mod-clone-object' is not a single tree, but a forest, i.e. an array of trees. One tree for each object which occurs in the complete object graph. And in the WeakMap we put simply the array index of where that tree occurs in the forest. The root object is always the first tree (i.e. = forest[0]).

The keys of the tree(-object)s in the forest are same keys the corresponding object/node has had before the transformation. But the values are all 'wrapped' / turned into objects. A (pre trafo) non-object value is 'wrapped' like as follows: before: { ..., foo: 'bar', ...} after: {..., foo: {value: 'bar'}, ...}. And objects are wrapped like this: before: {..., foo: {...(object)...}, ...} after: {..., foo: {pointer: 42}, ...}. Meaning that the information on obj.foo is to be found in the tree at forest[42].

Here is an example. Let's make some object

obj = {L: {foo:'bar'}, R: {lorem: 'ipsum'}}
obj.R.uncle = obj.L
obj.L.root = obj

Decycled with the forest method, we get this

[
    {
        L: { pointer: 1 },
        R: { pointer: 2 }
    },
    {
        foo: { value: "bar" },
        root: { pointer: 0 }
    },
    {
        lorem: { value: "ipsum" },
        uncle: { pointer: 1 }
    }
]

While the forest method is constructing above object we construct (at the same time) an array, containing obj (the root) at position 0, obj.L at position 1, and obj.R at position 2. And the WeakMap is nothing other than the inverse mapping of that array, i.e. obj -> 0, obj.L -> 1, obj.R -> 2

Decycled with the classic method, we get an object rather than an array:

{
    "L": {
        "foo": "bar",
        "root": {
            "$ref": "$"
        }
    },
    "R": {
        "lorem": "ipsum",
        "uncle": {
            "$ref": "$[\"L\"]"
        }
    }
}

and the WeakMap encodes obj -> '$', obj.L -> $["L"], obj.R -> $["R"]

The huge performance boost occurs for the reverse method (where the cycles are being put back in) - while there is no significant performance difference for the 'decycle'. The reason is that retrocycle uses both regular expressions and eval, both of which are prone to be performance eaters. (it's more likely the eval here, I'd say.) Even if the 'classic' (Crockford) method is rewritten without eval (which is easy: just store the array ['lorem', 'ipsum', 'dolor', 'sit', 'amet'] instead of the string '$.lorem.ipsum.dolor.sit.amet', and then replace the eval by a simple for loop): the for loop replacing the eval will need much longer (linear in path length) than just going straight to forest[i] for given i (constant time).

Voilà the code:

if (typeof JSON.decycleIntoForest !== "function") {
  (function() {
    "use strict";
    var ignore = [Boolean, Date, Number, RegExp, String];

    function primitive(item) {
      if (typeof item === 'object') {
        if (item === null) {
          return true;
        }
        for (var i = 0; i < ignore.length; i++) {
          if (item instanceof ignore[i]) {
            return true;
          }
        }
        return false;
      } else {
        return true;
      }
    }

    function infant(value) {
      return Array.isArray(value) ? [] : {};
    }
    JSON.decycleIntoForest = function decycleIntoForest(object, replacer) {
      if (typeof replacer !== 'function') {
        replacer = function(x) {
          return x;
        }
      }
      object = replacer(object);
      if (primitive(object)) return object;
      var objects = [object];
      var forest = [infant(object)];
      var bucket = new WeakMap(); // bucket = inverse of objects 
      bucket.set(object, 0); // i.e., map object to index in array
      function addToBucket(obj) {
        var result = objects.length;
        objects.push(obj);
        bucket.set(obj, result);
        return result;
      }

      function isInBucket(obj) {
        return bucket.has(obj);
        // objects[bucket.get(obj)] === obj, iff true is returned
      }

      function processNode(source, target) {
        Object.keys(source).forEach(function(key) {
          var value = replacer(source[key]);
          if (primitive(value)) {
            target[key] = {
              value: value
            };
          } else {
            var ptr;
            if (isInBucket(value)) {
              ptr = bucket.get(value);
            } else {
              ptr = addToBucket(value);
              var newTree = infant(value);
              forest.push(newTree);
              processNode(value, newTree);
            }
            target[key] = {
              pointer: ptr
            };
          }
        });
      }
      processNode(object, forest[0]);
      return forest;
    };
  })();
}
if (typeof JSON.deForestIntoCycle !== "function") {
  (function() {
    "use strict";
    JSON.deForestIntoCycle = function deForestIntoCycle(forest) {
      var objects = [];
      var objectRequested = [];
      var todo = [];

      function processTree(idx) {
        if (idx in objects) return objects[idx];
        if (objectRequested[idx]) return null;
        objectRequested[idx] = true;
        var tree = forest[idx];
        var node = Array.isArray(tree) ? [] : {};
        for (var key in tree) {
          var o = tree[key];
          if ('pointer' in o) {
            var ptr = o.pointer;
            var value = processTree(ptr);
            if (value === null) {
              todo.push({
                node: node,
                key: key,
                idx: ptr
              });
            } else {
              node[key] = value;
            }
          } else {
            if ('value' in o) {
              node[key] = o.value;
            } else {
              throw new Error('unexpected')
            }
          }
        }
        objects[idx] = node;
        return node;
      }
      var result = processTree(0);
      for (var i = 0; i < todo.length; i++) {
        var item = todo[i];
        item.node[item.key] = objects[item.idx];
      }
      return result;
    };
  })();
}

obj = {
  L: {
    foo: 'bar'
  },
  R: {
    lorem: 'ipsum'
  }
}
obj.R.uncle = obj.L
obj.L.root = obj
objForest = JSON.decycleIntoForest(obj)
console.log(JSON.stringify(objForest, null, 4));

The performance gains for the 2nd step (putting the cycles back in) get larger and larger when the problem size grows. When the string length of the decycled object (after JSON.stringify) is huge (tens or hundreds of Megabyte) the ratio between the respective runtimes approaches a thousand.

Speed Test

For the speed test, let's create some rather large object with tons of cycles. First, we create a complete binary tree, and then, we're going to put in cycles by putting in uncle pointers. Every node except the root and the 2 direct children of the root have exactly one uncle = the unique sibling of the parent.

create complete binary tree:

function multiForEach(func) {
  return function(arr2d) {
    var LEVEL = arr2d.length;

    function inner(stack) {
      var level = stack.length;
      if (level >= LEVEL) {
        func(stack);
      } else {
        var arr = arr2d[level];
        for (var i = 0; i < arr.length; i++) {
          inner(stack.concat(arr[i]));
        }
      }
    }
    inner([]);
  }
};

function makeTree(depth) {
  var root = {};
  multiForEach(function(arr) {
    var node = root;
    var value = '';
    for (var i = 0; i < arr.length; i++) {
      var a = arr[i];
      value = value + a;
      if (!(a in node)) {
        node[a] = {};
      }
      node = node[a];
    }
    node.value = value;
  })('0'.repeat(depth).split('').map(function() {
    return ['L', 'R'];
  }))
  return root;
}
document.getElementById('the').textContent =
  JSON.stringify(makeTree(2), null, 4)
<pre id="the"></pre>

uncles:

function inflateViaUncle(tree){
    if (!tree) return;
    if (typeof tree !== 'object') return;
    function inflate(node, sibling){
        var  hasL = (typeof    node.L === 'object');
        var  hasR = (typeof    node.R === 'object');
        var _hasL = (typeof sibling.L === 'object');
        var _hasR = (typeof sibling.R === 'object');
        if ( hasL){    node.L.uncle = sibling; }
        if ( hasR){    node.R.uncle = sibling; }
        if (_hasL){ sibling.L.uncle = node;    }
        if (_hasR){ sibling.R.uncle = node;    }
        if ( hasL &&  hasR){ inflate(   node.L,    node.R); }
        if (_hasL && _hasR){ inflate(sibling.L, sibling.R); }
    }
    var hasL = (typeof tree.L === 'object');
    var hasR = (typeof tree.R === 'object');
    if (hasL && hasR) { inflate(tree.L, tree.R); }
    return tree;
}

speed tests:

function testForestMethod(depth){
    var inputTree = inflateViaUncle(makeTree(depth));
    var start = performance.now();
    var cycleFree = JSON.decycleIntoForest(inputTree);
    var end1 = performance.now();
    var duration1 = Math.round(1000*(end1 - start))/1000;
    var length = JSON.stringify(cycleFree).length;
    start = performance.now();
    var roundTrip = JSON.deForestIntoCycle(cycleFree);
    var end2 = performance.now();
    var duration2 = Math.round(1000*(end2 - start))/1000;
    return [depth, duration1, length, duration2];
}
function testClassic(depth){
    var inputTree = inflateViaUncle(makeTree(depth));
    var start = performance.now();
    var cycleFree = JSON.decycle(inputTree);
    var end1 = performance.now();
    var duration1 = Math.round(1000*(end1 - start))/1000;
    var length = JSON.stringify(cycleFree).length;
    start = performance.now();
    var roundTrip = JSON.retrocycle(cycleFree);
    var end2 = performance.now();
    var duration2 = Math.round(1000*(end2 - start))/1000;
    return [depth, duration1, length, duration2];
}

results:

[tree-depth, duration step1 (ms), length after JSON.stringify, duration step2 (ms)]
// forest method
[8, 1.745, 30609, 0.625]
[9, 4.59, 62134, 0.84]
[10, 5.675, 127666, 2.315]
[11, 6.95, 259762, 2.03]
[12, 10.42, 526000, 2.495]
[13, 20.13, 1075329, 5.755]
[14, 89.695, 2189437, 11.795]
[15, 94.08, 4434039, 10.485]
[16, 235.09, 9018146, 36.74]
[17, 351.71, 18389792, 92.495]
[18, 742.42, 37264152, 255.94]

// classic method
[8, 1.66, 160257, 31.125]
[9, 4.265, 401701, 71.365]
[10, 3.92, 984393, 159.685]
[11, 12.71, 2367853, 321.76]
[12, 11.27, 5607825, 772.13]
[13, 31.125, 13107637, 1555.705]
[14, 70.23, 30294489, 3291.94]
[15, 230.6, 69337597, 7294.44]
[16, 315.5, 157352481, 15717.095]
[17, 635.825, 354419269, 33921.05]

link to classic: cycle.js

Tags

Recent Questions

Top Questions

Home Tags Terms of Service Privacy Policy DMCA Contact Us

©2020 All rights reserved.