Bento, the office suite that fits in a file
TypeScript mit-licenseofficeoffice-365office-suiteoffice-toolsoffice365open-sourcepowerpointself-hostedsingle-page-appslidesslideshareslideshowslideshow-galleryslideshow-makerslideshows
// SPDX-License-Identifier: MIT
// Copyright (c) 2026 The Bento authors
// bento-sync for dash — the CRDT engine. Pure data, no DOM, no imports beyond
// the model types and the store's own writer, so the same file runs in the
// browser session layer and in the node convergence rig
// (scripts/test-dash-sync.ts, node --experimental-strip-types).
//
// Design, rationale and the honest list of what LOSES DATA: docs/dash-collab.md.
// Read that before changing anything here.
//
// WHY THIS IS NOT slides/src/sync/crdt.ts
//
// Slides' engine keys per-element nodes and diffs two whole-document snapshots.
// Neither transfers. A dash workbook is COLUMNAR and dictionary-encoded: cell
// values live in per-column arrays addressed by ROW POSITION, and the document
// is routinely 10-25 MB. Two consequences set the whole shape of this file:
//
// 1. NO SNAPSHOT DIFFING. `JSON.stringify(doc)` costs ~10 ms on a 12 MB
// workbook (store.ts measured it, which is why history here is typed
// inverses rather than snapshots) and a shadow copy doubles resident
// memory. So ops are minted from the store's `Patch` objects, which are
// already a complete, position-independent description of every mutation.
// The store's comment predicted this: "The same Patch objects are the undo
// entries, the future CRDT ops and the agent API."
//
// 2. STATE MUST BE O(EDITS), NEVER O(ROWS). Anything per-row — an order key,
// a birth stamp, a shadow value — is multiplied by a million. The saved
// state also rides in the FILE (`collab.sync`), so O(rows) state would
// undo the entire point of the 4.8-bytes-per-cell encoding. Therefore a
// row that nobody has touched costs ZERO bytes here: rows get state only
// when an op inserts or deletes them, and cells only when an op writes
// them.
//
// THE ALGEBRA
//
// - Node identity. `@doc`; `s␟<sheet>`; `c␟<sheet>␟<col>`; `r␟<sheet>␟<rid>`.
// Column ids are SHEET-scoped (model.ts:478 — two sheets may both call a
// column `c1`) and so are rids, so both are composite. This is slides'
// lesson (bare ids collapsed the morph idiom) applied before it could bite.
//
// - Cells are PROPERTIES OF THE ROW NODE, keyed by column id: register
// `r␟s1␟7 ⟹ v␟price`. That is per-cell last-writer-wins for free, out of
// exactly the same (lamport, actor) register machinery slides uses for
// `x`/`fill`. Cell overrides (the `cells` overlay) are a second key space
// on the same node, `o␟price`.
//
// - A SPREADSHEET's cells are properties of the SHEET NODE, keyed by their A1
// ADDRESS: `s␟c1 ⟹ g␟B7` is the cell at B7, `p␟B7` its formatting, `w␟C`
// a column width, `h␟4` a row height. A `CanvasSheet` (kind:'canvas') has
// no rows and no columns to hang a node on — it is a sparse map — so the
// sheet is the only node there is, and the address is the only key the
// format offers.
//
// WHY A POSITION KEY, when a position key is exactly what makes a row
// insert hard. The choice was made three times over and each answer says
// the same thing:
//
// 1. THE DOCUMENT SUPPLIES NO CELL IDENTITY. A dataset row carries a
// `rid` in the FILE — minted at insert, never reused — which is what
// lets `r␟s1␟7` mean the same row on two replicas that have never
// spoken. A spreadsheet cell carries nothing but its address. Any
// identity would have to be MINTED at adoption, and minted identically
// by every replica of the file, so it would be a function of the
// address anyway — plus a stored address↔identity map.
// 2. THAT MAP WOULD BE O(CELLS). Invariant 2 above is that state is
// O(edits) and never O(rows); the map is one entry per NON-EMPTY cell
// whether anyone edited it or not, and it rides in the FILE
// (`collab.sync`). A 40k-cell invoice model would carry 40k identities
// to make a feature nobody has yet correct. The address is free: an
// untouched cell costs zero bytes here, exactly as an untouched row
// does.
// 3. NOTHING MOVES A CELL TODAY. `store.ts` has exactly two spreadsheet
// patches — `setCanvasCells` and `setCanvasSizes` — and neither shifts
// an address. There is no insert-row, no insert-column, no cut-and-
// shift on this kind. A position key is only wrong once something
// moves, and identity bought before then is identity that has to be
// maintained through every read (`validate.ts`, `preview.ts`,
// `cellformula.ts` and the format itself all address by A1) for no
// convergence gained.
//
// SO THE RULE FOR WHOEVER ADDS THE ROW INSERT, and it is the whole reason
// this paragraph is long: a patch that MOVES cells cannot be minted as
// `cvc` ops over the addresses it lands on. Two replicas inserting rows
// concurrently would each renumber the other's writes and no register
// ordering can repair it — the write and the shift are not the same kind
// of event. It needs either an explicit shift op that transforms the key
// space (and the registers with it, since a register keyed `g␟B7` is a
// claim about a POSITION), or a per-sheet row/column order of the kind the
// dataset kind has, at which point the cell keys become (rowId, colId) and
// stop being positions at all. Until one of those exists, an unhandled
// patch MUST keep falling through `localOne`'s default arm to the snapshot
// fallback: coarse and correct beats fine and wrong. The fallback is the
// safety net for this kind and must be narrowed, never removed.
//
// TWO REGISTERS PER CELL, not one and not one per field. `v` (the value)
// and `f` (the formula that produced it) are one fact — splitting them
// merges a formula from one replica with a cached number from another and
// shows a cell that never existed anywhere — so they share a register with
// everything else the cell computes (`g␟`). Presentation (`format`,
// `color`, `bg`, `bold`, `align`, `note`) is independent of the value in
// both directions and gets its own (`p␟`), so bolding a cell while someone
// retypes it keeps both. That is the same split the dataset kind already
// makes between `v␟col` and `o␟col`, for the same reason.
//
// Which registers a write CLAIMS is diffed against the pre-state at mint
// time (`localOne` runs before the store applies), because the patch always
// carries the whole cell — `cellprops.ts` writes `{...cell, bold:true}` —
// so the object alone cannot say what changed. The op carries the whole
// cell too, plus the claim mask, so a receiver in any state can apply it.
//
// - Row ORDER is a FRACTIONAL INDEX over rids, and the trick that makes it
// affordable is that most rows never get one. rids are minted at insert
// and NEVER reused (rowcol.ts is emphatic about this), which is what makes
// them usable as identity at all. A row that came with the file takes its
// key from its position in the adopted baseline sequence (`base`, one
// run-length list per sheet — 20 bytes for 4200 rows), so it costs
// nothing; only an INSERTED row stores an explicit key, minted between its
// neighbours' keys. Order is then `sort by (key, rid)`, a pure function of
// converged state. Cost: O(inserts) + O(sheets).
//
// Two earlier designs failed here and the rig caught both, which is why
// the third is spelled out. (1) An LWW register over the whole `rids`
// list: concurrent structural edits silently drop one side's rows.
// (2) An RGA whose inserts name an ANCHOR RID, with deleted anchors
// resolved by walking back to the anchor's own anchor — that walk lands a
// row ahead of rows which used to sit in between, and two replicas that
// applied the deletes in different orders disagreed (seed 16 of 20).
// A fractional key needs neither tombstone nor chain: neighbours may die
// without moving anything, because the key already sits between them.
//
// - Sheets and columns are few, so they get slides' fractional `pos` keys
// verbatim (keyBetween/spreadKey copied below — dash cannot import from
// slides/, and PLATFORM §9 says genericizing the engine is its own
// project).
//
// - Liveness is births vs tombs, highest (l,a) wins — delete beats
// concurrent edits, an insert is a whole-node assignment that resurrects
// by out-stamping the tomb. Values displaced during a node's dead window
// park in `stash` and replay on resurrection only while their register is
// still the winner. All three rules are slides', which earned them.
//
// - Delivery is per-actor contiguous `s` with a gap buffer, plus a `pending`
// buffer for ops naming a node we have not seen yet. Also slides'.
//
// WHAT WRITES THE DOCUMENT. Structural changes and cell writes go through the
// store's own `applyPatch` — deliberately, because rowcol.ts already names the
// failure: "Two copies of one op is how the inverse and the forward drift
// apart." A second row-splicer here would have to know about run-length rids,
// dictionary interning and dictLen truncation, and would silently diverge from
// the local path the first time either changed. Plain property sets are
// assigned directly (there is no patch that can express "delete this key" —
// `setSheetProps` refuses `undefined` on purpose — and the CRDT must be able
// to.)
import { applyPatch, readCell, type Patch } from '../store.ts'
import { APPEARANCE_FIELDS } from '../model.ts'
import type { CanvasCell, CanvasSheet, CellOverride, Column, ColumnData, DashDoc, Sheet, TableSheet } from '../model.ts'
/**
* Sync format version — stamped into SyncStateJSON (`v`) and every wire frame
* (`pv`). Mismatched state and frames are DISCARDED on sight rather than
* misread: the file still opens, it simply rejoins as a fresh adopt. Same rule
* as slides' SYNC_V and model.ts's frozen-policy handling.
*/
export const SYNC_V = 2
export const DOC_NODE = '@doc'
/**
* Top-level document keys that belong to THIS COPY and never to the room.
*
* `collab` is the room, its keys and this copy's role; `docId` is identity;
* `readonly`/`template` are what this copy may do and how it opens; `format`,
* `version` and `policy` are what this build agreed to read. None of them is
* shared content, and every one of them is something a sender could use
* against a receiver: a `set` op or a snapshot register for `collab` made
* every receiver adopt the SENDER'S room, and the next save wrote it into
* their file. Senders include any writer through the relay and — with no
* signature at all — any page on the same origin through the BroadcastChannel,
* which on file:// is every local document.
*
* Refused on the way in (`applySet`, `mergeSnapshot`) and never emitted on the
* way out (`localOne`). A key is matched on its top-level field, so
* `collab.sync` is as local as `collab`.
*/
/**
* Names that must never be used as an object key from remote data.
*
* `target[k] = v` with k `__proto__` REPLACES the target's prototype, so a
* remote `set` named `__proto__` could make `doc.readonly` read true and
* `doc.collab` read the sender's room through inheritance, with nothing on
* the document itself to show for it. And this engine looks up per-node and
* per-actor maps with `??=` (`this.stash[node] ??= {}`, `this.gap[a] ??= []`):
* a node or actor named `constructor` or `__proto__` resolves to an INHERITED
* object there, and the write lands on `Object` or `Object.prototype` for the
* whole page. So all three are refused wherever a remote string becomes a
* key, as the whole key or as any segment of a composite one (`names.x`,
* a node id, `col:rid`). Values are never inspected — a cell may say
* "constructor".
*/
const UNSAFE_KEYS: ReadonlySet<string> = new Set(['__proto__', 'constructor', 'prototype'])
export const isUnsafeKey = (s: unknown): boolean =>
typeof s === 'string' && s.split(/[^A-Za-z0-9_$]+/).some((seg) => UNSAFE_KEYS.has(seg))
/** Any own object KEY at any depth that is unsafe, or any `id` that is (ids become keys later). */
function hasUnsafeKeys(v: unknown): boolean {
if (!v || typeof v !== 'object') return false
// An array's keys are its indices — a 100k-row column must not run the
// pattern 100k times. Only its elements can carry keys.
if (Array.isArray(v)) {
for (const x of v) if (x && typeof x === 'object' && hasUnsafeKeys(x)) return true
return false
}
for (const k of Object.keys(v)) {
if (isUnsafeKey(k)) return true
const x = (v as Record<string, unknown>)[k]
if (k === 'id' && isUnsafeKey(x)) return true
if (hasUnsafeKeys(x)) return true
}
return false
}
/** An op whose identifiers, or whose payload's keys, could reach a prototype. */
export function isUnsafeOp(op: Op): boolean {
const o = op as unknown as Record<string, unknown>
for (const f of ['a', 'n', 'k', 'sh', 'col']) if (isUnsafeKey(o[f])) return true
if (Array.isArray(o.keys) && o.keys.some(isUnsafeKey)) return true
// payload objects: their keys are written onto nodes and maps
for (const f of ['v', 'node', 'vals']) if (hasUnsafeKeys(o[f])) return true
return false
}
export const LOCAL_ONLY_DOC_KEYS: ReadonlySet<string> = new Set([
'collab', 'docId', 'readonly', 'template', 'format', 'version', 'policy',
// Volatile and history fields: never content, and the kernel engine's own
// skipDoc. Dash has no `revisions`/`trail` today; the shared history engine
// would bring them, and this set must already be right when it does.
'modified', 'revisions', 'trail',
])
export const isLocalOnlyDocKey = (k: string): boolean => {
const dot = k.indexOf('.')
return LOCAL_ONLY_DOC_KEYS.has(dot > 0 ? k.slice(0, dot) : k)
}
/** node-id separator. U+001F cannot appear in a sheet/column id: import mints
* them by slugging (import.ts) and the parser repairs anything else. */
const NS = '\u001f'
export const shNode = (sheet: string): string => `s${NS}${sheet}`
export const colNode = (sheet: string, col: string): string => `c${NS}${sheet}${NS}${col}`
export const rowNode = (sheet: string, rid: number): string => `r${NS}${sheet}${NS}${rid}`
/** cell-value key on a row node */
const vKey = (col: string): string => `v${NS}${col}`
/* --- cell-override key space on a row node ---------------------------------
*
* TWO REGISTERS PER OVERRIDE, not one: `o␟<col>` is the override's CONTENT
* (the hand correction, its provenance, the per-cell formula) and `q␟<col>` is
* its PRESENTATION (bold, colours, borders, the display pattern).
*
* Exactly the split §6.9 of docs/dash-collab.md already made for the
* spreadsheet kind's `g␟B7` / `p␟B7`, and made for the same reason: bolding a
* cell while a collaborator retypes it must keep BOTH. As one register it kept
* whichever arrived second and silently discarded the other — invisible in the
* sync state, because the register would agree on both replicas.
*
* `v`/`was`/`f` deliberately stay in ONE register together (they are
* alternatives and a split would show a formula from one replica beside a
* cached number from another), and provenance rides with them because `by`,
* `at`, `why` and `againstHash` are statements ABOUT that value.
*/
/** cell-override CONTENT key on a row node */
const oKey = (col: string): string => `o${NS}${col}`
/** cell-override PRESENTATION key on a row node */
const oPKey = (col: string): string => `q${NS}${col}`
const isVKey = (k: string): boolean => k.charCodeAt(0) === 118 /* 'v' */ && k[1] === NS
/** which half of an override this row-node key addresses: 1 content, 2 presentation */
const oHalf = (k: string): 1 | 2 => (k.charCodeAt(0) === 113 /* 'q' */ ? 2 : 1)
const keyCol = (k: string): string => k.slice(2)
/* --- spreadsheet (kind:'canvas') key spaces, all on the SHEET node ---------
* `g␟B7` the cell's content, `p␟B7` its presentation, `w␟C` a column width,
* `h␟4` a row height. The separator is what keeps them out of the sheet's
* property namespace: U+001F cannot occur in a key `setSheetProps` can write. */
const cvKey = (a1: string): string => `g${NS}${a1}`
const cvPKey = (a1: string): string => `p${NS}${a1}`
/** size key. `axis` is 'w' (column width, keyed by LETTER) or 'h' (row height,
* keyed by the 1-based number) — the two halves of an A1 address, exactly as
* `CanvasSheet.cols`/`rows` spell them. */
const cvZKey = (axis: 'w' | 'h', k: string): string => `${axis}${NS}${k}`
/** does this sheet-node register key address spreadsheet content? */
const isCvKey = (k: string): boolean =>
k[1] === NS && (k[0] === 'g' || k[0] === 'p' || k[0] === 'w' || k[0] === 'h')
const cvAddr = (k: string): string => k.slice(2)
/**
* A cell's presentation fields.
*
* Everything NOT in this set is content — including keys a future build adds,
* which is the conservative direction: an unknown field lands in the register
* that already carries `v` and `f`, so at worst it is merged more coarsely than
* it could be, never incoherently.
*/
const CV_PRES = new Set<string>([...APPEARANCE_FIELDS, 'format', 'note'])
/** stable text for one half of a cell — the comparison mint-time diffing needs */
const cvGroupText = (cell: CanvasCell | null | undefined, pres: boolean): string => {
if (!cell) return ''
const keys = Object.keys(cell).filter((k) => CV_PRES.has(k) === pres && cell[k] !== undefined).sort()
return keys.map((k) => `${JSON.stringify(k)}:${JSON.stringify(cell[k])}`).join(',')
}
/** which registers a write to this cell claims: 1 = content, 2 = presentation */
const cvMask = (prev: CanvasCell | undefined, next: CanvasCell | null): number =>
(cvGroupText(prev, false) === cvGroupText(next, false) ? 0 : 1) |
(cvGroupText(prev, true) === cvGroupText(next, true) ? 0 : 2)
/**
* A dataset override's presentation fields — the `q␟<col>` half.
*
* LITERALLY `CV_PRES`, and that is the point rather than a shortcut: the two
* kinds carry the same appearance vocabulary (model.ts `APPEARANCE_FIELDS`),
* so the engine must split them the same way or bolding a cell would merge
* differently depending on which tab it was on — which is the class of drift
* this whole change exists to end. Aliased rather than inlined so the two
* readers below say which kind they are about.
*
* Anything NOT in this set is content, including keys a future build adds:
* conservative in the safe direction, since an unknown field is then merged
* more coarsely than it could be and never incoherently.
*/
const OV_PRES = CV_PRES
/** stable text for one half of an override — the comparison mint-time diffing needs */
const ovGroupText = (cell: CellOverride | null | undefined, pres: boolean): string => {
if (!cell) return ''
const keys = Object.keys(cell).filter((k) => OV_PRES.has(k) === pres && cell[k] !== undefined).sort()
return keys.map((k) => `${JSON.stringify(k)}:${JSON.stringify(cell[k])}`).join(',')
}
/** which registers a write to this override claims: 1 = content, 2 = presentation */
const ovMask = (prev: CellOverride | undefined, next: CellOverride | null): number =>
(ovGroupText(prev, false) === ovGroupText(next, false) ? 0 : 1) |
(ovGroupText(prev, true) === ovGroupText(next, true) ? 0 : 2)
/**
* The override a claim produces — cvMerge's twin, and deliberately identical
* in shape so the two kinds cannot acquire different merge semantics.
*
* An override left with nothing at all is REMOVED (`null`): the overlay is
* sparse and an empty `{}` entry is a hand correction that says nothing, which
* validate.ts would go on to report as an override nobody can see.
*/
const ovMerge = (
base: CellOverride | undefined, payload: CellOverride | null, mask: number,
): CellOverride | null => {
const out: CellOverride = { ...(base ?? {}) }
for (const half of [false, true]) {
if (!(mask & (half ? 2 : 1))) continue
for (const k of Object.keys(out)) if (OV_PRES.has(k) === half) delete out[k]
for (const k of Object.keys(payload ?? {})) {
if (OV_PRES.has(k) !== half) continue
const v = (payload as CellOverride)[k]
if (v !== undefined) out[k] = v
}
}
return Object.keys(out).length ? out : null
}
/**
* The cell a claim produces: take the claimed halves from the payload, keep the
* rest of what is already there. A payload of `null` clears the halves it
* claims, and a cell left with nothing is REMOVED — a spreadsheet is sparse,
* and a cleared cell lingering as `{}` is neither sparse nor equal to the same
* sheet reached another way (store.ts is emphatic; test-dash-canvascells pins it).
*/
const cvMerge = (base: CanvasCell | undefined, payload: CanvasCell | null, mask: number): CanvasCell | null => {
const out: CanvasCell = { ...(base ?? {}) }
for (const half of [false, true]) {
if (!(mask & (half ? 2 : 1))) continue
for (const k of Object.keys(out)) if (CV_PRES.has(k) === half) delete out[k]
for (const [k, v] of Object.entries(payload ?? {})) {
if (CV_PRES.has(k) === half && v !== undefined) out[k] = v
}
}
return Object.keys(out).length ? out : null
}
const canvasOf = (doc: DashDoc, id: string): CanvasSheet | undefined => {
const s = doc.sheets.find((x) => x.id === id)
return s && s.kind === 'canvas' ? s : undefined
}
/** sheet id out of a sheet/column/row node id */
const nodeSheet = (node: string): string => {
const i = node.indexOf(NS)
const j = node.indexOf(NS, i + 1)
return j < 0 ? node.slice(i + 1) : node.slice(i + 1, j)
}
const nodeTail = (node: string): string => node.slice(node.indexOf(NS, node.indexOf(NS) + 1) + 1)
/* eslint-disable no-console */
const dbg = (id: string, msg: string) => {
const g = globalThis as unknown as { __dbgNode?: string; __dbgTag?: string }
// comma-separated so one run can watch a row and the column that fights it
if (g.__dbgNode && g.__dbgNode.split(',').includes(id)) console.log(` [dbg ${g.__dbgTag ?? ''} ${msg}]`)
}
// ---------------------------------------------------------------------------
// fractional order keys — base-62 midstrings (copied from slides/src/sync/crdt.ts;
// pure functions, no behaviour change, and the two engines must agree on
// nothing so the duplication is inert)
// ---------------------------------------------------------------------------
const DIGITS = '0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz'
const D = (c: string) => DIGITS.indexOf(c)
/** A key strictly between `a` and `b` ('' = unbounded on that side). */
export function keyBetween(a: string, b: string): string {
let out = ''
for (let i = 0; ; i++) {
const da = i < a.length ? D(a[i]) : 0
const db = i < b.length ? D(b[i]) : 62
if (da === db) { out += DIGITS[da]; continue }
if (db - da > 1) return out + DIGITS[Math.floor((da + db) / 2)]
out += DIGITS[da]
for (let j = i + 1; ; j++) {
const ta = j < a.length ? D(a[j]) : 0
if (62 - ta > 1) return out + DIGITS[Math.floor((ta + 62) / 2)]
out += DIGITS[ta]
}
}
}
/** Deterministic evenly-spread key for index i of n (file adoption). */
export function spreadKey(i: number, n: number): string {
let v = (i + 1) / (n + 1)
let out = ''
const need = Math.max(2, Math.ceil(Math.log(n + 2) / Math.log(62)) + 1)
for (let k = 0; k < need; k++) {
v *= 62
const d = Math.min(61, Math.floor(v))
out += DIGITS[d]
v -= d
}
while (out.length > 1 && out.endsWith('0')) out = out.slice(0, -1)
return out === '0' ? '1' : out
}
// ---------------------------------------------------------------------------
// run-length rid helpers
// ---------------------------------------------------------------------------
export type Rle = Array<[number, number]>
const rleCount = (rle: Rle): number => rle.reduce((n, [, c]) => n + c, 0)
const rleExpand = (rle: Rle): number[] => {
const out: number[] = []
for (const [start, count] of rle) for (let i = 0; i < count; i++) out.push(start + i)
return out
}
const rleCompress = (flat: number[]): Rle => {
const out: Rle = []
for (const rid of flat) {
const tail = out[out.length - 1]
if (tail && tail[0] + tail[1] === rid) tail[1]++
else out.push([rid, 1])
}
return out
}
/** position of `rid`, or -1. Walks runs, so it is O(runs) not O(rows). */
const rleIndex = (rle: Rle, rid: number): number => {
let i = 0
for (const [start, count] of rle) {
if (rid >= start && rid < start + count) return i + (rid - start)
i += count
}
return -1
}
/** rid at position `i`, or 0. */
const rleAt = (rle: Rle, i: number): number => {
if (i < 0) return 0
let seen = 0
for (const [start, count] of rle) {
if (i < seen + count) return start + (i - seen)
seen += count
}
return 0
}
const rleHas = (rle: Rle, rid: number): boolean => rleIndex(rle, rid) >= 0
// ---------------------------------------------------------------------------
// ops
// ---------------------------------------------------------------------------
export type Reg = [number, string] // [lamport, actor]
const newer = (l: number, a: string, r: Reg | undefined): boolean =>
!r || l > r[0] || (l === r[0] && a > r[1])
/**
* Strictly older than the register — the test a property write must use.
*
* Not `!newer(...)`: that also rejects the register's OWN op, and an op can be
* re-applied legitimately. A value gated behind a dead node advances the
* register and parks, and when the node comes back the parked op replays with
* exactly the stamp already recorded. `!newer` swallowed it, so the value
* arrived nowhere while a replica that saw the resurrection first kept it.
* Re-applying an op is idempotent by construction — same stamp, same value.
*/
const older = (l: number, a: string, r: Reg | undefined): boolean =>
!!r && (l < r[0] || (l === r[0] && a < r[1]))
const regNewer = (x: Reg, y: Reg | undefined): boolean => newer(x[0], x[1], y)
const cmpReg = (x: Reg, y: Reg): number => x[0] - y[0] || (x[1] < y[1] ? -1 : x[1] > y[1] ? 1 : 0)
export interface OpBase {
a: string // actor
s: number // per-actor contiguous sequence (delivery / version vector)
l: number // lamport (conflict order)
}
/** per-(node, key) LWW register. `n` absent = the document node. `v` absent =
* delete the key — the one spelling of a delete, because `JSON.stringify`
* erases `{k: undefined}` and a delete that evaporates on the wire lands on
* one replica only (rowcol.ts met this hazard twice and says so). */
export interface SetOp extends OpBase { op: 'set'; n?: string; k: string; v?: unknown }
/** cell VALUES for one column: per-(row, column) LWW. Many rids per op because
* a paste or a fill-down is one gesture and must be one undo step, one op. */
export interface CellOp extends OpBase { op: 'cell'; sh: string; col: string; rids: number[]; v: unknown[] }
/** cell OVERRIDES (the `cells` overlay), keys `<colId>:<rid>` exactly as the
* document stores them. `null` deletes (and is what survives JSON). */
/**
* DATASET cell overrides, keyed `<colId>:<rid>` on the ROW node.
*
* `v[i]` is the WHOLE override as the writer left it (or `null` = removed) and
* `m[i]` is which halves of it this write CLAIMS — 1 content, 2 presentation,
* 3 both. The payload is whole so a receiver in any state can apply the claim;
* the mask is what stops a bold click from also re-asserting a hand correction
* the writer never touched. `CvCellOp` below carries the identical pair for the
* spreadsheet kind, and the two are meant to stay identical.
*
* `m` is REQUIRED rather than optional, and SYNC_V went to 2 with it: an old
* client would ignore the field and apply the whole payload, which converges
* with itself and diverges against a new one (its concurrent bold takes the
* new client's stale value while the new client's retype drops the bold).
* Version-gating the frame turns a silent divergence into two replicas that
* simply do not speak, which is the honest failure.
*/
export interface OvrOp extends OpBase {
op: 'ovr'; sh: string; keys: string[]; v: Array<CellOverride | null>; m: number[]
}
/**
* SPREADSHEET cells (`kind:'canvas'`), keyed by A1 address on the sheet node.
*
* `v[i]` is the WHOLE cell as the writer left it (or `null` = removed, the
* spelling that survives JSON), and `m[i]` is which halves of it this write
* CLAIMS — 1 content, 2 presentation, 3 both. The payload is whole so a
* receiver in any state can apply the claim; the mask is what stops a bold
* click from also re-asserting a value the writer never touched.
*
* Many addresses per op because a paste, a fill and a delete are each one edit
* to a reader and must be one undo step — the same rule `setCanvasCells` gives.
*/
export interface CvCellOp extends OpBase {
op: 'cvc'; sh: string; keys: string[]; v: Array<CanvasCell | null>; m: number[]
}
/** SPREADSHEET column widths and row heights. `keys` are already prefixed
* `w<letter>` / `h<number>`, so one op carries both axes exactly as the patch
* does. `null` removes the entry (and the container with the last of them —
* applyPatch owns that rule, and it is why this is a separate op there). */
export interface CvSizeOp extends OpBase {
op: 'cvz'; sh: string; keys: string[]; v: Array<number | null>
}
/**
* Row insert. `ord[i]` is the row's fractional key, never a position:
* positions shift under concurrency and a key does not. `vals` is colId → one
* value per rid, the shape store.ts's insertRows patch already carries.
*/
export interface RinsOp extends OpBase {
op: 'rins'; sh: string; rids: number[]; ord: string[]
vals?: Record<string, unknown[]>
}
/** Row delete. Carries nothing but the rids: a fractional key needs no
* tombstone to stay meaningful, so a dead row leaves nothing behind but its
* tombstone stamp. */
export interface RdelOp extends OpBase { op: 'rdel'; sh: string; rids: number[] }
/**
* Sheet or column insert (the node id says which).
*
* A COLUMN insert carries metadata only — never its values. Its values follow
* as an ordinary `cell` op, minted in the same commit. That is a deliberate
* narrowing: while a column payload assigned cells, every cell in the sheet
* had TWO possible owners (the column's payload and the row's), the answer
* depended on which insert out-stamped the other, and the rig kept finding
* orderings where two replicas disagreed about a number. With values riding as
* cell ops there is exactly one writer per cell and the register decides, as
* it does for everything else.
*
* The price, stated plainly: adding a fully-populated column mints one
* register per cell, so a 100k-row column costs ~100k register entries in the
* sync state (and in `collab.sync` if the file is saved mid-session). Adding
* columns in bulk is what IMPORT does, and import creates a whole SHEET, whose
* insert does carry its rows wholesale. See docs/dash-collab.md.
*/
export interface InsOp extends OpBase {
op: 'ins'; n: string; ord: string
node: Sheet | Column
/**
* A column's storage ENCODING (never its values). The receiver creates the
* column empty in this encoding and the cell op fills it. Without it a
* re-created column could come back `raw` on one replica and `dict` on
* another, and then the same write lands as the number 5795 here and the
* string "5795" there — dictionary storage interns through String().
*/
enc?: 'raw' | 'dict'
}
export interface DelOp extends OpBase { op: 'del'; n: string }
export interface OrdOp extends OpBase { op: 'ord'; n: string; ord: string }
export type Op = SetOp | CellOp | OvrOp | CvCellOp | CvSizeOp | RinsOp | RdelOp | InsOp | DelOp | OrdOp
// ---------------------------------------------------------------------------
// serializable state
// ---------------------------------------------------------------------------
interface PosEntry { p: string; o: string; r: Reg }
export interface SyncStateJSON {
v: number
lamport: number
vv: Record<string, number>
/** NESTED by node, so a row's twelve cell registers name the row once. The
* flat `"<node> <key>"` map slides uses would repeat a 40-byte composite
* row-node id per cell — measurable in a file, not in a deck. */
regs: Record<string, Record<string, Reg>>
pos: Record<string, PosEntry>
births: Record<string, Reg>
tombs: Record<string, Reg>
/** inserted row node → its fractional order key. Baseline rows are absent
* and derive theirs from `base`, which is the whole scaling trick. */
rpos: Record<string, string>
/**
* inserted row node → the columns its insert actually carried.
*
* One entry per inserted ROW (a dozen short ids), not one per cell, which is
* what keeps this O(inserts). It is what makes "the insert supersedes older
* writes" precise: an insert minted before a column existed says nothing
* about that column, and must not out-stamp a value written into it.
*/
rnamed: Record<string, string[]>
/** sheet id → the row sequence as ADOPTED (from the file, or from a sheet
* insert's payload). Gives baseline rows the anchor they never had an op
* for. Run-length encoded: 20 bytes for 4200 rows. */
base: Record<string, Rle>
stash: Record<string, Record<string, { v?: unknown; r: Reg }>>
}
export interface ApplyResult {
changed: boolean
/** rows/columns/sheets appeared or moved — the grid must relayout, not repaint */
structure: boolean
}
const clone = <T>(v: T): T => (v === undefined ? v : JSON.parse(JSON.stringify(v)) as T)
// ---------------------------------------------------------------------------
export class DashSync {
actor: string
lamport = 0
vv: Record<string, number> = {}
private seq = 0
regs: Record<string, Record<string, Reg>> = {}
pos: Record<string, PosEntry> = {}
births: Record<string, Reg> = {}
tombs: Record<string, Reg> = {}
rpos: Record<string, string> = {}
rnamed: Record<string, string[]> = {}
base: Record<string, Rle> = {}
stash: Record<string, Record<string, { v?: unknown; r: Reg }>> = {}
/** ops naming a node we have not seen yet, keyed by node id */
private pending: Record<string, Op[]> = {}
/** out-of-order ops per actor awaiting their gap to fill */
private gap: Record<string, Op[]> = {}
/**
* Per-sheet row order as of the last mutation we know about — the PRE-state
* a local delete needs (it has to read the cell values it displaces before
* the store removes them) and the list an insert's anchors are read off.
* Run-length encoded, so a 4200-row sheet is 20 bytes here too.
*/
private rids: Record<string, Rle> = {}
/**
* Local structural changes waiting for the store to apply them.
*
* `local()` runs BEFORE the store mutates the document, so it cannot do the
* reclaiming that the remote paths do inline. The session calls settle()
* straight after the commit and these are replayed there.
*/
private localRows: Array<{ sh: string; rid: number; birth: Reg; named: string[]; vals: Record<string, unknown> }> = []
private localCols: Array<{ sh: string; col: string; birth: Reg; enc?: 'raw' | 'dict'; rids: number[]; vals: unknown[] }> = []
/**
* A local patch this engine cannot express as ops (a future patch op, or one
* of the store's reserved `applySteps`/`refreshBinding`). The session ships a
* state snapshot instead of silently dropping the change — an edit the user
* believes landed is the one failure mode worth extra machinery.
*/
unsynced = false
/** base-62-safe form of the actor id, appended to every minted order key */
private keySuffix: string
constructor(actor: string) {
this.actor = actor
this.keySuffix = actor.replace(/[^0-9A-Za-z]/g, '') || '1'
}
/** actors with buffered out-of-order ops → catch-up should be requested */
get gappedActors(): string[] {
return Object.keys(this.gap).filter((a) => this.gap[a].length)
}
/** dead iff the latest delete out-stamps the latest insert */
dead(node: string): boolean {
const t = this.tombs[node]
if (!t) return false
const b = this.births[node]
return !b || !regNewer(b, t)
}
/** did the insert that created this row carry a value for `col`? */
private rowNames(node: string, col: string): boolean {
const l = this.rnamed[node]
return !!l && l.includes(col)
}
private reg(node: string, key: string): Reg | undefined {
return this.regs[node]?.[key]
}
private setReg(node: string, key: string, r: Reg): void {
;(this.regs[node] ??= {})[key] = r
}
toJSON(): SyncStateJSON {
return {
v: SYNC_V,
lamport: this.lamport,
vv: this.vv,
regs: this.regs,
pos: this.pos,
births: this.births,
tombs: this.tombs,
rpos: this.rpos,
rnamed: this.rnamed,
base: this.base,
stash: this.stash,
}
}
static fromJSON(actor: string, j: SyncStateJSON): DashSync {
const s = new DashSync(actor)
if (!j || j.v !== SYNC_V) return s // unreadable state: rejoin as a fresh adopt
s.lamport = j.lamport ?? 0
s.vv = j.vv ?? {}
s.seq = s.vv[actor] ?? 0
s.regs = j.regs ?? {}
s.pos = j.pos ?? {}
s.births = j.births ?? {}
s.tombs = j.tombs ?? {}
s.rpos = j.rpos ?? {}
s.rnamed = j.rnamed ?? {}
s.base = j.base ?? {}
s.stash = j.stash ?? {}
return s
}
// --- adoption ------------------------------------------------------------
/**
* Adopt a document that has never synced: deterministic pos keys from the
* current array order (two readers of one file derive the same keys) with
* the null register [0,''] that loses to every real op.
*
* ROWS GET NOTHING, and that is the whole scaling decision. Their order is
* the file's own `rids`, which every replica of that file already agrees on,
* so an untouched row costs zero bytes of sync state.
*/
adopt(doc: DashDoc): void {
const ns = doc.sheets.length
doc.sheets.forEach((s, i) => {
const sn = shNode(s.id)
if (!this.pos[sn]) this.pos[sn] = { p: DOC_NODE, o: spreadKey(i, ns), r: [0, ''] }
if (s.kind !== 'table') return
// the baseline sequence: what every replica of THIS file agrees the row
// order was before anybody edited it
this.base[s.id] ??= clone(s.rids)
this.seedColumnPos(s)
})
this.snapRids(doc)
}
/**
* Give a table sheet's columns their deterministic order keys.
*
* Every replica must do this for every sheet it ever holds, however the
* sheet arrived — from the file, from a peer's insert, or from a snapshot.
* Miss one and the column order stops being a function of the keys: the
* replica that MINTED an addColumn keeps the store's array position while
* everyone else sorts by keys the payload's columns never got, and the two
* show the same columns in different orders.
*/
private seedColumnPos(sheet: Sheet): void {
if (sheet.kind !== 'table') return
const sn = shNode(sheet.id)
const n = sheet.columns.length
sheet.columns.forEach((c, j) => {
const cn = colNode(sheet.id, c.id)
if (!this.pos[cn]) this.pos[cn] = { p: sn, o: spreadKey(j, n), r: [0, ''] }
})
}
/**
* Refresh the row-order shadow, and drop an override overlay that has been
* emptied.
*
* `cells: {}` is not a state the document should ever be in: an empty
* overlay is the absence of an overlay. It arises because `setOverrides`'s
* INVERSE only carries `dropEmpty` when the container did not exist before
* the patch, so undoing the removal of the last override leaves the empty
* object behind — on the undoing replica alone, since every peer receives
* the op through a path that always drops it. A twelve-byte difference in
* the saved file, and a diverged fingerprint. (The real fix is one flag in
* store.ts; see docs/dash-collab.md.)
*/
private snapRids(doc: DashDoc): void {
const seen = new Set<string>()
for (const s of doc.sheets) {
if (s.kind !== 'table') continue
seen.add(s.id)
if (s.cells && !Object.keys(s.cells).length) delete s.cells
// The watermark joins here, on every settle point, because it is
// document data that a plain monotonic counter cannot converge — see
// settleWatermark.
settleWatermark(s, this.births)
this.rids[s.id] = clone(s.rids)
}
for (const id of Object.keys(this.rids)) if (!seen.has(id)) delete this.rids[id]
}
// --- local op minting ----------------------------------------------------
private stamp(): OpBase {
this.lamport++
this.seq++
this.vv[this.actor] = this.seq
return { a: this.actor, s: this.seq, l: this.lamport }
}
/**
* Mint ops for patches the store is ABOUT TO APPLY.
*
* Pre-apply, deliberately, and it is the one ordering subtlety in this file:
* a delete has to read what it displaces (the row's registered cell values
* park in the stash so a later resurrection can lose to them) and a delete's
* `prev` anchors have to be read before the rows go. Everything else is
* indifferent. The engine keeps its own run-length row shadow so it never
* needs to look at a post-state.
*/
local(doc: DashDoc, patches: Patch[]): Op[] {
const ops: Op[] = []
for (const p of patches) this.localOne(doc, p, ops)
return ops
}
private localOne(doc: DashDoc, p: Patch, ops: Op[]): void {
const push = <T extends Op>(o: T): T => {
// Never put this copy's own keys on the wire (LOCAL_ONLY_DOC_KEYS).
if (o.op === 'set' && ((o as unknown as SetOp).n ?? DOC_NODE) === DOC_NODE && isLocalOnlyDocKey((o as unknown as SetOp).k)) return o
ops.push(o)
return o
}
switch (p.op) {
case 'setCells': {
// dictLen is a local undo artefact (it truncates a dictionary this edit
// grew); shipping it would truncate the RECEIVER's dictionary, which
// has a different length. Values are the wire format, never indices.
//
// It also has to be DISARMED HERE, on the patch the store is about to
// apply, and that is not tidiness — it is a silent data loss.
//
// A dictionary column's `idx` array points into a dictionary SHARED by
// every cell in the column, and `applyPatch` honours `dictLen` with a
// blunt `data.dict.length = p.dictLen`. That is sound for one writer:
// the only entries above the watermark are the ones this patch interned,
// and undo unwinds edits in the order they were made, so the dictionary
// is always exactly the length the inverse expects. Under collaboration
// it is false. A remote `cell` op that lands BETWEEN a local commit and
// its undo interns its own strings into the same dictionary, above the
// watermark the inverse recorded — so the undo drops them, and every
// cell pointing at them reads back null. It is asymmetric by
// construction: only the undoing replica truncates, only the values it
// did not author are lost, and NOTHING in the sync state changes — no
// register moves, no birth, no tomb — so the two replicas end up with
// identical sync states and different workbooks. That is exactly the
// shape of rig seeds 124 (ACTORS=4, STEPS=250) and 307 (ACTORS=5,
// STEPS=300): a text column with two blanks where a peer's values were,
// and every other field in agreement.
//
// The neighbouring guess — that the loss was in the column dead-window
// path (resetColumnValues/parkColumn) — was wrong; the column in both
// seeds was never deleted at all. The undo that loses the values need
// not even name the affected rows.
//
// Disarming costs the orphaned strings (the dictionary no longer shrinks
// back), which store.ts already calls "semantically right and no longer
// byte-identical". A live session has given that up regardless: two
// replicas intern in the order their ops arrive, so their dictionaries
// never matched byte-for-byte — which is why the rig's fingerprint
// compares materialized values, not encodings.
delete p.dictLen
const o = push<CellOp>({ ...this.stamp(), op: 'cell', sh: p.sheet, col: p.col, rids: p.rids.slice(), v: clone(p.v) })
p.rids.forEach((rid) => this.setReg(rowNode(p.sheet, rid), vKey(p.col), [o.l, o.a]))
break
}
case 'setOverrides': {
// Diffed against the PRE-state, for the reason `setCanvasCells` gives
// two arms down: the patch carries WHOLE overrides (cellfmt.ts writes
// `{...over, bold:true}`), so the object alone cannot say whether the
// correction moved, the formatting moved, or neither.
const sheet = tableOf(doc, p.sheet)
const keys: string[] = []
const vals: Array<CellOverride | null> = []
const masks: number[] = []
for (let i = 0; i < p.keys.length; i++) {
const k = p.keys[i]
const next = (p.v[i] ?? null) as CellOverride | null
const m = ovMask(sheet?.cells?.[k], next)
if (!m) continue // wrote what was already there: nothing to claim
keys.push(k)
vals.push(next)
masks.push(m)
}
if (!keys.length) break
const o = push<OvrOp>({
...this.stamp(), op: 'ovr', sh: p.sheet, keys, v: clone(vals), m: masks,
})
keys.forEach((k, i) => {
const col = k.slice(0, k.indexOf(':'))
const rid = Number(k.slice(k.indexOf(':') + 1))
const node = rowNode(p.sheet, rid)
if (masks[i] & 1) this.setReg(node, oKey(col), [o.l, o.a])
if (masks[i] & 2) this.setReg(node, oPKey(col), [o.l, o.a])
})
break
}
case 'setCanvasCells': {
// Diffed against the PRE-state, which is the only place the claim can
// be computed: the patch carries whole cells (cellprops.ts writes
// `{...cell, bold:true}`), so the object alone cannot say whether the
// value moved, the formatting moved, or neither.
const sheet = canvasOf(doc, p.sheet)
const n = shNode(p.sheet)
const keys: string[] = []
const vals: Array<CanvasCell | null> = []
const masks: number[] = []
for (const [k, next] of Object.entries(p.cells)) {
const m = cvMask(sheet?.cells?.[k], next ?? null)
if (!m) continue // wrote what was already there: nothing to claim
keys.push(k)
vals.push(next ?? null)
masks.push(m)
}
if (!keys.length) break
const o = push<CvCellOp>({ ...this.stamp(), op: 'cvc', sh: p.sheet, keys, v: clone(vals), m: masks })
keys.forEach((k, i) => {
if (masks[i] & 1) this.setReg(n, cvKey(k), [o.l, o.a])
if (masks[i] & 2) this.setReg(n, cvPKey(k), [o.l, o.a])
})
break
}
case 'setCanvasSizes': {
const n = shNode(p.sheet)
const keys: string[] = []
const vals: Array<number | null> = []
for (const [k, v] of Object.entries(p.cols ?? {})) { keys.push(`w${k}`); vals.push(v ?? null) }
for (const [k, v] of Object.entries(p.rows ?? {})) { keys.push(`h${k}`); vals.push(v ?? null) }
if (!keys.length) break
const o = push<CvSizeOp>({ ...this.stamp(), op: 'cvz', sh: p.sheet, keys, v: vals.slice() })
keys.forEach((k) => this.setReg(n, cvZKey(k[0] as 'w' | 'h', k.slice(1)), [o.l, o.a]))
break
}
case 'insertRows': {
const before = this.rids[p.sheet] ?? []
// Simulate the store's own splice (store.ts insertRows: ascending by
// position, each `at` a position in the GROWING list) so the keys are
// minted between the right neighbours — including rows inserted
// earlier in this same patch, which is why the keys are assigned in
// the same ascending pass rather than up front.
const flat = rleExpand(before)
const order = p.rids.map((rid, i) => ({ rid, at: p.at?.[i] ?? flat.length + i, i }))
.sort((a, b) => a.at - b.at)
const ord: string[] = new Array(p.rids.length).fill('')
for (const { rid, at, i } of order) {
const pos = Math.min(at, flat.length)
const lo = pos > 0 ? this.rowKey(p.sheet, flat[pos - 1]) : ''
const hi = pos < flat.length ? this.rowKey(p.sheet, flat[pos]) : ''
// The actor suffix is not decoration. Two replicas inserting between
// the same neighbours compute the SAME midstring, and then the list
// each one materialises depends on which rows it happened to have —
// one replica's sequence stops being sorted by key and every later
// binary search lands somewhere else (rig seed 42). Suffixing makes
// every key unique, so the sequence is sorted by construction on
// every replica. Safe to append: keyBetween never returns a key that
// is a prefix of its upper bound, so extending it cannot overshoot.
const key = keyBetween(lo, hi) + this.keySuffix
ord[i] = key
this.rpos[rowNode(p.sheet, rid)] = key
flat.splice(pos, 0, rid)
}
const o = push<RinsOp>({
...this.stamp(), op: 'rins', sh: p.sheet, rids: p.rids.slice(), ord,
...(p.values ? { vals: clone(p.values) } : {}),
})
p.rids.forEach((rid) => {
const n = rowNode(p.sheet, rid)
dbg(n, `local rins@${o.l} vals=${JSON.stringify(Object.fromEntries(Object.entries(p.values ?? {}).map(([c, a]) => [c, a[p.rids.indexOf(rid)]])))}`)
this.births[n] = [o.l, o.a]
this.rnamed[n] = Object.keys(p.values ?? {})
// NOT `delete this.stash[n]`: values parked for columns this insert
// does not carry still belong to the row, and settle() is what puts
// them back. Dropping them here left the author of an undo showing a
// blank cell that every collaborator could see filled in.
const at = p.rids.indexOf(rid)
const vals: Record<string, unknown> = {}
for (const [col, arr] of Object.entries(p.values ?? {})) vals[col] = arr[at]
this.localRows.push({ sh: p.sheet, rid, birth: [o.l, o.a], named: this.rnamed[n], vals })
})
this.rids[p.sheet] = rleCompress(flat)
break
}
case 'deleteRows': {
const before = this.rids[p.sheet] ?? []
const sheet = tableOf(doc, p.sheet)
const o = push<RdelOp>({ ...this.stamp(), op: 'rdel', sh: p.sheet, rids: p.rids.slice() })
p.rids.forEach((rid) => {
const n = rowNode(p.sheet, rid)
dbg(n, `local rdel@${o.l}`)
if (sheet) this.stashRow(sheet, p.sheet, rid)
this.tombs[n] = [o.l, o.a]
})
const flat = rleExpand(before).filter((r) => !p.rids.includes(r))
this.rids[p.sheet] = rleCompress(flat)
break
}
case 'addColumn': {
const sheet = tableOf(doc, p.sheet)
const ids = sheet ? sheet.columns.map((c) => c.id) : []
const at = p.at ?? ids.length
ids.splice(at, 0, p.column.id)
const ord = this.keyAround(shNode(p.sheet), ids.map((id) => colNode(p.sheet, id)), at)
const n = colNode(p.sheet, p.column.id)
const o = push<InsOp>({
...this.stamp(), op: 'ins', n, ord, node: clone(p.column),
// `pack` is an author-chosen archive encoding that cannot be written
// into (store.ts refuses); a synced column comes back writable.
...(p.data ? { enc: p.data.enc === 'dict' ? 'dict' as const : 'raw' as const } : {}),
})
// The values follow as a cell op — see InsOp. Nulls are skipped: a
// blank needs no register, and a fresh column is blank everywhere.
const keep: number[] = []
const vals: unknown[] = []
if (p.data) {
const rids = rleExpand(this.rids[p.sheet] ?? [])
rids.forEach((rid, i) => {
const v = readCell(p.data!, i)
if (v === null || v === undefined) return
keep.push(rid)
vals.push(v)
})
if (keep.length) {
const c = push<CellOp>({ ...this.stamp(), op: 'cell', sh: p.sheet, col: p.column.id, rids: keep, v: clone(vals) })
keep.forEach((rid) => this.setReg(rowNode(p.sheet, rid), vKey(p.column.id), [c.l, c.a]))
}
}
this.births[n] = [o.l, o.a]
this.pos[n] = { p: shNode(p.sheet), o: ord, r: [o.l, o.a] }
delete this.stash[n]
this.localCols.push({
sh: p.sheet, col: p.column.id, birth: [o.l, o.a],
...(p.data ? { enc: p.data.enc === 'dict' ? 'dict' as const : 'raw' as const } : {}),
rids: keep, vals: clone(vals),
})
break
}
case 'removeColumn': {
const n = colNode(p.sheet, p.col)
const sheet = tableOf(doc, p.sheet)
const col = sheet?.columns.find((c) => c.id === p.col)
const o = push<DelOp>({ ...this.stamp(), op: 'del', n })
if (sheet) this.parkColumn(sheet, p.col)
if (col) this.stashNode(col as unknown as Record<string, unknown>, n)
this.tombs[n] = [o.l, o.a]
break
}
case 'reorderColumns': {
this.diffOrder(p.order.map((id) => colNode(p.sheet, id)), shNode(p.sheet), push)
break
}
case 'setColumn': {
const n = colNode(p.sheet, p.col)
for (const [k, v] of Object.entries(p.patch)) {
const o = push<SetOp>({ ...this.stamp(), op: 'set', n, k, ...(v === undefined ? {} : { v: clone(v) }) })
this.setReg(n, k, [o.l, o.a])
}
break
}
case 'setSheetProps': {
const n = shNode(p.sheet)
for (const [k, v] of Object.entries(p.props)) {
const o = push<SetOp>({ ...this.stamp(), op: 'set', n, k, v: clone(v) })
this.setReg(n, k, [o.l, o.a])
}
for (const k of p.drop ?? []) {
const o = push<SetOp>({ ...this.stamp(), op: 'set', n, k })
this.setReg(n, k, [o.l, o.a])
}
break
}
case 'setMeasure': {
const k = `measures.${p.name}`
const o = push<SetOp>({ ...this.stamp(), op: 'set', k, ...(p.measure === undefined ? {} : { v: clone(p.measure) }) })
this.setReg(DOC_NODE, k, [o.l, o.a])
break
}
case 'setTitle': {
const o = push<SetOp>({ ...this.stamp(), op: 'set', k: 'title', v: p.title })
this.setReg(DOC_NODE, 'title', [o.l, o.a])
break
}
default:
// applySteps / refreshBinding (the store refuses both today), or a
// patch op a future build minted. Never silently dropped: the session
// ships a whole-state snapshot, which is slower and always correct.
this.unsynced = true
break
}
}
/** Sheets are added by `replaceDoc` today (there is no addSheet patch), so
* their ops are minted explicitly by the session's structural reconciler. */
sheetIns(doc: DashDoc, sheet: Sheet): InsOp {
const ids = doc.sheets.map((s) => shNode(s.id))
const at = doc.sheets.findIndex((s) => s.id === sheet.id)
const ord = this.keyAround(DOC_NODE, ids, at < 0 ? ids.length : at)
const n = shNode(sheet.id)
const o: InsOp = { ...this.stamp(), op: 'ins', n, ord, node: clone(sheet) }
this.births[n] = [o.l, o.a]
this.pos[n] = { p: DOC_NODE, o: ord, r: [o.l, o.a] }
delete this.stash[n]
if (sheet.kind === 'table') {
this.rids[sheet.id] = clone(sheet.rids)
this.base[sheet.id] ??= clone(sheet.rids)
this.seedColumnPos(sheet)
}
return o
}
sheetDel(sheetId: string): DelOp {
const n = shNode(sheetId)
const o: DelOp = { ...this.stamp(), op: 'del', n }
this.tombs[n] = [o.l, o.a]
delete this.rids[sheetId]
return o
}
/** ord key for position i within `nodes` under parent `p` */
private keyAround(p: string, nodes: string[], i: number): string {
const ordOf = (n: string | undefined) =>
n && this.pos[n] && this.pos[n].p === p ? this.pos[n].o : undefined
let lo = ''
for (let k = i - 1; k >= 0; k--) { const o = ordOf(nodes[k]); if (o) { lo = o; break } }
let hi = ''
for (let k = i + 1; k < nodes.length; k++) {
const o = ordOf(nodes[k])
if (o && (!lo || o > lo)) { hi = o; break }
}
return keyBetween(lo, hi)
}
/** Emit ord ops for nodes whose relative order changed: keep a longest
* increasing run (by current pos key) untouched, re-key the rest. */
private diffOrder(nodes: string[], parent: string, push: <T extends Op>(o: T) => T): void {
if (nodes.some((n) => !this.pos[n])) return // unknown — keyed elsewhere
const keys = nodes.map((n) => this.pos[n].o + ' ' + n)
const keep = new Set(longestIncreasing(keys))
for (let i = 0; i < nodes.length; i++) {
if (keep.has(i) && this.pos[nodes[i]].p === parent) continue
let lo = ''
for (let k = i - 1; k >= 0; k--) {
const e = this.pos[nodes[k]]
if (e && e.p === parent) { lo = e.o; break }
}
let hi = ''
for (let k = i + 1; k < nodes.length; k++) {
if (!keep.has(k)) continue
const e = this.pos[nodes[k]]
if (e && e.p === parent && e.o > lo) { hi = e.o; break }
}
const ord = keyBetween(lo, hi)
const o = push<OrdOp>({ ...this.stamp(), op: 'ord', n: nodes[i], ord })
this.pos[nodes[i]] = { p: parent, o: ord, r: [o.l, o.a] }
}
}
// --- applying remote ops -------------------------------------------------
apply(doc: DashDoc, ops: Op[]): ApplyResult {
const res: ApplyResult = { changed: false, structure: false }
for (const op of ops) this.applyOne(doc, op, res)
this.reconcileParked(doc)
if (res.structure) this.rematerialize(doc)
this.snapRids(doc)
return res
}
private applyOne(doc: DashDoc, op: Op, res: ApplyResult): void {
if (op.a === this.actor) return // our own ops are pre-applied at mint time
// The actor names keys below (`this.vv[op.a]`, `this.gap[op.a] ??= []`)
// before anything else looks at the op, so it is checked first, and such
// an op is not even delivered: no honest replica has that actor id.
if (isUnsafeKey(op.a)) return
const seen = this.vv[op.a] ?? 0
if (op.s <= seen) return // duplicate
if (op.s > seen + 1) {
const g = (this.gap[op.a] ??= [])
if (!g.some((o) => o.s === op.s)) { g.push(op); g.sort((x, y) => x.s - y.s) }
return
}
this.vv[op.a] = op.s
this.lamport = Math.max(this.lamport, op.l)
this.applyEffect(doc, op, res)
const g = this.gap[op.a]
while (g && g.length && g[0].s === this.vv[op.a] + 1) {
const next = g.shift()!
this.vv[op.a] = next.s
this.lamport = Math.max(this.lamport, next.l)
this.applyEffect(doc, next, res)
}
}
private applyEffect(doc: DashDoc, op: Op, res: ApplyResult): void {
// Delivered (the sequence advanced, so no gap and no `need` storm) but
// without effect. Gap-buffered and parked ops replay through here too.
if (isUnsafeOp(op)) return
switch (op.op) {
case 'set': this.applySet(doc, op, res); break
case 'cell': this.applyCell(doc, op, res); break
case 'ovr': this.applyOvr(doc, op, res); break
case 'cvc': this.applyCvCell(doc, op, res); break
case 'cvz': this.applyCvSize(doc, op, res); break
case 'rins': this.applyRins(doc, op, res); break
case 'rdel': this.applyRdel(doc, op, res); break
case 'ins': this.applyIns(doc, op, res); break
case 'del': this.applyDel(doc, op, res); break
case 'ord': this.applyOrd(doc, op, res); break
}
}
private pend(node: string, op: Op): void {
dbg(node, `PEND ${op.op}@${op.l},${op.a}`)
;(this.pending[node] ??= []).push(op)
}
/**
* Drain everything parked on a sheet's members.
*
* A row that arrives INSIDE a sheet payload has no insert op of its own, so
* nothing ever fires the per-row drain for it — an override that raced ahead
* of the sheet stayed parked forever on the replicas that received it early,
* and only the author kept it. Sheet-level events therefore have to sweep
* the whole namespace, not just their own node.
*/
private drainSheet(doc: DashDoc, sheetId: string): void {
const rows = rowNode(sheetId, 0).slice(0, -1)
const cols = colNode(sheetId, '')
for (const node of Object.keys(this.pending)) {
if (node.startsWith(rows) || node.startsWith(cols)) this.drainPending(doc, node)
}
}
private drainPending(doc: DashDoc, node: string, res?: ApplyResult): void {
const ps = this.pending[node]
if (!ps) return
delete this.pending[node]
const r: ApplyResult = res ?? { changed: false, structure: false }
for (const p of ps) this.applyEffect(doc, p, r)
}
/**
* Retry every parked op after a LOCAL change has been applied.
*
* Remote ops park on nodes we have not seen; the drains that release them
* all hang off remote events. A row brought back by the user's own undo
* fires none of them, so an override or a cell edit waiting on that row
* stayed parked forever — on the peers that received it early, and only
* there (rig seed 57). The session calls this right after the store has
* applied a local commit; the queue is O(edits) and an op that still cannot
* land simply parks again.
*/
settle(doc: DashDoc): ApplyResult {
const res: ApplyResult = { changed: false, structure: false }
// (snapRids at the foot of this method performs the watermark join)
for (const { sh, rid, birth, named, vals } of this.localRows.splice(0)) {
const sheet = tableOf(doc, sh)
if (!sheet || !rleHas(sheet.rids, rid)) continue
this.replayStashRow(doc, sheet, sh, rid, birth, new Set(named))
// The remote path's park, for the local one: a value the insert carried
// for a column that does not exist here has nowhere to go, and applyPatch
// simply drops it. Park it against the row's birth so the column's
// arrival can claim it — the author of an insert must end up with the
// same cells as everyone who received it.
for (const col of named) {
if (sheet.data[col]) continue
const st = (this.stash[rowNode(sh, rid)] ??= {})
// Same rule as the remote path: a parked write NEWER than this insert
// out-stamps the insert's claim on the column and must survive it.
const cur = st[vKey(col)]
if (cur && regNewer(cur.r, birth)) continue
st[vKey(col)] = { v: clone(vals[col] ?? null), r: clone(birth) }
}
}
for (const { sh, col, birth, enc, rids, vals } of this.localCols.splice(0)) {
const sheet = tableOf(doc, sh)
if (!sheet || !sheet.columns.some((c) => c.id === col)) continue
// The author of a column insert takes the SAME path as everyone who
// receives it: reset to the encoding, then apply the values the op
// carries. The store has already written `p.data` here, and if that
// snapshot was stale (undo of a delete, rows changed since) the author
// would otherwise be the only participant holding the stale version.
this.resetColumnValues(doc, sheet, col, birth, enc)
const live = rids.filter((rid) => rleHas(sheet.rids, rid))
if (live.length && sheet.data[col]) {
applyPatch(doc, {
op: 'setCells', sheet: sh, col, rids: live,
v: live.map((rid) => clone(vals[rids.indexOf(rid)])),
})
}
}
for (const node of Object.keys(this.pending)) this.drainPending(doc, node, res)
this.reconcileParked(doc)
if (res.structure) this.rematerialize(doc)
this.snapRids(doc)
return res
}
// --- property sets --------------------------------------------------------
private applySet(doc: DashDoc, op: SetOp, res: ApplyResult): void {
const node = op.n ?? DOC_NODE
// A peer cannot set this copy's room, identity or permissions — see
// LOCAL_ONLY_DOC_KEYS. Checked before the register moves only to keep the
// state free of registers nothing may ever write; mergeSnapshot refuses
// the same keys, so a stray register would be inert either way.
if (node === DOC_NODE && isLocalOnlyDocKey(op.k)) return
if (older(op.l, op.a, this.reg(node, op.k))) return
if (node === DOC_NODE) {
this.setReg(node, op.k, [op.l, op.a])
writeDocKey(doc, op.k, op.v)
res.changed = true
return
}
// birth gate: an ins is a whole-node assignment, so sets older than the
// node's (re)birth are superseded everywhere (the register still advances)
const birth = this.births[node]
if (birth && !newer(op.l, op.a, birth)) { this.setReg(node, op.k, [op.l, op.a]); return }
if (this.dead(node)) {
this.setReg(node, op.k, [op.l, op.a])
;(this.stash[node] ??= {})[op.k] =
op.v === undefined ? { r: [op.l, op.a] } : { v: clone(op.v), r: [op.l, op.a] }
return
}
const sheetId = nodeSheet(node)
if (this.dead(shNode(sheetId))) {
// The sheet is gone, so there is nothing to write — but the register
// must still advance, or the replica that applied this op BEFORE the
// sheet died would carry a register its peers never learn and the two
// states would disagree forever about a value neither can see.
this.setReg(node, op.k, [op.l, op.a])
;(this.stash[node] ??= {})[op.k] =
op.v === undefined ? { r: [op.l, op.a] } : { v: clone(op.v), r: [op.l, op.a] }
return
}
const sheet = doc.sheets.find((s) => s.id === sheetId)
if (!sheet) { this.pend(shNode(sheetId), op); return }
let target: Record<string, unknown> | undefined
if (node[0] === 's') target = sheet as unknown as Record<string, unknown>
else {
if (sheet.kind !== 'table') return
target = sheet.columns.find((c) => c.id === nodeTail(node)) as unknown as Record<string, unknown> | undefined
if (!target) { this.pend(node, op); return }
}
this.setReg(node, op.k, [op.l, op.a])
writeKey(target, op.k, op.v)
res.changed = true
if (node[0] === 's') res.structure = true // sheet name/frozen/condfmt all relayout
}
// --- cells ----------------------------------------------------------------
private applyCell(doc: DashDoc, op: CellOp, res: ApplyResult): void {
const sheet = tableOf(doc, op.sh)
// A missing sheet is two different situations and they must not be
// conflated: DEAD means every replica will agree it is gone, so the op is
// book-kept and dropped; ABSENT means its insert is still in flight, so
// the op waits (applyDel/applyIns both drain this queue).
if (!sheet && !this.dead(shNode(op.sh))) { this.pend(shNode(op.sh), op); return }
// A formula column stores no values (model.ts: storing them would let a
// file carry a number that disagrees with the formula) — nothing to write,
// and applyPatch would throw. The register still advances so state converges.
// The COLUMN is the other half of a cell's identity, so it gates the op the
// same way the sheet does. Absent-and-not-dead means its insert is still in
// flight: pend WITHOUT advancing any register, or the drained op would find
// its own register already recorded and skip itself — the value would be
// dropped on this replica and kept on the sender's, which is how one
// workbook ends up with a number the other has never heard of.
if (sheet && !sheet.columns.some((c) => c.id === op.col)) {
if (!this.dead(colNode(op.sh, op.col))) { this.pend(colNode(op.sh, op.col), op); return }
}
// A column insert carries the whole column's values, so it is a whole-node
// assignment for every cell in it: writes older than the (re)birth lose,
// exactly as they do against a row's birth.
const colBirth = this.births[colNode(op.sh, op.col)]
const colDead = this.dead(colNode(op.sh, op.col))
// A column insert is a whole-column event: writes minted before it are
// superseded, exactly as a row insert supersedes writes to the row.
const superseded = colBirth !== undefined && !newer(op.l, op.a, colBirth)
const hasData = !!sheet?.data[op.col]
const live: number[] = []
const liveV: unknown[] = []
for (let i = 0; i < op.rids.length; i++) {
const rid = op.rids[i]
const node = rowNode(op.sh, rid)
const key = vKey(op.col)
if (older(op.l, op.a, this.reg(node, key))) continue
// The row's insert supersedes older writes ONLY into the columns it
// carried; a write into any other column is untouched by it.
const birth = this.births[node]
if (birth && !newer(op.l, op.a, birth) && this.rowNames(node, op.col)) {
this.setReg(node, key, [op.l, op.a])
continue
}
if (this.dead(node)) {
this.setReg(node, key, [op.l, op.a])
;(this.stash[node] ??= {})[key] = { v: clone(op.v[i]), r: [op.l, op.a] }
continue
}
if (!sheet || superseded) { this.setReg(node, key, [op.l, op.a]); continue }
if (colDead) {
// Buried HERE — but an undo may already have revived it elsewhere, and
// this write may out-stamp that revival, in which case the replicas
// that got them the other way round keep it. So advance the register
// (states converge) and PARK the op on the column: if the column comes
// back the write replays, and if it does not the op simply never runs.
// Dropping it instead cost exactly one replica exactly one number.
this.setReg(node, key, [op.l, op.a])
this.pend(colNode(op.sh, op.col), { ...op, rids: [rid], v: [op.v[i]] })
continue
}
if (!rleHas(sheet!.rids, rid)) {
// the row's insert has not arrived yet (cross-actor delivery race)
this.pend(node, { ...op, rids: [rid], v: [op.v[i]] })
continue
}
this.setReg(node, key, [op.l, op.a])
live.push(rid)
liveV.push(op.v[i])
}
if (!live.length || !hasData) return
applyPatch(doc, { op: 'setCells', sheet: op.sh, col: op.col, rids: live, v: clone(liveV) })
res.changed = true
}
private applyOvr(doc: DashDoc, op: OvrOp, res: ApplyResult): void {
const sheet = tableOf(doc, op.sh)
if (!sheet && !this.dead(shNode(op.sh))) { this.pend(shNode(op.sh), op); return }
const cols = new Set(op.keys.map((k) => k.slice(0, k.indexOf(':'))))
for (const c of cols) {
if (sheet && !sheet.columns.some((x) => x.id === c) && !this.dead(colNode(op.sh, c))) {
this.pend(colNode(op.sh, c), op)
return
}
}
const keys: string[] = []
const vals: Array<CellOverride | null> = []
for (let i = 0; i < op.keys.length; i++) {
const k = op.keys[i]
const col = k.slice(0, k.indexOf(':'))
const rid = Number(k.slice(k.indexOf(':') + 1))
const node = rowNode(op.sh, rid)
// Per HALF, exactly as applyCvCell does: the content register and the
// presentation register race independently, so every gate below has to
// be asked twice and may answer differently for the two. `mask` collects
// the halves that survive all of them; the payload is whole, so a half
// that loses simply is not taken from it.
let mask = 0
const halves: Array<[1 | 2, string]> = [[1, oKey(col)], [2, oPKey(col)]]
let pended = false
for (const [half, key] of halves) {
if (!(op.m[i] & half)) continue
if (older(op.l, op.a, this.reg(node, key))) continue
// Overrides are not carried by a row insert, but a row's DEATH takes
// them with it (killRowOverrides), so a rebirth does supersede an older
// one — no `rnamed` exception here, unlike cell values.
const birth = this.births[node]
if (birth && !newer(op.l, op.a, birth)) { this.setReg(node, key, [op.l, op.a]); continue }
if (this.dead(node)) {
this.setReg(node, key, [op.l, op.a])
;(this.stash[node] ??= {})[key] = { v: clone(op.v[i]), r: [op.l, op.a] }
continue
}
if (!sheet) { this.setReg(node, key, [op.l, op.a]); continue } // the sheet is gone
const cb = this.births[colNode(op.sh, col)]
if (cb && !newer(op.l, op.a, cb)) { this.setReg(node, key, [op.l, op.a]); continue } // superseded
if (this.dead(colNode(op.sh, col))) { // buried here — park it, see applyCell
this.setReg(node, key, [op.l, op.a])
if (!pended) {
this.pend(colNode(op.sh, col), { ...op, keys: [k], v: [op.v[i]], m: [op.m[i]] })
pended = true
}
continue
}
if (!rleHas(sheet.rids, rid)) {
// The row is not here yet: queue the WHOLE key (both claimed halves)
// once and leave every register alone, so the replay re-runs these
// same gates against the state the row's insert brings with it.
if (!pended) { this.pend(node, { ...op, keys: [k], v: [op.v[i]], m: [op.m[i]] }); pended = true }
mask = 0
break
}
this.setReg(node, key, [op.l, op.a])
mask |= half
}
if (!mask || !sheet) continue
keys.push(k)
vals.push(ovMerge(sheet.cells?.[k], op.v[i], mask))
}
if (!keys.length) return
applyPatch(doc, { op: 'setOverrides', sheet: op.sh, keys, v: clone(vals), dropEmpty: true })
res.changed = true
}
// --- spreadsheet cells ----------------------------------------------------
/**
* A spreadsheet write: per-(address, half) LWW on the sheet node.
*
* The gates are the ones every other value op uses, in the same order and
* for the same reasons. A sheet we have not seen yet means its insert is
* still in flight, so the op WAITS (applyIns/applyDel drain the queue); a
* sheet that is dead means every replica will agree it is gone, so the
* register advances — states must converge on a value nobody can see — and
* the value is dropped. Nothing is parked for a resurrection here: a sheet
* insert carries `cells` wholesale and out-stamps everything inside it
* (docs/dash-collab.md §6.3), so a stash entry could only fight its own
* payload.
*/
private applyCvCell(doc: DashDoc, op: CvCellOp, res: ApplyResult): void {
const n = shNode(op.sh)
const sheet = canvasOf(doc, op.sh)
if (!sheet && !this.dead(n) && !doc.sheets.some((s) => s.id === op.sh)) { this.pend(n, op); return }
const birth = this.births[n]
const cells: Record<string, CanvasCell | null> = {}
let any = false
for (let i = 0; i < op.keys.length; i++) {
const a1 = op.keys[i]
let mask = 0
for (const half of [1, 2]) {
if (!(op.m[i] & half)) continue
const key = half === 1 ? cvKey(a1) : cvPKey(a1)
if (older(op.l, op.a, this.reg(n, key))) continue
this.setReg(n, key, [op.l, op.a])
// a sheet insert is a whole-node assignment, `cells` included
if (birth && !newer(op.l, op.a, birth)) continue
if (!sheet || this.dead(n)) continue
mask |= half
}
if (!mask) continue
cells[a1] = cvMerge(sheet!.cells?.[a1], op.v[i], mask)
any = true
}
if (!any) return
applyPatch(doc, { op: 'setCanvasCells', sheet: op.sh, cells: clone(cells) })
res.changed = true
}
private applyCvSize(doc: DashDoc, op: CvSizeOp, res: ApplyResult): void {
const n = shNode(op.sh)
const sheet = canvasOf(doc, op.sh)
if (!sheet && !this.dead(n) && !doc.sheets.some((s) => s.id === op.sh)) { this.pend(n, op); return }
const birth = this.births[n]
const cols: Record<string, number | null> = {}
const rows: Record<string, number | null> = {}
let any = false
for (let i = 0; i < op.keys.length; i++) {
const axis = op.keys[i][0] as 'w' | 'h'
const k = op.keys[i].slice(1)
if (older(op.l, op.a, this.reg(n, cvZKey(axis, k)))) continue
this.setReg(n, cvZKey(axis, k), [op.l, op.a])
if (birth && !newer(op.l, op.a, birth)) continue
if (!sheet || this.dead(n)) continue
;(axis === 'w' ? cols : rows)[k] = op.v[i]
any = true
}
if (!any) return
applyPatch(doc, {
op: 'setCanvasSizes', sheet: op.sh,
...(Object.keys(cols).length ? { cols } : {}), ...(Object.keys(rows).length ? { rows } : {}),
})
res.changed = true
res.structure = true // widths and heights are layout, not paint
}
// --- rows -----------------------------------------------------------------
/**
* A row's fractional order key.
*
* Explicit for inserted rows; DERIVED for the rows that came with the sheet,
* from their position in the adopted baseline. That derivation is the reason
* a million-row workbook costs nothing to sync until somebody edits it.
*/
/** Exposed for the convergence rig's sortedness invariant — not an app
* surface. The rig asserts, after every apply, that a sheet's `rids` really
* is sorted by (key, rid); a binary search over a list that is not sorted
* lands anywhere, which is how row order diverges while every register
* agrees. */
rowOrderKey(sh: string, rid: number): string { return this.rowKey(sh, rid) }
private rowKey(sh: string, rid: number): string {
const explicit = this.rpos[rowNode(sh, rid)]
if (explicit !== undefined) return explicit
const b = this.base[sh]
if (b) {
const i = rleIndex(b, rid)
if (i >= 0) return spreadKey(i, rleCount(b))
}
// No baseline (state discarded, or a hand-built sheet): fall back to the
// rid itself so the order is at least stable and total. Padded so that 9
// sorts before 10 — an unpadded number sorts lexicographically and would
// put row 10 before row 9.
return `~${String(rid).padStart(12, '0')}`
}
/** where a key belongs in a sheet's live sequence (binary search: the list is
* always sorted by (key, rid), and rleAt walks runs, not rows) */
private rowIndexFor(sheet: TableSheet, sh: string, key: string, rid: number): number {
const after = (at: number): boolean => {
const other = rleAt(sheet.rids, at)
const k = this.rowKey(sh, other)
return k < key || (k === key && other < rid)
}
let lo = 0
let hi = rleCount(sheet.rids)
while (lo < hi) {
const mid = (lo + hi) >> 1
if (after(mid)) lo = mid + 1
else hi = mid
}
return lo
}
/**
* Move a row that is already in the sheet to where its (new) key says it
* belongs.
*
* Only a resurrection can change a live row's key, so this is rare — but it
* has to rebuild the column arrays, because a row's VALUES are addressed by
* position and moving the rid alone would hand every row below the move
* somebody else's numbers. `permuteRows` is the same routine the snapshot
* merge uses: one pass per column, dictionaries kept intact, `pack` columns
* left alone.
*/
private relocateRow(sheet: TableSheet, sh: string, rid: number): void {
const flat = rleExpand(sheet.rids)
const at = flat.indexOf(rid)
if (at < 0) return
flat.splice(at, 1)
const key = this.rowKey(sh, rid)
let lo = 0
let hi = flat.length
while (lo < hi) {
const mid = (lo + hi) >> 1
const other = flat[mid]
const k = this.rowKey(sh, other)
if (k < key || (k === key && other < rid)) lo = mid + 1
else hi = mid
}
if (lo === at) return
flat.splice(lo, 0, rid)
permuteRows(sheet, flat)
}
private applyRins(doc: DashDoc, op: RinsOp, res: ApplyResult): void {
const sheet = tableOf(doc, op.sh)
const stamp: Reg = [op.l, op.a]
if (!sheet && !this.dead(shNode(op.sh))) { this.pend(shNode(op.sh), op); return }
for (let i = 0; i < op.rids.length; i++) {
const rid = op.rids[i]
const node = rowNode(op.sh, rid)
const birth = this.births[node]
if (birth && !newer(op.l, op.a, birth)) continue // an older create
const wasKey = this.rpos[node]
this.births[node] = stamp
this.rpos[node] = op.ord[i]
this.rnamed[node] = Object.keys(op.vals ?? {})
res.changed = true
res.structure = true
// A delete still out-stamps this insert. The key is recorded above
// regardless, so ops waiting on this row can resolve now.
if (!sheet || this.dead(node)) { this.drainPending(doc, node); continue }
// AN INSERT IS A WHOLE-ROW ASSIGNMENT, and until now it only said so to
// ops that arrived AFTER it. `applyOvr` has always refused an override
// older than the row's birth ("a row's DEATH takes its overrides with
// it, so a rebirth supersedes an older one") — but nothing swept the
// overrides ALREADY IN THE DOCUMENT when a rebirth landed on a replica
// that had applied them first. So the same override survived on whoever
// heard the write before the resurrection and vanished on everybody
// else: identical registers, identical births and tombs, one workbook
// with an extra hand correction. Found at ACTORS=4 once the rig started
// racing override CONTENT against override PRESENTATION (seed 520 of
// SEEDS=800 STEPS=300); it is not a fault of that split — the same hole
// is reachable with the single register, it simply needed an
// interleaving nobody had drawn yet.
this.supersedeRowOverrides(doc, sheet, op.sh, rid, stamp)
if (rleHas(sheet.rids, rid)) {
// ALREADY HERE — and the winning insert has just given the row a NEW
// key, so the row has to MOVE to match it. Recording the key and
// leaving the row where it sat is what broke row order at six actors
// (rig seed 116).
//
// The asymmetry is exact and invisible in the sync state, because the
// key both replicas end up holding is the same one. A row deleted and
// then resurrected by TWO actors gets two competing `rins`, and the
// higher (lamport, actor) wins the key everywhere. But a replica that
// received the loser FIRST already has the row in the document, so the
// winner arrives down this branch and only updated `rpos`; a replica
// that received the winner first placed the row by binary search at the
// winning key and then discarded the loser at the "an older create"
// gate. Same `rpos`, same births, same tombs — two different sequences.
//
// Worse than one row in the wrong place: `rids` is now no longer sorted
// by (key, rid), and `rowIndexFor` is a BINARY SEARCH that assumes it
// is. Every later insert on that replica lands somewhere arbitrary, so
// one stale key spreads into a wholly different row order. That is why
// it took six actors to see — it needs two concurrent resurrections of
// one row plus a later insert to amplify.
if (wasKey !== op.ord[i]) this.relocateRow(sheet, op.sh, rid)
continue
}
const idx = this.rowIndexFor(sheet, op.sh, op.ord[i], rid)
const vals: Record<string, unknown[]> = {}
for (const [col, arr] of Object.entries(op.vals ?? {})) vals[col] = [clone(arr[i])]
const named = new Set(Object.keys(vals))
// Where a row insert and a column insert cross, the newer one owns the
// cell. The column's payload is empty by construction, so "the column
// wins" means the cell is left blank for its own cell op to fill.
for (const col of named) {
const cb = this.births[colNode(op.sh, col)]
if (cb && !regNewer(stamp, cb)) { delete vals[col]; named.delete(col) }
}
dbg(node, `rins@${op.l},${op.a} ord=${op.ord[i]} at=${idx} vals=${JSON.stringify(vals)}`)
applyPatch(doc, { op: 'insertRows', sheet: op.sh, rids: [rid], at: [idx], values: vals })
this.replayStashRow(doc, sheet, op.sh, rid, stamp, named)
// A value for a column whose insert has not arrived has nowhere to go —
// applyPatch writes only into columns that exist — so park it against
// this row's birth and let the column's arrival claim it. AFTER the
// replay, which clears the stash it just consumed. Nulls are parked too:
// the parked entry is also the RECORD that this row's insert claimed the
// column, which is what tells the arriving column to stand down.
for (const col of named) {
if (sheet.data[col]) continue
const st = (this.stash[node] ??= {})
// NEVER clobber a parked entry that is NEWER than this insert. The
// insert claims the column, but a write minted after it out-stamps the
// claim, and the parked copy may be the only one left: on the author of
// that write the value was applied straight to a live document and was
// never pended anywhere, so overwriting it here deleted it outright,
// while every replica that received the write while the column was
// buried still had it queued on the column node and replayed it when
// the column came back. Rig seed 163 (ACTORS=6, STEPS=250): five
// replicas holding a number and its own author holding a blank.
// parkColumn has always carried the equivalent rule.
const cur = st[vKey(col)]
if (cur && regNewer(cur.r, stamp)) continue
st[vKey(col)] = { v: clone(vals[col]?.[0] ?? null), r: clone(stamp) }
}
this.drainPending(doc, node)
}
}
/**
* Drop the override halves a row's (re)birth out-stamps.
*
* The document-side twin of `applyOvr`'s birth gate, and it has to exist for
* the same reason `resetColumnValues` exists beside the column-birth gate: an
* assignment that only filters ops arriving later is not an assignment, it is
* a race the delivery order decides.
*
* Per HALF, because the two registers are independent — a presentation half
* written after the resurrection survives beside a content half written
* before it, and that is the correct answer rather than a nicety. A half with
* NO register at all is superseded too: its authority is nothing, and nothing
* does not out-stamp a birth.
*/
private supersedeRowOverrides(
doc: DashDoc, sheet: TableSheet, sh: string, rid: number, birth: Reg,
): void {
if (!sheet.cells) return
const node = rowNode(sh, rid)
const keys: string[] = []
const vals: Array<CellOverride | null> = []
for (const k of Object.keys(sheet.cells)) {
if (Number(k.slice(k.indexOf(':') + 1)) !== rid) continue
const col = k.slice(0, k.indexOf(':'))
let mask = 0
const rc = this.reg(node, oKey(col))
const rp = this.reg(node, oPKey(col))
if (!rc || !regNewer(rc, birth)) mask |= 1
if (!rp || !regNewer(rp, birth)) mask |= 2
if (!mask) continue
const next = ovMerge(sheet.cells[k], null, mask)
if (next === null && sheet.cells[k] === undefined) continue
keys.push(k)
vals.push(next)
}
if (!keys.length) return
applyPatch(doc, { op: 'setOverrides', sheet: sheet.id, keys, v: vals, dropEmpty: true })
}
private applyRdel(doc: DashDoc, op: RdelOp, res: ApplyResult): void {
const sheet = tableOf(doc, op.sh)
if (!sheet && !this.dead(shNode(op.sh))) { this.pend(shNode(op.sh), op); return }
const gone: number[] = []
for (let i = 0; i < op.rids.length; i++) {
const rid = op.rids[i]
const node = rowNode(op.sh, rid)
if (!this.tombs[node] || newer(op.l, op.a, this.tombs[node])) this.tombs[node] = [op.l, op.a]
if (!this.dead(node)) continue
if (sheet && rleHas(sheet.rids, rid)) {
this.stashRow(sheet, op.sh, rid)
gone.push(rid)
}
this.drainPending(doc, node)
}
if (gone.length) {
dropRowOverrides(doc, sheet!, gone)
applyPatch(doc, { op: 'deleteRows', sheet: op.sh, rids: gone })
}
res.changed = true
res.structure = true
}
/**
* Who currently owns a cell's value?
*
* A cell sits in the intersection of TWO whole-node assignments — the row's
* insert payload and the COLUMN's insert payload — so the authority is
* max(cell register, column birth, row birth). But an assignment only claims
* the cells it actually NAMES: a row insert minted before a column existed
* says nothing about that column, and must not blank it. `fromRow` is that
* distinction — the caller knows whether the row's payload carried this
* column, because it is holding the payload. Without this the answer depended on arrival order, both ways round:
* a replica that got the column insert after a row's resurrection wrote the
* row payload's blank over a number all its peers could see (seed 18), and a
* replica that got a row insert before the column existed dropped the value
* the row was carrying for it (seed 36). Neither is recoverable later, which
* is why both are parked rather than resolved on the spot.
*/
private cellAuth(sh: string, rid: number, key: string, fromRow = true): Reg | undefined {
const r = this.reg(rowNode(sh, rid), key)
if (!isVKey(key) || !fromRow) return r
const b = this.births[rowNode(sh, rid)]
return r && (!b || regNewer(r, b)) ? r : b
}
/**
* Park a dying row's cell values so a later resurrection can lose to them.
*
* Registered cells (somebody typed in them) and cells owned by a column that
* was created after the row — everything whose authority might out-stamp the
* insert that brings the row back. Cells nobody has touched, in columns older
* than the row, have no authority to record and cost nothing here: that is
* what keeps the state O(edits) on a sheet with a million untouched rows.
*/
private stashRow(sheet: TableSheet, sh: string, rid: number): void {
const node = rowNode(sh, rid)
const at = rleIndex(sheet.rids, rid)
if (at < 0) return
const keys = new Set(Object.keys(this.regs[node] ?? {}))
for (const c of this.rnamed[node] ?? []) keys.add(vKey(c))
if (!keys.size) return
const st = (this.stash[node] ??= {})
for (const k of keys) {
// `rnamed` again: the row's birth is only an authority over the columns
// its insert carried. Parking a value under the row's stamp when the row
// never claimed that column made the stamp unrecognisable at the next
// resurrection, and the value was quietly dropped on that replica alone.
const r = this.cellAuth(sh, rid, k, !isVKey(k) || this.rowNames(node, keyCol(k)))
if (!r) continue
const v = isVKey(k) ? readCell(sheet.data[keyCol(k)], at) : sheet.cells?.[`${keyCol(k)}:${rid}`]
if (!(k in st) || cmpReg(st[k].r, r) !== 0) {
st[k] = v === undefined ? { r: clone(r) } : { v: clone(v), r: clone(r) }
}
}
}
/**
* Replay parked values over a row that has just (re)appeared.
*
* `named` is the set of columns the insert's payload carried. For those, the
* row is a competing assignment and only a NEWER authority may overwrite it.
* For every other column the row makes no claim at all, so whatever the
* column last said still stands and is restored unconditionally — otherwise
* `applyPatch`'s blank for an uncarried column silently becomes the value.
*/
private replayStashRow(doc: DashDoc, sheet: TableSheet, sh: string, rid: number, birth: Reg, named: Set<string>): void {
const node = rowNode(sh, rid)
const st = this.stash[node]
if (!st) return
const keep: Record<string, { v?: unknown; r: Reg }> = {}
for (const [k, ent] of Object.entries(st)) {
const col = keyCol(k)
// The column is not here — buried, or its insert has not landed yet.
// Either way the value STAYS PARKED rather than being written (it would
// go into a column that does not exist) or dropped (deadness is a
// transient view; an undo that revives the column is exactly the case
// where a peer still holds this value, and assignColumnData reclaims
// parked entries when the column comes back).
if (this.dead(colNode(sh, col)) || (isVKey(k) && !sheet.data[col])) { keep[k] = ent; continue }
const claims = !isVKey(k) || named.has(col)
const r = this.cellAuth(sh, rid, k, claims)
// The authority the value is being weighed under.
//
// When the row's payload CLAIMS this column the two are competing
// assignments and only a strictly newer one may survive the rebirth.
//
// When it does NOT claim it, the parked entry IS the last word for the
// cell, and asking `cellAuth(…, fromRow:false)` for a verdict was the
// seed-374/184 bug. `rnamed` records only the CURRENT birth's claim, so a
// row resurrected TWICE — the first insert naming the column, the second
// (from a peer who did not have the column yet) not naming it —
// overwrites the record that the first insert ever claimed anything.
// After that the parked entry's stamp is the older birth, `cellAuth`
// returns the bare cell register (or undefined, when the value only ever
// arrived in a row payload), the stale guard below sees two different
// stamps and drops the value — while the author of the second
// resurrection, which never held a parked copy because it never processed
// the first insert, keeps the number it already had in the document. The
// MINORITY replica was right: an insert that does not name a column makes
// no claim on it, so nothing has superseded the parked value and it must
// come back. Only something strictly NEWER than the parked stamp can
// displace it.
const auth = claims ? r : (r && regNewer(r, ent.r) ? r : ent.r)
if (!auth) continue
if (claims && !regNewer(auth, birth)) continue
// THE COLUMN'S OWN BIRTH IS THE OTHER ASSIGNMENT, and it has to be
// weighed here as well as in reconcileParked — this is where the two
// readers of the stash disagreed.
//
// A cell sits under two whole-node assignments (cellAuth says so), yet
// this replay only ever compared the parked authority against the ROW's
// rebirth. So a value parked during the COLUMN's dead window was written
// back the moment its row reappeared, no matter how much newer the
// column's resurrection was. The asymmetry that follows is exact: the
// replica that had the value in hand (parked at delete time, or stashed
// because the write arrived while the row was dead) restored it, while
// every replica that reached the column's rebirth through
// resetColumnValues — which DOES apply the rule, `!regNewer(auth, birth)`
// — correctly blanked it. Same registers, same births, same tombs on both
// sides; one number more on one workbook. Rig seed 307 (ACTORS=5,
// STEPS=300): a column removed and re-added by undo at lamport 23/24, a
// value written to it at lamport 2 and parked, and the row carrying that
// cell resurrected at lamport 8 by a peer's own undo. The [24] rebirth
// supersedes both, and only the replay thought otherwise.
//
// reconcileParked has carried this rule from the start ("The column's own
// birth beats anything parked before it"); it simply never got the chance
// to apply it, because replayStashRow runs inside applyRins and has
// already written the document by the time the batch reconciles.
const cb = this.births[colNode(sh, col)]
if (cb && !regNewer(auth, cb)) continue
// stale guard: the parked value must belong to the CURRENT authority — a
// newer write that landed elsewhere supersedes it
if (cmpReg(ent.r, auth) !== 0) continue
dbg(node, `stash-replay ${k} := ${JSON.stringify(ent.v)}`)
if (isVKey(k)) {
if (sheet.data[col]) applyPatch(doc, { op: 'setCells', sheet: sh, col, rids: [rid], v: [clone(ent.v ?? null)] })
} else {
// MERGED, not assigned: the entry is a whole override parked under ONE
// of its two register keys, so it may only put back its own half. The
// other half's entry (if its register also survived) replays beside it
// in this same loop and puts back the other. Assigning the whole thing
// would let a replayed presentation half resurrect a hand correction
// whose own register had already been superseded.
const okey = `${col}:${rid}`
applyPatch(doc, {
op: 'setOverrides', sheet: sh, keys: [okey],
v: [ovMerge(sheet.cells?.[okey], 'v' in ent ? clone(ent.v) as CellOverride : null, oHalf(k))],
dropEmpty: true,
})
}
}
if (Object.keys(keep).length) this.stash[node] = keep
else delete this.stash[node]
}
/**
* A column insert assigns the whole column: it blanks the values and keeps
* only the cells that out-stamp it — a `set` register, or the birth of a row
* created after the column and carrying it. The blanked cells are filled by
* the cell op that accompanies the insert.
*
* Runs on BOTH paths, including the one where the column is still present.
* A replica that received the resurrect before the delete never removes
* anything, and if the rebirth left its values alone it would keep numbers
* every replica that processed the delete has lost.
*
* O(edits) to find the survivors, O(rows) to rebuild the array — which is
* what the store's own addColumn costs anyway.
*/
private resetColumnValues(doc: DashDoc, sheet: TableSheet, col: string, birth: Reg, enc: 'raw' | 'dict' | undefined): void {
const key = vKey(col)
const prefix = rowNode(sheet.id, 0).slice(0, -1) // `r␟<sheet>␟`
const keeps: Array<[number, unknown]> = []
for (const node of new Set([...Object.keys(this.births), ...Object.keys(this.regs).filter((n) => key in this.regs[n])])) {
if (!node.startsWith(prefix)) continue
const rid = Number(nodeTail(node))
const at = rleIndex(sheet.rids, rid)
if (at < 0) continue
const r = this.reg(node, key)
const b = this.rowNames(node, col) ? this.births[node] : undefined
const auth = r && (!b || regNewer(r, b)) ? r : b
if (!auth || !regNewer(auth, birth)) continue
// the document if the column is still here, otherwise what its death parked
const ent = this.stash[node]?.[key]
const v = sheet.data[col] ? readCell(sheet.data[col], at)
: (ent && cmpReg(ent.r, auth) === 0 ? (ent.v ?? null) : null)
if (ent) {
delete this.stash[node][key]
if (!Object.keys(this.stash[node]).length) delete this.stash[node]
}
keeps.push([rid, v])
}
const n = rleCount(sheet.rids)
if (enc === undefined) delete sheet.data[col] // a formula column stores nothing
else if (enc === 'dict') sheet.data[col] = { enc: 'dict', dict: [], idx: new Array(n).fill(null) }
else sheet.data[col] = { enc: 'raw', v: new Array(n).fill(null) }
if (!sheet.data[col]) return
for (const [rid, v] of keeps) {
if (v === null || v === undefined) continue
applyPatch(doc, { op: 'setCells', sheet: sheet.id, col, rids: [rid], v: [clone(v)] })
}
}
/**
* Park what a column removal destroys, so a resurrection can weigh it.
*
* Cell values live in the document, not here, so once the column is gone the
* only replicas that can still produce them are the ones that kept a copy. A
* replica that had the write PENDING (the column was already buried when it
* arrived) replays it after the rebirth; this is the same guarantee for the
* replica that had already applied it. With only one of the two halves, the
* same cell came back filled on one side and empty on the other.
*/
private parkColumn(sheet: TableSheet, col: string): void {
const key = vKey(col)
const ok = oKey(col)
const okp = oPKey(col)
const prefix = rowNode(sheet.id, 0).slice(0, -1) // `r␟<sheet>␟`
const park = (node: string, k: string, v: unknown, r: Reg | undefined) => {
if (!r) return
const st = (this.stash[node] ??= {})
// Never clobber an entry that already holds this authority: it is the
// one with the value, and ours may be the blank it is waiting to fill.
if (!(k in st) || cmpReg(st[k].r, r) !== 0) st[k] = { v: clone(v), r: clone(r) }
}
for (const node of new Set([...Object.keys(this.births), ...Object.keys(this.regs).filter((n) => key in this.regs[n])])) {
if (!node.startsWith(prefix)) continue
const rid = Number(nodeTail(node))
const at = rleIndex(sheet.rids, rid)
if (at < 0) continue
park(node, key, readCell(sheet.data[col], at), this.cellAuth(sheet.id, rid, key, this.rowNames(node, col)))
}
for (const k of Object.keys(sheet.cells ?? {})) {
if (k.slice(0, k.indexOf(':')) !== col) continue
const rid = Number(k.slice(k.indexOf(':') + 1))
const node = rowNode(sheet.id, rid)
// BOTH HALVES, each under its own register's authority. Parking the whole
// override under both keys is right rather than wasteful: the replay
// merges by half (`ovMerge`), so each entry contributes only its own
// side, and a content half that outlived its presentation half — or the
// reverse — comes back exactly as far as its register earned.
park(node, ok, sheet.cells![k], this.reg(node, ok))
park(node, okp, sheet.cells![k], this.reg(node, okp))
}
}
private killColumn(doc: DashDoc, sheet: TableSheet, col: string): void {
dbg(colNode(sheet.id, col), `killColumn`)
this.parkColumn(sheet, col)
const keys = Object.keys(sheet.cells ?? {}).filter((k) => k.slice(0, k.indexOf(':')) === col)
if (keys.length) applyPatch(doc, { op: 'setOverrides', sheet: sheet.id, keys, v: keys.map(() => null), dropEmpty: true })
applyPatch(doc, { op: 'removeColumn', sheet: sheet.id, col })
}
// --- sheets and columns ---------------------------------------------------
private applyIns(doc: DashDoc, op: InsOp, res: ApplyResult): void {
const stamp: Reg = [op.l, op.a]
const node = op.n
const isSheet = node[0] === 's'
// Resolve the host sheet BEFORE stamping the birth. Stamping first and
// pending afterwards looks harmless and is not: the drained op then finds
// its own birth already recorded, fails the "an older create" gate, and
// returns — the column silently never appears.
let host: TableSheet | undefined
let sheetGone = false
if (!isSheet) {
const sheetId = nodeSheet(node)
sheetGone = this.dead(shNode(sheetId))
if (!sheetGone) {
host = tableOf(doc, sheetId)
if (!host) { this.pend(shNode(sheetId), op); return }
}
}
const birth = this.births[node]
if (birth && !newer(op.l, op.a, birth)) return // an older create
this.births[node] = stamp
if (!this.pos[node] || regNewer(stamp, this.pos[node].r)) {
this.pos[node] = { p: isSheet ? DOC_NODE : shNode(nodeSheet(node)), o: op.ord, r: stamp }
}
res.changed = true
res.structure = true
if (isSheet) {
// Derived from the payload, so every replica computes the same thing —
// and must, even when the sheet is already dead here. A replica that
// learned of the death first would otherwise be missing order keys its
// peers hold, and the two sync states would never match again.
const seed = op.node as Sheet
if (seed.kind === 'table') this.base[seed.id] ??= clone(seed.rids)
this.seedColumnPos(seed)
}
if (this.dead(node) || sheetGone) { this.drainPending(doc, node); return }
if (isSheet) {
const src = op.node as Sheet
const existing = doc.sheets.find((s) => s.id === src.id)
if (existing) {
this.assignNode(existing as unknown as Record<string, unknown>, src as unknown as Record<string, unknown>, node, stamp, SHEET_STRUCTURAL)
} else {
doc.sheets.push(clone(src))
this.replayStash(doc.sheets[doc.sheets.length - 1] as unknown as Record<string, unknown>, node, stamp)
}
const landed = doc.sheets.find((s) => s.id === src.id)
if (landed && landed.kind === 'table') {
// A payload can carry columns and rows that somebody else has already
// buried. Adopting them wholesale would resurrect the dead on whichever
// replica happened to receive the sheet last.
this.pruneDead(doc, landed)
this.rids[src.id] = clone(landed.rids)
}
this.drainSheet(doc, src.id)
} else {
const sheet = host!
const src = op.node as Column
const existing = sheet.columns.find((c) => c.id === src.id)
if (existing) {
this.assignNode(existing as unknown as Record<string, unknown>, src as unknown as Record<string, unknown>, node, stamp, ['id'])
} else {
applyPatch(doc, { op: 'addColumn', sheet: sheet.id, column: clone(src) })
this.replayStash(sheet.columns[sheet.columns.length - 1] as unknown as Record<string, unknown>, node, stamp)
}
// BOTH paths reset the values, including the one where the column is
// already here. A replica that received the resurrect before the delete
// never removes anything, and if the rebirth left its values alone it
// would keep numbers that every replica which processed the delete has
// lost. Same event, same effect, whatever order it arrives in.
this.resetColumnValues(doc, sheet, src.id, stamp, op.enc)
dbg(node, `cins@${op.l},${op.a} ${src.id}`)
}
this.drainPending(doc, node)
}
/** drop members of a freshly-adopted sheet that are dead under our liveness */
private pruneDead(doc: DashDoc, sheet: TableSheet): void {
for (let i = sheet.columns.length - 1; i >= 0; i--) {
if (!this.dead(colNode(sheet.id, sheet.columns[i].id))) continue
this.killColumn(doc, sheet, sheet.columns[i].id)
}
const dead = rleExpand(sheet.rids).filter((rid) => this.dead(rowNode(sheet.id, rid)))
if (dead.length) {
dropRowOverrides(doc, sheet, dead)
applyPatch(doc, { op: 'deleteRows', sheet: sheet.id, rids: dead })
}
}
private applyDel(doc: DashDoc, op: DelOp, res: ApplyResult): void {
const node = op.n
if (!this.tombs[node] || newer(op.l, op.a, this.tombs[node])) this.tombs[node] = [op.l, op.a]
if (this.dead(node)) {
if (node[0] === 's') {
const i = doc.sheets.findIndex((s) => s.id === nodeSheet(node))
if (i >= 0) {
this.stashNode(doc.sheets[i] as unknown as Record<string, unknown>, node)
doc.sheets.splice(i, 1)
delete this.rids[nodeSheet(node)]
}
this.drainSheet(doc, nodeSheet(node))
} else {
const sheetId = nodeSheet(node)
const sheet = tableOf(doc, sheetId)
const colId = nodeTail(node)
const col = sheet?.columns.find((c) => c.id === colId)
if (sheet && col) {
this.stashNode(col as unknown as Record<string, unknown>, node)
this.killColumn(doc, sheet, colId)
}
}
}
this.drainPending(doc, node)
res.changed = true
res.structure = true
}
private applyOrd(_doc: DashDoc, op: OrdOp, res: ApplyResult): void {
const cur = this.pos[op.n]
if (cur && !newer(op.l, op.a, cur.r)) return
const parent = op.n[0] === 's' ? DOC_NODE : shNode(nodeSheet(op.n))
this.pos[op.n] = { p: parent, o: op.ord, r: [op.l, op.a] }
// a move never resurrects, and rematerialize (run once per apply batch)
// is what turns the pos registers back into array order
if (this.dead(op.n)) return
res.changed = true
res.structure = true
}
/**
* Whole-node assignment from an insert payload: every property whose register
* is OLDER than the (re)birth takes the payload's value; properties with
* newer registers keep the set-winner. Runs identically on every replica —
* including ones where the node never died — which is what makes
* resurrection convergent.
*/
private assignNode(node: Record<string, unknown>, payload: Record<string, unknown>, id: string, birth: Reg, skip: readonly string[]): void {
for (const k of new Set([...Object.keys(node), ...Object.keys(payload)])) {
if (skip.includes(k)) continue
const r = this.reg(id, k)
if (r && regNewer(r, birth)) continue // a newer set beats the assignment
writeKey(node, k, payload[k] === undefined ? undefined : clone(payload[k]))
}
this.replayStash(node, id, birth)
}
/** park a to-be-removed node's registered property values (see replayStash) */
private stashNode(node: Record<string, unknown>, id: string): void {
const keys = this.regs[id]
if (!keys) return
const st = (this.stash[id] ??= {})
for (const [k, r] of Object.entries(keys)) {
// Spreadsheet cells are not node PROPERTIES: `node['g␟B7']` is not where
// the value lives, and replayStash would write that key onto the sheet
// object as junk. They travel in the sheet payload instead (§6.3).
if (isCvKey(k)) continue
if (!(k in st) || cmpReg(st[k].r, r) !== 0) {
st[k] = node[k] === undefined ? { r: clone(r) } : { v: clone(node[k]), r: clone(r) }
}
}
}
/** replay dead-window property values that out-rank a resurrecting insert */
private replayStash(node: Record<string, unknown>, id: string, birth: Reg): void {
const st = this.stash[id]
if (!st) return
for (const [k, ent] of Object.entries(st)) {
if (isCvKey(k)) continue // not a property of the node — see stashNode
const r = this.reg(id, k)
if (!r || !regNewer(r, birth)) continue
if (cmpReg(ent.r, r) !== 0) continue
writeKey(node, k, 'v' in ent ? clone(ent.v) : undefined)
}
delete this.stash[id]
}
/**
* Settle parked cell values whose row and column are both live again.
*
* The stash is written by four different events (a row dies, a column dies,
* a write lands on something dead, a column payload covers a row we lack)
* and read by four more, and making every pair agree on WHO reclaims WHAT
* was where the ordering bugs lived. This is the single rule instead: a
* parked value belongs to the document as soon as its row and its column are
* both there, provided it still holds the cell's authority. If it does not,
* something newer won and the parked copy is forgotten.
*
* Runs after every batch. Costs O(parked), which is O(edits) and shrinks as
* entries are consumed — never O(rows).
*/
private reconcileParked(doc: DashDoc): void {
for (const node of Object.keys(this.stash)) {
if (node[0] !== 'r') continue // sheet/column property stashes settle on rebirth
const sh = nodeSheet(node)
const rid = Number(nodeTail(node))
const sheet = tableOf(doc, sh)
if (!sheet || this.dead(node) || !rleHas(sheet.rids, rid)) continue
const st = this.stash[node]
for (const k of Object.keys(st)) {
const col = keyCol(k)
if (this.dead(colNode(sh, col))) continue // may yet be dug up
const live = isVKey(k) ? !!sheet.data[col] : sheet.columns.some((c) => c.id === col)
if (!live) continue // the column's insert has not landed here yet
const claims = !isVKey(k) || this.rowNames(node, col)
const r = this.cellAuth(sh, rid, k, claims)
// Same rule replayStashRow applies, and it has to be the same rule or
// the two readers of the stash disagree again: when the row's current
// birth does not CLAIM this column, the parked entry is the cell's last
// word and only something strictly newer displaces it. Asking for a
// register that may never have existed (the value arrived in an earlier
// insert's payload, and `rnamed` has since been overwritten by a second
// resurrection) dropped the value here too — on every replica except
// the second resurrector. Seeds 374 and 184.
const auth = claims ? r : (r && regNewer(r, st[k].r) ? r : st[k].r)
// THE ROW'S OWN REBIRTH BEATS IT TOO, and this is the rule that was
// here in `replayStashRow` and missing here — the exact asymmetry that
// file keeps warning about, "the two readers of the stash disagree".
//
// An entry only reaches this reader when `replayStashRow` had to KEEP
// it (the column was buried at the moment the row came back), so it is
// the rebirth's loser arriving by the slower road. Without the check it
// was written back unconditionally: the replica that happened to hold a
// parked copy restored a hand correction that every replica reaching
// the same rebirth through `replayStashRow` had correctly dropped.
// Same registers, same births, same tombs, one workbook with an extra
// override — rig seed 520 at ACTORS=4 (a3 wrote an override at lamport
// 19, a2 deleted and resurrected the row at 20/21, and only a3's own
// parked copy came back).
//
// OVERRIDE KEYS ONLY, deliberately narrow. An insert never carries an
// override — `applyOvr` says so in its own words ("no `rnamed`
// exception here, unlike cell values") — so for `o␟col` / `q␟col` a
// rebirth is an unconditional supersede and this is simply the rule
// the other reader already applies.
//
// Cell VALUES are not touched, and that is measured rather than
// cautious: extending it to `v␟col` (where a payload CAN claim the
// column, so the question is genuinely about the claim) diverged a
// value at ACTORS=5 seed 226 — a number that survived on the replica
// holding the parked copy and not on the one that had it in the
// document. Those paths are tuned by five closed seeds; this hole was
// in the override half, and the fix belongs there.
const rb = this.births[node]
// `auth` may be undefined here (a key whose register never existed);
// nothing does not out-stamp a birth, so it is superseded too.
if (!isVKey(k) && rb && (!auth || !regNewer(auth, rb))) { delete st[k]; continue }
// The column's own birth beats anything parked before it: a value a
// row was holding for a column that has since been (re)created belongs
// to the creation, not to the row.
const cb = this.births[colNode(sh, col)]
if (auth && cmpReg(st[k].r, auth) === 0 && !(cb && !regNewer(st[k].r, cb))) {
dbg(node, `settle parked ${k} := ${JSON.stringify(st[k].v)}`)
if (isVKey(k)) applyPatch(doc, { op: 'setCells', sheet: sh, col, rids: [rid], v: [clone(st[k].v ?? null)] })
else {
// Merged by half — replayStashRow's reasoning, and it has to be the
// same rule here or the two readers of the stash disagree again.
const okey = `${col}:${rid}`
applyPatch(doc, {
op: 'setOverrides', sheet: sh, keys: [okey],
v: [ovMerge(sheet.cells?.[okey],
st[k].v === undefined ? null : clone(st[k].v) as CellOverride, oHalf(k))],
dropEmpty: true,
})
}
}
delete st[k] // consumed, or superseded by something newer
}
if (!Object.keys(st).length) delete this.stash[node]
}
}
/** rebuild sheet and column order from pos registers (rows are maintained
* incrementally by the RGA — a global row sort would be O(rows) per op) */
private rematerialize(doc: DashDoc): void {
const ord = (n: string) => (this.pos[n] ? this.pos[n].o : '')
const cmp = (x: string, y: string) => {
const a = ord(x)
const b = ord(y)
if (a !== b) return a < b ? -1 : 1
return x < y ? -1 : 1
}
doc.sheets.sort((s1, s2) => cmp(shNode(s1.id), shNode(s2.id)))
for (const s of doc.sheets) {
if (s.kind !== 'table') continue
s.columns.sort((c1, c2) => cmp(colNode(s.id, c1.id), colNode(s.id, c2.id)))
}
}
// --- state-based merge (file forks, late joiners, catch-up beyond the log) -
/**
* Merge a remote (doc, state) pair into ours. Register-wise LWW with value
* adoption from the winning side, liveness max, and a symmetric row-order
* interleave. merge(A←B) followed by merge(B←A) must leave both identical,
* which is why nothing here may consult "which side is local".
*/
mergeSnapshot(doc: DashDoc, rdoc: DashDoc, rstate: SyncStateJSON): ApplyResult {
const res: ApplyResult = { changed: false, structure: false }
if (!rstate || rstate.v !== SYNC_V) return res
// Every map in the state is keyed by a remote node id, actor or register
// name, and the document's sheets and columns are inserted by their ids —
// one unsafe key anywhere and the WHOLE snapshot is refused. A snapshot is
// an optimisation; ops still converge without it.
if (hasUnsafeKeys(rstate) || hasUnsafeKeys(rdoc)) return res
this.lamport = Math.max(this.lamport, rstate.lamport ?? 0)
for (const [a, s] of Object.entries(rstate.vv ?? {})) {
if ((this.vv[a] ?? 0) < s) {
this.vv[a] = s
if (a === this.actor) this.seq = s
this.gap[a] = (this.gap[a] ?? []).filter((o) => o.s > s)
res.changed = true
}
}
const rebirths: string[] = []
for (const [id, r] of Object.entries(rstate.births ?? {})) {
if (!this.births[id] || regNewer(r, this.births[id])) { this.births[id] = clone(r); rebirths.push(id) }
}
for (const [id, r] of Object.entries(rstate.tombs ?? {})) {
if (!this.tombs[id] || regNewer(r, this.tombs[id])) { this.tombs[id] = clone(r); res.changed = true }
}
// A row's key is minted once and never changes, so first-wins is exact.
for (const [id, k] of Object.entries(rstate.rpos ?? {})) {
if (!(id in this.rpos)) this.rpos[id] = k
}
// Baselines: identical for two copies of one file, but two copies adopted
// at DIFFERENT points in a file's history disagree about which rows were
// there to begin with. Union them symmetrically so both sides derive the
// same keys — the alternative is two forks that each think the other's
// rows belong somewhere else.
for (const [id, b] of Object.entries(rstate.base ?? {})) {
const mine = this.base[id]
if (!mine) { this.base[id] = clone(b); continue }
const merged = mergeOrder(rleExpand(mine), rleExpand(b), () => undefined)
if (merged.length !== rleCount(mine)) this.base[id] = rleCompress(merged)
}
for (const [id, rp] of Object.entries(rstate.pos ?? {})) {
const cur = this.pos[id]
if (!cur || regNewer(rp.r, cur.r)) { this.pos[id] = clone(rp); res.changed = true; res.structure = true }
}
// --- structure: sheets, then per-sheet rows and columns
for (let i = doc.sheets.length - 1; i >= 0; i--) {
const s = doc.sheets[i]
if (this.dead(shNode(s.id))) {
this.stashNode(s as unknown as Record<string, unknown>, shNode(s.id))
doc.sheets.splice(i, 1)
delete this.rids[s.id]
res.changed = res.structure = true
}
}
for (const rs of rdoc.sheets) {
if (this.dead(shNode(rs.id))) continue
if (doc.sheets.some((s) => s.id === rs.id)) continue
doc.sheets.push(clone(rs))
this.seedColumnPos(rs)
if (rs.kind === 'table') {
this.rids[rs.id] = clone(rs.rids)
this.base[rs.id] ??= clone(rs.rids)
}
res.changed = res.structure = true
}
const rById = new Map(rdoc.sheets.map((s) => [s.id, s]))
for (const s of doc.sheets) {
if (s.kind !== 'table') continue
const rsheet = rById.get(s.id)
const rt = rsheet && rsheet.kind === 'table' ? rsheet : undefined
this.mergeColumns(doc, s, rt, res)
this.mergeRows(doc, s, rt, res)
}
// --- whole-node assignments the remote saw and we did not
for (const id of rebirths) {
if (this.dead(id) || id[0] === 'r') continue // rows assign through mergeRows
const src = remoteNode(rdoc, id)
const dst = localNode(doc, id)
if (!src || !dst) continue
this.assignNode(dst, src, id, this.births[id], id[0] === 's' ? SHEET_STRUCTURAL : ['id'])
res.changed = true
if (id[0] === 's') res.structure = true
}
// --- property registers: the winning side's value lives in its document
for (const [node, keys] of Object.entries(rstate.regs ?? {})) {
for (const [key, rr] of Object.entries(keys)) {
// the sender's room, identity and permissions are not content
if (node === DOC_NODE && isLocalOnlyDocKey(key)) continue
if (!regNewer(rr, this.reg(node, key))) continue
this.setReg(node, key, clone(rr))
if (node !== DOC_NODE) {
const b = this.births[node]
if (b && !regNewer(rr, b)) continue // superseded by a whole-node assignment
}
if (node[0] === 'r') { this.mergeCellReg(doc, rdoc, rstate, node, key, rr); continue }
// A spreadsheet cell/size lives in the sheet's own sparse maps, not in
// a property of the sheet object — the generic write below would put
// `"g␟B7": …` at the top level of the sheet and every reader of the
// file would have to explain it.
if (node[0] === 's' && isCvKey(key)) { this.mergeCvReg(doc, rdoc, node, key); continue }
if (node !== DOC_NODE && this.dead(node)) {
const src = remoteNode(rdoc, node)
const rstash = rstate.stash?.[node]?.[key]
if (src && src[key] !== undefined) (this.stash[node] ??= {})[key] = { v: clone(src[key]), r: clone(rr) }
else if (rstash) (this.stash[node] ??= {})[key] = clone(rstash)
continue
}
const src = node === DOC_NODE ? (rdoc as unknown as Record<string, unknown>) : remoteNode(rdoc, node)
const dst = node === DOC_NODE ? (doc as unknown as Record<string, unknown>) : localNode(doc, node)
if (!src || !dst) continue
if (node === DOC_NODE) writeDocKey(doc, key, readDocKey(rdoc, key))
else writeKey(dst, key, src[key])
res.changed = true
if (node === DOC_NODE || node[0] === 's') res.structure = true
}
}
this.reconcileParked(doc)
if (res.structure) this.rematerialize(doc)
this.snapRids(doc)
return res
}
/**
* One spreadsheet register during a snapshot merge: the remote holds this
* half of the cell (or this width), so take its value out of the remote
* document's sparse map and write it into ours at the same address.
*
* Reads NOTHING that says which side is local — the value comes from
* whichever side's register won, which is what makes merge(A←B) and
* merge(B←A) land in the same place.
*/
private mergeCvReg(doc: DashDoc, rdoc: DashDoc, node: string, key: string): void {
const sh = nodeSheet(node)
const sheet = canvasOf(doc, sh)
if (!sheet || this.dead(node)) return
const rsheet = canvasOf(rdoc, sh)
const addr = cvAddr(key)
if (key[0] === 'w' || key[0] === 'h') {
const v = (key[0] === 'w' ? rsheet?.cols : rsheet?.rows)?.[addr] ?? null
applyPatch(doc, {
op: 'setCanvasSizes', sheet: sh,
...(key[0] === 'w' ? { cols: { [addr]: v } } : { rows: { [addr]: v } }),
})
return
}
const merged = cvMerge(sheet.cells?.[addr], rsheet?.cells?.[addr] ?? null, key[0] === 'g' ? 1 : 2)
applyPatch(doc, { op: 'setCanvasCells', sheet: sh, cells: { [addr]: clone(merged) } })
}
/** one cell register during a snapshot merge: read the winner's value out of
* the remote's columnar arrays and write it into ours by rid */
private mergeCellReg(doc: DashDoc, rdoc: DashDoc, rstate: SyncStateJSON, node: string, key: string, rr: Reg): void {
const sh = nodeSheet(node)
const rid = Number(nodeTail(node))
const col = keyCol(key)
const sheet = tableOf(doc, sh)
const rsheet = tableOf(rdoc, sh)
const rAt = rsheet ? rleIndex(rsheet.rids, rid) : -1
const value = isVKey(key)
? (rAt >= 0 && rsheet ? readCell(rsheet.data[col], rAt) : rstate.stash?.[node]?.[key]?.v)
: (rsheet?.cells?.[`${col}:${rid}`] ?? rstate.stash?.[node]?.[key]?.v)
if (this.dead(node) || !sheet || !rleHas(sheet.rids, rid)) {
;(this.stash[node] ??= {})[key] = { v: clone(value), r: clone(rr) }
return
}
if (isVKey(key)) {
if (sheet.data[col]) applyPatch(doc, { op: 'setCells', sheet: sh, col, rids: [rid], v: [clone(value ?? null)] })
} else {
// One HALF of the override, taken from whichever side's register won —
// which is what keeps merge(A←B) and merge(B←A) landing in the same
// place when the two sides won opposite halves of the same cell.
const okey = `${col}:${rid}`
applyPatch(doc, {
op: 'setOverrides', sheet: sh, keys: [okey],
v: [ovMerge(sheet.cells?.[okey],
value === undefined ? null : clone(value) as CellOverride, oHalf(key))],
dropEmpty: true,
})
}
}
private mergeColumns(doc: DashDoc, sheet: TableSheet, rsheet: TableSheet | undefined, res: ApplyResult): void {
for (let i = sheet.columns.length - 1; i >= 0; i--) {
const n = colNode(sheet.id, sheet.columns[i].id)
if (!this.dead(n)) continue
this.stashNode(sheet.columns[i] as unknown as Record<string, unknown>, n)
this.killColumn(doc, sheet, sheet.columns[i].id)
res.changed = res.structure = true
}
if (!rsheet) return
const myRids = rleExpand(sheet.rids)
for (const rc of rsheet.columns) {
if (this.dead(colNode(sheet.id, rc.id))) continue
if (sheet.columns.some((c) => c.id === rc.id)) continue
sheet.columns.push(clone(rc))
const rd = rsheet.data[rc.id]
if (rd) sheet.data[rc.id] = alignColumnData(rd, rleExpand(rsheet.rids), myRids)
res.changed = res.structure = true
}
}
/**
* Reconcile two row sequences.
*
* Rows only one side knows about are adopted with their values; rows dead
* under merged liveness leave. The ORDER is a symmetric interleave (see
* mergeOrder) rather than a winner-takes-all — which is the honest limit of
* merging two sequences from state alone, since neither side kept the op log
* that produced the other's order.
*/
private mergeRows(doc: DashDoc, sheet: TableSheet, rsheet: TableSheet | undefined, res: ApplyResult): void {
const mine = rleExpand(sheet.rids)
const dropped = mine.filter((rid) => this.dead(rowNode(sheet.id, rid)))
if (dropped.length) {
for (const rid of dropped) this.stashRow(sheet, sheet.id, rid)
dropRowOverrides(doc, sheet, dropped)
applyPatch(doc, { op: 'deleteRows', sheet: sheet.id, rids: dropped })
res.changed = res.structure = true
}
if (!rsheet) return
const live = rleExpand(sheet.rids)
const theirs = rleExpand(rsheet.rids).filter((rid) => !this.dead(rowNode(sheet.id, rid)))
const order = mergeOrder(live, theirs, (rid) => this.births[rowNode(sheet.id, rid)])
// adopt rows only they have, in the merged order, one splice each
for (let i = 0; i < order.length; i++) {
const rid = order[i]
if (rleHas(sheet.rids, rid)) continue
const at = rleIndex(rsheet.rids, rid)
const vals: Record<string, unknown[]> = {}
for (const col of Object.keys(sheet.data)) {
const rd = rsheet.data[col]
vals[col] = [rd ? readCell(rd, at) : null]
}
applyPatch(doc, { op: 'insertRows', sheet: sheet.id, rids: [rid], at: [Math.min(i, rleCount(sheet.rids))], values: vals })
for (const [k, ov] of Object.entries(rsheet.cells ?? {})) {
if (Number(k.slice(k.indexOf(':') + 1)) !== rid) continue
applyPatch(doc, { op: 'setOverrides', sheet: sheet.id, keys: [k], v: [clone(ov)], dropEmpty: true })
}
res.changed = res.structure = true
}
// then settle the order itself
const now = rleExpand(sheet.rids)
if (now.length === order.length && now.every((r, i) => r === order[i])) return
permuteRows(sheet, order)
res.changed = res.structure = true
}
/** ops from our log this version vector is missing (peer catch-up) */
missingFor(log: Op[], vv: Record<string, number>): Op[] {
return log.filter((o) => o.s > (vv[o.a] ?? 0))
}
}
// ---------------------------------------------------------------------------
// helpers
// ---------------------------------------------------------------------------
/** sheet-node keys that the payload owns wholesale: structure moves through
* row/column ops, never through a property register. Mirrors store.ts's
* `STRUCTURAL` refusal set in rowcol.ts, deliberately. */
const SHEET_STRUCTURAL = ['id', 'kind', 'columns', 'data', 'rids', 'cells'] as const
const tableOf = (doc: DashDoc, id: string): TableSheet | undefined => {
const s = doc.sheets.find((x) => x.id === id)
return s && s.kind === 'table' ? s : undefined
}
/**
* Take a removed row's cell overrides with it.
*
* `rowcol.deleteRowsAt` does this in the app, in the same commit, because an
* override keyed to a rid nobody can reach is garbage that the next writer
* inherits. The CRDT has to do it too, and not merely as tidiness: a replica
* that wrote the override BEFORE the delete arrived would otherwise keep it
* while a replica that got the delete first never writes it at all, and two
* workbooks would differ by a note pinned to a row that no longer exists.
* Deterministic given liveness, and safe because a rid is never reused.
*/
/** the row-axis twin of DashSync.killColumn (see rowcol.deleteRowsAt) */
function dropRowOverrides(doc: DashDoc, sheet: TableSheet, rids: number[]): void {
if (!sheet.cells) return
const doomed = new Set(rids)
const keys = Object.keys(sheet.cells).filter((k) => doomed.has(Number(k.slice(k.indexOf(':') + 1))))
if (!keys.length) return
applyPatch(doc, { op: 'setOverrides', sheet: sheet.id, keys, v: keys.map(() => null), dropEmpty: true })
}
function writeKey(target: Record<string, unknown>, k: string, v: unknown): void {
if (v === undefined) delete target[k]
else target[k] = v
}
/** doc-level keys support dotted per-entry registers for the map fields, so two
* people adding different measures (or assets) both keep theirs. */
function writeDocKey(doc: DashDoc, k: string, v: unknown): void {
const dot = k.indexOf('.')
const field = dot > 0 ? k.slice(0, dot) : ''
if (field === 'measures' || field === 'assets' || field === 'blobs' || field === 'names') {
const map = ((doc as unknown as Record<string, Record<string, unknown>>)[field] ??= {})
const key = k.slice(dot + 1)
if (v === undefined) delete map[key]
else map[key] = clone(v)
return
}
writeKey(doc as unknown as Record<string, unknown>, k, v === undefined ? undefined : clone(v))
}
function readDocKey(doc: DashDoc, k: string): unknown {
const dot = k.indexOf('.')
const field = dot > 0 ? k.slice(0, dot) : ''
if (field === 'measures' || field === 'assets' || field === 'blobs' || field === 'names') {
return (doc as unknown as Record<string, Record<string, unknown> | undefined>)[field]?.[k.slice(dot + 1)]
}
return (doc as unknown as Record<string, unknown>)[k]
}
const remoteNode = (rdoc: DashDoc, node: string): Record<string, unknown> | undefined => {
if (node === DOC_NODE) return rdoc as unknown as Record<string, unknown>
const sheet = rdoc.sheets.find((s) => s.id === nodeSheet(node))
if (!sheet) return undefined
if (node[0] === 's') return sheet as unknown as Record<string, unknown>
if (sheet.kind !== 'table') return undefined
return sheet.columns.find((c) => c.id === nodeTail(node)) as unknown as Record<string, unknown> | undefined
}
const localNode = remoteNode
/**
* Re-align a column's encoded values from the sender's row order to ours.
*
* A column travels with the rid list it was encoded against, because the two
* replicas' row orders need not match — and reading a column at the wrong
* offsets is the silent-wrong-number failure this whole app is built to
* refuse. Rows we do not have are dropped; rows the sender lacked come out null.
*/
export function alignColumnData(data: ColumnData, from: number[], to: number[]): ColumnData {
if (data.enc === 'pack') return data // opaque archive encoding — cannot re-index
const at = new Map<number, number>()
from.forEach((rid, i) => at.set(rid, i))
if (data.enc === 'dict') {
return { enc: 'dict', dict: data.dict.slice(), idx: to.map((rid) => { const i = at.get(rid); return i === undefined ? null : (data.idx[i] ?? null) }) }
}
return { enc: 'raw', v: to.map((rid) => { const i = at.get(rid); return i === undefined ? null : (data.v[i] ?? null) }) }
}
/**
* Permute a sheet's rows into `order`.
*
* Rebuilds each column's index array rather than writing values one at a time:
* a dict column keeps its dictionary (no re-interning, no dictionary growth)
* and a raw column is one map. `pack` columns are opaque and are left ALONE —
* store.ts refuses to write them for the same reason, and silently re-indexing
* an archive column would misalign every value in it.
*/
/**
* Settle a sheet's rid watermark to a value every replica agrees on.
*
* `nextRid` is DOCUMENT data (store.ts raises it on every insert and delete so
* a rid is never minted twice), and a plain monotonic counter does not
* converge: two replicas that each did a different number of structural edits
* hold different numbers, and the documents differ forever. Measured before
* this existed: seed 12 diverged on `nextRid` 4002 against 4001 and on nothing
* else.
*
* A monotonic counter's join is MAX, and this engine already knows every rid
* that has ever existed for a sheet — `births` keeps a register for each row
* node whether or not it is still alive. So the converged watermark is one past
* the largest of them, which both replicas compute identically once their
* states agree, and which can never go below a rid that existed.
*/
function settleWatermark(sheet: TableSheet, births: Record<string, Reg>): void {
const prefix = rowNode(sheet.id, 0).slice(0, -1)
let hi = 0
for (const [start, count] of sheet.rids) hi = Math.max(hi, start + count - 1)
for (const k of Object.keys(births)) {
if (!k.startsWith(prefix)) continue
const rid = Number(k.slice(prefix.length))
if (Number.isFinite(rid)) hi = Math.max(hi, rid)
}
sheet.nextRid = hi + 1
}
function permuteRows(sheet: TableSheet, order: number[]): void {
const from = rleExpand(sheet.rids)
const at = new Map<number, number>()
from.forEach((rid, i) => at.set(rid, i))
for (const [col, d] of Object.entries(sheet.data)) {
if (d.enc === 'raw') sheet.data[col] = { enc: 'raw', v: order.map((rid) => { const i = at.get(rid); return i === undefined ? null : (d.v[i] ?? null) }) }
else if (d.enc === 'dict') sheet.data[col] = { enc: 'dict', dict: d.dict, idx: order.map((rid) => { const i = at.get(rid); return i === undefined ? null : (d.idx[i] ?? null) }) }
}
sheet.rids = rleCompress(order)
}
/**
* Symmetric two-sequence interleave.
*
* The rule may never ask which side is "local" — merge(A,B) and merge(B,A)
* have to produce the same list, or two forks that exchange snapshots settle on
* different row orders and never converge. So at every step the choice is made
* from the elements themselves: an element the other list does not contain goes
* first, and a genuine tie breaks on (birth stamp, rid), which both sides agree
* on.
*/
export function mergeOrder(a: number[], b: number[], birthOf: (rid: number) => Reg | undefined): number[] {
const inB = new Set(b)
const inA = new Set(a)
const out: number[] = []
const taken = new Set<number>()
let i = 0
let j = 0
const rank = (rid: number): string => {
const r = birthOf(rid)
return r ? `1${String(r[0]).padStart(12, '0')}${r[1]}${rid}` : `0${String(rid).padStart(12, '0')}`
}
const take = (rid: number) => { if (!taken.has(rid)) { taken.add(rid); out.push(rid) } }
while (i < a.length || j < b.length) {
while (i < a.length && taken.has(a[i])) i++
while (j < b.length && taken.has(b[j])) j++
if (i >= a.length) { if (j < b.length) take(b[j++]) ; continue }
if (j >= b.length) { take(a[i++]); continue }
const x = a[i]
const y = b[j]
if (x === y) { take(x); i++; j++; continue }
const xShared = inB.has(x)
const yShared = inA.has(y)
if (xShared && !yShared) { take(y); j++; continue }
if (!xShared && yShared) { take(x); i++; continue }
// both exclusive, or both shared but out of order: decide from the rows
if (rank(x) <= rank(y)) { take(x); i++ } else { take(y); j++ }
}
return out
}
/** indices of a longest strictly-increasing subsequence */
function longestIncreasing(keys: string[]): number[] {
const tails: number[] = []
const prev = new Array<number>(keys.length).fill(-1)
for (let i = 0; i < keys.length; i++) {
let lo = 0
let hi = tails.length
while (lo < hi) {
const mid = (lo + hi) >> 1
if (keys[tails[mid]] < keys[i]) lo = mid + 1
else hi = mid
}
if (lo > 0) prev[i] = tails[lo - 1]
tails[lo] = i
}
const out: number[] = []
let k = tails.length ? tails[tails.length - 1] : -1
while (k >= 0) { out.push(k); k = prev[k] }
return out.reverse()
}
/**
* Is this patch safe to commit into a LIVE session?
*
* The asymmetry this closes is easy to miss and impossible to see afterwards.
* A locally committed patch is applied by the store unconditionally — it has no
* idea what a peer deleted — while the very same change, arriving as an op, is
* gated by liveness on every other replica. So an edit naming a row or column
* that is gone lands HERE and nowhere else, and the workbooks differ by a value
* only one person can see. `applyPatch` makes it worse for cells specifically:
* a `setCells` naming an unknown rid is silently skipped rather than refused,
* so nothing surfaces at the call site either.
*
* The rule is the honest one: you cannot edit what is not there. Undo is where
* this actually bites (its inverses were built against a document state that a
* collaborator has since changed), which is why the session filters rather than
* throws — a refused inverse is a lost undo step, and a divergent workbook is
* worse.
*/
export function committable(doc: DashDoc, p: Patch): boolean {
const table = (id: string): TableSheet | undefined => tableOf(doc, id)
const ridOf = (k: string) => Number(k.slice(k.indexOf(':') + 1))
const colOf = (k: string) => k.slice(0, k.indexOf(':'))
switch (p.op) {
case 'setCells': {
const s = table(p.sheet)
return !!s && !!s.data[p.col] && p.rids.every((r) => rleHas(s.rids, r))
}
case 'setOverrides': {
const s = table(p.sheet)
return !!s && p.keys.every((k) =>
rleHas(s.rids, ridOf(k)) && s.columns.some((c) => c.id === colOf(k)))
}
case 'insertRows': {
const s = table(p.sheet)
if (!s || !p.rids.every((r) => !rleHas(s.rids, r))) return false
// Every position must be reachable AT THE MOMENT it is spliced.
// store.ts's insertRows splices `rids` and the column arrays at `at`
// (which Array.splice clamps) but then writes the value at the RAW
// index, so an `at` past the end leaves a hole and a column one entry
// longer than the sheet has rows — after which every cell below the gap
// reads the next row's number. It is reachable exactly here: undo of a
// row delete carries the positions the rows had, and a collaborator may
// have removed rows since. Refusing costs one undo step.
let n = rleCount(s.rids)
for (const at of (p.at ?? []).slice().sort((x, y) => x - y)) {
if (at > n) return false
n++
}
return true
}
case 'deleteRows': return !!table(p.sheet)
// The spreadsheet kind, and here the rule bites harder than elsewhere:
// `applyPatch`'s `canvas()` THROWS on a sheet that is gone (or that is a
// dataset), so an undo replaying a write into a sheet a collaborator
// deleted would not merely diverge, it would take the commit down. Reached
// through the same door as every other refusal: you cannot edit what is
// not there.
case 'setCanvasCells':
case 'setCanvasSizes': {
const s = doc.sheets.find((x) => x.id === p.sheet)
return !!s && s.kind === 'canvas'
}
case 'addColumn': {
const s = table(p.sheet)
if (!s || s.columns.some((c) => c.id === p.column.id)) return false
// A column's values are addressed by POSITION, so an array that is not
// exactly as long as the sheet has rows shifts every cell below the gap
// — silently, and identically on every replica, which is worse than a
// crash. It happens for real: `removeColumn`'s inverse carries the data
// snapshot taken at removal, and rows may have come or gone since, so an
// undo can restore a column that no longer fits the sheet it is going
// back into. Refusing costs one undo step; accepting costs the numbers.
if (!p.data) return true
const len = p.data.enc === 'raw' ? p.data.v.length : p.data.enc === 'dict' ? p.data.idx.length : -1
return len < 0 || len === rleCount(s.rids)
}
case 'removeColumn':
case 'setColumn': return !!table(p.sheet)?.columns.some((c) => c.id === p.col)
case 'reorderColumns': {
const s = table(p.sheet)
return !!s && p.order.length === s.columns.length && p.order.every((id) => s.columns.some((c) => c.id === id))
}
// ANY KIND, matching `applyPatch`. This asked `table(p.sheet)` — the same
// narrowing store.ts had — so under a live session a rename of a
// spreadsheet or a pivot was FILTERED OUT of the commit as uncommittable
// and reported as `patch-refused`: the edit vanished locally as well as
// remotely, which is worse than the throw it was mirroring. The question
// this gate asks is "is the target still there?", and for a sheet-level op
// the target is a sheet.
case 'setSheetProps': return doc.sheets.some((s) => s.id === p.sheet)
// `applyPatch` REFUSES a `reorderSheets` that is not a permutation of the
// current list, and it is right to — an id left out would delete a sheet.
// But an undo replaying an order minted before a collaborator added or
// removed a sheet is exactly that, and a throw out of `commit` is worse
// than a lost undo step. Refused here, as `reorderColumns` already is.
case 'reorderSheets':
return p.order.length === doc.sheets.length &&
p.order.every((id) => doc.sheets.some((s) => s.id === id))
default: return true
}
}
/** Exposed for the convergence rig, as store.ts does — not an app surface. */
export const _internals = { rleExpand, rleCompress, rleIndex, rleAt, permuteRows, longestIncreasing }