git.sesse.net Git - remoteglot/blob - www/js/json_delta.js

   1 /* JSON-delta v1.1.3 - A diff/patch pair for JSON-serialized data
   2 structures.
   3
   4 Copyright 2013-2015 Philip J. Roberts <himself@phil-roberts.name>.
   5 All rights reserved
   6
   7 Redistribution and use in source and binary forms, with or without
   8 modification, are permitted provided that the following conditions are
   9 met:
  10
  11 1. Redistributions of source code must retain the above copyright
  12 notice, this list of conditions and the following disclaimer.
  13
  14 2. Redistributions in binary form must reproduce the above copyright
  15 notice, this list of conditions and the following disclaimer in the
  16 documentation and/or other materials provided with the distribution.
  17
  18 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
  19 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  20 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  21 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
  22 HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  23 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  24 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  25 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  26 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  27 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29
  30 This implementation is based heavily on the original python2 version:
  31 see http://www.phil-roberts.name/json-delta/ for further
  32 documentation.  */
  33
  34 JSON_delta = {
  35     // Main entry points: ======================================================
  36     patch: function(struc, diff) {
  37         /* Apply the sequence of diff stanzas diff to the structure
  38          struc, and returns the patched structure. */
  39         var stan_key;
  40         for (stan_key = 0; stan_key < diff.length; stan_key++) {
  41             struc = this.patchStanza(struc, diff[stan_key]);
  42         }
  43         return struc;
  44     },
  45
  46     diff: function(left, right, minimal, key) {
  47         /* Build a diff between the structures left and right.
  48
  49          Parameters:
  50              key: this is used for mutual recursion between this
  51                  function and those it calls.  Normally it should be
  52                  left unset or set as its default [].
  53
  54              minimal: if this flag is set true, the function will try
  55                  harder to find the diff that encodes as the shortest
  56                  possible JSON string, at the expense of using more of
  57                  both memory and processor time (as alternatives are
  58                  computed and compared).
  59         */
  60         key = key !== undefined ? key : [];
  61         minimal = minimal !== undefined ? minimal : true;
  62         var dumbdiff = [[key, right]], my_diff = [], common;
  63
  64         if (this.structureWorthInvestigating(left, right)) {
  65             common = this.commonality(left, right);
  66             if (minimal) {
  67                 my_diff = this.needleDiff(left, right, minimal, key);
  68             } else if (common < 0.5) {
  69                 my_diff = this.thisLevelDiff(left, right, key, common);
  70             } else {
  71                 my_diff = this.keysetDiff(left, right, minimal, key);
  72             }
  73         } else {
  74             my_diff = this.thisLevelDiff(left, right, key, 0.0);
  75         }
  76
  77         if (minimal) {
  78             if (JSON.stringify(dumbdiff).length <
  79                 JSON.stringify(my_diff).length) {
  80                 my_diff = dumbdiff;
  81             }
  82         }
  83
  84         if (key.length === 0) {
  85             if (my_diff.length > 1) {
  86                 my_diff = this.sortStanzas(my_diff);
  87             }
  88         }
  89         return my_diff;
  90     },
  91
  92     // =========================================================================
  93
  94     isStrictlyEqual: function(left, right) {
  95         /* Recursively compare the (potentially nested) objects left
  96          * and right */
  97         var idx, ks, key;
  98         if (this.isTerminal(left) && this.isTerminal(right)) {
  99             return (left === right);
 100         }
 101         if (this.isTerminal(left) || this.isTerminal(right)) {
 102             return false;
 103         }
 104         if (left instanceof Array && right instanceof Array) {
 105             if (left.length !== right.length) {
 106                 return false;
 107             }
 108             for (idx = 0; idx < left.length; idx++) {
 109                 if (! this.isStrictlyEqual(left[idx], right[idx])) {
 110                     return false;
 111                 }
 112             }
 113             return true;
 114         }
 115         if (left instanceof Array || right instanceof Array) {
 116             return false;
 117         }
 118         ks = this.computeKeysets(left, right);
 119         if (ks[1].length !== 0 || ks[2].length !== 0) {
 120             return false;
 121         }
 122         for (idx = 0; idx < ks[0].length; idx++) {
 123             key = ks[0][idx];
 124             if (! this.isStrictlyEqual(left[key], right[key])) {
 125                 return false;
 126             }
 127         }
 128         return true;
 129     },
 130
 131     isTerminal: function(obj) {
 132         /* Test whether obj will be a terminal node in the tree when
 133          * serialized as JSON. */
 134         if (typeof obj === 'string' || typeof obj === 'number' ||
 135             typeof obj === 'boolean' || obj === null) {
 136             return true;
 137         }
 138         return false;
 139     },
 140
 141     appendKey: function(stanzas, arr, key) {
 142         /* Get the appropriate key for appending to the array arr,
 143          * assuming that stanzas will also be applied, and arr appears
 144          * at key within the overall structure. */
 145         key = key !== undefined ? key : [];
 146         var addition_key = arr.length, prior_key, i;
 147         for (i = 0; i < stanzas.length; i++) {
 148             prior_key = stanzas[i][0];
 149             if (stanzas[i].length > 1 &&
 150                 prior_key.length === key.length + 1 &&
 151                 prior_key[prior_key.length-1] >= addition_key)
 152             { addition_key = prior_key[prior_key.length-1] + 1; }
 153         }
 154         return addition_key;
 155     },
 156
 157     loopOver: function(obj, callback) {
 158         /* Helper function for looping over obj.  Does the Right Thing
 159          * whether obj is an array or not. */
 160         var i, key;
 161         if (obj instanceof Array) {
 162             for (i = 0; i < obj.length; i++) {
 163                 callback(obj, i);
 164             }
 165         } else {
 166             for (key in obj) {
 167                 if (obj.hasOwnProperty(key)) {
 168                     callback(obj, key);
 169                 }
 170             }
 171         }
 172     },
 173
 174     splitDeletions: function(diff) {
 175         /* Split the stanzas in diff into an array of two arrays:
 176          * [modifications, deletions]. */
 177         var idx;
 178         if (diff.length === 0) {return [[], diff];}
 179         diff.sort(function(a, b) {return b.length - a.length;});
 180         for (idx = 0; idx < diff.length; idx++) {
 181             if (diff[idx].length === 1) {break;}
 182         }
 183         return [diff.slice(0, idx), diff.slice(idx)];
 184     },
 185
 186     sortStanzas: function(diff) {
 187         /* Sorts the stanzas in a diff: node changes can occur in any
 188          * order, but deletions from sequences have to happen last
 189          * node first: ['foo', 'bar', 'baz'] -> ['foo', 'bar'] ->
 190          * ['foo'] -> [] and additions to sequences have to happen
 191          * leftmost-node-first: [] -> ['foo'] -> ['foo', 'bar'] ->
 192          * ['foo', 'bar', 'baz']. */
 193
 194         // First we divide the stanzas using splitDeletions():
 195         var split_thing = this.splitDeletions(diff);
 196         // Then we sort modifications in ascending order of last key:
 197         split_thing[0].sort(
 198             function(a, b) {return a[0].slice(-1)[0] - b[0].slice(-1)[0];}
 199         );
 200         // And deletions in descending order of last key:
 201         split_thing[1].sort(
 202             function(a, b) {return b[0].slice(-1)[0] - a[0].slice(-1)[0];}
 203         );
 204         // And recombine:
 205         return split_thing[0].concat(split_thing[1]);
 206     },
 207
 208     computeKeysets: function(left, right) {
 209         /* Returns an array of three arrays (overlap, left_only,
 210          * right_only), representing the properties common to left and
 211          * right, only defined for left, and only defined for right,
 212          * respectively. */
 213         var overlap = [], left_only = [], right_only = [];
 214         var target = overlap;
 215
 216         this.loopOver(left, function(obj, key) {
 217             if (right[key] !== undefined) {
 218                 target = overlap;
 219             }
 220             else {
 221                 target = left_only;
 222             }
 223             target.push(key);
 224         });
 225         this.loopOver(right, function(obj, key) {
 226             if (left[key] === undefined) {
 227                 right_only.push(key);
 228             }
 229         });
 230         return [overlap, left_only, right_only];
 231     },
 232
 233     structureWorthInvestigating: function(left, right) {
 234         /* Test whether it is worth looking at the internal structure
 235          * of `left` and `right` to see if they can be efficiently
 236          * diffed. */
 237         if (this.isTerminal(left) || this.isTerminal(right)) {
 238             return false;
 239         }
 240         if ((left.length === 0) || (right.length === 0)) {
 241             return false;
 242         }
 243         if ((left instanceof Array) && (right instanceof Array)) {
 244             return true;
 245         }
 246         if ((left instanceof Array) || (right instanceof Array)) {
 247             return false;
 248         }
 249         if ((typeof left === 'object') && (typeof right === 'object')) {
 250             return true;
 251         }
 252         return false;
 253     },
 254
 255     commonality: function(left, right) {
 256         /* Calculate the amount that the structures left and right
 257          * have in common */
 258         var com = 0, tot = 0;
 259         var elem, keysets, o, l, r, idx;
 260         if (this.isTerminal(left) || this.isTerminal(right)) {
 261             return 0;
 262         }
 263
 264         if ((left instanceof Array) && (right instanceof Array)) {
 265             for (idx = 0; idx < left.length; idx++) {
 266                 elem = left[idx];
 267                 if (right.indexOf(elem) !== -1) {
 268                     com++;
 269                 }
 270             }
 271             tot = Math.max(left.length, right.length);
 272         }
 273         else {
 274             if ((left instanceof Array) || (right instanceof Array)) {
 275                 return 0;
 276             }
 277             keysets = this.computeKeysets(left, right);
 278             o = keysets[0]; l = keysets[1]; r = keysets[2];
 279             com = o.length;
 280             tot = o.length + l.length + r.length;
 281             for (idx = 0; idx < r.length; idx++) {
 282                 elem = r[idx];
 283                 if (l.indexOf(elem) === -1) {
 284                     tot++;
 285                 }
 286             }
 287         }
 288         if (tot === 0) {return 0;}
 289         return com / tot;
 290     },
 291
 292     thisLevelDiff: function(left, right, key, common) {
 293         /* Returns a sequence of diff stanzas between the objects left
 294          * and right, assuming that they are each at the position key
 295          * within the overall structure. */
 296         var out = [], idx, okey;
 297         key = key !== undefined ? key : [];
 298
 299         if (common === undefined) {
 300             common = this.commonality(left, right);
 301         }
 302
 303         if (common) {
 304             var ks = this.computeKeysets(left, right);
 305             for (idx = 0; idx < ks[0].length; idx++) {
 306                 okey = ks[0][idx];
 307                 if (left[okey] !== right[okey]) {
 308                     out.push([key.concat([okey]), right[okey]]);
 309                 }
 310             }
 311             for (idx = 0; idx < ks[1].length; idx++) {
 312                 okey = ks[1][idx];
 313                 out.push([key.concat([okey])]);
 314             }
 315             for (idx = 0; idx < ks[2].length; idx++) {
 316                 okey = ks[2][idx];
 317                 out.push([key.concat([okey]), right[okey]]);
 318             }
 319             return out;
 320         }
 321         if (! this.isStrictlyEqual(left, right)) {
 322             return [[key, right]];
 323         }
 324         return [];
 325     },
 326
 327     keysetDiff: function(left, right, minimal, key) {
 328         /* Compute a diff between left and right, without treating
 329          * arrays differently from objects. */
 330         minimal = minimal !== undefined ? minimal : true;
 331         var out = [], k;
 332         var ks = this.computeKeysets(left, right);
 333         for (k = 0; k < ks[1].length; k++) {
 334             out.push([key.concat(ks[1][k])]);
 335         }
 336         for (k = 0; k < ks[2].length; k++) {
 337             out.push([key.concat(ks[2][k]), right[ks[2][k]]]);
 338         }
 339         for (k = 0; k < ks[0].length; k++) {
 340             out = out.concat(this.diff(left[ks[0][k]], right[ks[0][k]],
 341                                        minimal, key.concat([ks[0][k]])));
 342         }
 343         return out;
 344     },
 345
 346     needleDiff: function(left, right, minimal, key) {
 347         /* Compute a diff between left and right.  If both are arrays,
 348          * a variant of Needleman-Wunsch sequence alignment is used to
 349          * make the diff minimal (at a significant cost in both
 350          * storage and processing).  Otherwise, the parms are passed on
 351          * to keysetDiff.*/
 352         if (! (left instanceof Array && right instanceof Array)) {
 353             return this.keysetDiff(left, right, minimal, key);
 354         }
 355         minimal = minimal !== undefined ? minimal : true;
 356         var down_col = 0, lastrow = [], i, sub_i, left_i, right_i, col_i;
 357         var row, first_left_i, left_elem, right_elem;
 358         var cand_length, win_length, cand, winner;
 359
 360         var modify_cand = function () {
 361             if (col_i + 1 < lastrow.length) {
 362                 return lastrow[col_i+1].concat(
 363                     JSON_delta.diff(left_elem, right_elem,
 364                                     minimal, key.concat([left_i]))
 365                 );
 366             }
 367         };
 368
 369         var delete_cand = function () {
 370             if (row.length > 0) {
 371                 return row[0].concat([[key.concat([left_i])]]);
 372             }
 373         };
 374
 375         var append_cand = function () {
 376             if (col_i === down_col) {
 377                 return lastrow[col_i].concat(
 378                     [[key.concat([JSON_delta.appendKey(lastrow[col_i], left, key)]),
 379                       right_elem]]
 380                 );
 381             }
 382         };
 383         var cand_funcs = [modify_cand, delete_cand, append_cand];
 384
 385         for (i = 0; i <= left.length; i++) {
 386             lastrow.unshift([]);
 387             for (sub_i = 0; sub_i < i; sub_i++) {
 388                 lastrow[0].push([key.concat([sub_i])]);
 389             }
 390         }
 391
 392         for (right_i = 0; right_i < right.length; right_i++) {
 393             right_elem = right[right_i];
 394             first_left_i = Math.min(right_i, left.length - 1);
 395             row = [];
 396             for (left_i = first_left_i; left_i < left.length; left_i++) {
 397                 left_elem = left[left_i];
 398                 col_i = left.length - left_i - 1;
 399                 win_length = Infinity;
 400                 for (i = 0; i < cand_funcs.length; i++) {
 401                     cand = cand_funcs[i]();
 402                     if (cand !== undefined) {
 403                         cand_length = JSON.stringify(cand).length;
 404                         if (cand_length < win_length) {
 405                             winner = cand;
 406                             win_length = cand_length;
 407                         }
 408                     }
 409                 }
 410                 row.unshift(winner);
 411             }
 412             lastrow = row;
 413         }
 414         return winner;
 415     },
 416
 417     patchStanza: function(struc, diff) {
 418         /* Applies the diff stanza diff to the structure struc.
 419          Returns the modified structure. */
 420         var key = diff[0];
 421         switch (key.length) {
 422         case 0:
 423             struc = diff[1];
 424             break;
 425         case 1:
 426             if (diff.length === 1) {
 427                 if (struc.splice === undefined) {
 428                     delete struc[key[0]];
 429                 }
 430                 else {
 431                     struc.splice(key[0], 1);
 432                 }
 433             }
 434             else {
 435                 struc[key[0]] = diff[1];
 436             }
 437             break;
 438         default:
 439             var pass_key = key.slice(1), pass_struc = struc[key[0]];
 440             var pass_diff = [pass_key].concat(diff.slice(1));
 441             if (pass_struc === undefined) {
 442                 if (typeof pass_key[0] === 'string') {
 443                     pass_struc = {};
 444                 } else {
 445                     pass_struc = [];
 446                 }
 447             }
 448             struc[key[0]] = this.patchStanza(pass_struc, pass_diff);
 449         }
 450         return struc;
 451     }
 452 };
 453
 454 // node.js
 455 if (typeof exports !== 'undefined') exports.JSON_delta = JSON_delta;