Generic deep diff between two objects

Question

I have two objects: oldObj and newObj.

The data in oldObj was used to populate a form and newObj is the result of the user changing data in this form and submitting it.

Both objects are deep, ie. they have properties that are objects or arrays of objects etc - they can be n levels deep, thus the diff algorithm needs to be recursive.

Now I need to not just figure out what was changed (as in added/updated/deleted) from oldObj to newObj, but also how to best represent it.

So far my thoughts was to just build a genericDeepDiffBetweenObjects method that would return an object on the form {add:{...},upd:{...},del:{...}} but then I thought: somebody else must have needed this before.

So... does anyone know of a library or a piece of code that will do this and maybe have an even better way of representing the difference (in a way that is still JSON serializable)?

Update:

I have thought of a better way to represent the updated data, by using the same object structure as newObj, but turning all property values into objects on the form:

{type: '<update|create|delete>', data: <propertyValue>}

So if newObj.prop1 = 'new value' and oldObj.prop1 = 'old value' it would set returnObj.prop1 = {type: 'update', data: 'new value'}

Update 2:

It gets truely hairy when we get to properties that are arrays, since the array [1,2,3] should be counted as equal to [2,3,1], which is simple enough for arrays of value based types like string, int & bool, but gets really difficult to handle when it comes to arrays of reference types like objects and arrays.

Example arrays that should be found equal:

[1,[{c: 1},2,3],{a:'hey'}] and [{a:'hey'},1,[3,{c: 1},2]]

Not only is it quite complex to check for this type of deep value equality, but also to figure out a good way to represent the changes that might be.

Solution 1

I wrote a little class that is doing what you want, you can test it here.

Only thing that is different from your proposal is that I don't consider

[1,[{c: 1},2,3],{a:'hey'}]

and

[{a:'hey'},1,[3,{c: 1},2]]

to be same, because I think that arrays are not equal if order of their elements is not same. Of course this can be changed if needed. Also this code can be further enhanced to take function as argument that will be used to format diff object in arbitrary way based on passed primitive values (now this job is done by "compareValues" method).

var deepDiffMapper = function () {
  return {
    VALUE_CREATED: 'created',
    VALUE_UPDATED: 'updated',
    VALUE_DELETED: 'deleted',
    VALUE_UNCHANGED: 'unchanged',
    map: function(obj1, obj2) {
      if (this.isFunction(obj1) || this.isFunction(obj2)) {
        throw 'Invalid argument. Function given, object expected.';
      }
      if (this.isValue(obj1) || this.isValue(obj2)) {
        return {
          type: this.compareValues(obj1, obj2),
          data: obj1 === undefined ? obj2 : obj1
        };
      }

      var diff = {};
      for (var key in obj1) {
        if (this.isFunction(obj1[key])) {
          continue;
        }

        var value2 = undefined;
        if (obj2[key] !== undefined) {
          value2 = obj2[key];
        }

        diff[key] = this.map(obj1[key], value2);
      }
      for (var key in obj2) {
        if (this.isFunction(obj2[key]) || diff[key] !== undefined) {
          continue;
        }

        diff[key] = this.map(undefined, obj2[key]);
      }

      return diff;

    },
    compareValues: function (value1, value2) {
      if (value1 === value2) {
        return this.VALUE_UNCHANGED;
      }
      if (this.isDate(value1) && this.isDate(value2) && value1.getTime() === value2.getTime()) {
        return this.VALUE_UNCHANGED;
      }
      if (value1 === undefined) {
        return this.VALUE_CREATED;
      }
      if (value2 === undefined) {
        return this.VALUE_DELETED;
      }
      return this.VALUE_UPDATED;
    },
    isFunction: function (x) {
      return Object.prototype.toString.call(x) === '[object Function]';
    },
    isArray: function (x) {
      return Object.prototype.toString.call(x) === '[object Array]';
    },
    isDate: function (x) {
      return Object.prototype.toString.call(x) === '[object Date]';
    },
    isObject: function (x) {
      return Object.prototype.toString.call(x) === '[object Object]';
    },
    isValue: function (x) {
      return !this.isObject(x) && !this.isArray(x);
    }
  }
}();


var result = deepDiffMapper.map({
  a: 'i am unchanged',
  b: 'i am deleted',
  e: {
    a: 1,
    b: false,
    c: null
  },
  f: [1, {
    a: 'same',
    b: [{
      a: 'same'
    }, {
      d: 'delete'
    }]
  }],
  g: new Date('2017.11.25')
}, {
  a: 'i am unchanged',
  c: 'i am created',
  e: {
    a: '1',
    b: '',
    d: 'created'
  },
  f: [{
    a: 'same',
    b: [{
      a: 'same'
    }, {
      c: 'create'
    }]
  }, 1],
  g: new Date('2017.11.25')
});
console.log(result);

Solution 2

Using Underscore, a simple diff:

var o1 = {a: 1, b: 2, c: 2},
    o2 = {a: 2, b: 1, c: 2};

_.omit(o1, function(v,k) { return o2[k] === v; })

Results in the parts of o1 that correspond but with different values in o2:

{a: 1, b: 2}

It'd be different for a deep diff:

function diff(a,b) {
    var r = {};
    _.each(a, function(v,k) {
        if(b[k] === v) return;
        // but what if it returns an empty object? still attach?
        r[k] = _.isObject(v)
                ? _.diff(v, b[k])
                : v
            ;
        });
    return r;
}

As pointed out by @Juhana in the comments, the above is only a diff a-->b and not reversible (meaning extra properties in b would be ignored). Use instead a-->b-->a:

(function(_) {
  function deepDiff(a, b, r) {
    _.each(a, function(v, k) {
      // already checked this or equal...
      if (r.hasOwnProperty(k) || b[k] === v) return;
      // but what if it returns an empty object? still attach?
      r[k] = _.isObject(v) ? _.diff(v, b[k]) : v;
    });
  }

  /* the function */
  _.mixin({
    diff: function(a, b) {
      var r = {};
      deepDiff(a, b, r);
      deepDiff(b, a, r);
      return r;
    }
  });
})(_.noConflict());

See http://jsfiddle.net/drzaus/9g5qoxwj/ for full example+tests+mixins

Solution 3

I'd like to offer an ES6 solution...This is a one-way diff, meaning that it will return keys/values from o2 that are not identical to their counterparts in o1:

let o1 = {
  one: 1,
  two: 2,
  three: 3
}

let o2 = {
  two: 2,
  three: 3,
  four: 4
}

let diff = Object.keys(o2).reduce((diff, key) => {
  if (o1[key] === o2[key]) return diff
  return {
    ...diff,
    [key]: o2[key]
  }
}, {})

Solution 4

Using Lodash:

_.mergeWith(oldObj, newObj, function (objectValue, sourceValue, key, object, source) {
    if ( !(_.isEqual(objectValue, sourceValue)) && (Object(objectValue) !== objectValue)) {
        console.log(key + "\n    Expected: " + sourceValue + "\n    Actual: " + objectValue);
    }
});

I don't use key/object/source but I left it in there if you need to access them. The object comparison just prevents the console from printing the differences to the console from the outermost element to the innermost element.

You can add some logic inside to handle arrays. Perhaps sort the arrays first. This is a very flexible solution.

EDIT

Changed from _.merge to _.mergeWith due to lodash update. Thanks Aviron for noticing the change.

Solution 5

Here is a JavaScript library which can be used for finding diff between two JavaScript objects:

Github URL: https://github.com/cosmicanant/recursive-diff

Npmjs url: https://www.npmjs.com/package/recursive-diff

recursive-diff library can be used in the browser as well as in a Node.js based server side application. For browser, it can be used as below:

<script type="text" src="https://unpkg.com/recursive-diff@latest/dist/recursive-diff.min.js"/>
<script type="text/javascript">
     const ob1 = {a:1, b: [2,3]};
     const ob2 = {a:2, b: [3,3,1]};
     const delta = recursiveDiff.getDiff(ob1,ob2); 
     /* console.log(delta) will dump following data 
     [
         {path: ['a'], op: 'update', val: 2}
         {path: ['b', '0'], op: 'update',val: 3},
         {path: ['b',2], op: 'add', val: 1 },
     ]
      */
     const ob3 = recursiveDiff.applyDiff(ob1, delta); //expect ob3 is deep equal to ob2
 </script>

Whereas in a node.js based application it can be used as below:

const diff = require('recursive-diff');
const ob1 = {a: 1}, ob2: {b:2};
const diff = diff.getDiff(ob1, ob2);

View more solutions

Comments

[a'r]

possible duplicate of Difference in JSON objects using Javascript/JQuery

[Martin Jespersen]

@a'r: It is not a duplicate of stackoverflow.com/questions/1200562/… - I know how to traverse the objects, I am looking for prior art since this is non trivial and will take real time to implement, and I'd rather use a library than make it from scratch.

[sbgoran]

Do you really need diff of objects, is that newObj generated from server on form submit response? Because if you don't have "server updates" of a object you could simplify your problem by attaching appropriate event listeners and upon user interaction (object change) you could update/generate wanted change list.

[Martin Jespersen]

@sbgoran: newObj is generated by js code reading values from a form in the DOM. There are several ways to keep state and do this much easier, but I'd like to keep it stateless as an exercise. Also I am looking for prior art to see how others might have tackled this, if indeed anyone has.

[Benja]

here's a very sophisticated library to diff/patch any pair of Javascript objects github.com/benjamine/jsondiffpatch you can see it live here: benjamine.github.io/jsondiffpatch/demo/index.html (disclaimer: I'm the author)

[Martin Jespersen]

+1 It's not a bad piece of code. There is a bug however (check this example out: jsfiddle.net/kySNu/3 c is created as undefined but should be the string 'i am created'), and besides it doesn't do what I need since it is lacking the deep array value compare which is the most crucial (and complex/difficult) part. As a side note the construct 'array' != typeof(obj) is useless since arrays are objects that are instances of arrays.

[sbgoran]

I updated code, but I'm not sure what value you want in resulting object, right now code is returning value from first object and if it doesn't exist value from second one will be set as data.

[sbgoran]

And how do you mean "lacking the deep array value compare" for arrays you'll get for each index that {type: ..., data:..} object. What is missing is searching value from first array in second, but as I mentioned in my answer I don't think that arrays are equal if order of their values are not equal ([1, 2, 3] is not equal to [3, 2, 1] in my opinion).

[Martin Jespersen]

Despite your opinion, the data is in fact equal, as in - the data is in a database and an array reflects a table (which might or might not have subtables etc)

[sbgoran]

@MartinJespersen OK, how would you generically treat this arrays then: [{key: 'value1'}] and [{key: 'value2'}, {key: 'value3'}]. Now is first object in first array updated with "value1" or "value2". And this is simple example, it could get much complicated with deep nesting. If you want/need deep nesting comparison regardless of key position don't create arrays of objects, create objects with nested objects like for previous example: {inner: {key: 'value1'}} and {inner: {key: 'value2'}, otherInner: {key: 'value3'}}.

[Martin Jespersen]

I agree with you last point of view - the original data structure should be changed to something that is easier to do an actual diff on. Congrats, you nailed it :)

[bm_i]

Nice solution but you might want to check that if(o1[key] === o1[key]) line dude

[Aviran Cohen]

In lodash 4.15.0 _.merge with customizer function is no longer supported so you should use _.mergeWith instead.

[PerfectPixel]

There is a minor flaw when it comes to boolean values. If obj1 = true and obj2 = false, the assignment data: obj1 || obj2 will yield true even though the type is updated. This can be solved with a more strict check data: obj2 === undefined ? obj1 : obj2.

[sbgoran]

@PerfectPixel Thanks, I updated the code with more strict check, but I used obj1 value as a default to stay inline with previous logic.

[PerfectPixel]

@sbgoran thanks for the update. However using obj1 as a default will yield an incorrect diff. I modified your fiddle an added the property g which is updated from true to false. Expected would be data false and type changed. However obj1 !== undefined, therefore, obj1 is used and data is true not false. Here is the fiddle: jsfiddle.net/kySNu/275 :-)

[Sander van den Akker]

Unfortunately this code does not work with javascript date objects. Those are always flagged as being updated.

[xpy]

Please include the code in your answer as well, not just a fiddle.

[Sean H]

Is the code complete? I'm getting Uncaught SyntaxError: Unexpected token ...

[senornestor]

It works for me in the console of Chrome 58. The let keyword is ES6 and the ... object spread operator is ES future, so you need to run this in an environment that supports them.

[Ulysse BN]

May miss a little bit of explanation, but at least this one works like a charm, +1!

[Spurious]

I like the solution but it has one problem, if the object is deeper than one level, it will return all the values in the changed nested objects - or at least that's whats happening for me.

[Nemesarial]

Yup, this is not recursive @Spurious

[SrAxi]

great solution! Updated with ES6, just what I was looking for. Make it recursive is quite straight forward. Thanks!

[Malvineous]

Just bear in mind that with this solution, for each element in the object you get an entirely new object built with all existing elements copied into it just to add one item to the array. For small objects it's fine, but it will slow down exponentially for larger objects.

[Raven]

It seems like defineProperty would solve this problem with better performance, if i remember correctly it works all the way down to IE9.

[Ben Taliadoros]

Does the return { ...diff, [key]: o2[key] } diff attribute not need to be named?

[senornestor]

Ben, the [key] is a "computed property name" meaning that the value of key will be used as the property name in the object.

[Tofandel]

This also doesn't work if the elements inside are objects {a: '1', b: '2'} === {a: '1', b: '2'} is false because they are different objects you need to add a check like if (typeof o1[key] === "object" && typeof o2[key] === "object") { return JSON.stringify(o1[key]) === JSON.stringify(o2[key]); } You also need to concat the keys of both objects to get a full diff Object.keys(o1).concat(Object.keys(o2)).reduce(...)

[Joe Allen]

this function is great but not working in nested object.

[Anant]

date support is added

[Michael Freidgeim]

@SrAxi, how to Make it recursive?

[SrAxi]

@MichaelFreidgeim Transform that into a function that accepts 2 objects. Inside it, whenever you iterate, call itself passing the object that you want to compare to and current object in iteration.

[shieldgenerator7]

you know an answer is good when it gets copied and modified a lot

[Endless]

Ty, the original was too verbose. But i had to modify it further to also check for typed arrays... isArray: x => Array.isArray(x) || ArrayBuffer.isView(x)

[user3245268]

Should this be marked as the correct answer now?

[davidmars]

this is the way

[Someone Special]

what doesR represent??

[Ivan Titkov]

@SomeoneSpecial it is ramda js library ramdajs.com

[Mike 'Pomax' Kamermans]

This looks like this is still lacking the move operation. Not everything is a set, unset, or update.

[Mike 'Pomax' Kamermans]

Unfortunately it looks like this never added "move" support, which is pretty crucial for preserving object references, rather than blindly rebuilding inert content that happens to have the same object shape.

[redshift]

nice and simple. Thanks.

[slugmandrew]

This is a nice improvement, though worth mentioning that if the two objects match then it just returns undefined :)

[Daniel]

If you have some parameters not showing up no matter which is your obj1 you can combine them with Object.assign({}, deepDifference(obj1,obj2), deepDifference(obj1,obj2));