# 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](https://josephg.com/blog/crdts-go-brrr/) approach by Joseph Gentle, using the YATA ordering algorithm.

> See [Operations](/operations.md) 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

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

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

// 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

// 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:

1. **Lamport timestamp** - Higher timestamp goes first
2. **Parent position** - If timestamps equal, compare parent positions
3. **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](https://github.com/josephg/diamond-types) —
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](/rope-demo).