search

json-patch / json-patch2

A possibile revision to the JSON-Patch format
44 stars 0 forks source link

Patching shared arrays is tricky business #5

Open briancavalier opened 10 years ago

briancavalier commented 10 years ago

I don't really know if it should be JSON Patch's goal to support that kind of scenario, but I've definitely run into it. So far, on client-server systems where multiple users might change data in the same collection, I've considered giving up on arrays in favor of objects, which means all but abandoning things like Java+JPA+Lists in server code in favor of Set or Map.

However, if the Sets/Maps are keyed on ids, which they often are, this raises the problem of server-assigned ids: how can a client submit a patch to add an item where the object key is supposed to be an id that needs to be assigned by the server?

Other diff/patch systems, ie typical text diff/patch, provide additional context around each change. They do this so that the patching algorithm can be more resilient, applying patches to a document, even if the document has changed, as long as the patch doesn't actually conflict.

Patching the lines of a text file is not unlike patching arrays with JSON Patch. If you have multiple parties patching the same array, you either have to lock the array so that only one party at a time can submit patches (which must also be sent to all parties involved before they can start submitting patches, so that their array indices are correct!), or you have to use a smart patching algorithm. The latter is what all modern version control systems do (they apply other techniques as well, such as patch commutation) to avoid locking, and merge without human intervention as often as possible.

To support some scenarios, we've started implementing patch commutation, but using it effectively requires patch inversion (which is also tricky) and keeping a history of patches, whereas contextual patching requires neither of those.

There's always the option of peppering your patches with test ops and having them fail often, but it really seems like we can do better, given some of the interesting things that other patching systems are capable of.

So, I just wanted to start the discussion and see what everyone's thoughts are on smart/contextual patching, patch commutation and algebra, and on approaches for shared arrays in general.

mitar commented 5 years ago

I think such computations you are describing here are probably at the higher level than the patch format. You are using an example of plan text diff, which is just a patch how to represent which lines got changed and how. But the algorithm how to use that patch to merge it in is part of git (or some other tool), when you are using git. Not part of the patch itself.

So yes, additional context would be useful, but that might just be a particular extension. For example, braid is trying to standardize that context information, and it seems it is mostly just needed to have the version of the state at which patch should arrive, and what are parent state versions which are an input to patching.

So, in short, I think that context depends on the algorithm to use for resolving patch conflicts, but some standard ones might be possible to construct. But all of that could be a different standard and not part of the JSON patch itself. Maybe JSON patch could just reserve some keywords or explicitly allow adding more fields to the patch payload. The problem is that JSON is an array, Maybe we should make it an object with one property for steps of the patch, so:

{
  "context": <value>,
  "steps": [
    ...
  ]
}

This would make it much easier to extend. And add some global metadata to the whole set of steps. While additional metadata could go into each step as well.