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) {
44 for (let idx in left) {
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) {
58 for (let key in ks[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});
78 for (var idx in diff) {
79 if (diff[idx].length === 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);
112 for (let key in left) {
124 for (let key in right) {
128 if (! (key in left)) {
129 right_only.push(key);
132 return [overlap, left_only, right_only]
135 commonality: function (left, right) {
139 if (this.isTerminal(left) || this.isTerminal(right)) {
143 if ((left instanceof Array) && (right instanceof Array)) {
144 for (let idx in left) {
146 if (right.indexOf(elem) != -1) {
150 tot = Math.max(left.length, right.length);
152 else if ((left instanceof Array) || (right instanceof Array)) {
156 var ks = this.computeKeysets(left, right);
157 let o = ks[0]; let l = ks[1]; let r = ks[2];
159 tot = o.length + l.length + r.length;
162 if (l.indexOf(elem) == -1) {
167 if (tot == 0) {return 0}
171 thisLevelDiff: function (left, right, key, common) {
172 // Returns a sequence of diff stanzas between the objects left and
173 // right, assuming that they are each at the position key within
174 // the overall structure.
176 key = typeof key !== 'undefined' ? key: [];
178 if (typeof common == 'undefined') {
179 common = this.commonality(left, right);
183 var ks = this.computeKeysets(left, right);
184 for (let idx in ks[0]) {
185 let okey = ks[0][idx];
186 if (left[okey] != right[okey]) {
187 out.push([key.concat([okey]), right[okey]]);
190 for (let idx in ks[1]) {
191 let okey = ks[1][idx];
192 out.push([key.concat([okey])]);
194 for (let idx in ks[2]) {
195 let okey = ks[2][idx];
196 out.push([key.concat([okey]), right[okey]]);
200 else if ( ! this.isStrictlyEqual(left,right)) {
201 return [[key, right]]
208 keysetDiff: function (left, right, key) {
210 var ks = this.computeKeysets(left, right);
211 for (let k in ks[1]) {
212 out.push([key.concat(ks[1][k])]);
214 for (let k in ks[2]) {
215 out.push([key.concat(ks[2][k]), right[ks[2][k]]]);
217 for (let k in ks[0]) {
218 out = out.concat(this.diff(left[ks[0][k]], right[ks[0][k]],
219 key.concat([ks[0][k]])))
224 patchStanza: function (struc, diff) {
225 // Applies the diff stanza diff to the structure struc. Returns
226 // the modified structure.
228 switch (key.length) {
233 if (diff.length == 1) {
234 if (typeof struc.splice == 'undefined') {
235 delete struc[key[0]];
238 struc.splice(key[0], 1);
242 struc[key[0]] = diff[1];
246 let pass_key = key.slice(1);
247 let pass_struc = struc[key[0]];
248 let pass_diff = [pass_key].concat(diff.slice(1));
249 struc[key[0]] = this.patchStanza(pass_struc, pass_diff);
254 patch: function (struc, diff) {
255 // Applies the sequence of diff stanzas diff to the structure
256 // struc, and returns the patched structure.
257 for (let stan_key in diff) {
258 struc = this.patchStanza(struc, diff[stan_key]);
263 diff: function (left, right, key, minimal) {
264 key = typeof key !== 'undefined' ? key : [];
265 minimal = typeof minimal !== 'undefined' ? minimal: true;
266 var dumbdiff = [[key, right]]
269 let common = this.commonality(left, right);
271 my_diff = this.thisLevelDiff(left, right, key, common);
274 my_diff = this.keysetDiff(left, right, key);
278 if (JSON.stringify(dumbdiff).length <
279 JSON.stringify(my_diff).length) {
284 if (key.length == 0) {
285 if (my_diff.length > 1) {
286 my_diff = this.sortStanzas(my_diff);
294 if (typeof exports !== 'undefined') exports.JSON_delta = JSON_delta;