evaluator.ts · Source

evaluator.tspackages/database-engine/src/formula/evaluator.tsraw ← formula11,981 B← Back to the app
1/**
2 * @factory/database-engine/formula — safe AST evaluator (TASK-0084 R5).
3 *
4 * Walks the AST only (zero eval — the CI grep gate). Type rules:
5 *  - arithmetic on non-numbers → TYPE; `date + 1` → TYPE with a "use dateAdd"
6 *    hint;
7 *  - cross-type comparison (number < date) → TYPE; string < string and
8 *    date < date allowed;
9 *  - null in arithmetic → null propagation (`null + 1` = null);
10 *    `null == null` = true, `null == 0` = false;
11 *  - `if`/`and`/`or` are lazy (only the taken branch / until first match).
12 * Budget (TASK-0134): two cooperating DoS guards, both enforced at every
13 * charge point (node visits AND per-argument charges inside function impls):
14 *  - `EVAL_OP_LIMIT` (100k node visits) → `FormulaError("FORMULA_TIMEOUT")`;
15 *  - `EVAL_TIMEOUT_MS` (50 ms wall-clock, cooperative — checked between node
16 *    steps via an injectable `now()`; deterministic in tests, `Date.now()`
17 *    in production) → `FormulaError("FORMULA_TIMEOUT")`.
18 * `FORMULA_TIMEOUT` is the canonical error code (docs/api/authentication.md
19 * §9.1); the API maps it to a 422 with `details[0] = { reason:
20 * "formula_timeout" }`.
21 * There is no separate hard-kill: the AST walk has no yield points beyond
22 * node boundaries, so the per-step cooperative check + op counter IS the cap
23 * (recorded decision — an AbortController-style hard cap would require
24 * re-architecting the walk and buys nothing over the two budgets).
25 * Any output string > 1 MB → RUNTIME (separate output guard, unchanged).
26 */
27 
28import type { AstNode, EValue, FormulaContext, FormulaType } from "./types.js";
29import { FormulaError, EVAL_OP_LIMIT, EVAL_TIMEOUT_MS, MAX_STEPS, MAX_OUTPUT_BYTES } from "./types.js";
30import { FUNCTIONS, type Budget, normalizeProperty, unknownPropertyMessage } from "./functions.js";
31 
32export interface EvalResult {
33  value: EValue;
34  steps: number;
35}
36 
37/** Options for `evaluateFormula`. All optional — back-compat with Phase 6. */
38export interface EvalOptions {
39  /**
40   * Injectable wall clock (epoch ms) for the `EVAL_TIMEOUT_MS` budget.
41   * Defaults to `Date.now`. Tests pin this to make the wall-clock guard
42   * deterministic (e.g. advance it 51 ms mid-evaluation).
43   */
44  now?: () => number;
45}
46 
47function runtime(message: string): never {
48  throw new FormulaError("RUNTIME", message);
49}
50 
51function formulaTimeout(message: string): never {
52  throw new FormulaError("FORMULA_TIMEOUT", message);
53}
54 
55/**
56 * The internal budget carries the wall-clock deadline alongside the public
57 * `Budget` surface (`{ steps, charge }` — unchanged for function impls).
58 * Both DoS guards are enforced in ONE place (`checkBudget`), called from
59 * every charge point (node visits AND `budget.charge(n)` inside impls), so
60 * a hostile expression cannot escape either budget via the other's path.
61 */
62interface InternalBudget extends Budget {
63  deadline: number;
64  now: () => number;
65}
66 
67/** Enforce both budgets; throws FORMULA_TIMEOUT on either violation. */
68function checkBudget(b: InternalBudget): void {
69  if (b.steps > EVAL_OP_LIMIT)
70    formulaTimeout(`Evaluation op limit exceeded (${EVAL_OP_LIMIT} ops)`);
71  if (b.now() > b.deadline)
72    formulaTimeout(`Evaluation wall-clock budget exceeded (${EVAL_TIMEOUT_MS} ms)`);
73}
74 
75export function evaluateFormula(ast: AstNode, ctx: FormulaContext, opts: EvalOptions = {}): EvalResult {
76  const now = opts.now ?? Date.now;
77  const budget: InternalBudget = {
78    steps: 0,
79    now,
80    deadline: now() + EVAL_TIMEOUT_MS,
81    charge(n: number) {
82      budget.steps += n;
83      checkBudget(budget);
84    },
85  };
86  const ev = walk(ast, ctx, budget);
87  checkBudget(budget);
88  checkOutput(ev);
89  return { value: ev, steps: budget.steps };
90}
91 
92function checkOutput(ev: EValue): void {
93  if (ev.t === "string" && (ev.v as string).length > MAX_OUTPUT_BYTES)
94    runtime("Evaluation output exceeds 1 MB");
95  if (ev.t === "array") for (const x of ev.v as EValue[]) checkOutput(x);
96}
97 
98function charge(budget: InternalBudget): void {
99  budget.steps++;
100  checkBudget(budget);
101}
102 
103function walk(node: AstNode, ctx: FormulaContext, budget: InternalBudget): EValue {
104  charge(budget);
105  switch (node.type) {
106    case "Literal": {
107      if (node.literalType === "number") return { v: node.value as number, t: "number" };
108      if (node.literalType === "string") return { v: node.value as string, t: "string" };
109      if (node.literalType === "date") return { v: node.value as string, t: "date" };
110      return { v: node.value as boolean, t: "bool" };
111    }
112    case "NullLiteral":
113      return { v: null, t: "null" };
114    case "ArrayLiteral":
115      return { v: node.elements.map((e) => walk(e, ctx, budget)), t: "array" };
116    case "Prop": {
117      const v = ctx.properties[node.name];
118      if (v === undefined)
119        throw new FormulaError(
120          "TYPE",
121          unknownPropertyMessage(node.name, ctx),
122          undefined,
123          node.name,
124        );
125      return normalizeProperty(v, ctx, node.name);
126    }
127    case "Call": {
128      const fn = FUNCTIONS[node.name];
129      if (!fn) throw new FormulaError("UNKNOWN_FUNCTION", `unknown function "${node.name}"`);
130      const [min, max] = fn.arity;
131      if (node.args.length < min || (Number.isFinite(max) && node.args.length > max)) {
132        throw new FormulaError(
133          "TYPE",
134          `${node.name}() expects ${min === max ? min : `${min}–${Number.isFinite(max) ? max : "∞"}`} arguments, got ${node.args.length}`,
135        );
136      }
137      // `and(...)` / `or(...)` are LAZY: walk args left→right, short-circuit on
138      // the first decisive value, propagate null only when nothing decisive.
139      if (node.name === "and" || node.name === "or") {
140        const wantTrue = node.name === "or";
141        let sawNull = false;
142        for (const a of node.args) {
143          const v = walk(a, ctx, budget);
144          if (v.t === "null") {
145            sawNull = true;
146            continue;
147          }
148          if (v.t !== "bool") typeErr(`${node.name}() requires bool arguments, got ${v.t}`);
149          // decisive value: and → false, or → true; otherwise keep walking
150          if ((v.v as boolean) === wantTrue) return { v: wantTrue, t: "bool" };
151        }
152        return sawNull ? { v: null, t: "null" } : { v: !wantTrue, t: "bool" }; // all-true and / all-false or
153      }
154      // `prop(name)` is evaluated with the literal argument (it IS the lookup)
155      const args = node.args.map((a): EValue =>
156        node.name === "prop" && a.type === "Literal"
157          ? { v: a.value as string, t: "string" }
158          : walk(a, ctx, budget),
159      );
160      return fn.impl(args, ctx, budget);
161    }
162    case "UnaryOp": {
163      if (node.op === "-") {
164        const v = walk(node.operand, ctx, budget);
165        if (v.t === "null") return { v: null, t: "null" };
166        if (v.t !== "number") typeErr(`-x requires a number, got ${v.t}`);
167        return { v: -(v.v as number), t: "number" };
168      }
169      const v = walk(node.operand, ctx, budget);
170      if (v.t === "null") return { v: null, t: "null" };
171      if (v.t !== "bool") typeErr(`not requires a bool, got ${v.t}`);
172      return { v: !(v.v as boolean), t: "bool" };
173    }
174    case "BinaryOp":
175      return binaryOp(node, ctx, budget);
176    case "If": {
177      const cond = walk(node.cond, ctx, budget);
178      if (cond.t === "null") return { v: null, t: "null" }; // null cond → null propagation (documented)
179      if (cond.t !== "bool") typeErr(`if(cond) requires a bool, got ${cond.t}`);
180      // lazy: only the taken branch is walked
181      return (cond.v as boolean) ? walk(node.then, ctx, budget) : walk(node.else, ctx, budget);
182    }
183  }
184}
185 
186function typeErr(message: string): never {
187  throw new FormulaError("TYPE", message);
188}
189 
190function isNumericType(t: FormulaType): boolean {
191  return t === "number";
192}
193function isComparablePair(a: FormulaType, b: FormulaType): boolean {
194  if (a === "null" || b === "null") return true; // equality with null handled below
195  if (a === b) return a === "number" || a === "string" || a === "date" || a === "bool";
196  return false;
197}
198 
199function binaryOp(
200  node: Extract<AstNode, { type: "BinaryOp" }>,
201  ctx: FormulaContext,
202  budget: InternalBudget,
203): EValue {
204  const op = node.op;
205  const logical = op === "and" || op === "or";
206  const comparison =
207    op === "==" || op === "!=" || op === "<" || op === "<=" || op === ">" || op === ">=";
208  // lazy logical ops
209  if (logical) {
210    const l = walk(node.left, ctx, budget);
211    if (l.t === "null") return { v: null, t: "null" };
212    if (l.t !== "bool") typeErr(`${op} requires bool operands, got ${l.t}`);
213    const lBool = l.v as boolean;
214    if ((op === "and" && !lBool) || (op === "or" && lBool)) return { v: lBool, t: "bool" };
215    const r = walk(node.right, ctx, budget);
216    if (r.t === "null") return { v: null, t: "null" };
217    if (r.t !== "bool") typeErr(`${op} requires bool operands, got ${r.t}`);
218    return { v: op === "and" ? (r.v as boolean) : true, t: "bool" };
219  }
220 
221  const l = walk(node.left, ctx, budget);
222  const r = walk(node.right, ctx, budget);
223 
224  // equality / inequality: null semantics — null == null → true, null == 0 → false
225  if (op === "==" || op === "!=") {
226    const eq = (a: EValue, b: EValue): boolean => {
227      if (a.t === "null" || b.t === "null") return a.t === "null" && b.t === "null";
228      if (a.t !== b.t) return false;
229      if (a.t === "array") {
230        const av = a.v as EValue[],
231          bv = b.v as EValue[];
232        if (av.length !== bv.length) return false;
233        return av.every((x, i) => eq(x, bv[i]!));
234      }
235      return (a.v as unknown) === (b.v as unknown);
236    };
237    const result = op === "==" ? eq(l, r) : !eq(l, r);
238    return { v: result, t: "bool" };
239  }
240 
241  // ordering comparisons
242  if (comparison) {
243    if (l.t === "null" || r.t === "null") return { v: false, t: "bool" }; // nulls never order
244    if (!isComparablePair(l.t, r.t)) typeErr(`cannot compare ${l.t} with ${r.t}`);
245    let cmp = 0;
246    if (l.t === "number" && r.t === "number") cmp = (l.v as number) - (r.v as number);
247    else if (l.t === "date" && r.t === "date") {
248      const lt = new Date(
249        (l.v as string).length === 10 ? (l.v as string) + "T00:00:00Z" : (l.v as string),
250      ).getTime();
251      const rt = new Date(
252        (r.v as string).length === 10 ? (r.v as string) + "T00:00:00Z" : (r.v as string),
253      ).getTime();
254      cmp = lt - rt;
255    } else if (l.t === "string" && r.t === "string")
256      cmp = (l.v as string) < (r.v as string) ? -1 : (l.v as string) > (r.v as string) ? 1 : 0;
257    else if (l.t === "bool" && r.t === "bool") cmp = Number(l.v) - Number(r.v);
258    const result = op === "<" ? cmp < 0 : op === "<=" ? cmp <= 0 : op === ">" ? cmp > 0 : cmp >= 0;
259    return { v: result, t: "bool" };
260  }
261 
262  // arithmetic
263  if (op === "+" || op === "-" || op === "*" || op === "/" || op === "%") {
264    if (op === "+" && (l.t === "date" || r.t === "date")) {
265      typeErr(`date arithmetic requires dateAdd(date, amount, unit), got date ${op} value`);
266    }
267    // null propagation in arithmetic (documented: null + 1 = null)
268    if (l.t === "null" || r.t === "null") return { v: null, t: "null" };
269    if (!isNumericType(l.t) || !isNumericType(r.t))
270      typeErr(`arithmetic ${op} requires number operands, got ${l.t} and ${r.t}`);
271    const a = l.v as number;
272    const b = r.v as number;
273    let out: number;
274    switch (op) {
275      case "+":
276        out = a + b;
277        break;
278      case "-":
279        out = a - b;
280        break;
281      case "*":
282        out = a * b;
283        break;
284      case "/":
285        if (b === 0) return { v: null, t: "null" }; // 1/0 = null (no Infinity/NaN leaks)
286        out = a / b;
287        break;
288      case "%":
289        if (b === 0) return { v: null, t: "null" };
290        out = a % b;
291        break;
292      default:
293        out = a;
294    }
295    if (!Number.isFinite(out)) return { v: null, t: "null" };
296    return { v: out, t: "number" };
297  }
298 
299  typeErr(`unknown operator "${op}"`);
300}
301 
302export { FUNCTIONS as _FUNCTIONS };
303