Computed and locked values

/**
 * Values computed from others, kept up to date by doing as little as a change
 * asks: the fields of a record that a formula derives from its other fields,
 * and the fields people have locked against change.
 *
 * - **Live.** A plan puts the computed fields in dependency order once. A change
 *   to some fields recomputes only the computed fields downstream of them, in
 *   that order, and stops wherever a value comes out as it was: what depends on
 *   an unchanged value is not recomputed.
 * - **Locked.** A lock is one of two kinds. A *frozen* computed field keeps the
 *   value it has — typed over its formula, or as it stood — and stops
 *   following what it is computed from, which may go on changing; what depends
 *   on it sees the kept value. A *held* field may not change at all: a write to
 *   it is refused, and so, when it is computed, is any write that would change
 *   it by way of what it is computed from. A field that is not computed refuses
 *   writes under either kind.
 * - **Cycles.** Fields whose formulas lead round to themselves, and everything
 *   computed from them, are never computed: they hold no value, and the plan
 *   names them.
 *
 * A formula is given here already compiled — its references and a function
 * that evaluates it — so this knows nothing of how formulas are written. A
 * reference is a field's key, or a dotted path into a list of records
 * (`lines.amount`), which depends on the list's field (`lines`).
 *
 * The plan holds the order and each field's dependencies as typed arrays, with
 * scratch space kept and reused: deriving a record allocates the new record,
 * if anything in it changed, and nothing else.
 */
import { graphFrom, topologicalOrder } from "../algorithms/topological.ts";
import type { AnyRecord, CellChange, RecordChange } from "./record-changes.ts";
import { compileFormula } from "../algorithms/formula.ts";
import type { FormulaType } from "../algorithms/formula.ts";
import { conform, resolve } from "./schema.ts";
import type { ObjectSchema, Schema } from "./schema.ts";

/** A computed field: its key, what it reads, and how it is computed from what it reads. */
export interface Derivation {
  readonly key: string;
  readonly references: readonly string[];
  /** Given a reader of the record's values by reference, the field's value; `null` for none. */
  readonly evaluate: (get: (reference: string) => unknown) => unknown;
}

export interface DerivedPlan {
  /** The computed fields that can be computed, in the order to compute them. */
  readonly order: readonly string[];
  /** Computed fields in a cycle, or computed from one: never computed. */
  readonly cyclic: ReadonlySet<string>;
  /** Whether a field is computed — by a formula, though it may be in a cycle. */
  readonly computes: (key: string) => boolean;
  /** @internal */
  readonly steps: ReadonlyArray<Derivation>;
  /** @internal For each step, the indices of the fields it reads: `reads[readsAt[s] … readsAt[s + 1])`. */
  readonly readsAt: Int32Array;
  readonly reads: Int32Array;
  /** @internal Each field's index, and the step that computes it (−1 for none). */
  readonly index: ReadonlyMap<string, number>;
  readonly stepOf: Int32Array;
  /** @internal Which fields have changed, in the derivation going on: reused. */
  readonly dirty: Uint8Array;
}

/** The field a reference depends on: the first part of a dotted path. */
const fieldOf = (reference: string): string => {
  const dot = reference.indexOf(".");
  return dot === -1 ? reference : reference.slice(0, dot);
};

/** Put computed fields in the order to compute them, once for as many records as there are. */
export function planDerivations(derivations: readonly Derivation[]): DerivedPlan {
  const index = new Map<string, number>();
  const place = (key: string) => {
    let at = index.get(key);
    if (at === undefined) {
      at = index.size;
      index.set(key, at);
    }
    return at;
  };
  const computed = new Map<string, Derivation>();
  for (const derivation of derivations) {
    if (computed.has(derivation.key)) {
      throw new RangeError(`The field ${JSON.stringify(derivation.key)} is computed twice.`);
    }
    computed.set(derivation.key, derivation);
    place(derivation.key);
  }
  const edges: number[] = [];
  for (const derivation of derivations) {
    const to = index.get(derivation.key)!;
    for (const reference of derivation.references) edges.push(place(fieldOf(reference)), to);
  }
  const graph = graphFrom(index.size, edges);

  // Kahn's order over the whole graph; what it cannot reach is in a cycle or downstream of one.
  const order = topologicalOrder(graph) ?? partialOrder(graph.offsets, graph.targets);
  const keys = [...index.keys()];
  const steps: Derivation[] = [];
  const stepOf = new Int32Array(index.size).fill(-1);
  for (const node of order) {
    const derivation = computed.get(keys[node]!);
    if (derivation === undefined) continue;
    stepOf[node] = steps.length;
    steps.push(derivation);
  }
  const cyclic = new Set<string>();
  for (const key of computed.keys()) if (stepOf[index.get(key)!] === -1) cyclic.add(key);

  const readsAt = new Int32Array(steps.length + 1);
  const all: number[] = [];
  for (const [at, step] of steps.entries()) {
    const seen = new Set<number>();
    for (const reference of step.references) seen.add(index.get(fieldOf(reference))!);
    all.push(...seen);
    readsAt[at + 1] = all.length;
  }
  return {
    order: steps.map((step) => step.key),
    cyclic,
    computes: (key) => computed.has(key),
    steps,
    readsAt,
    reads: Int32Array.from(all),
    index,
    stepOf,
    dirty: new Uint8Array(index.size),
  };
}

/** The nodes Kahn's algorithm reaches: all but those on a cycle and downstream of one. */
function partialOrder(offsets: Int32Array, targets: Int32Array): Int32Array {
  const count = offsets.length - 1;
  const waiting = new Int32Array(count);
  for (let edge = 0; edge < targets.length; edge += 1) waiting[targets[edge]!]! += 1;
  const queue = new Int32Array(count);
  let tail = 0;
  for (let node = 0; node < count; node += 1) if (waiting[node] === 0) queue[tail++] = node;
  for (let head = 0; head < tail; head += 1) {
    const node = queue[head]!;
    for (let edge = offsets[node]!; edge < offsets[node + 1]!; edge += 1) {
      const to = targets[edge]!;
      waiting[to]! -= 1;
      if (waiting[to] === 0) queue[tail++] = to;
    }
  }
  return queue.subarray(0, tail);
}

/** A record's value at a reference: a field, or the field of each item of a list of records. */
export function readReference(record: AnyRecord, reference: string): unknown {
  const dot = reference.indexOf(".");
  if (dot === -1) return record[reference] ?? null;
  const list = record[reference.slice(0, dot)];
  if (!Array.isArray(list)) return [];
  const rest = reference.slice(dot + 1);
  return list.map((item: unknown) =>
    item !== null && typeof item === "object" ? readReference(item as AnyRecord, rest) : null,
  );
}

export interface DeriveOptions {
  /**
   * The fields that changed since the record's computed values were last right.
   * Left out, every computed field is computed. A computed field named here is
   * computed again itself: that is how one is unlocked.
   */
  readonly changed?: readonly string[];
  /** Whether a computed field is frozen: it keeps the value it has. */
  readonly frozen?: (key: string) => boolean;
}

/**
 * The record with its computed fields right: the same record when none of them
 * changed. Fields in a cycle hold `null`.
 */
export function deriveRecord<R extends AnyRecord>(
  plan: DerivedPlan,
  record: R,
  options: DeriveOptions = {},
): R & AnyRecord {
  const { steps, readsAt, reads, index, dirty } = plan;
  const { changed, frozen } = options;
  const everything = changed === undefined;
  if (!everything) {
    for (const key of changed) {
      const at = index.get(key);
      if (at !== undefined) dirty[at] = 1;
    }
  }
  let next: Record<string, unknown> | null = null;
  const get = (reference: string) => readReference(next ?? record, reference);
  try {
    for (let step = 0; step < steps.length; step += 1) {
      const { key, evaluate } = steps[step]!;
      const at = index.get(key)!;
      let due = everything || dirty[at] === 1;
      for (let read = readsAt[step]!; !due && read < readsAt[step + 1]!; read += 1)
        due = dirty[reads[read]!] === 1;
      if (!due) continue;
      // What it keeps is what depends on it sees: unchanged, unless it was itself just written.
      if (frozen?.(key) === true) continue;
      const value = normalise(evaluate(get));
      // A computed field is there, holding nothing if it holds nothing; one already right is left be.
      const current = next ?? record;
      if (Object.hasOwn(current, key) && Object.is(value, current[key])) continue;
      next ??= { ...record };
      next[key] = value;
      dirty[at] = 1;
    }
    // A field in a cycle holds nothing, whatever it held.
    for (const key of plan.cyclic) {
      if (((next ?? record)[key] ?? null) === null) continue;
      next ??= { ...record };
      next[key] = null;
    }
  } finally {
    dirty.fill(0);
  }
  return (next ?? record) as R & AnyRecord;
}

// A formula's "nothing" is `null`, however it said it.
const normalise = (value: unknown): unknown =>
  value === undefined || (typeof value === "number" && !Number.isFinite(value)) ? null : value;

/**
 * The computed values a change to a list of records brings with it, as a change
 * of its own — to apply after it, and to undo with it as one. `before` is the
 * list the change was made to.
 */
export function deriveChange<R extends AnyRecord>(
  plan: DerivedPlan,
  before: readonly R[],
  change: RecordChange<R>,
  frozen?: (row: number, key: string) => boolean,
): RecordChange<R> | null {
  if (plan.steps.length === 0 && plan.cyclic.size === 0) return null;
  const cells: CellChange[] = [];
  const derive = (row: number, record: R, changed?: readonly string[]) => {
    const derived = deriveRecord(plan, record, {
      ...(changed === undefined ? {} : { changed }),
      ...(frozen === undefined ? {} : { frozen: (key: string) => frozen(row, key) }),
    });
    if (derived === record) return;
    for (const key of [...plan.order, ...plan.cyclic]) {
      if (!Object.is(derived[key], record[key])) {
        cells.push({ row, key, value: derived[key] ?? null, previous: record[key] ?? null });
      }
    }
  };
  switch (change.kind) {
    case "cells": {
      // Each record once, with every field the change wrote to it.
      const byRow = new Map<number, string[]>();
      for (const { row, key } of change.cells) {
        const keys = byRow.get(row);
        if (keys === undefined) byRow.set(row, [key]);
        else keys.push(key);
      }
      for (const [row, keys] of byRow) {
        const record = before[row];
        if (record === undefined) continue;
        const written: Record<string, unknown> = { ...record };
        for (const cell of change.cells) if (cell.row === row) written[cell.key] = cell.value;
        derive(row, written as R, keys);
      }
      break;
    }
    case "insert": {
      const at = Math.min(Math.max(change.at, 0), before.length);
      for (const [offset, record] of change.rows.entries()) derive(at + offset, record);
      break;
    }
    case "remove":
      return null;
  }
  return cells.length === 0 ? null : { kind: "cells", cells };
}

/** The key a lock on one field of one record is held under. */
export function lockKey(record: string, field: string): string {
  return `${record}\u001f${field}`;
}

export type Lock = "frozen" | "held";

/**
 * Locks kept under records' places (`lockKey(String(place), field)`), moved
 * with their records past records put in or taken out: a lock on a record
 * taken out goes with it. Locks of any other key, and a change of cells, are
 * left as they are; the same map when nothing moved.
 */
export function locksAfter(
  locks: ReadonlyMap<string, Lock>,
  change: RecordChange,
): ReadonlyMap<string, Lock> {
  if (change.kind === "cells" || locks.size === 0) return locks;
  const place = (at: number): number | null => {
    if (change.kind === "insert") return at >= change.at ? at + change.rows.length : at;
    let gone = 0;
    for (const run of change.runs) {
      if (at < run.at) break;
      if (at < run.at + run.rows.length) return null;
      gone += run.rows.length;
    }
    return at - gone;
  };
  let moved = false;
  const next = new Map<string, Lock>();
  for (const [key, lock] of locks) {
    const split = key.indexOf("\u001f");
    const record = split === -1 ? "" : key.slice(0, split);
    const at = /^(?:0|[1-9]\d*)$/.test(record) ? Number(record) : null;
    const to = at === null ? null : place(at);
    if (at !== null && to !== at) moved = true;
    if (at === null) next.set(key, lock);
    else if (to !== null) next.set(lockKey(String(to), key.slice(split + 1)), lock);
  }
  return moved ? next : locks;
}

/** What may be done to a field's lock, in the order a menu offers it. */
export type LockAction = "hold" | "freeze" | "unlock";

/**
 * What a field's menu offers: any field can be held; a computed one that is not
 * locked can be frozen, and a frozen one held; a locked one unlocked — which,
 * for a frozen computed field, is to unfreeze it and compute it again.
 */
export function lockActions(computed: boolean, lock: Lock | undefined): readonly LockAction[] {
  if (lock === undefined) return computed ? ["hold", "freeze"] : ["hold"];
  return lock === "frozen" && computed ? ["hold", "unlock"] : ["unlock"];
}

/**
 * The words for locks and computed values, in English: the items of a value's
 * menu, what a computed or locked value says of itself, and what a refused
 * change says. A component lets each be replaced.
 */
export interface LockMessages {
  readonly hold: string;
  readonly freeze: string;
  readonly unlock: string;
  /** Unlocking a frozen computed value, which computes it again. */
  readonly unfreeze: string;
  /** What a computed value says it is computed as: its formula. */
  readonly computed: (formula: string) => string;
  readonly frozen: string;
  readonly held: string;
  /** Said where a change was refused, naming the held value it would have changed. */
  readonly refused: (label: string) => string;
  /** A word beside a value's name, for the eye: what its description says in full. */
  readonly computedMark: string;
  readonly frozenMark: string;
  readonly heldMark: string;
}

export const LOCK_MESSAGES: LockMessages = {
  hold: "Hold value",
  freeze: "Freeze",
  unlock: "Unlock",
  unfreeze: "Unfreeze",
  computed: (formula) => `Computed as ${formula}.`,
  frozen: "Frozen: kept as it is.",
  held: "Held: it may not change.",
  refused: (label) => `${label} is held; this would change it.`,
  computedMark: "computed",
  frozenMark: "frozen",
  heldMark: "held",
};

/** A change to one record under its locks: the record it comes to, or the field that refused it. */
export interface RecordEdit<R> {
  /** The record written, with what it computes; the record as it was, when refused. */
  readonly record: R;
  /** Computed fields that were written over, and are frozen now at what was written. */
  readonly frozen: readonly string[];
  /** The locked field that refused the change, if one did. */
  readonly refusedBy: string | undefined;
}

/**
 * One record changed from `before` to `after`, as a form changes it: every field
 * that differs is written at once. A computed field written over that was not
 * locked is frozen at what was written. A change locks refuse is not made at
 * all — the field that refused it is named — and one they allow comes with
 * everything it computes, recomputing only what the written fields reach.
 */
export function editRecord<R extends AnyRecord>(
  plan: DerivedPlan,
  before: R,
  after: R,
  lockOf: (key: string) => Lock | undefined,
): RecordEdit<R> {
  const changed: string[] = [];
  for (const key of new Set([...Object.keys(before), ...Object.keys(after)])) {
    if (!Object.is(before[key], after[key])) changed.push(key);
  }
  if (changed.length === 0) return { record: after, frozen: [], refusedBy: undefined };
  const frozen = changed.filter((key) => plan.computes(key) && lockOf(key) === undefined);
  const lock = (key: string) => (frozen.includes(key) ? "frozen" : lockOf(key));
  const cells = changed.map((key) => ({
    row: 0,
    key,
    value: after[key] ?? null,
    previous: before[key] ?? null,
  }));
  const { refused } = guardChange(plan, [before], { kind: "cells", cells }, (_row, key) => lock(key));
  if (refused.length > 0) return { record: before, frozen: [], refusedBy: refused[0]!.by };
  const record = deriveRecord(plan, after, { changed, frozen: (key) => lock(key) === "frozen" });
  return { record, frozen, refusedBy: undefined };
}

/**
 * A record with one field's lock taken off. A computed field is computed again —
 * that is how a frozen one is unfrozen — unless that would change a held one,
 * which then refuses it, as it would any other change.
 */
export function unlockRecord<R extends AnyRecord>(
  plan: DerivedPlan,
  record: R,
  key: string,
  lockOf: (key: string) => Lock | undefined,
): { readonly record: R; readonly refusedBy: string | undefined } {
  if (!plan.computes(key)) return { record, refusedBy: undefined };
  const lock = (field: string) => (field === key ? undefined : lockOf(field));
  const after = deriveRecord(plan, record, { changed: [key], frozen: (field) => lock(field) === "frozen" });
  const by = plan.order.find(
    (field) => lock(field) === "held" && !Object.is(after[field] ?? null, record[field] ?? null),
  );
  return by === undefined ? { record: after, refusedBy: undefined } : { record, refusedBy: by };
}

/** Writes to many records under their locks: what is done, what it freezes, and what was refused. */
export interface RecordsEdit {
  /** The writes that may be made, with every computed value they move after them, as one change; none, `null`. */
  readonly change: { readonly kind: "cells"; readonly cells: readonly CellChange[] } | null;
  /** Computed cells written over, frozen now at what was written. */
  readonly frozen: ReadonlyArray<{ readonly row: number; readonly key: string }>;
  readonly refused: readonly Refusal[];
}

/**
 * Writes to the fields of many records at once — a paste, a fill, a cleared
 * block — as a table makes them. A write that changes nothing is no write. A
 * computed field written over that was not locked is frozen at what was
 * written, unless it is what the field would come to anyway: written with
 * what the record now computes for it, it goes on following. What locks
 * refuse is left out and named (`guardChange`); what may be done comes with
 * every computed value it moves, recomputing only what the writes reach.
 */
export function editRecords<R extends AnyRecord>(
  plan: DerivedPlan,
  before: readonly R[],
  cells: readonly CellChange[],
  lockOf: (row: number, key: string) => Lock | undefined,
): RecordsEdit {
  const writes = cells.filter((cell) => !Object.is(cell.value ?? null, before[cell.row]?.[cell.key] ?? null));
  // Computed fields written over that nothing locks: frozen, unless the write agrees with the formula.
  const freezing = new Set<CellChange>();
  const byRow = new Map<number, CellChange[]>();
  for (const cell of writes) {
    if (!plan.computes(cell.key) || lockOf(cell.row, cell.key) !== undefined) continue;
    const row = byRow.get(cell.row);
    if (row === undefined) byRow.set(cell.row, [cell]);
    else row.push(cell);
  }
  const agreeing = new Set<CellChange>();
  for (const [row, candidates] of byRow) {
    const record = before[row];
    if (record === undefined) continue;
    const written: Record<string, unknown> = { ...record };
    const keys: string[] = [];
    for (const cell of writes) {
      if (cell.row !== row) continue;
      written[cell.key] = cell.value;
      keys.push(cell.key);
    }
    const following = deriveRecord(plan, written, {
      changed: keys,
      frozen: (key) => lockOf(row, key) === "frozen" && !candidates.some((cell) => cell.key === key),
    });
    for (const cell of candidates) {
      if (Object.is(following[cell.key] ?? null, cell.value ?? null)) agreeing.add(cell);
      else freezing.add(cell);
    }
  }
  const asked = writes.filter((cell) => !agreeing.has(cell));
  const frozenAt = new Set([...freezing].map((cell) => `${cell.row}\u001f${cell.key}`));
  const lock = (row: number, key: string) =>
    frozenAt.has(`${row}\u001f${key}`) ? "frozen" : lockOf(row, key);
  const { allowed, refused } = guardChange(plan, before, { kind: "cells", cells: asked }, lock);
  const done = allowed?.kind === "cells" ? allowed.cells : [];
  // What agreed is not written but computed again, as following: the derivation makes it, if it differs at all.
  const reached: CellChange[] = [...done];
  for (const cell of agreeing) {
    if (refused.some((refusal) => refusal.cell.row === cell.row)) continue;
    const was = before[cell.row]?.[cell.key] ?? null;
    reached.push({ ...cell, value: was, previous: was });
  }
  const derived =
    reached.length === 0
      ? null
      : deriveChange(
          plan,
          before,
          { kind: "cells", cells: reached },
          (row, key) => lock(row, key) === "frozen",
        );
  const written = [...done, ...(derived?.kind === "cells" ? derived.cells : [])];
  return {
    change: written.length === 0 ? null : { kind: "cells", cells: written },
    frozen: done.filter((cell) => freezing.has(cell)).map(({ row, key }) => ({ row, key })),
    refused,
  };
}

/** A write that was refused, and the locked field that refused it: itself, or what it would have changed. */
export interface Refusal {
  readonly cell: CellChange;
  readonly by: string;
}

/**
 * A change with what locks refuse taken out: what may be done, if anything, and
 * what was refused and by which field — for the interface to say so.
 *
 * A write to a field that is not computed is refused when the field is locked.
 * A write to a computed field is refused when it is held, and taken as its new
 * kept value when it is frozen. And the writes to one record are refused
 * together when, between them, they would change one of its held computed
 * fields by way of what it is computed from: they were made as one.
 */
export function guardChange<R extends AnyRecord>(
  plan: DerivedPlan,
  before: readonly R[],
  change: RecordChange<R>,
  lockOf: (row: number, key: string) => Lock | undefined,
): { readonly allowed: RecordChange<R> | null; readonly refused: readonly Refusal[] } {
  if (change.kind !== "cells") return { allowed: change, refused: [] };
  const refused: Refusal[] = [];
  const direct: CellChange[] = [];
  for (const cell of change.cells) {
    const lock = lockOf(cell.row, cell.key);
    const writable = lock === undefined || (lock === "frozen" && plan.computes(cell.key));
    if (writable) direct.push(cell);
    else refused.push({ cell, by: cell.key });
  }
  // Each record's remaining writes, tried together against its held computed fields.
  const allowed: CellChange[] = [];
  const rows = new Map<number, CellChange[]>();
  for (const cell of direct) {
    const cells = rows.get(cell.row);
    if (cells === undefined) rows.set(cell.row, [cell]);
    else cells.push(cell);
  }
  for (const [row, cells] of rows) {
    const record = before[row];
    const breaks =
      record === undefined ? undefined : heldBroken(plan, record, cells, (key) => lockOf(row, key));
    if (breaks === undefined) allowed.push(...cells);
    else for (const cell of cells) refused.push({ cell, by: breaks });
  }
  if (refused.length === 0) return { allowed: change, refused };
  // In the order they were asked for.
  const order = new Map(change.cells.map((cell, at) => [cell, at]));
  allowed.sort((a, b) => order.get(a)! - order.get(b)!);
  return { allowed: allowed.length === 0 ? null : { kind: "cells", cells: allowed }, refused };
}

/** The first held computed field that these writes to a record would change; none, `undefined`. */
function heldBroken(
  plan: DerivedPlan,
  record: AnyRecord,
  cells: readonly CellChange[],
  lockOf: (key: string) => Lock | undefined,
): string | undefined {
  let holds = false;
  for (const key of plan.order) if (lockOf(key) === "held") holds = true;
  if (!holds) return undefined;
  const written: Record<string, unknown> = { ...record };
  for (const cell of cells) written[cell.key] = cell.value;
  const after = deriveRecord(plan, written, {
    changed: cells.map((cell) => cell.key),
    frozen: (key) => lockOf(key) === "frozen",
  });
  for (const key of plan.order) {
    if (lockOf(key) === "held" && !Object.is(after[key] ?? null, record[key] ?? null)) return key;
  }
  return undefined;
}

/**
 * Records made to fit a changed schema (as `conform` makes them), as a change
 * that can be undone, and the held values it would change — a field dropped, a
 * value of a kind the field no longer has, an option that is gone. A caller
 * that finds any refuses the schema change and says which; a limit moved past a
 * value changes nothing, for the value is kept and reported as out of range,
 * and a field renamed moves its value, which is not lost — the lock moves with
 * it, by the caller, under the new name.
 */
export function conformRecords<R extends AnyRecord>(
  definition: ObjectSchema,
  before: ObjectSchema,
  rows: readonly R[],
  lockOf: (row: number, key: string) => Lock | undefined,
): {
  readonly rows: readonly AnyRecord[];
  readonly change: RecordChange | null;
  readonly blocked: readonly CellChange[];
} {
  const cells: CellChange[] = [];
  const blocked: CellChange[] = [];
  const next = rows.map((record, row) => {
    const fitted = conform(definition, record, before) as AnyRecord;
    if (fitted === record) return record;
    // A field renamed keeps its value under its new name: what moved was not lost.
    const gained = Object.keys(fitted).filter((key) => !Object.hasOwn(record, key));
    for (const key of new Set([...Object.keys(record), ...Object.keys(fitted)])) {
      const value = Object.hasOwn(fitted, key) ? fitted[key] : undefined;
      if (Object.is(value, record[key])) continue;
      const cell = { row, key, value, previous: record[key] };
      cells.push(cell);
      const moved = value === undefined && gained.some((to) => Object.is(fitted[to], record[key]));
      if (lockOf(row, key) === "held" && !moved) blocked.push(cell);
    }
    return fitted;
  });
  return { rows: next, change: cells.length === 0 ? null : { kind: "cells", cells }, blocked };
}

/** What a schema's formulas could not be read as, field by field: for the field to say, and underline. */
export interface FormulaProblem {
  readonly key: string;
  readonly message: string;
  readonly at: number;
  readonly length: number;
}

/** The kind of value a formula would have to give, or read, for a field of this schema. */
function formulaType(stated: Schema): FormulaType | undefined {
  const definition = resolve(stated);
  switch (definition.kind) {
    case "number":
    case "date":
    case "boolean":
      return definition.kind;
    case "text":
    case "choice":
      return "text";
    default:
      return undefined;
  }
}

/** A list's items as a formula reads them: a list of one kind of value. */
function listOf(type: FormulaType | undefined): FormulaType | undefined {
  return type === "number" || type === "text" || type === "boolean" || type === "date"
    ? (`list-${type}` as FormulaType)
    : undefined;
}

/**
 * The plan for a record schema's computed fields — those with a `formula` —
 * with each formula read against the fields it names, and what could not be.
 * A formula that cannot be read, or gives a kind its field cannot hold, makes
 * its field no computed field at all: it is a problem, and the value is left
 * as it is.
 */
export function schemaDerivations(definition: ObjectSchema): {
  readonly plan: DerivedPlan;
  readonly problems: readonly FormulaProblem[];
  /** Whether any formula reads today's date, and so changes from day to day. */
  readonly volatile: boolean;
} {
  const fields = new Map(definition.fields.map((field) => [field.key, resolve(field.schema)]));
  const scope = (path: string): FormulaType | undefined => {
    const dot = path.indexOf(".");
    const own = fields.get(dot === -1 ? path : path.slice(0, dot));
    if (own === undefined) return undefined;
    if (dot === -1) return own.kind === "list" ? listOf(formulaType(own.item)) : formulaType(own);
    if (own.kind !== "list") return undefined;
    const item = resolve(own.item);
    if (item.kind !== "object") return undefined;
    const inner = item.fields.find((field) => field.key === path.slice(dot + 1));
    return inner === undefined ? undefined : listOf(formulaType(inner.schema));
  };
  const derivations: Derivation[] = [];
  const problems: FormulaProblem[] = [];
  let volatile = false;
  for (const { key, schema } of definition.fields) {
    const text = schema.formula;
    if (text === undefined) continue;
    const compiled = compileFormula(text, scope);
    if (!compiled.ok) {
      problems.push({ key, message: compiled.message, at: compiled.at, length: compiled.length });
      continue;
    }
    const wanted = formulaType(schema);
    if (wanted === undefined || compiled.type !== wanted) {
      problems.push({
        key,
        message:
          wanted === undefined
            ? "This field cannot be computed."
            : `This formula gives ${describe(compiled.type)}, and the field holds ${describe(wanted)}.`,
        at: 0,
        length: text.length,
      });
      continue;
    }
    volatile ||= compiled.volatile;
    derivations.push({ key, references: compiled.references, evaluate: compiled.evaluate });
  }
  const plan = planDerivations(derivations);
  for (const key of plan.cyclic) {
    const text = fields.get(key)?.formula ?? "";
    problems.push({
      key,
      message: "This formula depends on itself, through the fields it reads.",
      at: 0,
      length: text.length,
    });
  }
  return { plan, problems, volatile };
}

const derivationsOfSchema = new WeakMap<ObjectSchema, ReturnType<typeof schemaDerivations>>();

/** `schemaDerivations`, read once for each schema object however often it is asked. */
export function derivationsOf(definition: ObjectSchema): ReturnType<typeof schemaDerivations> {
  let found = derivationsOfSchema.get(definition);
  if (found === undefined) {
    found = schemaDerivations(definition);
    derivationsOfSchema.set(definition, found);
  }
  return found;
}

const isRecord = (value: unknown): value is AnyRecord =>
  typeof value === "object" && value !== null && !Array.isArray(value);

/** The record schema a value of this schema is read as: a record's own, or a variant's chosen one. */
function recordSchemaOf(stated: Schema, value: AnyRecord): ObjectSchema | undefined {
  const definition = resolve(stated);
  if (definition.kind === "object") return definition;
  if (definition.kind !== "variant") return undefined;
  return definition.variants.find((variant) => variant.value === value[definition.tag])?.schema;
}

/** A value made right throughout, recomputing only within what differs from `before`. */
function deriveValue(stated: Schema, before: unknown, after: unknown): unknown {
  if (Object.is(before, after)) return after;
  if (Array.isArray(after)) {
    const definition = resolve(stated);
    if (definition.kind !== "list") return after;
    const was = Array.isArray(before) ? before : [];
    let next: unknown[] | undefined;
    for (let index = 0; index < after.length; index += 1) {
      const item = deriveValue(definition.item, was[index], after[index]);
      if (next === undefined && !Object.is(item, after[index])) next = after.slice(0, index);
      next?.push(item);
    }
    return next ?? after;
  }
  if (!isRecord(after)) return after;
  const own = recordSchemaOf(stated, after);
  if (own === undefined) return after;
  const inner = deriveNested(own, before, after);
  const was = isRecord(before) ? before : undefined;
  const { plan } = derivationsOf(own);
  if (was === undefined) return deriveRecord(plan, inner);
  const changed: string[] = [];
  for (const key of new Set([...Object.keys(was), ...Object.keys(inner)])) {
    if (!Object.is(was[key], inner[key])) changed.push(key);
  }
  return deriveRecord(plan, inner, { changed });
}

/**
 * A record with the computed fields of every record within it made right — in
 * its records, its lists of records and its variants, at any depth — and its
 * own left for the caller, who knows its locks. Only what differs from `before`
 * is looked into; what is the same object is passed by. A record within, that
 * was not there before, is computed whole.
 */
export function deriveNested<R extends AnyRecord>(definition: ObjectSchema, before: unknown, after: R): R {
  const was = isRecord(before) ? before : undefined;
  let next: Record<string, unknown> | undefined;
  for (const { key, schema } of definition.fields) {
    const value = after[key];
    const derived = deriveValue(schema, was?.[key], value);
    if (Object.is(derived, value)) continue;
    next ??= { ...after };
    next[key] = derived;
  }
  return (next ?? after) as R;
}

const describe = (type: FormulaType): string =>
  type.startsWith("list-") ? `a list of ${type.slice(5)}s` : type === "text" ? "text" : `a ${type}`;

/**
 * The value for `free` that keeps the computed field `held` at the value it has
 * once `record` has changed — the third way a lock can go: the total is agreed,
 * the quantity changes, the price makes up the difference. Found by the secant
 * method from the free field's own value, which a formula of the first degree
 * (most of them) settles in one step. A value is given only if it keeps the
 * held one exactly, once `round` has had it — made to the free field's
 * precision, say; `null` if there is none to be found.
 */
export function balance(
  plan: DerivedPlan,
  record: AnyRecord,
  held: string,
  free: string,
  target: number,
  round: (value: number) => number = (value) => value,
): number | null {
  const start = record[free];
  // A value that is not a number has nothing to start from; one not finite finds nothing either.
  if (typeof start !== "number") return null;
  const at = (value: number) => {
    const result = deriveRecord(plan, { ...record, [free]: value }, { changed: [free] })[held];
    return typeof result === "number" ? result : Number.NaN;
  };
  const keeps = (value: number) => Object.is(at(value), target);
  // Nothing to look for: a step saved, not a different answer.
  if (keeps(start)) return start;
  let x0 = start;
  let x1 = start === 0 ? 1 : start * 1.01;
  let f0 = at(x0) - target;
  let f1 = at(x1) - target;
  for (let step = 0; step < 60 && Number.isFinite(f0) && Number.isFinite(f1); step += 1) {
    if (f1 === f0) break;
    const x2 = x1 - (f1 * (x1 - x0)) / (f1 - f0);
    if (!Number.isFinite(x2)) break;
    const rounded = round(x2);
    if (keeps(rounded)) return rounded;
    [x0, f0] = [x1, f1];
    [x1, f1] = [x2, at(x2) - target];
    if (Math.abs(f1) <= Number.EPSILON * Math.max(1, Math.abs(target))) break;
  }
  const near = round(x1);
  return keeps(near) ? near : null;
}