benjamine / jsondiffpatch

Diff & patch JavaScript objects
MIT License
4.83k stars 472 forks source link

crash with cyclic structures #152

Open sjoerd222888 opened 8 years ago

sjoerd222888 commented 8 years ago

The following code will make the current tab in chrome crash:

var parent = {
    child : {
        parent : {}
        }
    }

parent.child.parent = parent;

var parentTwo = {
    child : {
        parent : {}
    }
}

parentTwo.child.parent = parentTwo;     

var delta  = jsondiffpatch.diff(parentTwo, parent);

At first JsonDiffPatch should not make the whole tab crash but rather throw an error with a corresponding error message.

If it is clear that JsonDiffPatch does not support cyclic structures it would be nice to mention this in the documentation.

Maybe it would be possible to write a plugin to support cyclic structures? I don't know.

benjamine commented 8 years ago

hi, thanks, yes, I think it is possible to detect circular references with a plugin. jsondiffpatch walks the object tree with a linked stack, so it's possible at each node (see docs/plugins.md for an example plugin) to ask for all the ancestors (context.left, context.parent.left, context.parent.parent.left) and do a === to find the circular ref. note that not all circular references cause this lib to fail, the infinite loop is only possible when you have, like in the example, a circular reference in both sides of the diff, and in the same path.

sjoerd222888 commented 8 years ago

Thanks. With the help of context.parent it is indeed possible.

Here a possible working plugin to detect a loop. I have added a safeguard check because it if you change the code and make a mistake it will again crash chrome which is not really nice.

var isLoop = function(context) {
    var i=0;        
    var currentParentContext = context.parent;
    while (currentParentContext !== undefined){
        console.log("checking parent level " + i)
        if(currentParentContext.left === context.left  && currentParentContext.right === context.right ){
            return true;
         }
         currentParentContext = currentParentContext.parent;
         i++;
         if(i>=100000){
            throw Error("fatal error in loop detection");
        }
    }
    return false;
}

//custom filter to handle cyclic loop
var loopDetectionFilter = function(context) {
    if (typeof context.left === 'object' && typeof context.right === 'object') {
        if (isLoop(context)) {
            context.setResult(undefined);
            context.exit();
        }
    }
}

loopDetectionFilter.filterName = 'loopDetection';

var jsondiffpatchInstance = jsondiffpatch.create();
jsondiffpatchInstance.processor.pipes.diff.before('trivial', loopDetectionFilter);
benjamine commented 8 years ago

that looks great!, just a comment, if a loop is detected, I think I would throw an Error too, but of course, that depends on your needs.

benjamine commented 8 years ago

on a second thought, that's fine, if a loop is found, ignoring that branch is fine for diffing, as any difference will be detected in a parent, nice.

snej commented 6 years ago

If it is clear that JsonDiffPatch does not support cyclic structures it would be nice to mention this in the documentation.

FYI, JSON does not support cycles (or DAGs), just trees. Any JavaScript object structure with a cycle is not valid JSON, so IMHO the library's behavior is undefined. But of course errors are nicer undefined behavior than crashes...

sjoerd222888 commented 6 years ago

Absolutely right but the library is for diffing original JavaScript structures and creates JSON based diff information. So having cyclic objects and then describe the difference between them with a non-cyclic JSON make absolutely sense to me. The question is not about a cyclic diff JSON but comparison of cyclic objects.

snej commented 6 years ago

the library is for diffing original JavaScript structures

Ah — I had missed that detail. I'm just seeing this as a tool for delta-compressing JSON. Never mind!