1 /* JSON-delta v1.1.3 - 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 splitDeletions: function(diff) {
175 /* Split the stanzas in diff into an array of two arrays:
176 * [modifications, deletions]. */
178 if (diff.length === 0) {return [[], diff];}
179 diff.sort(function(a, b) {return b.length - a.length;});
180 for (idx = 0; idx < diff.length; idx++) {
181 if (diff[idx].length === 1) {break;}
183 return [diff.slice(0, idx), diff.slice(idx)];
186 sortStanzas: function(diff) {
187 /* Sorts the stanzas in a diff: node changes can occur in any
188 * order, but deletions from sequences have to happen last
189 * node first: ['foo', 'bar', 'baz'] -> ['foo', 'bar'] ->
190 * ['foo'] -> [] and additions to sequences have to happen
191 * leftmost-node-first: [] -> ['foo'] -> ['foo', 'bar'] ->
192 * ['foo', 'bar', 'baz']. */
194 // First we divide the stanzas using splitDeletions():
195 var split_thing = this.splitDeletions(diff);
196 // Then we sort modifications in ascending order of last key:
198 function(a, b) {return a[0].slice(-1)[0] - b[0].slice(-1)[0];}
200 // And deletions in descending order of last key:
202 function(a, b) {return b[0].slice(-1)[0] - a[0].slice(-1)[0];}
205 return split_thing[0].concat(split_thing[1]);
208 computeKeysets: function(left, right) {
209 /* Returns an array of three arrays (overlap, left_only,
210 * right_only), representing the properties common to left and
211 * right, only defined for left, and only defined for right,
213 var overlap = [], left_only = [], right_only = [];
214 var target = overlap;
216 this.loopOver(left, function(obj, key) {
217 if (right[key] !== undefined) {
225 this.loopOver(right, function(obj, key) {
226 if (left[key] === undefined) {
227 right_only.push(key);
230 return [overlap, left_only, right_only];
233 structureWorthInvestigating: function(left, right) {
234 /* Test whether it is worth looking at the internal structure
235 * of `left` and `right` to see if they can be efficiently
237 if (this.isTerminal(left) || this.isTerminal(right)) {
240 if ((left.length === 0) || (right.length === 0)) {
243 if ((left instanceof Array) && (right instanceof Array)) {
246 if ((left instanceof Array) || (right instanceof Array)) {
249 if ((typeof left === 'object') && (typeof right === 'object')) {
255 commonality: function(left, right) {
256 /* Calculate the amount that the structures left and right
258 var com = 0, tot = 0;
259 var elem, keysets, o, l, r, idx;
260 if (this.isTerminal(left) || this.isTerminal(right)) {
264 if ((left instanceof Array) && (right instanceof Array)) {
265 for (idx = 0; idx < left.length; idx++) {
267 if (right.indexOf(elem) !== -1) {
271 tot = Math.max(left.length, right.length);
274 if ((left instanceof Array) || (right instanceof Array)) {
277 keysets = this.computeKeysets(left, right);
278 o = keysets[0]; l = keysets[1]; r = keysets[2];
280 tot = o.length + l.length + r.length;
281 for (idx = 0; idx < r.length; idx++) {
283 if (l.indexOf(elem) === -1) {
288 if (tot === 0) {return 0;}
292 thisLevelDiff: function(left, right, key, common) {
293 /* Returns a sequence of diff stanzas between the objects left
294 * and right, assuming that they are each at the position key
295 * within the overall structure. */
296 var out = [], idx, okey;
297 key = key !== undefined ? key : [];
299 if (common === undefined) {
300 common = this.commonality(left, right);
304 var ks = this.computeKeysets(left, right);
305 for (idx = 0; idx < ks[0].length; idx++) {
307 if (left[okey] !== right[okey]) {
308 out.push([key.concat([okey]), right[okey]]);
311 for (idx = 0; idx < ks[1].length; idx++) {
313 out.push([key.concat([okey])]);
315 for (idx = 0; idx < ks[2].length; idx++) {
317 out.push([key.concat([okey]), right[okey]]);
321 if (! this.isStrictlyEqual(left, right)) {
322 return [[key, right]];
327 keysetDiff: function(left, right, minimal, key) {
328 /* Compute a diff between left and right, without treating
329 * arrays differently from objects. */
330 minimal = minimal !== undefined ? minimal : true;
332 var ks = this.computeKeysets(left, right);
333 for (k = 0; k < ks[1].length; k++) {
334 out.push([key.concat(ks[1][k])]);
336 for (k = 0; k < ks[2].length; k++) {
337 out.push([key.concat(ks[2][k]), right[ks[2][k]]]);
339 for (k = 0; k < ks[0].length; k++) {
340 out = out.concat(this.diff(left[ks[0][k]], right[ks[0][k]],
341 minimal, key.concat([ks[0][k]])));
346 needleDiff: function(left, right, minimal, key) {
347 /* Compute a diff between left and right. If both are arrays,
348 * a variant of Needleman-Wunsch sequence alignment is used to
349 * make the diff minimal (at a significant cost in both
350 * storage and processing). Otherwise, the parms are passed on
352 if (! (left instanceof Array && right instanceof Array)) {
353 return this.keysetDiff(left, right, minimal, key);
355 minimal = minimal !== undefined ? minimal : true;
356 var down_col = 0, lastrow = [], i, sub_i, left_i, right_i, col_i;
357 var row, first_left_i, left_elem, right_elem;
358 var cand_length, win_length, cand, winner;
360 var modify_cand = function () {
361 if (col_i + 1 < lastrow.length) {
362 return lastrow[col_i+1].concat(
363 JSON_delta.diff(left_elem, right_elem,
364 minimal, key.concat([left_i]))
369 var delete_cand = function () {
370 if (row.length > 0) {
371 return row[0].concat([[key.concat([left_i])]]);
375 var append_cand = function () {
376 if (col_i === down_col) {
377 return lastrow[col_i].concat(
378 [[key.concat([JSON_delta.appendKey(lastrow[col_i], left, key)]),
383 var cand_funcs = [modify_cand, delete_cand, append_cand];
385 for (i = 0; i <= left.length; i++) {
387 for (sub_i = 0; sub_i < i; sub_i++) {
388 lastrow[0].push([key.concat([sub_i])]);
392 for (right_i = 0; right_i < right.length; right_i++) {
393 right_elem = right[right_i];
394 first_left_i = Math.min(right_i, left.length - 1);
396 for (left_i = first_left_i; left_i < left.length; left_i++) {
397 left_elem = left[left_i];
398 col_i = left.length - left_i - 1;
399 win_length = Infinity;
400 for (i = 0; i < cand_funcs.length; i++) {
401 cand = cand_funcs[i]();
402 if (cand !== undefined) {
403 cand_length = JSON.stringify(cand).length;
404 if (cand_length < win_length) {
406 win_length = cand_length;
417 patchStanza: function(struc, diff) {
418 /* Applies the diff stanza diff to the structure struc.
419 Returns the modified structure. */
421 switch (key.length) {
426 if (diff.length === 1) {
427 if (struc.splice === undefined) {
428 delete struc[key[0]];
431 struc.splice(key[0], 1);
435 struc[key[0]] = diff[1];
439 var pass_key = key.slice(1), pass_struc = struc[key[0]];
440 var pass_diff = [pass_key].concat(diff.slice(1));
441 if (pass_struc === undefined) {
442 if (typeof pass_key[0] === 'string') {
448 struc[key[0]] = this.patchStanza(pass_struc, pass_diff);
455 if (typeof exports !== 'undefined') exports.JSON_delta = JSON_delta;