Skip to content

Use native Yorkie Tree split/merge for concurrent convergence#126

Merged
hackerwins merged 10 commits into
mainfrom
feat/native-split-merge
Apr 13, 2026
Merged

Use native Yorkie Tree split/merge for concurrent convergence#126
hackerwins merged 10 commits into
mainfrom
feat/native-split-merge

Conversation

@hackerwins

@hackerwins hackerwins commented Apr 13, 2026

Copy link
Copy Markdown
Collaborator

Summary

  • Upgrade @yorkie-js/sdk and @yorkie-js/react to 0.7.4
  • Replace block-replacement split/merge in YorkieDocStore with native Yorkie Tree CRDT operations
  • splitBlock: 2× editByPath (block replace + insert) → single atomic editByPath(path, path, undefined, 2) + styleByPath
  • mergeBlock: 2× editByPath (block replace + delete) → single boundary deletion editByPath
  • Add concurrent integration tests verifying convergence with two Yorkie clients

Motivation

Previously, split (Enter key) and merge (Backspace at paragraph start) used block replacement — two independent editByPath calls that are LWW (Last-Writer-Wins). When two users press Enter in the same paragraph simultaneously, one split was lost.

With SDK 0.7.4's convergence fixes, native Tree split/merge operations preserve both edits as atomic CRDT operations.

splitLevel=2

Yorkie's splitLevel counts element ancestors from the text position upward (text nodes excluded). Our tree structure doc → block → inline → text requires splitLevel=2 to reach block level: inline (level 1) → block (level 2).

Concurrent Integration Test Results

Test Result
split + text insert (same paragraph) ✅ Converged
split + split (same paragraph, different offsets) ✅ Converged
merge + text insert ✅ Converged
split + merge (adjacent blocks) ✅ Converged
split + text delete ✅ Converged

Known Limitations

  • Two integration tests remain skipped in Yorkie SDK — concurrently-split-split-test and concurrently-split-edit-test — both involve mixed splitLevel values on deeply nested trees. Our uniform splitLevel=2 on a flat block list is a narrower pattern and converges correctly.
  • Header/footer split/merge unchanged (uses writeFullDocument)
  • Table cell internal split/merge deferred to Phase 4

Test plan

  • pnpm verify:fast passes
  • 9 new unit tests for splitBlock/mergeBlock (round-trip, styled inlines, edge cases)
  • 5 concurrent integration tests with two Yorkie clients (YORKIE_RPC_ADDR=http://localhost:8080 pnpm frontend test:integration)
  • Manual QA: open two browser tabs, split/merge in the same paragraph concurrently

🤖 Generated with Claude Code

Summary by CodeRabbit

  • Documentation

    • Updated design guidance for block-level split/merge behavior and known-risks/limitations.
  • Refactor

    • Switched block split/merge to native structural operations for more robust editing behavior.
  • Chores

    • Bumped Yorkie JS SDK dependencies to v0.7.4 in backend and frontend packages.
  • Tests

    • Added unit and integration tests plus a two-client test helper to validate concurrent split/merge and sync convergence.

Replace two editByPath calls (block replacement + insert) with a single
editByPath(path, path, undefined, 2) atomic CRDT split. This enables
concurrent split convergence — two users pressing Enter in the same
paragraph both produce correct results instead of LWW conflict.
Replace two editByPath calls (block replacement + delete) with a single
boundary deletion that triggers automatic CRDT merge. This preserves
concurrent text edits during merge — if one user merges while another
types, both edits survive.
Document the SDK 0.7.4 native split/merge strategy: splitLevel=2 for
block-level CRDT split, boundary deletion for merge. Note known
concurrent edge cases from upstream skipped tests.
Verify native Yorkie Tree split/merge convergence with two clients:
- split + text insert (same paragraph)
- split + split (same paragraph, different offsets)
- merge + text insert
- split + merge (adjacent blocks)
- split + text delete

All 5 tests converge correctly with SDK 0.7.4. Requires Yorkie server.
@coderabbitai

coderabbitai Bot commented Apr 13, 2026

Copy link
Copy Markdown

Warning

Rate limit exceeded

@hackerwins has exceeded the limit for the number of commits that can be reviewed per hour. Please wait 2 minutes and 20 seconds before requesting another review.

Your organization is not enrolled in usage-based pricing. Contact your admin to enable usage-based pricing to continue reviews beyond the rate limit, or try again in 2 minutes and 20 seconds.

⌛ How to resolve this issue?

After the wait time has elapsed, a review can be triggered using the @coderabbitai review command as a PR comment. Alternatively, push new commits to this PR.

We recommend that you space out your commits to avoid hitting the rate limit.

🚦 How do rate limits work?

CodeRabbit enforces hourly rate limits for each developer per organization.

Our paid plans have higher rate limits than the trial, open-source and free plans. In all cases, we re-allow further reviews after a brief timeout.

Please see our FAQ for further information.

ℹ️ Review info
⚙️ Run configuration

Configuration used: defaults

Review profile: CHILL

Plan: Pro

Run ID: 7f99372f-578e-462e-a667-633b847d6429

📥 Commits

Reviewing files that changed from the base of the PR and between cd1f831 and 5fe6cc0.

📒 Files selected for processing (1)
  • packages/frontend/src/app/docs/yorkie-doc-store.ts
📝 Walkthrough

Walkthrough

Refactors split/merge to use Yorkie Tree native operations: split via editByPath(..., splitLevel=2) + styleByPath, merge via boundary deletion editByPath to let the CRDT combine blocks. Adds tests, test helpers, and bumps Yorkie SDK/react versions.

Changes

Cohort / File(s) Summary
Design Documentation
docs/design/docs/docs-intent-preserving-edits.md
Updated strategy: Split uses native Yorkie Tree split (editByPath(..., splitLevel=2)) plus styleByPath; Merge uses boundary deletion. Revised known issues and added native-split divergence risk; LWW scoped to style ops.
Dependencies
packages/backend/package.json, packages/frontend/package.json
Bumped @yorkie-js/sdk 0.7.3 → 0.7.4 (both); bumped @yorkie-js/react 0.7.3 → 0.7.4 (frontend).
Core Store Implementation
packages/frontend/src/app/docs/yorkie-doc-store.ts
Replaced block-replace semantics with native tree split (resolve offset → editByPath(..., undefined, 2)) and styleByPath for after-block attrs; merge implemented as boundary deletion editByPath([blockIdx, inlineCount],[nextIdx,0]) with adjacency check; cache updates retained.
Integration Tests (concurrent)
packages/frontend/tests/app/docs/yorkie-doc-store-concurrent.integration.ts
Added multi-case two-user integration suite exercising concurrent split/merge scenarios (split+insert, split+split, merge+insert, split+merge, split+delete) with convergence assertions.
Unit Tests
packages/frontend/tests/app/docs/yorkie-doc-store.test.ts
Added/extended unit tests for splitBlock and mergeBlock: edge offsets, inline style preservation, block attributes for headings/list-items, merge invariants, and split-then-merge round-trip.
Test Helpers
packages/frontend/tests/helpers/two-user-docs-yorkie.ts
New Yorkie-backed test helper: createTwoUserDocs, TwoUserDocsContext, makeBlock, createClient, and syncClients to coordinate two-client integration tests and cleanup.

Sequence Diagram(s)

sequenceDiagram
    participant User
    participant Store as YorkieDocStore
    participant Tree as Yorkie Tree CRDT
    participant Styler as styleByPath

    User->>Store: splitBlock(blockIdx, offset)
    Store->>Store: resolveOffset() -> (inlineIndex,charOffset)
    Store->>Tree: editByPath(inlinePath, undefined, splitLevel=2)
    Tree-->>Store: split performed, new "after" block node
    Store->>Styler: styleByPath(afterBlockPath, afterAttrs)
    Styler-->>Tree: apply attributes to after block
    Store->>Store: update in-memory cache (applySplitBlock)
    Store-->>User: return split result
Loading
sequenceDiagram
    participant User
    participant Store as YorkieDocStore
    participant Tree as Yorkie Tree CRDT

    User->>Store: mergeBlock(blockIdx)
    Store->>Store: verify adjacency, compute boundary ([blockIdx,end] -> [nextIdx,0])
    Store->>Tree: editByPath([blockIdx, inlineCount], [nextIdx, 0])
    Tree-->>Store: delete boundary range, CRDT merges blocks
    Store->>Store: update in-memory cache (applyMerge/compute merged)
    Store-->>User: return merged result
Loading

Estimated code review effort

🎯 4 (Complex) | ⏱️ ~60 minutes

Possibly related PRs

Poem

🐰 I nibbled lines where branches part,

Split with care, then stitched the heart,
CRDT dances, styles stay true,
Two clients hop — convergence anew! ✨

🚥 Pre-merge checks | ✅ 2 | ❌ 1

❌ Failed checks (1 warning)

Check name Status Explanation Resolution
Docstring Coverage ⚠️ Warning Docstring coverage is 60.00% which is insufficient. The required threshold is 80.00%. Write docstrings for the functions missing them to satisfy the coverage threshold.
✅ Passed checks (2 passed)
Check name Status Explanation
Description Check ✅ Passed Check skipped - CodeRabbit’s high-level summary is enabled.
Title check ✅ Passed The pull request title clearly and specifically describes the main change: migrating from block-replacement split/merge operations to native Yorkie Tree CRDT operations for improved concurrent convergence.

✏️ Tip: You can configure your own custom pre-merge checks in the settings.

✨ Finishing Touches
🧪 Generate unit tests (beta)
  • Create PR with unit tests
  • Commit unit tests in branch feat/native-split-merge

Thanks for using CodeRabbit! It's free for OSS, and your support helps us grow. If you like it, consider giving us a shout-out.

❤️ Share

Comment @coderabbitai help to get the list of available commands and usage tips.

@github-actions

github-actions Bot commented Apr 13, 2026

Copy link
Copy Markdown
Contributor

Verification: verify:self

Result: ✅ PASS in 116.4s

Lane Status Duration
sheets:build ✅ pass 12.4s
docs:build ✅ pass 7.5s
verify:fast ✅ pass 58.5s
frontend:build ✅ pass 16.3s
verify:frontend:chunks ✅ pass 0.3s
backend:build ✅ pass 4.8s
cli:build ✅ pass 1.8s
verify:entropy ✅ pass 14.8s

Verification: verify:integration

Result: ✅ PASS

@codecov

codecov Bot commented Apr 13, 2026

Copy link
Copy Markdown

Codecov Report

✅ All modified and coverable lines are covered by tests.

📢 Thoughts on this report? Let us know!

@coderabbitai coderabbitai Bot left a comment

Copy link
Copy Markdown

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Actionable comments posted: 4

🤖 Prompt for all review comments with AI agents
Verify each finding against the current code and only fix it if needed.

Inline comments:
In `@packages/frontend/src/app/docs/yorkie-doc-store.ts`:
- Around line 850-858: The tree.editByPath call can delete a wide range when
nextIdx is not directly adjacent to blockIdx; before calling tree.editByPath
(and before the corresponding cache removal logic handling nextIdx), validate
that nextIdx === blockIdx + 1 and reject or bail out otherwise to avoid deleting
intermediate blocks; update the guard inside this.doc.update (around the tree
variable and the existing editByPath invocation) to check adjacency and only
perform tree.editByPath([blockIdx + off, firstBlockInlineCount], [nextIdx + off,
0]) when that adjacency holds, and apply the same adjacency check to the
analogous code block handling lines ~861-868 so local cache updates remain
consistent with Yorkie edits.

In `@packages/frontend/tests/app/docs/yorkie-doc-store-concurrent.integration.ts`:
- Around line 41-50: Replace the current equality checks that only compare
textA/textB/fullText with a structural comparison of normalized block snapshots
from docA and docB: implement a small normalizer (e.g.,
normalizeBlocks(doc.blocks)) that maps each block to a canonical shape
containing stable identifiers relevant to behavior (block type, list/heading
attrs, children count, and the joined inline text) and then assert deep equality
between normalizeBlocks(docA.blocks) and normalizeBlocks(docB.blocks) as well as
the expected presence/length of inserted text ("XXX") in the joined inline text;
update the assertions around variables docA, docB, textA/textB/fullText to use
normalizeBlocks and assert.deepEqual on those snapshots so metadata mismatches
(IDs/types/attrs) fail the test.

In `@packages/frontend/tests/app/docs/yorkie-doc-store.test.ts`:
- Around line 350-465: Add tests covering block-level attributes when splitting:
within the existing splitBlock suite add one test that splits a heading block
into a paragraph (e.g., create a Block with type 'heading' and headingLevel set,
call store.splitBlock(block.id, offset, 'new-id', 'paragraph') and assert the
first block keeps headingLevel and the new block has type 'paragraph' and
correct attrs), and another test that splits a list-item into another list-item
(create a Block with type 'list-item' and listKind/listLevel set, call
store.splitBlock(..., 'list-item'), then assert both resulting blocks preserve
listKind/listLevel); reference store.splitBlock, makeBlock or direct Block
literal, generateBlockId and DEFAULT_BLOCK_STYLE to locate where to add these
cases.

In `@packages/frontend/tests/helpers/two-user-docs-yorkie.ts`:
- Around line 81-100: Wrap the setup sequence that calls clientA.activate(),
clientB.activate(), clientA.attach(...), storeA.setDocument(...),
clientA.sync(...), clientB.attach(...), and syncClients(...) in a try/catch; in
the catch block perform the same cleanup you do on success (call
detach/deactivate on clientA and clientB and any doc detach as appropriate) and
then rethrow the error so activated clients/sessions are always torn down on
failure.
🪄 Autofix (Beta)

Fix all unresolved CodeRabbit comments on this PR:

  • Push a commit to this branch (recommended)
  • Create a new PR with the fixes

ℹ️ Review info
⚙️ Run configuration

Configuration used: defaults

Review profile: CHILL

Plan: Pro

Run ID: b6c68c64-d432-4ced-a24b-67ff0c3344ad

📥 Commits

Reviewing files that changed from the base of the PR and between 5779065 and 659571d.

⛔ Files ignored due to path filters (1)
  • pnpm-lock.yaml is excluded by !**/pnpm-lock.yaml
📒 Files selected for processing (7)
  • docs/design/docs/docs-intent-preserving-edits.md
  • packages/backend/package.json
  • packages/frontend/package.json
  • packages/frontend/src/app/docs/yorkie-doc-store.ts
  • packages/frontend/tests/app/docs/yorkie-doc-store-concurrent.integration.ts
  • packages/frontend/tests/app/docs/yorkie-doc-store.test.ts
  • packages/frontend/tests/helpers/two-user-docs-yorkie.ts

Comment thread packages/frontend/src/app/docs/yorkie-doc-store.ts
Comment thread packages/frontend/tests/app/docs/yorkie-doc-store-concurrent.integration.ts Outdated
Comment thread packages/frontend/tests/app/docs/yorkie-doc-store.test.ts
Comment thread packages/frontend/tests/helpers/two-user-docs-yorkie.ts Outdated
- Guard non-adjacent block merge with adjacency check
- Add heading and list-item split attribute tests
- Use structural block comparison in integration tests
- Clean up Yorkie clients on setup failure in test helper

@coderabbitai coderabbitai Bot left a comment

Copy link
Copy Markdown

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Actionable comments posted: 1

♻️ Duplicate comments (2)
packages/frontend/src/app/docs/yorkie-doc-store.ts (1)

835-848: ⚠️ Potential issue | 🟠 Major

Apply the adjacency check in the header/footer branch too.

The new guard only protects body merges. If both IDs resolve into the same header/footer, this branch still merges reversed or non-adjacent blocks and deletes only hf2, which can corrupt that region.

🐛 Suggested fix
     const hf1 = this.findHeaderFooterBlock(blockId, currentDoc);
     const hf2 = this.findHeaderFooterBlock(nextBlockId, currentDoc);
     if (hf1 && hf2 && hf1.region === hf2.region) {
+      if (hf2.index !== hf1.index + 1) {
+        throw new Error('Blocks to merge must be adjacent and in order');
+      }
       const merged = applyMergeBlocks(hf1.blocks[hf1.index], hf2.blocks[hf2.index]);
       hf1.blocks[hf1.index] = merged;
       hf1.blocks.splice(hf2.index, 1);
       this.commitHeaderFooterChange(currentDoc);
       return;
🤖 Prompt for AI Agents
Verify each finding against the current code and only fix it if needed.

In `@packages/frontend/src/app/docs/yorkie-doc-store.ts` around lines 835 - 848,
The header/footer merge branch (using findHeaderFooterBlock, hf1/hf2,
applyMergeBlocks and commitHeaderFooterChange) lacks the adjacency/order check
present for body blocks, so it can merge non-adjacent or reversed header/footer
blocks and corrupt the region; add the same validation you use for body merges:
when hf1 && hf2 && hf1.region === hf2.region ensure hf2.index and hf1.index
exist and that hf2.index === hf1.index + 1 (or otherwise enforce adjacency and
correct order), throw an Error like 'Blocks to merge must be adjacent and in
order' if the check fails, and only then perform the applyMergeBlocks, replace
hf1.blocks[hf1.index] with merged, splice hf2.index, and call
commitHeaderFooterChange.
packages/frontend/tests/helpers/two-user-docs-yorkie.ts (1)

81-95: ⚠️ Potential issue | 🟠 Major

Move client activation inside the guarded setup path.

clientA.activate() and clientB.activate() still run before the try. If clientB.activate() throws, clientA stays active and the catch cleanup never runs.

♻️ Suggested fix
-  await clientA.activate();
-  await clientB.activate();
-
   const cleanup = async () => {
     await Promise.allSettled([
       clientA.detach(docA),
       clientB.detach(docB),
     ]);
@@
   };
 
   try {
+    await clientA.activate();
+    await clientB.activate();
+
     // Client A creates the initial document with a Tree
     await clientA.attach(docA, {
       syncMode: SyncMode.Manual,
     });

Also applies to: 125-127

🤖 Prompt for AI Agents
Verify each finding against the current code and only fix it if needed.

In `@packages/frontend/tests/helpers/two-user-docs-yorkie.ts` around lines 81 -
95, Move the client activations into the guarded setup so partial activation
can't leak: call clientA.activate() and clientB.activate() inside the try (or
before entering try but only after both clients are constructed and within a
try/finally block) so that the cleanup function (which calls clientA.detach,
clientB.detach, clientA.deactivate, clientB.deactivate) always runs in the
finally/catch path; adjust the surrounding block around clientA.activate,
clientB.activate, the existing cleanup constant, and the try/finally so any
exception from clientB.activate triggers the cleanup for clientA via the finally
block.
🤖 Prompt for all review comments with AI agents
Verify each finding against the current code and only fix it if needed.

Inline comments:
In `@packages/frontend/src/app/docs/yorkie-doc-store.ts`:
- Around line 788-806: Before calling the native split (the tree.editByPath
invocation inside this.doc.update in splitBlock), validate that the target block
is a splittable text block: use the same block obtained from
currentDoc.blocks[blockIdx] and check its shape/type or presence of inline
children (i.e., that resolveOffset returned a valid inlineIndex and that
block.inline/children[inlineIndex] exists and contains text content) and bail
out early (throw or return) for non-text blocks like table, horizontal-rule, or
page-break so you never call tree.editByPath with an invalid Yorkie path.

---

Duplicate comments:
In `@packages/frontend/src/app/docs/yorkie-doc-store.ts`:
- Around line 835-848: The header/footer merge branch (using
findHeaderFooterBlock, hf1/hf2, applyMergeBlocks and commitHeaderFooterChange)
lacks the adjacency/order check present for body blocks, so it can merge
non-adjacent or reversed header/footer blocks and corrupt the region; add the
same validation you use for body merges: when hf1 && hf2 && hf1.region ===
hf2.region ensure hf2.index and hf1.index exist and that hf2.index === hf1.index
+ 1 (or otherwise enforce adjacency and correct order), throw an Error like
'Blocks to merge must be adjacent and in order' if the check fails, and only
then perform the applyMergeBlocks, replace hf1.blocks[hf1.index] with merged,
splice hf2.index, and call commitHeaderFooterChange.

In `@packages/frontend/tests/helpers/two-user-docs-yorkie.ts`:
- Around line 81-95: Move the client activations into the guarded setup so
partial activation can't leak: call clientA.activate() and clientB.activate()
inside the try (or before entering try but only after both clients are
constructed and within a try/finally block) so that the cleanup function (which
calls clientA.detach, clientB.detach, clientA.deactivate, clientB.deactivate)
always runs in the finally/catch path; adjust the surrounding block around
clientA.activate, clientB.activate, the existing cleanup constant, and the
try/finally so any exception from clientB.activate triggers the cleanup for
clientA via the finally block.
🪄 Autofix (Beta)

Fix all unresolved CodeRabbit comments on this PR:

  • Push a commit to this branch (recommended)
  • Create a new PR with the fixes

ℹ️ Review info
⚙️ Run configuration

Configuration used: defaults

Review profile: CHILL

Plan: Pro

Run ID: 7db45cb1-3024-4a39-b78d-386feea8dc32

📥 Commits

Reviewing files that changed from the base of the PR and between 659571d and cd1f831.

📒 Files selected for processing (4)
  • packages/frontend/src/app/docs/yorkie-doc-store.ts
  • packages/frontend/tests/app/docs/yorkie-doc-store-concurrent.integration.ts
  • packages/frontend/tests/app/docs/yorkie-doc-store.test.ts
  • packages/frontend/tests/helpers/two-user-docs-yorkie.ts
✅ Files skipped from review due to trivial changes (1)
  • packages/frontend/tests/app/docs/yorkie-doc-store-concurrent.integration.ts
🚧 Files skipped from review as they are similar to previous changes (1)
  • packages/frontend/tests/app/docs/yorkie-doc-store.test.ts

Comment thread packages/frontend/src/app/docs/yorkie-doc-store.ts
@hackerwins
hackerwins merged commit a7f429a into main Apr 13, 2026
4 checks passed
@hackerwins
hackerwins deleted the feat/native-split-merge branch April 13, 2026 06:58
hackerwins added a commit that referenced this pull request Apr 13, 2026
Replace block-replacement split/merge in YorkieDocStore with native
Yorkie Tree CRDT operations (SDK 0.7.4), enabling concurrent
convergence instead of last-writer-wins.

- splitBlock: atomic editByPath(path, path, undefined, 2) + styleByPath
- mergeBlock: single boundary deletion editByPath
- Adjacency guard on mergeBlock, block-type guard on splitBlock
- 11 unit tests (split/merge, round-trip, heading/list-item attrs)
- 5 concurrent integration tests with two Yorkie clients
- Design doc updated for native split/merge strategy

Co-authored-by: Claude Opus 4.6 (1M context) <[email protected]>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

1 participant