SPB Git

Repository Public

expr.ts 9.5 KB 211 lines typescript

1/**2 * Safe arithmetic expressions for `function-plot`.3 *4 * A document (possibly written by a model) supplies a formula as text. It is never executed as code: this module5 * tokenises it, parses it by recursive descent into a small tree, and walks that tree. There is no `eval`, no6 * `Function`, no property access, no string, no assignment — only numbers, names, operators and a fixed list of functions.7 *8 *   expr    := term (("+" | "-") term)*9 *   term    := unary (("*" | "/") unary)*10 *   unary   := ("-" | "+") unary | power11 *   power   := primary ("^" unary)?            right-associative; −x^2 = −(x^2)12 *   primary := number | name | name "(" expr ("," expr)* ")" | "(" expr ")"13 */1415export const MAX_EXPR_LENGTH = 300;16export const MAX_EXPR_DEPTH = 32;1718export class ExprError extends Error {19  constructor(message: string, readonly position: number) { super(message); this.name = "ExprError"; }20}2122export type ExprNode =23  | { t: "num"; v: number }24  | { t: "var"; name: string }25  | { t: "neg"; a: ExprNode }26  | { t: "bin"; op: "+" | "-" | "*" | "/" | "^"; a: ExprNode; b: ExprNode }27  | { t: "call"; fn: string; args: ExprNode[] };2829export interface ParsedExpr {30  source: string;31  ast: ExprNode;32  /** Free names in order of first appearance (constants and function names excluded): `x` and the parameters. */33  variables: string[];34}3536interface Fn { min: number; max: number; f: (...a: number[]) => number }37const one = (f: (x: number) => number): Fn => ({ min: 1, max: 1, f });38const FUNCTIONS: ReadonlyMap<string, Fn> = new Map<string, Fn>([39  ["exp", one(Math.exp)], ["log", one(Math.log)], ["ln", one(Math.log)], ["log10", one(Math.log10)], ["sqrt", one(Math.sqrt)],40  ["abs", one(Math.abs)], ["sin", one(Math.sin)], ["cos", one(Math.cos)], ["tan", one(Math.tan)], ["tanh", one(Math.tanh)],41  ["sigmoid", one((x) => 1 / (1 + Math.exp(-x)))], ["relu", one((x) => Math.max(0, x))], ["floor", one(Math.floor)],42  ["max", { min: 1, max: 8, f: (...a) => Math.max(...a) }], ["min", { min: 1, max: 8, f: (...a) => Math.min(...a) }],43  ["pow", { min: 2, max: 2, f: (a, b) => Math.pow(a, b) }],44]);45const CONSTANTS: ReadonlyMap<string, number> = new Map([["pi", Math.PI], ["e", Math.E]]);46/** Names that are never accepted, whatever the context: they mean something to JavaScript, not to a formula. */47const FORBIDDEN = new Set([48  "constructor", "prototype", "proto", "toString", "valueOf", "hasOwnProperty", "eval", "Function", "window", "globalThis",49  "global", "self", "document", "this", "import", "require", "process", "new", "return", "function", "class", "await", "async",50  "yield", "delete", "typeof", "void", "var", "let", "const", "fetch", "location", "Object", "Reflect", "Proxy",51]);5253export const EXPR_FUNCTIONS: readonly string[] = [...FUNCTIONS.keys()];54export const EXPR_CONSTANTS: readonly string[] = [...CONSTANTS.keys()];5556type Token = { k: "num"; v: number; pos: number } | { k: "id"; v: string; pos: number } | { k: "op"; v: string; pos: number } | { k: "end"; pos: number };5758function tokenize(src: string): Token[] {59  const out: Token[] = [];60  let i = 0;61  const isDigit = (c: string | undefined) => c !== undefined && c >= "0" && c <= "9";62  const isAlpha = (c: string | undefined) => c !== undefined && ((c >= "a" && c <= "z") || (c >= "A" && c <= "Z"));63  while (i < src.length) {64    const c = src[i];65    if (c === " " || c === "\t" || c === "\n" || c === "\r") { i++; continue; }66    if (isDigit(c) || (c === "." && isDigit(src[i + 1]))) {67      const start = i;68      while (isDigit(src[i])) i++;69      if (src[i] === "." && isDigit(src[i + 1])) { i++; while (isDigit(src[i])) i++; }70      else if (src[i] === "." && !isAlpha(src[i + 1])) i++; // "2." is 271      if ((src[i] === "e" || src[i] === "E") && (isDigit(src[i + 1]) || ((src[i + 1] === "+" || src[i + 1] === "-") && isDigit(src[i + 2])))) {72        i += 2; while (isDigit(src[i])) i++;73      }74      const v = Number(src.slice(start, i));75      if (!Number.isFinite(v)) throw new ExprError(`invalid number "${src.slice(start, i)}" at position ${start + 1}`, start);76      out.push({ k: "num", v, pos: start });77      continue;78    }79    if (isAlpha(c)) {80      const start = i;81      while (isAlpha(src[i]) || isDigit(src[i])) i++;82      out.push({ k: "id", v: src.slice(start, i), pos: start });83      continue;84    }85    if ("+-*/^(),".includes(c)) { out.push({ k: "op", v: c, pos: i }); i++; continue; }86    if (c === ".") throw new ExprError(`property access is not allowed ("." at position ${i + 1})`, i);87    if (c === "_" || c === "$") throw new ExprError(`names may only contain letters and digits ("${c}" at position ${i + 1})`, i);88    throw new ExprError(`unexpected character "${c}" at position ${i + 1}`, i);89  }90  out.push({ k: "end", pos: src.length });91  return out;92}9394/** Parses a formula. Throws ExprError with a message meant to be shown to the author. */95export function parseExpr(source: string): ParsedExpr {96  if (typeof source !== "string") throw new ExprError("the expression must be text", 0);97  if (source.length > MAX_EXPR_LENGTH) throw new ExprError(`expression too long (${source.length} characters, limit ${MAX_EXPR_LENGTH})`, MAX_EXPR_LENGTH);98  if (!source.trim()) throw new ExprError("the expression is empty", 0);99  const tokens = tokenize(source);100  const variables: string[] = [];101  let p = 0;102  let depth = 0;103  const peek = (): Token => tokens[p];104  const isOp = (v: string): boolean => { const t = tokens[p]; return t.k === "op" && t.v === v; };105  const describe = (t: Token): string => (t.k === "end" ? "end of expression" : `"${t.k === "num" ? String(t.v) : t.v}" at position ${t.pos + 1}`);106  const enter = (t: Token) => { if (++depth > MAX_EXPR_DEPTH) throw new ExprError(`expression nested too deeply (limit ${MAX_EXPR_DEPTH})`, t.pos); };107108  const expr = (): ExprNode => {109    enter(peek());110    let a = term();111    while (isOp("+") || isOp("-")) { const op = isOp("+") ? "+" : "-"; p++; a = { t: "bin", op, a, b: term() }; }112    depth--;113    return a;114  };115  const term = (): ExprNode => {116    let a = unary();117    while (isOp("*") || isOp("/")) { const op = isOp("*") ? "*" : "/"; p++; a = { t: "bin", op, a, b: unary() }; }118    return a;119  };120  const unary = (): ExprNode => {121    if (isOp("-") || isOp("+")) {122      const neg = isOp("-");123      enter(peek()); p++;124      const a = unary();125      depth--;126      return neg ? { t: "neg", a } : a;127    }128    return power();129  };130  const power = (): ExprNode => {131    const a = primary();132    if (isOp("^")) { enter(peek()); p++; const b = unary(); depth--; return { t: "bin", op: "^", a, b }; }133    return a;134  };135  const primary = (): ExprNode => {136    const t = peek();137    if (t.k === "num") { p++; return { t: "num", v: t.v }; }138    if (t.k === "id") {139      p++;140      if (FORBIDDEN.has(t.v)) throw new ExprError(`"${t.v}" is not allowed in an expression`, t.pos);141      if (isOp("(")) {142        const fn = FUNCTIONS.get(t.v);143        if (!fn) throw new ExprError(`unknown function "${t.v}" (available: ${EXPR_FUNCTIONS.join(", ")})`, t.pos);144        p++;145        const args: ExprNode[] = [];146        if (!isOp(")")) { args.push(expr()); while (isOp(",")) { p++; args.push(expr()); } }147        if (!isOp(")")) throw new ExprError(`expected ")" to close ${t.v}(…), found ${describe(peek())}`, peek().pos);148        p++;149        if (args.length < fn.min || args.length > fn.max) {150          throw new ExprError(`${t.v}() takes ${fn.min === fn.max ? fn.min : `${fn.min} to ${fn.max}`} argument${fn.max === 1 ? "" : "s"}, got ${args.length}`, t.pos);151        }152        return { t: "call", fn: t.v, args };153      }154      if (FUNCTIONS.has(t.v)) throw new ExprError(`"${t.v}" is a function: write ${t.v}(…)`, t.pos);155      if (CONSTANTS.has(t.v)) return { t: "num", v: CONSTANTS.get(t.v) ?? NaN };156      if (!variables.includes(t.v)) variables.push(t.v);157      return { t: "var", name: t.v };158    }159    if (t.k === "op" && t.v === "(") {160      p++;161      const a = expr();162      if (!isOp(")")) throw new ExprError(`expected ")", found ${describe(peek())}`, peek().pos);163      p++;164      return a;165    }166    throw new ExprError(`unexpected ${describe(t)}`, t.pos);167  };168169  const ast = expr();170  const rest = peek();171  if (rest.k !== "end") throw new ExprError(`unexpected ${describe(rest)}`, rest.pos);172  return { source, ast, variables };173}174175export function tryParseExpr(source: string): { ok: true; expr: ParsedExpr } | { ok: false; error: string } {176  try { return { ok: true, expr: parseExpr(source) }; }177  catch (e) { return { ok: false, error: e instanceof ExprError ? e.message : "invalid expression" }; }178}179180function walk(n: ExprNode, scope: Readonly<Record<string, number>>): number {181  switch (n.t) {182    case "num": return n.v;183    case "var": {184      if (!Object.hasOwn(scope, n.name)) throw new ExprError(`no value for "${n.name}"`, 0);185      return scope[n.name];186    }187    case "neg": return -walk(n.a, scope);188    case "bin": {189      const a = walk(n.a, scope), b = walk(n.b, scope);190      switch (n.op) {191        case "+": return a + b;192        case "-": return a - b;193        case "*": return a * b;194        case "/": return a / b;195        case "^": return Math.pow(a, b);196      }197      return NaN;198    }199    case "call": {200      const fn = FUNCTIONS.get(n.fn);201      return fn ? fn.f(...n.args.map((a) => walk(a, scope))) : NaN;202    }203  }204}205206/** Value of the expression for the given variable values. Anything that is not a finite number comes back as NaN (a gap in the curve). */207export function evaluateExpr(expr: ParsedExpr, scope: Readonly<Record<string, number>>): number {208  const v = walk(expr.ast, scope);209  return Number.isFinite(v) ? v : NaN;210}211
Files main
Menu

Theme