Skip to content

armgit / bento

Public Imported from GitHub
0

Bento, the office suite that fits in a file

59.4 KB
Raw Blame
// SPDX-License-Identifier: MIT
// Copyright (c) 2026 The Bento authors
// The STEP ENGINE — the relational pipeline the format has described since
// commit one, and which until now nothing executed.
//
// `TableSheet.steps` says how the numbers were arrived at:
//
//     import | bind | type | filter | derive | sort | group | join | union
//           | pivot | unpivot | limit | patch
//
// That is SQL's shape, already in the file, already collaborative, already
// undoable — and `applySteps` in store.ts threw "not implemented yet" while the
// grid's filtering and sorting were VIEW state that never touched it. This
// module closes that gap. docs/dash-sql.md then compiles SQL to `Step[]` and
// hands it here; that surface is step two and this is step one, owed regardless.
//
// THE ROW REPRESENTATION IS AN INDEX VECTOR, AND THAT IS THE WHOLE DESIGN.
// A `filter` does not copy a column and does not build row objects: it produces
// an `Int32Array` of positions, and every step downstream indexes through it.
// The concepting measured why — 1M `{v, f}` cell objects cost 44 MB of heap
// against 8 bytes per cell for a typed array — and the budgets this has to hit
// are stated in bytes-per-row terms it cannot reach any other way (single
// threaded, from `file://`, 10,000,000 rows: full scan sum 5.9 ms, filter + sum
// 10.6 ms, two-dimension group-by 11.5 ms, top-100 8.9 ms). A row-shaped
// pipeline is not a slower version of this; it is a different product.
//
// So there are exactly four allocations in this file that scale with rows:
//
//   1. the BASE materialisation of a column, once per column per source, cached
//      on the source and shared by every frame that descends from it;
//   2. an `Int32Array` per step that changes which rows are in play — one entry
//      per row that SURVIVES, not per row considered;
//   3. one BYTE per row while a filter is deciding, freed when it has decided;
//   4. a TRANSIENT gather of a referenced column, and only when the frame has
//      shrunk far enough that gathering beats reading the source through the
//      index vector (see `evalRowwise`) — one column, dropped when the step ends.
//
// Nothing here retains a per-step copy of a column. `_internals.stats` counts
// all four, so scripts/test-dash-steps.ts PROVES it: twenty chained filters over
// 100,000 rows gather zero cells and retain zero, and the engine holds 2.5 MB
// where the same answer computed row-shaped holds 16.8 MB.
//
// ONE EXPRESSION LANGUAGE. `filter.where` and `derive.expr` go through
// formula.ts's `evaluate` — the same 91 functions, the same coercions, the same
// visible errors — so `SUM` in a step means what `SUM` in a cell means. There
// is no second dialect here and there must never be one; `dependencies()`
// tells us which columns an expression touches so only those are materialised.
//
// ERRORS ARE VISIBLE, NEVER ZERO. formula.ts's rule, inherited whole. A row
// whose predicate could not be evaluated is DROPPED AND COUNTED, never silently
// swept; a predicate that failed on EVERY row halts the pipeline, because
// "no rows matched" and "your column name is misspelt" look identical on screen
// and only one of them is true.
//
// AND THE REFUSAL THIS ENGINE EXISTS TO MAKE: `join-fanout`. A join whose
// declared cardinality the data contradicts silently multiplies every measure
// downstream, and that failure has been printing confidently doubled totals in
// production tooling for a decade. dash holds the declaration (`Step.join.card`),
// so it can check it. It checks it, and it REFUSES — it does not produce the
// doubled total with a warning beside it.

import type {
  CellOverride, Column, ColumnData, ColumnType, DashDoc, Sheet, Step, TableSheet,
} from './model.ts'
import { readCell } from './store.ts'
import { compare, isBlank } from './filter.ts'
import { planSplit, type SplitSpec } from './tocolumns.ts'
import { dependencies, evaluate, isErr, recalc, type Cell, type EvalCtx, type Vec } from './formula.ts'

// --- what a step run reports --------------------------------------------------
//
// FINDINGS, NOT EXCEPTIONS — validate.ts's shape (validate.ts:59) and for the
// same reason: the caller decides what to show, and `showFindings` renders a
// `{code, severity, message}` without a translation layer. Nothing in this file
// throws at the caller; a throw from deeper down (a packed column, a malformed
// step) is caught and converted into a `fatal` finding naming the step.

export type StepSeverity =
  /** the pipeline stopped here. There is no result to show, and that is the point. */
  | 'fatal'
  /** this build cannot run the step. Show the last known values with a badge,
   *  NEVER zero — an empty bar chart reads as ZERO, which is a number, which is
   *  a lie (model.ts:183). */
  | 'unresolved'
  /** it ran, and something about it deserves a reader's attention. */
  | 'suspicious'

export interface StepIssue {
  /** stable machine-readable code, e.g. 'join-fanout' */
  code: string
  severity: StepSeverity
  /** one line, actionable on its own — it must name WHICH step and WHAT. */
  message: string
  /** index into the step list */
  at?: number
  op?: string
  column?: string
  /** rows affected, when a count is what makes the finding legible */
  rows?: number
}

/** Steps that are PROVENANCE: they record where data came from and are never
 *  re-run by recalculation (model.ts:156). Exported because store.ts's
 *  `applySteps` has to know where the re-executable tail begins, and two
 *  definitions of that seam is how a patch and its inverse drift apart. */
export const PROVENANCE_OPS: ReadonlySet<string> = new Set(['import', 'bind'])

/** Steps whose effect is already in the sheet's own bytes by the time the
 *  pipeline runs, so re-running them here would apply them twice.
 *  `type` coerced at import and wrote `Column.type`/`failed`; `patch` wrote the
 *  hand corrections into `cells`. They are carried for lineage, not replay. */
const SETTLED_OPS: ReadonlySet<string> = new Set(['type', 'patch'])

/** Declared in the format and deliberately NOT in this cut. Saying so is the
 *  point: a half-implemented pivot that silently drops a dimension is worse
 *  than one that refuses. */
const DEFERRED_OPS: ReadonlySet<string> = new Set(['pivot', 'unpivot'])

// --- the column store ---------------------------------------------------------

/**
 * A source: the columns of one sheet, materialised ONCE and shared by every
 * frame descended from it.
 *
 * `vec` is lazy and memoised, so a pipeline that filters on one column of a
 * forty-column sheet materialises one column. That is not an optimisation, it
 * is the difference between opening the file and not.
 */
export interface Source {
  /** sheet id, for lineage and for naming joined columns */
  id: string
  name: string
  /** rows in the source, before any step */
  n: number
  columns: Column[]
  /** colId → dense values, length `n`. Memoised. Throws on a packed column. */
  vec(colId: string): Vec | undefined
}

/**
 * A frame: a source, plus WHICH of its rows are in play and in what order.
 *
 * `rows === null` means "every row of the source, in order" — the identity
 * frame, which costs nothing and which lets the first `filter` in a pipeline
 * read the source's own vector with no copy at all.
 *
 * `derived` holds columns a `derive` step computed. They are in FRAME space
 * (one value per frame position), because they exist only for this frame;
 * source columns are in SOURCE space and are reached through `rows`.
 */
export interface Frame {
  src: Source
  rows: Int32Array | null
  n: number
  /** metadata for every column visible here, in order */
  columns: Column[]
  /** colId → values in FRAME space, for columns this frame computed */
  derived: Map<string, Vec>
}

export interface StepResult {
  /** false when a step refused or could not be run */
  ok: boolean
  /** the last frame produced. ON REFUSAL this is the frame BEFORE the failing
   *  step — never a partial or a fabricated one. */
  frame: Frame
  /** how many steps ran to completion */
  ran: number
  issues: StepIssue[]
  /** a step this build cannot execute stopped the run (unknown op, pivot) */
  unresolved: boolean
}

export interface RunOpts {
  /** for `join` and `union`, which name another sheet */
  doc?: DashDoc
  /** override sheet lookup (id first, then name) — the SQL surface will want
   *  to resolve a CTE name to a frame it built rather than to a saved sheet */
  sheets?: (ref: string) => TableSheet | undefined
  /** frozen `TODAY()`/`NOW()`, exactly as `recalc` takes it */
  now?: string
}

// --- allocation accounting ----------------------------------------------------
//
// The performance claim in this file's header is checkable, so it is CHECKED.
// These counters are how scripts/test-dash-steps.ts proves the pipeline is
// index-shaped instead of taking its word for it: a row-object implementation
// cannot keep `gatherCells` sublinear in the number of steps, and a
// column-copying one cannot keep `retainedCells` at zero.

const stats = {
  /** cells materialised from the SHEET — the unavoidable base cost, once per column */
  sourceCells: 0,
  /** Int32Array entries allocated by steps that change the row set */
  indexCells: 0,
  /** cells gathered TRANSIENTLY to evaluate an expression; garbage after the step */
  gatherCells: 0,
  /** one byte per row while a filter decides — transient, and a quarter of what
   *  a full-width candidate vector would cost */
  maskBytes: 0,
  /** cells a step RETAINED in a frame: derived columns and group/union output.
   *  A filter, a sort and a limit must never move this. */
  retainedCells: 0,
  frames: 0,
}
const resetStats = (): void => {
  stats.sourceCells = 0; stats.indexCells = 0; stats.gatherCells = 0
  stats.retainedCells = 0; stats.frames = 0; stats.maskBytes = 0
}

// --- values -------------------------------------------------------------------

/**
 * The digit shape a string must have to be READ as a number.
 *
 * The THIRD copy of this rule (filter.ts:112, pivot.ts:260), and copied for the
 * same reason pivot.ts states: filter.ts does not export it. It is copied
 * rather than loosened — `Number('')` is 0, which is how a blank becomes a
 * zero, and a percent column stores the FRACTION so reading "50%" as 50 is
 * wrong by a factor of a hundred.
 *
 * Used ONLY for grouping keys and sort order, where it must agree with the
 * filter menu and the pivot or the same click gives two answers. Aggregate
 * ARITHMETIC deliberately does not use it — see `aggregate` below, which is
 * formula.ts's rule so that SUM means one thing in this app.
 *
 * IF filter.ts EVER EXPORTS `asNumber`, TAKE IT AND DELETE THIS.
 */
const NUMERIC = /^[+-]?(?:(?:\d{1,3}(?:,\d{3})+|\d+)(?:\.\d+)?|\.\d+)$/

function asNumber(v: unknown): number | null {
  if (typeof v === 'number') return Number.isFinite(v) ? v : null
  if (typeof v === 'boolean') return v ? 1 : 0
  if (typeof v !== 'string') return null
  const s = v.trim()
  if (s === '' || !NUMERIC.test(s)) return null
  const n = Number(s.replace(/,/g, ''))
  return Number.isFinite(n) ? n : null
}

/**
 * The ONE canonical group key — pivot.ts:277's, deliberately identical.
 *
 * Two values collapse into one group here exactly when they collapse into one
 * checkbox in the filter menu and one row in a pivot. A reader who ticks
 * "North" in the filter, sees "North" in the pivot and groups by region in a
 * step is looking at the same set of rows all three times, or the app has three
 * opinions about what a category is.
 */
function matchKey(v: unknown): string {
  if (isBlank(v)) return ' blank'
  const n = asNumber(v)
  return n === null ? `t:${String(v).trim().toLowerCase()}` : `n:${n}`
}

/**
 * Build a source from a table sheet.
 *
 * Formula columns come from `recalc`, computed once on first demand and in
 * dependency order — the alternative is a step reading a formula column's stale
 * values, which is the right shape and the wrong numbers.
 *
 * Cell OVERRIDES are applied. They are the hand corrections somebody made to
 * imported data, and a pipeline that ignored them would total the numbers the
 * author already said were wrong. Per-cell FORMULAS (`CellOverride.f`) are
 * cellformula.ts's and are not evaluated here; the stored `v` beside them is.
 */
export function sourceOf(sheet: TableSheet): Source {
  const n = sheet.rids.reduce((a, [, c]) => a + c, 0)
  const byId = new Map<string, Column>()
  for (const c of sheet.columns) byId.set(c.id, c)

  const cache = new Map<string, Vec>()
  let computed: Map<string, Vec> | null = null

  /** rid → row position, built ONLY when there are overrides to place. At 10M
   *  rows this map is expensive and almost always unnecessary. */
  let ridRow: Map<number, number> | null = null
  const rowOfRid = (rid: number): number => {
    if (!ridRow) {
      ridRow = new Map()
      let i = 0
      for (const [start, count] of sheet.rids) {
        for (let k = 0; k < count; k++) ridRow.set(start + k, i++)
      }
    }
    return ridRow.get(rid) ?? -1
  }

  const applyOverrides = (colId: string, out: Vec): void => {
    const cells = sheet.cells
    if (!cells) return
    const prefix = `${colId}:`
    for (const key of Object.keys(cells)) {
      if (!key.startsWith(prefix)) continue
      const o = cells[key] as CellOverride
      if (!o || !('v' in o)) continue
      const row = rowOfRid(Number(key.slice(prefix.length)))
      if (row >= 0 && row < n) out[row] = o.v as Cell
    }
  }

  return {
    id: sheet.id,
    name: sheet.name,
    n,
    columns: sheet.columns,
    vec(colId: string): Vec | undefined {
      const hit = cache.get(colId)
      if (hit) return hit
      const col = byId.get(colId)
      if (!col) return undefined
      let out: Vec
      if (col.formula) {
        if (!computed) computed = recalc(sheet, undefined).values
        out = computed.get(colId) ?? new Array<Cell>(n).fill(null)
      } else {
        const d: ColumnData | undefined = sheet.data[colId]
        // `pack` is an opaque archive encoding and `readCell` answers null for
        // every row of one (store.ts:274). Running a pipeline through that
        // gives one "(blank)" group holding the whole sheet and a grand total
        // of nothing — a wrong answer with no symptom. rowcol.ts refuses packed
        // columns for edits and pivot.ts for reads; this refuses them for steps.
        if (d && d.enc === 'pack') {
          throw new Error(`column "${col.name || colId}" is packed and cannot be stepped over — promote it to raw first`)
        }
        out = new Array<Cell>(n)
        for (let i = 0; i < n; i++) out[i] = readCell(d, i) as Cell
      }
      applyOverrides(colId, out)
      stats.sourceCells += n
      cache.set(colId, out)
      return out
    },
  }
}

/** The whole sheet, unfiltered and in order. Costs one object. */
export function frameOf(src: Source): Frame {
  stats.frames++
  return { src, rows: null, n: src.n, columns: src.columns.slice(), derived: new Map() }
}

/** Resolve a column reference — id first, then name, then either case-folded. */
export function columnOf(frame: Frame, ref: string): Column | undefined {
  const lower = ref.toLowerCase()
  let byName: Column | undefined
  let byFold: Column | undefined
  for (const c of frame.columns) {
    if (c.id === ref) return c
    if (!byName && c.name === ref) byName = c
    if (!byFold && (c.id.toLowerCase() === lower || (c.name ?? '').toLowerCase() === lower)) byFold = c
  }
  return byName ?? byFold
}

/**
 * The values of one column IN FRAME ORDER.
 *
 * THE IDENTITY CASE RETURNS THE SOURCE'S OWN ARRAY — not a copy, not a view,
 * the same object. That is the property the whole design rests on, and the rig
 * asserts it with `===` rather than believing this comment.
 *
 * When the frame is a subset the values are GATHERED, and that gather is
 * transient by design: it is not cached on the frame, so a twenty-step pipeline
 * does not retain twenty copies of a column. `evalRowwise` avoids it entirely
 * for the ordinary predicate — see there, because a gather per step is exactly
 * the cost this file exists to not pay.
 */
export function values(frame: Frame, ref: string): Vec | undefined {
  const col = columnOf(frame, ref)
  if (!col) return undefined
  const own = frame.derived.get(col.id)
  if (own) return own
  const base = frame.src.vec(col.id)
  if (!base) return undefined
  if (frame.rows === null) return base
  const rows = frame.rows
  const out = new Array<Cell>(frame.n)
  for (let i = 0; i < frame.n; i++) out[i] = base[rows[i]] ?? null
  stats.gatherCells += frame.n
  return out
}

/**
 * A child frame holding `pos` — positions IN THE PARENT'S FRAME SPACE.
 *
 * One helper for filter, sort, limit and the fanout side of join, because they
 * differ only in how they choose `pos`. Source columns re-index for free (the
 * index vector composes); derived columns are gathered, because they are
 * genuinely this pipeline's own data and live nowhere else.
 *
 * `pos` MAY BE CONSUMED — composed into source space in place. Every caller
 * allocates it fresh for this call, and the alternative is a second index
 * vector per step for no gain.
 */
function reindex(frame: Frame, pos: Int32Array): Frame {
  let rows: Int32Array
  if (frame.rows === null) {
    // Frame positions ARE source rows here, so the index vector is already right.
    rows = pos
  } else if (frame.derived.size === 0) {
    const parent = frame.rows
    for (let i = 0; i < pos.length; i++) pos[i] = parent[pos[i]]
    rows = pos
  } else {
    // Derived columns are addressed by FRAME position, so `pos` has to survive
    // the gather below; compose into a second vector instead.
    rows = new Int32Array(pos.length)
    for (let i = 0; i < pos.length; i++) rows[i] = frame.rows[pos[i]]
    stats.indexCells += pos.length
  }
  const derived = new Map<string, Vec>()
  for (const [k, v] of frame.derived) {
    const out = new Array<Cell>(pos.length)
    for (let i = 0; i < pos.length; i++) out[i] = v[pos[i]] ?? null
    stats.retainedCells += pos.length
    derived.set(k, out)
  }
  stats.frames++
  return { src: frame.src, rows, n: pos.length, columns: frame.columns.slice(), derived }
}

/** An expression's context: ONLY the columns it names get materialised. */
function ctxFor(frame: Frame, src: string, now?: string): EvalCtx {
  const cols = new Map<string, Vec>()
  for (const ref of dependencies(src)) {
    const v = values(frame, ref)
    if (!v) continue
    cols.set(ref, v)
    cols.set(ref.toLowerCase(), v)
  }
  return { cols, n: frame.n, now }
}

/**
 * An expression's values, evaluated the cheap way when the cheap way is
 * IDENTICAL.
 *
 * The problem this solves is the whole performance story of a filter chain. A
 * frame that is a subset has to hand its columns to `evaluate` in FRAME order,
 * which means gathering them — and a gather per step is a column copy per step,
 * which is precisely the shape this file promises not to have.
 *
 * A ROW-WISE expression does not need frame order. `value > 60` gives the same
 * answer for row 4,000 whether or not rows 1 to 3,999 are still in play, so it
 * can be evaluated over the SOURCE's own arrays — which are already
 * materialised and shared — and read back through the index vector. No gather,
 * no allocation, no copy, at any depth of chaining.
 *
 * WHAT MAKES AN EXPRESSION ROW-WISE HERE: it contains no `(`. That is a blunt
 * test and a deliberately conservative one — it is not trying to be clever, it
 * is trying to be UNABLE to be wrong. `SUM(value)`, `AVERAGE(value)`,
 * `COUNTIF(...)` and every other whole-column function must see the frame and
 * only the frame (a `HAVING`-shaped filter is exactly that), and all of them
 * need a bracket to be written. An expression with a bracket in a string
 * literal takes the slow path for nothing, which costs a gather and never costs
 * an answer.
 *
 * The other two guards: a DERIVED column exists only in frame space, and a
 * frame that has shrunk to a fraction of its source is cheaper to gather than
 * to evaluate whole. Both fall back, and falling back is always correct.
 */
interface Evaluated {
  out: Vec
  /** true when `out` is indexed by SOURCE row rather than by frame position */
  sourceSpace: boolean
}

function evalRowwise(frame: Frame, src: string, now?: string): Evaluated {
  const rows = frame.rows
  if (rows !== null && !src.includes('(') && frame.n * 2 >= frame.src.n) {
    const cols = new Map<string, Vec>()
    let usable = true
    for (const ref of dependencies(src)) {
      const c = columnOf(frame, ref)
      if (c && frame.derived.has(c.id)) { usable = false; break }
      const v = c ? frame.src.vec(c.id) : undefined
      if (!v) continue // an unknown name errors identically on either path
      cols.set(ref, v)
      cols.set(ref.toLowerCase(), v)
    }
    if (usable) return { out: evaluate(src, { cols, n: frame.src.n, now }), sourceSpace: true }
  }
  return { out: evaluate(src, ctxFor(frame, src, now)), sourceSpace: false }
}

// --- the steps ----------------------------------------------------------------

/** What a step handler answers with. A `fatal` or `unresolved` issue stops the run. */
interface StepOut {
  frame?: Frame
  issues?: StepIssue[]
}

const issue = (
  code: string, severity: StepSeverity, message: string, extra: Partial<StepIssue> = {},
): StepIssue => ({ code, severity, message, ...extra })

/**
 * `filter` — a predicate over the frame, producing an INDEX VECTOR.
 *
 * TWO REFUSALS LIVE HERE, and they are the difference between a filter and a
 * disappearance:
 *
 *   - a predicate that errored on EVERY row is FATAL. `region = "Nort"` matching
 *     nothing and `regoin = "North"` matching nothing look identical on screen
 *     — an empty grid — and only one of them is the data's fault.
 *   - a predicate that errored on SOME rows drops them and SAYS SO. Those rows
 *     are not a matter of opinion; they are rows the pipeline could not judge,
 *     and a total computed without them is short by an amount nobody can see.
 */
function stepFilter(frame: Frame, step: { where?: unknown }, at: number, now?: string): StepOut {
  const where = typeof step.where === 'string' ? step.where : ''
  if (!where.trim()) {
    return { issues: [issue('filter-empty', 'suspicious', `Step ${at + 1} is a filter with no condition, so it kept every row.`, { at, op: 'filter' })] }
  }
  const { out, sourceSpace } = evalRowwise(frame, where, now)
  const rows = frame.rows
  // ONE BYTE PER ROW while deciding, then ONE Int32Array of exactly the rows
  // that survived. Writing candidates into a full-width Int32Array first costs
  // four times the transient memory for a filter that keeps a tenth of the rows.
  const mask = new Uint8Array(frame.n)
  stats.maskBytes += frame.n
  let k = 0
  let errors = 0
  for (let i = 0; i < frame.n; i++) {
    const v = (sourceSpace ? out[rows![i]] : out[i]) ?? null
    if (isErr(v)) { errors++; continue }
    // A blank is not a match. Excel's rule, SQL's rule, and the only one that
    // does not turn an empty cell into a silent yes.
    if (v === false || v === null || v === '' || v === 0) continue
    mask[i] = 1
    k++
  }
  if (errors === frame.n && frame.n > 0) {
    const why = out.length ? String(out[0]) : '#VALUE!'
    return {
      issues: [issue('filter-unresolved', 'fatal',
        `Step ${at + 1}: the condition ${JSON.stringify(where)} could not be evaluated on any row (${why}). That is not an empty result — it is a condition this workbook cannot answer, so the pipeline stopped rather than show you nothing and call it data.`,
        { at, op: 'filter', rows: frame.n })],
    }
  }
  const issues: StepIssue[] = []
  if (errors) {
    issues.push(issue('filter-errors', 'suspicious',
      `Step ${at + 1}: ${errors} row(s) were dropped because ${JSON.stringify(where)} could not be evaluated on them. Anything totalled below is short by those rows.`,
      { at, op: 'filter', rows: errors }))
  }
  // Everything survived: hand back the SAME frame. A filter that filters
  // nothing should cost nothing.
  if (k === frame.n) return { frame, issues }
  const pos = new Int32Array(k)
  stats.indexCells += k
  let w = 0
  for (let i = 0; i < frame.n; i++) if (mask[i]) pos[w++] = i
  return { frame: reindex(frame, pos), issues }
}

/** `derive` — one expression, one new column, one vectorised pass. */
function stepDerive(
  frame: Frame,
  step: { col?: unknown; name?: unknown; expr?: unknown; type?: unknown; unit?: unknown },
  at: number,
  now?: string,
): StepOut {
  const expr = typeof step.expr === 'string' ? step.expr : ''
  const id = typeof step.col === 'string' && step.col ? step.col : ''
  const name = typeof step.name === 'string' && step.name ? step.name : id
  if (!id || !expr.trim()) {
    return {
      issues: [issue('derive-incomplete', 'fatal',
        `Step ${at + 1} is a derive without ${!id ? 'a column id' : 'an expression'}, so there is nothing to compute.`,
        { at, op: 'derive' })],
    }
  }
  const out = evaluate(expr, ctxFor(frame, expr, now))
  const vals: Vec = new Array<Cell>(frame.n)
  let errors = 0
  for (let i = 0; i < frame.n; i++) {
    const v = out[i] ?? null
    if (isErr(v)) errors++
    vals[i] = v
  }
  stats.retainedCells += frame.n
  const derived = new Map(frame.derived)
  derived.set(id, vals)
  const columns = frame.columns.filter((c) => c.id !== id)
  columns.push({
    id,
    name,
    type: (typeof step.type === 'string' ? step.type : inferType(vals)) as ColumnType,
    ...(typeof step.unit === 'string' ? { unit: step.unit } : {}),
  } as Column)
  stats.frames++
  const next: Frame = { src: frame.src, rows: frame.rows, n: frame.n, columns, derived }
  const issues: StepIssue[] = []
  if (errors) {
    // NOT fatal, and not silently zeroed: the error cells stay in the column so
    // a reader sees #NAME? where a number should be. formula.ts's rule.
    issues.push(issue(errors === frame.n ? 'derive-unresolved' : 'derive-errors', 'suspicious',
      `Step ${at + 1}: ${JSON.stringify(expr)} could not be computed on ${errors} of ${frame.n} row(s); those cells read as an error rather than as a number.`,
      { at, op: 'derive', column: id, rows: errors }))
  }
  return { frame: next, issues }
}

/**
 * `split` — one text column into several. Text to Columns, as a declaration.
 *
 * Three things make it an op rather than N `derive`s, and they are argued in
 * full in tocolumns.ts's header: there is no SPLIT in the expression language,
 * the delimiter must live in ONE place rather than N that can disagree, and the
 * output types have to come from import.ts's whole-column inference — which
 * REFUSES on an ambiguous date column — rather than from `derive`'s per-value
 * guess.
 *
 * THE SOURCE COLUMN SURVIVES. Excel replaces it with field one; that makes the
 * step non-idempotent, and a step that has eaten its own input cannot be
 * re-run, which is the entire point of putting it in the pipeline. Running this
 * pipeline twice produces the same frame.
 */
function stepSplit(
  frame: Frame,
  step: { col?: unknown; by?: unknown; widths?: unknown; into?: unknown; quoted?: unknown; trim?: unknown },
  at: number,
): StepOut {
  const ref = typeof step.col === 'string' ? step.col : ''
  const into = Array.isArray(step.into)
    ? (step.into as unknown[]).filter((t): t is { id: string; name: string } =>
      !!t && typeof (t as { id?: unknown }).id === 'string' && (t as { id: string }).id !== '')
      .map((t) => ({ id: t.id, name: typeof t.name === 'string' && t.name ? t.name : t.id }))
    : []
  const widths = Array.isArray(step.widths)
    ? (step.widths as unknown[]).filter((n): n is number => typeof n === 'number') : []
  const spec: SplitSpec = {
    ...(widths.length ? { widths } : { by: typeof step.by === 'string' ? step.by : '' }),
    ...(step.quoted === false ? { quoted: false } : {}),
    ...(step.trim === false ? { trim: false } : {}),
  }
  if (!ref || !into.length || (!widths.length && !spec.by)) {
    return {
      issues: [issue('split-incomplete', 'fatal',
        `Step ${at + 1} is a split without ${!ref ? 'a column' : !into.length ? 'any output columns' : 'a delimiter or widths'}, so there is nothing to cut.`,
        { at, op: 'split' })],
    }
  }
  const col = columnOf(frame, ref)
  const src = values(frame, ref)
  if (!col || !src) {
    return {
      issues: [issue('split-no-column', 'fatal',
        `Step ${at + 1} splits ${JSON.stringify(ref)}, and this sheet has no such column.`,
        { at, op: 'split', column: ref })],
    }
  }
  // ONE plan for the app and the pipeline. The grid's Text to Columns command
  // calls `planSplit` directly to write the columns into a base sheet's bytes;
  // if this re-derived them a second way the two would drift, and the drift
  // would show up as a re-run changing a column nobody edited.
  const plan = planSplit(src.slice(0, frame.n), spec, into)
  const derived = new Map(frame.derived)
  plan.columns.forEach((c, i) => {
    derived.set(c.id, plan.values[i] as Vec)
    stats.retainedCells += frame.n
  })
  const made = new Set(plan.columns.map((c) => c.id))
  const columns = frame.columns.filter((c) => !made.has(c.id)).concat(plan.columns)
  stats.frames++
  const issues = plan.findings.map((f) => issue(f.code, 'suspicious',
    `Step ${at + 1}: ${f.message}`, { at, op: 'split', column: f.column }))
  return { frame: { src: frame.src, rows: frame.rows, n: frame.n, columns, derived }, issues }
}

function inferType(vals: Vec): ColumnType {
  let seen = false
  for (let i = 0; i < vals.length; i++) {
    const v = vals[i]
    if (v == null || v === '' || isErr(v)) continue
    seen = true
    if (typeof v !== 'number') return typeof v === 'boolean' ? 'bool' : 'text'
  }
  return seen ? 'number' : 'text'
}

/**
 * `sort` — a permutation of the index vector, and no column moves.
 *
 * Ordering is filter.ts's `compare`, so a step-sorted result and a
 * column-header sort put the rows in the SAME order. Two orderings of one
 * column is how a story step and a grid come to show different top tens.
 *
 * The comparator TIE-BREAKS ON POSITION, which makes the order total. Stability
 * is then a property of the comparator rather than of whichever sort the engine
 * happens to use, so `group` after `sort` is reproducible everywhere.
 */
function stepSort(frame: Frame, step: { by?: unknown; dir?: unknown }, at: number): StepOut {
  const by = typeof step.by === 'string' ? step.by : ''
  const vals = by ? values(frame, by) : undefined
  if (!vals) {
    return {
      issues: [issue('sort-missing-column', 'fatal',
        `Step ${at + 1} sorts by ${JSON.stringify(by)}, which is not a column here. Sorting by nothing would leave the rows in an order that only looks deliberate.`,
        { at, op: 'sort', column: by })],
    }
  }
  const pos = new Int32Array(frame.n)
  for (let i = 0; i < frame.n; i++) pos[i] = i
  stats.indexCells += frame.n
  pos.sort(sortComparator(vals, step.dir === 'desc'))
  return { frame: reindex(frame, pos) }
}

/**
 * The comparator, as its own function so its one load-bearing property is
 * TESTABLE: it is a TOTAL order — it returns 0 only when comparing a position
 * with itself.
 *
 * That is what makes the sort stable, and it makes it stable BY CONSTRUCTION
 * rather than by relying on the engine's sort being stable. %TypedArray%.sort
 * has been required to be stable since ES2019, so the difference is invisible
 * on a conformant engine and a rig cannot catch its removal by sorting — which
 * is exactly why the property is asserted on the comparator directly.
 */
function sortComparator(vals: Vec, desc: boolean): (a: number, b: number) => number {
  const sign = desc ? -1 : 1
  return (a, b) => {
    const c = compare(vals[a] ?? null, vals[b] ?? null)
    return c !== 0 ? c * sign : a - b
  }
}

/** `limit` — a window of the index vector. Top-100 of ten million rows is this. */
function stepLimit(frame: Frame, step: { n?: unknown; offset?: unknown }, at: number): StepOut {
  const want = typeof step.n === 'number' && Number.isFinite(step.n) ? Math.max(0, Math.floor(step.n)) : -1
  const off = typeof step.offset === 'number' && Number.isFinite(step.offset) ? Math.max(0, Math.floor(step.offset)) : 0
  if (want < 0) {
    return {
      issues: [issue('limit-missing-n', 'fatal',
        `Step ${at + 1} is a limit with no row count.`, { at, op: 'limit' })],
    }
  }
  const start = Math.min(off, frame.n)
  const end = Math.min(start + want, frame.n)
  if (start === 0 && end === frame.n) return { frame }
  const pos = new Int32Array(end - start)
  for (let i = 0; i < pos.length; i++) pos[i] = start + i
  stats.indexCells += pos.length
  return { frame: reindex(frame, pos) }
}

// --- aggregation --------------------------------------------------------------
//
// ONE MEANING FOR SUM. The aggregate names in `Step.group.agg` dispatch to
// formula.ts, so `{fn:'sum'}` in a step and `=SUM(col)` in a cell produce the
// same number on the same column — including on the awkward inputs, which is
// where two implementations diverge and where the divergence is invisible.
//
// The five hot ones are open-coded because a group-by over ten million rows
// cannot afford `evaluate` per group; they reproduce formula.ts's range reading
// (`rangeNumber`) EXACTLY rather than approximately, and scripts/test-dash-steps.ts
// cross-checks every one of them against `evaluate` on adversarial data. If
// that rig ever fails, this fast path is wrong and formula.ts is right.
//
// Everything else — MEDIAN, STDEV, PRODUCT, COUNTUNIQUE, MODE, VAR — routes
// through `evaluate` and costs nothing to support, which is the whole argument
// for having one expression language instead of two.

/** What one cell of a column contributes to an aggregate — formula.ts's
 *  `rangeNumber` (rule 1 above its `num`): a NUMBER, or nothing. Text is
 *  skipped even when it looks like a number, and so are booleans, because a
 *  column handed to SUM is a RANGE, and that is what Excel does with one. This
 *  used to reproduce `num`, which read the text "50%" as 50 — the arithmetic
 *  half of review finding 3.1. The blank cases are handled by the CALLER
 *  (formula.ts `numbersIn`: a blank is absent, because AVERAGE over three
 *  numbers and seven empty cells is the mean of three). */
function fnum(v: Cell): number | null {
  return typeof v === 'number' ? v : null
}

/** Aggregate names this file open-codes, lowercased. */
const FAST = new Set(['sum', 'count', 'avg', 'average', 'min', 'max'])

/** Aggregates that COUNT rather than compute, and so are not poisoned by an
 *  error cell — formula.ts's `COUNTING`. Everything else propagates the first
 *  error it meets: a SUM over a range holding `#REF!` is `#REF!`, never the
 *  total of the cells that happened to work, which is a number with a piece
 *  missing and no way to tell. */
const FAST_COUNTING = new Set(['count'])

/** What a step's `fn` is called in formula.ts. */
const AGG_ALIAS: Record<string, string> = {
  avg: 'AVERAGE',
  average: 'AVERAGE',
  countdistinct: 'COUNTUNIQUE',
  countunique: 'COUNTUNIQUE',
  counta: 'COUNTA',
  countblank: 'COUNTBLANK',
}

/**
 * Aggregate `vals[pos[i]]` for `i` in `[from, to)`.
 *
 * `null` for `of` on a `count` is COUNT(*) — the number of rows in the group,
 * which is a different question from "how many numbers are in this column" and
 * the one people mean when they write `COUNT(*)`.
 */
function aggregate(fn: string, vals: Vec | null, pos: Int32Array, from: number, to: number): Cell {
  const key = fn.toLowerCase()
  if (!vals) return to - from
  if (FAST.has(key)) {
    const counting = FAST_COUNTING.has(key)
    let sum = 0
    let count = 0
    let min = Infinity
    let max = -Infinity
    for (let i = from; i < to; i++) {
      const raw = vals[pos[i]] ?? null
      // A BLANK IS NOT A ZERO in an aggregate (formula.ts `numbersIn`).
      if (raw === null || raw === '') continue
      if (isErr(raw)) {
        if (!counting) return raw
        continue
      }
      const n = fnum(raw)
      if (n === null) continue
      count++
      sum += n
      if (n < min) min = n
      if (n > max) max = n
    }
    switch (key) {
      case 'sum': return sum
      // formula.ts's MIN/MAX answer 0 for an empty set and AVERAGE answers
      // #DIV/0!. Both are reproduced deliberately: a step that disagreed with a
      // cell about the empty case is exactly the drift this file exists to avoid.
      case 'min': return count ? min : 0
      case 'max': return count ? max : 0
      case 'count': return count
      default: return count ? sum / count : evaluate('1/0', { cols: new Map(), n: 1 })[0]
    }
  }
  // The general path: hand the group's values to formula.ts under a name no
  // column can collide with, and let the one expression language answer.
  const slice: Vec = new Array<Cell>(to - from)
  for (let i = from; i < to; i++) slice[i - from] = vals[pos[i]] ?? null
  const name = AGG_ALIAS[key] ?? fn.toUpperCase()
  const cols = new Map<string, Vec>([['_g', slice], ['_G', slice]])
  return evaluate(`${name}(_g)`, { cols, n: slice.length })[0] ?? null
}

/**
 * `group` — the one step that MATERIALISES, because an aggregate is new data.
 *
 * Grouping is by the canonical key (`matchKey`), so a group here holds exactly
 * the rows the filter menu's checkbox for that value would hold. Group ORDER is
 * first appearance, which makes `sort → group` produce sorted groups and makes
 * two readers of one file see the same table — SQL guarantees no order at all,
 * and "no order" in a saved document means "a different order for each of you".
 */
function stepGroup(
  frame: Frame,
  step: { by?: unknown; agg?: unknown },
  at: number,
): StepOut {
  const by = Array.isArray(step.by) ? (step.by as unknown[]).filter((x): x is string => typeof x === 'string') : []
  const aggs = Array.isArray(step.agg)
    ? (step.agg as Array<{ fn?: unknown; of?: unknown; as?: unknown }>)
    : []
  if (!by.length && !aggs.length) {
    return { issues: [issue('group-empty', 'fatal', `Step ${at + 1} is a group with neither keys nor aggregates.`, { at, op: 'group' })] }
  }
  const issues: StepIssue[] = []

  const keyVecs: Vec[] = []
  const keyCols: Column[] = []
  for (const ref of by) {
    const v = values(frame, ref)
    const col = columnOf(frame, ref)
    if (!v || !col) {
      return {
        issues: [issue('group-missing-column', 'fatal',
          `Step ${at + 1} groups by ${JSON.stringify(ref)}, which is not a column here. Grouping by a column that is not there would silently collapse every row into one total.`,
          { at, op: 'group', column: ref })],
      }
    }
    keyVecs.push(v)
    keyCols.push(col)
  }

  // Bucket by canonical key, remembering first appearance. `order` holds the
  // frame positions grouped together, so aggregation is one contiguous walk.
  const seen = new Map<string, number>()
  const members: number[][] = []
  const firstRow: number[] = []
  for (let i = 0; i < frame.n; i++) {
    let k = ''
    for (let d = 0; d < keyVecs.length; d++) {
    // U+001F between the parts, and NOT bare concatenation: without a separator
    // ("ab", "c") and ("a", "bc") are ONE group — two dimensions merged into
    // one row, showing a total nobody can trace. The same separator the CRDT
    // uses for its composite node keys, for the same reason.
      k += (d ? '' : '') + matchKey(keyVecs[d][i] ?? null)
    }
    let g = seen.get(k)
    if (g === undefined) { g = members.length; seen.set(k, g); members.push([]); firstRow.push(i) }
    members[g].push(i)
  }
  const groups = members.length
  const pos = new Int32Array(frame.n)
  const starts = new Int32Array(groups + 1)
  let w = 0
  for (let g = 0; g < groups; g++) {
    starts[g] = w
    for (const i of members[g]) pos[w++] = i
  }
  starts[groups] = w
  stats.indexCells += frame.n + groups + 1

  // ---- the output table
  const columns: Column[] = []
  const data: Record<string, Vec> = {}
  for (let d = 0; d < keyCols.length; d++) {
    const src = keyCols[d]
    const out: Vec = new Array<Cell>(groups)
    // The FIRST value seen, not the canonical key: "North" is what the author
    // typed and what the reader should read, even though "north" grouped with it.
    for (let g = 0; g < groups; g++) out[g] = keyVecs[d][firstRow[g]] ?? null
    columns.push({ id: src.id, name: src.name, type: src.type, ...(src.format ? { format: src.format } : {}) } as Column)
    data[src.id] = out
    stats.retainedCells += groups
  }
  for (let a = 0; a < aggs.length; a++) {
    const spec = aggs[a]
    const fn = typeof spec.fn === 'string' ? spec.fn : 'count'
    const of = typeof spec.of === 'string' && spec.of ? spec.of : null
    const id = typeof spec.as === 'string' && spec.as ? spec.as : `${fn}_${of ?? 'rows'}`
    let vals: Vec | null = null
    if (of) {
      const v = values(frame, of)
      if (!v) {
        return {
          issues: [issue('group-missing-measure', 'fatal',
            `Step ${at + 1} aggregates ${JSON.stringify(of)}, which is not a column here. An aggregate over a column that is not there totals to zero, and zero is a number a reader will believe.`,
            { at, op: 'group', column: of })],
        }
      }
      vals = v
    }
    const out: Vec = new Array<Cell>(groups)
    for (let g = 0; g < groups; g++) out[g] = aggregate(fn, vals, pos, starts[g], starts[g + 1])
    stats.retainedCells += groups
    if (out.length && isErr(out[0]) && String(out[0]) === '#NAME?') {
      issues.push(issue('group-unknown-agg', 'suspicious',
        `Step ${at + 1}: no aggregate named ${JSON.stringify(fn)} — the column ${JSON.stringify(id)} reads #NAME? rather than a plausible total.`,
        { at, op: 'group', column: id }))
    }
    columns.push({ id, name: id, type: 'number' } as Column)
    data[id] = out
  }
  return { frame: tableFrame(`${frame.src.id}+group`, frame.src.name, groups, columns, data), issues }
}

/** A frame over freshly computed columns — what `group`, `join` and `union` make. */
function tableFrame(
  id: string, name: string, n: number, columns: Column[], data: Record<string, Vec>,
): Frame {
  const src: Source = {
    id, name, n, columns,
    vec: (colId: string) => data[colId],
  }
  stats.frames++
  return { src, rows: null, n, columns: columns.slice(), derived: new Map() }
}

// --- join ---------------------------------------------------------------------

/**
 * `join` — and THE REFUSAL.
 *
 * `card` is the author's DECLARATION of what one row of the other sheet means:
 * `'one'` says "at most one match per row here", which is the ordinary
 * fact-to-dimension lookup, and `'many'` says "this will multiply rows, and I
 * mean it". The failure this guards against is the first declaration meeting
 * data that contradicts it: every left row that matches two right rows is
 * silently duplicated, and every measure downstream doubles. The total looks
 * fine. It is the single most expensive quiet bug in analytics tooling, and it
 * has been printing wrong numbers for a decade because the declaration was
 * never written down anywhere a tool could check it.
 *
 * dash writes it down. So this checks it, and REFUSES — it does not produce
 * the doubled total with a warning next to it, because a number on screen wins
 * every argument with a warning beside it.
 *
 * Both cardinalities LEFT JOIN: an unmatched row is kept with blanks and
 * COUNTED, never dropped. Dropping unmatched rows is the other way to make a
 * total quietly wrong, and it is even harder to see.
 */
function stepJoin(
  frame: Frame,
  step: { with?: unknown; on?: unknown; card?: unknown; fields?: unknown },
  at: number,
  opts: RunOpts,
): StepOut {
  const withRef = typeof step.with === 'string' ? step.with : ''
  const on = Array.isArray(step.on) ? step.on : []
  const leftRef = typeof on[0] === 'string' ? on[0] : ''
  const rightRef = typeof on[1] === 'string' ? on[1] : ''
  const card = step.card === 'many' ? 'many' : 'one'
  const fields = Array.isArray(step.fields)
    ? (step.fields as unknown[]).filter((x): x is string => typeof x === 'string')
    : []

  const other = resolveSheet(withRef, opts)
  if (!other) {
    return {
      issues: [issue('join-missing-sheet', 'fatal',
        `Step ${at + 1} joins to ${JSON.stringify(withRef)}, which is not a table sheet in this workbook.`,
        { at, op: 'join' })],
    }
  }
  const leftVals = leftRef ? values(frame, leftRef) : undefined
  if (!leftVals) {
    return {
      issues: [issue('join-missing-column', 'fatal',
        `Step ${at + 1} joins on ${JSON.stringify(leftRef)}, which is not a column here.`,
        { at, op: 'join', column: leftRef })],
    }
  }
  const rsrc = sourceOf(other)
  const rframe = frameOf(rsrc)
  const rightVals = rightRef ? values(rframe, rightRef) : undefined
  if (!rightVals) {
    return {
      issues: [issue('join-missing-column', 'fatal',
        `Step ${at + 1} joins on ${JSON.stringify(rightRef)}, which is not a column of ${JSON.stringify(other.name || other.id)}.`,
        { at, op: 'join', column: rightRef })],
    }
  }

  // ---- index the right side, and check the declaration while doing it
  const index = new Map<string, number[]>()
  let worstKey = ''
  let worst = 1
  for (let r = 0; r < rsrc.n; r++) {
    const k = matchKey(rightVals[r] ?? null)
    const bucket = index.get(k)
    if (bucket) {
      bucket.push(r)
      if (bucket.length > worst) { worst = bucket.length; worstKey = String(rightVals[r] ?? '') }
    } else index.set(k, [r])
  }
  if (card === 'one' && worst > 1) {
    // How bad it would have been, said in the only unit that matters.
    let fanned = 0
    for (let i = 0; i < frame.n; i++) {
      const b = index.get(matchKey(leftVals[i] ?? null))
      if (b && b.length > 1) fanned += b.length - 1
    }
    return {
      issues: [issue('join-fanout', 'fatal',
        `Step ${at + 1} declares one match per row (card: "one"), but ${JSON.stringify(other.name || other.id)} holds ${worst} rows for ${JSON.stringify(worstKey)} on ${JSON.stringify(rightRef)}. Running it would add ${fanned} duplicate row(s) and multiply every total below by that much, with nothing on screen to show it. The join was refused instead. Either make ${JSON.stringify(rightRef)} unique, or declare card: "many" and mean it.`,
        { at, op: 'join', column: rightRef, rows: fanned })],
    }
  }

  // ---- the added columns
  const rcols: Column[] = []
  const taken = new Set(frame.columns.map((c) => c.id))
  for (const f of fields) {
    const col = columnOf(rframe, f)
    if (!col) {
      return {
        issues: [issue('join-missing-field', 'fatal',
          `Step ${at + 1} takes ${JSON.stringify(f)} from ${JSON.stringify(other.name || other.id)}, which has no such column.`,
          { at, op: 'join', column: f })],
      }
    }
    rcols.push(col)
  }

  const issues: StepIssue[] = []

  // ---- the row mapping
  let out = frame
  let matchOf: Int32Array
  if (card === 'one') {
    matchOf = new Int32Array(frame.n).fill(-1)
    let unmatched = 0
    for (let i = 0; i < frame.n; i++) {
      const b = index.get(matchKey(leftVals[i] ?? null))
      if (b) matchOf[i] = b[0]
      else unmatched++
    }
    stats.indexCells += frame.n
    if (unmatched) {
      issues.push(issue('join-unmatched', 'suspicious',
        `Step ${at + 1}: ${unmatched} of ${frame.n} row(s) found no match in ${JSON.stringify(other.name || other.id)}; their joined columns are blank. A key that misses is data telling you something.`,
        { at, op: 'join', rows: unmatched }))
    }
  } else {
    // The DECLARED fanout. Rows multiply, and that was the author's intent.
    const pos: number[] = []
    const hits: number[] = []
    let unmatched = 0
    for (let i = 0; i < frame.n; i++) {
      const b = index.get(matchKey(leftVals[i] ?? null))
      if (!b) { pos.push(i); hits.push(-1); unmatched++; continue }
      for (const r of b) { pos.push(i); hits.push(r) }
    }
    stats.indexCells += pos.length * 2
    out = reindex(frame, Int32Array.from(pos))
    matchOf = Int32Array.from(hits)
    if (pos.length !== frame.n) {
      issues.push(issue('join-fanned', 'suspicious',
        `Step ${at + 1} multiplied ${frame.n} row(s) into ${pos.length} (card: "many", as declared). Every measure below is now at the grain of ${JSON.stringify(other.name || other.id)}.`,
        { at, op: 'join', rows: pos.length - frame.n }))
    }
    if (unmatched) {
      issues.push(issue('join-unmatched', 'suspicious',
        `Step ${at + 1}: ${unmatched} row(s) found no match in ${JSON.stringify(other.name || other.id)}; their joined columns are blank.`,
        { at, op: 'join', rows: unmatched }))
    }
  }

  const derived = new Map(out.derived)
  const columns = out.columns.slice()
  for (const col of rcols) {
    const rv = rsrc.vec(col.id)!
    const id = taken.has(col.id) ? `${other.id}.${col.id}` : col.id
    const name = taken.has(col.id) ? `${other.name || other.id}.${col.name}` : col.name
    const vals: Vec = new Array<Cell>(out.n)
    for (let i = 0; i < out.n; i++) vals[i] = matchOf[i] < 0 ? null : (rv[matchOf[i]] ?? null)
    stats.retainedCells += out.n
    derived.set(id, vals)
    columns.push({ ...col, id, name } as Column)
    if (id !== col.id) {
      issues.push(issue('join-name-clash', 'suspicious',
        `Step ${at + 1}: ${JSON.stringify(col.name)} exists on both sides, so the joined one is named ${JSON.stringify(name)}.`,
        { at, op: 'join', column: id }))
    }
  }
  stats.frames++
  return { frame: { src: out.src, rows: out.rows, n: out.n, columns, derived }, issues }
}

// --- union --------------------------------------------------------------------

/**
 * `union` — rows from another sheet, appended.
 *
 * MATCHED BY COLUMN IDENTITY, not by position. SQL unions positionally because
 * a result set has no stable column identity to match on; dash's columns DO
 * have one (`Column.id` is the whole reason a rename cannot break a formula),
 * so matching positionally here would mean two sheets with the same columns in
 * a different order silently interleaving amounts with dates.
 *
 * A column present on only one side is filled blank and REPORTED. No overlap at
 * all is fatal: that is not a union, it is two tables stacked by accident.
 *
 * This step materialises, because a union genuinely is two column stores and
 * one index vector cannot address both.
 */
function stepUnion(
  frame: Frame, step: { with?: unknown; all?: unknown }, at: number, opts: RunOpts,
): StepOut {
  const refs = Array.isArray(step.with)
    ? (step.with as unknown[]).filter((x): x is string => typeof x === 'string')
    : typeof step.with === 'string' ? [step.with] : []
  if (!refs.length) {
    return { issues: [issue('union-missing-sheet', 'fatal', `Step ${at + 1} is a union with nothing to union.`, { at, op: 'union' })] }
  }
  const issues: StepIssue[] = []
  const parts: Array<{ frame: Frame; label: string }> = [{ frame, label: frame.src.name || frame.src.id }]
  for (const ref of refs) {
    const other = resolveSheet(ref, opts)
    if (!other) {
      return {
        issues: [issue('union-missing-sheet', 'fatal',
          `Step ${at + 1} unions with ${JSON.stringify(ref)}, which is not a table sheet in this workbook.`,
          { at, op: 'union' })],
      }
    }
    parts.push({ frame: frameOf(sourceOf(other)), label: other.name || other.id })
  }

  // Which columns the result has, in this frame's order, then anything new.
  const columns: Column[] = frame.columns.map((c) => ({ ...c }))
  const has = new Map<string, number>()
  frame.columns.forEach((c, i) => { has.set(unionKey(c), i) })
  for (const p of parts.slice(1)) {
    for (const c of p.frame.columns) {
      if (has.has(unionKey(c))) continue
      has.set(unionKey(c), columns.length)
      columns.push({ ...c })
    }
  }
  let shared = 0
  for (const c of parts[1].frame.columns) if (has.get(unionKey(c))! < frame.columns.length) shared++
  if (!shared) {
    return {
      issues: [issue('union-disjoint', 'fatal',
        `Step ${at + 1} unions ${JSON.stringify(parts[0].label)} with ${JSON.stringify(parts[1].label)}, and they share no columns. Stacking them would produce a table where every row is blank in half its columns.`,
        { at, op: 'union' })],
    }
  }

  const total = parts.reduce((a, p) => a + p.frame.n, 0)
  const data: Record<string, Vec> = {}
  for (const c of columns) data[c.id] = new Array<Cell>(total).fill(null)
  let w = 0
  const missing = new Set<string>()
  for (const p of parts) {
    for (const c of columns) {
      const v = values(p.frame, c.id) ?? (c.name ? values(p.frame, c.name) : undefined)
      if (!v) { missing.add(`${p.label}.${c.name || c.id}`); continue }
      const dst = data[c.id]
      for (let i = 0; i < p.frame.n; i++) dst[w + i] = v[i] ?? null
    }
    w += p.frame.n
  }
  stats.retainedCells += total * columns.length
  if (missing.size) {
    issues.push(issue('union-shape', 'suspicious',
      `Step ${at + 1}: ${[...missing].slice(0, 4).join(', ')}${missing.size > 4 ? ` and ${missing.size - 4} more` : ''} — column(s) missing on one side of the union, filled blank. Blank is not zero, and nothing below will total them as zero.`,
      { at, op: 'union' }))
  }

  // UNION ALL is the default, matching SQL. `all: false` dedupes on the whole row.
  if (step.all === false) {
    const seen = new Set<string>()
    const keep: number[] = []
    for (let i = 0; i < total; i++) {
      let k = ''
      for (const c of columns) k += matchKey(data[c.id][i]) + ''
      if (seen.has(k)) continue
      seen.add(k)
      keep.push(i)
    }
    if (keep.length !== total) {
      const out: Record<string, Vec> = {}
      for (const c of columns) {
        const src = data[c.id]
        const dst: Vec = new Array<Cell>(keep.length)
        for (let i = 0; i < keep.length; i++) dst[i] = src[keep[i]]
        out[c.id] = dst
      }
      stats.retainedCells += keep.length * columns.length
      issues.push(issue('union-deduped', 'suspicious',
        `Step ${at + 1} removed ${total - keep.length} duplicate row(s) (union, not union all).`,
        { at, op: 'union', rows: total - keep.length }))
      return { frame: tableFrame(`${frame.src.id}+union`, frame.src.name, keep.length, columns, out), issues }
    }
  }
  return { frame: tableFrame(`${frame.src.id}+union`, frame.src.name, total, columns, data), issues }
}

const unionKey = (c: Column): string => (c.name ? c.name.trim().toLowerCase() : c.id)

function resolveSheet(ref: string, opts: RunOpts): TableSheet | undefined {
  if (opts.sheets) {
    const hit = opts.sheets(ref)
    if (hit) return hit
  }
  const sheets = opts.doc?.sheets ?? []
  const byId = sheets.find((s: Sheet) => s.id === ref)
  if (byId && byId.kind === 'table') return byId
  const byName = sheets.find((s: Sheet) => s.name === ref)
  if (byName && byName.kind === 'table') return byName
  return undefined
}

// --- the runner ---------------------------------------------------------------

/**
 * Run a step list over a sheet.
 *
 * STOPS AT THE FIRST STEP IT CANNOT RUN, and hands back the frame from BEFORE
 * that step together with the finding that explains it. It never skips a step
 * and carries on: a pipeline missing its middle is not a partial answer, it is
 * a different question, and the answer to a different question looks exactly
 * like the answer to yours.
 */
export function runSteps(
  input: TableSheet | Frame, steps: readonly Step[], opts: RunOpts = {},
): StepResult {
  let frame = isFrame(input) ? input : frameOf(sourceOf(input))
  const issues: StepIssue[] = []
  let ran = 0
  let unresolved = false

  for (let at = 0; at < steps.length; at++) {
    const step = steps[at] as { op?: unknown } & Record<string, unknown>
    const op = typeof step?.op === 'string' ? step.op : ''

    if (PROVENANCE_OPS.has(op) || SETTLED_OPS.has(op)) { ran++; continue }
    if (DEFERRED_OPS.has(op)) {
      issues.push(issue('step-not-implemented', 'unresolved',
        `Step ${at + 1} is a "${op}", which this build cannot run yet. Everything below it is unresolved — the values you can see are the ones from before this step, not a result.`,
        { at, op }))
      unresolved = true
      break
    }

    let out: StepOut
    try {
      switch (op) {
        case 'filter': out = stepFilter(frame, step as never, at, opts.now); break
        case 'derive': out = stepDerive(frame, step as never, at, opts.now); break
        case 'split': out = stepSplit(frame, step as never, at); break
        case 'sort': out = stepSort(frame, step as never, at); break
        case 'limit': out = stepLimit(frame, step as never, at); break
        case 'group': out = stepGroup(frame, step as never, at); break
        case 'join': out = stepJoin(frame, step as never, at, opts); break
        case 'union': out = stepUnion(frame, step as never, at, opts); break
        default:
          // An op a NEWER build wrote. The file keeps it (PLATFORM §3) and this
          // build must not pretend to have run it — descendants are unresolved,
          // and views show last known values with a badge, never zero.
          issues.push(issue('unknown-op', 'unresolved',
            `Step ${at + 1} is a "${op || '(no op)'}", which this build does not know. It was kept in the file and NOT run; anything below it is unresolved rather than wrong.`,
            { at, op }))
          unresolved = true
          out = {}
      }
    } catch (e) {
      // A packed column, a malformed step, anything deeper. A throw reaching the
      // caller would take the whole grid down; a finding names the step.
      out = {
        issues: [issue('step-threw', 'fatal',
          `Step ${at + 1} ("${op}") could not run: ${e instanceof Error ? e.message : String(e)}`,
          { at, op })],
      }
    }
    if (out.issues) issues.push(...out.issues)
    if (unresolved) break
    const stopped = (out.issues ?? []).some((i) => i.severity === 'fatal' || i.severity === 'unresolved')
    if (stopped) {
      if ((out.issues ?? []).some((i) => i.severity === 'unresolved')) unresolved = true
      return { ok: false, frame, ran, issues, unresolved }
    }
    if (out.frame) frame = out.frame
    ran++
  }
  const ok = !unresolved && !issues.some((i) => i.severity === 'fatal')
  return { ok, frame, ran, issues, unresolved }
}

const isFrame = (v: TableSheet | Frame): v is Frame =>
  typeof (v as Frame).src === 'object' && (v as Frame).src !== null && 'vec' in (v as Frame).src

/** Run a sheet's own step list. The ordinary call. */
export function runSheet(doc: DashDoc, sheetId: string, opts: RunOpts = {}): StepResult | undefined {
  const s = doc.sheets.find((x: Sheet) => x.id === sheetId)
  if (!s || s.kind !== 'table') return undefined
  return runSteps(s, s.steps ?? [], { doc, ...opts })
}

// --- materialisation ----------------------------------------------------------

/**
 * A frame as a real sheet — what "the result is a sheet with a tab like any
 * other" means in practice.
 *
 * `enc: 'raw'`, deliberately. Dictionary encoding is what makes the FORMAT fit
 * and belongs to whatever writes this into a document; a derived sheet that has
 * not been saved yet has no such obligation, and re-interning on the way out is
 * a decision for the call site, not a hidden one here.
 *
 * ERROR CELLS ARE WRITTEN AS THEIR CODE. A `#DIV/0!` becomes the string
 * "#DIV/0!", so a saved result shows the error that produced it rather than a
 * blank the next reader will total as zero.
 */
export function materialize(frame: Frame, meta: { id: string; name: string; from?: string; steps?: Step[] }): TableSheet {
  const data: Record<string, ColumnData> = {}
  for (const c of frame.columns) {
    const v = values(frame, c.id)
    const out = new Array<number | string | boolean | null>(frame.n)
    for (let i = 0; i < frame.n; i++) {
      const x = v ? (v[i] ?? null) : null
      out[i] = isErr(x) ? String(x) : (x as number | string | boolean | null)
    }
    data[c.id] = { enc: 'raw', v: out }
  }
  return {
    id: meta.id,
    name: meta.name,
    kind: 'table',
    rids: frame.n ? [[1, frame.n]] : [],
    nextRid: frame.n + 1,
    columns: frame.columns.map((c) => ({ ...c })),
    data,
    steps: meta.steps ?? [],
    ...(meta.from ? { from: meta.from } : {}),
  }
}

export const _internals = {
  stats, resetStats, asNumber, matchKey, aggregate, fnum, reindex,
  FAST, FAST_COUNTING, AGG_ALIAS, SETTLED_OPS, DEFERRED_OPS, sortComparator,
}