Refine test codes in Tree to clearly describe feature specification

[sejongk]

Description:
Currently, test codes of CRDT play an important role in not only testing but also describing feature specifications.
However, due to increased complexity, the codes in Tree are unable to describe them clearly.

Why:

Problem

1. Vagueness of test names
   It is often challenging to identify the purpose of the test via its name at first glance.
   In addition, there are various formats of test names. For example, some of them use BDD(Behavior-driven development), but others use another format.

2. Inconsistency of test code format between Go SDK and JS SDK
   JS SDK utilizes a hierarchy of test cases, but Go SDK doesn't.

3. Lack of clarity of the range definition of Merge and Split operations
   Although both Merge and Split operations involve a ranged operation, the definition is not clear for the spec.

4. Possibility of the existence of more dimensions
   We currently use three dimensions to describe the spec, Edit type, Range type, and Node type.
   I doubt whether there are more dimensions that are not identified yet.

Solution

1. Define an universal and clear format for the test name

I suggest using BDD with three levels, each of which represents Edit type, Range type, Other dimensions(e.g. Node type, Position).

describe('Concurrent editing, insert and insert', () => {
  describe('In overlapping range', () => {
    it('With element and text At left position', function ({ task }) {

2. Make the format of test code of Go SDK consistent with that of JS SDK

Use Subtests in Go SDK to describe the hierarchy between test cases.

3. Define the exact range of Merge and Split operations

I think both Merge and Split operations can be divided into the Delete operation and the Insert operation.
After breaking down the operation, we can recognize the hidden operation range.

Split <p>a|b</p> -> <p>a</p><p>b</p>

• Tree.Edit: Edit(2,2, nil, 1)
• Sub-operations: Delete(2,3,nil,0) + Insert(4,4, '<p>b</p>', 0)
• Actual range: (2,3)

Merge <p>a</p><p>b</p> -> <p>a|b</p>

• Tree.Edit: Edit(2,4, nil, 0)
• Sub-operations: Delete(3,6,nil,0) + Insert(2,2, 'b', 0)
• Actual range: (3,6)

Concerning the exact range of operations, we can categorize them into Range types (e.g. overlapping, contained, side by side).

4. Find out the concealed dimensions

If there are many cases that aren't clearly defined by the current dimensions (Edit type, Range type, and Node type), we should figure out the common patterns and extract them into a new dimension.

Possible Combinations

Possible Edit Types

C: Collapsed, R: Ranged

• C + C
  • Insert + Insert (C + C)
• R + C
  • Delete + Insert (R + C)
  • Merge + Insert (R + C)
  • Split + Insert (R + C)
• R + R
  • Delete + Delete (R + R)
  • Delete + Merge (R + R)
  • Delete + Split (R + R)
  • Merge + Merge (R + R)
  • Merge + Split (R + R)
  • Split + Split (R + R)

Possible Range Types per Edit Type

• C + C
  • Side by Side
• R + C
  • Side by Side
  • Contained (R > C)
• R + R
  • Side by Side
  • Contained (R1 > R2)
  • Contained (R1 < R2)
  • Overlapping

Possible Element Types per Edit Type

• Split: Element
• Merge: Element
• Insert: Element, Text
• Delete: Element, Text

Overall

There are almost 50 possible cases, but I'm sure there will be additional cases and impossible cases among the below cases.
Therefore, it is better to use the below list as a reference.

• Insert + Insert (C + C)
  • Side by Side
    • Element - Element
    • Element - Text
    • Text - Text
• Delete + Insert (R + C)
  • Side by Side
    • Element - Element
    • Element - Text
    • Text - Text
  • Contained
    • Element - Element
    • Element - Text
    • Text - Text
• Merge + Insert (R + C)
  • Side by Side
    • Element - Element
    • Element - Text
  • Contained
    • Element - Element
    • Element - Text
• Split + Insert (R + C)
  • Side by Side
    • Element - Element
    • Element - Text
  • Side by Side
    • Element - Element
    • Element - Text
• Delete + Delete (R + R)
  • Side by Side
    • Element - Element
    • Element - Text
    • Text - Text
  • Contained
    • Element - Element
    • Element - Text
    • Text - Text
  • Overlapping
    • Element - Element
    • Element - Text
    • Text - Text
• Delete + Merge (R + R)
  • Side by Side
    • Element - Element
    • Text - Element
  • Contained
    • Element - Element (Delete > Merge)
    • Element - Element (Delete < Merge)
    • Text - Element (Delete < Merge)
  • Overlapping
    • Element - Element
    • Text - Element
• Delete + Split (R + R)
  • Side by Side
    • Element - Element
    • Text - Element
  • Contained
    • Element - Element
    • Text - Element
  • Overlapping
    • Element - Element
    • Text - Element
• Merge + Merge (R + R)
  • Side by Side
    • Element - Element
  • Contained
    • Element - Element
  • Overlapping
    • Element - Element
• Merge + Split (R + R)
  • Side by Side
    • Element - Element
  • Contained
    • Element - Element
• Split + Split (R + R)
  • Side by Side
    • Element - Element
  • Contained
    • Element - Element
  • Overlapping
    • Element - Element

[hackerwins]

• Go SDK: Add merge and split concurrency tests #780
• JS SDK: Add Tree concurrency tests yorkie-js-sdk#792

[hackerwins]

This was fixed by #780