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

   1 /* JSON-delta v2.0 - 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     inArray: function(keypath) {
 175         var terminal = keypath[keypath.length - 1];
 176         return (typeof terminal === 'number')
 177     },
 178
 179     inObject: function(keypath) {
 180         var terminal = keypath[keypath.length - 1];
 181         return (typeof terminal === 'string')
 182     },
 183
 184     splitDiff: function(diff) {
 185         /* Split the stanzas in diff into an array of three arrays:
 186          * [modifications, deletions, insertions]. */
 187         var idx, objs = [], mods = [], dels = [], inss = [];
 188         var dests = {3: inss, 1: dels}, stanza, keypath;
 189         if (diff.length === 0) {return [[], diff];}
 190         for (idx = 0; idx < diff.length; idx++) {
 191             stanza = diff[idx]
 192             if (stanza.length === 2) {
 193                 if (this.inObject(stanza[0])) {
 194                     objs.push(stanza);
 195                 } else {
 196                     mods.push(stanza);
 197                 }
 198             } else {
 199                 dests[stanza.length].push(stanza)
 200             }
 201         }
 202         return [objs, mods, dels, inss];
 203     },
 204
 205     stableKeypathLengthSort: function(stanzas) {
 206         var comparator = function (a, b) {
 207             var swap;
 208             if (a[0].length === b[0].length) {
 209                 return a[0][0] - b[0][0];
 210             }
 211             return b[0].length - a[0].length;
 212         }
 213         for (var i = 0; i < stanzas.length; i++) {
 214             stanzas[i][0].unshift(i)
 215         }
 216         stanzas.sort(comparator)
 217         for (i = 0; i < stanzas.length; i++) {
 218             stanzas[i][0].shift()
 219         }
 220         return stanzas
 221     },
 222
 223     keypathCompare: function(a, b) {
 224         a = a[0]; b = b[0];
 225         if (a.length !== b.length) {
 226             return a.length - b.length;
 227         }
 228         for (var i = 0; i < a.length; i++) {
 229             if (typeof a[i] === 'number' && a[i] !== b[i]) {
 230                 return a[i] - b[i];
 231             }
 232         }
 233         return 0;
 234     },
 235
 236     keypathCompareReverse: function(a, b) {
 237         a = a[0]; b = b[0];
 238         if (a.length !== b.length) {
 239             return b.length - a.length;
 240         }
 241         for (var i = 0; i < a.length; i++) {
 242             if (typeof a[i] === 'number' && a[i] !== b[i]) {
 243                 return b[i] - a[i];
 244             }
 245         }
 246         return 0;
 247     },
 248
 249     sortStanzas: function(diff) {
 250         /* Sorts the stanzas in a diff: object changes can occur in
 251          * any order, but deletions from arrays have to happen last
 252          * node first: ['foo', 'bar', 'baz'] -> ['foo', 'bar'] ->
 253          * ['foo'] -> []; additions to sequences have to happen
 254          * leftmost-node-first: [] -> ['foo'] -> ['foo', 'bar'] ->
 255          * ['foo', 'bar', 'baz'], and insert-and-shift alterations to
 256          * arrays must happen last. */
 257
 258         // First we divide the stanzas using splitDiff():
 259         var split_thing = this.splitDiff(diff);
 260         // Then we sort modifications of arrays in ascending order of keypath
 261         // (note that we can’t tell appends from mods on the info available):
 262         split_thing[1].sort(this.keypathCompare);
 263         // Deletions from arrays in descending order of keypath:
 264         split_thing[2].sort(this.keypathCompareReverse);
 265         // And insert-and-shifts in ascending order of keypath:
 266         split_thing[3].sort(this.keypathCompare)
 267         diff = split_thing[0].concat(
 268             split_thing[1], split_thing[2], split_thing[3]
 269         );
 270         // Finally, we sort by length of keypath:
 271         diff = this.stableKeypathLengthSort(diff, true)
 272         return diff
 273     },
 274
 275     computeKeysets: function(left, right) {
 276         /* Returns an array of three arrays (overlap, left_only,
 277          * right_only), representing the properties common to left and
 278          * right, only defined for left, and only defined for right,
 279          * respectively. */
 280         var overlap = [], left_only = [], right_only = [];
 281         var target = overlap;
 282
 283         this.loopOver(left, function(obj, key) {
 284             if (right[key] !== undefined) {
 285                 target = overlap;
 286             }
 287             else {
 288                 target = left_only;
 289             }
 290             target.push(key);
 291         });
 292         this.loopOver(right, function(obj, key) {
 293             if (left[key] === undefined) {
 294                 right_only.push(key);
 295             }
 296         });
 297         return [overlap, left_only, right_only];
 298     },
 299
 300     structureWorthInvestigating: function(left, right) {
 301         /* Test whether it is worth looking at the internal structure
 302          * of `left` and `right` to see if they can be efficiently
 303          * diffed. */
 304         if (this.isTerminal(left) || this.isTerminal(right)) {
 305             return false;
 306         }
 307         if ((left.length === 0) || (right.length === 0)) {
 308             return false;
 309         }
 310         if ((left instanceof Array) && (right instanceof Array)) {
 311             return true;
 312         }
 313         if ((left instanceof Array) || (right instanceof Array)) {
 314             return false;
 315         }
 316         if ((typeof left === 'object') && (typeof right === 'object')) {
 317             return true;
 318         }
 319         return false;
 320     },
 321
 322     commonality: function(left, right) {
 323         /* Calculate the amount that the structures left and right
 324          * have in common */
 325         var com = 0, tot = 0;
 326         var elem, keysets, o, l, r, idx;
 327         if (this.isTerminal(left) || this.isTerminal(right)) {
 328             return 0;
 329         }
 330
 331         if ((left instanceof Array) && (right instanceof Array)) {
 332             for (idx = 0; idx < left.length; idx++) {
 333                 elem = left[idx];
 334                 if (right.indexOf(elem) !== -1) {
 335                     com++;
 336                 }
 337             }
 338             tot = Math.max(left.length, right.length);
 339         }
 340         else {
 341             if ((left instanceof Array) || (right instanceof Array)) {
 342                 return 0;
 343             }
 344             keysets = this.computeKeysets(left, right);
 345             o = keysets[0]; l = keysets[1]; r = keysets[2];
 346             com = o.length;
 347             tot = o.length + l.length + r.length;
 348             for (idx = 0; idx < r.length; idx++) {
 349                 elem = r[idx];
 350                 if (l.indexOf(elem) === -1) {
 351                     tot++;
 352                 }
 353             }
 354         }
 355         if (tot === 0) {return 0;}
 356         return com / tot;
 357     },
 358
 359     thisLevelDiff: function(left, right, key, common) {
 360         /* Returns a sequence of diff stanzas between the objects left
 361          * and right, assuming that they are each at the position key
 362          * within the overall structure. */
 363         var out = [], idx, okey;
 364         key = key !== undefined ? key : [];
 365
 366         if (common === undefined) {
 367             common = this.commonality(left, right);
 368         }
 369
 370         if (common) {
 371             var ks = this.computeKeysets(left, right);
 372             for (idx = 0; idx < ks[0].length; idx++) {
 373                 okey = ks[0][idx];
 374                 if (left[okey] !== right[okey]) {
 375                     out.push([key.concat([okey]), right[okey]]);
 376                 }
 377             }
 378             for (idx = 0; idx < ks[1].length; idx++) {
 379                 okey = ks[1][idx];
 380                 out.push([key.concat([okey])]);
 381             }
 382             for (idx = 0; idx < ks[2].length; idx++) {
 383                 okey = ks[2][idx];
 384                 out.push([key.concat([okey]), right[okey]]);
 385             }
 386             return out;
 387         }
 388         if (! this.isStrictlyEqual(left, right)) {
 389             return [[key, right]];
 390         }
 391         return [];
 392     },
 393
 394     keysetDiff: function(left, right, minimal, key) {
 395         /* Compute a diff between left and right, without treating
 396          * arrays differently from objects. */
 397         minimal = minimal !== undefined ? minimal : true;
 398         var out = [], k;
 399         var ks = this.computeKeysets(left, right);
 400         for (k = 0; k < ks[1].length; k++) {
 401             out.push([key.concat(ks[1][k])]);
 402         }
 403         for (k = 0; k < ks[2].length; k++) {
 404             out.push([key.concat(ks[2][k]), right[ks[2][k]]]);
 405         }
 406         for (k = 0; k < ks[0].length; k++) {
 407             out = out.concat(this.diff(left[ks[0][k]], right[ks[0][k]],
 408                                        minimal, key.concat([ks[0][k]])));
 409         }
 410         return out;
 411     },
 412
 413     needleDiff: function(left, right, minimal, key) {
 414         /* Compute a diff between left and right.  If both are arrays,
 415          * a variant of Needleman-Wunsch sequence alignment is used to
 416          * make the diff minimal (at a significant cost in both
 417          * storage and processing).  Otherwise, the parms are passed on
 418          * to keysetDiff.*/
 419         if (! (left instanceof Array && right instanceof Array)) {
 420             return this.keysetDiff(left, right, minimal, key);
 421         }
 422         minimal = minimal !== undefined ? minimal : true;
 423         var down_col = 0, lastrow = [], i, sub_i, left_i, right_i, col_i;
 424         var row, first_left_i, left_elem, right_elem;
 425         var cand_length, win_length, cand, winner;
 426
 427         var modify_cand = function () {
 428             if (col_i + 1 < lastrow.length) {
 429                 return lastrow[col_i+1].concat(
 430                     JSON_delta.diff(left_elem, right_elem,
 431                                     minimal, key.concat([left_i]))
 432                 );
 433             }
 434         };
 435
 436         var delete_cand = function () {
 437             if (row.length > 0) {
 438                 return row[0].concat([[key.concat([left_i])]]);
 439             }
 440         };
 441
 442         var append_cand = function () {
 443             if (col_i === down_col) {
 444                 return lastrow[col_i].concat(
 445                     [[key.concat([JSON_delta.appendKey(lastrow[col_i], left, key)]),
 446                       right_elem]]
 447                 );
 448             }
 449         };
 450
 451         var insert_cand = function () {
 452             if (col_i !== down_col) {
 453                 return lastrow[col_i].concat(
 454                     [[key.concat([right_i]), right_elem, "i"]]
 455                 );
 456             }
 457         };
 458
 459         var cand_funcs = [modify_cand, delete_cand, append_cand, insert_cand];
 460
 461         for (i = 0; i <= left.length; i++) {
 462             lastrow.unshift([]);
 463             for (sub_i = 0; sub_i < i; sub_i++) {
 464                 lastrow[0].push([key.concat([sub_i])]);
 465             }
 466         }
 467
 468         for (right_i = 0; right_i < right.length; right_i++) {
 469             right_elem = right[right_i];
 470             row = []
 471             for (left_i = 0; left_i < left.length; left_i++) {
 472                 left_elem = left[left_i];
 473                 col_i = left.length - left_i - 1;
 474                 win_length = Infinity;
 475                 for (i = 0; i < cand_funcs.length; i++) {
 476                     cand = cand_funcs[i]();
 477                     if (cand !== undefined) {
 478                         cand_length = JSON.stringify(cand).length;
 479                         if (cand_length < win_length) {
 480                             winner = cand;
 481                             win_length = cand_length;
 482                         }
 483                     }
 484                 }
 485                 row.unshift(winner);
 486             }
 487             lastrow = row;
 488         }
 489         return winner;
 490     },
 491
 492     patchStanza: function(struc, diff) {
 493         /* Applies the diff stanza diff to the structure struc.
 494          Returns the modified structure. */
 495         var key = diff[0];
 496         switch (key.length) {
 497         case 0:
 498             struc = diff[1];
 499             break;
 500         case 1:
 501             if (diff.length === 1) {
 502                 if (struc.splice === undefined) {
 503                     delete struc[key[0]];
 504                 }
 505                 else {
 506                     struc.splice(key[0], 1);
 507                 }
 508             } else if (diff.length === 3) {
 509                 if (struc.splice === undefined) {
 510                     struc[key[0]] = diff[1];
 511                 } else {
 512                     struc.splice(key[0], 0, diff[1]);
 513                 }
 514             }
 515             else {
 516                 struc[key[0]] = diff[1];
 517             }
 518             break;
 519         default:
 520             var pass_key = key.slice(1), pass_struc = struc[key[0]];
 521             var pass_diff = [pass_key].concat(diff.slice(1));
 522             if (pass_struc === undefined) {
 523                 if (typeof pass_key[0] === 'string') {
 524                     pass_struc = {};
 525                 } else {
 526                     pass_struc = [];
 527                 }
 528             }
 529             struc[key[0]] = this.patchStanza(pass_struc, pass_diff);
 530         }
 531         return struc;
 532     }
 533 };