Skip to content

armgit / bento

Public Imported from GitHub
0

Bento, the office suite that fits in a file

19.4 KB
Raw Blame
#!/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)