Add patch commutation

[briancavalier]

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.

[briancavalier]

See #9 and http://en.wikibooks.org/wiki/Understanding_Darcs/Patch_theory

[briancavalier]

And see http://byorgey.wordpress.com/2008/02/13/patch-theory-part-ii-some-basics/

[aaronshaf]

Thanks for the reading materials. I am trying to digest them.

I assume patch commutation requires support for inverse on all operation types, since (as I poorly understand patch commutation), you are potentially required to undo past operations and then reorder them?

Edit: Nevermind, I'm reading more and answered my own question.

[aaronshaf]

Of interest: https://github.com/dominictarr/crdt

[briancavalier]

@aaronshaf commutation in and of itself doesn't require inverses. However, merging and rebasing algorithms that rely on patch commutation do require inverses--pretty much exactly what you said:

you are potentially required to undo past operations and then reorder them

[briancavalier]

There a basic, but incomplete implementation in the add-commutation branch. It definitely isn't complete, but it exposed more areas where we need to do some thinking. I had to invent a noop patch operation to commute some things :(

[briancavalier]

And now I'm thinking that everywhere I used a noop, the right thing may be to fail loudly instead ... gonna stew on that a bit.

[briancavalier]

Arrays are working. See #17 for objects.