suaveplan/openspec/changes/crdt-completion/specs/crdt/spec.md

<!-- markdownlint-disable MD024 -->

# Capability Spec Delta: crdt (crdt-completion)

**Package**: `@suaveplan/crdt`
**Status**: PROPOSED

> Every requirement below carries a `**Verified by:**` line at authoring time. No exceptions. (See `openspec/AGENTS.md` Section 13.)

## ADDED Requirements

### Requirement: G-Set grow-only set CRDT

The package SHALL expose a `GSet<T>` class implementing `CRDT<Set<T>, GSetState<T>>`. The class SHALL support `add(value: T): void`, `has(value: T): boolean`, `value(): Set<T>`, `state(): GSetState<T>`, `merge(remote: GSetState<T>): void`, `toJSON(): string`, `fromJSON(json: string): void`, and `clone(): GSet<T>`. `merge` SHALL be a set union — idempotent, commutative, and associative. The state envelope SHALL include `type: "g-set"` for cross-CRDT serialisation discrimination.

#### Scenario: add then has returns true

- **WHEN** `gset.add("a")` is called and then `gset.has("a")` is called
- **THEN** the result is `true`

#### Scenario: merge is set union

- **WHEN** `gset1` holds `{"a", "b"}` and `gset2` holds `{"b", "c"}` and `gset1.merge(gset2.state())` is called
- **THEN** `gset1.value()` equals `Set { "a", "b", "c" }`

#### Scenario: merge is idempotent

- **WHEN** `gset1.merge(gset2.state())` is called twice in succession
- **THEN** the second call leaves `gset1.value()` unchanged from after the first call

#### Scenario: merge is commutative

- **WHEN** two pairs of merges are performed in opposite orders against fresh clones
- **THEN** the resulting `value()` sets are deeply equal

#### Scenario: merge is associative

- **WHEN** `(a ∪ b) ∪ c` is computed against fresh clones and `a ∪ (b ∪ c)` is computed against another set of fresh clones
- **THEN** the resulting `value()` sets are deeply equal

#### Scenario: toJSON / fromJSON round-trip

- **WHEN** a populated `GSet` is serialised via `toJSON()` and a fresh `GSet` calls `fromJSON(json)`
- **THEN** the fresh instance's `value()` equals the original's `value()`

#### Scenario: initialElements seeds the set

- **WHEN** `new GSet<string>("node-1", { initialElements: ["a", "b", "c"] })` is constructed
- **THEN** `gset.value()` equals `Set { "a", "b", "c" }` immediately

#### Scenario: BigInt element rejected

- **WHEN** `gset.add(BigInt(1) as never)` is called
- **THEN** `CrdtError` is thrown with code `GSET_INVALID_ELEMENT` and `context.value` set to the offending input

**Verified by:** `packages/flow/crdt/src/crdts/g-set/g-set.test.ts::"adds an element and reports has() true"` AND `packages/flow/crdt/src/crdts/g-set/g-set.test.ts::"merge is set union"` AND `packages/flow/crdt/src/crdts/g-set/g-set.test.ts::"merge is idempotent"` AND `packages/flow/crdt/src/crdts/g-set/g-set.test.ts::"merge is commutative"` AND `packages/flow/crdt/src/crdts/g-set/g-set.test.ts::"merge is associative"` AND `packages/flow/crdt/src/crdts/g-set/g-set.test.ts::"toJSON / fromJSON round-trip"` AND `packages/flow/crdt/src/crdts/g-set/g-set.test.ts::"initialElements seeds the set"` AND `packages/flow/crdt/src/crdts/g-set/g-set.spec-conformance.test.ts::"throws GSET_INVALID_ELEMENT for BigInt element"`

---

### Requirement: LWW-Map last-write-wins map CRDT

The package SHALL expose a `LWWMap<V>` class implementing `CRDT<Map<string, V>, LWWMapState<V>>`. The class SHALL support `set(key: string, value: V, ts?: number): void`, `get(key: string): V | undefined`, `has(key: string): boolean`, `delete(key: string, ts?: number): boolean`, `keys(): string[]`, `value(): Map<string, V>`, `state(): LWWMapState<V>`, `merge(remote: LWWMapState<V>): void`, `toJSON(): string`, `fromJSON(json: string): void`, `clone(): LWWMap<V>`, and `reset(): void`.

The constructor SHALL accept an optional injectable `Clock` from `@suaveplan/types`; when an explicit `ts` argument is omitted from `set` or `delete`, the clock's `now()` SHALL provide it. Tie-break on equal timestamp SHALL compare `nodeId` lexicographically (matching `LWWRegister`). Deletes SHALL leave a tombstone preserving the timestamp; subsequent `set` with a strictly greater timestamp SHALL clear the tombstone. `merge` SHALL respect tombstones across both directions: remote entries older than a local tombstone are dropped; remote tombstones newer than a local entry remove the entry. `merge` SHALL be idempotent, commutative, and associative.

#### Scenario: set then get returns the value

- **WHEN** `map.set("k", "v")` is called and then `map.get("k")` is called
- **THEN** the result is `"v"`

#### Scenario: older set is no-op

- **WHEN** `map.set("k", "v1", 100)` is called and then `map.set("k", "v0", 50)` is called
- **THEN** `map.get("k")` returns `"v1"`

#### Scenario: tie-break on equal timestamp uses nodeId

- **WHEN** two replicas with `nodeId = "a"` and `nodeId = "b"` both write `key="k"` at the same timestamp `100`
- **THEN** the merged result is the value written by `nodeId = "b"` (lexicographically greater)

#### Scenario: delete leaves a tombstone

- **WHEN** `map.delete("k", 100)` is called
- **THEN** `map.has("k")` returns `false` AND `map.get("k")` returns `undefined` AND the internal state contains a tombstone with timestamp `100`

#### Scenario: re-add after delete

- **WHEN** `map.delete("k", 100)` is called and then `map.set("k", "v", 200)` is called
- **THEN** `map.get("k")` returns `"v"` AND the tombstone is cleared

#### Scenario: merge respects tombstones — older remote entry dropped

- **WHEN** local has tombstone for `"k"` at ts `200` and remote state has entry `{k: { value: "v", timestamp: 100 }}`
- **THEN** after `local.merge(remote.state())`, `local.has("k")` returns `false`

#### Scenario: merge respects tombstones — newer remote tombstone removes local entry

- **WHEN** local has entry `{k: "v", ts: 100}` and remote has tombstone for `"k"` at ts `200`
- **THEN** after `local.merge(remote.state())`, `local.has("k")` returns `false`

#### Scenario: injected Clock provides timestamps

- **WHEN** `new LWWMap("node-1", { clock: { now: () => 555 } })` is constructed and `map.set("k", "v")` is called without a ts argument
- **THEN** the resulting entry has `timestamp: 555`

#### Scenario: merge is idempotent / commutative / associative

- **WHEN** the property test runs over 100 random key/value/timestamp triples per replica
- **THEN** `merge` satisfies all three CRDT properties

#### Scenario: reset clears state

- **WHEN** `map.reset()` is called against a populated map
- **THEN** `map.value().size === 0` AND no tombstones remain

#### Scenario: non-string key rejected

- **WHEN** `map.set(BigInt(1) as never, "v")` is called
- **THEN** `CrdtError` is thrown with code `LWWMAP_INVALID_KEY`

**Verified by:** `packages/flow/crdt/src/crdts/lww-map/lww-map.test.ts::"set then get returns the value"` AND `packages/flow/crdt/src/crdts/lww-map/lww-map.test.ts::"set with explicit timestamp respects ordering"` AND `packages/flow/crdt/src/crdts/lww-map/lww-map.test.ts::"tie-break on equal timestamp uses nodeId"` AND `packages/flow/crdt/src/crdts/lww-map/lww-map.test.ts::"delete leaves a tombstone"` AND `packages/flow/crdt/src/crdts/lww-map/lww-map.test.ts::"set after delete with greater ts clears tombstone"` AND `packages/flow/crdt/src/crdts/lww-map/lww-map.test.ts::"merge respects tombstones — older remote entry dropped"` AND `packages/flow/crdt/src/crdts/lww-map/lww-map.test.ts::"merge respects tombstones — newer remote tombstone removes local entry"` AND `packages/flow/crdt/src/crdts/lww-map/lww-map.test.ts::"merge is idempotent / commutative / associative"` AND `packages/flow/crdt/src/crdts/lww-map/lww-map.test.ts::"reset clears entries and tombstones"` AND `packages/flow/crdt/src/crdts/lww-map/lww-map.spec-conformance.test.ts::"set without ts pulls from injected clock"` AND `packages/flow/crdt/src/crdts/lww-map/lww-map.spec-conformance.test.ts::"throws LWWMAP_INVALID_KEY for non-string key"`

<!-- markdownlint-enable MD024 -->