Repository: yorkie-team/yorkie
Pull request #545 (2023-06-07 15:50:48)

Support UTF16 Code Units in yorkie.Tree
<!--  Thanks for sending a pull request! -->

**What this PR does / why we need it**:

Support UTF16 code units with rune in yorkie.Tree.

This is to support yorkie.Tree to handle multilingual.

Because previous yorkie.Tree did not support this, there was a bug when splitting text nodes that contains other languages like Korean (eg: splitting text node `한글` with offset of `2` resulted something like `�`, `글`, `��`). 

And because of this, tree structure got corrupted, leading to misbehavior of tree edit operation and failure of snapshot(bytes) conversion.

**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/crdt/tree.go b/pkg/document/crdt/tree.go
index b5598d0c..5a439ee5 100644
--- a/pkg/document/crdt/tree.go
+++ b/pkg/document/crdt/tree.go
@@ -20,6 +20,7 @@ import (
 	"errors"
 	"fmt"
 	"strings"
+	"unicode/utf16"
 
 	"github.com/yorkie-team/yorkie/pkg/document/time"
 	"github.com/yorkie-team/yorkie/pkg/index"
@@ -127,7 +128,8 @@ func (n *TreeNode) IsRemoved() bool {
 
 // Length returns the length of this node.
 func (n *TreeNode) Length() int {
-	return len(n.Value)
+	encoded := utf16.Encode([]rune(n.Value))
+	return len(encoded)
 }
 
 // String returns the string representation of this node.
@@ -175,16 +177,17 @@ func (n *TreeNode) SplitText(offset int) *TreeNode {
 		return nil
 	}
 
-	leftValue := n.Value[:offset]
-	rightValue := n.Value[offset:]
+	encoded := utf16.Encode([]rune(n.Value))
+	leftRune := utf16.Decode(encoded[0:offset])
+	rightRune := utf16.Decode(encoded[offset:])
 
-	n.Value = leftValue
-	n.IndexTreeNode.Length = len(leftValue)
+	n.Value = string(leftRune)
+	n.IndexTreeNode.Length = len(leftRune)
 
 	rightNode := NewTreeNode(&TreePos{
 		CreatedAt: n.Pos.CreatedAt,
 		Offset:    offset,
-	}, n.Type(), rightValue)
+	}, n.Type(), string(rightRune))
 	n.IndexTreeNode.Parent.InsertAfterInternal(rightNode.IndexTreeNode, n.IndexTreeNode)
 
 	return rightNode


Test patch:
diff --git a/api/converter/converter_test.go b/api/converter/converter_test.go
index ca7c5b76..c247913a 100644
--- a/api/converter/converter_test.go
+++ b/api/converter/converter_test.go
@@ -113,6 +113,16 @@ func TestConverter(t *testing.T) {
 				Increase(10).
 				Increase(math.MaxInt64)
 
+			// tree
+			root.SetNewTree("k5").
+				Edit(0, 0, &json.TreeNode{
+					Type: "p",
+					Children: []json.TreeNode{{
+						Type:  "text",
+						Value: "Hello world",
+					}},
+				})
+
 			return nil
 		})
 		assert.NoError(t, err)
diff --git a/pkg/document/crdt/tree_test.go b/pkg/document/crdt/tree_test.go
index 2b5fa9eb..efbbacae 100644
--- a/pkg/document/crdt/tree_test.go
+++ b/pkg/document/crdt/tree_test.go
@@ -54,6 +54,28 @@ func TestTreeNode(t *testing.T) {
 		assert.Equal(t, &crdt.TreePos{CreatedAt: time.InitialTicket, Offset: 0}, left.Pos)
 		assert.Equal(t, &crdt.TreePos{CreatedAt: time.InitialTicket, Offset: 5}, right.Pos)
 	})
+
+	t.Run("UTF-16 code unit test", func(t *testing.T) {
+		tests := []struct {
+			length int
+			value  string
+		}{
+			{4, "abcd"},
+			{6, "우리나라한글"},
+			{8, "अनुच्छेद"},
+			{10, "Ĺo͂řȩm̅"},
+			{12, "🌷🎁💩😜👍🏳"},
+		}
+		for _, test := range tests {
+			para := crdt.NewTreeNode(crdt.DummyTreePos, "p")
+			para.Append(crdt.NewTreeNode(crdt.DummyTreePos, "text", test.value))
+
+			left := para.Child(0)
+			assert.Equal(t, test.length, left.Len())
+			right := left.Split(2)
+			assert.Equal(t, test.length-2, right.Len())
+		}
+	})
 }
 
 func TestTree(t *testing.T) {