Repository: yorkie-team/yorkie
Pull request #356 (2022-07-06 09:43:40)

Apply Splay range deletion
<!--  Thanks for sending a pull request! -->

**What this PR does / why we need it**:

This commit applies again the existing commit that was reverted
due to instability. (#341)

Using the splay operation, this commit separates nodes in
given range as a subtree to delete. Since each node to delete
is not `splay`ed, performance improvement is expected.

**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



Patch:
diff --git a/pkg/document/json/rga_tree_split.go b/pkg/document/json/rga_tree_split.go
index dee3db7d..5fc60bcf 100644
--- a/pkg/document/json/rga_tree_split.go
+++ b/pkg/document/json/rga_tree_split.go
@@ -247,7 +247,7 @@ func (s *RGATreeSplitNode[V]) setPrev(node *RGATreeSplitNode[V]) {
 }
 
 func (s *RGATreeSplitNode[V]) split(offset int) *RGATreeSplitNode[V] {
-	newNode := NewRGATreeSplitNode[V](
+	newNode := NewRGATreeSplitNode(
 		s.id.Split(offset),
 		s.value.Split(offset).(V),
 	)
@@ -452,7 +452,7 @@ func (s *RGATreeSplit[V]) edit(
 
 	// 03. insert a new node
 	if content.Len() > 0 {
-		inserted := s.InsertAfter(fromLeft, NewRGATreeSplitNode[V](NewRGATreeSplitNodeID(editedAt, 0), content))
+		inserted := s.InsertAfter(fromLeft, NewRGATreeSplitNode(NewRGATreeSplitNodeID(editedAt, 0), content))
 		caretPos = NewRGATreeSplitNodePos(inserted.id, inserted.contentLen())
 	}
 
@@ -482,6 +482,17 @@ func (s *RGATreeSplit[V]) deleteNodes(
 	createdAtMapByActor := make(map[string]*time.Ticket)
 	removedNodeMap := make(map[string]*RGATreeSplitNode[V])
 
+	if len(candidates) == 0 {
+		return createdAtMapByActor, removedNodeMap
+	}
+
+	// There are 2 types of nodes in `candidates`: should delete, should not delete.
+	// `nodesToKeep` contains nodes should not delete,
+	// then is used to find the boundary of the range to be deleted.
+	var nodesToKeep []*RGATreeSplitNode[V]
+	leftEdge, rightEdge := s.findEdgesOfCandidates(candidates)
+	nodesToKeep = append(nodesToKeep, leftEdge)
+
 	for _, node := range candidates {
 		actorIDHex := node.createdAt().ActorIDHex()
 
@@ -498,7 +509,7 @@ func (s *RGATreeSplit[V]) deleteNodes(
 		}
 
 		if node.Remove(editedAt, latestCreatedAt) {
-			s.treeByIndex.Splay(node.indexNode)
+			node.indexNode.InitWeight()
 			latestCreatedAt := createdAtMapByActor[actorIDHex]
 			createdAt := node.id.createdAt
 			if latestCreatedAt == nil || createdAt.After(latestCreatedAt) {
@@ -506,12 +517,41 @@ func (s *RGATreeSplit[V]) deleteNodes(
 			}
 
 			removedNodeMap[node.id.key()] = node
+		} else if node.removedAt == nil {
+			nodesToKeep = append(nodesToKeep, node)
 		}
 	}
+	nodesToKeep = append(nodesToKeep, rightEdge)
+	s.deleteIndexNodes(nodesToKeep)
 
 	return createdAtMapByActor, removedNodeMap
 }
 
+// findEdgesOfCandidates finds the edges outside `candidates`,
+// (which has not already been deleted, or be undefined but not yet implemented)
+// right edge is undefined means `candidates` contains the end of text.
+func (s *RGATreeSplit[V]) findEdgesOfCandidates(
+	candidates []*RGATreeSplitNode[V],
+) (*RGATreeSplitNode[V], *RGATreeSplitNode[V]) {
+	return candidates[0].prev, candidates[len(candidates)-1].next
+}
+
+// deleteIndexNodes clears the index nodes of the given deletion boundaries.
+// The boundaries mean the nodes that will not be deleted in the range.
+func (s *RGATreeSplit[V]) deleteIndexNodes(boundaries []*RGATreeSplitNode[V]) {
+	for i := 0; i < len(boundaries)-1; i++ {
+		leftBoundary := boundaries[i]
+		rightBoundary := boundaries[i+1]
+		if leftBoundary.next == rightBoundary {
+			// If there is no node to delete between boundaries, do notting.
+		} else if rightBoundary == nil {
+			s.treeByIndex.DeleteRange(leftBoundary.indexNode, nil)
+		} else {
+			s.treeByIndex.DeleteRange(leftBoundary.indexNode, rightBoundary.indexNode)
+		}
+	}
+}
+
 func (s *RGATreeSplit[V]) marshal() string {
 	builder := strings.Builder{}
 
diff --git a/pkg/splay/splay.go b/pkg/splay/splay.go
index 40456a42..8c694a9a 100644
--- a/pkg/splay/splay.go
+++ b/pkg/splay/splay.go
@@ -42,7 +42,7 @@ func NewNode[V Value](value V) *Node[V] {
 	n := &Node[V]{
 		value: value,
 	}
-	n.initWeight()
+	n.InitWeight()
 	return n
 }
 
@@ -65,7 +65,8 @@ func (t *Node[V]) rightWeight() int {
 	return t.right.weight
 }
 
-func (t *Node[V]) initWeight() {
+//InitWeight sets initial weight of this node.
+func (t *Node[V]) InitWeight() {
 	t.weight = t.value.Len()
 }
 
@@ -237,7 +238,7 @@ func (t *Tree[V]) AnnotatedString() string {
 
 // UpdateWeight recalculates the weight of this node with the value and children.
 func (t *Tree[V]) UpdateWeight(node *Node[V]) {
-	node.initWeight()
+	node.InitWeight()
 
 	if node.left != nil {
 		node.increaseWeight(node.leftWeight())
@@ -248,6 +249,13 @@ func (t *Tree[V]) UpdateWeight(node *Node[V]) {
 	}
 }
 
+func (t *Tree[V]) updateTreeWeight(node *Node[V]) {
+	for node != nil {
+		t.UpdateWeight(node)
+		node = node.parent
+	}
+}
+
 // Delete deletes the given node from this Tree.
 func (t *Tree[V]) Delete(node *Node[V]) {
 	t.Splay(node)
@@ -280,6 +288,40 @@ func (t *Tree[V]) Delete(node *Node[V]) {
 	}
 }
 
+// DeleteRange separates the range between given 2 boundaries from this Tree.
+// This function separates the range to delete as a subtree
+// 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.
+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)
+	}
+	// 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)
+}
+
+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]) rotateLeft(pivot *Node[V]) {
 	root := pivot.parent
 	if root.parent != nil {


Test patch:
diff --git a/pkg/splay/splay_test.go b/pkg/splay/splay_test.go
index 2b9d5eab..4530116d 100644
--- a/pkg/splay/splay_test.go
+++ b/pkg/splay/splay_test.go
@@ -26,15 +26,19 @@ import (
 
 type stringValue struct {
 	content string
+	removed bool
 }
 
 func newSplayNode(content string) *splay.Node[*stringValue] {
-	return splay.NewNode[*stringValue](&stringValue{
+	return splay.NewNode(&stringValue{
 		content: content,
 	})
 }
 
 func (v *stringValue) Len() int {
+	if v.removed {
+		return 0
+	}
 	return len(v.content)
 }
 
@@ -101,28 +105,62 @@ func TestSplayTree(t *testing.T) {
 		assert.Equal(t, tree.IndexOf(nodeO), 3)
 	})
 
-	t.Run("range separation test", func(t *testing.T) {
-		tree := splay.NewTree[*stringValue](nil)
-
-		tree.Insert(newSplayNode("A"))
-		assert.Equal(t, "[1,1]A", tree.AnnotatedString())
-		tree.Insert(newSplayNode("BB"))
-		assert.Equal(t, "[1,1]A[3,2]BB", tree.AnnotatedString())
-		tree.Insert(newSplayNode("CCC"))
-		assert.Equal(t, "[1,1]A[3,2]BB[6,3]CCC", tree.AnnotatedString())
-		tree.Insert(newSplayNode("DDDD"))
-		assert.Equal(t, "[1,1]A[3,2]BB[6,3]CCC[10,4]DDDD", tree.AnnotatedString())
-		tree.Insert(newSplayNode("EEEEE"))
-		assert.Equal(t, "[1,1]A[3,2]BB[6,3]CCC[10,4]DDDD[15,5]EEEEE", tree.AnnotatedString())
-		tree.Insert(newSplayNode("FFFF"))
-		assert.Equal(t, "[1,1]A[3,2]BB[6,3]CCC[10,4]DDDD[15,5]EEEEE[19,4]FFFF", tree.AnnotatedString())
-		tree.Insert(newSplayNode("GGG"))
-		assert.Equal(t, "[1,1]A[3,2]BB[6,3]CCC[10,4]DDDD[15,5]EEEEE[19,4]FFFF[22,3]GGG", tree.AnnotatedString())
-		tree.Insert(newSplayNode("HH"))
-		assert.Equal(t, "[1,1]A[3,2]BB[6,3]CCC[10,4]DDDD[15,5]EEEEE[19,4]FFFF[22,3]GGG[24,2]HH", tree.AnnotatedString())
-		tree.Insert(newSplayNode("I"))
-		assert.Equal(t,
-			"[1,1]A[3,2]BB[6,3]CCC[10,4]DDDD[15,5]EEEEE[19,4]FFFF[22,3]GGG[24,2]HH[25,1]I",
-			tree.AnnotatedString())
+	t.Run("range delition test", func(t *testing.T) {
+		tree, nodes := makeSampleTree()
+		// check the filtering of DeleteRange
+		removeNodes(nodes, 7, 8)
+		tree.DeleteRange(nodes[6], nil)
+		assert.Equal(
+			t,
+			"[1,1]A[3,2]BB[6,3]CCC[10,4]DDDD[15,5]EEEEE[19,4]FFFF[22,3]GGG[0,0]HH[0,0]I",
+			tree.AnnotatedString(),
+		)
+
+		tree, nodes = makeSampleTree()
+		// check the case 1 of DeleteRange
+		removeNodes(nodes, 3, 6)
+		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",
+			tree.AnnotatedString(),
+		)
+
+		tree, nodes = makeSampleTree()
+		tree.Splay(nodes[6])
+		tree.Splay(nodes[2])
+		// check the case 2 of DeleteRange
+		removeNodes(nodes, 3, 7)
+		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",
+			tree.AnnotatedString(),
+		)
 	})
 }
+
+func makeSampleTree() (*splay.Tree[*stringValue], []*splay.Node[*stringValue]) {
+	tree := splay.NewTree[*stringValue](nil)
+	var nodes []*splay.Node[*stringValue]
+
+	nodes = append(nodes, tree.Insert(newSplayNode("A")))
+	nodes = append(nodes, tree.Insert(newSplayNode("BB")))
+	nodes = append(nodes, tree.Insert(newSplayNode("CCC")))
+	nodes = append(nodes, tree.Insert(newSplayNode("DDDD")))
+	nodes = append(nodes, tree.Insert(newSplayNode("EEEEE")))
+	nodes = append(nodes, tree.Insert(newSplayNode("FFFF")))
+	nodes = append(nodes, tree.Insert(newSplayNode("GGG")))
+	nodes = append(nodes, tree.Insert(newSplayNode("HH")))
+	nodes = append(nodes, tree.Insert(newSplayNode("I")))
+
+	return tree, nodes
+}
+
+// Make nodes in given range the same state as tombstone.
+func removeNodes(nodes []*splay.Node[*stringValue], from, to int) {
+	for i := from; i <= to; i++ {
+		nodes[i].Value().removed = true
+		nodes[i].InitWeight()
+	}
+}