Description
I experienced too much recursion errors when trying to diff ~5+ MB JSON files.
I ended up not using jsondiffpatch, but I am sharing my experiments below in the hope they would be found useful.
I think the error is caused by the LCS algorithm, and I attempted the following approach that seemed to work. However please note that it has not been tested, and in particular I am not sure if indices1 and indices2 are set properly.
// Adapted from http://rosettacode.org/wiki/Longest_common_subsequence#Dynamic_Programming_4
function lcs(x, y, match, ctx) {
var m = x.length;
var n = y.length;
// Build the c-table.
var i, j, row = [], c = [], left, diag, latch;
for (j = 0; j < n; row[j++] = 0);
for (i = 0; i < m; i++) {
c[i] = row = row.slice();
for (diag = 0, j = 0; j < n; j++, diag = latch) {
latch = row[j];
if ( match(x, y, i, j, ctx) ) {
row[j] = diag + 1;
} else {
left = row[j-1] || 0;
if (left > row[j]) {
row[j] = left;
}
}
}
}
i--, j--;
// row[j] now contains the length of the lcs.
// Recover the lcs from the table.
var sequence = [], indices1 = [], indices2 = [];
while (i > -1 && j > -1) {
switch (c[i][j]) {
default:
j--;
sequence.unshift(x[i]);
indices1.unshift(i); // ?
indices2.unshift(j); // ?
case (i && c[i-1][j]):
i--;
continue;
case (j && c[i][j-1]):
j--;
}
}
return { sequence, indices1, indices2 };
}The above function is to be called as follows. It makes unnecessary all the other functions in this file but defaultMatch:
--- jsondiffpatch/src/filters/lcs.js
+++ jsondiffpatch/src/filters/lcs.js
@@ -63,8 +63,8 @@
var get = function(array1, array2, match, context) {
context = context || {};
- var matrix = lengthMatrix(array1, array2, match || defaultMatch, context);
- var result = backtrack(matrix, array1, array2, array1.length, array2.length, context);
+ match = match || defaultMatch;
+ var result = lcs(array1, array2, match, context);
if (typeof array1 === 'string' && typeof array2 === 'string') {
result.sequence = result.sequence.join('');
}Metadata
Metadata
Assignees
Labels
No labels