1 /* JSON-delta v2.0 - A diff/patch pair for JSON-serialized data
4 Copyright 2013-2015 Philip J. Roberts <himself@phil-roberts.name>.
7 Redistribution and use in source and binary forms, with or without
8 modification, are permitted provided that the following conditions are
11 1. Redistributions of source code must retain the above copyright
12 notice, this list of conditions and the following disclaimer.
14 2. Redistributions in binary form must reproduce the above copyright
15 notice, this list of conditions and the following disclaimer in the
16 documentation and/or other materials provided with the distribution.
18 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22 HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 This implementation is based heavily on the original python2 version:
31 see http://www.phil-roberts.name/json-delta/ for further
35 // Main entry points: ======================================================
36 patch: function(struc, diff) {
37 /* Apply the sequence of diff stanzas diff to the structure
38 struc, and returns the patched structure. */
40 for (stan_key = 0; stan_key < diff.length; stan_key++) {
41 struc = this.patchStanza(struc, diff[stan_key]);
46 diff: function(left, right, minimal, key) {
47 /* Build a diff between the structures left and right.
50 key: this is used for mutual recursion between this
51 function and those it calls. Normally it should be
52 left unset or set as its default [].
54 minimal: if this flag is set true, the function will try
55 harder to find the diff that encodes as the shortest
56 possible JSON string, at the expense of using more of
57 both memory and processor time (as alternatives are
58 computed and compared).
60 key = key !== undefined ? key : [];
61 minimal = minimal !== undefined ? minimal : true;
62 var dumbdiff = [[key, right]], my_diff = [], common;
64 if (this.structureWorthInvestigating(left, right)) {
65 common = this.commonality(left, right);
67 my_diff = this.needleDiff(left, right, minimal, key);
68 } else if (common < 0.5) {
69 my_diff = this.thisLevelDiff(left, right, key, common);
71 my_diff = this.keysetDiff(left, right, minimal, key);
74 my_diff = this.thisLevelDiff(left, right, key, 0.0);
78 if (JSON.stringify(dumbdiff).length <
79 JSON.stringify(my_diff).length) {
84 if (key.length === 0) {
85 if (my_diff.length > 1) {
86 my_diff = this.sortStanzas(my_diff);
92 // =========================================================================
94 isStrictlyEqual: function(left, right) {
95 /* Recursively compare the (potentially nested) objects left
98 if (this.isTerminal(left) && this.isTerminal(right)) {
99 return (left === right);
101 if (this.isTerminal(left) || this.isTerminal(right)) {
104 if (left instanceof Array && right instanceof Array) {
105 if (left.length !== right.length) {
108 for (idx = 0; idx < left.length; idx++) {
109 if (! this.isStrictlyEqual(left[idx], right[idx])) {
115 if (left instanceof Array || right instanceof Array) {
118 ks = this.computeKeysets(left, right);
119 if (ks[1].length !== 0 || ks[2].length !== 0) {
122 for (idx = 0; idx < ks[0].length; idx++) {
124 if (! this.isStrictlyEqual(left[key], right[key])) {
131 isTerminal: function(obj) {
132 /* Test whether obj will be a terminal node in the tree when
133 * serialized as JSON. */
134 if (typeof obj === 'string' || typeof obj === 'number' ||
135 typeof obj === 'boolean' || obj === null) {
141 appendKey: function(stanzas, arr, key) {
142 /* Get the appropriate key for appending to the array arr,
143 * assuming that stanzas will also be applied, and arr appears
144 * at key within the overall structure. */
145 key = key !== undefined ? key : [];
146 var addition_key = arr.length, prior_key, i;
147 for (i = 0; i < stanzas.length; i++) {
148 prior_key = stanzas[i][0];
149 if (stanzas[i].length > 1 &&
150 prior_key.length === key.length + 1 &&
151 prior_key[prior_key.length-1] >= addition_key)
152 { addition_key = prior_key[prior_key.length-1] + 1; }
157 loopOver: function(obj, callback) {
158 /* Helper function for looping over obj. Does the Right Thing
159 * whether obj is an array or not. */
161 if (obj instanceof Array) {
162 for (i = 0; i < obj.length; i++) {
167 if (obj.hasOwnProperty(key)) {
174 inArray: function(keypath) {
175 var terminal = keypath[keypath.length - 1];
176 return (typeof terminal === 'number')
179 inObject: function(keypath) {
180 var terminal = keypath[keypath.length - 1];
181 return (typeof terminal === 'string')
184 splitDiff: function(diff) {
185 /* Split the stanzas in diff into an array of three arrays:
186 * [modifications, deletions, insertions]. */
187 var idx, objs = [], mods = [], dels = [], inss = [];
188 var dests = {3: inss, 1: dels}, stanza, keypath;
189 if (diff.length === 0) {return [[], diff];}
190 for (idx = 0; idx < diff.length; idx++) {
192 if (stanza.length === 2) {
193 if (this.inObject(stanza[0])) {
199 dests[stanza.length].push(stanza)
202 return [objs, mods, dels, inss];
205 stableKeypathLengthSort: function(stanzas) {
206 var comparator = function (a, b) {
208 if (a[0].length === b[0].length) {
209 return a[0][0] - b[0][0];
211 return b[0].length - a[0].length;
213 for (var i = 0; i < stanzas.length; i++) {
214 stanzas[i][0].unshift(i)
216 stanzas.sort(comparator)
217 for (i = 0; i < stanzas.length; i++) {
218 stanzas[i][0].shift()
223 keypathCompare: function(a, b) {
225 if (a.length !== b.length) {
226 return a.length - b.length;
228 for (var i = 0; i < a.length; i++) {
229 if (typeof a[i] === 'number' && a[i] !== b[i]) {
236 keypathCompareReverse: function(a, b) {
238 if (a.length !== b.length) {
239 return b.length - a.length;
241 for (var i = 0; i < a.length; i++) {
242 if (typeof a[i] === 'number' && a[i] !== b[i]) {
249 sortStanzas: function(diff) {
250 /* Sorts the stanzas in a diff: object changes can occur in
251 * any order, but deletions from arrays have to happen last
252 * node first: ['foo', 'bar', 'baz'] -> ['foo', 'bar'] ->
253 * ['foo'] -> []; additions to sequences have to happen
254 * leftmost-node-first: [] -> ['foo'] -> ['foo', 'bar'] ->
255 * ['foo', 'bar', 'baz'], and insert-and-shift alterations to
256 * arrays must happen last. */
258 // First we divide the stanzas using splitDiff():
259 var split_thing = this.splitDiff(diff);
260 // Then we sort modifications of arrays in ascending order of keypath
261 // (note that we can’t tell appends from mods on the info available):
262 split_thing[1].sort(this.keypathCompare);
263 // Deletions from arrays in descending order of keypath:
264 split_thing[2].sort(this.keypathCompareReverse);
265 // And insert-and-shifts in ascending order of keypath:
266 split_thing[3].sort(this.keypathCompare)
267 diff = split_thing[0].concat(
268 split_thing[1], split_thing[2], split_thing[3]
270 // Finally, we sort by length of keypath:
271 diff = this.stableKeypathLengthSort(diff, true)
275 computeKeysets: function(left, right) {
276 /* Returns an array of three arrays (overlap, left_only,
277 * right_only), representing the properties common to left and
278 * right, only defined for left, and only defined for right,
280 var overlap = [], left_only = [], right_only = [];
281 var target = overlap;
283 this.loopOver(left, function(obj, key) {
284 if (right[key] !== undefined) {
292 this.loopOver(right, function(obj, key) {
293 if (left[key] === undefined) {
294 right_only.push(key);
297 return [overlap, left_only, right_only];
300 structureWorthInvestigating: function(left, right) {
301 /* Test whether it is worth looking at the internal structure
302 * of `left` and `right` to see if they can be efficiently
304 if (this.isTerminal(left) || this.isTerminal(right)) {
307 if ((left.length === 0) || (right.length === 0)) {
310 if ((left instanceof Array) && (right instanceof Array)) {
313 if ((left instanceof Array) || (right instanceof Array)) {
316 if ((typeof left === 'object') && (typeof right === 'object')) {
322 commonality: function(left, right) {
323 /* Calculate the amount that the structures left and right
325 var com = 0, tot = 0;
326 var elem, keysets, o, l, r, idx;
327 if (this.isTerminal(left) || this.isTerminal(right)) {
331 if ((left instanceof Array) && (right instanceof Array)) {
332 for (idx = 0; idx < left.length; idx++) {
334 if (right.indexOf(elem) !== -1) {
338 tot = Math.max(left.length, right.length);
341 if ((left instanceof Array) || (right instanceof Array)) {
344 keysets = this.computeKeysets(left, right);
345 o = keysets[0]; l = keysets[1]; r = keysets[2];
347 tot = o.length + l.length + r.length;
348 for (idx = 0; idx < r.length; idx++) {
350 if (l.indexOf(elem) === -1) {
355 if (tot === 0) {return 0;}
359 thisLevelDiff: function(left, right, key, common) {
360 /* Returns a sequence of diff stanzas between the objects left
361 * and right, assuming that they are each at the position key
362 * within the overall structure. */
363 var out = [], idx, okey;
364 key = key !== undefined ? key : [];
366 if (common === undefined) {
367 common = this.commonality(left, right);
371 var ks = this.computeKeysets(left, right);
372 for (idx = 0; idx < ks[0].length; idx++) {
374 if (left[okey] !== right[okey]) {
375 out.push([key.concat([okey]), right[okey]]);
378 for (idx = 0; idx < ks[1].length; idx++) {
380 out.push([key.concat([okey])]);
382 for (idx = 0; idx < ks[2].length; idx++) {
384 out.push([key.concat([okey]), right[okey]]);
388 if (! this.isStrictlyEqual(left, right)) {
389 return [[key, right]];
394 keysetDiff: function(left, right, minimal, key) {
395 /* Compute a diff between left and right, without treating
396 * arrays differently from objects. */
397 minimal = minimal !== undefined ? minimal : true;
399 var ks = this.computeKeysets(left, right);
400 for (k = 0; k < ks[1].length; k++) {
401 out.push([key.concat(ks[1][k])]);
403 for (k = 0; k < ks[2].length; k++) {
404 out.push([key.concat(ks[2][k]), right[ks[2][k]]]);
406 for (k = 0; k < ks[0].length; k++) {
407 out = out.concat(this.diff(left[ks[0][k]], right[ks[0][k]],
408 minimal, key.concat([ks[0][k]])));
413 needleDiff: function(left, right, minimal, key) {
414 /* Compute a diff between left and right. If both are arrays,
415 * a variant of Needleman-Wunsch sequence alignment is used to
416 * make the diff minimal (at a significant cost in both
417 * storage and processing). Otherwise, the parms are passed on
419 if (! (left instanceof Array && right instanceof Array)) {
420 return this.keysetDiff(left, right, minimal, key);
422 minimal = minimal !== undefined ? minimal : true;
423 var down_col = 0, lastrow = [], i, sub_i, left_i, right_i, col_i;
424 var row, first_left_i, left_elem, right_elem;
425 var cand_length, win_length, cand, winner;
427 var modify_cand = function () {
428 if (col_i + 1 < lastrow.length) {
429 return lastrow[col_i+1].concat(
430 JSON_delta.diff(left_elem, right_elem,
431 minimal, key.concat([left_i]))
436 var delete_cand = function () {
437 if (row.length > 0) {
438 return row[0].concat([[key.concat([left_i])]]);
442 var append_cand = function () {
443 if (col_i === down_col) {
444 return lastrow[col_i].concat(
445 [[key.concat([JSON_delta.appendKey(lastrow[col_i], left, key)]),
451 var insert_cand = function () {
452 if (col_i !== down_col) {
453 return lastrow[col_i].concat(
454 [[key.concat([right_i]), right_elem, "i"]]
459 var cand_funcs = [modify_cand, delete_cand, append_cand, insert_cand];
461 for (i = 0; i <= left.length; i++) {
463 for (sub_i = 0; sub_i < i; sub_i++) {
464 lastrow[0].push([key.concat([sub_i])]);
468 for (right_i = 0; right_i < right.length; right_i++) {
469 right_elem = right[right_i];
471 for (left_i = 0; left_i < left.length; left_i++) {
472 left_elem = left[left_i];
473 col_i = left.length - left_i - 1;
474 win_length = Infinity;
475 for (i = 0; i < cand_funcs.length; i++) {
476 cand = cand_funcs[i]();
477 if (cand !== undefined) {
478 cand_length = JSON.stringify(cand).length;
479 if (cand_length < win_length) {
481 win_length = cand_length;
492 patchStanza: function(struc, diff) {
493 /* Applies the diff stanza diff to the structure struc.
494 Returns the modified structure. */
496 switch (key.length) {
501 if (diff.length === 1) {
502 if (struc.splice === undefined) {
503 delete struc[key[0]];
506 struc.splice(key[0], 1);
508 } else if (diff.length === 3) {
509 if (struc.splice === undefined) {
510 struc[key[0]] = diff[1];
512 struc.splice(key[0], 0, diff[1]);
516 struc[key[0]] = diff[1];
520 var pass_key = key.slice(1), pass_struc = struc[key[0]];
521 var pass_diff = [pass_key].concat(diff.slice(1));
522 if (pass_struc === undefined) {
523 if (typeof pass_key[0] === 'string') {
529 struc[key[0]] = this.patchStanza(pass_struc, pass_diff);