Error in concurrent editing and styling (Edit+Style) handling
hackerwins opened this issue · 2 comments
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:
- Differentiate between nodes that have been newly inserted and existing nodes during the concurrent editing and styling process by comparing
Node.CreatedAt
andeditedAt
timeTicket. - 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.
Case 'insert-front + style'
![image](https://private-user-images.githubusercontent.com/31478163/303220868-81449755-a979-448b-bb14-bc3170311cde.png?jwt=eyJhbGciOiJIUzI1NiIsInR5cCI6IkpXVCJ9.eyJpc3MiOiJnaXRodWIuY29tIiwiYXVkIjoicmF3LmdpdGh1YnVzZXJjb250ZW50LmNvbSIsImtleSI6ImtleTUiLCJleHAiOjE3MTU5MjUxMDksIm5iZiI6MTcxNTkyNDgwOSwicGF0aCI6Ii8zMTQ3ODE2My8zMDMyMjA4NjgtODE0NDk3NTUtYTk3OS00NDhiLWJiMTQtYmMzMTcwMzExY2RlLnBuZz9YLUFtei1BbGdvcml0aG09QVdTNC1ITUFDLVNIQTI1NiZYLUFtei1DcmVkZW50aWFsPUFLSUFWQ09EWUxTQTUzUFFLNFpBJTJGMjAyNDA1MTclMkZ1cy1lYXN0LTElMkZzMyUyRmF3czRfcmVxdWVzdCZYLUFtei1EYXRlPTIwMjQwNTE3VDA1NDY0OVomWC1BbXotRXhwaXJlcz0zMDAmWC1BbXotU2lnbmF0dXJlPTlmZWY1MTcyZGZiMWRkNWM1MjFmYTEyMTE5N2ExNmJkYjdmODMwNDViY2IwNGYwNjM5MjY1ZjRkOTA3Y2E1YTcmWC1BbXotU2lnbmVkSGVhZGVycz1ob3N0JmFjdG9yX2lkPTAma2V5X2lkPTAmcmVwb19pZD0wIn0.uNbGtS25NYWlM8X3DOOkBkI3sNDNTFgtQ8MNA_iXVh8)
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
- 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>
- 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]
- Client1's local change: Edit(Insert)
- 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
- 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.
- Go SDK: #854
- JS SDK: yorkie-team/yorkie-js-sdk#803
- Android SDK
- iOS SDK