Error in treePath for Remote Changes in tree.edit operation for concurrent edit

[raararaara]

What happened:
In the scenario of concurrent editing in tree.edit, there is an issue where the fromPath and toPath for remote change events related to section deletion are not returning correctly.

To illustrate further, let's consider the following situation:

initial: `<r><c><p><n>0123456</n></p></c></r>`

        |          <- client 2 cursor
  |         |      <- client 1 cursor
 0 1 2 3 4 5 6

Client 1 deletes the block "12345" and adds 'z'
Client 2 adds 'x' between '3' and '4'

The remote change received by client 2 is as follows:

1. fromPath: [0,0,0,1], toPath: [0,0,0,4]
2. fromPath: [0,0,0,5], toPath: [0,0,0,7]

However, due to the result of the first remote change, the offset of the second remote change should be adjusted to [0,0,0,2] & [0,0,0,4].

You can reproduce the issue using the test code below:

it.only('Should return correct range path for block edit', async function ({
  task,
}) {
  await withTwoClientsAndDocuments<{ t: Tree }>(async (c1, d1, c2, d2) => {
    d1.update((root) => {
      root.t = new Tree({
        type: 'r',
        children: [
          {
            type: 'c',
            children: [
              {
                type: 'p',
                children: [
                  {
                    type: 'n',
                    children: [],
                  },
                ],
              },
            ],
          },
        ],
      });
    });
    await c1.sync();
    await c2.sync();
    assert.equal(
      d1.getRoot().t.toXML(),
      /*html*/ `<r><c><p><n></n></p></c></r>`,
    );
    assert.equal(
      d2.getRoot().t.toXML(),
      /*html*/ `<r><c><p><n></n></p></c></r>`,
    );

    d1.update((r) =>
      r.t.editByPath([0, 0, 0, 0], [0, 0, 0, 0], {
        type: 'text',
        value: '0123456',
      }),
    );
    await c1.sync();
    await c2.sync();
    assert.equal(
      d1.getRoot().t.toXML(),
      /*html*/ `<r><c><p><n>0123456</n></p></c></r>`,
    );
    assert.equal(
      d2.getRoot().t.toXML(),
      /*html*/ `<r><c><p><n>0123456</n></p></c></r>`,
    );

    const eventCollector = new EventCollector<{ type: DocEventType }>();
    const unsub = d2.subscribe((event) => {
      if (event.type === 'remote-change') {
        if (event.value.operations.length > 1) {
          const op1 = event.value.operations[0] as TreeEditOpInfo;
          assert.deepEqual(op1.fromPath, [0, 0, 0, 1]);
          assert.deepEqual(op1.toPath, [0, 0, 0, 4]);
          const op2 = event.value.operations[1] as TreeEditOpInfo;
          assert.deepEqual(op2.fromPath, [0, 0, 0, 5]); // should be [0, 0, 0, 2]
          assert.deepEqual(op2.toPath, [0, 0, 0, 7]); // should be [0, 0, 0, 4]
        }
        eventCollector.add({ type: event.type });
      }
    });

    d1.update((r) => r.t.editByPath([0, 0, 0, 1], [0, 0, 0, 6]));
    d1.update((r) =>
      r.t.editByPath([0, 0, 0, 1], [0, 0, 0, 1], {
        type: 'text',
        value: 'z',
      }),
    );
    d2.update((r) =>
      r.t.editByPath([0, 0, 0, 4], [0, 0, 0, 4], {
        type: 'text',
        value: 'x',
      }),
    );

    await c1.sync();
    await c2.sync();
    await c1.sync();

    assert.equal(
      d1.getRoot().t.toXML(),
      /*html*/ `<r><c><p><n>0zx6</n></p></c></r>`,
    );
    assert.equal(
      d2.getRoot().t.toXML(),
      /*html*/ `<r><c><p><n>0zx6</n></p></c></r>`,
    );

    await eventCollector.waitAndVerifyNthEvent(1, {
      type: DocEventType.RemoteChange,
    });
    unsub();
  }, task.name);
});

What you expected to happen:

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

Anything else we need to know?:

Environment:

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

[raararaara]

I tried reproducing the above situation using fromIdx and toIdx rather than editByPath, but the same result was obtained.

But interestingly, when we recreated a similar situation in text.edit situation, I saw that the order of the two events was reversed.

yorkie-js-sdk/src/document/crdt/rga_tree_split.ts

Lines 935 to 971 in 653f98e

	private makeChanges(
	boundaries: Array<RGATreeSplitNode<T> | undefined>,
	editedAt: TimeTicket,
	): Array<ValueChange<T>> {
	const changes: Array<ValueChange<T>> = [];
	let fromIdx: number, toIdx: number;
	for (let i = 0; i < boundaries.length - 1; i++) {
	const leftBoundary = boundaries[i];
	const rightBoundary = boundaries[i + 1];
	if (leftBoundary!.getNext() == rightBoundary) {
	continue;
	}
	[fromIdx] = this.findIndexesFromRange(
	leftBoundary!.getNext()!.createPosRange(),
	);
	if (rightBoundary) {
	[, toIdx] = this.findIndexesFromRange(
	rightBoundary.getPrev()!.createPosRange(),
	);
	} else {
	toIdx = this.treeByIndex.length;
	}
	if (fromIdx < toIdx) {
	changes.push({
	actor: editedAt.getActorID(),
	from: fromIdx,
	to: toIdx,
	});
	}
	}
	return changes.reverse();
	}

Based on this result, in the case of trees as well, I think that when deletion of consecutive sections occurs, it may be possible to solve the problem by delivering change events in reverse order rather than adjusting the index from the previous event.

[hackerwins]

We can think about the below solutions for this issue:

• A. Reversing events similar to Text.Edit and propagating them to users.
• B. Calculating the index of events based on previous events.

Regarding solution A, since Text is linear in structure and Tree is hierarchical, we need to consider side-effect of reversing.

[raararaara]

Although Tree is hierarchical, it can be applied like a linear data structure by mapping it into a 'token list' and performing operations based on it.

As mentioned in the comment above, changes to textNode do not require index adjustment when the order is reversed, so it does not seem to be a problem to resolve the issue by reversing the order when creating changes for range deletion in the tree.

yorkie-js-sdk/src/document/crdt/tree.ts

Lines 1388 to 1449 in dc9146f

	private makeDeletionChanges(
	candidates: Array<TreeToken<CRDTTreeNode>>,
	editedAt: TimeTicket,
	): Array<TreeChange> {
	const changes: Array<TreeChange> = [];
	const ranges: Array<Array<TreeToken<CRDTTreeNode>>> = [];
	// Generate ranges by accumulating consecutive nodes.
	let start = null;
	let end = null;
	for (let i = 0; i < candidates.length; i++) {
	const cur = candidates[i];
	const next = candidates[i + 1];
	if (!start) {
	start = cur;
	}
	end = cur;
	const rightToken = this.findRightToken(cur);
	if (
	!rightToken ||
	!next ||
	rightToken[0] !== next[0] ||
	rightToken[1] !== next[1]
	) {
	ranges.push([start, end]);
	start = null;
	end = null;
	}
	}
	// Convert each range to a deletion change.
	for (const range of ranges) {
	const [start, end] = range;
	const [fromLeft, fromLeftTokenType] = this.findLeftToken(start);
	const [toLeft, toLeftTokenType] = end;
	const fromParent =
	fromLeftTokenType === TokenType.Start ? fromLeft : fromLeft.parent!;
	const toParent =
	toLeftTokenType === TokenType.Start ? toLeft : toLeft.parent!;
	const fromIdx = this.toIndex(fromParent, fromLeft);
	const toIdx = this.toIndex(toParent, toLeft);
	if (fromIdx < toIdx) {
	// When the range is overlapped with the previous one, compact them.
	if (changes.length > 0 && fromIdx === changes[changes.length - 1].to) {
	changes[changes.length - 1].to = toIdx;
	changes[changes.length - 1].toPath = this.toPath(toParent, toLeft);
	} else {
	changes.push({
	type: TreeChangeType.Content,
	from: fromIdx,
	to: toIdx,
	fromPath: this.toPath(fromParent, fromLeft),
	toPath: this.toPath(toParent, toLeft),
	actor: editedAt.getActorID(),
	});
	}
	}
	}
	return changes;
	}