-/* JSON-delta v1.1.3 - A diff/patch pair for JSON-serialized data
-structures.
+/* JSON-delta v0.2 - A diff/patch pair for JSON-serialized data structures.
-Copyright 2013-2015 Philip J. Roberts <himself@phil-roberts.name>.
+Copyright 2013-2014 Philip J. Roberts <himself@phil-roberts.name>.
All rights reserved
Redistribution and use in source and binary forms, with or without
This implementation is based heavily on the original python2 version:
see http://www.phil-roberts.name/json-delta/ for further
documentation. */
-
JSON_delta = {
- // Main entry points: ======================================================
- patch: function(struc, diff) {
- /* Apply the sequence of diff stanzas diff to the structure
- struc, and returns the patched structure. */
- var stan_key;
- for (stan_key = 0; stan_key < diff.length; stan_key++) {
- struc = this.patchStanza(struc, diff[stan_key]);
- }
- return struc;
+ isStrictlyEqual: function (left, right) {
+ if (this.isTerminal(left) && this.isTerminal(right)) {
+ return (left === right);
+ }
+ if (this.isTerminal(left) || this.isTerminal(right)) {
+ return false;
+ }
+ if (left instanceof Array && right instanceof Array) {
+ if (left.length != right.length) {
+ return false;
+ }
+ for (idx in left) {
+ if ( ! this.isStrictlyEqual(left[idx], right[idx])) {
+ return false;
+ }
+ }
+ return true;
+ }
+ if (left instanceof Array || right instanceof Array) {
+ return false;
+ }
+ var ks = this.computeKeysets(left, right);
+ if (ks[1].length != 0 || ks[2].length != 0) {
+ return false;
+ }
+ for (key in ks[0]) {
+ key = ks[0][key];
+ if ( ! this.isStrictlyEqual(left[key], right[key])) {
+ return false
+ }
+ }
+ return true;
},
- diff: function(left, right, minimal, key) {
- /* Build a diff between the structures left and right.
-
- Parameters:
- key: this is used for mutual recursion between this
- function and those it calls. Normally it should be
- left unset or set as its default [].
-
- minimal: if this flag is set true, the function will try
- harder to find the diff that encodes as the shortest
- possible JSON string, at the expense of using more of
- both memory and processor time (as alternatives are
- computed and compared).
- */
- key = key !== undefined ? key : [];
- minimal = minimal !== undefined ? minimal : true;
- var dumbdiff = [[key, right]], my_diff = [], common;
-
- if (this.structureWorthInvestigating(left, right)) {
- common = this.commonality(left, right);
- if (minimal) {
- my_diff = this.needleDiff(left, right, minimal, key);
- } else if (common < 0.5) {
- my_diff = this.thisLevelDiff(left, right, key, common);
- } else {
- my_diff = this.keysetDiff(left, right, minimal, key);
- }
- } else {
- my_diff = this.thisLevelDiff(left, right, key, 0.0);
+ isTerminal: function (obj) {
+ if (typeof obj == "string" || typeof obj == "number"
+ || typeof obj == "boolean" || obj == null) {
+ return true;
}
-
- if (minimal) {
- if (JSON.stringify(dumbdiff).length <
- JSON.stringify(my_diff).length) {
- my_diff = dumbdiff;
- }
- }
-
- if (key.length === 0) {
- if (my_diff.length > 1) {
- my_diff = this.sortStanzas(my_diff);
- }
- }
- return my_diff;
+ return false;
},
- // =========================================================================
-
- isStrictlyEqual: function(left, right) {
- /* Recursively compare the (potentially nested) objects left
- * and right */
- var idx, ks, key;
- if (this.isTerminal(left) && this.isTerminal(right)) {
- return (left === right);
- }
- if (this.isTerminal(left) || this.isTerminal(right)) {
- return false;
- }
- if (left instanceof Array && right instanceof Array) {
- if (left.length !== right.length) {
- return false;
- }
- for (idx = 0; idx < left.length; idx++) {
- if (! this.isStrictlyEqual(left[idx], right[idx])) {
- return false;
- }
- }
- return true;
- }
- if (left instanceof Array || right instanceof Array) {
- return false;
- }
- ks = this.computeKeysets(left, right);
- if (ks[1].length !== 0 || ks[2].length !== 0) {
- return false;
- }
- for (idx = 0; idx < ks[0].length; idx++) {
- key = ks[0][idx];
- if (! this.isStrictlyEqual(left[key], right[key])) {
- return false;
- }
- }
- return true;
+ splitDeletions: function (diff) {
+ if (diff.length == 0) {return [[], diff]}
+ diff.sort(function (a,b) {return b.length-a.length});
+ for (idx in diff) {
+ if (diff[idx] > 1) {break}
+ }
+ return [diff.slice(0,idx), diff.slice(idx)]
},
- isTerminal: function(obj) {
- /* Test whether obj will be a terminal node in the tree when
- * serialized as JSON. */
- if (typeof obj === 'string' || typeof obj === 'number' ||
- typeof obj === 'boolean' || obj === null) {
- return true;
- }
- return false;
+ sortStanzas: function (diff) {
+ // Sorts the stanzas in a diff: node changes can occur in any
+ // order, but deletions from sequences have to happen last node
+ // first: ['foo', 'bar', 'baz'] -> ['foo', 'bar'] -> ['foo'] ->
+ // [] and additions to sequences have to happen
+ // leftmost-node-first: [] -> ['foo'] -> ['foo', 'bar'] ->
+ // ['foo', 'bar', 'baz'].
+
+
+ // First we divide the stanzas using splitDeletions():
+ var split_thing = this.splitDeletions(diff);
+ // Then we sort modifications in ascending order of last key:
+ split_thing[0].sort(function (a,b) {return a[0].slice(-1)[0]-b[0].slice(-1)[0]});
+ // And deletions in descending order of last key:
+ split_thing[1].sort(function (a,b) {return b[0].slice(-1)[0]-a[0].slice(-1)[0]});
+ // And recombine:
+ return split_thing[0].concat(split_thing[1])
},
- appendKey: function(stanzas, arr, key) {
- /* Get the appropriate key for appending to the array arr,
- * assuming that stanzas will also be applied, and arr appears
- * at key within the overall structure. */
- key = key !== undefined ? key : [];
- var addition_key = arr.length, prior_key, i;
- for (i = 0; i < stanzas.length; i++) {
- prior_key = stanzas[i][0];
- if (stanzas[i].length > 1 &&
- prior_key.length === key.length + 1 &&
- prior_key[prior_key.length-1] >= addition_key)
- { addition_key = prior_key[prior_key.length-1] + 1; }
+ computeKeysets: function (left, right) {
+ /* Returns an array of three arrays (overlap, left_only,
+ * right_only), representing the properties common to left and
+ * right, only defined for left, and only defined for right,
+ * respectively. */
+ var overlap = [], left_only = [], right_only = [];
+ var target = overlap;
+ var targ_num = (left instanceof Array);
+
+ for (key in left) {
+ if (targ_num) {
+ key = Number(key)
+ }
+ if (key in right) {
+ target = overlap;
+ }
+ else {
+ target = left_only;
+ }
+ target.push(key);
+ }
+ for (key in right) {
+ if (targ_num) {
+ key = Number(key)
+ }
+ if (! (key in left)) {
+ right_only.push(key);
+ }
}
- return addition_key;
+ return [overlap, left_only, right_only]
},
- loopOver: function(obj, callback) {
- /* Helper function for looping over obj. Does the Right Thing
- * whether obj is an array or not. */
- var i, key;
- if (obj instanceof Array) {
- for (i = 0; i < obj.length; i++) {
- callback(obj, i);
+ commonality: function (left, right) {
+ var com = 0;
+ var tot = 0;
+ if (this.isTerminal(left) || this.isTerminal(right)) {
+ return 0;
+ }
+
+ if ((left instanceof Array) && (right instanceof Array)) {
+ for (idx in left) {
+ elem = left[idx];
+ if (right.indexOf(elem) != -1) {
+ com += 1;
+ }
}
- } else {
- for (key in obj) {
- if (obj.hasOwnProperty(key)) {
- callback(obj, key);
+ tot = Math.max(left.length, right.length);
+ }
+ else if ((left instanceof Array) || (right instanceof Array)) {
+ return 0;
+ }
+ else {
+ var ks = this.computeKeysets(left, right);
+ o = ks[0]; l = ks[1]; r = ks[2];
+ com = o.length;
+ tot = o.length + l.length + r.length;
+ for (idx in r) {
+ elem = r[idx];
+ if (l.indexOf(elem) == -1) {
+ tot += 1
}
}
}
+ if (tot == 0) {return 0}
+ return com / tot;
},
- splitDeletions: function(diff) {
- /* Split the stanzas in diff into an array of two arrays:
- * [modifications, deletions]. */
- var idx;
- if (diff.length === 0) {return [[], diff];}
- diff.sort(function(a, b) {return b.length - a.length;});
- for (idx = 0; idx < diff.length; idx++) {
- if (diff[idx].length === 1) {break;}
- }
- return [diff.slice(0, idx), diff.slice(idx)];
- },
-
- sortStanzas: function(diff) {
- /* Sorts the stanzas in a diff: node changes can occur in any
- * order, but deletions from sequences have to happen last
- * node first: ['foo', 'bar', 'baz'] -> ['foo', 'bar'] ->
- * ['foo'] -> [] and additions to sequences have to happen
- * leftmost-node-first: [] -> ['foo'] -> ['foo', 'bar'] ->
- * ['foo', 'bar', 'baz']. */
-
- // First we divide the stanzas using splitDeletions():
- var split_thing = this.splitDeletions(diff);
- // Then we sort modifications in ascending order of last key:
- split_thing[0].sort(
- function(a, b) {return a[0].slice(-1)[0] - b[0].slice(-1)[0];}
- );
- // And deletions in descending order of last key:
- split_thing[1].sort(
- function(a, b) {return b[0].slice(-1)[0] - a[0].slice(-1)[0];}
- );
- // And recombine:
- return split_thing[0].concat(split_thing[1]);
- },
+ thisLevelDiff: function (left, right, key, common) {
+ // Returns a sequence of diff stanzas between the objects left and
+ // right, assuming that they are each at the position key within
+ // the overall structure.
+ var out = [];
+ key = typeof key !== 'undefined' ? key: [];
- computeKeysets: function(left, right) {
- /* Returns an array of three arrays (overlap, left_only,
- * right_only), representing the properties common to left and
- * right, only defined for left, and only defined for right,
- * respectively. */
- var overlap = [], left_only = [], right_only = [];
- var target = overlap;
+ if (typeof common == 'undefined') {
+ common = this.commonality(left, right);
+ }
- this.loopOver(left, function(obj, key) {
- if (right[key] !== undefined) {
- target = overlap;
- }
- else {
- target = left_only;
- }
- target.push(key);
- });
- this.loopOver(right, function(obj, key) {
- if (left[key] === undefined) {
- right_only.push(key);
- }
- });
- return [overlap, left_only, right_only];
+ if (common) {
+ var ks = this.computeKeysets(left, right);
+ for (idx in ks[0]) {
+ okey = ks[0][idx];
+ if (left[okey] != right[okey]) {
+ out.push([key.concat([okey]), right[okey]]);
+ }
+ }
+ for (idx in ks[1]) {
+ okey = ks[1][idx];
+ out.push([key.concat([okey])]);
+ }
+ for (idx in ks[2]) {
+ okey = ks[2][idx];
+ out.push([key.concat([okey]), right[okey]]);
+ }
+ return out
+ }
+ else if ( ! this.isStrictlyEqual(left,right)) {
+ return [[key, right]]
+ }
+ else {
+ return []
+ }
},
- structureWorthInvestigating: function(left, right) {
- /* Test whether it is worth looking at the internal structure
- * of `left` and `right` to see if they can be efficiently
- * diffed. */
- if (this.isTerminal(left) || this.isTerminal(right)) {
- return false;
- }
- if ((left.length === 0) || (right.length === 0)) {
- return false;
+ keysetDiff: function (left, right, key) {
+ var out = [];
+ var ks = this.computeKeysets(left, right);
+ for (k in ks[1]) {
+ out.push([key.concat(ks[1][k])]);
}
- if ((left instanceof Array) && (right instanceof Array)) {
- return true;
+ for (k in ks[2]) {
+ out.push([key.concat(ks[2][k]), right[ks[2][k]]]);
}
- if ((left instanceof Array) || (right instanceof Array)) {
- return false;
- }
- if ((typeof left === 'object') && (typeof right === 'object')) {
- return true;
+ for (k in ks[0]) {
+ out = out.concat(this.diff(left[ks[0][k]], right[ks[0][k]],
+ key.concat([ks[0][k]])))
}
- return false;
+ return out;
},
- commonality: function(left, right) {
- /* Calculate the amount that the structures left and right
- * have in common */
- var com = 0, tot = 0;
- var elem, keysets, o, l, r, idx;
- if (this.isTerminal(left) || this.isTerminal(right)) {
- return 0;
- }
-
- if ((left instanceof Array) && (right instanceof Array)) {
- for (idx = 0; idx < left.length; idx++) {
- elem = left[idx];
- if (right.indexOf(elem) !== -1) {
- com++;
- }
- }
- tot = Math.max(left.length, right.length);
- }
- else {
- if ((left instanceof Array) || (right instanceof Array)) {
- return 0;
- }
- keysets = this.computeKeysets(left, right);
- o = keysets[0]; l = keysets[1]; r = keysets[2];
- com = o.length;
- tot = o.length + l.length + r.length;
- for (idx = 0; idx < r.length; idx++) {
- elem = r[idx];
- if (l.indexOf(elem) === -1) {
- tot++;
- }
- }
- }
- if (tot === 0) {return 0;}
- return com / tot;
+ patchStanza: function (struc, diff) {
+ // Applies the diff stanza diff to the structure struc. Returns
+ // the modified structure.
+ key = diff[0];
+ switch (key.length) {
+ case 0:
+ struc = diff[1];
+ break;
+ case 1:
+ if (diff.length == 1) {
+ if (typeof struc.splice == 'undefined') {
+ delete struc[key[0]];
+ }
+ else {
+ struc.splice(key[0], 1);
+ }
+ }
+ else {
+ struc[key[0]] = diff[1];
+ }
+ break;
+ default:
+ pass_key = key.slice(1);
+ pass_struc = struc[key[0]];
+ pass_diff = [pass_key].concat(diff.slice(1));
+ struc[key[0]] = this.patchStanza(pass_struc, pass_diff);
+ }
+ return struc;
},
- thisLevelDiff: function(left, right, key, common) {
- /* Returns a sequence of diff stanzas between the objects left
- * and right, assuming that they are each at the position key
- * within the overall structure. */
- var out = [], idx, okey;
- key = key !== undefined ? key : [];
-
- if (common === undefined) {
- common = this.commonality(left, right);
- }
-
- if (common) {
- var ks = this.computeKeysets(left, right);
- for (idx = 0; idx < ks[0].length; idx++) {
- okey = ks[0][idx];
- if (left[okey] !== right[okey]) {
- out.push([key.concat([okey]), right[okey]]);
- }
- }
- for (idx = 0; idx < ks[1].length; idx++) {
- okey = ks[1][idx];
- out.push([key.concat([okey])]);
- }
- for (idx = 0; idx < ks[2].length; idx++) {
- okey = ks[2][idx];
- out.push([key.concat([okey]), right[okey]]);
- }
- return out;
- }
- if (! this.isStrictlyEqual(left, right)) {
- return [[key, right]];
- }
- return [];
+ patch: function (struc, diff) {
+ // Applies the sequence of diff stanzas diff to the structure
+ // struc, and returns the patched structure.
+ for (stan_key in diff) {
+ struc = this.patchStanza(struc, diff[stan_key]);
+ }
+ return struc
},
- keysetDiff: function(left, right, minimal, key) {
- /* Compute a diff between left and right, without treating
- * arrays differently from objects. */
- minimal = minimal !== undefined ? minimal : true;
- var out = [], k;
- var ks = this.computeKeysets(left, right);
- for (k = 0; k < ks[1].length; k++) {
- out.push([key.concat(ks[1][k])]);
- }
- for (k = 0; k < ks[2].length; k++) {
- out.push([key.concat(ks[2][k]), right[ks[2][k]]]);
- }
- for (k = 0; k < ks[0].length; k++) {
- out = out.concat(this.diff(left[ks[0][k]], right[ks[0][k]],
- minimal, key.concat([ks[0][k]])));
- }
- return out;
- },
+ diff: function (left, right, key, minimal) {
+ key = typeof key !== 'undefined' ? key : [];
+ minimal = typeof minimal !== 'undefined' ? minimal: true;
+ var dumbdiff = [[key, right]]
+ var my_diff = [];
- needleDiff: function(left, right, minimal, key) {
- /* Compute a diff between left and right. If both are arrays,
- * a variant of Needleman-Wunsch sequence alignment is used to
- * make the diff minimal (at a significant cost in both
- * storage and processing). Otherwise, the parms are passed on
- * to keysetDiff.*/
- if (! (left instanceof Array && right instanceof Array)) {
- return this.keysetDiff(left, right, minimal, key);
+ common = this.commonality(left, right);
+ if (common < 0.5) {
+ my_diff = this.thisLevelDiff(left, right, key, common);
}
- minimal = minimal !== undefined ? minimal : true;
- var down_col = 0, lastrow = [], i, sub_i, left_i, right_i, col_i;
- var row, first_left_i, left_elem, right_elem;
- var cand_length, win_length, cand, winner;
-
- var modify_cand = function () {
- if (col_i + 1 < lastrow.length) {
- return lastrow[col_i+1].concat(
- JSON_delta.diff(left_elem, right_elem,
- minimal, key.concat([left_i]))
- );
- }
- };
-
- var delete_cand = function () {
- if (row.length > 0) {
- return row[0].concat([[key.concat([left_i])]]);
- }
- };
-
- var append_cand = function () {
- if (col_i === down_col) {
- return lastrow[col_i].concat(
- [[key.concat([JSON_delta.appendKey(lastrow[col_i], left, key)]),
- right_elem]]
- );
- }
- };
- var cand_funcs = [modify_cand, delete_cand, append_cand];
-
- for (i = 0; i <= left.length; i++) {
- lastrow.unshift([]);
- for (sub_i = 0; sub_i < i; sub_i++) {
- lastrow[0].push([key.concat([sub_i])]);
- }
+ else {
+ my_diff = this.keysetDiff(left, right, key);
}
- for (right_i = 0; right_i < right.length; right_i++) {
- right_elem = right[right_i];
- first_left_i = Math.min(right_i, left.length - 1);
- row = [];
- for (left_i = first_left_i; left_i < left.length; left_i++) {
- left_elem = left[left_i];
- col_i = left.length - left_i - 1;
- win_length = Infinity;
- for (i = 0; i < cand_funcs.length; i++) {
- cand = cand_funcs[i]();
- if (cand !== undefined) {
- cand_length = JSON.stringify(cand).length;
- if (cand_length < win_length) {
- winner = cand;
- win_length = cand_length;
- }
- }
- }
- row.unshift(winner);
+ if (minimal) {
+ if (JSON.stringify(dumbdiff).length <
+ JSON.stringify(my_diff).length) {
+ my_diff = dumbdiff
}
- lastrow = row;
}
- return winner;
- },
- patchStanza: function(struc, diff) {
- /* Applies the diff stanza diff to the structure struc.
- Returns the modified structure. */
- var key = diff[0];
- switch (key.length) {
- case 0:
- struc = diff[1];
- break;
- case 1:
- if (diff.length === 1) {
- if (struc.splice === undefined) {
- delete struc[key[0]];
- }
- else {
- struc.splice(key[0], 1);
- }
- }
- else {
- struc[key[0]] = diff[1];
- }
- break;
- default:
- var pass_key = key.slice(1), pass_struc = struc[key[0]];
- var pass_diff = [pass_key].concat(diff.slice(1));
- if (pass_struc === undefined) {
- if (typeof pass_key[0] === 'string') {
- pass_struc = {};
- } else {
- pass_struc = [];
- }
+ if (key.length == 0) {
+ if (my_diff.length > 1) {
+ my_diff = this.sortStanzas(my_diff);
}
- struc[key[0]] = this.patchStanza(pass_struc, pass_diff);
- }
- return struc;
+ }
+ return my_diff;
}
-};
+}
+
+// node.js
+if (typeof exports !== 'undefined') exports.JSON_delta = JSON_delta;
projects / remoteglot / blobdiff