Identifying removed item from patch diffs?

[skokenes]

We use SlateJS on top of an Automerge document for collaborative text editing. When remote changes are synced with our Automerge document, we use the patch.diffs to determine what changes were made and turn those into a list of Slate operations we can apply to our Slate editor to keep it in sync.

When text or objects are removed remotely, we get a RemoveEdit generated https://github.com/automerge/automerge/blob/main/%40types/automerge/index.d.ts#L301. The RemoveEdit tells us the index of the element to remove, which is enough to generate a Slate remove operation. However, it doesn't tell us the contents of the text or object removed. It would be useful to be able to get this information so that we can properly set up undo/redo stacks in Slate. With a local Slate delete operation for example, Slate records the text character deleted so that an inverse operation for inserting that character can be generated on redo.

Is there any way to use the current patch.diffs to determine what text or object was present at the specified index before deletion?

[ept]

Hi @skokenes, can you look at the previous document state (before you applied the patch — it should still be available since it's immutable) and work out the deleted value from there? If the patch just contains a single RemoveEdit you should be able to just look up the index in the old object. It gets more complicated if a patch contains a sequence of edits, since indexes later in the list of edits can be influenced by edits earlier in the list.

The Observable class contains some code that tries to match up the old and the new array indexes, but to be honest I'm not sure how correct it is. But perhaps it's a basis that you can start from.

[skokenes]

Yea, my problem is sequences of edits, so the indices are shifting

[ept]

An O(n^2) algorithm would be: for every RemoveEdit, scan over all the following edits in the list, and if their index is after the removal position, increase it by one. Likewise, for every addition, scan over the following edits and decrease by one if their index is after the insertion position. After all indexes have been rewritten in this way, they should point at the correct element in the old array. I think.

With some further cleverness it might be possible to reduce this to O(n) but I'm not sure off the top of my head.

[ept]

You can reduce it to O(n) if the edits appear in ascending order: in this case you know that for each edit in the list, all the subsequent edits must have the same or greater index. In this case, you can do a single iteration over the list of edits and keep an offset as you go along, adding that offset to each edit's index. For a remove edit you increase the offset by 1, for an insert you decrease the offset by 1. This is what's implemented here: https://github.com/automerge/automerge/blob/main/frontend/observable.js#L79-L94