How to handle different paths when working with CRDTs (Yjs), when 2 changes happen concurrently?

Question

I'm currently trying to build a collaborative Drag&Drop HTML-Editor with Yjs. I'm using Node.js with JavaScript and jQuery. A node server (y-websocket) handles the distribution of events to other connected users.

The Data-Structure

I am representing my HTML as a mix of YArray and YMap, which are data-structures provided by Yjs.

It is simply an array containing maps. Those maps have another attribute called "children" which is another array containing maps.

Yjs uses LSEQ CRDTs to merge concurrent changes.

In the following example, we have a "h1"-tag, followed by a div that contains a "p"-tag as its child:

Example:

[
0:    {
      attributes: {class: "canvas-cmp-heading", contenteditable: "true"}
      children: []
      content: "This is a h1"
      dataID: "bga8npswu"
      parent: "canvas"
      tag: "h1"
      }

1:    {
      attributes: {class: "canvas-cmp-div", data-container: "true"}
      children: [
            0:    {
                  attributes: {class: "canvas-cmp sortable ", contenteditable: "true"}
                  children: []
                  content: "This is a paragraph"
                  dataID: "xtytr071u"
                  parent: "ozvmok37w"
                  }
                ]
       }
]

The Problem

Inserting and deleting works fine. However, problems arise when 2 users concurrently move different elements that are (or will be) in relation to each other. Since Yjs doesn't have a move function, we represent moving as "Copy, Delete and Insert"

Consider the following:

User 1 moves the paragraph into div2. At the same time, User 2 moves div2 into div1.

Here's a simple image explain what I mean.

Concurrent move

The outcome of this is the following:

[
     0: {
          attributes: {class: "canvas-cmp-div", data-container: "true"}
          dataID: "t4dyxn8oc"
          parent: "drd1og7yq"
          tag: "div"
          children: [
                      0: {
                           attributes: {class: "canvas-cmp-div", data-container:"true"}
                           children: []
                           dataID: "t6od980jf"
                           parent: "t4dyxn8oc"
                           tag: "div"
                         }
                          
                    ]
         }
]

The outcome above shows a div containing another div. This is excepted since LSEQ uses Last-Writer-Wins. This means paragraph will be lost.

The desired outcome should be the following:

[
     0: {
          attributes: {class: "canvas-cmp-div", data-container: "true"}
          dataID: "t4dyxn8oc"
          parent: "drd1og7yq"
          tag: "div"
          children: [
                      0: {
                           attributes: {class: "canvas-cmp-div", data-container:"true"}
                           dataID: "t6od980jf"
                           parent: "t4dyxn8oc"
                           tag: "div"
                           children: [
                                       0: {
                                       attributes: {class: "canvas-cmp-p", data-container:"true"}
                                       dataID: "d2edyhg42"
                                       parent: "t6od980jf"
                                       tag: "p"
                                       children: []
                                           }
                                     ]
                         }

                     ]
         }
]

The problem is the extra depth. The algorithm doesn't know that an extra depth must be added for the "p"-tag.

Here is what my nested function looks like:

 move_nested(el, event)
    {
        let dataID = el.attr('data-id')
        let index = el.index()

        let oldPath = this.getPathFromElement(el) // The path to the currently dragged element

        if (el.parent()[0] == event.target)
            return

        let newPath = this.getPathFromElement($(event.target)) // Path to where we want to drop it

        this.doc.transact(() =>
        {
            let sourceMap = this.mainArray
            let targetMap = this.mainArray.get(newPath.shift())

            while (oldPath.length - 1 > 0) //Get the parent-map of the dragged element
            {
                sourceMap = sourceMap.get(oldPath.shift()).get('children')
            }
            while (newPath.length > 0) //Get the target-map we drop the element into
            {
                targetMap = targetMap.get('children').get(newPath.shift())
            }

            let clone = sourceMap.get(oldPath[0]).clone() //Clone the map
            clone.set('parent', $(event.target).attr('data-id'))
            sourceMap.delete(oldPath.shift()) //Remove the old map from the old location
            targetMap.get('children').push([clone]) //Insert the cloned map to the target location
        })
    }

Any incoming updates are handled by the observeDeep function provided by Yjs.

 let docLoaded = false
 this.mainArray.observeDeep(events =>
 {
    if (!docLoaded)
    {
        const changes = events[0].changes.delta[0] ?? null
        if (changes)
           this.renderDoc(events[0].target, changes)

        docLoaded = true
    }
    else
    {
       for (const event of events)
       {
          const changes = event.changes
          this.renderChanges(changes)
       }
    }
})

My Idea

I came up with the idea of using a completely flat hierarchy instead of nested arrays.

For example:

[

0: { "p1", "parent":"div1" }

1: { "div1", "parent": null, "children": ["p1"] }

2: { "div2", "parent": null, "children": [] }
    
]   

div2 would update its parent to div1, p would update its parent to div2. This could theoretically work when 2 changes happen concurrently on different depths, since there is no new depth that needs to be created when moving things concurrently.

The problem here is when we transform the complete array back to HTML, how would I know which elements have to be created first. (We can't append a "p"-Tag to a div that does not yet exists). I don't want to run n-times through my array to get the right order. That seems inefficient when there are a lot of elements.

How could I tackle this?