Skip to content

armgit / bento

Public Imported from GitHub
0

Bento, the office suite that fits in a file

74.9 KB
Raw Blame
// SPDX-License-Identifier: MIT
// Copyright (c) 2026 The Bento authors
// Per-cell formulas: `=B4*1.2` in one cell, evaluated in dependency order.
//
// WHY THIS EXISTS WHEN COLUMN FORMULAS ALREADY DO. A column expression is the
// better tool and stays the default — it names columns by identity, so it
// survives every structural edit (formula.ts's header makes that case, and a1.ts
// explains the price of admitting positions back). But a spreadsheet that
// cannot put a number in one cell is not a spreadsheet. A total under a block,
// a fudge factor, an invoice line: these are single cells, and the person
// typing `=B4*1.2` is not going to be argued out of it.
//
// THE WHOLE MODULE IS A BRIDGE, and deliberately owns no engine of its own:
//
//   a1.ts       decides what is a reference and where it points
//   formula.ts  parses and evaluates the expression, and owns the error values
//   here        binds one to the other, and orders the cells
//
// The binding trick is that formula.ts's `ref` node resolves a NAME against
// `ctx.cols`. So a reference does not need parser support at all: rewrite `B4`
// to a generated name, bind that name to a one-element vector holding B4's
// value, and evaluate over `n = 1`. A RANGE binds the same way to a longer
// vector, which is why `SUM(A1:A5)` works without `:` ever becoming an operator
// — `SUM` already aggregates a vector.
//
// Generated names are `_a1_<i>`, which formula.ts's lexer reads as one
// identifier and a1.ts's scanner will not mistake for a reference on a later
// pass (it starts with `_`, and a reference must start with a letter). A column
// genuinely called `_a1_0` would collide; it also cannot be typed as a column
// name in the UI, and `[_a1_0]` still reaches it.
//
// ORDER IS THE CORRECTNESS PROBLEM, not evaluation. `=B1+1` in A1 and `=A1*2`
// in C1 have to compute in that order or C1 reads a stale value — and unlike a
// stale value in a cache, this one is written into the document and looks
// authoritative. Kahn again (formula.ts does it over columns; this does it over
// cells), and anything still in the graph when the queue drains is in a cycle
// and gets `#CYCLE!`. Never a plausible number: a cycle resolved by "whatever we
// had last time" is the failure mode where a model quietly reports a different
// answer on every recalculation and nobody can tell which one was right.
//
// THE GRAPH SPANS SHEETS (v0.3). `Sheet1!A1` is a reference like any other, so
// the ordering problem and the cycle problem are both WORKBOOK-wide: A1 on one
// sheet feeding B1 on another has to settle first, and a circle drawn through
// three sheets is exactly as circular as one drawn in a single cell. So
// `recalcWorkbook` is the real entry point and `recalcCells` is the one-sheet
// case of it. A reference to a sheet that is NOT THERE is `#REF!` for the whole
// formula — never a blank, which would read as an empty cell somebody had not
// filled in yet, and never a zero.
//
// SPARSE IS THE POINT OF THE SPREADSHEET KIND, so a range is never expanded
// over a rectangle the sheet does not occupy. `SUM(A1:A100000)` on a sheet with
// three filled cells binds three cells, because the source clips the rectangle
// to what it actually holds before anything is allocated (`CellSource.clipRange`,
// and `canvasCellSource` implements it off the sparse map's own index). The
// head of a range is NEVER moved, only its tail: two ranges of the same shape
// must stay index-aligned or `SUMIF(A1:A100, ">5", B1:B100)` pairs the wrong
// rows together, and that is a wrong number that looks like a right one.

import {
  evaluate, isErr, recalc, spillError, syntaxProblem, vecShape, FormulaError,
  type Cell, type Shaped, type SyntaxProblem, type Vec,
} from './formula.ts'
import {
  expandRange, formatRef, isNameLike, mapNames, mapRefs, rewriteFormulaRefs,
  shiftRefsForInsert, parseRef, sheetQualifiers, RANGE_CELL_MAX, REF_ERR,
  type CellRef, type RangeRef, type ShiftScope,
} from './a1.ts'
import { readCell } from './store.ts'
import type { CanvasCell, CanvasSheet, DefinedName, Sheet, TableSheet } from './model.ts'

/** A position, plus the sheet it is on when the reference named one. */
export type ScopedRef = CellRef & { sheet?: string }

/**
 * The sheet as a plain grid of positions, so this module never has to know
 * about columns, rids, dictionary encoding or overrides. Whoever calls it owns
 * that translation — and the rig can hand over a literal array.
 *
 * `rows`/`cols` are the sheet's EXTENT: a position outside them reads blank,
 * which is what `A50` on a ten-row sheet has always meant here.
 */
export interface CellSource {
  rows: number
  cols: number
  /** The formula source at a position (with or without its leading `=`), if it has one. */
  formulaAt(row: number, col: number): string | undefined
  /** The STORED value at a position — never a formula's result. */
  valueAt(row: number, col: number): Cell
  /**
   * OPTIONAL. Every position that holds a formula.
   *
   * Without it the recalculation walks `rows × cols`, which is right for a
   * dataset and ruinous for a sparse sheet: two cells at A1 and Z10000 would
   * cost 260,000 `formulaAt` calls to find. A sparse source knows its own
   * formulas and hands them over.
   */
  formulaCells?(): Iterable<{ row: number; col: number; src: string }>
  /**
   * OPTIONAL. Trim a rectangle to the part of it this sheet occupies, or `null`
   * when it occupies none of it.
   *
   * ONLY THE TAIL MAY MOVE. The first cell of the returned rectangle must be
   * the first cell of the one asked for, because a bound range is a vector and
   * two vectors from two ranges are paired BY INDEX.
   */
  clipRange?(range: RangeRef): RangeRef | null
  /**
   * OPTIONAL. Set when this sheet exists but its cells cannot be addressed —
   * a pivot's numbers are derived from a spec and live nowhere a position can
   * name. Every read returns this as `#N/A`, because the honest answer is "not
   * available", and a blank would say the cell is empty when it plainly is not.
   */
  unavailable?: string
  /**
   * OPTIONAL. May an array result SPILL across this sheet?
   *
   * True for the SPREADSHEET kind and nothing else — see the SPILL block below
   * for the argument, which is docs/dash-sheet-kinds.md's own: a dataset is
   * typed per COLUMN and is exactly as long as the rows it has, so there is
   * nowhere for a rectangle of arbitrary shape to land, and the columnar answer
   * to the same need — one expression down a whole column — already exists.
   */
  spill?: boolean
}

/**
 * One sheet of a workbook, under the name references use to reach it.
 *
 * `vectors` is a FUNCTION because building it materialises every column of a
 * dataset sheet, and a workbook where nothing references a sheet must not pay
 * for it. It is called at most once per recalculation, and only for a sheet
 * that actually evaluates something.
 */
export interface SheetSource {
  /**
   * What the result is keyed by — the sheet's id, which the document guarantees
   * is unique. Defaults to the name, which it does NOT: renaming a tab to an
   * existing name is allowed (tabs.ts refuses only an EMPTY name), and two
   * sheets called "Sales" must still both compute.
   */
  id?: string
  name: string
  source: CellSource
  /** Column names visible to a formula ON this sheet — `SUM(amount)` in a cell. */
  vectors?(): Map<string, Vec>
  /** The document's defined names as this sheet sees them (columns shadow). */
  names?: NameScope
  /**
   * OPTIONAL. Which KIND of sheet this is, and therefore what the `1` of `A1`
   * counts on it. See the ROW BASE block below — a reference that crosses from
   * one kind to the other is the one place the two answers meet.
   */
  kind?: RowBase
  /**
   * OPTIONAL. This sheet is being computed ON ITS OWN, not as part of a
   * document — `recalcCells`, and a promotion previewing a detached range.
   *
   * A one-sheet list is indistinguishable from a one-sheet workbook, so without
   * this the failed qualifier says "there is no sheet called Jan in this
   * workbook" about a sheet that is sitting in the tab strip of the workbook
   * the caller declined to pass. See `ERR_SHEET`.
   */
  detached?: boolean
}

// --- what the `1` of `A1` counts --------------------------------------------
//
// THE TRAP. `Contacts!D2` on a DATASET is the second row of the DATA. `D2` in
// the spreadsheet COPY of that same dataset is the second row INCLUDING the
// header, which is the first row of the data. Both are internally consistent,
// and side by side on one screen they are off by one — a wrong number with no
// symptom, which is the failure this codebase names everywhere else.
//
// WHAT IS TRUE, and it is one rule rather than two:
//
//   AN A1 ROW NUMBER IS THE ROW NUMBER THE ADDRESSED SHEET PAINTS IN ITS OWN
//   GUTTER.
//
// That rule is already satisfied by both kinds and is the only one a reader can
// CHECK — look at the sheet, read the number beside the row. On a dataset the
// gutter counts data rows, because a dataset has exactly the rows it has and
// its header is chrome rather than a row (docs/dash-excel-gap.md finding 14
// files that under DELIBERATE DIFFERENCE). On a spreadsheet the gutter counts
// every row, because a spreadsheet has no headers — only cells, one of which
// happens to hold a word.
//
// THE ALTERNATIVE WAS REJECTED. Making a dataset's A1 count the header — which
// is what Excel does, and would make the two kinds agree — puts the formula's
// row numbers out of step with the row numbers printed down the side of the
// very same sheet. That is a worse mismatch: the cross-kind one needs two
// sheets to be seen, this one needs none. It would also silently change what
// every `Pipeline!A2` in every saved file already means.
//
// SO THE OFFSET IS NOT REMOVED, IT IS OWNED. `promote.flattenToSpreadsheet`
// already does the only thing that makes the two bases safe to coexist: it
// shifts a copied sheet's LOCAL formulas by the header row and leaves QUALIFIED
// references exactly as written, so nothing is re-pointed at a different row by
// the conversion. `rowMeaning` is the sentence for the other half — the reader
// who has both sheets on screen and is about to type an address at one of them.

/** Which of the two answers a sheet gives to "what does row 1 mean". */
export type RowBase = 'dataset' | 'spreadsheet'

export const rowBaseOf = (sheet: Sheet): RowBase | undefined =>
  sheet.kind === 'table' ? 'dataset' : sheet.kind === 'canvas' ? 'spreadsheet' : undefined

/**
 * What an address AT this sheet counts, in one sentence, for a reader who has
 * two kinds of sheet in front of them.
 *
 * Plain English and no i18n, the convention this file, a1.ts and formula.ts all
 * keep: the panel that shows it owns the translation, the engine owns the fact.
 */
export function rowMeaning(sheet: Sheet): string | undefined {
  const base = rowBaseOf(sheet)
  if (base === 'dataset') {
    return `"${sheet.name}" is a dataset, so ${sheet.name}!A1 is its first DATA row. ` +
      'The header is not a row — the address matches the row number beside it.'
  }
  if (base === 'spreadsheet') {
    return `"${sheet.name}" is a spreadsheet, so ${sheet.name}!A1 is the top row of the grid. ` +
      'A header there is an ordinary cell that happens to hold a word, and it is row 1.'
  }
  return undefined
}

/**
 * What a formula's references are resolved against: which sheets exist, and
 * how big a rectangle each of them really occupies.
 *
 * The DEFAULT refuses every qualified name. That is deliberate: `bindRefs` and
 * `evalCell` can be called with one sheet and no workbook at all, and the
 * honest answer to `Sheet1!A1` in that setting is `#REF!` — the alternative,
 * which this module shipped until the scanner learned about qualifiers, is
 * silently reading the LOCAL A1 and reporting another sheet's number.
 */
export interface RefScope {
  /** Is there a sheet by this name? Case-insensitively, as Excel matches. */
  has(sheet: string): boolean
  /** Trim a rectangle on that sheet (`undefined` = the formula's own sheet). */
  clip(range: RangeRef, sheet: string | undefined): RangeRef | null
  /** OPTIONAL. The document's defined names, minus anything this sheet's own
   *  columns claim. Absent = no names, and every word is a column or `#NAME?`. */
  names?: NameScope
  /**
   * OPTIONAL. Was this scope assembled from a WHOLE workbook?
   *
   * It decides which of two different sentences a failed qualifier gets, and
   * the difference matters to the person reading it. With a workbook, `has()`
   * returning false is a FACT: there is no sheet by that name, go and check the
   * spelling on the tab. Without one, `has()` returns false for every name
   * including the ones sitting in the tab strip, and telling the reader their
   * sheet does not exist is a lie that sends them looking for a deleted sheet
   * that was never deleted.
   */
  workbook?: boolean
}

const NO_SHEETS: RefScope = { has: () => false, clip: (r) => r, workbook: false }

/**
 * The separator between a sheet key and a cell key in a workbook graph node.
 * U+001F, the composite-key trick the CRDT already uses — written as an escape
 * because a literal control character in source survives no copy and no edit.
 */
const NODE_SEP = String.fromCharCode(0x1f)

const sheetKey = (name: string): string => name.toLowerCase()

/** `col,row`, both 0-based — the key a computed-cell map is keyed by. */
export const cellKey = (row: number, col: number): string => `${col},${row}`

export interface CellRecalc {
  /**
   * position key → computed value.
   *
   * Every cell that holds a formula, AND every cell a spill covers. A spilled
   * value is a computed value like any other — it is here and it is nowhere
   * else, because it is never written into the document (see SPILL below).
   */
  values: Map<string, Cell>
  /** the cells that could not be ordered, reported rather than guessed at */
  cycles: string[]
  /** evaluation order, for tests and for explaining a result to a reader */
  order: string[]
  /**
   * Every cell a spill covers — the ANCHOR included — under the anchor that
   * produced it and the rectangle's shape.
   *
   * Whoever paints the sheet reads this to know that a cell holding nothing is
   * nonetheless showing something, and whoever edits it reads it to know that
   * the cell is output rather than input.
   */
  spills: Map<string, SpillClaim>
}

export interface SpillClaim {
  /** the cell key of the formula that produced this value */
  anchor: string
  rows: number
  cols: number
}

/** Is this cell text a formula? The one place the `=` convention is decided. */
export const isFormula = (v: unknown): v is string =>
  typeof v === 'string' && v.length > 1 && v.startsWith('=')

/** The expression inside a formula, without the `=`. */
export const formulaBody = (src: string): string =>
  src.startsWith('=') ? src.slice(1) : src

// --- defined names -----------------------------------------------------------
//
// `=B4*TaxRate` instead of `=B4*0.2`, and `=SUM(Q3Sales)` instead of
// `=SUM('Q3 pipeline'!B2:B41)`.
//
// WHY THEY MATTER MORE HERE THAN IN EXCEL. dash's claim is that a number can be
// traced to where it came from; `=B4*0.2` cannot be traced anywhere, because
// 0.2 is not written down as anything and the next person has to guess whether
// it is VAT, a discount or a typo. A name is the place the guess is answered,
// and one edit moves every use of it at once.
//
// THE MECHANISM IS SUBSTITUTION, AND THAT IS THE WHOLE DESIGN. A name is
// replaced by its TEXT before a reference is bound, so `SUM(Q3Sales)` becomes
// `SUM('Q3 pipeline'!B2:B41)` and every part of this module that already
// works — the binder, the clipper, the workbook-wide dependency ordering, the
// cycle detector — sees a formula it already understands. A name does not need
// its own node kind, its own vector binding, or its own edges: the cells a name
// reaches ARE the cells the formula depends on, and `cellDeps` reports them for
// free. The alternative (bind the name straight to a vector) would have made a
// named range invisible to the ordering, so `TaxRate` pointing at a cell that
// is itself computed would read a stale value.
//
// SCOPE IS THE DOCUMENT, and only the document — see the DEFINED NAMES block in
// model.ts for why one namespace instead of Excel's two, and why a column name
// on a dataset sheet wins over a document name.
//
// A NAME THAT IS NOT DEFINED IS LEFT ALONE, and formula.ts then reports
// `#NAME?`. That is already the right answer and already the one it gives.

/** What a defined name resolves to, for the walk that substitutes it. */
export interface NameScope {
  /** Substitution TEXT for a name, case-insensitively. `undefined` = unknown. */
  lookup(name: string): string | undefined
}

const NO_NAMES: NameScope = { lookup: () => undefined }

/**
 * How many times an expansion may go round before it is called a cycle.
 *
 * A name may be written in terms of another name — Excel allows it and a rate
 * card built out of named parts is the reason to — so one pass is not enough.
 * Eight is far past any chain a person writes and small enough that a
 * pathological document cannot spend a frame here.
 */
export const NAME_DEPTH = 8

/** What `expandNames` reports instead of a name when the chain never settles. */
export const TOO_DEEP = 'a chain of names too deep to resolve'

/**
 * The text a definition substitutes, or `undefined` when it defines nothing.
 *
 * A REFERENCE goes in verbatim: parenthesising `A1:A5` would still work, and
 * would also make every trace of the expansion read worse than the thing the
 * author typed. A LITERAL is parenthesised, because a negative constant
 * substituted into `=2^Rate` has to bind as a value and not as an operator, and
 * a text constant is re-quoted with Excel's doubled-quote escape so a name
 * holding `He said "no"` cannot terminate its own string.
 *
 * `ref` WINS over `v`. Both being set is a document that contradicts itself,
 * and picking the more specific of the two is the only reading that cannot
 * quietly turn a range into a number.
 */
export function nameText(d: DefinedName | undefined): string | undefined {
  if (!d) return undefined
  if (typeof d.ref === 'string' && d.ref.trim() !== '') return d.ref.trim()
  if (typeof d.v === 'number') return Number.isFinite(d.v) ? `(${d.v})` : undefined
  if (typeof d.v === 'string') return `"${d.v.replace(/"/g, '""')}"`
  return undefined
}

/**
 * Substitute every defined name in an expression, repeatedly, until nothing
 * changes.
 *
 * `cycle` names the definition that came back round. A name defined in terms of
 * itself is not resolvable and must not be answered with the partial expansion
 * eight rounds got to — that is a number, and it would look like one.
 *
 * A name is tracked per ROUND, not per occurrence: `=Alpha+Alpha` expands both
 * occurrences of one name at one depth, which is not a cycle. `Alpha` appearing
 * again in the NEXT round means the expansion put it back, which is.
 */
export function expandNames(
  src: string,
  scope: NameScope = NO_NAMES,
): { expr: string; cycle?: string } {
  // A document with no names pays NOTHING: no walk, no allocation. The scanner
  // is one pass over the source per round and a workbook recalculates every
  // formula on every keystroke, so "free when unused" is the price of putting
  // this in the hot path at all.
  if (scope === NO_NAMES) return { expr: src }
  let text = src
  let cycle: string | undefined
  const done = new Set<string>()
  // NAME_DEPTH + 1 rounds: a chain that deep needs one round per link, plus
  // one that finds nothing left to do. Without the confirming round a
  // legitimate chain of exactly NAME_DEPTH would be reported as a cycle.
  for (let pass = 0; pass <= NAME_DEPTH && !cycle; pass++) {
    const round = new Set<string>()
    let hit = false
    text = mapNames(text, (w) => {
      const sub = scope.lookup(w)
      if (sub === undefined) return w
      const k = w.toLowerCase()
      if (done.has(k)) { cycle = w; return w }
      round.add(k)
      hit = true
      return sub
    })
    if (!hit) return { expr: text, cycle }
    for (const k of round) done.add(k)
  }
  // Still expanding after NAME_DEPTH rounds without a name repeating: a chain
  // longer than anything a person writes, and indistinguishable from a cycle
  // built out of enough distinct names. Refused rather than truncated — a
  // partial expansion evaluates to a NUMBER, and it would look like one.
  return { expr: text, cycle: cycle ?? TOO_DEEP }
}

/**
 * The document's name table as a scope, minus anything a column already claims.
 *
 * `shadowed` is the sheet's own column names. It is asked LAST and costs one
 * set lookup per candidate word, so a workbook with no names pays nothing —
 * the table is empty and `lookup` returns on the first line.
 */
export function documentNames(
  names: Record<string, DefinedName> | undefined,
  shadowed?: ReadonlySet<string>,
): NameScope {
  const table = new Map<string, string>()
  for (const [k, d] of Object.entries(names ?? {})) {
    const text = nameText(d)
    // A name spelled like a cell is unreachable — a1.ts resolves `TAX1` as an
    // address long before the word reaches this table — so it is dropped here
    // rather than sitting in the file looking as if it applies.
    if (text !== undefined && isNameLike(k)) table.set(k.toLowerCase(), text)
  }
  if (!table.size) return NO_NAMES
  return {
    lookup: (w) => (shadowed?.has(w.toLowerCase()) ? undefined : table.get(w.toLowerCase())),
  }
}

/** Why a proposed name is refused. `null` = it is fine. Panels localise these. */
export type NameProblem = 'empty' | 'shape' | 'cellshaped' | 'taken'

export const NAME_PROBLEM_EN: Record<NameProblem, string> = {
  empty: 'A name cannot be blank.',
  shape: 'A name must start with a letter or underscore, and hold only letters, digits, "_" and ".".',
  cellshaped: 'That is a cell address, so a formula would read the cell and never the name.',
  taken: 'There is already a name spelled that way.',
}

/**
 * Is this a name a formula could actually reach?
 *
 * The `cellshaped` refusal is the load-bearing one and the one a naive
 * implementation skips: `TAX1` parses as a cell address, so a definition under
 * that spelling would be accepted, saved, and never once consulted. Refusing at
 * the point of definition is the only place a person can be told.
 */
export function validateDefinedName(
  name: string,
  existing?: Record<string, DefinedName>,
): NameProblem | null {
  const n = name.trim()
  if (!n) return 'empty'
  if (parseRef(n)) return 'cellshaped'
  if (!isNameLike(n)) return 'shape'
  const k = n.toLowerCase()
  for (const have of Object.keys(existing ?? {})) {
    if (have !== n && have.toLowerCase() === k) return 'taken'
  }
  return null
}

/**
 * Move every defined name's `ref` because rows or columns were inserted or
 * removed — the same rewrite `shiftSheetFormulas` does for formulas, and it has
 * to happen at the same moment or a name goes on pointing at a row that is now
 * somebody else's.
 *
 * Returns only the entries that CHANGED, so an edit that touched nothing does
 * not land the whole name table in an undo step.
 *
 * A name whose target is entirely deleted comes back as `#REF!` and STAYS IN
 * THE TABLE. Dropping it would report `#NAME?` at every use — "you never
 * defined that" — for an event that was "the cells you named were deleted".
 * The first is a lie about what happened and gives the reader nothing to fix;
 * the second leaves the definition sitting there to be re-pointed.
 */
export function shiftDefinedNames(
  names: Record<string, DefinedName> | undefined,
  axis: 'row' | 'col',
  at: number,
  count: number,
  scope?: ShiftScope,
): Array<[string, string]> {
  const out: Array<[string, string]> = []
  for (const [k, d] of Object.entries(names ?? {})) {
    const ref = typeof d?.ref === 'string' ? d.ref : undefined
    if (ref === undefined || ref.trim() === '' || ref.includes(REF_ERR)) continue
    const next = shiftRefsForInsert(ref, axis, at, count, scope)
    if (next !== ref) out.push([k, next])
  }
  return out
}

// --- dependencies -----------------------------------------------------------

interface Dep {
  /** the generated name this reference was bound to */
  name: string
  /** the sheet it names, when it named one */
  sheet?: string
  /** the positions it covers — one for a reference, many for a range */
  cells: ScopedRef[]
  /** how wide the (clipped) rectangle is, so a lookup can read its shape */
  width?: number
  /** the range was too large to expand, so the whole formula is an error */
  tooBig?: boolean
  /** the source already carried a `#REF!` from an earlier structural edit */
  dead?: boolean
  /** it names a sheet this workbook does not have */
  missing?: boolean
  /** a defined name that expands into itself — the offending spelling */
  nameCycle?: string
}

/** Cells in a rectangle, without building it — the check the cap is made of. */
const rectSize = (a: CellRef, b: CellRef): number =>
  (Math.abs(a.col - b.col) + 1) * (Math.abs(a.row - b.row) + 1)

/**
 * Rewrite a formula's references to bound names, and report what it read.
 *
 * A `#REF!` already sitting in the source is carried through as `dead` rather
 * than parsed: a1.ts minted it because the cell it named was deleted, and the
 * only honest result is the same error again. Letting it reach formula.ts would
 * turn a precise "that cell is gone" into `#VALUE! could not parse`.
 *
 * `scope` decides two things and refuses rather than guessing at both: whether
 * a named sheet exists (it does not ⇒ `missing`, and the formula is `#REF!`),
 * and how much of a rectangle that sheet occupies. The size cap is checked on
 * the rectangle AS WRITTEN, before any clipping — `A1:XFD1048576` is a typo
 * whichever sheet it lands on, and answering it with a clipped handful of cells
 * would be answering a question nobody asked.
 */
export function bindRefs(src: string, scope: RefScope = NO_SHEETS): { expr: string; deps: Dep[] } {
  const deps: Dep[] = []
  // NAMES FIRST, then references. A name substitutes TEXT, so by the time the
  // reference scanner runs there is nothing left that it has not always known
  // how to read — see the DEFINED NAMES block above for why that ordering is
  // the entire design rather than an implementation detail.
  const named = expandNames(src, scope.names)
  if (named.cycle !== undefined) {
    return { expr: named.expr, deps: [{ name: '', cells: [], nameCycle: named.cycle }] }
  }
  src = named.expr
  const expr = mapRefs(src, (u) => {
    const name = `_a1_${deps.length}`
    const sheet = u.sheet
    if (sheet !== undefined && !scope.has(sheet)) {
      deps.push({ name, sheet, cells: [], missing: true })
      return name
    }
    if (!u.to) {
      deps.push({ name, sheet, cells: [{ ...u.from, sheet }] })
      return name
    }
    if (rectSize(u.from, u.to) > RANGE_CELL_MAX) {
      deps.push({ name, sheet, cells: [], tooBig: true })
      return name
    }
    const box = scope.clip({ from: u.from, to: u.to }, sheet)
    const cells = box === null ? [] : expandRange(box)
    if (cells === null) {
      deps.push({ name, sheet, cells: [], tooBig: true })
      return name
    }
    if (sheet !== undefined) for (const c of cells as ScopedRef[]) c.sheet = sheet
    const width = box === null ? 0 : Math.abs(box.to.col - box.from.col) + 1
    deps.push({ name, sheet, cells, width })
    return name
  })
  // The scanner leaves `#REF!` alone (it is not a reference), so look for it in
  // the ORIGINAL text — the rewrite may have introduced names around it.
  return { expr, deps: src.includes(REF_ERR) ? [{ name: '', cells: [], dead: true }] : deps }
}

/** Every position a formula reads, for the dependency graph. */
export const cellDeps = (src: string, scope?: RefScope): ScopedRef[] =>
  bindRefs(src, scope).deps.flatMap((d) => d.cells)

// --- evaluation -------------------------------------------------------------

const ERR_REF = (why = 'the referenced cell was deleted'): FormulaError =>
  new FormulaError(REF_ERR, why)
/**
 * A qualified reference that did not land, and the two reasons it can fail.
 *
 * `#REF!` is the right code for the FIRST one only. To a spreadsheet reader
 * `#REF!` means "the thing this pointed at was deleted" — their file, their
 * mistake — so spending it on "this evaluation was not given the workbook"
 * blames the reader for the caller's limit. The code has to stay `#REF!` in
 * both (it is what Excel gives for a deleted sheet, and the grid has one column
 * of space to say it in), so the whole difference lives in `why`, which is what
 * the panel actually shows.
 */
const ERR_SHEET = (name: string, workbook = true): FormulaError =>
  new FormulaError(REF_ERR, workbook
    ? `there is no sheet called "${name}" in this workbook`
    : `"${name}" is another sheet, and this formula is being computed on its ` +
      'own — outside the workbook that would resolve it')
/**
 * `Jan!Amount` — a sheet, and then something that is not an address on it.
 *
 * The spelling a DATASET author reaches for, because on their own sheet a
 * column name is exactly how you say which column. It bound as nothing, so
 * formula.ts used to report the bare word `Jan` as an unknown name — and once
 * the column language learned to name the cross-sheet boundary, a CELL formula
 * would have inherited that sentence and been told to put it in a cell, which
 * is where it already was. A cell formula CAN reach another sheet; what it
 * cannot do is address a column there, because a column name is not a position
 * and the other sheet is reached by position.
 */
const ERR_NOT_ADDRESS = (sheet: string, after: string): FormulaError =>
  new FormulaError('#NAME?',
    `"${sheet}" is a sheet, but "${after}" is not a cell address on it. ` +
    `A formula reaches another sheet by position — ${sheet}!B2, or ${sheet}!B1:B6 — ` +
    'and a column name only names a column on its own sheet.')
const ERR_BIG = (): FormulaError =>
  new FormulaError('#VALUE!', 'the range covers too many cells to evaluate')
const ERR_CYCLE = (): FormulaError => new FormulaError('#CYCLE!')
const ERR_NAME_CYCLE = (name: string): FormulaError =>
  new FormulaError('#CYCLE!', name.startsWith('a chain')
    ? name
    : `the name "${name}" is defined in terms of itself`)

/**
 * Evaluate one cell's formula, reading other cells through `read`.
 *
 * `read` returns what a reference SEES — a computed value if that cell is
 * itself a formula, a stored value otherwise — which is why ordering happens
 * outside this function and not inside it.
 *
 * A reference off the edge of the sheet is EMPTY, not an error. `A50` on a
 * ten-row sheet is a blank cell in every spreadsheet ever written; `#REF!` means
 * something specific and narrower — the cell you named was deleted — and
 * spending it on "you pointed past the end" would make the one error that
 * carries real information indistinguishable from a typo.
 *
 * A reference to a SHEET that is not there is the deleted case, not the past-
 * the-end case, so it is `#REF!` for the whole formula. That is what Excel does
 * with a deleted sheet, and it is the only answer that cannot be mistaken for
 * data: `Pipeline!D2` reading blank would put an empty cell where a number was
 * supposed to be, and `=Pipeline!D2*1.2` would then report 0.
 */
export function evalCell(
  src: string,
  read: (r: ScopedRef) => Cell,
  opts: { now?: string; cols?: Map<string, Vec>; scope?: RefScope } = {},
): Cell {
  return evalCellArray(src, read, opts).value
}

/**
 * What a formula's result IS, before it is squeezed into one cell.
 *
 * `evalCell` has always thrown everything past the first value away, which is
 * why `=A1:A10*2` reported one number and looked like a mistake. It is not a
 * mistake — it is an ARRAY, and the modern answer is to let it SPILL. See the
 * SPILL block further down for the geometry and the collision rule; this
 * function's only job is to say what shape came back.
 *
 * `cells` is present only when there is more than one, so the scalar path
 * allocates nothing new and every existing caller is unaffected.
 */
export interface CellResult {
  /** what the ANCHOR cell shows: the top-left value, or the error */
  value: Cell
  rows: number
  cols: number
  /** row-major, set only when `rows * cols > 1` */
  cells?: Vec
}

export function evalCellArray(
  src: string,
  read: (r: ScopedRef) => Cell,
  opts: { now?: string; cols?: Map<string, Vec>; scope?: RefScope } = {},
): CellResult {
  const one = (v: Cell): CellResult => ({ value: v, rows: 1, cols: 1 })
  const { expr, deps } = bindRefs(formulaBody(src), opts.scope)
  const circular = deps.find((d) => d.nameCycle !== undefined)
  if (circular) return one(ERR_NAME_CYCLE(circular.nameCycle!))
  if (deps.some((d) => d.dead)) return one(ERR_REF())
  const gone = deps.find((d) => d.missing)
  if (gone) return one(ERR_SHEET(gone.sheet ?? '', opts.scope?.workbook !== false))
  // A qualifier still in the REWRITTEN expression is one that bound to no
  // reference — every real one has become a generated name by now, and a
  // missing sheet was caught on the line above.
  const stray = expr.indexOf('!') < 0 ? undefined : sheetQualifiers(expr)[0]
  if (stray) return one(ERR_NOT_ADDRESS(stray.sheet, stray.after))
  if (deps.some((d) => d.tooBig)) return one(ERR_BIG())

  // Column names stay visible, so a cell formula can also say `SUM(amount)`.
  // The generated names are added on top and cannot collide with them.
  const cols = new Map<string, Vec>(opts.cols ?? [])
  for (const d of deps) {
    const vec: Vec = d.cells.map(read)
    // A range knows its own shape, which is what VLOOKUP and INDEX(r, row, col)
    // read to tell a 2-column table from a 20-row one.
    if (d.width !== undefined) (vec as Vec & Shaped).__cols = d.width
    cols.set(d.name, vec)
  }

  const out = evaluate(expr, { cols, n: 1, now: opts.now })
  if (out.length <= 1) return one(out[0] ?? null)
  const shape = vecShape(out)
  return { value: out[0] ?? null, rows: shape.rows, cols: shape.cols, cells: out }
}

/**
 * Would this cell formula PARSE? null when it would; otherwise why not, with
 * the place it went wrong spelled as the author wrote it.
 *
 * ENTRY ONLY — the cell editor and the formula bar ask before committing
 * (finding 3.4). A formula already in a file is never refused: it evaluates,
 * forgivingly, as it always has. References are swapped for placeholders that
 * read as plain words (they are what `bindRefs` would swap them for), so the
 * grammar is formula.ts's own and the only thing this adds is the swap back.
 */
export function cellFormulaProblem(src: string, scope: RefScope = NO_SHEETS): SyntaxProblem | null {
  const named = expandNames(formulaBody(src), scope.names)
  if (named.cycle !== undefined) return null          // evaluates to its own error
  // `#REF!` is a reference that was deleted — a formula, not a typo
  if (named.expr.includes(REF_ERR)) return null
  const texts: string[] = []
  const expr = mapRefs(named.expr, (u) => { texts.push(u.text); return `_ref${texts.length - 1}_` })
  const why = syntaxProblem(expr)
  if (!why) return null
  const back = why.near.match(/^_ref(\d+)_$/)
  return back ? { ...why, near: texts[Number(back[1])] ?? why.near } : why
}

// --- ordering ---------------------------------------------------------------

/** How much of a rectangle a source occupies, when it has no opinion of its own. */
function extentClip(src: CellSource, r: RangeRef): RangeRef | null {
  if (src.unavailable) return null
  const c0 = Math.min(r.from.col, r.to.col)
  const c1 = Math.max(r.from.col, r.to.col)
  const r0 = Math.min(r.from.row, r.to.row)
  const r1 = Math.max(r.from.row, r.to.row)
  if (c0 < 0 || r0 < 0 || c0 >= src.cols || r0 >= src.rows) return null
  return {
    from: { col: c0, row: r0, absCol: false, absRow: false },
    to: {
      col: Math.min(c1, src.cols - 1),
      row: Math.min(r1, src.rows - 1),
      absCol: false,
      absRow: false,
    },
  }
}

const clipTo = (src: CellSource, r: RangeRef): RangeRef | null =>
  src.clipRange ? src.clipRange(r) : extentClip(src, r)

/** Every formula on a sheet — from its own index when it keeps one. */
function formulasOf(src: CellSource): Array<{ row: number; col: number; src: string }> {
  if (src.formulaCells) return [...src.formulaCells()]
  const out: Array<{ row: number; col: number; src: string }> = []
  for (let r = 0; r < src.rows; r++) {
    for (let c = 0; c < src.cols; c++) {
      const f = src.formulaAt(r, c)
      if (f !== undefined) out.push({ row: r, col: c, src: f })
    }
  }
  return out
}

// --- SPILL --------------------------------------------------------------------
//
// `=A1:A10*2` in ONE cell, and ten values appear. Muscle memory for anyone who
// has used Excel since 2019, and the single most jarring absence for them.
//
// A SPILLED RANGE IS COMPUTED, NOT STORED, and everything below follows from
// that one sentence. Only the ANCHOR holds a formula; the other cells are
// OUTPUT. They are written into `CellRecalc.values` and into nothing else —
// never into `sheet.cells`, so they cannot be saved as if someone typed them,
// cannot be edited independently, and vanish the instant the anchor changes,
// because the next recalculation simply does not produce them. Materialising
// them into the document would be the same failure as caching a formula's
// result next to the formula: two answers to one question, and the stale one
// looks exactly as authoritative as the live one.
//
// COLLISION BLOCKS, IT NEVER OVERWRITES. Anything already in the spill area —
// a typed value, another formula, another spill — stops the whole spill and the
// anchor reads `#SPILL!`. Overwriting is data loss, and it is data loss of the
// worst kind: silent, and to a cell the author was looking at. The anchor keeps
// its formula and starts working again the moment the obstruction is cleared.
//
// WHICH KIND: THE SPREADSHEET, AND DELIBERATELY NOT THE DATASET.
// docs/dash-sheet-kinds.md draws the line and this lands on the right side of
// it. A dataset is typed per COLUMN and is "exactly the rows there are"; a
// spill is a rectangle of arbitrary shape arriving at an arbitrary position, so
// on a dataset it would have to either invent rows (breaking the extent rule)
// or write cells of its own type into a typed column (breaking the type rule).
// And the columnar answer to the same need is already there and is better: a
// COLUMN FORMULA is one expression that fills a whole column by construction,
// survives every structural edit, and cannot collide with anything. `=A1:A10*2`
// spilling down a dataset would be a worse spelling of a feature that kind
// already has. So `CellSource.spill` is true for the spreadsheet kind alone,
// and on a dataset a cell formula keeps returning its first value as it always
// has.
//
// ORDERING IS THE HARD PART, and it is why this runs to a FIXED POINT. A cell
// reading `D2` where D2 is spill output has a dependency on the ANCHOR at D1 —
// but the footprint is not known until the anchor has been evaluated, and the
// evaluation order is decided by the dependencies. That is circular, so the
// recalculation is run again with the footprints the previous run discovered,
// until the footprints stop changing. In practice that is two passes: one to
// find them, one to use them. A workbook with no spills does one pass and pays
// nothing. A spill whose own size depends on its own output never settles, and
// after SPILL_PASSES those anchors are told so rather than being handed
// whichever answer the last iteration happened to hold.
//
// CONFLICTS ARE RESOLVED IN READING ORDER, not in evaluation order. Two spills
// that want the same cell have to produce the same winner on every machine and
// after every reload, and evaluation order depends on the dependency graph and
// on the order a sparse cell map happens to enumerate. Top-most then left-most
// wins; the other reads `#SPILL!`.

/** How far a spill may reach before it is refused. Excel's own sheet bounds. */
const SPILL_MAX_ROWS = 1_048_576
const SPILL_MAX_COLS = 16_384
/**
 * Cells one spill may place.
 *
 * A range binds up to RANGE_CELL_MAX (a million), and a million cells the grid
 * has to paint is a dead tab rather than an answer. `#SPILL!` is answerable.
 */
export const SPILL_CELL_MAX = 100_000
/** Iterations before a spill that resizes itself is called circular. */
const SPILL_PASSES = 6

/**
 * Compute every formula cell in a WORKBOOK, in dependency order.
 *
 * Kahn's algorithm over cells, exactly as the single-sheet version always did —
 * the only difference is that a node is now `<sheet>U+001F<col>,<row>` and an
 * edge may cross a sheet boundary. That is what makes a cycle drawn THROUGH
 * another sheet detectable at all: `Sheet1!A1 = Sheet2!A1 + 1` and
 * `Sheet2!A1 = Sheet1!A1` is a circle, and per-sheet ordering can only see two
 * halves of it, each of which looks perfectly settled on its own.
 *
 * A NODE IS NAMESPACED BY THE SHEET'S POSITION, not by its name, and every
 * sheet computes. Names are not unique — renaming a tab to one already in use
 * is allowed — so keying the graph by name would make the second "Sales" a
 * sheet whose formulas silently never ran. What names DO decide is where a
 * reference lands: `Sales!A1` resolves to the FIRST sheet of that name,
 * case-insensitively as Excel matches, which is at least predictable.
 *
 * SPILLED OUTPUT IS PART OF THE GRAPH, which is why the whole thing may run
 * more than once — see the SPILL block above.
 *
 * Returns one result per sheet, keyed by `id` where it has one and by `name`
 * otherwise.
 */
export function recalcWorkbook(sheets: SheetSource[], now?: string): Map<string, CellRecalc> {
  /** name → the sheet POSITION a reference to that name resolves to. */
  const byName = new Map<string, number>()
  sheets.forEach((s, i) => {
    const k = sheetKey(s.name)
    if (!byName.has(k)) byName.set(k, i)
  })

  const node = (at: number, row: number, col: number): string =>
    `${at}${NODE_SEP}${cellKey(row, col)}`

  /** Which sheet a reference lands on: the one it named, or the one it is on. */
  const targetAt = (ref: ScopedRef, self: number): number =>
    ref.sheet === undefined ? self : byName.get(sheetKey(ref.sheet)) ?? -1

  // every formula in the workbook, and the one graph they all live in
  const formulas = new Map<string, { at: number; row: number; col: number; src: string }>()
  sheets.forEach((s, i) => {
    for (const f of formulasOf(s.source)) {
      formulas.set(node(i, f.row, f.col), { at: i, row: f.row, col: f.col, src: f.src })
    }
  })

  /**
   * Is there something at this position that a spill must not write over?
   *
   * A stored value or a formula. NOT formatting: a coloured empty cell is still
   * empty, and Excel spills through one. Past the sheet's stored extent there
   * is by definition nothing.
   */
  const occupied = (at: number, row: number, col: number): boolean => {
    const s = sheets[at]
    if (!s) return true
    if (row >= s.source.rows || col >= s.source.cols) return false
    if (s.source.formulaAt(row, col) !== undefined) return true
    const v = s.source.valueAt(row, col)
    return v !== null && v !== undefined && v !== ''
  }

  interface Attempt {
    k: string; at: number; row: number; col: number
    rows: number; cols: number; cells: Vec
  }
  interface Pass {
    values: Map<string, Cell>
    order: string[]
    cycles: string[]
    claims: Map<string, SpillClaim>
  }

  const anySpill = sheets.some((s) => s.source.spill)

  const runPass = (prior: Map<string, SpillClaim>): Pass => {
    // How far each sheet reaches once the PREVIOUS pass's spills are counted.
    // A range over spilled cells must bind them — `SUM(A1:A20)` under a spill
    // that fills A1:A10 on a sheet that stores only A1 would otherwise clip to
    // one cell and total one number. The head of a range is never moved, only
    // its tail, so this can only over-include, and an over-included empty cell
    // reads as empty.
    const reach = new Map<number, { rows: number; cols: number }>()
    for (const key of prior.keys()) {
      const sep = key.indexOf(NODE_SEP)
      const at = Number(key.slice(0, sep))
      const p = posOf(key.slice(sep + 1))
      if (!p) continue
      const r = reach.get(at) ?? { rows: 0, cols: 0 }
      if (p.row + 1 > r.rows) r.rows = p.row + 1
      if (p.col + 1 > r.cols) r.cols = p.col + 1
      reach.set(at, r)
    }

    const clipOn = (at: number, r: RangeRef): RangeRef | null => {
      const s = sheets[at]
      if (!s) return null
      const base = clipTo(s.source, r)
      const far = reach.get(at)
      if (!far || s.source.unavailable) return base
      const c0 = Math.min(r.from.col, r.to.col)
      const c1 = Math.max(r.from.col, r.to.col)
      const r0 = Math.min(r.from.row, r.to.row)
      const r1 = Math.max(r.from.row, r.to.row)
      if (c0 < 0 || r0 < 0) return base
      const lastRow = Math.min(r1, far.rows - 1)
      const lastCol = Math.min(c1, far.cols - 1)
      if (lastRow < r0 || lastCol < c0) return base
      const abs = { absCol: false, absRow: false }
      if (base === null) {
        return { from: { col: c0, row: r0, ...abs }, to: { col: lastCol, row: lastRow, ...abs } }
      }
      return {
        from: base.from,
        to: {
          col: Math.max(base.to.col, lastCol),
          row: Math.max(base.to.row, lastRow),
          ...abs,
        },
      }
    }

    const scopeFor = (self: number): RefScope => ({
      workbook: !sheets[self]?.detached,
      has: (name) => byName.has(sheetKey(name)),
      clip: (r, name) => {
        const at = name === undefined ? self : byName.get(sheetKey(name)) ?? -1
        return at < 0 ? null : clipOn(at, r)
      },
      names: sheets[self]?.names,
    })

    const scopes = new Map<number, RefScope>()
    const scopeOf = (at: number): RefScope => {
      let sc = scopes.get(at)
      if (!sc) { sc = scopeFor(at); scopes.set(at, sc) }
      return sc
    }

    // Edges, counted between cells that hold formulas — and now also from a
    // SPILL ANCHOR to whoever reads a cell it covers. Without that edge the
    // reader is ordered before the anchor and sees the stored (empty) cell.
    const needs = new Map<string, Set<string>>()
    const feeds = new Map<string, Set<string>>()
    for (const [k, f] of formulas) {
      const n = new Set<string>()
      for (const ref of cellDeps(formulaBody(f.src), scopeOf(f.at))) {
        const at = targetAt(ref, f.at)
        if (at < 0) continue
        const dk = node(at, ref.row, ref.col)
        const owner = formulas.has(dk) ? dk : prior.get(dk)?.anchor
        if (owner === undefined) continue
        if (owner === k) {
          // A self-reference is a cycle of one, and so is a formula reading its
          // own spill. Neither can be an edge (Kahn would never dequeue it and
          // it would look like an unrelated cycle), so it is recorded as a
          // dependency on itself and caught by the drain below.
          n.add(k)
          continue
        }
        n.add(owner)
        if (!feeds.has(owner)) feeds.set(owner, new Set())
        feeds.get(owner)!.add(k)
      }
      needs.set(k, n)
    }

    const values = new Map<string, Cell>()
    const left = new Map<string, number>()
    const queue: string[] = []
    for (const [k, n] of needs) {
      left.set(k, n.size)
      if (n.size === 0) queue.push(k)
    }

    /**
     * What a reference sees: a computed value if we have one, else what is
     * stored.
     *
     * The COMPUTED lookup happens before the bounds check, and only when this
     * pass knows about spills: a spilled cell is routinely past the sheet's
     * stored extent (that is what an unbounded sheet is for), so a bounds check
     * first would answer "empty" for a cell that is plainly showing a number.
     *
     * The unqualified case is otherwise the hot one — a range over ten thousand
     * cells on this sheet is ten thousand calls — so it resolves without a
     * lookup.
     */
    const spillsKnown = prior.size > 0
    const readFrom = (self: number) => {
      const own = sheets[self]
      return (r: ScopedRef): Cell => {
        const at = r.sheet === undefined ? self : byName.get(sheetKey(r.sheet)) ?? -1
        const s = r.sheet === undefined ? own : sheets[at]
        if (!s) return ERR_SHEET(r.sheet ?? '', !own?.detached)
        if (s.source.unavailable) return new FormulaError('#N/A', s.source.unavailable)
        if (r.row < 0 || r.col < 0) return null
        if (spillsKnown) {
          const sk = node(at, r.row, r.col)
          if (values.has(sk)) return values.get(sk)!
        }
        if (r.row >= s.source.rows || r.col >= s.source.cols) return null
        const k = node(at, r.row, r.col)
        if (values.has(k)) return values.get(k)!
        // BACKSTOP, and currently unreachable: every formula dependency is an
        // edge, so Kahn settles it before this cell is dequeued, and a formula
        // inside a cycle is never dequeued at all. It stays because the failure
        // it prevents is silent — a future change to the edge rules would
        // otherwise let a reference read a stored value that a formula was
        // about to overwrite, and the result would be a plausible number nobody
        // could tell was stale. Deliberately not covered by the rig: a check
        // that cannot fail is worse than no check, and this line's job is
        // redundancy.
        if (formulas.has(k)) return ERR_CYCLE()
        return s.source.valueAt(r.row, r.col)
      }
    }

    // The column vectors a sheet's own formulas can name (`SUM(amount)`), built
    // at most once per sheet and only for a sheet that computes something.
    const vecs = new Map<number, Map<string, Vec> | undefined>()
    const vectorsOf = (at: number): Map<string, Vec> | undefined => {
      if (!vecs.has(at)) vecs.set(at, sheets[at]?.vectors?.())
      return vecs.get(at)
    }
    const readers = new Map<number, (r: ScopedRef) => Cell>()
    const readerOf = (at: number): (r: ScopedRef) => Cell => {
      let rd = readers.get(at)
      if (!rd) { rd = readFrom(at); readers.set(at, rd) }
      return rd
    }

    /** Why this array result cannot land here, or `null` if it can. */
    const blocked = (a: Attempt): string | null => {
      if (a.rows * a.cols > SPILL_CELL_MAX) {
        return `the result is ${a.rows * a.cols} cells, more than one formula may place`
      }
      if (a.row + a.rows > SPILL_MAX_ROWS || a.col + a.cols > SPILL_MAX_COLS) {
        return 'the result runs off the edge of the sheet'
      }
      for (let r = 0; r < a.rows; r++) {
        for (let c = 0; c < a.cols; c++) {
          if (r === 0 && c === 0) continue
          const row = a.row + r
          const col = a.col + c
          if (occupied(a.at, row, col)) {
            return `${formatRef({ col, row, absCol: false, absRow: false })} is not empty`
          }
          const held = prior.get(node(a.at, row, col))
          if (held && held.anchor !== a.k) {
            return `${formatRef({ col, row, absCol: false, absRow: false })} already holds another formula's result`
          }
        }
      }
      return null
    }

    const attempts: Attempt[] = []
    const write = (a: Attempt, claims: Map<string, SpillClaim>): void => {
      const shape = { anchor: a.k, rows: a.rows, cols: a.cols }
      claims.set(a.k, shape)
      for (let r = 0; r < a.rows; r++) {
        for (let c = 0; c < a.cols; c++) {
          if (r === 0 && c === 0) continue
          const nk = node(a.at, a.row + r, a.col + c)
          values.set(nk, a.cells[r * a.cols + c] ?? null)
          claims.set(nk, shape)
        }
      }
    }

    const order: string[] = []
    const live = new Map<string, SpillClaim>()
    while (queue.length) {
      const k = queue.shift()!
      const f = formulas.get(k)!
      order.push(k)
      const res = evalCellArray(f.src, readerOf(f.at), {
        now, cols: vectorsOf(f.at), scope: scopeOf(f.at),
      })
      values.set(k, res.value)
      if (res.cells && sheets[f.at]?.source.spill) {
        const a: Attempt = {
          k, at: f.at, row: f.row, col: f.col, rows: res.rows, cols: res.cols, cells: res.cells,
        }
        const why = blocked(a)
        if (why) values.set(k, spillError(why))
        else { attempts.push(a); write(a, live) }
      }
      for (const d of feeds.get(k) ?? []) {
        const rem = (left.get(d) ?? 1) - 1
        left.set(d, rem)
        if (rem === 0) queue.push(d)
      }
    }

    // Two spills that both got this far want the same cell. Reading order
    // decides, never evaluation order — see the SPILL block. The loser's values
    // are removed and the winners are re-written, because the loser may have
    // clobbered an overlapping cell on its way past.
    let claims = live
    if (attempts.length > 1) {
      const sorted = [...attempts].sort((x, y) =>
        x.at - y.at || x.row - y.row || x.col - y.col)
      const kept: Attempt[] = []
      const taken = new Set<string>()
      const losers: Attempt[] = []
      for (const a of sorted) {
        let clash = false
        for (let r = 0; r < a.rows && !clash; r++) {
          for (let c = 0; c < a.cols && !clash; c++) {
            if (taken.has(node(a.at, a.row + r, a.col + c))) clash = true
          }
        }
        if (clash) { losers.push(a); continue }
        kept.push(a)
        for (let r = 0; r < a.rows; r++) {
          for (let c = 0; c < a.cols; c++) taken.add(node(a.at, a.row + r, a.col + c))
        }
      }
      if (losers.length) {
        claims = new Map()
        for (const a of losers) {
          for (let r = 0; r < a.rows; r++) {
            for (let c = 0; c < a.cols; c++) {
              if (r === 0 && c === 0) continue
              values.delete(node(a.at, a.row + r, a.col + c))
            }
          }
          values.set(a.k, spillError("another formula's result already covers these cells"))
        }
        for (const a of kept) write(a, claims)
      }
    }

    // Never dequeued ⇒ never evaluated ⇒ in a cycle. A formula node cannot be
    // in `values` for any other reason: a spill only ever writes to cells that
    // the occupancy check proved hold neither a value nor a formula.
    const cycles: string[] = []
    const settled = new Set(order)
    for (const k of formulas.keys()) {
      if (!settled.has(k)) { cycles.push(k); values.set(k, ERR_CYCLE()) }
    }

    return { values, order, cycles, claims }
  }

  /** Do two passes agree about where every spill landed? */
  const same = (a: Map<string, SpillClaim>, b: Map<string, SpillClaim>): boolean => {
    if (a.size !== b.size) return false
    for (const [k, v] of a) {
      const w = b.get(k)
      if (!w || w.anchor !== v.anchor || w.rows !== v.rows || w.cols !== v.cols) return false
    }
    return true
  }

  let pass = runPass(new Map())
  if (anySpill && pass.claims.size) {
    let settled = false
    for (let i = 0; i < SPILL_PASSES; i++) {
      const next = runPass(pass.claims)
      if (same(next.claims, pass.claims)) { pass = next; settled = true; break }
      pass = next
    }
    if (!settled) {
      // A spill whose footprint depends on its own output. Told, not guessed
      // at: the alternative is handing the reader whichever size the last
      // iteration happened to hold, which is a different number on a different
      // day and nothing on screen says so.
      const anchors = new Set<string>()
      for (const c of pass.claims.values()) anchors.add(c.anchor)
      for (const k of anchors) {
        pass.values.set(k, spillError('the size of this result depends on where it lands'))
      }
      for (const [k, c] of [...pass.claims]) {
        if (k !== c.anchor) pass.values.delete(k)
      }
      pass.claims = new Map()
    }
  }

  // split back out, per sheet, in the keys the callers already use
  const out = new Map<string, CellRecalc>()
  const keyed = sheets.map((s) => s.id ?? s.name)
  for (const k of keyed) {
    if (!out.has(k)) {
      out.set(k, { values: new Map(), cycles: [], order: [], spills: new Map() })
    }
  }
  const bucket = (id: string): CellRecalc | undefined =>
    out.get(keyed[Number(id.slice(0, id.indexOf(NODE_SEP)))])
  const cellOf = (id: string): string => id.slice(id.indexOf(NODE_SEP) + 1)
  for (const [id, v] of pass.values) bucket(id)?.values.set(cellOf(id), v)
  for (const id of pass.order) bucket(id)?.order.push(cellOf(id))
  for (const id of pass.cycles) bucket(id)?.cycles.push(cellOf(id))
  for (const [id, c] of pass.claims) {
    bucket(id)?.spills.set(cellOf(id), { anchor: cellOf(c.anchor), rows: c.rows, cols: c.cols })
  }
  return out
}

/**
 * How far a sheet is occupied once its spills are counted.
 *
 * The grid rules its sheet from the USED range outward, and a spill's output is
 * used range that is in no cell map. Without this a `=A1:A100*2` on a
 * three-row sheet would paint its first forty rows and stop, and the reader
 * would have no way to tell a spill that ended from one that ran out of paper.
 */
export function spillExtent(r: CellRecalc): { rows: number; cols: number } {
  let rows = 0
  let cols = 0
  for (const key of r.spills.keys()) {
    const p = posOf(key)
    if (!p) continue
    if (p.row + 1 > rows) rows = p.row + 1
    if (p.col + 1 > cols) cols = p.col + 1
  }
  return { rows, cols }
}

/**
 * Is this cell OUTPUT rather than input — a value that arrived from an anchor
 * somewhere else?
 *
 * The anchor itself is not spilled output: it holds the formula, and it is the
 * one cell of the rectangle a person may edit.
 */
export function spilledFrom(r: CellRecalc, row: number, col: number): string | undefined {
  const k = cellKey(row, col)
  const c = r.spills.get(k)
  return c && c.anchor !== k ? c.anchor : undefined
}

/**
 * Compute every formula cell in ONE sheet, in dependency order.
 *
 * The single-sheet case of `recalcWorkbook`, and the shape every caller used
 * before sheets could reference each other. A qualified reference here names a
 * sheet this call cannot see, so it reads `#REF!` — pass the whole workbook to
 * resolve one.
 */
export function recalcCells(
  src: CellSource,
  now?: string,
  cols?: Map<string, Vec>,
  names?: NameScope,
): CellRecalc {
  const one: SheetSource = {
    name: '', source: src, vectors: cols && (() => cols), names, detached: true,
  }
  return recalcWorkbook([one], now).get('')!
}

/**
 * One sheet's cell formulas, computed THROUGH ITS WORKBOOK — the call a grid
 * painting a sheet should make, of EITHER kind.
 *
 * THIS EXISTS BECAUSE THE TWO KINDS HAD TWO DIFFERENT ANSWERS TO ONE QUESTION.
 * A spreadsheet sheet went through `recalcWorkbook`, so `=Contacts!D2` resolved.
 * A dataset sheet went through `recalcCells`, which is one sheet and no
 * workbook, so the identical formula in the identical workbook came back
 * `#REF!` — and, worse, `#REF! there is no sheet called "Contacts" in this
 * workbook` about a sheet sitting in the tab strip. That was never a decision
 * about the kinds; it was two call sites, and a kind is not a place to keep an
 * accident.
 *
 * A DATASET RESOLVES CROSS-SHEET REFERENCES IN A CELL FORMULA. It already
 * resolves them in the other direction (a spreadsheet has read `Pipeline!A1`
 * since the workbook graph landed), a per-cell override is already the CELLULAR
 * escape hatch inside the columnar kind, and it is already bound by this module,
 * which is already workbook-wide. The boundary that actually exists between the
 * kinds is where the TYPE lives, and a cell override is on the cellular side of
 * it either way. Refusing only the outbound direction made the dataset the
 * lesser kind, which docs/dash-sheet-kinds.md says in as many words it is not.
 *
 * A COLUMN FORMULA STILL DOES NOT, and that refusal is `formula.ts`'s —
 * see `crossSheetRefusal` there for why a column expression reaching another
 * sheet is either a position that will move or a join with no key.
 *
 * `own` supplies the caller's already-computed column formulas for a sheet it
 * has painted, so they are not evaluated twice; every other sheet resolves
 * lazily and only if something reads it.
 */
export function recalcSheetCells(
  doc: { sheets?: Sheet[]; names?: Record<string, DefinedName>; modified?: string },
  sheetId: string,
  own?: (sheet: TableSheet) => Map<string, Vec> | undefined,
): CellRecalc {
  return recalcWorkbook(workbookSources(doc, own), doc.modified).get(sheetId)
    ?? { values: new Map(), cycles: [], order: [], spills: new Map() }
}

// --- the sheets themselves ---------------------------------------------------
//
// One `CellSource` per sheet KIND, so that the workbook a formula resolves
// against is assembled in one place rather than three. The grid, Find and the
// validator each built their own view of a dataset sheet before this, which was
// survivable while a formula could only see its own sheet and is not now: a
// reference across sheets means every sheet has to be addressable by whoever
// happens to be recalculating, including the one that is not on screen.

/** The canonical key of a spreadsheet cell, and the A1 spelling read as well. */
function posOf(key: string): { row: number; col: number } | null {
  const i = key.indexOf(',')
  if (i > 0) {
    const col = Number(key.slice(0, i))
    const row = Number(key.slice(i + 1))
    if (Number.isInteger(col) && Number.isInteger(row) && col >= 0 && row >= 0) return { row, col }
    return null
  }
  const r = parseRef(key)
  return r ? { row: r.row, col: r.col } : null
}

/**
 * A SPREADSHEET sheet (`kind: 'canvas'`) as a grid of positions.
 *
 * Keyed by `cellKey(row, col)` — what `setCanvasCells` writes (store.ts) — and
 * an A1 key is read too, because `preview.ts` and `validate.ts` were written
 * against that spelling and files exist with it. Reading both is tolerance at
 * the edge, not a second convention: nothing here ever writes a key.
 *
 * NOTHING IS SCANNED TWICE. The sparse map is walked ONCE, into the three
 * things a recalculation asks for — the cells, the formulas, and how far each
 * column reaches. Without that last index `SUM(A1:A100000)` on a sheet holding
 * three numbers would expand a hundred thousand references to find them, which
 * is the whole cost this kind exists to avoid.
 */
export function canvasCellSource(sheet: Pick<CanvasSheet, 'cells'>): CellSource {
  const cells = new Map<string, CanvasCell>()
  const formulas: Array<{ row: number; col: number; src: string }> = []
  /** column → the last row of it that holds anything */
  const reach = new Map<number, number>()
  let rows = 0
  let cols = 0

  for (const [key, cell] of Object.entries(sheet.cells ?? {})) {
    const p = posOf(key)
    // A key that names no position is left alone: it is somebody else's data or
    // a typo, and inventing a position for it would put a value on the sheet
    // that the file does not say is there. validate.ts reports it.
    if (!p || !cell) continue
    cells.set(cellKey(p.row, p.col), cell)
    if (p.row >= rows) rows = p.row + 1
    if (p.col >= cols) cols = p.col + 1
    const far = reach.get(p.col)
    if (far === undefined || p.row > far) reach.set(p.col, p.row)
    const f = cell.f
    if (typeof f === 'string' && f.trim() !== '') formulas.push({ row: p.row, col: p.col, src: f })
  }

  return {
    rows,
    cols,
    // THE SPREADSHEET KIND, and the only one. See the SPILL block above.
    spill: true,
    formulaAt: (r, c) => {
      const f = cells.get(cellKey(r, c))?.f
      return typeof f === 'string' && f.trim() !== '' ? f : undefined
    },
    valueAt: (r, c) => {
      const cell = cells.get(cellKey(r, c))
      // A cell holding only a formula stores no value: its number is computed,
      // and reading a stale `v` back would be the cache-that-looks-authoritative
      // failure the header warns about.
      return cell === undefined || cell.v === undefined ? null : (cell.v as Cell)
    },
    formulaCells: () => formulas,
    clipRange: (r) => {
      const c0 = Math.min(r.from.col, r.to.col)
      const c1 = Math.max(r.from.col, r.to.col)
      const r0 = Math.min(r.from.row, r.to.row)
      const r1 = Math.max(r.from.row, r.to.row)
      if (c0 < 0 || r0 < 0 || c0 >= cols || r0 >= rows) return null
      // How far down this BAND of columns anything reaches — not how far the
      // sheet reaches, so a stray cell in column Z costs column A nothing.
      let last = -1
      for (const [col, far] of reach) {
        if (col >= c0 && col <= c1 && far > last) last = far
      }
      if (last < r0) return null
      return {
        from: { col: c0, row: r0, absCol: false, absRow: false },
        to: {
          col: Math.min(c1, cols - 1),
          row: Math.min(r1, last),
          absCol: false,
          absRow: false,
        },
      }
    },
  }
}

/** Row index → rid, walking the run-length runs rather than expanding them. */
const ridAtRow = (sheet: TableSheet, row: number): number => {
  let seen = 0
  for (const [start, count] of sheet.rids) {
    if (row < seen + count) return start + (row - seen)
    seen += count
  }
  return -1
}

/** rid → row index. The inverse, and just as cheap. */
const rowOfRid = (sheet: TableSheet, rid: number): number => {
  let seen = 0
  for (const [start, count] of sheet.rids) {
    if (rid >= start && rid < start + count) return seen + (rid - start)
    seen += count
  }
  return -1
}

/**
 * A DATASET sheet (`kind: 'table'`) as a grid of positions, so `Pipeline!D2`
 * means what a reader plainly thinks it means: the cell two rows down the
 * fourth column of that table.
 *
 * Column ORDER is the sheet's own, hidden columns included. A reference is a
 * position and the position must not move because somebody hid a column — the
 * grid draws a subset, the file has all of them, and the file is what a formula
 * addresses.
 *
 * `computed` is that sheet's column formulas, already evaluated (formula.ts's
 * `recalc`). Without it a computed column reads as its stored value, which is
 * usually nothing at all.
 */
export function tableCellSource(
  sheet: TableSheet,
  computed?: Map<string, Vec> | (() => Map<string, Vec> | undefined),
): CellSource {
  const rows = sheet.rids.reduce((n, [, count]) => n + count, 0)
  const columns = sheet.columns
  // A FUNCTION is how a workbook says "only if somebody reads this sheet". A
  // workbook recalculates on every keystroke and most of its sheets are not
  // referenced by anything, so evaluating a 100k-row dataset's column formulas
  // to build a source nobody reads is the whole cost of making the graph
  // workbook-wide. Resolved at most once, here.
  let memo: Map<string, Vec> | undefined
  let asked = false
  const comp = (): Map<string, Vec> | undefined => {
    if (typeof computed !== 'function') return computed
    if (!asked) { asked = true; memo = computed() }
    return memo
  }
  return {
    rows,
    cols: columns.length,
    formulaAt: (r, c) => {
      const col = columns[c]
      if (!col) return undefined
      const f = sheet.cells?.[`${col.id}:${ridAtRow(sheet, r)}`]?.f
      return typeof f === 'string' && f.trim() !== '' ? f : undefined
    },
    valueAt: (r, c) => {
      const col = columns[c]
      if (!col) return null
      const over = sheet.cells?.[`${col.id}:${ridAtRow(sheet, r)}`]
      if (over && 'v' in over) return over.v as Cell
      // Only a COMPUTED column pays for the resolution. A plain stored column
      // is read straight out of the dictionary, which is what keeps a reference
      // into an ordinary dataset free.
      const vec = col.formula ? comp()?.get(col.id) : undefined
      return (vec ? vec[r] ?? null : readCell(sheet.data[col.id], r) as Cell)
    },
    formulaCells: () => {
      const out: Array<{ row: number; col: number; src: string }> = []
      const index = new Map(columns.map((c, i) => [c.id, i]))
      for (const [key, over] of Object.entries(sheet.cells ?? {})) {
        const f = over?.f
        if (typeof f !== 'string' || f.trim() === '') continue
        const i = key.indexOf(':')
        if (i < 0) continue
        const col = index.get(key.slice(0, i))
        const row = rowOfRid(sheet, Number(key.slice(i + 1)))
        // A formula whose column or row is gone is not a formula anywhere: it
        // has no position, so it computes nothing and is reported by the
        // validator rather than evaluated against a cell it does not occupy.
        if (col === undefined || row < 0) continue
        out.push({ row, col, src: f })
      }
      return out
    },
  }
}

/** The column names a formula on a dataset sheet may use, id and name alike. */
export function columnVectors(
  sheet: TableSheet,
  computed?: Map<string, Vec> | (() => Map<string, Vec> | undefined),
): Map<string, Vec> {
  const n = sheet.rids.reduce((a, [, c]) => a + c, 0)
  const resolved = typeof computed === 'function' ? computed() : computed
  const out = new Map<string, Vec>()
  const put = (k: string, v: Vec) => { out.set(k, v); out.set(k.toLowerCase(), v) }
  for (const c of sheet.columns) {
    const v = resolved?.get(c.id)
      ?? Array.from({ length: n }, (_, i) => readCell(sheet.data[c.id], i) as Cell)
    put(c.id, v)
    put(c.name, v)
  }
  return out
}

/**
 * A sheet whose cells exist but cannot be addressed — a pivot's numbers come
 * from a spec, not from positions.
 *
 * `#N/A` and not a blank. The sheet is plainly full of numbers on screen, so
 * "there is nothing there" would be a lie, and `=Pivot!B4*12` would report a
 * confident zero. `#N/A` says the value is not available, which is exactly the
 * situation.
 */
export const unaddressableSource = (why: string): CellSource => ({
  rows: 0,
  cols: 0,
  formulaAt: () => undefined,
  valueAt: () => null,
  formulaCells: () => [],
  clipRange: () => null,
  unavailable: why,
})

/**
 * Every sheet of a workbook, under the name a reference reaches it by.
 *
 * This is what turns `recalcWorkbook` from an interface into a feature: hand it
 * the document and cross-sheet references resolve. `computed` supplies a table
 * sheet's already-evaluated column formulas, because this module does not run
 * them — formula.ts's `recalc` does, and doing it again here would be a second
 * answer to the same question.
 *
 * Results come back keyed by SHEET ID, which the document keeps unique, rather
 * than by the name a reference uses to reach it, which it does not.
 */
export function workbookSources(
  doc: { sheets?: Sheet[]; names?: Record<string, DefinedName>; modified?: string },
  computed?: (sheet: TableSheet) => Map<string, Vec> | undefined,
): SheetSource[] {
  // The document's defined names, per sheet, with that sheet's own column
  // names removed — a column wins, see the DEFINED NAMES block in model.ts.
  // Only the column NAMES are read, never their values, so a workbook of
  // hundred-thousand-row datasets pays a set of strings and nothing else.
  const namesFor = (shadow?: ReadonlySet<string>): NameScope =>
    documentNames(doc.names, shadow)
  return (doc.sheets ?? []).map((s): SheetSource => {
    if (s.kind === 'table') {
      const t = s as TableSheet
      // THE CALLER'S CACHE FIRST, THEN OUR OWN, AND ONLY IF ASKED.
      //
      // `computed` exists because the sheet on screen has already been
      // recalculated by whoever is painting it, and running formula.ts's
      // `recalc` over it a second time would be a second answer to one
      // question. But every OTHER dataset in the workbook used to get
      // `undefined`, which meant a calculated column read as its STORED value —
      // usually nothing at all. So `=Sales!C2` into a calculated column
      // answered blank, and `=Sales!C2*1.2` answered a confident 0: the exact
      // error-becomes-a-zero failure this codebase refuses everywhere else.
      //
      // Falling back to a real recalculation closes that, and it is affordable
      // only because `tableCellSource` resolves this LAZILY — a workbook of
      // 100k-row datasets pays nothing for the ones no formula reaches, which
      // is nearly all of them, and pays once for the ones it does.
      const comp = () => computed?.(t) ?? (t.columns.some((c) => c.formula)
        ? recalc(t, doc.modified).values
        : undefined)
      const shadow = new Set<string>()
      for (const c of t.columns) {
        shadow.add(c.id.toLowerCase())
        shadow.add(c.name.toLowerCase())
      }
      return {
        id: t.id,
        name: t.name,
        source: tableCellSource(t, comp),
        vectors: () => columnVectors(t, comp),
        kind: 'dataset',
        names: namesFor(shadow),
      }
    }
    if (s.kind === 'canvas') {
      // A spreadsheet has no columns to shadow anything: nothing is named but
      // the cells, and a cell address can never be a defined name.
      return {
        id: s.id,
        name: s.name,
        source: canvasCellSource(s as CanvasSheet),
        names: namesFor(),
        kind: 'spreadsheet',
      }
    }
    return {
      id: s.id,
      name: s.name,
      source: unaddressableSource(
        `the cells of ${s.kind} sheet "${s.name}" are derived and cannot be referenced by position`,
      ),
    }
  })
}


/** A computed value as the grid should show it. Errors print as their code. */
export const displayCell = (v: Cell): string =>
  v === null || v === undefined ? '' : isErr(v) ? String(v) : String(v)

export const _internals = { formatRef, ERR_REF, ERR_BIG, ERR_CYCLE }

// --- keeping references pointing at the right cells --------------------------
//
// The two halves of the problem a1.ts's header sets out, wired to the two
// events that cause them. They are DIFFERENT rules and the difference is the
// thing people get wrong:
//
//   COPY/FILL   the formula moved, the cells did not. References move WITH it,
//               except the `$`-pinned ones. `=A1*2` copied a row down is
//               `=A2*2` — that is the whole point of copying a formula.
//   INSERT/DEL  the CELLS moved, the formula did not. Every reference moves,
//               `$` included, because the cell it names physically moved. A
//               reference INTO a deleted row becomes `#REF!`, never the row
//               that slid up into the gap — a reference silently re-pointed at
//               someone else's data is a wrong number wearing a right one's
//               clothes.

/**
 * A formula moved by (dRow, dCol) — copy, paste and fill.
 *
 * Returns the source unchanged when it holds no references, so a workbook of
 * constants pays nothing.
 */
export function translateCellFormula(src: string, dRow: number, dCol: number): string {
  if (!isFormula(src) || (dRow === 0 && dCol === 0)) return src
  return `=${rewriteFormulaRefs(formulaBody(src), dRow, dCol)}`
}

/**
 * Every cell formula in a sheet, rewritten because `count` rows or columns were
 * inserted at 0-based index `at` (or removed, when `count` is negative).
 *
 * Returns the keys whose source CHANGED, and their new text. Rewriting the
 * unchanged ones too would work and would also put the whole sheet's formulas
 * into one undo step's inverse for an edit that touched three of them.
 *
 * `scope` is how a workbook says WHICH sheet the rows were inserted into, so
 * that the formulas on every OTHER sheet can be rewritten by the same call: a
 * reference is moved only when it points at the sheet that changed shape. With
 * no scope the edit is taken to be on the sheet whose formulas these are, which
 * is what the single-sheet callers have always meant.
 */
export function shiftSheetFormulas(
  formulas: Iterable<[string, string]>,
  axis: 'row' | 'col',
  at: number,
  count: number,
  scope?: ShiftScope,
): Array<[string, string]> {
  const out: Array<[string, string]> = []
  for (const [key, src] of formulas) {
    if (!isFormula(src)) continue
    const next = `=${shiftRefsForInsert(formulaBody(src), axis, at, count, scope)}`
    if (next !== src) out.push([key, next])
  }
  return out
}