dominictarr / xdiff

diff complex javascript objects

xdiff

diff, diff3, patch (nearly) arbitary json documents.

examples

var x = require('xdiff')

var a = SOMEOBJECT
var b = SOMEOBJECT_AFTER_CHANGES

var diff = x.diff(a, b)

// can apply a diff to A to get B

var patched = x.patch(a, diff)

require('assert').deepEqual(a, patched)

diff, patch, diff3

with diff you can create a diff that is applyable with patch you can diff nested objects, and arrays.

with diff3 you create a diff from two objects that have been edited concurrently, you need to also to pass the concestor.

also see adiff which xdiff depends on to diff arrays.

xdiff is compatible with snob

Objects

var a = {a: true, c: 'deleteme'}
var b = {a: true, b: false}
var p = x.diff(a, b)

will create a diff like this:

[ ['set', ['root', 'b'], false]
, ['del', ['root', 'c']] ]

operations on nested objects are represented by thier path, unless the object has an ID. (see below)

var a0 = {A: {AA: '?'}}
var a1 = {A: {AA: 'aardvark'}}
var p = x.diff(a, b)

will create diff like this:

 [['set', ['root', 'A', 'AA'], 'aardvark']]

Arrays

var a = [1, 2 , 3]
var b = [0, 1, 'hello', 3]
var p = x.diff(a, b)

will create a diff like

[ 'splice', ['root'], [
    [ 1, 1, 'hello] //at index 1 delete one item and insert hello
  , [ 0, 0, 0]      //at index 0 delete 0 items and insert `0`
]

Objects in Arrays

if you give objects an ID, then xdiff will beable to track it properly, even if it's moved. even if it's concurrently changed.

var a = [{__id__: '#1'}, 5, {__id__: '#2'}]
var b = [5, {__id__: '#2'}, {__id__: '#1', prop: 'surprise'}]
var p = x.diff(a, b)

will produce a diff like this

  [ ['set', ['#1', 'prop'], 'surprise'] //this applies the change to object #1
  , ['splice', ['root'], [ 
      [ 3, 0, '#=*#1'] //this just updates the reference!
    , [ 0, 1]
    ] ]
  ]

if you don't don't use id's xdiff won't know that an object that has changed is actually the same object. this would cause it to reinsert a new copy of that object.

id's are this is really useful when you need to do 3-way-merges to merge together concurrent changes.

in a future version, xdiff will allow changing the id key. currently it uses only the __id__ property.

3-way-merge: diff3

three way merge takes 3 objects, mine, yours and an old object, which must be the concestor of both mine and yours.

if there are concurrent changes, xdiff will choose to use the change from mine

in a future version, xdiff will support injectable resolve function, so that you can choose how to rosolve the merge.

licence

MIT / Apache2

xdiff's Issues

Standalone Browserified Version Locks up when diffing arrays

Hey Dominic,

Was just trying to use xdiff in the browser as a standalone js file, i.e:

browserify index.js --standalone xdiff

Once I do this, however, diffing arrays just locks up the browser. I'm going to investigate this further myself, but thought I should probably log an issue also.

To replicate the problem, just diff two empty arrays. I'll let you know if I get to the bottom of it.

Cheers,
Damon.

reconsider project naming..

Thanks for writing adiff and xdiff... I add this note with the utmost of respect and apprectiation for your work here.

It's a bit odd that the "adiff" project is actually close to (or exactly) an implemention of the somewhat well known "xdiff" algorithm used in Git, and your "xdiff" project is actually a "javascript tree diff" tool using "adiff".

http://mail.xmailserver.net/xdfs.pdf
http://www.xmailserver.org/xdiff-lib.html

For the sake of people understanding what exists here, you might consider renaming "adiff" to "xdiff" or "js-xdiff", and renaming "xdiff" to "js-tree-diff"

diff3 can produce quite unexpected merges

Repro:

var x = require("xdiff");
var util = require("util");
var o = {"k":["B","C","D","E"]};
var o2 = JSON.parse(JSON.stringify(o));
var a = {"k":["B","X","X","X","X","D","E","ERROR"]}
var b = {"k":["B","C","D","E"]}
var b2 = {"k":["B","Y","D","E"]}

var m = x.patch(o, x.diff3(a,o,b));
console.log(util.inspect(m));

var m2 = x.patch(o2, x.diff3(a,o2,b2));
console.log(util.inspect(m2));

Expected Output:

{ k: [ 'B', 'X', 'X', 'X', 'X', 'D', 'E', 'ERROR' ] }
{ k: [ 'B', 'X', 'X', 'X', 'X', 'D', 'E', 'ERROR' ] }

Actual Output:

{ k: [ 'B', 'X', 'X', 'X', 'X', 'D', 'E', 'ERROR' ] }
{ k: [ 'B', 'X', 'X', 'X', 'ERROR', 'X', 'D', 'E' ] }

(well, maybe "expected output" could be different, but inserting a "fragment" in the middle of another "fragment" is clearly wrong)

How to you propose to change the __id__ value ?

In my use of xdiff, I need to deduce uniqueness from the "id" field, not __id__. I have seen it was one of your next amelioration.

How do you propose to go about it ?

I was thinking about:

var x = require('xdiff').withIdField('id')

var x = require('xdiff')
x.setIdField('id')

A bit uglier, add an idField parameter to all the functions defaulting to __id__ if not specified:

function shallowEqual (a, b, idField) {
...