TextRope - Collaborative Text CRDT

TextRope is a high-performance text CRDT (Conflict-free Replicated Data Type) for real-time collaborative text editing. It's based on the 5000x faster CRDTs approach by Joseph Gentle, using the YATA ordering algorithm.

See Operations for text operation types that work with TextRope.

Features

YATA ordering - Consistent ordering for concurrent edits with reduced interleaving
Run-length encoding - Multi-character spans for memory efficiency
Span splitting - Handles mid-span insertions correctly
B-tree backed - O(log n) insertions and position lookups via a balanced tree
Compact snapshots - Remove tombstones for efficient storage

Quick Example

Text operations follow the same pattern as other operations in the graph:

typescript

import { createEmptyGraph, applyMessage } from '@vuer-ai/vuer-rtc';

let graph = createEmptyGraph();
let lamport = 0;

const msg = (ops) => ({
  id: `msg-${++lamport}`,
  sessionId: 'alice',
  clock: { alice: lamport },
  lamportTime: lamport,
  timestamp: Date.now(),
  ops,
});

// Create a text document node
graph = applyMessage(graph, msg([
  { ot: 'node.insert', key: '', path: 'children',
    value: { key: 'doc-1', tag: 'TextDocument', name: 'My Doc' } },
]));

// Initialize text content
graph = applyMessage(graph, msg([
  { ot: 'text.init', key: 'doc-1', path: 'content', value: 'Hello' },
]));

// Insert more text
graph = applyMessage(graph, msg([
  { ot: 'text.insert', key: 'doc-1', path: 'content', position: 5, value: [null, ' World'] },
]));

console.log(graph.nodes['doc-1'].content);  // "Hello World"

// Delete text
graph = applyMessage(graph, msg([
  { ot: 'text.delete', key: 'doc-1', path: 'content', position: 5, length: 6 },
]));

console.log(graph.nodes['doc-1'].content);  // "Hello"

Text Operations

Operation	Description	Example
`text.init`	Initialize text property	`{ ot: 'text.init', key: 'doc-1', path: 'content', value: 'Hello' }`
`text.insert`	Insert at position	`{ ot: 'text.insert', key: 'doc-1', path: 'content', position: 5, value: [null, ' World'] }`
`text.delete`	Delete at position	`{ ot: 'text.delete', key: 'doc-1', path: 'content', position: 0, length: 6 }`
`text.replace`	Atomic delete + insert	`{ ot: 'text.replace', key: 'doc-1', path: 'content', position: 0, length: 5, value: [null, 'Hi'] }`

Important: Use text.replace instead of separate text.delete + text.insert when replacing a selection. The edit buffer deduplicates by key:path, so a delete followed by an insert on the same key and path will lose the delete. text.replace performs both atomically in a single operation.

Multi-User Collaboration

When multiple users edit concurrently, the CRDT ensures convergence:

typescript

// Alice's graph
let graphA = createEmptyGraph();
graphA = applyMessage(graphA, msgA([
  { ot: 'node.insert', key: '', path: 'children',
    value: { key: 'doc-1', tag: 'TextDocument', name: 'Shared Doc' } },
  { ot: 'text.init', key: 'doc-1', path: 'content', value: 'Hello' },
]));

// Bob syncs Alice's state
let graphB = graphA;

// Alice inserts at the beginning
const aliceOp = msgA([
  { ot: 'text.insert', key: 'doc-1', path: 'content', position: 0, value: [null, 'A: '] },
]);
graphA = applyMessage(graphA, aliceOp);

// Bob inserts at the end (concurrently)
const bobOp = msgB([
  { ot: 'text.insert', key: 'doc-1', path: 'content', position: 5, value: [null, ' -Bob'] },
]);
graphB = applyMessage(graphB, bobOp);

// Sync operations
graphA = applyMessage(graphA, bobOp);
graphB = applyMessage(graphB, aliceOp);

// Both converge
console.log(graphA.nodes['doc-1'].content);  // "A: Hello -Bob"
console.log(graphB.nodes['doc-1'].content);  // "A: Hello -Bob"

Accessing the TextRope

typescript

import { getTextDocument } from '@vuer-ai/vuer-rtc';

const rope = getTextDocument(graph, 'doc-1', 'content');

console.log(rope?.items);     // Internal items
console.log(rope?.agentId);   // Agent ID
console.log(rope?.clock);     // Lamport clock

Standalone Usage

Use the functional API directly without the graph:

typescript

import {
  create, getText, insert, remove, replace,
  apply, applyDelete, applyReplace, toRaw, fromRaw,
} from '@vuer-ai/vuer-rtc/crdt';

// Create a rope — returns a TextRope class instance
const rope = create('agent-1');

// insert() mutates rope and returns an InsertOp for syncing
const op1 = insert(rope, 0, 'Hello');
const op2 = insert(rope, 5, ' World');
console.log(getText(rope));  // "Hello World"

// remove() mutates rope and returns a DeleteOp
const op3 = remove(rope, 5, 6);
console.log(getText(rope));  // "Hello"

// replace() does delete + insert atomically
const op4 = replace(rope, 0, 5, 'Hi');
console.log(getText(rope));  // "Hi"

// Sync to another rope
const rope2 = create('agent-2');
apply(rope2, op1);
apply(rope2, op2);
console.log(getText(rope2));  // "Hello World"

// Save to storage (minimal format)
const raw = toRaw(rope);
localStorage.setItem('doc', JSON.stringify(raw));

// Restore from storage
const restored = fromRaw(JSON.parse(localStorage.getItem('doc')!));

Operations are plain data objects. The edit journal vs committed journal distinction happens at a higher level.

TextRope Data Structure

TextRope is a class instance backed by a B-tree for O(log n) operations:

typescript

class TextRope {
  _tree: ItemTree;                       // B-tree of text spans
  _agentIndex: Map<string, SpanEntry[]>; // Per-agent sorted index for O(log m) ID lookups
  agentId: string;                       // This agent's ID
  clock: number;                         // Local sequence counter
  maxSeq: number;                        // Max Lamport timestamp seen
}

interface Item {
  id: ItemId;              // Unique identifier { agent, seq }
  content: string;         // Text content
  isDeleted: boolean;      // Tombstone flag
  parentId: ItemId | null; // Insert position reference
  seq: number;             // Lamport timestamp
}

Snapshots

typescript

// Full snapshot (includes tombstones)
const snap = snapshot(rope);

// Compacted snapshot (removes tombstones, merges consecutive spans)
const compacted = compact(rope);

// Restore from snapshot
const restored = fromSnapshot(snap);

// Restore with new agent ID
const newSession = fromSnapshot(snap, 'new-agent-id');

Use compact() for storage when you don't need undo history.

Raw Format (Minimal Storage)

For maximum storage efficiency, use toRaw() and fromRaw():

typescript

import { toRaw, fromRaw, type RawTextRope } from '@vuer-ai/vuer-rtc/crdt';

// Convert to raw array format
const raw: RawTextRope = toRaw(rope);
// Format: [agentId, clock, maxSeq, [[agent, seq, content, parentAgent, parentSeq], ...]]

// Store as JSON (very compact)
const json = JSON.stringify(raw);

// Restore from raw
const restored = fromRaw(raw);

// Restore with new agent ID
const newSession = fromRaw(raw, 'new-agent-id');

The raw format removes all tombstones and uses positional arrays instead of objects for minimal size.

Design Philosophy

TextRope uses a class + standalone functions pattern:

Class instance: TextRope is a class with internal B-tree and agent index — this ensures immutable state libraries (like Immer) skip it rather than wrapping its internals in proxies
Standalone functions: All operations (insert, remove, getText, etc.) are pure functions that take the rope as the first argument
Factory function: create('agent-id') returns a new TextRope instance
Serializable via snapshots: Use snapshot(rope) / fromSnapshot(snap) or toRaw(rope) / fromRaw(raw) for storage

This design allows:

O(log n) insertions and lookups via the B-tree backing
Safe deep-cloning via snapshot() (important for state management — prevents mutation of previous states)
Works with any framework (React, Vue, etc.)
Agent-seq index for O(log m) ID lookups without invalidation

API Reference

Functions

Function	Description
`create(agentId)`	Create a new TextRope
`getText(rope)`	Get visible text content
`getLength(rope)`	Get character count
`insert(rope, position, content)`	Insert text, returns `InsertOp`
`insertWithSplit(rope, position, content)`	Insert with span splitting
`remove(rope, position, length)`	Delete text, returns `DeleteOp`
`replace(rope, position, deleteLen, text)`	Replace text atomically, returns `ReplaceOp`
`move(rope, from, length, to)`	Move text, returns `MoveOp`
`apply(rope, op)`	Apply an `InsertOp`
`applyDelete(rope, op)`	Apply a `DeleteOp`
`applyReplace(rope, op)`	Apply a `ReplaceOp`
`applyMove(rope, op)`	Apply a `MoveOp`
`merge(rope, other)`	Merge another rope
`snapshot(rope)`	Full snapshot
`compact(rope)`	Compacted snapshot (no tombstones)
`toRaw(rope)`	Minimal array format for storage
`fromRaw(raw, agentId?)`	Restore from raw format
`fromSnapshot(snap, agentId?)`	Restore from snapshot
`getStats(rope)`	Get statistics

Types

typescript

interface InsertOp {
  id: ItemId;
  content: string;
  parentId: ItemId | null;
  seq: number;
}

interface DeleteOp {
  deletions: Array<{ id: ItemId; length: number }>;
}

interface MoveOp {
  delete: DeleteOp;
  insert: InsertOp;
}

interface ReplaceOp {
  delete: DeleteOp;
  insert: InsertOp;
}

interface ItemId {
  agent: string;
  seq: number;
}

How It Works

YATA Ordering Algorithm

YATA (Yet Another Transformation Approach) orders concurrent inserts:

Lamport timestamp - Higher timestamp goes first
Parent position - If timestamps equal, compare parent positions
Agent ID - If still equal, use agent ID for deterministic ordering

This reduces interleaving of concurrent edits compared to pure RGA.

Run-Length Encoding

Consecutive characters from the same agent are stored in a single item:

typescript

insert(rope, 0, 'h');
insert(rope, 1, 'e');
insert(rope, 2, 'l');
insert(rope, 3, 'l');
insert(rope, 4, 'o');
// May be stored as one item with content "hello"

Span Splitting

When inserting in the middle of a span, the span is split:

typescript

insert(rope, 0, 'hello');  // One item
insertWithSplit(rope, 2, 'XX');
// Result: "heXXllo"
// Items: ["he", "XX", "llo"]

Cross-Agent Convergence

TextRope uses character-level parent IDs to ensure convergence even when span boundaries differ across agents. Each character within a multi-character span has a logical ID: { agent, seq + offset }.

When Agent A inserts mid-span, the InsertOp.parentId references the exact character position, not the span start. When Agent B receives this op, it splits its local span at the correct character boundary:

typescript

// Agent 1 has "hello" as one span → inserts at position 2
const op = insertWithSplit(rope1, 2, 'X');
// op.parentId = { agent: 'agent-1', seq: 1 }  (the 'e' character)

// Agent 2 also has "hello" as one span
apply(rope2, op);
// Agent 2 splits "hello" → "he" | "X" | "llo"
// Both agents: "heXllo" ✓

DeleteOp uses an ID-range format — each deletion specifies a start ID and length. This allows correct application regardless of how the receiving agent has split its spans:

typescript

// Agent 1 deletes "ell" from "hello" → returns:
// { deletions: [{ id: { agent: 'agent-1', seq: 1 }, length: 3 }] }
//
// Agent 2 may have "hello" split differently, but applyDelete
// matches by agent + seq range, not by item position

Architecture

3-Component Design

vuer-rtc uses a 3-component architecture for text handling:

┌─────────────────────────────────────────────────────┐
│                 1. StringRope                       │
│                (Pure Data Structure)                │
├─────────────────────────────────────────────────────┤
│  Simple mutable string wrapper                      │
│  - insert(position, text)                           │
│  - delete(position, length)                         │
│  - toString() → string                              │
│  - toJSON() → string (serializes as plain string)   │
│  - Can be upgraded to B-tree later for O(log n)     │
└─────────────────────────────────────────────────────┘

┌─────────────────────────────────────────────────────┐
│                 2. TextCRDT (TextRope)              │
│              (Standalone Text Documents)            │
├─────────────────────────────────────────────────────┤
│  Full CRDT with B-tree + metadata                   │
│  _tree: ItemTree   ← B-tree of text spans           │
│  _agentIndex: Map  ← per-agent sorted index         │
│  agentId: string   ← this agent's ID                │
│  clock: number     ← local sequence counter         │
│  maxSeq: number    ← max Lamport time seen          │
│                                                      │
│  Used for: Standalone Text objects                  │
└─────────────────────────────────────────────────────┘

┌─────────────────────────────────────────────────────┐
│                 3. GraphTextCRDT                    │
│             (Graph Node Text Coordination)          │
├─────────────────────────────────────────────────────┤
│  Manages TextRope instances for graph properties    │
│  - Any string property can accept text.* ops        │
│  - Addressed via key + path                         │
│  - CRDT state stored in _textRope.{path}            │
└─────────────────────────────────────────────────────┘

Storage in SceneGraph

┌─────────────────────────────────────────────────────┐
│                    SceneGraph                       │
│  (manual spread-based immutable updates)            │
├─────────────────────────────────────────────────────┤
│  nodes['doc-1']                                     │
│    ├── content: "Hello World"  ← visible string     │
│    └── _textRope.content: TextRope ← CRDT state     │
└─────────────────────────────────────────────────────┘

TextRope is a class instance. Shallow cloning preserves references (Immer skips class instances). Standalone functions like insert(), apply(), and getText() operate on it. Use snapshot() to deep-clone a rope for safe state management.

Performance

TextRope is optimized for real-world editing workloads. We benchmark against diamond-types editing traces — real collaborative editing sessions captured from production use.

Benchmark Results

Dataset	Patches	Time	Throughput
friendsforever	4,288	5ms	858K patches/s
sveltecomponent	19,749	46ms	429K patches/s
clownschool	23,182	63ms	368K patches/s
rustcode	40,173	200ms	201K patches/s

All benchmarks replay real editing traces and verify the final text matches the expected output exactly.

Optimizations

TextRope uses several techniques to achieve high throughput:

Fast-path local operations — Local inserts skip the O(n) deduplication and parent search scans that are only needed for remote operations. This alone provides a 10-28x speedup over the naive path.
Cursor caching — Sequential edits (the common case in typing) reuse the last position lookup, converting O(n) position scanning to O(1).
Agent-seq index — A lazily-built per-agent sorted index enables O(log n) ID lookups for remote operation integration, replacing O(n) linear scans.
Batch delete application — Remote deletes are grouped by agent, ranges are merged, and applied in a single pass per agent — O(n + d log d) instead of O(d·n).
Run-length encoding — Consecutive characters from the same agent share a single item, reducing memory and scan overhead.

Complexity

Operation	Sequential	Random	Remote
`insert` / `insertWithSplit`	O(1)	O(n)	O(n + log m)
`remove`	O(1)	O(n)	—
`apply` (remote insert)	—	—	O(n + log m)
`applyDelete` (remote delete)	—	—	O(n + d log d)
`getText`	O(n)	O(n)	O(n)

Where n = total items, m = items per agent, d = deletions in the batch.

Notes

Tombstones — Deleted items remain for CRDT consistency. Use compact() for storage.
Network efficiency — Send InsertOp/DeleteOp over the network, not full snapshots.
Scalability — Suitable for documents up to ~100K characters with real-time responsiveness.

Try it live: See TextRope in action in the Rope Demo.