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.

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
Plain object - TextRope is a simple data container, not a class
Compact snapshots - Remove tombstones for efficient storage

Quick Example

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

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([
  { otype: 'node.insert', key: '', path: 'children',
    value: { key: 'doc-1', tag: 'TextDocument', name: 'My Doc' } },
]));

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

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

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

// Delete text
graph = applyMessage(graph, msg([
  { otype: '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	`{ otype: 'text.init', key: 'doc-1', path: 'content', value: 'Hello' }`
`text.insert`	Insert at position	`{ otype: 'text.insert', key: 'doc-1', path: 'content', position: 5, value: ' World' }`
`text.delete`	Delete at position	`{ otype: 'text.delete', key: 'doc-1', path: 'content', position: 0, length: 6 }`

Multi-User Collaboration

When multiple users edit concurrently, the CRDT ensures convergence:

// Alice's graph
let graphA = createEmptyGraph();
graphA = applyMessage(graphA, msgA([
  { otype: 'node.insert', key: '', path: 'children',
    value: { key: 'doc-1', tag: 'TextDocument', name: 'Shared Doc' } },
  { otype: '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([
  { otype: 'text.insert', key: 'doc-1', path: 'content', position: 0, value: 'A: ' },
]);
graphA = applyMessage(graphA, aliceOp);

// Bob inserts at the end (concurrently)
const bobOp = msgB([
  { otype: 'text.insert', key: 'doc-1', path: 'content', position: 5, value: ' -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

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:

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

// Create a rope - returns a plain object { items, agentId, clock, maxSeq }
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"

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

interface TextRope {
  items: Item[];      // Text spans (including tombstones)
  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

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

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 follows a data + functions pattern, not OOP:

Plain objects: TextRope is a simple data container with no methods
Standalone functions: All operations are pure functions that take the rope as the first argument
No classes: No new Rope() - just create('agent-id') returns a plain object
Serializable: The rope is just { items, agentId, clock, maxSeq } - directly JSON-serializable

This design allows:

Easy serialization/deserialization
Predictable state management
Works with any framework (React, Vue, etc.)
No prototype chain overhead

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`
`move(rope, from, length, to)`	Move text, returns `MoveOp`
`apply(rope, op)`	Apply an `InsertOp`
`applyDelete(rope, op)`	Apply a `DeleteOp`
`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

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

interface DeleteOp {
  ids: ItemId[];
}

interface MoveOp {
  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:

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:

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

Architecture

┌─────────────────────────────────────────────────────┐
│                    SceneGraph                       │
│  (uses Immer for immutable updates)                 │
├─────────────────────────────────────────────────────┤
│  nodes['doc-1']                                     │
│    ├── content: "Hello World"  ← visible string     │
│    └── _textCrdt.content: TextRope ← CRDT data      │
└─────────────────────────────────────────────────────┘
                         │
                         ▼
┌─────────────────────────────────────────────────────┐
│                    TextRope                         │
│  (plain data object)                                │
├─────────────────────────────────────────────────────┤
│  items: Item[]     ← text spans with CRDT metadata  │
│  agentId: string   ← this agent's ID                │
│  clock: number     ← local sequence counter         │
│  maxSeq: number    ← max Lamport time seen          │
└─────────────────────────────────────────────────────┘

All data structures are plain objects. Functions like insert(), apply(), and getText() operate on these objects.

Performance

O(n) operations - Flat list, suitable for documents up to ~100K characters
Tombstones - Deleted items remain. Use compact() for storage
Network efficiency - Send InsertOp/DeleteOp over the network, not full snapshots