too much recursion errors with large JSON files

[Geoffrey-A]

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('');
   }