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.

Answer 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);