diff-merge-patch

Diff, merge and patch sets, ordered lists, ordered sets and dictionaries in JavaScript:

• diff(before, after) - returns you all changes in 'after' since 'before'
• merge(diffs) - 3-way merging of multiple diffs on the same base object
• patch(before, diff) - patches an object using a (merged) diff

Design goals

• its all just diffs: merge should only need diffs as input and returns itself a new diff
• no magic: make any merge conflicts explicit to cater for different conflict resolution mechanisms
• be commutative: the order of diffs in a merge should not matter
• be recursive: implement diff, patch and merge for basic data structures and use them to support complex data structures

Supported Data Structures

• Sets
• Ordered Lists
• Ordered Sets
• Dictionaries

Sets

Sets are represented as JavasScript Arrays:

var before = [1, 2, 3, 4]
var after1 = [1, 2, 4, 5, 6]
var after2 = [1, 2, 3, 4, 5, 7]

diff

Set diff returns you all inserted and deleted elements:

var diff = require('diff-patch-merge').set.diff
 
var diff1 = diff(before, after1)
// returns:
{diff: [{delete: 3}, {insert: 5}, {insert: 6}]}
 
var diff2 = diff(before, after2)
// returns:
{diff: [{insert: 5}, {insert: 7}]}
 

merge

You can merge multiple diffs that are based on the same old object.
It combines all diffs into a new diff annotating each change with the source diff:

var merge = require('diff-patch-merge').set.merge
 
var mergedDiff = merge([diff1, diff2])
// returns:
{
  diff: [
    {delete: 3, source: [0]},
    {insert: 5, source: [0, 1]},
    {insert: 6, source: [0]},
    {insert: 7, source: [1]}
  ]
}

patch

You can apply diffs as patches to an old set (results of merge() are diffs too):

var patch = require('diff-patch-merge').set.patch
 
var patched = patch(old, mergedDiff)
// returns:
[1, 2, 4, 5, 6, 7]

Ordered Lists

If you want the order of elements considered when doing a diff/merge/patch, ordered lists are the solution for you!

Just like sets they are represented as JavaScript arrays:

var before = [1, 2, 3, 4]
var after1 = [1, 2, 4, 5, 7]
var after2 = [6, 1, 2, 3, 4, 7]

diff

var diff = require('diff-merge-patch').orderedList.diff
 
var diff1 = diff(before, after1)
// returns:
[
  {op: '-', length: 1, indexBefore: 1, indexAfter: 1},
  {op: '+', indexBefore: 3, indexAfter: 2, values: [5, 7]}
]

merge

Merging ordered list diffs never results in conflicts.

var merge = require('diff-merge-patch').orderedList.merge
 
var mergedDiff = merge([diff1, diff2])
// returns:
[
  {op: '+', indexBefore: -1, values: [6], source: [1]},
  {op: '-', length: 1, indexBefore: 1, source: [0]},
  {op: '+', indexBefore: 3, values: [5, 7], source: [0]},
  {op: '+', indexBefore: 3, values: [7], source: [1]}
]

patch

var patch = require('diff-merge-patch').orderedList.patch
 
var patched = patch(before, mergedDiff)
// returns:
[6, 1, 2, 4, 5, 7, 7]

Ordered Sets

Ordered Sets are similar to Ordered Lists except that all elements are globally unique.
This allows diff/merge/patch to consider position changes of elements. In ordered list diffs there is no notion of movement, they can only be seen as a delete and insert of the same element.

Ordered Sets are represented as JavaScript arrays:

var before = [1, 2, 3, 4, 5],
var after1 = [2, 6, 1, 5, 4, 3]
var after2 = [2, 4, 1, 7, 3, 5]

diff

var diff = require('diff-merge-patch').orderedSet.diff
 
var diff1 = diff(before, after1)
// returns:
{
  diff: [
    [3, [{insert: 6}, {move: 0}]],
    [4, [{move: 3}, {move: 2}]]
  ]
}
 
var diff2 = diff(before, after2)
// returns:
{
  diff: [
    [3, [{move: 0}, {insert: 7}, {move: 2}]]
  ]
}

merge

Merging of Ordered List diffs can lead to conflicts:

var merge = require('diff-merge-patch').orderedSet.merge
 
// Note: orderedSet.merge() currently only accepts two diffs as input
var mergedDiff = merge([diff1, diff2])
// returns:
{
  diff: [
    [3, [{insert: 6, source: [0]}, {move: 0, source: [0, 1]}, {insert: 7, source: [1]}, {move: 2, conflict: 1, source: [1]}]],
    [4, [{move: 3, source: [0]}, {move: 2, conflict: 1, source: [0]}]]
  ],
  conflict: 1
}

Each corresponding conflict receives the same conflict-ID.
To use a diff including conflicts to patch the old ordered set you first have to resolve them.
The library comes with a simple conflict resolution strategy which you can invoke like this:

var resolve = require('diff-merge-path').orderedSet.resolve
 
// pick source 0 as the winner of each conflict:
var resolvedDiff = resolve(mergedDiff, 0)
// returns:
{
  diff: [
    [3, [{insert: 6, source: [0]}, {move: 0, source: [0, 1]}, {insert: 7, source: [1]}]],
    [4, [{move: 3, source: [0]}, {move: 2, source: [0]}]]
  ]
}

The algorithm simply picks the conflicting update that comes from the source you pass in.
Depending on your application you may want to implement different resolution strategies.

patch

Diffs can be used to patch the original ordered list:

var patch = require('diff-merge-patch').orderedSet.patch
 
var patched = patch(before, resolvedDiff)
// returns:
[2, 6, 1, 7, 5, 4, 3]

Dictionaries

The same set of functions is implemented for dictionaries.
They are represented as JavaScript Objects:

var dictionary = require('diff-merge-patch').dictionary
 
var before = {1: 1, 2: 2, 3: 3, 4: 4}
var after1 = {5: 6, 3: 8, 2: 2, 4: 4, 1: 5}
var after2 = {2: 2, 1: 9, 4: 5}
 
var diff1 = dictionary.diff(before, after1)
// returns:
{
  diff: {
    5: {value: 6},
    1: {value: 5},
    3: {value: 8}
  }
}
 
var diff2 = dictionary.diff(before, after2)
// returns:
{
  diff: {
    1: {value: 9},
    4: {value: 5},
    3: {value: null}
  }
}
 
var diffsMerged = dictionary.merge([diff1, diff2])
// returns merged diffs with conflicts:
{
  diff: {
    1: [{value: 5, source: [0]}, {value: 9, source: [1]}],
    3: [{value: 8, source: [0]}, {value: null, source: [1]}],
    4: {value: 5, source: [1]},
    5: {value: 6, source: [0]}
  },
  conflict: [1, 3]
}
 
// resolve all conflicts picking sourc 0 as the winner:
diffsMerged = dictionary.resolve(diffsMerged, 0)
 
var result = patch(before, diffsMerged)

Todo

• Trees (Ordered/Unordered) - can be built using the core data structures
• Tuple set (for tabular data e.g. from a relational database)

Contributors

This project was created by Mirko Kiefer (@mirkokiefer).