How to handle circular references and maybe save some bandwidth.

1-circular-object.md

The Problem

If we have object like this

var x = {foo:1}
x.bar = x

We can't send it over http, because of circular reference. We also can't stringify it. Another problem we may have multiple references to same object. Like this:

var palette1 = {red:'red',green:'green',blue:'blue'}
var palette2 = {red:'red',green:'green',blue:'blue'}
var data = {
  rows: [
    { id:0, ..., palette: palette1}, 
    { id:1, ..., palette: palette2}, 
    { id:2, ..., palette: palette1}, 
    { id:3, ..., palette: palette2}
    ...
  ]
}

If we'll do JSON.stringify(data) - it will return long string, but actually a lot of data is repeated.

More then that, if we'll do data = JSON.parse(JSON.stringify(data)) - we will have many instances of palette1 & palette2. Now if we'll change data.rows[0].palette.red = 'orange', 3rd item will still contain 'red' data.rows[2].palette.red === 'red'

The Solution

To solve the problem, we may recursively traverse over the object and replace reused and circular references by some kind of link.

var reused = {foo:1, bar:2}
var x = {
   a: reused,
   b: reused
}
x.c = x

It will look like this:

{
  a: {foo:1, bar:2},
  b: '@root.a',
  c: '@root'
}

2-circular-object-solution.js

const DEFAULT_PROTOCOL = {
    root: 'root',
    linkFn: p => `@${p}`,
    isLinkFn: p => ('' + p).startsWith('@'),
    delinkFn: (path, ref) => {
        const p = ref.replace(/^@/, '')
        return new Function('root', `${path} = ${p}`);
    }
}

function traverse(d, { root, isLinkFn, delinkFn } = DEFAULT_PROTOCOL, todo = [], path = false) {
    const pp = path || root
    if (typeof d === 'string' && isLinkFn(d)) {
        todo.push(delinkFn(`${pp}`, d))
        return todo
    }
    if (typeof d === 'object') {
        if (Array.isArray(d)) {
            d.forEach((val, ix) => {
                traverse(val, { root, isLinkFn, delinkFn }, todo, `${pp}[${ix}]`)
            })
            return todo
        } else {
            Object.keys(d).forEach((key) => {
                traverse(d[key], { root, isLinkFn, delinkFn }, todo, `${pp}.${key}`)
            })
            return todo
        }
    }
    return todo
}

export function pack(d, { root, linkFn } = DEFAULT_PROTOCOL, { path, visited = [] } = {}) {
    const pp = path || root
    if (d !== undefined && d !== null && typeof d === 'object') {
        visited.push({ path: pp, val: d })
        if (Array.isArray(d)) {
            return d.map((val, ix) => {
                const v = visited.find((t) => t.val === val)
                if (v) {
                    return linkFn(v.path)
                }
                return pack(val, { root, linkFn }, { path: `${pp}[${ix}]`, visited })
            })
        }
        return Object.keys(d).map((key) => {
            const v = visited.find((t) => t.val === d[key])
            if (v) {
                return { key, val: linkFn(v.path) }
            }
            return { key, val: pack(d[key], { root, linkFn }, { path: pp + '.' + key, linkFn, visited }) }
        }).reduce((acc, i) => ({ ...acc, [i.key]: i.val }), {})
    } else {
        return d
    }
}

export function unpack(d, protocol = DEFAULT_PROTOCOL) {
    const todo = traverse(d, protocol)
    todo.forEach(f => f(d))
    return d
}

3-circular-object-test.js

import {pack, unpack} from './circular-object-solution'

var a = { aa: 1, bb: 2 }
var b = [3, a]

var d = {
    foo: a,
    bar: b,
    deep: {
        deep:
        {
            deep: [a, b]
        }
    },
    long: [a, b, a, b, a, b, a]
}

d.circular = d

console.log('------------------------ Original ------------------------')
console.dir(d, { depth: null })

const packed = pack(d)
console.log('------------------------- Packed -------------------------')
console.log(JSON.stringify(packed, null, '  '))

const unpacked = unpack(packed)
console.log('------------------------ Unpacked ------------------------')
console.dir(unpacked, { depth: null })

4-output.md

------------------------ Original ------------------------
{
  foo: { aa: 1, bb: 2 },
  bar: [ 3, { aa: 1, bb: 2 } ],
  deep: {
    deep: {
      deep: [ { aa: 1, bb: 2 }, [ 3, { aa: 1, bb: 2 } ] ]
    }
  },
  long: [
    { aa: 1, bb: 2 },
    [ 3, { aa: 1, bb: 2 } ],
    { aa: 1, bb: 2 },
    [ 3, { aa: 1, bb: 2 } ],
    { aa: 1, bb: 2 },
    [ 3, { aa: 1, bb: 2 } ],
    { aa: 1, bb: 2 }
  ],
  circular: [Circular]
}
------------------------- Packed -------------------------
{
  "foo": {
    "aa": 1,
    "bb": 2
  },
  "bar": [
    3,
    "@root.foo"
  ],
  "deep": {
    "deep": {
      "deep": [
        "@root.foo",
        "@root.bar"
      ]
    }
  },
  "long": [
    "@root.foo",
    "@root.bar",
    "@root.foo",
    "@root.bar",
    "@root.foo",
    "@root.bar",
    "@root.foo"
  ],
  "circular": "@root"
}
------------------------ Unpacked ------------------------
{
  foo: { aa: 1, bb: 2 },
  bar: [ 3, { aa: 1, bb: 2 } ],
  deep: {
    deep: {
      deep: [ { aa: 1, bb: 2 }, [ 3, { aa: 1, bb: 2 } ] ]
    }
  },
  long: [
    { aa: 1, bb: 2 },
    [ 3, { aa: 1, bb: 2 } ],
    { aa: 1, bb: 2 },
    [ 3, { aa: 1, bb: 2 } ],
    { aa: 1, bb: 2 },
    [ 3, { aa: 1, bb: 2 } ],
    { aa: 1, bb: 2 }
  ],
  circular: [Circular]
}