Document doesn't converge when using `Array.MoveAfter`

[chacha912]

What happened:

When using moveAfter with the reference element being moved, the document does not converge as expected.

What you expected to happen:

The document should converge to [2,1,3,4,0].

How to reproduce it (as minimally and precisely as possible):

Execute the following test code in the yorkie-js-sdk:

it('Can handle concurrent moveAfter', async function ({ task }) {
  type TestDoc = { k1: JSONArray<number> };
  await withTwoClientsAndDocuments<TestDoc>(async (c1, d1, c2, d2) => {
    d1.update((root) => {
      root.k1 = [0, 1, 2, 3, 4];
      assert.equal('{"k1":[0,1,2,3,4]}', root.toJSON!());
    });
    await c1.sync();
    await c2.sync();
    assert.equal(d1.toJSON!(), d2.toJSON!());

    d1.update((root) => {
      const prev = root.k1.getElementByIndex!(0);
      const item = root.k1.getElementByIndex!(2);
      root.k1.moveAfter!(prev.getID!(), item.getID!());
      assert.equal('{"k1":[0,2,1,3,4]}', root.toJSON!());
    });

    d2.update((root) => {
      const prev = root.k1.getElementByIndex!(4);
      const item = root.k1.getElementByIndex!(0);
      root.k1.moveAfter!(prev.getID!(), item.getID!());
      assert.equal('{"k1":[1,2,3,4,0]}', root.toJSON!());
    });

    await c1.sync();
    await c2.sync();
    await c1.sync();
    // d1 /= d2 
    assert.equal(d1.toSortedJSON(), `{"k1":[2,1,3,4,0]}`);
    assert.equal(d2.toSortedJSON(), `{"k1":[1,3,4,0,2]}`);
  }, task.name);
});

Anything else we need to know?:

In cases where the same node is moved or when elements are moved to the same position, the operation is commutative by comparing movedAt and executedAt. However, when the reference element is moved, a different approach may be necessary for convergence. (Refer to: Why a move operation is hard)

Environment:

• Operating system:
• Browser and version:
• Yorkie version (use yorkie version): v0.4.8
• Yorkie JS SDK version: v0.4.8

[cloneot]

The same problem occurs between moveAfter and insertAfter. When using insertAfter with the reference element being moved, the document does not converge as expected.

Example:

• Initial: root.list = [0, 1, 2]
• Client A: root.list.moveAfter(0, 2) // root.list = [0,2,1]
• Client B: root.list.insertAfter(2, 3) // root.list = [0,1,2,3]
• Result: [0,2,3,1] or [0,2,1,3]

Test code in the yorkie/test/integration/array_test.go:

func TestArrayMoveInsert(t *testing.T) {
    clients := activeClients(t, 2)
    c1, c2 := clients[0], clients[1]
    defer deactivateAndCloseClients(t, clients)

    t.Run("concurrent array move/insert simple test (ii)", func(t *testing.T) {
        ctx := context.Background()
        d1 := document.New(helper.TestDocKey(t))
        err := c1.Attach(ctx, d1)
        assert.NoError(t, err)

        d2 := document.New(helper.TestDocKey(t))
        err = c2.Attach(ctx, d2)
        assert.NoError(t, err)

        assert.NoError(t, d1.Update(func(root *json.Object, p *presence.Presence) error {
            root.SetNewArray("k1").AddInteger(0, 1, 2)
            assert.Equal(t, `{"k1":[0,1,2]}`, root.Marshal())
            return nil
        }, "add 0, 1, 2 by c1"))

        assert.NoError(t, c1.Sync(ctx))
        assert.NoError(t, c2.Sync(ctx))

        assert.NoError(t, d1.Update(func(root *json.Object, p *presence.Presence) error {
            next := root.GetArray("k1").Get(1)
            item := root.GetArray("k1").Get(2)

            root.GetArray("k1").MoveBefore(next.CreatedAt(), item.CreatedAt())
            assert.Equal(t, `{"k1":[0,2,1]}`, root.Marshal())
            return nil
        }, "move k1[2] before k1[1] by c1"))

        assert.NoError(t, d2.Update(func(root *json.Object, p *presence.Presence) error {
            root.GetArray("k1").InsertIntegerAfter(2, 3)
            assert.Equal(t, `{"k1":[0,1,2,3]}`, root.Marshal())
            return nil
        }, "insert 3 after k1[2] by c2"))

        syncClientsThenAssertEqual(t, []clientAndDocPair{{c1, d1}, {c2, d2}})
    })
}

[cloneot]

Loro's MovableList test code:

• It converges as intended
• run the test online: StackBlitz
  • move.prev vs move.target ✅
  • insert.prev vs move.target ✅
  • move.target vs move.target ✅