dad457b527204c9e86a196dd7a24346fbf4fb81a
[remoteglot] / www / js / json_delta.js
1 /* JSON-delta v0.2 - A diff/patch pair for JSON-serialized data structures.
2
3 Copyright 2013-2014 Philip J. Roberts <himself@phil-roberts.name>.
4 All rights reserved
5
6 Redistribution and use in source and binary forms, with or without
7 modification, are permitted provided that the following conditions are
8 met:
9
10 1. Redistributions of source code must retain the above copyright
11 notice, this list of conditions and the following disclaimer.
12
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.
16
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.
28
29 This implementation is based heavily on the original python2 version:
30 see http://www.phil-roberts.name/json-delta/ for further
31 documentation.  */
32 JSON_delta = {
33     isStrictlyEqual: function (left, right) {
34         if (this.isTerminal(left) && this.isTerminal(right)) {
35             return (left === right);
36         }
37         if (this.isTerminal(left) || this.isTerminal(right)) {
38             return false;
39         }
40         if (left instanceof Array && right instanceof Array) {
41             if (left.length != right.length) {
42                 return false;
43             }
44             for (idx in left) {
45                 if ( ! this.isStrictlyEqual(left[idx], right[idx])) {
46                     return false;
47                 }
48             }
49             return true;
50         }
51         if (left instanceof Array || right instanceof Array) {
52             return false;
53         }
54         var ks = this.computeKeysets(left, right);
55         if (ks[1].length != 0 || ks[2].length != 0) {
56             return false;
57         }
58         for (key in ks[0]) {
59             key = ks[0][key];
60             if ( ! this.isStrictlyEqual(left[key], right[key])) {
61                 return false
62             }
63         }
64         return true;
65     },
66
67     isTerminal: function (obj) {
68         if (typeof obj == "string" || typeof obj == "number"
69             || typeof obj == "boolean" || obj == null) {
70             return true;
71         }
72         return false;
73     },
74
75     splitDeletions: function (diff) {
76         if (diff.length == 0) {return [[], diff]}
77         diff.sort(function (a,b) {return b.length-a.length});
78         for (idx in diff) {
79             if (diff[idx] > 1) {break}
80         }
81         return [diff.slice(0,idx), diff.slice(idx)]
82     },
83
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'].
91
92
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]});
99         // And recombine:
100         return split_thing[0].concat(split_thing[1])
101     },
102
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,
107          * respectively. */
108         var overlap = [], left_only = [], right_only = [];
109         var target = overlap;
110         var targ_num = (left instanceof Array);
111
112         for (key in left) {
113             if (targ_num) {
114                 key = Number(key)
115             }
116             if (key in right) {
117                 target = overlap;
118             }
119             else {
120                 target = left_only;
121             }
122             target.push(key);
123         }
124         for (key in right) {
125             if (targ_num) {
126                 key = Number(key)
127             }
128             if (! (key in left)) {
129                 right_only.push(key);
130             }
131         }
132         return [overlap, left_only, right_only]
133     },
134
135     commonality: function (left, right) {
136         var com = 0;
137         var tot = 0;
138         if (this.isTerminal(left) || this.isTerminal(right)) {
139             return 0;
140         }
141
142         if ((left instanceof Array) && (right instanceof Array)) {
143             for (idx in left) {
144                 elem = left[idx];
145                 if (right.indexOf(elem) != -1) {
146                     com += 1;
147                 }
148             }
149             tot = Math.max(left.length, right.length);
150         }
151         else if ((left instanceof Array) || (right instanceof Array)) {
152             return 0;
153         }
154         else {
155             var ks = this.computeKeysets(left, right);
156             o = ks[0]; l = ks[1]; r = ks[2];
157             com = o.length;
158             tot = o.length + l.length + r.length;
159             for (idx in r) {
160                 elem = r[idx];
161                 if (l.indexOf(elem) == -1) {
162                     tot += 1
163                 }
164             }
165         }
166         if (tot == 0) {return 0}
167         return com / tot;
168     },
169
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.
174         var out = [];
175         key = typeof key !== 'undefined' ? key: [];
176
177         if (typeof common == 'undefined') {
178             common = this.commonality(left, right);
179         }
180
181         if (common) {
182             var ks = this.computeKeysets(left, right);
183             for (idx in ks[0]) {
184                 okey = ks[0][idx];
185                 if (left[okey] != right[okey]) {
186                     out.push([key.concat([okey]), right[okey]]);
187                 }
188             }
189             for (idx in ks[1]) {
190                 okey = ks[1][idx];
191                 out.push([key.concat([okey])]);
192             }
193             for (idx in ks[2]) {
194                 okey = ks[2][idx];
195                 out.push([key.concat([okey]), right[okey]]);
196             }
197             return out
198         }
199         else if ( ! this.isStrictlyEqual(left,right)) {
200             return [[key, right]]
201         }
202         else {
203             return []
204         }
205     },
206
207     keysetDiff: function (left, right, key) {
208         var out = [];
209         var ks = this.computeKeysets(left, right);
210         for (k in ks[1]) {
211             out.push([key.concat(ks[1][k])]);
212         }
213         for (k in ks[2]) {
214             out.push([key.concat(ks[2][k]), right[ks[2][k]]]);
215         }
216         for (k in ks[0]) {
217             out = out.concat(this.diff(left[ks[0][k]], right[ks[0][k]],
218                                        key.concat([ks[0][k]])))
219         }
220         return out;
221     },
222
223     patchStanza: function (struc, diff) {
224         // Applies the diff stanza diff to the structure struc.  Returns
225         // the modified structure.
226         key = diff[0];
227         switch (key.length) {
228         case 0:
229             struc = diff[1];
230             break;
231         case 1:
232             if (diff.length == 1) {
233                 if (typeof struc.splice == 'undefined') {
234                     delete struc[key[0]];
235                 }
236                 else {
237                     struc.splice(key[0], 1);
238                 }
239             }
240             else {
241                 struc[key[0]] = diff[1];
242             }
243             break;
244         default:
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);
249         }
250         return struc;
251     },
252
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]);
258         }
259         return struc
260     },
261
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]]
266         var my_diff = [];
267
268         common = this.commonality(left, right);
269         if (common < 0.5) {
270             my_diff = this.thisLevelDiff(left, right, key, common);
271         }
272         else {
273             my_diff = this.keysetDiff(left, right, key);
274         }
275
276         if (minimal) {
277             if (JSON.stringify(dumbdiff).length <
278                 JSON.stringify(my_diff).length) {
279                 my_diff = dumbdiff
280             }
281         }
282
283         if (key.length == 0) {
284             if (my_diff.length > 1) {
285                 my_diff = this.sortStanzas(my_diff);
286             }
287         }
288         return my_diff;
289     }
290 }
291
292 // node.js
293 if (typeof exports !== 'undefined') exports.JSON_delta = JSON_delta;