Tree undo/redo index reconciliation fails with mixed char-level and block-level ops

[hackerwins]

Summary

When a Tree contains a mix of character-level (text insert/delete) and block-level (element replacement via editBulkByPath) operations in the undo history, redo() produces incorrect results or throws index is out of range errors. The reconcileOperation() logic in TreeEditOperation does not properly adjust stored indices when the tree size changes significantly between undo and redo.

Environment

• @yorkie-js/sdk version: 0.7.3-alpha (also reproducible on main)
• Single client (no server needed)

Reproduction

Test Case (add to history_tree_test.ts)

it('should handle undo/redo with mixed char-level and block-level ops', () => {
  const doc = new Document<{ t: Tree }>('test-doc');
  doc.update((root) => {
    root.t = new Tree({
      type: 'doc',
      children: [
        {
          type: 'p',
          children: [{ type: 'text', value: 'x' }],
        },
      ],
    });
  }, 'init');

  // Step 1: Character-level insert
  doc.update((root) => {
    root.t.editByPath([0, 0], [0, 0], { type: 'text', value: 'asdf' });
  }, 'type asdf');
  assert.equal(xmlOf(doc), '<doc><p>asdfx</p></doc>');

  // Step 2: Block-level replacement (split block — replace 1 block with 2)
  doc.update((root) => {
    root.t.editBulkByPath([0], [1], [
      { type: 'p', children: [{ type: 'text', value: 'asdf' }] },
      { type: 'p', children: [{ type: 'text', value: 'x' }] },
    ]);
  }, 'split block');
  assert.equal(xmlOf(doc), '<doc><p>asdf</p><p>x</p></doc>');

  // Step 3: Character-level insert in second block
  doc.update((root) => {
    root.t.editByPath([1, 0], [1, 0], { type: 'text', value: 'asdf' });
  }, 'type in block 2');
  assert.equal(xmlOf(doc), '<doc><p>asdf</p><p>asdfx</p></doc>');

  // Step 4: Undo all 3 operations
  doc.history.undo(); // → <doc><p>asdf</p><p>x</p></doc>
  doc.history.undo(); // → <doc><p>asdfx</p></doc>
  doc.history.undo(); // → <doc><p>x</p></doc>

  // Step 5: Redo all — this fails
  doc.history.redo();
  assert.equal(xmlOf(doc), '<doc><p>asdfx</p></doc>'); // ✅ OK

  doc.history.redo(); // Redo split
  // Expected: <doc><p>asdf</p><p>x</p></doc>
  // Actual:   <doc><p>asdf</p><p>asdfx</p></doc>  ← WRONG
  assert.equal(xmlOf(doc), '<doc><p>asdf</p><p>x</p></doc>');

  doc.history.redo();
  assert.equal(xmlOf(doc), '<doc><p>asdf</p><p>asdfx</p></doc>');
});

Results

Step	Expected	Actual	Status
Redo typing	<p>asdfx</p>	<p>asdfx</p>	✅
Redo split	<p>asdf</p><p>x</p>	<p>asdf</p><p>asdfx</p>	❌ Wrong content
Redo typing in block 2	<p>asdf</p><p>asdfx</p>	(depends on previous)	❌

In more complex scenarios (multiple blocks, Korean IME input), redo throws:

YorkieError: index is out of range: 18 > 15
  at findTreePos (index_tree.ts:770)
  at execute (tree_edit_operation.ts:144)
  at executeUndoRedo (document.ts:1940)

Root Cause Analysis

1. toReverseOperation() stores indices based on post-edit tree state

In tree_edit_operation.ts, when a reverse operation is created:

const reverseFromIdx = preEditFromIdx;
const reverseToIdx = preEditFromIdx + insertedContentSize;

For a block-level replacement (e.g., replacing a 7-unit <p> with two <p> elements totaling 14 units), reverseToIdx would be 0 + 14 = 14.

2. reconcileOperation() doesn't handle asymmetric tree sizes

When undo operations change the tree size (e.g., undo the split shrinks the tree), the redo stack's stored indices reference positions in the larger post-split tree. When redo is called on the smaller pre-split tree, tree.findPos(14) exceeds the tree's visibleSize.

The 6-case overlap logic in reconcileOperation() (lines 313-396) attempts to adjust indices, but:

• Cases 3-6 are marked as TODO(Phase 2) and skipped
• The reconciliation uses remote operation indices that may be from a different tree state
• There's no bounds check after reconciliation to ensure adjusted indices ≤ tree size

3. Single-client undo chain exposes the issue

Even without remote clients, a sequence of undo operations acts as "changes" that should trigger reconciliation on the redo stack. But redo entries' indices may not be properly adjusted when preceding undo operations change the tree structure.

Context

We discovered this while building Wafflebase, a collaborative document editor using Yorkie Tree CRDT. The editor performs block-level element replacements (replacing entire <p> elements) for operations like Enter (split block) and Backspace (merge blocks), mixed with character-level text insertions for typing.

The workaround of using only character-level operations for text editing (avoiding block-level replacement for typing) resolves the undo issue for typing, but split/merge still requires block-level operations where redo fails.

[hackerwins]

Additional reproduction: multi-client sync failure

The single-client fix in #1196 resolves local undo/redo, but syncing undo/redo operations to a remote client crashes during garbage collection.

Reproduction test

it('should sync mixed char+block ops and undo/redo to remote client', async ({ task }) => {
  type TestDoc = { t: Tree };
  await withTwoClientsAndDocuments<TestDoc>(async (c1, d1, c2, d2) => {
    d1.update((root) => {
      root.t = new Tree({
        type: 'doc',
        children: [{ type: 'p', children: [{ type: 'text', value: 'x' }] }],
      });
    }, 'init');
    await c1.sync();
    await c2.sync();

    // Client 1: char-level insert
    d1.update((root) => {
      root.t.editByPath([0, 0], [0, 0], { type: 'text', value: 'asdf' });
    }, 'type asdf');
    await c1.sync();
    await c2.sync();

    // Client 1: block-level split (replace 1 block with 2)
    d1.update((root) => {
      root.t.editBulkByPath([0], [1], [
        { type: 'p', children: [{ type: 'text', value: 'asdf' }] },
        { type: 'p', children: [{ type: 'text', value: 'x' }] },
      ]);
    }, 'split block');
    await c1.sync();
    await c2.sync();

    // Client 1: char-level insert in second block
    d1.update((root) => {
      root.t.editByPath([1, 0], [1, 0], { type: 'text', value: 'a' });
    }, 'type in block 2');
    await c1.sync();
    await c2.sync();

    // Client 1: undo all, syncing after each
    d1.history.undo();
    await c1.sync(); await c2.sync();
    d1.history.undo();
    await c1.sync(); await c2.sync();
    d1.history.undo();
    await c1.sync(); await c2.sync();

    // Client 1: redo — crashes on remote client during sync
    d1.history.redo();
    await c1.sync(); await c2.sync();
    d1.history.redo();  // redo split
    await c1.sync();
    await c2.sync();  // 💥 remote client crashes here
  }, task.name);
});

Error

TypeError: Cannot read properties of undefined (reading 'left')
  at LLRBTree.removeInternal (llrb_tree.ts:245)
  at CRDTTree.purge (tree.ts:1364)
  at CRDTRoot.garbageCollect (root.ts:355)
  at Document.applyChangePack (document.ts:1108)
  at Client.syncInternal (client.ts:1850)

The error occurs during garbage collection when the remote client syncs the redo operation. The CRDTTree.purge tries to remove a node from the internal LLRBTree index, but the node doesn't exist — likely because the preTombstoned filtering in #1196 removed it from the reverse operation's content, but it was still registered as a GC target.

Test file

Full test file with both single-client and multi-client cases:
history_tree_block_replace_test.ts (can be added to test/integration/)