Bento, the office suite that fits in a file
TypeScript mit-licenseofficeoffice-365office-suiteoffice-toolsoffice365open-sourcepowerpointself-hostedsingle-page-appslidesslideshareslideshowslideshow-galleryslideshow-makerslideshows
#!/usr/bin/env node
// SPDX-License-Identifier: MIT
// Copyright (c) 2026 The Bento authors
// bento/spaces under the shared CRDT engine — convergence, and the format's
// own invariants after convergence.
//
// node scripts/test-sync-spaces.ts
// SEEDS=300 STEPS=80 ACTORS=4 node scripts/test-sync-spaces.ts
//
// TWO DIFFERENT QUESTIONS, and only the first is what a CRDT rig usually asks.
//
// 1. DO REPLICAS CONVERGE? Standard, and the engine's own property.
//
// 2. IS WHAT THEY CONVERGE ON A LEGAL bento/spaces DOCUMENT? This is the one
// that matters here, and it has no slides equivalent. `page.blocks` is
// FLAT AND IN PRE-ORDER — the format's guarantee is "a child always
// follows its parent, so one forward pass rebuilds the tree" — while the
// engine stores order as fractional position keys and `parent` as an
// ordinary last-writer-wins register. Those are two independent merge
// domains describing one visual tree. Two perfectly legal concurrent edits
// (you indent a block, I move one) can therefore converge on a state every
// replica agrees about and no renderer can draw correctly.
//
// If that is real, it is a FORMAT-LEVEL decision and it has to be made
// before any spaces file carries collaboration state — which is why this
// rig reports it as data rather than asserting a verdict it cannot know.
//
// The engine is the kernel's, bound to ('pages','blocks'). Nothing here is
// spaces app code: this is the shape binding and its evidence.
import { SyncEngine } from '../kernel/src/sync/crdt.ts'
import { mulberry32, baseDoc, randomMutation, type Doc } from './lib/sync-fixtures-spaces.ts'
import { effectiveParents, descendantsOf } from '../spaces/src/model.ts'
// The binding lives with the APP (spaces/src/sync/crdt.ts), not here. Two
// definitions of a frozen format constant is precisely how a fork starts: the
// shape strings are minted into every persisted SyncStateJSON and every relay
// frame, so a rig that carries its own copy can go green while the app ships
// something else. Re-exported so existing importers are unaffected.
// (`export … from` re-exports without binding the name locally, and this rig
// uses it below — so it is imported and re-exported.)
import { SPACES_SHAPE } from '../spaces/src/sync/crdt.ts'
import { SPACES_FIELDS } from '../spaces/src/docclass.ts'
export { SPACES_SHAPE }
class SpacesSync extends SyncEngine {
constructor(actor: string) { super(actor, SPACES_SHAPE) }
}
const SEEDS = parseInt(process.env.SEEDS ?? '120', 10)
const STEPS = parseInt(process.env.STEPS ?? '60', 10)
const ACTORS = parseInt(process.env.ACTORS ?? '3', 10)
let failures = 0
let checks = 0
function ok(cond: boolean, msg: string) {
checks++
if (!cond) { failures++; console.log(` FAIL ${msg}`) }
}
const clone = <T>(v: T): T => JSON.parse(JSON.stringify(v))
class Replica {
doc: Doc
state: SpacesSync
shadow: string
constructor(actor: string, doc: Doc) {
this.doc = doc
this.state = new SpacesSync(actor)
this.state.adopt(this.doc as never)
this.shadow = JSON.stringify(this.doc)
}
mutate(fn: (d: Doc) => void) {
fn(this.doc)
return this.flush()
}
flush() {
const ops = this.state.diff(JSON.parse(this.shadow), this.doc as never, { text: true })
this.shadow = JSON.stringify(this.doc)
return ops
}
receive(ops: unknown[]) {
this.state.apply(this.doc as never, ops as never)
this.shadow = JSON.stringify(this.doc)
}
}
// ---------------------------------------------------------------------------
// the format's invariants, checked on a MERGED document
// ---------------------------------------------------------------------------
interface Violations {
preorderBlocks: number // a block whose parent appears later, or not at all
danglingBlock: number // parent names a block not in this page
preorderPages: number
danglingPage: number
pageCycle: number
dupBlockId: number // the same block id on two pages
}
function inspect(doc: Doc): Violations {
const v: Violations = { preorderBlocks: 0, danglingBlock: 0, preorderPages: 0, danglingPage: 0, pageCycle: 0, dupBlockId: 0 }
const seenBlock = new Map<string, string>()
for (const p of doc.pages) {
const at = new Map<string, number>()
p.blocks.forEach((b, i) => at.set(b.id, i))
p.blocks.forEach((b, i) => {
if (seenBlock.has(b.id) && seenBlock.get(b.id) !== p.id) v.dupBlockId++
seenBlock.set(b.id, p.id)
if (b.parent === undefined) return
const j = at.get(String(b.parent))
if (j === undefined) v.danglingBlock++
else if (j >= i) v.preorderBlocks++ // parent at or after the child
})
}
const pageAt = new Map<string, number>()
doc.pages.forEach((p, i) => pageAt.set(p.id, i))
doc.pages.forEach((p, i) => {
if (p.parent === undefined) return
const j = pageAt.get(String(p.parent))
if (j === undefined) v.danglingPage++
else if (j >= i) v.preorderPages++
})
// page cycles: walk up from every page with a hop cap
for (const p of doc.pages) {
const seen = new Set<string>()
let up: string | undefined = p.id
while (up && !seen.has(up)) {
seen.add(up)
up = doc.pages.find((q) => q.id === up)?.parent as string | undefined
if (up && seen.has(up)) { v.pageCycle++; break }
}
}
return v
}
const total = (v: Violations) => Object.values(v).reduce((a, b) => a + b, 0)
// ---------------------------------------------------------------------------
// the run
// ---------------------------------------------------------------------------
console.log('bento/spaces under the shared CRDT engine\n')
const worst: Violations = { preorderBlocks: 0, danglingBlock: 0, preorderPages: 0, danglingPage: 0, pageCycle: 0, dupBlockId: 0 }
let seedsWithViolations = 0
let diverged = 0
let opsTotal = 0
let soloBroken = 0
let measured = 0
let ruleBroken = 0
let ruleChecked = 0
for (let seed = 1; seed <= SEEDS; seed++) {
const rnd = mulberry32(seed * 7919)
const base = baseDoc()
const reps = Array.from({ length: ACTORS }, (_, i) => new Replica(`a${i}`, clone(base)))
// a lone replica running actor 0's edits and receiving nothing
const solo = new Replica('solo', clone(base))
const queues = new Map<string, unknown[][]>()
for (let f = 0; f < ACTORS; f++) for (let t = 0; t < ACTORS; t++) if (f !== t) queues.set(`${f}>${t}`, [])
for (let s = 0; s < STEPS; s++) {
if (rnd() < 0.6) {
const a = Math.floor(rnd() * ACTORS)
const mseed = (seed * 1_000_003 + s * 7919) >>> 0
if (a === 0) solo.mutate(randomMutation(solo.doc, mulberry32(mseed)))
const ops = reps[a].mutate(randomMutation(reps[a].doc, mulberry32(mseed)))
opsTotal += ops.length
if (ops.length) for (let t = 0; t < ACTORS; t++) if (t !== a) queues.get(`${a}>${t}`)!.push(ops)
} else {
const keys = [...queues.keys()].filter((k) => queues.get(k)!.length)
if (!keys.length) continue
const k = keys[Math.floor(rnd() * keys.length)]
const to = parseInt(k.split('>')[1], 10)
reps[to].receive(queues.get(k)!.shift()!)
}
}
// drain everything
let guard = 0
for (;;) {
const k = [...queues.keys()].find((x) => queues.get(x)!.length)
if (!k || guard++ > 10000) break
reps[parseInt(k.split('>')[1], 10)].receive(queues.get(k)!.shift()!)
}
const first = JSON.stringify(reps[0].doc)
for (let i = 1; i < ACTORS; i++) {
if (JSON.stringify(reps[i].doc) !== first) {
diverged++
if (diverged === 1) console.log(` FAIL seed ${seed}: replicas a0 and a${i} disagree`)
break
}
}
// THE CONTROL, and the rig is worthless without it. If the generator itself
// produced illegal documents, every violation below would be its fault
// rather than the merge's. So each replica is inspected BEFORE it receives
// anything (soloDoc, driven by the same edits), and that must be spotless.
// A seed whose SOLO document is already illegal proves nothing about
// merging, so it is excluded from the statistic rather than counted. The
// measurement is then over seeds where the generator is provably clean —
// which is a stronger basis than "every generator bug we happened to find
// has been fixed".
if (total(inspect(solo.doc)) > 0) { soloBroken++; continue }
measured++
// THE TREE RULE, on a document the merge actually produced. The violations
// below are real and expected; what must never happen is the RULE failing on
// one of them — a parent that is not strictly earlier, a walk that cycles, or
// a subtree that contains its own root (which is what makes a delete take
// blocks nobody selected).
for (const page of reps[0].doc.pages) {
const at = new Map<string, number>()
page.blocks.forEach((b, i) => at.set(b.id, i))
const eff = effectiveParents(page as never)
for (const b of page.blocks) {
const par = eff.get(b.id)
if (par !== undefined && (at.get(par) ?? 1e9) >= (at.get(b.id) ?? -1)) ruleBroken++
if (par === b.id) ruleBroken++
const walked = new Set<string>()
for (let up = par; up; up = eff.get(up)) {
if (walked.has(up)) { ruleBroken++; break }
walked.add(up)
}
if (descendantsOf(page as never, b.id).has(b.id)) ruleBroken++
ruleChecked++
}
}
const v = inspect(reps[0].doc)
if (total(v) > 0) {
seedsWithViolations++
for (const k of Object.keys(worst) as Array<keyof Violations>) worst[k] = Math.max(worst[k], v[k])
}
}
ok(diverged === 0, `all replicas converge (${diverged} seed(s) diverged)`)
ok(ruleBroken === 0,
`the effective-parent rule holds on every merged document ` +
`(${ruleBroken} failure(s) across ${ruleChecked} blocks) — no cycle, no late parent, ` +
'no subtree containing its own root')
// The control is REPORTED, not asserted: a seed the generator got wrong is
// excluded from the measurement, so it cannot contaminate the finding. What
// would invalidate the rig is excluding most of them, so that IS asserted.
console.log(` ok control: ${measured}/${SEEDS} seeds had a provably legal solo document ` +
`(${soloBroken} excluded — the generator, not the merge)`)
ok(measured > SEEDS * 0.9,
`the control excluded too much to measure anything (${measured}/${SEEDS} usable)`)
console.log(` ok convergence: ${SEEDS} seeds × ${STEPS} steps × ${ACTORS} actors, ${opsTotal} ops`)
// ---- the format report ------------------------------------------------------
console.log('')
console.log(' bento/spaces format invariants on the MERGED document:')
console.log(` seeds producing at least one violation: ${seedsWithViolations}/${measured} ` +
`(${(seedsWithViolations / Math.max(1, measured) * 100).toFixed(1)}%)`)
for (const [k, n] of Object.entries(worst)) {
console.log(` ${k.padEnd(16)} worst-case in one document: ${n}`)
}
console.log('')
// ---------------------------------------------------------------------------
// WHAT IS ASSERTED, AND WHY IT IS ONLY CONVERGENCE
//
// Convergence is the ENGINE's property, and it holds. Everything in the table
// above is a property of the FORMAT meeting the engine, and every one of them
// is an open design question this rig exists to have discovered rather than to
// have pre-judged:
//
// · pre-order vs `parent` — two independent merge domains for one visual
// tree. The fix is a rule (derive the tree at render time and tolerate any
// array order, or repair after apply), and a repair that COMMITS would mint
// ord ops and can ping-pong between replicas forever.
// · page cycles — `Store.tree()` recurses from the root with no visited set,
// so a cycle makes pages vanish from the sidebar AND from the markdown
// export, while still being in the file.
// · duplicate block ids — the engine duplicates a node on concurrent moves to
// two different parents, BY DESIGN (docs/collab-design.md). In slides that
// is the morph idiom and it is correct. In spaces, block ids are unique
// document-wide (parseDoc's `seen` set spans pages and blocks),
// `buildIndex` keys blocks by bare id, and `#p/<page>/<block>` anchors
// assume it — so the same behaviour is a defect.
//
// Failing the build on any of those would be asserting an answer nobody has
// chosen. STRICT=1 turns them into assertions — flip it in CI the moment the
// decisions land, and this rig becomes their enforcement.
// ---------------------------------------------------------------------------
// ---------------------------------------------------------------------------
// page.design is a page property REGISTER, like width or cover: it travels,
// concurrent choices converge on one, and "Same as parent" (the key DELETED)
// travels as a deletion — never as a stored empty value.
// ---------------------------------------------------------------------------
{
const pd = (d: Doc, id: string) => (d.pages.find((p) => p.id === id) as { design?: unknown } | undefined)?.design
const a = new Replica('pd-a', baseDoc())
const b = new Replica('pd-b', clone(a.doc))
const setOn = (r: Replica, v: string | null) => r.mutate((d) => {
const p = d.pages.find((x) => x.id === 'p2') as { design?: unknown }
if (v === null) delete p.design
else p.design = v
})
b.receive(setOn(a, 'ledger'))
ok(pd(b.doc, 'p2') === 'ledger', 'a page design chosen on one replica arrives on the other')
const opsA = setOn(a, 'studio')
const opsB = setOn(b, 'riso')
a.receive(opsB)
b.receive(opsA)
ok(pd(a.doc, 'p2') === pd(b.doc, 'p2') && ['studio', 'riso'].includes(String(pd(a.doc, 'p2'))),
`two concurrent page-design choices converge on one of them (${String(pd(a.doc, 'p2'))})`)
b.receive(setOn(a, null))
ok(!Object.hasOwn(b.doc.pages.find((p) => p.id === 'p2')!, 'design') && pd(a.doc, 'p2') === undefined,
'"Same as parent" (the key deleted) arrives as a deletion — no key is left behind')
ok(JSON.stringify(a.doc) === JSON.stringify(b.doc), 'both replicas end byte-identical')
}
// ---------------------------------------------------------------------------
// DOC-LEVEL KEYS GO BY ALLOWLIST (kernel #683, bound in spaces/src/sync/crdt.ts).
//
// SPACES_SHAPE carries the real field map, so a replica EMITS only the doc keys
// docclass.ts classes 'content'. Every non-content key spaces has today is also
// on the kernel's skipDoc floor, so the half that is NEW here is the UNKNOWN key:
// a field a newer build added, opened in this build, is never echoed to the
// room — and one that ARRIVES from such a peer is kept in this file but, again,
// never re-emitted. Not emitting a key is not deleting it.
//
// Mutation: drop SPACES_FIELDS from the shape() call → the unknown-key rows go
// red (the shipped denylist emits anything it does not explicitly skip).
// ---------------------------------------------------------------------------
{
type R = Record<string, unknown>
const docSets = (ops: unknown[]): string[] => (ops as R[])
.filter((o) => o.op === 'set' && o.el === undefined && o.sl === undefined)
.map((o) => String(o.k).split('.')[0])
const NON_CONTENT = Object.keys(SPACES_FIELDS).filter((k) => (SPACES_FIELDS as R)[k] !== 'content')
ok(SPACES_SHAPE.classes === SPACES_FIELDS, 'the spaces sync shape is bound to the real field map (docclass.ts)')
// SENDER — every field at once, so a row names which key leaked
{
const a = new SpacesSync('al-a')
const d = clone(baseDoc()) as unknown as R
a.adopt(d as never)
const before = clone(d)
d.title = 'renamed'
d.footnotes = { n1: 'a note' }
d.design = 'ledger'
d.periods = { s1: { label: 'Sprint 1', from: '2026-10-01', to: '2026-10-14', base: {} } }
for (const k of NON_CONTENT) d[k] = k === 'collab' ? { room: 'wX', key: 'LEAK' } : `changed-${k}`
d.futureField = 'a field a newer build added'
const sent = docSets(a.diff(before as never, d as never, { text: true }) as never)
ok(['title', 'footnotes', 'design', 'periods'].every((k) => sent.includes(k)),
`content keys are emitted, the per-key periods map included (${sent.join(', ')})`)
const leaked = NON_CONTENT.filter((k) => sent.includes(k))
ok(leaked.length === 0, `no non-content key is emitted (${NON_CONTENT.join(', ')}${leaked.length ? ` — LEAKED ${leaked.join(', ')}` : ''})`)
ok(!sent.includes('futureField'), 'an UNKNOWN key (a newer build\'s field opened here) is never emitted')
const out = a.outboundDoc(clone(d) as never) as R
ok(out.futureField === undefined && NON_CONTENT.every((k) => out[k] === undefined || k === 'collab' && out[k] === undefined),
'the snapshot doc a replica sends carries neither the unknown key nor any non-content key')
}
// RECEIVER — an older, unbound build emits whatever it does not skip
{
const OLD = new SyncEngine('al-old', { ...SPACES_SHAPE, classes: undefined })
const od = clone(baseDoc()) as unknown as R
OLD.adopt(od as never)
const a = new SpacesSync('al-recv')
const ad = clone(od)
a.adopt(ad as never)
const before = clone(od)
od.futureField = 'from a newer build'
od.title = 'old peer renamed it'
a.apply(ad as never, OLD.diff(before as never, od as never, { text: true }) as never)
ok(ad.futureField === 'from a newer build' && ad.title === 'old peer renamed it',
'an unknown key from a peer is APPLIED here (kept in this file), beside the content edit')
const regs = Object.keys((a.toJSON() as { regs: R }).regs)
ok(!regs.some((k) => k.endsWith(' futureField')) && regs.some((k) => k.endsWith(' title')),
'…and never echoed: the stamped state carries the title register, not the unknown one')
// this replica's next edits: delivered to the old peer, in order (an
// undelivered op would leave a sequence gap the engine rightly holds back)
const step = (change: R): unknown[] => {
const prev = clone(ad)
Object.assign(ad, change)
const ops = a.diff(prev as never, ad as never, { text: true }) as unknown[]
OLD.apply(od as never, ops as never)
return ops
}
ok(!docSets(step({ title: 'again' })).includes('futureField'), '…nor does this replica\'s next diff re-send it')
step({ design: 'riso' })
ok(od.design === 'riso' && od.title === 'again', 'a bound and an unbound replica still converge on content (mixed-version room)')
}
}
const STRICT = process.env.STRICT === '1'
if (STRICT) {
ok(worst.dupBlockId === 0, `no merge produced the same block id on two pages (worst ${worst.dupBlockId})`)
ok(worst.preorderBlocks === 0, `no merge broke block pre-order (worst ${worst.preorderBlocks})`)
ok(worst.danglingBlock === 0, `no merge left a dangling block parent (worst ${worst.danglingBlock})`)
ok(worst.preorderPages === 0, `no merge broke page pre-order (worst ${worst.preorderPages})`)
ok(worst.danglingPage === 0, `no merge left a dangling page parent (worst ${worst.danglingPage})`)
ok(worst.pageCycle === 0, `no merge produced a page cycle (worst ${worst.pageCycle})`)
} else if (seedsWithViolations) {
console.log(' OPEN — merged documents violate the flat pre-order invariant, and')
console.log(' that is the expected consequence of `parent` being an ordinary')
console.log(' register while order is a position key. Two legal concurrent edits')
console.log(' meet, every replica agrees, and no forward pass can rebuild the tree.')
console.log(' These are FORMAT decisions and they must be settled before a spaces')
console.log(' file carries collaboration state. Re-run with STRICT=1 to hold the')
console.log(' line once they are. See docs/DECISIONS.md.')
console.log('')
}
console.log(`${checks - failures}/${checks} assertions passed`)
if (failures) process.exit(1)