Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

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

Open
malhar-trivedi opened this issue Jul 18, 2016 · 4 comments · May be fixed by #173
Open

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

malhar-trivedi opened this issue Jul 18, 2016 · 4 comments · May be fixed by #173

Comments

@malhar-trivedi
Copy link

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
Copy link
Owner

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
Copy link

kimptoc commented Feb 12, 2017

FWIW - Still see this issue in 0.2.4.

@benjamine
Copy link
Owner

yes @kimptoc this ticket is still open.

@dirb dirb linked a pull request Feb 20, 2017 that will close this issue
@udaybuie
Copy link

udaybuie commented Oct 8, 2019

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?

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging a pull request may close this issue.

4 participants