Add patch inversion

[briancavalier]

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

[briancavalier]

Potential issues:

1. remove cannot be inverted. As defined in the RFC, remove does not carry any information about what is removed, only from where it should be removed. So, without the original document context, or a value providing the actual what, the remove operation itself cannot be transformed correctly into an add.
2. Since remove cannot be inverted, neither can replace, since replace is exactly a remove followed by an add. Again, the context of what was replaced is needed.
3. test can be inverted, but it's non-obvious: inverting a patch means reversing the order of operations in the patch. By doing that, test operations become tests on post-conditions, rather than pre-conditions. For example, the following patch tests the pre-condition that the value at /foo is "bar" before replacing it with "baz":

[{ "op":"test", "path":"/foo", "value":"bar" }, { "op":"replace", "path":"/foo", "value":"baz"}]

Inverting the patch yields a post-condition test that "baz" was indeed replaced with "bar". Note that the test operation itself is unchanged:

[{ "op":"replace", "path":"/foo", "value":"bar"}, { "op":"test", "path":"/foo", "value":"bar" }]

Of course, for the purposes of that example, I've ignored the fact that replace can't be inverted :)

[briancavalier]

Hmmm, perhaps test is the key. If every remove or replace operation were preceded by a test which tests that the path that is about to be removed/replaced has the expected value, then that value can be used to generate the inverted add or replace.

For example, this patch cannot be inverted:

[{ "op":"remove", "path":"/foo"}]

However, by adding a test:

[{ "op":"test", "path":"/foo", "value":"bar" }, { "op":"remove", "path":"/foo"}]

We now know the value that is being removed: if the value of /foo is not "bar" then the patch will fail. Thus, the value must have been "bar". Inverting the patch should yield:

[{ "op":"add", "path":"/foo", "value":"bar"}, { "op":"test", "path":"/foo", "value":"bar" }]

which adds the previously removed "bar", and then tests that it was added as a post-condition. It's possible that we can leave out the post-condition test, but that means when inverting all add and replace operations, we must insert test operations to record the value.

I think we would have to put that responsibility on the caller by saying that patches containing remove and replace operations are only invertible if they contain the appropriate accompanying test operations.

[briancavalier]

Copy is also a problem.

First, an important invariant is that inverse(inverse(p)) yields a patch that is of "equivalent effect" as p. It doesn't have to be identical, but patch(p, json) === patch(inverse(inverse(p)), json) does need to hold.

The obvious inverse of copy is remove. However, the obvious inverse of remove is add, but copy is also an inverse of remove! Thus remove has 2 possible inverses.

One suggestion by @unscriptable is to augment patch operations with an optional inverse property. So, when inverting a copy, we could produce:

{ op: 'remove', from: '/todos/2', inverse: { op: 'copy', from: '/todos/1', path: '/todos/2 }' }

Where the inverse property contains the original copy operation. Then, when inverting again, we can look for the inverse property and use it if it's there. For any remove that doesn't have an inverse property, we just assume that we can invert it to an add (given the test constraint above).

[briancavalier]

In the near term, here's what I'm gonna do:

1. When a replace or remove is encountered, it must be preceded by an appropriate test, otherwise throw.
2. When an add or replace is encountered, generate the appropriate test operation, in addition to a remove or replace, as part of the inverse.
3. When a copy is encountered, throw, since a copy inverse could not, itself, be inverted.
4. When a test is encountered that is not associated with a replace or remove, add it verbatim to the inverse. Not sure what else to do here, and not even sure we would ever actually encounter such a thing.

[aaronshaf]

This sounds like a great idea!

[briancavalier]

Cool, thanks @aaronshaf. I've implemented a proof-of-concept of the inverse strategy above, and so far it's working well. I need to write more tests for it, but I'm hoping to have it committed tomorrow.

[briancavalier]

Initial version of patch inversion in #14.

[briancavalier]

Patch inverses landed in #14. We may find out that we have to amend the format for other types of inverses (or even just for copy), but we can address that in a new issue.