Repository: yorkie-team/yorkie
Pull request #364 (2022-07-20 04:19:11)

Fix incorrect index for nodes newly created then concurrently removed
<!--  Thanks for sending a pull request! -->

**What this PR does / why we need it**:

Nodes newly created then concurrently removed in the range to be deleted
had incorrect weight since they were not included in either nodesToKeep
or nodesToDelete. This problem causes incorrect indexing, and this commit
fixes that missing weight updates.

all changes are same with https://github.com/yorkie-team/yorkie-js-sdk/pull/334

**Which issue(s) this PR fixes**:
<!--
*Automatically closes linked issue when PR is merged.
Usage: `Fixes #<issue number>`, or `Fixes (paste link of issue)`.
-->
Fixes #

**Special notes for your reviewer**:

**Does this PR introduce a user-facing change?**:
<!--
If no, just write "NONE" in the release-note block below.
If yes, a release note is required:
Enter your extended release note in the block below. If the PR requires additional action from users switching to the new release, include the string "action required".
-->
```release-note

```

**Additional documentation**:

<!--
This section can be blank if this pull request does not require a release note.

Please use the following format for linking documentation:
- [Usage]: <link>
- [Other doc]: <link>
-->
```docs

```

**Checklist**:
- [x] Added relevant tests or not required
- [x] Didn't break anything


codecov[bot]: # [Codecov](https://codecov.io/gh/yorkie-team/yorkie/pull/364?src=pr&el=h1&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=yorkie-team) Report
> Merging [#364](https://codecov.io/gh/yorkie-team/yorkie/pull/364?src=pr&el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=yorkie-team) (7d8d9ad) into [main](https://codecov.io/gh/yorkie-team/yorkie/commit/d119a2eb7b6f2180024d1558ab9b6dea62d781b3?el=desc&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=yorkie-team) (d119a2e) will **decrease** coverage by `0.05%`.
> The diff coverage is `50.00%`.

```diff
@@            Coverage Diff             @@
##             main     #364      +/-   ##
==========================================
- Coverage   48.66%   48.61%   -0.06%     
==========================================
  Files          67       67              
  Lines        5493     5507      +14     
==========================================
+ Hits         2673     2677       +4     
- Misses       2528     2538      +10     
  Partials      292      292              
```


| [Impacted Files](https://codecov.io/gh/yorkie-team/yorkie/pull/364?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=yorkie-team) | Coverage Δ | |
|---|---|---|
| [pkg/document/json/rga\_tree\_split.go](https://codecov.io/gh/yorkie-team/yorkie/pull/364/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=yorkie-team#diff-cGtnL2RvY3VtZW50L2pzb24vcmdhX3RyZWVfc3BsaXQuZ28=) | `73.75% <0.00%> (-0.31%)` | :arrow_down: |
| [pkg/document/json/text.go](https://codecov.io/gh/yorkie-team/yorkie/pull/364/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=yorkie-team#diff-cGtnL2RvY3VtZW50L2pzb24vdGV4dC5nbw==) | `48.43% <0.00%> (-0.77%)` | :arrow_down: |
| [pkg/splay/splay.go](https://codecov.io/gh/yorkie-team/yorkie/pull/364/diff?src=pr&el=tree&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=yorkie-team#diff-cGtnL3NwbGF5L3NwbGF5Lmdv) | `77.65% <61.11%> (-3.03%)` | :arrow_down: |

------

[Continue to review full report at Codecov](https://codecov.io/gh/yorkie-team/yorkie/pull/364?src=pr&el=continue&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=yorkie-team).
> **Legend** - [Click here to learn more](https://docs.codecov.io/docs/codecov-delta?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=yorkie-team)
> `Δ = absolute <relative> (impact)`, `ø = not affected`, `? = missing data`
> Powered by [Codecov](https://codecov.io/gh/yorkie-team/yorkie/pull/364?src=pr&el=footer&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=yorkie-team). Last update [d119a2e...7d8d9ad](https://codecov.io/gh/yorkie-team/yorkie/pull/364?src=pr&el=lastupdated&utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=yorkie-team). Read the [comment docs](https://docs.codecov.io/docs/pull-request-comments?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=yorkie-team).


Patch:
diff --git a/pkg/document/json/rga_tree_split.go b/pkg/document/json/rga_tree_split.go
index 5fc60bcf..25b48617 100644
--- a/pkg/document/json/rga_tree_split.go
+++ b/pkg/document/json/rga_tree_split.go
@@ -414,6 +414,12 @@ func (s *RGATreeSplit[V]) FindNode(id *RGATreeSplitNodeID) *RGATreeSplitNode[V]
 	return s.findFloorNode(id)
 }
 
+// CheckWeight returns false when there is an incorrect weight node.
+// for debugging purpose.
+func (s *RGATreeSplit[V]) CheckWeight() bool {
+	return s.treeByIndex.CheckWeight()
+}
+
 func (s *RGATreeSplit[V]) findFloorNode(id *RGATreeSplitNodeID) *RGATreeSplitNode[V] {
 	key, value := s.treeByID.Floor(id)
 	if key == nil {
@@ -509,7 +515,6 @@ func (s *RGATreeSplit[V]) deleteNodes(
 		}
 
 		if node.Remove(editedAt, latestCreatedAt) {
-			node.indexNode.InitWeight()
 			latestCreatedAt := createdAtMapByActor[actorIDHex]
 			createdAt := node.id.createdAt
 			if latestCreatedAt == nil || createdAt.After(latestCreatedAt) {
@@ -517,7 +522,7 @@ func (s *RGATreeSplit[V]) deleteNodes(
 			}
 
 			removedNodeMap[node.id.key()] = node
-		} else if node.removedAt == nil {
+		} else {
 			nodesToKeep = append(nodesToKeep, node)
 		}
 	}
@@ -544,6 +549,7 @@ func (s *RGATreeSplit[V]) deleteIndexNodes(boundaries []*RGATreeSplitNode[V]) {
 		rightBoundary := boundaries[i+1]
 		if leftBoundary.next == rightBoundary {
 			// If there is no node to delete between boundaries, do notting.
+			continue
 		} else if rightBoundary == nil {
 			s.treeByIndex.DeleteRange(leftBoundary.indexNode, nil)
 		} else {
diff --git a/pkg/document/json/text.go b/pkg/document/json/text.go
index 4df5fe55..e35d0464 100644
--- a/pkg/document/json/text.go
+++ b/pkg/document/json/text.go
@@ -216,6 +216,12 @@ func (t *Text) AnnotatedString() string {
 	return t.rgaTreeSplit.AnnotatedString()
 }
 
+// CheckWeight returns false when there is an incorrect weight node.
+// for debugging purpose.
+func (t *Text) CheckWeight() bool {
+	return t.rgaTreeSplit.CheckWeight()
+}
+
 // removedNodesLen returns length of removed nodes
 func (t *Text) removedNodesLen() int {
 	return t.rgaTreeSplit.removedNodesLen()
diff --git a/pkg/splay/splay.go b/pkg/splay/splay.go
index 8c694a9a..825c7bc9 100644
--- a/pkg/splay/splay.go
+++ b/pkg/splay/splay.go
@@ -236,6 +236,21 @@ func (t *Tree[V]) AnnotatedString() string {
 	return builder.String()
 }
 
+// CheckWeight returns false when there is an incorrect weight node.
+// for debugging purpose.
+func (t *Tree[V]) CheckWeight() bool {
+	var nodes []*Node[V]
+	traversePostOrder(t.root, func(node *Node[V]) {
+		nodes = append(nodes, node)
+	})
+	for _, node := range nodes {
+		if node.weight != node.Value().Len()+node.leftWeight()+node.rightWeight() {
+			return false
+		}
+	}
+	return true
+}
+
 // UpdateWeight recalculates the weight of this node with the value and children.
 func (t *Tree[V]) UpdateWeight(node *Node[V]) {
 	node.InitWeight()
@@ -293,33 +308,24 @@ func (t *Tree[V]) Delete(node *Node[V]) {
 // by splaying outer boundary nodes.
 // leftBoundary must exist because of 0-indexed initial dummy node of tree,
 // but rightBoundary can be nil means range to delete includes the end of tree.
+// Refer to the design document: ./design/range-deletion-in-slay-tree.md
 func (t *Tree[V]) DeleteRange(leftBoundary, rightBoundary *Node[V]) {
 	if rightBoundary == nil {
 		t.Splay(leftBoundary)
-		// After splaying, all the range is the right subtree of leftBoundary.
 		t.cutOffRight(leftBoundary)
 		return
 	}
-	t.Splay(rightBoundary)
 	t.Splay(leftBoundary)
-	// After splaying twice, leftBoundary must be the root and
-	// rightBoundary is leftBoundary.right.right(case 1) or leftBoundary.right(case 2)
-	if leftBoundary.right != rightBoundary {
-		// If case 1, changes to case 2 by rotateLeft (makes rightBoundary be leftBoundary.right).
-		t.rotateLeft(rightBoundary)
+	t.Splay(rightBoundary)
+	if rightBoundary.left != leftBoundary {
+		t.rotateRight(leftBoundary)
 	}
-	// In case 2, since rightBoundary is leftBoundary.right,
-	// all the range nodes between 2 boundaries are in the left subtree of rightBoundary.
-	t.cutOffLeft(rightBoundary)
+	t.cutOffRight(leftBoundary)
 }
 
-func (t *Tree[V]) cutOffLeft(node *Node[V]) {
-	// TODO(Eithea): The node to delete is not actually disconnected from the tree yet.
-	t.updateTreeWeight(node)
-}
-
-func (t *Tree[V]) cutOffRight(node *Node[V]) {
-	t.updateTreeWeight(node)
+func (t *Tree[V]) cutOffRight(root *Node[V]) {
+	traversePostOrder(root.right, func(node *Node[V]) { node.InitWeight() })
+	t.updateTreeWeight(root)
 }
 
 func (t *Tree[V]) rotateLeft(pivot *Node[V]) {
@@ -391,6 +397,16 @@ func traverseInOrder[V Value](node *Node[V], callback func(node *Node[V])) {
 	traverseInOrder(node.right, callback)
 }
 
+func traversePostOrder[V Value](node *Node[V], callback func(node *Node[V])) {
+	if node == nil {
+		return
+	}
+
+	traversePostOrder(node.left, callback)
+	traversePostOrder(node.right, callback)
+	callback(node)
+}
+
 func isLeftChild[V Value](node *Node[V]) bool {
 	return node != nil && node.parent != nil && node.parent.left == node
 }


Test patch:
diff --git a/pkg/splay/splay_test.go b/pkg/splay/splay_test.go
index 4530116d..7f6e69b6 100644
--- a/pkg/splay/splay_test.go
+++ b/pkg/splay/splay_test.go
@@ -122,7 +122,7 @@ func TestSplayTree(t *testing.T) {
 		tree.DeleteRange(nodes[2], nodes[7])
 		assert.Equal(
 			t,
-			"[1,1]A[3,2]BB[9,3]CCC[0,0]DDDD[0,0]EEEEE[0,0]FFFF[0,0]GGG[3,2]HH[1,1]I",
+			"[1,1]A[3,2]BB[6,3]CCC[0,0]DDDD[0,0]EEEEE[0,0]FFFF[0,0]GGG[9,2]HH[1,1]I",
 			tree.AnnotatedString(),
 		)
 
@@ -134,7 +134,7 @@ func TestSplayTree(t *testing.T) {
 		tree.DeleteRange(nodes[2], nodes[8])
 		assert.Equal(
 			t,
-			"[1,1]A[3,2]BB[7,3]CCC[0,0]DDDD[0,0]EEEEE[0,0]FFFF[0,0]GGG[0,0]HH[1,1]I",
+			"[1,1]A[3,2]BB[6,3]CCC[0,0]DDDD[0,0]EEEEE[0,0]FFFF[0,0]GGG[0,0]HH[7,1]I",
 			tree.AnnotatedString(),
 		)
 	})
diff --git a/test/integration/text_test.go b/test/integration/text_test.go
index 3a991222..9a1470d6 100644
--- a/test/integration/text_test.go
+++ b/test/integration/text_test.go
@@ -131,4 +131,102 @@ func TestText(t *testing.T) {
 
 		syncClientsThenAssertEqual(t, []clientAndDocPair{{c1, d1}, {c2, d2}})
 	})
+
+	t.Run("concurrent block deletions test", func(t *testing.T) {
+		ctx := context.Background()
+
+		d1 := document.New(key.Key(t.Name()))
+		err := c1.Attach(ctx, d1)
+		assert.NoError(t, err)
+
+		err = d1.Update(func(root *proxy.ObjectProxy) error {
+			root.SetNewText("k1")
+			return nil
+		}, "set a new text by c1")
+		assert.NoError(t, err)
+		err = c1.Sync(ctx)
+		assert.NoError(t, err)
+
+		d2 := document.New(key.Key(t.Name()))
+		err = c2.Attach(ctx, d2)
+		assert.NoError(t, err)
+
+		err = d1.Update(func(root *proxy.ObjectProxy) error {
+			root.GetText("k1").Edit(0, 0, "123")
+			root.GetText("k1").Edit(3, 3, "456")
+			root.GetText("k1").Edit(6, 6, "789")
+			return nil
+		}, "set new text by c1")
+		assert.NoError(t, err)
+
+		syncClientsThenAssertEqual(t, []clientAndDocPair{{c1, d1}, {c2, d2}})
+		assert.Equal(t, `{"k1":"123456789"}`, d2.Marshal())
+
+		err = d1.Update(func(root *proxy.ObjectProxy) error {
+			root.GetText("k1").Edit(1, 7, "")
+			return nil
+		}, "delete block by c1")
+		assert.NoError(t, err)
+		assert.Equal(t, `{"k1":"189"}`, d1.Marshal())
+
+		err = d2.Update(func(root *proxy.ObjectProxy) error {
+			root.GetText("k1").Edit(2, 5, "")
+			return nil
+		}, "delete block by c2")
+		assert.NoError(t, err)
+		assert.Equal(t, `{"k1":"126789"}`, d2.Marshal())
+
+		syncClientsThenAssertEqual(t, []clientAndDocPair{{c1, d1}, {c2, d2}})
+	})
+
+	t.Run("new creation then concurrent deletion test", func(t *testing.T) {
+		ctx := context.Background()
+
+		d1 := document.New(key.Key(t.Name()))
+		err := c1.Attach(ctx, d1)
+		assert.NoError(t, err)
+
+		err = d1.Update(func(root *proxy.ObjectProxy) error {
+			root.SetNewText("k1")
+			return nil
+		}, "set a new text by c1")
+		assert.NoError(t, err)
+		err = c1.Sync(ctx)
+		assert.NoError(t, err)
+
+		d2 := document.New(key.Key(t.Name()))
+		err = c2.Attach(ctx, d2)
+		assert.NoError(t, err)
+
+		err = d1.Update(func(root *proxy.ObjectProxy) error {
+			root.GetText("k1").Edit(0, 0, "0")
+			root.GetText("k1").Edit(1, 1, "0")
+			root.GetText("k1").Edit(2, 2, "0")
+			return nil
+		}, "set new text by c1")
+		assert.NoError(t, err)
+
+		syncClientsThenAssertEqual(t, []clientAndDocPair{{c1, d1}, {c2, d2}})
+		assert.Equal(t, `{"k1":"000"}`, d2.Marshal())
+
+		err = d1.Update(func(root *proxy.ObjectProxy) error {
+			root.GetText("k1").Edit(1, 2, "1")
+			root.GetText("k1").Edit(1, 2, "1")
+			root.GetText("k1").Edit(1, 2, "")
+			return nil
+		}, "newly create then delete by c1")
+		assert.NoError(t, err)
+		assert.Equal(t, `{"k1":"00"}`, d1.Marshal())
+
+		err = d2.Update(func(root *proxy.ObjectProxy) error {
+			root.GetText("k1").Edit(0, 3, "")
+			return nil
+		}, "delete the range includes above new nodes")
+		assert.NoError(t, err)
+		assert.Equal(t, `{"k1":""}`, d2.Marshal())
+
+		syncClientsThenAssertEqual(t, []clientAndDocPair{{c1, d1}, {c2, d2}})
+		assert.True(t, d1.Root().GetText("k1").CheckWeight())
+		assert.True(t, d2.Root().GetText("k1").CheckWeight())
+	})
 }