Moving elements in lists

Hello everyone,

Kevin and contributors - thanks so much for Yjs - it’s an impressive piece of kit!

I’m building a collaborative application where users can reorder nodes in an ordered tree. I’ve modeled the hierarchy as a Y.Map<Y.Array<string>> where the keys are node ids, and the values are the ids of that node’s children. (My move operation is a delete followed by an insert).

This works nicely except for moves. If two peers concurrently move a node to different destinations we end up with a dupe.

Martin Kleppmann has described the problem nicely in this paper/video.

Are there any known techniques or workarounds for dealing with moves in Yjs?

Many thanks,

Just to be clear–the hierarchy is modeled as Y.Map<string, Y.Array<string>>, correct? (Reading a Map with only one type in its type signature was tripping me up).

Correct. Consider the following tree:

countries
+--france
|  +--paris
+--spain
   +--madrid
   +--seville

That would be represented as follows in a Y.Map<string, Y.Array<string>> (using JSON syntax)

{
    "__ROOTS__": ["countries"], // convenience entry for quickly finding root(s)
    "countries": ["france", "spain"],
    "france": ["paris"],
    "paris": [],
    "spain": ["madrid", "seville"],
    "madrid": [],
    "seville": [],
}

The problem of moving items doesn’t require a model this complex though. Let’s consider reordering in a simple list (Y.Array<string>):

["wash floors", "get milk", "homeschooling"]

Peer A moves "wash floors" to index 1, while Peer B moves "wash floors" to index 2. Since the move operation doesn’t exist, they both delete the "wash floors" element, then insert it at the new index. When these operations are merged we end up with "wash floors" twice in the list.

My question is - can this kind of conflict be resolved in Yjs? If not, would this be possible to add?

According to Martin Kleppmann, a CRDT move operation can be implementd with a combination of a List CRDT (Y.Array in the case of Yjs), an AWSet and a LWWRegister. I’d love to contribute this, but I think I need to learn a lot more about CRDTs and the Yjs codebase before I’d be able to.

Anyone more able than me?

Btw here is the paper: https://martin.kleppmann.com/papers/list-move-papoc20.pdf

Hi @aslakhellesoy,

Moving element(s) is possible in any list CRDT, as Martin Kleppmann described. He just discusses a single approach, but there are probably more solutions that can be explored. My first idea was to use special move-items that will refer to a range (start;beginning) of items (In Yjs terms an item is an integrated list-CRDT operation that consists of a unique id, content(s), and a position (next item; previous item)). The moved items would be marked as moved and would refer to the move operation. In case of a concurrent move, a last writer wins algorithm is simply implemented by comparing the unique identifiers of the move items that overlap.

This would have the advantage that you can move ranges of text. It would even be possible to move text from one Y.Array to another Y.Array.

Here are some of my concerns:
• How would rich-text semantic (formatted text) work in combination with the ability to move text? It would probably expected that moved text retains the formatting attributes.
• Introducing moving semantics requires a new event system. Implementing an event system for just insert/delete with formatting attributes is already incredible difficult. How do you even express moving semantics in events?
• Moving semantics also affect other areas of Yjs. It will probably take a lot of effort to make it work with version histories.
• How do you even visualize moving semantics with, for example, ProseMirrors version history implementation.
• While your example example is absolutely reasonable, I think that moving semantics on text/arrays is not yet worth the effort. How would you even recognize moving of text in current text editors? They also only work with insert/delete semantics.
• If I’m going to implement moving semantics in Yjs, I also want to introduce copying semantics. This would allow us copy types from one type to another. Basically you should be able to do const user = ydoc.getMap('my-user'); ydoc.getMap('editor').set('currentUser', user). My idea is also that you would be able to use copy semantics to use Yjs to better organize data / replace Firestore / provide some kind of indexing ability.

I was just writing down my thoughts. I do want to have moving / copying semantics in Yjs eventually. But there is a lot of work to be done.

You can actually implement some kind of moving semantic yourself. You don’t need to have Yjs for that. It only gets complicated when you introduce copying ranges. Based on your second example you could do the following:

// Every item has a unique ID:
const data = [
  { content: "wash floors", id: "Xyz" },
  { content: "get milk", id: "gz3" },
  { content: "homeschooling", id: "39z" }
]

const yarray = ydoc.getArray('myfood')

/*
On every change you ensure that there are no duplicate ids.
This will ensure that content is not duplicated when a two clients move the same item at the same time.
The easiest implementation is to keep the last unique item and delete the rest:
 */
yarray.observe(event => {
  // temporary Set of all ids used in yarray
  const uniqueIds = new Set()
  const array = yarray.toArray()
  // bundle all changes in a transaction, so that only one event is fired
  yarray.doc.transact(() => {
    // delete from right to left so that deletions don't affect the current position
    for (let i = array.length - 1; i >= 0; i--) {
      const item = array[i]
      if (uniqueIds.has(item.id)) {
        // We already found this item, delete it
        yarray.delete(i, 1)
      } else {
       // This is the first time we found this item (the id is unique)
       uniqueIds.add(item.id)
      }
    }
  })
})

// Initialize content _after_ the above handler has been registered.
yarray.insert(0, data)

const moveItem = (yarray, from, to) => {
  yarray.doc.transact(() => {
    const item = yarray.get(from)
    yarray.delete(from)
    // we already deleted an item, we might need to adjust the position
    const adjustedPosition = from < to ? to - 1 : to
    yarray.insert(adjustedPosition, [item])
  })
}

// Now you can move items:

moveItem(yarray, 0, 2)

Thanks @dmonad for your detailed reply and the workaround. I had something like that in mind, and it’s reassuring to see your recommendation.