Upgrade JSON-delta to v2.0, to hopefully fix some diffing bugs.
[remoteglot] / www / js / json_delta.js
index ab0c3e3..f379ac5 100644 (file)
@@ -1,4 +1,4 @@
-/* JSON-delta v1.1.3 - A diff/patch pair for JSON-serialized data
+/* JSON-delta v2.0 - A diff/patch pair for JSON-serialized data
 structures.
 
 Copyright 2013-2015 Philip J. Roberts <himself@phil-roberts.name>.
@@ -171,38 +171,105 @@ JSON_delta = {
        }
     },
 
-    splitDeletions: function(diff) {
-       /* Split the stanzas in diff into an array of two arrays:
-        * [modifications, deletions]. */
-       var idx;
+    inArray: function(keypath) {
+       var terminal = keypath[keypath.length - 1];
+       return (typeof terminal === 'number') 
+    },
+
+    inObject: function(keypath) {
+       var terminal = keypath[keypath.length - 1];
+       return (typeof terminal === 'string') 
+    },
+
+    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];}
-        diff.sort(function(a, b) {return b.length - a.length;});
         for (idx = 0; idx < diff.length; idx++) {
-            if (diff[idx].length === 1) {break;}
+           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 [diff.slice(0, idx), diff.slice(idx)];
+        return [objs, mods, dels, inss];
+    },
+
+    stableKeypathLengthSort: function(stanzas) {
+       var comparator = function (a, b) {
+           var swap;
+           if (a[0].length === b[0].length) {
+               return a[0][0] - b[0][0];
+           }
+           return b[0].length - a[0].length;
+       }
+       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 stanzas
+    },
+    
+    keypathCompare: function(a, b) {
+       a = a[0]; b = b[0];
+       if (a.length !== b.length) {
+           return a.length - b.length;
+       }
+       for (var i = 0; i < a.length; i++) {
+           if (typeof a[i] === 'number' && a[i] !== b[i]) {
+               return a[i] - b[i];
+           }
+       }
+       return 0;
+    },
+
+    keypathCompareReverse: function(a, b) {
+       a = a[0]; b = b[0];
+       if (a.length !== b.length) {
+           return b.length - a.length;
+       }
+       for (var i = 0; i < a.length; i++) {
+           if (typeof a[i] === 'number' && a[i] !== b[i]) {
+               return b[i] - a[i];
+           }
+       }
+       return 0;
     },
 
     sortStanzas: function(diff) {
-        /* Sorts the stanzas in a diff: node changes can occur in any
-        * order, but deletions from sequences have to happen last
+        /* 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'] -> [] and additions to sequences have to happen
+        * ['foo'] -> []; 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];}
+        * ['foo', 'bar', 'baz'], and insert-and-shift alterations to
+        * arrays must happen last. */
+
+        // 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]
        );
-        // And recombine:
-        return split_thing[0].concat(split_thing[1]);
+       // Finally, we sort by length of keypath:
+       diff = this.stableKeypathLengthSort(diff, true)
+       return diff
     },
 
     computeKeysets: function(left, right) {
@@ -380,7 +447,16 @@ JSON_delta = {
                );
            }
        };
-       var cand_funcs = [modify_cand, delete_cand, append_cand];
+
+       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([]);
@@ -391,9 +467,8 @@ JSON_delta = {
 
        for (right_i = 0; right_i < right.length; right_i++) {
            right_elem = right[right_i];
-           first_left_i = Math.min(right_i, left.length - 1);
-           row = [];
-           for (left_i = first_left_i; left_i < left.length; left_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;
@@ -430,7 +505,13 @@ JSON_delta = {
                 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];
             }