cujojs/jiff

JSON Patch and diff based on rfc6902

jiff's Issues

Low footprint long text diffs

One of the great things about benjamine's jsondiffpatch is the ability to generate terse patches for changes made to long strings. See the "text" example here.

Right now, with JSON Patch it seems one is stuck doing a large replace. This is doubly awful if one supplies a test operation for the inverse.

Could jiff amend rfc6902 with a patch operation, and use google-diff-match-patch for it?

My use case is making/tracking changes made to wiki articles without wholesale PUTs. I don't want to store the entire article on every PATCH.

Thanks for the wonderful library!

Add patch inversion

Being able to invert patches can help in patch commutation and other scenarios. We should at least consider adding it.

Improve LCS

The LCS algorithm for array diffing works well, but could be made more efficient by combining the lcs construction and the subsequent reduce, and by returning early in cases where it's not necessary to create the lcs matrix:

1. Two passes are done on the common prefix. Could be reduced to 1 pass if lcs() and reduce() are combined.
2. The LCS matrix construction can be skipped entirely when the common prefix + suffix length === a.length or b.length (or both). When:
   1. prefix+suffix length === a.length === b.length, can return immediately. No work to do.
   2. prefix+suffix length === a.length, can emit remaining span of b as additions
   3. prefix+suffix length === b.length, can emit remaining span of a as removals

undefined in comparison creates invalid diff

For the following example:

jiff.diff(
    {
        Field1: '1'
    },
    {
        Field1: undefined
    }
);

The diff creates:

[
  { op: 'test', path: '/Field1', value: '1' },
  { op: 'replace', path: '/Field1', value: undefined },
  { op: 'test', path: '/Field1', value: '1' },
  { op: 'remove', path: '/Field1' }
]

I see two things potentially wrong with this:

1. The replace op with {... value: undefined}, when stringified, will result in a replace op with no value field which isn't valid for json-patch.
2. Even if the first two ops pass, the third op will fail since the value has been changed to undefined.

Is the expectation that I JSON.stringify and JSON.parse before jiff.diff?

Remove patchInPlace?

Now that patching is atomic by default, we may just want to ditch patchInPlace if patching is "fast enough". It's pretty hazardous, especially now that test is implemented.

Check for `move` where `path` is a child of `from`

which is impossible. See the end of https://tools.ietf.org/html/rfc6902#section-4.4

Which operations are generated using `jiff.diff`

I'm developing a MongoDB adapter for JSON Patches and am using jiff to do diffs. Because some operations are not possible with the underlying query language I was wondering if I might make do with just a subset of the operations defined in the RFC.

So I have a couple of questions, that I think I've got the answers to from reading the source, but I'd love if you could confirm:

• Is /arr/- reference used? I don't seem to find it in the diff function.
• Are only add, remove, replace and test used? This seems to be my conclusion from reading through diff, appendChanges, appendObjectChanges, appendArrayChanges etc. and also form some informal tests

Date becomes object after patching

in Chome Canary, OS X

"jiff": "^0.6.0",

code:

    console.log diff, store
    store = jiff.patch diff, store
    console.log store

its log:

diff:

[{"op":"add","path":"/messages","value":[{"id":"7ksRCQ--","time":"2014-12-03T11:40:16.816Z","userId":"7yjrlN0x","text":"df","thread":"default","isThread":false},{"id":"m1xaT7Z-","time":"2014-12-03T11:35:34.723Z","userId":"7yjrlN0x","text":"\nd","thread":"default","isThread":false},{"id":"XJ_As7bW","time":"2014-12-03T11:27:26.617Z","userId":"7yjrlN0x","text":"df","thread":"default","isThread":false},{"id":"Qktysm--","time":"2014-12-03T11:23:27.602Z","userId":"7yjrlN0x","text":"s","thread":"default","isThread":false},{"id":"71SWqm--","time":"2014-12-03T11:19:39.281Z","userId":"7yjrlN0x","text":"x","thread":"default","isThread":false},{"id":"Qkk2KmZb","time":"2014-12-03T11:18:13.355Z","userId":"7yjrlN0x","text":"d","thread":"default","isThread":false},{"id":"mJnUOX-b","time":"2014-12-03T11:12:34.643Z","userId":"7yjrlN0x","text":"f","thread":"default","isThread":false},{"id":"myvuw7Z-","time":"2014-12-03T11:08:44.971Z","userId":"7yjrlN0x","text":"sdfsf","thread":"default","isThread":false},{"id":"mJo1D7-b","time":"2014-12-03T11:06:25.369Z","userId":"7yjrlN0x","text":"che","thread":"default","isThread":false},{"id":"7J8LIXWZ","time":"2014-12-03T11:03:56.608Z","userId":"7yjrlN0x","text":"sdf","thread":"default","isThread":false}]},{"op":"add","path":"/threads","value":[]},{"op":"add","path":"/user","value":{"name":"chen","avatar":"","nickname":"","thread":"default","id":"7yjrlN0x","online":true}}]

result:

{"messages":[{"id":"7ksRCQ--","time":"2014-12-03T11:40:16.000Z","userId":"7yjrlN0x","text":"df","thread":"default","isThread":false},{"id":"m1xaT7Z-","time":"2014-12-03T11:35:34.000Z","userId":"7yjrlN0x","text":"\nd","thread":"default","isThread":false},{"id":"XJ_As7bW","time":"2014-12-03T11:27:26.000Z","userId":"7yjrlN0x","text":"df","thread":"default","isThread":false},{"id":"Qktysm--","time":"2014-12-03T11:23:27.000Z","userId":"7yjrlN0x","text":"s","thread":"default","isThread":false},{"id":"71SWqm--","time":"2014-12-03T11:19:39.000Z","userId":"7yjrlN0x","text":"x","thread":"default","isThread":false},{"id":"Qkk2KmZb","time":"2014-12-03T11:18:13.000Z","userId":"7yjrlN0x","text":"d","thread":"default","isThread":false},{"id":"mJnUOX-b","time":"2014-12-03T11:12:34.000Z","userId":"7yjrlN0x","text":"f","thread":"default","isThread":false},{"id":"myvuw7Z-","time":"2014-12-03T11:08:44.000Z","userId":"7yjrlN0x","text":"sdfsf","thread":"default","isThread":false},{"id":"mJo1D7-b","time":"2014-12-03T11:06:25.000Z","userId":"7yjrlN0x","text":"che","thread":"default","isThread":false},{"id":"7J8LIXWZ","time":"2014-12-03T11:03:56.000Z","userId":"7yjrlN0x","text":"sdf","thread":"default","isThread":false}],"threads":[],"user":{"name":"chen","avatar":"","nickname":"","thread":"default","id":"7yjrlN0x","online":true}}

Proposal: invertible remove, replace, and copy

Given the discussion in #9, and our decision to (ab)use test for now, I figured we could use this issue to focus in on other alternatives that allow patch inversion. We could potentially propose additions/changes to RFC6902.

jiff is not defined

I suspect this is more of an issue regarding my lack of understanding of Browserify, so apologies if that's the case!

I put jiff through Browserify:

browserify /bower_components/jiff/jiff.js > /bower_components/jiff/jiff_bundle.js

I added a script tag for jiff_bundle.js. Now when I call jiff.diff, I get the following:

ReferenceError: jiff is not defined

Any idea what I'm doing wrong? Thanks :)

Reverse jiff.patch arg order

Total breaking API change, but here's why it could be very nice:

var patched = patches.reduce(function(data, patch) {
    return jiff.patch(patch, data);
}, data);

becomes:

var patched = patches.reduce(jiff.patch, data);

Detect invalid patches

Need to detect at least the following cases, and throw a proper error type:

1. add a path whose parent doesn't exist, eg add /foo/bar, when foo doesn't exist
2. replace a path that doesn't exist
3. remove a path that doesn't exist (hmmm, should this just be silent instead??)

Medium vulnerability in SNYK

We are using SNYK and after adding the jiff package a medium vulnerability was detected, connected to the add operation.

See https://security.snyk.io/vuln/SNYK-JS-JIFF-1017118 for more information

It would've been great if additional validation was made to get rid of this vulnerability.

Make patching atomic by default

RFC6902 specifically says that patching must be atomic. Currently, jiff.patch(patch, target) mutates target as it executes. If a patch operations fails, target will be left in an inconsistent state. Clearly not atomic :)

Atomic patching requires creating a clone (jiff.clone). We could make that the default behavior of jiff.patch, and provide an opt-in, mutating version (jiff.patchInPlace or somesuch), that people can opt into if they want to avoid the clone hit.

Improper patch creation when changing an array to an object

First off, thanks for this wonderful library! I've written an event store which uses it and I've encountered the following behavior which I believe to be a bug:

var a = {
  "stuff": ['x']
};

var b = {
  "stuff": {
    "a": "x"
  }
};

var patch = jiff.diff(a,b);

results in a patch like this:

[
  {
    "op": "add"
    "path": "/stuff/a"
    "value": "x"
  }
  {
    "op": "test"
    "path": "/stuff/0"
    "value": "x"
  }
  {
    "op": "remove"
    "path": "/stuff/0"
  }
]

This patch cannot be applied however because the path "/stuff/a" isn't valid for an array:

c = jiff.patch(patch, a);  // SyntaxError: invalid array index a

The patch I expected to see is:

[
  {
    "op": "replace"
    "path": "/stuff"
    "value": {
      "a": "x"
    }
  }
]

Am I way off base here?

Extend commutation to tree (object) paths

#16 adds commutation for patches sharing a common array ancestor, or in the same array. It doesn't support objects yet. Need to add that.

Hash function doesn't appear to be working

I can't seem to get the diff function to use the hash function that I'm passing in. I wanted to override the comparison of dates so that equivalent dates do not produce a patch. Below is the code that I've been trying.

var jiff = require('jiff');
var obj1 = {
    myDate: new Date('2019-1-1'),
    hello: 8
}
var obj2 = {
    myDate: new Date('2019-1-1'),
    hello: 9
}

const hashFunction = (x) => {
  if (x instanceof Date) {
    return x.getTime();
  } else if (Array.isArray(x) || typeof(x) === "object") {
    return JSON.stringify(x);
  } else {
    return x;
  }
}

console.log(jiff.diff(obj1, obj2, hashFunction ));

This always prints "myDate" as part of the patch and putting a break point inside the hash function never hits.

I've tried passing the hash function in this way and also in the options object with no luck. Am I misunderstanding the docs or what the hash function is being used for?

Add patch commutation

This is the approach used by modern vcs, like git, darcs, etc. to dealing with diverging patch scenarios. There are other techniques, but this could be a very useful one for use cases like synchronization.

Ability to provide a helper for patch test

I have a system, where I create patches for Mongoose documents. When I have nested documents, with sub-documents, and want to apply a patch the test fails, caused by the sub-document _id not being a simple string.

Generate diffs that comply with inversion constraints

See #9

Remove fails if the value for the key is undefined.

A { a: undefined }
B {}
patch = diff(A,B) (results in 'remove a')
patchInPlace(patch, A)

fails with "path does not exist"

// key must exist for remove
if(notFound(pointer) || pointer.target[pointer.key] === void 0) {
	throw new InvalidPatchOperationError('path does not exist ' + change.path);
}

The cause is the check for pointer.target[pointer.key] not being undefined.
The key needs to be present, but if the value is undefined that shouldn't prevent a removal.

Object Array Matching

I'm trying to find a way to reduce unnecessary array patches and I'm curious if there is a solution for this scenario. I have items that contain an array of objects like this:

{
    "things": [
        {
            "id": "123",
            "foo": "jiff",
            "bar": "jiff"
        },
        {
            "id": "abc",
            "foo": "jiff",
            "bar": "jiff"
        }
    ]
}

Currently when I diff changes to this type of structure I end up with add and remove operations for entire "things" objects even when only a single property in the object changes (e.g. things[0].foo changes but the other properties remain constant).

I understand why this happens but is there a way to provide a hint to jiff so that it could match array objects on their "id" value? Or is that something that a feature that you would consider including?

Wrong Output when something is added at front and deleted in between

const oldValue = [
    {
      Details: [{
        Amount: 100,
        CurrencyCode: 'USD',
        Quantity: 2,
        RegisteredPrice: 20,
        id: 10,
      }],
      Type: 'Variable',
      Product: 'NaN',
      id: 10,
    },
    {
      Details: [{
        Amount: 110,
        CurrencyCode: 'USD',
        Quantity: 16,
        RegisteredPrice: 20,
        id: 20,
      }],
      Type: 'Type-11',
      Product: 'Product-11',
      id: 20,
    },
    {
      Details: [{
        Amount: 120,
        CurrencyCode: 'USD',
        Quantity: 17,
        RegisteredPrice: 20,
        id: 30,
      }],
      Type: 'Type-12',
      Product: 'Product-12',
      id: 30,
    },
  ];
  const newValue = [
    {
      Details: [{
        Amount: 100,
        CurrencyCode: 'USD',
        Quantity: 2,
        RegisteredPrice: 20,
        id: 40,
      }],
      Type: 'Variable',
      Product: 'NaN',
      id: 40,
    },
    {
      Details: [{
        Amount: 100,
        CurrencyCode: 'USD',
        Quantity: 2,
        RegisteredPrice: 20,
        id: 10,
      }],
      Type: 'Variable',
      Product: 'NaN',
      id: 10,
    },
    {
      Details: [{
        Amount: 120,
        CurrencyCode: 'USD',
        Quantity: 17,
        RegisteredPrice: 20,
        id: 30,
      }],
      Type: 'Type-12',
      Product: 'Product-12',
      id: 30,
    },
  ];
function hashFn(x) {
    return x.id;
}
console.log(jiff.diff(oldValue,newValue,{hash: hashFn,invertible:false}));

Output:
[ { op: 'add', path: '/0', value: { Details: [Array], Type: 'Variable', Product: 'NaN', id: 40 }, context: undefined }, { op: 'remove', path: '/2', context: undefined } ]

Expected:
[ { op: 'add', path: '/0', value: { Details: [Array], Type: 'Variable', Product: 'NaN', id: 40 }, context: undefined }, { op: 'remove', path: '/1', context: undefined } ]

Array with objects causes weird (broken) patches

Comparing arrays with simple objects results in a weird broken patch.

import { diff } from 'jiff'

const $old = [{ id: 1 }]
const $new = [{ id: 2 }]
const $patch = diff($old, $new)
console.log($patch)

Expected outcome:

[
  { op: "test", path: "/0/id", value: 1 },
  { op: "replace", path: "/0/id", value: 2 },
]

Actual outcome:

[
  { op: "add", path: "/0", value: { id: 2 } },
  { op: "test", path: "/1", value: { id: 1 } },
  { op: "remove", path: "/1" },
]

I tried with a custom hasher method from another issue, but this didn't help.

Update: I switched to https://github.com/Starcounter-Jack/JSON-Patch which does exactly what I expected above.

Use these tests

This json-patch-tests repo looks like it contains lots of test cases based on the RFC. Let's use them.

String/Number object clone results in strange patch results

let patch:jiff.JSONPatch = [{
    'op': 'add',
    'path': '/test/321/prop1',
    'value': new String('value'),
    'context': { id : '321' }
  }]
  let doc = {test: [{
    id: '321',
    prop1: 'old_value'
  }]}
  let result = jiff.patch(patch, doc, {
    findContext: (index, array, context) => {
      return array.findIndex((value, index, array) => value["id"] === context.id);
    }
  })

which results in

{
  "test":[{
    "id":"321",
    "prop1":{
      "0":"v",
      "1":"a",
      "2":"l",
      "3":"u",
      "4":"e"
    }
  }]
}"

ideally the clone logic would have a special case for String objects if possible resulting in

{
  "test":[{
    "id":"321",
    "prop1":"value"
  }]
}

something like the following in clone could work

function clone(x) {
	if(x == null || typeof x !== 'object' || x instanceof String || x instanceof Number) {
		return x;
	}

	if(Array.isArray(x)) {
		return cloneArray(x);
	}

	return cloneObject(x);
}

Add option for extra `test` operations

Currently, jiff generates extra test operations to enable patch inversion. The test ops also provide an extra level of safety even without inversion: they make sure you're not applying a patch to a document that has diverged far from the version from which the patch was generated.

However, some folks may not need inversion, and thus may want to opt out of the extra test ops in order to get smaller patches.

See #26

Large diffs

I am changing one property in a larger set of JSON and the diff is just as large as the original JSON. Here is the original JSON:

{"images":[{"id":"bdb71c44-f980-499b-abf5-5aed88a04625","entries":[{"templateProperties":{"content":"Other","contentURI":"https://beta.familysearch.org/indexing-service/template/templates/record?name=record.template.431","reviewState":"agree"},"fields":[{"label":"RELATIONSHIP_2","content":" Brother-in-Law","contentURI":"","reviewState":"agree","previousContent":""},{"label":"RELATIVE_GN","content":"BOB","contentURI":"","reviewState":"agree","previousContent":""},{"label":"RELATIVE_SURN","content":"JONESS","contentURI":"","reviewState":"agree","previousContent":""},{"label":"RELATIVE_TITLE_TERMS","content":"","contentURI":"","reviewState":"agree","previousContent":""}]},{"templateProperties":{"content":"","contentURI":""},"fields":[]}],"header":{"fields":[{"label":"Image Type","content":"","previousContent":"","reviewState":"agree"},{"label":"Duplicate Image","content":"","previousContent":"","reviewState":"agree"},{"label":"2ndheader","content":"asdf","previousContent":"","reviewState":"agree"}]}},{"id":"80a2b121-87b6-46d6-8ea6-c5fe971943f3","entries":[{"templateProperties":{"content":"","contentURI":""},"fields":[]}],"header":{"fields":[{"label":"Image Type","content":"","previousContent":"","reviewState":"agree"},{"label":"Duplicate Image","content":"","previousContent":"","reviewState":"agree"},{"label":"2ndheader","content":"","previousContent":"","reviewState":"agree"}]}}],"userId":"28e8e455-e070-4fa1-b6f7-35098f5ae18d"}

Updated JSON:

{"images":[{"id":"bdb71c44-f980-499b-abf5-5aed88a04625","entries":[{"templateProperties":{"content":"Other","contentURI":"https://beta.familysearch.org/indexing-service/template/templates/record?name=record.template.431","reviewState":"agree"},"fields":[{"label":"RELATIONSHIP_2","content":" Brother-in-Law","contentURI":"","reviewState":"agree","previousContent":""},{"label":"RELATIVE_GN","content":"BOB","contentURI":"","reviewState":"agree","previousContent":""},{"label":"RELATIVE_SURN","content":"JONESS","contentURI":"","reviewState":"agree","previousContent":""},{"label":"RELATIVE_TITLE_TERMS","content":"","contentURI":"","reviewState":"agree","previousContent":""}]},{"templateProperties":{"content":"","contentURI":""},"fields":[]}],"header":{"fields":[{"label":"Image Type","content":"","previousContent":"","reviewState":"agree"},{"label":"Duplicate Image","content":"","previousContent":"","reviewState":"agree"},{"label":"2ndheader","content":"asdf","previousContent":"","reviewState":"agree"}]}},{"id":"80a2b121-87b6-46d6-8ea6-c5fe971943f3","entries":[{"templateProperties":{"content":"","contentURI":""},"fields":[]}],"header":{"fields":[{"label":"Image Type","content":"","previousContent":"","reviewState":"agree"},{"label":"Duplicate Image","content":"","previousContent":"","reviewState":"agree"},{"label":"2ndheader","content":"","previousContent":"","reviewState":"agree"}]}}],"userId":"28e8e455-e070-4fa1-b6f7-35098f5ae18d"}

The DIFF:

[{"op":"add","path":"/images/0","value":{"id":"bdb71c44-f980-499b-abf5-5aed88a04625","entries":[{"templateProperties":{"content":"Other","contentURI":"https://beta.familysearch.org/indexing-service/template/templates/record?name=record.template.431","reviewState":"agree"},"fields":[{"label":"RELATIONSHIP_2","content":" Brother-in-Law","contentURI":"","reviewState":"agree","previousContent":""},{"label":"RELATIVE_GN","content":"BOB","contentURI":"","reviewState":"agree","previousContent":""},{"label":"RELATIVE_SURN","content":"JONES","contentURI":"","reviewState":"agree","previousContent":""},{"label":"RELATIVE_TITLE_TERMS","content":"","contentURI":"","reviewState":"agree","previousContent":""}]},{"templateProperties":{"content":"","contentURI":""},"fields":[]}],"header":{"fields":[{"label":"Image Type","content":"","previousContent":"","reviewState":"agree"},{"label":"Duplicate Image","content":"","previousContent":"","reviewState":"agree"},{"label":"2ndheader","content":"asdf","previousContent":"","reviewState":"agree"}]}}},{"op":"test","path":"/images/1","value":{"id":"bdb71c44-f980-499b-abf5-5aed88a04625","entries":[{"templateProperties":{"content":"Other","contentURI":"https://beta.familysearch.org/indexing-service/template/templates/record?name=record.template.431","reviewState":"agree"},"fields":[{"label":"RELATIONSHIP_2","content":" Brother-in-Law","contentURI":"","reviewState":"agree","previousContent":""},{"label":"RELATIVE_GN","content":"BOB","contentURI":"","reviewState":"agree","previousContent":""},{"label":"RELATIVE_SURN","content":"JONESS","contentURI":"","reviewState":"agree","previousContent":""},{"label":"RELATIVE_TITLE_TERMS","content":"","contentURI":"","reviewState":"agree","previousContent":""}]},{"templateProperties":{"content":"","contentURI":""},"fields":[]}],"header":{"fields":[{"label":"Image Type","content":"","previousContent":"","reviewState":"agree"},{"label":"Duplicate Image","content":"","previousContent":"","reviewState":"agree"},{"label":"2ndheader","content":"asdf","previousContent":"","reviewState":"agree"}]}}},{"op":"remove","path":"/images/1"}]

not have AMD browser version

not have AMD browser version

Validate array indices before calling parseInt

See json-patch/json-patch-tests#5 and here in the JSON Pointer RFC. Numeric array indexes have a much tighter format than lenient parseInt allows. We may need to check via regex before parsing.

Diff of two equal objects is not empty

jiff.diff({
  "a": {
    "b": {
      "c": [ ["a"], ["b"], ["c"] ]
    }
  }
}, {
  "a": {
    "b": {
      "c": [ ["a"], ["b"], ["c"] ]
    }
  }
});

Produces the following patch:

[ { op: 'add',
    path: '/a/b/c/0',
    value: [ 'a' ],
    context: undefined },
  { op: 'add',
    path: '/a/b/c/1',
    value: [ 'b' ],
    context: undefined },
  { op: 'add',
    path: '/a/b/c/2',
    value: [ 'c' ],
    context: undefined },
  { op: 'test',
    path: '/a/b/c/3',
    value: [ 'a' ],
    context: undefined },
  { op: 'remove', path: '/a/b/c/3', context: undefined },
  { op: 'test',
    path: '/a/b/c/3',
    value: [ 'b' ],
    context: undefined },
  { op: 'remove', path: '/a/b/c/3', context: undefined },
  { op: 'test',
    path: '/a/b/c/3',
    value: [ 'c' ],
    context: undefined },
  { op: 'remove', path: '/a/b/c/3', context: undefined } ]

Which is correct, in the sense that applying the patch will yield the correct result; but not efficient, as the patch could simply be empty.