fogsaadiff

fogsaadiff

I created this library because of frustration that typical diffs didn't work very well on arrays, e.g. when you insert or delete a value, often the diff will say that every value after it has changed.

JSON Patch defines a JSON document structure for expressing a sequence of operations to apply to a JavaScript Object Notation (JSON) document; it is suitable for use with the HTTP PATCH method.

fogsaadiff creates a JSON Patch document by diffing two JSON objects.

I have created it with the intention that it would be a good diff for working with different versions of a single immutable datastructure, so most of the deeply nested objects would be structurally shared and refer to the same objects.

Because of this, I look for opportunities to return early, and I try to avoid replacing whole objects. I also attempt to find an optimal alignment for any arrays that keeps the number of insertions and deletions small.

Implementation

The main body of the diff has been modified from the diff implemented in JSON8.

The array part of the diff is an alignment made by the fogsaa algorithm. It has been ported from C code that I found in github by Hanaa Mohamed.

I re-export the patch from immutable-json-patch, because that is likely to be the most appropriate patch function to use for use cases where this diff is useful.

Example

const bob = {name: 'bob', email: '[e-mail]', age: 32, address: {no: 52, street: "state st"}}
const toby = {name: 'toby', email: '[e-mail]', age: 27, address: {no: 33, street: "mine close"}}
const jim = {name: 'jim', email: '[e-mail]', age: 11, address: {no: 1, street: "world"}}
const alf = {name: 'alf', email: '[e-mail]', age: 15, address: {no: 3, street: "leon st"}}
const toby2 = {name: 'toby', email: '[e-mail]', age: 17, address: {no: 33, street: "mine close"}}

const a = [toby, bob, jim]
const b = [alf, toby2, bob, jim]

const p = diff(a, b)
const r = patch(a, p)

// The diff & patching process has not changed any items in a that didn't need to be changed.
console.log(a[1] === r[2], a[2] === r[3], r[0] === alf, r[2] === bob, r[3] === jim, r[1].address === toby.address)

The patch that fogsadiff identifies looks like this:

[
  {
    "op": "replace",
    "path": "/0/age",
    "value": 17
  },
  {
    "op": "add",
    "path": "/0",
    "value": {
      "name": "alf",
      "email": "[e-mail]",
      "age": 15,
      "address": {
        "no": 3,
        "street": "leon st"
      }
    }
  }
]

Notice that it's spotted that there's been a single insertion and a single edit, and the other values in the array haven't changed at all. JSON8 diff will create a patch that replaces every item in the array with a new one, with 44 lines of patch, instead of 19.