git.sesse.net Git - remoteglot/blob - 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 const 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 (let 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 (let 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 (var idx in diff) {
  79             if (diff[idx].length === 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 (let 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 (let 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         var elem;
 139         if (this.isTerminal(left) || this.isTerminal(right)) {
 140             return 0;
 141         }
 142
 143         if ((left instanceof Array) && (right instanceof Array)) {
 144             for (let idx in left) {
 145                 elem = left[idx];
 146                 if (right.indexOf(elem) != -1) {
 147                     com += 1;
 148                 }
 149             }
 150             tot = Math.max(left.length, right.length);
 151         }
 152         else if ((left instanceof Array) || (right instanceof Array)) {
 153             return 0;
 154         }
 155         else {
 156             var ks = this.computeKeysets(left, right);
 157             let o = ks[0]; let l = ks[1]; let r = ks[2];
 158             com = o.length;
 159             tot = o.length + l.length + r.length;
 160             for (let idx in r) {
 161                 elem = r[idx];
 162                 if (l.indexOf(elem) == -1) {
 163                     tot += 1
 164                 }
 165             }
 166         }
 167         if (tot == 0) {return 0}
 168         return com / tot;
 169     },
 170
 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.
 175         var out = [];
 176         key = typeof key !== 'undefined' ? key: [];
 177
 178         if (typeof common == 'undefined') {
 179             common = this.commonality(left, right);
 180         }
 181
 182         if (common) {
 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]]);
 188                 }
 189             }
 190             for (let idx in ks[1]) {
 191                 let okey = ks[1][idx];
 192                 out.push([key.concat([okey])]);
 193             }
 194             for (let idx in ks[2]) {
 195                 let okey = ks[2][idx];
 196                 out.push([key.concat([okey]), right[okey]]);
 197             }
 198             return out
 199         }
 200         else if ( ! this.isStrictlyEqual(left,right)) {
 201             return [[key, right]]
 202         }
 203         else {
 204             return []
 205         }
 206     },
 207
 208     keysetDiff: function (left, right, key) {
 209         var out = [];
 210         var ks = this.computeKeysets(left, right);
 211         for (let k in ks[1]) {
 212             out.push([key.concat(ks[1][k])]);
 213         }
 214         for (let k in ks[2]) {
 215             out.push([key.concat(ks[2][k]), right[ks[2][k]]]);
 216         }
 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]])))
 220         }
 221         return out;
 222     },
 223
 224     patchStanza: function (struc, diff) {
 225         // Applies the diff stanza diff to the structure struc.  Returns
 226         // the modified structure.
 227         let key = diff[0];
 228         switch (key.length) {
 229         case 0:
 230             struc = diff[1];
 231             break;
 232         case 1:
 233             if (diff.length == 1) {
 234                 if (typeof struc.splice == 'undefined') {
 235                     delete struc[key[0]];
 236                 }
 237                 else {
 238                     struc.splice(key[0], 1);
 239                 }
 240             }
 241             else {
 242                 struc[key[0]] = diff[1];
 243             }
 244             break;
 245         default:
 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);
 250         }
 251         return struc;
 252     },
 253
 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]);
 259         }
 260         return struc
 261     },
 262
 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]]
 267         var my_diff = [];
 268
 269         let common = this.commonality(left, right);
 270         if (common < 0.5) {
 271             my_diff = this.thisLevelDiff(left, right, key, common);
 272         }
 273         else {
 274             my_diff = this.keysetDiff(left, right, key);
 275         }
 276
 277         if (minimal) {
 278             if (JSON.stringify(dumbdiff).length <
 279                 JSON.stringify(my_diff).length) {
 280                 my_diff = dumbdiff
 281             }
 282         }
 283
 284         if (key.length == 0) {
 285             if (my_diff.length > 1) {
 286                 my_diff = this.sortStanzas(my_diff);
 287             }
 288         }
 289         return my_diff;
 290     }
 291 }
 292
 293 // node.js
 294 if (typeof exports !== 'undefined') exports.JSON_delta = JSON_delta;