npm package: @sovereignbase/convergent-replicated-list
Description: Convergent Replicated List (CR-List), a delta CRDT for an ordered sequence of entries.
Latest version: 1.0.2

[![npm version](https://img.shields.io/npm/v/@sovereignbase/convergent-replicated-list)](https://www.npmjs.com/package/@sovereignbase/convergent-replicated-list)
[![CI](https://github.com/sovereignbase/convergent-replicated-list/actions/workflows/ci.yaml/badge.svg?branch=master)](https://github.com/sovereignbase/convergent-replicated-list/actions/workflows/ci.yaml)
[![codecov](https://codecov.io/gh/sovereignbase/convergent-replicated-list/branch/master/graph/badge.svg)](https://codecov.io/gh/sovereignbase/convergent-replicated-list)
[![license](https://img.shields.io/npm/l/@sovereignbase/convergent-replicated-list)](LICENSE)

# convergent-replicated-list

Convergent Replicated List (CR-List), a delta CRDT for an ordered sequence of entries.

## Compatibility

- Runtimes: Node >= 20, modern browsers, Bun, Deno, Cloudflare Workers, Edge Runtime.
- Module format: ESM + CommonJS.
- Required globals / APIs: `EventTarget`, `CustomEvent`, `structuredClone`.
- TypeScript: bundled types.

## Goals

- Deterministic convergence of the live list projection under asynchronous gossip delivery.
- Consistent behavior across Node, browsers, worker, and edge runtimes.
- Garbage collection possibility without breaking live-view convergence.
- Event-driven API

## Installation

```sh
npm install @sovereignbase/convergent-replicated-list
# or
pnpm add @sovereignbase/convergent-replicated-list
# or
yarn add @sovereignbase/convergent-replicated-list
# or
bun add @sovereignbase/convergent-replicated-list
# or
deno add jsr:@sovereignbase/convergent-replicated-list
# or
vlt install jsr:@sovereignbase/convergent-replicated-list
```

## Usage

### Copy-paste example

```ts
import { CRList } from '@sovereignbase/convergent-replicated-list'

const alice = new CRList<string>()
const bob = new CRList<string>()

alice.addEventListener('delta', (event) => {
  bob.merge(event.detail)
})

alice.append('hello')
alice.append('world')
alice.prepend('first')

console.log([...alice]) // ['first', 'hello', 'world']
console.log([...bob]) // ['first', 'hello', 'world']
console.log(alice[1]) // 'hello'
```

### Hydrating from a snapshot

```ts
import {
  CRList,
  type CRListSnapshot,
} from '@sovereignbase/convergent-replicated-list'

const source = new CRList<string>()
let snapshot!: CRListSnapshot<string>

source.addEventListener(
  'snapshot',
  (event) => {
    snapshot = event.detail
  },
  { once: true }
)

source.append('draft')
source.append('ready')
source.snapshot()

const restored = new CRList<string>(snapshot)

console.log([...restored]) // ['draft', 'ready']
```

### Event channels

```ts
import { CRList } from '@sovereignbase/convergent-replicated-list'

const list = new CRList<string>()

list.addEventListener('delta', (event) => {
  console.log('delta', event.detail)
})

list.addEventListener('change', (event) => {
  console.log('change', event.detail)
})

list.addEventListener('snapshot', (event) => {
  console.log('snapshot', event.detail)
})

list.addEventListener('ack', (event) => {
  console.log('ack', event.detail)
})

list.append('a')
list[0] = 'b'
delete list[0]
```

### Iteration and JSON serialization

```ts
import { CRList } from '@sovereignbase/convergent-replicated-list'

const list = new CRList<string>()

list[0] = 'up'
list.append('dude!')
list.prepend('What is')

const serialized = JSON.stringify(list)
const restored = new CRList<string>(JSON.parse(serialized))

for (const value of list) {
  console.log(value)
}

for (const index in list) {
  console.log(index)
}

list.forEach((value, index, target) => {
  console.log(index, value, target.size)
})

console.log([...restored]) // ['What is', 'up', 'dude!']
```

Numeric reads, `for...of`, and `forEach()` return detached copies of visible
values. Mutating those returned values does not mutate the underlying replica
state.

### Acknowledgements and garbage collection

```ts
import { CRList } from '@sovereignbase/convergent-replicated-list'

const alice = new CRList<string>()
const bob = new CRList<string>()
const frontiers = new Map<string, string>()

alice.addEventListener('delta', (event) => bob.merge(event.detail))
bob.addEventListener('delta', (event) => alice.merge(event.detail))

alice.addEventListener('ack', (event) => {
  frontiers.set('alice', event.detail)
})

bob.addEventListener('ack', (event) => {
  frontiers.set('bob', event.detail)
})

alice.append('x')
alice[0] = 'y'
delete alice[0]

alice.acknowledge()
bob.acknowledge()

alice.garbageCollect([...frontiers.values()])
bob.garbageCollect([...frontiers.values()])
```

### Advanced exports

If you need to build your own ordered-sequence CRDT binding instead of using the
high-level `CRList` class, the package also exports the core CRUD and MAGS
functions together with the replica and payload types.

Those low-level exports let you build custom list abstractions, protocol
wrappers, or framework-specific bindings while preserving the same convergence
rules as the default `CRList` binding.

```ts
import {
  __create,
  __update,
  __merge,
  __snapshot,
  type CRListDelta,
  type CRListSnapshot,
} from '@sovereignbase/convergent-replicated-list'

const replica = __create<string>()
const local = __update(0, ['hello', 'world'], replica, 'after')

if (local) {
  const outgoing: CRListDelta<string> = local.delta
  const remoteChange = __merge(replica, outgoing)

  console.log(remoteChange)
}

const snapshot: CRListSnapshot<string> = __snapshot(replica)
console.log(snapshot)
```

The intended split is:

- `__create`, `__read`, `__update`, `__delete` for local replica mutations.
- `__merge`, `__acknowledge`, `__garbageCollect`, `__snapshot` for gossip,
  compaction, and serialization.
- `CRList` when you want the default event-driven class API.

## Runtime behavior

### Validation and errors

Low-level exports can throw `CRListError` with stable error codes:

- `VALUE_NOT_CLONEABLE`
- `INDEX_OUT_OF_BOUNDS`
- `LIST_EMPTY`
- `LIST_INTEGRITY_VIOLATION`
- `UPDATE_EXPECTED_AN_ARRAY`

Ingress stays tolerant:

- malformed top-level merge payloads are ignored
- malformed snapshot values are dropped during hydration
- invalid UUIDs are ignored
- duplicate insert and delete deltas are idempotent
- stale or malicious deltas do not break convergence of the live view

### Safety and copying semantics

- Snapshots are serializable full-state payloads.
- Deltas are serializable gossip payloads.
- `change` is a minimal index-keyed local patch.
- `toJSON()` returns a detached serializable snapshot.
- Numeric reads, `for...of`, and `forEach()` expose detached copies of visible values rather than mutable references into replica state.
- `for...of`, `forEach()`, numeric indexing, `append()`, `prepend()`, `remove()`, `merge()`, `snapshot()`, `acknowledge()`, and `garbageCollect()` all operate on the live list projection.

### Convergence and compaction

- The convergence target is the live list projection, not internal cursor placement.
- Stable `predecessor` anchors determine deterministic ordering together with UUIDv7 sorting when placement cannot be resolved from a live predecessor chain.
- Tombstones remain until acknowledgement frontiers make them safe to collect.
- Garbage collection does not change the converged live projection for replicas that later catch up from delta or snapshot state.

## Tests

```sh
npm run test
```

What the current test suite covers:

- Coverage on built `dist/**/*.js`: `100%` statements, `99.67%` branches, `100%` functions, and `100%` lines, together with focused source-coverage tests for helper edge paths.
- Public `CRList` surface: indexing, iteration, `forEach`, proxy traps, events, JSON/inspect behavior.
- Core edge paths and malicious ingress handling for `__create`, `__read`, `__update`, `__delete`, `__merge`, `__snapshot`, `__acknowledge`, and `__garbageCollect`.
- Internal defensive branches under intentionally corrupt in-memory replica state.
- Integration convergence stress for:
  - local CRUD live-view semantics
  - snapshot hydration independent of value order
  - merge idempotency for duplicate insert/delete deltas
  - stale-peer acknowledgement and garbage collection recovery
  - shuffled asynchronous gossip delivery
  - shuffled delivery with replica restarts
  - concurrent insert after concurrently deleted predecessor
  - `100` aggressive deterministic convergence scenarios
- End-to-end runtime matrix for:
  - Node ESM
  - Node CJS
  - Bun ESM
  - Bun CJS
  - Deno ESM
  - Cloudflare Workers ESM
  - Edge Runtime ESM
  - Browsers via Playwright: Chromium, Firefox, WebKit, mobile Chrome, mobile Safari

## Benchmarks

```sh
npm run bench
```

The benchmark runner currently uses:

- `LIST_SIZE = 5_000`
- `RUN_TIMES = 250`
- output columns: `group`, `scenario`, `n`, `ops`, `ms`, `ms/op`, `ops/sec`

Last measured on Node `v22.14.0` (`win32 x64`):

| group   | scenario                              |     n | ops |       ms | ms/op |    ops/sec |
| ------- | ------------------------------------- | ----: | --: | -------: | ----: | ---------: |
| `crud`  | `create / hydrate snapshot`           | 5,000 | 250 | 8,817.80 | 35.27 |      28.35 |
| `crud`  | `read / random indexed reads`         | 5,000 | 250 |    12.59 |  0.05 |  19,854.03 |
| `crud`  | `update / append after tail`          | 5,000 | 250 |     2.26 |  0.01 | 110,507.01 |
| `crud`  | `update / insert before middle`       | 5,000 | 250 |    22.27 |  0.09 |  11,224.10 |
| `crud`  | `update / overwrite random`           | 5,000 | 250 |    13.95 |  0.06 |  17,919.61 |
| `crud`  | `delete / single deletes from middle` | 5,000 | 250 |    23.21 |  0.09 |  10,772.98 |
| `crud`  | `delete / range deletes`              | 5,000 | 250 |     6.32 |  0.03 |  39,562.60 |
| `mags`  | `snapshot`                            | 5,000 | 250 | 5,354.28 | 21.42 |      46.69 |
| `mags`  | `acknowledge`                         | 5,000 | 250 |    47.24 |  0.19 |   5,291.76 |
| `mags`  | `garbage collect`                     | 5,000 | 250 |   163.55 |  0.65 |   1,528.59 |
| `mags`  | `merge ordered deltas`                | 5,000 | 250 |    19.25 |  0.08 |  12,986.74 |
| `mags`  | `merge shuffled gossip`               | 5,000 | 250 |   485.99 |  1.94 |     514.41 |
| `class` | `constructor / hydrate snapshot`      | 5,000 | 250 | 8,119.67 | 32.48 |      30.79 |
| `class` | `append after tail`                   | 5,000 | 250 |     2.87 |  0.01 |  87,232.63 |
| `class` | `prepend before middle`               | 5,000 | 250 |     7.76 |  0.03 |  32,228.95 |
| `class` | `remove from middle`                  | 5,000 | 250 |     5.20 |  0.02 |  48,084.32 |
| `class` | `snapshot`                            | 5,000 | 250 | 5,842.47 | 23.37 |      42.79 |
| `class` | `acknowledge`                         | 5,000 | 250 |   127.77 |  0.51 |   1,956.68 |
| `class` | `garbage collect`                     | 5,000 | 250 |   323.20 |  1.29 |     773.51 |
| `class` | `merge ordered deltas`                | 5,000 | 250 |     8.61 |  0.03 |  29,021.17 |
| `class` | `merge shuffled gossip`               | 5,000 | 250 |   523.53 |  2.09 |     477.53 |

## License

Apache-2.0