Comparing the structure of JSON objects in JavaScript

Question

I use angular translators for a large application. Having several people making code translations +, many times the translation objects are not synchronized.

I am creating a Grunt plugin to look at the structure of both files and compare it (just keys and general structure, not values).

Basic goals:

• Look at each file and see if the structure of the entire object (or the file, in this case) exists - this is the same as the translated ones;
• On error, return a key that does not match.

Turns out it was a little harder than I expected. So I decided that I could do something like:

• Sort object ;
• Check the type of data that contains the value (since they are translations, it will only have strings or objects for attachments) and save them in another object, making the key equal to the original key, and the value will be string 'String' or object in case it is an object. This object contains children;
• Repeat steps 1-2 recursively until the entire object is matched and sorted;
• Do the same for all files
• String and compare everything.

A small example might be the following object:

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

will be displayed:

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

After that, I would contract all the objects and continue a rigorous comparison.

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

, , .

: , , . - : D , , , . , , "enter" . , , . ?

Answer 1

, JSON: jsonA 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;
    }

    if (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); 

, JSON. , JSON, JS, Date, Regexes .. .

Answer 2

, - . ,

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 + "}";
}

getValueRepresentation - , "String" getComparableForObject. , Symbol , repr, obj[repr] = comparable getValueRepresentation obj[repr] .

Answer 3

. O(n⋅log(n)). . A B :

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

@Katana31, , , :

# 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)

( , JSON/ ):

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 equivalence, but does not reduce the objects to a directly comparable value (for example, strings). I have not tested performance testing, but I suspect that it will not add meaningful value, although it will eliminate the need to re-ensure that objects are non-cyclic. For this reason, you can easily split compareObjectStructure into two functions - one for comparing structures and one for checking loops.