1 /* JSON-delta v0.2 - A diff/patch pair for JSON-serialized data structures.
3 Copyright 2013-2014 Philip J. Roberts <himself@phil-roberts.name>.
6 Redistribution and use in source and binary forms, with or without
7 modification, are permitted provided that the following conditions are
10 1. Redistributions of source code must retain the above copyright
11 notice, this list of conditions and the following disclaimer.
13 2. Redistributions in binary form must reproduce the above copyright
14 notice, this list of conditions and the following disclaimer in the
15 documentation and/or other materials provided with the distribution.
17 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
18 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
19 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
20 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
21 HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
22 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
23 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
24 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
25 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
26 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
27 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 This implementation is based heavily on the original python2 version:
30 see http://www.phil-roberts.name/json-delta/ for further
33 isStrictlyEqual: function (left, right) {
34 if (this.isTerminal(left) && this.isTerminal(right)) {
35 return (left === right);
37 if (this.isTerminal(left) || this.isTerminal(right)) {
40 if (left instanceof Array && right instanceof Array) {
41 if (left.length != right.length) {
45 if ( ! this.isStrictlyEqual(left[idx], right[idx])) {
51 if (left instanceof Array || right instanceof Array) {
54 var ks = this.computeKeysets(left, right);
55 if (ks[1].length != 0 || ks[2].length != 0) {
60 if ( ! this.isStrictlyEqual(left[key], right[key])) {
67 isTerminal: function (obj) {
68 if (typeof obj == "string" || typeof obj == "number"
69 || typeof obj == "boolean" || obj == null) {
75 splitDeletions: function (diff) {
76 if (diff.length == 0) {return [[], diff]}
77 diff.sort(function (a,b) {return b.length-a.length});
79 if (diff[idx] > 1) {break}
81 return [diff.slice(0,idx), diff.slice(idx)]
84 sortStanzas: function (diff) {
85 // Sorts the stanzas in a diff: node changes can occur in any
86 // order, but deletions from sequences have to happen last node
87 // first: ['foo', 'bar', 'baz'] -> ['foo', 'bar'] -> ['foo'] ->
88 // [] and additions to sequences have to happen
89 // leftmost-node-first: [] -> ['foo'] -> ['foo', 'bar'] ->
90 // ['foo', 'bar', 'baz'].
93 // First we divide the stanzas using splitDeletions():
94 var split_thing = this.splitDeletions(diff);
95 // Then we sort modifications in ascending order of last key:
96 split_thing[0].sort(function (a,b) {return a[0].slice(-1)[0]-b[0].slice(-1)[0]});
97 // And deletions in descending order of last key:
98 split_thing[1].sort(function (a,b) {return b[0].slice(-1)[0]-a[0].slice(-1)[0]});
100 return split_thing[0].concat(split_thing[1])
103 computeKeysets: function (left, right) {
104 /* Returns an array of three arrays (overlap, left_only,
105 * right_only), representing the properties common to left and
106 * right, only defined for left, and only defined for right,
108 var overlap = [], left_only = [], right_only = [];
109 var target = overlap;
110 var targ_num = (left instanceof Array);
128 if (! (key in left)) {
129 right_only.push(key);
132 return [overlap, left_only, right_only]
135 commonality: function (left, right) {
138 if (this.isTerminal(left) || this.isTerminal(right)) {
142 if ((left instanceof Array) && (right instanceof Array)) {
145 if (right.indexOf(elem) != -1) {
149 tot = Math.max(left.length, right.length);
151 else if ((left instanceof Array) || (right instanceof Array)) {
155 var ks = this.computeKeysets(left, right);
156 o = ks[0]; l = ks[1]; r = ks[2];
158 tot = o.length + l.length + r.length;
161 if (l.indexOf(elem) == -1) {
166 if (tot == 0) {return 0}
170 thisLevelDiff: function (left, right, key, common) {
171 // Returns a sequence of diff stanzas between the objects left and
172 // right, assuming that they are each at the position key within
173 // the overall structure.
175 key = typeof key !== 'undefined' ? key: [];
177 if (typeof common == 'undefined') {
178 common = this.commonality(left, right);
182 var ks = this.computeKeysets(left, right);
185 if (left[okey] != right[okey]) {
186 out.push([key.concat([okey]), right[okey]]);
191 out.push([key.concat([okey])]);
195 out.push([key.concat([okey]), right[okey]]);
199 else if ( ! this.isStrictlyEqual(left,right)) {
200 return [[key, right]]
207 keysetDiff: function (left, right, key) {
209 var ks = this.computeKeysets(left, right);
211 out.push([key.concat(ks[1][k])]);
214 out.push([key.concat(ks[2][k]), right[ks[2][k]]]);
217 out = out.concat(this.diff(left[ks[0][k]], right[ks[0][k]],
218 key.concat([ks[0][k]])))
223 patchStanza: function (struc, diff) {
224 // Applies the diff stanza diff to the structure struc. Returns
225 // the modified structure.
227 switch (key.length) {
232 if (diff.length == 1) {
233 if (typeof struc.splice == 'undefined') {
234 delete struc[key[0]];
237 struc.splice(key[0], 1);
241 struc[key[0]] = diff[1];
245 pass_key = key.slice(1);
246 pass_struc = struc[key[0]];
247 pass_diff = [pass_key].concat(diff.slice(1));
248 struc[key[0]] = this.patchStanza(pass_struc, pass_diff);
253 patch: function (struc, diff) {
254 // Applies the sequence of diff stanzas diff to the structure
255 // struc, and returns the patched structure.
256 for (stan_key in diff) {
257 struc = this.patchStanza(struc, diff[stan_key]);
262 diff: function (left, right, key, minimal) {
263 key = typeof key !== 'undefined' ? key : [];
264 minimal = typeof minimal !== 'undefined' ? minimal: true;
265 var dumbdiff = [[key, right]]
268 common = this.commonality(left, right);
270 my_diff = this.thisLevelDiff(left, right, key, common);
273 my_diff = this.keysetDiff(left, right, key);
277 if (JSON.stringify(dumbdiff).length <
278 JSON.stringify(my_diff).length) {
283 if (key.length == 0) {
284 if (my_diff.length > 1) {
285 my_diff = this.sortStanzas(my_diff);
293 if (typeof exports !== 'undefined') exports.JSON_delta = JSON_delta;