Comparing 2 JSON objects structure in JavaScript

Question

I am using angular-translate for a big application. Having several people committing code + translations, many times the translation objects are not in sync.

I am building a Grunt plugin to look at both files' structure and compare it (just the keys and overall structure, not values).

The main goals are:

• Look into each file, and check if the structure of the whole object (or file, in this case) is the exact same as the translated ones;
• On error, return the key that doesn't match.

It turns out it was a bit more complicated than I anticipated. So i figured I could do something like:

1. Sort the object;
2. Check the type of data the value contains (since they are translations, it will only have strings, or objects for the nestings) and store it in another object, making the key equal to the original key and the value would be a string 'String', or an object in case it's an object. That object contains the children elements;
3. Recursively repeat steps 1-2 until the whole object is mapped and sorted;
4. Do the same for all the files
5. Stringify and compare everything.

A tiny example would be the following object:

{
  key1: 'cool',
  key2: 'cooler',
  keyWhatever: {
    anotherObject: {
      key1: 'better',
      keyX: 'awesome'
    },
    aObject: 'actually, it\'s a string'
  },
  aKey: 'more awesomeness'
}

would map to:

{
  aKey: 'String',
  key1: 'String',
  key2: 'String',
  keyWhatever: {
    aObject: 'String',
    anotherObject: {
      key1: 'String',
      keyX: 'String'
    }
  }
}

After this, I would stringify all the objects and proceed with a strict comparison.

My question is, is there a better way to perform this? Both in terms of simplicity and performance, since there are many translation files and they are fairly big.

I tried to look for libraries that would already do this, but I couldn't find any.

Thank you

EDIT: Thank you Jared for pointing out objects can't be sorted. I am ashamed for saying something like that :D Another solution could be iterating each of the properties on the main translation file, and in case they are strings, compare the key with the other files. In case they are objects, "enter" them, and do the same. Maybe it is even simpler than my first guess. What should be done?

Answer 1

Lets say you have two JSON objects, jsonA and jsonB.

function compareValues(a, b) {

    //if a and b aren't the same type, they can't be equal
    if (typeof a !== typeof b) {
        return false;
    }
 
    // Need the truthy guard because
    // typeof null === 'object'
    if (a && typeof a === 'object') {
        var keysA = Object.keys(a).sort(),
            keysB = Object.keys(b).sort();

        //if a and b are objects with different no of keys, unequal
        if (keysA.length !== keysB.length) {
            return false;
        }

        //if keys aren't all the same, unequal
        if (!keysA.every(function(k, i) { return k === keysB[i];})) {
            return false;
        }

        //recurse on the values for each key
        return keysA.every(function(key) {
            //if we made it here, they have identical keys
            return compareValues(a[key], b[key]);
        });

    //for primitives just use a straight up check
    } else {
        return a === b;
    }
}

//true if their structure, values, and keys are identical    
var passed = compareValues(jsonA, jsonB); 

Note that this can overflow the stack for deeply nested JSON objects. Note also that this will work for JSON but not necessarily regular JS objects as special handling is needed for Date Objects, Regexes, etc.

Answer 2

Sorting an array of the keys from the object works. However, sorting has an average time complexity of O(n⋅log(n)). We can do better. A fast general algorithm for ensuring two sets A and B are equivalent is as follows:

for item in B
  if item in A
    remove item from A
  else
    sets are not equivalent
sets are equivalent iff A is empty

To address @Katana31, we can detect circular references as we go by maintaining a set of visited objects and ensuring that all descendents of that object are not already in the list:

# poorly written pseudo-code
fn detectCycles(A, found = {})
  if A in found
    there is a cycle
  else
    found = clone(found)
    add A to found
    for child in A
      detectCycles(child, found)

Here's a complete implementation (you can find a simplified version that assumes JSON/non-circular input here):

var hasOwn = Object.prototype.hasOwnProperty;
var indexOf = Array.prototype.indexOf;

function isObjectEmpty(obj) {
  for (var key in obj) {
    return false;
  }

  return true;
}

function copyKeys(obj) {
  var newObj = {};

  for (var key in obj) {
    newObj[key] = undefined;
  }

  return newObj;
}

// compares the structure of arbitrary values
function compareObjectStructure(a, b) {
  return function innerCompare(a, b, pathA, pathB) {
    if (typeof a !== typeof b) {
      return false;
    }

    if (typeof a === 'object') {
      // both or neither, but not mismatched
      if (Array.isArray(a) !== Array.isArray(b)) {
        return false;
      }

      if (indexOf.call(pathA, a) !== -1 || indexOf.call(pathB, b) !== -1) {
        return false;
      }

      pathA = pathA.slice();
      pathA.push(a);

      pathB = pathB.slice();
      pathB.push(b);

      if (Array.isArray(a)) {
        // can't compare structure in array if we don't have items in both
        if (!a.length || !b.length) {
          return true;
        }

        for (var i = 1; i < a.length; i++) {
          if (!innerCompare(a[0], a[i], pathA, pathA)) {
            return false;
          }
        }

        for (var i = 0; i < b.length; i++) {
          if (!innerCompare(a[0], b[i], pathA, pathB)) {
            return false;
          }
        }

        return true;
      }

      var map = copyKeys(a), keys = Object.keys(b);

      for (var i = 0; i < keys.length; i++) {
        var key = keys[i];

        if (!hasOwn.call(map, key) || !innerCompare(a[key], b[key], pathA,
            pathB)) {
          return false;
        }

        delete map[key];
      }

      // we should've found all the keys in the map
      return isObjectEmpty(map);
    }

    return true;
  }(a, b, [], []);
}

Note that this implementation directly compares two objects for structural equivalency, but doesn't reduce the objects to a directly comparable value (like a string). I haven't done any performance testing, but I suspect that it won't add significant value, though it will remove the need to repeatedly ensure objects are non-cyclic. For that reason, you could easily split compareObjectStructure into two functions - one to compare the structure and one to check for cycles.

Answer 3

Actually you do need to sort the keys, as they are not required to be spit out in any particular order. Write a function,

function getComparableForObject(obj) {
    var keys = Object.keys(obj);
    keys.sort(a, b => a > b ? 1 : -1);

    var comparable = keys.map(
            key => key + ":" + getValueRepresentation(obj[key])
        ).join(",");
    return "{" + comparable + "}";
}

Where getValueRepresentation is a function that either returns "String" or calls getComparableForObject. If you are worried about circular references, add a Symbol to the outer scope, repr, assign obj[repr] = comparable in the function above, and in getValueRepresentation check every object for a defined obj[repr] and return it instead of processing it recursively.