Maximum call stack size is exceeded if very large array is provided for diff

[malhar-trivedi]

node @v4.4.7
jsondiffpatch @0.1.43

while taking diff for very large arrays (it could contain more than 5k objects), I encounter this error.

/Users/malhar.trivedi/node_modules/jsondiffpatch/src/filters/arrays.js:42
function matchItems(array1, array2, index1, index2, context) {
                   ^

RangeError: Maximum call stack size exceeded
    at Array.matchItems [as match] (/Users/malhar.trivedi/node_modules/jsondiffpatch/src/filters/arrays.js:42:20)
    at backtrack (/Users/malhar.trivedi/node_modules/jsondiffpatch/src/filters/lcs.js:49:14)
    at backtrack (/Users/malhar.trivedi/node_modules/jsondiffpatch/src/filters/lcs.js:50:23)
    at backtrack (/Users/malhar.trivedi/node_modules/jsondiffpatch/src/filters/lcs.js:58:12)
    at backtrack (/Users/malhar.trivedi/node_modules/jsondiffpatch/src/filters/lcs.js:60:12)
    at backtrack (/Users/malhar.trivedi/node_modules/jsondiffpatch/src/filters/lcs.js:60:12)
    at backtrack (/Users/malhar.trivedi/node_modules/jsondiffpatch/src/filters/lcs.js:50:23)
    at backtrack (/Users/malhar.trivedi/node_modules/jsondiffpatch/src/filters/lcs.js:60:12)
    at backtrack (/Users/malhar.trivedi/node_modules/jsondiffpatch/src/filters/lcs.js:50:23)
    at backtrack (/Users/malhar.trivedi/node_modules/jsondiffpatch/src/filters/lcs.js:58:12)

Here's the sample code to reproduce this error. This sample data has large array size because value of object size is relatively small. as I increase object size, I can further reduce size of array.

'use strict';

const jsondiffpatch = require('jsondiffpatch');
const options = {
    objectHash: function (obj) {
        return obj.id || JSON.stringify(obj);
    }
};

const ARRAY_LENGTH = 7000;
const seedData = {
    field1: 'some string data',
    field2: 'some another string data. Este es completa basura escrito en español',
    field3: 'This is a complete garbage and should not be considered even',
    timestamp: Date.now()
};
const LARGE_STRING = 'This becomes much more larger field than it was before. It might even contain unicode characters as well \uFFFF \
                    This one has completely different characters than it used to before \uFFFF';

function createData(){    
    let result = [];
    for (let i=0; i < ARRAY_LENGTH; i++) {
        if(Math.random() > 0.5) {
            result.push(Object.assign({}, seedData, {
                timestamp: Date.now(),
                field1 : LARGE_STRING,
                field3 : LARGE_STRING
            }));
        } else {
            result.push(seedData);
        }        
    }
    return result;    
}

function testForLargeArray () {
    let largeArray1 = createData();
    let largeArray2 = createData();
    let differ = jsondiffpatch.create(options);
    let diff = differ.diff(largeArray1, largeArray2);
}
testForLargeArray();

[benjamine]

that's nice!, thanks, I see what you mean now, the problem is in the LCS algorithm (used when diffing arrays), I suspect LCS might be a bit too expensive for very large arrays and we could fallback to a simpler strategy for these, or try to split the diff in chunks somehow.
Just a guess though, thanks for bringing this up, I'll take a deeper look.

[kimptoc]

FWIW - Still see this issue in 0.2.4.

[benjamine]

yes @kimptoc this ticket is still open.

[udaybuie]

hi, i am facing the same issue, i tried a work around by sorting both array using array sort(using all key in array's each object), without providing any hash function in jsondiffpatch, and i am certain it gives the right result when both arrays are equal, but how to get the diff when they are not equal? may i know if we are planning to fix this issue in near future?