search

mikolalysenko / patcher.js

JSON diffing and patching library
Other
113 stars 7 forks source link

JSON Patch? #4

Open NV opened 12 years ago

NV commented 12 years ago

Have you considered using JSON Patch? It’s more efficient when it comes to patch size.

> require('patcher').computePatch([1,2,3,4,5], [2,3,4,5])
{ '0': 2,
  '1': 3,
  '2': 4,
  '3': 5,
  '$r': 4 }

JSON Patch using remove operation:

{ "remove": "0" }

It also has handy add, move, and replace operations.

https://github.com/bruth/jsonpatch-js is a partial implementation (applies patches, doesn’t yet generate them).

mikolalysenko commented 12 years ago

I think that implementing remove like that would be tricky to do, but if JSON patch can make it work, then that is great!

I have not done much work on this project (or any hobby coding in general) lately since I have been busy with my PhD thesis. One thing that I had considered, but decided against for technical reasons, was using dynamic programming to merge arrays via a series of splice operations. This could easily be done in quadratic time for arrays of primitive types, which would be good for small to medium size arrays that undergo lots of dynamic insertions/updates. Unfortunately, the problem comes in when dealing with either large arrays -- where the overhead of storing the table quickly becomes too large -- or more pathologically when dealing with arrays of objects.

In the end, this feature did not matter much for the application I was working (which was a videogame). In my case, all the arrays were typically small fixed size vectors of floating point numbers, and component-wise diffing turned out to be the `right' thing to do in that the patches were typically quite small (basically an index + coordinate value). Of course, I could easily see wanting this sort of behavior in a different setting, where for example you might be storing queues in those arrays instead.

I think that there probably isn't going to be a one-size-fits all solution to this problem, and that without bringing in big guns like stronger schema/typing systems it will be hard to quickly generate really good patches for arrays that take advantage of all these special cases.

That said, I am fully willing to admit that there is probably quite a bit of room for improvement in the patches that patcher.js spits out. If you have some ideas and want to take a crack at adding them yourself, then by all means give it a try and submit a pull request!