X-Git-Url: https://git.sesse.net/?p=remoteglot;a=blobdiff_plain;f=www%2Fjs%2Fjson_delta.js;h=f379ac5d72569851cacdc0cbb9c12bcf789d325a;hp=357fa7aba3e6b2439effb91320a95765acbb4840;hb=ac9db84904ea04e52f5abd631611aa452239e421;hpb=c22dc885ba5a973043a8e0964e29efb8e92c52e8 diff --git a/www/js/json_delta.js b/www/js/json_delta.js index 357fa7a..f379ac5 100644 --- a/www/js/json_delta.js +++ b/www/js/json_delta.js @@ -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 . @@ -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]; } @@ -450,6 +531,3 @@ JSON_delta = { return struc; } }; - -// node.js -if (typeof exports !== 'undefined') exports.JSON_delta = JSON_delta;