Skip to content

Instantly share code, notes, and snippets.

@robertpitt
Forked from bruth/jsondiff.js
Created September 10, 2013 17:25
Show Gist options
  • Save robertpitt/6512680 to your computer and use it in GitHub Desktop.
Save robertpitt/6512680 to your computer and use it in GitHub Desktop.
var jsondiff = (function() {
// Patch helper functions
function getParent(paths, path) {
return paths[path.substr(0, path.match(/\//g).length)];
}
// Checks if `obj` is an array or object
function isContainer(obj) {
return _.isArray(obj) || _.isObject(obj);
}
// Checks if the two objects are of the same container type
function isSameContainer(obj1, obj2) {
return (_.isArray(obj1) && _.isArray(obj2)) || (_.isObject(obj1) && _.isObject(obj2));
}
// Flattens an object to a hash of paths and values.
function flattenObject(obj, prefix, paths) {
prefix || (prefix = '/');
paths || (paths = {});
// Do not bother logging the root path
paths[prefix] = {
path: prefix,
value: obj
};
prefix !== '/' && (prefix = prefix + '/')
// Recurse for container types
if (_.isArray(obj)) {
for (var i = 0, l = obj.length; i < l; i++) {
flattenObject(obj[i], prefix + i, paths);
}
} else if (_.isObject(obj)) {
for (var key in obj) {
flattenObject(obj[key], prefix + key, paths);
}
}
return paths;
}
// Constructs a patch that when applied to `obj2`, it will be equivalent
// to `obj1`. The patch format conforms to IETF JSON Patch proposal
// http://tools.ietf.org/html/draft-ietf-appsawg-json-patch-01
function constructPatch(obj1, obj2) {
// Patches are only applicable to two of the same container types.
if (!isSameContainer(obj1, obj2)) {
throw new Error('Patches can only be derived from objects or arrays');
}
var paths1 = flattenObject(obj1),
paths2 = flattenObject(obj2),
key1,
key2,
doc1,
doc2,
patch = [],
add = {},
remove = {},
replace = {},
move = {};
// Iterate over the first object's paths and compare them to the second
// set of paths.
for (key1 in paths1) {
doc1 = paths1[key1], doc2 = paths2[key1];
// If the parent of `doc2` doesn't exist, skip it since neither a
// remove or replace can occur.
if (!getParent(paths2, key1)) {
continue;
}
// If there is a miss in the second object, the key will be marked for
// removal.
if (!doc2) {
remove[key1] = doc1;
// If both members have existing values, make sure they are not the
// same container and they are not equal. If they are the same
// container type, values will be replaced downstream.
} else if (!isSameContainer(doc1.value, doc2.value) && !_.isEqual(doc1.value, doc2.value)) {
replace[key1] = doc2;
}
}
// Iterate over the second object's paths and compare them to the first
// set of paths.
for (key2 in paths2) {
doc1 = paths1[key2], doc2 = paths2[key2];
// Missing in first object, thus we mark it to be added.
// If the parent path is not present in the first obj, then this
// means the whole array/object is new.
if (!doc1 && isSameContainer(getParent(paths1, key2), getParent(paths2, key2))) {
add[key2] = doc2;
}
}
// Attempt to promote add/remove operations to a move operation.
// The first occurence of the same value, we can promote to a move.
for (key1 in remove) {
doc1 = remove[key1];
for (key2 in add) {
doc2 = add[key2];
if (_.isEqual(doc2.value, doc1.value)) {
// Remove them from previous hashes
delete remove[key1];
delete add[key2];
move[key1] = doc2
break;
}
}
}
var key;
// Populate the patch
for (key in add) {
patch.push({add: key, value: add[key].value});
}
for (key in remove) {
patch.push({remove: key});
}
for (key in replace) {
patch.push({replace: key, value: replace[key].value});
}
for (key in move) {
patch.push({move: key, to: move[key].path, value: move[key].value});
}
return patch;
}
return constructPatch;
})();
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment