Upgrade JSON-delta to v2.0, to hopefully fix some diffing bugs.
authorSteinar H. Gunderson <sgunderson@bigfoot.com>
Thu, 24 Nov 2016 08:42:05 +0000 (09:42 +0100)
committerSteinar H. Gunderson <sgunderson@bigfoot.com>
Thu, 24 Nov 2016 08:42:05 +0000 (09:42 +0100)
www/js/json_delta.js

index dad457b..f379ac5 100644 (file)
@@ -1,6 +1,7 @@
-/* JSON-delta v0.2 - A diff/patch pair for JSON-serialized data structures.
+/* JSON-delta v2.0 - A diff/patch pair for JSON-serialized data
+structures.
 
-Copyright 2013-2014 Philip J. Roberts <himself@phil-roberts.name>.
+Copyright 2013-2015 Philip J. Roberts <himself@phil-roberts.name>.
 All rights reserved
 
 Redistribution and use in source and binary forms, with or without
@@ -29,265 +30,504 @@ OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 This implementation is based heavily on the original python2 version:
 see http://www.phil-roberts.name/json-delta/ for further
 documentation.  */
+
 JSON_delta = {
-    isStrictlyEqual: function (left, right) {
-       if (this.isTerminal(left) && this.isTerminal(right)) {
-           return (left === right);
+    // Main entry points: ======================================================
+    patch: function(struc, diff) {
+        /* Apply the sequence of diff stanzas diff to the structure
+         struc, and returns the patched structure. */
+       var stan_key;
+        for (stan_key = 0; stan_key < diff.length; stan_key++) {
+            struc = this.patchStanza(struc, diff[stan_key]);
+        }
+        return struc;
+    },
+
+    diff: function(left, right, minimal, key) {
+       /* Build a diff between the structures left and right.
+
+        Parameters:
+            key: this is used for mutual recursion between this
+                function and those it calls.  Normally it should be
+                left unset or set as its default [].
+
+            minimal: if this flag is set true, the function will try
+                 harder to find the diff that encodes as the shortest
+                 possible JSON string, at the expense of using more of
+                 both memory and processor time (as alternatives are
+                 computed and compared).
+       */
+        key = key !== undefined ? key : [];
+        minimal = minimal !== undefined ? minimal : true;
+        var dumbdiff = [[key, right]], my_diff = [], common;
+
+       if (this.structureWorthInvestigating(left, right)) {
+           common = this.commonality(left, right);
+            if (minimal) {
+               my_diff = this.needleDiff(left, right, minimal, key);
+            } else if (common < 0.5) {
+               my_diff = this.thisLevelDiff(left, right, key, common);
+            } else {
+               my_diff = this.keysetDiff(left, right, minimal, key);
+            }
+       } else {
+           my_diff = this.thisLevelDiff(left, right, key, 0.0);
        }
-       if (this.isTerminal(left) || this.isTerminal(right)) {
-           return false;
+
+        if (minimal) {
+            if (JSON.stringify(dumbdiff).length <
+                JSON.stringify(my_diff).length) {
+                my_diff = dumbdiff;
+            }
+        }
+
+        if (key.length === 0) {
+            if (my_diff.length > 1) {
+                my_diff = this.sortStanzas(my_diff);
+            }
+        }
+        return my_diff;
+    },
+
+    // =========================================================================
+
+    isStrictlyEqual: function(left, right) {
+       /* Recursively compare the (potentially nested) objects left
+        * and right */
+       var idx, ks, key;
+        if (this.isTerminal(left) && this.isTerminal(right)) {
+            return (left === right);
+        }
+        if (this.isTerminal(left) || this.isTerminal(right)) {
+            return false;
+        }
+        if (left instanceof Array && right instanceof Array) {
+            if (left.length !== right.length) {
+                return false;
+            }
+            for (idx = 0; idx < left.length; idx++) {
+                if (! this.isStrictlyEqual(left[idx], right[idx])) {
+                    return false;
+                }
+            }
+            return true;
+        }
+        if (left instanceof Array || right instanceof Array) {
+            return false;
+        }
+        ks = this.computeKeysets(left, right);
+        if (ks[1].length !== 0 || ks[2].length !== 0) {
+            return false;
+        }
+        for (idx = 0; idx < ks[0].length; idx++) {
+            key = ks[0][idx];
+            if (! this.isStrictlyEqual(left[key], right[key])) {
+                return false;
+            }
+        }
+        return true;
+    },
+
+    isTerminal: function(obj) {
+       /* Test whether obj will be a terminal node in the tree when
+        * serialized as JSON. */
+        if (typeof obj === 'string' || typeof obj === 'number' ||
+           typeof obj === 'boolean' || obj === null) {
+            return true;
+        }
+        return false;
+    },
+
+    appendKey: function(stanzas, arr, key) {
+       /* Get the appropriate key for appending to the array arr,
+        * assuming that stanzas will also be applied, and arr appears
+        * at key within the overall structure. */
+       key = key !== undefined ? key : [];
+       var addition_key = arr.length, prior_key, i;
+       for (i = 0; i < stanzas.length; i++) {
+           prior_key = stanzas[i][0];
+           if (stanzas[i].length > 1 &&
+               prior_key.length === key.length + 1 &&
+               prior_key[prior_key.length-1] >= addition_key)
+           { addition_key = prior_key[prior_key.length-1] + 1; }
        }
-       if (left instanceof Array && right instanceof Array) {
-           if (left.length != right.length) {
-               return false;
+       return addition_key;
+    },
+
+    loopOver: function(obj, callback) {
+       /* Helper function for looping over obj.  Does the Right Thing
+        * whether obj is an array or not. */
+       var i, key;
+       if (obj instanceof Array) {
+           for (i = 0; i < obj.length; i++) {
+               callback(obj, i);
            }
-           for (idx in left) {
-               if ( ! this.isStrictlyEqual(left[idx], right[idx])) {
-                   return false;
+       } else {
+           for (key in obj) {
+               if (obj.hasOwnProperty(key)) {
+                   callback(obj, key);
                }
            }
-           return true;
        }
-       if (left instanceof Array || right instanceof Array) {
-           return false;
-       }
-       var ks = this.computeKeysets(left, right);
-       if (ks[1].length != 0 || ks[2].length != 0) {
-           return false;
-       }
-       for (key in ks[0]) {
-           key = ks[0][key];
-           if ( ! this.isStrictlyEqual(left[key], right[key])) {
-               return false
-           }
-       }
-       return true;
     },
 
-    isTerminal: function (obj) {
-       if (typeof obj == "string" || typeof obj == "number"
-           || typeof obj == "boolean" || obj == null) {
-           return true;
-       }
-       return false;
+    inArray: function(keypath) {
+       var terminal = keypath[keypath.length - 1];
+       return (typeof terminal === 'number') 
     },
 
-    splitDeletions: function (diff) {
-       if (diff.length == 0) {return [[], diff]}
-       diff.sort(function (a,b) {return b.length-a.length});
-       for (idx in diff) {
-           if (diff[idx] > 1) {break}
-       }
-       return [diff.slice(0,idx), diff.slice(idx)]
+    inObject: function(keypath) {
+       var terminal = keypath[keypath.length - 1];
+       return (typeof terminal === 'string') 
     },
 
-    sortStanzas: function (diff) {
-       // Sorts the stanzas in a diff: node changes can occur in any
-       // order, but deletions from sequences have to happen last node
-       // first: ['foo', 'bar', 'baz'] -> ['foo', 'bar'] -> ['foo'] ->
-       // [] and additions to sequences have to happen
-       // leftmost-node-first: [] -> ['foo'] -> ['foo', 'bar'] ->
-       // ['foo', 'bar', 'baz'].
-
-
-       // First we divide the stanzas using splitDeletions():
-       var split_thing = this.splitDeletions(diff);
-       // Then we sort modifications in ascending order of last key:
-       split_thing[0].sort(function (a,b) {return a[0].slice(-1)[0]-b[0].slice(-1)[0]});
-       // And deletions in descending order of last key:
-       split_thing[1].sort(function (a,b) {return b[0].slice(-1)[0]-a[0].slice(-1)[0]});
-       // And recombine:
-       return split_thing[0].concat(split_thing[1])
+    splitDiff: function(diff) {
+       /* Split the stanzas in diff into an array of three arrays:
+        * [modifications, deletions, insertions]. */
+       var idx, objs = [], mods = [], dels = [], inss = [];
+       var dests = {3: inss, 1: dels}, stanza, keypath;
+        if (diff.length === 0) {return [[], diff];}
+        for (idx = 0; idx < diff.length; idx++) {
+           stanza = diff[idx]
+           if (stanza.length === 2) {
+               if (this.inObject(stanza[0])) {
+                   objs.push(stanza);
+               } else {
+                   mods.push(stanza);
+               }
+           } else {
+               dests[stanza.length].push(stanza)
+           }
+        }
+        return [objs, mods, dels, inss];
     },
 
-    computeKeysets: function (left, right) {
-       /* Returns an array of three arrays (overlap, left_only,
-        * right_only), representing the properties common to left and
-        * right, only defined for left, and only defined for right,
-        * respectively. */
-       var overlap = [], left_only = [], right_only = [];
-       var target = overlap;
-       var targ_num = (left instanceof Array);
-
-       for (key in left) {
-           if (targ_num) {
-               key = Number(key)
-           }
-           if (key in right) {
-               target = overlap;
-           }
-           else {
-               target = left_only;
+    stableKeypathLengthSort: function(stanzas) {
+       var comparator = function (a, b) {
+           var swap;
+           if (a[0].length === b[0].length) {
+               return a[0][0] - b[0][0];
            }
-           target.push(key);
+           return b[0].length - a[0].length;
        }
-       for (key in right) {
-           if (targ_num) {
-               key = Number(key)
-           }
-           if (! (key in left)) {
-               right_only.push(key);
-           }
+       for (var i = 0; i < stanzas.length; i++) {
+           stanzas[i][0].unshift(i)
+       }
+       stanzas.sort(comparator)
+       for (i = 0; i < stanzas.length; i++) {
+           stanzas[i][0].shift()
        }
-       return [overlap, left_only, right_only]
+       return stanzas
     },
-
-    commonality: function (left, right) {
-       var com = 0;
-       var tot = 0;
-       if (this.isTerminal(left) || this.isTerminal(right)) {
-           return 0;
+    
+    keypathCompare: function(a, b) {
+       a = a[0]; b = b[0];
+       if (a.length !== b.length) {
+           return a.length - b.length;
        }
-
-       if ((left instanceof Array) && (right instanceof Array)) {
-           for (idx in left) {
-               elem = left[idx];
-               if (right.indexOf(elem) != -1) {
-                   com += 1;
-               }
+       for (var i = 0; i < a.length; i++) {
+           if (typeof a[i] === 'number' && a[i] !== b[i]) {
+               return a[i] - b[i];
            }
-           tot = Math.max(left.length, right.length);
        }
-       else if ((left instanceof Array) || (right instanceof Array)) {
-           return 0;
+       return 0;
+    },
+
+    keypathCompareReverse: function(a, b) {
+       a = a[0]; b = b[0];
+       if (a.length !== b.length) {
+           return b.length - a.length;
        }
-       else {
-            var ks = this.computeKeysets(left, right);
-            o = ks[0]; l = ks[1]; r = ks[2];
-           com = o.length;
-           tot = o.length + l.length + r.length;
-           for (idx in r) {
-               elem = r[idx];
-               if (l.indexOf(elem) == -1) {
-                   tot += 1
-               }
+       for (var i = 0; i < a.length; i++) {
+           if (typeof a[i] === 'number' && a[i] !== b[i]) {
+               return b[i] - a[i];
            }
        }
-       if (tot == 0) {return 0}
-       return com / tot;
+       return 0;
     },
 
-    thisLevelDiff: function (left, right, key, common) {
-       // Returns a sequence of diff stanzas between the objects left and
-       // right, assuming that they are each at the position key within
-       // the overall structure.
-       var out = [];
-       key = typeof key !== 'undefined' ? key: [];
+    sortStanzas: function(diff) {
+        /* Sorts the stanzas in a diff: object changes can occur in
+        * any order, but deletions from arrays have to happen last
+        * node first: ['foo', 'bar', 'baz'] -> ['foo', 'bar'] ->
+        * ['foo'] -> []; additions to sequences have to happen
+        * leftmost-node-first: [] -> ['foo'] -> ['foo', 'bar'] ->
+        * ['foo', 'bar', 'baz'], and insert-and-shift alterations to
+        * arrays must happen last. */
 
-       if (typeof common == 'undefined') {
-           common = this.commonality(left, right);
-       }
+        // First we divide the stanzas using splitDiff():
+        var split_thing = this.splitDiff(diff);
+       // Then we sort modifications of arrays in ascending order of keypath
+       // (note that we can’t tell appends from mods on the info available):
+        split_thing[1].sort(this.keypathCompare);
+        // Deletions from arrays in descending order of keypath:
+        split_thing[2].sort(this.keypathCompareReverse);
+       // And insert-and-shifts in ascending order of keypath:
+        split_thing[3].sort(this.keypathCompare)
+        diff = split_thing[0].concat(
+           split_thing[1], split_thing[2], split_thing[3]
+       );
+       // Finally, we sort by length of keypath:
+       diff = this.stableKeypathLengthSort(diff, true)
+       return diff
+    },
 
-       if (common) {
-           var ks = this.computeKeysets(left, right);
-           for (idx in ks[0]) {
-               okey = ks[0][idx];
-               if (left[okey] != right[okey]) {
-                   out.push([key.concat([okey]), right[okey]]);
-               }
-           }
-           for (idx in ks[1]) {
-               okey = ks[1][idx];
-               out.push([key.concat([okey])]);
-           }
-           for (idx in ks[2]) {
-               okey = ks[2][idx];
-               out.push([key.concat([okey]), right[okey]]);
-           }
-           return out
-       }
-       else if ( ! this.isStrictlyEqual(left,right)) {
-           return [[key, right]]
-       }
-       else {
-           return []
-       }
+    computeKeysets: function(left, right) {
+        /* Returns an array of three arrays (overlap, left_only,
+         * right_only), representing the properties common to left and
+         * right, only defined for left, and only defined for right,
+         * respectively. */
+        var overlap = [], left_only = [], right_only = [];
+        var target = overlap;
+
+        this.loopOver(left, function(obj, key) {
+            if (right[key] !== undefined) {
+                target = overlap;
+            }
+            else {
+                target = left_only;
+            }
+            target.push(key);
+        });
+        this.loopOver(right, function(obj, key) {
+            if (left[key] === undefined) {
+                right_only.push(key);
+            }
+        });
+        return [overlap, left_only, right_only];
     },
 
-    keysetDiff: function (left, right, key) {
-       var out = [];
-       var ks = this.computeKeysets(left, right);
-       for (k in ks[1]) {
-           out.push([key.concat(ks[1][k])]);
+    structureWorthInvestigating: function(left, right) {
+       /* Test whether it is worth looking at the internal structure
+        * of `left` and `right` to see if they can be efficiently
+        * diffed. */
+        if (this.isTerminal(left) || this.isTerminal(right)) {
+            return false;
+        }
+       if ((left.length === 0) || (right.length === 0)) {
+           return false;
        }
-       for (k in ks[2]) {
-           out.push([key.concat(ks[2][k]), right[ks[2][k]]]);
+        if ((left instanceof Array) && (right instanceof Array)) {
+           return true;
        }
-       for (k in ks[0]) {
-           out = out.concat(this.diff(left[ks[0][k]], right[ks[0][k]],
-                                      key.concat([ks[0][k]])))
+       if ((left instanceof Array) || (right instanceof Array)) {
+           return false;
+       }
+       if ((typeof left === 'object') && (typeof right === 'object')) {
+           return true;
        }
-       return out;
+       return false;
     },
 
-    patchStanza: function (struc, diff) {
-       // Applies the diff stanza diff to the structure struc.  Returns
-       // the modified structure.
-       key = diff[0];
-       switch (key.length) {
-       case 0:
-           struc = diff[1];
-           break;
-       case 1:
-           if (diff.length == 1) {
-               if (typeof struc.splice == 'undefined') {
-                   delete struc[key[0]];
-               }
-               else {
-                   struc.splice(key[0], 1);
-               }
-           }
-           else {
-               struc[key[0]] = diff[1];
-           }
-           break;
-       default:
-           pass_key = key.slice(1);
-           pass_struc = struc[key[0]];
-           pass_diff = [pass_key].concat(diff.slice(1));
-           struc[key[0]] = this.patchStanza(pass_struc, pass_diff);
-       }
-       return struc;
+    commonality: function(left, right) {
+       /* Calculate the amount that the structures left and right
+        * have in common */
+        var com = 0, tot = 0;
+        var elem, keysets, o, l, r, idx;
+        if (this.isTerminal(left) || this.isTerminal(right)) {
+            return 0;
+        }
+
+        if ((left instanceof Array) && (right instanceof Array)) {
+            for (idx = 0; idx < left.length; idx++) {
+                elem = left[idx];
+                if (right.indexOf(elem) !== -1) {
+                    com++;
+                }
+            }
+            tot = Math.max(left.length, right.length);
+        }
+        else {
+           if ((left instanceof Array) || (right instanceof Array)) {
+               return 0;
+            }
+            keysets = this.computeKeysets(left, right);
+            o = keysets[0]; l = keysets[1]; r = keysets[2];
+            com = o.length;
+            tot = o.length + l.length + r.length;
+            for (idx = 0; idx < r.length; idx++) {
+                elem = r[idx];
+                if (l.indexOf(elem) === -1) {
+                    tot++;
+                }
+            }
+        }
+        if (tot === 0) {return 0;}
+        return com / tot;
     },
 
-    patch: function (struc, diff) {
-       // Applies the sequence of diff stanzas diff to the structure
-       // struc, and returns the patched structure.
-       for (stan_key in diff) {
-           struc = this.patchStanza(struc, diff[stan_key]);
-       }
-       return struc
+    thisLevelDiff: function(left, right, key, common) {
+        /* Returns a sequence of diff stanzas between the objects left
+        * and right, assuming that they are each at the position key
+        * within the overall structure. */
+        var out = [], idx, okey;
+        key = key !== undefined ? key : [];
+
+        if (common === undefined) {
+            common = this.commonality(left, right);
+        }
+
+        if (common) {
+            var ks = this.computeKeysets(left, right);
+            for (idx = 0; idx < ks[0].length; idx++) {
+                okey = ks[0][idx];
+                if (left[okey] !== right[okey]) {
+                    out.push([key.concat([okey]), right[okey]]);
+                }
+            }
+            for (idx = 0; idx < ks[1].length; idx++) {
+                okey = ks[1][idx];
+                out.push([key.concat([okey])]);
+            }
+            for (idx = 0; idx < ks[2].length; idx++) {
+                okey = ks[2][idx];
+                out.push([key.concat([okey]), right[okey]]);
+            }
+            return out;
+        }
+        if (! this.isStrictlyEqual(left, right)) {
+            return [[key, right]];
+        }
+        return [];
     },
 
-    diff: function (left, right, key, minimal) {
-       key = typeof key !== 'undefined' ? key : [];
-       minimal = typeof minimal !== 'undefined' ? minimal: true;
-       var dumbdiff = [[key, right]]
-       var my_diff = [];
+    keysetDiff: function(left, right, minimal, key) {
+       /* Compute a diff between left and right, without treating
+        * arrays differently from objects. */
+        minimal = minimal !== undefined ? minimal : true;
+        var out = [], k;
+        var ks = this.computeKeysets(left, right);
+        for (k = 0; k < ks[1].length; k++) {
+            out.push([key.concat(ks[1][k])]);
+        }
+        for (k = 0; k < ks[2].length; k++) {
+            out.push([key.concat(ks[2][k]), right[ks[2][k]]]);
+        }
+        for (k = 0; k < ks[0].length; k++) {
+            out = out.concat(this.diff(left[ks[0][k]], right[ks[0][k]],
+                                       minimal, key.concat([ks[0][k]])));
+        }
+        return out;
+    },
 
-       common = this.commonality(left, right);
-       if (common < 0.5) {
-           my_diff = this.thisLevelDiff(left, right, key, common);
-       }
-       else {
-           my_diff = this.keysetDiff(left, right, key);
+    needleDiff: function(left, right, minimal, key) {
+       /* Compute a diff between left and right.  If both are arrays,
+        * a variant of Needleman-Wunsch sequence alignment is used to
+        * make the diff minimal (at a significant cost in both
+        * storage and processing).  Otherwise, the parms are passed on
+        * to keysetDiff.*/
+        if (! (left instanceof Array && right instanceof Array)) {
+           return this.keysetDiff(left, right, minimal, key);
        }
+        minimal = minimal !== undefined ? minimal : true;
+       var down_col = 0, lastrow = [], i, sub_i, left_i, right_i, col_i;
+       var row, first_left_i, left_elem, right_elem;
+       var cand_length, win_length, cand, winner;
+
+       var modify_cand = function () {
+           if (col_i + 1 < lastrow.length) {
+               return lastrow[col_i+1].concat(
+                   JSON_delta.diff(left_elem, right_elem,
+                                   minimal, key.concat([left_i]))
+               );
+           }
+       };
+
+       var delete_cand = function () {
+           if (row.length > 0) {
+               return row[0].concat([[key.concat([left_i])]]);
+           }
+       };
+
+       var append_cand = function () {
+           if (col_i === down_col) {
+               return lastrow[col_i].concat(
+                   [[key.concat([JSON_delta.appendKey(lastrow[col_i], left, key)]),
+                     right_elem]]
+               );
+           }
+       };
 
-       if (minimal) {
-           if (JSON.stringify(dumbdiff).length <
-               JSON.stringify(my_diff).length) {
-               my_diff = dumbdiff
+       var insert_cand = function () {
+           if (col_i !== down_col) {
+               return lastrow[col_i].concat(
+                   [[key.concat([right_i]), right_elem, "i"]]
+               );
+           }
+       };
+
+       var cand_funcs = [modify_cand, delete_cand, append_cand, insert_cand];
+
+       for (i = 0; i <= left.length; i++) {
+           lastrow.unshift([]);
+           for (sub_i = 0; sub_i < i; sub_i++) {
+               lastrow[0].push([key.concat([sub_i])]);
            }
        }
 
-       if (key.length == 0) {
-           if (my_diff.length > 1) {
-               my_diff = this.sortStanzas(my_diff);
+       for (right_i = 0; right_i < right.length; right_i++) {
+           right_elem = right[right_i];
+           row = []
+           for (left_i = 0; left_i < left.length; left_i++) {
+               left_elem = left[left_i];
+               col_i = left.length - left_i - 1;
+               win_length = Infinity;
+               for (i = 0; i < cand_funcs.length; i++) {
+                   cand = cand_funcs[i]();
+                   if (cand !== undefined) {
+                       cand_length = JSON.stringify(cand).length;
+                       if (cand_length < win_length) {
+                           winner = cand;
+                           win_length = cand_length;
+                       }
+                   }
+               }
+               row.unshift(winner);
            }
+           lastrow = row;
        }
-       return my_diff;
-    }
-}
+       return winner;
+    },
 
-// node.js
-if (typeof exports !== 'undefined') exports.JSON_delta = JSON_delta;
+    patchStanza: function(struc, diff) {
+        /* Applies the diff stanza diff to the structure struc.
+         Returns the modified structure. */
+        var key = diff[0];
+        switch (key.length) {
+        case 0:
+            struc = diff[1];
+            break;
+        case 1:
+            if (diff.length === 1) {
+                if (struc.splice === undefined) {
+                    delete struc[key[0]];
+                }
+                else {
+                    struc.splice(key[0], 1);
+                }
+            } else if (diff.length === 3) {
+               if (struc.splice === undefined) {
+                    struc[key[0]] = diff[1];
+               } else {
+                   struc.splice(key[0], 0, diff[1]);
+               }
+           }
+            else {
+                struc[key[0]] = diff[1];
+            }
+            break;
+        default:
+            var pass_key = key.slice(1), pass_struc = struc[key[0]];
+            var pass_diff = [pass_key].concat(diff.slice(1));
+           if (pass_struc === undefined) {
+               if (typeof pass_key[0] === 'string') {
+                   pass_struc = {};
+               } else {
+                   pass_struc = [];
+               }
+           }
+            struc[key[0]] = this.patchStanza(pass_struc, pass_diff);
+        }
+        return struc;
+    }
+};