small-json-diff

Library for creating small RFC6902 compliant json diffs. The char length of the diff is guaranteed to be smaller than that of the diff produced by replacing the entire object. This is recursively true for each sub-object.

The algorithm will produce "add", "remove" and "replace" operations. The diff produced (limited to these operations) will be the smallest possible as long as no arrays are used. The optimal diff may not be computed when multiple changes are made inside an array. But some common scenarios are supported:

1. One or more items gets a new value.
2. One or more items are added to the end of the array.
3. One or more items are removed from the end of the array.
4. Exactly one item is added or removed at any position in the array.

1 can be combined with 2 or 3. In all of these cases the optimal diff will be produced.

Install

Install the current version (and save it as a dependency):

$ npm install small-json-diff --save

Usage

var smallJsonDiff = require("small-json-diff");

var oldDocument = {
    type: "Test document",
    arrayWillChange: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
    numberWillChange: 1,
    prop1: 1,
    prop2: {
        test1: 123,
        test2: 456
    },
    prop3: null
};

var newDocument = {
    type: "Test document",
    arrayWillChange: [1, 2, 3, 4, 5],
    numberWillChange: 2,
    prop1: 1,
    prop2: {
        test1: 123,
        test2: 456
    },
    prop3: null
};

var diff = smallJsonDiff.diff(oldDocument, newDocument);

// diff = [
//   {
//     "op": "replace",
//     "path": "/numberWillChange",
//     "value": 2
//   },
//   {
//     "op": "replace",
//     "path": "/arrayWillChange",
//     "value": [1, 2, 3, 4, 5]
//   }
// ]

The diff can be used as input to a patch operation for any RFC6902 compliant library. For instance could the fast-json-patch library be used like this:

var fastJsonPatch = require("fast-json-patch");

var newDocument = fastJsonPatch.applyPatch(oldDocument, diff);

Typescript

This library is written in Typescript and the Typescript definitions are included.

Complexity

The complexity of the diff funciton is O(n) where n is the number of unique paths in the objects that are diffed.

Main logic (simplified)

The paths in the old object and new object are traversed. During this traversal the information needed to create a small diff is gathered and stored in a tree structure. For each node the correct diff operation is determined. There are 5 possible operations: "add", "remove", "replace", "children" and "none.

• "add" = Perform add operation for this node's path with the value at this path in the new object.

• "remove" = Perform remove operation for this node's path.

• "replace" = Perform replace operation for this node's path with the value at this path in the new object.

• "none" = Do nothing. The values match.

• "children" = Perform the operations dictated by this node's children

The length of the diff required to perform the operation is determined and stored as "diffSize". When the operation is "children" the diffSize is the sum of the children's diffSizes.

When determining what operation should be performed the diffSize of using "children" is compared to the diffSize of performing a "replace".

Arrays are scanned in such a way that add/remove of 1 element will be detected.