Repository Public
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