Sequence replace: Automerge vs. other DDSes

[yann-achard]

Hello. I am testing some of the corner case resolutions of various DDSes and Automerge seems to behave unexpectedly in this specific case:

it('Insert at index vs replace [index]', () => { // <= This test passes but maybe should not?
    s1 = Automerge.change(Automerge.init(), doc => doc.a = ['a'])
    s2 = Automerge.merge(Automerge.init(), s1)
    s1 = Automerge.change(s1, doc => {
            doc.a.deleteAt(0, 1)
            doc.a.insertAt(0, '1')
        }
    )
    s2 = Automerge.change(s2, doc => doc.a.insertAt(0, '2'))
    s1 = Automerge.merge(s1, s2)
    assert.deepStrictEqual(s1.a.join(''), '12') // Would have expected either '21' or a non-deterministic output.
})

Other DDSes I have tried this on deterministically produce the merge state ['2', '1']. Those are:

• Fluid sequence
• text-unicode (for both "left" and "right" tie-braking)
• OT-JSON1 (for both "left" and "right" tie-braking)

Is the outcome in Automerge in fact non-deterministic and I just haven't managed to trigger the other outcome (is there a reliable way to do that?)?

Am I wrong in expecting the outcome to be ['2', '1'] for Automerge?

Thank you!

[DUG-nick]

Hey,

it is non-deterministic, at least going by the documentation Conflicting Changes.

It references your case directly

If users concurrently insert or delete items in a list (or characters in a text document), Automerge preserves all the insertions and deletions. If two users concurrently insert at the same position, Automerge will arbitrarily place one of the insertions first and the other second, while ensuring that the final order is the same on all nodes.

Kind regards, Nick

[ept]

Hi @yann-achard, in general it's non-deterministic, but in this particular example it happens to be deterministic. The two concurrent insertions of '1' and '2' at the beginning of the array are ordered by the operation IDs of those insertion operations. Operation IDs consist of a per-actor counter followed by the ID of the actor that generated them. In this case, the operation doc.a.deleteAt(0, 1) will have the same counter value as the operation doc.a.insertAt(0, '2'), but the operation doc.a.insertAt(0, '1') will have a higher counter value because it is preceded by a delete operation. Therefore, the insertion of '1' (with the higher counter) will always be ordered before the insertion of '2' (with the lower counter).

If you remove the line doc.a.deleteAt(0, 1), or if you add the same delete operation before doc.a.insertAt(0, '2'), then the two insertion operations should have the same counter, and thus the merged outcome should become nondeterministic because they are now being ordered by actorId.

[yann-achard]

Thank you @ept and @DUG-nick. I was able to reproduce the nondeterminism by adding an operation before doc.a.insertAt(0, '2') as described.