js detect cyclic references in objects

js detect cyclic references in objects


If you ever have to recurse through a javascript object then cyclic or copied references can be a problem. Here's a rad algorithm to fix that.

In trying to deal with this I did have a look at a few existing resources like
this post from 2011 and this S/O question.

Basically you recurse through the object and store each object in an array, and then use Array.prototype.indexOf to check whether any object you're testing has been seen before.

That's great, but I wanted to render objects to be human readable, which adds a few problems beyond merely detecting cyclic or copied objects:

  • Say an object appears once at the root level, and then under a different parent, buried deep in the structure. I want to be sure that the root level object is the "real" one, and the deep one is marked as a "copy".
  • When a copy is found, I want the path to the "real" object.
  • I don't want to mutate the actual object.

To explain what I mean, consider an object like this:

let someObject = {}
    let obj = {
      a: {
        b: {
          c: someObject
        }
      },
      d: someObject
    }
    

I want to ensure that I end up with something like this:

{
      a: {
        b: {
          c: '[Copy root > d]'
        }
      },
      d: someObject
    }
    

So with these requirements in mind.. this is what I came up with.

import set from 'lodash.set'
    function render (obj) {
      // use copy so we don't mutate files
      let copy = {}
      // store objects, for loop below will iterate over them
      let list = [ obj ]
      // store paths
      //  - each item will align with list above
      //  - each item will be an array, which can be passed to lodash.set
      let paths = [ [ 'root' ] ]
      // this for loop allows you to mutate list inside iteration
      for (let idx = 0; idx < list.length; idx++) {
        let item = list[idx]
        // iterate over properties contained in each item, copy as necessary, add to
        // list as required
        Object.keys(item).forEach((key) => {
          // store path of current item
          let path = paths[idx].concat([key])
          // check if this item has been rendered already
          let copyIdx = list.indexOf(item[key])
          if (~copyIdx) {
            return set(copy, path, `[Copy: ${paths[copyIdx].join(' > ')}]`)
          }
          // store objects so we can iterate over them
          if (item[key] instanceof Object) {
            list.push(item[key])
            paths.push(path)
            return
          }
          // if none of the above apply, just stash the value
          set(copy, path, item[key])
        })
      }
      return copy.root
    }
    

Purists will groan at the use of lodash.set, you could copypasta the set fn from lodash if that's how you roll. It's fairly long and complex though.. I don't see the problem in letting lodash maintain it.