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 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;