Great talk! I look forward to diving into "Interleaving anomalies in collaborative text editors" to see how Kleppmann et al fixed the RGA interleaving issue.

The section on moving items in a list makes my mind jump to Causal Trees (≈RGA). The problem here is that a) we need the concept of a list bucket or slot, and b) we also need to preserve the sequential integrity of runs of items as in text editing. In CT/RGA, each letter/item is simultaneously a list bucket and its contents. I wonder if this problem could be solved by adding a "reanchor" op that moves the "contents" (and some/all children) of a letter op to the "bucket" of another letter op?

Each reanchor op would have the job of "moving" a subtree of text to a new parent bucket. (Under the hood, the subtree would obviously remain topologically unchanged for convergence purposes, but the reanchor op would inform how the tree is parsed and turned into a user-visible list or string.) First, the reanchor op would need to reference the start and end letter/item ops in a given subtree; and second, the reanchor op would need to reference the letter/item op into whose bucket the subtree contents will be moved. If the set of subtrees for a range of text/items contains multiple independent subtrees, they would each need their own reanchor op. Concurrent moves of the same subtree would be resolved as LWW, similar to the Kleppmann proposal.

Let's say you have a graph for string "ABCD" that looks roughly like this, sans metadata:

        +---+
        | A |
        ++-++
         | |
      v--+ +--v
    +---+   +---+
    | B |   | C |
    +---+   +-+-+
              |
              v
            +-+-+
            | D |
            +---+

If you wanted to move "CD" after "A", you would add the following op:

        +---+
        | A +<---------+
        ++-++          |
         | |           |
      v--+ +--v        |
    +---+   +---+      |
    | B |   | C +<---+ |
    +---+   +-+-+    | |
              |      | |
              v      | |
            +-+-+   ++-++
            | D +<--+ m |
            +---+   +---+

"m" references "C" and "D" as the subtree range, and "A" as the target bucket. The string would render as "ACDB".

We can get cycles with this scheme, but as far as strings or lists are concerned, this doesn't actually matter, since the parent references aren't reflected in the output (as they would be with an explicit tree data structure). If, concurrently to this, another device wanted to move "A" after "C", the merged graph would look like this:

    +---+   +---+
    | m +-->+ A +<---------+
    +-+-+   ++-++          |
      |      | |           |
      |   v--+ +--v        |
      | +---+   +---+      |
      | | B |   | C +<---+ |
      | +---+   +-+-+    | |
      +---------^ |      | |
                  v      | |
                +-+-+   ++-++
                | D +<--+ m |
                +---+   +---+

How does this get resolved? Well, we can simply read this as "move the contents of 'A' to the bucket for 'C', and move the contents of subtree 'C' through 'D' to the bucket for 'A'." The string would consequently render as "CDBA", as we would expect.

This is just a sketch, not sure if it would actually work in practice. Pain points are a) moving multiple subtrees in a somewhat atomic way (when the range to be moved covers more than a single run of items), b) sane results when overlapping ranges are moved concurrently, c) moving items to a bucket whose contents had already been moved before, and d) parsing performance, especially given the fact that we'll now have ops (and their children) whose contents might end up in arbitrary places in the output string or list. Might just end up with a slow, confusing, and labyrinthine data structure.

There's also the question of intent: does the user want to move a range of items to the slot currently occupied by a different item, or do they want to move that range to the right of that item? Lists of notes will want the former, while strings will usually want the latter. Perhaps the reanchor op could explicitly differentiate between these two cases.