@hecto/crdt

Conflict-free replicated data types for collaborative text: site identity, fractional indexing, a Fugue sequence, an event graph, binary encoding, text and JSON merge, and an operation-log client. hecto's own implementation — no third-party CRDT library.

pnpm add @hecto/crdt

import { createText } from '@hecto/crdt/fugue'

const alice = createText('alice')
const bob = createText('bob')

const hello = alice.insert(0, 'hello')
for (const op of hello) bob.apply(op)

const fromAlice = alice.insert(5, ' there')
const fromBob = bob.insert(5, ' world')
for (const op of fromBob) alice.apply(op)
for (const op of fromAlice) bob.apply(op)

alice.toString() === bob.toString() // true

What's in the box

• . — SiteId, OpId, compareOpId, StateVector
• ./fractional — between(a, b, site)
• ./fugue — createText, insert, delete, apply, toString, idAt, indexOfId, stateVector, opsSince
• ./graph — createEventGraph: append-only DAG, frontier, topological order, diffVersions, nearest common ancestors
• ./encoding — encodeOps / decodeOps, snapshots, state vectors
• ./merge — createTextDocument: event-graph text with localSplice, receive, idAt, indexOfId
• ./json-merge — createJsonDocument: the same graph over any @hecto/diff patch
• ./client — createDocClient: offline queue, SSE reconnect, presence

Indices are UTF-16 code units, matching @hecto/diff splices.

Identity

import { compareOpId } from '@hecto/crdt'
import type { OpId } from '@hecto/crdt'

const id: OpId = { site: 'alice', seq: 3 }
compareOpId({ site: 'alice', seq: 1 }, { site: 'bob', seq: 1 }) // -1

SiteId names one replica. Each site hands out seq in strictly increasing order, so (site, seq) is unique. StateVector maps a site to the highest contiguous seq received from it.

Fractional indexing

import { between } from '@hecto/crdt/fractional'

const first = between(null, null, 'alice')
const second = between(first, null, 'alice')
const middle = between(first, second, 'bob')
first < middle && middle < second // true

between returns a base-62 key with a !<site> suffix. Two sites minting in the same gap share a core and stay distinct by suffix. Plain string comparison is the order. Repeated inserts at one spot grow the key; 10,000 insertions at a fixed spot stay under 2,100 characters.

Fugue

createText(site) implements Weidner & Kleppmann, The Art of the Fugue (2023), Section 4, Algorithm 1. Deletes are tombstones. apply is idempotent and buffers an op whose parent, delete target, or earlier same-site seq has not arrived.

createText(site) stores forward typing runs as spans and looks up positions in O(log n). createText(site, { spans: false }) is the per-character oracle used by merge replay.

Two sites typing aaaa and bbbb at one position converge on aaaabbbb or bbbbaaaa, never a mixture.

Event graph

import { createEventGraph } from '@hecto/crdt/graph'

const graph = createEventGraph<string>()
graph.add({ id: { site: 'alice', seq: 1 }, parents: [], patch: 'root' })
graph.frontier() // [{ site: 'alice', seq: 1 }]

add accepts an exact duplicate idempotently, rejects the same id with different content (DuplicateEvent), rejects an unknown parent (UnknownParent — the caller buffers), and requires id.seq to be exactly one more than the highest seq already accepted from that site (OutOfOrderSeq).

Encoding

import { createText } from '@hecto/crdt/fugue'
import { decodeOps, encodeOps } from '@hecto/crdt/encoding'

const alice = createText('alice')
const ops = alice.insert(0, 'hello')
const bytes = encodeOps(ops)
decodeOps(bytes) // deep-equal to `ops`

Structure (ids, parents, tombstones) and content (inserted text) are separate sections so a host can encrypt content and still merge. splitEncoded / joinEncoded slice that boundary. Decoding untrusted bytes throws only a typed DecodeError.

Text merge

import { isOk } from '@hecto/fp'
import { createTextDocument } from '@hecto/crdt/merge'

const alice = createTextDocument('alice')
const hello = alice.localSplice(0, 0, 'hello')
const bob = createTextDocument('bob')
const received = bob.receive(hello)
isOk(received) // true
bob.text // 'hello'
bob.idAt(0) // { site: 'alice', seq: 1 }

If event.parents equals the frontier, the splice applies as written. Otherwise both branches replay through a temporary Fugue replica and the incoming event is emitted as splices already transformed onto the current text. receive of an unknown parent returns UnknownParent and holds the event. receive of an event already in the graph is idempotent. idAt / indexOfId are the shared character ids presence carets use. Empty text has no id.

JSON merge

import { isOk } from '@hecto/fp'
import { patch } from '@hecto/diff'
import { createJsonDocument } from '@hecto/crdt/json-merge'

const alice = createJsonDocument('alice', { value: { n: 1 } })
const bump = alice.localPatch(
  patch([{ op: 'replace', path: ['n'], oldValue: 1, newValue: 2 }]),
)
const bob = createJsonDocument('bob', { value: { n: 1 } })
const received = bob.receive(bump)
isOk(received) // true
bob.value // { n: 2 }

Text splices merge through Fugue. Concurrent replaces resolve last-writer-wins by (lamport, site). Concurrent array adds at one index order by site. remove tombstones the path. Lamport is 1 + max(parent lamports) and is never stored on the event.

Client

import { createDocClient } from '@hecto/crdt/client'
import { createTextDocument } from '@hecto/crdt/merge'

const text = createTextDocument('alice')
const hello = text.localSplice(0, 0, 'hello')
const client = createDocClient({
  url: 'https://docs.example/',
  docId: 'note-1',
  clientId: 'alice',
  sessionId: 'session-alice',
  userId: 'alice',
  displayName: 'Alice',
})
void client.send([hello])
client.disconnect()

Talks to @hecto/doc-server without importing it. send queues while offline. reconnect() opens the SSE stream from the current state vector (?sv= and ?clientId=). Presence POST is { activity, cursor } only — identity comes from the host options, never from publish(). Subscribe listeners never see an event this client minted.