Error in concurrent editing and styling (Edit+Style) handling

[hackerwins]

Description:

What happened:
Refer to #780 , there is an error occurring in the concurrent editing and styling (Edit+Style) handling. Failure cases related to Style operation are as follows:

• Edit and Style (15/84 cases)

  • (6) {equal, equal-multiple} / {insert-front, insert-middle, replace} / style
  • (4) {intersect, A -> B} / {insert-middle, insert-back} / style
  • (1) A contains B / insert-middle / style
  • (4) B contains A / {insert-front, insert-middle, insert-back, replace} / style

• Split and Edit (46/144 cases)

  • (2) A contains B / {split-1, split-2} / {style, remove-style}
  • (2) B contains A / {split-1, split-2} / {style}
  • (1) B contains A / split-2 / remove-style
  • (8) {right node text, right node element} / {split-1, split-2} / {style, remove-style}
  • (2) A -> B / {split-1, split-2} / {style}
  • (1) A -> B / split-2 / remove-style

What you expected to happen:
The concurrent editing and styling (Edit+Style) should work without any errors.

How to reproduce it (as minimally and precisely as possible):
To reproduce the issue, follow the steps:

1. Differentiate between nodes that have been newly inserted and existing nodes during the concurrent editing and styling process by comparing Node.CreatedAt and editedAt timeTicket.
2. The style operation is ignored for nodes created before concurrency edit.

Anything else we need to know?:
The error appears to be related to the violation of the commutative property.

[raararaara]

Case 'insert-front + style'

Description

During concurrent editing and styling of a document, there is an issue where the style attribute is applied to newly inserted nodes. This behavior is unexpected and incorrect.

Steps to Reproduce

1. Set the initial state of the document as follows:

      0               1 2    3               4 5    6               7 8    9
<root> <p color="red"> a </p> <p color="red"> b </p> <p color="red"> c </p> </root>
<root>
  <p color="red">a</p>
  <p color="red">b</p>
  <p color="red">c</p>
</root>

2. Perform the following changes concurrently:
   • Client1's local change: Edit(Insert) <p italic="true">d</p> at [3, 3]
   • Client2's local change: Style attribute "bold"="aa" at [3, 6]
3. Sync Client1 and Client2

Current Result

The results after applying and syncing local changes to each client are as follows:

Client1:

• After Edit(local change)

<root>
  <p color="red">a</p>
  <p italic="true">d</p>
  <p color="red">b</p>
  <p color="red">c</p>
</root>

• Edit after Style(sync)

<root>
  <p color="red">a</p>
  <p "bold"="aa" italic="true">d</p>
  <p "bold"="aa" color="red">b</p>
  <p color="red">c</p>
</root>

Client2:

• After Style(local change)

<root>
  <p color="red">a</p>
  <p "bold"="aa" color="red">b</p>
  <p color="red">c</p>
</root>

• Style after Edit(sync)

<root>
  <p color="red">a</p>
  <p italic="true">d</p>
  <p "bold"="aa" color="red">b</p>
  <p color="red">c</p>
</root>

Suggestion

1. Lamport clock comparison

It is important to differentiate between nodes that have been newly inserted and existing nodes during the concurrent editing and styling process. This distinction will help in precisely applying style operations within the appropriate scope.

By applying the rules below, all failure cases for style-related tests that occurred in the previously written tree-concurrency-test can be resolved.

• Before
  

  yorkie/pkg/document/crdt/tree.go

  Lines 859 to 871 in a8f6bc2

  	err = t.traverseInPosRange(fromParent, fromLeft, toParent, toLeft,
  	func(token index.TreeToken[*TreeNode], _ bool) {
  	node := token.Node
  	if !node.IsRemoved() && !node.IsText() && len(attributes) > 0 {
  	if node.Attrs == nil {
  	node.Attrs = NewRHT()
  	}
  	for key, value := range attributes {
  	node.Attrs.Set(key, value, editedAt)
  	}
  	}
  	})

• After

	err = t.traverseInPosRange(fromParent, fromLeft, toParent, toLeft,
		func(token index.TreeToken[*TreeNode], _ bool) {
			node := token.Node
			if !node.IsRemoved() && !node.IsText() && len(attributes) > 0 {
				if editedAt.After(node.ID.CreatedAt) {
					return
				}

				// ...
			}
		})

Since the priority of the Lamport timestamp does not guarantee concurrent causality, this method does not solve the problem.

[hackerwins]

• Go SDK: Handle concurrent editing and styling in Tree #854
• JS SDK: Handle concurrent editing and styling in Tree yorkie-js-sdk#803
• Android SDK: Handle concurrent editing and styling in Tree yorkie-android-sdk#178
• iOS SDK: Handle concurrent editing and styling in Tree yorkie-ios-sdk#166