Build a Spreadsheet Formula Engine

// src/spreadsheet/engine.ts — Formula engine with parsing, dependency tracking, and recalculation

type CellValue = string | number | boolean | null;
type CellRef = { col: number; row: number };

interface Cell {
  ref: string;               // "A1", "B2", etc.
  rawValue: string;          // what the user typed ("=SUM(A1:A5)" or "42")
  computedValue: CellValue;  // the result after formula evaluation
  formula: boolean;          // true if rawValue starts with "="
  dependencies: string[];    // cell refs this cell depends on
  dependents: string[];      // cells that depend on this cell
  error: string | null;
}

interface Sheet {
  id: string;
  cells: Map<string, Cell>;
  name: string;
}

// Built-in functions
const FUNCTIONS: Record<string, (...args: any[]) => CellValue> = {
  SUM: (...args) => args.flat(Infinity).filter((v): v is number => typeof v === "number").reduce((a, b) => a + b, 0),
  AVERAGE: (...args) => {
    const nums = args.flat(Infinity).filter((v): v is number => typeof v === "number");
    return nums.length > 0 ? nums.reduce((a, b) => a + b, 0) / nums.length : 0;
  },
  MIN: (...args) => Math.min(...args.flat(Infinity).filter((v): v is number => typeof v === "number")),
  MAX: (...args) => Math.max(...args.flat(Infinity).filter((v): v is number => typeof v === "number")),
  COUNT: (...args) => args.flat(Infinity).filter((v) => typeof v === "number").length,
  COUNTA: (...args) => args.flat(Infinity).filter((v) => v !== null && v !== "").length,
  IF: (condition, trueVal, falseVal) => condition ? trueVal : falseVal,
  AND: (...args) => args.flat(Infinity).every(Boolean),
  OR: (...args) => args.flat(Infinity).some(Boolean),
  NOT: (val) => !val,
  ABS: (val) => Math.abs(Number(val)),
  ROUND: (val, decimals = 0) => Number(Number(val).toFixed(decimals)),
  CEIL: (val) => Math.ceil(Number(val)),
  FLOOR: (val) => Math.floor(Number(val)),
  CONCATENATE: (...args) => args.flat(Infinity).join(""),
  LEFT: (text, n) => String(text).slice(0, n),
  RIGHT: (text, n) => String(text).slice(-n),
  LEN: (text) => String(text).length,
  UPPER: (text) => String(text).toUpperCase(),
  LOWER: (text) => String(text).toLowerCase(),
  TRIM: (text) => String(text).trim(),
  NOW: () => new Date().toISOString(),
  TODAY: () => new Date().toISOString().slice(0, 10),
  ISNUMBER: (val) => typeof val === "number",
  ISBLANK: (val) => val === null || val === "" || val === undefined,
};

// Parse and evaluate a formula
export function evaluate(formula: string, getCellValue: (ref: string) => CellValue): CellValue {
  // Remove leading "="
  const expr = formula.startsWith("=") ? formula.slice(1) : formula;
  return parseExpression(expr.trim(), getCellValue);
}

function parseExpression(expr: string, getCellValue: (ref: string) => CellValue): CellValue {
  // Handle function calls: SUM(A1:A5)
  const funcMatch = expr.match(/^([A-Z]+)\((.*)\)$/i);
  if (funcMatch) {
    const funcName = funcMatch[1].toUpperCase();
    const func = FUNCTIONS[funcName];
    if (!func) throw new Error(`Unknown function: ${funcName}`);

    const args = parseArguments(funcMatch[2], getCellValue);
    return func(...args);
  }

  // Handle cell ranges: A1:A5
  if (/^[A-Z]+\d+:[A-Z]+\d+$/i.test(expr)) {
    return expandRange(expr, getCellValue);
  }

  // Handle cell reference: A1
  if (/^[A-Z]+\d+$/i.test(expr)) {
    return getCellValue(expr.toUpperCase());
  }

  // Handle comparison operators
  for (const op of ["<=", ">=", "<>", "=", "<", ">"]) {
    const parts = splitExpression(expr, op);
    if (parts) {
      const left = parseExpression(parts[0], getCellValue);
      const right = parseExpression(parts[1], getCellValue);
      switch (op) {
        case "=": return left === right;
        case "<>": return left !== right;
        case "<": return Number(left) < Number(right);
        case ">": return Number(left) > Number(right);
        case "<=": return Number(left) <= Number(right);
        case ">=": return Number(left) >= Number(right);
      }
    }
  }

  // Handle arithmetic: +, -, *, /
  for (const op of ["+", "-", "*", "/"]) {
    const parts = splitExpression(expr, op);
    if (parts) {
      const left = Number(parseExpression(parts[0], getCellValue));
      const right = Number(parseExpression(parts[1], getCellValue));
      switch (op) {
        case "+": return left + right;
        case "-": return left - right;
        case "*": return left * right;
        case "/": return right !== 0 ? left / right : null;
      }
    }
  }

  // Handle string literals
  if (expr.startsWith('"') && expr.endsWith('"')) return expr.slice(1, -1);

  // Handle numbers
  if (!isNaN(Number(expr))) return Number(expr);

  // Handle booleans
  if (expr.toUpperCase() === "TRUE") return true;
  if (expr.toUpperCase() === "FALSE") return false;

  return expr;  // return as string
}

function parseArguments(argsStr: string, getCellValue: (ref: string) => CellValue): any[] {
  const args: any[] = [];
  let depth = 0;
  let current = "";

  for (const char of argsStr) {
    if (char === "(" ) depth++;
    if (char === ")") depth--;
    if (char === "," && depth === 0) {
      args.push(parseExpression(current.trim(), getCellValue));
      current = "";
    } else {
      current += char;
    }
  }
  if (current.trim()) args.push(parseExpression(current.trim(), getCellValue));

  return args;
}

function expandRange(range: string, getCellValue: (ref: string) => CellValue): CellValue[] {
  const [start, end] = range.split(":");
  const startRef = parseCellRef(start);
  const endRef = parseCellRef(end);
  const values: CellValue[] = [];

  for (let row = startRef.row; row <= endRef.row; row++) {
    for (let col = startRef.col; col <= endRef.col; col++) {
      const ref = `${String.fromCharCode(65 + col)}${row}`;
      values.push(getCellValue(ref));
    }
  }

  return values;
}

function parseCellRef(ref: string): CellRef {
  const col = ref.charCodeAt(0) - 65;
  const row = parseInt(ref.slice(1));
  return { col, row };
}

function splitExpression(expr: string, operator: string): [string, string] | null {
  let depth = 0;
  // Search from right for +/- (lower precedence) and left for */
  const searchFromRight = ["+", "-"].includes(operator);
  const start = searchFromRight ? expr.length - 1 : 0;
  const end = searchFromRight ? -1 : expr.length;
  const step = searchFromRight ? -1 : 1;

  for (let i = start; i !== end; i += step) {
    if (expr[i] === "(") depth++;
    if (expr[i] === ")") depth--;
    if (depth === 0 && expr.slice(i, i + operator.length) === operator && i > 0 && i < expr.length - 1) {
      return [expr.slice(0, i), expr.slice(i + operator.length)];
    }
  }
  return null;
}

// Track dependencies and detect circular references
export function getDependencies(formula: string): string[] {
  const refs = formula.match(/[A-Z]+\d+/gi) || [];
  // Expand ranges
  const rangePattern = /([A-Z]+\d+):([A-Z]+\d+)/gi;
  let match;
  while ((match = rangePattern.exec(formula)) !== null) {
    const expanded = expandRange(match[0], () => null).map((_, i) => {
      const startRef = parseCellRef(match![1]);
      const col = startRef.col + (i % (parseCellRef(match![2]).col - startRef.col + 1));
      const row = startRef.row + Math.floor(i / (parseCellRef(match![2]).col - startRef.col + 1));
      return `${String.fromCharCode(65 + col)}${row}`;
    });
    refs.push(...expanded);
  }
  return [...new Set(refs.map((r) => r.toUpperCase()))];
}

export function detectCircularRef(cellRef: string, deps: string[], allDeps: Map<string, string[]>): boolean {
  const visited = new Set<string>();
  function dfs(ref: string): boolean {
    if (ref === cellRef) return true;
    if (visited.has(ref)) return false;
    visited.add(ref);
    const cellDeps = allDeps.get(ref) || [];
    return cellDeps.some((d) => dfs(d));
  }
  return deps.some((d) => dfs(d));
}

// Recalculate affected cells in topological order
export function recalculate(
  changedCell: string,
  sheet: Sheet
): Map<string, CellValue> {
  const updates = new Map<string, CellValue>();
  const toRecalc: string[] = [changedCell];
  const visited = new Set<string>();

  while (toRecalc.length > 0) {
    const ref = toRecalc.shift()!;
    if (visited.has(ref)) continue;
    visited.add(ref);

    const cell = sheet.cells.get(ref);
    if (!cell) continue;

    if (cell.formula) {
      try {
        const value = evaluate(cell.rawValue, (r) => {
          const c = sheet.cells.get(r);
          return c ? c.computedValue : null;
        });
        cell.computedValue = value;
        cell.error = null;
      } catch (e: any) {
        cell.error = e.message;
        cell.computedValue = null;
      }
      updates.set(ref, cell.computedValue);
    }

    // Add dependents to recalculation queue
    for (const dep of cell.dependents) {
      toRecalc.push(dep);
    }
  }

  return updates;
}