From: Steinar H. Gunderson Date: Fri, 25 Nov 2016 21:04:02 +0000 (+0100) Subject: Revert "Upgrade JSON-delta to v2.0, to hopefully fix some diffing bugs." X-Git-Url: https://git.sesse.net/?p=remoteglot;a=commitdiff_plain;h=499cd5d2a43e0eebf7b2756784c879dcb3f420c0;ds=sidebyside Revert "Upgrade JSON-delta to v2.0, to hopefully fix some diffing bugs." This reverts commit ac9db84904ea04e52f5abd631611aa452239e421. --- diff --git a/www/js/json_delta.js b/www/js/json_delta.js index f379ac5..dad457b 100644 --- a/www/js/json_delta.js +++ b/www/js/json_delta.js @@ -1,7 +1,6 @@ -/* JSON-delta v2.0 - A diff/patch pair for JSON-serialized data -structures. +/* JSON-delta v0.2 - A diff/patch pair for JSON-serialized data structures. -Copyright 2013-2015 Philip J. Roberts . +Copyright 2013-2014 Philip J. Roberts . All rights reserved Redistribution and use in source and binary forms, with or without @@ -30,504 +29,265 @@ 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 = { - // 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); + isStrictlyEqual: function (left, right) { + if (this.isTerminal(left) && this.isTerminal(right)) { + return (left === right); } - - 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 (this.isTerminal(left) || this.isTerminal(right)) { + 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); + if (left instanceof Array && right instanceof Array) { + if (left.length != right.length) { + return false; } - } else { - for (key in obj) { - if (obj.hasOwnProperty(key)) { - callback(obj, key); + for (idx in left) { + if ( ! this.isStrictlyEqual(left[idx], right[idx])) { + return false; } } + 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; }, - inArray: function(keypath) { - var terminal = keypath[keypath.length - 1]; - return (typeof terminal === 'number') + isTerminal: function (obj) { + if (typeof obj == "string" || typeof obj == "number" + || typeof obj == "boolean" || obj == null) { + return true; + } + return false; }, - inObject: function(keypath) { - var terminal = keypath[keypath.length - 1]; - return (typeof terminal === 'string') + 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)] }, - 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]; + 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]) }, - stableKeypathLengthSort: function(stanzas) { - var comparator = function (a, b) { - var swap; - if (a[0].length === b[0].length) { - return a[0][0] - b[0][0]; + 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) } - return b[0].length - a[0].length; - } - for (var i = 0; i < stanzas.length; i++) { - stanzas[i][0].unshift(i) + if (key in right) { + target = overlap; + } + else { + target = left_only; + } + target.push(key); } - stanzas.sort(comparator) - for (i = 0; i < stanzas.length; i++) { - stanzas[i][0].shift() + for (key in right) { + if (targ_num) { + key = Number(key) + } + if (! (key in left)) { + right_only.push(key); + } } - return stanzas + return [overlap, left_only, right_only] }, - - keypathCompare: function(a, b) { - a = a[0]; b = b[0]; - if (a.length !== b.length) { - return a.length - b.length; + + commonality: function (left, right) { + var com = 0; + var tot = 0; + if (this.isTerminal(left) || this.isTerminal(right)) { + return 0; } - for (var i = 0; i < a.length; i++) { - if (typeof a[i] === 'number' && a[i] !== b[i]) { - return a[i] - b[i]; + + if ((left instanceof Array) && (right instanceof Array)) { + for (idx in left) { + elem = left[idx]; + if (right.indexOf(elem) != -1) { + com += 1; + } } + tot = Math.max(left.length, right.length); } - return 0; - }, - - keypathCompareReverse: function(a, b) { - a = a[0]; b = b[0]; - if (a.length !== b.length) { - return b.length - a.length; + else if ((left instanceof Array) || (right instanceof Array)) { + return 0; } - for (var i = 0; i < a.length; i++) { - if (typeof a[i] === 'number' && a[i] !== b[i]) { - return b[i] - a[i]; + 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 + } } } - return 0; + if (tot == 0) {return 0} + return com / tot; }, - 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. */ - - // 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 - }, + 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: []; - 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; + if (typeof common == 'undefined') { + common = this.commonality(left, right); + } - 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]; + 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 [] + } }, - 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; + 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])]); } - if ((left instanceof Array) && (right instanceof Array)) { - return true; + for (k in ks[2]) { + out.push([key.concat(ks[2][k]), right[ks[2][k]]]); } - if ((left instanceof Array) || (right instanceof Array)) { - return false; - } - if ((typeof left === 'object') && (typeof right === 'object')) { - 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]]))) } - return false; + return out; }, - 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; + 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; }, - 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 []; + 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 }, - 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; - }, + diff: function (left, right, key, minimal) { + key = typeof key !== 'undefined' ? key : []; + minimal = typeof minimal !== 'undefined' ? minimal: true; + var dumbdiff = [[key, right]] + var my_diff = []; - 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); + common = this.commonality(left, right); + if (common < 0.5) { + my_diff = this.thisLevelDiff(left, right, key, common); } - 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]] - ); - } - }; - - 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])]); - } + else { + my_diff = this.keysetDiff(left, right, key); } - 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); + if (minimal) { + if (JSON.stringify(dumbdiff).length < + JSON.stringify(my_diff).length) { + my_diff = dumbdiff } - lastrow = row; } - return winner; - }, - 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 = []; - } + if (key.length == 0) { + if (my_diff.length > 1) { + my_diff = this.sortStanzas(my_diff); } - struc[key[0]] = this.patchStanza(pass_struc, pass_diff); - } - return struc; + } + return my_diff; } -}; +} + +// node.js +if (typeof exports !== 'undefined') exports.JSON_delta = JSON_delta;