search

automerge / automerge-classic

A JSON-like data structure (a CRDT) that can be modified concurrently by different users, and merged again automatically.
http://automerge.org/
MIT License
14.75k stars 466 forks source link

Implement the new sequence patch format, fixes #311 #328

Closed alexjg closed 3 years ago

alexjg commented 3 years ago

This is a first shot at implementing the new sequence patch format outlined in #311. It's mostly working with the exception of the Observable API. I need to spend some time figuring that out but I wanted to get some eyes on this first.

There is one outstanding question I have which relates to the value of the pred attribute for multiOp delete operations. Consider this operation:

{
  obj: listId, 
  action: 'del', 
  elemId: '1@xxx', 
  multiOp: 2,
  insert: false,
}

In order for this to work we need to specify the predecessor operations for each element being overwritten. The approach I've gone for in this patch is to flatten the predecessor IDs for the whole set of deleted list elements into one pred array and attached it to the op. This works but it feels clumsy and belies the intent of this protocol change - which is to reduce the size of these operations - as we have to include at least one predecessor ID for every deleted element. Is there a better way? Have I misunderstood the use of the pred attribute in the protocol?

ept commented 3 years ago

Hi @alexjg, I'm now working on this (I have some work-in-progress commits on this branch that I've not yet pushed). Could you hold off on force-pushing it please, since it means I have to rebase my stuff too?

alexjg commented 3 years ago

Ah apologies, I didn't realise you were working on it. I've just been keeping it up to date with the work being merged into performance.

ept commented 3 years ago

No worries, that makes sense and I should have said I was working on it! Anyway, sorry for the long delay on this, and I will have more news soon.

ept commented 3 years ago

Okay, I have finally finished with this. Sorry it has taken so long, and thank you @alexjg for doing the original work. I have found and fixed a number of bugs, and added tests for them. Most importantly, in order to group several insertions into a multi-insert they must all have sequential elemIds (i.e. the actor parts of the elemIds are all the same, and the counter part increments by 1 for each element), and in order to group several deletions they must have sequential elemIds and sequential preds. I think the code now ensures this.

I expect automerge/automerge-rs#88 will need updating correspondingly. @alexjg @orionz @jeffa5 could one of you help me with this please?

I am going to go ahead and merge this because folks are desperate to get a 1.0-preview release on npm; apologies for not waiting for the Rust implementation to reach parity. We can follow up with a release of the wasm backend when the equivalent of this PR is also finished on the Rust side.